There are k! distinct lex, grlex, and grevlex orders on a polynomial ring in k indeterminates

Prove that there are k! distinct lex orders on F[x_1,\ldots,x_k]. Show similarly that there are k! distinct grlex and grevlex orders.


Each lex (and grlex and grevlex) order on F[x_1,\ldots,x_k] is (by definition) induced by a linear order of the indeterminates x_1, \ldots, x_k. Each linear order of [1,k] certainly corresponds to a permutation, so that there are at most |S_k| = k! distinct lex (and grlex and grevlex) orders. It remains to be shown that distinct permutations \tau \in S_k induce distinct monomial orders.

Suppose >_1 and >_2 are distinct linear orders of [1,k]. That is, there exist a,b \in [1,k] such that x_a >_1 x_b and x_b >_2 x_a. We immediately see that the lex, grlex, and grevlex orders induced by >_1 and >_2 are distinct, as those orders coincide with >_1 and >_2 on the set \{x_1, \ldots, x_k\}.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: