Pelletier–Ressayre hidden symmetry page 0

# The Pelletier–Ressayre hidden symmetry for Littlewood–Richardson
coefficients

Darij Grinberg

###### Abstract

Abstract. We prove an identity for Littlewood–Richardson coefficients
conjectured by Pelletier and Ressayre. The proof relies on a novel birational
involution defined over any semifield.

Keywords: symmetric functions, Schur functions, Schur polynomials,
Littlewood–Richardson coefficients, birational combinatorics,
detropicalization, partitions.

MSC2010 Mathematics Subject Classifications: 05E05.

###### Contents

  1. 1 Notations
  2. 2 The theorem
  3. 3 A birational involution
    1. 3.1 Semifields
    2. 3.2 The birational involution
  4. 4 Proof of the main theorem
    1. 4.1 From the life of snakes
    2. 4.2 $h_{k}^{+}$, $h_{k}^{-}$ and the Pieri rule
    3. 4.3 Computing $\overline{s}_{\alpha}$
    4. 4.4 The sets $R_{\mu,a,b}\left(\gamma\right)$ and a formula for $h_{a}^{-}h_{b}^{+}\overline{s}_{\mu}$
    5. 4.5 The map $\mathbf{f}_{\mu}$
    6. 4.6 The finale
  5. 5 Final remarks
    1. 5.1 Aside: A Jacobi–Trudi formula for Schur Laurent polynomials
    2. 5.2 Questions on $\mathbf{f}_{u}$
    3. 5.3 On the genesis of $\varphi$ (and $\mathbf{f}_{u}$)
    4. 5.4 The birational $R$-matrix connection

## ***

One of the central concepts in the theory of symmetric functions are the
Littlewood–Richardson coefficients $c_{\mu,\nu}^{\lambda}$: the coefficients
when a product $s_{\mu}s_{\nu}$ of two Schur functions is expanded back in the
Schur basis $\left(s_{\lambda}\right)_{\lambda\in\operatorname*{Par}}$.
Various properties of these coefficients have been found, among them
combinatorial interpretations, vanishing results, bounds and symmetries (i.e.,
equalities between $c_{\mu,\nu}^{\lambda}$ for different $\lambda,\mu,\nu$). A
recent overview of the latter can be found in [BriRos20].

In [PelRes20], Pelletier and Ressayre conjectured a further symmetry of
Littlewood–Richardson coefficients. Unless the classical ones, it is a partial
symmetry (i.e., it does not cover every Littlewood–Richardson coefficient); it
is furthermore much less simple to state, to the extent that Pelletier and
Ressayre have conjectured its existence while leaving open the question which
exact coefficients it matches up. In this paper, we answer this question and
prove the conjecture thus concretized.

The conjecture, in its original (unconcrete) form, can be stated as follows:
Let $n\geq 2$, and consider the set $\operatorname*{Par}\left[n\right]$ of all
partitions having length $\leq n$. Let $a$ and $b$ be two nonnegative
integers, and define the two partitions $\alpha=\left(a+b,a^{n-2}\right)$ and
$\beta=\left(a+b,b^{n-2}\right)$ (where $c^{n-2}$ means
$\underbrace{c,c,\ldots,c}_{n-2\text{ times}}$, as usual in partition
combinatorics). Fix another partition
$\mu\in\operatorname*{Par}\left[n\right]$. Then, the families
$\left(c_{\alpha,\mu}^{\omega}\right)_{\omega\in\operatorname*{Par}\left[n\right]}$
and
$\left(c_{\beta,\mu}^{\omega}\right)_{\omega\in\operatorname*{Par}\left[n\right]}$
of Littlewood–Richardson coefficients seem to be identical up to permutation.
(We can restate this in terms of Schur polynomials in the $n$ variables
$x_{1},x_{2},\ldots,x_{n}$; this then becomes the claim that the products
$s_{\alpha}\left(x_{1},x_{2},\ldots,x_{n}\right)\cdot
s_{\mu}\left(x_{1},x_{2},\ldots,x_{n}\right)$ and
$s_{\beta}\left(x_{1},x_{2},\ldots,x_{n}\right)\cdot
s_{\mu}\left(x_{1},x_{2},\ldots,x_{n}\right)$, when expanded in the basis of
Schur polynomials, have the same multiset of coefficients.)

Pelletier and Ressayre have proved this conjecture for $n=3$ (see [PelRes20,
Corollary 2]) and in some further cases. We shall prove it in full generality,
and construct what is essentially a bijection
$\varphi:\operatorname*{Par}\left[n\right]\rightarrow\operatorname*{Par}\left[n\right]$
that makes it explicit (i.e., that satisfies
$c_{\alpha,\mu}^{\omega}=c_{\beta,\mu}^{\varphi\left(\omega\right)}$ for each
$\omega\in\operatorname*{Par}\left[n\right]$). To be fully precise, $\varphi$
will not be a bijection
$\operatorname*{Par}\left[n\right]\rightarrow\operatorname*{Par}\left[n\right]$,
but rather a bijection from $\mathbb{Z}^{n}$ to $\mathbb{Z}^{n}$, and it will
satisfy $c_{\alpha,\mu}^{\omega}=c_{\beta,\mu}^{\varphi\left(\omega\right)}$
with the understanding that $c_{\alpha,\mu}^{\omega}=c_{\beta,\mu}^{\omega}=0$
when $\omega\notin\operatorname*{Par}\left[n\right]$. (Here,
$\operatorname*{Par}\left[n\right]$ is understood to be a subset of
$\mathbb{Z}^{n}$ by identifying each partition
$\lambda\in\operatorname*{Par}\left[n\right]$ with the $n$-tuple
$\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)$.)

We will define this bijection $\varphi$ by explicit (if somewhat intricate)
formulas that “mingle” the entries of the partition it is being applied to
with those of $\mu$ (as well as $a$ and $b$) using the $\min$ and $+$
operators. These formulas are best understood in the birational picture, in
which these $\min$ and $+$ operators are generalized to the addition and the
multiplication of an arbitrary semifield. (Our proof does not require this
generality, but the birational picture has the advantage of greater
familiarity and better notational support. It also suggests a possible
connection with the notion of a geometric crystal – see Question
LABEL:quest.cryst for details –, which could throw some light on the otherwise
rather mysterious bijection.)

Another ingredient of our proof is an explicit formula for
$s_{\alpha}\left(x_{1},x_{2},\ldots,x_{n}\right)$ for the above-mentioned
partition $\alpha$.

#### Acknowledgments

I thank Sunita Chepuri, Grigori Olshanski, Pasha Pylyavskyy and Tom Roby for
interesting and helpful conversations.

Parts of this paper were written at the Mathematisches Forschungsinstitut
Oberwolfach, where I was staying as a Leibniz fellow in Summer 2020. The
SageMath computer algebra system [SageMath] has been used in discovering some
of the results.

### Remark on alternative versions

This paper also has a detailed version [Grinbe20], which includes some proofs
that have been omitted from the present version (mostly basic properties of
symmetric functions).

An older version of this paper appeared as Oberwolfach Preprint OWP-2020-18.

##  1 Notations

We will use the following notations (most of which are also used in [GriRei20,
§2.1]):

  * •

We let $\mathbb{N}=\left\\{0,1,2,\ldots\right\\}$.

  * •

We fix a commutative ring $\mathbf{k}$; we will use this $\mathbf{k}$ as the
base ring in what follows.

  * •

A _weak composition_ means an infinite sequence of nonnegative integers that
contains only finitely many nonzero entries (i.e., a sequence
$\left(\alpha_{1},\alpha_{2},\alpha_{3},\ldots\right)\in\mathbb{N}^{\infty}$
such that all but finitely many $i\in\left\\{1,2,3,\ldots\right\\}$ satisfy
$\alpha_{i}=0$).

  * •

We let $\operatorname*{WC}$ denote the set of all weak compositions.

  * •

For any weak composition $\alpha$ and any positive integer $i$, we let
$\alpha_{i}$ denote the $i$-th entry of $\alpha$ (so that
$\alpha=\left(\alpha_{1},\alpha_{2},\alpha_{3},\ldots\right)$). More
generally, we use this notation whenever $\alpha$ is an infinite sequence of
any kind of objects.

  * •

The _size_ $\left|\alpha\right|$ of a weak composition $\alpha$ is defined to
be $\alpha_{1}+\alpha_{2}+\alpha_{3}+\cdots\in\mathbb{N}$.

  * •

A _partition_ means a weak composition whose entries weakly decrease (i.e., a
weak composition $\alpha$ satisfying
$\alpha_{1}\geq\alpha_{2}\geq\alpha_{3}\geq\cdots$).

  * •

We let $\operatorname*{Par}$ denote the set of all partitions.

  * •

We will sometimes omit trailing zeroes from partitions: i.e., a partition
$\lambda=\left(\lambda_{1},\lambda_{2},\lambda_{3},\ldots\right)$ will be
identified with the $k$-tuple
$\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)$ whenever
$k\in\mathbb{N}$ satisfies
$\lambda_{k+1}=\lambda_{k+2}=\lambda_{k+3}=\cdots=0$. For example,
$\left(3,2,1,0,0,0,\ldots\right)=\left(3,2,1\right)=\left(3,2,1,0\right)$.

As a consequence of this, an $n$-tuple
$\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)\in\mathbb{Z}^{n}$
(for any given $n\in\mathbb{N}$) is a partition if and only if it satisfies
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq 0$.

  * •

A _part_ of a partition $\lambda$ means a nonzero entry of $\lambda$. For
example, the parts of the partition
$\left(3,1,1\right)=\left(3,1,1,0,0,0,\ldots\right)$ are $3,1,1$.

  * •

The _length_ of a partition $\lambda$ means the smallest $k\in\mathbb{N}$ such
that $\lambda_{k+1}=\lambda_{k+2}=\lambda_{k+3}=\cdots=0$. Equivalently, the
length of a partition $\lambda$ is the number of parts of $\lambda$ (counted
with multiplicity). This length is denoted by $\ell\left(\lambda\right)$. For
example,
$\ell\left(\left(4,2,0,0\right)\right)=\ell\left(\left(4,2\right)\right)=2$
and $\ell\left(\left(5,1,1\right)\right)=3$.

  * •

We will use the notation $m^{k}$ for “$\underbrace{m,m,\ldots,m}_{k\text{
times}}$” in partitions and tuples (whenever $m\in\mathbb{N}$ and
$k\in\mathbb{N}$). (For example,
$\left(2,1^{4}\right)=\left(2,1,1,1,1\right)$.)

  * •

We let $\Lambda$ denote the ring of symmetric functions in infinitely many
variables $x_{1},x_{2},x_{3},\ldots$ over $\mathbf{k}$. This is a subring of
the ring $\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ of
formal power series. To be more specific, $\Lambda$ consists of all power
series in $\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ that
are symmetric (i.e., invariant under permutations of the variables) and of
bounded degree (see [GriRei20, §2.1] for the precise meaning of this).

  * •

A _monomial_ shall mean a formal expression of the form
$x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}x_{3}^{\alpha_{3}}\cdots$ with
$\alpha\in\operatorname*{WC}$. Formal power series are formal infinite
$\mathbf{k}$-linear combinations of such monomials.

  * •

For any weak composition $\alpha$, we let $\mathbf{x}^{\alpha}$ denote the
monomial $x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}x_{3}^{\alpha_{3}}\cdots$.

  * •

The _degree_ of a monomial $\mathbf{x}^{\alpha}$ is defined to be
$\left|\alpha\right|$.

We shall use the symmetric functions $h_{n}$ and $s_{\lambda}$ in $\Lambda$ as
defined in [GriRei20, Sections 2.1 and 2.2]. Let us briefly recall how they
are defined:

  * •

For each $n\in\mathbb{Z}$, we define the _complete homogeneous symmetric
function_ $h_{n}\in\Lambda$ by

$h_{n}=\sum\limits_{i_{1}\leq i_{2}\leq\cdots\leq
i_{n}}x_{i_{1}}x_{i_{2}}\cdots
x_{i_{n}}=\sum\limits_{\begin{subarray}{c}\alpha\in\operatorname*{WC};\\\
\left|\alpha\right|=n\end{subarray}}\mathbf{x}^{\alpha}.$

Thus, $h_{0}=1$ and $h_{n}=0$ for all $n<0$.

  * •

For each partition $\lambda$, we define the _Schur function_
$s_{\lambda}\in\Lambda$ by

$s_{\lambda}=\sum\limits\mathbf{x}_{T},$

where the sum ranges over all semistandard tableaux $T$ of shape $\lambda$,
and where $\mathbf{x}_{T}$ denotes the monomial obtained by multiplying the
$x_{i}$ for all entries $i$ of $T$. We refer the reader to [GriRei20,
Definition 2.2.1] or to [Stanle01, §7.10] for the details of this definition
and further descriptions of the Schur functions.

The family $\left(s_{\lambda}\right)_{\lambda\in\operatorname*{Par}}$ is a
basis of the $\mathbf{k}$-module $\Lambda$, and is known as the _Schur basis_.
It is easy to see that each $n\in\mathbb{N}$ satisfies
$s_{\left(n\right)}=h_{n}$.

  * •

We shall use the _Littlewood–Richardson coefficients_ $c_{\mu,\nu}^{\lambda}$
(for $\lambda,\mu,\nu\in\operatorname*{Par}$), as defined in [GriRei20,
Definition 2.5.8], in [Stanle01, §7.15] or in [Egge19, Chapter 10]. One of
their defining properties is the following fact (see, e.g., [GriRei20,
(2.5.6)] or [Stanle01, (7.64)] or [Egge19, (10.1)]): Any two partitions
$\mu,\nu\in\operatorname*{Par}$ satisfy

$s_{\mu}s_{\nu}=\sum\limits_{\lambda\in\operatorname*{Par}}c_{\mu,\nu}^{\lambda}s_{\lambda}.$
(1)

##  2 The theorem

######  Convention 2.1.

  1. (a)

For the rest of this paper, we fix a positive integer $n$.

  2. (b)

Let $\operatorname*{Par}\left[n\right]$ be the set of all partitions having
length $\leq n$. In other words,

$\displaystyle\operatorname*{Par}\left[n\right]$
$\displaystyle=\left\\{\lambda\in\operatorname*{Par}\ \mid\
\lambda=\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)\right\\}=\operatorname*{Par}\cap\mathbb{N}^{n}$
$\displaystyle=\left\\{\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)\in\mathbb{Z}^{n}\
\mid\ \lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq 0\right\\}$

(where we are using our convention that trailing zeroes can be omitted from
partitions, so that a partition of length $\leq n$ can always be identified
with an $n$-tuple).

  3. (c)

A family $\left(u_{i}\right)_{i\in\mathbb{Z}}$ of objects (e.g., of numbers)
is said to be $n$_-periodic_ if each $j\in\mathbb{Z}$ satisfies
$u_{j}=u_{j+n}$. Equivalently, a family $\left(u_{i}\right)_{i\in\mathbb{Z}}$
of objects is $n$-periodic if and only if it has the property that

$\left(u_{j}=u_{j^{\prime}}\text{ whenever }j\text{ and }j^{\prime}\text{ are
two integers satisfying }j\equiv j^{\prime}\operatorname{mod}n\right).$

Thus, an $n$-periodic family $\left(u_{i}\right)_{i\in\mathbb{Z}}$ is uniquely
determined by the $n$ entries $u_{1},u_{2},\ldots,u_{n}$ (because for any
integer $j$, we have $u_{j}=u_{j^{\prime}}$, where $j^{\prime}$ is the unique
element of $\left\\{1,2,\ldots,n\right\\}$ that is congruent to $j$ modulo
$n$).

######  Example 2.1.

If $n=3$, then both partitions $\left(3,2\right)$ and $\left(3,2,2\right)$
belong to $\operatorname*{Par}\left[n\right]$, while the partition
$\left(3,2,2,2\right)$ does not. The $n$-tuples $\left(4,2,1\right)$ and
$\left(3,3,0\right)$ are partitions, while the $n$-tuples
$\left(1,0,-1\right)$ and $\left(2,0,1\right)$ are not.

If $\zeta$ is an $n$-th root of unity, then the family
$\left(\zeta^{i}\right)_{i\in\mathbb{Z}}$ of complex numbers is $n$-periodic.

We can now state our main theorem, which is a concretization of [PelRes20,
Conjecture 1]:

######  Theorem 2.2.

Assume that $n\geq 2$. Let $a,b\in\mathbb{N}$.

Define the two partitions $\alpha=\left(a+b,a^{n-2}\right)$ and
$\beta=\left(a+b,b^{n-2}\right)$.

Fix any partition $\mu\in\operatorname*{Par}\left[n\right]$.

Define a map $\varphi:\mathbb{Z}^{n}\rightarrow\mathbb{Z}^{n}$ as follows:

Let $\omega\in\mathbb{Z}^{n}$. Define an $n$-tuple
$\nu=\left(\nu_{1},\nu_{2},\ldots,\nu_{n}\right)\in\mathbb{Z}^{n}$ by
$\nu_{i}=\omega_{i}-a$ for each $i\in\left\\{1,2,\ldots,n\right\\}$, where
$\omega_{i}$ means the $i$-th entry of $\omega$.

For each $i\in\mathbb{Z}$, we let $i\\#$ denote the unique element of
$\left\\{1,2,\ldots,n\right\\}$ congruent to $i$ modulo $n$.

For each $j\in\mathbb{Z}$, set

$\displaystyle\tau_{j}$
$\displaystyle=\min\left\\{\left(\nu_{\left(j+1\right)\\#}+\nu_{\left(j+2\right)\\#}+\cdots+\nu_{\left(j+k\right)\\#}\right)\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\left.+\left(\mu_{\left(j+k+1\right)\\#}+\mu_{\left(j+k+2\right)\\#}+\cdots+\mu_{\left(j+n-1\right)\\#}\right)\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.\ \mid\
k\in\left\\{0,1,\ldots,n-1\right\\}\vphantom{\left(\nu_{\left(j+1\right)\\#}\right)}\right\\}.$

Define an $n$-tuple
$\eta=\left(\eta_{1},\eta_{2},\ldots,\eta_{n}\right)\in\mathbb{Z}^{n}$ by
setting

$\eta_{i}=\mu_{i\\#}+\left(\mu_{\left(i-1\right)\\#}+\tau_{\left(i-1\right)\\#}\right)-\left(\nu_{\left(i+1\right)\\#}+\tau_{\left(i+1\right)\\#}\right)\
\ \ \ \ \ \ \ \ \ \text{for each }i\in\left\\{1,2,\ldots,n\right\\}.$

Let $\varphi\left(\omega\right)$ be the $n$-tuple
$\left(\eta_{1}+b,\eta_{2}+b,\ldots,\eta_{n}+b\right)\in\mathbb{Z}^{n}$. Thus,
we have defined a map $\varphi:\mathbb{Z}^{n}\rightarrow\mathbb{Z}^{n}$.

Then:

  * (a)

The map $\varphi$ is a bijection.

  * (b)

We have

$c_{\alpha,\mu}^{\omega}=c_{\beta,\mu}^{\varphi\left(\omega\right)}\ \ \ \ \ \
\ \ \ \ \text{for each }\omega\in\mathbb{Z}^{n}.$

Here, we are using the convention that every $n$-tuple
$\omega\in\mathbb{Z}^{n}$ that is not a partition satisfies
$c_{\alpha,\mu}^{\omega}=0$ and $c_{\beta,\mu}^{\omega}=0$.

This theorem will be proved at the end of this paper, after we have shown
several (often seemingly unrelated, yet eventually useful) results.

######  Example 2.3.

Let $n=4$ and $a=1$ and $b=4$. The partitions $\alpha$ and $\beta$ defined in
Theorem 2.2 then take the forms
$\alpha=\left(1+4,1^{2}\right)=\left(5,1,1\right)$ and
$\beta=\left(1+4,4^{2}\right)=\left(5,4,4\right)$.

Let $\mu\in\operatorname*{Par}\left[n\right]$ be the partition
$\left(2,1\right)=\left(2,1,0,0\right)$. Let
$\omega\in\operatorname*{Par}\left[n\right]$ be the partition
$\left(5,3,2\right)=\left(5,3,2,0\right)$. We shall compute the $n$-tuple
$\varphi\left(\omega\right)$ defined in Theorem 2.2.

Indeed, the $n$-tuple $\nu$ from Theorem 2.2 is

$\nu=\left(\omega_{1}-a,\omega_{2}-a,\omega_{3}-a,\omega_{4}-a\right)=\left(5-1,3-1,2-1,0-1\right)=\left(4,2,1,-1\right).$

The integers $i\\#$ from Theorem 2.2 form an $n$-periodic family

$\left(i\\#\right)_{i\in\mathbb{Z}}=\left(\ldots,0\\#,1\\#,2\\#,3\\#,4\\#,5\\#,6\\#,7\\#,\ldots\right)=\left(\ldots,4,1,2,3,4,1,2,3,\ldots\right).$

The integers $\tau_{j}$ (for $j\in\mathbb{Z}$) from Theorem 2.2 are given by

$\displaystyle\tau_{1}$
$\displaystyle=\min\left\\{\left(\nu_{2\\#}+\nu_{3\\#}+\cdots+\nu_{\left(k+1\right)\\#}\right)+\left(\mu_{\left(k+2\right)\\#}+\mu_{\left(k+3\right)\\#}+\cdots+\mu_{4\\#}\right)\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.\ \mid\
k\in\left\\{0,1,2,3\right\\}\right\\}$
$\displaystyle=\min\left\\{\mu_{2\\#}+\mu_{3\\#}+\mu_{4\\#},\ \ \
\nu_{2\\#}+\mu_{3\\#}+\mu_{4\\#},\ \ \ \nu_{2\\#}+\nu_{3\\#}+\mu_{4\\#},\ \ \
\nu_{2\\#}+\nu_{3\\#}+\nu_{4\\#}\right\\}$
$\displaystyle=\min\left\\{\mu_{2}+\mu_{3}+\mu_{4},\ \ \
\nu_{2}+\mu_{3}+\mu_{4},\ \ \ \nu_{2}+\nu_{3}+\mu_{4},\ \ \
\nu_{2}+\nu_{3}+\nu_{4}\right\\}$ $\displaystyle=\min\left\\{1+0+0,\ \ \
2+0+0,\ \ \ 2+1+0,\ \ \ 2+1+\left(-1\right)\right\\}$
$\displaystyle=\min\left\\{1,2,3,2\right\\}=1$

and

$\displaystyle\tau_{2}$
$\displaystyle=\min\left\\{\left(\nu_{3\\#}+\nu_{4\\#}+\cdots+\nu_{\left(k+2\right)\\#}\right)+\left(\mu_{\left(k+3\right)\\#}+\mu_{\left(k+4\right)\\#}+\cdots+\mu_{5\\#}\right)\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.\ \mid\
k\in\left\\{0,1,2,3\right\\}\right\\}$
$\displaystyle=\min\left\\{\mu_{3\\#}+\mu_{4\\#}+\mu_{5\\#},\ \ \
\nu_{3\\#}+\mu_{4\\#}+\mu_{5\\#},\ \ \ \nu_{3\\#}+\nu_{4\\#}+\mu_{5\\#},\ \ \
\nu_{3\\#}+\nu_{4\\#}+\nu_{5\\#}\right\\}$
$\displaystyle=\min\left\\{\mu_{3}+\mu_{4}+\mu_{1},\ \ \
\nu_{3}+\mu_{4}+\mu_{1},\ \ \ \nu_{3}+\nu_{4}+\mu_{1},\ \ \
\nu_{3}+\nu_{4}+\nu_{1}\right\\}$ $\displaystyle=\min\left\\{0+0+2,\ \ \
1+0+2,\ \ \ 1+\left(-1\right)+2,\ \ \ 1+\left(-1\right)+4\right\\}$
$\displaystyle=\min\left\\{2,3,2,4\right\\}=2$

and

$\displaystyle\tau_{3}$
$\displaystyle=\min\left\\{\left(\nu_{4\\#}+\nu_{5\\#}+\cdots+\nu_{\left(k+3\right)\\#}\right)+\left(\mu_{\left(k+4\right)\\#}+\mu_{\left(k+5\right)\\#}+\cdots+\mu_{6\\#}\right)\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.\ \mid\
k\in\left\\{0,1,2,3\right\\}\right\\}$
$\displaystyle=\min\left\\{\mu_{4\\#}+\mu_{5\\#}+\mu_{6\\#},\ \ \
\nu_{4\\#}+\mu_{5\\#}+\mu_{6\\#},\ \ \ \nu_{4\\#}+\nu_{5\\#}+\mu_{6\\#},\ \ \
\nu_{4\\#}+\nu_{5\\#}+\nu_{6\\#}\right\\}$
$\displaystyle=\min\left\\{\mu_{4}+\mu_{1}+\mu_{2},\ \ \
\nu_{4}+\mu_{1}+\mu_{2},\ \ \ \nu_{4}+\nu_{1}+\mu_{2},\ \ \
\nu_{4}+\nu_{1}+\nu_{2}\right\\}$ $\displaystyle=\min\left\\{0+2+1,\ \ \
\left(-1\right)+2+1,\ \ \ \left(-1\right)+4+1,\ \ \
\left(-1\right)+4+2\right\\}$ $\displaystyle=\min\left\\{3,2,4,5\right\\}=2$

and

$\displaystyle\tau_{4}$
$\displaystyle=\min\left\\{\left(\nu_{5\\#}+\nu_{6\\#}+\cdots+\nu_{\left(k+4\right)\\#}\right)+\left(\mu_{\left(k+5\right)\\#}+\mu_{\left(k+6\right)\\#}+\cdots+\mu_{7\\#}\right)\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.\ \mid\
k\in\left\\{0,1,2,3\right\\}\right\\}$
$\displaystyle=\min\left\\{\mu_{5\\#}+\mu_{6\\#}+\mu_{7\\#},\ \ \
\nu_{5\\#}+\mu_{6\\#}+\mu_{7\\#},\ \ \ \nu_{5\\#}+\nu_{6\\#}+\mu_{7\\#},\ \ \
\nu_{5\\#}+\nu_{6\\#}+\nu_{7\\#}\right\\}$
$\displaystyle=\min\left\\{\mu_{1}+\mu_{2}+\mu_{3},\ \ \
\nu_{1}+\mu_{2}+\mu_{3},\ \ \ \nu_{1}+\nu_{2}+\mu_{3},\ \ \
\nu_{1}+\nu_{2}+\nu_{3}\right\\}$ $\displaystyle=\min\left\\{2+1+0,\ \ \
4+1+0,\ \ \ 4+2+0,\ \ \ 4+2+1\right\\}$
$\displaystyle=\min\left\\{3,5,6,7\right\\}=3$

and

$\tau_{j}=\tau_{j^{\prime}}\ \ \ \ \ \ \ \ \ \ \text{whenever }j\equiv
j^{\prime}\operatorname{mod}4$

(the latter equality follows from the $n$-periodicity of the family
$\left(i\\#\right)_{i\in\mathbb{Z}}$). Thus, the $n$-tuple
$\eta=\left(\eta_{1},\eta_{2},\ldots,\eta_{n}\right)$ from Theorem 2.2 is
given by

$\eta_{1}=\underbrace{\mu_{1\\#}}_{=\mu_{1}=2}+\left(\underbrace{\mu_{0\\#}}_{=\mu_{4}=0}+\underbrace{\tau_{0\\#}}_{=\tau_{4}=3}\right)-\left(\underbrace{\nu_{2\\#}}_{=\nu_{2}=2}+\underbrace{\tau_{2\\#}}_{=\tau_{2}=2}\right)=2+\left(0+3\right)-\left(2+2\right)=1$

and

$\eta_{2}=\underbrace{\mu_{2\\#}}_{=\mu_{2}=1}+\left(\underbrace{\mu_{1\\#}}_{=\mu_{1}=2}+\underbrace{\tau_{1\\#}}_{=\tau_{1}=1}\right)-\left(\underbrace{\nu_{3\\#}}_{=\nu_{3}=1}+\underbrace{\tau_{3\\#}}_{=\tau_{3}=2}\right)=1+\left(2+1\right)-\left(1+2\right)=1$

and

$\eta_{3}=\underbrace{\mu_{3\\#}}_{=\mu_{3}=0}+\left(\underbrace{\mu_{2\\#}}_{=\mu_{2}=1}+\underbrace{\tau_{2\\#}}_{=\tau_{2}=2}\right)-\left(\underbrace{\nu_{4\\#}}_{=\nu_{4}=-1}+\underbrace{\tau_{4\\#}}_{=\tau_{4}=3}\right)=0+\left(1+2\right)-\left(\left(-1\right)+3\right)=1$

and

$\eta_{4}=\underbrace{\mu_{4\\#}}_{=\mu_{4}=0}+\left(\underbrace{\mu_{3\\#}}_{=\mu_{3}=0}+\underbrace{\tau_{3\\#}}_{=\tau_{3}=2}\right)-\left(\underbrace{\nu_{5\\#}}_{=\nu_{1}=4}+\underbrace{\tau_{5\\#}}_{=\tau_{1}=1}\right)=0+\left(0+2\right)-\left(4+1\right)=-3,$

so $\eta=\left(1,1,1,-3\right)$. Hence,
$\varphi\left(\omega\right)=\left(1+b,1+b,1+b,-3+b\right)=\left(5,5,5,1\right)$
(since $b=4$). This is a partition. Theorem 2.2 (b) now yields
$c_{\alpha,\mu}^{\omega}=c_{\beta,\mu}^{\varphi\left(\omega\right)}$, that is,
$c_{\left(5,1,1\right),\left(2,1\right)}^{\left(5,3,2\right)}=c_{\left(5,4,4\right),\left(2,1\right)}^{\left(5,5,5,1\right)}$.
And indeed, this equality holds (both of its sides being equal to $1$).

######  Question 2.4.

Can the bijection $\varphi$ in Theorem 2.2 be defined in a more “intuitive”
way, similar to (e.g.) jeu-de-taquin or the RSK correspondence? (Of course,
there is no tableau being transformed here, just a partition, but this should
make this construction easier.)

##  3 A birational involution

The leading role in our proof of Theorem 2.2 will be played by a certain
piecewise-linear involution (which is similar to the bijection $\varphi$ in
Theorem 2.2, but without the shifting by $-a$ and $b$). For the sake of
convenience, we prefer to study this involution in a more general setting, in
which the operations $\min$, $+$ and $-$ are replaced by the structure
operations $+$, $\cdot$ and $/$ of a semifield. This kind of generalization is
called _detropicalization_ (or _birational lifting_ , or _tropicalization_ in
the older combinatorial literature); see, e.g., [Kirill01], [NouYam02],
[EinPro13, Sections 5 and 9] or [Roby15, §4.2] for examples of this procedure
(although our use of it will be conceptually simpler).

###  3.1 Semifields

We recall some basic definitions from basic abstract algebra (mostly to avoid
confusion arising from slight terminological differences):

  * •

A _semigroup_ means a pair $\left(S,\ast\right)$, where $S$ is a set and where
$\ast$ is an associative binary operation on $S$. We do not require this
operation $\ast$ to have a neutral element. We usually write the operation
$\ast$ infix (i.e., we write $a\ast b$ instead of $\ast\left(a,b\right)$ when
$a,b\in S$).

  * •

A semigroup $\left(S,\ast\right)$ is said to be _abelian_ if the operation
$\ast$ is commutative (i.e., we have $a\ast b=b\ast a$ for all $a,b\in S$).

  * •

A _monoid_ means a triple $\left(S,\ast,e\right)$, where $\left(S,\ast\right)$
is a semigroup and where $e$ is a neutral element for the operation $\ast$
(that is, $e$ is an element of $S$ that satisfies $e\ast a=a\ast e=a$ for each
$a\in S$). Usually, the monoid $\left(S,\ast,e\right)$ is equated with the
semigroup $\left(S,\ast\right)$ because the neutral element is uniquely
determined by $S$ and $\ast$.

  * •

If $\left(S,\ast,e\right)$ is a monoid and $a$ is an element of $S$, then an
_inverse_ of $a$ (with respect to $\ast$) means an element $b$ of $S$
satisfying $a\ast b=b\ast a=e$. Such an inverse of $a$ is always unique when
it exists.

  * •

A _group_ means a monoid $\left(S,\ast,e\right)$ such that each element of $S$
has an inverse (with respect to $\ast$).

We next recall the definition of a semifield (more precisely, the one we will
be using, as there are many competing ones):

######  Definition 3.1.

A _semifield_ means a set $\mathbb{K}$ endowed with

  * •

two binary operations called “addition” and “multiplication”, and denoted by
$+$ and $\cdot$, respectively, and both written infix (i.e., we write $a+b$
and $a\cdot b$ instead of $+\left(a,b\right)$ and $\cdot\left(a,b\right)$),
and

  * •

an element called “unity” and denoted by $1$

such that $\left(\mathbb{K},+\right)$ is an abelian semigroup and
$\left(\mathbb{K},\cdot,1\right)$ is an abelian group, and such that the
following axiom is satisfied:

  * •

Distributivity: We have $a\cdot\left(b+c\right)=\left(a\cdot
b\right)+\left(a\cdot c\right)$ and $\left(a+b\right)\cdot c=\left(a\cdot
c\right)+\left(b\cdot c\right)$ for all $a\in\mathbb{K}$, $b\in\mathbb{K}$ and
$c\in\mathbb{K}$.

Thus, a semifield is similar to a field, except that it has no additive
inverses and no zero element, but, on the other hand, has multiplicative
inverses for all its elements (not just the nonzero ones).

######  Example 3.2.

Let $\mathbb{Q}_{+}$ be the set of all positive rational numbers. Then,
$\mathbb{Q}_{+}$ (endowed with its standard addition and multiplication and
the number $1$) is a semifield.

######  Example 3.3.

Let $\left(\mathbb{A},\ast,e\right)$ be any totally ordered abelian group
(whose operation is $\ast$ and whose neutral element is $e$). Then,
$\mathbb{A}$ becomes a semifield if we endow it with the “addition” $\min$
(that is, we set $a+b:=\min\left\\{a,b\right\\}$ for all $a,b\in\mathbb{A}$),
the “multiplication” $\ast$ (that is, we set $a\cdot b:=a\ast b$ for all
$a,b\in\mathbb{A}$), and the “unity” $e$. This semifield
$\left(\mathbb{A},\min,\ast,e\right)$ is called the _min tropical semifield_
of $\left(\mathbb{A},\ast,e\right)$.

######  Convention 3.1.

All conventions that are typically used for fields will be used for semifields
as well, to the extent they apply. Specifically:

  * •

If $\mathbb{K}$ is a semifield, and if $a,b\in\mathbb{K}$, then $a\cdot b$
shall be abbreviated by $ab$.

  * •

We shall use the standard “PEMDAS” convention that multiplication-like
operations have higher precedence than addition-like operations; thus, e.g.,
the expression “$ab+ac$” must be understood as
“$\left(ab\right)+\left(ac\right)$” (and not, for example, as
“$a\left(b+a\right)c$”).

  * •

If $\mathbb{K}$ is a semifield, then the inverse of any element
$b\in\mathbb{K}$ in the abelian group $\left(\mathbb{K},\cdot,1\right)$ will
be denoted by $b^{-1}$. Note that this inverse is always defined (unlike when
$\mathbb{K}$ is a field).

  * •

If $\mathbb{K}$ is a semifield, and if $a,b\in\mathbb{K}$, then the product
$ab^{-1}$ will be denoted by $a/b$ and by $\dfrac{a}{b}$. Note that this is
always defined (unlike when $\mathbb{K}$ is a field).

  * •

Finite products $\prod\limits_{i\in I}a_{i}$ of elements of a semifield are
defined in the same way as in commutative rings. The same applies to finite
sums $\sum\limits_{i\in I}a_{i}$ as long as they are nonempty (i.e., as long
as $I\neq\varnothing$). The empty sum is not defined in a semifield, since
there is no zero element.

###  3.2 The birational involution

For the rest of Section 3, we agree to the following two conventions:

######  Convention 3.2.

We fix a positive integer $n$ and a semifield $\mathbb{K}$. We also fix an
$n$-tuple $u\in\mathbb{K}^{n}$.

######  Convention 3.3.

If $a\in\mathbb{K}^{n}$ is an $n$-tuple, and if $i\in\mathbb{Z}$, then $a_{i}$
shall denote the $i^{\prime}$-th entry of $a$, where $i^{\prime}$ is the
unique element of $\left\\{1,2,\ldots,n\right\\}$ satisfying $i^{\prime}\equiv
i\operatorname{mod}n$. Thus, each $n$-tuple $a\in\mathbb{K}^{n}$ satisfies
$a=\left(a_{1},a_{2},\ldots,a_{n}\right)$ and $a_{i}=a_{i+n}$ for each
$i\in\mathbb{Z}$. Therefore, if $a\in\mathbb{K}^{n}$ is any $n$-tuple, then
the family $\left(a_{i}\right)_{i\in\mathbb{Z}}$ is $n$-periodic.

We shall soon use the letter $x$ for an $n$-tuple in $\mathbb{K}^{n}$; thus,
$x_{1},x_{2},\ldots,x_{n}$ will be the entries of this $n$-tuple. This has
nothing to do with the indeterminates $x_{1},x_{2},x_{3},\ldots$ from Section
1 (that unfortunately use the same letters); we actually forget all
conventions from Section 1 (apart from
$\mathbb{N}=\left\\{0,1,2,\ldots\right\\}$) for the entire Section 3.

The following is obvious:

######  Lemma 3.4.

If $a\in\mathbb{K}^{n}$ is any $n$-tuple, then $a_{k+1}a_{k+2}\cdots
a_{k+n}=a_{1}a_{2}\cdots a_{n}$ for each $k\in\mathbb{Z}$.

######  Definition 3.5.

We define a map $\mathbf{f}_{u}:\mathbb{K}^{n}\rightarrow\mathbb{K}^{n}$ as
follows:

Let $x\in\mathbb{K}^{n}$ be an $n$-tuple. For each $j\in\mathbb{Z}$ and
$r\in\mathbb{N}$, define an element $t_{r,j}\in\mathbb{K}$ by

$t_{r,j}=\sum\limits_{k=0}^{r}\underbrace{x_{j+1}x_{j+2}\cdots
x_{j+k}}_{=\prod\limits_{i=1}^{k}x_{j+i}}\cdot\underbrace{u_{j+k+1}u_{j+k+2}\cdots
u_{j+r}}_{=\prod\limits_{i=k+1}^{r}u_{j+i}}.$

Define $y\in\mathbb{K}^{n}$ by setting

$y_{i}=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}\ \ \ \ \ \ \ \
\ \ \text{for each }i\in\left\\{1,2,\ldots,n\right\\}.$

Set $\mathbf{f}_{u}\left(x\right)=y$.

######  Example 3.6.

Set $n=4$ for this example. Let $x\in\mathbb{K}^{n}$ be an $n$-tuple; thus,
$x=\left(x_{1},x_{2},x_{3},x_{4}\right)$. Let us see what the definition of
$\mathbf{f}_{u}\left(x\right)$ in Definition 3.5 boils down to in this case.

Let us first compute the elements $t_{n-1,j}=t_{3,j}$ from Definition 3.5. The
definition of $t_{3,0}$ yields

$\displaystyle t_{3,0}$
$\displaystyle=\sum\limits_{k=0}^{3}x_{0+1}x_{0+2}\cdots x_{0+k}\cdot
u_{0+k+1}u_{0+k+2}\cdots u_{0+3}$
$\displaystyle=\sum\limits_{k=0}^{3}x_{1}x_{2}\cdots x_{k}\cdot
u_{k+1}u_{k+2}\cdots u_{3}$
$\displaystyle=u_{1}u_{2}u_{3}+x_{1}u_{2}u_{3}+x_{1}x_{2}u_{3}+x_{1}x_{2}x_{3}.$

Similarly,

$\displaystyle t_{3,1}$
$\displaystyle=u_{2}u_{3}u_{4}+x_{2}u_{3}u_{4}+x_{2}x_{3}u_{4}+x_{2}x_{3}x_{4};$
$\displaystyle t_{3,2}$
$\displaystyle=u_{3}u_{4}u_{5}+x_{3}u_{4}u_{5}+x_{3}x_{4}u_{5}+x_{3}x_{4}x_{5}$
$\displaystyle=u_{3}u_{4}u_{1}+x_{3}u_{4}u_{1}+x_{3}x_{4}u_{1}+x_{3}x_{4}x_{1}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since }u_{5}=u_{1}\text{ and
}x_{5}=x_{1}\right);$ $\displaystyle t_{3,3}$
$\displaystyle=u_{4}u_{5}u_{6}+x_{4}u_{5}u_{6}+x_{4}x_{5}u_{6}+x_{4}x_{5}x_{6}$
$\displaystyle=u_{4}u_{1}u_{2}+x_{4}u_{1}u_{2}+x_{4}x_{1}u_{2}+x_{4}x_{1}x_{2}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since }u_{5}=u_{1}\text{ and
}x_{5}=x_{1}\text{ and }u_{6}=u_{2}\text{ and }x_{6}=x_{2}\right).$

We don’t need to compute any further $t_{3,j}$’s, since we can easily see that

$t_{3,j}=t_{3,j^{\prime}}\text{ for any integers }j\text{ and
}j^{\prime}\text{ satisfying }j\equiv j^{\prime}\operatorname{mod}4.$ (2)

Thus, in particular, $t_{3,4}=t_{3,0}$ and $t_{3,5}=t_{3,1}$.

Now, let us compute the $4$-tuple $y\in\mathbb{K}^{n}=\mathbb{K}^{4}$ from
Definition 3.5. By its definition, we have

$\displaystyle y_{1}$
$\displaystyle=u_{1}\cdot\dfrac{u_{1-1}t_{3,1-1}}{x_{1+1}t_{3,1+1}}=u_{1}\cdot\dfrac{u_{0}t_{3,0}}{x_{2}t_{3,2}}=u_{1}\cdot\dfrac{u_{4}t_{3,0}}{x_{2}t_{3,2}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since }u_{0}=u_{4}\right)$
$\displaystyle=u_{1}\cdot\dfrac{u_{4}\left(u_{1}u_{2}u_{3}+x_{1}u_{2}u_{3}+x_{1}x_{2}u_{3}+x_{1}x_{2}x_{3}\right)}{x_{2}\left(u_{3}u_{4}u_{1}+x_{3}u_{4}u_{1}+x_{3}x_{4}u_{1}+x_{3}x_{4}x_{1}\right)}$

(by our formulas for $t_{3,0}$ and $t_{3,2}$). Similar computations lead to

$\displaystyle y_{2}$
$\displaystyle=u_{2}\cdot\dfrac{u_{1}\left(u_{2}u_{3}u_{4}+x_{2}u_{3}u_{4}+x_{2}x_{3}u_{4}+x_{2}x_{3}x_{4}\right)}{x_{3}\left(u_{4}u_{1}u_{2}+x_{4}u_{1}u_{2}+x_{4}x_{1}u_{2}+x_{4}x_{1}x_{2}\right)};$
$\displaystyle y_{3}$
$\displaystyle=u_{3}\cdot\dfrac{u_{2}\left(u_{3}u_{4}u_{1}+x_{3}u_{4}u_{1}+x_{3}x_{4}u_{1}+x_{3}x_{4}x_{1}\right)}{x_{4}\left(u_{1}u_{2}u_{3}+x_{1}u_{2}u_{3}+x_{1}x_{2}u_{3}+x_{1}x_{2}x_{3}\right)};$
$\displaystyle y_{4}$
$\displaystyle=u_{4}\cdot\dfrac{u_{3}\left(u_{4}u_{1}u_{2}+x_{4}u_{1}u_{2}+x_{4}x_{1}u_{2}+x_{4}x_{1}x_{2}\right)}{x_{1}\left(u_{2}u_{3}u_{4}+x_{2}u_{3}u_{4}+x_{2}x_{3}u_{4}+x_{2}x_{3}x_{4}\right)}.$

Of course, knowing one of these four equalities is enough; the expression for
$y_{i+1}$ is obtained from the expression for $y_{i}$ by shifting all indices
(other than the “$3$”s that were originally “$n-1$”s) forward by $1$.

######  Remark 3.7.

Instead of assuming $\mathbb{K}$ to be a semifield, we could have assumed that
$\mathbb{K}$ is an infinite field. In that case, the $\mathbf{f}_{u}$ in
Definition 3.5 would be a birational map instead of a map in the usual sense
of this word, since the denominators $x_{i+1}t_{n-1,i+1}$ in the definition of
$y$ can be zero. Everything we say below about $\mathbf{f}_{u}$ would
nevertheless still hold on the level of birational maps.

The map $\mathbf{f}_{u}$ we just defined has the following properties:

######  Theorem 3.8.

  1. (a)

The map $\mathbf{f}_{u}$ is an involution (i.e., we have
$\mathbf{f}_{u}\circ\mathbf{f}_{u}=\operatorname*{id}$).

  2. (b)

Let $x\in\mathbb{K}^{n}$ and $y\in\mathbb{K}^{n}$ be such that
$y=\mathbf{f}_{u}\left(x\right)$. Then,

$y_{1}y_{2}\cdots y_{n}\cdot x_{1}x_{2}\cdots x_{n}=\left(u_{1}u_{2}\cdots
u_{n}\right)^{2}.$

  3. (c)

Let $x\in\mathbb{K}^{n}$ and $y\in\mathbb{K}^{n}$ be such that
$y=\mathbf{f}_{u}\left(x\right)$. Then,

$\left(u_{i}+x_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{x_{i+1}}\right)=\left(u_{i}+y_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{y_{i+1}}\right)$

for each $i\in\mathbb{Z}$.

  4. (d)

Let $x\in\mathbb{K}^{n}$ and $y\in\mathbb{K}^{n}$ be such that
$y=\mathbf{f}_{u}\left(x\right)$. Then,

$\prod\limits_{i=1}^{n}\dfrac{u_{i}+x_{i}}{x_{i}}=\prod\limits_{i=1}^{n}\dfrac{u_{i}+y_{i}}{u_{i}}.$

Theorem 3.8 will be crucial for us; but before we can prove it, we will need a
few lemmas.

######  Lemma 3.9.

Let $x\in\mathbb{K}^{n}$ be an $n$-tuple. Let $t_{r,j}$ and $y$ be as in
Definition 3.5. Then:

  1. (a)

We have $t_{r,j}=t_{r,j^{\prime}}$ for any $r\in\mathbb{N}$ and any two
integers $j$ and $j^{\prime}$ satisfying $j\equiv
j^{\prime}\operatorname{mod}n$. In other words, for each $r\in\mathbb{N}$, the
family $\left(t_{r,j}\right)_{j\in\mathbb{Z}}$ is $n$-periodic.

  2. (b)

We have $t_{0,j}=1$ for each $j\in\mathbb{Z}$.

  3. (c)

For each $r\in\mathbb{N}$ and $j\in\mathbb{Z}$, we have

$x_{j}t_{r,j}+u_{j}u_{j+1}\cdots u_{j+r}=t_{r+1,j-1}.$

  4. (d)

For each $r\in\mathbb{N}$ and $j\in\mathbb{Z}$, we have

$u_{j+r+1}t_{r,j}+x_{j+1}x_{j+2}\cdots x_{j+r+1}=t_{r+1,j}.$

  5. (e)

For each $a\in\mathbb{Z}$ and $b\in\mathbb{Z}$, we have

$x_{a}t_{n-1,a}+u_{b-1}t_{n-1,b-1}=x_{b}t_{n-1,b}+u_{a-1}t_{n-1,a-1}.$

  6. (f)

For each $i\in\mathbb{Z}$, we have

$x_{i+1}t_{n-1,i+1}+u_{i-1}t_{n-1,i-1}=\left(x_{i}+u_{i}\right)t_{n-1,i}.$

  7. (g)

For each $j\in\mathbb{Z}$ and each positive integer $q$, we have

$t_{n-1,j+q+1}\cdot x_{j+2}x_{j+3}\cdots
x_{j+q+1}+u_{j}t_{n-1,j}t_{q-1,j+1}=t_{n-1,j+1}t_{q,j}.$

  8. (h)

For each $i\in\mathbb{Z}$, we have

$y_{i}=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}.$

Now, for each $j\in\mathbb{Z}$ and $r\in\mathbb{N}$, let us define an element
$t_{r,j}^{\prime}\in\mathbb{K}$ by

$t_{r,j}^{\prime}=\sum\limits_{k=0}^{r}\underbrace{y_{j+1}y_{j+2}\cdots
y_{j+k}}_{=\prod\limits_{i=1}^{k}y_{j+i}}\cdot\underbrace{u_{j+k+1}u_{j+k+2}\cdots
u_{j+r}}_{=\prod\limits_{i=k+1}^{r}u_{j+i}}.$

(This is precisely how $t_{r,j}$ was defined, except that we are using $y$ in
place of $x$ now.) Then:

  1. (i)

For each $j\in\mathbb{Z}$ and $q\in\mathbb{N}$, we have

$\dfrac{t_{q,j}^{\prime}}{u_{j+1}u_{j+2}\cdots
u_{j+q}}=\dfrac{t_{n-1,j+1}}{t_{n-1,j+q+1}}\cdot\dfrac{t_{q,j}}{x_{j+2}x_{j+3}\cdots
x_{j+q+1}}.$

  2. (j)

For each $j\in\mathbb{Z}$, we have

$\dfrac{t_{n-1,j}^{\prime}u_{j}}{u_{1}u_{2}\cdots
u_{n}}=\dfrac{t_{n-1,j+1}x_{j+1}}{x_{1}x_{2}\cdots x_{n}}.$

  3. (k)

For each $i\in\mathbb{Z}$, we have

$x_{i}=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}^{\prime}}{y_{i+1}t_{n-1,i+1}^{\prime}}.$

######  Proof 3.10 (Proof of Lemma 3.9.).

The proof of this lemma is long but unsophisticated: Each part follows by
rather straightforward computations (and, in the cases of parts (g) and (i),
an induction on $q$) from the previously proven parts. We shall show the
details, but a computationally inclined reader may have a better time
reconstructing them independently.111We note that the hardest parts of the
proof – namely, the proofs of parts (g), (i), (j) and (k) – can be sidestepped
entirely, as these parts will only be used in the proof of Theorem 3.8 (a),
but we will give an alternative proof of Theorem 3.8 (a) later on (in Remark
3.18), which avoids using them.

(a) Let $r\in\mathbb{N}$. The definition of $t_{r,j}$ shows that
$t_{r,j}=t_{r,j+n}$ for each $j\in\mathbb{Z}$ (since each $i\in\mathbb{Z}$
satisfies $u_{i}=u_{i+n}$ and $x_{i}=x_{i+n}$). Thus, the family
$\left(t_{r,j}\right)_{j\in\mathbb{Z}}$ is $n$-periodic. This yields the claim
of Lemma 3.9 (a).

(b) Trivial consequence of the definition of $t_{0,j}$.

(c) Let $r\in\mathbb{N}$ and $j\in\mathbb{Z}$. Then, the definition of
$t_{r+1,j-1}$ yields

$\displaystyle t_{r+1,j-1}$
$\displaystyle=\sum\limits_{k=0}^{r+1}x_{j}x_{j+1}\cdots x_{j+k-1}\cdot
u_{j+k}u_{j+k+1}\cdots u_{j+r}$ $\displaystyle=\underbrace{x_{j}x_{j+1}\cdots
x_{j-1}}_{=\left(\text{empty product}\right)=1}\cdot u_{j}u_{j+1}\cdots
u_{j+r}+\sum\limits_{k=1}^{r+1}\underbrace{x_{j}x_{j+1}\cdots
x_{j+k-1}}_{=x_{j}\cdot x_{j+1}x_{j+2}\cdots x_{j+k-1}}\cdot
u_{j+k}u_{j+k+1}\cdots u_{j+r}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\text{here, we have split off the addend for }k=0\text{ from the
sum}\right)$ $\displaystyle=u_{j}u_{j+1}\cdots
u_{j+r}+\underbrace{\sum\limits_{k=1}^{r+1}x_{j}\cdot x_{j+1}x_{j+2}\cdots
x_{j+k-1}\cdot u_{j+k}u_{j+k+1}\cdots
u_{j+r}}_{=x_{j}\sum\limits_{k=1}^{r+1}x_{j+1}x_{j+2}\cdots x_{j+k-1}\cdot
u_{j+k}u_{j+k+1}\cdots u_{j+r}}$ $\displaystyle=u_{j}u_{j+1}\cdots
u_{j+r}+x_{j}\underbrace{\sum\limits_{k=1}^{r+1}x_{j+1}x_{j+2}\cdots
x_{j+k-1}\cdot u_{j+k}u_{j+k+1}\cdots
u_{j+r}}_{\begin{subarray}{c}=\sum\limits_{k=0}^{r}x_{j+1}x_{j+2}\cdots
x_{j+k}\cdot u_{j+k+1}u_{j+k+2}\cdots u_{j+r}\\\ \text{(here, we have
substituted }k\text{ for }k-1\text{ in the sum)}\end{subarray}}$
$\displaystyle=u_{j}u_{j+1}\cdots
u_{j+r}+x_{j}\underbrace{\sum\limits_{k=0}^{r}x_{j+1}x_{j+2}\cdots
x_{j+k}\cdot u_{j+k+1}u_{j+k+2}\cdots u_{j+r}}_{\begin{subarray}{c}=t_{r,j}\\\
\text{(by the definition of }t_{r,j}\text{)}\end{subarray}}$
$\displaystyle=u_{j}u_{j+1}\cdots
u_{j+r}+x_{j}t_{r,j}=x_{j}t_{r,j}+u_{j}u_{j+1}\cdots u_{j+r}.$

This proves Lemma 3.9 (c).

(d) Let $r\in\mathbb{N}$ and $j\in\mathbb{Z}$. Then, the definition of
$t_{r+1,j}$ yields

$\displaystyle t_{r+1,j}$
$\displaystyle=\sum\limits_{k=0}^{r+1}x_{j+1}x_{j+2}\cdots x_{j+k}\cdot
u_{j+k+1}u_{j+k+2}\cdots u_{j+r+1}$
$\displaystyle=\sum\limits_{k=0}^{r}x_{j+1}x_{j+2}\cdots
x_{j+k}\cdot\underbrace{u_{j+k+1}u_{j+k+2}\cdots
u_{j+r+1}}_{=u_{j+k+1}u_{j+k+2}\cdots u_{j+r}\cdot u_{j+r+1}}$ $\displaystyle\
\ \ \ \ \ \ \ \ \ +x_{j+1}x_{j+2}\cdots
x_{j+r+1}\cdot\underbrace{u_{j+\left(r+1\right)+1}u_{j+\left(r+1\right)+2}\cdots
u_{j+r+1}}_{=\left(\text{empty product}\right)=1}$ $\displaystyle\ \ \ \ \ \ \
\ \ \ \left(\text{here, we have split off the addend for }k=r+1\text{ from the
sum}\right)$
$\displaystyle=\underbrace{\sum\limits_{k=0}^{r}x_{j+1}x_{j+2}\cdots
x_{j+k}\cdot u_{j+k+1}u_{j+k+2}\cdots u_{j+r}\cdot
u_{j+r+1}}_{=u_{j+r+1}\sum\limits_{k=0}^{r}x_{j+1}x_{j+2}\cdots x_{j+k}\cdot
u_{j+k+1}u_{j+k+2}\cdots u_{j+r}}+x_{j+1}x_{j+2}\cdots x_{j+r+1}$
$\displaystyle=u_{j+r+1}\underbrace{\sum\limits_{k=0}^{r}x_{j+1}x_{j+2}\cdots
x_{j+k}\cdot u_{j+k+1}u_{j+k+2}\cdots u_{j+r}}_{\begin{subarray}{c}=t_{r,j}\\\
\text{(by the definition of
}t_{r,j}\text{)}\end{subarray}}+x_{j+1}x_{j+2}\cdots x_{j+r+1}$
$\displaystyle=u_{j+r+1}t_{r,j}+x_{j+1}x_{j+2}\cdots x_{j+r+1}.$

This proves Lemma 3.9 (d).

(e) We WLOG assume that $n\neq 1$, since otherwise the claim is easy to check
by hand. Thus, $n\geq 2$, so that $n-2\in\mathbb{N}$.

Let $a\in\mathbb{Z}$ and $b\in\mathbb{Z}$. Then, Lemma 3.9 (c) (applied to
$r=n-2$ and $j=a$) yields

$x_{a}t_{n-2,a}+u_{a}u_{a+1}\cdots
u_{a+n-2}=t_{\left(n-2\right)+1,a-1}=t_{n-1,a-1}$

(since $\left(n-2\right)+1=n-1$). Multiplying both sides of this equality by
$u_{a-1}$, we obtain

$u_{a-1}\left(x_{a}t_{n-2,a}+u_{a}u_{a+1}\cdots
u_{a+n-2}\right)=u_{a-1}t_{n-1,a-1}.$

Hence,

$\displaystyle u_{a-1}t_{n-1,a-1}$
$\displaystyle=u_{a-1}\left(x_{a}t_{n-2,a}+u_{a}u_{a+1}\cdots
u_{a+n-2}\right)$
$\displaystyle=\underbrace{u_{a-1}x_{a}}_{=x_{a}u_{a-1}}t_{n-2,a}+\underbrace{u_{a-1}\cdot
u_{a}u_{a+1}\cdots u_{a+n-2}}_{\begin{subarray}{c}=u_{a-1}u_{a}\cdots
u_{a+n-2}\\\ =u_{\left(a-2\right)+1}u_{\left(a-2\right)+2}\cdots
u_{\left(a-2\right)+n}\\\ =u_{1}u_{2}\cdots u_{n}\\\ \text{(by Lemma
\ref{lem.aprod})}\end{subarray}}$
$\displaystyle=x_{a}u_{a-1}t_{n-2,a}+u_{1}u_{2}\cdots u_{n}.$ (3)

Also, Lemma 3.9 (d) (applied to $r=n-2$ and $j=b$) yields

$u_{b+\left(n-2\right)+1}t_{n-2,b}+x_{b+1}x_{b+2}\cdots
x_{b+\left(n-2\right)+1}=t_{\left(n-2\right)+1,b}.$

In view of $\left(n-2\right)+1=n-1$, this rewrites as

$u_{b+n-1}t_{n-2,b}+x_{b+1}x_{b+2}\cdots x_{b+n-1}=t_{n-1,b}.$

Multiplying both sides of this equality by $x_{b}$, we obtain

$x_{b}\left(u_{b+n-1}t_{n-2,b}+x_{b+1}x_{b+2}\cdots
x_{b+n-1}\right)=x_{b}t_{n-1,b},$

so that

$\displaystyle x_{b}t_{n-1,b}$
$\displaystyle=x_{b}\left(u_{b+n-1}t_{n-2,b}+x_{b+1}x_{b+2}\cdots
x_{b+n-1}\right)$
$\displaystyle=x_{b}\underbrace{u_{b+n-1}}_{=u_{\left(b-1\right)+n}=u_{b-1}}t_{n-2,b}+\underbrace{x_{b}\cdot
x_{b+1}x_{b+2}\cdots x_{b+n-1}}_{\begin{subarray}{c}=x_{b}x_{b+1}\cdots
x_{b+n-1}\\\ =x_{\left(b-1\right)+1}x_{\left(b-1\right)+2}\cdots
x_{\left(b-1\right)+n}\\\ =x_{1}x_{2}\cdots x_{n}\\\ \text{(by Lemma
\ref{lem.aprod})}\end{subarray}}$
$\displaystyle=x_{b}u_{b-1}t_{n-2,b}+x_{1}x_{2}\cdots x_{n}.$

Adding (3) to this equality, we obtain

$\displaystyle x_{b}t_{n-1,b}+u_{a-1}t_{n-1,a-1}$
$\displaystyle=x_{b}u_{b-1}t_{n-2,b}+x_{1}x_{2}\cdots
x_{n}+x_{a}u_{a-1}t_{n-2,a}+u_{1}u_{2}\cdots u_{n}$ (4)
$\displaystyle=x_{a}u_{a-1}t_{n-2,a}+x_{1}x_{2}\cdots
x_{n}+x_{b}u_{b-1}t_{n-2,b}+u_{1}u_{2}\cdots u_{n}.$

The same argument (applied to $b$ and $a$ instead of $a$ and $b$) yields

$\displaystyle x_{a}t_{n-1,a}+u_{b-1}t_{n-1,b-1}$
$\displaystyle=x_{b}u_{b-1}t_{n-2,b}+x_{1}x_{2}\cdots
x_{n}+x_{a}u_{a-1}t_{n-2,a}+u_{1}u_{2}\cdots u_{n}.$

Comparing this with (4), we obtain
$x_{a}t_{n-1,a}+u_{b-1}t_{n-1,b-1}=x_{b}t_{n-1,b}+u_{a-1}t_{n-1,a-1}$. This
proves Lemma 3.9 (e).

(f) Applying Lemma 3.9 (e) to $a=i+1$ and $b=i$, we obtain

$\displaystyle x_{i+1}t_{n-1,i+1}+u_{i-1}t_{n-1,i-1}$
$\displaystyle=x_{i}t_{n-1,i}+\underbrace{u_{i+1-1}}_{=u_{i}}\underbrace{t_{n-1,i+1-1}}_{=t_{n-1,i}}$
$\displaystyle=x_{i}t_{n-1,i}+u_{i}t_{n-1,i}=\left(x_{i}+u_{i}\right)t_{n-1,i}.$

This proves Lemma 3.9 (f).

(g) We shall prove Lemma 3.9 (g) by induction on $q$:

Induction base: Let us show that Lemma 3.9 (g) holds for $q=1$.

Indeed, let $j\in\mathbb{Z}$. The definition of $t_{1,j}$ yields

$t_{1,j}=\sum\limits_{k=0}^{1}x_{j+1}x_{j+2}\cdots x_{j+k}\cdot
u_{j+k+1}u_{j+k+2}\cdots u_{j+1}=x_{j+1}+u_{j+1}.$

Hence,

$t_{n-1,j+1}\underbrace{t_{1,j}}_{=x_{j+1}+u_{j+1}}=t_{n-1,j+1}\left(x_{j+1}+u_{j+1}\right)=\left(x_{j+1}+u_{j+1}\right)t_{n-1,j+1}.$

Comparing this with

$\displaystyle\underbrace{t_{n-1,j+1+1}}_{=t_{n-1,j+2}}\cdot\underbrace{x_{j+2}x_{j+3}\cdots
x_{j+1+1}}_{\begin{subarray}{c}=x_{j+2}x_{j+3}\cdots x_{j+2}\\\
=x_{j+2}\end{subarray}}+u_{j}t_{n-1,j}\underbrace{t_{1-1,j+1}}_{\begin{subarray}{c}=t_{0,j+1}=1\\\
\text{(by Lemma \ref{lem.f.steps} {(b)})}\end{subarray}}$
$\displaystyle=t_{n-1,j+2}x_{j+2}+u_{j}t_{n-1,j}=x_{j+2}t_{n-1,j+2}+u_{j}t_{n-1,j}=\left(x_{j+1}+u_{j+1}\right)t_{n-1,j+1}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{by Lemma \ref{lem.f.steps}
{(f)}, applied to }i=j+1\right),$

we obtain

$t_{n-1,j+1+1}\cdot x_{j+2}x_{j+3}\cdots
x_{j+1+1}+u_{j}t_{n-1,j}t_{1-1,j+1}=t_{n-1,j+1}t_{1,j}.$

Now, forget that we fixed $j$. We thus have proved that

$t_{n-1,j+1+1}\cdot x_{j+2}x_{j+3}\cdots
x_{j+1+1}+u_{j}t_{n-1,j}t_{1-1,j+1}=t_{n-1,j+1}t_{1,j}$

for each $j\in\mathbb{Z}$. In other words, Lemma 3.9 (g) holds for $q=1$. This
completes the induction base.222We could have simplified this part of the
proof by taking $q=0$ as induction base instead. But this would have required
extending the semifield $\mathbb{K}$ to a semiring
$\mathbb{K}\sqcup\left\\{0\right\\}$ by adjoining a zero (since $t_{-1,j}$
would be an empty sum). It is not hard to do this, but we prefer computations
to technicalities.

Induction step: Fix a positive integer $p$. Assume (as induction hypothesis)
that Lemma 3.9 (g) holds for $q=p$. We must now show that Lemma 3.9 (g) holds
for $q=p+1$.

We have assumed that Lemma 3.9 (g) holds for $q=p$. In other words, each
$j\in\mathbb{Z}$ satisfies

$t_{n-1,j+p+1}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+1}+u_{j}t_{n-1,j}t_{p-1,j+1}=t_{n-1,j+1}t_{p,j}.$ (5)

Now, let $j\in\mathbb{Z}$ be arbitrary. Then, Lemma 3.9 (d) (applied to $r=p$)
yields

$u_{j+p+1}t_{p,j}+x_{j+1}x_{j+2}\cdots x_{j+p+1}=t_{p+1,j}.$

Multiplying both sides of this equality by $t_{n-1,j+1}$, we obtain

$t_{n-1,j+1}\left(u_{j+p+1}t_{p,j}+x_{j+1}x_{j+2}\cdots
x_{j+p+1}\right)=t_{n-1,j+1}t_{p+1,j}.$

Hence,

$\displaystyle t_{n-1,j+1}t_{p+1,j}$
$\displaystyle=t_{n-1,j+1}\left(u_{j+p+1}t_{p,j}+x_{j+1}x_{j+2}\cdots
x_{j+p+1}\right)$
$\displaystyle=\underbrace{t_{n-1,j+1}u_{j+p+1}}_{=u_{j+p+1}t_{n-1,j+1}}t_{p,j}+t_{n-1,j+1}\cdot
x_{j+1}x_{j+2}\cdots x_{j+p+1}$
$\displaystyle=u_{j+p+1}\underbrace{t_{n-1,j+1}t_{p,j}}_{\begin{subarray}{c}=t_{n-1,j+p+1}\cdot
x_{j+2}x_{j+3}\cdots x_{j+p+1}+u_{j}t_{n-1,j}t_{p-1,j+1}\\\ \text{(by
(\ref{pf.lem.f.steps.g.IH}))}\end{subarray}}+t_{n-1,j+1}\cdot\underbrace{x_{j+1}x_{j+2}\cdots
x_{j+p+1}}_{=x_{j+1}\cdot x_{j+2}x_{j+3}\cdots x_{j+p+1}}$
$\displaystyle=u_{j+p+1}\left(t_{n-1,j+p+1}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+1}+u_{j}t_{n-1,j}t_{p-1,j+1}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
+t_{n-1,j+1}\cdot x_{j+1}\cdot x_{j+2}x_{j+3}\cdots x_{j+p+1}$
$\displaystyle=u_{j+p+1}t_{n-1,j+p+1}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+1}+u_{j+p+1}u_{j}t_{n-1,j}t_{p-1,j+1}$ $\displaystyle\ \ \ \ \ \ \ \ \
\ +t_{n-1,j+1}\cdot x_{j+1}\cdot x_{j+2}x_{j+3}\cdots x_{j+p+1}$
$\displaystyle=\underbrace{\left(u_{j+p+1}t_{n-1,j+p+1}+t_{n-1,j+1}\cdot
x_{j+1}\right)}_{\begin{subarray}{c}=x_{j+1}t_{n-1,j+1}+u_{j+p+1}t_{n-1,j+p+1}\end{subarray}}\cdot
x_{j+2}x_{j+3}\cdots x_{j+p+1}+u_{j+p+1}u_{j}t_{n-1,j}t_{p-1,j+1}$
$\displaystyle=\underbrace{\left(x_{j+1}t_{n-1,j+1}+u_{j+p+1}t_{n-1,j+p+1}\right)}_{\begin{subarray}{c}=x_{j+p+2}t_{n-1,j+p+2}+u_{j}t_{n-1,j}\\\
\text{(by Lemma \ref{lem.f.steps} {(e)}, applied to }a=j+1\text{ and
}b=j+p+2\text{)}\end{subarray}}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+1}+u_{j+p+1}u_{j}t_{n-1,j}t_{p-1,j+1}$
$\displaystyle=\left(x_{j+p+2}t_{n-1,j+p+2}+u_{j}t_{n-1,j}\right)\cdot
x_{j+2}x_{j+3}\cdots x_{j+p+1}+u_{j+p+1}u_{j}t_{n-1,j}t_{p-1,j+1}$
$\displaystyle=x_{j+p+2}t_{n-1,j+p+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+1}+u_{j}t_{n-1,j}\cdot x_{j+2}x_{j+3}\cdots x_{j+p+1}$ $\displaystyle\
\ \ \ \ \ \ \ \ \ +u_{j+p+1}u_{j}t_{n-1,j}t_{p-1,j+1}$
$\displaystyle=u_{j}t_{n-1,j}\underbrace{\left(u_{j+p+1}t_{p-1,j+1}+x_{j+2}x_{j+3}\cdots
x_{j+p+1}\right)}_{\begin{subarray}{c}=t_{p,j+1}\\\ \text{(by Lemma
\ref{lem.f.steps} {(d)}, applied to }j+1\text{ and }p-1\text{ instead of
}j\text{ and }r\text{)}\end{subarray}}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
+\underbrace{x_{j+p+2}t_{n-1,j+p+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+1}}_{=t_{n-1,j+p+2}\cdot x_{j+2}x_{j+3}\cdots x_{j+p+1}\cdot
x_{j+p+2}}$
$\displaystyle=u_{j}t_{n-1,j}t_{p,j+1}+t_{n-1,j+p+2}\cdot\underbrace{x_{j+2}x_{j+3}\cdots
x_{j+p+1}\cdot x_{j+p+2}}_{=x_{j+2}x_{j+3}\cdots x_{j+p+2}}$
$\displaystyle=u_{j}t_{n-1,j}t_{p,j+1}+t_{n-1,j+p+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+2}$ $\displaystyle=t_{n-1,j+p+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+2}+u_{j}t_{n-1,j}t_{p,j+1}.$

In other words,

$t_{n-1,j+p+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+2}+u_{j}t_{n-1,j}t_{p,j+1}=t_{n-1,j+1}t_{p+1,j}.$

Now, forget that we fixed $j$. We thus have proved that each $j\in\mathbb{Z}$
satisfies

$t_{n-1,j+p+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+p+2}+u_{j}t_{n-1,j}t_{p,j+1}=t_{n-1,j+1}t_{p+1,j}.$

In other words, Lemma 3.9 (g) holds for $q=p+1$. This completes the induction
step. Hence, Lemma 3.9 (g) is proved by induction.

(h) For $i\in\left\\{1,2,\ldots,n\right\\}$, the claim of Lemma 3.9 (h)
follows from the definition of $y$. Thus, it also holds for all
$i\in\mathbb{Z}$, since any integers $j$ and $j^{\prime}$ satisfying $j\equiv
j^{\prime}\operatorname{mod}n$ satisfy $x_{j}=x_{j^{\prime}}$ and
$u_{j}=u_{j^{\prime}}$ and $t_{n-1,j}=t_{n-1,j^{\prime}}$ (by Lemma 3.9 (a))
and $y_{j}=y_{j^{\prime}}$. Thus, Lemma 3.9 (h) is proved.

(i) We shall prove Lemma 3.9 (i) by induction on $q$:

Induction base: For each $j\in\mathbb{Z}$, we have

$\dfrac{t_{0,j}^{\prime}}{u_{j+1}u_{j+2}\cdots
u_{j}}=\dfrac{t_{n-1,j+1}}{t_{n-1,j+1}}\cdot\dfrac{t_{0,j}}{x_{j+2}x_{j+3}\cdots
x_{j+1}}$ 333Proof. Let $j\in\mathbb{Z}$. Lemma 3.9 (b) yields $t_{0,j}=1$.
Similarly, $t_{0,j}^{\prime}=1$. From this equality, and from
$u_{j+1}u_{j+2}\cdots u_{j}=\left(\text{empty product}\right)=1$, we obtain
$\dfrac{t_{0,j}^{\prime}}{u_{j+1}u_{j+2}\cdots u_{j}}=\dfrac{1}{1}.$ Comparing
this with
$\displaystyle\dfrac{t_{n-1,j+1}}{t_{n-1,j+1}}\cdot\dfrac{t_{0,j}}{x_{j+2}x_{j+3}\cdots
x_{j+1}}$ $\displaystyle=\dfrac{t_{0,j}}{x_{j+2}x_{j+3}\cdots
x_{j+1}}=\dfrac{1}{1}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since
}t_{0,j}=1\text{ and }x_{j+2}x_{j+3}\cdots x_{j+1}=\left(\text{empty
product}\right)=1\right),$ we obtain
$\dfrac{t_{0,j}^{\prime}}{u_{j+1}u_{j+2}\cdots
u_{j}}=\dfrac{t_{n-1,j+1}}{t_{n-1,j+1}}\cdot\dfrac{t_{0,j}}{x_{j+2}x_{j+3}\cdots
x_{j+1}}$. Qed.

. In other words, Lemma 3.9 (i) holds for $q=0$. This completes the induction
base.

Induction step: Fix $r\in\mathbb{N}$. Assume (as induction hypothesis) that
Lemma 3.9 (i) holds for $q=r$. We must now show that Lemma 3.9 (i) holds for
$q=r+1$.

We have assumed that Lemma 3.9 (i) holds for $q=r$. In other words, each
$j\in\mathbb{Z}$ satisfies

$\dfrac{t_{r,j}^{\prime}}{u_{j+1}u_{j+2}\cdots
u_{j+r}}=\dfrac{t_{n-1,j+1}}{t_{n-1,j+r+1}}\cdot\dfrac{t_{r,j}}{x_{j+2}x_{j+3}\cdots
x_{j+r+1}}.$ (6)

Now, let $j\in\mathbb{Z}$ be arbitrary. Then, (6) (applied to $j+1$ instead of
$j$) yields

$\dfrac{t_{r,j+1}^{\prime}}{u_{j+2}u_{j+3}\cdots
u_{j+r+1}}=\dfrac{t_{n-1,j+2}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r,j+1}}{x_{j+3}x_{j+4}\cdots
x_{j+r+2}}.$ (7)

But Lemma 3.9 (c) (applied to $j+1$ instead of $j$) yields

$x_{j+1}t_{r,j+1}+u_{j+1}u_{j+2}\cdots u_{j+r+1}=t_{r+1,j}.$

Hence,

$t_{r+1,j}=x_{j+1}t_{r,j+1}+u_{j+1}u_{j+2}\cdots
u_{j+r+1}=u_{j+1}u_{j+2}\cdots u_{j+r+1}+x_{j+1}t_{r,j+1}.$

The same reasoning (applied to $y$ and $t_{r,j}^{\prime}$ instead of $x$ and
$t_{r,j}$) yields

$t_{r+1,j}^{\prime}=u_{j+1}u_{j+2}\cdots u_{j+r+1}+y_{j+1}t_{r,j+1}^{\prime}.$

Hence,

$\displaystyle\dfrac{t_{r+1,j}^{\prime}}{u_{j+1}u_{j+2}\cdots u_{j+r+1}}$
$\displaystyle=\dfrac{u_{j+1}u_{j+2}\cdots
u_{j+r+1}+y_{j+1}t_{r,j+1}^{\prime}}{u_{j+1}u_{j+2}\cdots u_{j+r+1}}$
$\displaystyle=1+\underbrace{\dfrac{y_{j+1}t_{r,j+1}^{\prime}}{u_{j+1}u_{j+2}\cdots
u_{j+r+1}}}_{\begin{subarray}{c}=\dfrac{y_{j+1}t_{r,j+1}^{\prime}}{u_{j+1}\cdot
u_{j+2}u_{j+3}\cdots u_{j+r+1}}\\\
=\dfrac{y_{j+1}}{u_{j+1}}\cdot\dfrac{t_{r,j+1}^{\prime}}{u_{j+2}u_{j+3}\cdots
u_{j+r+1}}\end{subarray}}$
$\displaystyle=1+\dfrac{y_{j+1}}{u_{j+1}}\cdot\underbrace{\dfrac{t_{r,j+1}^{\prime}}{u_{j+2}u_{j+3}\cdots
u_{j+r+1}}}_{\begin{subarray}{c}=\dfrac{t_{n-1,j+2}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r,j+1}}{x_{j+3}x_{j+4}\cdots
x_{j+r+2}}\\\ \text{(by (\ref{pf.lem.f.steps.i.short.IH3}))}\end{subarray}}$
$\displaystyle=1+\dfrac{y_{j+1}}{u_{j+1}}\cdot\dfrac{t_{n-1,j+2}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r,j+1}}{x_{j+3}x_{j+4}\cdots
x_{j+r+2}}.$ (8)

But Lemma 3.9 (h) (applied to $i=j+1$) yields

$y_{j+1}=u_{j+1}\cdot\dfrac{u_{j}t_{n-1,j}}{x_{j+2}t_{n-1,j+2}}.$

Dividing this equality by $u_{j+1}$, we find

$\dfrac{y_{j+1}}{u_{j+1}}=\dfrac{u_{j}t_{n-1,j}}{x_{j+2}t_{n-1,j+2}}.$

Hence, (8) becomes

$\displaystyle\dfrac{t_{r+1,j}^{\prime}}{u_{j+1}u_{j+2}\cdots u_{j+r+1}}$
$\displaystyle=1+\underbrace{\dfrac{y_{j+1}}{u_{j+1}}}_{=\dfrac{u_{j}t_{n-1,j}}{x_{j+2}t_{n-1,j+2}}}\cdot\dfrac{t_{n-1,j+2}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r,j+1}}{x_{j+3}x_{j+4}\cdots
x_{j+r+2}}$
$\displaystyle=1+\dfrac{u_{j}t_{n-1,j}}{x_{j+2}t_{n-1,j+2}}\cdot\dfrac{t_{n-1,j+2}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r,j+1}}{x_{j+3}x_{j+4}\cdots
x_{j+r+2}}$
$\displaystyle=1+\dfrac{u_{j}t_{n-1,j}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r,j+1}}{x_{j+2}\cdot
x_{j+3}x_{j+4}\cdots x_{j+r+2}}$
$\displaystyle=1+\dfrac{u_{j}t_{n-1,j}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r,j+1}}{x_{j+2}x_{j+3}\cdots
x_{j+r+2}}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since }x_{j+2}\cdot
x_{j+3}x_{j+4}\cdots x_{j+r+2}=x_{j+2}x_{j+3}\cdots x_{j+r+2}\right)$
$\displaystyle=\dfrac{t_{n-1,j+r+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+r+2}+u_{j}t_{n-1,j}t_{r,j+1}}{t_{n-1,j+r+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+r+2}}.$ (9)

But Lemma 3.9 (g) (applied to $q=r+1$) yields

$t_{n-1,j+r+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+r+2}+u_{j}t_{n-1,j}t_{r,j+1}=t_{n-1,j+1}t_{r+1,j}.$ (10)

Hence, (9) becomes

$\displaystyle\dfrac{t_{r+1,j}^{\prime}}{u_{j+1}u_{j+2}\cdots u_{j+r+1}}$
$\displaystyle=\dfrac{t_{n-1,j+r+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+r+2}+u_{j}t_{n-1,j}t_{r,j+1}}{t_{n-1,j+r+2}\cdot x_{j+2}x_{j+3}\cdots
x_{j+r+2}}$ $\displaystyle=\dfrac{t_{n-1,j+1}t_{r+1,j}}{t_{n-1,j+r+2}\cdot
x_{j+2}x_{j+3}\cdots x_{j+r+2}}\ \ \ \ \ \ \ \ \ \ \left(\text{by
(\ref{pf.lem.f.steps.i.short.8})}\right)$
$\displaystyle=\dfrac{t_{n-1,j+1}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r+1,j}}{x_{j+2}x_{j+3}\cdots
x_{j+r+2}}.$

Forget that we fixed $j$. We thus have shown that each $j\in\mathbb{Z}$
satisfies

$\dfrac{t_{r+1,j}^{\prime}}{u_{j+1}u_{j+2}\cdots
u_{j+r+1}}=\dfrac{t_{n-1,j+1}}{t_{n-1,j+r+2}}\cdot\dfrac{t_{r+1,j}}{x_{j+2}x_{j+3}\cdots
x_{j+r+2}}.$

In other words, Lemma 3.9 (i) holds for $q=r+1$. This completes the induction
step. Hence, Lemma 3.9 (i) is proved by induction.

(j) Let $j\in\mathbb{Z}$. Then, $u_{j+n}=u_{j}$ (by Convention 3.3). Lemma 3.9
(i) (applied to $q=n-1$) yields

$\displaystyle\dfrac{t_{n-1,j}^{\prime}}{u_{j+1}u_{j+2}\cdots u_{j+n-1}}$
$\displaystyle=\dfrac{t_{n-1,j+1}}{t_{n-1,j+\left(n-1\right)+1}}\cdot\dfrac{t_{n-1,j}}{x_{j+2}x_{j+3}\cdots
x_{j+\left(n-1\right)+1}}$
$\displaystyle=\dfrac{t_{n-1,j+1}}{t_{n-1,j+n}}\cdot\dfrac{t_{n-1,j}}{x_{j+2}x_{j+3}\cdots
x_{j+n}}$ (11)

(since $\left(n-1\right)+1=n$). But $j\equiv j+n\operatorname{mod}n$; hence,
Lemma 3.9 (a) (applied to $r=n-1$ and $j^{\prime}=j+n$) yields
$t_{n-1,j}=t_{n-1,j+n}$. Hence, (11) becomes

$\displaystyle\dfrac{t_{n-1,j}^{\prime}}{u_{j+1}u_{j+2}\cdots u_{j+n-1}}$
$\displaystyle=\dfrac{t_{n-1,j+1}}{t_{n-1,j+n}}\cdot\dfrac{t_{n-1,j}}{x_{j+2}x_{j+3}\cdots
x_{j+n}}=\dfrac{t_{n-1,j+1}}{t_{n-1,j+n}}\cdot\dfrac{t_{n-1,j+n}}{x_{j+2}x_{j+3}\cdots
x_{j+n}}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since
}t_{n-1,j}=t_{n-1,j+n}\right)$
$\displaystyle=\dfrac{t_{n-1,j+1}}{x_{j+2}x_{j+3}\cdots
x_{j+n}}=\dfrac{t_{n-1,j+1}x_{j+1}}{x_{j+2}x_{j+3}\cdots x_{j+n}\cdot
x_{j+1}}=\dfrac{t_{n-1,j+1}x_{j+1}}{x_{1}x_{2}\cdots x_{n}}$

(since $x_{j+2}x_{j+3}\cdots x_{j+n}\cdot x_{j+1}=x_{j+1}\cdot
x_{j+2}x_{j+3}\cdots x_{j+n}=x_{j+1}x_{j+2}\cdots x_{j+n}=x_{1}x_{2}\cdots
x_{n}$ (by Lemma 3.4)). Hence,

$\displaystyle\dfrac{t_{n-1,j+1}x_{j+1}}{x_{1}x_{2}\cdots x_{n}}$
$\displaystyle=\dfrac{t_{n-1,j}^{\prime}}{u_{j+1}u_{j+2}\cdots
u_{j+n-1}}=\dfrac{t_{n-1,j}^{\prime}u_{j+n}}{u_{j+1}u_{j+2}\cdots
u_{j+n-1}\cdot u_{j+n}}=\dfrac{t_{n-1,j}^{\prime}u_{j+n}}{u_{j+1}u_{j+2}\cdots
u_{j+n}}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since
}u_{j+1}u_{j+2}\cdots u_{j+n-1}\cdot u_{j+n}=u_{j+1}u_{j+2}\cdots
u_{j+n}\right)$
$\displaystyle=\dfrac{t_{n-1,j}^{\prime}u_{j}}{u_{j+1}u_{j+2}\cdots u_{j+n}}\
\ \ \ \ \ \ \ \ \ \left(\text{since }u_{j+n}=u_{j}\right)$
$\displaystyle=\dfrac{t_{n-1,j}^{\prime}u_{j}}{u_{1}u_{2}\cdots u_{n}}$

(since $u_{j+1}u_{j+2}\cdots u_{j+n}=u_{1}u_{2}\cdots u_{n}$ (by Lemma 3.4)).
This proves Lemma 3.9 (j).

(k) Let $i\in\mathbb{Z}$. Applying Lemma 3.9 (j) to $j=i-1$, we obtain

$\dfrac{t_{n-1,i-1}^{\prime}u_{i-1}}{u_{1}u_{2}\cdots
u_{n}}=\dfrac{t_{n-1,i}x_{i}}{x_{1}x_{2}\cdots x_{n}}.$

Applying Lemma 3.9 (j) to $j=i+1$, we obtain

$\dfrac{t_{n-1,i+1}^{\prime}u_{i+1}}{u_{1}u_{2}\cdots
u_{n}}=\dfrac{t_{n-1,i+2}x_{i+2}}{x_{1}x_{2}\cdots x_{n}}.$

Dividing the former equality by the latter, we obtain

$\dfrac{t_{n-1,i-1}^{\prime}u_{i-1}}{u_{1}u_{2}\cdots
u_{n}}/\dfrac{t_{n-1,i+1}^{\prime}u_{i+1}}{u_{1}u_{2}\cdots
u_{n}}=\dfrac{t_{n-1,i}x_{i}}{x_{1}x_{2}\cdots
x_{n}}/\dfrac{t_{n-1,i+2}x_{i+2}}{x_{1}x_{2}\cdots x_{n}}.$

This rewrites as

$\dfrac{t_{n-1,i-1}^{\prime}u_{i-1}}{t_{n-1,i+1}^{\prime}u_{i+1}}=\dfrac{t_{n-1,i}x_{i}}{t_{n-1,i+2}x_{i+2}}.$

Multiplying both sides of this equality by $u_{i+1}$, we obtain

$\dfrac{t_{n-1,i-1}^{\prime}u_{i-1}}{t_{n-1,i+1}^{\prime}}=u_{i+1}\cdot\dfrac{t_{n-1,i}x_{i}}{t_{n-1,i+2}x_{i+2}}.$
(12)

Now,

$\displaystyle
u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}^{\prime}}{y_{i+1}t_{n-1,i+1}^{\prime}}$
$\displaystyle=\underbrace{\dfrac{t_{n-1,i-1}^{\prime}u_{i-1}}{t_{n-1,i+1}^{\prime}}}_{\begin{subarray}{c}=u_{i+1}\cdot\dfrac{t_{n-1,i}x_{i}}{t_{n-1,i+2}x_{i+2}}\\\
\text{(by (\ref{pf.lem.f.steps.k.short.4}))}\end{subarray}}\cdot
u_{i}/\underbrace{y_{i+1}}_{\begin{subarray}{c}=u_{i+1}\cdot\dfrac{u_{i}t_{n-1,i}}{x_{i+2}t_{n-1,i+2}}\\\
\text{(by Lemma \ref{lem.f.steps} {(h)},}\\\ \text{applied to }i+1\text{
instead of }i\text{)}\end{subarray}}$
$\displaystyle=u_{i+1}\cdot\dfrac{t_{n-1,i}x_{i}}{t_{n-1,i+2}x_{i+2}}\cdot
u_{i}/\left(u_{i+1}\cdot\dfrac{u_{i}t_{n-1,i}}{x_{i+2}t_{n-1,i+2}}\right)=x_{i}.$

This proves Lemma 3.9 (k).

######  Lemma 3.11.

Let $x\in\mathbb{K}^{n}$ be an $n$-tuple. For each $j\in\mathbb{Z}$, let

$q_{j}=\sum\limits_{k=0}^{n-1}\underbrace{x_{j+1}x_{j+2}\cdots
x_{j+k}}_{=\prod\limits_{i=1}^{k}x_{j+i}}\cdot\underbrace{u_{j+k+1}u_{j+k+2}\cdots
u_{j+n-1}}_{=\prod\limits_{i=k+1}^{n-1}u_{j+i}}.$

Let $z\in\mathbb{K}^{n}$ be such that

$z_{i}=u_{i}\cdot\dfrac{u_{i-1}q_{i-1}}{x_{i+1}q_{i+1}}\ \ \ \ \ \ \ \ \ \
\text{for each }i\in\left\\{1,2,\ldots,n\right\\}.$

Then, $\mathbf{f}_{u}\left(x\right)=z$.

######  Proof 3.12 (Proof of Lemma 3.11.).

Let $t_{r,j}$ and $y$ be as in Definition 3.5. Then, $t_{n-1,j}=q_{j}$ for
each $j\in\mathbb{Z}$ (by comparing the definitions of $t_{n-1,j}$ and
$q_{j}$). Hence, $z_{i}=y_{i}$ for each $i\in\left\\{1,2,\ldots,n\right\\}$
(by comparing the definitions of $z_{i}$ and $y_{i}$). Hence,
$z=y=\mathbf{f}_{u}\left(x\right)$ (since $\mathbf{f}_{u}\left(x\right)$ was
defined to be $y$). This proves Lemma 3.11.

For future convenience, let us restate Lemma 3.11 with different labels:

######  Lemma 3.13.

Let $y\in\mathbb{K}^{n}$ be an $n$-tuple. For each $j\in\mathbb{Z}$, let

$r_{j}=\sum\limits_{k=0}^{n-1}\underbrace{y_{j+1}y_{j+2}\cdots
y_{j+k}}_{=\prod\limits_{i=1}^{k}y_{j+i}}\cdot\underbrace{u_{j+k+1}u_{j+k+2}\cdots
u_{j+n-1}}_{=\prod\limits_{i=k+1}^{n-1}u_{j+i}}.$

Let $x\in\mathbb{K}^{n}$ be such that

$x_{i}=u_{i}\cdot\dfrac{u_{i-1}r_{i-1}}{y_{i+1}r_{i+1}}\ \ \ \ \ \ \ \ \ \
\text{for each }i\in\left\\{1,2,\ldots,n\right\\}.$

Then, $\mathbf{f}_{u}\left(y\right)=x$.

######  Proof 3.14 (Proof of Lemma 3.13.).

Lemma 3.13 is just Lemma 3.11, with $x$, $q_{j}$ and $z$ renamed as $y$,
$r_{j}$ and $x$.

We are now ready for the proof of Theorem 3.8:

######  Proof 3.15 (Proof of Theorem 3.8.).

(a) Let $x\in\mathbb{K}^{n}$. We shall prove that
$\left(\mathbf{f}_{u}\circ\mathbf{f}_{u}\right)\left(x\right)=x$.

Let $t_{r,j}$ and $y$ be as in Definition 3.5. Then,
$\mathbf{f}_{u}\left(x\right)=y$ (by the definition of $\mathbf{f}_{u}$), so
that $y=\mathbf{f}_{u}\left(x\right)$. Let $t_{r,j}^{\prime}$ (for each
$r\in\mathbb{N}$ and $j\in\mathbb{Z}$) be as in Lemma 3.9. The definition of
$t_{n-1,j}^{\prime}$ shows that

$t_{n-1,j}^{\prime}=\sum\limits_{k=0}^{n-1}\underbrace{y_{j+1}y_{j+2}\cdots
y_{j+k}}_{=\prod\limits_{i=1}^{k}y_{j+i}}\cdot\underbrace{u_{j+k+1}u_{j+k+2}\cdots
u_{j+n-1}}_{=\prod\limits_{i=k+1}^{n-1}u_{j+i}}$

for each $j\in\mathbb{Z}$. Lemma 3.9 (k) shows that

$x_{i}=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}^{\prime}}{y_{i+1}t_{n-1,i+1}^{\prime}}\
\ \ \ \ \ \ \ \ \ \text{for each }i\in\left\\{1,2,\ldots,n\right\\}.$

Thus, Lemma 3.13 (applied to $r_{j}=t_{n-1,j}^{\prime}$) yields that
$\mathbf{f}_{u}\left(y\right)=x$. Hence,
$x=\mathbf{f}_{u}\left(\underbrace{y}_{=\mathbf{f}_{u}\left(x\right)}\right)=\mathbf{f}_{u}\left(\mathbf{f}_{u}\left(x\right)\right)=\left(\mathbf{f}_{u}\circ\mathbf{f}_{u}\right)\left(x\right)$.
In other words,
$\left(\mathbf{f}_{u}\circ\mathbf{f}_{u}\right)\left(x\right)=x$.

Forget that we fixed $x$. We thus have proved that
$\left(\mathbf{f}_{u}\circ\mathbf{f}_{u}\right)\left(x\right)=x$ for each
$x\in\mathbb{K}^{n}$. In other words,
$\mathbf{f}_{u}\circ\mathbf{f}_{u}=\operatorname*{id}$. In other words,
$\mathbf{f}_{u}$ is an involution. This proves Theorem 3.8 (a).

(b) Let $t_{r,j}$ be as in Definition 3.5. Note that the $y$ from Definition
3.5 is precisely the $y$ in Theorem 3.8 (b) (because both $y$’s satisfy
$\mathbf{f}_{u}\left(x\right)=y$).

Lemma 3.9 (a) yields $t_{n-1,0}=t_{n-1,n}$ (since $0\equiv
n\operatorname{mod}n$) and $t_{n-1,1}=t_{n-1,n+1}$ (since $1\equiv
n+1\operatorname{mod}n$). Multiplying these two equalities, we obtain
$t_{n-1,0}t_{n-1,1}=t_{n-1,n}t_{n-1,n+1}$, whence

$\dfrac{t_{n-1,0}t_{n-1,1}}{t_{n-1,n}t_{n-1,n+1}}=1.$ (13)

We have

$\displaystyle y_{1}y_{2}\cdots y_{n}$
$\displaystyle=\prod\limits_{i=1}^{n}\underbrace{y_{i}}_{\begin{subarray}{c}=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}\\\
\text{(by the definition of }y\\\ \text{in Definition
\ref{def.f})}\end{subarray}}=\prod\limits_{i=1}^{n}\left(u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}\right)$
$\displaystyle=\left(\prod\limits_{i=1}^{n}u_{i}\right)\cdot\dfrac{\left(\prod\limits_{i=1}^{n}u_{i-1}\right)\cdot\left(\prod\limits_{i=1}^{n}t_{n-1,i-1}\right)}{\left(\prod\limits_{i=1}^{n}x_{i+1}\right)\cdot\left(\prod\limits_{i=1}^{n}t_{n-1,i+1}\right)}$
$\displaystyle=\underbrace{\left(\prod\limits_{i=1}^{n}u_{i}\right)}_{=u_{1}u_{2}\cdots
u_{n}}\cdot\underbrace{\left(\prod\limits_{i=1}^{n}u_{i-1}\right)}_{\begin{subarray}{c}=u_{0}u_{1}\cdots
u_{n-1}\\\ =u_{1}u_{2}\cdots u_{n}\\\ \text{(by Lemma
\ref{lem.aprod})}\end{subarray}}\cdot\underbrace{\left(\prod\limits_{i=1}^{n}t_{n-1,i-1}\right)}_{\begin{subarray}{c}=t_{n-1,0}t_{n-1,1}\cdots
t_{n-1,n-1}\\\ =\dfrac{t_{n-1,0}t_{n-1,1}\cdots
t_{n-1,n+1}}{t_{n-1,n}t_{n-1,n+1}}\end{subarray}}$ $\displaystyle\ \ \ \ \ \ \
\ \ \
/\left(\underbrace{\left(\prod\limits_{i=1}^{n}x_{i+1}\right)}_{\begin{subarray}{c}=x_{2}x_{3}\cdots
x_{n+1}\\\ =x_{1}x_{2}\cdots x_{n}\\\ \text{(by Lemma
\ref{lem.aprod})}\end{subarray}}\cdot\underbrace{\left(\prod\limits_{i=1}^{n}t_{n-1,i+1}\right)}_{\begin{subarray}{c}=t_{n-1,2}t_{n-1,3}\cdots
t_{n-1,n+1}\\\ =\dfrac{t_{n-1,0}t_{n-1,1}\cdots
t_{n-1,n+1}}{t_{n-1,0}t_{n-1,1}}\end{subarray}}\right)$
$\displaystyle=\left(u_{1}u_{2}\cdots u_{n}\right)\cdot\left(u_{1}u_{2}\cdots
u_{n}\right)\cdot\dfrac{t_{n-1,0}t_{n-1,1}\cdots
t_{n-1,n+1}}{t_{n-1,n}t_{n-1,n+1}}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
/\left(\left(x_{1}x_{2}\cdots x_{n}\right)\cdot\dfrac{t_{n-1,0}t_{n-1,1}\cdots
t_{n-1,n+1}}{t_{n-1,0}t_{n-1,1}}\right)$
$\displaystyle=\dfrac{\left(u_{1}u_{2}\cdots
u_{n}\right)^{2}}{x_{1}x_{2}\cdots
x_{n}}\cdot\underbrace{\dfrac{t_{n-1,0}t_{n-1,1}}{t_{n-1,n}t_{n-1,n+1}}}_{\begin{subarray}{c}=1\\\
\text{(by
(\ref{pf.thm.f.full.b.1}))}\end{subarray}}=\dfrac{\left(u_{1}u_{2}\cdots
u_{n}\right)^{2}}{x_{1}x_{2}\cdots x_{n}},$

so that

$y_{1}y_{2}\cdots y_{n}\cdot x_{1}x_{2}\cdots x_{n}=\left(u_{1}u_{2}\cdots
u_{n}\right)^{2}.$

This proves Theorem 3.8 (b).

(c) Let $t_{r,j}$ be as in Definition 3.5. Note that the $y$ from Definition
3.5 is precisely the $y$ in Theorem 3.8 (c) (because both $y$’s satisfy
$\mathbf{f}_{u}\left(x\right)=y$).

Let $i\in\mathbb{Z}$. Then,

$\displaystyle
u_{i}+\underbrace{y_{i}}_{\begin{subarray}{c}=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}\\\
\text{(by Lemma \ref{lem.f.steps} {(h)})}\end{subarray}}$
$\displaystyle=u_{i}+u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}=u_{i}\left(1+\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}\right)=u_{i}\cdot\dfrac{x_{i+1}t_{n-1,i+1}+u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}$
$\displaystyle=\dfrac{u_{i}}{x_{i+1}t_{n-1,i+1}}\underbrace{\left(x_{i+1}t_{n-1,i+1}+u_{i-1}t_{n-1,i-1}\right)}_{\begin{subarray}{c}=\left(x_{i}+u_{i}\right)t_{n-1,i}\\\
\text{(by Lemma \ref{lem.f.steps} {(f)})}\end{subarray}}$
$\displaystyle=\dfrac{u_{i}}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}.$
(14)

Now,

$\displaystyle\dfrac{1}{u_{i}}+\dfrac{1}{y_{i}}$
$\displaystyle=\underbrace{\left(u_{i}+y_{i}\right)}_{\begin{subarray}{c}=\dfrac{u_{i}}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}\\\
\text{(by (\ref{pf.thm.f.full.c.1}))}\end{subarray}}/\left(u_{i}\cdot
y_{i}\right)=\dfrac{u_{i}}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}/\left(u_{i}\cdot
y_{i}\right)$
$\displaystyle=\dfrac{1}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}/\underbrace{y_{i}}_{\begin{subarray}{c}=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}\\\
\text{(by Lemma \ref{lem.f.steps} {(h)})}\end{subarray}}$
$\displaystyle=\dfrac{1}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}/\left(u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}\right)=\dfrac{\left(x_{i}+u_{i}\right)t_{n-1,i}}{u_{i}u_{i-1}t_{n-1,i-1}}.$

The same argument (applied to $i+1$ instead of $i$) yields

$\dfrac{1}{u_{i+1}}+\dfrac{1}{y_{i+1}}=\dfrac{\left(x_{i+1}+u_{i+1}\right)t_{n-1,i+1}}{u_{i+1}u_{\left(i+1\right)-1}t_{n-1,\left(i+1\right)-1}}=\dfrac{\left(x_{i+1}+u_{i+1}\right)t_{n-1,i+1}}{u_{i+1}u_{i}t_{n-1,i}}$

(since $\left(i+1\right)-1=i$). Multiplying (14) with this equality, we obtain

$\displaystyle\left(u_{i}+y_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{y_{i+1}}\right)$
$\displaystyle=\dfrac{u_{i}}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}\cdot\dfrac{\left(x_{i+1}+u_{i+1}\right)t_{n-1,i+1}}{u_{i+1}u_{i}t_{n-1,i}}$
$\displaystyle=\underbrace{\left(x_{i}+u_{i}\right)}_{=u_{i}+x_{i}}\cdot\underbrace{\dfrac{x_{i+1}+u_{i+1}}{x_{i+1}u_{i+1}}}_{=\dfrac{1}{u_{i+1}}+\dfrac{1}{x_{i+1}}}=\left(u_{i}+x_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{x_{i+1}}\right).$

This proves Theorem 3.8 (c).

(d) Let $t_{r,j}$ be as in Definition 3.5. Note that the $y$ from Definition
3.5 is precisely the $y$ in Theorem 3.8 (d) (because both $y$’s satisfy
$\mathbf{f}_{u}\left(x\right)=y$).

We have

$\displaystyle\prod\limits_{i=1}^{n}x_{i+1}$ $\displaystyle=x_{2}x_{3}\cdots
x_{n+1}=x_{1}x_{2}\cdots x_{n}\ \ \ \ \ \ \ \ \ \ \left(\text{by Lemma
\ref{lem.aprod}}\right)$ $\displaystyle=\prod\limits_{i=1}^{n}x_{i}$ (15)

and

$\displaystyle\prod\limits_{i=1}^{n}t_{n-1,i+1}$
$\displaystyle=\prod\limits_{i=2}^{n+1}t_{n-1,i}\ \ \ \ \ \ \ \ \ \
\left(\text{here, we have substituted }i\text{ for }i+1\text{ in the
product}\right)$
$\displaystyle=\underbrace{t_{n-1,n+1}}_{\begin{subarray}{c}=t_{n-1,1}\\\
\text{(by Lemma \ref{lem.f.steps} {(a)},}\\\ \text{since }n+1\equiv
1\operatorname{mod}n\text{)}\end{subarray}}\prod\limits_{i=2}^{n}t_{n-1,i}=t_{n-1,1}\prod\limits_{i=2}^{n}t_{n-1,i}$
$\displaystyle=\prod\limits_{i=1}^{n}t_{n-1,i}.$ (16)

Every $i\in\mathbb{Z}$ satisfies (14) (as we have shown in the proof of
Theorem 3.8 (c) above). Hence,

$\displaystyle\prod\limits_{i=1}^{n}\underbrace{\left(u_{i}+y_{i}\right)}_{\begin{subarray}{c}=\dfrac{u_{i}}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}\\\
\text{(by (\ref{pf.thm.f.full.c.1}))}\end{subarray}}$
$\displaystyle=\prod\limits_{i=1}^{n}\left(\dfrac{u_{i}}{x_{i+1}t_{n-1,i+1}}\left(x_{i}+u_{i}\right)t_{n-1,i}\right)$
$\displaystyle=\dfrac{\prod\limits_{i=1}^{n}u_{i}}{\left(\prod\limits_{i=1}^{n}x_{i+1}\right)\left(\prod\limits_{i=1}^{n}t_{n-1,i+1}\right)}\left(\prod\limits_{i=1}^{n}\left(x_{i}+u_{i}\right)\right)\left(\prod\limits_{i=1}^{n}t_{n-1,i}\right)$
$\displaystyle=\dfrac{\prod\limits_{i=1}^{n}u_{i}}{\left(\prod\limits_{i=1}^{n}x_{i}\right)\left(\prod\limits_{i=1}^{n}t_{n-1,i}\right)}\left(\prod\limits_{i=1}^{n}\left(x_{i}+u_{i}\right)\right)\left(\prod\limits_{i=1}^{n}t_{n-1,i}\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(\text{by
(\ref{pf.thm.f.full.d.1}) and (\ref{pf.thm.f.full.d.2})}\right)$
$\displaystyle=\left(\prod\limits_{i=1}^{n}u_{i}\right)\underbrace{\dfrac{\prod\limits_{i=1}^{n}\left(x_{i}+u_{i}\right)}{\prod\limits_{i=1}^{n}x_{i}}}_{=\prod\limits_{i=1}^{n}\dfrac{x_{i}+u_{i}}{x_{i}}}=\left(\prod\limits_{i=1}^{n}u_{i}\right)\prod\limits_{i=1}^{n}\dfrac{x_{i}+u_{i}}{x_{i}}.$

Thus,

$\dfrac{\prod\limits_{i=1}^{n}\left(u_{i}+y_{i}\right)}{\prod\limits_{i=1}^{n}u_{i}}=\prod\limits_{i=1}^{n}\underbrace{\dfrac{x_{i}+u_{i}}{x_{i}}}_{=\dfrac{u_{i}+x_{i}}{x_{i}}}=\prod\limits_{i=1}^{n}\dfrac{u_{i}+x_{i}}{x_{i}},$

so that

$\prod\limits_{i=1}^{n}\dfrac{u_{i}+x_{i}}{x_{i}}=\dfrac{\prod\limits_{i=1}^{n}\left(u_{i}+y_{i}\right)}{\prod\limits_{i=1}^{n}u_{i}}=\prod\limits_{i=1}^{n}\dfrac{u_{i}+y_{i}}{u_{i}}.$

This proves Theorem 3.8 (d).

Let us observe one more property of the involution $\mathbf{f}_{u}$ (even
though we will have no use for it):

######  Proposition 3.16.

Let $x\in\mathbb{K}^{n}$ be such that $x_{1}x_{2}\cdots x_{n}=u_{1}u_{2}\cdots
u_{n}$. Then, $\mathbf{f}_{u}\left(x\right)=x$.

######  Proof 3.17 (Proof of Proposition 3.16.).

Let $t_{r,j}$ and $y$ be as in Definition 3.5. Then,
$\mathbf{f}_{u}\left(x\right)=y$ (by the definition of $\mathbf{f}_{u}$).

Let $i\in\mathbb{Z}$. We shall first show that
$u_{i-1}t_{n-1,i-1}=x_{i}t_{n-1,i}$.

Indeed, the definition of $t_{n-1,i}$ yields

$t_{n-1,i}=\sum\limits_{k=0}^{n-1}x_{i+1}x_{i+2}\cdots x_{i+k}\cdot
u_{i+k+1}u_{i+k+2}\cdots u_{i+n-1}.$

Multiplying both sides of this equality by $x_{i}$, we find

$\displaystyle x_{i}t_{n-1,i}$
$\displaystyle=x_{i}\sum\limits_{k=0}^{n-1}x_{i+1}x_{i+2}\cdots x_{i+k}\cdot
u_{i+k+1}u_{i+k+2}\cdots u_{i+n-1}$
$\displaystyle=\sum\limits_{k=0}^{n-1}\underbrace{x_{i}\cdot
x_{i+1}x_{i+2}\cdots x_{i+k}}_{=x_{i}x_{i+1}\cdots x_{i+k}}\cdot
u_{i+k+1}u_{i+k+2}\cdots u_{i+n-1}$
$\displaystyle=\sum\limits_{k=0}^{n-1}x_{i}x_{i+1}\cdots x_{i+k}\cdot
u_{i+k+1}u_{i+k+2}\cdots u_{i+n-1}$
$\displaystyle=\underbrace{x_{i}x_{i+1}\cdots
x_{i+n-1}}_{\begin{subarray}{c}=x_{1}x_{2}\cdots x_{n}\\\ \text{(by Lemma
\ref{lem.aprod})}\end{subarray}}\cdot\underbrace{u_{i+n}u_{i+n+1}\cdots
u_{i+n-1}}_{=\left(\text{empty product}\right)=1}$ $\displaystyle\ \ \ \ \ \ \
\ \ \ +\sum\limits_{k=0}^{n-2}x_{i}x_{i+1}\cdots x_{i+k}\cdot
u_{i+k+1}u_{i+k+2}\cdots u_{i+n-1}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \left(\text{here, we have split off the addend for }k=n-1\text{
from the sum}\right)$ $\displaystyle=\underbrace{x_{1}x_{2}\cdots
x_{n}}_{=u_{1}u_{2}\cdots
u_{n}}+\underbrace{\sum\limits_{k=0}^{n-2}x_{i}x_{i+1}\cdots x_{i+k}\cdot
u_{i+k+1}u_{i+k+2}\cdots
u_{i+n-1}}_{\begin{subarray}{c}=\sum\limits_{k=1}^{n-1}x_{i}x_{i+1}\cdots
x_{i+k-1}\cdot u_{i+k}u_{i+k+1}\cdots u_{i+n-1}\\\ \text{(here, we have
substituted }k-1\text{ for }k\text{ in the sum)}\end{subarray}}$
$\displaystyle=u_{1}u_{2}\cdots
u_{n}+\sum\limits_{k=1}^{n-1}x_{i}x_{i+1}\cdots x_{i+k-1}\cdot
u_{i+k}u_{i+k+1}\cdots u_{i+n-1}.$ (17)

On the other hand, we have $u_{i-1}=u_{i+n-1}$ (since $i-1\equiv
i+n-1\operatorname{mod}n$) and

$\displaystyle t_{n-1,i-1}$
$\displaystyle=\sum\limits_{k=0}^{n-1}\underbrace{x_{\left(i-1\right)+1}x_{\left(i-1\right)+2}\cdots
x_{\left(i-1\right)+k}}_{=x_{i}x_{i+1}\cdots
x_{i+k-1}}\cdot\underbrace{u_{\left(i-1\right)+k+1}u_{\left(i-1\right)+k+2}\cdots
u_{\left(i-1\right)+n-1}}_{=u_{i+k}u_{i+k+1}\cdots u_{i+n-2}}$ $\displaystyle\
\ \ \ \ \ \ \ \ \ \left(\text{by the definition of }t_{n-1,i-1}\right)$
$\displaystyle=\sum\limits_{k=0}^{n-1}x_{i}x_{i+1}\cdots x_{i+k-1}\cdot
u_{i+k}u_{i+k+1}\cdots u_{i+n-2}.$

Multiplying these two equalities, we obtain

$\displaystyle u_{i-1}t_{n-1,i-1}$
$\displaystyle=u_{i+n-1}\sum\limits_{k=0}^{n-1}x_{i}x_{i+1}\cdots
x_{i+k-1}\cdot u_{i+k}u_{i+k+1}\cdots u_{i+n-2}$
$\displaystyle=\sum\limits_{k=0}^{n-1}x_{i}x_{i+1}\cdots
x_{i+k-1}\cdot\underbrace{u_{i+k}u_{i+k+1}\cdots u_{i+n-2}\cdot
u_{i+n-1}}_{=u_{i+k}u_{i+k+1}\cdots u_{i+n-1}}$
$\displaystyle=\sum\limits_{k=0}^{n-1}x_{i}x_{i+1}\cdots x_{i+k-1}\cdot
u_{i+k}u_{i+k+1}\cdots u_{i+n-1}$
$\displaystyle=\underbrace{x_{i}x_{i+1}\cdots x_{i+0-1}}_{=\left(\text{empty
product}\right)=1}\cdot\underbrace{u_{i+0}u_{i+0+1}\cdots
u_{i+n-1}}_{\begin{subarray}{c}=u_{i}u_{i+1}\cdots u_{i+n-1}\\\
=u_{1}u_{2}\cdots u_{n}\\\ \text{(by Lemma \ref{lem.aprod})}\end{subarray}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ +\sum\limits_{k=1}^{n-1}x_{i}x_{i+1}\cdots
x_{i+k-1}\cdot u_{i+k}u_{i+k+1}\cdots u_{i+n-1}$ $\displaystyle\ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \left(\text{here, we have split off the addend for
}k=0\text{ from the sum}\right)$ $\displaystyle=u_{1}u_{2}\cdots
u_{n}+\sum\limits_{k=1}^{n-1}x_{i}x_{i+1}\cdots x_{i+k-1}\cdot
u_{i+k}u_{i+k+1}\cdots u_{i+n-1}.$

Comparing this with (17), we obtain

$u_{i-1}t_{n-1,i-1}=x_{i}t_{n-1,i}.$ (18)

The same argument (applied to $i+1$ instead of $i$) yields

$u_{i}t_{n-1,i}=x_{i+1}t_{n-1,i+1}.$ (19)

Now, the definition of $y$ yields

$\displaystyle y_{i}$
$\displaystyle=u_{i}\cdot\dfrac{u_{i-1}t_{n-1,i-1}}{x_{i+1}t_{n-1,i+1}}=u_{i}\underbrace{u_{i-1}t_{n-1,i-1}}_{\begin{subarray}{c}=x_{i}t_{n-1,i}\\\
\text{(by (\ref{pf.prop.f.equal-
case.short.4}))}\end{subarray}}/\underbrace{\left(x_{i+1}t_{n-1,i+1}\right)}_{\begin{subarray}{c}=u_{i}t_{n-1,i}\\\
\text{(by (\ref{pf.prop.f.equal-case.short.5}))}\end{subarray}}$
$\displaystyle=u_{i}x_{i}t_{n-1,i}/\left(u_{i}t_{n-1,i}\right)=x_{i}.$

Now, forget that we fixed $i$. We thus have proved that $y_{i}=x_{i}$ for each
$i\in\mathbb{Z}$. Thus, in particular, $y_{i}=x_{i}$ for each
$i\in\left\\{1,2,\ldots,n\right\\}$. In other words, $y=x$. Hence,
$\mathbf{f}_{u}\left(x\right)=y=x$. This proves Proposition 3.16.

######  Remark 3.18.

There is an alternative proof of Theorem 3.8 (a) that avoids the use of the
more complicated parts of Lemma 3.9 (specifically, of parts (g), (i), (j) and
(k)). Let us outline this proof:

The claim of Theorem 3.8 (a) can be restated as the equality
$\mathbf{f}_{u}\left(\mathbf{f}_{u}\left(x\right)\right)=x$ for each
$x\in\mathbb{K}^{n}$. This equality boils down to a set of identities between
rational functions in the variables
$u_{1},u_{2},\ldots,u_{n},x_{1},x_{2},\ldots,x_{n}$ (since each entry of
$\mathbf{f}_{u}\left(x\right)$ is a rational function in these variables, and
each entry of $\mathbf{f}_{u}\left(\mathbf{f}_{u}\left(x\right)\right)$ is a
rational function in the former entries as well as
$u_{1},u_{2},\ldots,u_{n}$). These rational functions are subtraction-free
(i.e., no subtraction signs appear in them), and thus are defined over any
semifield. But there is a general principle saying that if we need to prove an
identity between two subtraction-free rational functions, it is sufficient to
prove that it holds over the semifield $\mathbb{Q}_{+}$ from Example 3.2.
(Indeed, this principle follows from the fact that any subtraction-free
rational function can be rewritten as a ratio of two polynomials with
nonnegative integer coefficients, and thus an identity between two
subtraction-free rational functions can be rewritten as an identity between
two such polynomials; but the latter kind of identity will necessarily be true
if it has been checked on all positive rational numbers.)

As a consequence of this discussion, in order to prove Theorem 3.8 (a) in full
generality, it suffices to prove Theorem 3.8 (a) in the case when
$\mathbb{K}=\mathbb{Q}_{+}$. So let us restrict ourselves to this case. Let
$x\in\mathbb{K}^{n}$. We must show that
$\mathbf{f}_{u}\left(\mathbf{f}_{u}\left(x\right)\right)=x$.

Let $y=\mathbf{f}_{u}\left(x\right)$, and let
$z=\mathbf{f}_{u}\left(y\right)$. We will show that $z=x$.

Assume the contrary. Thus, $z\neq x$. Hence, there exists some
$i\in\left\\{1,2,\ldots,n\right\\}$ such that $z_{i}\neq x_{i}$. Consider this
$i$. Hence, either $z_{i}>x_{i}$ or $z_{i}<x_{i}$. We WLOG assume that
$z_{i}>x_{i}$ (since the proof in the case of $z_{i}<x_{i}$ is identical,
except that all inequality signs are reversed). But Theorem 3.8 (c) yields

$\left(u_{i}+x_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{x_{i+1}}\right)=\left(u_{i}+y_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{y_{i+1}}\right).$

Likewise, Theorem 3.8 (c) (applied to $y$ and $z$ instead of $x$ and $y$)
yields

$\left(u_{i}+y_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{y_{i+1}}\right)=\left(u_{i}+z_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{z_{i+1}}\right)$

(since $z=\mathbf{f}_{u}\left(y\right)$). Hence,

$\displaystyle\left(u_{i}+x_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{x_{i+1}}\right)$
$\displaystyle=\left(u_{i}+y_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{y_{i+1}}\right)$
$\displaystyle=\left(u_{i}+\underbrace{z_{i}}_{>x_{i}}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{z_{i+1}}\right)$
$\displaystyle>\left(u_{i}+x_{i}\right)\left(\dfrac{1}{u_{i+1}}+\dfrac{1}{z_{i+1}}\right).$

Cancelling the positive number $u_{i}+x_{i}$ from this inequality, we obtain
$\dfrac{1}{u_{i+1}}+\dfrac{1}{x_{i+1}}>\dfrac{1}{u_{i+1}}+\dfrac{1}{z_{i+1}}$.
Hence, $\dfrac{1}{x_{i+1}}>\dfrac{1}{z_{i+1}}$, so that $z_{i+1}>x_{i+1}$.
Thus, from $z_{i}>x_{i}$, we have obtained $z_{i+1}>x_{i+1}$. The same
reasoning (but applied to $i+1$ instead of $i$) now yields $z_{i+2}>x_{i+2}$
(since $z_{i+1}>x_{i+1}$). Proceeding in the same way, we successively obtain
$z_{i+3}>x_{i+3}$ and $z_{i+4}>x_{i+4}$ and $z_{i+5}>x_{i+5}$ and so on.
Hence,

$\underbrace{z_{i}}_{>x_{i}}\underbrace{z_{i+1}}_{>x_{i+1}}\cdots\underbrace{z_{i+n-1}}_{>x_{i+n-1}}>x_{i}x_{i+1}\cdots
x_{i+n-1}.$ (20)

But Theorem 3.8 (b) yields

$y_{1}y_{2}\cdots y_{n}\cdot x_{1}x_{2}\cdots x_{n}=\left(u_{1}u_{2}\cdots
u_{n}\right)^{2}.$

Also, Theorem 3.8 (b) (applied to $y$ and $z$ instead of $x$ and $y$) yields

$z_{1}z_{2}\cdots z_{n}\cdot y_{1}y_{2}\cdots y_{n}=\left(u_{1}u_{2}\cdots
u_{n}\right)^{2}$

(since $z=\mathbf{f}_{u}\left(y\right)$). Comparing these two equalities, we
find $y_{1}y_{2}\cdots y_{n}\cdot x_{1}x_{2}\cdots x_{n}=z_{1}z_{2}\cdots
z_{n}\cdot y_{1}y_{2}\cdots y_{n}$, so that

$x_{1}x_{2}\cdots x_{n}=z_{1}z_{2}\cdots z_{n}.$ (21)

But Lemma 3.4 yields $z_{i}z_{i+1}\cdots z_{i+n-1}=z_{1}z_{2}\cdots z_{n}$ and
$x_{i}x_{i+1}\cdots x_{i+n-1}=x_{1}x_{2}\cdots x_{n}$. In light of these two
equalities, we can rewrite (20) as $z_{1}z_{2}\cdots z_{n}>x_{1}x_{2}\cdots
x_{n}$. This, however, contradicts (21). This contradiction shows that our
assumption was false, thus concluding our proof of $z=x$.

Now,
$\mathbf{f}_{u}\left(\underbrace{\mathbf{f}_{u}\left(x\right)}_{=y}\right)=\mathbf{f}_{u}\left(y\right)=z=x$,
as we wanted to prove. Hence, Theorem 3.8 (a) is proved again.

We shall take up the study of the birational involution $\mathbf{f}_{u}$ again
in Subsection 5.2, where we will pose several questions about its meaning and
uniqueness properties.

##  4 Proof of the main theorem

We shall now slowly approach the proof of Theorem 2.2 through a long sequence
of auxiliary results, some of them easy, some well-known.

###  4.1 From the life of snakes

Recall the conventions introduced in Section 1 and in Convention 2.1. Let us
next introduce some further notations.

######  Definition 4.1.

  1. (a)

Let $\mathcal{L}$ denote the ring $\mathbf{k}\left[x_{1}^{\pm 1},x_{2}^{\pm
1},\ldots,x_{n}^{\pm 1}\right]$ of Laurent polynomials in the $n$
indeterminates $x_{1},x_{2},\ldots,x_{n}$ over $\mathbf{k}$. Clearly, the
polynomial ring $\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]$ is a subring
of $\mathcal{L}$.

  2. (b)

We let $x_{\Pi}$ denote the monomial $x_{1}x_{2}\cdots
x_{n}\in\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]\subseteq\mathcal{L}$.

If $f\in\Lambda$ is a symmetric function444or, more generally, any formal
power series in $\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$
that is of bounded degree, and if $a_{1},a_{2},\ldots,a_{n}$ are $n$ elements
of a commutative $\mathbf{k}$-algebra $A$, then
$f\left(a_{1},a_{2},\ldots,a_{n},0,0,0,\ldots\right)$ means the result of
substituting $a_{1},a_{2},\ldots,a_{n},0,0,0,\ldots$ for
$x_{1},x_{2},\ldots,x_{n},x_{n+1},x_{n+2},x_{n+3},\ldots$ in $f$. This is a
well-defined element of $A$ (see [GriRei20, Exercise 2.1.2] for the proof),
and is denoted by $f\left(a_{1},a_{2},\ldots,a_{n}\right)$. It is called the
_evaluation_ of $f$ at $a_{1},a_{2},\ldots,a_{n}$.

For any symmetric function $f\in\Lambda$, the evaluation

$f\left(x_{1},x_{2},\ldots,x_{n}\right)=f\left(x_{1},x_{2},\ldots,x_{n},0,0,0,\ldots\right)$

is a polynomial in $\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]$ and thus
a Laurent polynomial in $\mathcal{L}$. Moreover, for any symmetric function
$f\in\Lambda$, the evaluation

$f\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)=f\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1},0,0,0,\ldots\right)$

is a Laurent polynomial in $\mathcal{L}$ as well.

######  Convention 4.1.

For the rest of Section 4, let us agree to the following notation: If $\gamma$
is an $n$-tuple (of any objects), then we let $\gamma_{i}$ denote the $i$-th
entry of $\gamma$ whenever $i\in\left\\{1,2,\ldots,n\right\\}$. Thus, each
$n$-tuple $\gamma$ satisfies
$\gamma=\left(\gamma_{1},\gamma_{2},\ldots,\gamma_{n}\right)$.

######  Definition 4.2.

  1. (a)

A _snake_ means an $n$-tuple
$\lambda=\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)$ of integers
(not necessarily nonnegative) such that
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$.

  2. (b)

A snake $\lambda$ is said to be _nonnegative_ if it belongs to
$\mathbb{N}^{n}$ (that is, if all its entries are nonnegative). Thus, a
nonnegative snake is the same as a partition having length $\leq n$. In other
words, a nonnegative snake is the same as a partition
$\lambda\in\operatorname*{Par}\left[n\right]$.

  3. (c)

If $\lambda\in\mathbb{Z}^{n}$ is an $n$-tuple, and $d$ is an integer, then
$\lambda+d$ denotes the $n$-tuple
$\left(\lambda_{1}+d,\lambda_{2}+d,\ldots,\lambda_{n}+d\right)\in\mathbb{Z}^{n}$
(which is obtained from $\lambda$ by adding $d$ to each entry), whereas
$\lambda-d$ denotes the $n$-tuple
$\left(\lambda_{1}-d,\lambda_{2}-d,\ldots,\lambda_{n}-d\right)\in\mathbb{Z}^{n}$.
(Thus, $\lambda-d=\lambda+\left(-d\right)$.)

  4. (d)

If $\lambda\in\mathbb{Z}^{n}$, then $\lambda^{\vee}$ denotes the $n$-tuple
$\left(-\lambda_{n},-\lambda_{n-1},\ldots,-\lambda_{1}\right)\in\mathbb{Z}^{n}$.

  5. (e)

We regard $\mathbb{Z}^{n}$ as a $\mathbb{Z}$-module in the obvious way. Thus,
if $\lambda\in\mathbb{Z}^{n}$ and $\mu\in\mathbb{Z}^{n}$ are two $n$-tuples of
integers, then

$\displaystyle\lambda+\mu$
$\displaystyle=\left(\lambda_{1}+\mu_{1},\lambda_{2}+\mu_{2},\ldots,\lambda_{n}+\mu_{n}\right),$
$\displaystyle\lambda-\mu$
$\displaystyle=\left(\lambda_{1}-\mu_{1},\lambda_{2}-\mu_{2},\ldots,\lambda_{n}-\mu_{n}\right).$

  6. (f)

We let $\rho$ denote the nonnegative snake
$\left(n-1,n-2,\ldots,2,1,0\right)$. Thus,

$\rho_{i}=n-i\ \ \ \ \ \ \ \ \ \ \text{for each
}i\in\left\\{1,2,\ldots,n\right\\}.$ (22)

######  Example 4.3.

In this example, let $n=3$.

  1. (a)

The four $3$-tuples $\left(3,1,0\right)$, $\left(2,2,1\right)$,
$\left(1,0,-1\right)$ and $\left(-1,-2,-5\right)$ are examples of snakes.

  2. (b)

The first two of these four snakes (but not the last two) are nonnegative.

  3. (c)

We have $\left(5,3,1\right)+3=\left(8,6,4\right)$ and
$\left(5,3,1\right)-3=\left(2,0,-2\right)$.

  4. (d)

We have $\left(5,2,2\right)^{\vee}=\left(-2,-2,-5\right)$.

  5. (e)

We have $\left(2,1,2\right)+\left(3,4,5\right)=\left(5,5,7\right)$.

  6. (f)

We have $\rho=\left(2,1,0\right)$.

Note that what we call a “snake” here is called a “staircase of height $n$” in
Stembridge’s work [Stembr87], where he uses these snakes to index finite-
dimensional polynomial representations of the group
$\operatorname*{GL}\nolimits_{n}\left(\mathbb{C}\right)$. We avoid calling
them “staircases”, as that word has since been used for other things (in
particular, $\rho$ is often called “the $n$-staircase” in the jargon of
combinatorialists).

The notations introduced in Definition 4.2 have the following properties:

######  Proposition 4.4.

  1. (a)

If $\lambda$ is a snake, and $d$ is an integer, then $\lambda+d$ and
$\lambda-d$ are snakes as well.

  2. (b)

If $\lambda$ is a snake, then $\lambda^{\vee}$ is a snake as well.

  3. (c)

We have $\left(\lambda+\mu\right)+d=\left(\lambda+d\right)+\mu$ for any
$\lambda\in\mathbb{Z}^{n}$, $\mu\in\mathbb{Z}^{n}$ and $d\in\mathbb{Z}$.

  4. (d)

We have $\lambda+\left(d+e\right)=\left(\lambda+d\right)+e$ for any
$\lambda\in\mathbb{Z}^{n}$, $d\in\mathbb{Z}$ and $e\in\mathbb{Z}$.

  5. (e)

We have $\left(\lambda+d\right)-d=\left(\lambda-d\right)+d=\lambda$ for any
$\lambda\in\mathbb{Z}^{n}$ and $d\in\mathbb{Z}$.

######  Proof 4.5 (Proof of Proposition 4.4.).

Completely straightforward.

Let us now assign a Laurent polynomial $a_{\lambda}$ to each
$\lambda\in\mathbb{Z}^{n}$:

######  Definition 4.6.

Let $\lambda\in\mathbb{Z}^{n}$ be any $n$-tuple. Then, we define the Laurent
polynomial

$a_{\lambda}:=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}x_{w\left(1\right)}^{\lambda_{1}}x_{w\left(2\right)}^{\lambda_{2}}\cdots
x_{w\left(n\right)}^{\lambda_{n}}\in\mathcal{L},$

where $\mathfrak{S}_{n}$ is the symmetric group of the set
$\left\\{1,2,\ldots,n\right\\}$ (and where $\left(-1\right)^{w}$ denotes the
sign of a permutation $w$). This Laurent polynomial $a_{\lambda}$ is called
the _alternant_ corresponding to the $n$-tuple $\lambda$.

(The “$a$” in the notation “$a_{\lambda}$” has nothing to do with the $a$ in
Theorem 2.2.)

######  Example 4.7.

We have

$\displaystyle a_{\left(5,3,2\right)}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{3}}\left(-1\right)^{w}x_{w\left(1\right)}^{5}x_{w\left(2\right)}^{3}x_{w\left(3\right)}^{2}$
$\displaystyle=x_{1}^{5}x_{2}^{3}x_{3}^{2}+x_{2}^{5}x_{3}^{3}x_{1}^{2}+x_{3}^{5}x_{1}^{3}x_{2}^{2}-x_{1}^{5}x_{3}^{3}x_{2}^{2}-x_{2}^{5}x_{1}^{3}x_{3}^{2}-x_{3}^{5}x_{2}^{3}x_{1}^{2}.$

The sum in Definition 4.6 is the same kind of sum that appears in the
definition of a determinant. Therefore, we can rewrite the alternant as
follows:

######  Proposition 4.8.

Let $\lambda\in\mathbb{Z}^{n}$ be an $n$-tuple. Then, the alternant
$a_{\lambda}\in\mathcal{L}$ satisfies

$a_{\lambda}=\det\left(\left(x_{j}^{\lambda_{i}}\right)_{1\leq i\leq n,\ 1\leq
j\leq n}\right)=\det\left(\left(x_{i}^{\lambda_{j}}\right)_{1\leq i\leq n,\
1\leq j\leq n}\right).$

Thus, in particular, the alternant $a_{\rho}$ corresponding to the snake

$\rho=\left(n-1,n-2,\ldots,2,1,0\right)=\left(n-1,n-2,\ldots,n-n\right)$

satisfies

$a_{\rho}=\det\left(\left(x_{i}^{n-j}\right)_{1\leq i\leq n,\ 1\leq j\leq
n}\right)=\prod\limits_{1\leq i<j\leq n}\left(x_{i}-x_{j}\right)$

(by the classical formula for the Vandermonde determinant).

We recall a standard concept from commutative algebra: An element $a$ of a
commutative ring $A$ is said to be regular if it has the property that every
$x\in A$ satisfying $ax=0$ must satisfy $x=0$. (Thus, regular elements are the
same as elements that are not zero-divisors, if one does not require zero-
divisors to be nonzero555Unfortunately, there is no agreement in the
literature on whether zero-divisors should be required to be nonzero. This is
one of the reasons why we are avoiding this notion..)

######  Lemma 4.9.

The alternant $a_{\rho}$ is a regular element of $\mathcal{L}$.

######  Proof 4.10 (Proof of Lemma 4.9.).

Let $b\in\mathcal{L}$ be such that $a_{\rho}b=0$. We want to show that $b=0$.

We know that $b$ is a Laurent polynomial, and thus has the form
$b=\dfrac{c}{x_{1}^{u_{1}}x_{2}^{u_{2}}\cdots x_{n}^{u_{n}}}$ for some
$u_{1},u_{2},\ldots,u_{n}\in\mathbb{Z}$ and some polynomial
$c\in\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]$. Consider these
$u_{1},u_{2},\ldots,u_{n}$ and this $c$. From
$b=\dfrac{c}{x_{1}^{u_{1}}x_{2}^{u_{2}}\cdots x_{n}^{u_{n}}}$, we obtain
$c=b\cdot x_{1}^{u_{1}}x_{2}^{u_{2}}\cdots x_{n}^{u_{n}}$. Multiplying this
equality by $a_{\rho}$, we obtain

$a_{\rho}c=\underbrace{a_{\rho}b}_{=0}\cdot x_{1}^{u_{1}}x_{2}^{u_{2}}\cdots
x_{n}^{u_{n}}=0.$

But it is a well-known fact (see, e.g., [Grinbe19, Corollary 4.4]) that the
polynomial $\prod\limits_{1\leq i<j\leq n}\left(x_{i}-x_{j}\right)$ is a
regular element of $\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]$. In other
words, $a_{\rho}$ is a regular element of
$\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]$ (since
$a_{\rho}=\prod\limits_{1\leq i<j\leq n}\left(x_{i}-x_{j}\right)$). Hence,
from $a_{\rho}c=0$, we obtain $c=0$. Now,
$b=\dfrac{c}{x_{1}^{u_{1}}x_{2}^{u_{2}}\cdots x_{n}^{u_{n}}}=0$ (since $c=0$).

Forget that we fixed $b$. We thus have shown that each $b\in\mathcal{L}$
satisfying $a_{\rho}b=0$ satisfies $b=0$. In other words, $a_{\rho}$ is a
regular element of $\mathcal{L}$. This proves Lemma 4.9.

Lemma 4.9 shows that fractions of the form $\dfrac{u}{a_{\rho}}$ (where
$u\in\mathcal{L}$) are well-defined if $u$ is a multiple of $a_{\rho}$. (That
is, there is never more than one $b\in\mathcal{L}$ that satisfies
$a_{\rho}b=u$.)

We notice that the element $x_{\Pi}=x_{1}x_{2}\cdots x_{n}$ of $\mathcal{L}$
is invertible (since $x_{1},x_{2},\ldots,x_{n}$ are invertible in
$\mathcal{L}$).

######  Lemma 4.11.

Let $\lambda\in\mathbb{Z}^{n}$ be any $n$-tuple, and let $d\in\mathbb{Z}$.
Then, $a_{\lambda+d}=x_{\Pi}^{d}a_{\lambda}$.

######  Proof 4.12 (Proof of Lemma 4.11.).

The definition of $a_{\lambda}$ yields

$a_{\lambda}=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}x_{w\left(1\right)}^{\lambda_{1}}x_{w\left(2\right)}^{\lambda_{2}}\cdots
x_{w\left(n\right)}^{\lambda_{n}}.$ (23)

But the definition of $\lambda+d$ yields
$\lambda+d=\left(\lambda_{1}+d,\lambda_{2}+d,\ldots,\lambda_{n}+d\right)$.
Hence, the definition of $a_{\lambda+d}$ yields

$\displaystyle a_{\lambda+d}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\underbrace{x_{w\left(1\right)}^{\lambda_{1}+d}x_{w\left(2\right)}^{\lambda_{2}+d}\cdots
x_{w\left(n\right)}^{\lambda_{n}+d}}_{=\left(x_{w\left(1\right)}^{\lambda_{1}}x_{w\left(2\right)}^{\lambda_{2}}\cdots
x_{w\left(n\right)}^{\lambda_{n}}\right)\left(x_{w\left(1\right)}^{d}x_{w\left(2\right)}^{d}\cdots
x_{w\left(n\right)}^{d}\right)}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\left(x_{w\left(1\right)}^{\lambda_{1}}x_{w\left(2\right)}^{\lambda_{2}}\cdots
x_{w\left(n\right)}^{\lambda_{n}}\right)\underbrace{\left(x_{w\left(1\right)}^{d}x_{w\left(2\right)}^{d}\cdots
x_{w\left(n\right)}^{d}\right)}_{\begin{subarray}{c}=x_{1}^{d}x_{2}^{d}\cdots
x_{n}^{d}\\\ \text{(since
}w:\left\\{1,2,\ldots,n\right\\}\rightarrow\left\\{1,2,\ldots,n\right\\}\\\
\text{is a bijection)}\end{subarray}}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\left(x_{w\left(1\right)}^{\lambda_{1}}x_{w\left(2\right)}^{\lambda_{2}}\cdots
x_{w\left(n\right)}^{\lambda_{n}}\right)\underbrace{\left(x_{1}^{d}x_{2}^{d}\cdots
x_{n}^{d}\right)}_{\begin{subarray}{c}=\left(x_{1}x_{2}\cdots
x_{n}\right)^{d}=x_{\Pi}^{d}\\\ \text{(since }x_{1}x_{2}\cdots
x_{n}=x_{\Pi}\text{)}\end{subarray}}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\left(x_{w\left(1\right)}^{\lambda_{1}}x_{w\left(2\right)}^{\lambda_{2}}\cdots
x_{w\left(n\right)}^{\lambda_{n}}\right)x_{\Pi}^{d}$
$\displaystyle=x_{\Pi}^{d}\underbrace{\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}x_{w\left(1\right)}^{\lambda_{1}}x_{w\left(2\right)}^{\lambda_{2}}\cdots
x_{w\left(n\right)}^{\lambda_{n}}}_{\begin{subarray}{c}=a_{\lambda}\\\
\text{(by
(\ref{pf.lem.alt.move.short.alam=}))}\end{subarray}}=x_{\Pi}^{d}a_{\lambda}.$

This proves Lemma 4.11.

######  Lemma 4.13.

Let $\lambda$ be a snake. Then, $a_{\lambda+\rho}$ is a multiple of $a_{\rho}$
in $\mathcal{L}$.

######  Proof 4.14 (Proof of Lemma 4.13.).

Our proof will consist of two steps:

> Step 1: We will prove Lemma 4.13 in the particular case when $\lambda$ is
> nonnegative.

> Step 2: We will use Lemma 4.11 to derive the general case of Lemma 4.13 from
> this particular case.

We will use this strategy again further on; we shall refer to it as the
_right-shift strategy_.

Here are the details of the two steps:

Step 1: Let us prove that Lemma 4.13 holds in the particular case when
$\lambda$ is nonnegative.

Indeed, let us assume that $\lambda$ is nonnegative. We must show that
$a_{\lambda+\rho}$ is a multiple of $a_{\rho}$ in $\mathcal{L}$.

We know that $\lambda$ is a nonnegative snake, thus a partition of length
$\leq n$. Hence, [GriRei20, Corollary 2.6.7] shows that
$s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)=\dfrac{a_{\lambda+\rho}}{a_{\rho}}$.
Thus, $a_{\lambda+\rho}=a_{\rho}\cdot
s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)$. This shows that
$a_{\lambda+\rho}$ is a multiple of $a_{\rho}$ in $\mathcal{L}$ (since
$s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)\in\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]\subseteq\mathcal{L}$).
Thus, Lemma 4.13 is proved under the assumption that $\lambda$ is nonnegative.
This completes Step 1.

Step 2: Let us now prove Lemma 4.13 in the general case.

We know that $\lambda$ is a snake. Thus,
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$. Hence, each
$i\in\left\\{1,2,\ldots,n\right\\}$ satisfies $\lambda_{i}\geq\lambda_{n}$ and
thus

$\lambda_{i}-\lambda_{n}\geq 0.$ (24)

The snake $\lambda$ may or may not be nonnegative. However, there exists some
integer $d$ such that the snake $\lambda+d$ is nonnegative666Indeed, for
example, we can take $d=-\lambda_{n}$. Then, all entries of $\lambda+d$ have
the form $\lambda_{i}+\underbrace{d}_{=-\lambda_{n}}=\lambda_{i}-\lambda_{n}$
for some $i\in\left\\{1,2,\ldots,n\right\\}$, and thus are nonnegative
(because of (24)); this shows that the snake $\lambda+d$ is nonnegative..
Consider this $d$. Proposition 4.4 (c) (applied to $\mu=\rho$) yields
$\left(\lambda+\rho\right)+d=\left(\lambda+d\right)+\rho$.

The snake $\lambda+d$ is nonnegative; thus, we can apply Lemma 4.13 to
$\lambda+d$ instead of $\lambda$ (because in Step 1, we have proved that Lemma
4.13 holds in the particular case when $\lambda$ is nonnegative). Thus we
conclude that $a_{\left(\lambda+d\right)+\rho}$ is a multiple of $a_{\rho}$ in
$\mathcal{L}$. In other words, there exists some $u\in\mathcal{L}$ such that
$a_{\left(\lambda+d\right)+\rho}=a_{\rho}u$. Consider this $u$. From
$\left(\lambda+\rho\right)+d=\left(\lambda+d\right)+\rho$, we obtain
$a_{\left(\lambda+\rho\right)+d}=a_{\left(\lambda+d\right)+\rho}=a_{\rho}u$.

Lemma 4.11 (applied to $\lambda+\rho$ instead of $\lambda$) yields
$a_{\left(\lambda+\rho\right)+d}=x_{\Pi}^{d}a_{\lambda+\rho}$. Since the
element $x_{\Pi}$ of $\mathcal{L}$ is invertible, we thus obtain

$a_{\lambda+\rho}=\underbrace{\left(x_{\Pi}^{d}\right)^{-1}}_{=x_{\Pi}^{-d}}\underbrace{a_{\left(\lambda+\rho\right)+d}}_{=a_{\rho}u}=x_{\Pi}^{-d}a_{\rho}u=a_{\rho}\cdot
x_{\Pi}^{-d}u.$

Hence, $a_{\lambda+\rho}$ is a multiple of $a_{\rho}$ (since
$x_{\Pi}^{-d}u\in\mathcal{L}$). This proves Lemma 4.13. Thus, Step 2 is
complete, and Lemma 4.13 is proven.

######  Definition 4.15.

Let $\lambda$ be a snake. We define an element
$\overline{s}_{\lambda}\in\mathcal{L}$ by
$\overline{s}_{\lambda}=\dfrac{a_{\lambda+\rho}}{a_{\rho}}$. (This is well-
defined, because Lemma 4.13 shows that $a_{\lambda+\rho}$ is a multiple of
$a_{\rho}$ in $\mathcal{L}$, and because Lemma 4.9 shows that the fraction
$\dfrac{a_{\lambda+\rho}}{a_{\rho}}$ is uniquely defined.)

It makes sense to refer to the elements $\overline{s}_{\lambda}$ just defined
as “Schur Laurent polynomials”. In fact, as the following lemma shows, they
are identical with the Schur polynomials
$s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)$ when the snake $\lambda$ is
nonnegative:

######  Lemma 4.16.

Let $\lambda\in\operatorname*{Par}\left[n\right]$. Then,

$\overline{s}_{\lambda}=s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right).$

######  Proof 4.17 (Proof of Lemma 4.16.).

We know that $\lambda$ is a partition of length $\leq n$ (since
$\lambda\in\operatorname*{Par}\left[n\right]$). Hence, $\lambda$ is a
nonnegative snake. Furthermore, since $\lambda$ is a partition of length $\leq
n$, we can apply [GriRei20, Corollary 2.6.7] and obtain
$s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)=\dfrac{a_{\lambda+\rho}}{a_{\rho}}=\overline{s}_{\lambda}$
(since $\overline{s}_{\lambda}$ was defined to be
$\dfrac{a_{\lambda+\rho}}{a_{\rho}}$). This proves Lemma 4.16.

The Schur Laurent polynomials $\overline{s}_{\lambda}$ appear in Stembridge’s
[Stembr87], where they are named $s_{\lambda}$. (The equivalence of our
definition with his follows from [Stembr87, Theorem 7.1].)

Furthermore, from Lemma 4.11, we can easily obtain an analogous property for
Schur Laurent polynomials:

######  Lemma 4.18.

Let $\lambda\in\mathbb{Z}^{n}$ be any snake, and let $d\in\mathbb{Z}$. Then,
$\overline{s}_{\lambda+d}=x_{\Pi}^{d}\overline{s}_{\lambda}$.

######  Proof 4.19 (Proof of Lemma 4.18.).

Proposition 4.4 (c) (applied to $\mu=\rho$) yields
$\left(\lambda+\rho\right)+d=\left(\lambda+d\right)+\rho$. But Lemma 4.11
(applied to $\lambda+\rho$ instead of $\lambda$) yields
$a_{\left(\lambda+\rho\right)+d}=x_{\Pi}^{d}a_{\lambda+\rho}$. This rewrites
as $a_{\left(\lambda+d\right)+\rho}=x_{\Pi}^{d}a_{\lambda+\rho}$ (since
$\left(\lambda+\rho\right)+d=\left(\lambda+d\right)+\rho$).

The definition of $\overline{s}_{\lambda+d}$ yields

$\overline{s}_{\lambda+d}=\dfrac{a_{\left(\lambda+d\right)+\rho}}{a_{\rho}}=\dfrac{x_{\Pi}^{d}a_{\lambda+\rho}}{a_{\rho}}\
\ \ \ \ \ \ \ \ \ \left(\text{since
}a_{\left(\lambda+d\right)+\rho}=x_{\Pi}^{d}a_{\lambda+\rho}\right).$

Comparing this with

$x_{\Pi}^{d}\underbrace{\overline{s}_{\lambda}}_{\begin{subarray}{c}=\dfrac{a_{\lambda+\rho}}{a_{\rho}}\\\
\text{(by the definition of
}\overline{s}_{\lambda}\text{)}\end{subarray}}=x_{\Pi}^{d}\cdot\dfrac{a_{\lambda+\rho}}{a_{\rho}}=\dfrac{x_{\Pi}^{d}a_{\lambda+\rho}}{a_{\rho}},$

we obtain $\overline{s}_{\lambda+d}=x_{\Pi}^{d}\overline{s}_{\lambda}$. This
proves Lemma 4.18.

######  Lemma 4.20.

Let $\mu,\nu\in\operatorname*{Par}\left[n\right]$. Then,

$\overline{s}_{\mu}\overline{s}_{\nu}=\sum\limits_{\lambda\in\operatorname*{Par}\left[n\right]}c_{\mu,\nu}^{\lambda}\overline{s}_{\lambda}.$

######  Proof 4.21 (Proof of Lemma 4.20.).

It is well-known (see, e.g., [GriRei20, Exercise 2.3.8(b)]) that if $\lambda$
is a partition having length $>n$, then

$s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)=0.$ (25)

We know that $\mu\in\operatorname*{Par}\left[n\right]$. Hence, Lemma 4.16
(applied to $\lambda=\mu$) yields
$\overline{s}_{\mu}=s_{\mu}\left(x_{1},x_{2},\ldots,x_{n}\right)$. Likewise,
$\overline{s}_{\nu}=s_{\nu}\left(x_{1},x_{2},\ldots,x_{n}\right)$. Multiplying
these two equalities, we obtain

$\displaystyle\overline{s}_{\mu}\overline{s}_{\nu}$
$\displaystyle=s_{\mu}\left(x_{1},x_{2},\ldots,x_{n}\right)\cdot
s_{\nu}\left(x_{1},x_{2},\ldots,x_{n}\right)$
$\displaystyle=\underbrace{\left(s_{\mu}s_{\nu}\right)}_{\begin{subarray}{c}=\sum\limits_{\lambda\in\operatorname*{Par}}c_{\mu,\nu}^{\lambda}s_{\lambda}\\\
\text{(by
(\ref{eq.lrcoeff.def}))}\end{subarray}}\left(x_{1},x_{2},\ldots,x_{n}\right)=\sum\limits_{\lambda\in\operatorname*{Par}}c_{\mu,\nu}^{\lambda}s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)$
$\displaystyle=\underbrace{\sum\limits_{\begin{subarray}{c}\lambda\in\operatorname*{Par};\\\
\lambda\text{ has length }\leq
n\end{subarray}}}_{\begin{subarray}{c}=\sum\limits_{\lambda\in\operatorname*{Par}\left[n\right]}\\\
\text{(by the definition of
}\operatorname*{Par}\left[n\right]\text{)}\end{subarray}}c_{\mu,\nu}^{\lambda}s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)+\sum\limits_{\begin{subarray}{c}\lambda\in\operatorname*{Par};\\\
\lambda\text{ has length
}>n\end{subarray}}c_{\mu,\nu}^{\lambda}\underbrace{s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)}_{\begin{subarray}{c}=0\\\
\text{(by (\ref{pf.lem.alt.lrr.=0}))}\end{subarray}}$
$\displaystyle=\sum\limits_{\lambda\in\operatorname*{Par}\left[n\right]}c_{\mu,\nu}^{\lambda}\underbrace{s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)}_{\begin{subarray}{c}=\overline{s}_{\lambda}\\\
\text{(by Lemma
\ref{lem.alt.sbar})}\end{subarray}}+\underbrace{\sum\limits_{\begin{subarray}{c}\lambda\in\operatorname*{Par};\\\
\lambda\text{ has length
}>n\end{subarray}}c_{\mu,\nu}^{\lambda}0}_{=0}=\sum\limits_{\lambda\in\operatorname*{Par}\left[n\right]}c_{\mu,\nu}^{\lambda}\overline{s}_{\lambda}.$

This proves Lemma 4.20.

######  Lemma 4.22.

The family
$\left(\overline{s}_{\lambda}\right)_{\lambda\in\left\\{\text{snakes}\right\\}}$
of elements of $\mathcal{L}$ is $\mathbf{k}$-linearly independent.

######  Proof 4.23 (Proof of Lemma 4.22.).

Let us define a _strict snake_ to be an $n$-tuple $\alpha\in\mathbb{Z}^{n}$ of
integers satisfying $\alpha_{1}>\alpha_{2}>\cdots>\alpha_{n}$. It is easy to
see that the map

$\displaystyle\left\\{\text{snakes}\right\\}$
$\displaystyle\rightarrow\left\\{\text{strict snakes}\right\\},$
$\displaystyle\lambda$ $\displaystyle\mapsto\lambda+\rho$ (26)

is a bijection.

It is also easy to see that if $\alpha$ and $\beta$ are two strict snakes,
then

$\left(\text{the coefficient of }x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots
x_{n}^{\beta_{n}}\text{ in }a_{\alpha}\right)=\delta_{\alpha,\beta},$ (27)

where $\delta_{\alpha,\beta}$ is the Kronecker delta of $\alpha$ and $\beta$
(that is, the integer $\begin{cases}1,&\text{if }\alpha=\beta;\\\ 0,&\text{if
}\alpha\neq\beta\end{cases}$ ).

Now, assume that
$\left(u_{\lambda}\right)_{\lambda\in\left\\{\text{snakes}\right\\}}\in\mathbf{k}^{\left\\{\text{snakes}\right\\}}$
be a family of scalars with the property that $\left(\text{all but finitely
many snakes }\lambda\text{ satisfy }u_{\lambda}=0\right)$ and

$\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}\overline{s}_{\lambda}=0.$
(28)

We shall show that $u_{\lambda}=0$ for all snakes $\lambda$.

Indeed, fix a snake $\mu$. Then, $\mu+\rho$ is a strict snake (since the map
(26) is a bijection). Let us denote this strict snake by $\beta$. Thus,
$\beta=\mu+\rho$.

If $\lambda$ is any snake, then $\lambda+\rho$ is a strict snake (since the
map (26) is a bijection), and thus satisfies

$\displaystyle\left(\text{the coefficient of
}x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{n}^{\beta_{n}}\text{ in
}a_{\lambda+\rho}\right)$ $\displaystyle=\delta_{\lambda+\rho,\beta}\ \ \ \ \
\ \ \ \ \ \left(\text{by (\ref{pf.lem.alt.linind.coeff-kron}), applied to
}\alpha=\lambda+\rho\right)$ $\displaystyle=\delta_{\lambda+\rho,\mu+\rho}\ \
\ \ \ \ \ \ \ \ \left(\text{since }\beta=\mu+\rho\right)$
$\displaystyle=\delta_{\lambda,\mu}$ (29)

(since $\lambda+\rho=\mu+\rho$ holds if and only if $\lambda=\mu$ holds).

From (28), we obtain

$0=\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}\underbrace{\overline{s}_{\lambda}}_{\begin{subarray}{c}=\dfrac{a_{\lambda+\rho}}{a_{\rho}}\\\
\text{(by the definition of
}\overline{s}_{\lambda}\text{)}\end{subarray}}=\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}\dfrac{a_{\lambda+\rho}}{a_{\rho}}=\dfrac{1}{a_{\rho}}\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}a_{\lambda+\rho}.$

Multiplying both sides of this equality by $a_{\rho}$, we obtain

$0=\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}a_{\lambda+\rho}.$

Hence,

$\displaystyle\left(\text{the coefficient of
}x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{n}^{\beta_{n}}\text{ in
}0\right)$ $\displaystyle=\left(\text{the coefficient of
}x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{n}^{\beta_{n}}\text{ in
}\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}a_{\lambda+\rho}\right)$
$\displaystyle=\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}\underbrace{\left(\text{the
coefficient of }x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots
x_{n}^{\beta_{n}}\text{ in
}a_{\lambda+\rho}\right)}_{\begin{subarray}{c}=\delta_{\lambda,\mu}\\\
\text{(by (\ref{pf.lem.alt.linind.5}))}\end{subarray}}$
$\displaystyle=\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}\delta_{\lambda,\mu}=u_{\mu},$

so that

$u_{\mu}=\left(\text{the coefficient of
}x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{n}^{\beta_{n}}\text{ in
}0\right)=0.$

Now, forget that we fixed $\mu$. We thus have proved that $u_{\mu}=0$ for all
snakes $\mu$. In other words, $u_{\lambda}=0$ for all snakes $\lambda$.

Forget that we fixed
$\left(u_{\lambda}\right)_{\lambda\in\left\\{\text{snakes}\right\\}}$. We thus
have shown that if
$\left(u_{\lambda}\right)_{\lambda\in\left\\{\text{snakes}\right\\}}\in\mathbf{k}^{\left\\{\text{snakes}\right\\}}$
is a family of scalars with the property that
$\left(\text{all but finitely many snakes }\lambda\text{ satisfy
}u_{\lambda}=0\right)$ and
$\sum\limits_{\lambda\in\left\\{\text{snakes}\right\\}}u_{\lambda}\overline{s}_{\lambda}=0$,
then $u_{\lambda}=0$ for all snakes $\lambda$. In other words, the family
$\left(\overline{s}_{\lambda}\right)_{\lambda\in\left\\{\text{snakes}\right\\}}$
of elements of $\mathcal{L}$ is $\mathbf{k}$-linearly independent. This proves
Lemma 4.22.

Lemma 4.22 is actually part of a stronger claim: The family
$\left(\overline{s}_{\lambda}\right)_{\lambda\in\left\\{\text{snakes}\right\\}}$
is a basis of the $\mathbf{k}$-module of symmetric Laurent polynomials in
$x_{1},x_{2},\ldots,x_{n}$. We shall not need this, however, so we omit the
proof777Just in case: It follows easily from Lemma 4.18 and [GriRei20, Remark
2.3.9(d)]..

Recall Definition 4.2 (d). Our next lemma connects the Laurent polynomials
$\overline{s}_{\lambda}$ and $\overline{s}_{\lambda^{\vee}}$ for every snake
$\lambda$; it is folklore (see [GriRei20, Exercise 2.9.15(d)] for an
equivalent version), but we shall prove it for the sake of completeness.

######  Lemma 4.24.

Let $\lambda$ be a snake. Then,

$\overline{s}_{\lambda^{\vee}}=\overline{s}_{\lambda}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right).$

Here, of course,
$\overline{s}_{\lambda}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)$
means the result of substituting $x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}$ for
$x_{1},x_{2},\ldots,x_{n}$ in the Laurent polynomial
$\overline{s}_{\lambda}\in\mathcal{L}$.

######  Proof 4.25 (Proof of Lemma 4.24.).

Let $w_{0}\in\mathfrak{S}_{n}$ be the permutation of
$\left\\{1,2,\ldots,n\right\\}$ that sends each
$i\in\left\\{1,2,\ldots,n\right\\}$ to $n+1-i$. The map
$\mathfrak{S}_{n}\rightarrow\mathfrak{S}_{n},\ w\mapsto w\circ w_{0}$ is a
bijection (since $\mathfrak{S}_{n}$ is a group).

For each $i\in\left\\{1,2,\ldots,n\right\\}$, we have

$\left(\lambda+\rho\right)_{i}=\lambda_{i}+\underbrace{\rho_{i}}_{\begin{subarray}{c}=n-i\\\
\text{(by (\ref{eq.snakes.f.rhoi=}))}\end{subarray}}=\lambda_{i}+n-i.$ (30)

Proposition 4.4 (b) shows that $\lambda^{\vee}$ is a snake. Thus, using
Proposition 4.4 (a), we conclude that $\lambda^{\vee}+\left(1-n\right)$ is a
snake. Let us denote this snake by $\mu$. Thus,
$\mu=\lambda^{\vee}+\left(1-n\right)$. Hence,
$\mu+\rho=\left(\lambda^{\vee}+\left(1-n\right)\right)+\rho=\left(\lambda^{\vee}+\rho\right)+\left(1-n\right)$
(this follows from Proposition 4.4 (c), applied to $\lambda^{\vee}$, $\rho$
and $1-n$ instead of $\lambda$, $\mu$ and $d$). Therefore,

$a_{\mu+\rho}=a_{\left(\lambda^{\vee}+\rho\right)+\left(1-n\right)}=x_{\Pi}^{1-n}a_{\lambda^{\vee}+\rho}$
(31)

(by Lemma 4.11, applied to $\lambda^{\vee}+\rho$ and $1-n$ instead of
$\lambda$ and $d$).

The definition of $\lambda^{\vee}$ yields
$\lambda^{\vee}=\left(-\lambda_{n},-\lambda_{n-1},\ldots,-\lambda_{1}\right)$.
Hence, for each $i\in\left\\{1,2,\ldots,n\right\\}$, we have

$\left(\lambda^{\vee}\right)_{i}=-\lambda_{n+1-i}.$ (32)

Thus, for each $i\in\left\\{1,2,\ldots,n\right\\}$, we have

$\displaystyle\left(\mu+\rho\right)_{i}$
$\displaystyle=\underbrace{\mu_{i}}_{\begin{subarray}{c}=\left(\lambda^{\vee}+\left(1-n\right)\right)_{i}\\\
\text{(since
}\mu=\lambda^{\vee}+\left(1-n\right)\text{)}\end{subarray}}+\underbrace{\rho_{i}}_{\begin{subarray}{c}=n-i\\\
\text{(by
(\ref{eq.snakes.f.rhoi=}))}\end{subarray}}=\underbrace{\left(\lambda^{\vee}+\left(1-n\right)\right)_{i}}_{\begin{subarray}{c}=\left(\lambda^{\vee}\right)_{i}+\left(1-n\right)\\\
\text{(by the definition of
}\lambda^{\vee}+\left(1-n\right)\text{)}\end{subarray}}+n-i$
$\displaystyle=\underbrace{\left(\lambda^{\vee}\right)_{i}}_{\begin{subarray}{c}=-\lambda_{n+1-i}\\\
\text{(by
(\ref{pf.lem.alt.inverses.check}))}\end{subarray}}+\underbrace{\left(1-n\right)+n-i}_{=1-i}$
$\displaystyle=-\lambda_{n+1-i}+1-i.$ (33)

Hence, the definition of $a_{\mu+\rho}$ yields

$\displaystyle a_{\mu+\rho}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\underbrace{x_{w\left(1\right)}^{\left(\mu+\rho\right)_{1}}x_{w\left(2\right)}^{\left(\mu+\rho\right)_{2}}\cdots
x_{w\left(n\right)}^{\left(\mu+\rho\right)_{n}}}_{=\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(i\right)}^{\left(\mu+\rho\right)_{i}}}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}\underbrace{x_{w\left(i\right)}^{\left(\mu+\rho\right)_{i}}}_{\begin{subarray}{c}=x_{w\left(i\right)}^{-\lambda_{n+1-i}+1-i}\\\
\text{(since (\ref{pf.lem.alt.inverses.chec2}) yields
}\left(\mu+\rho\right)_{i}=-\lambda_{n+1-i}+1-i\text{)}\end{subarray}}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(i\right)}^{-\lambda_{n+1-i}+1-i}.$
(34)

The definition of $a_{\lambda+\rho}$ yields

$\displaystyle a_{\lambda+\rho}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\underbrace{x_{w\left(1\right)}^{\left(\lambda+\rho\right)_{1}}x_{w\left(2\right)}^{\left(\lambda+\rho\right)_{2}}\cdots
x_{w\left(n\right)}^{\left(\lambda+\rho\right)_{n}}}_{=\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(i\right)}^{\left(\lambda+\rho\right)_{i}}}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}\underbrace{x_{w\left(i\right)}^{\left(\lambda+\rho\right)_{i}}}_{\begin{subarray}{c}=x_{w\left(i\right)}^{\lambda_{i}+n-i}\\\
\text{(since (\ref{pf.lem.alt.inverses.rho2}) yields
}\left(\lambda+\rho\right)_{i}=\lambda_{i}+n-i\text{)}\end{subarray}}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(i\right)}^{\lambda_{i}+n-i}.$

Substituting $x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}$ for
$x_{1},x_{2},\ldots,x_{n}$ on both sides of this equality, we obtain

$\displaystyle
a_{\lambda+\rho}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}\underbrace{\left(x_{w\left(i\right)}^{-1}\right)^{\lambda_{i}+n-i}}_{=x_{w\left(i\right)}^{-\left(\lambda_{i}+n-i\right)}}=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(i\right)}^{-\left(\lambda_{i}+n-i\right)}$
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\underbrace{\left(-1\right)^{w\circ
w_{0}}}_{=\left(-1\right)^{w}\left(-1\right)^{w_{0}}}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}\underbrace{x_{\left(w\circ
w_{0}\right)\left(i\right)}^{-\left(\lambda_{i}+n-i\right)}}_{\begin{subarray}{c}=x_{w\left(n+1-i\right)}^{-\lambda_{i}-n+i}\\\
\text{(since }-\left(\lambda_{i}+n-i\right)=-\lambda_{i}-n+i\\\ \text{and
}\left(w\circ
w_{0}\right)\left(i\right)=w\left(w_{0}\left(i\right)\right)=w\left(n+1-i\right)\\\
\text{(because }w_{0}\left(i\right)=n+1-i\text{))}\end{subarray}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\begin{array}[c]{c}\text{here, we have
substituted }w\circ w_{0}\text{ for }w\text{ in the sum,}\\\ \text{since the
map }\mathfrak{S}_{n}\rightarrow\mathfrak{S}_{n},\ w\mapsto w\circ w_{0}\text{
is a bijection}\end{array}\right)$ (37)
$\displaystyle=\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\left(-1\right)^{w_{0}}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(n+1-i\right)}^{-\lambda_{i}-n+i}$
$\displaystyle=\left(-1\right)^{w_{0}}\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\underbrace{\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(n+1-i\right)}^{-\lambda_{i}-n+i}}_{\begin{subarray}{c}=\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(n+1-\left(n+1-i\right)\right)}^{-\lambda_{n+1-i}-n+\left(n+1-i\right)}\\\
\text{(here, we have substituted }n+1-i\text{ for }i\\\ \text{in the
product)}\end{subarray}}$
$\displaystyle=\left(-1\right)^{w_{0}}\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}\underbrace{x_{w\left(n+1-\left(n+1-i\right)\right)}^{-\lambda_{n+1-i}-n+\left(n+1-i\right)}}_{\begin{subarray}{c}=x_{w\left(i\right)}^{-\lambda_{n+1-i}+1-i}\\\
\text{(since }-\lambda_{n+1-i}-n+\left(n+1-i\right)=-\lambda_{n+1-i}+1-i\\\
\text{and }n+1-\left(n+1-i\right)=i\text{)}\end{subarray}}$
$\displaystyle=\left(-1\right)^{w_{0}}\underbrace{\sum\limits_{w\in\mathfrak{S}_{n}}\left(-1\right)^{w}\prod\limits_{i\in\left\\{1,2,\ldots,n\right\\}}x_{w\left(i\right)}^{-\lambda_{n+1-i}+1-i}}_{\begin{subarray}{c}=a_{\mu+\rho}\\\
\text{(by
(\ref{pf.lem.alt.inverses.ampr}))}\end{subarray}}=\left(-1\right)^{w_{0}}\underbrace{a_{\mu+\rho}}_{\begin{subarray}{c}=x_{\Pi}^{1-n}a_{\lambda^{\vee}+\rho}\\\
\text{(by (\ref{pf.lem.alt.inverses.0}))}\end{subarray}}$
$\displaystyle=\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}a_{\lambda^{\vee}+\rho}.$
(38)

On the other hand, let us denote the snake
$\left(\underbrace{0,0,\ldots,0}_{n\text{ times}}\right)\in\mathbb{Z}^{n}$ by
$\varnothing$; note that it satisfies
$\varnothing^{\vee}=\left(\underbrace{-0,-0,\ldots,-0}_{n\text{
times}}\right)=\left(\underbrace{0,0,\ldots,0}_{n\text{
times}}\right)=\varnothing$. We have proved (38) for any snake $\lambda$;
thus, we can apply (38) to $\varnothing$ instead of $\lambda$. We thus obtain

$a_{\varnothing+\rho}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)=\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}a_{\varnothing^{\vee}+\rho}.$

In view of $\varnothing+\rho=\rho$ and
$\underbrace{\varnothing^{\vee}}_{=\varnothing}+\rho=\varnothing+\rho=\rho$,
we can rewrite this as

$a_{\rho}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)=\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}a_{\rho}.$
(39)

The definition of $\overline{s}_{\lambda}$ yields
$\overline{s}_{\lambda}=\dfrac{a_{\lambda+\rho}}{a_{\rho}}$. Hence,
$a_{\lambda+\rho}=\overline{s}_{\lambda}a_{\rho}$. Substituting
$x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}$ for $x_{1},x_{2},\ldots,x_{n}$ on
both sides of this equality, we obtain

$\displaystyle
a_{\lambda+\rho}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)$
$\displaystyle=\left(\overline{s}_{\lambda}a_{\rho}\right)\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)$
$\displaystyle=\overline{s}_{\lambda}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)\cdot\underbrace{a_{\rho}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)}_{\begin{subarray}{c}=\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}a_{\rho}\\\
\text{(by (\ref{pf.lem.alt.inverses.a2}))}\end{subarray}}$
$\displaystyle=\overline{s}_{\lambda}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)\cdot\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}a_{\rho}.$

Comparing this with (38), we find

$\overline{s}_{\lambda}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)\cdot\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}a_{\rho}=\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}a_{\lambda^{\vee}+\rho}.$
(40)

The element $\left(-1\right)^{w_{0}}x_{\Pi}^{1-n}$ of $\mathcal{L}$ is
invertible (since $x_{\Pi}$ is invertible), and thus we can cancel it from the
equality (40). As a result, we obtain

$\overline{s}_{\lambda}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)\cdot
a_{\rho}=a_{\lambda^{\vee}+\rho}.$ (41)

But the definition of $\overline{s}_{\lambda^{\vee}}$ yields

$\overline{s}_{\lambda^{\vee}}=\dfrac{a_{\lambda^{\vee}+\rho}}{a_{\rho}}=\overline{s}_{\lambda}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right)$

(by (41)). This proves Lemma 4.24.

###  4.2 $h_{k}^{+}$, $h_{k}^{-}$ and the Pieri rule

######  Definition 4.26.

Let $k\in\mathbb{Z}$. Then, we define two Laurent polynomials
$h_{k}^{+}\in\mathcal{L}$ and $h_{k}^{-}\in\mathcal{L}$ by

$\displaystyle h_{k}^{+}$
$\displaystyle=h_{k}\left(x_{1},x_{2},\ldots,x_{n}\right)\ \ \ \ \ \ \ \ \ \
\text{and}$ $\displaystyle h_{k}^{-}$
$\displaystyle=h_{k}\left(x_{1}^{-1},x_{2}^{-1},\ldots,x_{n}^{-1}\right).$

Note that if $k\in\mathbb{Z}$ is negative, then
$h_{k}^{+}=\underbrace{h_{k}}_{=0}\left(x_{1},x_{2},\ldots,x_{n}\right)=0$ and
$h_{k}^{-}=0$ (similarly).

We begin by describing $h_{k}^{+}$ as a Schur Laurent polynomial:

######  Lemma 4.27.

Let $k\in\mathbb{N}$. Then, the partition $\left(k\right)$ is a nonnegative
snake (when regarded as the $n$-tuple $\left(k,0,0,\ldots,0\right)$), and
satisfies

$\overline{s}_{\left(k\right)}=h_{k}^{+}.$

######  Proof 4.28 (Proof of Lemma 4.27.).

The partition $\left(k\right)$ has length $\leq n$ (since it has length $\leq
1$, but we have $n\geq 1$). Thus, it is a nonnegative snake (since every
partition having length $\leq n$ is a nonnegative snake) and belongs to
$\operatorname*{Par}\left[n\right]$. Hence, Lemma 4.16 (applied to
$\lambda=\left(k\right)$) yields
$\overline{s}_{\left(k\right)}=s_{\left(k\right)}\left(x_{1},x_{2},\ldots,x_{n}\right)=h_{k}\left(x_{1},x_{2},\ldots,x_{n}\right)$
(since $s_{\left(k\right)}=h_{k}$). Comparing this with
$h_{k}^{+}=h_{k}\left(x_{1},x_{2},\ldots,x_{n}\right)$, we obtain
$\overline{s}_{\left(k\right)}=h_{k}^{+}$. This proves Lemma 4.27.

Next, we need to know what happens when a Schur Laurent polynomial
$\overline{s}_{\lambda}$ is multiplied by some $h_{k}^{+}$. The answer to this
question is classically given by the first Pieri rule; we shall state it in a
form that will be most convenient to us. To do so, we introduce some more
notation:

######  Definition 4.29.

Let $\lambda\in\mathbb{Z}^{n}$. Then, we define the _size_
$\left|\lambda\right|$ of $\lambda$ to be the integer
$\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n}$.

######  Definition 4.30.

Let $\lambda,\mu\in\mathbb{Z}^{n}$. Then, we write that
$\mu\rightharpoonup\lambda$ if and only if we have

$\mu_{1}\geq\lambda_{1}\geq\mu_{2}\geq\lambda_{2}\geq\cdots\geq\mu_{n}\geq\lambda_{n}.$
(42)

In other words, we write that $\mu\rightharpoonup\lambda$ if and only if we
have

$\displaystyle\left(\mu_{i}\geq\lambda_{i}\text{ for each
}i\in\left\\{1,2,\ldots,n\right\\}\right)\ \ \ \ \ \ \ \ \ \ \text{and}$
$\displaystyle\left(\lambda_{i}\geq\mu_{i+1}\text{ for each
}i\in\left\\{1,2,\ldots,n-1\right\\}\right).$

The following properties of the sizes of $n$-tuples are obvious:

######  Proposition 4.31.

  1. (a)

If $\lambda,\mu\in\mathbb{Z}^{n}$, then
$\left|\lambda+\mu\right|=\left|\lambda\right|+\left|\mu\right|$.

  2. (b)

If $\lambda\in\mathbb{Z}^{n}$ and $d\in\mathbb{Z}$, then
$\left|\lambda+d\right|=\left|\lambda\right|+nd$.

  3. (c)

If $\lambda\in\mathbb{Z}^{n}$, then
$\left|\lambda^{\vee}\right|=-\left|\lambda\right|$.

The relation $\rightharpoonup$ defined in Definition 4.30 has the following
simple properties:

######  Proposition 4.32.

Let $\lambda,\mu\in\mathbb{Z}^{n}$.

  1. (a)

If $\mu\rightharpoonup\lambda$, then both $\lambda$ and $\mu$ are snakes.

  2. (b)

We have $\mu\rightharpoonup\lambda$ if and only if
$\lambda^{\vee}\rightharpoonup\mu^{\vee}$.

  3. (c)

Let $d\in\mathbb{Z}$. Then, we have $\mu\rightharpoonup\lambda$ if and only if
$\mu+d\rightharpoonup\lambda+d$.

######  Proof 4.33 (Proof of Proposition 4.32.).

(a) Assume that $\mu\rightharpoonup\lambda$. Thus, the chain of inequalities
(42) holds (by Definition 4.30). But this chain of inequalities implies both
$\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{n}$ and
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$. Thus, $\mu$ and
$\lambda$ are snakes. This proves Proposition 4.32 (a).

(b) The definition of $\mu^{\vee}$ yields
$\mu^{\vee}=\left(-\mu_{n},-\mu_{n-1},\ldots,-\mu_{1}\right)$. Similarly,
$\lambda^{\vee}=\left(-\lambda_{n},-\lambda_{n-1},\ldots,-\lambda_{1}\right)$.
Hence, we have $\lambda^{\vee}\rightharpoonup\mu^{\vee}$ if and only if we
have

$-\lambda_{n}\geq-\mu_{n}\geq-\lambda_{n-1}\geq-\mu_{n-1}\geq\cdots\geq-\lambda_{1}\geq-\mu_{1}$

(because of Definition 4.30).

Thus, we have the following chain of equivalences:

$\displaystyle\left(\lambda^{\vee}\rightharpoonup\mu^{\vee}\right)\ $
$\displaystyle\Longleftrightarrow\
\left(-\lambda_{n}\geq-\mu_{n}\geq-\lambda_{n-1}\geq-\mu_{n-1}\geq\cdots\geq-\lambda_{1}\geq-\mu_{1}\right)$
$\displaystyle\Longleftrightarrow\
\left(\lambda_{n}\leq\mu_{n}\leq\lambda_{n-1}\leq\mu_{n-1}\leq\cdots\leq\lambda_{1}\leq\mu_{1}\right)$
$\displaystyle\Longleftrightarrow\
\left(\mu_{1}\geq\lambda_{1}\geq\mu_{2}\geq\lambda_{2}\geq\cdots\geq\mu_{n}\geq\lambda_{n}\right)$
$\displaystyle\Longleftrightarrow\ \left(\mu\rightharpoonup\lambda\right)\ \ \
\ \ \ \ \ \ \ \left(\text{by Definition \ref{def.horstr}}\right).$

In other words, we have $\mu\rightharpoonup\lambda$ if and only if
$\lambda^{\vee}\rightharpoonup\mu^{\vee}$. This proves Proposition 4.32 (b).

(c) This follows easily from Definition 4.30.

We can now state the Pieri rule in the form we need:

######  Proposition 4.34.

Let $\lambda$ be a snake. Let $k\in\mathbb{Z}$. Then,

$h_{k}^{+}\cdot\overline{s}_{\lambda}=\sum\limits_{\begin{subarray}{c}\mu\text{
is a snake;}\\\ \mu\rightharpoonup\lambda;\
\left|\mu\right|-\left|\lambda\right|=k\end{subarray}}\overline{s}_{\mu}.$
(43)

This can be proven directly using alternants; but let us give a proof based on
known theory:

######  Proof 4.35 (Proof of Proposition 4.34.).

We follow the same right-shift strategy as we did in our proof of Lemma 4.13.
Thus, our proof shall consist of two steps:

> Step 1: We will prove Proposition 4.34 in the particular case when $\lambda$
> is nonnegative.

> Step 2: We will use Lemma 4.18 to derive the general case of Proposition
> 4.34 from this particular case.

Here are the details of the two steps:

Step 1: Let us prove that Proposition 4.34 holds in the particular case when
$\lambda$ is nonnegative.

Indeed, let us assume that $\lambda$ is nonnegative. We must prove the
equality (43).

If $k<0$, then both sides of this equality are $0$ 888Proof. Assume that
$k<0$. We must show that both sides of (43) are $0$. Indeed, from $k<0$, we
obtain $h_{k}=0$, thus
$h_{k}^{+}=\underbrace{h_{k}}_{=0}\left(x_{1},x_{2},\ldots,x_{n}\right)=0$.
Hence, $\underbrace{h_{k}^{+}}_{=0}\cdot\overline{s}_{\lambda}=0$. In other
words, the left hand side of (43) is $0$. It remains to show that the right
hand side of (43) is $0$. This will follow if we can show that the sum on this
right hand side is empty, i.e., that there exists no snake $\mu$ such that
$\mu\rightharpoonup\lambda$ and $\left|\mu\right|-\left|\lambda\right|=k$. So
let us show this. Let $\mu$ be a snake such that $\mu\rightharpoonup\lambda$
and $\left|\mu\right|-\left|\lambda\right|=k$. We shall derive a
contradiction. From $\mu\rightharpoonup\lambda$, we obtain
$\mu_{1}\geq\lambda_{1}\geq\mu_{2}\geq\lambda_{2}\geq\cdots\geq\mu_{n}\geq\lambda_{n}$
(by the definition of “$\mu\rightharpoonup\lambda$”). Hence,
$\mu_{i}\geq\lambda_{i}$ for each $i\in\left\\{1,2,\ldots,n\right\\}$. Thus,
$\sum\limits_{i=1}^{n}\underbrace{\mu_{i}}_{\geq\lambda_{i}}\geq\sum\limits_{i=1}^{n}\lambda_{i}$.
In other words, $\left|\mu\right|\geq\left|\lambda\right|$ (since
$\left|\mu\right|=\mu_{1}+\mu_{2}+\cdots+\mu_{n}=\sum\limits_{i=1}^{n}\mu_{i}$
and similarly $\left|\lambda\right|=\sum\limits_{i=1}^{n}\lambda_{i}$). Hence,
$\left|\mu\right|-\left|\lambda\right|\geq 0$. But this contradicts
$\left|\mu\right|-\left|\lambda\right|=k<0$. Forget that we fixed $\mu$. We
thus have found a contradiction whenever $\mu$ is a snake such that
$\mu\rightharpoonup\lambda$ and $\left|\mu\right|-\left|\lambda\right|=k$.
Hence, there exists no such snake $\mu$. In other words, the sum on the right
hand side of (43) is empty. Hence, the right hand side of (43) is $0$. This
completes our proof.. Thus, the equality (43) holds if $k<0$. Therefore, for
the rest of Step 1, we WLOG assume that $k\geq 0$. In other words,
$k\in\mathbb{N}$.

Note that $\lambda$ is a partition of length $\leq n$ (since $\lambda$ is a
nonnegative snake). In other words,
$\lambda\in\operatorname*{Par}\left[n\right]$.

We will use some standard notations concerning partitions. Specifically:

  * •

If $\alpha=\left(\alpha_{1},\alpha_{2},\alpha_{3},\ldots\right)$ and
$\beta=\left(\beta_{1},\beta_{2},\beta_{3},\ldots\right)$ are two partitions,
then we will write $\alpha\subseteq\beta$ if and only if each
$i\in\left\\{1,2,3,\ldots\right\\}$ satisfies $\alpha_{i}\leq\beta_{i}$. (This
is precisely the definition of $\alpha\subseteq\beta$ given in [GriRei20,
Definition 2.3.1].)

  * •

If $\alpha=\left(\alpha_{1},\alpha_{2},\alpha_{3},\ldots\right)$ and
$\beta=\left(\beta_{1},\beta_{2},\beta_{3},\ldots\right)$ are two partitions,
then we say that $\alpha/\beta$ _is a horizontal strip_ if they satisfy

$\beta\subseteq\alpha\text{ and }\left(\text{every
}i\in\left\\{1,2,3,\ldots\right\\}\text{ satisfies
}\beta_{i}\geq\alpha_{i+1}\right).$

(This is not literally how a “horizontal strip” is defined in [GriRei20], but
it is equivalent to that definition; the equivalence follows from [GriRei20,
Exercise 2.7.5(a)].)

  * •

If $\alpha$ and $\beta$ are two partitions, and if $k\in\mathbb{N}$, then we
say that $\alpha/\beta$ _is a horizontal_ $k$_-strip_ if $\alpha/\beta$ is a
horizontal strip and we have $\left|\alpha\right|-\left|\beta\right|=k$. (This
is equivalent to the definition of a “horizontal $k$-strip” in [GriRei20,
§2.7]).

We note the following claim:

> Claim 1: We have
>
> $\displaystyle\left\\{\text{partitions
> }\mu\in\operatorname*{Par}\left[n\right]\text{ such that }\mu/\lambda\text{
> is a horizontal }k\text{-strip}\right\\}$
> $\displaystyle=\left\\{\text{snakes }\mu\text{ such that
> }\mu\rightharpoonup\lambda\text{ and}\
> \left|\mu\right|-\left|\lambda\right|=k\right\\}.$

[Proof of Claim 1: This is an exercise in unraveling definitions and recalling