G H E Duchamp

P Blasiak
email: pawel.blasiak@ifj.edu.pl

A Horzela

K A Penson
email: penson@lptl.jussieu.fr

A I Solomon
email: a.i.solomon@open.ac.uk

Hopf Algebras in General and in Combinatorial Physics: a practical introduction

This tutorial is intended to give an accessible introduction to Hopf algebras. The mathematical context is that of representation theory, and we also illustrate the structures with examples taken from combinatorics and quantum physics, showing that in this latter case the axioms of Hopf algebra arise naturally. The text contains many exercises, some taken from physics, aimed at expanding and exemplifying the concepts introduced.

Introduction

Quantum Theory seen in action is an interplay of mathematical ideas and physical concepts. From a modern perspective its formalism and structure are founded on the theory of Hilbert spaces [START_REF] Isham | Lectures on Quantum Theory: Mathematical and Structural Foundations[END_REF][START_REF] Peres | Quantum Theory: Concepts and Methods[END_REF]. Using a few basic postulates, the physical notions of a system and apparatus, as well as transformations and measurements, are described in terms of linear operators. In this way the algebra of operators constitutes a proper mathematical framework within which quantum theories may be constructed. The structure of this algebra is determined by two operations, namely -addition and multiplication of operators; and these lie at the root of all fundamental aspects of Quantum Theory.

The formalism of quantum theory represents the physical concepts of states, observables and their transformations as objects in some Hilbert space H and subsequently provides a scheme for measurement predictions. Briefly, vectors in the Hilbert space describe states of a system, and linear forms in V * represent basic observables. Both concepts combine in the measurement process which provides a probabilistic distribution of results and is given by the Born rule. Physical information about the system is gained by transforming the system and/or apparatus in various ways and performing measurements. Sets of transformations usually possess some structure -such as that of a group, semi-group, Lie algebra, etc. -and in general can be handled within the concept of an algebra A. The action of the algebra on the vector space of states V and observables V * is simply its representation. Hence if an algebra is to describe physical transformations it has to have representations in all physically relevant systems. This requirement directly leads to the Hopf algebra structures in physics. From the mathematical viewpoint the structure of the theory, modulo details, seems to be clear. Physicists, however, need to have some additional properties and constructions to move freely in this arena. Here we will show how the structure of Hopf algebras enters into the game in the context of representations. The first issue at point is the construction of tensor product of vector spaces which is needed for the description of composite systems. Suppose, we know how some transformations act on individual systems, i.e. we know representations of the algebra in each vector space V 1 and V 2 , respectively. Hence natural need arises for a canonical construction of an induced representation of this algebra in V 1 ⊗V 2 which would describe its action on the composite system. Such a scheme exists and is provided by the co-product in the algebra, i.e. a morphism ∆ : A -→ A ⊗ A. The physical plausibility of this construction requires the equivalence of representations built on (V 1 ⊗ V 2 ) ⊗ V 3 and V 1 ⊗ (V 2 ⊗ V 3 ) -since the composition of three systems can not depend on the order in which it is done. This requirement forces the co-product to be co-associative. Another point is connected with the fact that from the physical point of view the vector space C represents a trivial system having only one property -"being itself" -which can not change. Hence one should have a canonical representation of the algebra on a trivial system, denoted by ǫ : A -→ C. Next, since the composition of any system with a trivial one can not introduce new representations, those on V and V ⊗ C should be equivalent. This requirement imposes the condition on ǫ to be a co-unit in the algebra. In this way we motivate the need for a bi-algebra structure in physics. The concept of an antipode enters in the context of measurement. Measurement in a system is described in in terms of V * × V and measurement predictions are given through the canonical pairing c : V * × V -→ C. Observables, described in the dual space V * , can also be transformed and representations of appropriate algebras are given with the help of an anti-morphism α : A -→ A. Physics requires that transformation preformed on the system and apparatus simultaneously should not change the measurement results, hence the pairing should trivially transform under the action of the bi-algebra. We thus obtain the condition on α to be an antipode, which is the last ingredient of a Hopf Algebra.

Many Hopf algebras are motivated by various theories (physical or close to physics) such as renormalization [START_REF] Brouder | Renormalization of QED with planar binary trees[END_REF][START_REF] Broadhurst | Towards cohomology of renormalization: bigrading the combinatorial Hopf algebra of rooted trees[END_REF][START_REF] Brouder | Trees, renormalization and differential equations[END_REF][START_REF] Connes | Hopf algebras, Renormalization and Noncommutative geometry[END_REF][START_REF] Kreimer | On the Hopf algebra structure of pertubative quantum field theories[END_REF], non-commutative geometry [START_REF] Connes | Hopf algebras, Renormalization and Noncommutative geometry[END_REF][START_REF] Connes | Hopf algebras, cyclic cohomology and the transverse index theorem[END_REF], physical chemistry [START_REF] Patras | Symmetry-Adapted Polynomial Basis for Global Potential Energy Surfaces -Applications to XY4 Molecules[END_REF][START_REF] Brouder | Quantum field theory and Hopf algebra cohomology[END_REF], computer science [START_REF] Duchamp | Sweedler's duals and Schützenberger's calculus[END_REF], algebraic combinatorics [START_REF] Brouder | Trees, renormalization and differential equations[END_REF][START_REF] Hoffman | Combinatorics of rooted trees and Hopf algebras[END_REF][START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF][START_REF] Chapoton | An operational calculus for the Mould operad[END_REF], algebra [START_REF] Foissy | Finite-dimensional comodules over the Hopf algebra of rooted trees[END_REF][START_REF] Foissy | Les algèbres de Hopf des arbres enracinés I[END_REF][START_REF] Foissy | Les algèbres de Hopf des arbres enracinś II[END_REF].

Operators

Generalities

Throughout this text we will consider (linear) operators ω : V -→ V , where V is a vector space over k (k is a field of scalars which can be thought of as R or C). The set of all (linear) operators V -→ V is an algebra (see appendix) which will be denoted by End K (V ).

What is a representation

It is not rare in Physics that we consider, instead of a single operator, a set or a family of operators (ω α ) α∈A and often the index set itself has a structure. In the old books one finds the family-like notation, where ρ(α) is denoted, say, ω α . As a family of operators (ω α ) α∈A is no more than a mapping ρ : A → End k (V ) (see [START_REF] Bourbaki | Theory of sets[END_REF], Ch. II 3.4 remark), we wprefer to exhibit the mapping by considering it defined as such. This will be precisely the concept of representation that we will illustrate by familiar examples. Moreover using arrows allows, as we will see more clearly below, for extension and factorization procedures.

• First case: A is a group In this case, we postulate that the action of the operators be compatible with the laws of a group; that is, for all α, β ∈ A,

ρ(α.β) = ρ(α) • ρ(β) ρ(α -1 ) = (ρ(α)) -1 (1)
which is equivalent to

ρ(α.β) = ρ(α) • ρ(β) ρ(1 A ) = 1 End(V ) (2)
Note that each of these conditions implies that the range of ρ is in Aut k (V ) (= GL n (k), the linear group), the set of one-to-one elements of End k (V ) (called automorphisms).

• Second case: A is a Lie algebra

In this case, one requires that

ρ([α, β]) = ρ(α) • ρ(β) -ρ(β) • ρ(α) = [ρ(α), ρ(β)]. (3)
We will see that these two types of action (of a group or Lie algebra) can be unified through the concept of the representation of an algebra (or which amounts to the same thing, of a module).

In the first case, one invokes the group algebra k[A] (see appendix). In the case of a Lie algebra, one invokes the enveloping algebra U(A) (or U k (A) see appendix). In both cases, the original representation ρ is extended to a representation of an associative algebra with unit (AAU) as follows: Definition 2.1 Let (A, +, •) be an AAU. A collection of operators {ρ(α)} α∈A in a vector space V is said to be a representation of A iff the mapping ρ : A → End(V ) is compatible with the operations and units of A. This means that, identically (i. e. for all α, β ∈ A and λ ∈ K).

G ρ / / can End k (V ) k[G] ρ 9
     ρ(α + β) = ρ(α) + ρ(β), ρ(λα) = λρ(α), ρ(α • β) = ρ(α) • ρ(β), ρ(1 A ) = Id V , (4)
where • denotes composition of operators. Remarks 2.2 (i) This is equivalent to saying that the arrow ρ : A → End(V ) from A to End(V ) is a morphism of algebras (with units). (ii) In this case, it is sometimes convenient to denote by α.v the action of ρ(α) on v (i.e. the element ρ(α) [v]) for α ∈ A and v ∈ V . (iii) It may happen (and this often occurs) that a representation has relations that are not present in the original algebra. In this case the representation is said to be not faithful. More rigourously a representation is said to be faithful iff ρ is injective or, which is equivalent, ker(ρ) = ρ -1 ({0}) = {0} (for algebras and Lie algebras) and

ker(ρ) = ρ -1 ({1 V }) = {1 G } (for groups). Example 2.3 : Let G = {1, c, c 2 } be the cyclic group of order 3 (c is the cycle 1 → 2 → 3 → 1), G admits the plane representation by ρ(c) = -1/2 - √ 3/2 √ 3/2 -1/2
(it is the matrix corresponding to a rotation of 2π/3). ( 5)

Thus, ρ(c 2 ) = -1/2 √ 3/2 - √ 3/2 -1/2 and, of course, ρ(1) = 1 0 0 1 . (6)
The representation ρ is faithful while its extension to the group algebra is not, as seen from:

ρ(1 + c + c 2 ) = 0 0 0 0 whereas 1 + c + c 2 = 0 in C[G]. (7)
Note 2.4 Note that the situation is even worse for a Lie algebra, as U k (G) is infinite dimensional iff G is not zero.

Operations on representations

Now, we would like to see the representations of AAU as building blocks to construct new ones. The elementary operations on vector spaces are:

-sums -tensor products -duals

Hence, an important problem is: Given representations ρ i : A → V i on the building blocks

V i ; i = 1, 2 how does one naturally construct representations on V 1 ⊕ V 2 , V 1 ⊗ V 2 and V * i . Sums will cause no problem as the sum V 1 ⊕ V 2 of two vector spaces V 1 and V 2 amounts to taking their cartesian product V 1 ⊕ V 2 ∼ = V 1 × V 2 . Then, if ρ i : A → V i ; i = 1, 2 are two representations of A then the mapping ρ 1 ⊕ ρ 2 : A → V 1 ⊗ V 2 such that ρ 1 ⊕ ρ 2 (a)[(v 1 , v 2 )] = (ρ 1 (a)[v 1 ], ρ 2 (a)[v 2 ]) (8)
which can be symbolically written

ρ 1 ⊕ ρ 2 = ρ 1 0 0 ρ 2 , ( 9
)
is a representation of A in V 1 ⊕ V 2 .
Dualization will be discussed later and solved by the existence of an antipode. Now, we start with the problem of constructing representations on tensor products. This will be solved by means of the notion of "scheme of actions" which is to be formalized, in our case, by the concept of comultiplication (or coproduct).

Arrows and addition or multiplication formulas

Let us give first some examples where comultiplication naturally arises. We begin with functions admitting an "addition formula" or "multiplication formula". This means functions such that for all x, y

f (x * y) = n i=1 f (1) i (x)f (2)
i (y), [START_REF] Bourbaki | Integration I[END_REF] where * is a certain (associative) operation on the defining set of f and (f

(1) i , f (2)
i ) n i=1 be two (finite) families of functions on the same set (see exercises (11.1) and (11.2) on representative functions).

The first examples are taken in the function space † R R (with * = +, the ordinary addition of real numbers). The following functions admit "addition formulas" which can be expressed diagramatically as follows.

Diagram

Addition formula

R × R + / / cos 1 cos 2 -sin 1 sin 2 # # F F F F F F F F F R cos R cos(x + y) = cos(x) cos(y) -sin(x) sin(y) R × R + / / sin 1 cos 2 + sin 2 cos 1 # # F F F F F F F F F R sin R sin(x + y) = sin(x) cos(y) + sin(y) cos(x) R × R + / / exp 1 exp 2 # # F F F F F F F F F R exp R exp(x + y) = exp(y) exp(x) R × R + / / n j=0 ( n j )pr (j) 1 pr (n-j) 2 # # F F F F F F F F F R ( ) n R (x + y) n = n j=0 n j x j y n-j
Another example can be given where the domain set (source) is C n×n , the algebra of square n × n matrices with complex coefficients. Let a ij : C n×n -→ C be the linear form which "takes" the coefficient of address (i, j) (row i and column j), that is to say a ij (M) := M[i, j]. Then, the law of multiplication of matrices says that

MN[i, j] = n k=1 M[i, k]N[k, j],
which can be represented in the style of Eq. [START_REF] Bourbaki | Integration I[END_REF] by [START_REF] Broadhurst | Towards cohomology of renormalization: bigrading the combinatorial Hopf algebra of rooted trees[END_REF] holds when the definition set (source) is a (multiplicative) semigroup of matrices (for example, the semigroup of unipotent positive matrices).

a ij (MN) = n k=1 a ik (M)a kj (N). ( 11
)
C n×n × C n×n product / / n k=1 (a ik ) 1 (a kj ) 2 ) ) S S
We now proceed to linear mappings that admit such "addition" or, rather, "multiplication" formulas.

Derivations: Let A be an arbitrary algebra with law of multiplication:

A ⊗ A µ -→ A. (12)
A derivation of A is an operator D : A -→ A which follows the Leibniz rule, that is for all x, y ∈ A, one has

D(xy) = D(x)y + xD(y) (Leibniz rule). (13)
In the spirit of what has been represented above one has

A ⊗ A µ / / D 1 Id 2 +Id 1 D 2 # # G G G G G G G G G A D A
which (as we have linear spaces and mappings) can be better represented by

A ⊗ A µ / / D⊗Id+Id⊗D A D A ⊗ A µ / / A
Automorphisms: An automorphism of A is an invertible linear mapping g : A -→ A such that for all x, y ∈ A, one has

g(xy) = g(x)g(y), (14)
which, in the spirit of what precedes can be represented by

A ⊗ A µ / / g⊗g A g A ⊗ A µ / / A
Now remark that, classically, group representations act as automorphisms and representations of Lie algebras act as derivations. This immediately provides a scheme for constructing tensor products of two representations.

Tensor product of two representations (groups and Lie algebras): First, take two representations of a group G, ρ i : G -→ End(V i ), i = 1, 2. The action of g ∈ G on the tensor space V 1 ⊗ V 2 is given by

g(v 1 ⊗ v 2 ) = g(v 1 ) ⊗ g(v 2 ). ( 15
)
This means that the "tensor product" of the two (group) representations ρ i , i = 1, 2 is given by the following data

• Space : V 1 ⊗ V 2 • Action : ρ 1 ×ρ 2 : g → ρ 1 (g) ⊗ ρ 2 (g)
Likewise, if we have two representations

ρ i : G -→ End(V i ), i = 1, 2 of the Lie algebra G the action of g ∈ G on a tensor product V 1 ⊗ V 2 is given by g(v 1 ⊗ v 2 ) = g(v 1 ) ⊗ v 2 + v 1 ⊗ g(v 2 ). (16)
Again, the "tensor product" of the two (Lie algebra) representations ρ i , i = 1, 2 is given by the following data

• Space : V 1 ⊗ V 2 • Action : ρ 1 ×ρ 2 : g → ρ 1 (g) ⊗ Id V 2 (g) + Id V 1 (g) ⊗ ρ 2 (g)
Roughly speaking, in the first case g acts by g ⊗ g and in the second one by g ⊗ 1 + 1 ⊗ g.

In view of two above cases it is convenient to construct linear mappings:

A ∆ -→ A ⊗ A , (17)
such that, in each case,

ρ 1 ×ρ 2 = (ρ 1 ⊗ ρ 2 ) • ∆. In the first case (A = C[G]) one gets ∆ g∈G α g g = g∈G α g g ⊗ g. (18)
In the second case, one has first to construct the comultiplication on the monomials g 1 ...g n ; g i ∈ G) as they span (A = U k (G)). Then, using the rule ∆(g) = g ⊗ 1 + 1 ⊗ g (for g ∈ G) and the fact that ∆ is supposed to be a morphism for the multiplication (the justification of this rests on the fact that the constructed action must be a representation see below around formula [START_REF] Isham | Lectures on Quantum Theory: Mathematical and Structural Foundations[END_REF] and exercise (11.5)), one has

∆(g 1 ...g n ) = (g 1 ⊗ 1 + 1 ⊗ g 1 )(g 2 ⊗ 1 + 1 ⊗ g 2 )...(g n ⊗ 1 + 1 ⊗ g n ) = I+J=[1...n] g[I] ⊗ g[J]. (19)
Where, for

I = {i 1 , i 2 , • • • , i k } (1 ≤ i 1 < i 2 < • • • < i k ≤ n), g[I] stands for g i 1 g i 2 • • • g i k
In each case (group algebra and envelopping algebra) one again gets a mapping ∆ : A → A ⊗ A which will be expressed by

∆(a) = n i=1 a (1) i ⊗ a (2) i (20)
which is rephrased compactly by

∆(a) = (1)(2) a (1) ⊗ a (2) . (21)
The action of a ∈ A on a tensor v 1 ⊗ v 2 is then, in both cases, given by

a.(v 1 ⊗ v 2 ) = n i=1 a (1) i .v 1 ⊗ a (2) i .v 2 = (1)(2) a (1) .v 1 ⊗ a (2) .v 2 . ( 22
)
One can easily check, in these two cases, that

a.b.(v 1 ⊗ v 2 ) = (ab).(v 1 ⊗ v 2 ), (23)
but in general [START_REF] Duchamp | Direct and dual laws for automata with multiplicities[END_REF] does not guarantee [START_REF] Duchamp | Free partially commutative structures[END_REF]; this point will be discussed below in section

(4).
Expression [START_REF] Duchamp | Feynman graphs and related Hopf algebras[END_REF] is very convenient for proofs and computations and known as Sweedler's notation.

Remarks 3.2 i) In every case, we have extracted the "scheme of action" for building the tensor product of two representations. This scheme (a linear mapping ∆ : A → A ⊗ A) is independent of the considered representations and, in each case,

ρ 1 ×ρ 2 = (ρ 1 ⊗ ρ 2 ) • ∆ (24)
ii) Sweedler's notation becomes transparent when one speaks the language of "structure constants". Let ∆ : C → C ⊗ C be a comultiplication and (b i ) i∈I a (linear) basis of C. One has

∆(b i ) = j,k∈I λ j,k i b j ⊗ b k . ( 25
)
the family (λ j,k i ) i,j,k∈I is called the "structure constants" of the comultiplication ∆. Note the duality with the notion the "structure constants" of a multiplication µ :

A ⊗ A → A : if (b i ) i∈I is a (linear) basis of A, one has µ(b i ⊗ b j ) = k∈I λ k i,j b k . (26)
For necessary and sufficient conditions for a family to be structure constants (see exercise (11.12)).

Then, the general construction for tensor products goes as follows.

Definition 3.3 : Let A be a vector space, a comultiplication ∆ on A is a linear mapping

A ∆ -→ A ⊗ A.
Such a pair (vector space, comultiplication) without any prescription about the linear mapping "comultiplication" is called a coalgebra.

Now, imitating (24), if A is an algebra and ρ 1 , ρ 2 are representations of A in V 1 , V 2 , for each a ∈ A, we can construct an action of a on V 1 ⊗ V 2 by V 1 ⊗ V 2 (ρ 1 ⊗ρ 2 )•∆(a) -→ V 1 ⊗ V 2 . ( 27
)
This means that if ∆(a) = (1)(2) a (1) ⊗ a (2) , then, (a) acts on the tensor product by

a.(v 1 ⊗ v 2 ) = (1)(2) a (1) .v 1 ⊗ a (2) .v 2 = (1)(2) ρ 1 (a (1) )[v 1 ] ⊗ ρ 2 (a (2) )[v 2 ]. (28)
But, at this stage, it is just an action and not (necessarily) a representation of A. We shall later give the requirements on ∆ for the construction of the tensor product to be reasonable (i. e. compatible with the usual tensor properties).

For the moment let us pause and consider some well known examples of comultiplication.

Combinatorics of some comultiplications

The first type of comultiplication is given by duality. This means by a formula of type

∆(x)|y ⊗ z ⊗2 = x|y * z (29)
for a certain law of algebra V ⊗ V * → V , where | is a non degenerate scalar product in V and | ⊗2 stands for its extension to V ⊗ V . In the case of words * is the concatenation and | is given by u|v = δ u,v . The comultiplication ∆ Cauchy , dual to the concatenation, is given on a word w by

∆(w) = uv=w u ⊗ v. (30)
In the same spirit, one can define a comultiplication on the algebra of a finite group by

∆(g) = g 1 g 2 =g g 1 ⊗ g 2 . ( 31
)
The second example is given by the multiplication law of elementary comultiplications, that is, if for each letter x one has ∆(

x) = x ⊗ 1 + 1 ⊗ x, then ∆(w) = ∆(a 1 ...a n ) = ∆(a 1 )∆(a 2 )...∆(a n ) = I+J=[1...n] w[I] ⊗ w[J] (32)
where

w[{i 1 , i 2 , • • • i k }] = a i 1 a i 2 • • • a i k (for 1 ≤ i 1 < i 2 < • • • < i k ≤ n).
This comultiplication is dual to [START_REF] Ford | Proc. Nat. Acad[END_REF] below for q = 0 (shuffle product).

Another example is a deformation (perturbation for small q) of the preceding. With

∆(a) = a ⊗ 1 + 1 ⊗ a + qa ⊗ a, one has ∆(w) = ∆(a 1 ...a n ) = ∆(a 1 )∆(a 2 )...∆(a n ) = I∪J=[1...n] q |I∩J| w[I] ⊗ w[J]. (33)
Note that this comultiplication is dual (in the sense of (29)) to the q-infiltration product given by the recursive formula (for general q and with 1 A * as the empty word)

w ↑ 1 A * = 1 A * ↑ w = w au ↑ bv = a(u ↑ bv) + b(au ↑ v) + qδ a,b (u ↑ v). ( 34
)
This product is an interpolation between the shuffle (q = 0) and the (classical) infiltration (q = 1) [START_REF] Duchamp | Direct and dual laws for automata with multiplicities[END_REF].

Requirements for a reasonable construction of tensor products

We have so far constructed an action of A on tensors, but nothing indicates that this is a representation (see exercise (11.5)). So, the following question is natural.

Q.1.) If A is an algebra and ∆ : A → A ⊗ A
, what do we require on ∆ if we want the construction above to be a representation of A on tensor products ?

For a, b ∈ A, ρ i representations of A in V i , and v i ∈ V i for i = 1, 2, we must have the following identity:

a.(b.v 1 ⊗ v 2 ) = (ab).v 1 ⊗ v 2 ⇐⇒ ∆(ab).v 1 ⊗ v 2 = ∆(a).(∆(b).v 1 ⊗ v 2 ). ( 35
)
One can prove that, if this is true identically for all a, b ∈ A and all pairs of representations (see exercise (11.5)), one has

∆(ab) = ∆(a)∆(b). (36)
and, of course, if the latter holds, [START_REF] Hazewinkel | Hopf algebras of endomorphisms of Hopf algebras[END_REF] is true. This can be rephrased by saying that ∆ is a morphism A → A ⊗ A.

Now, one would like to keep compatibility with the associativity of tensor products. This means that if we want to tensor u ⊗ v with w it must give the same action as tensoring u with v ⊗ w. This means that we have to address the following question.

Q.2.) If

A is an algebra and ∆ : A → A ⊗ A is a morphism of algebras, what do we require on ∆ if we want the construction above to be associative ? More precisely, for three representations ρ i , i = 1, 2, 3 of A, we want Let us compute (up to the identification above)

ρ 1 ×(ρ 2 ×ρ 3 ) = (ρ 1 ×ρ 2 )×ρ 3 (37) up to the identifications (u ⊗ v) ⊗ w = u ⊗ (v ⊗ w) = u ⊗ v ⊗ w (if
a.[(u ⊗ v) ⊗ w] = ∆(a).(u ⊗ v) ⊗ w = (∆ ⊗ Id) • ∆(a) u ⊗ v ⊗ w (38)
on the other hand

a.[u ⊗ (v ⊗ w)] = ∆(a).u ⊗ (v ⊗ w) = (Id ⊗ ∆) • ∆(a) u ⊗ v ⊗ w . (39)
Again, one can prove (see exercise (11.6)) that this holds identically (i. e. for every a ∈ A and triple of representations) iff (Id ⊗ ∆)

• ∆ = (∆ ⊗ Id) • ∆, i.e. A ∆ / / ∆ A ⊗ A Id⊗∆ A ⊗ A ∆⊗Id / / A ⊗ A ⊗ A (40)
Remark 4.1 The property [START_REF] Kreimer | On the Hopf algebra structure of pertubative quantum field theories[END_REF] is called co-associativity since if one reverses the arrows and replaces ∆ by µ, the multiplication in an algebra, the diagram expresses associativity (see also exercise (11.7) on duals of co-algebras).

A ⊗ A ⊗ A µ⊗Id / / Id⊗µ A ⊗ A µ A ⊗ A µ / / A
But the tensor product is not only associative, it has a "neutral" map which is "tensoring by the field of scalars". This derives from the fact that the canonical mappings

V ⊗ k k canr -→ V can l ←-k ⊗ k V. (41)
This can be summarized by the following question.

Q.3.) If

A is an algebra and ∆ : A → A ⊗ A a co-associative morphism of algebras, what do we require on ∆ if we want the construction above to admit "tensoring by the field of scalars" as neutral ?

More precisely, we must have a representation of A in C (which means a morphism of algebras A ǫ -→ C) such that for a representation ρ of A, we want

ρ×ǫ = ǫ×ρ = ρ (42)
up to the identification u ⊗ 1 = 1 ⊗ u = u through the isomorphisms (41) (if one is not satisfied with this identification, see exercise (11.8)).

Hence, for all a ∈ A and ρ representation on V , we should have:

can r (a.(v ⊗ 1)) = a.v, (43)
and

a.(v ⊗ 1) = (1)(2) ρ(a (1) ) ⊗ ǫ(a (2) ) [v ⊗ 1] = (ρ ⊗ Id C ) • (1)(2) a (1) ⊗ ǫ(a (2) ) [v ⊗ 1] (44) = (ρ ⊗ Id C ) • (Id ⊗ ǫ) • ∆(a)[v ⊗ 1], a.v = ρ(a)[v] = can r (ρ(a)[v] ⊗ 1) = can r (ρ ⊗ Id(a)[v ⊗ 1]). ( 45
)
Similar computations could be made on the left, we leave them to the reader as an exercise.

This means that one should require that

A ∆ / / Id A ⊗ A Id⊗ǫ A A ⊗ C canr o o A ∆ / / Id A ⊗ A ǫ⊗Id A C ⊗ A can l o o Such a mapping ǫ : A -→ C is called a co-unit.
Remark 4.2 Again, one can prove (see excercice (11.7) for details) that

ǫ is a counit for (A, ∆) ⇐⇒ ǫ is a counit for (A * , * ∆ ). ( 46
)

Bialgebras

Motivated by the preceding discussion, we define a bialgebra an algebra (associative with unit) endowed with a comultiplication (co-associative with counit) which allows for the two tensor properties of associativity and unit (see discussion above). More precisely

Definition 5.1 : (A, •, 1 A , ∆, ǫ) is said to be a bialgebra iff (1) (A, •, 1 A ) is an AAU, ( 2
) (A, ∆, ǫ) is a coalgebra coassociative with counit, (3)
∆ is a morphism of AAU and ǫ is a morphism of AAU.

The name bialgebra comes from the fact that the space A is endowed with two structures (one of AAU and one of co-AAU) with a certain compatibility between the two.

Examples of bialgebras

Free algebra (word version : noncommutative polynomials)

Let A be an alphabet (a set of variables) and A * be the free monoid constructed on A (see Basic Structures (12.2)). For any field of scalars k (one may think of k = R or C), we call the algebra of noncommutative polynomials k A (or free algebra), the algebra k[A * ] of the free monoid A * constructed on A. This is the set of functions f : A * → k with finite support endowed with the convolution product

f * g(w) = uv=w f (u)g(v) (47)
Each word w ∈ A * is identified with its characteristic function (i.e. the Dirac function with value 1 at w and 0 elsewhere). These functions form a basis of k A and then, every f ∈ k A can be written uniquely as a finite sum f = f (w)w. The inclusion mapping A ֒→ k A will be denoted here by can A .

Comultiplications The free algebra k A admits many comultiplications (even with the two requirements of being a morphism and coassociative). As A * is a basis of k A , it is sufficient to define it on the words (if we require ∆ to be a morphism it is enough to define it on letters).

Example 1 . -The first example is the dual of the Cauchy (or convolution) product

∆(w) = uv=w u ⊗ v (48)
is not a morphism as ∆(ab

) = ab ⊗ 1 + a ⊗ b + 1 ⊗ ab and ∆(a)∆(b) = ab ⊗ 1 + a ⊗ b + b ⊗ a + 1 ⊗ ab
but it can be checked that it is coassociative (see also exercice (11.7) for a quick proof of this fact). . This comultiplication is a morphism but not coassociative as

(I ⊗ ∆) • ∆(a) = a ⊗ b ⊗ a ; (∆ ⊗ I) • ∆(a) = a ⊗ a ⊗ b Example 3 .
-The third example is given on the letters by

∆(a) = a ⊗ 1 + 1 ⊗ a + qa ⊗ a
where q ∈ k. One can prove that

∆(w) = ∆(a 1 ...a n ) = ∆(a 1 )∆(a 2 )...∆(a n ) = I∪J=[1..|w|] q |I∩J| w[I] ⊗ w[J] ( 49
)
this comultiplication is coassociative. For q = 0, one gets a comultiplication given on the letters by ∆ s (a) = a ⊗ 1 + 1 ⊗ a.

For every polynomial P ∈ k A , set ǫ(P ) = P (1 A * ) (the constant term). Then (k A , * , ∆ s , ǫ) is a bialgebra. One has also another bialgebra structure with, for all a ∈ A

∆ h (a) = a ⊗ a ; ǫ aug (a) = 1 (50)
this bialgebra (k A , * , ∆ h , ǫ aug ) is a substructure of the bialgebra of the free group.

Algebra of polynomials (commutative polynomials)

We continue with the same alphabet A, but this time, we take as algebra k[A]. The construction is similar but the monomials, instead of words, are all the commutative products of letters i.e. a α 1 1 a α 2 2 • • • a αn n with n arbitrary and α i ∈ N. Denoting MON(A) the monoid of these monomials (comprising, as neutral, the empty one) and with ∆ s (a) = a ⊗ 1 + 1 ⊗ a, ǫ(P ) = P (1 MON(A) ), one can again check that (k[A], * , ∆ s , ǫ) is a bialgebra.

Algebra of partially commutative polynomials

For the detailed construction of a partially commutative monoid, the reader is referred to [START_REF] Cartier | Problèmes combinatoires de commutation et rarrangements[END_REF][START_REF] Duchamp | Free partially commutative structures[END_REF]. These monoids generalize both the free and free commutative monoids. To a given graph (non-oriented and without loops) ϑ ⊂ A × A, one can asssociate the monoid presented by generators and relations (see basic structures (51) This is exactly the monoid obtained as a quotient structure of the free monoid (A * ) by the smallest equivalence compatible with products (a congruence ‡) which contains the pairs (xy, yx) (x,y)∈ϑ . A geometric model of this monoid using pieces was developped by X. Viennot [START_REF] Viennot | Heaps of pieces, I: Basic definitions and combinatorial lemmas[END_REF] where pieces are located on "positions" (drawn on a plane) two pieces "commute" iff they are on positions which do not intersect (see fig 1 below).

a b c

Fig 1 . -Representation of a partially commutative monomial by "heaps of pieces" [START_REF] Viennot | Heaps of pieces, I: Basic definitions and combinatorial lemmas[END_REF]. Here "a" commutes with "c" (they are on non-concurrent positions) and "b" commutes with no other piece. The monomial represented can be written by several words as acbc 3 ba 2 c = cabc 3 baca = cabc 3 bca 2 .

The partially commutative algebra k A, ϑ is the algebra k[M(A, ϑ)] [START_REF] Duchamp | Free partially commutative structures[END_REF]. Again, one can check that (k A, ϑ , * , ∆ s , ǫ) (constructed as above) is a bialgebra.

Algebra of a group

Let G be a group. The algebra under consideration is k[G]. We define, for g ∈ G, ∆(g) = g ⊗ g and ǫ(g) = 1, then, one can check that (k[G], ., ∆, ǫ) is a bialgebra.

Antipode and the problem of duals

Each vector space V comes with its dualΣ

V * = Hom C (V, C).
(52) ‡ See exercise (11.4) and the presentation of monoids "by generators and relations in paragraph "(12.2). Σ In general, for two k-vector spaces V and W , Hom k (V, W ) is the set of all linear mappings V → W .

In the case of groups, g -→ g -1 does the job; in the case of Lie algebras g -→ -g (extended by reverse products to the enveloping algebra) works.

On the other hand, in the classical textbooks, the discussion of "complete reductibility" goes with the existence of an "invariant" scalar product φ :

V × V → k on a space V .
For a group G, this reads

(∀g ∈ G)(∀x, y ∈ V ) φ(g.x, g.y) = φ(x, y) (56)
(think of unitary representations).

For a Lie algebra G, this reads

(∀g ∈ G)(∀x, y ∈ V ) φ(g.x, y) + φ(x, g.y) = 0 (57)
(think of the Killing form). Now, linearizing the situation by Φ(x ⊗ y) = φ(x, y) and remembering our unit representation, one can rephrase (56) and (57) in

(∀a ∈ A)(∀x, y ∈ V ) Φ( (1)(2)
a (1) .x ⊗ a (2) .y) = ǫ(a)Φ(x ⊗ y) .

Likewise, we will say that a bilinear form Φ :

U ⊗ V → k is invariant is it satisfies (∀a ∈ A)(∀x ∈ U, y ∈ V ) Φ( (1)(2)
a (1) .x ⊗ a (2) .y) = ǫ(a)Φ(x ⊗ y) . ( 59
)
which means that Φ is A linear for the structures being given respectively by ρ 1 ×ρ 2 on U ⊗ k V and ǫ on k. Now, suppose that we have constructed a representation of a certain algebra A on U * by means of an antimorphism α : A → A. To require that the natural contraction c : U * ⊗ U → k be "invariant" means that

(∀a ∈ A)(∀f ∈ U * , y ∈ U) c( (1)(2) a (1) .f ⊗ a (2) .y) = ǫ(a)c(f ⊗ y) = ǫ(a)f (y) ; (∀a ∈ A)(∀f ∈ U * , y ∈ U) (1)(2) f (α(a (1) )a (2) .y) = ǫ(a)f (y) . (60)
It is easy to check (taking a basis (e i ) i∈I and its dual family (e * i ) i∈I for example) that (60) is equivalent to

(∀a ∈ A) ρ U ( (1)(2) α(a (1) )a (2) ) = ǫ(a)Id U . (61)
Likewise, taking the natural contraction c : U ⊗ U * → k, one gets

(∀a ∈ A) ρ U ( (1)(2)
a (1) α(a (2) )) = ǫ(a)Id U . (62)
Taking U = A and for ρ U the left regular representation, one gets

(∀a ∈ A) (1)(2) a (1) α(a (2) ) = (1)(2) α(a (1) )a (2) ) = ǫ(a) . (63)
Motivated by the preceding discussion, one can make the following definition.

Definition 6.1 Let (A, •, 1 A , ∆, ǫ) be a bialgebra. A linear mapping α : A → A is called an antipode for A, if for all a ∈ A (1)(2)
α(a (1) )a (2) = (1)(2)
a (1) α(a (2) ) = 1 A ǫ(a). (64)
One can prove (see exercise (11.9)), that this means that α is the inverse of Id A for a certain product of an algebra (AAU) on End k (A) and this implies (see exercise (11.9)) that (i) If α exists (as a solution of Eq.( 64)), it is unique.

(ii) If α exists, it is an antimorphism. Definition 6.2 : (Hopf Algebra) (A, •, 1 A , ∆, ǫ, S) is said to be a Hopf algebra iff

(1) B = (A, •, 1 A , ∆, ǫ) is a bialgebra, (2)
S is an antipode (then unique) for B

In many combinatorial cases (see exercise on local finiteness (11.10)), one can compute the antipode by

α(d) = ∞ k=0 (-1) k+1 (I + ) ( * k) (d)). ( 65
)
where I + is the projection on B + = ker(ǫ) such that I + (1 B ) = 0.

whose hamiltonian is H (β ≡ 1/kT , k = Boltzmann's constant T = absolute temperature). We may evaluate the trace over any complete set of states; we choose the (over-)complete set of coherent states

|z = e -|z| 2 /2 n (z n / √ n!)a +n |0 (67)
where a + is the boson creation operator satisfying [a, a + ] = 1 and for which the completeness or resolution of unity property is

1 π dz|z z| = I ≡ d(z)|z z|. ( 68
)
Sometimes physicists write d 2 z to emphasize that the integral is two dimensional (over R) but here, the l. h. s. of (68) is the integration of the operator valued function z → |z z| -see [START_REF] Bourbaki | Integration I[END_REF] Chap. III Paragraph 3 -w.r.t. the Haar mesure of C which is dz.

The simplest, and generic, example is the free single boson hamiltonian H = ǫa + a for which the appropriate trace calculation is

Z = 1 π dz z|exp(-βa + a)|z = = 1 π dz z| : exp(a + a(e -βǫ -1) : |z . ( 69
)
Here we have used the following well known relation for the forgetful normal ordering operator : f (a, a + ) : which means "normally order the creation and annihilation operators in f forgetting the commutation relation [a, a + ] = 1" ¶. We may write the Partition Function in general as

Z(x) = F (x, z)d(z) (70)
thereby defining the Partition Function Integrand (PFI) F (x, z). We have explicitly written the dependence on x = -β, the inverse temperature, and ǫ, the energy scale in the hamiltonian.

Combinatorial aspects: Bell numbers

The generic free boson example Eq. (70) above may be rewritten to show the connection with certain well known combinatorial numbers. Writing y = |z| 2 and x = -βǫ, Eq.( 70) becomes

Z = ∞ 0 dy exp(y(e x -1)) . (71)
This is an integral over the classical exponential generating function for the Bell polynomials

exp(y(e x -1)) = ∞ n=0 B n (y) x n n! (72)
where the Bell number is B n (1) = B(n), the number of ways of putting n different objects into n identical containers (some may be left empty). Related to the Bell numbers are the Stirling numbers of the second kind S(n, k), which are defined as the number of ways of putting n different objects into k identical containers, leaving none empty. From the definition we have B(n) = n k=1 S(n, k) (for n = 0). The foregoing gives a combinatorial interpretation of the partition function integrand F (x, y) as the exponential generating function of the Bell polynomials.

Graphs

We now give a graphical representation of the Bell numbers. Consider labelled lines which emanate from a white dot, the origin, and finish on a black dot, the vertex. We shall allow only one line from each white dot but impose no limit on the number of ¶ Of course, this procedure may alter the value of the operator to which it is applied. lines ending on a black dot. Clearly this simulates the definition of S(n, k) and B(n), with the white dots playing the role of the distinguishable objects, whence the lines are labelled, and the black dots that of the indistinguishable containers. The identification of the graphs for 1,2 and 3 lines is given in Figure 2. We have concentrated on the Bell number sequence and its associated graphs since, as we shall show, there is a sense in which this sequence of graphs is generic. That is, we can represent any combinatorial sequence by the same sequence of graphs as in the Figure 2 with suitable vertex multipliers (denoted by the V terms in the same figure). Consider a general partition function

Z = T r exp(-βH) (73)
where the Hamiltonian is given by H = ǫw(a, a + ), with w a string (= sum of products of positive powers) of boson creation and annihilation operators. The partition function integrand F for which we seek to give a graphical expansion, is

Z(x) = F (x, z)d(z) (74)
where

F (x, z) = z|exp(xw)|z = (x = -βǫ) = ∞ n=0 z|w n |z x n n! = ∞ n=0 W n (z) x n n! = exp ∞ n=1 V n (z) x n n! (75)
with obvious definitions of W n and V n . The sequences {W n } and {V n } may each be recursively obtained from the other. This relates the sequence of multipliers {V n } of Figure 2 to the Hamiltonian of Eq. (73). The lower limit 1 in the V n summation is a consequence of the normalization of the coherent state |z .

The Hopf Algebra L Bell

We briefly describe the Hopf algebra L Bell which the diagrams of Figure 2 define. 1. Each distinct diagram is an individual basis element of L Bell ; thus the dimension is infinite. (Visualise each diagram in a "box".) The sum of two diagrams is simply the two boxes containing the diagrams. Scalar multiples are formal; for example, they may be provided by the V coefficients. Precisely, as a vector space, L Bell is the space freely generated by the diagrams of Figure 2 (see APPENDIX : Function Spaces).

2. The identity element e is the empty diagram (an empty box).

3. Multiplication is the juxtaposition of two diagrams within the same "box". L Bell is generated by the connected diagrams; this is a consequence of the Connected Graph Theorem [START_REF] Ford | Proc. Nat. Acad[END_REF]. Since we have not here specified an order for the juxtaposition, multipli cation is commutative.

Suppose that one can express H as

H(a, a + , b, b + ) = H 1 (a, a + ) + H 2 (b, b + ). ( 78
)
and that, exp(λH 1 ) and exp(λH 2 ) (λ = -β) are solved i.e. that we have expressions

F (λ) = exp(λH 1 ) = ∞ n=0 λ n n! H (n) 1 (a, a + ) ; G(λ) = exp(λH 2 ) = ∞ n=0 λ n n! H (n) 2 (b, b + ) (79) It is not difficult to check that exp(λH) = exp λ(H 1 + H 2 ) = F (λ d dx )G(x) x=0 (80)
This leads us to define, in general, the "Hadamard exponential product". Let

F (z) = n≥0 a n z n n! , G(z) = n≥0 b n z n n! (81)
and define their product (the "Hadamard exponential product") by

H(F, G) := n≥0 a n b n z n n! = H(F, G) = F z d dx G(x) x=0 . (82)
When F (0) and G(0) are not zero one can normalize the functions in this bilinear product so that F (0) = G(0) = 1. We would like to obtain compact and generic formulas. If we write the functions as

F (z) = exp ∞ n=1 L n z n n! and G(z) = exp ∞ n=1 V n z n n! . ( 83
)
that is, as free exponentials, then by using Bell polynomials in the sets of variables L, V (see [START_REF] Duchamp | Feynman graphs and related Hopf algebras[END_REF][START_REF] Duchamp | One-parameter groups and combinatorial physics[END_REF] for details), we obtain

H(F, G) = n≥0 z n n! P 1 ,P 2 ∈U Pn L T ype(P 1 ) V T ype(P 2 ) (84)
where UP n is the set of unordered partitions of [1

• • • n].
An unordered partition P of a set X is a collection of (nonempty) subsets of X, mutually disjoint and covering X (i.e. the union of all the subsets is X, see [START_REF] Duchamp | A Three Parameter Hopf Deformation of the Algebra of Feynman-like Diagrams[END_REF] for details). The type of P ∈ UP n (denoted above by T ype(P )) is the multi-index (α i ) i∈N + such that α k is the number of k-blocks, that is the number of members of P with cardinality k.

At this point the formula entangles and the diagrams of the theory arise.

Note particularly that

• the monomial L T ype(P 1 ) V T ype(P 2 ) needs much less information than that which is contained in the individual partitions P 1 , P 2 (for example, one can relabel the elements without changing the monomial),

• two partitions have an incidence matrix from which it is still possible to recover the types of the partitions.

The construction now proceeds as follows.

(i) Take two unordered partitions of [1

• • • n], say P 1 , P 2 .
(ii) Write down their incidence matrix (card

(Y ∩ Z)) (Y,Z)∈P 1 ×P 2 .
(iii) Construct the diagram representing the multiplicities of the incidence matrix : for each block of P 1 draw a black spot (resp. for each block of P 2 draw a white spot).

(iv) Draw lines between the black spot Y ∈ P 1 and the white spot Z ∈ P 2 ; there are card(Y ∩ Z) such.

(v) Remove the information of the blocks Y, Z, • • •.

In so doing, one obtains a bipartite graph with p (= card(P 1 )) black spots, q (= card(P 2 )) white spots, no isolated vertex and integer multiplicities. We denote the set of such diagrams by diag. The incidence matrix corresponding to the diagram (as drawn) or these partitions is

  0 2 1 0 1 1 3 0 0 0 1 2   .
But, due to the fact that the defining partitions are unordered, one can permute the spots (black and white, between themselves) and, so, the lines and columns of this matrix can be permuted. Thus, the diagram could be represented by the matrix

  0 0 1 2 0 2 1 0 1 0 3 1   as well.
The product formula now reads

H(F, G) = n≥0 z n n! d∈diag |d|=n mult(d)L α(d) V β(d) (85)
where α(d) (resp. β(d)) is the "white spot type" (resp. the "black spot type") i.e. the multi-index

(α i ) i∈N + (resp. (β i ) i∈N + ) such that α i (resp. β i )

Diagrams

One can design a (graphically) natural multiplicative structure on diag such that the arrow

d → L α(d) V β(d) . ( 86
)
be a morphism. This is provided by the concatenation of the diagrams (the result, i.e. the diagram obtained in placing d 2 at the right of d 1 , will be denoted by [d 1 |d 2 ] D ). One must check that this product is compatible with the equivalence of the permutation of white and black spots among themselves, which is rather straightforward (see [START_REF] Duchamp | Feynman graphs and related Hopf algebras[END_REF][START_REF] Duchamp | A Three Parameter Hopf Deformation of the Algebra of Feynman-like Diagrams[END_REF]). We have Proposition 8.2 [START_REF] Duchamp | A Three Parameter Hopf Deformation of the Algebra of Feynman-like Diagrams[END_REF] Let diag be the set of diagrams (including the empty one).

i) The law (d 1 , d 2 ) → [d 1 |d 2 ] D endows diag with the structure of a commutative monoid with the empty diagram as neutral element(this diagram will, therefore, be denoted by d) is a morphism of monoids, the codomain of this arrow being the monoid of (commutative) monomials in the alphabet L ∪ V i.e.

1 diag ). ii) The arrow d → L α(d) V β(

MON(L

∪ V) = {L α V β } α,β∈(N + ) (N) = n,m≥1 {L α 1 1 L α 2 2 • • • L αn n V β 1 1 V β 2 2 • • • V βm m } α i ,β j ∈N . ( 87
)
iii) The monoid (diag, [-|-] D , 1 diag ) is a free commutative monoid. The set on which it is built is the set of the connected (non-empty) diagrams.

Remark 8.3

The reader who is not familiar with the algebraic structure of MON(X) can find rigorous definitions in paragraph (12.2).

We denote φ mon,diag the arrow diag → MON(L ∪ V).

Labelled diagrams

We have seen the diagrams (of diag) are in one-to-one correspondence with classes of matrices as in Fig. 3. In order to fix one representative of this class, we have to number the black (resp. white) spots from 1 to, say p (resp. q). Doing so, one obtains a packed matrix [START_REF] Duchamp | Non commutative functions VI: Free quasisymmetric functions and related algebras[END_REF] that is, a matrix of integers with no row nor column consisting entirely of zeroes. In this way, we define the labelled diagrams.

Definition 8.4 A labelled diagram of size p × q is a bi-coloured (vertices are p black and q white spots) graph

• with no isolated vertex

• every black spot is joined to a white spot by an arbitrary quantity (but a positive integer) of lines

• the black (resp. white) spots are numbered from 1 to p (resp. from 1 to q).

As in paragraph (8.1), one can concatenate the labelled diagrams, the result, i.e. the diagram obtained in placing D 2 at the right of D 1 , will be denoted by [D 1 |D 2 ] L . This time we need not check compatibility with classes. We have a structure of free monoid (but not commutative this time) Proposition 8.5 [START_REF] Duchamp | A Three Parameter Hopf Deformation of the Algebra of Feynman-like Diagrams[END_REF] Let ldiag be the set of labeled diagrams (including the empty one).

i) The law

(d 1 , d 2 ) → [d 1 |d 2 ]
L endows ldiag with the structure of a noncommutative monoid with the empty diagram (p = q = 0) as neutral element (which will, therefore, be denoted by 1 ldiag ).

ii) The arrow from ldiag to diag, which implies "forgetting the labels of the vertices" is a morphism of monoids.

iii) The monoid (ldiag, [-|-] L , 1 ldiag ) is a free (noncommutative) monoid which is constructed on the set of irreducible diagrams which are diagrams d = 1 ldiag which cannot be written

d = [d 1 |d 2 ] L with d i = 1 ldiag . Remark 8.6 i) In a general monoid (M, ⋆, 1 M ), the irreducible elements are the elements x = 1 M such that x = y ⋆ z =⇒ 1 M ∈ {y, z}.
ii) It can happen that an irreducible of ldiag has an image in diag which splits (i. e. is reducible), as shown by the simple example of the cross defined by the incidence matrix 0 1 1 0 .

Hopf algebras DIAG and LDIAG

Let us first construct the Hopf algebra on the labelled diagrams (details can be found in [START_REF] Duchamp | A Three Parameter Hopf Deformation of the Algebra of Feynman-like Diagrams[END_REF]). In order to define the comultiplication, we need the notion of "restriction of a labelled diagram". Consider d ∈ ldiag of size p × q. For any subset I ⊂ [1.

.p], we define a labelled diagram d[I] (of size k × l, k = card(I)) by taking the k = |I| black spots numbered in I and the edges (resp. white spots) that are connected to them. We take this subgraph and relabel the black (resp. white) spots in increasing order. The construction of the Hopf algebra LDIAG goes as follows :

(i) the algebra structure is that of algebra of the monoid ldiag so that the elements of LDIAG are

x = d∈ldiag α d d (88)
(the sum is finitely supported)

(ii) the comultiplication is given, on a labelled diagram d ∈ ldiag of size p × q, by ∆ L (d) = I+J=[1..p] d[I] × d[J] (89)
(iii) the counit is "taking the coefficient of the void diagram", that is, for x as in Eq. (88),

ǫ L (x) = α 1 ldiag . (90)
One can check that (LDIAG, [-|-] L , 1 ldiag , ∆ L , ǫ L ) is a bialgebra (for proofs see [START_REF] Duchamp | A Three Parameter Hopf Deformation of the Algebra of Feynman-like Diagrams[END_REF]). Now one can check that we satisfy the conditions of exercise (11.10) question 3 and the antipode S L can be computed by formula (124) of the same exercise.

We have so far constructed the Hopf algebra (LDIAG, [-|-] L , 1 ldiag , ∆, ǫ, S L ).

The constructions above are compatible with the arrow φ DIAG,LDIAG : LDIAG → DIAG deduced from the class-map φ diag,ldiag : ldiag → diag (a diagram is a class of labelled diagrams under permutations of black and white spots among themselves). So that, one can deduce "by taking quotients" a structure of Hopf algebra on the algebra of diag. Denoting this algebra by DIAG, one has a natural Hopf algebra structure (DIAG, [-|-] D , 1 diag , ∆ D , ǫ D , S D ) and one can prove that this is the unique Hopf algebra structure such that φ DIAG,LDIAG is a morphism for the algebra and coalgebra structures.

9. Link between LDIAG and other Hopf algebras

The deformed case

One can construct a three-parameter Hopf algebra deformation of LDIAG (see [START_REF] Duchamp | A Three Parameter Hopf Deformation of the Algebra of Feynman-like Diagrams[END_REF]), denoted LDIAG(q c , q s , q t ) such that LDIAG(0, 0, 0) = LDIAG and LDIAG(1, 1, 1) = MQSym the algebra of Matrix Quasi Symmetric Functions [START_REF] Duchamp | Non commutative functions VI: Free quasisymmetric functions and related algebras[END_REF]).

On the other hand, it was proved by L. Foissy [START_REF] Foissy | Les algèbres de Hopf des arbres enracinés I[END_REF][START_REF] Foissy | Les algèbres de Hopf des arbres enracinś II[END_REF] that one of the planar decorated trees Hopf algebra is isomorphic MQSym and even to LDIAG(1, q s , t) for every q s and t ∈ {0, 1}. The complete picture is given below.

Duals of Hopf algebras

The question of dualizing a Hopf algebra (i.e. endowing the dual -or a subspace of it -with a structure of Hopf algebra) is solved, in complete generality, by the machinery of Sweedler's duals. The procedure consists in taking the "representative" linear forms (instead of all the linear forms) and dualize w.r.t. the following table

comultiplication → multiplication counit → unit multiplication → comultiplication unit → counit antipode
→ trsnspose of the antipode.

In the case when the Hopf algebra is free as an algebra (which is often the case with noncommutative Hopf algebras of combinatorial physics), one can use rational expressions of Automata Theory to get a genuine calculus within this dual (see [START_REF] Duchamp | Sweedler's duals and Schützenberger's calculus[END_REF]).

EXERCISES Exercise 11.1 Representative functions on R (Complex valued)

. A function R f -→ C is said to be representative if there exist (f (1)
i ) n i=1 and (f

i ) n i=1 such that, for all x, y ∈ R one has

f (x + y) = n i=1 f (1) i (x)f (2)
i (y).

(91)

1) Show that cos, cos 2 , sin, exp and a → a n are representative. Provide minimal sums of type Eq.(91).

2) Show that the following are equivalent i) f is representative.

ii) There exists a group representation (R, +)

ρ -→ C n×n , a row vector λ ∈ C 1×n , a column vector γ ∈ C n×1 such that f (x) = λρ(x)γ. iii) (f t ) t∈R is of finite rank in C R (here f t , the shift of f by t, is the function x -→ f (x + t)).
3) Show that the minimal n such that formula Eq.( 91) holds is also the rank (over C) of (f t ) t∈R . 4) a) If f is continuous then ρ can be chosen so and ρ(x) = e xT for a certain matrix T ∈ C n×n . b) In this case show that representative functions are linear combinations of products of polynomials and exponentials.

5) f ∈ C R is representative iff Re(f ) = (f + f )/2 and Im(f ) = (f -f)/2i are representative in R R .
6) Show that the set of representative functions of C R is a C-vector space. This space will be denoted Rep C (R). 7) Show that the functions ϕ n,λ = x n e λx are a basis of Rep C (R) ∩ C o (R; C) (i.e. continuous complex valued representative functions on R). 8) Deduce from (7) that the following statement is false: "If a entire function f : R → C is such that (f t ) t∈Z is of finite rank, then it is representative". Hint : Consider exp(exp(2iπx)).

Exercise 11.2 Representative functions in general (see also [START_REF] Solomon | Hopf Algebras[END_REF][START_REF] Chari | A guide to quantum groups[END_REF]) Let M be a monoid (semigroup with unit) and k a field (one can first think of k = R, C). For a function M f -→ k one defines the shifts:

f z : x -→ f (zx), y f : x -→ f (xy), y f z : x -→ f (zxy). ( 92
)
1)a) Check the following formulas

(f y 1 ) y 2 = f y 1 y 2 , y 2 ( y 1 f ) = y 2 y 1 f ( x f ) y = x (f y ) = x f y . ( 93
)
As for groups, if M is a monoid, a M-module structure on a vector space V is defined by a morphism or an anti-morphism M → End k (V ). b) From Eqs.(93) define two canonical M-module structures of k M .

2)a) Show that the following are equivalent i)

(f z ) z∈M is of finite rank in k M . ii) ( y f ) y∈M is of finite rank in k M .
iii) ( y f z ) y,z∈M is of finite rank in k M . iv) There exist two families (f

i ) n i=1 and (f

(2) i ) n i=1 such that f (xy) = n i=1 f (1) i (x)f (2)
i (y).

(

94)

v) There exists a representation of M ρ : M -→ k n×n , a row vector λ ∈ k 1×n , a column vector γ ∈ k n×1 such that f (x) = λρ(x)γ for all x ∈ M. b) Using (v) above, show that the (pointwise) product of two representative functions is representative.

One denotes Rep k (M) the space of (k-valued) representative functions on M.

3) a) Recall briefly why the mapping

k M ⊗ k M → k M ×M (95) defined by n i=1 f (1) i ⊗ f (2) i → (x, y) → n i=1 f (1)
i (x)f Exercise 11.3 (Example of a monoid coming from dissipation theory [START_REF] Solomon | Thermalization of squeezed states[END_REF]). Let (M n , ×) be the monoid of n × n complex square matrices endowed with the usual product (M n , .) = (C n×n , ×)

We define a state (Von Neumann) as a positive semi-definite hermitian matrix of trace one (= 1) i.e. a matrix ρ such that

(i) ρ = ρ * (ii) (∀x ∈ C n×1 )(x * ρx ≥ 0) (iii) T r(ρ) = 1.
The set of such states will be denoted by S n . 1) (Structure) a) Show that S n is convex. b) Show that S n is compact.

Hint : Consider the set of possible spectra i.e. the simplex

S = {(λ 1 , λ 2 , • • • , λ n ) ∈ (R + ) n | n i=1 λ i = 1}
and show that S n is the range of the continuous mapping φ : U (n) × S → M n given by the formula

φ(u, s) = udu * ; with d =      λ 1 0 • • • 0 0 λ 2 • • • 0 . . . 0 • • • 0 λ n      (97)
and where s

= (λ 1 , λ 2 , • • • , λ n ).
c) Show that the extremal elements [START_REF] Bourbaki | Topological Vector Spaces[END_REF] of the compact S n is the set of orthogonal projections of rank one and that this set is connected by arcs.

2) (KS condition) We say that a finite family (k i ) i∈I (I is finite) of elements in M n fulfils the KS condition iff i∈I k * i k i = I n (I n is the unity matrix, the unit of the monoid M n ). On the other hand, given two finite families A = (k i ) i∈I and B = (l j ) j∈J , we define A * B as the family

A * B = (k i l j ) (i,j)∈I×J (98)
a) Show that, if A and B fulfil the KS condition then so too does A * B.

To every (finite) family A = (k i ) i∈I which fulfils the KS condition, we attach a transformation φ A : M n → M n , given by the formula

φ A (M) = i∈I k i Mk * i (99)
b) Show that φ A is linear and preserves S n (i.e. φ A (S n ) ⊂ S n ). c) Show that if A and B fulfil the KS condition, one has

φ A • φ B = φ A * B ( 100
)
Conclude that the φ A form a semigroup of transformations (with unit). d) (Example) Let (E i,j ) i,j∈{1,2} be the set of the four matrix units in M 2 . Show that the following families fulfil KS condition

A = (E 11 , 1 (2) E 12 , 1 (2) E 22 ) B = ( 1 (2) E 11 , 1 (2) E 21 , E 22 ) (101)
Compute A * B.

3) (Description of the semigroup at the level of multisets). In order to pull-back the formula (100) at the level of multisets, we remark that the order or the labelling of the elements k i is irrelevant; all that counts is their multiplicities. a) (Example showing that the "set" structure is too weak). Let (E i,j ) i,j∈{1,2} be the set of the four matrix units in M 2 and set

A = ( 1 (2) E 11 , 1 (2)
(∀M ∈ M n )(λ M ∈ N) (103)
the set of elements fulfilling (103) will be denoted

N[M n ]. b)
To every finite family of matrices (in M n ) A = (M i ) i∈I one may associate its sum (in

R[M n ]) S(A) = i∈I M i , check that it is an element of N[M n ] and that every element of N[M n ] is obtained so. c) Show that S(A * B) = S(A).S(B) ∈ N[M n ] ⊂ R[M n ] and deduce that (N[M n ], .) is a monoid. d) To every multiset of matrices (in M n ) A = M ∈Mn α(M)[M]
, one associates

T (A) = M ∈Mn α(M)[M * M]
show that, if A = (M i ) i∈I is a finite set of matrices, one has i∈I

M * i M i = T (S(A)) (104) e) Show that, if T (A) = I n , T (A.B) = T (B). We denote N[M n ] KS the set of A ∈ N[M n ] such that T (A) = I n .
f ) Check that the mapping φ A defined previously depends only on S(A) and denote, for A ∈ N[M n ] KS the mapping Φ A deduced from this property. g) Prove that the mapping (N[M n ] KS , .) → (End C (C n×n ), •) is a morphism of semigroups (preserving the units).

4) (Invertible elements) To every

A = M ∈Mn α(M)[M] ∈ N[M n ] KS one associates ǫ(A) = M ∈Mn α(M) ∈ N. a) Prove that ǫ(A.B) = ǫ(A)ǫ(B) (105
then prove that ≡ is compatible with the right and left "translations" of the monoid this means that

(∀ x, y, t, s ∈ S)(x ≡ y =⇒ [s * x * t ≡ s * y * t]) (108)
b) Conversely, we suppose that ≡ is an equivalence on M satisfying condition (108), show that the result Cl(x ′ * y ′ ) does not depend on the choice of x ′ ∈ Cl(x); y ′ ∈ Cl(x) and therefore construct a law ⊥ on M/ ≡ such that the class function is a morphism (i.e. (107)). c) Show moreover that, in the preceding conditions, M/ ≡, ⊥, Cl(1 M ) is a monoid.

Exercise 11.5 Let A be an AAU and ∆ : A → A ⊗ A a comultiplication. We build (tensor) products of two representations by the formula [START_REF] Duchamp | Congruences Compatible with the Shuffle Product[END_REF], more precisely by

can • (ρ 1 ⊗ ρ 2 ) • ∆ (109)
where can :

End(V 1 ) ⊗ End(V 2 ) → End(V 1 ⊗ V 2 )
is the canonical mapping. a) Prove that, if ∆ is a morphism of algebras, then the linear mapping

ρ 1 × ρ 2 : A → End(V 1 ⊗ V 2 ) ( 110
)
defined by the composition (109) is a morphism of AAU (and hence a representation).

b) Prove that, if ρ 1 × ρ 2 is a representation for any pair ρ 1 , ρ 2 of representations of A, then ∆ is a morphism of AAU (use ρ 1 = ρ 2 , the -regular -representation of A on itself by multiplications on the left).

Exercise 11.6 We consider the canonical isomorphisms

can 1|23 : V 1 ⊗ (V 2 ⊗ V 3 ) → V 1 ⊗ V 2 ⊗ V 3 can 12|3 : (V 1 ⊗ V 2 ) ⊗ V 3 → V 1 ⊗ V 2 ⊗ V 3 (111)
Show that, in order to have [START_REF] Hoffman | Quasi-shuffle products[END_REF] for every triple ρ i , i = 1, 2, 3 of representations it is necessary and sufficient that

can 12|3 • (∆ ⊗ Id A ) • ∆ = can 1|23 • (Id A ⊗ ∆) • ∆ (112)
(for the necessary condition, consider again the left regular representations).

Exercise 11.7 Let (A, ∆) be a coalgebra (∆ is an arbitrary -but fixed -linear mapping) and (A * , * ∆ ) be its dual algebra. Explicitely, for f, g ∈ A * and x ∈ A (for convenience, the law is written in infix denotation)

f * ∆ g|x = f ⊗ g|∆(x) (113)
Prove the following equivalences

∆ is co-associative ⇐⇒ * ∆ is associative (114) (∀ǫ ∈ A * ) ǫ is a unity for (A * , * ∆ ) ⇐⇒ ǫ is a co-unity for (A, ∆) (115)
Exercise 11.8 The mappings can l , can r are as in [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF]. Prove that, in order that for any representation ρ of A, one has

can l • (ǫ ⊗ ρ) • ∆ = can r • (ρ ⊗ ǫ) • ∆ (116)
it is necessary and sufficient that ǫ be a counit.

Exercise 11.9 Let (C, ∆) be a coalgebra and (A, µ) ba an algebra on the same (commutative) field of scalars k. We define a multiplication (called convolution) on Hom k (C, A) by

f * g = µ • (f ⊗ g) • ∆ (117) so that, if ∆(x) = (1)(2) x (1) x (2) , f * g(x) = (1)(2)
f (x (1) )g(x (2) ).

1) If A is associative and C coassociative, show that the algebra (Hom k (C, A), * ) is associative.

2) We suppose moreover that C admits a counit ǫ : C → k and A a unit 1 A (identified with the linear mapping k → A given by λ → λ1 A ). Show that 1 A • ǫ (traditionnally denoted 1 A ǫ) is the unit of the algebra (Hom k (C, A), * ).

3) Let (B, * , 1, ∆, ǫ) be a bialgebra. The convolution under consideration will be that constructed between the coalgebra (B, ∆, ǫ) and the algebra (B, * , 1). a) Let S ∈ End(B). Show that the following are equivalent i) S is an antipode for B ii) S is the inverse of Id B in (End k (B), * ). b) Deduce from (b) that the antipode, if it exists, is unique. c) Prove that the bialgebra (k A , * , ∆ h , ǫ aug ) defined around equation (50) admits no antipode (if the alphabet A is not empty). 4) Let (C, ∆, ǫ) be a coalgebra coassociative with counit. We define ∆ 2 by T 2,3 • ∆ ⊗ ∆ where T 2,3 : C ⊗4 → C ⊗4 is the flip between the 2nd and the 3rd component

T 2,3 (x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ) = x 1 ⊗ x 3 ⊗ x 2 ⊗ x 4 (118) a) Show that (C ⊗ C, ∆ 2 , ǫ ⊗ ǫ) (with ǫ ⊗ ǫ(x ⊗ y) = ǫ(x)ǫ(y)) is coassociative coalgebra with counit.
Let (H, µ, 1, ∆, ǫ, S) be a Hopf algebra. The convolution * here will be that constructed between the coalgebra (H ⊗ H, ∆ 2 , ǫ ⊗ ǫ) and the algebra (H, µ, 1). We consider the two elements ν i ∈ (Hom k (H ⊗ H, H), * ) defined by ν 1 = S • µ and ν 2 (x ⊗ y) = S(y)S(x). b) Show that the elements ν i are the convolutional inverses of µ. Deduce from this that S : H → H is an antimorphism of algebras.

Exercise 11.10 1) Let (B, * , 1, ∆, ǫ) be a bialgebra, we denote by B + the kernel of ǫ. a) Prove that B = B + ⊕ k.1 B . We denote I + the projection B → B + with respect to the preceding decomposition. b) Prove that, for every x ∈ B + , one can write

∆(x) = x ⊗ 1 + 1 ⊗ x + (1) (2)
x (1) ⊗ x (2) with x (i) ∈ B + (119)

2) Define for x ∈ B + ,

∆ + (x) = ∆(x) -(x ⊗ 1 + 1 ⊗ x) = (1) (2)
x b) Prove that (B * ) + is a subalgebra of (B, * ∆ ) and that its law is dual of ∆ + . c) Prove that the algebra (B * , * ∆ ) is obtained from (B * ) + , * ∆ + by adjunction of the unity ǫ.

3) The bialgebra is called locally finite if

(∀x ∈ B)(∃k ∈ N * )(∆ +(k) (x) = 0). ( 122
)
The projection I + being as above, show that, in case B is locally finite, ., 1 G , ∆, ǫ, S) be the Hopf algebra of G. a) Show that {(g -1)} g∈G-{1} is a basis of H + (defined as above) and that ∆ + (g -1) = (g -1) ⊗ (g -1). b) Show that, if G = {1}, H + is not locally finite, but H admits an antipode.

2) Prove that, if the coproduct of H is graded (i.e. there exists a decomposition H = ⊕ n∈N H n with ∆(H n ) ⊂ a+b=n H a ⊗ H b ) and H 0 = k.1 H , then the comultiplication is locally finite.

3) Define the degree of a labelled diagram as its number of edges and LDIAG n as the vector space generated by the diagrams of degree n and check that we satisfy the conditions of exercise (11.10) question 5.

Exercise 11.12 1) Show that, in order that a family (λ k i,j ) i,j,k∈I be the family of structure constants of some algebra it is necessary and sufficient that (∀(i, j) ∈ I 2 ) (λ k i,j ) k∈I is finitely supported (125)

2) Similarly show that in order that a family (λ j,k i ) i,j,k∈I be the family of structure constants of some coalgebra it is necessary and sufficient that (∀i ∈ I) (λ j,k i ) (j,k)∈I 2 is finitely supported (126)

3) Give examples of mappings λ : I 3 → k such that the corresponding families satisfy i) (125) and (126)

ii) (125) and not (126)

iii) (126) and not (125) iv) none of (125) and (126)

4)

Give further examples such as those in 3) i-iii but now defining associative (resp. coassociative) multiplications (resp. comultiplications).

12. APPENDIX

Function spaces

Throughout the text, we use the basic constructions of set theory and algebra (see [START_REF] Bourbaki | Theory of sets[END_REF][START_REF] Bourbaki | Algebra, chapter 1-III[END_REF]). The set of mappings between two sets X and Y is denoted by Y X . Thus if k is a field

k X = {f : X -→ k} (127)
the vector space of all functions defined on X with values in k. For each function f ∈ k X , we call the "support of f " the set of points x ∈ X such that f (x) is not zero + .

supp(f ) = {x ∈ X : f (x) = 0} (128) the set of functions with finite support is a vector subspace of k X which is denoted by k (X) .

An interesting extension of this notion to other sets of coefficients is the combinatorial notion of (finite) multisets.

Recall that a multiset is a (set with repetitions) [START_REF] Kreimer | On the Hopf algebra structure of pertubative quantum field theories[END_REF]. For example, the first multisets with elements from {a, b} are {}, {a}, {b}, {a, a}, {a, b}, {b, b}, {a, a, a}, {a, a, b}, {a, b, b}, {b, b, b}, {a, a, a, a}, {a, a, a, b}, {a, a, b, b}, {a, b, b, b}, {b, b, b, b},

• • • . (129)
A multiset with elements in X is then described equivalently by a multiplicity function α : X → N with finite support. The support of such a mapping is defined as in (128) and the set of finite multiplicity functions will be denoted by N (X) (see below the free commutative monoid (12.4)). For example, the multiplicity functions {a, b} → N corresponding to the multisets given in http://en.wikipedia.org/wiki/Monoid Definition 12.3 (Free Monoid) The free monoid of alphabet X is the set of strings x 1 x 2 • • • x n with letters x i ∈ X (comprising the empty string). This set is denoted X * , its law is the concatenation and its neutral element is the empty string.

It is easily seen that this monoid is free in the following sense. For any "set-theoretical" mapping φ : X → M, where (M, * ) is a monoid, φ can be extended to strings so that

X φ / / can ! ! C C C C C C C C M X * φ O O (132)
Definition 12.4 (Free Commutative Monoid) The free commutative monoid of the alphabet X is the set of monomials X α (α ∈ N (X) ). This set is denoted by MON(X) and its law is the multiplication of monomials

X α X β = X α+β (133)
It is easily seen that this monoid is free in the following sense. For any "set-theoretical" mapping φ : X → M, where (M, * ) is a commutative monoid, φ can be extended to monomials so that

X φ / / can % % J J J J J J J J J J M MON(X) φ O O (134)
An interesting application of the free monoid is the explicit construction of a monoid defined "by generators and relations". Let X be a set (of generators) and R = (u i , v i ) i∈I a family of pairs of words, then one can construct explicitely the smallest (i.e. the intersection of) congruence ≡ R for which (∀i ∈ I)(u i ≡ v i ).

Example 2 .

 2 -A second example is given, on the alphabet A = {a, b} by ∆(a) = a ⊗ b; ∆(b) = b ⊗ a then ∆(w) = w ⊗ w where w stands for the word w with a (resp. b) changed in b (resp. a)

  (12.2) and diagram (137))M(A, ϑ) = A; (xy = yx) (x,y)∈ϑ Mon .

  The spaces V * and V are in duality byp, ψ = p(ψ)(53)Now, if one has a representation (on the left) of A on V , one gets a representation on the right on V * by p.a, ψ = p, a.ψ (54) If we want to have the action of A on the left again, one should use an anti-morphism α : A -→ A that is α ∈ End k (A) such that, for all x, y ∈ A α(xy) = α(y)α(x).

7. Hopf algebras and partition functions 7 . 1 .

 71 Partition Function Integrand Consider the Partition Function Z of a Quantum Statistical Mechanical System Z = T r exp(-βH)

Fig 2 .

 2 Fig 2. -Graphs for B(n), n = 1, 2, 3.

4 .) 8 .

 48 The comultiplication ∆ : L Bell → L Bell ⊗ L Bell is defined by ∆(e) = e ⊗ e (unit e, the empty box) ∆(x) = x ⊗ e + e ⊗ x (generator x) ∆(AB) = ∆(A)∆(B) otherwise so that ∆ is an algebra homomorphism. (76The case of two modes Let us consider an hamiltonian on two modes H(a, a + , b, b + ), with [a, a + ] = 1 [b, b + ] = 1 [a ǫ 1 , b ǫ 2 ] = 0, ǫ i being + or empty (4 relations)

Note 8 . 1

 81 is the number of white spots (resp. black spots) of degree i (i lines connected to the spot) and mult(d) is the number of pairs of unordered partitions of [1 • • • |d|] (here |d| = |α(d)| = |β(d)| is the number of lines of d) with associated diagram d. The diagrams as well as the product formula were introduced in [3].

  that, if n is minimal in (94), the families of functions f the mapping Rep k (M) → Rep k (M) ⊗ Rep k (M) defined by f → defines a structure of coassociative coalgebra on Rep k (M) Has it a co-unit ? We denote by ∆ the compultiplication contructed above. 4) Show that (Rep k (M), ., 1, ∆, ǫ 1 M ) (with 1 the constant-valued function equal to 1 on M and ǫ the Dirac measure f → f (1 M )) is a bialgebra.

  ) b) Prove that ǫ(A) = 1 =⇒ |supp(α)| = 1 (106) and, thus, in this condition, A = [M] (a single matrix). c) Deduce from (a) and (b) that the set of invertible elements of N[M n ] KS is exactly the unitary group U(n). Exercise 11.4 Let (M, * , 1 M ) be a monoid, ≡ an equivalence relation on M and Cl : M → M/ ≡ the class function (which, to every element of M associates its class Cl(x)). a) Suppose that there is an (internal) law ⊥ on M/ ≡ such that Cl is a morphism i.e. one has (∀x, y ∈ M)(Cl(x * y) = Cl(x) ⊥ Cl(y))

1 )

 1 ⊗ x (2) (120) a) Check that (B + , ∆ + ) is a coassociative coalgebra. Define (B * ) + = {f ∈ B * |f (1) = 0}(121)

(

  ∀x ∈ B)(∃N ∈ N * )(∀k ≥ N)((I + ) k (x) is an antipode for B. Exercise 11.11 1) Let G be a group and H = (C[G],

  (130) are, in the same order (we characterize α by the pair (α(a), α(b))) (0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3), (4, 0),[START_REF] Bender | Quantum field theory of partitions[END_REF][START_REF] Solomon | Hopf Algebras[END_REF],[START_REF] Bayen | Deformation and Quantization[END_REF][START_REF] Bayen | Deformation and Quantization[END_REF],[START_REF] Solomon | Hopf Algebras[END_REF][START_REF] Bender | Quantum field theory of partitions[END_REF], (0, 4), • • • (130) 12.2. Basic structures Definition 12.1 (Semigroup) A semigroup (S, * ) is a set S endowed with a closed binary operation * satisfying an associative law, this means that, for all x, y, z ∈ S one has x * (y * z) = (x * y) * z. http://en.wikipedia.org/wiki/Semigroup Definition 12.2 (Monoid) A monoid (M, * ) is a semigroup which possesses a neutral element, i.e. an element e ∈ M such that, for all x ∈ M: e * x = x * e = x. (131) Such an element, if it exists is unique. The neutral element is often denoted 1 M .

  Show that the multisets of M n are exactly the elements M ∈Mn λ M [M] (here we note [M] the image of M ∈ M n in the algebra R[M n ] in order to forbid matrix addition) of the algebra R[M n ] such that

	E 12 ,	1 (2)	E 21 ,	1 (2)	E 22 )	(102)
	compute A * A and check that it has (non-zero) repeated elements and thus corresponds to a multiset (see appendix).
	b)

† As usual, Y X is the set of all mappings from X to Y , see appendix.

+ In integration theory, the support of a function is the closure of what we define as the (algebraic) support.

Let say that two words U, V ∈ X * are "related" by ≡ R if there is a chain of replacements of the type pu i s → pv i s or pv i s → pu i s p, s ∈ X * leading from U to V . Formally, there exists a chain

such that for each j < n U j = p j Aq j ; U j+1 = p j Bq j with (A, B) = (u i , v i ) or (B, A) = (u i , v i ) for some i (depending on j. One can show that the constructed ≡ R is a congruence (see exercise (108)) and we define

as the quotient X * / ≡ R . This monoid has the following property : if φX * → M is a morphism (of monoids) such that, for all i ∈ I one has φ(

Definition 12.5 (Group) A group (G, * ) is a monoid such that for each x ∈ G there exists y such that

For fixed x such an element is unique and is usually denoted by x -1 and called the inverse of x.

The algebra (k[M], * ) is an AAU.

Each m ∈ M may be identified with its characteristic function (i.e. the Dirac function δ m with value 1 at m and 0 elsewhere). These functions form a basis of k[M] and then, every f ∈ k[M] can be written as a finite sum f = w f (w)w. Through this identification the unity of M and k[M] coincide. The algebra of a monoid solves the following univeral problem. Let M be a monoid and j : M → k[M] the embedding described above. For any AAU A and any morphism of monoids φ : M → A ((A, .) is a monoid), one has an unique factorization

where φ is a morphism of AAU. Likewise, the enveloping algebra U k (G) of a Lie algebra G with the canonical mapping can : U k (G) → G is the solution of a universal problem. The specifications are the following where φ is a morphism of AAU.


Benjamin Merkel
email: merkel.benjamin@gmail.com

Sébastien Descamps

Nigel G Yoccoz

Jóhannis Danielsen

Francis Daunt

Kjell E Erikstad

Aleksey V Ezhov

David Grémillet

Maria Gavrilo

Svein-Håkon Lorentsen

Tone K Reiertsen

Harald Steen

Geir H Systad

Þorkell Lindberg Þórarinsson

Sarah Wanless

Hallvard Strøm

Population ecology Earlier colony arrival but no trend in hatching timing in two congeneric seabirds

Keywords: behaviour, ecology guillemots, murres, pre-laying period, timing of egg-laying, Uria aalge, Uria lomvia

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Timing of life-history events such as reproduction is predicted to have evolved to optimally use temporally favourable conditions in seasonal systems [START_REF] Varpe | Life history adaptations to seasonality[END_REF]. Breeding phenology is a key adaptation with direct consequences on reproductive success and population dynamics [START_REF] Youngflesh | Circumpolar analysis of the Adélie penguin reveals the importance of environmental variability in phenological mismatch[END_REF][START_REF] Mclean | Predicting when climate-driven phenotypic change affects population dynamics[END_REF]. Rapid climate change has led to an © 2019 The Author(s) Published by the Royal Society. All rights reserved. advancement of the annual cycle in many organisms in temperate and polar regions, while species that have not adjusted to climate change seem to be more prone to population declines [START_REF] Walther | Ecological responses to recent climate change[END_REF][START_REF] Møller | Populations of migratory bird species that did not show a phenological response to climate change are declining[END_REF]. In seabirds, the timing of egg-laying has been shown to be insensitive to changing climatic conditions globally, highlighting the vulnerability of this group to mismatches with lower-trophic-level resources [START_REF] Keogan | Global phenological insensitivity to shifting ocean temperatures among seabirds[END_REF]. Yet, spring arrival at the colony, and the pre-laying period-the time between arrival at the colony and egg-laying-are also important and rarely considered components affecting breeding success. This period allows birds to establish and defend nest sites [START_REF] Kokko | Competition for breeding sites and site-dependent population regulation in a highly colonial seabird, the common guillemot Uria aalge[END_REF], build up body condition [START_REF] Bêty | Body condition, migration, and timing of reproduction in snow geese: a test of the condition-dependent model of optimal clutch size[END_REF][START_REF] Sénéchal | Do purely capital layers exist among flying birds? Evidence of exogenous contribution to arctic-nesting common eider eggs[END_REF] and mate [START_REF] Birkhead | Extra-pair matings and mate guarding in the common murre Uria aalge[END_REF], which often starts months before egg-laying [START_REF] Harris | Dramatic changes in the return date of guillemots Uria aalge to colonies in Shetland, 1962-2005[END_REF][START_REF] Quillfeldt | Behavioural plasticity in the early breeding season of pelagic seabirds-a case study of thin-billed prions from two oceans[END_REF].

Here, we took advantage of a large tracking dataset, enabling us to determine arrival dates in two seabird species, across 9 years (2009-2018) and 14 colonies across a large latitudinal gradient (62°N-79°N), to test if arrival date does not exhibit any trend across years, similar to timing of egglaying [START_REF] Keogan | Global phenological insensitivity to shifting ocean temperatures among seabirds[END_REF]. These data were available for two colonial, congeneric species, the common (hereafter COGU, Uria aalge) and Brünnich's guillemot (hereafter BRGU, Uria lomvia). These species are long-distance migrants [START_REF] Frederiksen | Migration and wintering of a declining seabird, the thick-billed murre Uria lomvia, on an ocean basin scale: conservation implications[END_REF][START_REF] Tranquilla | Multiple-colony winter habitat use by murres Uria spp. in the Northwest Atlantic Ocean: implications for marine risk assessment[END_REF][START_REF] Linnebjerg | Non-breeding areas of three sympatric auk species breeding in three Icelandic colonies[END_REF], have similar morphology and life history [START_REF] Benowitz-Fredericks | Benefits and costs of rapid growth in common murre chicks Uria aalge[END_REF][START_REF] Gaston | Bird families of the world. The Auks Alcidae[END_REF], and exhibit no trend in breeding phenology [START_REF] Descamps | Diverging phenological responses of Arctic seabirds to an earlier spring[END_REF], but contrasting population trends [START_REF]Seabird population trends and causes of change: 1986-2015 report[END_REF][START_REF] Fauchald | The status and trends of seabirds breeding in Norway and Svalbard[END_REF][START_REF] Garðarsson | The numbers of large auks on the cliffs of Iceland in 2006-2008[END_REF]. Their arrival date is hypothesized to be driven by the timing of food availability in the vicinity of the colony [START_REF] Taylor | Earlier colony attendance by Guillemots and Razorbills[END_REF][START_REF] Harris | Fall colony attendance and breeding success in the common murre[END_REF], which can be roughly approximated by latitude [START_REF] Burr | Later at higher latitudes: largescale variability in seabird breeding timing and synchronicity[END_REF], or by colony size through increasing pressure on nest site defence displayed as longer pre-laying periods in larger colonies [START_REF] Harris | Dramatic changes in the return date of guillemots Uria aalge to colonies in Shetland, 1962-2005[END_REF][START_REF] Birkhead | Attendance patterns of guillemots Uria aalge at breeding colonies on Skomer Island[END_REF][START_REF] Hatchwell | Intraspecific variation in extrapair copulation and mate defence in common guillemots Uria aalge[END_REF]. We tested the hypothesis that the arrival date is without trend across years, similar to the egg-laying date. Furthermore, we examined if arrival date is delayed with latitude, similar to the timing of egg-laying [START_REF] Burr | Later at higher latitudes: largescale variability in seabird breeding timing and synchronicity[END_REF], or determined by colony size due to pressure on nest site defence.

Material and methods (a) Data acquisition

The date of first arrival at the colony for each colony and species was estimated using salt water immersion data recorded by light-level geolocators deployed on adult breeders. The arrival date was here defined as the date when the pre-laying period commences. It was identified as the date when the majority of tracked individuals attended the colony for the first time after the nonbreeding period, using the assumption that first arrival back at the colony is synchronized and independent of sex in guillemots [START_REF] Hatchwell | Intraspecific variation in extrapair copulation and mate defence in common guillemots Uria aalge[END_REF][START_REF] Gaston | The thick-billed murres of Prince Leopold Island[END_REF][START_REF] Wilhelm | Influence of cyclic pre-lay attendance on synchronous breeding in common murres[END_REF] (details in the electronic supplementary material). Using a colony-wide first arrival date rather than individual arrival dates resulted in more robust results due to limitations in logger data resolution and accuracy. Tracking data were available from 14 colonies (figure 1a), for 1-8 years (in the period 2009-2018) [START_REF] Merkel | Data from: Earlier colony arrival but no trend in hatching timing in two congeneric seabirds (Uria spp.) across the North Atlantic[END_REF]. BRGU and COGU breed sympatrically at five of these colonies. Three instances of estimated arrival dates could be validated with available time-lapse camera data at two colonies (electronic supplementary material, figure S1). To estimate prelaying duration as well as temporal changes in phenology, we royalsocietypublishing.org/journal/rsbl Biol. Lett. 15: 20190634 gathered annual measures of breeding timing which were available as population-level mean hatching dates at 12 colonies (details in the electronic supplementary material) for 1-7 years (in the period 2009-2018) [START_REF] Burr | Later at higher latitudes: largescale variability in seabird breeding timing and synchronicity[END_REF][START_REF] Barrett | Key-site monitoring in Norway[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2012, including Svalbard and Jan Mayen[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2013, including Svalbard and Jan Mayen[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2014, including Svalbard and Jan Mayen[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2015, including Svalbard and Jan Mayen[END_REF][START_REF] Anker-Nilssen | Key-site monitoring in Norway 2016, including Svalbard and Jan Mayen[END_REF][START_REF] Anker-Nilssen | Key-site monitoring in Norway 2017, including Svalbard and Jan Mayen[END_REF][START_REF] Kolbeinsson | Vöktun bjargfuglastofna 2018 -Framvinduskýrsla[END_REF]. To assess the potential consequences of variable arrival dates on reproductive success, we used annual breeding success for which data were available from five colonies (details in the electronic supplementary material) for 4-6 years (in the period 2010-2017) [START_REF] Barrett | Key-site monitoring in Norway[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2012, including Svalbard and Jan Mayen[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2013, including Svalbard and Jan Mayen[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2014, including Svalbard and Jan Mayen[END_REF][START_REF] Barrett | Key-site monitoring in Norway 2015, including Svalbard and Jan Mayen[END_REF][START_REF] Anker-Nilssen | Key-site monitoring in Norway 2016, including Svalbard and Jan Mayen[END_REF][START_REF] Anker-Nilssen | Key-site monitoring in Norway 2017, including Svalbard and Jan Mayen[END_REF][START_REF] Kolbeinsson | Vöktun bjargfuglastofna 2018 -Framvinduskýrsla[END_REF].

(b) Data analysis (i) Temporal trends in breeding phenology and their consequences

Colony-and species-specific inter-annual variation in arrival dates was quantified as standard deviation (SD) from mean arrival timing. To test if arrival date changes with year, we applied a linear mixed-effect model (LME, package lme4) with relative arrival dates (mean = 0) as response variable (n = 79), year and species as fixed effects and id (as combination of colony and species) as random intercept. The same model was applied on a subset of data for which mean hatching date data were available (n = 40). Using this subset, we applied the same fixed and random effects to relative pre-laying duration as well as relative mean hatching date as response variables in order to assess if guillemot hatching timing and pre-laying duration have changed over time. Most parsimonious models were selected using the Akaike information criterion [START_REF] Pinheiro | Mixed-effects models in S and S-PLUS[END_REF], resulting in all instances in removal of species and its interaction with year as predictor variables. We calculated the percentage of variance explained by the fixed effects (marginal R 2 ) and fixed and random effects (conditional R 2 ; [START_REF] Nakagawa | A general and simple method for obtaining R2 from generalized linear mixed-effects models[END_REF]). In order to assess if a large-scale factor is driving temporal trends in arrival date, we assessed temporal synchrony as mean correlation of relative arrival dates between colonies using the msynch function ( package ncf [START_REF] Bjørnstad | Spatial population dynamics: analyzing patterns and processes of population synchrony[END_REF]). To test if potential temporal trends in arrival date had an effect on reproductive output, we applied an LME with standardized breeding success (SD = 1, mean = 0) as response variable, relative arrival date as fixed effect and id as random intercept (n = 33).

(ii) Effect of latitude and colony size on arrival date

To test for the effect of latitude on arrival date at the colony, we applied a linear model with mean species-and colony-specific arrival date as the response variable (n = 19) and latitude and species and their interaction as predictors. Furthermore, if latitude drives arrival date, we would expect that colonies close to each other would exhibit similar arrival timing. Hence, we used a Mantel correlation test with 1000 permutations ( package ade4) to test if spatial proximity can explain the mean arrival date in either species. Alternatively, to test if arrival date and consequently pre-laying duration can be instead linked to colony size, we applied a linear model with mean species-and colony-specific pre-laying duration as the response variable (n = 15) and colony size on the log-scale and species as predictors. Population counts are taken from a similar time period to account for the contrasting population trends (electronic supplementary material, table S1).

To account for collinearity, we also tested latitude against colony size, but found no overall latitudinal trend (linear model, β latitude = -0.10 with standard error (SE) = 0.10, adj. R 2 ≤ -0.01). R (v. 3.5.1, [START_REF]R: a language and environment for statistical computing[END_REF]) was used for all statistical analyses.

Results

(a) Timing of colony arrival

Annual arrival dates varied between 28 January and 18 April with considerable variation across the Northeast Atlantic (figure 1b). Most of this variation is found among colonies (SD = 21.6 and 16.2 days for COGU and BRGU, respectively, electronic supplementary material, figure S1) and species (SD = 12.8 days across sympatric colonies), while colony-and species-specific inter-annual variation was significantly smaller (mean SD = 7.8 and 4.9 days for COGU and BRGU, respectively).

(b) Temporal variability in breeding phenology and its consequences

Timing of hatching in guillemots showed no trend over time (β year = -0.17 with SE = 0.23, marg. R 2 = 0.01, cond. R 2 = 0.01; figure 2c). By contrast, arrival date at the colony advanced by 1.4 days/year irrespective of species (full dataset: β year = -1.4 with SE = 0.28, marg. R 2 = 0.24, cond. R 2 = 0.24; subset with available mean hatching data: β year = -1.7 with SE = 0.35, marg. R 2 = 0.39, cond. R 2 = 0.39; figure 2a). This was also visible as prolonged pre-laying duration (β year = 1.4 with SE = 0.40, marg. R 2 = 0.23, cond. R 2 = 0.23; figure 2b) as arrival date and pre-laying duration were highly and negatively correlated (-0.86). Colony arrival dates did not display synchrony among each other for either species (COGU: mean correlation = 0.15 with 95% confidence interval (CI) = -0.34-0.55 and BRGU: 0.09 with CI = -0.56-0.71).

No consequence of an advancing arrival date was detectable in exhibited breeding success for either species (β std. arrival = -0.005 with SE = 0.02, marg. R 2 = <0.01, cond. R 2 = <0.01; figure 2d).

(c) Does latitude or colony size predict the arrival date?

Mean arrival date at the colony could not be explained by latitude and the two species exhibited opposite trends (β latitude BRGU = 1.63 with SE = 1.24 and β latitude * COGU = -2.73 with SE = 2.19, adj. R 2 = 0.23; figure 1b). Similarly, there was weak evidence for an effect of proximity on arrival dates for COGUs (Mantel correlation = 0.19, p = 0.14), but somewhat stronger evidence in BRGUs (Mantel correlation = 0.29, p = 0.034). Contrastingly, pre-laying duration showed substantial variability among colonies (mean = 75 days, SD = 19, range = 49-102) and was highly correlated with colony size (β log(size) = 6.96 with SE = 0.97, adj. R 2 = 0.82; figure 1c).

Discussion

The main findings of our study are that timing of first arrival at the colony of both guillemot species and all colonies was highly variable and advanced through time despite no visible trend in mean hatching date. This advancement had apparently no effect on guillemot average breeding success. Furthermore, the duration of the pre-laying period and hence timing of arrival is not determined by latitude, but is better explained by the size of the colony, being longer in large colonies.

Theoretically, the minimum pre-laying duration required in guillemots is 5 days, as females undertake a 4 day long pre-laying exodus away from the colony [START_REF] Birkhead | Egg formation and the pre-laying period of the common guillemot Una aalge[END_REF]. Yolk formation (usually 14-15 days [START_REF] Birkhead | Egg formation and the pre-laying period of the common guillemot Una aalge[END_REF]) could also occur away from the colony and fertilization occurs very soon after ovulation, which in turn occurs 24 h before the egg is laid [START_REF] Birkhead | Extra-pair matings and mate guarding in the common murre Uria aalge[END_REF]. So, copulation right before the pre-laying exodus should be sufficient. Nonetheless, here we identified extensive pre-laying periods of more than one and up to several months with large variability between colonies and species. In an extreme case of a population further south, most breeding birds arrive back royalsocietypublishing.org/journal/rsbl Biol. Lett. 15: 20190634 at the colony already in the autumn and in at least some years birds attend the breeding sites throughout the winter [START_REF] Harris | Dramatic changes in the return date of guillemots Uria aalge to colonies in Shetland, 1962-2005[END_REF][START_REF] Harris | Breeding status and sex of common murres (Uria aalge) at a colony in Autumn[END_REF]. This variability may have costs and benefits associated with it. During the pre-laying period prospective breeders attend the colonies at regular intervals [START_REF] Hatchwell | Intraspecific variation in extrapair copulation and mate defence in common guillemots Uria aalge[END_REF][START_REF] Gaston | The thick-billed murres of Prince Leopold Island[END_REF][START_REF] Wilhelm | Influence of cyclic pre-lay attendance on synchronous breeding in common murres[END_REF] which restricts them to quasi-central place foraging. This, in turn, limits their available prey options and could even lead to local depletion of food resources before spring bloom at large colonies [START_REF] Ashmole | The regulation of numbers of tropical oceanic birds[END_REF], decreasing their body condition and potentially breeding probability prior to breeding. Alternatively, early return to the breeding sites might help secure nesting sites, mating partners and facilitate courtship [START_REF] Harris | Fall colony attendance and breeding success in the common murre[END_REF], or it might be a response to unfavourable conditions experienced by these migrants during the end of their non-breeding period, resulting in an earlier return to the colony.

We showed that colony arrival date advanced in both the Brünnich's and common guillemot across the study area, while their timing of hatching did not display any trend as shown previously in seabirds globally [START_REF] Keogan | Global phenological insensitivity to shifting ocean temperatures among seabirds[END_REF] and for alcids in the Atlantic and Pacific [START_REF] Descamps | Diverging phenological responses of Arctic seabirds to an earlier spring[END_REF]. Contrary to these previous studies, concluding that breeding phenology is insensitive to short-term climatic change, we identified a clear trend in arrival dates across both species studied. This advancement resulted in an increasing pre-laying duration as mean hatching date did not advance, suggesting that part of breeding in these seabirds is indeed sensitive to changing conditions, although we cannot derive conclusions regarding the process driving this phenomenon or if it is an adaption to a changing environment. A potential explanation could be that the cue used to time arrival across the North Atlantic is changing as has been shown in some passerine species [START_REF] Marra | The influence of climate on the timing and rate of spring bird migration[END_REF], but could not be demonstrated in others [START_REF] Both | Adjustment to climate change is constrained by arrival date in a long-distance migrant bird[END_REF][START_REF] Fraser | A trans-hemispheric migratory songbird does not advance spring schedules or increase migration rate in response to record-setting temperatures at breeding sites[END_REF].

Although overall timing in both species exhibits the same trend, arrival time series were not synchronized between species and colonies. This indicates that short-term fluctuations in arrival date were not parallel through time among species and/or colonies, which suggests the interaction between large-scale environmental trends acting on the entire species combined with more local features. However, environmental conditions, although exhibiting the same trend, do not change homogeneously across the genus' range [START_REF]Climate change 2013: the physical science basis. Contribution of working group I to the fifth assessment report of the intergovernmental panel on climate change[END_REF], which encompasses most of the North Atlantic for these species breeding within the study area [START_REF] Frederiksen | Migration and wintering of a declining seabird, the thick-billed murre Uria lomvia, on an ocean basin scale: conservation implications[END_REF][START_REF] Tranquilla | Multiple-colony winter habitat use by murres Uria spp. in the Northwest Atlantic Ocean: implications for marine risk assessment[END_REF][START_REF] Linnebjerg | Non-breeding areas of three sympatric auk species breeding in three Icelandic colonies[END_REF]. Hence, synchrony is not necessarily expected. As of now, we could not detect any immediate consequences of advancing arrival dates on population-wide reproductive success. As we used adult breeders to estimate arrival times, we cannot make any inference of the potential effect of advancing arrival dates on breeding propensity. Not all birds breed every year [START_REF] Harris | Survival and nonbreeding of adult common guillemots Una aalge[END_REF][START_REF] Reed | Skipped breeding in common guillemots in a changing climate: restraint or constraint?[END_REF] and the egg laying and hatching dates as well as the recorded breeding success may reflect only individuals with sufficient body condition, i.e. the ones that managed to get enough energy during the pre-laying period in order to breed [START_REF] Bêty | Body condition, migration, and timing of reproduction in snow geese: a test of the condition-dependent model of optimal clutch size[END_REF].

Pre-laying duration and hence arrival timing at the colony could be linked with colony size [START_REF] Harris | Dramatic changes in the return date of guillemots Uria aalge to colonies in Shetland, 1962-2005[END_REF][START_REF] Birkhead | Attendance patterns of guillemots Uria aalge at breeding colonies on Skomer Island[END_REF][START_REF] Hatchwell | Intraspecific variation in extrapair copulation and mate defence in common guillemots Uria aalge[END_REF] rather than latitude. This could explain the displayed large-scale variability in arrival timings between colonies as well as the lack of synchronicity between time series. Although guillemots typically show high nest site fidelity, site changes are documented which usually increase nest site quality for the usurper and decrease it for the usurped [START_REF] Jeschke | How partnerships end in guillemots Uria aalge: chance events, adaptive change, or forced divorce?[END_REF] underlining the importance of nest site defence as a potential driver of arrival date resulting in the pressure to arrive earlier in larger colonies [START_REF] Harris | Dramatic changes in the return date of guillemots Uria aalge to colonies in Shetland, 1962-2005[END_REF][START_REF] Birkhead | Attendance patterns of guillemots Uria aalge at breeding colonies on Skomer Island[END_REF][START_REF] Hatchwell | Intraspecific variation in extrapair copulation and mate defence in common guillemots Uria aalge[END_REF]. But, the influence of environmental conditions on arrival timing cannot be ruled out, as unfavourable weather has already been shown to affect pre-laying colony attendance in BRGU [START_REF] Gaston | The thick-billed murres of Prince Leopold Island[END_REF] although the same could not yet be shown for arrival timing. royalsocietypublishing.org/journal/rsbl Biol. Lett. 15: 20190634

Our large-scale approach highlights the extent and importance of the pre-laying period in contributing to the challenges faced by colonial breeders in a changing environment. The advancing trend in arrival dates elucidates that not all parts of breeding phenology in seabirds are insensitive to change across years, although we cannot make inferences if this change is adaptive or not.

Ethics. All animal research was conducted in accordance with relevant in country protocols and were granted by: the County Governor of Nordland, the County Governor of Finnmark, the Governor of Svalbard, the Norwegian Food Safety Authority (FOTS ID: 6291, 8482, 15603), the National Museum of the Faroe Islands and the Icelandic Institute of Natural History.

Figure 1 .

 1 Figure 1. (a) The colony locations of COGU (red) and BRGU (blue) included in the study. (b) The relationship between mean arrival date and latitude, while (c) shows the correlation of mean pre-laying duration and colony size. Colonies with less certain pre-laying duration estimates are indicated as open circles. Bands in (b) and (c) indicate 95% CIs for predicted values.

Figure 2 .

 2 Figure 2. Temporal trends in arrival dates at the colony (a), pre-laying duration (b) and mean hatching date (c). The dashed line in (a) represents linear mixedeffect model predictions for the subset of data for which hatching timing information was available (squares), while the solid line in (a) illustrates the same model prediction for arrival date using the entire dataset (squares and dots). (d) The relationship between advancing arrival date and breeding success. Bands in all panels indicate bootstrapped 95% CIs for predicted values calculated using the bootMer function with 1000 simulations (package lme4). Red and blue symbols represent COGU and BRGU, respectively.

Acknowledgements. We thank Børge Moe, Hálfdán Helgi Helgason and Vegard Sandøy Bråthen for logistical support within SEATRACK as well as Mike Harris, Stephen Votier and Tim Guilford for insightful comments which improved the manuscript. This work would not have been possible without the combined effort and long-term engagement of many researchers as well as numerous field assistants all across the Northeast Atlantic.

Data accessibility. Data are available through the Norwegian Polar Data Centre (doi:10.21334/npolar.2019.55169600), SEAPOP reports (www. seapop.no/no/publikasjoner/) and NNA reports (nna.is/wp-content/ uploads/2018/12/NNA1804-Bjargfuglavoktun2018_framvinduskyrsla2. pdf).

Authors' contributions. B.M. conceived the study, conducted the data analysis and drafted the manuscript; S.D., N.G.Y. and H.Str. supervised the study; all authors provided data, contributed to article drafts, approved the final version of this manuscript and agree to be held accountable for the content.

Funding. Funding for this study was provided by the Norwegian Ministry for Climate and the Environment, the Norwegian Ministry of Foreign Affairs and the Norwegian Oil and Gas Association through the SEATRACK project (www.seapop.no/en/seatrack) as well as from the Research Council of Norway ( project 216547), TOTAL E&P Norway and the TOTAL Foundation and the UK Natural Environment Research Council's National Capability.

Competing interests. We declare we have no competing interests.