Proofs: F5 algorithm

The signature-based F5 algorithm terminates and returns the reduced Gröbner basis full

This proof shows: correctness, termination.

Let $K$ be a field, $R = K[x_1, \ldots, x_n]$ with a monomial order $>$, and $f_1, \ldots, f_s \in R$. Let $R^s$ be the free module with basis $e_1, \ldots, e_s$ and $\alpha \mapsto \bar\alpha = \sum_i \alpha_i f_i$ the map onto $I = \langle f_1, \ldots, f_s \rangle$. Module monomials $u e_i$ are ordered position over term: $u e_i < v e_j$ if $i < j$, or $i = j$ and $u < v$. This is a well-order compatible with multiplication by monomials. For $\alpha \ne 0$ the signature $s(\alpha)$ is its largest module monomial.

A pair $(\sigma, p)$ is a labeled polynomial if $p = \bar\alpha$ for some $\alpha$ with $s(\alpha) = \sigma$. For a finite set $B$ of labeled polynomials, write $\operatorname{sig}(g) = \sigma$ for $(\sigma, g) \in B$. A standard s-representation of $\bar\alpha \ne 0$ is $\bar\alpha = \sum_k c_k t_k g_k$ with $g_k \in B$, monomials $t_k$, $t_k \operatorname{sig}(g_k) \le s(\alpha)$ and $\operatorname{LM}(t_k g_k) \le \operatorname{LM}(\bar\alpha)$. We say $B$ is a signature Gröbner basis below $\sigma$ if every $\alpha$ with $s(\alpha) < \sigma$ and $\bar\alpha \ne 0$ has one. A labeled $(\sigma, p)$ is regular top-reduced by $B$ if no $g \in B$ and monomial $t$ satisfy $t \operatorname{LM}(g) = \operatorname{LM}(p)$ and $t \operatorname{sig}(g) < \sigma$. A signature $\tau$ is a syzygy signature if $\tau = s(\gamma)$ for some $\gamma$ with $\bar\gamma = 0$; then every multiple $w\tau$ is one too.

Lemma 1 (labels are valid). Every queue entry and every element of $B$ is a labeled polynomial, and every element of Syz is a syzygy signature.

Proof. The entry $(e_i, f_i)$ comes from $\alpha = e_i$. For an S-pair of $(\sigma_r, r)$ and $(\sigma_g, g)$ with multipliers $u_r, u_g$ and $u_r \sigma_r \ne u_g \sigma_g$, the combination $(u_r/\operatorname{LC}(r))\alpha_r - (u_g/\operatorname{LC}(g))\alpha_g$ has signature $\max(u_r\sigma_r, u_g\sigma_g)$, which is the label used at line L9. A regular reduction step subtracts $c\, t\, g$ with $t \operatorname{sig}(g) < \sigma$, which does not change the signature of the module element. For $g \in B$ with $\operatorname{sig}(g)$ of index $j < i$, the element $\gamma = g\, e_i - f_i \alpha_g$ has $\bar\gamma = g f_i - f_i g = 0$ and $s(\gamma) = \operatorname{LM}(g) e_i$, since $f_i \alpha_g$ involves only indices at most $j$; these are the signatures added at line L4. A reduction to zero at line L7 gives a labeled $(\sigma, 0)$, hence a syzygy signature. $\square$

Lemma 2 (order of processing). The signatures handled at line L3 strictly increase, and when $\sigma$ is handled, every signature smaller than $\sigma$ that was ever put in the queue has already been handled.

Proof. A candidate created while handling $\sigma$ has signature at least $u_r \sigma \ge \sigma$. The smallest entry is taken each time, and an entry whose signature was already handled is skipped, so handled signatures strictly increase. $\square$

Lemma 3 (uniqueness of leading monomials). Let $B$ be a signature Gröbner basis below $\sigma$, and let $(\sigma, p)$ and $(\sigma, q)$ be labeled polynomials, both regular top-reduced by $B$. Then $p = 0$ if and only if $q = 0$, and otherwise $\operatorname{LM}(p) = \operatorname{LM}(q)$.

Proof. Take $\alpha, \beta$ with signature $\sigma$ and images $p, q$, and $c \in K$ with $s(\alpha - c\beta) < \sigma$. Suppose $p \ne 0$ and either $q = 0$ or $\operatorname{LM}(p) > \operatorname{LM}(q)$. Then $p - cq \ne 0$ with $\operatorname{LM}(p - cq) = \operatorname{LM}(p)$, and its standard s-representation contains a term $c_k t_k g_k$ with $\operatorname{LM}(t_k g_k) = \operatorname{LM}(p)$ and $t_k \operatorname{sig}(g_k) \le s(\alpha - c\beta) < \sigma$. So $p$ is not regular top-reduced, a contradiction. The case with $p$ and $q$ exchanged is the same. $\square$

Lemma 4 (completeness). Let $\sigma$ be a signature such that every candidate signature smaller than $\sigma$ has been handled, and let $B$ be the current basis. Then $B$ is a signature Gröbner basis below $\sigma$. The same holds with no bound on $\sigma$ when the queue is empty.

Proof. By induction on the signatures handled (assume the lemma at each earlier handled signature), and inside that by well-founded induction on $\tau = s(\alpha) < \sigma$. Let $\tau = u e_i$ and $\bar\alpha \ne 0$.

Case 1: $\tau$ is a syzygy signature, $\tau = s(\gamma)$ with $\bar\gamma = 0$. Then $\alpha - c\gamma$ has a smaller signature and the same image, and the inner induction gives a standard s-representation.

Case 2: otherwise. Then $e_i$ is not a syzygy signature either, so its candidate was not discarded at line L5 and did not reduce to zero; it was the first signature of index $i$, so it is not singular top-reducible, and $B$ contains an element of signature $e_i$. Hence some $g \in B$ has $\operatorname{sig}(g) \mid \tau$. Among all such $g$, with $t g$ of signature $\tau$, choose one with $\operatorname{LM}(t g)$ smallest. Choose $c$ with $s(\alpha - c\, t\, \alpha_g) < \tau$; by the inner induction its image $\bar\alpha - c\, t g$ is $0$ or has a standard s-representation. If $\operatorname{LM}(t g) \le \operatorname{LM}(\bar\alpha)$, adding $c\, t g$ gives a standard s-representation of $\bar\alpha$. Otherwise $\operatorname{LM}(\bar\alpha - c\, t g) = \operatorname{LM}(t g) =: m$, so there are $g' \in B$ and $t'$ with $t' \operatorname{LM}(g') = m$ and $t' \operatorname{sig}(g') < \tau$; here $g' \ne g$.

Let $\ell = \operatorname{lcm}(\operatorname{LM}(g), \operatorname{LM}(g'))$, $m = w \ell$, and $a = \ell / \operatorname{LM}(g)$, $b = \ell / \operatorname{LM}(g')$. Then $w a \operatorname{sig}(g) = \tau > w b \operatorname{sig}(g')$, so the S-pair of $g$ and $g'$ is regular with signature $\rho = a \operatorname{sig}(g)$, $w \rho = \tau$, and $\rho < \sigma$. It was put in the queue when the later of $g, g'$ was added (or skipped there because $\rho$ was handled), so by Lemma 2 the signature $\rho$ was handled, with some candidate $(\rho, p)$. Let $B_\rho$ be the basis at that time; by the outer induction it is a signature Gröbner basis below $\rho$. Let $S$ be the S-polynomial of $g, g'$, with $\operatorname{LM}(S) < \ell$ or $S = 0$, and $S'$ its regular top-reduction by $B_\rho$.

• If $\rho$ was discarded at line L5 or $p$ reduced to zero, $\rho$ is a syzygy signature by Lemma 1, and so is $\tau = w\rho$: excluded in Case 2.
• Otherwise $p$ reduced to $r \ne 0$, which is regular top-reduced by $B_\rho$. By Lemma 3, $S' \ne 0$ and $\operatorname{LM}(r) = \operatorname{LM}(S') \le \operatorname{LM}(S) < \ell$. If $r$ was added to $B$, then $w r$ has signature $\tau$ and $\operatorname{LM}(w r) < w \ell = m$. If $r$ was discarded at line L8, some $h \in B$ and $t_h$ have $t_h \operatorname{sig}(h) = \rho$ and $t_h \operatorname{LM}(h) = \operatorname{LM}(r)$, so $w t_h h$ has signature $\tau$ and leading monomial below $m$.

Both contradict the choice of $g$. So Case 2 always ends with a standard s-representation. When the queue is empty, every regular S-pair and every $e_i$ has been handled, and the same argument applies to all $\tau$. $\square$

Theorem. The algorithm terminates and returns the reduced Gröbner basis of $I$.

Proof. Termination. Each regular reduction terminates, because the leading monomial decreases in a well-order. Suppose infinitely many elements were added to $B$. Then infinitely many have the same index $i$. By Dickson's lemma applied to the monomials $(\operatorname{LM}(r), u_r)$ in $2n$ variables, where $\operatorname{sig}(r) = u_r e_i$, there are $r_k$ added before $r_l$ with $\operatorname{LM}(r_k) \mid \operatorname{LM}(r_l)$ and $u_k \mid u_l$. Put $t = \operatorname{LM}(r_l)/\operatorname{LM}(r_k)$ and $v = u_l/u_k$. Since $r_l$ is regular top-reduced and not singular top-reducible (line L8), $t u_k > u_l = v u_k$, so $t > v$. Then $v r_k$ is labeled with signature $\operatorname{sig}(r_l)$ and $\operatorname{LM}(v r_k) < \operatorname{LM}(r_l)$, and its regular top-reduction by the basis at the time of $r_l$ has a leading monomial below $\operatorname{LM}(r_l)$ or is zero. This contradicts Lemma 3, which applies by Lemma 4. So $B$ is finite, each element creates finitely many candidates, and the loop ends.

Correctness. By Lemma 1, $B \subseteq I$. When the queue is empty, Lemma 4 says that every nonzero $f = \bar\alpha \in I$ has a standard s-representation, so $\operatorname{LM}(f) = \operatorname{LM}(t g)$ for some $g \in B$, and $\operatorname{LM}(g) \mid \operatorname{LM}(f)$. So the polynomials of $B$ form a Gröbner basis of $I$, and line L10 turns it into the reduced Gröbner basis, which is unique (CLO Chapter 2, Section 7). $\blacksquare$