Séminaire Lotharingien de Combinatoire 54A (2007), Article B54Am

FREE QUASI-SYMMETRIC FUNCTIONS, PRODUCT ACTIONS AND QUANTUM FIELD THEORY OF PARTITIONS

Gérard H. E. Duchamp^{†}, Jean-Gabriel Luque^{‡}, K. A. Penson^{⋆}, Christophe Tollu^{†}

† LIPN, UMR CNRS 7030 Institut Galilée - Université Paris-Nord 99, avenue Jean-Baptiste Clément 93430 Villetaneuse, France

‡ IGM, Laboratoire d’informatique UMR 8049 IGM-LabInfo 77454 Marne-la-Vallée Cedex 2, France.

⋆ LPTL, Laboratoire de Physique Théorique des Liquides, CNRS UMR 7600 Université Pierre et Marie Curie, Tour 16, 5^{ième} étage, 4, place Jussieu, F 75252 Paris Cedex 05, France

              E-mail: ghed@lipn.univ-paris13.fr, luque@univ-mlv.fr,
                penson@lptl.jussieu.fr, ct@lipn.univ-paris13.fr

Abstract. We investigate two associative products over the ring of symmetric functions related to the intransitive and Cartesian products of permutation groups. As an application, we give an enumeration of some Feynman type diagrams arising in Bender’s QFT (quantum field theory) of partitions. We end by exploring possibilities to construct noncommutative analogues.

Résumé. Nous étudions deux lois produits associatives sur les fonctions symétriques correspondant aux produits intransitif et cartésien des groupes de permutations. Nous donnons comme application l’énumération de certains diagrammes de Feynman apparaissant dans la QFT (théorie quantique des champs) des partitions de Bender. Enfin, nous donnons quelques pistes possibles pour construire des analogues non-commutatifs.

1. Introduction

In a relatively recent paper, Bender, Brody and Meister introduced a special Field Theory described by

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

in order to prove that any sequence of numbers {a_{n}} can be generated by a suitable set of rules applied to some type of Feynman diagrams [1, 2]. These diagrams actually are 2-coloured multigraphs with no isolated vertex.

Expanding one factor of formula (1), one can observe surprising links between: the normal ordering problem (for bosons), the parametric Stieltjes moment problem and the convolution of kernels, substitution matrices (such as generalised Stirling matrices) and one-parameter groups of analytic substitutions [8, 9, 15]. Our aim in this paper is to make more explicit the connections between symmetric functions (either commutative or noncommutative) and the Feynman diagrams (either labelled or unlabelled) arising in Bender and al.’s Quantum Field Theory of Partitions, and used in combinatorial physics

The paper is organized as follows. In Section 2, we define two binary operations on 𝔖 = ⨆ 𝔖_{n}, respectively related to the intransitive and Cartesian products of permutation groups. We prove that both operations are associative, hence giving the graded vector space ⨁_{n≥0} ℚ[𝔖_{n}] the structure of a 2-associative algebra. In Section 3, we show how the latter algebraic structure can be carried over to the commutative symmetric functions, and we further investigate the 2-associative algebra Sym with respect to distributivity. We also take advantage of the construction to recall, in its proper context, Pólya’s cycle index theorem; as an application, we use it to establish an inductive formula for the generating functions of the Feynman diagrams associated with Bender’s QFT of partitions. Section 4 is dedicated to noncommutative analogues of the constructions introduced in Section 3: we show how the Feynman diagrams obtained by expanding formula (1) are related to the algebras FQSym and MQSym [6].

2. Actions of a direct product of permutation groups

2.1. Direct product actions. The actions of the direct product of two permutation groups (in particular, on the structure of the cycles) give rise to interesting properties related to the enumeration of unlabelled objects [14]. We open this section with the definition of two actions (namely, intransitive and Cartesian). For greater detail about these constructions (or for constructions involving the wreath product) the reader is referred to [4].

Consider two pairs (G_{1}, X_{1}) and (G_{2}, X_{2}), where each G_{i} is a permutation group acting on the set X_{i}, either finite or infinite. The intransitive action of G_{1} ×G_{2} on X_{1} ⊔X_{2} (here ⊔ means disjoint union) is defined by the rule

(σ_{1}, σ_{2})x = \begin{cases}σ_{1}x & if x ∈ X_{1}, \\ σ_{2}x & if x ∈ X_{2}. \end{cases}  (2)

This action will be denoted by (G_{1}, X_{1}) → + (G_{2}, X_{2}) := (G_{1} × G_{2}, X_{1} ⊔ X_{2}). The Cartesian action of G_{1} × G_{2} on X_{1} × X_{2} is defined by

(σ_{1}, σ_{2})(x_{1}, x_{2}) = (σ_{1}x_{1}, σ_{2}x_{2}).  (3)

This action will be denoted by (G_{1}, X_{1}) ↗ ↘ (G_{2}, X_{2}) := (G_{1} × G_{2}, X_{1} × X_{2}). Note that neither of the two binary operations just defined is commutative. A natural question to ask is whether such a structure enjoys some algebraic properties. For example, is ↗ ↘ distributive over → + ?

In other words, what is the meaning of

(G_{1}, X_{1}) ↗ ↘ ((G_{2}, X_{2}) → + (G_{3}, X_{3})) = (G_{1} × G_{2} × G_{3}, X_{1} × (X_{2} ⊔ X_{3}))

and

((G_{1}, X_{1}) ↗ ↘ (G_{2}, X_{2})) → + ((G_{1}, X_{1}) ↗ ↘ (G_{3}, X_{3})) = (G_{1} × G_{2} × G_{1} × G_{3}, (X_{1} × X_{2}) ⊔ (X_{1} × X_{3})).

The groups G_{1} × G_{2} × G_{1} × G_{3} and G_{1} × G_{2} × G_{3} are not isomorphic, so distributivity does not hold, although the set-theoretical Cartesian product is distributive over disjoint union. However an examination of the structure of the cycles (see [4] for the general construction or Section 2.2 for a particular case) shows that the cycles are the same. More precisely, a cycle can appear with different multiplicities according to which group is acting, but if we focus on the set of the cycles, the two structures are similar.

We now exhibit a construction which accounts for such a phenomenon.

FREE QUASI-SYMMETRIC FUNCTIONS, PRODUCT ACTIONS AND QUANTUM FIELD THEORY 3

2.2. Explicit realization. We will denote by ∘_{N} the natural action of 𝔖_{n} on {0, …, n− 1}. Let 𝔖_{n} and 𝔖_{m} be two symmetric groups, we note by ∘_{I} the intransitive action of 𝔖_{n} × 𝔖_{m} on {0, ⋯, n + m − 1} and by ∘_{C} the Cartesian action of 𝔖_{n} × 𝔖_{m} on {0, …, nm − 1}. More precisely, for σ_{1} ∈ 𝔖_{n} and σ_{2} ∈ 𝔖_{m},

(σ_{1}, σ_{2}) ∘_{I} i = \begin{cases}σ_{1} ∘_{N} i & if 0 ≤ i ≤ n − 1, \\ (σ_{2} ∘_{N} (i − n)) + n & if n ≤ i ≤ n + m − 1, \end{cases}  (4)

for 0 ≤ i ≤ n + m − 1, and

(σ_{1}, σ_{2}) ∘_{C} (j + nk) = (σ_{1} ∘_{N} j) + n(σ_{2} ∘_{N} k)  (5)

for 0 ≤ j ≤ n − 1 and 0 ≤ k ≤ m − 1.

The intransitive product is the map → + : 𝔖_{n} × 𝔖_{m} → 𝔖_{n+m} defined by

σ_{1} → + σ_{2} = σ_{1}σ_{2}[n],  (6)

where σ_{2}[n] denotes σ_{2} composed with the shifted substitution i ↦ i + n (here permutations are considered as words and → + is nothing else but shifted concatenation).

Example 2.1. Let σ_{1} = 1320 ∈ 𝔖_{4} and σ_{2} = 534120 ∈ 𝔖_{6}. Here, we denote a permutation of 𝔖_{n} by the word whose ith letter is the image of i under the natural action on {0, …, n − 1}). With this notation, we obtain

σ_{1} → + σ_{2} = 1320978564

and

σ_{2} → + σ_{1} = 5341207986.

Clearly, it turns out that → + is not commutative.

The following proposition shows that the natural action of (the image under → + of 𝔖_{n} × 𝔖_{m} in) 𝔖_{n+m} coincides with the intransitive action of 𝔖_{n} × 𝔖_{m}.

Proposition 2.2. We have (σ_{1} → + σ_{2}) ∘_{N} i = (σ_{1}, σ_{2}) ∘_{I} i.

Let us introduce a similar construction for the Cartesian action: we define a map ↗ ↘: 𝔖_{n} × 𝔖_{m} → 𝔖_{nm} by

σ_{1} ↗ ↘ σ_{2} = ∏_{i,j} c_{i} ↗ ↘ c′_{j},  (7)

where σ_{1} = c_{1} ⋯ c_{k} (respectively σ_{2} = c′_{1} ⋯ c′_{k′}) is the decomposition of σ_{1} (respectively σ_{2}) into a product of cycles and, for two cycles c = (i_{0}, ⋯, i_{l−1}), c′ = (j_{0}, ⋯, j_{l′−1}),

c ↗ ↘ c′ = ∏_{s=0}^{gcd(l,l′)−1}(ϕ(s, 0), ϕ(s + 1, 1) ⋯, ϕ(lcm(l, l′) − 1, lcm(l, l′) − 1)),  (8)

where ϕ(k, k′) = i_{k mod l} +nj_{k′ mod l′}. Just like the intransitive action, the Cartesian action coincides with the natural action of (the image under ↗ ↘ of of 𝔖_{n} × 𝔖_{m} in) 𝔖_{nm}.

Proposition 2.3. We have (σ_{1} ↗ ↘ σ_{2}) ∘_{N} i = (σ_{1}, σ_{2}) ∘_{C} i .

Proof. From (7), it suffices to prove the property when σ_{1} = c and σ_{2} = c′ are two cycles. But (8) is equivalent to

c ↗ ↘ c′ = ∏_{s=0}^{gcd(l,l′)−1}(i_{s} + nj_{0}, (c, c′) ∘_{C} (i_{s} + nj_{0}), …, (c^{lcm(l,l′)−1}, c′^{lcm(l,l′)−1}) ∘_{C} (i_{s} + nj_{0}))

= ∏_{s=0}^{gcd(l,l′)−1}(i_{s} + nj_{0}, c ∘_{C} i_{s} + nc′ ∘_{N} j_{0}, …, c^{lcm(l,l′)−1} ∘_{N} i_{s} + nc′^{lcm(l,l′)−1} ∘_{N} j_{0})),

which completes the proof. □

Example 2.4. Consider the two permutations σ_{1} = 2031 ∈ 𝔖_{4} and σ_{2} = 01723456 ∈ 𝔖_{8}. The permutation σ_{1} consists of a unique cycle c_{1} = (0, 2, 3, 1) and σ_{2} = c′_{1}c′_{2}c′_{3} is the product of the three cycles c′_{1} = (0), c′_{2} = (1) and c′_{3} = (7, 6, 5, 4, 3, 2). Hence, the permutation σ_{1} ↗ ↘ σ_{2} is the product of four cycles given by

(1) c_{1} ↗ ↘ c′_{1} = (0, 2, 3, 1),

(2) c_{1} ↗ ↘ c′_{2} = (4, 6, 7, 5),

(3) c_{1} ↗ ↘ c′_{3} = (28, 26, 23, 17, 12, 10, 31, 25, 20, 18, 15, 9)

(30, 27, 21, 16, 14, 11, 29, 24, 22, 19, 13, 8).

To illustrate Proposition 2.3, it suffices to draw the cycles in the Cartesian product {0, …, n−1}×{0, …, m−1} whose elements are re-labelled through (i, j) ↦ i+nj. For example, the two cycles appearing in c_{1} ↗ ↘ c′_{3} give the following partition of {0, 1, 2, 3} × {2, 3, 4, 5, 6, 7}.

[figure: 0; 2; 3; 1; 0; 7; 6; 5; 4; 3; 2; 7; ↗; ↗; ↗; ↗; ↓; ↓; ↓; ←; (28, 26, 23, 17, 12, 10, 31, 25, 20, 18, 15, 9); 0; 2; 3; 1; 0; 7; 6; 5; 4; 3; 2; 7; ↗; ↗; ↗; ↗; ↗; ↓; ↓; ↓; ←; ←; (30, 27, 21, 16, 14, 11, 29, 24, 22, 19, 13, 8)]

On the other hand, the permutation σ_{2} ↗ ↘ σ_{1} is the product of the four cycles (1) c′_{1} ↗ ↘ c_{1} = (0, 16, 24, 8),

(2) c′_{2} ↗ ↘ c_{1} = (1, 17, 25, 9),

(3) c′_{3} ↗ ↘ c_{1} = (7, 22, 29, 12, 3, 18, 31, 14, 5, 20, 27, 10)

(6, 21, 28, 11, 2, 23, 30, 13, 4, 19, 26, 15).

Clearly, σ_{1} ↗ ↘ σ_{2} ≠ σ_{2} ↗ ↘ σ_{1} : the binary operation ↗ ↘ is not commutative.

2.3. Algebraic structure. The advantage of the new structures over the ones defined in Section 2.1 consists in the omission of the operations over the groups. Hence, algebraic properties come into light quite naturally.

First, the two operations are associative.

Proposition 2.5. Associativity. Let σ_{1} ∈ 𝔖_{n}, σ_{2} ∈ 𝔖_{m} and σ_{3} ∈ 𝔖_{p} be 3 permutations

(1) σ_{1} → + (σ_{2} → + σ_{3}) = (σ_{1} → + σ_{2}) → + σ_{3}

(2) σ_{1} ↗ ↘ (σ_{2} ↗ ↘ σ_{3}) = (σ_{1} ↗ ↘ σ_{2}) ↗ ↘ σ_{3}

Proof. 1) Set η_{1} = σ_{1} → + (σ_{2} → + σ_{3}) and η_{2} = (σ_{1} → + σ_{2}) → + σ_{3}. One has

η_{1} ∘_{N} i = \begin{cases}σ_{1} ∘_{N} i & if 0 ≤ i ≤ n − 1, \\ σ_{2} ∘_{N} (i − n) + n & if n ≤ i ≤ m + n − 1, \\ σ_{3} ∘_{N} (i − n − m) + n + m & if n + m ≤ i ≤ n + m + p − 1, \end{cases}

for each 0 ≤ i ≤ n + m − 1, and the same holds for η_{2} ∘_{N} i. It follows that η_{1} = η_{2}.

2) The strategy is the same. First, we set η_{1} = σ_{1} ↗ ↘ (σ_{2} ↗ ↘ σ_{3}) and η_{2} = (σ_{1} ↗ ↘ σ_{2}) ↗ ↘ σ_{3}. The action of η_{1} can be computed as follows

η_{1} ∘_{N} (i + ni′) = σ_{1} ∘_{N} i + n(σ_{2} ↗ ↘ σ_{3}) ∘_{N} i′ = σ_{1} ∘_{N} i + nσ_{2} ∘_{N} j + nmσ_{3} ∘_{N} k,

where 0 ≤ i ≤ n − 1, 0 ≤ i′ ≤ mp − 1, 0 ≤ j ≤ m − 1 and 0 ≤ k ≤ p − 1.

On the other hand, the action of η_{2} is

η_{2} ∘_{N} (k′ + nmk) = (σ_{1} ↗ ↘ σ_{2}) ∘_{N} k′ + nmσ_{3} ∘_{N} k = σ_{1} ∘_{N} i + nσ_{2} ∘_{N} j + nmσ_{3} ∘_{N} k,

where 0 ≤ i ≤ n − 1, 0 ≤ j ≤ m − 1, 0 ≤ k ≤ p − 1 and 0 ≤ k′ ≤ nm − 1. Hence, η_{1} ∘_{N} i = η_{2} ∘_{N} i for 0 ≤ i ≤ nmp − 1 and η_{1} = η_{2}. □

From Examples 2.1 and 2.4, neither → + nor ↗ ↘ is commutative. But, one has the property of left distributivity.

Proposition 2.6. Semi-distributivity. Let σ_{1} ∈ 𝔖_{n}, σ_{2} ∈ 𝔖_{m} and σ_{3} ∈ 𝔖_{p} be three permutations

σ_{1} ↗ ↘ (σ_{2} → + σ_{3}) = (σ_{1} ↗ ↘ σ_{2}) → + (σ_{1} ↗ ↘ σ_{3}).

Proof. We use the same method as in the proof of Proposition 2.5. First, let us define η_{1} = σ_{1} ↗ ↘ (σ_{2} → + σ_{2}) and η_{2} = (σ_{1} ↗ ↘ σ_{2}) → + (σ_{1} ↗ ↘ σ_{3}). The action of η_{1} is

η_{1} ∘_{N} (i + nj) = η_{1} ∘_{N} i + n(σ_{2} → + σ_{3}) ∘_{N} j
= \begin{cases}σ_{1} ∘_{N} i + nσ_{2} ∘_{N} j & if 0 ≤ j ≤ m − 1, \\ σ_{1} ∘_{N} i + nσ_{3} ∘_{N} (j − m) + m & if m ≤ j ≤ p + m − 1, \end{cases}  (9)

where 0 ≤ i ≤ n − 1 and 0 ≤ j ≤ m + p − 1.

On the other hand, one has

η_{2} ∘_{N} k = \begin{cases}(σ_{1} ↗ ↘ σ_{2}) ∘_{N} k & if 0 ≤ k ≤ nm − 1, \\ (σ_{1} ↗ ↘ σ_{3}) ∘_{N} (k − nm) + nm & if nm ≤ k ≤ n(m + p) − 1. \end{cases}  (10)

If 0 ≤ k ≤ mn − 1, we set k = i + nj where 0 ≤ i ≤ n − 1 and 0 ≤ j ≤ m − 1. Hence,

(σ_{1} ↗ ↘ σ_{2}) ∘_{N} k = σ_{1} ∘_{N} i + nσ_{2} ∘_{N} j.  (11)

Similarly, if nm ≤ k ≤ n(m + p) − 1, we set (k − nm) = i + nj where 0 ≤ i ≤ n − 1 and 0 ≤ j ≤ p − 1. Hence,

(σ_{1} ↗ ↘ σ_{3}) ∘_{N} (k − nm) + nm = σ_{1} ∘_{N} i + n(σ_{3} ∘_{N} (j − m) + m).  (12)

Substituting (11) and (12) in (10), one recovers the right hand side of (9). It follows immediately that η_{1} = η_{2}. □

The two binary operations can be extended by linearity to the graded vector space ⨁_{n≥0} ℚ[𝔖_{n}] and endow this space with the structure of a 2-associative algebra, i.e., a vector space equipped with 2 associative products [11]). In the next section, we construct a product ⋆ in Sym (the algebra of symmetric functions) defined on the power sums and appearing when one examines the cycle index of a Cartesian product. This product is the image of ↗ ↘ under a particular homomorphism of 2-associative algebras. We will prove that this last property implies the associativity of ⋆ and the distributivity of ⋆ over × (the natural product in Sym) and +.

3. Cycle index algebra

3.1. Cartesian product in Sym. We first construct a homomorphism of 2-associative algebras ⨁_{n≥0} ℚ[𝔖_{n}] → Sym.

The arrow maps a permutation σ ∈ 𝔖_{n} to a product of power sums. For j ≥ 1, let c_{j}(σ) be the number of cycles of length j in σ and set

ℨ(σ) = ∏_{j=0}^{∞} p_{j}^{c_{j}(σ)},  (13)

where p_{i} denotes the ith power sum symmetric function. We claim that ℨ is a homomorphism of algebras mapping → + to × (the usual product in Sym) and such that ↗ ↘ is compatible with ℨ to the extent that there exists an associative product on Sym such that ℨ is also a homomorphism mapping ↗ ↘ to it. This second law is given on the power sums basis by

∏_{1≤i≤∞} p_{i}^{α_{i}} ⋆ ∏_{1≤j≤∞} p_{j}^{β_{j}} = ∏_{1≤i,j≤∞} p_{lcm(i,j)}^{α_{i}β_{j} gcd(i,j)}.  (14)

(The sequences (α_{i})_{i≥1}, (β_{j})_{j≥1} have finite support.) It is straightforward to check the following facts.

Proposition 3.1. i) The map ℨ : ⨁_{n≥0} ℚ[𝔖_{n}] → Sym is a homomorphism of 2associative algebras mapping the two products → + ; ↗ ↘ respectively to ×; ⋆. (Recall that × denotes the usual product of Sym.) More precisely, for σ, τ ∈ ⊔_{n≥0}𝔖_{n} = 𝔖 one has

ℨ(σ → + τ) = ℨ(σ)ℨ(τ) ; ℨ(σ ↗ ↘ τ) = ℨ(σ) ⋆ ℨ(τ).  (15)

ii) The product ⋆ is associative, commutative and distributive over ×.

Proof. i) For the first relation of (15), one just notices that c_{j}(σ → + τ) = c_{j}(σ) + c_{j}(τ). For the second relation, one observes that the Cartesian product of a i-cycle and a j-cycle produces gcd(i, j) cycles of length lcm(i, j). Thus, one has c_{r}(σ ↗ ↘ τ) = ∑_{lcm(p,q)=r} gcd(p, q)c_{p}(σ)c_{q}(τ), whence (15).

ii) When σ ∈ 𝔖_{n} is a cycle of maximum length, one has ℨ(σ) = p_{n}, hence the image of ℨ contains also all the products of power sums and we get Im(ℨ) = Sym. Then, by Proposition 3.1(i), ⋆ is distributive on the left over ×. Complete distributivity is a consequence of the commutativity of ⋆, which straightforwardly follows from the definition.

□

The following structural result goes into particulars of the distributivity of ⋆ over ×.

Proposition 3.2. Let ℕ^{∗} and 𝔭 respectively stand for the set of positive natural numbers and the set of prime numbers. Let ℕ^{(ℕ^{∗})} (respectively ℕ^{(𝔭)}) denote the set of sequences of natural numbers indexed by ℕ^{∗} (respectively indexed by 𝔭) with finitely many non-zero elements. Let P be the set of products of power sums, i.e., P = {∏_{i=1}^{∞} p_{i}^{α_{i}}}_{(α_{i})_{i≥1}∈ℕ^{(ℕ^{∗})}}. Then P is closed under × and ⋆: more precisely (P, ×, ⋆) is isomorphic to a subsemiring of the ℤ-algebra ℤ[ℕ^{(𝔭)}] of the monoid (ℕ^{(𝔭)}, sup) (where sup stands for the componentwise supremum).

Proof. The fact that P is closed under × and ⋆ follows from the definition and (14). Now P contains the two units (1 and p_{1}) of the 2-associative algebra Sym, therefore (as a consequence of the properties established for the products ×, ⋆) it is a semiring. For every q ∈ 𝔭 and n ∈ ℕ^{∗}, let ν_{q}(n) denote the exponent of q in the decomposition of n in prime factors (n = ∏_{q∈𝔭} q^{ν_{q}(n)}); for a fixed n, we naturally identify q ↦ ν_{q}(n) with the sequence (ν_{2}(n), ν_{3}(n), …) ∈ ℕ^{(𝔭)}. Define an arrow ϕ : P → ℤ[ℕ^{(𝔭)}] by

ϕ( ∏_{1≤i≤∞} p_{i}^{α_{i}}) = ∑_{1≤i≤∞} iα_{i}(q ↦ ν_{q}(i)).  (16)

As ϕ(m_{1}m_{2}) = ϕ(m_{1}) + ϕ(m_{2}) by construction (16), it suffices to prove that

ϕ(p_{i} ⋆ p_{j}) = ϕ(p_{i}) ×_{sup} ϕ(p_{j}),

where ×_{sup} stands for the product in ℤ[(ℕ^{(𝔭)}, sup)]. But

ϕ(p_{i} ⋆ p_{j}) = ϕ(p_{lcm(i,j)}^{gcd(i,j)})
= gcd(i, j)ϕ(p_{lcm(i,j)})
= gcd(i, j) lcm(i, j)(q ↦ ν_{q}(lcm(i, j))
= gcd(i, j) lcm(i, j)(q ↦ sup(ν_{q}(i), ν_{q}(j)))
= ij(q ↦ sup(ν_{q}(i), ν_{q}(j)))
= ϕ(p_{i}) ×_{sup} ϕ(p_{j}).

Since the arrow ϕ is clearly into, the claim is proved. □

3.2. Cycle index. Let 𝔖 = ⨆_{n≥0} 𝔖_{n} be the disjoint union of all the symmetric groups and 𝔖_{sg} = ⋃_{n≥0} (𝔖_{n})_{sg} be the set of all the subgroups of all symmetric groups. For the sake of simplicity, we identify a permutation group G ∈ (𝔖_{n})_{sg} with its action (G, {0, …, n − 1}) (see Section 2.1). The laws → + and ↗ ↘ can be defined over 𝔖_{sg}; for G_{1} ∈ (𝔖_{n})_{sg} and G_{2} ∈ (𝔖_{m})_{sg}, set

G_{1} → + G_{2} := (G_{1} × G_{2}, {0, …, n + m − 1}),  (17)

where G_{1} acts on {0, …, n − 1} and G_{2} acts on {n, …, n + m − 1}, and

G_{1} ↗ ↘ G_{2} := (G_{1} × G_{2}, {0, …, nm − 1}),  (18)

where the action on {0, …, nm − 1} is given by (σ_{1}, σ_{2})k = ψ^{−1}((σ_{1}, σ_{2})ψ(k)), the map ψ being the bijection ψ : {0, …, nm − 1} → {0, …, n − 1} × {0, …, m − 1} defined by ψ(i + nj) = (i, j) if 0 ≤ i ≤ n − 1 and 0 ≤ j ≤ m − 1 and (σ_{1}, σ_{2})(i, j) = (σ_{1}i, σ_{2}j). Note that both → + and ↗ ↘ are associative but ↗ ↘ is not distributive over → + .

Let Z : 𝔖_{sg} → Sym be defined by

Z(G) = ℨ (\frac{1}{|G|} ∑_{σ∈G} σ) ,  (19)

where the map ℨ is defined by Equation 13 above.

Z(G) is called Pólya’s cycle index (or Pólya’s cycle indicator polynomial) of G [14].

Example 3.3. (1) The cycle index of the symmetric group 𝔖_{n} is Z(𝔖_{n}) = h_{n}. (2) The cycle index of the alternating group A_{n} is Z(A_{n}) = h_{n} + e_{n}. Here h_{n} (respectively e_{n}) denotes the nth complete (respectively the nth elementary)

symmetric function. These examples appear as exercises in [12, p. 29, Ex. 9].

Since ℨ is a homomorphism of 2-associative algebras, one recovers the classical relations (see [4])

Z(G_{1} → + G_{2}) = Z(G_{1})Z(G_{2})  (20)
Z(G_{1} ↗ ↘ G_{2}) = Z(G_{1}) ⋆ Z(G_{2})  (21)

Example 3.4. (1) The cycle index of the intransitive product of two symmetric groups 𝔖_{n} and 𝔖_{m} is

Z(𝔖_{n} → + 𝔖_{m}) = h_{n}h_{m}.

(2) The cycle index of the Cartesian product of two symmetric groups 𝔖_{n} and 𝔖_{m} is

Z(𝔖_{n} ↗ ↘ 𝔖_{m}) = h_{n} ⋆ h_{m} = _{∑_{|λ|=n} ; |ρ|=m}m_{λ} ⋆ m_{ρ} = _{∑_{|λ|=n} ; |ρ|=m} \frac{1}{z_{λ}z_{ρ}} ∏_{i,j} p_{lcm(λ_{i},ρ_{j})}^{gcd(λ_{i},ρ_{j})},

where the sum runs over all (integer) partitions λ = λ_{1} ≥ λ_{2} ≥ ⋯ of n and all (integer) partitions ρ = ρ_{1} ≥ ρ_{2} ≥ ⋯ of m; m_{λ} denotes the monomial symmetric function indexed by λ and z_{λ} = ∏ i^{n_{i}}n_{i}!, where n_{i} is the number of parts of λ equal to i.

3.3. Enumeration of a type of Feynman diagrams related to the Quantum Field Theory of partitions. The cycle indexes are classical tools used in combination with Pólya’s theorem, for the enumeration of unlabelled objects [10, 14]. Let us review Pólya’s general method.

Consider a permutation group G acting on a finite set X = {x_{1}, ⋯, x_{n}}. Let L = {l_{0}, …, l_{p}, … } be another (possibly infinite) set, and f : X → L. The type t(f) of f is the vector (i_{0}, …, i_{p}, …), where i_{k} is the number of elements of X whose image by f is l_{k}. The shape s(f) of f is the integer partition obtained by sorting in the decreasing order t(f) and erasing the zeroes. For example, a function f having the type t(f) = (0, 1, 0, 9, 1, 2, 0, …, 0, …) has the shape s(f) = (9, 2, 1, 1). The group G naturally acts on L^{X} by (σ ∘_{N} f) (x) = f(σ ∘x), where ∘ denotes the action of G on X, and ∘_{N} preserves the shape. Besides, Pólya’s cycle index of G, Z(G), is a symmetric polynomial and can expanded in the basis {m_{λ}}_{λ⊢n} of monomial symmetric polynomials. Pólya’s cycle index theorem asserts that the coefficient of m_{λ} in this expansion is the number d_{λ}^{s}(G, L) of G-classes on L^{X} with given shape λ:

Z(G) = ∑_{λ} d_{λ}^{s}(G, L)m_{λ}.  (22)

Now, let us apply this method to enumerate the Feynman diagrams arising in the expansion of formula (1). These diagrams are unlabelled 2-coloured multigraphs (or 2-coloured graphs with edges weighted by positive integers) with no isolated vertex. By a 2-coloured multigraph, we mean an undirected multigraph whose vertex set is partitioned into a set of white vertices and a set of black vertices, such that every undirected multiedge joins a white vertex with a black vertex.

First, we enumerate all unlabelled 2-coloured multigraphs. Such a computation can be found in [10], so we will only sketch the general case^{1}. Henceforth, and until the end of the present section, 2-coloured multigraphs will be simply referred to as ‘multigraphs’. Let n and m be the numbers of white vertices and the number of black vertices of the multigraph, respectively. We represent the multiedge set of the multigraph as a function e from {0, …, n − 1} × {0, …, m − 1} to ℕ. The type (respectively the shape) of a such a multigraph is the type (respectively the shape) of its multiedge set, i.e., t(e) (respectively s(e)). The ith component of the type vector gives the number of (multi)edges with weight i.

As we consider unlabelled multigraphs, we identify multigraphs that can be obtained from one another by independently permuting the white vertices and the blacks vertices, i.e by a Cartesian action of an ordered pair (σ_{1}, σ_{2}) ∈ 𝔖_{n} × 𝔖_{m}. Therefore, the number d_{I}(n, m) of multigraphs with type I is equal to the number of orbits with type I, for the action of 𝔖_{n} ↗ ↘ 𝔖_{m} on ℕ^{{0,...,n−1}×{0,...,m−1}}. Hence, the generating function of the shape is given by

g(n, m) := ∑_{λ} d_{λ}^{s}(n, m)m_{λ} = Z(𝔖_{n}) ⋆ Z(𝔖_{m}).  (23)

Specializing the symmetric function appearing in 23 to the alphabet {y_{0}, …, y_{k}, …, }, the coefficient d_{I}^{t}(n, m) of ∏ y_{k}^{i_{k}} in the expansion of g(n, m) is equal to the number of multigraphs with type I = (i_{0}, …, i_{k}, …),

g(n, m) = ∑_{I=(i_{0},...,i_{p},...)} d_{I}^{t}(n, m) ∏_{k=0}^{∞} y_{k}^{i_{k}}.  (24)

1Of course, the following computations (and more general ones) could be carried out within the framework of the theory of species [3].

Note that one can enumerate multigraphs having (multi)edges with weights less than or equal to p by specializing to the finite alphabet {y_{0}, …, y_{p}}.

Let us define the generating functions of the type of our Feynman diagrams

F (n, m) := ∑_{I=(i_{0},...,i_{p},...)} f_{I}^{t}(n, m) ∏_{k=0}^{∞} y_{k}^{i_{k}},  (25)

where f_{I}^{t}(n, m) denotes the number of Feynman diagrams of type I. Observe that F (n, m) is a symmetric function over the alphabet {y_{1}, …, y_{p}, … } but not over {y_{0}, …, y_{p}, … }.

Example 3.5. Let us give the first examples of generating functions, for weights in {0, 1, 2}.

(1) F (1, 1) = y_{1} + y_{2},

(2) F (2, 1) = F (1, 2) = y_{1}^{2} + y_{1}y_{2} + y_{2}^{2},

(3) F (2, 2) = y_{0}^{2}y_{1}^{2} + y_{0}^{2}y_{2}^{2} + y_{0}^{2}y_{1}y_{2} + y_{0}y_{1}^{3} + 3y_{0}y_{1}^{2}y_{2} + 3y_{0}y_{1}y_{2}^{2} + y_{0}y_{2}^{3} + y_{1}^{4} + y_{1}^{3}y_{2} +

3y_{1}^{2}y_{2}^{2} + y_{1}y_{2}^{3} + y_{2}^{4}. One can remark that under this specialization,

F (2, 2) + F (2, 1)y_{0}^{2} + F (1, 2)y_{0}^{2} + F (1, 1)y_{0}^{3} + y_{0}^{4} = 3m_{22} + m_{4} + 3m_{211} + m_{31} = g(2, 2).

The latter equality can be formulated in a more general setting.

Theorem 3.6. One has the following decomposition of the cycle index:

Z(𝔖_{n} ↗ ↘ 𝔖_{m}) = y_{0}^{nm} + ∑_{(1,1)≤_{lex}(k,p)≤_{lex}(n,m)} F (k, p)y_{0}^{nm−kp}.  (26)

Proof. It suffices to notice that a 2-coloured multigraph is either a 2-coloured multigraph with no isolated vertex (i.e., a Feynman diagram) or the union of some isolated vertex and a smaller 2-coloured multigraph. □

This yields a nice induction formula for the F (n, m)’s.

Example 3.7. From Theorem 3.6, one has

F (3, 2) = Z(𝔖_{3} ↗ ↘ 𝔖_{2}) − F (3, 1)y_{0}^{3} − F (2, 2)y_{0}^{2} − F (2, 1)y_{0}^{4} − F (1, 2)y_{0}^{4} − F (1, 1)y_{0}^{5} − y_{0}^{6}.

From Example 3.5, it suffices to compute F (3, 1) = y_{1}^{3} + y_{2}^{3} to enumerate Feynman diagrams whose edges are weighted by 0, 1 or 2. After simplification, one obtains

F (3, 2) = y_{2}^{6} + y_{2}^{5}y_{1} + 3y_{2}^{4}y_{1} + 3y_{2}^{4}y_{1}y_{0} + 2y_{2}^{4}y_{0}^{2} + 3y_{2}^{3}y_{1}^{3} + 6y_{2}^{3}y_{1}^{2}y_{0} + 5y_{2}^{3}y_{1}y_{0}^{2}

+ y_{2}^{3}y_{0}^{3} + 3y_{2}^{2}y_{1}^{4} + 3y_{2}^{2}y_{1}^{3}y_{0} + 8y_{2}^{2}y_{1}^{2}y_{0}^{2} + 3y_{2}^{2}y_{1}y_{0}^{3} + y_{2}y_{1}^{5} + 3y_{2}y_{1}^{4}y_{0} + 5y_{2}y_{1}^{3}y_{0}^{2}

+ 3y_{2}y_{1}^{2}y_{0}^{3} + y_{1}^{6} + y_{1}^{5}y_{0} + y_{1}^{3}y_{0}^{3} + 2y_{1}^{2}y_{0}^{4}.

For example, there are eight (2, 2, 2)-Feynman diagrams:

[figure]

4. Noncommutative realizations

4.1. Free quasi-symmetric cycle index algebra. Let (A, <) be an ordered alphabet and w ∈ A^{∗} a word of length n. One denotes by Std(w) the standardization of w, i.e., the permutation σ ∈ 𝔖_{n} defined by

σ(i) = (Number of letters = w[i] in w[1..i] + number of letters < w[i] in w). (27)

Recall that the algebra FQSym of free quasi-symmetric functions is defined by one of its bases, indexed by 𝔖 and defined as follows:

F_{σ} = ∑_{Std(w)=σ^{−1}} w ∈ ℤ⟨⟨A⟩⟩.  (28)

In [6], it is shown that FQSym is freely generated by the F_{σ}’s, where σ runs over the connected permutations (see [5]) (i.e., permutations such that σ([1, k]) ≠ [1, k] for each k). The algebra FQSym is spanned by a linear basis, {F^{σ}}_{σ∈𝔖}, whose product implements the intransitive action → + :

F^{σ} = F_{σ_{1}} ⋯ F_{σ_{n}},  (29)

where σ = σ_{1} → + ⋯ → + σ_{n} is the maximal factorisation of σ as a product of connected permutations. As a consequence of this definition, one has

F^{σ}F^{τ} = F^{σ→ + τ}.  (30)

This naturally induces an isomorphism of algebras

\underline{ℨ} : (⨁_{n≥0} ℚ[𝔖_{n}], → + , +) → (FQSym, ·, +)
σ ↦ F^{σ}.  (31)

One defines the product ⋆ on FQSym by F^{σ} ⋆ F^{τ} := F^{σ↗ ↘τ}, so \underline{ℨ} becomes a morphism of 2-associative algebras. Furthermore, ⋆ is associative, distributive over the sum and semi-distributive over the shifted concatenation.

4.2. Free quasi-symmetric analogue of Pólya’s cycle index. Recall that 𝔖_{sg} denotes the set of all permutation groups. Following the same pattern as in the commutative setting (see Sections 3.1 and 3.2 above), one defines a map \underline{Z} : 𝔖_{sg} → FQSym by

\underline{Z}(G) := \underline{ℨ} (\frac{1}{|G|} ∑_{σ∈G} σ) = \frac{1}{|G|} ∑_{σ∈G} F^{σ}.  (32)

\underline{Z}(G) will be called Pólya’s free quasi symmetric cycle index of G.

Note 4.1. There is another basis of FQSym indexed by permutations, namely {G^{σ}}_{σ∈𝔖}. It is obtained by setting G_{σ} = F_{σ^{−1}}, and applying the same construction as above to get a linear basis multiplicative with respect to → + (see Equation (30)), yields

G^{σ} = G_{σ_{1}} ⋯ G_{σ_{n}},  (33)

where σ = σ_{1} → + ⋯ → + σ_{n} is the maximal factorisation of σ as a product of connected permutations. In this case, σ^{−1} splits maximally into σ_{1}^{−1} → + ⋯ → + σ_{n}^{−1}, so one also has G^{σ} = F^{σ^{−1}} and formula (32) can be rewritten

\underline{Z}(G) = \frac{1}{|G|} ∑_{σ∈G} G^{σ}.  (34)

The polynomial \underline{Z}(G) has properties similar to that of Z(G), in particular with respect to the laws → + and ↗ ↘.

Proposition 4.2. Let G_{1}, G_{2} ∈ 𝔖_{sg} be two permutation groups, one has (1) \underline{Z}(G_{1} → + G_{2}) = \underline{Z}(G_{1})\underline{Z}(G_{2}).

(2) \underline{Z}(G_{1} ↗ ↘ G_{2}) = \underline{Z}(G_{1}) ⋆ \underline{Z}(G_{2}).

Consider the homomorphism z : FQSym → Sym defined by z(F^{σ}) = ℨ(σ). Note that it is not a Hopf homomorphism because z(F^{231}) = p_{3}.

The following diagram is commutative:

𝔖_{sg} ⟶^{\underline{Z}} FQSym
Z ↓ ^{z} ↙ ↑ \underline{ℨ}  (35)
Sym ⟵_{ℨ} ⨁_{n≥0} ℚ[𝔖_{n}]

Example 4.3. (1) The free quasi-symmetric cycle index of 𝔖_{n} is

H_{n} := \underline{Z}(𝔖_{n}) = \frac{1}{n!} ∑_{σ∈𝔖_{n}} F^{σ}.

One can regard H_{n} as a free quasi-symmetric analogue of the complete symmetric function h_{n}: indeed z(H_{n}) = Z(𝔖_{n}) = h_{n}.

(2) One can define free quasi-symmetric analogues of elementary symmetric functions, by considering the free quasi-symmetric cycle index of the alternative groups:

E_{n} := \underline{Z}(A_{n}) − \underline{Z}(𝔖_{n}).

We get z(E_{n}) = Z(A_{n}) − Z(𝔖_{n}) = e_{n}.

(3) The knowledge of analogues of other symmetric functions should be useful to understand the combinatorics of the free quasi-symmetric cycle indexes. In particular, it should be interesting to find free quasi-symmetric functions whose images by z are the monomial symmetric functions.

4.3. Realizations in MQSym. We will call labelled diagrams the Feynman diagrams as defined in Section 3.3, but with p white (respectively q black) vertices labelled bijectively by integers in [1..p] (respectively in [1..q]). When one draws such a diagram, one implicitly assumes that the labelling goes from top to bottom:

[figure]
Labelled diagram of the matrix ( \begin{matrix}2 & 0 & 1 \\ 0 & 2 & 1 \end{matrix} )

Now, to such a p × q labelled diagram, we can associate a matrix in ℕ^{p×q} and this correspondence is one-to-one. The condition that no vertex be isolated is equivalent to the condition that there be no complete line or column of zeroes, i.e., the representative matrix is packed [6]. In the same way, the diagrams are in one-to-one correspondence with the classes of packed matrices under the permutations of lines and columns as shown below (the vertical arrows are then one-to-one):

Packed matrices ⟶^{Class} Classes of packed matrices
↓  ↓
Labelled diagrams ⟶  Diagrams

(36)

There is an interesting structure of Hopf algebra (in fact an enveloping algebra) over the diagrams [7] which can be pulled back in a natural way to labelled diagrams.

The correspondence described above allows to construct a new Hopf algebra structure on MQSym and a Hopf algebra structure on the space spanned by the classes.

5. Conclusion

Other realizations in Hopf algebras seem feasible. For example, let us consider the Hopf algebras of graphs GQSym^{110} and GT Sym^{110} defined in [13]. An interesting mapping from ⨁_{n≥0} ℚ[𝔖_{N}] to GQSym^{110} or GT Sym^{110} can be constructed, sending each cycle to an equivalent loop.

More precisely, J.-Y. Thibon (personal communication) showed to us how to construct a non-commutative Hopf algebra which is the dual of a quotient of a subalgebra of GT Sym^{110}. This algebra is Hopf homomorphic to Sym and has two bases indexed by permutations, whose commutative images are proportional to power sums and monomial symmetric functions, respectively. This construction gives natural noncommutative analogues of Pólya’s cycle index.

Acknowledgements We are grateful to J.-Y. Thibon for fruitful comments.

References

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

[2] C.M. Bender, D.C. Brody, and B.K. Meister, Combinatorics and field theory, Twistor Newsletter 45 (2000) 36–39.

[3] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press (Encyclopedia of Mathematics and its Applications 67), Cambridge, 1997.

[4] P.J. Cameron, D.A. Gewurz, and F. Merola, Product action (2004), available at

http://www.maths.qmw.ac.uk/∼pjc/preprints/product.pdf.

[5] L. Comtet, Sur les cœfficients de l’inverse de la série formelle ∑ n!t^{n}, C.R. Acad. Sci. Paris, Ser. A 275 (1972) 569–572.

[6] G. Duchamp, F. Hivert, and J.-Y. Thibon, Non commutative functions VI: Free quasi-symmetric functions and related algebras, Int. J. Algebra Comput. 12(5) (2002) 671–717.

[7] G. H. E. Duchamp, K.A. Penson, A.I. Solomon, A. Horzela, and P. Blasiak, Hopf algebras and Lie group structures inherent in combinatorial field theories, New symmetries in Mathematical Physics (CIRM, November 22–26, 2004).

[8] G. H. E. Duchamp, K.A. Penson, A.I. Solomon, A. Horzela and P. Blasiak, One-parameter groups and combinatorial physics, Third International Workshop on Contemporary Problems in Mathematical Physics (COPROMAPH3), Porto–Novo (Benin), November 2003; arχiv:quant-ph/0401126.

[9] K.A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A.I. Solomon, Hierarchical Dobiński-type relations via substitution and the moment problem, J. Phys. A: Math. Gen. 37 (2004) 3475–3487;

arχiv:quant-ph/0312202.

[10] V. Krishnamurthy, Combinatorics, Theory and Applications, Affiliated East-West Press, New Delhi–Madras, 1927.

[11] J.-L. Loday and M. Ronco, On the structure of cofree Hopf algebras, J. reine angew. Math. 592

(2006) 123–155; arχiv:math.QA/0405330.

[12] I.G. Macdonald, Symmetric functions and Hall polynomials, second edition, Clarendon Press, Oxford, 1995.

[13] J.-C. Novelli, J.-Y. Thibon, and N. Thiéry, Algèbres de Hopf de graphes, C. R. Acad. Sci. Paris Ser. I

339 (2004) 607–610; available at http://www-igm.univ-mlv.fr/∼jyt/ARTICLES/graphs.ps.

[14] G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen., Acta Math. 68 (1937) 145–254.

[15] A.I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K.A. Penson, Combinatorial Physics, Normal Order and Model Feynman Graphs, in B. Gruber, G. Marmo, and N. Yoshinaga (Eds): Symmetries in Science, Vol. XI, Kluwer Publ., 2004; arχiv:quant-ph/0310174.