Polynomial division and Universal bases

Polynomial division

$\DeclareMathOperator{\In}{In} \DeclareMathOperator{\ld}{Ld} \DeclareMathOperator{\kk}{\mathbb{K}} \DeclareMathOperator{\rnpos}{\mathbb{R}^n_{> 0}} \DeclareMathOperator{\rnzero}{\mathbb{R}^n_{\geq 0}} \DeclareMathOperator{\rr}{\mathbb{R}} \DeclareMathOperator{\scrB}{\mathcal{B}} \DeclareMathOperator{\scrI}{\mathcal{I}} \DeclareMathOperator{\scrJ}{\mathcal{J}} \DeclareMathOperator{\supp}{Supp} \DeclareMathOperator{\znpos}{\mathbb{Z}^n_{> 0}} \DeclareMathOperator{\znzero}{\mathbb{Z}^n_{\geq 0}} \DeclareMathOperator{\zz}{\mathbb{Z}}$In this post we talk about division with respect to polynomials in more than one variables, which is a pretty cute algorithm that changed the face of a big part of mathematics, via e.g. Gröbner bases which we will also talk about. Dividing by polynomials in a single variable is straightforward – to divide $f$ by $g$, you pick a monomial $m$ such that the highest degree terms of $f$ and $mg$ are equal, then repeat the same process with $f – mg$ in place of $f$. Since the degree, as a nonnegative integer, can not drop infinitely many times, this algorithm stops after a finitely many steps, and you end up with polynomials $q$ (the quotient) and $r$ (the remainder) such that $f = qg + r$ and $\deg(r) < \deg(f)$. To divide by polynomials in more than one variables, you need an analogue of the “highest degree monomial term” of the single-variable case. A natural resolution comes via monomial orders.

A monomial order is a binary relation $\preceq$ on $\znzero$ such that

$\preceq$ is a total order,
$\preceq$ is compatible with the addition on $\znzero$, i.e. $\alpha \preceq \beta$ implies $\alpha + \gamma \preceq \beta + \gamma$ for all $\gamma \in \znzero$, and
$0 \preceq \alpha$ for all $\alpha \in \znzero$.

It turns out that in the presence of the first two conditions, the third one is equivalent to the following condition:

$\preceq$ is a well order on $\znzero$

(For one direction: if $\alpha \preceq 0$ for some $\alpha \in \znzero \setminus \{0\}$, then $\{\alpha, 2\alpha, 3\alpha, \ldots \}$ is an infinite set with no minimal element with respect to $\preceq$. See [Mon21, Corollary B.47] for an elementary proof for the opposite direction.)

The support $\supp(f)$ of a polynomial $f \in \kk[x_1, \ldots, x_n]$, where $\kk$ is a field, is the set of all $\alpha \in \znzero$ such that $x^\alpha$ appears in $f$ with a nonzero coefficient. We write $\delta_\preceq(f)$ for the maximal element of $\supp(f)$ with respect to $\preceq$. The leading term $\ld_\preceq(f)$ of $f$ with respect to $\preceq$ is the monomial term $cx^\alpha$ where $\alpha = \delta_\preceq(f)$ and $c$ is the coefficient of $x^\alpha$ in $f$. The division algorithm in $\kk[x_1, \ldots, x_n]$ is the procedure for reducing a polynomial $f$ by a finite ordered collection of polynomials $g_1, \ldots, g_N$ as follows:

If there is $i$ such that $\ld_\preceq(g_i)$ divides $\ld_\preceq(f)$, then pick the smallest such $i$, and replace $f$ by $f – hg_i$, where $h := \ld_\preceq(f)/\ld_\preceq(g_i)$.
Otherwise $\ld_\preceq(f)$ is not divisible by $\ld_\preceq(g_i)$ for any $i$; in this case replace $f$ by $f – \ld_\preceq(f)$.
Repeat.

Since $\delta_\preceq(f)$ decreases at every step of the division algorithm, the well ordering property of $\preceq$ implies that the algorithm stops after finitely many steps. It is clear that after the algorithm stops, one has \[f = \sum_i h_i g_i + r\] where either $r = 0$, or for every $i$, $\ld_\preceq(g_i)$ does not divide any term of $r$; we say that $r$ is the remainder of $f$ modulo division by the $g_i$. This immediately implies the following result:

Theorem 1. Let $g_1, \ldots, g_N$ be elements of an ideal $I$ of $\kk[x_1, \ldots, x_n]$ such that $\ld_\preceq(g_1), \ldots, \ld_\preceq(g_N)$ generate the leading ideal $\ld_\preceq(I)$ generated by $\{\ld_\preceq(f): f \in I\}$. Then for all $f \in \kk[x_1, \ldots, x_n],$ the following are equivalent:

$f \in I$,
the remainder of $f$ modulo $g_1, \ldots, g_N$ is zero.

A Gröbner basis of $I$ with respect to a monomial ordering $\preceq$ is simply a finite set of elements $g_1, \ldots, g_N \in I$ such that $\ld_\preceq(g_i),$ $1 \leq i \leq N,$ generate $\ld_\preceq(I)$.

For later use we record a few corollaries of the division algorithm.

Corollary 1. Let $I \supseteq J$ be ideals of $\kk[x_1, \ldots, x_n]$. If $I \supsetneqq J$, then $\ld_\preceq(I) \supsetneqq \ld_\preceq(J)$ for every monomial order $\preceq$.

Proof. If there are $g_1, \ldots, g_N \in J$ such that $\ld_\preceq(g_i)$, $i = 1, \ldots, N$, generate $\ld_\preceq(I)$, then Theorem 1 implies that $g_1, \ldots, g_N$ generate $I$, so that $I = J$.

Corollary 2. Let $I$ be an ideal of $\kk[x_1, \ldots, x_n]$. There can not exist monomial orders $\preceq_1, \preceq_2$ such that $\ld_{\preceq_1}(I) \subsetneqq \ld_{\preceq_2}(I)$.

Proof. Write $J_k := \ld_{\preceq_k}(I)$, $k = 1, 2$. Assume to the contrary that $J_1 \subsetneqq J_2$. Choose $g_1, \ldots, g_N \in I$ such that $\ld_{\preceq_2}(g_i)$, $i = 1, \ldots, N$, generate $J_1$. Choose $f \in I$ such that $\ld_{\preceq_2}(f) \not\in J_1$. Let $r$ be the remainder of the division of $f$ by $g_1, \ldots, g_N$ with respect to $\preceq_2$. Then $r$ is a nonzero element of $I$ such that $\supp(r) \cap \supp(J_1) = \emptyset$. On the other hand, if $h_1, \ldots, h_M \in I$ are such that $\ld_{\preceq_1}(h_1), \ldots, \ld_{\preceq_1}(h_M)$ generate $J_1$, then division of $r$ by $h_1, \ldots, h_M$ with respect to $\preceq_1$ implies that $r \not\in I$, which is a contradiction.

Starting from a Gröbner basis of an ideal, one can discard “redundant” elements (whose leading terms are divisible by the leading term of some other basis element) and then replace each remaining element by the remainder of the division by the others to obtain a reduced Gröbner basis, i.e. a Gröbner basis such that

no monomial term of any basis element is divisible by the leading term of any other basis element, and
the leading coefficient, i.e. the coefficient of the leading term, of each basis element is $1.$

Corollary 3. The reduced Gröbner basis is uniquely determined up to a permutation by the leading ideal. In particular,

up to a permutation of the basis elements there is a unique reduced Gröbner basis for every monomial order, and
if an ideal has the same leading ideal for two monomial orders, then it also has the same reduced Gröbner basis (up to permutations) for those monomial orders.

Proof. Indeed, fix two reduced Gröbner bases $g_1, \ldots, g_N$ and $h_1, \ldots, h_M$ of an ideal $I$ with respect to a monomial order $\preceq.$ For each $h_j$, its leading term is divisible by the leading term of at least one $g_i,$ but there can not be more than one such $i,$ since then

either the leading term of both such $g_i$ would be divisible by $h_j,$
or there would be $j’ \neq j$ such that the leading term of $h_{j’}$ divides the leading term of one of the $g_i$, and therefore in turn divides the leading term of $h_j$

Each of these possibilities contradicts the reducedness of one of the above Gröbner bases. It follows that for each $j \in \{1, \ldots, M\},$ there is a unique $i \in \{1, \ldots, N\}$ such that $\ld_\preceq(g_i)$ divides $\ld_\preceq(h_j).$ Similarly for each $i \in \{1, \ldots, N\},$ there is a unique $j \in \{1, \ldots, M\}$ such that $\ld_\preceq(h_j)$ divides $\ld_\preceq(g_i).$ It follows that $M = N$ and after reordering the $g_i$ and the $h_j$ if necessary, one can ensure that $\ld_\preceq(g_i) = \ld_\preceq(h_i),$ $i = 1, \ldots, N.$ Now fix $i$ and divide $h_i$ by $g_1, \ldots, g_N.$ Since for $j \neq i$ the leading term of $g_j$ does not divide any monomial term of $h_i,$ after the first step the remainder is $h_i – g_i,$ and if $h_i – g_i \neq 0,$ then at the second step the leading term of $h_i – g_i$ must be divisible by the leading term of $g_i.$ But this is impossible, since the exponent of each monomial term of $h_i – g_i$ is smaller than $\delta_\preceq(g_i) = \delta_\preceq(h_i).$ It follows that $h_i = g_i,$ which proves the first assertion. For the second assertion, pick a monomial order $\preceq’$ such that $\ld_{\preceq’}(I) = \ld_\preceq(I).$ Let $\alpha_i := \delta_{\preceq}(g_i),$ $i = 1, \ldots, n.$ Fix $i.$ Since $\ld_{\preceq’}(I)$ is generated by $x^{\alpha_1}, \ldots, x^{\alpha_N}$, it follows that $\ld_{\preceq’}(g_i)$ is divisible by some $x^{\alpha_j}.$ Since no monomial in the support of $g_i$ is divisible by $x^{\alpha_j}$ for $j \neq i$ it must be divisible by $x^{\alpha_i}.$ Since $\alpha_i$ is also in the support of $g_i,$ we must have that $\delta_{\preceq’}(g_i) = \alpha_i.$ It follows that $g_1, \ldots, g_N$ form a Gröbner basis of $I$ with respect to $\preceq’$ as well. It is clear that this is a reduced Gröbner basis, as required.

Universal bases for Leading ideals

In this section we prove that as $\preceq$ varies over all possible monomial orders, there can be only finitely many leading ideals for a given ideal of a polynomial ring. The argument is elementary and very cute. I learned it from [Stu96, Chapter 1]. Mora and Robbiano [MoRobbiano88, Page 193] write that it is due to Alessandro Logar.

Theorem 2. Every ideal $I$ of $\kk[x_1, \ldots, x_n]$ has finitely many distinct leading ideals. In particular, there is a finite subset of $I$ such that for every monomial order, the leading terms of polynomials in that subset generate the leading ideal of $I.$

Proof. Assume to the contrary that there is an infinite collection $\scrJ_0$ of distinct leading ideals of $I$. Pick an arbitrary nonzero element $f_1 \in I$. Out of the finitely many monomial terms of $f_1$, there must be one, say $m_1$, such that $\scrJ_1 := \{J \in \scrJ_0: \langle m_1 \rangle \subsetneqq J\}$ is infinite. Pick $J_1 \in \scrJ_1$ and a monomial order $\preceq_1$ such that to $J_1 = \ld_{\preceq_1}(I)$. Since $m_1 \in J_1$, there is $g_1 \in I$ such that $\ld_{\preceq_1}(g_1) = m_1$, and since $\langle m_1 \rangle \neq J_1$, there is $h_1 \in I$ such that $\ld_{\preceq_1}(h_1) \not\in \langle m_1 \rangle.$ Let $f_2$ be the remainder of $h_1$ modulo division by $g_1$. Then $f_2$ is nonzero, and no monomial term in $f_2$ belongs to $\langle m_1 \rangle$. Since $f_2$ has finitely many monomial terms, there must be a monomial term $m_2$ of $f_2$ such that $\scrJ_2 := \{J \in \scrJ_1: \langle m_1, m_2 \rangle \subsetneqq J\}$ is infinite. Now choose $J_2 \in \scrJ_2$ and a monomial order $\preceq_2$ such that to $J_2 = \ld_{\preceq_2}(I)$. As in the preceding case, there are $g_{21}, g_{22}, h_2 \in I$ such that $\ld_{\preceq_2}(g_{21}) = m_1$, $\ld_{\preceq_2}(g_{22}) = m_2$, and $\ld_{\preceq_2}(h_2) \not\in \langle m_1, m_2 \rangle.$ Define $f_3$ to be the remainder of $h_2$ modulo division by $g_{21}, g_{22}$. Then $f_3$ is nonzero, and no monomial term in $f_3$ belongs to $\langle m_1, m_2 \rangle,$ and we can proceed to define $\scrJ_3$ as above. In this way we get an infinite strictly increasing chain of monomial ideals: \[ \langle m_1 \rangle \subsetneqq \langle m_1, m_2 \rangle \subsetneqq \langle m_1, m_2, m_3 \rangle \subsetneqq \cdots \] which violates the Noetherianity of $\kk[x_1, \ldots, x_n]$ and completes the proof of the first assertion. The second assertion then follows from Corollary 3.

A universal (leading) basis for an ideal $I$ of $\kk[x_1, \ldots, x_n]$ is an ordered collection $\scrB$ of elements in $I$ such that for every monomial order $\preceq$ on $\znzero$, the leading ideal of $I$ with respect to $\preceq$ is generated by the leading terms of the elements in $\scrB$. The above theorem implies that every ideal has a finite universal basis.

Every leading ideal comes from a positive weighted degree

Weighted degrees are natural generalizations of degree. Every $\omega \in \rr^n$ defines a weighted degree, and for $f \in \kk[x_1, \ldots, x_n]$ we write $\ld_\omega(f)$ for the corresponding leading term of $f$. Given an ideal $I$ of $\kk[x_1, \ldots, x_n]$ we similarly write $\ld_\omega(I)$ for its leading ideal generated by $\ld_\omega(f)$ for all $f \in I$. In this section, also following [Stu96, Chapter 1], we prove the following result:

Theorem 3. For every ideal $I$ of $\kk[x_1, \ldots, x_n]$ and every monomial order $\preceq$, there is $\omega \in \znpos$ such that $\ld_\omega(I) = \ld_\preceq(I)$ (in particular, this means that $\ld_\omega(I)$ is a monomial ideal).

Remark. With a bit more work it can be more can be established (the proof is completely analogous to the proof of Theorem 3 from the next post): given a monomial order $\preceq$ and polynomials $g_1, \ldots, g_N ,$ there is $\omega \in \znpos$ such that \[\ld_\omega(g_i) = \ld_\preceq(g_i),\ i = 1, \ldots, N.\]If in addition the $g_i$ are elements of an ideal $I$ such that $\ld_\preceq(g_i),$ $i = 1, \ldots, N,$ generate $\ld_\preceq(I),$ then\[\ld_\omega(I) = \langle \ld_\omega(g_1), \ldots, \ld_\omega(g_N)\rangle = \langle \ld_\preceq(g_1), \ldots, \ld_\preceq(g_N)\rangle = \ld_\preceq(I)\]Moreover, every $f \in I$ has an expression of the form $f = \sum_i f_ig_i$ such that

$\delta_\preceq(f) = \max_\preceq\{\delta_\preceq(f_ig_i)\},$ and
$\omega(f) = \max\{\omega(f_ig_i)\}.$

Proof of Theorem 3. Fix a Gröbner basis $g_1, \ldots, g_N$ of $I$ with respect to $\preceq$. Write \[g_i = c_{i0} x^{\alpha_{i0}} + \cdots + c_{iN_i}x^{\alpha_{iN_i}}\]with $\alpha_{i0} = \delta_\preceq(g_i)$. Define \[C := \{\omega \in \rnzero: \langle \omega, \alpha_{i0} – \alpha_{ij} \rangle \geq 0,\ i = 1, \ldots, N,\ j = 1, \ldots, N_i\}\]Note that $C$ is a convex polyhedral cone. We claim that $\dim(C) = n$. Indeed, $C$ is dual to the cone $C’$ generated by $\alpha_{i0} – \alpha_{ij},\ i = 1, \ldots, N,\ j = 1, \ldots, N_i$, and the standard basis vectors $e_1, \ldots, e_n$ of $\rr^n$. If $\dim(C) < n$, it would follow that $C’$ is not strongly convex. Since $C’$ is also rational, there would be nonnegative integers $\lambda_{ij}$, not all zero, such that \[\sum_{i,j}\lambda_{ij}(\alpha_{i0} – \alpha_{ij}) = -\sum_k r_ke_k\]for some nonnegative integers $r_1, \ldots, r_n$. Due to the second and third properties of a monomial order, it would follow that \[\sum_{i,j}\lambda_{ij} \alpha_{i0} \preceq \sum_{i,j}\lambda_{ij} \alpha_{ij}\]On the other hand, by construction $\alpha_{i0} \succ \alpha_{ij}$ for each $i,j$, so that \[\sum_{i,j}\lambda_{ij} \alpha_{i0} \succ \sum_{i,j}\lambda_{ij} \alpha_{ij}\]This contradiction shows that $\dim(C) = n$, as claimed. In particular this implies (see e.g. [Mon21, Proposition V.15]) that the topological interior $C^0$ of $C$ has a nonempty intersection with $\znpos$, and if $\omega \in C^0 \cap \znpos$, then $\ld_\omega(g_i) = c_{i0}x^{\alpha_{i0}}$. Since $\ld_\preceq(I)$ is generated by $c_{i0}x^{\alpha_{i0}}$, $i = 1, \ldots, N,$ it follows that $\ld_\omega(I) \supseteq \ld_\preceq(I)$. If this containment were proper, then Corollary 1 to Theorem 1 would imply that \[\ld_\preceq(\ld_\omega(I)) \supsetneqq \ld_\preceq(\ld_\preceq(I)) = \ld_\preceq(I)\]On the other hand, it is straightforward to check that \[\ld_\preceq(\ld_\omega(I)) = \ld_{\preceq_\omega}(I)\] where $\preceq_\omega$ is the binary relation on $\znzero$ defined as follows: $\alpha \preceq_\omega \beta$ if and only if either $\langle \omega, \alpha \rangle < \langle \omega, \beta \rangle$, or $\langle \omega, \alpha \rangle = \langle \omega, \beta \rangle$ and $\alpha \preceq \beta$. Since $\omega \in \znzero$, it follows that $\preceq_\omega$ is a monomial order, and taken toegther, the last two displays above contradict Corollary 2 to Theorem 1. Consequently, $\ld_\omega(I) = \ld_\preceq(I)$, as required.

References

[Stu96] Bernd Sturmfels, Gröbner bases and convex polytopes, AMS, 1996.
[MoraRobbiano88] Teo Mora and Lorenzo Robbiano, The Gröbner fan of an ideal, J. Symbolic Computation, 1988 (6).
[Mon21] Pinaki Mondal, How many zeroes?, CMS/CAIMS/Springer, 2021 (arxiv:1806.05346).

pinaki's homepage

Polynomial division and Universal bases