Monthly Archives: July 2022

Polynomial division over valued fields – Part I (Chan-Maclagan’s Algorithm for Homogeneous Divisors)

$\DeclareMathOperator{\In}{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 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 all linear orders. 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:

  1. if \(ax^\alpha \preceq bx^\beta,\) then \(acx^{\alpha+\gamma} \preceq bcx^{\beta+\gamma}\) for all \(c \in \kk\setminus\{0\}\) and \(\gamma \in \znzero,\)
  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).\)

At this point it is useful to introduce some notation: we will use \(\prec\) to denote “strict ordering” with respect to \(\preceq,\) and write \(\preceqeq\) to denote “equivalence” with respect to \(\preceq,\) i.e.

  • \(a \prec b\) if and only if \(a \preceq b\) and \(b \not\preceq a\).
  • \(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.

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 definition 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 addition, 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.

Finally, note that if $\leq$ is a linear monomial preorder and $\preceq$ is an almost linear monomial order, then one can “refine” $\leq$ by an almost linear monomial order $\preceq’$ defined as follows: $ax^\alpha \preceq’ bx^\beta$ if and only if

  • either $ax^\alpha \leq bx^\beta$ and $bx^\beta \not\leq ax^\alpha$,
  • or $ax^\alpha \leq bx^\beta$ and $bx^\beta \leq ax^\alpha$, and $ax^\alpha \preceq bx^\beta$.

It is straightforward to check that $\preceq’$ is an almost linear monomial order on $\scrM$. Note that it is indeed possible that $\preceq’$ is “almost linear” instead of “linear”: this is the case if there are $a \neq b \in \kk\setminus \{0\}$ and $\alpha \in \znzero$ such that $ax^\alpha \leq bx^\alpha$, $bx^\alpha \leq ax^\alpha$, but neither $ax^\alpha \preceq bx^\alpha$ nor $bx^\alpha \preceq ax^\alpha$; in that case $ax^\alpha$ and $bx^\alpha$ are not related via $\preceq$.

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 linear monomial preorder $\leq$ and an almost linear monomial order $\preceq$ on $\znpos,$ let $\preceq’$ be the refinement of $\leq$ 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_{\leq}(g_1), \ldots, \In_{\leq}(g_N)$ generate $\In_{\leq}(I).$

Proof. First note that $\In_{\leq}(I)$ is also $\Sigma$-homogeneous. Indeed, if $f \in I$, then each $\Sigma$-homogeneous component $f_i$ of $f$ is also in $I$. Since the supports of the $f_i$ are mutually disjoint, $\In_{\leq}(I)$ must be the sum of some of the $\In_{\leq}(f_i)$, each of which is $\Sigma$-homogeneous. This shows that $\In_{\leq}(I)$ is $\Sigma$-homogeneous. Now pick a $\Sigma$-homogeneous $f \in I.$ Since $\In_{\preceq’}(g_1), \ldots, \In_{\preceq’}(g_N)$ generate $\In_{\preceq’}(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’}(f) = \In_{\preceq’}(q_1g_1) \prec’ \In_{\preceq’}(q_2g_2) \prec’ \cdots \prec’ \In_{\preceq’}(q_sg_s)\]
This implies that
\[\In_{\preceq’}(q_1g_1) \leq \In_{\preceq’}(q_2g_2) \leq \cdots \leq \In_{\preceq’}(q_sg_s)\]
Pick the smallest $i$ such that
\[\In_{\preceq’}(q_ig_i) \lt \In_{\preceq’}(q_{i+1}g_{i+1})\]
We claim that
\[\In_{\leq}(f) = \sum_{i’=1}^i \In_{\preceq’}(q_{i’}g_{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 = (f – \In_{\preceq’}(f)) – (h_1 – \In_{\preceq’}(f))\]
Since $\preceq’$ is an almost linear order, and $\In_{\preceq’}(f) = \In_{\preceq’}(h_1)$, it follows that

  • Every monomial term $ax^\alpha$ of $f – \In_{\preceq’}(f)$ satisfies: $ax^\alpha \succ’ \In_{\preceq’}(f)$.
  • Every monomial term $ax^\alpha$ of $h_1 – \In_{\preceq’}(f)$ satisfies: $ax^\alpha \succ’ \In_{\preceq’}(f)$.
  • Since $\preceq’$ restricts to a valuation on $\kk \setminus \{0\}$, and is compatible with multiplication by monomials, it follows that
    \[\In_{\preceq’}(f) \prec’ \In_{\preceq’}(f_1)\]
  • In addition, (the monomial in) $\In_{\preceq’}(f)$ is not in the support of $f_1$.
    Repeating this process to $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,\]

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\).

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. 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 first post on polynomial divisions via initial terms 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