$\displaystyle=\sum_{\sigma\in\operatorname{Sh}_{\ell,m}}v_{\sigma\left(1\right)}v_{\sigma\left(2\right)}\cdots
v_{\sigma\left(\ell+m\right)}$ $\displaystyle\qquad\qquad\text{ for all
}\ell,m\in{\mathbb{N}}\text{ and }v_{1},v_{2},\ldots,v_{\ell+m}\in V.$
414141Again, this is well-defined by the $\ell+m$-multilinearity of the right
hand side.

Consider also the comultiplication $\epsilon$ of the Hopf algebra
$T\left(V\right)$.

Then, the $\mathbf{k}$-module $T\left(V\right)$, endowed with the
multiplication $\underline{\shuffle}$, the unit $1_{T\left(V\right)}\in
V^{\otimes 0}\subset T\left(V\right)$, the comultiplication
$\Delta_{\shuffle}$ and the counit $\epsilon$, becomes a commutative Hopf
algebra. This Hopf algebra is called the shuffle algebra of $V$, and denoted
by $\operatorname{Sh}\left(V\right)$. The antipode of the Hopf algebra
$\operatorname{Sh}\left(V\right)$ is precisely the antipode $S$ of
$T\left(V\right)$.

######  Exercise 1.74.

Prove Proposition 1.73.

[Hint: When $V$ is a finite free $\mathbf{k}$-module, Proposition 1.73 follows
from Example 1.69. The trick is to derive the general case from this specific
one. Every $\mathbf{k}$-linear map $f:W\to V$ between two $\mathbf{k}$-modules
$W$ and $V$ induces a map $T\left(f\right):T\left(W\right)\to T\left(V\right)$
which preserves $\Delta_{\shuffle}$, $\underline{\shuffle}$,
$1_{T\left(W\right)}$, $\epsilon$ and $S$ (in the appropriate meanings – e.g.,
preserving $\Delta_{\shuffle}$ means $\Delta_{\shuffle}\circ
T\left(f\right)=\left(T\left(f\right)\otimes
T\left(f\right)\right)\circ\Delta_{\shuffle}$). Show that each of the
equalities that need to be proven in order to verify Proposition 1.73 can be
“transported” along such a map $T\left(f\right)$ from a $T\left(W\right)$ for
a suitably chosen finite free $\mathbf{k}$-module $W$.]

It is also possible to prove Proposition 1.73 “by foot”, as long as one is
ready to make combinatorial arguments about cutting shuffles.

######  Remark 1.75.

  * (a)

Let $V$ be a finite free $\mathbf{k}$-module. The Hopf algebra
$T\left(V\right)^{o}$ (studied in Example 1.69) is naturally isomorphic to the
shuffle algebra $\operatorname{Sh}\left(V^{\ast}\right)$ (defined as in
Proposition 1.73 but for $V^{\ast}$ instead of $V$) as Hopf algebras, by the
obvious isomorphism (namely, the direct sum of the isomorphisms
$\left(V^{\otimes n}\right)^{\ast}\to\left(V^{\ast}\right)^{\otimes n}$ over
all $n\in{\mathbb{N}}$). 424242This can be verified by comparing (1.20) with
the definition of $\Delta_{\shuffle}$, and comparing (1.23) with the
definition of $\underline{\shuffle}$.

  * (b)

The same statement applies to the case when $V$ is a graded
$\mathbf{k}$-module of finite type satisfying $V_{0}=0$ rather than a finite
free $\mathbf{k}$-module, provided that $V^{\ast}$ and $\left(V^{\otimes
n}\right)^{\ast}$ are replaced by $V^{o}$ and $\left(V^{\otimes
n}\right)^{o}$.

We shall return to shuffle algebras in Section 6.3, where we will show that
under certain conditions (${\mathbb{Q}}$ being a subring of $\mathbf{k}$, and
$V$ being a free $\mathbf{k}$-module) the algebra structure on a shuffle
algebra $\operatorname{Sh}(V)$ is a polynomial algebra in an appropriately
chosen set of generators434343This says nothing about the coalgebra structure
on $\operatorname{Sh}(V)$ – which is much more complicated in these
generators..

##  2\. Review of symmetric functions $\Lambda$ as Hopf algebra

Here we review the ring of symmetric functions, borrowing heavily from
standard treatments, such as Macdonald [114, Chap. I], Sagan [148, Chap. 4],
and Stanley [164, Chap. 7], but emphasizing the Hopf structure early on.

###  2.1. Definition of $\Lambda$

As before, $\mathbf{k}$ here is a commutative ring (hence could be a field or
the integers ${\mathbb{Z}}$; these are the usual choices). Given an infinite
variable set ${\mathbf{x}}=(x_{1},x_{2},\ldots)$, a monomial
${\mathbf{x}}^{\alpha}:=x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots$ is indexed
by an element $\alpha=(\alpha_{1},\alpha_{2},\ldots)$ in
${\mathbb{N}}^{\infty}$ having finite support444444The support of a sequence
$\alpha=\left(\alpha_{1},\alpha_{2},\alpha_{3},\ldots\right)\in{\mathbb{N}}^{\infty}$
is defined to be the set of all positive integers $i$ for which
$\alpha_{i}\neq 0$.; such $\alpha$ are called weak compositions. The nonzero
ones among the integers $\alpha_{1},\alpha_{2},\ldots$ are called the parts of
the weak composition $\alpha$. We will consider the ring $R({\mathbf{x}})$ of
formal power series
$f({\mathbf{x}})=\sum_{\alpha}c_{\alpha}{\mathbf{x}}^{\alpha}$ with
$c_{\alpha}$ in $\mathbf{k}$ of bounded degree, that is, where there exists
some bound $d=d(f)$ for which
$\deg({\mathbf{x}}^{\alpha}):=\sum_{i}\alpha_{i}>d$ implies $c_{\alpha}=0$. It
is easy to see that the product of two such power series is well-defined, and
also has bounded degree.

The symmetric group $\mathfrak{S}_{n}$ permuting the first $n$ variables
$x_{1},\ldots,x_{n}$ acts as a group of automorphisms on $R({\mathbf{x}})$, as
does the union $\mathfrak{S}_{(\infty)}=\bigcup_{n\geq 0}\mathfrak{S}_{n}$ of
the infinite ascending chain
$\mathfrak{S}_{0}\subset\mathfrak{S}_{1}\subset\mathfrak{S}_{2}\subset\cdots$
of symmetric groups454545This ascending chain is constructed as follows: For
every $n\in{\mathbb{N}}$, there is an injective group homomorphism
$\iota_{n}:\mathfrak{S}_{n}\to\mathfrak{S}_{n+1}$ which sends every
permutation $\sigma\in\mathfrak{S}_{n}$ to the permutation
$\iota_{n}\left(\sigma\right)=\tau\in\mathfrak{S}_{n}$ defined by
$\tau\left(i\right)=\begin{cases}\sigma\left(i\right),&\text{if }i\leq n;\\\
i,&\text{if }i=n+1\end{cases}\qquad\text{ for all
}i\in\left\\{1,2,\ldots,n+1\right\\}.$ These homomorphisms $\iota_{n}$ for all
$n$ form a chain
$\mathfrak{S}_{0}\overset{\iota_{0}}{\longrightarrow}\mathfrak{S}_{1}\overset{\iota_{1}}{\longrightarrow}\mathfrak{S}_{2}\overset{\iota_{2}}{\longrightarrow}\cdots$,
which is often regarded as a chain of inclusions.. This group
$\mathfrak{S}_{(\infty)}$ can also be described as the group of all
permutations of the set $\left\\{1,2,3,\ldots\right\\}$ which leave all but
finitely many elements invariant.

######  Definition 2.1.

The ring of symmetric functions in ${\mathbf{x}}$ with coefficients in
$\mathbf{k}$, denoted
$\Lambda=\Lambda_{\mathbf{k}}=\Lambda({\mathbf{x}})=\Lambda_{\mathbf{k}}({\mathbf{x}}),$
is the $\mathfrak{S}_{(\infty)}$-invariant subalgebra
$R({\mathbf{x}})^{\mathfrak{S}_{(\infty)}}$ of $R({\mathbf{x}})$:

$\Lambda:=\left\\{f=\sum_{\alpha}c_{\alpha}{\mathbf{x}}^{\alpha}\in
R({\mathbf{x}}):c_{\alpha}=c_{\beta}\text{ if }\alpha,\beta\text{ lie in the
same }\mathfrak{S}_{(\infty)}\text{-orbit}\right\\}.$

We refer to the elements of $\Lambda$ as symmetric functions (over
$\mathbf{k}$); however, despite this terminology, they are not functions in
the usual sense.464646Being power series, they can be evaluated at appropriate
families of variables. But this does not make them functions (no more than
polynomials are functions). The terminology “symmetric function” is thus not
well-chosen; but it is standard.

Note that $\Lambda$ is a graded $\mathbf{k}$-algebra, since
$\Lambda=\bigoplus_{n\geq 0}\Lambda_{n}$ where $\Lambda_{n}$ are the symmetric
functions $f=\sum_{\alpha}c_{\alpha}{\mathbf{x}}^{\alpha}$ which are
homogeneous of degree $n$, meaning $\deg({\mathbf{x}}^{\alpha})=n$ for all
$c_{\alpha}\neq 0$.

######  Exercise 2.2.

Let $f\in R\left({\mathbf{x}}\right)$. Let $A$ be a commutative
$\mathbf{k}$-algebra, and $a_{1},a_{2},\ldots,a_{k}$ be finitely many elements
of $A$. Show that substituting $a_{1},a_{2},\ldots,a_{k},0,0,0,\ldots$ for
$x_{1},x_{2},x_{3},\ldots$ in $f$ yields an infinite sum in which all but
finitely many addends are zero. Hence, this sum has a value in $A$, which is
commonly denoted by $f\left(a_{1},a_{2},\ldots,a_{k}\right)$.

######  Definition 2.3.

A partition
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell},0,0,\ldots)$ is a weak
composition whose entries weakly decrease:
$\lambda_{1}\geq\cdots\geq\lambda_{\ell}>0$. The (uniquely defined) $\ell$ is
said to be the length of the partition $\lambda$ and denoted by
$\ell\left(\lambda\right)$. One sometimes omits trailing zeroes from a
partition: e.g., one can write the partition $\left(3,1,0,0,0,\ldots\right)$
as $\left(3,1\right)$. We will often (but not always) write $\lambda_{i}$ for
the $i$-th entry of the partition $\lambda$ (for instance, $\lambda_{2}=3$ if
$\lambda=\left(5,3,1,1\right)$) and call it the $i$-th part of $\lambda$. The
sum
$\lambda_{1}+\lambda_{2}+\cdots+\lambda_{\ell}=\lambda_{1}+\lambda_{2}+\cdots$
(where $\ell=\ell\left(\lambda\right)$) of all parts of $\lambda$ is called
the size of $\lambda$ and denoted by $\left|\lambda\right|$; for a given
integer $n$, the partitions of size $n$ are referred to as the partitions of
$n$. The empty partition $()$ is denoted by $\varnothing$.

Every weak composition $\alpha$ lies in the $\mathfrak{S}_{(\infty)}$-orbit of
a unique partition
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell},0,0,\ldots)$ with
$\lambda_{1}\geq\cdots\geq\lambda_{\ell}>0$. For any partition $\lambda$,
define the monomial symmetric function

(2.1)
$m_{\lambda}:=\sum_{\alpha\in\mathfrak{S}_{(\infty)}\lambda}{\mathbf{x}}^{\alpha}.$

Letting $\lambda$ run through the set $\operatorname{Par}$ of all partitions,
this gives the monomial $\mathbf{k}$-basis $\\{m_{\lambda}\\}$ of $\Lambda$.
Letting $\lambda$ run only through the set $\operatorname{Par}_{n}$ of
partitions of $n$ gives the monomial $\mathbf{k}$-basis for $\Lambda_{n}$.

######  Example 2.4.

For $n=3$, one has

$\displaystyle m_{(3)}$ $\displaystyle=x_{1}^{3}+x_{2}^{3}+x_{3}^{3}+\cdots$
$\displaystyle m_{(2,1)}$
$\displaystyle=x_{1}^{2}x_{2}+x_{1}x_{2}^{2}+x_{1}^{2}x_{3}+x_{1}x_{3}^{2}+\cdots$
$\displaystyle m_{(1,1,1)}$
$\displaystyle=x_{1}x_{2}x_{3}+x_{1}x_{2}x_{4}+x_{1}x_{3}x_{4}+x_{2}x_{3}x_{4}+x_{1}x_{2}x_{5}+\cdots$

######  Remark 2.5.

We have defined the symmetric functions as the elements of
$R\left({\mathbf{x}}\right)$ invariant under the group
$\mathfrak{S}_{(\infty)}$. However, they also are the elements of
$R\left({\mathbf{x}}\right)$ invariant under the group $\mathfrak{S}_{\infty}$
of all permutations of the set $\left\\{1,2,3,\ldots\right\\}$. 474747Proof.
We need to show that
$\Lambda=R\left({\mathbf{x}}\right)^{\mathfrak{S}_{\infty}}$. Since
$\Lambda=\left\\{f=\sum_{\alpha}c_{\alpha}{\mathbf{x}}^{\alpha}\in
R\left({\mathbf{x}}\right):c_{\alpha}=c_{\beta}\text{ if }\alpha,\beta\text{
lie in the same }\mathfrak{S}_{(\infty)}\text{-orbit}\right\\}$ and
$R\left({\mathbf{x}}\right)^{\mathfrak{S}_{\infty}}=\left\\{f=\sum_{\alpha}c_{\alpha}{\mathbf{x}}^{\alpha}\in
R\left({\mathbf{x}}\right):c_{\alpha}=c_{\beta}\text{ if }\alpha,\beta\text{
lie in the same }\mathfrak{S}_{\infty}\text{-orbit}\right\\},$ this will
follow immediately if we can show that two weak compositions $\alpha$ and
$\beta$ lie in the same $\mathfrak{S}_{(\infty)}$-orbit if and only if they
lie in the same $\mathfrak{S}_{\infty}$-orbit. But this is straightforward to
check (in fact, two weak compositions $\alpha$ and $\beta$ lie in the same
orbit under either group if and only if they have the same multiset of nonzero
entries).

######  Remark 2.6.

It is sometimes convenient to work with finite variable sets
$x_{1},\ldots,x_{n}$, which one justifies as follows. Note that the algebra
homomorphism

$R({\mathbf{x}})\rightarrow
R(x_{1},\ldots,x_{n})=\mathbf{k}[x_{1},\ldots,x_{n}]$

which sends $x_{n+1},x_{n+2},\ldots$ to $0$ restricts to an algebra
homomorphism

$\Lambda_{\mathbf{k}}({\mathbf{x}})\rightarrow\Lambda_{\mathbf{k}}(x_{1},\ldots,x_{n})=\mathbf{k}[x_{1},\ldots,x_{n}]^{\mathfrak{S}_{n}}.$

Furthermore, this last homomorphism is a $\mathbf{k}$-linear isomorphism when
restricted to $\Lambda_{i}$ for $0\leq i\leq n$, since it sends the monomial
basis elements $m_{\lambda}({\mathbf{x}})$ to the monomial basis elements
$m_{\lambda}(x_{1},\ldots,x_{n})$. Thus when one proves identities in
$\Lambda_{\mathbf{k}}(x_{1},\ldots,x_{n})$ for all $n$, they are valid in
$\Lambda$, that is, $\Lambda$ is the inverse limit of the
$\Lambda(x_{1},\ldots,x_{n})$ in the category of graded
$\mathbf{k}$-algebras.484848Warning: The word “graded” here is crucial.
Indeed, $\Lambda$ is not the inverse limit of the
$\Lambda(x_{1},\ldots,x_{n})$ in the category of $\mathbf{k}$-algebras. In
fact, the latter limit is the $\mathbf{k}$-algebra of all symmetric power
series $f$ in $\mathbf{k}\left[{\mathbf{x}}\right]$ with the following
property: For each $g\in{\mathbb{N}}$, there exists a $d\in{\mathbb{N}}$ such
that every monomial in $f$ that involves exactly $g$ distinct indeterminates
has degree at most $d$. For example, the power series
$\left(1+x_{1}\right)\left(1+x_{2}\right)\left(1+x_{3}\right)\cdots$ and
$m_{\left(1\right)}+m_{\left(2,2\right)}+m_{\left(3,3,3\right)}+\cdots$
satisfy this property, although they do not lie in $\Lambda$ (unless
$\mathbf{k}$ is a trivial ring).

This characterization of $\Lambda$ as an inverse limit of the graded
$\mathbf{k}$-algebras $\Lambda(x_{1},\ldots,x_{n})$ can be used as an
alternative definition of $\Lambda$. The definitions used by Macdonald [114]
and Wildon [180] are closely related (see [114, §1.2, p. 19, Remark 1], [70,
§A.11] and [180, §1.7] for discussions of this definition). It also suggests
that much of the theory of symmetric functions can be rewritten in terms of
the $\Lambda(x_{1},\ldots,x_{n})$ (at the cost of extra complexity); and this
indeed is possible494949See, for example, [94, Chapter SYM] for various
results of this present chapter rewritten in terms of symmetric polynomials in
finitely many variables..

One can also define a comultiplication on $\Lambda$ as follows. Note that when
one decomposes the variables into two sets
$({\mathbf{x}},{\mathbf{y}})=(x_{1},x_{2},\ldots,y_{1},y_{2},\ldots)$, one has
a ring homomorphism

$\begin{array}[]{rcl}R({\mathbf{x}})\otimes
R({\mathbf{x}})&\longrightarrow&R({\mathbf{x}},{\mathbf{y}})\\\
f({\mathbf{x}})\otimes
g({\mathbf{x}})&\longmapsto&f({\mathbf{x}})g({\mathbf{y}}).\end{array}$

This restricts to an isomorphism

(2.2) $\Lambda\otimes\Lambda=R({\mathbf{x}})^{\mathfrak{S}_{(\infty)}}\otimes
R({\mathbf{x}})^{\mathfrak{S}_{(\infty)}}\longrightarrow
R({\mathbf{x}},{\mathbf{y}})^{\mathfrak{S}_{(\infty)}\times\mathfrak{S}_{(\infty)}}$

where $\mathfrak{S}_{(\infty)}\times\mathfrak{S}_{(\infty)}$ denotes
permutations of (finite subsets of) the ${\mathbf{x}}$ and separate
permutations of (finite subsets of) the ${\mathbf{y}}$, because
$R({\mathbf{x}},{\mathbf{y}})^{\mathfrak{S}_{(\infty)}\times\mathfrak{S}_{(\infty)}}$
has $\mathbf{k}$-basis
$\\{m_{\lambda}({\mathbf{x}})m_{\mu}({\mathbf{y}})\\}_{\lambda,\mu\in\operatorname{Par}}$.
As $\mathfrak{S}_{(\infty)}\times\mathfrak{S}_{(\infty)}$ is a subgroup of the
group $\mathfrak{S}_{(\infty,\infty)}$ (the group of all permutations of
$\left\\{x_{1},x_{2},\ldots,y_{1},y_{2},\ldots\right\\}$ leaving all but
finitely many variables invariant) acting on all of
$({\mathbf{x}},{\mathbf{y}})$, one gets an inclusion of rings

$\Lambda({\mathbf{x}},{\mathbf{y}})=R({\mathbf{x}},{\mathbf{y}})^{\mathfrak{S}_{(\infty,\infty)}}\hookrightarrow
R({\mathbf{x}},{\mathbf{y}})^{\mathfrak{S}_{(\infty)}\times\mathfrak{S}_{(\infty)}}\cong\Lambda\otimes\Lambda$

where the last isomorphism is the inverse of the one in (2.2). This gives a
comultiplication

$\begin{array}[]{rcl}\Lambda=\Lambda({\mathbf{x}})&\overset{\Delta}{\longrightarrow}&\Lambda({\mathbf{x}},{\mathbf{y}})\hookrightarrow\Lambda\otimes\Lambda\\\
f({\mathbf{x}})=f(x_{1},x_{2},\ldots)&\longmapsto&f({\mathbf{x}},{\mathbf{y}})=f(x_{1},x_{2},\ldots,y_{1},y_{2},\ldots).\end{array}$

Here, $f\left(x_{1},x_{2},\ldots,y_{1},y_{2},\ldots\right)$ means the result
of choosing some bijection
$\phi:\left\\{x_{1},x_{2},x_{3},\ldots\right\\}\to\left\\{x_{1},x_{2},\ldots,y_{1},y_{2},\ldots\right\\}$
and substituting $\phi\left(x_{i}\right)$ for every $x_{i}$ in $f$. (The
choice of $\phi$ is irrelevant since $f$ is symmetric.505050To be more
precise, the choice of $\phi$ is irrelevant because $f$ is
$\mathfrak{S}_{\infty}$-invariant, with the notations of Remark 2.5.)

######  Example 2.7.

One has

$\displaystyle\Delta m_{(2,1)}$
$\displaystyle=m_{(2,1)}(x_{1},x_{2},\ldots,y_{1},y_{2},\ldots)$
$\displaystyle=x_{1}^{2}x_{2}+x_{1}x_{2}^{2}+\cdots$
$\displaystyle\quad+x_{1}^{2}y_{1}+x_{1}^{2}y_{2}+\cdots$
$\displaystyle\quad+x_{1}y_{1}^{2}+x_{1}y_{2}^{2}+\cdots$
$\displaystyle\quad+y_{1}^{2}y_{2}+y_{1}y_{2}^{2}+\cdots$
$\displaystyle=m_{(2,1)}({\mathbf{x}})+m_{(2)}({\mathbf{x}})m_{(1)}({\mathbf{y}})+m_{(1)}({\mathbf{x}})m_{(2)}({\mathbf{y}})+m_{(2,1)}({\mathbf{y}})$
$\displaystyle=m_{(2,1)}\otimes 1+m_{(2)}\otimes m_{(1)}+m_{(1)}\otimes
m_{(2)}+1\otimes m_{(2,1)}.$

This example generalizes easily to the following formula

(2.3) $\Delta m_{\lambda}=\sum_{\begin{subarray}{c}(\mu,\nu):\\\
\mu\sqcup\nu=\lambda\end{subarray}}m_{\mu}\otimes m_{\nu},$

in which $\mu\sqcup\nu$ is the partition obtained by taking the multiset union
of the parts of $\mu$ and $\nu$, and then reordering them to make them weakly
decreasing.

Checking that $\Delta$ is coassociative amounts to checking that

$(\Delta\otimes\operatorname{id})\circ\Delta
f=f({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})=(\operatorname{id}\otimes\Delta)\circ\Delta
f$

inside $\Lambda({\mathbf{x}},{\mathbf{y}},{\mathbf{z}})$ as a subring of
$\Lambda\otimes\Lambda\otimes\Lambda$. The counit
$\Lambda\overset{\epsilon}{\rightarrow}\mathbf{k}$ is defined in the usual
fashion for graded connected coalgebras, namely $\epsilon$ annihilates
$I=\bigoplus_{n>0}\Lambda_{n}$, and $\epsilon$ is the identity on
$\Lambda_{0}=\mathbf{k}$; alternatively $\epsilon$ sends a symmetric function
$f({\mathbf{x}})$ to its constant term $f(0,0,\ldots)$.

Note that $\Delta$ is an algebra morphism
$\Lambda\rightarrow\Lambda\otimes\Lambda$ because it is a composition of maps
which are all algebra morphisms. As the unit and counit axioms are easily
checked, $\Lambda$ becomes a graded connected $\mathbf{k}$-bialgebra of finite
type, and hence also a Hopf algebra by Proposition 1.36. We will identify its
antipode more explicitly in Section 2.4 below.

###  2.2. Other Bases

We introduce the usual other bases of $\Lambda$, and explain their
significance later.

######  Definition 2.8.

Define the families of power sum symmetric functions $p_{n}$, elementary
symmetric functions $e_{n}$, and complete homogeneous symmetric functions
$h_{n}$, for $n=1,2,3,\ldots$ by

(2.4) $\displaystyle p_{n}$
$\displaystyle:=x_{1}^{n}+x_{2}^{n}+\cdots=m_{(n)}$ (2.5) $\displaystyle
e_{n}$ $\displaystyle:=\sum_{i_{1}<\cdots<i_{n}}x_{i_{1}}\cdots
x_{i_{n}}=m_{(1^{n})}$ (2.6) $\displaystyle h_{n}$
$\displaystyle:=\sum_{i_{1}\leq\cdots\leq i_{n}}x_{i_{1}}\cdots
x_{i_{n}}=\sum_{\lambda\in\operatorname{Par}_{n}}m_{\lambda}$

Here, we are using the multiplicative notation for partitions: whenever
$\left(m_{1},m_{2},m_{3},\cdots\right)$ is a weak composition,
$\left(1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots\right)$ denotes the partition
$\lambda$ such that for every $i$, the multiplicity of the part $i$ in
$\lambda$ is $m_{i}$. The $i^{m_{i}}$ satisfying $m_{i}=0$ are often omitted
from this notation, and so the $\left(1^{n}\right)$ in (2.5) means
$\left(\underbrace{1,1,\ldots,1}_{n\text{ ones}}\right)$. (For another
example,
$\left(1^{2}3^{1}4^{3}\right)=\left(1^{2}2^{0}3^{1}4^{3}5^{0}6^{0}7^{0}\cdots\right)$
means the partition $\left(4,4,4,3,1,1\right)$.) By convention, also define
$h_{0}=e_{0}=1$, and $h_{n}=e_{n}=0$ if $n<0$. Extend these multiplicatively
to partitions $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell})$ with
$\lambda_{1}\geq\cdots\geq\lambda_{\ell}>0$:

$\displaystyle p_{\lambda}$
$\displaystyle:=p_{\lambda_{1}}p_{\lambda_{2}}\cdots p_{\lambda_{\ell}}$
$\displaystyle e_{\lambda}$
$\displaystyle:=e_{\lambda_{1}}e_{\lambda_{2}}\cdots e_{\lambda_{\ell}}$
$\displaystyle h_{\lambda}$
$\displaystyle:=h_{\lambda_{1}}h_{\lambda_{2}}\cdots h_{\lambda_{\ell}}$

Also define the Schur function

(2.7) $s_{\lambda}:=\sum_{T}{\mathbf{x}}^{\operatorname{cont}(T)}$

where $T$ runs through all column-strict tableaux of shape $\lambda$, that is,
$T$ is an assignment of entries in $\\{1,2,3,\ldots\\}$ to the cells of the
Ferrers diagram515151The Ferrers diagram of a partition $\lambda$ is defined
as the set of all pairs $\left(i,j\right)\in\left\\{1,2,3,\ldots\right\\}^{2}$
satisfying $j\leq\lambda_{i}$. This is a set of cardinality
$\left|\lambda\right|$. Usually, one visually represents a Ferrers diagram by
drawing its elements $\left(i,j\right)$ as points on the plane, although
(unlike the standard convention for drawing points on the plane) one lets the
x-axis go top-to-bottom (i.e., the point $\left(i+1,j\right)$ is one step
below the point $\left(i,j\right)$), and the y-axis go left-to-right (i.e.,
the point $\left(i,j+1\right)$ is one step to the right of the point
$\left(i,j\right)$). (This is the so-called English notation, also known as
the matrix notation because it is precisely the way one labels the entries of
a matrix. Other notations appear in literature, such as the French notation
used, e.g., in Malvenuto’s [117], and the Russian notation used, e.g., in
parts of Kerov’s [86].) These points are drawn either as dots or as square
boxes; in the latter case, the boxes are centered at the points they
represent, and they have sidelength $1$ so that the boxes centered around
$\left(i,j\right)$ and $\left(i,j+1\right)$ touch each other along a sideline.
For example, the Ferrers diagram of the partition $\left(3,2,2\right)$ is
represented as  $\begin{matrix}\bullet&\bullet&\bullet\\\ \bullet&\bullet&\\\
\bullet&\bullet&\\\ \end{matrix}\text{ (using dots) }\qquad\qquad\text{ or as
}\qquad\qquad\begin{tabular}[]{ccc}\hline\cr\vrule\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol
&\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol
&\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol \\\
\hline\cr\vrule\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol
&\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol &\\\
\cline{1-2}\cr\vrule\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol
&\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol &\\\
\cline{1-2}\cr\end{tabular}\text{ (using boxes).}$ The Ferrers diagram of a
partition $\lambda$ uniquely determines $\lambda$. One refers to the elements
of the Ferrers diagram of $\lambda$ as the cells (or boxes) of this diagram
(which is particularly natural when one represents them by boxes) or, briefly,
as the cells of $\lambda$. Notation like “west”, “north”, “left”, “right”,
“row” and “column” concerning cells of Ferrers diagrams normally refers to
their visual representation. Ferrers diagrams are also known as Young
diagrams. One can characterize the Ferrers diagrams of partitions as follows:
A finite subset $S$ of $\left\\{1,2,3,\ldots\right\\}^{2}$ is the Ferrers
diagram of some partition if and only if for every $\left(i,j\right)\in S$ and
every $\left(i^{\prime},j^{\prime}\right)\in\left\\{1,2,3,\ldots\right\\}^{2}$
satisfying $i^{\prime}\leq i$ and $j^{\prime}\leq j$, we have
$\left(i^{\prime},j^{\prime}\right)\in S$. In other words, a finite subset $S$
of $\left\\{1,2,3,\ldots\right\\}^{2}$ is the Ferrers diagram of some
partition if and only if it is a lower set of the poset
$\left\\{1,2,3,\ldots\right\\}^{2}$ with respect to the componentwise order.
for $\lambda$, weakly increasing left-to-right in rows, and strictly
increasing top-to-bottom in columns. Here $\operatorname{cont}(T)$ denotes the
weak composition $\left(|T^{-1}(1)|,|T^{-1}(2)|,|T^{-1}(3)|,\ldots\right)$, so
that ${\mathbf{x}}^{\operatorname{cont}(T)}=\prod_{i}x_{i}^{|T^{-1}(i)|}$. For
example,525252To visually represent a column-strict tableau $T$ of shape
$\lambda$, we draw the same picture as when representing the Ferrers diagram
of $\lambda$, but with a little difference: a cell $\left(i,j\right)$ is no
longer represented by a dot or box, but instead is represented by the entry of
$T$ assigned to this cell. Accordingly, the entry of $T$ assigned to a given
cell $c$ is often referred to as the entry of $T$ in $c$.

$T=\begin{matrix}1&1&1&4&7\\\ 2&3&3&&\\\ 4&4&6&&\\\ 6&7\end{matrix}$

is a column-strict tableau of shape $\lambda=(5,3,3,2)$ with
${\mathbf{x}}^{\operatorname{cont}(T)}=x_{1}^{3}x_{2}^{1}x_{3}^{2}x_{4}^{3}x_{5}^{0}x_{6}^{2}x_{7}^{2}$.

######  Example 2.9.

One has

$\displaystyle m_{(1)}$
$\displaystyle=p_{(1)}=e_{(1)}=h_{(1)}=s_{(1)}=x_{1}+x_{2}+x_{3}+\cdots$
$\displaystyle s_{(n)}$ $\displaystyle=h_{n}$ $\displaystyle s_{(1^{n})}$
$\displaystyle=e_{n}$

######  Example 2.10.

One has for $\lambda=(2,1)$ that

$\begin{array}[]{rl}p_{(2,1)}&=p_{2}p_{1}=(x_{1}^{2}+x_{2}^{2}+\cdots)(x_{1}+x_{2}+\cdots)\\\
&=m_{(2,1)}+m_{(3)}\\\ &\\\
e_{(2,1)}&=e_{2}e_{1}=(x_{1}x_{2}+x_{1}x_{3}+\cdots)(x_{1}+x_{2}+\cdots)\\\
&=m_{(2,1)}+3m_{(1,1,1)}\\\ &\\\
h_{(2,1)}&=h_{2}h_{1}=(x_{1}^{2}+x_{2}^{2}+\cdots+x_{1}x_{2}+x_{1}x_{3}+\cdots)(x_{1}+x_{2}+\cdots)\\\
&=m_{(3)}+2m_{(2,1)}+3m_{(1,1,1)}\\\ \end{array}$

and

$\displaystyle\begin{matrix}s_{(2,1)}&=x_{1}^{2}x_{2}&+x_{1}^{2}x_{3}&+x_{1}x_{2}^{2}&+x_{1}x_{3}^{2}&+x_{1}x_{2}x_{3}&+x_{1}x_{2}x_{3}&+x_{1}x_{2}x_{4}&+\cdots\\\
&11&11&12&13&12&13&12&\\\
&2\phantom{1}&3\phantom{1}&2\phantom{1}&3\phantom{1}&3\phantom{1}&2\phantom{1}&4\phantom{1}&\\\
\end{matrix}$ $\displaystyle\qquad\quad=m_{(2,1)}+2m_{(1,1,1)}$

In fact, one has these transition matrices for $n=3$ expressing elements in
terms of the monomial basis $m_{\lambda}$:

$\bordermatrix{~{}&p_{(3)}&p_{(2,1)}&p_{(1,1,1)}\cr m_{(3)}&1&1&1\cr
m_{(2,1)}&0&1&3\cr
m_{(1,1,1)}&0&0&6}\qquad\bordermatrix{~{}&e_{(3)}&e_{(2,1)}&e_{(1,1,1)}\cr
m_{(3)}&0&0&1\cr m_{(2,1)}&0&1&3\cr m_{(1,1,1)}&1&3&6}$
$\bordermatrix{~{}&h_{(3)}&h_{(2,1)}&h_{(1,1,1)}\cr m_{(3)}&1&1&1\cr
m_{(2,1)}&1&2&3\cr
m_{(1,1,1)}&1&3&6}\qquad\bordermatrix{~{}&s_{(3)}&s_{(2,1)}&s_{(1,1,1)}\cr
m_{(3)}&1&0&0\cr m_{(2,1)}&1&1&0\cr m_{(1,1,1)}&1&2&1}$

Our next goal is to show that $e_{\lambda},s_{\lambda},h_{\lambda}$ (and,
under some conditions, the $p_{\lambda}$ as well) all give bases for
$\Lambda$. However at the moment it is not yet even clear that $s_{\lambda}$
are symmetric!

######  Proposition 2.11.

Schur functions $s_{\lambda}$ are symmetric, that is, they lie in $\Lambda$.

###### Proof.

It suffices to show $s_{\lambda}$ is symmetric under swapping the variables
$x_{i},x_{i+1}$, by providing an involution $\iota$ on the set of all column-
strict tableaux $T$ of shape $\lambda$ which switches the
$\operatorname{cont}(T)$ for $(i,i+1)\operatorname{cont}(T)$. Restrict
attention to the entries $i,i+1$ in $T$, which must look something like this:

$\setcounter{MaxMatrixCols}{14}\begin{matrix}&&&&&&&&i&i&i&i&i+1&i+1\\\
&i&i&i&i&i&i+1&i+1&i+1&i+1&i+1&&&\\\ i+1&i+1&i+1&&&&&&&&&&\end{matrix}$

One finds several vertically aligned pairs $\begin{matrix}i\\\
i+1\end{matrix}$. If one were to remove all such pairs, the remaining entries
would be a sequence of rows, each looking like this:

(2.8) $\underbrace{i,i,\ldots,i}_{r\text{
occurrences}},\underbrace{i+1,i+1,\ldots,i+1}_{s\text{ occurrences}}$

An involution due to Bender and Knuth tells us to leave fixed all the
vertically aligned pairs $\begin{matrix}i\\\ i+1\end{matrix}$, but change each
sequence as in (2.8) to this:

$\underbrace{i,i,\ldots,i}_{s\text{
occurrences}},\underbrace{i+1,i+1,\ldots,i+1}_{r\text{ occurrences}}$

For example, the above configuration in $T$ would change to

$\setcounter{MaxMatrixCols}{14}\begin{matrix}&&&&&&&&i&i&i&i&i&i+1\\\
&i&i&i&i&i+1&i+1&i+1&i+1&i+1&i+1&&&\\\ i&i+1&i+1&&&&&&&&&&\end{matrix}$

It is easily checked that this map is an involution, and that it has the
effect of swapping $(i,i+1)$ in $\operatorname{cont}(T)$. ∎

######  Remark 2.12.

The symmetry of Schur functions allows one to reformulate them via column-
strict tableaux defined with respect to any total ordering $\mathcal{L}$ on
the positive integers, rather than the usual $1<2<3<\cdots$. For example, one
can use the reverse order535353This reverse order is what one uses when one
defines a Schur function as a generating function for reverse semistandard
tableaux or column-strict plane partitions; see Stanley [164, Proposition
7.10.4]. $\cdots<3<2<1,$ or even more exotic orders, such as

$1<3<5<7<\cdots<2<4<6<8<\cdots.$

Say that an assignment $T$ of entries in $\\{1,2,3,\ldots\\}$ to the cells of
the Ferrers diagram of $\lambda$ is an $\mathcal{L}$-column-strict tableau if
it is weakly $\mathcal{L}$-increasing left-to-right in rows, and strictly
$\mathcal{L}$-increasing top-to-bottom in columns.

######  Proposition 2.13.

For any total order $\mathcal{L}$ on the positive integers,

(2.9) $s_{\lambda}=\sum_{T}{\mathbf{x}}^{\operatorname{cont}(T)}$

as $T$ runs through all $\mathcal{L}$-column-strict tableaux of shape
$\lambda$.

###### Proof.

Given a weak composition $\alpha=(\alpha_{1},\alpha_{2},\ldots)$ with
$\alpha_{n+1}=\alpha_{n+2}=\cdots=0$, assume that the integers $1,2,\ldots,n$
are totally ordered by $\mathcal{L}$ as
$w(1)<_{\mathcal{L}}\cdots<_{\mathcal{L}}w(n)$ for some $w$ in
$\mathfrak{S}_{n}$. Then the coefficient of
${\mathbf{x}}^{\alpha}=x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ on the
right side of (2.9) is the same as the coefficient of
${\mathbf{x}}^{w^{-1}(\alpha)}$ on the right side of (2.7) defining
$s_{\lambda}$, which by symmetry of $s_{\lambda}$ is the same as the
coefficient of ${\mathbf{x}}^{\alpha}$ on the right side of (2.7). ∎

It is now not hard to show that $p_{\lambda},e_{\lambda},s_{\lambda}$ give
bases by a triangularity argument545454See Section 11.1 for some notions and
notations that will be used in this argument.. For this purpose, let us
introduce a useful partial order on partitions.

######  Definition 2.14.

The dominance or majorization order on $\operatorname{Par}_{n}$ is the partial
order on the set $\operatorname{Par}_{n}$ whose greater-or-equal relation
$\triangleright$ is defined as follows: For two partitions $\lambda$ and $\mu$
of $n$, we set $\lambda\triangleright\mu$ (and say that $\lambda$ dominates,
or majorizes, $\mu$) if and only if

$\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k}\geq\mu_{1}+\mu_{2}+\cdots+\mu_{k}\quad\text{
for }k=1,2,\ldots,n.$

(The definition of dominance would not change if we would replace “for
$k=1,2,\ldots,n$” by “for every positive integer $k$” or by “for every
$k\in{\mathbb{N}}$”.)

######  Definition 2.15.

For a partition $\lambda$, its conjugate or transpose partition $\lambda^{t}$
is the one whose Ferrers diagram is obtained from that of $\lambda$ by
exchanging rows for columns. Alternatively, one has this formula for its
$i^{th}$ part:

(2.10) $(\lambda^{t})_{i}:=|\\{j:\lambda_{j}\geq i\\}|.$

######  Exercise 2.16.

Let $\lambda,\mu\in\operatorname{Par}_{n}$. Show that
$\lambda\triangleright\mu$ if and only if $\mu^{t}\triangleright\lambda^{t}$.

######  Proposition 2.17.

The sets $\\{e_{\lambda}\\},\\{s_{\lambda}\\}$ as $\lambda$ runs through all
partitions give $\mathbf{k}$-bases for $\Lambda_{\mathbf{k}}$ for any
commutative ring $\mathbf{k}$. The same holds for $\\{p_{\lambda}\\}$ when
${\mathbb{Q}}$ is a subring of $\mathbf{k}$.

Our proof of this proposition will involve three separate arguments, one for
each of the three alleged bases $\\{s_{\lambda}\\},\\{e_{\lambda}\\}$ and
$\\{p_{\lambda}\\}$; however, all these three arguments fit the same mold:
Each one shows that the alleged basis expands invertibly
triangularly555555i.e., triangularly, with all diagonal coefficients being
invertible in the basis $\\{m_{\lambda}\\}$ (possibly after reindexing), with
an appropriately chosen partial order on the indexing set. We will simplify
our life by restricting ourselves to $\operatorname{Par}_{n}$ for a given
$n\in{\mathbb{N}}$, and by stating the common part of the three arguments in a
greater generality (so that we won’t have to repeat it thrice):

######  Lemma 2.18.

Let $S$ be a finite poset. We write $\leq$ for the smaller-or-equal relation
of $S$.

Let $M$ be a free $\mathbf{k}$-module with a basis
$\left(b_{\lambda}\right)_{\lambda\in S}$. Let
$\left(a_{\lambda}\right)_{\lambda\in S}$ be a further family of elements of
$M$.

For each $\lambda\in S$, let $\left(g_{\lambda,\mu}\right)_{\mu\in S}$ be the
family of the coefficients in the expansion of $a_{\lambda}\in M$ in the basis
$\left(b_{\mu}\right)_{\mu\in S}$; in other words, let
$\left(g_{\lambda,\mu}\right)_{\mu\in S}\in\mathbf{k}^{S}$ be such that
$a_{\lambda}=\sum\limits_{\mu\in S}g_{\lambda,\mu}b_{\mu}$. Assume that:

  * •

Assumption A1: Any $\lambda\in S$ and $\mu\in S$ satisfy $g_{\lambda,\mu}=0$
unless $\mu\leq\lambda$.

  * •

Assumption A2: For any $\lambda\in S$, the element $g_{\lambda,\lambda}$ of
$\mathbf{k}$ is invertible.

Then, the family $\left(a_{\lambda}\right)_{\lambda\in S}$ is a basis of the
$\mathbf{k}$-module $M$.

###### Proof of Lemma 2.18..

Use the notations of Section 11.1. Assumptions A1 and A2 yield that the
$S\times S$-matrix $\left(g_{\lambda,\mu}\right)_{\left(\lambda,\mu\right)\in
S\times S}\in\mathbf{k}^{S\times S}$ is invertibly triangular. But the
definition of the $g_{\lambda,\mu}$ yields that the family
$\left(a_{\lambda}\right)_{\lambda\in S}$ expands in the family
$\left(b_{\lambda}\right)_{\lambda\in S}$ through this matrix
$\left(g_{\lambda,\mu}\right)_{\left(\lambda,\mu\right)\in S\times S}$. Since
the latter matrix is invertibly triangular, this shows that the family
$\left(a_{\lambda}\right)_{\lambda\in S}$ expands invertibly triangularly in
the family $\left(b_{\lambda}\right)_{\lambda\in S}$. Therefore, Corollary
11.19(e) (applied to $\left(e_{s}\right)_{s\in
S}=\left(a_{\lambda}\right)_{\lambda\in S}$ and $\left(f_{s}\right)_{s\in
S}=\left(b_{\lambda}\right)_{\lambda\in S}$) shows that
$\left(a_{\lambda}\right)_{\lambda\in S}$ is a basis of the
$\mathbf{k}$-module $M$ (since $\left(b_{\lambda}\right)_{\lambda\in S}$ is a
basis of the $\mathbf{k}$-module $M$). ∎

###### Proof of Proposition 2.17..

We can restrict our attention to each homogeneous component $\Lambda_{n}$ and
partitions $\lambda$ of $n$. Thus, we have to prove that, for each
$n\in{\mathbb{N}}$, the families
$\left(e_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ and
$\left(s_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ are bases of the
$\mathbf{k}$-module $\Lambda_{n}$, and that the same holds for
$\left(p_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ if
${\mathbb{Q}}$ is a subring of $\mathbf{k}$.

Fix $n\in{\mathbb{N}}$. We already know that
$\left(m_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ is a basis of
the $\mathbf{k}$-module $\Lambda_{n}$.

  1. 1.

We shall first show that the family
$\left(s_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ is a basis of
the $\mathbf{k}$-module $\Lambda_{n}$.

For every partition $\lambda$, we have
$s_{\lambda}=\sum_{\mu\in\operatorname{Par}}K_{\lambda,\mu}m_{\mu}$, where the
coefficient $K_{\lambda,\mu}$ is the Kostka number counting the column-strict
tableaux $T$ of shape $\lambda$ having $\operatorname{cont}(T)=\mu$; this
follows because both sides are symmetric functions, and $K_{\lambda,\mu}$ is
the coefficient of ${\mathbf{x}}^{\mu}$ on both sides565656In general, in
order to prove that two symmetric functions $f$ and $g$ are equal, it suffices
to show that, for every $\mu\in\operatorname{Par}$, the coefficients of
${\mathbf{x}}^{\mu}$ in $f$ and in $g$ are equal. (Indeed, all other
coefficients are determined by these coefficients because of the symmetry.).
Thus, for every $\lambda\in\operatorname{Par}_{n}$, one has

(2.11) $s_{\lambda}=\sum_{\mu\in\operatorname{Par}_{n}}K_{\lambda,\mu}m_{\mu}$

(since $s_{\lambda}$ is homogeneous of degree $n$). But if $\lambda$ and $\mu$
are partitions satisfying $K_{\lambda,\mu}\neq 0$, then there exists a column-
strict tableau $T$ of shape $\lambda$ having $\operatorname{cont}(T)=\mu$
(since $K_{\lambda,\mu}$ counts such tableaux), and therefore we must have
$\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k}\geq\mu_{1}+\mu_{2}+\cdots+\mu_{k}$
for each positive integer $k$ (since the entries $1,2,\ldots,k$ in $T$ must
all lie within the first $k$ rows of $\lambda$); in other words,
$\lambda\triangleright\mu$ (if $K_{\lambda,\mu}\neq 0$). In other words,

(2.12) $\text{any }\lambda\in\operatorname{Par}_{n}\text{ and
}\mu\in\operatorname{Par}_{n}\text{ satisfy }K_{\lambda,\mu}=0\text{ unless
}\lambda\triangleright\mu.$

One can also check that $K_{\lambda,\lambda}=1$ for any
$\lambda\in\operatorname{Par}_{n}$. Hence,

(2.13) $\text{for any }\lambda\in\operatorname{Par}_{n}\text{, the element
}K_{\lambda,\lambda}\text{ of }\mathbf{k}\text{ is invertible.}$

Now, let us regard the set $\operatorname{Par}_{n}$ as a poset, whose greater-
or-equal relation is $\triangleright$. Lemma 2.18 (applied to
$S=\operatorname{Par}_{n}$, $M=\Lambda_{n}$, $a_{\lambda}=s_{\lambda}$,
$b_{\lambda}=m_{\lambda}$ and $g_{\lambda,\mu}=K_{\lambda,\mu}$) shows that
the family $\left(s_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ is a
basis of the $\mathbf{k}$-module $\Lambda_{n}$ (because the Assumptions A1 and
A2 of Lemma 2.18 are satisfied575757Indeed, they follow from (2.12) and
(2.13), respectively.).

  2. 2.

Before we show that
$\left(e_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ is a basis, we
define a few notations regarding integer matrices. A $\\{0,1\\}$-matrix means
a matrix whose entries belong to the set $\\{0,1\\}$. If
$A\in{\mathbb{N}}^{\ell\times m}$ is a matrix, then the row sums of $A$ means
the $\ell$-tuple $\left(r_{1},r_{2},\ldots,r_{\ell}\right)$, where each
$r_{i}$ is the sum of all entries in the $i$-th row of $A$; similarly, the
column sums of $A$ means the $m$-tuple
$\left(c_{1},c_{2},\ldots,c_{m}\right)$, where each $c_{j}$ is the sum of all
entries in the $j$-th column of $A$.

For every $\lambda\in\operatorname{Par}_{n}$, one has

(2.14)
$e_{\lambda}=\sum_{\mu\in\operatorname{Par}_{n}}a_{\lambda,\mu}m_{\mu},$

where $a_{\lambda,\mu}$ counts $\\{0,1\\}$-matrices (of size
$\ell\left(\lambda\right)\times\ell\left(\mu\right)$) having row sums
$\lambda$ and column sums $\mu$: indeed, when one expands
$e_{\lambda_{1}}e_{\lambda_{2}}\cdots$, choosing the monomial $x_{j_{1}}\ldots
x_{j_{\lambda_{i}}}$ in the $e_{\lambda_{i}}$ factor corresponds to putting
$1$’s in the $i^{th}$ row and columns $j_{1},\ldots,j_{\lambda_{i}}$ of the
$\\{0,1\\}$-matrix. Applying (2.14) to $\lambda^{t}$ instead of $\lambda$, we
see that

(2.15)
$e_{\lambda^{t}}=\sum_{\mu\in\operatorname{Par}_{n}}a_{\lambda^{t},\mu}m_{\mu}$

for every $\lambda\in\operatorname{Par}_{n}$.

It is not hard to check585858This is the easy implication in the Gale-Ryser
Theorem. that $a_{\lambda,\mu}$ vanishes unless
$\lambda^{t}\triangleright\mu$. Applying this to $\lambda^{t}$ instead of
$\lambda$, we conclude that

(2.16) $\text{any }\lambda\in\operatorname{Par}_{n}\text{ and
}\mu\in\operatorname{Par}_{n}\text{ satisfy }a_{\lambda^{t},\mu}=0\text{
unless }\lambda\triangleright\mu.$

Moreover, one can show that $a_{\lambda^{t},\lambda}=1$ for each
$\lambda\in\operatorname{Par}_{n}$. Hence,

(2.17) $\text{for any }\lambda\in\operatorname{Par}_{n}\text{, the element
}a_{\lambda^{t},\lambda}\text{ of }\mathbf{k}\text{ is invertible.}$

Now, let us regard the set $\operatorname{Par}_{n}$ as a poset, whose greater-
or-equal relation is $\triangleright$. Lemma 2.18 (applied to
$S=\operatorname{Par}_{n}$, $M=\Lambda_{n}$, $a_{\lambda}=e_{\lambda^{t}}$,
$b_{\lambda}=m_{\lambda}$ and $g_{\lambda,\mu}=a_{\lambda^{t},\mu}$) shows
that the family
$\left(e_{\lambda^{t}}\right)_{\lambda\in\operatorname{Par}_{n}}$ is a basis
of the $\mathbf{k}$-module $\Lambda_{n}$ (because the Assumptions A1 and A2 of
Lemma 2.18 are satisfied595959Indeed, they follow from (2.16) and (2.17),
respectively.). Hence,
$\left(e_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ is a basis of
$\Lambda_{n}$.

  3. 3.

Assume now that ${\mathbb{Q}}$ is a subring of $\mathbf{k}$. For every
$\lambda\in\operatorname{Par}_{n}$, one has

(2.18)
$p_{\lambda}=\sum_{\mu\in\operatorname{Par}_{n}}b_{\lambda,\mu}m_{\mu},$

where $b_{\lambda,\mu}$ counts the ways to partition the nonzero parts
$\lambda_{1},\ldots,\lambda_{\ell}$ into blocks such that the sums of the
blocks give $\mu$; more formally, $b_{\lambda,\mu}$ is the number of maps
$\varphi:\\{1,2,\ldots,\ell\\}\rightarrow\\{1,2,3,\ldots\\}$ having
$\mu_{j}=\sum_{i:\varphi(i)=j}\lambda_{i}$ for $j=1,2,\ldots$. Again it is not
hard to check that

(2.19) $\text{any }\lambda\in\operatorname{Par}_{n}\text{ and
}\mu\in\operatorname{Par}_{n}\text{ satisfy }b_{\lambda,\mu}=0\text{ unless
}\mu\triangleright\lambda.$

Furthermore, for any $\lambda\in\operatorname{Par}_{n}$, the element
$b_{\lambda,\lambda}$ is a positive integer, and thus invertible in
$\mathbf{k}$ (since ${\mathbb{Q}}$ is a subring of $\mathbf{k}$). Thus,

(2.20) $\text{for any }\lambda\in\operatorname{Par}_{n}\text{, the element
}b_{\lambda,\lambda}\text{ of }\mathbf{k}\text{ is invertible}$

(although we don’t always have $b_{\lambda,\lambda}=1$ this time).

Now, let us regard the set $\operatorname{Par}_{n}$ as a poset, whose smaller-
or-equal relation is $\triangleright$. Lemma 2.18 (applied to
$S=\operatorname{Par}_{n}$, $M=\Lambda_{n}$, $a_{\lambda}=p_{\lambda}$,
$b_{\lambda}=m_{\lambda}$ and $g_{\lambda,\mu}=b_{\lambda,\mu}$) shows that
the family $\left(p_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ is a
basis of the $\mathbf{k}$-module $\Lambda_{n}$ (because the Assumptions A1 and
A2 of Lemma 2.18 are satisfied606060Indeed, they follow from (2.19) and
(2.20), respectively.).

∎

######  Remark 2.19.

When ${\mathbb{Q}}$ is not a subring of $\mathbf{k}$, the family
$\left\\{p_{\lambda}\right\\}$ is not (in general) a basis of
$\Lambda_{\mathbf{k}}$; for instance,
$e_{2}=\frac{1}{2}\left(p_{(1,1)}-p_{2}\right)\in\Lambda_{{\mathbb{Q}}}$ is
not in the ${\mathbb{Z}}$-span of this family. However, if we define
$b_{\lambda,\mu}$ as in the above proof, then the ${\mathbb{Z}}$-linear span
of all $p_{\lambda}$ equals the ${\mathbb{Z}}$-linear span of all
$b_{\lambda,\lambda}m_{\lambda}$. Indeed, if
$\mu=\left(\mu_{1},\mu_{2},\ldots,\mu_{k}\right)$ with $k=\ell(\mu)$, then
$b_{\mu,\mu}$ is the size of the subgroup of $\mathfrak{S}_{k}$ consisting of
all permutations $\sigma\in\mathfrak{S}_{k}$ having each $i$ satisfy
$\mu_{\sigma(i)}=\mu_{i}$. As a consequence, $b_{\mu,\mu}$ divides
$b_{\lambda,\mu}$ for every partition $\mu$ of the same size as $\lambda$
(because this group acts616161Specifically, an element $\sigma$ of the group
takes $\varphi:\\{1,2,\ldots,\ell\\}\rightarrow\\{1,2,3,\ldots\\}$ to
$\sigma\circ\varphi$. freely on the set which is enumerated by
$b_{\lambda,\mu}$). Hence, the
$\operatorname{Par}_{n}\times\operatorname{Par}_{n}$-matrix
$\left(\dfrac{b_{\lambda,\mu}}{b_{\mu,\mu}}\right)_{\left(\lambda,\mu\right)\in\operatorname{Par}_{n}\times\operatorname{Par}_{n}}$
has integer entries. Furthermore, this matrix is unitriangular626262Here, we
are using the terminology defined in Section 11.1, and we are regarding
$\operatorname{Par}_{n}$ as a poset whose smaller-or-equal relation is
$\triangleright$. (indeed, (2.19) shows that it is triangular, but its
diagonal entries are clearly $1$) and thus invertibly triangular. But (2.18)
shows that the family
$\left(p_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ expands in the
family
$\left(b_{\lambda,\lambda}m_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$
through this matrix. Hence, the family
$\left(p_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ expands
invertibly triangularly in the family
$\left(b_{\lambda,\lambda}m_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$.
Thus, Corollary 11.19(b) (applied to ${\mathbb{Z}}$, $\Lambda_{n}$,
$\operatorname{Par}_{n}$,
$\left(p_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ and
$\left(b_{\lambda,\lambda}m_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$
instead of $\mathbf{k}$, $M$, $S$, $\left(e_{s}\right)_{s\in S}$ and
$\left(f_{s}\right)_{s\in S}$) shows that the ${\mathbb{Z}}$-submodule of
$\Lambda_{n}$ spanned by
$\left(p_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$ is the
${\mathbb{Z}}$-submodule of $\Lambda_{n}$ spanned by
$\left(b_{\lambda,\lambda}m_{\lambda}\right)_{\lambda\in\operatorname{Par}_{n}}$.

###  2.3. Comultiplications

Thinking about comultiplication
$\Lambda\overset{\Delta}{\rightarrow}\Lambda\otimes\Lambda$ on Schur functions
forces us to immediately confront the following.

######  Definition 2.20.

For partitions $\mu,\lambda$ say that $\mu\subseteq\lambda$ if
$\mu_{i}\leq\lambda_{i}$ for $i=1,2,\ldots$, so the Ferrers diagram for $\mu$
is a subset of the cells for the Ferrers diagram of $\lambda$. In this case,
define the skew (Ferrers) diagram $\lambda/\mu$ to be their set
difference.636363In other words, the skew Ferrers diagram $\lambda/\mu$ is the
set of all $\left(i,j\right)\in\left\\{1,2,3,\ldots\right\\}^{2}$ satisfying
$\mu_{i}<j\leq\lambda_{i}$. While the Ferrers diagram for a single partition
$\lambda$ uniquely determines $\lambda$, the skew Ferrers diagram
$\lambda/\mu$ does not uniquely determine $\mu$ and $\lambda$. (For instance,
it is empty whenever $\lambda=\mu$.) When one wants to keep $\mu$ and
$\lambda$ in memory, one speaks of the skew shape $\lambda/\mu$; this simply
means the pair $\left(\mu,\lambda\right)$. Every notion defined for skew
Ferrers diagrams also makes sense for skew shapes, because to any skew shape
$\lambda/\mu$ we can assign the skew Ferrers diagram $\lambda/\mu$ (even if
not injectively). For instance, the cells of the skew shape $\lambda/\mu$ are
the cells of the skew Ferrers diagram $\lambda/\mu$. One can characterize the
skew Ferrers diagrams as follows: A finite subset $S$ of
$\left\\{1,2,3,\ldots\right\\}^{2}$ is a skew Ferrers diagram (i.e., there
exist two partitions $\lambda$ and $\mu$ such that $\mu\subseteq\lambda$ and
such that $S$ is the skew Ferrers diagram $\lambda/\mu$) if and only if for
every $\left(i,j\right)\in S$, every
$\left(i^{\prime},j^{\prime}\right)\in\left\\{1,2,3,\ldots\right\\}^{2}$ and
every $\left(i^{\prime\prime},j^{\prime\prime}\right)\in S$ satisfying
$i^{\prime\prime}\leq i^{\prime}\leq i$ and $j^{\prime\prime}\leq
j^{\prime}\leq j$, we have $\left(i^{\prime},j^{\prime}\right)\in S$.

Then define the skew Schur function $s_{\lambda/\mu}({\mathbf{x}})$ to be the
sum $s_{\lambda/\mu}:=\sum_{T}{\mathbf{x}}^{\operatorname{cont}(T)}$, where
the sum ranges over all column-strict tableaux $T$ of shape $\lambda/\mu$,
that is, assignments of a value in $\\{1,2,3,\ldots\\}$ to each cell of
$\lambda/\mu$, weakly increasing left-to-right in rows, and strictly
increasing top-to-bottom in columns.

######  Example 2.21.

$T=\begin{matrix}\cdot&\cdot&\cdot&2&5\\\ \cdot&1&1&&\\\ 2&2&4&&\\\
4&5\end{matrix}$

is a column-strict tableau of shape $\lambda/\mu=(5,3,3,2)/(3,1,0,0)$ and it
has
${\mathbf{x}}^{\operatorname{cont}(T)}=x_{1}^{2}x_{2}^{3}x_{3}^{0}x_{4}^{2}x_{5}^{2}$.

######  Remark 2.22.

If $\mu$ and $\lambda$ are partitions such that $\mu\subseteq\lambda$, then
$s_{\lambda/\mu}\in\Lambda$. (This is proven similarly as Proposition 2.11.)
Actually, if $\mu\subseteq\lambda$, then
$s_{\lambda/\mu}\in\Lambda_{\left|\lambda/\mu\right|}$, where
$\left|\lambda/\mu\right|$ denotes the number of cells of the skew shape
$\lambda/\mu$ (so
$\left|\lambda/\mu\right|=\left|\lambda\right|-\left|\mu\right|$).

It is customary to define $s_{\lambda/\mu}$ to be $0$ if we don’t have
$\mu\subseteq\lambda$. This can also be seen by a literal reading of the
definition $s_{\lambda/\mu}:=\sum_{T}{\mathbf{x}}^{\operatorname{cont}(T)}$,
as long as we understand that there are no column-strict tableaux of shape
$\lambda/\mu$ when $\lambda/\mu$ is not defined.

Clearly, every partition $\lambda$ satisfies
$s_{\lambda}=s_{\lambda/\varnothing}$.

######  Exercise 2.23.

  * (a)

State and prove an analogue of Proposition 2.13 for skew Schur functions.

  * (b)

Let $\lambda$, $\mu$, $\lambda^{\prime}$ and $\mu^{\prime}$ be partitions such
that $\mu\subseteq\lambda$ and $\mu^{\prime}\subseteq\lambda^{\prime}$. Assume
that the skew Ferrers diagram $\lambda^{\prime}/\mu^{\prime}$ can be obtained
from the skew Ferrers diagram $\lambda/\mu$ by a $180^{\circ}$
rotation.646464For example, this happens when $\lambda=\left(3,2\right)$,
$\mu=\left(1\right)$, $\lambda^{\prime}=\left(5,4\right)$ and
$\mu^{\prime}=\left(3,1\right)$. Prove that
$s_{\lambda/\mu}=s_{\lambda^{\prime}/\mu^{\prime}}$.

######  Exercise 2.24.

Let $\lambda$ and $\mu$ be two partitions, and let $k\in{\mathbb{N}}$ be such
that656565As usual, we write $\nu_{k}$ for the $k$-th entry of a partition
$\nu$. $\mu_{k}\geq\lambda_{k+1}$. Let $F$ be the skew Ferrers diagram
$\lambda/\mu$. Let $F_{\operatorname{rows}\leq k}$ denote the subset of $F$
consisting of all $\left(i,j\right)\in F$ satisfying $i\leq k$. Let
$F_{\operatorname{rows}>k}$ denote the subset of $F$ consisting of all
$\left(i,j\right)\in F$ satisfying $i>k$. Let $\alpha$ and $\beta$ be two
partitions such that $\beta\subseteq\alpha$ and such that the skew Ferrers
diagram $\alpha/\beta$ can be obtained from $F_{\operatorname{rows}\leq k}$ by
parallel translation. Let $\gamma$ and $\delta$ be two partitions such that
$\delta\subseteq\gamma$ and such that the skew Ferrers diagram $\gamma/\delta$
can be obtained from $F_{\operatorname{rows}>k}$ by parallel
translation.666666Here is an example of the situation:
$\lambda=\left(6,5,5,2,2\right)$, $\mu=\left(4,4,3,1\right)$, $k=3$
(satisfying $\mu_{k}=\mu_{3}=3\geq 2=\lambda_{4}=\lambda_{k+1}$),
$\alpha=\left(3,2,2\right)$, $\beta=\left(1,1\right)$,
$\gamma=\left(2,2\right)$, and $\delta=\left(1\right)$. Prove that
$s_{\lambda/\mu}=s_{\alpha/\beta}s_{\gamma/\delta}$.

######  Proposition 2.25.

The comultiplication
$\Lambda\overset{\Delta}{\rightarrow}\Lambda\otimes\Lambda$ has the following
effect on the symmetric functions discussed so far676767 The abbreviated
summation indexing $\sum_{i+j=n}t_{i,j}$ used here is intended to mean
$\sum_{\begin{subarray}{c}(i,j):\\\ 0\leq i,j\leq n,\\\
i+j=n\end{subarray}}t_{i,j}.$ :

  1. (i)

$\Delta p_{n}=1\otimes p_{n}+p_{n}\otimes 1$ for every $n\geq 1$, that is, the
power sums $p_{n}$ are primitive.

  2. (ii)

$\Delta e_{n}=\sum_{i+j=n}e_{i}\otimes e_{j}$ for every $n\in{\mathbb{N}}$.

  3. (iii)

$\Delta h_{n}=\sum_{i+j=n}h_{i}\otimes h_{j}$ for every $n\in{\mathbb{N}}$.

  4. (iv)

$\Delta s_{\lambda}=\sum_{\mu\subseteq\lambda}s_{\mu}\otimes s_{\lambda/\mu}$
for any partition $\lambda$.

  5. (v)

$\Delta s_{\lambda/\nu}=\sum_{\begin{subarray}{c}\mu\in\operatorname{Par}:\\\
\nu\subseteq\mu\subseteq\lambda\end{subarray}}s_{\mu/\nu}\otimes
s_{\lambda/\mu}$ for any partitions $\lambda$ and $\nu$.

###### Proof.

Recall that $\Delta$ sends $f({\mathbf{x}})\mapsto
f({\mathbf{x}},{\mathbf{y}})$, and one can easily check that

  1. (i)

$p_{n}({\mathbf{x}},{\mathbf{y}})=\sum_{i}x_{i}^{n}+\sum_{i}y_{i}^{n}=p_{n}({\mathbf{x}})\cdot
1+1\cdot p_{n}({\mathbf{y}})$

  2. (ii)

$e_{n}({\mathbf{x}},{\mathbf{y}})=\sum_{i+j=n}e_{i}({\mathbf{x}})e_{j}({\mathbf{y}})$

  3. (iii)

$h_{n}({\mathbf{x}},{\mathbf{y}})=\sum_{i+j=n}h_{i}({\mathbf{x}})h_{j}({\mathbf{y}})$

For assertion (iv), note that by (2.9), one has

(2.21)
$s_{\lambda}({\mathbf{x}},{\mathbf{y}})=\sum_{T}({\mathbf{x}},{\mathbf{y}})^{\operatorname{cont}(T)},$

where the sum is over column-strict tableaux $T$ of shape $\lambda$ having
entries in the linearly ordered alphabet

(2.22) $x_{1}<x_{2}<\cdots<y_{1}<y_{2}<\cdots.$ 686868Here,
$({\mathbf{x}},{\mathbf{y}})^{\operatorname{cont}(T)}$ means the monomial
$\prod_{a\in\mathfrak{A}}a^{\left|T^{-1}\left(a\right)\right|}$, where
$\mathfrak{A}$ denotes the totally ordered alphabet
$x_{1}<x_{2}<\cdots<y_{1}<y_{2}<\cdots$. In other words,
$({\mathbf{x}},{\mathbf{y}})^{\operatorname{cont}(T)}$ is the product of all
entries of the tableau $T$ (which is a monomial, since the entries of $T$ are
not numbers but variables). The following rather formal argument should allay
any doubts as to why (2.21) holds: Let $\mathcal{L}$ denote the totally
ordered set which is given by the set $\left\\{1,2,3,\ldots\right\\}$ of
positive integers, equipped with the total order
$1<_{\mathcal{L}}3<_{\mathcal{L}}5<_{\mathcal{L}}7<_{\mathcal{L}}\cdots<_{\mathcal{L}}2<_{\mathcal{L}}4<_{\mathcal{L}}6<_{\mathcal{L}}8<_{\mathcal{L}}\cdots$.
Then, (2.9) yields $s_{\lambda}=\sum_{T}{\mathbf{x}}^{\operatorname{cont}(T)}$
as $T$ runs through all $\mathcal{L}$-column-strict tableaux of shape
$\lambda$. Substituting the variables
$x_{1},y_{1},x_{2},y_{2},x_{3},y_{3},\ldots$ for
$x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},\ldots$ (that is, substituting $x_{i}$
for $x_{2i-1}$ and $y_{i}$ for $x_{2i}$) in this equality, we obtain (2.21).

For example,

$T=\begin{matrix}x_{1}&x_{1}&x_{1}&y_{2}&y_{5}\\\ x_{2}&y_{1}&y_{1}&&\\\
y_{2}&y_{2}&y_{4}&&\\\ y_{4}&y_{5}\end{matrix}$

is such a tableau of shape $\lambda=(5,3,3,2)$. Note that the restriction of
$T$ to the alphabet ${\mathbf{x}}$ gives a column-strict tableau
$T_{\mathbf{x}}$ of some shape $\mu\subseteq\lambda$, and the restriction of
$T$ to the alphabet ${\mathbf{y}}$ gives a column-strict tableau
$T_{\mathbf{y}}$ of shape $\lambda/\mu$ (e.g. for $T$ in the example above,
the tableau $T_{\mathbf{y}}$ appeared in Example 2.21). Consequently, one has

$\displaystyle s_{\lambda}({\mathbf{x}},{\mathbf{y}})=$
$\displaystyle\sum_{T}{\mathbf{x}}^{\operatorname{cont}(T_{\mathbf{x}})}\cdot{\mathbf{y}}^{\operatorname{cont}(T_{\mathbf{y}})}$
(2.23) $\displaystyle=$
$\displaystyle\sum_{\mu\subseteq\lambda}\left(\sum_{T_{\mathbf{x}}}{\mathbf{x}}^{\operatorname{cont}(T_{\mathbf{x}})}\right)\left(\sum_{T_{\mathbf{y}}}{\mathbf{y}}^{\operatorname{cont}(T_{\mathbf{y}})}\right)=\sum_{\mu\subseteq\lambda}s_{\mu}({\mathbf{x}})s_{\lambda/\mu}({\mathbf{y}}).$

Assertion (v) is obvious in the case when we don’t have $\nu\subseteq\lambda$
(in fact, in this case, both $s_{\lambda/\nu}$ and
$\sum_{\begin{subarray}{c}\mu\in\operatorname{Par}:\\\
\nu\subseteq\mu\subseteq\lambda\end{subarray}}s_{\mu/\nu}\otimes
s_{\lambda/\mu}$ are clearly zero). In the remaining case, the proof of
assertion (v) is similar to that of (iv). (Of course, the tableaux $T$ and
$T_{{\mathbf{x}}}$ now have skew shapes $\lambda/\nu$ and $\mu/\nu$, and
instead of (2.9), we need to use the answer to Exercise 2.23(a).) ∎

Notice that parts (ii) and (iii) of Proposition 2.25 are particular cases of
part (iv), since $h_{n}=s_{(n)}$ and $e_{n}=s_{(1^{n})}$.

######  Exercise 2.26.

  * (a)

Show that the Hopf algebra $\Lambda$ is cocommutative.

  * (b)

Show that $\Delta
s_{\lambda/\nu}=\sum_{\begin{subarray}{c}\mu\in\operatorname{Par}:\\\
\nu\subseteq\mu\subseteq\lambda\end{subarray}}s_{\lambda/\mu}\otimes
s_{\mu/\nu}$ for any partitions $\lambda$ and $\nu$.

######  Exercise 2.27.

Let $n\in{\mathbb{N}}$. Consider the finite variable set
$\left(x_{1},x_{2},\ldots,x_{n}\right)$ as a subset of
${\mathbf{x}}=\left(x_{1},x_{2},x_{3},\ldots\right)$. Recall that
$f\left(x_{1},x_{2},\ldots,x_{n}\right)$ is a well-defined element of
$\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]$ for every $f\in
R\left({\mathbf{x}}\right)$ (and therefore also for every $f\in\Lambda$, since
$\Lambda\subset R\left({\mathbf{x}}\right)$), according to Exercise 2.2.

  * (a)

Show that any two partitions $\lambda$ and $\mu$ satisfy

$s_{\lambda/\mu}\left(x_{1},x_{2},\ldots,x_{n}\right)=\sum_{\begin{subarray}{c}T\text{
is a column-strict}\\\ \text{tableau of shape }\lambda/\mu\text{;}\\\
\text{all entries of }T\text{ belong}\\\ \text{to
}\left\\{1,2,\ldots,n\right\\}\end{subarray}}{\mathbf{x}}^{\operatorname{cont}\left(T\right)}.$

  * (b)

If $\lambda$ is a partition having more than $n$ parts (where the word “parts”
means “nonzero parts”), then show that
$s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)=0$.

######  Remark 2.28.

An analogue of Proposition 2.17 holds for symmetric polynomials in finitely
many variables: Let $N\in{\mathbb{N}}$. Then, we have

  * (a)

The set $\left\\{m_{\lambda}\left(x_{1},x_{2},\ldots,x_{N}\right)\right\\}$,
as $\lambda$ runs through all partitions having length $\leq N$, is a basis of
the $\mathbf{k}$-module
$\Lambda\left(x_{1},x_{2},\ldots,x_{N}\right)=\mathbf{k}\left[x_{1},x_{2},\ldots,x_{N}\right]^{\mathfrak{S}_{N}}$.

  * (b)

For any partition $\lambda$ having length $>N$, we have
$m_{\lambda}\left(x_{1},x_{2},\ldots,x_{N}\right)=0$.

  * (c)

The set $\left\\{e_{\lambda}\left(x_{1},x_{2},\ldots,x_{N}\right)\right\\}$,
as $\lambda$ runs through all partitions whose parts are all $\leq N$, is a
basis of the $\mathbf{k}$-module
$\Lambda\left(x_{1},x_{2},\ldots,x_{N}\right)$.

  * (d)

The set $\left\\{s_{\lambda}\left(x_{1},x_{2},\ldots,x_{N}\right)\right\\}$,
as $\lambda$ runs through all partitions having length $\leq N$, is a basis of
the $\mathbf{k}$-module $\Lambda\left(x_{1},x_{2},\ldots,x_{N}\right)$.

  * (e)

If ${\mathbb{Q}}$ is a subring of $\mathbf{k}$, then the set
$\left\\{p_{\lambda}\left(x_{1},x_{2},\ldots,x_{N}\right)\right\\}$, as
$\lambda$ runs through all partitions having length $\leq N$, is a basis of
the $\mathbf{k}$-module $\Lambda\left(x_{1},x_{2},\ldots,x_{N}\right)$.

  * (f)

If ${\mathbb{Q}}$ is a subring of $\mathbf{k}$, then the set
$\left\\{p_{\lambda}\left(x_{1},x_{2},\ldots,x_{N}\right)\right\\}$, as
$\lambda$ runs through all partitions whose parts are all $\leq N$, is a basis
of the $\mathbf{k}$-module $\Lambda\left(x_{1},x_{2},\ldots,x_{N}\right)$.

Indeed, the claims (a) and (b) are obvious, while the claims (c), (d) and (e)
are proven similarly to our proof of Proposition 2.17. We leave the proof of
(f) to the reader.

Claim (c) can be rewritten as follows: The elementary symmetric polynomials
$e_{i}\left(x_{1},x_{2},\ldots,x_{N}\right)$, for
$i\in\left\\{1,2,\ldots,N\right\\}$, form an algebraically independent
generating set of $\Lambda\left(x_{1},x_{2},\ldots,x_{N}\right)$. This is
precisely the well-known theorem (due to Gauss)696969See, e.g., [36, Symmetric
Polynomials, Theorem 5 and Remark 17] or [177, §5.3] or [24, Theorem 1]. In a
slightly different form, it also appears in [94, Theorem (5.10)]. that every
symmetric polynomial in $N$ variables $x_{1},x_{2},\ldots,x_{N}$ can be
written uniquely as a polynomial in the $N$ elementary symmetric polynomials.

###  2.4. The antipode, the involution $\omega$, and algebra generators

Since $\Lambda$ is a graded connected $\mathbf{k}$-bialgebra, it will have an
antipode $\Lambda\overset{S}{\rightarrow}\Lambda$ making it a Hopf algebra by
Proposition 1.36. However, several issues will be resolved by identifying $S$
more explicitly now.

######  Proposition 2.29.

Each of $\\{e_{n}\\}_{n=1,2,\ldots},\\{h_{n}\\}_{n=1,2,\ldots}$ are
algebraically independent, and generate $\Lambda_{\mathbf{k}}$ as a polynomial
algebra for any commutative ring $\mathbf{k}$. The same holds for
$\\{p_{n}\\}_{n=1,2,\ldots}$ when ${\mathbb{Q}}$ is a subring of $\mathbf{k}$.

Furthermore, the antipode $S$ acts as follows:

  1. (i)

$S(p_{n})=-p_{n}$

  2. (ii)

$S(e_{n})=(-1)^{n}h_{n}$

  3. (iii)

$S(h_{n})=(-1)^{n}e_{n}$

###### Proof.

The assertions that $\\{e_{n}\\},\\{p_{n}\\}$ are algebraically independent
and generate $\Lambda$ are equivalent to Proposition 2.17 asserting
$\\{e_{\lambda}\\},\\{p_{\lambda}\\}$ give bases for $\Lambda$. The assertion
$S(p_{n})=-p_{n}$ follows from Proposition 1.37 since $p_{n}$ is primitive by
Proposition 2.25(i).

For the remaining assertions, start with the easy generating function
identities

(2.24) $\displaystyle H(t)$
$\displaystyle:=\prod_{i=1}^{\infty}(1-x_{i}t)^{-1}=1+h_{1}({\mathbf{x}})t+h_{2}({\mathbf{x}})t^{2}+\cdots=\sum_{n\geq
0}h_{n}({\mathbf{x}})t^{n}$ (2.25) $\displaystyle E(t)$
$\displaystyle:=\prod_{i=1}^{\infty}(1+x_{i}t)=1+e_{1}({\mathbf{x}})t+e_{2}({\mathbf{x}})t^{2}+\cdots=\sum_{n\geq
0}e_{n}({\mathbf{x}})t^{n}$

which shows that

(2.26) $1=E(-t)H(t)=\left(\sum_{n\geq
0}e_{n}({\mathbf{x}})(-t)^{n}\right)\left(\sum_{n\geq
0}h_{n}({\mathbf{x}})t^{n}\right)$

and hence, equating coefficients of powers of $t$, that for $n=0,1,2,\ldots$
one has

(2.27) $\sum_{i+j=n}(-1)^{i}e_{i}h_{j}=\delta_{0,n}.$

This lets one recursively express the $e_{n}$ in terms of $h_{n}$ and vice-
versa:

(2.28) $\displaystyle e_{0}$ $\displaystyle:=1=:h_{0}$ $\displaystyle e_{n}$
$\displaystyle=e_{n-1}h_{1}-e_{n-2}h_{2}+e_{n-3}h_{3}-\cdots$ $\displaystyle
h_{n}$ $\displaystyle=h_{n-1}e_{1}-h_{n-2}e_{2}+h_{n-3}e_{3}-\cdots$

for $n=1,2,\ldots$ Thus if one uses the algebraic independence of the
generators $\\{e_{n}\\}$ for $\Lambda$ to define an algebra endomorphism as
follows

(2.29) $\begin{array}[]{rcl}\Lambda&\overset{\omega}{\rightarrow}&\Lambda\\\
e_{n}&\longmapsto&h_{n},\end{array}$

then the identical form of the two recursions in (2.28) shows that $\omega$
also sends $h_{n}\mapsto e_{n}$. Therefore $\omega$ is an involutive
automorphism of $\Lambda$, and the $\\{h_{n}\\}$ are another algebraically
independent generating set for $\Lambda$.

For the assertion about the antipode $S$ applied to $e_{n}$ or $h_{n}$, note
that the coproduct formulas for $e_{n},h_{n}$ in Proposition 2.25(ii),(iii)
show that the defining relations for their antipodes (1.13) will in this case
be

$\displaystyle\sum_{i+j=n}S(e_{i})e_{j}$
$\displaystyle=\delta_{0,n}=\sum_{i+j=n}e_{i}S(e_{j})$
$\displaystyle\sum_{i+j=n}S(h_{i})h_{j}$
$\displaystyle=\delta_{0,n}=\sum_{i+j=n}h_{i}S(h_{j})$

because $u\epsilon(e_{n})=u\epsilon(h_{n})=\delta_{0,n}$. Comparing these to
(2.27), one concludes via induction on $n$ that $S(e_{n})=(-1)^{n}h_{n}$ and
$S(h_{n})=(-1)^{n}e_{n}$. ∎

The $\mathbf{k}$-algebra endomorphism $\omega$ of $\Lambda$ defined in the
proof of Proposition 2.29 is known as the fundamental involution on $\Lambda$.
We record for future use two results that were shown in the above proof: that
$\omega$ is an involution, and that it sends $e_{n}$ to $h_{n}$ and vice versa
for every positive integer $n$.

Proposition 2.29 shows that the antipode $S$ on $\Lambda$ is, up to sign, the
same as the fundamental involution $\omega$: one has

(2.30) $S(f)=(-1)^{n}\omega(f)\text{ for }f\in\Lambda_{n}$

since this formula holds for all elements of the generating set $\\{e_{n}\\}$
(or $\\{h_{n}\\}$).

######  Remark 2.30.

Up to now we have not yet derived how the involution $\omega$ and the antipode
$S$ act on (skew) Schur functions, which is quite beautiful: If $\lambda$ and
$\mu$ are partitions satisfying $\mu\subseteq\lambda$, then

(2.31) $\displaystyle\omega(s_{\lambda/\mu})$
$\displaystyle=s_{\lambda^{t}/\mu^{t}}$ $\displaystyle S(s_{\lambda/\mu})$
$\displaystyle=(-1)^{|\lambda/\mu|}s_{\lambda^{t}/\mu^{t}}$

where recall that $\lambda^{t}$ is the transpose or conjugate partition to
$\lambda$, and $|\lambda/\mu|$ is the number of squares in the skew diagram
$\lambda/\mu$, that is, $|\lambda/\mu|=n-k$ if $\lambda,\mu$ lie in
$\operatorname{Par}_{n},\operatorname{Par}_{k}$ respectively.

We will deduce this later in three ways (once as an exercise using the Pieri
rules in Exercise 2.70, once again using skewing operators in Exercise 2.77,
and for the third time from the action of the antipode in
$\operatorname{QSym}$ on $P$-partition enumerators in Corollary 5.29).
However, one could also deduce it immediately from our knowledge of the action
of $\omega$ and $S$ on $e_{n},h_{n}$, if we were to prove the following famous
Jacobi-Trudi and dual Jacobi-Trudi formulas707070The second of the following
identities is also known as the von Nägelsbach-Kostka identity.:

######  Theorem 2.31.

Skew Schur functions are the following polynomials in
$\\{h_{n}\\},\\{e_{n}\\}$:

(2.32) $\displaystyle s_{\lambda/\mu}$
$\displaystyle=\det(h_{\lambda_{i}-\mu_{j}-i+j})_{i,j=1,2,\ldots,\ell}$ (2.33)
$\displaystyle s_{\lambda^{t}/\mu^{t}}$
$\displaystyle=\det(e_{\lambda_{i}-\mu_{j}-i+j})_{i,j=1,2,\ldots,\ell}$

for any two partitions $\lambda$ and $\mu$ and any $\ell\in{\mathbb{N}}$
satisfying $\ell\left(\lambda\right)\leq\ell$ and
$\ell\left(\mu\right)\leq\ell$.

Since we appear not to need these formulas in the sequel, we will not prove
them right away. However, a proof is sketched in the solution to Exercise
2.72, and various proofs are well-explained in [100, (39) and (41)], [114,
§I.5], [146, Thm. 7.1], [148, §4.5], [164, §7.16], [176, Thms. 3.5 and 3.5∗];
also, a simultaneous generalization of both formulas is shown in [66, Theorem
11], and two others in [143, 1.9] and [68, Thm. 3.1]. An elegant treatment of
Schur polynomials taking the Jacobi-Trudi formula (2.32) as the definition of
$s_{\lambda}$ is given by Tamvakis [172].

###  2.5. Cauchy product, Hall inner product, self-duality

The Schur functions, although a bit unmotivated right now, have special
properties with regard to the Hopf structure. One property is intimately
connected with the following Cauchy identity.

######  Theorem 2.32.

In the power series ring
$\mathbf{k}\left[\left[{\mathbf{x}},{\mathbf{y}}\right]\right]:=\mathbf{k}\left[\left[x_{1},x_{2},\ldots,y_{1},y_{2},\ldots\right]\right]$,
one has the following expansion:

(2.34)
$\prod_{i,j=1}^{\infty}(1-x_{i}y_{j})^{-1}=\sum_{\lambda\in\operatorname{Par}}s_{\lambda}({\mathbf{x}})s_{\lambda}({\mathbf{y}}).$

######  Remark 2.33.

The left hand side of (2.34) is known as the Cauchy product, or Cauchy kernel.

An equivalent version of the equality (2.34) is obtained by replacing each
$x_{i}$ by $x_{i}t$, and writing the resulting identity in the power series
ring $R({\mathbf{x}},{\mathbf{y}})[[t]]$:

(2.35)
$\prod_{i,j=1}^{\infty}(1-tx_{i}y_{j})^{-1}=\sum_{\lambda\in\operatorname{Par}}t^{|\lambda|}s_{\lambda}({\mathbf{x}})s_{\lambda}({\mathbf{y}}).$

(Recall that $|\lambda|=\lambda_{1}+\lambda_{2}+\cdots+\lambda_{\ell}$ for any
partition
$\lambda=\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell}\right)$.)

###### Proof of Theorem 2.32.

We follow the standard combinatorial proof (see [148, §4.8],[164,
§7.11,7.12]), which rewrites the left and right sides of (2.35), and then
compares them with the Robinson-Schensted-Knuth (RSK) bijection.717171The RSK
bijection has been introduced by Knuth [89], where what we call “biletters” is
referred to as “two-line arrays”. The most important ingredient of this
algorithm – the RS-insertion operation – however goes back to Schensted. The
special case of the RSK algorithm where the biword has to be a permutation
(written in two-line notation) and the two tableaux have to be standard (i.e.,
each of them has content $\left(1^{n}\right)$, where $n$ is the size of their
shape) is the famous Robinson-Schensted correspondence [104]. More about these
algorithms can be found in [148, Chapter 3], [164, §7.11-7.12], [57, Chapters
1 and A], [26, §3, §6] and various other places. On the left side, expanding
out each geometric series

$(1-tx_{i}y_{j})^{-1}=1+tx_{i}y_{j}+(tx_{i}y_{j})^{2}+(tx_{i}y_{j})^{3}+\cdots$

and thinking of $(x_{i}y_{j})^{m}$ as $m$ occurrences of a biletter727272A
biletter here simply means a pair of letters, written as a column vector. A
letter means a positive integer. $\binom{i}{j}$, we see that the left hand
side can be rewritten as the sum of
$t^{\ell}\left(x_{i_{1}}y_{j_{1}}\right)\left(x_{i_{2}}y_{j_{2}}\right)\cdots\left(x_{i_{\ell}}y_{j_{\ell}}\right)$
over all multisets
$\left\\{\binom{i_{1}}{j_{1}},\ldots,\binom{i_{\ell}}{j_{\ell}}\right\\}$ of
biletters. Order the biletters in such a multiset in the lexicographic order
$\leq_{lex}$, which is the total order on the set of all biletters defined by

$\binom{i_{1}}{j_{1}}\leq_{lex}\binom{i_{2}}{j_{2}}\quad\Longleftrightarrow\quad\left(\text{we
have }i_{1}\leq i_{2}\text{, and if }i_{1}=i_{2}\text{, then }j_{1}\leq
j_{2}\right).$

Defining a biword to be an array
$\binom{{\mathbf{i}}}{{\mathbf{j}}}=\binom{i_{1}\cdots i_{\ell}}{j_{1}\cdots
j_{\ell}}$ in which the biletters are ordered
$\binom{i_{1}}{j_{1}}\leq_{lex}\cdots\leq_{lex}\binom{i_{\ell}}{j_{\ell}}$,
then the left side of (2.35) is the sum $\sum
t^{\ell}{\mathbf{x}}^{\operatorname{cont}({\mathbf{i}})}{\mathbf{y}}^{\operatorname{cont}({\mathbf{j}})}$
over all biwords $\binom{{\mathbf{i}}}{{\mathbf{j}}}$, where $\ell$ stands for
the number of biletters in the biword. On the right side, expanding out the
Schur functions as sums of tableaux gives
$\sum_{(P,Q)}t^{\ell}{\mathbf{x}}^{\operatorname{cont}(Q)}{\mathbf{y}}^{\operatorname{cont}(P)}$
in which the sum is over all ordered pairs $(P,Q)$ of column-strict tableaux
having the same shape737373And this shape should be the Ferrers diagram of a
partition (not just a skew partition)., with $\ell$ cells. (We shall refer to
such pairs as tableau pairs from now on.)

The Robinson-Schensted-Knuth algorithm gives us a bijection between the
biwords $\binom{{\mathbf{i}}}{{\mathbf{j}}}$ and the tableau pairs $(P,Q)$,
which has the property that

$\displaystyle\operatorname{cont}({\mathbf{i}})$
$\displaystyle=\operatorname{cont}(Q),$
$\displaystyle\operatorname{cont}({\mathbf{j}})$
$\displaystyle=\operatorname{cont}(P)$

(and that the length $\ell$ of the biword $\binom{{\mathbf{i}}}{{\mathbf{j}}}$
equals the size $\left|\lambda\right|$ of the common shape of $P$ and $Q$; but
this follows automatically from
$\operatorname{cont}({\mathbf{i}})=\operatorname{cont}(Q)$). Clearly, once
such a bijection is constructed, the equality (2.35) will follow.

Before we define this algorithm, we introduce a simpler operation known as RS-
insertion (short for Robinson-Schensted insertion). RS-insertion takes as
input a column-strict tableau $P$ and a letter $j$, and returns a new column-
strict tableau $P^{\prime}$ along with a corner cell747474A corner cell of a
tableau or a Ferrers diagram is defined to be a cell $c$ which belongs to the
tableau (resp. diagram) but whose immediate neighbors to the east and to the
south don’t. $c$ of $P^{\prime}$, which is constructed as follows: Start out
by setting $P^{\prime}=P$. The letter $j$ tries to insert itself into the
first row of $P^{\prime}$ by either bumping out the leftmost letter in the
first row strictly larger than $j$, or else placing itself at the right end of
the row if no such larger letter exists. If a letter was bumped from the first
row, this letter follows the same rules to insert itself into the second row,
and so on757575Here, rows are allowed to be empty – so it is possible that a
letter is bumped from the last nonempty row of $P^{\prime}$ and settles in the
next, initially empty, row.. This series of bumps must eventually come to an
end767676since we can only bump out entries from nonempty rows. At the end of
the bumping, the tableau $P^{\prime}$ created has an extra corner cell not
present in $P$. If we call this corner cell $c$, then $P^{\prime}$ (in its
final form) and $c$ are what the RS-insertion operation returns. One says that
$P^{\prime}$ is the result of inserting777777This terminology is reminiscent
of insertion into binary search trees, a basic operation in theoretical
computer science. This is more than superficial similarity; there are, in
fact, various analogies between Ferrers diagrams (and their fillings) and
unlabelled plane binary trees (resp. their labellings), and one of them is the
analogy between RS-insertion and binary search tree insertion. See [76, §4.1].
$c$ into the tableau $P$. It is straightforward to see that this resulting
filling $P^{\prime}$ is a column-strict tableau787878Indeed, the reader can
check that $P^{\prime}$ remains a column-strict tableau throughout the
algorithm that defines RS-insertion. (The only part of this that isn’t obvious
is showing that when a letter $t$ bumped out of some row $k$ is inserted into
row $k+1$, the property that the letters increase strictly down columns is
preserved. Argue that the bumping-out of $t$ from row $k$ was caused by the
insertion of another letter $u<t$, and that the cell of row $k+1$ into which
$t$ is then being inserted is in the same column as this $u$, or in a column
further left than it.).

######  Example 2.34.

To give an example of this operation, let us insert the letter $j=3$ into the
column-strict tableau $\begin{matrix}1&1&3&3&4\\\ 2&2&4&6&\\\ 3&4&7&&\\\
5&&&&\end{matrix}$ (we are showing all intermediate states of $P^{\prime}$;
the underlined letter is always the one that is going to be bumped out at the
next step):

$\displaystyle\begin{matrix}1&1&3&3&\underline{4}\\\ 2&2&4&6&\\\ 3&4&7&&\\\
5&&&&\end{matrix}\quad$
$\displaystyle\overset{\longmapsto}{\begin{subarray}{c}\text{insert 3;}\\\
\text{bump out 4}\end{subarray}}\quad\begin{matrix}1&1&3&3&3\\\
2&2&4&\underline{6}&\\\ 3&4&7&&\\\
5&&&&\end{matrix}\quad\overset{\longmapsto}{\begin{subarray}{c}\text{insert
4;}\\\ \text{bump out 6}\end{subarray}}\quad\begin{matrix}1&1&3&3&3\\\
2&2&4&4&\\\ 3&4&\underline{7}&&\\\ 5&&&&\end{matrix}$
$\displaystyle\overset{\longmapsto}{\begin{subarray}{c}\text{insert 6;}\\\
\text{bump out 7}\end{subarray}}\quad\begin{matrix}1&1&3&3&3\\\ 2&2&4&4&\\\
3&4&6&&\\\
5&&&&\end{matrix}\quad\overset{\longmapsto}{\begin{subarray}{c}\text{insert
7;}\\\ \text{done}\end{subarray}}\quad\begin{matrix}1&1&3&3&3\\\ 2&2&4&4&\\\
3&4&6&&\\\ 5&7&&&\end{matrix}.$

The last tableau in this sequence is the column-strict tableau that is
returned. The corner cell that is returned is the second cell of the fourth
row (the one containing $7$).

RS-insertion will be used as a step in the RSK algorithm; the construction
will rely on a simple fact known as the row bumping lemma. Let us first define
the notion of a bumping path (or bumping route): If $P$ is a column-strict
tableau, and $j$ is a letter, then some letters are inserted into some cells
when RS-insertion is applied to $P$ and $j$. The sequence of these cells (in
the order in which they see letters inserted into them) is called the bumping
path for $P$ and $j$. This bumping path always ends with the corner cell $c$
which is returned by RS-insertion. As an example, when $j=1$ is inserted into
the tableau $P$ shown below, the result $P^{\prime}$ is shown with all entries
on the bumping path underlined:

$P=\begin{matrix}1&1&2&2&3\\\ 2&2&4&4&\\\ 3&4&5&&\\\
4&6&6&&\end{matrix}\qquad\underset{j=1}{\overset{\text{insert}}{\longmapsto}}\qquad
P^{\prime}=\begin{matrix}1&1&\underline{1}&2&3\\\ 2&2&\underline{2}&4&\\\
3&4&\underline{4}&&\\\ 4&\underline{5}&6&&\\\ \underline{6}&&&&\end{matrix}$

A first simple observation about bumping paths is that bumping paths trend
weakly left – that is, if the bumping path of $P$ and $j$ is
$\left(c_{1},c_{2},\ldots,c_{k}\right)$, then, for each $1\leq i<k$, the cell
$c_{i+1}$ lies in the same column as $c_{i}$ or in a column further
left.797979This follows easily from the preservation of column-strictness
during RS-insertion. A subtler property of bumping paths is the following row
bumping lemma ([57, p. 9]):

> Row bumping lemma: Let $P$ be a column-strict tableau, and let $j$ and
> $j^{\prime}$ be two letters. Applying RS-insertion to the tableau $P$ and
> the letter $j$ yields a new column-strict tableau $P^{\prime}$ and a corner
> cell $c$. Applying RS-insertion to the tableau $P^{\prime}$ and the letter
> $j^{\prime}$ yields a new column-strict tableau $P^{\prime\prime}$ and a
> corner cell $c^{\prime}$.
>
>   1. (a)
>
> Assume that $j\leq j^{\prime}$. Then, the bumping path for $P^{\prime}$ and
> $j^{\prime}$ stays strictly to the right, within each row, of the bumping
> path for $P$ and $j$. The cell $c^{\prime}$ (in which the bumping path for
> $P^{\prime}$ and $j^{\prime}$ ends) is in the same row as the cell $c$ (in
> which the bumping path for $P$ and $j$ ends) or in a row further up; it is
> also in a column further right than $c$.
>
>   2. (b)
>
> Assume instead that $j>j^{\prime}$. Then, the bumping path for $P^{\prime}$
> and $j^{\prime}$ stays weakly to the left, within each row, of the bumping
> path for $P$ and $j$. The cell $c^{\prime}$ (in which the bumping path for
> $P^{\prime}$ and $j^{\prime}$ ends) is in a row further down than the cell
> $c$ (in which the bumping path for $P$ and $j$ ends); it is also in the same
> column as $c$ or in a column further left.
>
>

This lemma can be easily proven by induction over the row.808080We leave the
details to the reader, only giving the main idea for (a) (the proof of (b) is
similar). To prove the first claim of (a), it is enough to show that for every
$i$, if any letter is inserted into row $i$ during RS-insertion for
$P^{\prime}$ and $j^{\prime}$, then some letter is also inserted into row $i$
during RS-insertion for $P$ and $j$, and the former insertion happens in a
cell strictly to the right of the cell where the latter insertion happens.
This follows by induction over $i$. In the induction step, we need to show
that if, for a positive integer $i$, we try to consecutively insert two
letters $k$ and $k^{\prime}$, in this order, into the $i$-th row of a column-
strict tableau, possibly bumping out existing letters in the process, and if
we have $k\leq k^{\prime}$, then the cell into which $k$ is inserted is
strictly to the left of the cell into which $k^{\prime}$ is inserted, and the
letter bumped out by the insertion of $k$ is $\leq$ to the letter bumped out
by the insertion of $k^{\prime}$ (or else the insertion of $k^{\prime}$ bumps
out no letter at all – but it cannot happen that $k^{\prime}$ bumps out a
letter but $k$ does not). This statement is completely straightforward to
check (by only studying the $i$-th row). This way, the first claim of (a) is
proven, and this entails that the cell $c^{\prime}$ (being the last cell of
the bumping path for $P^{\prime}$ and $j^{\prime}$) is in the same row as the
cell $c$ or in a row further up. It only remains to show that $c^{\prime}$ is
in a column further right than $c$. This follows by noticing that, if $k$ is
the row in which the cell $c^{\prime}$ lies, then $c^{\prime}$ is in a column
further right than the entry of the bumping path for $P$ and $j$ in row $k$
(by the first claim of (a)), and this latter entry is further right than or in
the same column as the ultimate entry $c$ of this bumping path (since bumping
paths trend weakly left).

We can now define the actual RSK algorithm. Let
$\binom{{\mathbf{i}}}{{\mathbf{j}}}$ be a biword. Starting with the pair
$(P_{0},Q_{0})=(\varnothing,\varnothing)$ and $m=0$, the algorithm applies the
following steps (see Example 2.35 below):

  * •

If $i_{m+1}$ does not exist (that is, $m$ is the length of ${\mathbf{i}}$),
stop.

  * •

Apply RS-insertion to the column-strict tableau $P_{m}$ and the letter
$j_{m+1}$ (the bottom letter of $\binom{i_{m+1}}{j_{m+1}}$). Let $P_{m+1}$ be
the resulting column-strict tableau, and let $c_{m+1}$ be the resulting corner
cell.

  * •

Create $Q_{m+1}$ from $Q_{m}$ by adding the top letter $i_{m+1}$ of
$\binom{i_{m+1}}{j_{m+1}}$ to $Q_{m}$ in the cell $c_{m+1}$ (which, as we
recall, is the extra corner cell of $P_{m+1}$ not present in $P_{m}$).

  * •

Set $m$ to $m+1$.

After all of the biletters have been thus processed, the result of the RSK
algorithm is $(P_{\ell},Q_{\ell})=:(P,Q)$.

######  Example 2.35.

The term in the expansion of the left side of (2.34) corresponding to

$(x_{1}y_{2})^{1}(x_{1}y_{4})^{1}(x_{2}y_{1})^{1}(x_{4}y_{1})^{1}(x_{4}y_{3})^{2}(x_{5}y_{2})^{1}$

is the biword $\binom{{\mathbf{i}}}{{\mathbf{j}}}=\binom{1124445}{2411332}$,
whose RSK algorithm goes as follows:

$\begin{array}[]{rcl|rcl}P_{0}&=&\varnothing&Q_{0}&=&\varnothing\\\ &&&&&\\\
P_{1}&=&\begin{matrix}2\end{matrix}&Q_{1}&=&\begin{matrix}1\end{matrix}\\\
&&&&&\\\
P_{2}&=&\begin{matrix}2&4\end{matrix}&Q_{2}&=&\begin{matrix}1&1\end{matrix}\\\
&&&&&\\\ P_{3}&=&\begin{matrix}1&4\\\
2\end{matrix}&Q_{3}&=&\begin{matrix}1&1\\\ 2\end{matrix}\\\ &&&&&\\\
P_{4}&=&\begin{matrix}1&1\\\ 2&4\end{matrix}&Q_{4}&=&\begin{matrix}1&1\\\
2&4\end{matrix}\\\ &&&&&\\\ P_{5}&=&\begin{matrix}1&1&3\\\
2&4&\end{matrix}&Q_{5}&=&\begin{matrix}1&1&4\\\ 2&4&\end{matrix}\\\ &&&&&\\\
P_{6}&=&\begin{matrix}1&1&3&3\\\
2&4&&\end{matrix}&Q_{6}&=&\begin{matrix}1&1&4&4\\\ 2&4&&\end{matrix}\\\
&&&&&\\\ P:=P_{7}&=&\begin{matrix}1&1&2&3\\\ 2&3&&\\\
4&&&\end{matrix}&Q:=Q_{7}&=&\begin{matrix}1&1&4&4\\\ 2&4&&\\\
5&&&\end{matrix}\\\ \end{array}$

The bumping rule obviously maintains the property that $P_{m}$ is a column-
strict tableau of some Ferrers shape throughout. It should be clear that
$(P_{m},Q_{m})$ have the same shape at each stage. Also, the construction of
$Q_{m}$ shows that it is at least weakly increasing in rows and weakly
increasing in columns throughout. What is perhaps least clear is that $Q_{m}$
remains strictly increasing down columns. That is, when one has a string of
equal letters on top $i_{m}=i_{m+1}=\cdots=i_{m+r}$, so that on bottom one
bumps in $j_{m}\leq j_{m+1}\leq\cdots\leq j_{m+r}$, one needs to know that the
new cells form a horizontal strip, that is, no two of them lie in the same
column818181Actually, each of these new cells (except for the first one) is in
a column further right than the previous one. We will use this stronger fact
further below.. This follows from (the last claim of) part (a) of the row
bumping lemma. Hence, the result $\left(P,Q\right)$ of the RSK algorithm is a
tableau pair.

To see that the RSK map is a bijection, we show how to recover
$\binom{{\mathbf{i}}}{{\mathbf{j}}}$ from $(P,Q)$. This is done by reverse
bumping from $(P_{m+1},Q_{m+1})$ to recover both the biletter
$\binom{i_{m+1}}{j_{m+1}}$ and the tableaux $(P_{m},Q_{m})$, as follows.
Firstly, $i_{m+1}$ is the maximum entry of $Q_{m+1}$, and $Q_{m}$ is obtained
by removing the rightmost occurrence of this letter $i_{m+1}$ from $Q_{m+1}$.
828282It necessarily has to be the rightmost occurrence, since (according to
the previous footnote) the cell into which $i_{m+1}$ was filled at the step
from $Q_{m}$ to $Q_{m+1}$ lies further right than any existing cell of $Q_{m}$
containing the letter $i_{m+1}$. To produce $P_{m}$ and $j_{m+1}$, find the
position of the rightmost occurrence of $i_{m+1}$ in $Q_{m+1}$, and start
reverse bumping in $P_{m+1}$ from the entry in this same position, where
reverse bumping an entry means inserting it into one row higher by having it
bump out the rightmost entry which is strictly smaller.838383Let us give a few
more details on this “reverse bumping” procedure. Reverse bumping (also known
as RS-deletion or reverse RS-insertion) is an operation which takes a column-
strict tableau $P^{\prime}$ and a corner cell $c$ of $P^{\prime}$, and
constructs a column-strict tableau $P$ and a letter $j$ such that RS-insertion
for $P$ and $j$ yields $P^{\prime}$ and $c$. It starts by setting
$P=P^{\prime}$, and removing the entry in the cell $c$ from $P$. This removed
entry is then denoted by $k$, and is inserted into the row of $P$ above $c$,
bumping out the rightmost entry which is smaller than $k$. The letter which is
bumped out – say, $\ell$ –, in turn, is inserted into the row above it,
bumping out the rightmost entry which is smaller than $\ell$. This procedure
continues in the same way until an entry is bumped out of the first row (which
will eventually happen). The reverse bumping operation returns the resulting
tableau $P$ and the entry which is bumped out of the first row. It is
straightforward to check that the reverse bumping operation is well-defined
(i.e., $P$ does stay a column-strict tableau throughout the procedure) and is
the inverse of the RS-insertion operation. (In fact, these two operations undo
each other step by step.) The entry bumped out of the first row is $j_{m+1}$,
and the resulting tableau is $P_{m}$.

Finally, to see that the RSK map is surjective, one needs to show that the
reverse bumping procedure can be applied to any pair $(P,Q)$ of column-strict
tableaux of the same shape, and will result in a (lexicographically ordered)
biword $\binom{{\mathbf{i}}}{{\mathbf{j}}}$. We leave this verification to the
reader.848484It is easy to see that repeatedly applying reverse bumping to
$(P,Q)$ will result in a sequence
$\binom{i_{\ell}}{j_{\ell}},\binom{i_{\ell-1}}{j_{\ell-1}},\ldots,\binom{i_{1}}{j_{1}}$
of biletters such that applying the RSK algorithm to $\binom{i_{1}\cdots
i_{\ell}}{j_{1}\cdots j_{\ell}}$ gives back $(P,Q)$. The question is why we
have
$\binom{i_{1}}{j_{1}}\leq_{lex}\cdots\leq_{lex}\binom{i_{\ell}}{j_{\ell}}$.
Since the chain of inequalities $i_{1}\leq i_{2}\leq\cdots\leq i_{\ell}$ is
clear from the choice of entry to reverse-bump, it only remains to show that
for every string $i_{m}=i_{m+1}=\cdots=i_{m+r}$ of equal top letters, the
corresponding bottom letters weakly increase (that is, $j_{m}\leq
j_{m+1}\leq\cdots\leq j_{m+r}$). One way to see it is to apply part (b) of the
row bumping lemma. ∎

This is by far not the only known proof of Theorem 2.32. Two further proofs
will be sketched in Exercise 2.69 and Exercise 2.67.

######  Corollary 2.36.

In the Schur function basis $\\{s_{\lambda}\\}$ for $\Lambda$, the structure
constants for multiplication and comultiplication are the same, that is, if
one defines $c^{\lambda}_{\mu,\nu},\hat{c}^{\lambda}_{\mu,\nu}$ via the unique
expansions

(2.36) $\displaystyle s_{\mu}s_{\nu}$
$\displaystyle=\sum_{\lambda}c^{\lambda}_{\mu,\nu}s_{\lambda}$
$\displaystyle\Delta(s_{\lambda})$
$\displaystyle=\sum_{\mu,\nu}\hat{c}^{\lambda}_{\mu,\nu}s_{\mu}\otimes
s_{\nu}$

then $c^{\lambda}_{\mu,\nu}=\hat{c}^{\lambda}_{\mu,\nu}$.

###### Proof.

Work in the ring
$\mathbf{k}\left[\left[{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}\right]\right]$,
where ${\mathbf{y}}=\left(y_{1},y_{2},y_{3},\ldots\right)$ and
${\mathbf{z}}=\left(z_{1},z_{2},z_{3},\ldots\right)$ are two new sets of
variables. The identity (2.34) lets one interpret both
$c^{\lambda}_{\mu,\nu},\hat{c}^{\lambda}_{\mu,\nu}$ as the
coefficient858585Speaking of coefficients makes sense here since
$\Lambda\left({\mathbf{x}}\right)\otimes\Lambda\left({\mathbf{y}}\right)\otimes\Lambda\left({\mathbf{z}}\right)$
embeds into
$\mathbf{k}\left[\left[{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}\right]\right]$.
of $s_{\mu}({\mathbf{x}})s_{\nu}({\mathbf{y}})s_{\lambda}({\mathbf{z}})$ in
the product

$\displaystyle\prod_{i,j=1}^{\infty}(1-x_{i}z_{j})^{-1}\prod_{i,j=1}^{\infty}(1-y_{i}z_{j})^{-1}$
$\displaystyle\overset{\eqref{Cauchy-
identity}}{=}\left(\sum_{\mu}s_{\mu}({\mathbf{x}})s_{\mu}({\mathbf{z}})\right)\left(\sum_{\nu}s_{\nu}({\mathbf{y}})s_{\nu}({\mathbf{z}})\right)$
$\displaystyle=\sum_{\mu,\nu}s_{\mu}({\mathbf{x}})s_{\nu}({\mathbf{y}})\cdot
s_{\mu}({\mathbf{z}})s_{\nu}({\mathbf{z}})$
$\displaystyle=\sum_{\mu,\nu}s_{\mu}({\mathbf{x}})s_{\nu}({\mathbf{y}})\left(\sum_{\lambda}c^{\lambda}_{\mu,\nu}s_{\lambda}({\mathbf{z}})\right)$

since, regarding $x_{1},x_{2},\ldots,y_{1},y_{2},\ldots$ as lying in a single
variable set $({\mathbf{x}},{\mathbf{y}})$, separate from the variables
${\mathbf{z}}$, the Cauchy identity (2.34) expands the same product as

$\displaystyle\prod_{i,j=1}^{\infty}(1-x_{i}z_{j})^{-1}\prod_{i,j=1}^{\infty}(1-y_{i}z_{j})^{-1}$
$\displaystyle=\sum_{\lambda}s_{\lambda}({\mathbf{x}},{\mathbf{y}})s_{\lambda}({\mathbf{z}})$
$\displaystyle=\sum_{\lambda}\left(\sum_{\mu,\nu}\hat{c}^{\lambda}_{\mu,\nu}s_{\mu}({\mathbf{x}})s_{\nu}({\mathbf{y}})\right)s_{\lambda}({\mathbf{z}}).$

∎

######  Definition 2.37.

The coefficients $c^{\lambda}_{\mu,\nu}=\hat{c}^{\lambda}_{\mu,\nu}$ appearing
in the expansions (2.36) are called Littlewood-Richardson coefficients.

######  Remark 2.38.

We will interpret $c^{\lambda}_{\mu,\nu}$ combinatorially in Section 2.6. By
now, however, we can already prove some properties of these coefficients:

We have

(2.37) $c^{\lambda}_{\mu,\nu}=c^{\lambda}_{\nu,\mu}\qquad\qquad\text{ for all
}\lambda,\mu,\nu\in\operatorname{Par}$

(by comparing coefficients in
$\sum_{\lambda}c^{\lambda}_{\mu,\nu}s_{\lambda}=s_{\mu}s_{\nu}=s_{\nu}s_{\mu}=\sum_{\lambda}c^{\lambda}_{\nu,\mu}s_{\lambda}$).
Also, noting on one hand the expansion

$s_{\lambda}({\mathbf{x}},{\mathbf{y}})=\Delta(s_{\lambda})=\sum_{\mu,\nu}c^{\lambda}_{\mu,\nu}s_{\mu}({\mathbf{x}})s_{\nu}({\mathbf{y}})$

and on the other hand

$s_{\lambda}({\mathbf{x}},{\mathbf{y}})=\sum_{\mu\subseteq\lambda}s_{\mu}({\mathbf{x}})s_{\lambda/\mu}({\mathbf{y}})=\sum_{\mu\in\operatorname{Par}}s_{\mu}({\mathbf{x}})s_{\lambda/\mu}({\mathbf{y}})$
868686In the last equality, we removed the condition $\mu\subseteq\lambda$ on
the addends of the sum; this does not change the value of the sum (because we
have $s_{\lambda/\mu}=0$ whenever we don’t have $\mu\subseteq\lambda$).

one concludes another standard interpretation for $c^{\lambda}_{\mu,\nu}$:

$s_{\lambda/\mu}=\sum_{\nu}c^{\lambda}_{\mu,\nu}s_{\nu}$

whenever $\lambda$ and $\mu$ are two partitions (not necessarily satisfying
$\mu\subseteq\lambda$). In particular, $c^{\lambda}_{\mu,\nu}$ vanishes unless
$\mu\subseteq\lambda$. Consequently, $c^{\lambda}_{\mu,\nu}$ vanishes unless
$\nu\subseteq\lambda$ as well (since
$c^{\lambda}_{\mu,\nu}=c^{\lambda}_{\nu,\mu}$) and furthermore vanishes unless
the equality $\left|\mu\right|+\left|\nu\right|=\left|\lambda\right|$
holds878787In fact, this is clear when we don’t have $\mu\subseteq\lambda$.
When we do have $\mu\subseteq\lambda$, this follows from observing that
$s_{\lambda/\mu}\in\Lambda_{\left|\lambda/\mu\right|}$ has zero coefficient
before $s_{\nu}$ whenever
$\left|\mu\right|+\left|\nu\right|\neq\left|\lambda\right|$.. Altogether, we
conclude that $c^{\lambda}_{\mu,\nu}$ vanishes unless
$\mu,\nu\subseteq\lambda$ and $|\mu|+|\nu|=|\lambda|$.

######  Exercise 2.39.

Show that any four partitions $\kappa$, $\lambda$, $\varphi$ and $\psi$
satisfy

$\sum_{\rho\in\operatorname{Par}}c^{\rho}_{\kappa,\lambda}c^{\rho}_{\varphi,\psi}=\sum_{\left(\alpha,\beta,\gamma,\delta\right)\in\operatorname{Par}^{4}}c^{\lambda}_{\beta,\delta}c^{\varphi}_{\alpha,\beta}c^{\psi}_{\gamma,\delta}.$

######  Exercise 2.40.

  * (a)

For any partition $\mu$, prove that

$\sum_{\lambda\in\operatorname{Par}}s_{\lambda}\left({\mathbf{x}}\right)s_{\lambda/\mu}\left({\mathbf{y}}\right)=s_{\mu}\left({\mathbf{x}}\right)\cdot\prod_{i,j=1}^{\infty}\left(1-x_{i}y_{j}\right)^{-1}$

in the power series ring
$\mathbf{k}\left[\left[{\mathbf{x}},{\mathbf{y}}\right]\right]=\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots,y_{1},y_{2},y_{3},\ldots\right]\right]$.

  * (b)

Let $\alpha$ and $\beta$ be two partitions. Show that

$\sum_{\lambda\in\operatorname{Par}}s_{\lambda/\alpha}\left({\mathbf{x}}\right)s_{\lambda/\beta}\left({\mathbf{y}}\right)=\left(\sum_{\rho\in\operatorname{Par}}s_{\beta/\rho}\left({\mathbf{x}}\right)s_{\alpha/\rho}\left({\mathbf{y}}\right)\right)\cdot\prod_{i,j=1}^{\infty}\left(1-x_{i}y_{j}\right)^{-1}$

in the power series ring
$\mathbf{k}\left[\left[{\mathbf{x}},{\mathbf{y}}\right]\right]=\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots,y_{1},y_{2},y_{3},\ldots\right]\right]$.

[Hint: For (b), expand the product

$\prod_{i,j=1}^{\infty}\left(1-x_{i}y_{j}\right)^{-1}\prod_{i,j=1}^{\infty}\left(1-x_{i}w_{j}\right)^{-1}\prod_{i,j=1}^{\infty}\left(1-z_{i}y_{j}\right)^{-1}\prod_{i,j=1}^{\infty}\left(1-z_{i}w_{j}\right)^{-1}$

in the power series ring
$\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots,y_{1},y_{2},y_{3},\ldots,z_{1},z_{2},z_{3},\ldots,w_{1},w_{2},w_{3},\ldots\right]\right]$
in two ways: once by applying Theorem 2.32 to the two variable sets
$\left({\mathbf{z}},{\mathbf{x}}\right)$ and
$\left(\mathbf{w},{\mathbf{y}}\right)$ and then using (2.23); once again by
applying (2.34) to the two variable sets ${\mathbf{z}}$ and $\mathbf{w}$ and
then applying Exercise 2.40(a) twice.]

The statement of Exercise 2.40(b) is known as the skew Cauchy identity, and
appears in Sagan-Stanley [149, Cor. 6.12], Stanley [164, exercise 7.27(c)] and
Macdonald [114, §I.5, example 26]; it seems to be due to Zelevinsky. It
generalizes the statement of Exercise 2.40(a), which in turn is a
generalization of Theorem 2.32.

######  Definition 2.41.

Define the Hall inner product on $\Lambda$ to be the $\mathbf{k}$-bilinear
form $(\cdot,\cdot)$ which makes $\\{s_{\lambda}\\}$ an orthonormal basis,
that is, $(s_{\lambda},s_{\nu})=\delta_{\lambda,\nu}$.

######  Exercise 2.42.

  * (a)

If $n$ and $m$ are two distinct nonnegative integers, and if $f\in\Lambda_{n}$
and $g\in\Lambda_{m}$, then show that $\left(f,g\right)=0$.

  * (b)

If $n\in{\mathbb{N}}$ and $f\in\Lambda_{n}$, then prove that
$\left(h_{n},f\right)=f\left(1\right)$ (where $f\left(1\right)$ is defined as
in Exercise 2.2).

The Hall inner product induces a $\mathbf{k}$-module homomorphism
$\Lambda\to\Lambda^{o}$ (sending every $f\in\Lambda$ to the
$\mathbf{k}$-linear map $\Lambda\to\mathbf{k},\ g\mapsto\left(f,g\right)$).
This homomorphism is invertible (since the Hall inner product has an
orthonormal basis), so that $\Lambda^{o}\cong\Lambda$ as $\mathbf{k}$-modules.
But in fact, more can be said:

######  Corollary 2.43.

The isomorphism $\Lambda^{o}\cong\Lambda$ induced by the Hall inner product is
an isomorphism of Hopf algebras.

###### Proof.

We have seen that the orthonormal basis $\\{s_{\lambda}\\}$ of Schur functions
is self-dual, in the sense that its multiplication and comultiplication
structure constants are the same. Thus the isomorphism
$\Lambda^{o}\cong\Lambda$ induced by the Hall inner product is an isomorphism
of bialgebras, and hence also a Hopf algebra isomorphism by Proposition
1.46(c). ∎

We next identify two other dual pairs of bases, by expanding the Cauchy
product in two other ways.

######  Proposition 2.44.

One can also expand

(2.38)
$\prod_{i,j=1}^{\infty}(1-x_{i}y_{j})^{-1}=\sum_{\lambda\in\operatorname{Par}}h_{\lambda}({\mathbf{x}})m_{\lambda}({\mathbf{y}})=\sum_{\lambda\in\operatorname{Par}}z_{\lambda}^{-1}p_{\lambda}({\mathbf{x}})p_{\lambda}({\mathbf{y}})$

where $z_{\lambda}:=m_{1}!\cdot 1^{m_{1}}\cdot m_{2}!\cdot 2^{m_{2}}\cdots$ if
$\lambda=(1^{m_{1}},2^{m_{2}},\ldots)$ with multiplicity $m_{i}$ for the part
$i$. (Here, we assume that ${\mathbb{Q}}$ is a subring of $\mathbf{k}$ for the
last equality.)

######  Remark 2.45.

It is relevant later (and explains the notation) that $z_{\lambda}$ is the
size of the $\mathfrak{S}_{n}$-centralizer subgroup for a permutation having
cycle type888888If $\sigma$ is a permutation of a finite set $X$, then the
cycle type of $\sigma$ is defined as the list of the lengths of all cycles of
$\sigma$ (that is, of all orbits of $\sigma$ acting on $X$) written in
decreasing order. This is clearly a partition of $\left|X\right|$. (Some other
authors write it in increasing order instead, or treat it as a multiset.) For
instance, the permutation of the set $\left\\{0,3,6,9,12\right\\}$ which sends
$0$ to $3$, $3$ to $9$, $6$ to $6$, $9$ to $0$, and $12$ to $12$ is
$\left(3,1,1\right)$, since the cycles of this permutation have lengths $3$,
$1$ and $1$. It is known that two permutations in $\mathfrak{S}_{n}$ have the
same cycle type if and only if they are conjugate. Thus, for a given partition
$\lambda$ with $\left|\lambda\right|=n$, any two permutations in
$\mathfrak{S}_{n}$ having cycle type $\lambda$ are conjugate and therefore
their $\mathfrak{S}_{n}$-centralizer subgroups have the same size. $\lambda$
with $|\lambda|=n$. This is a classical (and fairly easy) result (see, e.g.,
[148, Prop. 1.1.1] or [164, Prop. 7.7.3] for a proof).

###### Proof of Proposition 2.44..

For the first expansion, note that (2.24) shows

$\displaystyle\prod_{i,j=1}^{\infty}(1-x_{i}y_{j})^{-1}$
$\displaystyle=\prod_{j=1}^{\infty}\sum_{n\geq 0}h_{n}({\mathbf{x}})y_{j}^{n}$
$\displaystyle=\sum_{\begin{subarray}{c}\text{weak }\\\ \text{ compositions
}\\\
(n_{1},n_{2},\ldots)\end{subarray}}(h_{n_{1}}({\mathbf{x}})h_{n_{2}}({\mathbf{x}})\cdots)(y_{1}^{n_{1}}y_{2}^{n_{2}}\cdots)$
$\displaystyle=\sum_{\lambda\in\operatorname{Par}}\sum_{\begin{subarray}{c}\text{weak
}\\\ \text{ compositions }\\\ (n_{1},n_{2},\ldots)\\\ \text{ satisfying }\\\
(n_{1},n_{2},\ldots)\in\mathfrak{S}_{(\infty)}\lambda\end{subarray}}\underbrace{(h_{n_{1}}({\mathbf{x}})h_{n_{2}}({\mathbf{x}})\cdots)}_{\begin{subarray}{c}=h_{\lambda}({\mathbf{x}})\\\
\text{ (since
}(n_{1},n_{2},\ldots)\in\mathfrak{S}_{(\infty)}\lambda\text{)}\end{subarray}}\underbrace{(y_{1}^{n_{1}}y_{2}^{n_{2}}\cdots)}_{={\mathbf{y}}^{(n_{1},n_{2},\ldots)}}$
$\displaystyle=\sum_{\lambda\in\operatorname{Par}}h_{\lambda}({\mathbf{x}})\underbrace{\sum_{\begin{subarray}{c}\text{weak
}\\\ \text{ compositions }\\\ (n_{1},n_{2},\ldots)\\\ \text{ satisfying }\\\
(n_{1},n_{2},\ldots)\in\mathfrak{S}_{(\infty)}\lambda\end{subarray}}{\mathbf{y}}^{(n_{1},n_{2},\ldots)}}_{=m_{\lambda}({\mathbf{y}})}$
$\displaystyle=\sum_{\lambda\in\operatorname{Par}}h_{\lambda}({\mathbf{x}})m_{\lambda}({\mathbf{y}}).$

For the second expansion (and for later use in the proof of Theorem 4.59) note
that

(2.39) $\log
H(t)=\log\prod_{i=1}^{\infty}(1-x_{i}t)^{-1}=\sum_{i=1}^{\infty}-\log(1-x_{i}t)=\sum_{i=1}^{\infty}\sum_{m=1}^{\infty}\frac{(x_{i}t)^{m}}{m}=\sum_{m=1}^{\infty}\frac{1}{m}p_{m}({\mathbf{x}})t^{m}$

so that taking $\frac{d}{dt}$ then shows that

(2.40) $P(t):=\sum_{m\geq
0}p_{m+1}t^{m}=\frac{H^{\prime}(t)}{H(t)}=H^{\prime}(t)E(-t).$

A similar calculation shows that

(2.41)
$\log\prod_{i,j=1}^{\infty}(1-x_{i}y_{j})^{-1}=\sum_{m=1}^{\infty}\frac{1}{m}p_{m}({\mathbf{x}})p_{m}({\mathbf{y}})$

and hence

$\displaystyle\prod_{i,j=1}^{\infty}(1-x_{i}y_{j})^{-1}=\exp\left(\sum_{m=1}^{\infty}\frac{1}{m}p_{m}({\mathbf{x}})p_{m}({\mathbf{y}})\right)=\prod_{m=1}^{\infty}\exp\left(\frac{1}{m}p_{m}({\mathbf{x}})p_{m}({\mathbf{y}})\right)$
$\displaystyle=\prod_{m=1}^{\infty}\sum_{k=0}^{\infty}\frac{1}{k!}\left(\frac{1}{m}p_{m}({\mathbf{x}})p_{m}({\mathbf{y}})\right)^{k}=\sum_{\begin{subarray}{c}\text{weak
compositions }\\\
\left(k_{1},k_{2},k_{3},\ldots\right)\end{subarray}}\prod_{m=1}^{\infty}\left(\frac{1}{k_{m}!}\left(\frac{1}{m}p_{m}({\mathbf{x}})p_{m}({\mathbf{y}})\right)^{k_{m}}\right)$
$\displaystyle\qquad\qquad\left(\text{by the product rule}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}\text{weak compositions }\\\
\left(k_{1},k_{2},k_{3},\ldots\right)\end{subarray}}\prod_{m=1}^{\infty}\frac{\left(p_{m}({\mathbf{x}})p_{m}({\mathbf{y}})\right)^{k_{m}}}{k_{m}!m^{k_{m}}}=\sum_{\begin{subarray}{c}\text{weak
compositions }\\\
\left(k_{1},k_{2},k_{3},\ldots\right)\end{subarray}}\frac{\prod_{m=1}^{\infty}\left(p_{m}({\mathbf{x}})\right)^{k_{m}}\prod_{m=1}^{\infty}\left(p_{m}({\mathbf{y}})\right)^{k_{m}}}{\prod_{m=1}^{\infty}\left(k_{m}!m^{k_{m}}\right)}$
$\displaystyle=\sum_{\begin{subarray}{c}\text{weak compositions }\\\
\left(k_{1},k_{2},k_{3},\ldots\right)\end{subarray}}\frac{p_{\left(1^{k_{1}}2^{k_{2}}3^{k_{3}}\cdots\right)}\left({\mathbf{x}}\right)p_{\left(1^{k_{1}}2^{k_{2}}3^{k_{3}}\cdots\right)}\left({\mathbf{y}}\right)}{z_{\left(1^{k_{1}}2^{k_{2}}3^{k_{3}}\cdots\right)}}=\sum_{\lambda\in\operatorname{Par}}\frac{p_{\lambda}({\mathbf{x}})p_{\lambda}({\mathbf{y}})}{z_{\lambda}}$

due to the fact that every partition can be uniquely written in the form
$\left(1^{k_{1}}2^{k_{2}}3^{k_{3}}\cdots\right)$ with
$\left(k_{1},k_{2},k_{3},\ldots\right)$ a weak composition. ∎

######  Corollary 2.46.

  * (a)

With respect to the Hall inner product on $\Lambda$, one also has dual bases
$\\{h_{\lambda}\\}$ and $\\{m_{\lambda}\\}$.

  * (b)

If ${\mathbb{Q}}$ is a subring of $\mathbf{k}$, then $\\{p_{\lambda}\\}$ and
$\left\\{z_{\lambda}^{-1}p_{\lambda}\right\\}$ are also dual bases with
respect to the Hall inner product on $\Lambda$.

  * (c)

If ${\mathbb{R}}$ is a subring of $\mathbf{k}$, then
$\left\\{\dfrac{p_{\lambda}}{\sqrt{z_{\lambda}}}\right\\}$ is an orthonormal
basis of $\Lambda$ with respect to the Hall inner product.

###### Proof.

Since (2.34) and (2.38) showed

$\prod_{i,j=1}^{\infty}(1-x_{i}y_{j})^{-1}=\sum_{\lambda\in\operatorname{Par}}s_{\lambda}({\mathbf{x}})s_{\lambda}({\mathbf{y}})\\\
=\sum_{\lambda\in\operatorname{Par}}h_{\lambda}({\mathbf{x}})m_{\lambda}({\mathbf{y}})\\\
=\sum_{\lambda\in\operatorname{Par}}p_{\lambda}({\mathbf{x}})z_{\lambda}^{-1}p_{\lambda}({\mathbf{y}})=\sum_{\lambda\in\operatorname{Par}}\frac{p_{\lambda}({\mathbf{x}})}{\sqrt{z_{\lambda}}}\frac{p_{\lambda}({\mathbf{y}})}{\sqrt{z_{\lambda}}}$

it suffices to show that any pair of graded bases898989A basis
$\left\\{w_{\lambda}\right\\}$ of $\Lambda$ indexed by the partitions
$\lambda$ is said to be graded if every $n\in{\mathbb{N}}$ and
$\lambda\in\operatorname{Par}_{n}$ satisfy $w_{\lambda}\in\Lambda_{n}$.
$\\{u_{\lambda}\\},\\{v_{\lambda}\\}$ having

$\sum_{\lambda\in\operatorname{Par}}s_{\lambda}({\mathbf{x}})s_{\lambda}({\mathbf{y}})=\sum_{\lambda\in\operatorname{Par}}u_{\lambda}({\mathbf{x}})v_{\lambda}({\mathbf{y}})$

will be dual with respect to $(\cdot,\cdot)$. Write transition matrices
$A=\left(a_{\nu,\lambda}\right)_{\left(\nu,\lambda\right)\in\operatorname{Par}\times\operatorname{Par}}$
and
$B=\left(b_{\nu,\lambda}\right)_{\left(\nu,\lambda\right)\in\operatorname{Par}\times\operatorname{Par}}$
uniquely expressing

(2.42) $\displaystyle u_{\lambda}$
$\displaystyle=\sum_{\nu}a_{\nu,\lambda}s_{\nu},$ (2.43) $\displaystyle
v_{\lambda}$ $\displaystyle=\sum_{\nu}b_{\nu,\lambda}s_{\nu}.$

Recall that
$\operatorname{Par}=\bigsqcup_{r\in{\mathbb{N}}}\operatorname{Par}_{r}$.
Hence, we can view $A$ as a block matrix, where the blocks are indexed by
pairs of nonnegative integers, and the $\left(r,s\right)$-th block is
$\left(a_{\nu,\lambda}\right)_{\left(\nu,\lambda\right)\in\operatorname{Par}_{r}\times\operatorname{Par}_{s}}$.
For reasons of homogeneity909090More precisely: The power series $u_{\lambda}$
is homogeneous of degree $\left|\lambda\right|$, and the power series
$s_{\nu}$ is homogeneous of degree $\left|\nu\right|$., we have
$a_{\nu,\lambda}=0$ for any
$\left(\nu,\lambda\right)\in\operatorname{Par}^{2}$ satisfying
$\left|\nu\right|\neq\left|\lambda\right|$. Therefore, the
$\left(r,s\right)$-th block of $A$ is zero whenever $r\neq s$. In other words,
the block matrix $A$ is block-diagonal. Similarly, $B$ can be viewed as a
block-diagonal matrix. The diagonal blocks of $A$ and $B$ are finite square
matrices (since $\operatorname{Par}_{r}$ is a finite set for each
$r\in{\mathbb{N}}$); therefore, products such as $A^{t}B$, $B^{t}A$ and
$AB^{t}$ are well-defined (since all sums involved in their definition have
only finitely many nonzero addends) and subject to the law of associativity.
Moreover, the matrix $A$ is invertible (being a transition matrix between two
bases), and its inverse is again block-diagonal (because $A$ is block-
diagonal).

The equalities (2.42) and (2.43) show that
$(u_{\alpha},v_{\beta})=\sum_{\nu}a_{\nu,\alpha}b_{\nu,\beta}$ (by the
orthonormality of the $s_{\lambda}$). Hence, we want to prove that
$\sum_{\nu}a_{\nu,\alpha}b_{\nu,\beta}=\delta_{\alpha,\beta}$. In other words,
we want to prove that $A^{t}B=I$, that is, $B^{-1}=A^{t}$. On the other hand,
one has

$\sum_{\lambda}s_{\lambda}({\mathbf{x}})s_{\lambda}({\mathbf{y}})=\sum_{\lambda}u_{\lambda}({\mathbf{x}})v_{\lambda}({\mathbf{y}})=\sum_{\lambda}\sum_{\nu}a_{\nu,\lambda}s_{\nu}({\mathbf{x}})\sum_{\rho}b_{\rho,\lambda}s_{\rho}({\mathbf{y}}).$

Comparing coefficients919191Comparing coefficients is legitimate since
$\Lambda\left({\mathbf{x}}\right)\otimes\Lambda\left({\mathbf{y}}\right)$
embeds into $\mathbf{k}\left[\left[{\mathbf{x}},{\mathbf{y}}\right]\right]$.
of $s_{\nu}({\mathbf{x}})s_{\rho}({\mathbf{y}})$ forces
$\sum_{\lambda}a_{\nu,\lambda}b_{\rho,\lambda}=\delta_{\nu,\rho}$, or in other
words, $AB^{t}=I$. Since $A$ is invertible, this yields $B^{t}A=I$, and hence
$A^{t}B=I$, as desired.929292In our argument above, we have obtained the
invertibility of $A$ from the fact that $A$ is a transition matrix between two
bases. Here is an alternative way to prove that $A$ is invertible: Recall that
$A$ and $B^{t}$ are block-diagonal matrices. Hence, the equality $AB^{t}=I$
rewrites as $A_{r,r}\left(B^{t}\right)_{r,r}=I$ for all $r\in{\mathbb{N}}$,
where we are using the notation $C_{r,s}$ for the $\left(r,s\right)$-th block
of a block matrix $C$. But this shows that each diagonal block $A_{r,r}$ of
$A$ is right-invertible. Therefore, each diagonal block $A_{r,r}$ of $A$ is
invertible (because $A_{r,r}$ is a square matrix of finite size, and such
matrices are always invertible when they are right-invertible). Consequently,
the block-diagonal matrix $A$ is invertible, and its inverse is again a block-
diagonal matrix (whose diagonal blocks are the inverses of the $A_{r,r}$). ∎

Corollary 2.46 is a known and fundamental fact939393For example, Corollary
2.46(a) appears in [100, Corollary 3.3] (though the definition of Schur
functions in [100] is different from ours; we will meet this alternative
definition later on), and parts (b) and (c) of Corollary 2.46 are equivalent
to [114, §I.4, (4.7)] (though Macdonald defines the Hall inner product using
Corollary 2.46(a)).. However, our definition of the Hall inner product is
unusual; most authors (e.g., Macdonald in [114, §I.4, (4.5)],
Hazewinkel/Gubareni/Kirichenko in [73, Def. 4.1.21], and Stanley in [164,
(7.30)]) define the Hall inner product as the bilinear form satisfying
$\left(h_{\lambda},m_{\mu}\right)=\delta_{\lambda,\mu}$ (or, alternatively,
$\left(m_{\lambda},h_{\mu}\right)=\delta_{\lambda,\mu}$), and only later prove
that the basis $\left\\{s_{\lambda}\right\\}$ is orthonormal with respect to
this scalar product. (Of course, the fact that this definition is equivalent
to our Definition 2.41 follows either from this orthonormality, or from our
Corollary 2.46(a).)

The tactic applied in the proof of Corollary 2.46 can not only be used to show
that certain bases of $\Lambda$ are dual, but also, with a little help from
linear algebra over rings (Exercise 2.47), it can be strengthened to show that
certain families of symmetric functions are bases to begin with, as we will
see in Exercise 2.48.

######  Exercise 2.47.

  * (a)

Prove that if an endomorphism of a finitely generated $\mathbf{k}$-module is
surjective, then this endomorphism is a $\mathbf{k}$-module isomorphism.

  * (b)

Let $A$ be a finite free $\mathbf{k}$-module with finite basis
$\left(\gamma_{i}\right)_{i\in I}$. Let $\left(\beta_{i}\right)_{i\in I}$ be a
family of elements of $A$ which spans the $\mathbf{k}$-module $A$. Prove that
$\left(\beta_{i}\right)_{i\in I}$ is a $\mathbf{k}$-basis of $A$.

######  Exercise 2.48.

  * (a)

Assume that for every partition $\lambda$, two homogeneous elements
$u_{\lambda}$ and $v_{\lambda}$ of $\Lambda$, both having degree
$\left|\lambda\right|$, are given. Assume further that

$\sum_{\lambda\in\operatorname{Par}}s_{\lambda}\left({\mathbf{x}}\right)s_{\lambda}\left({\mathbf{y}}\right)=\sum_{\lambda\in\operatorname{Par}}u_{\lambda}\left({\mathbf{x}}\right)v_{\lambda}\left({\mathbf{y}}\right)$

in
$\mathbf{k}\left[\left[{\mathbf{x}},{\mathbf{y}}\right]\right]=\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots,y_{1},y_{2},y_{3},\ldots\right]\right]$.
Show that $\left(u_{\lambda}\right)_{\lambda\in\operatorname{Par}}$ and
$\left(v_{\lambda}\right)_{\lambda\in\operatorname{Par}}$ are
$\mathbf{k}$-bases of $\Lambda$, and actually are dual bases with respect to
the Hall inner product on $\Lambda$.

  * (b)

Use this to give a new proof of the fact that
$\left(h_{\lambda}\right)_{\lambda\in\operatorname{Par}}$ is a
$\mathbf{k}$-basis of $\Lambda$.

######  Exercise 2.49.

Prove that $\sum_{m\geq
0}p_{m+1}t^{m}=\dfrac{H^{\prime}\left(t\right)}{H\left(t\right)}$. (This was
proven in (2.40) in the case when ${\mathbb{Q}}$ is a subring of $\mathbf{k}$,
but here we make no requirements on $\mathbf{k}$.)

###  2.6. Bialternants, Littlewood-Richardson: Stembridge’s concise proof

There is a more natural way in which Schur functions arise as a
$\mathbf{k}$-basis for $\Lambda$, coming from consideration of polynomials in
a finite variable set, and the relation between those which are symmetric and
those which are alternating.

For the remainder of this section, fix a nonnegative integer $n$, and let
${\mathbf{x}}=(x_{1},\ldots,x_{n})$ be a finite variable set. This means that
$s_{\lambda/\mu}=s_{\lambda/\mu}({\mathbf{x}})=\sum_{T}{\mathbf{x}}^{\operatorname{cont}(T)}$
is a generating function for column-strict tableaux $T$ as in Definition 2.20,
but with the extra condition that $T$ have entries in $\\{1,2,\ldots,n\\}$.
949494See Exercise 2.27(a) for this. As a consequence, $s_{\lambda/\mu}$ is a
polynomial in $\mathbf{k}\left[x_{1},x_{2},\ldots,x_{n}\right]$ (not just a
power series), since there are only finitely many column-strict tableaux $T$
of shape $\lambda/\mu$ having all their entries in
$\left\\{1,2,\ldots,n\right\\}$. We will assume without further mention that
all partitions appearing in the section have at most $n$ parts.

######  Definition 2.50.

Let $\mathbf{k}$ be the ring ${\mathbb{Z}}$ or a field of characteristic not
equal to $2$. (We require this to avoid certain annoyances in the discussion
of alternating polynomials in characteristic $2$.)

Say that a polynomial $f({\mathbf{x}})=f(x_{1},\ldots,x_{n})$ is alternating
if for every permutation $w$ in $\mathfrak{S}_{n}$ one has that

$(wf)({\mathbf{x}})=f(x_{w(1)},\ldots,x_{w(n)})=\operatorname{sgn}(w)f({\mathbf{x}}).$

Let $\Lambda^{\operatorname{sgn}}\subset\mathbf{k}[x_{1},\ldots,x_{n}]$ denote
the subset of alternating polynomials959595When $\mathbf{k}$ has
characteristic $2$ (or, more generally, is an arbitrary commutative ring), it
is probably best to define the alternating polynomials
$\Lambda^{\operatorname{sgn}}_{\mathbf{k}}$ as the $\mathbf{k}$-submodule
$\Lambda^{\operatorname{sgn}}\otimes_{{\mathbb{Z}}}\mathbf{k}$ of
${\mathbb{Z}}[x_{1},\ldots,x_{n}]\otimes_{{\mathbb{Z}}}\mathbf{k}\cong\mathbf{k}[x_{1},\ldots,x_{n}]$..

As with $\Lambda$ and its monomial basis $\\{m_{\lambda}\\}$, there is an
obvious $\mathbf{k}$-basis for $\Lambda^{\operatorname{sgn}}$, coming from the
fact that a polynomial $f=\sum_{\alpha}c_{\alpha}{\mathbf{x}}^{\alpha}$ is
alternating if and only if $c_{w(\alpha)}=\operatorname{sgn}(w)c_{\alpha}$ for
every $w$ in $\mathfrak{S}_{n}$ and every $\alpha\in{\mathbb{N}}^{n}$. This
means that every alternating $f$ is a $\mathbf{k}$-linear combination of the
following elements.

######  Definition 2.51.

For $\alpha=(\alpha_{1},\ldots,\alpha_{n})$ in ${\mathbb{N}}^{n}$, define the
alternant

$a_{\alpha}:=\sum_{w\in\mathfrak{S}_{n}}\operatorname{sgn}(w)w({\mathbf{x}}^{\alpha})=\det\left[\begin{matrix}x_{1}^{\alpha_{1}}&\cdots&x_{1}^{\alpha_{n}}\\\
x_{2}^{\alpha_{1}}&\cdots&x_{2}^{\alpha_{n}}\\\ \vdots&\ddots&\vdots\\\
x_{n}^{\alpha_{1}}&\cdots&x_{n}^{\alpha_{n}}\end{matrix}\right].$

######  Example 2.52.

One has

$a_{(1,5,0)}=x_{1}^{1}x_{2}^{5}x_{3}^{0}-x_{1}^{5}x_{2}^{1}x_{3}^{0}-x_{1}^{1}x_{2}^{0}x_{3}^{5}-x_{1}^{0}x_{2}^{5}x_{3}^{1}+x_{1}^{0}x_{2}^{1}x_{3}^{5}+x_{1}^{5}x_{2}^{0}x_{3}^{1}=-a_{(5,1,0)}.$

Similarly, $a_{w\left(\alpha\right)}=\operatorname{sgn}(w)a_{\alpha}$ for
every $w\in\mathfrak{S}_{n}$ and every $\alpha\in{\mathbb{N}}^{n}$.

Meanwhile, $a_{(5,2,2)}=0$ since the transposition $t=\binom{123}{132}$ fixes
$(5,2,2)$ and hence

$a_{(5,2,2)}=t(a_{(5,2,2)})=\operatorname{sgn}(t)a_{(5,2,2)}=-a_{(5,2,2)}.$
969696One subtlety should be addressed: We want to prove that $a_{(5,2,2)}=0$
in $\mathbf{k}\left[x_{1},\ldots,x_{n}\right]$ for every commutative ring
$\mathbf{k}$. It is clearly enough to prove that $a_{(5,2,2)}=0$ in
${\mathbb{Z}}\left[x_{1},\ldots,x_{n}\right]$. Since $2$ is not a zero-divisor
in ${\mathbb{Z}}\left[x_{1},\ldots,x_{n}\right]$, we can achieve this by
showing that $a_{(5,2,2)}=-a_{(5,2,2)}$. We would not be able to make this
argument directly over an arbitrary commutative ring $\mathbf{k}$.

Alternatively, $a_{(5,2,2)}=0$ as it is a determinant of a matrix with two
equal columns. Similarly, $a_{\alpha}=0$ for every $n$-tuple
$\alpha\in{\mathbb{N}}^{n}$ having two equal entries.

This example illustrates that, for a $\mathbf{k}$-basis for
$\Lambda^{\operatorname{sgn}}$, one can restrict attention to alternants
$a_{\alpha}$ in which $\alpha$ is a strict partition, i.e., in which $\alpha$
satisfies $\alpha_{1}>\alpha_{2}>\cdots>\alpha_{n}$. One can therefore
uniquely express $\alpha=\lambda+\rho$, where $\lambda$ is a (weak) partition
$\lambda_{1}\geq\cdots\geq\lambda_{n}\geq 0$ and where
$\rho:=(n-1,n-2,\ldots,2,1,0)$ is sometimes called the staircase
partition979797The name is owed to its Ferrers shape. For instance, if $n=5$,
then the Ferrers diagram of $\rho$ (represented using dots) has the form
$\begin{matrix}\bullet&\bullet&\bullet&\bullet\\\ \bullet&\bullet&\bullet&\\\
\bullet&\bullet&&\\\ \bullet&&&\end{matrix}.$ . For example
$\alpha=(5,1,0)=(3,0,0)+(2,1,0)=\lambda+\rho$.

######  Proposition 2.53.

Let $\mathbf{k}$ be the ring ${\mathbb{Z}}$ or a field of characteristic not
equal to $2$.

The alternants $\\{a_{\lambda+\rho}\\}$ as $\lambda$ runs through the
partitions with at most $n$ parts form a $\mathbf{k}$-basis for
$\Lambda^{\operatorname{sgn}}$. In addition, the bialternants
$\\{\frac{a_{\lambda+\rho}}{a_{\rho}}\\}$ as $\lambda$ runs through the same
set form a $\mathbf{k}$-basis for
$\Lambda(x_{1},\ldots,x_{n})=\mathbf{k}[x_{1},\ldots,x_{n}]^{\mathfrak{S}_{n}}$.

###### Proof.

The first assertion should be clear from our previous discussion: the
alternants $\\{a_{\lambda+\rho}\\}$ span $\Lambda^{\operatorname{sgn}}$ by
definition, and they are $\mathbf{k}$-linearly independent because they are
supported on disjoint sets of monomials ${\mathbf{x}}^{\alpha}$.

The second assertion follows from the first, after proving the following
Claim: $f({\mathbf{x}})$ lies in $\Lambda^{\operatorname{sgn}}$ if and only if
$f({\mathbf{x}})=a_{\rho}\cdot g({\mathbf{x}})$ where $g({\mathbf{x}})$ lies
in $\mathbf{k}[{\mathbf{x}}]^{\mathfrak{S}_{n}}$ and where

$a_{\rho}=\det(x_{i}^{n-j})_{i,j=1,2,\ldots,n}=\prod_{1\leq i<j\leq
n}(x_{i}-x_{j})$

is the Vandermonde determinant/product. In other words

$\Lambda^{\operatorname{sgn}}=a_{\rho}\cdot\mathbf{k}[{\mathbf{x}}]^{\mathfrak{S}_{n}}$

is a free $\mathbf{k}[{\mathbf{x}}]^{\mathfrak{S}_{n}}$-module of rank one,
with $a_{\rho}$ as its $\mathbf{k}[{\mathbf{x}}]^{\mathfrak{S}_{n}}$-basis
element.

To see the Claim, first note the inclusion

$\Lambda^{\operatorname{sgn}}\supset
a_{\rho}\cdot\mathbf{k}[{\mathbf{x}}]^{\mathfrak{S}_{n}}$

since the product of a symmetric polynomial and an alternating polynomial is
an alternating polynomial. For the reverse inclusion, note that since an
alternating polynomial $f({\mathbf{x}})$ changes sign whenever one exchanges
two distinct variables $x_{i},x_{j}$, it must vanish upon setting
$x_{i}=x_{j}$, and therefore be divisible by $x_{i}-x_{j}$, so divisible by
the entire product $\prod_{1\leq i<j\leq n}(x_{i}-x_{j})=a_{\rho}$. But then
the quotient $g({\mathbf{x}})=\frac{f({\mathbf{x}})}{a_{\rho}}$ is symmetric,
as it is a quotient of two alternating polynomials. ∎

Let us now return to the general setting, where $\mathbf{k}$ is an arbitrary
commutative ring. We are not requiring that the assumptions of Proposition
2.53 be valid; we can still study the $a_{\alpha}$ of Definition 2.51, but we
cannot use Proposition 2.53 anymore. We will show that the fraction
$\frac{a_{\lambda+\rho}}{a_{\rho}}$ is nevertheless a well-defined polynomial
in $\Lambda\left(x_{1},\ldots,x_{n}\right)$ whenever $\lambda$ is a
partition989898This can also be deduced by base change from the
$\mathbf{k}={\mathbb{Z}}$ case of Proposition 2.53., and in fact equals the
Schur function $s_{\lambda}({\mathbf{x}})$. As a consequence, the mysterious
bialternant basis $\\{\frac{a_{\lambda+\rho}}{a_{\rho}}\\}$ of
$\Lambda\left(x_{1},\ldots,x_{n}\right)$ defined in Proposition 2.53 still
exists in the general setting, and is plainly the Schur functions
$\\{s_{\lambda}({\mathbf{x}})\\}$. Stembridge [167] noted that one could give
a remarkably concise proof of an even stronger assertion, which simultaneously
gives one of the standard combinatorial interpretations for the Littlewood-
Richardson coefficients $c^{\lambda}_{\mu,\nu}$. For the purposes of stating
it, we introduce for a tableau $T$ the notation $T|_{\operatorname{cols}\geq
j}$ (resp. $T|_{\operatorname{cols}\leq j}$) to indicate the subtableau which
is the restriction of $T$ to the union of its columns $j,j+1,j+2,\ldots$
(resp. columns $1,2,\ldots,j$).

######  Theorem 2.54.

For partitions $\lambda,\mu,\nu$ with $\mu\subseteq\lambda$, one
has999999Again, we can drop the requirement that $\mu\subseteq\lambda$,
provided that we understand that there are no column-strict tableaux of shape
$\lambda/\mu$ unless $\mu\subseteq\lambda$.

$a_{\nu+\rho}s_{\lambda/\mu}=\sum_{T}a_{\nu+\operatorname{cont}(T)+\rho}$

where $T$ runs through all column-strict tableaux with entries in
$\\{1,2,\ldots,n\\}$ of shape $\lambda/\mu$ with the property that for all
$j=1,2,\ldots$ one has $\nu+\operatorname{cont}(T|_{\operatorname{cols}\geq
j})$ a partition.

Before proving Theorem 2.54, let us see some of its consequences.

######  Corollary 2.55.

For any partition $\lambda$, we have100100100Notice that division by
$a_{\rho}$ is unambiguous in the ring
$\mathbf{k}\left[x_{1},\ldots,x_{n}\right]$, since $a_{\rho}$ is not a zero-
divisor (in fact, $a_{\rho}=\prod_{1\leq i<j\leq n}(x_{i}-x_{j})$ is the
product of the binomials $x_{i}-x_{j}$, none of which is a zero-divisor).

$s_{\lambda}({\mathbf{x}})=\frac{a_{\lambda+\rho}}{a_{\rho}}.$

###### Proof.

Take $\nu=\mu=\varnothing$ in Theorem 2.54. Note that for any $\lambda$, there
is only one column-strict tableau $T$ of shape $\lambda$ having each
$\operatorname{cont}(T|_{\operatorname{cols}\geq j})$ a partition, namely the
one having every entry in row $i$ equal to $i$:

$\begin{matrix}1&1&1&1&1\\\ 2&2&2&&\\\ 3&3&3&&\\\ 4&4\end{matrix}$

Furthermore, this $T$ has $\operatorname{cont}(T)=\lambda$, so the theorem
says $a_{\rho}s_{\lambda}=a_{\lambda+\rho}$. ∎

######  Example 2.56.

For $n=2$, so that $\rho=(1,0)$, if we take $\lambda=(4,2)$, then one has

$\displaystyle\frac{a_{\lambda+\rho}}{a_{\rho}}$
$\displaystyle=\frac{a_{(4,2)+(1,0)}}{a_{(1,0)}}=\frac{a_{(5,2)}}{a_{(1,0)}}$
$\displaystyle=\frac{x_{1}^{5}x_{2}^{2}-x_{1}^{2}x_{2}^{5}}{x_{1}-x_{2}}$
$\displaystyle=x_{1}^{4}x_{2}^{2}+x_{1}^{3}x_{2}^{3}+x_{1}^{2}x_{2}^{4}$
$\displaystyle={\mathbf{x}}^{\operatorname{cont}{\left(\begin{matrix}1111\\\
22\phantom{1}\phantom{1}\end{matrix}\right)}}+{\mathbf{x}}^{\operatorname{cont}{\left(\begin{matrix}1112\\\
22\phantom{1}\phantom{1}\end{matrix}\right)}}+{\mathbf{x}}^{\operatorname{cont}{\left(\begin{matrix}1122\\\
22\phantom{1}\phantom{1}\end{matrix}\right)}}$
$\displaystyle=s_{(4,2)}=s_{\lambda}.$

Some authors use the equality in Corollary 2.55 to define the Schur polynomial
$s_{\lambda}\left(x_{1},x_{2},\ldots,x_{n}\right)$ in $n$ variables; this
definition, however, has the drawback of not generalizing easily to infinitely
many variables or to skew Schur functions101101101With some effort, it is
possible to use Corollary 2.55 in order to define the Schur function
$s_{\lambda}$ in infinitely many variables. Indeed, one can define this Schur
function as the unique element of $\Lambda$ whose evaluation at
$\left(x_{1},x_{2},\ldots,x_{n}\right)$ equals
$\frac{a_{\lambda+\rho}}{a_{\rho}}$ for every $n\in{\mathbb{N}}$. If one wants
to use such a definition, however, one needs to check that such an element
exists. This is the approach to defining $s_{\lambda}$ taken in [100,
Definition 1.4.2] and in [114, §I.3]..

Next divide through by $a_{\rho}$ on both sides of Theorem 2.54 (and use
Corollary 2.55) to give the following.

######  Corollary 2.57.

For partitions $\lambda,\mu,\nu$ having at most $n$ parts, one has

(2.44) $s_{\nu}s_{\lambda/\mu}=\sum_{T}s_{\nu+\operatorname{cont}(T)}$

where $T$ runs through the same set as in Theorem 2.54. In particular, taking
$\nu=\varnothing$, we obtain

(2.45) $s_{\lambda/\mu}=\sum_{T}s_{\operatorname{cont}(T)}$

where in the sum $T$ runs through all column-strict tableaux of shape
$\lambda/\mu$ for which each $\operatorname{cont}(T|_{\operatorname{cols}\geq
j})$ is a partition.

###### Proof of Theorem 2.54.

Start by rewriting the left side of the theorem, and using the fact that
$w(s_{\lambda/\mu})=s_{\lambda/\mu}$ for any $w$ in $\mathfrak{S}_{n}$:

$\displaystyle a_{\nu+\rho}s_{\lambda/\mu}$
$\displaystyle=\sum_{w\in\mathfrak{S}_{n}}\operatorname{sgn}(w){\mathbf{x}}^{w(\nu+\rho)}w(s_{\lambda/\mu})$
$\displaystyle=\sum_{w\in\mathfrak{S}_{n}}\operatorname{sgn}(w){\mathbf{x}}^{w(\nu+\rho)}\sum_{\begin{subarray}{c}\text{column-
strict }T\\\ \text{ of shape
}\lambda/\mu\end{subarray}}{\mathbf{x}}^{w(\operatorname{cont}(T))}$
$\displaystyle=\sum_{\begin{subarray}{c}\text{column-strict }T\\\ \text{ of
shape
}\lambda/\mu\end{subarray}}\qquad\sum_{w\in\mathfrak{S}_{n}}\operatorname{sgn}(w){\mathbf{x}}^{w(\nu+\operatorname{cont}(T)+\rho)}$
$\displaystyle=\sum_{\begin{subarray}{c}\text{column-strict }T\\\ \text{ of
shape }\lambda/\mu\end{subarray}}a_{\nu+\operatorname{cont}(T)+\rho}$

We wish to cancel out all the summands indexed by column-strict tableaux $T$
which fail any of the conditions that
$\nu+\operatorname{cont}(T|_{\operatorname{cols}\geq j})$ be a partition.
Given such a $T$, find the maximal $j$ for which it fails this
condition102102102Such a $j$ exists because
$\nu+\operatorname{cont}(T|_{\operatorname{cols}\geq j})$ is a partition for
all sufficiently high $j$ (in fact, $\nu$ itself is a partition)., and then
find the minimal $k$ for which

$\nu_{k}+\operatorname{cont}_{k}(T|_{\operatorname{cols}\geq
j})<\nu_{k+1}+\operatorname{cont}_{k+1}(T|_{\operatorname{cols}\geq j}).$

Maximality of $j$ forces

$\nu_{k}+\operatorname{cont}_{k}(T|_{\operatorname{cols}\geq
j+1})\geq\nu_{k+1}+\operatorname{cont}_{k+1}(T|_{\operatorname{cols}\geq
j+1}).$

Since column-strictness implies that column $j$ of $T$ can contain at most one
occurrence of $k$ or of $k+1$ (or neither or both), the previous two
inequalities imply that column $j$ must contain an occurrence of $k+1$ and no
occurrence of $k$, so that

$\nu_{k}+\operatorname{cont}_{k}(T|_{\operatorname{cols}\geq
j})+1=\nu_{k+1}+\operatorname{cont}_{k+1}(T|_{\operatorname{cols}\geq j}).$

This implies that the adjacent transposition $t_{k,k+1}$ swapping $k$ and
$k+1$ fixes the vector $\nu+\operatorname{cont}(T|_{\operatorname{cols}\geq
j})+\rho$.

Now create a new tableau $T^{*}$ from $T$ by applying the Bender-Knuth
involution (from the proof of Proposition 2.11) on letters $k,k+1$, but only
to columns $1,2,\ldots,j-1$ of $T$, leaving columns $j,j+1,j+2,\ldots$
unchanged. One should check that $T^{*}$ is still column-strict, but this
holds because column $j$ of $T$ has no occurrences of letter $k$. Note that

$t_{k,k+1}\operatorname{cont}(T|_{\operatorname{cols}\leq
j-1})=\operatorname{cont}(T^{*}|_{\operatorname{cols}\leq j-1})$

and hence

$t_{k,k+1}(\nu+\operatorname{cont}(T)+\rho)=\nu+\operatorname{cont}(T^{*})+\rho$

so that
$a_{\nu+\operatorname{cont}(T)+\rho}=-a_{\nu+\operatorname{cont}(T^{*})+\rho}$.

Because $T,T^{*}$ have exactly the same columns $j,j+1,j+2,\ldots$, the
tableau $T^{*}$ is also a violator of at least one of the conditions that
$\nu+\operatorname{cont}(T^{*}|_{\operatorname{cols}\geq j})$ be a partition,
and has the same choice of maximal $j$ and minimal $k$ as did $T$. Hence the
map $T\mapsto T^{*}$ is an involution on the violators that lets one cancel
their summands $a_{\nu+\operatorname{cont}(T)+\rho}$ and
$a_{\nu+\operatorname{cont}(T^{*})+\rho}$ in pairs. ∎

So far (in this section) we have worked with a finite set of variables
$x_{1},x_{2},\ldots,x_{n}$ (where $n$ is a fixed nonnegative integer) and with
partitions having at most $n$ parts. We now drop these conventions and
restrictions; thus, partitions again mean arbitrary partitions, and
${\mathbf{x}}$ again means the infinite family
$\left(x_{1},x_{2},x_{3},\ldots\right)$ of variables. In this setting, we have
the following analogue of Corollary 2.57:

######  Corollary 2.58.

For partitions $\lambda,\mu,\nu$ (of any lengths), one has

(2.46) $s_{\nu}s_{\lambda/\mu}=\sum_{T}s_{\nu+\operatorname{cont}(T)}$

where $T$ runs through all column-strict tableaux of shape $\lambda/\mu$ with
the property that for all $j=1,2,\ldots$ one has
$\nu+\operatorname{cont}(T|_{\operatorname{cols}\geq j})$ a partition. In
particular, taking $\nu=\varnothing$, we obtain

(2.47) $s_{\lambda/\mu}=\sum_{T}s_{\operatorname{cont}(T)}$

where in the sum $T$ runs through all column-strict tableaux of shape
$\lambda/\mu$ for which each $\operatorname{cont}(T|_{\operatorname{cols}\geq
j})$ is a partition.

###### Proof of Corollary 2.58..

Essentially, Corollary 2.58 is obtained from Corollary 2.57 by “letting $n$
(that is, the number of variables) tend to $\infty$”. This can be formalized
in different ways: One way is to endow the ring of power series
$\mathbf{k}\left[\left[{\mathbf{x}}\right]\right]=\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$
with the coefficientwise topology103103103This topology is defined as follows:
We endow the ring $\mathbf{k}$ with the discrete topology. Then, we can regard
the $\mathbf{k}$-module $\mathbf{k}\left[\left[{\mathbf{x}}\right]\right]$ as
a direct product of infinitely many copies of $\mathbf{k}$ (by identifying
every power series in $\mathbf{k}\left[\left[{\mathbf{x}}\right]\right]$ with
the family of its coefficients). Hence, the product topology is a well-defined
topology on $\mathbf{k}\left[\left[{\mathbf{x}}\right]\right]$; this topology
is denoted as the coefficientwise topology. Its name is due to the fact that a
sequence $\left(a_{n}\right)_{n\in{\mathbb{N}}}$ of power series converges to
a power series $a$ with respect to this topology if and only if for every
monomial $\mathfrak{m}$, all sufficiently high $n\in{\mathbb{N}}$ satisfy
$\left(\text{the coefficient of }\mathfrak{m}\text{ in
}a_{n}\right)=\left(\text{the coefficient of }\mathfrak{m}\text{ in
}a\right).$ , and to show that the left hand side of (2.44) tends to the left
hand side of (2.46) when $n\to\infty$, and the same holds for the right hand
sides. A different approach proceeds by regarding $\Lambda$ as the inverse
limit of the $\Lambda\left(x_{1},x_{2},\ldots,x_{n}\right)$. ∎

Comparing coefficients of a given Schur function $s_{\nu}$ in (2.47), we
obtain the following version of the Littlewood-Richardson rule.

######  Corollary 2.59.

For partitions $\lambda,\mu,\nu$ (of any lengths), the Littlewood-Richardson
coefficient $c^{\lambda}_{\mu,\nu}$ counts column-strict tableaux $T$ of shape
$\lambda/\mu$ with $\operatorname{cont}(T)=\nu$ having the property that each
$\operatorname{cont}(T|_{\operatorname{cols}\geq j})$ is a partition.

###  2.7. The Pieri and Assaf-McNamara skew Pieri rule

The classical Pieri rule refers to two special cases of the Littlewood-
Richardson rule. To state them, recall that a skew shape is called a
horizontal (resp. vertical) strip if no two of its cells lie in the same
column (resp. row). A horizontal (resp. vertical) $n$-strip (for
$n\in{\mathbb{N}}$) shall mean a horizontal (resp. vertical) strip of size $n$
(that is, having exactly $n$ cells).

######  Theorem 2.60.

For every partition $\lambda$ and any $n\in{\mathbb{N}}$, we have

(2.48) $\displaystyle s_{\lambda}h_{n}=$
$\displaystyle\sum_{\begin{subarray}{c}\lambda^{+}:\lambda^{+}/\lambda\text{
is a }\\\ \text{horizontal }n\text{-strip}\end{subarray}}s_{\lambda^{+}}$
(2.49) $\displaystyle s_{\lambda}e_{n}=$
$\displaystyle\sum_{\begin{subarray}{c}\lambda^{+}:\lambda^{+}/\lambda\text{
is a }\\\ \text{vertical }n\text{-strip}\end{subarray}}s_{\lambda^{+}}$

######  Example 2.61.

$\displaystyle\begin{matrix}s&&&\\\ &\square&\square&\square\\\
&\square&\square&\\\