Coverage for local/lib/python2.7/site-packages/sage/algebras/letterplace/free_algebra_element_letterplace.pyx : 70%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
############################################################################### # # Copyright (C) 2011 Simon King <simon.king@uni-jena.de> # Distributed under the terms of the GNU General Public License (GPL), # version 2 or any later version. The full text of the GPL is available at: # http://www.gnu.org/licenses/ # ###############################################################################
""" Weighted homogeneous elements of free algebras, in letterplace implementation.
AUTHOR:
- Simon King (2011-03-23): Trac ticket :trac:`7797`
""" from __future__ import print_function
from cpython.object cimport PyObject_RichCompare
# Define some singular functions
##################### # Free algebra elements cdef class FreeAlgebraElement_letterplace(AlgebraElement): """ Weighted 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
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
""" def __init__(self, A, x, check=True): """ INPUT:
- A free associative unital algebra in letterplace implementation, `A`. - A homogeneous polynomial that can be coerced into the currently used polynomial ring of `A`. - ``check`` (optional bool, default ``True``): Do not attempt the above coercion (for internal use only).
TESTS::
sage: from sage.algebras.letterplace.free_algebra_element_letterplace import FreeAlgebraElement_letterplace sage: F.<x,y,z> = FreeAlgebra(GF(3), implementation='letterplace') sage: F.set_degbound(2) sage: P = F.current_ring() sage: F.set_degbound(4) sage: P == F.current_ring() False sage: p = FreeAlgebraElement_letterplace(F,P.1*P.3+2*P.0*P.4); p -x*y + y*x sage: loads(dumps(p)) == p True
""" raise ValueError("Free algebras based on Letterplace can currently only work with weighted homogeneous elements") def __reduce__(self): """ Pickling.
TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: loads(dumps(x*y*x)) == x*y*x # indirect doctest True
""" def __copy__(self): """ TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: copy(x*y*z+z*y*x) == x*y*z+z*y*x # indirect doctest True
""" def __hash__(self): """ TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: set([x*y*z, z*y+x*z,x*y*z]) # indirect doctest {x*z + z*y, x*y*z}
"""
def __iter__(self): """ Iterates over the pairs "tuple of exponents, coefficient".
EXAMPLES::
sage: F.<w,x,y,z> = FreeAlgebra(GF(3), implementation='letterplace') sage: p = x*y-z^2 sage: sorted(p) # indirect doctest [((0, 0, 0, 1, 0, 0, 0, 1), 2), ((0, 1, 0, 0, 0, 0, 1, 0), 1)] """
def _repr_(self): """ TESTS::
sage: K.<z> = GF(25) sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace') sage: -(a+b*(z+1)-c)^2 # indirect doctest -a*a + (4*z + 4)*a*b + a*c + (4*z + 4)*b*a + (2*z + 1)*b*b + (z + 1)*b*c + c*a + (z + 1)*c*b - c*c
It is possible to change the names temporarily::
sage: from sage.structure.parent_gens import localvars sage: with localvars(F, ['w', 'x','y']): ....: print(a+b*(z+1)-c) w + (z + 1)*x - y sage: print(a+b*(z+1)-c) a + (z + 1)*b - c
""" else: else: else: else: else: else: L.extend(['+',repr(c)]) else: else: if L: L.extend(['-',repr(-c)]) else: L.append(repr(c)) else: else: else: else: else: else: if L: L.extend(['+',repr(c)]) else: L.append(repr(c))
def _latex_(self): """ TESTS::
sage: K.<z> = GF(25) sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace', degrees=[1,2,3]) sage: -(a*b*(z+1)-c)^2 (2*z + 1)*a*b*a*b + (z + 1)*a*b*c + (z + 1)*c*a*b - c*c sage: latex(-(a*b*(z+1)-c)^2) # indirect doctest \left(2 z + 1\right) a b a b + \left(z + 1\right) a b c + \left(z + 1\right) c a b - c c
""" for E,c in zip(self._poly.exponents(),self._poly.coefficients()): monstr = P.exponents_to_latex(E) if monstr: if c==1: if L: L.extend(['+',monstr]) else: L.append(monstr) elif c==-1: if L: L.extend(['-',monstr]) else: L.append('-'+monstr) else: if L: if c>=0: L.extend(['+',repr(latex(c))+' '+monstr]) else: L.extend(['-',repr(latex(-c))+' '+monstr]) else: L.append(repr(latex(c))+' '+monstr) else: if c>=0: if L: L.extend(['+',repr(latex(c))]) else: L.append(repr(latex(c))) else: if L: L.extend(['-',repr(latex(-c))]) else: L.append(repr(c)) else: if L: L.extend(['+',monstr]) else: L.append(monstr) else: L.append('-'+monstr) else: else: else: if L: L.extend(['+',repr(latex(c))]) else: L.append(repr(latex(c))) return '0'
def degree(self): """ 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
"""
def letterplace_polynomial(self): """ 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
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
"""
def lm(self): """ 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
"""
def lt(self): """ 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
"""
def lc(self): """ 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
"""
def __nonzero__(self): """ TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: bool(x) # indirect doctest True sage: bool(F.zero()) False
"""
def lm_divides(self, FreeAlgebraElement_letterplace p): """ 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
""" raise TypeError("The two arguments must be elements in the same free algebra.") return False cdef int i return True return False
cpdef _richcmp_(self, other, int op): """ Implement comparisons, using the Cython richcmp convention.
TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: p = ((2*x+3*y-4*z)^2*(5*y+6*z)) sage: p - p.lt() < p # indirect doctest True """
################################ ## Arithmetic cpdef _neg_(self): """ TESTS::
sage: K.<z> = GF(25) sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace') sage: -((z+2)*a^2*b+3*c^3) # indirect doctest (4*z + 3)*a*a*b + (2)*c*c*c sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: -(3*x*y+2*z^2) -3*x*y - 2*z*z
""" cpdef _add_(self, other): """ Addition, under the side condition that either one summand is zero, or both summands have the same degree.
TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: x+y # indirect doctest x + y sage: x+1 Traceback (most recent call last): ... ArithmeticError: Can only add elements of the same weighted degree sage: x+0 x sage: 0+x x
""" # update the polynomials
cpdef _sub_(self, other): """ Difference, under the side condition that either one summand is zero or both have the same weighted degree.
TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: x*y-y*x # indirect doctest x*y - y*x sage: x-1 Traceback (most recent call last): ... ArithmeticError: Can only subtract elements of the same degree sage: x-0 x sage: 0-x -x
Here is an example with non-trivial degree weights::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: x*y+z x*y + z
""" # update the polynomials
cpdef _lmul_(self, Element right): """ Multiplication from the right with an element of the base ring.
TESTS::
sage: K.<z> = GF(25) sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace') sage: (a+b)*(z+1) # indirect doctest (z + 1)*a + (z + 1)*b
"""
cpdef _rmul_(self, Element left): """ Multiplication from the left with an element of the base ring.
TESTS::
sage: K.<z> = GF(25) sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace') sage: (z+1)*(a+b) # indirect doctest (z + 1)*a + (z + 1)*b
"""
cpdef _mul_(self, other): """ Product of two free algebra elements in letterplace implementation.
TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: (x*y+z)*z # indirect doctest x*y*z + z*z
""" # we must put the polynomials into the same ring
def __pow__(FreeAlgebraElement_letterplace self, int n, k): """ TESTS::
sage: K.<z> = GF(25) sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace') sage: (a+z*b)^3 # indirect doctest a*a*a + (z)*a*a*b + (z)*a*b*a + (z + 3)*a*b*b + (z)*b*a*a + (z + 3)*b*a*b + (z + 3)*b*b*a + (4*z + 3)*b*b*b
""" raise ValueError("Negative exponents are not allowed") return FreeAlgebraElement_letterplace(A, A._current_ring(1), check=False) return self cdef MPolynomial_libsingular p,q cdef int i
## Groebner related stuff def reduce(self, G): """ 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
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
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
""" return P.zero() else:
def normal_form(self,I): """ 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
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
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
""" raise ValueError("Can not compute normal form wrt an ideal that does not belong to %s" % self._parent) |