Gröbner bases and membership¶

Sparse coefficient arrays can describe systems of polynomial equations. Use a Gröbner basis for polynomial reduction and ideal membership. For real inequalities and sign conditions, see inequalities and CAD.

Prepare a basis and reuse it¶

The equations \(x-y=0\) and \(x^2-1=0\) imply \(y^2-1=0\). Each term below is an exponent tuple followed by its coefficient; no expression parser is involved.

"""Reuse a basis and recover a witness against the original generators."""
from poly import sparse
from std.testing import assert_equal, assert_true


def main() raises:
    var first = [((1, 0), 1), ((0, 1), -1)]  # x - y
    var second = [((2, 0), 1), ((0, 0), -1)]  # x**2 - 1
    var basis = sparse.groebner([first.copy(), second.copy()], order="lex")
    assert_true(sparse.check_groebner(basis))
    var candidate = [((0, 2), 1), ((0, 0), -1)]  # y**2 - 1
    print("Basis polynomials:", len(basis))
    print("Member:", sparse.contains(candidate, basis))
    var witness = sparse.membership(candidate, basis)
    assert_true(Bool(witness))
    assert_true(sparse.check_membership(witness.value()))
    var recovered = sparse.add(sparse.multiply(witness.value().cofactors[0], first), sparse.multiply(witness.value().cofactors[1], second))
    assert_equal(len(sparse.subtract(recovered, candidate)), 0)
    print("Original-generator identity checked")

Basis polynomials: 2
Member: True
Original-generator identity checked

sparse.groebner accepts an iterable of sparse polynomials. For differently typed polynomials, pass a tuple: the function infers their common field before computing the basis. Integer inputs promote to QQ; rational, Gaussian rational, and prime-field inputs retain their fields. Modular coefficients can mix with integers, but cannot mix implicitly with rationals or Gaussian rationals. Every polynomial must have the same power shape, and modular inputs must agree on the prime, including when a prepared polynomial is zero.

The result is an iterable of immutable sparse arrays. Reuse it with the functional calls sparse.reduce(p, basis), sparse.contains(p, basis), and sparse.membership(p, basis). A query can promote into the prepared field; it cannot widen that field. Prepare a new basis if the coefficient domain changes.

Choose order="lex" for lexicographic elimination, "grlex" for graded lexicographic order, or the default "grevlex" for graded reverse lexicographic order. axes lists variable priority from highest to lowest. Array outputs keep their usual canonical term storage; the prepared basis retains the computational order internally.

Membership here is over the inferred field. With integer input, the ideal generated by \(2x\) contains \(x\) over QQ. This is not integer-ring ideal membership.

Choose how much evidence to retain¶

By default, the basis keeps cofactor rows against the original generators. sparse.membership uses them to return a witness whose cofactors follow the original input order. It returns None for a nonmember. sparse.check_membership checks the identity without recomputing a basis.

sparse.check_groebner verifies both ideal containments and the Buchberger pair criterion using arithmetic and reduction. Its claim is the Gröbner property and equality with the original ideal; it does not separately certify reducedness or presentation order.

Cofactor rows can be much larger than the basis. Set witnesses=False if you only need normal forms or Boolean membership. Witness extraction and basis checking then raise DOMAIN; they do not silently recompute the basis.

Over rationals under grevlex without witnesses, the basis is reconstructed from modular images and then certified exactly, which is most of the work for large coefficients. certify=False skips the certificate: the result is still checked against one more modular image, so it is the reduced basis with high probability, but it is no longer proved.

An empty, typed generator iterable represents the zero ideal. Zero generators are allowed, and a basis copy shares the prepared storage. All input preparation, computation, and output wrapping use the same budget. An exhausted budget raises rather than reporting nonmembership.