Talk:Lehmer code

Ambiguity about the term and its meaning

While this article used to be a redirect to a section of Permutation, it has now been made an independent article based on a translation of the French WP article on the subject. While I see not much wrong with that (provided the article is rapidly cleaned up, notably the references), I should note that the description now contradicts the one in the permutation article, in two respects: the values are taken to start at 1 rather than 0, and they count at position i the inversions {i,j} with j≤i (left inversions at i) rather than with j>i (right inversion at i).

I think there is agreement over the fact that there are basically 4 variations of the concept (listed by Knuth in exercise 5.1.1−7 (p. 19) of volume III of The art of computer programming, which number can be doubled by counting from 1 rather than from 0, and once more by complementary counting: counting non-inversions rather than inversions, so that the identity gives the highest possible values rather than the lowest), and that "inversion table" and "Lehmer code" both refer to one of those variations. However, while it is mathematically not very interesting which one is actually meant, I think WP should be clear and coherent about it (especially since people no doubt will use it as a quick reference). I don't think that there is universal agreement about which variation should be called Lehmer code; I would tend to say that the original Lehmer article should be decisive, unless a coherent (maybe different) convention is established since. Unfortunately the original article seems obscure and hard to get at (the AMS does not seem to distribute it anymore in any form), and Knuth (which I would consider an authoritative reference) refuses to use the term Lehmer code (for good historic reasons, I think), and there is no universal agreement about that term in modern usage. Some non-authoritative (but non-WP)references I found by Google:

1. Harald Fripertinger's pages (SYMMETRICA) use the convention in the Permutation article: $L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\}$ (number of right-inversions at i)
2. This page (apparently by A. Kerber) uses the same convention, even more explicitly
3. This paper published in DMCTS uses a variation counting non-inversions
4. This page related to the factoradic number system again uses the convention of numbers 1,2 in this list
5. The combinat pacage of the MuPAD system uses again the same definition (but I admit the heavily German bias in these references which are likely not all independent).
6. PlanetMath calls it Lucas-Lehmer code, gives a rather incomprehensible sentence, but clearly ties it to the factorial number system
7. A paper by Štefan Peško again agrees with this definition
8. A paper by Vincent Vajnovszki uses the convention used in the French WP (currently also in this article), except that it starts from 0 (and therefore counts inversions): $t_{i}=\#\{j<i:\sigma _{j}>\sigma _{i}\}$
9. The SAGE sytem uses the same convention as SYMMETRICA and MuPAD, of items 1,2,4,5,(6),7
10. A recent paper by P. Tarau also gives an agreeing definition.
11. The fxtbook (published as "Matters Computational") also gives a concurring definition

I'll stop my list here. Actually, I started the list with the intention to show the lack of agreement, but there appears to be a fairly strong tendency to the notion described in the Permutation article (counting inversions to the right), which I will now call the majority definition. Also those using a different convention do not seem to agree among each other.

One word about the factorial number system. It is not the same as Lehmer code, since it encodes (large) numbers rather than permutations by sequences of small numbers. However such a large number is easily (and often) associated to the corresponding permutation in the lexicographically ordered list, and under this correspondence the factorial number system (with the most significant digit on the left, as is usual for number systems) matches the majority definition of Lehmer code. Therefore I would count item 6 on the above list as support for the majority. Also this point of view allows giving a property that singles out the majority definition among all other variants: it is the only variant for which the lexicographic ordering on permutations corresponds to the lexicographic ordering of the corresponding codes. (Well actually its own variant that counts from 1 also has this property, but apart from being used by nobody as far as I know, such variants does not correctly count the total number of inversions, which is a good reason to count from 0.)

I would propose:

1. to call this article "Inversion table" rather than "Lehmer code", and treat the Lehmer code as a variation. Because Knuth does mention and define inversion tables, I think we could safely stick to that definition (which is the Lehmer code of the inverse permutation, using the majority definition);
2. to change the definition of Lehmer code the majority definition;
3. make sure the article is internally coherent.

In fact the three propositions are independent, so even if one prefers to keep the name "Lehmer code", I think it's definition should be changed. Marc van Leeuwen (talk) 13:07, 8 October 2011 (UTC)

OK, let's get started now

The above, immensely valuable comment, was made while the translation of the article was still a work in progress, with more focus on translating and formating than on the intrisic concepts. This initial phase being now completed, I'm all in favor of consolidating the scientific accuarcy.

The question of (count from 0 | count from 1) is now addressed, albeit briefly, in (now clean) [#3] - Maybe it could use its own paragraph rather than a mere footnote ? Also a footnote to a footnote was lost in translation : Knuth is cited as citing one Marshall Hall on his choice of the phrase "invertion table" over "Lehmer code". Maybe the complete Hall reference shall be retrieved and included here ?

And of course, I feel that the main goal should be to tie the (factoradic, permutation, Lehmer code) articles in a consistent and readable triptic. — Preceding unsigned comment added by Herix (talk • contribs) 14:11, 8 October 2011 (UTC)

Named for whom

The article currently claims this was named for Derrick Henry Lehmer, but in the article on the father of D. H. Lehmer, Derrick Norman Lehmer, he is credited. So was this named for the father, for the son, or for both? /80.71.135.103 (talk) 11:12, 4 September 2013 (UTC)

The paper cited in the current article is by D.H. Lehmer, so I think that must be the correct attribution, unless that paper itself should say differently (I must admit not having accessed it). If my memory serves, the article is referred to from Knuth's TAOCP (probably volume 1, or maybe the recent volume 4A, check their index) who can be trusted for historical accuracy, but I think he makes no claims about this being the very first reference.