\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
\usepackage{wasysym}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, July 05, 2020 11:29:29}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\are}{\ar@{-}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\bigcapnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcap}{\bigcapnonlimits\limits}
\newcommand{\maketoc}{\tableofcontents}
\iffalse
\NOEXPAND{\maketoc}{\tableofcontents}
\fi
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{Errata to ``Noncommutative Schur functions''}
\ohead{\today}
\begin{document}

\begin{center}
\textbf{Noncommutative Schur functions and their applications}

\textit{Sergey Fomin and Curtis Greene}

\url{https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.6773&rep=rep1&type=pdf}
(\texttt{fomin greene - ncschur.ps})

version of 12 December 1996

\textbf{Errata and addenda by Darij Grinberg}

\bigskip
\end{center}

\maketoc


\setcounter{section}{7}

\section*{***}

The following is a list of errors and comments to the paper \textquotedblleft
Noncommutative Schur functions and their applications\textquotedblright\ by
Sergey Fomin and Curtis Greene in the version of 12 December 1996. (This is
not \href{https://doi.org/10.1016/S0012-365X(98)00140-X}{the version that was
published in Discrete Mathematics 306 (2006), pp. 1080--1096}; but almost all
of the errors listed here exist in the published version as well. Of course,
the numbering of the pages differs from that in the published version.)

\section{Errata}

\begin{itemize}
\item \textbf{Page 2, Section 1:} After \textquotedblleft the sum ranges over
all semi-standard tableaux $T$ of shape $\lambda$\textquotedblright, add
\textquotedblleft with entries in $\left\{  1,2,\ldots,n\right\}
$\textquotedblright.

\item \textbf{Page 2, Section 1:} After \textquotedblleft For example, if
$\lambda=\left(  3,2\right)  $\textquotedblright, add \textquotedblleft and
$n=2$\textquotedblright.

\item \textbf{Page 2, Section 1:} After \textquotedblleft the sum is over all
semi-standard skew tableaux $T$ of shape $\lambda/\mu$\textquotedblright, add
\textquotedblleft with entries in $\left\{  1,2,\ldots,n\right\}
$\textquotedblright.

\item \textbf{Page 4, Section 1:} Replace \textquotedblleft$u_{i}$ adds a box
in row $i$\textquotedblright\ by \textquotedblleft$u_{i}$ adds a box in column
$i$\textquotedblright. (This typo has been corrected in
\href{https://doi.org/10.1016/S0012-365X(98)00140-X}{the published version of
the paper}.)

\item \textbf{Page 4, Theorem 2:} It should be said that here and in the
following, the conjugate of a partition $\lambda$ is denoted by $\lambda
^{\prime}$.

\item \textbf{Page 5, just before Theorem 1.3:} I would add the following
sentence right before Theorem 1.3: \textquotedblleft An \textit{ascent} of a
word $w=a_{1}a_{2}\cdots a_{m}$ means an index $i\in\left\{  1,2,\ldots
,m-1\right\}  $ such that $a_{i}\leq a_{i+1}$.\textquotedblright

\item \textbf{Page 6, the paragraph above Example 2.2:} You write:
\textquotedblleft In the case of the plactic algebra, $F_{h}$ is just the
Schur function $s_{\lambda^{\ast}}$\textquotedblright. I think $\lambda^{\ast
}$ means the transpose of the partition $\lambda$ here; but this should be
explained. (It is not a common notation for the transpose. You seem to
yourself use a different notation -- namely, $\lambda^{\prime}$ -- later in
the paper.)

\item \textbf{Page 6, the paragraph above Example 2.2:} Replace
\textquotedblleft all standard tableaux T\textquotedblright\ by
\textquotedblleft all standard tableaux $T$\textquotedblright\ (the
\textquotedblleft$T$\textquotedblright\ should be in mathmode).

This said, I don't understand the whole sentence around this: How do you
manage to restrict attention to the standard tableaux? Many of the $h$'s have
repeated letters. I would rather prove the fact that $F_{h}=s_{\lambda^{\ast}%
}$ using a variation on the RSK algorithm.

\item \textbf{Page 7, Example 2.4:} Replace \textquotedblleft are the
permutations $a_{1}\cdots a_{n}$\textquotedblright\ by \textquotedblleft are
the permutations $a_{1}\cdots a_{n+1}\in S_{n+1}$ (written here in one-line
notation, i.e., such that $a_{i}$ is the image of $i$)\textquotedblright.

\item \textbf{Page 10, (3.3):} After the equality (3.3), I suggest explaining
that $\det\left(  e_{\lambda_{i}^{\prime}-\mu_{j}^{\prime}+j-i}\left(
\mathbf{u}\right)  \right)  $ means the determinant of the $N\times N$-matrix
$\left(  e_{\lambda_{i}^{\prime}-\mu_{j}^{\prime}+j-i}\left(  \mathbf{u}%
\right)  \right)  _{1\leq i\leq N,\ 1\leq j\leq N}$, where $N$ is a
nonnegative integer large enough to satisfy $N\geq\lambda_{1}$ and $N\geq
\mu_{1}$.

\item \textbf{Page 11, proof of Lemma 3.2:} \textquotedblleft with families of
lattice paths $\left(  \pi_{1j_{1}},\pi_{2j_{2}},\ldots\right)  $%
\textquotedblright\ $\rightarrow$ \textquotedblleft with families of lattice
paths $\left(  \pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}\right)  $, where
$N$ is the size of the matrix on the right hand side of
(3.3)\textquotedblright.

Likewise, replace \textquotedblleft$\left(  \pi_{1j_{1}},\pi_{2j_{2}}%
,\ldots\right)  $\textquotedblright\ by \textquotedblleft$\left(  \pi_{1j_{1}%
},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}\right)  $\textquotedblright\ throughout the
rest of this proof.

\item \textbf{Page 11, proof of Lemma 3.2:} It would be good to explain what a
\textquotedblleft lattice path\textquotedblright\ is. Probably the simplest
way to do so is the following: Let $G$ be the directed graph whose vertex set
is $\mathbb{Z}^{2}$ and which has arcs from every lattice point $\left(
\alpha,\beta\right)  \in\mathbb{Z}^{2}$ to $\left(  \alpha+1,\beta\right)  $
and to $\left(  \alpha,\beta+1\right)  $ (and no further arcs). Then, a
\textit{lattice path} means a (directed) path on $G$.

\item \textbf{Page 11, proof of Lemma 3.2:} In the caption of Figure 1,
replace \textquotedblleft$m\left(  \pi_{21}\right)  =5432,\ m\left(  \pi
_{12}\right)  =5,\ m\left(  \pi_{33}\right)  =51$\textquotedblright\ by
\textquotedblleft$m\left(  \pi_{21}\right)  =u_{5}u_{4}u_{3}u_{2},\ m\left(
\pi_{12}\right)  =u_{5},\ m\left(  \pi_{33}\right)  =u_{5}u_{1}$%
\textquotedblright.

\item \textbf{Page 11, proof of Lemma 3.2:} Replace \textquotedblleft the
expression $e_{\lambda_{i}^{\prime}-\mu_{j}^{\prime}+j-i}\left(
\mathbf{u}\right)  $\textquotedblright\ by \textquotedblleft the expression
$e_{\lambda_{j}^{\prime}-\mu_{i}^{\prime}+i-j}\left(  \mathbf{u}\right)
$\textquotedblright.

\item \textbf{Page 12, proof of Lemma 3.2:} Here you write: \textquotedblleft
The corresponding two paths must have consecutive terminal points, say $Q_{k}$
and $Q_{k+1}$\textquotedblright. This claim (and also the implicit claim that
only two paths intersect in the lexicographically maximal intersection) is not
completely obvious and, in my opinion, warrants some justification. I give
detailed proofs of these claims in Subsection \ref{subsect.11} below. (Namely,
these two claims are parts \textbf{(a)} and \textbf{(b)} of Lemma
\ref{lem.3.2.obv}.)

\item \textbf{Page 12, proof of Lemma 3.2:} After \textquotedblleft Then
$m\left(  \pi_{i,k}\right)  m\left(  \pi_{j,k+1}\right)  $ may be factored
as\textquotedblright, I'd add a footnote saying that we are abusing notation
to equate any string $i_{1}i_{2}\cdots i_{k}$ of elements of $\left\{
1,2,\ldots,n\right\}  $ with the corresponding product $u_{i_{1}}u_{i_{2}%
}\cdots u_{i_{k}}$.

\item \textbf{Page 12, proof of Lemma 3.2:} You write: \textquotedblleft Here
$p$ labels the vertical segment in $\pi_{i,k}$ that lies just above $\left(
\alpha,\beta\right)  $\textquotedblright. This relies on the fact that there
is a vertical segment in $\pi_{i,k}$ that lies just above $\left(
\alpha,\beta\right)  $ (in other words, the path $\pi_{i,k}$ exits $\left(
\alpha,\beta\right)  $ in the northern direction). Again, this fact is not
completely obvious; I shall prove it in Subsection \ref{subsect.11} below.
(Namely, this fact is Lemma \ref{lem.3.2.obv} \textbf{(c)}.)

\item \textbf{Page 12, proof of Lemma 3.2:} I think \textquotedblleft%
$A=a_{1}a_{2}\ldots$ and $B=b_{1}b_{2}\ldots$\textquotedblright\ should be
replaced by \textquotedblleft$A=\ldots a_{2}a_{1}$ and $B=\ldots b_{2}b_{1}%
$\textquotedblright. (It would also be good to mention that the
\textquotedblleft$\ldots$\textquotedblright\ symbols here do not signify
infinite strings, but merely finite strings whose lengths are immaterial.) You
should also mention that $\ell\left(  A\right)  \geq\ell\left(  B\right)  $,
where $\ell\left(  C\right)  $ denotes the length of a string $C$.

\item \textbf{Page 12, proof of Lemma 3.3:} I don't understand what you mean
by \textquotedblleft jeu-de-taquin transformations\textquotedblright\ here. I
give a completely elementary proof of Lemma 3.3 in Subsection
\ref{subsect.jdt} below.

\item \textbf{Page 13, proof of Lemma 3.3:} \textquotedblleft by all
configurations\textquotedblright\ $\rightarrow$ \textquotedblleft by all
families of paths\textquotedblright.

\item \textbf{Page 13, proof of Lemma 3.3:} \textquotedblleft not involving
$P_{j},P_{k},Q_{k},Q_{k+1}$\textquotedblright\ $\rightarrow$ \textquotedblleft
not involving $P_{i},P_{j},Q_{k},Q_{k+1}$\textquotedblright.

\item \textbf{Page 13, proof of Lemma 3.3:} You write: \textquotedblleft Hence
we have constructed a sign-reversing involution which leaves only terms of
(3.3) corresponding to non-intersecting families of paths\textquotedblright.
This is not correct as stated. What you have constructed is not an involution
on the set of all families $\left(  \pi_{1j_{1}},\pi_{2j_{2}},\ldots
,\pi_{Nj_{N}}\right)  $ of paths. The problem is that each term%
\[
W_{1}Ape_{r}\left(  u_{1},\ldots,u_{\alpha+\beta}\right)  Be_{s}\left(
u_{1},\ldots,u_{\alpha+\beta}\right)  W_{2}%
\]
is not a single monomial corresponding to a single family of paths, but rather
a sum of such monomials for a certain set of families of paths (namely, for
the set of all families that agree with the original family everywhere except
on the initial segments of $\pi_{i,k}$ and $\pi_{j,k+1}$). By showing that it
equals%
\[
W_{1}Ape_{s}\left(  u_{1},\ldots,u_{\alpha+\beta}\right)  Be_{r}\left(
u_{1},\ldots,u_{\alpha+\beta}\right)  W_{2},
\]
you can conclude that the contributions of all these families to the
determinant in (3.3) cancel against the contributions of another such set of
families. This way, all terms in (3.3) contributed by intersecting families of
paths are cancelled, whereas the terms contributed by non-intersecting
families of paths are preserved. This shows that the determinant in (3.3)
reduces to the sum of the contributions of non-intersecting families; however,
this does not construct a sign-reversing involution on the single monomials in
(3.3). (Fortunately, you don't need such an involution.)

\item \textbf{Page 13, proof of Lemma 3.3:} After \textquotedblleft Now the
argument continues exactly as in the commutative case.\textquotedblright, add
\textquotedblleft Every family $\left(  \pi_{1j_{1}},\pi_{2j_{2}},\ldots
,\pi_{Nj_{N}}\right)  $ of non-intersecting paths $\pi_{ij_{i}}$ must have
$\left(  j_{1},j_{2},\ldots,j_{N}\right)  =\left(  1,2,\ldots,N\right)
$.\textquotedblright\ See Subsection \ref{subsect.only-id} below for the proof
of this statement. (Namely, this statement is Lemma \ref{lem.only-id}.)

\item \textbf{Page 13, proof of Lemma 3.3:} After \textquotedblleft and hence
of Theorem 1.1\textquotedblright\ (in the last sentence of the proof), I would
add \textquotedblleft(since the (unique) algebra homomorphism from
$\Lambda_{n}$ to $A$ that sends $e_{1},e_{2},e_{3},\ldots$ to $e_{1}\left(
\mathbf{u}\right)  ,e_{2}\left(  \mathbf{u}\right)  ,e_{3}\left(
\mathbf{u}\right)  ,\ldots$ will send each $e_{i}$ (for $i\in\mathbb{Z}$) to
the corresponding $e_{i}\left(  \mathbf{u}\right)  $ (because $e_{0}\left(
\mathbf{u}\right)  =1$ and $e_{i}\left(  \mathbf{u}\right)  =0$ for all
$i<0$), and therefore will send each $s_{\lambda/\mu}=\det\left(
e_{\lambda_{i}^{\prime}-\mu_{j}^{\prime}+j-i}\right)  $ to $\det\left(
e_{\lambda_{i}^{\prime}-\mu_{j}^{\prime}+j-i}\left(  \mathbf{u}\right)
\right)  =\mathfrak{J}_{\lambda/\mu}\left(  \mathbf{u}\right)  =s_{\lambda
/\mu}\left(  \mathbf{u}\right)  $ (by Lemma 3.2))\textquotedblright.

\item \textbf{Page 15, proof of Theorem 1.3:} After \textquotedblleft the
complete noncommutative analog of the Frobenius formula
(5.2)\textquotedblright, I would add \textquotedblleft, namely the formula%
\[
p_{\alpha}\left(  \mathbf{u}\right)  =\operatorname*{sgn}\left(
\alpha\right)  \sum_{\lambda}\chi_{\lambda}\left(  \alpha\right)
s_{\lambda^{\prime}}\left(  \mathbf{u}\right)
\]
\textquotedblright\ (just for the sake of clarity).

\item \textbf{Page 18, Section 6:} \textquotedblleft a linear operator in
$V\otimes V$\textquotedblright\ $\rightarrow$ \textquotedblleft a linear
operator from $V\otimes V$ to $V\otimes V$\textquotedblright.

\item \textbf{Page 18, Section 6:} \textquotedblleft Now let $u_{i}$ act
in\textquotedblright\ $\rightarrow$ \textquotedblleft Now let $u_{i}$ act
on\textquotedblright.

\item \textbf{Page 18, Section 6:} \textquotedblleft by $u_{i}=I^{\left(
i-1\right)  }\otimes u\otimes I^{\left(  n-i\right)  }$\textquotedblright%
\ $\rightarrow$ \textquotedblleft by $u_{i}=I^{\otimes\left(  i-1\right)
}\otimes u\otimes I^{\otimes\left(  n-i\right)  }$\textquotedblright.

\item \textbf{Page 18, Section 6:} \textquotedblleft an identity
operator\textquotedblright\ $\rightarrow$ \textquotedblleft the identity
operator\textquotedblright.

\item \textbf{Page 18, Example 6.1:} After \textquotedblleft and $\epsilon$ is
a \textit{right} unit of $\mathcal{M}$\textquotedblright, add
\textquotedblleft(that is, $\epsilon\in\mathcal{M}$ satisfies $\alpha
\epsilon=\alpha$ for each $\alpha\in\mathcal{M}$)\textquotedblright. (The
notion of a right unit used here is not very well-known.)

\item \textbf{Page 18, Example 6.1:} After \textquotedblleft If $\epsilon$ is
a \textit{left} unit of $\mathcal{M}$\textquotedblright, add \textquotedblleft%
(that is, $\epsilon\in\mathcal{M}$ satisfies $\epsilon\alpha=\alpha$ for each
$\alpha\in\mathcal{M}$)\textquotedblright.

\item \textbf{Page 19, Lemma 6.6:} I think you want to assume that the
operations $\wedge$ and $\vee$ are associative here. (At least, I need this
assumption to prove the sufficiency.)

\item \textbf{Page 20, Example 6.7:} I don't think $u$ is well-defined as
stated: the right-hand side $p\cdot\alpha\otimes\beta+\left(  1-p\right)
\cdot\alpha\otimes\alpha$ is not bilinear in $\left(  \alpha,\beta\right)  $,
so the equation does not yield a well-defined linear map from the tensor
product $V\otimes V$. (But you can salvage this definition by requiring the
equation to hold only in the case when $\alpha$ and $\beta$ belong to a fixed
basis of $V$.)
\end{itemize}

\section{Remarks and addenda}

\subsection{Another proof of the symmetry of $F_{h/g}$}

On page 4, you say that \textquotedblleft Note that $F_{h/g}$ is a function in
the commuting variables $x_{i}$ alone; we shall later demonstrate that this is
indeed a symmetric function, in the ordinary sense\textquotedblright. It is,
in fact, easy to derive the symmetry of $F_{h/g}$ from Theorem 1.1 (or, even
better, from Lemma 3.1):

\begin{proof}
[Proof of the fact that $F_{h/g}$ is symmetric in the $x_{i}$:]The relations
(1.2) and (1.3) hold. Therefore, the conditions of Lemma 3.1 are satisfied (in
fact, the relations (3.2) follow immediately from (1.2), whereas the relations
(3.2) follow from (1.2) when $j-i>1$ and from (1.3) when $j-i=1$). Hence,
Lemma 3.1 yields that the elements $e_{k}\left(  u_{1},\ldots,u_{n}\right)  $
for $k\in\mathbb{N}$ commute. These elements clearly commute with all of the
$x_{1},x_{2},\ldots,x_{m}$. Thus, all of the elements $e_{k}\left(
u_{1},\ldots,u_{n}\right)  $ and the elements $x_{1},x_{2},\ldots,x_{m}$
commute with each other. Therefore, the subalgebra of $A$ generated by the
elements $e_{k}\left(  u_{1},\ldots,u_{n}\right)  $ and the elements
$x_{1},x_{2},\ldots,x_{m}$ is commutative\footnote{Here, $A$ is supposed to be
an algebra that contains $u_{1},u_{2},\ldots,u_{n}$ and $x_{1},x_{2}%
,\ldots,x_{m}$.}. Let $B$ denote this subalgebra.

Let $Z\left(  A\right)  $ denote the center of the ring $A$. For every $t\in
Z\left(  A\right)  $, we have%
\begin{align}
\prod_{j=n}^{1}\left(  1+tu_{j}\right)   &  =\left(  1+tu_{n}\right)  \left(
1+tu_{n-1}\right)  \cdots\left(  1+tu_{1}\right) \nonumber\\
&  =\sum_{k=0}^{n}e_{k}\left(  u_{1},\ldots,u_{n}\right)  t^{n}.
\label{p4.vieta}%
\end{align}
(In fact, this is a noncommutative analogue of the classical formula that
$\prod_{j=1}^{n}\left(  1+t\alpha_{j}\right)  =\sum_{k=0}^{n}e_{k}\left(
\alpha_{1},\ldots,\alpha_{n}\right)  t^{n}$ for any elements $\alpha
_{1},\alpha_{2},\ldots,\alpha_{n},t$ of a commutative algebra; and it can be
proven by induction over $n$ in the same way.) Now, for every $i\in\left\{
1,2,\ldots,m\right\}  $, we have%
\begin{align*}
\prod_{j=n}^{1}\left(  1+x_{i}u_{j}\right)   &  =\sum_{k=0}^{n}%
\underbrace{e_{k}\left(  u_{1},\ldots,u_{n}\right)  }_{\in B}\underbrace{x_{i}%
^{n}}_{\substack{\in B\\\text{(since }x_{i}\in B\text{)}}%
}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{p4.vieta}), applied to }%
t=x_{i}\right) \\
&  \in\sum_{k=0}^{n}BB\subseteq B.
\end{align*}
Thus, $\prod_{i=1}^{m}\prod_{j=n}^{1}\left(  1+x_{i}u_{j}\right)  $ is a
product of elements of $B$. Since $B$ is commutative, this shows that the
order of these elements is immaterial -- that is, we can reorder the entries
of the (outer) product $\prod_{i=1}^{m}\prod_{j=n}^{1}\left(  1+x_{i}%
u_{j}\right)  $ without changing its value. But reordering the entries of the
(outer) product $\prod_{i=1}^{m}\prod_{j=n}^{1}\left(  1+x_{i}u_{j}\right)  $
has the same effect as permuting the variables $x_{1},x_{2},\ldots,x_{m}$.
Therefore, we conclude that permuting the variables $x_{1},x_{2},\ldots,x_{m}$
does not change the value of $\prod_{i=1}^{m}\prod_{j=n}^{1}\left(
1+x_{i}u_{j}\right)  $. Therefore, permuting the variables $x_{1},x_{2}%
,\ldots,x_{m}$ does not change the value of $\left\langle \prod_{i=1}^{m}%
\prod_{j=n}^{1}\left(  1+x_{i}u_{j}\right)  g,h\right\rangle $. In other
words, $\left\langle \prod_{i=1}^{m}\prod_{j=n}^{1}\left(  1+x_{i}%
u_{j}\right)  g,h\right\rangle $ is symmetric in the $x_{1},x_{2},\ldots
,x_{m}$. Qed.
\end{proof}

\subsection{\label{subsect.11}Some details for the proof of Lemma 3.2}

In this subsection, we shall give detailed proofs of three statements left
unproved in the proof of Lemma 3.2.

The notations introduced during the proof of Lemma 3.2 shall be used
throughout Subsection \ref{subsect.11}. We shall prove the claim
\textquotedblleft The corresponding two paths must have consecutive terminal
points, say $Q_{k}$ and $Q_{k+1}$\textquotedblright\ made on page 12, as well
as the implicit claim that only two paths intersect in the lexicographically
maximal intersection. We shall also prove that the path that ends in $Q_{k}$
has a vertical segment that lies just above $\left(  \alpha,\beta\right)  $.

In the following, an \textquotedblleft intersection point\textquotedblright%
\ will mean a point in which (at least) two of the paths $\pi_{1j_{1}}%
,\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect. We shall now prove the following:

\begin{lemma}
\label{lem.3.2.obv}Let $X$ denote the intersection point $\left(  \alpha
,\beta\right)  $ with the pair $\left(  \alpha+\beta,\alpha-\beta\right)  $
lexicographically maximal. Then:

\textbf{(a)} Exactly two of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots
,\pi_{Nj_{N}}$ intersect at $X$.

\textbf{(b)} These two paths must end at two points of the form $Q_{k}$ and
$Q_{k+1}$ for some $k\in\left\{  1,2,\ldots,N-1\right\}  $.

\textbf{(c)} The path (among these two paths) that ends in $Q_{k}$ contains
the vertical segment $\left(  \alpha,\beta\right)  \mapsto\left(  \alpha
,\beta+1\right)  $, where $\left(  \alpha,\beta\right)  =X$.
\end{lemma}

Before we prove Lemma \ref{lem.3.2.obv}, let us introduce a notation. The
\textit{depth} of a lattice point $\left(  \gamma,\delta\right)  \in
\mathbb{Z}^{2}$ will mean the sum $\gamma+\delta$; it will be denoted by
$\mathbf{d}\left(  \left(  \gamma,\delta\right)  \right)  $. The \textit{tilt}
of a lattice point $\left(  \gamma,\delta\right)  \in\mathbb{Z}^{2}$ will mean
the difference $\gamma-\delta$; it will be denoted by $\mathbf{t}\left(
\left(  \gamma,\delta\right)  \right)  $. Notice that the pair $\left(
\mathbf{d}\left(  T\right)  ,\mathbf{t}\left(  T\right)  \right)  $ uniquely
determines a point $T\in\mathbb{Z}^{2}$. In other words, if $T_{1}$ and
$T_{2}$ are two points in $\mathbb{Z}^{2}$ such that $\left(  \mathbf{d}%
\left(  T_{1}\right)  ,\mathbf{t}\left(  T_{1}\right)  \right)  =\left(
\mathbf{d}\left(  T_{2}\right)  ,\mathbf{t}\left(  T_{2}\right)  \right)  $,
then%
\begin{equation}
T_{1}=T_{2}. \label{11.T1=T2}%
\end{equation}
Notice also that every $T\in\mathbb{Z}^{2}$ satisfies%
\begin{equation}
\mathbf{t}\left(  T\right)  \equiv\mathbf{d}\left(  T\right)
\operatorname{mod}2. \label{11.tTdT}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.tTdT}):} Let $T\in\mathbb{Z}^{2}$. Let us
write $T$ in the form $\left(  \gamma,\delta\right)  $ for some integers
$\gamma$ and $\delta$. Then, $\mathbf{t}\left(  \underbrace{T}_{=\left(
\gamma,\delta\right)  }\right)  =\mathbf{t}\left(  \left(  \gamma
,\delta\right)  \right)  =\gamma-\delta$ (by the definition of $\mathbf{t}%
\left(  \left(  \gamma,\delta\right)  \right)  $) and $\mathbf{d}\left(
\underbrace{T}_{=\left(  \gamma,\delta\right)  }\right)  =\mathbf{d}\left(
\left(  \gamma,\delta\right)  \right)  =\gamma+\delta$ (by the definition of
$\mathbf{d}\left(  \left(  \gamma,\delta\right)  \right)  $). Now,
$\mathbf{t}\left(  T\right)  =\gamma-\delta=\gamma+\underbrace{\left(
-1\right)  }_{\equiv1\operatorname{mod}2}\delta\equiv\gamma+\delta
=\mathbf{d}\left(  T\right)  \operatorname{mod}2$. This proves (\ref{11.tTdT}%
).}

We have%
\begin{equation}
\mathbf{d}\left(  P_{i}\right)  =0\ \ \ \ \ \ \ \ \ \ \text{for every }%
i\in\left\{  1,2,\ldots,N\right\}  .\label{11.dPi}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.dPi}):} Let $i\in\left\{  1,2,\ldots
,N\right\}  $. Then, the definition of $P_{i}$ yields $P_{i}=\left(  \left(
i-1\right)  -\mu_{i}^{\prime},-\left(  i-1\right)  +\mu_{i}^{\prime}\right)
$, so that
\begin{align*}
\mathbf{d}\left(  P_{i}\right)    & =\mathbf{d}\left(  \left(  \left(
i-1\right)  -\mu_{i}^{\prime},-\left(  i-1\right)  +\mu_{i}^{\prime}\right)
\right)  =\left(  \left(  i-1\right)  -\mu_{i}^{\prime}\right)  +\left(
-\left(  i-1\right)  +\mu_{i}^{\prime}\right)  \\
& \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\mathbf{d}\left(
\left(  \left(  i-1\right)  -\mu_{i}^{\prime},-\left(  i-1\right)  +\mu
_{i}^{\prime}\right)  \right)  \right)  \\
& =0.
\end{align*}
This proves (\ref{11.dPi}).} Also,%
\begin{equation}
\mathbf{d}\left(  Q_{j}\right)  =n\ \ \ \ \ \ \ \ \ \ \text{for every }%
j\in\left\{  1,2,\ldots,N\right\}  .\label{11.dQj}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.dQj}):} Let $j\in\left\{  1,2,\ldots
,N\right\}  $. Then, the definition of $Q_{j}$ yields $Q_{j}=\left(  n+\left(
j-1\right)  -\lambda_{j}^{\prime},-\left(  j-1\right)  +\lambda_{j}^{\prime
}\right)  $, so that
\begin{align*}
\mathbf{d}\left(  Q_{j}\right)    & =\mathbf{d}\left(  \left(  n+\left(
j-1\right)  -\lambda_{j}^{\prime},-\left(  j-1\right)  +\lambda_{j}^{\prime
}\right)  \right)  =\left(  n+\left(  j-1\right)  -\lambda_{j}^{\prime
}\right)  +\left(  -\left(  j-1\right)  +\lambda_{j}^{\prime}\right)  \\
& \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\mathbf{d}\left(
\left(  n+\left(  j-1\right)  -\lambda_{j}^{\prime},-\left(  j-1\right)
+\lambda_{j}^{\prime}\right)  \right)  \right)  \\
& =n.
\end{align*}
This proves (\ref{11.dQj}).} Now, let us consider the directed graph $G$
(which was defined above in my first comment on \textquotedblleft page 11,
proof of Lemma 3.2\textquotedblright). If $\left(  U,V\right)  $ is an arc of
the directed graph $G$, then%
\begin{equation}
\mathbf{d}\left(  V\right)  =\mathbf{d}\left(  U\right)  +1\label{11.dVU}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.dVU}):} Let $\left(  U,V\right)  $ be an
arc of the directed graph $G$. Write the point $U$ in the form $U=\left(
\gamma,\delta\right)  $. Then, $V$ is either $\left(  \gamma+1,\delta\right)
$ or $\left(  \gamma,\delta+1\right)  $ (since $\left(  U,V\right)  $ is an
arc of $G$). In either of these two cases, we have $\mathbf{d}\left(
V\right)  =\mathbf{d}\left(  U\right)  +1$. Hence, (\ref{11.dVU}) is proven.}
and%
\begin{equation}
\mathbf{t}\left(  U\right)  -1\leq\mathbf{t}\left(  V\right)  \leq
\mathbf{t}\left(  U\right)  +1\label{11.tVU}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.tVU}):} Let $\left(  U,V\right)  $ be an
arc of the directed graph $G$. Write the point $U$ in the form $U=\left(
\gamma,\delta\right)  $. Then, $V$ is either $\left(  \gamma+1,\delta\right)
$ or $\left(  \gamma,\delta+1\right)  $ (since $\left(  U,V\right)  $ is an
arc of $G$). We have $\mathbf{t}\left(  V\right)  =\mathbf{t}\left(  U\right)
+1$ in the first of these two cases, and we have $\mathbf{t}\left(  V\right)
=\mathbf{t}\left(  U\right)  -1$ in the second of these two cases. Thus, we
have $\mathbf{t}\left(  U\right)  -1\leq\mathbf{t}\left(  V\right)
\leq\mathbf{t}\left(  U\right)  +1$ in either case. Hence, (\ref{11.tVU}) is
proven.}. For every $i\in\left\{  1,2,\ldots,N\right\}  $ and every
$k\in\left\{  0,1,\ldots,n\right\}  $,%
\begin{equation}
\text{there exists exactly one point }F\text{ on the path }\pi_{ij_{i}}\text{
such that }\mathbf{d}\left(  F\right)  =k.\label{11.F}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.F}):} Let $i\in\left\{  1,2,\ldots
,N\right\}  $. Write the path $\pi_{ij_{i}}$ in the form $\left(  F_{0}%
,F_{1},\ldots,F_{\ell}\right)  $. Since the path $\pi_{ij_{i}}$ begins at
$P_{i}$ and ends at $Q_{j_{i}}$, we must have $F_{0}=P_{i}$ and $F_{\ell
}=Q_{j_{i}}$. Moreover, for every $p\in\left\{  0,1,\ldots,\ell-1\right\}  $,
the pair $\left(  F_{p},F_{p+1}\right)  $ is an arc of the directed graph $G$
(since $\left(  F_{0},F_{1},\ldots,F_{\ell}\right)  $ is a path in $G$) and
thus satisfies $\mathbf{d}\left(  F_{p+1}\right)  =\mathbf{d}\left(
F_{p}\right)  +1$ (by (\ref{11.dVU}), applied to $U=F_{p}$ and $V=F_{p+1}$).
\par
Thus, we know that $\mathbf{d}\left(  F_{p+1}\right)  =\mathbf{d}\left(
F_{p}\right)  +1$ for every $p\in\left\{  0,1,\ldots,\ell-1\right\}  $. In
other words, $\left(  \mathbf{d}\left(  F_{0}\right)  ,\mathbf{d}\left(
F_{1}\right)  ,\ldots,\mathbf{d}\left(  F_{\ell}\right)  \right)  $ is an
arithmetic sequence with difference $1$ (that is, $\mathbf{d}\left(
F_{p}\right)  $ grows by $1$ every time we increase $p$ by $1$). Thus,%
\begin{equation}
\mathbf{d}\left(  F_{p}\right)  =\mathbf{d}\left(  F_{0}\right)
+p\ \ \ \ \ \ \ \ \ \ \text{for every }p\in\left\{  0,1,\ldots,\ell\right\}
.\label{11.F.pf.1}%
\end{equation}
Since $\mathbf{d}\left(  \underbrace{F_{0}}_{=P_{i}}\right)  =\mathbf{d}%
\left(  P_{i}\right)  =0$ (by (\ref{11.dPi})), this shows that%
\begin{equation}
\mathbf{d}\left(  F_{p}\right)  =\underbrace{\mathbf{d}\left(  F_{0}\right)
}_{=0}+p=p\ \ \ \ \ \ \ \ \ \ \text{for every }p\in\left\{  0,1,\ldots
,\ell\right\}  .\label{11.F.pf.2}%
\end{equation}
Applying this to $p=\ell$, we obtain $\mathbf{d}\left(  F_{\ell}\right)
=\ell$. Thus, $\ell=\mathbf{d}\left(  \underbrace{F_{\ell}}_{=Q_{j_{i}}%
}\right)  =\mathbf{d}\left(  Q_{j_{i}}\right)  =n$ (by (\ref{11.dQj}), applied
to $j=j_{i}$).
\par
Now, let $k\in\left\{  0,1,\ldots,n\right\}  $. Thus, $k\in\left\{
0,1,\ldots,\ell\right\}  $ (since $\ell=n$). Applying (\ref{11.F.pf.2}) to
$p=k$, we obtain $\mathbf{d}\left(  F_{k}\right)  =k$. Hence, $F_{k}$ is a
point on the path $\pi_{ij_{i}}$ (since $\pi_{ij_{i}}=\left(  F_{0}%
,F_{1},\ldots,F_{\ell}\right)  $) satisfying $\mathbf{d}\left(  F_{k}\right)
=k$. In other words, $F_{k}$ is a point $F$ on the path $\pi_{ij_{i}}$ such
that $\mathbf{d}\left(  F\right)  =k$.
\par
On the other hand, let $F$ be any point on the path $\pi_{ij_{i}}$ such that
$\mathbf{d}\left(  F\right)  =k$. Then, $F=F_{p}$ for some $p\in\left\{
0,1,\ldots,\ell\right\}  $ (since $F$ is a point on the path $\pi_{ij_{i}%
}=\left(  F_{0},F_{1},\ldots,F_{\ell}\right)  $). Consider this $p$. Then,
$k=\mathbf{d}\left(  \underbrace{F}_{=F_{p}}\right)  =\mathbf{d}\left(
F_{p}\right)  =p$ (by (\ref{11.F.pf.2})), so that $F_{k}=F_{p}$ and thus
$F=F_{p}=F_{k}$. Now, let us forget that we fixed $F$. We thus have shown that
if $F$ is any point on the path $\pi_{ij_{i}}$ such that $\mathbf{d}\left(
F\right)  =k$, then $F=F_{k}$. Hence, there exists at most one point $F$ on
the path $\pi_{ij_{i}}$ such that $\mathbf{d}\left(  F\right)  =k$. Since
there exists at least one such point (namely, $F_{k}$), we can thus conclude
that there exists exactly one point $F$ on the path $\pi_{ij_{i}}$ such that
$\mathbf{d}\left(  F\right)  =k$. This proves (\ref{11.F}).} We shall denote
this point by $F_{i,k}$. Thus, for every $i\in\left\{  1,2,\ldots,N\right\}  $
and every $k\in\left\{  0,1,\ldots,n\right\}  $, we have%
\begin{equation}
\mathbf{d}\left(  F_{i,k}\right)  =k.\label{11.dFik}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.dFik}):} Let $i\in\left\{  1,2,\ldots
,N\right\}  $ and $k\in\left\{  0,1,\ldots,n\right\}  $. Then, $F_{i,k}$ is
defined as the unique point $F$ on the path $\pi_{ij_{i}}$ such that
$\mathbf{d}\left(  F\right)  =k$. Hence, $F_{i,k}$ is a point $F$ on the path
$\pi_{ij_{i}}$ such that $\mathbf{d}\left(  F\right)  =k$. In other words,
$F_{i,k}$ belongs to the path $\pi_{ij_{i}}$ and satisfies $\mathbf{d}\left(
F_{i,k}\right)  =k$. This proves (\ref{11.dFik}).} Notice that for every
$i\in\left\{  1,2,\ldots,N\right\}  $, every point $U$ on the path
$\pi_{ij_{i}}$ satisfies%
\begin{equation}
\mathbf{d}\left(  U\right)  \in\left\{  0,1,\ldots,n\right\}  .\label{11.dU}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.dU}):} Let $i\in\left\{  1,2,\ldots
,N\right\}  $. Let $U$ be a point on the path $\pi_{ij_{i}}$. Write the path
$\pi_{ij_{i}}$ in the form $\left(  F_{0},F_{1},\ldots,F_{\ell}\right)  $. We
can prove that%
\begin{equation}
\mathbf{d}\left(  F_{p}\right)  =p\ \ \ \ \ \ \ \ \ \ \text{for every }%
p\in\left\{  0,1,\ldots,\ell\right\}  .\label{11.dU.pf.1}%
\end{equation}
(This can be proven just as we proved (\ref{11.F.pf.2}) in our proof of
(\ref{11.F}).) Also, $\ell=n$. (Again, this can be proven just as in our proof
of (\ref{11.F}).)
\par
But recall that $\pi_{ij_{i}}=\left(  F_{0},F_{1},\ldots,F_{\ell}\right)  $.
Hence, $U$ is a point on the path $\left(  F_{0},F_{1},\ldots,F_{\ell}\right)
$ (since $U$ is a point on the path $\pi_{ij_{i}}$). In other words, there
exists a $p\in\left\{  0,1,\ldots,\ell\right\}  $ such that $U=F_{p}$.
Consider this $p$. We have $p\in\left\{  0,1,\ldots,\ell\right\}  =\left\{
0,1,\ldots,n\right\}  $ (since $\ell=n$). Now, (\ref{11.dU.pf.1}) yields
$\mathbf{d}\left(  F_{p}\right)  =p$. So $\mathbf{d}\left(  \underbrace{U}%
_{=F_{p}}\right)  =\mathbf{d}\left(  F_{p}\right)  =p\in\left\{
0,1,\ldots,n\right\}  $. This proves (\ref{11.dU}).}.

We have%
\begin{equation}
F_{i,n}=Q_{j_{i}}\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{
1,2,\ldots,N\right\}  . \label{11.Fin}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.Fin}):} Let $i\in\left\{  1,2,\ldots
,N\right\}  $. Then, $Q_{j_{i}}$ is a point on the path $\pi_{ij_{i}}$ (since
$\pi_{ij_{i}}$ is a path from $P_{i}$ to $Q_{j_{i}}$) and satisfies
$\mathbf{d}\left(  Q_{j_{i}}\right)  =n$ (by (\ref{11.dQj}), applied to
$j=j_{i}$). Hence, $Q_{j_{i}}$ is a point $F$ on the path $\pi_{ij_{i}}$ such
that $\mathbf{d}\left(  F\right)  =n$. But we know (from (\ref{11.F}), applied
to $k=n$) that there exists exactly one such point; and we have denoted this
point by $F_{i,n}$. Therefore, $Q_{j_{i}}=F_{i,n}$. This proves (\ref{11.Fin}%
).} Also, for every $i\in\left\{  1,2,\ldots,N\right\}  $ and every
$k\in\left\{  0,1,\ldots,n-1\right\}  $,%
\begin{equation}
\text{the pair }\left(  F_{i,k},F_{i,k+1}\right)  \text{ is an arc of the path
}\pi_{ij_{i}}. \label{11.Fik1}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.Fik1}):} Let $i\in\left\{  1,2,\ldots
,N\right\}  $. Let $k\in\left\{  0,1,\ldots,n-1\right\}  $. Then, both
$F_{i,k}$ and $F_{i,k+1}$ are well-defined points on the path $\pi_{ij_{i}}$
(by the definition of $F_{i,k}$ and $F_{i,k+1}$). From $k\in\left\{
0,1,\ldots,n-1\right\}  $, we obtain $k+1\in\left\{  1,2,\ldots,n\right\}
\subseteq\left\{  0,1,\ldots,n\right\}  $.
\par
We know that $F_{i,k}$ is the unique point $F$ on the path $\pi_{ij_{i}}$ such
that $\mathbf{d}\left(  F\right)  =k$ (according to the definition of
$F_{i,k}$). Thus, $F_{i,k}$ is a point on the path $\pi_{ij_{i}}$ and
satisfies $\mathbf{d}\left(  F_{i,k}\right)  =k$. We have $\mathbf{d}\left(
F_{i,k}\right)  =k\neq n=\mathbf{d}\left(  Q_{j_{i}}\right)  $ (because
$\mathbf{d}\left(  Q_{j_{i}}\right)  =n$ (by (\ref{11.dQj}), applied to
$j=j_{i}$)), and thus $F_{i,k}\neq Q_{j_{i}}$. Therefore, $F_{i,k}$ is not the
terminus of the path $\pi_{ij_{i}}$ (since the terminus of the path
$\pi_{ij_{i}}$ is $Q_{j_{i}}$). Hence, the next point after $F_{i,k}$ on the
path $\pi_{ij_{i}}$ is well-defined. Let $F^{\prime}$ denote this next point.
\par
Clearly, $\left(  F_{i,k},F^{\prime}\right)  $ is an arc of the path
$\pi_{ij_{i}}$ (since $F^{\prime}$ is the next point after $F_{i,k}$ on the
path $\pi_{ij_{i}}$). Thus, $\left(  F_{i,k},F^{\prime}\right)  $ is an arc of
the directed graph $G$ (since $\pi_{ij_{i}}$ is a path on this directed
graph). Hence, (\ref{11.dVU}) (applied to $U=F_{i,k}$ and $V=F^{\prime}$)
yields $\mathbf{d}\left(  F^{\prime}\right)  =\underbrace{\mathbf{d}\left(
F_{i,k}\right)  }_{=k}+1=k+1$. Also, $F^{\prime}$ lies on $\pi_{ij_{i}}$.
Hence, $F^{\prime}$ is a point $F$ on the path $\pi_{ij_{i}}$ such that
$\mathbf{d}\left(  F\right)  =k+1$. But we know that there exists exactly one
such point $F$ (according to (\ref{11.F}), applied to $k+1$ instead of $k$),
and we have denoted this point $F$ by $F_{i,k+1}$. Hence, $F^{\prime}$ is
$F_{i,k+1}$. Thus, $\left(  F_{i,k},F_{i,k+1}\right)  $ is an arc of the path
$\pi_{ij_{i}}$ (since $\left(  F_{i,k},F^{\prime}\right)  $ is an arc of the
path $\pi_{ij_{i}}$). This proves (\ref{11.Fik1}).} Therefore, for every
$i\in\left\{  1,2,\ldots,N\right\}  $ and every $k\in\left\{  0,1,\ldots
,n-1\right\}  $,
\begin{equation}
\text{the pair }\left(  F_{i,k},F_{i,k+1}\right)  \text{ is an arc of the
directed graph }G. \label{11.Fik}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.Fik}):} Let $i\in\left\{  1,2,\ldots
,N\right\}  $. Let $k\in\left\{  0,1,\ldots,n-1\right\}  $. Then,
(\ref{11.Fik1}) shows that the pair $\left(  F_{i,k},F_{i,k+1}\right)  $ is an
arc of the path $\pi_{ij_{i}}$. Thus, the pair $\left(  F_{i,k},F_{i,k+1}%
\right)  $ is an arc of the directed graph $G$ (since $\pi_{ij_{i}}$ is a path
on this directed graph). This proves (\ref{11.Fik}).}

We have%
\begin{equation}
\mathbf{t}\left(  Q_{1}\right)  <\mathbf{t}\left(  Q_{2}\right)
<\cdots<\mathbf{t}\left(  Q_{N}\right)  .\label{11.tQinc}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.tQinc}):} Let $j\in\left\{  1,2,\ldots
,N-1\right\}  $. We will now show that $\mathbf{t}\left(  Q_{j}\right)
<\mathbf{t}\left(  Q_{j+1}\right)  $.
\par
The definition of $Q_{j}$ yields $Q_{j}=\left(  n+\left(  j-1\right)
-\lambda_{j}^{\prime},-\left(  j-1\right)  +\lambda_{j}^{\prime}\right)  $, so
that $\mathbf{t}\left(  Q_{j}\right)  =\mathbf{t}\left(  \left(  n+\left(
j-1\right)  -\lambda_{j}^{\prime},-\left(  j-1\right)  +\lambda_{j}^{\prime
}\right)  \right)  =\left(  n+\left(  j-1\right)  -\lambda_{j}^{\prime
}\right)  -\left(  -\left(  j-1\right)  +\lambda_{j}^{\prime}\right)
=n+2\left(  j-1\right)  -2\lambda_{j}^{\prime}$. The same argument (applied to
$j+1$ instead of $j$) yields $\mathbf{t}\left(  Q_{j+1}\right)  =n+2\left(
\left(  j+1\right)  -1\right)  -2\lambda_{j+1}^{\prime}$. But $\lambda
^{\prime}$ is a partition, and thus we have $\lambda_{1}^{\prime}\geq
\lambda_{2}^{\prime}\geq\lambda_{3}^{\prime}\geq\cdots$. Hence, $\lambda
_{j}^{\prime}\geq\lambda_{j+1}^{\prime}$. Now,%
\[
\mathbf{t}\left(  Q_{j}\right)  =n+2\left(  \underbrace{j}_{<j+1}-1\right)
-2\underbrace{\lambda_{j}^{\prime}}_{\geq\lambda_{j+1}^{\prime}}<n+2\left(
\left(  j+1\right)  -1\right)  -2\lambda_{j+1}^{\prime}=\mathbf{t}\left(
Q_{j+1}\right)  .
\]
\par
Let us now forget that we fixed $j$. We thus have proven that $\mathbf{t}%
\left(  Q_{j}\right)  <\mathbf{t}\left(  Q_{j+1}\right)  $ for every
$j\in\left\{  1,2,\ldots,N-1\right\}  $. In other words, $\mathbf{t}\left(
Q_{1}\right)  <\mathbf{t}\left(  Q_{2}\right)  <\cdots<\mathbf{t}\left(
Q_{N}\right)  $. This proves (\ref{11.tQinc}).} Thus, the numbers
$\mathbf{t}\left(  Q_{1}\right)  ,\mathbf{t}\left(  Q_{2}\right)
,\ldots,\mathbf{t}\left(  Q_{N}\right)  $ are pairwise distinct. Hence, the
points $Q_{1},Q_{2},\ldots,Q_{N}$ are pairwise distinct.

Let us now come to the proof of Lemma \ref{lem.3.2.obv}.

\begin{proof}
[Proof of Lemma \ref{lem.3.2.obv}.]Let us first observe that%
\begin{equation}
\text{every intersection point }Y\text{ satisfies }\mathbf{d}\left(  Y\right)
\leq\mathbf{d}\left(  X\right)  . \label{11.dQdP}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.dQdP}):} We know (from the definition of
$X$) that $X$ is the intersection point $\left(  \alpha,\beta\right)  $ with
the pair $\left(  \alpha+\beta,\alpha-\beta\right)  $ lexicographically
maximal. In other words, $X$ is the intersection point $\left(  \alpha
,\beta\right)  $ with the pair $\left(  \mathbf{d}\left(  \left(  \alpha
,\beta\right)  \right)  ,\mathbf{t}\left(  \left(  \alpha,\beta\right)
\right)  \right)  $ lexicographically maximal (because every point $\left(
\alpha,\beta\right)  \in\mathbb{Z}^{2}$ satisfies $\mathbf{d}\left(  \left(
\alpha,\beta\right)  \right)  =\alpha+\beta$ and $\mathbf{t}\left(  \left(
\alpha,\beta\right)  \right)  =\alpha-\beta$). Hence, every intersection point
$Y$ satisfies $\left(  \mathbf{d}\left(  X\right)  ,\mathbf{t}\left(
X\right)  \right)  \geq\left(  \mathbf{d}\left(  Y\right)  ,\mathbf{t}\left(
Y\right)  \right)  $ in lexicographic order. Thus, every intersection point
$Y$ satisfies $\mathbf{d}\left(  X\right)  \geq\mathbf{d}\left(  Y\right)  $.
This proves (\ref{11.dQdP}).}

If $k\in\left\{  0,1,\ldots,n\right\}  $ is such that $k>\mathbf{d}\left(
X\right)  $, then any two distinct elements $\mathfrak{u}$ and $\mathfrak{v}$
of $\left\{  1,2,\ldots,N\right\}  $ satisfy%
\begin{equation}
\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  . \label{11.tFuk}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.tFuk}):} Let $k\in\left\{  0,1,\ldots
,n\right\}  $ be such that $k>\mathbf{d}\left(  X\right)  $. Let
$\mathfrak{u}$ and $\mathfrak{v}$ be two distinct elements of $\left\{
1,2,\ldots,N\right\}  $. We need to prove (\ref{11.tFuk}).
\par
Assume the contrary. Thus, (\ref{11.tFuk}) does not hold. In other words,
$\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  =\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  $. But $\mathbf{d}\left(  F_{\mathfrak{u}%
,k}\right)  =k$ (by (\ref{11.dFik}), applied to $i=\mathfrak{u}$) and
$\mathbf{d}\left(  F_{\mathfrak{v},k}\right)  =k$ (by (\ref{11.dFik}), applied
to $i=\mathfrak{v}$). Hence, $\mathbf{d}\left(  F_{\mathfrak{u},k}\right)
=k=\mathbf{d}\left(  F_{\mathfrak{v},k}\right)  $. Altogether, $\left(
\underbrace{\mathbf{d}\left(  F_{\mathfrak{u},k}\right)  }_{=\mathbf{d}\left(
F_{\mathfrak{v},k}\right)  },\underbrace{\mathbf{t}\left(  F_{\mathfrak{u}%
,k}\right)  }_{=\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  }\right)
=\left(  \mathbf{d}\left(  F_{\mathfrak{v},k}\right)  ,\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  \right)  $. Thus, (\ref{11.T1=T2}) (applied to
$T_{1}=F_{\mathfrak{u},k}$ and $T_{2}=F_{\mathfrak{v},k}$) yields
$F_{\mathfrak{u},k}=F_{\mathfrak{v},k}$.
\par
But $F_{\mathfrak{u},k}$ is the unique point $F$ on the path $\pi
_{\mathfrak{u}j_{\mathfrak{u}}}$ such that $\mathbf{d}\left(  F\right)  =k$
(according to the definition of $F_{\mathfrak{u},k}$). Hence, $F_{\mathfrak{u}%
,k}$ is a point $F$ on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ such that
$\mathbf{d}\left(  F\right)  =k$. In particular, $F_{\mathfrak{u},k}$ is a
point on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$. Similarly,
$F_{\mathfrak{v},k}$ is a point on the path $\pi_{\mathfrak{v}j_{\mathfrak{v}%
}}$. In other words, $F_{\mathfrak{u},k}$ is a point on the path
$\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ (since $F_{\mathfrak{u},k}%
=F_{\mathfrak{v},k}$). The point $F_{\mathfrak{u},k}$ thus lies on both paths
$\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$.
Hence, $F_{\mathfrak{u},k}$ is a point in which (at least) two of the paths
$\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect (namely, the paths
$\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}%
$). In other words, $F_{\mathfrak{u},k}$ is an intersection (since
$\mathfrak{u}$ and $\mathfrak{v}$ are distinct). Hence, (\ref{11.dQdP})
(applied to $Y=F_{\mathfrak{u},k}$) yields $\mathbf{d}\left(  F_{\mathfrak{u}%
,k}\right)  \leq\mathbf{d}\left(  X\right)  $. But this contradicts
$\mathbf{d}\left(  F_{\mathfrak{u},k}\right)  =k>\mathbf{d}\left(  X\right)
$. This contradiction proves that our assumption was wrong. Thus,
(\ref{11.tFuk}) is proven.} Moreover, if $k\in\left\{  0,1,\ldots,n\right\}  $
and if $\mathfrak{u}$ and $\mathfrak{v}$ are two elements of $\left\{
1,2,\ldots,N\right\}  $, then%
\begin{equation}
\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{u},k}\right)  +1. \label{11.tFvk}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.tFvk}):} Let $k\in\left\{  0,1,\ldots
,n\right\}  $, and let $\mathfrak{u}$ and $\mathfrak{v}$ be two elements of
$\left\{  1,2,\ldots,N\right\}  $. We need to prove that (\ref{11.tFvk})
holds.
\par
Assume the contrary. Thus, (\ref{11.tFvk}) does not hold. Thus, we have
$\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  =\mathbf{t}\left(
F_{\mathfrak{u},k}\right)  +1$. But (\ref{11.tTdT}) (applied to
$T=F_{\mathfrak{v},k}$) yields $\mathbf{t}\left(  F_{\mathfrak{v},k}\right)
\equiv\mathbf{d}\left(  F_{\mathfrak{v},k}\right)  \operatorname{mod}2$.
Hence, $\mathbf{d}\left(  F_{\mathfrak{v},k}\right)  \equiv\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  =\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
+1\operatorname{mod}2$. But $\mathbf{d}\left(  F_{\mathfrak{v},k}\right)  =k$
(by (\ref{11.dFik}), applied to $i=\mathfrak{v}$) and thus $k=\mathbf{d}%
\left(  F_{\mathfrak{v},k}\right)  \equiv\mathbf{t}\left(  F_{\mathfrak{u}%
,k}\right)  +1\operatorname{mod}2$. However, (\ref{11.tTdT}) (applied to
$T=F_{\mathfrak{u},k}$) yields $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
\equiv\mathbf{d}\left(  F_{\mathfrak{u},k}\right)  \operatorname{mod}2$. Also,
$\mathbf{d}\left(  F_{\mathfrak{u},k}\right)  =k$ (by (\ref{11.dFik}), applied
to $i=\mathfrak{u}$), so that $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
\equiv\mathbf{d}\left(  F_{\mathfrak{u},k}\right)  =k\operatorname{mod}2$.
Thus, $k\equiv\underbrace{\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
}_{\equiv k\operatorname{mod}2}+1\operatorname{mod}2\equiv
k+1\operatorname{mod}2$. Subtracting $k$ from this congruence, we obtain
$0\equiv1\operatorname{mod}2$, which is absurd. Hence, we have obtained a
contradiction. Thus, our assumption was wrong, and (\ref{11.tFvk}) is proven.}

But recall that $\left(  j_{1},j_{2},\ldots,j_{N}\right)  $ is a permutation
of $\left\{  1,2,\ldots,N\right\}  $. Denote this permutation by $\mathbf{j}$.
Thus,
\begin{equation}
\mathbf{j}\left(  i\right)  =j_{i}\ \ \ \ \ \ \ \ \ \ \text{for every }%
i\in\left\{  1,2,\ldots,N\right\}  . \label{11.ji}%
\end{equation}
Now, for every $j\in\left\{  1,2,\ldots,N-1\right\}  $, we have%
\begin{equation}
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j\right)  ,k}\right)
\leq\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j+1\right)  ,k}\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }k\in\left\{  \mathbf{d}\left(  X\right)
,\mathbf{d}\left(  X\right)  +1,\ldots,n\right\}  . \label{11.tFinc1}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.tFinc1}):} Let $j\in\left\{
1,2,\ldots,N-1\right\}  $. Set $\mathfrak{u}=\mathbf{j}^{-1}\left(  j\right)
$ and $\mathfrak{v}=\mathbf{j}^{-1}\left(  j+1\right)  $. We need to prove
(\ref{11.tFinc1}).
\par
Let us (for the sake of contradiction) assume the contrary. Thus, not every
$k\in\left\{  \mathbf{d}\left(  X\right)  ,\mathbf{d}\left(  X\right)
+1,\ldots,n\right\}  $ satisfies $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j\right)  ,k}\right)  \leq\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j+1\right)  ,k}\right)  $. In other words, not every $k\in\left\{
\mathbf{d}\left(  X\right)  ,\mathbf{d}\left(  X\right)  +1,\ldots,n\right\}
$ satisfies $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  \leq\mathbf{t}%
\left(  F_{\mathfrak{v},k}\right)  $ (because $\mathfrak{u}=\mathbf{j}%
^{-1}\left(  j\right)  $ and $\mathfrak{v}=\mathbf{j}^{-1}\left(  j+1\right)
$). In other words, there exists a $k\in\left\{  \mathbf{d}\left(  X\right)
,\mathbf{d}\left(  X\right)  +1,\ldots,n\right\}  $ such that $\mathbf{t}%
\left(  F_{\mathfrak{u},k}\right)  >\mathbf{t}\left(  F_{\mathfrak{v}%
,k}\right)  $. Let $\ell$ be the \textbf{highest} such $k$. Thus, $\ell$ is a
$k\in\left\{  \mathbf{d}\left(  X\right)  ,\mathbf{d}\left(  X\right)
+1,\ldots,n\right\}  $ such that $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
>\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  $. Hence, $\ell$ belongs to
$\left\{  \mathbf{d}\left(  X\right)  ,\mathbf{d}\left(  X\right)
+1,\ldots,n\right\}  $ and satisfies $\mathbf{t}\left(  F_{\mathfrak{u},\ell
}\right)  >\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  $. We have
$\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)  \geq\mathbf{t}\left(
F_{\mathfrak{v},\ell}\right)  +1$ (since $\mathbf{t}\left(  F_{\mathfrak{u}%
,\ell}\right)  $ and $\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  $ are
integers and satisfy $\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)
>\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  $). In other words,
$\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  +1\leq\mathbf{t}\left(
F_{\mathfrak{u},\ell}\right)  $.
\par
Let us first assume (for the sake of contradiction) that $\ell=n$. Then,
$F_{\mathfrak{u},\ell}=F_{\mathfrak{u},n}=Q_{j_{\mathfrak{u}}}$ (by
(\ref{11.Fin}), applied to $i=\mathfrak{u}$). But the definition of
$\mathbf{j}\left(  \mathfrak{u}\right)  $ yields $\mathbf{j}\left(
\mathfrak{u}\right)  =j_{\mathfrak{u}}$, so that $j_{\mathfrak{u}}%
=\mathbf{j}\left(  \mathfrak{u}\right)  =j$ (since $\mathfrak{u}%
=\mathbf{j}^{-1}\left(  j\right)  $) and thus $Q_{j_{\mathfrak{u}}}=Q_{j}$.
Also, from $\ell=n$, we obtain $F_{\mathfrak{v},\ell}=F_{\mathfrak{v}%
,n}=Q_{j_{\mathfrak{v}}}$ (by (\ref{11.Fin}), applied to $i=\mathfrak{v}$).
But the definition of $\mathbf{j}\left(  \mathfrak{v}\right)  $ yields
$\mathbf{j}\left(  \mathfrak{v}\right)  =j_{\mathfrak{v}}$, so that
$j_{\mathfrak{v}}=\mathbf{j}\left(  \mathfrak{v}\right)  =j+1$ (since
$\mathfrak{v}=\mathbf{j}^{-1}\left(  j+1\right)  $) and thus
$Q_{j_{\mathfrak{v}}}=Q_{j+1}$. But $\mathbf{t}\left(  Q_{j}\right)
<\mathbf{t}\left(  Q_{j+1}\right)  $ (by (\ref{11.tQinc})). Now,
$\mathbf{t}\left(  \underbrace{F_{\mathfrak{u},\ell}}_{=Q_{j_{\mathfrak{u}}%
}=Q_{j}}\right)  =\mathbf{t}\left(  Q_{j}\right)  <\mathbf{t}\left(
Q_{j+1}\right)  $ contradicts $\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)
>\mathbf{t}\left(  \underbrace{F_{\mathfrak{v},\ell}}_{=Q_{j_{\mathfrak{v}}%
}=Q_{j+1}}\right)  =\mathbf{t}\left(  Q_{j+1}\right)  $. This contradiction
proves that our assumption (that $\ell=n$) was wrong. Hence, we cannot have
$\ell=n$.
\par
We have $\mathbf{d}\left(  X\right)  \in\left\{  0,1,\ldots,n\right\}  $ (by
(\ref{11.dU}), applied to $U=X$), thus $0\leq\mathbf{d}\left(  X\right)  $. We
have $\ell\in\left\{  \mathbf{d}\left(  X\right)  ,\mathbf{d}\left(  X\right)
+1,\ldots,n\right\}  $, thus $\mathbf{d}\left(  X\right)  \leq\ell\leq n$.
Thus, $\ell<n$ (since $\ell\leq n$ but not $\ell=n$) and $0\leq\mathbf{d}%
\left(  X\right)  \leq\ell$. Hence, $0\leq\ell<n$, so that $\ell\in\left\{
0,1,\ldots,n-1\right\}  $ and thus $\ell+1\in\left\{  1,2,\ldots,n\right\}
\subseteq\left\{  0,1,\ldots,n\right\}  $, so that $\ell+1\leq n$. Moreover,
$\ell+1\in\left\{  \mathbf{d}\left(  X\right)  ,\mathbf{d}\left(  X\right)
+1,\ldots,n\right\}  $ (since $\mathbf{d}\left(  X\right)  \leq\ell\leq\ell+1$
and $\ell+1\leq n$).
\par
But $\ell\in\left\{  0,1,\ldots,n-1\right\}  $. Thus, (\ref{11.Fik}) (applied
to $k=\mathfrak{u}$ and $i=\ell$) shows that the pair $\left(  F_{\mathfrak{u}%
,\ell},F_{\mathfrak{u},\ell+1}\right)  $ is an arc of the directed graph $G$.
Therefore, (\ref{11.tVU}) (applied to $U=F_{\mathfrak{u},\ell}$ and
$V=F_{\mathfrak{u},\ell+1}$) shows that $\mathbf{t}\left(  F_{\mathfrak{u}%
,\ell}\right)  -1\leq\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)
\leq\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)  +1$. The same argument
(but with every $\mathfrak{u}$ replaced by $\mathfrak{v}$) yields
$\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  -1\leq\mathbf{t}\left(
F_{\mathfrak{v},\ell+1}\right)  \leq\mathbf{t}\left(  F_{\mathfrak{v},\ell
}\right)  +1$. Thus, $\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)
\leq\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  +1\leq\mathbf{t}\left(
F_{\mathfrak{u},\ell}\right)  \leq\mathbf{t}\left(  F_{\mathfrak{u},\ell
+1}\right)  +1$ (since $\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)
-1\leq\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  $). Combined with
$\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{u},\ell+1}\right)  +1$ (which is a consequence of (\ref{11.tFvk}%
), applied to $\ell+1$ instead of $k$), this yields $\mathbf{t}\left(
F_{\mathfrak{v},\ell+1}\right)  <\mathbf{t}\left(  F_{\mathfrak{u},\ell
+1}\right)  +1$. Since $\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  $
and $\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  +1$ are integers, this
yields $\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  \leq\left(
\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  +1\right)  -1=\mathbf{t}%
\left(  F_{\mathfrak{u},\ell+1}\right)  $.
\par
We have $\mathbf{d}\left(  X\right)  \leq\ell<\ell+1$ and thus $\ell
+1>\mathbf{d}\left(  X\right)  $. Hence, (\ref{11.tFuk}) (applied to
$k=\ell+1$) yields $\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)
\neq\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  $. In other words,
$\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{u},\ell+1}\right)  $. Combined with $\mathbf{t}\left(
F_{\mathfrak{v},\ell+1}\right)  \leq\mathbf{t}\left(  F_{\mathfrak{u},\ell
+1}\right)  $, this yields $\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)
<\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  $. In other words,
$\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  >\mathbf{t}\left(
F_{\mathfrak{v},\ell+1}\right)  $. Hence, $\ell+1$ is a $k\in\left\{
\mathbf{d}\left(  X\right)  ,\mathbf{d}\left(  X\right)  +1,\ldots,n\right\}
$ such that $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  >\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  $. Since the highest such $k$ is $\ell$ (by the
definition of $\ell$), this yields that $\ell+1\leq\ell$. But this contradicts
$\ell+1>\ell$. This contradiction shows that our assumption was wrong. Hence,
(\ref{11.tFinc1}) is proven.} Consequently, if $k\in\left\{  0,1,\ldots
,n\right\}  $ is such that $k>\mathbf{d}\left(  X\right)  $, then%
\begin{equation}
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  1\right)  ,k}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  2\right)  ,k}\right)
<\cdots<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  N\right)  ,k}\right)  .
\label{11.tFstrinc1}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.tFstrinc1}):} Let $k\in\left\{
0,1,\ldots,n\right\}  $ be such that $k>\mathbf{d}\left(  X\right)  $. Let
$j\in\left\{  1,2,\ldots,N-1\right\}  $. Since $k\geq\mathbf{d}\left(
X\right)  $ (because $k>\mathbf{d}\left(  X\right)  $) and $k\leq n$ (since
$k\in\left\{  0,1,\ldots,n\right\}  $), we have $k\in\left\{  \mathbf{d}%
\left(  X\right)  ,\mathbf{d}\left(  X\right)  +1,\ldots,n\right\}  $. Hence,
(\ref{11.tFinc1}) yields $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j\right)  ,k}\right)  \leq\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j+1\right)  ,k}\right)  $. But $\mathbf{j}\left(  \mathbf{j}^{-1}\left(
j\right)  \right)  =j\neq j+1=\mathbf{j}\left(  \mathbf{j}^{-1}\left(
j+1\right)  \right)  $, so that $\mathbf{j}^{-1}\left(  j\right)
\neq\mathbf{j}^{-1}\left(  j+1\right)  $. In other words, the positive
integers $\mathbf{j}^{-1}\left(  j\right)  $ and $\mathbf{j}^{-1}\left(
j+1\right)  $ are distinct. Thus, (\ref{11.tFuk}) (applied to $\mathfrak{u}%
=\mathbf{j}^{-1}\left(  j\right)  $ and $\mathfrak{v}=\mathbf{j}^{-1}\left(
j+1\right)  $) yields $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j\right)
,k}\right)  \neq\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j+1\right)
,k}\right)  $. Combined with $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j\right)  ,k}\right)  \leq\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j+1\right)  ,k}\right)  $, this yields $\mathbf{t}\left(  F_{\mathbf{j}%
^{-1}\left(  j\right)  ,k}\right)  <\mathbf{t}\left(  F_{\mathbf{j}%
^{-1}\left(  j+1\right)  ,k}\right)  $.
\par
Now, let us forget that we fixed $j\in\left\{  1,2,\ldots,N-1\right\}  $.
Thus, we have shown that $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j\right)  ,k}\right)  <\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j+1\right)
,k}\right)  $ for every $j\in\left\{  1,2,\ldots,N-1\right\}  $. In other
words, $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  1\right)  ,k}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  2\right)  ,k}\right)
<\cdots<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  N\right)  ,k}\right)  $.
This proves (\ref{11.tFstrinc1}).}

Next, we notice that%
\begin{equation}
\mathbf{d}\left(  X\right)  \in\left\{  0,1,\ldots,n-1\right\}  .
\label{11.dX}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.dX}):} The point $X$ is an intersection
point (in fact, $X$ is the intersection point $\left(  \alpha,\beta\right)  $
with the pair $\left(  \alpha+\beta,\alpha-\beta\right)  $ lexicographically
maximal). In other words, $X$ is a point in which (at least) two of the paths
$\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect. In other words, at
least two of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$
intersect at $X$. In other words, there exist two distinct elements
$\mathfrak{u}$ and $\mathfrak{v}$ of $\left\{  1,2,\ldots,N\right\}  $ such
that the paths $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}%
j_{\mathfrak{v}}}$ intersect at $X$. Consider these $\mathfrak{u}$ and
$\mathfrak{v}$. We can WLOG assume that $\mathbf{j}\left(  \mathfrak{u}%
\right)  \leq\mathbf{j}\left(  \mathfrak{v}\right)  $ (since otherwise, we can
just switch $\mathfrak{u}$ with $\mathfrak{v}$). Assume this. We have
$\mathfrak{u}\neq\mathfrak{v}$ (since $\mathfrak{u}$ and $\mathfrak{v}$ are
distinct), and thus $\mathbf{j}\left(  \mathfrak{u}\right)  \neq
\mathbf{j}\left(  \mathfrak{v}\right)  $ (since $\mathbf{j}$ is injective
(since $\mathbf{j}$ is a permutation)). Thus, $\mathbf{j}\left(
\mathfrak{u}\right)  <\mathbf{j}\left(  \mathfrak{v}\right)  $ (since
$\mathbf{j}\left(  \mathfrak{u}\right)  \leq\mathbf{j}\left(  \mathfrak{v}%
\right)  $).
\par
The point $X$ lies on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ (since the
paths $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}%
j_{\mathfrak{v}}}$ intersect at $X$). Hence, (\ref{11.dU}) (applied to
$i=\mathfrak{u}$ and $U=X$) yields $\mathbf{d}\left(  X\right)  \in\left\{
0,1,\ldots,n\right\}  $.
\par
We now assume (for the sake of contradiction) that $\mathbf{d}\left(
X\right)  =n$.
\par
Recall that there exists exactly one point $F$ on the path $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$ such that $\mathbf{d}\left(  F\right)  =n$ (according to
(\ref{11.F}), applied to $i=\mathfrak{u}$ and $k=n$); this point is denoted by
$F_{\mathfrak{u},n}$. Thus, $F_{\mathfrak{u},n}$ is the unique point $F$ on
the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ such that $\mathbf{d}\left(
F\right)  =n$. Since $X$ is a point $F$ on the path $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$ such that $\mathbf{d}\left(  F\right)  =n$ (because $X$
lies on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and satisfies
$\mathbf{d}\left(  X\right)  =n$), this yields that $X$ is $F_{\mathfrak{u}%
,n}$. In other words, $X=F_{\mathfrak{u},n}$. But (\ref{11.Fin}) (applied to
$i=\mathfrak{u}$) yields $F_{\mathfrak{u},n}=Q_{j_{\mathfrak{u}}}$. But the
definition of $\mathbf{j}$ yields $\mathbf{j}\left(  \mathfrak{u}\right)
=j_{\mathfrak{u}}$. Hence, $Q_{\mathbf{j}\left(  \mathfrak{u}\right)
}=Q_{j_{\mathfrak{u}}}$, so that $X=F_{\mathfrak{u},n}=Q_{j_{\mathfrak{u}}%
}=Q_{\mathbf{j}\left(  \mathfrak{u}\right)  }$. The same argument (but with
$\mathfrak{u}$ replaced by $\mathfrak{v}$) yields $X=Q_{\mathbf{j}\left(
\mathfrak{v}\right)  }$.
\par
But (\ref{11.tQinc}) yields $\mathbf{t}\left(  Q_{1}\right)  <\mathbf{t}%
\left(  Q_{2}\right)  <\cdots<\mathbf{t}\left(  Q_{N}\right)  $. In other
words, if $\mathfrak{a}\in\left\{  1,2,\ldots,N\right\}  $ and $\mathfrak{b}%
\in\left\{  1,2,\ldots,N\right\}  $ satisfy $\mathfrak{a}<\mathfrak{b}$, then
$\mathbf{t}\left(  Q_{\mathfrak{a}}\right)  <\mathbf{t}\left(  Q_{\mathfrak{b}%
}\right)  $. Applying this to $\mathfrak{a}=\mathbf{j}\left(  \mathfrak{u}%
\right)  $ and $\mathfrak{b}=\mathbf{j}\left(  \mathfrak{v}\right)  $, we
obtain $\mathbf{t}\left(  Q_{\mathbf{j}\left(  \mathfrak{u}\right)  }\right)
<\mathbf{t}\left(  Q_{\mathbf{j}\left(  \mathfrak{v}\right)  }\right)  $
(since $\mathbf{j}\left(  \mathfrak{u}\right)  <\mathbf{j}\left(
\mathfrak{v}\right)  $). But this contradicts $\mathbf{t}\left(
\underbrace{Q_{\mathbf{j}\left(  \mathfrak{u}\right)  }}_{=X=Q_{\mathbf{j}%
\left(  \mathfrak{v}\right)  }}\right)  =\mathbf{t}\left(  Q_{\mathbf{j}%
\left(  \mathfrak{v}\right)  }\right)  $. This contradiction proves that our
assumption (that $\mathbf{d}\left(  X\right)  =n$) was wrong. Hence, we cannot
have $\mathbf{d}\left(  X\right)  =n$. In other words, we have $\mathbf{d}%
\left(  X\right)  \neq n$. Combined with $\mathbf{d}\left(  X\right)
\in\left\{  0,1,\ldots,n\right\}  $, this yields $\mathbf{d}\left(  X\right)
\in\left\{  0,1,\ldots,n\right\}  \setminus\left\{  n\right\}  =\left\{
0,1,\ldots,n-1\right\}  $. This proves (\ref{11.dX}).} Now, if $\mathfrak{u}%
\in\left\{  1,2,\ldots,N\right\}  $ and $\mathfrak{v}\in\left\{
1,2,\ldots,N\right\}  $ are such that $F_{\mathfrak{u},\mathbf{d}\left(
X\right)  }=F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }$, then%
\begin{equation}
\mathbf{j}\left(  \mathfrak{v}\right)  \leq\mathbf{j}\left(  \mathfrak{u}%
\right)  +1. \label{11.jvju}%
\end{equation}
\footnote{\textit{Proof of (\ref{11.jvju}):} Let $\mathfrak{u}\in\left\{
1,2,\ldots,N\right\}  $ and $\mathfrak{v}\in\left\{  1,2,\ldots,N\right\}  $
be such that $F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }=F_{\mathfrak{v}%
,\mathbf{d}\left(  X\right)  }$. We need to prove that (\ref{11.jvju}) holds.
\par
In fact, let us assume the contrary. Then, (\ref{11.jvju}) does not hold. In
other words, $\mathbf{j}\left(  \mathfrak{v}\right)  >\mathbf{j}\left(
\mathfrak{u}\right)  +1$. Hence, $\mathbf{j}\left(  \mathfrak{v}\right)
>\mathbf{j}\left(  \mathfrak{u}\right)  +1>\mathbf{j}\left(  \mathfrak{u}%
\right)  $, so that $\mathbf{j}\left(  \mathfrak{v}\right)  \neq
\mathbf{j}\left(  \mathfrak{u}\right)  $ and thus $\mathfrak{v}\neq
\mathfrak{u}$. Hence, $\mathfrak{u}\neq\mathfrak{v}$.
\par
We have $\mathbf{j}\left(  \mathfrak{u}\right)  \in\left\{  1,2,\ldots
,N\right\}  $, thus $\mathbf{j}\left(  \mathfrak{u}\right)  \geq1$. We have
$\mathbf{j}\left(  \mathfrak{v}\right)  \in\left\{  1,2,\ldots,N\right\}  $,
thus $\mathbf{j}\left(  \mathfrak{v}\right)  \leq N$. Hence, $N\geq
\mathbf{j}\left(  \mathfrak{v}\right)  >\mathbf{j}\left(  \mathfrak{u}\right)
+1>\mathbf{j}\left(  \mathfrak{u}\right)  $, and thus $\mathbf{j}\left(
\mathfrak{u}\right)  <N$. Therefore, $\mathbf{j}\left(  \mathfrak{u}\right)
\in\left\{  1,2,\ldots,N-1\right\}  $ (since $\mathbf{j}\left(  \mathfrak{u}%
\right)  \geq1$).
\par
$>\mathbf{j}\left(  \mathfrak{u}\right)  $, we conclude that $\mathbf{j}%
\left(  \mathfrak{u}\right)  +1\in\left\{  1,2,\ldots,N\right\}  $ (since both
$\mathbf{j}\left(  \mathfrak{v}\right)  $ and $\mathbf{j}\left(
\mathfrak{u}\right)  $ belong to $\left\{  1,2,\ldots,N\right\}  $). Hence,
$\mathbf{j}^{-1}\left(  \mathbf{j}\left(  \mathfrak{u}\right)  +1\right)  $ is
a well-defined element of $\left\{  1,2,\ldots,N\right\}  $. Denote this
element by $\mathfrak{w}$. Thus, $\mathfrak{w}=\mathbf{j}^{-1}\left(
\mathbf{j}\left(  \mathfrak{u}\right)  +1\right)  $.
\par
From (\ref{11.dX}), we obtain $\mathbf{d}\left(  X\right)  \in\left\{
0,1,\ldots,n-1\right\}  $, thus $\mathbf{d}\left(  X\right)  +1\in\left\{
1,2,\ldots,n\right\}  \subseteq\left\{  0,1,\ldots,n\right\}  $. Let
$k=\mathbf{d}\left(  X\right)  +1$. Then, $k=\mathbf{d}\left(  X\right)
+1\in\left\{  0,1,\ldots,n\right\}  $ and $k=\mathbf{d}\left(  X\right)
+1>\mathbf{d}\left(  X\right)  $. Thus, (\ref{11.tFstrinc1}) yields
$\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  1\right)  ,k}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  2\right)  ,k}\right)
<\cdots<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  N\right)  ,k}\right)  $.
In other words, any $\mathfrak{a}\in\left\{  1,2,\ldots,N\right\}  $ and
$\mathfrak{b}\in\left\{  1,2,\ldots,N\right\}  $ satisfying $\mathfrak{a}%
<\mathfrak{b}$ must satisfy%
\begin{equation}
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  \mathfrak{a}\right)  ,k}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  \mathfrak{b}\right)  ,k}\right)
. \label{11.jvju.pf.1}%
\end{equation}
\par
We know (from (\ref{11.Fik}), applied to $\mathfrak{u}$ and $\mathbf{d}\left(
X\right)  $ instead of $i$ and $k$) that the pair $\left(  F_{\mathfrak{u}%
,\mathbf{d}\left(  X\right)  },F_{\mathfrak{u},\mathbf{d}\left(  X\right)
+1}\right)  $ is an arc of the directed graph $G$. Hence, (\ref{11.tVU})
(applied to $\left(  U,V\right)  =\left(  F_{\mathfrak{u},\mathbf{d}\left(
X\right)  },F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}\right)  $) yields
$\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }\right)
-1\leq\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)
+1}\right)  \leq\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)
}\right)  +1$. In other words,
\[
\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }\right)
-1\leq\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  \leq\mathbf{t}\left(
F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }\right)  +1
\]
(since $k=\mathbf{d}\left(  X\right)  +1$). The same argument (but with
$\mathfrak{u}$ replaced by $\mathfrak{v}$) yields%
\[
\mathbf{t}\left(  F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }\right)
-1\leq\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  \leq\mathbf{t}\left(
F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }\right)  +1.
\]
Hence, $\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  \leq\mathbf{t}\left(
F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }\right)  +1$, so that
$\mathbf{t}\left(  F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }\right)
\geq\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  -1$, so that $\mathbf{t}%
\left(  \underbrace{F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }%
}_{=F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }}\right)  =\mathbf{t}\left(
F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }\right)  \geq\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  -1$. But from $\mathbf{t}\left(  F_{\mathfrak{u}%
,\mathbf{d}\left(  X\right)  }\right)  -1\leq\mathbf{t}\left(  F_{\mathfrak{u}%
,k}\right)  $, we obtain $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
\geq\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }\right)
-1$, so that $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  +1\geq
\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }\right)
\geq\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  -1$.
\par
On the other hand, $\mathbf{j}\left(  \mathfrak{u}\right)  <\mathbf{j}\left(
u\right)  +1$. Hence, (\ref{11.jvju.pf.1}) (applied to $\mathfrak{a}%
=\mathbf{j}\left(  \mathfrak{u}\right)  $ and $\mathfrak{b}=\mathbf{j}\left(
\mathfrak{u}\right)  +1$) yields $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
\mathbf{j}\left(  \mathfrak{u}\right)  \right)  ,k}\right)  <\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  \mathbf{j}\left(  \mathfrak{u}\right)  +1\right)
,k}\right)  $. In other words, $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
<\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  $ (since $\mathbf{j}^{-1}\left(
\mathbf{j}\left(  \mathfrak{u}\right)  \right)  =\mathfrak{u}$ and
$\mathbf{j}^{-1}\left(  \mathbf{j}\left(  \mathfrak{u}\right)  +1\right)
=\mathfrak{w}$). Thus, $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
\leq\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  -1$ (since $\mathbf{t}\left(
F_{\mathfrak{u},k}\right)  $ and $\mathbf{t}\left(  F_{\mathfrak{w},k}\right)
$ are integers). Thus, $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)
+1\leq\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  $, so that $\mathbf{t}%
\left(  F_{\mathfrak{w},k}\right)  \geq\mathbf{t}\left(  F_{\mathfrak{u}%
,k}\right)  +1\geq\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  -1$.
\par
But we know that $\mathbf{j}\left(  \mathfrak{v}\right)  >\mathbf{j}\left(
\mathfrak{u}\right)  +1$, so that $\mathbf{j}\left(  \mathfrak{u}\right)
+1<\mathbf{j}\left(  \mathfrak{v}\right)  $. Hence, (\ref{11.jvju.pf.1})
(applied to $\mathfrak{a}=\mathbf{j}\left(  \mathfrak{u}\right)  +1$ and
$\mathfrak{b}=\mathbf{j}\left(  \mathfrak{v}\right)  $) yields $\mathbf{t}%
\left(  F_{\mathbf{j}^{-1}\left(  \mathbf{j}\left(  \mathfrak{u}\right)
+1\right)  ,k}\right)  <\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
\mathbf{j}\left(  \mathfrak{v}\right)  \right)  ,k}\right)  $. In other words,
$\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  <\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  $ (since $\mathbf{j}^{-1}\left(  \mathbf{j}\left(
\mathfrak{u}\right)  +1\right)  =\mathfrak{w}$ and $\mathbf{j}^{-1}\left(
\mathbf{j}\left(  \mathfrak{v}\right)  \right)  =\mathfrak{v}$). Thus,
$\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  \leq\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  -1$ (since $\mathbf{t}\left(  F_{\mathfrak{w}%
,k}\right)  $ and $\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  $ are
integers). Combined with $\mathbf{t}\left(  F_{\mathfrak{w},k}\right)
\geq\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  -1$, this yields
$\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  =\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  -1$. That is, $\mathbf{t}\left(  F_{\mathfrak{v}%
,k}\right)  =\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  +1$.
\par
But (\ref{11.tFvk}) (applied to $\mathfrak{w}$ instead of $\mathfrak{u}$)
yields $\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{w},k}\right)  +1$. This contradicts $\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  =\mathbf{t}\left(  F_{\mathfrak{w},k}\right)  +1$.
This contradiction shows that our assumption was wrong. Hence, (\ref{11.jvju})
is proven.}

We now proceed to the proofs of the three parts of Lemma \ref{lem.3.2.obv}:

\textbf{(a)} We know that $X$ is an intersection point. Hence, (at least) two
of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect at $X$.
Therefore, in order to prove Lemma \ref{lem.3.2.obv} \textbf{(a)}, we only
need to show that no more than two of the paths $\pi_{1j_{1}},\pi_{2j_{2}%
},\ldots,\pi_{Nj_{N}}$ intersect at $X$. Let us prove this.

Indeed, let us assume the contrary (for the sake of contradiction). Thus, more
than two of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$
intersect at $X$. Hence, at least three of the paths $\pi_{1j_{1}},\pi
_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect at $X$. In other words, at least
three of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ pass
through $X$. In other words, there exist three pairwise distinct elements
$\mathfrak{u}$, $\mathfrak{v}$ and $\mathfrak{w}$ of $\left\{  1,2,\ldots
,N\right\}  $ such that the paths $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$,
$\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ and $\pi_{\mathfrak{w}j_{\mathfrak{w}}}$
pass through $X$. Consider these $\mathfrak{u}$, $\mathfrak{v}$ and
$\mathfrak{w}$. We can assume WLOG that $\mathbf{j}\left(  \mathfrak{u}%
\right)  \leq\mathbf{j}\left(  \mathfrak{v}\right)  \leq\mathbf{j}\left(
\mathfrak{w}\right)  $ (since otherwise, we can just permute $\mathfrak{u}$,
$\mathfrak{v}$ and $\mathfrak{w}$). Assume this. The map $\mathbf{j}$ is a
permutation, and thus injective. Hence, $\mathbf{j}\left(  \mathfrak{u}%
\right)  \neq\mathbf{j}\left(  \mathfrak{v}\right)  $ (since $\mathfrak{u}%
\neq\mathfrak{v}$ (since $\mathfrak{u}$, $\mathfrak{v}$ and $\mathfrak{w}$ are
pairwise distinct)), so that $\mathbf{j}\left(  \mathfrak{u}\right)
<\mathbf{j}\left(  \mathfrak{v}\right)  $ (since $\mathbf{j}\left(
\mathfrak{u}\right)  \leq\mathbf{j}\left(  \mathfrak{v}\right)  $). Thus,
$\mathbf{j}\left(  \mathfrak{u}\right)  \leq\mathbf{j}\left(  \mathfrak{v}%
\right)  -1$ (since $\mathbf{j}\left(  \mathfrak{u}\right)  $ and
$\mathbf{j}\left(  \mathfrak{v}\right)  $ are integers). In other words,
$\mathbf{j}\left(  \mathfrak{u}\right)  +1\leq\mathbf{j}\left(  \mathfrak{v}%
\right)  $.

From (\ref{11.dX}), we obtain $\mathbf{d}\left(  X\right)  \in\left\{
0,1,\ldots,n-1\right\}  \subseteq\left\{  0,1,\ldots,n\right\}  $. Thus, there
exists exactly one point $F$ on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$
such that $\mathbf{d}\left(  F\right)  =\mathbf{d}\left(  X\right)  $
(according to (\ref{11.F}), applied to $i=\mathfrak{u}$ and $k=\mathbf{d}%
\left(  X\right)  $); this point is denoted by $F_{\mathfrak{u},\mathbf{d}%
\left(  X\right)  }$. Thus, $F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }$ is
the unique point $F$ on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ such
that $\mathbf{d}\left(  F\right)  =\mathbf{d}\left(  X\right)  $. Since $X$ is
a point $F$ on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ such that
$\mathbf{d}\left(  F\right)  =\mathbf{d}\left(  X\right)  $ (because $X$ lies
on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and satisfies $\mathbf{d}%
\left(  X\right)  =\mathbf{d}\left(  X\right)  $), this yields that $X$ is
$F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }$. In other words,
$X=F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }$. The same reasoning (applied
to $\mathfrak{v}$ instead of $\mathfrak{u}$) yields $X=F_{\mathfrak{v}%
,\mathbf{d}\left(  X\right)  }$. Thus, $F_{\mathfrak{u},\mathbf{d}\left(
X\right)  }=X=F_{\mathfrak{v},\mathbf{d}\left(  X\right)  }$. Hence,
(\ref{11.jvju}) yields $\mathbf{j}\left(  \mathfrak{v}\right)  \leq
\mathbf{j}\left(  \mathfrak{u}\right)  +1$. Combined with $\mathbf{j}\left(
\mathfrak{u}\right)  +1\leq\mathbf{j}\left(  \mathfrak{v}\right)  $, this
yields $\mathbf{j}\left(  \mathfrak{v}\right)  =\mathbf{j}\left(
\mathfrak{u}\right)  +1$. The same argument (but applied to $\mathfrak{w}$
instead of $\mathfrak{v}$) shows that $\mathbf{j}\left(  \mathfrak{w}\right)
=\mathbf{j}\left(  \mathfrak{u}\right)  +1$. Thus, $\mathbf{j}\left(
\mathfrak{v}\right)  =\mathbf{j}\left(  \mathfrak{u}\right)  +1=\mathbf{j}%
\left(  \mathfrak{w}\right)  $, so that $\mathfrak{v}=\mathfrak{w}$ (since the
map $\mathbf{j}$ is injective). But the integers $\mathfrak{u}$,
$\mathfrak{v}$ and $\mathfrak{w}$ are pairwise distinct. Thus, $\mathfrak{v}%
\neq\mathfrak{w}$. This contradicts $\mathfrak{v}=\mathfrak{w}$. This
contradiction proves that our assumption was wrong. Hence, we have shown that
no more than two of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$
intersect at $X$. This completes the proof of Lemma \ref{lem.3.2.obv}
\textbf{(a)}.

\textbf{(b)} We know from Lemma \ref{lem.3.2.obv} \textbf{(a)} that exactly
two of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect at
$X$. We now must show that these two paths must end at two points of the form
$Q_{k}$ and $Q_{k+1}$ for some $k\in\left\{  1,2,\ldots,N-1\right\}  $.

Let $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}%
}}$ be these two paths, with $\mathfrak{u}$ and $\mathfrak{v}$ being distinct
elements of $\left\{  1,2,\ldots,N\right\}  $. Thus, the two paths
$\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$
intersect at $X$. In other words, the two paths $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ pass through $X$.
We can assume WLOG that $\mathbf{j}\left(  \mathfrak{u}\right)  \leq
\mathbf{j}\left(  \mathfrak{v}\right)  $ (since otherwise, we can just permute
$\mathfrak{u}$ and $\mathfrak{v}$). Assume this. The map $\mathbf{j}$ is a
permutation, and thus injective. Hence, $\mathbf{j}\left(  \mathfrak{u}%
\right)  \neq\mathbf{j}\left(  \mathfrak{v}\right)  $ (since $\mathfrak{u}%
\neq\mathfrak{v}$ (since $\mathfrak{u}$ and $\mathfrak{v}$ are distinct)).
Now, we have $\mathbf{j}\left(  \mathfrak{v}\right)  =\mathbf{j}\left(
\mathfrak{u}\right)  +1$. (This can be proven in exactly the same manner as we
proved it in the proof of Lemma \ref{lem.3.2.obv} \textbf{(a)}.) The
definition of $\mathbf{j}$ yields $\mathbf{j}\left(  \mathfrak{u}\right)
=j_{\mathfrak{u}}$ and $\mathbf{j}\left(  \mathfrak{v}\right)
=j_{\mathfrak{v}}$. Thus, $j_{\mathfrak{v}}=\mathbf{j}\left(  \mathfrak{v}%
\right)  =\underbrace{\mathbf{j}\left(  \mathfrak{u}\right)  }%
_{=j_{\mathfrak{u}}}+1=j_{\mathfrak{u}}+1$. But the path $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$ ends at the point $Q_{j_{\mathfrak{u}}}$ (according to the
definition of this path). The path $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ ends
at the point $Q_{j_{\mathfrak{v}}}$ (according to the definition of this
path). In other words, the path $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ ends at
the point $Q_{j_{\mathfrak{u}}+1}$ (since $j_{\mathfrak{v}}=j_{\mathfrak{u}%
}+1$). Hence, the paths $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and
$\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ end at the points $Q_{j_{\mathfrak{u}}}$
and $Q_{j_{\mathfrak{u}}+1}$. Hence, the paths $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ end at two points
of the form $Q_{k}$ and $Q_{k+1}$ for some $k\in\left\{  1,2,\ldots
,N-1\right\}  $ (namely, for $k=j_{\mathfrak{u}}$).

Now, recall that exactly two of the paths $\pi_{1j_{1}},\pi_{2j_{2}}%
,\ldots,\pi_{Nj_{N}}$ intersect at $X$ -- namely, the two paths $\pi
_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$. We
have shown that these two paths $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and
$\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ end at two points of the form $Q_{k}$ and
$Q_{k+1}$ for some $k\in\left\{  1,2,\ldots,N-1\right\}  $. In other words,
Lemma \ref{lem.3.2.obv} \textbf{(b)} is proven.

\textbf{(c)} Let $\left(  \alpha,\beta\right)  =X$.

We know from Lemma \ref{lem.3.2.obv} \textbf{(a)} that exactly two of the
paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect at $X$. Lemma
\ref{lem.3.2.obv} \textbf{(b)} furthermore shows that these two paths must end
at two points of the form $Q_{k}$ and $Q_{k+1}$ for some $k\in\left\{
1,2,\ldots,N-1\right\}  $. Let $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and
$\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ be these two paths, labelled in such a
way that $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ ends at $Q_{k}$ whereas
$\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ ends at $Q_{k+1}$ (where $k$ is as in the
previous sentence). Furthermore, consider the $k\in\left\{  1,2,\ldots
,N-1\right\}  $ for which this holds. From $k\in\left\{  1,2,\ldots
,N-1\right\}  $, we obtain $k\in\left\{  1,2,\ldots,N\right\}  $ and
$k+1\in\left\{  1,2,\ldots,N\right\}  $.

The path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ ends at the point
$Q_{j_{\mathfrak{u}}}$ (according to the definition of this path). In other
words,
\[
\left(  \text{the point at which the path }\pi_{\mathfrak{u}j_{\mathfrak{u}}%
}\text{ ends}\right)  =Q_{j_{\mathfrak{u}}}.
\]
On the other hand,%
\[
\left(  \text{the point at which the path }\pi_{\mathfrak{u}j_{\mathfrak{u}}%
}\text{ ends}\right)  =Q_{k}%
\]
(since the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ ends at $Q_{k}$).
Comparing these two equalities, we obtain $Q_{j_{\mathfrak{u}}}=Q_{k}$. From
this, we obtain $j_{\mathfrak{u}}=k$ (since the points $Q_{1},Q_{2}%
,\ldots,Q_{N}$ are pairwise distinct). The definition of $\mathbf{j}$ yields
$\mathbf{j}\left(  \mathfrak{u}\right)  =j_{\mathfrak{u}}=k$. Hence,
$\mathfrak{u}=\mathbf{j}^{-1}\left(  k\right)  $.

Furthermore, the path $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ ends at the point
$Q_{j_{\mathfrak{v}}}$ (according to the definition of this path). In other
words,
\[
\left(  \text{the point at which the path }\pi_{\mathfrak{v}j_{\mathfrak{v}}%
}\text{ ends}\right)  =Q_{j_{\mathfrak{v}}}.
\]
On the other hand,%
\[
\left(  \text{the point at which the path }\pi_{\mathfrak{v}j_{\mathfrak{v}}%
}\text{ ends}\right)  =Q_{k+1}%
\]
(since the path $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ ends at $Q_{k+1}$).
Comparing these two equalities, we obtain $Q_{j_{\mathfrak{v}}}=Q_{k+1}$. From
this, we obtain $j_{\mathfrak{v}}=k+1$ (since the points $Q_{1},Q_{2}%
,\ldots,Q_{N}$ are pairwise distinct). The definition of $\mathbf{j}$ yields
$\mathbf{j}\left(  \mathfrak{v}\right)  =j_{\mathfrak{v}}=k+1$. Hence,
$\mathfrak{v}=\mathbf{j}^{-1}\left(  k+1\right)  $.

Now, (\ref{11.dX}) yields $\mathbf{d}\left(  X\right)  \in\left\{
0,1,\ldots,n-1\right\}  $, whence $\mathbf{d}\left(  X\right)  +1\in\left\{
1,2,\ldots,n\right\}  \subseteq\left\{  0,1,\ldots,n\right\}  $. Hence,
(\ref{11.tFstrinc1}) (applied to $\mathbf{d}\left(  X\right)  +1$ instead of
$k$) shows that%
\[
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  1\right)  ,\mathbf{d}\left(
X\right)  +1}\right)  <\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  2\right)
,\mathbf{d}\left(  X\right)  +1}\right)  <\cdots<\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  N\right)  ,\mathbf{d}\left(  X\right)  +1}\right)
\]
(since $\mathbf{d}\left(  X\right)  +1>\mathbf{d}\left(  X\right)  $). In
other words,%
\[
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  r\right)  ,\mathbf{d}\left(
X\right)  +1}\right)  <\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  r+1\right)
,\mathbf{d}\left(  X\right)  +1}\right)
\]
for each $r\in\left\{  1,2,\ldots,N-1\right\}  $. Applying this to $r=k$, we
obtain%
\[
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  k\right)  ,\mathbf{d}\left(
X\right)  +1}\right)  <\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  k+1\right)
,\mathbf{d}\left(  X\right)  +1}\right)  .
\]
In view of $\mathfrak{u}=\mathbf{j}^{-1}\left(  k\right)  $ and $\mathfrak{v}%
=\mathbf{j}^{-1}\left(  k+1\right)  $, we can rewrite this as%
\begin{equation}
\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}\right)
<\mathbf{t}\left(  F_{\mathfrak{v},\mathbf{d}\left(  X\right)  +1}\right)  .
\label{pf.lem.3.2.obv.c.3}%
\end{equation}


On the other hand, we have $X=F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }$.
(This can be shown in the same way as we proved it during the proof of Lemma
\ref{lem.3.2.obv} \textbf{(a)}.) Hence, $F_{\mathfrak{u},\mathbf{d}\left(
X\right)  }=X=\left(  \alpha,\beta\right)  $ (since we have set $\left(
\alpha,\beta\right)  =X$).

Recall that $\mathbf{d}\left(  X\right)  \in\left\{  0,1,\ldots,n-1\right\}
$. Hence, (\ref{11.Fik}) (applied to $\mathfrak{u}$ and $\mathbf{d}\left(
X\right)  $ instead of $i$ and $k$) yields that the pair $\left(
F_{\mathfrak{u},\mathbf{d}\left(  X\right)  },F_{\mathfrak{u},\mathbf{d}%
\left(  X\right)  +1}\right)  $ is an arc of the directed graph $G$. In other
words, the pair $\left(  \left(  \alpha,\beta\right)  ,F_{\mathfrak{u}%
,\mathbf{d}\left(  X\right)  +1}\right)  $ is an arc of the directed graph $G$
(since $F_{\mathfrak{u},\mathbf{d}\left(  X\right)  }=\left(  \alpha
,\beta\right)  $). In other words, the directed graph $G$ has an arc from
$\left(  \alpha,\beta\right)  $ to $F_{\mathfrak{u},\mathbf{d}\left(
X\right)  +1}$.

But the only arcs of $G$ that start in $\left(  \alpha,\beta\right)  $ are
$\left(  \left(  \alpha,\beta\right)  ,\left(  \alpha+1,\beta\right)  \right)
$ and $\left(  \left(  \alpha,\beta\right)  ,\left(  \alpha,\beta+1\right)
\right)  $ (by the definition of $G$). Hence, the only points $Y$ such that
the directed graph $G$ has an arc from $\left(  \alpha,\beta\right)  $ to $Y$
are $\left(  \alpha+1,\beta\right)  $ and $\left(  \alpha,\beta+1\right)  $.
Thus, the point $F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}$ must be one
of these two points $\left(  \alpha+1,\beta\right)  $ and $\left(
\alpha,\beta+1\right)  $ (since the directed graph $G$ has an arc from
$\left(  \alpha,\beta\right)  $ to $F_{\mathfrak{u},\mathbf{d}\left(
X\right)  +1}$). In other words, we have either $F_{\mathfrak{u}%
,\mathbf{d}\left(  X\right)  +1}=\left(  \alpha+1,\beta\right)  $ or
$F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}=\left(  \alpha,\beta
+1\right)  $.

Recall that the pair $\left(  \left(  \alpha,\beta\right)  ,F_{\mathfrak{u}%
,\mathbf{d}\left(  X\right)  +1}\right)  $ is an arc of the directed graph
$G$. The same argument (applied to $\mathfrak{v}$ instead of $\mathfrak{u}$)
shows that the pair $\left(  \left(  \alpha,\beta\right)  ,F_{\mathfrak{v}%
,\mathbf{d}\left(  X\right)  +1}\right)  $ is an arc of the directed graph
$G$. Hence, (\ref{11.tVU}) (applied to $\left(  \alpha,\beta\right)  $ and
$F_{\mathfrak{v},\mathbf{d}\left(  X\right)  +1}$ instead of $U$ and $V$)
shows that
\[
\mathbf{t}\left(  \left(  \alpha,\beta\right)  \right)  -1\leq\mathbf{t}%
\left(  F_{\mathfrak{v},\mathbf{d}\left(  X\right)  +1}\right)  \leq
\mathbf{t}\left(  \left(  \alpha,\beta\right)  \right)  +1.
\]
Hence, (\ref{pf.lem.3.2.obv.c.3}) becomes%
\begin{align}
\mathbf{t}\left(  F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}\right)   &
<\mathbf{t}\left(  F_{\mathfrak{v},\mathbf{d}\left(  X\right)  +1}\right)
\leq\underbrace{\mathbf{t}\left(  \left(  \alpha,\beta\right)  \right)
}_{\substack{=\alpha-\beta\\\text{(by the definition of }\mathbf{t}\left(
\left(  \alpha,\beta\right)  \right)  \text{)}}}+1\nonumber\\
&  =\alpha-\beta+1=\left(  \alpha+1\right)  -\beta. \label{pf.lem.3.2.obv.c.8}%
\end{align}


However, if we had $F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}=\left(
\alpha+1,\beta\right)  $, then we would have%
\[
\mathbf{t}\left(  \underbrace{F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}%
}_{=\left(  \alpha+1,\beta\right)  }\right)  =\mathbf{t}\left(  \left(
\alpha+1,\beta\right)  \right)  =\left(  \alpha+1\right)  -\beta
\]
(by the definition of $\mathbf{t}\left(  \left(  \alpha+1,\beta\right)
\right)  $), which would contradict (\ref{pf.lem.3.2.obv.c.8}). Hence, we
cannot have $F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}=\left(
\alpha+1,\beta\right)  $. Thus, we have $F_{\mathfrak{u},\mathbf{d}\left(
X\right)  +1}=\left(  \alpha,\beta+1\right)  $ (since we have either
$F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}=\left(  \alpha+1,\beta
\right)  $ or $F_{\mathfrak{u},\mathbf{d}\left(  X\right)  +1}=\left(
\alpha,\beta+1\right)  $).

But (\ref{11.Fik1}) (applied to $\mathfrak{u}$ and $\mathbf{d}\left(
X\right)  $ instead of $i$ and $k$) shows that the pair $\left(
F_{\mathfrak{u},\mathbf{d}\left(  X\right)  },F_{\mathfrak{u},\mathbf{d}%
\left(  X\right)  +1}\right)  $ is an arc of the path $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$. In view of $F_{\mathfrak{u},\mathbf{d}\left(  X\right)
}=\left(  \alpha,\beta\right)  $ and $F_{\mathfrak{u},\mathbf{d}\left(
X\right)  +1}=\left(  \alpha,\beta+1\right)  $, we can rewrite this as
follows: The pair $\left(  \left(  \alpha,\beta\right)  ,\left(  \alpha
,\beta+1\right)  \right)  $ is an arc of the path $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$. In other words, the path $\pi_{\mathfrak{u}j_{\mathfrak{u}%
}}$ contains the vertical segment $\left(  \alpha,\beta\right)  \mapsto\left(
\alpha,\beta+1\right)  $.

Now, let us recall that exactly two of the paths $\pi_{1j_{1}},\pi_{2j_{2}%
},\ldots,\pi_{Nj_{N}}$ intersect at $X$, and these two paths are
$\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$.
Among these two paths, the one that ends in $Q_{k}$ is $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$ (since we have labelled them by $\pi_{\mathfrak{u}%
j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ in such a way that
$\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ ends at $Q_{k}$ whereas $\pi
_{\mathfrak{v}j_{\mathfrak{v}}}$ ends at $Q_{k+1}$). In other words, the path
(among the two paths discussed in Lemma \ref{lem.3.2.obv} \textbf{(b)}) that
ends in $Q_{k}$ is $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$. As we have just
shown, this path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ contains the vertical
segment $\left(  \alpha,\beta\right)  \mapsto\left(  \alpha,\beta+1\right)  $.
In other words, the path (among the two paths discussed in Lemma
\ref{lem.3.2.obv} \textbf{(b)}) that ends in $Q_{k}$ contains the vertical
segment $\left(  \alpha,\beta\right)  \mapsto\left(  \alpha,\beta+1\right)  $
(because this path is $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$). This proves Lemma
\ref{lem.3.2.obv} \textbf{(c)}.
\end{proof}

\subsection{\label{subsect.jdt}Proof of Lemma 3.3}

As promised above, let me give a self-contained proof of Lemma 3.3. First, I
will rewrite this lemma in a more self-contained fashion:

\begin{lemma}
\label{lem.3.3}Let $u_{1},u_{2},\ldots,u_{n}$ be $n$ elements of an
associative algebra $\mathfrak{A}$ which satisfy the relations (1.2). In this
lemma, \textquotedblleft letters\textquotedblright\ will always mean elements
of $\left\{  1,2,\ldots,n\right\}  $, and \textquotedblleft
strings\textquotedblright\ will always mean finite words composed of these
letters. Let $A=a_{\alpha}\ldots a_{2}a_{1}$ and $B=b_{\beta}\ldots b_{2}%
b_{1}$ be two strings such that $\alpha\geq\beta$. Let $X=x_{1}x_{2}\ldots
x_{\varphi}$ and $Y=y_{1}y_{2}\cdots y_{\psi}$ be two further strings. Let $p$
be a letter. Assume that
\begin{align*}
&  a_{\alpha}>a_{\alpha-1}>\cdots>a_{1}>p>x_{1}>x_{2}>\cdots>x_{\varphi},\\
&  b_{\beta}>b_{\beta-1}>\cdots>b_{1}>p,\ \ \ \ \ \ \ \ \ \ \text{and}\\
&  \left(  a_{i}\leq b_{i}\text{ for every }i\in\left\{  1,2,\ldots
,\beta\right\}  \right)  .
\end{align*}
Let $\mathbf{A}=u_{a_{\alpha}}\cdots u_{a_{2}}u_{a_{1}}$, $\mathbf{B}%
=u_{b_{\beta}}\cdots u_{b_{2}}u_{b_{1}}$, $\mathbf{p}=u_{p}$, $\mathbf{X}%
=u_{x_{1}}u_{x_{2}}\cdots u_{x_{\varphi}}$ and $\mathbf{Y}=u_{y_{1}}u_{y_{2}%
}\cdots u_{y_{\psi}}$. Then, $\mathbf{ApXBY}=\mathbf{ApBXY}$ in $\mathfrak{A}$.
\end{lemma}

Note that you denote the elements $\mathbf{A}$, $\mathbf{B}$, $\mathbf{p}$,
$\mathbf{X}$ and $\mathbf{Y}$ of $\mathfrak{A}$ (defined in Lemma
\ref{lem.3.3}) by $A$, $B$, $p$, $X$ and $Y$, but I want to avoid this abuse
of notation. I have also renamed your algebra $A$ as $\mathfrak{A}$, since the
letter $A$ is used for one of the strings. Thus, Lemma \ref{lem.3.3} yields
the claim $ApXBY=ApBXY$ of your Lemma 3.3.

It thus remains to prove Lemma \ref{lem.3.3}. Before we do so, we shall show
two lemmas:

\begin{lemma}
\label{lem.3.3a}Let $u_{1},u_{2},\ldots,u_{n}$ be $n$ elements of an
associative algebra $\mathfrak{A}$ which satisfy the relations%
\begin{equation}
u_{j}u_{i}u_{k}=u_{j}u_{k}u_{i}\ \ \ \ \ \ \ \ \ \ \text{for all }i<j<k.
\label{eq.l3.3a.2}%
\end{equation}
In this lemma, \textquotedblleft letters\textquotedblright\ will always mean
elements of $\left\{  1,2,\ldots,n\right\}  $, and \textquotedblleft
strings\textquotedblright\ will always mean finite words composed of these
letters. Let $a$ and $b$ be two letters such that $b>a$. Let $V=v_{1}%
v_{2}\ldots v_{\gamma}$ be a string such that%
\[
a>v_{1}>v_{2}>\cdots>v_{\gamma}.
\]
Let $\mathbf{a}=u_{a}$, $\mathbf{b}=u_{b}$ and $\mathbf{V}=u_{v_{1}}u_{v_{2}%
}\cdots u_{v_{\gamma}}$. Then, $\mathbf{aVb}=\mathbf{abV}$ in $\mathfrak{A}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.3.3a}.]If $\gamma=0$, then%
\begin{align*}
\mathbf{V}  &  =u_{v_{1}}u_{v_{2}}\cdots u_{v_{\gamma}}=u_{v_{1}}u_{v_{2}%
}\cdots u_{v_{0}}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\gamma=0\right) \\
&  =\left(  \text{empty product}\right)  =1.
\end{align*}
Hence, if $\gamma=0$, then $\mathbf{aVb}=\mathbf{abV}$ is obviously true
(because $\mathbf{a}\underbrace{\mathbf{V}}_{=1}\mathbf{b}=\mathbf{ab}$ and
$\mathbf{ab}\underbrace{\mathbf{V}}_{=1}=\mathbf{ab}$). Thus, for the rest of
this proof, we can WLOG assume that $\gamma\neq0$. Assume this. Thus,
$\gamma\geq1$ (since $\gamma\neq0$ and $\gamma\in\mathbb{N}$). Therefore,
$1\in\left\{  1,2,\ldots,\gamma\right\}  $. Hence, $v_{1}$ is well-defined.

From $a>v_{1}>v_{2}>\cdots>v_{\gamma}$, we obtain $a>v_{1}$ (since
$1\in\left\{  1,2,\ldots,\gamma\right\}  $). Hence, $v_{1}<a<b$ (since $b>a$).
Thus, (\ref{eq.l3.3a.2}) (applied to $i=v_{1}$, $j=a$ and $k=b$) yields
$u_{a}u_{v_{1}}u_{b}=u_{a}u_{b}u_{v_{1}}$.

We shall prove that every $\rho\in\left\{  1,2,\ldots,\gamma\right\}  $
satisfies%
\begin{equation}
\mathbf{a}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{\rho}}\right)  \mathbf{b}%
=\mathbf{ab}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{\rho}}\right)  .
\label{12.l3.3a.pf.1}%
\end{equation}


[\textit{Proof of (\ref{12.l3.3a.pf.1}):} We will prove (\ref{12.l3.3a.pf.1})
by induction over $\rho$:

\textit{Induction base:} Comparing%
\[
\underbrace{\mathbf{a}}_{=u_{a}}\underbrace{\left(  u_{v_{1}}u_{v_{2}}\cdots
u_{v_{1}}\right)  }_{=u_{v_{1}}}\underbrace{\mathbf{b}}_{=u_{b}}=u_{a}%
u_{v_{1}}u_{b}=u_{a}u_{b}u_{v_{1}}%
\]
with%
\[
\underbrace{\mathbf{a}}_{=u_{a}}\underbrace{\mathbf{b}}_{=u_{b}}%
\underbrace{\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{1}}\right)  }_{=u_{v_{1}}%
}=u_{a}u_{b}u_{v_{1}},
\]
we obtain $\mathbf{a}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{1}}\right)
\mathbf{b}=\mathbf{ab}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{1}}\right)  $. In
other words, (\ref{12.l3.3a.pf.1}) holds for $\rho=1$. This completes the
induction base.

\textit{Induction step:} Let $r\in\left\{  1,2,\ldots,\gamma-1\right\}  $.
Assume (as the induction hypothesis) that (\ref{12.l3.3a.pf.1}) holds for
$\rho=r$. We must prove that (\ref{12.l3.3a.pf.1}) holds for $\rho=r+1$.

Recall that $a>v_{1}>v_{2}>\cdots>v_{\gamma}$. Hence, $a>v_{h}$ for every
$h\in\left\{  1,2,\ldots,\gamma\right\}  $. Applying this to $h=r$, we obtain
$a>v_{r}$. Hence, $b>a>v_{r}$. On the other hand, $v_{r}>v_{r+1}$ (since
$v_{1}>v_{2}>\cdots>v_{\gamma}$), so that $v_{r+1}<v_{r}<b$ (since $b>v_{r}$).
Thus, (\ref{eq.l3.3a.2}) (applied to $i=v_{r+1}$, $j=v_{r}$ and $k=b$) yields
$u_{v_{r}}u_{v_{r+1}}u_{b}=u_{v_{r}}u_{b}u_{v_{r+1}}$.

Recall that we assumed that (\ref{12.l3.3a.pf.1}) holds for $\rho=r$. In other
words, we have%
\begin{equation}
\mathbf{a}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r}}\right)  \mathbf{b}%
=\mathbf{ab}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r}}\right)  .
\label{12.l3.3a.pf.1.pf.IH}%
\end{equation}
Now, comparing%
\begin{align*}
\mathbf{a}\underbrace{\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r+1}}\right)
}_{=\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r-1}}\right)  u_{v_{r}}u_{v_{r+1}}%
}\underbrace{\mathbf{b}}_{=u_{b}}  &  =\mathbf{a}\left(  u_{v_{1}}u_{v_{2}%
}\cdots u_{v_{r-1}}\right)  \underbrace{u_{v_{r}}u_{v_{r+1}}u_{b}}_{=u_{v_{r}%
}u_{b}u_{v_{r+1}}}\\
&  =\mathbf{a}\underbrace{\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r-1}}\right)
u_{v_{r}}}_{=u_{v_{1}}u_{v_{2}}\cdots u_{v_{r}}}\underbrace{u_{b}%
}_{\substack{=\mathbf{b}\\\text{(since }\mathbf{b}=u_{b}\text{)}}}u_{v_{r+1}%
}\\
&  =\underbrace{\mathbf{a}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r}}\right)
\mathbf{b}}_{\substack{=\mathbf{ab}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r}%
}\right)  \\\text{(by (\ref{12.l3.3a.pf.1.pf.IH}))}}}u_{v_{r+1}}\\
&  =\mathbf{ab}\underbrace{\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{r}}\right)
u_{v_{r+1}}}_{=u_{v_{1}}u_{v_{2}}\cdots u_{v_{r+1}}}=\mathbf{ab}\left(
u_{v_{1}}u_{v_{2}}\cdots u_{v_{r+1}}\right)  .
\end{align*}
In other words, (\ref{12.l3.3a.pf.1}) holds for $\rho=r+1$. This completes the
induction step. Thus, (\ref{12.l3.3a.pf.1}) is proved by induction.]

We have $\gamma\in\left\{  1,2,\ldots,\gamma\right\}  $ (since $\gamma\geq1$).
Hence, (\ref{12.l3.3a.pf.1}) (applied to $\rho=\gamma$) yields%
\[
\mathbf{a}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{\gamma}}\right)
\mathbf{b}=\mathbf{ab}\left(  u_{v_{1}}u_{v_{2}}\cdots u_{v_{\gamma}}\right)
.
\]
In view of $\mathbf{V}=u_{v_{1}}u_{v_{2}}\cdots u_{v_{\gamma}}$, this rewrites
as $\mathbf{aVb}=\mathbf{abV}$. This proves Lemma \ref{lem.3.3a}.
\end{proof}

Our second lemma is a stronger version of Lemma \ref{lem.3.3}:

\begin{lemma}
\label{lem.3.3gen}Let $u_{1},u_{2},\ldots,u_{n}$ be $n$ elements of an
associative algebra $\mathfrak{A}$ which satisfy the relations
(\ref{eq.l3.3a.2}). In this lemma, \textquotedblleft letters\textquotedblright%
\ will always mean elements of $\left\{  1,2,\ldots,n\right\}  $, and
\textquotedblleft strings\textquotedblright\ will always mean finite words
composed of these letters. Let $A=a_{\alpha}\ldots a_{2}a_{1}$ and
$B=b_{\beta}\ldots b_{2}b_{1}$ be two strings such that $\alpha\geq\beta-1$.
Let $X=x_{1}x_{2}\ldots x_{\varphi}$ be a further string. Let $p$ be a letter.
Assume that
\begin{align*}
&  a_{\alpha}>a_{\alpha-1}>\cdots>a_{1}>p>x_{1}>x_{2}>\cdots>x_{\varphi},\\
&  b_{\beta}>b_{\beta-1}>\cdots>b_{1}>p,\ \ \ \ \ \ \ \ \ \ \text{and}\\
&  \left(  a_{i}\leq b_{i}\text{ for every }i\in\left\{  1,2,\ldots
,\beta-1\right\}  \right)  .
\end{align*}
Let $\mathbf{A}=u_{a_{\alpha}}\cdots u_{a_{2}}u_{a_{1}}$, $\mathbf{B}%
=u_{b_{\beta}}\cdots u_{b_{2}}u_{b_{1}}$, $\mathbf{p}=u_{p}$, and
$\mathbf{X}=u_{x_{1}}u_{x_{2}}\cdots u_{x_{\varphi}}$. Then, $\mathbf{ApXB}%
=\mathbf{ApBX}$ in $\mathfrak{A}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.3.3gen}.]Let us extend the $\alpha$-tuple $\left(
a_{\alpha},a_{\alpha-1},\ldots,a_{1}\right)  $ to an $\left(  \alpha+1\right)
$-tuple $\left(  a_{\alpha},a_{\alpha-1},\ldots,a_{1},a_{0}\right)  $ by
setting $a_{0}=p$. Thus, $a_{0},a_{1},\ldots,a_{\alpha}$ are well-defined
letters. In other words, $a_{j}$ is a well-defined letter for each
$j\in\left\{  0,1,\ldots,\alpha\right\}  $.

But recall that we have the chain of inequalities
\[
a_{\alpha}>a_{\alpha-1}>\cdots>a_{1}>p>x_{1}>x_{2}>\cdots>x_{\varphi}.
\]
In view of $a_{0}=p$, this rewrites as%
\begin{equation}
a_{\alpha}>a_{\alpha-1}>\cdots>a_{1}>a_{0}>x_{1}>x_{2}>\cdots>x_{\varphi}.
\label{pf.lem.3.3gen.ineqs1}%
\end{equation}
Also, $\mathbf{p}=u_{p}=u_{a_{0}}$ (since $p=a_{0}$).

From $\alpha\geq\beta-1$, we obtain $\beta-1\leq\alpha$, thus $\left\{
0,1,\ldots,\beta-1\right\}  \subseteq\left\{  0,1,\ldots,\alpha\right\}  $.

We have%
\begin{align}
&  \underbrace{\mathbf{A}}_{=u_{a_{\alpha}}\cdots u_{a_{2}}u_{a_{1}}%
}\underbrace{\mathbf{p}}_{=u_{a_{0}}}\nonumber\\
&  =\left(  u_{a_{\alpha}}\cdots u_{a_{2}}u_{a_{1}}\right)  u_{a_{0}%
}=u_{a_{\alpha}}\cdots u_{a_{1}}u_{a_{0}}\nonumber\\
&  =\left(  u_{a_{\alpha}}\cdots u_{a_{\beta+1}}u_{a_{\beta}}\right)  \left(
u_{a_{\beta-1}}u_{a_{\beta-2}}\cdots u_{a_{0}}\right)
\label{pf.lem.3.3gen.Ap=}%
\end{align}
(since $\alpha\geq\beta-1$).

If $i\in\left\{  0,1,\ldots,\beta\right\}  $, then the numbers $i-1,i-2,\ldots
,0$ are elements of $\left\{  0,1,\ldots,\beta-1\right\}  $ and thus are
elements of $\left\{  0,1,\ldots,\alpha\right\}  $ (since $\left\{
0,1,\ldots,\beta-1\right\}  \subseteq\left\{  0,1,\ldots,\alpha\right\}  $).
Hence, if $i\in\left\{  0,1,\ldots,\beta\right\}  $, then $a_{i-1}%
,a_{i-2},\ldots,a_{0}$ are well-defined letters (since $a_{j}$ is a
well-defined letter for each $j\in\left\{  0,1,\ldots,\alpha\right\}  $).
Thus, for each $i\in\left\{  0,1,\ldots,\beta\right\}  $, we can define an
element $\mathbf{A}_{i}$ of $\mathfrak{A}$ by%
\[
\mathbf{A}_{i}=u_{a_{i-1}}u_{a_{i-2}}\cdots u_{a_{0}}.
\]
Consider this $\mathbf{A}_{i}$.

The definition of $\mathbf{A}_{\beta}$ yields $\mathbf{A}_{\beta}%
=u_{a_{\beta-1}}u_{a_{\beta-2}}\cdots u_{a_{0}}$. Hence,%
\begin{align}
&  \left(  u_{a_{\alpha}}\cdots u_{a_{\beta+1}}u_{a_{\beta}}\right)
\underbrace{\mathbf{A}_{\beta}}_{=u_{a_{\beta-1}}u_{a_{\beta-2}}\cdots
u_{a_{0}}}\nonumber\\
&  =\left(  u_{a_{\alpha}}\cdots u_{a_{\beta+1}}u_{a_{\beta}}\right)  \left(
u_{a_{\beta-1}}u_{a_{\beta-2}}\cdots u_{a_{0}}\right) \nonumber\\
&  =\mathbf{Ap}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.3.3gen.Ap=}%
)}\right)  . \label{pf.lem.3.3gen.=Ap}%
\end{align}


For each $i\in\left\{  0,1,\ldots,\beta\right\}  $, we set%
\[
\mathbf{B}_{i}=u_{b_{i}}u_{b_{i-1}}\cdots u_{b_{1}}.
\]
Thus,%
\[
\mathbf{B}_{0}=u_{b_{0}}u_{b_{0-1}}\cdots u_{b_{1}}=\left(  \text{empty
product}\right)  =1
\]
and%
\[
\mathbf{B}_{\beta}=u_{b_{\beta}}u_{b_{\beta-1}}\cdots u_{b_{1}}=u_{b_{\beta}%
}\cdots u_{b_{2}}u_{b_{1}}=\mathbf{B}%
\]
(since $\mathbf{B}=u_{b_{\beta}}\cdots u_{b_{2}}u_{b_{1}}$).

We now claim that%
\begin{equation}
\mathbf{A}_{i}\mathbf{XB}_{i}=\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{X}
\label{pf.lem.3.3gen.main}%
\end{equation}
for each $i\in\left\{  0,1,\ldots,\beta\right\}  $.

[\textit{Proof of (\ref{pf.lem.3.3gen.main}):} We shall prove
(\ref{pf.lem.3.3gen.main}) by induction on $i$:

\textit{Induction base:} Comparing $\mathbf{A}_{0}\mathbf{X}%
\underbrace{\mathbf{B}_{0}}_{=1}=\mathbf{A}_{0}\mathbf{X}$ with $\mathbf{A}%
_{0}\underbrace{\mathbf{B}_{0}}_{=1}\mathbf{X}=\mathbf{A}_{0}\mathbf{X}$, we
obtain $\mathbf{A}_{0}\mathbf{XB}_{0}=\mathbf{A}_{0}\mathbf{B}_{0}\mathbf{X}$.
In other words, (\ref{pf.lem.3.3gen.main}) holds for $i=0$. This completes the
induction base.

\textit{Induction step:} Let $s\in\left\{  0,1,\ldots,\beta-1\right\}  $.
Assume (as the induction hypothesis) that (\ref{pf.lem.3.3gen.main}) holds for
$i=s$. We must prove that (\ref{pf.lem.3.3gen.main}) holds for $i=s+1$.

We have assumed that (\ref{pf.lem.3.3gen.main}) holds for $i=s$. In other
words, we have%
\begin{equation}
\mathbf{A}_{s}\mathbf{XB}_{s}=\mathbf{A}_{s}\mathbf{B}_{s}\mathbf{X}.
\label{pf.lem.3.3gen.main.pf.IH}%
\end{equation}


It is easy to see that $a_{s}<b_{s+1}$\ \ \ \ \footnote{\textit{Proof.} We are
in one of the following two cases:
\par
\textit{Case 1:} We have $s=0$.
\par
\textit{Case 2:} We have $s\neq0$.
\par
Let us first consider Case 1. In this case, we have $s=0$. Hence, $a_{s}%
=a_{0}=p$. Also, $s=0$, so that $0=s\in\left\{  0,1,\ldots,\beta-1\right\}  $,
so that $0\leq\beta-1$ and thus $\beta\geq1$. Hence, $1\in\left\{
1,2,\ldots,\beta\right\}  $, so that $b_{1}$ is well-defined. From $b_{\beta
}>b_{\beta-1}>\cdots>b_{1}>p$, we thus obtain $b_{1}>p$. But $s=0$, so that
$s+1=1$ and therefore $b_{s+1}=b_{1}>p=a_{s}$ (since $a_{s}=p$). Thus,
$a_{s}<b_{s+1}$. Hence, $a_{s}<b_{s+1}$ is proved in Case 1.
\par
Let us now consider Case 2. In this case, we have $s\neq0$. Combining this
with $s\in\left\{  0,1,\ldots,\beta-1\right\}  $, we obtain $s\in\left\{
0,1,\ldots,\beta-1\right\}  \setminus\left\{  0\right\}  =\left\{
1,2,\ldots,\beta-1\right\}  $.
\par
We assumed that $\left(  a_{i}\leq b_{i}\text{ for every }i\in\left\{
1,2,\ldots,\beta-1\right\}  \right)  $. Applying this to $i=s$, we obtain
$a_{s}\leq b_{s}$ (since $s\in\left\{  1,2,\ldots,\beta-1\right\}  $). But
from $b_{\beta}>b_{\beta-1}>\cdots>b_{1}>p$, we obtain $b_{\beta}>b_{\beta
-1}>\cdots>b_{1}$. In other words, $b_{i+1}>b_{i}$ for each $i\in\left\{
1,2,\ldots,\beta-1\right\}  $. Applying this to $i=s$, we obtain
$b_{s+1}>b_{s}$ (since $s\in\left\{  1,2,\ldots,\beta-1\right\}  $). Hence,
$b_{s}<b_{s+1}$, so that $a_{s}\leq b_{s}<b_{s+1}$. Thus, $a_{s}<b_{s+1}$ is
proved in Case 2.
\par
We have now proved $a_{s}<b_{s+1}$ in both Cases 1 and 2. Since these two
Cases cover all possibilities, we thus conclude that $a_{s}<b_{s+1}$ always
holds.}. Thus, $b_{s+1}>a_{s}$. Also, $s\in\left\{  0,1,\ldots,\beta
-1\right\}  $ shows that $s\leq\beta-1\leq\alpha$.

The definition of $\mathbf{A}_{s}$ yields $\mathbf{A}_{s}=u_{a_{s-1}%
}u_{a_{s-2}}\cdots u_{a_{0}}$. The definition of $\mathbf{A}_{s+1}$ yields
\begin{align}
\mathbf{A}_{s+1}  &  =u_{a_{\left(  s+1\right)  -1}}u_{a_{\left(  s+1\right)
-2}}\cdots u_{a_{0}}=u_{a_{s}}u_{a_{s-1}}\cdots u_{a_{0}}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(  s+1\right)  -1=s\right)
\nonumber\\
&  =u_{a_{s}}\underbrace{\left(  u_{a_{s-1}}u_{a_{s-2}}\cdots u_{a_{0}%
}\right)  }_{\substack{=\mathbf{A}_{s}\\\text{(since }\mathbf{A}%
_{s}=u_{a_{s-1}}u_{a_{s-2}}\cdots u_{a_{0}}\text{)}}}=u_{a_{s}}\mathbf{A}_{s}.
\label{pf.lem.3.3gen.main.pf.Asp1}%
\end{align}


The definition of $\mathbf{B}_{s}$ yields $\mathbf{B}_{s}=u_{b_{s}}u_{b_{s-1}%
}\cdots u_{b_{1}}$. The definition of $\mathbf{B}_{s+1}$ yields
\begin{align}
\mathbf{B}_{s+1}  &  =u_{b_{s+1}}u_{b_{\left(  s+1\right)  -1}}\cdots
u_{b_{1}}=u_{b_{s+1}}u_{b_{s}}\cdots u_{b_{1}}=u_{b_{s+1}}\underbrace{\left(
u_{b_{s}}u_{b_{s-1}}\cdots u_{b_{1}}\right)  }_{\substack{=\mathbf{B}%
_{s}\\\text{(since }\mathbf{B}_{s}=u_{b_{s}}u_{b_{s-1}}\cdots u_{b_{1}%
}\text{)}}}\nonumber\\
&  =u_{b_{s+1}}\mathbf{B}_{s}. \label{pf.lem.3.3gen.main.pf.Bsp1}%
\end{align}


From (\ref{pf.lem.3.3gen.ineqs1}), we obtain $a_{\alpha}>a_{\alpha-1}%
>\cdots>a_{1}>a_{0}$. Since $s\leq\alpha$, this yields $a_{s}>a_{s-1}%
>a_{s-2}>\cdots>a_{0}$.

Now, let $V_{1}$ be the string defined by $V_{1}=a_{s-1}a_{s-2}\cdots a_{0}$.
This string satisfies $a_{s}>a_{s-1}>a_{s-2}>\cdots>a_{0}$ and $\mathbf{A}%
_{s}=u_{a_{s-1}}u_{a_{s-2}}\cdots u_{a_{0}}$. Hence, Lemma \ref{lem.3.3a}
(applied to $\gamma=s$ and $V=V_{1}$ and $\left(  v_{1},v_{2},\ldots
,v_{\gamma}\right)  =\left(  a_{s-1},a_{s-2},\ldots,a_{0}\right)  $ and
$a=a_{s}$ and $b=b_{s+1}$ and $\mathbf{V}=\mathbf{A}_{s}$ and $\mathbf{a}%
=u_{a_{s}}$ and $\mathbf{b}=u_{b_{s+1}}$) yields%
\begin{equation}
u_{a_{s}}\mathbf{A}_{s}u_{b_{s+1}}=u_{a_{s}}u_{b_{s+1}}\mathbf{A}_{s}
\label{pf.lem.3.3gen.main.pf.4}%
\end{equation}
(since $u_{a_{s}}=u_{a_{s}}$ and $u_{b_{s+1}}=u_{b_{s+1}}$).

Furthermore, let us define a $\left(  s+\varphi\right)  $-tuple $\left(
v_{1},v_{2},\ldots,v_{s+\varphi}\right)  $ of letters by%
\[
\left(  v_{1},v_{2},\ldots,v_{s+\varphi}\right)  =\left(  a_{s-1}%
,a_{s-2},\ldots,a_{0},x_{1},x_{2},\ldots,x_{\varphi}\right)  .
\]
Let $V$ be the string defined by $V=v_{1}v_{2}\cdots v_{s+\varphi}$. Combining
$a_{s}>a_{s-1}>a_{s-2}>\cdots>a_{0}$ with $a_{0}>x_{1}>x_{2}>\cdots
>x_{\varphi}$ (which follows from (\ref{pf.lem.3.3gen.ineqs1})), we see that
\[
a_{s}>a_{s-1}>a_{s-2}>\cdots>a_{0}>x_{1}>x_{2}>\cdots>x_{\varphi}.
\]
In view of $\left(  v_{1},v_{2},\ldots,v_{s+\varphi}\right)  =\left(
a_{s-1},a_{s-2},\ldots,a_{0},x_{1},x_{2},\ldots,x_{\varphi}\right)  $, we can
rewrite this as%
\[
a_{s}>v_{1}>v_{2}>\cdots>v_{s}>v_{s+1}>v_{s+2}>\cdots>v_{s+\varphi}.
\]
In other words,%
\[
a_{s}>v_{1}>v_{2}>\cdots>v_{s+\varphi}.
\]
Moreover, from $\left(  v_{1},v_{2},\ldots,v_{s+\varphi}\right)  =\left(
a_{s-1},a_{s-2},\ldots,a_{0},x_{1},x_{2},\ldots,x_{\varphi}\right)  $, we
obtain%
\[
u_{v_{1}}u_{v_{2}}\cdots u_{v_{s+\varphi}}=u_{a_{s-1}}u_{a_{s-2}}\cdots
u_{a_{0}}u_{x_{1}}u_{x_{2}}\cdots u_{x_{\varphi}}.
\]
Comparing this with
\[
\underbrace{\mathbf{A}_{s}}_{=u_{a_{s-1}}u_{a_{s-2}}\cdots u_{a_{0}}%
}\underbrace{\mathbf{X}}_{=u_{x_{1}}u_{x_{2}}\cdots u_{x_{\varphi}}%
}=u_{a_{s-1}}u_{a_{s-2}}\cdots u_{a_{0}}u_{x_{1}}u_{x_{2}}\cdots
u_{x_{\varphi}},
\]
we obtain%
\[
\mathbf{A}_{s}\mathbf{X}=u_{v_{1}}u_{v_{2}}\cdots u_{v_{s+\varphi}}.
\]
Hence, Lemma \ref{lem.3.3a} (applied to $\gamma=s+\varphi$ and $a=a_{s}$ and
$b=b_{s+1}$ and $\mathbf{V}=\mathbf{A}_{s}\mathbf{X}$ and $\mathbf{a}%
=u_{a_{s}}$ and $\mathbf{b}=u_{b_{s+1}}$) yields%
\begin{equation}
u_{a_{s}}\mathbf{A}_{s}\mathbf{X}u_{b_{s+1}}=u_{a_{s}}u_{b_{s+1}}%
\mathbf{A}_{s}\mathbf{X} \label{pf.lem.3.3gen.main.pf.5}%
\end{equation}
(since $u_{a_{s}}=u_{a_{s}}$ and $u_{b_{s+1}}=u_{b_{s+1}}$). Now,%
\[
\underbrace{\mathbf{A}_{s+1}}_{\substack{=u_{a_{s}}\mathbf{A}_{s}\\\text{(by
(\ref{pf.lem.3.3gen.main.pf.Asp1}))}}}\mathbf{X}\underbrace{\mathbf{B}_{s+1}%
}_{\substack{=u_{b_{s+1}}\mathbf{B}_{s}\\\text{(by
(\ref{pf.lem.3.3gen.main.pf.Bsp1}))}}}=\underbrace{u_{a_{s}}\mathbf{A}%
_{s}\mathbf{X}u_{b_{s+1}}}_{\substack{=u_{a_{s}}u_{b_{s+1}}\mathbf{A}%
_{s}\mathbf{X}\\\text{(by (\ref{pf.lem.3.3gen.main.pf.5}))}}}\mathbf{B}%
_{s}=u_{a_{s}}u_{b_{s+1}}\underbrace{\mathbf{A}_{s}\mathbf{XB}_{s}%
}_{\substack{=\mathbf{A}_{s}\mathbf{B}_{s}\mathbf{X}\\\text{(by
(\ref{pf.lem.3.3gen.main.pf.IH}))}}}=u_{a_{s}}u_{b_{s+1}}\mathbf{A}%
_{s}\mathbf{B}_{s}\mathbf{X}.
\]
Comparing this with%
\[
\underbrace{\mathbf{A}_{s+1}}_{\substack{=u_{a_{s}}\mathbf{A}_{s}\\\text{(by
(\ref{pf.lem.3.3gen.main.pf.Asp1}))}}}\underbrace{\mathbf{B}_{s+1}%
}_{\substack{=u_{b_{s+1}}\mathbf{B}_{s}\\\text{(by
(\ref{pf.lem.3.3gen.main.pf.Bsp1}))}}}\mathbf{X}=\underbrace{u_{a_{s}%
}\mathbf{A}_{s}u_{b_{s+1}}}_{\substack{=u_{a_{s}}u_{b_{s+1}}\mathbf{A}%
_{s}\\\text{(by (\ref{pf.lem.3.3gen.main.pf.4}))}}}\mathbf{B}_{s}%
\mathbf{X}=u_{a_{s}}u_{b_{s+1}}\mathbf{A}_{s}\mathbf{B}_{s}\mathbf{X},
\]
we obtain $\mathbf{A}_{s+1}\mathbf{XB}_{s+1}=\mathbf{A}_{s+1}\mathbf{B}%
_{s+1}\mathbf{X}$. In other words, (\ref{pf.lem.3.3gen.main}) holds for
$i=s+1$. This completes the induction step. Hence, the induction proof of
(\ref{pf.lem.3.3gen.main}) is complete.]

Now, (\ref{pf.lem.3.3gen.main}) (applied to $i=\beta$) yields
\[
\mathbf{A}_{\beta}\mathbf{XB}_{\beta}=\mathbf{A}_{\beta}\mathbf{B}_{\beta
}\mathbf{X}.
\]
Hence,%
\[
\left(  u_{a_{\alpha}}\cdots u_{a_{\beta+1}}u_{a_{\beta}}\right)
\underbrace{\mathbf{A}_{\beta}\mathbf{XB}_{\beta}}_{=\mathbf{A}_{\beta
}\mathbf{B}_{\beta}\mathbf{X}}=\underbrace{\left(  u_{a_{\alpha}}\cdots
u_{a_{\beta+1}}u_{a_{\beta}}\right)  \mathbf{A}_{\beta}}%
_{\substack{=\mathbf{Ap}\\\text{(by (\ref{pf.lem.3.3gen.=Ap}))}}%
}\underbrace{\mathbf{B}_{\beta}}_{=\mathbf{B}}\mathbf{X}=\mathbf{ApBX}.
\]
Therefore,%
\[
\mathbf{ApBX}=\underbrace{\left(  u_{a_{\alpha}}\cdots u_{a_{\beta+1}%
}u_{a_{\beta}}\right)  \mathbf{A}_{\beta}}_{\substack{=\mathbf{Ap}\\\text{(by
(\ref{pf.lem.3.3gen.=Ap}))}}}\mathbf{X}\underbrace{\mathbf{B}_{\beta}%
}_{=\mathbf{B}}=\mathbf{ApXB}.
\]
This proves Lemma \ref{lem.3.3gen}.
\end{proof}

\begin{proof}
[Proof of Lemma \ref{lem.3.3}.]We assumed that $u_{1},u_{2},\ldots,u_{n}$
satisfy the relations (1.2). Thus, in particular, the second equality of (1.2)
is satisfied. In other words, we have%
\[
u_{j}u_{i}u_{k}=u_{j}u_{k}u_{i}\ \ \ \ \ \ \ \ \ \ \text{for all }i<j\leq
k\text{ satisfying }\left\vert i-k\right\vert \geq2.
\]
Hence, in particular, we have%
\[
u_{j}u_{i}u_{k}=u_{j}u_{k}u_{i}\ \ \ \ \ \ \ \ \ \ \text{for all }i<j<k
\]
(because every three letters $i,j,k$ satisfying $i<j<k$ satisfy $\left\vert
i-k\right\vert \geq2$\ \ \ \ \footnote{\textit{Proof.} Let $i,j,k$ be three
letters satisfying $i<j<k$. We must prove that $\left\vert i-k\right\vert
\geq2$.
\par
We have $i<j$ and thus $i\leq j-1$ (since $i$ and $j$ are integers). We have
$j<k$ and thus $j\leq k-1$ (since $j$ and $k$ are integers). Now,
$i\leq\underbrace{j}_{\leq k-1}-1\leq\left(  k-1\right)  -1=k-2$, so that
$i-k\leq-2<0$ and therefore $\left\vert i-k\right\vert =-\underbrace{\left(
i-k\right)  }_{\leq-2}\geq-\left(  -2\right)  =2$. Qed.}). In other words,
$u_{1},u_{2},\ldots,u_{n}$ satisfy the relations (\ref{eq.l3.3a.2}). From
$\alpha\geq\beta$, we obtain $\alpha\geq\beta\geq\beta-1$. Furthermore, we
have assumed that $\left(  a_{i}\leq b_{i}\text{ for every }i\in\left\{
1,2,\ldots,\beta\right\}  \right)  $; thus, $\left(  a_{i}\leq b_{i}\text{ for
every }i\in\left\{  1,2,\ldots,\beta-1\right\}  \right)  $. Hence, Lemma
\ref{lem.3.3gen} yields $\mathbf{ApXB}=\mathbf{ApBX}$ in $\mathfrak{A}$.
Hence, $\underbrace{\mathbf{ApXB}}_{=\mathbf{ApBX}}\mathbf{Y}=\mathbf{ApBXY}$.
This proves Lemma \ref{lem.3.3}.
\end{proof}

\subsection{\label{subsect.only-id}Proof of $\left(  j_{1},j_{2},\ldots
,j_{N}\right)  =\left(  1,2,\ldots,N\right)  $}

The notations introduced during the proof of Lemma 3.2 shall be used
throughout Subsection \ref{subsect.only-id}. We want to show the following lemma:

\begin{lemma}
\label{lem.only-id}Let $\left(  \pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}%
}\right)  $ be a non-intersecting family of lattice paths, where each
$\pi_{ij_{i}}$ is a path from $P_{i}$ to $Q_{j}$. Then, $\left(  j_{1}%
,j_{2},\ldots,j_{N}\right)  =\left(  1,2,\ldots,N\right)  $.
\end{lemma}

This lemma is used to link the left hand side of (3.3) with the terms on the
right hand side of (3.3) that survive the cancellation.

Lemma \ref{lem.only-id} is a particular case of Proposition 2 in
math.stackexchange question \#2870640 (
\url{https://math.stackexchange.com/questions/2870640} ), but let us give a
self-contained proof here.

\begin{proof}
[Proof of Lemma \ref{lem.only-id}.]We shall use the notations introduced in
Subsection \ref{subsect.11}. (In particular, we will use the points $F_{i,k}$
defined in Subsection \ref{subsect.11}.)

The following arguments mirror some of the arguments made at the beginning of
the proof of Lemma \ref{lem.3.2.obv} (but we are having it somewhat easier
now, since the family $\left(  \pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}%
}\right)  $ is non-intersecting).

If $k\in\left\{  0,1,\ldots,n\right\}  $, then any two distinct elements
$\mathfrak{u}$ and $\mathfrak{v}$ of $\left\{  1,2,\ldots,N\right\}  $ satisfy%
\begin{equation}
\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  . \label{pf.lem.only-id.tFuk}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.only-id.tFuk}):} Let $k\in\left\{
0,1,\ldots,n\right\}  $. Let $\mathfrak{u}$ and $\mathfrak{v}$ be two distinct
elements of $\left\{  1,2,\ldots,N\right\}  $. We need to prove
(\ref{pf.lem.only-id.tFuk}).
\par
Assume the contrary. Thus, (\ref{pf.lem.only-id.tFuk}) does not hold. In other
words, $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  =\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  $. But $\mathbf{d}\left(  F_{\mathfrak{u}%
,k}\right)  =k$ (by (\ref{11.dFik}), applied to $i=\mathfrak{u}$) and
$\mathbf{d}\left(  F_{\mathfrak{v},k}\right)  =k$ (by (\ref{11.dFik}), applied
to $i=\mathfrak{v}$). Hence, $\mathbf{d}\left(  F_{\mathfrak{u},k}\right)
=k=\mathbf{d}\left(  F_{\mathfrak{v},k}\right)  $. Altogether, $\left(
\underbrace{\mathbf{d}\left(  F_{\mathfrak{u},k}\right)  }_{=\mathbf{d}\left(
F_{\mathfrak{v},k}\right)  },\underbrace{\mathbf{t}\left(  F_{\mathfrak{u}%
,k}\right)  }_{=\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  }\right)
=\left(  \mathbf{d}\left(  F_{\mathfrak{v},k}\right)  ,\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  \right)  $. Thus, (\ref{11.T1=T2}) (applied to
$T_{1}=F_{\mathfrak{u},k}$ and $T_{2}=F_{\mathfrak{v},k}$) yields
$F_{\mathfrak{u},k}=F_{\mathfrak{v},k}$.
\par
But $F_{\mathfrak{u},k}$ is the unique point $F$ on the path $\pi
_{\mathfrak{u}j_{\mathfrak{u}}}$ such that $\mathbf{d}\left(  F\right)  =k$
(according to the definition of $F_{\mathfrak{u},k}$). Hence, $F_{\mathfrak{u}%
,k}$ is a point $F$ on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ such that
$\mathbf{d}\left(  F\right)  =k$. In particular, $F_{\mathfrak{u},k}$ is a
point on the path $\pi_{\mathfrak{u}j_{\mathfrak{u}}}$. Similarly,
$F_{\mathfrak{v},k}$ is a point on the path $\pi_{\mathfrak{v}j_{\mathfrak{v}%
}}$. In other words, $F_{\mathfrak{u},k}$ is a point on the path
$\pi_{\mathfrak{v}j_{\mathfrak{v}}}$ (since $F_{\mathfrak{u},k}%
=F_{\mathfrak{v},k}$). The point $F_{\mathfrak{u},k}$ thus lies on both paths
$\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}$.
Hence, $F_{\mathfrak{u},k}$ is a point in which (at least) two of the paths
$\pi_{1j_{1}},\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}$ intersect (namely, the paths
$\pi_{\mathfrak{u}j_{\mathfrak{u}}}$ and $\pi_{\mathfrak{v}j_{\mathfrak{v}}}%
$). Thus, (at least) two of the paths $\pi_{1j_{1}},\pi_{2j_{2}},\ldots
,\pi_{Nj_{N}}$ intersect. But no two of the paths $\pi_{1j_{1}},\pi_{2j_{2}%
},\ldots,\pi_{Nj_{N}}$ intersect (since the family $\left(  \pi_{1j_{1}}%
,\pi_{2j_{2}},\ldots,\pi_{Nj_{N}}\right)  $ is non-intersecting). The previous
two sentences contradict each other. This contradiction proves that our
assumption was wrong. Thus, (\ref{pf.lem.only-id.tFuk}) is proven.} Moreover,
if $k\in\left\{  0,1,\ldots,n\right\}  $ and if $\mathfrak{u}$ and
$\mathfrak{v}$ are two elements of $\left\{  1,2,\ldots,N\right\}  $, then%
\begin{equation}
\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{u},k}\right)  +1. \label{pf.lem.only-id.tFvk}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.only-id.tFvk}):} This statement is
precisely (\ref{11.tFvk}), and can be proved in the exact same way as
(\ref{11.tFvk}) was proved.}

But recall that $\left(  j_{1},j_{2},\ldots,j_{N}\right)  $ is a permutation
of $\left\{  1,2,\ldots,N\right\}  $. Denote this permutation by $\mathbf{j}$.
Thus,
\begin{equation}
\mathbf{j}\left(  i\right)  =j_{i}\ \ \ \ \ \ \ \ \ \ \text{for every }%
i\in\left\{  1,2,\ldots,N\right\}  . \label{pf.lem.only-id.ji}%
\end{equation}
Now, for every $j\in\left\{  1,2,\ldots,N-1\right\}  $, we have%
\begin{equation}
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j\right)  ,k}\right)
\leq\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j+1\right)  ,k}\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }k\in\left\{  0,1,\ldots,n\right\}  .
\label{pf.lem.only-id.tFinc1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.only-id.tFinc1}):} Let $j\in\left\{
1,2,\ldots,N-1\right\}  $. Set $\mathfrak{u}=\mathbf{j}^{-1}\left(  j\right)
$ and $\mathfrak{v}=\mathbf{j}^{-1}\left(  j+1\right)  $. We need to prove
(\ref{pf.lem.only-id.tFinc1}).
\par
Let us (for the sake of contradiction) assume the contrary. Thus, not every
$k\in\left\{  0,1,\ldots,n\right\}  $ satisfies $\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  j\right)  ,k}\right)  \leq\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  j+1\right)  ,k}\right)  $. In other words, not every
$k\in\left\{  0,1,\ldots,n\right\}  $ satisfies $\mathbf{t}\left(
F_{\mathfrak{u},k}\right)  \leq\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  $
(because $\mathfrak{u}=\mathbf{j}^{-1}\left(  j\right)  $ and $\mathfrak{v}%
=\mathbf{j}^{-1}\left(  j+1\right)  $). In other words, there exists a
$k\in\left\{  0,1,\ldots,n\right\}  $ such that $\mathbf{t}\left(
F_{\mathfrak{u},k}\right)  >\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  $.
Let $\ell$ be the \textbf{highest} such $k$. Thus, $\ell$ is a $k\in\left\{
0,1,\ldots,n\right\}  $ such that $\mathbf{t}\left(  F_{\mathfrak{u}%
,k}\right)  >\mathbf{t}\left(  F_{\mathfrak{v},k}\right)  $. Hence, $\ell$
belongs to $\left\{  0,1,\ldots,n\right\}  $ and satisfies $\mathbf{t}\left(
F_{\mathfrak{u},\ell}\right)  >\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)
$. We have $\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)  \geq
\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  +1$ (since $\mathbf{t}\left(
F_{\mathfrak{u},\ell}\right)  $ and $\mathbf{t}\left(  F_{\mathfrak{v},\ell
}\right)  $ are integers and satisfy $\mathbf{t}\left(  F_{\mathfrak{u},\ell
}\right)  >\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  $). In other words,
$\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  +1\leq\mathbf{t}\left(
F_{\mathfrak{u},\ell}\right)  $.
\par
Let us first assume (for the sake of contradiction) that $\ell=n$. Then,
$F_{\mathfrak{u},\ell}=F_{\mathfrak{u},n}=Q_{j_{\mathfrak{u}}}$ (by
(\ref{11.Fin}), applied to $i=\mathfrak{u}$). But the definition of
$\mathbf{j}\left(  \mathfrak{u}\right)  $ yields $\mathbf{j}\left(
\mathfrak{u}\right)  =j_{\mathfrak{u}}$, so that $j_{\mathfrak{u}}%
=\mathbf{j}\left(  \mathfrak{u}\right)  =j$ (since $\mathfrak{u}%
=\mathbf{j}^{-1}\left(  j\right)  $) and thus $Q_{j_{\mathfrak{u}}}=Q_{j}$.
Also, from $\ell=n$, we obtain $F_{\mathfrak{v},\ell}=F_{\mathfrak{v}%
,n}=Q_{j_{\mathfrak{v}}}$ (by (\ref{11.Fin}), applied to $i=\mathfrak{v}$).
But the definition of $\mathbf{j}\left(  \mathfrak{v}\right)  $ yields
$\mathbf{j}\left(  \mathfrak{v}\right)  =j_{\mathfrak{v}}$, so that
$j_{\mathfrak{v}}=\mathbf{j}\left(  \mathfrak{v}\right)  =j+1$ (since
$\mathfrak{v}=\mathbf{j}^{-1}\left(  j+1\right)  $) and thus
$Q_{j_{\mathfrak{v}}}=Q_{j+1}$. But $\mathbf{t}\left(  Q_{j}\right)
<\mathbf{t}\left(  Q_{j+1}\right)  $ (by (\ref{11.tQinc})). Now,
$\mathbf{t}\left(  \underbrace{F_{\mathfrak{u},\ell}}_{=Q_{j_{\mathfrak{u}}%
}=Q_{j}}\right)  =\mathbf{t}\left(  Q_{j}\right)  <\mathbf{t}\left(
Q_{j+1}\right)  $ contradicts $\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)
>\mathbf{t}\left(  \underbrace{F_{\mathfrak{v},\ell}}_{=Q_{j_{\mathfrak{v}}%
}=Q_{j+1}}\right)  =\mathbf{t}\left(  Q_{j+1}\right)  $. This contradiction
proves that our assumption (that $\ell=n$) was wrong. Hence, we cannot have
$\ell=n$.
\par
Thus, $\ell<n$ (since $\ell\leq n$ but not $\ell=n$) and $0\leq\ell$ (since
$\ell\in\left\{  0,1,\ldots,n\right\}  $). Hence, $0\leq\ell<n$, so that
$\ell\in\left\{  0,1,\ldots,n-1\right\}  $ and thus $\ell+1\in\left\{
1,2,\ldots,n\right\}  \subseteq\left\{  0,1,\ldots,n\right\}  $. Therefore,
(\ref{pf.lem.only-id.tFuk}) (applied to $k=\ell+1$) yields $\mathbf{t}\left(
F_{\mathfrak{u},\ell+1}\right)  \neq\mathbf{t}\left(  F_{\mathfrak{v},\ell
+1}\right)  $. In other words, $\mathbf{t}\left(  F_{\mathfrak{v},\ell
+1}\right)  \neq\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  $.
\par
But $\ell\in\left\{  0,1,\ldots,n-1\right\}  $. Thus, (\ref{11.Fik}) (applied
to $k=\mathfrak{u}$ and $i=\ell$) shows that the pair $\left(  F_{\mathfrak{u}%
,\ell},F_{\mathfrak{u},\ell+1}\right)  $ is an arc of the directed graph $G$.
Therefore, (\ref{11.tVU}) (applied to $U=F_{\mathfrak{u},\ell}$ and
$V=F_{\mathfrak{u},\ell+1}$) shows that $\mathbf{t}\left(  F_{\mathfrak{u}%
,\ell}\right)  -1\leq\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)
\leq\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)  +1$. The same argument
(but with every $\mathfrak{u}$ replaced by $\mathfrak{v}$) yields
$\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  -1\leq\mathbf{t}\left(
F_{\mathfrak{v},\ell+1}\right)  \leq\mathbf{t}\left(  F_{\mathfrak{v},\ell
}\right)  +1$. Thus, $\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)
\leq\mathbf{t}\left(  F_{\mathfrak{v},\ell}\right)  +1\leq\mathbf{t}\left(
F_{\mathfrak{u},\ell}\right)  \leq\mathbf{t}\left(  F_{\mathfrak{u},\ell
+1}\right)  +1$ (since $\mathbf{t}\left(  F_{\mathfrak{u},\ell}\right)
-1\leq\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  $). Combined with
$\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  \neq\mathbf{t}\left(
F_{\mathfrak{u},\ell+1}\right)  +1$ (which is a consequence of
(\ref{pf.lem.only-id.tFvk}), applied to $\ell+1$ instead of $k$), this yields
$\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  <\mathbf{t}\left(
F_{\mathfrak{u},\ell+1}\right)  +1$. Since $\mathbf{t}\left(  F_{\mathfrak{v}%
,\ell+1}\right)  $ and $\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  +1$
are integers, this yields $\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)
\leq\left(  \mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  +1\right)
-1=\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  $.
\par
Combined with $\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)
\neq\mathbf{t}\left(  F_{\mathfrak{u},\ell+1}\right)  $, this yields
$\mathbf{t}\left(  F_{\mathfrak{v},\ell+1}\right)  <\mathbf{t}\left(
F_{\mathfrak{u},\ell+1}\right)  $. In other words, $\mathbf{t}\left(
F_{\mathfrak{u},\ell+1}\right)  >\mathbf{t}\left(  F_{\mathfrak{v},\ell
+1}\right)  $. Hence, $\ell+1$ is a $k\in\left\{  0,1,\ldots,n\right\}  $ such
that $\mathbf{t}\left(  F_{\mathfrak{u},k}\right)  >\mathbf{t}\left(
F_{\mathfrak{v},k}\right)  $. Since the highest such $k$ is $\ell$ (by the
definition of $\ell$), this yields that $\ell+1\leq\ell$. But this contradicts
$\ell+1>\ell$. This contradiction shows that our assumption was wrong. Hence,
(\ref{pf.lem.only-id.tFinc1}) is proven.} Consequently, if $k\in\left\{
0,1,\ldots,n\right\}  $, then%
\begin{equation}
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  1\right)  ,k}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  2\right)  ,k}\right)
<\cdots<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  N\right)  ,k}\right)  .
\label{pf.lem.only-id.tFstrinc1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.only-id.tFstrinc1}):} Let
$k\in\left\{  0,1,\ldots,n\right\}  $. Let $j\in\left\{  1,2,\ldots
,N-1\right\}  $. Now, (\ref{pf.lem.only-id.tFinc1}) yields $\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  j\right)  ,k}\right)  \leq\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  j+1\right)  ,k}\right)  $. But $\mathbf{j}\left(
\mathbf{j}^{-1}\left(  j\right)  \right)  =j\neq j+1=\mathbf{j}\left(
\mathbf{j}^{-1}\left(  j+1\right)  \right)  $, so that $\mathbf{j}^{-1}\left(
j\right)  \neq\mathbf{j}^{-1}\left(  j+1\right)  $. In other words, the
positive integers $\mathbf{j}^{-1}\left(  j\right)  $ and $\mathbf{j}%
^{-1}\left(  j+1\right)  $ are distinct. Thus, (\ref{pf.lem.only-id.tFuk})
(applied to $\mathfrak{u}=\mathbf{j}^{-1}\left(  j\right)  $ and
$\mathfrak{v}=\mathbf{j}^{-1}\left(  j+1\right)  $) yields $\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  j\right)  ,k}\right)  \neq\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  j+1\right)  ,k}\right)  $. Combined with
$\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j\right)  ,k}\right)
\leq\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j+1\right)  ,k}\right)  $,
this yields $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j\right)  ,k}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j+1\right)  ,k}\right)  $.
\par
Now, let us forget that we fixed $j\in\left\{  1,2,\ldots,N-1\right\}  $.
Thus, we have shown that $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(
j\right)  ,k}\right)  <\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  j+1\right)
,k}\right)  $ for every $j\in\left\{  1,2,\ldots,N-1\right\}  $. In other
words, $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  1\right)  ,k}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  2\right)  ,k}\right)
<\cdots<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  N\right)  ,k}\right)  $.
This proves (\ref{pf.lem.only-id.tFstrinc1}).}

Now, let us show a chain of inequalities analogous to (\ref{11.tQinc}).
Namely, we have%
\begin{equation}
\mathbf{t}\left(  P_{1}\right)  <\mathbf{t}\left(  P_{2}\right)
<\cdots<\mathbf{t}\left(  P_{N}\right)  . \label{pf.lem.only-id.tPinc}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.only-id.tPinc}):} Let $i\in\left\{
1,2,\ldots,N-1\right\}  $. We will now show that $\mathbf{t}\left(
P_{i}\right)  <\mathbf{t}\left(  P_{i+1}\right)  $.
\par
The definition of $P_{i}$ yields $P_{i}=\left(  \left(  i-1\right)  -\mu
_{i}^{\prime},-\left(  i-1\right)  +\mu_{i}^{\prime}\right)  $, so that
$\mathbf{t}\left(  P_{i}\right)  =\mathbf{t}\left(  \left(  \left(
i-1\right)  -\mu_{i}^{\prime},-\left(  i-1\right)  +\mu_{i}^{\prime}\right)
\right)  =\left(  \left(  i-1\right)  -\mu_{i}^{\prime}\right)  -\left(
-\left(  i-1\right)  +\mu_{i}^{\prime}\right)  =2\left(  i-1\right)  -2\mu
_{i}^{\prime}$. The same argument (applied to $i+1$ instead of $i$) yields
$\mathbf{t}\left(  P_{i+1}\right)  =2\left(  \left(  i+1\right)  -1\right)
-2\mu_{i+1}^{\prime}$. But $\mu^{\prime}$ is a partition, and thus we have
$\mu_{1}^{\prime}\geq\mu_{2}^{\prime}\geq\mu_{3}^{\prime}\geq\cdots$. Hence,
$\mu_{i}^{\prime}\geq\mu_{i+1}^{\prime}$. Now,%
\[
\mathbf{t}\left(  P_{i}\right)  =2\left(  \underbrace{i}_{<i+1}-1\right)
-2\underbrace{\mu_{i}^{\prime}}_{\geq\mu_{i+1}^{\prime}}<2\left(  \left(
i+1\right)  -1\right)  -2\mu_{i+1}^{\prime}=\mathbf{t}\left(  P_{i+1}\right)
.
\]
\par
Let us now forget that we fixed $i$. We thus have proven that $\mathbf{t}%
\left(  P_{i}\right)  <\mathbf{t}\left(  P_{i+1}\right)  $ for every
$i\in\left\{  1,2,\ldots,N-1\right\}  $. In other words, $\mathbf{t}\left(
P_{1}\right)  <\mathbf{t}\left(  P_{2}\right)  <\cdots<\mathbf{t}\left(
P_{N}\right)  $. This proves (\ref{pf.lem.only-id.tPinc}).}

On the other hand, we have%
\begin{equation}
F_{i,0}=P_{i}\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{  1,2,\ldots
,N\right\}  . \label{pf.lem.only-id.Fi0}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.only-id.Fi0}):} Let $i\in\left\{
1,2,\ldots,N\right\}  $. Then, $P_{i}$ is a point on the path $\pi_{ij_{i}}$
(since $\pi_{ij_{i}}$ is a path from $P_{i}$ to $Q_{j_{i}}$) and satisfies
$\mathbf{d}\left(  P_{i}\right)  =0$ (by (\ref{11.dPi})). Hence, $P_{i}$ is a
point $F$ on the path $\pi_{ij_{i}}$ such that $\mathbf{d}\left(  F\right)
=0$. But we know (from (\ref{11.F}), applied to $k=0$) that there exists
exactly one such point; and we have denoted this point by $F_{i,0}$.
Therefore, $P_{i}=F_{i,0}$. This proves (\ref{pf.lem.only-id.Fi0}).} Hence,
using (\ref{pf.lem.only-id.tFstrinc1}), we can easily see that%
\begin{equation}
\mathbf{t}\left(  P_{\mathbf{j}^{-1}\left(  1\right)  }\right)  <\mathbf{t}%
\left(  P_{\mathbf{j}^{-1}\left(  2\right)  }\right)  <\cdots<\mathbf{t}%
\left(  P_{\mathbf{j}^{-1}\left(  N\right)  }\right)  .
\label{pf.lem.only-id.tPstrinc1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.only-id.tPstrinc1}):} Applying
(\ref{pf.lem.only-id.tFstrinc1}) to $k=0$, we obtain%
\begin{equation}
\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  1\right)  ,0}\right)
<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  2\right)  ,0}\right)
<\cdots<\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  N\right)  ,0}\right)
\label{pf.lem.only-id.tPstrinc1.pf.1}%
\end{equation}
(since $0\in\left\{  0,1,\ldots,n\right\}  $).
\par
Now, fix $\ell\in\left\{  1,2,\ldots,N-1\right\}  $. Then, $\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  \ell\right)  ,0}\right)  <\mathbf{t}\left(
F_{\mathbf{j}^{-1}\left(  \ell+1\right)  ,0}\right)  $ (because of
(\ref{pf.lem.only-id.tPstrinc1.pf.1})). But $\ell\in\left\{  1,2,\ldots
,N-1\right\}  \subseteq\left\{  1,2,\ldots,N\right\}  $, so that
$\mathbf{j}^{-1}\left(  \ell\right)  \in\left\{  1,2,\ldots,N\right\}  $;
hence, (\ref{pf.lem.only-id.Fi0}) (applied to $i=\mathbf{j}^{-1}\left(
\ell\right)  $) yields $F_{\mathbf{j}^{-1}\left(  \ell\right)  ,0}%
=P_{\mathbf{j}^{-1}\left(  \ell\right)  }$. Also, from $\ell\in\left\{
1,2,\ldots,N-1\right\}  $, we obtain $\ell+1\in\left\{  1,2,\ldots,N\right\}
$, so that $\mathbf{j}^{-1}\left(  \ell+1\right)  \in\left\{  1,2,\ldots
,N\right\}  $; hence, (\ref{pf.lem.only-id.Fi0}) (applied to $i=\mathbf{j}%
^{-1}\left(  \ell+1\right)  $) yields $F_{\mathbf{j}^{-1}\left(
\ell+1\right)  ,0}=P_{\mathbf{j}^{-1}\left(  \ell+1\right)  }$.
\par
Now, recall that $\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  \ell\right)
,0}\right)  <\mathbf{t}\left(  F_{\mathbf{j}^{-1}\left(  \ell+1\right)
,0}\right)  $. This rewrites as $\mathbf{t}\left(  P_{\mathbf{j}^{-1}\left(
\ell\right)  }\right)  <\mathbf{t}\left(  P_{\mathbf{j}^{-1}\left(
\ell+1\right)  }\right)  $ (since $F_{\mathbf{j}^{-1}\left(  \ell\right)
,0}=P_{\mathbf{j}^{-1}\left(  \ell\right)  }$ and $F_{\mathbf{j}^{-1}\left(
\ell+1\right)  ,0}=P_{\mathbf{j}^{-1}\left(  \ell+1\right)  }$).
\par
Forget that we fixed $\ell$. We thus have proved that $\mathbf{t}\left(
P_{\mathbf{j}^{-1}\left(  \ell\right)  }\right)  <\mathbf{t}\left(
P_{\mathbf{j}^{-1}\left(  \ell+1\right)  }\right)  $ for each $\ell\in\left\{
1,2,\ldots,N-1\right\}  $. In other words,%
\[
\mathbf{t}\left(  P_{\mathbf{j}^{-1}\left(  1\right)  }\right)  <\mathbf{t}%
\left(  P_{\mathbf{j}^{-1}\left(  2\right)  }\right)  <\cdots<\mathbf{t}%
\left(  P_{\mathbf{j}^{-1}\left(  N\right)  }\right)  .
\]
This proves (\ref{pf.lem.only-id.tPstrinc1}).}

Now, let us fix some $k\in\left\{  1,2,\ldots,N-1\right\}  $. We shall show
that $\mathbf{j}\left(  k\right)  \leq\mathbf{j}\left(  k+1\right)  $.

Indeed, assume the contrary. Thus, $\mathbf{j}\left(  k\right)  >\mathbf{j}%
\left(  k+1\right)  $. Set $\mathfrak{u}=\mathbf{j}\left(  k\right)  $ and
$\mathfrak{v}=\mathbf{j}\left(  k+1\right)  $. Thus, $\mathfrak{u}%
=\mathbf{j}\left(  k\right)  >\mathbf{j}\left(  k+1\right)  =\mathfrak{v}$
(since $\mathfrak{v}=\mathbf{j}\left(  k+1\right)  $), so that $\mathfrak{v}%
<\mathfrak{u}$. Furthermore, $\mathbf{j}^{-1}\left(  \mathfrak{v}\right)
=k+1$ (since $\mathfrak{v}=\mathbf{j}\left(  k+1\right)  $) and $\mathbf{j}%
^{-1}\left(  \mathfrak{u}\right)  =k$ (since $\mathfrak{u}=\mathbf{j}\left(
k\right)  $).

But (\ref{pf.lem.only-id.tPstrinc1}) yields $\mathbf{t}\left(  P_{\mathbf{j}%
^{-1}\left(  \mathfrak{p}\right)  }\right)  <\mathbf{t}\left(  P_{\mathbf{j}%
^{-1}\left(  \mathfrak{q}\right)  }\right)  $ whenever $\mathfrak{p}$ and
$\mathfrak{q}$ are two elements of $\left\{  1,2,\ldots,N\right\}  $
satisfying $\mathfrak{p}<\mathfrak{q}$. Applying this to $\mathfrak{p}%
=\mathfrak{v}$ and $\mathfrak{q}=\mathfrak{u}$, we obtain $\mathbf{t}\left(
P_{\mathbf{j}^{-1}\left(  \mathfrak{v}\right)  }\right)  <\mathbf{t}\left(
P_{\mathbf{j}^{-1}\left(  \mathfrak{u}\right)  }\right)  $ (since
$\mathfrak{v}<\mathfrak{u}$). This rewrites as $\mathbf{t}\left(
P_{k+1}\right)  <\mathbf{t}\left(  P_{k}\right)  $ (since $\mathbf{j}%
^{-1}\left(  \mathfrak{v}\right)  =k+1$ and $\mathbf{j}^{-1}\left(
\mathfrak{u}\right)  =k$).

But (\ref{pf.lem.only-id.tPinc}) yields $\mathbf{t}\left(  P_{k}\right)
<\mathbf{t}\left(  P_{k+1}\right)  $. This contradicts $\mathbf{t}\left(
P_{k+1}\right)  <\mathbf{t}\left(  P_{k}\right)  $. This contradiction shows
that our assumption was false. Hence, $\mathbf{j}\left(  k\right)
\leq\mathbf{j}\left(  k+1\right)  $ is proven.

Now, forget that we fixed $k$. We thus have shown that $\mathbf{j}\left(
k\right)  \leq\mathbf{j}\left(  k+1\right)  $ for each $k\in\left\{
1,2,\ldots,N-1\right\}  $. In other words, $\mathbf{j}\left(  1\right)
\leq\mathbf{j}\left(  2\right)  \leq\cdots\leq\mathbf{j}\left(  N\right)  $.

But it is well-known (and easy to see) that the only permutation $\sigma$ of
$\left\{  1,2,\ldots,N\right\}  $ that satisfies $\sigma\left(  1\right)
\leq\sigma\left(  2\right)  \leq\cdots\leq\sigma\left(  N\right)  $ is the
identity permutation $\operatorname*{id}$. In other words, if $\sigma$ is a
permutation of $\left\{  1,2,\ldots,N\right\}  $ that satisfies $\sigma\left(
1\right)  \leq\sigma\left(  2\right)  \leq\cdots\leq\sigma\left(  N\right)  $,
then $\sigma=\operatorname*{id}$. Applying this to $\sigma=\mathbf{j}$, we
obtain $\mathbf{j}=\operatorname*{id}$ (since $\mathbf{j}$ is a permutation of
$\left\{  1,2,\ldots,N\right\}  $ that satisfies $\mathbf{j}\left(  1\right)
\leq\mathbf{j}\left(  2\right)  \leq\cdots\leq\mathbf{j}\left(  N\right)  $).
Hence, each $i\in\left\{  1,2,\ldots,N\right\}  $ satisfies%
\[
\underbrace{\mathbf{j}}_{=\operatorname*{id}}\left(  i\right)
=\operatorname*{id}\left(  i\right)  =i
\]
and therefore $i=\mathbf{j}\left(  i\right)  =j_{i}$ (by the definition of
$\mathbf{j}$). In other words, $\left(  1,2,\ldots,N\right)  =\left(
j_{1},j_{2},\ldots,j_{N}\right)  $. This proves Lemma \ref{lem.only-id}.
\end{proof}


\end{document}