{\catcode`\^^M=\active %
  \gdef\adrbox{\catcode`\^^M=\active %
  \def^^M{\egroup\hbox\bgroup}}}
\def\adresse{\par\nobreak%
  \vskip 24pt plus 6pt minus 3pt%
  \hbox to \hsize\bgroup\hfill%
  \def\fin{\egroup\egroup\hskip2em\egroup\vfill\eject}%
  \adrbox\vbox\bgroup\hbox\bgroup}
\def\fin{\vfill\eject}

\catcode'32=9
\magnification=1200

% particularite du pilote canon

\voffset=1cm
\hoffset=0cm
%\hoffset=1cm
\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm8
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bb=\bboard

\tenpoint

%���������������������� dactylographie fran�aise �����������������

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

%���������������������� format de sortie �����������������

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, t.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr�s une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\catcode`\@=12

{\catcode`\^^M=\active %
  \gdef\adrbox{\catcode`\^^M=\active %
  \def^^M{\egroup\hbox\bgroup}}}
\def\adresse{\par\nobreak%
  \vskip 24pt plus 6pt minus 3pt%
  \hbox to \hsize\bgroup\hfill%
  \def\fin{\egroup\egroup\hskip2em\egroup\vfill\eject}%
  \adrbox\vbox\bgroup\hbox\bgroup}
\def\fin{\vfill\eject}
\pageno=55

\titrecourant={SHUFFLE-INVARIANT TOTAL ORDERS}
\auteurcourant={K. LEEB AND G. PIRILLO}

\eightpoint
\leftline{Publ. I.R.M.A. Strasbourg, $\oldstyle 1984$, 229/S--08}
\leftline{Actes 8\emini\ S\'eminaire Lotharingien, p. 55--58}

\tenpoint
\let\it=\sl

\def\shuffle{\sqcup\kern-1.75pt \sqcup}
\def\leeb{\raise 2pt \hbox{$\cdot\atop\uparrow$}}
\vskip 1.5cm
\centerline{{\bf SHUFFLE-INVARIANT TOTAL ORDERS}}
\vskip 2.8mm
\centerline{\sevenrm BY}
\vskip 2.8mm
\centerline{{\petcap Klaus} LEEB \footnote{$(^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.} {\sevenrm AND}
{\petcap Giuseppe} PIRILLO}

\vskip .5cm
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 $({^iA},<_i)$ compatible
with the shuffling of words are described by sequences
of order-epimorphisms together with signs :
  $$\matrix{\leeb&+\cr
            \leeb&-\cr
            \leeb&-\cr
            \leeb&+\cr}$$
  $$(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
\pd 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 :

\th 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.
\finth

\th Theorem $(-)$|Even over the alphabet $2=\{ 0,1\} $ there is
an ordering not of the above form, yet compatible with the 
usual (disjoint) shuffling.
\finth

For the sake of a better acquaintance with the operation of
shuffling we first explain the counterexample of \pd THEOREM $-$ :
           
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
$\shuffle$-compatible family of orders $(^i2,<_i)$ :
  $$\matrix{{\rm small}& 0& 01& 100& 1001& 11000& 110001&\cr
                   &\bigwedge&
  \hrulefill&\hrulefill&  \hrulefill&  \hrulefill&  \hrulefill&
  \ldots\cr
            {\rm big}& 1& 10& 011& 0110& 00111& 001110&\cr}$$
where the upper line continues as follows :
  $$w_{2n}=1^m0^m0\qquad
w_{2n+1}=1^n0^n01$$
and lists the smaller of the two elements $w$
$\overline w$ ($^-$ denotes complement). As we are talking
about $\shuffle$-compatible {\it total} orders, at
each length {\it 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^a0^a0(1)$ cannot be useful
in deciding small
$1^{a+d}0^{a+d}0(1)$
because the remaining word is 
$1^d0^d(1)$, which by shuffling $10$
(and 1) is big.

For the proof of \pd THEOREM $+$ we first
extract all the necessary information on the
diagram from $(^1A, <_1)$ and
$(^2A, <_2)$, then we show that this indeed 
fully determines the family $(^iA, <_i)_i$.
Next we assign to decisions $a<b$ a priority level,
i.e. a class modulo an equivalence relation $\sim$ : 
  $$a<b\sim c<d\qquad {\rm if}\qquad
\matrix{a&d\cr
        \wedge&\vee\cr
        b&c\cr}
\not=
\matrix{d&a\cr
        \vee&\wedge\cr
        c&b\cr}$$
meaning : if one is $\bigwedge$, the other is $\bigvee$.

To each of these priorities there is of 
course associated a sign 
  $$+\ {\rm if}\ \matrix{a&d\cr
                     \wedge&\vee\cr
                     b&c\cr}\quad {\rm is}\quad 
{\textstyle \bigwedge},
\qquad -\ {\rm if}\ 
\matrix{a&d\cr
        \wedge&\vee\cr
        b&c\cr}\quad {\rm is}\quad {\textstyle\bigvee},$$
whenever $a<b\sim c<d$.

The priorities want a total ordering
  $$a<b\bigm<c<d\quad {\rm iff}\quad
\matrix{a&d\cr
        \wedge&\vee\cr
        b&c\cr}\quad {\rm is}\quad {\textstyle\bigwedge}
\quad \hbox{{\it and}}\quad
\matrix{d&a\cr
        \vee&\wedge\cr
        c&b\cr}\quad {\rm is}\quad {\textstyle\bigwedge}.$$

Finally we have to show that each priority level consists
of intervals in $(A,<)$.
The relation $\sim$ is reflexive, because
  $$\matrix{a&b\cr
            \wedge&\vee\cr
            b&a\cr}
\not=
\matrix{b&a\cr
        \vee&\wedge\cr
        a&b\cr},$$
symmetric by definition.
Next we show that the definition of sign
is consistent : 

\vskip 5pt
Let $a<b\sim c<d$ get $+$, where 
$c<d\sim e<f$ gets $-$.
But then
  $$\bigwedge\matrix{a&d\cr
                     \wedge&\vee\cr
                     b&c\cr}\qquad
\matrix{d&e\cr
        \vee&\wedge\cr
        c&f\cr}\bigwedge$$
could be shuffled to yield
  $$\bigvee\matrix{d&a\cr
                   \vee&\wedge\cr
                   c&b\cr}\qquad
\matrix{e&d\cr
        \wedge&\vee\cr
        f&c\cr}\bigvee,$$
a contradiction.
Thus also $c<d\sim e<f$ would get $+$. We show that
then $a<b\sim e<f$ and gets $+$. Just inspect
  $$\bigwedge\matrix{a&d&f\cr
                     \wedge&\vee&\|\cr
                     b&c&f\cr
                     \|&\wedge&\vee\cr
                     b&d&e\cr}\qquad
{\rm and}\qquad
\bigvee\matrix{f&c&a\cr
               \vee&\wedge&\|\cr
               e&d&a&\cr
               \|&\vee&\wedge\cr
               e&c&d\cr}.$$
The relation $a<b\bigm< c<d$ is clearly total.
There remains compatibility with $\sim$ and transitivity.

So let $a<b\bigm< c<d$ and either 
$e<d\sim e<f$ or $c<d\bigm< 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
  $$\matrix{a&e\cr
            \wedge&\vee\cr
            b&d\cr
            \|&\vee\cr
            b&c\cr}$$
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 \pd 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.
  $$\matrix{X&=&v&a&d&f&x\cr
             &&\vee&\wedge&\vee&\vee&\wedge\cr
            Y&=&u&b&c&e&y\cr}$$
We just have to take all the pairs involving             
$$\matrix{a\cr
         \wedge\cr
         b\cr}$$ 
as one component and use amalgameted
shuffle (union of words) to compose the desired
$X<Y$.

\vskip 24pt 
\eightpoint

\divers 1|\pd LEEB (Klaus)|Salamitaktik beim Quaderpacken,
Arbeitsberichte des IMMD, Bd. 11/N\omini\ 5, April $\oldstyle 1978$|

\tenpoint
\adresse
Klaus {\petcap Leeb}, 
Informatik~I,
Universit\"at Erlangen-N\"urnberg, 
D-850 Erlangen, R.F.A.

and 

Giuseppe {\petcap Pirillo},
Istituto di Matematica,
Universit\`a di Firenze, 
Viale Morgagni 67/A,
I-Firenze, Italie

\fin
           
\bye
