GitHub

Free Associative Algebras

Two-sided ideals

Types

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

Constructors

ideal(R::FreeAssAlgebra, g::Vector{T}) where T <: FreeAssAlgElem
ideal(g::Vector{T}) where T <: FreeAssAlgElem

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::FreeAssAlgIdeal, deg_bound::Int=-1; protocol::Bool=false)

Return the Groebner basis of I with respect to the degree bound deg_bound. If protocol is true, the protocol of the computation is also returned. The default value of deg_bound is -1, which means that no degree bound is imposed, which leads to a computation that uses a much slower algorithm, that may not terminate, but returns 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> 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::FreeAssAlgElem, I::FreeAssAlgIdeal, deg_bound::Int)

Returns 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