Advanced: Gröbner Basis Theory

Gröbner bases are the core tool of the theory of ideals in multivariate polynomial rings. This chapter starts from the basic definitions of monomial ideals and S-polynomials, systematically explains the theoretical foundations of Buchberger's algorithm, the F4 matrix method, and the F5 signature method, and describes how oCAS implements these algorithms in Rust.

Prerequisites

Before reading this chapter, we recommend familiarity with the following:

• Polynomial algebra: the multivariate polynomial ring $\mathbb{F}[x_1, \ldots, x_n]$, monomial orders (Lex / Grlex / Grevlex), multivariate division with remainder — see Polynomial Algebra
• Linear algebra: matrix operations, Gaussian elimination, row echelon form — see Linear Algebra
• Finite fields: construction and basic operations of $\mathbb{F}_p$ — see Finite Fields and Modular Arithmetic
• Ideals and quotient rings: basic notions of ideals $I \subseteq \mathbb{F}[x_1, \ldots, x_n]$ and quotient rings $R/I$

For a systematic learning path, see path A in the Mathematical Foundations Overview.

Basic Concepts

Monomial Ideals

Definition. Let $R = \mathbb{F}[x_1, \ldots, x_n]$. An ideal generated by monomials

$$M = \langle x^{\alpha^{(1)}}, x^{\alpha^{(2)}}, \ldots, x^{\alpha^{(s)}} \rangle$$

is called a monomial ideal. We have $f \in M$ if and only if the monomial of every nonzero term of $f$ is divisible by some $x^{\alpha^{(i)}}$.

Example. $M = \langle x^2, xy \rangle \subseteq \mathbb{F}[x, y]$. The terms of $f = x^2 y + x y^2$: $x^2 y$ is divisible by $x^2$, and $xy^2$ is divisible by $xy$, so $f \in M$. But the monomial $y^3$ of $g = y^3$ is divisible by neither $x^2$ nor $xy$, so $g \notin M$.

Dickson's Lemma

Lemma (Dickson). Every subset $S$ of $\mathbb{N}^n$ has a finite set $M \subseteq S$ of minimal elements such that for every $\alpha \in S$ there exists $\beta \in M$ with $\beta \leq \alpha$ (componentwise comparison).

Equivalent formulation: every monomial ideal in $\mathbb{F}[x_1, \ldots, x_n]$ is generated by finitely many monomials.

Proof sketch (induction on $n$).

• $n = 1$: every nonempty subset of $\mathbb{N}$ has a least element; take it as $M$.
• $n \to n+1$: for $S \subseteq \mathbb{N}^{n+1}$, consider the sections $S_a = {(\alpha_2, \ldots, \alpha_{n+1}) : (a, \alpha_2, \ldots, \alpha_{n+1}) \in S}$ for each $a \in \mathbb{N}$. By the induction hypothesis each $S_a$ has finitely many minimal elements. Further analyzing the elements "dominated by smaller first components" allows the construction of a finite minimal set for $S$.

Significance: Dickson's lemma guarantees the finite generation of monomial ideals, which directly implies the Hilbert basis theorem — every polynomial ideal is finitely generated. Gröbner basis theory builds a systematic method for "finding suitable generators" on this foundation.

S-polynomials

Definition. Let $f, g \in R$ be nonzero polynomials. Let $\gamma = \text{lcm}(\text{lm}(f), \text{lm}(g))$ — the componentwise maximum of the exponent vectors. The S-polynomial of $f$ and $g$ is

$$S(f, g) = \frac{x^\gamma}{\text{lt}(f)} \cdot f - \frac{x^\gamma}{\text{lt}(g)} \cdot g = \frac{x^\gamma}{\text{lm}(f)} \cdot f - \frac{x^\gamma}{\text{lm}(g)} \cdot g$$

The key property of the S-polynomial is that its leading term is canceled. Intuitively, $S(f,g)$ measures the "inconsistency" of $f$ and $g$ beyond their leading terms. When the leading monomials of $f$ and $g$ are coprime (i.e. $\text{lcm} = \text{lm}(f) \cdot \text{lm}(g)$), $S(f,g)$ can usually be reduced directly to zero — this is Buchberger's first optimization criterion.

Example. In $\mathbb{F}[x, y]$, take $f = x^2 - y$ and $g = xy - 1$ (Grevlex order).

$$\gamma = \text{lcm}(x^2, xy) = x^2 y$$

$$S(f, g) = \frac{x^2 y}{x^2} \cdot (x^2 - y) - \frac{x^2 y}{xy} \cdot (xy - 1) = y(x^2 - y) - x(xy - 1) = -y^2 + x$$

Definition of a Gröbner Basis

Definition. Fix a monomial order $\succ$. A generating set ${g_1, \ldots, g_t}$ of an ideal $I$ is called a Gröbner basis of $I$ with respect to $\succ$ if

$$\langle \text{lt}(g_1), \ldots, \text{lt}(g_t) \rangle = \langle \text{lt}(f) : f \in I \rangle$$

i.e. the ideal generated by the leading terms of the generators equals exactly the ideal generated by the leading terms of all polynomials in $I$ (the leading term ideal $L(I)$ of $I$).

Equivalent characterization (Buchberger's criterion). ${g_1, \ldots, g_t}$ is a Gröbner basis of $I$ if and only if for every pair $i \neq j$, the remainder of $S(g_i, g_j)$ on division by ${g_1, \ldots, g_t}$ is zero.

The core value of Gröbner bases:

1. Membership testing: $f \in I$ if and only if the remainder of $f$ on division by the Gröbner basis is zero (uniqueness of the normal form)
2. Equality testing of ideals: two ideals satisfy $I = J$ if and only if their (reduced) Gröbner bases coincide
3. Elimination: a Gröbner basis under the Lex order naturally has the elimination property (generators of the elimination ideal appear in the basis)
4. Structure of the quotient ring: a $k$-vector space basis of $R/I$ is given by the monomials not divisible by any leading monomial of the ideal (the staircase)

Reduced Gröbner bases. A Gröbner basis ${g_1, \ldots, g_t}$ is reduced if:

1. each $g_i$ is monic ($\text{lc}(g_i) = 1$)
2. for $i \neq j$, no nonzero term of $g_i$ is divisible by $\text{lm}(g_j)$

The reduced Gröbner basis is unique (for a fixed order and field). All of oCAS's algorithms output reduced Gröbner bases.

Core Theory

Buchberger's Algorithm

Buchberger's algorithm (1965) is the classical method for computing Gröbner bases. Its idea is simple and direct: repeatedly construct S-polynomials and reduce them until all S-polynomials reduce to zero.

Input: F = {f1, ..., fs} (generators of the ideal)
Output: G (Gröbner basis)

G ← F
P ← {(fi, fj) | i < j}  // initial set of critical pairs
while P ≠ ∅:
    take a pair (f, g) from P
    h ← NF(S(f, g), G)   // remainder of the S-polynomial on division by G
    if h ≠ 0:
        P ← P ∪ {(h, g') | g' ∈ G}  // add new critical pairs
        G ← G ∪ {h}
return G

Termination: guaranteed by Buchberger's criterion — each new element strictly enlarges the leading term ideal, and the Hilbert basis theorem guarantees the chain terminates. In practice the implementation also needs minimize (removing redundant elements) and auto_reduce (mutual reduction) to obtain the reduced basis.

Efficiency issues: the main bottlenecks of the naive Buchberger algorithm are —

1. Number of critical pairs: $O(|G|^2)$ critical pairs, most of which are redundant
2. One at a time: only one S-polynomial is reduced per step; no batching is exploited
3. Repeated scanning: finding a reducer requires a linear scan of the whole basis

The following three sections introduce the methods that address these problems: Gebauer–Moeller filtering (Buchberger speedup), F4 (batching), and F5 (avoiding reductions to zero).

Buchberger's Criteria and Optimizations

Buchberger's two criteria can drastically reduce the number of critical pairs that must be processed.

First criterion (coprime leading monomials). If $\text{lm}(f_i)$ and $\text{lm}(f_j)$ are coprime (i.e. $\gcd = 1$), then

$$S(f_i, f_j) \xrightarrow{G} 0$$

i.e. this S-polynomial reduces directly to zero, and the critical pair can be removed from the set.

Proof: let $\text{lm}(f_i) = m_i$ and $\text{lm}(f_j) = m_j$ with $\gcd(m_i, m_j) = 1$. Then $\text{lcm}(m_i, m_j) = m_i m_j$ and $S(f_i, f_j) = m_j f_i - m_i f_j$. When reducing term by term, every nonzero term $c \cdot x^\alpha$ satisfies that $x^\alpha$ is divisible by either $m_i$ or $m_j$, so it can be reduced by the corresponding $f_i$ or $f_j$; the final remainder is zero. $\square$

Second criterion (chain criterion / generalization of Buchberger's criterion). Let $f_k \in G$. If $\text{lm}(f_k)$ divides $\text{lcm}(\text{lm}(f_i), \text{lm}(f_j))$, and both $\text{lcm}(\text{lm}(f_i), \text{lm}(f_k))$ and $\text{lcm}(\text{lm}(f_j), \text{lm}(f_k))$ strictly divide $\text{lcm}(\text{lm}(f_i), \text{lm}(f_j))$, then

$$S(f_i, f_j) \xrightarrow{G} 0$$

and the critical pair $(f_i, f_j)$ need not be processed.

Redundant pairs: more generally, if the $\text{lcm}$ of a critical pair $(f_i, f_j)$ is divisible by the $\text{lcm}$ of another existing critical pair, then $(f_i, f_j)$ is redundant — processing the other pair already subsumes this one.

Gebauer–Moeller Critical Pair Management

Gebauer and Moeller (1988) systematized Buchberger's criteria into an efficient framework for managing critical pairs. When a new polynomial $f_{\text{new}}$ is added to the basis $G = {f_1, \ldots, f_m}$:

1. Generate candidate pairs: $P_{\text{new}} = {(f_{\text{new}}, f_i) \mid 1 \leq i \leq m}$
2. First-criterion filtering: delete the pairs where $\text{lm}(f_{\text{new}})$ and $\text{lm}(f_i)$ are coprime
3. Second-criterion filtering: delete the pairs whose $\text{lcm}$ is divided by the $\text{lcm}$ of another (still live) pair (divisibility includes equality; duplicate pairs are dropped)
4. Redundant pair cleanup: mark old pairs whose $\text{lcm}$ is divisible by the $\text{lcm}$ of a new pair as redundant
5. Merge: merge the filtered $P_{\text{new}}$ into the main critical pair set

Key optimization: sort the critical pairs by the size of their $\text{lcm}$ (compared with the monomial order) and process the small ones first — this makes the larger pairs more likely to be filtered out by the second criterion.

The F4 Algorithm: Batched Matrix Row Echelon

The core idea of the F4 algorithm (Faugère 1999) is: batch the reduction of many S-polynomials into a single sparse-matrix row-echelon computation.

Symbolic Preprocessing

F4 does not divide S-polynomials directly; instead it first performs symbolic preprocessing: for the selected set of critical pairs, find all the reducers needed (monomial multiples of basis elements), expand their nonzero terms, and map them to column indices.

Concrete steps:

1. Select critical pairs: take a batch of critical pairs from the queue (sorted by $\text{lcm}$)
2. Collect monomials: for each selected critical pair, compute the monomials appearing in the S-polynomial; for each monomial that needs reduction, find a reducer in the basis and expand it multiplied by the corresponding monomial
3. Build the column map: order all monomials that occur and number them $0, 1, \ldots, N-1$
4. Construct the matrix: each row corresponds to a polynomial (an S-polynomial or a multiple of a reducer), each column to a monomial, and the matrix entries are coefficients

This produces a sparse matrix $M$ in which the nonzero entries of each row correspond to the nonzero terms of a polynomial.

Row Echelon Computation

Perform Gaussian elimination (row echelonization) on the matrix $M$:

1. Sort the rows by their first nonzero column
2. Eliminate column by column: find a row whose first nonzero entry is in the current column to serve as the pivot, and eliminate that column in the remaining rows
3. Among the rows after elimination, the polynomials corresponding to the nonzero rows are the new basis elements

ℤ_p native fast path. When the coefficient domain is the finite field $\mathbb{F}_p$ ($p < 2^{31}$), all matrix operations use i64 modular arithmetic — no BigInt overhead. This includes:

• the sparse row subtraction sub_scaled_fp: merge two rows in ascending column order, skip the first column (already eliminated), compute $(row_j - c \cdot pivot_j) \bmod p$ term by term, and drop zero entries
• the modular inverse lookup mod_inv: extended Euclid
• the modular reduction norm_mod: keep coefficients in $[0, p)$

Extracting New Basis Elements

After elimination, every nonzero row $r$ of the matrix corresponds to a polynomial $h_r$. For $h_r$:

1. if the leading term of $h_r$ is "new" (not in the set of leading terms collected so far), add it to the basis
2. further simplify with tail reduction: reduce the tail terms of $h_r$ using the existing basis elements

Complexity of F4

The main cost of F4 is the row-echelon computation — for a matrix with $m$ rows and $N$ columns, Gaussian elimination requires $O(m \cdot N \cdot \text{nnz_per_row})$ field operations. In practice the matrices are sparse ($\text{nnz_per_row} \ll N$), and since Gebauer–Moeller filtering reduces the number of critical pairs, F4 is one to two orders of magnitude faster than the naive Buchberger algorithm.

The F5 Algorithm: Signature-Based Gröbner Bases

The revolutionary contribution of the F5 algorithm (Faugère 2002) is that it identifies and rejects S-polynomials that would reduce to zero before the matrix is even constructed. This is achieved by attaching a signature to every polynomial.

Signatures and Module Representations

The ideal generation problem is turned into a module element problem. Let $I = \langle f_1, \ldots, f_s \rangle$ and consider the standard basis $e_1, \ldots, e_s$ of the free module $R^s$. Every polynomial $h = \sum q_i f_i$ corresponds to a module element

$$\vec{h} = (q_1, \ldots, q_s) = \sum q_i e_i$$

The signature of $h$ is defined as the "highest" monomial multiple in the module element:

$$\text{sig}(h) = \max_\succ {x^{\alpha_i} e_i : q_i \neq 0}$$

where the comparison uses the pot (position-over-term) order: first compare the module positions (the indices $i$ of the $e_i$; a smaller index gives a smaller signature, processed earlier), then the monomials. That is, $x^\alpha e_i \succ x^\beta e_j$ if and only if $i > j$, or $i = j$ and $\alpha \succ \beta$.

Intuition: the signature records the "origin" of the polynomial $h$ — which multiple ($x^\alpha$) of which generator ($f_i$) it was derived from. The signature of a polynomial is the minimal representation of its derivation history.

The F5 Criterion

Signature criterion. If the signature of a candidate S-polynomial is a monomial multiple of some known syzygy, then this S-polynomial necessarily reduces to zero — it can be rejected directly, without entering the matrix.

Meaning of a syzygy: when a row of the matrix reduces to zero, the corresponding polynomial satisfies $h = 0$, but its module representation is $(q_1, \ldots, q_s) \neq 0$. This yields a syzygy (relation) $\sum q_i f_i = 0$. The signature $\text{sig}(h)$ of that row records this syzygy.

The SyzygySet data structure: for each module position $k$, maintain the set of leading monomials of the known syzygies. To test whether a signature $(k, t)$ is a syzygy, check whether some stored leading monomial of a $k$-position syzygy divides $t$.

Regular Sequences and Complete Avoidance of Reductions to Zero

Theorem (Faugère 2002). If the input generators $f_1, \ldots, f_s$ form a regular sequence, then the F5 signature criterion suffices to reject all reductions to zero — i.e. no row of the matrix ever reduces to zero.

Definition of a regular sequence: $f_1, \ldots, f_s$ form a regular sequence if $f_1$ is not a zero divisor and, for $i > 1$, $f_i$ is not a zero divisor in $R/\langle f_1, \ldots, f_{i-1} \rangle$.

In practice, even when the generators do not form a regular sequence, the F5 signature criterion still filters out a large number of reductions to zero. In the literature, F5 achieves order-of-magnitude speedups over F4 on hard benchmark ideals (the oCAS F5 implementation is still being optimized).

Matrix Construction in F5

F5's matrix construction is similar to F4's, but every row additionally carries signature information:

1. Incremental processing: add the generators $f_1, f_2, \ldots, f_s$ one at a time
2. Labeled S-polynomials: every S-polynomial enters the matrix carrying its signature
3. Symbolic preprocessing: the same as in F4, but the signatures of reducers must also propagate — when reducing with a multiple $x^\delta g$ of a basis element $g$, the new row's signature is $x^\delta \cdot \text{sig}(g)$
4. Syzygy updates: the signature of a row that reduces to zero is added to the SyzygySet

Labeled rows: each row in the matrix is stored as (Signature, Vec<(coefficient, column)>) — a pairing of the signature with the sparse row data. During row-echelon computation the signature is preserved (row operations are linear combinations of rows, and the signature of the result is the maximum of the signatures of the participating rows).

Complexity Advantages of F5

In theory, the F5 signature criterion guarantees:

• for regular sequences: no zero rows in the matrix, so the matrix size is minimized
• for general ideals: a large reduction in zero rows, saving row-echelon cost

In practice the main bottlenecks are signature comparison and SyzygySet lookups. The oCAS implementation optimizes these operations with SmallVec and HashMap.

Equivalence of Monomial Orders and Change of Ordering

Different computational tasks require different monomial orders:

The standard strategy is "compute fast, then convert":

1. Compute the basis with Grevlex (fastest — the intermediate polynomials have the lowest degrees)
2. Convert to Lex (needed for elimination and solving)

Two conversion methods:

Method 1: recomputation (reorder). Reinterpret the polynomials of the Grevlex basis under the Lex order, then rerun F4 under Lex. For general ideals this is the default method — the basis elements may need additional reduction under the new order.

Method 2: FGLM (for zero-dimensional ideals only). The FGLM algorithm (detailed in the next subsection) performs the change of ordering for zero-dimensional ideals in $O(n \cdot D^3)$, far faster than recomputation.

The FGLM Algorithm

FGLM (Faugère–Gianni–Lazard–Mora 1993) provides an efficient change-of-ordering algorithm for zero-dimensional ideals.

Prerequisite: the ideal $I$ is zero-dimensional, i.e. $R/I$ is finite-dimensional as a $k$-vector space.

The Staircase and Normal Forms

Staircase: the set of monomials not divisible by any leading monomial $\text{lm}(g_i)$. For a zero-dimensional ideal the staircase is finite, of size $D = \dim_k(R/I)$.

The monomials of the staircase form a $k$-vector space basis of $R/I$. The normal form $f \bmod I$ of any polynomial $f$ can be represented uniquely as a $k$-linear combination of staircase monomials.

Algorithm Idea

FGLM enumerates monomials in increasing target order, computes their normal forms, and detects linear relations:

Input: GB_src (reduced Gröbner basis in the source order)
Output: GB_tgt (reduced Gröbner basis in the target order)

S ← {1}                    // processed monomials (in the staircase)
B ← {x1, x2, ..., xn}     // the border: "neighbors" of the processed monomials
GB_tgt ← ∅
seen_nf ← {}               // normal forms already seen

for m in increasing target order:
    nf ← normal_form(m, GB_src)  // compute the normal form under the source-order basis
    if nf ∈ span(seen_nf):        // linearly dependent?
        coeffs ← find_relation(seen_nf, nf)
        new_poly ← m - Σ coeffs_i · m_i
        GB_tgt ← GB_tgt ∪ {new_poly}
    else:
        S ← S ∪ {m}
        seen_nf ← seen_nf ∪ {nf}
        B ← B ∪ {m · xi : i = 1..n}  // expand the border
    if |S| = D:                     // the staircase is full
        break
return minimize(GB_tgt)

Key properties:

• every linear dependence produces one polynomial of the target-order basis
• every linear independence step extends the staircase, until its size reaches $D$
• the total number of operations is $O(n \cdot D^3)$ — $D$ normal-form computations (each $O(D^2)$), plus $D$ Gaussian eliminations (each $O(D^2)$)

The non-zero-dimensional case: when the staircase is infinite, FGLM cannot terminate — fglm returns None, and reorder must be used instead.

Hilbert Functions and Regularity

The Hilbert function is a powerful tool for describing the structure of graded rings; in Gröbner basis computation it provides early-termination bounds.

Hilbert Functions and Hilbert Series

Definition. Let $I \subseteq R = \mathbb{F}[x_1, \ldots, x_n]$ be a homogeneous ideal. The Hilbert function

$$H_{R/I}(d) = \dim_\mathbb{F} (R/I)_d$$

measures the vector-space dimension of the degree-$d$ homogeneous component of the quotient ring.

The Hilbert series is the generating function of the Hilbert function:

$$\text{HS}{R/I}(t) = \sum{d=0}^{\infty} H_{R/I}(d) \cdot t^d$$

Theorem (Macaulay). The Hilbert series of $R/I$ depends only on the leading term ideal $\langle \text{lm}(g) : g \in \text{GB}(I) \rangle$, i.e.

$$\text{HS}{R/I}(t) = \text{HS}{R/\langle\text{LM}(I)\rangle}(t)$$

This means we can compute the Hilbert series from the leading terms of the Gröbner basis alone, without knowing any other information about the ideal.

Hilbert Series of Monomial Ideals

For an ideal $M$ generated by monomials $m_1, \ldots, m_s$, the inclusion–exclusion principle gives:

$$\text{HS}_{R/M}(t) = \frac{N(t)}{(1-t)^n}$$

where the numerator $N(t)$ is

$$N(t) = \sum_{k=0}^{s} (-1)^k \sum_{\substack{S \subseteq {1,\ldots,s} \ |S| = k}} t^{\deg \text{lcm}(S)}$$

Here $\text{lcm}(\emptyset) = 1$ (degree 0) and $\text{lcm}({m_i}) = m_i$.

Expansion:

$$N(t) = 1 - \sum_{i} t^{\deg m_i} + \sum_{i < j} t^{\deg \text{lcm}(m_i, m_j)} - \sum_{i < j < k} t^{\deg \text{lcm}(m_i, m_j, m_k)} + \cdots$$

Example. $M = \langle x^2, xy \rangle \subseteq \mathbb{F}[x, y]$ ($n = 2$).

• $|S| = 0$: $t^0 = 1$
• $|S| = 1$: $-t^2 - t^2 = -2t^2$ ($\deg(x^2) = \deg(xy) = 2$)
• $|S| = 2$: $+t^{\deg \text{lcm}(x^2, xy)} = +t^{\deg(x^2 y)} = +t^3$

$$N(t) = 1 - 2t^2 + t^3$$

$$\text{HS}_{R/M}(t) = \frac{1 - 2t^2 + t^3}{(1-t)^2}$$

Regularity and Early Termination

Regularity is defined as the degree of the highest-degree nonzero term of the Hilbert numerator $N(t)$:

$$\text{reg}(M) = \max{d : [t^d] N(t) \neq 0}$$

Theorem (Bayer–Stillman). For a zero-dimensional ideal, the degrees of all polynomials in the Gröbner basis do not exceed $\text{reg}(M)$.

This means F4 can safely ignore critical pairs whose degree exceeds the regularity bound — they necessarily reduce to zero. The hilbert module of oCAS computes this bound via regularity_bound and uses it as an early-termination hint for F4 (an advisory bound; it does not affect correctness).

Complete Hilbert Series

The Hilbert series can also be computed for Gröbner bases of general (non-homogeneous) ideals:

$$\text{HS}_{R/I}(t) = \frac{N(t)}{(1-t)^n}$$

where $N(t)$ is given by the inclusion–exclusion formula for the leading term ideal. oCAS provides the HilbertSeries struct, supporting:

• hilbert_function(d): $\dim_k (R/I)_d$ (by expanding the coefficient of $t^d$ in $\frac{N(t)}{(1-t)^n}$)
• dimension(): when $N(1) \neq 0$ the dimension is $n - \text{ord}_{t=1}(N(t))$, i.e. the order of vanishing of $(1-t)$
• degree(): the degree of the projective variety equals $h(1)$, where $h(t) = N(t)/(1-t)^{n-\dim}$ is the numerator after removing the factor $(1-t)^{n-\dim}$; for zero-dimensional ideals ($\dim = 0$) this equals $\dim_k(R/I)$ (the number of points)
• hilbert_polynomial(): for sufficiently large $d$, $H_{R/I}(d)$ is a polynomial in $d$, computed by Lagrange interpolation

Implementation in oCAS

oCAS implements the three Gröbner basis algorithms and the Hilbert series computation in ocas-poly/src/groebner/. The unified entry point groebner_basis(ideal, Algorithm::Auto) currently routes to F4 by default.

f4.rs: The F4 Matrix Row-Echelon Algorithm

Gebauer–Moeller Critical Pair Management

The update_pairs function performs Gebauer–Moeller filtering each time a new polynomial is added to the basis:

1. Generate candidates: pair the new polynomial with every existing element of the basis
2. First criterion (monomial_are_coprime): if the leading monomials are coprime, skip directly (the product criterion)
3. Second criterion (chain criterion, sequential elimination): if the $\text{lcm}$ of another (still live) candidate pair divides the current pair's $\text{lcm}$ (divisibility includes equality; duplicate pairs are dropped), the current pair is redundant and not kept
4. Update criterion (for old pairs): an old pair is removed only when the new leading monomial divides its $\text{lcm}$ and both $\text{lcm}(i, \text{new})$ and $\text{lcm}(j, \text{new})$ are strictly smaller than $\text{lcm}(i,j)$; equality must be kept (otherwise S-polynomials required for completeness would be dropped)

The CriticalPair struct precomputes the $\text{lcm}$ and the monomial differences (the information needed to construct S-polynomials), avoiding repeated computation in later steps.

DivisorIndex: O(1)-ish Reducer Lookup

The core operation of symbolic preprocessing is "find the element of the basis whose leading monomial divides a given monomial". A naive implementation requires a linear scan costing $O(\text{monomials} \times |\text{basis}|)$. oCAS accelerates this operation with a support bitmask index.

support_mask: for an exponent vector $\alpha = (\alpha_1, \ldots, \alpha_n)$, define the bitmask

$$\text{mask}(\alpha) = \sum_{v : \alpha_v > 0} 2^v$$

i.e. bit $v$ is set if and only if the variable $x_v$ occurs in the monomial (variable indices up to 63).

Key observation: if $\text{lm}(g)$ divides $x^\alpha$, then $\text{support}(\text{lm}(g)) \subseteq \text{support}(x^\alpha)$. Hence a query only needs to enumerate the submasks of $\text{mask}(x^\alpha)$ and inspect the basis elements in the corresponding buckets.

The DivisorIndex structure:

#![allow(unused)]
fn main() {
struct DivisorIndex {
    // support_mask → list of basis element indices having this mask
    buckets: HashMap<u64, Vec<usize>>,
}
}

The query find_reducer(index, basis, exp):

1. compute $m = \text{mask}(\text{exp})$
2. enumerate all submasks $s \subseteq m$ of $m$
3. for each basis element $g$ in buckets[s], check exactly whether $\text{lm}(g) \mid x^\text{exp}$
4. among all reducers satisfying the condition, choose the one with the fewest terms (to speed up reduction)

Enumerating submasks costs $O(3^v)$ ($v$ = the number of variables), but in practice $v$ is usually small ($\leq 10$) and the buckets contain very few elements.

SimpCache: A Cache for Multiples of Reducers

During symbolic preprocessing, the same basis element may be used to reduce several different monomials with different differences. SimpCache<P> caches the computed polynomial multiples:

#![allow(unused)]
fn main() {
type SimpCache<P> = Vec<(SmallVec<[usize; 4]>, P)>;
}

get_simplified(cache, diff, basis_poly) checks the cache first and returns the cached value on a hit; otherwise it computes $x^{\text{diff}} \cdot \text{basis_poly}$ and stores it in the cache. The cache persists across rounds.

The ℤ_p Native Fast Path

When the coefficient domain is FiniteField(p) ($p < 2^{31}$), F4 uses FpPoly instead of the generic polynomial type:

#![allow(unused)]
fn main() {
struct FpPoly {
    terms: Vec<(i64, SmallVec<[usize; 4]>)>,  // (coeff, exponent)
    // coeff ∈ [0, p), sorted in descending order
}
}

All matrix operations run on i64 — no BigInt overhead. sub_scaled_fp implements O(nnz) sparse row subtraction with a two-pointer merge:

#![allow(unused)]
fn main() {
fn sub_scaled_fp(
    row: &mut Vec<(i64, usize)>,     // ascending column order
    pivot: &[(i64, usize)],           // ascending column order
    c: i64,                           // multiplier
    p: i64,                           // modulus
    scratch: &mut Vec<(i64, usize)>,  // scratch buffer
) {
    // two-pointer merge: row -= c * pivot
    // the first column (pivot column) is eliminated automatically (c = row[head_col] / pivot[head_col])
    // all results taken mod p; zero coefficients dropped
}
}

register_row_fp additionally caches the FpPoly representations of S-polynomials and reducer multiples for reuse across rounds.

The Matrix Elimination Flow

The complete F4 flow:

1. Select critical pairs: take pairs from the queue sorted by $\text{lcm}$ size
2. Symbolic preprocessing: expand the S-polynomial of each pair and all reducers, and build the column map
3. Row echelonization: echelonize_fp (ℤ_p fast path) or echelonize_generic (generic)
4. Extract new elements: convert the nonzero rows back to polynomials and check whether the leading term is "new"
5. Update basis and pairs: add the new elements to the basis, and let update_pairs update the critical pair queue

f5.rs: The F5 Signature Algorithm

The Signature Structure

#![allow(unused)]
fn main() {
struct Signature {
    module_pos: usize,              // generator index k
    monomial: SmallVec<[usize; 4]>, // monomial exponents
}
}

Signatures are compared with the pot (position-over-term) order: first compare module_pos (smaller first), then compare monomial with the monomial order O.

LabeledPoly: Basis Elements with Signatures

#![allow(unused)]
fn main() {
struct LabeledPoly<D: Domain, O: MonomialOrder> {
    poly: SparseMultivariatePolynomial<D, O>,
    sig: Signature,
}
}

Every basis element carries a signature. When reducing with a multiple $x^\delta g$ of $g$, the signature of the new polynomial is $x^\delta \cdot \text{sig}(g)$.

SyzygySet: Tracking Reductions to Zero

#![allow(unused)]
fn main() {
struct SyzygySet {
    // module_pos → list of leading monomials of the known syzygies at that position
    lms: HashMap<usize, Vec<SmallVec<[usize; 4]>>>,
}
}

insert(sig): when a matrix row reduces to zero, its signature $(k, t)$ is recorded — $t$ is stored in lms[k].

contains(sig): test a signature $(k, t)$ — if there exists $s$ in lms[k] with $s \mid t$, it is a syzygy. monomial_divides(t, s) performs the componentwise comparison ($t_i \geq s_i$ for all $i$).

Matrix Construction and Elimination

The build_and_reduce flow of F5:

1. Select pairs: critical pair selection similar to F4 (shares the update_pairs implementation)
2. Syzygy filtering: before a pair enters the matrix, check its signature — if it is a syzygy, skip it
3. Labeled rows: each row carries (Signature, Vec<(coefficient, column)>)
4. Symbolic preprocessing: the same column-map construction as in F4, but the signatures of reducers must propagate
5. Row echelonization: sort the rows in ascending signature order and run Gaussian elimination
6. Extract new elements: nonzero rows are extracted as LabeledPoly, keeping their signatures
7. Syzygy updates: the signatures of zero rows are added to SyzygySet

The ℤ_p Fast Path

F5 reuses F4's infrastructure — FpPoly, CriticalPair, update_pairs — and adds signature labels via LabeledFpPoly and LabeledFpRow. The structure of f5_fp is completely symmetric to the generic f5 — only the polynomial representation switches from a generic domain to i64 modular arithmetic.

hilbert.rs: Hilbert Series Computation

Implementing Inclusion–Exclusion

hilbert_numerator(generators) computes the Hilbert numerator of the monomial ideal $\langle m_1, \ldots, m_s \rangle$:

#![allow(unused)]
fn main() {
pub fn hilbert_numerator(generators: &[Vec<usize>]) -> Vec<(usize, i64)> {
    // iterate over all subsets S ⊆ {0, ..., s-1}
    // |S| = k contributes (-1)^k · t^{deg lcm(S)}
    // returns a sparse representation as (degree, coefficient) pairs
}
}

All $2^s$ subsets are enumerated (practical limit around $s \leq 20$); for each subset the degree of the $\text{lcm}$ is computed (componentwise maximum, then summed) and accumulated with its sign at the corresponding degree.

The Regularity Bound

regularity_bound(generators) returns the degree of the highest-degree nonzero term of the Hilbert numerator:

$$\text{reg} = \max{d : [t^d] N(t) \neq 0}$$

F4 uses this bound as an early-termination hint — when selecting critical pairs, a pair with $\deg(\text{lcm}) > \text{reg}$ can be safely skipped. This does not affect correctness (only efficiency) and is only valid for zero-dimensional ideals.

Complete Hilbert Series

hilbert_series(gb) computes the complete Hilbert series $\frac{N(t)}{(1-t)^n}$ of $R/I$ from a Gröbner basis:

1. Extract leading terms: take the leading exponent vector of each polynomial in the basis
2. Inclusion–exclusion: call hilbert_numerator to obtain $N(t)$
3. Expand the series: $\frac{N(t)}{(1-t)^n} = N(t) \cdot \sum_{k \geq 0} \binom{n+k-1}{k} t^k$

Methods of the HilbertSeries struct:

binomial_general(n, k) computes the generalized binomial coefficient $\binom{n+k-1}{k}$ ($n$ may be negative or zero), used to expand $(1-t)^{-n}$.

fglm.rs: The Zero-Dimensional Change-of-Ordering Algorithm

Computing the Staircase

compute_staircase(lms, n_vars) enumerates the monomials not divisible by any leading monomial:

1. start a BFS at $1 = x_1^0 \cdots x_n^0$
2. for each monomial $m$, check whether it is divisible by some $\text{lm}(g_i)$
3. monomials that are not divisible are added to the staircase, and all their "neighbors" ($m \cdot x_i$) enter the queue
4. if the staircase has not stopped growing after exceeding a threshold, return None (positive-dimensional ideal)

Computing Normal Forms

normal_form_monomial(m, gb, staircase, domain) computes the normal form of a monomial $m$ under the source-order basis, represented as a $k$-vector in staircase coordinates:

$$m \bmod I = \sum_{i=1}^{D} c_i \cdot s_i$$

where $s_1, \ldots, s_D$ are the staircase monomials. The computation is the standard multivariate division algorithm.

Detecting Linear Dependences

find_relation(seen, nf, domain) tests whether the new normal form nf lies in the span of the normal forms already seen. It uses incremental Gaussian elimination: maintain a matrix in row-echelon form and try to reduce each new vector — if it reduces to zero, a relation has been found.

Border Management

mark_multiples(visited, m, n_vars, max_deg) marks all multiples of a monomial $m$ (up to total degree max_deg) as visited, avoiding duplicate insertion into the border. It uses recursive enumeration.

The Unified Entry Point and Algorithm Selection

#![allow(unused)]
fn main() {
pub fn groebner_basis<D: Domain + 'static, O: MonomialOrder>(
    ideal: &[SparseMultivariatePolynomial<D, O>],
    algo: Algorithm,
) -> GroebnerBasis<D, O>
}

The Algorithm enum:

All paths ultimately output a reduced Gröbner basis: first minimize (remove redundant elements whose leading terms are divisible by the leading term of another element), then auto_reduce (mutually reduce the tail terms).

Advanced Topics

Practical Performance: F4 vs Buchberger

oCAS's benchmarks (ocas-tests/benches/groebner.rs) compare Buchberger and F4 on the cyclic-n ideals:

F5's signature criterion can in principle avoid reductions to zero and has the potential for order-of-magnitude speedups on hard ideals, but the oCAS F5 implementation is recent and has no official benchmark data yet.

Practical advice: use Algorithm::Auto (currently = F4) for general ideals; for systems known to be regular sequences, explicitly specifying Algorithm::F5 may be faster.

Theoretical Guarantees of F5

Theorem. The F5 algorithm is "optimal" in the following sense:

1. No redundant reductions: for regular sequences, no row of the matrix reduces to zero
2. Completeness: it produces exactly the same reduced Gröbner basis as F4
3. Signature uniqueness: the signature of each polynomial uniquely determines its origin

These guarantees make F5 the theoretical first choice for hard ideals, although in practice F4's simpler implementation is often faster on small and medium problems.

Applications of the Hilbert Series

The Hilbert series is not merely a theoretical tool; it has the following practical applications in oCAS:

1. Early termination: the regularity bound $\text{reg}(M)$ provides a reliable degree bound for F4
2. Dimension testing: the Krull dimension of $R/I$ equals the order of the pole of $\text{HS}(t)$ at $t=1$
3. Degree computation: the degree of the projective variety equals $N(1)$ (for zero-dimensional ideals, the staircase size)
4. Zero-dimensionality test: $N(1) \neq 0$ if and only if the ideal is zero-dimensional

Gröbner Bases in Computational Algebraic Geometry

Gröbner bases are the universal tool of computational algebraic geometry. In oCAS they support the following applications (see FGLM and Elimination Theory and Gröbner Basis Implementation for details):

• Solving polynomial systems: Gröbner basis → elimination → univariate equation → root isolation
• Ideal operations: membership testing, sum, product, quotient, saturation, intersection, elimination, radical, primary decomposition
• Geometric properties of varieties: dimension, degree, irreducible components

References

1. Cox, D., Little, J. & O'Shea, D. Ideals, Varieties, and Algorithms. 4th ed., Springer, 2015.

   • Chapter 2: definition of Gröbner bases, Buchberger's algorithm, Buchberger's criteria
   • Chapter 3: the elimination theorem and ideal operations
   • Chapter 8: FGLM and change of ordering

2. Adams, W.W. & Loustaunau, P. An Introduction to Gröbner Bases. AMS, 1994.

   • Chapters 4–5: detailed analysis of Buchberger's algorithm, Gebauer–Moeller optimizations

3. Faugère, J.-C. "A New Efficient Algorithm for Computing Gröbner Bases (F4)." Journal of Pure and Applied Algebra, 139(1–3):61–88, 1999.

   • The original F4 paper: batched matrix row echelon

4. Faugère, J.-C. "A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F5)." ISSAC 2002, pp. 75–83.

   • The original F5 paper: the signature criterion and regular sequences

5. Faugère, J.-C., Gianni, P., Lazard, D. & Mora, T. "Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering." Journal of Symbolic Computation, 16(4):329–344, 1993.

   • The original FGLM paper

6. Gebauer, R. & Möller, H.M. "On an Installation of Buchberger's Algorithm." Journal of Symbolic Computation, 6(2–3):275–286, 1988.

   • The Gebauer–Moeller critical pair filtering criteria

7. Eder, C. & Perry, J. "Signature-based Algorithms to Compute Gröbner Bases." ISSAC 2009, pp. 139–146.

   • Eder–Perry's formalization of F5

8. Bayer, D. & Stillman, M. "A Criterion for Detecting m-Regularity." Inventiones Mathematicae, 87(1):1–11, 1987.

   • The relation between regularity bounds and Hilbert functions

9. Gathen, J. von zur & Gerhard, J. Modern Computer Algebra. 3rd ed., Cambridge University Press, 2013.

   • Chapter 21: a comprehensive survey of Gröbner bases

See also:

• Polynomial Algebra — monomial orders, the foundations of the multivariate division algorithm
• Linear Algebra — the Bareiss algorithm and Gaussian elimination
• FGLM and Elimination Theory — detailed analysis of FGLM and ideal operations
• Gröbner Basis Implementation — usage guide, benchmarks, and the ideal operations API
• Rust API: Gröbner Bases and Ideals — function signatures and complete examples