Séminaire Lotharingien de Combinatoire 68 (2013), Article B68c

A WORD HOPF ALGEBRA BASED ON THE SELECTION/QUOTIENT PRINCIPLE

GÉRARD H. E. DUCHAMP^{1}, NGUYEN HOANG-NGHIA^{1}, AND ADRIAN TANASA^{1,2}

Abstract. We define a Hopf algebra structure on the vector space spanned by packed words using a selection/quotient coproduct. We show that this algebra is free on its irreducible packed words. We also compute the Hilbert series of this Hopf algebra, and we investigate its primitive elements.

1. Introduction

In algebraic combinatorics, one often associates algebraic structures with various sets of combinatorial objects. Such structures are, for example, Hopf algebras on trees, graphs, tableaux, matroids, words, etc.

A first type of combinatorial Hopf algebra structure is constructed using the selection/quotient principle. This simply means that the comultiplication is of the form

Δ(S) = _{∑_{A⊆S+} ; conditions}S[A] ⊗ S/_{A},  (1.1)

where S[A] is a substructure of S and S/_{A} is a quotient.

Examples of such Hopf algebras are the Connes–Kreimer Hopf algebra of Feynman graphs, underlying the combinatorics of perturbative renormalization in quantum field theory [2] or in non-commutative Moyal quantum field theory [10], [11] (the interested reader may also consult [12], [14] for some short reviews of these algebras). For the sake of completeness, let us also mention that similar Hopf algebraic structures have been proposed for quantum gravity spin-foam models, see [7], [13].

Matroid theory has been introduced by Whitney in [15]. A structure of matroid Hopf algebra is defined in [8], where the product is given by the direct sum operation and the coproduct is given by the selection/quotient principle mentioned above.

A second type of combinatorial Hopf algebra structure relies on the selection/complement principle. This means that the comultiplication is of the form

Δ(S) = _{∑_{A⊆S+} ; conditions}S[A] ⊗ [S − A].  (1.2)

Examples of such Hopf algebras are the Loday–Ronco Hopf algebra of planar binary trees [6] or the Hopf algebra of matrix quasi-symmetric functions MQSym [3].

It would thus be interesting to find Hopf algebraic structures on words with a comultiplication not of type (1.2), but of type (1.1). This is the issue we address in this paper.

In this article, we introduce a new Hopf algebraic structure, which we call WMat, on the set of packed words with product given by the shifted concatenation and coproduct given by such a selection/quotient principle. Each letter x_{j}, j ≥ 1, can be seen as the infinite column vector with 1 at the j^{th} place and all other entries zero. WMat has the zero column, x_{0}, as a special element. In graph theory, it would correspond to the self-loop. Using the notion of irreducible element, we prove that WMat is free as an algebra.

gerard.duchamp@lipn.univ-paris13.fr nguyen.hoang@lipn.univ-paris13.fr adrian.tanasa@ens-lyon.org.

2. Algebra structure

2.1. Definitions. Let X be an infinite totally ordered alphabet {x_{i}}_{i≥0} and X^{∗} be the set of words with letters in the alphabet X.

A word w of length n = |w| is a mapping i ↦ w[i] from {1, 2, …, |w|} to X. For a letter x_{i} ∈ X, the partial degree |w|_{x_{i}} is the number of times the letter x_{i} occurs in the word w. We have

|w|_{x_{i}} = ∑_{j=1}^{|w|} δ_{w[j],x_{i}}.  (2.1)

For a word w ∈ X^{∗}, we define the alphabet Alph(w) as the set of its letters, while IAlph(w) denotes the set of indices in Alph(w). In symbols,

Alph(w) = {x_{i} : |w|_{x_{i}} ≠ 0} ; IAlph(w) = {i ∈ ℕ : |w|_{x_{i}} ≠ 0}.  (2.2)

The upper bound sup(w) is the supremum of IAlph(w), i.e.,

sup(w) = sup_{ℕ}(IAlph(w)).  (2.3)

We denote the empty word by 1_{X^{∗}}, and we put sup(1_{X^{∗}}) = 0.

Let us define the substitution operators. Let w = x_{i_{1}} … x_{i_{m}} and ϕ : IAlph(w) ⟶ ℕ, with ϕ(0) = 0. We then have

S_{ϕ}(x_{i_{1}} … x_{i_{m}}) = x_{ϕ(i_{1})} … x_{ϕ(i_{m})}.  (2.4)

Next we define the pack operator of a word w. Let {j_{1}, j_{2}, …, j_{k}} = IAlph(w) \ {0} with j_{1} < j_{2} < ⋯ < j_{k} and define ϕ_{w} as

ϕ_{w}(i) = \begin{cases}m, & if i = j_{m}, \\ 0, & if i = 0. \end{cases}  (2.5)

The corresponding packed word, denoted by pack(w), is S_{ϕ_{w}}(w). A word w ∈ X^{∗} is said to be packed if w = pack(w).

Example 2.1. Let w = x_{1}x_{1}x_{5}x_{0}x_{4}. Then we have pack(w) = x_{1}x_{1}x_{3}x_{0}x_{2}.

Remark 2.2. The presence of the letter x_{0} dramatically influences the picture since there is an infinite number of distinct packed words of weight m (here, the weight is the sum of the indices), which are obtained by adding multiple copies of the letter x_{0}.

Example 2.3. The packed words of weight 2 are x_{0}^{k_{1}}x_{1}x_{0}^{k_{2}}x_{1}x_{0}^{k_{3}}, with k_{1}, k_{2}, k_{3} ≥ 0.

The operator pack : X^{∗} ⟶ X^{∗} is idempotent (pack∘pack = pack). By linear extension, it defines a projector. The image, pack(X^{∗}), is the set of packed words.

Let u, v be two words. We define the shifted concatenation ∗ by

u ∗ v = uT_{sup(u)}(v),  (2.6)

where, for t ∈ ℕ, T_{t}(w) denotes the image of w by S_{ϕ} for ϕ(n) = n + t if n > 0 and ϕ(0) = 0 (that is, all letters are reindexed except x_{0}). It is straightforward to check that, in the case the words are packed, the result of a shifted concatenation is a packed word.

A WORD HOPF ALGEBRA BASED ON THE SELECTION/QUOTIENT PRINCIPLE 3

Definition 2.4. Let k be a field. We define the vector space H = span_{k}(pack(X^{∗})). This space is endowed with a product (on the words) given by

μ :H ⊗ H ⟶ H,
u ⊗ v ⟼ u ∗ v.

Remark 2.5. The product above is similar to the shifted concatenation for permutations (see [3]). Moreover, if u and v are two words in X^{∗}, then sup(u ∗ v) = sup(u) + sup(v). Proposition 2.6. (H, μ, 1_{X^{∗}}) is an associative algebra with unit. Proof. Let u, v, w be three words in H. We have

(u ∗ v) ∗ w = (uT_{sup(u)}(v))T_{sup(u∗v)}(w) = u(T_{sup(u)}(v)(T_{sup(u)+sup(v)})(w)) = u ∗ (v ∗ w). (2.7)

Thus, (H, μ) is associative. On the other hand, for all u ∈ pack(X^{∗}), we have

u ∗ 1_{X^{∗}} = uT_{sup(u)}(1_{X^{∗}}) = u1_{X^{∗}} = u ,

and

1_{X^{∗}} ∗ u = (1_{X^{∗}})T_{sup(1_{X^{∗}})}(u) = (1_{X^{∗}})u = u .

Now observe that pack(1_{X^{∗}}) = 1_{X^{∗}}. This is in fact obvious from the fact that 1_{X^{∗}} = 1_{H}. We conclude that (H, μ, 1_{X^{∗}}) is an associative algebra with unit. □

As already announced in the introduction, we call this algebra WMat. Remark 2.7. The product is non-commutative, for example: x_{1} ∗ x_{1}x_{1} ≠ x_{1}x_{1} ∗ x_{1}.

Let w = x_{k_{1}} … x_{k_{n}} be a word and I ⊆ {1, 2, …, n}. The subword w[I] is defined as x_{k_{i_{1}}} … x_{k_{i_{l}}}, where I = {i_{1}, i_{2}, …, i_{l}} with i_{1} < i_{2} < ⋯ < i_{l}. A further notation that we shall use from here on is I + J for the disjoint union of the two sets I and J. Lemma 2.8. Let u, v be two words, and I ⊂ {1, 2, …, |u|} and J ⊂ {|u| + 1, |u| + 2, …, |u| + |v|}. Then we have

pack(u ∗ v[I + J]) = pack(u[I]) ∗ pack(v[J′]),  (2.8)

where J′ is the set {i − |u| : i ∈ J}. Proof. By direct computation, we have

pack(u ∗ v[I + J]) = pack(uT_{sup(u)}(v)[I + J]) = pack(u[I]T_{sup(u)}(v)[J]).  (2.9)

Furthermore, we have sup(u[I]) ≤ sup(u), and this, together with (2.9), leads to

pack(u[I]T_{sup(u)}(v)[J]) = pack(u[I]T_{sup(u[I])}(v[J′])) = pack(u[I]) ∗ pack(v[J′]). (2.10)
□

Theorem 2.9. Let k⟨X⟩ be equipped with the shifted concatenation. The mapping pack

k⟨X⟩ ⟶^{pack} H  (2.11)

is a homomorphism of associative algebras with unit. Proof. By using Lemma 2.8 with I = {1, 2, …, |u|} and J = {|u|+1, |u|+2, …, |u|+|v|}, the assertion of the theorem follows immediately. □

2.2. WMat is a free algebra. WMat is, by construction, the algebra of the monoid pack(X^{∗}), therefore to check that WMat is a free algebra, it is sufficient to show that pack(X^{∗}) is a free monoid on its letters. In the following diagram, a free monoid is a pair (F (X), j_{X}) where F (X) is a monoid, j_{X} : X → F (X) is a mapping such that for all M ∈ Mon and all f : X → M there exists a unique f_{X} ∈ Hom(F (X), M) such that f = f_{x} ∘ j_{X}.

Set ; Monoids ; X ; M ; F (X) ; f ; j_{X} ; f_{X}

Here we use an “internal” characterization of free monoids in terms of irreducible elements.

Definition 2.10. A packed word w in pack(X^{∗}) is called an irreducible word if and only if it cannot be written in the form w = u ∗ v, where u and v are two non trivial packed words.

Example 2.11. The word x_{1}x_{1}x_{1} is an irreducible word. The word x_{1}x_{1}x_{2} is a reducible word because it can be written as x_{1}x_{1}x_{2} = x_{1}x_{1} ∗ x_{1}.

Proposition 2.12. If w is a packed word, then w can be written uniquely as w = v_{1} ∗ v_{2} ∗ ⋯ ∗ v_{n}, where v_{i} are non-trivial irreducible words, 1 ≤ i ≤ n.

Proof. The i^{th} position of word w is called an admissible cut if sup(w[1 … i]) = inf(w[i + 1 … |w|]) − 1 or sup(w[i + 1 … |w|]) = 0, where inf(w) is the infimum of IAlph(w).

Since the length of word is finite, we may write w = v_{1} ∗ v_{2} ∗ … v_{n}, with n maximal and v_{i} non-trivial, 1 ≤ i ≤ n.

We assume that one word can be written in two ways

w = v_{1} ∗ v_{2} ∗ ⋯ ∗ v_{n}  (2.12)

and

w = v′_{1} ∗ v′_{2} ∗ ⋯ ∗ v′_{m}.  (2.13)

Denoting by k the first number such that v_{k} ≠ v′_{k}, without loss of generality we may suppose that |v_{k}| < |v′_{k}|. From Equation (2.12), the k^{th} position is an admissible cut of w. From Equation (2.13), the k^{th} position is not an admissible cut of w. Thus, we obtain a contradiction. Hence, we have n = m and v_{i} = v′_{i} for all 1 ≤ i ≤ n. □

We thus conclude that pack(X^{∗}) is free as monoid with the packed words as a basis.

3. Bialgebra structure

We now give the definition of the coproduct and prove that the coassociativity property holds.

Definition 3.1. For A ⊂ X, we define w/A = S_{ϕ_{A}}(w) with

ϕ_{A}(i) = \begin{cases}i, & if x_{i} ∉ A, \\ 0, & if x_{i} ∈ A. \end{cases}

For a word u, we define ^{w}/_{u} = ^{w}/_{Alph(u)}.

Definition 3.2. The coproduct of H is given by

Δ(w) = ∑_{I+J={1,...,|w|}} pack(w[I]) ⊗ pack(w[J]/_{w[I]}), for all w ∈ H.  (3.1)

Example 3.3. We have

Δ(x_{1}x_{2}x_{1}) = x_{1}x_{2}x_{1} ⊗ 1_{X^{∗}} + x_{1} ⊗ x_{1}x_{0} + x_{1} ⊗ x_{1}^{2} + x_{1} ⊗ x_{0}x_{1} + x_{1}x_{2} ⊗ x_{0}

+ x_{1}^{2} ⊗ x_{1} + x_{2}x_{1} ⊗ x_{0} + 1_{X^{∗}} ⊗ x_{1}x_{2}x_{1}.

Next, we prove coassociativity.

Let I = {i_{1}, i_{2}, …, i_{n}} and I_{1} = {j_{1}, j_{2}, …, j_{k}} ⊆ {1, 2, …, |I|}, and let α be the mapping

α : I ⟶ {1, 2, …, n},
i_{s} ⟼ s.  (3.2)

Lemma 3.4. Let w ∈ X^{∗} be a word, I be a subset of {1, 2, …, |w|}, and I_{1} ⊂ {1, 2, …, |I|}. Then we have

pack(w[I])[I_{1}] = S_{ϕ_{w[I]}}(w[I′_{1}]),  (3.3)

where I′_{1} is α^{−1}(I_{1}) and ϕ_{w[I]} is the packing map of w[I] that is given in (2.5).

Proof. Using the definition of the packing map ϕ_{w[I]}, we can directly check that Equation (3.3) holds. □

Lemma 3.5. Let w, w_{1}, w_{2} ∈ X^{∗} be words and ϕ be a strictly increasing map from IAlph(w) to ℕ. Then

pack(S_{ϕ}(w)) = pack(w)  (3.4)

and

S_{ϕ}(^{w_{1}}/_{w_{2}}) = ^{S_{ϕ}(w_{1})}/_{S_{ϕ}(w_{2})}.  (3.5)

Proof. In order to prove (3.4), we observe that

pack(S_{ϕ}(w)) = S_{ϕ_{0}}(S_{ϕ}(w)) = S_{ϕ_{0}∘ϕ}(w),  (3.6)

where ϕ_{0} is the packing map which is given in (2.5). Note that both ϕ and ϕ_{0} are strictly increasing maps.

We write I = IAlph(w) = {j_{1}, j_{2}, …, j_{k}}, j_{1} < j_{2} < ⋯ < j_{k}, and j′_{i} = ϕ(j_{i}), i = 1, 2, …, k, so that the image set ϕ(I) is given by ϕ(I) = {j′_{1}, j′_{2}, …, j′_{k}} with j′_{1} < j′_{2} < ⋯ < j′_{k}. From the definition of ϕ_{0}, we have ϕ_{0}(j′_{i}) = i = ϕ_{0}(j_{i}). This leads to

S_{ϕ_{0}∘ϕ}(w) = S_{ϕ_{0}}(w) = pack(w),  (3.7)

from which (3.4) follows in combination with (3.6).

Now we turn to the proof of (3.5). Let I_{2} = Alph(w_{2}) and I′_{2} = Alph(S_{ϕ}(w_{1})). Using this notation, the left-hand side of (3.5) becomes

S_{ϕ}(^{w_{1}}/_{w_{2}}) = S_{ϕ}(S_{ϕ_{I_{2}}}(w_{1})) = S_{ϕ∘ϕ_{I_{2}}}(w_{1}),  (3.8)

and the right-hand side becomes

S_{ϕ}(w_{1})/_{S_{ϕ}(w_{2})} = S_{ϕ_{I′_{2}}}(S_{ϕ}(w_{1})) = S_{ϕ_{I′_{2}}∘ϕ}(w_{1}).  (3.9)

With x_{i} ∈ Alph(w_{1}), there are two cases:

1. If x_{i} ∈ I_{2}, then ϕ_{I_{2}}(i) = 0 and ϕ ∘ ϕ_{I_{2}}(i) = 0 since ϕ is a strictly increasing map.

On the other hand, ϕ(i) ∈ I′_{2}, and this implies ϕ_{I′_{2}} ∘ ϕ(i) = ϕ_{I′_{2}}(ϕ(i)) = 0.

2. If x_{i} ∉ I_{2}, then ϕ_{I_{2}}(i) = i and ϕ ∘ ϕ_{I_{2}}(i) = ϕ(i). On the other hand, since ϕ is a

strictly increasing map, we have ϕ(i) ∉ I′_{2}, and ϕ_{I′_{2}} ∘ ϕ(i) = ϕ(i).

Thus, we have ϕ ∘ ϕ_{I_{2}}(i) = ϕ_{I′_{2}} ∘ ϕ(i). Using this result and (3.8) and (3.9), we arrive at (3.5). □

Lemma 3.6. Let w be a word in H, and I, J, K be three mutually disjoint subsets of {1, 2, …, |w|}. Then

\frac{^{w[K]}/_{w[I]}}{^{w[J]}/_{w[I]}} = ^{w[K]}/_{w[I+J]}.  (3.10)

Proof. Using Lemma 3.5, we have

\frac{^{w[K]}/_{w[I]}}{^{w[J]}/_{w[I]}} = ^{S_{ϕ_{I}} (w[K])}/_{S_{ϕ_{I}} (w[K])} = S_{ϕ_{I}}(^{w[K]}/_{w[J]})

= S_{ϕ_{I}}(S_{ϕ_{J}} (w[K])) = S_{ϕ_{I}∘ϕ_{J}} (w[K]) =^{w[K]} /_{w[I+J]}.

□

Proposition 3.7. The vector space H endowed with the coproduct (3.1) is a coassociative coalgebra with co-unit. The co-unit is given by

ϵ(w) = \begin{cases}1, & if w = 1_{H}, \\ 0, & otherwise. \end{cases}

Proof. We first prove the coassociativity of the coproduct (3.1), that is,

(Δ ⊗ Id) ∘ Δ(w) = (Id ⊗ Δ) ∘ Δ(w).  (3.11)

The left-hand side (3.11) can be written in the form

(Δ ⊗ Id) ∘ Δ(w) = ∑_{I+J={1,...,|w|}} ( ∑_{I_{1}+I_{2}={1,...,|I|}} pack(pack(w[I])[I_{1}])

⊗ pack(^{pack(w[I][I_{2}])}/_{pack(w[I][I_{1}])})) ⊗ pack(^{w[J]}/_{w[I]})

= ∑_{I+J={1,...,|w|]} ( ∑_{I′_{1}+I′_{2}=I} pack(S_{ϕ}(w[I′_{1}])) ⊗ pack(^{S_{ϕ}(w[I′_{2}])}/_{S_{ϕ}(w[I′_{1}])})) ⊗ pack(^{w[J]}/_{w[I]})

s = ∑_{I′_{1}+I′_{2}+J={1,...,|w|}} pack(w[I′_{1}]) ⊗ pack(^{w[I_{2}]}/_{w[I′_{1}]}) ⊗ pack(^{w[J]}/_{w[I_{1}+I_{2}]}).  (3.12)

The right-hand side of (3.11) can be written as

(Id ⊗ Δ) ∘ Δ(w)

= ∑_{I+J={1,...,|w|}} pack(w[I]) ⊗ ( ∑_{J_{1}+J_{2}={1,...,|J|}} pack(pack(^{w[J]}/_{w[I]}))[J_{1}])

⊗pack(^{pack(^{w[J]}/_{w[I]})[J_{2}]}/_{pack(^{w[J]}/_{w[I]})[J_{1}]})))

= ∑_{I+J={1,...,|w|}} pack(w[I]) ⊗ ( ∑_{J′_{1}+J′_{2}=J} pack(^{w[J′_{1}]}/_{w[I]}) ⊗ pack(S_{ϕ}(^{^{w[J′_{2}]}/_{w[I]}}/_{w[J′_{1}]/_{w[I]}})))

= ∑_{I+J={1,...,|w|}} pack(w[I]) ⊗ ( ∑_{J′_{1}+J′_{2}=J} pack(^{w[J′_{1}]}/_{w[I]}) ⊗ pack(^{w[J′_{2}]}/_{w_{[I+J′_{1}]}}))

= ∑_{I+J′_{1}+J′_{2}={1,...,|w|}} pack(w[I]) ⊗ pack(^{w[J′_{1}]}/_{w[I]}) ⊗ pack(^{w[J′_{2}]}/_{w_{[I+J′_{1}]}}).  (3.13)

Comparing (3.12) and (3.13), we conclude that the coproduct (3.1) is coassociative.

We now claim that

(ϵ ⊗ Id) ∘ Δ(w) = (Id ⊗ ϵ) ∘ Δ(w),  (3.14)

for all words w ∈ H. In order to establish this claim, we rewrite the left-hand side of (3.14) as

(ϵ ⊗ Id) ∘ Δ(w) = (ϵ ⊗ Id) ( ∑_{I+J={1,...,|w|}} pack(w[I]) ⊗ pack(w[J]/w[I]))

= ∑_{I+J={1,...,|w|}} ϵ(pack(w[I])) ⊗ pack(w[J]/w[I]) = 1_{H} ⊗ pack(w) = pack(w),

and the right-hand side as

(Id ⊗ ϵ) ∘ Δ(w) = (Id ⊗ ϵ) ( ∑_{I+J={1,...,|w|}} pack(w[I]) ⊗ pack(w[J]/w[I]))

= ∑_{I+J={1,...,|w|}} pack(w[I]) ⊗ ϵ(pack(w[J]/w[I])) = pack(w) ⊗ 1_{H} = pack(w).

Consequently, the triple (H, Δ, ϵ) is a coassociative coalgebra with co-unit. □

Remark 3.8. This coalgebra is not cocommutative. For example, we have

T_{12} ∘ Δ(x_{1}^{2}) = T_{12}(x_{1}^{2} ⊗ 1_{H} + 2x_{1} ⊗ x_{0} + 1_{H} ⊗ x_{1}^{2})
= x_{1}^{2} ⊗ 1_{H} + 2x_{0} ⊗ x_{1} + 1_{H} ⊗ x_{1}^{2} ≠ Δ(x_{1}^{2}),

where the operator T_{12} is given by T_{12}(u ⊗ v) = v ⊗ u.

Lemma 3.9. Let u, v be two words. Furthermore, let I_{1}+J_{1} = {1, 2, …, |u|} and I_{2}+J_{2} = {|u| + 1, |u| + 2, …, |u| + |v|}. Then

pack(^{u∗v[J_{1}+J_{2}]}/_{u∗v[I_{1}+I_{2}]}) = pack(^{u[J_{1}]}/_{u[I_{1}]}) ∗ pack(^{v[J′_{2}]}/_{v[I′_{2}]}),  (3.15)

where I′_{2} is the set {k − |u| : k ∈ I_{2}} and J′_{2} is the set {k − |u| : k ∈ J_{2}}.

Proof. We have

pack(^{u∗v[J_{1}+J_{2}]}/_{u∗v[I_{1}+I_{2}]}) = pack(S_{ϕ_{I_{1}+I_{2}}}(u ∗ v[J_{1} + J_{2}]))
= pack(S_{ϕ_{I_{1}+I_{2}}}(uT_{sup(u)}(v)[J_{1} + J_{2}]))
= pack(S_{ϕ_{I_{1}}+ϕ_{I_{2}}}(u[J_{1}]T_{sup(u)}(v)[J_{2}]))
= pack(S_{ϕ_{I_{1}}}S_{ϕ_{I_{2}}}(u[J_{1}]T_{sup(u)}(v[J′_{2}])))
= pack(S_{ϕ_{I_{1}}}(u[J_{1}])S_{ϕ_{I_{2}}}(T_{sup(u)}(v[J′_{2}])))
= pack(^{u[J_{1}]}/_{u[I_{1}]})T_{sup(^{u[J_{1}]}/_{u[I_{1}]})}pack(S_{ϕ_{I′_{2}}}(v[J′_{2}]))
= pack((^{u[J_{1}]}/_{u[I_{1}]}) ∗ pack(^{u[J′_{2}]}/_{u[I′_{2}]}).
□

Proposition 3.10. For any words u, v in H, we have

Δ(u ∗ v) = Δ(u) ∗^{⊗2} Δ(v).  (3.16)

Proof. We have

Δ(u ∗ v) = ∑_{\begin{matrix}I_{1}+I_{2}=I \\ J_{1}+J_{2}=J \\ I_{1},J_{1}⊂\{1,...,|u|\} \\ I_{2},J_{2}⊂\{|u|+1,...,|u|+|v|\} \end{matrix}} (pack(u ∗ v[I_{1} + I_{2}])) ⊗ (pack(^{(u∗v[J_{1}+J_{2}]}/_{(u∗v[I_{1}+I_{2}]}))

= ∑_{\begin{matrix}I_{1}+J_{1}=\{1,...,|u|\} \\ I′_{2}+J′_{2}=\{1,...,|v|\} \end{matrix}} (pack(u[I_{1}]) ⊗ pack(^{u[J_{1}]}/_{u[I_{1}]})) ∗ (pack(v[I_{2}]) ⊗ pack(^{u[J′_{2}]}/_{u[I′_{2}]}))

= ( ∑_{I_{1}+J_{1}={1,...,|u|}} pack(u[I_{1}]) ⊗ pack(^{u[J_{1}]}/_{u[I_{1}]}))

∗ ( ∑_{I′_{2}+J′_{2}={1,...,|v|}} pack(v[I_{2}]) ⊗ pack(^{u[J′_{2}]}/_{u[I′_{2}]}))

=Δ(u) ∗^{⊗2} Δ(v).
□

Since H is graded by word length, we have the following theorem.

Theorem 3.11. (H, ∗, 1_{H}, Δ, ϵ) is a Hopf algebra.

Proof. This follows from the above results. □

For w ≠ 1_{H}, the antipode is given by the recursion

S(w) = −w − ∑_{I+J={1,...,|w|},I,J≠∅} S(pack(w[I])) ∗ pack(^{w[J]}/_{w[I]}).  (3.17)

4. Hilbert series of the Hopf algebra WMat

In this section, we compute the number of packed words with length n and supremum k. It is the same as the number of cyclically ordered partitions of an n-element set. Using the formula for Stirling numbers of the second kind (see [1]), we obtain an explicit formula for the number of packed words with length n, which we denote by d_{n}.

Definition 4.1. The Stirling number of the second kind S(n, k) counts the number of set partitions of an n-element set into precisely k blocks. They are given by the recurrence

S(n + 1, k) = S(n, k − 1) + kS(n, k), for 0 < k ≤ n,

and initial conditions S(0, 0) = 1 and S(n, 0) = 0 for n > 0.

We may define a word without x_{0} by its positions, meaning that, if a word w = x_{i_{1}}x_{i_{2}} … x_{i_{n}} has length n and alphabet IAlph(w) = {1, 2, …, k}, then this word can be determined from the list {S_{1}, S_{2}, …, S_{k}}, where S_{i} is the set of positions of x_{i} in the word w, with 1 ≤ i ≤ k. It is straightforward to check that (S_{i})_{1≤i≤k} is a partition of {1, 2, …, n}.

We may divide the set of packed words with length n and supremum k into two parts: “pure” packed words (which have no x_{0} in their alphabet), denoted by pack_{n,k}^{+}(X), and packed words which have x_{0} in their alphabet, denoted by pack_{n,k}^{0}(X). It is obvious that

d(n, k) = #pack_{n,k}^{+}(X) + #pack_{n,k}^{0}(X).  (4.1)

We now compute the cardinality of these two sets separately.

Consider a word w ∈ pack_{n,k}^{+}(X). Clearly, we have IAlph(w) = {1, 2, …, k}. This word is determined by {S_{1}, S_{2}, …, S_{k}}, where S_{i} is the set of positions of x_{i}, for 1 ≤ i ≤ k. It is obvious that:

(1) S_{i} ≠ ∅, for all i ∈ {1, 2, …, k};

(2) ⨆_{1≤i≤k} S_{i} = {1, 2, …, n}. Note that (1) and (2) hold even for w = 1_{H}.

Thus, the cardinality of packed words with length n and supremum k equals

d^{+}(n, k) = #pack_{n,k}^{+}(X) = S(n, k)k!.  (4.2)

Similarly, a word w ∈ #pack_{n,k}^{0}(X) can be determined by {S_{0}, S_{1}, S_{2}, …, S_{k}} where S_{i} is the set of positions of x_{i}, for 0 ≤ i ≤ k. In this case, we have

d^{0}(n, k) = #pack_{n,k}^{0}(X) = S(n, k + 1)(k + 1)!.  (4.3)

The number of packed words with length n and supremum k is then the sum of these two numbers, namely

d(n, k) = d^{+}(n, k) + d^{0}(n, k) = S(n, k)k! + S(n, k + 1)(k + 1)! = S(n + 1, k + 1)k!. (4.4)

Using Maple, we computed the first few values of d(n, k). They are displayed in Table 1. Note that the values of Table 1 correspond to those of the triangular array A028246 in [9].

Remark 4.2. Formulas (4.2) and (4.3) imply that the packed words of length n and supremum k without, respectively with, x_{0} are in bijection with the ordered partitions of {1, 2, …, n} into k blocks, respectively into k + 1 blocks. Therefore formula (4.4) implies that the set of packed words of length n with supremum k is in bijection with the circularly ordered partitions of n + 1 elements into k + 1 blocks.

The number d_{n} of all packed words of length n is then given by

d_{n} = ∑_{k=0}^{n} d(n, k) = ∑_{k=0}^{n} S(n + 1, k + 1)k!.  (4.5)

Using again Maple, we computed the values listed in Table 2.

k
0 1  2  3  4  5  6  7  8
0 1 0  0  0  0  0  0  0  0
1 1 1  0  0  0  0  0  0  0
2 1 3  2  0  0  0  0  0  0
3 1 7 12  6  0  0  0  0  0
n 4 1 15 50  60  24  0  0  0  0
5 1 31 180 390  360  120  0  0  0
6 1 63 602 2100 3360 2520  720  0  0
7 1 127 1932 10206 25200 31920 20160 5040  0
8 1 255 6050 46620 166824 317520 332640 181440 40320

Table 1. Values of d(n, k) given by the explicit formula (4.4) and computed with Maple.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ d_{n} & 1 & 2 & 6 & 26 & 150 & 1082 & 9366 & 94586 & 1091670 & 14174522 & 204495126 \end{matrix}

Table 2. Some value of d_{n} by the formula (4.5).

The number of packed words is the sequence A000629 in [9], where it is also mentioned that this sequence corresponds to the sequence of ordered Bell numbers multiplied by two (except for the 0th term).

The ordinary and exponential generating functions of our sequence are also given in [9], while the ordinary generating function is given by the formula ∑_{n≥0} \frac{2^{n}n!x^{n}}{∏_{k=0}^{n}(1+kx)}. The exponential generating function is given by \frac{e^{x}}{2−e^{x}}. Below we provide the proof of the latter fact.

First, recall that the exponential generating function of the ordered Bell numbers (see, for example, page 109 of [4]) is

\frac{1}{2 − e^{x}} = ∑_{n≥0} ∑_{k=0}^{n} S(n, k)k!\frac{x^{n}}{n!} .  (4.6)

By differentiating both sides of this equation with respect to x, we obtain

\frac{e^{x}}{2 − e^{x}} = ∑_{n≥1} ∑_{k=1}^{n} S(n, k)k!\frac{x^{n−1}}{(n − 1)!}.  (4.7)

Combining (4.5) and (4.7), we get

\frac{e^{x}}{2 − e^{x}} = ∑_{n≥0} ∑_{k=0}^{n} S(n + 1, k + 1)k!\frac{x^{n}}{n!} = ∑_{n≥0} d_{n} \frac{x^{n}}{n!} ,  (4.8)

as claimed in [9].

We now investigate the combinatorics of irreducible packed words (see Definition 2.10). First, we notice that there are still infinitely many irreducible packed words of weight m, and again they are obtained by adding multiple copies of the letter x_{0}.

Example 4.3. The word x_{1}x_{0}^{k}x_{1}x_{0}^{k}x_{1} (with k an arbitrary positive integer) is an irreducible packed word of weight 3.

Let us denote by i_{n} the number of irreducible packed words of length n. Then we have

i_{n} = ∑_{\begin{matrix}j_{1}+···+j_{k}=n \\ j_{l}≠0 \end{matrix}}(−1)^{k+1}d_{j_{1}} … d_{j_{k}}.  (4.9)

Using Maple, we computed the first values of i_{n}. They are displayed in Table 3.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ i_{n} & 1 & 2 & 2 & 10 & 66 & 538 & 5170 & 59906 & 704226 & 9671930 & 145992338 \end{matrix}

Table 3. The ten first values of the number of irreducible packed words

Note that this sequence does not appear in Sloane’s On-Line Encyclopedia of Integer Sequences [9].

5. Primitive elements of WMat

We emphasize that this Hopf algebra, although graded, is not cocommutative and thus the primitive elements do not generate the whole algebra but only the sub-Hopf algebra on which Δ is cocommutative (the largest subalgebra on which the Cartier–Quillen–Milnor– Moore theorem holds).

We denote by P rim(WMat) the algebra generated by the primitive elements of H. We recall the following result.

Lemma 5.1. Let V^{(1)} and V^{(2)} be two graded vector spaces,

V^{(i)} = ⊕_{n≥0}V_{n}^{(i)}, i = 1, 2.  (5.1)

Furthermore, let ϕ ∈ Hom^{gr}(V^{(1)}, V^{(2)}), that is, ϕ(V_{n}^{(1)}) ⊆ V_{n}^{(2)}) for all n ≥ 0. Then Ker(ϕ) is graded.

We then obtain the following property of P rim(WMat).

Proposition 5.2. P rim(WMat) is a Lie subalgebra of WMat, graded by the word’s length.

Proof. We define the mapping

Δ^{+} :  WMat ⟶ WMat ⊗ WMat
\begin{cases}1_{H} & ⟼ 0, \\ h & ⟼ Δ(h) − 1_{H} ⊗ h − h ⊗ 1_{H}. \end{cases}  (5.2)

This mapping is graded. Using Lemma 5.1, we infer P rim(WMat) = Ker(Δ^{+}). Thus, the subalgebra P rim(WMat) is graded. □

Let us now compute the dimensions of the first few spaces P rim(WMat)_{n}:

• For n = 1, a basis is formed by the primitive elements x_{0} and x_{1}. Then one can check that the primitive elements of length 1 have the form ax_{0} + bx_{1}, with a and b scalars.

• For n = 2, a basis is formed by the primitive elements x_{0}x_{1} −x_{1}x_{0} and x_{1}x_{2} −x_{2}x_{1}. Then one can check that all the primitive elements of length 2 have the form a(x_{0}x_{1} − x_{1}x_{0}) + b(x_{1}x_{2} − x_{2}x_{1}), with a and b scalars. This is seen by explicitly solving a system of 4 equations with d_{2} = 6 variables.

Nevertheless, the explicit calculations quickly become lengthy. For example, for n = 3, we have to solve a system of 22 equations with 26 variables.

To conclude, let us give some a posteriori explanations on the choice of the name “WMat” for our algebraic structure. We have defined here a Hopf algebra on some set of words with a selection/quotient coproduct rule in the spirit of graphs [2] and matroid Hopf algebras [8]. We could thus call our algebra WGraph or WMat. We prefer the name WMat, since matroids are more general structures than graphs.

On the other hand, the ”W” in our name simply refers to the fact that we have a Hopf algebra with basis indexed by a subset X of the free monoid ℕ^{∗}. Let us say that, at this point, there is no polynomial realization of WMat (as is is the case for W Sym or W QSym or the Connes–Kreimer Hopf algebras on trees; see [5] and the references therein).

This actually seems to us to be an important perspective for future work related to the new Hopf algebra proposed in this paper.

Acknowledgements

We thank Jean-Yves Thibon for various discussions and suggestions. The authors acknowledge a Université Paris 13, Sorbonne Paris Cité BQR grant. A. Tanasa was supported by the grants PN 09 37 01 02 and CNCSIS Tinere Echipe 77/04.08.2010. G. H. E. Duchamp was supported by the grants ANR BLAN08-2 332204 (Physique Combinatoire) and PAN-CNRS 177494 (Combinatorial Structures and Probability Amplitudes).

References

[1] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Presses Universitaires de France, Paris, 1974.

[2] A. Connes and D. Kreimer, Renormalization in quantum field theory and the Riemann–Hilbert problem I: The Hopf algebra structure of graphs and the main theorem, Commun. Math. Phys. 210 (2000), 249–273.

[3] G. H. E. Duchamp, F. Hivert and J.-Y. Thibon, Noncommutative functions VI: Free quasisymmetric functions and related algebras, Internat. J. Algebra Comput. 12 (2002), 671–717.

[4] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[5] L. Foissy, J.-C. Novelli and J.-Y. Thibon, Polynomial realizations of some combinatorial Hopf algebras, J. Noncomm. Geom (in press); arχiv:1009.2067.

[6] J.-L. Loday and M. O. Ronco, Hopf algebra of the planar binary trees, Adv. Math. 139 (1998), 293–309.

[7] F. Markopoulou, Coarse graining in spin foam models, Class. Quant. Grav. 20 (2003), 777-800.

[8] W. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra 96 (1994), 299–330.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, available at:

http://www.oeis.org.

[10] A. Tanasa and D. Kreimer, Combinatorial Dyson–Schwinger equations in noncommutative field theory, J. Noncomm. Geom. 7 (2013), 255–289.

[11] A. Tanasa and F. Vignes-Tourneret, Hopf algebra of non-commutative field theory, J. Noncomm. Geom. 2 (2008), 125–139.

[12] A. Tanasa, Combinatorial Hopf algebras in (noncommutative) quantum field theory, Rom. J. Phys. 55 (2010), 1142–1155.

[13] A. Tanasa, Algebraic structures in quantum gravity, Class. Quant. Grav. 27 (2010), 095008, 16 pp.

[14] A. Tanasa, Some combinatorial aspects of quantum field theory, Sém. Lothar. Combin. 65 (2012), Article B65g, 30 pp.

[15] H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57 (1935), 509–533.

1LIPN - Institut Galilée - Université Paris 13, Sorbonne Paris Cité, CNRS UMR 7030, 99 avenue Jean-Baptiste Clément, F-93430 Villetaneuse, France,

2Horia Hulubei National Institute for Physics and Nuclear Engineering,, P.O.B. MG-6, 077125 Magurele, Romania