GroebnerBasis

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

GroebnerBasis[{p1, p2, ...}, {x1, x2, ...}]

gives a list of polynomials that form a Gröbner basis for the ideal generated by the pi over Q[x1, x2, ...].

GroebnerBasis[{p1, ...}, {x1, ...}, {y1, ...}]

eliminates the yi and returns a Gröbner basis of the elimination ideal in {x1, ...}.

TimeConstrained[GroebnerBasis[...], t] aborts cleanly via the

cooperative deadline hook. Lex order can be exponentially slow on systems with 3+ variables; switch to MonomialOrder -> DegreeReverseLexicographic for hard inputs.

Notes

Free symbols in pi that are not in vars (and not a known constant like Pi, E, EulerGamma, ...) are auto-promoted to coefficient-ring parameters and survive in the basis polynomials. Options: MonomialOrder -\> Lexicographic (default) | DegreeReverseLexicographic | EliminationOrder | a weight matrix {{...}, ...} of integers (one column per variable, defining a custom term order); CoefficientDomain -\> Rationals (default); Method -\> "Buchberger" (default) | "GroebnerWalk"; Sort -\> True reverses the main-variable list; ParameterVariables -\> p or {p1, ...} marks parameters explicitly (the main-variable list is then optional and is auto-derived from the polys). Other settings emit GroebnerBasis::nimpl and fall back; Modulus emits GroebnerBasis::modnotimpl and falls back to the rational basis. Polynomial equations (Equal\[a, b\]) are accepted in place of polynomials; each is rewritten as a - b before computation.

Examples (14)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (6)

In[1]:= GroebnerBasis[{x^2 - 2 y^2, x y - 3}, {x, y}]
Out[1]= {-9 + 2 y^4, 3 x - 2 y^3}

In[2]:= GroebnerBasis[{x + y, x^2 - 1, y^2 - 2 x}, {x, y}]
Out[2]= {1}

In[3]:= GroebnerBasis[{(x-1)(x-2), (x-2)(x-3)}, x]
Out[3]= {-2 + x}

In[4]:= GroebnerBasis[{x + 2 y + 3 z, 4 x + 5 y + 6 z, 7 x + 8 y + 9 z}, {x, y, z}]
Out[4]= {y + 2 z, x - z}

In[5]:= GroebnerBasis[{x^2 - 2 y^2 == 1, x y == 3}, {x, y}]
Out[5]= {-9 + y^2 + 2 y^4, 3 x - y - 2 y^3}

In[6]:= TimeConstrained[GroebnerBasis[hard_polys, {x, y, z}], 3]
Out[6]= GroebnerBasis[hard_polys, {x, y, z}]

Options (4)

In[7]:= GroebnerBasis[polys, ParameterVariables -> x]
Out[7]= GroebnerBasis[polys, ParameterVariables -> x]

In[8]:= GroebnerBasis[polys, {x, y, z}, Sort -> True] === GroebnerBasis[polys, {z, y, x}]
Out[8]= False

In[9]:= GroebnerBasis[{-5x^2 + y z - x - 1, 2x + 3 x y + y^2, x - 3y + x z - 2 z^2}, {x, y, z}, MonomialOrder -> {{1, 3, 1}, {-1, 2, 0}, {4, -3, 2}}]
Out[9]= {-21 x - 13 x^2 - 15 x^3 + 6 z + 6 x z + 20 x^2 z + 20 x z^2, 60 + 39 x + 287 x^2 - 15 x^3 + 6 z - 14 x z + 20 x^2 z + 40 z^3, -x + 3 y - x z + 2 z^2, 10 - 38 x + 141 x^2 - 305 x^3 + 325 x^4 - 12 z - 82 x z - 50 x^2 z + 20 z^2, 30 + 913 x + 189 x^2 + 4545 x^3 + 42 z + 1132 x z + 630 x^2 z + 1950 x^3 z - 200 z^2}

In[10]:= GroebnerBasis[polys, {x, y, z}, Method -> "GroebnerWalk"] === GroebnerBasis[polys, {x, y, z}]
Out[10]= False

Applications (4)

In[11]:= GroebnerBasis[{x^2 + y^2 - 1, x - y}, {x, y}]
Out[11]= {-1 + 2 y^2, x - y}

In[12]:= GroebnerBasis[{x y - 1, x - y}, {x, y}]
Out[12]= {-1 + y^2, x - y}

In[13]:= GroebnerBasis[{x^2 - y, x^3 - z}, {x, y, z}]
Out[13]= {y^3 - z^2, -y^2 + x z, x y - z, x^2 - y}

In[14]:= GroebnerBasis[{x + y + z, x y + y z + z x, x y z - 1}, {x, y, z}]
Out[14]= {-1 + z^3, y^2 + y z + z^2, x + y + z}

Options & behaviour

Options

Option	Default	Supported
MonomialOrder	Lexicographic	Lexicographic, DegreeReverseLexicographic, EliminationOrder, or an integer weight matrix {{...}, ...} (one column per variable) defining a custom term order
CoefficientDomain	Rationals	Rationals, Automatic, Integers (strong Gröbner basis over Z), RationalFunctions (basis over the field Q(params)), Polynomials[x, ...] (named symbols become coefficient-ring parameters), InexactNumbers[p] (monic basis with p-digit real coefficients)
Method	Automatic	"Buchberger", "GroebnerWalk", Automatic
Sort	False	True reverses the main-variable list before the basis is computed (matching Mathematica's empirical behaviour).
ParameterVariables	(unset)	Symbol or list of symbols treated as coefficient-ring parameters; with no positional vars argument the main-variable list is auto-derived from the polynomials.
Modulus	0	Modulus -> p with prime p in [2, 2^31) computes the basis over the finite field GF(p) (src/poly/gbmod.c, Lexicographic / DegreeReverseLexicographic). A non-prime p, an out-of-range p, or a coefficient with no image in GF(p) falls back to the rational basis with a one-shot note. Not combined with elimination or RationalFunctions parameters in this version.

A weight-matrix MonomialOrder must be a rectangular list of integer rows with exactly one column per main variable, and must define a valid term order: full column rank (so distinct monomials never tie) and a positive first non-zero entry in every column (so each variable exceeds 1, making the order well-founded). Matrices that fail either condition, or that are used together with elimination/parameter variables, emit GroebnerBasis::nimpl and fall back to Lexicographic.

Settings outside this table emit a GroebnerBasis::nimpl diagnostic to stderr and fall back to the default. Deferred (not implemented in this release):

• MonomialOrder -> DegreeLexicographic.
• Modulus -> n (modular Gröbner bases): emits a GroebnerBasis::modnotimpl diagnostic and falls back to the rational basis.

CoefficientDomain -> Integers computes a strong Gröbner basis over the ring Z (any parameter symbol is treated as an ordinary variable of the polynomial ring Z[vars]). Because the leading coefficients are not units, the strong basis generally carries more generators than the rational basis — completion forms, per pair, both the S-polynomial (coefficient lcm) and a Bézout G-polynomial (coefficient gcd), and reduction cancels a term only when the divisor's leading coefficient divides it. Polynomial content is preserved (it is ideal data over Z), so a constant generator c denotes the ideal c·Z[x] rather than {1}.

CoefficientDomain -> Polynomials[x, ...] makes the named symbols coefficient-ring variables (equivalent to listing them in ParameterVariables). CoefficientDomain -> InexactNumbers[p] computes the exact basis, makes each polynomial monic, and renders coefficients as p-digit machine/MPFR reals; inexact (Real) input coefficients are rationalised before the computation. This is exact-compute-then-round, not a genuine floating-point Buchberger run.

CoefficientDomain -> RationalFunctions computes the basis over the field Q(params), where the parameters (the non-main symbols) are units. The ring basis over Q[params][main vars] is autoreduced — generators whose main leading monomial is a multiple of another's are dropped — yielding the (typically smaller) field basis; coefficients are kept as primitive integer polynomials in the parameters. Honoured in the plain form only (no elimination block) and equivalent to Rationals when there are no parameters.

Algorithm

groebnerbasis.c

`GroebnerBasis[polys, vars]` and `GroebnerBasis[polys, mainVars,

elimVars]` -- the user-facing entry point that drives the Buchberger

core in groebner.c.  See SPEC.md and docs/spec/builtins/arithmetic-

and-algebra.md for the surface this implements.

Supported options (others emit GroebnerBasis::nimpl):

  MonomialOrder      -> Lexicographic            (default)
                      | DegreeReverseLexicographic
                      | EliminationOrder         (forced by the 3-arg form)
  CoefficientDomain  -> Rationals | Automatic    (default)
  Method             -> "Buchberger" | Automatic (default)

Performance

Against other systems, from the benchmark suite (same input, results cross-checked for agreement):

case	Mathilda	Wolfram	Python
GroebnerBasis cyclic-5	43.5 s	18 s	8.78e+03 s
GroebnerBasis cyclic-4	0.223 s	0.355 s	0.997 s
Resultant of two deg-8 polys	0.076 s	0.748 s	0.696 s
GroebnerBasis 3-var quadratic system	0.048 s	0.223 s	0.34 s
GroebnerBasis cyclic-3	0.041 s	0.071 s	0.175 s
Eliminate 2 vars from 3	0.007 s	0.028 s	0.303 s

Implementation notes

Algorithm. builtin_groebner_basis (in src/poly/groebnerbasis.c) is the front end; the engine is in groebner.c and the order conversion in groebnerwalk.c. The front end parses GroebnerBasis[polys, vars] (and the 3-arg elimination form GroebnerBasis[polys, mainVars, elimVars]), reads the MonomialOrder (Lexicographic default, DegreeReverseLexicographic, or EliminationOrder — forced by the 3-arg form), CoefficientDomain and Method options, converts each polynomial to the internal GBPoly via gb_from_expr, runs the core, and renders the basis back to expressions.

The core gb_buchberger is textbook Buchberger with Gebauer–Möller pair management: each new basis element is folded in with gm_update, which applies Buchberger criterion 1 (coprime leading monomials) and the Gebauer–Möller M/F/B criteria to discard provably useless pairs without re-walking exponents. The main loop picks the next pair by the normal strategy (gm_pick_pair), forms the S-polynomial (gb_spoly, using the pointwise-max lcm of the two leading exponent vectors), fully reduces it against the current basis (gb_reduce, multivariate division to a normal form), and adds any non-zero remainder (made monic). After saturation, gb_finalize_basis inter-reduces and normalises to the unique reduced Gröbner basis. A tc_check_deadline hook lets TimeConstrained abort between pairs.

For expensive target orders the front end can route through the Gröbner walk (gb_groebner_walk, the Collart–Kalkbrener–Mall algorithm): compute the basis under the cheap DegreeReverseLexicographic order, then walk along the weight path w(t) = (1−t)·(1,…,1) + t·σ across the Gröbner fan, rewriting through initial-form ideals at each cone wall, with a guaranteed fall-back to a direct gb_buchberger run under the target order on any overflow or degenerate lift.

Data structures. GBPoly holds rational coefficients as a parallel array of GMP mpq_t alongside a row-major int* exps (n_terms × n_vars) exponent matrix, with a borrowed GBWeightMatrix defining the order and an elim_pivot for elimination blocks. Pairs are GMPair records carrying a precomputed lcm and a dead flag.

Complexity / limits. Buchberger's algorithm is doubly-exponential in the worst case; lexicographic bases especially can blow up, which is why grevlex-then-walk is offered. Arithmetic is exact (mpq_t/mpz-guarded int64 weights). Unsupported option values emit a GroebnerBasis::nimpl diagnostic.

• Protected.
• Computes the reduced Gröbner basis under the requested monomial order via Buchberger's algorithm. Pair selection uses the normal strategy (smallest LCM total degree first); pair pruning uses Buchberger's coprime-LMs criterion together with Gebauer-Möller's M / F / B chain criteria. Each basis polynomial is returned in primitive-over-Z form with positive leading coefficient and the basis is sorted ascending by leading monomial — matching Mathematica's output convention.
• Polynomial equations (Equal[a, b]) are accepted in place of polynomials; each is rewritten as a - b and Expanded before conversion.
• The single-variable shorthand GroebnerBasis[polys, x] is accepted as a synonym for GroebnerBasis[polys, {x}].
• Parameters: any free symbol that appears in the polynomials but is not in the explicit vars, the elimination block, or the ParameterVariables list — and is not a known mathematical constant (Pi, E, EulerGamma, Catalan, Degree, Infinity, True, False, ...) — is automatically promoted to a parameter and appended to the joint variable array in last-priority lex position. This is the conventional "Gröbner basis over Z[params][main_vars]" form; consistency constraints on the parameter values themselves (purely- parameter polynomials) are kept in the output.
• Cooperative abort: the Buchberger loop calls tc_check_deadline() once per S-pair iteration so TimeConstrained[GroebnerBasis[...], t] aborts cleanly when the budget expires (returns $Aborted).
• Performance note: pure-lex Gröbner-basis computation is subject to exponential coefficient blowup on many systems with three or more variables; if GroebnerBasis[polys, vars] is slow, switching to MonomialOrder -> DegreeReverseLexicographic is often dramatically faster. Method -> "GroebnerWalk" computes a cheap grevlex basis and then converts it to the requested order along the Gröbner fan; for hard lex (or weight-matrix) targets this is usually much faster than direct Buchberger while returning the identical reduced basis.

Attributes: Protected.

References

See also: Expand, Pi, E, EulerGamma, Catalan, Degree, Sort, Modulus

• Cox, Little & O'Shea, "Ideals, Varieties, and Algorithms" (Springer) — Buchberger's algorithm, monomial orders, and elimination.
• von zur Gathen & Gerhard, "Modern Computer Algebra" (3rd ed.), Ch. 21 (Gröbner bases).
• B. Buchberger, "An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal" (PhD thesis, 1965).
• R. Gebauer, H. M. Möller, "On an installation of Buchberger's algorithm", J. Symbolic Computation 1988.
• S. Collart, M. Kalkbrener, D. Mall, "Converting bases with the Gröbner walk", J. Symbolic Computation 1997.
• T. Becker, V. Weispfenning, Gröbner Bases (Springer, 1993).
• Source: src/poly/groebnerbasis.c
• Specification: docs/spec/builtins/structural-manipulation.md
• Tests: tests/test_groebner.c

Notes & additional examples

Notes

GroebnerBasis[polys, vars] computes a Gröbner basis of the ideal under the default Lexicographic monomial order via Buchberger's algorithm. The lex order triangularizes the system: in the circle-meets-line example the basis isolates -1 + 2 y^2 (a univariate consequence in the last variable) plus the linear relation. The symmetric-functions system reduces to z^3 = 1, exposing the roots of unity, while the implicitization example returns the full reduced basis describing the twisted cubic. Set MonomialOrder -> DegreeReverseLexicographic for systems with three or more variables, where lex order can be exponentially slow; a third argument selects elimination variables, and Equal equations are accepted in place of bare polynomials.