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 <: FreeAssociativeAlgebraElemIdeal 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 — Functiongroebner_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 == :deglexand the base ring isQQ, 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*yIf a finite Gröbner basis exists, it solves the ideal membership problem.
ideal_membership — Methodideal_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