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

exponent_word(a::FreeAssociativeAlgebraElem{T}, i::Int) where T <: RingElement

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

evaluate(a::FreeAssociativeAlgebraElem{T}, vals::Vector{U}) where {T <: RingElement, U <: NCRingElem}

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)

exponent_words(a::FreeAssociativeAlgebraElem{T}) where T <: RingElement

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.

groebner_basis(g::Vector{FreeAssociativeAlgebraElem{T}}, reduction_bound::Int = typemax(Int), remove_redundancies::Bool = false)

normal_form(f::FreeAssociativeAlgebraElem{T}, g::Vector{FreeAssociativeAlgebraElem{T}}, aut::AhoCorasickAutomaton)

interreduce!(g::Vector{FreeAssociativeAlgebraElem{T}}) where T

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