Free associative unital algebras, implemented via Singular’s letterplace rings

AUTHOR:

With this implementation, Groebner bases out to a degree bound and normal forms can be computed for twosided weighted homogeneous ideals of free algebras. For now, all computations are restricted to weighted homogeneous elements, i.e., other elements cannot be created by arithmetic operations.

EXAMPLES:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F
sage: I
Twosided Ideal (x*y + y*z, x*x + x*y - y*x - y*y) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
sage: x*(x*I.0-I.1*y+I.0*y)-I.1*y*z
x*y*x*y + x*y*y*y - x*y*y*z + x*y*z*y + y*x*y*z + y*y*y*z
sage: x^2*I.0-x*I.1*y+x*I.0*y-I.1*y*z in I
True
>>> from sage.all import *
>>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> F
Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
>>> I = F*[x*y+y*z,x**Integer(2)+x*y-y*x-y**Integer(2)]*F
>>> I
Twosided Ideal (x*y + y*z, x*x + x*y - y*x - y*y) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
>>> x*(x*I.gen(0)-I.gen(1)*y+I.gen(0)*y)-I.gen(1)*y*z
x*y*x*y + x*y*y*y - x*y*y*z + x*y*z*y + y*x*y*z + y*y*y*z
>>> x**Integer(2)*I.gen(0)-x*I.gen(1)*y+x*I.gen(0)*y-I.gen(1)*y*z in I
True

The preceding containment test is based on the computation of Groebner bases with degree bound:

sage: I.groebner_basis(degbound=4)
Twosided Ideal (x*y + y*z,
    x*x - y*x - y*y - y*z,
    y*y*y - y*y*z + y*z*y - y*z*z,
    y*y*x + y*y*z + y*z*x + y*z*z,
    y*y*z*y - y*y*z*z + y*z*z*y - y*z*z*z,
    y*z*y*y - y*z*y*z + y*z*z*y - y*z*z*z,
    y*y*z*x + y*y*z*z + y*z*z*x + y*z*z*z,
    y*z*y*x + y*z*y*z + y*z*z*x + y*z*z*z) of Free Associative Unital
    Algebra on 3 generators (x, y, z) over Rational Field
>>> from sage.all import *
>>> I.groebner_basis(degbound=Integer(4))
Twosided Ideal (x*y + y*z,
    x*x - y*x - y*y - y*z,
    y*y*y - y*y*z + y*z*y - y*z*z,
    y*y*x + y*y*z + y*z*x + y*z*z,
    y*y*z*y - y*y*z*z + y*z*z*y - y*z*z*z,
    y*z*y*y - y*z*y*z + y*z*z*y - y*z*z*z,
    y*y*z*x + y*y*z*z + y*z*z*x + y*z*z*z,
    y*z*y*x + y*z*y*z + y*z*z*x + y*z*z*z) of Free Associative Unital
    Algebra on 3 generators (x, y, z) over Rational Field

When reducing an element by \(I\), the original generators are chosen:

sage: (y*z*y*y).reduce(I)
y*z*y*y
>>> from sage.all import *
>>> (y*z*y*y).reduce(I)
y*z*y*y

However, there is a method for computing the normal form of an element, which is the same as reduction by the Groebner basis out to the degree of that element:

sage: (y*z*y*y).normal_form(I)
y*z*y*z - y*z*z*y + y*z*z*z
sage: (y*z*y*y).reduce(I.groebner_basis(4))
y*z*y*z - y*z*z*y + y*z*z*z
>>> from sage.all import *
>>> (y*z*y*y).normal_form(I)
y*z*y*z - y*z*z*y + y*z*z*z
>>> (y*z*y*y).reduce(I.groebner_basis(Integer(4)))
y*z*y*z - y*z*z*y + y*z*z*z

The default term order derives from the degree reverse lexicographic order on the commutative version of the free algebra:

sage: F.commutative_ring().term_order()
Degree reverse lexicographic term order
>>> from sage.all import *
>>> F.commutative_ring().term_order()
Degree reverse lexicographic term order

A different term order can be chosen, and of course may yield a different normal form:

sage: L.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace', order='lex')
sage: L.commutative_ring().term_order()
Lexicographic term order
sage: J = L*[a*b+b*c,a^2+a*b-b*c-c^2]*L
sage: J.groebner_basis(4)
Twosided Ideal (2*b*c*b - b*c*c + c*c*b,
    a*b + b*c,
    -a*c*c + 2*b*c*a + 2*b*c*c + c*c*a,
    a*c*c*b - 2*b*c*c*b + b*c*c*c,
    a*a - 2*b*c - c*c,
    a*c*c*a - 2*b*c*c*a - 4*b*c*c*c - c*c*c*c) of Free Associative Unital
    Algebra on 3 generators (a, b, c) over Rational Field
sage: (b*c*b*b).normal_form(J)
1/2*b*c*c*b - 1/2*c*c*b*b
>>> from sage.all import *
>>> L = FreeAlgebra(QQ, implementation='letterplace', order='lex', names=('a', 'b', 'c',)); (a, b, c,) = L._first_ngens(3)
>>> L.commutative_ring().term_order()
Lexicographic term order
>>> J = L*[a*b+b*c,a**Integer(2)+a*b-b*c-c**Integer(2)]*L
>>> J.groebner_basis(Integer(4))
Twosided Ideal (2*b*c*b - b*c*c + c*c*b,
    a*b + b*c,
    -a*c*c + 2*b*c*a + 2*b*c*c + c*c*a,
    a*c*c*b - 2*b*c*c*b + b*c*c*c,
    a*a - 2*b*c - c*c,
    a*c*c*a - 2*b*c*c*a - 4*b*c*c*c - c*c*c*c) of Free Associative Unital
    Algebra on 3 generators (a, b, c) over Rational Field
>>> (b*c*b*b).normal_form(J)
1/2*b*c*c*b - 1/2*c*c*b*b

Here is an example with degree weights:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[1,2,3])
sage: (x*y+z).degree()
3
>>> from sage.all import *
>>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(1),Integer(2),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> (x*y+z).degree()
3

Todo

The computation of Groebner bases only works for global term orderings, and all elements must be weighted homogeneous with respect to positive integral degree weights. It is ongoing work in Singular to lift these restrictions.

We support coercion from the letterplace wrapper to the corresponding generic implementation of a free algebra (FreeAlgebra_generic), but there is no coercion in the opposite direction, since the generic implementation also comprises non-homogeneous elements.

We also do not support coercion from a subalgebra, or between free algebras with different term orderings, yet.

class sage.algebras.letterplace.free_algebra_letterplace.FreeAlgebra_letterplace[source]

Bases: Parent

Finitely generated free algebra, with arithmetic restricted to weighted homogeneous elements.

Note

The restriction to weighted homogeneous elements should be lifted as soon as the restriction to homogeneous elements is lifted in Singular’s “Letterplace algebras”.

EXAMPLES:

sage: K.<z> = GF(25)
sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators (a, b, c) over Finite Field in z of size 5^2
sage: P = F.commutative_ring()
sage: P
Multivariate Polynomial Ring in a, b, c over Finite Field in z of size 5^2
>>> from sage.all import *
>>> K = GF(Integer(25), names=('z',)); (z,) = K._first_ngens(1)
>>> F = FreeAlgebra(K, implementation='letterplace', names=('a', 'b', 'c',)); (a, b, c,) = F._first_ngens(3)
>>> F
Free Associative Unital Algebra on 3 generators (a, b, c) over Finite Field in z of size 5^2
>>> P = F.commutative_ring()
>>> P
Multivariate Polynomial Ring in a, b, c over Finite Field in z of size 5^2

We can do arithmetic as usual, as long as we stay (weighted) homogeneous:

sage: (z*a+(z+1)*b+2*c)^2
(z + 3)*a*a + (2*z + 3)*a*b + (2*z)*a*c + (2*z + 3)*b*a + (3*z + 4)*b*b + (2*z + 2)*b*c + (2*z)*c*a + (2*z + 2)*c*b - c*c
sage: a+1
Traceback (most recent call last):
...
ArithmeticError: can only add elements of the same weighted degree
>>> from sage.all import *
>>> (z*a+(z+Integer(1))*b+Integer(2)*c)**Integer(2)
(z + 3)*a*a + (2*z + 3)*a*b + (2*z)*a*c + (2*z + 3)*b*a + (3*z + 4)*b*b + (2*z + 2)*b*c + (2*z)*c*a + (2*z + 2)*c*b - c*c
>>> a+Integer(1)
Traceback (most recent call last):
...
ArithmeticError: can only add elements of the same weighted degree
commutative_ring()[source]

Return the commutative version of this free algebra.

Note

This commutative ring is used as a unique key of the free algebra.

EXAMPLES:

sage: K.<z> = GF(25)
sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators (a, b, c) over Finite Field in z of size 5^2
sage: F.commutative_ring()
Multivariate Polynomial Ring in a, b, c over Finite Field in z of size 5^2
sage: FreeAlgebra(F.commutative_ring()) is F
True
>>> from sage.all import *
>>> K = GF(Integer(25), names=('z',)); (z,) = K._first_ngens(1)
>>> F = FreeAlgebra(K, implementation='letterplace', names=('a', 'b', 'c',)); (a, b, c,) = F._first_ngens(3)
>>> F
Free Associative Unital Algebra on 3 generators (a, b, c) over Finite Field in z of size 5^2
>>> F.commutative_ring()
Multivariate Polynomial Ring in a, b, c over Finite Field in z of size 5^2
>>> FreeAlgebra(F.commutative_ring()) is F
True
current_ring()[source]

Return the commutative ring that is used to emulate the non-commutative multiplication out to the current degree.

EXAMPLES:

sage: F.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.current_ring()
Multivariate Polynomial Ring in a, b, c over Rational Field
sage: a*b
a*b
sage: F.current_ring()
Multivariate Polynomial Ring in a, b, c, a_1, b_1, c_1 over Rational Field
sage: F.set_degbound(3)
sage: F.current_ring()
Multivariate Polynomial Ring in a, b, c, a_1, b_1, c_1, a_2, b_2, c_2 over Rational Field
>>> from sage.all import *
>>> F = FreeAlgebra(QQ, implementation='letterplace', names=('a', 'b', 'c',)); (a, b, c,) = F._first_ngens(3)
>>> F.current_ring()
Multivariate Polynomial Ring in a, b, c over Rational Field
>>> a*b
a*b
>>> F.current_ring()
Multivariate Polynomial Ring in a, b, c, a_1, b_1, c_1 over Rational Field
>>> F.set_degbound(Integer(3))
>>> F.current_ring()
Multivariate Polynomial Ring in a, b, c, a_1, b_1, c_1, a_2, b_2, c_2 over Rational Field
degbound()[source]

Return the degree bound that is currently used.

Note

When multiplying two elements of this free algebra, the degree bound will be dynamically adapted. It can also be set by set_degbound().

EXAMPLES:

In order to avoid we get a free algebras from the cache that was created in another doctest and has a different degree bound, we choose a base ring that does not appear in other tests:

sage: F.<x,y,z> = FreeAlgebra(ZZ, implementation='letterplace')
sage: F.degbound()
1
sage: x*y
x*y
sage: F.degbound()
2
sage: F.set_degbound(4)
sage: F.degbound()
4
>>> from sage.all import *
>>> F = FreeAlgebra(ZZ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> F.degbound()
1
>>> x*y
x*y
>>> F.degbound()
2
>>> F.set_degbound(Integer(4))
>>> F.degbound()
4
gen(i)[source]

Return the \(i\)-th generator.

INPUT:

  • i – integer

OUTPUT: the generator with index \(i\)

EXAMPLES:

sage: F.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.1 is F.1  # indirect doctest
True
sage: F.gen(2)
c
>>> from sage.all import *
>>> F = FreeAlgebra(QQ, implementation='letterplace', names=('a', 'b', 'c',)); (a, b, c,) = F._first_ngens(3)
>>> F.gen(1) is F.gen(1)  # indirect doctest
True
>>> F.gen(Integer(2))
c
generator_degrees()[source]
gens()[source]

Return the tuple of generators.

EXAMPLES:

sage: F.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.gens()
(a, b, c)
>>> from sage.all import *
>>> F = FreeAlgebra(QQ, implementation='letterplace', names=('a', 'b', 'c',)); (a, b, c,) = F._first_ngens(3)
>>> F.gens()
(a, b, c)
ideal_monoid()[source]

Return the monoid of ideals of this free algebra.

EXAMPLES:

sage: F.<x,y> = FreeAlgebra(GF(2), implementation='letterplace')
sage: F.ideal_monoid()
Monoid of ideals of Free Associative Unital Algebra on 2 generators (x, y) over Finite Field of size 2
sage: F.ideal_monoid() is F.ideal_monoid()
True
>>> from sage.all import *
>>> F = FreeAlgebra(GF(Integer(2)), implementation='letterplace', names=('x', 'y',)); (x, y,) = F._first_ngens(2)
>>> F.ideal_monoid()
Monoid of ideals of Free Associative Unital Algebra on 2 generators (x, y) over Finite Field of size 2
>>> F.ideal_monoid() is F.ideal_monoid()
True
is_field(proof=True)[source]

Tell whether this free algebra is a field.

Note

This would only be the case in the degenerate case of no generators. But such an example cannot be constructed in this implementation.

ngens()[source]

Return the number of generators.

EXAMPLES:

sage: F.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.ngens()
3
>>> from sage.all import *
>>> F = FreeAlgebra(QQ, implementation='letterplace', names=('a', 'b', 'c',)); (a, b, c,) = F._first_ngens(3)
>>> F.ngens()
3
set_degbound(d)[source]

Increase the degree bound that is currently in place.

Note

The degree bound cannot be decreased.

EXAMPLES:

In order to avoid we get a free algebras from the cache that was created in another doctest and has a different degree bound, we choose a base ring that does not appear in other tests:

sage: F.<x,y,z> = FreeAlgebra(GF(251), implementation='letterplace')
sage: F.degbound()
1
sage: x*y
x*y
sage: F.degbound()
2
sage: F.set_degbound(4)
sage: F.degbound()
4
sage: F.set_degbound(2)
sage: F.degbound()
4
>>> from sage.all import *
>>> F = FreeAlgebra(GF(Integer(251)), implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> F.degbound()
1
>>> x*y
x*y
>>> F.degbound()
2
>>> F.set_degbound(Integer(4))
>>> F.degbound()
4
>>> F.set_degbound(Integer(2))
>>> F.degbound()
4
term_order_of_block()[source]

Return the term order that is used for the commutative version of this free algebra.

EXAMPLES:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.term_order_of_block()
Degree reverse lexicographic term order
sage: L.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace',order='lex')
sage: L.term_order_of_block()
Lexicographic term order
>>> from sage.all import *
>>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> F.term_order_of_block()
Degree reverse lexicographic term order
>>> L = FreeAlgebra(QQ, implementation='letterplace',order='lex', names=('a', 'b', 'c',)); (a, b, c,) = L._first_ngens(3)
>>> L.term_order_of_block()
Lexicographic term order
class sage.algebras.letterplace.free_algebra_letterplace.FreeAlgebra_letterplace_libsingular[source]

Bases: object

Internally used wrapper around a Singular Letterplace polynomial ring.