Free algebras#

AUTHORS:

  • David Kohel (2005-09)

  • William Stein (2006-11-01): add all doctests; implemented many things.

  • Simon King (2011-04): Put free algebras into the category framework. Reimplement free algebra constructor, using a UniqueFactory for handling different implementations of free algebras. Allow degree weights for free algebras in letterplace implementation.

EXAMPLES:

sage: F = FreeAlgebra(ZZ, 3, 'x,y,z')
sage: F.base_ring()
Integer Ring
sage: G = FreeAlgebra(F, 2, 'm,n'); G
Free Algebra on 2 generators (m, n) over
 Free Algebra on 3 generators (x, y, z) over Integer Ring
sage: G.base_ring()
Free Algebra on 3 generators (x, y, z) over Integer Ring

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ, Integer(3), 'x,y,z')
>>> F.base_ring()
Integer Ring
>>> G = FreeAlgebra(F, Integer(2), 'm,n'); G
Free Algebra on 2 generators (m, n) over
 Free Algebra on 3 generators (x, y, z) over Integer Ring
>>> G.base_ring()
Free Algebra on 3 generators (x, y, z) over Integer Ring

The above free algebra is based on a generic implementation. By Issue #7797, there is a different implementation FreeAlgebra_letterplace based on Singular’s letterplace rings. It is currently restricted to weighted homogeneous elements and is therefore not the default. But the arithmetic is much faster than in the generic implementation. Moreover, we can compute Groebner bases with degree bound for its two-sided ideals, and thus provide ideal containment tests:

sage: # needs sage.libs.singular
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace'); 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.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
sage: y*z*y*y*z*z + 2*y*z*y*z*z*x + y*z*y*z*z*z - y*z*z*y*z*x + y*z*z*z*z*x in I
True

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> 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.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
>>> y*z*y*y*z*z + Integer(2)*y*z*y*z*z*x + y*z*y*z*z*z - y*z*z*y*z*x + y*z*z*z*z*x in I
True

Positive integral degree weights for the letterplace implementation was introduced in Issue #7797:

sage: # needs sage.libs.singular
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3])
sage: x.degree()
2
sage: y.degree()
1
sage: z.degree()
3
sage: I = F*[x*y-y*x, x^2+2*y*z, (x*y)^2-z^2]*F
sage: Q.<a,b,c> = F.quo(I)
sage: TestSuite(Q).run()
sage: a^2*b^2
c*c

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> x.degree()
2
>>> y.degree()
1
>>> z.degree()
3
>>> I = F*[x*y-y*x, x**Integer(2)+Integer(2)*y*z, (x*y)**Integer(2)-z**Integer(2)]*F
>>> Q = F.quo(I, names=('a', 'b', 'c',)); (a, b, c,) = Q._first_ngens(3)
>>> TestSuite(Q).run()
>>> a**Integer(2)*b**Integer(2)
c*c
class sage.algebras.free_algebra.FreeAlgebraFactory[source]#

Bases: UniqueFactory

A constructor of free algebras.

See free_algebra for examples and corner cases.

EXAMPLES:

sage: FreeAlgebra(GF(5),3,'x')
Free Algebra on 3 generators (x0, x1, x2) over Finite Field of size 5
sage: F.<x,y,z> = FreeAlgebra(GF(5),3)
sage: (x+y+z)^2
x^2 + x*y + x*z + y*x + y^2 + y*z + z*x + z*y + z^2
sage: FreeAlgebra(GF(5),3, 'xx, zba, Y')
Free Algebra on 3 generators (xx, zba, Y) over Finite Field of size 5
sage: FreeAlgebra(GF(5),3, 'abc')
Free Algebra on 3 generators (a, b, c) over Finite Field of size 5
sage: FreeAlgebra(GF(5),1, 'z')
Free Algebra on 1 generators (z,) over Finite Field of size 5
sage: FreeAlgebra(GF(5),1, ['alpha'])
Free Algebra on 1 generators (alpha,) over Finite Field of size 5
sage: FreeAlgebra(FreeAlgebra(ZZ,1,'a'), 2, 'x')
Free Algebra on 2 generators (x0, x1) over
 Free Algebra on 1 generators (a,) over Integer Ring

>>> from sage.all import *
>>> FreeAlgebra(GF(Integer(5)),Integer(3),'x')
Free Algebra on 3 generators (x0, x1, x2) over Finite Field of size 5
>>> F = FreeAlgebra(GF(Integer(5)),Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> (x+y+z)**Integer(2)
x^2 + x*y + x*z + y*x + y^2 + y*z + z*x + z*y + z^2
>>> FreeAlgebra(GF(Integer(5)),Integer(3), 'xx, zba, Y')
Free Algebra on 3 generators (xx, zba, Y) over Finite Field of size 5
>>> FreeAlgebra(GF(Integer(5)),Integer(3), 'abc')
Free Algebra on 3 generators (a, b, c) over Finite Field of size 5
>>> FreeAlgebra(GF(Integer(5)),Integer(1), 'z')
Free Algebra on 1 generators (z,) over Finite Field of size 5
>>> FreeAlgebra(GF(Integer(5)),Integer(1), ['alpha'])
Free Algebra on 1 generators (alpha,) over Finite Field of size 5
>>> FreeAlgebra(FreeAlgebra(ZZ,Integer(1),'a'), Integer(2), 'x')
Free Algebra on 2 generators (x0, x1) over
 Free Algebra on 1 generators (a,) over Integer Ring

Free algebras are globally unique:

sage: F = FreeAlgebra(ZZ,3,'x,y,z')
sage: G = FreeAlgebra(ZZ,3,'x,y,z')
sage: F is G
True
sage: F.<x,y,z> = FreeAlgebra(GF(5),3)  # indirect doctest
sage: F is loads(dumps(F))
True
sage: F is FreeAlgebra(GF(5),['x','y','z'])
True
sage: copy(F) is F is loads(dumps(F))
True
sage: TestSuite(F).run()

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> G = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> F is G
True
>>> F = FreeAlgebra(GF(Integer(5)),Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)# indirect doctest
>>> F is loads(dumps(F))
True
>>> F is FreeAlgebra(GF(Integer(5)),['x','y','z'])
True
>>> copy(F) is F is loads(dumps(F))
True
>>> TestSuite(F).run()

By Issue #7797, we provide a different implementation of free algebras, based on Singular’s “letterplace rings”. Our letterplace wrapper allows for choosing positive integral degree weights for the generators of the free algebra. However, only (weighted) homogeneous elements are supported. Of course, isomorphic algebras in different implementations are not identical:

sage: # needs sage.libs.singular
sage: G = FreeAlgebra(GF(5),['x','y','z'], implementation='letterplace')
sage: F == G
False
sage: G is FreeAlgebra(GF(5),['x','y','z'], implementation='letterplace')
True
sage: copy(G) is G is loads(dumps(G))
True
sage: TestSuite(G).run()

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> G = FreeAlgebra(GF(Integer(5)),['x','y','z'], implementation='letterplace')
>>> F == G
False
>>> G is FreeAlgebra(GF(Integer(5)),['x','y','z'], implementation='letterplace')
True
>>> copy(G) is G is loads(dumps(G))
True
>>> TestSuite(G).run()

sage: # needs sage.libs.singular
sage: H = FreeAlgebra(GF(5), ['x','y','z'], implementation='letterplace',
....:                 degrees=[1,2,3])
sage: F != H != G
True
sage: H is FreeAlgebra(GF(5),['x','y','z'], implementation='letterplace',
....:                  degrees=[1,2,3])
True
sage: copy(H) is H is loads(dumps(H))
True
sage: TestSuite(H).run()

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> H = FreeAlgebra(GF(Integer(5)), ['x','y','z'], implementation='letterplace',
...                 degrees=[Integer(1),Integer(2),Integer(3)])
>>> F != H != G
True
>>> H is FreeAlgebra(GF(Integer(5)),['x','y','z'], implementation='letterplace',
...                  degrees=[Integer(1),Integer(2),Integer(3)])
True
>>> copy(H) is H is loads(dumps(H))
True
>>> TestSuite(H).run()

Free algebras commute with their base ring.

sage: K.<a,b> = FreeAlgebra(QQ,2)
sage: K.is_commutative()
False
sage: L.<c> = FreeAlgebra(K,1)
sage: L.is_commutative()
False
sage: s = a*b^2 * c^3; s
a*b^2*c^3
sage: parent(s)
Free Algebra on 1 generators (c,) over
 Free Algebra on 2 generators (a, b) over Rational Field
sage: c^3 * a * b^2
a*b^2*c^3

>>> from sage.all import *
>>> K = FreeAlgebra(QQ,Integer(2), names=('a', 'b',)); (a, b,) = K._first_ngens(2)
>>> K.is_commutative()
False
>>> L = FreeAlgebra(K,Integer(1), names=('c',)); (c,) = L._first_ngens(1)
>>> L.is_commutative()
False
>>> s = a*b**Integer(2) * c**Integer(3); s
a*b^2*c^3
>>> parent(s)
Free Algebra on 1 generators (c,) over
 Free Algebra on 2 generators (a, b) over Rational Field
>>> c**Integer(3) * a * b**Integer(2)
a*b^2*c^3
create_key(base_ring, arg1=None, arg2=None, sparse=None, order=None, names=None, name=None, implementation=None, degrees=None)[source]#

Create the key under which a free algebra is stored.

create_object(version, key)[source]#

Construct the free algebra that belongs to a unique key.

NOTE:

Of course, that method should not be called directly, since it does not use the cache of free algebras.

class sage.algebras.free_algebra.FreeAlgebra_generic(R, n, names, degrees=None)[source]#

Bases: CombinatorialFreeModule

The free algebra on \(n\) generators over a base ring.

INPUT:

  • R – a ring

  • n – an integer

  • names – the generator names

  • degrees – (optional) a tuple or list specifying the degrees of all the generators, if omitted, the algebra is not graded

EXAMPLES:

sage: F.<x,y,z> = FreeAlgebra(QQ, 3); F
Free Algebra on 3 generators (x, y, z) over Rational Field
sage: mul(F.gens())
x*y*z
sage: mul([ F.gen(i%3) for i in range(12) ])
x*y*z*x*y*z*x*y*z*x*y*z
sage: mul([ F.gen(i%3) for i in range(12) ]) + mul([ F.gen(i%2) for i in range(12) ])
x*y*x*y*x*y*x*y*x*y*x*y + x*y*z*x*y*z*x*y*z*x*y*z
sage: (2 + x*z + x^2)^2 + (x - y)^2
4 + 5*x^2 - x*y + 4*x*z - y*x + y^2 + x^4 + x^3*z + x*z*x^2 + x*z*x*z

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3); F
Free Algebra on 3 generators (x, y, z) over Rational Field
>>> mul(F.gens())
x*y*z
>>> mul([ F.gen(i%Integer(3)) for i in range(Integer(12)) ])
x*y*z*x*y*z*x*y*z*x*y*z
>>> mul([ F.gen(i%Integer(3)) for i in range(Integer(12)) ]) + mul([ F.gen(i%Integer(2)) for i in range(Integer(12)) ])
x*y*x*y*x*y*x*y*x*y*x*y + x*y*z*x*y*z*x*y*z*x*y*z
>>> (Integer(2) + x*z + x**Integer(2))**Integer(2) + (x - y)**Integer(2)
4 + 5*x^2 - x*y + 4*x*z - y*x + y^2 + x^4 + x^3*z + x*z*x^2 + x*z*x*z
Element[source]#

alias of FreeAlgebraElement

algebra_generators()[source]#

Return the algebra generators of self.

EXAMPLES:

sage: F = FreeAlgebra(ZZ,3,'x,y,z')
sage: F.algebra_generators()
Finite family {'x': x, 'y': y, 'z': z}

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> F.algebra_generators()
Finite family {'x': x, 'y': y, 'z': z}
degree_on_basis(m)[source]#

Return the degree of the basis element indexed by m.

EXAMPLES:

sage: A.<a, b> = FreeAlgebra(QQ, degrees=(1, -1))
sage: m = A.basis().keys()[42]
sage: m
a*b*a*b^2
sage: A.degree_on_basis(m)
-1
sage: (a*b*a*b^2).degree()
-1

>>> from sage.all import *
>>> A = FreeAlgebra(QQ, degrees=(Integer(1), -Integer(1)), names=('a', 'b',)); (a, b,) = A._first_ngens(2)
>>> m = A.basis().keys()[Integer(42)]
>>> m
a*b*a*b^2
>>> A.degree_on_basis(m)
-1
>>> (a*b*a*b**Integer(2)).degree()
-1
g_algebra(relations, names=None, order='degrevlex', check=True)[source]#

The \(G\)-Algebra derived from this algebra by relations.

By default is assumed, that two variables commute.

Todo

  • Coercion doesn’t work yet, there is some cheating about assumptions

  • The optional argument check controls checking the degeneracy conditions. Furthermore, the default values interfere with non-degeneracy conditions.

EXAMPLES:

sage: # needs sage.libs.singular
sage: A.<x,y,z> = FreeAlgebra(QQ,3)
sage: G = A.g_algebra({y*x: -x*y})
sage: (x,y,z) = G.gens()
sage: x*y
x*y
sage: y*x
-x*y
sage: z*x
x*z
sage: (x,y,z) = A.gens()
sage: G = A.g_algebra({y*x: -x*y + 1})
sage: (x,y,z) = G.gens()
sage: y*x
-x*y + 1
sage: (x,y,z) = A.gens()
sage: G = A.g_algebra({y*x: -x*y + z})
sage: (x,y,z) = G.gens()
sage: y*x
-x*y + z

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> A = FreeAlgebra(QQ,Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = A._first_ngens(3)
>>> G = A.g_algebra({y*x: -x*y})
>>> (x,y,z) = G.gens()
>>> x*y
x*y
>>> y*x
-x*y
>>> z*x
x*z
>>> (x,y,z) = A.gens()
>>> G = A.g_algebra({y*x: -x*y + Integer(1)})
>>> (x,y,z) = G.gens()
>>> y*x
-x*y + 1
>>> (x,y,z) = A.gens()
>>> G = A.g_algebra({y*x: -x*y + z})
>>> (x,y,z) = G.gens()
>>> y*x
-x*y + z
gen(i)[source]#

The i-th generator of the algebra.

EXAMPLES:

sage: F = FreeAlgebra(ZZ,3,'x,y,z')
sage: F.gen(0)
x

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> F.gen(Integer(0))
x
gens()[source]#

Return the generators of self.

EXAMPLES:

sage: F = FreeAlgebra(ZZ,3,'x,y,z')
sage: F.gens()
(x, y, z)

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> F.gens()
(x, y, z)
is_field(proof=True)[source]#

Return True if this Free Algebra is a field.

This happens only if the base ring is a field and there are no generators

EXAMPLES:

sage: A = FreeAlgebra(QQ,0,'')
sage: A.is_field()
True
sage: A = FreeAlgebra(QQ,1,'x')
sage: A.is_field()
False

>>> from sage.all import *
>>> A = FreeAlgebra(QQ,Integer(0),'')
>>> A.is_field()
True
>>> A = FreeAlgebra(QQ,Integer(1),'x')
>>> A.is_field()
False
lie_polynomial(w)[source]#

Return the Lie polynomial associated to the Lyndon word w. If w is not Lyndon, then return the product of Lie polynomials of the Lyndon factorization of w.

Given a Lyndon word \(w\), the Lie polynomial \(L_w\) is defined recursively by \(L_w = [L_u, L_v]\), where \(w = uv\) is the standard factorization of \(w\), and \(L_w = w\) when \(w\) is a single letter.

INPUT:

  • w – a word or an element of the free monoid

EXAMPLES:

sage: F = FreeAlgebra(QQ, 3, 'x,y,z')
sage: M.<x,y,z> = FreeMonoid(3)
sage: F.lie_polynomial(x*y)
x*y - y*x
sage: F.lie_polynomial(y*x)
y*x
sage: F.lie_polynomial(x^2*y*x)
x^2*y*x - 2*x*y*x^2 + y*x^3
sage: F.lie_polynomial(y*z*x*z*x*z)
y*z*x*z*x*z - y*z*x*z^2*x - y*z^2*x^2*z + y*z^2*x*z*x
 - z*y*x*z*x*z + z*y*x*z^2*x + z*y*z*x^2*z - z*y*z*x*z*x

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(3), 'x,y,z')
>>> M = FreeMonoid(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = M._first_ngens(3)
>>> F.lie_polynomial(x*y)
x*y - y*x
>>> F.lie_polynomial(y*x)
y*x
>>> F.lie_polynomial(x**Integer(2)*y*x)
x^2*y*x - 2*x*y*x^2 + y*x^3
>>> F.lie_polynomial(y*z*x*z*x*z)
y*z*x*z*x*z - y*z*x*z^2*x - y*z^2*x^2*z + y*z^2*x*z*x
 - z*y*x*z*x*z + z*y*x*z^2*x + z*y*z*x^2*z - z*y*z*x*z*x
monoid()[source]#

The free monoid of generators of the algebra.

EXAMPLES:

sage: F = FreeAlgebra(ZZ,3,'x,y,z')
sage: F.monoid()
Free monoid on 3 generators (x, y, z)

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> F.monoid()
Free monoid on 3 generators (x, y, z)
ngens()[source]#

The number of generators of the algebra.

EXAMPLES:

sage: F = FreeAlgebra(ZZ,3,'x,y,z')
sage: F.ngens()
3

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> F.ngens()
3
one_basis()[source]#

Return the index of the basis element \(1\).

EXAMPLES:

sage: F = FreeAlgebra(QQ, 2, 'x,y')
sage: F.one_basis()
1
sage: F.one_basis().parent()
Free monoid on 2 generators (x, y)

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), 'x,y')
>>> F.one_basis()
1
>>> F.one_basis().parent()
Free monoid on 2 generators (x, y)
pbw_basis()[source]#

Return the Poincaré-Birkhoff-Witt (PBW) basis of self.

EXAMPLES:

sage: F.<x,y> = FreeAlgebra(QQ, 2)
sage: F.poincare_birkhoff_witt_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 2 generators (x, y) over Rational Field

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), names=('x', 'y',)); (x, y,) = F._first_ngens(2)
>>> F.poincare_birkhoff_witt_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 2 generators (x, y) over Rational Field
pbw_element(elt)[source]#

Return the element elt in the Poincaré-Birkhoff-Witt basis.

EXAMPLES:

sage: F.<x,y> = FreeAlgebra(QQ, 2)
sage: F.pbw_element(x*y - y*x + 2)
2*PBW[1] + PBW[x*y]
sage: F.pbw_element(F.one())
PBW[1]
sage: F.pbw_element(x*y*x + x^3*y)
PBW[x*y]*PBW[x] + PBW[y]*PBW[x]^2 + PBW[x^3*y]
 + 3*PBW[x^2*y]*PBW[x] + 3*PBW[x*y]*PBW[x]^2 + PBW[y]*PBW[x]^3

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), names=('x', 'y',)); (x, y,) = F._first_ngens(2)
>>> F.pbw_element(x*y - y*x + Integer(2))
2*PBW[1] + PBW[x*y]
>>> F.pbw_element(F.one())
PBW[1]
>>> F.pbw_element(x*y*x + x**Integer(3)*y)
PBW[x*y]*PBW[x] + PBW[y]*PBW[x]^2 + PBW[x^3*y]
 + 3*PBW[x^2*y]*PBW[x] + 3*PBW[x*y]*PBW[x]^2 + PBW[y]*PBW[x]^3
poincare_birkhoff_witt_basis()[source]#

Return the Poincaré-Birkhoff-Witt (PBW) basis of self.

EXAMPLES:

sage: F.<x,y> = FreeAlgebra(QQ, 2)
sage: F.poincare_birkhoff_witt_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 2 generators (x, y) over Rational Field

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), names=('x', 'y',)); (x, y,) = F._first_ngens(2)
>>> F.poincare_birkhoff_witt_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 2 generators (x, y) over Rational Field
product_on_basis(x, y)[source]#

Return the product of the basis elements indexed by x and y.

EXAMPLES:

sage: F = FreeAlgebra(ZZ,3,'x,y,z')
sage: I = F.basis().keys()
sage: x,y,z = I.gens()
sage: F.product_on_basis(x*y, z*y)
x*y*z*y

>>> from sage.all import *
>>> F = FreeAlgebra(ZZ,Integer(3),'x,y,z')
>>> I = F.basis().keys()
>>> x,y,z = I.gens()
>>> F.product_on_basis(x*y, z*y)
x*y*z*y
quo(mons, mats=None, names=None, **args)[source]#

Return a quotient algebra.

The quotient algebra is defined via the action of a free algebra \(A\) on a (finitely generated) free module. The input for the quotient algebra is a list of monomials (in the underlying monoid for \(A\)) which form a free basis for the module of \(A\), and a list of matrices, which give the action of the free generators of \(A\) on this monomial basis.

EXAMPLES:

Here is the quaternion algebra defined in terms of three generators:

sage: n = 3
sage: A = FreeAlgebra(QQ,n,'i')
sage: F = A.monoid()
sage: i, j, k = F.gens()
sage: mons = [ F(1), i, j, k ]
sage: M = MatrixSpace(QQ,4)
sage: mats = [M([0,1,0,0, -1,0,0,0, 0,0,0,-1, 0,0,1,0]),
....:         M([0,0,1,0, 0,0,0,1, -1,0,0,0, 0,-1,0,0]),
....:         M([0,0,0,1, 0,0,-1,0, 0,1,0,0, -1,0,0,0]) ]
sage: H.<i,j,k> = A.quotient(mons, mats); H
Free algebra quotient on 3 generators ('i', 'j', 'k') and dimension 4
 over Rational Field

>>> from sage.all import *
>>> n = Integer(3)
>>> A = FreeAlgebra(QQ,n,'i')
>>> F = A.monoid()
>>> i, j, k = F.gens()
>>> mons = [ F(Integer(1)), i, j, k ]
>>> M = MatrixSpace(QQ,Integer(4))
>>> mats = [M([Integer(0),Integer(1),Integer(0),Integer(0), -Integer(1),Integer(0),Integer(0),Integer(0), Integer(0),Integer(0),Integer(0),-Integer(1), Integer(0),Integer(0),Integer(1),Integer(0)]),
...         M([Integer(0),Integer(0),Integer(1),Integer(0), Integer(0),Integer(0),Integer(0),Integer(1), -Integer(1),Integer(0),Integer(0),Integer(0), Integer(0),-Integer(1),Integer(0),Integer(0)]),
...         M([Integer(0),Integer(0),Integer(0),Integer(1), Integer(0),Integer(0),-Integer(1),Integer(0), Integer(0),Integer(1),Integer(0),Integer(0), -Integer(1),Integer(0),Integer(0),Integer(0)]) ]
>>> H = A.quotient(mons, mats, names=('i', 'j', 'k',)); (i, j, k,) = H._first_ngens(3); H
Free algebra quotient on 3 generators ('i', 'j', 'k') and dimension 4
 over Rational Field
quotient(mons, mats=None, names=None, **args)[source]#

Return a quotient algebra.

The quotient algebra is defined via the action of a free algebra \(A\) on a (finitely generated) free module. The input for the quotient algebra is a list of monomials (in the underlying monoid for \(A\)) which form a free basis for the module of \(A\), and a list of matrices, which give the action of the free generators of \(A\) on this monomial basis.

EXAMPLES:

Here is the quaternion algebra defined in terms of three generators:

sage: n = 3
sage: A = FreeAlgebra(QQ,n,'i')
sage: F = A.monoid()
sage: i, j, k = F.gens()
sage: mons = [ F(1), i, j, k ]
sage: M = MatrixSpace(QQ,4)
sage: mats = [M([0,1,0,0, -1,0,0,0, 0,0,0,-1, 0,0,1,0]),
....:         M([0,0,1,0, 0,0,0,1, -1,0,0,0, 0,-1,0,0]),
....:         M([0,0,0,1, 0,0,-1,0, 0,1,0,0, -1,0,0,0]) ]
sage: H.<i,j,k> = A.quotient(mons, mats); H
Free algebra quotient on 3 generators ('i', 'j', 'k') and dimension 4
 over Rational Field

>>> from sage.all import *
>>> n = Integer(3)
>>> A = FreeAlgebra(QQ,n,'i')
>>> F = A.monoid()
>>> i, j, k = F.gens()
>>> mons = [ F(Integer(1)), i, j, k ]
>>> M = MatrixSpace(QQ,Integer(4))
>>> mats = [M([Integer(0),Integer(1),Integer(0),Integer(0), -Integer(1),Integer(0),Integer(0),Integer(0), Integer(0),Integer(0),Integer(0),-Integer(1), Integer(0),Integer(0),Integer(1),Integer(0)]),
...         M([Integer(0),Integer(0),Integer(1),Integer(0), Integer(0),Integer(0),Integer(0),Integer(1), -Integer(1),Integer(0),Integer(0),Integer(0), Integer(0),-Integer(1),Integer(0),Integer(0)]),
...         M([Integer(0),Integer(0),Integer(0),Integer(1), Integer(0),Integer(0),-Integer(1),Integer(0), Integer(0),Integer(1),Integer(0),Integer(0), -Integer(1),Integer(0),Integer(0),Integer(0)]) ]
>>> H = A.quotient(mons, mats, names=('i', 'j', 'k',)); (i, j, k,) = H._first_ngens(3); H
Free algebra quotient on 3 generators ('i', 'j', 'k') and dimension 4
 over Rational Field
class sage.algebras.free_algebra.PBWBasisOfFreeAlgebra(alg)[source]#

Bases: CombinatorialFreeModule

The Poincaré-Birkhoff-Witt basis of the free algebra.

EXAMPLES:

sage: F.<x,y> = FreeAlgebra(QQ, 2)
sage: PBW = F.pbw_basis()
sage: px, py = PBW.gens()
sage: px * py
PBW[x*y] + PBW[y]*PBW[x]
sage: py * px
PBW[y]*PBW[x]
sage: px * py^3 * px - 2*px * py
-2*PBW[x*y] - 2*PBW[y]*PBW[x] + PBW[x*y^3]*PBW[x]
 + 3*PBW[y]*PBW[x*y^2]*PBW[x] + 3*PBW[y]^2*PBW[x*y]*PBW[x]
 + PBW[y]^3*PBW[x]^2

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), names=('x', 'y',)); (x, y,) = F._first_ngens(2)
>>> PBW = F.pbw_basis()
>>> px, py = PBW.gens()
>>> px * py
PBW[x*y] + PBW[y]*PBW[x]
>>> py * px
PBW[y]*PBW[x]
>>> px * py**Integer(3) * px - Integer(2)*px * py
-2*PBW[x*y] - 2*PBW[y]*PBW[x] + PBW[x*y^3]*PBW[x]
 + 3*PBW[y]*PBW[x*y^2]*PBW[x] + 3*PBW[y]^2*PBW[x*y]*PBW[x]
 + PBW[y]^3*PBW[x]^2

We can convert between the two bases:

sage: p = PBW(x*y - y*x + 2); p
2*PBW[1] + PBW[x*y]
sage: F(p)
2 + x*y - y*x
sage: f = F.pbw_element(x*y*x + x^3*y + x + 3)
sage: F(PBW(f)) == f
True
sage: p = px*py + py^4*px^2
sage: F(p)
x*y + y^4*x^2
sage: PBW(F(p)) == p
True

>>> from sage.all import *
>>> p = PBW(x*y - y*x + Integer(2)); p
2*PBW[1] + PBW[x*y]
>>> F(p)
2 + x*y - y*x
>>> f = F.pbw_element(x*y*x + x**Integer(3)*y + x + Integer(3))
>>> F(PBW(f)) == f
True
>>> p = px*py + py**Integer(4)*px**Integer(2)
>>> F(p)
x*y + y^4*x^2
>>> PBW(F(p)) == p
True

Note that multiplication in the PBW basis agrees with multiplication as monomials:

sage: F(px * py^3 * px - 2*px * py) == x*y^3*x - 2*x*y
True

>>> from sage.all import *
>>> F(px * py**Integer(3) * px - Integer(2)*px * py) == x*y**Integer(3)*x - Integer(2)*x*y
True

We verify Examples 1 and 2 in [MR1989]:

sage: F.<x,y,z> = FreeAlgebra(QQ)
sage: PBW = F.pbw_basis()
sage: PBW(x*y*z)
PBW[x*y*z] + PBW[x*z*y] + PBW[y]*PBW[x*z] + PBW[y*z]*PBW[x]
 + PBW[z]*PBW[x*y] + PBW[z]*PBW[y]*PBW[x]
sage: PBW(x*y*y*x)
PBW[x*y^2]*PBW[x] + 2*PBW[y]*PBW[x*y]*PBW[x] + PBW[y]^2*PBW[x]^2

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> PBW = F.pbw_basis()
>>> PBW(x*y*z)
PBW[x*y*z] + PBW[x*z*y] + PBW[y]*PBW[x*z] + PBW[y*z]*PBW[x]
 + PBW[z]*PBW[x*y] + PBW[z]*PBW[y]*PBW[x]
>>> PBW(x*y*y*x)
PBW[x*y^2]*PBW[x] + 2*PBW[y]*PBW[x*y]*PBW[x] + PBW[y]^2*PBW[x]^2
class Element[source]#

Bases: IndexedFreeModuleElement

expand()[source]#

Expand self in the monomials of the free algebra.

EXAMPLES:

sage: F = FreeAlgebra(QQ, 2, 'x,y')
sage: PBW = F.pbw_basis()
sage: x,y = F.monoid().gens()
sage: f = PBW(x^2*y) + PBW(x) + PBW(y^4*x)
sage: f.expand()
x + x^2*y - 2*x*y*x + y*x^2 + y^4*x

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), 'x,y')
>>> PBW = F.pbw_basis()
>>> x,y = F.monoid().gens()
>>> f = PBW(x**Integer(2)*y) + PBW(x) + PBW(y**Integer(4)*x)
>>> f.expand()
x + x^2*y - 2*x*y*x + y*x^2 + y^4*x
algebra_generators()[source]#

Return the generators of self as an algebra.

EXAMPLES:

sage: PBW = FreeAlgebra(QQ, 2, 'x,y').pbw_basis()
sage: gens = PBW.algebra_generators(); gens
(PBW[x], PBW[y])
sage: all(g.parent() is PBW for g in gens)
True

>>> from sage.all import *
>>> PBW = FreeAlgebra(QQ, Integer(2), 'x,y').pbw_basis()
>>> gens = PBW.algebra_generators(); gens
(PBW[x], PBW[y])
>>> all(g.parent() is PBW for g in gens)
True
expansion(t)[source]#

Return the expansion of the element t of the Poincaré-Birkhoff-Witt basis in the monomials of the free algebra.

EXAMPLES:

sage: F = FreeAlgebra(QQ, 2, 'x,y')
sage: PBW = F.pbw_basis()
sage: x,y = F.monoid().gens()
sage: PBW.expansion(PBW(x*y))
x*y - y*x
sage: PBW.expansion(PBW.one())
1
sage: PBW.expansion(PBW(x*y*x) + 2*PBW(x) + 3)
3 + 2*x + x*y*x - y*x^2

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), 'x,y')
>>> PBW = F.pbw_basis()
>>> x,y = F.monoid().gens()
>>> PBW.expansion(PBW(x*y))
x*y - y*x
>>> PBW.expansion(PBW.one())
1
>>> PBW.expansion(PBW(x*y*x) + Integer(2)*PBW(x) + Integer(3))
3 + 2*x + x*y*x - y*x^2
free_algebra()[source]#

Return the associated free algebra of self.

EXAMPLES:

sage: PBW = FreeAlgebra(QQ, 2, 'x,y').pbw_basis()
sage: PBW.free_algebra()
Free Algebra on 2 generators (x, y) over Rational Field

>>> from sage.all import *
>>> PBW = FreeAlgebra(QQ, Integer(2), 'x,y').pbw_basis()
>>> PBW.free_algebra()
Free Algebra on 2 generators (x, y) over Rational Field
gen(i)[source]#

Return the i-th generator of self.

EXAMPLES:

sage: PBW = FreeAlgebra(QQ, 2, 'x,y').pbw_basis()
sage: PBW.gen(0)
PBW[x]
sage: PBW.gen(1)
PBW[y]

>>> from sage.all import *
>>> PBW = FreeAlgebra(QQ, Integer(2), 'x,y').pbw_basis()
>>> PBW.gen(Integer(0))
PBW[x]
>>> PBW.gen(Integer(1))
PBW[y]
gens()[source]#

Return the generators of self as an algebra.

EXAMPLES:

sage: PBW = FreeAlgebra(QQ, 2, 'x,y').pbw_basis()
sage: gens = PBW.algebra_generators(); gens
(PBW[x], PBW[y])
sage: all(g.parent() is PBW for g in gens)
True

>>> from sage.all import *
>>> PBW = FreeAlgebra(QQ, Integer(2), 'x,y').pbw_basis()
>>> gens = PBW.algebra_generators(); gens
(PBW[x], PBW[y])
>>> all(g.parent() is PBW for g in gens)
True
one_basis()[source]#

Return the index of the basis element for \(1\).

EXAMPLES:

sage: PBW = FreeAlgebra(QQ, 2, 'x,y').pbw_basis()
sage: PBW.one_basis()
1
sage: PBW.one_basis().parent()
Free monoid on 2 generators (x, y)

>>> from sage.all import *
>>> PBW = FreeAlgebra(QQ, Integer(2), 'x,y').pbw_basis()
>>> PBW.one_basis()
1
>>> PBW.one_basis().parent()
Free monoid on 2 generators (x, y)
product(u, v)[source]#

Return the product of two elements u and v.

EXAMPLES:

sage: F = FreeAlgebra(QQ, 2, 'x,y')
sage: PBW = F.pbw_basis()
sage: x, y = PBW.gens()
sage: PBW.product(x, y)
PBW[x*y] + PBW[y]*PBW[x]
sage: PBW.product(y, x)
PBW[y]*PBW[x]
sage: PBW.product(y^2*x, x*y*x)
PBW[y]^2*PBW[x^2*y]*PBW[x] + 2*PBW[y]^2*PBW[x*y]*PBW[x]^2 + PBW[y]^3*PBW[x]^3

>>> from sage.all import *
>>> F = FreeAlgebra(QQ, Integer(2), 'x,y')
>>> PBW = F.pbw_basis()
>>> x, y = PBW.gens()
>>> PBW.product(x, y)
PBW[x*y] + PBW[y]*PBW[x]
>>> PBW.product(y, x)
PBW[y]*PBW[x]
>>> PBW.product(y**Integer(2)*x, x*y*x)
PBW[y]^2*PBW[x^2*y]*PBW[x] + 2*PBW[y]^2*PBW[x*y]*PBW[x]^2 + PBW[y]^3*PBW[x]^3
sage.algebras.free_algebra.is_FreeAlgebra(x)[source]#

Return True if x is a free algebra; otherwise, return False.

EXAMPLES:

sage: from sage.algebras.free_algebra import is_FreeAlgebra
sage: is_FreeAlgebra(5)
doctest:warning...
DeprecationWarning: the function is_FreeAlgebra is deprecated;
use 'isinstance(..., (FreeAlgebra_generic, FreeAlgebra_letterplace))' instead
See https://github.com/sagemath/sage/issues/37896 for details.
False
sage: is_FreeAlgebra(ZZ)
False
sage: is_FreeAlgebra(FreeAlgebra(ZZ,100,'x'))
True
sage: is_FreeAlgebra(FreeAlgebra(ZZ,10,'x',implementation='letterplace'))
True
sage: is_FreeAlgebra(FreeAlgebra(ZZ,10,'x',implementation='letterplace',
....:                            degrees=list(range(1,11))))
True

>>> from sage.all import *
>>> from sage.algebras.free_algebra import is_FreeAlgebra
>>> is_FreeAlgebra(Integer(5))
doctest:warning...
DeprecationWarning: the function is_FreeAlgebra is deprecated;
use 'isinstance(..., (FreeAlgebra_generic, FreeAlgebra_letterplace))' instead
See https://github.com/sagemath/sage/issues/37896 for details.
False
>>> is_FreeAlgebra(ZZ)
False
>>> is_FreeAlgebra(FreeAlgebra(ZZ,Integer(100),'x'))
True
>>> is_FreeAlgebra(FreeAlgebra(ZZ,Integer(10),'x',implementation='letterplace'))
True
>>> is_FreeAlgebra(FreeAlgebra(ZZ,Integer(10),'x',implementation='letterplace',
...                            degrees=list(range(Integer(1),Integer(11)))))
True