# Division with power series

$$\DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\In}{In} \DeclareMathOperator{\ld}{Ld} \DeclareMathOperator{\kk}{\mathbb{K}} \DeclareMathOperator{\nd}{ND} \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{\znplusonezero}{\mathbb{Z}^{n+1}_{\geq 0}} \DeclareMathOperator{\znplusonepos}{\mathbb{Z}^{n+1}_{> 0}} \DeclareMathOperator{\znpos}{\mathbb{Z}^n_{> 0}} \DeclareMathOperator{\znzero}{\mathbb{Z}^n_{\geq 0}} \DeclareMathOperator{\zz}{\mathbb{Z}}$$In this post we look at division in the ring $$\hat R := \kk[[x_1, \ldots, x_n]]$$ of formal power series over a field $$\kk$$. In contrast to division in polynomial rings discussed in the preceding post, while trying to divide by power series, one is forced to consider initial terms with respect to monomial orders.

The initial exponent $$\nu_\preceq(f)$$ of $$f \in \hat R$$ with respect to a monomial order $$\preceq$$ is the minimal element of $$\supp(f)$$ with respect to $$\preceq$$ (note: the minimal element is guaranteed to exist due to the well ordering property of a monomial order). The initial term $$\In_\preceq(f)$$ of $$f$$ is the monomial term $$cx^\alpha$$ where $$\alpha = \nu_\preceq(f)$$ and $$c$$ is the coefficient of $$x^\alpha$$ in $$f$$. Given an ideal $$I$$ of $$\hat R$$, its initial ideal $$\In_\preceq(I)$$ is the ideal generated by $$\{\In_\preceq(f): f \in I\}$$.

Lemma 1. If $$f_1, \ldots, f_N \in \hat R$$ have mutually distinct values of $$\nu_\preceq$$, then the $$f_i$$ are linearly independent over $$\kk$$.

Proof. Indeed, pick the unique $$i$$ such that $$\nu_\preceq(f_i) = \min_\preceq\{\nu_\preceq(f_j): j = 1, \ldots, N\}$$. Then $$\nu_\preceq(f_i)$$ does not appear in the support of $$f_j$$ for any $$j \neq i$$, so it can not be cancelled by any $$\kk$$-linear combination of the $$(f_j)_{j \neq i}$$.

The division algorithm in $$\hat R$$ is completely analogous to that for polynomials, the only twist being that the process may not stop in finitely many steps, the quotient and remainders are defined as the (well-defined) limits of the quotients and remainders computed in the finite steps. The division of $$f \in \hat R$$ by an ordered collection $$g_1, \ldots, g_N$$ of elements in $$\hat R$$ goes as follows:

1. Initially set $$f_0 := f$$, and define $$r_0, q_{0,1}, \ldots, q_{0,N}$$ to be zero. ($$r_i$$ and the $$q_{i,j}$$ would be the finite step approximations of respectively the remainder and the quotients, and they will be updated in every step.)
2. Assuming $$f_i, r_i, q_{i,1}, \ldots, q_{i,N}$$ have been computed, proceed to the next step as follows:
1. If there is $$j$$ such that $$\In_\preceq(g_j)$$ divides $$\In_\preceq(f_i)$$, then pick the smallest such $$j$$, compute $$q’_{i,j} := \In_\preceq(f_i)/\In_\preceq(g_j)$$, and set$f_{i+1} := f_i – q’_{i,j}g_j,$$q_{i+1,j} := q_{i,j} + q’_{i,j},$$q_{i+1,k} := q_{i,k}\ \text{if}\ k \neq j,$ $r_{i+1} := r_i$
2. Otherwise $$\In_\preceq(f_i)$$ is not divisible by $$\In_\preceq(g_j)$$ for any $$j$$; in this case define$f_{i+1} := f_i – \In_\preceq(f_i),$$q_{i+1,j} := q_{i,j},\ j = 1, \ldots, N,$$r_{i+1} := r_i + \In_\preceq(f_i)$
3. Set $$r := \lim_{i \to \infty}r_i$$ and $$q_j := \lim_{i \to \infty}q_{i,j}$$, $$j = 1, \ldots, N.$$

Theorem 1. $$r$$ and the $$q_j$$ are well defined elements in $$\hat R$$ such that $f = \sum_j q_jg_j + r$where

• either $$r = 0$$ or no monomial term in $$r$$ is divisible by $$\In_\preceq(g_j)$$ for any $$j$$;
• $$\In_\preceq(\sum_j q_jg_j) \in \langle \In_\preceq(g_j): j = 1, \ldots, N \rangle$$; more precisely, there is a reordering $$i_1, \ldots, i_s$$ of $$\{i: q_i \neq 0\}$$ such that $\In_\preceq(\sum_j q_jg_j) = \In_\preceq(q_{i_1}g_{i_1}) \prec \In_\preceq(q_{i_2}g_{i_2}) \prec \cdots \prec \In_\preceq(q_{i_s}g_{i_s})$where all the $$\prec$$ orders on the right hand side are strict.

In addition, if $$g_1, \ldots, g_N$$ are elements of an ideal $$I$$ of $$\hat R$$ such that $$\In_\preceq(g_1), \ldots, \In_\preceq(g_N)$$ generate $$\In_\preceq(I)$$, then the following are equivalent:

1. $$f \in I$$,
2. $$r = 0$$.

In particular, $$g_1, \ldots, g_N$$ generate $$I$$ as well.

Proof. By construction at every step $$i$$, for each of $$r_i, q_{i,1}, \ldots, q_{i,N}$$, either it remains unchanged from the previous step or its initial exponent increases from the previous step. Lemma 1 then implies that for each degree $$d$$, if $$i$$ is sufficiently large, then all terms (if any) added to $$r_i$$ or $$q_{i,j}$$ have degree greater than $$d$$. This proves that $$r$$ and the $$q_j$$ are well defined power series, and similarly, it follows that $$\lim_{i \to \infty} f_i = 0.$$ All the remaining assertions of Theorem 1 are then immediate.

All the results of polynomial division discussed in the previous post have corresponding analogues for power series:

Corollary 1. Let $$I \supseteq J$$ be ideals of $$\hat R$$. If $$I \supsetneqq J$$, then $$\In_\preceq(I) \supsetneqq \In_\preceq(J)$$ for every monomial order $$\preceq$$.

Corollary 2. Let $$I$$ be an ideal of $$\hat R$$. There can not exist monomial orders $$\preceq_1, \preceq_2$$ such that $$\In_{\preceq_1}(I) \subsetneqq \In_{\preceq_2}(I)$$.

The proofs of Corollaries 1 and 2 are identical to that from the polynomial case, one only needs to replace “leading” (terms, ideals, etc) by the corresponding “initial” versions. We also have the analogue for a “reduced” Gröbner basis: a finite ordered collection of elements $$g_1, \ldots, g_N$$ from an ideal $$I$$ is called a reduced initial basis with respect to a monomial order $$\preceq$$ if the following hold:

1. the initial terms of the $$g_i$$ generate $$\In_\preceq(I),$$
2. no monomial term of any $$g_i$$ is divisible by the initial term of any $$g_j$$ for $$j \neq i$$, and
3. the initial coefficient, i.e. the coefficient of the initial term, of each $$g_i$$ is $$1.$$

A reduced initial basis can be produced by taking a minimal set of elements of $$I$$ whose initial terms generate $$\In_\preceq(I)$$ and then replacing each element by the remainder of the division by other elements. Corollary 3 of the polynomial division is not completely true for power series, since even an ideal $$I$$ generated by a single power series $$\phi$$ has infinitely many distinct initial bases: for each polynomial $$f$$ without constant term, $$(1 + \psi)\phi$$ is a reduced initial basis of $$I$$ for any power series $\psi$ with zero constant term. However, some parts of the result still remain valid:

Corollary 3. For an ideal $I$ of $\hat R$, its initial ideal (with respect to a monomial order) uniquely determines the number of the elements and the initial terms of a reduced initial basis. Moreover, if $I$ has the same initial ideal for two monomial orders, then any reduced initial basis of $I$ with respect to one of the monomial orders is a reduced initial basis with respect to the other monomial order as well.

Proof. Indeed, let $g_1, \ldots, g_N$ be a reduced initial basis of $I$ with respect to a monomial order $\preceq$. If $h_1, \ldots, h_M$ is also a reduced initial basis of $I$ with respect to $\preceq$, then the same arguments as in the proof of Corollary 3 of the preceding post show that $M = N$, and after a reordering of the $h_i$ if necessary one has $\In_\preceq(h_i) = \In_\preceq(g_i)$, $i = 1, \ldots, N$. This proves the first assertion. For the second assertion, pick a monomial order $\preceq’$ such that$\In_{\preceq’}(I) = \In_\preceq(I).$ Let $\alpha_i := \nu_{\preceq}(g_i),$ $i = 1, \ldots, N.$ Fix $i.$ Since $\In_{\preceq’}(I)$ is generated by $x^{\alpha_1}, \ldots, x^{\alpha_N}$, it follows that $\In_{\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$, $\In_{\preceq’}(g_i)$ must be divisible by $x^{\alpha_i}.$ Since $\alpha_i$ is also in the support of $g_i,$ we must have that $\nu_{\preceq’}(g_i) = \alpha_i.$ It follows that that $g_i,$ $i = 1, \ldots, N,$ form a reduced initial basis of $I$ with respect to $\preceq’$ as well.

The proof of the Universal Basis Theorem (i.e. Theorem 2 in the previous post) used the fact that the support of a polynomial is finite. To adapt this proof for power series we seek the help of Newton diagrams. Given a power series $$f$$, it follows from basic convex geometry that the convex hull of $$\supp(f) + \rnzero$$ is a convex rational polyhedron (see e.g. [Mon21, Corollary B.48 and Proposition V.29]. The Newton diagram $$\nd(f)$$ of $$f$$ is the union of compact faces of this polyhedron. We write $$f_{\nd}$$ for the “part” of $$f$$ supported at its Newton diagram; more precisely, if $$f = \sum_\alpha c_\alpha x^\alpha$$, then $f_{\nd} := \sum_{\alpha \in \nd(f)} c_\alpha x^\alpha$Note in particular that $$\supp(f_{\nd})$$ is finite.

Lemma 2. For any monomial order $$\preceq$$ and power series $$f$$, $$\In_\preceq(f) = \In_\preceq(f_{\nd}).$$

Proof. Every $$\alpha \in \supp(f) \setminus \nd(f)$$ is a convex rational combination $\alpha = \sum_{i=1}^N r_i(\alpha_i + \beta_i)$such that

• $$\alpha_i \in \nd(f)$$, $$\beta_i \in \rnzero$$,
• each $$\alpha_i$$ is a vertex of $$\nd(f)$$,
• the coordinates of all $$\beta_i$$ are rational
• not all $$\beta_i$$ are zero

Then clearing out the denominators of all $$r_i$$ and $$\beta_i$$ leads to an identity of the form $k\alpha = \alpha_{i_1} + \cdots + \alpha_{i_k} + \beta$where $$k$$ is a positive integer, $$\alpha_{i_j}$$ are vertices of $$\nd(f)$$, and $$\beta$$ is a nonzero element of $$\znzero$$. It is then clear from the defining properties of a monomial order that there is at least one $$j$$ such that $$\alpha \succ \alpha_{i_j}$$, concluding the proof.

Theorem 2 (Universal Basis Theorem). Every ideal $$I$$ of $$\hat R$$ has finitely many distinct initial ideals. In particular, there is a finite collection $$\scrB$$ of elements in $$I$$ such that for every monomial order $$\preceq$$ on $$\znzero$$, the initial ideal of $$I$$ with respect to $$\preceq$$ is generated by the initial terms of the elements in $$\scrB$$.

Proof. Assume to the contrary that there is an infinite collection $$\scrJ_0$$ of distinct initial ideals of $$I$$. Pick an arbitrary nonzero element $$f_1 \in I$$. Due to Lemma 2, out of the finitely many monomial terms of $$f_{1, \nd}$$, 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 = \In_{\preceq_1}(I)$$. Since $$m_1 \in J_1$$, there is $$g_1 \in I$$ such that $$\In_{\preceq_1}(g_1) = m_1$$, and since $$\langle m_1 \rangle \neq J_1$$, there is $$h_1 \in I$$ such that $$\In_{\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, \nd}$$ has finitely many monomial terms, due to Lemma 2 there must be a monomial term $$m_2$$ of $$f_{2, \nd}$$ 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 = \In_{\preceq_2}(I)$$. As in the preceding case, there are $$g_{21}, g_{22}, h_2 \in I$$ such that $$\In_{\preceq_2}(g_{21}) = m_1$$, $$\In_{\preceq_2}(g_{22}) = m_2$$, and $$\In_{\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 to Theorem 1.

## Weighted orders in division

Every $$\omega \in \rr^n$$ defines a weighted order on $$\hat R$$, and for $$f \in \hat R$$ we write (by an abuse of notation) $$\omega(f)$$ and $$\In_\omega(f)$$ respectively for the corresponding order and initial term of $$f$$. Note that

• There can be $$\omega$$ and $$f$$ such that $$\omega(f) = -\infty$$, in which case $$\In_\omega(f)$$ is not defined!
• If $$\omega \in \rnzero,$$ then $$\omega(f) \geq 0$$ and $$\In_\omega(f)$$ is defined for all $$f \in \hat R.$$

Given an ideal $$I$$ of $$\hat R$$ we write $$\In_\omega(I)$$ for its initial ideal generated by $$\In_\omega(f)$$ for all $$f \in I$$ such that $$\In_\omega(f)$$ is defined.

Theorem 3. Let $$\preceq$$ be a monomial order and $$g_1, \ldots, g_N \in \hat R.$$ Then there is $$\omega \in \znpos$$ such that $\In_\omega(g_i) = \In_\preceq(g_i),\ i = 1, \ldots, N.$If in addition the $$g_i$$ are elements of an ideal $$I$$ such that $$\In_\preceq(g_i),$$ $$i = 1, \ldots, N,$$ generate $$\In_\preceq(I),$$ then$\In_\omega(I) = \langle \In_\omega(g_1), \ldots, \In_\omega(g_N)\rangle = \langle \In_\preceq(g_1), \ldots, \In_\preceq(g_N)\rangle = \In_\preceq(I)$In particular $$\In_\omega(I)$$ is a monomial ideal. Moreover, every $$f \in I$$ has an expression of the form $$f = \sum_i f_ig_i$$ such that

1. $$\nu_\preceq(f) = \min_\preceq\{\nu_\preceq(f_ig_i)\},$$ and
2. $$\omega(f) = \min\{\omega(f_ig_i)\}.$$

Proof. Write $g_{i,\nd} = c_{i0} x^{\alpha_{i0}} + \cdots + c_{iN_i}x^{\alpha_{iN_i}}$with $$\alpha_{i0} = \nu_\preceq(g_i)$$. Define $C := \{\omega \in \rnzero: \langle \omega, \alpha_{i0} – \alpha_{ij} \rangle \leq 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_{ij} – \alpha_{i0},\ i = 1, \ldots, N,\ j = 1, \ldots, N_i$$ (notice the switch from $$\alpha_{i0} – \alpha_{ij}$$ in the formula for $$C$$ to $$\alpha_{ij} – \alpha_{i0}$$ in the formula for $$C’$$) 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_{ij} – \alpha_{i0}) = -\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_{ij} \preceq \sum_{i,j}\lambda_{ij} \alpha_{i0}$On the other hand, by construction $$\alpha_{ij} \succ \alpha_{i0}$$ for each $$i,j$$, so that $\sum_{i,j}\lambda_{ij} \alpha_{ij} \succ \sum_{i,j}\lambda_{ij} \alpha_{i0}$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 $$\In_\omega(g_i) = c_{i0}x^{\alpha_{i0}}$$. This proves the first assertion. The remaining part of the theorem follows immediately from Lemma 3 below.

Remark. Given $$\omega \in \znpos$$ and elements $$g_1, \ldots, g_N$$ of an ideal $$I$$ such that $$\In_\omega(g_i) = \In_\preceq(g_i)$$ for each $$i$$ and $$\In_\preceq(g_i)$$, $$i = 1, \ldots, N$$, generate $$\In_\preceq(I)$$, if one only wanted to prove that $$\In_\omega(I) = \In_\preceq(I),$$ then one can give a much less involved argument than Lemma 3 following [Stu96, Chapter 1]. Indeed, since $$\In_\omega(g_i) = \In_\preceq(g_i)$$ for each $$i$$, it follows that $$\In_\omega(I) \supseteq \In_\preceq(I)$$. If this containment were proper, then Corollary 1 to Theorem 1 would imply that $\In_\preceq(\In_\omega(I)) \supsetneqq \In_\preceq(\In_\preceq(I)) = \In_\preceq(I)$On the other hand, it is straightforward to check that $\In_\preceq(\In_\omega(I)) = \In_{\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, so that the last two displays would contradict Corollary 2 to Theorem 1. It follows that $$\In_\omega(I) = \In_\preceq(I),$$ as required.

Lemma 3. In the situation of Theorem 1 assume there is $$\omega$$ such that $$\omega(\In_\preceq(g_j)) = \omega(g_j)$$ (i.e. $$\omega(g_j)$$ is finite and $$\In_\preceq(g_j)$$ is a monomial with $$\omega$$-value equal to $$\omega(g_j)$$) for each $$j$$. Then

1. $$\omega(q_jg_j) \geq \omega(f)$$ for each $$j$$.
2. $$\omega(r) \geq \omega(f)$$.
3. Assume in addition $$\omega \in \rnpos$$, $$In_\preceq(g_j),$$ $$j = 1, \ldots, N,$$ generate $$\In_\preceq(I)$$, where $$I$$ is the ideal generated by $$g_1, \ldots, g_N,$$ and $$I$$ contains $$f.$$ Then $$\In_\omega(f)$$ is in the ideal generated by $$\In_\omega(g_j),$$ $$j = 1, \ldots, N.$$ (Note that the non-negativity of the coordinates of $$\omega$$ ensures that $$\In_\omega(f)$$ is well defined.) Moreover, $$f$$ has an expression of the form $$f = \sum_i f_ig_i$$ such that
1. $$\nu_\preceq(f) = \min_\preceq\{\nu_\preceq(f_ig_i)\},$$ and
2. $$\omega(f) = \min\{\omega(f_ig_i)\}.$$

Proof. It is straightforward to check that the first two assertions are true for the first step of the division algorithm, and $$\omega(f_1) \geq \omega(f)$$. Now substitute $$f$$ by $$f_1$$ and repeat to see that the first two assertions hold in general. It remains to prove the third assertion. Since $$f \in I,$$ and the initial forms the $$g_i$$ generate the inital ideal of $$I$$, by the division algorithm $$f$$ has an expression of the form $f = \sum_i f_ig_i$such that $$\nu_\preceq(f) = \min_\preceq\{\nu_\preceq(f_ig_i)\},$$ i.e. property 3.1 of Theorem 2 is satisfied. Assume property 3.2 is not satisfied. Then there must be a cancellation of the form $\sum_j \In_\omega(f_{i_j})\In_\omega(g_{i_j}) = 0$ where the sum is over all $$j$$ such that $$\omega(f_{i_j}) + \omega(g_{i_j})$$ is the smallest. We claim that $\nu_\preceq(f) \prec \nu_\preceq(f_{i_j}g_{i_j})$for each $$j$$ (where “$$\prec$$” denotes “strictly smaller with respect to $$\preceq$$”). Indeed, by Theorem 1, there is only one $$i$$ such that $$f_ig_i$$ has a monomial term with exponent $$\nu_\preceq(f)$$, so that this term can not cancel with any other monomial term in the support of $$f_kg_k$$ for $$k \neq i,$$ proving the claim. Now write $f = \sum_{i \neq i_j}f_ig_i + \sum_j (f_{i_j} – \In_\omega(f_{i,j}))g_{i_j} + f’$where $$f’ := \sum_j \In_\omega (f_{i_j})g_{i_j}.$$ Since the initial terms of the $$g_{i_j}$$ with respect to $$\omega$$ and $$\preceq$$ are “compatible”, and since $$\sum_j \In_\omega(f_{i_j})\In_\omega(g_{i_j}) = 0$$, it follows that $\nu_\preceq(f’) \succ \nu_\preceq (f_{i_j} g_{i_j})$for each $$j$$. Note in addition that $\nu_\preceq(f’) \succ \nu_\preceq(f)$ due to the above claim. Since $$f’$$ is in the ideal generated by the $$g_i$$, we can write $$f’ = \sum_i f’_ig_i,$$ where the $$f’_i$$ are the quotients produced by the division algorithm. It follows that $f = \sum_{i \neq i_j}f_ig_i + \sum_j (f_{i_j} – \In_\omega(f_{i,j}))g_{i_j} + \sum_i f’_ig_i$This suggests a double induction to track the change in this expression for $$f$$ in comparison to the original expression $$f = \sum_i f_ig_i$$ as follows: given $$h = (h_1, \ldots, h_N)$$ such that $$f = \sum_i h_ig_i$$, define $m(h) := \min_i\{\omega(h_ig_i)\}$and$\alpha(h) := \min_\preceq\{\nu_\preceq(\In_\omega(h_ig_i)): \omega(h_ig_i) = m(h)\}$Our discussion above implies that if property 3.2 is not satisfied, then starting from an expression of $$f$$ satisfying property 3.1, the value for the pair $$(m, \alpha)$$ can be increased (where the ordering on the pair is initially by $$m$$ and then by $$\preceq$$ on $$\alpha$$) while ensuring that property 3.1 remains true. Since each coordinate of $$\omega$$ is positive, for each value of $$m$$, the space of $$\omega$$-homogeneous elements of $$\omega$$-order (or degree) $$m$$ is finite dimensional, and therefore due to Lemma 1, it is not possible for only $$\alpha$$ to increase while keeping $$m$$ unchanged. Consequently at some point we must have an expression $$f = \sum_i h_ig_i$$ such that $$m(h) = \omega(f),$$ as required to complete the proof.

## (An adaptation of) Buchberger’s algorithm

Given two nonzero monomial terms $$ax^\alpha, bx^\beta$$, we define their lowest common multiple as $\lcm(ax^\alpha, bx^\beta) := x^{\max(\alpha, \beta)}$where the maximum is taken componentwise. Note that the coefficient of the lowest common divisor is by definition $$1$$, regardless of the coefficients of the original monomials. Buchberger’s algorithm for computing Gröbner bases of polynomial ideals adapts easily to the computation of initial ideals in the ring of power series (note that this “algorithm” is not really finite, since the division algorithm is defined only as the limit of an infinite process. For truly finite algorithms one needs something like Mora’s algorithm):

Input: a monomial order $$\preceq$$ and a finite ordered collection $$g_1, \ldots, g_s$$ of nonzero elements in $$\hat R$$. Denote the ideal generated by $$g_1, \ldots, g_s$$ in $$\hat R$$ by $$I$$.

Output: a finite ordered collection $$\scrB$$ of nonzero elements in $$I$$ whose initial terms generate $$\In_\preceq(I)$$.

Procedure:

1. Set $$\scrB_0 := (g_1, \ldots, g_s)$$.
2. Assuming $$\scrB_k = (h_1, \ldots, h_{s_k})$$ has been computed, compute $$\scrB_{k+1}$$ as follows: for each $$i, j$$, $$1 \leq i < j \leq k$$,
• Define $S(h_i, h_j) := \frac{\lcm(\In_\preceq(h_i), \In_\preceq(h_j))}{\In_\preceq(h_i)}h_i – \frac{\lcm(\In_\preceq(h_i), \In_\preceq(h_j))}{\In_\preceq(h_j)}h_j$
• Divide each $$S(h_i, h_j)$$ by $$\scrB_k$$. Define $$\scrB_{k+1}$$ to be the union of $$\scrB_k$$ and the set of all nonzero remainders of $$S(h_i, h_j)$$ by $$\scrB_k$$.
3. Repeat until you get $$\scrB_{k+1} = \scrB_k$$. Then $$\scrB := \scrB_k$$ is the desired output.

Theorem 4. The above algorithm stops in finitely many steps and the output is a finite collections of elements of $$I$$ whose initial terms generate $$\In_\preceq(I)$$.

Proof. Since we start with elements in $$I$$, it is clear that all new elements added to the original list are also from $$I$$. The process also stops in finitely many steps, since whenever a new element is added to the list, the ideal generated by their initial terms gets larger (due to Theorem 1), and the Noetherianity of $$\hat R$$ precludes infinite strictly increasing chains of ideals. It remains to show that $$(\In_\preceq(g): g \in \scrB)$$ generate $$\In_\preceq(I)$$. Enumerate the elements in $$\scrB$$ by $$g_1, \ldots, g_N.$$ We may assume without loss of generality that the coefficient of $$\In_\preceq(g_i)$$ is $$1$$, i.e. $$\In_\preceq(g_i)$$ is of the form $$x^{\alpha_i}$$. Pick $$f \in I.$$ Since the $$g_i$$ generate $$I$$, there is an expression $$f = \sum_i f_ig_i$$ with $$f_i \in \hat R.$$ Due to Theorem 3 there is $$\omega \in \znpos$$ such that $$\In_\omega(f) = \In_\preceq(f)$$ and $$\In_\omega(g_i) = \In_\preceq(g_i)$$ for each $$i$$. Define the pair $$(m, \alpha)$$ as in the proof of Lemma 3, i.e. $m(f_1, \ldots, f_N) := \min_i\{\omega(f_ig_i)\}$and$\alpha(f_1, \ldots, f_N) := \min_\preceq\{\nu_\preceq(\In_\omega(f_ig_i)): \omega(f_ig_i) = m(f_1, \ldots, f_N)\}$If $$m(f_1, \ldots, f_N) = \omega(f)$$, then it would follow that $$\In_\preceq(f) = \In_\omega(f)$$ is a sum of the form $$\sum_j \In_\omega(f_{i_j})\In_\omega(g_{i_j}) = \sum_j \In_\omega(f_{i_j})\In_\preceq(g_{i_j})$$ and therefore would be in the ideal generated by the $$\In_\preceq(g_i)$$. So assume $m(f_1, \ldots, f_N) < \omega(f)$Then there must be a cancellation of the form $\sum_j \In_\omega(f_{i_j})\In_\omega(g_{i_j}) = \sum_j \In_\omega(f_{i_j})\In_\preceq(g_{i_j}) = 0$ where the sum is over all $$j$$ such that $$\omega(f_{i_j}) + \omega(g_{i_j}) = m(f_1, \ldots, f_N).$$ It follows that $\sum_k \In_\preceq(\In_\omega(f_{i_{j,k}})\In_\preceq (g_{i_{j,k}})) = 0$ where the sum is over all $$k$$ such that $$\nu_\preceq(f_{i_{j,k}}g_{i_{j,k}}) = \alpha(f_1, \ldots, f_N) =: \alpha.$$ This implies that $$\In_\preceq(\In_\omega(f_{i_{j,k}})) = b_{i_{j,k}}x^{\alpha – \alpha_{i_{j,k}}}$$ with $$\sum_k b_{i_{j,k}} = 0.$$ Write $f = \sum_{i \neq i_j}f_ig_i + \sum_j (f_{i_j} – \In_\omega(f_{i,j}))g_{i_j} + f’_1 + f’_2$where $f’_1 := \sum_{i_j \neq i_{j,k}} \In_\omega(f_{i,j}) g_{i_j} + \sum_k (\In_\omega(f_{i_{j,k}}) – \In_\preceq(\In_\omega(f_{i_{j,k}})))g_{i_{j,k}}$and $f’_2 := \sum_k \In_\preceq(\In_\omega (f_{i_{j,k}})) g_{i_{j,k}}$Since $$b_{i_{j,1}} = -\sum_{k > 1} b_{i_{j,k}},$$ it follows that $f’_2 = \sum_k b_{i_{j,k}}x^{\alpha – \alpha_{i_{j,k}}}g_{i_{j,k}} = \sum_{k> 1} b_{i_{j,k}} (x^{\alpha – \alpha_{i_{j,k}}}g_{i_{j,k}} – x^{\alpha – \alpha_{i_{j,1}}}g_{i_{j,1}}) = \sum_{k > 1} b_{i_{j,k}}x^{\alpha – \beta_{i_{j,k}}}S(g_{i_{j,k}}, g_{i_{j,1}})$where $$x^{\beta_{i_{j,k}}}:= \lcm(x^{\alpha_{i_{j,k}}}, x^{\alpha_{i_{j,1}}}).$$ Due to Buchberger’s algorithm and Theorem 1, whenever $$S(g_{i_{j,k}}, g_{i_{j,1}})$$ is nonzero, it can be expressed as $$\sum_i h_ig_i$$ such that $\min_i(\nu_\preceq(h_ig_i)) = \nu_\preceq(S(g_{i_{j,k}}, g_{i_{j,1}}))$It is clear by construction of $$S(\cdot, \cdot)$$ that $\nu_\preceq (x^{\alpha- \beta_{i_{j,k}}}S(g_{i_{j,k}}, g_{i_{j,1}})) \succ \alpha$It follows that $$f$$ can be expressed as $$\sum_i \tilde f_i g_i$$ such that

• either $$m(\tilde f_1, \ldots, \tilde f_N) > m(f_1, \ldots, f_N)$$,
• or $$m(\tilde f_1, \ldots, \tilde f_N) = m(f_1, \ldots, f_N)$$ and $$\alpha(\tilde f_1, \ldots, \tilde f_N) > \alpha(f_1, \ldots, f_N).$$

To summarize: as long as $$m(f_1, \ldots, f_N) < \omega(f)$$, it is possible to find another expression $$f = \sum_i \tilde f_i g_i$$ such that the value for the pair $$(m, \alpha)$$ increases (where the ordering on the pair is initially by $$m$$ and then by $$\preceq$$ on $$\alpha$$). Since each coordinate of $$\omega$$ is positive, for each value of $$m$$, the space of $$\omega$$-homogeneous elements of $$\omega$$-order (or degree) $$m$$ is finite dimensional, and therefore due to Lemma 1, it is not possible for only $$\alpha$$ to increase while keeping $$m$$ unchanged. Consequently at some point we must arrive at an expression $$f = \sum_i h_ig_i$$ such that $$m(h_1, \ldots, h_N) = \omega(f),$$ which implies that $$\In_\preceq(f) = \In_\omega(f)$$ is in the ideal generated by the $$\In_\omega(g_i) = \In_\preceq(g_i),$$ $$i = 1, \ldots, N,$$ and completes the proof.

# 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

1. $$\preceq$$ is a total order,
2. $$\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
3. $$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:

1. 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)$$.
2. 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)$$.
3. 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

1. no monomial term of any basis element is divisible by the leading term of any other basis element, and
2. 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,

1. up to a permutation of the basis elements there is a unique reduced Gröbner basis for every monomial order, and
2. 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

1. $$\delta_\preceq(f) = \max_\preceq\{\delta_\preceq(f_ig_i)\},$$ and
2. $$\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.

# Lüroth’s theorem (a “constructive” proof)

Lüroth’s theorem (Lüroth 1876 for $$k = \mathbb{C}$$, Steinitz 1910 in general). If $$k \subseteq K$$ are fields such that $$k \subseteq K \subseteq k(x)$$, where $$x$$ is an indeterminate over $$k$$, then $$K = k(g)$$ for some rational function $$g$$ of $$x$$ over $$k$$.

I am going to present a “constructive” proof of Lüroth’s theorem due to Netto (1895) that I learned from Schinzel’s Selected Topics on Polynomials (and give some applications to criteria for proper polynomial parametrizations). The proof uses the following result which I am not going to prove here:

Proposition (with the set up of Lüroth’s theorem). $$K$$ is finitely generated over $$k$$, i.e. there are finitely many rational functions $$g_1, \ldots, g_s \in k(x)$$ such that $$K = k(g_1, \ldots, g_s)$$.

The proof is constructive in the following sense: given $$g_1, \ldots, g_s$$ as in the proposition, it gives an algorithm to determine $$g$$ such that $$K = k(g)$$. We use the following notation in the proof: given a rational function $$h \in k(x)$$, if $$h = h_1/h_2$$ with polynomials $$h_1, h_2 \in k[x]$$ with $$\gcd(h_1, h_2) = 1$$, then we define $$\deg_\max(h) := \max\{\deg(h_1), \deg(h_2)\}$$.

## Proof of Lüroth’s theorem

It suffices to consider the case that $$K \neq k$$. Pick $$g_1, \ldots, g_s$$ as in the proposition. Write $$g_i = F_i/G_i$$, where

• $$\gcd(F_i, G_i) = 1$$ (Property 1).

Without loss of generality (i.e. discarding $$g_i \in k$$ or replacing $$g_i$$ by $$1/(g_i + a_i)$$ for appropriate $$a_i \in k$$ if necessary) we can also ensure that

• $$\deg(F_i) > 0$$ and $$\deg(F_i) > \deg(G_i)$$ (Property 2).

Consider the polynomials $H_i := F_i(t) – g_iG_i(t) \in K[t] \subset k(x)[t], i = 1, \ldots, s,$ where $$t$$ is a new indeterminate. Let $$H$$ be the greatest common divisor of $$H_1, \ldots, H_s$$ in $$k(x)[t]$$ which is also monic in $$t$$. Since the Euclidean algorithm for computing $$\gcd$$ respects the field of definition, it follows that:

• $$H$$ is also the greatest common divisor of $$H_1, \ldots, H_s$$ in $$K[t]$$, which means, if $$H = \sum_j h_j t^j$$, then each $$h_j \in K$$ (Property 3).

Let $$H^* \in k[x,t]$$ be the polynomial obtained by “clearing the denominator” of $$H$$; in other words, $$H = H^*/h(x)$$ for some polynomial $$h \in k[x]$$ and $$H^*$$ is primitive as a polynomial in $$t$$ (i.e. the greatest common divisor in $$k[x]$$ of the coefficients in $$H^*$$ of powers of $$t$$ is 1). By Gauss’s lemma, $$H^*$$ divides $$H^*_i := F_i(t)G_i(x) – F_i(x)G_i(t)$$ in $$k[x,t]$$, i.e. there is $$Q_i \in k[x,t]$$ such that $$H^*_i = H^* Q_i$$.

Claim 1. If $$\deg_t(H^*) < \deg_t(H^*_i)$$, then $$\deg_x(Q_i) > 0$$.

Proof of Claim 1. Assume $$\deg_t(H^*) < \deg_t(H^*_i)$$. Then $$\deg_t(Q_i) > 1$$. If in addition $$\deg_x(Q_i) = 0$$, then we can write $$Q_i(t)$$ for $$Q_i$$. Let $$F_i(t) \equiv \tilde F_i(t) \mod Q_i(t)$$ and $$G_i(t) \equiv \tilde G_i(t) \mod Q_i(t)$$ with $$\deg(\tilde F_i) < \deg(Q_i)$$ and $$\deg(\tilde G_i) < \deg(Q_i)$$. Then $$\tilde F_i(t)G_i(x) – F_i(x) \tilde G_i(t) \equiv 0 \mod Q_i(t)$$. Comparing degrees in $$t$$, we have $$\tilde F_i(t)G_i(x) = F_i(x) \tilde G_i(t)$$. It is straightforward to check that this contradicts Propeties1 and 2 above, and completes the proof of Claim 1.

Let $$m := \min\{\deg_\max(g_i): i = 1, \ldots, s\}$$, and pick $$i$$ such that $$\deg_\max(g_i) = m$$. Property 2 above implies that $$\deg_t(H^*_i) = \deg_x(H^*_i) = m$$. If $$\deg_t(H^*) < m$$, then Claim 1 implies that $$\deg_x(H^*) < \deg_x(H^*_i) = m$$. If the $$h_j$$ are as in Property 3 above, it follows that $$\deg_\max(h_j) < m$$ for each $$j$$. Since $$H^* \not\in k[t]$$ (e.g. since $$t-x$$ divides each $$H_i$$), there must be at least one $$h_j \not \in k$$. Since adding that $$h_j$$ to the list of the $$g_i$$ decreases the value of $$m$$, it follows that the following algorithm must stop:

### Algorithm

• Step 1: Pick $$g_i := F_i/G_i$$, $$i = 1, \ldots, s$$, satisfying properties 1 and 2 above.
• Step 2: Compute the monic (with respect to $$t$$) $$\gcd$$ of $$F_i(t) – g_i G_i(t)$$, $$i = 1, \ldots, s$$, in $$k(x)[t]$$; call it $$H$$.
• Step 3: Write $$H = \sum_j h_j(x) t^j$$. Then each $$h_j \in k(g_1, \ldots, g_s)$$. If $$\deg_t(H) < \min\{\deg_\max(g_i): i = 1, \ldots, s\}$$, then adjoin all (or, at least one) of the $$h_j$$ such that $$h_j \not\in k$$ to the list of the $$g_i$$ (possibly after an appropriate transformation to ensure Property 2), and repeat.

After the last step of the algorithm, $$H$$ must be one of the $$H_i$$, in other words, there is $$\nu$$ such that $\gcd(F_i(t) – g_i G_i(t): i = 1, \ldots, s) = F_{\nu}(t) – g_{\nu}G_{\nu}(t).$

Claim 2. $$K = k(g_{\nu})$$.

Proof of Claim 2 (and last step of the proof of Lüroth’s theorem). For a given $$i$$, polynomial division in $$k(g_\nu)[t]$$ gives $$P, Q \in k(g_\nu)[t]$$ such that $F_i(t) = (F_{\nu}(t) – g_{\nu}G_{\nu}(t))P + Q,$ where $$\deg_t(Q) < \deg_t(F_{\nu}(t) – g_{\nu}G_{\nu}(t))$$. If $$Q = 0$$, then $$F_i(t) = (F_{\nu}(t) – g_{\nu}G_{\nu}(t))P$$, and clearing out the denominator (with respect to $$k[g_\nu]$$) of $$P$$ gives an identity of the form $$F_i(t)p(g_\nu) = (F_{\nu}(t) – g_{\nu}G_{\nu}(t))P^* \in k[g_\nu, t]$$ which is impossible, since $$F_{\nu}(t) – g_{\nu}G_{\nu}(t)$$ does not factor in $$k[g_\nu, t]$$. Therefore $$Q \neq 0$$. Similarly, $G_i(t) = (F_{\nu}(t) – g_{\nu}G_{\nu}(t))R + S,$ where $$R, S \in k(g_\nu)[t]$$, $$S \neq 0$$, and $$\deg_t(S) < \deg_t(F_{\nu}(t) – g_{\nu}G_{\nu}(t))$$. It follows that $F_i(t) – g_iG_i(t) = (F_{\nu}(t) – g_{\nu}G_{\nu}(t))(P – g_iR) + Q – g_iS.$ Since $$F_{\nu}(t) – g_{\nu}G_{\nu}(t)$$ divides $$F_{i}(t) – g_{i}G_{i}(t)$$ in $$k(x)[t]$$ and since $$\deg_t(Q – g_iS) < \deg_t(F_{\nu}(t) – g_{\nu}G_{\nu}(t))$$, it follows that $$Q = g_iS$$. Taking the leading coefficients (with respect to $$t$$) $$q_0, s_0 \in k(g_\nu)$$ of $$Q$$ and $$S$$ gives that $$g_i = q_0/s_0 \in k(g_\nu)$$, as required to complete the proof.

## Applications

The following question seems to be interesting (geometrically, it asks when a given polynomial parametrization of a rational affine plane curve is proper).

Question 1. Let $$k$$ be a field and $$x$$ be an indeterminate over $$k$$ and $$g_1, g_2 \in k[x]$$. When is $$k(g_1, g_2) = k(x)$$?

We now give a sufficient condition for the equality in Question 1. Note that the proof is elementary: it does not use Lüroth’s theorem, only follows the steps of the above proof in a special case.

Corollary 1. In the set up of Question 1, let $$d_i := \deg(g_i)$$, $$i = 1, 2$$. If the $$\gcd$$ of $$x^{d_1} – 1, x^{d_2} – 1$$ in $$k[x]$$ is $$x – 1$$, then $k(g_1, g_2) = k(t)$. In particular, if $$d_1, d_2$$ are relatively prime and the characteristic of $$k$$ is either zero or greater than both $$d_1, d_2$$, then $k(g_1, g_2) = k(x)$.

Remark. Corollary 1 is true without the restriction on characteristics, i.e. the following holds: “if $$d_1, d_2$$ are relatively prime, then $k(g_1, g_2) = k(x)$.” François Brunault (in a comment to one of my questions on MathOverflow) provided the following simple one line proof: $$[k(x): k(g_1, g_2)]$$ divides both $$[k(x): k(g_i)] = d_i$$, and therefore must be $$1$$.

My original proof of Corollary 1. Following the algorithm from the above proof of Lüroth’s theorem, let $$H_i := g_i(t) – g_i(x)$$, $$i = 1, 2$$, and $$H \in k(x)[t]$$ be the monic (with respect to $$t$$) greatest common divisor of $$H_1, H_2$$.

Claim 1.1. $$H = t – x$$.

Proof. It is clear that $$t-x$$ divides $$H$$ in $$k(x)[t]$$, so that $$H(x,t) = (t-x)h_1(x,t)/h_2(x)$$ for some $$h_1(x,t) \in k[x,t]$$ and $$h_2(x) \in k[x]$$. It follows that there is $$Q_i(x,t) \in k[x,t]$$ and $$P_i(x) \in k[x]$$ such that $$H_i(x,t)P_i(x)h_2(x) = (t-x)h_1(x,t)Q_i(x,t)$$. Since $$h_2(x)$$ and $$(t-x)h_1(x,t)$$ have no common factor, it follows that $$h_2(x)$$ divides $$Q_i(x,t)$$, and after cancelling $$h_2(x)$$ from both sides, one can write $H_i(x,t)P_i(x) = (t-x)h_1(x,t)Q’_i(x,t),\ i = 1, 2.$ Taking the leading form of both sides with respect to the usual degree on $$k[x,t]$$, we have that $(t^{d_i} – x^{d_i})x^{p_i} = a_i(t-x)\mathrm{ld}(h_1)\mathrm{ld}(Q’_i)$ where $$a_i \in k \setminus \{0\}$$ and $$\mathrm{ld}(\cdot)$$ is the leading form with respect to the usual degree on $$k[x,t]$$. Since $$\gcd(x^{d_1} – 1, x^{d_2} – 1) = x – 1$$, it follows that $$\mathrm{ld}(h_1)$$ does not have any factor common with $$t^{d_i} – x^{d_i}$$, and consequently, $$t^{d_i} – x^{d_i}$$ divides $$(t-x)\mathrm{ld}(Q’_i)$$. In particular, $$\deg_t(Q’_i) = d_i – 1$$. But then $$\deg_t(h_1) = 0$$. Since $$H = (t-x)h_1(x)/h_2(x)$$ is monic in $$t$$, it follows that $$H = t – x$$, which proves Claim 1.1.

Since both $$H_i$$ are elements of $$k(g_1, g_2)[t]$$, and since the Euclidean algorithm to compute $$\gcd$$ of polynomials (in a single variable over a field) preserves the field of definition, it follows that $$H \in k(g_1, g_2)[t]$$ as well (this is precisely the observation of Property 3 from the above proof of Lüroth’s theorem). Consequently $$x \in k(g_1, g_2)$$, as required to prove Corollary 1.

## References

• Andrzej Schinzel, Selected Topics on Polynomials, The University of Michigan Press, 1982.

# Publications

## Overview

Starting from my PhD thesis Towards a Bezout-type Theory of Affine Varieties written at University of Toronto under the supervision of Pierre Milman, my research in math falls under two broad themes:

• Compactification of affine varieties
• Affine Bézout problem

I am in particular interested in one of the simplest cases of the first problem:

• Compactification of $\mathbb{C}^2$

## Papers

### Compactification of $\mathbb{C}^2$

#### Preprints

• Normal equivariant compactifications of $\mathbb{G}^2_a$ of Picard rank one, arXiv:1610.03563.
• Mori dream surfaces associated with curves with one place at infinity, arXiv:1312.2168.
• Analytic compactifications of $\mathbb{C}^2$ part II – one irreducible curve at infinity, arXiv:1307.5577.

### Affine Bézout problem

#### Preprints

• Intersection multiplicity, Milnor number and Bernstein’s theorem, arXiv:1607.04860

# Simplest singularity on non-algebraic normal Moishezon surfaces

A classical question in complex analytic geometry is to understand when a given analytic space is algebraic (i.e. analytiﬁcation of an algebraic scheme). A necessary condition for this to hold is that the transcendence degree of the ﬁeld of global meromorphic functions must be equal to the dimension of the space, i.e. the space has to be Moishezon. For dimension 2, it is a classical result that it is also suﬃcient, provided the space is nonsingular (Chow and Kodaira, 1952).

In general it is not clear how to determine algebraicity of normal (singular) Moishezon surfaces and our understanding of non-algebraic Moishezon surfaces, more precisely what prevents them from being algebraic, remains incomplete (Schröer [Sch00] gives a necessary and suﬃcient for algebraicity, but it is not very suitable for computation in a given case). We [Mon16] gave an example of a non-algebraic normal Moishezon surface $$X$$ which has the simplest possible singularity in the following sense: $$X$$ has only one singular point $$P$$, and the singularity at $$P$$

1. has multiplicity 2 and geometric genus 1,
2. is almost rational in the sense of [Ném07], and
3. is a Gorenstein hypersurface singularity which is minimally elliptic (in the sense of [Lau77]).

The claim that singularity of $$X$$ is the simplest possible is based on combining the preceding facts with the following observations:

• a Moishezon surface whose singularities are rational (i.e. with geometric genus zero) is algebraic [Art62], and
• minimally elliptic Gorenstein singularities form in a sense the simplest class of non-rational singularities.

The weighted dual graph of the resolution of singularity of $$X$$ at $$P$$ is of type $$D_{9,∗,0}$$ in the classiﬁcation of [Lau77] and the self-intersection number of its fundamental divisor is −2. It follows from [Lau77, Table 2] that the singularity at the origin of $$z^2 = x^5 + xy^5$$ is also of the same type.

## References

• [Art62] Michael Artin, Some numerical criteria for contractability of curves on algebraic surfaces, Amer. J. Math., 84:485–496,
• [Lau77] Henry B. Laufer, On minimally elliptic singularities, Amer. J. Math., 99(6):1257–1295, 1977.
• [Mon16] Pinaki Mondal, Algebraicity of normal analytic compactiﬁcations of $$\mathbb{C}^2$$ with one irreducible curve at inﬁnity, Algebra & Number Theory, 10(8), 2016.
• [Ném07] András Némethi, Graded roots and singularities, In Singularities in geometry and topology, pages 394–463. World Sci. Publ., Hackensack, NJ, 2007.
• [Sch00] Stefan Schröer, On contractible curves on normal surfaces, J. Reine Angew. Math., 524:1–15, 2000.