S-polynomial of polynomials with relatively prime leading terms

Question

I've read in a bunch of texts that the S-polynomial of two polynomials with relatively prime leading terms always reduces to zero, i.e. the remainder of the division of $S(f,g)$ by a set of polynomials containing $f$ and $g$ is zero.

Can someone give me a hint about the proof? I've read in an answer to this post that whenever $\gcd(\mathrm{LT}(f),\mathrm{LT}(g))=1$ we can write $S(f,g)=-(g-\mathrm{LT}(g))f+(f-\mathrm{LT}(f))g$, but I don't know why this should help: why can we say that that form of $S(f,g)$ as a polynomial combination of $f$ and $g$ comes from a division? I know that not all the expressions of a polynomial $f\in k[x_1,\dots, x_n]$ as $f=p_1q_1+\cdots+p_sq_s+r$ come from a division of $f$ by $\{q_1,\dots, q_s\}$...

Answer 1

This is as in the reference that you propose related to improvements in Buchberger's algorithm. In the case of Cox's Ideals, Varieties and Algorithms the relevant sections to understand of the proof I want to share are Proposition 4 of section 2.9 and Exercise 11 from section 2.3.

The idea goes as follows:

Define $\exp(F)$ as the exponent of the leading term of polynomial $F$ and $N(F)$ as the set of exponents of the monomials of the distributive form of $F$. For our polynomials write $\alpha = \exp(F),\beta = \exp(G)$.

In our conditions $\gcd(x^{\alpha},x^{\beta}) = 1$ so $\operatorname{lcm}(x^{\alpha},x^{\beta}) = x^{\alpha+\beta}$. Write also $F = X^{\alpha}+F'$, $G = X^{\beta}+G'$ where we are assuming for simplicity (as Cox does) that $F,G$ are monic. Then we express the $S$-poynomial as:

$$S(F,G) = X^{\alpha+\beta-\alpha}F-X^{\alpha+\beta-\beta}G = X^{\beta}F - X^{\alpha}G = X^{\alpha+\beta}+X^{\beta}F'-X^{\alpha+\beta}-X^{\alpha}G' = X^{\beta}F'-X^{\alpha}G' = X^{\beta}F'-X^{\alpha}G'+F'G'-F'G' = F'(G'+X^{\beta})-G'(X^{\alpha}+F') = F'G-G'F = Q_1F+Q_2G.$$

We are still not happy with this expression since the precise meaning of $R(S(F,G),\{F,G\}) = 0$ requires that the computed remainder is unique. So if you revisit exercise 11 above you'll see that you need to check two further conditions:

$\exp(F)+N(Q_1) \subseteq \Delta^1 = \exp(F)+\mathbb{N}^n$

$\exp(G)+N(Q_2) \subseteq \Delta^2 = \exp(G)+\mathbb{N}^n \setminus \Delta^1$

The second is the "difficult" one; by contradiction:

Suppose $\gamma \in N(Q_2)$ such that $\beta+\gamma \in \Delta^1$ then $\beta +\gamma = \alpha + \delta$ with $\delta \in \mathbb{N}^n$. I can define a $\lambda \in \mathbb{N}^n$ such that $\gamma = \alpha + \lambda$, but this gives you a contradiction since $\exp(F') > \exp(F) = \alpha$ and with the previous expression we would have $\gamma > \alpha$ where $\gamma \in N(F')$.

The precise $\lambda$ is $\lambda_i = \gamma_i$ if $\beta_i > 0$ (because in this case $\alpha_i = 0$ since $\gcd(x^{\alpha},x^{\beta}) = 1$), and $\lambda_i = \delta_i$ if $\beta_i = 0$.

I think this is easier than the one in Adams once you grasp the notation and have the necessary background specially regarding the precise formulation of division algorithm with unique remainder and quotients.

Answer 2

Most of the following answer is copypasted from Section 3.2 of Darij Grinberg, t-unique reductions for Mészàros's subdivision algebra, arXiv:1704.00839v4, where I found myself forced to introduce Gröbner bases because all the standard texts only considered the case of a field. (I have changed the notations, though.)

Let $\mathbf{k}$ be a commutative ring with unity. Let $\Xi$ be a set of indeterminates. Let $\mathcal{X}$ be the polynomial ring $\mathbf{k}\left[ \xi\ \mid\ \xi\in\Xi\right] $ over $\mathbf{k}$ in these indeterminates. Let $\mathbf{M}$ be the set of all monomials in these indeterminates (i.e., the free abelian monoid on the set $\Xi$). Notice that my monomials don't contain coefficients.

For example, if $\Xi$ is an $n$-element set $\left\{x_1, x_2, \ldots, x_n\right\}$, then $\mathcal{X}$ is the standard polynomial ring $\mathbf{k}\left[x_1, x_2, \ldots, x_n\right]$ in $n$ indeterminates, and $\mathbf{M}$ is the set of all monomials in these indeterminates.

Definition. A term order on $\mathbf{M}$ is a total order on the set $\mathbf{M}$ that satisfies the following conditions:

• Each $\mathbf{m}\in\mathbf{M}$ satisfies $1\leq\mathbf{m}$ (where $1$ is the trivial monomial in $\mathbf{M}$).

• If $\mathbf{m}$, $\mathbf{u}$ and $\mathbf{v}$ are three elements of $\mathbf{M}$ satisfying $\mathbf{u}\leq\mathbf{v}$, then $\mathbf{mu} \leq\mathbf{mv}$.

For example, if $\Xi$ is an $n$-element set $\left\{x_1, x_2, \ldots, x_n\right\}$, then there are several well-known term orders on $\mathbf{M}$; here are the most important two:

• The lexicographic order is the total order on $\mathbf{M}$ in which two monomials $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ and $x_1^{b_1} x_2^{b_2} \cdots x_n^{b_n}$ satisfy $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} \leq x_1^{b_1} x_2^{b_2} \cdots x_n^{b_n}$ if and only if some $i \in \left\{1,2,\ldots,n\right\}$ satisfies $a_i < b_i$ and ($a_j = b_j$ for all $j < i$).

• The graded lexicographic order is the total order on $\mathbf{M}$ in which two monomials $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ and $x_1^{b_1} x_2^{b_2} \cdots x_n^{b_n}$ satisfy $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} \leq x_1^{b_1} x_2^{b_2} \cdots x_n^{b_n}$ if and only if either $a_1 + a_2 + \cdots + a_n < b_1 + b_2 + \cdots + b_n$ or ($a_1 + a_2 + \cdots + a_n = b_1 + b_2 + \cdots + b_n$, and some $i \in \left\{1,2,\ldots,n\right\}$ satisfies $a_i < b_i$ and ($a_j = b_j$ for all $j < i$)).

It is well-known that every monomial order is a well-order. (I am not sure if this is true in constructive mathematics; but even then, the lexicographic order and the graded lexicographic order are well-orders in the constructive sense of this word, i.e., we can perform strong induction on a monomial $\mathbf{m} \in \mathbf{M}$ along these orders.)

Definition. Two monomials $\mathbf{m}=\prod_{\xi\in\Xi}\xi^{m_{\xi}}$ and $\mathbf{n}=\prod_{\xi\in\Xi}\xi^{n_{\xi}}$ in $\mathbf{M}$ are said to be non-disjoint if there exists some $\xi\in\Xi$ satisfying $m_{\xi}>0$ and $n_{\xi}>0$. Otherwise, $\mathbf{m}$ and $\mathbf{n}$ are said to be disjoint.

In your notation, two monomials $\mathbf{m}$ and $\mathbf{n}$ are disjoint if and only if $\gcd\left( \mathbf{m},\mathbf{n}\right) =1$.

For example, if $\Xi$ is an $n$-element set $\left\{x_1, x_2, \ldots, x_n\right\}$, then the monomials $x_2 x_4^2$ and $x_3$ are disjoint, whereas the monomials $x_2 x_4^2$ and $x_2^2 x_3$ are non-disjoint.

Definition. If $\mathbf{m}=\prod_{\xi\in\Xi}\xi^{m_{\xi}}$ and $\mathbf{n}=\prod_{\xi\in\Xi}\xi^{n_{\xi}}$ are two monomials in $\mathbf{M}$, then the lowest common multiple $\operatorname{lcm} \left( \mathbf{m},\mathbf{n}\right) $ of $\mathbf{m}$ and $\mathbf{n}$ is defined to be the monomial $\prod_{\xi\in\Xi}\xi ^{\max\left\{ m_{\xi},n_{\xi}\right\} }$.

Thus, two monomials $\mathbf{m}$ and $\mathbf{n}$ are disjoint if and only if they satisfy $\operatorname{lcm}\left( \mathbf{m},\mathbf{n}\right) =\mathbf{mn}$.

It is easy to prove the following universal property of the lowest common multiple: If $\mathbf{m}$, $\mathbf{n}$ and $\mathbf{p}$ are three monomials in $\mathbf{M}$ such that $\mathbf{p}$ is a multiple of $\mathbf{m}$ and of $\mathbf{n}$ at the same time, then $\mathbf{p}$ is a multiple of $\operatorname{lcm}\left( \mathbf{m},\mathbf{n}\right) $. Conversely, if $\mathbf{p}$ is a multiple of $\operatorname{lcm}\left( \mathbf{m},\mathbf{n}\right) $, then $\mathbf{p}$ is a multiple of $\mathbf{m}$ and of $\mathbf{n}$ at the same time.

For example, if $\Xi$ is an $n$-element set $\left\{x_1, x_2, \ldots, x_n\right\}$, then $\operatorname{lcm}\left( x_2 x_4^2 , x_3\right) = x_2 x_3 x_4^2$ and $\operatorname{lcm}\left( x_2 x_4^2 , x_2^2 x_3\right) = x_2^2 x_3 x_4^2$.

From now on, let us assume that some term order on $\mathbf{M}$ has been chosen. The next definitions will all rely on this term order.

Definition. If $f\in\mathcal{X}$ is a nonzero polynomial, then the head term of $f$ denotes the largest $\mathbf{m}\in\mathbf{M}$ such that the coefficient of $\mathbf{m}$ in $f$ is nonzero. This head term will be denoted by $\operatorname*{HT}\left( f\right) $.

What I call the "head term" is what you call the "leading term".

For example, if $\Xi$ is an $n$-element set $\left\{x_1, x_2, \ldots, x_n\right\}$, and if we use the lexicographic order, then the head term of $5 x_2^2 x_3 - x_2 x_3^4 + x_3 + x_7 + 4$ is $x_2^2 x_3$. But if we use the graded lexicographic order instead, then the head term is $x_2 x_3^4$ instead.

Definition. A nonzero polynomial $f\in\mathcal{X}$ is said to be monic if the coefficient of $\operatorname*{HT}\left( f\right) $ in $f$ is $1$.

Definition. If $g_{1}$ and $g_{2}$ are two monic polynomials in $\mathcal{X}$, then the S-polynomial of $g_{1}$ and $g_{2}$ is defined to be the polynomial $\mathbf{s}_{1}g_{1}-\mathbf{s}_{2}g_{2}$, where $\mathbf{s}_{1}$ and $\mathbf{s}_{2}$ are the unique two monomials satisfying $\mathbf{s}_{1}\operatorname*{HT}\left( g_{1}\right) =\mathbf{s}_{2}\operatorname*{HT}\left( g_{2}\right) =\operatorname{lcm} \left( \operatorname*{HT}\left( g_{1}\right) ,\operatorname*{HT}\left( g_{2}\right) \right) $. This S-polynomial is denoted by $\operatorname*{spol}\left( g_{1},g_{2}\right) $.

For example, if $\Xi$ is a $n$-element set $\left\{x_1, x_2, \ldots, x_n\right\}$, and if we use the lexicographic order, then $\operatorname{spol}\left(x_1^2 x_2 - x_1, x_1 x_2^2 - x_2\right) = x_2 \left(x_1^2 x_2 - x_1\right) - x_1 \left(x_1 x_2^2 - x_2\right) = 0$ and $\operatorname{spol}\left(x_1^2 x_2 - x_2, x_1 x_2^2 - x_1\right) = x_2 \left(x_1^2 x_2 - x_2\right) - x_1 \left(x_1 x_2^2 - x_1\right) = x_1^2 - x_2^2$.

From now on, let $G$ be a subset of $\mathcal{X}$ that consists of monic polynomials.

Definition. We define a binary relation $\underset{G}{\longrightarrow}$ on the set $\mathcal{X}$ as follows: For two polynomials $f$ and $g$ in $\mathcal{X}$, we set $f\underset{G}{\longrightarrow}g$ (and say that $f$ reduces to $g$ modulo $G$) if there exists some $p\in G$ and some monomials $\mathbf{t}\in\mathbf{M}$ and $\mathbf{s}\in\mathbf{M}$ with the following properties:

• The coefficient of $\mathbf{t}$ in $f$ is $\neq0$.

• We have $\mathbf{s}\cdot\operatorname*{HT}\left( p\right) =\mathbf{t}$.

• If $a$ is the coefficient of $\mathbf{t}$ in $f$, then $g=f-a\cdot \mathbf{s}\cdot p$.

We let $\overset{\ast}{\underset{G}{\longrightarrow}}$ denote the reflexive-and-transitive closure of the relation $\underset{G}{\longrightarrow}$.

For example, if $\Xi$ is a $n$-element set $\left\{x_1, x_2, \ldots, x_n\right\}$, and if we use the lexicographic order, and if $G = \left\{ x_1^2 x_2 - x_2, x_1 x_2^2 - x_1 \right\}$, then $x_1^3 + x_1^2 x_2^2 \underset{G}{\longrightarrow} x_1^3 + x_2^2$ (because for $f = x_1^3 + x_1^2 x_2^2$ and $g = x_1^3 + x_2^2$ and $a = 1$ and $p = x_1^2 x_2 - x_2 \in G$ and $\mathbf{t} = x_1^2 x_2^2 \in \mathbf{M}$ and $\mathbf{s} = x_2 \in \mathbf{M}$, the three properties in the definition of $\underset{G}{\longrightarrow}$ are satisfied).

Now, we claim the following:

Lemma 1. Let $S$ be a finite set. For each $s\in S$, let $g_{s}$ be an element of $G$, and let $\mathbf{s}_{s}\in\mathbf{M}$ and $a_{s} \in\mathbf{k}$ be arbitrary. Assume that the monomials $\mathbf{s} _{s}\operatorname*{HT}\left( g_{s}\right) $ for all $s\in S$ are distinct. Then, $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}\overset{\ast }{\underset{G}{\longrightarrow}}0$.

Proof of Lemma 1. We proceed by strong induction on $\left\vert S\right\vert $. If $\left\vert S\right\vert =0$, then Lemma 1 is obvious (because in this case, we have $\sum_{s\in S}a_{s}\mathbf{s}_s g_{s}=\left( \text{empty sum}\right) =0\overset{\ast}{\underset{G}{\longrightarrow}}0$). Hence, WLOG assume that $\left\vert S\right\vert >0$.

Let $t$ be the element of $S$ with highest $\mathbf{s}_{t}\operatorname*{HT} \left( g_{t}\right) $. Then, $t$ is the unique element of $S$ with highest $\mathbf{s}_{t}\operatorname*{HT}\left( g_{t}\right) $ (since the monomials $\mathbf{s}_{s}\operatorname*{HT}\left( g_{s}\right) $ for all $s\in S$ are distinct). By the induction hypothesis, we have $\sum_{s\in S\setminus\left\{ t\right\} }a_{s}\mathbf{s}_{s}g_{s}\overset{\ast }{\underset{G}{\longrightarrow}}0$ (since $\left\vert S\setminus\left\{ t\right\} \right\vert <\left\vert S\right\vert $). If $a_{t}=0$, then this immediately rewrites as $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s} \overset{\ast}{\underset{G}{\longrightarrow}}0$, and so we are done. Hence, WLOG assume that $a_{t}\neq0$. Hence, the head term of $\sum_{s\in S} a_{s}\mathbf{s}_{s}g_{s}$ is $\mathbf{s}_{t}\operatorname*{HT}\left( g_{t}\right) $, with coefficient $a_{t}$ (since $t$ is the unique element of $S$ with highest $\mathbf{s}_{t}\operatorname*{HT}\left( g_{t}\right) $). Thus, we know that:

• The coefficient of $\mathbf{s}_{t}\operatorname*{HT}\left( g_{t}\right) $ is $\neq0$ (since $a_{t}\neq0$).

• We have $\mathbf{s}_{t}\cdot\operatorname*{HT}\left( g_{t}\right) =\mathbf{s}_{t}\operatorname*{HT}\left( g_{t}\right) $.

• If $a$ is the coefficient of $\mathbf{s}_{t}\operatorname*{HT}\left( g_{t}\right) $ in $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}$, then $\sum_{s\in S\setminus\left\{ t\right\} }a_{s}\mathbf{s}_{s}g_{s}=\sum_{s\in S} a_{s}\mathbf{s}_{s}g_{s}-a\cdot\mathbf{s}_{t}\cdot g_{t}$ (because this $a$ is $a_{t}$).

Hence, the definition of the relation $\underset{G}{\longrightarrow}$ yields $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}\underset{G}{\longrightarrow} \sum_{s\in S\setminus\left\{ t\right\} }a_{s}\mathbf{s}_{s}g_{s}$. Combining this with $\sum_{s\in S\setminus\left\{ t\right\} }a_{s} \mathbf{s}_{s}g_{s}\overset{\ast}{\underset{G}{\longrightarrow}}0$, we obtain $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}\overset{\ast }{\underset{G}{\longrightarrow}}0$ (since $\overset{\ast }{\underset{G}{\longrightarrow}}$ is the reflexive-and-transitive closure of the relation $\underset{G}{\longrightarrow}$). This completes the induction step, and thus Lemma 1 is proven.

Let us restate Lemma 1 using a stupid definition:

Definition. Let $S$ be a finite set. For each $s\in S$, let $g_{s}$ be an element of $G$, and let $\mathbf{s}_{s}\in\mathbf{M}$ and $a_{s} \in\mathbf{k}$ be arbitrary. Assume that the monomials $\mathbf{s} _{s}\operatorname*{HT}\left( g_{s}\right) $ for all $s\in S$ are distinct. Then, $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}$ is said to be an overlap-free combination of $G$.

Corollary 2. If $f$ is an overlap-free combination of $G$, then $f\overset{\ast}{\underset{G}{\longrightarrow}}0$.

Proof of Corollary 2. This is precisely Lemma 1.

Lemma 3. Let $S$ and $T$ be two finite sets. For each $s\in S$, let $g_{s}$ be an element of $G$, and let $\mathbf{s}_{s}\in\mathbf{M}$ and $a_{s}\in\mathbf{k}$ be arbitrary. For each $t\in T$, let $h_{t}$ be an element of $G$, and let $\mathbf{t}_{t}\in\mathbf{M}$ and $b_{t} \in\mathbf{k}$ be arbitrary. Let us make the following three assumptions:

• The monomials $\mathbf{s}_{s}\operatorname*{HT}\left( g_{s}\right) $ for all $s\in S$ are distinct.

• The monomials $\mathbf{t}_{t}\operatorname*{HT}\left( h_{t}\right) $ for all $t\in T$ are distinct.

• We have $\mathbf{s}_{s}\operatorname*{HT}\left( g_{s}\right) \neq\mathbf{t}_{t}\operatorname*{HT}\left( h_{t}\right) $ for all $s\in S$ and $t\in T$.

Then, $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}+\sum_{t\in T}b_{t} \mathbf{t}_{t}h_{t}\overset{\ast}{\underset{G}{\longrightarrow}}0$.

Proof of Lemma 3. The three assumptions we made say that the monomials $\mathbf{s}_{s}\operatorname*{HT}\left( g_{s}\right) $ for all $s\in S$ and the monomials $\mathbf{t}_{t}\operatorname*{HT}\left( h_{t}\right) $ for all $t\in T$ (considered all together, as a family of $\left\vert S\right\vert +\left\vert T\right\vert $ monomials) are distinct. Hence, $\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}+\sum_{t\in T}b_{t}\mathbf{t} _{t}h_{t}$ is an overlap-free combination of $G$. Thus, Corollary 2 (applied to $f=\sum_{s\in S}a_{s}\mathbf{s}_{s}g_{s}+\sum_{t\in T}b_{t} \mathbf{t}_{t}h_{t}$) shows that $\sum_{s\in S}a_{s}\mathbf{s}_{s} g_{s}+\sum_{t\in T}b_{t}\mathbf{t}_{t}h_{t}\overset{\ast }{\underset{G}{\longrightarrow}}0$. This proves Lemma 3.

Theorem 4. Let $f\in G$ and $g\in G$ be such that the monomials $\operatorname*{HT}\left( f\right) $ and $\operatorname*{HT}\left( g\right) $ are disjoint. Then, $\operatorname*{spol}\left( f,g\right) \overset{\ast}{\underset{G}{\longrightarrow}}0$.

Proof of Theorem 4. The polynomials $f$ and $g$ are monic (since they belong to $G$). Thus, the definition of $\operatorname*{spol}\left( f,g\right) $ yields $\operatorname*{spol}\left( f,g\right) =\mathbf{x}f-\mathbf{y}g$, where $\mathbf{x}$ and $\mathbf{y}$ are the unique two monomials satisfying $\mathbf{x}\operatorname*{HT}\left( f\right) =\mathbf{y} \operatorname*{HT}\left( g\right) =\operatorname{lcm}\left( \operatorname*{HT}\left( f\right) ,\operatorname*{HT}\left( g\right) \right) $. Consider these $\mathbf{x}$ and $\mathbf{y}$. Since $\operatorname*{HT}\left( f\right) $ and $\operatorname*{HT}\left( g\right) $ are disjoint, we have $\operatorname{lcm}\left( \operatorname*{HT}\left( f\right) ,\operatorname*{HT}\left( g\right) \right) =\operatorname*{HT}\left( f\right) \cdot\operatorname*{HT}\left( g\right) $. Thus, $\mathbf{y}\operatorname*{HT}\left( g\right) =\operatorname{lcm}\left( \operatorname*{HT}\left( f\right) ,\operatorname*{HT}\left( g\right) \right) =\operatorname*{HT}\left( f\right) \cdot\operatorname*{HT}\left( g\right) $. Cancelling $\operatorname*{HT}\left( g\right) $, we obtain $\mathbf{y} =\operatorname*{HT}\left( f\right) $. Similarly, $\mathbf{x} =\operatorname*{HT}\left( g\right) $.

The polynomial $f$ is monic. Hence, the polynomial $f-\operatorname*{HT} \left( f\right) $ has a smaller head term than $f$. In other words, the polynomial $f-\operatorname*{HT}\left( f\right) $ is a $\mathbf{k}$-linear combination of monomials smaller than $\operatorname*{HT}\left( f\right) $. In view of $\mathbf{y}=\operatorname*{HT}\left( f\right) $, this rewrites as follows: The polynomial $f-\mathbf{y}$ is a $\mathbf{k}$-linear combination of monomials smaller than $\mathbf{y}$. Thus, $f-\mathbf{y}$ can be written as $f-\mathbf{y}=\sum_{s\in S}\lambda_{s}\mathbf{s}_{s}$ for some finite set $S$, some distinct monomials $\mathbf{s}_{s} \in\mathbf{M}$ that are smaller than $\mathbf{y}$, and some scalars $\lambda_{s}\in\mathbf{k}$. Consider these $S$, $\mathbf{s}_{s}$ and $\lambda_{s}$.

The polynomial $g$ is monic. Hence, the polynomial $g-\operatorname*{HT} \left( g\right) $ has a smaller head term than $g$. In other words, the polynomial $g-\operatorname*{HT}\left( g\right) $ is a $\mathbf{k}$-linear combination of monomials smaller than $\operatorname*{HT}\left( g\right) $. In view of $\mathbf{x}=\operatorname*{HT}\left( g\right) $, this rewrites as follows: The polynomial $g-\mathbf{x}$ is a $\mathbf{k}$-linear combination of monomials smaller than $\mathbf{x}$. Thus, $g-\mathbf{x}$ can be written as $g-\mathbf{x}=\sum_{t\in T}\mu_{t}\mathbf{t}_{t}$ for some finite set $T$, some distinct monomials $\mathbf{t}_{t}\in\mathbf{M}$ that are smaller than $\mathbf{x}$, and some scalars $\mu_{t}\in\mathbf{k}$. Consider these $T$, $\mathbf{t}_{t}$ and $\mu_{t}$.

Recall that $\operatorname{lcm}\left( \operatorname*{HT}\left( f\right) ,\operatorname*{HT}\left( g\right) \right) =\operatorname*{HT}\left( f\right) \cdot\operatorname*{HT}\left( g\right) $. In view of $\mathbf{y} =\operatorname*{HT}\left( f\right) $ and $\mathbf{x} =\operatorname*{HT}\left( g\right) $, this rewrites as $\operatorname{lcm} \left( \mathbf{y} , \mathbf{x} \right) = \mathbf{y} \mathbf{x}$.

Now, \begin{align*} \operatorname*{spol}\left( f,g\right) & =\mathbf{x}f-\mathbf{y} g=\underbrace{\left( f-\mathbf{y}\right) }_{=\sum_{s\in S}\lambda _{s}\mathbf{s}_{s}}g-\underbrace{\left( g-\mathbf{x}\right) } _{=\sum_{t\in T}\mu_{t}\mathbf{t}_{t}}f\\ & =\left( \sum_{s\in S}\lambda_{s}\mathbf{s}_{s}\right) g-\left( \sum_{t\in T}\mu_{t}\mathbf{t}_{t}\right) f=\sum_{s\in S}\lambda _{s}\mathbf{s}_{s}g-\sum_{t\in T}\mu_{t}\mathbf{t}_{t}f\\ & =\sum_{s\in S}\lambda_{s}\mathbf{s}_{s}g+\sum_{t\in T}\left( -\mu _{t}\right) \mathbf{t}_{t}f. \end{align*}

Now, we make the following three observations:

• The monomials $\mathbf{s}_{s}\operatorname*{HT}\left( g\right) $ for all $s\in S$ are distinct. (This is because the monomials $\mathbf{s}_{s}$ for all $s\in S$ are distinct.)

• The monomials $\mathbf{t}_{t}\operatorname*{HT}\left( f\right) $ for all $t\in T$ are distinct. (This is because the monomials $\mathbf{t}_{t}$ for all $t\in T$ are distinct.)

• We have $\mathbf{s}_{s}\operatorname*{HT}\left( g\right) \neq \mathbf{t}_{t}\operatorname*{HT}\left( f\right) $ for all $s\in S$ and $t\in T$. [Proof: Assume the contrary. Thus, there exist $s\in S$ and $t\in T$ such that $\mathbf{s}_{s}\operatorname*{HT}\left( g\right) =\mathbf{t}_{t}\operatorname*{HT}\left( f\right) $. Consider these $s$ and $t$. We have $\mathbf{s}_{s}\operatorname*{HT}\left( g\right) =\mathbf{t}_{t}\operatorname*{HT}\left( f\right) $; in other words, $\mathbf{s}_{s} \mathbf{x} =\mathbf{t}_{t} \mathbf{y}$ (since $\mathbf{y} =\operatorname*{HT}\left( f\right) $ and $\mathbf{x} =\operatorname*{HT}\left( g\right) $). But $\mathbf{s}_{s}<\mathbf{y}$ (since all monomials $\mathbf{s}_{s}$ are smaller than $\mathbf{y}$). The monomial $\mathbf{s}_{s} \mathbf{x}$ is a multiple of $\mathbf{y}$ and $\mathbf{x}$ at the same time (since $\mathbf{s}_{s} \mathbf{x} =\mathbf{t}_{t} \mathbf{y}$). Thus (by the universal property of the lowest common multiple), we conclude that $\mathbf{s}_{s} \mathbf{x}$ is a multiple of $\operatorname{lcm} \left( \mathbf{y} , \mathbf{x} \right) = \mathbf{y} \mathbf{x}$. In other words, $\mathbf{s}_{s} \mathbf{x} =\mathbf{z} \mathbf{y} \mathbf{x} $ for some monomial $\mathbf{z}\in\mathbf{M}$. Consider this $\mathbf{z}$. Canceling $\mathbf{x}$ from $\mathbf{s}_{s} \mathbf{x} =\mathbf{z} \mathbf{y} \mathbf{x}$, we obtain $\mathbf{s}_{s} =\mathbf{z} \mathbf{y} = \mathbf{y} \cdot \mathbf{z}$. Since our order is a term order, we have $1\leq\mathbf{z}$ and thus $\mathbf{y}\cdot1\leq\mathbf{y}\cdot\mathbf{z} =\mathbf{s}_{s} <\mathbf{y}=\mathbf{y}\cdot1$. This is clearly absurd. This contradiction completes our proof.]

Due to these three observations, we can apply Lemma 3 to $g_{s}=g$, $a_{s}=\lambda_{s}$, $h_{t}=f$ and $b_{t}=-\mu_{t}$. We thus obtain $\sum_{s\in S}\lambda_{s}\mathbf{s}_{s}g+\sum_{t\in T}\left( -\mu _{t}\right) \mathbf{t}_{t}f\overset{\ast}{\underset{G}{\longrightarrow}}0$. In view of $\operatorname*{spol}\left( f,g\right) =\sum_{s\in S}\lambda _{s}\mathbf{s}_{s}g+\sum_{t\in T}\left( -\mu_{t}\right) \mathbf{t}_{t} f$, this rewrites as $\operatorname*{spol}\left( f,g\right) \overset{\ast }{\underset{G}{\longrightarrow}}0$. This proves Theorem 4.