Free algebras
AbstractAlgebra.jl provides a module, implemented in src/FreeAssociativeAlgebra.jl
for free associative algebras over any commutative ring belonging to the AbstractAlgebra abstract type hierarchy.
Generic free algebra types
AbstractAlgebra provides a generic type Generic.FreeAssociativeAlgebraElem{T}
where T
is the type of elements of the coefficient ring. The elements are implemented using a Julia array of coefficients and a vector of vectors of Int
s for the monomial words. Parent objects of such elements have type Generic.FreeAssociativeAlgebra{T}
.
The element types belong to the abstract type NCRingElem
, and the algebra types belong to the abstract type NCRing
.
The following basic functions are implemented.
base_ring(R::FreeAssociativeAlgebra)
base_ring(a::FreeAssociativeAlgebraElem)
parent(a::FreeAssociativeAlgebraElem)
characteristic(R::FreeAssociativeAlgebra)
Free algebra constructors
free_associative_algebra(R::Ring, s::AbstractVector{<:VarName}; cached::Bool = true)
free_associative_algebra(R::Ring, n::Int, s::VarName; cached::Bool = false)
The first constructor, given a base ring R
and an array s
of variables, will return a tuple S, (x, ...)
representing the new algebra $S = R \left<x, \ldots \right>$ and a tuple of generators $(x, ...)$.
The second constructor given a string s
and a number of variables n
will do the same as the first constructor except that the variables will be automatically numbered as, s1
, s2
, ..., sn
.
By default the parent object S
will depend only on R
and (x, ...)
and will be cached. Setting the optional argument cached
to false
will prevent the parent object S
from being cached.
Examples
julia> R, (x, y) = free_associative_algebra(ZZ, [:x, :y])
(Free associative algebra on 2 indeterminates over integers, AbstractAlgebra.Generic.FreeAssociativeAlgebraElem{BigInt}[x, y])
julia> (x + y + 1)^2
x^2 + x*y + y*x + y^2 + 2*x + 2*y + 1
julia> (x*y*x*x)^4
x*y*x^3*y*x^3*y*x^3*y*x^2
Free algebra element constructors
Elements of a free algebra can be constructed from the generators in the usual way using arithmetic operations. Also, all of the standard ring element constructors may be used. Finally, the MPolyBuildCtx
is overloaded to work with coefficients and monomial words and not exponent vectors.
Examples
julia> R, (x, y, z) = free_associative_algebra(ZZ, [:x, :y, :z])
(Free associative algebra on 3 indeterminates over integers, AbstractAlgebra.Generic.FreeAssociativeAlgebraElem{BigInt}[x, y, z])
julia> B = MPolyBuildCtx(R)
Builder for an element of R
julia> push_term!(B, ZZ(1), [1,2,3,1]); push_term!(B, ZZ(2), [3,3,1]); finish(B)
x*y*z*x + 2*z^2*x
julia> push_term!(B, ZZ(3), [3,3,3]); push_term!(B, ZZ(4), Int[]); finish(B)
3*z^3 + 4
julia> [gen(R, 2), R(9)]
2-element Vector{AbstractAlgebra.Generic.FreeAssociativeAlgebraElem{BigInt}}:
y
9
Element functions
Basic manipulation
The standard ring functions are available. The following functions from the multivariate polynomial interface are provided.
symbols(S::FreeAssociativeAlgebra)
number_of_variables(f::FreeAssociativeAlgebra)
gens(S::FreeAssociativeAlgebra)
gen(S::FreeAssociativeAlgebra, i::Int)
is_gen(x::FreeAssociativeAlgebraElem)
total_degree(a::FreeAssociativeAlgebraElem)
length(f::FreeAssociativeAlgebraElem)
As with multivariate polynomials, an implementation must provide access to the elements as a sum of individual terms in some order. The length
function provides the number of such terms, and the following functions provide the first such term.
leading_coefficient(a::FreeAssociativeAlgebraElem)
leading_monomial(a::FreeAssociativeAlgebraElem)
leading_term(a::FreeAssociativeAlgebraElem)
leading_exponent_word(a::FreeAssociativeAlgebraElem)
For types that allow constant time access to coefficients, the following are also available, allowing access to the given coefficient, monomial or term. Terms are numbered from the most significant first.
coeff(f::FreeAssociativeAlgebraElem, n::Int)
monomial(f::FreeAssociativeAlgebraElem, n::Int)
term(f::FreeAssociativeAlgebraElem, n::Int)
In contrast with the interface for multivariable polynomials, the function exponent_vector
is replaced by exponent_word
AbstractAlgebra.Generic.exponent_word
— Methodexponent_word(a::FreeAssociativeAlgebraElem{T}, i::Int) where T <: RingElement
Return a vector of variable indices corresponding to the monomial of the $i$-th term of $a$. Term numbering begins at $1$, and the variable indices are given in the order of the variables for the ring.
Examples
julia> R, (x, y, z) = free_associative_algebra(ZZ, [:x, :y, :z])
(Free associative algebra on 3 indeterminates over integers, AbstractAlgebra.Generic.FreeAssociativeAlgebraElem{BigInt}[x, y, z])
julia> map(total_degree, (R(0), R(1), -x^2*y^2*z^2*x + z*y))
(-1, 0, 7)
julia> leading_term(-x^2*y^2*z^2*x + z*y)
-x^2*y^2*z^2*x
julia> leading_monomial(-x^2*y^2*z^2*x + z*y)
x^2*y^2*z^2*x
julia> leading_coefficient(-x^2*y^2*z^2*x + z*y)
-1
julia> exponent_word(-x^2*y^2*z^2*x + z*y, 1)
7-element Vector{Int64}:
1
1
2
2
3
3
1
AbstractAlgebra.evaluate
— Methodevaluate(a::FreeAssociativeAlgebraElem{T}, vals::Vector{U}) where {T <: RingElement, U <: NCRingElem}
Evaluate a
by substituting in the array of values for each of the variables. The evaluation will succeed if multiplication is defined between elements of the coefficient ring of a
and elements of vals
.
The syntax a(vals...)
is also supported.
Examples
julia> R, (x, y) = free_associative_algebra(ZZ, ["x", "y"]);
julia> f = x*y - y*x
x*y - y*x
julia> S = matrix_ring(ZZ, 2);
julia> m1 = S([1 2; 3 4])
[1 2]
[3 4]
julia> m2 = S([0 1; 1 0])
[0 1]
[1 0]
julia> evaluate(f, [m1, m2])
[-1 -3]
[ 3 1]
julia> m1*m2 - m2*m1 == evaluate(f, [m1, m2])
true
julia> m1*m2 - m2*m1 == f(m1, m2)
true
Iterators
The following iterators are provided for elements of a free associative algebra, with exponent_words
providing the analogous functionality that exponent_vectors
provides for multivariate polynomials.
terms(p::FreeAssociativeAlgebraElem)
coefficients(p::FreeAssociativeAlgebraElem)
monomials(p::FreeAssociativeAlgebraElem)
AbstractAlgebra.exponent_words
— Methodexponent_words(a::FreeAssociativeAlgebraElem{T}) where T <: RingElement
Return an iterator for the exponent words of the given polynomial. To retrieve an array of the exponent words, use collect(exponent_words(a))
.
Examples
julia> R, (a, b, c) = free_associative_algebra(ZZ, [:a, :b, :c])
(Free associative algebra on 3 indeterminates over integers, AbstractAlgebra.Generic.FreeAssociativeAlgebraElem{BigInt}[a, b, c])
julia> collect(terms(3*b*a*c - b + c + 2))
4-element Vector{Any}:
3*b*a*c
-b
c
2
julia> collect(coefficients(3*b*a*c - b + c + 2))
4-element Vector{Any}:
3
-1
1
2
julia> collect(monomials(3*b*a*c - b + c + 2))
4-element Vector{Any}:
b*a*c
b
c
1
julia> collect(exponent_words(3*b*a*c - b + c + 2))
4-element Vector{Vector{Int64}}:
[2, 1, 3]
[2]
[3]
[]
Groebner bases
The function groebner_basis
provides the computation of a Groebner basis of an ideal, given a set of generators of that ideal. Since such a Groebner basis is not necessarily finite, one can additionally pass a reduction_bound
to the function, to only compute a partial Groebner basis.
AbstractAlgebra.Generic.groebner_basis
— Methodgroebner_basis(g::Vector{FreeAssociativeAlgebraElem{T}}, reduction_bound::Int = typemax(Int), remove_redundancies::Bool = false)
Compute a Groebner basis for the ideal generated by g
. Stop when reduction_bound
many non-zero entries have been added to the Groebner basis. If the computation stops due to the bound being exceeded, the result is in general not an actual Groebner basis, just a subset of one. However, whenever the normal form with respect to this incomplete Groebner basis is 0
, it will also be 0
with respect to the full Groebner basis.
If remove_redundancies
is set to true, some redundant obstructions will be removed during the computation, which might save time, however in practice it seems to inflate the running time regularly.
AbstractAlgebra.Generic.normal_form
— Methodnormal_form(f::FreeAssociativeAlgebraElem{T}, g::Vector{FreeAssociativeAlgebraElem{T}}, aut::AhoCorasickAutomaton)
Assuming g
is a Groebner basis and aut
an Aho-Corasick automaton for the elements of g
, compute the normal form of f
with respect to g
AbstractAlgebra.Generic.interreduce!
— Methodinterreduce!(g::Vector{FreeAssociativeAlgebraElem{T}}) where T
Interreduce a given Groebner basis with itself, i.e. compute the normal form of each element of g
with respect to the rest of the elements and discard elements with normal form $0$ and duplicates.
The implementation uses a non-commutative version of the Buchberger algorithm as described in
Xingqiang Xiu, Non-commutative Gröbner Bases and Applications, PhD thesis, 2012.
Examples
julia> R = @free_associative_algebra(GF(2), [:x, :y, :u, :v, :t, :s])
Free associative algebra on 6 indeterminates x, y, u, v, ..., s
over finite field F_2
julia> g = Generic.groebner_basis([u*(x*y)^3 + u*(x*y)^2 + u + v, (y*x)^3*t + (y*x)^2*t + t + s])
5-element Vector{AbstractAlgebra.Generic.FreeAssociativeAlgebraElem{AbstractAlgebra.GFElem{Int64}}}:
u*x*y*x*y*x*y + u*x*y*x*y + u + v
y*x*y*x*y*x*t + y*x*y*x*t + t + s
u*x*s + v*x*t
u*x*y*x*s + v*x*y*x*t
u*x*y*x*y*x*s + v*x*y*x*y*x*t
In order to check whether a given element of the algebra is in the ideal generated by a Groebner basis g
, one can compute its normal form.
julia> R = @free_associative_algebra(GF(2), [:x, :y, :u, :v, :t, :s]);
julia> g = Generic.groebner_basis([u*(x*y)^3 + u*(x*y)^2 + u + v, (y*x)^3*t + (y*x)^2*t + t + s]);
julia> normal_form(u*(x*y)^3*s*t + u*(x*y)^2*s*t +u*s*t + v*s*t, g)
0