Gröbner bases and membership¶

These operations compute reduced Gröbner bases over exact coefficient fields, using Buchberger's algorithm and Gebauer–Möller pair pruning. It selects the least LCM first, with ties broken by stable pair indices. Over primes below \(2^{31}\) under GRLEX and GREVLEX, bases computed without cofactors use F4, which reduces all pairs of least LCM degree together as one sparse matrix; the result is the same reduced basis. Over QQ under GREVLEX the inputs are homogenized and the basis is reconstructed from images modulo primes and certified by exact checks, or computed exactly if reconstruction gives up; the result is again the same reduced basis. Bases are monic and sorted by decreasing leading monomial.

LEX, GRLEX, and GREVLEX are accepted; KERNEL is storage order and raises DOMAIN. Generators may arrive in another order and are reordered explicitly. All generators must belong to one coefficient field. Empty or all-zero generator lists produce the empty basis.

Cofactor tracking is optional because witnesses can grow much larger than the basis. Membership enables tracking and returns multipliers in the original generator order, including zero generators. The checker verifies only the polynomial identity and does not compute a Gröbner basis.

Example¶

The equations \(x-y=0\) and \(x^2-1=0\) imply \(y^2-1=0\). membership returns multipliers for the original generators, and check_membership verifies the identity without repeating the Gröbner computation:

"""Prove an ideal membership using an independently checked identity."""
from std.testing import assert_equal, assert_true
from polynomials import Budget, QQ, NoContext, PolynomialRing, SparsePoly, groebner, membership, check_membership


def main() raises:
    var work = Budget()
    var ring = PolynomialRing[QQ].create(["x", "y"], NoContext(), work)
    var generators: List[SparsePoly[QQ]] = [ring.parse("x - y", work), ring.parse("x^2 - 1", work)]
    var basis = groebner(generators, generators[0].order, work)
    var candidate = ring.parse("y^2 - 1", work)
    var witness = membership(candidate, generators, candidate.order, work)
    assert_true(Bool(witness))
    var verified = check_membership(candidate, generators, witness.value(), work)
    assert_equal(len(basis.basis), 2)
    assert_true(verified)
    print("Basis elements:", len(basis.basis))
    print("Membership checked:", verified)

Basis elements: 2
Membership checked: True

Exact complex coefficients¶

QQi represents the field \(\mathbb Q(i)\): numbers \(a+bi\) with rational \(a,b\). Construct a coefficient as QQi(ExactComplex(real, imag)), importing ExactComplex and Rational from apn_mojo. Its context is NoContext(); there is no precision parameter. Arithmetic, zero tests, reduction and membership identities are exact.

The existing groebner, reduce, membership, MembershipCertificate and check_membership APIs accept SparsePoly[QQi]. LEX, GRLEX and GREVLEX and optional cofactor tracking have the same semantics as over QQ.

For \(I=\langle x^2-iy,xy-1\rangle\) in lexicographic order \(x>y\), the reduced basis is \([x-iy^2,y^3+i]\), and \(x^3\) reduces to \(i\):

"""Exact complex coefficients, Gröbner reduction, and membership witnesses."""
from apn_mojo import ExactComplex
from polynomials import Budget, QQi, NoContext, SparsePoly, MonomialOrder, groebner, reduce, membership, check_membership


def main() raises:
    var work = Budget()
    var order = MonomialOrder(MonomialOrder.LEX, [0, 1], work)
    var x = SparsePoly[QQi].variable(0, order, NoContext(), work)
    var y = SparsePoly[QQi].variable(1, order, NoContext(), work)
    var i = QQi(ExactComplex(0, 1))
    var imag = SparsePoly[QQi].constant(i, order, work)
    var one = SparsePoly[QQi].constant(QQi.one(NoContext()), order, work)
    var generators: List[SparsePoly[QQi]] = [x.pow(2, work).sub(y.scale(i, work), work), x.mul(y, work).sub(one, work)]
    var basis = groebner(generators, order, work)
    var expected: List[SparsePoly[QQi]] = [x.sub(y.pow(2, work).scale(i, work), work), y.pow(3, work).add(imag, work)]
    if basis.basis != expected:
        raise Error("unexpected exact complex basis")
    print("Exact complex basis elements:", len(basis.basis))
    var cube = x.pow(3, work)
    if reduce(cube, basis, work).remainder != imag:
        raise Error("x^3 should reduce to i")
    print("x^3 reduces exactly to i")
    var target = cube.sub(imag, work)
    var proof = membership(target, generators, order, work)
    if not proof or not check_membership(target, generators, proof.value(), work):
        raise Error("complex membership witness did not check")
    print("Complex membership certificate checked")

Exact complex basis elements: 2
x^3 reduces exactly to i
Complex membership certificate checked

This field includes rational complex numbers, but not coefficients such as \(\sqrt{2}+i\). Rounded ComplexDomain and enclosing ComplexBallDomain remain separate numerical domains and cannot instantiate an exact Gröbner basis. The kernel codec still accepts QQ polynomials only; complex membership certificates are checked by the library and have no kernel wire encoding. QQi also supports exact factorization. Exact complex algebraic-number values use poly.algebraic.Complex and the inferred QQbar field, which also supports these field-generic Gröbner operations. See algebraic coefficients. Numerical complex roots use certified regions.

GroebnerBasis¶

struct GroebnerBasis[C: CoefficientField](Copyable, Movable, Writable)

A reduced monic basis and optional combinations of its input generators.

Parameters.

• C: The coefficient field.

Defined in src/polynomials/groebner.mojo.

GroebnerBasis.__init__¶

def __init__(out self, var order: MonomialOrder, var basis: List[SparsePoly[Self.C]], var cofactors: Optional[List[List[SparsePoly[Self.C]]]])

Hold a basis and optional cofactor rows, without a trace.

Arguments.

• order: The admissible monomial order used by the basis.
• basis: The reduced basis in decreasing leading-monomial order.
• cofactors: One row per basis element, with columns in input generator order.

GroebnerBasis.__init__¶

def __init__(out self, var order: MonomialOrder, var basis: List[SparsePoly[Self.C]], var cofactors: Optional[List[List[SparsePoly[Self.C]]]], var trace: Optional[GroebnerTrace[Self.C]])

Hold a basis with optional cofactor rows and an optional trace.

Arguments.

• order: The admissible monomial order used by the basis.
• basis: The reduced basis in decreasing leading-monomial order.
• cofactors: One row per basis element, with columns in input generator order.
• trace: How each basis element arises from the input generators.

GroebnerTrace¶

@fieldwise_init
struct GroebnerTrace[C: CoefficientField](Copyable, Movable, Writable)

How every basis element arises from the input generators, as a straight-line combination.

Trace polynomial i, for i below generators, is input generator i in the basis's monomial order; polynomial generators + k is the sum of the multiples in step k, which refer only to earlier polynomials. Each basis element equals the trace polynomial basis_sources names, so it lies in the ideal of the generators, without its combination of them ever being expanded.

Parameters.

• C: The coefficient field.

Defined in src/polynomials/groebner.mojo.

GroebnerTrace.replay¶

def replay(self, generators: List[SparsePoly[Self.C]], basis: List[SparsePoly[Self.C]], mut budget: Budget) raises PolyError -> Bool

Recompute every trace polynomial and compare the basis with its sources.

Arguments.

• generators: The input generators, in trace order.
• basis: The basis the trace describes.
• budget: The shared work allowance.

Returns. Whether every basis element equals its source trace polynomial.

Raises.

• PolyError: DOMAIN for mixed fields or orders, LIMIT or CAPACITY on work limits.

GroebnerTrace.cofactors¶

def cofactors(self, index: Int, generators: List[SparsePoly[Self.C]], mut budget: Budget) raises PolyError -> List[SparsePoly[Self.C]]

Expand one basis element's combination of the input generators.

Arguments.

• index: The basis element.
• generators: The input generators, in trace order; their order is that of the cofactors.
• budget: The shared work allowance.

Returns. One multiplier per input generator, summing with them to the basis element.

Raises.

• PolyError: DOMAIN for an index outside the basis, LIMIT or CAPACITY on work limits.

TraceTerm¶

@fieldwise_init
struct TraceTerm[C: CoefficientField](Copyable, Movable, Writable)

One multiple in a trace step: a term times an earlier trace polynomial.

Parameters.

• C: The coefficient field.

Defined in src/polynomials/groebner.mojo.

groebner¶

def groebner[C: CoefficientField](generators: List[SparsePoly[C]], order: MonomialOrder, mut budget: Budget, track_cofactors: Bool = False, certify: Bool = True, trace: Bool = False) raises PolyError -> GroebnerBasis[C]

Compute the reduced monic basis with deterministic Gebauer–Möller pruning.

Parameters.

• C: The coefficient field.

Arguments.

• generators: Polynomials in one field; zero generators are allowed.
• order: LEX, GRLEX, or GREVLEX with every input variable listed.
• budget: The shared work allowance.
• track_cofactors: Whether to retain combinations of the original generators.
• certify: Whether a basis over QQ computed from modular images is certified exactly; without it the result is the reduced basis with high probability, and is not proved.
• trace: Whether to record how each basis element arises from the generators, without expanding cofactor rows.

Returns. The reduced basis, optional cofactor rows in generator order, and an optional trace.

Raises.

• PolyError: DOMAIN for KERNEL order, mixed fields or malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/groebner.mojo.

reduce¶

def reduce[C: CoefficientField](f: SparsePoly[C], basis: GroebnerBasis[C], mut budget: Budget) raises PolyError -> ListDivision[C]

Reduce a polynomial by a Gröbner basis in its chosen monomial order.

Parameters.

• C: The coefficient field.

Arguments.

• f: The polynomial to reduce.
• basis: The basis and its monomial order.
• budget: The shared work allowance.

Returns. Quotients in basis order and the unique normal form.

Raises.

• PolyError: DOMAIN for incompatible fields or invalid orders, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/groebner.mojo.

membership¶

def membership[C: CoefficientField](f: SparsePoly[C], generators: List[SparsePoly[C]], order: MonomialOrder, mut budget: Budget) raises PolyError -> Optional[MembershipCertificate[C]]

Find a certificate expressing f as a combination of the given generators.

Parameters.

• C: The coefficient field.

Arguments.

• f: The proposed ideal member.
• generators: The ordered original generators.
• order: The admissible monomial order used for the computation.
• budget: The shared work allowance.

Returns. Cofactors in generator order when f belongs to the ideal, otherwise None.

Raises.

• PolyError: DOMAIN for mixed fields or invalid orders, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/groebner.mojo.

check_groebner_basis¶

def check_groebner_basis[C: CoefficientField](generators: List[SparsePoly[C]], basis: GroebnerBasis[C], mut budget: Budget) raises PolyError -> Bool

Check that the generators reduce to zero modulo a basis and that the basis satisfies Buchberger's criterion.

Together these give ⊆ and make the basis a Gröbner basis. The check does not show that the basis lies in the generators' ideal (a trace or cofactor rows do that) or that it is reduced.

Parameters.

• C: The coefficient field.

Arguments.

• generators: The polynomials that must reduce to zero.
• basis: The basis and its monomial order.
• budget: The shared work allowance.

Returns. Whether every generator and every S-pair reduces to zero.

Raises.

• PolyError: DOMAIN for mixed fields or orders, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/groebner.mojo.

MembershipCertificate¶

@fieldwise_init
struct MembershipCertificate[C: CoefficientRing](Copyable, Movable, Writable)

Polynomial multipliers proving membership in the supplied ideal (B-C1).

Parameters.

• C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

check_membership¶

def check_membership[C: CoefficientRing](f: SparsePoly[C], generators: List[SparsePoly[C]], certificate: MembershipCertificate[C], mut budget: Budget) raises PolyError -> Bool

Check an ideal-membership identity without constructing a Gröbner basis.

Parameters.

• C: The coefficient ring.

Arguments.

• f: The claimed member of the ideal.
• generators: The original generators in certificate order.
• certificate: One multiplier per generator.
• budget: The shared work allowance.

Returns. Whether f equals the sum of multiplier times generator.

Raises.

• PolyError: DOMAIN for malformed input or mixed rings, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.