Coverage for local/lib/python2.7/site-packages/sage/algebras/letterplace/letterplace_ideal.pyx : 99%
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/ # ###############################################################################
""" 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:`7797`.
"""
from sage.algebras.letterplace.free_algebra_letterplace cimport FreeAlgebra_letterplace from sage.algebras.letterplace.free_algebra_element_letterplace cimport FreeAlgebraElement_letterplace
##################### # Define some singular functions
""" 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
""" """ INPUT:
- ``ring``: A free algebra in letterplace implementation. - ``gens``: List, tuple or sequence of generators. - ``coerce`` (optional bool, default ``True``): Shall ``gens`` be coerced first? - ``side``: optional string, one of ``"twosided"`` (default), ``"left"`` or ``"right"``. Determines whether the ideal is a left, right or twosided ideal. Groebner bases or only supported in the twosided case.
TESTS::
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: from sage.algebras.letterplace.letterplace_ideal import LetterplaceIdeal sage: LetterplaceIdeal(F,x) Twosided Ideal (x) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field sage: LetterplaceIdeal(F,[x,y],side='left') Left Ideal (x, y) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
It is not correctly detected that this class inherits from an extension class. Therefore, we have to skip one item of the test suite::
sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F sage: TestSuite(I).run(skip=['_test_category'],verbose=True) running ._test_eq() . . . pass running ._test_new() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass
""" """ 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.
NOTES:
- 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`.
""" cdef FreeAlgebraElement_letterplace x degbound = A.degbound() # Set the options required by letterplace
""" The containment test is based on a normal form computation.
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*I.0-I.1*y+I.0*y in I # indirect doctest True sage: 1 in I False
"""
""" 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, if ``G`` is an element of the algebra. - The reduction of this ideal by the elements resp. generators of ``G``, if ``G`` 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
""" |