Abstract
Monomials are products of variables. Examples of monomials in three variables include:
x3, xy2z, xy2, y4, x2z2.
A monomial order is a way to compare any two monomials and determine a “winner” in a consistent manner.
Formally, a monomial order ≤τ is an order in the set of monomials satisfying:
- (i) (Trichotomy) If v and w are monomials then exactly one of the following three is true
v<τ w,v=worw<τ v
- (ii) (Reflexivity) w ≤τ w for all monomials w.
- (iii) (Anti-symmetry) If v and w are monomials such w ≤τ v and v ≤τ v then v = w.
- (iv) (Transitivity) If u, v and w are monomials such u ≤τ v and v ≤τ w then u ≤τ w.
- (v) (Consistency) If v and w are monomials and v ≤τ w then u·v ≤τ u·w for all monomials u.
- (vi) (Smallest element) 1 ≤τ w for all monomials w.
The three classical monomial orders are the lexicographic order
y4 ≤lex xy2 ≤lex xy2z ≤lex x2z2 ≤lex x3.
(how high a monomial is depends on how high the powers of its variables, when written in
alphabetical order, are); the graded lexicographc order
xy2 ≤glex x3 ≤glex y4 ≤glex xy2z ≤glex x2z2
(how high a monomial is depends first on the sum of the powers of its variables and in case of ties, it depends on how high the powers of its variables, when written in alphabetical order, are); and the graded reverse lexicographic order
xy2 ≤grevlex x3 ≤grevlex x2z2 ≤grevlex xy2z ≤grevlex y4
(how high a monomial is depends first on the sum of the powers of its variables and in case of ties, it depends on how low the powers of its variables, when written in reverse alphabetical order, are).
Some monomial orders have the property of being uniquely determined by its induced orders. What this means is that if we know exactly how monomials involving only the variables x and y are ordered, along with with how monomials involving only the variables x and z are orderd, and how monomials involving only the variables y and z are ordered, then we can determine how all monomials are ordered.
It is known that, in three variables or more, the lexicographic order is uniquely determined by its induced orders, and that in, four variables or more, the graded lexicographic and the graded reverse lexicographic orders are uniquely determined by its induced orders.
It is also known that regardless of how many variables are considered there are monomial orders that are not uniquely determined by its induced orders. And that for any number of variables, over three, there are infinitely many different monomial orders that are uniquely determined by its induced orders.
This project intends to study different aspects of monomial orders that are uniquely determined by their induced orders (i.e. reconstructible monomial orders), with a particular focus towards determining all monomial orders in three, four (and possibly five) variables that are reconstructible, along with the determination of an algorithm that would allow for (i) the determination of whether a monomial is reconstructible or not and (ii) the process of the reconstruction.