Homogeneous ideals of free algebras¶
For twosided ideals and when the base ring is a field, this implementation also provides Groebner bases and ideal containment tests.
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
One can compute Groebner bases out to a finite degree, can compute normal forms and can test containment in the ideal:
sage: I.groebner_basis(degbound=3)
Twosided Ideal (y*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x + y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
sage: (x*y*z*y*x).normal_form(I)
y*z*z*y*z + y*z*z*z*x + y*z*z*z*z
sage: x*y*z*y*x - (x*y*z*y*x).normal_form(I) in I
True
AUTHOR:
Simon King (2011-03-22): See trac ticket #7797.
-
class
sage.algebras.letterplace.letterplace_ideal.
LetterplaceIdeal
(ring, gens, coerce=True, side='twosided')¶ Bases:
sage.rings.noncommutative_ideals.Ideal_nc
Graded homogeneous ideals in free algebras.
In the two-sided case over a field, one can compute Groebner bases up to a degree bound, normal forms of graded homogeneous elements of the free algebra, and ideal containment.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') 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: I.groebner_basis(2) Twosided Ideal (x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field sage: I.groebner_basis(4) Twosided Ideal (y*z*y*y - y*z*y*z + y*z*z*y - y*z*z*z, y*z*y*x + y*z*y*z + y*z*z*x + y*z*z*z, y*y*z*y - y*y*z*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*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x + y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
Groebner bases are cached. If one has computed a Groebner basis out to a high degree then it will also be returned if a Groebner basis with a lower degree bound is requested:
sage: I.groebner_basis(2) Twosided Ideal (y*z*y*y - y*z*y*z + y*z*z*y - y*z*z*z, y*z*y*x + y*z*y*z + y*z*z*x + y*z*z*z, y*y*z*y - y*y*z*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*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x + y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
Of course, the normal form of any element has to satisfy the following:
sage: x*y*z*y*x - (x*y*z*y*x).normal_form(I) in I True
Left and right ideals can be constructed, but only twosided ideals provide Groebner bases:
sage: JL = F*[x*y+y*z,x^2+x*y-y*x-y^2]; JL Left 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: JR = [x*y+y*z,x^2+x*y-y*x-y^2]*F; JR Right 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: JR.groebner_basis(2) Traceback (most recent call last): ... TypeError: This ideal is not two-sided. We can only compute two-sided Groebner bases sage: JL.groebner_basis(2) Traceback (most recent call last): ... TypeError: This ideal is not two-sided. We can only compute two-sided Groebner bases
Also, it is currently not possible to compute a Groebner basis when the base ring is not a field:
sage: FZ.<a,b,c> = FreeAlgebra(ZZ, implementation='letterplace') sage: J = FZ*[a^3-b^3]*FZ sage: J.groebner_basis(2) Traceback (most recent call last): ... TypeError: Currently, we can only compute Groebner bases if the ring of coefficients is a field
The letterplace implementation of free algebras also provides integral degree weights for the generators, and we can compute Groebner bases for twosided graded homogeneous ideals:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace',degrees=[1,2,3]) sage: I = F*[x*y+z-y*x,x*y*z-x^6+y^3]*F sage: I.groebner_basis(Infinity) Twosided Ideal (x*z*z - y*x*x*z - y*x*y*y + y*x*z*x + y*y*y*x + z*x*z + z*y*y - z*z*x, x*y - y*x + z, x*x*x*x*z*y*y + x*x*x*z*y*y*x - x*x*x*z*y*z - x*x*z*y*x*z + x*x*z*y*y*x*x + x*x*z*y*y*y - x*x*z*y*z*x - x*z*y*x*x*z - x*z*y*x*z*x + x*z*y*y*x*x*x + 2*x*z*y*y*y*x - 2*x*z*y*y*z - x*z*y*z*x*x - x*z*y*z*y + y*x*z*x*x*x*x*x - 4*y*x*z*x*x*z - 4*y*x*z*x*z*x + 4*y*x*z*y*x*x*x + 3*y*x*z*y*y*x - 4*y*x*z*y*z + y*y*x*x*x*x*z + y*y*x*x*x*z*x - 3*y*y*x*x*z*x*x - y*y*x*x*z*y + 5*y*y*x*z*x*x*x + 4*y*y*x*z*y*x - 4*y*y*y*x*x*z + 4*y*y*y*x*z*x + 3*y*y*y*y*z + 4*y*y*y*z*x*x + 6*y*y*y*z*y + y*y*z*x*x*x*x + y*y*z*x*z + 7*y*y*z*y*x*x + 7*y*y*z*y*y - 7*y*y*z*z*x - y*z*x*x*x*z - y*z*x*x*z*x + 3*y*z*x*z*x*x + y*z*x*z*y + y*z*y*x*x*x*x - 3*y*z*y*x*z + 7*y*z*y*y*x*x + 3*y*z*y*y*y - 3*y*z*y*z*x - 5*y*z*z*x*x*x - 4*y*z*z*y*x + 4*y*z*z*z - z*y*x*x*x*z - z*y*x*x*z*x - z*y*x*z*x*x - z*y*x*z*y + z*y*y*x*x*x*x - 3*z*y*y*x*z + 3*z*y*y*y*x*x + z*y*y*y*y - 3*z*y*y*z*x - z*y*z*x*x*x - 2*z*y*z*y*x + 2*z*y*z*z - z*z*x*x*x*x*x + 4*z*z*x*x*z + 4*z*z*x*z*x - 4*z*z*y*x*x*x - 3*z*z*y*y*x + 4*z*z*y*z + 4*z*z*z*x*x + 2*z*z*z*y, x*x*x*x*x*z + x*x*x*x*z*x + x*x*x*z*x*x + x*x*z*x*x*x + x*z*x*x*x*x + y*x*z*y - y*y*x*z + y*z*z + z*x*x*x*x*x - z*z*y, x*x*x*x*x*x - y*x*z - y*y*y + z*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
Again, we can compute normal forms:
sage: (z*I.0-I.1).normal_form(I) 0 sage: (z*I.0-x*y*z).normal_form(I) -y*x*z + z*z
-
groebner_basis
(degbound=None)¶ Twosided Groebner basis with degree bound.
INPUT:
degbound
(optional integer, or Infinity): If it is provided, a Groebner basis at least out to that degree is returned. By default, the current degree bound of the underlying ring is used.
ASSUMPTIONS:
Currently, we can only compute Groebner bases for twosided ideals, and the ring of coefficients must be a field. A \(TypeError\) is raised if one of these conditions is violated.
Note
The result is cached. The same Groebner basis is returned if a smaller degree bound than the known one is requested.
If the degree bound
Infinity
is requested, it is attempted to compute a complete Groebner basis. But we can not guarantee that the computation will terminate, since not all twosided homogeneous ideals of a free algebra have a finite Groebner basis.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F
Since \(F\) was cached and since its degree bound can not be decreased, it may happen that, as a side effect of other tests, it already has a degree bound bigger than 3. So, we can not test against the output of
I.groebner_basis()
:sage: F.set_degbound(3) sage: I.groebner_basis() # not tested Twosided Ideal (y*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x + y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field sage: I.groebner_basis(4) Twosided Ideal (y*z*y*y - y*z*y*z + y*z*z*y - y*z*z*z, y*z*y*x + y*z*y*z + y*z*z*x + y*z*z*z, y*y*z*y - y*y*z*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*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x + y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field sage: I.groebner_basis(2) is I.groebner_basis(4) True sage: G = I.groebner_basis(4) sage: G.groebner_basis(3) is G True
If a finite complete Groebner basis exists, we can compute it as follows:
sage: I = F*[x*y-y*x,x*z-z*x,y*z-z*y,x^2*y-z^3,x*y^2+z*x^2]*F sage: I.groebner_basis(Infinity) Twosided Ideal (z*z*z*y*y + z*z*z*z*x, z*x*x*x + z*z*z*y, y*z - z*y, y*y*x + z*x*x, y*x*x - z*z*z, x*z - z*x, x*y - y*x) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
Since the commutators of the generators are contained in the ideal, we can verify the above result by a computation in a polynomial ring in negative lexicographic order:
sage: P.<c,b,a> = PolynomialRing(QQ,order='neglex') sage: J = P*[a^2*b-c^3,a*b^2+c*a^2] sage: J.groebner_basis() [b*a^2 - c^3, b^2*a + c*a^2, c*a^3 + c^3*b, c^3*b^2 + c^4*a]
Aparently, the results are compatible, by sending \(a\) to \(x\), \(b\) to \(y\) and \(c\) to \(z\).
-
reduce
(G)¶ Reduction of this ideal by another ideal, or normal form of an algebra element with respect to this ideal.
INPUT:
G
: A list or tuple of elements, an ideal, the ambient algebra, or a single element.
OUTPUT:
The normal form of
G
with respect to this ideal, ifG
is an element of the algebra.The reduction of this ideal by the elements resp. generators of
G
, ifG
is a list, tuple or ideal.The zero ideal, if
G
is the algebra containing this ideal.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F sage: I.reduce(F) Twosided Ideal (0) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field sage: I.reduce(x^3) -y*z*x - y*z*y - y*z*z sage: I.reduce([x*y]) Twosided Ideal (y*z, x*x - y*x - y*y) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field sage: I.reduce(F*[x^2+x*y,y^2+y*z]*F) Twosided Ideal (x*y + y*z, -y*x + y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
-
-
sage.algebras.letterplace.letterplace_ideal.
poly_reduce
(ring=None, interruptible=True, attributes=None, *args)¶ Construct a new Singular kernel function.
EXAMPLES:
sage: from sage.libs.singular.function import SingularKernelFunction sage: R.<x,y> = PolynomialRing(QQ, order='lex') sage: I = R.ideal(x + 1, x*y + 1) sage: f = SingularKernelFunction("std") sage: f(I) [y - 1, x + 1] sage: SingularKernelFunction("no_such_function") Traceback (most recent call last): ... NameError: Singular kernel function 'no_such_function' is not defined
-
sage.algebras.letterplace.letterplace_ideal.
singular_system
(ring=None, interruptible=True, attributes=None, *args)¶ Construct a new Singular kernel function.
EXAMPLES:
sage: from sage.libs.singular.function import SingularKernelFunction sage: R.<x,y> = PolynomialRing(QQ, order='lex') sage: I = R.ideal(x + 1, x*y + 1) sage: f = SingularKernelFunction("std") sage: f(I) [y - 1, x + 1] sage: SingularKernelFunction("no_such_function") Traceback (most recent call last): ... NameError: Singular kernel function 'no_such_function' is not defined