Proofs: Buchberger's algorithm

Buchberger's algorithm stops and returns a Gröbner basis full

This proof shows: correctness, termination.

We use the notation of the page. $K$ is a field, $>$ is a monomial order on $K[x_1, \ldots, x_n]$, $F = (f_1, \ldots, f_s)$ and $I = \langle f_1, \ldots, f_s \rangle$. For $i \ne j$, $x^{\gamma_{ij}}$ is the lcm of $\operatorname{LM}(g_i)$ and $\operatorname{LM}(g_j)$. An lcm-representation of $S(g_i, g_j)$ by $G = (g_1, \ldots, g_t)$ is an equation $S(g_i, g_j) = \sum_{l=1}^t A_l g_l$ with $\operatorname{LM}(A_l g_l) < x^{\gamma_{ij}}$ whenever $A_l g_l \ne 0$. We use two facts.

• Division (D). Division of $p$ by a list $G$ stops and gives $p = \sum_l A_l g_l + h$, where no term of $h$ is divisible by any $\operatorname{LM}(g_l)$, and $\operatorname{LM}(A_l g_l) \le \operatorname{LM}(p)$ and $\operatorname{LM}(h) \le \operatorname{LM}(p)$ whenever these are nonzero. (See multivariate division.)
• Buchberger's criterion (BC). A finite set of nonzero generators of $I$ is a Gröbner basis of $I$ if each of its S-polynomials has an lcm-representation. The product criterion: if $\operatorname{LM}(g_i)$ and $\operatorname{LM}(g_j)$ are coprime, $S(g_i, g_j)$ has an lcm-representation by $\{g_i, g_j\}$. (Both are proved on the page Buchberger's criteria.)

Invariants. At each test of line L3:

(I1) Each $g_u$ is a nonzero element of $I$, and $\{g_1, \ldots, g_t\}$ generates $I$.

(I2) For each pair $1 \le i < j \le t$ that is not in $B$, $S(g_i, g_j)$ has an lcm-representation by $(g_1, \ldots, g_t)$.

Initialization. After lines L1 and L2, $G$ holds the nonzero $f_i$, which are in $I$ and generate $I$ (a zero generator adds nothing). Every pair $i < j \le t$ is in $B$, so (I2) holds with nothing to check.

Maintenance. Consider one round, with the pair $(i, j)$ removed at line L4. An lcm-representation by a list stays one when the list grows, since we may take $A_l = 0$ for new elements. So (I2) for old pairs not in $B$ stays true, and we only check the pair $(i, j)$ and the new pairs.

• If line L5 skips the pair, the product criterion gives an lcm-representation of $S(g_i, g_j)$ by $\{g_i, g_j\} \subseteq G$.
• Otherwise line L6 gives, by (D), $S(g_i, g_j) = \sum_l A_l g_l + h$ with $\operatorname{LM}(A_l g_l) \le \operatorname{LM}(S(g_i, g_j))$. The leading terms of the two parts of $S(g_i, g_j)$ cancel, so $S(g_i, g_j) = 0$ or $\operatorname{LM}(S(g_i, g_j)) < x^{\gamma_{ij}}$. If $h = 0$, the sum is an lcm-representation (if $S(g_i, g_j) = 0$ all $A_l$ are $0$ and the empty sum is one). If $h \ne 0$, line L8 appends $h$ as $g_t$, and $S(g_i, g_j) = \sum_l A_l g_l + 1 \cdot g_t$ is an lcm-representation, because $\operatorname{LM}(h) \le \operatorname{LM}(S(g_i, g_j)) < x^{\gamma_{ij}}$.
• For (I1): $h = S(g_i, g_j) - \sum_l A_l g_l$ is a combination of elements of $I$, so $h \in I$, and $h \ne 0$ when it is appended. Adding an element of $I$ to a generating set of $I$ keeps it a generating set.
• Line L9 puts each new pair $(u, t)$ into $B$, so (I2) does not speak about them.

Exit. When line L3 finds $B = \emptyset$, (I2) covers all pairs $i < j \le t$, and (I1) says that $G$ is a finite set of nonzero generators of $I$. By (BC), $G$ is a Gröbner basis of $I$. It contains the nonzero elements of $F$ by line L1, and line L10 returns it. If $F$ has no nonzero element, $G$ is empty, which is the Gröbner basis of $I = \{0\}$ by convention.

Termination. Let $J_t = \langle \operatorname{LM}(g_1), \ldots, \operatorname{LM}(g_t) \rangle$, a monomial ideal.

Step 1: each run of line L8 makes $J$ strictly larger. The new $h$ is a nonzero remainder, so by (D) no $\operatorname{LM}(g_u)$ with $u < t$ divides any term of $h$, in particular $\operatorname{LM}(h)$. A monomial lies in a monomial ideal exactly when one of the generating monomials divides it. So $\operatorname{LM}(h) \notin J_{t-1}$, and $J_{t-1} \subsetneq J_t$.

Step 2: line L8 runs finitely often. Suppose it ran infinitely often. Then $J_{t_0} \subsetneq J_{t_0 + 1} \subsetneq \cdots$ is an infinite strictly increasing chain of ideals of $K[x_1, \ldots, x_n]$. Its union $J$ is an ideal, and by the Hilbert basis theorem (or by Dickson's lemma for monomial ideals) it is generated by finitely many elements. Each of them lies in some $J_t$, so all of them lie in one $J_T$, and then $J = J_T = J_{T+1}$, a contradiction.

Step 3: the loop stops. Let $t^\ast$ be the final length of $G$, which exists by Step 2. Each round removes exactly one pair from $B$ at line L4, and pairs enter $B$ only at lines L2 and L9, with $j \le t^\ast$ each time and each pair at most once. So $B$ receives at most $\binom{t^\ast}{2}$ pairs in total, and the number of rounds is at most $\binom{t^\ast}{2}$. Each round stops, because division stops by (D). $\blacksquare$

Remark. The proof gives no bound on $t^\ast$, because the chain argument of Step 2 is not quantitative. This is why the complexity section gives only bounds for the problem.