Formal Power Series and Algebraic Combinatorics Séries Formelles et Combinatoire Algébrique Tianjin, China 2007

Hopf algebras of diagrams

G. H. E. Duchamp^{a}, J-G. Luque^{b}, J-C. Novelli^{b}, C. Tollu^{a}, F. Toumazet^{a}

Abstract. We investigate several Hopf algebras of diagrams related to the Quantum Field Theory of Partitions and whose product comes from WSym or WQSym, the algebras of word symmetric or quasi-symmetric functions. Bases of these algebras are indexed either by bipartite graphs (labelled or unlabelled) or by packed matrices (with integer or set coefficients). Realizations on bi-words are exhibited, and it is shown how these algebras fit well into a commutative diagram. Hopf deformations and dendriform structures are also considered for some algebras in the picture.

Résumé. Nous étudions plusieurs algèbres de Hopf de diagrammes liées à la Théorie Quantique des Champs des Partitions et dont le produit provient de WSym et WQSym. Ces algèbres ont des bases indexées à des graphs bipartis (étiquetés ou non) ou à des matrices tassées (à cœfficients entiers ou ensemblistes). On donne des réalisations sur des bi-mots et on montre comment ces algèbres s’intègrent dans un diagramme commutatif. Pour certaines d’entre elles, on établit des structures dendriformes et l’existence de déformations préservant la structure de Hopf.

1. Introduction

The purpose of the present paper is twofold. First, we want to tighten the links between a body of Hopf algebras related to physics and the realm of noncommutative symmetric functions, although the latter domains are no longer disconnected [10, 5, 8]. Second, we aim at providing examples of combinatorial shifting (a generic way of deforming algebras) and expounding how MQSym could be considered a construction scheme including its first appearance with integers [7] as a special case. Our paper is the continuation of [3], as we go deeper into the connections between combinatorial Hopf algebras and the Feynman diagrams of a special Field Theory introduced by Bender, Brody and Meister [1]. These Feynman diagrams arose in the expansion of

(1)  G(z) = exp\{ ∑_{n≥1} \frac{L_{n}}{n!}( z\frac{∂}{∂x}) ^{n}\} exp\{ ∑_{m≥1} V_{m}\frac{x^{m}}{m!}\}|_{x=0}

and are bipartite finite graphs with no isolated vertex, and edges weighted with integers. They are in bijective correspondence with packed matrices of integers up to a permutation of the columns and a permutation of the rows. The algorithm constructing the matrix from the associated diagram uses as an intermediate structure a particular packed matrix whose entries are sets. Such set matrices appear when one computes the internal product in WSym [15] and in WQSym [11, 13], then isomorphic to the Solomon-Tits algebra. In this context, it becomes natural to investigate Hopf algebras of (set) packed matrices whose product comes from WSym or WQSym. The paper is organized as follows. In Section 2, the connection between the Quantum Field Theory of Partitions and a three-parameter deformation of the Hopf algebra LDIAG of labelled diagrams is explained. We introduce the shifting principle (Subsection 2.2) and give two illustrations. The first one enables to see LDIAG as the shifted version of an algebra of unlabelled diagrams. The second one (Subsection 2.3) explains how to carry over some constructions from algebras of integer matrices to algebras of set matrices. In Section 3, we investigate eight Hopf algebras of matrices related to labelled or unlabelled diagrams. In particular, we exhibit realizations on biwords and show how some of these are dendriform bialgebras.

1991 Mathematics Subject Classification. Primary 05E99, Secondary 16W30, 18D50, 81T18.

Key words and phrases. Hopf algebras, Bi-partite graphs, dendriform structures.

2  G. H. E. Duchamp^{a}, J-G. Luque^{b}, J-C. Novelli^{b}, C. Tollu^{a}, F. Toumazet^{a}

Acknowledgements. The first author would like to thank Bodo Lass for an illuminating seminar talk on the algebraic treatment of bipartite graphs. He is also greatly indebted to Karol Penson for clearing up the physical origin of the diagrams.

2. Hopf algebras coming from physics

2.1. Algebras of diagrams. Many computations carried out by physicists reduce to the ‘product formula’, a bilinear coupling between two Taylor expandable functions, introduced by C.M. Bender, D.C. Brody, and B.K. Meister in their celebrated Quantum field theory of partitions (henceforth referred to as QFTP) [1]. For an example of such a computation derived from a partition function linked to the Free Boson Gas model, see [17]. To make the story short, the last expansion of the formula involves a summation over all diagrams of a certain type [1, 4] a labelled version of which is described below. These diagrams are bipartite graphs with multiple edges. It is in order to show that every (combinatorial) sequence of integers can be represented by Feynman diagrams subjected to suited rules that Bender, Brody and Meister [1] introduced QFTP as a toy model. The case when the expansions of the two functions occurring in the product formula have constant term 1 is of special interest. The functions can then be presented as exponentials which can be regarded as ”free” through the classical Bell polynomials expansion [5] or as coming from the integration of a Frechet one-parameter group of operators [4]. Working out the formal case, one sees that the coupling results in a summation without multiplicity of a certain kind of labelled bipartite graphs which are equivalent, as a data structure, to pairs of unordered partitions of the same set {1,2,...,n}. The sum can be reduced to a sum of topologically inequivalent diagrams (a monoidal basis of DIAG), at the cost of introducing multiplicities. Theses graphs, which can be considered as the Feynman diagrams of the QFTP, generate a Hopf algebra compatible with the product and co-addition on the multipliers. Interpreting DIAG as the Hopf homomorphic image of its planar counterpart, LDIAG, gives access to the noncommutative world and to deformations: the product is deformed by taking into account, through two variables, the number of crossings of edges involved in the superposition or the transposition of two vertices, the coproduct is obtained by interpolating. This gives the final picture of [17]. Labelled diagrams can be identified with their weight functions which are mappings ω : ℕ^{+} × ℕ^{+} → ℕ such that the supporting subgraph

(2)  Γ_{ω} = {(i,j) ∈ ℕ^{+} × ℕ^{+} | w(i,j) ≠ 0}

has projections i.e., pr_{1}(Γ_{ω}) = [1,p]; pr_{2}(Γ_{ω}) = [1,q] for some p,q ∈ ℕ^{+} .

Figure 1. A labelled diagram of shape 3 × 4.

Let ldiag denote the set of labelled diagrams. With any element d of ldiag, one can associate the monomial 𝕃^{α(d)}𝕍^{β(d)}, called its multiplier, where α(d) (resp. β(d)) is the “white spot type” (resp. the “black spot type”) i.e., the multi-index (α_{i})_{i∈ℕ^{+}} (resp. (β_{i})_{i∈ℕ^{+}} ) such that α_{i} (resp. β_{i}) is the number of white spots (resp. black spots) of degree i. For example, the multiplier of the labelled diagram of Figure 1 is 𝕃^{(0,0,2,0,1)}𝕍^{(1,1,1,0,1)}. One can endow ldiag with an algebra structure denoted by LDIAG where the sum is the formal sum and the product is the shifted concatenation of diagrams, i.e. consists in juxtaposing the second diagram to the right of the first one and then adding to the labels of the black spots (resp. of the white spots) of the second diagram the number of black spots (resp. of white spots) of the first diagram. Then the application sending a diagram to its multiplier is an algebra homomorphism. Moreover, the black spots (resp. white spots) of diagram d can be permuted without changing the monomial 𝕃^{α(d)}𝕍^{β(d)}. The classes of labelled diagrams up to this equivalence relation (permutations of white – or black – spots among themselves) are naturally represented by unlabelled diagrams. The set of unlabelled diagrams will be henceforth denoted by diag.

1 1 2 2 3  1 1 2 2 3 1 1 2 2 3

Figure 2. Equivalent labelled diagrams.

The set diag can also be endowed with an algebra structure, denoted by DIAG, e.g. as the quotient of LDIAG by the equivalence classes of labelled diagrams. In DIAG, the product of d_{1} by d_{2} is basic concatenation, i.e. simply consists in juxtaposing d_{2} to the right of d_{1} [5].

2.2. Shifted algebras and applications. A three-parameter deformation of LDIAG, LDIAG(q_{c},q_{s},t) has been recently constructed, which specializes to both LDIAG (q_{c} = q_{s} = t = 0) and MQSym (q_{c} = q_{s} = t = 1). This construction involves a deformation of the algebra structure, which can be seen as a particular case of the rather general principle of shifting. This principle will be further exemplified in the sequel of the present paper.

Lemma 2.1. (Shifting lemma.) Let A = ⊕_{α∈M} A_{α} be an algebra graded (as a vector space) on a commutative monoid (M,+). Let s : (M,+) ↦ (End_{alg}(A),∘) be an homomorphism such that the modified law, given by

(3)  x ∗_{s}y:= x s_{α} (y) for all x ∈ A_{α} , y ∈ A

is M-graded. Then, if A is associative, so is the deformed law ∗_{s}.

Such a procedure, whenever possible, will be called the shifting of A by the shift s. We now recall the construction of LDIAG(q_{c},q_{s}) as the shifting of another algebra of diagrams.

Let M = ℕ^{(ℕ^{+} )} be the additive monoid of multidegrees and M^{+} = M − {0} the associated semigroup. A labelled diagram d with p white spots and q black spots can be encoded by a word W (d) ∈ (M^{+} )^{∗} as

(4)  W (d) = α_{1}α_{2}··· α_{q},

where, for all i ≤ p, the i-th letter of α_{j} is the number of edges joining the black spot j and the white spot i (see Figure 3).

The edges adjacent to the blackspots correspond successively to the multidegrees (2) (two edges to the first white spot), (1,3,1) (one edge to the first and third white spots and three edges to the second one), (0,1,2) and (0,1). Thus the code is W (d) = (2)(1,3,1)(0,1,2)(0,1).

Figure 3. Coding a diagram with a word of multidegrees.

Let k be a ring, one can skew the product in k⟨M^{+} ⟩, counting crossings and superpositions as for LDIAG.

Proposition 2.2. Let k be a ring, q_{c},q_{s} ∈ k, and consider the deformed graded law on k⟨M^{+} ⟩ defined by

(5)  \{ \begin{matrix}1_{(M^{+} )^{∗}}∗ w & = & w ∗ 1_{(M^{+} )^{∗}} = w, \\ αu ∗ βv & = & α(u ∗ βv) + q_{c}^{|αu||β|}β(αu ∗ v) + q_{s}^{|α||β|}q_{c}^{|u||β|}(α + β)(u ∗ v), \end{matrix}

where α,β ∈ M^{+} , u,v ∈ (M^{+} )^{∗}, the weight |α| of multidegree α is just the sum of its coordinates and the weight |u| of the word u = α_{1}··· α_{t} is |u| = ∑ _{i=1}^{t} |α_{i}|. This product is associative.

The algebra (k⟨M^{+} ⟩,+,∗) is denoted by MLDIAG (q_{c},q_{s}). In the shifted version, the product amounts to performing all superpositions of black spots and/or crossings of edges, weighting them with the corresponding value q_{s} or q_{c}, powered by the number of crossings of edges. This construction is reminiscent, up to the deformations, of Hoffman’s [12] and its variants [2, 9], and also of an older one, the infiltration product in computer science [14, 6]. The shift going from MLDIAG (q_{c},q_{s}) to itself is the following. Let α_{1}α_{2}··· α_{p} ∈ (M^{+} )^{∗} and n ∈ ℕ. One sets

(6)  s_{n}(α_{1}α_{2}··· α_{p}) := (0^{n}α_{1})(0^{n}α_{2})··· (0^{n}α_{p})

where 0^{n}α is the insertion of n zeroes on the left of α. Note that n ↦ s_{n} is a homomorphism of monoids (ℕ,+) → End_{alg}(MLDIAG (q_{c},q_{s})).

2.3. Another application of the shifting principle. The Hopf operations of MQSym as described in [7] do not depend on the fact that the entries of the matrices are integers. For a pointed set (X,x_{0}) (i.e., x_{0} ∈ X), let us denote by MQSym_{k}(X,x_{0}) the k-vector space spanned by rectangular matrices with entries in X with no line or column filled with x_{0} (which plays now the rôle of zero) and the product, coproduct, unit and counit as in [7]. It is clear that MQSym_{k}(X,x_{0}) is a Hopf algebra and that the correspondence (X,x_{0}) ↦ MQSym_{k}(X,x_{0}) is a functor from the category of pointed sets (endowed with the strict arrows, that is, the mappings ϕ : (X,x_{0}) → (Y,y_{0}) such that ϕ(x_{0}) = y_{0} and ϕ(X −{x_{0}}) ⊂ Y −{y_{0}}) to the category of k-Hopf algebras. In the particular case when X = 2^{(N^{+} )}, that is, finite subsets of ℕ^{+} , and x_{0} = ∅, one can define a shift by a translation of the elements. More precisely, for F ∈ 2^{(N^{+} )} and M a p × q matrix with coefficients in 2^{(N^{+} )}, one sets

(7)  s_{n}(F) = \{x + n\}_{x∈F} , s_{n}(M) = (s_{n}(M[i,j]))_{{1≤i≤p \atop 1≤j≤q}} .

One can check that the s_{n} define a shift on MQSym_{k}(2^{(N^{+} )},∅) for the grading given by

(8)  MQSym_{k}(2^{(N^{+} )},∅)_{n} = span of the matrices whose maximum number in the entries is n.

For example, the vector space generated by the packed matrices whose entries partition the set {1,2,··· n} is closed by the product. This is the algebra SMQSym. We shall soon see that this corresponds to labelling also the edges of a labelled diagram with numbers from 1 to k.

3. Packed matrices and related Hopf algebras

3.1. The combinatorial objects. In the sequel, we will represent different kinds of diagrams using matrices to emphasize the parallel between this construction and the construction of MQSym ([7]).

3.1.1. Set packed matrices. Since the computations are the same in many cases, let us begin with the most general case and explain how one recovers the other cases by algebraic means. Let us consider the set lldiag of bipartite graphs with white and black vertices, and edges, all three labelled by intervals [1,p]. The diagrams ldiag are obtained by erasing the numbers the edges of one such element. The set lldiag is in direct bijection with set packed matrices, that are matrices containing disjoint subsets of [1,n] for some n ∈ ℕ with no line or column filled with empty sets such that the union of all subsets is [1,n] itself. The bijection consists in putting k in the cell (i,j) of the matrix if the edge labelled k connects the white dot labelled i with the black dot labelled j. Figure 4 shows an example of such a matrix.

( \begin{matrix}\{3\} & \{6\} & \{2\} \\ ∅ & \{1,5\} & \{4\} \end{matrix} )

Figure 4. A set packed matrix.

Note that set packed matrices are in bijection with pairs of set compositions, or, ordered partition of [1,n]: given a set packed matrix, compute the ordered sequence of the unions of the elements in the same row (resp. column). For example, the set packed matrix of Figure 4 gives rise to the two set compositions {2,3,6},{1,4,5} and {3},{1,5,6},{2,4}. Given two set compositions Π and Π′, define M_{ij} := Π_{i}∩ Π′_{j}. It is then easy to compute that the generating series depending on n of such matrices is given by the square of the ordered Bell numbers, that is sequence A122725 in [16].

3.1.2. Integer packed matrices. As already said, if one forgets the ordering of the edges of an element of lldiag, one recovers an element of ldiag. Its matrix representation is an integer packed matrix, that is, a matrix with no line or column filled with zeros. The encoding is simple: m_{ij} is equal to the number of edges between the white spot labelled i and the black spot labelled j. Note that, from the matrix point of view, it consists in replacing the subsets by their cardinality. Figure 5 shows an example of such a matrix.

( \begin{matrix}1 & 1 & 1 \\ 0 & 2 & 1 \end{matrix} )

Figure 5. An integer packed matrix.

The generating series of such matrices depending on n is given by sequence A120733 of [16].

3.1.3. Other packed matrices. During our study, we will also need diagrams where one forgets about the labels of the white spots, or about the labels of the black spots, or about all labels. Those three classes of diagrams are respectively in bijection with matrices up to a permutation of the rows, a permutation of the columns, and simultaneous permutations of both.

3.2. Word quasi-symmetric and symmetric functions. Let us recall briefly the definition of two already known combinatorial Hopf algebras that will be useful in the sequel.

3.2.1. WQSym. We use the notations of [13]. The word quasi-symmetric functions are the noncommutative polynomial invariants of Hivert’s quasi-symmetrizing action [11]

(9)  WQSym(A) := ℂ⟨A⟩^{𝔖(A)_{QS}}.

When A is an infinite alphabet, WQSym(A) is a graded Hopf algebra whose basis is indexed by set compositions, or, equivalently, packed words. Recall that packed words are words w on the alphabet [1,k] where if i ≠ 1 appears in w, then i−1 also appears in w. The bijection between both sets is that w_{i} = j iff i is in the j-th part of the set composition (see Figure 6 for an example).

cbbadacb  ⟷  [{4,6},{2,3,8},{1,7},{5}]

Figure 6. A packed word and its corresponding set composition.

By definition, WQSym is generated by the polynomials

(10)  WQ_{u}:= ∑_{pack(w)=u} w,

where u = pack(w) is the packed word having the same comparison relations between all elements as w. The product in WQSym is given by

(11)  WQ_{u}WQ_{v} = ∑_{w∈u⋆_{W}v}WQ_{w},

where the convolution u ⋆_{W}v of two packed words is defined by

(12)  u ⋆_{W}v = ∑_{w_{1},w_{2};w=w_{1}w_{2} packed pack(w_{1})=u, pack(w_{2})=v} w.

The coproduct is given by

(13)  ΔWQ_{w}(A) = ∑_{u,v;w∈u⋓_{W}v}WQ_{u}⊗ WQ_{v}

where u ⋓_{W} v denotes the packed shifted shuffle that is the shuffle of u and v′= v[max(u)], that is the word v′_{i}= v_{i}+ max(u). The dual algebra WQSym^{∗} of WQSym is a subalgebra of the Parking quasi-symmetric functions PQSym. This algebra has a multiplicative basis denoted by F^{w}, where the product is the shifted concatenation, that is u.v[max(u)].

3.2.2. WSym. The algebra of word symmetric functions WSym, first defined by Rosas and Sagan in [15], where it is called the algebra of symmetric functions in noncommuting variables, is the Hopf subalgebra of WQSym generated by

(14)  W_{π} := ∑_{sp(u)=π} WQ_{u},

where sp(u) is the (unordered) set partition obtained by forgetting the order of the parts of its corresponding set composition. Its dual WSym^{∗} is the quotient of WQSym^{∗}

(15)  WSym^{∗} = WQSym^{∗}/_{J}

where J is the ideal generated by the polynomials F^{u}− F^{v} with u and v corresponding to the same set partition. We denote by F^{sp(u)} the image of F^{u} by the canonical surjection.

4. Hopf algebras of set packed matrices

4.1. Set matrix quasi-symmetric functions. The construction of the Hopf algebra SMQSym over set packed matrices is a direct translation of the construction of MQSym ([11, 7]). Consider the linear subspace spanned by the elements SMQ_{M}, where M runs over the set of set packed matrices. We denote by h(M) the number of rows of M. Then define

(16)  SMQ_{P}SMQ_{Q}:= ∑_{R∈ (P,Q)}SMQ_{R}

where the augmented shuffle of P and Q, (P,Q) is defined as follows: let Q′ be obtained from Q by adding the greatest number inside P to all elements inside Q. Let r be an integer between max(p,q) and p + q, where p = h(P) and q = h(Q). Insert rows of zeros in the matrices P and Q′so as to form matrices P̃ and Q̃′of height r. Let R be the matrix obtained by gluing Q̃′to the right of P̃. The set (P,Q) is formed by all the matrices with no row of 0’s obtained this way. For example,

(17)

SMQ_{( \begin{matrix}\{3,4\} & \{1\} \\ \{2\} & ∅ \end{matrix})} SMQ_{(_{\{2,3,4\} \{1\}})} = SMQ_{( \begin{matrix}\{3,4\} & \{1\} & ∅ & ∅ \\ \{2\} & ∅ & ∅ & ∅ \\ ∅ & ∅ & \{6,7,8\} & \{5\} \end{matrix})} + SMQ_{( \begin{matrix}\{3,4\} & \{1\} & ∅ & ∅ \\ \{2\} & ∅ & \{6,7,8\} & \{5\} \end{matrix})}

+SMQ_{( \begin{matrix}\{3,4\} & \{1\} & ∅ & ∅ \\ ∅ & ∅ & \{6,7,8\} & \{5\} \\ \{2\} & ∅ & ∅ & ∅ \end{matrix})} + SMQ_{( \begin{matrix}\{3,4\} & \{1\} & \{6,7,8\} & \{5\} \\ \{2\} & ∅ & ∅ & ∅ \end{matrix})} + SMQ_{( \begin{matrix}∅ & ∅ & \{6,7,8\} & \{5\} \\ \{3,4\} & \{1\} & ∅ & ∅ \\ \{2\} & ∅ & ∅ & ∅ \end{matrix})} .

The coproduct ΔSMQ_{M} is defined by

(18)  ΔSMQ_{A}= ∑_{A=\binom{A_{1}}{A_{2}}} SMQ_{std(A_{1})}⊗ SMQ_{std(A_{2})},

where std(A) denotes the standardized of the matrix A, that is the matrix obtained by the substitution a_{i} ↦ i, where a_{1} < ···< a_{n} are the integers appearing in A. For example,

(19)  ΔSMQ_{( \begin{matrix}\{2,4\} & \{1\} \\ \{6\} & \{3,5\} \end{matrix})} = SMQ_{( \begin{matrix}\{2,4\} & \{1\} \\ \{6\} & \{3,5\} \end{matrix})} ⊗ 1 + SMQ_{(_{\{2,3\} \{1\}})}⊗ SMQ_{(_{\{3\} \{1,2\}})}+ 1 ⊗ SMQ_{( \begin{matrix}\{2,4\} & \{1\} \\ \{6\} & \{3,5\} \end{matrix})}

Rather than checking the compatibility between the product and the coproduct, one can look for a realization of SMQSym, here in terms of noncommutative bi-words, that will later give useful guidelines to select or understand homomorphisms between the different algebras.

4.2. Realization of SMQSym. A noncommutative bi-word is a word over an alphabet of bi-letters \left⟨{a_{i} \atop b_{j}}\right⟩ with

i,j ∈ ℕ where a_{i} and b_{j} are letters of two distinct ordered alphabets A and B. We will denote by ℂ\left⟨{A \atop B}\right⟩ the algebra of

the (potentially infinite) polynomials over the bi-letters \left⟨{a \atop b}\right⟩ for the product ⋆ defined by

(20)  \left⟨{u_{1} \atop v_{1}}\right⟩ ⋆ \left⟨{u_{2} \atop v_{2}}\right⟩ = \left⟨{u_{1}.u_{2} \atop v_{1}.v_{2}[max(v_{1})]}\right⟩ ,

where v_{1}.v_{2}[k] denotes the concatenation of v_{1} with the word v_{2} whose letters are shifted by k and max(v_{1}) the maximal letter of v_{1}. For example,

(21)  \left⟨{142 \atop 236}\right⟩ ⋆ \left⟨{24 \atop 31}\right⟩ = \left⟨{14224 \atop 23697}\right⟩

Lemma 4.1. The product ⋆ is associative.

One associates to each set packed matrix the bi-word such that its ith bi-letter is the coordinate in which the letter i appears in the matrix. For example,

(22)  bi-word( \begin{matrix}\{2,4\} & \{1\} \\ \{6\} & \{3,5\} \end{matrix} ) = \left⟨{a_{1}a_{1}a_{2}a_{1}a_{2}a_{2} \atop b_{2}b_{1}b_{2}b_{1}b_{2}b_{1}}\right⟩ .

A bi-word is said bi-packed if its two words are packed. The bi-packed of a bi-word is the bi-word obtained by packing its two words. The set packed matrices are obviously in bijection with the bi-packed bi-words. Let \left⟨{u \atop v}\right⟩ be a bi-packed bi-word. Then

Theorem 4.2.

• The algebra SMQSym can be realized on bi-words by

(23)  SMQ\left⟨{u \atop v}\right⟩:= ∑_{bipacked\left⟨{u′ \atop v′}\right⟩=\left⟨{u \atop v}\right⟩} \left⟨{u′ \atop v′}\right⟩ .

• SMQSym is a Hopf algebra.

• SMQSym is isomorphic as a Hopf algebra to the graded endomorphisms of WQSym:

(24)  End_{gr}WQSym = ⨁_{n∈ℕ}WQSym_{n}⊗ WQSym _{n}^{∗}

through the Hopf homomorphism

(25)  ϕ ( SMQ\left⟨{u \atop v}\right⟩) = WQ_{u}⊗ F^{v}.

Indeed, from the point of view of the realization, the coproduct of SMQSym is given by the usual trick of noncommutative symmetric functions, considering the alphabet A as an ordered sum of two mutually commuting alphabets A′ˆ+A′′, hence being a homomorphism for the product.

4.3. Set matrix half-symmetric functions.

4.3.1. The Hopf algebra SMRSym. Let SMRSym be the subalgebra of SMQSym generated by the polynomials SMR_{π_{1},Π_{2}} indexed by a set partition π_{1} and a set composition Π_{2} and defined by

(26)  SMR_{(π_{1},Π_{2})} := ∑_{sp(Π_{1})=π_{1}} SMQ_{Π_{1},Π_{2}} .

(27)

SMR_{\{\{13\},\{4\},\{2\}\},[\{123\},\{4\}]} = SMQ_{( \begin{matrix}\{1,3\} & ∅ \\ ∅ & \{4\} \\ \{2\} & ∅ \end{matrix})} + SMQ_{( \begin{matrix}\{1,3\} & ∅ \\ \{2\} & ∅ \\ ∅ & \{4\} \end{matrix})} + SMQ_{( \begin{matrix}∅ & \{4\} \\ \{1,3\} & ∅ \\ \{2\} & ∅ \end{matrix})}

+SMQ_{( \begin{matrix}∅ & \{4\} \\ \{2\} & ∅ \\ \{1,3\} & ∅ \end{matrix})} + SMQ_{( \begin{matrix}\{2\} & ∅ \\ ∅ & \{4\} \\ \{1,3\} & ∅ \end{matrix})} + SMQ_{( \begin{matrix}\{2\} & ∅ \\ \{1,3\} & ∅ \\ ∅ & \{4\} \end{matrix})}

Note that a pair constituted by a set partition and a set composition is equivalent to a set packed matrix up to a permutation of its rows. Hence, the realization on bi-words follows: for example,

(28)  SMR_{\{\{13\},\{4\},\{2\}\},[\{123\},\{4\}]}= ∑_{i_{1},i_{2},i_{3} distinct j_{1}<j_{2}} \left⟨{a_{i_{1}} a_{i_{2}} a_{i_{1}} a_{i_{3}} \atop b_{j_{1}}b_{j_{1}}b_{j_{1}}b_{j_{2}}}\right⟩

Proposition 4.3.

• SMRSym is isomorphic to ⊕WSym_{n}⊗ WQSym _{n}^{∗}.

• SMRSym is a co-commutative Hopf subalgebra of SMQSym.

4.3.2. The Hopf algebra SMCSym. Forgetting about the order of the columns instead of the rows leads to another Hopf algebra, SMCSym, a basis of which is indexed by the pairs (Π_{1},π_{2}) (Π_{1} is a set composition and π_{2} is a set partition). It is the quotient of SMQSym by the polynomials

(29)  SMQ_{Π_{1},Π_{2}} − SMQ_{Π_{1},Π′_{2}}

where sp(Π_{2}) = sp(Π′_{2}). Note that this quotient can be brought down to the bi-words. We will denote by α the canonical surjection:

(30)  α(SMQ_{Π_{1},Π_{2}} ) =: SMC_{Π_{1},sp(Π_{2})}

The algebra SMCSym is spanned by the SMC_{Π_{1},π_{2}} where Π_{1} is a set composition and π_{2} is a set partition.

Proposition 4.4.

• SMCSym is isomorphic to ⊕WQSym_{n}⊗ WSym_{n}^{∗},

• SMCSym is a Hopf algebra.

Note that both SMRSym and SMCSym have the same Hilbert series, given by the product of ordered Bell numbers by unordered Bell numbers. This gives one new example of two different Hopf structures on the same combinatorial set since SMCSym is neither commutative nor cocommutative.

4.4. Set matrix symmetric functions. The algebra SMSym of set matrix symmetric functions is the subalgebra of SMCSym generated by the polynomials

(31)  SM_{π_{1},π_{2}} = ∑_{sp(Π_{1})=π_{1}} SMR_{Π_{1},π_{2}}

For example,

(32)  SM_{\{\{1,3\},\{4\},\{2\}\},\{\{1,2,3\},\{4\}\}} = ∑_{i_{1},i_{2},i_{3} distinct j_{1}<j_{2}} \left⟨{a_{i_{1}}a_{i_{3}} a_{i_{1}} a_{i_{2}} \atop b_{j_{1}}b_{j_{1}}b_{j_{1}}b_{j_{2}}}\right⟩

Theorem 4.5.

• SMSym is a co-commutative Hopf subalgebra of SMCSym.

• SMSym is isomorphic as an algebra to End_{gr}WSym = ⨁ WSym_{n}⊗ WSym_{n}^{∗}.

• SMSym is isomorphic to the quotient of SMRSym by the ideal generated by the polynomials SMR_{π_{1},Π_{2}} − SMR_{π_{1},Π′_{2}} with sp(Π_{2}) = sp(Π′_{2}).

5. Hopf algebras of packed integer matrices

5.1. Matrix quasi-symmetric functions. Let SA be the set of packed set matrices such that if one reads the entries by columns from top to bottom and from left to right, then one obtains the numbers 1 to n in the usual order.

(33)  ( \begin{matrix}\{1,2\} & ∅ \\ ∅ & \{4\} \\ \{3\} & ∅ \end{matrix} )  ( \begin{matrix}\{1,3\} & ∅ \\ ∅ & \{4\} \\ \{2\} & ∅ \end{matrix} )

Figure 7. An element of SA and an element not in SA.

Let us consider the subalgebra MQSym′of SMQSym generated by the elements of SA.

For example,

(34)  MQ_{( \begin{matrix}2 & 0 & 1 \\ 0 & 3 & 4 \end{matrix})} = ∑_{{i_{1}<i_{2} \atop j_{1}<j_{2}<j_{3}}} \left⟨{a_{i_{1}} a_{i_{1}} a_{i_{1}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} \atop b_{j_{1}}b_{j_{1}}b_{j_{3}}b_{j_{2}}b_{j_{2}}b_{j_{2}}b_{j_{3}}b_{j_{3}}b_{j_{3}}b_{j_{3}}}\right⟩

Theorem 5.1. MQSym′is isomorphic as a Hopf algebra to MQSym.

5.2. Matrix half-symmetric functions. We reproduce the same construction as for set packed matrices. We define three algebras MRSym (resp. MCSym, MSym) of packed matrices up to a permutation of rows (resp. of columns, resp. of rows and columns).

5.2.1. The Hopf algebra MRSym. Let MRSym be the subalgebra of MQSym generated by the polynomials

(35)  MR_{A}:= ∑ MQ_{B}

where B is obtained from A by any permutation of its rows. As for SMRSym, the realization of MRSym on bi-words is automatic. For example,

(36)  MR_{( \begin{matrix}2 & 1 & 0 \\ 0 & 3 & 4 \end{matrix})} = MQ_{( \begin{matrix}2 & 1 & 0 \\ 0 & 3 & 4 \end{matrix})} + MQ_{( \begin{matrix}0 & 3 & 4 \\ 2 & 1 & 0 \end{matrix})} = ∑_{{i_{1}≠i_{2} \atop j_{1}<j_{2}<j_{3}}} \left⟨{a_{i_{1}} a_{i_{1}} a_{i_{1}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} a_{i_{2}} \atop b_{j_{1}}b_{j_{1}}b_{j_{3}}b_{j_{2}}b_{j_{2}}b_{j_{2}}b_{j_{3}}b_{j_{3}}b_{j_{3}}b_{j_{3}}}\right⟩ .

Theorem 5.2.

(1) MRSym is a co-commutative Hopf subalgebra of MQSym,

(2) MRSym is also the subalgebra of SMRSym generated by the elements SMR_{A} where A is any matrix such that each element of the set composition of its columns is an interval of [1,n].

5.2.2. The Hopf algebra MCSym. We construct the algebra MCSym as the quotient of MQSym by the ideal generated by the polynomials MQ_{A}− MQ_{B} where B can be obtained from A by a permutation of its columns.

Theorem 5.3.

(1) MCSym is a commutative Hopf algebra,

(2) MCSym is isomorphic as a Hopf algebra to the subalgebra of SMCSym generated by the elements SMC_{A}, such that each element of the set partition of its columns is an interval of [1,n].

5.2.3. Dimensions of MRSym and MCSym. The dimension of the homogeneous component of degree n of MRSym or MCSym is equal to the number of packed matrices such that the sum of the entries is equal to n, up a permutation of the rows. Let us denote by PMuR(p,q,n) the number of such p × q matrices. One has obviously

(37)  dimMRSym_{n} = ∑_{1≤p,q≤n} PMuR(p,q,n).

The integers PMuR(p,q,n) can be computed through the induction

(38)  PMuR(p,q,n) = MuR(p,q,n) − ∑_{1≤k,l≤p,q} \binom{q}{l} PMuR(k,l,n),

where MuR(p,q,n) is the number of p×q matrices up to a permutations of the rows with the sums of the entries equal to n. Solving this induction and substituting it in equation (37), one gets

(39)  dimMRSym_{n} = ∑_{i=1}^{n+1}(−1)^{n−i} T_{n+1,i+1} MuR(n,i,n),

where T_{n,k} = ∑ _{j=0}^{n−k}(−1)^{n−k−j} \binom{j+k−1}{j} is known as the number of minimal covers of an unlabeled n-set that cover k points of that set uniquely (see sequence A056885 of [16]). The generating series of the T_{n,k} is

∑_{i,j} T_{i,j}x^{i}y^{j} = \frac{1 − x}{(1 + x) (1 − x − xy)} .

The integer MuR(n,i,n), computed via the Pólya enumeration theorem, is the coefficient of x^{n} in the cycle index Z(G_{n,i}), evaluated over the alphabet 1 + x + ··· + x^{n}+ ··· , of the subgroup G_{n_{,}i} of 𝔖_{in} generated by the permutations σ.σ[n].σ[2n]. ···.σ[in] for σ ∈ 𝔖_{n} (here . denotes the concatenation).

This coefficient is also the number of partitions N_{n,i} of n objects with i colors whose generating series is

∑_{n} N_{n,i}x^{n} = ∏_{k} ( \frac{1}{1 − x^{k}} ) ^{\binom{i+k}{i}} .

Hence

Proposition 5.4.

(40)  dimMRSym_{n} = ∑_{i=1}^{n+1}(−1)^{n−i} T_{n+1,i+1} N_{n,i}.

The first values are

Hilb(MRSym) = Hilb(MCSym) = 1 + t + 4t^{2}+ 16t^{3}+ 76t^{4}+ 400t^{5}+ 2356t^{6}+ 15200t^{7}+ 106644t^{8}
+ 806320t^{9}+ 6526580t^{10}+ ···

(41)

5.3. Matrix symmetric functions. The algebra MSym of matrix symmetric functions is the subalgebra of MCSym generated by

(42)  ∑_{σ∈𝔖_{n}} MR_{B},

where B is obtained from A by any permutation of its rows.

Theorem 5.5.

(1) MSym is a commutative and co-commutative Hopf subalgebra of MCSym.

(2) MSym is isomorphic as a Hopf algebra to the subalgebra of SMSym generated by the elements SM_{A}, such that each element of the set partition of its columns is an interval of [1,n].

(3) MSym is isomorphic to the quotient of MRSym by the ideal generated by the polynomials MR_{A}− MR_{B} where B can be obtained from A by a permutation of its columns.

The following diagram commutes

[figure: SMQSym; MQSym; SMRSym; MRSym; SMCSym; MCSym; SMSym; MSym]

6. Dendriform structures over SMQSym

6.1. Tridendriform structure. One defines three product rules over bi-words as follows:

(1) \left⟨{u_{1} \atop v_{1}}\right⟩ ≺ \left⟨{u_{2} \atop v_{2}}\right⟩ = \left⟨{u_{1} \atop v_{1}}\right⟩ ⋆ \left⟨{u_{2} \atop v_{2}}\right⟩ if max(u_{1}) > max(u_{2}), and 0 otherwise.

(2) \left⟨{u_{1} \atop v_{1}}\right⟩ ∘ \left⟨{u_{2} \atop v_{2}}\right⟩ = \left⟨{u_{1} \atop v_{1}}\right⟩ ⋆ \left⟨{u_{2} \atop v_{2}}\right⟩ if max(u_{1}) = max(u_{2}), and 0 otherwise.

(3) \left⟨{u_{1} \atop v_{1}}\right⟩ ≻ \left⟨{u_{2} \atop v_{2}}\right⟩ = \left⟨{u_{1} \atop v_{1}}\right⟩ ⋆ \left⟨{u_{2} \atop v_{2}}\right⟩ if max(u_{1}) < max(u_{2}), and 0 otherwise.

Proposition 6.1. The algebra of bi-words endowed with the three product rules ≺,∘, and ≻ is a tridendriform algebra. Moreover, SMQSym is stable by those three rules. So it is a tridendriform algebra.

More precisely, one has:

HOPF ALGEBRAS OF DIAGRAMS  11

(1) SMQ\left⟨{u \atop v}\right⟩≺ SMQ\left⟨{u′ \atop v′}\right⟩ = ∑_{{w=x.y∈u⋆_{W}u′ \atop |x|=|u|; max(y)<max(x)}} SMQ_{\left⟨{w \atop vv′[max(v)]}\right⟩}

(2) SMQ\left⟨{u \atop v}\right⟩∘ SMQ\left⟨{u′ \atop v′}\right⟩ = ∑_{{w=x.y∈u⋆_{W}u′ \atop |x|=|u|; max(y)=max(x)}} SMQ_{\left⟨{w \atop vv′[max(v)]}\right⟩}

(3) SMQ\left⟨{u \atop v}\right⟩≻ SMQ\left⟨{u′ \atop v′}\right⟩ = ∑_{{w=x.y∈u⋆_{W}u′ \atop |x|=|u|; max(y)>max(x)}} SMQ_{\left⟨{w \atop vv′[max(v)]}\right⟩}.

Corollary 6.2. SMCSym, MQSym and MCSym are tridendriform.

6.2. Bidendriform structures. Let us define two product rules ≪=≺ and ≫= ∘+ ≻ on bi-words. We now split the non-trivial parts of the coproduct of the SMQ of SMQSym, as

(1) Δ_{≪} (SMQ_{A}) = ∑_{{A=\binom{B}{C}, A≠B,C \atop max(B)=max(A)}} SMQ_{std(B)}⊗ SMQ_{std(C)}.

(2) Δ_{≫} (SMQ_{A}) = ∑_{{A=\binom{B}{C}, A≠B,C \atop max(C)=max(A)}} SMQ_{std(B)}⊗ SMQ_{std(C)}.

Theorem 6.3. SMQSym is a bidendriform bialgebra. Recall that SMCSym is the quotient of SMQSym by the ideal generated by SMQ_{A}− SMQ_{B} where A and B are the same matrices up to a permutation of their columns, the row containing the maximal element is the same for any element of a given class, so that the left coproduct and the right coproduct are compatible with the quotient. Moreover, the left and right coproduct are internal within MQSym, so that Corollary 6.4. SMCSym and MQSym are bidendriform sub-bialgebras of SMQSym.

6.3. bi-words realization of LDiag(q_{c},q_{s}). Let us define a two-parameter generalization of MQSym. For this purpose, consider bi-words with parameter-commuting bi-letters depending on the biletters as follows:

\begin{matrix}\left⟨{yx \atop zt}\right⟩ = q_{c} \left⟨{xy \atop tz}\right⟩ & if y > x, \\ \left⟨{xx \atop zt}\right⟩ = q_{s} \left⟨{xx \atop tz}\right⟩ & if z < t. \end{matrix} ; (43)

Let us now define the realization as a sum of bi-words of a packed integer matrix with p rows and q columns:

(44)  LD_{M}:= ∑_{{i_{1}<··· <ip \atop j_{1}<··· <jq}} ∏_{a=1}^{n} ∏_{b=p}^{1} \left⟨{i_{a} \atop j_{b}}\right⟩ ^{M_{ij}} .

For example,

(45)  LD_{( \begin{matrix}3 & 5 \\ 1 & 3 \end{matrix})} := ∑_{{i_{1}<i_{2} \atop j_{1}<j_{2}}} \left⟨{i_{1}^{5}i_{1}^{3}i_{2}^{3}i_{2} \atop j_{2}^{5}j_{1}^{3}j_{2}^{3}j_{1}}\right⟩ .

We then have Theorem 6.5.

• The LD generate an algebra,

• The specialization q_{s} = q_{c} = 1 gives back MQSym. For example, one has:

(46)  LD_{( \begin{matrix}2 & 0 \\ 1 & 4 \end{matrix})} ⋆ LD_{(1)} = LD_{( \begin{matrix}2 & 0 & 0 \\ 1 & 4 & 0 \\ 0 & 0 & 1 \end{matrix})} + q_{s}^{5}LD_{( \begin{matrix}2 & 0 & 0 \\ 1 & 4 & 1 \end{matrix})} + q_{c}^{5}LD_{( \begin{matrix}2 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 4 & 0 \end{matrix})} + q_{c}^{5}q_{s}^{2}LD_{( \begin{matrix}2 & 0 & 1 \\ 1 & 4 & 0 \end{matrix})} + q_{c}^{7}LD_{( \begin{matrix}0 & 0 & 1 \\ 2 & 0 & 0 \\ 1 & 4 & 0 \end{matrix})}

since

\begin{aligned}∑_{{i_{1}<i_{2} \atop j_{1}<j_{2}}} \left⟨{i_{1}i_{1}i_{2}i_{2}i_{2}i_{2}i_{2} \atop j_{1}j_{1}j_{2}j_{2}j_{2}j_{2}j_{1}}\right⟩ ⋆ ∑ \left⟨{i \atop j}\right⟩ = & ∑_{{i_{1}<i_{2}<i_{3} \atop j_{1}<j_{2}<j_{3}}} \left⟨{i_{1}^{2}i_{2}^{4}i_{2}i_{3} \atop j_{1}^{2}j_{2}^{4}j_{1}j_{3}}\right⟩ + ∑_{{i_{1}<i_{2}(=i_{3}) \atop j_{1}<j_{2}<j_{3}}} q_{s}^{5} \left⟨{i_{1}^{2}i_{2}i_{2}^{4}i_{2} \atop j_{1}^{2}j_{3}j_{2}^{4}j_{1}}\right⟩ + ∑_{{i_{1}<i_{3}<i_{2} \atop j_{1}<j_{2}<j_{3}}} q_{c}^{5} \left⟨{i_{1}^{2}i_{3}i_{2}^{4}i_{2} \atop j_{1}^{2}j_{3}j_{2}^{4}j_{1}}\right⟩ \\ & + ∑_{{i_{1}(=i_{3})<i_{2} \atop j_{1}<j_{2}<j_{3}}} q_{s}^{2}q_{c}^{5} \left⟨{i_{1}i_{1}^{2}i_{2}^{4}i_{2} \atop j_{3}j_{1}^{2}j_{2}^{4}j_{1}}\right⟩ + ∑_{{i_{3}<i_{1}<i_{2} \atop j_{1}<j_{2}<j_{3}}} q_{c}^{7} \left⟨{i_{3}i_{1}^{2}i_{2}^{4}i_{2} \atop j_{3}j_{1}^{2}j_{2}^{4}j_{1}}\right⟩ . \end{aligned} ; (47)

References

[1] C. M. Bender, D. C. Brody, and B. K. Meister, Quantum field theory of partitions, J. Math. Phys. 40 (1999) 3239

[2] P. Cartier, Fonctions polylogarithmes, nombres polyzêtas et groupes pro-unipotents, Séminaire Bourbaki, Mars 2001, 53ème année, 2000-2001, 885

[3] G.H.E. Duchamp, J.-G. Luque, K.A. Penson, and C. Tollu, Free quasi-symmetric functions, product actions and quantum field theory of partition, Proc. FPSAC/SFCA 2005, Messina, Italy. ArXiv: cs.SC/0412061

[4] G. Duchamp, A.I. Solomon, K.A. Penson, A. Horzela, and P. Blasiak, One-parameter groups and combinatorial physics, Proceedings of the Symposium Third International Workshop on Contemporary Problems in Mathematical Physics (COPROMAPH3) (Porto-Novo, Benin, Nov. 2003), J. Govaerts, M. N. Hounkonnou and A. Z. Msezane (eds.), p.436 (World Scientific Publishing 2004). ArXiv:

    quant-ph/04011262

[5] G. H. E. Duchamp, P. Blasiak, A. Horzela, K. A. Penson, and A. I. Solomon, Feynman graphs and related Hopf algebras, J. Phys: Conference Series (30) (2006) 107, Proc of SSPCM’05, Myczkowce, Poland. ArXiv: cs.SC/0510041

[6] G. Duchamp , M. Flouret, É. Laugerotte., and J.-G. Luque, Direct and dual laws for automata with multiplicities, Theoret. Comp. Sci. 267, 105-120 (2001).

[7] G. Duchamp, F. Hivert, and J.-Y. Thibon, Non commutative functions VI: Free quasi-symmetric functions and related algebras, International Journal of Algebra and Computation 12(5) (2002). ArXiv: math.CO/0105065

[8] G.H.E. Duchamp, A.I. Solomon, P. Blasiak, K.A. Penson, and A. Horzela, A multipurpose Hopf deformation of the algebra Feynman-like diagrams, Group26, New York, 2006. ArXiv: cs.OH/0609107

[9] K. Ebrahimi-Fard and L. Guo, Mixable shuffles, quasi-shuffles and Hopf algebras, J. Algebr. Comb. 24 (2006) 83101.

[10] L. Foissy, Bidendriform bialgebras, trees, and free quasisymmetric functions, to appear in J. Pure and Applied Algebra. ArXiv: math.RA/0505207

[11] F. Hivert, Combinatoire des fonctions quasi-symétriques, Thèse de Doctorat, Marne-La-Vallée, 1999.

[12] M. E. Hoffman, The Hopf algebra structure of multiple harmonic sums, Nuclear Physics B (Proceedings Supplement) 135 (2004), 215-219.

[13] J.-C Novelli and J.-Y. Thibon, Polynomial realizations of some trialgebras, Proc. FPSAC/SFCA 2006, San Diego.

[14] P. Ochsenschläger, Binomialkoeffitzenten und Shuffle-Zahlen, Technischer Bericht, Fachbereich Informatik, T. H. Darmstadt (1981).

[15] M. Rosas and B. Sagan, Symmetric functions in noncommuting variables, Trans. Amer. Math. Soc. 358 (2006) 215-232.

[16] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/~njas/sequences/

[17] A.I. Solomon, G.H.E. Duchamp, P. Blasiak, A. Horzela, and K. A. Penson, Hopf Algebra Structure of a model Quantum Field Theory, Group26, New York, 2006.

(a) Institut Galilée, LIPN, Université de Paris 13 et CNRS, UMR 7030, 99, avenue J.-B. Clément, 93430 Villetaneuse, France

(b) Institut Gaspard Monge, Université de Marne-la-Vallée, 5, boulevard Descartes, Champs-sur-Marne, 77454 Marnela-Vallée Cedex 2, France E-mail address, Gérard Henry Edmond Duchamp: ghed@lipn.univ-paris13.fr E-mail address, Jean-Gabriel Luque: luque@univ-mlv.fr E-mail address, Jean-Christophe Novelli: novelli@univ-mlv.fr E-mail address, Christophe Tollu: ct@lipn.univ-paris13.fr E-mail address, Frédéric Toumazet: ft@lipn.univ-paris13.fr