{\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