Take the 2-minute tour ×

Are there any articles/books/examples where a non-standard monomial order is used? What are the applications of these monomial orders? In particular, uses in groebner bases and variable elimination.

(Nonstandard is by my definition something that is not mentioned in wikipedia, and yes, all monomial orders can be specified by weight orders, but I am after explicit monomial orders.)

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

Yes. An important concept involving non-standard monomial orderings is that of a universal Gr\"obner basis:

Let $k$ be a field and $I \subset k[x_1, ..., x_n]$ an ideal. Then, a finite subset $U \subset I$ is called a universal Groebner basis if $U$ is a Groebner basis of $I$ w.r.t. all monomial orders over $x_1, ..., x_n$.

Every such ideal $I$ has a universal Groebner basis: $I$ has only finitely many reduced Groebner bases, and the union of these is a universal Groebner basis for $I$.

There is a global "combinatorial space" for studying the transformation of Groebner bases of I under changes of the underlying monomial order: the state polytope of I, or the Groebner Fan of I. This gives rise to deep connections between the theory of convex polytopes and Groebner basis theory. These objects become very useful in algebraic geometry (in particular, in tropical geometry and in the theory of toric ideals and toric varieties).

Sturmfels's "Groebner Bases and Convex Polytopes" is a great resource for this and covers applications to toric varieties, regular triangulations, and many other problems. See also, for instance, "Groebner bases and triangulations of the second hypersimplex" by De Loera, Sturmfels, and Thomas, Combinatorica, 15, 409-424 (1995).

There is a very nice recent piece of software called GFan by Jensen for computing Groebner fans (from which universal Groebner bases may be extracted). [ http://www.math.tu-berlin.de/~jensen/software/gfan/gfan.html ]

Also, in decision methods for the theory of real closed fields, non-standard monomial orderings are used in some proof construction methods. For instance, a method due to Tiwari for computing Positivstellensatz witnesses certifying the emptiness of a semialgebraic set defined by a purely conjunctive Tarski formula involves constructing non-standard monomial orders. These non-standard orders are constructed, one after the other, so that in each successive one, a Positivstellensatz witness is made "lower" in the active monomial order and will eventually be forced to appear in a Groebner basis. See [ http://www.csl.sri.com/users/tiwari/html/csl05b.html ].

share|improve this answer
Ah, I see that this may not be what you are after, as you wanted "explicit" non-standard monomial orders. Sorry. I hope it is at least helpful in some way! –  Grant Olney Passmore Apr 6 '11 at 20:14
add comment

I saw an example on a cotangent bundle to ${\mathbb A}^n$, in which the right order to use was lex on $p_1$, revlex on $q_1$, lex on $p_2$, revlex on $q_2$, and so on. The lex/revlex is sort of natural once you view the $q$ coordinates as dual to the $p$.

share|improve this answer
add comment

Your Answer


