10
$\begingroup$

An ordering of monomials in the free associative algebra $k\langle x_1,\ldots,x_n\rangle$ is called a monomial ordering (EDIT: it seems that an equally common term used in this context is "term ordering", while "monomial ordering" only requires the first condition below) if

  • it is a well-ordering;

  • for three monomials $a,b,c$ we have $ac<bc$ and $ca<cb$ whenever $a<b$.

My main general question is whether there are any general classification results for monomial orderings. A very mild particular case which is of interest already would be to assume that our ordering extends the partial order given by the total degree.

I spent some time thinking about it, and realised that I lack good intuition about it. In the commutative case, the situation is quite straightforward: every order is an appropriate superposition of several partial orderings given by assigning some weights to generators, as proved by L. Robbiano in the paper "Term orderings on the polynomial ring" MR0826583 (87e:13006). In the noncommutative case, I do not expect any description which is remotely as economic (though who knows), but even partial results could be helpful.

My motivation, as it probably always the case, is coming from Gröbner bases: there are several situations where I could guess a good ordering solving some problem, but there are cases where my imagination is not enough, and I would like to know if there are ways to look for a "good" ordering in a way which is as far from mere guessing as possible.

Improve this question
$\endgroup$
4
  • $\begingroup$ Any ordering of the free group gives a noncommutative monomial ordering. There is plenty of literature on orderings of the free group, so that might be a good place to get started. $\endgroup$
    – zeb
    Commented Feb 17, 2012 at 14:49
  • $\begingroup$ I would be much obliged if you could be a little bit more precise than that and point me to some literature discussing this question. What I was able to find out so far were some papers where right orderings were discussed, and some other papers discussing orderings of groups which are very far from free. $\endgroup$
    – Vladimir Dotsenko
    Commented Feb 17, 2012 at 15:11
  • $\begingroup$ P.S. Of course I also saw some examples of orderings for the free groups, but I don't think that I saw anything remotely similar to even a discussion of a question of classification. However, I am sure there are things I overlooked, and I would be happy to have a precise pointer (alas that "plenty of literature" you are referring to seems to be somewhat elusive). $\endgroup$
    – Vladimir Dotsenko
    Commented Feb 17, 2012 at 15:27
  • $\begingroup$ You are probably right - I just remembered seeing papers about orderable groups that mentioned several orderings of the free group, and assumed it was a well understood topic. $\endgroup$
    – zeb
    Commented Feb 22, 2012 at 20:01

2 Answers 2

Reset to default
3
$\begingroup$

There are very few results as far as classification goes. This paper of Hermiller gives an idea of the messiness of the noncommutative case. Martin, Scott, Perlo-Freeman, and Prohle have all done work on termination orderings that may be relevant. This paper has some of that work.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Having had a quick glance at the first paper, I should probably edit my question, since that paper implies that what I am looking at is term orderings (they use monomial orderings for any well-ordered structure, not necessarily compatible with the product)! But these references are very helpful nevertheless, thanks a lot! $\endgroup$
    – Vladimir Dotsenko
    Commented Feb 22, 2012 at 23:12
  • $\begingroup$ Just out of curiousity, after looking at the title of you PhD thesis on your webpage, is your thesis available free of charge somewhere, or one has to buy it from one of many places (including Amazon!) where it is listed for sale? $\endgroup$
    – Vladimir Dotsenko
    Commented Feb 22, 2012 at 23:20
  • $\begingroup$ Vladimir, the dissertation itself is not, but the Weight Ideal paper on arXiv contains results probably most relevant to your question about classification (I was thinking about this question then too)! $\endgroup$
    – Jeremiah Johnson
    Commented Mar 2, 2012 at 12:25
  • 1
    $\begingroup$ Thanks. [The idea of making people pay to view your thesis still appears a bit puzzling, but it's of course your choice!] $\endgroup$
    – Vladimir Dotsenko
    Commented Mar 12, 2012 at 14:32
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Apr 16, 2023 at 15:22
1
$\begingroup$

Monomial orderings are relevant to Grobner basis theory, and perhaps the notion of involutive systems is relevant to your question: as a start see

Evans, G.A. and Wensley, C.D. Complete involutive rewriting systems. J. Symbolic Comput. 42~(11-12) (2007) 1034--1051.

and Gareth Evans Thesis: math.RA/0602140.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Of course they are relevant to Grobner bases - I actually mentioned it in the question! I will check out "involutive systems", though if it is about rewriting systems, as opposed to Grobner basis, the compatibility with the product would probably be missing or not that important at least? $\endgroup$
    – Vladimir Dotsenko
    Commented Feb 22, 2012 at 23:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .