# Polynomial division over valued fields – Part II (Stronger universal bases)

$\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**.