Weighted homogeneous elements of free algebras, in letterplace implementation#
AUTHOR:
Simon King (2011-03-23): Github issue Issue #7797
- class sage.algebras.letterplace.free_algebra_element_letterplace.FreeAlgebraElement_letterplace[source]#
Bases:
AlgebraElementWeighted homogeneous elements of a free associative unital algebra (letterplace implementation)
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: x+y x + y sage: x*y !=y*x True sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F sage: (y^3).reduce(I) y*y*y sage: (y^3).normal_form(I) y*y*z - y*z*y + y*z*z
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> x+y x + y >>> x*y !=y*x True >>> I = F*[x*y+y*z,x**Integer(2)+x*y-y*x-y**Integer(2)]*F >>> (y**Integer(3)).reduce(I) y*y*y >>> (y**Integer(3)).normal_form(I) y*y*z - y*z*y + y*z*z
Here is an example with nontrivial degree weights:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: I = F*[x*y-y*x, x^2+2*y*z, (x*y)^2-z^2]*F sage: x.degree() 2 sage: y.degree() 1 sage: z.degree() 3 sage: (x*y)^3 x*y*x*y*x*y sage: ((x*y)^3).normal_form(I) z*z*y*x sage: ((x*y)^3).degree() 9
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> I = F*[x*y-y*x, x**Integer(2)+Integer(2)*y*z, (x*y)**Integer(2)-z**Integer(2)]*F >>> x.degree() 2 >>> y.degree() 1 >>> z.degree() 3 >>> (x*y)**Integer(3) x*y*x*y*x*y >>> ((x*y)**Integer(3)).normal_form(I) z*z*y*x >>> ((x*y)**Integer(3)).degree() 9
- degree()[source]#
Return the degree of this element.
Note
Generators may have a positive integral degree weight. All elements must be weighted homogeneous.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((x+y+z)^3).degree() 3 sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((x*y+z)^3).degree() 9
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((x+y+z)**Integer(3)).degree() 3 >>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((x*y+z)**Integer(3)).degree() 9
- lc()[source]#
The leading coefficient of this free algebra element, as element of the base ring.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lc() 20 sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lc().parent() is F.base() True sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2).lc() 4
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((Integer(2)*x+Integer(3)*y-Integer(4)*z)**Integer(2)*(Integer(5)*y+Integer(6)*z)).lc() 20 >>> ((Integer(2)*x+Integer(3)*y-Integer(4)*z)**Integer(2)*(Integer(5)*y+Integer(6)*z)).lc().parent() is F.base() True >>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((Integer(2)*x*y+z)**Integer(2)).lc() 4
- letterplace_polynomial()[source]#
Return the commutative polynomial that is used internally to represent this free algebra element.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((x+y-z)^2).letterplace_polynomial() x*x_1 + x*y_1 - x*z_1 + y*x_1 + y*y_1 - y*z_1 - z*x_1 - z*y_1 + z*z_1
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((x+y-z)**Integer(2)).letterplace_polynomial() x*x_1 + x*y_1 - x*z_1 + y*x_1 + y*y_1 - y*z_1 - z*x_1 - z*y_1 + z*z_1
If degree weights are used, the letterplace polynomial is homogenized by slack variables:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((x*y+z)^2).letterplace_polynomial() x*x__1*y_2*x_3*x__4*y_5 + x*x__1*y_2*z_3*x__4*x__5 + z*x__1*x__2*x_3*x__4*y_5 + z*x__1*x__2*z_3*x__4*x__5
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((x*y+z)**Integer(2)).letterplace_polynomial() x*x__1*y_2*x_3*x__4*y_5 + x*x__1*y_2*z_3*x__4*x__5 + z*x__1*x__2*x_3*x__4*y_5 + z*x__1*x__2*z_3*x__4*x__5
- lm()[source]#
The leading monomial of this free algebra element.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lm() x*x*y sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2).lm() x*y*x*y
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((Integer(2)*x+Integer(3)*y-Integer(4)*z)**Integer(2)*(Integer(5)*y+Integer(6)*z)).lm() x*x*y >>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((Integer(2)*x*y+z)**Integer(2)).lm() x*y*x*y
- lm_divides(p)[source]#
Tell whether or not the leading monomial of self divides the leading monomial of another element.
Note
A free algebra element \(p\) divides another one \(q\) if there are free algebra elements \(s\) and \(t\) such that \(spt = q\).
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2*z).lm() x*y*x*y*z sage: (y*x*y-y^4).lm() y*x*y sage: (y*x*y-y^4).lm_divides((2*x*y+z)^2*z) True
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((Integer(2)*x*y+z)**Integer(2)*z).lm() x*y*x*y*z >>> (y*x*y-y**Integer(4)).lm() y*x*y >>> (y*x*y-y**Integer(4)).lm_divides((Integer(2)*x*y+z)**Integer(2)*z) True
- lt()[source]#
The leading term (monomial times coefficient) of this free algebra element.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lt() 20*x*x*y sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2).lt() 4*x*y*x*y
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((Integer(2)*x+Integer(3)*y-Integer(4)*z)**Integer(2)*(Integer(5)*y+Integer(6)*z)).lt() 20*x*x*y >>> F = FreeAlgebra(QQ, implementation='letterplace', degrees=[Integer(2),Integer(1),Integer(3)], names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> ((Integer(2)*x*y+z)**Integer(2)).lt() 4*x*y*x*y
- normal_form(I)[source]#
Return the normal form of this element with respect to a twosided weighted homogeneous ideal.
INPUT:
A twosided homogeneous ideal \(I\) of the parent \(F\) of this element, \(x\).
OUTPUT:
The normal form of \(x\) wrt. \(I\).
Note
The normal form is computed by reduction with respect to a Groebnerbasis of \(I\) with degree bound \(deg(x)\).
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: (x^5).normal_form(I) -y*z*z*z*x - y*z*z*z*y - y*z*z*z*z
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> I = F*[x*y+y*z,x**Integer(2)+x*y-y*x-y**Integer(2)]*F >>> (x**Integer(5)).normal_form(I) -y*z*z*z*x - y*z*z*z*y - y*z*z*z*z
We verify two basic properties of normal forms: The difference of an element and its normal form is contained in the ideal, and if two elements of the free algebra differ by an element of the ideal then they have the same normal form:
sage: x^5 - (x^5).normal_form(I) in I True sage: (x^5+x*I.0*y*z-3*z^2*I.1*y).normal_form(I) == (x^5).normal_form(I) True
>>> from sage.all import * >>> x**Integer(5) - (x**Integer(5)).normal_form(I) in I True >>> (x**Integer(5)+x*I.gen(0)*y*z-Integer(3)*z**Integer(2)*I.gen(1)*y).normal_form(I) == (x**Integer(5)).normal_form(I) True
Here is an example with non-trivial degree weights:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[1,2,3]) sage: I = F*[x*y-y*x+z, y^2+2*x*z, (x*y)^2-z^2]*F sage: ((x*y)^3).normal_form(I) z*z*y*x - z*z*z sage: (x*y)^3-((x*y)^3).normal_form(I) in I True sage: ((x*y)^3+2*z*I.0*z+y*I.1*z-x*I.2*y).normal_form(I) == ((x*y)^3).normal_form(I) True
>>> 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) >>> I = F*[x*y-y*x+z, y**Integer(2)+Integer(2)*x*z, (x*y)**Integer(2)-z**Integer(2)]*F >>> ((x*y)**Integer(3)).normal_form(I) z*z*y*x - z*z*z >>> (x*y)**Integer(3)-((x*y)**Integer(3)).normal_form(I) in I True >>> ((x*y)**Integer(3)+Integer(2)*z*I.gen(0)*z+y*I.gen(1)*z-x*I.gen(2)*y).normal_form(I) == ((x*y)**Integer(3)).normal_form(I) True
- reduce(G)[source]#
Reduce this element by a list of elements or by a twosided weighted homogeneous ideal.
INPUT:
Either a list or tuple of weighted homogeneous elements of the free algebra, or an ideal of the free algebra, or an ideal in the commutative polynomial ring that is currently used to implement the multiplication in the free algebra.
OUTPUT:
The twosided reduction of this element by the argument.
Note
This may not be the normal form of this element, unless the argument is a twosided Groebner basis up to the degree of this element.
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: p = y^2*z*y^2+y*z*y*z*y
>>> from sage.all import * >>> F = FreeAlgebra(QQ, implementation='letterplace', names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3) >>> I = F*[x*y+y*z,x**Integer(2)+x*y-y*x-y**Integer(2)]*F >>> p = y**Integer(2)*z*y**Integer(2)+y*z*y*z*y
We compute the letterplace version of the Groebner basis of \(I\) with degree bound 4:
sage: G = F._reductor_(I.groebner_basis(4).gens(),4) sage: G.ring() is F.current_ring() True
>>> from sage.all import * >>> G = F._reductor_(I.groebner_basis(Integer(4)).gens(),Integer(4)) >>> G.ring() is F.current_ring() True
Since the element \(p\) is of degree 5, it is no surprise that its reductions with respect to the original generators of \(I\) (of degree 2), or with respect to \(G\) (Groebner basis with degree bound 4), or with respect to the Groebner basis with degree bound 5 (which yields its normal form) are pairwise different:
sage: p.reduce(I) y*y*z*y*y + y*z*y*z*y sage: p.reduce(G) y*y*z*z*y + y*z*y*z*y - y*z*z*y*y + y*z*z*z*y sage: p.normal_form(I) y*y*z*z*z + y*z*y*z*z - y*z*z*y*z + y*z*z*z*z sage: p.reduce(I) != p.reduce(G) != p.normal_form(I) != p.reduce(I) True
>>> from sage.all import * >>> p.reduce(I) y*y*z*y*y + y*z*y*z*y >>> p.reduce(G) y*y*z*z*y + y*z*y*z*y - y*z*z*y*y + y*z*z*z*y >>> p.normal_form(I) y*y*z*z*z + y*z*y*z*z - y*z*z*y*z + y*z*z*z*z >>> p.reduce(I) != p.reduce(G) != p.normal_form(I) != p.reduce(I) True
- sage.algebras.letterplace.free_algebra_element_letterplace.poly_reduce(ring=None, interruptible=True, attributes=None, *args)[source]#
This function is an automatically generated C wrapper around the Singular function ‘NF’.
This wrapper takes care of converting Sage datatypes to Singular datatypes and vice versa. In addition to whatever parameters the underlying Singular function accepts when called, this function also accepts the following keyword parameters:
INPUT:
args– a list of argumentsring– a multivariate polynomial ringinterruptible– ifTruepressing Ctrl + C during the execution of this function will interrupt the computation (default:True)attributes– a dictionary of optional Singular attributes assigned to Singular objects (default:None)
If
ringis not specified, it is guessed from the given arguments. If this is not possible, then a dummy ring, univariate polynomial ring overQQ, is used.EXAMPLES:
sage: groebner = sage.libs.singular.function_factory.ff.groebner sage: P.<x, y> = PolynomialRing(QQ) sage: I = P.ideal(x^2-y, y+x) sage: groebner(I) [x + y, y^2 - y] sage: triangL = sage.libs.singular.function_factory.ff.triang__lib.triangL sage: P.<x1, x2> = PolynomialRing(QQ, order='lex') sage: f1 = 1/2*((x1^2 + 2*x1 - 4)*x2^2 + 2*(x1^2 + x1)*x2 + x1^2) sage: f2 = 1/2*((x1^2 + 2*x1 + 1)*x2^2 + 2*(x1^2 + x1)*x2 - 4*x1^2) sage: I = Ideal(Ideal(f1,f2).groebner_basis()[::-1]) sage: triangL(I, attributes={I:{'isSB':1}}) [[x2^4 + 4*x2^3 - 6*x2^2 - 20*x2 + 5, 8*x1 - x2^3 + x2^2 + 13*x2 - 5], [x2, x1^2], [x2, x1^2], [x2, x1^2]]
>>> from sage.all import * >>> groebner = sage.libs.singular.function_factory.ff.groebner >>> P = PolynomialRing(QQ, names=('x', 'y',)); (x, y,) = P._first_ngens(2) >>> I = P.ideal(x**Integer(2)-y, y+x) >>> groebner(I) [x + y, y^2 - y] >>> triangL = sage.libs.singular.function_factory.ff.triang__lib.triangL >>> P = PolynomialRing(QQ, order='lex', names=('x1', 'x2',)); (x1, x2,) = P._first_ngens(2) >>> f1 = Integer(1)/Integer(2)*((x1**Integer(2) + Integer(2)*x1 - Integer(4))*x2**Integer(2) + Integer(2)*(x1**Integer(2) + x1)*x2 + x1**Integer(2)) >>> f2 = Integer(1)/Integer(2)*((x1**Integer(2) + Integer(2)*x1 + Integer(1))*x2**Integer(2) + Integer(2)*(x1**Integer(2) + x1)*x2 - Integer(4)*x1**Integer(2)) >>> I = Ideal(Ideal(f1,f2).groebner_basis()[::-Integer(1)]) >>> triangL(I, attributes={I:{'isSB':Integer(1)}}) [[x2^4 + 4*x2^3 - 6*x2^2 - 20*x2 + 5, 8*x1 - x2^3 + x2^2 + 13*x2 - 5], [x2, x1^2], [x2, x1^2], [x2, x1^2]]
The Singular documentation for ‘NF’ is given below.
5.1.131 reduce -------------- `*Syntax:*' `reduce (' poly_expression`,' ideal_expression `)' `reduce (' poly_expression`,' ideal_expression`,' int_expression `)' `reduce (' poly_expression`,' poly_expression`,' ideal_expression `)' `reduce (' vector_expression`,' ideal_expression `)' `reduce (' vector_expression`,' ideal_expression`,' int_expression `)' `reduce (' vector_expression`,' module_expression `)' `reduce (' vector_expression`,' module_expression`,' int_expression `)' `reduce (' vector_expression`,' poly_expression`,' module_expression `)' `reduce (' ideal_expression`,' ideal_expression `)' `reduce (' ideal_expression`,' ideal_expression`,' int_expression `)' `reduce (' ideal_expression`,' matrix_expression`,' ideal_expression `)' `reduce (' module_expression`,' ideal_expression `)' `reduce (' module_expression`,' ideal_expression`,' int_expression `)' `reduce (' module_expression`,' module_expression `)' `reduce (' module_expression`,' module_expression`,' int_expression `)' `reduce (' module_expression`,' matrix_expression`,' module_expression `)' `reduce (' poly/vector/ideal/module`,' ideal/module`,' int`,' intvec `)' `reduce (' ideal`,' matrix`,' ideal`,' int `)' `reduce (' poly`,' poly`,' ideal`,' int `)' `reduce (' poly`,' poly`,' ideal`,' int`,' intvec `)' `*Type:*' the type of the first argument `*Purpose:*' reduces a polynomial, vector, ideal or module to its normal form with respect to an ideal or module represented by a standard basis. Returns 0 if and only if the polynomial (resp. vector, ideal, module) is an element (resp. subideal, submodule) of the ideal (resp. module). The result may have no meaning if the second argument is not a standard basis. The third (optional) argument of type int modifies the behavior: * 0 default * 1 consider only the leading term and do no tail reduction. * 2 tail reduction:n the local/mixed ordering case: reduce also with bad ecart * 4 reduce without division, return possibly a non-zero constant multiple of the remainder If a second argument `u' of type poly or matrix is given, the first argument `p' is replaced by `p/u'. This works only for zero dimensional ideals (resp. modules) in the third argument and gives, even in a local ring, a reduced normal form which is the projection to the quotient by the ideal (resp. module). One may give a degree bound in the fourth argument with respect to a weight vector in the fifth argument in order have a finite computation. If some of the weights are zero, the procedure may not terminate! `*Note_*' The commands `reduce' and `NF' are synonymous. `*Example:*' ring r1 = 0,(z,y,x),ds; poly s1=2x5y+7x2y4+3x2yz3; poly s2=1x2y2z2+3z8; poly s3=4xy5+2x2y2z3+11x10; ideal i=s1,s2,s3; ideal j=std(i); reduce(3z3yx2+7y4x2+yx5+z12y2x2,j); ==> -yx5+2401/81y14x2+2744/81y11x5+392/27y8x8+224/81y5x11+16/81y2x14 reduce(3z3yx2+7y4x2+yx5+z12y2x2,j,1); ==> -yx5+z12y2x2 // 4 arguments: ring rs=0,x,ds; // normalform of 1/(1+x) w.r.t. (x3) up to degree 5 reduce(poly(1),1+x,ideal(x3),5); ==> // ** _ is no standard basis ==> 1-x+x2 * Menu: See * division:: * ideal:: * module:: * poly operations:: * std:: * vector::