$\DeclareMathOperator{\gr}{gr} \DeclareMathOperator{\In}{In} \DeclareMathOperator{\Inn}{\overline{In}} \DeclareMathOperator{\Incoeff}{In_coeff} \DeclareMathOperator{\Inexp}{In_exp} \DeclareMathOperator{\ld}{Ld} \newcommand{\qq}{\mathbb{Q}} \newcommand{\kk}{\mathbb{K}} \DeclareMathOperator{\ord}{ord} \newcommand{\preceqeq}{\preceq_{\equiv}} \newcommand{\rnpos}{\mathbb{R}^n_{> 0}} \newcommand{\rnzero}{\mathbb{R}^n_{\geq 0}} \newcommand{\rr}{\mathbb{R}} \newcommand{\scrB}{\mathcal{B}} \newcommand{\scrK}{\mathcal{K}} \newcommand{\scrM}{\mathcal{M}} \DeclareMathOperator{\supp}{Supp} \newcommand{\znplusonezero}{\mathbb{Z}^{n+1}_{\geq 0}} \newcommand{\znplusonepos}{\mathbb{Z}^{n+1}_{> 0}} \newcommand{\znpos}{\mathbb{Z}^n_{> 0}} \newcommand{\znzero}{\mathbb{Z}^n_{\geq 0}} \newcommand{\zz}{\mathbb{Z}}$
In this post we continue the discussion of polynomial division over valued fields from where we left at Part I. We keep the numberings of the environments (example, theorem, corollary etc) as in Part 1 (e.g. we start here with Example 2 below, since Part I had an example labeled Example 1). The goal of this post is to get to stronger versions of the “Universal Basis Theorem” (Theorem 2) from Part I, in which we prove existence of universal bases for wider collections of preorders (i.e. reflexive and transitive binary relations) and not necessarily homogeneous ideals. First we revisit the notion of almost linear monomial orders.

Almost linearity vs valuation on $\kk$

Let $\preceq$ be an almost linear monomial order on $\scrM := \{ax^\alpha: a \in \kk \setminus \{0\},$ $\alpha := (\alpha_1, \ldots, \alpha_n)$ $\in \znzero\}.$ We have seen that $\preceq$ restricts to a total binary relation on $\kk,$ and it is straightforward to check that $\preceqeq$ is an equivalence relation on $\kk$. Let $[\kk]$ be the set of equivalence classes of $\preceqeq$.

Proposition 1. $[\kk \setminus \{0\}]$ is a totally ordered abelian group with identity $[1]$ and addition given by $[a] + [b] := [ab]$. Moreover, the map $a \mapsto [a]$ is a valuation.

Proof. Indeed, it is easy to check that the addition is well defined, and $-[a] = [a^{-1}]$ with respect to this product, and it makes $[\kk \setminus \{0\}]$ an abelian group with identity $[1]$. Now $\preceq$ induces an order on $[\kk \setminus \{0\}]$ defined as follows: $[a] \preceq [b]$ if and only if $a \preceq b$. It is then clear that $\preceq$ is well defined, and it is a total binary relation which is reflexive, transitive, and anti-symmetric; in other words, $\preceq$ induces a total order on $[\kk \setminus \{0\}]$. This proves the first assertion. That $[\cdot]$ is a valuation on $\kk \setminus \{0\}$ follows from the definition of the addition on $[\kk \setminus \{0\}]$ and the defining Property 3 of almost linear monomial orders.

Linear monomial preorders

A linear monomial preorder $\leq$ on $\scrM := \{ax^\alpha: a \in \kk \setminus \{0\},\ \alpha := (\alpha_1, \ldots, \alpha_n) \in \znzero\}$ is a binary relation on $\scrM$ which satisfies all properties of an almost linear monomial order except for the following: it is allowed to be a linear preorder (instead of a linear order) on all monomials with different exponents. More precisely, it satisfies the following properties:

1. $\leq$ is reflexive and transitive,
2. $\leq$ is linear, i.e. for any two elements $a_1x^{\alpha_1}, a_2x^{\alpha_2} \in \scrM$, either $a_1x^{\alpha_1} \leq a_2x^{\alpha_2}$, or $a_2x^{\alpha_2} \leq a_1x^{\alpha_1}$, or $a_1x^{\alpha_1} \leq a_2x^{\alpha_2} \leq a_1x^{\alpha_1}$.
3. if $ax^\alpha \leq bx^\beta,$ then $acx^{\alpha+\gamma} \leq bcx^{\beta+\gamma}$ for all $c \in \kk\setminus\{0\}$ and $\gamma \in \znzero,$
4. $\leq$ restricts to a valuation on $\kk \setminus \{0\}$.

The strict variant $\lt$ of $\leq$ is defined as follows: $a_1x^{\alpha_1} \lt a_2x^{\alpha_2}$ if and only if $a_1x^{\alpha_1} \leq a_2x^{\alpha_2}$ and $a_2x^{\alpha_2} \not\leq a_1x^{\alpha_1}.$

Example 2. Property 3, i.e. compatibility with the product of monomials, may not be true for the strict variant $\lt$. Indeed, in the case that $n = 1$, consider the binary relation $\lt$ on $\scrM$ such that $\lt$ is trivial on $\kk$, and $1 \lt x \leq x^2$, and $x^2 \leq x$ (which implies that $\lt$ is an equivalence relation on $x^k$, $k \geq 1$). Then $\lt$ is a linear monomial preorder, and $1 \lt x$, but $x \not\lt x^2$.

The notions of initial and leading monomial forms make sense for a linear monomial preorder $\leq$: for $f = \sum_\alpha a_\alpha x^\alpha$, $\In_\leq(f)$ is simply the sum of all $a_\alpha x^{\alpha}$ such that $a_\alpha x^{\alpha} = \min_{\alpha’} \{a_{\alpha’}x^{\alpha’}\}$. The initial or leading forms corresponding to linear monomial preorders generalize the initial or leading forms corresponding to totally ordered gradings introduced in the previous post.

Example 2 motivates the following definition: a linear strictly monomial preorder $\leq$ is a linear monomial preorder whose strict variant $\lt$ is compatible with the product of monomials, i.e. which satisfies the following property:

• if $ax^\alpha \lt bx^\beta,$ then $acx^{\alpha+\gamma} \lt bcx^{\beta+\gamma}$ for all $c \in \kk\setminus\{0\}$ and $\gamma \in \znzero$,
• or equivalently, $\In_{\leq} (cx^{\gamma}f) = cx^{\gamma} \In_{\leq}(f)$ for all $f \in \kk[x_1, \ldots, x_n]$, $c \in \kk\setminus\{0\}$ and $\gamma \in \znzero$.

Example 3. It may not be true that $\In_{\leq} (fg) = \In_{\leq}(f) \In_{\leq}(g).$ Indeed, consider the $p$-adic valuation $\nu_p$ on $\qq$ from Example 1. Let $\leq_p$ be the preorder on $\qq[x,y]$ which trivially extends (the preorder on $\kk$ induced by) $\nu_p$; more precisely, $ax^\alpha y^\beta \leq_p a’x^{\alpha’}y^{\beta’}$ if and only if $\nu_p(a) \leq \nu_p(b)$. If $f = x+y$ and $g := x + (p-1)y$, then $\In_{\leq_p}(f) = f$ and $\In_{\leq_p}(g) = g$. However, $fg = x^2 + pxy + (p-1)y^2$, so that
\[\In_{\leq_p}(fg) = x^2 + (p-1)y^2 \neq fg = \In_{\leq_p}(f)\In_{\leq_p}(g)\]

The above example shows that a straightforward analogue of Theorem 1* from the preceding post is not true in general. In particular, let $\preceq$ be an almost linear monomial order and $\preceq_p$ be the “refinement” of $\leq_p$ by $\preceq$ (as described in the preceding post). If $I$ is the principal ideal of $\qq[x,y]$ generated by $f$, then $\In_{\preceq_p}(f)$ generates $\In_{\preceq_p}(I)$. However, $\In_{\leq_p}(f)$ does not generate $\In_{\leq_p}(I)$. This shows that one needs to consider the initial ideal in some sort of a graded ring corresponding to the valuation on $\kk$.

Monomial (decreasing) filtrations

A decreasing filtration on a ring $R$ by a totally ordered group $\Sigma$ (or in short, a $\Sigma$-filtration) is a family $(R_\sigma)_{\sigma \in \Sigma}$ of additive subgroups of $R$ indexed by $\Sigma$ such that

• $R = \bigcup_{\sigma \in \Sigma} R_\sigma$
• for each $\sigma,\tau \in \Sigma$,
  • $R_\sigma \supseteq R_\tau$ whenever $\sigma \leq \tau$,
  • if $f \in R_\sigma$ and $g \in R_\tau$, then $fg \in R_{\sigma\tau}$.

The graded ring corresponding to the filtration is
\[\gr R := \oplus_\sigma \bar R_\sigma\]
where
\[\bar R_\sigma := R_\sigma/(\bigcup_{\tau > \sigma} R_\tau)\]
It is clear that $\gr R$ is a graded ring in the usual sense (as described e.g. in the preceding post). Let $f \in R$. If $f \in R_\sigma$, then we write $(f)_\sigma$ for the image of $f$ in the degree $\sigma$ component of $\gr R.$ The order of $f$ with respect to $\Sigma$, denoted $\ord_\Sigma(f)$, is the supremum over all $\sigma \in \Sigma$ such that $f \in R_\sigma$. The initial form of $f$ with respect to $\Sigma$ is
\[
\Inn(f) :=
\begin{cases}
0 &\text{if}\ \ord_\Sigma(f)\ \text{does not exist}, \\
(f)_\mu & \text{if}\ \mu = \ord_\Sigma(f) \in \Sigma
\end{cases}
\]
For an ideal $I$ of $R$, we write $\Inn(I)$ for the ideal in $\gr R$ generated by $\Inn(f)$ for all $f \in I$.

The filtration defines a preorder (i.e. a reflexive and transitive binary relation) $\leq_\Sigma$ on $R$ defined as follows: $f \leq_\Sigma g$ if and only the following holds: for each $\sigma \in \Sigma$ such that $f \in R_\sigma$, there is $\tau \in \Sigma$, $\tau \geq \sigma$, such that $g \in R_\tau$.

Proposition 2. $\leq_\Sigma$ is a linear (or total) preorder on $R$. For each $f,g \in R$, either $f \leq_\Sigma (f+g)$ or $g \leq_\Sigma (f+g)$.

Proof. Indeed, assume $f \not{\leq}_\Sigma g$. Then there is $\sigma \in \Sigma$ such that $f \in R_\sigma$ such that for each $\tau \in \Sigma$ such that $g \in R_\tau$, we have $\sigma \not\leq \tau$. However, $\leq$ is a linear order on $\Sigma$, and therefore, for each such $\tau$, we have $\tau \leq \sigma$. This implies that $g \leq_\Sigma f$, and proves the first assertion. For the second assertion we may assume without loss of generality that $f \leq_\Sigma g$ (since $\leq_\Sigma$ is a total preorder). Then if $f \in R_\sigma$, then $g \in R_\sigma$ as well, so that $f+g \in R_\sigma$. Consequently, $f \leq_\Sigma (f+ g)$, as required.

Let $\equiv_\Sigma$ denote denote the “equivalence” relation induced by $\leq_\Sigma$, i.e. $f \equiv_\Sigma g$ if and only if $f \leq_\Sigma g \leq_\Sigma f.$

Proposition 3. Assume $R$ contains a field $\kk$ and the restriction of $\leq_\Sigma$ to $\kk$ is “compatible with multiplication” in the sense that for each $a,b,c \in \kk \setminus \{0\}$, if $a \leq_\Sigma b$, then $ac \leq_\Sigma bc$. Then

1. the map which sends $f \in R$ to its equivalence class $[f]$ with respect to $\equiv_\Sigma$ restricts to a valuation on $\kk$.
2. The valuation group is $[\kk] := \{[a]: a \in \kk \setminus \{0\}\}$ with the zero element $[1]$ and the addition defined by $[a] + [b] := [ab]$.

Proof. Follows from the second assertion of Proposition 2 combined with the arguments of the proof of Proposition 1.

The “strict” variant of $\leq_\Sigma$, denoted as $\lt_\Sigma$ is defined as follows: $f \lt_\Sigma g$ if and only if $f \leq_\Sigma g$ and $g \not{\leq}_\Sigma f$. Now consider the case that $R := \kk[x_1, \ldots, x_n]$, where $\kk$ is a field and the $x_i$ are indeterminates. We say that

• The filtration by $\Sigma$ is a monomial filtration if
  1. it is “defined by monomials”, i.e. for each $f \in R$ and $\sigma \in \Sigma$, $f \in R_\sigma$ if and only if each monomial term of $f$ is in $R_\sigma$,
  2. $\leq_\Sigma$ is compatible with the multiplication by monomials, i.e. if $f \leq_\Sigma g$, then $ax^\alpha f \leq_\Sigma ax^\alpha g$ for each $a \in \kk$ and $\alpha \in \znzero$.
• The filtration by $\Sigma$ is a strictly monomial filtration if it is a monomial filtration, and in addition $\lt_\Sigma$ is compatible with the multiplication by monomials, i.e. if $f \lt_\Sigma g$, then $ax^\alpha f \lt_\Sigma ax^\alpha g$ for each $a \in \kk$ and $\alpha \in \znzero$.

If $\Sigma$ is a monomial filtration on $R := \kk[x_1, \ldots, x_n]$, then one can define an “initial form” corresponding to $\Sigma$ in $R$ (i.e. not in $\gr R$) as follows: pick $f \in R$. If $\Inn(f) = 0$, then define
\[\In(f) := 0\]
Otherwise let $\sigma := \ord_\Sigma(f) \in \Sigma$. Let $f = \sum_j a_j x^{\alpha_j}$ be the decomposition of $f$ in its monomial terms. Since the filtration by $\Sigma$ is monomial, each $a_j x^{\alpha_j} \in R_\sigma$. We claim that there is $j$ such that $\ord_\Sigma(a_j x^{\alpha_j}) = \sigma$. Indeed, otherwise for each $j$, there is $\sigma_j \in \Sigma$, $\sigma_j \gt_\Sigma \sigma$, such that $a_j x^{\alpha_j} \in S_{\sigma_j}$. But then $\sigma \lt_\Sigma \min_{\leq_\Sigma} \sigma_j \leq_\Sigma \ord_\Sigma(f),$ which is a contradiction. This proves the claim. Consequently we may (and do) define
\[\In(f) := \sum_{\ord_\Sigma(a_j x^{\alpha_j}) = \ord_\Sigma(f)} a_j x^{\alpha_j}\]

Proposition 4. Let $\Sigma$ be a monomial filtration on $R:= \kk[x_1, \ldots, x_n]$. Let $f = \sum_j a_j x^{\alpha_j} \in R$ be such that $\sigma := \ord_\Sigma(f)$ exists. Then

1. $\ord_\Sigma(\In(f)) = \sigma.$
2. For each monomial term $a_\alpha x^\alpha$ of $\In(f)$, $\ord_\Sigma(a_\alpha x^\alpha) = \sigma.$
3. For each monomial term $a_\alpha x^\alpha$ of $\In(f)$ and $a’_{\alpha’}x^{\alpha’}$ of $f – \In(f)$, $a_\alpha x^\alpha \lt_\Sigma a’_{\alpha’}x^{\alpha’}$.

Proof. This is clear from the definitions.

Given an almost linear monomial order $\preceq$, one can use it to “refine” $\leq_\Sigma$ as follows: write $ax^\alpha \preceq_\Sigma bx^\beta$ if and only if

• either $ax^\alpha \lt_\Sigma bx^\beta$,
• or $ax^\alpha \leq_\Sigma bx^\beta \leq_\Sigma ax^\alpha$, and $ax^\alpha \preceq bx^\beta$.

We say that $\preceq$ is $\kk$-compatible with (the filtration by) $\Sigma$ if the following holds: for each $a, b \in \kk$, if $a \leq_\Sigma b$, then $a \preceq b$.

Proposition 5. Assume the filtration by $\Sigma$ is a strictly monomial filtration on $R := \kk[x_1, \ldots, x_n]$ and $\preceq$ is $\kk$-compatible with $\Sigma$. Then $\preceq_\Sigma$ is an almost linear monomial order.

Proof. Indeed, condition $1$ of almost linear monomial orders (i.e. compatibility with multiplication by monomials) is true due to the “strict monomiality” of the filtration. Condition $2$ (that $1 \preceq_\Sigma -1 \preceq_\Sigma 1$) follows since each $R_\sigma$ is an additive group. As regards to the third condition (that $a \preceq_\Sigma (a+b)$ or $b \preceq_\Sigma (a+b)$), we may assume without loss of generality that $a \leq_\Sigma b$. Then Proposition 2 implies that $a \leq_\Sigma (a+b)$. The $\kk$-compatibility between $\preceq$ and $\Sigma$ then implies that $a \preceq (a+b)$. It then follows from the definition of If $\preceq_\Sigma$ that $a \preceq_\Sigma (a+b)$, as required.

Theorem 1*. Let $I$ be an ideal of $S := \kk[x_1, \ldots, x_n]$ which is homogeneous with respect to a shallow monomial grading on $S$ by a group $\Sigma.$ Given a strictly monomial filtration on $S$ by a (totally ordered) group $\Omega$, and an almost linear monomial order $\preceq$ which is $\kk$-compatible with $\Omega,$ let $\preceq_\Omega$ be the refinement of $\leq_\Omega$ by $\preceq.$ If $g_1, \ldots, g_N$ are $\Sigma$-homogeneous elements of $I$ such that $\In_{\preceq_\Omega}(g_1), \ldots, \In_{\preceq_\Omega}(g_N)$ generate $\In_{\preceq_\Omega}(I),$ then $\Inn_{\Omega}(g_1), \ldots, \Inn_{\Omega}(g_N)$ generate $\Inn_{\Omega}(I).$

Proof. Pick $f \in I.$ Since $\In_{\preceq_\Omega}(g_1), \ldots, \In_{\preceq_\Omega}(g_N)$ generate $\In_{\preceq_\Omega}(I),$ due to Theorem 1, after reordering the $g_i$ if necessary, there is an expression
\[f = \sum_{i=1}^s q_ig_i \]
such that
\[\In_{\preceq_\Omega}(f) = \In_{\preceq_\Omega}(q_1g_1) \prec_\Omega \In_{\preceq_\Omega}(q_2g_2) \prec_\Omega \cdots \prec_\Omega \In_{\preceq_\Omega}(q_sg_s)\]
It suffices to consider the case that $\Inn_\Omega(f) \neq 0$. Let $\omega := \ord_\Omega(f) \in \Omega$. Propositions 4 and 5 imply that

• $\omega = \ord_\Omega(\In_{\preceq_\Omega}(f)) = \ord_\Omega(q_1g_1)$

On the other hand, it follows from the definition of $\preceq_\Omega$ that for each $i \leq j$,

• $\In_{\preceq_\Omega}(q_ig_i) \leq_\Omega a_{j,\alpha} x^\alpha$ for each monomial term $a_{j,\alpha} x^\alpha$ of $q_{j}g_{j}$;
• in particular, if $\omega_i := \ord_\Omega(\In_{\preceq_\Omega}(q_ig_i))$ exists in $\Omega$, then there is $\omega’_j \geq_\Omega \omega_i$ such that each monomial of $q_jg_j$ is in $S_{\omega’_j}$.

Consequently, there is $j$, $1 \leq j \leq s$, such that

• $\ord_\Omega(q_ig_i) = \omega$ for $1 \leq i \leq j$,
• either $j = s$, or there is $\omega’ \in \Omega$, $\omega’ \gt_\Omega \omega$, such that for each $i’ > j$, each monomial of $q_{i’}g_{i’}$ is in $S_{\omega’}$.

It follows that
\[\Inn_\Omega(f) = \Inn_\Omega(\sum_{i=1}^j q_ig_i) \in \bar S_\omega\]
Since $\ord_\Omega(q_ig_i) = \omega$ for each $i \leq j$, Proposition 4 then implies that
\[\Inn_\Omega(f) = \sum_{i=1}^j \Inn_\Omega(q_ig_i)\]
Since the $\Omega$-filtration is strictly monomial, it then follows that
\[\Inn_\Omega(f) = \sum_{i=1}^j \Inn_\Omega(q_i)\Inn_\Omega(g_i)\]
which completes the proof of Theorem 1*.

We now prove a somewhat weak converse of Theorem 1*. Let $\preceq$ be an almost linear monomial order on $S := \kk[x_1, \ldots, x_n]$. Consider the induced equivalence relation on the set of monomials: $ax^\alpha \preceqeq bx^\beta$ if and only if $ax^\alpha \preceq bx^\beta \preceq ax^\alpha$. Let $\Omega_+$ be the set of equivalence classes $[ax^\alpha]$ of nonzero monomials $ax^\alpha \in S$.

Proposition 6. $\Omega_+$ is a cancellative (commutative) semigroup with identity $[1]$ under the operation
\[ [ax^\alpha] + [bx^\beta] := [abx^{\alpha + \beta}] \]
In particular, the $\Omega_+$ is a subsemigroup of the “group of differences” in $\Omega$. There is a total ordering $\preceq$ on $\Omega$ defined as follows: $[ax^\alpha] – [bx^\beta] \leq [a’x^{\alpha’}] – [b’x^{\beta’}]$ if and only if $ab’x^{\alpha + \beta’} \leq a’bx^{\alpha’ + \beta}.$

Proof. It is straightforward to verify the Lemma using the “strict compatibility” (defining Property 1) of almost linear monomial orders with multiplications by monomials.

The $\Omega$-filtration on $S$ induced by $\preceq$ is given by defining $S_\omega$ to be the abelian group generated by (i.e. the $\zz$-span of) all monomials $ax^\alpha$ such that $\omega \preceq [ax^\alpha]$.

Proposition 7. The $\Omega$-filtration on $S$ is strictly monomial.

Proof. This should also be clear.

Now we arrive at the claimed “converse” to Theorem 1*:

Proposition 8. Let $I$ be an ideal of $S$ (note that it does not have to be homogeneous with respect to any monomial grading). If $g_1, \ldots, g_N \in S$ are such that $\Inn_\Omega(g_1), \ldots, \Inn_\Omega(g_N)$ generate $\Inn_\Omega(I)$, then $\In_\preceq(g_1), \ldots, \In_\preceq(g_N)$ generate $\In_\preceq(I)$.

Proof. Indeed, pick $f \in I$. Note that $\ord_\Omega(f)$ exists, and equals the class $\omega := [\In_{\preceq}(f)]$ in $\Omega$. By assumption there are $f_i \in S$ and $\omega_i \preceq [\In_{\preceq}(f_i)]$ such that
\[\Inn_\Omega(f) = \sum_i (f_i)_{\omega_i} \Inn_\Omega(g_i)\]
where we write $(f_i)_{\omega_i}$ for the image of $f_i$ in the degree $\omega_i$ component of $\gr_\Omega S.$ We can also assume that for each $i$,

1. either $(f_i)_{\omega_i} = 0$, i.e. $\omega_i \prec [\In_{\preceq}(f_i)]$,
2. or $[\In_{\preceq}(f)] = [\In_{\preceq}(f_i)] + [\In_{\preceq}(g_i)] = [\In_{\preceq}(f_ig_i)]$

Moreover, there is at least one $i$ such that the second option above holds. However, then $\In_{\preceq}(f_ig_i)$ and $\In_{\preceq}(f)$ must have the same exponent (but possibly different coefficient in $\kk \setminus \{0\}$), i.e. $\In_{\preceq}(g_i)$ divides $\In_{\preceq}(f)$. It is then clear that $\In_{\preceq}(f)$ is in the ideal generated by $\In_{\preceq}(g_i)$, which proves the Proposition.

Universal initial bases – stronger versions

Theorem 2* (Universal Bases – version 2). Let $I$ be an ideal of $S := \kk[x_1, \ldots, x_n]$ which is homogeneous with respect to a shallow monomial grading on $S$ by a group $\Sigma.$ There is a finite collection $g_1, \ldots, g_N$ of $\Sigma$-homogeneous elements of $I$ such that

1. For every almost linear monomial order $\preceq$, the initial terms $\In_\preceq(g_i)$ of the $g_i$ generate the initial ideal $\In_\preceq(I)$ of $I.$
2. For every totally ordered group $\Omega$ and every strictly monomial $\Omega$-filtration on $S$, the initial terms $\Inn_\Omega(g_i)$ of the $g_i$ generate the initial ideal $\Inn_\Omega(I)$ of $I.$

Proof. Theorem 2 implies that there is a finite collection $g_1, \ldots, g_N$ of $\Sigma$-homogeneous elements of $I$ such that for every almost linear monomial order $\preceq$ on $S$, the initial terms $\In_{\preceq}(g_i)$ of the $g_i$ generate $\In_\preceq(I)$. We show that the $g_i$ also satisfy the second assertion of Theorem 2*. Indeed, given a strictly monomial filtration on $S$ by a totally ordered group $\Omega$, pick any monomial order $\preceq$ on $\znzero$, and extend it to $\scrM := \{ax^\alpha: a \in \kk \setminus \{0\},\ \alpha := (\alpha_1, \ldots, \alpha_n) \in \znzero\}$ as follows: $ax^\alpha \leq bx^\beta$ if and only if

• either $ax^\alpha \lt_\Omega bx^\beta$,
• or $ax^\alpha \lt_\Omega bx^\beta \lt ax^\alpha$ and $\alpha \preceq \beta$.

It is straightforward to check that $\preceq$ defines an almost linear monomial order on $\scrM$ which is $\kk$-compatible with $\Omega$. Now apply Theorem 1* to complete the proof.

Now we extend Theorem 2* to possibly non-homogeneous ideals.

Theorem 2** (Universal Bases – version 3). Let $I$ be an ideal of $S := \kk[x_1, \ldots, x_n].$ There is a finite collection $g_1, \ldots, g_N$ of elements of $I$ such that

1. For every almost linear monomial order $\preceq$, the initial terms $\In_\preceq(g_i)$ of the $g_i$ generate the initial ideal $\In_\preceq(I)$ of $I.$
2. For every totally ordered group $\Omega$ and every strictly monomial $\Omega$-filtration on $S$, the initial terms $\Inn_\Omega(g_i)$ of the $g_i$ generate the initial ideal $\Inn_\Omega(I)$ of $I.$

Proof. Indeed, take another variable $x_0,$ and consider the homogenization (in the usual sense) $I^h$ of $I$ with respect to $x_0, \ldots, x_n,$ i.e. $I^h$ is the ideal of $S’ := \kk[x_0, \ldots, x_n]$ generated by
\[f^h := x_0^{\eta(f)}f(x_1/x_0^{\eta_1}, \ldots, x_n/x_0^{\eta_n})\]
for all $f \in I$. Given a strictly monomial filtration on $S$ by a totally ordered group $\Omega$, we define an $\Omega$-filtration on $S$’ as follows:
\[S’_\omega := \{f \in S’: f|_{x_0 = 1} \in S_\omega\}\]
Since the $\Omega$-filtration on $S$ is strictly monomial, it is straightforward to check that the $\Omega$-filtration on $S’$ is also strictly monomial. For each $f \in I,$ it is straightforward to check that
\[(\In_\Omega(f^h))|_{x_0 = 1} = \In_\Omega(f)\]
where $\In_\Omega$ is defined as in Proposition 4. On the other hand, if $f$ is a homogeneous element of $I^h,$ then the monomials in the support of $f$ are in one-to-one correspondence with the monomials in the support of $f|_{x_0 = 1}$ and
\[(\In_\Omega(f))|_{x_0 = 1} = \In_\Omega(f|_{x_0 = 1})\]
By Theorem 2* there are homogeneous $f_1, \ldots, f_N \in I^h$ independent of $\Omega$ such that $\Inn_\Omega(I^h)$ is generated by $\Inn_\Omega(f_i),$ $i = 1, \ldots, N.$ We claim that $\Inn_\Omega(I)$ is generated by $\Inn_\Omega(f_i|_{x_0=1}),$ $i = 1, \ldots, N.$ Indeed, pick $f \in I$ such that $\Inn_\Omega(f) \neq 0$. Then $\ord_\Omega(f)$ exists; call it $\omega$. Moreover,
\[\ord_\Omega(f^h) = \omega\]
as well (Proposition 4). On $\gr_\Omega(S’)$ we have an identity of the form
\[\Inn_\Omega(f^h) = \sum_i (g_i)_{\omega_i}\Inn_\Omega(f_i)\]
Since $(g_i)_{\omega_i} \neq 0$ if and only if $\omega_i = \ord_\Omega(g_i)$, we can write
\[\Inn_\Omega(f^h) = \sum_i \Inn_\Omega(g_i)\Inn_\Omega(f_i)\]
where the sum is over all $i$ such that both $\ord_\Omega(g_i)$ and $\ord_\Omega(f_i)$ exist and $\ord_\Omega(g_i) + \ord_\Omega(f_i) = \omega$. This implies that
\[f^h – \sum_i \In_\Omega(g_i)\In_\Omega(f_i) \in S’_{\omega’}\]
for some $\omega’ \gt \omega$ (where $\In_\Omega(\cdot)$ is defined as in Proposition 4). However, then
\[
(f^h – \sum_i \In_\Omega(g_i)\In_\Omega(f_i))|_{x_0 =1}
= f – \sum_i \In_\Omega(g_i|_{x_0 =1}) \In_\Omega(f_i|_{x_0 =1}) \in S_{\omega’}
\]
where the sum is over all $i$ such that $\ord_\Omega(g_i|_{x_0=1})$ and $\ord_\Omega(f_i|_{x_0=1})$ exist and $\ord_\Omega(g_i|_{x_0=1}) + \ord_\Omega(f_i|_{x_0=1}) = \omega = \ord_\Omega(f)$. This implies that
\[\Inn_\Omega(f) = \sum_i \Inn_\Omega(g_i|_{x_0=1})\Inn_\Omega(f_i|_{x_0=1}) \in \gr_\Omega(S)\]
This completes the proof of the claim and consequently, assertion 2 of Theorem 2**. Assertion 1 then follows from Proposition 8. This completes the proof of Theorem 2**.

$\DeclareMathOperator{\gr}{gr} \DeclareMathOperator{\In}{In} \DeclareMathOperator{\Inn}{\overline{In}} \DeclareMathOperator{\Incoeff}{In_coeff} \DeclareMathOperator{\Inexp}{In_exp} \DeclareMathOperator{\ld}{Ld} \newcommand{\qq}{\mathbb{Q}} \newcommand{\kk}{\mathbb{K}} \DeclareMathOperator{\ord}{ord} \newcommand{\preceqeq}{\preceq_{\equiv}} \newcommand{\rnpos}{\mathbb{R}^n_{> 0}} \newcommand{\rnzero}{\mathbb{R}^n_{\geq 0}} \newcommand{\rr}{\mathbb{R}} \newcommand{\scrB}{\mathcal{B}} \newcommand{\scrK}{\mathcal{K}} \newcommand{\scrM}{\mathcal{M}} \DeclareMathOperator{\supp}{Supp} \newcommand{\znplusonezero}{\mathbb{Z}^{n+1}_{\geq 0}} \newcommand{\znplusonepos}{\mathbb{Z}^{n+1}_{> 0}} \newcommand{\znpos}{\mathbb{Z}^n_{> 0}} \newcommand{\znzero}{\mathbb{Z}^n_{\geq 0}} \newcommand{\zz}{\mathbb{Z}}$
Today we discuss division of polynomials over valued fields, i.e. fields equipped with a (real) valuation, and consider orderings on monomials which incorporate that valuation. The goal is to arrive at various versions of the “universal basis theorem” which states that for every ideal there is a finite set of polynomials which determine the initial ideal with respect to various collections of linear preorders (i.e. reflexive and transitive binary relations) including the set of all linear orders. In fact we end this post with the first version of the universal basis theorem, and treat stronger versions of the universal basis theorem in a future post. As we have seen, the universal basis theorem for linear orders is harder to establish than that for monomial orders. The trend continues, and the case of linear orders over valued fields is even harder.

Example 1 [Chan-Maclagan2013]. Consider the \(p\)-adic valuation \(\nu_p\) on \(\qq,\) where \(p\) is a prime number, and \(\nu_p\) is defined on \(\qq\) as: \[\nu_p(p^qa/b) := q\] where \(a, b\) are integers relatively prime to \(p\), and \(q\) is an arbitrary integer. This defines a \(\zz^3\)-grading on \(S := \qq[x,y]\) with homogeneous components \[S_{(q,\alpha, \beta)} := \{ax^\alpha y^\beta: a \in \qq,\ \nu_p(a) = q\}\]Take any group order on \(\zz^2\) and define an ordering \(\preceq’\) on monomial terms of \(S\) as follows: \(ax^\alpha y^\beta \preceq’ a’x^{\alpha’}y^{\beta’}\) if and only if

• either \(\nu_p(a) < \nu_p(b),\) or
• \(\nu_p(a) = \nu_p(b)\) and \((\alpha, \beta) \preceq (\alpha’, \beta’)\)

Note that \(\preceq’\) is not a total order on the set of monomial terms on \(S,\) since there are monomial terms \(T \neq T’\) such that \(T \preceq’ T’\) and \(T’ \preceq’ T,\) e.g. take \(T := x\) and \(T’ := qx\) where \(q\) is any integer relatively prime to \(p.\) Nonetheless, we can try to follow the naive initial-term-cancelling division from the preceding post on \(S\) with respect to \(\preceq’.\) So take \(g_1 := x – py,\) \(g_2 := y – px\) and try dividing \(f := x\) by \(g_1, g_2\) following the naive initial-term-cancelling division strategy. The initial terms of \(g_1, g_2\) with respect to \(\preceq’\) are respectively \(x\) and \(y.\) It follows that

• after the first step one has: \(f = g_1 + py,\)
• after the second step one has: \(f = g_1 + pg_2 + p^2x,\)
• after the third step one has: \(f = (1+p^2)g_1 + pg_2 + p^3y,\)
• after the fourth step one has: \(f = (1+p^2)g_1 + (p+p^3)g_2 + p^4x,\)

and so on. It is clear that the process does not terminate. On the other hand, if we recognize the remainder \(p^2x\) in the second step as \(p^2f,\) then rearranging the terms in the second step one has: \[f = \frac{1}{1-p^2}g_1 + \frac{p}{1-p^2}g_2\]which seems to be a reasonable outcome for a division process. Chan and Maclagan [Chan-Maclagan2013] showed that this always works.

Almost linear orders

An almost linear order on the set \(\scrM := \{ax^\alpha: a \in \kk \setminus \{0\},\ \alpha := (\alpha_1, \ldots, \alpha_n) \in \znzero\}\) of monomial terms is a reflexive and transitive binary relation on \(\scrM\) which is a linear order on all monomials with different exponents, i.e. every finite set of monomials with pairwise distinct exponents has a unique minimal element. Every linear order on \(\znzero\) trivially lifts to a almost linear order on monomial terms which simply ignores the coefficients and applies the original linear order on the exponents. The relation \(\preceq’\) from Example 1 is an example of a nontrivial almost linear order.

The notions of initial and leading monomial terms make sense for an almost linear order \(\preceq\) on monomial terms, and therefore every step of the “initial term cancelling division” also makes sense. Recall that the initial term cancelling division of a polynomial \(f\) by a finite ordered collection \(g_1, \ldots, g_N\) of polynomials proceeds as follows:

1. Set \(h_0 := f\)
2. If \(h_j = 0\) for some \(j \geq 0,\) then stop.
3. Otherwise if there is \(i\) such that \(\In_\preceq(g_i)\) divides \(\In_\preceq(h_j)\), then pick the smallest such \(i\), and set \(h_{j+1} := h_j – qg_i\), where \(q := \In_\preceq(h_j)/\In_\preceq(g_i)\).
4. Otherwise \(\In_\preceq(h_j)\) is not divisible by \(\In_\preceq(g_i)\) for any \(i\); in this case set \(h_{j+1} := h_j – \In_\preceq(h_j).\)
5. Repeat steps 2-4 with \(j + 1\) in place of \(j.\)

Example 1 shows that for a general almost linear order \(\preceq\) the above algorithm may not end even if the divisors are homogeneous with respect to a shallow monomial grading. However, it also suggests a way forward, namely to use remainders from earlier steps of the division. To fix notation, write \(r_j\) for the remainder and \(q_{j,i}\) to be the multiplier of \(g_i\) after \(j\) iterations of the algorithm. After the \(j\)-th iteration one has \[f = \sum_i q_{j,i}g_i + r_j = \sum_i q_{j,i}g_i + r_{j,0} + r_{j,1}\]where

• \(r_{j,1}\) is the part of remainder that has already been computed; in particular, none of the monomials in the support of \(r_{j,1}\) is divisible by \(\In(g_i)\) for any \(i = 1, \ldots, s.\)
• \(r_{j,0}\) is the part of the remainder “yet to be explored,” i.e. it is the \(h_j\) from the above algorithm.

Let \(a_j \in \kk\) and \(\alpha_j \in \znzero\) be respectively the coefficient and the exponent of \(\In_\preceq(r_{j,0}),\) i.e. \[\In_\preceq(r_{j,0}) = a_j x^{\alpha_j}\](in the sequel we use \(\Incoeff(r_{j,0})\) and \(\Inexp(r_{j,0})\) to denote respectively \(a_j\) and \(\alpha_j.\)) Let \(r’_{j,0} := r_{j,0} – \In_\preceq(r_{j,0}).\) For the \((j+1)\)-th iteration, Example 1 suggests that it is useful to look out for \(k < j\) such that \(\alpha_k = \alpha_j.\) Indeed, if such \(k\) exists, then writing \(c_j := a_j/a_k,\) the above equation for \(f\) can be rearranged as
\[\begin{align*}
f &= \sum_i q_{j,i}g_i + a_jx^{\alpha_j} + r’_{j,0} + r_{j,1}
= \sum_i q_{j,i}g_i + c_j\In_\preceq(r_{k,0}) + r’_{j,0} + r_{j,1} \\
&= \sum_i q_{j,i}g_i + c_j(r_{k,0} – r’_{k,0}) + r’_{j,0} + r_{j,1}
= \sum_i q_{j,i}g_i + c_j(f – \sum_i q_{k,i}g_i – r_{k,1} – r’_{k,0}) + r’_{j,0} + r_{j,1} \\
&= c_jf + \sum_i (q_{j,i} – c_j q_{k,i})g_i + (r’_{j,0} – c_jr’_{k,0}) + (r_{j,1} – c_jr_{k,1})
\end{align*}\]
If \(c_j \neq 1,\) then it follows that
\[\begin{align}
f
&= \sum_i \frac{q_{j,i} – c_jq_{k,i}}{1-c_j}g_i + \frac{r’_{j,0} – c_jr’_{k,0}}{1-c_j} + \frac{r_{j,1} – c_jr_{k,1}}{1-c_j}
\end{align}\]

Almost linear monomial orders

We say that $\preceq$ is an almost linear group order or an almost linear monomial order if it is an almost linear order on the set of monomial terms which is also compatible with respect to product and sum of monomial terms in the following way (it follows from discussions below and the next post on division that every almost linear monomial order is also a linear monomial preorder):

1. for all $a, b, c \in \kk\setminus\{0\}$ and $\alpha, \beta, \gamma \in \znzero$,
   • if $ax^\alpha \preceq bx^\beta,$ then $acx^{\alpha+\gamma} \preceq bcx^{\beta+\gamma},$
   • if $ax^\alpha \prec bx^\beta,$ then $acx^{\alpha+\gamma} \prec bcx^{\beta+\gamma},$ (this property is used in the second from the last sentence in the proof of Theorem 1)
2. \(1 \preceq -1\) and \(-1 \preceq 1,\)
3. for all \(a, b \in \kk,\) either \(a \preceq (a+b)\) or \(b \preceq (a+b).\)

In Property 1 above we used $\prec$ to denote the “strict order” with respect to $\preceq,$ i.e.

• $a \prec b$ if and only if $a \preceq b$ and $b \not\preceq a.$

We also write \(\preceqeq\) to denote “equivalence” with respect to \(\preceq,\) i.e.

• \(a \preceqeq b\) if and only if \(a \preceq b\) and \(b \preceq a\),

Property 2 of almost linear group orders then can be rewritten as

• \(-1 \preceqeq 1.\)

Note that Property 1 implies the following seemingly stronger statement:

• if \(ax^\alpha \preceq bx^\beta,\) and \(cx^\gamma \preceq dx^\delta,\) then \(acx^{\alpha+\gamma} \preceq bdx^{\beta+\delta}\) for all \(c,d \in \kk\setminus\{0\}\) and \(\gamma, \delta \in \znpos. \)

Property 1 and 2 then imply that

• \(ax^\alpha \preceq bx^\beta\) if and only if \(-ax^\alpha \preceq bx^\beta\) if and only if \(ax^\alpha \preceq -bx^\beta\) if and only if \(-ax^\alpha \preceq -bx^\beta.\)

Also due to Property 2 and 3, \(\preceq\) can be consistently extended to \(\scrM \cup \{0\}\) via declaring

• \(ax^\alpha \preceq 0\) for all \(a \in \kk\) and \(\alpha \in \znzero.\)

In presence of Properties 1 and 2, Property 3 implies that

• \(\preceq\) restricts to a total preorder on \(\kk,\) i.e. for all \(a, b \in \kk,\) either \(a \preceq b\) or \(b \preceq a\) (or both). Indeed, assume without loss of generality that \(a\preceq a+b.\) Since \(b = (a+b) – a,\) it follows that \(a+b \preceq b\) or \(-a \preceq b.\) Both of these possibilities imply that \(a \preceq b.\)
• If \(a \prec b,\) then \(a \preceqeq a+b.\) Indeed, Property 3 immediately implies that \(a \preceq a+b.\) On the other hand, since \(a = (a+b) – b,\) and \(b \not\preceq a,\) we must have that \(a+b \preceq a.\)

If \(\preceq\) is indeed an almost linear group order, then at each step of the initial-term-cancelling division algorithm, the initial term of \(h_j\) strictly increases with respect to \(\preceq\), i.e.
\[\In_\preceq(h_j) \prec \In_\preceq(h_{j+1})\]
It follows that in the last displayed equation for \(f\) above \(c_j\) can not be \(1,\) so that the equation is well defined. In fact, it is straightforward to check that \(1 \prec c_j\). The defining properties of almost linear group orders then imply that
\[1 – c_j \preceqeq 1\]
which in turn implies that
\[
\In_\preceq(r_{j,0})
\prec \In_\preceq(r’_{j,0} – c_jr’_{k,0})
\preceqeq \In_\preceq\left(\frac{r’_{j,0} – c_jr’_{k,0}}{1-c_j}\right)
\]
Consequently, if we set
\[r_{j+1,0} := \frac{r’_{j,0} – c_jr’_{k,0}}{1-c_j}\]
then
\[\In_\preceq(r_{j,0}) \prec \In_\preceq(r_{j+1,0})\]
We now rewrite the initial-term-cancelling-division algorithm for almost linear group orders to incorporate these observations. Recall that the aim of this algorithm is to find an expression\[f = \sum_i q_ig_i + r\]such that

• either \(r = 0\) or no monomial term in \(r\) is divisible by \(\In_\preceq(g_i)\) for any \(i\), and
• 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})\]

Each step of the algorithm below expresses \(f\) as\[f = \sum_j q_{j,i}g_i + r_{j,0} + r_{j,1}\]where \(j\) is the step, \(r_{j,0}\) is the “part” of \(f\) “still to be explored” and \(r_{j,1}\) is the part of the remainder that has been computed. In particular, either \(r_{j,1} = 0\) or no monomial term in \(r_{j,1}\) is divisible by \(\In_\preceq(g_i)\) for any \(i\). The algorithm stops when \(r_{j,0} = 0.\)

Initial term cancelling division, version 2: Given a polynomial \(f\) (the dividend), a finite ordered collection \(g_1, \ldots, g_N\) of polynomials (the divisors) and an almost linear monomial order \(\preceq,\) proceed as follows: start with \(j = 0.\) Set \(q_{0,i} := 0\) for all \(i,\) \(r_{0, 0} := f\) and \(r_{0, 1} := 0.\) Now proceed as follows:

1. If \(r_{j,0} = 0,\) then stop.
2. Otherwise check if there is \(k < j\) such that
   \[\Inexp(r_{k,0}) = \Inexp(r_{j,0})\]
   If such \(k\) exists, then necessarily one has
   \[c_j := \Incoeff(r_{j,0})/\Incoeff(r_{k,0}) \succ 1\]
   Then define
   \[\begin{align*}
   q_{j+1,i} &:= \frac{q_{j,i} – c_jq_{k,i}}{1-c_j},\ i = 1, \ldots, N, \\
   r_{j+1,0} &:= \frac{r’_{j, 0} – c_jr’_{k,0}}{1-c_j}, \\
   r_{j+1,1} &:= \frac{r_{j, 1} – c_jr_{k,1}}{1-c_j}
   \end{align*}\]
   where
   \[r’_{j,0} := r_{j,0} – \In_\preceq(r_{j,0})\]
   and \(r’_{k,0}\) is defined similarly. Note that there is an ambiguity at this step in choosing \(k\) if there are more than one choices. Below we will define a criterion for choosing \(k\).
3. Otherwise if there is \(i\) such that \(\In_\preceq(g_i)\) divides \(\In_\preceq(r_{j,0})\), then pick the smallest such \(i\), and with \(q := \In_\preceq(r_{j,0})/\In_\preceq(g_i),\) define
   \[\begin{align*}
   r_{j+1,0} &:= r_{j,0} – qg_i, \\
   r_{j+1,1} &:= r_{j,1}, \\
   q_{j+1,k} &:=
   \begin{cases}
   q_{j,i} + q &\text{if}\ k = i,\\
   q_{j,i} & \text{otherwise.}
   \end{cases}
   \end{align*}\]
4. Otherwise set
   \[\begin{align*}
   r_{j+1,0} &:= r_{j,0}, \\
   r_{j+1,1} &:= r_{j,1} + \In_\preceq(r_{j,0}), \\
   q_{j+1,i} &:= q_{j,i},\ i = 1, \ldots, N.
   \end{align*}\]
5. Repeat steps 2-4 with \(j + 1\) in place of \(j.\)

Earlier discussions on division via initial terms suggest that it might be prudent to consider the special case that the divisors \(g_1, \ldots, g_N\) are homogeneous with respect to a shallow monomial grading \(\Sigma.\) In that case, if the condition is step 2 is not satisfied at any iteration, then we claim that the algorithm must stop in finitely many steps. Indeed, if the condition in step 2 is not satisfied, then each time \(r_{j,0}\) gets updated in step 3, a monomial with different exponent is added to the support of \(r_{j,0}.\) Since \(g_i\) are homogeneous with respect to \(\Sigma\) the \(\Sigma\)-supports of all \(r_{j,k}\) are contained in the \(\Sigma\)-support of \(f\) and therefore due to the shallowness, the number of monomials in \(r_{j,0}\) can grow indefinitely. Consequently \(r_{j,0}\) must remain unchanged after a finite number of steps. But then step 4 can not repeat infinitely many times, since that would result in the number of monomials in \(r_{j,1}\) getting indefinitely larger. Therefore, if the algorithm is to continue without stopping, the condition in step 2 must be satisfied at infinitely many iterations. Now comes a crucial observation of Chan and Maclagan [Chan-Maclagan2013]:

Criterion to pick \(k\) in Step 2: In Step 2, if there are more than one choice for \(k < j\) such that \(\Inexp(r_{k,0}) = \Inexp(r_{j,0}),\) then choose any \(k\) such that the number of monomials in \(r_{k,0}\) which are not in \(r_{j,0}\) is the smallest possible. Actually the only thing you really need to ensure stoppage in finitely many steps is: if it is possible, then \(k\) should be chosen such that \(\supp(r_{k,0}) \subseteq \supp(r_{j,0}).\)

Theorem 1. If \(g_1, \ldots, g_N\) are homogeneous with respect to a shallow monomial grading \(\Sigma\) and the above criterion is used to pick \(k\) in Step 2 of the initial term cancelling division by \(g_1, \ldots, g_N\) with respect to an almost linear monomial order \(\preceq,\) then the division algorithm stops in finitely many steps. The outcome of the algorithm satisfies the “aim” of the algorithm (described in the paragraphs preceding the version 2 of the division algorithm).

Proof. Since the \(g_i\) are homogeneous, \(\supp_\Sigma(r_{j,0}) \subseteq \supp_\Sigma(f)\) for each \(j.\) Since the grading is shallow, there are finitely many possible choices for the usual support \(\supp(r_{j,0}) \subseteq \znzero\) of \(r_{j,0}\) consisting of the exponents of the monomials appearing in \(r_{j,0}.\) Therefore there must be \(j_0\) such that for each \(j \geq j_0,\) if \(r_{j,0} \neq 0,\) then there is already \(k < j\) such that \(\supp(r_{k,0}) = \supp(r_{j,0}).\) But then for each \(j \geq j_0,\) if \(r_{j,0} \neq 0,\) the Step 2 condition is satisfied at each step, and the above criterion for picking \(k\) ensures that \(\supp(r_{k,0}) \subseteq \supp(r_{j,0})\) so that the size of the support of \(r_{j+1,0}\) decreases compared to that of \(r_{j,0}.\) Since the support of a polynomial is finite, \(r_{j,0}\) must become zero in finitely many steps beyond \(j_0.\) To see that the “aim” is satisfied, note that the condition regarding the remainder is clear. For the condition regarding the quotients, it suffices to show that for each \(i, j,\) either \(q_{j,i} = 0\) or \(\In_\preceq(q_{j+1,i}) = \In_\preceq(q_{j,i}).\) This is clear in Steps 3 and 4. For Step 2, this follows from the observation that \(c_j \succ 1\) and, either \(q_{k,i} = 0\) or \(\In_\preceq(q_{j,i}) = \In_\preceq(q_{k,i}).\) This completes the proof of Theorem 1.

Corollary 1. Let \(I \supseteq J\) be ideals of \(S := \kk[x_1, \ldots, x_n]\) such that \(J\) is homogeneous with respect to a shallow monomial grading on \(S.\) If \(I \supsetneqq J\), then \(\In_\preceq(I) \supsetneqq \In_\preceq(J)\) for every almost linear monomial order \(\preceq.\)

Proof. Pick homogeneous \(g_1, \ldots, g_N \in J\) such that \(\In_\preceq(g_i)\), \(i = 1, \ldots, N\), generate \(\In_\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 \(S := \kk[x_1, \ldots, x_n]\) which is homogeneous with respect to a shallow monomial grading on \(S.\) There can not exist almost linear monomial orders \(\preceq_1, \preceq_2\) such that \(\In_{\preceq_1}(I) \subsetneqq \In_{\preceq_2}(I)\).

Proof. Write \(J_k := \In_{\preceq_k}(I)\), \(k = 1, 2\). Assume to the contrary that \(J_1 \subsetneqq J_2\). Then we can choose homogeneous \(g_1, \ldots, g_N \in I\) such that \(\In_{\preceq_2}(g_i)\), \(i = 1, \ldots, N\), generate \(J_1\). Choose \(f \in I\) such that \(\In_{\preceq_2}(f) \not\in J_1.\) Let \(r\) be the remainder of the Chan-Maclagan 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\) are homogeneous elements in \(I\) such that \(\In_{\preceq_1}(h_1), \ldots, \In_{\preceq_1}(h_M)\) generate \(J_1,\) then the Chan-Maclagan division of \(r\) by \(h_1, \ldots, h_M\) with respect to \(\preceq_1\) implies that \(r \not\in I,\) which is a contradiction. This completes the proof.

The notion of reduced initial basis described in the earlier post on division of power series also applies to an almost linear monomial order: a finite ordered collection of elements \(g_1, \ldots, g_N\) from an ideal \(I\) of \(S\) is called a reduced initial basis with respect to an almost linear 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.\)

If \(I\) is homogeneous with respect to a shallow monomial \(\Sigma\)-grading on \(S\), then a reduced initial basis for \(I\) can be produced by taking a minimal set of \(\Sigma\)-homogeneous elements of \(I\) whose initial terms generate \(\In_\preceq(I)\) and then replacing each element by the remainder of the Chan-Maclagan division by other elements.

Corollary 3. Let \(I\) be an ideal of \(S := \kk[x_1, \ldots, x_n]\) which is homogeneous with respect to a shallow monomial \(\Sigma\)-grading on \(S\), and \(\preceq, \preceq’\) be almost linear monomial orders such that
\[\In_\preceq(I) = \In_{\preceq’}(I)\]
Then any reduced \(\Sigma\)-homogeneous initial basis of \(I\) with respect to one of \(\preceq, \preceq’\) is also a reduced initial basis with respect to the other one, and for each element of the basis, the initial terms with respect to $\preceq$ and $\preceq’$ are identical. Moreover, the number of elements on a reduced $\Sigma$-homogeneous initial basis of $I$ is also uniquely determined by $I$.

Proof. Indeed, pick a reduced initial basis \(g_1, \ldots, g_N\) of \(I\) with respect to \(\preceq\). Let \(\alpha_i := \nu_{\preceq}(g_i),\) \(i = 1, \ldots, n.\) Fix \(i.\) Since \(\In_{\preceq’}(I)\) is also 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\) it must be divisible by \(x^{\alpha_i}.\) Since \(\alpha_i\) is also in the support of \(g_i,\) and \(g_i\) is \(\Sigma\)-homogeneous and the grading by \(\Sigma\) is shallow, Remark 1 in the preceding post implies that the only monomial in \(g_i\) divisible by \(x^{\alpha_i}\) is \(x^{\alpha_i}\) itself, so that \(\nu_{\preceq’}(g_i) = \alpha_i.\) It follows that that \(\In_{\preceq’}(g_i),\) \(i = 1, \ldots, N,\) form a reduced initial basis of \(I\) with respect to \(\preceq’\) as well. The proof of the last assertion is similar to that in the proof of Corollary 3 in the preceding post.

Theorem 2 (Universal Bases – version 1). Let $I$ be an ideal of $S := \kk[x_1, \ldots, x_n]$ which is homogeneous with respect to a shallow monomial grading on $S$ by a group $\Sigma.$ There are finitely many distinct initial ideals of $I$ with respect to almost linear monomial orders. In particular, there is a finite subset of $\Sigma$-homogeneous elements of $I$ such that for every almost linear monomial order, the initial terms of polynomials in that subset generate the initial ideal of $I.$

Proof. Regarding the first assertion, Logar’s argument for the leading ideal case from the proof of Theorem 2 in the earlier post on polynomial division applies almost immediately to the present situation – one only needs to choose homogeneous elements in every case and replace “$\ld$” with “$\In$”. The second assertion then follows from Corollary 3 to Theorem 1.

References

• [Chan-Maclagan2013] Andrew J. Chan and Diane Maclagan, Groebner bases over fields with valuations, 2013, arxiv:1303.0729.

\(\DeclareMathOperator{\In}{In} \DeclareMathOperator{\ld}{Ld} \DeclareMathOperator{\kk}{\mathbb{K}} \DeclareMathOperator{\ord}{ord} \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}}\)This is a continuation of an earlier post on polynomial division where we looked at division of polynomials via cancelling the leading term with respect to a monomial order. Here we look at “initial terms” of polynomials with respect to monomial orders, and show that, similar to the case of leading ideals, there can be only finitely many “initial ideals” for a given ideal of a polynomial ring. The problem with division via cancelling the initial term, as opposed to the cancellation of the leading term in (Step 1 of) the division algorithm, is that the initial exponent can indefinitely increase (whereas the termination of the original division algorithm is guaranteed by the fact that the leading exponent can not indefinitely decrease). This is the reason the initial-term-cancelling-division works for power series, as we have seen in the preceding post, but not for polynomials. There are (at least) two natural ways to proceed:

1. To treat the polynomials as power series, and apply the power series division algorithm even when the divisors and the dividend are polynomials. In this case the quotient and the remainder may not be polynomials, but it can be shown that the initial ideal of a polynomial ideal \(I\) agrees with the initial ideal of the ideal of the ring of power series generated by \(I\), and from this it follows that every ideal can have at most finitely many initial ideals, and every initial ideal comes from a weight.
2. To homogenize the original ideal with respect to a new variable, and consider initial-term-cancelling-division only by homogeneous polynomials. In this case for each homogeneous term, say of degree \(d\), of the dividend, the corresponding term of the remainder can not escape the finite dimensional vector space of homogeneous polynomials of degree \(d\), which ensures that the algorithm terminates in finitely many steps.

The first one will be pursued in a subsequent post. Here we take the second approach. Its shortcoming of the second approach is that, at least in the form described above, it applies only to homogeneous ideals. However, this division algorithm actually works whenever the divisors are homogeneous with respect to any grading on the polynomial ring which is “compatible” with monomials and has finite dimensional graded components. Moreover, the division can be adapted to any linear, but not necessarily well, order on \(\znpos\) which is compatible with the addition on \(\znpos.\)

Shallow monomial gradings on the polynomial Ring

A grading on a ring \(R\) by a group \(\Sigma\) (or in short, a \(\Sigma\)-grading) is a family \((R_\sigma)_{\sigma \in \Sigma}\) of additive subgroups of \(R\) indexed by \(\Sigma\) such that

• \(R = \oplus_{\sigma \in \Sigma} R_\sigma,\) and
• for each \(\sigma, \tau \in \Sigma,\) if \(f \in R_\sigma\) and \(g \in R_\tau,\) then \(fg \in R_{\sigma\tau}\)

We will work with rings containing a field \(\kk\), and require our gradings to satisfy the additional property that

• each \(R_\sigma\) is a vector space over \(\kk\), or equivalently, \(\kk \subseteq R_\epsilon,\) where \(\epsilon\) is the unit of \(\Sigma.\)

The elements of \(R_\sigma,\) \(\sigma \in \Sigma,\) are called homogeneous of degree \(\sigma,\) and given \(f \in R,\) its homogeneous components are homogeneous elements \(f_\sigma\) such that \[f = \sum_{\sigma \in \Sigma} f_\sigma\]We write \(\supp_\Sigma(f)\) for the set of all elements in \(\Sigma\) that “support” \(f,\) i.e. \[\supp_\Sigma(f) := \{\sigma \in \Sigma: f_\sigma \neq 0\}\]A homogeneous ideal of \(R\) is an ideal generated by homogeneous elements; equivalently, an ideal is homogeneous if and only if it contains all homogeneous components of each of its elements.

A grading on \(S := \kk[x_1, \ldots, x_n]\) is monomial compatible, or simply a monomial grading, if every monomial in \((x_1, \ldots, x_n)\) is homogeneous, and it is shallow if for all \(\sigma\) the dimension of \(S_\sigma\) (as a vector space over \(\kk\)) is finite. Given any \(n\)-tuple of weights \((w_1, \ldots, w_n)\in \rr^n,\) the corresponding weighted degree defines a monomial compatible \(\rr\)-grading on \(S\) which is shallow if every \(w_i\) is positive. More generally, any linear map \(\pi: \rr^n \to \rr^m\) induces a monomial compatible \(\rr^m\)-grading on \(S\) which is shallow if and only if the restriction of \(\pi\) to \(\zz^n\) is injective. In particular, every monomial order on \(S\) induces a shallow monomial compatible \(\zz^n\)-grading on \(S\) such that \(\dim_\kk(S_\sigma) = 1\) for each \(\sigma \in \zz^n.\)

Remark 1. If a grading on \(S := \kk[x_1, \ldots, x_n]\) by a group \(\Sigma\) is shallow, then the graded component of \(S\) corresponding to the unit in \(\Sigma\) must consist only of \(\kk.\)

Initial-term-cancelling division by homogeneous elements with respect to shallow monomial gradings

Let \(\preceq\) be a group order (i.e. an order which is compatible with addition) on \(\znpos\) which is linear (but not necessarily well-) order. The notions of initial exponent/term/ideal with respect to \(\preceq\) still makes sense for polynomials. The following observation, made in the previous post for monomial orders, also holds for linear orders with the same proof:

Lemma 1. If \(f_1, \ldots, f_N\) are polynomials with mutually distinct values of \(\nu_\preceq\), then the \(f_i\) are linearly independent over \(\kk\).

Fix an arbitrary shallow monomial compatible \(\Sigma\)-grading on \(S := \kk[x_1, \ldots, x_n].\) The initial-term-cancelling-division algorithm in \(S\) is the procedure for reducing a polynomial \(f\) by a finite ordered collection of homogeneous (with respect to \(\Sigma\)) polynomials \(g_1, \ldots, g_N\) as follows:

1. Set \(h := f\)
2. If there is \(i\) such that \(\In_\preceq(g_i)\) divides \(\In_\preceq(h)\), then pick the smallest such \(i\), and replace \(h\) by \(h – qg_i\), where \(q := \In_\preceq(h)/\In_\preceq(g_i)\).
3. Otherwise \(\In_\preceq(h)\) is not divisible by \(\In_\preceq(g_i)\) for any \(i\); in this case replace \(h\) by \(h – \In_\preceq(h).\)
4. Repeat steps 2-3 until \(h\) reduces to the zero polynomial.

Note that the grading and the linear order are not related – they are chosen completely independently of one another. Nevertheless, the division algorithm terminates:

Theorem 1. The above algorithm (of initial-term-cancelling-division by polynomials which are homogeneous with respect to shallow monomial gradings) stops in finitely many steps, and after the final step one has: \[f = \sum_i q_ig_i + r\]where

• either \(r = 0\) or no monomial term in \(r\) is divisible by \(\In_\preceq(g_i)\) for any \(i\), and
• \(\In_\preceq(\sum_i q_ig_i) \in \langle \In_\preceq(g_i): i = 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.

If \(g_1, \ldots, g_N\) are elements of an ideal \(I\) of \(\kk[x_1, \ldots, x_n]\) 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\) is the zero polynomial.

Proof. Let \(\sigma_1, \ldots, \sigma_s\) be the elements of \(\supp_\Sigma(f).\) Since the grading is monomial compatible, \(\In_\preceq(f) \in S_{\sigma_j}\) for some \(j,\) and if \(\In_\preceq(g_i)\) divides \(\In_\preceq(f),\) then since \(g_i\) is homogeneous with respect to \(\Sigma,\) both \(qg_i\) and \(f – qg_i\) are also in \(S_{\sigma_j},\) where \(q := \In_\preceq(f)/\In_\preceq(g_i).\) It follows that after every repetition of steps 2 and 3,

• each nonzero homogeneous component of \(h\) has degree \(\sigma_k\) for some \(k = 1, \ldots, s,\) i.e. \[\supp_\Sigma(h) \subseteq \supp_\Sigma(f)\]
• there is at least one \(j\) such that \(\nu_\preceq(h_{\sigma_j})\) increases from the previous iteration.

Since the grading is shallow, each \(S_{\sigma_j}\) is finite dimensional over \(\kk\), and therefore Lemma 1 implies that the algorithm stops in finitely many steps. The other assertions of Theorem 1 are immediate.

A totally ordered grading on \(S := \kk[x_1, \ldots, x_n]\) is a grading by a totally ordered group \(\Omega\) (which in particular means that the ordering is compatible with the group law, i.e. if \(a \preceq b\) then \(ac \preceq bc\) and \(ca \preceq cb\) for all \(c \in \Omega\)). If a grading is totally ordered, then every polynomial has a well defined initial/leading form which is simply the homogeneous component of respectively the lowest/highest degree. For an ideal of \(S,\) its initial/leading ideal is the ideal generated by respectively the initial/leading forms of its elements. Every total group order \(\preceq\) on \(\znpos\) induces a “refinement” of the grading by \(\Omega\) in the following way: define \(\alpha \preceq’ \beta\) if and only if

• either \(\ord_\Omega(x^\alpha)\) is strictly smaller than \(\ord_\Omega(x^\beta)\) with respect to the ordering on \(\Omega\) (where \(\ord_\Omega(f)\) is the smallest element (with respect to the ordering on \(\Omega\)) of \(\supp_\Omega(f)\)), or
• \(\ord_\Omega(x^\alpha) = \ord_\Omega(x^\beta)\) and \(\alpha \preceq \beta\)

It is straightforward to check that \(\preceq’\) is also a total group order on \(\znpos.\) It is a “weak refinement” of the grading by \(\Omega\) in the sense that if \(\ord_\Omega(x^\alpha)\) is less than \(\ord_\Omega(x^\beta)\) with respect to the ordering on \(\Omega\) then \(\alpha \prec’ \beta.\) Note that if the grading by \(\Omega\) is not monomial compatible, then there may exist polynomials \(f, g\) such that \(\ord_\Omega(f)\) is less than or equal to \(\ord_\Omega(g)\) but \(\In_{\preceq’}(f)\) is greater than \(\In_{\preceq’}(g)\) with respect to \(\preceq’.\)

Theorem 1*. Let \(I\) be an ideal of \(S\) which is homogeneous with respect to a shallow monomial grading on \(S\) by a group \(\Sigma.\) Given a monomial grading of \(S\) by a totally ordered group \(\Omega\) and a total group order \(\preceq\) on \(\znpos,\) let \(\preceq’\) be the above refinement of the \(\Omega\)-grading by \(\preceq.\) If \(g_1, \ldots, g_N\) are \(\Sigma\)-homogeneous elements of \(I\) such that \(\In_{\preceq’}(g_1), \ldots, \In_{\preceq’}(g_N)\) generate \(\In_{\preceq’}(I),\) then \(\In_{\Omega}(g_1), \ldots, \In_{\Omega}(g_N)\) generate \(\In_{\Omega}(I).\)

Proof. Pick \(f \in I.\) Since \(\In_{\preceq’}(g_1), \ldots, \In_{\preceq’}(g_N)\) generate \(\In_{\preceq’}(I),\) there is \(i_1\) such that \(\In_{\preceq’}(g_{i_1})\) divides \(\In_{\preceq’}(f),\) i.e. there is \(a_{i_1} \in \kk\) and \(\alpha_{i_1} \in \znzero\) such that \[\In_{\preceq’}(f) = a_{i_1}x^{\alpha_{i_1}}\In_{\preceq’}(g_{i_1})\]
Let
\[h_1 := a_{i_1}x^{\alpha_{i_1}}g_{i_1},\quad f_1 := f – h_1\]
Since the \(\Omega\)-grading is monomial compatible, it follows that \[\ord_\Omega(h_1) = \ord_\Omega(x^{\alpha_{i_1}}) + \ord_\Omega(g_{i_1}) = \ord_\Omega(x^{\alpha_{i_1}}) + \ord_\Omega(\In_{\preceq’}(g_{i_1})) = \ord_\Omega(\In_{\preceq’}(f)) = \ord_\Omega(f)\]
Note that

• The monomial compatibility of the \(\Omega\)-grading was used in the second and the last of the above equalities.
• we used “\(+\)” to denote the group operation on \(\Omega,\) since \(S\) is commutative and therefore every grading on \(S\) can also be induced by a grading by an abelian group.

It follows from the above display that
\[\ord_\Omega(f) \preceq_\Omega \ord_\Omega(f_1)\]
where “\(\preceq_\Omega\)” is the ordering on \(\Omega.\) Now, since the \(\Sigma\)-grading is monomial compatible, and since \(g_{i_1}\) is \(\Sigma\)-homogeneous, it follows that
\[\supp_\Sigma(f_1) \subseteq \supp_\Sigma(f)\]
The shallowness of the \(\Sigma\)-grading then implies that if we keep repeating this process to construct \(f_2\) from \(f_1\) and \(f_3\) from \(f_2\) and so on, then from a step onward \(f_0 := f, f_1, f_2, \ldots, \) would be linearly dependent over \(\kk.\) On the other hand, since
\[\nu_{\preceq’}(f_0) \prec’ \nu_{\preceq’}(f_1) \prec’ \cdots,\]
Lemma 1 implies that as long as \(f_k\) is nonzero, it would be linearly independent of \(f_0, \ldots, f_{k-1}.\) Consequently, the process must stop, and there is \(k\) such that \(f_k = 0.\) In particular, there is \(m \geq 0\) such that \[\ord_\Omega(f_0) = \cdots = \ord_\Omega(f_m) \prec_\Omega \ord_\Omega(f_{m+1})\]where \(\prec_\Omega\) denotes “strictly smaller” with respect to \(\preceq_\Omega.\) This means \[\ord_\Omega(f) = \ord_\Omega(h_1) = \cdots = \ord_\Omega(h_{m+1})\]and\[\ord_\Omega(f – h_1 – \cdots – h_{m+1}) \succ_\Omega \ord_\Omega(f)\]It follows that \[\In_\Omega(f) = \In_\Omega(h_1 + \cdots + h_{m+1}) = \In_\Omega(h_1) + \cdots + \In_\Omega(h_{m+1})\] Since \(\In_\Omega(h_1) + \cdots + \In_\Omega(h_{m+1})\) is in the ideal generated by \(\In_\Omega(g_{i_1}), \ldots, \In_\Omega(g_{i_{m+1}})\), we are done!

We also have analogues of the corollaries to Theorem 1 from the preceding post. Corollary 1 below fails if we allow \(J\) to be non-homogeneous, as evidenced by taking \(I := \langle x \rangle\) and \(J := \langle x + x^2 \rangle\). I suspect Corollary 2 remains true for non-homogeneous ideals, but need to think harder.

Corollary 1. Let \(I \supseteq J\) be ideals of \(S := \kk[x_1, \ldots, x_n]\) such that \(J\) is homogeneous with respect to a shallow monomial grading on \(S.\) If \(I \supsetneqq J\), then \(\In_\preceq(I) \supsetneqq \In_\preceq(J)\) for every linear group order \(\preceq\) on \(\znpos.\)

Proof. Pick homogeneous \(g_1, \ldots, g_N \in J\) such that \(\In_\preceq(g_i)\), \(i = 1, \ldots, N\), generate \(\In_\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 \(S := \kk[x_1, \ldots, x_n]\) which is homogeneous with respect to a shallow monomial grading on \(S.\) There can not exist linear group orders \(\preceq_1, \preceq_2\) on \(\znpos\) such that \(\In_{\preceq_1}(I) \subsetneqq \In_{\preceq_2}(I)\).

Proof. Write \(J_k := \In_{\preceq_k}(I)\), \(k = 1, 2\). Assume to the contrary that \(J_1 \subsetneqq J_2\). Then we can choose homogeneous \(g_1, \ldots, g_N \in I\) such that \(\In_{\preceq_2}(g_i)\), \(i = 1, \ldots, N\), generate \(J_1\). Choose \(f \in I\) such that \(\In_{\preceq_2}(f) \not\in J_1.\) Let \(r\) be the remainder of the initial-term-cancelling-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\) are homogeneous elements in \(I\) such that \(\In_{\preceq_1}(h_1), \ldots, \In_{\preceq_1}(h_M)\) generate \(J_1,\) then initial-term-cancelling-division of \(r\) by \(h_1, \ldots, h_M\) with respect to \(\preceq_1\) implies that \(r \not\in I,\) which is a contradiction. This completes the proof.

The notion of reduced initial basis described in the preceding post on division of power series also applies to an arbitrary linear group order on \(\znpos\): a finite ordered collection of elements \(g_1, \ldots, g_N\) from an ideal \(I\) of \(S\) is called a reduced initial basis with respect to a linear group 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.\)

If \(I\) is homogeneous with respect to a shallow monomial \(\Sigma\)-grading on \(S\), then a reduced initial basis for \(I\) can be produced by taking a minimal set of \(\Sigma\)-homogeneous elements of \(I\) whose initial terms generate \(\In_\preceq(I)\) and then replacing each element by the remainder of the initial-term-cancelling-division by other elements.

Corollary 3. Let \(I\) be an ideal of \(S := \kk[x_1, \ldots, x_n]\) which is homogeneous with respect to a shallow monomial \(\Sigma\)-grading on \(S\), and \(\preceq, \preceq’\) be linear group orders on \(\znpos\) such that
\[\In_\preceq(I) = \In_{\preceq’}(I)\]
Then any reduced \(\Sigma\)-homogeneous initial basis of \(I\) with respect to one of \(\preceq, \preceq’\) is also a reduced initial basis with respect to the other one. Moreover, the number of elements on a reduced $\Sigma$-homogeneous initial basis of $I$ is also uniquely determined by $I$.

Proof. Indeed, pick a reduced initial basis \(g_1, \ldots, g_N\) of \(I\) with respect to \(\preceq\). Let \(\alpha_i := \nu_{\preceq}(g_i),\) \(i = 1, \ldots, n.\) Fix \(i.\) Since \(\In_{\preceq’}(I)\) is also 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\) it must be divisible by \(x^{\alpha_i}.\) Since \(\alpha_i\) is also in the support of \(g_i,\) and \(g_i\) is \(\Sigma\)-homogeneous and the grading by \(\Sigma\) is shallow, Remark 1 above implies that the only monomial in \(g_i\) divisible by \(x^{\alpha_i}\) is \(x^{\alpha_i}\) itself, so that \(\nu_{\preceq’}(g_i) = \alpha_i.\) It follows that that \(\In_{\preceq’}(g_i),\) \(i = 1, \ldots, N,\) form a reduced initial basis of \(I\) with respect to \(\preceq’\) as well. The last assertion follows via the same arguments as in the beginning of the proof of Corollary 3 of the earlier post on polynomial division.

Universal Initial Bases

Theorem 2. Let \(I\) be an ideal of \(S := \kk[x_1, \ldots, x_n]\) which is homogeneous with respect to a shallow monomial grading on \(S\) by a group \(\Sigma.\) There are finitely many distinct initial ideals of \(I\) with respect to linear group orders. In particular, there is a finite subset of \(\Sigma\)-homogeneous elements of \(I\) such that for every linear group order on \(\znpos,\) the initial terms of polynomials in that subset generate the initial ideal of \(I.\)

Proof. Regarding the first assertion, Logar’s argument for the leading ideal case from the proof of Theorem 2 in the previous post on polynomial division applies almost immediately to the present situation – one only needs to choose homogeneous elements in every case and replace “\(\ld\)” with “\(\In\)”. The second assertion then follows from Corollary 3 to Theorem 1.

We now present two successively stronger versions of Theorem 2.

Theorem 2*. Theorem 2 continues to hold if “linear group orders on \(\znpos\)” are substituted by “totally ordered monomial gradings on \(S := \kk[x_1, \ldots, x_n].\)” In other words, if \(I\) is a homogeneous ideal of \(S\) with respect to a shallow monomial grading on \(S,\) then there are finitely many distinct initial ideals of \(I\) with respect to totally ordered monomial gradings on \(S.\) In particular, there is a finite subset of \(\Sigma\)-homogeneous elements of \(I\) such that for every totally ordered monomial gradings on \(S,\) the initial forms of polynomials in that subset generate the initial ideal of \(I.\)

Proof. Theorem 2 implies that there is a finite subset of of \(\Sigma\)-homogeneous elements of \(I\) such that for every linear group order on \(\znpos,\) the initial terms of polynomials in that subset generate the initial ideal of \(I.\) Now apply Theorem 1*.

Theorem 2**. Theorem 2* holds for all (i.e. not necessarily homogeneous) ideals of \(S := \kk[x_1, \ldots, x_n].\) In other words, if \(I\) is an ideal of \(S,\) then there are finitely many distinct initial ideals of \(I\) with respect to totally ordered monomial gradings on \(S.\) In particular, there is a finite subset of elements of \(I\) such that for every totally ordered monomial gradings on \(S,\) the initial forms of polynomials in that subset generate the initial ideal of \(I.\)

Proof. Indeed, given an ideal \(I\) of \(S,\) take another variable \(x_0,\) and consider the homogenization (in the usual sense) \(I^h\) of \(I\) with respect to \(x_0, \ldots, x_n,\) i.e. \(I^h\) is the ideal of \(\kk[x_0, \ldots, x_n]\) generated by \[f^h := x_0^{\eta(f)}f(x_1/x_0^{\eta_1}, \ldots, x_n/x_0^{\eta_n})\]for all \(f \in I\). Given a monomial grading on \(S\) by a totally ordered group \(\Omega\), consider the induced \(\Omega\)-grading on \(S’ := \kk[x_0, \ldots, x_n]\) defined by: \[S’_\omega := \{f \in S’: f|_{x_0 = 1} \in S_\omega\}\]Since the \(\Omega\)-grading on \(S\) is monomial compatible, so is the grading on \(S’.\) For each \(f \in I,\) it is straightforward to check that \[(\In_\Omega(f^h))|_{x_0 = 1} = \In_\Omega(f)\] On the other hand, if \(f\) is a homogeneous element of \(I^h,\) then the monomials in the support of \(f\) are in one-to-one correspondence with the monomials in the support of \(f|_{x_0 = 1}\) and \[(\In_\Omega(f))|_{x_0 = 1} = \In_\Omega(f|_{x_0 = 1})\]By Theorem 2* there are homogeneous \(f_1, \ldots, f_N \in I^h\) independent of \(\Omega\) such that \(\In_\Omega(I^h)\) is generated by \(\In_\Omega(f_i),\) \(i = 1, \ldots, N.\) It then follows from the above discussion that \(\In_\Omega(I)\) is generated by \(\In_\Omega(f_i|_{x_0 = 1}),\) \(i = 1, \ldots, N.\) This proves Theorem 2**.

Every initial ideal comes from a weight

In this section we consider weighted orders as opposed to weighted degrees from the previous post. Every \(\omega \in \rr^n\) defines a weighted order, and for \(f \in \kk[x_1, \ldots, x_n]\) we write \(\In_\omega(f)\) for the corresponding initial term of \(f\). Given an ideal \(I\) of \(\kk[x_1, \ldots, x_n]\) we similarly write \(\In_\omega(I)\) for its leading ideal generated by \(\In_\omega(f)\) for all \(f \in I\).

Theorem 3. Let \(I\) be an ideal of \(S := \kk[x_1, \ldots, x_n]\) which is homogeneous with respect to a shallow monomial grading on \(S.\) For every linear group order \(\preceq\) on \(\znpos,\) there is \(\omega = (\omega_1, \ldots, \omega_n) \in \zz^n\) such that \(\In_\omega(I) = \In_\preceq(I)\) (in particular, this means that \(\In_\omega(I)\) is a monomial ideal). Moreover, one can ensure that

1. \(\omega_i \neq 0\) for all \(i,\)
2. \(\omega_i > 0\) if and only if \(e_i \succ 0\),
3. \(\omega_i < 0\) if and only if \(e_i \prec 0,\)

where \(e_i\) is the standard \(i\)-th basis vector of \(\zz^n.\)

Proof. Fix \(g_1, \ldots, g_N \in I\) such that \(\In_\preceq(g_i)\), \(i = 1, \ldots, N\), generate \(\In_\preceq(I)\). Write \[g_i = c_{i0} x^{\alpha_{i0}} + \cdots + c_{iN_i}x^{\alpha_{iN_i}}\]with \(\alpha_{i0} = \nu_\preceq(g_i)\). Let \(C\) be the set of all \(\omega \in \rr^n\) such that

1. \(\langle \omega, \alpha_{i0} – \alpha_{ij} \rangle \leq 0,\) \( i = 1, \ldots, N,\) \(j = 1, \ldots, N_i,\)
2. \(\omega_i \geq 0\) for all \(i\) such that \(e_i \succ 0\),
3. \(\omega_i \leq 0\) for all \(i\) such that \(e_i \prec 0.\)

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\) and \(\epsilon_i e_i\), \(i = 1, \ldots, n,\) where \(\epsilon_i = \pm 1\) depending on wheter \(e_i \succ 0\) or \(e_i \prec 0.\) (Notice the switch from \(\alpha_{i0} – \alpha_{ij}\) from the first condition defining \(C\) to \(\alpha_{ij} – \alpha_{i0}\) in the definition of \(C’.\)) 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_k\epsilon_ke_k\]for some nonnegative integers \(r_1, \ldots, r_n\). Since \(\preceq\) is compatible with addition on \(\znpos,\) 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 \(\zz^n\), and if \(\omega \in C^0 \cap \zz^n\), then \(\In_\omega(g_i) = c_{i0}x^{\alpha_{i0}}\). Since \(\In_\preceq(I)\) is generated by \(c_{i0}x^{\alpha_{i0}}\), \(i = 1, \ldots, N,\) it follows that \(\In_\omega(I) \supseteq \In_\preceq(I)\). If this containment were proper, then since \(\In_\preceq(I)\) is a monomial (and therefore, homogeneous in the usual sense) ideal, 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\). It is straightforward to check that \(\preceq_\omega\) is a linear group order on \(\znpos,\) and consequently, the two preceding displays would contradict Corollary 2 to Theorem 1. It follows that \(\In_\omega(I) = \In_\preceq(I),\) as required.

Remark. I think there are stronger versions of Theorem 3 analogous to the stronger versions of Theorem 2 above. In particular, I think the following is true, although I am not able to prove it.

Theorem 3** (I don’t know whether it is true). Theorem 3 continues to hold even if \(I\) is not homogeneous and “linear group orders on \(\znpos\)” are substituted by “totally ordered monomial gradings on \(S := \kk[x_1, \ldots, x_n].\)” In other words, if \(I\) is any ideal of \(S,\) then for every monomial grading on \(S\) by a totally ordered group \(\Omega,\) there is \(\omega = (\omega_1, \ldots, \omega_n) \in \zz^n\) such that \(\In_\omega(I) = \In_\Omega(I).\) Moreover, one can ensure that

1. \(\omega_i = 0\) if and only if \(\deg_\Omega(x_i) = 0_\Omega,\) where \(0_\Omega\) is the identity element of \(\Omega,\)
2. \(\omega_i > 0\) if and only if \(\deg_\Omega(x_i) \succ_\Omega 0_\Omega\),
3. \(\omega_i < 0\) if and only if \(\deg_\Omega(x_i) \prec_\Omega 0_\Omega,\)

where \(e_i\) is the standard \(i\)-th basis vector of \(\zz^n.\)