Séminaire Lotharingien de Combinatoire 62 (2010), Article B62e

COMBINATORIAL DEFORMATIONS OF ALGEBRAS: TWISTING AND PERTURBATIONS

G. H. E. DUCHAMP*, C. TOLLU*, K. A. PENSON^{†} AND G. KOSHEVOY^{‡}

Abstract. The framework used to prove the multiplicative deformation of the algebra of Feynman–Bender diagrams is that of a twisted shifted dual law (in fact, doubly twisted). We give here a clear interpretation of its two parameters. The crossing parameter is a deformation of the tensor structure, whereas the superposition parameter is a perturbation of the shuffle coproduct which, in its turn, can be interpreted as the diagonal restriction of a superproduct. Here, we systematically explain these constructions in detail.

Contents

1. Introduction

2. The deformed algebra LDIAG(q_{c}, q_{s}) 3 2.1. Review of the construction of the algebra 3 2.2. Coding and the recursive definition 5 3. Colour factors and products 6 4. Special classes of laws 8 4.1. Dual laws 8 4.2. Deformed laws 9 4.3. Shifted laws 9 5. Application to the structure of LDIAG(q_{c}, q_{s}) 11 5.1. Associativity of LDIAG(q_{c}, q_{s}) using the previous tools 11 5.2. Structure of LDIAG(q_{c}, q_{s}) 12 6. Conclusion 13 References 13

1. Introduction

In [1], Bender, Brody, and Meister introduced a special field theory, then called “Quantum Field Theory of Partitions”. This theory is based on the bilinear product defined by

H(F, G) = F (z \frac{d}{dx}) G(x)|_{x=0} .  (1.1)

*LIPN - UMR 7030 CNRS - Université Paris 13 F-93430 Villetaneuse, France; †Laboratoire de Physique Théorique de la Matière Condensée Université Pierre et Marie Curie,

CNRS UMR 7600 Tour 24 - 2ième étage, 4 place Jussieu, F 75252 Paris cedex 05; ‡Central Institute of Economics and Mathematics (CEMI) Russian Academy of Sciences.

If one expands this formula in the case when F and G are free exponentials, one obtains a summation over all the (finite) bipartite^{1} graphs with multiple edges and no isolated point [6] (the set of these diagrams will be called diag), a data structure which is equivalent to classes of packed matrices [8] under permutations of rows and columns.

So, one has a Feynman-type expansion of the product formula

H (exp ( ∑_{n=1}^{∞} L_{n} \frac{z^{n}}{n!} ), exp ( ∑_{n=1}^{∞} V_{n} \frac{z^{n}}{n!} )) = ∑_{n≥0} \frac{z^{n}}{n!}_{∑_{d∈diag} ; |d|=n} mult(d)𝕃^{α(d)}𝕍^{β(d)}, (1.2)

where mult(d) is the number of pairs (P_{1}, P_{2}) of (ordered) set partitions of {1, …, n} which correspond to a diagram d, where |d| the number of edges in d, and

𝕃^{α(d)} = L_{1}^{α_{1}}L_{2}^{α_{2}} ⋯; 𝕍^{β(d)} = V_{1}^{β_{1}}V_{2}^{β_{2}} ⋯  (1.3)

is the multiindex notation for the monomials in 𝕃 ∪ 𝕍, i.e., α_{i} = α_{i}(d) (respectively β_{j} = β_{j}(d)) is the number of white (respectively black) spots of degree i (respectively j) in d.

The set diag endowed with the operation of disjoint union inherits the structure of a monoid such that the arrow d ↦ 𝕃^{α(d)}𝕍^{β(d)} is a homomorphism (of monoids), and then, by linear extension, one deduces an algebra homomorphism

ℂ[diag] → Pol(ℂ; 𝕃 ∪ 𝕍) ,  (1.4)

where Pol(ℂ; 𝕃 ∪ 𝕍) is the Hopf algebra of (commutative) polynomials with complex coefficients generated by the alphabet 𝕃 ∪ 𝕍. For at least three models of Physics, one can specialize 𝕃 so that the canonical Hopf algebra structure of Pol(ℂ; 𝕃 ∪ 𝕍) can be lifted, through (1.4). The resulting Hopf algebra (based on ℂ[diag]) has been denoted DIAG. To our great surprise, this Hopf algebra structure could be lifted at the (noncommutative) level of the objects themselves instead of classes, resulting in the construction of a Hopf algebra on (linear combinations of) “labelled diagrams” (the monoid ldiag, see [6]). As these “labelled diagrams” are in one-to-one correspondence with the packed matrices of MQSym, we get two (combinatorially natural) structures of algebra (and coalgebra) on the vector space ℂ[ldiag], and one could raise the question of the existence of a continuous deformation between the two. The answer is positive and can be performed through a three-parameter (two formal, or continuous, and one boolean) Hopf deformation^{2} of LDIAG called LDIAG(q_{c}, q_{s}, q_{t}) [6] such that

LDIAG(0, 0, 0) ≃ LDIAG ; LDIAG(1, 1, 1) ≃ MQSym .  (1.5)

The rôle of the two parameters q_{c}, q_{s} (algebra parameters, whereas q_{t} is a coalgebra parameter) was discovered just counting crossings and superpositions in the twisted labelled diagrams (see [6] for details). This simple statistics (counting crossings and superpositions) yields an associative product on the diagrams. The first proof given for the associativity was mainly computational, and it was actually a surprise that associativity held. This raised the need to understand this phenomenon in a deeper way and the question whether the two parameters (q_{c} and q_{s}) would be of different nature. The aim of this paper is to answer this question and give a conceptual proof of associativity by developing four building blocks which are general and separately easy to test: addition of a group-like element to a coassociative coalgebra, shifting lemma, codiagonal deformation of a semigroup, and extension of a colour factor to words.

1The (bi)-partition of the vertices is understood to be ordered. In this case, the term bicoloured can also be found in the literature.

2This algebra deformation has received recently another realisation in terms of biwords [9].

The essential ingredient in the two last operations is what has become nowadays a useful tool, the coloured product of algebras, for which we give some new results.

Acknowledgements. The authors are pleased to acknowledge the hospitality of institutions in Moscow and New York. Special thanks are due to Catherine Borgen for having created a fertile atmosphere in Exeter (UK) where the first and last parts of this manuscript were prepared. We also acknowledge support from the French Ministry of Science and Higher Education under Grant ANR PhysComb. We are grateful to Jim Stasheff for having raised the question of the different natures of the parameters q_{c} and q_{s}.

2. The deformed algebra LDIAG(q_{c}, q_{s})

2.1. Review of the construction of the algebra. The complete story of the algebra of Feynman–Bender diagrams which arose in Combinatorial Physics in 2005 can be found in [6], and a fragment of it, as well as a realisation using an alternative data structure, in [9].

Recall that (classical) shuffle products (of words) can be expressed in two ways:

a) by a recursion;

b) by a summation on (and by means of) some permutations.

Here, we will trace back the construction of the deformed product between two diagrams, starting from an analog of (b) (using however the symmetric semigroup instead of the symmetric group, see below) and going gradually to (a) following the first description of the deformed case which was graphical (and was discovered as such in [6]).

The diagrams on which the product has to be performed are plane bipartite graphs (vertices being called black and white spots) with multiple ordered edges; they look as follows:

[figure: 1; 2; 3; 4; 1; 2; 3]

Fig 1. — Labelled diagram of format 3 × 4.

One can define more formally this data structure using the equivalent notion of a weight function. Here, it is a function ω : ℕ^{+} × ℕ^{+} → ℕ (as in [9]) with support

supp(ω) = {(i, j) ∈ ℕ^{+} × ℕ^{+} | w(i, j) ≠ 0}  (2.1)

having projections of the form pr_{1}(supp(ω)) = [1 … p]; pr_{2}(supp(ω)) = [1 … q] for some p, q ∈ ℕ^{+}. This last description can be rephrased without pr_{i} by observing that p (respectively q) is the last i such that there exists a j ∈ ℕ^{+} with ω(i, j) ≠ 0 (respectively q is the last j such that there exists an i ∈ ℕ^{+} with ω(i, j) ≠ 0). In this way our graphs are in one-to-one correspondence with such weight functions.

\begin{matrix}j & 2 & 3 & 1 & 2 & 3 & 3 & 4 \\ i & 1 & 1 & 2 & 2 & 2 & 3 & 3 \\ ω(i, j) & 2 & 1 & 1 & 1 & 3 & 1 & 2 \end{matrix}

Fig 2. — The weight function (when not 0) of the diagram in Fig 1. Here p = 3 and q = 4.

We are now in the position to describe the (deformed) product of our diagrams by means of the symmetric semigroup (whereas the symmetric group would only provide crossings as it occurs with the shuffle product). The symmetric semigroup on a finite set F (denoted here SSG_{F}) is the set of endofunctions F → F. In order to preserve the requirement that black spots are labelled from 1 to some integer, we have to require that the mapping acting on the diagram d with n black spots has an image of the type [1 … m] for some m ≤ n. The result, denoted by d.f, has m black spots such that the black spot of (former) label “i” bears the new label f(i).

If we consider any onto mapping [1 … p] → [1 … r], the diagram d.f = d′ has the weight function ω′ defined by

ω′(i, k) = ∑_{f(j)=i} ω(j, k) ,  (2.2)

which can be easily checked to be admissible in our context. Before giving the expression of the deformed product, we must define local partial degrees. For a black spot with label “l”, we denote by bks(d, l) its degree (number of adjacent edges). For d_{1} (respectively d_{2}) with p (respectively q) black spots, let [d_{1}|d_{2}]_{L} be their concatenation (non-deformed product). Then the deformed product of d_{1} by d_{2} reads

[d_{1}|d_{2}]_{L(q_{c},q_{s})} = ∑_{f∈Shs(p,q)} (_{∏_{i<j} ; f(i)>f(j)}q_{c}^{bks(d_{1},i).bks(d_{2},j)})(_{∏_{i<j} ; f(i)=f(j)}q_{s}^{bks(d_{1},i).bks(d_{2},j)})[d_{1}|d_{2}]_{L}.f,

(2.3)

where Shs(p, q) is the set of mappings f ∈ SSG_{[1...p+q]} with image an interval of type [1 … m] (with max{p, q} ≤ m ≤ p + q), and such that

f(1) < f(2) < ⋯ < f(p) ; f(p + 1) < f(p + 2) < ⋯ < f(p + q) .  (2.4)

This condition, similar to that of the shuffle product, guarantees that the black spots of the diagrams are kept in order during the process of shuffling with superposition (hence the name Shs).

2.2. Coding and the recursive definition. The graphical and symmetric-semigroup-indexed description of the deformed product neither gives immediately a recursive definition nor an explanation of “why” the product is associative. We will, on our way to understand this (as well as the different natures of its parameters), proceed in three steps:

• encoding the diagrams by words of monomials,

• presenting the product as a shifted law,

• give a recursive definition of the (non-shifted) law. The code used here relies on monomials over a commutative alphabet of variables 𝕏 = {x_{i}}_{i≥1}. As in [6], we let 𝔐𝔒𝔑(𝕏) denote the monoid of monomials {𝕏^{α}}_{α∈ℕ^{(𝕏)}} (indeed, the free commutative monoid over 𝕏) and 𝔐𝔒𝔑^{+}(X) = {𝕏^{α}}_{α∈ℕ^{(𝕏)}−{0}} the semigroup of its non-unit elements (the free commutative semigroup over 𝕏).

Note that each weight function ω ∈ ℕ^{(ℕ^{+}×ℕ^{+})} yields an equivalent “word of monomials^{3}” W (ω) = w_{1}.w_{2}. · · · .w_{p} such that

W (ω)[i] = w_{i} = ∏_{j=1}^{∞} x_{j}^{ω(i,j)} .  (2.5)

The correspondence code : ℕ^{(ℕ^{+}×ℕ^{+})} → (𝔐𝔒𝔑^{+}(X))^{∗} is one-to-one and provides at once a way to code each labelled diagram through its weight function as a word of monomials. Conversely, a word W ∈ (𝔐𝔒𝔑^{+}(X))^{∗} is the code of a diagram (i.e., the image by code of the weight function of a diagram) if and only if

indexes(Alph(W)) = [1 … m]  (2.6)

(where indexes(Alph(W)) is the set of i ∈ ℕ^{+} such that an x_{i} is involved in W). Due to the special indexation of its alphabet, the monoid (𝔐𝔒𝔑^{+}(X))^{∗} comes equipped with a set of endomorphisms, the translations T_{n} defined on the variables by T_{n}(x_{i}) = x_{i+n} and extended to 𝔐𝔒𝔑^{+}(X), to (𝔐𝔒𝔑^{+}(X))^{∗} and then to K⟨𝔐𝔒𝔑^{+}(X)⟩.

Note that the code of a concatenation reads

code([d_{1}|d_{2}]_{L}) = code(d_{1}).T_{max(indexes(Alph(code(d_{1}))))}(code(d_{2})) .  (2.7)

Therefore, the function “code” being below extended by linearity, the reader may check easily that one can compute recursively the deformed product on the codes by

code([d_{1}|d_{2}]_{L}) = code(d_{1}) ↑ T_{max(indexes(Alph(code(d_{1}))))}(code(d_{2})),  (2.8)

where the bilinear product ↑ is recursively defined on the words by

\{ \begin{matrix}1_{(𝔐𝔒𝔑^{+}(X))^{∗}} ↑ w & = & w ↑ 1_{(𝔐𝔒𝔑^{+}(X))^{∗}} = w \\ au ↑ bv & = & a(u ↑ bv) + q_{c}^{|au||b|}b(au ↑ v) + q_{c}^{|u||b|}q_{s}^{|a||b|}(a · b)(u ↑ v) \end{matrix} , (2.9)

where a · b (medium · dot) denotes the (monomial, commutative) product of a and b within 𝔐𝔒𝔑^{+}(X).

It is this last recursion that we will decompose and analyse below in order to get a better understanding of the parameters.

The associativity of the product (2.9) is a consequence of the following proposition.

3The low point . here is used to emphasize concatenation which is elsewhere denoted by simple juxtaposition of letters.

Proposition 2.1 ([6, Prop. 5.1]). Let (S, .) be a semigroup graded by a degree function | |_{d} : S → ℕ (i.e., a homomorphism to (ℕ, +)) and S^{∗} the set of lists (denoted by words a_{1}a_{2} ⋯ a_{k}) with letters in S (including the empty list 1_{S^{∗}}).

Let q_{c}, q_{s} ∈ K be two elements in a (commutative) ring K. We define on K⟨S⟩ = K[S^{∗}] a new product ↑ by

w ↑ 1_{S^{∗}} = 1_{S^{∗}} ↑ w = w
au ↑ bv = a(u ↑ bv) + q_{c}^{|au|_{d}|b|_{d}}b(au ↑ v) + q_{c}^{|u|_{d}|b|_{d}}q_{s}^{|a|_{d}|b|_{d}}(a.b)(u ↑ v), (2.10)

where the weights are extended additively to lists (words) by

|a_{1}a_{2} ⋯ a_{k}|_{d} = ∑_{i=1}^{k} |a_{i}|_{d} .

Then the new product ↑ is graded, associative, with 1_{S^{∗}} as its unit.

The questions that have arisen in the introduction can now be reformulated as follows: Q1) Are q_{c} and q_{s} of the same nature? Q2) If no, can the associativity be explained, step by step, by constructions which

will show their different natures? Here, by “nature,” it is understood that q_{c} and q_{s}, although at the level of statistics

they seem to play a similar rôle, could be distinguished by general algebra. Indeed, in the sequel, we attempt to show that q_{c} is of geometric nature (deformation at the level of the tensor structure), whereas q_{s} is of perturbative nature (perturbation of the Lie coproduct).

With this aim in mind, we need to recall a now classical tool, the coloured product of two algebras.

3. Colour factors and products

Colour factors were introduced by R. Ree [14], and the theory was developed or used in [7, 5, 12, 16]. See also [2]^{4}.

Let A = ⨁_{α∈D}A_{α} and B = ⨁_{β∈D} B_{β} be two D-graded associative K-algebras^{5} (D is a

commutative semigroup whose law is denoted additively). Readers that are not familiar with graded algebras can think of D = ℕ^{(X)}, the free commutative monoid over X, and A_{α} = K[X]_{α}, the space of homogeneous polynomials of multidegree α.

Given a mapping χ : D × D ⟶ K, we define an algebra product on A ⊗ B by

(x_{1} ⊗ y_{1})(x_{2} ⊗ y_{2}) = χ(β_{1}, α_{2})(x_{1}x_{2} ⊗ y_{1}y_{2})  (3.1)

for (x_{i}) ∈ A_{α_{i}} and (y_{i}) ∈ B_{β_{i}} (i = 1, 2).

Equating the expressions that we obtain for ((x_{1} ⊗ y_{1})(x_{2} ⊗ y_{2})) (x_{3} ⊗ y_{3}) and (x_{1} ⊗ y_{1}) ((x_{2} ⊗ y_{2})(x_{3} ⊗ y_{3})) by using (3.1), we are led to the following proposition.

Proposition 3.1 ([16]). Let χ : D × D ⟶ K. The following are equivalent: i) For A, B D-graded associative algebras, the product defined by (3.1) is associa-

4In fact, some of them (“Facteurs de commutation”, with values in {−1, 1} and an [anti]symmetry condition) are already considered in the edition of 1970 of [2]. See Section 10 (Dérivations) of Chapter III.

5Not necessarily with unit.

tive. ii) For all α_{1}, α_{2}, α_{3}, β_{1}, β_{2}, β_{3}) ∈ D we have

χ(β_{1}, α_{2})χ(β_{1} + β_{2}, α_{3}) = χ(β_{2}, α_{3})χ(β_{1}, α_{2} + α_{3}).  (3.2)

Definition 3.2. Every mapping χ : D×D ⟶ K which fulfills the equivalent conditions of Proposition 3.1 will be called a colour (twisting) factor.

Remarks 3.3. I) If χ is bilinear, which means in this context that the following equations are satisfied (for all α, α′, β, β′ ∈ D):

χ(α + α′, β) = χ(α, β)χ(α′, β)
χ(α, β + β′) = χ(α, β)χ(α, β′),  (3.3)

then the two sides of (3.2) amount to

χ(β_{1}, α_{2})χ(β_{1}, α_{3})χ(β_{2}, α_{3}) = ∏_{1≤i<j≤3} χ(β_{i}, α_{j}),  (3.4)

and hence χ is a colour factor^{6}. But the full class of colour factors is much larger than solutions of Eq. (3.3). Just observe that Eq. (3.2) is homogeneous in the classical sense, i.e., for all λ ∈ K, if χ fulfills (3.2), then after rescaling by λ it still does. Hence, for example, any constant function on D × D is a colour factor. This shows the existence of colour factors that are not bilinear.

II) The converse part of Proposition 3.1 (i.e., ii) ⟹ i)) can be easily proved by considering (free) semigroup algebras K[D].

Notes 3.4. I) The colour product of two algebras A = ⨁_{α∈D}A_{α} and B = ⨁_{β∈D} B_{β} comes

also as a graded algebra by

(A ⊗ B)_{γ} = ⨁_{α+β=γ} A_{α} ⊗ B_{β}.  (3.5)

The usual identification

(A ⊗ B) ⊗ C ≃ A ⊗ (B ⊗ C)  (3.6)

holds for coloured products.

II) Moreover, if A →^{f} A′ (respectively B →^{g} B′) are two homomorphisms of (graded) algebras (over the same semigroup of degrees D), then A ⊗ B ⟶^{f⊗g} A′ ⊗ B′ is an algebra homomorphism (the colour products being taken with respect to the same colour factor).

6These bilinear mappings are also called bicharacters in the literature [14].

4. Special classes of laws

4.1. Dual laws.

4.1.1. Algebras and coalgebras in duality. An algebra (A, μ) and a coalgebra (C, Δ) are said to be in duality if and only if there is a non-degenerate pairing ⟨−|−⟩ such that for all x, y ∈ A, z ∈ C

⟨μ(x, y)|z⟩ = ⟨x ⊗ y|Δ(z)⟩^{⊗2}.  (4.1)

In the following, a product K⟨A⟩ ⊗ K⟨A⟩ ⟶^{∗} K⟨A⟩ on the free algebra which is the dual of a comultiplication will be called dual law, the pairing being given on the basis of words by ⟨u|v⟩ = δ_{u,v}. Our first examples are essential in modern and not-so-modern research (cf. [13, 15]). First of all, we have the dual of the Cauchy product

Δ_{Cauchy}(w) = ∑_{uv=w} u ⊗ v .  (4.2)

In contrast to (4.2), which is not an algebra homomorphism^{7}

K⟨A⟩ ⟶ K⟨A⟩ ⊗ K⟨A⟩ ,  (4.3)

one has three very well-known examples being so, namely duals of the shuffle , the Hadamard ⊙ and the infiltration product ↑. As they are homomorphisms between the algebras (4.3), they are well defined by their values on the letters; namely, we have

Δ (x) = x ⊗ 1 + 1 ⊗ x ; Δ_{⊙}(x) = x ⊗ x ; Δ_{↑}(x) = x ⊗ 1 + 1 ⊗ x + x ⊗ x , (4.4)

respectively. One can prove that the deformations Δ_{q} = Δ (x) + qΔ_{⊙}(x) are also coassociative, and that they are the unique solutions of the problem of bialgebra comultiplications on K⟨A⟩ that are compatible with subalphabets [10]. In the sequel, we will make use of the following lemma several times, the proof of which is left to the reader.

Lemma 4.1. Let A be an algebra and C be a coalgebra in (non-degenerate) duality. Then A is associative if and only if C is coassociative.

4.1.2. Duality between group-like elements and units. Let (C, Δ) be a coalgebra with counit ϵ : C → K. We call an element u group-like if it satisfies

ϵ(u) = 1 ; Δ(u) = u ⊗ u .  (4.5)

One then has C = ker(ϵ) ⊕ K.u and

Δ(y) = Δ^{+}(y) + y ⊗ u + u ⊗ y − ϵ(y)u ⊗ u ,  (4.6)

where Δ^{+} is a comultiplication on C for which ker(ϵ) = C^{+} is a subcoalgebra (i.e., Δ^{+}(C^{+}) ⊂ C^{+} ⊗ C^{+}; cf. [3]).

Proposition 4.2. Let (C, Δ, ϵ) be a coalgebra with counit, u a group-like element in C, and (C^{+}, Δ^{+}) be as in (4.6). On the other hand, let A be an algebra and A^{(1)} = A⊕K.v be the algebra with unit constructed from A by adjunction of the unit v. Then, if C^{+} and A are in duality by ⟨ | ⟩, so are C and A^{(1)} by ⟨ | ⟩_{•}, the latter being defined by

⟨x + αv|y + βu⟩_{•} = ⟨x|y⟩ + βα  (4.7)

7Unless A = ∅.

for x ∈ A and y ∈ C^{+} = ker(ϵ).

Proof. Let

⟨(x_{1} + α_{1}v) ⊗ (x_{2} + α_{2}v)|Δ(y + βu)⟩_{•}^{⊗2}

= ⟨(x_{1} + α_{1}v) ⊗ (x_{2} + α_{2}v)|Δ^{+}(y) + y ⊗ u + u ⊗ y + βu ⊗ u)⟩_{•}^{⊗2}. (4.8)

However, according to the fact that

⟨x_{i}|u⟩ = ⟨x_{1} ⊗ v|Δ^{+}(y)⟩ = ⟨v ⊗ x_{2}|Δ^{+}(y)⟩ = ⟨v ⊗ v|Δ^{+}(y)⟩ = ⟨v|y⟩ = 0,

one concludes from (4.8) that

⟨(x_{1} + α_{1}v) ⊗ (x_{2} + α_{2}v)|Δ(y + βu)⟩_{•}^{⊗2}
= ⟨x_{1} ⊗ x_{2}|Δ^{+}(y)⟩^{⊗2} + α_{2}⟨x_{1}|y⟩ + α_{1}⟨x_{2}|y⟩ + α_{1}α_{2}β

= ⟨x_{1}x_{2} + α_{2}x_{1} + α_{1}x_{2} + α_{1}α_{2}v|y + βu⟩_{•} = ⟨(x_{1} + α_{1}v)(x_{2} + α_{2}v)|y + βu⟩_{•},

which proves the claim. □

4.2. Deformed laws. Let S be a semigroup graded by a semigroup of degrees D and A = K[S] its algebra. A colour factor χ : D × D → K being given, we endow the algebra A ⊗ A with the coloured tensor product structure. Notice that the diagonal subspace D_{S} = ⨁_{x∈S} Kx ⊗ x is a subalgebra since

(x ⊗ x)(y ⊗ y) = χ(x, y) xy ⊗ xy .  (4.9)

Transferring (4.9) back to A by means of the isomorphism of vector spaces, A → D_{S}, one sees immediately that the deformed product on A given by

x._{χ}y = χ(x, y) xy  (4.10)

(for x, y ∈ D) is associative.

From now on, we suppose that the semigroup D satisfies condition [D] of Bourbaki [2], which means that, for all z ∈ D, the number of solutions (x, y) ∈ D^{2} of the equation xy = z is finite. This condition is satisfied by almost all the graded semigroups used by combinatorialists, in particular by the semigroups (ℕ, +), (ℕ^{+}, ×), (ℕ^{(X)}, +).

If A is endowed with the scalar product for which the basis (s)_{s∈S} is orthonormal, the pairing is non-degenerate and the dual comultiplication is given by

Δ(z) = ∑_{xy=z} χ(x, y) x ⊗ y .  (4.11)

The construction together with Lemma 4.1 proves that this comultiplication on A is coassociative.

4.3. Shifted laws. We begin by a very general version of the “shifting lemma” (more general than the one given and needed in [6]).

We start from an algebra A decomposed (as a vector space) into the direct sum

A = ⨁_{α∈D} A_{α}

over D, a semigroup. We denote by End^{α}(A) the algebra homomorphisms A → A (then multiplicative) which “shift by α” (i.e., ϕ ∈ End^{α}(A) if and only if, for all β ∈ D, one has ϕ(A_{β}) ⊂ A_{α+β}). This situation is typical of “shift of indices” in free algebras.

For example, let Y = {y_{j}}_{j≥1} = {y_{1}, y_{2}, …, y_{k}, … } be an infinite alphabet, D be its indexing semigroup (ℕ^{+}, +) and A be the algebra K⟨Y ⟩. For every monomial (word) w let d(w) be the maximal index j of a letter y_{j} occurring in w. With K⟨Y ⟩_{j} := ⨁_{d(w)=j} K.w, one gets a direct sum decomposition

K⟨Y ⟩ = ⨁_{j≥1} K⟨Y ⟩_{j} ,  (4.12)

for which K⟨Y ⟩ is not a graded algebra (it is, in fact for the sup law in ℕ^{+}, but we aim here at constructing a graded algebra for the addition of degrees). The change of variables T_{n}(y_{j}) := y_{j+n} defines an algebra homomorphism T_{n} ∈ End^{n}(A). The algebra product is the usual concatenation, whereas the shifted law reads

w_{1} \overline{conc} w_{2} := w_{1}T_{n}(w_{2}),

where n = max{j ≥ 1||w_{1}|_{y_{j}} ≠ 0}.

One can easily check that the following spaces are subalgebras of (K⟨Y ⟩, \overline{conc}):

(1) the space generated by packed words (i.e., the words whose alphabet indices are of the form [1 … q]);

(2) the space generated by injective words (each letter occurs at most once);

(3) the space generated by permutation words (packed and injective, see [7]);

(4) the space generated by increasing (respectively strictly increasing) words; i.e., w = y_{j_{1}}y_{j_{2}} ⋯ y_{j_{k}} such that the function r → j_{r} is increasing (respectively strictly increasing);

(5) the space generated by disconnected words (i.e., w = y_{j_{1}}y_{j_{2}} ⋯ y_{j_{k}} such that there exists an index r < k with y_{j_{r}+1} not occurring in w).

The following lemma gives general conditions for such shifted laws to be associative.

Lemma 4.3. Let A be an algebra (whose multiplicative law will be denoted by ⋆) and A = ⨁_{α∈D} A_{α} a decomposition of A as a direct sum over D, a semigroup (A is then graded, but only as a vector space). Let α ↦ T_{α}: D → End^{gr}(A) be a semigroup homomorphism such that T_{α} ∈ End^{α}(A). Explicitly, for all α, β ∈ D, x ∈ A_{β}, we have

T_{α}(x) ∈ A_{α+β} and T_{α} ∘ T_{β} = T_{α+β} .  (4.13)

We suppose that the shifted law defined for x ∈ A_{α} and y ∈ A by

x ¯⋆ y = x ⋆ T_{α}(y)  (4.14)

is graded for the decomposition

A = ⨁_{α∈D} A_{α}

(i.e., if x ∈ A_{α} and y ∈ A_{β} then x ¯⋆ y ∈ A_{α+β}). Then, if the law ⋆ is associative, so is the law ¯⋆.

Proof. One only needs to prove the identity of associativity of ¯⋆ for homogeneous elements. Suppose that ⋆ is associative. Then, for x ∈ A_{α}, y ∈ A_{β}, and z ∈ A, one has

x¯⋆(y¯⋆z) = x ⋆ T_{α}(y¯⋆z) = x ⋆ T_{α}(y ⋆ T_{β}(z))) = x ⋆ (T_{α}(y) ⋆ T_{α}(T_{β}(z)))

= x ⋆ (T_{α}(y) ⋆ T_{α+β}(z)) = (x ⋆ T_{α}(y)) ⋆ T_{α+β}(z) = \underbrace{(x ¯⋆ y)}_{∈A_{α+β}} ⋆ T_{α+β}(z) = (x¯⋆y)¯⋆z.

□

5. Application to the structure of LDIAG(q_{c}, q_{s})

5.1. Associativity of LDIAG(q_{c}, q_{s}) using the previous tools. As was stated in Section 2.2, we just have to prove Proposition 2.1, and we keep the notations of it. We first observe, from Section 4.2, that, for a semigroup S of type (D)^{8}, graded by a degree function | |_{d} : S → ℕ, the comultiplication Δ_{1} : K[S] → K[S] ⊗ K[S] given for s ∈ S by

Δ_{1}(s) = ∑_{rt=s} q_{s}^{|r|_{d}|t|_{d}}r ⊗ t  (5.1)

is coassociative.

Now we endow K⟨S⟩ ⊗ K⟨S⟩ with the structure of coloured product given by the bicharacter on S^{∗}

χ(u, v) = _{∏_{1≤i≤|u|} ; 1≤j≤|v|}q_{c}^{|u[i]|_{d}|v[j]|_{d}}.  (5.2)

One defines a mapping Δ : S → K⟨S⟩ ⊗ K⟨S⟩ by

Δ(s) = s ⊗ 1_{S^{∗}} + 1_{S^{∗}} ⊗ s + Δ_{1}(s),  (5.3)

which is extended to an algebra homomorphism Δ : K⟨S⟩ → K⟨S⟩ ⊗ K⟨S⟩. Note that V = ⨁_{x∈S∪{1_{S^{∗}}}} K.x = KS ⊕ K.1_{S^{∗}} is a subcoalgebra for Δ, and the coalgebra V is, by Section 4.1.2, still coassociative. Now one has to prove that the following rectangle is commutative:

\xymatrix{K⟨S⟩ \ar[r]^{Δ} \ar[d]_{Δ} & K⟨S⟩ ⊗ K⟨S⟩ \ar[d]^{Id⊗Δ} \\ K⟨S⟩ ⊗ K⟨S⟩ \ar[r]^{Δ⊗Id} & K⟨S⟩ ⊗ K⟨S⟩ ⊗ K⟨S⟩} .  (5.4)

By Note (3.4).II), all the arrows are algebra homomorphisms, and, in particular, the composites (Id ⊗ Δ) ∘ Δ and (Δ ⊗ Id) ∘ Δ, which, as we just proved, coincide on S (coassociativity of the subcoalgebra V). This shows that the rectangle (5.4) is commutative.

End of the duality. We denote by ↓ the law which is dual to Δ. This law, being dual to a coassociative comultiplication, is associative. We prove that it satisfies the same recursion as in Proposition 2.1, so ↓=↑. It is sufficient to prove the recursion for non-empty factors. One has

8After [2], a semigroup S of type (D) is such that the product mapping S × S → S has finite fibers.

au ↓ bv = ∑_{w∈S^{+}}⟨au ↓ bv|w⟩w

= _{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ↓ bv|xw_{1}⟩xw_{1}

= _{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ⊗ bv|Δ(x)Δ(w_{1})⟩xw_{1}

= _{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ⊗ bv|(x ⊗ 1 + 1 ⊗ x + ∑_{yz=x} χ(y, z)y ⊗ z)Δ(w_{1})⟩xw_{1}

= _{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ⊗ bv|(x ⊗ 1)Δ(w_{1})⟩xw_{1} +_{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ⊗ bv|(1 ⊗ x)Δ(w_{1})⟩xw_{1}

+_{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ⊗ bv|(∑_{yz=x} χ(y, z)y ⊗ z)Δ(w_{1})⟩xw_{1}

= _{∑_{x=a} ; w_{1}∈S^{∗}}⟨au ⊗ bv|(x ⊗ 1)Δ(w_{1})⟩xw_{1} +_{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ⊗ bv|(1 ⊗ x) ∑_{i,j} β_{ij}w_{i} ⊗ w_{j}⟩xw_{1}

+_{∑_{x∈S} ; w_{1}∈S^{∗}}⟨au ⊗ bv|(∑_{yz=x} χ(y, z)y ⊗ z) ∑_{i,j} β_{ij}w_{i} ⊗ w_{j}⟩xw_{1}

= a(u ↓ bv) + q_{c}^{|au|_{d}|b|_{d}}b(au ↓ v) + q_{c}^{|u|_{d}|b|_{d}}q_{s}^{|a|_{d}|b|_{d}}(a.b)(u ↓ v) ,

which proves the claim.

5.2. Structure of LDIAG(q_{c}, q_{s}). This section is devoted to the thorough study of the structure of LDIAG(q_{c}, q_{s}), using that of the algebra of (𝔐𝔒𝔑^{+}(X))^{∗} endowed with the shifted law ¯↑.

We first investigate the structure of the monoid ((𝔐𝔒𝔑^{+}(X))^{∗}, ¯⋆), extending to some extent Proposition 3.1 of [6]. For a general monoid, (M, ⋆, 1_{M}), the irreducible elements are the elements x ≠ 1_{M} such that x = y ⋆ z implies 1_{M} ∈ {y, z}. The set of these elements will be denoted by irr(M). For convenience, in the following statement, M stands for the monoid ((𝔐𝔒𝔑^{+}(X))^{∗}, ¯⋆), M^{+} = M − {1_{M}}, and M_{c} is the submonoid of codes of diagrams (i.e., words which satisfy Eq. (2.6)).

The monoid M is free. An element w = m_{1}.m_{2}. · · · .m_{l} ∈ M^{+} (hence l = |w| > 0) is reducible if and only if there exists 0 < k < l such that

(indices(Alph(m_{1}.m_{2}. · · · .m_{k}))) ≺ (indices(Alph(m_{k+1}.m_{k+2}. · · · .m_{l}))), (5.5)

where, for two nonempty subsets X, Y ⊂ ℕ^{+}, one writes ≺ for the relation of majoration, i.e.,

(∀(x, y) ∈ X × Y)(x < y) .  (5.6)

One checks readily that the monoid M_{c} is generated by the subalphabet irr(M) ∩ M_{c}, and therefore it is free.

Now we need a classical tool of general algebra (see [4, Ch. III] for details). Let (A, μ) be an algebra endowed with an increasing exhaustive filtration (A_{n})_{n∈ℕ} (i.e., two-sided ideals such that A_{n} ⊂ A_{n+1} and ⋃_{n∈ℕ} A_{n} = A). It is classical to construct the associated graded algebra Gr(A) = ⨁_{n≥0} A_{n}/A_{n−1} by passing the law to quotients, i.e., μ̄_{p,q} : A_{p}/A_{p−1}⊗A_{q}/A_{q−1} → A_{p+q}/A_{p+q−1} (one sets A_{−1} = {0}). A classical lemma (and easy exercise) states that, if the associated graded algebra is free, so is A.

Now, returning to (K⟨𝔐𝔒𝔑^{+}(X)⟩, ¯↑) (¯↑ is the shifted deformed law), one constructs a filtration by the number of irreducible components of a word of monomials (call it l(w) for w ∈ 𝔐𝔒𝔑^{+}(X)). From (2.10), one gets

w_{1}¯↑w_{2} = w_{1}¯⋆w_{2} + ∑_{l(w)<l(w_{1})+l(w_{2})} P_{w}(q_{c}, q_{s})w,  (5.7)

with P_{w} ∈ K[q_{c}, q_{s}] (indeed, ¯↑ is the same law as in (2.10) but shifted). Consequently, the associated graded algebra is, by a triangularity argument, free. One can then state the following structure theorem.

Theorem 5.1. The algebra K⟨𝔐𝔒𝔑^{+}(X)⟩, endowed with the shifted deformed law ¯↑, is free on the irreducible words. Furthermore, the algebra LDIAG(q_{c}, q_{s}), isomorphic to a subalgebra generated by irreducible words, is free for every choice of (q_{c}, q_{s}).

6. Conclusion

To summarize, we can state that the deformed algebra LDIAG(q_{c}, q_{s}), which originates from a special quantum field theory [1], is free, and its law can be constructed from very general procedures: it is a shifted twisted law. Before shifting, one can observe that the law is, in fact, dual to a comultiplication on a free algebra. This comultiplication is a perturbation, with q_{s} (the superposition parameter) of the shuffle comultiplication on this free algebra. The parameter q_{s} is obtained by addition of a perturbating factor which is just dual to a (diagonally) deformed law of a semigroup, whereas the crossing parameter q_{c} is obtained by extending a colour factor of an algebra to the tensor structure (i.e., to words).

References

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

[2] N. Bourbaki, Algebra, Chapters 1–3, Springer, 2002.

[3] N. Bourbaki, Lie Groups and Lie Algebras, Chapters 1–3, Springer, 2004.

[4] N. Bourbaki, Algèbre Commutative, chapitres 1–4, Springer, 2006.

[5] J. Désarménien, G. H. E. Duchamp, D. Krob, and G. Melançon, Quelques remarques sur les superalgèbres de Lie libres, Comptes Rendus Acad. Sci. Paris Sér. I 318 (1994), 419– 424.

[6] G. H. E. Duchamp, K. A. Penson, P. Blasiak, A. Horzela, and A. I. Solomon, A three parameter Hopf deformation of the algebra of Feynman-like diagrams, J. Russian Laser Research 31 (2010), 162–181; arχiv:0704.2522.

[7] G. H. E. Duchamp, A. Klyachko, D. Krob, and J.-Y. Thibon, Noncommutative symmetric functions III: Deformations of Cauchy and convolution algebras, Discrete Mathematics Theoret. Computer Science 1 (1997), 159–216.

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

[9] G. H. E. Duchamp, J.-G. Luque, J.-C. Novelli, C. Tollu, and F. Toumazet, Hopf algebras of diagrams, Proceedings of the 19th Conference on “Formal Power Series and Algebraic Combinatorics”, Tianjin, China, 2007.

[10] G. H. E. Duchamp, M. Flouret, É. Laugerotte, and J.-G. Luque, Direct and dual laws for automata with multiplicities, Theoret. Computer Science 267 (2001), 105–120.

[11] M. Lothaire, Combinatorics on Words, corrected reprint of the 1983 original, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997.

[12] A. A. Mikhalev and A. A. Zolotykh, Combinatorial Aspects of Lie Superalgebras, CRC Press, Boca Raton, New York, 1995.

[13] P. Ochsenschläger, Binomialkoeffizienten und Shuffle-Zahlen, Technischer Bericht, Fachbereich Informatik, T. H. Darmstadt, 1981.

[14] R. Ree, Generalized Lie elements, Canad. J. Math. 12 (1960), 493–502.

[15] M. Rosso, Groupes quantiques et algèbres de battage quantiques, Comptes Rendus Acad. Sci. Paris Sér. I 320 (1995), 145–148.

[16] J. Zhou, Combinatoire des dérivations, thèse de doctorat, Université de Marne-la-Vallée, 1996.