Thus, the interval system corresponding to $\alpha\beta$ is a
$\left(p+q\right)$-tuple of intervals which covers $\left[0:n+m\right]^{+}$.
Denote this $\left(p+q\right)$-tuple by
$\left(I_{1},I_{2},\ldots,I_{p+q}\right)$.

Let $\tau\in\operatorname{Sh}_{p,q}$. Set
$\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$. Then,

$u\underset{\sigma}{\shuffle}v=\left(uv\right)\left[I_{\tau\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\tau\left(p+q\right)}\right].$

######  Exercise 6.63.

Prove Lemma 6.62.

Having these notations and trivialities in place, we can say a bit more about
the lexicographically highest element of a shuffle product than what was said
in Theorem 6.44:

######  Theorem 6.64.

Let $u$ and $v$ be two words. Let $n=\ell\left(u\right)$ and
$m=\ell\left(v\right)$.

Let $\left(a_{1},a_{2},\ldots,a_{p}\right)$ be the CFL factorization of $u$.
Let $\left(b_{1},b_{2},\ldots,b_{q}\right)$ be the CFL factorization of $v$.

Let $\alpha$ be the $p$-tuple
$\left(\ell\left(a_{1}\right),\ell\left(a_{2}\right),\ldots,\ell\left(a_{p}\right)\right)$.
Then, $\alpha$ is a composition240240240since Lyndon words are nonempty, and
thus $\ell\left(a_{i}\right)>0$ for every $i$ of length $p$ and size
$\sum_{k=1}^{p}\ell\left(a_{k}\right)=\ell\left(\underbrace{a_{1}a_{2}\cdots
a_{p}}_{=u}\right)=\ell\left(u\right)=n$.

Let $\beta$ be the $q$-tuple
$\left(\ell\left(b_{1}\right),\ell\left(b_{2}\right),\ldots,\ell\left(b_{q}\right)\right)$.
Then, $\beta$ is a composition of length $q$ and size
$\sum_{k=1}^{q}\ell\left(b_{k}\right)=m$. 241241241The proof of this is the
same as the proof of the fact that $\alpha$ is a composition of length $p$ and
size $\sum_{k=1}^{p}\ell\left(\alpha_{k}\right)=n$.

Now, $\alpha$ is a composition of length $p$ and size $n$, and $\beta$ is a
composition of length $q$ and size $m$. Thus, the concatenation $\alpha\beta$
of these two tuples is a composition of length $p+q$ and size $n+m$. The
interval system corresponding to this composition $\alpha\beta$ is a
$\left(p+q\right)$-tuple (since said composition has length $p+q$); denote
this $\left(p+q\right)$-tuple by $\left(I_{1},I_{2},\ldots,I_{p+q}\right)$.

  * (a)

If $\tau\in\operatorname{Sh}_{p,q}$ satisfies
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$,
and if we set $\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$, then
$\sigma\in\operatorname{Sh}_{n,m}$, and the word
$u\underset{\sigma}{\shuffle}v$ is the lexicographically highest element of
the multiset $u\shuffle v$.

  * (b)

Let $\sigma\in\operatorname{Sh}_{n,m}$ be a permutation such that
$u\underset{\sigma}{\shuffle}v$ is the lexicographically highest element of
the multiset $u\shuffle v$. Then, there exists a unique permutation
$\tau\in\operatorname{Sh}_{p,q}$ satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$
and $\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$.

###### Proof.

Before we step to the actual proof, we need to make some preparation. First of
all, $\left(I_{1},I_{2},\ldots,I_{p+q}\right)$ is the interval system
corresponding to the composition $\alpha\beta$. In other words,

(6.5)
$\left(I_{1},I_{2},\ldots,I_{p+q}\right)=\operatorname*{intsys}\left(\alpha\beta\right).$

But since
$\alpha=\left(\ell\left(a_{1}\right),\ell\left(a_{2}\right),\ldots,\ell\left(a_{p}\right)\right)$
and
$\beta=\left(\ell\left(b_{1}\right),\ell\left(b_{2}\right),\ldots,\ell\left(b_{q}\right)\right)$,
we have

$\alpha\beta=\left(\ell\left(a_{1}\right),\ell\left(a_{2}\right),\ldots,\ell\left(a_{p}\right),\ell\left(b_{1}\right),\ell\left(b_{2}\right),\ldots,\ell\left(b_{q}\right)\right).$

Thus, (6.5) rewrites as

$\left(I_{1},I_{2},\ldots,I_{p+q}\right)=\operatorname*{intsys}\left(\ell\left(a_{1}\right),\ell\left(a_{2}\right),\ldots,\ell\left(a_{p}\right),\ell\left(b_{1}\right),\ell\left(b_{2}\right),\ldots,\ell\left(b_{q}\right)\right).$

By the definition of
$\operatorname*{intsys}\left(\ell\left(a_{1}\right),\ell\left(a_{2}\right),\ldots,\ell\left(a_{p}\right),\ell\left(b_{1}\right),\ell\left(b_{2}\right),\ldots,\ell\left(b_{q}\right)\right)$,
we thus have

$I_{i}=\left[\sum_{k=1}^{i-1}\ell\left(a_{k}\right):\sum_{k=1}^{i}\ell\left(a_{k}\right)\right]^{+}\
\ \ \ \ \ \ \ \ \ \text{for every }i\in\left\\{1,2,\ldots,p\right\\},$

and besides

$I_{p+j}=\left[n+\sum_{k=1}^{j-1}\ell\left(b_{k}\right):n+\sum_{k=1}^{j}\ell\left(b_{k}\right)\right]^{+}\
\ \ \ \ \ \ \ \ \ \text{for every }j\in\left\\{1,2,\ldots,q\right\\}$

(since $\sum_{k=1}^{p}\ell\left(a_{k}\right)=n$). Moreover, Remark 6.48(c)
shows that $\left(I_{1},I_{2},\ldots,I_{p+q}\right)$ is a
$\left(p+q\right)$-tuple of nonempty intervals of ${\mathbb{Z}}$ and satisfies
the following three properties:

  * •

The intervals $I_{1}$, $I_{2}$, $\ldots$, $I_{p+q}$ form a set partition of
the set $\left[0:n+m\right]^{+}$.

  * •

We have $I_{1}<I_{2}<\cdots<I_{p+q}$.

  * •

We have $\left|I_{i}\right|=\ell\left(a_{i}\right)$ for every
$i\in\left\\{1,2,\ldots,p\right\\}$ and
$\left|I_{p+j}\right|=\ell\left(b_{j}\right)$ for every
$j\in\left\\{1,2,\ldots,q\right\\}$.

Of course, every $i\in\left\\{1,2,\ldots,p\right\\}$ satisfies

(6.6) $I_{i}\subset\left[0:n\right]^{+}\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \
\ \ \ \ \ \left(uv\right)\left[I_{i}\right]=u\left[I_{i}\right]=a_{i}.$

Meanwhile, every $i\in\left\\{p+1,p+2,\ldots,p+q\right\\}$ satisfies

(6.7) $I_{i}\subset\left[n:n+m\right]^{+}\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \
\ \ \ \ \ \ \left(uv\right)\left[I_{i}\right]=v\left[I_{i}-n\right]=b_{i-p}$

(where $I_{i}-n$ denotes the interval $\left\\{k-n\ \mid\ k\in
I_{i}\right\\}$). We thus see that

(6.8) $\left(uv\right)\left[I_{i}\right]\text{ is a Lyndon word}\ \ \ \ \ \ \
\ \ \ \text{for every }i\in\left\\{1,2,\ldots,p+q\right\\}$ 242242242Indeed,
when $i\leq p$, this follows from (6.6) and the fact that $a_{i}$ is Lyndon;
whereas in the other case, this follows from (6.7) and the fact that $b_{i-p}$
is Lyndon.

.

By the definition of a CFL factorization, we have $a_{1}\geq
a_{2}\geq\cdots\geq a_{p}$ and $b_{1}\geq b_{2}\geq\cdots\geq b_{q}$.

We have $\sigma\in\operatorname{Sh}_{n,m}$, so that
$\sigma^{-1}\left(1\right)<\sigma^{-1}\left(2\right)<\cdots<\sigma^{-1}\left(n\right)$
and
$\sigma^{-1}\left(n+1\right)<\sigma^{-1}\left(n+2\right)<\cdots<\sigma^{-1}\left(n+m\right)$.
In other words, the restriction of the map $\sigma^{-1}$ to the interval
$\left[0:n\right]^{+}$ is strictly increasing, and so is the restriction of
the map $\sigma^{-1}$ to the interval $\left[n:n+m\right]^{+}$.

(b) We will first show that

(6.9) $\text{if }J\subset\left[0:n\right]^{+}\text{ is an interval such that
the word }\left(uv\right)\left[J\right]\text{ is Lyndon, then
}\sigma^{-1}\left(J\right)\text{ is an interval.}$

Proof of (6.9): We will prove (6.9) by strong induction over $\left|J\right|$.

So, fix some $N\in{\mathbb{N}}$. Assume (as the induction hypothesis) that
(6.9) has been proven whenever $\left|J\right|<N$. We now need to prove (6.9)
when $\left|J\right|=N$.

Let $J\subset\left[0:n\right]^{+}$ be an interval such that the word
$\left(uv\right)\left[J\right]$ is Lyndon and such that $\left|J\right|=N$. We
have to prove that $\sigma^{-1}\left(J\right)$ is an interval. This is obvious
if $\left|J\right|=1$ (because in this case, $\sigma^{-1}\left(J\right)$ is a
one-element set, thus trivially an interval). Hence, we WLOG assume that we
don’t have $\left|J\right|=1$. We also don’t have $\left|J\right|=0$, because
$\left(uv\right)\left[J\right]$ has to be Lyndon (and the empty word is not).
So we have $\left|J\right|>1$. Now,
$\ell\left(\left(uv\right)\left[J\right]\right)=\left|J\right|>1$, and thus
$\left(uv\right)\left[J\right]$ is a Lyndon word of length $>1$. Let
$v^{\prime}$ be the (lexicographically) smallest nonempty proper suffix of
$\left(uv\right)\left[J\right]$. Since $v^{\prime}$ is a proper suffix of $w$,
there exists a nonempty $u^{\prime}\in\mathfrak{A}^{\ast}$ such that
$\left(uv\right)\left[J\right]=u^{\prime}v^{\prime}$. Consider this
$u^{\prime}$.

Now, Theorem 6.30(a) (applied to $\left(uv\right)\left[J\right]$, $u^{\prime}$
and $v^{\prime}$ instead of $w$, $u$ and $v$) yields that the words
$u^{\prime}$ and $v^{\prime}$ are Lyndon. Also, Theorem 6.30(b) (applied to
$\left(uv\right)\left[J\right]$, $u^{\prime}$ and $v^{\prime}$ instead of $w$,
$u$ and $v$) yields that
$u^{\prime}<\left(uv\right)\left[J\right]<v^{\prime}$.

But from the fact that $\left(uv\right)\left[J\right]=u^{\prime}v^{\prime}$
with $u^{\prime}$ and $v^{\prime}$ both being nonempty, it becomes immediately
clear that we can write $J$ as a union of two disjoint nonempty intervals $K$
and $L$ such that $K<L$, $u^{\prime}=\left(uv\right)\left[K\right]$ and
$v^{\prime}=\left(uv\right)\left[L\right]$. Consider these $K$ and $L$. The
intervals $K$ and $L$ are nonempty and have their sizes add up to $N$ (since
they are disjoint and their union is $J$), and hence both must have size
smaller than $\left|J\right|=N$. So $K\subset\left[0:n\right]^{+}$ is an
interval of size $\left|K\right|<N$ having the property that
$\left(uv\right)\left[K\right]$ is Lyndon (since
$\left(uv\right)\left[K\right]=u^{\prime}$ is Lyndon). Thus, we can apply
(6.9) to $K$ instead of $J$ (because of the induction hypothesis). As a
result, we conclude that $\sigma^{-1}\left(K\right)$ is an interval.
Similarly, we can apply (6.9) to $L$ instead of $J$ (we know that
$\left(uv\right)\left[L\right]$ is Lyndon since
$\left(uv\right)\left[L\right]=v^{\prime}$), and learn that
$\sigma^{-1}\left(L\right)$ is an interval. The intervals
$\sigma^{-1}\left(K\right)$ and $\sigma^{-1}\left(L\right)$ are both nonempty
(since $K$ and $L$ are nonempty), and their union is
$\sigma^{-1}\left(J\right)$ (because the union of $K$ and $L$ is $J$). The
nonempty intervals $K$ and $L$ both are subsets of $\left[0:n\right]^{+}$
(since their union is $J\subset\left[0:n\right]^{+}$), and their union $K\cup
L$ is an interval (since their union $K\cup L$ is $J$, and we know that $J$ is
an interval).

Now, assume (for the sake of contradiction) that $\sigma^{-1}\left(J\right)$
is not an interval. Since $J$ is the union of $K$ and $L$, we have $J=K\cup L$
and thus $\sigma^{-1}\left(J\right)=\sigma^{-1}\left(K\cup
L\right)=\sigma^{-1}\left(K\right)\cup\sigma^{-1}\left(L\right)$ (since
$\sigma$ is a bijection). Therefore,
$\sigma^{-1}\left(K\right)\cup\sigma^{-1}\left(L\right)$ is not an interval
(since $\sigma^{-1}\left(J\right)$ is not an interval). Thus, Lemma 6.50(b)
yields that there exists a nonempty interval $P\subset\left[n:n+m\right]^{+}$
such that $\sigma^{-1}\left(P\right)$,
$\sigma^{-1}\left(K\right)\cup\sigma^{-1}\left(P\right)$ and
$\sigma^{-1}\left(P\right)\cup\sigma^{-1}\left(L\right)$ are intervals and
such that
$\sigma^{-1}\left(K\right)<\sigma^{-1}\left(P\right)<\sigma^{-1}\left(L\right)$.
Consider this $P$. Since $P$ is nonempty, we have $\left|P\right|\neq 0$.

Lemma 6.52(b) (applied to $K$ and $P$ instead of $I$ and $J$) yields

(6.10)
$\left(uv\right)\left[K\right]\cdot\left(uv\right)\left[P\right]\geq\left(uv\right)\left[P\right]\cdot\left(uv\right)\left[K\right].$

Since $\left(uv\right)\left[K\right]=u^{\prime}$, this rewrites as

(6.11)
$u^{\prime}\cdot\left(uv\right)\left[P\right]\geq\left(uv\right)\left[P\right]\cdot
u^{\prime}.$

But Lemma 6.52(c) (applied to $P$ and $L$ instead of $I$ and $J$) yields

(6.12)
$\left(uv\right)\left[P\right]\cdot\left(uv\right)\left[L\right]\geq\left(uv\right)\left[L\right]\cdot\left(uv\right)\left[P\right].$

Since $\left(uv\right)\left[L\right]=v^{\prime}$, this rewrites as

(6.13) $\left(uv\right)\left[P\right]\cdot v^{\prime}\geq
v^{\prime}\cdot\left(uv\right)\left[P\right].$

Recall also that $u^{\prime}<v^{\prime}$, and that both words $u^{\prime}$ and
$v^{\prime}$ are Lyndon. Now, Corollary 6.17 (applied to $u^{\prime}$,
$v^{\prime}$ and $\left(uv\right)\left[P\right]$ instead of $u$, $v$ and $z$)
yields that $\left(uv\right)\left[P\right]$ is the empty word (because of
(6.11) and (6.13)), so that
$\ell\left(\left(uv\right)\left[P\right]\right)=0$. This contradicts
$\ell\left(\left(uv\right)\left[P\right]\right)=\left|P\right|\neq 0$. This
contradiction shows that our assumption (that $\sigma^{-1}\left(J\right)$ is
not an interval) was wrong. Hence, $\sigma^{-1}\left(J\right)$ is an interval.
This completes the induction step, and thus (6.9) is proven.

Similarly to (6.9), we can show that

(6.14) $\text{if }J\subset\left[n:n+m\right]^{+}\text{ is an interval such
that the word }\left(uv\right)\left[J\right]\text{ is Lyndon, then
}\sigma^{-1}\left(J\right)\text{ is an interval.}$

Now, let $i\in\left\\{1,2,\ldots,p+q\right\\}$ be arbitrary. We are going to
prove that

(6.15) $\sigma^{-1}\left(I_{i}\right)\text{ is an interval.}$

Proof of (6.15): We must be in one of the following two cases:

Case 1: We have $i\in\left\\{1,2,\ldots,p\right\\}$.

Case 2: We have $i\in\left\\{p+1,p+2,\ldots,p+q\right\\}$.

Let us first consider Case 1. In this case, we have
$i\in\left\\{1,2,\ldots,p\right\\}$. Thus, $I_{i}\subset\left[0:n\right]^{+}$
(by (6.6)). Also, (6.6) yields that $\left(uv\right)\left[I_{i}\right]=a_{i}$
is a Lyndon word. Hence, (6.9) (applied to $J=I_{i}$) yields that
$\sigma^{-1}\left(I_{i}\right)$ is an interval. Thus, (6.15) is proven in Case
1.

Similarly, we can prove (6.15) in Case 2, using (6.7) and (6.14) instead of
(6.6) and (6.9), respectively. Hence, (6.15) is proven.

So we know that $\sigma^{-1}\left(I_{i}\right)$ is an interval. But we also
know that either $I_{i}\subset\left[0:n\right]^{+}$ or
$I_{i}\subset\left[n:n+m\right]^{+}$ (depending on whether $i\leq p$ or
$i>p$). As a consequence, the restriction of the map $\sigma^{-1}$ to the
interval $I_{i}$ is increasing (because the restriction of the map
$\sigma^{-1}$ to the interval $\left[0:n\right]^{+}$ is strictly increasing,
and so is the restriction of the map $\sigma^{-1}$ to the interval
$\left[n:n+m\right]^{+}$).

Now, let us forget that we fixed $i$. We thus have shown that every
$i\in\left\\{1,2,\ldots,p+q\right\\}$ has the two properties that:

  * •

the set $\sigma^{-1}\left(I_{i}\right)$ is an interval;

  * •

the restriction of the map $\sigma^{-1}$ to the interval $I_{i}$ is
increasing.

In other words, the permutation $\sigma$ is
$\left(\alpha\beta\right)$-clumping (since
$\left(I_{1},I_{2},\ldots,I_{p+q}\right)$ is the interval system corresponding
to the composition $\alpha\beta$). Hence, Proposition 6.58(b) (applied to
$n+m$, $\alpha\beta$ and $p+q$ instead of $n$, $\alpha$ and $\ell$) shows that
there exists a unique $\tau\in\mathfrak{S}_{p+q}$ satisfying
$\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$. Thus, the
uniqueness part of Theorem 6.64(b) (i.e., the claim that the $\tau$ in Theorem
6.64(b) is unique if it exists) is proven.

It now remains to prove the existence part of Theorem 6.64(b), i.e., to prove
that there exists at least one permutation $\tau\in\operatorname{Sh}_{p,q}$
satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$
and $\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$. We already
know that there exists a unique $\tau\in\mathfrak{S}_{p+q}$ satisfying
$\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$. Consider this
$\tau$. We will now prove that
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$
and $\tau\in\operatorname{Sh}_{p,q}$. Once this is done, the existence part of
Theorem 6.64(b) will be proven, and thus the proof of Theorem 6.64(b) will be
complete.

Proposition 6.60 yields that $\tau\in\operatorname{Sh}_{p,q}$ if and only if
$\operatorname*{iper}\left(\alpha\beta,\tau\right)\in\operatorname{Sh}_{n,m}$.
Since we know that
$\operatorname*{iper}\left(\alpha\beta,\tau\right)=\sigma\in\operatorname{Sh}_{n,m}$,
we thus conclude that $\tau\in\operatorname{Sh}_{p,q}$. The only thing that
remains to be proven now is that

(6.16)
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right].$

Proof of (6.16): We have $\tau\in\operatorname{Sh}_{p,q}$. In other words,
$\tau^{-1}\left(1\right)<\tau^{-1}\left(2\right)<\cdots<\tau^{-1}\left(p\right)$
and
$\tau^{-1}\left(p+1\right)<\tau^{-1}\left(p+2\right)<\cdots<\tau^{-1}\left(p+q\right)$.
In other words, the restriction of the map $\tau^{-1}$ to the interval
$\left[0:p\right]^{+}$ is strictly increasing, and so is the restriction of
the map $\tau^{-1}$ to the interval $\left[p:p+q\right]^{+}$.

Let $i\in\left\\{1,2,\ldots,p+q-1\right\\}$. We will show that

(6.17)
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right].$

Clearly, both $\tau\left(i\right)$ and $\tau\left(i+1\right)$ belong to
$\left\\{1,2,\ldots,p+q\right\\}=\left\\{1,2,\ldots,p\right\\}\cup\left\\{p+1,p+2,\ldots,p+q\right\\}$.
Thus, we must be in one of the following four cases:

Case 1: We have $\tau\left(i\right)\in\left\\{1,2,\ldots,p\right\\}$ and
$\tau\left(i+1\right)\in\left\\{1,2,\ldots,p\right\\}$.

Case 2: We have $\tau\left(i\right)\in\left\\{1,2,\ldots,p\right\\}$ and
$\tau\left(i+1\right)\in\left\\{p+1,p+2,\ldots,p+q\right\\}$.

Case 3: We have $\tau\left(i\right)\in\left\\{p+1,p+2,\ldots,p+q\right\\}$ and
$\tau\left(i+1\right)\in\left\\{1,2,\ldots,p\right\\}$.

Case 4: We have $\tau\left(i\right)\in\left\\{p+1,p+2,\ldots,p+q\right\\}$ and
$\tau\left(i+1\right)\in\left\\{p+1,p+2,\ldots,p+q\right\\}$.

Let us consider Case 1 first. In this case, we have
$\tau\left(i\right)\in\left\\{1,2,\ldots,p\right\\}$ and
$\tau\left(i+1\right)\in\left\\{1,2,\ldots,p\right\\}$. From the fact that the
restriction of the map $\tau^{-1}$ to the interval $\left[0:p\right]^{+}$ is
strictly increasing, we can easily deduce
$\tau\left(i\right)<\tau\left(i+1\right)$ 243243243Proof. Assume the contrary.
Then, $\tau\left(i\right)\geq\tau\left(i+1\right)$. Since both
$\tau\left(i\right)$ and $\tau\left(i+1\right)$ belong to
$\left\\{1,2,\ldots,p\right\\}=\left[0:p\right]^{+}$, this yields
$\tau^{-1}\left(\tau\left(i\right)\right)\geq\tau^{-1}\left(\tau\left(i+1\right)\right)$
(since the restriction of the map $\tau^{-1}$ to the interval
$\left[0:p\right]^{+}$ is strictly increasing), which contradicts
$\tau^{-1}\left(\tau\left(i\right)\right)=i<i+1=\tau^{-1}\left(\tau\left(i+1\right)\right)$.
This contradiction proves the assumption wrong, qed.. Therefore,
$a_{\tau\left(i\right)}\geq a_{\tau\left(i+1\right)}$ (since $a_{1}\geq
a_{2}\geq\cdots\geq a_{p}$).

But
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]=a_{\tau\left(i\right)}$
(by (6.6), applied to $\tau\left(i\right)$ instead of $i$) and
$\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]=a_{\tau\left(i+1\right)}$
(similarly). In view of these equalities, the inequality
$a_{\tau\left(i\right)}\geq a_{\tau\left(i+1\right)}$ rewrites as
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]$.
Thus, (6.17) is proven in Case 1.

Similarly, we can show (6.17) in Case 4 (observing that
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]=b_{\tau\left(i\right)-p}$
and
$\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]=b_{\tau\left(i+1\right)-p}$
in this case).

Let us now consider Case 2. In this case, we have
$\tau\left(i\right)\in\left\\{1,2,\ldots,p\right\\}$ and
$\tau\left(i+1\right)\in\left\\{p+1,p+2,\ldots,p+q\right\\}$. From
$\tau\left(i\right)\in\left\\{1,2,\ldots,p\right\\}$, we conclude that
$I_{\tau\left(i\right)}\subset\left[0:n\right]^{+}$. From
$\tau\left(i+1\right)\in\left\\{p+1,p+2,\ldots,p+q\right\\}$, we conclude that
$I_{\tau\left(i+1\right)}\subset\left[n:n+m\right]^{+}$. The intervals
$I_{\tau\left(i\right)}$ and $I_{\tau\left(i+1\right)}$ are clearly nonempty.

Proposition 6.56(d) (applied to $n+m$, $\alpha\beta$, $p+q$ and
$\left(I_{1},I_{2},\ldots,I_{p+q}\right)$ instead of $n$, $\alpha$, $\ell$ and
$\left(I_{1},I_{2},\ldots,I_{\ell}\right)$) yields that the sets
$\sigma^{-1}\left(I_{\tau\left(i\right)}\right)$,
$\sigma^{-1}\left(I_{\tau\left(i+1\right)}\right)$ and
$\sigma^{-1}\left(I_{\tau\left(i\right)}\right)\cup\sigma^{-1}\left(I_{\tau\left(i+1\right)}\right)$
are nonempty intervals, and that we have
$\sigma^{-1}\left(I_{\tau\left(i\right)}\right)<\sigma^{-1}\left(I_{\tau\left(i+1\right)}\right)$.
Hence, Lemma 6.52(b) (applied to $I=I_{\tau\left(i\right)}$ and
$J=I_{\tau\left(i+1\right)}$) yields

$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(i\right)}\right].$

But $\left(uv\right)\left[I_{\tau\left(i\right)}\right]$ and
$\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]$ are Lyndon words (as a
consequence of (6.8)). Thus, Proposition 6.18 (applied to
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]$ and
$\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]$ instead of $u$ and $v$)
shows that
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]$
if and only if
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(i\right)}\right]$.
Since we know that
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(i\right)}\right]$
holds, we thus conclude that
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]$.
Thus, (6.17) is proven in Case 2.

The proof of (6.17) in Case 3 is analogous to that in Case 2 (the main
difference being that Lemma 6.52(c) is used in lieu of Lemma 6.52(b)).

Thus, (6.17) is proven in all possible cases. So we always have (6.17). In
other words,
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]$.

Now, forget that we fixed $i$. We hence have shown that
$\left(uv\right)\left[I_{\tau\left(i\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(i+1\right)}\right]$
for all $i\in\left\\{1,2,\ldots,p+q-1\right\\}$. This proves (6.16), and thus
completes our proof of Theorem 6.64(b).

(a) Let $\tau\in\operatorname{Sh}_{p,q}$ be such that

(6.18)
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right].$

Set $\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$. Then,
Proposition 6.60 yields that $\tau\in\operatorname{Sh}_{p,q}$ if and only if
$\operatorname*{iper}\left(\alpha\beta,\tau\right)\in\operatorname{Sh}_{n,m}$.
Since we know that $\tau\in\operatorname{Sh}_{p,q}$, we can deduce from this
that
$\operatorname*{iper}\left(\alpha\beta,\tau\right)\in\operatorname{Sh}_{n,m}$,
so that
$\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)\in\operatorname{Sh}_{n,m}$.

It remains to prove that the word $u\underset{\sigma}{\shuffle}v$ is the
lexicographically highest element of the multiset $u\shuffle v$.

It is clear that the multiset $u\shuffle v$ has some lexicographically highest
element. This element has the form $u\underset{\widetilde{\sigma}}{\shuffle}v$
for some $\widetilde{\sigma}\in\operatorname{Sh}_{n,m}$ (because any element
of this multiset has such a form). Consider this $\widetilde{\sigma}$. Theorem
6.64(b) (applied to $\widetilde{\sigma}$ instead of $\sigma$) yields that
there exists a unique permutation $\widetilde{\tau}\in\operatorname{Sh}_{p,q}$
satisfying
$\left(uv\right)\left[I_{\widetilde{\tau}\left(1\right)}\right]\geq\left(uv\right)\left[I_{\widetilde{\tau}\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\widetilde{\tau}\left(p+q\right)}\right]$
and
$\widetilde{\sigma}=\operatorname*{iper}\left(\alpha\beta,\widetilde{\tau}\right)$.
(What we call $\widetilde{\tau}$ here is what has been called $\tau$ in
Theorem 6.64(b).)

Now, the chain of inequalities
$\left(uv\right)\left[I_{\widetilde{\tau}\left(1\right)}\right]\geq\left(uv\right)\left[I_{\widetilde{\tau}\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\widetilde{\tau}\left(p+q\right)}\right]$
shows that the list
$\left(\left(uv\right)\left[I_{\widetilde{\tau}\left(1\right)}\right],\left(uv\right)\left[I_{\widetilde{\tau}\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\widetilde{\tau}\left(p+q\right)}\right]\right)$
is the result of sorting the list
$\left(\left(uv\right)\left[I_{1}\right],\left(uv\right)\left[I_{2}\right],\ldots,\left(uv\right)\left[I_{p+q}\right]\right)$
in decreasing order. But the chain of inequalities (6.18) shows that the list
$\left(\left(uv\right)\left[I_{\tau\left(1\right)}\right],\left(uv\right)\left[I_{\tau\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$
is the result of sorting the same list
$\left(\left(uv\right)\left[I_{1}\right],\left(uv\right)\left[I_{2}\right],\ldots,\left(uv\right)\left[I_{p+q}\right]\right)$
in decreasing order. So each of the two lists
$\left(\left(uv\right)\left[I_{\widetilde{\tau}\left(1\right)}\right],\left(uv\right)\left[I_{\widetilde{\tau}\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\widetilde{\tau}\left(p+q\right)}\right]\right)$
and
$\left(\left(uv\right)\left[I_{\tau\left(1\right)}\right],\left(uv\right)\left[I_{\tau\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$
is the result of sorting one and the same list
$\left(\left(uv\right)\left[I_{1}\right],\left(uv\right)\left[I_{2}\right],\ldots,\left(uv\right)\left[I_{p+q}\right]\right)$
in decreasing order. Since the result of sorting a given list in decreasing
order is unique, this yields

$\left(\left(uv\right)\left[I_{\widetilde{\tau}\left(1\right)}\right],\left(uv\right)\left[I_{\widetilde{\tau}\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\widetilde{\tau}\left(p+q\right)}\right]\right)=\left(\left(uv\right)\left[I_{\tau\left(1\right)}\right],\left(uv\right)\left[I_{\tau\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right).$

Hence,

(6.19)
$\left(uv\right)\left[I_{\widetilde{\tau}\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\widetilde{\tau}\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\widetilde{\tau}\left(p+q\right)}\right]=\left(uv\right)\left[I_{\tau\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\tau\left(p+q\right)}\right].$

But Lemma 6.62 yields

(6.20)
$u\underset{\sigma}{\shuffle}v=\left(uv\right)\left[I_{\tau\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\tau\left(p+q\right)}\right].$

Meanwhile, Lemma 6.62 (applied to $\widetilde{\tau}$ and $\widetilde{\sigma}$
instead of $\tau$ and $\sigma$) yields

$\displaystyle u\underset{\widetilde{\sigma}}{\shuffle}v$
$\displaystyle=\left(uv\right)\left[I_{\widetilde{\tau}\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\widetilde{\tau}\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\widetilde{\tau}\left(p+q\right)}\right]$
$\displaystyle=\left(uv\right)\left[I_{\tau\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\
\ \ \ \ \ \ \ \ \ \left(\text{by
(\ref{pf.thm.shuffle.lyndon.full.a.5})}\right)$
$\displaystyle=u\underset{\sigma}{\shuffle}v\ \ \ \ \ \ \ \ \ \ \left(\text{by
(\ref{pf.thm.shuffle.lyndon.full.a.6})}\right).$

Thus, $u\underset{\sigma}{\shuffle}v$ is the lexicographically highest element
of the multiset $u\shuffle v$ (since we know that
$u\underset{\widetilde{\sigma}}{\shuffle}v$ is the lexicographically highest
element of the multiset $u\shuffle v$). This proves Theorem 6.64(a). ∎

Now, in order to prove Theorem 6.44, we record a very simple fact about
counting shuffles:

######  Proposition 6.65.

Let $p\in{\mathbb{N}}$ and $q\in{\mathbb{N}}$. Let $\mathfrak{W}$ be a totally
ordered set, and let
$h:\left\\{1,2,\ldots,p+q\right\\}\rightarrow\mathfrak{W}$ be a map. Assume
that $h\left(1\right)\geq h\left(2\right)\geq\cdots\geq h\left(p\right)$ and
$h\left(p+1\right)\geq h\left(p+2\right)\geq\cdots\geq h\left(p+q\right)$.

For every $w\in\mathfrak{W}$, let $\mathfrak{a}\left(w\right)$ denote the
number of all $i\in\left\\{1,2,\ldots,p\right\\}$ satisfying
$h\left(i\right)=w$, and let $\mathfrak{b}\left(w\right)$ denote the number of
all $i\in\left\\{p+1,p+2,\ldots,p+q\right\\}$ satisfying $h\left(i\right)=w$.

Then, the number of $\tau\in\operatorname{Sh}_{p,q}$ satisfying
$h\left(\tau\left(1\right)\right)\geq
h\left(\tau\left(2\right)\right)\geq\cdots\geq
h\left(\tau\left(p+q\right)\right)$ is
$\prod_{w\in\mathfrak{W}}\dbinom{\mathfrak{a}\left(w\right)+\mathfrak{b}\left(w\right)}{\mathfrak{a}\left(w\right)}$.
(Of course, all but finitely many factors of this product are $1$.)

######  Exercise 6.66.

Prove Proposition 6.65.

###### Proof of Theorem 6.44..

Let $n=\ell\left(u\right)$ and $m=\ell\left(v\right)$. Define $\alpha$,
$\beta$ and $\left(I_{1},I_{2},\ldots,I_{p+q}\right)$ as in Theorem 6.64.

Since $\left(a_{1},a_{2},\ldots,a_{p}\right)$ is the CFL factorization of $u$,
we have $a_{1}\geq a_{2}\geq\cdots\geq a_{p}$ and $a_{1}a_{2}\cdots a_{p}=u$.
Similarly, $b_{1}\geq b_{2}\geq\cdots\geq b_{q}$ and $b_{1}b_{2}\cdots
b_{q}=v$.

From (6.6), we see that $\left(uv\right)\left[I_{i}\right]=a_{i}$ for every
$i\in\left\\{1,2,\ldots,p\right\\}$. From (6.7), we see that
$\left(uv\right)\left[I_{i}\right]=b_{i-p}$ for every
$i\in\left\\{p+1,p+2,\ldots,p+q\right\\}$. Combining these two equalities, we
obtain

(6.21) $\left(uv\right)\left[I_{i}\right]=\left\\{\begin{array}[c]{c}a_{i},\ \
\ \ \ \ \ \ \ \ \text{if }i\leq p;\\\ b_{i-p},\ \ \ \ \ \ \ \ \ \ \text{if
}i>p\end{array}\right.\ \ \ \ \ \ \ \ \ \ \text{for every
}i\in\left\\{1,2,\ldots,p+q\right\\}.$

In other words,

(6.22)
$\left(\left(uv\right)\left[I_{1}\right],\left(uv\right)\left[I_{2}\right],\ldots,\left(uv\right)\left[I_{p+q}\right]\right)=\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right).$

(a) Let $z$ be the lexicographically highest element of the multiset
$u\shuffle v$. We must prove that $z=c_{1}c_{2}\cdots c_{p+q}$.

Since $z\in u\shuffle v$, we can write $z$ in the form
$u\underset{\sigma}{\shuffle}v$ for some $\sigma\in\operatorname{Sh}_{n,m}$
(since we can write any element of $u\shuffle v$ in this form). Consider this
$\sigma$. Then, $u\underset{\sigma}{\shuffle}v=z$ is the lexicographically
highest element of the multiset $u\shuffle v$. Hence, Theorem 6.64(b) yields
that there exists a unique permutation $\tau\in\operatorname{Sh}_{p,q}$
satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$
and $\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$. Consider this
$\tau$.

Now, $\tau\in\operatorname{Sh}_{p,q}\subset\mathfrak{S}_{p+q}$ is a
permutation, and thus the list
$\left(\left(uv\right)\left[I_{\tau\left(1\right)}\right],\left(uv\right)\left[I_{\tau\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$
is a rearrangement of the list
$\left(\left(uv\right)\left[I_{1}\right],\left(uv\right)\left[I_{2}\right],\ldots,\left(uv\right)\left[I_{p+q}\right]\right)$.
Due to (6.22), this rewrites as follows: The list
$\left(\left(uv\right)\left[I_{\tau\left(1\right)}\right],\left(uv\right)\left[I_{\tau\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$
is a rearrangement of the list
$\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right)$. Hence,
$\left(\left(uv\right)\left[I_{\tau\left(1\right)}\right],\left(uv\right)\left[I_{\tau\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$
is the result of sorting the list
$\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right)$ in decreasing
order (since
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$).
But since the result of sorting the list
$\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right)$ in decreasing
order is $\left(c_{1},c_{2},\ldots,c_{p+q}\right)$, this becomes

$\left(\left(uv\right)\left[I_{\tau\left(1\right)}\right],\left(uv\right)\left[I_{\tau\left(2\right)}\right],\ldots,\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)=\left(c_{1},c_{2},\ldots,c_{p+q}\right).$

Hence,

$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]=c_{1}\cdot
c_{2}\cdot\cdots\cdot c_{p+q}.$

But Lemma 6.62 yields

$u\underset{\sigma}{\shuffle}v=\left(uv\right)\left[I_{\tau\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\tau\left(p+q\right)}\right].$

Altogether, we have

$\displaystyle
z=u\underset{\sigma}{\shuffle}v=\left(uv\right)\left[I_{\tau\left(1\right)}\right]\cdot\left(uv\right)\left[I_{\tau\left(2\right)}\right]\cdot\cdots\cdot\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]=c_{1}\cdot
c_{2}\cdot\cdots\cdot c_{p+q}=c_{1}c_{2}\cdots c_{p+q}.$

This proves Theorem 6.44(a).

(b) Recall that $u\shuffle v=\left\\{u\underset{\sigma}{\shuffle}v\ :\
\sigma\in\operatorname{Sh}_{n,m}\right\\}_{\text{multiset}}$. Hence,

$\displaystyle\left(\text{the multiplicity with which the lexicographically
highest element of the multiset}\right.$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left.u\shuffle v\text{ appears in the multiset }u\shuffle v\right)$
$\displaystyle=\left(\text{the number of all
}\sigma\in\operatorname{Sh}_{n,m}\text{ such that
}u\underset{\sigma}{\shuffle}v\text{ is the}\right.$ $\displaystyle\ \ \ \ \ \
\ \ \ \ \left.\text{lexicographically highest element of the multiset
}u\shuffle v\right).$

But for a given $\sigma\in\operatorname{Sh}_{n,m}$, we know that
$u\underset{\sigma}{\shuffle}v$ is the lexicographically highest element of
the multiset $u\shuffle v$ if and only if $\sigma$ can be written in the form
$\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$ for some
$\tau\in\operatorname{Sh}_{p,q}$ satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$.
244244244In fact, the “if” part of this assertion follows from Theorem
6.64(a), whereas its “only if” part follows from Theorem 6.64(b). Hence,

$\displaystyle\left(\text{the number of all
}\sigma\in\operatorname{Sh}_{n,m}\text{ such that
}u\underset{\sigma}{\shuffle}v\text{ is the}\right.$ $\displaystyle\ \ \ \ \ \
\ \ \ \ \left.\text{lexicographically highest element of the multiset
}u\shuffle v\right)$ $\displaystyle=\left(\text{the number of all
}\sigma\in\operatorname{Sh}_{n,m}\text{ which can be written in the form
}\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left.\text{for some
}\tau\in\operatorname{Sh}_{p,q}\text{ satisfying
}\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$
$\displaystyle=\left(\text{the number of all
}\tau\in\operatorname{Sh}_{p,q}\text{ satisfying
}\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$

(because if a $\sigma\in\operatorname{Sh}_{n,m}$ can be written in the form
$\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$ for some
$\tau\in\operatorname{Sh}_{p,q}$ satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$,
then $\sigma$ can be written uniquely in this form245245245Proof. Let
$\sigma\in\operatorname{Sh}_{n,m}$ be such that $\sigma$ can be written in the
form $\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$ for some
$\tau\in\operatorname{Sh}_{p,q}$ satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$.
Then, the word $u\underset{\sigma}{\shuffle}v$ is the lexicographically
highest element of the multiset $u\shuffle v$ (according to Theorem 6.64(a)).
Hence, there exists a unique permutation $\tau\in\operatorname{Sh}_{p,q}$
satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$
and $\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$ (according to
Theorem 6.64(b)). In other words, $\sigma$ can be written uniquely in the form
$\sigma=\operatorname*{iper}\left(\alpha\beta,\tau\right)$ for some
$\tau\in\operatorname{Sh}_{p,q}$ satisfying
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$,
qed.). Thus,

$\displaystyle\left(\text{the multiplicity with which the lexicographically
highest element of the multiset}\right.$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left.u\shuffle v\text{ appears in the multiset }u\shuffle v\right)$
$\displaystyle=\left(\text{the number of all
}\sigma\in\operatorname{Sh}_{n,m}\text{ such that
}u\underset{\sigma}{\shuffle}v\text{ is the}\right.$ $\displaystyle\ \ \ \ \ \
\ \ \ \ \left.\text{lexicographically highest element of the multiset
}u\shuffle v\right)$ (6.23) $\displaystyle=\left(\text{the number of all
}\tau\in\operatorname{Sh}_{p,q}\text{ satisfying
}\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right).$

Now, define a map $h:\left\\{1,2,\ldots,p+q\right\\}\rightarrow\mathfrak{L}$
by

$h\left(i\right)=\left\\{\begin{array}[c]{c}a_{i},\ \ \ \ \ \ \ \ \ \ \text{if
}i\leq p;\\\ b_{i-p},\ \ \ \ \ \ \ \ \ \ \text{if }i>p\end{array}\right.\ \ \
\ \ \ \ \ \ \ \text{for every }i\in\left\\{1,2,\ldots,p+q\right\\}.$

Then, $h\left(1\right)\geq h\left(2\right)\geq\cdots\geq h\left(p\right)$
(because this is just a rewriting of $a_{1}\geq a_{2}\geq\cdots\geq a_{p}$)
and $h\left(p+1\right)\geq h\left(p+2\right)\geq\cdots\geq h\left(p+q\right)$
(since this is just a rewriting of $b_{1}\geq b_{2}\geq\cdots\geq b_{q}$). For
every $w\in\mathfrak{L}$, the number of all
$i\in\left\\{1,2,\ldots,p\right\\}$ satisfying $h\left(i\right)=w$ is

$\displaystyle\left|\left\\{i\in\left\\{1,2,\ldots,p\right\\}\ \mid\
\underbrace{h\left(i\right)}_{=a_{i}}=w\right\\}\right|$
$\displaystyle=\left|\left\\{i\in\left\\{1,2,\ldots,p\right\\}\ \mid\
a_{i}=w\right\\}\right|$ $\displaystyle=\left(\text{the number of terms in the
list }\left(a_{1},a_{2},\ldots,a_{p}\right)\text{ which are equal to
}w\right)$ $\displaystyle=\left(\text{the number of terms in the CFL
factorization of }u\text{ which are equal to }w\right)$ $\displaystyle\ \ \ \
\ \ \ \ \ \ \left(\text{since the list
}\left(a_{1},a_{2},\ldots,a_{p}\right)\text{ is the CFL factorization of
}u\right)$ $\displaystyle=\operatorname{mult}_{w}u$

(because $\operatorname{mult}_{w}u$ is defined as the number of terms in the
CFL factorization of $u$ which are equal to $w$). Similarly, for every
$w\in\mathfrak{L}$, the number of all
$i\in\left\\{p+1,p+2,\ldots,p+q\right\\}$ satisfying $h\left(i\right)=w$
equals $\operatorname{mult}_{w}v$. Thus, we can apply Proposition 6.65 to
$\mathfrak{W}=\mathfrak{L}$,
$\mathfrak{a}\left(w\right)=\operatorname{mult}_{w}u$ and
$\mathfrak{b}\left(w\right)=\operatorname{mult}_{w}v$. As a result, we see
that the number of $\tau\in\operatorname{Sh}_{p,q}$ satisfying
$h\left(\tau\left(1\right)\right)\geq
h\left(\tau\left(2\right)\right)\geq\cdots\geq
h\left(\tau\left(p+q\right)\right)$ is
$\prod_{w\in\mathfrak{L}}\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}$.
In other words,

$\displaystyle\left(\text{the number of all
}\tau\in\operatorname{Sh}_{p,q}\text{ satisfying
}h\left(\tau\left(1\right)\right)\geq
h\left(\tau\left(2\right)\right)\geq\cdots\geq
h\left(\tau\left(p+q\right)\right)\right)$ (6.24)
$\displaystyle=\prod_{w\in\mathfrak{L}}\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}.$

But for every $i\in\left\\{1,2,\ldots,p+q\right\\}$, we have

$h\left(i\right)=\left\\{\begin{array}[c]{c}a_{i},\ \ \ \ \ \ \ \ \ \ \text{if
}i\leq p;\\\ b_{i-p},\ \ \ \ \ \ \ \ \ \ \text{if
}i>p\end{array}\right.=\left(uv\right)\left[I_{i}\right]\ \ \ \ \ \ \ \ \ \
\left(\text{by (\ref{pf.thm.shuffle.lyndon.used.uvIi})}\right).$

Hence, for any $\tau\in\operatorname{Sh}_{p,q}$, the condition
$h\left(\tau\left(1\right)\right)\geq
h\left(\tau\left(2\right)\right)\geq\cdots\geq
h\left(\tau\left(p+q\right)\right)$ is equivalent to
$\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]$.
Thus,

$\displaystyle\left(\text{the number of all
}\tau\in\operatorname{Sh}_{p,q}\text{ satisfying
}\underbrace{h\left(\tau\left(1\right)\right)\geq
h\left(\tau\left(2\right)\right)\geq\cdots\geq
h\left(\tau\left(p+q\right)\right)}_{\begin{subarray}{c}\text{this is
equivalent to}\\\
\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\end{subarray}}\right)$
$\displaystyle=\left(\text{the number of all
}\tau\in\operatorname{Sh}_{p,q}\text{ satisfying
}\left(uv\right)\left[I_{\tau\left(1\right)}\right]\geq\left(uv\right)\left[I_{\tau\left(2\right)}\right]\geq\cdots\geq\left(uv\right)\left[I_{\tau\left(p+q\right)}\right]\right)$
$\displaystyle=\left(\text{the multiplicity with which the lexicographically
highest element of the multiset}\right.$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left.u\shuffle v\text{ appears in the multiset }u\shuffle v\right)$

(by (6.23)). Compared with (6.24), this yields

$\displaystyle\left(\text{the multiplicity with which the lexicographically
highest element of the multiset}\right.$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left.u\shuffle v\text{ appears in the multiset }u\shuffle v\right)$
$\displaystyle=\prod_{w\in\mathfrak{L}}\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}.$

This proves Theorem 6.44(b).

(c) We shall use the notations of Theorem 6.44(a) and Theorem 6.44(b).

Assume that $a_{i}\geq b_{j}$ for every $i\in\left\\{1,2,\ldots,p\right\\}$
and $j\in\left\\{1,2,\ldots,q\right\\}$. This, combined with $a_{1}\geq
a_{2}\geq\cdots\geq a_{p}$ and $b_{1}\geq b_{2}\geq\cdots\geq b_{q}$, yields
that $a_{1}\geq a_{2}\geq\cdots\geq a_{p}\geq b_{1}\geq b_{2}\geq\cdots\geq
b_{q}$. Thus, the list
$\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right)$ is weakly
decreasing. Thus, the result of sorting the list
$\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right)$ in decreasing
order is the list
$\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right)$ itself. But
since this result is $\left(c_{1},c_{2},\ldots,c_{p+q}\right)$, this shows
that
$\left(c_{1},c_{2},\ldots,c_{p+q}\right)=\left(a_{1},a_{2},\ldots,a_{p},b_{1},b_{2},\ldots,b_{q}\right)$.
Hence, $c_{1}c_{2}\cdots c_{p+q}=\underbrace{a_{1}a_{2}\cdots
a_{p}}_{=u}\underbrace{b_{1}b_{2}\cdots b_{q}}_{=v}=uv$. Now, Theorem 6.44(a)
yields that the lexicographically highest element of the multiset $u\shuffle
v$ is $c_{1}c_{2}\cdots c_{p+q}=uv$. This proves Theorem 6.44(c).

(d) We shall use the notations of Theorem 6.44(a) and Theorem 6.44(b).

Assume that $a_{i}>b_{j}$ for every $i\in\left\\{1,2,\ldots,p\right\\}$ and
$j\in\left\\{1,2,\ldots,q\right\\}$. Thus, $a_{i}\geq b_{j}$ for every
$i\in\left\\{1,2,\ldots,p\right\\}$ and $j\in\left\\{1,2,\ldots,q\right\\}$.
Hence, Theorem 6.44(c) yields that the lexicographically highest element of
the multiset $u\shuffle v$ is $uv$. Therefore, Theorem 6.44(b) shows that the
multiplicity with which this word $uv$ appears in the multiset $u\shuffle v$
is
$\prod_{w\in\mathfrak{L}}\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}$.

Now, every $w\in\mathfrak{L}$ satisfies
$\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}=1$
246246246Proof. Assume the contrary. Then, there exists at least one
$w\in\mathfrak{L}$ such that
$\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}\neq
1$. Consider this $w$. Both $\operatorname{mult}_{w}u$ and
$\operatorname{mult}_{w}v$ must be positive (since
$\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}\neq
1$). Since $\operatorname{mult}_{w}u$ is positive, there must be at least one
term in the CFL factorization of $u$ which is equal to $w$. In other words,
there is at least one $i\in\left\\{1,2,\ldots,p\right\\}$ satisfying $a_{i}=w$
(since $\left(a_{1},a_{2},\ldots,a_{p}\right)$ is the CFL factorization of
$u$). Similarly, there is at least one $j\in\left\\{1,2,\ldots,q\right\\}$
satisfying $b_{j}=w$. These $i$ and $j$ satisfy $a_{i}=w=b_{j}$, which
contradicts $a_{i}>b_{j}$. This contradiction shows that our assumption was
false, qed.. Thus, as we know, the multiplicity with which this word $uv$
appears in the multiset $u\shuffle v$ is
$\prod_{w\in\mathfrak{L}}\underbrace{\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}}_{=1}=\prod_{w\in\mathfrak{L}}1=1$.
This proves Theorem 6.44(d).

(e) We shall use the notations of Theorem 6.44(a) and Theorem 6.44(b).

Since $u$ is a Lyndon word, the $1$-tuple $\left(u\right)$ is the CFL
factorization of $u$. Hence, we can apply Theorem 6.44(c) to $1$ and
$\left(u\right)$ instead of $p$ and $\left(a_{1},a_{2},\ldots,a_{p}\right)$.
As a result, we conclude that the lexicographically highest element of the
multiset $u\shuffle v$ is $uv$. It remains to prove that the multiplicity with
which this word $uv$ appears in the multiset $u\shuffle v$ is
$\operatorname{mult}_{u}v+1$.

For every $w\in\mathfrak{L}$ satisfying $w\neq u$, we have

(6.25) $\operatorname{mult}_{w}u=0$ 247247247Proof of (6.25): Let
$w\in\mathfrak{L}$ be such that $w\neq u$. Then, the number of terms in the
list $\left(u\right)$ which are equal to $w$ is $0$. Since $\left(u\right)$ is
the CFL factorization of $u$, this rewrites as follows: The number of terms in
the CFL factorization of $u$ which are equal to $w$ is $0$. In other words,
$\operatorname{mult}_{w}u=0$. This proves (6.25).

. Also, $\operatorname{mult}_{u}u=1$ (for a similar reason). But $uv$ is the
lexicographically highest element of the multiset $u\shuffle v$. Hence, the
multiplicity with which the word $uv$ appears in the multiset $u\shuffle v$ is
the multiplicity with which the lexicographically highest element of the
multiset $u\shuffle v$ appears in the multiset $u\shuffle v$. According to
Theorem 6.44(b), the latter multiplicity is

$\displaystyle\prod_{w\in\mathfrak{L}}\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}$
$\displaystyle=\underbrace{\dbinom{\operatorname{mult}_{u}u+\operatorname{mult}_{u}v}{\operatorname{mult}_{u}u}}_{\begin{subarray}{c}=\dbinom{1+\operatorname{mult}_{u}v}{1}\\\
\text{(since
}\operatorname{mult}_{u}u=1\text{)}\end{subarray}}\cdot\prod_{\begin{subarray}{c}w\in\mathfrak{L;}\\\
w\neq
u\end{subarray}}\underbrace{\dbinom{\operatorname{mult}_{w}u+\operatorname{mult}_{w}v}{\operatorname{mult}_{w}u}}_{\begin{subarray}{c}=\dbinom{0+\operatorname{mult}_{w}v}{0}\\\
\text{(since }\operatorname{mult}_{w}u=0\text{ (by
(\ref{pf.thm.shuffle.lyndon.used.e.0})))}\end{subarray}}\ \ \ \ \ \ \ \ \ \
\left(\text{since }u\in\mathfrak{L}\right)$
$\displaystyle=\underbrace{\dbinom{1+\operatorname{mult}_{u}v}{1}}_{=1+\operatorname{mult}_{u}v=\operatorname{mult}_{u}v+1}\cdot\prod_{\begin{subarray}{c}w\in\mathfrak{L;}\\\
w\neq
u\end{subarray}}\underbrace{\dbinom{0+\operatorname{mult}_{w}v}{0}}_{=1}=\left(\operatorname{mult}_{u}v+1\right)\cdot\underbrace{\prod_{\begin{subarray}{c}w\in\mathfrak{L;}\\\
w\neq u\end{subarray}}1}_{=1}=\operatorname{mult}_{u}v+1.$

This proves Theorem 6.44(e). ∎

As an application of our preceding results, we can prove a further necessary
and sufficient criterion for a word to be Lyndon; this criterion is due to
Chen/Fox/Lyndon [34,
$\mathfrak{A}^{\prime\prime}=\mathfrak{A}^{\prime\prime\prime\prime}$]:

######  Exercise 6.67.

Let $w\in\mathfrak{A}^{\ast}$ be a nonempty word. Prove that $w$ is Lyndon if
and only if for any two nonempty words $u\in\mathfrak{A}^{\ast}$ and
$v\in\mathfrak{A}^{\ast}$ satisfying $w=uv$, there exists at least one $s\in
u\shuffle v$ satisfying $s>w$.

###  6.3. Radford’s theorem on the shuffle algebra

We recall that our goal in Chapter 6 is to exhibit an algebraically
independent generating set of the $\mathbf{k}$-algebra $\operatorname{QSym}$.
Having the notion of Lyndon words – which will, to some extent, but not
literally, parametrize this generating set – in place, we could start the
construction of this generating set immediately. However, it might come off as
rather unmotivated this way, and so we begin with some warmups. First, we
shall prove Radford’s theorem on the shuffle algebra.

######  Definition 6.68.

A polynomial algebra will mean a $\mathbf{k}$-algebra which is isomorphic to
the polynomial ring $\mathbf{k}\left[x_{i}\ \mid\ i\in I\right]$ as a
$\mathbf{k}$-algebra (for some indexing set $I$). Note that $I$ need not be
finite.

Equivalently, a polynomial algebra can be defined as a $\mathbf{k}$-algebra
which has an algebraically independent (over $\mathbf{k}$) generating set. Yet
equivalently, a polynomial algebra can be defined as a $\mathbf{k}$-algebra
which is isomorphic to the symmetric algebra of a free $\mathbf{k}$-module.

Keep in mind that when we say that a certain bialgebra $A$ is a polynomial
algebra, we are making no statement about the coalgebra structure on $A$. The
isomorphism from $A$ to the symmetric algebra of a free $\mathbf{k}$-module
need not be a coalgebra isomorphism, and the algebraically independent
generating set of $A$ need not consist of primitives. Thus, showing that a
bialgebra $A$ is a polynomial algebra does not trivialize the study of its
bialgebraic structure.

######  Remark 6.69.

Let $V$ be a $\mathbf{k}$-module, and let $\mathfrak{A}$ be a totally ordered
set. Let $b_{a}$ be an element of $V$ for every $a\in\mathfrak{A}$. Consider
the shuffle algebra $\operatorname*{Sh}\left(V\right)$ (defined in Definition
1.73).

For every word $w\in\mathfrak{A}^{\ast}$ over the alphabet $\mathfrak{A}$, let
us define an element $b_{w}$ of $\operatorname*{Sh}\left(V\right)$ by
$b_{w}=b_{w_{1}}b_{w_{2}}\cdots b_{w_{\ell}}$, where $\ell$ is the length of
$w$. (The multiplication used here is that of $T\left(V\right)$, not that of
$\operatorname*{Sh}\left(V\right)$; the latter is denoted by
$\underline{\shuffle}$.)

Let $u\in\mathfrak{A}^{\ast}$ and $v\in\mathfrak{A}^{\ast}$ be two words over
the alphabet $\mathfrak{A}$. Let $n=\ell\left(u\right)$ and
$m=\ell\left(v\right)$. Then,

$b_{u}\underline{\shuffle}b_{v}=\sum_{\sigma\in\operatorname{Sh}_{n,m}}b_{u\underset{\sigma}{\shuffle}v}.$

######  Exercise 6.70.

Prove Remark 6.69.

[Hint: This follows from the definition of $\underline{\shuffle}$.]

We can now state Radford’s theorem [141, Theorem 3.1.1(e)]:

######  Theorem 6.71.

Assume that $\mathbb{Q}$ is a subring of $\mathbf{k}$. Let $V$ be a free
$\mathbf{k}$-module with a basis $\left(b_{a}\right)_{a\in\mathfrak{A}}$,
where $\mathfrak{A}$ is a totally ordered set. Then, the shuffle algebra
$\operatorname*{Sh}\left(V\right)$ (defined in Definition 1.73) is a
polynomial $\mathbf{k}$-algebra. An algebraically independent generating set
of $\operatorname*{Sh}\left(V\right)$ can be constructed as follows:

For every word $w\in\mathfrak{A}^{\ast}$ over the alphabet $\mathfrak{A}$, let
us define an element $b_{w}$ of $\operatorname*{Sh}\left(V\right)$ by
$b_{w}=b_{w_{1}}b_{w_{2}}\cdots b_{w_{\ell}}$, where $\ell$ is the length of
$w$. (The multiplication used here is that of $T\left(V\right)$, not that of
$\operatorname*{Sh}\left(V\right)$; the latter is denoted by
$\underline{\shuffle}$.) Let $\mathfrak{L}$ denote the set of all Lyndon words
over the alphabet $\mathfrak{A}$. Then,
$\left(b_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically independent
generating set of the $\mathbf{k}$-algebra $\operatorname*{Sh}\left(V\right)$.

######  Example 6.72.

For this example, let $\mathfrak{A}$ be the alphabet
$\left\\{1,2,3,\ldots\right\\}$ with total order given by $1<2<3<\cdots$, and
assume that $\mathbb{Q}$ is a subring of $\mathbf{k}$. Let $V$ be the free
$\mathbf{k}$-module with basis $\left(b_{a}\right)_{a\in\mathfrak{A}}$. We use
the notations of Theorem 6.71. Then, Theorem 6.71 yields that
$\left(b_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically independent
generating set of the $\mathbf{k}$-algebra $\operatorname*{Sh}\left(V\right)$.
Here are some examples of elements of $\operatorname*{Sh}\left(V\right)$
written as polynomials in this generating set:

$\displaystyle b_{12}$ $\displaystyle=b_{12}\ \ \ \ \ \ \ \ \ \
\left(\text{the word }12\text{ itself is Lyndon}\right);$ $\displaystyle
b_{21}$ $\displaystyle=b_{1}\underline{\shuffle}b_{2}-b_{12};$ $\displaystyle
b_{11}$ $\displaystyle=\dfrac{1}{2}b_{1}\underline{\shuffle}b_{1};$
$\displaystyle b_{123}$ $\displaystyle=b_{123}\ \ \ \ \ \ \ \ \ \
\left(\text{the word }123\text{ itself is Lyndon}\right);$ $\displaystyle
b_{132}$ $\displaystyle=b_{132}\ \ \ \ \ \ \ \ \ \ \left(\text{the word
}132\text{ itself is Lyndon}\right);$ $\displaystyle b_{213}$
$\displaystyle=b_{2}\underline{\shuffle}b_{13}-b_{123}-b_{132};$
$\displaystyle b_{231}$
$\displaystyle=b_{23}\underline{\shuffle}b_{1}-b_{2}\underline{\shuffle}b_{13}+b_{132};$
$\displaystyle b_{312}$
$\displaystyle=b_{3}\underline{\shuffle}b_{12}-b_{123}-b_{132};$
$\displaystyle b_{321}$
$\displaystyle=b_{1}\underline{\shuffle}b_{2}\underline{\shuffle}b_{3}-b_{23}\underline{\shuffle}b_{1}-b_{3}\underline{\shuffle}b_{12}+b_{123};$
$\displaystyle b_{112}$ $\displaystyle=b_{112}\ \ \ \ \ \ \ \ \ \
\left(\text{the word }112\text{ itself is Lyndon}\right);$ $\displaystyle
b_{121}$ $\displaystyle=b_{12}\underline{\shuffle}b_{1}-2b_{112};$
$\displaystyle b_{1212}$
$\displaystyle=\dfrac{1}{2}b_{12}\underline{\shuffle}b_{12}-2b_{1122};$
$\displaystyle b_{4321}$
$\displaystyle=b_{1}\underline{\shuffle}b_{2}\underline{\shuffle}b_{3}\underline{\shuffle}b_{4}-b_{1}\underline{\shuffle}b_{2}\underline{\shuffle}b_{34}-b_{1}\underline{\shuffle}b_{23}\underline{\shuffle}b_{4}-b_{12}\underline{\shuffle}b_{3}\underline{\shuffle}b_{4}$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+b_{1}\underline{\shuffle}b_{234}+b_{12}\underline{\shuffle}b_{34}+b_{123}\underline{\shuffle}b_{4}-b_{1234}.$
248248248A pattern emerges in the formulas for $b_{21}$, $b_{321}$ and
$b_{4321}$: for every $n\in{\mathbb{N}}$, we have
$b_{\left(n,n-1,\ldots,1\right)}=\sum_{\alpha\in\operatorname{Comp}_{n}}\left(-1\right)^{n-\ell\left(\alpha\right)}b_{\mathbf{d}_{1}\left(\alpha\right)}\underline{\shuffle}b_{\mathbf{d}_{2}\left(\alpha\right)}\underline{\shuffle}\cdots\underline{\shuffle}b_{\mathbf{d}_{\ell\left(\alpha\right)}\left(\alpha\right)},$
where
$\left(\mathbf{d}_{1}\left(\alpha\right)\right)\cdot\left(\mathbf{d}_{2}\left(\alpha\right)\right)\cdot\cdots\cdot\left(\mathbf{d}_{\ell\left(\alpha\right)}\left(\alpha\right)\right)$
is the factorization of the word $\left(1,2,\ldots,n\right)$ into factors of
length $\alpha_{1}$, $\alpha_{2}$, $\ldots$, $\alpha_{\ell}$ (where
$\alpha=\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)$). This can be
proved by an application of the principle of inclusion and exclusion (as it is
easy to see that for any composition $\alpha$ of $n$, the product
$b_{\mathbf{d}_{1}\left(\alpha\right)}\underline{\shuffle}b_{\mathbf{d}_{2}\left(\alpha\right)}\underline{\shuffle}\cdots\underline{\shuffle}b_{\mathbf{d}_{\ell\left(\alpha\right)}\left(\alpha\right)}$
equals the sum of $b_{\beta}$ for all words $\beta\in\mathfrak{S}_{n}$
satisfying $\operatorname*{Des}\left(\beta^{-1}\right)\subset
D\left(\alpha\right)$).

Note that Theorem 6.71 cannot survive without the condition that $\mathbb{Q}$
be a subring of $\mathbf{k}$. For instance, for any $v\in V$, we have
$v\underline{\shuffle}v=2vv$ in $\operatorname*{Sh}\left(V\right)$, which
vanishes if $2=0$ in $\mathbf{k}$; this stands in contrast to the fact that
polynomial $\mathbf{k}$-algebras are integral domains when $\mathbf{k}$ itself
is one. We will see that $\operatorname{QSym}$ is less sensitive towards the
base ring in this regard (although proving that $\operatorname{QSym}$ is a
polynomial algebra is much easier when $\mathbb{Q}$ is a subring of
$\mathbf{k}$).

In our proof of Theorem 6.71 (but not only there), we will use part (a) of the
following lemma249249249And in a later proof, we will also use its part (c)
(which is tailored for application to $\operatorname{QSym}$)., which makes
proving that certain families indexed by Lyndon words generate certain
$\mathbf{k}$-algebras more comfortable:

######  Lemma 6.73.

Let $A$ be a commutative $\mathbf{k}$-algebra. Let $\mathfrak{A}$ be a totally
ordered set. Let $\mathfrak{L}$ be the set of all Lyndon words over the
alphabet $\mathfrak{A}$. Let $b_{w}$ be an element of $A$ for every
$w\in\mathfrak{L}$. For every word $u\in\mathfrak{A}^{\ast}$, define an
element $\mathbf{b}_{u}$ of $A$ by $\mathbf{b}_{u}=b_{a_{1}}b_{a_{2}}\cdots
b_{a_{p}}$, where $\left(a_{1},a_{2},\ldots,a_{p}\right)$ is the CFL
factorization of $u$.

  * (a)

The family $\left(b_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically
independent generating set of the $\mathbf{k}$-algebra $A$ if and only if the
family $\left(\mathbf{b}_{u}\right)_{u\in\mathfrak{A}^{\ast}}$ is a basis of
the $\mathbf{k}$-module $A$.

  * (b)

The family $\left(b_{w}\right)_{w\in\mathfrak{L}}$ generates the
$\mathbf{k}$-algebra $A$ if and only if the family
$\left(\mathbf{b}_{u}\right)_{u\in\mathfrak{A}^{\ast}}$ spans the
$\mathbf{k}$-module $A$.

  * (c)

Assume that the $\mathbf{k}$-algebra $A$ is graded. Let
$\operatorname*{wt}:\mathfrak{A}\rightarrow\left\\{1,2,3,\ldots\right\\}$ be
any map such that for every $N\in\left\\{1,2,3,\ldots\right\\}$, the set
$\operatorname{wt}^{-1}\left(N\right)$ is finite.

For every word $w\in\mathfrak{A}^{\ast}$, define an element
$\operatorname*{Wt}\left(w\right)\in{\mathbb{N}}$ by
$\operatorname*{Wt}\left(w\right)=\operatorname*{wt}\left(w_{1}\right)+\operatorname*{wt}\left(w_{2}\right)+\cdots+\operatorname*{wt}\left(w_{k}\right)$,
where $k$ is the length of $w$.

Assume that for every $w\in\mathfrak{L}$, the element $b_{w}$ of $A$ is
homogeneous of degree $\operatorname*{Wt}\left(w\right)$.

Assume further that the $\mathbf{k}$-module $A$ has a basis
$\left(g_{u}\right)_{u\in\mathfrak{A}^{\ast}}$ having the property that for
every $u\in\mathfrak{A}^{\ast}$, the element $g_{u}$ of $A$ is homogeneous of
degree $\operatorname*{Wt}\left(u\right)$.

Assume also that the family $\left(b_{w}\right)_{w\in\mathfrak{L}}$ generates
the $\mathbf{k}$-algebra $A$.

Then, this family $\left(b_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically
independent generating set of the $\mathbf{k}$-algebra $A$.

######  Exercise 6.74.

Prove Lemma 6.73.

[Hint: For (a) and (b), notice that the $\mathbf{b}_{u}$ are the “monomials”
in the $b_{w}$. For (c), use Exercise 2.47(b) in every homogeneous component
of $A$.]

The main workhorse of our proof of Theorem 6.71 will be the following
consequence of Theorem 6.44(c):

######  Proposition 6.75.

Let $V$ be a free $\mathbf{k}$-module with a basis
$\left(b_{a}\right)_{a\in\mathfrak{A}}$, where $\mathfrak{A}$ is a totally
ordered set.

For every word $w\in\mathfrak{A}^{\ast}$ over the alphabet $\mathfrak{A}$, let
us define an element $b_{w}$ of $\operatorname*{Sh}\left(V\right)$ by
$b_{w}=b_{w_{1}}b_{w_{2}}\cdots b_{w_{\ell}}$, where $\ell$ is the length of
$w$. (The multiplication used here is that of $T\left(V\right)$, not that of
$\operatorname*{Sh}\left(V\right)$; the latter is denoted by
$\underline{\shuffle}$.)

For every word $u\in\mathfrak{A}^{\ast}$, define an element $\mathbf{b}_{u}$
by
$\mathbf{b}_{u}=b_{a_{1}}\underline{\shuffle}b_{a_{2}}\underline{\shuffle}\cdots\underline{\shuffle}b_{a_{p}}$,
where $\left(a_{1},a_{2},\ldots,a_{p}\right)$ is the CFL factorization of $u$.

If $\ell\in{\mathbb{N}}$ and if $x\in\mathfrak{A}^{\ell}$ is a word, then
there is a family
$\left(\eta_{x,y}\right)_{y\in\mathfrak{A}^{\ell}}\in{\mathbb{N}}^{\mathfrak{A}^{\ell}}$
of elements of ${\mathbb{N}}$ satisfying

$\mathbf{b}_{x}=\sum_{\begin{subarray}{c}y\in\mathfrak{A}^{\ell};\\\ y\leq
x\end{subarray}}\eta_{x,y}b_{y}$

and $\eta_{x,x}\neq 0$ (in ${\mathbb{N}}$).

Before we prove this, let us show a very simple lemma:

######  Lemma 6.76.

Let $\mathfrak{A}$ be a totally ordered set. Let $n\in{\mathbb{N}}$ and
$m\in{\mathbb{N}}$. Let $\sigma\in\operatorname{Sh}_{n,m}$.

(a) If $u$, $v$ and $v^{\prime}$ are three words satisfying
$\ell\left(u\right)=n$, $\ell\left(v\right)=m$,
$\ell\left(v^{\prime}\right)=m$ and $v^{\prime}<v$, then
$u\underset{\sigma}{\shuffle}v^{\prime}<u\underset{\sigma}{\shuffle}v$.

(b) If $u$, $u^{\prime}$ and $v$ are three words satisfying
$\ell\left(u\right)=n$, $\ell\left(u^{\prime}\right)=n$,
$\ell\left(v\right)=m$ and $u^{\prime}<u$, then
$u^{\prime}\underset{\sigma}{\shuffle}v<u\underset{\sigma}{\shuffle}v$.

(c) If $u$, $v$ and $v^{\prime}$ are three words satisfying
$\ell\left(u\right)=n$, $\ell\left(v\right)=m$,
$\ell\left(v^{\prime}\right)=m$ and $v^{\prime}\leq v$, then
$u\underset{\sigma}{\shuffle}v^{\prime}\leq u\underset{\sigma}{\shuffle}v$.

######  Exercise 6.77.

Prove Lemma 6.76.

######  Exercise 6.78.

Prove Proposition 6.75.

[Hint: Proceed by induction over $\ell$. In the induction step, apply Theorem
6.44(c)250250250Or Theorem 6.44(e), if you prefer. to $u=a_{1}$ and
$v=a_{2}a_{3}\cdots a_{p}$, where $\left(a_{1},a_{2},\ldots,a_{p}\right)$ is
the CFL factorization of $x$. Use Lemma 6.76 to get rid of smaller terms.]

######  Exercise 6.79.

Prove Theorem 6.71.

[Hint: According to Lemma 6.73(a), it suffices to show that the family
$\left(\mathbf{b}_{u}\right)_{u\in\mathfrak{A}^{\ast}}$ defined in Proposition
6.75 is a basis of the $\mathbf{k}$-module $\operatorname*{Sh}\left(V\right)$.
When $\mathfrak{A}$ is finite, the latter can be proven by triangularity using
Proposition 6.75. Reduce the general case to that of finite $\mathfrak{A}$.]

###  6.4. Polynomial freeness of $\operatorname{QSym}$: statement and easy
parts

######  Definition 6.80.

For the rest of Chapter 6, we introduce the following notations: We let
$\mathfrak{A}$ be the totally ordered set $\left\\{1,2,3,\ldots\right\\}$ with
its natural order (that is, $1<2<3<\cdots$.) Thus, the words over
$\mathfrak{A}$ are precisely the compositions. That is,
$\mathfrak{A}^{\ast}=\operatorname{Comp}$. We let $\mathfrak{L}$ denote the
set of all Lyndon words over $\mathfrak{A}$. These Lyndon words are also
called Lyndon compositions.

A natural question is how many Lyndon compositions of a given size exist.
While we will not use the answer, we nevertheless record it:

######  Exercise 6.81.

Show that the number of Lyndon compositions of size $n$ equals

$\dfrac{1}{n}\sum\limits_{d\mid
n}\mu\left(d\right)\left(2^{n/d}-1\right)=\dfrac{1}{n}\sum\limits_{d\mid
n}\mu\left(d\right)2^{n/d}-\delta_{n,1}$

for every positive integer $n$ (where “$\sum\limits_{d\mid n}$” means a sum
over all positive divisors of $n$, and where $\mu$ is the number-theoretic
Möbius function).

[Hint: One solution is similar to the solution of Exercise 6.29 using CFL
factorization. Another proceeds by defining a bijection between Lyndon
compositions and Lyndon words over a two-letter alphabet
$\left\\{\mathbf{0},\mathbf{1}\right\\}$ (with $\mathbf{0}<\mathbf{1}$) which
are $\neq\mathbf{1}$. 251251251This bijection is obtained by restricting the
bijection  $\displaystyle\operatorname{Comp}$
$\displaystyle\rightarrow\left\\{w\in\left\\{\mathbf{0},\mathbf{1}\right\\}^{\ast}\mid
w\text{ does not start with }\mathbf{1}\right\\},$
$\displaystyle\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)$
$\displaystyle\mapsto\mathbf{01}^{\alpha_{1}-1}\mathbf{01}^{\alpha_{2}-1}\cdots\mathbf{01}^{\alpha_{\ell}-1}$
(where $\mathbf{01}^{k}$ is to be read as
$\mathbf{0}\left(\mathbf{1}^{k}\right)$, not as
$\left(\mathbf{01}\right)^{k}$) to the set of Lyndon compositions. The idea
behind this bijection is well-known in the Grothendieck-Teichmüller community:
see, e.g., [74, §3.1] (and see [61, Note 5.16] for a different appearance of
this idea).]

Let us now state Hazewinkel’s result ([69, Theorem 8.1], [73, §6.7]) which is
the main goal of Chapter 6:

######  Theorem 6.82.

The $\mathbf{k}$-algebra $\operatorname{QSym}$ is a polynomial algebra. It is
isomorphic, as a graded $\mathbf{k}$-algebra, to the $\mathbf{k}$-algebra
$\mathbf{k}\left[x_{w}\ \mid\ w\in\mathfrak{L}\right]$. Here, the grading on
$\mathbf{k}\left[x_{w}\ \mid\ w\in\mathfrak{L}\right]$ is defined by setting
$\deg\left(x_{w}\right)=\sum_{i=1}^{\ell\left(w\right)}w_{i}$ for every
$w\in\mathfrak{L}$.

We shall prove Theorem 6.82 in the next section (Section 6.5). But the
particular case of Theorem 6.82 when $\mathbb{Q}$ is a subring of $\mathbf{k}$
can be proven more easily; we state it as a proposition:

######  Proposition 6.83.

Assume that $\mathbb{Q}$ is a subring of $\mathbf{k}$. Then, Theorem 6.82
holds.

We will give two proofs of Proposition 6.83 in this Section 6.4; a third proof
of Proposition 6.83 will immediately result from the proof of Theorem 6.82 in
Section 6.5. (There is virtue in giving three different proofs, as they all
construct different isomorphisms $\mathbf{k}\left[x_{w}\ \mid\
w\in\mathfrak{L}\right]\rightarrow\operatorname{QSym}$.)

Our first proof – originating in Malvenuto’s [117, Corollaire 4.20] – can be
given right away; it relies on Exercise 5.44:

###### First proof of Proposition 6.83..

Let $V$ be the free $\mathbf{k}$-module with basis
$\left(\mathfrak{b}_{n}\right)_{n\in\left\\{1,2,3,\ldots\right\\}}$. Endow the
$\mathbf{k}$-module $V$ with a grading by assigning to each basis vector
$\mathfrak{b}_{n}$ the degree $n$. Exercise 5.44(k) shows that
$\operatorname{QSym}$ is isomorphic to the shuffle algebra
$\operatorname{Sh}\left(V\right)$ (defined as in Proposition 1.73) as Hopf
algebras. By being a bit more careful, we can obtain the slightly stronger
result that $\operatorname{QSym}$ is isomorphic to the shuffle algebra
$\operatorname{Sh}\left(V\right)$ as graded Hopf algebras252252252Proof. In
the solution of Exercise 5.44(k), we have shown that $\operatorname{QSym}\cong
T\left(V\right)^{o}$ as graded Hopf algebras. But Remark 1.75(b) shows that
the Hopf algebra $T\left(V\right)^{o}$ is naturally isomorphic to the shuffle
algebra $\operatorname*{Sh}\left(V^{o}\right)$ as Hopf algebras; it is easy to
see that the natural isomorphism
$T\left(V\right)^{o}\rightarrow\operatorname*{Sh}\left(V^{o}\right)$ is graded
(because it is the direct sum of the isomorphisms $\left(V^{\otimes
n}\right)^{o}\rightarrow\left(V^{o}\right)^{\otimes n}$ over all
$n\in{\mathbb{N}}$, and each of these isomorphisms is graded). Hence,
$T\left(V\right)^{o}\cong\operatorname*{Sh}\left(V^{o}\right)$ as graded Hopf
algebras. But $V^{o}\cong V$ as graded $\mathbf{k}$-modules (since $V$ is of
finite type), and thus
$\operatorname*{Sh}\left(V^{o}\right)\cong\operatorname*{Sh}\left(V\right)$ as
graded Hopf algebras. Altogether, we obtain $\operatorname{QSym}\cong
T\left(V\right)^{o}\cong\operatorname*{Sh}\left(V^{o}\right)\cong\operatorname*{Sh}\left(V\right)$
as graded Hopf algebras, qed.. In particular,
$\operatorname{QSym}\cong\operatorname*{Sh}\left(V\right)$ as graded
$\mathbf{k}$-algebras.

Theorem 6.71 (applied to $b_{a}=\mathfrak{b}_{a}$) yields that the shuffle
algebra $\operatorname*{Sh}\left(V\right)$ is a polynomial
$\mathbf{k}$-algebra, and that an algebraically independent generating set of
$\operatorname*{Sh}\left(V\right)$ can be constructed as follows:

For every word $w\in\mathfrak{A}^{\ast}$ over the alphabet $\mathfrak{A}$, let
us define an element $\mathfrak{b}_{w}$ of $\operatorname*{Sh}\left(V\right)$
by
$\mathfrak{b}_{w}=\mathfrak{b}_{w_{1}}\mathfrak{b}_{w_{2}}\cdots\mathfrak{b}_{w_{\ell}}$,
where $\ell$ is the length of $w$. (The multiplication used here is that of
$T\left(V\right)$, not that of $\operatorname*{Sh}\left(V\right)$; the latter
is denoted by $\underline{\shuffle}$.) Then,
$\left(\mathfrak{b}_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically
independent generating set of the $\mathbf{k}$-algebra
$\operatorname*{Sh}\left(V\right)$.

For every $w\in\mathfrak{A}^{\ast}$, we have
$\mathfrak{b}_{w}=\mathfrak{b}_{w_{1}}\mathfrak{b}_{w_{2}}\cdots\mathfrak{b}_{w_{\ell\left(w\right)}}$
(by the definition of $\mathfrak{b}_{w}$). For every
$w\in\mathfrak{A}^{\ast}$, the element
$\mathfrak{b}_{w}=\mathfrak{b}_{w_{1}}\mathfrak{b}_{w_{2}}\cdots\mathfrak{b}_{w_{\ell\left(w\right)}}$
of $\operatorname*{Sh}\left(V\right)$ is homogeneous of degree
$\sum_{i=1}^{\ell\left(w\right)}\underbrace{\deg\left(\mathfrak{b}_{w_{i}}\right)}_{=w_{i}}=\sum_{i=1}^{\ell\left(w\right)}w_{i}$.

Now, define a grading on the $\mathbf{k}$-algebra $\mathbf{k}\left[x_{w}\
\mid\ w\in\mathfrak{L}\right]$ by setting
$\deg\left(x_{w}\right)=\sum_{i=1}^{\ell\left(w\right)}w_{i}$ for every
$w\in\mathfrak{L}$. By the universal property of the polynomial algebra
$\mathbf{k}\left[x_{w}\ \mid\ w\in\mathfrak{L}\right]$, we can define a
$\mathbf{k}$-algebra homomorphism $\Phi:\mathbf{k}\left[x_{w}\ \mid\
w\in\mathfrak{L}\right]\rightarrow\operatorname*{Sh}\left(V\right)$ by setting

$\Phi\left(x_{w}\right)=\mathfrak{b}_{w}\ \ \ \ \ \ \ \ \ \ \text{for every
}w\in\mathfrak{L}.$

This homomorphism $\Phi$ is a $\mathbf{k}$-algebra isomorphism (since
$\left(\mathfrak{b}_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically
independent generating set of the $\mathbf{k}$-algebra
$\operatorname*{Sh}\left(V\right)$) and is graded (because for every
$w\in\mathfrak{L}$, the element $\mathfrak{b}_{w}$ of
$\operatorname*{Sh}\left(V\right)$ is homogeneous of degree
$\sum_{i=1}^{\ell\left(w\right)}w_{i}=\deg\left(x_{w}\right)$). Thus, $\Phi$
is an isomorphism of graded $\mathbf{k}$-algebras. Hence,
$\operatorname*{Sh}\left(V\right)\cong\mathbf{k}\left[x_{w}\ \mid\
w\in\mathfrak{L}\right]$ as graded $\mathbf{k}$-algebras. Altogether,
$\operatorname{QSym}\cong\operatorname*{Sh}\left(V\right)\cong\mathbf{k}\left[x_{w}\
\mid\ w\in\mathfrak{L}\right]$ as graded $\mathbf{k}$-algebras. Thus,
$\operatorname{QSym}$ is a polynomial algebra. This proves Theorem 6.82 under
the assumption that $\mathbb{Q}$ be a subring of $\mathbf{k}$. In other words,
this proves Proposition 6.83. ∎

Our second proof of Proposition 6.83 comes from Hazewinkel/Gubareni/Kirichenko
[73] (where Proposition 6.83 appears as [73, Theorem 6.5.13]). This proof will
construct an explicit algebraically independent family generating the
$\mathbf{k}$-algebra $\operatorname{QSym}$. 253253253We could, of course,
obtain such a family from our above proof as well (this is done by Malvenuto
in [117, Corollaire 4.20]), but it won’t be a very simple one. The generating
set will be very unsophisticated: it will be
$\left(M_{\alpha}\right)_{\alpha\in\mathfrak{L}}$, where $\mathfrak{A}$ and
$\mathfrak{L}$ are as in Theorem 6.82. Here, we are using the fact that words
over the alphabet $\left\\{1,2,3,\ldots\right\\}$ are the same thing as
compositions, so, in particular, a monomial quasisymmetric function
$M_{\alpha}$ is defined for every such word $\alpha$.

It takes a bit of work to show that this family indeed fits the bill. We begin
with a corollary of Proposition 5.3 that is essentially obtained by throwing
away all non-bijective maps $f$:

######  Proposition 6.84.

Let $\alpha\in\mathfrak{A}^{\ast}$ and $\beta\in\mathfrak{A}^{\ast}$. Then,

$\displaystyle M_{\alpha}M_{\beta}$
$\displaystyle=\sum_{\gamma\in\alpha\shuffle\beta}M_{\gamma}+\left(\text{a sum
of terms of the form }M_{\delta}\text{ with
}\delta\in\mathfrak{A}^{\ast}\text{ satisfying
}\ell\left(\delta\right)<\ell\left(\alpha\right)+\ell\left(\beta\right)\right).$
254254254The sum $\sum_{\gamma\in\alpha\shuffle\beta}M_{\gamma}$ ranges over
the multiset $\alpha\shuffle\beta$; if an element appears several times in
$\alpha\shuffle\beta$, then it has accordingly many addends corresponding to
it.

######  Exercise 6.85.

Prove Proposition 6.84.

[Hint: Recall what was said about the $p=\ell+m$ case in Example 5.4.]

######  Corollary 6.86.

Let $\alpha\in\mathfrak{A}^{\ast}$ and $\beta\in\mathfrak{A}^{\ast}$. Then,
$M_{\alpha}M_{\beta}$ is a sum of terms of the form $M_{\delta}$ with
$\delta\in\mathfrak{A}^{\ast}$ satisfying
$\ell\left(\delta\right)\leq\ell\left(\alpha\right)+\ell\left(\beta\right)$.

######  Exercise 6.87.

Prove Corollary 6.86.

We now define a partial order on the compositions of a given nonnegative
integer:

######  Definition 6.88.

Let $n\in{\mathbb{N}}$. We define a binary relation
$\underset{\operatorname*{wll}}{\leq}$ on the set $\operatorname{Comp}_{n}$ as
follows: For two compositions $\alpha$ and $\beta$ in
$\operatorname{Comp}_{n}$, we set
$\alpha\underset{\operatorname*{wll}}{\leq}\beta$ if and only if

$\text{either }\ell\left(\alpha\right)<\ell\left(\beta\right)\text{ or
}\left(\ell\left(\alpha\right)=\ell\left(\beta\right)\text{ and
}\alpha\leq\beta\text{ in lexicographic order}\right)\text{.}$

This binary relation $\underset{\operatorname*{wll}}{\leq}$ is the smaller-or-
equal relation of a total order on $\operatorname{Comp}_{n}$; we refer to said
total order as the wll-order on $\operatorname{Comp}_{n}$, and we denote by
$\underset{\operatorname*{wll}}{<}$ the smaller relation of this total order.

Notice that if $\alpha$ and $\beta$ are two compositions satisfying
$\ell\left(\alpha\right)=\ell\left(\beta\right)$, then $\alpha\leq\beta$ in
lexicographic order if and only if $\alpha\leq\beta$ with respect to the
relation $\leq$ defined in Definition 6.1.

A remark about the name “wll-order” is in order. We have taken this notation
from [69, Definition 6.7.14], where it is used for an extension of this order
to the whole set $\operatorname{Comp}$. We will never use this extension, as
we will only ever compare two compositions of the same integer.255255255In
[69, Definition 6.7.14], the name “wll-order” is introduced as an abbreviation
for “weight first, then length, then lexicographic” (in the sense that two
compositions are first compared by their weights, then, if the weights are
equal, by their lengths, and finally, if the lengths are also equal, by the
lexicographic order). For us, the alternative explanation “word length, then
lexicographic” serves just as well.

We now state a fact which is similar (and plays a similar role) to Proposition
6.75:

######  Proposition 6.89.

For every composition $u\in\operatorname{Comp}=\mathfrak{A}^{\ast}$, define an
element $\mathbf{M}_{u}\in\operatorname{QSym}$ by
$\mathbf{M}_{u}=M_{a_{1}}M_{a_{2}}\cdots M_{a_{p}}$, where
$\left(a_{1},a_{2},\ldots,a_{p}\right)$ is the CFL factorization of the word
$u$.

If $n\in{\mathbb{N}}$ and if $x\in\operatorname{Comp}_{n}$, then there is a
family
$\left(\eta_{x,y}\right)_{y\in\operatorname{Comp}_{n}}\in{\mathbb{N}}^{\operatorname{Comp}_{n}}$
of elements of ${\mathbb{N}}$ satisfying

$\mathbf{M}_{x}=\sum_{\begin{subarray}{c}y\in\operatorname{Comp}_{n};\\\
y\underset{\operatorname*{wll}}{\leq}x\end{subarray}}\eta_{x,y}M_{y}$

and $\eta_{x,x}\neq 0$ (in ${\mathbb{N}}$).

Before we prove it, let us show the following lemma:

######  Lemma 6.90.

Let $n\in{\mathbb{N}}$ and $m\in{\mathbb{N}}$. Let
$u\in\operatorname{Comp}_{n}$ and $v\in\operatorname{Comp}_{m}$. Let $z$ be
the lexicographically highest element of the multiset $u\shuffle v$.

(a) We have $z\in\operatorname{Comp}_{n+m}$.

(b) There exists a positive integer $h$ such that

$M_{u}M_{v}=hM_{z}+\left(\text{a sum of terms of the form }M_{w}\text{ with
}w\in\operatorname{Comp}_{n+m}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}z\right).$

(c) Let $v^{\prime}\in\operatorname{Comp}_{m}$ be such that
$v^{\prime}\underset{\operatorname*{wll}}{<}v$. Then,

$M_{u}M_{v^{\prime}}=\left(\text{a sum of terms of the form }M_{w}\text{ with
}w\in\operatorname{Comp}_{n+m}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}z\right).$

######  Exercise 6.91.

Prove Lemma 6.90.

[Hint: For (b), set $h$ to be the multiplicity with which the word $z$ appears
in the multiset $u\shuffle v$, then use Proposition 6.84 and notice that
$M_{u}M_{v}$ is homogeneous of degree $n+m$. For (c), use (b) for $v^{\prime}$
instead of $v$ and notice that Lemma 6.76(a) shows that the lexicographically
highest element of the multiset $u\shuffle v^{\prime}$ is
$\underset{\operatorname*{wll}}{<}z$.]

######  Exercise 6.92.

Prove Proposition 6.89.

[Hint: Proceed by strong induction over $n$. In the induction step, let
$\left(a_{1},a_{2},\ldots,a_{p}\right)$ be the CFL factorization of $x$, and
set $u=a_{1}$ and $v=a_{2}a_{3}\cdots a_{p}$; then apply Proposition 6.89 to
$v$ instead of $x$, and multiply the resulting equality
$\mathbf{M}_{v}=\sum_{\begin{subarray}{c}y\in\operatorname{Comp}_{\left|v\right|};\\\
y\underset{\operatorname*{wll}}{\leq}v\end{subarray}}\eta_{v,y}M_{y}$ with
$M_{u}$ to obtain an expression for $M_{u}\mathbf{M}_{v}=\mathbf{M}_{x}$. Use
Lemma 6.90 to show that this expression has the form
$\sum_{\begin{subarray}{c}y\in\operatorname{Comp}_{n};\\\
y\underset{\operatorname*{wll}}{\leq}x\end{subarray}}\eta_{x,y}M_{y}$ with
$\eta_{x,x}\neq 0$; here it helps to remember that the lexicographically
highest element of the multiset $u\shuffle v$ is $uv=x$ (by Theorem 6.44(c)).]

We are almost ready to give our second proof of Proposition 6.83; our last
step is the following proposition:

######  Proposition 6.93.

Assume that $\mathbb{Q}$ is a subring of $\mathbf{k}$. Then,
$\left(M_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically independent
generating set of the $\mathbf{k}$-algebra $\operatorname{QSym}$.

######  Exercise 6.94.

Prove Proposition 6.93.

[Hint: Define $\mathbf{M}_{u}$ for every $u\in\operatorname{Comp}$ as in
Proposition 6.89. Conclude from Proposition 6.89 that, for every
$n\in{\mathbb{N}}$, the family
$\left(\mathbf{M}_{u}\right)_{u\in\operatorname{Comp}_{n}}$ expands invertibly
triangularly256256256See Definition 11.16(c) for the meaning of this. (with
respect to the total order $\underset{\operatorname*{wll}}{\leq}$ on
$\operatorname{Comp}_{n}$) with respect to the basis
$\left(M_{u}\right)_{u\in\operatorname{Comp}_{n}}$ of
$\operatorname{QSym}_{n}$. Conclude that this family
$\left(\mathbf{M}_{u}\right)_{u\in\operatorname{Comp}_{n}}$ is a basis of
$\operatorname{QSym}_{n}$ itself, and so the whole family
$\left(\mathbf{M}_{u}\right)_{u\in\operatorname{Comp}}$ is a basis of
$\operatorname{QSym}$. Conclude using Lemma 6.73(a).]

###### Second proof of Proposition 6.83..

Proposition 6.93 yields that $\left(M_{w}\right)_{w\in\mathfrak{L}}$ is an
algebraically independent generating set of the $\mathbf{k}$-algebra
$\operatorname{QSym}$.

Define a grading on the $\mathbf{k}$-algebra $\mathbf{k}\left[x_{w}\ \mid\
w\in\mathfrak{L}\right]$ by setting
$\deg\left(x_{w}\right)=\sum_{i=1}^{\ell\left(w\right)}w_{i}$ for every
$w\in\mathfrak{L}$. By the universal property of the polynomial algebra
$\mathbf{k}\left[x_{w}\ \mid\ w\in\mathfrak{L}\right]$, we can define a
$\mathbf{k}$-algebra homomorphism $\Phi:\mathbf{k}\left[x_{w}\ \mid\
w\in\mathfrak{L}\right]\rightarrow\operatorname{QSym}$ by setting

$\Phi\left(x_{w}\right)=M_{w}\ \ \ \ \ \ \ \ \ \ \text{for every
}w\in\mathfrak{L}.$

This homomorphism $\Phi$ is a $\mathbf{k}$-algebra isomorphism (since
$\left(M_{w}\right)_{w\in\mathfrak{L}}$ is an algebraically independent
generating set of the $\mathbf{k}$-algebra $\operatorname{QSym}$) and is
graded (because for every $w\in\mathfrak{L}$, the element $M_{w}$ of
$\operatorname{QSym}$ is homogeneous of degree
$\left|w\right|=\sum_{i=1}^{\ell\left(w\right)}w_{i}=\deg\left(x_{w}\right)$).
Thus, $\Phi$ is an isomorphism of graded $\mathbf{k}$-algebras. Hence,
$\operatorname{QSym}\cong\mathbf{k}\left[x_{w}\ \mid\ w\in\mathfrak{L}\right]$
as graded $\mathbf{k}$-algebras. In particular, this shows that
$\operatorname{QSym}$ is a polynomial algebra. This proves Theorem 6.82 under
the assumption that $\mathbb{Q}$ be a subring of $\mathbf{k}$. Proposition
6.83 is thus proven again. ∎

###  6.5. Polynomial freeness of $\operatorname{QSym}$: the general case

We now will prepare for proving Theorem 6.82 without any assumptions on
$\mathbf{k}$. In our proof, we follow [69] and [73, §6.7], but without using
the language of plethysm and Frobenius maps. We start with the following
definition:

######  Definition 6.95.

Let $\alpha$ be a composition. Write $\alpha$ in the form
$\alpha=\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)$ with
$\ell=\ell\left(\alpha\right)$.

(a) Let $\operatorname*{SIS}\left(\ell\right)$ denote the set of all strictly
increasing $\ell$-tuples $\left(i_{1},i_{2},\ldots,i_{\ell}\right)$ of
positive integers.257257257“Strictly increasing” means that
$i_{1}<i_{2}<\cdots<i_{\ell}$ here. Of course, the elements of
$\operatorname*{SIS}\left(\ell\right)$ are in 1-to-1 correspondence with
$\ell$-element subsets of $\left\\{1,2,3,\ldots\right\\}$. For every
$\ell$-tuple
$\mathbf{i}=\left(i_{1},i_{2},\ldots,i_{\ell}\right)\in\operatorname*{SIS}\left(\ell\right)$,
we denote the monomial $x_{i_{1}}^{\alpha_{1}}x_{i_{2}}^{\alpha_{2}}\cdots
x_{i_{\ell}}^{\alpha_{\ell}}$ by $\mathbf{x}_{\mathbf{i}}^{\alpha}$. This
$\mathbf{x}_{\mathbf{i}}^{\alpha}$ is a monomial of degree
$\alpha_{1}+\alpha_{2}+\cdots+\alpha_{\ell}=\left|\alpha\right|$. Then,

(6.26)
$M_{\alpha}=\sum_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\mathbf{x}_{\mathbf{i}}^{\alpha}.$
258258258Proof of (6.26): By the definition of $M_{\alpha}$, we have
$\displaystyle M_{\alpha}$
$\displaystyle=\underbrace{\sum_{i_{1}<i_{2}<\cdots<i_{\ell}\text{ in
}\left\\{1,2,3,\ldots\right\\}}}_{=\sum_{\left(i_{1},i_{2},\ldots,i_{\ell}\right)\in\operatorname*{SIS}\left(\ell\right)}}x_{i_{1}}^{\alpha_{1}}x_{i_{2}}^{\alpha_{2}}\cdots
x_{i_{\ell}}^{\alpha_{\ell}}=\sum_{\left(i_{1},i_{2},\ldots,i_{\ell}\right)\in\operatorname*{SIS}\left(\ell\right)}x_{i_{1}}^{\alpha_{1}}x_{i_{2}}^{\alpha_{2}}\cdots
x_{i_{\ell}}^{\alpha_{\ell}}=\sum_{\mathbf{i}=\left(i_{1},i_{2},\ldots,i_{\ell}\right)\in\operatorname*{SIS}\left(\ell\right)}\underbrace{x_{i_{1}}^{\alpha_{1}}x_{i_{2}}^{\alpha_{2}}\cdots
x_{i_{\ell}}^{\alpha_{\ell}}}_{\begin{subarray}{c}=\mathbf{x}_{\mathbf{i}}^{\alpha}\\\
\text{(by the definition of
}\mathbf{x}_{\mathbf{i}}^{\alpha}\text{)}\end{subarray}}$
$\displaystyle=\sum_{\mathbf{i}=\left(i_{1},i_{2},\ldots,i_{\ell}\right)\in\operatorname*{SIS}\left(\ell\right)}\mathbf{x}_{\mathbf{i}}^{\alpha}=\sum_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\mathbf{x}_{\mathbf{i}}^{\alpha},$
qed.

(b) Consider the ring $\mathbf{k}\left[\left[\mathbf{x}\right]\right]$ endowed
with the coefficientwise topology259259259This 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. 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).$ Note that this is not the topology obtained by taking the
completion of $\mathbf{k}\left[x_{1},x_{2},x_{3},\ldots\right]$ with respect
to the standard grading (in which all $x_{i}$ have degree $1$). (The latter
completion is actually a smaller ring than
$\mathbf{k}\left[{\mathbf{x}}\right]$.). The family
$\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}$
of elements of $\mathbf{k}\left[\left[\mathbf{x}\right]\right]$ is power-
summable260260260Let us define what “power-summable” means for us: A family
$\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in{\mathbb{N}}^{\mathbf{I}}$
(where $\mathbf{I}$ is some set) is said to be finitely supported if all but
finitely many $\mathbf{i}\in\mathbf{I}$ satisfy $n_{\mathbf{i}}=0$. If
$\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in{\mathbb{N}}^{\mathbf{I}}$
is a finitely supported family, then
$\sum_{\mathbf{i}\in\mathbf{I}}n_{\mathbf{i}}$ is a well-defined element of
${\mathbb{N}}$. If $N\in{\mathbb{N}}$, then a family
$\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in{\mathbb{N}}^{\mathbf{I}}$
will be called $\left(\leq N\right)$-supported if it is finitely supported and
satisfies $\sum_{\mathbf{i}\in\mathbf{I}}n_{\mathbf{i}}\leq N$. We say that a
family $\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in
R^{\mathbf{I}}$ of elements of a topological commutative $\mathbf{k}$-algebra
$R$ is power-summable if it satisfies the following property: For every
$N\in{\mathbb{N}}$, the sum
$\sum_{\begin{subarray}{c}\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in{\mathbb{N}}^{\mathbf{I}};\\\
\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\text{ is }\left(\leq
N\right)\text{-supported
}\end{subarray}}\alpha_{\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}}\prod_{\mathbf{i}\in\mathbf{I}}s_{\mathbf{i}}^{n_{\mathbf{i}}}$
converges in the topology on $R$ for every choice of scalars
$\alpha_{\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}}\in\mathbf{k}$
corresponding to all $\left(\leq N\right)$-supported
$\left(n_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in{\mathbb{N}}^{\mathbf{I}}$.
In our specific case, we consider
$\mathbf{k}\left[\left[\mathbf{x}\right]\right]$ as a topological commutative
$\mathbf{k}$-algebra, where the topology is the coefficientwise topology. The
fact that the family
$\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}$
is power-summable then can be proven as follows:  • If
$\alpha\neq\varnothing$, then this fact follows from the (easily-verified)
observation that every given monomial in the variables
$x_{1},x_{2},x_{3},\ldots$ can be written as a product of monomials of the
form $\mathbf{x}_{\mathbf{i}}^{\alpha}$ (with
$\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)$) in only finitely many
ways. • If $\alpha=\varnothing$, then this fact follows by noticing that
$\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}$
is a finite family (indeed,
$\operatorname*{SIS}\left(\ell\right)=\operatorname*{SIS}\left(0\right)=\left\\{\left({}\right)\right\\}$),
and every finite family is power-summable. . Hence, for every $f\in\Lambda$,
there is a well-defined power series
$f\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)\in\mathbf{k}\left[\left[\mathbf{x}\right]\right]$
obtained by “evaluating” $f$ at
$\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}$
261261261Here is how this power series
$f\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)$
is formally defined: Let $R$ be any topological commutative
$\mathbf{k}$-algebra, and let
$\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in R^{\mathbf{I}}$ be
any power-summable family of elements of $R$. Assume that the indexing set
$\mathbf{I}$ is countably infinite, and fix a bijection
$\mathfrak{j}:\left\\{1,2,3,\ldots\right\\}\rightarrow\mathbf{I}$. Let $g\in
R\left(\mathbf{x}\right)$ be arbitrary. Then, we can substitute
$s_{\mathfrak{j}\left(1\right)}$, $s_{\mathfrak{j}\left(2\right)}$,
$s_{\mathfrak{j}\left(3\right)}$, $\ldots$ for the variables $x_{1}$, $x_{2}$,
$x_{3}$, $\ldots$ in $g$, thus obtaining an infinite sum which converges in
$R$ (in fact, its convergence follows from the fact that the family
$\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in R^{\mathbf{I}}$ is
power-summable). The value of this sum will be denoted by
$g\left(\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\right)$. In
general, this value depends on the choice of the bijection $\mathfrak{j}$, so
the notation
$g\left(\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\right)$ is
unambiguous only if this bijection $\mathfrak{j}$ is chosen once and for all.
However, when $g\in\Lambda$, one can easily see that the choice of
$\mathfrak{j}$ has no effect on
$g\left(\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\right)$. We can
still define
$g\left(\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\right)$ when the
set $\mathbf{I}$ is finite instead of being countably infinite. In this case,
we only need to modify our above definition as follows: Instead of fixing a
bijection $\mathfrak{j}:\left\\{1,2,3,\ldots\right\\}\rightarrow\mathbf{I}$,
we now fix a bijection
$\mathfrak{j}:\left\\{1,2,\ldots,\left|\mathbf{I}\right|\right\\}\rightarrow\mathbf{I}$,
and instead of substituting $s_{\mathfrak{j}\left(1\right)}$,
$s_{\mathfrak{j}\left(2\right)}$, $s_{\mathfrak{j}\left(3\right)}$, $\ldots$
for the variables $x_{1}$, $x_{2}$, $x_{3}$, $\ldots$ in $g$, we now
substitute $s_{\mathfrak{j}\left(1\right)}$, $s_{\mathfrak{j}\left(2\right)}$,
$\ldots$, $s_{\mathfrak{j}\left(\left|\mathbf{I}\right|\right)}$, $0$, $0$,
$0$, $\ldots$ for the variables $x_{1}$, $x_{2}$, $x_{3}$, $\ldots$ in $g$.
Again, the same observations hold as before:
$g\left(\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\right)$ is
independent on $\mathfrak{j}$ if $g\in\Lambda$. Hence,
$g\left(\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\right)$ is well-
defined for every $g\in R\left(\mathbf{x}\right)$, every countable (i.e.,
finite or countably infinite) set $\mathbf{I}$, every topological commutative
$\mathbf{k}$-algebra $R$ and every power-summable family
$\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}\in R^{\mathbf{I}}$ of
elements of $R$, as long as a bijection $\mathfrak{j}$ is chosen. In
particular, we can apply this to $g=f$,
$\mathbf{I}=\operatorname*{SIS}\left(\ell\right)$,
$R=\mathbf{k}\left[\left[\mathbf{x}\right]\right]$ and
$\left(s_{\mathbf{i}}\right)_{\mathbf{i}\in\mathbf{I}}=\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}$,
choosing $\mathfrak{j}$ to be the bijection which sends every positive integer
$k$ to the $k$-th smallest element of $\operatorname*{SIS}\left(\ell\right)$
in the lexicographic order. (Of course, since $f\in\Lambda$, the choice of
$\mathfrak{j}$ is irrelevant.). In particular, for every $s\in{\mathbb{Z}}$,
we can evaluate the symmetric function $e_{s}\in\Lambda$ 262262262Recall that
$e_{0}=1$, and that $e_{s}=0$ for $s<0$. at
$\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}$.
The resulting power series
$e_{s}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)\in\mathbf{k}\left[\left[\mathbf{x}\right]\right]$
will be denoted $M_{\alpha}^{\left\langle s\right\rangle}$. Thus,

$M_{\alpha}^{\left\langle
s\right\rangle}=e_{s}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right).$

The power series $M_{\alpha}^{\left\langle s\right\rangle}$ are the power
series $e_{s}\left(\alpha\right)$ in [73]. We will shortly (in Corollary
6.102(a)) see that $M_{\alpha}^{\left\langle
s\right\rangle}\in\operatorname{QSym}$ (although this is also easy to prove by
inspection). Here are some examples of $M_{\alpha}^{\left\langle
s\right\rangle}$:

######  Example 6.96.

If $\alpha$ is a composition and $\ell$ denotes its length
$\ell\left(\alpha\right)$, then

$M_{\alpha}^{\left\langle
0\right\rangle}=\underbrace{e_{0}}_{=1}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)=1\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)=1$

and

$M_{\alpha}^{\left\langle
1\right\rangle}=e_{1}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)=\sum_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\mathbf{x}_{\mathbf{i}}^{\alpha}=M_{\alpha}\
\ \ \ \ \ \ \ \ \ \left(\text{by (\ref{eq.def.QSym.Malphas.a.1})}\right)$

and263263263This is not completely obvious, but easy to check (see Exercise
6.98(b)).

$M_{\alpha}^{\left\langle
2\right\rangle}=e_{2}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)=\sum_{\begin{subarray}{c}\mathbf{i}\in\operatorname*{SIS}\left(\ell\right),\
\mathbf{j}\in\operatorname*{SIS}\left(\ell\right);\\\
\mathbf{i}<\mathbf{j}\end{subarray}}\mathbf{x}_{\mathbf{i}}^{\alpha}\mathbf{x}_{\mathbf{j}}^{\alpha}$

(where the notation “$\mathbf{i}<\mathbf{j}$” should be interpreted with
respect to an arbitrary but fixed total order on the set
$\operatorname*{SIS}\left(\ell\right)$ – for example, the lexicographic
order). Applying the last of these three equalities to
$\alpha=\left(2,1\right)$, we obtain

$\displaystyle M_{\left(2,1\right)}^{\left\langle 2\right\rangle}$
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{i}\in\operatorname*{SIS}\left(2\right),\
\mathbf{j}\in\operatorname*{SIS}\left(2\right),\\\
\mathbf{i}<\mathbf{j}\end{subarray}}\mathbf{x}_{\mathbf{i}}^{\left(2,1\right)}\mathbf{x}_{\mathbf{j}}^{\left(2,1\right)}=\sum_{\begin{subarray}{c}\left(i_{1},i_{2}\right)\in\operatorname*{SIS}\left(2\right),\
\left(j_{1},j_{2}\right)\in\operatorname*{SIS}\left(2\right);\\\
\left(i_{1},i_{2}\right)<\left(j_{1},j_{2}\right)\end{subarray}}\underbrace{\mathbf{x}_{\left(i_{1},i_{2}\right)}^{\left(2,1\right)}}_{=x_{i_{1}}^{2}x_{i_{2}}^{1}}\underbrace{\mathbf{x}_{\left(j_{1},j_{2}\right)}^{\left(2,1\right)}}_{=x_{j_{1}}^{2}x_{j_{2}}^{1}}$
$\displaystyle=\sum_{\begin{subarray}{c}\left(i_{1},i_{2}\right)\in\operatorname*{SIS}\left(2\right),\
\left(j_{1},j_{2}\right)\in\operatorname*{SIS}\left(2\right);\\\
\left(i_{1},i_{2}\right)<\left(j_{1},j_{2}\right)\end{subarray}}x_{i_{1}}^{2}x_{i_{2}}^{1}x_{j_{1}}^{2}x_{j_{2}}^{1}$
$\displaystyle=\underbrace{\sum_{\begin{subarray}{c}i_{1}<i_{2};\
j_{1}<j_{2};\\\
i_{1}<j_{1}\end{subarray}}x_{i_{1}}^{2}x_{i_{2}}^{1}x_{j_{1}}^{2}x_{j_{2}}^{1}}_{=M_{\left(2,1,2,1\right)}+M_{\left(2,3,1\right)}+2M_{\left(2,2,1,1\right)}+M_{\left(2,2,2\right)}}+\underbrace{\sum_{\begin{subarray}{c}i_{1}<i_{2};\
j_{1}<j_{2};\\\ i_{1}=j_{1},\
i_{2}<j_{2}\end{subarray}}x_{i_{1}}^{2}x_{i_{2}}^{1}x_{j_{1}}^{2}x_{j_{2}}^{1}}_{=M_{\left(4,1,1\right)}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{here, we have WLOG assumed that
the order on }\operatorname*{SIS}\left(2\right)\text{ is
lexicographic}\right)$
$\displaystyle=M_{\left(2,1,2,1\right)}+M_{\left(2,3,1\right)}+2M_{\left(2,2,1,1\right)}+M_{\left(2,2,2\right)}+M_{\left(4,1,1\right)}.$

Of course, every negative integer $s$ satisfies $M_{\alpha}^{\left\langle
s\right\rangle}=\underbrace{e_{s}}_{=0}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)=0$.

There is a determinantal formula for the $s!M_{\alpha}^{\left\langle
s\right\rangle}$ (and thus also for $M_{\alpha}^{\left\langle s\right\rangle}$
when $s!$ is invertible in $\mathbf{k}$), but in order to state it, we need to
introduce one more notation:

######  Definition 6.97.

Let $\alpha=\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)$ be a
composition, and let $k$ be a positive integer. Then,
$\alpha\left\\{k\right\\}$ will denote the composition
$\left(k\alpha_{1},k\alpha_{2},\ldots,k\alpha_{\ell}\right)$. Clearly,
$\ell\left(\alpha\left\\{k\right\\}\right)=\ell\left(\alpha\right)$ and
$\left|\alpha\left\\{k\right\\}\right|=k\left|\alpha\right|$.

######  Exercise 6.98.

Let $\alpha$ be a composition. Write the composition $\alpha$ in the form
$\alpha=\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)$ with
$\ell=\ell\left(\alpha\right)$.

  1. (a)

Show that the $s$-th power-sum symmetric function $p_{s}\in\Lambda$ satisfies

$p_{s}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)=M_{\alpha\left\\{s\right\\}}$

for every positive integer $s$.

  2. (b)

Let us fix a total order on the set $\operatorname*{SIS}\left(\ell\right)$
(for example, the lexicographic order). Show that the $s$-th elementary
symmetric function $e_{s}\in\Lambda$ satisfies

$M_{\alpha}^{\left\langle
s\right\rangle}=e_{s}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)=\sum_{\begin{subarray}{c}\left(\mathbf{i}_{1},\mathbf{i}_{2},\ldots,\mathbf{i}_{s}\right)\in\left(\operatorname*{SIS}\left(\ell\right)\right)^{s};\\\
\mathbf{i}_{1}<\mathbf{i}_{2}<\cdots<\mathbf{i}_{s}\end{subarray}}\mathbf{x}_{\mathbf{i}_{1}}^{\alpha}\mathbf{x}_{\mathbf{i}_{2}}^{\alpha}\cdots\mathbf{x}_{\mathbf{i}_{s}}^{\alpha}$

for every $s\in{\mathbb{N}}$.

  3. (c)

Let $s\in{\mathbb{N}}$, and let $n$ be a positive integer. Let
$e_{s}^{\left\langle n\right\rangle}$ be the symmetric function
$\sum_{i_{1}<i_{2}<\cdots<i_{s}}x_{i_{1}}^{n}x_{i_{2}}^{n}\cdots
x_{i_{s}}^{n}\in\Lambda$. Then, show that

$M_{\alpha\left\\{n\right\\}}^{\left\langle
s\right\rangle}=e_{s}^{\left\langle
n\right\rangle}\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right).$

  4. (d)

Let $s\in{\mathbb{N}}$, and let $n$ be a positive integer. Prove that there
exists a polynomial $P\in\mathbf{k}\left[z_{1},z_{2},z_{3},\ldots\right]$ such
that $M_{\alpha\left\\{n\right\\}}^{\left\langle
s\right\rangle}=P\left(M_{\alpha}^{\left\langle
1\right\rangle},M_{\alpha}^{\left\langle
2\right\rangle},M_{\alpha}^{\left\langle 3\right\rangle},\ldots\right)$.

[Hint: For (a), (b) and (c), apply the definition of
$f\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)$
with $f$ a symmetric function264264264There are two subtleties that need to be
addressed:  • the fact that the definition of
$f\left(\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}\right)$
distinguishes between two cases depending on whether or not
$\operatorname*{SIS}\left(\ell\right)$ is finite; • the fact that the total
order on the set $\left\\{1,2,3,\ldots\right\\}$ (which appears in the
summation subscript in the equality
$e_{s}=\sum_{\begin{subarray}{c}\left(i_{1},i_{2},\ldots,i_{s}\right)\in\left\\{1,2,3,\ldots\right\\}^{s};\\\
i_{1}<i_{2}<\cdots<i_{s}\end{subarray}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{s}}$)
has nothing to do with the total order on the set
$\operatorname*{SIS}\left(\ell\right)$ (which appears in the summation
subscript in
$\sum_{\begin{subarray}{c}\left(\mathbf{i}_{1},\mathbf{i}_{2},\ldots,\mathbf{i}_{s}\right)\in\left(\operatorname*{SIS}\left(\ell\right)\right)^{s};\\\
\mathbf{i}_{1}<\mathbf{i}_{2}<\cdots<\mathbf{i}_{s}\end{subarray}}\mathbf{x}_{\mathbf{i}_{1}}^{\alpha}\mathbf{x}_{\mathbf{i}_{2}}^{\alpha}\cdots\mathbf{x}_{\mathbf{i}_{s}}^{\alpha}$).
For instance, the former total order is well-founded, whereas the latter may
and may not be. So there is (generally) no bijection between
$\left\\{1,2,3,\ldots\right\\}$ and $\operatorname*{SIS}\left(\ell\right)$
preserving these orders (even if $\operatorname*{SIS}\left(\ell\right)$ is
infinite). Fortunately, this does not matter much, because the total order is
only being used to ensure that every product of $s$ pairwise distinct elements
appears exactly once in the sum. . For (d), recall that $\Lambda$ is generated
by $e_{1},e_{2},e_{3},\ldots$.]

######  Exercise 6.99.

Let $s\in{\mathbb{N}}$. Show that the composition $\left(1\right)$ satisfies
$M_{\left(1\right)}^{\left\langle s\right\rangle}=e_{s}$.

######  Proposition 6.100.

Let $\alpha=\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)$ be a
composition.

(a) Let $n\in{\mathbb{N}}$. Define a matrix
$A_{n}^{\left\langle\alpha\right\rangle}=\left(a_{i,j}^{\left\langle\alpha\right\rangle}\right)_{i,j=1,2,\ldots,n}$
by

$a_{i,j}^{\left\langle\alpha\right\rangle}=\begin{cases}M_{\alpha\left\\{i-j+1\right\\}},&\text{if
}i\geq j;\\\ i,&\text{if }i=j-1;\\\ 0,&\text{if
}i<j-1\end{cases}\qquad\qquad\text{ for all
}\left(i,j\right)\in\left\\{1,2,\ldots,n\right\\}^{2}.$

This matrix $A_{n}^{\left\langle\alpha\right\rangle}$ looks as follows:

$A_{n}^{\left\langle\alpha\right\rangle}=\left(\begin{array}[c]{cccccc}M_{\alpha\left\\{1\right\\}}&1&0&\cdots&0&0\\\
M_{\alpha\left\\{2\right\\}}&M_{\alpha\left\\{1\right\\}}&2&\cdots&0&0\\\
M_{\alpha\left\\{3\right\\}}&M_{\alpha\left\\{2\right\\}}&M_{\alpha\left\\{1\right\\}}&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
M_{\alpha\left\\{n-1\right\\}}&M_{\alpha\left\\{n-2\right\\}}&M_{\alpha\left\\{n-3\right\\}}&\cdots&M_{\alpha\left\\{1\right\\}}&n-1\\\
M_{\alpha\left\\{n\right\\}}&M_{\alpha\left\\{n-1\right\\}}&M_{\alpha\left\\{n-2\right\\}}&\cdots&M_{\alpha\left\\{2\right\\}}&M_{\alpha\left\\{1\right\\}}\end{array}\right).$

Then,
$\det\left(A_{n}^{\left\langle\alpha\right\rangle}\right)=n!M_{\alpha}^{\left\langle
n\right\rangle}$.

(b) Let $n$ be a positive integer. Define a matrix
$B_{n}^{\left\langle\alpha\right\rangle}=\left(b_{i,j}^{\left\langle\alpha\right\rangle}\right)_{i,j=1,2,\ldots,n}$
by

$b_{i,j}^{\left\langle\alpha\right\rangle}=\begin{cases}iM_{\alpha}^{\left\langle
i\right\rangle},&\text{if }j=1;\\\ M_{\alpha}^{\left\langle
i-j+1\right\rangle},&\text{if }j>1\end{cases}\qquad\qquad\text{ for all
}\left(i,j\right)\in\left\\{1,2,\ldots,n\right\\}^{2}.$

The matrix $B_{n}^{\left\langle\alpha\right\rangle}$ looks as follows:

$\displaystyle B_{n}^{\left\langle\alpha\right\rangle}$
$\displaystyle=\left(\begin{array}[c]{cccccc}M_{\alpha}^{\left\langle
1\right\rangle}&M_{\alpha}^{\left\langle
0\right\rangle}&M_{\alpha}^{\left\langle-1\right\rangle}&\cdots&M_{\alpha}^{\left\langle-n+3\right\rangle}&M_{\alpha}^{\left\langle-n+2\right\rangle}\\\
2M_{\alpha}^{\left\langle 2\right\rangle}&M_{\alpha}^{\left\langle
1\right\rangle}&M_{\alpha}^{\left\langle
0\right\rangle}&\cdots&M_{\alpha}^{\left\langle-n+4\right\rangle}&M_{\alpha}^{\left\langle-n+3\right\rangle}\\\
3M_{\alpha}^{\left\langle 3\right\rangle}&M_{\alpha}^{\left\langle
2\right\rangle}&M_{\alpha}^{\left\langle
1\right\rangle}&\cdots&M_{\alpha}^{\left\langle-n+5\right\rangle}&M_{\alpha}^{\left\langle-n+4\right\rangle}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\left(n-1\right)M_{\alpha}^{\left\langle
n-1\right\rangle}&M_{\alpha}^{\left\langle
n-2\right\rangle}&M_{\alpha}^{\left\langle
n-3\right\rangle}&\cdots&M_{\alpha}^{\left\langle
1\right\rangle}&M_{\alpha}^{\left\langle 0\right\rangle}\\\
nM_{\alpha}^{\left\langle n\right\rangle}&M_{\alpha}^{\left\langle
n-1\right\rangle}&M_{\alpha}^{\left\langle
n-2\right\rangle}&\cdots&M_{\alpha}^{\left\langle
2\right\rangle}&M_{\alpha}^{\left\langle 1\right\rangle}\end{array}\right)$
$\displaystyle=\left(\begin{array}[c]{cccccc}M_{\alpha}^{\left\langle
1\right\rangle}&1&0&\cdots&0&0\\\ 2M_{\alpha}^{\left\langle
2\right\rangle}&M_{\alpha}^{\left\langle 1\right\rangle}&1&\cdots&0&0\\\
3M_{\alpha}^{\left\langle 3\right\rangle}&M_{\alpha}^{\left\langle
2\right\rangle}&M_{\alpha}^{\left\langle 1\right\rangle}&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\left(n-1\right)M_{\alpha}^{\left\langle
n-1\right\rangle}&M_{\alpha}^{\left\langle
n-2\right\rangle}&M_{\alpha}^{\left\langle
n-3\right\rangle}&\cdots&M_{\alpha}^{\left\langle 1\right\rangle}&1\\\
nM_{\alpha}^{\left\langle n\right\rangle}&M_{\alpha}^{\left\langle
n-1\right\rangle}&M_{\alpha}^{\left\langle
n-2\right\rangle}&\cdots&M_{\alpha}^{\left\langle
2\right\rangle}&M_{\alpha}^{\left\langle 1\right\rangle}\end{array}\right).$

Then,
$\det\left(B_{n}^{\left\langle\alpha\right\rangle}\right)=M_{\alpha\left\\{n\right\\}}$.

######  Exercise 6.101.

Prove Proposition 6.100.

[Hint: Substitute
$\left(\mathbf{x}_{\mathbf{i}}^{\alpha}\right)_{\mathbf{i}\in\operatorname*{SIS}\left(\ell\right)}$
for the variable set in Exercise 2.90, and recall Exercise 6.98(a).]

######  Corollary 6.102.

Let $\alpha$ be a composition. Let $s\in{\mathbb{Z}}$.

  1. (a)

We have $M_{\alpha}^{\left\langle s\right\rangle}\in\operatorname{QSym}$.

  2. (b)

We have $M_{\alpha}^{\left\langle
s\right\rangle}\in\operatorname{QSym}_{s\left|\alpha\right|}$.

######  Exercise 6.103.

Prove Corollary 6.102.

We make one further definition:

######  Definition 6.104.

Let $\alpha$ be a nonempty composition. Then, we denote by $\gcd\alpha$ the
greatest common divisor of the parts of $\alpha$. (For instance,
$\gcd\left(8,6,4\right)=2$.) We also define $\operatorname*{red}\alpha$ to be
the composition
$\left(\dfrac{\alpha_{1}}{\gcd\alpha},\dfrac{\alpha_{2}}{\gcd\alpha},\ldots,\dfrac{\alpha_{\ell}}{\gcd\alpha}\right)$,
where $\alpha$ is written in the form
$\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)$.

We say that a nonempty composition $\alpha$ is reduced if $\gcd\alpha=1$.

We define $\mathfrak{RL}$ to be the set of all reduced Lyndon compositions. In
other words, $\mathfrak{RL}=\left\\{w\in\mathfrak{L}\ \mid\ w\text{ is
reduced}\right\\}$ (since $\mathfrak{L}$ is the set of all Lyndon
compositions).

Hazewinkel, in [73, proof of Thm. 6.7.5], denotes $\mathfrak{RL}$ by $eLYN$,
calling reduced Lyndon compositions “elementary Lyndon words”.

######  Remark 6.105.

Let $\alpha$ be a nonempty composition.

(a) We have
$\alpha=\left(\operatorname*{red}\alpha\right)\left\\{\gcd\alpha\right\\}$.

(b) The composition $\alpha$ is Lyndon if and only if the composition
$\operatorname*{red}\alpha$ is Lyndon.

(c) The composition $\operatorname*{red}\alpha$ is reduced.

(d) If $\alpha$ is reduced, then $\operatorname*{red}\alpha=\alpha$.

(e) If $s\in\left\\{1,2,3,\ldots\right\\}$, then the composition
$\alpha\left\\{s\right\\}$ is nonempty and satisfies
$\operatorname*{red}\left(\alpha\left\\{s\right\\}\right)=\operatorname*{red}\alpha$
and $\gcd\left(\alpha\left\\{s\right\\}\right)=s\gcd\alpha$.

(f) We have
$\left(\gcd\alpha\right)\left|\operatorname*{red}\alpha\right|=\left|\alpha\right|$.

######  Exercise 6.106.

Prove Remark 6.105.

Our goal in this section is now to prove the following result of Hazewinkel:

######  Theorem 6.107.

The family $\left(M_{w}^{\left\langle
s\right\rangle}\right)_{\left(w,s\right)\in\mathfrak{RL}\times\left\\{1,2,3,\ldots\right\\}}$
is an algebraically independent generating set of the $\mathbf{k}$-algebra
$\operatorname{QSym}$.

This will (almost) immediately yield Theorem 6.82.

Our first step towards proving Theorem 6.107 is the following observation:

######  Lemma 6.108.

The family $\left(M_{w}^{\left\langle
s\right\rangle}\right)_{\left(w,s\right)\in\mathfrak{RL}\times\left\\{1,2,3,\ldots\right\\}}$
is a reindexing of the family
$\left(M_{\operatorname*{red}\alpha}^{\left\langle\gcd\alpha\right\rangle}\right)_{\alpha\in\mathfrak{L}}$.

######  Exercise 6.109.

Prove Lemma 6.108.

Next, we show a lemma:

######  Lemma 6.110.

Let $\alpha$ be a nonempty composition. Let $s\in{\mathbb{N}}$. Then,

(6.27) $s!M_{\alpha}^{\left\langle
s\right\rangle}-M_{\alpha}^{s}\in\sum_{\begin{subarray}{c}\beta\in\operatorname{Comp}_{s\left|\alpha\right|};\\\
\ell\left(\beta\right)\leq\left(s-1\right)\ell\left(\alpha\right)\end{subarray}}\mathbf{k}M_{\beta}.$

(That is, $s!M_{\alpha}^{\left\langle s\right\rangle}-M_{\alpha}^{s}$ is a
$\mathbf{k}$-linear combination of terms of the form $M_{\beta}$ with $\beta$
ranging over the compositions of $s\left|\alpha\right|$ satisfying
$\ell\left(\beta\right)\leq\left(s-1\right)\ell\left(\alpha\right)$.)

######  Exercise 6.111.

Prove Lemma 6.110.

[Hint: There are two approaches: One is to apply Proposition 6.100(a) and
expand the determinant; the other is to argue which monomials can appear in
$s!M_{\alpha}^{\left\langle s\right\rangle}-M_{\alpha}^{s}$.]

We now return to studying products of monomial quasisymmetric functions:

######  Lemma 6.112.

Let $n\in{\mathbb{N}}$ and $m\in{\mathbb{N}}$. Let
$u\in\operatorname{Comp}_{n}$ and $v\in\operatorname{Comp}_{m}$. Let $z$ be
the lexicographically highest element of the multiset $u\shuffle v$. Let $h$
be the multiplicity with which the word $z$ appears in the multiset $u\shuffle
v$. Then,265265265The following equality makes sense because we have
$z\in\operatorname{Comp}_{n+m}$ (by Lemma 6.90(a)).

$M_{u}M_{v}=hM_{z}+\left(\text{a sum of terms of the form }M_{w}\text{ with
}w\in\operatorname{Comp}_{n+m}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}z\right).$

###### Proof of Lemma 6.112..

Lemma 6.112 was shown during the proof of Lemma 6.90(b). ∎

######  Corollary 6.113.

Let $n\in{\mathbb{N}}$ and $m\in{\mathbb{N}}$. Let
$u\in\operatorname{Comp}_{n}$ and $v\in\operatorname{Comp}_{m}$. Regard $u$
and $v$ as words in $\mathfrak{A}^{\ast}$. Assume that $u$ is a Lyndon word.
Let $\left(b_{1},b_{2},\ldots,b_{q}\right)$ be the CFL factorization of the
word $v$.

Assume that $u\geq b_{j}$ for every $j\in\left\\{1,2,\ldots,q\right\\}$. Let

$h=1+\left|\left\\{j\in\left\\{1,2,\ldots,q\right\\}\ \mid\
b_{j}=u\right\\}\right|.$

Then,

$M_{u}M_{v}=hM_{uv}+\left(\text{a sum of terms of the form }M_{w}\text{ with
}w\in\operatorname{Comp}_{n+m}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}uv\right).$

######  Exercise 6.114.

Prove Corollary 6.113.

[Hint: Apply Lemma 6.112, and notice that $uv$ is the lexicographically
highest element of the multiset $u\shuffle v$ (by Theorem 6.44(e)), and that
$h$ is the multiplicity with which this word $uv$ appears in the multiset
$u\shuffle v$ (this is a rewriting of Theorem 6.44(e)).]

######  Corollary 6.115.

Let $k\in{\mathbb{N}}$ and $s\in{\mathbb{N}}$. Let
$x\in\operatorname{Comp}_{k}$ be such that $x$ is a Lyndon word. Then:

  1. (a)

The lexicographically highest element of the multiset $x\shuffle x^{s}$ is
$x^{s+1}$.

  2. (b)

We have

$M_{x}M_{x^{s}}=\left(s+1\right)M_{x^{s+1}}+\left(\text{a sum of terms of the
form }M_{w}\text{ with }w\in\operatorname{Comp}_{\left(s+1\right)k}\text{
satisfying }w\underset{\operatorname*{wll}}{<}x^{s+1}\right).$

  3. (c)

Let $t\in\operatorname{Comp}_{sk}$ be such that
$t\underset{\operatorname*{wll}}{<}x^{s}$. Then,

$M_{x}M_{t}=\left(\text{a sum of terms of the form }M_{w}\text{ with
}w\in\operatorname{Comp}_{\left(s+1\right)k}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}x^{s+1}\right).$

######  Exercise 6.116.

Prove Corollary 6.115.

[Hint: Notice that $\left(\underbrace{x,x,\ldots,x}_{s\text{ times}}\right)$
is the CFL factorization of the word $x^{s}$. Now, part (a) of Corollary 6.115
follows from Theorem 6.44(c), part (b) follows from Corollary 6.113, and part
(c) from Lemma 6.90(c) (using part (a)).]

######  Corollary 6.117.

Let $n\in{\mathbb{N}}$ and $m\in{\mathbb{N}}$. Let
$u\in\operatorname{Comp}_{n}$ and $v\in\operatorname{Comp}_{m}$. Regard $u$
and $v$ as words in $\mathfrak{A}^{\ast}$. Let
$\left(a_{1},a_{2},\ldots,a_{p}\right)$ be the CFL factorization of $u$. Let
$\left(b_{1},b_{2},\ldots,b_{q}\right)$ be the CFL factorization of the word
$v$. Assume that $a_{i}>b_{j}$ for every $i\in\left\\{1,2,\ldots,p\right\\}$
and $j\in\left\\{1,2,\ldots,q\right\\}$. Then,

$M_{u}M_{v}=M_{uv}+\left(\text{a sum of terms of the form }M_{w}\text{ with
}w\in\operatorname{Comp}_{n+m}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}uv\right).$

######  Exercise 6.118.

Prove Corollary 6.117.

[Hint: Combine Lemma 6.112 with the parts (c) and (d) of Theorem 6.44.]

######  Corollary 6.119.

Let $n\in{\mathbb{N}}$. Let $u\in\operatorname{Comp}_{n}$ be a nonempty
composition. Regard $u$ as a word in $\mathfrak{A}^{\ast}$. Let
$\left(a_{1},a_{2},\ldots,a_{p}\right)$ be the CFL factorization of $u$. Let
$k\in\left\\{1,2,\ldots,p-1\right\\}$ be such that $a_{k}>a_{k+1}$. Let $x$ be
the word $a_{1}a_{2}\cdots a_{k}$, and let $y$ be the word
$a_{k+1}a_{k+2}\cdots a_{p}$. Then,

$M_{u}=M_{x}M_{y}-\left(\text{a sum of terms of the form }M_{w}\text{ with
}w\in\operatorname{Comp}_{n}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}u\right).$

######  Exercise 6.120.

Prove Corollary 6.119.

[Hint: Apply Corollary 6.117 to $x$, $y$, $\left|x\right|$, $\left|y\right|$,
$k$, $p-k$, $\left(a_{1},a_{2},\ldots,a_{k}\right)$ and
$\left(a_{k+1},a_{k+2},\ldots,a_{p}\right)$ instead of $u$, $v$, $n$, $m$,
$p$, $q$, $\left(a_{1},a_{2},\ldots,a_{p}\right)$ and
$\left(b_{1},b_{2},\ldots,b_{q}\right)$; then, notice that $xy=u$ and
$\left|x\right|+\left|y\right|=n$.]

######  Corollary 6.121.

Let $k\in{\mathbb{N}}$. Let $x\in\operatorname{Comp}_{k}$ be a composition.
Assume that $x$ is a Lyndon word. Let $s\in{\mathbb{N}}$. Then,

$M_{x}^{s}-s!M_{x^{s}}\in\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}.$

(Recall that $x^{s}$ is defined to be the word $\underbrace{xx\cdots
x}_{s\text{ times}}$.)

######  Exercise 6.122.

Prove Corollary 6.121.

[Hint: Rewrite the claim of Corollary 6.121 in the form $M_{x}^{s}\in
s!M_{x^{s}}+\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}$. This
can be proven by induction over $s$, where in the induction step we need the
following two observations:

  1. (1)

We have
$M_{x}M_{x^{s}}\in\left(s+1\right)M_{x^{s+1}}+\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{\left(s+1\right)k};\\\
w\underset{\operatorname*{wll}}{<}x^{s+1}\end{subarray}}\mathbf{k}M_{w}$.

  2. (2)

For every $t\in\operatorname{Comp}_{sk}$ satisfying
$t\underset{\operatorname*{wll}}{<}x^{s}$, we have
$M_{x}M_{t}\in\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{\left(s+1\right)k};\\\
w\underset{\operatorname*{wll}}{<}x^{s+1}\end{subarray}}\mathbf{k}M_{w}$.

These two observations follow from parts (b) and (c) of Corollary 6.115.]

######  Corollary 6.123.

Let $k\in{\mathbb{N}}$. Let $x\in\operatorname{Comp}_{k}$ be a composition.
Assume that $x$ is a Lyndon word. Let $s\in{\mathbb{N}}$. Then,

$M_{x}^{\left\langle
s\right\rangle}-M_{x^{s}}\in\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}.$

(Recall that $x^{s}$ is defined to be the word $\underbrace{xx\cdots
x}_{s\text{ times}}$.)

######  Exercise 6.124.

Prove Corollary 6.123.

[Hint: Lemma 6.110 (applied to $\alpha=x$) yields

$s!M_{x}^{\left\langle
s\right\rangle}-M_{x}^{s}\in\sum_{\begin{subarray}{c}\beta\in\operatorname{Comp}_{sk};\\\
\ell\left(\beta\right)\leq\left(s-1\right)\ell\left(x\right)\end{subarray}}M_{\beta}=\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
\ell\left(w\right)\leq\left(s-1\right)\ell\left(x\right)\end{subarray}}\mathbf{k}M_{w}\subset\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}$
266266266since every $w\in\operatorname{Comp}_{sk}$ with the property that
$\ell\left(w\right)\leq\left(s-1\right)\ell\left(x\right)$ must satisfy
$w\underset{\operatorname*{wll}}{<}x^{s}$

. Adding this to the claim of Corollary 6.121, obtain $s!M_{x}^{\left\langle
s\right\rangle}-s!M_{x^{s}}\in\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}$, that
is, $s!\left(M_{x}^{\left\langle
s\right\rangle}-M_{x^{s}}\right)\in\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}$. It
remains to get rid of the $s!$ on the left hand side. Assume WLOG that
$\mathbf{k}={\mathbb{Z}}$, and argue that every $f\in\operatorname{QSym}$
satisfying $s!\cdot
f\in\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}$ must
itself lie in $\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{sk};\\\
w\underset{\operatorname*{wll}}{<}x^{s}\end{subarray}}\mathbf{k}M_{w}$.]

We are now ready to prove Theorem 6.107:

######  Exercise 6.125.

Prove Theorem 6.107.

[Hint: Lemma 6.108 yields that the family $\left(M_{w}^{\left\langle
s\right\rangle}\right)_{\left(w,s\right)\in\mathfrak{RL}\times\left\\{1,2,3,\ldots\right\\}}$
is a reindexing of the family
$\left(M_{\operatorname*{red}w}^{\left\langle\gcd
w\right\rangle}\right)_{w\in\mathfrak{L}}$. Hence, it is enough to prove that
the family $\left(M_{\operatorname*{red}w}^{\left\langle\gcd
w\right\rangle}\right)_{w\in\mathfrak{L}}$ is an algebraically independent
generating set of the $\mathbf{k}$-algebra $\operatorname{QSym}$. The latter
claim, in turn, will follow from Lemma 6.73(c)267267267applied to
$A=\operatorname{QSym}$, $b_{w}=M_{\operatorname*{red}w}^{\left\langle\gcd
w\right\rangle}$, $\operatorname*{wt}\left(N\right)=N$ and $g_{u}=M_{u}$ once
it is proven that the family $\left(M_{\operatorname*{red}w}^{\left\langle\gcd
w\right\rangle}\right)_{w\in\mathfrak{L}}$ generates the $\mathbf{k}$-algebra
$\operatorname{QSym}$. So it remains to show that the family
$\left(M_{\operatorname*{red}w}^{\left\langle\gcd
w\right\rangle}\right)_{w\in\mathfrak{L}}$ generates the $\mathbf{k}$-algebra
$\operatorname{QSym}$.

Let $U$ denote the $\mathbf{k}$-subalgebra of $\operatorname{QSym}$ generated
by $\left(M_{\operatorname*{red}w}^{\left\langle\gcd
w\right\rangle}\right)_{w\in\mathfrak{L}}$. It then suffices to prove that
$U=\operatorname{QSym}$. To this purpose, it is enough to prove that

(6.28) $M_{\beta}\in U\ \ \ \ \ \ \ \ \ \ \text{for every composition }\beta.$

For every reduced Lyndon composition $\alpha$ and every
$j\in\left\\{1,2,3,\ldots\right\\}$, the quasisymmetric function
$M_{\alpha}^{\left\langle j\right\rangle}$ is an element of the family
$\left(M_{\operatorname*{red}w}^{\left\langle\gcd
w\right\rangle}\right)_{w\in\mathfrak{L}}$ and thus belongs to $U$. Combine
this with Exercise 6.98(d) to see that

(6.29) $M_{\beta}^{\left\langle s\right\rangle}\in U\ \ \ \ \ \ \ \ \ \
\text{for every Lyndon composition }\beta\text{ and every
}s\in\left\\{1,2,3,\ldots\right\\}$

(because every Lyndon composition $\beta$ can be written as
$\alpha\left\\{n\right\\}$ for a reduced Lyndon composition $\alpha$ and an
$n\in\left\\{1,2,3,\ldots\right\\}$). Now, prove (6.28) by strong induction:
first, induce over $\left|\beta\right|$, and then, for fixed
$\left|\beta\right|$, induce over $\beta$ in the wll-order. The induction step
looks as follows: Fix some composition $\alpha$, and assume (as induction
hypothesis) that:

  * •

(6.28) holds for every composition $\beta$ satisfying
$\left|\beta\right|<\left|\alpha\right|$;

  * •

(6.28) holds for every composition $\beta$ satisfying
$\left|\beta\right|=\left|\alpha\right|$ and
$\beta\underset{\operatorname*{wll}}{<}\alpha$.

It remains to prove that (6.28) holds for $\beta=\alpha$. In other words, it
remains to prove that $M_{\alpha}\in U$. Let
$\left(a_{1},a_{2},\ldots,a_{p}\right)$ be the CFL factorization of the word
$\alpha$. Assume WLOG that $p\neq 0$ (else, all is trivial). We are in one of
the following two cases:

Case 1: All of the words $a_{1}$, $a_{2}$, $\ldots$, $a_{p}$ are equal.

Case 2: Not all of the words $a_{1}$, $a_{2}$, $\ldots$, $a_{p}$ are equal.

In Case 2, there exists a $k\in\left\\{1,2,\ldots,p-1\right\\}$ satisfying
$a_{k}>a_{k+1}$ (since $a_{1}\geq a_{2}\geq\cdots\geq a_{p}$), and thus
Corollary 6.119 (applied to $u=\alpha$, $n=\left|\alpha\right|$,
$x=a_{1}a_{2}\cdots a_{k}$ and $y=a_{k}a_{k+1}\cdots a_{p}$) shows that

$\displaystyle M_{\alpha}$ $\displaystyle=\underbrace{M_{a_{1}a_{2}\cdots
a_{k}}}_{\begin{subarray}{c}\in U\\\ \text{(by the induction}\\\
\text{hypothesis)}\end{subarray}}\underbrace{M_{a_{k}a_{k+1}\cdots
a_{p}}}_{\begin{subarray}{c}\in U\\\ \text{(by the induction}\\\
\text{hypothesis)}\end{subarray}}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
-\left(\text{a sum of terms of the form
}\underbrace{M_{w}}_{\begin{subarray}{c}\in U\\\ \text{(by the induction}\\\
\text{hypothesis)}\end{subarray}}\text{ with
}w\in\operatorname{Comp}_{\left|\alpha\right|}\text{ satisfying
}w\underset{\operatorname*{wll}}{<}\alpha\right)$ $\displaystyle\in
UU-\left(\text{a sum of terms in }U\right)\subset U.$

Hence, it only remains to deal with Case 1. In this case, set
$x=a_{1}=a_{2}=\cdots=a_{p}$. Thus, $\alpha=a_{1}a_{2}\cdots a_{p}=x^{p}$,
whence $\left|\alpha\right|=p\left|x\right|$. But Corollary 6.123 (applied to
$s=p$ and $k=\left|x\right|$) yields

$\displaystyle M_{x}^{\left\langle p\right\rangle}-M_{x^{p}}$
$\displaystyle\in\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{p\left|x\right|};\\\
w\underset{\operatorname*{wll}}{<}x^{p}\end{subarray}}\mathbf{k}M_{w}=\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{\left|\alpha\right|};\\\
w\underset{\operatorname*{wll}}{<}\alpha\end{subarray}}\mathbf{k}\underbrace{M_{w}}_{\begin{subarray}{c}\in
U\\\ \text{(by the induction}\\\ \text{hypothesis)}\end{subarray}}\ \ \ \ \ \
\ \ \ \ \left(\text{since }p\left|x\right|=\left|\alpha\right|\text{ and
}x^{p}=\alpha\right)$
$\displaystyle\subset\sum_{\begin{subarray}{c}w\in\operatorname{Comp}_{N};\\\
w\underset{\operatorname*{wll}}{<}\alpha\end{subarray}}\mathbf{k}U\subset U,$

so that $M_{x^{p}}\in\underbrace{M_{x}^{\left\langle
p\right\rangle}}_{\begin{subarray}{c}\in U\\\ \text{(by
(\ref{exe.thm.QSym.lyndon.Z-genset.hint2}))}\end{subarray}}-U\subset
U-U\subset U$. This rewrites as $M_{\alpha}\in U$ (since $\alpha=x^{p}$). So
$M_{\alpha}\in U$ is proven in both Cases 1 and 2, and thus the induction
proof of (6.28) is finished.]

######  Exercise 6.126.

Prove Theorem 6.82.

Of course, this proof of Theorem 6.82 yields a new (third) proof for
Proposition 6.83.

We notice the following corollary of our approach to Theorem 6.82:

######  Corollary 6.127.

The $\Lambda$-algebra $\operatorname{QSym}$ is a polynomial algebra (over
$\Lambda$).

######  Exercise 6.128.

Prove Corollary 6.127.

[Hint: The algebraically independent generating set $\left(M_{w}^{\left\langle
s\right\rangle}\right)_{\left(w,s\right)\in\mathfrak{RL}\times\left\\{1,2,3,\ldots\right\\}}$
of $\operatorname{QSym}$ contains the elements
$M_{\left(1\right)}^{\left\langle s\right\rangle}=e_{s}\in\Lambda$ for all
$s\in\left\\{1,2,3,\ldots\right\\}$.]

##  7\. Aguiar-Bergeron-Sottile character theory Part I: $\operatorname{QSym}$
as a terminal object

It turns out that the universal mapping property of $\operatorname{NSym}$ as a
free associative algebra leads via duality to a universal property for its
dual $\operatorname{QSym}$, elegantly explaining several combinatorial
invariants that take the form of quasisymmetric or symmetric functions:

  1. $\bullet$

Ehrenborg’s quasisymmetric function of a ranked poset [51],

  2. $\bullet$

Stanley’s chromatic symmetric function of a graph [163],

  3. $\bullet$

the quasisymmetric function of a matroid considered in [20].

###  7.1. Characters and the universal property

######  Definition 7.1.

Given a Hopf algebra $A$ over $\mathbf{k}$, a character is an algebra morphism
$A\overset{\zeta}{\longrightarrow}\mathbf{k}$, that is,

  1. $\bullet$

$\zeta(1_{A})=1_{\mathbf{k}}$,

  2. $\bullet$

$\zeta$ is $\mathbf{k}$-linear, and

  3. $\bullet$

$\zeta(ab)=\zeta(a)\zeta(b)$ for $a,b$ in $A$.

######  Example 7.2.

A particularly important character for $A=\operatorname{QSym}$ is defined as
follows:268268268We are using the notation of Proposition 5.9 here, and we are
still identifying $\operatorname{QSym}$ with
$\operatorname{QSym}\left({\mathbf{x}}\right)$, where ${\mathbf{x}}$ denotes
the infinite chain $\left(x_{1}<x_{2}<\cdots\right)$.

$\begin{array}[]{rcl}\operatorname{QSym}&\overset{\zeta_{Q}}{\longrightarrow}&\mathbf{k}\\\
f({\mathbf{x}})&\longmapsto&f(1,0,0,\ldots)=\left[f({\mathbf{x}})\right]_{x_{1}=1,x_{2}=x_{3}=\cdots=0}.\end{array}$

Hence,

$\zeta_{Q}(M_{\alpha})=\zeta_{Q}(L_{\alpha})=\begin{cases}1&\text{ if
}\alpha=(n)\text{ for some }n,\\\ 0&\text{ otherwise.}\end{cases}$

In other words, the restriction $\zeta_{Q}|_{{\operatorname{QSym}}_{n}}$
coincides with the functional $H_{n}$ in
$\operatorname{NSym}_{n}=\operatorname{Hom}_{\mathbf{k}}(\operatorname{QSym}_{n},\mathbf{k})$:
one has for $f$ in $\operatorname{QSym}_{n}$ that

(7.1) $\zeta_{Q}(f)=(H_{n},f).$

It is worth remarking that there is nothing special about setting $x_{1}=1$
and $x_{2}=x_{3}=\cdots=0$: for quasisymmetric $f$, we could have defined the
same character $\zeta_{Q}$ by picking any variable, say $x_{n}$, and sending

$f({\mathbf{x}})\longmapsto\left[f({\mathbf{x}})\right]_{\begin{subarray}{c}x_{n}=1,\text{
and}\\\ x_{m}=0\text{ for }m\neq n\end{subarray}}.$

This character
$\operatorname{QSym}\overset{\zeta_{Q}}{\longrightarrow}\mathbf{k}$ has a
certain universal property.

######  Theorem 7.3.

A connected graded Hopf algebra $A$ together with a character
$A\overset{\zeta}{\longrightarrow}\mathbf{k}$ induces a unique graded Hopf
morphism $A\overset{\Psi}{\longrightarrow}\operatorname{QSym}$ making this
diagram commute:

(7.2)
$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Psi}$$\scriptstyle{\zeta}$$\textstyle{\operatorname{QSym}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\zeta_{Q}}$$\textstyle{\mathbf{k}}$

Furthermore, $\Psi$ has this formula on elements of $A_{n}$:

(7.3)
$\Psi(a)=\sum_{\alpha\in\operatorname{Comp}_{n}}\zeta_{\alpha}(a)M_{\alpha}$

where for $\alpha=(\alpha_{1},\ldots,\alpha_{\ell})$, the map $\zeta_{\alpha}$
is the composite

$A_{n}\overset{\Delta^{(\ell-1)}}{\longrightarrow}A^{\otimes\ell}\overset{\pi_{\alpha}}{\longrightarrow}A_{\alpha_{1}}\otimes\cdots\otimes
A_{\alpha_{\ell}}\overset{\zeta^{\otimes\ell}}{\longrightarrow}\mathbf{k}$

in which
$A^{\otimes\ell}\overset{\pi_{\alpha}}{\longrightarrow}A_{\alpha_{1}}\otimes\cdots\otimes
A_{\alpha_{\ell}}$ is the canonical projection.