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 Ints 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_wordMethod
exponent_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.

source

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.evaluateMethod
evaluate(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
source

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_wordsMethod
exponent_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)).

source

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_basisMethod
groebner_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.

source
AbstractAlgebra.Generic.normal_formMethod
normal_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

source
AbstractAlgebra.Generic.interreduce!Method
interreduce!(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.

source

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