# Lexicographical order

(Redirected from Colexicographical order)
For similarly named ordering systems outside mathematics, see Alphabetical order and Collation.

In mathematics, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters. This generalization consists primarily in defining a total order over the sequences (often called words in computer science) of elements of a finite totally ordered set, often called alphabet.

There are several variants and generalizations of the lexicographical ordering. One of them, widely used in combinatorics, allows ordering subsets of a fixed finite set. It consists in using a total order on the finite set, for converting subsets into increasing sequences, to which the lexicographical order is applied. Another generalization defines an order on a Cartesian product of partially ordered sets; this order is a total order if and only the factors of the Cartesian product are totally ordered.

## Motivation and definition

The word lexicographic is derived from lexicon, the set of words that are used in some language and appear in dictionaries and encyclopedias. The lexicographic order has thus been introduced for sorting the entries of dictionaries and encyclopedias. This has been formalized in the following way.

Let us consider a finite set A, often called alphabet, which is totally ordered. In dictionaries, this is the common alphabet, ordered by the alphabetical order. In book indexes, the alphabet is generally extended to all alphanumeric characters; it is the object of a specific convention whether a digit is considered as smaller or larger than a letter. The lexicographic order is a total order on the sequences of elements of A, often called words on A, which is defined as follows.

Given two different sequences of the same length, a1a2...ak and b1b2...bk, the first one is smaller than the second one for the lexicographical order, if ai<bi (for the order of A), for the first i where ai and bi differ.

That comparison assumes both sequences are the same length. To compare sequences of different length, the shorter sequence is usually padded at the end with enough "blanks" (a special symbol that is treated as smaller than every element of A). This way of comparing sequences of different lengths is always used in dictionaries. However, in combinatorics, an other convention is frequently used, consisting in considering that a shorter sequence is always smaller than a longer sequence. This variant of the lexicographical order is sometimes called shortlex order.

For example, the word "Thomas" appears before "Thompson" in dictionaries because the letter 'a' comes before the letter 'p' in the alphabet. The 5th letter is the first that is different in the two words; the first 4 letters are "Thom" in both. Because it is the first difference, the 5th letter is the most significant difference (for an alphabetical ordering).

An important property of the lexicographical order is that it it is a well-order, that is every decreasing sequence of words is finite.[1][2]

## Numeral systems and date

The lexicographical order is not only used in dictionaries, it is also commonly used for comparing numbers and date.

One of the drawbacks of the Roman numeral system is that, when looking at two numbers, it is not always immediate to see which is the smaller. On the other hand, with the positional notation of the Hindu–Arabic numeral system, comparing numbers is easy, because the natural order on nonnegative integers is the same as the variant shortlex of the lexicographic order. In fact, with positional notation, a nonnegative integer is represented by a sequence of numerical digits, and an integer is larger than another one if either it has more digits or the number of digits is the same, and the first digit which differs is larger. For real numbers written in decimal notation, a slightly different variant of the lexicographical order is used: the parts on the left of the decimal point are compared as before; if they are equal, the parts at the right of the decimal point are compared with the lexicographical order.

When negative numbers are also considered, one has to revert the order for comparing negative numbers. This is not usually a problem for humans, but it may for computers (testing the sign takes some time). This is one of the reasons of adopting two's complement representation for representing signed integers in computers.

Another example of a non-dictionary use of the lexicographical ordering appears with the ISO 8601 date formatting scheme, which expresses a date as YYYY-MM-DD. This formatting scheme has the advantage that the lexicographical order on sequences of characters that represent dates is the same as the chronological order: an earlier date is smaller for the lexicographical order than a later date. This date ordering makes much easier computerized sorting of dates, by avoiding the need of a specific sorting algorithm.

## Monoid of words

The monoid of words over an alphabet A is the free monoid over A. That is, the elements of the monoid are the finite sequences (words) of elements of A (including the empty sequence, of length 0), and the operation (multiplication) is the concatenation of words. A word u is a prefix of another word v if there exists a word w such v = uw.

With this terminology, the above definition of the lexicographical order becomes more concise: Given a partially or totally ordered set A, and two words a and b over A, then one has a < b for the lexicographical order, if

• either a is a prefix of b
• or there exists words u, v, w (possibly empty) and elements x and y of A such that
x < y
a = uxv
b = uyw

If < is a total order on A, then so is the lexicographic order on the words of A. However, in general this is not a well-order, even though if the alphabet A is well-ordered; for instance, if A = {a, b}, the language {anb | n ≥ 0} has no least element: ... < aab < ab < b for the lexicographical order.

As many applications require well orders, a variant of the lexicographical orders often used. This well-order, sometimes called shortlex or quasi-lexicographical order, consists in considering first the lengths of the words (if length(a) < length(b), then a < b), and, if the lengths are equal, using the lexicographical order. If the order on A is a well-order, the same is true for shortly.[2][3]

## Cartesian products

The lexicographical order defines an order on a Cartesian product of ordered sets, which is a total order when all these sets are totally ordered. In fact, an element of a Cartesian product E1× ... ×En is a sequence such that its ith element belongs to Ei for every i. As, for evaluating the lexicographical order of sequences, one compares only elements which have the same rank in the sequences, the lexicographical order order applies to Cartesian products of ordered sets.

Specifically, given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as

(a,b) ≤ (a′,b′) if and only if a < a or (a = a′ and bb′).

The result is a partial order. If A and B are each totally ordered, then the result is a total order as well. The lexicographical order of two totally ordered sets is thus a linear extension of their product order.

One can define similarly the lexicographic order on the Cartesian product of an infinite family of ordered sets, if the family is indexed by the nonnegative integers or, more generally by a well-ordered set. This generalized lexicographical order is a total order, if each factor set is totally ordered.

Unlike the finite case, an infinite product of well-orders is not necessarily well-ordered by the lexicographical order. For instance, the set of countably infinite binary sequences (by definition, the set of functions from non-negative integers to {0, 1}, also known as the Cantor space {0, 1}ω) is not well-ordered; the subset of sequences that have precisely one 1 (i.e. { 100000..., 010000..., 001000..., ... }) does not have a least element under the lexicographical order induced by 0 < 1, because 100000... > 010000... > 001000... > ... is an infinite descending chain.[1] Similarly, the infinite lexicographic product is not Noetherian either because 011111... < 101111... < 110111 ... < ... is an infinite ascending chain.

## Functions over a well-ordered set

The functions from a well-ordered set X to a totally ordered set Y may be identified with sequences indexed by X of elements of Y. They can thus be ordered by the lexicographical order, and for two such functions f and g, the lexicographical order is thus determined by their values for the smallest x such that f(x) ≠ g(x).

If Y is also well-ordered and X is finite, then the resulting order is a well-order. As shown above, if X is infinite this is not the case.

## Finite subsets

Orderings of the 3-subsets of {1, ..., 6}, represented as sets of red squares, increasing sequences (in blue), or by their indicator functions, converted in decimal notation (in grey). The grey numbers are also the rank of the subsets in all subsets of {1, ..., 6}, numbered in colexicographical order, and starting from 0. The lexicographical (lex) and colexicographical (colex) orders are on the top and the corresponding reverse orders (rev) on the bottom
One passes from an order to its reverse order, either by reading bottom-up instead of up-bottom, or by exchanging red and white colors.

In combinatorics, one has often to enumerate, and therefore to order the finite subsets of a given set S. For this, one usually chooses an order on S. Then, sorting a subset of S is equivalent to convert it into an increasing sequence. The lexicographic order on the resulting sequences induces thus an order on the subsets, which is also called the lexicographical order.

In this context, one generally prefer to sort first the subsets by cardinality, such as in the shortlex order. Therefore, in the following, we will consider only orders on subsets of fixed cardinal.

For example, using the natural order of the integers, the lexicographical ordering on the subsets of three elements of S = {1, 2, 3, 4, 5, 6} is

123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <
234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456.

For ordering finite subsets of a given cardinality of the natural numbers, the colexicographical order (see below) is often more convenient, because all initial segments are finite, and thus the colexicographical order defines an order isomorphism between the natural numbers and the set of sets of n natural numbers. This is not the case for the lexicographical order, as, with the lexicographical order, we have, for example, 12n < 134 for every n > 2.

## Group orders of ${\displaystyle {\mathbb {Z}}^{n}}$

Let ${\displaystyle {\mathbb {Z}}^{n}}$ be the free Abelian group of rank n, whose elements are sequences of n integers, and operation is the addition. A group order on ${\displaystyle {\mathbb {Z}}^{n}}$ is a total order, which is compatible with addition, that is

${\displaystyle a

The lexicographical ordering is a group order on ${\displaystyle {\mathbb {Z}}^{n}.}$

The lexicographical ordering may also be used to characterize all group orders on ${\displaystyle {\mathbb {Z}}^{n}.}$[4][5] In fact, n linear forms with real coefficients, define a map from ${\displaystyle {\mathbb {Z}}^{n}}$ into ${\displaystyle {\mathbb {R}}^{n},}$ which is injective if the forms are linearly independent (it may be also injective if the forms are dependent, see below). The lexicographic order on the image of this map induces a group order on ${\displaystyle {\mathbb {Z}}^{n}.}$ Robbiano's theorem is that every group order may be obtained in this way.

More precisely, given a group order on ${\displaystyle {\mathbb {Z}}^{n},}$ there exist an integer sn and s linear forms with real coefficients, such that the induced map ${\displaystyle \varphi }$ from ${\displaystyle {\mathbb {Z}}^{n}}$ into ${\displaystyle {\mathbb {R}}^{s}}$ has the following properties;

• ${\displaystyle \varphi }$ is injective;
• the resulting isomorphism from ${\displaystyle {\mathbb {Z}}^{n}}$ to the image of ${\displaystyle \varphi }$ is an order isomorphism when the image is equipped with the lexicographical order on ${\displaystyle {\mathbb {R}}^{s}.}$

## Colexicographic order

Orderings of the 24 permutations of {1,...,5} that are 5-cycles (in blue). The inversion vectors (in red) of permutations in colex order are in revcolex order, and vice versa.

The colexicographic or colex order is a variant of the lexicographical order, which is obtained by reading finite sequences from the right to the left instead of reading them from the left to the right. More precisely, while the lexicographical order between two sequences is defined by

a1a2...ak <lex b1b2...bk if ai<bi for the first i where ai and bi differ,

the colexicographical order is defined by

a1a2...ak <colex b1b2...bk if ai<bi for the last i where ai and bi differ

In general, the difference between the colexicographical order and the lexicographical order is not very significant. However, when considering increasing sequences, typically for coding subsets, the two orders differ significantly.

For example for ordering the increasing sequences (or the sets) of two natural integers, the lexicographical order begins by

12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ...,

and the colexicographic order begins by

12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ....

The main property of the colexicographical order for increasing sequences of a given length is that every initial segment is finite. In other words, the colexicographical order for increasing sequences of a given length induces an order isomorphism with the natural numbers, and allows enumerating these sequences. This is frequently used in combinatorics, for example in the proof of the Kruskal-Katona theorem.

## Monomials

When considering polynomials, the order of the terms does not matter in general, as the addition is commutative. However, some algorithms, such as polynomial long division require a specific order of the terms. Many of the main algorithms for multivariate polynomials are related with Gröbner bases, concept that requires the choice of a monomial order, that is a total order, which is compatible with the monoid structure of the monomials. Here "compatible" means that ${\displaystyle a, if the monoid operation is denoted multiplicatively. This compatibility implies that the product of a polynomial by a monomial does not change the order of the terms. For Gröbner bases, a further condition must be satisfied, namely that every non constant monomial is greater than the monomial 1. However this condition is not needed for other related algorithms, such as the algorithms for the computation of the tangent cone.

As Gröbner bases are defined for polynomials in a fixed number of variables, it is common to identify monomials (for example ${\displaystyle x_{1}x_{2}^{3}x_{4}x_{5}^{2}}$) with their exponent vectors (here [1, 3, 0, 1, 2]). If n is the number of variable, every monomial order is thus the restriction to ${\displaystyle {\mathbb {N}}^{n}}$ of a monomial order of ${\displaystyle {\mathbb {Z}}^{n}}$ (see above § Group orders of ${\displaystyle {\mathbb {Z}}^{n}}$, for a classification).

One of these admissible orders is the lexicographical order. It is, historically, the first to have been used for defining Gröbner bases, and is sometimes called pure lexicographical order for distinguishing it from other orders that are also related to a lexicographical order.

Another one is consists in comparing first the total degrees, and then resolving the conflicts by using the lexicographical order. This order is not widely used, as either the lexicographical order or the degree reverse lexicographical order have generally better properties.

The degree reverse lexicographical order consists also in comparing first the total degrees, and, in case of equality of the total degrees, using the reverse of the colexicographical order. That is, given two exponent vectors, one has

${\displaystyle [a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]}$

if either

${\displaystyle a_{1}+\cdots +a_{n}

or

${\displaystyle a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\quad {\text{and}}\quad a_{i}>b_{i}\;{\text{for the largest }}i{\text{ such that }}a_{i}\neq b_{i}.}$

For this ordering, the monomials of degree one have the same order as the corresponding indeterminates (this would not be the case if the reverse lexicographical order would be used). For comparing monomials in two variables of the same total degree, this order is the same as the lexicographic order. This is not the case with more variables. For example, for exponent vectors of monomials of degree two in three variables, one has for the degree reverse lexicographic order:

${\displaystyle [0,0,2]<[0,1,1]<[1,0,1]<[0,2,0]<[1,1,0]<[2,0,0]}$

For the lexicographical order, the same exponent vectors are ordered as

${\displaystyle [0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0].}$

A useful property of the degree reverse lexicographical order is that a homogeneous polynomial is a multiple of the least indeterminate if and only if its leading monomial (its greater monomial) is a multiple of this least indeterminate.