L Foissy
email: loic.foissy@univ-reims.fr

Free and cofree Hopf algebras

Keywords: Free and cofree Hopf algebras; self-duality, AMS CLASSIFICATION, 16W30

We first prove that a graded, connected, free and cofree Hopf algebra is always self-dual; then that two graded, connected, free and cofree Hopf algebras are isomorphic if, and only if, they have the same Poincaré-Hilbert formal series. If the characteristic of the base field is zero, we prove that the Lie algebra of the primitive elements of such an object is free, and we deduce a characterization of the formal series of free and cofree Hopf algebras by a condition of growth of the coefficients. We finally show that two graded, connected, free and cofree Hopf algebras are isomorphic as (non graded) Hopf algebras if, and only if, the Lie algebra of their primitive elements have the same number of generators.

Introduction

The theory of combinatorial Hopf algebras has known a great extension in the last decade. It turns out that an important part of the Hopf algebras studied in this theory are both free and cofree, for example:

1. The Hopf algebra FQSym of free quasi-symmetric functions [START_REF] Malvenuto | Produits et coproduits des fonctions quasi-symétriques et de l'algèbre des descentes[END_REF][START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF][START_REF] Poirier | Algèbres de Hopf de tableaux[END_REF], also known as the Malvenuto-Reutenauer Hopf algebra.

2. The Hopf algebra PQSym of parking functions [START_REF] Novelli | Hopf algebras and dendriform structures arising from parking functions[END_REF][START_REF]Parking functions and descent algebras[END_REF].

3. The Hopf algebra on set compositions, called P Π in [START_REF] Aguiar | Coxeter groups and Hopf algebras[END_REF] and NCQSym in [START_REF] Bergeron | The Hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and co-free[END_REF].

4. The isomorphic Hopf algebras RΠ and SΠ on pairs of permutations of [START_REF] Aguiar | Coxeter groups and Hopf algebras[END_REF].

5. The Loday-Ronco Hopf algebra H LR of planar binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF] and its dual YSym [START_REF] Aguiar | Structure of the Loday-Ronco Hopf algebra of trees[END_REF].

6. The Hopf algebras of planar rooted trees [START_REF]Les algèbres de Hopf des arbres enracinés décorés. II[END_REF][START_REF] Holtkamp | Comparison of Hopf algebras on trees[END_REF], also known as the non-commutative Connes-Kreimer Hopf algebra H N CK , and its decorated versions.

7. The Hopf algebra of double posets H DP [START_REF] Malvenuto | A self-dual Hopf algebra on double partially ordered sets[END_REF].

8. The Hopf algebra of ordered forests H o and its subalgebra of heap-ordered forests H ho [START_REF] Foissy | Ordered forests, permutations and iterated integrals[END_REF].

9. The free 2-As algebras [START_REF]On the structure of cofree Hopf algebras[END_REF].

10. The Hopf algebra of uniform block permutations H U BP [START_REF] Aguiar | The Hopf algebra of uniform block permutations[END_REF].

11. And, if the characteristic of the base field K is zero, the Hopf algebra K[X].

Note that the space of generators and the space of cogenerators are not the same in these examples, except for K[X].

It also turns out that certain of these objects are self-dual. The self-duality is proved by the construction of a more or less explicit pairing for FQSym, the Connes-Kreimer Hopf algebras, the Hopf algebra of posets and K[X]. In the case of PQSym or the Hopf algebra of ordered forests, the self-duality and the cofreeness is proved by the construction of an non-explicit isomorphism with a Connes-Kreimer Hopf algebra, using non-associative products and coproducts and a rigidity theorem [START_REF]Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF][START_REF]Ordered forests and parking functions[END_REF]. It can similarly be proved that the Hopf algebra of double posets is isomorphic to a Connes-Kreimer Hopf algebra. As a corollary, any two of these objects with the same formal series are isomorphic, and their Lie algebras of primitive elements are free if the characteristic of the base field is zero. Note that the self-duality of RΠ and SΠ and the freeness of their Lie algebras of primitive elements were not proved yet and are implied by theorem 5 and corollary 13 of the present text.

In this context, the following questions are natural:

1. Is a free and cofree Hopf algebra always self-dual? 2. Are two free and cofree Hopf algebras with the same formal series always isomorphic?

3. What can be said of the structure of the Lie algebra of the primitive elements of a free and cofree Hopf algebra?

We here give a positive answer to questions 1 and 2 and prove for question 3 that these Lie algebras are free if the characteristic of the base field is 0. We first prove that any free and cofree Hopf algebra H can be given a non-degenerate, symmetric Hopf pairing, so is self-dual. More precisely, if g is the Lie algebra of the primitive elements of H and H + is the augmentation ideal of H, then any non-degenerate symmetric pairing on the space of indecomposable primitive elements g g∩H +2 can be (not uniquely) extended to a non-degenerate, symmetric Hopf pairing on H (theorem 5). We then deduce that two free and cofree Hopf algebras H and H ′ are isomorphic as graded Hopf algebras if, and only if, H and H ′ have the same Poincaré-Hilbert formal series (theorem 8).

Restricting us to a base field of characteristic zero, we characterize the formal series of free and cofree Hopf algebras. We first prove that the Lie algebra g is free, answering question 3 (corollary 13). We deduce in proposition 14 relations between the coefficients of the following formal series:

R(h) = ∞ n=0 dim(H n )h n , P (h) = ∞ n=1 dim(g n )h n , S(h) = ∞ n=1 dim g g ∩ H +2 n h n .
Using non-commutative Connes-Kreimer Hopf algebras, we prove that the formal series S(h) can be arbitrarily chosen (corollary 17). As a consequence, the formal series of free and cofree Hopf algebras are characterized by growth conditions of the coefficients, expressed in corollary [START_REF]Parking functions and descent algebras[END_REF]. As the growth condition characterizing the formal series of non-commutative Connes-Kreimer Hopf algebras is distinct (theorem 21), this implies that there exists free and cofree Hopf algebras that are neither K[X] nor Connes-Kreimer Hopf algebras.

Let H and H ′ be two graded, connected, free and connected Hopf algebras. Are they isomorphic as (non-graded) Hopf algebras? In order to answer this question, we first refine their graduation into a bigraduation in the last section of this text.

Notations.

1. In the whole text, K is a commutative field of characteristic = 2. Any algebra, coalgebra, Hopf algebra. . . of the text will be taken over K.

2. If H is a Hopf algebra, we denote by H + its augmentation ideal and by P rim(H) or by g if there is no ambiguity the Lie algebra of its primitive elements. Moreover, H + inherits a coassociative, non counitary coproduct ∆ defined by

∆(x) = ∆(x) -x ⊗ 1 -1 ⊗ x for all x ∈ H + .
The square product H +2 of the ideal H + by itself is called the space of decomposable elements [START_REF] Milnor | On the structure of Hopf algebras[END_REF]; the quotients H + H +2 and g g∩H +2 are respectively called the space of indecomposable elements and of indecomposable primitive elements.

Aknowledgements. This work was partially supported by a PEPS.

1 Free and cofree Hopf algebras are self-dual

Hopf pairings

We first recall the following definition:

Definition 1 1. Let H, H ′ be two graded, connected Hopf algebras. A homogeneous Hopf pairing is a bilinear form -, -: H × H ′ -→ K such that: (a) For all x ∈ H, x ′ ∈ H ′ , x, 1 = ε(x) and 1, x ′ = ε(x ′ ). (b) For all x, y ∈ H, y ′ , z ′ ∈ H ′ , xy, z ′ = x ⊗ y, ∆(z ′ ) and x, y ′ z ′ = ∆(x), y ′ ⊗ z ′ . (c) If x, x ′ are homogeneous of different degrees, then x, x ′ = 0.
2. Let H be a graded, connected Hopf algebra. We shall say that H is self-dual if it can be given a non-degenerate Hopf pairing -, -: H × H -→ K.

Note. As all the Hopf pairings considered here are homogeneous, we shall simply write "Hopf pairings" for "homogeneous Hopf pairings" in this text.

Let -, -be any pairing on H × H ′ . It is a Hopf pairing if, and only if, the following map is a morphism of graded Hopf algebras:

H -→ H ′ * x -→ x, -,
where H ′ * is the graded dual of H ′ . Moreover, if the pairing is non-degenerate, then this map is an isomorphism. Conversely, any morphism of graded Hopf algebras φ : H -→ H ′ * gives a Hopf pairing, defined by x, x ′ = φ(x)(x ′ ). As a consequence, a graded, connected Hopf algebra H is self-dual in the sense of definition 1 if, and only if, it is isomorphic to H * as a graded Hopf algebra; moreover, symmetry of the pairing is equivalent to self-duality of the isomorphism.

Lemma 2 Let H, H ′ be two graded, connected Hopf algebras, and let -, -be a Hopf pairing on

H × H ′ . Let us fix n ≥ 1. If -, -|H k ×H ′ k is non-degenerate for all k < n, then in H ′ n , ((H +2 ) n ) ⊥ = P rim(H ′ ) n . Proof. Let z ∈ H ′ n . For any x ∈ H k , y ∈ H n-k , 1 ≤ k ≤ n -1: xy, z = x ⊗ y, ∆(z) = x ⊗ y, 1 ⊗ z + z ⊗ 1 + ∆(z) = ε(x) y, z + ε(y) x, z + x ⊗ y, ∆(z) = x ⊗ y, ∆(z) . If z is primitive, then ∆(z) = 0, so xy, z = 0 and z ∈ ((H +2 ) n ) ⊥ . Conversely, if z ∈ ((H +2 ) n ) ⊥ , then ∆(z) ∈ ((H + ⊗ H + ) n ) ⊥ .
As the pairing is non-degenerate in degree < n:

((H + ⊗ H + ) n ) ⊥ = n-1 k=1 H k ⊗ H n-k ⊥ = (0), so z is primitive. 2
As a consequence, if H is a graded, connected, self-dual Hopf algebra, any non-degenerate Hopf pairing on H induces a non-degenerate, homogeneous pairing on g g∩H +2 , where g is the Lie algebra P rim(H). This pairing will be called the induced pairing on g g∩H +2 .

Lemma 3 Let H be a graded, connected, self-dual Hopf algebra, with a symmetric, nondegenerate Hopf pairing -, -. Let us fix n ∈ N. Let h n be a complement of (g ∩ H +2 ) n in g n and let m n be a complement of (g ∩ H +2 ) n in H +2 . Then h n is non-isotropic, that is to say the restriction -, -|hn×hn is non-degenerate. There exists a complement w n of g n + H +2 n in H n , such that, in H n :

• w ⊥ n = w n ⊕ h n ⊕ m n and the restriction of the pairing to (g ∩ H +2 ) n × w n is non-degenerate. • h ⊥ n = (g ∩ H +2
) n ⊕ m n ⊕ w n and the restriction of the pairing to h n × h n is non-degenerate.

• m ⊥ n = (g∩H +2 ) n ⊕h n ⊕w n and the restriction of the pairing to m n ×m n is non-degenerate.

• ((g ∩ H +2 ) n ) ⊥ = (g ∩ H +2
) n ⊕ m n ⊕ h n and the restriction of the pairing to

w n × (g ∩ H +2 ) n is non-degenerate. Proof. By lemma 2, g n ∩ g ⊥ n = (g ∩ H +2 ) n and H +2 n ∩ (H +2 n ) ⊥ = (g ∩ H +2 ) n .
Hence, h n and m n are non-isotropic subspaces of H n . Moreover:

((g ∩ H +2 ) n ) ⊥ = g ⊥ n + ((H +2 ) n ) ⊥ = H +2 n + g n = (g ∩ H +2 ) n ⊕ m n ⊕ h n .
Let us choose any complement w n of g n + H +2 n in H n . As the pairing is non-degenerate:

dim(g n ) = dim(H n ) -dim(g ⊥ n ) dim(g n ) = dim(H n ) -dim(H +2 ) n dim((g ∩ H +2 ) n ) + dim(h n ) = dim(H n ) -dim((g ∩ H +2 ) n ) -dim(m n ) dim((g ∩ H +2 ) n ) + dim(h n ) = dim(h n ) + dim(w n ), so dim(w n ) = dim((g ∩ H +2 ) n ). Moreover, (g ∩ H +2 ) ⊥ n = g n ⊕ (H +2
) n by lemma 2, so w n ∩ ((g ∩ H +2 ) n ) ⊥ = (0) by choice of w n . Hence, the restriction of the pairing to (g ∩ H +2 ) n × w n is non-degenerate. We finally obtain a decomposition:

H n = (g ∩ H +2 ) n ⊕ m n ⊕ h n ⊕ w n .
Let us choose an adapted basis of H n : (x i ) i∈I ∪ (y j ) j∈J ∪ (z k ) k∈K ∪ (t i ) i∈I (we can choose the same set of indices for the bases of (g ∩ H +2 ) n and w n , as they have the same dimension). In this basis, the matrix of the pairing has the following form:

    0 0 0 C 0 A 0 D 0 0 B E C T D T E T F     ,
where A, B are symmetric, invertible matrices, and C is an invertible matrix. Changing the basis of w n so that (x i ) i∈I and (t i ) i∈I are dual, we can assume that C is an identity matrix. Let A j be the j-th column of A, B k the k-th column of B, and so on. As A and B are invertible, there exists scalars λ (i) j and µ (i) k such that:

D i = j∈J λ (i) j A j , E i = k∈K µ (i) k B k .
We then put:

t ′ i = t i - j∈J λ (i) j y j - k∈K µ (i) k z k - i ′ ∈I f i,i ′ 2 x i ′ .
An easy computation proves that t ′ i is orthogonal to y j , z k , and t ′ i ′ for all j, k, i ′ . Taking the vector space w ′ n generated by the t ′ i , we obtain a complement of g n +H +2 n such that in an adapted basis of

H n = (g ∩ H +2 ) n ⊕ m n ⊕ h n ⊕ w ′
n , the matrix of the pairing has the following form:

    0 0 0 C 0 A 0 0 0 0 B 0 C T 0 0 0     ,
where A and B are symmetric, invertible matrices and C is an invertible matrix. The assertions on the orthogonals are then immediate.

2

Remark. As a consequence, choosing bases of (g ∩ H +2 ) n and w n in duality, the matrix of the pairing has the following form:

    0 0 0 I 0 A 0 0 0 0 B 0 I 0 0 0     ,
where A and B are symmetric, invertible matrices and I is an identity matrix.

1.2 Self-duality of a free and cofree Hopf algebra Lemma 4 Let H be a graded, connected, free and cofree Hopf algebra. Then, for all n ≥ 1:

dim(g n ) = dim H + H +2 n .
Proof. As H is free, there exists a graded subspace V ⊆ H, such that H ≈ T (V ) as an algebra. We shall consider the following formal series:

R(h) = ∞ k=0 dim(H k )h k , P (h) = ∞ k=0 dim(g k )h k , G(h) = ∞ k=0 dim(V k )h k .
As H ≈ T (V ) as an algebra,

H + = V ⊕ H +2 , so for all n ≥ 1, dim(V n ) = dim H + H +2 n . Moreover R(h) = 1 1-G(h) or equivalently G(h) = 1 -1 R(h)
. As H is cofree, it is isomorphic as a coalgebra to coT (g), the tensor coalgebra cogenerated by g (that is to say T (g) as a vector space, with the deconcatenation product). So R(h) =

or equivalently P (h) = 1 -1 R(h) = G(h). Hence, for all n ≥ 1, dim(g n ) = dim(V n ). 2
Theorem 5 Let H be a graded, connected, free and cofree Hopf algebra. Let us choose a nondegenerate, homogeneous pairing on g g∩H +2 . There exists a non-degenerate Hopf pairing -,on H, inducing the chosen pairing on g g∩H +2 . Moreover, if the pairing on g g∩H +2 is symmetric, then we can assume that the pairing on H is symmetric.

Proof. For all n ≥ 1, let us choose a complement m n of (H +2 ∩ g) n in (H +2 ) n , a complement h n of (H +2 ∩ g) n in g n , and a complement w n of (H +2 + g) n in H n . Hence:

H n = (H +2 ∩ g) n ⊕ m n ⊕ h n ⊕ w n .
Note that h n is isomorphic, as a vector space, with g g∩H +2 n

. Hence, there is a pairing -,on h n , making the restriction to h n of the canonical projection onto

g g∩H +2 n
an isometry.

We put V n = h n ⊕ w n ; for all n ≥ 1, V n is a complement of (H +2 ) n in H n . We denote by H n the subalgebra of H generated by

H 0 ⊕ . . . ⊕ H n . Then H n is freely generated by V 1 ⊕ . . . ⊕ V n .
Moreover, for all k ≤ n:

∆(H k ) ⊆ k i=0 H i ⊗ H k-i ⊆ H n ⊗ H n , so H n is a Hopf subalgebra of H.
We construct by induction on n a homogeneous injective Hopf algebra morphism φ (n) from H n to H * such that:

1. for all x, y ∈ h n , φ (n) (x)(y) = x, y . 2. φ (n) |H n-1 = φ (n-1) .
We first define φ (0) by φ (0) (1) = ε = 1 H * . Let us assume that φ (n-1) is constructed.

• for v ∈ V i , i ≤ n -1, φ (n) (v) = φ (n-1) (v). This is an element of H * i , by homogeneity of φ (n-1) . • for v ∈ h n , φ (n) (v) ∈ H *
n is defined by:

φ (n) (v)(x) =    v, x if x ∈ h n , 0 if x ∈ H +2 , 0 if x ∈ w n ,
where -, -is the pairing on h n defined earlier.

• for v ∈ w n , we define φ (n) (v) ∈ H * n by φ (n) (v)(x) =      0 if x ∈ h n , 0 if w ∈ w n , (φ (n-1) ) ⊗k • ∆(k-1) (v) (v 1 ⊗ . . . ⊗ v k ) if x = v 1 . . . v k , where v 1 , . . . , v k are homogeneous elements of V 1 ⊕. . .⊕V n-1 , k ≥ 2. As H +2 n = (H n-1 ) n = T (V 1 ⊕ . . . ⊕ V n-1 ) n , this perfectly defines φ(v). As H n is freely generated by V 1 ⊕ . . . ⊕ V n , we extend φ (n) to an algebra morphism from H n to H * . As φ (n) sends an element of V i to an element of H * i for all i ≤ n, φ (n)
is homogeneous. It clearly statisfies the two points of the induction hypothesis. It remains to prove that it is an injective Hopf algebra morphism. Let us first prove that φ

(n) is a Hopf algebra morphism. It is enough to prove that for v ∈ V 1 ⊕ . . . ⊕ V n , φ (n) ⊗ φ (n) • ∆(v) = ∆ • φ (n) (v). Using the induction hypothesis, we can restrict ourselves to v ∈ V n = h n ⊕ w n , and finally to v ∈ h n or v ∈ w n . If v ∈ h n , then, by definition, φ (n) (v) is orthogonal to H +2 , so φ (n) (v) is primitive by lemma 2, with H ′ = H * . As v is also primitive, the required assertion is proved in this case. If v ∈ w n , let x = v 1 . . . v k and y = v k+1 . . . v k+l , where v 1 , . . . , v k+l are homogeneous elements of V 1 ⊕ . . . ⊕ V n-1 . Then: ∆ • φ (n) (v) (x ⊗ y) = φ (n) (v)(xy) = (φ (n-1) ) ⊗k+l • ∆(k+l-1) (v) (v 1 ⊗ . . . ⊗ v k+l ) = (φ (n-1) ) ⊗k+l • ∆(k-1) ⊗ ∆(l-1) • ∆(v) (v 1 ⊗ . . . ⊗ v k+l ) = ∆(k-1) • φ (n-1) ⊗ ∆(l-1) • φ (n-1) • ∆(v) (v 1 ⊗ . . . ⊗ v k+l ) = φ (n-1) ⊗ φ (n-1) • ∆(v) (x ⊗ y) = φ (n) ⊗ φ (n) • ∆(v) (x ⊗ y).
We used the induction hypothesis for the fourth equality. This proves the required assertion, so φ (n) is a Hopf algebra morphism.

Let us now prove the injectivity of φ

(n) . Let x ∈ V n , such that φ (n) (x) ∈ H * +2 . Let us prove that x = 0. By homogeneity, φ (n) (x) ∈ H * +2 n . As φ (n-1) is injective, comparing the dimension of the homogeneous component of degree i of H n-1 and H * for all i ≤ n -1, we deduce that H * i ⊆ Im(φ (n-1) ) if i ≤ n -1. So H * +2 n ⊆ Im(φ (n-1) ). Hence, there exists y ∈ H n-1 , homogeneous of degree n -1, such that φ (n) (x) = φ (n-1) (y). So y ∈ (H n ) +2 and x -y ∈ Ker(φ (n) ). By the induction hypothesis, φ (n) restricted to the homogeneous components of degree ≤ n -1 is injective, so if x -y = 0, it is a non-zero element of Ker(φ (n) ) of minimal degree: as φ (n) is a Hopf algebra morphism, x -y is primitive. So x -y ∈ h n ⊕ (g ∩ H +2 ) n . Moreover, y ∈ (H +2 ) n , so x ∈ (h n ⊕ (g ∩ H +2 ) n ⊕ m n ) ∩ (h n ⊕ w n ) = h n . As the pairing on h n × h n is non-degenerate, if x = 0, there exists z ∈ h n , such that φ (n) (x)(z) = x, z = 0, so φ (n) (x) / ∈ g ⊥ = H * +2 : contradiction. So x = 0.
This proves that φ 1) is an injective Hopf algebra morphism, we deduce that φ

(n) (V n ) ∩ H * +2 = (0) and φ (n) |Vn is injective. As φ (n-
(n) (V k ) ∩ H * +2 = (0) and φ (n) |V k is injective for all k ≤ n. As H is cofree, H * is free, so φ (n) (V 1 ⊕ . . . ⊕ V n ) generates a free subalgebra of H * . As φ (n) |V 1 ⊕...⊕Vn is injective and H n is freely generated by V 1 ⊕ . . . ⊕ V n , φ (n) is injective. Conclusion. Let x ∈ H. We put φ(x) = φ (n) (x) for any n ≥ deg(x)
. By the second point of the induction, this is well-defined. As φ (n) is an injective and homogeneous Hopf algebra morphism for all n, φ also is. Comparing the formal series of H and H * , φ is an isomorphism. So it defines a non-degenerate, homogeneous Hopf pairing on H. By the first point of the induction, it implies the chosen pairing on g g∩H +2 .

Let us finally prove the symmetry of this pairing if the pairing on

g g∩H +2 is symmetric. Let x, y ∈ H n , let us prove that x, y = y, x by induction on n. As H 0 = K, it is obvious if n = 0. If n ≥ 1, then x, y = φ (n) (x)(y). It is then enough to prove this for x, y ∈ h n , or w n , or (H +2 ) n . First case. If x ∈ (H +2 ) n , let us put x = x 1 x 2
, where x 1 , x 2 are homogeneous, of degree < n. Then, by the induction hypothesis:

x, y = x 1 ⊗ x 2 , ∆(y) = x 1 ⊗ x 2 , ∆(y) = ∆(y), x 1 ⊗ x 2 = y, x . The proof is similar if y ∈ (H +2 ) n .
Second subcase. If x ∈ w n and y ∈ h n or w n , then by definition of φ (n) , x, y = y, x = 0. The proof is similar if y ∈ w n and x ∈ h n or w n .

Last subcase. If x, y ∈ h n , then x, y = y, x as the pairing on g g∩H +2 is symmetric. 2

Remark. It is possible to extend a symmetric pairing on g g∩H +2 to a non-symmetric, nondegenerate Hopf pairing on H: it is enough to arbitrarily change the values of φ

(n) (v)(x) for v ∈ h n and x ∈ w n , or v ∈ w n and x ∈ h n .
Corollary 6 Let H be a graded, connected Hopf algebra, free and cofree. Then it is self-dual.

Proof. It is enough to choose a non-degenerate, homogeneous pairing on g g∩H +2 and then to apply theorem 5. 2

Isomorphisms of free and cofree Hopf algebras

Proposition 7 Let H and H ′ be two free and cofree Hopf algebras, both with a symmetric, non-degenerate Hopf pairing, such that

g g∩H +2 n and g ′ g ′ ∩H ′+2 n
, endowed with the pairings induced from the Hopf pairings, are isometric for all n ≥ 1. Then there exists a Hopf algebra isomorphism from H to H ′ which is an isometry.

Proof. We inductively construct a homogeneous isomorphism φ

(n) : H n -→ H ′ n , such that: 1. φ (n) |H n-1 = φ (n-1) if n ≥ 1. 2. φ (n) (x), φ (n) (y) = x, y for all x, y ∈ H n .
We define φ (0) :

H 0 = K -→ H ′ 0 by φ (0) (1) = 1. Let us assume that φ (n-1) is constructed. We choose a decomposition H n = (g ∩ H +2 ) n ⊕ m n ⊕ h n ⊕ w n as in lemma 3. As φ (n-1) is a Hopf algebra isomorphism, φ (n-1) ((H n-1 ) n ) = φ (n-1) (H +2 ) n = (H ′ n-1 ) n = H ′ +2 n . As a consequence, φ(m n ) = m ′ n is a complement of (g ′ ∩ H ′ +2 ) n in H ′ +2 n .
Moreover, as the isometry

φ (n-1) sends (H n-1 ) n = H +2 n to (H ′ n-1 ) n = H ′ +2 n , it induces an isometry from (g ∩ H +2 ) n to (g ′ ∩ H ′ +2 ) n and from m n to m ′ n . Let us choose a complement h n of (g ∩ H +2 ) n in g n and a complement h ′ n of (g ′ ∩ H ′ +2 ) n in g ′ n . As h n is isometric with g g∩H +2 n and h ′ n with g ′ g ′ ∩H ′+2 n
, there exists an isometry φ : h n -→ h ′ n . Using lemma 3, there exists a basis

(x i ) i∈I ∪ (y j ) j∈J ∪ (z k ) k∈K ∪ (t i ) i∈I adapted to the decomposition H n = (g ∩ H +2 ) n ⊕ m n ⊕ h n ⊕ w n , and a basis (φ (n-1) (x i )) i∈I ∪ (φ (n-1) (y j )) j∈J ∪ (φ(z k )) k∈K ∪ (t ′ i ) i∈I
, such that the matrices of the pairing of H n and H ′ n in these bases are both equal to:

    0 0 0 I 0 A 0 0 0 0 B 0 I 0 0 0     .
We then define φ

(n) on H 0 ⊕ . . . ⊕ H n by putting φ (n) (x) = x if x ∈ H n-1 , φ (n) (x) = φ(x) if x ∈ h n and φ (n) (t i ) = t ′ i for all i ∈ I. As H n is freely generated by h 1 ⊕ w 1 ⊕ . . . ⊕ h n ⊕ w n , φ (n) is extended to an algebra morphism from H n to H ′ n . As its image contains h ′ 1 ⊕ w ′ 1 ⊕ . . . ⊕ h ′ n ⊕ w ′ n , which freely generates H ′ n , it is surjective. As φ (n) induces a linear isomorphism from h 1 ⊕ w 1 ⊕ . . . ⊕ h n ⊕ w n to h ′ 1 ⊕ w ′ 1 ⊕ . . . ⊕ h ′ n ⊕ w ′ n , φ (n)
is an isomorphism. By construction (for i = n) and by the induction hypothesis (for i < n), φ

(n) |H i is an isometry from H i to H ′ i for all i ≤ n. Let us prove that φ (n) is a Hopf algebra isomorphism. It is enough to prove that ∆•φ (n) (x) = (φ (n) ⊗ φ (n) ) • ∆(x) for x ∈ h 1 ⊕ w 1 ⊕ . . . ⊕ h n ⊕ w n . If x ∈ h 1 ⊕ w 1 ⊕ . . . ⊕ h n-1 ⊕ w n-1 , this comes from the induction hypothesis. If x ∈ h n , then both x and φ (n) (x) ∈ h ′ n are primitive, so the result is obvious. Let us assume that x ∈ w n . Let us take y ′ ∈ H ′ k , z ′ ∈ H ′ l , with k + l = n. As φ (n) (H i ) = H ′ i if i ≤ n, we put y ′ = φ (n) (y) and z ′ = φ (n) (z): (φ (n) ⊗ φ (n) ) • ∆(x), y ′ ⊗ z ′ = (φ (n) ⊗ φ (n) ) • ∆(x), φ (n) (y) ⊗ φ (n) (z) = ∆(x), y ⊗ z = x, yz = φ (n) (x), φ (n) (yz) = φ (n) (x), φ (n) (y)φ (n) (z) = ∆ • φ (n) (x), φ (n) (y) ⊗ φ (n) (z) = ∆ • φ (n) (x), y ′ ⊗ z ′ .
By homogeneity, we deduce that (φ

(n) ⊗ φ (n) ) • ∆(x) -∆ • φ (n) (x) ∈ (H ′ ⊗ H ′ ) ⊥ = (0), as the pairing of H ′ is non-degenerate.
It remains to show that φ (n) is an isometry: let us prove that x, y = φ (n) (x), φ (n) (y) , for x, y ∈ H n . We can assume that x is homogenous of degree k. If k ≤ n, by homogeneity of φ (n) and the pairing, this is true as φ

(n) |Hn is an isometry from H n to H ′ n . If k > n,
as H n us generated by elements of degree ≤ n, we can assume that x = x 1 . . . x k , with x i homogeneous of degree ≤ n for all i. Then:

φ (n) (x), φ (n) (y) = φ (n) (x 1 ) . . . φ (n) (x k ), φ (n) (y) = φ (n) (x 1 ) ⊗ . . . ⊗ φ (n) (x k ), ∆ (k-1) • φ (n) (y) = φ (n) (x 1 ) ⊗ . . . ⊗ φ (n) (x k ), (φ (n) ⊗ . . . ⊗ φ (n) ) • ∆ (k-1) (y) = x 1 ⊗ . . . ⊗ x k , ∆ (k-1) (y) = x 1 . . . x k , y = x, y .
Conclusion. We define φ : H -→ H ′ by φ(x) = φ (n) (x) for all x ∈ H n . By the first point of the induction, this does not depend of the choice of n. Moreover, φ is clearly an isomorphism of Hopf algebras and an isometry.

2

Remark. Note that the pairings used in proposition 7 are any Hopf pairings, not necessarily the Hopf pairings obtained by extension of a non-degenerate bilinear form on g g∩H +2 in theorem 5.

Theorem 8 Let H and H ′ be two connected, graded Hopf algebras, both free and cofree. The following conditions are equivalent:

1. H and H ′ are isomorphic graded Hopf algebras. i for all i < n. From the proof of theorem 5, we can extend them to pairings on H n-1 and H ′ n-1 . From the proof of proposition 7, H n-1 and H ′ n-1 are isomorphic Hopf algebras. As a consequence:

dim(H +2 n ) = dim((H n-1 ) n ) = dim((H n-1 ) n ) = dim(H ′+2 n ), dim(g ∩ H +2 n ) = dim((g ∩ H n-1 ) n ) = dim((g ′ ∩ H n-1 ) n ) = dim(g ′ ∩ H ′+2 n ).
Using a decomposition of lemma 3 for H, we deduce:

dim(H n ) = dim(H +2 n ) + dim(h n ) + dim(w n ) = dim(H +2 n ) + dim g g ∩ H +2 n + dim((g ∩ H +2 ) n ).
Using a decomposition of lemma 3 for H ′ and combining the different equalities, we obtain:

dim(H n ) -dim(H ′ n ) = dim g g ∩ H +2 n -dim g ′ g ′ ∩ H ′+2 n .
So this is not zero: H and H ′ do not have the same formal series.

2

Remark. This result immediately implies that FQSym and H ho are isomorphic, proving again a result of [START_REF] Foissy | Ordered forests, permutations and iterated integrals[END_REF]. Similarly, PQSym and H o are isomorphic, as proved in [START_REF]Ordered forests and parking functions[END_REF]; RΠ and SΠ are isomorphic, as proved in [START_REF] Aguiar | Coxeter groups and Hopf algebras[END_REF].

2 Formal series of a free and cofree Hopf algebra in characteristic zero

In all this section, we assume that the characteristic of the base field is 0.

General preliminary results

We first put here together several technical results.

Notations. Let A be a graded connected Hopf algebra.

• I A is the ideal of A generated by the commutators of A. The quotient A ab = A/I A is a graded, connected, commutative Hopf algebra.

• C A is the greatest cocommutative subcoalgebra of A. It is a graded, connected, cocommutative Hopf subalgebra of A.

• P rim(A) is the Lie algebra of the primitive elements of A.

• coP rim(A) is the Lie coalgebra of A, that is to say A + A +2 . The Lie cobracket is given by δ

(x) = (π ⊗ π) • ( ∆ -∆op )(x)
, where π is the canonical projection from A + to coP rim(A). Note that coP rim(A) is the space of indecomposable elements, denoted by Q(A) in [START_REF] Milnor | On the structure of Hopf algebras[END_REF].

Let P rim(A) ab = P rim(A)

[P rim(A),P rim(A)] . As the Lie algebra of P rim(A ab ) is abelian, there exists a natural map:

π A : P rim(A) ab -→ P rim(A ab ) x + [P rim(A), P rim(A)] -→ x + I A .
The kernel of π A is

I A ∩P rim(A) [P rim(A),P rim(A)] .
Let coP rim(A) ab = {x ∈ coP rim(A) | δ(x) = 0}. As C A is cocommutative, the Lie coalgebra of C A is trivial; hence, there is a natural map:

ι A : coP rim(C A ) -→ coP rim(A) ab x + C +2 A -→ x + A +2 .
This map is well-defined, as

C +2 A ⊆ A +2 . Its kernel is C A ∩A +2 C +2 A .
Let A * be the graded dual of A. Using the duality between A and A * , it is easy to prove:

• I ⊥ A = C A * so A ab = C A * and C * A = (A * ) ab .
• P rim(A) ⊥ = (1) + A * +2 , so P rim(A) * = coP rim(A * ). As a consequence of these two points, coP rim(C A ) * = P rim(C * A ) = P rim((A * ) ab ).

• [P rim(A), P rim(A)] ⊥ = coP rim(A * ) ab , so (coP rim(A) ab ) * = P rim(A * ) ab .

Via these identifications, π * A = ι A * and ι * A = π A * . So:

Lemma 9 1. Let us fix an integer n. The following assertions are equivalent:

(a) π A is injective in degree n.

(b) ι A * is surjective in degree n.

(c) [P rim(A), P rim(A)] n = (P rim(A) ∩ I A ) n .

2. Let us fix an integer n. The following assertions are equivalent:

(a) ι A is injective in degree n.

(b) π A * is surjective in degree n. (c) (C A ∩ A +2 ) n = (C +2 A ) n .
Lemma 10 (char(K) = 0). If A is cocommutative or commutative, then π A and ι A are isomorphisms.

Proof. Let us assume that A is cocommutative. As the characteristic of the base field is zero, by the Cartier-Quillen-Milnor-Moore theorem, A is the enveloping algebra of P rim(A). Using the universal property of enveloping algebras, it is not difficult to prove that A ab = U (P rim(A) ab ) = S(P rim(A) ab )). As P rim(U (P rim(A ab ))) = P rim(A ab ), π A is clearly bijective. As A is cocommutative, C A = A and coP rim(A) ab = coP rim(A). So ι A is the identity of coP rim(A).

Let us now assume that A is commutative. Then A * is cocommutative, so ι A * and π A * are bijective. Hence, their transposes π A and ι A are bijective.

2

Proposition 11 (char(K) = 0). Let A be any graded, connected Hopf algebra. Then P rim(A) ∩ A +2 = P rim(A) ∩ I A and C A = U (P rim(A)). Moreover, the following assertions are equivalent:

1. π A is injective in degree n.

2. ι A * is surjective in degree n.

3. ι A is injective in degree n.

4. π A * is surjective in degree n.

(P rim(A) ∩ A +2

) n = [P rim(A), P rim(A)] n .

(C

A ∩ A +2 ) n = (C +2 A ) n .

Proof. As I

A ∩ A +2 , P rim(A) ∩ I A ⊆ P rim(A) ∩ A +2 . Let x ∈ P rim(A) ∩ A +2 . Then x + I A ∈ P rim(A ab ) ∩ A +2 ab . As A ab is commutative, ι A ab is a bijection, so C A ab ∩ A +2 ab = C +2 A ab . As x + I A is primitive, it belongs to C A ab , so x + I A ∈ C +2
A ab ∩ P rim(A ab ). By the Cartier-Quillen-Milnor-Moore theorem, C A ab is a symmetric Hopf algebra, so C +2

A ab ∩ P rim(A ab ) = (0). So x ∈ P rim(A) ∩ I A .

As K +P rim(A) is a cocommutative subcoalgebra of A, it is included in C A . So P rim(C A ) = P rim(A). By the Cartier-Quillen-Milnor-Moore theorem, C A = U (P rim(A)).

By lemma 9, 1, 2 and 5 are equivalent, and 3, 4 and 6 are equivalent. As C A = U (P rim(A)),

C + A = P rim(A) + C +2 A , so coP rim(C A ) = P rim(A) P rim(A)∩C +2 A . As a consequence, the kernel of ι A is P rim(A)∩A +2 P rim(A)∩C +2 A . Moreover, as C A is cocommutative, π A is bijective, so P rim(A) ∩ C +2 A = P rim(A) ∩ I C A = [P rim(A), P rim(A)].
Finally, the kernel of ι A is P rim(A)∩A +2

[P rim(A),P rim(A)] . So 3 and 5 are equivalent. 2

Remark. If the characteristic of the base field is a prime integer p, it may be false that C A = U (P rim(A)). The weaker assertion telling that C A is generated by P rim(A), so is a quotient of U (P rim(A)), may also be false. For example, let us consider the Hopf algebra of divided powers A, that is to say the graded dual of K[X]. This Hopf algebra as a basis (x (n) ) n≥0 , the product and coproduct are given by:

x (i) x (j) = i + j i x (i+j) , ∆(x (n) ) = i+j=n x (i) ⊗ x (j) .
As A is cocommutative, C A = A. It is not difficult to see that P rim(A) = V ect x (1) , and the subalgebra generated by P rim(A) is V ect(x (i) , 0 ≤ i < p), so is not equal to C A .

Primitive elements of a free and cofree Hopf algebra

Proposition 12 (char(K) = 0). Let H be a graded, connected, free and cofree Hopf algebra. Then ι H and π H are isomorphisms.

Proof. Let us prove by induction on

n that (C H ∩ H +2 ) n = (C +2 H ) n .
There is nothing to prove for n = 0. Let us assume the result at all rank k < n.

As H is free, let us choose a graded subspace V of H, such that H = T (V ) as an algebra. Then H + = V ⊕H +2 , so coP rim(H) is identified with V . For all k ∈ N, we denote by π k the projection on V k in H = T (V ). Then the Lie cobracket of V is given by δ

(v) = (π 1 ⊗ π 1 ) • (∆ -∆ op )(v).
For any word w = v 1 . . . v k in homogeneous elements of V , we put d(w) = (deg(v 1 ), . . . , deg(v k )). We obtain in this way a gradation of H, indexed by words in nonnegative integers. These words are totally ordered in the following way: if w = (a 1 , . . . , a m ) and w ′ = (a ′ 1 , . . . , a ′ n ) are two different words, then w < w ′ if, and only if, (m < n), or (m = n and there exists an index i,

such that a 1 = a ′ 1 , . . . , a i = a ′ i , a i+1 < a ′ i+1 ). Let x ∈ (C H ∩ H +2 ) n .
We can write:

x = n k=2 (a 1 ,...,a k )∈N k a 1 +...+a k =n x a 1 ,...,a k x k
, where x a 1 ,...,a k is a linear span of words w such that d(w) = (a 1 , . . . , a k ). Let us put I n the set of words (a 1 , . . . , a k ) such that a 1 + . . . + a k = n. This set is finite and totally ordered. Its greatest element is (1, . . . , 1). Let us proceed by a decreasing induction on the smallest w = (a 1 , . . . , a n ) ∈ I n such that x w = 0. If w = (1, . . . , 1), then x is in the subalgebra generated by

H 1 . As H is connected, H 1 ⊆ C H , so x ∈ C +2 H .
Let us assume the result for all w ′ > w = (a 1 , . . . , a k ) in I n . We first prove that x a 1 ,...,a k ∈ V k ab . We put:

x k = i v (i) 1 . . . v (i) k .
By minimality of (a 1 , . . . , a k ), we obtain:

(π k ⊗ π 1 ) • (∆ -∆ op )(x) = i k j=1 v (i) 1 . . . v (i) j ′ . . . v (j) k ⊗ v (i) j ′′ , with the notation δ(v) = v ′ ⊗ v ′′ for all v ∈ V . As x ∈ C H , ∆(x) = ∆ op (x)
, so this is zero. As H is freely generated by V , we deduce:

i k j=1 v (i) 1 ⊗ . . . ⊗ v (i) j ′ ⊗ . . . ⊗ v (j) k ⊗ v (i) j ′′ = 0.
Considering the terms of this sum of the form v 1 ⊗ . . . ⊗ v k+1 , with deg(v 1 ) + deg(v k+1 ) minimal, we obtain that:

(b 1 ,...,b k )∈In b 1 =a 1 x b 1 ,...,bn ∈ V ab V k-1 .
Considering the terms of the form v 1 ⊗ . . . ⊗ v k+1 , with deg(v 1 ) = a 1 and deg(v 2 ) + deg(v k+1 ) minimal, we obtain that:

(b 1 ,...,b k )∈In b 1 =a 1 , b 2 =a 2 x b 1 ,...,bn ∈ V 2 ab V k-2 .
Iterating the process, we finally obtain that x a 1 ,...,a k ∈ V k ab .

We now put:

x a 1 ,...,a k = i w (i) 1 . . . w (i) k ,
where the w (i) j belong to (V ab ) a i . As k ≥ 2, a 1 , . . . , a k < n. By the induction hypothesis, ι H is bijective in degree a i for all i. So there exists x (i)

j in P rim(H) a j , such that x (i) j -w (i) j ∈ H +2 .
We consider the following element:

y = x - i x (i) 1 . . . x (i) k in(C +2 H )n .
As the x

∈ (C +2 H ) n . So x ∈ (C +2 H ) n .
Conclusion. So assertion 6 of proposition 11 is satisfied for all n. Hence, for all n, ι H is injective in degree n and ι H * is surjective in degree n. By corollary 6, H * is isomorphic to H. So ι H is surjective in degree n. A similar proof holds for π H . 2

Corollary 13 (char(K) = 0). Let H be a graded, connected, free and cofree Hopf algebra. Then [g, g] = g ∩ H +2 . Let h be a graded subspace of H such that g = [g, g] ⊕ h.

1. Then h freely generates the Lie algebra g. The subalgebra generated by h is a free Hopf subalgebra of H, isomorphic to U (g).

2. The graded Hopf algebra H ab is isomorphic to the shuffle algebra coT (h).

Proof. 1. By proposition 11, as π H is injective by proposition 12, [g, g] = g ∩ H +2 . As g = [g, g] + h, h generates the Lie algebra g. Moreover, h ∩ H +2 ⊆ h ∩ g ∩ H +2 = h ∩ [g, g] = (0), so h generates a free algebra K h . As h ⊆ g, K h is clearly a cocommutative Hopf subalgebra of H. As h generates the Lie algebra g, by the Cartier-Quillen-Milnor-Moore theorem, K h is isomorphic to U (g). So the algebra U (g) is freely generated by h, which implies that the Lie algebra g is freely generated by h.

2.

As H is self-dual, the Hopf algebras U (g) * = (C H ) * , (H * ) ab and H ab are isomorphic. By the first point, U (g) is isomorphic to

T (h), so H ab is isomorphic to T (h * ) * ≈ coT (h). 2
Remarks.

1. Corollary 13 is false in characteristic p. Indeed,

g p = V ect(x p | x ∈ g) ⊆ g ∩ H +2 . It is also false that g ∩ H +2 = [g, g] + g p .
For example, let us consider a free and cofree Hopf algebra H over K, such that g g∩H +2 is one-dimensional, concentrated in degree 1. So H 1 is one-dimensional, generated by an element x, which is primitive. It is not difficult to show that

H i = V ect(x i ) if i < p. As a consequence, g 1 = V ect(x) and g i = (0) if 2 ≤ i ≤ p -1.
As H is cofree, there exists y ∈ H p , such that :

∆(y) = y ⊗ 1 + p-1 i=1 x i i! ⊗ x p-i (p -i)! + 1 ⊗ y.
It is then not difficult to show that (x p , y) is a basis of H p . So [g, g] p+1 = (0) and (g p ) p+1 = (0). But xy -yx is a non-zero element of (g ∩ H +2 ) p+1 .

2. If H is a non-commutative Connes-Kreimer Hopf algebra, then P rim(H) is a free brace algebra; conversely, any free brace algebra is isomorphic to the Lie algebra of a noncommutative Connes-Kreimer Hopf algebra [START_REF] Chapoton | Un théorème de Cartier-Milnor-Moore-Quillen pour les bigèbres dendriformes et les algèbres braces[END_REF][START_REF]Les algèbres de Hopf des arbres enracinés décorés. II[END_REF][START_REF] Ronco | Eulerian idempotents and Milnor-Moore theorem for certain noncocommutative Hopf algebras[END_REF]. One then recovers the result of [START_REF] Foissy | Les algèbres de Hopf des arbres enracinés décorés. I[END_REF], telling that in characteristic zero, a free brace algebra is a free Lie algebra.

Poincaré-Hilbert series of H

Let H be a graded, connected, free and cofree Hopf algebra. We put:

R(h) = ∞ n=0 dim(H n )h n , P (h) = ∞ n=1 dim(g n )h n , S(h) = ∞ n=1 dim g g ∩ H +2 n h n .
The coefficients of R(h), P (h) and S(h) will be respectively denoted by r n , p n and s n .

Proposition 14 (char(K) = 0). The following relations between R(h), P (h) and S(h) are satisfied:

1. R(h) = 1 1 -P (h)
and

P (h) = 1 - 1 R(h) . 2. 1 -S(h) = ∞ n=1 (1 -h n ) pn .
Proof. 1. This comes from the cofreeness of H, see lemma 4.

2. We use the notations of corollary 13. Then h and g g∩H +2 have the same Poincaré-Hilbert series. As U (g) is freely generated by h, the Poincaré-Hilbert series of U (g) is

1 1-S(h) . By the Poincaré-Birkhoff-Witt theorem, 1 1 -S(h) = ∞ n=1 1 (1 -h n ) pn . 2
The first point of proposition 14 allows to compute r n in function of p 1 , . . . , p n and p n in function of r 1 , . . . , r n ; the second point allows to compute s n in function of p 1 , . . . , p n and p n in function of s 1 , . . . , s n . For example:

r 1 = p 1 p 1 = r 1 r 2 = p 2 + p 2 1 p 2 = r 2 -r 2 1 r 3 = p 3 + p 3 1 + 2p 2 p 1 p 3 = r 3 + r 3 1 -2r 2 r 1 p 1 = s 1 s 1 = p 1 p 2 = s 2 + s 2 1 2 - s 1 2 s 2 = p 2 - p 2 1 2 + p 1 2 p 3 = s 3 - s 1 3 + s 1 s 2 + s 3 1 3 s 3 = p 3 + p 1 3 -p 1 p 2 - p 2 1 2 + p 3 1 6 r 1 = s 1 s 1 = r 1 r 2 = s 2 + 3s 2 1 2 - s 1 2 s 2 = r 2 - 3r 2 1 2 + r 1 2 r 3 = s 3 - s 1 3 + 3s 1 s 2 -s 2 1 + 7s 3 1 3 s 3 = r 3 + r 1 3 -3r 1 r 2 - r 2 1 2 + 13r 3 1 6
Remark. These formulas are false if the characteristic of the base field is not zero. For example, let us take S(h) = h. The formulas of proposition 14 gives then that p 1 = 1 and p n = 0 if n ≥ 2, so P (h) = h and finally R(h) = 1 1-h : as a consequence, H = K[h] as a Hopf algebra. If the characteristic of the base field is a prime integer p, then P rim(H) = V ect(X

p k | k ∈ N), so P (h) = h: contradiction.
Here are several applications of these formulas, for the Hopf algebras of the introduction: We here denote by 2-As(1) the free 2-As algebra on one generator. The third row is sequence A122826 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF], whereas the fifth row is sequence A122720.

s 1 s 2 s
Note that, for all n ≥ 1, s n = S n (r 1 , . . . , r n ) for particular polynomials

S n (R 1 , . . . , R n ) ∈ Q[R 1 , . . . , R n ].
We define these polynomials here:

Definition 15 We put in the algebra Q[R 1 , . . . , R n , . . .][[h]]: ∞ n=1 P n (R 1 , . . . , R n )h n = 1 - 1 1 + ∞ n=1 R n h n , ∞ n=1 S n (R 1 , . . . , R n )h n = 1 - ∞ n=1 (1 -h n ) Pn(S 1 ,...,Sn) = 1 - ∞ n=1 ∞ k=0 P n (R 1 , . . . , R n ) . . . (P n (R 1 , . . . , R n ) -k + 1) k! h nk .
Examples.

S 1 (R 1 ) = R 1 S 2 (R 1 , R 2 ) = R 2 - 3R 2 1 2 + R 1 2 S 3 (R 1 , R 2 , R 3 ) = R 3 + R 1 3 -3R 1 R 2 - R 2 1 2 + 13R 3 1 6
Remark. It is not difficult to show that if r i ∈ Z for all 1 ≤ i ≤ n, then P n (r 1 , . . . , r n ), S n (r 1 , . . . , r n ) ∈ Z.

Free and cofree Hopf subalgebras

Proposition 16 (char(K) = 0). Let H be a graded, connected, free and cofree Hopf algebra, with a non-degenerate symmetric Hopf pairing. Let g ′ be a graded, non-isotropic subspace of g g∩H +2 . There exists a free and cofree Hopf subalgebra

H ′ of H, that g ′ = g ′ g ′ ∩H ′+2 .
Proof. Let us choose a graded complement h of g ∩ H +2 in g. The canonical projection π from g to g g∩H +2 induces an isometry π from h to g g∩H +2 . Let h ′ be π -1 |h (g ′ ): h ′ is a supspace of h, isometric with g ′ . As g ′ is non-isotropic, h ′ is non-isotropic. Let us put h ′′ = h ′⊥ ∩ h. Then h ′ and h ′′ are graded subspaces of h and h = h ′ ⊕ h ′′ . By corollary 13, h freely generates g as a Lie algebra. We then denote by g ′ the sub-Lie algebra of g generated by h ′ and by g ′′ the Lie ideal of g generated by h ′′ . Then g = g ′ ⊕ g ′′ and:

g ∩ H +2 = [g, g] = [g ′ , g ′ ] ⊕ [g, g ′′ ] = (g ′ ∩ H +2 ) ⊕ (g ′′ ∩ H +2 ).
We now construct by induction on n subspaces m ′ n ⊕ m ′′ n = m n and w ′ n ⊕ w ′′ n = w n of H n , as in lemma 3, such that:

of m ′ n ⊕ (g ∩ H +2 ) n in H +2 n included in (I n-1 ) n . As m ′ n ⊆ H ′ n-1 , m ′ n ⊥ m ′′ n . We put m n = m ′ n ⊕ m ′′ n .
We finally choose a w n as in lemma 3.

As a summary, we obtain a decomposition:

H n = (g ′ ∩ H ′ n-1 +2 ) n ⊕ g ′′ n (g∩H +2 )n ⊕ m ′ n ⊕ m ′′ n mn ⊕ h ′ n ⊕ h ′′ n hn ⊕w n , (H n-1 ) n = g ′ ∩ H ′ n-1 +2 n ⊕ m ′ n .
In a basis adapted to the decomposition, by lemma 3 the matrix of the pairing has the form:

            0 0 0 0 0 0 I 0 0 0 0 0 0 0 0 I 0 0 A ′ 0 0 0 0 0 0 0 0 A ′′ 0 0 0 0 0 0 0 0 B ′ 0 0 0 0 0 0 0 0 B ′′ 0 0 I 0 0 0 0 0 0 0 0 I 0 0 0 0 0 0             .
We naturally decompose w n as a direct sum w ′ n ⊕ w ′′ n , in order to split the last column and last row of the matrix. All the required subspaces are now defined. A basis of (H ′ n ) n is given by the blocks 1, 3, 5, 7 of the basis. A basis of (I n ) n is given by the blocks 2, 4, 6, 8 of the basis. It is matricially clear that (H ′ n ) n ⊥ (I n ) n . As these subspaces are in direct sum, (H

′ n ) ⊥ n = (I n ) n in H n . Let us take x ∈ w ′ n . If y ∈ (I n ) k , z ∈ H l , with k + l = n, then as yz ∈ (I n ) n , 0 = x, yz = ∆(x)y ⊗ z . So ∆(x) ∈ (I n ⊗ H) ⊥ n . Similarly, ∆(x) ∈ (H ⊗ I n ) ⊥ n . As (I n ) ⊥ i = (H ′ n ) i by the preceding remark if i = n and the induction hypothesis if i < n, we deduce that ∆(x) ∈ H ′ n ⊗ H ′ n . As H ′ n-1 is a Hopf subalgebra, we deduce that H ′ n is a Hopf subalgebra.
Let us prove that (H ′ n ) i ⊥ (I n ) i for all i. We already prove it for i ≤ n. If i > n + 1, let us take x ∈ (H ′ n ) i and y ∈ (I n ) i . As i > n, we can assume that y = y 1 y 2 y 3 , with y 1 , y 3 ∈ H, y 2 ∈ (I n ) k with k ≤ n. Using the homogeneity of the pairing and the property of orthogonality at rank k:

x, y = ∆ (2) (x)

∈H ⊗3 n , y 1 ⊗ y 2 ⊗ y 3 = 0,
as y 2 ⊥ H n . This ends the induction.

Conclusion.

We the take H ′ the subalgebra generated by h ′ ⊕ w ′ and I the ideal generated by h ′′ + w ′′ . By construction, H ′ is a free Hopf algebra. As H is freely generated by h ′ ⊕ w ′ ⊕ h ′′ ⊕ w ′′ , H ′ ⊕ I = H. Moreover H ′ ⊥ I, so H ′ = I ⊥ , comparing their formal series. As a conclusion, H ′ is a non-isotropic subspace of H, so has a non-degenerate, symmetric Hopf pairing. By construction of h ′ ,

g ′ g ′ ∩H ′+2 is g ′ . 2
2.5 Existence of free and cofree Hopf algebra with a given formal series

Corollary 17 (char(K) = 0). Let V be a graded space such that V 0 = (0), with a symmetric, homogeneous non-degenerate pairing. There exists a graded, connected, free and cofree Hopf algebra H, with a symmetric, non-degenerate Hopf pairing, such that g g∩H +2 is isometric with V . Moreover, H is unique, up to an isomorphism. = s n for all n ≥ 1. Moreover, it is unique, up to an isomorphism.

Proof

Proof. Existence. Let V be a graded space such that dim(V n ) = s n for all n ≥ 1. Let us choose a non-degenerate, homogeneous symmetric pairing on V . Then corollary 17 proves the existence of H.

Unicity. Comes directly from theorem 8, 2 =⇒ 1.

2

So graded, connected, free and cofree Hopf algebras are entirely determined by sequences of dimensions:

Corollary 19 (char(K) = 0). Let (r n ) n≥1 be any sequence of integers. There exists a graded, connected, free and cofree Hopf algebra

H such that dim(H n ) = r n for all n ≥ 1 if, and only if, S n (r 1 , . . . , r n ) ≥ 0 for all n ≥ 1 (recall that S n (R 1 , . . . , R n ) is defined in definition 15). Proof. =⇒. As S n (r 1 , . . . , r n ) = dim g g∩H +2 n
for all n ≥ 1.

⇐=. Let us put s n = S n (r 1 , . . . , r n ). From corollary 18, there exists a graded, connected, free and cofree Hopf algebra H such that dim

g g∩H +2 n = s n for all n ≥ 1. From proposition 14, dim(H n ) = r n for all n ≥ 1. 2
Remark. It is not difficult to show that S n (R 1 , . . . , R n ) -R n ∈ Q[R 1 , . . . , R n-1 ]
. So the condition on the r n of corollary 19 can be seen as a growth condition on the coefficients r n .

Noncommutative Connes-Kreimer Hopf algebras

When is a free and cofree Hopf algebra a noncommutative Connes-Kreimer Hopf algebra? Definition 20 The family of polynomials D

n (R 1 , . . . , R n ) ∈ Q[R 1 , . . . , R n ] is defined by: ∞ n=1 D n (R 1 , . . . , R n )h n = ∞ n=1 (-1) n+1 n ∞ k=1 R k h k n = ∞ k=1 R k h k -1 ∞ k=1 R k h k 2 .
Examples.

D 1 (R 1 ) = R 1 D 2 (R 1 , R 2 ) = R 2 -2R 2 1 D 3 (R 1 , R 2 , R 3 ) = R 3 -4R 2 R 1 + 3R 2 1
Theorem 21 Let H be a graded, connected, free and cofree Hopf algebra. We put r n = dim(H n ) for all n ≥ 1. Then H is isomorphic to a noncommutative Connes-Kreimer Hopf algebra if, and only if, D n (r 1 , . . . , r n ) ≥ 0 for all n ≥ 1.

Proof. =⇒. We assume that H is isomorphic to the Hopf algebra of planar trees decorated by D, here denoted by H D N CK . Let D(h) be the formal series of D. Then, from [START_REF] Foissy | Les algèbres de Hopf des arbres enracinés décorés. I[END_REF], D(h) = R(h)-1 R(h) 2 , so Card(D n ) = D n (r 1 , . . . , r n ) ≥ 0 for all n ≥ 1.

⇐=. Let D be a graded set, such that Card(D n ) = D n (r 1 , . . . , r n ) for all n ≥ 1 (it is clear that D n (r 1 , . . . , r n ) is an integer). The formal series of D is D(h) = R(h)-1 R(h) 2 , so the formal series of H D N CK is:

1 -1 -4D(h) 2D(h) = R(h).
By theorem 8, H and H D N CK are isomorphic. 2

Remarks.

1. Let H be a free and cofree Hopf algebra, such that s 1 = s 2 = 1, s 3 = 0. By corollary 18, this exists. As s 2 = 0, H is not equal to K[X]. By proposition 14, r 1 = 1, r 2 = 2, r 3 = 4. So D 3 (r 1 , r 2 , r 3 ) = -1 < 0: H is not isomorphic to a non-commutative Connes-Kreimer Hopf algebra. The third line is sequence A122827 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF], whereas the fifth line is sequence A122705.

3 Isomorphisms of free and cofree Hopf algebras

3.1 Bigraduation of a free and cofree graded Hopf algebra Let V be a vector space. A bigraduation of V is a N 2 -graduation of V . If V = (i,j)

V i,j is a bigraded space, the first induced graduation of V is

  j≥0 V i,j   i≥0
and the second induced

graduation of V is   i≥0 V i,j   j≥0 .
There is an immediate notion of bigraded Hopf algebra. A bigraded Hopf algebra H is connected if H 0,0 = K and H 0,j = H i,0 = (0) for all i, j ≥ 1. If H is a connected, bigraded Hopf algebra, then both induced graduation of H are connected.

Lemma 22 (Char(K) = (0)). Let H be a graded, connected, free and cofree Hopf algebra. Consider any bigradation of g [g,g] such that:

1. The first induced graduation on g [g,g] by this bigraduation is the graduation induced by the graduation of H.

2. For all i, j ≥ 0, g [g,g] i,0 = g [g,g] 0,j = (0).

Then there exists a connected bigraduation of H, inducing this bigraduation on g [g,g] .

Proof. We choose a non-degenerate, homogeneous Hopf pairing on H Let us fix a decomposition H = [g, g] ⊕ m ⊕ h ⊕ w of lemma 3. Then h is identified with g [g,g] via the canonical projection. We then define a bigraduation on h, making the canonical projection bihomogenous. It is clear that the first induced graduation on h induced by this bigraduation is the graduation of h. As g is freely generated by h, the bigraduation of h is extended to a graduation of the Lie algebra g = [g, g] ⊕ h. As h i,0 = h 0,j = 0 for all i, j, g i,0 = g 0,j = (0) for all i, j.

We define H m,n by induction on m such that:

1. g n is a bigraded subspace of H n and this bigraduation is the same as the one defined just before.

2. For all i, j, k, l such that i + k = m, H i,j H k,l ⊆ H m,j+l .

3. For all x ∈ H m,n : ∆(x) ∈ i+k=m,j+l=n

H i,j ⊗ H k,l .
For m = 0, it is enough to take H 0,0 = K and H 0,n = (0) if n ≥ 1. Let us assume the result at all ranks < m. As H is free, the bigraduation of H 0 ⊕ . . . ⊕ H m-1 can be uniquely extended to H +2 m = [g, g] m ⊕ m m such that condition 2 is satisfied. Moreover, this clearly extends the bigraduation of g and, for all x ∈ [g, g] m ⊕ m m ⊕ h m , the third point is satisfied, using the induction hypothesis for y and z and the second point if x = yz ∈ H +2 m . It remains to define the bigraduation on w m , such that the third point is satisfied for all x ∈ w m . Let us choose a basis (x i ) i∈I of [g, g] m made of bihomogeneous elements. Let (t i ) i∈I be the dual basis (for the pairing of H) of w n . We give a bigraduation on w n , putting t i bihomogeneous of the same bidegree as x i for all i. Then, for all i ∈ I, if y and z are such that yz is bihomogeneous of a different bidegree, ∆(x), y ⊗ z = x, yz = 0. So ∆(x) is bihomogeneous of the same bidegree as x: the third point is satisfied.

2

j

  are primitive, y ∈ (C H ∩ H +2 ) n . Moreover, y a 1 ,...,a k = 0 by definition of the x (i) j . If y b 1 ,...,b l = 0, then x b 1 ,...,b l = 0 or l > k. By definition of the order on the words, the smallest (b 1 , . . . , b l ) such that y b 1 ,...,b l = 0 is strictly greater that (a 1 , . . . , a k ): as a consequence, y

  We then prove that H and H ′ are isomorphic if, and only if, g [g,g] and g ′ [g ′ ,g ′ ] have the same dimension. As a corollary, FQSym, PQSym, NCQSym, RΠ, SΠ, H LR , YSym, H N CK and its decorated version H D N CK for any non-empty graded set D, H DP , H o , H ho , the free 2-As algebras, and H U BP are isomorphic.

  ∩H ′+2 are isomorphic graded spaces.3. H and H ′ have the same Poincaré-Hilbert formal series. We choose non-degenerate, symmetric, isometric pairings on By theorem 5, there exists symmetric, non-degenerate Hopf pairings on H and H ′ , and inducing the chosen pairings on ∩H ′+2 . By proposition 7, H and H ′ are isomorphic.3 =⇒ 2. We proceed by contraposition: let us assume that ∩H ′+2 are not isomorphic graded spaces. There exists an integer n, such that

	2. g ′ Proof. Clearly, 1 =⇒ 2, 3. g g ′ g∩H +2 and
	2 =⇒ 1. g g∩H +2	n	and	g ′ g ′ ∩H ′+2
	isomorphic spaces if i < n and non-degenerate isometric pairings on g g∩H +2	g g∩H +2 and and g ′ g ′ ∩H ′+2 g ′ g g ′ g∩H +2 and g ′ g g∩H +2 i and are not isomorphic spaces. We choose g ′ g ′ g ′ ∩H ′+2 are i n g g∩H +2 n i g ′ and g ′ ∩H ′+2

n for all n ≥ 1.

  1. The subalgebra H′ n generated by h ′ 1 ⊕ . . . ⊕ h ′ n ⊕ w ′ 1 ⊕ . . . ⊕ w ′′ n is a Hopf subalgebra. 2. Let I n be the ideal of H generated by h ′′ 1 ⊕ . . . ⊕ h ′′ n ⊕ w ′′ 1 ⊕ . . . ⊕ w ′′ n . Then H ′ n ⊥ I n .For n = 0, all these subspaces are 0. Let us assume they are constructed at all rank < n. Let us choose a complement m ′ n of (g∩ H ′ +2 n-1 ) n in (H ′ +2 n-1 ) n . As H n-1 is freely generated by h 1 ⊕. . .⊕h n-1 ⊕w 1 ⊕. . .⊕w n , (H n-1 ) n = H +2 n = (H ′ n-1) n ⊕(I n-1 ) n . By the induction hypothesis, these subspaces are orthogonal. We can then choose a complement m ′′ n

  . Existence. Let us choose a basis (v d ) d∈D formed by homogeneous elements of V , where D is a graded set, such that deg(d) = deg(v d ) for all d ∈ D. Let us consider the Hopf algebra H D P R of plane trees decorated by D decorated by D: from [6], it is free and cofree. Moreover, the plane trees q d , d ∈ D, are linearly independant, primitive elements of H D P R , and the space generated by these elements intersects (H D P R ) +2 on (0). So the elements ( q d ) d∈D are linearly independant elements of +2 generated by the q d is identified with V . The pairing of V can be arbitrarily extended to +2 in a non-degenerate symmetric, homogeneous pairing. This pairing induces a pairing on H D P R by theorem 5. From proposition 16, H D P R contains a graded, connected, free and cofree Hopf subalgebra H ′ , such that Let (s n ) n≥1 be any sequence of integers. There exists a graded, connected, free and cofree, Hopf algebra H such that dim

	g g∩(H D P R ) +2 . The subspace of	g g∩(H D P R ) g
		g∩(H D P R ) g
		g∩H +2	n

g ′ g ′ ∩H ′+2 = V as a graded quadratic space.

Unicity. Comes directly from proposition 7.

2

Corollary 18 (char(K) = 0).

  2. However, at the exception of K[X], all the Hopf algebras of the introduction are isomorphic to a non-commutative Connes-Kreimer Hopf algebra.Here are examples of d n = Card(D n ) for these objects.

		d 1 d 2 d 3 d 4	d 5	d 6	d 7	d 8
	H LR or YSym or H N CK 1 0 0	0	0	0	0	0
	2-As(1)	1 0 1	4	17	76	353	1 688
	FQSym or H ho	1 0 1	6	39	284	2 305	20 682
	P Π or NCQSym	1 1 4 28	240	2 384	26 832	337 168
	PQSym or H o	1 1 7 66	786	11 278	189 391	364 8711
	H U BP	1 1 7 72	962	16 135	330 624	8 117 752
	H DP	1 1 10 148 3 336 112 376 5 591 196	406 621 996
	RΠ or SΠ	1 2 23 432 11 929 456 054 23 186 987 1 518 898 380

Isomorphisms of free and cofree Hopf algebras

Proposition 23 (Char(K) = 0). Let H and H ′ be two graded, connected, free and cofree Hopf algebra. Thery are isomorphic as (non-graded) Hopf algebras if, and only if, dim g

Let us choose a basis (e i ) 1≤i≤n be a basis of g [g,g] made of homogeneous elements. We give g [g,g] a bigraduation, putting e i bihomogenous of degree (deg(e i ), i). By lemma 22, this bigraduation is extended to H. Considering the second induced graduation, H becomes a graded, connected free and cofree Hopf algebra, such that the Poincaré-Hilbert series of g [g,g] is h-h n+1 1-h , with the convention h ∞ = 0. The same can be done with H ′ . By theorem 8, H and H ′ are isomorphic as graded (for the second induced graduation) Hopf algebras.

2

Remark. As g is a free Lie algebra, dim g [g,g] can be interpreted as the number of generators of g.


S Biancamaria

F Hossain

D P Lettenmaier

Forecasting transboundary river water elevations from space

Over 90% of Bangladesh's surface water is generated upstream of its border, yet no real-time information is shared by India (the upstream country) with respect to two major transboundary rivers, the Ganges and Brahmaputra. This constraint limits operational forecasts of river states inside Bangladesh to lead times of no more than three days.

Topex/Poseidon satellite altimetry measurements of water levels in India, combined with insitu measurements inside Bangladesh allow extension of this lead time. We show that for both rivers, it is practically feasible to forecast water elevation anomalies during the critical monsoon season (June to September) near the Bangladesh border with an RMSE of about 0.40 m for lead times up to 5-days. Longer 10-day forecasts have higher errors (RMSE between 0.60 m and 0.80 m) but still provide useful information for operational applications.

These results demonstrate the tremendous potential of satellite altimetry for transboundary river management.

Introduction

Two hundred and fifty-six major river basins, covering 45% of the global land area exclusive of Antarctica and Greenland, are split between two or more countries [START_REF] Wolf | International river basins of the world[END_REF]. The absence of information sharing among some riparian nations has led to numerous tensions in the past [START_REF] Balthrop | A review of state of the art on treaties in relation to management of transboundary flooding in international river basins and the Global Precipitation Measurement mission[END_REF]. A classic case of uncoordinated management of transboundary flooding occurs in the Ganges-Brahmaputra River basins. More than 90% of surface water flowing through Bangladesh comes from the countries upstream -mostly India [START_REF] Nishat | Water resources modeling of the Ganges-Brahmaputra-Meghna river basins using satellite remote sensing data[END_REF]. Hydrological measurements on the Ganges and Brahmaputra Rivers are viewed as sensitive by India, and no treaty provides for sharing of such data between the two nations at operational time scales [START_REF] Balthrop | A review of state of the art on treaties in relation to management of transboundary flooding in international river basins and the Global Precipitation Measurement mission[END_REF]. For this reason, water elevation (WE) forecasts in the interior and southern parts of Bangladesh are limited to lead times of two to three days [START_REF] Ahmad | Regional cooperation in flood management in the Ganges-Brahmaputra-Meghna region: Bangladesh perspective[END_REF]. Increasing this lead time would be very valuable both for disaster preparedness and agricultural water management.

Previous studies have shown that combination of rainfall satellite measurements and modeling can successfully forecast streamflow in Bangladesh [START_REF] Nishat | Water resources modeling of the Ganges-Brahmaputra-Meghna river basins using satellite remote sensing data[END_REF][START_REF] Hopson | A 1-10-day ensemble forecasting scheme for the major river basins of Bangladesh: Forecasting severe floods of 2003-07[END_REF][START_REF] Webster | Extended-range probabilistic forecasts of Ganges and Brahmaputra floods in Bangladesh[END_REF]. In particular, [START_REF] Hopson | A 1-10-day ensemble forecasting scheme for the major river basins of Bangladesh: Forecasting severe floods of 2003-07[END_REF] and [START_REF] Webster | Extended-range probabilistic forecasts of Ganges and Brahmaputra floods in Bangladesh[END_REF] developed a daily 1-15-day flood forecasting system for Bangladesh, based on statistically adjusted (with satellite observations) quantitative precipitation forecasts from the European Centre for Medium-Range Weather Forecasts (ECMWF). This system has successfully forecasted floods since 2004, with an accuracy of ±1 day in flood onset and retreat [START_REF] Webster | Extended-range probabilistic forecasts of Ganges and Brahmaputra floods in Bangladesh[END_REF]. However, [START_REF] Hopson | A 1-10-day ensemble forecasting scheme for the major river basins of Bangladesh: Forecasting severe floods of 2003-07[END_REF] highlight that "if river flow measurements higher up in the catchment were available and could be routed downriver to the forecast location, errors in rainfall-runoff modeling ... could be reduced". Satellite altimetry observations have the potential to provide such information. [START_REF] Birkinshaw | Using satellite altimetry data to augment flow estimation techniques on the Mekong River[END_REF] have used both in-situ and altimetry WE time series on the Mekong basin, combined with hydrologic modeling to forecast discharge downstream. However, in their approach satellite altimetry is one of several data sources, and the impact of the lead time in the context of water management was not investigated. Here we show the potential for satellite altimetry to extend forecast lead time in a case where it is the only source of upstream river stage data.

The Brahmaputra and Ganges Rivers

The locations of the Ganges and Brahmaputra rivers and the political boundaries of the riparian countries are shown in Figure 1. The drainage area of the Ganges basin is about 1,065,000 km 2 . It is shared among China, India, Nepal and Bangladesh. The Brahmaputra has a drainage area of about 574,000 km 2 and is shared among China, India, Bhutan and Bangladesh [START_REF] Nishat | Water resources modeling of the Ganges-Brahmaputra-Meghna river basins using satellite remote sensing data[END_REF].

The upstream-most in-situ gauges in Bangladesh used in this study are located at Hardinge Bridge on the Ganges and at Bahadurabad on the Brahmaputra (Figure 1). WE (referenced to the Public Work Department, PWD datum of Bangladesh Government) have been collected by the Bangladesh Water Development Board (BWDB) and Institute of Water Modeling (IWM, Bangladesh). They are daily (some days missing) and are available from January 2000 to September 2005. Figure 2 shows in-situ WE time series measured at the Bahadurabad (Figure 2.a) and Hardinge Bridge (Figure 2.b) gauges for all years available in the period of record. The Brahmaputra can be considered unregulated with no major hydraulic structures, whereas the Ganges is highly regulated with at least 34 dams and diversion points in India and Nepal [START_REF] Hopson | A 1-10-day ensemble forecasting scheme for the major river basins of Bangladesh: Forecasting severe floods of 2003-07[END_REF]. The hydraulic structures are intended primarily for use during the dry season and do not act as a control structure to regulate flow during the monsoon season [START_REF] Jian | Large-scale controls on Ganges and Brahmaputra river discharge on intraseasonal time-scales[END_REF]. At Bahadurabad and at Hardinge Bridge, the mean annual (monsoon season) discharges are around 16,800 m 3 .s -1 (39,400 m 3 .s -1 ) and 7,100 m 3 .s -1 (24,300 m 3 .s -1 ), respectively. The transboundary region of Meghna is relatively smaller than Ganges and Brahmaputra to have a significant impact on forecasting of WE inside Bangladesh and has not been considered in this study.

Methodology

We used estimates of WE in India derived from the Topex/Poseidon (T/P) satellite nadir altimeter to forecast WE at Bahadurabad and Hardinge Bridge. T/P WE were computed by the Laboratoire d'Etudes en Géophysique et Océanographie Spatiales (LEGOS) and were downloaded from the HydroWeb data base (http://www.legos.obsmip.fr/en/soa/hydrologie/hydroweb/). T/P was a joint National Aeronautics and Space Administration (NASA) and Centre National d'Etudes Spatiales (CNES) satellite mission launched in August 1992, with a 10-day repeat period. In September 2002, the T/P orbit was changed due to the launch of a new satellite altimeter (JASON-1), which defines the T/P HydroWeb period of record from 1993 to mid-2002. Nadir altimeters like T/P measure WE only in a vertical plane, i.e. along the satellite's ground track (shown in Figure 1); therefore, relatively few locations on each river are observed. The locations (referred as "virtual stations") of the T/P measurements on the Ganges and the Brahmaputra in India are shown in 1 shows the distance between each T/P virtual station (VS) used in this study and the in-situ gauge on the river, along with the number of observations available in the T/P time series, the mean time between two consecutive observations, and the river drainage area at the VS. These four VS were selected to span a range of distances from the in-situ gauges and to have a maximum number of observations. Temporal gaps in T/P time series arise from instrument errors, inaccurate atmospheric corrections, and errors due to the retracking of the data and interaction with the surrounding land.

Correlations between the in-situ WE anomalies (h insitu ) measured at the gauge locations and the upstream T/P WE anomalies in India (h alti ) k days earlier were computed as follows:

Corr h  k = cov [ h insitu t ,h alti t+k  ] stdev [ h insitu  t  ] ⋅stdev [ h alti t+k  ] (1)
where k is the lead time, t corresponds to the date for which h alti (t+k) is available (for the few days when h insitu (t) is missing, it was linearly interpolated from the closest measurement in time), cov is the covariance, stdev is the standard deviation and Corr h is the correlation coefficient between the two time series. The lead time k was allowed to vary from 0 to 40 days. For each of these lead times, a linear fit was computed to relate the water surface elevation at the in-situ gauge and the water level at the VS k days earlier.

Forecasting Brahmaputra River WE anomalies

On the Brahmaputra River, correlations between in-situ and upstream T/P WE anomalies are quite high (> 0.9) for lead time up to 25 days over the entire time period; however, this is somewhat misleading as much of the correlation is due to the high and almost concurrent seasonality of WE. For this reason, we computed correlations, for various lead times, only over the monsoon period (June to September) when floods occur. For this period, all correlations for lead times below 10 days are highly significant (p < 0.05). As expected, the highest correlations are for VS n°166_1, which is the closest to Bahadurabad. In-situ and upstream T/P WE anomalies remain significantly correlated (above 0.9 for VS n°166_1 and 0.8 for VS n°242_1 during the monsoon period) for a lead time around 5 days. Correlations for lead times less than 10 days, correlations remain above 0.8 for VS n°166_1, but decrease substantially for lead times greater than 5 days.

For each VS and for lead times less than 5 days, the RMSE between the T/P forecasts and the in-situ measurements for the monsoon period is lower than or near 0.40 m with a minimum around 3 days (which corresponds to the maximum correlation). At lead times greater than 5 days, RMSE increases significantly and tends to stabilize for lead times above 10 days at around or slightly above 0.50 m for VS n°166_1 and 0.70 m for VS n°242_1. These results are very encouraging as the forecast is quite close to the observation. On the other hand, it should be noted that some local maxima (like the one in August 2000) are slightly underestimated in the forecasted time series. This might be due to satellite measurement errors, errors in the T/P-in situ WE regression and the fact that the methodology used does not explicitly account for inflows between the location of the virtual and real gauges.

Forecasting Ganges River WE anomalies

During the monsoon, the correlation for VS n°014_1 (located 530 km upstream of the gauge, Table 1) is maximum for lead time around 5 days and then decreases (it is below 0.9 for lead times above 10 days). As VS n°116_2 is farther upstream from the gauge (1560 km, Table 1), the correlation is lower (still above 0.9 for lead times between 8 and 13 days) and is highest for a 10-day lead time. For lead times greater than 14 days, the correlation decreases and is similar to that for VS n°014_1. The different timing in the occurrence of the maximum correlation between the two VS is due to the large distance (above 1000 km) between them.

As for the Brahmaputra River, RMSE during the monsoon period between in-situ and forecast WE anomalies from T/P data has a minimum around the same lead time that maximizes the correlation. For VS n°014_1 the RMSE is minimum at around 0.40 m for a 5-day lead time and remains between 0.40 m and 0.60 m for lead times below 10 days, beyond which, RMSE increases significantly. For VS n°116_2, the RMSE is higher, and its minimum value is around 0.90 m for a 14-day lead time. This was expected due to the greater distance to the gauge.

Figures 3.c and 3.d show the in-situ and forecasted WE anomalies at the gauge location from T/P VS n°014_1 for a 5-day and a 10-day lead time, respectively. As for the Brahmaputra River, the forecasts remain very close to the in-situ measurements.

Discussion

Our results clearly show that T/P forecasts follow well the rising and receding trends in observed water surface elevation with modest bias. The persistence of high correlations between upstream and downstream WE anomalies for a range of practically useful lead times and the relatively low RMSE, compared to the differences in WE between low and high flows (around 6 m at Bahadurabad and 8 m at Hardinge Bridge, Figure 2), are encouraging. We believe that the relatively high forecast skill is due to the fact that even though the VS are far upstream (see Table 1), most of the runoff that reaches Bangladesh is generated far upstream, and the relationship between upstream and downstream water levels is affected primarily by channel processes. The Brahmaputra drainage area is around 506,000 km 2 at Bahadurabad and 345,000 km 2 at the 550 km upstream T/P VS n°242_1 (Table 1). On the Ganges, the drainage area is 944,000 km 2 at Hardinge Bridge and 756,900 km 2 at T/P VS n°014_1 530 km upstream (Table 1). Therefore, WE are less sensitive to local and short-term precipitation events and remain correlated over long distances. Combined with the higher impact of human activity, this could also explain higher RMSE on the Ganges: as its mean annual discharge is two times lower than that of the Brahmaputra, it is more affected by high frequency variations. For each VS, the ratio between the distance to the in-situ gage and the lead time which gives the maximum correlation is around 1 m.s -1 , the same order as the rivers' velocity [START_REF] Jian | Large-scale controls on Ganges and Brahmaputra river discharge on intraseasonal time-scales[END_REF]. Because T/P data are not available after 2006, data from the new nadir altimeter Jason-2, launched in 2008 on the same orbit than T/P, would need to be used for real time forecast observations. The time latency of Jasonn-2 Interim Geophysical Data Record is around 2 days and the retracking of this product can be done immediately, which means that near real time forecast is feasible.

The current good quality of the forecast might even be improved using ancillary satellite data, such as precipitation or river width estimates. In addition, more accurate satellite-based WE measurements would help to better detect peaks in WE. This could be done by retracking altimeter measurements as suggested by [START_REF] Lee | Louisiana wetland water level monitoring using retracked TOPEX/POSEIDON altimetry[END_REF]. Moreover, the low time resolution in the T/P time series could be addressed by combining forecasts from different VS and using multiple satellite altimeters. Errors on these multi-source forecasts will vary in time depending on the altimeter and the VS used.

The future Surface Water and Ocean Topography (SWOT) wide swath altimeter (a NASA/CNES mission, planned for 2019), will provide much improved forecast coverage (in both geographic extent, and the size of rivers for which coverage will be provided) and accuracy. SWOT will provide 2-D maps of WE along a 120 km wide swath with a 100 m horizontal resolution and a 10 cm minimum vertical accuracy (usually better) [START_REF] Rodríguez | SWOT Science Requirements Document, Jet. Propul. Lab. document[END_REF], providing 2 to 4 observations on the study domain per repeat period (22 days), allowing a much more precise forecast of flooding or low flow events. Furthermore, the approach presented in this paper can augment alternative approaches, like that of [START_REF] Webster | Extended-range probabilistic forecasts of Ganges and Brahmaputra floods in Bangladesh[END_REF], that seek to improve forecast lead times by incorporating long lead probabilistic precipitation forecast information into streamflow forecasts. We also foresee a future pathway by which altimetric information from planned satellites like SWOT can be incorporated into hydrodynamic models.

Conclusions

For both the Ganges and Brahmaputra rivers, it is possible to forecast WE anomalies during the monsoon season from upstream nadir altimeter measurements of WE anomalies with a lead time at least 5 days longer than is currently feasible, with RMSE around 0.40 m. 10-day forecasts during the monsoon season are also feasible, although with RMSE between 0.60 m and 0.80 m, depending on the river and the VS used. Our results demonstrate that satellite altimeter data have a huge potential to improve forecasting of WE anomalies at the Bangladesh borders and, therefore, could provide valuable information for flood forecast systems needed for downstream nations in large transboundary river basins more generally.

Combining satellite altimetry measurements with weather, hydrological, and hydrodynamic forecast methods offers the potential to further extend forecast lead times. The use of multiple altimeter measurements, along with ancillary satellite observations can help to constrain forecast errors. We also emphasize the limitations of current generation satellite altimeters, which were primarily designed for oceanographic applications and are limited by their relatively infrequent repeat periods (10 days for Topex/Poseidon) and relatively inaccurate measurements of river heights. The proposed wide swath SWOT mission is expected to improve greatly both forecast accuracy and time sampling of rivers and may well represent a major breakthrough in the ability of downstream countries to manage riverine hazards. 1. Distance from the in-situ gauge, number of observations, mean and median time between two consecutive observations and river drainage area (from HYDRO1k) for each Topex/Poseidon virtual station (from HydroWeb) on the Ganges and Brahmaputra rivers.

Forecasts using time series from virtual stations in bold are shown in Figure 3. Table Table 1. Distance from the in-situ gauge, number of observations, mean and median time between two consecutive observations and river drainage area (from HYDRO1k) for each Topex/Poseidon virtual station (from HydroWeb) on the Ganges and Brahmaputra rivers.

Forecasts using time series from virtual stations in bold are shown in Figure 3

Figure 1 .

 1 Figure 1. The overlapping time period of T/P with in-situ WE measurements is January 2001 to August 2002 at Hardinge Bridge and January 2000 to August 2002 at Bahadurabad. Table

Figures 3 .

 3 Figures 3.a and 3.b show the in-situ (blue curve) and forecasted WE anomalies at the gauge location from T/P VS n°166_1 (red triangles) for a 5-day and a 10-day lead time, respectively.

Figure 1 .

 1 Figure 1. Map of the study domain. Ganges basin (red hatched area) and Brahmaputra basin (magenta hatched area) boundaries come from HYDRO1k. Locations of measurements from the satellite nadir altimeter Topex/Poseidon on the Ganges and the Brahmaputra rivers (available on HydroWeb) are represented, respectively, by red and purple dots (yellow lines correspond to the satellite ground tracks). Green dots correspond to the furthest upstream insitu gauges in Bangladesh. The background topography used in this map is the ETOPO1 topography dataset. Lakes, rivers and political boundaries come from the CIA World Data Bank II.

Figure 2 .

 2 Figure 2. In-situ water elevation time series measured on the Brahmaputra at Bahadurabad (a) and on the Ganges at Hardinge Bridge (b).

Figure 3 .

 3 Figure 3. (a) Measured water elevation anomaly time series at Bahadurabad (blue) and the T/P virtual station n°166_1 forecasted water elevation anomalies at the gauge location for a 5day lead time (red triangles). (b) Similar plot for 10-day lead time T/P virtual station n°166_1 forecasted water elevation anomalies. (c) Measured water elevation anomaly time series at Hardinge Bridge (blue) and the T/P virtual station n°014_1 forecasted water elevation anomalies at the gauge location for a 5-day lead time (red triangles). (d) Similar plot for 10day lead time T/P virtual station n°014_1 forecasted water elevation anomalies. Plots of the linear fit between time-lagged T/P and in-situ time series used to compute these forecasts are included in the auxiliary materials.

Table Legend :

 Legend Table

  .

	Figures
	Figure 1:
	T/P Virtual station	River	Distance to the gauge (km)	Number of obs.	Mean/median time btw obs. (days)	Drainage area (km 2 )
	166_1	Brahmaputra 250	58	16/10	408,500
	242_1	Brahmaputra	550	71	14/10	345,100
	014_1	Ganges	530	25	22/20	756,900
	116_2	Ganges	1560	49	12/10	38,400

Acknowledgements

The BWDB and IWM are gratefully acknowledged for providing the in-situ measurements used in this study. These data were available to the second author (F. Hossain) as part a Memorandum of Understanding between Tennessee Technological University and IWM for technical collaboration and staff training. We also thank the LEGOS for processing and releasing T/P time series via the HydroWeb database. We are thankful to E. A. Clark of the University of Washington for thoughtful comments on earlier version of the manuscript. We gratefully acknowledge Hyongki Lee and Peter Webster, both of whom identified themselves as reviewers of the paper, for their helpful comments and suggestions, which we believe improved the quality of the paper. This study was funded by the NASA Grant No.

NNX07AT12G to the University of Washington.