% This file is obtained from ``pathjdt.tex'' by merging all \input files
\def\jobname{pathjdt}

% The first few lines set the format required by the S\'eminare Lotharingien
% that apparently wishes to cater for the visually handicapped (sorry
% Dominique, I couldn't resist). If your eyesight is all right, and you wish
% to avoid ugly line- and page-breaks, and/or reduce the printed output by
% 10 pages, and/or to avoid having to generate several fonts at unusual sizes,
% then you can simply remove \visuallychallengedtrue below.

\newif\ifvisuallychallenged \visuallychallengedtrue

\ifvisuallychallenged
\mag=\magstep1
\hsize=14 true cm
\vsize=23.5 true cm \advance \vsize -24 true pt % space for page numbers
\tolerance=1000 \def~{\penalty9999\ } % this will prevent overfull hboxes
\let\formloaded=\relax
\fi

%\input CWIreport % expanded here:
% Macros defining the format of CWI reports

\ifx\CWIloaded\undefined \let\CWIloaded\relax \else \endinput \fi

% Maybe we aren't using plain.tex version 3.0 yet ...
\ifx\topglue\undefined \def\topglue{\nointerlineskip\vglue-\topskip\vskip}\fi

\ifx\formloaded\undefined % page dimensions can be explicitly overruled
  \vsize=24.5 cm \advance \vsize -24pt % space for page numbers
  \hsize=16 cm
% \normalbaselineskip=13pt\normallineskiplimit=.1pt\normallineskip.1pt
% \normalbaselines
% \setbox\strutbox=\hbox{\vrule height8.9pt depth4pt width0pt}
  \let\formloaded\relax % but this file should be loaded before marxmax.tex
\fi

% Preliminaries

\catcode`_=11 % control sequence names with this letter are private

\def\let_next{\let\next=}
{\obeylines\gdef\default_address%
 {Universit\'e de Poitiers, D\'epartement de Math\'ematiques,
  40 Avenue du Recteur Pineau, 86022 Poitiers, France}}

\newtoks\title \newtoks\MSCcodes \newtoks\CRcodes \newtoks\keywords
\newtoks\titlenote
\newif\if_started

\font\seventeenbf=cmbx10 scaled \magstep 3
\font\twelvebf=cmbx12
\font\twelverm=cmr12

\font\seventeenssbf=cmssbx10 scaled \magstep 3
\font\twelvessbf=cmssbx10 at 12 pt
\font\twelvess=cmss12

\font\tenss=cmss10
\font\tenssit=cmssi10
\font\tenssbf=cmssbx10
\def\sans
{\def\rm{\fam0\tenss}\def\it{\fam\itfam\tenssit}\def\bf{\fam\bffam\tenssbf}\rm
}

% Nine point type (for footnotes and references); math sizes 9--7--5 pt

\font\ninerm=cmr9 \font\nineit=cmti9 \font\ninebf=cmbx9 \font\ninesl=cmsl9
\font\ninett=cmtt9 \font\ninei=cmmi9 \font\ninesy=cmsy9
\font\niness=cmss9 \font\ninessit=cmssi9 \font\ninessbf=cmssbx10 at 9 pt
\skewchar\ninei='177 \skewchar\ninesy='60

\def\ninept
{\def\rm{\fam0\ninerm}\def\it{\fam\itfam\nineit}\def\bf{\fam\bffam\ninebf}%
 \def\sl{\fam\slfam\ninesl}\def\tt{\fam\ttfam\ninett}\rm
 \def\sans{\def\rm{\fam0\niness}\def\it{\fam\itfam\ninessit}%
           \def\sl{\fam\slfam\ninessit}\def\bf{\fam\bffam\ninessbf}\rm}
 \textfont0\ninerm \textfont1\ninei \textfont2=\ninesy
 \textfont\itfam\nineit \textfont\slfam\ninesl
 \textfont\bffam\ninebf \textfont\ttfam\ninett
 \normalbaselineskip=11pt \normalbaselines
 \setbox\strutbox=\hbox{\vrule height 8 pt depth 3 pt width 0 pt}%
}

% general utilities

\long\def\centerpar#1{\begingroup
  \advance\leftskip by 0pt plus 1 fil minus 3pt \rightskip=\leftskip
	\parindent=0pt \parfillskip=0pt \linepenalty=100
  \noindent\ignorespaces#1\par\endgroup}

\def\good_break{\unskip\penalty-10\ \ignorespaces}% \suggested break point

% redefine footnotes to be in 9pt type and independent of context settings
\catcode`@=11
\def\vfootnote#1%
{\insert\footins\bgroup \ninept
 \interlinepenalty=\interfootnotelinepenalty
 \splittopskip=\ht\strutbox % determines top baselines of broken footnotes
 \splitmaxdepth=\dp\strutbox % likewise for bottom lines
 \floatingpenalty=20000 % please don't break footnotes, if possible
 \leftskip=1pc \rightskip=1pc \spaceskip=0pt \xspaceskip=0pt
 \parindent=0pt \parskip=3pt minus 1pt \parfillskip=0pt plus 1 fil
 \textindent{#1}\footstrut\futurelet\next\f@@t
}
\catcode`@=12

% defaults
\let\_authors\empty % initialise to no authors

% Fetching author's information.
% Syntax: ([..] means optional)
% ( \Author[=] {<name>} 
%   [ \address[=]{<address >} ]
%   [ \email[=]{<email>} ]
%   [ \URL[=]{<WWW address>} ]
% )*
%
% result recorded in \_authors (macro)

\def\Author#1{\def\this_author{#1}%
  \ifx\this_author\_eq \let_next\Author % allow "\Author={"
  \else \let_next\let_next \afterassignment\_author 
  \fi \next}
\def\_author
 {\let\this_addr=\default_address
  \ifx\next\address \let_next\get_address
  \else \ifx\next\email \let_next\get_email
  \else \ifx\next\URL \let_next\get_URL
  \else \add_author
  \fi\fi\fi \next
}

\def\address#1{\errmessage
 {\string\address\space should only follow \string\Author}}
\def\email#1{\errmessage
 {\string\email\space should only follow \string\Author}}
\def\URL#1{\errmessage
 {\string\URL\space should only follow \string\Author}}

\def\get_address{\begingroup\obeylines\get_addr}
\def\get_addr#1%
{\endgroup\def\this_addr{#1}%
  \ifx\this_addr\_cr \let_next\get_address % ignore newline before "{"
  \else\ifx\this_addr\_eq \let_next\get_address % allow an "=" sign
       \else \let_next\let_next \afterassignment\get_ad
  \fi\fi \next
}
\def\get_ad
{\ifx\next\email \let_next\get_email
 \else \ifx\next\URL \let_next\get_URL
 \else \add_author
 \fi\fi \next
}

\def\get_email#1%
{\def\this_email{#1}%
  \ifx\this_email\_eq \let_next\get_email
  \else \edef\this_addr{\this_addr\endgraf{\tt #1}}%
    \let_next\let_next \afterassignment\after_em
  \fi \next
}
\def\after_em{\ifx\next\URL \let_next\get_URL \else \add_author \fi \next}
\def\get_URL#1%
{\def\this_URL{#1}%
 \ifx\this_URL\_eq \let_next\get_URL
 \else 
  {\def~{\char "7E }%
   \xdef\this_addr{\this_addr\endgraf{\noexpand\tt URL: http://#1}}%
  }\let_next\add_author
 \fi \next
}

\def\_eq{=}{\obeylines\gdef\_cr{^^M}}

\def\add_author % Does not and should not use \next!
{\toks0=\expandafter{\_authors}%
 \xdef\_authors
 {\the\toks0 \noexpand\\{\this_author\noexpand\_addr{\this_addr}}}%
}

% Getting the article started

\def\start_art
{\vfil\eject \ifodd\pageno\else \shipout\vbox to \vsize{}\advancepageno\fi

 \topglue 10mm plus 3 mm minus 2mm
 \centerpar{\let\\=\good_break\seventeenssbf \baselineskip=22pt \the\title}%
 \ifx \_authors\empty \message{Warning: no authors specified.}\else
   \bigskip\centerpar
    {\twelvess
     \def\par{\ifhmode\endgraf\else\medskip\fi}\obeylines
     \def\_addr##1{\smallskip{\ninessit\let\\=\par\noindent##1\endgraf}}%
     \def\\##1{\bigskip##1}\_authors
    }\bigskip
 \fi
 \_startedtrue
}

% Triggering the start of the article

\outer\def\abstract
{\if_started \errmessage{Abstract must be placed at start of article.}%
 \else \start_art \bigskip \begingroup \ninept \sans \narrower
   \leftline{\hskip\leftskip ABSTRACT}\nobreak\smallskip
	 \everypar{\everypar{}\setbox0=\lastbox}%
 \fi
}

\outer\def\maintext
{\if_started\medskip\endgroup\else\start_art\fi
 \if &\the\MSCcodes\the\CRcodes\the\keywords\the\titlenote&\else
  {\narrower\ninept\sans
   \if &\the\MSCcodes&\else
     \hangindent=4em \noindent
     {\it 1991 Mathematics Subject Classification:\/} \the\MSCcodes.
     \par\fi
   \if &\the\CRcodes&\else
     \hangindent=4em \noindent
     {\it 1991 Computing Reviews Subject Classification:\/} \the\CRcodes.
     \par\fi
   \if &\the\keywords&\else
     \hangindent=2em \noindent{\it Keywords and Phrases:\/} \the\keywords.
     \par\fi
   \if &\the\titlenote&\else
     {\def\\{\unskip\hfil\break\ignorespaces}%
      \hangindent=2em \noindent{\it Note:\/} \the\titlenote.
      \par}\fi
  }\bigskip
 \fi
}

\def\sticksection % to be issued before \beginsection to prevent page break
{\vbox\bgroup\parskip=0pt \everypar{\egroup\noindent}}


\def\newreport
{\vfil \eject \secno=0\subsecno=0\proclno=0 \eqnumber=0 \pageno=1 \mark{}
 \title={}\MSCcodes={}\CRcodes={}\keywords={}\titlenote={}
 \let\_authors\empty
 \_startedfalse
}

\catcode`_=8 % Now underscores are for subscripts again
% END of CWIreport.tex

%\input marxmax % expanded here:
% Protection

\ifx\macrosloaded\relax  \endinput \else \let\macrosloaded\relax \fi
\ifx\formloaded\undefined \input form \fi

\catcode`@=11

% TeXnical tricks

\def\letnext{\let\next= }
\def\defnext{\def\next}   % Not \outer, in case \next is.
\def\reset#1{\global#1=0 }
\def\useouter #1 {\begingroup
                  \expandafter\let\csname#1\endcsname=\relax % not outer
                  \afterassignment\endgroup\global}
\def\?#1\then#2\else#3\fi{#1\defnext{#2}\else\defnext{#3}\fi \next}
\newif\ifnot
\newif\ifnomessage \nomessagetrue % used to suppress expansions in \message
\let\domessage=\message \def\message#1{{\nomessagefalse\domessage{#1}}}

% File handling

\newif\iftoc 
\def\writetoc{\write\tocfile}\def\tocfile{-1 }
\useouter newwrite
\def\opentoc{\newwrite\tocfile\openout\tocfile=\jobname.toc }
\edef\tocheader{\string\NotocSection\space Table of contents.
  \string\noindent\string\medskip}
\def\maketoc{\opentoc\writetoc{\tocheader}\toctrue}

\def\str#1{\string#1 }
% The following prohibits expansion between $..$,
% but there shouldn't be any groups there.
{\catcode`@=3 % weird math shifts, cannot occur in math mode
 \gdef\passord#1$#2\end{#1\ifx@#2@\else\getmath#2\end\fi}
 \gdef\getmath#1${$\noex#1\endmath$\passord}
 \gdef\noex#1\endmath{\ifx@#1@\else\donoex#1\endmath\fi}
 \gdef\donoex#1{\noexpand#1\noex}
 \gdef\nomathexp#1{\passord#1$\end}
}
\def\putmark#1{\mark
  {\count1=\the\secno \count2=\the\subsecno \count3=\the\proclno
   \marktoks={\ignorespaces\setchap\space#1}}}% set counters, running head
\def\setchap{\ifnum\secno<0 Appendix \lastlabel.\else\lastlabel\fi}
\def\puttoc#1{\toks0={\nomathexp{#1} \str\onpage\folio.}\edef\next
                      {{\str\tocitem \lastlabel=\the\toks0}}\writetoc\next}
\def\setmark#1{\putmark{#1}\puttoc{#1}}

\output=
{\everyhbox{}% don't interfere into output routine
 \firstmark \headline={\tenit \ifodd\pageno\hfill\fi \the\marktoks \hfil }
 \let~\relax % ~ shouldn't be expanded in index file, and doesn't occur in:
 \plainoutput
}

\newwrite\labfile
\def\tolab{\write\labfile}
\def\writelab{\openout\labfile=\jobname.lab
              \global\let\writelab=\tolab \tolab}
\def\chklab#1\lastlabel#2.{\def\next{#2}\ifx\next\empty}% if #1/=\lastlabel
\def\deflab#1{\chklab#1\lastlabel.\writelab{\string\def\string#1{#1}}\fi}
\def\savecount#1{\writelab{#1=\number#1}}
\toks0={\savecount\secno\savecount\subsecno\savecount\proclno
        \savecount\eqnumber
        \savecount\pageno\writelab{\string\advancepageno}}
\toks2=\expandafter{\bye}
\edef\bye{\the\toks0 \the\toks2}


\newwrite\indexfile
\def\toindex{\write\indexfile}
\def\writeindex{\openout\indexfile=\jobname.inx
                \global\let\writeindex=\toindex \toindex}
\def\inx#1{\writeindex{\nomathexp{#1} @\folio.}}
\def\index#1{\inx{#1}#1}
\def\closeindex{\vfil\eject % Ensure final entries are written
                \ifx\writeindex\toindex \immediate\closeout\indexfile \fi}

% Layout style

\font\boldit=cmbxti10 % for subsection headings
\font\ssq=cmssq8 \font\ssqi=cmssqi8 % for quotations

\newcount\secno \newcount\subsecno \newcount\proclno \newcount\itemno
\reset\secno \reset\subsecno \reset\proclno \reset\itemno
\newdimen\itemindent \itemindent=\parindent % the default, but changable
\newtoks\marktoks

\let\Sec\S % Section mark
\useouter beginsection
 \outer\def\newsection #1.
  {\ifnewsec \endgroup \fi % previous (sub)section might be empty
   \global\advance\secno by 1
   \ifnum-1<\subsecno \reset\subsecno \fi % <0 means no subsections used
   \reset\proclno
   \edef\lastlabel{\number\secno}%
   {\parskip0pt\beginsection\ifnomessage\Sec\fi\lastlabel. #1.\par
    \par}% immediately terminate the paragraph started by \beginsection
   \setmark{#1}% this mark follows the non-breakable space below the title
   \startsec % this replaces the indent-defeating code of \beginsection
  }
\def\subsection #1.
  {\secbigbreak
   \global\advance\subsecno by 1 \reset\proclno
   \edef\lastlabel{\number\secno.\number\subsecno}%
    \leftline{\bf\lastlabel.\enspace
              \defnext{#1}\ifx\next\empty\else \boldit#1.\fi}\setmark{#1}%
    \nobreak\smallskip\startsec}
\useouter beginsection
 \outer\def\Appendix #1.
  {\ifnum\secno>0 \startapx\fi
   \global\advance\secno by -1 \reset\subsecno \reset\proclno
   \edef\lastlabel
    {\ifcase -\secno \or A\or B\or C\or D\or E\or F\or G\or H\or I\or J\fi}%
   {\parskip0pt\beginsection Appendix \lastlabel. #1.\par\par}%
   \setmark{#1}\startsec}
\def\startapx{\ifx\writetoc\totoc\totoc{\str\Appendices}\fi \secno=0 }
\useouter beginsection
 \outer\def\Supplement #1.
  {\let\lastlabel=\empty
   \global\ifnum\secno<0 \secno=1000 \else\advance\secno by 1 \fi
   \beginsection #1.\par\par\setmark{#1}\startsec}
\useouter beginsection
 \outer\def\NotocSection #1.
  {\let\lastlabel=\empty \reset\secno
   \beginsection #1.\par\par\putmark{#1}\startsec}

\newif\ifnewsec % communication with proclaim etc.
\def\startsec
  {\begingroup \newsectrue\parskip0pt\parindent0pt \everypar{\endgroup}}
\def\secbigbreak
  {\ifnewsec \endgroup
     \ifdim\lastskip<\bigskipamount \removelastskip\bigskip \fi % no penalty
   \else \bigbreak
   \fi}
\def\secmedbreak
  {\ifnewsec \endgroup
     \ifdim\lastskip<\medskipamount \removelastskip\medskip \fi % no penalty
   \else \medbreak
   \fi}
\def\labelsec#1{\global\let#1=\lastlabel \deflab#1\nobreak}% prolong nobreak

% for \startsec to work properly, a paragraph should not begin with `{text}'
% here we fix those macros that do such a thing. In the meantime we deactivate
% the accents within messages, so that only the base character will appear

{\let\x=\expandafter
 % in the following macro #1 is the \cs to be redefined; \next is defined to
 % do the redefinition, which it achieves using the old expansion passed to it
 % as an argument; after defining \next, it is called with the expansion of #1
 \def~#1{\defnext##1{\gdef#1{\ifnomessage\leavevmode##1\fi}}\x\next\x{#1}}
 ~\copyright
 % the following is similar, but now \cs itself takes one argument. When
 % passing the 'expansion' of \cs, that argument is given as '#1', which will
 % capture the formal argument of \cs in the redefinition within \next
 \def~#1{\defnext##1{\gdef#1####1{\ifnomessage\leavevmode##1\else####1\fi}}%
         \x\next\x{#1{##1}}}
 ~\` ~\' ~\v ~\^^_ ~\u ~\^^S ~\= ~\^ ~\^^D ~\. ~\H ~\~ ~\" ~\t
}


\def\quotation{\begingroup\everypar{}\parfillskip=0pt
  \leftskip=0pt plus \hsize \def\par{\ifhmode\/\endgraf\nobreak\fi}\obeylines
  \let\it=\ssq\let\rm=\ssqi\rm % switch roman and italic
  \baselineskip=10pt\parskip=0pt}
\def\author#1, #2.{\vskip2pt\it #1, \rm #2\par\smallskip\endgroup}

\newcount\eqnumber \eqnumber=0
\def\neqn(#1#2){\global\advance\eqnumber by 1
                (\ifcat a\noexpand#1%
                        \errmessage{Incorrect label #1#2}\number\eqnumber
                 \else\xdef#1{\number\eqnumber}\deflab#1%
                      #1\rm#2% #2 is possible tail, like "a,b"
                 \fi)}
\def\label{\ifinner\else \eqno \fi \neqn}
\def\nn{\label(\lastlabel)}
\newcount\acc
\def\add#1#2{\acc=#1\advance\acc#2\relax\number\acc}

\def\heading "#1"{\smallbreak\noindent{\sl #1}.\quad\ignorespaces}
\outer\def\proclaim#1. #2#3\par
  {\secmedbreak \global\advance\proclno by 1 \reset\itemno
   \edef\lastlabel{\number\secno\ifnum-1<\subsecno.\number\subsecno
                                \fi.\number\proclno}
   {\interlinepenalty=300 \parskip=0pt\def\par{\endgraf\penalty200 }% (item)
    \noindent % Emit \baselineskip & \parskip glue BEFORE doing \deflab
    \if\let\noexpand#2% Is #2 a control sequence?
     \ifx\undefined#2% don't redefine a control sequence
      \global\let#2\lastlabel \deflab#2\letnext\ignorespaces
     \else\defnext{#2}\fi
    \else\defnext{#2}\fi
    \bf\lastlabel.\enspace#1.\enspace \sl\next#3\endgraf}%
   \ifdim \lastskip<\medskipamount \removelastskip\penalty55\medskip \fi}
\def\dueto#1.{\unskip~[#1].}

\def\newpar{\ifhmode\par\fi{\parskip0pt\noindent}}% no extra vertical space
\def\enditem{\newpar\reset\itemno}
\def\item{\doindent\itemindent}
\def\itemitem{\doindent{2\itemindent}}
\def\doindent#1#2{\newpar
  \hangindent#1\hangafter0 \llap{#2\enspace}\ignorespaces}

\def\statitemnr#1{(\number#1)}
\def\statitem{\global\advance\itemno by 1 \item{\statitemnr\itemno}}
\def\eqitemnr#1{(\romannumeral#1)}
\def\eqitem{\global\advance\itemno by 1 \item{\eqitemnr\itemno}}
\def\defitemnr#1{\count@=#1\advance\count@96\char\count@.}
\def\defitem{\global\advance\itemno by 1 \item{\defitemnr\itemno}}

\def\proof{\heading "Proof"} \def\proofof#1{\heading "Proof of #1"}
\def\QED{\dimen0=.5em\advance\dimen0\wd\QEDbox\advance\dimen0.4pt
         \unskip\kern\dimen0\vadjust{\vskip-\baselineskip}\unhcopy\tightbox
         \copy\QEDbox{\pretolerance=1000\parfillskip=0.4pt\smallbreak}}
\def\QEDQED{\unskip\nobreak\enskip\kern\wd\QEDbox
            {\setbox\QEDbox=\hbox{\copy\QEDbox\enspace\copy\QEDbox}\QED}}

\def\emph#1{{\it #1}\futurelet\next\doitcor}
\def\newterm#1{{\sl\index{#1}}\futurelet\next\doitcor}
\def\foreign#1{{\sl #1}\futurelet\next\doitcor}
\def\doitcor{\if.\next\else\if,\next\else\/\fi\fi}
\def\needfil{\penalty-100\vfil\penalty1500\vfilneg}% raggedbottom, if needed
\def\bigdisplay{\ifmmode \errmessage{Display begun in math mode.}
                \else\ifhmode\unskip\vadjust{\needfil}%
                     \else\needfil\noindent\fi$$\fi}
\def\frame#1{\leavevmode\hbox{\vrule\vtop{\vbox{\hrule\kern2pt
     \hbox{\strut\kern2pt#1\kern2pt}}\kern2pt\hrule}\vrule}} % framed box
\def\clap#1{\hbox to 0pt {\hss#1\hss}}

\def\setbaselineskip{\par\afterassignment\setbskip\skip0 =}
\def\setbskip{\null\baselineskip=\skip0 \vskip-\baselineskip}
\def\forceeven{\eject\ifodd\pageno \null\mark{\marktoks{}}\vfil\eject \fi}
\def\forceodd{\eject\ifodd\pageno\else\null\mark{\marktoks{}}\vfil\eject\fi}
\def\topglue{\eject\afterassignment\topglu\skip0 }
\def\topglu{\hrule height0pt\vskip\skip0\vskip-\topskip
     \dimen0=\baselineskip\advance\dimen0-\topskip \prevdepth=\dimen0 }
\def\endraggedbottom{\par\penalty9999 % allow overfull page to go
  \normalbottom{\output={\unvbox255\penalty0 }\eject}}
% output routine resets topskip glue

\def\qdef#1{\?\ifx #1\undefined \then \def #1%
              \else \toks0={#1}\afterassignment\chkdef\def\next
              \fi}
\def\qqdef#1{%
\?\ifx #1\undefined
  \then \message{Patching definition:\string#1.}\let\Qdef=\qdef\def#1%
  \else \toks0={#1}\afterassignment\chkdef\def\next
  \fi}
\let\Qdef=\qqdef
\def\chkdef{\expandafter\let\expandafter\curcs\the\toks0 % space is crucial!
  \ifx\next\curcs\else
  \message{Altered definition:\the\toks0= \meaning\next,
                              should have been \meaning\curcs.}\fi}
\def\text#1{\quad\hbox{#1}\quad} \def\ttext#1{\qquad\hbox{#1}\qquad}
\def\tex#{\quad\hbox}            \def\ttex#{\qquad\hbox}
\def\calign #1{\null\,\vcenter{\openup1\jot
     \ialign{\strut\hfil$\displaystyle##$\hfil\cr#1\crcr}}\,}

% Symbols

\newcount\t@
\def\mathdef #1=#2 #3%
{\count@=\z@
 {\def\t{#2}\nottrue
  \loop \xdef\next{\ifcase \count@
    Ord\or Op\or Bin\or Rel\or Open\or Close\or Punct\or VarFam\else #2\fi}%
    \ifx \next\t \notfalse \fi
  \ifnot \global\advance\count@ by 1 \repeat
 }\multiply\count@"1000
 \t@=\expandafter
 \ifx\expandafter\delimiter#3\divide\t@"1000 \nottrue
 \else
   \ifcat \alpha#3#3\nottrue
   \else \mathcode`#3 \ifnum\t@<"7000 \nottrue \else \notfalse \fi
   \fi
 \fi
 \advance\count@\t@
 \ifnot \divide\t@"1000 \multiply\t@"1000 \advance\count@-\t@
   \mathchardef#1=\count@
 \else \divide\t@"100 \multiply\t@"100 \advance\count@-\t@
   \def\next{#1}\afterassignment\mathd@f \t@=
 \fi
}
\def\mathd@f
{\multiply\t@"100 \advance\count@\t@ \expandafter\mathchardef\next=\count@}
\def\mathorddef #1={\mathdef #1=Ord }

\mathorddef\N=N\bffam
\mathorddef\Z=Z\bffam
\mathorddef\Q=Q\bffam
\mathorddef\R=R\bffam
\mathorddef\C=C\bffam
\mathorddef\P=P\bffam
\def\Np{\N_{>0}}
\mathorddef\1=1\bffam
\mathorddef\2=2\bffam
\mathorddef\ii=i\bffam % imaginary unit
\mathorddef\\=\lambda
\mathdef\:=Punct :
\let\Id=\1
\mathorddef\Sym=S\bffam % symmetric group

\def\opdef#1{{\escapechar-1\xdef#1{\mathop{\fam0 \string#1}\nolimits}}}
\def\altopdef#1#2{\def#1{\mathop{\rm #2}\nolimits}}
\def\li(#1#2..#3){%
  {#1_{#2}},\penalty\binoppenalty\ldots,\penalty\binoppenalty#1_{#3}}
\def\lix(#1#2.#3.#4){%
  {#1_{#2}},\penalty\binoppenalty\ldots,\widehat#1_{#3},\penalty\binoppenalty
  \ldots,#1_{#4}}
\def\({\bigl(}\def\){\bigr)}
\def\inv{^{-1}}
\def\<#1>{{\langle #1\rangle}}
\let\oslash=\o \def\o{^\circ} \def\p{^\perp}

\def\defeq{\buildrel\topsmash{\rm def}\over =}
\mathdef\orbit=Bin \backslash
\mathdef\union=Rel \cup \mathdef\Union=Op \bigcup
\let\disju=\amalg \let\Disju=\coprod
\let\tensor=\otimes \let\Tensor=\bigotimes
\let\directsum=\oplus \let\Directsum=\bigoplus
\def\setof#1:#2\endset{{\{\,#1\mid#2\,\}}}
\def\Setof#1:#2\endset{\left\{\,#1\,\,\vrule\,\,#2\,\right\}}
\let\isom=\cong \let\cong=\equiv \let\equiv=\sim % correct wrong names
\def\isomto{\buildrel\equiv\over\rightarrow}
\def\otmosi{\buildrel\equiv\over\leftarrow}
\let\ssubset=\subset \let\subset=\subseteq
\let\ssupset=\supset \let\supset=\supseteq
\mathdef\implies=Rel \Rightarrow
\mathdef\thru=Bin \cap
\mathdef\Thru=Op \bigcap
\mathdef\act=Bin \cdot
\let\eps=\varepsilon
\mathdef\after=Bin \circ % function composition
\let\baraccent=\= \def\={\relax\?\ifmmode\then\approx\else\baraccent\fi}

\opdef\sg \opdef\Ker\opdef\Im \opdef\Aut \opdef\End \opdef\rk
\altopdef\kar{char}
\def\Card#1{\##1}

% Standard abbrev.'s

\def\mo.{morphism}
\def\iso.{iso\mo.}
\def\cor.{correspond}
\def\de.{definition}
\def\De.{Definition}
\def\lcit{loc.\thinspace cit.}

% Boxes

\def\topsmash#1{{\def\finsm@sh{\ht\z@\z@ \box\z@}\smash{#1}}}
\def\botsmash#1{{\def\finsm@sh{\dp\z@\z@ \box\z@}\smash{#1}}}


\newbox\tightbox % for "tight" breaks
\setbox\tightbox=
\hbox{\penalty -200               \skip0 = 0pt plus 0.05 \hsize
      \hskip \skip0 \penalty    0 
      \hskip \skip0 \penalty  200 \skip0 = .1\hsize
      \hskip \skip0 \penalty  283 
      \hskip \skip0 \penalty  346
      \hskip \skip0 \penalty  400
      \hskip \skip0 \penalty  447 
      \hskip \skip0 \penalty  490
      \hskip \skip0 \penalty  529
      \hskip \skip0 \penalty  567 
      \hskip \skip0 \penalty  600
      \hskip \skip0 \penalty  632
      \hskip 2\hsize % make it an offer TeX can't refuse
      \vadjust{}\hfil} % warning if you change \hsize do it FIRST. 
\newbox\QEDbox
\setbox\QEDbox=\hbox
{\kern-0.2pt\vrule height 6pt \kern-0.4pt % backspace
 \vbox to 6pt
  {\kern -0.2pt
   \hbox to 6.4pt{\hrulefill\kern-0.2pt\vrule}\vfil
   \hrule width 6.2pt
   \kern -0.2pt}%
 \kern-0.4pt \vbox to 6pt{\leaders\vrule\vfil\kern-0.2pt}\kern-0.2pt
}

% Nine point type (for footnotes and references); math sizes 9--7--5 pt

\ifx\ninept\undefined % don't overwrite more sophisticated \ninept macros

\font\ninerm=cmr9 \font\nineit=cmti9 \font\ninebf=cmbx9 \font\ninesl=cmsl9
\font\ninett=cmtt9 \font\ninei=cmmi9 \font\ninesy=cmsy9
\skewchar\ninei='177 \skewchar\ninesy='60

\def\ninept
{\def\rm{\fam0\ninerm}\def\it{\fam\itfam\nineit}\def\bf{\fam\bffam\ninebf}%
 \def\sl{\fam\slfam\ninesl}\def\tt{\fam\ttfam\ninett}\rm
 \textfont0\ninerm \textfont1\ninei \textfont2=\ninesy
 \textfont\itfam\nineit \textfont\slfam\ninesl
 \textfont\bffam\ninebf \textfont\ttfam\ninett
 \normalbaselineskip=11pt \normalbaselines
 \setbox\strutbox=\hbox{\vrule height 8 pt depth 3 pt width 0 pt}%
}

\fi

\def\caps#1{{\ninept #1}}

% redefine footnotes to be in 9pt type and independent of context settings
\def\vfootnote#1%
{\insert\footins\bgroup \ninept
 \interlinepenalty=\interfootnotelinepenalty
 \splittopskip=\ht\strutbox % determines top baselines of broken footnotes
 \splitmaxdepth=\dp\strutbox % likewise for bottom lines
 \floatingpenalty=20000 % please don't break footnotes, if possible
 \leftskip=1pc \rightskip=1pc \spaceskip=0pt \xspaceskip=0pt
 \parindent=0pt \parskip=3pt minus 1pt \parfillskip=0pt plus 1 fil
 \textindent{#1}\footstrut\futurelet\next\f@@t
}


% References

\catcode`_=11 % control sequence names with this letter are private

\def\label_#1#2{\expandafter\xdef \csname#1.\endcsname{#2}}
\def\ref#1{\ref_#1,,,.}
\def\ref_#1,#2,,#3.{\expandafter\ref_lab\csname#1.\endcsname{#3#2}}
\def\ref_lab#1#2{\ifx #1\relax \errmessage{Reference to undefined label}%
                 \else [#1#2]\fi
                }
\newdimen\refindent
\refindent=36pt

\def\initrefs % For initialising reference labels at start of article
{\begingroup\setbox0=\vbox\bgroup
 \def\chapter ##1\par{}% avoid problems with chapter number and tocfile
 \def\endrefs{\egroup\egroup\endgroup}% end \beginrefs & \init_ref
 \let\author=\_auth \let\title=\_tit \let\vol=\_vol
 \def\endref{\iffalse{\fi}\ifx\the_key\undefined\else
    \label_{\expandafter\strip_space\the_key _}%
           {\expandafter\strip_space\the_mark _}\fi
    \endgroup}%
}
\def\readrefs{\initrefs \input \jobname.ref }

\def\strip_space #1 _{#1}

\def\ref_item#1{\iffalse{\fi}% must have an unbalanced explicit brace here
  \ifx#1\undefined \else
    \errmessage{Multiple definition of #1 within reference}\fi
  \edef#1{\iffalse}\fi
}

\outer\def\beginrefs{\noindent\par % fire up \everypar
  \bgroup \ninept
  \frenchspacing\tolerance=900
  \let\ref=\_ref \let\author=\_auth \let\title=\_tit
  \let\vol=\_vol \let\year\_year}

\outer\def\endrefs{\egroup\smallbreak}

\def\_ref{\begingroup
  \def\par{\endref\par}\def\ref{\endref\ref}\edef\the_mark{\iffalse}\fi}
\def\_auth{\ref_item\the_author}
\def\_tit{\ref_item\the_title}
\def\key{\ref_item\the_key}
\def\series{\ref_item\the_series}
\def\publ{\ref_item\the_publ}
\def\ISBN{\ref_item\the_ISBN}
\def\journal{\ref_item\the_journal}
\def\_vol{\ref_item\the_vol}
\def\_year{\ref_item\the_year}
\def\pages{\ref_item\the_pages\range_}
\def\npages{\ref_item\the_pages\amount_}
\def\idno{\ref_item\the_idno}
\def\inbook{\ref_item\the_inbook}
\def\ed{\ref_item\the_ed}
\def\report{\ref_item\the_report}
\def\endnote{\ref_item\the_endnote}

\def\range_{\noexpand\range_}   % these cancel the \edef in \ref_item
\def\amount_{\noexpand\amount_}
\def\do_amount{{\aftergroup\do_pp\aftergroup}}
\def\do_pp{~pp}
\def\expl_pp{\def\range_{pp.~}\let\amount_=\do_amount} % if `pp.' is desired
\def\impl_pp{\let\range_\empty\let\amount_=\do_amount} % if `pp.' not desired

\def\_opt#1#2{\ifx#1\undefined\else{\def\__{#1\unskip}#2}\fi}

\def\q_plur#1{\expandafter\q_s#1,_}\def\q_s#1,#2_{\ifx _#2_\else s\fi}

\def\_pages{\expandafter\pages_\the_pages\unskip---_}
\def\pages_#1-#2#3-#4_{#1\ifx _#4_\else\if -#2--#3\else --#2#3\fi\fi}
\def\opt_pages#1{\ifx\the_pages\undefined\else{\let\__\_pages#1}\fi}

\def\endref
{\iffalse{\fi}\let\par\endgraf\smallbreak\hangindent\refindent
 \setbox0=\hbox{[\the_mark\unskip]\enspace}\noindent
 \ifdim\wd0<\refindent \hbox to \refindent{\unhbox0\hfil}\else\unhbox0 \fi
 \format_author{\the_author\unskip},
 \ifx\the_inbook\undefined
   \ifx\the_journal\undefined
     \ifx\the_publ\undefined
       \ifx\the_report\undefined 
	 \errhelp{A reference must at least have a \journal \inbook \publ^^J
        	  or \report field defined.}%
         \errmessage{Unrecognised reference}%
       \else \format_report \fi
     \else \format_book \fi
   \else \format_article \fi
 \else\format_proceedings \fi
 \unskip \_opt\the_endnote{. \__}.
 \endgraf\endgroup
}

\def\format_author#1{{\rm#1}}

\def\format_report
{{\sl \the_title\unskip}, \the_report\unskip\expl_pp\opt_pages{, \__}%
 \_opt\the_year{, (\__)}}
\def\format_book
{{\sl\the_title\unskip},\expl_pp\opt_pages{ \__,}%
 \_opt\the_series{ \__\_opt\the_ed{ (\__, ed\q_plur\the_ed.)}%
 \_opt\the_vol{ \__}\_opt\the_idno{, \__},} \the_publ\unskip,
 \the_year\unskip\_opt\the_ISBN{, ISBN \__}}
\def\format_article
{``\the_title\unskip'', {\sl\the_journal\unskip\_opt\the_vol{\/ \bf\__}}%
 \_opt\the_idno{, \__}\_opt\the_year{, (\__)}\impl_pp\opt_pages{, \__}}
\def\format_proceedings
{``\the_title\unskip'',\expl_pp\opt_pages{ \__} in {\sl\the_inbook\unskip}%
 \_opt\the_ed{ (\__, ed\q_plur\the_ed.)},
 \_opt\the_series{\__\_opt\the_vol{ \__}\_opt\the_idno{, \__}, }%
 \_opt\the_publ{\__, }\the_year}

\catcode`_=8 % Now underscores are for subscripts again
\catcode`@=12 % and `@' cannot be used in control sequences
% END of marxmax.tex

%\maketoc % uncomment if you want a table of contents at the end

\refindent=2.7pc

\font\frak=eufm10

\opdef\Tab \opdef\Pic \opdef\dom
\def\pic{\pi_{\rm c}}
\def\pir{\pi_{\rm r}}
\def\LRT{T'}
\def\Anm{A_{n-1}}

\mathorddef\A=A2
\def\Pdom{{\cal P}^+}
\def\gl{\hbox{\frak gl}}
\def\g{\hbox{\frak g}}
\def\h{\hbox{\frak h}}
\def\b{\hbox{\frak b}}
\def\ch{^\vee}

\def\+{\item{$\circ$}}

\opdef\m
\def\mm<#1+#2,#3>{\lfloor\if0#1\else#1+\fi#2\rfloor_{#3}}

%\readrefs ->
\initrefs
%\input \jobname.ref 
\beginrefs

\ref KaNa \key crystal graphs
\author M. Kashiwara and T. Nakashima
\title Crystal graphs for representations of the $q$-analogue of classical
       Lie algebras
\journal Journal of Algebra \vol 165 \pages 295-345 \year 1994
\endref

\ref vLee1 \key van Leeuwen festschrift
 \author M. A. A. van Leeuwen
 \title The Robinson-Schensted and Sch\"utzenberger algorithms, an elementary
        approach
 \journal Electronic J. of Combinatorics \vol 3 (no.~2) \idno R15 \year 1996
 \npages 32
\endref

\ref vLee2 \key van Leeuwen pictures
 \author M. A. A. van Leeuwen
 \title Tableau algorithms defined naturally for pictures
 \journal Discrete Mathematics \vol 157 \year 1996 \pages 321-362
\endref

\ref vLee3 \key van Leeuwen edge sequences
 \author M. A. A. van Leeuwen
 \title Edge sequences, ribbon tableaux, and an action of affine permutations
 \report Report MAS-R9707, CWI, Amsterdam
 \endnote To appear in {\sl European Journal of Combinatorics}
\endref

\ref vLee4 \key van Leeuwen domino tableaux
 \author M. A. A. van Leeuwen
 \title Some bijective correspondences involving domino tableaux
 \report Report MAS-R9708, CWI, Amsterdam
\endref

\ref Litt1 \key Littelmann Kac-Moody
 \author P. Littelmann
 \title A Littlewood-Richardson rule for symmetrizable Kac-Moody algebras
 \journal Inventiones mathematicae \vol 116 \year 1994 \pages 329-346
\endref

\ref Litt2 \key Littelmann paths
 \author P. Littelmann
 \title Paths and root operators in representation theory
 \journal Annals of Mathematics \vol 142 \year 1995 \pages 499-525
\endref

\ref Litt3 \key Littelmann plactic
 \author P. Littelmann
 \title A plactic algebra for semisimple Lie algebras
 \journal Advances in Math. \vol 124 (2) \year Dec. 1996 \pages 312-331
\endref

\ref Macd \key Macdonald
 \author I. G. Macdonald
 \title Symmetric Functions and Hall Polynomials
 \publ Clarendon press, Oxford \year 1979
 \series Oxford Mathematical Monographs
\endref

\ref Rob \key Robinson
 \author G. de B. Robinson
 \title On the representations of the symmetric group
 \journal American Journal of Math. \vol 60 \year 1938 \pages 745-760
\endref


\ref Zel1 \key Zelevinsky pictures
 \author  A. V. Zelevinsky
 \title A Generalisation of the Littlewood-Richardson Rule and the
  Robinson-Schensted-Knuth Correspondence
 \journal Journal of Algebra \vol 69 \year 1981 \pages 82-94
\endref


\endrefs
% END of pathjdt.ref

\Author={Marc A. A. van Leeuwen}
\email={maavl@mathlabo.univ-poitiers.fr}
\URL{wwwmathlabo.univ-poitiers.fr/~maavl/}

\title={An analogue of Jeu de taquin for Littelmann's crystal paths}
\MSCcodes={05E10}
\keywords{Jeu de taquin, Littlewood-Richardson rule, crystal graphs,
  path crystals}

\abstract

Littelmann has given a combinatorial model for the characters of
representations of semisimple Lie algebras, in terms of certain paths traced
in the space of (rational) weights. From it, a description of the
decomposition of tensor products can be derived that generalises the
Littlewood-Richardson rule (the latter is valid in type~$A_n$ only). We
present a new combinatorial construction that expresses in a bijective manner
the symmetry of the tensor product in this path model. In type~$A_n$, where
there is a correspondence between paths and skew tableaux, this construction
is equivalent to Sch\"utzen\-berger's \foreign{jeu de taquin}; in the general
case the construction retains its most crucial properties of symmetry and
confluence.

\maintext

\newsection Introduction.

In this note we wish to present a simple construction that appears to arise
naturally in the context of Littelmann's paths. Indeed, we found it while
trying to formulate an answer to a question asked (by Alain Lascoux) during a
lecture by Littelmann on this subject at the S\'eminaire Lotharingien; the
question was whether one could exhibit combinatorially the symmetry of the
tensor product in the formula given, in terms of paths, for tensor product
decompositions.

This paper is organised as follows. After recalling some of Littelmann's
notions in \Sec2, we analyse the symmetry of the traditional
Littlewood-Richardson rule in \Sec3, and translate the procedure that exhibits
the symmetry (which is essentially jeu de taquin) into the language of paths.
Then in \Sec4 we extend this construction successively to two broader classes
of paths, with instances for other types of groups than~$A_n$, namely the
classes of $m$-paths (built from the path models of minuscule representations)
and of $\psi$-paths (incorporating also the path models of quasi-minuscule
representations); the latter removes any restrictions on the type of the group
or the representation. Finally in \Sec5 we give a construction in the context
of arbitrary piecewise linear paths that generalises the earlier
constructions; however, we have not (yet) established the essential connection
with Littelmann's root operations for this general construction.

\newsection Notations used.

We shall assume without explicit reference the notations and results of
\ref{Littelmann paths}. We mention in particular the following notations. We
denote by~$X$ the weight lattice of a complex Lie algebra~$\g$, that for
simplicity we shall assume to be finite dimensional and reductive, and by
$\Pi$ the set of piecewise linear paths in the space $X_\Q=X\tensor_\Z\Q$ of
rational weights. All paths are parametrised by the interval~$[0,1]\subset\Q$,
and start at~$0$, so that $\pi(0)=0$ for all $\pi\in\Pi$, while $\pi(1)$
denotes the end point of~$\pi$. For $\mu\in X$, the straight path from~$0$
to~$\mu$ is denoted by~$\pi_\mu$. The reverse or dual path of $\pi\in\Pi$ is
denoted by $\pi^*$, and $\pi*\pi'$ denotes the concatenation of two paths. The
set of paths~$\pi$ such that $\pi(t)$ is dominant for all $t\in[0,1]$, and
such that $\pi(1)\in X$ (i.e., it is an integral dominant weight), is denoted
by $\Pdom$. The root operators $e_\alpha$ and $f_\alpha$ formally act on the
free $\Z$-module $\Z\Pi$, but since the image of every generator $\pi\in\Pi$
of that $\Z$-module is either another such generator or~$0$, we shall consider
the root operators as maps $\Pi\to\Pi\union\{0\}$. The subset of $\Pi$
reachable from some $\pi\in\Pdom$ by repeated application of root operators is
denoted by~$B_\pi$. To avoid too deeply nested subscripts we shall write
$e_i$~and~$f_i$ for the root operators $e_{\alpha_i}$~and~$f_{\alpha_i}$. For
a weight~$\\$, a path~$\pi$ and a simple root~$\alpha$, we shall write
$\mm<\\+\pi,\alpha>$ for the number $\min_{t\in[0,1]}\<\\+\pi(t),\alpha\ch>$,
or simply $\mm<0+\pi,\alpha>$ if $\\=0$; the path $\pi$ is called
$\\$-dominant if $\mm<\\+\pi,\alpha>\geq0$ for all simple roots~$\alpha$.

\newsection Paths in type $\Anm$, tableaux, and jeu de taquin.

We shall first consider the correspondence between paths in type~$\Anm$ and
Young tableaux, and the connection between the Littlewood-Richardson rule in
terms of paths and the classical one. Then we shall consider the question of
symmetry of these rules with respect to the order of the tensorands.

\subsection Paths and Littlewood-Richardson tableaux.

Let us first recall the well known correspondence between partitions with at
most $n$~parts and dominant integral weights for~$\g=\gl_n$.
Let~$\h\subset\gl_n$ be the Cartan subalgebra consisting of diagonal matrices,
and $\b\subset\gl_n$ the Borel subalgebgra of upper triangular matrices. For
$i=1,\ldots,n$ let $\eps_i\in\h^*$ be the weight that takes the $(i,i)$
diagonal entry; then the set of simple roots with respect to~$\b$ is
$\setof\alpha_i:i=1,\ldots,n-1\endset$ where $\alpha_i=\eps_i-\eps_{i+1}$, and
the set of fundamental weights is $\setof\omega_i:i=1,\ldots,n-1\endset$ where
$\omega_i=\sum_{j\leq i}\eps_j$. We shall identify any vector
$\\=(\li(\\1..n))\in\Z^n$ with the weight $\sum_{i=1}^n\\_i\eps_i$; since one
has $\<\\,\alpha_i\ch>=\\_i-\\_{i+1}$, it follows that this is a dominant
integral weight if and only if $\\$ is a partition.

Now we shall define a correspondence between the set~$\Tab_\mu$ of
semistandard Young tableaux of shape~$\mu$, and the set~$B_\pi$ for a specific
path~$\pi=\pic(\mu)\in\Pdom$, which is determined as follows. Write $\mu$ as a
sum of terms~$\omega_i$ (so the term $\omega_i$ is repeated $\mu_i-\mu_{i+1}$
times) ordered by (weakly) increasing index~$i$, and then replace each
$\omega_i$ by its expression $\sum_{j\leq i}\eps_j$ as a sum of
terms~$\eps_j$, again ordered by increasing index. The path~$\pic(\mu)$ is
obtained from the resulting sum by replacing each of the $|\mu|$ terms of the
form~$\eps_j$ by the corresponding path~$\pi_{\eps_j}$, and addition by
concatenation. We shall call any path of the form
$\pi_{\eps_{j_1}}*\cdots*\pi_{\eps_{j_l}}$ an $\eps$-path of length~$l$; such
paths are characterised by the sequence $\li(j1..l)$ of indices. If $f_i$ is
applied to an $\eps$-path and the result is not~$0$, then it changes one
segment $\pi_{\eps_i}$ into $\pi_{\eps_{i+1}}$. Therefore any path
in~$B_{\pic(\mu)}$ is an $\eps$-path of length~$|\mu|$. Inserting its sequence
of indices into a Young diagram of shape~$\mu$, proceeding by columns from
right to left and from top to bottom within each column, one obtains a
tableau, and it can be shown that this defines a bijection
from~$B_{\pic(\mu)}$ to~$\Tab_\mu$. Note that a subsequence of segments
contributing to any one column of length~$i$ of the tableau stems from the
sequence of segments~$\pi_{\eps_j}$ corresponding (before application of
the~$f_\alpha$) to one term~$\omega_i$ in the sum for~$\mu$.

\heading "Remark" In fact one could have used instead of~$\pic(\mu)$ another
path~$\bar\pic(\mu)$, formed by concatenating straight line
paths~$\pi_{\omega_i}$ corresponding to the terms~$\omega_i$ in the first sum
for~$\mu$. One then obtains a bijection between $B_{\bar\pic(\mu)}$ and the
\emph{same} set~$\Tab_\mu$ of tableaux: every application of $f_\alpha$ that
does not yield~$0$ transforms one path segment into another straight segment,
of the form~$\pi_{\eps_I}$ with $I$ an $i$-element subset of~$\{1,\ldots,n\}$
and $\eps_I=\sum_{j\in I}\eps_j$; that segment corresponds to a column with
set of entries~$I$ in the Young tableau. Remarkably, $\Tab_\mu$ can even be
used to describe in a direct way many other sets $B_{\pi'}$, where
$\pi'\in\Pdom$ is an $\eps$-path. For instance, if $\pir(\mu)$ denotes the
$\eps$-path corresponding to the expression $\mu=\sum_{i=1}^n\mu_i\eps_i$
(i.e., with weakly increasing indices), then each path in~$B_{\pir(\mu)}$ is
an $\eps$-path whose sequence of indices is obtained by listing the entries of
a tableau in~$\Tab_\mu$ \emph{by rows} from right to left. We have given
prominence to $\pic(\mu)$ rather than to $\pir(\mu)$ because it seems to be
the preferred choice for mathematical reasons: the proof that $B_\pi$
corresponds to $\Tab_\mu$ is the easiest for $\pi=\pic(\mu)$, and the relation
between $B_{\pic(\mu)}$ and a set of tableaux has analogues in other classical
types (see~\ref{crystal graphs}), which is not the case with~$B_{\pir(\mu)}$.
Historically however it is (the set of sequences of indices corresponding to)
$B_{\pir(\mu)}$ that has received more attention: for instance, the fact that
the operators~$e_\alpha$ preserve compatibility with the tableau conditions is
already assumed implicitly in \ref{Robinson}, and proved in \ref{Macdonald,
I~(9.6)}. Note also that our choice is not of crucial importance: while the
relation between paths and tableaux was instrumental in finding the
construction presented below, that construction itself will be formulated in
terms of paths, and applicable regardless of any connection of those paths
with tableaux.

By the decomposition formula of \ref{Littelmann paths}, the multiplicity of
the irreducible $\gl_n$-module $V_\nu$ in the tensor product $V_\\\tensor
V_\mu$ equals the number of $\\$-dominant paths in~$B_{\pic(\mu)}$ of
weight~$\nu-\\$, i.e., paths $\pi\in B_{\pic(\mu)}$ for which the translated
path $\\+\pi$ goes from $\\$~to~$\nu$ and lies entirely within the dominant
chamber. Each segment of~$\\+\pi$ goes from one dominant integral weight to
another, so we obtain a sequence of partitions from~$\\$ to~$\nu$ that we
shall call the $\\$-chain of~$\pi$. If $\pi$ was derived, as shown above, from
$T\in\Tab_\mu$, then its $\\$-chain can be formed, starting from~$\\$, by
traversing~$T$ in the order indicated, and for every entry~$i$ encountered
forming a new partition by adding~$1$ to part~$i$ of the previous partition.
If we extend this procedure slightly by filling at each step the square (in
row~$i$) added to the Young diagram of the partition with a particular
number~$r$, then this will associate to~$T$ a Littlewood-Richardson
tableaux~$\LRT$ of shape~$\nu/\\$ and weight~$\mu$ (as used in the classical
formulation of the Littlewood-Richardson rule). It suffices to specify~$r$: it
is the row number in~$T$ of the entry~$i$ encountered at the current step.

In fact this procedure defines a correspondence between the squares~$s$ of~$T$
and the squares~$t$ of~$\LRT$, i.e., a bijection between the squares of the
Young diagram of~$\mu$ and those of the skew diagram $\nu/\\$. This bijection
is such that in~$T$ the square~$s$ contains the row number the corresponding
square~$t$, while in~$\LRT$ the square~$t$ contains the row number of~$s$. It
follws that $T$ can be reconstructed from~$\LRT$ by a quite similar procedure.
In fact one may consider both $T$ and~$\LRT$ merely as ways to represent the
bijection between squares. The bijections so occurring can be characterised by
geometric properties that are contained in the notion of \newterm{pictures}
(\ref{Zelevinsky pictures}); using this notion it becomes obvious that for
$\LRT$ one finds exactly the set of Littlewood-Richardson tableaux of
shape~$\nu/\\$ and weight~$\mu$. Pictures provide a very versatile means to
study these tableaux, due to the fact that many operations can be defined
directly in terms of pictures, see~\ref{van Leeuwen pictures} (in that paper
the conditions in the definition of pictures are transposed; in citing results
we shall adapt for this difference). Below we shall freely use constructions
defined for pictures and their properties; for the convenience of those not
acquainted with pictures, we shall also give the translations of those
constructions in terms of tableaux. It is worth noting that if one takes $T$
to represent a path $\pi'\in B_{\pir(\mu)}$ rather than $\pi\in
B_{\pic(\mu)}$, then one not only obtains the same set of admissible~$T$
(i.e., $\pi$ is $\\$-dominant if and only if $\pi'$~is), but for each such~$T$
the two orders of traversal lead to the same picture (bijection between
squares of~$\mu$ and of~$\nu/\\$), and therefore construct the same
Littlewood-Richardson tableau~$\LRT$. The path~$\pi'$ moreover has the
property that its $\\$-chain gives the standardisation of the semistandard
tableau~$\LRT$, which is not the case with~$\pi$.

\subsection Symmetry of the Littlewood-Richardson rule.

We now turn to the question of exhibiting the symmetry of the tensor product
combinatorially in type~$\Anm$, using Littlewood-Richardson tableaux.

We are looking for a bijection between Littlewood-Richardson tableaux of shape
$\nu/\\$ and weight~$\mu$ on one side, and Littlewood-Richardson tableaux of
shape $\nu/\mu$ and weight~$\\$ on the other side. In terms of pictures such a
bijection is fairly easy to construct. There is a unique picture $\\\to-\\$,
which may be ``glued'' to any given picture $f\:\nu/\\\to\mu$, to form a
picture $\bar f\:\nu\to\mu\uplus-\\$ (the operation `$\uplus$' is
``concatenation'' of skew diagrams in the anti-diagonal direction, or more
precisely of classes of skew diagrams modulo translation in the plane). Then
one can apply the Sch\"utzen\-berger algorithm for pictures to obtain a
picture $S(\bar f)\:\nu\to\\\uplus-\mu$; the image under the inverse picture
$S(\bar f)\inv$ of the factor $-\mu$ of the image is necessarily the
subdiagram~$\mu$ of~$\nu$, so by restriction of~$S(\bar f)$ to the complement
of this subdiagram we obtain the desired picture $\nu/\mu\to\\$. The
construction is easily seen to be involutive, and hence it defines a bijection
between the sets of pictures $\Pic(\nu/\\,\mu)$ and~$\Pic(\nu/\mu,\\)$.

In terms of Littlewood-Richardson tableaux such as~$\LRT$, this construction
amounts to the following. The skew tableau of shape~$\nu/\\$ is extended to a
tableau of shape~$\nu$ by filling each square of~$\\$ with minus its distance
to the bottom of its column in~$\\$ (so the lowest square in each column
gets~$-1$, the square above it~$-2$, etc.); the important property of this
subtableau of shape~$\\$ is that it corresponds under the Sch\"utzen\-berger
involution to the ``canonical'' tableau of shape and weight~$\\$, in which
each row~$i$ is filled with entries~$i$. One then applies the
Sch\"utzen\-berger involution to the full semistandard tableau of shape~$\nu$
to obtain another such tableau in which the multiset of entries is negated, so
that for each of the negative entries in the original tableau (within the
Young diagram of~$\\$) one now has a positive entry (at some other place of
course), and vice versa; the subtableau of positive entries of the new tableau
is a Littlewood-Richardson tableau of shape $\nu/\mu$ and weight~$\\$.

This algorithm can be simplified, if one recalls that one way to compute the
Sch\"utzen\-berger involution applied to a Young tableau~$Y$, is by
``inflation''. This is done by traversing the entries~$i$ of~$Y$ in increasing
order (as usual processing equal entries from left to right), using them to
repeatedly modify a tableau~$Z$, initially empty, as follows: one performs an
outward jeu de taquin slide of~$Z$ into the square occupied by~$i$ in~$Y$,
after which the vacated top-left corner of~$Z$ is filled with the value~$-i$.
Applying this algorithm to the semistandard Young tableau extended
from~$\LRT$, one sees that in a first stage of computation the
Sch\"utzen\-berger involution is applied to the subtableau of shape~$\\$; as
remarked, the result is the canonical tableau of shape~$\\$. In a second stage
outward slides are then applied to this tableau according to~$\LRT$; the
(negative) entries added at the top-left during the second stage can be
ignored, since they will be removed from the final result anyway. So the
bijection expressing the symmetry of the Littlewood-Richardson rule with
respect to the partitions $\\$~and~$\mu$ describing the tensorands is given by
jeu de taquin, rather than by the full Sch\"utzen\-berger algorithm; it is
described in the following proposition, whose proof is contained in the
reasoning above.

\proclaim Proposition. \LRsymprop
A bijection between Littlewood-Richardson tableaux~$L$ of shape $\nu/\\$ and
weight~$\mu$ and Littlewood-Richardson tableaux~$M$ of shape $\nu/\mu$ and
weight~$\\$ is given by the following algorithm: the tableau~$M$ is obtained
from the canonical tableau of shape and weight~$\\$ by applying a series of
successive outward jeu de taquin slides into the squares of~$\nu/\\$, as
ordered by increasing entries in~$L$, where squares with equal entries are
ordered from left to right. Applying the same algorithm to~$M$ (interchanging
the values of $\\$~and~$\mu$) will reconstruct~$L$.
\QED

\subsection Jeu de taquin for chains of partitions, and for paths.

We shall now translate the construction above back in terms of paths, which
will result in a remarkably simple operation that can be generalised to other
types than~$\Anm$. In associating paths with tableaux such as $L$~and~$M$ in
the proposition above, sequences of partitions are natural intermediate
objects: on one hand $L$ is used there only to obtain an ordering of the
squares within its shape~$\nu/\\$, as represented by its standardisation, which
corresponds to a saturated increasing chain of partitions from~$\\$ to~$\nu$;
on the other hand such a chain of partitions is the $\\$-chain of some
$\eps$-path.

As was noted above, the $\\$-chain of a $\\$-dominant path $\pi\in
B_{\pic(\mu)}$ does not correspond to the standardisation of the corresponding
Littlewood-Richardson tableau~$\LRT$. We can nevertheless interpret the jeu de
taquin process as operating directly on paths, in two ways. One is to
pragmatically choose to work with $\\$-dominant paths in~$B_{\pir(\mu)}$
rather than in~$B_{\pic(\mu)}$; as remarked above, the $\\$-chain of such a
path does correspond to the standardisation the associated
Littlewood-Richardson tableau. More fundamentally, one may observe that $\LRT$
really represents a picture $\nu/\\\to\mu$, which has many specialisations
(standard tableaux of shape~$\nu/\\$ that can be associated with it according
to some ``reading'' of~$\mu$); one of these is the standardisation of~$\LRT$,
while the $\\$-chain of $\pi\in B_{\pic(\mu)}$ corresponds to another.
Moreover, different specialisations of the same picture have the property that
when used to determine sequences of jeu de taquin slides, the final effect of
any of these sequences of slides on the same initial tableau is identical
(this is more generally true for tableaux that are dual equivalent).
Therefore, if in proposition~\LRsymprop\ we take for~$L$ the
Littlewood-Richardson tableau constructed from~$\pi\in B_{\pic(\mu)}$, then
the same tableau~$M$ will be computed as in the proposition if we apply slides
according to the $\\$-chain of~$\pi$, rather than according to the
specialisation of~$L$.

We arrive at describing jeu de taquin in terms of chains of partitions. It is
not necessary that the initial tableau to which we apply outward slides is a
Young tableau; therefore we shall admit chains that start in an arbitrary
partition~$\kappa$. Given a saturated increasing chain of partitions
from~$\kappa$ to~$\\$ (for instance, with $\kappa=(0)$, the $0$-chain
of~$\pic(\\)$) corresponding to a (semi)standard tableau~$C$, and a similar
chain from~$\\$ to~$\nu$ (the $\\$-chain of a $\\$-dominant $\eps$-path)
corresponding to a tableau~$L$, the question is to describe the chain of
partitions corresponding to the skew tableau~$M$ resulting from the
application of successive outward jeu de taquin slides to~$C$ into the squares
added in the chain of~$L$. This has been done in \ref{van Leeuwen
festschrift,~\Sec2} (for the Sch\"utzen\-berger algorithm, but it applies also
to jeu de taquin), see also \ref{van Leeuwen domino tableaux,~\Sec2.1}. The
family of partitions~$\\^{[i,j]}$, defined by the fact that
$\\^{[i,0]}$,~\dots,~$\\^{[i,l]}$ is the chain corresponding to the tableau
obtained after applying $i$~slides to~$C$, satisfies a local condition that
allows $\\^{[i+1,j]}$ to be determined when $\\^{[i,j]}$,~$\\^{[i,j+1]}$,
and~$\\^{[i+1,j+1]}$ are given:

\proclaim Rule. \taquinrule
One has $\\^{[i,j+1]}=\\^{[i+1,j]}$ if and only if the two squares of
$\\^{[i+1,j+1]}\setminus\\^{[i,j]}$ are adjacent.

Note that in the case that the mentioned squares are non-adjacent,
$\\^{[i+1,j]}$ is the unique partition strictly between $\\^{[i,j]}$
and~$\\^{[i+1,j+1]}$ that differs from~$\\^{[i,j+1]}$. This rule allows all
partitions~$\\^{[i,j]}$ to be computed when they are initially given only for
pairs~$(i,j)$ with $i=0$ (by means of~$C$) or $j=l$ (by means of~$L$). The
same rule also allows $\\^{[i,j+1]}$ to be determined when
$\\^{[i,j]}$,~$\\^{[i+1,j]}$, and~$\\^{[i+1,j+1]}$ are given. This reaffirms
that the construction of proposition~\LRsymprop\ is its own inverse. Note that
in the proposition we take~$C$ to be the canonical tableau of shape~$\\$; this
is possible since we know that $M$ must be a Littlewood-Richardson tableau,
and therefore be reducible by jeu de taquin to this canonical tableau. In
order to define a similar construction in terms of paths however, it will be
necessary to explicitly supply data corresponding to~$C$: if we want to
construct from a $\\$-dominant path $p\in B_\pi$ a corresponding
$\mu$-dominant path~$p'$ (where $\mu=\pi(1)$), then we must specify the path
$\pi'\in\Pdom$ such that $\mu\in B_{\pi'}$; similiarly the inverse operation
requires $\pi$ to be specified. Therefore the path analogue of the bijection
of proposition~\LRsymprop\ will be a bijective correspondence
$(p,\pi')\leftrightarrow(p',\pi)$.

We shall now reformulate the rule above in terms of $\eps$-paths. With respect
to chains of partitions there are some minor differences. First of all,
partitions are limited to those with at most $n$~parts. Second, we are
interested primarily in the vertical and horizontal difference vectors
$v_{i,j}=\\^{[i+1,j]}-\\^{[i,j]}$ and $h_{i,j}=\\^{[i,j+1]}-\\^{[i,j]}$, which
lie in the set $\{\li(\eps1..n)\}$, and represent segments of $\eps$-paths;
indeed, they are equal to $\eps_r$ where $r$ is the row number of the square
$\\^{[i+1,j]}\setminus\\^{[i,j]}$ respectively of the square
$\\^{[i,j+1]}\setminus\\^{[i,j]}$. Now in case the two squares mentioned in
rule~\taquinrule\ are non-adjacent, the square
$\\^{[i+1,j]}\setminus\\^{[i,j]}$ is equal to
$\\^{[i+1,j+1]}\setminus\\^{[i,j+1]}$, and similarly the square
$\\^{[i,j+1]}\setminus\\^{[i,j]}$ is equal to
$\\^{[i+1,j+1]}\setminus\\^{[i+1,j]}$; in this case we therefore certainly
have $v_{i,j}=v_{i,j+1}$ and (equivalently) $h_{i+1,j}=h_{i,j}$. These two
equalities remain valid in case the squares mentioned in rule~\taquinrule\ are
horizontally adjacent, i.e., they both lie in the same row~$r$, since in that
case $v_{i,j}=v_{i,j+1}=h_{i+1,j}=h_{i,j}=\eps_r$. Therefore, the only case
where $v_{i,j}\neq v_{i,j+1}$, and where $h_{i+1,j}\neq h_{i,j}$, is when the
two squares of $\\^{[i+1,j+1]}\setminus\\^{[i,j]}$ are vertically adjacent;
in that case, if the rows containing these squares are $r$~and~$r+1$, one has
$h_{i,j}=\eps_r=v_{i,j}$ and $v_{i,j+1}=\eps_{r+1}=h_{i+1,j}$. Given these
values of $h_{i,j}$~and~$v_{i,j+1}$ (or of $v_{i,j}$~and~$h_{i+1,j}$), the
condition that there is indeed vertical adjacency can be expressed as
$\\^{[i,j]}_r=\\^{[i,j]}_{r+1}$, or equivalently as
$\<\\^{[i,j]},\alpha_r\ch>=0$. Note that with this condition satisfied it
would not even be possible to have $v_{i,j}=v_{i,j+1}$, since that would
make $\<\\^{[i,j+1]},\alpha_r\ch>=-1$, contradicting the fact that
$\\^{[i,j+1]}$ is a partition, and corresponds to a dominant weight.
We arrive at the following rule that describes how $v_{i,j}$ and $h_{i+1,j}$
are determined by the values of $h_{i,j}$, $v_{i,j+1}$ and $\\^{[i,j]}$.

\proclaim Rule. \epspathrule
One has $v_{i,j}=v_{i,j+1}$ and $h_{i+1,j}=h_{i,j}$, unless for some~$r$ one
has $h_{i,j}=\eps_r$, \ $v_{i,j+1}=\eps_{r+1}$, and
$\<\\^{[i,j]},\alpha_r\ch>=0$, in which case $v_{i,j}=\eps_r$ and
$h_{i+1,j}=\eps_{r+1}$.

We can now reformulate jeu de taquin in terms of $\eps$-paths. A strict
translation of proposition~\LRsymprop\ into this language would give a
statement that only applies to $\eps$-paths that correspond to semistandard
Young tableaux, but as explained above we remove that restriction by supplying
an extra parameter~$\pi'$. To recover that proposition one should take
$\kappa=(0)$, and $\pi'$ equal to the $\eps$-path corresponding to the
canonical tableau of shape~$\\$, i.e., to $\pic(\\)$~or~$\pir(\\)$, depending
on the chosen correspondence between paths and tableaux.

\proclaim Construction (jeu de taquin for $\eps$-paths). \epspathjdt
Let $\kappa,\\,\nu$ be dominant integral weights for~$\gl_n$, \ $\pi'$ a
$\kappa$-dominant $\eps$-path of length~$l$ with $\pi'(1)=\\-\kappa$, and $p$
a $\\$-dominant $\eps$-path of length~$k$ with $p(1)=\nu-\\$. We construct a
dominant integral weight $\mu$, a $\kappa$-dominant $\eps$-path~$\pi$ of
length~$k$ with $\pi(1)=\mu-\kappa$, and a $\mu$-dominant $\eps$-path~$p'$ of
length~$l$ with $p'(1)=\nu-\mu$ in the following steps.
\+ Set $\li(h0,0..0,l-1)$ according to the sequence of segments of~$\pi'$, and
   $\li(v0,l..k-1,l)$ according to the sequence of segments of~$p$;
\+ Set $\\^{[0,j]}:=\kappa+\sum_{j'<j}h_{0,j'}$ for $0\leq j\leq l$, and
   $\\^{[i,l]}:=\\+\sum_{i'<i}v_{i',l}$ for $0\leq i\leq k$;
\+ Determine the values $h_{i,j}$ for $0<i\leq k$ and $l>j\geq 0$, as well as
   $v_{i,j}$ for $0\leq i<k$ and $l>j\geq 0$ using rule~\epspathrule, setting
   $\\^{[i,j+1]}:=\\^{[i,j]}+v_{i,j}=\\^{[i+1,j+1]}-h_{i+1,j}$ after
   each application of the rule;
\+ Return $\pi=\pi_{v_{0,0}}*\cdots*\pi_{v_{k-1,0}}$ and
   $p'=\pi_{h_{k,0}}*\cdots*\pi_{h_{k,l-1}}$.

Note that the relations between the parameters of the construction allow all
of them to be deduced if $\kappa$,~$\pi'$, and~$p$ are given; we shall
therefore consider the construction to be parametrised by $(\kappa,\pi',p)$,
and to return the pair~$(\pi,p')$.
The following theorem is obvious, both from the symmetry of the construction,
and from the fact that that construction is just a reformulation of jeu de
taquin.

\proclaim Theorem (symmetry of jeu de taquin for $\eps$-paths). \epsinvthm
The construction~\epspathjdt\ is its own inverse: if when applied to
$(\kappa,\pi',p)$ it returns $(\pi,p')$, then applied to $(\kappa,\pi,p')$ it
will return $(\pi',p)$. Moreover, it is symmetric with respect to dualisation
of paths: when applied to $(\nu,p^*,\pi'^*)$ it will return $(p'^*,\pi^*)$.
\QED

Despite its somewhat technical formulation, the following lemma is just an
expression of the trivial fact that jeu de taquin consists of consecutive
application of slides: performing inward slides according to a path $\pi'_2$
followed by performing inward slides according to $\pi'_1$ amounts to
performing inward slides according to the concatenation $\pi'_1*\pi'_2$.

\proclaim Lemma. \epsconcatlemma
Let construction~\epspathjdt\ be applicable to $(\kappa,\pi',p)$. If
$\pi'$ is of the form~$\pi'_1*\pi'_2$, then the construction is applicable
to $(\kappa+\pi'_1(1),\pi'_2,p)$, and calling the result of this application
$(q,p'_2)$, it is also applicable to~$(\kappa,\pi'_1,q)$; calling the result
of this second application $(\pi,p'_1)$, the result of applying the
construction to $(\kappa,\pi',p)$ will be $(\pi,p'_1*p'_2)$. A similar
composition formula holds if $p$ is of the form~$p_1*p_2$.
\QED

The following theorem establishes the fundamental link between jeu de taquin
and Littelmans's root operators $e_\alpha$~and~$f_\alpha$. It is not an
entirely new result: the fact that the definition of
$e_\alpha$~and~$f_\alpha$ corresponds to jeu de taquin on tableaux of two rows
is well known to experts; a discussion of this relation including a proof of
a statement equivalent to the theorem can be found in in~\ref{van Leeuwen
domino tableaux, \Sec3.1}. We shall give another proof here that is
formulated in terms of paths, so that generalisation to other types will be
straightforward.

\proclaim Theorem. \epsrootopthm
In the situation of construction~\epspathjdt\ the path~$\pi$ can be obtained
from~$p$ by application of a sequence of operators~$e_i$, and similarly the
path~$p'$ can be obtained from~$\pi'$ by application of a sequence of
operators~$f_i$. In particular, if $\kappa=0$, one has $p\in B_\pi$ and $p'\in
B_{\pi'}$.

\proof 
By symmetry (theorem~\epsinvthm) it suffices to prove the first statement
(about $p$~and~$\pi$). By lemma~\epsconcatlemma, it will suffice to prove the
case where $\pi'$ has length~$1$, which we therefore assume henceforth. In
order to proceed by induction on the length of~$p$, it is necessary to
strengthen the statement being proved as follows: there exists a sequence of
indices $\li(i1..n)$ (with $n\geq0$), and a sequence of paths
$p=p_n,\li(pn-1..0)=\pi$, such that for $j=n,\ldots,1$, one has
$p_{j-1}=e_{i_j}(p_j)$ and $\mm<\kappa+p_j,\alpha_{i_j}>=-1$ (which shows that
$p_j$ is \emph{not} $\kappa$-dominant for $j>0$). If $p$ is of length~$0$ we
take $n=0$ and there is nothing to prove; assume therefore that $p$ has
positive length. Let $v=\\^{[1,1]}-\\^{[0,1]}$ in construction~\epspathjdt, so
that we can write $p=\pi_v*q$; similarly put $v'=\\^{[1,0]}-\\^{[0,0]}$ and
$\pi=\pi_{v'}*\rho$. With $\kappa'=\\^{[1,0]}$ we consider the construction
applied to $(\kappa',\pi_{h_{1,0}},q)$, which by lemma~\epsconcatlemma\
returns~$(\rho,p')$. By the induction hypothesis there exist indices
$\li(i1..m)$ and paths $q=\li(qm..0)=\rho$ with $q_{j-1}=e_{i_j}(q_j)$ and
$\mm<\kappa'+q_j,\alpha_{i_j}>=-1$ for $0<j\leq m$. For $j\leq m$ we put
$p_j=\pi_{v'}*q_j$ (so that in particular $p_0=\pi$). Then for $0<j\leq m$ one
has $\mm<\kappa+p_j,\alpha_{i_j}> =\mm<\kappa'+q_j,\alpha_{i_j}>=-1$, since
the path $\pi_{v'}$ is $\kappa$-dominant with $\pi_{v'}(1)=v'=\kappa'-\kappa$.
We see moreover that the minimum taken in the first expression is attained
only in the second part of the concatentation $p_j=\pi_{v'}*q_j$; from the
definition of~$e_i$ we therefore have
$e_i(p_j)=\pi_{v'}*e_j(q_j)=\pi_{v'}*q_{j-1}=p_{j-1}$. Now if $v'=v$, we have
$p=\pi_v*q=\pi_{v'}*q_m=p_m$ so that we take $n=m$ and we are done. Otherwise
we are in the exceptional case of rule~\epspathrule\ for $(i,j)=(0,0)$, so
that $\pi'=\pi_{v'}=\pi_{\eps_r}$, \ $\pi_v=\pi_{\eps_{r+1}}$, and
$\<\kappa,\alpha_r\ch>=\<\\^{[1,1]},\alpha_r\ch>=0$ for some~$r$. Since the
path~$q$ is $\\^{[1,1]}$-dominant, this implies $\<q(t),\alpha_r\ch>\geq0$ for
all~$t$, so that $\mm<\kappa+p,\alpha_r>=-1$, which minimum is first attained
at the point of concatenation of $p=\pi_v*q$; consequently, we have by the
definition of~$e_r$ that $e_r(p)=\pi_{\eps_r}*q=\pi_{v'}*q_m=p_m$. In this
case we therefore put $n=m+1$ and $i_n=r$, and we have established all that
needs to be proved.
\QED

\newsection Jeu de taquin for other types of groups.

Now the stage has been set in type~$\Anm$, we may consider possible
generalisations to other types of groups. While the traditional planar form of
jeu de taquin does not seem to be easily generalised, the situation is quite
different for the formulation in terms of paths, since there are only a few
points in the discussion above that are specific for type~$\Anm$, and need
replacement for other types. Firstly, one needs a replacement for the set
$\setof\pi_{\eps_i}:i=1,\ldots,n\endset$ of elementary path segments, and
hence for the class of $\eps$-paths; secondly, rule~\epspathrule\ will need to
be adapted to this new class of paths. Once this is done, a counterpart of the
construction~\epspathjdt\ can be defined with only the most obvious
adaptations. Provided the replacement for rule~\epspathrule\ preserves its
symmetry, the analogue of theorem~\epsinvthm\ will be valid, with an equally
simple proof; the analogue of lemma~\epsconcatlemma\ remains a triviality.
Having succeeded so far, we shall have a involutive construction that operates
on pairs~$(p,\pi')$ of paths; then in order that we can use this construction
to define, for any paths $\pi,\pi'\in\Pdom$ (in the chosen class) with
$\pi(1)=\mu$ and $\pi'(1)=\\$, a bijective correspondence between
$\\$-dominant paths in~$B_\pi$ and $\mu$-dominant paths in~$B_{\pi'}$, it is
essential that the analogue of theorem~\epsrootopthm\ holds. Most of its proof
will remain valid without modification, but the final argument involving a
single configuration governed by (an analogue of) rule~\epspathrule\ needs to
be verified. Each time we establish these points, we obtain a combinatorial
analogue of jeu de taquin that shares two of its most fundamental properties:
symmetry (theorem~\epsinvthm) and confluence, i.e., the fact that, for
$\kappa=0$, the correspondence $p\to\pi$ is independent of the choice
of~$\pi'\in\Pdom$ (this will be a consequence of the analogue of
theorem~\epsrootopthm\ and the fact that from any path~$p$ at most one
path~$\pi\in\Pdom$ can be obtained by applications of root
operators~$e_\alpha$). The combinatorial constructions that we shall find have
a common generalisation to arbitrary piecewise linear paths, and maybe even to
continuous paths; however, in this generality the combinatorial nature of the
construction will be lost.

\subsection Minuscule representations and $m$-paths.

Let~$W$ be the Weyl group of~$\g$. A non-trivial irreducible representation
of~$\g$ is called \newterm{minuscule} if its set of weights forms a single
$W$-orbit; these weights are called minuscule weights. The following
representations are minuscule: all fundamental representations in type~$A_n$,
the natural (defining) representation in types $C_n$~and~$D_n$, the spin
representation in type~$B_n$, the half-spin representations in type~$D_n$,
the two \hbox{$27$-}dimensional representations in type~$E_6$, and the
\hbox{$56$-}dimensional representation in type~$E_7$; there are no minuscule
representations in types $G_2$,~$F_4$ and~$E_8$, since, as the weight lattice
coincides with the root lattice in these types, all representations contain
the weight~$0$. For any minuscule weight~$m$ and any root~$\alpha$ one has
$\<m,\alpha\ch>\in\{-1,0,1\}$, since otherwise $m+\Z\alpha$ would intersect
the weight system in more than two points. Therefore one has
$B_{\pi_\\}=\setof\pi_m:m\in W\\\endset$ for any dominant minuscule
weight~$\\$. This makes the class of paths obtained by concatenation of
segments~$\pi_m$ for $m$~minuscule a good candidate to replace the class
of~$\eps$-paths. We shall call any concatenation of~$l$ segments of the
form~$\pi_m$, with $m$ minuscule, an $m$-path (pun not intended) of
length~$l$.

In order to formulate an analogue of rule~\epspathrule\ for $m$-paths, we are
led to consider the following situation. Let $\kappa$,~$\\$ and~$\mu$ be
dominant integral weights such that $\pi_{\\-\kappa}$ and $\pi_{\nu-\\}$ are
$m$-paths of length~$1$; the question is to find a dominant weight~$\mu$ such
that $\pi_{\mu-\kappa}$ can be obtained from~$\pi_{\nu-\\}$ by a series of
applications of operators~$e_\alpha$ with $\<\kappa,\alpha\ch>=0$, and such
that the argument~$\pi_{v_i}$ to which the operator is applied satisfies
$\<v_i,\alpha\ch>=-1$ (there is a similar condition for the transformation
$\pi_{\\-\kappa}\to\pi_{\nu-\mu}$, which involves operators~$f_\alpha$). The
main difference with the situation for $\eps$-paths is that, whereas in that
case at most one application of $e_r$ suffices (which transforms
$\pi_{\nu-\\}=\pi_{\eps_{r+1}}$ into $\pi_{\mu-\kappa}=\pi_{\eps_r}$), a
series of applications may be needed for $m$-paths. This phenomeneon already
occurs in type~$\Anm$: if one takes $\kappa=\nu=0$, and $\\=\omega_i$, so that
$\\-\kappa=\omega_i=\eps_{\{1,\ldots,i\}}$, and
$\nu-\\=-\omega_i=\eps_{\{i+1,\ldots,n\}}$, then the only possibility is to
have $\mu=\omega_{n-i}$, so that
$\mu-\kappa=\omega_{n-i}=\eps_{\{1,\ldots,n-i\}}$ and
$\nu-\mu=-\omega_{n-i}=\eps_{\{n-i+1,\ldots,n\}}$; the transformation of
$\pi_{\eps_{\{i+1,\ldots,n\}}}$ into~$\pi_{\eps_{\{1,\ldots,n-i\}}}$ requires
a total of $i(n-i)$ applications of operators~$\eps_\alpha$ (some operators
may be applied more than once, but never twice in succession).

We see in this example that the seqence of operators applied may not be unique
(unlike in the proof of theorem~\epsrootopthm), but the final result is. In
fact it is not difficult to see that this is true in general. Let $S=\setof
i:\<\kappa,\alpha_i\ch>=\<\nu,\alpha_i\ch>=0\endset$, and put $v_0=\nu-\\$,
$h_0=\\-\kappa$; these are the initial candidates for
$\mu-\kappa$~and~$\nu-\mu$ (the sum of these candidates will always
be~$\nu-\kappa$). In order that $\mu$ be dominant, it is necessary that
$\<\mu-\kappa,\alpha_i\ch>=\<\mu-\nu,\alpha_i\ch>\geq0$ for all $i\in S$.
Therefore, while there exists for the current candidates $v_j$~and~$h_j$ for
$\mu-\kappa$~and~$\nu-\mu$ an $i\in S$ with
$\<v_j,\alpha_i\ch>=\<-h_j,\alpha_i\ch>=-1$ we choose such an~$i$ and replace
the candidates by $v_{j+1}=s_{\alpha_i}(v_j)=v_j+\alpha_i$ and
$h_{j+1}=s_{\alpha_i}(h_j)=h_j-\alpha_i$. After a finite number of steps this
process terminates, and we set $\mu=\kappa+v_l=\nu-h_l$ for the final values
$v_l,h_l$. Writing $W_{\kappa,\nu}$ for the subgroup of~$W$ stabilising
$\kappa$~and~$\nu$ (it is generated by $\setof s_{\alpha_i}:i\in S\endset$),
and $\dom_{W_{\kappa,\nu}}$ for the map that sends any weight to the
$W_{\kappa,\nu}$-dominant representative of its $W_{\kappa,\nu}$-orbit, we
clearly have $\mu-\kappa=\dom_{W_{\kappa,\nu}}(\nu-\\)$
and~$\mu-\nu=\dom_{W_{\kappa,\nu}}(\kappa-\\)$, which shows that these values
are independent of the choices made of the indices~$i$. We have achieved
$\<\mu,\alpha_i\ch>\geq0$ for all $i\in S$; to prove that $\mu$ is dominant it
suffices to establish the same for $i\notin S$. For such~$i$ we have
$\<\kappa,\alpha_i\ch>\geq1$ or~$\<\nu,\alpha_i\ch>\geq1$ (possible both);
since $\<\mu-\kappa,\alpha_i\ch>$ and~$\<\nu-\mu,\alpha_i\ch>$ lie in
$\{-1,0,1\}$, either of these inequalities implies $\<\mu,\alpha_i\ch>\geq0$.
From this description we see that in fact $\mu=\dom_W(\kappa+\nu-\\)$. We can
therefore formulate a generalisation of rule~\epspathrule\ simply as follows.

\proclaim Rule. \mpathrule
$\\^{[i+1,j]}=\dom_W(\\^{[i,j]}+\\^{[i+1,j+1]}-\\^{[i,j+1]})$.

\proclaim Lemma. \mpathsym
For fixed values of $\\^{[i,j]}$ and~$\\^{[i+1,j+1]}$, the correspondence
between $\\^{[i,j+1]}$ and~$\\^{[i+1,j]}$ determined by rule~\mpathrule\ is
symmetrical. Moreover the rule is symmetrical in $\\^{[i,j]}$
and~$\\^{[i+1,j+1]}$. 

\proof
From the considerations above it follows that $\mu=w(\kappa+\nu-\\)$ for some
$w\in W$ that fixes $\kappa$~and~$\nu$; this implies
$\\=w\inv(\kappa+\nu-\mu)$, and since $\\$ is dominant, this establishes the
first symmetry. The second symmetry is obvious.
\QED

As the path segments $h_{i,j}$ and~$v_{i,j}$ are absent from the formulation
of the rule~\mpathrule, we can formulate a construction that is in the spirit
of the original formulation of jeu de taquin in term of chains of partitions,
in that only a doubly indexed family of partitions is considered. It should be
noted however that paths were used to find rule~\mpathrule, and they will play
a r\^ole in proofs concerning the construction as well.

\proclaim Construction (jeu de taquin for $m$-paths). \mpathjdt
Let $\kappa,\\,\nu$ be dominant integral weights for~$\g$, \ $\pi'$ a
$\kappa$-dominant $m$-path of length~$l$ with $\pi'(1)=\\-\kappa$, and $p$ a
$\\$-dominant $m$-path of length~$k$ with $p(1)=\nu-\\$; we assume for each of
$\pi'$~and~$p$ that their segments are traversed at equal speeds. We construct
a dominant integral weight $\mu$, a $\kappa$-dominant $m$-path~$\pi$ of
length~$k$ with $\pi(1)=\mu-\kappa$, and a $\mu$-dominant $m$-path~$p'$ of
length~$l$ with $p'(1)=\nu-\mu$ in the following steps.
\+ Set $\\^{[0,j]}:=\kappa+\pi'(j/l)$ for $0\leq j\leq l$, and
   $\\^{[i,l]}:=\\+p(i/k)$ for $0\leq i\leq k$;
\+ Determine the values $\\^{[i,j]}$ for $0<i\leq k$ and $l>j\geq 0$ using
   rule~\mpathrule;
\+ Return $\pi=\pi_{v_1}*\cdots*\pi_{v_k}$ and
   $p'=\pi_{h_1}*\cdots*\pi_{h_l}$, where $v_i=\\^{[i,0]}-\\^{[i-1,0]}$ and
   $h_j=\\^{[k,j]}-\\^{[k,j-1]}$. 

\proclaim Theorem (symmetry of jeu de taquin for $m$-paths). \minvthm
The construction~\mpathjdt\ is its own inverse: if when applied to
$(\kappa,\pi',p)$ it returns $(\pi,p')$, then applied to $(\kappa,\pi,p')$ it
will return $(\pi',p)$. Moreover, it is symmetric with respect to dualisation
of paths: when applied to $(\nu,p^*,\pi'^*)$ it will return $(p'^*,\pi^*)$.

\proof
This is immediate from lemma \mpathsym.
\QED

\proclaim Lemma. \mconcatlemma
Lemma \epsconcatlemma\ remains valid when construction~\epspathjdt\ is
replaced by construction~\mpathjdt.
\QED

\proclaim Theorem. \mrootopthm
In the situation of construction~\mpathjdt\ the path~$\pi$ can be obtained
from~$p$ by application of a sequence of operators~$e_i$, and similarly the
path~$p'$ can be obtained from~$\pi'$ by application of a sequence of
operators~$f_i$. In particular, if $\kappa=0$, one has $p\in B_\pi$ and $p'\in
B_{\pi'}$.

\proof
The proof of theorem~\epsrootopthm\ can be followed literally, with the
obvious replacement of references by their counterparts for $m$-paths, up to
and including the proof that $e_i(p_j)=p_{j-1}$ for $0<j\leq m$; after that we
continue as follows. Let $v=\li(v0..l)=v'$ be the sequence of vectors in the
discussion preceding the statement of rule~\mpathrule; put $n=m+l$ and
$p_{n-i}=\pi_{v_i}*q$ for $i=0,\ldots,l$ (this agrees with the previous
definition of~$p_m$, and we have $p_n=p$). It was established there that for
all $i<l$ there exists a simple root~$\alpha$ such that
$\<\kappa,\alpha\ch>=\<\\^{[1,1]},\alpha\ch>=0$, \ $\<v_i,\alpha\ch>=-1$, and
$v_{i+1}=s_\alpha(v_i)$, so that $\pi_{v_{i+1}}=e_\alpha(\pi_{v_i})$. Since
the path~$q$ is $\\^{[1,1]}$-dominant we have $\<q(t),\alpha\ch>\geq0$ for
all~$t$, so that $\mm<\kappa+p_{n-i},\alpha>=-1$, and
$e_\alpha(p_{n-i})=e_\alpha(\pi_{v_i}*q)=\pi_{v_{i+1}}*q=p_{n-i-1}$; this
establishes all that needs to be proved.
\QED

\subsection Quasi-minuscule weights and $\psi$-paths.

We can extend the class of paths for which our construction works beyond that
of $m$-paths by allowing path segments that correspond to the weights of
representations slightly larger than the minuscule ones, which will in
particular allow us to treat paths for groups of the types $G_2$,~$F_4$,
and~$E_8$ that do not possess minuscule representations. As we shall see, the
extra freedom will lead to a considerable increase in the number of situations
that need to be treated.

An irreducible representation is called quasi-minuscule if its set of weights
consists of two $W$-orbits, one of which is~$\{0\}$; the weights in the other
orbit are called quasi-minuscule weights. The orbit of quasi-minuscule weights
is contained in the root lattice, and its dominant representative is a minimal
non-zero element of the intersection of the dominant chamber with the root
lattice; in particular quasi-minuscule weights are roots. One checks easily
that for every simple type there is a unique quasi-minuscule representation:
this is the adjoint representation for the simply laced types $A_n$,~$D_n$
and~$E_n$, and the representation whose non-zero weights are the short roots
for the other types $B_n$,~$C_n$, $F_4$, and~$G_2$ (for type~$B_n$ this is the
natural representation). For similar reasons as mentioned for minuscule
weights, one has for any root~$\alpha$ and any quasi-minuscule
weight~$m\notin\{-\alpha,\alpha\}$ that $\<m,\alpha\ch>\in\{-1,0,1\}$. It
follows that if $\\$ is a dominant quasi-minuscule weight, then the only paths
in~$B_{\pi_\\}$ that are not of the form~$\pi_m$ for $m\in W\\$ are those of
the form
$e_\alpha(\pi_{-\alpha})=f_\alpha(\pi_\alpha)=\pi_{-\alpha/2}*\pi_{\alpha/2}$
for the simple roots~$\alpha$ occurring in~$W\\$; we shall denote such a path
by $\psi_\alpha$. We define a $\psi$-path of length~$l$ to be a concatenation
of $l$~segments that occur in the union of the sets $B_{\pi_\\}$ for the
dominant weights~$\\$ that are either minuscule or quasi-minuscule.

Now we consider the question of extending rule~\mpathrule\ to deal with any
pair of $\psi$-paths of length~$1$. As before we consider dominant integral
weights $\kappa$,~$\\$, $\nu$, and we put $S=\setof
i:\<\kappa,\alpha_i\ch>=\<\nu,\alpha_i\ch>=0\endset$. Since the paths involved
are no longer necessarily linear, it does not suffice to consider just the
differences $\\-\kappa$ and $\nu-\\$; therefore let $p$~and~$q$ be
$\psi$-paths of length~$1$ such that $p(1)=\nu-\\$ and $q(1)=\\-\kappa$. Our
goal is to find paths $p'$~and~$q'$, obtained from $p$~and~$q$ respectively by
applications of operators $e_\alpha$ and~$f_\alpha$, such that
$\mu=\kappa+p'(1)=\nu-q'(1)$ is dominant, and moreover $p'$ is
$\kappa$-dominant and $q'$ is $\mu$-dominant (this is an extra condition only
when $p'$ or $q'$ is of the form~$\psi_\alpha$).

We consider first the case that both $p$~and~$q$ are linear (i.e., not of the
form~$\psi_\alpha$), which includes the case of $m$-paths treated above. Like
in that case we perform an iteration, but now on a pair of paths, which we
initialise by $p_0=p,q_0=q$. The iteration is the following one:
\item{$(*)$} As long as there exists for the current pair $p_j,q_j$
             some~$i\in{S}$ with
             $\<p_j(1),\alpha_i\ch>=\<-q_j(1),\alpha_i\ch>=-1$, we choose such
             an~$i$ and put $p_{j+1}=e_{\alpha_i}(p_j)$ and
             $q_{j+1}=f_{\alpha_i}(q_j)$.
\enditem
All the paths so obtained are linear, since we could only have
$p_{j+1}=\psi_\alpha$ if $\alpha_i=\alpha$ and~$p_j=\pi_{-\alpha}$, which
would violate $\<p_j(1),\alpha_i\ch>=-1$. It follows also that this iteration
cannot make a transition from negative to positive roots: if any $p_j$ is of
the form~$\pi_\beta$ for a negative root~$\beta$, then the same is true for
all~$p_j$'s; a similar statement holds when $p_j=\pi_\beta$ for a positive
root~$\beta$, and also for the $q_j$'s in place of the~$p_j$'s.

If for the final paths $p_k,q_k$ obtained after the iteration, the weight
$\tilde\mu=\\+p_k(1)=\nu-q_k(1)$ is dominant, then we put $p'=p_k$ and
$q'=q_k$. Otherwise, let $i$ be such that $\<\tilde\mu,\alpha_i\ch><0$.
Suppose first that $i\notin S$; then since either $\<\kappa,\alpha_i\ch>>0$ or
$\<\\,\alpha_i\ch>>0$, we must have $p_k=\pi_{-\alpha_i}$ or
$q_k=\pi_{\alpha_i}$ (possibly both). We put $p'=p_{k+1}=e_{\alpha_i}(p_k)$
and $q'=q_{k+1}=f_{\alpha_i}(q_k)$; since $\mu=\\+p'(1)=\nu-q'(1)$ is equal to
$\kappa$~or~$\nu$, it is dominant, and one has $\<\mu,\alpha_i\ch>=1$, from
which it follows that $p'$ is $\kappa$-dominant and $q'$ is $\mu$-dominant.
Now suppose $i\in S$; since the iteration~$(*)$ has terminated, it must be
that $\<p_k(1),\alpha_i\ch>=-2$, so $p_k=\pi_{-\alpha_i}$ and
$q_k=\pi_{\alpha_i}$. We then put $p_{k+1}=q_{k+1}=\psi_{\alpha_i}$ and
$p_{k+2}=\pi_\alpha$, \ $q_{k+2}=\pi_{-\alpha}$ (so that
$p_{j+1}=e_{\alpha_i}(p_j)$ and $q_{j+1}=f_{\alpha_i}(q_j)$ for $j=k,k+1$),
after which we resume the iteration~$(*)$, and set $p'$~and~$q'$ respectively
to the final paths $p_l,q_l$ so obtained. From the fact that the iteration
cannot make a transition between negative and positive roots it follows that
this time $\mu=\\+p'(1)=\nu-q'(1)$ must be dominant.

Next we consider the case that $p=\psi_\alpha$ and $q=\psi_\beta$ for simple
roots $\alpha,\beta$. If $\alpha\neq\beta$ or if $\alpha=\beta$ and
$\<\\,\alpha\ch>>1$ then we put $p'=p$ and~$q'=q$, so that
$\mu=\kappa=\\=\nu$. If $\alpha=\beta$ and $\<\kappa,\alpha\ch>=1$ we put
$p_1=e_\alpha(p)=\pi_\alpha$ and $q_1=f_\alpha(q)=\pi_{-\alpha}$ and then
perform iteration~$(*)$. We set $p'$~and~$q'$ respectively to the final paths
$p_l,q_l$ obtained; as in the case above we see that $\mu=\\+p'(1)=\nu-q'(1)$
is dominant.

We are left with the possibility that exactly one of $p$~and~$q$ is linear. We
shall only treat the case that this is~$q$, as the other case is symmetric
(by interchange of $\kappa$~and~$\nu$ and dualisation of the paths); let
$p=\psi_\alpha$. If $\<\kappa,\alpha\ch>>0$, then we put $p'=p$ and~$q'=q$, so
that $\mu=\kappa$ is dominant and $p'$ is $\kappa$-dominant; we assume
henceforth that $\<\kappa,\alpha\ch>=0$. If $q=\pi_\alpha$ then we put
$p'=e_\alpha(p)=\pi_\alpha$ and $q'=f_\alpha(q)=\psi_\alpha$. Otherwise we put
$p_1=e_\alpha(p)=\pi_\alpha$ and $q_1=f_\alpha(q)$, after which perform
iteration~$(*)$, calling the final paths obtained $p_k,q_k$. As in the case of
linear $p$~and~$q$ it is possible that for $\tilde\mu=\\+p_k(1)=\nu-q_k(1)$
there is some~$i$ for which $\<\tilde\mu,\alpha_i\ch><0$, but this time only
for $i\notin S$ and $q_k=\pi_{\alpha_i}$, since $p_k\neq\pi_{-\alpha_i}$. If
this is the case we put $p'=p_{k+1}=e_{\alpha_i}(p_k)$ and
$q'=q_{k+1}=f_{\alpha_i}(q_k)=\psi_{\alpha_i}$, and otherwise ($\tilde\mu$ is
dominant) we put $p'=p_k$ and $q'=q_k$; both cases are just like the
corresponding ones for linear $p$~and~$q$.

This concludes the description of the determination of $p'$ and~$q'$. We shall
now try to formulate the result as concisely as possible. To this end we shall
use the fact that $\mu$ determines either of $p'$ and~$q'$ if the path in
question is linear, i.e., if $\mu$ differs from $\kappa$ respectively
from~$\nu$; if not, then the path is of the form~$\psi_\alpha$, and it
suffices to specify in addition to~$\mu$ the simple root~$\alpha$. We also
simplify the formulation by using the fact that if $\\$ equals either $\kappa$
or~$\nu$, then the other one can be expressed as $\kappa+\nu-\\$. Since like
before the rule stated will be used in a larger construction, we give the
weights and path segments in the construction as elements of doubly indexed
families. We leave it to the reader to verify that the results computed above
satisfy the description below.

\proclaim Rule. \psipathrule
Let $\kappa=\\^{[i,j]}$, \ $\\=\\^{[i,j+1]}$, \ $\nu=\\^{[i+1,j+1]}$, \
$p=v_{i,j+1}$, and $q=h_{i,j}$; the weight $\mu=\\^{[i+1,j]}$ and the paths
$p'=v_{i,j}$ and $q'=h_{i+1,j}$ are determined according to the following
cases.
\item{(a)} If $p$ and $q$ are linear, then $\mu=\dom_W(\kappa+\nu-\\)$; in case
          $\mu$ equals $\kappa$ or~$\nu$, the corresponding path
          is equal to~$\psi_\alpha$, where
          $\alpha=\mu-\dom_{W_{\kappa,\nu}}(\kappa+\nu-\\)$.
\item{(b)} If $\<\\,\alpha\ch>=1$ and $\psi_\alpha\in\{p,q\}$ for some simple
          root~$\alpha$, and either $p=q$ or $\<\kappa+\nu-\\,\alpha\ch>=0$,
          then $\mu=\dom_W(\kappa+\nu-\\+\alpha)$; in case $\mu$ equals
          $\kappa$ or~$\nu$, the corresponding path is equal
          to~$\psi_{\alpha'}$, where
          $\alpha'=\mu-\dom_{W_{\kappa,\nu}}(\kappa+\nu-\\+\alpha)$.
\item{(c)} If $\psi_\alpha\in\{p,q\}$ for some simple root~$\alpha$, with
          $\<\\,\alpha\ch>=2$ and $\<\kappa+\nu-\\,\alpha\ch>=0$, then
          $p'=q$, \ $q'=p$, and~$\mu=\\$.
\item{(d)} If either $\{p,q\}=\{\psi_\alpha,\psi_\beta\}$ for simple roots
          $\alpha\neq\beta$, or $\psi_\alpha\in\{p,q\}$ for some simple
          root~$\alpha$ and $\<\kappa+\nu-\\,\alpha\ch>>0$, then $p'=p$, \
          $q'=q$, and~$\mu=\kappa+\nu-\\$.

\proclaim Lemma. \psipathsym
For fixed values of $\\^{[i,j]}$ and~$\\^{[i+1,j+1]}$, the correspondence
determined by rule~\psipathrule\ between $\\^{[i,j+1]}$ and~$\\^{[i+1,j]}$,
and between $(h_{i,j},v_{i,j+1})$ and $(v_{i,j},h_{i+1,j})$, is symmetrical.

\proof
This follows from a careful analysis of the different cases that can arise. In
cases (c)~and~(d) of rule~\psipathrule, replacement of~$\\$ by the indicated
value of~$\mu$ leads to the same case, and gives back the original value
of~$\\$ for~$\mu$. We may therefore assume that one of cases (a)~and~(b)
applies. Define weights~$\mu_0,\mu_1,\mu_2,\mu_3$ by $\mu_0=\kappa+\nu-\\$, \
$\mu_1=\mu_0$ in case~(a) and $\mu_1=\mu_0+\alpha$ in case~(b), \
$\mu_2=\dom_{W_{\kappa,\nu}}(\mu_1)$, and $\mu_3=\mu$; replacing $\\$
by~$\mu$, call the corresponding weights $\\_0,\\_1,\\_2,\\_3$. One then
proves successively that $\\_i=\kappa+\nu-\mu_{3-i}$ for $i=0,1,2,3$ in a
straightforward manner in all the cases, using the details that were given
before the statement of rule~\psipathrule.
\QED

\proclaim Construction (jeu de taquin for $\psi$-paths). \psipathjdt
Let $\kappa,\\,\nu$ be dominant integral weights for~$\g$, \ $\pi'$ a
$\kappa$-dominant $\psi$-path of length~$l$ with $\pi'(1)=\\-\kappa$, and $p$
a $\\$-dominant $\psi$-path of length~$k$ with $p(1)=\nu-\\$. We construct a
dominant integral weight $\mu$, a $\kappa$-dominant $\psi$-path~$\pi$ of
length~$k$ with $\pi(1)=\mu-\kappa$, and a $\mu$-dominant $\psi$-path~$p'$ of
length~$l$ with $p'(1)=\nu-\mu$, in the following steps.
\+ Let $\pi'=h_{0,0}*\cdots*h_{0,l-1}$ and $p=v_{0,l}*\cdots*v_{k-1,l}$, where
   the $h_{i,j}$ and $v_{i,j}$ are $\psi$-paths of length~$1$;
\+ Set $\\^{[0,j]}:=\kappa+\sum_{j'<j}h_{0,j'}(1)$ for $0\leq j\leq l$, and
   $\\^{[i,l]}:=\\+\sum_{i'<i}v_{i',l}(1)$ for $0\leq i\leq k$;
\+ Determine the weights~$\\^{[i+1,j]}$ and the paths $h_{i+1,j}$
   and~$v_{i,j}$ for $0\leq i<k$ and $l>j\geq 0$, using rule~\psipathrule;
\+ Return $\pi=v_{0,0}*\cdots*v_{k-1,0}$ and $p'=h_{k,0}*\cdots*h_{k,l-1}$.

\proclaim Theorem (symmetry of jeu de taquin for $\psi$-paths). \psiinvthm
The construction~\psipathjdt\ is its own inverse: if when applied to
$(\kappa,\pi',p)$ it returns $(\pi,p')$, then applied to $(\kappa,\pi,p')$ it
will return $(\pi',p)$. Moreover, it is symmetric with respect to dualisation
of paths: when applied to $(\nu,p^*,\pi'^*)$ it will return $(p'^*,\pi^*)$.

\proof
This is immediate from lemma \psipathsym.
\QED

\proclaim Lemma. \psiconcatlemma
Lemma \epsconcatlemma\ remains valid when construction~\epspathjdt\ is
replaced by construction~\psipathjdt.
\QED

\proclaim Theorem. \psirootopthm
In the situation of construction~\psipathjdt\ the path~$\pi$ can be obtained
from~$p$ by application of a sequence of operators~$e_i$, and similarly the
path~$p'$ can be obtained from~$\pi'$ by application of a sequence of
operators~$f_i$. In particular, if $\kappa=0$, one has $p\in B_\pi$ and $p'\in
B_{\pi'}$.

\proof
By symmetry (theorem~\psiinvthm) it suffices to prove the first statement
(about $p$~and~$\pi$). By lemma~\psiconcatlemma, it will suffice to prove the
case where $\pi'$ has length~$1$, which we therefore assume henceforth. In
order to proceed by induction on the length of~$p$, it is necessary to
strengthen the statement being proved as follows. There exists a sequence of
indices $\li(i1..n)$ (with $n\geq0$) and a sequence of paths
$p=p_n,\li(pn-1..0)=\pi$, such that for $j=n,\ldots,1$, one has
$e_{i_j}(p_j)=p_{j-1}$, and moreover $\mm<\kappa+p_j,\alpha_{i_j}><0$ except
when $\pi'=\psi_\alpha$ for some simple root~$\alpha$ and $j=n$, in which case
one has $\alpha_{i_n}=\alpha$ and $\mm<\kappa+p_j,\alpha>=0$. To this we add
one more detail: if $\pi'=\psi_\alpha$ and $\mm<\kappa+p,\alpha>=0$, then
$n>0$.

If $p$ is of length~$0$ we take $n=0$ and there is nothing to prove; assume
therefore that $p$ has positive length. Let $v=v_{0,1}$ in
construction~\epspathjdt, so that we can write $p=v*q$; similarly put
$v'=v_{0,0}$ and $\pi=v'*\rho$. Put $\kappa'=\\^{[1,0]}$ and $\\'=\\^{[1,1]}$;
we consider the construction applied to $(\kappa',h_{1,0},q)$, which by
lemma~\psiconcatlemma\ returns~$(\rho,p')$. By the induction hypothesis there
exist indices $\li(im..1)$ and paths $q=\li(qm..0)=\rho$ with
$q_{j-1}=e_{i_j}(q_j)$ for $j=m,\ldots,1$. Let $v=\li(v0..l)=v'$ be the
sequence of paths called $\li(p0..l)$ in the discussion preceding the
statement of rule~\psipathrule; put $n=m+l$. It was established there that for
all $j<l$ there exists a simple root~$\alpha$ such that
$v_{j+1}=e_\alpha(v_j)$; let the index of this root be~$i_{n-j}$, thus
extending our sequence of indices to $\li(in..1)$. We shall say that we are in
the exceptional case if $m>0$, \ $l>0$, and $h_{1,0}=\psi_\alpha$ for some
simple root~$\alpha$; otherwise we are in the regular case. Define a sequence
of paths $p=\li(pn..0)=\pi$ as follows: set $p_j=v_{n-j}*q$ for $n\geq j>m$
and $p_j=v'*q_j$ for $m>j\geq0$; finally set $p_m=v'*q$ in the regular case,
and $p_m=v_{l-1}*q_{m-1}$ in the exceptional case.

We shall first show that the only possibility to have $f_{i_j}(v'*q_{j-1})\neq
v'*q_i$ for $0<j\leq m$ occurs for $j=m$ in the exceptional case, and that we
then have $f_{i_m}(v'*q_{m-1})=v_{l-1}*q_{m-1}$; this will establish
$e_{i_j}(p_j)=p_{j-1}$ for $j\leq m$. Putting $\alpha=\alpha_{i_j}$, the
operator~$f_\alpha$ will only apply to the left factor of $v'*q_{j-1}$ if
$$
  \mm<\kappa'+v'^*,\alpha>  <  \mm<\kappa'+q_{j-1},\alpha>. \label(\firstineq)
$$
Since $v'^*$ is $\kappa'$-dominant, the left hand side is non-negative, so
(\firstineq) can only hold if its right hand side, which equals
$\mm<\kappa'+q_j,\alpha>+1$ since $q_{j-1}=e_\alpha(q_j)$, is strictly
positive; by the induction hypothesis this only happens when
$h_{1,0}=\psi_\alpha$ and $j=m$, and the right hand side then equals~$1$.
Therefore the left hand side must be~$0$, which excludes case~(d) of
rule~\psipathrule, so that we have $l>0$ and are in the exceptional case. It
can be seen from rule~\psipathrule\ that $h_{1,0}=\psi_\alpha$ and $l>0$ imply
that $\alpha_{i_{m+1}}=\alpha$ and $\mm<\kappa+v_l,\alpha>=0$; therefore the
left hand side of~(\firstineq) is indeed~$0$ in this case and
$f_\alpha(v')=v_{l-1}$, so that we have $f_\alpha(v'*q_{m-1})=v_{l-1}*q_{m-1}$
as claimed.

We proceed to show similarly that the only possibility to have
$e_{i_{n-j}}(v_j*q)\neq v_{j+1}*q$ for $0\leq j<l$ occurs for $j=l-1$ in the
exceptional case, and that we then have
$e_{i_{m+1}}(v_{l-1}*q)=v_{l-1}*q_{m-1}$; this will establish
$e_{i_k}(p_k)=p_{k-1}$ for $k>m$. Putting $\alpha=\alpha_{i_{n-j}}$, the
operator~$e_\alpha$ will only apply to the right factor of $v_j*q$ if
$$
  \mm<\\'+v_j^*,\alpha>  >  \mm<\\'+q,\alpha>. \label(\secondineq)
$$
Since $q$ is $\\'$-dominant, the right hand side is non-negative, so
(\secondineq) can only hold if its left hand side is strictly positive, and in
particular $\<\\',\alpha\ch>>0$. Since we have $e_\alpha(v_j)=v_{j+1}$, it can
be seen from rule~\psipathrule\ that we must have $j=0$ or $j=l-1$; however if
$j=0\neq l-1$, we would be in case~(b) of that rule with $v_0=v=\psi_\alpha$,
and the left hand side of~(\secondineq) would be~$0$, which allows us to
conclude $j=l-1$. Now whichever of the cases (a),~(b), or~(c) gives
$v_l=e_\alpha(v_{l-1})$ with $\<\\',\alpha\ch>>0$, it also gives
$h_{1,0}=\psi_\alpha$, and makes the left hand side of~(\secondineq) equal
to~$1$. By the induction hypothesis (including the detail added) the right
hand side of~(\secondineq) will now be~$0$ if and only if $m>0$, which means
we are in the exceptional case; we then have moreover $\alpha_{i_m}=\alpha$,
so that indeed $e_\alpha(v_{l-1}*q)=v_{l-1}*e_\alpha(q)=v_{l-1}*q_{m-1}$, as
claimed.

It remains to establish the statements involving
$\mm<\kappa+p_j,\alpha_{i_j}>$ needed for the induction. If $0<j<m$, or if
$j=m$ in the regular case, one has $p_j=v'*q_j$; as $v'$ is $\kappa$-dominant
with $v'(1)=\kappa'-\kappa$ this implies
$\mm<\kappa+p_j,\alpha_{i_j}>=\mm<\kappa'+q_j,\alpha_{i_j}>$. Everything then
follows immediately from the corresponding part of the induction hypothesis
(if $l=0$ one uses $h_{1,0}=\pi'$). This covers all cases with $l=0$, so from
now on assume $l>0$. If $m<j<n$, or if $j=n$ and $\pi'$ is linear, then we
have $\mm<\\+v_{n-j},\alpha_{i_j}><0$ by the construction of the sequence
$\li(v0..l)$, and since $p_j=v_{n-j}*q$ this implies
$\mm<\\+p_j,\alpha_{i_j}><0$. If on the other hand $\pi'=\psi_\alpha$ (so that
$\kappa=\\$), then we see from cases (b)~and~(c) of rule~\psipathrule\ that
$\alpha_{i_n}=\alpha$ and $\mm<\kappa+v,\alpha>=0$, which implies
$\mm<\kappa+p,\alpha>=0$ since $p$ is $\\$-dominant. The only case left is
$j=m$ in the exceptional case; put $\alpha=\alpha_{i_{m+1}}=\alpha_{i_m}$, so
that $h_{1,0}=\psi_\alpha$. One can show $\mm<\kappa+p_m,\alpha>=-1$ in various
ways, as the minimum is attained at both sides of the concatenation
$p_m=v_{l-1}*q_{m-1}$. For instance, we have seen that
$\mm<\kappa+v_l,\alpha>=0$ in this case, which implies
$\mm<\kappa+v_{l-1},\alpha>=-1$ since $v_l=e_\alpha(v_{l-1})$. This completes
our proof.
\QED

\subsecno=-1
\newsection Generalisation of jeu de taquin to piecewise linear paths.

We shall now generalise the constructions considered so far to a much larger
class of paths than that of the $\psi$-paths, namely for the entire
class~$\Pi$ of piecewise linear paths in the space of rational weigths. The
rule that describes the construction in the elementary cases will become
simpler than rule~\psipathrule, and in fact resembles rule~\mpathrule, yet we
shall see that the global construction contains construction~\psipathjdt\ as a
special case. Given this circumstance, it may seem silly that we went through
all the complications of the preceding subsection. There is however an
important price that we pay for the simplicity and generality of the new
construction: it gives us no direct control over integrality, and therefore
does not allow a direct connection to be made with the root operators
$e_\alpha$ and $f_\alpha$.

It turns out that the simplest way to describe the jeu de taquin construction
for piecewise linear paths is not using doubly indexed families of paths, or
collections of ``horizontal'' and ``vertical'' path segments, but using
``2-dimensional'' paths, that is to say, piecewise linear maps
$f\:[0,1]\times[0,1]\to X_\Q$ (here piecewise linear means there is a finite
triangulation of $[0,1]\times[0,1]$ such that the restriction of~$f$ to each
of the triangles is linear). For these maps we do not require (as was done for
paths) that they must always ``start at~$0$'', but we shall require that their
image is contained in the dominant chamber. Then instead of conditions like
rule~\psipathrule, we shall impose the following somewhat curious functional
equation.

\proclaim Rule. \plpathrule
For every pair of intervals $[s_0,s_1],[t_0,t_1]\subset[0,1]$ such that $f$ is
linear on each of the line segments $\{s_0\}\times[t_0,t_1]$ and
$[s_0,s_1]\times\{t_1\}$, one has $f(s,t)=\dom_W\(f_0(s,t)\)$ for
$(s,t)\in[s_0,s_1]\times[t_0,t_1]$, where $f_0$ is the linear function given
by $f_0(s,t)=f(s_0,t)+f(s,t_1)-f(s_0,t_1)$.

If we prescribe~$f$ on each of the segments $\{s_0\}\times[t_0,t_1]$ and
$[s_0,s_1]\times\{t_1\}$ by functions that are linear and everywhere dominant,
then $f(s,t)=\dom_W\(f_0(s,t)\)$ (with $f_0$ as in the rule) defines an
extension of~$f$ to $[s_0,s_1]\times[t_0,t_1]$ that is piecewise linear and
everywhere dominant. In particular this extension determines piecewise linear
paths on the edges $[s_0,s_1]\times\{t_0\}$ and $\{s_1\}\times[t_0,t_1]$ of
the rectangle $[s_0,s_1]\times[t_0,t_1]$ opposite to those on which $f$ was
prescribed. We shall call this operation of extending~$f$ across a rectangle
$[s_0,s_1]\times[t_0,t_1]$ an elementary extension of~$f$.
%
We still need to show that the condition of rule~\plpathrule\ is satisfied for
any applicable subintervals of $[s_0,s_1]$ and $[t_0,t_1]$, so let
$[s_0',s_1']\subset[s_0,s_1]$ and $[t_0',t_1']\subset[t_0,t_1]$ be such that
$f$ is linear on $L_1=\{s_0'\}\times[t_0',t_1']$ and on
$L_2=[s_0',s_1']\times\{t_1'\}$. We first show that the weights
$f_0(s_0',t_0')$ and $f_0(s_1',t_1')$ are not separated by any wall, i.e.,
that there is no root~$\beta$ (positive or negative) for which the linear
functional $\phi(x,y)=\<f_0(x,y),\beta\ch>$ has $\phi(s_0',t_0')<0$ and
$\phi(s_1',t_1')>0$. If there were such a root~$\beta$, then
$\phi(s_0',t_1')\neq0$ would contradict the linearity of~$f$ either on~$L_1$
or on~$L_2$, whereas $\phi(s_0',t_1')=0$ would imply by linearity that
$\phi(s_0,t_0)<0$ and $\phi(s_1,t_1)>0$, contradicting the fact that both
$f_0(s_0,t_0)$ and $f_0(s_1,t_1)$ are dominant. Therefore, there exists a
$w\in W$ such that $f(s,t)=w(f_0(s,t))$ on $L_1\union L_2$. Being linear, $f_0$
satisfies $f_0(s,t)=f_0(s_0',t)+f_0(s,t_1')-f_0(s_0',t_1')$; hence the
validity of rule~\plpathrule\ is established by the following computation for
$(s,t)\in[s_0',s_1']\times[t_0',t_1']$:
$$ \eqalign
{ f(s,t)=\dom_W\(w(f_0(s,t))\)
 &=\dom_W\(w\(f_0(s_0',t)+f_0(s,t_1')-f_0(s_0',t_1')\)\) \cr
 &=\dom_W\(f(s_0',t)+f(s,t_1')-f(s_0',t_1')\). \cr
}
$$

Because of the way the rule is formulated, there is no need for a counterpart
of construction~\psipathjdt: a piecewise linear function~$f$ defined on
$[0,1]\times[0,1]$ that satisfies the rule must match any function constructed
by repeated elementary extensions from the restriction of~$f$ to the edges
$\{0\}\times[0,1]$ and $[0,1]\times\{1\}$ of the unit square. However, it is
not immediately obvious that repeated elementary extensions suffice to cover
all of the unit square. To see the difficulty, imagine that
\emph{every} elementary extension would result at each of the opposite edges
of the rectangle in a path consisting of two different linear parts; then
infinitely many elementary extensions could be applied, but they would fail to
define~$f$ beyond a certain subset with fractal boundary. We shall show that
this cannot happen; to do so we need to consider the directions of the
segments of the paths obtained by elementary extension. For a dominant
weight~$\\$ and weight~$\mu$ in its orbit~$W\\$, the set $\setof w\in W:
\mu=w(\\)\endset$ is a coset in $W/W_\\$, and it does not change when $\mu$ is
multiplied by a positive scalar. We define this coset to be the direction
of~$\pi_\mu$, or of any translate of a positive multiple of~$\pi_\mu$, and
endow $W/W_\\$ with the Bruhat order, and the associated length function~$l$.
Then the following lemma is an immediate consequence of the definition of
elementary extensions.

\proclaim Lemma. \dirlemma
Let $f$ satisfy rule~\plpathrule\ on $[s_0,s_1]\times[t_0,t_1]$ and be linear
on $\{s_0\}\times[t_0,t_1]$ and $[s_0,s_1]\times\{t_1\}$; let the direction of
the path defined by~$f$ along $[s_0,s_1]\times\{t_1\}$ be~$\tau$, and let 
the path defined by~$f$ along $[s_0,s_1]\times\{t_0\}$ be $\pi_0*\cdots*\pi_n$
where the $\pi_i$ are linear paths with differenct directions $\tau_i$. Then
$\tau\leq\tau_0<\cdots<\tau_n$, and consequently $n\leq l(\tau)$. Similar
statements hold for the other two edges.
\QED

\proclaim Theorem/construction (jeu de taquin for piecewise linear paths).
\plpathjdt
Let $\kappa,\\,\nu$ be dominant integral weights for~$\g$, \ $\pi'$ a
$\kappa$-dominant piecewise linear path with $\pi'(1)=\\-\kappa$, and $p$
a $\\$-dominant piecewise linear path with $p(1)=\nu-\\$. There is a unique
piecewise linear function $f\:[0,1]\times[0,1]\to X_\Q$ with
$f(0,t)=\kappa+\pi'(t)$ and $f(t,1)=\\+p(t)$ for $t\in[0,1]$ that satisfies
rule~\plpathrule. Putting $\mu=f(1,0)$, we may define a $\kappa$-dominant
piecewise linear path~$\pi$ with $\pi(1)=\mu-\kappa$ by
$\pi(t)=f(t,0)-\kappa$, and a $\mu$-dominant piecewise linear path~$p'$ with
$p'(1)=\nu-\mu$ by $p(t)=f(1,t)-\mu$.

\proof
We shall show that by repeatedly applying elementary extensions to~$f$ we
succeed after a finite number of step in finding an extension of $f$ to all of
$[0,1]\times[0,1]$, which is then automatically unique. By a trivial induction
on the number of linear segments from which $p$ is concatenated, we may reduce
to the case that $p$ is linear. We cannot continue with a similar induction on
the number of segments of~$\pi'$ however; instead we apply induction on the
length $l(\tau)$ of the direction~$\tau$ of the path~$p$. For $l(\tau)=0$,
which is equivalent to $p\in\Pdom$, the function~$f$ given by
$f(s,t)=\kappa+\pi'(t)+p(s)$ is everywhere dominant, and is therefore the
unique function satisfying the conditions in the theorem. Now suppose
$l(\tau)=l>0$. For each fixed value of~$l$ we apply induction on the number of
linear segments from which $\pi'$ is concatenated. If $\pi'$ is linear,
elementary extension suffices to define~$f$ uniquely on $[0,1]\times[0,1]$.
Otherwise we apply elementary extension to $p$ and the final linear segment
of~$\pi'$. Let the piecewise linear path obtained at the side opposite to~$p$
be $p_0*\cdots*p_n$; let the segment $p_i$ give the values of~$f$ on
$[s_i,s_{i+1}]\times\{t_1\}$ and have direcion~$\tau_i$ ($i=0,\ldots,n$).
Because of lemma~\dirlemma\ we have $l(\tau_0)\leq l$ and $l(\tau_i)<l$ for
$i>0$. In case $l(\tau_0)=l$ we can extend $f$ to $[s_0,s_1]\times[0,t_1]$ by
induction on the number of segments of~$\pi'$; for the remaining segments
$p_i$ (including $p_0$ if $l(\tau_0)<l$) we can apply the hypothesis of
induction with respect to $l(\tau)$, and conclude that we can extend $f$
successively to the rectangles $[s_i,s_{i+1}]\times[0,t_1]$; this defines $f$
uniquely on $[0,1]\times[0,1]$. \QED

It is not difficult to see that the rules \mpathrule~and~\psipathrule\ can
obtained as instances of construction~\plpathjdt; as a consequence, that
construction generalises the constructions \mpathjdt~and~\psipathjdt. The
symmetries of those constructions are preserved, since one can show with
similar arguments as we gave to show that the function obtained by elementary
extension satisfies rule~\plpathrule, that the transpose function
$f'(s,t)=f(t,s)$ also satisfies that rule.

\proclaim Theorem (symmetry of jeu de taquin for piecewise linear paths).
\plinvthm
If a piecewise linear function~$f$ satisfies rule~\plpathrule, then the
transpose function~$f'$ defined by $f'(s,t)=f(t,s)$ satisfies that rule as
well. In particular, the construction~\plpathjdt\ is its own inverse: if when
applied to $(\kappa,\pi',p)$ it returns $(\pi,p')$, then applied to
$(\kappa,\pi,p')$ it will return $(\pi',p)$. Moreover,
construction~\plpathjdt\ is symmetrical with respect to dualisation
of paths: when applied to $(\nu,p^*,\pi'^*)$ it will return $(p'^*,\pi^*)$.
\QED

Since construction~\plpathjdt\ is does not refer to any integrality condition
at all, it is not easy to relate it directly to the root operators $e_\alpha$
and $f_\alpha$. It is for instance not true that the paths $\pi$~and~$p$ are
related by a sequence of applications of such operators, not even in the case
of an elementary extension. What one gets instead is a sequence of
applications of fractional powers $e_\alpha^x$ or $f_\alpha^x$ of root
operators with $x\in\Q$; here $e_\alpha^x$ maps a path~$p$ to a non-zero value
if and only if $\mm<0+p,\alpha>\leq-x$, in which case one has
$$
  e_\alpha^x(p)(s) =
  p(s)+\max\left(0,x+\mm<0+p,\alpha>-\min_{t\in[0,s]}\<p(t),\alpha\ch>\right)
  \alpha.
$$
A relation with root operators which seems plausible, and which we hope to
establish in further work, can be formulated as follows. Let us call a path
$p\in\Pi$ of integral shape if $p\in B_\pi$ for some $\pi\in\Pdom$. Then if
$\kappa\in X$, and if $\pi'$ and $p$ are of integral shape, then so are the
paths $\pi$~and~$p'$ obtained from $\kappa$,~$\pi'$, and~$p$ by
construction~\plpathjdt; moreover $\pi$ can be obtained from~$p$ by a sequence
of applications of operators $e_\alpha$, and $p'$ from~$\pi'$ by applications
of operators $f_\alpha$. This would imply in particular that if $\kappa=0$
then $p\in B_\pi$ and $p'\in B_{\pi'}$, and that the construction defines, for
any fixed pair of paths $\pi,\pi'\in\Pdom$ with $\pi'(1)=\\$ and $\pi(1)=\mu$,
a bijection between the $\\$-dominant paths $p\in B_\pi$ and the
$\mu$-dominant paths $p'\in B_{\pi'}$, with moreover $\\+p(1)=\mu+p'(1)$. It
would also imply that any class of paths of integral shape, that is closed
under the root operators (such as for instance the class of
Lakshmibai-Seshadri paths), would also be closed under
construction~\plpathjdt, which would therefore give rise to a special instance
of it, similar to constructions
\mpathjdt~and~\psipathjdt.

\Supplement References.

%\input \jobname.ref
\beginrefs

\ref KaNa \key crystal graphs
\author M. Kashiwara and T. Nakashima
\title Crystal graphs for representations of the $q$-analogue of classical
       Lie algebras
\journal Journal of Algebra \vol 165 \pages 295-345 \year 1994
\endref

\ref vLee1 \key van Leeuwen festschrift
 \author M. A. A. van Leeuwen
 \title The Robinson-Schensted and Sch\"utzenberger algorithms, an elementary
        approach
 \journal Electronic J. of Combinatorics \vol 3 (no.~2) \idno R15 \year 1996
 \npages 32
\endref

\ref vLee2 \key van Leeuwen pictures
 \author M. A. A. van Leeuwen
 \title Tableau algorithms defined naturally for pictures
 \journal Discrete Mathematics \vol 157 \year 1996 \pages 321-362
\endref

\ref vLee3 \key van Leeuwen edge sequences
 \author M. A. A. van Leeuwen
 \title Edge sequences, ribbon tableaux, and an action of affine permutations
 \report Report MAS-R9707, CWI, Amsterdam
 \endnote To appear in {\sl European Journal of Combinatorics}
\endref

\ref vLee4 \key van Leeuwen domino tableaux
 \author M. A. A. van Leeuwen
 \title Some bijective correspondences involving domino tableaux
 \report Report MAS-R9708, CWI, Amsterdam
\endref

\ref Litt1 \key Littelmann Kac-Moody
 \author P. Littelmann
 \title A Littlewood-Richardson rule for symmetrizable Kac-Moody algebras
 \journal Inventiones mathematicae \vol 116 \year 1994 \pages 329-346
\endref

\ref Litt2 \key Littelmann paths
 \author P. Littelmann
 \title Paths and root operators in representation theory
 \journal Annals of Mathematics \vol 142 \year 1995 \pages 499-525
\endref

\ref Litt3 \key Littelmann plactic
 \author P. Littelmann
 \title A plactic algebra for semisimple Lie algebras
 \journal Advances in Math. \vol 124 (2) \year Dec. 1996 \pages 312-331
\endref

\ref Macd \key Macdonald
 \author I. G. Macdonald
 \title Symmetric Functions and Hall Polynomials
 \publ Clarendon press, Oxford \year 1979
 \series Oxford Mathematical Monographs
\endref

\ref Rob \key Robinson
 \author G. de B. Robinson
 \title On the representations of the symmetric group
 \journal American Journal of Math. \vol 60 \year 1938 \pages 745-760
\endref


\ref Zel1 \key Zelevinsky pictures
 \author  A. V. Zelevinsky
 \title A Generalisation of the Littlewood-Richardson Rule and the
  Robinson-Schensted-Knuth Correspondence
 \journal Journal of Algebra \vol 69 \year 1981 \pages 82-94
\endref


\endrefs
% END of pathjdt.ref

\iftoc
  \closeout\tocfile \vfil\eject \def\tocitem#1=#2\onpage#3. {\par\line{\hbox
  to 1.5pc{\bf #1\hss}\quad#2\dotfill#3}\ignorespaces} \input \jobname.toc

\fi

\bye