text:
# Structure of the Malvenuto-Reutenauer Hopf algebra of permutations

## Introduction

Malvenuto  introduced the Hopf algebra $`𝔖\mathrm{𝑆𝑦𝑚}`$ of permutations, which has a linear basis $`\{_uu𝔖_n,n0\}`$ indexed by permutations in all symmetric groups $`𝔖_n`$. The Hopf algebra $`𝔖\mathrm{𝑆𝑦𝑚}`$ is non-commutative, non-cocommutative, self-dual, and graded. Among its sub-, quotient-, and subquotient- Hopf algebras are many algebras central to algebraic combinatorics. These include the algebra of symmetric functions , Gessel’s algebra $`𝒬\mathrm{𝑆𝑦𝑚}`$ of quasi-symmetric functions , the algebra of non-commutative symmetric functions , the Loday-Ronco algebra of planar binary trees , Stembridge’s algebra of peaks , the Billera-Liu algebra of Eulerian enumeration , and others. The structure of these combinatorial Hopf algebras with respect to certain distinguished bases has been an important theme in algebraic combinatorics, with applications to the combinatorial problems these algebras were created to study. Here, we obtain a detailed understanding of the structure of $`𝔖\mathrm{𝑆𝑦𝑚}`$, both in algebraic and combinatorial terms.

Our main tool is a new basis $`\{_uu𝔖_n,n0\}`$ for $`𝔖\mathrm{𝑆𝑦𝑚}`$ related to the original basis by Möbius inversion on the weak order on the symmetric groups. These bases $`\{_u\}`$ and $`\{_u\}`$ are analogous to the monomial basis and the fundamental basis of $`𝒬\mathrm{𝑆𝑦𝑚}`$, which are related via Möbius inversion on their index sets, the Boolean posets $`𝒬_n`$. We refer to them as the monomial basis and the fundamental basis of $`𝔖\mathrm{𝑆𝑦𝑚}`$.

We give enumerative-combinatorial descriptions of the product, coproduct, and antipode of $`𝔖\mathrm{𝑆𝑦𝑚}`$ with respect to the monomial basis $`\{_u\}`$. In Section 3, we show that the coproduct is obtained by splitting a permutation at certain special positions that we call global descents. Descents and global descents are left adjoint and right adjoint to a natural map $`𝒬_n𝔖_n`$. These results rely on some non-trivial properties of the weak order developed in Section 2.

The product is studied in Section 4. The structure constants are non-negative integers with the following geometric-combinatorial description. The 1-skeleton of the permutahedron $`\mathrm{\Pi }_{n1}`$ is the Hasse diagram of the weak order on $`𝔖_n`$. The facets of the permutahedron are canonically isomorphic to products of lower dimensional permutahedra. Say that a facet isomorphic to $`\mathrm{\Pi }_{p1}\times \mathrm{\Pi }_{q1}`$ has type $`(p,q)`$. Given $`u𝔖_p`$ and $`v𝔖_q`$, such a facet has a distinguished vertex corresponding to $`(u,v)`$ under the canonical isomorphism. Then, for $`w𝔖_{p+q}`$, the coefficient of $`_w`$ in $`_u_v`$ is the number of facets of the permutahedron $`\mathrm{\Pi }_{p+q1}`$ of type $`(p,q)`$ with the property that the distinguished vertex is below $`w`$ (in the weak order) and closer to $`w`$ than any other vertex in the facet.

In Section 5 we find explicit formulas for the antipode with respect to both bases. The structure constants with respect to the monomial basis have constant sign, as for $`𝒬\mathrm{𝑆𝑦𝑚}`$. The situation is more complicated for the fundamental basis, which may explain why no such explicit formulas were previously known.

Elucidating the elementary structure of $`𝔖\mathrm{𝑆𝑦𝑚}`$ with respect to the monomial basis reveals further algebraic structures of $`𝔖\mathrm{𝑆𝑦𝑚}`$. In Section 6, we show that $`𝔖\mathrm{𝑆𝑦𝑚}`$ is a cofree graded coalgebra. A consequence is that its coradical filtration (a filtration encapsulating the complexity of iterated coproducts) is the algebraic counterpart of a filtration of the symmetric groups by certain lower order ideals. In particular, we show that the space of primitive elements is spanned by the set $`\{_uu\text{ has no global descents}\}`$. Cofreenes was shown by Poirier and Reutenauer  in dual form, through the introduction of a different basis. The study of primitive elements was pursued from this point of view by Duchamp, Hivert, and Thibon . The generating function for the graded space of primitive elements is

$$1\frac{1}{_{n0}n!x^n}.$$

Comtet essentially studied the combinatorics of global descents \[6, Exercise VI.14\]. These results add an algebraic perspective to the pure combinatorics he studied.

There is a well-known morphism of Hopf algebras $`𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚}`$ that maps one fundamental basis onto the other, by associating to a permutation $`u`$ its descent set $`\mathrm{Des}(u)`$. In Section 7, we describe this map on the monomial bases and then derive a new geometric description for the product of monomial quasi-symmetric functions in which the role of the permutahedron is played by the cube.

In Section 8 we show that $`𝔖\mathrm{𝑆𝑦𝑚}`$ decomposes as a crossed product over $`𝒬\mathrm{𝑆𝑦𝑚}`$. This construction from the theory of Hopf algebras is a generalization of the notion of group extensions. We provide a combinatorial description for the Hopf kernel of the map $`𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚}`$, which is a subalgebra of $`𝔖\mathrm{𝑆𝑦𝑚}`$.

We study the self-duality of $`𝔖\mathrm{𝑆𝑦𝑚}`$ in Section 9 and its enumerative consequences. For instance, a result of Foata and Schützenberger  on the numbers

$$d(𝖲,𝖳):=\mathrm{\#}\{w𝔖_n\mathrm{Des}(w)=𝖲,\mathrm{Des}(w^1)=𝖳\}$$

follows directly from this self-duality and we obtain analogous results for the numbers

$$\theta (u,v):=\mathrm{\#}\{w𝔖_nwu,w^1v\}.$$

Most of the order-theoretic properties that underlie these algebraic results are presented in Section 2. Central to these are the existence of two Galois connections (involving descents and global descents) between the posets of permutations of $`[n]`$ and of subsets of $`[n1]`$, as well as the order properties of the decomposition of $`𝔖_n`$ into cosets of $`𝔖_p\times 𝔖_q`$.

We thank Swapneel Mahajan, who suggested a simplification to the proof of Theorem 3.1, Nantel Bergeron, one of whose questions motivated the results of Section 8, and the referees of an abridged version for helpful comments.

## 1. Basic definitions and results

We use only elementary properties of Hopf algebras, as given in the book . Our Hopf algebras $`H`$ will be graded connected Hopf algebras over $``$. Thus the $``$-algebra $`H`$ is the direct sum $`\{H_nn=0,1,\mathrm{}\}`$ of its homogeneous components $`H_n`$, with $`H_0=`$, the product and coproduct respect the grading, and the counit is projection onto $`H_0`$.

Throughout, $`n`$ is a non-negative integer and $`[n]`$ denotes the set $`\{1,2,\mathrm{},n\}`$. A composition $`\alpha `$ of $`n`$ is a sequence $`\alpha =(\alpha _1,\mathrm{},\alpha _k)`$ of positive integers with $`n=\alpha _1+\alpha _2+\mathrm{}+\alpha _k`$. To a composition $`\alpha `$ of $`n`$, we associate the set $`I(\alpha ):=\{\alpha _1,\alpha _1+\alpha _2,\mathrm{},\alpha _1+\mathrm{}+\alpha _{k1}\}`$. This gives a bijection between compositions of $`n`$ and subsets of $`[n1]`$. Compositions of $`n`$ are partially ordered by *refinement*. The cover relations are of the form

$$(\alpha _1,\mathrm{},\alpha _i+\alpha _{i+1},\mathrm{},\alpha _k)(\alpha _1,\mathrm{},\alpha _k).$$

Under the association $`\alpha I(\alpha )`$, refinement corresponds to set inclusion, so we simply identify the poset of compositions with the Boolean poset $`𝒬_n`$ of subsets of $`[n1]`$.

Let $`𝔖_n`$ be the group of permutations of $`[n]`$. We use one-line notation for permutations, writing $`u=(u_1,u_2,\mathrm{},u_n)`$ where $`u_i=u(i)`$. Sometimes we may omit the commas and write $`u=u_1\mathrm{}u_n`$. A permutation $`u`$ has a *descent* at a position $`p`$ if $`u_p>u_{p+1}`$. An *inversion* in a permutation $`u𝔖_n`$ is a pair of positions $`1i<jn`$ with $`u_i>u_j`$. The set of descents and inversions are denoted by $`\mathrm{Des}(u)`$ and $`\mathrm{Inv}(u)`$, respectively. The length of a permutation $`u`$ is $`\mathrm{}(u)=\mathrm{\#}\mathrm{Inv}(u)`$.

Given $`p,q0`$, we consider the product $`𝔖_p\times 𝔖_q`$ to be a subgroup of $`𝔖_{p+q}`$, where $`𝔖_p`$ permutes $`[p]`$ and $`𝔖_q`$ permutes $`\{p+1,\mathrm{},p+q\}`$. For $`u𝔖_p`$ and $`v𝔖_q`$, write $`u\times v`$ for the permutation in $`𝔖_{p+q}`$ corresponding to $`(u,v)𝔖_p\times 𝔖_q`$ under this embedding.

More generally, given a subset $`𝖲=\{p_1<\mathrm{}<p_k\}`$ of $`[n1]`$, we have the (standard) parabolic or Young subgroup

$$𝔖_𝖲:=𝔖_{p_1}\times 𝔖_{p_2p_1}\times \mathrm{}\times 𝔖_{np_k}𝔖_n.$$

The notation $`𝔖_𝖲`$ suppresses the dependence on $`n`$, which will either be understood or will be made explicit when this is used.

Lastly, we use $``$ to denote disjoint union.

### 1.1. The Hopf algebra of permutations of Malvenuto and Reutenauer

Let $`𝔖\mathrm{𝑆𝑦𝑚}`$ be the graded vector space over $``$ with basis $`_{n0}𝔖_n`$, graded by $`n`$. This vector space has a graded Hopf algebra structure first considered in Malvenuto’s thesis \[22, §5.2\] and in her work with Reutenauer . (In , it is called the algebra of free quasi-symmetric functions.) Write $`_u`$ for the basis element corresponding to $`u𝔖_n`$ for $`n>0`$ and $`1`$ for the basis element of degree $`0`$.

The product of two basis elements is obtained by shuffling the corresponding permutations, as in the following example.

$`_{\textcolor[rgb]{0,0,1}{12}}_{\textcolor[rgb]{0.4,0,0}{312}}`$ $`=`$ $`_{\textcolor[rgb]{0,0,1}{12}\textcolor[rgb]{0.4,0,0}{534}}+_{\textcolor[rgb]{0,0,1}{1}\textcolor[rgb]{0.4,0,0}{5}\textcolor[rgb]{0,0,1}{2}\textcolor[rgb]{0.4,0,0}{34}}+_{\textcolor[rgb]{0,0,1}{1}\textcolor[rgb]{0.4,0,0}{53}\textcolor[rgb]{0,0,1}{2}\textcolor[rgb]{0.4,0,0}{4}}+_{\textcolor[rgb]{0,0,1}{1}\textcolor[rgb]{0.4,0,0}{534}\textcolor[rgb]{0,0,1}{2}}+_{\textcolor[rgb]{0.4,0,0}{5}\textcolor[rgb]{0,0,1}{12}\textcolor[rgb]{0.4,0,0}{34}}`$
$`+_{\textcolor[rgb]{0.4,0,0}{5}\textcolor[rgb]{0,0,1}{1}\textcolor[rgb]{0.4,0,0}{3}\textcolor[rgb]{0,0,1}{2}\textcolor[rgb]{0.4,0,0}{4}}+_{\textcolor[rgb]{0.4,0,0}{5}\textcolor[rgb]{0,0,1}{1}\textcolor[rgb]{0.4,0,0}{34}\textcolor[rgb]{0,0,1}{2}}+_{\textcolor[rgb]{0.4,0,0}{53}\textcolor[rgb]{0,0,1}{12}\textcolor[rgb]{0.4,0,0}{4}}+_{\textcolor[rgb]{0.4,0,0}{53}\textcolor[rgb]{0,0,1}{1}\textcolor[rgb]{0.4,0,0}{4}\textcolor[rgb]{0,0,1}{2}}+_{\textcolor[rgb]{0.4,0,0}{534}\textcolor[rgb]{0,0,1}{12}}.`$
More precisely, for $`p,q>0`$, set

$`𝔖^{(p,q)}:=`$ $`\{\zeta 𝔖_{p+q}\zeta \text{ has at most one descent, at position }p\}`$
$`=`$ $`\{\zeta 𝔖_{p+q}\zeta _1<\mathrm{}<\zeta _p,\zeta _{p+1}<\mathrm{}<\zeta _n\}.`$
This is the collection of minimal (in length) representatives of left cosets of $`𝔖_p\times 𝔖_q`$ in $`𝔖_{p+q}`$. In the literature, they are sometimes referred to as $`(p,q)`$-shuffles, but sometimes it is the inverses of these permutations that carry that name. We will refer to them as Grassmannian permutations. With these definitions, we describe the product. For $`u𝔖_p`$ and $`v𝔖_q`$, set

(1.1)
$$_u_v=\underset{\zeta 𝔖^{(p,q)}}{}_{(u\times v)\zeta ^1}.$$

This endows $`𝔖\mathrm{𝑆𝑦𝑚}`$ with the structure of a graded algebra with unit 1.

The algebra $`𝔖\mathrm{𝑆𝑦𝑚}`$ is also a graded coalgebra with coproduct given by all ways of splitting a permutation. For a sequence $`(a_1,\mathrm{},a_p)`$ of distinct integers, let its standard permutationfootnotetext: Some authors call this flattening. $`\mathrm{st}(a_1,\mathrm{},a_p)𝔖_p`$ be the permutation $`u`$ defined by

(1.2)
$$u_i<u_ja_i<a_j.$$

For instance, $`\mathrm{st}(625)=312`$. The coproduct $`\mathrm{\Delta }:𝔖\mathrm{𝑆𝑦𝑚}𝔖\mathrm{𝑆𝑦𝑚}\text{ }𝔖\mathrm{𝑆𝑦𝑚}`$ is defined by

(1.3)
$$\mathrm{\Delta }(_u)=\underset{p=0}{\overset{n}{}}_{\mathrm{st}(u_1,\mathrm{},u_p)}\text{ }_{\mathrm{st}(u_{p+1},\mathrm{},u_n)},$$

when $`u𝔖_n`$. For instance, $`\mathrm{\Delta }(_{42531})`$ is

$$1\text{ }_{42531}+_1\text{ }_{2431}+_{21}\text{ }_{321}+_{213}\text{ }_{21}+_{3142}\text{ }_1+_{42531}\text{ }1.$$

$`𝔖\mathrm{𝑆𝑦𝑚}`$ is a graded connected Hopf algebra \[22, théorème 5.4\].

We refer to the set $`\{_u\}`$ as the fundamental basis of $`𝔖\mathrm{𝑆𝑦𝑚}`$. The main goal of this paper is to obtain a detailed description of the Hopf algebra structure of $`𝔖\mathrm{𝑆𝑦𝑚}`$. To this end, the definition of a second basis for $`𝔖\mathrm{𝑆𝑦𝑚}`$ (in § 1.3) will prove crucial.

This Hopf algebra $`𝔖\mathrm{𝑆𝑦𝑚}`$ of Malvenuto and Reutenauer has been an object of recent interest . We remark that sometimes it is the dual Hopf algebra that is considered. To compare results, one may use that $`𝔖\mathrm{𝑆𝑦𝑚}`$ is self-dual under the map $`_u_{u^1}^{}`$, where $`_{u^1}^{}`$ is the element of the dual basis that is dual to $`_{u^1}`$. We explore this further in Section 9.

### 1.2. The Hopf algebra of quasi-symmetric functions

Basic references for quasi-symmetric functions are \[29, 9.4\] and \[33, Section 7.19\]; however, everything we need will be reviewed here.

The algebra $`𝒬\mathrm{𝑆𝑦𝑚}`$ of quasi-symmetric functions is a subalgebra of the algebra of formal power series in countably many variables $`x_1,x_2,\mathrm{}`$. It has a basis of monomial quasi-symmetric functions $`M_\alpha `$ indexed by compositions $`\alpha =(\alpha _1,\mathrm{},\alpha _k)`$, where

$$M_\alpha :=\underset{i_1<\mathrm{}<i_k}{}x_{i_1}^{\alpha _1}x_{i_2}^{\alpha _2}\mathrm{}x_{i_k}^{\alpha _k}.$$

The product of these monomial functions is given by quasi-shuffles of their indices. A *quasi-shuffle* of compositions $`\alpha `$ and $`\beta `$ is a shuffle of the components of $`\alpha `$ and $`\beta `$, where in addition we may replace any number of pairs of consecutive components $`(\alpha _i,\beta _j)`$ in the shuffle by $`\alpha _i+\beta _j`$. Then we have

(1.4)
$$M_\alpha M_\beta =\underset{\gamma }{}M_\gamma ,$$

where the sum is over all quasi-shuffles $`\gamma `$ of the compositions $`\alpha `$ and $`\beta `$. For instance,

(1.5)
$$M_{(2)}M_{(1,1)}=M_{(1,1,2)}+M_{(1,2,1)}+M_{(2,1,1)}+M_{(1,3)}+M_{(3,1)}.$$

The unit element is indexed by the empty composition $`1=M_{()}`$.

Let $`X`$ and $`Y`$ be two countable ordered sets and $`XY`$ its disjoint union, totally ordered by $`X<Y`$. Then $`\mathrm{\Delta }:f(X)f(XY)`$ gives $`𝒬\mathrm{𝑆𝑦𝑚}`$ the structure of a coalgebra. In terms of the monomial quasi-symmetric functions, we have

(1.6)
$$\mathrm{\Delta }\left(M_{(\alpha _1,\mathrm{},\alpha _k)}\right)=\underset{p=0}{\overset{k}{}}M_{(\alpha _1,\mathrm{},\alpha _p)}\text{ }M_{(\alpha _{p+1},\mathrm{},\alpha _k)}.$$

For instance, $`\mathrm{\Delta }(M_{(2,1)})=1\text{ }M_{(2,1)}+M_{(2)}\text{ }M_{(1)}+M_{(2,1)}\text{ }1`$.

The algebra of quasi-symmetric functions was introduced by Gessel . Its Hopf algebra structure was introduced by Malvenuto \[22, Section 4.1\]. The description of the product in terms of quasi-shuffles can be found in  and is equivalent to \[10, Lemma 3.3\]. A $`q`$-version of this construction appears in \[36, Section 5\] and .

The algebra $`𝒬\mathrm{𝑆𝑦𝑚}`$ is a graded connected Hopf algebra whose component in degree $`n`$ is spanned by those $`M_\alpha `$ with $`\alpha `$ a composition of $`n`$. Malvenuto \[22, corollaire 4.20\] and Ehrenborg \[10, Proposition 3.4\] independently gave an explicit formula for the antipode

(1.7)
$$S(M_\alpha )=(1)^{c(\alpha )}\underset{\beta \alpha }{}M_{\stackrel{~}{\beta }}.$$

Here, $`c(\alpha )`$ is the number of components of $`\alpha `$, and if $`\beta =(\beta _1,\beta _2,\mathrm{},\beta _t)`$ then $`\stackrel{~}{\beta }`$ is $`\beta `$ written in reverse order $`(\beta _t,\mathrm{},\beta _2,\beta _1)`$.

Gessel’s fundamental quasi-symmetric function $`F_\alpha `$ is defined by

$$F_\alpha =\underset{\alpha \beta }{}M_\beta ,$$

By Möbius inversion, we have

$$M_\alpha =\underset{\alpha \beta }{}(1)^{c(\beta )c(\alpha )}F_\beta .$$

Thus the set $`\{F_\alpha \}`$ forms another basis of $`𝒬\mathrm{𝑆𝑦𝑚}`$.

It is sometimes advantageous to index these monomial and fundamental quasi-symmetric functions by subsets of $`[n1]`$. Accordingly, given a composition $`\alpha `$ of $`n`$ with $`𝖲=I(\alpha )`$, we define

$$F_𝖲:=F_\alpha \text{and}M_𝖲:=M_\alpha .$$

The notation $`F_𝖲`$ suppresses the dependence on $`n`$, which will be usually understood from the context; otherwise it will be made explicit by writing $`F_{𝖲,n}`$.

In terms of power series,

(1.8)
$$F_𝖲=\underset{\begin{array}{c}i_1i_2\mathrm{}i_n\\ p𝖲i_p<i_{p+1}\text{}\end{array}}{}x_{i_1}x_{i_2}\mathrm{}x_{i_n}.$$

We mention that there is an analogous realization of the Malvenuto-Reutenauer Hopf algebra as a subalgebra of an algebra of non-commutative power series, due to Duchamp, Hivert, and Thibon. To this end, one defines

(1.9)
$$_u=\underset{\begin{array}{c}i_1i_2\mathrm{}i_n\\ p\mathrm{Des}(u)i_p<i_{p+1}\text{}\end{array}}{}x_{i_{u^1(1)}}x_{i_{u^1(2)}}\mathrm{}x_{i_{u^1(n)}}.$$

This is discussed in \[8, Section 3.1\], in slightly different terms. In this realization, the coproduct of $`𝔖\mathrm{𝑆𝑦𝑚}`$ is induced by the ordinal sum of commuting alphabets \[8, Prop. 3.4\].

### 1.3. The monomial basis of the Malvenuto-Reutenauer Hopf algebra

The descent set of a permutation $`u𝔖_n`$ is the subset of $`[n1]`$ recording the descents of $`u`$

(1.10)
$$\mathrm{Des}(u):=\{p[n1]u_p>u_{p+1}\}.$$

Thus $`\mathrm{Des}(46512837)=\{2,3,6\}`$. Malvenuto \[22, théorèmes 5.12, 5.13, and 5.18\] shows that there is a morphism of Hopf algebras

(1.11)
$$\begin{array}{ccccc}\hfill 𝒟& :& \hfill 𝔖\mathrm{𝑆𝑦𝑚}& & 𝒬\mathrm{𝑆𝑦𝑚}\hfill \\ & & \hfill _u& & F_{\mathrm{Des}(u)}\text{}\hfill \end{array}$$

(This is equivalent to Theorem 3.3 in .) This explains our name and notation for the fundamental basis of $`𝔖\mathrm{𝑆𝑦𝑚}`$. This map extends to power series, where it is simply the abelianization: there is a commutative diagram

This is evident from (1.8) and (1.9). It is easy to see, however, that $`𝒟`$ is not the abelianization of $`𝔖\mathrm{𝑆𝑦𝑚}`$.

In analogy to the basis of monomial quasi-symmetric functions, we define a new *monomial* basis $`\{_u\}`$ for the Malvenuto-Reutenauer Hopf algebra. For each $`n0`$ and $`u𝔖_n`$, let

(1.12)
$$_u:=\underset{uv}{}\mu _{𝔖_n}(u,v)_v,$$

where $`uv`$ in the weak order in $`𝔖_n`$ (described in Section 2) and $`\mu _{𝔖_n}`$ is the Möbius function of this partial order. By Möbius inversion,

(1.13)
$$_u:=\underset{uv}{}_v,$$

so these elements $`_u`$ indeed form a basis of $`𝔖\mathrm{𝑆𝑦𝑚}`$. For instance,

$$_{4123}=_{4123}_{4132}_{4213}+_{4321}.$$

We will show that $`_u`$ maps either to $`M_{\mathrm{Des}(u)}`$ or to 0 under the map $`𝒟:𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚}`$.

## 2. The weak order on the symmetric group

Let $`\mathrm{Inv}(u)`$ be the set of inversions of a permutation $`u𝔖_n`$,

$$\mathrm{Inv}(u):=\{(i,j)[n]\times [n]i<j\text{ and }u_i>u_j\}.$$

The inversion set determines the permutation. Given $`u`$ and $`v𝔖_n`$, we write $`uv`$ if $`\mathrm{Inv}(u)\mathrm{Inv}(v)`$. This defines the left weak order on $`𝔖_n`$.

Figure 1 shows the (left) weak order on $`𝔖_4`$. The weak order has another characterization

$$uvw𝔖_n\text{ such that }v=wu\text{ and }\mathrm{}(v)=\mathrm{}(w)+\mathrm{}(u),$$

where $`\mathrm{}(u)`$ is the number of inversions of $`u`$. The cover relations $`uv`$ occur when $`w`$ is an adjacent transposition. Thus, $`uv`$ precisely when $`v`$ is obtained from $`u`$ by transposing a pair of consecutive values of $`u`$; a pair $`(u_i,u_j)`$ such that $`i<j`$ and $`u_j=u_i+1`$. The identity permutation $`1_n`$ is the minimum element of $`𝔖_n`$ and $`\omega _n=(n,\mathrm{},2,1)`$ is the maximum.

This weak order is a lattice , whose structure we describe. First, a set $`J`$ is the inversion set of a permutation in $`𝔖_n`$ if and only if both $`J`$ and its complement $`\mathrm{Inv}(\omega _n)J`$ are transitively closed ($`(i,j)J`$ and $`(j,k)J`$ imply $`(i,k)J`$, and the same for its complement). The join (least upper bound) of two permutations $`u`$ and $`v𝔖_n`$ is the permutation $`uv`$ whose inversion set is the transitive closure of the union of the inversion sets of $`u`$ and $`v`$

(2.1)
$$\{(i,j)\text{ chain }i=k_0<\mathrm{}<k_s=j\text{ s.t. }r,(k_{r1},k_r)\mathrm{Inv}(u)\mathrm{Inv}(v)\}.$$

Similarly, the meet (greatest lower bound) of $`u`$ and $`v`$ is the permutation $`uv`$ whose inversion set is

(2.2)
$$\{(i,j)\text{ chains }i=k_0<\mathrm{}<k_s=j,r\text{ s.t. }(k_{r1},k_r)\mathrm{Inv}(u)\mathrm{Inv}(v)\}.$$

The Möbius function of the weak order takes values in $`\{1,0,1\}`$. Explicit descriptions can be found in \[3, Corollary 3\] or \[9, Theorem 1.2\]. We will not need that description, but will use several basic facts on the weak order that we develop here.

### 2.1. Grassmannian permutations and the weak order

In Section 1, we defined $`𝔖^{(p,q)}`$ to be the set of minimal (in length) representatives of (left) cosets of $`𝔖_p\times 𝔖_q`$ in the symmetric group $`𝔖_{p+q}`$. Thus the map

$$\begin{array}{ccccc}\hfill \lambda & :& 𝔖^{(p,q)}\times 𝔖_p\times 𝔖_q& & 𝔖_{p+q}\\ & & (\zeta ,u,v)& & \zeta (u\times v)\text{}\end{array}$$

is a bijection. We leave the following description of the inverse to the reader.

###### Lemma 2.1.

Let $`w𝔖_{p+q}`$, and set $`\zeta :=w\left(\mathrm{st}(w_1,\mathrm{},w_p)\times \mathrm{st}(w_{p+1},\mathrm{},w_{p+q})\right)^1`$. Then $`\zeta 𝔖^{(p,q)}`$ and $`\lambda ^1(w)=(\zeta ,\mathrm{st}(w_1,\mathrm{},w_p),\mathrm{st}(w_{p+1},\mathrm{},w_{p+q}))`$.

We describe the order-theoretic properties of this decomposition into cosets.The first step is to characterize the inversion sets of Grassmannian permutations. A subset $`J`$ of $`[p]\times [q]`$ is cornered if $`(h,k)J`$ implies that $`(i,j)J`$ whenever $`1ih`$ and $`1jk`$. The reason for this definition is that a set $`I`$ is the inversion set of a Grassmannian permutation $`\zeta 𝔖^{(p,q)}`$ if and only if

(2.3)
$$\begin{array}{cc}\hfill (i)& I\{1,\mathrm{},p\}\times \{p+1,\mathrm{},p+q\},\text{ and}\hfill \\ \hfill (ii)& \text{the shifted set }\{(p+1i,jp)(i,j)I\}[p]\times [q]\text{ is cornered}.\text{}\hfill \end{array}$$

Given an arbitrary subset $`J`$ of $`[p]\times [q]`$, let $`cr(J)`$ denote the smallest cornered subset containing $`J`$. Denote the obvious action of $`(u,v)𝔖_p\times 𝔖_q`$ on a subset $`J`$ of $`[p]\times [q]`$ by $`(u,v)(J)`$.

###### Lemma 2.2.

Let $`J`$ be a cornered subset of $`[p]\times [q]`$ and $`u𝔖_p`$ and $`v𝔖_q`$ any permutations. Then

$$J\mathrm{cr}\left((u,v)(J)\right).$$

###### Proof.

Let $`(i,j)J`$. The set $`\{u(h)1hi\}`$ has $`i`$ elements. Hence there is a number $`h`$ such that $`1hi`$ and $`u(h)i`$. Similarly there is number $`k`$ such that $`1kj`$ and $`v(k)j`$. Since $`J`$ is cornered, $`(h,k)J`$. Hence $`(u(h),v(k))(u,v)(J)`$. By construction, $`iu(h)`$ and $`jv(k)`$, so $`(i,j)\mathrm{cr}\left((u,v)(J)\right)`$, as needed. ∎

Denote the diagonal action of $`w𝔖_n`$ on a subset $`I`$ of $`[n]\times [n]`$ by $`w(I)`$. Suppose $`w=u\times v𝔖_p\times 𝔖_q`$ and $`I\{1,\mathrm{},p\}\times \{p+1,\mathrm{},p+q\}`$. Let $`J`$ be the result of shifting $`I`$, as in (2.3)(ii). It is easy to see that the result of shifting $`(u\times v)(I)`$ is $`(\stackrel{~}{u},v)(J)`$, where $`\stackrel{~}{u}(i)=p+1u(p+1i)`$.

###### Corollary 2.3.

Let $`\zeta `$ and $`\zeta ^{}𝔖^{(p,q)}`$ be Grassmannian permutations, and $`u𝔖_p`$ and $`v𝔖_q`$ be permutations. If $`(u\times v)\left(\mathrm{Inv}(\zeta )\right)\mathrm{Inv}(\zeta ^{})`$ then $`\zeta \zeta ^{}`$.

###### Proof.

We show that $`\mathrm{Inv}(\zeta )\mathrm{Inv}(\zeta ^{})`$. Let $`J`$ and $`J^{}`$ be the corresponding shifted sets. According to the previous discussion and the hypothesis, $`(\stackrel{~}{u},v)(J)J^{}`$. Hence cr$`\left((\stackrel{~}{u},v)(J)\right)J^{}`$, since $`J^{}`$ is cornered. By Lemma 2.2, $`J\mathrm{cr}\left((\stackrel{~}{u},v)(J)\right)`$, so $`JJ^{}`$. This implies the inclusion of inversion sets, as needed. ∎

The following lemma is straightforward.

###### Lemma 2.4.

Let $`\zeta 𝔖^{(p,q)}`$, $`u𝔖_p`$, $`v𝔖_q`$ and $`w:=\zeta (u\times v)𝔖_{p+q}`$. There is a decomposition of $`\mathrm{Inv}(w)`$ into disjoint subsets

$$\mathrm{Inv}(w)=\mathrm{Inv}(u)\left((p,p)+\mathrm{Inv}(v)\right)(u^1\times v^1)\left(\mathrm{Inv}(\zeta )\right).$$

We deduce some order-theoretic properties of the decomposition into left cosets. Define $`\zeta _{p,q}`$ to be the permutation of maximal length in $`𝔖^{(p,q)}`$, so that

$$\zeta _{p,q}:=(q+1,q+2,\mathrm{},q+p,1,\mathrm{\hspace{0.17em}2},\mathrm{},q).$$

###### Proposition 2.5.

Let $`\lambda :𝔖^{(p,q)}\times 𝔖_p\times 𝔖_q𝔖_{p+q}`$ be the bijection

$$\lambda (\zeta ,u,v)=\zeta (u\times v).$$

Then

* $`\lambda ^1`$ is order preserving. That is,

$$\zeta (u\times v)\zeta ^{}(u^{}\times v^{})\zeta \zeta ^{},uu^{},\text{ and }vv^{}.$$
* $`\lambda `$ is order preserving when restricted to any of the following sets

$$\{\zeta _{p,q}\}\times 𝔖_p\times 𝔖_q,\{1_{p+q}\}\times 𝔖_p\times 𝔖_q,\text{ or }𝔖^{(p,q)}\times \{(u,v)\},$$

for any $`u𝔖_p`$, $`v𝔖_q`$.

###### Proof.

Let $`w=\zeta (u\times v)`$ and $`w^{}=\zeta ^{}(u^{}\times v^{})`$. Suppose $`ww^{}`$, so that $`\mathrm{Inv}(w)\mathrm{Inv}(w^{})`$. By Lemma 2.4, we have $`\mathrm{Inv}(u)\mathrm{Inv}(u^{})`$, $`\mathrm{Inv}(v)\mathrm{Inv}(v^{})`$, and $`(u^{\prime \prime }\times v^{\prime \prime })\left(\mathrm{Inv}(\zeta )\right)\mathrm{Inv}(\zeta ^{})`$, where $`u^{\prime \prime }:=u^{}u^1`$ and $`v^{\prime \prime }:=v^{}v^1`$. Therefore, $`uu^{}`$, $`vv^{}`$, and by Corollary 2.3, $`\zeta \zeta ^{}`$. This proves (i).

Statement (ii) follows by a similar application of Lemma 2.4, noting that $`\mathrm{Inv}(\zeta _{p,q})=\{1,\mathrm{},p\}\times \{p+1,\mathrm{},n\}`$ and $`\mathrm{Inv}(1_{p+q})=\mathrm{}`$ are invariant under any permutation in $`𝔖_p\times 𝔖_q`$. ∎

Since Grassmannian permutations in $`𝔖^{(p,q)}`$ are left coset representatives of $`𝔖_p\times 𝔖_q`$ in $`𝔖_{p+q}`$, their inverses are right coset representatives. We discuss order-theoretic properties of this decomposition into right cosets.

Given a subset $`J`$ of $`[n]\times [n]`$, let

$$\stackrel{~}{J}=\{(j,i)(i,j)J\}.$$

We have the following key observation about the diagonal action of $`𝔖_n`$ on subsets of $`[n]\times [n]`$.

###### Lemma 2.6.

For any $`u𝔖_n`$, we have $`u\left(\stackrel{~}{\mathrm{Inv}(u)}\right)=\mathrm{Inv}(u^1)`$.

Proof. Note that $`u^1(u_i)=i`$. Thus $`\mathrm{Inv}(u^1)=\{u_h<u_kh>k\}`$. Then

$`\mathrm{}\text{}`$
$$u^1\left(\mathrm{Inv}(u^1)\right)=\{(h,k)k<h\text{ and }u_k>u_h\}=\stackrel{~}{\mathrm{Inv}(u)}.$$

###### Proposition 2.7.

Fix $`\zeta 𝔖^{(p,q)}`$ and consider the map $`\rho _\zeta :𝔖_p\times 𝔖_q𝔖_{p+q}`$ given by

$$\rho _\zeta (u,v)=(u\times v)\zeta ^1.$$

Then $`\rho _\zeta `$ is a convex embedding in the sense that

* $`\rho _\zeta `$ is injective;
* $`\rho _\zeta `$ is order-preserving: $`uu^{}\text{ and }vv^{}\rho _\zeta (u,v)\rho _\zeta (u^{},v^{})`$;
* $`\rho _\zeta `$ is convex: If $`\rho _\zeta (u,v)w\rho _\zeta (u^{},v^{})`$, for some $`u,u^{}𝔖_p`$ and $`v,v^{}𝔖_q`$, then there are $`u^{\prime \prime }𝔖_p`$ and $`v^{\prime \prime }𝔖_q`$ with $`w=\rho _\zeta (u^{\prime \prime },v^{\prime \prime })`$.

It follows that

* $`\rho _\zeta `$ preserves meets and joins.

###### Proof.

Assertion (a) is immediate. Set $`w:=(u\times v)\zeta ^1=\rho _\zeta (u,v)`$. Then $`w^1=\zeta (u^1\times v^1)`$. By Lemmas 2.4 and 2.6, we have

$`\mathrm{Inv}(w)`$ $`=`$ $`w^1\left(\stackrel{~}{\mathrm{Inv}(w^1)}\right)`$
$`=`$ $`\zeta (u^1\times v^1)\left(\stackrel{~}{\mathrm{Inv}(u^1)}\left((p,p)+\stackrel{~}{\mathrm{Inv}(v^1)}\right)(u\times v)\left(\stackrel{~}{\mathrm{Inv}(\zeta )}\right)\right)`$
$`=`$ $`\zeta \left(\mathrm{Inv}(u)\left((p,p)+\mathrm{Inv}(v)\right)\stackrel{~}{\mathrm{Inv}(\zeta )}\right).`$
Assertion (b) follows from this and the characterization of the weak order in terms of inversion sets.

For (c), decompose $`w=(u^{\prime \prime }\times v^{\prime \prime })\xi ^1`$. By assumption,

$$\zeta \left(\stackrel{~}{\mathrm{Inv}(\zeta )}\right)\xi \left(\stackrel{~}{\mathrm{Inv}(\xi )}\right)\zeta \left(\stackrel{~}{\mathrm{Inv}(\zeta )}\right).$$

Then $`\zeta =\xi `$ by Lemma 2.6, so $`w=\rho _\zeta (u^{\prime \prime },v^{\prime \prime })`$ as needed. ∎

### 2.2. Cosets of parabolic subgroups and the weak order

Write a subset $`𝖲`$ of $`[n1]`$ as $`𝖲=\{p_1<\mathrm{}<p_k\}`$. In Section 1, we defined the parabolic subgroup

$$𝔖_𝖲=𝔖_{p_1}\times 𝔖_{p_2p_1}\times \mathrm{}\times 𝔖_{np_k}𝔖_n.$$

Let $`𝔖^𝖲`$ be the set of minimal (in length) representatives of left cosets of $`𝔖_𝖲`$ in $`𝔖_n`$,

$$𝔖^𝖲=\{\zeta 𝔖_n\mathrm{Des}(\zeta )𝖲\}.$$

Grassmannian permutations are the special case $`𝔖^{(p,np)}=𝔖^{\{p\}}`$.

Let $`\zeta _𝖲`$ be the permutation of maximal length in $`𝔖^𝖲`$,

(2.4)
$$\zeta _𝖲:=(np_1+1,\mathrm{},n,np_2+1,\mathrm{},np_1,\mathrm{},1,\mathrm{},np_k).$$

We record the following facts about these coset representatives.

###### Lemma 2.8.

$`𝔖^𝖲`$ is an interval in the weak order of $`𝔖_n`$. The minimum element is the identity $`1_n`$ and the maximum is $`\zeta _𝖲`$.

Our proofs rely upon the following basic fact. Suppose $`p,q`$ are positive integers and $`𝖳`$ is a subset of $`[p1]`$. Define the subset $`𝖲`$ of $`[p+q1]`$ to be $`𝖳\{p\}`$. Then $`(\zeta ,\zeta ^{})\zeta (\zeta ^{}\times 1_q)`$ defines a bijection

(2.5)
$$𝔖^{(p,q)}\times 𝔖^𝖳𝔖^𝖲$$

The maximum elements are preserved under this map

(2.6)
$$\zeta _{p,q}(\zeta _𝖳\times 1_q)=\zeta _𝖲.$$

The analog of Proposition 2.5 for this decomposition of $`𝔖_n`$ into left cosets of $`𝔖_𝖲`$ follows from Proposition 2.5 by induction using (2.5) and (2.6).

###### Proposition 2.9.

Suppose $`𝖲`$ is a subset of $`[n1]`$. Let $`\lambda :𝔖^𝖲\times 𝔖_𝖲𝔖_n`$ be the bijection

$$\lambda (\zeta ,u)=\zeta u.$$

Then $`\lambda ^1`$ is order preserving, while $`\lambda `$ is order preserving when restricted to any of the following sets

$$\{\zeta _𝖲\}\times 𝔖_𝖲,\{1_n\}\times 𝔖_𝖲,\text{ or }𝔖^𝖲\times \{u\},\text{ for any }u𝔖_𝖲.$$

We state the analog of Proposition 2.7.

###### Proposition 2.10.

Let $`𝖲`$ be a subset of $`[n1]`$. Fix $`\zeta 𝔖^𝖲`$ and consider the map $`\rho _\zeta :𝔖_𝖲𝔖_n`$ given by

$$\rho _\zeta (u)=u\zeta ^1.$$

Then $`\rho _\zeta `$ is a convex embedding. In particular, it preserves meets and joins.

### 2.3. Descents

Let $`𝒬_n`$ denote the Boolean poset of subsets of $`[n1]`$, which we identify with the poset of compositions of $`n`$. We have the descent map $`\mathrm{Des}:𝔖_n𝒬_n`$ given by $`u\mathrm{Des}(u)`$, the descent set (1.10) of $`u`$. Let $`Z:𝒬_n𝔖_n`$ be the map defined by $`𝖲\zeta _𝖲`$, the maximum left coset representative of $`𝔖_𝖲`$ as in (2.4).

A *Galois connection* between posets $`P`$ and $`Q`$ is a pair $`(f,g)`$ of order preserving maps $`f:PQ`$ and $`g:QP`$ such that for any $`xP`$ and $`yQ`$,

(2.7)
$$f(x)yxg(y).$$

###### Proposition 2.11.

The pair of maps $`(\mathrm{Des},Z):𝔖_n𝒬_n`$ is a Galois connection.

###### Proof.

We verify that

* $`\mathrm{Des}:𝔖_n𝒬_n`$ is order preserving;
* $`Z:𝒬_n𝔖_n`$ is order preserving;
* $`\mathrm{Des}Z=id_{𝒬_n}`$;
* $`Z(𝖲)=\mathrm{max}\{u𝔖_n\mathrm{Des}(u)=𝖲\}`$.

First of all, the map $`\mathrm{Des}`$ is order preserving simply because $`p`$ is a descent of $`u`$ if and only if $`(p,p+1)\mathrm{Inv}(u)`$. This is (a). The remaining assertions follow immediately from

$`\zeta _𝖲`$ $`=\mathrm{max}\{u𝔖_n\mathrm{Des}(u)𝖲\}`$
$`=\mathrm{max}\{u𝔖_n\mathrm{Des}(u)=𝖲\},`$
which we know from Lemma 2.8.

Condition (2.7) follows formally. In fact, suppose $`𝖳=\mathrm{Des}(u)𝖲`$. Then by (d), $`uZ(𝖳)`$, and by (b), $`Z(𝖳)Z(𝖲)`$, so $`uZ(𝖲)`$. Conversely, suppose $`uZ(𝖲)`$. Then by (a) and (c), $`\mathrm{Des}(u)\mathrm{Des}(Z(𝖲))=𝖲`$. ∎

This Galois connection is why the monomial basis of $`𝔖\mathrm{𝑆𝑦𝑚}`$ is truly analogous to that of $`𝒬\mathrm{𝑆𝑦𝑚}`$, and explains why we consider the weak order rather than any other order on $`𝔖_n`$. The connection between the monomial bases of these two algebras will be elucidated in Theorem 7.3 using the previous result.

### 2.4. Global descents

###### Definition 2.12.

A permutation $`u𝔖_n`$ has a *global descent* at a position $`p[n1]`$ if

$$ip\text{ and }jp+1,u_i>u_j.$$

Equivalently, if $`\{u_1,\mathrm{},u_p\}=\{n,n1,\mathrm{},np+1\}`$. Let $`\mathrm{GDes}(u)[n1]`$ be the set of global descents of $`u`$. Note that $`\mathrm{GDes}(u)\mathrm{Des}(u)`$, but these are not equal in general.

In Section 2.3 we showed that the descent map $`\mathrm{Des}:𝔖_n𝒬_n`$ is left adjoint to the map $`Z:𝒬_n𝔖_n`$, in the sense that the pair $`(\mathrm{Des},Z)`$ forms a Galois connection, as in Proposition 2.11. That is, for $`u𝔖_n`$ and $`𝖲𝒬_n`$,

(2.8)
$$\mathrm{Des}(u)𝖲uZ(𝖲)=\zeta _𝖲.$$

The notion of global descents is a very natural companion of that of (ordinary) descents, in that the map $`\mathrm{GDes}:𝔖_n𝒬_n`$ is right adjoint to $`Z:𝒬_n𝔖_n`$.

###### Proposition 2.13.

The pair of maps $`(Z,\mathrm{GDes}):𝒬_n𝔖_n`$ is a Galois connection.

###### Proof.

We already know that $`Z`$ is order preserving. So is $`\mathrm{GDes}`$, because $`p`$ is a global descent of a permutation $`u`$ if and only if $`(i,j)\mathrm{Inv}(u)`$ for every $`ip`$, $`jp+1`$. It remains to check that

(2.9)
$$\zeta _𝖲u𝖲\mathrm{GDes}(u).$$

As in the proof of Proposition 2.11, this follows from

$`\zeta _𝖲`$ $`=\mathrm{min}\{u𝔖_n\mathrm{GDes}(u)𝖲\}`$
$`=\mathrm{min}\{u𝔖_n\mathrm{GDes}(u)=𝖲\},`$
which is clear from the definition of $`\zeta _𝖲`$. ∎

We turn to properties of the decomposition of $`𝔖_n`$ into left cosets of $`𝔖_𝖲`$ related to the notion of global descents. Recall that $`𝔖^{(p,q)}`$ is a set of representatives for the left cosets of $`𝔖_p\times 𝔖_q`$ in $`𝔖_{p+q}`$, and that $`\zeta _{p,q}=(q+1,q+2,\mathrm{},q+p,\mathrm{\hspace{0.17em}1},2,\mathrm{},q)`$.

###### Lemma 2.14.

Suppose $`p,q`$ are non-negative integers and let $`w𝔖_{p+q}`$. Then

$$p\mathrm{GDes}(w)w\zeta _{p,q}mod𝔖_p\times 𝔖_qw\zeta _{p,q}.$$

###### Proof.

First suppose that $`w𝔖_{p+q}`$ is in the same left coset of $`𝔖_p\times 𝔖_q`$ as is $`\zeta _{p,q}`$. Thus, there are permutations $`u𝔖_p`$ and $`v𝔖_q`$ such that

$$w=\zeta _{p,q}(u\times v).$$

If $`ip`$, then $`u_i\{1,\mathrm{},p\}`$ and thus $`w_i\{q+1,\mathrm{},q+p\}`$, so $`p`$ is a global descent of $`w`$ as needed.

For the other direction, suppose $`p`$ is a global descent of $`w`$ and set

$$\overline{w}:=\zeta _{p,q}^1w=(p+1,p+2,\mathrm{},p+q,1,2,\mathrm{},p)w.$$

Let $`1ip`$. By assumption, $`w_i\{q+1,\mathrm{},q+p\}`$. Hence $`\overline{w}_i\{1,\mathrm{},p\}`$, which means that $`\overline{w}=u\times v`$ for some $`u𝔖_p`$ and $`v𝔖_q`$, as needed.

Noting that $`\zeta _{p,q}`$ is a minimal coset representative and that the map $`\lambda ^1`$ is order preserving (Proposition 2.5(a)) proves the second equivalence. ∎

For any subset $`𝖲`$ of $`[n1]`$, we have the left coset map $`\lambda :𝔖^𝖲\times 𝔖_𝖲𝔖_n`$ of Section 2.2. Given a permutation $`u𝔖_n`$, consider its ‘projection’ $`u_𝖲`$ to $`𝔖_𝖲`$, which is defined to be the second component of $`\lambda ^1(u)`$. That is, $`\lambda ^1(u)=(\zeta ,u_𝖲)`$ for some permutation $`\zeta 𝔖^𝖲`$. If $`𝖲=\{p_1<p_2<\mathrm{}<p_k\}`$, then by Lemma 2.1,

(2.10)
$$u_𝖲=\mathrm{st}(u_1,\mathrm{},u_{p_1})\times \mathrm{st}(u_{p_1+1},\mathrm{},u_{p_2})\times \mathrm{}\times \mathrm{st}(u_{p_k+1},\mathrm{},u_n).$$

In particular, $`u_{\mathrm{}}=u`$ and $`u_{[n1]}=1_n`$. We relate this projection to the order and lattice structure of $`𝔖_n`$. For $`i<j`$, let $`[i,j):=\{i,i+1,\mathrm{},j1\}`$.

###### Lemma 2.15.

For any $`u𝔖_n`$ and subset $`𝖲`$ of $`[n1]`$,

$$\mathrm{Inv}(u_𝖲)=\{(i,j)\mathrm{Inv}(u)[i,j)𝖲=\mathrm{}\}.$$

In particular, $`u_𝖲u`$.

###### Proof.

Let $`i<j`$ be integers in $`[n]`$. Suppose that there is an element $`p𝖲`$ with $`ip<j`$. Since $`𝔖_𝖲𝔖_p\times 𝔖_{np}`$, we have $`u_𝖲𝔖_p\times 𝔖_{np}`$, and so $`u_𝖲(i)<u_𝖲(j)`$. Thus $`(i,j)\mathrm{Inv}(u_𝖲)`$. Suppose now that that $`[i,j)𝖲=\mathrm{}`$. Then there are consecutive elements $`p`$ and $`q`$ of $`𝖲`$ such that $`p<i<jq`$. By (2.10),

$$u_𝖲(i)=p+\mathrm{st}(u_{p+1},\mathrm{},u_q)(i)\text{ and }u_𝖲(j)=p+\mathrm{st}(u_{p+1},\mathrm{},u_q)(j).$$

By (1.2), this implies that

$$u_𝖲(i)>u_𝖲(j)u(i)>u(j),$$

and thus $`(i,j)\mathrm{Inv}(u_𝖲)(i,j)\mathrm{Inv}(u)`$. This completes the proof. ∎

###### Proposition 2.16.

Let $`u`$, $`v𝔖_n`$ and $`𝖲,𝖳`$ be subsets of $`[n1]`$. Then

1. If $`uv`$ then $`u_𝖲v_𝖲`$ and if $`𝖳𝖲`$ then $`u_𝖳u_𝖲`$.
2. $`u_𝖲v_𝖳=(uv)_{𝖲𝖳}`$,
3. If $`𝖲\mathrm{GDes}(v)`$ and $`𝖳\mathrm{GDes}(u)`$, then $`u_𝖲v_𝖳=(uv)_{𝖲𝖳}`$.

###### Proof.

The first statement is an immediate consequence of Lemma 2.15. For the second, we use (2.2) to show that $`\mathrm{Inv}(u_𝖲v_𝖳)=\mathrm{Inv}((uv)_{𝖲𝖳})`$.

First, suppose $`(i,j)\mathrm{Inv}((uv)_{𝖲𝖳})`$. Then by Lemma 2.15 and (2.2), we have $`[i,j)\left(𝖲𝖳\right)=\mathrm{}`$, and given a chain $`i=k_0<\mathrm{}<k_s=j`$, there is an index $`r`$ such that $`(k_{r1},k_r)\mathrm{Inv}(u)\mathrm{Inv}(v)`$. Hence we also have $`[k_{r1},k_r)\left(𝖲𝖳\right)=\mathrm{}`$, and thus $`(k_{r1},k_r)\mathrm{Inv}(u_𝖲)\mathrm{Inv}(v_𝖳)`$. Thus $`(i,j)\mathrm{Inv}(u_𝖲v_𝖳)`$.

We show the other inclusion. Let $`(i,j)\mathrm{Inv}(u_𝖲v_𝖳)`$. Considering the chain $`i<j`$, we must have $`(i,j)\mathrm{Inv}(u_𝖲)\mathrm{Inv}(v_𝖳)`$. In particular, $`[i,j)\left(𝖲𝖳\right)=\mathrm{}`$. On the other hand, for any chain $`i=k_0<\mathrm{}<k_s=j`$ there is an index $`r`$ such that $`(k_{r1},k_r)\mathrm{Inv}(u_𝖲)\mathrm{Inv}(v_𝖳)`$. Since this is a subset of $`\mathrm{Inv}(u)\mathrm{Inv}(v)`$, we have $`(i,j)\mathrm{Inv}(uv)`$. Together with $`[i,j)𝖲𝖳=\mathrm{}`$, we see that $`(i,j)\mathrm{Inv}((uv)_{𝖲𝖳})`$, proving the second statement.

For the third statement, first note that statement (i) implies that $`u_𝖲(uv)_𝖲(uv)_{𝖲𝖳}`$ and similarly $`v_𝖳(uv)_{𝖲𝖳}`$. Thus we have $`u_𝖲v_𝖳(uv)_{𝖲𝖳}`$. To show the other inequality, we need the assumptions on $`𝖲`$ and $`𝖳`$. With those assumptions, we show $`\mathrm{Inv}((uv)_{𝖲𝖳})\mathrm{Inv}(u_𝖲v_𝖳)`$.

Suppose that $`𝖲\mathrm{GDes}(v)`$ and $`𝖳\mathrm{GDes}(u)`$, so that $`𝖲`$ consists of global descents of $`v`$ and $`𝖳`$ consists of global descents of $`u`$. Let $`(i,j)\mathrm{Inv}((uv)_{𝖲𝖳})`$. Then, by Lemma 2.15 and (2.1), $`[i,j)𝖲𝖳=\mathrm{}`$ and there is a chain $`i=k_0<\mathrm{}<k_s=j`$ such that for every $`r`$, $`(k_{r1},k_r)\mathrm{Inv}(u)\mathrm{Inv}(v)`$. We refine this chain so that every pair of consecutive elements belongs to $`\mathrm{Inv}(u_𝖲)\mathrm{Inv}(v_𝖳)`$.

If $`[k_{r1},k_r)(𝖲𝖳)=\mathrm{}`$ then, by Lemma 2.15, $`(k_{r1},k_r)\mathrm{Inv}(u_𝖲)\mathrm{Inv}(v_𝖳)`$ and this interval need not be refined. If however the intersection is not empty, then choose any refinement

$$k_{r1}=k_0^{(r)}<k_1^{(r)}<\mathrm{}<k_{s_r}^{(r)}=k_r,$$

with the property that each interval $`[k_{t1}^{(r)},k_t^{(r)})`$ contains exactly one element of $`𝖲`$ or $`𝖳`$, but not an element of both. This is possible because $`[i,j)𝖲𝖳=\mathrm{}`$. We claim that each pair $`(k_{t1}^{(r)},k_t^{(r)})`$ is in $`\mathrm{Inv}(u_𝖲)\mathrm{Inv}(v_𝖳)`$. In fact, if $`[k_{t1}^{(r)},k_t^{(r)})`$ contains an element $`p𝖲`$, then that is a global descent of $`v`$, so $`(k_{t1}^{(r)},k_t^{(r)})\mathrm{Inv}(v)`$. Thus $`(k_{t1}^{(r)},k_t^{(r)})\mathrm{Inv}(v_𝖳)`$, since $`[k_{t1}^{(r)},k_t^{(r)})𝖳=\mathrm{}`$ by our construction of the refinement. Similarly, if $`[k_{t1}^{(r)},k_t^{(r)})`$ contains an element of $`𝖳`$, then $`(k_{t1}^{(r)},k_t^{(r)})\mathrm{Inv}(u_𝖲)`$. We have thus constructed a chain from $`i`$ to $`j`$ with the required property, which shows that $`(i,j)\mathrm{Inv}(u_𝖲v_𝖳)`$ and completes the proof. ∎

We calculate the descents and global descents of some particular permutations. The straightforward proof is left to the reader.

###### Lemma 2.17.

Let $`u𝔖_p`$ and $`v𝔖_q`$. Then

$`(\text{i})`$ $`\mathrm{Des}(u\times v)`$ $`=\mathrm{Des}(u)\left(p+\mathrm{Des}(v)\right),`$
$`(\text{i}i)`$ $`\mathrm{GDes}(u\times v)`$ $`=\mathrm{},`$
$`(\text{i}ii)`$ $`\mathrm{Des}\left(\zeta _{p,q}(u\times v)\right)`$ $`=\mathrm{Des}(u)\{p\}\left(p+\mathrm{Des}(v)\right),`$
$`(\text{i}v)`$ $`\mathrm{GDes}\left(\zeta _{p,q}(u\times v)\right)`$ $`=\mathrm{GDes}(u)\{p\}\left(p+\mathrm{GDes}(v)\right)`$
More generally, let $`u_{(i)}𝔖_{p_i}`$, $`i=1,\mathrm{},k`$, $`𝖲=\{p_1,p_1+p_2,\mathrm{},p_1+\mathrm{}+p_{k1}\}[n1]`$. Then

$`(\text{v})`$ $`\mathrm{Des}(u_{(1)}\times \mathrm{}\times u_{(k)})`$ $`={\displaystyle \underset{i=1}{\overset{k}{}}}\left(p_1+\mathrm{}+p_{i1}+\mathrm{Des}(u_{(i)})\right),`$
$`(\text{v}i)`$ $`\mathrm{GDes}(u_{(1)}\times \mathrm{}\times u_{(k)})`$ $`=\mathrm{},`$
$`(\text{v}ii)`$ $`\mathrm{Des}\left(\zeta _𝖲(u_{(1)}\times \mathrm{}\times u_{(k)})\right)`$ $`=𝖲{\displaystyle \underset{i=1}{\overset{k}{}}}\left(p_1+\mathrm{}+p_{i1}+\mathrm{Des}(u_{(i)})\right),`$
$`(\text{v}iii)`$ $`\mathrm{GDes}\left(\zeta _𝖲(u_{(1)}\times \mathrm{}\times u_{(k)})\right)`$ $`=𝖲{\displaystyle \underset{i=1}{\overset{k}{}}}\left(p_1+\mathrm{}+p_{i1}+\mathrm{GDes}(u_{(i)})\right).`$
###### Lemma 2.18.

Let $`u𝔖_n`$ and $`𝖲[n1]`$. Then

$$𝖲\mathrm{GDes}(u)u=\zeta _𝖲u_𝖲.$$

###### Proof.

The reverse implication follows from Lemma 2.17 (viii). The other follows by induction from Lemma 2.14 and (2.6). ∎

## 3. The coproduct of $`𝔖\mathrm{𝑆𝑦𝑚}`$

The coproduct of $`𝔖\mathrm{𝑆𝑦𝑚}`$ (1.3) takes a simple form on the monomial basis. We derive this formula using some results of Section 2. For a permutation $`u𝔖_n`$, define $`\overline{\mathrm{GDes}}(u)`$ to be $`\mathrm{GDes}(u)\{0,n\}`$.

###### Theorem 3.1.

Let $`u𝔖_n`$. Then

(3.1)
$$\mathrm{\Delta }(_u)=\underset{p\overline{\mathrm{GDes}}(u)}{}_{\mathrm{st}(u_1,\mathrm{},u_p)}\text{ }_{\mathrm{st}(u_{p+1},\mathrm{},u_n)}.$$

###### Proof.

Let $`\mathrm{\Delta }^{}:𝔖\mathrm{𝑆𝑦𝑚}𝔖\mathrm{𝑆𝑦𝑚}\text{ }𝔖\mathrm{𝑆𝑦𝑚}`$ be the map whose action on the monomial basis is defined by the sum (3.1). We show that $`\mathrm{\Delta }^{}`$ is the coproduct $`\mathrm{\Delta }`$, as defined by (1.3). We use the following notation. For $`w𝔖_n`$ and $`0pn`$, let $`w_{(1)}^p:=\mathrm{st}(w_1,\mathrm{},w_p)`$ and $`w_{(2)}^p:=\mathrm{st}(w_{p+1},\mathrm{},w_n)`$. By virtue of Lemmas 2.1 and 2.14, we have

$$v=\zeta _{p,np}(v_{(1)}^p\times v_{(2)}^p)p\overline{\mathrm{GDes}}(v).$$

Therefore,

$`\mathrm{\Delta }^{}(_u)`$ $`={\displaystyle \underset{uv}{}}\mathrm{\Delta }^{}(_v)={\displaystyle \underset{uv}{}}{\displaystyle \underset{p\overline{\mathrm{GDes}}(v)}{}}_{v_{(1)}^p}\text{ }_{v_{(2)}^p}`$
$`={\displaystyle \underset{p=0}{\overset{n}{}}}{\displaystyle \underset{\begin{array}{c}uv\\ v=\zeta _{p,np}(v_{(1)}^p\times v_{(2)}^p)\text{}\end{array}}{}}_{v_{(1)}^p}\text{ }_{v_{(2)}^p}={\displaystyle \underset{p=0}{\overset{n}{}}}{\displaystyle \underset{\begin{array}{c}v_1,v_2\\ u\zeta _{p,np}(v_1\times v_2)\text{}\end{array}}{}}_{v_1}\text{ }_{v_2}.`$
Write $`u=\zeta (u_{(1)}^p\times u_{(2)}^p)`$ for some $`\zeta 𝔖^{(p,np)}`$ which depends on $`p`$. By Proposition 2.5,

$$\zeta (u_{(1)}^p\times u_{(2)}^p)\zeta _{p,np}(v_1\times v_2)u_{(1)}^pv_1\text{ and }u_{(2)}^pv_2.$$

Therefore,

$`\mathrm{\Delta }^{}(_u)`$ $`={\displaystyle \underset{p=0}{\overset{n}{}}}{\displaystyle \underset{\begin{array}{c}v_1,v_2\\ u_{(1)}^pv_1,u_{(2)}^pv_2\end{array}}{}}_{v_1}\text{ }_{v_2}={\displaystyle \underset{p=0}{\overset{n}{}}}{\displaystyle \underset{u_{(1)}^pv_1}{}}_{v_1}{\displaystyle \underset{u_{(2)}^pv_2}{}}_{v_2}`$
$`={\displaystyle \underset{p=0}{\overset{n}{}}}_{u_{(1)}^p}\text{ }_{u_{(2)}^p}=\mathrm{\Delta }(_u).`$
###### Remark 3.2.

The action of the coproduct of $`𝔖\mathrm{𝑆𝑦𝑚}`$ on the fundamental basis can also be expressed in terms of the weak order. To see this, let $`u𝔖_n`$ and $`0pn`$ and write $`u=\zeta (u_{(1)}^p\times u_{(2)}^p)`$. By Proposition 2.5, $`u_{(1)}^p\times u_{(2)}^pu\zeta _{p,np}(u_{(1)}^p\times u_{(2)}^p)`$. Moreover, $`u_{(1)}^p`$ and $`u_{(2)}^p`$ are the only permutations in $`𝔖_p`$ and $`𝔖_{np}`$ with this property, again by Proposition 2.5. Therefore, equation (1.3) is also described by $`\mathrm{\Delta }(_u)=_v\text{ }_w`$, where the sum is over all $`p`$ from 0 to $`n`$ and all permutations $`v𝔖_p`$ and $`w𝔖_{np}`$ such that $`v\times wu\zeta _{p,np}(v\times w)`$. This fact (in its dual form) is due to Loday and Ronco \[20, Theorem 4.1\], who were the first to point out the relevance of the weak order to the Hopf algebra structure of $`𝔖\mathrm{𝑆𝑦𝑚}`$.

## 4. The product of $`𝔖\mathrm{𝑆𝑦𝑚}`$

We give an explicit formula for the product of $`𝔖\mathrm{𝑆𝑦𝑚}`$ in terms of its monomial basis and a geometric interpretation for the structure constants. Remarkably, these are still non-negative integers. For instance,

(4.1)
$$\begin{array}{c}_{12}_{21}=_{4312}+_{4231}+_{3421}+_{4123}+_{2341}\hfill \\ \hfill +_{1243}+_{1423}+_{1342}+3_{1432}+2_{2431}+2_{4132}.\end{array}$$

The structure constants count special ways of shuffling two permutations, according to certain conditions involving the weak order. Specifically, for $`u𝔖_p`$, $`v𝔖_q`$ and $`w𝔖_{p+q}`$, define $`A_{u,v}^w𝔖^{(p,q)}`$ to be those $`\zeta 𝔖^{(p,q)}`$ satisfying

(4.2)
$$\begin{array}{cc}(i)\hfill & (u\times v)\zeta ^1w,\text{ and}\hfill \\ (ii)\hfill & \text{if }uu^{}\text{ and }vv^{}\text{ satisfy }(u^{}\times v^{})\zeta ^1w\text{,}\hfill \\ & \text{then }u=u^{}\text{ and }v=v^{}\text{.}\hfill \end{array}$$

Set $`\alpha _{u,v}^w:=\mathrm{\#}A_{u,v}^w`$. We will prove the following theorem.

###### Theorem 4.1.

For any $`u𝔖_p`$ and $`v𝔖_q`$, we have

(4.3)
$$_u_v=\underset{w𝔖_{p+q}}{}\alpha _{u,v}^w_w.$$

For instance, in (4.1) the coefficient of $`_{2431}`$ in $`_{12}_{21}`$ is 2 because among the six permutations in $`𝔖^{(2,2)}`$,

$$1234,1324,1423,2314,2413,3412,$$

only the first two satisfy conditions $`(i)`$ and $`(ii)`$ of (4.2). In fact, $`2314`$, $`2413`$ and $`3412`$ do not satisfy $`(i)`$, while $`1423`$ satisfies $`(i)`$ but not $`(ii)`$.

The structure constants $`\alpha _{u,v}^w`$ admit a geometric-combinatorial description in terms of the permutahedron. To derive it, recall the convex embeddings of Proposition 2.7.

$$\rho _\zeta :𝔖_p\times 𝔖_q𝔖_{p+q},\rho _\zeta (u,v):=(u\times v)\zeta ^1.$$

Since $`\rho _\zeta `$ preserves joins, we may further rewrite the definition (4.2) of $`A_{u,v}^w`$ as

(4.4)
$$A_{u,v}^w=\{\zeta 𝔖^{(p,q)}(u,v)=\mathrm{max}\rho _\zeta ^1[1,w]\},$$

where $`[w,w^{}]:=\{w^{\prime \prime }ww^{\prime \prime }w^{}\}`$ denotes the interval between $`w`$ and $`w^{}`$.

The vertices of the $`(n1)`$-dimensional permutahedron can be indexed by the elements of $`𝔖_n`$ so that its 1-skeleton is the Hasse diagram of the weak order (see Figure 1). Facets of the permutahedron are products of two lower dimensional permutahedra, and the image of $`\rho _\zeta `$ is the set of vertices in a facet. Moreover, every facet arises in this way for a unique triple $`(p,q,\zeta )`$ with $`p+q=n`$ and $`\zeta 𝔖^{(p,q)}`$; see \[24, Lemma 4.2\], or \[4, Exer. 2.9\], or \[18, Prop. A.1\]. Let us say that such a facet has type $`(p,q)`$. Figure 3 displays the image of $`\rho _{1324}`$, a facet of the $`3`$-permutahedron of type $`(2,2)`$, and the permutation $`2431`$.

The description (4.4) of $`A_{u,v}^w`$ (and hence of $`\alpha _{u,v}^w`$) can be interpreted as follows: Given $`u𝔖_p`$, $`v𝔖_q`$, and $`w𝔖_{p+q}`$, the structure constant $`\alpha _{u,v}^w`$ counts the number of facets of type $`(p,q)`$ of the $`(p+q1)`$-permutahedron such that the vertex $`\rho _\zeta (u,v)`$ is below $`w`$ and it is the maximum vertex in that facet below $`w`$.

For instance, the facet $`\rho _{1324}`$ contributes to the structure constant $`\alpha _{12,21}^{2431}`$ because the vertex $`\rho _{1324}(12,21)=1423`$ satisfies the required properties in relation to the vertex $`w=2431`$, as shown in Figure 3.

This description of the product of $`𝔖\mathrm{𝑆𝑦𝑚}`$ has an analog for $`𝒬\mathrm{𝑆𝑦𝑚}`$ that we present in Section 7.

###### Proof of Theorem 4.1.

Expand the product $`_u_v`$ in the fundamental basis and then use Formula (1.1) to obtain

$`_u_v`$ $`={\displaystyle \underset{\begin{array}{c}uu^{}\\ vv^{}\end{array}}{}}\mu (u,u^{})\mu (v,v^{})_u^{}_v^{}`$
$`={\displaystyle \underset{\zeta 𝔖^{(p,q)}}{}}{\displaystyle \underset{\begin{array}{c}uu^{}\\ vv^{}\end{array}}{}}\mu (u,u^{})\mu (v,v^{})_{(u^{}\times v^{})\zeta ^1}.`$
Expressing this result in terms of the monomial basis and collecting like terms gives

$`_u_v`$ $`={\displaystyle \underset{\zeta 𝔖^{(p,q)}}{}}{\displaystyle \underset{\begin{array}{c}uu^{},vv^{}\\ (u^{}\times v^{})\zeta ^1w\end{array}}{}}\mu (u,u^{})\mu (v,v^{})_w`$
$`={\displaystyle \underset{w}{}}{\displaystyle \underset{\begin{array}{c}uu^{}\\ vv^{}\end{array}}{}}\mu (u,u^{})\mu (v,v^{})\beta _{u^{},v^{}}^w_w,`$
where $`\beta _{u^{},v^{}}^w`$ is the number of permutations in the set

$$B_{u^{},v^{}}^w:=\{\zeta 𝔖^{(p,q)}(u^{}\times v^{})\zeta ^1w\}.$$

The theorem will follow once we show that

$$\alpha _{u,v}^w=\underset{uu^{},vv^{}}{}\mu (u,u^{})\mu (v,v^{})\beta _{u^{},v^{}}^w,$$

or equivalently, by Möbius inversion on $`𝔖_p\times 𝔖_q`$,

$$\beta _{u,v}^w=\underset{uu^{},vv^{}}{}\alpha _{u^{},v^{}}^w.$$

We prove this last equality by showing that

$$B_{u,v}^w=\underset{uu^{},vv^{}}{}A_{u^{},v^{}}^w,$$

where the union is disjoint.

To see this, first suppose $`\zeta A_{u,v}^wA_{u^{},v^{}}^w`$. Then, by condition $`(i)`$ of (4.2),

$$(u\times v)\zeta ^1w\text{ and }(u^{}\times v^{})\zeta ^1w.$$

By Proposition 2.7.(d),

$$\left((uu^{})\times (vv^{})\right)\zeta ^1w.$$

But then, by condition $`(ii)`$ of (4.2),

$$u=uu^{}=u^{}\text{ and }v=vv^{}=v^{},$$

so the union is disjoint.

Next, suppose that $`\zeta A_{u^{},v^{}}^w`$ for some $`uu^{}`$ and $`vv^{}`$. Then, by condition $`(i)`$ of (4.2), $`(u^{}\times v^{})\zeta ^1w`$. By Proposition 2.7.(c) we have, $`(u\times v)\zeta ^1w`$, so $`\zeta B_{u,v}^w`$. This proves one inclusion.

For the other inclusion, suppose that $`\zeta B_{u,v}^w`$. Define

$$(\overline{u},\overline{v}):=\{(u^{},v^{})uu^{},vv^{},\text{ and }(u^{}\times v^{})\zeta ^1w\}.$$

Then $`\zeta A_{\overline{u},\overline{v}}^w`$: condition $`(i)`$ is satisfied because $`\rho _\zeta `$ preserves joins, and $`(ii)`$ simply by definition. This completes the proof. ∎

## 5. The antipode of $`𝔖\mathrm{𝑆𝑦𝑚}`$

Malvenuto left open the problem of an explicit formula for the antipode of $`𝔖\mathrm{𝑆𝑦𝑚}`$ \[22, pp. 59–60\]. We solve that problem, giving formulas that identify the coefficients of the antipode in terms of both the fundamental and monomial basis in explicit combinatorial terms.

We first review a general formula for the antipode of a connected Hopf algebra $`H`$, due to Takeuchi \[35, Lemma 14\] (see also Milnor and Moore ). Let $`H`$ be an arbitrary bialgebra with structure maps: multiplication $`m:H\text{ }HH`$, unit $`u:H`$, comultiplication $`\mathrm{\Delta }:HH\text{ }H`$, and counit $`ϵ:H`$. Set $`m^{(1)}=m`$, $`\mathrm{\Delta }^{(1)}=\mathrm{\Delta }`$, and for any $`k2`$,

$`m^{(k)}`$ $`=m(m^{(k1)}\text{ }\mathrm{𝑖𝑑}):H^{\text{ }k+1}H,\text{ and}`$
$`\mathrm{\Delta }^{(k)}`$ $`=(\mathrm{\Delta }^{(k1)}\text{ }\mathrm{𝑖𝑑})\mathrm{\Delta }:HH^{\text{ }k+1}.`$
These are the higher or iterated products and coproducts. We also set

$`m^{(1)}`$ $`=u:H,`$
$`\mathrm{\Delta }^{(1)}`$ $`=ϵ:H,\text{ and}`$
$`m^{(0)}`$ $`=\mathrm{\Delta }^{(0)}=\mathrm{𝑖𝑑}:HH.`$
If $`f:HH`$ is any linear map, the convolution powers of $`f`$ are, for any $`k0`$,

$$f^k=m^{(k1)}f^{\text{ }k}\mathrm{\Delta }^{(k1)}.$$

In particular, $`f^0=uϵ`$ and $`f^1=f`$.

We set $`\pi :=iduϵ`$. If $`\pi `$ is locally nilpotent with respect to convolution, then $`id=uϵ+\pi `$ is invertible with respect to convolution, with inverse

(5.1)
$$S=\underset{k0}{}(\pi )^k=\underset{k0}{}(1)^km^{(k1)}\pi ^{\text{ }k}\mathrm{\Delta }^{(k1)}.$$

This is certainly the case if $`H`$ is a graded connected bialgebra, in which case $`\pi `$ annihilates the component of degree $`0`$ (and hence $`\pi ^k`$ annihilates components of degree $`<k`$). Thus (5.1) is a general formula for the antipode of a graded connected Hopf algebra.

We will make use of this formula to find explicit formulas for the antipode of $`𝔖\mathrm{𝑆𝑦𝑚}`$. The first task is to describe the higher products and coproducts explicitly. We begin with the higher coproducts in terms of the fundamental and monomial bases.

###### Proposition 5.1.

Let $`v𝔖_n`$, $`n0`$, and $`k1`$. Then

* $`\mathrm{\Delta }^{(k)}(_v)={\displaystyle \underset{0p_1\mathrm{}p_kn}{}}_{\mathrm{st}(v_1,\mathrm{},v_{p_1})}\text{ }\mathrm{}\text{ }_{\mathrm{st}(v_{p_k+1},\mathrm{},v_n)}`$, and
* $`\mathrm{\Delta }^{(k)}(_v)={\displaystyle \underset{\begin{array}{c}0p_1\mathrm{}p_kn\\ p_i\overline{\mathrm{GDes}}(v)\text{}\end{array}}{}}_{\mathrm{st}(v_1,\mathrm{},v_{p_1})}\text{ }\mathrm{}\text{ }_{\mathrm{st}(v_{p_k+1},\mathrm{},v_n)}`$.

###### Proof.

Both formulas follow by induction from the corresponding descriptions of the coproduct, equations (1.3) and (3.1). ∎

We describe higher products in terms of minimal coset representatives $`𝔖^𝖲`$ of parabolic subgroups, whose basic properties were discussed in Section 2.2. Recall that for a subset $`𝖲=\{p_1<p_2<\mathrm{}<p_k\}`$ of $`[n1]`$, we have $`𝔖^𝖲=\{\zeta 𝔖_n\mathrm{Des}(\zeta )𝖲\}`$. Analogously to (4.2), given permutations $`v_{(1)}𝔖_{p_1}`$, $`v_{(2)}𝔖_{p_2p_1}`$, …, $`v_{(k+1)}𝔖_{np_k}`$, define $`A_{v_{(1)},v_{(2)},\mathrm{},v_{(k+1)}}^w𝔖^𝖲`$ to be those $`\zeta 𝔖^𝖲`$ satisfying

(5.2)
$$\begin{array}{cc}(i)\hfill & \left(v_{(1)}\times v_{(2)}\times \mathrm{}\times v_{(k+1)}\right)\zeta ^1w,\text{ and}\hfill \\ (ii)\hfill & \text{if }v_{(i)}v_{(i)}^{}i\text{ and }\text{}\left(v_{(1)}^{}\times v_{(2)}^{}\times \mathrm{}\times v_{(k+1)}^{}\right)\zeta ^1w,\hfill \\ & \text{then }v_{(i)}=v_{(i)}^{},i\text{ .}\hfill \end{array}$$

Set $`\alpha _{v_{(1)},v_{(2)},\mathrm{},v_{(k+1)}}^w:=\mathrm{\#}A_{v_{(1)},v_{(2)},\mathrm{},v_{(k+1)}}^w`$.

###### Proposition 5.2.

Let $`𝖲`$ and $`v_{(1)},\mathrm{},v_{(k+1)}`$ be as in the preceding paragraph. Then

* $`_{v_{(1)}}_{v_{(2)}}\mathrm{}_{v_{(k+1)}}={\displaystyle \underset{\zeta 𝔖^𝖲}{}}_{(v_{(1)}\times v_{(2)}\times \mathrm{}\times v_{(k+1)})\zeta ^1}`$ and
* $`_{v_{(1)}}_{v_{(2)}}\mathrm{}_{v_{(k+1)}}={\displaystyle \underset{w𝔖_n}{}}\alpha _{v_{(1)},v_{(2)},\mathrm{},v_{(k+1)}}^w_w`$,

###### Proof.

The first formula follows immediately by induction from (1.1) (the case $`k=2`$), using (2.5). The second formula can be deduced from (i) in the same way as in the proof of Theorem 4.1. ∎

The structure constants for the iterated product admit a geometric description similar to that of the product. The image of the map

$$\rho _\zeta :𝔖_𝖲𝔖_n,(v_{(1)}\times \mathrm{}\times v_{(k+1)})(v_{(1)}\times \mathrm{}\times v_{(k+1)})\zeta ^1,$$

consists of the vertices of a face of codimension $`k`$ in the $`(n1)`$-permutahedron, and every such face arises in this way for a unique pair $`(𝖲,\zeta )`$ with $`𝖲[n1]`$ having $`k`$ elements and $`\zeta 𝔖^𝖲`$. Let us say that such a face has *type* $`𝖲`$. The structure constant $`\alpha _{v_{(1)},\mathrm{},v_{(k+1)}}^w`$ counts the number of faces of type $`𝖲`$ with the property that the vertex $`\rho _\zeta (v_{(1)},\mathrm{},v_{(k+1)})`$ is below $`w`$ and it is the maximum vertex in its face below $`w`$.

We next determine the convolution powers of the projection $`\pi =iduϵ`$. Recall that for any subset $`𝖲=\{p_1<p_2<\mathrm{}<p_k\}[n1]`$ and $`v𝔖_n`$ we have

$$v_𝖲:=\mathrm{st}(v_1,\mathrm{},v_{p_1})\times \mathrm{st}(v_{p_1+1},\mathrm{},v_{p_2})\times \mathrm{}\times \mathrm{st}(v_{p_k+1},\mathrm{},v_n)𝔖_n,$$

as given by (2.10). We slightly amend our notation in order to simplify some subsequent statements. For $`v,w𝔖_n`$ and $`𝖲[n1]`$, set $`A_𝖲(v,w):=A_{v_{(1)},\mathrm{},v_{(k+1)}}^w`$, where $`v_{(1)},\mathrm{},v_{(k+1)}`$ are the factors of $`v_𝖲`$ in the definition above. Comparing with (5.2), we see that $`A_𝖲(v,w)𝔖^𝖲`$ consists of those $`\zeta 𝔖^𝖲`$ satisfying

(5.3)
$$\begin{array}{cc}(i)\hfill & v_𝖲\zeta ^1w,\text{ and}\hfill \\ \text{}(ii)\hfill & \text{if }vv^{}\text{ and }v_𝖲^{}\zeta ^1w\text{ then }v=v^{}\hfill \end{array}$$

Similarly, we define $`\alpha _𝖲(v,w):=\mathrm{\#}A_𝖲(v,w)`$. If $`v_{(1)},\mathrm{},v_{(k+1)}`$ are the factors in the definition of $`v_𝖲`$, then

(5.4)
$$\alpha _𝖲(v,w)=\alpha _{v_{(1)},\mathrm{},v_{(k+1)}}^w.$$

Let $`\left(\genfrac{}{}{0pt}{}{[n1]}{k1}\right)`$ be the collection of subsets of $`[n1]`$ of size $`k1`$.

###### Proposition 5.3.

Let $`n,k1`$ and $`v𝔖_n`$. Then

* $`\pi ^k(_v)={\displaystyle \underset{w𝔖_n}{}}{\displaystyle \underset{\begin{array}{c}𝖲\left(\genfrac{}{}{0pt}{}{[n1]}{k1}\right)\\ \mathrm{Des}(w^1v_𝖲)𝖲\end{array}}{}}_w`$, and
* $`\pi ^k(_v)={\displaystyle \underset{w𝔖_n}{}}{\displaystyle \underset{\begin{array}{c}𝖲\left(\genfrac{}{}{0pt}{}{\mathrm{GDes}(v)}{k1}\right)\end{array}}{}}\alpha _𝖲(v,w)_w`$.

###### Proof.

By Proposition 5.1(i),

$$\mathrm{\Delta }^{(k1)}(_v)=\underset{0p_1\mathrm{}p_{k1}n}{}_{\mathrm{st}(v_1,\mathrm{},v_{p_1})}\text{ }_{\mathrm{st}(v_{p_1+1},\mathrm{},v_{p_2})}\text{ }\mathrm{}\text{ }_{\mathrm{st}(v_{p_{k1}+1},\mathrm{},v_n)}.$$

Suppose that an equality $`p_i=p_{i+1}`$ occurs (where we define $`p_0=0`$ and $`p_k=n`$). The corresponding permutation $`\mathrm{st}(v_{p_i+1},\mathrm{},v_{p_{i+1}})`$ is then simply the unique permutation in $`𝔖_0`$, which indexes the element $`1\mathrm{ker}(\pi )`$. Therefore,

$`\pi ^k(_v)`$ $`=m^{(k1)}\pi ^{\text{ }k}\mathrm{\Delta }^{(k1)}(_v)`$
$`={\displaystyle \underset{0<p_1<p_2<\mathrm{}<p_{k1}<n}{}}_{\mathrm{st}(v_1,\mathrm{},v_{p_1})}_{\mathrm{st}(v_{p_1+1},\mathrm{},v_{p_2})}\mathrm{}_{\mathrm{st}(v_{p_{k1}+1},\mathrm{},v_n)}`$
$`={\displaystyle \underset{0<p_1<p_2<\mathrm{}<p_{k1}<n}{}}{\displaystyle \underset{\zeta 𝔖^{\{p_1,p_2,\mathrm{},p_{k1}\}}}{}}_{(\mathrm{st}(u_1,\mathrm{},u_{p_1})\times \mathrm{}\times \mathrm{st}(u_{p_{k1}+1},\mathrm{},u_n))\zeta ^1},`$
the last equality by the formula of Proposition 5.2(i) for the iterated product. Changing the index of summation in the first sum to $`𝖲\left(\genfrac{}{}{0pt}{}{[n1]}{k1}\right)`$ and using the definition of $`v_𝖲`$ gives

$$\pi ^k(_v)=\underset{𝖲\left(\genfrac{}{}{0pt}{}{[n1]}{k1}\right)}{}\underset{\zeta 𝔖^𝖲}{}_{v_𝖲\zeta ^1}.$$

Again reindexing the sum and using that $`𝔖^𝖲`$ consists of permutations whose descent set is a subset of $`𝖲`$, we obtain

$$\pi ^k(_v)=\underset{w𝔖_n}{}\underset{\begin{array}{c}𝖲\left(\genfrac{}{}{0pt}{}{[n1]}{k1}\right)\\ w^1v_𝖲𝔖^𝖲\end{array}}{}_w=\underset{w𝔖_n}{}\underset{\begin{array}{c}𝖲\left(\genfrac{}{}{0pt}{}{[n1]}{k1}\right)\\ \mathrm{Des}(w^1v_𝖲)𝖲\end{array}}{}_w,$$

establishing (i).

The second formula in terms of the monomial basis follows in exactly the same manner from Propositions 5.1(ii) and 5.2(ii) for the higher coproducts and products in terms of the monomial basis, using (5.4). ∎

We derive explicit formulas for the antipode on both bases. The formula for the fundamental basis is immediate from Proposition 5.3(i) and (5.1).

###### Theorem 5.4.

For $`v,w𝔖_n`$ set

$`\lambda (v,w):=`$ $`\mathrm{\#}\{𝖲[n1]\mathrm{Des}(w^1v_𝖲)𝖲\text{ and }\mathrm{\#}𝖲\text{ is odd}\}`$
$`\mathrm{\#}\{𝖲[n1]\mathrm{Des}(w^1v_𝖲)𝖲\text{ and }\mathrm{\#}𝖲\text{ is even}\}.`$
Then

(5.5)
$$S(_v)=\underset{w𝔖_n}{}\lambda (v,w)_w.$$

The coefficients of the antipode on the fundamental basis may indeed be positive or negative. For instance

$$S(_{231})=_{132}_{213}2_{231}+_{312}.$$

The coefficient of $`_{312}`$ is $`1`$ because $`\{1\}`$, $`\{2\}`$, and $`\{1,2\}`$ are the subsets $`𝖲`$ of $`\{1,2\}`$ which satisfy $`\mathrm{Des}\left((312)^1(231)_𝖲\right)𝖲`$.

Our description of these coefficients is semi-combinatorial, in the sense that it involves a difference of cardinalities of sets. On the monomial basis the situation is different. The sign of the coefficients of $`S(_v)`$ only depends on the number of global descents of $`v`$. We provide a fully combinatorial description of these coefficients. Let $`v,w𝔖_n`$ and suppose $`𝖲\mathrm{GDes}(v)`$. Define $`C_𝖲(v,w)𝔖^𝖲`$ to be those $`\zeta 𝔖^𝖲`$ satisfying

(5.6)
$$\begin{array}{cc}\hfill (i)& v_𝖲\zeta ^1w\text{,}\hfill \\ \hfill (ii)& \text{if }vv^{}\text{ and }v_𝖲^{}\zeta ^1w\text{ then }v=v^{}\text{,  and}\hfill \\ \hfill (iii)& \text{if }\mathrm{Des}(\zeta )𝖱𝖲\text{ and }v_𝖱\zeta ^1w\text{ then }𝖱=𝖲\text{.}\hfill \end{array}$$

Set $`\kappa (v,w):=\mathrm{\#}C_{\mathrm{GDes}(v)}(v,w)`$.

###### Theorem 5.5.

For $`v,w𝔖_n`$, we have

(5.7)
$$S(_v)=(1)^{\mathrm{\#}\mathrm{GDes}(v)+1}\underset{w𝔖_n}{}\kappa (v,w)_w.$$

For instance,

$$\begin{array}{c}S(_{3412})=_{1234}+2_{1324}+_{1342}+_{1423}\hfill \\ \hfill +_{2314}+_{2413}+_{3124}+_{3142}+_{3412}.\end{array}$$

Consider the coefficient of $`_{3412}`$. In this case, $`𝖲=\mathrm{GDes}(3412)=\{2\}`$, so

$$𝔖^𝖲=\{1234,1324,1423,2314,2413,3412\}.$$

Then $`1234`$ satisfies ($`i`$) and ($`ii`$) of (5.6) but not ($`iii`$), 1324 satisfies ($`i`$) and ($`iii`$) but not ($`ii`$), 1423, 2314 and 2413 do not satisfy ($`i`$), and 3412 is the only element of $`𝔖^{\{2\}}`$ that satisfies all three conditions of (5.6). Therefore $`C_𝖲(3412,3412)=\{3412\}`$ and the coefficient is $`\kappa (3412,3412)=1`$.

###### Remark 5.6.

The antipode of $`𝔖\mathrm{𝑆𝑦𝑚}`$ has infinite order. In fact, one may verify by induction that

$$S^{2m}(_{231})=_{231}+2m(_{213}_{132})m.$$

###### Proof of Theorem 5.5.

By formula (5.1) and Proposition 5.3(ii), we have

$$S(_v)=\underset{w𝔖_n}{}\underset{𝖲\mathrm{GDes}(v)}{}(1)^{\mathrm{\#}𝖲+1}\alpha _𝖲(v,w)_w.$$

For any $`𝖳\mathrm{GDes}(v)`$, define

(5.8)
$$\gamma _𝖳(v,w):=\underset{𝖲𝖳}{}(1)^{\mathrm{\#}𝖳𝖲}\alpha _𝖲(v,w)=\underset{𝖲𝖳}{}\mu (𝖲,𝖳)\alpha _𝖲(v,w),$$

where $`\mu (,)`$ is the Möbius function of the Boolean poset $`𝒬_n`$. We then have

$$S(_v)=(1)^{\mathrm{\#}\mathrm{GDes}(u)+1}\underset{w𝔖_n}{}\gamma _{\mathrm{GDes}(v)}(v,w)_w.$$

We complete the proof by showing that $`\kappa (v,w)=\gamma _{\mathrm{GDes}(v)}(v,w)`$, and more generally that $`\gamma _𝖲(v,w)=\mathrm{\#}C_𝖲(v,w)`$, where $`C_𝖲(v,w)`$ is defined in (5.6).

Möbius inversion using the definition (5.8) of $`\gamma _𝖳(v,w)`$ gives

$$\alpha _𝖳(v,w)=\underset{𝖲𝖳}{}\gamma _𝖲(v,w).$$

We prove this last equality by showing that

(5.9)
$$A_𝖳(v,w)=\underset{𝖲𝖳}{}C_𝖲(v,w),$$

where the union is disjoint. This implies that $`\gamma _𝖲(v,w)=\mathrm{\#}C_𝖲(v,w)`$, which will complete the proof. We argue that this is a disjoint union in several steps.

Claim 1: If $`𝖲𝖳\mathrm{GDes}(v)`$ then $`A_𝖲(v,w)A_𝖳(v,w)`$.

Let $`\zeta A_𝖲(v,w)`$. First of all, $`\zeta 𝔖^𝖲𝔖^𝖳`$, as $`𝔖^𝖲`$ is the set of permutations with descent set a subset of $`𝖲`$. By condition ($`i`$) of (5.6), $`v_𝖲\zeta ^1w`$. On the other hand, Proposition 2.16(i) implies that $`u_𝖳u_𝖲`$ and both permutations are elements of the parabolic subgroup $`𝔖_𝖲`$. Hence by Proposition 2.10, $`u_𝖳\zeta ^1u_𝖲\zeta ^1`$. Thus $`u_𝖳\zeta ^1w`$, which establishes condition ($`i`$) of (5.6) for $`\zeta `$ to be in $`A_𝖳(v,w)`$.

Now suppose that $`vv^{}`$ with $`v_𝖳^{}\zeta ^1w`$. Since $`v_𝖲\zeta ^1w`$, we deduce that

$$w(v_𝖲\zeta ^1)(v_𝖳^{}\zeta ^1)=(v_𝖲v_𝖳^{})\zeta ^1=(vv^{})_{𝖲𝖳}\zeta ^1=v_𝖲\zeta ^1.$$

The first equality is because $`\rho _\zeta `$ is a convex embedding and hence preserves joins by Proposition 2.10, and the second follows from Proposition 2.16(iii) as $`𝖲,𝖳\mathrm{GDes}(v)\mathrm{GDes}(v^{})`$. Hence, by condition ($`ii`$) for $`A_𝖲(v,w)`$, we have $`v=v^{}`$. This establishes ($`ii`$) for $`\zeta `$ to be in $`A_𝖳(v,w)`$ and completes the proof of Claim 1.

Claim 2: If $`𝖲,𝖳\mathrm{GDes}(v)`$, then $`A_𝖲(v,w)A_𝖳(v,w)=A_{𝖲𝖳}(v,w)`$.

The inclusion $`A_{𝖲𝖳}(v,w)A_𝖲(v,w)A_𝖳(v,w)`$ is a consequence of Claim 1. To prove the converse, let $`\zeta A_𝖲(v,w)A_𝖳(v,w)`$. Note that $`\zeta 𝔖^𝖲𝔖^𝖳`$, which equals $`𝔖^{𝖲𝖳}`$.

By condition ($`i`$) for $`\zeta A_𝖲(v,w)`$ and for $`\zeta A_𝖳(v,w)`$, we have $`v_𝖲\zeta ^1w`$ and $`v_𝖳\zeta ^1w`$. Therefore,

$$w(v_𝖲\zeta ^1)(v_𝖳\zeta ^1)=(v_𝖲v_𝖳)\zeta ^1=v_{𝖲𝖳}\zeta ^1.$$

As before, this uses Proposition 2.16(iii), which applies as $`𝖲,𝖳\mathrm{GDes}(u)`$. This proves condition ($`i`$) of (5.6) for $`\zeta `$ to be in $`A_{𝖲𝖳}(v,w)`$.

Now suppose that $`vv^{}`$ with $`v_{𝖲𝖳}^{}\zeta ^1w`$. By Proposition 2.16(i), $`v_𝖲^{}v_{𝖲𝖳}^{}`$. Then by Proposition 2.10, $`v_𝖲^{}\zeta ^1v_{𝖲𝖳}^{}\zeta ^1`$. Thus $`v_𝖲^{}\zeta ^1w`$ and by condition ($`ii`$) for $`A_𝖲(v,w)`$ we deduce that $`v=v^{}`$. This proves condition ($`ii`$) for $`\zeta `$ to be in $`A_{𝖲𝖳}(v,w)`$, and establishes Claim 2.

We complete the proof by showing that for $`𝖳\mathrm{GDes}(v)`$ we have the decomposition (5.9) of $`A_𝖳(v,w)`$ into disjoint subsets $`C_𝖲(v,w)`$. Comparing the definitions (5.3) and (5.6), we see that $`C_𝖲(v,w)A_𝖲(v,w)`$. Together with Claim 1 this implies that the right hand side of (5.9) is contained in the left hand side.

We show the union is disjoint. Suppose there is a permutation $`\zeta C_𝖲(v,w)C_𝖲^{}(v,w)`$. Then $`\zeta A_𝖲(v,w)A_𝖲^{}(v,w)`$ which equals $`A_{𝖲𝖲^{}}(v,w)`$, by Claim 2. Hence, by condition ($`i`$) for $`\zeta `$ to be in $`A_{𝖲𝖲^{}}(v,w)`$, we have $`v_{𝖲𝖲^{}}\zeta ^1w`$. But then, from condition ($`iii`$) for $`C_𝖲(v,w)`$ and for $`C_𝖲^{}(v,w)`$, we deduce that $`𝖲=𝖲𝖲^{}=𝖲^{}`$, proving the union is disjoint.

We show that $`A_𝖳(v,w)`$ is contained in the union of (5.9). Let $`\zeta A_𝖳(v,w)`$ and set

(5.10)
$$𝖲:=\{𝖱𝖱𝖳,\zeta A_𝖱(v,w)\}.$$

By Claim 2,

$$A_𝖲(v,w)=\{A_𝖱(v,w)𝖱𝖳,\zeta A_𝖱(v,w)\},$$

so $`\zeta A_𝖲(v,w)`$. To show that $`\zeta C_𝖲(v,w)`$, we must verify condition ($`iii`$) of (5.6).

Suppose $`\mathrm{Des}(\zeta )𝖱𝖲`$ and $`v_𝖱\zeta ^1w`$. We need to show that $`𝖲𝖱`$. By the definition (5.10) of $`𝖲`$, it suffices to show that $`\zeta A_𝖱(v,w)`$. By our assumption that $`v_𝖱\zeta ^1w`$, condition ($`i`$) for $`\zeta `$ to be in $`A_𝖱(v,w)`$ holds. We show that condition ($`ii`$) also holds. Suppose $`vv^{}`$ and $`v_𝖱^{}\zeta ^1w`$. By Proposition 2.16(i) we have $`v_𝖲^{}v_𝖱^{}`$, and so by Proposition 2.10, $`v_𝖲^{}\zeta ^1v_𝖱^{}\zeta ^1`$. Thus $`v_𝖲^{}\zeta ^1w`$, and by condition ($`ii`$) for $`\zeta `$ to be in $`A_𝖲(v,w)`$, we have $`v=v^{}`$. This establishes condition ($`ii`$) for $`\zeta `$ to be in $`A_𝖱(v,w)`$. Thus, $`\zeta A_𝖱(u,w)`$, and as explained above, shows that (5.9) is a disjoint union and completes the proof of the theorem. ∎

## 6. Cofreeness, primitive elements, and the coradical filtration of $`𝔖\mathrm{𝑆𝑦𝑚}`$

The monomial basis reveals the existence of a second coalgebra grading on $`𝔖\mathrm{𝑆𝑦𝑚}`$, given by the number of global descents of the indexing permutations. We show that with respect to this grading, $`𝔖\mathrm{𝑆𝑦𝑚}`$ is a cofree graded coalgebra. We deduce an elegant description of the coradical filtration: it corresponds to a filtration of the symmetric groups by certain lower order ideals determined by the number of global descents. In particular, the space of primitive elements is spanned by those $`_u`$ where $`u`$ has no global descents.

We review the notion of cofree graded coalgebras. Let $`V`$ be a vector space and set

$$Q(V):=\underset{k0}{}V^{\text{ }k}.$$

The space $`Q(V)`$, graded by $`k`$, becomes a graded coalgebra with the *deconcatenation* coproduct

$$\mathrm{\Delta }(v_1\text{ }\mathrm{}\text{ }v_k)=\underset{i=0}{\overset{k}{}}(v_1\text{ }\mathrm{}\text{ }v_i)(v_{i+1}\text{ }\mathrm{}\text{ }v_k),$$

and counit $`ϵ(v_1\text{ }\mathrm{}\text{ }v_k)=0`$ for $`k1`$. $`Q(V)`$ is connected, in the sense that the component of degree $`0`$ is identified with the base field via $`ϵ`$.

We call $`Q(V)`$ the cofree graded coalgebra cogenerated by $`V`$. The canonical projection $`\pi :Q(V)V`$ satisfies the following universal property. Given a graded coalgebra $`C=_{k0}C^k`$ and a linear map $`\phi :CV`$ where $`\phi (C^k)=0`$ when $`k1`$, there is a unique morphism of graded coalgebras $`\widehat{\phi }:CQ(V)`$ such that the following diagram commutes

Explicitly, $`\widehat{\phi }`$ is defined by

(6.1)
$$\widehat{\phi }_{|_{C^k}}=\phi ^{\text{ }k}\mathrm{\Delta }^{(k1)}.$$

In particular, $`\widehat{\phi }_{|_{C^0}}=ϵ`$, $`\widehat{\phi }_{|_{C^1}}=\phi `$, and $`\widehat{\phi }_{|_{C^2}}=(\phi \text{ }\phi )\mathrm{\Delta }`$.

We establish the cofreeness of $`𝔖\mathrm{𝑆𝑦𝑚}`$ by first defining a second coalgebra grading. Let $`𝔖^0:=𝔖_0`$, and for $`k1`$, let

$`𝔖_n^k`$ $`:=\{u𝔖_nu\text{ has exactly }k1\text{ global descents}\},\text{ and}`$
$`𝔖^k`$ $`:={\displaystyle \underset{n0}{}}𝔖_n^k.`$
For instance,

$$\begin{array}{c}𝔖^1=\{1\}\{12\}\{123,\mathrm{\hspace{0.17em}213},\mathrm{\hspace{0.17em}132}\}\{1234,\mathrm{\hspace{0.17em}2134},\mathrm{\hspace{0.17em}1324},\mathrm{\hspace{0.17em}1243},\mathrm{\hspace{0.17em}3124},\hfill \\ \hfill 2314,\mathrm{\hspace{0.17em}2143},\mathrm{\hspace{0.17em}1423},\mathrm{\hspace{0.17em}1342},\mathrm{\hspace{0.17em}3214},\mathrm{\hspace{0.17em}3142},\mathrm{\hspace{0.17em}2413},\mathrm{\hspace{0.17em}1432}\}\mathrm{}\end{array}$$

Let $`(𝔖\mathrm{𝑆𝑦𝑚})^k`$ be the vector subspace of $`𝔖\mathrm{𝑆𝑦𝑚}`$ spanned by $`\{_uu𝔖^k\}`$.

###### Theorem 6.1.

The decomposition $`𝔖\mathrm{𝑆𝑦𝑚}=_{k0}(𝔖\mathrm{𝑆𝑦𝑚})^k`$ is a coalgebra grading. Moreover, endowed with this grading, $`𝔖\mathrm{𝑆𝑦𝑚}`$ is a cofree graded coalgebra.

###### Proof.

Let $`u𝔖_n^k`$ and write $`\mathrm{GDes}(u)=\{p_1<\mathrm{}<p_{k1}\}`$. By Theorem 3.1,

$$\mathrm{\Delta }(_u)=1\text{ }_u+\underset{i=1}{\overset{k1}{}}_{\mathrm{st}(u_1,\mathrm{},u_{p_i})}\text{ }_{\mathrm{st}(u_{p_i+1},\mathrm{},u_n)}+_u\text{ }1.$$

Since $`\mathrm{st}(u_1,\mathrm{},u_{p_i})`$ and $`\mathrm{st}(u_{p_i+1},\mathrm{},u_n)`$ have $`i1`$ and $`k1i`$ global descents, we have

$$\mathrm{\Delta }\left((𝔖\mathrm{𝑆𝑦𝑚})^k\right)\underset{i=0}{\overset{k}{}}(𝔖\mathrm{𝑆𝑦𝑚})^i\text{ }(𝔖\mathrm{𝑆𝑦𝑚})^{ki}.$$

Thus $`𝔖\mathrm{𝑆𝑦𝑚}=_{k0}(𝔖\mathrm{𝑆𝑦𝑚})^k`$ is a graded coalgebra.

Let $`V=(𝔖\mathrm{𝑆𝑦𝑚})^1`$ and $`\phi :𝔖\mathrm{𝑆𝑦𝑚}V`$ the projection associated to the grading. Let $`\widehat{\phi }:𝔖\mathrm{𝑆𝑦𝑚}Q(V)`$ be the morphism of graded coalgebras into the cofree graded coalgebra on $`V`$. For $`u`$ as above, Proposition 5.1 gives,

$$\mathrm{\Delta }^{(k1)}(_u)=\underset{\begin{array}{c}0q_1\mathrm{}q_{k1}n\\ q_i\overline{\mathrm{GDes}}(u)\text{}\end{array}}{}_{\mathrm{st}(u_1,\mathrm{},u_{q_1})}\text{ }\mathrm{}\text{ }_{\mathrm{st}(u_{q_{k1}+1},\mathrm{},u_n)}.$$

Among these chains $`0q_1\mathrm{}q_{k1}n`$ of global descents of $`u`$, there is the chain $`0<p_1<\mathrm{}<p_{k1}<n`$. In any other chain there must be at least one equality, say $`q_i=q_{i+1}`$. Then $`\mathrm{st}(u_{q_i+1},\mathrm{},u_{q_{i+1}})`$ is the empty permutation and the corresponding term is just the identity $`1`$, which is annihilated by $`\phi `$. Therefore, by (6.1), $`\widehat{\phi }`$ is given by

$$\widehat{\phi }(_u)=_{\mathrm{st}(u_1,\mathrm{},u_{p_1})}\text{ }\mathrm{}\text{ }_{\mathrm{st}(u_{p_{k1}+1},\mathrm{},u_n)}V^{\text{ }k}.$$

Consider the map $`\psi :V^{\text{ }k}(𝔖\mathrm{𝑆𝑦𝑚})^k`$ that sends

$$_{v_{(1)}}\text{ }\mathrm{}\text{ }_{v_{(k)}}_{\zeta _𝖳(v_{(1)}\times \mathrm{}\times v_{(k)})},$$

where each $`v_{(i)}𝔖_{q_i}`$ and $`𝖳=\{q_1,q_1+q_2,\mathrm{},q_1+\mathrm{}+q_{k1}\}[n1]`$.

Lemma 2.17 implies that $`\mathrm{GDes}\left(\zeta _𝖳(v_{(1)}\times \mathrm{}\times v_{(k)})\right)=𝖳`$, since each $`v_{(i)}`$ has no global descents. Together with (2.10) this shows that $`\widehat{\phi }\psi =\mathrm{𝑖𝑑}`$.

On the other hand, letting $`𝖲=\mathrm{GDes}(u)`$, Lemma 2.18 implies that

$$u=\zeta _𝖲\left(\mathrm{st}(u_1,\mathrm{},u_{p_1})\times \mathrm{}\times \mathrm{st}(u_{p_{k1}+1},\mathrm{},u_n)\right).$$

This shows that $`\psi \widehat{\phi }=\mathrm{𝑖𝑑}`$. Thus $`\widehat{\phi }`$ is an isomorphism of graded coalgebras. ∎

###### Remark 6.2.

If $`V`$ is finite dimensional then the graded dual of $`Q(V)`$ is simply the (free) tensor algebra $`T(V^{})`$. More generally, suppose $`V=_{n1}V_n`$ is a graded vector space for which each component $`V_n`$ is finite dimensional. Then $`Q(V)`$ admits another grading, for which the elements of $`V_{n_1}\text{ }\mathrm{}\text{ }V_{n_k}`$ have degree $`n_1+\mathrm{}+n_k`$ (with respect to the other grading, these elements have degree $`k`$). With respect to this new grading, the homogeneous components are finite dimensional, and the graded dual of $`Q(V)`$ is the tensor algebra on the graded dual of $`V`$ (again a free algebra).

In our situation, $`𝔖\mathrm{𝑆𝑦𝑚}=Q(V)`$, with $`V`$ graded by the size $`n`$ of the indexing permutations $`u𝔖_n`$. The corresponding grading on $`𝔖\mathrm{𝑆𝑦𝑚}`$ is the original one, for which $`_u`$ has degree $`n`$ if $`u𝔖_n`$. Its graded dual is therefore a free algebra. It is known that $`𝔖\mathrm{𝑆𝑦𝑚}`$ is self-dual with respect to this grading (see Section 9). It follows that $`𝔖\mathrm{𝑆𝑦𝑚}`$ is also a free algebra. This is a result of Poirier and Reutenauer  who construct a different set of algebra generators, not directly related to the monomial basis. (See Remark 6.5.)

Let $`C`$ be a graded connected coalgebra. The coradical $`C^{(0)}`$ of $`C`$ is the 1-dimensional component in degree 0 (identified with the base field via the counit). The primitive elements of $`C`$ are

$$\text{P}(C):=\{xC\mathrm{\Delta }(x)=x\text{ }1+1\text{ }x\}.$$

Set $`C^{(1)}:=C^{(0)}\text{P}(C)`$, the first level of the coradical filtration. More generally, the $`k`$-th level of the coradical filtration is

$$C^{(k)}:=\left(\mathrm{\Delta }^{(k)}\right)^1(\underset{i+j=k}{}C^{\text{ }i}\text{ }C^{(0)}\text{ }C^{\text{ }j}).$$

We have $`C^{(0)}C^{(1)}C^{(2)}\mathrm{}C=_{k0}C^{(k)}`$, and

$$\mathrm{\Delta }(C^{(k)})\underset{i+j=k}{}C^{(i)}\text{ }C^{(j)}.$$

Thus, the coradical filtration measures the complexity of iterated coproducts.

Suppose now that $`C`$ is a cofree graded coalgebra $`Q(V)`$. Then the space of primitive elements is just $`V`$, and the $`k`$-th level of the coradical filtration is $`_{i=0}^kV^{\text{ }i}`$. These are straightforward consequences of the definition of the deconcatenation coproduct.

Define

$$𝔖_n^{(k)}:=\underset{i=0}{\overset{k}{}}𝔖_n^k\text{ and }𝔖^{(k)}:=\underset{i=0}{\overset{k}{}}𝔖^k.$$

In other words, $`𝔖^{(0)}=𝔖_0`$ and for $`k1`$,

$$𝔖_n^{(k)}=\{u𝔖_nu\text{ has at most }k1\text{ global descents}\}.$$

In Proposition 2.13 we showed that $`\mathrm{GDes}:𝔖_n𝒬_n`$ is order-preserving. Since $`𝒬_n`$ is ranked by the cardinality of a subset, it follows that $`𝔖_n^{(k)}`$ is a lower order ideal of $`𝔖_n`$, with $`𝔖_n^{(k)}𝔖_n^{(k+1)}`$. The coradical filtration corresponds precisely to this filtration of the weak order on the symmetric groups by lower ideals.

###### Corollary 6.3.

A linear basis for the $`k`$-th level of the coradical filtration of $`𝔖\mathrm{𝑆𝑦𝑚}`$ is

$$\{_uu𝔖^{(k)}\}.$$

In particular, a linear basis for the space of primitive elements is

$$\{_uu\text{ has no global descents}\}.$$

###### Proof.

This follows from the preceding discussion. ∎

The original grading of $`𝔖\mathrm{𝑆𝑦𝑚}=_n𝔖_n`$ yields a grading on the subspace $`P(𝔖\mathrm{𝑆𝑦𝑚})`$ of primitive elements and on each $`(𝔖\mathrm{𝑆𝑦𝑚})^k`$. Let $`G_1(t)`$ denote the Hilbert series of the space of primitive elements, or equivalently, the generating function for the set of permutations in $`𝔖_n`$ with no global descents,

$$G_1(t):=\underset{n1}{}dim_{}\left(\text{P}_n(𝔖\mathrm{𝑆𝑦𝑚})\right)t^n.$$

More generally, let $`G_k(t)`$ be the Hilbert series of $`(𝔖\mathrm{𝑆𝑦𝑚})^k`$, or equivalently, the generating function for permutations in $`𝔖_n`$ with exactly $`k1`$ global descents,

$$G_k(t):=\underset{nk}{}dim_{}\left((𝔖\mathrm{𝑆𝑦𝑚})_n^k\right)t^n.$$

For instance,

$`G_1(t)`$ $`=t+t^2+3t^3+13t^4+71t^5+461t^6+3447t^7+\mathrm{}`$
$`G_2(t)`$ $`=t^2+2t^3+7t^4+32t^5+177t^6+1142t^7+\mathrm{}`$
$`G_3(t)`$ $`=t^3+3t^4+12t^5+58t^6+327t^7+2109t^8+\mathrm{}`$
There are well-known relationships between the Hilbert series of a graded space $`V`$, its powers $`V^{\text{ }k}`$ and their sum $`Q(V)`$. In our case, these give the following formulas.

###### Corollary 6.4.

We have

1. $`dim_{}\left(\text{P}_n(𝔖\mathrm{𝑆𝑦𝑚})\right)=(1)^{n1}\left|\begin{array}{ccccc}1!& 2!& \mathrm{}& \mathrm{}& n!\\ 1& 1!& \mathrm{}& \mathrm{}& (n1)!\\ 0& 1& 1!& \mathrm{}& (n2)!\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& \mathrm{}& 0& 1& 1!\end{array}\right|`$.
2. $`G_1(t)=1{\displaystyle \frac{1}{_{n0}n!t^n}}`$ .
3. $`G_k(t)=\left(G_1(t)\right)^k`$ .

###### Remark 6.5.

Formula $`(i)`$ is analogous to a formula for ordinary descents in \[32, Example 2.2.4\]. Formulas $`(ii)`$ and $`(iii)`$ in Corollary 6.4 are due to Lentin \[17, Section 6.3\], see also Comtet \[6, Exercise VI.14\]. These references do not consider global descents, but rather the problem of decomposing a permutation $`u𝔖_n`$ as a non-trivial product $`u=v\times w`$. This is equivalent to our study of global descents, as we may write $`u=v\times w`$ with $`v𝔖_p`$ exactly when $`n+1p`$ is a global descent of $`u\omega _n`$. For instance, $`u=563241`$ has global descents $`\{2,5\}`$ and $`u\omega _6=142365=1\times 312\times 21`$. See the Encyclopedia of Integer Sequences  (A003319 and A059438) for additional references in this connection.

Poirier and Reutenauer  showed that the elements of the dual basis $`\{_u^{}\}`$ indexed by the connected permutations freely generate $`(𝔖\mathrm{𝑆𝑦𝑚})^{}`$. Duchamp, Hivert, and Thibon dualize the resulting linear basis, giving a different basis than we do for the space of primitive elements \[8, Prop. 3.6\].

## 7. The descent map to quasi-symmetric functions

We study the effect of the morphism of Hopf algebras (1.11)

$$𝒟:𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚},\text{ defined by }_uF_{\mathrm{Des}(u)}$$

on the monomial basis. Here, we use subsets $`𝖲`$ of $`[n1]`$ to index monomial and fundamental quasi-symmetric functions of degree $`n`$, as discussed at the end of Section 1.2. Our main tool is the Galois connection $`𝔖_n𝒬_n`$ of Section 2.3.

When we have a Galois connection between posets $`P`$ and $`Q`$ given by a pair of maps $`f:PQ`$ and $`g:QP`$ as in (2.7), a classical theorem of Rota \[30, Theorem 1\] states that the Möbius functions of $`P`$ and $`Q`$ are related by

$$xP\text{ and }wQ,\underset{\begin{array}{c}yP\\ xy,f(y)=w\end{array}}{}\mu _P(x,y)=\underset{\begin{array}{c}vQ\\ vw,g(v)=x\end{array}}{}\mu _Q(v,w).$$

A conceptual proof of this simple but extremely useful result can be found in .

###### Definition 7.1.

A permutation $`u𝔖_n`$ is closed if it is of the form $`u=\zeta _𝖳`$ for some $`𝖳𝒬_n`$.

Equivalently, in view of (2.8) and (2.9), $`u`$ is closed if and only if $`\mathrm{Des}(u)=\mathrm{GDes}(u)`$.

From Proposition 2.11, we deduce the following fact about the Möbius function of the weak order.

###### Corollary 7.2.

Let $`u𝔖_n`$ and $`𝖲𝒬_n`$. Then

(7.1)
$$\underset{\begin{array}{c}uv𝔖_n\\ \mathrm{Des}(v)=𝖲\end{array}}{}\mu _{𝔖_n}(u,v)=\{\begin{array}{cc}\mu _{𝒬_n}(\mathrm{Des}(u),𝖲)\hfill & \text{if }u\text{ is closed,}\hfill \\ 0\hfill & \text{if not.}\hfill \end{array}$$

###### Proof.

Rota’s formula says in this case that

$$\underset{\begin{array}{c}uv𝔖_n\\ \mathrm{Des}(v)=𝖲\text{}\end{array}}{}\mu _{𝔖_n}(u,v)=\underset{\begin{array}{c}𝖳𝖲𝒬_n\\ \zeta _T=u\text{}\end{array}}{}\mu _{𝒬_n}(𝖳,𝖲).$$

If $`u`$ is not closed, then the index set on the right hand side is empty. If $`u`$ is closed, then the index set consists only of the set $`𝖳=\mathrm{Des}(u)`$, by assertion (c) in the proof of Proposition 2.11. ∎

While there are explicit formulas for the Möbius function of the weak order, it is precisely the above result that allows us to obtain the description of the map $`𝒟:𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚}`$ in terms of the monomial bases.

###### Theorem 7.3.

Let $`u𝔖_n`$. Then

$$𝒟(_u)=\{\begin{array}{cc}M_{\mathrm{GDes}(u)}\hfill & \text{if }u\text{ is closed,}\hfill \\ 0\hfill & \text{if not.}\hfill \end{array}$$

###### Proof.

By definition, $`_u=_{uv}\mu _{𝔖_n}(u,v)_v`$, hence

$`𝒟(_u)`$ $`={\displaystyle \underset{uv}{}}\mu _{𝔖_n}(u,v)F_{\mathrm{Des}(v)}`$
$`={\displaystyle \underset{𝖲}{}}\left({\displaystyle \underset{\begin{array}{c}uv\\ \mathrm{Des}(v)=𝖲\end{array}}{}}\mu _{𝔖_n}(u,v)\right)F_𝖲`$
$`=\{\begin{array}{cc}_𝖲\mu _{𝒬_n}(\mathrm{Des}(u),𝖲)F_𝖲\hfill & \text{if }u\text{ is closed}\hfill \\ 0\hfill & \text{if not.}\hfill \end{array}`$
We complete the proof by noting that

$$M_{\mathrm{Des}(u)}=\underset{𝖲}{}\mu _{𝒬_n}(\mathrm{Des}(u),𝖲)F_𝖲$$

by the definition of $`M_{\mathrm{Des}(u)}`$, and that since $`u`$ is closed, $`\mathrm{Des}(u)=\mathrm{GDes}(u)`$. ∎

Malvenuto shows that $`𝒟`$ is a morphism of Hopf algebras by comparing the structures on the fundamental bases of $`𝔖\mathrm{𝑆𝑦𝑚}`$ and $`𝒬\mathrm{𝑆𝑦𝑚}`$. We do the same for the monomial bases of $`𝔖\mathrm{𝑆𝑦𝑚}`$ and $`𝒬\mathrm{𝑆𝑦𝑚}`$.

To compare the coproducts, first note that for any subsets $`𝖲[p1]`$ and $`𝖳[q1]`$,

$$\zeta _{𝖲\{p\}𝖳}=\zeta _{p,q}(\zeta _𝖲\times \zeta _𝖳).$$

Therefore, if $`u𝔖_n`$ and $`p\overline{\mathrm{GDes}}(u)`$, then

$`u`$ is closed $``$ both $`\mathrm{st}(u_1,\mathrm{},u_p)`$ and $`\mathrm{st}(u_{p+1},\mathrm{},u_n)`$ are closed.
It follows that applying the map $`𝒟:𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚}`$ to formula (3.1) gives the usual formula (1.6) for the coproduct of monomial quasi-symmetric functions.

For instance, we compare formula (4.1) with (1.5). Since $`𝒟(_{21})=M_{(1,1)}`$ and $`𝒟(_{12})=M_{(2)}`$, applying $`𝒟`$ to (4.1) results in (1.5). Indeed, the indices $`u`$ in the first row of (4.1) all are closed, while none in the second row are closed. It is easy to verify that the five terms on the right in the first row in (4.1) map to the five terms on the right in (1.5).

The situation is different for the products. The geometric description of the structure constants of the product on the monomial basis of $`𝔖\mathrm{𝑆𝑦𝑚}`$ (4.4) admits an analogue for $`𝒬\mathrm{𝑆𝑦𝑚}`$, but this turns out to be very different from the known description in terms of quasi-shuffles (1.4). We present this new description of the structure constants for the product of monomial quasi-symmetric functions.

The role of the permutahedron is now played by the cube. Associating a subset $`𝖲`$ of $`[n1]`$ to its characteristic function gives a bijection between subsets of $`[n1]`$ and vertices of the $`(n1)`$-dimensional cube $`[0,1]^{n1}`$. Coordinatewise comparison corresponds to subset inclusion, and the 1-skeleton of the cube becomes the Hasse diagram of the Boolean poset $`𝒬_n`$. In this way, we identify $`𝒬_n`$ with the vertices of the $`(n1)`$-dimensional cube.

For each Grassmannian permutation $`\zeta 𝔖^{(p,q)}`$, consider the map

$$r_\zeta :𝒬_p\times 𝒬_q𝒬_{p+q},(𝖲,𝖳)\mathrm{Des}((\zeta _𝖲\times \zeta _𝖳)\zeta ^1).$$

We describe this map $`r_\zeta `$ in more detail. To that end, set

$$\mathrm{Cons}_p(\zeta ):=\{i[p+q1]\zeta ^1(i)+1=\zeta ^1(i+1)\text{ and }\zeta ^1(i)p\},$$

and recall that the vertices in a face of the cube are an interval in the Boolean poset, with every interval corresponding to a unique face.

###### Lemma 7.4.

Let $`p,q`$ be positive integers and $`\zeta 𝔖^{(p,q)}`$. The image of $`r_\zeta `$ is the face

$$[\mathrm{Des}(\zeta ^1),\mathrm{Des}(\zeta ^1)\mathrm{Cons}_p(\zeta )],$$

which is isomorphic to the Boolean poset of subsets of $`\mathrm{Cons}_p(\zeta )`$.

###### Proof.

This is an immediate consequence of an alternative (and direct) description of $`r_\zeta (𝖲,𝖳)`$. For $`𝖳𝒬_q`$, set $`p+𝖳:=\{p+tt𝖳\}`$. Then, for $`(𝖲,𝖳)𝒬_p\times 𝒬_q`$, we have

(7.2)
$$r_\zeta (𝖲,𝖳)=\mathrm{Des}(\zeta ^1)(\mathrm{Cons}_p(\zeta )\zeta (𝖲(p+𝖳))).$$

Assuming this for a moment, we note that the association $`(𝖲,𝖳)\zeta \left(𝖲(p+𝖳)\right)`$ is a bijection between $`𝒬_p\times 𝒬_q`$ and subsets of $`\{i\zeta ^1(i)p\}`$. Intersecting with $`\mathrm{Cons}_p(\zeta )`$ we obtain a surjection onto subsets of $`\mathrm{Cons}_p(\zeta )`$, which yields the desired description of the image of $`r_\zeta `$.

We prove (7.2). Let $`(𝖲,𝖳)𝒬_p\times 𝒬_q`$ and set $`w:=(\zeta _𝖲\times \zeta _𝖳)\zeta ^1`$ so that $`\mathrm{Des}(w)=r_\zeta (𝖲,𝖳)`$. Note that $`\mathrm{Des}(\zeta _𝖲\times \zeta _𝖳)=𝖲(p+𝖳)`$ (this is a particular case of Lemma 2.17) and if $`ip<j`$, then $`(\zeta _𝖲\times \zeta _𝖳)(i)p<(\zeta _𝖲\times \zeta _𝖳)(j)`$.

Let $`i[n1]`$. We consider whether or not $`i`$ is a descent of $`w`$. First, suppose $`i\mathrm{Des}(\zeta ^1)`$. Since the values $`1,2,\mathrm{},p`$ and $`p+1,p+2,\mathrm{},p+q`$ occur in order in the permutation $`\zeta ^1`$ (because $`\zeta 𝔖^{(p,q)}`$), we must have $`\zeta ^1(i)>p\zeta ^1(i+1)`$ and so $`w(i)>pw(i+1)`$, thus $`i\mathrm{Des}(w)`$.

Now suppose that $`i`$ is not a descent of $`\zeta ^1`$. If $`\zeta ^1(i)+1<\zeta ^1(i+1)`$, then we must have $`\zeta ^1(i)p<\zeta ^1(i+1)`$, again because $`\zeta 𝔖^{(p,q)}`$. Hence $`w(i)p<w(i+1)`$ and $`i`$ is not a descent of $`w`$. If instead we have $`\zeta ^1(i)+1=\zeta ^1(i+1)`$, then there are two cases to consider. If $`i=\zeta ^1(p)`$, then this forces $`\zeta `$ to be $`1_{p+q}`$ so $`w(i)=w(p)p<w(i+1)`$, and we conclude that $`i`$ is not a descent of $`w`$. If $`i\zeta ^1(p)`$, then $`i\mathrm{Cons}_p(\zeta )`$ and we see that $`i`$ is a descent of $`w`$ exactly when $`\zeta ^1(i)𝖲(p+𝖳)`$. This proves (7.2) and completes the proof of the lemma. ∎

Unlike the case of the permutahedron, the image of $`r_\zeta `$ need not be a facet. Indeed, by Lemma 7.4, the image of $`r_\zeta `$ is a facet only if $`\mathrm{\#}\mathrm{Cons}_p(\zeta )=p+q2`$, and this occurs only when $`\zeta =1_{p+q}`$ or $`\zeta =\zeta _{p,q}`$. Figure 4 displays the vertices of the 3-cube and Figure 5 shows which faces occur as the image $`r_\zeta (𝒬_p\times 𝒬_q)`$.

Observe that while not all faces occur as images of some $`r_\zeta (𝒬_p\times 𝒬_q)`$, any face that does occur is the image of a unique such map. This is the general case.

###### Lemma 7.5.

A face of $`𝒬_n`$ is the image of $`𝒬_p\times 𝒬_{np}`$ under a map $`r_\zeta `$ for at most one pair $`(\zeta ,p)`$.

###### Proof.

Suppose $`\zeta 𝔖^{(p,np)}`$ for some $`0<p<n`$. We will observe that the pair of sets $`\mathrm{Des}(\zeta ^1)`$ and $`\mathrm{Cons}_p(\zeta )`$ determines $`\zeta `$ and $`p`$ uniquely by describing these sets.

Suppose first that $`\zeta =1_n`$. Then $`\mathrm{Des}(\zeta ^1)=\mathrm{}`$ and $`\mathrm{Cons}_p(\zeta )=[n1]\{p\}`$.

Suppose now that $`\zeta 𝔖^{(p,np)}`$ is not the identity permutation. Then $`\zeta `$ determines $`p`$ and $`\mathrm{Des}(\zeta ^1)\mathrm{}`$. Since the values $`1,2,\mathrm{},p`$ and $`p+1,\mathrm{},n`$ occur in order in $`\zeta ^1`$, there exist numbers

$$0b_0<a_1<b_1<\mathrm{}<a_k<b_kn$$

such that the values in $`[p]`$ occur in order in the intervals

$$[0,b_0],[a_1+1,b_1],\mathrm{},[a_k+1,b_k],$$

and the values in $`\{p+1,\mathrm{},n\}`$ in the complementary set. Thus $`\mathrm{Des}(\zeta ^1)=\{a_1,\mathrm{},a_k\}`$ and $`\mathrm{Cons}_p(\zeta )=[n1]\{b_0,a_1,b_1,a_2,\mathrm{},a_k,b_k\}`$.

It follows that $`\zeta `$ and $`p`$ determine and are determined by the sets $`\mathrm{Des}(\zeta ^1)`$ and $`\mathrm{Cons}_p(\zeta )`$, which completes the proof of the lemma. ∎

###### Theorem 7.6.

Suppose $`p,q`$ are positive integers. Let $`𝖲[p1]`$, $`𝖳[q1]`$ and $`𝖱[p+q1]`$. The coefficient of $`M_{p+q,𝖱}`$ in $`M_{p,𝖲}M_{q,𝖳}`$ is

(7.3)
$$\mathrm{\#}\{\zeta 𝔖^{(p,q)}(𝖲,𝖳)=\mathrm{max}r_\zeta ^1[\mathrm{},𝖱]\}.$$

In other words, this coefficient counts the number of faces of the cube of type $`(p,q)`$ with the property that the vertex $`r_\zeta (𝖲,𝖳)`$ is below $`𝖱`$ and it is the maximal vertex in the the face $`r_\zeta (𝒬_p\times 𝒬_q)`$ below $`𝖱`$.

###### Proof.

By Theorem 7.3, $`M_{p,𝖲}M_{q,𝖳}=𝒟(_{\zeta _𝖲}_{\zeta _𝖳})`$. We expand the product using Theorem 4.1, and then apply the map $`𝒟`$ and Theorem 7.3 to obtain

$$M_{p,𝖲}M_{q,𝖳}=𝒟(_{\zeta _𝖲}_{\zeta _𝖳})=𝒟\left(\underset{w𝔖_{p+q}}{}\alpha _{\zeta _𝖲,\zeta _𝖳}^w_w\right)=\underset{𝖱𝒬_{p+q}}{}\alpha _{\zeta _𝖲,\zeta _𝖳}^{\zeta _R}M_{p+q,𝖱}.$$

According to (4.4),

$$\alpha _{\zeta _𝖲,\zeta _𝖳}^{\zeta _𝖱}=\mathrm{\#}\{\zeta 𝔖^{(p,q)}(\zeta _𝖲,\zeta _𝖳)=\mathrm{max}\rho _\zeta ^1[1,\zeta _𝖱]\}.$$

By Proposition 2.11, for any $`𝖲`$, $`𝖳`$, and $`𝖱`$ we have

$$\mathrm{Des}\left((\zeta _𝖲\times \zeta _𝖳)\zeta ^1\right)𝖱(\zeta _𝖲\times \zeta _𝖳)\zeta ^1\zeta _𝖱.$$

In other words,

$$r_\zeta (𝖲,𝖳)𝖱\rho _\zeta (\zeta _𝖲,\zeta _𝖳)\zeta _𝖱.$$

This implies that the structure constant $`\alpha _{\zeta _𝖲,\zeta _𝖳}^{\zeta _R}`$ is as stated. ∎

We give an example. Let $`p=1`$, $`q=3`$, $`𝖲=\mathrm{}`$ and $`𝖳=\{1\}`$. In terms of compositions, we have $`M_{\mathrm{},1}=M_{(1)}`$, and $`M_{\{1\},3}=M_{(1,2)}`$. Equation (1.4) gives

$`M_{\mathrm{},1}M_{\{1\},3}=M_{(1)}M_{(1,2)}`$ $`=2M_{(1,1,2)}+M_{(1,2,1)}+M_{(2,2)}+M_{(1,3)}`$
$`=2M_{\{1,2\},4}+M_{\{1,3\},4}+M_{\{2\},4}+M_{\{1\},4}.`$
On the other hand, (7.3) also predicts that the coefficient of $`M_{\{1,2\}}`$ is $`2`$. Of the four possible faces of type $`(1,3)`$, only two satisfy the required condition. One corresponds to the shuffle $`1234`$ (it is a facet) and the other to $`2134`$ (it is an edge). They are shown in Figure 6, together with the vertices $`r_{1234}(\mathrm{},\{1\})=\{2\}`$, $`r_{2134}(\mathrm{},\{1\})=\{1\}`$, and the vertex $`\{1,2\}`$.

## 8. $`𝔖\mathrm{𝑆𝑦𝑚}`$ is a crossed product over $`𝒬\mathrm{𝑆𝑦𝑚}`$

We obtain a decomposition of the algebra structure of $`𝔖\mathrm{𝑆𝑦𝑚}`$ as a crossed product over the Hopf algebra $`𝒬\mathrm{𝑆𝑦𝑚}`$. We refer the reader to \[26, §7\] for a review of this construction in the general Hopf algebraic setting. Let us only say that the crossed product of a Hopf algebra $`K`$ with an algebra $`A`$ with respect to a Hopf cocycle $`\sigma :K\text{ }KA`$ is a certain algebra structure on the space $`AK`$, denoted by $`A\mathrm{\#}_\sigma K`$.

###### Theorem 8.1.

The map $`𝒵:𝒬\mathrm{𝑆𝑦𝑚}𝔖\mathrm{𝑆𝑦𝑚}`$, $`M_𝖲_{\zeta _𝖲}`$, is a morphism of coalgebras and a right inverse to the morphism of Hopf algebras $`𝒟:𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚}`$.

###### Proof.

This is immediate from Theorems 3.1 and 7.3. ∎

In this situation, an important theorem of Blattner, Cohen, and Montgomery  applies. Namely, suppose $`\pi :HK`$ is a morphism of Hopf algebras that admits a coalgebra splitting (right inverse) $`\gamma :KH`$. Then there is a *crossed product* decomposition

$$HA\mathrm{\#}_\sigma K$$

where $`A`$, a subalgebra of $`H`$, is the *left Hopf kernel* of $`\pi `$:

$$A=\{hHh_1\text{ }\pi (h_2)=h\text{ }1\}$$

and the *Hopf cocycle* $`\sigma :K\text{ }KA`$ is

(8.1)
$$\sigma (k,k^{})=\gamma (k_1)\gamma (k_1^{})S\gamma (k_2k_2^{}).$$

This result, as well as some generalizations, can be found in \[26, §7\]. Note that if $`\pi `$ and $`\gamma `$ preserve gradings, then so does the rest of the structure.

Let $`A`$ be the left Hopf kernel of $`𝒟:𝔖\mathrm{𝑆𝑦𝑚}𝒬\mathrm{𝑆𝑦𝑚}`$ and $`A_n`$ its $`n`$-th homogeneous component. Once again the monomial basis of $`𝔖\mathrm{𝑆𝑦𝑚}`$ proves useful in describing $`A`$.

###### Theorem 8.2.

A basis for $`A_n`$ is the set $`\{_u\}`$ where $`u`$ runs over all permutations of $`n`$ that are not of the form

($``$)
$$\mathrm{}12\mathrm{}nk$$

for any $`k=0,\mathrm{},n1`$. In particular,

$$dimA_n=n!\underset{k=0}{\overset{n1}{}}k!.$$

###### Proof.

By the theorem of Blattner, Cohen, and Montgomery, $`𝔖\mathrm{𝑆𝑦𝑚}A\mathrm{\#}_\sigma 𝒬\mathrm{𝑆𝑦𝑚}`$, in particular $`𝔖\mathrm{𝑆𝑦𝑚}A\text{ }𝒬\mathrm{𝑆𝑦𝑚}`$ as vector spaces. The generating functions for the dimensions of these algebras are therefore related by

$$\underset{n0}{\overset{\mathrm{}}{}}n!t^n=\underset{n0}{}a_nt^n\left(1+\underset{n1}{}2^{n1}t^n\right)=\underset{n0}{}a_nt^n\frac{1}{1_{n1}t^n}.$$

It follows that $`a_n=n!_{k=0}^{n1}k!`$ as claimed.

Observe that $`a_n`$ counts the permutations in $`𝔖_n`$ that are not of the form ($``$8.2). Since the $`_u`$ are linearly independent, it suffices to show that if $`u`$ is not of that form then $`_u`$ is in the Hopf kernel. Now, for any $`u𝔖_n`$ and $`p\mathrm{GDes}(u)`$, we have that $`\mathrm{st}(u_{p+1},\mathrm{},u_n)=(u_{p+1},\mathrm{},u_n)`$. Hence, if $`u`$ is not of the form ($``$8.2), the same is true of $`\mathrm{st}(u_{p+1},\mathrm{},u_n)`$ and therefore this permutation is not closed. It follows from Theorems 3.1 and 7.3 that $`(id\text{ }𝒟)\mathrm{\Delta }(_u)=_u\text{ }1`$. ∎

###### Remark 8.3.

These results were motivated by a question of Nantel Bergeron, who asked (in dual form) if $`𝔖\mathrm{𝑆𝑦𝑚}`$ is cofree as right comodule over $`𝒬\mathrm{𝑆𝑦𝑚}`$. This is an immediate consequence of the crossed product decomposition.

Consider again the general situation of a morphism of Hopf algebras $`\pi :HK`$ with a coalgebra splitting $`\gamma :KH`$. This induces an exact sequence of Lie algebras

(8.2)
$$0\text{P}(H)A\text{P}(H)\stackrel{𝜋}{}\text{P}(K)0$$

with a linear splitting $`\text{P}(K)\stackrel{𝛾}{}\text{P}(H)`$, where $`\text{P}(H)`$ denotes the space of primitive elements of $`H`$, viewed as a Lie algebra under the commutator bracket $`[h,h^{}]=hh^{}h^{}h`$.

The Hopf cocycle restricts to a linear map $`\sigma :\text{P}(K)\text{ }\text{P}(K)\text{P}(H)A`$; in fact, for primitive elements $`k`$ and $`k^{}`$, (8.1) specializes to

(8.3)
$$\sigma (k,k^{})=S\gamma (kk^{})\gamma (k^{})\gamma (k)$$

and a direct calculation shows that this element of $`H`$ is primitive. Moreover, the Lie cocycle corresponding to (8.2) is the map $`\stackrel{~}{\sigma }:\text{P}(K)\text{P}(K)\text{P}(H)A`$ given by

(8.4)
$$\stackrel{~}{\sigma }(k,k^{})=[\gamma (k),\gamma (k^{})]\gamma ([k,k^{}])=\sigma (k,k^{})\sigma (k^{},k).$$

This map is a non-abelian Lie cocycle in the sense that the following conditions hold. For $`k`$, $`k^{}\text{P}(K)`$ and $`a\text{P}(H)A`$,

$$k(k^{}a)k^{}(ka)=[\stackrel{~}{\sigma }(k,k^{}),a]+[k,k^{}]a$$

$$k\stackrel{~}{\sigma }(k^{},k^{\prime \prime })k^{}\stackrel{~}{\sigma }(k,k^{\prime \prime })+k^{\prime \prime }\stackrel{~}{\sigma }(k,k^{})=\stackrel{~}{\sigma }([k,k^{}],k^{\prime \prime })\stackrel{~}{\sigma }([k,k^{\prime \prime }],k^{})+\stackrel{~}{\sigma }([k^{},k^{\prime \prime }],k)$$

where $`ka=[\gamma (k),a]`$.

Let us apply these considerations to the morphism $`𝔖\mathrm{𝑆𝑦𝑚}\stackrel{𝒟}{}𝒬\mathrm{𝑆𝑦𝑚}`$ and the coalgebra splitting $`𝒬\mathrm{𝑆𝑦𝑚}\stackrel{𝒵}{}𝒬\mathrm{𝑆𝑦𝑚}`$. The structure constants of the Hopf cocycle $`\sigma `$ do not have constant sign. However, its restriction to primitive elements of $`𝒬\mathrm{𝑆𝑦𝑚}`$ has non-negative structure constants on the monomial bases. They turn out to be particular structure constants of the product of $`𝔖\mathrm{𝑆𝑦𝑚}`$.

Recall that these structure constants $`\alpha _{u,v}^w`$ are defined for $`u𝔖_p`$, $`v𝔖_q`$ and $`w𝔖_{p+q}`$ by the identity

$$_u_v=\underset{w𝔖_{p+q}}{}\alpha _{u,v}^w_w.$$

The combinatorial description of these constants showing their non-negativity is given by (4.2).

###### Lemma 8.4.

For $`p,q1`$, and $`w𝔖_{p+q}`$ closed, we have $`\alpha _{1_p,1_q}^w=0`$ except in the following cases

$$\alpha _{1_p,1_q}^{1_{p+q}}=1,\alpha _{1_p,1_p}^{\zeta _{p,p}}=2\text{ and if }pq\text{, then }\alpha _{1_p,1_q}^{\zeta _{p,q}}=1.$$

###### Proof.

Apply the map $`𝒟`$ to the product

$$\underset{w𝔖_{p+q}}{}\alpha _{1_p,1_q}^w_w=_{1_p}_{1_q},$$

to obtain (using (1.4))

$$\underset{w𝔖_{p+q}}{}\alpha _{1_p,1_q}^w𝒟(_w)=M_{(p)}M_{(q)}=M_{(p,q)}+M_{(q,p)}+M_{(p+q)}.$$

The result is immediate, as $`𝒟(_w)=0`$ unless $`w`$ is closed, and we have $`𝒟(_{\zeta _{p,q}})=M_{(p,q)}`$ and $`𝒟(_{1_{p+q}})=M_{(p+q)}`$. ∎

We use this lemma to give a combinatorial description of $`\sigma `$ and the Lie cocycle $`\stackrel{~}{\sigma }`$ on primitive elements. By (1.6), $`\{M_{(n)}\}_{n1}`$ is a linear basis for the space of primitive elements of $`𝒬\mathrm{𝑆𝑦𝑚}`$. Thus $`\text{P}(𝒬\mathrm{𝑆𝑦𝑚})`$ is an abelian Lie algebra with each homogeneous component of dimension $`1`$. Recall that $`\{_uu\text{ has no global descents}\}`$ is a basis of the primitive elements of $`𝔖\mathrm{𝑆𝑦𝑚}`$, and thus $`A\text{P}(𝔖\mathrm{𝑆𝑦𝑚})`$ has a basis given by those $`_u`$ where $`u`$ has no global descents and $`u`$ is not an identity permutation, $`1_n`$.

###### Theorem 8.5.

For any $`p`$, $`q1`$,

$`\sigma (M_{(p)},M_{(q)})`$ $`={\displaystyle \underset{w\zeta _{p,q},\zeta _{q,p},\mathrm{\hspace{0.17em}1}_{p+q}}{}}\alpha _{1_q,1_p}^w_w`$
$`\stackrel{~}{\sigma }(M_{(p)},M_{(q)})`$ $`={\displaystyle \underset{w}{}}\left(\alpha _{1_q,1_p}^w\alpha _{1_p,1_q}^w\right)_w.`$
###### Proof.

Since $`M_{(p)}M_{(q)}=M_{(p,q)}+M_{(q,p)}+M_{(p+q)}`$, (8.3) gives

$`\sigma (M_{(p)},M_{(q)})`$ $`=S𝒵(M_{(p,q)}+M_{(q,p)}+M_{(p+q)})𝒵(M_{(q)})𝒵(M_{(p)}`$
$`=S(_{\zeta _{p,q}}+_{\zeta _{q,p}}+_{1_{p+q}})_{1_q}_{1_p}.`$
Using (5.1) and (3.1), we compute $`S(_{\zeta _{p,q}})=_{1_p}_{1_q}_{\zeta _{p,q}}`$ and $`S(_{1_{p+q}})=_{1_{p+q}}`$. Therefore,

$$\sigma (M_{(p)},M_{(q)})=_{1_p}_{1_q}_{\zeta _{p,q}}_{\zeta _{q,p}}_{1_{p+q}}.$$

The formula for $`\sigma (M_{(p)},M_{(q)})`$ follows by expanding the product and using Lemma 8.4. The expression for $`\stackrel{~}{\sigma }`$ follows immediately from (8.4). ∎

## 9. Self-duality of $`𝔖\mathrm{𝑆𝑦𝑚}`$ and applications

The Hopf algebra $`𝔖\mathrm{𝑆𝑦𝑚}`$ is self-dual. This appears in \[22, section 5.2\], \[23, Theorem 3.3\], and . We provide a proof below, for completeness. We investigate the combinatorial implications of this self-duality, particularly when expressed in terms of the monomial basis. We explain how a result of Foata and Schützenberger on the numbers

$$d(𝖲,𝖳)=\mathrm{\#}\{x𝔖_n\mathrm{Des}(x)=𝖲,\mathrm{Des}(x^1)=𝖳\}$$

is a consequence of self-duality of $`𝔖\mathrm{𝑆𝑦𝑚}`$ and obtain analogous results for the numbers

$$\theta (u,v):=\mathrm{\#}\{x𝔖_nxu,x^1v\}.$$

The Hopf algebra $`𝔖\mathrm{𝑆𝑦𝑚}`$ is connected and graded with each homogeneous component finite dimensional. We consider its *graded dual* $`(𝔖\mathrm{𝑆𝑦𝑚})^{}`$ whose homogeneous component in degree $`n`$ is the linear dual of the homogeneous component in degree $`n`$ of $`𝔖\mathrm{𝑆𝑦𝑚}`$. Let $`\{_u^{}u𝔖_n,n0\}`$ and $`\{_u^{}u𝔖_n,n0\}`$ be the bases of $`(𝔖\mathrm{𝑆𝑦𝑚})^{}`$ dual to the fundamental and monomial bases of $`𝔖\mathrm{𝑆𝑦𝑚}`$, respectively. $`(𝔖\mathrm{𝑆𝑦𝑚})^{}`$ is another graded connected Hopf algebra.

###### Theorem 9.1.

The map

(9.1)
$$\mathrm{\Theta }:(𝔖\mathrm{𝑆𝑦𝑚})^{}𝔖\mathrm{𝑆𝑦𝑚},_u^{}_{u^1}$$

is an isomorphism of Hopf algebras. On the monomial basis it is given by

(9.2)
$$\mathrm{\Theta }(_u^{})=\underset{v}{}\theta (u,v)_v.$$

Proof. Note that $`\mathrm{\Theta }^{}=\mathrm{\Theta }`$. Therefore, it suffices to show that $`\mathrm{\Theta }`$ is a morphism of coalgebras. We rewrite the product (1.1) of $`𝔖\mathrm{𝑆𝑦𝑚}`$. Let $`u𝔖_p`$ and $`v𝔖_q`$. Then

$$_u_v=\underset{w𝔖_{p+q}}{}\mathrm{\#}\{\zeta 𝔖^{(p,q)}(u\times v)\zeta ^1=w\}_w.$$

Therefore the (dual) coproduct of $`(𝔖\mathrm{𝑆𝑦𝑚})^{}`$ is

$$\mathrm{\Delta }(_w^{})=\underset{p+q=n}{}\underset{u𝔖_p,v𝔖_q}{}\mathrm{\#}\{\zeta 𝔖^{(p,q)}(u\times v)\zeta ^1=w\}_u^{}\text{ }_v^{}.$$

On the other hand, as observed in 3.2, the coproduct of $`𝔖\mathrm{𝑆𝑦𝑚}`$ can be written as

$$\mathrm{\Delta }(_w)=\underset{p+q=n}{}\underset{u𝔖_p,v𝔖_q}{}\mathrm{\#}\{\zeta 𝔖^{(p,q)}\zeta (u\times v)=w\}_u\text{ }_v.$$

It follows that $`\mathrm{\Theta }`$ is a morphism of coalgebras because

$$w=\zeta (u\times v)w^1=(u^1\times v^1)\zeta ^1.$$

Since $`_u=_{ux}_x`$, we have $`_u^{}=_{xu}_x^{}`$. Therefore,

$`\mathrm{}\text{}`$
$$\mathrm{\Theta }(_u^{})=\underset{xu}{}_{x^1}=\underset{xu}{}\underset{x^1v}{}_v=\underset{v}{}\theta (u,v)_v.$$

Formula (9.2) for the morphism $`\mathrm{\Theta }`$ of Hopf algebras has combinatorial implications which we develop. Recall that $`\alpha ^w(u,v)`$ and $`\kappa (u,w)`$ denote the structure constants of the product and antipode of $`𝔖\mathrm{𝑆𝑦𝑚}`$ in terms of the monomial basis. These integers were described in Theorems 4.1 and 5.5. Consider $`\theta `$, $`\alpha ^w`$, and $`\kappa `$ to be matrices with rows and columns indexed by elements of $`𝔖_n`$.

###### Theorem 9.2.

For any $`u𝔖_p`$, $`v𝔖_q`$, and $`w𝔖_{p+q}`$, we have

* $`(\theta \alpha ^w\theta )(u,v)=\theta (\zeta _{p,q}(u\times v),w)`$ ,
* $`\kappa ^t\theta =\theta \kappa `$.

###### Proof.

By Lemma 2.14, the coproduct of $`𝔖\mathrm{𝑆𝑦𝑚}`$ (3.1) can be written as

$$\mathrm{\Delta }(_w)=\underset{p+q=n}{}\underset{\begin{array}{c}u𝔖_p,v𝔖_q\\ \zeta _{p,q}(u\times v)=w\end{array}}{}_u\text{ }_v,$$

Therefore, the dual product is

$$_u^{}_v^{}=_{\zeta _{p,q}(u\times v)}^{}.$$

Thus, the right hand side of (i) is the coefficient of $`_w`$ in $`\mathrm{\Theta }(_u^{}_v^{})`$. On the other hand, since $`\theta (u,v)=\theta (v,u)`$, we have

$$(\theta \alpha ^w\theta )(u,v)=\underset{x,y𝔖_n}{}\theta (u,x)\alpha ^w(x,y)\theta (y,v)=\underset{x,y𝔖_n}{}\theta (u,x)\theta (v,y)\alpha ^w(x,y).$$

Thus the left hand side of (i) is the coefficient of $`_w`$ in $`\mathrm{\Theta }(_u^{})\mathrm{\Theta }(_v^{})`$. Since $`\mathrm{\Theta }`$ is a morphism of algebras, (i) holds.

The second formula directly expresses that $`\mathrm{\Theta }`$ preserves antipodes, since the antipode of $`(𝔖\mathrm{𝑆𝑦𝑚})^{}`$ is the dual of the antipode of $`𝔖\mathrm{𝑆𝑦𝑚}`$. ∎

One may view Theorem 9.2(i) as a recursion reducing the computation of $`\theta (u,v)`$ to the case when $`u`$ and $`v`$ have no global descents, by virtue of Lemma 2.14. On the other hand, since $`\theta `$ is an invertible matrix, this provides another semi-combinatorial description of the structure constants $`\alpha ^w(u,v)`$.

One may also impose the condition that $`\mathrm{\Theta }`$ preserves coproducts, but this leads again to (i) of Theorem 9.2. On the other hand, the equivalent of (ii) of Theorem 9.2 for the fundamental basis leads to the following non-trivial identity.

###### Proposition 9.3.

For any $`u`$ and $`v𝔖_n`$,

$$\begin{array}{c}\mathrm{\#}\{𝖲[n1]\mathrm{Des}(vu_𝖲)𝖲\text{ and }\mathrm{\#}𝖲\text{ is odd}\}\hfill \\ \hfill +\mathrm{\#}\{𝖲[n1]\mathrm{Des}(uv_𝖲)𝖲\text{ and }\mathrm{\#}𝖲\text{ is even}\}\\ \hfill =\mathrm{\#}\{𝖲[n1]\mathrm{Des}(vu_𝖲)𝖲\text{ and }\mathrm{\#}𝖲\text{ is even}\}\\ \hfill +\mathrm{\#}\{𝖲[n1]\mathrm{Des}(uv_𝖲)𝖲\text{ and }\mathrm{\#}𝖲\text{ is odd}\}.\end{array}$$

###### Proof.

The formula above is equivalent to

(9.3)
$$\lambda (u,v^1)=\lambda (v,u^1),$$

where $`\lambda (,)`$ is the structure constant for the antipode with respect to the fundamental basis, as proven in Theorem 5.4. But (9.3) expresses that $`\mathrm{\Theta }`$ preserves antipodes (on the fundamental basis and its dual). ∎

We turn now to quasi-symmetric functions. The dual $`𝒬\mathrm{𝑆𝑦𝑚}^{}`$ of $`𝒬\mathrm{𝑆𝑦𝑚}`$ is the Hopf algebra of non-commutative symmetric functions of Gelfand, et. al. . It is the free associative algebra with generators $`\{M_{\mathrm{},n}^{}n0\}`$. This statement is dual to formula (1.6) for the coproduct of $`𝒬\mathrm{𝑆𝑦𝑚}`$.

Define numbers

$`b(𝖲,𝖳)`$ $`:=\mathrm{\#}\{u𝔖_n\mathrm{Des}(u)𝖲,\mathrm{Des}(u^1)𝖳\},`$
$`c(𝖲,𝖳)`$ $`:=\mathrm{\#}\{u𝔖_n\mathrm{Des}(u)𝖲,\mathrm{Des}(u^1)𝖳\},`$
$`d(𝖲,𝖳)`$ $`:=\mathrm{\#}\{u𝔖_n\mathrm{Des}(u)=𝖲,\mathrm{Des}(u^1)=𝖳\}.`$
Let $`\mathrm{\Phi }`$ denote the composite

$$𝒬\mathrm{𝑆𝑦𝑚}^{}\stackrel{𝒟^{}}{}(𝔖\mathrm{𝑆𝑦𝑚})^{}\stackrel{\Theta }{}𝔖\mathrm{𝑆𝑦𝑚}\stackrel{𝒟}{}𝒬\mathrm{𝑆𝑦𝑚}.$$

###### Proposition 9.4.

The morphism $`\mathrm{\Phi }:𝒬\mathrm{𝑆𝑦𝑚}^{}𝒬\mathrm{𝑆𝑦𝑚}`$ sends

$$F_𝖲^{}\underset{𝖳𝒬_n}{}d(𝖲,𝖳)F_𝖳\text{ and }M_𝖲^{}\underset{𝖳𝒬_n}{}b(𝖲,𝖳)M_𝖳,$$

for $`𝖲𝒬_n`$.

###### Proof.

Since $`𝒟(_u)=F_{\mathrm{Des}(u)}`$, the dual map satisfies $`𝒟^{}(F_𝖲^{})=_{\mathrm{Des}(u)=𝖲}_u^{}`$. Also, Theorem 7.3 dualizes to $`𝒟^{}(M_𝖲^{})=_{\zeta _𝖲}^{}`$. The descriptions of the composite above follow now from those for $`\mathrm{\Theta }`$ in (9.1) and (9.2), plus that $`\theta (\zeta _𝖲,\zeta _𝖳)=b(𝖲,𝖳)`$, which in turn follows from (2.8). ∎

We now use the fact that $`\mathrm{\Phi }:𝒬\mathrm{𝑆𝑦𝑚}^{}𝒬\mathrm{𝑆𝑦𝑚}`$ is a morphism of Hopf algebras. The image of $`\mathrm{\Phi }`$ is precisely the subalgebra of $`𝒬\mathrm{𝑆𝑦𝑚}`$ consisting of symmetric functions. Since $`𝒬\mathrm{𝑆𝑦𝑚}^{}`$ is generated by $`\{M_{\mathrm{},n}^{}n0\}`$, its image $`\mathrm{\Phi }(𝒬\mathrm{𝑆𝑦𝑚}^{})`$ is generated by $`\mathrm{\Phi }(M_{\mathrm{},n}^{})`$, for $`n0`$. Observe that $`b(\mathrm{},𝖳)=1`$ for every $`𝖳𝒬_n`$ as $`1_n`$ is the only permutation $`u`$ in $`𝔖_n`$ with $`\mathrm{Des}(u)\mathrm{}`$ and $`\mathrm{}=\mathrm{Des}(1_n^1)𝖳`$. Thus

$$\mathrm{\Phi }(M_{\mathrm{},n}^{})=\underset{𝖳𝒬_n}{}M_𝖳=F_{\mathrm{},n}.$$

Formula (1.8) shows that $`F_{\mathrm{},n}`$ is the complete homogeneous symmetric function of degree $`n`$. These generate the algebra of symmetric functions . Thus, $`\mathrm{\Phi }`$ is the *abelianization* map from non-commutative to commutative symmetric functions. We will not use this, but rather the explicit expression of $`\mathrm{\Phi }`$ of Proposition 9.4.

Let $`a^𝖱(𝖲,𝖳)`$ denote the structure constants of the product of $`𝒬\mathrm{𝑆𝑦𝑚}`$ with respect to its monomial basis. These integers are combinatorially described by (1.4) or (7.3). The following analog of Theorem 9.2 provides a recursion for computing the numbers $`b(𝖲,𝖳)`$ in terms of the structure constants $`a^𝖱(𝖲,𝖳)`$. We view $`a^𝖱`$ and $`b`$ as matrices with entries indexed by subsets of $`[n1]`$.

###### Proposition 9.5.

For any $`𝖲[p1]`$, $`𝖳[q1]`$, and $`𝖱[p+q1]`$,

(9.4)
$$(ba^𝖱b)(𝖲,𝖳)=b(𝖲\{p\}(p+𝖳),𝖱).$$

###### Proof.

The dual of the coproduct of $`𝒬\mathrm{𝑆𝑦𝑚}`$ (1.6) is

$$M_𝖲^{}M_𝖳^{}=M_{𝖲\{p\}(p+𝖳)}^{}.$$

Thus, the right hand side of (9.4) is the coefficient of $`M_𝖱`$ in $`\mathrm{\Phi }(M_𝖲^{}M_𝖳^{})`$. On the other hand, since $`b(𝖲,𝖳)=b(𝖳,𝖲)`$, we have

$$(ba^𝖱b)(𝖲,𝖳)=\underset{𝖲^{},𝖳^{}}{}b(𝖲,𝖲^{})a^𝖱(𝖲^{},𝖳^{})b(𝖳^{},𝖳)=\underset{𝖲^{},𝖳^{}}{}b(𝖲,𝖲^{})b(𝖳,𝖳^{})a^𝖱(𝖲^{},𝖳^{}).$$

Thus the left hand side of (9.4) is the coefficient of $`M_𝖱`$ in $`\mathrm{\Phi }(M_𝖲^{})\mathrm{\Phi }(M_𝖳^{})`$. Since $`\mathrm{\Phi }`$ is a morphism of algebras, (9.4) holds. ∎

Expressing that $`\mathrm{\Theta }`$ preserves the antipode in terms of the fundamental basis and its dual gives a result of Foata and Schützenberger , which Gessel obtained in his original work on quasi-symmetric functions by other means \[13, Corollary 6\] (Equation (iv) in the following corollary). For $`𝖲[n1]`$, define

$`𝖲^c`$ $`=\{i[n1]i𝖲\}`$
$`\stackrel{~}{𝖲}`$ $`=\{i[n1]ni𝖲\}.`$
###### Corollary 9.6.

For $`𝖲,𝖳[n1]`$, the numbers $`d(𝖲,𝖳)`$ satisfy

* $`d(𝖲,𝖳)=d(𝖳,𝖲)`$ ,
* $`d(𝖲,𝖳)=d(\stackrel{~}{𝖲},\stackrel{~}{𝖳})`$ ,
* $`d(𝖲,𝖳)=d(𝖲^c,𝖳^c)`$ , and
* $`d(𝖲,𝖳)=d(\stackrel{~}{𝖲},𝖳)`$.

###### Proof.

The symmetry (i) follows by considering the bijection $`uu^1`$. Similarly, (ii) follows by considering the bijection $`u\omega _nu\omega _n^1`$, where $`\omega _n=(n,\mathrm{}2,1)`$, as it is easy to see that $`\mathrm{Des}(\omega _nu\omega _n^1)=\stackrel{~}{\mathrm{Des}(u)}`$.

The antipode of $`𝒬\mathrm{𝑆𝑦𝑚}`$ is \[22, corollaire 4.20\]

$$S(F_𝖳)=(1)^nF_{\stackrel{~}{𝖳}^c}.$$

Since $`\mathrm{\Phi }`$ preserves antipodes, its explicit description in Proposition 9.4 implies that $`d(\stackrel{~}{𝖲}^c,𝖳)=d(𝖲,\stackrel{~}{𝖳}^c)`$. Together with (ii) this yields (iii).

Finally, to deduce (iv), consider the bijection $`u\omega _nu`$. Note that $`\mathrm{Des}(\omega _nu)=\mathrm{Des}(u)^c`$. Therefore

$$\mathrm{Des}((\omega _nu)^1)=\mathrm{Des}(\omega _n\omega _nu^1\omega _n^1)=\mathrm{Des}(\omega _nu\omega _n^1)^c=\stackrel{~}{\mathrm{Des}(u^1)}^c.$$

This shows that $`d(𝖲,𝖳)=d(𝖲^c,\stackrel{~}{𝖳}^c)`$. Together with (ii) and (iii) this gives (iv). ∎

Expressing the preservation of the antipode under $`\mathrm{\Phi }`$ in terms of monomial quasi-symmetric functions and their duals gives further, similar results.

###### Proposition 9.7.

The map $`S\mathrm{\Phi }=\mathrm{\Phi }S^{}:𝒬\mathrm{𝑆𝑦𝑚}^{}𝒬\mathrm{𝑆𝑦𝑚}`$ sends

$$M_𝖲^{}(1)^n\underset{𝖱}{}c(𝖲,\stackrel{~}{𝖱}^c)M_𝖱=(1)^n\underset{𝖱}{}c(𝖱,\stackrel{~}{𝖲}^c)M_𝖱.$$

Therefore,

$$c(𝖲,\stackrel{~}{𝖱}^c)=c(𝖱,\stackrel{~}{𝖲}^c).$$

###### Proof.

We will show that $`S\mathrm{\Phi }(M_𝖲^{})=(1)^n_𝖱c(𝖲,\stackrel{~}{𝖱}^c)M_𝖱`$. One shows similarly that $`\mathrm{\Phi }S^{}(M_𝖲^{})=(1)^n_𝖱c(𝖱,\stackrel{~}{𝖲}^c)M_𝖱`$.

As mentioned in (1.7), the antipode of $`𝒬\mathrm{𝑆𝑦𝑚}`$ is

$$S(M_𝖳)=(1)^{\mathrm{\#}𝖳+1}\underset{𝖱𝖳}{}M_{\stackrel{~}{𝖱}}.$$

Combining this with Proposition 9.4 shows that $`S\mathrm{\Phi }`$ sends

$$M_𝖲^{}\underset{𝖳}{}b(𝖲,𝖳)(1)^{\mathrm{\#}𝖳+1}\underset{𝖱𝖳}{}M_{\stackrel{~}{𝖱}}.$$

Thus, we have to show that for each $`𝖲`$ and $`𝖱`$,

$$\underset{𝖱𝖳}{}(1)^{\mathrm{\#}𝖳+1}b(𝖲,𝖳)=(1)^nc(𝖲,𝖱^c).$$

Now,

$`{\displaystyle \underset{𝖱𝖳}{}}(1)^{\mathrm{\#}𝖳+1}b(𝖲,𝖳)`$ $`={\displaystyle \underset{𝖱𝖳}{}}{\displaystyle \underset{𝖳^{}𝖳}{}}(1)^{\mathrm{\#}𝖳+1}\mathrm{\#}\{u\mathrm{Des}(u)𝖲,\mathrm{Des}(u^1)=𝖳^{}\}`$
$`={\displaystyle \underset{𝖳^{}}{}}\mathrm{\#}\{u\mathrm{Des}(u)𝖲,\mathrm{Des}(u^1)=𝖳^{}\}{\displaystyle \underset{𝖱𝖳^{}𝖳}{}}(1)^{\mathrm{\#}𝖳+1}`$
$`={\displaystyle \underset{𝖳^{}:𝖱𝖳^{}=[n1]}{}}(1)^n\mathrm{\#}\{u\mathrm{Des}(u)𝖲,\mathrm{Des}(u^1)=𝖳^{}\}`$
$`=(1)^n\mathrm{\#}\{u\mathrm{Des}(u)𝖲,\mathrm{Des}(u^1)𝖱=[n1]\}`$
$`=(1)^n\mathrm{\#}\{u\mathrm{Des}(u)𝖲,\mathrm{Des}(u^1)𝖱^c\}`$
$`=(1)^nc(𝖲,𝖱^c).`$
For completeness, we include the consequences on the numbers $`b`$ and $`c`$ that follow. Note that these also follow directly from

$$b(𝖲,𝖳)=\underset{\begin{array}{c}S^{}𝖲\\ T^{}𝖳\end{array}}{}d(𝖲,𝖳)\text{ and }c(𝖲,𝖳)=\underset{\begin{array}{c}S^{}𝖲\\ T^{}𝖳\end{array}}{}d(𝖲,𝖳).$$

###### Corollary 9.8.

For any $`𝖲`$, $`𝖳[n1]`$,

* $`b(𝖲,𝖳)=b(𝖳,𝖲)`$,
* $`b(𝖲,𝖳)=b(\stackrel{~}{𝖲},\stackrel{~}{𝖳})`$, and $`c(𝖲,𝖳)=c(\stackrel{~}{𝖲},\stackrel{~}{𝖳})`$,
* $`c(𝖲,𝖳)=c(𝖳^c,𝖲^c)`$,
* $`b(𝖲,𝖳)=b(\stackrel{~}{𝖲},𝖳)`$, and $`c(𝖲,𝖳)=c(\stackrel{~}{𝖲},𝖳)`$.