GitHub

Free Associative Algebras

Two-sided ideals

Types

The OSCAR type for two-sided ideals in a free associative algebra is FreeAssociativeAlgebraIdeal{T}, where T is the element type of the algebra.

Constructors

ideal(R::FreeAssociativeAlgebra, g::Vector{T}) where T <: FreeAssociativeAlgebraElem
ideal(g::Vector{T}) where T <: FreeAssociativeAlgebraElem

Ideal Membership

Non-commutative polynomial rings are not Noetherian. Hence, in general, Groebner bases do not exist. Hence calling the functions below may not terminate. Picking suitable term orders is difficult in the noncommutative case. Therefore, we fix the term order to be degree reverse lexicographic.

Setting the parameter deg_bound to a positive value yields the truncation of the Groebner bases to a fixed degree. Such a truncation is always finite.

groebner_basis — Function
groebner_basis(I::FreeAssociativeAlgebraIdeal, deg_bound::Int=-1; ordering::Symbol=:deglex, protocol::Bool=false, interreduce::Bool=false, algorithm::Symbol=:f4, probabilistic::Bool=false)
groebner_basis(g::Vector{<:FreeAssociativeAlgebraElem}, deg_bound::Int=-1; ordering::Symbol=:deglex, protocol::Bool=false, interreduce::Bool=false, algorithm::Symbol=:f4, probabilistic::Bool=false)

Compute the Groebner basis for a vector of generators g in a free associative algebra. Supports several algorithms and options for degree bounds, ordering, protocol, and interreduction.

By default (algorithm=:default), the algorithm is chosen as follows:

  • If ordering == :deglex and the base ring is QQ, use :f4.
  • If deg_bound == -1, use :buchberger.
  • Otherwise, use :letterplace.

Arguments

  • g::Vector{<:FreeAssociativeAlgebraElem}: Generators of the ideal.
  • deg_bound::Int: Degree bound for the computation (default: -1).
  • ordering::Symbol: Monomial ordering (default: :deglex).
  • protocol::Bool: Whether to return the computation protocol (default: false).
  • interreduce::Bool: Whether to interreduce the result (default: false).
  • algorithm::Symbol: Algorithm to use (:f4, :buchberger, :letterplace, or :default). If set to :default, the algorithm is chosen automatically based on the input.
  • probabilistic::Bool: Enable probabilistic behavior (default: false).

Returns

  • The Groebner basis as a vector of free associative algebra elements.
julia> free, (x,y,z) = free_associative_algebra(QQ, [:x, :y, :z]);

julia> f1 = x*y + y*z;

julia> f2 = x^2 + y^2;

julia> I = ideal([f1, f2]);

julia> gb = groebner_basis(I, 3; protocol=false)
Ideal generating system with elements
  1: x*y + y*z
  2: x^2 + y^2
  3: y^3 + y*z^2
  4: y^2*x + y*z*y
source

If a finite Gröbner basis exists, it solves the ideal membership problem.

ideal_membership — Method
ideal_membership(a::FreeAssociativeAlgebraElem, I::FreeAssociativeAlgebraIdeal, deg_bound::Int)

Return true if intermediate degree calculations bounded by deg_bound prove that $a$ is in $I$. Otherwise, returning false indicates an inconclusive answer, but larger deg_bounds give more confidence in a negative answer. If deg_bound is not specified, the default value is -1, which means that no degree bound is imposed, resulting in a calculation using a much slower algorithm that may not terminate, but will return a full Groebner basis if it does.

julia> free, (x,y,z) = free_associative_algebra(QQ, [:x, :y, :z]);

julia> f1 = x*y + y*z;

julia> I = ideal([f1]);

julia> ideal_membership(f1, I, 4)
true
source