Exterior algebras Gröbner bases

This contains the backend implementations in Cython for the Gröbner bases of exterior algebra.

AUTHORS:

  • Trevor K. Karn, Travis Scrimshaw (July 2022): Initial implementation

Todo

  • Refactor sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic so the result of the Gröbner bases is the corresponding sibling class.

  • Construct a custom class for storing/manipulating the current Gröbner basis during the computation.

  • Implement custom (sparse) linear algebra computation (in parallel) to take advantage of the structure of the vectors during reduction.

  • Extend this to work for any arbitrary Clifford algebra.

  • Extend this to work over more general rings.

  • Implement interfaces with other software, such as Macaulay2, REDUCE (specifically xideal), and f4ncgb (arXiv 2505.19304), for allowing easy access to alternative implementations.

class sage.algebras.exterior_algebra_groebner.GBElement[source]

Bases: object

Helper class for storing an element with its leading support both as a FrozenBitset and an Integer.

class sage.algebras.exterior_algebra_groebner.GroebnerStrategy[source]

Bases: object

A strategy for computing a Gröbner basis.

INPUT:

  • I – the ideal

compute_groebner(reduced=True)[source]

Compute the (reduced) left/right Gröbner basis for the ideal I.

EXAMPLES:

sage: E.<y, x> = ExteriorAlgebra(QQ)
sage: I = E.ideal([x*y - x, x*y - 1], side='left')
sage: I.groebner_basis()  # indirect doctest
(1,)
sage: J = E.ideal([x*y - x, 2*x*y - 2], side='left')
sage: J.groebner_basis()  # indirect doctest
(1,)

sage: E.<a,b,c,d> = ExteriorAlgebra(QQ)
sage: I = E.ideal([a+b*c], side='left')
sage: I.groebner_basis()  # indirect doctest
(a*b, a*c, b*c + a)
sage: I = E.ideal([a+b*c], side='twosided')
sage: I.groebner_basis()  # indirect doctest
(a*b, a*c, b*c + a, a*d)

sage: E = ExteriorAlgebra(QQ, 5)
sage: e0, e1, e2, e3, e4 = E.algebra_generators()
sage: G = [e0*e2 - e0*e3 + e2*e3, e1*e2 - e1*e4 + e2*e4]
sage: J = E.ideal(G)
sage: J.groebner_basis()  # indirect doctest
(e0*e2 - e0*e3 + e2*e3,
 e1*e2 - e1*e4 + e2*e4,
 -e0*e1*e3 + e0*e1*e4 - e0*e3*e4 + e1*e3*e4)
sage: all(J.reduce(b * g) == 0 for b in E.basis() for g in G)
True

>>> from sage.all import *
>>> E = ExteriorAlgebra(QQ, names=('y', 'x',)); (y, x,) = E._first_ngens(2)
>>> I = E.ideal([x*y - x, x*y - Integer(1)], side='left')
>>> I.groebner_basis()  # indirect doctest
(1,)
>>> J = E.ideal([x*y - x, Integer(2)*x*y - Integer(2)], side='left')
>>> J.groebner_basis()  # indirect doctest
(1,)

>>> E = ExteriorAlgebra(QQ, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = E._first_ngens(4)
>>> I = E.ideal([a+b*c], side='left')
>>> I.groebner_basis()  # indirect doctest
(a*b, a*c, b*c + a)
>>> I = E.ideal([a+b*c], side='twosided')
>>> I.groebner_basis()  # indirect doctest
(a*b, a*c, b*c + a, a*d)

>>> E = ExteriorAlgebra(QQ, Integer(5))
>>> e0, e1, e2, e3, e4 = E.algebra_generators()
>>> G = [e0*e2 - e0*e3 + e2*e3, e1*e2 - e1*e4 + e2*e4]
>>> J = E.ideal(G)
>>> J.groebner_basis()  # indirect doctest
(e0*e2 - e0*e3 + e2*e3,
 e1*e2 - e1*e4 + e2*e4,
 -e0*e1*e3 + e0*e1*e4 - e0*e3*e4 + e1*e3*e4)
>>> all(J.reduce(b * g) == Integer(0) for b in E.basis() for g in G)
True

Check using the example at the end of Section 5 of [Stokes1990] that the constructed Gröbner basis verifies ideal membership:

sage: E = ExteriorAlgebra(QQ, 6)
sage: e0, e1, e2, e3, e4, e5 = E.algebra_generators()
sage: G = [e4*e5 - e1*e2, e3*e4 - e0*e2]
sage: J = E.ideal(G)
sage: J.groebner_basis()
(e0*e2*e3, e0*e2*e4, e1*e2*e4, -e0*e2 + e3*e4,
 e0*e2*e5 - e1*e2*e3, e1*e2*e5, -e1*e2 + e4*e5)
sage: J.reduce(e1 * e2 * e5)
0
sage: all(J.reduce(b * g) == 0 for b in E.basis() for g in G)
True
[Python] 
>>> from sage.all import *
>>> E = ExteriorAlgebra(QQ, Integer(6))
>>> e0, e1, e2, e3, e4, e5 = E.algebra_generators()
>>> G = [e4*e5 - e1*e2, e3*e4 - e0*e2]
>>> J = E.ideal(G)
>>> J.groebner_basis()
(e0*e2*e3, e0*e2*e4, e1*e2*e4, -e0*e2 + e3*e4,
 e0*e2*e5 - e1*e2*e3, e1*e2*e5, -e1*e2 + e4*e5)
>>> J.reduce(e1 * e2 * e5)
0
>>> all(J.reduce(b * g) == Integer(0) for b in E.basis() for g in G)
True
groebner_basis[source]
monomial_to_int()[source]

Helper function to display the monomials in their term order used by self.

EXAMPLES:

sage: from sage.algebras.exterior_algebra_groebner import *
sage: E.<a,b,c,d> = ExteriorAlgebra(QQ)
sage: I = E.ideal([a, b])
sage: GroebnerStrategyDegLex(I).monomial_to_int()
{1: 0,
 a: 1, b: 2, c: 3, d: 4,
 a*b: 5, a*c: 6, a*d: 7, b*c: 8, b*d: 9, c*d: 10,
 a*b*c: 11, a*b*d: 12, a*c*d: 13, b*c*d: 14,
 a*b*c*d: 15}
sage: GroebnerStrategyDegRevLex(I).monomial_to_int()
{1: 0,
 a: 4, b: 3, c: 2, d: 1,
 a*b: 10, a*c: 9, a*d: 7, b*c: 8, b*d: 6, c*d: 5,
 a*b*c: 14, a*b*d: 13, a*c*d: 12, b*c*d: 11,
 a*b*c*d: 15}

>>> from sage.all import *
>>> from sage.algebras.exterior_algebra_groebner import *
>>> E = ExteriorAlgebra(QQ, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = E._first_ngens(4)
>>> I = E.ideal([a, b])
>>> GroebnerStrategyDegLex(I).monomial_to_int()
{1: 0,
 a: 1, b: 2, c: 3, d: 4,
 a*b: 5, a*c: 6, a*d: 7, b*c: 8, b*d: 9, c*d: 10,
 a*b*c: 11, a*b*d: 12, a*c*d: 13, b*c*d: 14,
 a*b*c*d: 15}
>>> GroebnerStrategyDegRevLex(I).monomial_to_int()
{1: 0,
 a: 4, b: 3, c: 2, d: 1,
 a*b: 10, a*c: 9, a*d: 7, b*c: 8, b*d: 6, c*d: 5,
 a*b*c: 14, a*b*d: 13, a*c*d: 12, b*c*d: 11,
 a*b*c*d: 15}
reduce(f)[source]

Reduce f modulo the ideal with Gröbner basis G.

EXAMPLES:

sage: E.<a,b,c,d,e> = ExteriorAlgebra(QQ)
sage: rels = [c*d*e - b*d*e + b*c*e - b*c*d,
....:         c*d*e - a*d*e + a*c*e - a*c*d,
....:         b*d*e - a*d*e + a*b*e - a*b*d,
....:         b*c*e - a*c*e + a*b*e - a*b*c,
....:         b*c*d - a*c*d + a*b*d - a*b*c]
sage: I = E.ideal(rels)
sage: GB = I.groebner_basis()
sage: I._groebner_strategy.reduce(a*b*e)
a*b*e
sage: I._groebner_strategy.reduce(b*d*e)
a*b*d - a*b*e + a*d*e
sage: I._groebner_strategy.reduce(c*d*e)
a*c*d - a*c*e + a*d*e
sage: I._groebner_strategy.reduce(a*b*c*d*e)
0
sage: I._groebner_strategy.reduce(a*b*c*d)
0
sage: I._groebner_strategy.reduce(E.zero())
0

>>> from sage.all import *
>>> E = ExteriorAlgebra(QQ, names=('a', 'b', 'c', 'd', 'e',)); (a, b, c, d, e,) = E._first_ngens(5)
>>> rels = [c*d*e - b*d*e + b*c*e - b*c*d,
...         c*d*e - a*d*e + a*c*e - a*c*d,
...         b*d*e - a*d*e + a*b*e - a*b*d,
...         b*c*e - a*c*e + a*b*e - a*b*c,
...         b*c*d - a*c*d + a*b*d - a*b*c]
>>> I = E.ideal(rels)
>>> GB = I.groebner_basis()
>>> I._groebner_strategy.reduce(a*b*e)
a*b*e
>>> I._groebner_strategy.reduce(b*d*e)
a*b*d - a*b*e + a*d*e
>>> I._groebner_strategy.reduce(c*d*e)
a*c*d - a*c*e + a*d*e
>>> I._groebner_strategy.reduce(a*b*c*d*e)
0
>>> I._groebner_strategy.reduce(a*b*c*d)
0
>>> I._groebner_strategy.reduce(E.zero())
0

Check Issue #37108 is fixed:

sage: E = ExteriorAlgebra(QQ, 6)
sage: E.inject_variables(verbose=False)
sage: gens = [-e0*e1*e2 + e0*e1*e5 - e0*e2*e3 - e0*e3*e5 + e1*e2*e3 + e1*e3*e5,
....:         e1*e2 - e1*e5 + e2*e5, e0*e2 - e0*e4 + e2*e4,
....:         e3*e4 - e3*e5 + e4*e5, e0*e1 - e0*e3 + e1*e3]
sage: I = E.ideal(gens)
sage: S = E.quo(I)
sage: I.reduce(e1*e3*e4*e5)
0
[Python] 
>>> from sage.all import *
>>> E = ExteriorAlgebra(QQ, Integer(6))
>>> E.inject_variables(verbose=False)
>>> gens = [-e0*e1*e2 + e0*e1*e5 - e0*e2*e3 - e0*e3*e5 + e1*e2*e3 + e1*e3*e5,
...         e1*e2 - e1*e5 + e2*e5, e0*e2 - e0*e4 + e2*e4,
...         e3*e4 - e3*e5 + e4*e5, e0*e1 - e0*e3 + e1*e3]
>>> I = E.ideal(gens)
>>> S = E.quo(I)
>>> I.reduce(e1*e3*e4*e5)
0
reduce_computed_gb()[source]

Convert the computed Gröbner basis to a reduced Gröbner basis.

EXAMPLES:

sage: E.<x,y,z> = ExteriorAlgebra(QQ)
sage: I = E.ideal([x+y*z, x - z - y, x*y*z])
sage: I.groebner_basis(reduced=False)
(x, x*y, -x + y + z, y*z + x, x*y*z)
sage: I._groebner_strategy.reduce_computed_gb()
sage: I._groebner_strategy.groebner_basis
(x, y + z)

>>> from sage.all import *
>>> E = ExteriorAlgebra(QQ, names=('x', 'y', 'z',)); (x, y, z,) = E._first_ngens(3)
>>> I = E.ideal([x+y*z, x - z - y, x*y*z])
>>> I.groebner_basis(reduced=False)
(x, x*y, -x + y + z, y*z + x, x*y*z)
>>> I._groebner_strategy.reduce_computed_gb()
>>> I._groebner_strategy.groebner_basis
(x, y + z)
sorted_monomials(as_dict=False)[source]

Helper function to display the monomials in their term order used by self.

EXAMPLES:

sage: from sage.algebras.exterior_algebra_groebner import *
sage: E.<x,y,z> = ExteriorAlgebra(QQ)
sage: I = E.ideal([x, y])
sage: GroebnerStrategyNegLex(I).sorted_monomials()
[1, x, y, x*y, z, x*z, y*z, x*y*z]
sage: GroebnerStrategyDegLex(I).sorted_monomials()
[1, x, y, z, x*y, x*z, y*z, x*y*z]
sage: GroebnerStrategyDegRevLex(I).sorted_monomials()
[1, z, y, x, y*z, x*z, x*y, x*y*z]

sage: E.<a,b,c,d> = ExteriorAlgebra(QQ)
sage: I = E.ideal([a, b])
sage: GroebnerStrategyNegLex(I).sorted_monomials()
[1,
 a,
 b, a*b,
 c, a*c, b*c, a*b*c,
 d, a*d, b*d, a*b*d, c*d, a*c*d, b*c*d, a*b*c*d]
sage: GroebnerStrategyDegLex(I).sorted_monomials()
[1,
 a, b, c, d,
 a*b, a*c, a*d, b*c, b*d, c*d,
 a*b*c, a*b*d, a*c*d, b*c*d,
 a*b*c*d]
sage: GroebnerStrategyDegRevLex(I).sorted_monomials()
[1,
 d, c, b, a,
 c*d, b*d, a*d, b*c, a*c, a*b,
 b*c*d, a*c*d, a*b*d, a*b*c,
 a*b*c*d]

>>> from sage.all import *
>>> from sage.algebras.exterior_algebra_groebner import *
>>> E = ExteriorAlgebra(QQ, names=('x', 'y', 'z',)); (x, y, z,) = E._first_ngens(3)
>>> I = E.ideal([x, y])
>>> GroebnerStrategyNegLex(I).sorted_monomials()
[1, x, y, x*y, z, x*z, y*z, x*y*z]
>>> GroebnerStrategyDegLex(I).sorted_monomials()
[1, x, y, z, x*y, x*z, y*z, x*y*z]
>>> GroebnerStrategyDegRevLex(I).sorted_monomials()
[1, z, y, x, y*z, x*z, x*y, x*y*z]

>>> E = ExteriorAlgebra(QQ, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = E._first_ngens(4)
>>> I = E.ideal([a, b])
>>> GroebnerStrategyNegLex(I).sorted_monomials()
[1,
 a,
 b, a*b,
 c, a*c, b*c, a*b*c,
 d, a*d, b*d, a*b*d, c*d, a*c*d, b*c*d, a*b*c*d]
>>> GroebnerStrategyDegLex(I).sorted_monomials()
[1,
 a, b, c, d,
 a*b, a*c, a*d, b*c, b*d, c*d,
 a*b*c, a*b*d, a*c*d, b*c*d,
 a*b*c*d]
>>> GroebnerStrategyDegRevLex(I).sorted_monomials()
[1,
 d, c, b, a,
 c*d, b*d, a*d, b*c, a*c, a*b,
 b*c*d, a*c*d, a*b*d, a*b*c,
 a*b*c*d]
class sage.algebras.exterior_algebra_groebner.GroebnerStrategyDegLex[source]

Bases: GroebnerStrategy

Gröbner basis strategy implementing degree lex ordering.

class sage.algebras.exterior_algebra_groebner.GroebnerStrategyDegRevLex[source]

Bases: GroebnerStrategy

Gröbner basis strategy implementing degree revlex ordering.

class sage.algebras.exterior_algebra_groebner.GroebnerStrategyNegLex[source]

Bases: GroebnerStrategy

Gröbner basis strategy implementing neglex ordering.