There are infinitely many monomial orders

Question

Show that if $n ≥ 2$ there are infinitely many monomial orders on $k[x_1, \ldots , x_n]$.

I think it is Robbiano theorem (with the exception $n>2$) at the link below but i can't understand proof: why we take $A,B$ from $\mathbb N^n $?

http://www.ces.clemson.edu/~janoski/reu/2012/REULec2Mohammed.pdf

If you have different proof other than link please say it or help about proof at link.

Answer 1

A monomial order on $k[x_1,\dots,x_n]$ is the same as an order on $\mathbb N^n$, because we can identify a monomial $x_1^{a_1}\cdots x_n^{a_n}$ with the vector $(a_1,\dots,a_n) \in \mathbb N^n$.

The rest of the proof is not very clearly written. Here's the beginning of an explanation. To show that $\geq_u \neq \geq_v$, we have to see that there exists $A,B \in \mathbb N^n$ with $A \geq_u B$ but with $B \geq_v A$. Clearly, this is equivalent to showing that there exists $C \in \mathbb Z^n$ with $C \cdot u \geq 0$, but $C \cdot v \leq 0$, where, as in the proof, $u=(1,\gamma,\gamma^2,\dots,\gamma^{n-1})$ and $v=(1,\tau,\dots,\tau^{n-1})$.

If this were not true, then the sign of $C \cdot u$ and $C \cdot v$ would be the same for all $C$. But this is equivalent to saying that $(C \cdot u)(C \cdot v) > 0$ for all $C$.

But if $(C \cdot u)(C \cdot v)=0$, then we would have a relation of the form $$ c_0^2 + c_0c_1(\gamma + \tau) + c_0c_2(\gamma^2+\tau^2)+c_1^2(\gamma \tau)+\cdots = 0 $$

But this shouldn't be possible for different transcendental $\gamma,\tau$, i.e. they are linearly independent over $\mathbb Q$.

Answer 2

A monomial $x_1^{a_1}\cdots x_n^{a_n}$ can be identified with the vector $A=(a_1,\dots,a_n)$ from $\mathbb N^n$.

Let's prove that theorem for $n=2$ which is actually enough (why?). We know that $a_1+a_2\gamma>0$ iff $a_1+a_2\tau>0$, where $a_1,a_2\in\mathbb Z$, and want to prove that $\gamma=\tau$. If, let's say, $\gamma >\tau$, then take a rational number $q=-a/b$ (with $b>0$) such that $\gamma>q>\tau$. Thus we have $a+b\gamma>0>a+b\tau$, a contradiction.

Answer 3

---

Proposition:

There is an infinite number of monomial orders in $\mathbb{K[x_1, \cdots, x_n]}$ if $n \ge 2$.

Proof:

For n=2:

Define weights $w_1 \ge 0$ and $w_2 \ge 0$, such that $w=(w_1,w_2)$ and $w_1 + w_2=1$.

Then we define $(a_1, a_2) \ge_{w} (b_1,b_2)$ if $w_1 a_1 + w_2 a_2 \ge w_1 b_1 + w_2 b_2$.

We should first verify (and this did not happen in the proof of "Robbiano's theorem) that $>_{w}$ is a well defined monomial order. That is we need to prove (and we will at each step) that

1. $\ge_{w}$ is a total order. That is, either $a >_w b$, or $a <_w b$, or $a=_wb$ . Since for any couple $a= (a_1, a_2) \in \mathbb{N}^2, b=(b_1,b_2) \in \mathbb{N}^2$, we have that either $w_1 a_1 + w_2 a_2 < w_1 b_1 + w_2 b_2$, or $w_1 a_1 + w_2 a_2 = w_1 b_1 + w_2 b_2$, or $w_1 a_1 + w_2 a_2 > w_1 b_1 + w_2 b_2$, then $>_w$ is a well a total order.

2. "$\ge_w$" is compatible with multiplication (or sum in this case). That is, if $a \ge_w b$, then for any $c=(c_1, c_2) \in \mathbb{N}^2$, $a+c \le_w b+c$.

   We show this. We have that, since $w_1 (a_1 + c_1) + w_2(a_2+c_2) = (w_1 a_1 + w_2 a_2 ) + (w_1 c_1 + w_2 c_2) \ge (w_1 b_1 + w_2 b_2) + (w_1 c_1+w_2 c_2) = w_1(b_1 + c_1) + w_2(b_2 + c_2)$ then $a+c \ge_w b+c$.

   Here we used the fact that $a \ge_w b$, and that $w_i \ge 0$, $i=1,2$.

3. $\ge_w$ is a well-ordering. That is, there is a minimum. This is true from $a \ge_w 0$. That is $0 w_1 + 0 w_2 = 0 \le a_1 w_1 + a_2 w_2$, for all $(a_1,a_2) \in \mathbb{N}$.

This shows that $\ge_w$ is a valid monomial order. Now, count how many weights can you build with $w_1 \ge 0, w_2 \ge 0$, $w_1 + w_2=1$? As many as $\aleph_1$.

Examples: The lexicographic order is found by choosing $w=(1,0)$, the reverse lexicographic order is found by choosing $w=(0,1)$, the pure grading order is found by choosing $w=(0.5, 0.5)$. Any order $w=(a,b)$ with $a>b$ gives priority to the first variable. If $b>a$ the priority is given to the second variable. The level of priority for the first variable ranges along the continuous interval $a \in [0,1]$. The case $a>b$ or $a<b$ is a graded lexicographic order (or reverse lexicographic order).

We still need to show that if there are two weights $w=(w_1, w_2)$, and $v=(v_1,v_2)$, such that $w \ne v$ then we can distinguish one order from the other. That is $\ge_w \ne \ge_v$ . For the order $\ge_w$ we have that if $a=(a_1, a_2) \ge_w (b_1, b_2)$ then \begin{equation} w_1 a_1 + w_2 a_2 \ge w_1 b_1 + w_2 b_2 \end{equation} We want to find $a,b$ such that \begin{equation} v_1 a_1 + v_2 a_2 < v_1 b_2 + v_2 b_2 \end{equation} This will make the two weights distinct. We can rewrite these two equations, by defining $c_1 = a_1 - b_1, c_2=a_2-b_2$, as \begin{eqnarray} w_1 c_1 + w_2 c_2 \ge 0 \nonumber \\ v_1 c_1 + v_2 c_2 < 0 \nonumber \end{eqnarray}

Since $w_1 = 1 - w_2$, and $v_1 = 1 - v_2$, then we write

\begin{eqnarray} w_1 c_1 + (1 - w_1) c_2 \ge 0 \nonumber \\ v_1 c_1 + (1- v_1) c_2 < 0 \nonumber \end{eqnarray} or (assuming $w_1 \ne 1)$. We are counting infinite orders and we do not care about not counting this particular one, still if $w_1 = 1$, this is the reverse lexicographic order, which is a valid order. We have then \begin{eqnarray} c_2 &\ge& \frac{ w_1 c_1}{1 - w_1} \quad \quad (1) \\ c_2 &<& \frac{ v_1 c_1}{1 - v_1} \quad \quad (2) \end{eqnarray}

The first equation (1) corresponds to a half-plane (in the $(c_1,c_2)$ coefficients) above the line $c_2 = w_1 c_1/(1-w_1)$, which goes through the origin. The second equation (2) corresponds to the lower half plane under the line $c_2 = v_1 c/(1 - v_1)$ through the origin. Since the two lines do not have the same slope (otherwise $w=v$ ), there is an angular intersection with infinite many points $(c_1, c_2)$ such that the two conditions are satisfied.

The pass to $\mathbb{N}^n$. Is trivial. Think of $w=(w_1, \cdots, w_n)$, such that $w_i \ge 0$, and $\sum_i w_i=1$. Only a bit more of writing....