Abstract
Many related products and coproducts (e.g. Hadamard, Cauchy, Kronecker, induction, internal, external, Solomon, composition, Malvenuto–Reutenauer, convolution, etc.) have been defined in the following objects: species, representations of the symmetric groups, symmetric functions, endomorphisms of graded connected Hopf algebras, permutations, non-commutative symmetric functions, quasi-symmetric functions, etc. With the purpose of simplifying and unifying this diversity we introduce yet, another product the Heisenberg product, that is not graded and its highest and lowest degree-terms are the classical external and internal products (and their namesakes in different contexts). In order to define it, we start from the two opposite more general extremes: species in the “commutative context”, and endomorphisms of Hopf algebras in the “non-commutative” environment. Both specialize to the space of commutative symmetric functions where the definitions coincide. We also deal with the different coproducts that these objects carry, to which we add the Heisenberg coproduct for quasi-symmetric functions, and study their Hopf algebra compatibility particularly for symmetric and non commutative symmetric functions. We obtain combinatorial formulas for the structure constants of the new product that extend, generalize and unify results due to Garsia, Remmel, Reutenauer and Solomon. In the space of quasi-symmetric functions, we describe explicitly the new operations in terms of alphabets.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
1.1 General description of the paper
The diagram in Fig. 1 displays the array of spaces we consider in this work and the table in Table 1 displays the variety of products that had been therein defined and given due consideration by many authors.
In all these levels we define a new product, that we call the Heisenberg product that is not graded and that at the smallest and largest degrees produce respectively the internal and external products (or their namesakes as depicted in Table 1). This is what we call the interpolation property of the Heisenberg product.
The name we choose for the new product, comes from the one that it usually carries at the level of Hopf algebras.
Relation among the spaces where the Heisenberg structure is introduced
Observe that we divided the spaces into three groups, marked with different kinds of boxes in the diagram. In the first group, marked with square boxes, we start by constructing the Heisenberg product in the category of species, or equivalently of representations of the symmetric groups and we translate it to the space of symmetric functions. The definition at the level of species is extremely simple (see Definition 1) and based on the decomposition of a set I in all possible manners as a union (not necessarily disjoint) of a couple of subsets. The theories of species and of representations of symmetric groups are equivalent, and this allows the translation of the product from the first category to the second. The language of species being cleaner, is probably the reason the Heisenberg product, that becomes more akward (Definition 9) for representations, was not discovered before by representation theorists. We use the Grothendieck group functor and the Frobenius characteristic map to move from categories to symmetric functions. This work is covered in Sects. 2 and 3. In the space of symmetric functions we give an explicit combinatorial formula for the Heisenberg product in the linear basis of the complete homogeneous symmetric functions. Later this formula will be the main tool used to relate the commutative with the non commutative environment in Sect. 8. We also find an explicit formula for the structure constants of the Heisenberg product in the basis of power sums. The existence of these simple formulæ poses the problem of finding an explicit description for the structure constants on the basis of Schur functions. The answer would contain as extreme cases the Littlewood-Richardson rule and (a still unknown) rule for the Kronecker coefficients.
In the second group, marked with oval boxes, we start by considering the Heisenberg product in the space of endomorphisms of a graded Hopf algebra in Sect. 4. This product comes from the theory of Hopf algebras and has recently been interpreted in terms of mixed wreaths (a variation of mixed distributive laws) in [29]. In Sect. 6 we restrict it, via Schur–Weyl duality, to the vector space linearly generated by permutations, on one side, and on the other side to what we define as the space of descents (or Garsia–Reutenauer) endomorphisms of a Hopf algebra in Sect. 5. These two constructions are confluent when we restrict both to the space of non-commutative symmetric functions in Sect. 7. Moreover, in this section we present two different proofs of the restriction of the Heisenberg product to the space of descents (non commutative symmetric functions), and also suggest two others, relating to work of Brown, Mahajan, Schocker and others. The first proof follows along the lines of results of Garsia and Reutenauer characterizing the descents via Schur–Weyl duality. In this perspective, the invariance of the space of descents within the space of permutations with respect to the Heisenberg product, becomes a result in Hopf algebra theory. The second proof that has a combinatorial content is based upon an explicit calculation of the Heisenberg product of elements of the canonical basis \(X_\alpha \), where \(\alpha \) is a composition.Footnote 1 By the interpolation property of the Heisenberg product, the combinatorial formula thus obtained, contains as special cases rules for the product in Solomon’s descent algebra and for the external product of two basis elements of \(\Sigma \). One readily verifies that the former is precisely the well-known rule of Garsia, Remmel, Reutenauer, and Solomon, and the latter is just the usual formula for the external product of the basic elements of the space of descents. In that manner, the apparently disconnected combinatorial descriptions of two different products: the Solomon and the external product, become connected by the introduction of the new Heisenberg product.
The square boxes and the oval boxes have as common ground the bold square box that contains the space of symmetric functions. We show in Sect. 8 that via the usual projection of non-commutative symmetric functions onto symmetric functions the two definitions of Heisenberg product coincide in the latter space . This, and the formal similarity of the constructions, justifies the use of the same name in both contexts.
Moreover, the spaces of non-commutative and commutative symmetric functions carry a well-known coalgebra structure. We show that this structure is compatible with the Heisenberg product, producing in both cases related Hopf algebras. This appears in Sects. 9 and 10.
Finally, the remaining vector space appearing in Table 1, is the space of quasi-symmetric functions, which is dual to the space of non-commutative symmetric functions. We construct by means of this duality, the Heisenberg coproduct in quasi-symmetric functions in Sect. 11. In this situation, this coproduct together with the usual product, endow the quasi-symmetric functions with a Hopf algebra structure.
In the “Appendix”, we present the proofs of three technical lemmas, that in order to spare the reader of some nonessential distractions, were omitted in the places that the statements appeared.
1.2 Terminology and general notations
In all the spaces we consider there are at least two well-known products. Although they are closely related by the inclusions, projections, and isomorphisms in Fig. 1, mathematical developments have given them non-consistent names in many cases.
Table 1 shows the more standard nomenclature.
The new product we introduce in this article, will be called in all the different contexts, the Heisenberg product.
We work over a field of characteristic zero, that will be denoted by \(\Bbbk \).
When dealing with results in Hopf algebra theory, we adopt the usual notations in the area as presented for example in [22]. We adopt Sweedler’s convention for the comultiplication and write \(\Delta (h)=\sum h_1 \otimes h_2\), moreover S in general will be the antipode. An element of the Hopf algebra is said to be primitive if \(\Delta (h)=h\otimes 1 + 1 \otimes h\). The space of primitive elements is denoted as \({\text {Prim}}(H)\).
The group of the permutations of n elements will be denoted as \(S_n\), \([n]:=\{1,\ldots ,n\}\) and a permutation \(\sigma :[n] \rightarrow [n]\) frequently will be written in word format as: \(\sigma (1),\ldots ,\sigma (n)\).
If \((a_1,\ldots ,a_r)\) is a composition of n we write \((a_1,\ldots ,a_r)\models n\). If we allow some of the elements \(a_i\) to be zero, we call it a weak composition or a pseudo composition. Two compositions with the same elements but in a different order are considered as different compositions but the same partition.
For the basic notations and results in the theory of representations of symmetric groups we refer the reader to Zelevinski’s [33].
2 Part 1. The commutative context
3 The Heisenberg product of species
We introduce the notion of Heisenberg product of two species, generalizing the ordinary Cauchy and Hadamard products. We follow the notation and terminology of [1] and [4].
Let \(\mathsf {set^{\times }}\) be the category of finite sets with bijections among them as morphisms. Let \(\mathbf {Vect}\) or \(\mathbf {Vect}_\Bbbk \) be the category of vector spaces over a fixed field.
For a more general approach to this subject see [30] and Remark 2.4.
Definition 2.1
The category of species, denoted as \(\mathbf {Sp}\), is the abelian category of functors from \(\mathsf {set^{\times }}\) into \(\mathbf {Vect}\): \(\mathbf {Sp}= \mathbf {Vect}^{\mathsf {set^{\times }}}\), with abelian structure induced by that of \(\mathbf {Vect}\). A functor \(\mathsf {p}:\mathsf {set^{\times }}\rightarrow \mathbf {Vect}\) of \(\mathbf {Sp}\) is called a species. The elements of \(\mathbf {Sp}(\mathsf {p},\mathsf {q})\) (the morphisms of \(\mathbf {Sp}\)), are the natural transformations between \(\mathsf {p}\) and \(\mathsf {q}\). The evaluation of the species \(\mathsf {p}\) over a set I is a vector space denoted as \(\mathsf {p}[I]\), and for a bijection f the effect of the species \(\mathsf {p}\) is denoted as \(\mathsf {p}[f]\). The image of the set \([n] = \{1,2,\ldots , n\}\) is written, for simplicity, \(\mathsf {p}\bigl [ [n] \bigr ] = \mathsf {p}[n]\), and by convention \(\mathsf {p}[0]=\mathsf {p}[\emptyset ]\).
For future reference we consider the following species:
-
(1)
The species one \(\mathsf {i}\): \(\mathsf {i}[\emptyset ]=\Bbbk \) and \(\mathsf {i}[I]=0\) for \(I\ne \emptyset \),
-
(2)
The exponential species \(\mathsf {e}\): \(\mathsf {e}[I]=\Bbbk \) for all I.
Definition 2.2
The Heisenberg product of species is the functor \({{\mathrm{\#}}}:\mathbf {Sp}\times \mathbf {Sp}\rightarrow \mathbf {Sp}\) given by:
Given two finite sets I and J, and a bijection \(f:I\rightarrow J\), we obtain a bijection \((S,T) \mapsto \bigl ( f(S), f(T) \bigr )\) between pairs (S, T) with \(I=S\cup T\), and pairs \((S',T')\) with \(J=S'\cup T'\). The map \((\mathsf {p}{{\mathrm{\#}}}\mathsf {q})[f]: (\mathsf {p}{{\mathrm{\#}}}\mathsf {q})[I] \rightarrow (\mathsf {p}{{\mathrm{\#}}}\mathsf {q})(J)\), induced by the maps
defines \(\mathsf {p}{{\mathrm{\#}}}\mathsf {q}\) for arrows. Hence, \(\mathsf {p}{{\mathrm{\#}}}\mathsf {q}\in \mathbf {Sp}\).
This definition involves in particular two special situations: the case of the Cauchy product and of the Hadamard product of species.
Indeed, consider the two “limit” situations in terms of the size of the intersection \(S \cap T\) in the above sum:
where the symbol \(S\sqcup T\) stands for the disjoint union of S and T.
Since we can write:
we say informally that the Heisenberg product “interpolates” between the Cauchy product \(\mathsf {p}{{\mathrm{\cdot }}}\mathsf {q}\) and the Hadamard product \(\mathsf {p}{{\mathrm{\times }}}\mathsf {q}\).
The triples \((\mathbf {Sp},{{\mathrm{\cdot }}}, \mathsf {i})\) and \((\mathbf {Sp},{{\mathrm{\times }}}, \mathsf {e})\), endowed with the obvious associative constraint, are additive monoidal categories with \(\mathsf {i}\) and \(\mathsf {e}\) as unit objects.
In the next theorem we present a generalization of this fact proving that \((\mathbf {Sp}, {{\mathrm{\#}}}, \mathsf {i})\) is also monoidal and additive.
Theorem 2.3
The functor \({{\mathrm{\#}}}:\mathbf {Sp}\times \mathbf {Sp}\rightarrow \mathbf {Sp}\), together with the natural associativity constraint and with the unit object \(\mathsf {i}\), endows the category \(\mathbf {Sp}\) with an additive monoidal structure.
Proof
Let \(\mathsf {p}\), \(\mathsf {q}\), and \(\mathsf {r}\) be three species. We prove that \(\bigl ((\mathsf {p}{{\mathrm{\#}}}\mathsf {q}) {{\mathrm{\#}}}\mathsf {r}\bigr )[I] = \bigl (\mathsf {p}{{\mathrm{\#}}}(\mathsf {q}{{\mathrm{\#}}}\mathsf {r}) \bigr ) [I] \) for all finite sets I.
We have
which implies that (2) and (3) coincide. From the definition (1) it is clear that \(\mathsf {p}{{\mathrm{\#}}}\mathsf {i}= \mathsf {i}{{\mathrm{\#}}}\mathsf {p}= \mathsf {p}\). \(\square \)
Remark 2.4
In [30], R. Street, lifts the classical \(\lambda \)-weighted Hurwitz products (see [13]), from algebras to the category of \({\mathcal {V}}\)-valued Joyal species for a convenient family of categories \({\mathcal {V}}\). In this context the weight is a set \(\Lambda \) and the particular casesof Hadamard, Heisenberg and Cauchy products appear for \(\Lambda =\infty \,,\,1\) and 0 respectively.
In addition to the relation via interpolation of the Cauchy, Hadamard and Heisenberg products, they are also related by a natural isomorphism:
The required isomorphism (4) appears naturally when we evaluate each side on a finite set I. We have:
and clearly both spaces are naturally isomorphic.
3.1 The Heisenberg product of representations of the symmetric group
The content of the theory of species and of the more classical theory of representations of the symmetric group are essentially the same even though the languages are different (see for example [4]). Using the equivalence of the categories, we translate the Heisenberg product to the category of representations.
Therefore, we obtain an associative product at the level of the representations of the symmetric groups, which interpolates between the Kronecker and the induction product.
Let \({\text {Rep}}(S_n)\) be the category whose objects are finite dimensional representations of \(S_n\) and whose morphisms are \(S_n\)-module homomorphisms. We consider the category
Theorem 2.5
[4] The functor \(\mathcal {F}:\mathbf {Sp}\rightarrow \mathbf {R}\) given by
is an equivalence of abelian categories. The action of the permutation group \(S_n\) in the space \(\mathsf {p}[n]\) is given by \(\sigma \cdot x=\mathsf {p}[\sigma ](x)\).
Using the functor \(\mathcal {F}\) we can express the Heisenberg product in terms of representations. The explicit construction uses the induction and restriction of representations to certain subgroups defined as follows.
Let p, q be non-negative integers. Given permutations \(\sigma \in S_p\) and \(\tau \in S_q\), let \(\sigma \times \tau \in S_{p+q}\) be the permutation
This operation gives an embedding of \(S_p\times S_q\) into \(S_{p+q}\) called the parabolic embedding.
Let n be an integer satisfying \(\max (p,q)\le n\le p+q\). Define the set \(S_p\times _nS_q=S_{n-q} \times S_{p+q-n} \times S_{n-p}\), and consider the embeddings
Definition 2.6
The Heisenberg product of representations is the functor \({{\mathrm{\#}}}: \mathbf {R}\times \mathbf {R}\rightarrow \mathbf {R}\) defined for \(V\in {\text {Rep}}(S_p)\) and \(W\in {\text {Rep}}(S_q)\) as
Let \((V{{\mathrm{\#}}}W)_n\) denote the component of degree n in (9) and the top component, that is, when \(n=p+q\). In this case, the embedding (8) is the identity and (7) is the standard parabolic embedding \(S_p \times S_q \hookrightarrow S_{p+q}\). Then, we have that:
which is the usual induction product of representations [10, 33].
On the other hand, when \(n=p=q\), the embedding (7) is the identity and (8) is the diagonal embedding \(S_n \hookrightarrow S_n\times S_n\). Therefore,
which is the Kronecker product of representations [10, 33].
The Heisenberg product contains terms of intermediate degrees between \(\max (p,q)\) and \(p+q\); in this sense it “interpolates” between the Kronecker and induction products. It is a remarkable fact that, as the Kronecker and induction products, the Heisenberg product is associative.
Moreover, it can be lifted to other settings (permutations, non-commutative symmetric functions, and dually, quasi-symmetric functions) and for all the instances of our construction of the new product, these properties hold.
The next theorem proves that the operation defined in (9) is the translation of the Heisenberg product in species defined in (1). Note that although the functor \(\mathcal {F}\) is an equivalence of categories, the language of species is considerably cleaner than the language of representations. The lengthy verifications in Theorem 2.7 ilustrate this claim.
Theorem 2.7
The Heisenberg product of representations endows \(\mathbf {R}\) with an additive monoidal structure with unit objet the following representation that is denoted as \(\mathsf {i}\): \(\Bbbk \) in degree zero and zero elsewhere. Moreover, the functor \(\mathcal {F}\) given in Theorem 2.5 is monoidal, i.e.
for species \(\mathsf {p}\) and \(\mathsf {q}\).
Proof
It is enough to verify that the Heisenberg product of representations defined by (9) satisfies (10), since \(\mathcal {F}\) is already an equivalence of categories and \(\mathbf {Sp}\) is a tensor category with the Heisenberg product and with unit \(\mathsf {i}\).
Fix i, j, and n, three non-negative integers such that \(\max (i,j)\le n\le i+j\). We claim that we have an isomorphism in \(\mathbf {R}\):
Once this isomorphism is established, taking the direct sum over i and j, we obtain the n-th coordinate of \(\mathcal {F}(\mathsf {p}{{\mathrm{\#}}}\mathsf {q})\) in the left hand side, and the n-th coordinate of the product \(\mathcal {F}(\mathsf {p}){{\mathrm{\#}}}\mathcal {F}(\mathsf {q})\) on \(\mathbf {R}\) in the right hand side.
The following fact can be proved easily. Let A and B be finite totally ordered sets. Given decompositions \(A=A_1\sqcup \dots \sqcup A_n\) and \(B=B_1\sqcup \dots \sqcup B_n\), with \({\#}A_i={\#}B_i\) for \(i=1,\dots ,n\), there is only one bijection \(f:A\rightarrow B\) such that \(f(A_i) = B_i\) and \(f_i = f_{|_{A_i}}:A_i\rightarrow B_i\) is increasing, for all \(i=1,\dots ,n\). We call f the canonical bijection between A and B induced by the partitions.
To establish the isomorphism we consider the following definitions. Given S and T such that \([n]=S\cup T\), let \(S'=S\setminus T\) and \(T'=T\setminus S\). If \({\#}S=i\) and \({\#}T=j\), then let \(f_{S,T}:[n]\rightarrow [n]\) be the canonical bijection induced by the following partitions of [n]:
and let \(f_{S'}\), \(f_{S\cap T}\), and \(f_{T'}\), be the restriction to the corresponding subsets. From the monotonicity conditions for \(f_{S,T}\), we get that \(f_{S,T}^{-1}\) belongs to \(S_i\times _nS_j\).
We consider the standard identification of the induction module \({\text {Ind}}_H^G(V)\) with the tensor product \(\Bbbk G\otimes _{\Bbbk H} V\). Let \(u\in \mathsf {p}[S]\) and \(v\in \mathsf {q}[T]\), and define the map
and extend it to the direct sum in (11).
For a permutation \(\sigma \in S_n\), the action of \(\sigma \) in \(u\otimes v\) is, according to Theorem 2.5,
Observe that \(\sigma \cdot (u\times v)\in \mathsf {p}\bigl [ \sigma (S) \bigr ] \otimes \mathsf {q}\bigl [ \sigma (T) \bigr ]\). The application of the map \(\psi \) yields
where \( \alpha =\mathsf {p}[ f_{\sigma (S')} \sqcup f_{\sigma (S)\cap \sigma (T)} ] \mathsf {p}[\sigma _{|_S}] \) and \( \beta =\mathsf {q}[ f_{\sigma (S)\cap \sigma (T)} \sqcup f_{\sigma (T')} ] \mathsf {q}[\sigma _{|_T}] \). Since we can decompose \(\sigma _{|_S}\) into \(\sigma _{|_S'} \sqcup \sigma _{|_{S\cap T}}\), then by the functoriality of \(\mathsf {p}\) we get that
Let \( \tilde{\sigma }_{S'} \) and \( \tilde{\sigma }_{S\cap T} \) be the only bijections such that the following diagrams commute
We conclude that \(\alpha \) can be rewritten as
and we proceed similarly with \(\beta \).
In accordance with (13) we deduce that:
Note that the permutation \( \tilde{\sigma }_{S'} \sqcup \tilde{\sigma }_{S\cap T} \sqcup \tilde{\sigma }_{T'} \) clearly belongs to \(S_i\times _nS_j\). In Eq. (14), since the tensor product of \(f^{-1}_{\sigma (S),\sigma (T)}\) with \(\alpha (u)\otimes \beta (v)\) is performed with respect to this subgroup, we can move the permutation to the left factor where we get \( f_{\sigma {S},\sigma {T}}^{-1} ( \tilde{\sigma }_{S'} \sqcup \tilde{\sigma }_{S\cap T} \sqcup \tilde{\sigma }_{T'}) = \sigma f_{S,T}^{-1} \). This equality results again from the diagrams (15). This is precisely the definition of the action of \(\sigma \) on the image of the map \(\psi \).
The map \(\psi \) is invertible, since for any element \(\sigma \otimes (x\otimes y)\), we decompose \(\sigma =\xi (\alpha \times \beta \times \gamma )\), where \(\alpha \times \beta \times \gamma \in S_{n-j}\times S_{i+j-n}\times S_{n-i}=S_i\times _n S_j\) and \(\xi \) is increasing in the intervals \([n-j]\), \([n-j+1,i]\), and \([i+1,n]\). Define the disjoint sets
Then, let \(S=A\sqcup B\) and \(T=B\sqcup C\). It is straightforward to find \(u\otimes v\) in \(\mathsf {p}[S]\otimes \mathsf {q}[T]\) such that \(\psi (u\otimes v) = \sigma \otimes (x\otimes y)\). Similarly, this process applied to the image of \(\psi \) in (12) yields back \(u\otimes v\). \(\square \)
3.2 The generating function of the Heisenberg product of two species
The generating function associated to a species \(\mathsf {p}\) is the formal series
The generating series associated to the Cauchy product \(\mathsf {p}{{\mathrm{\cdot }}}\mathsf {q}\) of two species is the usual (Cauchy) product of the power series \(F_\mathsf {p}\) and \(F_\mathsf {q}\). Similarly, the generating series of \(\mathsf {p}{{\mathrm{\times }}}\mathsf {q}\) is the Hadamard product of the generating series of \(\mathsf {p}\) and \(\mathsf {q}\). Explicitly, if \(F_\mathsf {p}(x)=\sum _{n\ge 0}a_n x^n/n!\) and \(F_\mathsf {q}(x)=\sum _{n\ge 0}b_n x^n/n!\), then
The classical names for these operations among formal series justify the names for the Cauchy and Hadamard products of species.
Theorem 2.8
The generating function of the Heisenberg product of two species \(\mathsf {p}\) and \(\mathsf {q}\) is
where
Proof
In the definition of the Heisenberg product of two species [Definition (1)], the pairs of sets (S, T) such that \([n]=S\cup T\), \({\#}S=i\), and \({\#}T=j\), are in bijection with the decompositions \([n]=U\sqcup W\sqcup V\) with \({\#}U + {\#}W = i\) and \({\#}W+{\#}V=j\). Indeed, just take \(U=S\setminus T\), \(V=T\setminus S\), and \(W=S\cap T\). Clearly, we obtain \({\#}U=n-i\), \({\#}V=n-j\), and \({\#}W=i+j-n\). The multinomial coefficient in the formula of \(F_{\mathsf {p}{{\mathrm{\#}}}\mathsf {q}}\) stands precisely for the number of possible ways to choose the decomposition U, V, W. \(\square \)
Remark 2.9
-
(1)
The above expression can be written in a more compact form as:
$$\begin{aligned} F_{\mathsf {p}{{\mathrm{\#}}}\mathsf {q}}(x) = \sum _{n\ge 0} \biggl ( \sum _{r+s+t=n} \left( {\begin{array}{c}n\\ r,s,t\end{array}}\right) a_{s+t}b_{r+t} \biggr ) \frac{x^n}{n!}. \end{aligned}$$The sequence of coefficients of the power series associated to the Heisenberg product, coincides with the so called 1-weighted Hurwitz product of the sequences \(\{a_n:n \ge 0\}\,,\,\{b_n:n \ge 0\}\) (see for example [13]).
-
(2)
The above relationship between the coefficients of the power series of Heisenberg product of the species and the 1-weighted Hurwitz product of the coefficients of the power series of the factors also appears in [30, Proposition 5.1]. See also Remark 2.4 for some general comments about this approach.
4 The Heisenberg product of symmetric functions
4.1 Species, representations of symmetric groups and symmetric functions
In this subsection we recall some basic facts about the relations between species (viewed as such or as representations of the family of all symmetric groups) and the space of symmetric functions.
Let \({\text {K}}(S_n)\) be the Grothendieck group or representation group of the category of finite dimensional \(S_n\)-modules, and call \(\mathcal {K}\) and 
the groups:
Consider the ring of polynomials \(\Bbbk [x_1,\ldots ,x_n]\) in n variables in which the symmetric group \(S_n\) acts by permuting the variables. Call \(\Lambda ^k_n\) the subring consisting the polynomials that are invariant under the action of \(S_n\) and are homogeneous of degree k. When \(m \ge n\), \(\Lambda _m^k\) projects naturally onto \(\Lambda _n^k\) via the homomorphism \(\rho ^k_{m,n}: \Lambda _m^k \rightarrow \Lambda _n^k\) which maps the first n variables to themselves, and the other variables to 0. The space \(\Lambda ^k\) is defined as the inverse limit of the system considered above.
For \(\Lambda ^k\) the space of symmetric functions of degree k, define
called the space of symmetric functions and its completion, respectively (see [19]).
Observe that \(\Lambda \) and \(\widehat{\Lambda }\) are subspaces of \(\Bbbk [x_1,x_2,\cdots ]\) and \(\Bbbk \llbracket x_1,x_2,\cdots \rrbracket \) respectively.
We recall the following definition of special elements in \(\Lambda \).
-
(1)
The elementary symmetric functions are defined by the generating series:
$$\begin{aligned} \sum _{r\ge 0}e_r(x_1,x_2,\ldots )t^r=\prod _{i \ge 1}(1+x_it), \end{aligned}$$ -
(2)
The complete homogeneous symmetric functions are defined by:
$$\begin{aligned} \sum _{r\ge 0}h_r(x_1,x_2,\ldots )t^r=\prod _{i \ge 1}(1-x_it)^{-1}, \end{aligned}$$ -
(3)
The power sums are defined by:
$$\begin{aligned} \sum _{r\ge 0}p_r(x_1,x_2,\ldots )t^r=\sum _{i \ge 1}x_i(1-x_it)^{-1}. \end{aligned}$$
The above defined functions are elements of \(\Bbbk \llbracket x_1,x_2,\ldots \rrbracket \), if we want to consider the corresponding elements in \(\Bbbk [x_1,x_2,\ldots x_n]\) we simply set \(0= x_{n+1}=x_{n+2}=\cdots \).
These, can in turn be defined in terms of the monoidal symmetric functions.
A partition (finite or almost finite) \(\alpha =(a_1,a_2,\ldots )\) with \(a_1 \ge a_2 \ge \cdots \ge 0\) determines a monomial \(x^\alpha =x_1^{a_1} x_2^{a_2} \ldots \).
The monomial symmetric function associated to \(\alpha \) and denoted as \(m_\alpha \) is
where \(\widehat{\alpha }\) stands for a composition and the symbol \(\widehat{\alpha } \leadsto \alpha \) means that the mentioned composition produces the given partition \(\alpha \) by permutation of the entries. For example \(m_{(21)} = \sum _{i \ne j} x_i^2x_j\).
We have the following equalites:
Elementary symmetric functions: \(e_r=m_{(1^r)}\) where \((1^r)\) is the partition of r formed only by 1’s.
Complete homogenous symmetric functions: \(h_r=\sum _{\{\alpha : |\alpha |=r\}} m_\alpha \) where the sum is taken over all the partitions of r.
Power sums: \(p_r=m_{(r)}\), where (r) is the partition \((r,0,0\ldots )\).
For an arbitrary partition \(\alpha =(a_1,a_2,\ldots )\) we define: \(e_\alpha =e_{a_1}e_{a_2}\ldots \), \(h_\alpha =h_{a_1}h_{a_2}\ldots \), \(p_\alpha =p_{a_1}p_{a_2}\ldots \).
When \(\alpha \) runs over all partitions, the set of all functions \(m_\alpha \) forms a \(\mathbb {Z}\)-basis of \(\Lambda \), and the same happens with the sets of the \(e_\alpha \)’s or the set of the \(h_{\alpha }\)’s. The set of the \(p_\alpha \)’s form a \(\mathbb {Q}\)-basis of \(\Lambda _\mathbb {Q}\).
The Frobenius characteristic map is the linear isomorphism
where V is a representation of \(S_n\), \(\mathrm {\chi _{V}}\) its character and \(p_{{\text {cycle}}(\sigma )}\) is the power sum associated to the partition of n defined by the cycle-type of \(\sigma \). The map \({\text {ch}}\) restricts to an isomorphisms of \(\mathcal {K}\) and \(\Lambda \). See [19, Proposition I.7.3] for proofs of the isomorphisms.
The above result, yields another perspective regarding the complete homogeneous symmetric functions.
Indeed, if \(\alpha =(a_1,\ldots ,a_r)\) is a composition of n and
it can be viewed as a subgroup of \(S_n\) by iterating (6). These are the so called parabolic subgroups of \(S_n\). Let \({\mathfrak {h}}_\alpha \) denote the permutation representation of \(S_n\) corresponding to the action by multiplication on the quotient \(S_n/S_\alpha \). The isomorphism class of \({\mathfrak {h}}_\alpha \) does not depend on the order of the parts of \(\alpha \), hence we will consider the representations \({\mathfrak {h}}_\alpha \) for \(\alpha \) running over the partitions of n.
If we denote the trivial \(S_\alpha \)-module by \(\mathbf {1}\) (we omit the dependence on \(\alpha \) for clarity), then the representation \({\mathfrak {h}}_\alpha \) can also be expressed as
The following equality holds \({\text {ch}}({\mathfrak {h}}_\alpha )=h_\alpha \) (see [19, Proposition I.7.3]).
4.2 The Heisenberg product of complete homogeneous symmetric functions
In Sect. 2 and in Sect. 3.1 we have established a path between the objects described in the diagram below:
where the double arrow means the application of the Grothendieck functor \({\text {K}}\).
Using the universal property of the Grothendieck group functor, it is clear that in order to translate the Heisenberg product from \(\mathbf {R}\) to 
it is enough to verify that it is compatible with direct sums.
It is easy to make this verification in the category of species, where the colimits are defined pointwisely as the colimits of vector spaces. Then, the distributive property of the tensor product with respect to direct sums shows that \((\mathsf {p}\oplus \mathsf {q}){{\mathrm{\#}}}\mathsf {r}= (\mathsf {p}{{\mathrm{\#}}}\mathsf {r})\oplus (\mathsf {q}{{\mathrm{\#}}}r)\) for \(\mathsf {p}\,,\mathsf {q}\,,\mathsf {r}\in \mathbf {R}\).
Hence the operation \({{\mathrm{\#}}}\) can be defined in 
, and the subgroup \(\mathcal {K}\) is clearly \({{\mathrm{\#}}}\)-closed since the definition of the Heisenberg product involves only a finite number of summands.
Now, by composition with the Frobenius characteristic isomorphism \({\text {ch}}: \mathcal {K}_\Bbbk \rightarrow \Lambda \), we obtain an associative product on symmetric functions, which we call Heisenberg product of symmetric functions.
The next theorem gives an explicit formula for the Heisenberg product in the linear basis of \(\Lambda \) formed by the complete homogenous symmetric functions. This theorem, besides providing a combinatorial rule useful for computations, will later be used to make the connection with the Heisenberg product of non-commutative symmetric functions in Sect. 8.
In order to express the coefficients of the Heisenberg product of two complete homogenous symmetric functions, we need to define a particular set of plane partitions as follows. Let \(\alpha =(a_1,\ldots ,a_r)\vDash p\) and \(\beta =(b_1,\ldots ,b_s)\vDash q\) be two compositions and n an integer with \(\max (p,q)\le n\le p+q\). Let \(a_0=n-p\), \(b_0=n-q\), and let \(\mathcal {M}_{\alpha ,\beta }^n\) be the set of all \((s+1)\times (r+1)\)-matrices
with non-negative integer entries and such that
-
the sequence of column sums is \((a_0,a_1,\ldots ,a_r)\),
-
the sequence of row sums is \((b_0,b_1,\ldots ,b_s)\),
-
the first entry is \(m_{00}=0\).
We illustrate these conditions as follows:
Let p(M) be the partition of n whose parts are the non-zero \(m_{ij}\).
Theorem 3.1
There is an associative product \({{\mathrm{\#}}}\) in \(\Lambda \), interpolating between the internal and external products, which can be expressed in the basis \((h_\alpha )\) of complete homogeneous functions as
For example, using this theorem we get
where the external product is recognized in the last term and the internal product in the first one, together with additional terms of degrees four and five.
The existence of this operation poses the problem of finding an explicit description for its structure constants on the basis of Schur functions. The answer would contain as extreme cases the Littlewood-Richardson rule and (a still unknown) rule for the Kronecker coefficients.
Proof of Theorem 3.1
We prove that the following formula holds in the category \(\mathbf {R}\):
where the representations \({\mathfrak {h}}_\alpha \) are the induced representations defined in (16). The application of the Grothendieck group functor and the Frobenius characteristic immediately yields (17).
We fix n in the range \(\max (p,q)\le n\le p+q\). The n-summand of \({\mathfrak {h}}_\alpha {{\mathrm{\#}}}{\mathfrak {h}}_\beta \) is, according to (9),
Consider the composition of the first two functors \( {\text {Res}}_{S_p\times _nS_q}^{S_p\times S_q} {\text {Ind}}_{S_\alpha \times S_\beta }^{S_p\times S_q} \) in the right hand side of (9). We use Mackey’s formula to interchange them (see [32]), as follows.
Let \(\Upsilon \subset S_p\times S_q\) be a complete set of representatives of the family of double cosets\( (S_p\times _nS_q) \mathbin {\backslash } (S_p\times S_q) \mathbin {/} (S_\alpha \times S_\beta ) \).
For each \(v\in \Upsilon \), define
The following diagram ilustrates the relative position of these groups and subgroups
In this situation Mackey’s formula reads as the equality
Using the transitivity of the induction functor and the property that it commutes with coproducts we deduce that (18) can be written as
In Lemma 3.2 we construct a bijection \(\upsilon \mapsto M_\upsilon \) between \(\Upsilon \) and \(\mathcal {M}_{\alpha ,\beta }^n\) with the property that \(S_{p(M_\upsilon )}=S_\alpha \times _n^\upsilon S_\beta \). Then (20) becomes
proving the theorem. \(\square \)
Lemma 3.2
In the notations of Theorem 3.1, there is a bijection \(\Upsilon \cong \mathcal {M}_{\alpha ,\beta }^n\) given by \(\upsilon \mapsto M_\upsilon \), such that \( S_{p(M_\upsilon )} = S_\alpha \times _n^\upsilon S_\beta \).
Proof
The proof of this rather technical lemma is postponed until the “Appendix 13.1”. \(\square \)
4.3 Relation with Rota–Stein Cliffordization process
In the articles [25, 26] the authors define what they call the Cliffordization process, that was first carried out to produce the Clifford algebra from the exterior algebra. This process is applied to a general bicommutative Hopf algebra H endowed with an associative operation \((\,| \,): H \otimes H \rightarrow H\) that satisfies the following compatibility conditions that are known under different names in the literature:
-
(1)
\((xy|z)=\sum (x|z_1)(y|z_2)\), \((x|yz)=\sum (x_1|y)(x_2|z)\);
-
(2)
\(\sum (x|y)_1 \otimes (x|y)_2=\sum (x_1|y_1) \otimes (x_2|y_2)\),
valid for all \(x,y \in H\).
In this context, if we call m (denote \(m(x,y)=xy\)) the original product in H, the mentioned authors define the circle product as the convolution \(\circledast =(\,|\,) \star m\) in the space \({\text {End}}(H \otimes H,H)\).
In explicit terms: \(x \circledast y =\sum (x_1|y_1)x_2y_2\) or \(x \circledast y =\sum x_1(x_2|y_1)y_2\) as it is written in [26] and [25]. Recall that the original product and coproduct are commutative. In the above papers the authors prove that \(\circledast \) is an associative product that is compatible with the original comultiplication \(\Delta \). In Theorem 9.2 the same compatibility is proved for the Heisenberg product of non commutative symmetric functions, and hence also for the commutative situation.
A more general construction along similar lines appears in [8]. The authors construct the so called hash products, working in the context of Frobenius Laplace pairings that are defined in the paper by properties related to the conditions (1) and (2) above. In the particular case of the space \(\Lambda \) of commutative symmetric functions, they use the hash (or circle) product to formulate classical character formulæ in a unified framework. In the combinatorial applications they deal for example with the reduced characters of Murnaghan and Littlewood or with what they call Thibon characters: c.f. [17, 18, 24, 31] and compare also with [5].
In the case of the symmetric functions, the circle product and the smash product are the same.
More precisely, recall that the symmetric functions admit a natural coproduct—dual to the external product—that can be defined on the generators of the basis of complete homogeneous symmetric functions as:
Clearly, this coproduct is compatible with the external product. Moreover the corresponding “external” Hopf algebra structure in \(\Lambda \), together with the internal product satisfy the hypothesis of the Cliffordization process as one can easily check working in the basis \(h_\alpha \) for \(\alpha \) a partition.
The identity that follows, that states that the Heisenberg product and the circle product coincide in the above context, was suggested to the authors by A. Zelevinski and does not hold for the space of non-commutative symmetric functions [see comment after Theorem (7.4)]. We present a combinatorial proof of this identity.
Lemma 3.3
(A. Zelevinski) Assume that \(f,g \in \Lambda \), then:
where \(\Delta (f)=\sum f_1\otimes f_2\) and \(\Delta (g)=\sum g_1\otimes g_2\).
Proof
The identity (22) follows from formula (17), by collecting the first row and first column of the matrix M as \((h_\alpha )_1\) and \((h_\beta )_2\), respectively, and the remaining submatrix of M is precisely the internal product of the second component \((h_\alpha )_2\) of the coproduct of \(h_\alpha \) with the first component \((h_\beta )_1\) of the coproduct of \(h_\beta \). \(\square \)
4.4 The Heisenberg product of power sums
The power sums \((p_\lambda )_{\lambda \vdash n, n\ge 0}\) form a linear basis of \(\Lambda \) over \(\mathbb {Q}\). In this subsection we give an explicit formula for the Heisenberg product in this basis.
Given two partitions \(\lambda \) and \(\mu \), denote by \(\lambda \mu \) the concatenation and reordering of \(\lambda \) and \(\mu \). For example, if \(\lambda =(3,2,1,1)\) and \(\mu =(2,2,1)\), then \(\lambda \mu =(3,2,2,2,1,1,1)\).
Theorem 3.4
The Heisenberg product in the basis of power sums can be expressed as
where \(z(\gamma )\) is the order of the stabilizer of the conjugacy class of a permutation of cycle-type \(\gamma \):
being \(m_r\) the number of times r occurs in \(\gamma \).
Proof
The coproduct in the basis of power sums is determined by requiring the functions \(p_n\), with n a non-negative integer, to be primitive elements: \(\Delta (p_n)=1\otimes p_n + p_n\otimes 1\). More explicitly,
Then, formula (22) reads
But \(p_{\alpha _2}{{\mathrm{*}}}p_{\beta _1}=z(\alpha _2)\delta _{\alpha _2,\beta _1}p_{\alpha _2}\), see [19, Chapter I (7.12)]. Since the external product of power sums is done by concatenating the partitions, we obtain the theorem. \(\square \)
As a particular case, assume that \(\lambda \) and \(\mu \) are partitions of n. Note that there is a term in degree n only when \(\lambda =\mu \), otherwise \(\gamma \) would never be the empty partition and the degree of \(p_{\alpha \gamma \beta }\) would be strictly greater than n. Therefore, the only term in degree n is
which is the expression of the internal product in the basis of power sums.
On the other hand for any partitions \(\lambda \) and \(\mu \), when \(\gamma \) is the empty partition, we obtain the term of largest degree, namely \(p_{\alpha \beta }\), since \(z(\gamma )=1\) in this case. This gives the external product \(p_\lambda {{\mathrm{\cdot }}}p_\mu = p_{\lambda \mu }\).
Note that the coefficients of Formula (23) in the basis of power sums are not necessarily the numbers \(z(\gamma )\). Indeed, the partition \(\lambda \) may be decomposed, in general, in more than one way as \(\lambda =\alpha \gamma \), since the operation of concatenation of partitions involves a reordering of the final result. For example, let \((1^n)\) be the partitions with n parts equal to 1. Then,
In this case, the partitions of Formula (23) are \(\alpha =(1^{n-v})\), \(\beta =(1^{n-u})\), and \(\gamma =(1^{u+v-n})\). The number of possible decompositions of \((1^u)\) into two partitions of length \(n-v\) and \(u+v-n\) is \(\left( {\begin{array}{c}u\\ n-v\end{array}}\right) \), and the same argument for \((1^v)\) yields the second binomial coefficient. The remaining factor of the coefficient is \(z(\gamma )=z\bigl ((1^{u+v-n})\bigr ) = (u+v-n)!\), according to Formula (24).
From the explicit expression \(h_{(n)}(x)=\sum x_{i_1}^{a_1}x_{i_2}^{a_2}\cdots x_{i_k}^{a_k}\) (where \((a_1,\ldots ,a_k)\) ranges over all possible permutations of the parts of \(\alpha =(\ell _1,\ldots ,\ell _k)\) for all partitions \(\alpha \) of n), it is clear that \(h_{(1^u)}=p_{(1^u)}\). Hence, Formula (25) can also be deduced from Theorem (3.1). We use this method in (44) for non-commutative symmetric functions.
5 Part 2. The non-commutative context
6 The Heisenberg product of endomorphisms
Let \((H,m,\Delta ,\iota ,\varepsilon ,S)\) be an arbitrary Hopf algebra, where \(m:H\otimes H\rightarrow H\) is the product, \(\Delta :H\rightarrow H\otimes H\) is the coproduct, \(\iota :\Bbbk \rightarrow H\) is the unit, \(\varepsilon :H\rightarrow \Bbbk \) is the counit, and \(S:H\rightarrow H\) is the antipode. The space \({\text {End}}(H)\) of linear endomorphisms of H carries several associative products. Let \(f,g\in {\text {End}}(H)\). Composition and convolution are respectively defined by the diagrams:
Definition 4.1
The Heisenberg product of endomorphisms, denoted as \(f {{\mathrm{\#}}}g\), for \(f,g \in {\text {End}}(H)\), is defined by the diagram:
where the map \({\mathrm {cyclic}}:H^{\otimes 3}\rightarrow H^{\otimes 3}\) is \(x\otimes y\otimes z\mapsto y\otimes z\otimes x\). The associativity of the Heisenberg product follows from the Hopf algebra axioms and its unit is the map \(\iota \varepsilon \).
In explicit terms one has:
We call \({\text {End}}_f(H)\) the subspace of \({\text {End}}(H)\) of finite rank linear homomorphisms, i.e. the image of the canonical inclusion \(H^*\otimes H\hookrightarrow {\text {End}}(H)\). It is clear that the three above operations restrict to \({\text {End}}_f(H)\) and that for the linear generators of \({\text {End}}_f(H)\) the Heisenberg product takes the following form: \(\alpha |h \# \beta |\ell = \sum \alpha (h_1 \rightharpoonup \beta )|h_2\ell \), where \((\alpha |h)(h')=\alpha (h')h\) for \(\alpha \in H^*,\,h,\,h'\in H\). It is also clear that if H is finite dimensional \({\text {End}}_f(H)={\text {End}}(H)\) is endowed with a coproduct given by the tensor products of the coproducts in \(H^*\) and H. This coproduct, is compatible with the convolution product but not with the others.
Remark 4.2
The Heisenberg product appears in the literature in different settings (see for example [22]). Given a Hopf algebra H and a H-module algebra A, the Heisenberg product is defined as the operation on the space \(A\otimes H\) given as:
If \(A=H^*\) and H acts on A by translations then (29) corresponds to (27) via the canonical inclusion \(H^*\otimes H\hookrightarrow {\text {End}}(H)\). Note that in the definition of the Heisenberg product in \({\text {End}}(H)\) there are no restrictions about the dimensions.
6.1 The case of K-equivariant endomorphisms
We need an equivariant version of the above construction.
Assume that K is another bialgebra and that H is a K-module bialgebra: H is endowed with a left action of the algebra K, if \(k \in K\) on \(h \in H\) the action is denoted as \((k,h)\mapsto k\cdot h: K \times H \rightarrow H\). We have that for all \(k \in K\) and \(h,\ell \in H\), \(\Delta (k\cdot h)= \sum k_1\cdot h_1 \otimes k_2 \cdot h_2\) and \(k\cdot (h\ell )=\sum (k_1\cdot h)(k_2 \cdot \ell )\).
The action of K on H, induces a right action of K on \(H^*\) via the formula: \(\alpha \in H^*\), \(h \in H\), \(k \in K\), \((\alpha \leftharpoonup k)(h) = \alpha (k \cdot h)\). With respect to this action and if H is finite dimensional, \(H^*\) becomes a right K-module bialgebra. In general \(H^*\) is only a K-module algebra.
Definition 4.3
Assume that H is a K-module bialgebra for a certain Hopf algebra K. We define an action of K on \({\text {End}}(H)\) as follows: if \(k \in K\) and \(f \in {{\text {End}}}(H)\), \((k\cdot f)(h) = \sum k_1\cdot f(S(k_2)h)\), where \(S:K \rightarrow K\) denotes the antipode. Explictly, the action on the generators of \({\text {End}}_f(H)\) is the following: for \(\alpha |h \in {{\text {End}}_f}(H)\) and \(k \in K\): \(k \cdot (\alpha |h)= \sum (\alpha \leftharpoonup Sk_2)| k_1 \cdot h\).
Remark 4.4
-
(1)
The K-invariant elements for this action, i.e. the elements \(f \in {{\text {End}}}(H)\) such that for all \(k \in K\), \(k \cdot f = \varepsilon (k)f\), are the K-equivariant homomorhisms. They form a vector subspace of \({\text {End}}(H)\) denoted as \({\text {End}}_K(H)\). Clearly, the K-action is compatible with composition.
-
(2)
In the case that K is cocommutative, the K-action is also compatible with the convolution product. Then \({{\text {End}}}(H)\) and \({{\text {End}}_f}(H)\) are K-module algebras with convolution and \({{\text {End}}}_{K}(H)\), \({{\text {End}}}_{f,K}(H)\) are subalgebras.
-
(3)
In the case that H is finite dimensional and K is cocommutative, the coproduct of \({{\text {End}}}(H)\) is compatible with the action of K. Indeed, if \(\alpha \in H^*\), \(h \in H\), \(k \in K\), we have that \(\Delta (k\cdot (\alpha |h))= \Delta ((\alpha \leftharpoonup Sk_2)| k_1\cdot h)= \sum (\alpha \leftharpoonup Sk_2)_1|(k_1\cdot h)_1 \otimes (\alpha \leftharpoonup Sk_2)_2|(k_1\cdot h)_2= \sum (\alpha _1 \leftharpoonup Sk_4)|(k_1\cdot h_1) \otimes (\alpha _2 \leftharpoonup Sk_3)|(k_2\cdot h_2) = \sum (\alpha _1 \leftharpoonup Sk_2)|(k_1\cdot h_1) \otimes (\alpha _2 \leftharpoonup Sk_4)|(k_3\cdot h_2) = \sum k_1 \cdot (\alpha _1|h_1) \otimes k_2 \cdot (\alpha _2|h_2)\).
Lemma 4.5
-
(1)
In the situation above, if K is cocommutative and H is a K-module bialgebra, then \({\text {End}}(H)\) endowed with the Heisenberg product is a K-module algebra and \({{\text {End}}}_f(H)\) is a K-subalgebra.
-
(2)
Moreover, \({\text {End}}_{K}(H)\) and \({\text {End}}_{f,K}(H)\) are \({{\mathrm{\#}}}\)-subalgebras of \({\text {End}}(H)\).
Proof
We prove only the assertion concerning the Heisenberg product in \({{\text {End}}}_f(H)\) as is the one we use in the applications. The rest of the proof is left to the reader. Consider \(\alpha ,\beta \in H^*\), \(h,\ell \in H\) and \(k \in K\).
We first compute:
next:
Now, the equality of (30) and (31) can be deduced from the following calculation: take \(\beta \in H^*\) , \(h,r \in H\) and \(k \in K\),
\(\sum (k_1\cdot h \rightharpoonup (\beta \leftharpoonup Sk_2))(r)= \sum (\beta \leftharpoonup Sk_2)(rk_1\cdot h)=\sum \beta ((Sk_2) \cdot (r (k_1 \cdot h)))= \sum \beta ((Sk_3 \cdot r) (Sk_2 k_1 \cdot h))=\sum \beta ((Sk \cdot r )h) = ((h \rightharpoonup \beta ) \leftharpoonup Sk)(r)\). \(\square \)
6.2 The case of endomorphisms of graded Hopf algebras
Assume that \(H= \bigoplus _{n \ge 0} H_n\) is a graded connected bialgebra, i.e. for all \(n,m \in \mathbb {N}\), \(H_n H_m \subset H_{n+m}\), \(\Delta (H_n) \subseteq \bigoplus _{p+q=n} H_p \otimes H_q\) and \(H_0=\Bbbk \) (a connectivity condition). It is well known that in this situation H is a Hopf algebra, and that the antipode preserves the degree.
Definition 4.6
Consider the following chain of linear subspaces of \({\text {End}}(H)\), where \({\text {End}}_{\text {gr}}(H)\) is the subspace of the linear endomorphisms of H that preserve the degree: \({\text {End}}(H) \supseteq {\text {End}}_{\text {gr}}(H) = \prod _n {\text {End}}(H_n) \supseteq \bigoplus _n {\text {End}}(H_n)=: {\text {end}}(H) \supseteq \bigoplus _n {\text {End}}_f(H_n)=: {\text {end}}_f(H) \).
In the case that each \(H_n\) is finite dimensional, \({\text {end}}(H)= {\text {end}}_f(H) = \bigoplus _n (H_n^* \otimes H_n)\), that can be endowed with a coproduct defined as below.
Definition 4.7
In the situation above, take \(\alpha |h \in H^*_n \otimes H_n\), if \(\Delta (\alpha )=\sum _{p+q=n} \alpha _p \otimes \alpha _q\) and \(\Delta (h)=\sum _{r+s=n} h_r \otimes h_s\), with \(\alpha _p \in H^*_p\) , \(\alpha _q \in H^*_q\), \(h_r \in H_r\), \(h_s \in H_s\); then \(\Delta (\alpha |h)=\sum _{a+b=n} \alpha _a|h_a \otimes \alpha _b|h_b\).
Remark 4.8
It is clear that the composition and convolution product defined in \({\text {End}}(H)\) restricts to the chain of subspaces considered above. Moreover, in the case that the \(H_n\) are finite dimensional, \({\text {end}}(H)\) endowed with the convolution product and the above defined coproduct is a graded bialgebra.
The behaviour of the Heisenberg product in the graded case is described in the proposition that follows, that plays a central role in our constructions.
Proposition 4.9
(1) The Heisenberg product of \({\text {End}}(H)\) restricts to \({\text {end}}(H)\). Moreover, if \(f\in {\text {End}}(H_p)\) and \(g\in {\text {End}}(H_q)\) then
and the top and bottom components of \(f{{\mathrm{\#}}}g\) are
(2) In the case that \(f= \alpha |k \in {\text {End}}(H_p)\) and \(g = \beta |\ell \in {\text {End}}(H_q)\), we have:
if \(\Delta (k)=\sum _{n} k_{n} \otimes k_{p-n}\) where \(k_{n} \in H_n\) and \(k_{p-n} \in H_{p-n}\). Hence the Heisenberg product of \({\text {End}}(H)\) also restricts to \({\text {end}}_f(H)\).
Proof
(1) Let \(h\in H_n\). The coproduct of h is
with \(h_a\in H_a\) and \(h_b\in H_b\). Using the formula (28) we obtain:
Suppose that f and g belong to \({\text {end}}(H)\). The computation of the degree of every term in the sum yields
proving that \(f{{\mathrm{\#}}}g\) is in \({\text {end}}(H)\).
We can refine the previous analysis as follows. Assume that \(f\in {\text {End}}(H_p)\) and \(g\in {\text {End}}(H_q)\). Then, Expression (34) is zero unless
Adding these two equations we get that \(n=a+b \le p+q\). On the other hand, \(p=a\le a+b=n\) and \(q = b + \deg \bigl ( {f(h_a)}_1 \bigr ) \le b+a = n\), hence \(\max (p,q) \le n\). This proves (32).
If we set \(n=p+q\) in (35) then we get \(\deg \bigl ({f(h_a)}_1\bigr )=0\), and (34) reduces to the convolution diagram in (26). If we set \(n=p=q\), then \(\deg (h_b)=\deg \bigl ({f(h_a)}_2\bigr )=0\), and (34) reduces to \(g\bigl (f(h)\bigr )=(g{{\mathrm{\circ }}}f)(h)\), which is the composition product.
(2) The equality \(\alpha |k \# \beta |\ell = \sum _{0 \le n \le {\text {min}}(p,q)} \alpha (k_n \rightharpoonup \beta )|k_{p-n}\ell \) where \(\Delta (k)= \sum k_n \otimes k_{p-n}\) follows immediately from the explicit formula (34) and from the considerations of (1) with the corresponding bounds for the degrees. \(\square \)
Thus and as expected, the Heisenberg product interpolates between the composition and convolution products. The analogous interpolation property at all other non-commutative levels (permutations and non-commutative symmetric functions) is a consequence of this general result.
Remark 4.10
-
(1)
Assume that that K is a commutative Hopf algebra and that H is graded connected K-module Hopf algebra as above. Assume also that the action of K preserves the grading. In this situation one can consider the chain of subspaces of \({\text {End}}(H)\) that follows:
$$\begin{aligned} \begin{array}{c c c c c c c} {\text {End}}(H) &{} \supseteq &{} {\text {End}}_{\text {gr}}(H) &{} \supseteq &{} {\text {end}}(H) &{} \supseteq &{} {\text {end}}_f(H) \\ \bigcup \mathbf {|}&{} &{} \bigcup \mathbf {|}&{} &{} \bigcup \mathbf {|} &{} &{} \bigcup \mathbf {|}\\ {\text {End}}_K(H) &{} \supseteq &{} {\text {End}}_{\text {gr},K}(H) &{} \supseteq &{} {\text {end}}_K(H) &{} \supseteq &{} {\text {end}}_{f,K}(H). \end{array} \end{aligned}$$ -
(2)
In this context it is clear that all the subspaces considered above are closed under the composition, convolution and Heisenberg products. In particular the following holds: if \(f\in {\text {End}}_K(H_p)\) and \(g\in {\text {End}}_K(H_q)\) then
$$\begin{aligned} f{{\mathrm{\#}}}g \in \bigoplus _{n=\max (p,q)}^{p+q} {\text {End}}_K(H_n). \end{aligned}$$(36)
7 The Heisenberg product of Garsia–Reutenauer endomorphisms
In this section we define a certain distinguished subspace of the endomorphisms of the Hopf algebra H, consisting of what we call the Garsia–Reutenauer endomorphisms. Then we show that the Heisenberg product in \({\text {End}}(H)\) (Sect. 4) can be restricted to this special subspace.
These endomorphisms are characterized in terms of their action on products of primitive elements of H.
The motivation for the definition is that in the case that H is the tensor algebra of a vector space, an important result of Garsia and Reutenauer (see [9]) relates this subspace with the space of non-commutative symmetric functions via Schur–Weyl duality (Lemma 6.1 and Theorem 7.2).
Definition 5.1
Let H be an arbitrary Hopf algebra. If \(h_1,\dots ,h_n \in H\), define
or in other words, \(G(h_1,\dots ,h_n)\) is the subspace generated by the products of the form \(h_{\sigma (1)} \cdots h_{\sigma (n)}\) for \(\sigma \in S_n\).
For later use, we record the explicit expressions of the comultiplication in elements that are products of primitives \(h_1\cdots h_n\) .
We consider the set \({\mathrm {Sh}}(p,q)\) of (p, q)-shuffles. A (p, q)-shuffle is a permutation \(\xi \in S_{p+q}\) such that
The comultiplication of \(h_1\cdots h_n\) is given by:
The following lemma lists some of the basic properties of the subspaces \(G(h_1,\dots ,h_n)\).
Lemma 5.2
For any \(h_1,\dots ,h_n \in H\) we have:
-
(i)
If \(a\in G(h_1,\dots ,h_k)\) and \(b\in G(h_{k+1},\dots ,h_n)\), then \(ab\in G(h_1,\dots h_n)\).
-
(ii)
If \(a\in G(h_1,\dots ,h_n)\) and \(h_1,\dots ,h_n\in {\text {Prim}}(H)\), then
$$\begin{aligned} \Delta (a) = \sum _{\begin{array}{c} k+\ell = n\\ \xi \in {\text {Sh}}(k,\ell ) \end{array}} a^{(1)}_\xi \otimes a^{(2)}_\xi , \end{aligned}$$where \(a^{(1)}_\xi \in G(h_{\xi (1)},\dots ,h_{\xi (k)})\) and \(a^{(2)}_\xi \in G(h_{\xi (k+1)},\dots ,h_{\xi (n)})\).
Definition 5.3
Let H be an arbitrary Hopf algebra. The space of Garsia–Reutenauer endomorphisms of H, that is denoted as \(\Sigma (H)\), is:
The subspace considered above plays for \({\text {End}}(H)\) the same role that the subspace of descents plays for the algebra of permutations.
Theorem 5.4
If H is a Hopf algebra, the space \(\Sigma (H)\) of Garsia–Reutenauer endomorphisms is a subalgebra of \({\text {End}}(H)\) with respect to the Heisenberg product.
Proof
Given a primitive element h, we have \(\iota \varepsilon (h)=0\), hence the unit of the Heisenberg product is in \(\Sigma (H)\).
Take two endomorphisms f and g in \(\Sigma (H)\), and let \(h_1,\dots ,h_n\in {\text {Prim}}(H)\). Then, we have by definition, see (37), (27) and (28):
As \(f(h_{\xi (1)}\cdots h_{\xi (k)})\in G(h_{\xi (1)}\cdots h_{\xi (k)})\), it follows from Lemma 5.2 that
with \(a^{(1)}_\eta \in G(h_{\xi \eta (1)},\dots ,h_{\xi \eta (r)})\) and \(a^{(2)}_\eta \in G(h_{\xi \eta (r+1)},\dots ,h_{\xi \eta (k)})\). Hence, we rewrite (38) as
But the argument of g belongs to \(G(h_{\xi (k+1)},\dots , h_{\xi (n)},h_{\xi \eta (1)},\dots ,h_{\xi \eta (r)})\). Using that \(g\in \Sigma (H)\) and using part (1) of Lemma 5.2 we obtain that
proving that \(f{{\mathrm{\#}}}g\in \Sigma (H)\). \(\square \)
Remark 5.5
It is easy to show that \(\Sigma (H)\) is also a subalgebra of \({\text {End}}(H)\) with respect to the composition and convolution products.
In the situation that H is a graded connected bialgebra, we can produce a homogeneous and equivariant version of the above results.
We define the following chain of subspaces of \(\Sigma (H)\):
and in the case that K is a commutative bialgebra that acts on H, by homogenous bialgebra endomorphisms (see Sect. 4) we define:
As all the objects described above are defined as intersections, it is clear that they are closed under composition, convolution and Heisenberg product.
8 The Heisenberg product of permutations
In order to translate the Heisenberg product from endomorphisms of Hopf algebras to permutations we specialize the constructions of Sect. 4 and apply the methods related to the Schur–Weyl duality theorem, see [16].
Let
be the tensor algebra of a finite dimensional vector space V. It is a graded connected Hopf algebra with product defined by concatenation and with coproduct uniquely determined by the condition that the algebra generators: i.e. the elements \(v \in V\), are primitive:
As \(v_1\otimes \dots \otimes v_n = v_1\cdots v_n\), we omit the tensors when writing elements of T(V).
The general linear group \({\text {GL}}(V)\) acts on V and hence on each \(V^{\otimes n}\) diagonally. Schur–Weyl duality, as presented for example in [7] or [16], guarantees that the only endomorphisms of T(V) which commute with the action of \({\text {GL}}(V)\) are (linear combinations of) permutations.
Let
be the direct sum of all symmetric group algebras. The product in \(\mathcal {S}\) is defined on permutations as the usual composition (denoted by \(\sigma {{\mathrm{\circ }}}\tau \) or \( \sigma \tau \)) when \(\sigma \) and \(\tau \) belong to the same homogeneous component of \(\mathcal {S}\), and is 0 in any other case. The identity in \(S_n\) is denoted by \(\mathrm {Id}_n\).
Lemma 6.1
(Schur–Weyl duality) In the notations above, let \(\Psi \) be the map
defined by sending \(\sigma \in S_n\) to the endomorphism \(\Psi (\sigma )\) of T(V), which in degree n is given by the right action of \(\sigma \) on \(V^{\otimes n}\):
and is 0 in the other homogeneous components. Then, \(\Psi \) is an homogeneous isomorphism of vector spaces.
Definition 6.2
The Heisenberg product of permutations \({{\mathrm{\#}}}: \mathcal {S}\times \mathcal {S}\rightarrow \mathcal {S}\) is defined by the commutativity of the diagram below:
Compare the above definition with the results by Malvenuto and Reutenauer in [21] where the authors deal with the convolution product in \(\mathcal {S}\). The considerations of Sect. 4, guarantee that the same methods can be applied in the situation treated in Definition 6.2 for the Heisenberg product.
This method, presented in [21] and used above, is important because it could be applied to other dualities than Schur–Weyl, i.e. to centralizer algebras of other groups (or Hopf algebras) acting on a tensor algebra.
It also can be applied to other products of endomorphisms, a remarkable case being that of the Drinfel’d product, which is studied in [23].
Next we exhibit an explicit formula for the Heisenberg product of two permutations, that at the lowest and highest degree, yield the usual formulæ for the composition and the Malvenuto–Reutenauer products respectively (see the table appearing in Table 1).
We establish the following notation for the (p, q) shuffle of maximal length:
Notice in particular that \(\beta _{p,q}=\beta _{q,p}^{-1}\).
Theorem 6.3
-
(1)
Let \(\sigma \in S_p\) and \(\tau \in S_q\). Then, the Heisenberg product in \(\mathcal {S}\) can be expressed as
$$\begin{aligned} \sigma {{\mathrm{\#}}}\tau = \sum _{n=\max (p,q)}^{p+q} \sum _{\begin{array}{c} \xi \in {\text {Sh}}(p,n-p)\\ \eta \in {\text {Sh}}(p+q-n,n-q) \end{array}} \xi \bigl ( (\sigma \eta ) \times \mathrm {Id}_{n-p} \bigr ) \beta _{2n-p-q, p+q-n} (\mathrm {Id}_{n-q}\times \tau ). \end{aligned}$$(40) -
(2)
When \(n=p+q\):
$$\begin{aligned} (\sigma {{\mathrm{\#}}}\tau )_n = \sigma {{\mathrm{\star }}}\tau = \sum _{\xi \in {\text {Sh}}(p,q)}\xi (\sigma \times \tau ), \end{aligned}$$where \(\sigma \times \tau \in S_{p+q}\) via the standard inclusion:
$$\begin{aligned} (\sigma \times \tau )(i)= {\left\{ \begin{array}{ll} \sigma (i) &{} \text { if }1\le i\le p\,,\\ p+\tau (i-p) &{} \text { if }p+1\le i\le p+q\,. \end{array}\right. } \end{aligned}$$When \(n=p=q\):
$$\begin{aligned} (\sigma {{\mathrm{\#}}}\tau )_n = \sigma \tau . \end{aligned}$$
Proof
-
(1)
Using (37) and (38) for the endomorphisms \(\Psi (\sigma )\) and \(\Psi (\tau )\) induced by the permutations \(\sigma \in S_p\) and \(\tau \in S_q\), respectively, we obtain:
$$\begin{aligned}&\bigl (\Psi (\sigma ) {{\mathrm{\#}}}\Psi (\tau ) \bigr ) (v_1\cdots v_n) \\&\quad = \sum _{\begin{array}{c} r+s=n\\ \xi \in {\text {Sh}}(r,s) \end{array}} \bigl ( \Psi (\sigma )(v_{\xi (1)}\cdots v_{\xi (r)}) \bigr )_2 \;\Psi (\tau ) \Bigl ( v_{\xi _{r+1}}\cdots v_{\xi _n}\, \bigl ( \Psi (\sigma )( v_{\xi (1)}\cdots v_{\xi (r)} ) \bigr )_1 \Bigr ). \end{aligned}$$The only non-zero terms occur when \(r=p\), hence
$$\begin{aligned} \begin{aligned}&\bigl (\Psi (\sigma ) {{\mathrm{\#}}}\Psi (\tau )\bigr ) (v_1\cdots v_n) \\&\quad = \sum _{\xi \in {\text {Sh}}(p,n-p)} \bigl ( \Psi (\sigma )(v_{\xi (1)}\cdots v_{\xi (p)}) \bigr )_2 \;\Psi (\tau )\Bigl ( v_{\xi (p+1)}\cdots v_{\xi (n)}\, \bigl ( \Psi (\sigma )( v_{\xi (1)}\cdots v_{\xi (p)} ) \bigr )_1 \Bigr ) \\&\quad = \sum _{\begin{array}{c} \xi \in {\text {Sh}}(p,n-p)\\ u+v=p \\ \eta \in {\text {Sh}}(u,v) \end{array}} v_{\xi \sigma \eta (u+1)} \cdots v_{\xi \sigma \eta (p)} \Psi (\tau )( v_{\xi (p+1)}\cdots v_{\xi (n)} v_{\xi \sigma \eta (1)} \cdots v_{\xi \sigma \eta (u)} ) \\&\quad = \sum _{\begin{array}{c} \xi \in {\text {Sh}}(p,n-p)\\ \eta \in {\text {Sh}}(p+q-n,n-q) \end{array}} v_{\xi \sigma \eta (p+q-n+1)} \cdots v_{\xi \sigma \eta (p)} v_{\xi \tau (p+1)}\cdots v_{\xi \tau (n)} v_{\xi \sigma \eta \tau (1)} \cdots v_{\xi \sigma \eta \tau (p+q-n)} \\&\quad = \sum _{\begin{array}{c} \xi \in {\text {Sh}}(p,n-p)\\ \eta \in {\text {Sh}}(p+q-n,n-q) \end{array}} \Psi \Bigl [ \xi \bigl ( (\sigma \eta ) \times \mathrm {Id}_{n-p} \bigr ) \beta _{2n-p-q, p+q-n} (\mathrm {Id}_{n-q}\times \tau ) \Bigr ](v_1\cdots v_n), \end{aligned} \end{aligned}$$which proves the first part of the theorem.
-
(2)
This part follows directly. Observe that for the case \(n=p+q\) we obtain the product of permutations as defined by Malvenuto–Reutenauer in [20, 21].
In the case \(n=p=q\) and since the action of \(S_n\) on \(V^{\otimes n}\) is from the right, the composition of permutations corresponds to composition of endomorphisms in the opposite order (compare with the results of Proposition 4.9).
\(\square \)
For example, writing the permutations in word format we obtain that:
Notice that the red terms correspond to the Malvenuto–Reutenauer product.
9 The Heisenberg product of non-commutative symmetric functions
The descent set of a permutation \(\sigma \in S_n\) is the subset of \([n-1]\) defined by
Given \(J\subseteq [n-1]\), define \(\mathcal {B}_J\) as the set of permutations \(\sigma \in S_n\) with \({\text {Des}}(\sigma )\subseteq J\), and consider the following elements of \(\Bbbk S_n\):
The family of subsets of \([n-1]\) is in bijective correspondence with the set of compositions of n. Recall that \(\alpha =(a_1,\ldots ,a_r)\) is a composition of n if all the \(a_i\) are positive integers and \(\sum _{i=1}^r a_i=n\), in this situation we write \(\alpha =(a_1,\ldots ,a_r) \models n\).
The bijection between compositions and subsets is:
For instance, if \(n=9\), then \(X_{(1,2,4,2)}=X_{\{1,3,7\}}\) and \(X_{(2,4,2,1)}=X_{\{2,6,8\}}\).
Definition 7.1
Let \(\Sigma _n=\Bbbk \{X_\alpha : \alpha \models n\} \subseteq \Bbbk S_n\) be the subspace linearly spanned by \(X_\alpha \) with \(\alpha \) a composition of n and
An important result of Garsia and Reutenauer characterizes the elements of \(\mathcal {S}\) whose images by \(\Psi \), in the notations of Lemma 6.1, belong to \(\sigma _{{\text {GL}}(V)}\big (T(V)\big )\). in terms of their action on the tensor algebra. Recall the Definition 5.3 of \(\sigma _{{\text {GL}}(V)}\big (T(V)\big )\).
Theorem 7.2
(Garsia–Reutenauer, [9]) Let \(\Psi \) be isomorphism defined in Lemma 6.1, then the following diagram commutes:
and the map \(\Psi |_{\Sigma }\) is surjective.
A fundamental result of Solomon [28] states that \(\Sigma _n\) is a subalgebra of the symmetric group algebra \(\Bbbk S_n\) with the composition product. This is Solomon’s descent algebra. It is also well-known that \(\Sigma \) is closed under the external product [11, 12, 21]; in fact,
The space \(\Sigma \) with the external product is the algebra of non-commutative symmetric functions.
The following theorem generalizes these two situations in view of the interpolation property of the Heisenberg product of permutations.
Theorem 7.3
The subspace \(\Sigma \subseteq \mathcal {S}\) is closed under the Heisenberg product.
Proof
This a direct result from Theorems 5.4, 7.2, and Schur–Weyl duality (Lemma 6.1). \(\square \)
The next theorem gives another version of the same result with an explicit description of the value of \(X_\alpha {{\mathrm{\#}}}X_\beta \) for \(\alpha \models p\) and \(\beta \models q\). The structure coefficients of \(X_\alpha {{\mathrm{\#}}}X_\beta \) are expressed in terms of the matrices \(\mathcal {M}_{\alpha ,\beta }^n\) defined in Sect. 3.2.
In [23] appears another combinatorial proof which extends a proof of Schocker in [27] for the composition product.
Moreover, another proof of Theorem 7.3 can be obtained by extending the Heisenberg product to the Coxeter complex of the symmetric group (that is, the faces of the permutahedron). This makes a connection with recent work of Brown, Mahajan, Schocker, and others on this aspect of the theory of descent algebras [3, 6, 27].
Recall the following definition: take \(\alpha =(a_1,\ldots ,a_r)\vDash p\), \(\beta =(b_1,\ldots ,b_s)\vDash q\) two compositions and let n be an integer satisfying \(\max (p,q)\le n\le p+q\). Let \(a_0:=n-p\), \(b_0:=n-q\), and \(\mathcal {M}_{\alpha ,\beta }^n\) be the set of all integral \((s+1)\times (r+1)\)-matrices with non-negative entries \(M=(m_{ij})_{ \begin{array}{c} 0\le i\le s\\ \,0\le j\le r \end{array}}\) such that: the sequence of column sums is \((a_0,a_1,\ldots ,a_r)\), the sequence of row sums is \((b_0,b_1,\ldots ,b_s)\) and the first entry is \(m_{00}=0\). To visualize these conditions consider the diagram appearing before Theorem 3.1.
Theorem 7.4
Let \(\alpha \vDash p\) and \(\beta \vDash q\) be two compositions. Then
where c(M) is the composition whose parts are the non-zero entries of M, read from left to right and from top to bottom.
Observe that even though this formula is similar to the one we had for symmetric functions (17), the occurrence of the compositions as indices of the basis makes the connection between the Heisenberg product and the external and Solomon products considerably subtler than in the commutative context. In particular, a formula like (22) no longer holds. Moreover, the above expression will allow us to make the connection with the Heisenberg product of the representations of the symmetric group. This point is taken up in Sect. 8.
By the interpolation property of the Heisenberg product, Theorem 7.4 contains as special cases rules for the product in Solomon’s descent algebra and for the external product of two basis elements of \(\Sigma \). One readily verifies that the former is precisely the well-known rule of Garsia, Remmel, Reutenauer, and Solomon as given in [9, Proposition 1.1], while the latter is the one appearing in (42).
As an example we have the following formula
where \((1^n)\) is the composition of n with n parts equal to 1. The coefficients arise by inspection of all the possible ways to fill out the entries of the matrix M in a diagram as below with row and column sums as prescribed.
Similarly, one verifies that:
where the S(n, k) are the Stirling numbers of the second kind.
Proof of Theorem 7.4
Let us take a fixed integer n between \(\max (p,q)\) and \(p+q\). To the compositions \(\alpha =(a_1,\ldots ,a_r)\) and \(\beta =(b_1,\ldots ,b_s)\) we associate the following sets:
Observe that the family of intervals \(\{E^n_j\}_{j\in \{0,\ldots , r\}}\) and \(\{F^n_i\}_{i\in \{0,\ldots , s\}}\) are partitions of [1, n]. It is also clear that \(\sigma \in \mathcal {B}_\alpha \) if and only if \(\sigma \times \mathrm {Id}_{n-p}\) is increasing in \(E^n_j\) for all \(j\in \{0,\ldots ,r\}\). Similarly, \(\tau \in \mathcal {B}_\beta \) if and only if \(\mathrm {Id}_{n-q}\times \tau \) is increasing in \(F^n_i\) for all \(i\in \{0,\ldots ,s\}\). Observe, also, that \({\#}{E^n_j}\) is the j-th coordinate of the pseudo-composition \((n-p,a_1,\ldots ,a_r)\), and \({\#}{F^n_i}\) is the i-th coordinate of \((n-q,b_1,\ldots ,b_s)\).
Given \(\eta \in {\text {Sh}}(p+q-n,n-q)\) and \(\tau \in \mathcal {B}_\beta \), call \(\varphi _{\eta ,\tau }=(\eta \times \mathrm {Id}_{n-p})\beta _0(\mathrm {Id}_{n-q}\times \tau )\) and define the matrix
where we have abbreviated \(\beta _{2n-p-q,p+q-n} = \beta _{0}\). In this situation \(M_{\eta ,\tau } \in \mathcal {M}_{\alpha ,\beta }^n\). Indeed, if we call \(m_{ij}= {\#}(F^n_i \cap \varphi _{\eta ,\tau }^{-1}E^n_j)\), for \(i=j=0\) we have that
which shows that the intersection \(F^n_0 \cap \varphi _{\eta ,\tau }^{-1}E^n_0\) is empty, and then \(m_{00}=0\). The sum \(m_{0j}+\cdots +m_{sj}\) equals the number of elements of \(E^n_j\), which is, as noted before, the j-th entry of the composition \((n-p,a_1,\ldots ,a_r)\). The same argument applies to the sum of the rows. In this manner, sending \(\tau \mapsto M_{\eta ,\tau }\) we define a map \(\mathcal {B}_\beta \rightarrow \mathcal {M}_{\alpha ,\beta }^n\). Take \(M = \{m_{ij}\} \in \mathcal {M}^n_{\alpha ,\beta }\) and let \(\mathcal {B}_\beta ^{\eta ,n}(M)\) the corresponding fiber of this map:
Therefore, we have a partition of \(\mathcal {B}_\beta = \bigcup _{M \in \mathcal {M}^n_{\alpha ,\beta }} \mathcal {B}_\beta ^{\eta ,n}(M)\).
For \(\xi \in {\text {Sh}}(p,n-p)\) and \(\eta \in {\text {Sh}}(p+q-n,n-q)\), let us denote \( g^n_{\xi ,\eta }(\sigma ,\tau ) = \xi \bigl ( (\sigma \eta )\times \mathrm {Id}_{n-p} \bigr ) \beta _0 (\mathrm {Id}_{n-q}\times \tau ) \), the n-term in the sum (40). The function \(g^n_{\xi ,\eta }\) is bilinear, and we can write
From now on as n is fixed we will omit it in the notation for the sets and the functions. Next we show that
For this, we write
If we denote by \(S_{\alpha ,\beta }(M)\) the set of elements \((\xi ,\eta ,\sigma ,\tau )\) such that \(\xi \in {\text {Sh}}(p,n-p)\), \(\eta \in {\text {Sh}}(p+q-n,n-q)\), \(\sigma \in \mathcal {B}_\alpha \) and \(\tau \in \mathcal {B}_\alpha ^\eta (M)\), then the map \(\psi :S_{\alpha ,\beta }(M)\rightarrow \mathcal {B}_{c(M)}\) given by \(\psi (\xi ,\eta ,\sigma ,\tau )=g_{\xi ,\eta }(\sigma , \tau )\) is a bijection. We prove this fact in Lemma 7.6. In this situation, if we group together the last three sums of (45) we obtain
which concludes the proof of the theorem. \(\square \)
In the following two lemmas we assume the notation of the previous theorem. Their proofs, being rather technical are presented in the “Appendix”. See: 13.2 and 13.3.
Lemma 7.5
For \(\eta \in {\text {Sh}}(p+q-n,n-q)\), \(\tau \in \mathcal {B}_\beta \) and for all \(i=0,\ldots ,s\) and \(j=0,\ldots ,r\), the sets
are disjoint intervals. Moreover, in each of these intervals the function \(\varphi _{\eta ,\tau }\) is increasing and has image either contained in [1, p] or contained in \([p+1,n]\).
Lemma 7.6
For \(M\in \mathcal {M}_{\alpha ,\beta }\), the map \(\psi :S_{\alpha ,\beta }(M) \rightarrow \mathcal {B}_{c(M)}\), which sends \((\xi ,\eta ,\sigma ,\tau )\) into \(g_{\xi ,\eta }(\sigma ,\tau )\), is a bijection.
10 From non-commutative to commutative symmetric functions
In the previous four sections of Part 2: Non-commutative context; we constructed the following commutative diagram of algebras when endowed with their respective Heisenberg products (omitting the part that includes the space \(\Lambda \)):
In the part of the above diagram that excludes \(\Lambda \), all the Heisenberg products are induced by the one defined in the larger space \({\text {end}}\bigl (T(V)\bigr )\). Recall also that the vertical isomorphisms are due to Schur–Weyl duality and to the results of [9] as mentioned in Sect. 7, Theorem 7.2.
We want to incorporate into this diagram the space of symmetric functions \(\Lambda \) equipped also with the Heisenberg product, this is expressed in the dotted arrow that is to be defined.
For each \(n\ge 0\) we define the linear map \(\pi _n:\Sigma _n\rightarrow \Lambda _n\) by its values on the basis \(\{X_\alpha : \alpha \text { composition of}\,\, n\}\) as:
where \(\widetilde{\alpha }\) is the partition of n obtained by reordering the entries of the composition \(\alpha \). Let us denote by \(\pi :\Sigma \twoheadrightarrow \Lambda \) the map induced in the direct sums.
It is well known that \(\pi \) is a morphism if we endow \(\Sigma \) with the Solomon product and \(\Lambda \) with the internal product, it is also a morphism when we endow both spaces with the external products.
The theorem that follows generalizes these compatibilities by proving that the map \(\pi :\Sigma \twoheadrightarrow \Lambda \) is a morphism with respect to the Heisenberg products in \(\Lambda \) and \(\Sigma \), as constructed in Sects. 3 and 7, respectively.
Theorem 8.1
For any pair of compositions \(\alpha \) and \(\beta \):
Proof
Comparing the explicit formulæ: Eqs. (17) and (43), it is clear that it is enough to construct for each n a bijection \(\psi :\mathcal {M}_{\alpha ,\beta }^n\rightarrow \mathcal {M}_{\widetilde{\alpha },\widetilde{\beta }}^n\), such that for all \(M\in \mathcal {M}_{\alpha ,\beta }^n\):
Let \(\sigma \) and \(\tau \) be two permutations which reorder into partitions the compositions \(\alpha =(a_1,\dots ,a_r)\) and \(\beta =(b_1,\dots ,b_s)\), respectively, i.e.:
Define \(\psi (M)\) as the matrix obtained from M by permuting its columns with the permutation \(\mathrm {Id}_1\times \sigma \) and its rows with the permutation \(\mathrm {Id}_1\times \tau \). Clearly \(\psi (M)\) is in \(\mathcal {M}_{\widetilde{\alpha },\widetilde{\beta }}^n\) and the map \(\psi \) is a bijection.
Moreover, since the (unordered) entries of M and \(\psi (M)\) are the same, we get Eq. (46). \(\square \)
11 Compatibility of the coproduct with the Heisenberg product
In various of the spaces depicted in the table in Fig. 1, coproducts can be introduced, and frequently they are compatible with the products we are considering. For brevity we concentrate in the consideration of the compatibility of the coproducts with the Heisenberg product at the level of permutations, of non commutative and of commutative symmetric functions. We start by considering a coproduct that is called the convolution (or external) coproduct.
We start by defining this coproduct at the level of \(\mathcal {S}\).
Let n be a positive integer and decompose it as \(n=p+q\). Then, as \({\mathrm {Sh}}^{-1}(p,q)\) is a set of representatives for the left cosets of \({S}_p\times {S}_q \subseteq {S}_n\), given \(\sigma \in {S}_{n}\) there is a unique triple \((\xi ,\sigma _p,\sigma '_q)\) such that: \(\xi \in {\mathrm {Sh}}(p,q)\), \(\sigma _p\in {S}_p\), \(\sigma '_q \in {S }_q\), and
The coproduct \(\Delta :\mathcal {S}\rightarrow \mathcal {S}\otimes \mathcal {S}\) is defined on \(\sigma \in {S}_n\) as
where \(\sigma _p\) and \(\sigma '_q\) are as in (47). For instances: \(\Delta (52413)=(\,\,)\otimes (52413)+(1)\otimes (4132)+(21)\otimes (321)+(231)\otimes (21)+(2413)\otimes (1)+(52413)\otimes (\,\,) \).
If follows directly from the formula (48) above (see [20]) that:
where for a pseudopartition \(\alpha \), \(\alpha ^{\widehat{\ }}\) indicates that parts equal to zero have been omitted.
It is then clear that the comultiplication \(\Delta \) can be restricted to the space of descents: i.e. that
Remark 9.1
In [20, Thèoréme 5.3, Remarque 5.15] it is proved that equipped with the convolution product and the above coproduct, \(\mathcal {S}\) becomes a graded connected Hopf algebra and it is also shown that \(\Delta \) is not compatible with the composition of permutations. Also in [2] a more recent and detalied study of \((\mathcal {S}, {{\mathrm{\star }}}, \Delta )\) is presented.
Taking into account that the Heisenberg product, interpolates between the convolution (or Malvenuto–Reutenauer) and the composition product at the level of the permutations, we cannot expect it to be compatible with the coproduct considered above.
These operations are better behaved if we restrict our attention to the non commutative symmetric functions.
Next we prove that \(\Delta \) is compatible with the Heisenberg product in \(\Sigma \), and in particular this implies that for descents the composition product is compatible with the comultiplication.
Theorem 9.2
The space \((\Sigma ,{{\mathrm{\#}}},\Delta )\) is a cocommutative Hopf algebra.
Proof
It is enough to prove the Heisenberg–multiplicativity of \(\Delta \) on elements of the form \(X_\alpha \) with \(\alpha \) a composition of p for different p’s.
Let \(\alpha \) and \(\beta \) be compositions of p and q, respectively. We use Formula (43) to compute
On the other hand,
We show that the sums (50) and (51) are the same as follows: take an octuple of indices corresponding to the sum (51): \((\gamma ,\gamma ',\delta ,\delta ',n,n',M,M')\) and construct the quadruple \(\bigl (n+n', M+M', c(M), c(M')\bigr )\). Denote by \({\text {col}}(M)\) (\({\text {row}}(M)\)) the vector whose entries are the sum of the columns (rows) of the matrix M. Since
where \(|\zeta |\) is the sum of the parts of a composition \(\zeta \), and similarly with \({\text {row}}(M+M')=(n+n'-q)\beta \), we see that \(M+M'\in \mathcal {M}^n_{\alpha ,\beta }\). As \(c(M)+c(M')=c(M+M')\), if we set
it is clear that \((\widetilde{n},\widetilde{M},\widetilde{\gamma }, \widetilde{\gamma '})\) is a quadruple of indices appearing in the sum (50) and that the corresponding summands of (50) and (51) are the same.
Moreover, it is clear that the above correspondence between the indices of the sums is bijective. \(\square \)
Consider now the space of symmetric functions \(\Lambda \) and the projection \(\pi : \Sigma \rightarrow \Lambda \). In Sects. 3.2 and 3.4, Eqs. (21) and (23) we defined a coproduct on \(\Lambda \) similar to the one defined above and dual to the external product. We then gave its expression on the natural basis of complete homogeneous functions and power sums.
In particular we have that in the notations of Sects. 3.2 and 3.4: \( \Delta (h_a)=\sum _{i+j=a}h_i \otimes h_j\) and \(\Delta (p_n) = 1\otimes p_n+p_n\otimes 1\).
Being \(\pi (X_\alpha )=h_\alpha \), and using the first of the above equalities and Theorem 9.2, we conclude the following result.
Corollary 9.3
The space of symmetric functions \(\Lambda \) equipped with the operations \(({{\mathrm{\#}}},\Delta )\) is a cocommutative Hopf algebra and the map \(\pi :\Sigma \rightarrow \Lambda \) is a morphism of Hopf algebras.
Proof
We have that:
Since \(\pi \) is Heisenberg multiplicative, we conclude that the coproduct and the Heisenberg product are compatible in the space \(\Sigma \). The compatibility of the coproduct and the Heisenberg product in \(\Sigma \) induces the compatibility in \(\Lambda \). \(\square \)
This theorem generalizes known results on \((\Lambda ,{{\mathrm{\cdot }}},\Delta )\) and \((\Lambda ,{{\mathrm{*}}},\Delta )\): see for example [10].
12 Isomorphisms between the Heisenberg, convolution, and composition products
We have mentioned until now, two kinds of relations between the three products we have been dealing with: one is the interpolation connection and the other the formula appearing in Lemma 3.3.
In the spaces of symmetric functions there are further relations between the Heisenberg, internal and external products.
First we show that the external and Heisenberg products are isomorphic (in the commutative and non-commutative situations), but the isomorphism is not degree-preserving.
Similarly we prove that the Heisenberg and internal products are isomorphic in the commutative context (the degrees are not preserved), but the isomorphism is only valid in the completion of the space.
Theorem 10.1
The map \(\psi :(\Sigma ,{{\mathrm{\cdot }}},\Delta )\rightarrow (\Sigma ,{{\mathrm{\#}}},\Delta )\) given by
is an isomorphism of Hopf algebras (which does not preserve the gradings).
Proof
Since the Heisenberg product has the external product as the only term in the upper degree, the matrix of the linear map \(\psi \) in the basis of the \(X_\alpha \)’s is triangular with 1 in the diagonal. Hence \(\psi \) is invertible and it is multiplicative because the external product in the basis of the \(X_\alpha \)’s is the concatenation of the compositions.
We finish by proving that \(\psi \) is comultiplicative:
Clearly, it is enough to prove (53) on the algebra generators \(X_{(a)}\) for all non-negative integers a. For the right hand side of (53) we have:
Applying the map \(\psi \otimes \psi \) and using formula (43) to compute \(\psi (X_{(a,a')}) = X_{(a)}{{\mathrm{\#}}}X_{(a')}\) and \(\psi (X_{(b,b')}) = X_{(b)}{{\mathrm{\#}}}X_{(b')}\) (note that we assume \(\psi (X_{(0)})\) to be the identity) we get
On the other hand, taking into account that \(\psi (X_{\alpha })=X_\alpha \) for partitions with only one part, the left hand side of (53) is:
By collecting together the terms in (54) with \(n+m=k\) and interchanging the sums, it is easy to see that (54) and (55) are the same expression. \(\square \)
Corollary 10.2
The map \((\Lambda ,{{\mathrm{\cdot }}},\Delta )\rightarrow (\Lambda ,{{\mathrm{\#}}},\Delta )\) given by
is an isomorphism of Hopf algebras (which does not preserve the gradings).
The Heisenberg and internal products are also isomorphic at the level of \(\widehat{\Lambda }\).
Theorem 10.3
The map \((\widehat{\Lambda },{{\mathrm{\#}}})\rightarrow (\widehat{\Lambda },{{\mathrm{*}}})\) given by
is an isomorphism of algebras.
Proof
This isomorphism follows from the isomorphism (4) in the category of species. Note that the species \(\mathsf {e}\) corresponds to the object \((\mathbf {1}_0, \mathbf {1}_1,\dots )\) in the category \(\mathbf {R}\), where \(\mathbf {1}_n\) is the trivial \(S_n\)-module. Applying the Grothendieck group construction and then the Frobenius map \({\text {ch}}\), we deduce that \(\mathsf {e}\) maps into the element \( \sum _{n\ge 0} h_{(n)} \) in \(\widehat{\Lambda }\). \(\square \)
Remark 10.4
We give negative answers to three questions on possible extensions of the above results.
-
(1)
The isomorphism \((\Sigma ,{{\mathrm{\cdot }}})\cong (\Sigma ,{{\mathrm{\#}}})\) of Theorem 10.1 does not extend to an isomorphism between \((\widehat{\Sigma },{{\mathrm{\cdot }}})\) and \((\widehat{\Sigma },{{\mathrm{\#}}})\). Indeed, in case it did extend:
$$\begin{aligned} \psi (X_{(1)}+X_{(1,1)}+X_{(1,1,1)}+\cdots )= X_{(1)}+X_{(1)}{{\mathrm{\#}}}X_{(1)}+X_{(1)}{{\mathrm{\#}}}X_{(1)}{{\mathrm{\#}}}X_{(1)} +\cdots , \end{aligned}$$(58)each of the terms in the infinite sum appearing in the right hand side of (58), contributes with a factor of degree 1 (namely, \(X_{(1)}\)); this infinite sum is not a well-defined element of \(\widehat{\Sigma }\).
-
(2)
The isomorphism \((\widehat{\Lambda },{{\mathrm{\#}}})\cong (\widehat{\Lambda },{{\mathrm{*}}})\) of Theorem 10.3 does not restrict to an isomorphism between \((\Lambda ,{{\mathrm{\#}}})\) and \((\Lambda ,{{\mathrm{*}}})\). Indeed, the element \(1\in \Lambda \) maps to \(\sum _{n\ge 0} h_{(n)}\) which is in \(\widehat{\Lambda }\) but not in \(\Lambda \).
-
(3)
A similar isomorphism to (57) cannot be established at the level of \(\widehat{\Sigma }=\prod _{n\ge 0}\Sigma _n\). The maps \(\varphi :f\mapsto f{{\mathrm{\cdot }}}\sum _{n\ge 0}X_{(n)} \quad \text {and}\quad \psi :f\mapsto \sum _{n\ge 0}X_{(n)}{{\mathrm{\cdot }}}f\) are not isomorphisms between \((\widehat{\Sigma },{{\mathrm{\#}}})\) and \((\widehat{\Sigma },{{\mathrm{*}}})\) because they are not not multiplicative. Indeed, using the rule (43) we obtain that:
$$\begin{aligned} X_{(3)}{{\mathrm{\#}}}X_{(3)} = X_{(3)}+X_{(1,1,2)}+X_{(2,2,1)}+X_{(3,3)}. \end{aligned}$$Then:
$$\begin{aligned} \varphi (X_{(3)}{{\mathrm{\#}}}X_{(3)}) = \sum _{n\ge 0} X_{(3,n)^{\widehat{\ }}}+ \sum _{n\ge 0} X_{(1,1,2,n)^{\widehat{\ }}}+ \sum _{n\ge 0} X_{(2,2,1,n)^{\widehat{\ }}}+ \sum _{n\ge 0} X_{(3,3,n)^{\widehat{\ }}}. \end{aligned}$$(59)On the other hand, computing \(\varphi (X_{(3)}){{\mathrm{*}}}\varphi (X_{(3)})\) using Solomon’s rule, gives:
$$\begin{aligned} \varphi (X_{(3)}){{\mathrm{*}}}\varphi (X_{(3)})&= \sum _{n,m} X_{(3,n)^{\widehat{\ }}} {{\mathrm{*}}}X_{(3,m)^{\widehat{\ }}} = \sum _nX_{(3,n)^{\widehat{\ }}} {{\mathrm{*}}}X_{(3,n)^{\widehat{\ }}} \nonumber \\&= \sum _{n\ge 0} X_{(3,n)^{\widehat{\ }}} + X_{(2,1,1,n)^{\widehat{\ }}} + X_{(1,2,2,n)^{\widehat{\ }}} + X_{(3,3,n)^{\widehat{\ }}}. \end{aligned}$$(60)We can see that (59) and (60) are different since, for example, the term \(X_{(2,1,1,n)^{\widehat{\ }}}\) appears in (60) but there is no term in (59) whose index is a composition starting with 2, 1, 1. A similar argument can be applied to show that \(\psi \) is also not multiplicative.
13 Part 3. Quasi-symmetric functions
14 The internal and external coproduct of quasi-symmetric functions
In this section we consider space of quasi-symmetric functions \(\mathcal {Q}\), dual to the non-commutative symmetric functions. First, in preparation to the introduction by dualization a new coproduct: the Heisenberg coproduct we recall the basic definitions of the internal and external coproducts.
In Sects. 7, 8 and 9 we dealt with the following diagram:
and endowed the different spaces with the Heisenberg product \({{\mathrm{\#}}}\) and the external coproduct \(\Delta \). In this part we introduce other coproducts, and to avoid confusions we rename the external coproduct as \(\Delta _{\circ }\) [it was called simply \(\Delta \) when considered in (48) and (21)]. We proved the compatibility of \(({{\mathrm{\#}}}, \Delta _{\circ })\) at the level of \(\Sigma \) and \(\Lambda \). This compatibility is consistent with the known results about of the external (or Malvenuto–Reutenauer) product and the coproduct at the three levels of the above diagram, and about the compatibility with the internal (and Solomon) product at the levels of \(\Lambda \) and \(\Sigma \) (compare with Remark 9.1).
Of the three Hopf algebras: \((\Sigma ,*,\Delta _{circ})\), \((\mathcal {S},{{\mathrm{\star }}},\Delta _{\circ })\) and \((\Lambda ,*,\Delta _{\circ })\) the second and third are self dual (see for example [11, 12, 14, 15, 21]).
Hence, we can complete the picture adding the space \(\mathcal {Q}\) that is the graded dual of \(\Sigma \), and that will fit into the following commutative diagram of Hopf algebras:
The diagram is self dual with respect to the antidiagonal. The new maps F and \(\pi ^*\) are the duals of the inclusion of \(\Sigma \) in \(\mathcal {S}\) and of the projection of \(\Sigma \) onto \(\Lambda \), respectively. The map F is described in detail in [2] and will not be used here. Note that the space \(\mathcal {S}\) is a Hopf algebra with respect to the Malvenuto–Reutenauer product (as noted in Remark 9.1) and not with respect to the composition product.
Next we recall the definition of \(\mathcal {Q}\). Let \(\mathbf {X}=\{x_1,x_2,\ldots \}\) be an alphabet, i.e. a countable set, totally ordered by \(x_1<x_2<\cdots \). Let \(\Bbbk [[\mathbf {X}]]\) be the algebra of formal power series on \(\mathbf {X}\) and \(\mathcal {Q}=\mathcal {Q}(\mathbf {X})\) the subspace linearly spanned by the elements
as \(\alpha =(a_1,\ldots ,a_r)\) runs over all compositions of n, for \(n\ge 0\). The space \(\mathcal {Q}\) is a graded subalgebra of \(\Bbbk [[\mathbf {X}]]\) known as the algebra of quasi-symmetric functions (see [12]). It is clear that any symmetric function is quasi-symmetric, hence we have the inclusion of algebras \(\Lambda \subseteq \mathcal {Q}\). In [21] it is proved that this map is \(\pi ^*\) defined above as the dual of the projection \(\pi :\Sigma \twoheadrightarrow \Lambda \) (see Sect. 8).
The algebra \(\mathcal {Q}\) carries two coproducts \(\Delta _{{{\mathrm{*}}}}\) and \(\Delta _{\circ }\) which are defined via evaluation of quasi-symmetric functions on alphabets. Let \(\mathbf {Y}\) be another alphabet. We can view the disjoint union \(\mathbf {X}+\mathbf {Y}\) (ordinal sum) and the Cartesian product \(\mathbf {X}\times \mathbf {Y}\) as alphabets as follows: on \(\mathbf {X}+\mathbf {Y}\) we keep the ordering among the variables of \(\mathbf {X}\) and among the variables of \(\mathbf {Y}\), and we require that every variable of \(\mathbf {X}\) precede every variable of \(\mathbf {Y}\). On \(\mathbf {X}\times \mathbf {Y}\) we impose the reverse lexicographic order:
The coproducts are defined by the formulas
together with the identification \( \mathcal {Q}(\mathbf {X},\mathbf {Y})\cong \mathcal {Q}(\mathbf {X})\otimes \mathcal {Q}(\mathbf {X}) \) (separation of variables).
Consider the following pairing between the homogeneous components of degree n of \(\mathcal {Q}\) and \(\Sigma \):
It is known [11, 12, 21] that this pairing identifies the product of quasi-symmetric functions with the coproduct (49) of \(\Sigma \), and the coproducts \(\Delta _{{{\mathrm{*}}}}\) and \(\Delta _{{{\mathrm{\cdot }}}}\) with the internal and external products of \(\Sigma \). In other words,
for any \(f,g\in \mathcal {Q}\) and \(u,v\in \Sigma \). Here we set \(\langle f\otimes g, u\otimes v\rangle =\langle f,u\rangle \langle g,v\rangle \).
15 The Heisenberg coproduct of quasi-symmetric functions
Let \(\Delta _{{{\mathrm{\#}}}}\) be the coproduct of \(\mathcal {Q}\) dual to the Heisenberg product of \(\Sigma \):
Since the Heisenberg product is a sum of terms of various degrees (32), the Heisenberg coproduct is a finite sum of the form
with \(0\le \deg (f_i)\) and \(\deg (f'_i)\le \deg (f)\le \deg (f_i)+\deg (f'_i)\). The terms corresponding to \(\deg (f)= \deg (f_i)=\deg (f'_i)\) and to \(\deg (f)=\deg (f_i)+\deg (f'_i)\) are the coproducts \(\Delta _{{{\mathrm{*}}}}(f)\) and \(\Delta _{{{\mathrm{\cdot }}}}(f)\), respectively.
Let \(\mathbf {1}+\mathbf {X}\) denote the alphabet \(\mathbf {X}\) together with a new variable \(x_0\) smaller than all the others and with the property \(x_0^k=x_0\) for any natural k. Let
be the Cartesian product of the alphabets \(\mathbf {1}+\mathbf {X}\) and \(\mathbf {1}+\mathbf {Y}\) with reverse lexicographic ordering and with the variable \((x_0,y_0)\) removed. We can suggestively denote \((\mathbf {1}+\mathbf {X})\times (\mathbf {1}+\mathbf {Y})-\mathbf {1}\) by \(\mathbf {X}+\mathbf {Y}+\mathbf {X}\mathbf {Y}\), although the order is given properly by the former expression.
The following result was obtained in conversation with Arun Ram.
Theorem 12.1
For any \(f\in \mathcal {Q}\),
Proof
We have to show that, with respect to the pairing (62),
for all \(\gamma \), \(\alpha \) and \(\beta \) compositions of n, p and q, respectively. Let us fix a composition \(\gamma \) of n and let k the length of \(\gamma \). Denote the set of indices of \(M_\gamma (\mathbf {X}+\mathbf {Y}+\mathbf {X}\mathbf {Y})\) by
Consider the set \( \mathcal {A}_{\alpha ,\beta } = \bigl \{M\in \mathcal {M}_{\alpha ,\beta }^n\mid w(M)=\gamma \bigr \} \) and define the map
as follows: given \((i_1,j_1)<\cdots <(i_k,j_k)\), let \(\widetilde{M}=(\widetilde{m}_{ij})\) be a matrix of zeros big enough to set \(\widetilde{m}_{j_\ell i_\ell }=\gamma _\ell \) (as usual in these proofs, we start the indices in 0). Then, remove all zero rows and columns, except those with index 0; let us call M to the result. Since (0, 0) is not a possible index, we have \(m_{00}=0\). Thus, \(M\in \mathcal {M}_{\alpha ,\beta }^n\) where \(\alpha \) is the composition obtained by adding all the rows of M but the first, and analogously with \(\beta \) and the rows of M.
The map \(\psi \) is surjective, since, given some \(M\in \mathcal {A}_{\alpha ,\beta }\), we can build a sequence of indices in \(\mathcal {Y}\) by reading the nonzero entries of M, say \(m_{uv}\), and considering the pairs (v, u) lexicographically ordered. Therefore, we can write
where \((xy)_q^\gamma \) denotes the monomial \((x_{i_1}y_{i_1})^{\gamma _1}\cdots (x_{i_k}y_{i_k})^{\gamma _k}\) for \(q= \bigl ((i_1,j_1),\ldots ,(i_k,j_k)\bigr )\). Collecting together the x’s and y’s establishes a bijection between the terms of the last sum indexed over \(\psi ^{-1}(M)\) and the terms of \(M_\alpha (\mathbf {X})M_\beta (\mathbf {Y})\). Indeed, take a term from this product, given by indices \(i_{r_1}<\cdots <i_{r_k}\) and \(j_{s_1}<\cdots <j_{s_\ell }\), and build the pairs \((j_{s_u},i_{r_v})\) such that \(m_{v,u}\not =0\). We also have to consider the pairs \((0,i_{r_v})\) and \((j_{s_u},0)\) according to nonzero entries in the first row and column of M. Ordering these indices it is clear that they belong to \(\psi ^{-1}(M)\) and this is the inverse process of grouping x’s and y’s.
Then, we can write
which obviously implies the equation (63). \(\square \)
We can express the dual of the isomorphism in Theorem 10.1 in term of alphabets in the full dual of \(\Sigma \), which is \(\widehat{\mathcal {Q}}=\prod _{n\ge 0}\mathcal {Q}_n\). The pairing \(\langle \,,\rangle : \Sigma \times \widehat{\mathcal {Q}}\rightarrow \Bbbk \) is defined by
where \(f_n\) and \(g_n\) are the restrictions of f and g to the homogeneous components of degree n, and \(\langle \,,\rangle _n\) is the pairing defined in (62).
For this, given an alphabet \(\mathbf {X}\) we define its exponential, \({\mathbf {e}}(\mathbf {X})\), by
where the divided power \(\mathbf {X}^{(n)}\) is the set
We endow \({\mathbf {e}}(\mathbf {X})\) with the reverse lexicographic order. With this notation the following equation holds:
where the equality is considered as ordered sets. Indeed, denote by \((x)_k\) the monomial \(x_{i_1}\cdots x_{i_k}\) with \(i_1<\cdots <i_k\). Then, given \((x)_k(y)_\ell < (x')_{k'}(y')_{\ell '}\) in \({\mathbf {e}}(\mathbf {X+Y})\), it is immediate to see that either \((y)_\ell <(y')_{\ell '}\) or \((y)_\ell =(y')_{\ell '}\) and \((x)_k<(x')_{k'}\), which is the definition of the order in the left hand side. Clearly, the same argument applies in the other direction.
Theorem 12.2
The dual of the isomorphism \(\psi \) from \((\Sigma ,{{\mathrm{\cdot }}},\Delta _{{{\mathrm{\cdot }}}})\) to \((\Sigma ,{{\mathrm{\#}}},\Delta _{{{\mathrm{\cdot }}}})\) of Theorem 10.1 with respect to the pairing \(\langle \,,\rangle \), is the isomorphism \(\psi ^*\) from \((\widehat{\mathcal {Q}},\cdot ,\Delta _{{{\mathrm{\#}}}})\) to \((\widehat{\mathcal {Q}},\cdot ,\Delta _{{{\mathrm{\cdot }}}})\) given by
Proof
We have to show that \(\bigl \langle \psi (X_\gamma ),f\bigr \rangle = \bigl \langle X_\gamma ,\psi ^*(f)\bigr \rangle \). Observe that, from the definition of the pairing, it is enough to prove this equation for each degree. Moreover, it is enough to prove it for the generators of the algebra \((\Sigma ,{{\mathrm{\cdot }}})\) since, for g and \(g'\) generators
Next, we prove the duality for the set of generators \(X_{(n)}\) for \(n\ge 0\), and for \(f=M_\alpha \) where \(\alpha \) is a composition of n. In this case we have \(\psi (X_{(n)})=X_{(n)}\) and the equation \(\bigl \langle X_{(n)},M_\alpha \bigr \rangle = \bigl \langle X_{(n)}, M_\alpha \bigl ({\mathbf {e}}(\mathbf {X})\bigr ) \bigr \rangle = \delta _{(n),\alpha }\) is immediately verified. \(\square \)
Endowed with the coproduct \(\Delta _{{{\mathrm{\#}}}}\), the algebra \(\mathcal {Q}\) is a graded connected Hopf algebra, in duality with the graded connected Hopf algebra \((\Sigma ,{{\mathrm{\#}}},\Delta )\).
We finish this section by expressing the antipode of this Hopf algebra in terms of the alphabets.
First, define the evaluation of quasi-symmetric functions on the the opposite of an alphabet \(\mathbf {X}\) by the equation
for any composition \(\alpha =(a_1,\ldots ,a_r)\) [compare with the definition of \(M_\alpha \) in (61)].
Next, we define the alphabet
as the disjoint union of the Cartesian powers \(\mathbf {X}^n\) under reverse lexicographic order. For instance \((x_3,x_1,x_2)<(x_2,x_2)<(x_1,x_3,x_2)\).
Theorem 12.3
The antipode of the Hopf algebra of quasi-symmetric functions \((\mathcal {Q},\cdot ,\Delta _{{{\mathrm{\#}}}})\) is:
Proof
By Theorem 12.1, it is enough to prove that \(M_\alpha \bigl (\mathbf {X}+(-\mathbf {X})^* + \mathbf {X} (-\mathbf {X})^* \bigr )=0\) for any alphabet \(\mathbf {X}\) and for any composition \(\alpha \). We illustrate the argument for a composition with only one part: \(\alpha =(a)\), the argument for a composition with several parts is essentially the same.
By selecting variables from each of the three alphabets \(\mathbf {X}\), \((-\mathbf {X})^*\), and \(\mathbf {X} (-\mathbf {X})^*\), we can write
It is easy to see that the first sum cancels with the terms with \(r=1\) of the second sum, while the remaining terms of the second sum cancel with the last sum. \(\square \)
Notes
Recall that a composition of a positive integer n is a way to write it as a sum of positive integers (with the order of the summands taken into account, i.e. (2,1) and (1,2) are different compositions of 3).
References
Aguiar, M.: Infinitesimal bialgebras, pre-Lie and dendriform algebras. In: Hopf algebras, Lecture Notes in Pure and Applied Mathematics, vol. 237, pp. 1–33. Dekker, New York (2004)
Aguiar, M., Sottile, F.: Structure of the Malvenuto–Reutenauer Hopf algebra of permutations. Adv. Math. 191(2), 225–275 (2005)
Aguiar, M., Swapneel, M.: Monoidal Functors, Species and Hopf Algebras, CRM Monograph Series, vol. 29. American Mathematical Society, Providence (2010)
Bergeron, F., Labelle, G., Leroux, P.: Combinatorial Species and Tree-like Structures. Cambridge University Press, Cambridge (1998)
Briand, E., Orellana, R., Rosas, M.: The stability of the Kronecker product of Schur functions. J. Algebra 331, 11–27 (2011)
Brown, K.S.: Semigroup and ring theoretical methods in probability. In: Dlab, V. (ed.) Representations of Finite Dimensional Algebras and Related Topics in Lie Theory and Geometry, Fields Inst. Commun., vol. 40, pp. 3–26. American Mathematical Society, Providence (2004)
Etingof, P., Golberg, O., Hensel, S., Liu, T., Schwendner, A., Vaintrob, D., Yudovina, E.: Introduction to representation theory. http://www-math.mit.edu/~etingof/replect.pdf (2011)
Fauser, B., Jarvis, P.D., King, R.C.: Hopf Algebras, distributive (Laplace) pairings and hash products: a unified approach to tensor product decompositions of group characters. ArXiv e-prints (2013)
Garsia, A.M., Reutenauer, C.: A decomposition of Solomon’s descent algebra. Adv. Math. 77(2), 189–262 (1989)
Geissinger, L.: Hopf algebras of symmetric functions and class functions. In: Combinatoire et représentation du groupe symétrique (Actes Table Ronde C.N.R.S., Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976). Lecture Notes in Math., vol. 579, pp. 168–181. Springer, Berlin (1977)
Gelfand, I.M., Krob, D., Lascoux, A., Leclerc, B., Retakh, V.S., Thibon, J.-Y.: Noncommutative symmetric functions. Adv. Math. 112(2), 218–348 (1995)
Gessel, I.: Multipartite \(P\)-partitions and inner products of skew Schur functions. In: Combinatorics and Algebra (Boulder, Colo., 1983), Contemp. Math., vol. 34, pp. 289–317. American Mathematical Society, Providence (1984)
Guo, L., Keigher, W.: Baxter algebras and shuffle products. Adv. Math. 150(1), 117–149 (2000)
Hazewinkel, M.: Symmetric functions, noncommutative symmetric functions and quasisymmetric functions. Acta Apl. Math. 75, 55–83 (2003)
Hazewinkel, M.: Symmetric functions, noncommutative symmetric functions and quasisymmetric functions ii. Acta Apl. Math. 85, 319–340 (2005)
Howe, R.: Perspectives on invariant theory: Schur duality, multiplicity free actions and beyond. In: The Schur Lectures (1992), Israel Math. Conf. Proc., Bar-Ilan Univ., vol. 8, pp. 1–182. Dekker, Bar-Ilan University, Ramat Gan (1995)
Littlewood, D.E.: The inner plethysm of S-functions. Can. J. Math. 10, 1–16 (1958)
Littlewood, D.E.: Products and plethysms of characters with orthogonal, symplectic and symmetric groups. Can. J. Math. 10, 17–32 (1958)
Macdonald, I.G.: Symmetric functions and Hall polynomials, 2nd edn. Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York (1995). With contributions by A. Zelevinsky, Oxford Science Publications
Malvenuto, C.: Produits et coproduits des fonctions quasi-symétriques et de l’algèbre des descents. Ph.D. thesis, Laboratoire de combinatoire et d’informatique mathématique (LACIM), Univ. du Québec à Montréal (1993)
Malvenuto, C., Reutenauer, C.: Duality between quasi-symmetric functions and the Solomon descent algebra. J. Algebra 177(3), 967–982 (1995)
Montgomery, S.: Hopf algebras and their actions on rings. In: CBMS Regional Conference Series in Mathematics, vol. 82, Published for the Conference Board of the Mathematical Sciences, Washington (1993)
Moreira, W.: Products of representations of the symmetric group and non-commutative versions. Ph.D. thesis, Texas A&M University (2008)
Murnaghan, F.D.: The analysis of the Kronecker products of irreducible representations of the symmetric group. Am. J. Math. 60, 761–787 (1938)
Rota, G.-C., Stein, J.A.: Plethystic algebras and vector symmetric functions. Proc. Natl. Acad. Sci. USA 91(26), 13062–13066 (1994)
Rota, G.-C., Stein, J.A.: Plethystic hopf algebras. Proc. Natl. Acad. Sci. USA 91(26), 13057–13061 (1994)
Schocker, M.: The descent algebra of the symmetric group. In: Dlab, V., Ringel, C.M. (eds.) Representations of Finite Dimensional Algebras and Related Topics in Lie Theory and Geometry, Fields Institute Communications, vol. 40, pp. 145–161. American Mathematical Society, Providence (2004)
Solomon, L.: A Mackey formula in the group ring of a Coxeter group. J. Algebra 41(2), 255–264 (1976)
Street, R.: Wreaths, mixed wreaths and twisted coactions. arXiv:1610.07281 [math.CT]
Street, R.: Weighted tensor products of Joyal species, graphs and charades. SIGMA 12(005), 1–20 (2016)
Thibon, J.-Y.: Hopf algebras of symmetric functions and tensor products of symmetric group representations. Int. J. Algebra Comput. 1(2), 207–221 (1991)
Weintraub, S.: Representation Theory of Finite Groups: Algebra and Arithmetic, Graduate Studies in Mathematics, vol. 59. American Mathematical Society, Providence (2003)
Zelevinsky, A.V.: Representations of finite classical groups. In: Lecture Notes in Mathematics, vol. 869. Springer, Berlin (1981)
Acknowledgements
We thank the referee for the many interesting suggestions and illuminating questions and references that together with a detailed list of typos and other mistakes, helped us to improve many aspects of the current work.
Author information
Authors and Affiliations
Corresponding author
Additional information
Este artigo é dedicado à amizade e ensinamentos de Antonio Paques.
Aguiar supported in part by NSF Grants DMS-0302423 and DMS-1401113. Walter Ferrer Santos would like to thank Csic-UDELAR, Conycit-MEC, Uruguay and Anii, Uruguay. We thank Universidad de la República and Texas A&M University where most of this work was completed between 2004 and 2006.
Appendices
Part 4. Appendix
The proofs
In this “Appendix” we provide the postponed proofs of the technical lemmas used in the paper.
1.1 Proof of Lemma 3.2
Proof
To define the bijection \(\Upsilon \rightarrow \mathcal {M}_{\alpha ,\beta }^n\), we start by splitting the interals [1, p] and [1, q] as below:
where \(\alpha =(a_1,\dots ,a_k)\) and \(\beta =(b_1,\dots ,b_s)\). Given an element \(v=\sigma \times \tau \in S_p\times S_q\) we consider the shuffles \(\zeta _\alpha (\sigma )\in {\text {Sh}}(\alpha )\) and \(\zeta _\beta (\tau )\in {\text {Sh}}(\beta )\) characterized by the equations
with \(u\in S_\alpha \) and \(v\in S_\beta \). To simplify the notation, we write \(\zeta _\alpha =\zeta _\alpha (\sigma )\) and \(\zeta _\beta =\zeta _\beta (\tau )\). We further split each interval \(E_i\) and \(F_j\) as below:
such that
for \(i=1,\dots ,k\) and \(j=1,\dots ,s\). Observe that with these definitions we have the decomposition of the interval [1, n] into
Define the matrix \(M_{\sigma \times \tau }\) of dimension \((k+1)\times (s+1)\) whose entries are
The matrix \(M_{\sigma \times \tau }\) belongs to \(\mathcal {M}_{\alpha ,\beta }^n\). Assume that \(i\not =0\). Since \(\zeta _\alpha (E''_i)\subseteq [n-q+1,p]\subseteq \bigsqcup _{j=1}^s \bigl (n-q +\zeta _\beta (F''_j)\bigr )\), we get
On the other hand, if \(i=0\), then, by (70), the sum of \(m_{0j}\) for \(j=0,\dots ,s\), coincides with \({\#}[p+1,n]=n-p\).
Next we show that the matrix \(M_{\sigma \times \tau }\) does not depend on the choice of representative of the coset \((S_p\times _nS_q)v\). Let \(x\in S_{n-q}\), \(y\in S_{p+q-n}\), and \(z\in S_{n-p}\), so that \(x\times y\times z\in S_p\times _nS_q\). Consider the representative \(v'=\sigma '\times \tau '\) where
Let \(\zeta '_\alpha \) and \(\zeta '_\beta \) the shuffles associate to \(v'\). As \(\zeta _\alpha (E'_i)\subseteq [1,n-q]\), then \((x\times y) \bigl (\zeta _\alpha (E'_i)\bigr ) = x\bigl (\zeta _\alpha (E'_i)\bigr )\). But we also have \(x\bigl (\zeta _\alpha (E'_i)\bigr ) = \zeta '_\alpha (E_i)=\zeta '_\alpha (\tilde{E}'_i)\sqcup \zeta '_\alpha (\tilde{E}''_i)\), where \(E_i=\tilde{E}'_i\sqcup \tilde{E}''_i\) is the decomposition of \(E_i\) corresponding to the shuffle \(\zeta '_\alpha \), that satisfies \(\zeta '_\alpha (\tilde{E}'_i) \subseteq [1,n-q]\) and \(\zeta '_\alpha (\tilde{E}''_i) \subseteq [n-q+1,p]\). In summary, \(x\bigl (\zeta _\alpha (E'_i)\bigr ) \subseteq \zeta '_\alpha (\tilde{E}'_i)\). Interchanging the roles of \(\zeta _\alpha \) and \(\zeta '_\alpha \) we obtain an equality, which implies that \(m_{i0}={\#}E'_i = {\#}\tilde{E}'_i = m'_{i0}\), where \(m'_{ij}\) are the entries of the matrix \(M_{v'}\). This proves the equality of the first row of the matrices. The argument for the other rows is similar.
The matrix \(M_v\) do not depend on the choice of representative of \(v(S_\alpha \times S_\beta )\), since the shuffles satisfying (67) are the same for all the elements on this coset. In conclusion, the matrix \(M_v\) depends only on the double cosets \((S_p\times _nS_q)v(S_\alpha \times S_\beta )\).
Next we show that the parabolic subgroup \(S_{p(M_v)}\) is \(S_\alpha \times _n^\upsilon S_\beta \). An element of \(S_\alpha \times _n^\upsilon S_\beta \) can be written as \(x\times y\times z\) where
Evaluating at \(\zeta _\alpha (E'_i)\) we deduce that \(\zeta _\alpha \sigma _{a_i}(E'_i) = x(E'_i)\) and conclude that \(\sigma _{a_i}(E'_i)=E'_i\). Proceeding in a similar manner with the other decompositions we obtain
for all \(i=1,\dots ,k\) and \(j=1,\dots ,s\).
This decomposition can be further refined. Evaluating as above at the subsets \(X_{ij}=\zeta _\alpha (E''_i)\cap \zeta _\beta (F'_j)\), we obtain the equality
Now, \( \zeta _\alpha \sigma _{a_i} \bigl ( \zeta _\alpha ^{-1}(X_{ij}) \bigr ) \subseteq \zeta _\alpha (E''_i) \) and also \( \zeta _\beta \tau _{b_j} \bigl ( \zeta _\beta ^{-1}(X_{ij}) \bigr ) \subseteq \zeta _\beta (F'_j) \). From the above equality we conclude that \( \zeta _\alpha \sigma _{a_i} \bigl ( \zeta _\alpha ^{-1}(X_{ij}) \bigr ) \subseteq \zeta _\alpha (E''_i)\cap \zeta _\beta (F'_j) \), and then \( \sigma _{a_i} \bigl ( \zeta _\alpha ^{-1}(X_{ij}) \bigr ) \subseteq \zeta _\alpha ^{-1}(X_{ij}) \). This inclusion is actually an equality, since both sets have the same cardinality. Therefore, we get the following refinment of (71)
Note that \({\#}X_{ij}=m_{ij}\), and thus the previous decomposition shows that \(x\times y\times z\) belongs to \(S_{p(M)}\).
The map \(\upsilon \mapsto M_\upsilon \) is invertible, since from the entries of the matrix \(M_\upsilon \) we can recover the shuffles \(\zeta _\alpha \) and \(\zeta _\beta \), which are in the same double coset as \(\upsilon \). \(\square \)
1.2 Proof of Lemma 7.5
Proof
As \(\eta \) and \(\tau \) are fixed throughout this lemma, we write \(\varphi =\varphi _{\eta ,\tau }\). Let \(x,y\in F_i\cap \varphi ^{-1} E_j\) with \(x<y\). Consider z such that \(x<z<y\). Therefore, \(x,y\in F_i\) and, since \(F_i\) is an interval, we conclude that \(z\in F_i\).
On the other hand \(\varphi (x), \varphi (y)\in E_j\). Since \(\tau \in \mathcal {B}_\beta \), then \(\mathrm {Id}\times \tau \) is increasing in \(F_i\):
In order to prove that \(\varphi (z)\) also belongs to \(E_j\), we consider the following cases:
-
(1)
Assume that \(j=0\). Then, \(\varphi (x),\varphi (y)\in E_0=[p+1,n]\). Since \((\eta \times \mathrm {Id})\) is the identity on that interval, this implies that \(\beta _0(\mathrm {Id}\times \tau )(x)\) and \(\beta _0(\mathrm {Id}\times \tau )(y)\) are in \([p+1,n]\). But \(\beta _0^{-1}[p+1,n] = [n-q+1, 2n-p-q]\) and \(\beta _0\) is increasing in that set. Therefore, the three terms in (73) belong to \([n-q+1,2n-p-q]\) and, applying \((\eta \times \mathrm {Id})\beta _0\), which is increasing on this set, we obtain that \(\varphi (x)<\varphi (z)<\varphi (y)\).
-
(2)
Assume that \(j>0\). Consider the cases:
-
(a)
Assume \(i=0\). In this case we have \(x,z,y\in F_0=[1,n-q]\). Then, applying \(\mathrm {Id}\times \tau |_{F_0}=\mathrm {Id}\) we continue in the same set. The permutation \(\beta _0\) sends increasingly \([1,n-q]\) into \([p+q-n+1,p]\). In this last interval, \(\eta \) is also increasing. Thus, the inequality (73) implies that \(\varphi (x)<\varphi (z)< \varphi (y)\).
-
(b)
Assume \(i>0\). We have that \(x,y,z\in F_j\subset [n-q+1,n]\). Applying \(\mathrm {Id}\times \tau \) we have that the terms of (73) are also in \([n-q+1,n]\). If \((\mathrm {Id}\times \tau )(x) \in [n-q+1,2n-p-q]\), then \(\beta _0(\mathrm {Id}\times \tau )(x)\in [p+1,n]\) and \(\varphi (x)\in [p+1,n]=E_0\), which contradicts the assumption \(j>0\). Therefore, the terms in (73) belong to \([2n-p-q+1, n]\). The permutation \(\beta _0\) maps increasingly this interval into \([1,p+q-n]\), and \(\eta \) is also increasing in that image. Thus, we conclude that \(\varphi (x)<\varphi (z)<\varphi (y)\).
-
(a)
In all the cases we obtain that \(\varphi (x)<\varphi (z)<\varphi (y)\), and since \(\varphi (x)\) and \(\varphi (y)\) belong to the interval \(E_j\), we deduce that \(\varphi (z)\in E_j\). This proves that \(F_i \cap \varphi ^{-1}E_j\) is an interval.
Notice that along the way we also proved that \(\varphi \) is increasing in the intervals \(F_i \cap \varphi ^{-1}E_j\) as well as the assertions concerning the images.
The fact that the intervals \(F_i \cap \varphi ^{-1}E_{j}\) are disjoint follows immediately from the fact that the sets \(E_{j}\), for \(j=0,\dots ,r\), and the sets \(F_{i}\), for \(i=0,\dots ,s\), are disjoint. This finishes the proof. \(\square \)
1.3 Proof of Lemma 7.6
Proof
For the matrix \(M=\{m_{ij}\}\), denote by \(s_{ij}\) the sum of the entries \(m_{k\ell }\) of M for \((k,\ell )\le (i,j)\) with respect to the lexicographical order of pairs. We define \(R_{00} = [1,s_{00}]\) and \(R_{ij} = [s_{k\ell }, s_{ij}]\) where \(s_{ij}\) covers \(s_{k\ell }\). Observe that some of the intervals \(R_{ij}\) may be empty. Also note that \({\#}R_{ij}=m_{ij}\).
The sequence \((R_{00},R_{01},\ldots , R_{sr})\) is a pseudo-partition of the interval [n] and \(\gamma \in \mathcal {B}_{c(M)}\) if and only if \(\gamma \) is increasing in \(R_{ij}\) for all \(i\in \{0,\ldots ,s\}\) and \(j\in \{0,\dots ,r\}\).
Since \(M\in \mathcal {M}_{\alpha ,\beta }\) and therefore, \(\sum _{j}{\#}(R_{ij})=\sum _j m_{ij} = {\#}F_i\), it follows that
Moreover, if \(\eta \in {\text {Sh}}(p+q-n,n-q)\) and \(\tau \in \mathcal {B}_\beta ^\eta \), then \(F_i\cap \varphi _{\eta ,\tau }^{-1}E_j = R_{ij}\). This can be seen from the fact both sets are intervals with the same cardinal and from the following relation:
In particular, we deduce that \(\varphi _{\eta ,\tau }\) is increasing in \(R_{ij}\).
Given \((\xi ,\eta ,\sigma ,\tau )\in S_{\alpha ,\beta }(M)\), we will show that \(g_{\xi ,\eta }(\sigma ,\tau )\in \mathcal {B}_{c(M)}\). To prove this, since \(\varphi _{\eta ,\tau }|_{R_{ij}}\) is increasing and \(\varphi _{\eta ,\tau }R_{ij} \subseteq E_j\), we observe that
is also increasing. According to Lemma 7.5, the images of \(R_{ij}\) under the previous permutation are in [1, p] or \([p+1,n]\), where \(\xi \) is increasing. Therefore, left multiplying by \(\xi \) we deduce that \(g_{\xi ,\eta }(\sigma ,\tau )\) is increasing in \(R_{ij}\), which proves that it belongs to \(\mathcal {B}_{c(M)}\).
We prove now that \(\psi \) is bijective. Given \(\gamma \in \mathcal {B}_{w(M)}\), we show that there exists a unique quadruple \((\xi ,\eta ,\sigma ,\tau )\in S_{\alpha ,\beta }(M)\) such that \(\psi (\xi ,\eta ,\sigma ,\tau )=\gamma \).
Assume there exists such a quadruple. Using the fact that \(E_j=\bigcup _i\varphi _{\eta ,\tau }R_{ij}\), we deduce that
This proves the uniqueness of the permutation \(\xi (\sigma \times \mathrm {Id})\), in other words, it is the only permutation which maps \(E_j\) increasingly into the set on the right side; and this implies the uniqueness of \(\xi \) and \(\sigma \). Therefore, we have that \( (\eta \times \mathrm {Id})\beta _0(\mathrm {Id}\times \tau ) = (\sigma \times \mathrm {Id})^{-1}\xi ^{-1}\gamma \).
Thus, \(\eta \) is characterized by the image of \([1,n-q]\) under the permutation on the right, which is \(\eta [p+q-n+1,p]\). The uniqueness of \(\tau \) follows immediately.
Given \(\gamma \in \mathcal {B}_{c(M)}\), to construct \((\xi ,\eta ,\sigma ,\tau )\) we note that
and, thus, we can construct a permutation \(\mu \) such that (75) is verified, increasingly mapping \(E_j\) into \(\gamma \bigl (\bigcup _i R_{ij}\bigr )\). This permutation can be written as \(\mu =\xi (\sigma \times \mu ')\) with \(\xi \in {\text {Sh}}(p,n-p)\), \(\sigma \in S_p\) and \(\mu '\in S_{n-p}\). Since \(\mu \) is increasing on \(E_0=[p+1,n]\) we conclude that \(\mu '=\mathrm {Id}_{n-p}\), and from the monotony on \(E_j\) with \(j>0\) we deduce that \(\sigma \in \mathcal {B}_\alpha \). In the same way as before, we construct \(\eta \) by mapping the interval \([1,n-q]\) and for this, we will show that
In particular, for \(i=0\), we obtain the desired property to define \(\eta \). We then consider \(\beta _0^{-1} (\eta \times \mathrm {Id})^{-1} (\sigma \times \mathrm {Id})^{-1}\gamma \), which equals \(\mathrm {Id}\times \tau \) for some \(\tau \in S_p\). Using (77) for \(i>0\) we conclude that \(\tau \in \mathcal {B}_\beta \); and it follows from (76) that the constructed \(\tau \) belongs to \(\mathcal {B}_\beta ^\eta (M)\).
It remains to prove (77). Take \(x_1,x_2\in F_i\) with \(x_1<x_2\). Then, \(x_1\in R_{ij_1}\) and \(x_2\in R_{ij_2}\) for some \(j_1\le j_2\). Assume that \(j_1=j_2\), then \(\gamma (x_1)<\gamma (x_2)\). In this case, we have \(\gamma (x_1)=\xi (\sigma \times \mathrm {Id})(e_1)\) and \(\gamma (x_2)=\xi (\sigma \times \mathrm {Id})(e_2)\) with \(e_1,e_2\in E_j\). Since \(\sigma \) is increasing in \(E_j\) we obtain that \(e_1<e_2\) as desired.
On the other hand, if \(j_1<j_2\), then \(e_1\in E_{j_1}\) and \(e_2\in E_{j_2}\) and the conclusion follows easily as all the elements of \(E_{j_1}\) are smaller than those of \(E_{j_2}\). \(\square \)
Rights and permissions
About this article
Cite this article
Aguiar, M., Ferrer Santos, W. & Moreira, W. The Heisenberg product: from Hopf algebras and species to symmetric functions. São Paulo J. Math. Sci. 11, 261–311 (2017). https://doi.org/10.1007/s40863-017-0072-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40863-017-0072-x