Combinatoire, Informatique et Physique : Algèbre des Diagrammes

Gérard H. E. Duchamp,

18.06.05 07:23

Contents

0 Tentative plan 1

3 Les problémes à une et deux exponentielles :

exp(g(x)) et exp(f(xd/dy))exp(g(y))|_{y=0}  2

3.1 Matrice de Stirling generalisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3.2 One parameter groups and the connected graph theorem . . . . . . . . . . . . . . 4 3.3 Product formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.4 The double exponential formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Monomial expansion of the double exponential formula 6

5 Diagrammatic expansion of the double exponential formula 9 5.1 FBD, bitypes and packed matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.2 Counting the multiplicities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5.2.1 For ordered bi-partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.2.2 For unordered bi-partitions . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6 The Hopf algebra structures Δ_{W S} and Δ_{BS} 11 6.1 Structure results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

0 Tentative plan

1) Second quantized partition function T r(exp(−βH))

2) Reordering problem for H = H(a^{+}, a) (with examples)

3) The exp(G(x)) and exp(F (xd/dy))G(y)|_{y=0} problems

4) Diagrammatic expansion for the double exponential form

5) The Hopf algebra structures Δ_{W S} and Δ_{BS}

6) Relation of the Hopf structures to the physical problems

3 Les problémes à une et deux exponentielles :

exp(g(x)) et exp(f(xd/dy))exp(g(y))|_{y=0}

3.1 Matrice de Stirling generalisée

Commençons par définir l’algèbre de Wey, W. Ce sera ici la ℂ-algèbre associative unifère (c’est à dire avec élément unité [2] III. 1 après la définition 1), définie par la présentation suivante

⟨a^{+}, a; [a^{+}, a] = 1⟩_{ℂ -alg-ass-unit}  (1)

c’est à dire par les deux générateurs {a, a^{+}} et l’unique relation [a, a^{+}] = 1. Cette algèbre est de dimension de Gelfand-Kirillov 2 et a une base constituée par les monômes {(a^{+})^{k}a^{l}}_{k,l≥0}. Lorsqu’un élément Ω ^{1} de W est exprimé selon cette base, on dit qu’il est en ordre normal (ou forme normale) soit

Ω = ∑_{k,l} α(k, l)(a^{+})^{k}a^{l}.  (2)

On sait qu’il est impossible de trouver une représentation ρ : W ↦ L(B) où B est un espace de Banach et ρ(a), ρ(a^{+}) sont des opérateurs continus, mais on peut trouver des représentations fidèles, par des opérateurs continus dans des espaces de Fréchet. La plus célèbre de ces représentations est la représentation de Bargmann-Fock qui agit sur l’espace des polynômes ℂ[x] muni de la topologie induite du produit ([11]). Les créations et annihilations sont les suivantes

a ↦ \frac{d}{dx}; a^{+} ↦ x  (3)

où x désigne ici l’endomorphisme P ↦ xP. Ceci rend évident le fait d’adopter la fonction de poids weight(a) = −1; weight(a^{+}) = 1. Soit donc Ω ∈ W un operateur homogène par rapport à cette fonction de poids. Il est de la forme

Ω = ∑_{k−l=e≥0} c(k, l)(a^{+})^{k}a^{l}  (4)

où e est le degré, qui est appelé excédent par les physiciens car il représente l’excédent (peut-être négatif) des créations sur les annihilations. Selon que celui-ci est positif ou négatif, la forme normale de Ω^{n} est

N (Ω^{n}) = (a^{+})^{ne} (∑_{k=0}^{∞} S_{Ω}(n, k)(a^{+})^{k}a^{k}) or (∑_{k=0}^{∞} S_{Ω}(n, k)(a^{+})^{k}a^{k}) (a)^{n|e|}  (5)

Nous obtenons ainsi des quantités combinatoires ^{2} à deux indices {S_{Ω}(n, k)}_{n,k≥0} c’est à dire une matrice doublement infinie de format N×N qui sera appelée matrice de Stirling généralisée de Ω. *** In fact, it is easily checked that, if the coefficients c(k, l) of Ω are non-negative integers, so are the entries (S_{Ω}(n, k)) of this matrix.

1Souvent appelé opérateur à cause de différentes représentations comme celle de Bargmann-Fock.

2Pour l’instant cela qualifiera des éléments de N, mais nous verrons des cas où elles comptent quelque chose.

For Ω = a^{+}a, one gets the usual matrix of Stirling numbers of the second kind.

⌈ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 3 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 7 & 6 & 1 & 0 & 0 & ⋯ \\ 0 & 1 & 15 & 25 & 10 & 1 & 0 & ⋯ \\ 0 & 1 & 31 & 90 & 65 & 15 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}  (6)

For Ω = a^{+}a + aa^{+}, we have

⌈ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 8 & 4 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 26 & 36 & 8 & 0 & 0 & 0 & ⋯ \\ 1 & 80 & 232 & 128 & 16 & 0 & 0 & ⋯ \\ 1 & 242 & 1320 & 1360 & 400 & 32 & 0 & ⋯ \\ 1 & 728 & 7084 & 12160 & 6320 & 1152 & 64 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}  (7)

and for Ω = a^{+}aa^{+} + a^{+}, we gets

⌈ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 6 & 6 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 24 & 36 & 12 & 1 & 0 & 0 & 0 & ⋯ \\ 120 & 240 & 120 & 20 & 1 & 0 & 0 & ⋯ \\ 720 & 1800 & 1200 & 300 & 30 & 1 & 0 & ⋯ \\ 5040 & 15120 & 12600 & 4200 & 630 & 42 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}  (8)

but, for w = a^{+}aaa^{+}a^{+}, one gets

⌈ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 12 & 60 & 54 & 14 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 144 & 1296 & 2232 & 1296 & 306 & 30 & 1 & 0 & 0 & ⋯ \\ 2880 & 40320 & 109440 & 105120 & 45000 & 9504 & 1016 & 52 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}  (9)

Let Ω = ∑_{k,l≥0≥0} c(k, l)(a^{+})^{k}a^{l} (finite supported sum) be a general term of W_{n} in normal form and call dominant term the sum of monomials with maximum length k + l. It is not difficult to prove that, if Ω is homogeneous, the dominant term consists in a single monomial c(k_{0}, l_{0})(a^{+})^{k_{0}}a^{l_{0}}. Thus, the dominant term of Ω^{n} is c(k_{0}, l_{0})^{n}(a^{+})^{nk_{0}}a^{nl_{0}} in the generalized Stirling matrix of Ω, the rightmost non-zero coefficient of the line n has address (n, n(k_{0} − l_{0})) and bears the coefficient c(k_{0}, l_{0})^{n}. Thus all the matrices are row-finite and triangular iff r = 1, which case will be of special interest for us in the following.

Remarque 3.1 There is a beautiful expression of the normal form of w^{n} in case w is a single word in {a, a^{+}}. The normal form of w is

N (w) = ∑_{k≥0} r(B, k)(a^{+})^{r−k}a^{s−k}  (10)

where r(B, k) is the kth rook number of a certain board B constructed after w (see [7, 12] put a more detailed reference), and r = |w|_{a^{+}}; s = |w|_{a} are the number of occurences of a^{+} and a in w.

3.2 One parameter groups and the connected graph theorem

In case Ω is homogeneous and sum of monomials with only one “a”, one has

Ω = ∑_{0≤p≤r} c_{1}(r, p)(a^{+})^{r−p}a(a^{+})^{p}  (11)

and the normal form of Ω writes q(a^{+})a + v(a^{+}) and the image of Ω under the Bargmann-Fock correspondence is

ω = q(x)\frac{d}{dx} + v(x)  (12)

   • cas des opérateurs avec un seul ``a'' : Ω = ∑_{0≤p≤r} c_{1}(r, p)(a^{+})^{r−p}a(a^{+})^{p}
   • lien avec les champs de vecteurs, les groupes  un paramètre, conjugacy trick
   • lien entre l'intégration et les formes normales, formule (avec e l'exédent)

∑_{n,k≥0} S_{Ω}(n, k)\frac{x^{n}}{n!} y^{k} = g(x)e^{yϕ(x)}  (13)
U_{λ}[f](x) = g(λx^{e})f (x (1 + ϕ(λx^{e})))  (14)

• exemple de Ω = x^{2} \frac{d}{dx}x + x\frac{d}{dx}x^{2}

       – on a d'abord la forme conjuguée

Ω = x^{2} \frac{d}{dx}x + x\frac{d}{dx}x^{2} = x^{− \frac{3}{2}} (2x^{3} \frac{d}{dx})x^{\frac{3}{2}}  (15)
e^{λΩ}[f] = x^{− \frac{3}{2}} e^{λ(2x^{3} \frac{d}{dx})}x^{\frac{3}{2}}  (16)
e^{λ(2x^{3} \frac{d}{dx})}[f](x) = f(u^{−1}(u(x) + λ)) for some straightening factor u  (17)

       – differentiating with respect to λ one obtains \frac{1}{u′(x)} = 2x^{3} and then with
         (17), one has the one-parameter group of transformations

e^{λ(2x^{3} \frac{d}{dx})}[f](x) = f(s_{λ}(x) = f (\sqrt{\frac{x^{2}}{1 − 4λx^{2}}} )  (18)

         thus, in view of (17) one gets

e^{λΩ}[f](x) = x^{− \frac{3}{2}} f(s_{λ}(x))s_{λ}(x)^{\frac{3}{2}} = \sqrt[4]{\frac{1}{(1 − 4λx^{2})^{3}}} f (\sqrt{\frac{x^{2}}{1 − 4λx^{2}}} )  (19)

       – and, with (13), we get

∑_{n,k≥0} S_{Ω}(n, k)\frac{x^{n}}{n} y^{k} = (1 − 4x)^{− \frac{3}{4}} exp (y ∑_{n>0} ( \begin{matrix}2n \\ n \end{matrix} ) x^{n})  (20)

         peut-^etre montrer que les coefficients de la série exponentielle (1−4x)^{− \frac{3}{4}}
         sont entiers et appliquer le produit étiqueté.

A great, powerful and celebrated result: (For certain classes of graphs) If C(x) is the EGF of CONNECTED graphs (of a certain class), then exp(C(x)) is the EGF of ALL graphs of the same class. (Uhlenbeck, Mayer, Touchard,) This implies that the matrix

M(n, k) = number of graphs with n vertices and having k connected components  (21)

is the matrix of a substitution (like S_{ω}(n, k) previously but without prefactor). One can prove, using a Zariski-like argument, that, if M is such a matrix (with identity diagonal) then, all its powers (positive, negative and fractional) are substitution matrices and form a one-parameter group of substitutions, thus coming from a vector field on the line which could (in theory) be computed. But no nice combinatorial principle seems to emerge. expliquer cela For example, to begin with the Stirling substitution z ↦ e^{z} − 1. We know that there is a unique one-parameter group of substitutions s_{λ}(z) such that, for λ integer, one has the value (s_{2}(z) ↔ partition of partitions)

s_{2}(z) = e^{e^{z}−1} − 1 ; s_{3}(z) = e^{e^{e^{z}−1}−1} − 1 ; s_{−1}(z) = ln(1 + z)  (22)

In fact, we have no nice description of this group nor of the vector field generating it.

Description de l'expression g(x)e^{yϕ(x)} avec le produit étiqueté

3.3 Product formula

The Hadamard product of two sequences (a_{n})_{n≥0}; (b_{n})_{n≥0} is given by the pointwise product (a_{n}b_{n})_{n≥0}. We can at once transfer this law on EGFs by

( ∑_{n≥0} a_{n} \frac{x^{n}}{n!} ) ⊙ ( ∑_{n≥0} b_{n} \frac{x^{n}}{n!} ) := ∑_{n≥0} a_{n}b_{n} \frac{x^{n}}{n!}  (23)

But, it is not difficult to check that the family

(\frac{(y \frac{∂}{∂x})^{n}}{n!} \frac{x^{m}}{m!} )_{n,m∈N}  (24)

is summable in C[[x, y]] as we have

\frac{(y \frac{∂}{∂x})^{n}}{n!} \frac{x^{m}}{m!} = \{ \begin{matrix}0 & if n > m \\ \frac{y^{n}x^{m−n}}{n!(m−n)!} & otherwise \end{matrix}  (25)

therefore, for F (x) = ∑_{n≥0} a_{n} \frac{x^{n}}{n!} and G(x) = ∑_{n≥0} b_{n} \frac{x^{n}}{n!} yields the product formula

(F ⊙ G)(x) := F (y \frac{∂}{∂x})G(x)|_{x=0} = ∑_{n≥0} a_{n}b_{n} \frac{y^{n}}{n!}  (26)

for this reason, we will call here ⊙ the Hadamard exponential product. With this product, the set of series form a commutative associative algebra with unit, which is actually the product algebra ℂ^{N} and we will return later on to the combinatorial significance of some of its elements (see section (??)).

3.4 The double exponential formula

The case F (0) = G(0) = 1 will be of special interest in the following study. Every series with constant term 1 can be represented by an exponential e^{∑_{n≥1} L_{n} \frac{x^{n}}{n!}} which can be developped using Bell polynomials and Faà di Bruno coefficients. Let us now recall some fact about these combinatorial features. We still consider the alphabet 𝕃 = {L_{1}, L_{2}, ⋯ } = {L_{i}}_{i≥1}, then the complete Bell polynomials [4] are defined by

exp(∑_{m≥1} L_{m} \frac{x^{m}}{m!} ) = ∑_{n≥0} Y_{n}(𝕃)\frac{x^{n}}{n!}  (27)

We will denote alternatively Y_{n}(L_{1}, ⋯ L_{n}) for Y_{n}(𝕃) as this polynomial is independant from the subalphabet (L_{m})_{m>n}. We know [4] that

Y_{n}(𝕃) = Y_{n}(L_{1}, ⋯ L_{n}) = ∑_{||α||=n}((α))𝕃^{α} = ∑_{||α||=n}((α))x_{1}^{α_{1}}x_{2}^{α_{2}} ⋯ x_{n}^{α_{n}}  (28)

where α = (α_{1}, α_{2}, ⋯ α_{n}) is an integral vector, 𝕃^{α} = L_{1}^{α_{1}}L_{2}^{α_{2}} ⋯ L_{n}^{α_{n}} is the multiindex standard notation and

((α)) = \frac{||α||!}{(1!)^{α_{1}}(2!)^{α_{2}} ⋯ (n!)^{α_{n}}(α_{1})! ⋯ (α_{n})!}  (29)

is the Faà di Bruno coefficient [5, 8] which will be interpreted, in the next section, as enumerating structures called set partitions. Combining (27) and (28) one gets

exp( ∑_{m≥1} L_{m} \frac{(y \frac{∂}{∂x})^{m}}{m!} )exp( ∑_{n≥1} V_{n} \frac{x^{n}}{n!} )|_{x=0} = ∑_{k≥0} \frac{y^{k}}{k!} ( ∑_{|α|=|β|}((α))((β))𝕃^{α}𝕍^{β}) (30)

Formula (30) will be called in the sequel the double exponential formula.

4 Monomial expansion of the double exponential formula

In this paragraph, we will use unordered and ordered set partitions. By unordered partition P of the set X we mean a finite subset P ⊂ (𝔓(X) − {∅}) (𝔓(X) is the set of all subsets of X [4]) such that

⋃_{Y ∈P} Y = X and (Y_{1}, Y_{2} ∈ P, Y_{1} ≠ Y_{2} ⟹ Y_{1} ∪ Y_{2} = ∅)  (31)

this explains why without any convention the classical Stirling number of second kind S(0, 0) equals 1. The elements of P are called blocks. Following Comtet ([5] p 39), we will say that a partition P is of type α = (α_{1}, α_{2}, ⋯, α_{m}) iff there is no j-block for j > m and α_{j} j-block(s) for each j ≤ m. This implies in particular that the set X is of cardinality ||α|| := ∑_{j=1}^{m} jα_{j}. The number of partitions of type α of a given set is (see [5, 8])

((α)) = \frac{||α||!}{∏_{j=1}^{m}(j!)^{α_{j}}α_{j}!}.  (32)

This number is called the Faà di Bruno coefficient of type α [8]. Here one can see easily that the number of blocks of a partition of type α is |α| = ∑_{j=1}^{m} α_{j}. An ordered partition of type α of the set X is just a partition in which the blocks are labelled from 1 to |α| (|α| is the number of blocks). In other words, one could say that an ordered partition is a list of subsets and an unordered partition is a set of subsets. To every ordered partition P = (B_{1}, B_{2}, ⋯, B_{|α|}) corresponds an unordered one Φ_{p}(P) = {B_{1}, B_{2}, ⋯, B_{|α|}} where Φ_{p} is the “forgetful” function which forgets the order. Now to a pair (P^{(1)}, P^{(2)}) of ordered partitions of the same set (call it X)

P^{(1)} = (B_{1}^{(1)}, B_{2}^{(1)}, ⋯, B_{k_{1}}^{(1)}); P^{(2)} = (B_{1}^{(2)}, B_{2}^{(2)}, ⋯, B_{k_{2}}^{(2)})  (33)

one can associate the intersection matrix IM_{o}(P^{(1)}, P^{(2)}) such that the entry of address (i, j) is the number of elements of the intersection of the block i of the first partition and the block j of the second. For example with partitions of X = {1, 2, 3, 4, 5, 6}, and specifying

P^{(1)} = ({1, 2, 5}, {3, 4, 6}), P^{(2)} = ({1, 2}, {3, 4}, {5, 6}),

one gets

{1, 2} {3, 4} {5, 6}
{1, 2, 5}  2  0  1
{3, 4, 6}  0  2  1

and hence the matrix

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

Formally, IM_{o}(P^{(1)}, P^{(2)}) is the matrix of size k_{1} × k_{2} such that

IM_{o}(P^{(1)}, P^{(2)})[i, j] = ♯ (B_{i}^{(1)} ⋂ B_{j}^{(2)})  (35)

The matrices obtained this way are identical to the so-called packed matrices defined in [6]. All packed matrix can be obtained through the matching procedure illustrated above. If we consider now a pair of unordered partitions (Q^{(1)}, Q^{(2)}), we cannot associate to them a single matrix but, rather a class of matrices obtained from the preimages of (Q^{(1)}, Q^{(2)}) under Φ_{p} × Φ_{p}. In a compact formulation, the set of matrices so obtained is

\{IM_{0}(P^{(1)}, P^{(2)})\}_{{Φp(P^{(1)})=Q^{(1)} \atop Φp(P^{(2)})=Q^{(2)}}}  (36)

For example, with

(Q^{(1)}, Q^{(2)}) = ({{1, 2, 5}, {3, 4, 6}} , {{1, 2}, {3, 4}, {5, 6}})  (37)

one gets the 12 preimages (P_{i}^{(1)}, P_{j}^{(2)}), where P_{i}^{(1)} are among the two preimages of Q^{(1)} and P_{j}^{(2)} are among the 6 preimages of Q^{(2)}. Explicitely

P_{1}^{(1)} = ({1, 2, 5}, {3, 4, 6}) P_{2}^{(1)} = ({3, 4, 6}, {1, 2, 5})

are the preimages of Q^{(1)} and

P_{1}^{(2)} = ({1, 2}, {3, 4}, {5, 6}) P_{2}^{(2)} = ({1, 2}, {5, 6}, {3, 4})
P_{3}^{(2)} = ({3, 4}, {1, 2}, {5, 6}) P_{4}^{(2)} = ({3, 4}, {5, 6}, {1, 2})
P_{5}^{(2)} = ({5, 6}, {1, 2}, {3, 4}) P_{6}^{(2)} = ({5, 6}, {3, 4}, {1, 2})

are the preimages of Q^{(2)}. The set of matrices so obtained reads

IM_{u}(M) = \{ (\begin{matrix}2 & 0 & 1 \\ 0 & 2 & 1 \end{matrix}) , (\begin{matrix}2 & 1 & 0 \\ 0 & 1 & 2 \end{matrix}) , (\begin{matrix}1 & 2 & 0 \\ 1 & 0 & 2 \end{matrix}) , (\begin{matrix}0 & 2 & 1 \\ 2 & 0 & 1 \end{matrix}) , (\begin{matrix}0 & 1 & 2 \\ 2 & 1 & 0 \end{matrix}) , (\begin{matrix}1 & 0 & 2 \\ 1 & 2 & 0 \end{matrix}) \}

This is the orbit of one of them under permutation of lines and columns. The acting group is the direct product 𝔖_{r} × 𝔖_{c} where r (resp. c) is the number of raws (resp. columns) of the given matrix. The actions of the elementary generators of this group are, for each i ∈ [1, r] (resp. j ∈ [1, c]), the σ_{i}^{r} (resp. σ_{j}^{c}) i.e. the exchange of raw i with raw i + 1 (resp. the exchange of column j with column j + 1).

Let us go back to the example and fix one of them, say M = (\begin{matrix}2 & 0 & 1 \\ 0 & 2 & 1 \end{matrix}), the number of elements

in the orbit is

\frac{12}{♯ symmetry group of M} = 6  (38)

the isotropy group of M being here the pair {Id, σ_{1}^{c}σ_{1}^{l}}. The correspondence which, to a pair of unordered partitions associates a class of matrices (under permutations of lines and columns) will be denoted IM_{u} as in the example. Thus, one gets a commutative diagram of mappings

Pairs of ordered partitions ⟶^{Φ_{p}×Φ_{p}} Pairs of unordered partitions
IM_{o}↓  ↓^{IM_{u}}
Packed matrices  ⟶^{Class} Classes of packed matrices
Dg_{o}↓  ↓^{Dg_{u}}
Labelled diagrams  ⟶^{Φ_{d}}  Diagrams

(39)

The scheme presented above shows how to associate to a pair of unordered (resp. ordered) set partitions a packed matrix (resp. a class of packed matrices). The packed matrices can be alternatively represented by labelled diagrams which are unoriented bipartite multigraphs. The two sets of vertices being a column of white spots and column of black spots as shown below

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

In the sequel we will set Diag_{u} := Dg_{u} ∘ IM_{u} and Diag_{o} := Dg_{o} ∘ IM_{o} for the mapping which associates diagrams to pairs of partitions. Now, the multiplicity of a diagram D is the number of pairs (P^{(1)}, P^{(2)}) of unordered partitions such that Dr_{u}(IM_{u}(P^{(1)}, P^{(2)})) = D. We remark that the types of the left (resp. right) components α(P^{(1)}) (resp. α(P^{(2)}) ) are the same. These common types are therefore characteristic of the diagram itself and we will refer to it as the left (resp. the right) type of D, α(D) (resp. β(D)). The product formula now reads

exp( ∑_{m≥1} \frac{L_{m}}{m!} (y \frac{∂}{∂x})^{m} )exp( ∑_{n≥1} \frac{V_{n}}{n!} x^{n})|_{x=0} = ∑_{n≥0} \frac{y^{n}}{n!} ( ∑_{{D diagram \atop |D|=n}} mult(D)𝕃^{α(D)}𝕍^{β(D)})

= ∑_{D diagram} \frac{mult(D)}{|d|!}m(D, 𝕃, 𝕍, y)  (40)

with

m(D, 𝕃, 𝕍, y) := 𝕃^{α(D)}𝕍^{β(D)}y^{|d|}  (41)

5 Diagrammatic expansion of the double exponential formula

The main interest of the expansion (30) is that we can impose (at least) two types of rules on the diagrams

• on the diagrams themselves (selection rules) : on the outgoing degrees, ingoing degrees, total or partial weights (the graph is supposed oriented from white to black spots)

   • décrire ce que l'on sait déjà faire sur les mon^mes :  produit et coproduit.
     Donner l'exemple d'un produit et du coprodt de x^{3}y^{5}

• on the set of diagrams (composition and decomposition rules) : product and coproduct on the space of diagrams.

The last item suggests us to (try to) structure the (specs of) diagrams into a Hopf algebra. To do so, we have to proceed in three steps.

• First Step : Define the space

• Second Step : Define a product

• Third Step : Define a coproduct

First step. — Let Diag_{ℂ} (resp. LDiag_{ℂ}) be the ℂ-vector space freely generated by the diagrams (resp. labelled diagrams) i.e.

Diag_{ℂ} := ⨁_{d diagram} ℂd ; LDiag_{ℂ} := ⨁_{d labelled diagram} ℂd  (42)

at this stage, we have a linear arrow LDiag_{ℂ} ↦ Diag_{ℂ} provided by the linear extension of Φ_{d}. Second step. — The product on the set of diagrams is just the is just the superposition of diagrams

d_{1} ⋆ d_{2} = \begin{matrix}d_{1} \\ d_{2} \end{matrix} .  (43)

This amounts to the blockdiagonal product of packed matrices. Indeed, for M_{1}, M_{2} packed one has

Dg_{o} ((\begin{matrix}M_{1} & 0 \\ 0 & M_{2} \end{matrix})) = Dg_{o}(M_{1}) ⋆ Dg_{o}(M_{2}).  (44)

This product yields the product of monomials in the following way. For D a diagram via the “m” correspondence as we have, with the setting of (41)

m(d_{1} ⋆ d_{2}, 𝕃, 𝕍, z) = m(d_{1}, 𝕃, 𝕍, z)m(d_{2}, 𝕃, 𝕍, z)  (45)

This product is associative with unit (the empty diagram) and thus endows the set of labelled diagrams with a structure of monoid. It is compatible with the arrow Φ_{d} and so defines the product on Diag which, in turn is compatible with the product of monomials.

Labelled diagrams^{2} ⟶^{Φ_{d}×Φ_{d}} Diagrams^{2} ⟶^{m(?,𝕃,𝕍,z)×m(?,𝕃,𝕍,z)} Monomials^{2}
product↓  ^{product}↓  ^{product}↓
Labelled diagrams ⟶^{Φ_{d}} Diagrams  ⟶^{m(?,𝕃,𝕍,z)}  Monomials

(46)

Third step. — For the coproduct on LDiag, we have several possibilities :

1. split with respect to the white spots (two ways : by intervals and by subsets)

2. split with respect to the black spots (two ways : by intervals and by subsets)

3. split with respect to the edges

Comment 5.1 : i) (3) does not give a nice identity with the monomials (when applying d ↦ m(d,?,?,?))) nor do (2) and (3) by intervals. ii) (2) and (3) are essentially the same (because of the WS ↔ BS symmetry). In fact (2) and (3) by subsets give a good representation and, moreover, they are appropriate for several physics models.

In section (6), we will develop the possibility (1) and (2) by subsets.

5.1 FBD, bitypes and packed matrices

5.2 Counting the multiplicities

5.2.1 For ordered bi-partitions

We here indicate a way to compute the factor mult(D) od a given diagram D. Let M be a packed matrix such that

Φ_{d}(Dr_{o}(M)) = D  (47)

we can formalize the notion of labelling the edges of D in the following way. We will say that a mapping

λ : [1..|D|] ↦ [1..|α(D)|] × [1..|β(D)|]  (48)

is M-compatible iff, for each address (i, j) ∈ [1..|α(D)|] × [1..|β(D)|], one has |λ^{−1}(i, j)| = M[i, j]. Every pair (P^{(1)}, P^{(2)}) of ordered partitions

P^{(1)} = (B_{1}^{(1)}, B_{2}^{(1)}, ⋯, B_{k_{1}}^{(1)}); P^{(2)} = (B_{1}^{(2)}, B_{2}^{(2)}, ⋯, B_{k_{2}}^{(2)})  (49)

such that IM_{o}(P^{(1)}, P^{(2)}) = M (hence k_{1} = α(D); k_{2} = β(D)) defines labelling M-compatible by

λ(s) = (i, j) ⟺ s ∈ B_{i}^{(1)} ∩ B_{j}^{(2)}  (50)

conversely, to every M-compatible labelling, one can associate the pair of ordered partitions

OP arts(λ) = ((pr_{1} ∘ λ)^{−1}(i))_{1≤i≤k_{1}} , ((pr_{2} ∘ λ)^{−1}(j))_{1≤j≤k_{2}})  (51)

and, by construction, these two correspondences are reciprocal and then one-to-one. Let similarily define

UP arts(λ) = ({(pr_{1} ∘ λ)^{−1}(i)}_{1≤i≤k_{1}} , {(pr_{2} ∘ λ)^{−1}(j)}_{1≤j≤k_{2}})  (52)

(this time not one-to-one). By construction, one has, for Φ_{d}(Dr_{o}(M)) = D,

mult_{o}(D) = ♯{UP arts(λ)}_{λ is M-compatible}  (53)

5.2.2 For unordered bi-partitions

The multiplicity used in the formula (40) is, for a given diagram D, the number of pairs (Q_{1}, Q_{2}) such that IM_{u}(Q_{1}, Q_{2}) = D. One can give a direct formula for the computation of these quantities. First, one can remark that mult(D) can be divided by ((α(D))), in the sense that the set of solutions of DG_{u} ∘ IM_{u}(Q_{1}, Q_{2}) = D can be partitionned into disjoint slices with respect to the first coordinate. Call

Slice_{Q}(D) = {Q_{2}|DG_{u} ∘ IM_{u}(Q, Q_{2}) = D}  (54)

it is not difficult to check that these slices are non void iff type(Q) = α(D), and that, thank to the relabelling, they have the same number of elements. Let now M ∈ N^{k×l} be a packed matrix such that Dg_{u}(class(M)) = D and λ_{1}, λ_{2}, ⋯ λ_{k} the types corresponding to the lines of M (i.e. λ_{j} is the set of non-zero entries, with their multiplicities, rearranged in decreasing order. Set

(((α))) := \frac{||α||!}{∏_{j=1}^{m}(j!)^{α_{j}}} .  (55)

(it is the number of ordered partitions of type α). Now, let C_{j} denote the j-th column of M. The equivalence on [1..l] defined by i ∼ j ⟺ C_{i} = C_{j} is a set partition. Let β = (β_{1}, β_{2}, ⋯ β_{l}) be its type. Then

mult(D) = ((α(D))\frac{(((λ_{1})))(((λ_{2}))) ⋯ (((λ_{k})))}{β_{1}!β_{2}! ⋯ β_{l}!}  (56)

6 The Hopf algebra structures Δ_{W S} and Δ_{BS}

The space spanned by the packed matrices has already received a structure of Hopf algebra, the algebra MQSym [6]. We briefly review the structure of this Hopf algebra.

review NCSFVI paragraph 5 and explain as well how the coproducts are linked with
the addition of alphabets

Here, doubling the variables of 𝕃 or 𝕍 suggests two new coproducts which will be denoted Δ_{W S} (for “white spots”) and Δ_{BS} (for “black spots”). We describe in details Δ_{W S} as the other coproduct is actually got by the same process but applied on the columns instead of the lines. Let M be a packed matrix of dimensions k_{1} × k_{2} for every subset X ∈ [1..k_{1}] we consider the matrix π_{X}(M) := pack(M[X, [1..k_{2}]]), the restriction to the lines of X and then packed (with this restriction to the lines, we only need to perform a horizontal packing). Thus, the coproduct Δ_{W S} reads

Δ_{W S}(M) = ∑_{X+Y =[1..k_{1}]} π_{X}(M) ⊗ π_{Y} (M)  (57)

To avoid confusion we will call the supporting space H_{W S} (= MQSym). We keep the (total) grading of MQSym by the total weight (i.e. the sum of the coefficients) of the matrices. The packed matrices are a linear basis of H_{W S} = MQSym, thus every element expresses uniquely

x = ∑_{M packed} λ_{M}(x)M  (58)

The coproduct above is cocommutative and with counit ϵ := λ_{∅} where ∅ is the void matrix corresponding to the void diagram this particular matrix will be denoted 1_{H_{W S}}. For example, with the packed matrix above one has

Δ_{W S}((\begin{matrix}2 & 0 \\ 0 & 2 \\ 1 & 1 \end{matrix})) = (\begin{matrix}2 & 0 \\ 0 & 2 \\ 1 & 1 \end{matrix}) ⊗ 1_{H_{W S}} + (2) ⊗ (\begin{matrix}0 & 2 \\ 1 & 1 \end{matrix}) + (2) ⊗ (\begin{matrix}2 & 0 \\ 1 & 1 \end{matrix}) + (1 1) ⊗ (\begin{matrix}2 & 0 \\ 0 & 2 \end{matrix}) +

(\begin{matrix}2 & 0 \\ 0 & 2 \end{matrix}) ⊗ (1 1) + (\begin{matrix}2 & 0 \\ 1 & 1 \end{matrix}) ⊗ (2) + (\begin{matrix}0 & 2 \\ 1 & 1 \end{matrix}) ⊗ (2) + 1_{H_{W S}} ⊗ (\begin{matrix}2 & 0 \\ 0 & 2 \\ 1 & 1 \end{matrix})

This coproduct is compatible with the usual coproduct on the monomials for an infinite family of alphabets 𝕍. More precisely set, for all N ≥ 0,

1_{N} := \{\underbrace{1, 1, ⋯ 1}_{N times}, 0, 0, 0, ⋯ \} i.e. V_{n} = 1 for n ≤ N and V_{n} = 0 otherwise.  (59)

Then, using Sweeler’s denotation, for theses 𝕍s, if Δ_{W S}(d) = ∑ d_{(1)} ⊗ d_{(2)}, one has

m(d, 𝕃′ + 𝕃′′, 1_{N}) = ∑ m(d_{(1)}, 𝕃′, 1_{N})m(d_{(2)}, 𝕃′′, 1_{N})  (60)

Thus, it can be shown that, with this structure (product with unit, coproduct and the counit), LDiag_{ℂ} is a graded bialgebra infinite dimensions and then a Hopf algebra. The arrow LDiag_{ℂ} ↦ Diag_{ℂ} endows Diag_{ℂ} with a structure of Hopf algebra.

6.1 Structure results

By a theorem of Cartier, Milnor and Moore [3, 10], it must be the envelopping algebra of its primitive elements (which we will described in a forthcoming paper), LDiag_{ℂ} is a Hopf algebra.

Acknowledgments

We thank ...

References

[1] J. Berstel, C. Reutenauer, Rational series and their languages EATCS Monographs on Theoretical Computer Science, Springer (1988).

[2] Bourbaki N., Algèbre Chapitres I à III, Hermann (1970).

[3] Cartier P., Séminaire “Sopus Lie”, 2ème année, Faculté des Sciences de Paris (1955-56)

[4] Comtet L., Analyse Combinatoire, PUF, Tome 1 (1970)

[5] Comtet L., Analyse Combinatoire, PUF, Tome 2 (1970)

[6] Duchamp G., Hivert F., Thibon J.Y. : Non commutative functions VI: Free quasisymmetric functions and related algebras, International Journal of Algebra and Computation Vol 12, No 5 (2002).

[7] G. Duchamp, A.I. Solomon, K.A. Penson, A. Horzela and P. B lasiak, One-parameter groups and combinatorial physics, Proceedings of the Symposium Third International Workshop on Contemporary Problems in Mathematical Physics (CO-PROMAPH3) (Porto-Novo, Benin, Nov. 2003), in press (World Scientific Publishing)

      arXiv: quant-ph/04011262

[8] Joni S.A., Rota G.-C., Colgebras and Bialgebras in Combinatorics, Studies in Applied Mathematics 61, 93-139 (1979).

[9] Knuth D., The art of computer programming Tome I. Addison-Wesley (1981)

[10] Milnor J., Moore J., On the structure of Hopf Algebras, Ann. of Math. 81 (1965), 211-264.

[11] Treves F., Topological vector spaces, distributions and kernels, Acad. Press (1967).

[12] A. Varvak, Rook numbers and the normal ordering problem, Preprint arXiv: math.

CO/0402376