Publ. I.R.M.A. Strasbourg, 1984, 229/S–08 Actes 8^{e} Séminaire Lotharingien, p. 55–58

SHUFFLE-INVARIANT TOTAL ORDERS

BY

Klaus LEEB (^{1}) AND Giuseppe PIRILLO

The results of this paper afford the right perspective on a conjecture the first author made after his characterization (Dec. 82) of invariant total orders on Hales-Jewett-morphisms : the families of total orders (^{i}A, <_{i}) compatible with the shuffling of words are described by sequences of orderepimorphisms together with signs :

\begin{matrix}{· \atop ↑} & + \\ {· \atop ↑} & − \\ {· \atop ↑} & − \\ {· \atop ↑} & + \end{matrix}

(A, <)−

where the ordering is by successive refinement along the <-morphisms while reading lexicographically in the direction indicated by the sign. The familiarity with such orders dates from SALAMITAKTIK [1] (1975). The second author had only 49% belief in this conjecture and thus while one of us tried to prove it, the other one tried to disprove it and in the end the following compromise resulted :

Theorem (+). — With respect to amalgamating shuffle (the same symbol may be placed by both factors in the same location of the shuffle), i.e., union of words, the above orderings are all the compatible ones.

Theorem (−). — Even over the alphabet 2 = {0, 1} there is an ordering not of the above form, yet compatible with the usual (disjoint) shuffling.

For the sake of a better acquaintance with the operation of shuffling we first explain the counterexample of THEOREM − :

(^{1}) The first author named would like to thank the C.N.R. and the Istituto di Analisi Globale, as well as the Istituto Matematica Ulisse Dini for the hospitality extended to him.

K. LEEB AND G. PIRILLO

For alphabet A = 2 = {0, 1} there is only one choice to be made for the determination of a diagram as described in the introduction : one sign which chooses between the lexicographic order from the left of from the right. We choose, say, + and define the following ⊔⊔-compatible family of orders (^{i}2, <_{i}) :

small 0 01 100 1001 11000 110001
⋀  …
big 1 10 011 0110 00111 001110

where the upper line continues as follows :

w_{2n} = 1^{m}0^{m}0 w_{2n+1} = 1^{n}0^{n}01

and lists the smaller of the two elements w \overline{w} (^{−} denotes complement). As we are talking about ⊔⊔-compatible total orders, at each length at most one new pair has to be decided, and we will show that indeed, it could not be decided by the earlier decisions : small 1^{a}0^{a}0(1) cannot be useful in deciding small 1^{a+d}0^{a+d}0(1) because the remaining word is 1^{d}0^{d}(1), which by shuffling 10 (and 1) is big.

For the proof of THEOREM + we first extract all the necessary information on the diagram from (^{1}A, <_{1}) and (^{2}A, <_{2}), then we show that this indeed fully determines the family (^{i}A, <_{i})_{i}. Next we assign to decisions a < b a priority level, i.e. a class modulo an equivalence relation ∼ :

a < b ∼ c < d  if  \begin{matrix}a & d \\ ∧ & ∨ \\ b & c \end{matrix} ≠ \begin{matrix}d & a \\ ∨ & ∧ \\ c & b \end{matrix}

meaning : if one is ⋀, the other is ⋁.

To each of these priorities there is of course associated a sign

+ if \begin{matrix}a & d \\ ∧ & ∨ \\ b & c \end{matrix} is ⋀, − if \begin{matrix}a & d \\ ∧ & ∨ \\ b & c \end{matrix} is ⋁,

whenever a < b ∼ c < d.

The priorities want a total ordering

a < b ⟨ c < d iff \begin{matrix}a & d \\ ∧ & ∨ \\ b & c \end{matrix} is ⋀ and \begin{matrix}d & a \\ ∨ & ∧ \\ c & b \end{matrix} is ⋀.

Finally we have to show that each priority level consists of intervals in (A, <). The relation ∼ is reflexive, because

\begin{matrix}a & b \\ ∧ & ∨ \\ b & a \end{matrix} ≠ \begin{matrix}b & a \\ ∨ & ∧ \\ a & b \end{matrix} ,

SHUFFLE-INVARIANT TOTAL ORDERS

symmetric by definition. Next we show that the definition of sign is consistent :

Let a < b ∼ c < d get +, where c < d ∼ e < f gets −. But then

⋀ \begin{matrix}a & d \\ ∧ & ∨ \\ b & c \end{matrix}  \begin{matrix}d & e \\ ∨ & ∧ \\ c & f \end{matrix} ⋀

could be shuffled to yield

⋁ \begin{matrix}d & a \\ ∨ & ∧ \\ c & b \end{matrix} \begin{matrix}e & d \\ ∧ & ∨ \\ f & c \end{matrix} ⋁,

a contradiction. Thus also c < d ∼ e < f would get +. We show that then a < b ∼ e < f and gets +. Just inspect

⋀ \begin{matrix}a & d & f \\ ∧ & ∨ & ∥ \\ b & c & f \\ ∥ & ∧ & ∨ \\ b & d & e \end{matrix}  and  ⋁ \begin{matrix}f & c & a \\ ∨ & ∧ & ∥ \\ e & d & a \\ ∥ & ∨ & ∧ \\ e & c & d \end{matrix} .

The relation a < b ⟨ c < d is clearly total. There remains compatibility with ∼ and transitivity.

So let a < b ⟨ c < d and either e < d ∼ e < f or c < d ⟨ e < f. In any case we can put c < d in a position where it wins against e < f. But since a < b wins against c < d in any position, so it does against e < f.

At the very last, diagrams for the type

\begin{matrix}a & e \\ ∧ & ∨ \\ b & d \\ ∥ & ∨ \\ b & c \end{matrix}

show that a < b cannot lose against d < e, yet win against c < e which is a prolongation c < d < e.

With all this knowledge we can now quickly prove our THEROREM +. We have to show that the strongest inequality a < b wins. Let it be at a level with sign +, say. Then opposing inequalities c < d, e < f of same strength can only occur farther right. Weaker inequalities u < v, x < y are welcome in any position and sense.

X = v a d f x
∨ ∧ ∨ ∨ ∧
Y = u b c e y

We just have to take all the pairs involving

\begin{matrix}a \\ ∧ \\ b \end{matrix}

as one component and use amalgameted shuffle (union of words) to compose the desired X < Y.

[1] LEEB (Klaus). — Salamitaktik beim Quaderpacken, Arbeitsberichte des IMMD, Bd. 11/N^{o} 5, April 1978.

Klaus Leeb, Informatik I, Universität Erlangen-Nürnberg, D-850 Erlangen, R.F.A.

and

Giuseppe Pirillo, Istituto di Matematica, Università di Firenze, Viale Morgagni 67/A, I-Firenze, Italie