Motivation: So apparently there's some sort of sport competition currently going on where I live, which leads to countries being given an element of $\mathbb{N}^3$ called a “medal count”, and not everyone agrees on what the best way to turn the medal counts into a total order on countries. Now fortunately, there is a mathematical notion we can relate this to: monomial orders. The two seemingly favorite ways of counting medals are lexicographic (“a gold medal is worth more than any number of silver”) and graded lexicographic (= degree lexicographic: “the total number of medals is the most important”); but weighted orders are also possible, and the New York Times even has a mathematically interesting interactive page showing how various countries rank according to the weights of the weighted order. This leads me to wonder what the space of all monomial orders actually looks like.
Let us fix $k\geq 1$ (the number of kinds of medals, if you wish, or the number of variables if you are thinking of orders on monomials over a set of indeterminates). By a monomial order on the free monoid with $k$ generators $\mathbb{N}^k$ we will mean a total order $\leq$ on $\mathbb{N}^k$ that is compatible with addition in the sense that:
we have $0\leq u$ for each $u\in\mathbb{N}^k$, and
if $u\leq v$ and $w\in\mathbb{N}^k$, then $u+w\leq v+w$.
(When the term “monomial order” is used, which is typically in the context of polynomial rings, elements of free monoid with $k$ generators, a.k.a., “monomials”, are usually written $x_1^{r_1}\cdots x_k^{r_k}$ where $x_1,\ldots,x_k$ are said generators, the monoid operation being denoted multiplicatively, and this corresponds to $(r_1,\ldots,r_k) \in \mathbb{N}^k$ above with the operation being denoted additively. But additive notation is much more convenient for the present question, so I will stick to it.)
Notation: Let $\mathcal{M}(k)$ be the set of all monomial orders on $\mathbb{N}^k$.
My question will basically “what kind of (topological? geometrical?) structure does $\mathcal{M}(k)$ have?”. But because it seems highly relevant, I would first like to state a description in terms of weight vectors. Before this, let me give a few standard examples.
Standard examples of monomial orders are:
lexicographic order, in which we order $(u_1,\ldots,u_k)$ and $(v_1,\ldots,v_k)$ by comparing first $u_1$ with $v_1$, then $u_2$ with $v_2$, and so on until a difference is found, which determines the order;
graded lexicographic order, in which we first compare $u_1+\cdots+u_k$ with $v_1+\cdots+v_k$ and, if they are equal, compare lexicographically;
graded reverse lexicographic order, in which we first compare $u_1+\cdots+u_k$, then $u_1+\cdots+u_{k-1}$, then $u_1+\cdots+u_{k-2}$, and so on down to $u_1$, with the corresponding $v$ values; and of course,
if $\lambda_1,\ldots,\lambda_k$ are nonnegative reals, we can define the weighted order in which we just compare $\lambda_1 u_1 + \cdots + \lambda_k u_k$ with $\lambda_1 v_1 + \cdots + \lambda_k v_k$, but to avoid cases of equality we will want to assume here that $\lambda_1,\ldots,\lambda_k$ are $\mathbb{Q}$-linearly independent.
In all these examples, elements of $\mathbb{N}^k$ are compared by comparing some linear form with nonnegative coefficients (“weights” $\lambda^{(1)}_1,\ldots,\lambda^{(1)}_k$), then, in case of equality, another ($\lambda^{(2)}$), and so on. A theorem by Lorenzo Robbiano (“Term orderings on the polynomial ring”, p. 513–517 in: Caviness (ed.), EUROCAL '85 (Linz 1985), Springer LNCS 204) states that this is always the case, and precisely classifies monomial orders on $\mathbb{N}^k$:
Theorem (Robbiano, 1985): Denote by $\mathcal{B}(d)$ the set of elements (“weight vectors”) $\lambda\in\mathbb{R}^k$ such that the $\mathbb{Q}$-span of the coordinates $\lambda_1,\ldots,\lambda_k$ has dimension $d$ as a $\mathbb{Q}$-vector space; and let $\mathcal{A}(d)$ be the quotient of $\mathcal{B}(d)$ by multiplication by positive reals (i.e., $\mathcal{A}(d) := \mathcal{B}(d)/{\sim}$ where $\lambda\sim\mu$ iff there is $t\in\mathbb{R} _ {>0}$ such that $\mu = t\lambda$). Then the monomial orders on $\mathbb{N}^k$ are precisely described by the following data:
a partition $d_1 + \cdots + d_s = k$ of $k$,
elements $\bar\lambda^{(1)},\ldots,\bar\lambda^{(s)}$ of $\mathcal{A}(d_1),\ldots,\mathcal{A}(d_s)$ respectively, such that (if we write $\lambda^{(i)}$ for an arbitrary representative in $\mathcal{B}(d_i)$ of $\bar\lambda^{(i)}$):
each $\lambda^{(i)}$ is orthogonal (as an element of $\mathbb{R}^k$) to all the $\lambda^{(j)}$ for $j<i$, and
for every nonzero $v\in\mathbb{N}^k$, the first nonzero coordinate of $\lambda^{(1)}\cdot v, \ldots, \lambda^{(s)}\cdot v$ is positive;
— precisely, given such data, the order between $u$ and $v$ is defined as the lexicographic comparison between $(\lambda^{(1)}\cdot u,\ldots,\lambda^{(s)}\cdot u)$ and $(\lambda^{(1)}\cdot v,\ldots,\lambda^{(s)}\cdot v)$.
(Here, $\lambda\cdot v$ refers to the standard scalar product $\sum_{i=1}^k \lambda_i v_i$ on $\mathbb{R}^k$, of course, and this is also the one implicit in the word “orthogonal”.)
The orthogonality condition is used to guarantee uniqueness of the $\lambda^{(i)}$ (up to $\sim$, that is), and can be achieved by a standard Gram-Schmidt construction. The positivity condition is used to achieve (1) above, and it is far less clear to me how it can be checked algorithmically (but I note that, in the special case where $s=1$ so $d_1 = k$, this second condition simply means that $\lambda^{(1)}_1,\ldots,\lambda^{(1)}_k$ are all positive).
As examples of this theorem, lexicographic ordering is represented by $\lambda^{(1)},\ldots,\lambda^{(s)}$ being $(1,0,\ldots,0)$ through $(0,\ldots,0,1)$; graded lexicographic ordering by $(1,1,\ldots,1)$ and then $(1,0,\ldots,0)$ through $(0,\ldots,0,1,0)$, except that we need apply Gram-Schmidt to make them orthogonal (i.e. subtract $(\frac{1}{k},\ldots,\frac{1}{k})$ to all except the first); and graded reverse lexicographic ordering by $(1,1,\ldots,1)$, $(1,\ldots,1,0)$ through $(1,0,\ldots,0)$, which again should be made orthogonal through a Gram-Schmidt process first; in these three examples, $s=k$. At the other extreme, the simple weighted order with $\mathbb{Q}$-linearly independent weights $\lambda_1,\ldots,\lambda_k$ corresponds to the case where $s=1$ and there is just one weight vector $\lambda^{(1)}$.
Now this is a fine description of $\mathcal{M}(k)$ as a set, but I am left wondering what it “looks like” geometrically. Clearly, a “big part” of it is simply $\mathcal{B}(k)$, which is simple enough to visualize; but what about the rest? We have a map from $\mathcal{M}(k)$ to the $(k-1)$-dimensional simplex defined by taking a monomial order to $\lambda^{(1)}$ renormalized to have sum $1$ (and this is an injection on $\mathcal{B}(k)$), and my intuition is that $\mathcal{M}(k)$ is some kind of “blowup” of this, but I don't know how to make it precise (I am reminisced of Zariski's “voûte étoilée”, but I don't understand it well). So, anyway:
Soft question: Can we give $\mathcal{M}(k)$ a geometrical structure? At the very least, a topology, but perhaps some kind of (generalized?) manifold structure. How should we visualize it?
(One topology which comes to my mind is the one having a subbasis consisting of the sets of orders $({<}) \in \mathcal{M}(k)$ such that $u<v$, for $u,v$ ranging in $\mathbb{N}^k$. I don't know if this is the most sensible one, but if you want a precise question and not a soft one, “is $\mathcal{M}(k)$ equipped with this topology homemorphic to a $k$-dimensional ball?” is a possibility.)
