Arzu Boysal

Michèle Vergne

Paradan's wall crossing formula for partition functions and Khovanski-Pukhlikov differential operator

Introduction

The function computing the number of ways one can decompose a vector as a linear combination with nonnegative integral coefficients of a fixed finite set of integral vectors is called a partition function. This problem can be expressed in terms of polytopes as follows. Let A be a r by N integral matrix with column vectors φ 1 , . . . , φ N , and assume that the elements φ k generate the lattice Z r . Let a ∈ Z r be a r-dimensional integral column vector and let P (Φ, a) := {y ∈ R N ≥0 |Ay = a} be the convex polytope associated to Φ = [φ 1 , φ 2 , . . . , φ N ] and a. The number of ways one can decompose a as a linear combination with nonnegative integral coefficients of the vectors φ i is the number of integral points in P (Φ, a). The function a → |P (Φ, a)∩Z N | will be called the partition function k(Φ)(a). It is intuitively clear that k(Φ)(a) is related to the volume function vol(Φ)(a) = volume(P (Φ, a)). The latter varies polynomially as a function of a, provided the polytope P (Φ, a) does not change 'shape', that is, when a varies in a chamber c for A. In short, there is a decomposition of R r in closure of chambers c i and polynomial functions v(Φ, c i ) such that the function vol(Φ)(a) coincide with the polynomial function v(Φ, c i )(a) on each cone c i . Similarly, there exists quasi-polynomial functions k(Φ, c i ) on Z r such that the function k(Φ)(a) coincide with the quasi-polynomial function k(Φ, c i )(a) on c i ∩ Z r .

When c 1 and c 2 are adjacent chambers, P-E. Paradan [START_REF] Paradan | Jump formulas in Hamiltonian Geometry[END_REF] gave a remarkable formula for the quasi-polynomial function k(Φ, c 1 )-k(Φ, c 2 ) as a convolution of distributions. There is an analogous formula for v(Φ, c 1 ) -v(Φ, c 2 ). In this note, we give an elementary algebraic proof of Paradan's convolution formula for the jumps. We also express k(Φ, c 1 ) -k(Φ, c 2 ) and v(Φ, c 1 ) -v(Φ, c 2 ) by one-dimensional residue formulae. Let us describe these residue formulae.

Let c 1 and c 2 be two adjacent chambers lying on two sides of a hyperplane W (determined by a primitive vector E). Define Φ 0 = Φ ∩ W . The intersection of c 1 and c 2 is contained in the closure of a chamber c 12 of Φ 0 .

Theorem 1

• Let v 12 = v(Φ 0 , c 12 ) be the polynomial function on W associated to the chamber c 12 of Φ 0 . Let V 12 be any polynomial function on R r extending v 12 . Then, if E, c 1 > 0, we have for a ∈ R r v(Φ, c 1 )(a)v(Φ, c 2 )(a) = Res z=0 V 12 (∂ x ) • e a,x+zE φ∈Φ\Φ 0 φ, x + zE x=0 .

• Suppose Φ is unimodular. Let k 12 = k(Φ 0 , c 12 ) be the polynomial function on W associated to the chamber c 12 of Φ 0 . Let K 12 be any polynomial function on R r extending k 12 . Then, if E, c 1 > 0, we have for

a ∈ R r k(Φ, c 1 )(a)-k(Φ, c 2 )(a) = Res z=0 K 12 (∂ x ) • e a,x+zE φ∈Φ\Φ 0 (1 -e -φ,x+zE ) x=0 .
In fact we will give a general version of the second part of this theorem in Section 6, where Φ is not necessarily unimodular.

It is immediate to see that both formulae for the jumps k(Φ, c 1 )k(Φ, c 2 ) and v(Φ, c 1 )-v(Φ, c 2 ) are related by the application of a generalized Khovanski-Pukhlikov differential operator [START_REF] Dahmen | The number of solutions to linear Diophantine equations and multivariate splines[END_REF], [START_REF] Khovanskii | The Riemann-Roch theorem for integrals and sums of quasi-polynomials on virtual polytopes (Russian)[END_REF], [START_REF] Brion | Residue formulae, vector partition functions and lattice points in rational polytopes[END_REF].

We also demonstrate in various examples how to use these formulae to compute the functions v(Φ, c) and k(Φ, c). 2 Partition functions

List of Notations

Definitions and notations

Let U be a r-dimensional real vector space and V be its dual vector space. We assume that V is equipped with a lattice Γ. We will usually denote by x the variable in U and by a the variable in V . We will see an element P of S(V ) both as a polynomial function on U and a differential operator on V via the relation P (∂ a )e a,x = P (x)e a,x . Let Φ = [φ 1 , φ 2 , . . . , φ N ] be a sequence of non-zero, not necessarily distinct, linear forms on U lying in an open half space. Assume that all the φ k ∈ Φ belong to the lattice Γ. We denote by < Φ > the linear span of Φ. Then Φ generates a lattice in < Φ >. We denote this lattice by ZΦ ⊂ Γ.

We consider R N with basis (ω 1 , . . . , ω N ) and let A be the linear map from R N to the vector space < Φ > defined by

A(ω k ) = φ k , 1 ≤ k ≤ N.
The vectors φ k are the column vectors of the matrix A, and the map A is surjective onto < Φ >. For a ∈< Φ >, we consider the convex polytope

P (Φ, a) := {t = (t 1 , t 2 , . . . , t N ) ∈ R N ≥0 | At = a}.
In other words,

P (Φ, a) = {t = (t 1 , t 2 , . . . , t N ) ∈ R N ≥0 | i t i φ i = a}.
Any polytope can be realized as a polytope P (Φ, a). Let C(Φ) ⊂< Φ > be the cone generated by {φ 1 , . . . , φ N }. The cone C(Φ) is a pointed polyhedral cone. The dual cone C(Φ) * of C(Φ) is defined by C(Φ) * = {x ∈ U | φ, x ≥ 0 for all φ ∈ Φ} and its interior is non-empty.

The polytope P (Φ, a) is empty if a is not in C(Φ). If a ∈< Φ > is in the relative interior of the cone C(Φ), then the polytope P (Φ, a) has dimension d := Ndim(< Φ >).

We choose dx on < Φ > * and denote by da the dual measure on < Φ >. Let dt be the Lebesgue measure on R N . The vector space Ker(A) = A -1 (0) is of dimension d = Ndim(< Φ >) and it is equipped with the quotient Lebesgue measure dt/da satisfying (dt/da)∧da = dt. For a ∈< Φ >, A -1 (a) is an affine space parallel to Ker(A), thus also equipped with the Lebesgue measure dt/da. Volumes of subsets of A -1 (a) are computed with this measure. In particular we can define for any a ∈< Φ >, the number vol(Φ)(a, dx) as being the volume of the convex set P (Φ, a) in the affine space A -1 (a) equipped with the measure dt/da. If dx is rescaled by c > 0, then vol(Φ)(a, cdx) = c vol(Φ)(a, dx). By definition, if the dimension of P (Φ, a) is less than d, vol(Φ)(a, dx) is equal to 0. Definition 2 Let < Φ > be the subspace of V generated by Φ.

• If a ∈< Φ >, define vol(Φ, dx)(a) = volume(P (Φ, a), dt/da). • If a ∈< Φ >, define k(Φ)(a) = |P (Φ, a) ∩ Z N |.
We extend the definition of the functions vol(Φ, dx)(a) and k(Φ)(a) as functions on V by defining vol(Φ, dx

)(a) = 0 if a / ∈< Φ >, k(Φ)(a) = 0 if a / ∈< Φ >. Clearly, vol(Φ, dx)(a) = 0 if a is not in C(Φ) and k(Φ, a) = 0 if a is not in ZΦ ∩ C(Φ).
In the rest of this article, we will formulate many of our statements when Φ generates V , as we can always reduce to this case replacing eventually V by < Φ >.

If Φ = [φ 1 , φ 2 , . . . , φ r ] consists of linearly independent vectors, then the set P (Φ, a) is just one point when a ∈ C(Φ) and is empty when a is not in the closed cone C(Φ). Thus the function vol(Φ)(a, dx) is just the characteristic function of the closed cone C(Φ) multiplied by | det(Φ)| -1 where the determinant is computed with respect to the Lebesque measure da. Similarly, the function k

(Φ)(a) is the characteristic function of C(Φ) ∩ r i=1 Zφ i . Lemma 3 Assume Φ = Φ ′ ∪ {φ} where Φ ′ generates < Φ >. Then vol(Φ, dx)(a) = t≥0 vol(Φ ′ , dx)(a -tφ)dt for any a ∈ V . Proof. Indeed, decompose Φ = [φ, Φ ′ ]. Then P (Φ, a) = {[t, t ′ ]; t ≥ 0, t ′ ∈ P (Φ ′ , a -tφ)}.
The proof follows by Fubini.

By induction, we obtain the following corollary.

Corollary 4 If Φ consists of linearly independent vectors, the function vol(Φ, dx)(a) is continuous on C(Φ). If Φ generates V with |Φ| > dim V , then the function vol(Φ, dx)(a) is continuous on V .
For an element γ in V , define the translation operator τ (γ) on functions k(a) on V by the formula: if a ∈ V , then

(τ (γ)k)(a) = k(a -γ).
The difference operator D(γ) = 1τ (γ) acts on functions k(a) on V by the formula:

(D(γ)k)(a) = k(a) -k(a -γ).
The following lemma is obvious from the definition.

Lemma 5 Let φ ∈ Φ and a ∈ Γ. Then

k(Φ)(a) = ∞ n=0 k(Φ \ {φ})(a -nφ).
The following relation follows immediately.

Lemma 6 Let φ ∈ Φ and a ∈ Γ. Then

(D(φ)k(Φ))(a) = k(Φ \ {φ})(a).
In particular, (D(φ)k(Φ))(a) is equal to 0 if a is not in the subspace of V generated by Φ \ {φ}.

Lemma 7 Assume Φ generates V . Let W be a hyperplane in V such that W ∩ C(Φ) is a facet of C(Φ). Let Φ 0 be the sequence Φ ∩ W which spans W . If a ∈ W , then k(Φ)(a) = k(Φ 0 )(a). Proof. As W ∩ C(Φ) is a facet of C(Φ), if a ∈ W ∩ C(Φ), any solution of a = N i=1 y i φ i with y i ≥ 0 will have y i = 0 for φ i / ∈ W .
The following lemma is also obtained immediately from Fubini's theorem applied to the integral vol(Φ, dx)(a)e -a,x da = 1

R N ≥0 e -N i=1 t i φ i ,x dt 1 dt 2 • • • dt N decomposed
φ∈Φ φ, x , a∈C(Φ)∩Γ k(Φ)(a)e -a,x = 1 φ∈Φ 1 -e -φ,x .

Chambers and the qualitative behavior of partition functions

In this section, we assume that Φ generates V . For any subset ν of Φ, we denote by C(ν) the closed cone generated by ν. We denote by C(Φ) sing the union of the cones C(ν) where ν is any subset of Φ of cardinality strictly less than r = dim(V ). By definition, the set C(Φ) reg of Φ-regular elements is the complement of C(Φ) sing . A connected component of C(Φ) reg is called a chamber. We remark that, according to our definition, the exterior of C(Φ) is itself a chamber denoted by c ext . The chambers contained in C(Φ) will be called interior chambers. If c is a chamber, and σ is a basis of V contained in Φ, then either c ⊂ C(σ), or c ∩ C(σ) = ∅, as the boundary of C(σ) does not intersect c. Let Φ ′ ⊂ Φ be such that Φ ′ generates V . If c is a chamber for Φ, there exists a unique chamber c ′ for Φ ′ such that c ⊂ c ′ .

A wall of Φ is a (real) hyperplane generated by r -1 linearly independent elements of Φ. It is clear that the boundary of a chamber c is contained in an union of walls.

We now define the notion of a quasi-polynomial function on the lattice Γ. Let Γ * be the dual lattice of Γ. An element x ∈ U gives rise to the exponential function e x (a) = e 2iπ x,a on Γ. Remark that the function e x (a) depends only of the class of x (still denoted by x) in the torus T (Γ) := U/Γ * .

Let M be a positive integer. A quasi-polynomial function with period M on Γ is a function K on Γ of the form K(a) = x∈F e x (a)P x (a) where F is a finite set of points of U such that MF ⊂ Γ * and P x are polynomial functions on V . Then the restriction of the function K to cosets h + MΓ of Γ/MΓ coincide with the restriction to h + MΓ of a polynomial function on V . If the degree of the polynomial P x (a) is less or equal to k for all x ∈ F , we say that K is a quasi-polynomial function of degree k and period M.

If Γ = Z and γ ∈ C * is a M th root of unity, the function n → n k γ n is a quasi-polynomial function on Z of period M and degree k.

If C is an affine closed cone in V with non empty interior, a quasipolynomial function on Γ vanishing on Γ ∩ C is identically equal to 0 on Γ.

If γ ∈ Γ, the difference operator D(γ)k(a) = k(a)k(aγ) leaves the space of quasi-polynomial functions on Γ stable.

The following theorem is well known (see [START_REF] Dahmen | The number of solutions to linear Diophantine equations and multivariate splines[END_REF], [START_REF] Brion | Residue formulae, vector partition functions and lattice points in rational polytopes[END_REF], [START_REF] Szenes | Residue formulae for vector partitions and Euler-MacLaurin sums[END_REF], [START_REF] Concini | Topics in hyperplane arrangements[END_REF]). See yet another proof in the forthcoming article [START_REF] Concini | Partition functions and Dahmen-Miccelli quasi-polynomials[END_REF].

Proposition 9 Let c be an interior chamber of C(Φ).

• There exists a unique homogeneous polynomial function v(Φ, dx, c) of degree d on V such that, for a ∈ c, vol(Φ, dx)(a) = v(Φ, dx, c)(a).

• There exists a unique quasi-polynomial function k(Φ, c) on Γ such that,

for a ∈ c ∩ Γ, k(Φ)(a) = k(Φ, c)(a).
Remark 10 The sequence Φ is called unimodular if, for any subset σ of Φ forming a basis of V , the subset σ is a basis of ZΦ. In other words, we have | det(σ)| = 1, where the determinant is computed using the volume da giving volume 1 to a fundamental domain for ZΦ. In this particular case, the function k(Φ, c) is polynomial on ZΦ.

In the next lemma, we list differential equations satisfied by the polynomial function v(Φ, dx, c).

Lemma 11 Let φ ∈ Φ. If Φ\{φ} does not generate V , then ∂(φ)v(Φ, dx, c) = 0.
If Φ \ {φ} generates V , let c ′ be the chamber of Φ \ {φ} containing c, then

∂(φ)v(Φ, dx, c) = v(Φ \ {φ}, dx, c ′ ).

Proof.

If Φ 0 = Φ \ {φ} is contained in a wall W , then V = W ⊕ Rφ, and it is immediate to see that an interior chamber c for Φ is of the form c = c 0 + R >0 φ, where c 0 is a chamber for Φ 0 . If a = w + tφ with w ∈ W and t > 0, then vol(Φ, dx, c)(w + tφ) = vol(Φ 0 , dx 0 , c 0 )(w), with dx 0 dφ = dx. This proves the first statement.

To prove the second statement, if a ∈ c, we use the following relation (as

given in Lemma 3) vol(Φ, dx)(a) -vol(Φ, dx)(a -ǫφ) = ǫ t=0 vol(Φ 0 , dx)(a -tφ)dt. Corollary 12 Let Φ 0 ⊂ Φ such that Φ 0 does not generate V . Then ( φ∈Φ\Φ 0 ∂(φ))v(Φ, dx, c) = 0.
In the next lemma, we list difference equations satisfied by the quasipolynomial function k(Φ, c).

Lemma 13 Let φ ∈ Φ. If Φ\{φ} does not generate V , then D(φ)k(Φ, c) = 0.

If Φ \ {φ} generates V , let c ′ be the chamber of Φ \ {φ} containing c, then

D(φ)k(Φ, c) = k(Φ \ {φ}, c ′ ) Proof. By Lemma 6, the function k(Φ) satisfies D(φ)k(Φ) = k(Φ \ {φ}).
Considering this relation on an affine subcone S of c such that Sφ does not touch the boundary of c, we obtain the relations of the lemma.

Two polynomial functions 3.1 Residue formula

Let L be the space of Laurent series in one variable z:

L := {f (z) = k≥k 0 f k z k }.
For f ∈ L, we denote by Res z=0 f (z) the coefficient f -1 of z -1 . If g is a germ of meromorphic function at z = 0, then g gives rise to an element of L by considering the Laurent series at z = 0 and we still denote by Res z=0 g its residue at z = 0. If g = d dz f , then Res z=0 g = 0. With the notation of Section 2.1, let E be a vector in U. It defines a hyperplane

W = {a ∈ V | a, E = 0} in V .
Definition 14 Let P be a polynomial function on V and let Ψ be a sequence of vectors not belonging to W . We define, for a ∈ V ,

• Pol(P, Ψ, E)(a) = Res z=0 P (∂ x ) • e a,x+zE ψ∈Ψ ψ,x+zE x=0 . • Par(P, Ψ, E)(a) = Res z=0 P (∂ x ) • e a,x+zE ψ∈Ψ (1-e -ψ,x+zE ) x=0
.

It is easy to see that Pol(P, Ψ, E)(a) as well as Par(P, Ψ, E)(a) are polynomial functions of a ∈ V .

Lemma 15 The functions Pol(P, Ψ, E) and Par(P, Ψ, E) depend only on the restriction p of P to W .

Proof. If p = 0, then P = EQ where Q is a polynomial function on V . Then P (∂ x )F (x + zE) = d dǫ Q(∂ x )F (ǫE + x + zE) ǫ=0 = d dǫ Q(∂ x )F (x + (z + ǫ)E) ǫ=0 = d dz (Q(∂ x )F (x + zE)) so that the residue Res z=0 vanishes on the function z → P (∂ x )F (x + zE) x=0 .
We can then give the following definitions.

Definition 16 Let p be a polynomial function on W . We define

Pol(p, Ψ, E) := Pol(P, Ψ, E)
where P is any polynomial on V extending p.

We define Par(p, Ψ, E) := Par(P, Ψ, E)

where P is any polynomial on V extending p.

In the following, given polynomials p, q, . . . on W , we denote by P, Q, . . . polynomials on V extending p, q, . . ..

Some properties

Let us list some properties satisfied by the function Pol(p, Ψ, E).

We first remark that if we replace ψ in Ψ by cψ with c = 0, then Pol(p, Ψ, E) becomes 1 c Pol(p, Ψ, E). We now discuss how Pol(p, Ψ, E) transforms under the action of differentiation.

Proposition 17 Let ψ ∈ Ψ. Then ∂(ψ)Pol(p, Ψ, E) = Pol(p, Ψ \ {ψ}, E). Let w ∈ W . Then ∂(w)Pol(p, Ψ, E) = Pol(∂(w)p, Ψ, E).
Proof. The first formula follows immediately from the definition.

For the second part of the proposition, we will use the following lemma, which is implied by the relation

P (∂ x ) x, w -x, w P (∂ x ) = (∂(w)P )(∂ x ).
Lemma 18 For any function J(x) of x ∈ U,

P (∂ x ) x, w J(x) x=0 = (∂(w)P )(∂ x )J(x) x=0 . Now, as w, E = 0, for J(x, z) = 1 ψ∈Ψ ψ,x+zE , we have ∂(w)Res z=0 P (∂ x )e a,x+zE J(x, z) x=0 = Res z=0 P (∂ x ) w, x e a,x+zE J(x, z) x=0 = Res z=0 (∂(w)P )(∂ x )e a,x+zE J(x, z) x=0 .
So we obtain the formula of the proposition.

Lemma 19

• If Ψ = {ψ}, then for w ∈ W and t ∈ R, Pol(p, {ψ}, E)(w + tψ) = Par(p, {ψ}, E)(w + tψ) = p(w) ψ, E . • If |Ψ| > 1, then the restriction of Pol(p, Ψ, E) to W vanishes of order |Ψ| -1.
Proof. Let U 0 = {x| ψ, x = 0}. We write U = U 0 ⊕ RE. The space S(U 0 ) is isomorphic to the space of polynomial functions on W . We may choose P in S(U 0 ). We write x = x 0 + x 1 E, with x 0 ∈ U 0 . In these coordinates ψ, x + zE = (x 1 + z) ψ, E is independent of x 0 . So we can set x 1 = 0 in the formula

Res z=0 P (∂ x 0 ) • e a,x+zE (x 1 + z) ψ, E x=0
and the residue is computed for a function that have a simple pole at z = 0. The formula follows. The other points are also easy to prove.

Let us list some difference equations satisfied by the function Par(p, Ψ, E).

Proposition 20 Let ψ ∈ Ψ. Then D(ψ)Par(p, Ψ, E) = Par(p, Ψ \ {ψ}, E). Let w ∈ W . Then τ (w)Par(p, Ψ, E) = Par(τ (w)p, Ψ, E).
Proof. The first formula follows immediately from the definition.

The translation operator τ (w) satisfies the relation

P (∂ x )e -w,x = e -w,x (τ (w)P )(∂ x ).
Thus, the second formula follows from the same argument as in the proof of the second item in Proposition 17.

Wall crossing formula for the volume

In this section, we give two formulae for the jump of the volume function across a wall. The first one uses convolutions of Heaviside distributions and is in the spirit of Paradan's formula ([8], Theorem 5.2) for the jump of the partition function. The second one is a one dimensional residue formula.

Inversion formula

We will need some formulae for Laplace transforms in dimension 1. For z > 0 and k ≥ 0 an integer, we have

(1) 1 z k+1 = ∞ 0 t k k! e -tz dt.
Consider the Laplace transform

L(p)(z) = R + e -tz p(t)dt. Assume that p(t) = ik c ik p i,k (t) is a linear combination of the functions p i,k (t) = e -tx i t k k! . We assume that x i > 0. Then, the integral defining L(p) is convergent. We have (2) L(p)(z) = i,k c ik (z + x i ) k+1 .
The following inversion formula is immediate to verify.

Lemma 21 Let R > 0. Assume that |x i | < R for all i. Then we have (3) p(t) = 1 2iπ |z|=R L(p)(z)e tz dz.
Reciprocally, if p is a continuous function on R such that L(p)(z) is convergent and given by Formula (2), then p is given by Equation

(3). If p(t) = k c k t k
k! is a polynomial (that is all the elements x i are equal to 0), then L(p)(z) is the Laurent polynomial k c k z -k-1 , and the inversion formula above reads ( 4)

p(t) = Res z=0 L(p)(z)e tz .

Convolution of measures

Let E ∈ U be a non zero linear form on V and W ⊂ V the corresponding hyperplane. Let

V + = {a ∈ V | a, E > 0} and V -= {a ∈ V | a, E < 0} denote the corresponding open half spaces. Let ∆ + = [α 1 , α 2 , . . . , α Q ] be a sequence of vectors contained in V + . Consider the span < ∆ + > of ∆ + .
We choose a Lebesgue measure da on < ∆ + > with dual measure dx on < ∆ + > * . We define the continuous function v(∆ + , dx)(a) on the cone C(∆ + ) ⊂< ∆ + > such that, for x ∈ C(∆ + ) * , we have ( 5)

1 α∈∆ + α, x = C(∆ + ) v(∆ + , dx)(a)e -a,x da. By Lemma 8, v(∆ + , dx)(a) = vol(∆ + , dx)(a).
We choose the Lebesgue measure dw = da/dt on W ∩ < ∆ + > where t = a, E . The measure dw determines a measure on all affine spaces W ∩ (a+ < ∆ + >).

Proposition 22 Let p be a polynomial function on W . We define

(p * v(∆ + , dx))(a) = W ∩(a+<∆ + >) p(w)v(∆ + , dx)(a -w)dw.
Then, for a ∈ V + , we have

(p * v(∆ + , dx))(a) = Pol(p, ∆ + , E)(a) for a ∈ V + .
Remark that p * v(∆ + , dx) depends only on the choice of E. Indeed, p * v(∆ + , dx) is the convolution of two functions, one of which depends on the measure dx, while the convolution depends on the measure dw. We see that finally this depends only of the choice of E.

We also remark that, for fixed a ∈ V + , the integral defining p * v(∆ + , dx) is in fact over the compact set W ∩ (a -C(∆ + )) where v(∆ + , dx)(aw) is not equal to zero . Proof.

We decompose W = W 0 ⊕ W 1 , where W 0 = W ∩ < ∆ + >. Then, we can write a ∈ V as a = tF + w 0 + w 1 , with F, E = 1. If p(w 0 + w 1 ) = p 0 (w 0 )p 1 (w 1 ), we see that (p * v(∆ + , dx))(tF + w 0 + w 1 ) = p 1 (w 1 )(p 0 * v(∆ + , dx))(tF +w 0 ). Hence, it is sufficient to prove the proposition in the case where ∆ + generates V . Then

(p * v(∆ + , dx))(a) = W p(w)v(∆ + , dx)(a -w)dw.
The polynomial nature of (p * v(∆ + , dx))(a) is clear intuitively. In any case, we will prove the explicit formula of the proposition, which gives a polynomial formula for (p * v(∆ + , dx))(a).

We need to compute, for a ∈ V + , I(a) := W p(w)v(∆ + , dx)(aw)dw. This integral is over a compact subset of W . Let P ∈ S(U) be a polynomial function on V extending p. We may write

I(a) = P (∂ x ) • W v(∆ + , dx)(a -w)e w,x dw x=0 . Define g x (a) = W v(∆ + , dx)(a -w)e -a-w,x dw.
Then g x (a) depends analytically on the variable x ∈ U, and we have ( 6)

I(a) = P (∂ x ) • e a,x g x (a) | x=0 .
The function a → g x (a) = W v(∆ + , dx)(aw)e -a-w,x dw is a continuous function of a modulo W , that is, it is a continuous function of the variable t = a, E ≥ 0 when a ∈ V + . We then write g x (t) = g x (tF ) = W v(∆ + , dx)(tFw)e -tF -w,x dw.

To identify the function g x (t), we compute its Laplace transform in one variable. Let z > 0. If x is in C(∆ + ) * , the integral defining L(g x ) is convergent and we have

L(g x )(z) = t>0 e -tz g x (tF )dt = V + e -a,zE v(∆ + , dx)(a)e -a,x da = 1 α∈∆ + α,x+zE
by Formula (5). Here α, x + zE = d α z + α, x with d α = α, E > 0 and α, x > 0. Thus, by partial fraction decomposition, L(g x )(z) is a function of the type given by Formula (2). By the inversion formula for the Laplace transform in one variable, we obtain that (for x small enough)

g x (a) = 1 2iπ |z|=1 e a,zE α∈∆ + α, x + zE dz.
Thus Formula (6) becomes

I(a) = P (∂ x ) • e a,x 1 2iπ |z|=1 e a,zE α∈∆ + α, x + zE dz x=0 = 1 2iπ |z|=1 P (∂ x ) • e a,x+zE α∈∆ + α, x + zE x=0 dz.
The function in the integrand has a Laurent series at z = 0 with polynomial coefficients in a of the form k g k (a)z k . Thus we obtain

I(a) = Res z=0 P (∂ x ) • e a,x+zE α∈∆ + α, x + zE x=0
.

This shows that I(a) coincide with the polynomial function Pol(p, ∆ + , E) on V + .

We also remark that, if p is homogeneous,

Pol(p, ∆ + , E) is homogenous in a of degree |∆ + | -1 + deg(p).

The jump for the volume function

Let vol(Φ, dx) be the locally polynomial function on the cone C(Φ) generated by Φ. Let W be a wall, determined by a vector E ∈ U. Let V + and V - denote the corresponding open half spaces. Define Φ 0 = Φ ∩ W ; this is a sequence of vectors in W spanning W .

Let c 1 ⊂ V + and c 2 ⊂ V -be two chambers on two sides of W and adjacent. Here, we mean that c 1 ∩ c 2 has non empty relative interior in W . Thus c 1 ∩ c 2 is contained in the closure of a chamber c 12 of Φ 0 . We choose the measure dw on W such that da = dwdt with t = a, E . We write

Φ = [Φ 0 , Φ + , Φ -] where Φ + = Φ ∩ V + and Φ -= Φ ∩ V -. Let R + (Φ) = [φ|φ ∈ Φ + ] ∪ [-φ|φ ∈ Φ -].
By construction, the sequence R + (Φ) is contained in V + .

Theorem 23 Let v 12 = v(Φ 0 , dw, c 12 ) be the polynomial function on W associated to the chamber

c 12 of Φ 0 . Then, if E, c 1 > 0, (7) v(Φ, dx, c 1 ) -v(Φ, dx, c 2 ) = Pol(v 12 , Φ \ Φ 0 , E).
Remark 24 We have

Pol(v 12 , Φ \ Φ 0 , E) = (-1) |Φ -| Pol(v 12 , R + (Φ), E).
Thus, by results of the preceding section, the difference of the volume functions v(Φ, dx, c 1 )v(Φ, dx, c 2 ) coincides on V + , up to sign, with the convolution of the polynomial measure v 12 (w)dw associated to the chamber c 12 and with the Heaviside distributions associated to the vectors ψ ∈ R + (Φ). This is in the line of Paradan's description of the jump formula for partition functions ([8], Theorem 5.2) .

Proof. Denote by Leq(Φ) the left hand side and by Req(Φ) the right hand side of Equation ( 7) above.

We will first verify the claim in the theorem when there is only one vector φ of Φ that does not lie in W . We can suppose that Φ + = {φ} and that E, φ = 1. Then the chamber c 1 is equal to c 12 ×R >0 φ, while c 2 is the exterior chamber. In this case, v(Φ, dx, c 1 )(w + tφ) = v(Φ 0 , (dw) * , c 12 )(w) = v 12 (w), while v(Φ, dx, c 2 ) = 0. The equation [START_REF] Khovanskii | The Riemann-Roch theorem for integrals and sums of quasi-polynomials on virtual polytopes (Russian)[END_REF] follows from the first item of Lemma 19.

If not, then |Φ| > dim(V ) and the function vol(Φ, dx) is continuous on V by Corollary 4. Let φ be a vector in Φ that does not lie in W . We may assume that φ ∈ V + . Then the sequence Φ ′ = Φ \ {φ} will still span V . The intersection of Φ ′ with W is Φ 0 . If c ′ 1 and c ′ 2 are the chambers of Φ ′ containing c 1 and c 2 respectively, they are adjacent with respect to W . As Φ ′ ∩ W = Φ 0 , the polynomial v ′ 12 attached to c 12 and Φ ′ ∩ W is equal to v 12 . By Lemma 11, we have

∂(φ)(v(Φ, c 1 ) -v(Φ, c 2 )) = v(Φ ′ , c ′ 1 ) -v(Φ ′ , c ′ 2 ).
By Proposition 17,

∂(φ)Pol(v 12 , Φ \ Φ 0 , E) = Pol(v 12 , Φ ′ \ Φ 0 , E).
By induction, we obtain ∂(φ)(Leq(Φ) -Req(Φ)) = 0. Thus the polynomial function Leq(Φ) -Req(Φ) is constant in the direction Rφ. The left hand side vanishes on W , as the function vol(Φ) is continuous on V . The right hand side also vanishes by Lemma 19. This establishes the theorem.

Consider a vector space V with basis {e i , i : 1, . . . , r}; we denote its dual basis by {e i }. The set is the set of positive roots for the system of type B r and generates V . We will denote a vector a ∈ V by a = r i=1 a i e i ; it lies in C(Φ(B r )) if and only if a 1 + • • • + a i ≥ 0 for all i : 1, . . . , r. This will be our notation for this root system in subsequent examples.

Φ(B r ) = {e i , 1 ≤ i ≤ r} ∪ {e i + e j , 1 ≤ i < j ≤ r} ∪ {e i -e j , 1 ≤ i < j ≤ r}
Example 25 We consider the root system of type B 2 (see Figure 1) with Φ = {e 1 , e 2 , e 1e 2 , e 1 + e 2 }. We will calculate v(Φ, c) for all the chambers using our formula in Theorem 23 iteratively starting from the exterior chamber.

(i) Jump from the exterior chamber to c 1 (W = Re 2 ): In this case

E = e 1 , Φ 0 = {e 2 }, Φ + = {e 1 + e 2 , e 1 , e 1 -e 2 } and Φ -= ∅. v(Φ, c 1 )(a) -v(Φ, c ext )(a) = Pol(1, Φ \ Φ 0 , E)(a) = Res z=0 e a,x+ze 1 φ∈Φ + ∪Φ -φ,x+ze 1 x=0 = Res z=0 e a 1 (x 1 +z)+a 2 x 2 (x 1 +z+x 2 )(x 1 +z)(x 1 +z-x 2 ) x=0 v(Φ, c 1 )(a) = Res z=0 e a 1 z z 3 = 1 2 a 2 1 . (ii) Jump from c 1 to c 2 (W = R(e 1 + e 2 )): We have E = e 1 -e 2 , Φ 0 = {e 1 + e 2 }, Φ + = {e 1 , e 1 -e 2 } and Φ -= {e 2 }. v(Φ, c 2 )(a) -v(Φ, c 1 )(a) = Pol(1, Φ \ Φ 0 , E)(a) = Res z=0 e a 1 (x 1 +z)+a 2 (x 2 -z) (x 1 +z)(x 1 -x 2 +2z)(x 2 -z) x=0 = -Res z=0 e (a 1 -a 2 )z 2z 3 = -1 4 (a 1 -a 2 ) 2 . Using (i), v(Φ, c 2 )(a) = 1 2 a 2 1 -1 4 (a 1 -a 2 ) 2 = 1 4 (a 1 + a 2 ) 2 -1 2 a 2 2 . (iii) Jump from c 2 to c 3 (W = Re 1 ): We have E = e 2 , Φ 0 = {e 1 }, Φ + = {e 2 , e 1 + e 2 } and Φ -= {e 1 -e 2 }. v(Φ, c 2 )(a) -v(Φ, c 3 )(a) = Pol(1, Φ \ Φ 0 , E)(a) = Res z=0 e a 1 x 1 +a 2 (x 2 +z) (x 2 +z)(x 1 +x 2 +z)(x 1 -x 2 -z) x=0 = -1 2 a 2 2 . Using (ii), v(Φ, c 3 )(a) = 1 2 a 2 1 -1 4 (a 1 -a 2 ) 2 + 1 2 a 2 2 = 1 4 (a 1 + a 2 ) 2 .
5 Wall crossing formula for the partition function: unimodular case

In this section, we compute the jump k(Φ, c 1 )k(Φ, c 2 ) of the partition function k(Φ) across a wall. In order to outline the main ideas in the proof, we will first consider the case where Φ is unimodular (see Remark 10 for the definition). We give two formulae. The first one is the convolution formula of Paradan ([8], Theorem 5.2). The second one is a one dimensional residue formula.

Discrete convolution

Let E ∈ U be a primitive element with respect to Γ * so that E, Γ = Z. Let Ψ be a sequence of vectors in Γ such that ψ, E = 0 for all ψ ∈ Ψ. Thus

Ψ = Ψ + ∪ Ψ -with Ψ + = Ψ ∩ V + and Ψ -= Ψ ∩ V -. Define R + (Ψ) = [ψ ψ ∈ Ψ + ] ∪ [-ψ|ψ ∈ Ψ -]. Let W := {a ∈ V | a, E = 0}, Γ 0 = Γ ∩ W.
We choose F ∈ Γ such that E, F = 1. We thus have Γ = Γ 0 ⊕ ZF . Let Γ ≥0 be the set of elements a ∈ Γ such that a, E ≥ 0. Let us define the function K + (Ψ) on Γ ≥0 such that we have, for x ∈ C(R + (Ψ)) * , ( 8)

ψ∈Ψ 1 1 -e -ψ,x = a∈Γ ≥0 K + (Ψ)(a)e -a,x , that is we have written 1/(1 -e -ψ ) = n≥0 e -nψ , if ψ ∈ Ψ + and 1/(1 -e -ψ ) = -e ψ /(1 -e ψ ) = - n>0 e nψ if ψ ∈ Ψ -.
Let κ -= ψ∈Ψ -ψ so that κ -, E = ψ∈Ψ -ψ, E is a strictly negative number if and only Ψ -is non empty. Then we have

K + (Ψ)(a) = (-1) |Ψ -| k(R + (Ψ))(a -κ -),
where k(R + (Ψ)) is the partition function of the system R + (Ψ).

The function K + (Ψ) is supported on the pointed cone -κ -+ C(R + (Ψ)). In particular the value K + (Ψ)(0) is 1 if Ψ -is empty, or 0 if Ψ -is not empty.

Let q be a polynomial function on Γ 0 . Define for a ∈ Γ C(q, Ψ, E)(a) := w∈Γ 0 q(w)K + (Ψ)(aw).

The sum is over the finite set Γ 0 ∩ (a -C(R + (Ψ))).

Theorem 26 Assume Ψ + is non empty. Assume that, for any ψ ∈ Ψ, we have ψ, E = ±1. Let q be a polynomial function on Γ 0 . Then, for a ∈ Γ ≥0 , C(q, Ψ, E)(a) = Par(q, Ψ, E)(a).

Proof. We need to compute, for a ∈ Γ ≥0 , S(a) :=

w∈Γ 0 q(w)K + (Ψ)(a -w).
This sum is over a finite set.

Let Q ∈ S(U) be a polynomial function on V extending q. We may write

S(a) = Q(∂ x ) • w∈Γ 0 K + (Ψ)(a -w)e w,x x=0 . Define G x (a) = w∈Γ 0 K + (Ψ)(a -w)e -a-w,x .
Then G x (a) depends in an analytic way of the variable x ∈ U, and we have ( 9)

S(a) = Q(∂ x ) • e a,x G x (a) | x=0 .
The function a → G x (a) = w∈Γ 0 K + (Ψ)(aw)e -a-w,x is a function on Γ/Γ 0 = ZF . To identify the function G x (nF ), we compute its discrete Laplace transform in one variable. Let x be in C(R + (Ψ)) * . Write u = e -z . We compute

L dis (G x )(u) = n≥0 G x (nF )u n = n≥0 G x (nF )e -nz
= n,w K + (Ψ)(nFw)e -nF -w,x e -nF,zE = a∈Γ K + (Ψ)(a)e -a,x e -a,zE =

1 ψ∈Ψ (1-e -ψ,x+zE ) = 1
ψ∈Ψ (1-e -ψ,x u ψ,E ) . In the fourth equality, we have written any element a ∈ Γ ≥0 as a = nF -w, with n ≥ 0 and w ∈ Γ 0 . The next equality is by the definition of the function K + (Ψ)(a). Furthermore, we see that the sum is convergent when |u| < 1.

As

L dis (G x )(u) = n≥0 G x (nF )u n , Cauchy formula reads G x (nF ) = 1 2iπ |u|=ǫ u -n L dis (G x )(u) du u = 1 2iπ |u|=ǫ u -n ψ∈Ψ (1-e -ψ,x u ψ,E ) du u .
Thus we obtain for n = a, E ,

S(a) = Q(∂ x ) • e a,x 1 2iπ |u|=ǫ u -n ψ∈Ψ (1 -e -ψ,x u ψ,E ) du u x=0 = 1 2iπ |u|=ǫ u -n Q(∂ x ) • e a,x ψ∈Ψ (1 -e -ψ,x u ψ,E ) x=0 du u .
As at least one of the ψ, E is positive and n ≥ 0, it is easy to see that the function under the integrand has no pole at u = ∞. As ψ, E = ±1, its poles are obtained for u = 0 and u = 1. The integral on |u| = ǫ computes the residue at u = 0. We use the residue theorem so that -S(a) can also be computed as the residue for u = 1. We use the coordinate u = e -z near u = 1, and we obtain

S(a) = Res z=0 Q(∂ x ) • e a,x+zE ψ∈Ψ (1 -e -ψ,x+zE ) x=0
which establishes the formula in the theorem.

Finally, we compute the restriction to W ∩ Γ of Par(q, Ψ, E).

Lemma 27

• If |Ψ -| = ∅
, then the restriction of Par(q, Ψ, E) to W is equal to q.

• If |Ψ -| > 0, then the restriction of Par(q, Ψ, E) to W vanishes.

Proof. The sum formula gives Par(q, Ψ, E)(w) = K + (Ψ)(0)q(w). Recall that K + (Ψ)(0) vanishes as soon as |Ψ -| > 0; it is equal to 1 if Ψ -= ∅.

The jump for the partition function

Let Φ be a sequence of vectors spanning the lattice Γ. In this section we assume that Φ is unimodular and that Γ = ZΦ.

Let k(Φ)(a) be the partition function. Then k(Φ)(a) coincides with a polynomial function on each chamber. We consider, as in Section 4.3, two adjacent chambers c 1 and c 2 separated by a wall W . As before, Φ 0 denotes W ∩ Φ; it is also a unimodular system for the lattice Γ ∩ W . Let k 12 = k(Φ 0 , c 12 ) be the polynomial function on W ∩ Γ associated to the chamber c 12 of Φ 0 . Consider the sequence Ψ = Φ \ Φ 0 . We choose E ∈ U such that Ψ + is non empty.

As the system Φ is assumed to be unimodular, the integers d φ = φ, E are equal to ±1 for any φ ∈ Φ not in W .

Theorem 28 Let k 12 = k(Φ 0 , c 12 ) be the polynomial function on W associated to the chamber c 12 . Then, if E, c 1 > 0, we have Proof. Denote by Leq(Φ) the left hand side and by Req(Φ) the right hand side of Equation ( 10) above.

As the system is unimodular, the lattice Γ is generated by Γ 0 and any φ not in W . So in a parallel way to the proof of the jump for the volume function, it would be sufficient to verify that D(φ)(Leq(Φ) -Req(Φ)) = 0 for some φ ∈ Φ not in W , and that (Leq(Φ) -Req(Φ)) vanishes on W . However, in order that our proof adapts without change to the non unimodular case, we will check D(φ)(Leq(Φ) -Req(Φ)) = 0 for any φ ∈ Φ.

Let us first verify Equation (10) above when there is only one vector φ of Φ not in W . We can suppose that Ψ + = {φ} and Ψ -is empty. In this case the wall W is a facet of the cone C(Φ). The chamber c 1 is equal to c 12 ×R >0 φ, while c 2 is the exterior chamber. It is easy to see that k(Φ, c 1 )(w + tφ) = k 12 (w), whereas k(Φ, c 2 ) = 0. The equation follows from the first item of Lemma 19.

Suppose that this is not the case. Let φ be in Φ, and denote Φ ′ = Φ \ {φ}. We study the difference equations satisfied by Leq(Φ) and Req(Φ).

We have several cases to consider.

• φ is not in W .

Then the sequence Φ ′ = Φ \ {φ} spans V and W is a wall for Φ ′ . The intersection of Φ ′ with W is Φ 0 . Let c ′ 1 and c ′ 2 be the chambers for Φ ′ containing c 1 , c 2 . Then, they are adjacent with respect to W . The chamber c 12 remains the same. By Lemma 13, we have

D(φ)(k(Φ, c 1 ) -k(Φ, c 2 )) = k(Φ ′ , c ′ 1 ) -k(Φ ′ , c ′ 2 ). By Proposition 20, D(φ)Par(k 12 , Φ \ Φ 0 , E) = Par(k 12 , Φ ′ \ Φ 0 , E).
By induction, we obtain D(φ)(Leq(Φ) -Req(Φ)) = 0. We now give some examples of jumps in partition functions for the root system of type A r (which is unimodular).

Let Y be an (r+1) dimensional vector space with basis {e i , i : 1, . . . , r+1}; we denote its dual basis by {e i }. Let V denote the vector space generated by the set of positive roots

Φ(A r ) = {e i -e j : 1 ≤ i < j ≤ r + 1} of A r . Then, V is a hyperplane in Y formed by points v = r+1 i=1 v i e i ∈ Y satisfying r+1 i=1 v i = 0. Using the explicit isomorphism p : R r → V defined by (a 1 , . . . , a r ) → a 1 e 1 + • • • + a r e r -(a 1 + • • • + a r )e r+1
, we write a ∈ V as a = r i=1 a i (e ie r+1 ). Under p * , the vector e ie r+1 determines the linear function

x i in U = V * ∼ R r . The vector a ∈ V lies in C(Φ(A r )) if and only if a 1 + • • • + a i ≥
0 for all i : 1, . . . , r. This will be our notation for subsequent examples concerning A r .

Example 30 We consider the root system of type A 2 with Φ = {e 1e 2 , e 2e 3 , e 1e 3 } (see Figure 2). The cone C(Φ) is comprised of two chambers c 1 = C({e 1e 3 , e 2e 3 }) and c 2 = C({e 1e 3 , e 1e 2 }). We will calculate both k(Φ, c 1 ) and k(Φ, c 2 ) using our formula in Theorem 28 iteratively starting from an exterior chamber.

(i) Jump from the exterior chamber to c 1 : In this case, E = e 1 , Φ 0 = {e 2e 3 }, Φ + = {e 1e 3 , e 1e 2 } and Φ -= ∅.

k(Φ, c 1 )(a) -k(Φ, c ext )(a) = Par(1, Φ \ Φ 0 , e 1 )(a) k(Φ, c 1 )(a) = Res z=0 e a 1 x 1 +a 2 x 2 +za 1 (1-e -x 1 -z )(1-e -x 1 +x 2 -z ) x=0 = Res z=0 e za 1 (1-e -z ) 2 = 1 + a 1 . (ii) Jump from c 1 to c 2 : We have E = e 2 , Φ 0 = {e 1 -e 3 }, Φ -= {e 1 -e 2 } and Φ + = {e 2 -e 3 }. k(Φ, c 1 )(a) -k(Φ, c 2 )(a) = Par(1, Φ \ Φ 0 , e 2 )(a) = Res z=0 e a 1 x 1 +a 2 x 2 +za 2 (1-e -x 2 -z )(1-e -x 1 +x 2 -z ) x=0 = Res z=0 e za 2 (1-e -z )(1-e z ) = -a 2 . Then, k(Φ, c 2 )(a) = 1 + a 1 + a 2 .
Example 31 We now consider the root system of type A 3 (see Figure 3 which depicts the 7 chambers of A 3 via the intersection of the ray R + α of each root α with the plane 3a 1 + 2a 2 + a 3 = 1).

We will calculate the jump in the partition function from c 1 := C({e 1e 2 , e 1 -e 3 , e 1 -e 4 }) to c 2 := C({e 1 -e 2 , e 3 -e 4 , e 1 -e 4 }). In this case, E = e 3 , Φ 0 = {e 1e 4 , e 2e 4 , e 1e 2 }, Φ + = {e 3e 4 } and Φ -= {e 1e 3 , e 2e 3 }. Notice that k 12 is the partition function corresponding to the chamber C({e 1e 4 , e 1e 2 }) of the copy of A 2 in A 3 having the set Φ 0 as its set of positive roots. Using the final calculation in part (ii) of Example 30 (e 4 here plays the role of e 3 in that example), k 12 (a) = a 1 + a 2 + 1. Then, by Theorem 28,

k(Φ, c 2 )(a) -k(Φ, c 1 )(a) = Par(k 12 , Φ \ Φ 0 , E)(a) = Res z=0 (∂ x 1 + ∂ x 2 + 1) • e a 1 x 1 +a 2 x 2 +za 3 (1-e -z )(1-e -x 1 +z )(1-e -x 2 +z) ) x=0 = 1
6 a 3 (a 3 -1)(2a 3 + 3a 2 + 3a 1 + 5).

Khovanskii-Pukhlikov differential operator

We recall that Γ = ZΦ. We normalize the measure dx in order that it gives volume 1 to a fundamental domain for Γ * , and we write v(Φ, dx, c) simply as v(Φ, c).

We recall the relation between the function k(Φ, c) and v(Φ, c). Define Todd(z) as the expansion of

z 1 -e -z = 1 + 1 2 z + 1 12 z 2 + • • • in power series in z. For φ ∈ Φ, Todd(∂(φ)
) is a differential operator of infinite order with constant coefficients. If p is a polynomial function on V , Todd(∂(φ))p is well defined and is a polynomial on V . We denote by Todd(Φ, ∂) the operator defined on polynomial functions on V by

Todd(Φ, ∂) = φ∈Φ Todd(∂(φ)).
The operator Todd(Φ, ∂) transforms a polynomial function into a polynomial function on Γ.

The following result has been proven in Dahmen-Micchelli [START_REF] Dahmen | The number of solutions to linear Diophantine equations and multivariate splines[END_REF].

Theorem 32 Let c be a chamber. Then

k(Φ, c)(a) = Todd(Φ, ∂) • v(Φ, c).
Here we give yet another proof of this theorem, by verifying that our explicit formula for the jumps are related by the Todd operator.

Let W be a wall of Φ determined by E. Assume that Φ + is non empty. Let Todd(Φ 0 , ∂) be the Todd operator related to the sequence Φ 0 = Φ ∩ W which is also unimodular.

Proposition 33 Let p be a polynomial function on W . Then

Todd(Φ, ∂)Pol(p, Φ \ Φ 0 , E) = Par(Todd(Φ 0 , ∂)P, Φ \ Φ 0 , E). Proof. We have Todd(Φ, ∂) = Todd(Φ \ Φ 0 , ∂)Todd(Φ 0 , ∂).

By Proposition 17

Todd(Φ 0 , ∂)Pol(p, Φ \ Φ 0 , E) = Pol(Todd(Φ 0 , ∂)p, Φ \ Φ 0 , E).
Let q = Todd(Φ 0 , ∂)p. Then we apply Todd(Φ \ Φ 0 , ∂) to

Pol(q, Φ \ Φ 0 , E) = Res z=0 Q(∂ x ) • e a,x+zE φ∈Φ\Φ 0 φ, x + zE x=0 .
We obtain

Todd(Φ \ Φ 0 , ∂)Pol(q, Φ \ Φ 0 , E)(a) = Par(q, Φ \ Φ 0 , E).
We now prove Theorem 32 by induction. We assume that Todd(Φ 0 , ∂)v(Φ 0 , c 12 ) = k(Φ 0 , c 12 ). We then obtain from Proposition 33:

Todd(Φ, ∂)(v(Φ, c 1 ) -v(Φ, c 2 )) = Todd(Φ, ∂)Pol(v(Φ 0 , c 12 ), Φ \ Φ 0 , E) = Par(Todd(Φ 0 , ∂)v(Φ 0 , c 12 ), Φ \ Φ 0 , E) = Par(k(Φ 0 , c 12 ), Φ \ Φ 0 , E) = k(Φ, c 1 ) -k(Φ, c 2 ).
Starting from the exterior chamber where k(Φ, c ext ) = Todd(Φ, ∂)•v(Φ, c ext ) = 0, we obtain by jumping over the walls that k(Φ, c) = Todd(Φ, ∂) • v(Φ, c) for any chamber.

6 Wall crossing formula for the partition function: general case

In this section, we compute the jump k(Φ, c 1 )k(Φ, c 2 ) of the partition function k(Φ) across a wall when Φ is an arbitrary system.

A particular quasi-polynomial function

Let W be a hyperplane of V determined by a primitive vector E, and Γ 0 = W ∩ Γ. We denote by T the torus V * /Γ * and T 0 the torus W * /Γ * 0 . The restriction map V * → W * induces a surjective homomorphism r : T → T 0 . The kernel of r is isomorphic to R/Z.

Let Q be a quasi-polynomial function on Γ. We may write Q(a) = y∈T e y (a)Q y (a) where y ∈ V * give rise to an element of finite order in V * /Γ * , still denoted by y. The set of elements g ∈ T such that r(g) = r(y) is isomorphic to R/Z. Definition 34 Let Q(a) = y∈T e y (a)Q y (a) be a quasi-polynomial function on Γ and let Ψ be a sequence of vectors not belonging to W . We define, for a ∈ Γ,

Para(Q, Ψ, E)(a) = y∈T g∈T |r(g)=r(y) Res z=0 Q y (∂ x ) • e a,x+2iπg+zE ψ∈Ψ (1 -e -ψ,x+2iπg+zE ) x=0 .
Remark 35 The definition may look strange, as we sum a priori on the infinite set r(g) = r(y). However, in order that the function

Q y (∂ x ) e a,x+2iπg+zE ψ∈Ψ (1 -e -ψ,x+2iπg+zE ) x=0
has a pole at z = 0, we see that there must exist a ψ in Ψ such that e 2iπ ψ,g = 1. As r(g) is fixed, this leaves a finite number of possibilities for g. More concretely, if y is given, any g such that r(g) = r(y) is of the form g = y+GE, and G must satisfy e 2iπG ψ,E = e -2iπ y,ψ for some ψ ∈ Ψ. Furthermore, we see that if the integers ψ, E are equal to ±1 for all ψ ∈ Ψ, and if Q is polynomial (so that y = 0 on the above equation), then Para(Q, Ψ, E) is equal to Par(Q, Ψ, E).

It is easy to see that Para(Q, Ψ, E)(a) is a quasi-polynomial function of a ∈ V . Furthermore, using the same argument as in the proof of Lemma 15, we obtain the following.

Lemma 36 The quasi-polynomial function Para(Q, Ψ, E) depends only on the restriction q of Q to Γ 0 .

Choose a primitive vector F such that Γ = Γ 0 ⊕ZF . Then we see that any quasi-polynomial function q on Γ 0 extends to a quasi-polynomial function Q on Γ.

Theorem 40 Let q be a quasi-polynomial function on Γ 0 . Assume that Ψ + is non empty. Then, for a ∈ Γ ≥0 , C(q, Ψ, E)(a) = Para(q, Ψ, E)(a).

Proof. We need to compute, for a ∈ Γ ≥0 , S(a) :=

w∈Γ 0 q(w)K + (Ψ)(a -w).
This sum is over a finite set.

Let Q(a) = y∈T e y (a)Q y (a) be any quasi-polynomial function on Γ extending q. We may write The function a → G x,y (a) = w∈Γ 0 K + (Ψ)(aw)e -a-w,x+2iπy is a function on Γ/Γ 0 = ZF . To identify the function G x,y (nF ), with n = a, E , we compute its discrete Laplace transform in one variable. With the same proof as the proof in Theorem 26, we obtain that for x in the dual cone to C(R + (Ψ)), L dis (G x,y )(u) = n≥0 G x,y (nF )u n is convergent for |u| < 1 and we obtain

S(a) = y∈T Q y (∂ x ) • w∈Γ 0 K + (Ψ)(a -w)e w,x+2iπy
G x,y (a) = 1 2iπ |u|=ǫ u -n ψ∈Ψ (1 -e -ψ,x+2iπy u ψ,E ) du u
where n = a, E .

Thus Formula (12) becomes

S(a) = y∈T Q y (∂ x ) • e a,x+2iπy 1 2iπ |u|=ǫ u -n ψ∈Ψ (1 -e -ψ,x+2iπy u ψ,E ) du u x=0 .
Theorem 42 Let k 12 = k(Φ 0 , c 12 ) be the quasi-polynomial function on Γ 0 associated to the chamber c 12 . Then, if E, c 1 > 0, we have

(13) k(Φ, c 1 ) -k(Φ, c 2 ) = Para(k 12 , Φ \ Φ 0 , E).
Proof.

The proof is exactly the same as in the proof of Theorem 28 corresponding to the unimodular case.

Example 43 We consider the root system of type B 2 (see Figure 1). We will calculate k(Φ, c) for all chambers c using our formula in Theorem 42 iteratively starting from an exterior chamber.

(i) Jump from the exterior chamber to c 1 : We have E = e 1 , Φ 0 = {e 2 }, Φ + = {e 1 + e 2 , e 1 , e 1e 2 } and Φ -= ∅. With the notation of Definition 14, Q = 1(hence y = 0) and φ, E = ±1 for all φ ∈ Φ\Φ 0 . Then, by Remark 35, (1-e -z )(1-e -2z )(1-e z ) + Res z=0

Para(1, Φ \ Φ 0 , E) = Par(1, Φ \ Φ 0 , E). We get k(Φ, c 1 )(a) -k(Φ, c ext )(a) = Res z=0 e a,x+ze 1 (1-e -(x 1 +x 2 +z) )(1-e -(x 1 +z) )(1-e -(x 1 -x 2 +z) ) x=0 k(Φ, c 1 )(a) = Res z=0 e a 1 z (1-e -z ) 3 = 1 2 (a 1 + 2)(a 1 + 1). (ii
(-1) a 1 +a 2 e (a 1 -a 2 )z (1+e -z )(1-e -2z )(1+e z ) = (-1) a 1 +a 2 1 8 -1 8 (2a 2 2 -4a 1 a 2 + 2a 2 1 + 1 -4a 2 + 4a 1 ) = -1 4 (a 2 -a 1 )(a 2 -a 1 -2) if a 1 + a 2 even, -1 4 (a 2 -a 1 -1) 2 if a 1 + a 2 odd = -1 4 (a 2 -a 1 -1 + ( 1+(-1) a 1 +a 2 2 ))(a 2 -a 1 -1 -( 1+(-1) a 1 +a 2 2
)).

Using (i), we get (1-e -z )(1-e -z )(1-e z ) = -1 2 a 2 (a 2 + 1). 1) a 1 +a 2 1 8 .

k(Φ, c 2 )(a) = 1 2 (a 1 + 2)(a 1 + 1) + (-1) a 1 +a 2 1 8 -1 8 (2a 2 2 -4a 1 a 2 + 2a 2 1 + 1 -4a 2 + 4a 1 ) = 1 4 a 2 1 + 1 2 a 1 a 2 -1 4 a 2 2 + a 1 + 1 2 a 2 + 7 8 + (-1) a 1 +a
Then, k(Φ, c 3 )(a) = 1 4 a 2 1 + 1 2 a 1 a 2 + 1 4 a 2 2 + a 1 + a 2 + 7 8 + (-

Generalized Khovanskii-Pukhlikov differential operator

Here Φ is a general sequence (not necessarily unimodular). We assume again that ZΦ = Γ. We choose the measure dx giving volume 1 to U/Γ * . We write v(Φ, c, dx) = v(Φ, c).

For the complex number ζ, define Todd(ζ, z) as the expansion of

z 1 -ζ -1 e -z
(Φ) = {g ∈ T | < Φ(g) >= V }.
The set G(Φ) is finite. Indeed, if g ∈ G(Φ), there must exists a basis σ of V extracted from Φ such that e φ (g) = 1 for all φ ∈ σ, and this gives a finite set of solutions. If Φ is unimodular, then G(Φ) is reduced to the identity element.

The following result has been proven in [START_REF] Brion | Residue formulae, vector partition functions and lattice points in rational polytopes[END_REF].

Theorem 45 Let c be a chamber. Then

k(Φ, c)(a) = Todd(G(Φ), Φ, ∂) • v(Φ, c).
Here we will give yet another proof of this theorem, by verifying that the explicit formula for the jumps are related by the Todd operator.

For the proof, it is easier to sum over 'all elements' t of T . If v is a polynomial function on V such that being understood that we only sum over the finite subset of t ∈ T such that Todd(t, Φ, ∂)

• v = 0. With this definition, for v = v(Φ, c), then Todd(T, Φ, ∂)v = Todd(G(Φ), Φ, ∂)v.
To prove Theorem 45, we follow the same scheme of proof as in Theorem 32.

Let W be a wall and let c 0 be a chamber of the wall for the sequence Φ 0 = Φ ∩ W . We only need to prove Theorem 46

(16) Todd(T, Φ, ∂)Pol(v(Φ 0 , c 0 ), Φ \ Φ 0 , E) = Para(k(Φ 0 , c 0 ), Φ \ Φ 0 , E).
Proof. It is easy to see that the function v := Pol(v(Φ 0 , c 0 ), Φ \ Φ 0 , E) satisfies the hypothesis (15) above. Let V 0 be a polynomial function on V extending v 0 = v(Φ 0 , c 0 ). Then (Todd(T, Φ, ∂)v)(a) is equal to

t 0 ∈T 0 t∈T | r(t)=t 0 e t (a)(Todd(t 0 , Φ 0 , ∂)Todd(t, Φ \ Φ 0 , ∂) • v)(a),
where T 0 denotes the torus W * /Γ * 0 . We have

e t (a)(Todd(t, Φ\Φ 0 , ∂)v)(a) = Res z=0 V 0 (∂ x ) • e a,x+2iπt+zE φ∈Φ\Φ 0 (1 -e -φ,x+2iπt+zE ) x=0 , so that (Todd(T, Φ, ∂)v)(a) is equal to = t 0 ∈T 0 t∈T |r(t)=t 0 Res z=0 (Todd(t 0 , Φ 0 , ∂)V 0 )(∂ x ) e a,x+2iπt+zE φ∈Φ\Φ 0 (1 -e -φ,x+2iπt+zE ) x=0 .
By induction hypothesis, a quasi-polynomial function extending k 0 (Φ 0 , c 0 ) is

t 0 ∈T 0 e t 0 (a)(Todd(t 0 , Φ 0 , ∂)V 0 )(a)
where we denote again by t 0 any element of T such that r(t) = t 0 . Thus the last formula is exactly the definition of Para(k 0 (Φ 0 , c 0 ), Φ \ Φ 0 , E)(a).

The rest of the proof is identical to the proof of Theorem 32.

Some examples

In this section we give further examples of jumps in partition and volume for various root systems.

Example 47 We will calculate the jump in volume from c 1 := C({e 1 , e 1e 2 , e 1 -e 3 } to c 2 := C({e 1 , e 1 -e 2 , e 1 +e 3 }) of B 3 (see Figure 4 where chambers (see Figure 4). We consider the copy B 2 in B 3 having the set {e 1 , e 3 , e 1 + e 3 , e 1e 3 } as its set of positive roots. This particular jump is over chamber C({e 1 , e 1 +e 3 }) of this B 2 . We have E = e 2 , Φ + = {e 2 , e 2 +e 3 , e 2 -e 3 , e 1 +e 2 } and Φ 8 . Then, with the notation of Section 6, we have y = 0 or y = e 1 +e 2 2 ; correspondingly Q 0 (a) = 1 4 (a 1 + a 2 ) 2 + a 1 + a 2 + 7 8 and Q e 1 +e 2 2 (a) = 1 8 . For y = 0, the only feasible g ∈ T giving a nontrivial residue at z = 0 for a summand in Para(k 12 , Φ \ Φ 0 , E) and satisfying r(g) = 0 is g = 0. On the other hand, for y = e (1-e -z )(1+e -z ) 2 (1+e z ) 2 + 1 8 Res z=0 (-1) a 1 +a 2 +a 3 e a 3 z (1+e -z )(1-e -z ) 2 (1-e z ) 2 = 1 2880 a 3 (a 3 -1)(a 3 + 2)(a 3 + 1)(4a 2 3 + 4a 3 + 30a 2 1 + 60a 2 a 1 + 30a 2 2 + 441 + 240a 1 + 240a 2 ) +(-1) a 1 +a 2 1 128 + (-1) a 1 +a 2 +a 3 1 384 (2a 3 + 1)(2a 2 3 + 2a 3 -3).

v(Φ, c 2 )(a) -v(Φ, c 1 )(a) = Pol(v 12 , Φ \ Φ 0 , E)(a) = Res z=0 v 12 (∂ x ) • e a 1 x 1 +a 2 x 2 +a 3 (z+x 3 ) (x 3 +z)(x 1 +x 3 +z)(x 2 +x 3 +z)(x 1 -x 3 -z)(x 2 -x 3 -z) x=0 = 1 1440 a 4 3 (30a 1 a 2 + 15a 2 1 + 15a 2 2 + 2a 2
-= {e 1 -e 2 }. Using part (ii) of Example 25, v 23 (a) = 1 4 (a 1 +a 3 ) 2 -1 2 a 2 3 . By Theorem 23, v(Φ, c 3 )(a) -v(Φ, c 2 )(a) = Pol(v 23 , Φ \ Φ 0 , E)(a) = Res z=0 v 23 (∂ x ) •
Let γ 3 := 1-(-1) a 3 2 and γ 12 := 1-(-1) a 1 +a 2

2

. Then, after some calculation, we can factor k(Φ, c 2 )(a)k(Φ, c 1 )(a) as: ) is in c nice if and only if a i > 0 for all 1 ≤ i ≤ r. Then, the copy of A r-1 (with positive roots {e ie j : 2 ≤ i < j ≤ r + 1}) in A r can be thought as the hyperplane W with c 1 = c ext , c 2 = c nice (A r ) and c 12 = c nice (A r-1 ). Together with the fact that k(A r-1 , c nice )(a) is independent of a r-1 , we have by Theorem 28, = 1 360 (a 1 + 3)(a 1 + 2)(a 1 + 1)(a 1 + 3 + a 2 + 3a 3 ) .(a 2 1 + 9a 1 + 5a 1 a 2 + 10a 2 2 + 20 + 30a 2 ).

In a similar fashion, using Theorem 23, we can calculate v(A n , c nice ) iteratively. The computation of v(A 7 , c nice ) took 12 seconds. The result is too big to be written here.

Recall that Baldoni-Beck-Cochet-Vergne [START_REF] Baldoni | Volume computation for polytopes and partition functions for classical root systems[END_REF] can compute individual numbers k(A n )(a) for a fixed, for n = 10 in less than 30 minutes. The full polynomial k(A n , c nice ) is computed in 7 minutes when n = 7 and 30 minutes when n = 8 on a 1, 13GHz computer. The method of Baldoni-Beck-Cochet-Vergne uses an arbitrary order on roots. The method of calculation which follows from wall crossing formulae seems less efficient, but it may give some light on the best order strategy and the complexity of calculations.

  real vector space; x ∈ U; dx Lebesgue measure on U. V dual of U; a ∈ V ; da dual Lebesgue measure on V . Γ a lattice in V ; γ ∈ Γ. Γ * dual lattice in U; Γ, Γ * ⊂ Z. T (Γ), T torus U/Γ * . Φ a sequence of nonzero vectors in Γ all on one side of a hyperplane ;φ ∈ Φ. C(Φ) cone generated by Φ. < Φ > vector space generated by Φ. ZΦ lattice generated by Φ in < Φ >. P (Φ, a) convex polytope associated to Φ and a. vol(Φ, dx)(a) volume of P (Φ, a) for the quotient measure dt/da. k(Φ)(a) number of integral points in P (Φ, a). c a chamber of C(Φ). v(Φ, dx, c) polynomial function coinciding with vol(Φ, dx) on the cone c. k(Φ, c) quasi-polynomial function coinciding with k(Φ) on c ∩ Γ. K quasi-polynomial function of a. τ (γ) translation operator (τ (γ)K)(a) = K(aγ). D(φ) difference operator (D(φ)K)(a) = K(a) -K(aγ). W hyperplane in V defined for a fixed E ∈ U by {a ∈ V | a, E = 0}. Ψ a sequence of vectors in Γ not in W ; ψ ∈ Ψ. ∆ + a sequence of vectors all on one side of W ; α ∈ ∆ + .

Lemma 8

 8 along the fibers of the map A : R N ≥0 → C(Φ), or to the analogous discrete sum. For x in the interior of C(Φ) * , C(Φ)

Figure 1 :

 1 Figure 1: Chambers of B 2

c 1 )

 1 k(Φ, c 2 ) = Par(k 12 , Φ \ Φ 0 , E). Remark 29 By Theorem 26, the function Par(k 12 , Φ\ Φ 0 , E) coincide, up to sign, on Γ ≥0 with the discrete convolution w∈W ∩Γ k 12 (w)k(R + (Ψ))(a-κ -w) of the polynomial function k 12 (w) on W by the partition function (shifted) k(R + (Ψ)). Thus, our residue formula for k(Φ, c 1 )k(Φ, c 2 ) coincide with Paradan's formula ([8], Theorem 5.2) for the jump of the partition function.

Figure 2 :

 2 Figure 2: Chambers of A 2

Figure 3 :

 3 Figure 3: Chambers of A 3

K

  + (Ψ)(aw)e -a-w,x+2iπy .Then G x,y (a) depends in an analytic way of the variable x ∈ U, and we have (12) S(a) = y∈T Q y (∂ x ) • e a,x+2iπy G x,y (a) x=0 .

) Jump from c 1 to c 2 :

 2 We have E = e 1e 2 , Φ 0 = {e 1 + e 2 }, Φ + = {e 1 , e 1e 2 } and Φ -= {e 2 }. We also have Q = k 12 = 1, thus y = 0. Then, the set of feasible g ∈ T giving a nontrivial residue at z = 0 for a summand in Para(1, Φ \ Φ 0 , E) and satisfying r(g) = 0 is {0, e 1 -e 2 2 }. By Theorem 42, k(Φ, c 2 )(a)k(Φ, c 1 )(a) = Para(1, Φ \ Φ 0 , E)(a) = g=0,g= e 1 -e -φ,x+2iπg+zE ) x=0 = Res z=0 e (a 1 -a 2 )z

2 1 8 .

 8 (iii) Jump from c 2 to c 3 : We have E = e 2 , Φ 0 = {e 1 }, Φ + = {e 2 , e 1 + e 2 } and Φ -= {e 1e 2 }. We again have Q = k 23 = 1 and φ, E = ±1 for all φ ∈ Φ \ Φ 0 . Thus, y = g = 0 and (as in part (i)) we can use the formula for the unimodular case:k(Φ, c 2 )(a)k(Φ, c 3 )(a) =Res z=0 e a,x+zE φ∈Φ\Φ 0 (1-e -φ,x+zE ) x=0 = Res z=0 e a 2 z

  into a power series in z. If ζ = 1, -1 e -z is analytic at z = 0. For φ ∈ Φ, Todd(ζ, ∂(φ)) is a differential operator of infinite order with constant coefficients. If p is a polynomial function on V , Todd(ζ, ∂(φ))p is well defined and is a polynomial on V . For g ∈ T = U/Γ * , define the Todd operator (a series of differential operators with constant coefficients) by Todd(g, Φ, ∂) := N k=1 Todd(e g (φ k ), ∂(φ k )), where e g (φ k ) := e 2iπ g,φ k . If G is a finite subset of T , we denote by Todd(G, Φ, ∂) the operator defined on polynomial functions v(a) on V by (Todd(G, Φ, ∂)v)(a) = g∈G e g (a)(Todd(g, Φ, ∂)v)(a). Let g ∈ T , and define Φ(g) = {φ ∈ Φ | e g (φ) = 1}. If Φ(g) do not generate V , it follows from Corollary 12 that ( φ / ∈Φ(g) ∂(φ))v(Φ, c) = 0. Thus Todd(g, Φ, ∂)v(Φ, c) = 0. Indeed Todd(g, Φ, ∂) is divisible by ( φ / ∈Φ(g) ∂(φ)) as follows from Equation (14) above. Definition 44 Define G

  , Φ, ∂) • v = 0 except for a finite number of elements t, we may define Todd(T, Φ, ∂)v(a) = t∈T e t (a)Todd(t, Φ, ∂) • v,

Figure 4 :

 4 Figure 4: Chambers of B 3

3 ). Example 48

 348 We will calculate the jump in volume from c 2 = C({e 1 , e 1e 2 , e 1 + e 3 }) to c 3 := C({e 1 , e 1 + e 3 , e 2e 3 }) ∩ C({e 1 , e 1 + e 3 , e 2 + e 3 }) of B 3

e a 1 -1 96 a 4 2 (a 2 1 + 2a 1 a 3 -a 2 3 ) 2 in B 3

 141323 x 1 +a 2 z+a 3 x 3 z(x 3 +z)(-x 3 +z)(x 1 +z)(x 1 -z) x=0=Example 49 We will calculate the jump in the partition function from c 1 = C({e 1 , e 1e 2 , e 1e 3 } to c 2 = C({e 1 , e 1e 2 , e 1 + e 3 }) of B 3 (see Figure4). This particular jump is over the chamber C({e 1 , e 1e 2 }) of the copy of B having positive roots Φ 0 = {e 1 , e 2 , e 1 + e 2 , e 1e 2 }. We have E = e 3 , Φ + = {e 3 , e 1 + e 3 , e 2 + e 3 }, Φ -= {e 1e 3 , e 2e 3 }.Using part (iii) of Example 43, k 12 (a) = 1 4 (a 1 + a 2 ) 2 + a 1 + a 2 + 7 8 + (-1) a 1 +a 2 1

1 +e 2 2 2 is { e 1 +e 2 2 , e 1 +e 2 +e 3 2 }. 2 ( 2 ( 8

 2222228 the feasible set of g giving a nontrivial residue at z = 0 for a summand in Para(k 12 , Φ \ Φ 0 , E) and satisfying r(g) = e 1 +e 2 Then, by Theorem 42,k(Φ, c 2 )(a)k(Φ, c 1 )(a) = Para(k 12 , Φ \ Φ 0 , E)(a) = Res z=0 Q 0 (∂ x ) • e a,x+ze 3 φ∈Φ + ∪Φ -(1-e -φ,x+ze 3 ) x=0 +Res z=0 Q e 1 +e 2 ∂ x ) • e a,x+iπ(e 1 +e 2 )+ze 3 φ∈Φ + ∪Φ -(1-e -φ,x+iπ(e 1 +e 2 )+ze 3 ) x=0 +Res z=0 Q e 1 +e 2 ∂ x ) •e a,x+iπ(e 1 +e 2 +e 3 )+ze 3φ∈Φ + ∪Φ -(1-e -φ,x+iπ(e 1 +e 2 +e 3 )+ze 3 ) x=0 = Res z=0 Q 0 (∂ x ) • e a 1 x 1 +a 2 x 2 +a 3 z (1-e -z )(1-e -(x 1 +z) )(1-e -(x 2 +z) )(1-e -(x 1 -z) )(1-e -(x 2 -z) ) x=0+ 1 Res z=0 (-1) a 1 +a 2 e a 3 z

3

 3 -γ 3 )(a 3 +2-γ 3 )•((1γ 3 )(f 1 -30(1γ 12 )(1 -2a 3 )) + γ 3 (f 2 -30(1γ 12 )(3 + 2a 3 ))) ,wheref 1 = 4a

1 6

 1 k(A r , c nice )(a) = Par(k(A r-1 , c nice ), {e 1e 2 , . . . , e 1e r+1 }, e 1 )(a)= Res z=0 k(A r-1 , c nice )(∂ x 2 , . . . , ∂ x r-1 ) • e a 1 z+a 2 x 2 +•••+a r-1 x r-1 (1-e x 2 -z )•••(1-e x r-1 -z )(1-e -z ) 2 x=0 . For example, using k(A 2 , c nice )(a) = a 1 + 1 (part (i) of Example 30), k(A 3 , c nice )(a) = Res z=0 (∂ x 2 + 1) • e a 1 z+a 2 x 2 (1-e -z ) 2 (1-e x 2 -z ) x=0 = 1 6 (a 1 + 2)(a 1 + 1)(a 1 + 3a 2 + 3).We can iteratively calculate,k(A 4 , c nice )(a) = Res z=0 (∂ x 2 + 2)(∂ x 2 + 1)(∂ x 2 + 3∂ x 3 + 3) •e a 1 z+a 2 x 2 +a 3 x 3 (1-e -z ) 2 (1-e x 2 -z )(1-e x 3 -z ) x=0

  + 60a 2 1 a 3 + 480a 3 a 2 + 120a 2 a 1 a 3 + 912a 3 + 480a 1 a 3 + 45Example 50 Let c nice denote the interior of the cone generated by the roots {e ie r+1 , 1 ≤ i ≤ r} of A r . With the notation of Section 5.2 , a = r i=1 a i (e ie r+1

	4 3 + 4a 3 3 + 30a 2 1 a 2 3 + 60a 2 a 1 a 2 3 + 240a 2 a 2 3 + 30a 2 2 a 2 3 + 437a 2 3 + 240a 2 3 a 1 -34a 3 -426 -60a 2 a 1 -30a 2 1 -240a 2 -30a 2 2 -240a 1 f 2 = 4a 4 3 + 12a 3 3 + 30a 2 1 a 2 3 + 60a 2 a 1 a 2 3 + 240a 2 a 2 3 + 30a 2 2 a 2 3 + 449a 2 3 + 240a 2 3 a 1 +60a 2 2 a 3

• φ is in W and Φ ′ 0 = Φ 0 \ {φ} span W . Then the sequence Φ ′ = Φ\{φ} spans V , and W is a wall for the system Φ ′ . Let c ′ 1 and c ′ 2 be the chambers for Φ ′ containing c 1 , c 2 . Then, they are adjacent with respect to W . By Lemma 13, we have

Let c ′ 12 be the chamber for the sequence Φ ′ 0 containing c 12 . The sequence Φ \ Φ 0 is equal to Φ ′ \ Φ ′ 0 . By Proposition 20, we obtain

So by induction, we conclude that D(φ)(Leq(Φ) -Req(Φ)) = 0 again.

• φ is in W and Φ ′ 0 does not span W . Then W is not a wall for the sequence Φ ′ .

It follows from the description given in Proposition 9 of the regular behavior of functions on chambers that k(Φ ′ , c ′ 1 )k(Φ ′ , c ′ 2 ) = 0. Thus, by Lemma 13,

Similarly, the function k(Φ 0 , c 12 ) satisfies D(φ)k(Φ 0 , c 12 ) = 0. As

We conclude that D(φ)(Leq(Φ) -Req(Φ)) = 0 for any φ ∈ Φ so that Leq(Φ) -Req(Φ) is constant on Γ = ZΦ. It is thus sufficient to verify that Leq(Φ) -Req(Φ) vanishes on W . If Φ + and Φ -are both non empty, both chambers c 1 and c 2 are interior chambers. So, Leq(Φ) vanishes on W . By Lemma 27, Req(Φ) also vanishes on W . If Φ -is empty, the wall W is a facet of C(Φ). The restriction of the function k(Φ, c) to a facet is the function k(Φ 0 , c 12 ). Thus Leq(Φ) restricts to k 12 on W by Lemma 7. This is the same for Req(Φ) by Lemma 27. Thus we established the theorem.

Definition 37 Let q be a quasi-polynomial function on Γ 0 . We define

where Q is any quasi-polynomial function on Γ extending q.

Remark 38 Let q be a quasi-polynomial function on Γ 0 ; we may write q(w) = y∈T 0 e y (w)q y (w). Let Q y denote any extension of the polynomial function q y on V . Then, while calculating Para(q, Ψ, E), we are in fact summing over g ∈ T such that r(g) = y.

Proof. The first formula is immediate from the definition. For the second formula, if r(g) = r(y) and if w ∈ Γ 0 , then e a-w,x+2iπg+zE = e -w,x e y (-w)e a,x+2iπg+zE , and the result follows as in the proof of Proposition 20.

Discrete convolution

We take the same notations as in Section 5.1. However here the system Ψ is arbitrary. We define, as before, the function K + (Ψ) on Γ ≥0 by the equation ( 11)

Let q be a quasi-polynomial function on Γ 0 . Define for a ∈ Γ ≥0 C(q, Ψ, E)(a) :=

As at least one of the ψ, E is strictly positive and n ≥ 0, the function F y (u) has no pole at ∞. The integral over |u| = ǫ computes the residue of F y (u) at u = 0. All other poles are such that u ψ,E = e ψ,2iπy for some ψ ∈ Ψ, so they are roots of unity ζ = e 2iπG with G ∈ R/Z. Any element g ∈ T with r(g) = r(y) is of the form g = y + GE with some G. We obtain

Res u=e 2iπG F y (u).

We write u = e 2iπG e -z in the neighborhood of e 2iπG and we obtain the formula of the theorem.

Similarly, we compute the restriction of Para(q, Ψ, E) to W ∩ Γ.

Lemma 41

• If |Ψ -| = ∅, then the restriction of Para(q, Ψ, E) to W is equal to q.

• If |Ψ -| > 0, then the restriction of Para(q, Ψ, E) to W vanishes.

Proof.

The sum formula gives Para(q, Ψ, E)(w) = K + (Ψ)(0)q(w) and K + (Ψ)(0) vanishes as soon as |Ψ -| > 0.

The jump for the partition function

Let Φ be a sequence of vectors spanning the lattice Γ. Let k(Φ)(a) be the partition function given by quasi-polynomial functions on chambers. We consider as in Section 5.2 two adjacent chambers c 1 and c 2 separated by a wall W . As before, Φ 0 denotes W ∩ Φ. Let k 12 = k(Φ 0 , c 12 ) be the quasipolynomial function on W ∩ Γ associated to the chamber c 12 of Φ 0 . Consider the sequence Ψ = Φ \ Φ 0 . We choose E ∈ U such that Ψ + is non empty. In the preceding section, we have associated a quasi-polynomial function Para(k 12 , Φ \ Φ 0 , E) on Γ to Φ \ Φ 0 , E and k 12 . We recall that Para(k 12 , Φ \ Φ 0 , E)(a) = w∈W ∩Γ k 12 (w)K + (Φ \ Φ 0 )(aw).


Sophie Leroux

Katia Feve

Florence Vignoles

Olivier Bouchez

Christophe C Klopp

Celine Noirot

David Gourichon

Sabine Richard

Christine Leterrier

Catherine Beaumont

Céline Noirot

Francis Minvielle

Alain Vignal

Frédérique Pitel
email: frederique.pitel@toulouse.inra.fr

Non PCR-amplified transcripts and AFLP® fragments as reduced representations of the quail genome for 454 Titanium sequencing

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

Findings

Next-generation sequencing can now generate from hundreds to thousands of megabases worth of data at a time [START_REF] Metzker | Sequencing technologies -the next generation[END_REF]. Although this is a great progress when compared to conventional Sanger sequencing, it remains costly to obtain SNP by whole-genome sequencing of many individuals, especially in species for which no assembly is available. Therefore, sequencing reduced representations libraries is still an efficient and sparing approach. We describe here two protocols used for high-throughput sequencing in quail with several improvements to existing methods [START_REF] Van Orsouw | Complexity reduction of polymorphic sequences (CRoPS): a novel approach for large-scale polymorphism discovery in complex genomes[END_REF][START_REF] Ng | Multiplex sequencing of paired-end ditags (MS-PET): a strategy for the ultra-high-throughput analysis of transcriptomes and genomes[END_REF]. These can be applied to 454 library preparations for several purposes, such as cDNA sequencing without sample amplification, genomic DNA sequencing of scarce samples, or genomic sample multiplexing.

Transcripts library preparation

Total RNA was extracted from about 500 mg of adult quail brains (3 quail lines [START_REF] Mills | Divergent selection for duration of tonic immobility and social reinstatement behavior in Japanese quail (Coturnix coturnix japonica) chicks[END_REF][START_REF] Minvielle | Changes in heterosis under within-line selection or reciprocal recurrent selection: an experiment on early egg production in Japanese quail[END_REF], 4 samples each) and total embryos (E8 stage, 3 quail lines, 2 samples each) according to the technique described by Le Meur et al [START_REF] Lemeur | The ovalbumin gene family: hormonal control of × and Y gene transcription and mRNA accumulation[END_REF], slightly modified. Briefly, tissues were homogenized with a tissue homogenizer (TH, OMNI International) with extraction solution (LiCl 3 M, urea 6 M, sodium acetate 10 mM, pH 5.6), and conserved overnight at 4°C. After centrifugation, pellets were washed twice with washing solution (LiCl 4 M, urea 8 M) and dissolved in 500 μl of TES (Tris 50 mM, EDTA 20 mM, SDS 0.5%, pH 7.5) with Proteinase K (100 μg/ml). After incubation (30 min, 37°C), total RNA was phenol extracted with Phase Lock Gel (Phase Lock Gel Heavy, 2 ml, 5 Prime) according to the manufacturer's instructions except for the use of LiCl 5 M instead of sodium acetate 2 M. Total RNA yield was estimated on a NanoDrop 1000 spectrophotometer (NanoDrop).

Next, a DNase treatment was performed to remove any potential remaining DNA. For 45 μg of total RNA per sample, 20 U of RNasine (Promega), 10 U of DNAse (Roche), 1× of PCR buffer (Invitrogen), and 1.5 mM of MgCl2 (Invitrogen) were added after which the samples were incubated 30 min at 37°C, before a purification step (RNeasy minElute Cleanup, Qiagen). A control PCR was systematically performed to check for the absence of genomic DNA. The quality of RNA samples was assessed using the Agilent 2100 Bioanalyzer (Agilent Technologies). Equivalent quantities of each sample were pooled to obtain 75 μg of treated total RNA, for each quail line.

Poly(A) + RNAs were then purified twice using the Dynabeads Oligo(dT) 25 kit (Invitrogen). First strand cDNA was synthesized from the purified mRNA, using the Superscript II Reverse Transcriptase (Invitrogen), according to the manufacturer instructions, with a modified primer, GAGAGAGAGACTGGAG(T) 16 VN, containing the GsuI restriction enzyme site (CTGGAGNNNNNNNNNNN NNNNN^, overhang NN-3′), to trim the polyA tail after cDNA synthesis. The other protocol modification was to use methylated dCTP (dm 5 CTP, Fermentas). The hemimethylation is necessary to avoid internal cleavage by subsequent GsuI digestion [START_REF] Shibata | Removal of polyA tails from full-length cDNA libraries for high-efficiency sequencing[END_REF].

The second strand cDNA was synthesized according to the Second Strand Synthesis Invitrogen protocol by adding 1× of Second-Strand Reaction Buffer (Invitrogen), 0.2 mM of classical dNTP mix, 10 U of E. coli DNA Ligase (New England Biolabs), 40 U of E. coli DNA Polymerase (New England Biolabs), 2.5 U of E. coli RNase H (New England Biolabs). The samples were incubated 2 hours at 16°C. Ten units of T4 DNA polymerase (New England Biolabs) were added for 5 minutes and the reaction was stopped by adding EDTA to a final concentration of 30 mM. Samples were then incubated 15 min at 37°C with 5 U of Ribonuclease I (Fermentas). Next, cDNA were extracted by using phenol/chloroform and Phase Lock Gel (Phase Lock Gel Light, 2 ml, 5 Prime), followed by ethanol precipitation. The pellets were resuspended in 6 μl of water.

The double-strand cDNA was digested with 5 U of GsuI for 60 minutes at 30°C, and the reaction was stopped by heating at 65°C for 20 minutes. The samples were then submitted to 454 sequencing, each library being prepared from the pooled cDNA obtained from two syntheses (namely issued from 2 × 75 μg of total RNA).

AFLP® fragments library preparation

Genomic DNA was extracted from blood samples of 6 animals (3 quail lines, 2 individuals each) with a rapid high-salt protocol [START_REF] Roussot | AFLP® linkage map of the Japanese quail Coturnix japonica[END_REF]. AFLP® fragments were generated as in [START_REF] Roussot | AFLP® linkage map of the Japanese quail Coturnix japonica[END_REF], except that we only performed the preamplification step. Briefly, 400 ng of genomic DNA were digested with 10 U of EcoRI and TaqI restriction enzymes (New England Biolabs). Adaptors [START_REF] Roussot | AFLP® linkage map of the Japanese quail Coturnix japonica[END_REF] were ligated to the DNA fragments obtained, and the ligation reaction was diluted 5-fold in water. PCR amplifications were carried out for each sample in 25 μl reactions containing 5 μl of diluted ligation, 0.2 units of Phusion high-fidelity DNA polymerase (New England Biolabs), 1× High-Fidelity buffer (New England Biolabs), 0.2 mM dNTP, and 0.2 μM of each primer on a GeneAmp PCR System 9700 thermocycler (Applied Biosystems).

PCR primers were modified from preamplification primers [START_REF] Roussot | AFLP® linkage map of the Japanese quail Coturnix japonica[END_REF] (Table 1): to identify the animal-of-origin for each sequence, a 4-base tag was added to the 5′-end of each primer, each sample being amplified with a Taqand an Eco-primers bearing the same tag. Primers were further modified by adding a 5′-phosphate to allow the ligation of the 454 sequencing primers. Unlike in the CRoPS™approach [START_REF] Van Orsouw | Complexity reduction of polymorphic sequences (CRoPS): a novel approach for large-scale polymorphism discovery in complex genomes[END_REF], we did not modify A and B sequencing primers and used the oligonucleotides delivered in the Roche kits.

Thirty-five PCR cycles were performed, each consisting of denaturation at 94°C for 30 s, annealing at 59°C for 30 s and elongation at 72°C for 60 s. The ramp rate was settled to 80%. Polishing of PCR products was realized by the addition of 0.6 U T4 DNA Polymerase (New England Biolabs), 1× BSA, 1× T4 buffer (New England Biolabs), 0.1 mM dNTP and incubation at 12°C for 15 min. EDTA (10 mM) was added to stop the enzymatic reaction (20 min incubation at 75°C). All 6 samples were pooled and loaded as a unique sample on a 1% agarose gel,

sequencing

Fragments were sequenced using the Roche 454 Life Sciences Genome Sequencer FLX following the manufacturer's instructions for the Titanium series (454 Life Science, Roche). Libraries were prepared according to the 454 protocol: nebulization (only for the cDNA), purification, and ligation of adaptors. The libraries were prepared with ~9 μg (AFLP® fragments) or ~1 μg (cDNA fragments) using the "Titanium General Library Preparation Kit". Both genome representations were treated alike, except that AFLP® fragments did not undergo the first 3 steps (nebulization, Ampure purification, fragment end polishing). Because the recovered quantities were very low, cDNA library preparation was optimized as in [START_REF] Maricic | Optimization of 454 sequencing library preparation from small amounts of DNA permits sequence determination of both DNA strands[END_REF] by retrieving fragments through heat denaturation: samples were eluted in 45 μL water, vortexed, denatured for 2 min at 90°C, and transferred to ice. A pellet of beads was obtained with the magnet, and the supernatant was collected and mixed with TE 10/1 to a final concentration of 1×. DNA fragments were amplified using the "GS FLX Titanium SV emPCR Kit" (cDNA) or "GS FLX Titanium LV emPCR Kit" (AFLP® fragments). Sequencing on the Genome Sequencer FLX was performed using the "GS FLX Sequencing Kit Titanium Reagents XLR70".

Sequence analyses

The sequences are available at NCBI (http://www.ncbi. nlm.nih.gov/, SRA database, Accession number SRP002189).

Genomic AFLP® fragments

AFLP® fragments were sequenced using a half-plate, producing 373,484 reads and nearly 92 Mb. The average depth (8.6× for 4,929 analysed contigs, but with 56% of sequences as singlets) could be improved by performing other sequencing runs. The average sequence length (246 bp) should be increased by a gel cut at a higher size around 400 bp, or a reamplification step with 2 to 3 selective nucleotides -to limit the number of different fragments and keep an acceptable coverage -followed by an Ampure purification to remove short fragments.

We tagged each sample individually before making the 454 library on the pooled individuals. This procedure can have many applications, by drastically reducing the cost time spent and the amount of samples needed for this step. Library preparation is an important step in the sequencing protocol, regarding both handling time and financial costs. Moreover, each library requires a minimum amount of DNA or RNA starting material. Here, a single library is prepared instead of one per sample when tagging and multiplexing individual libraries. In addition, when sample selection is performed by sizing on gel, multiplexing individuals before retrieving the DNA fraction decreases the number of gels cuts and DNA extractions before library preparation. An important point here is also to avoid potential bias in the representation of each individual genome that could be caused by unavoidable slight difference between gel migrations and size estimations when cutting the gels.

Out of 289,703 sequences longer than 120 bp, for which we analysed the presence of a tag, only a small proportion of sequences (454) did not show a tagged AFLP® primer at either end, with a tagging efficiency of 99.99%. However, only 55.8% (161,478/289,249) of sequences bore a tag at both ends. Given the average length of the sequenced fragments (the fraction was obtained from a 200-400 bp gel cut, but fragment lengths spanned a larger, about 100-500 bp, interval) and the average sequence length (246 bp), one could have expected a larger proportion of double-tagged fragments. Ninety five percent (153,469) of the double-tagged sequences showed the same tag at both ends. The remaining 5% either were chimeras with two different tags or included 1 or 2 false tags due to sequencing errors (tags not present in the primers we used). The relative representation of each sample according to its identification by the tagging approach was variable, but acceptable. The most abundant tag was only twice as frequent as the least frequent one (table 2). As observed previously for the very 5′end of the tag [START_REF] Van Orsouw | Complexity reduction of polymorphic sequences (CRoPS): a novel approach for large-scale polymorphism discovery in complex genomes[END_REF][START_REF] Binladen | The use of coded PCR primers enables high-throughput sequencing of multiple homolog amplification products by 454 parallel sequencing[END_REF], the presence of an AC sequence in the tag may have led to an underrepresentation of the TACG tag. Our experiments expand the use of CRoPS™ [START_REF] Van Orsouw | Complexity reduction of polymorphic sequences (CRoPS): a novel approach for large-scale polymorphism discovery in complex genomes[END_REF] technology to the Titanium version of 454 sequencing, without the need for modified sequencing primers, and with a single preamplification step.

Using AFLP® fragments to obtain a reduced representation of the genome allows developing SNP markers even for species lacking a whole-genome draft sequence [START_REF] Van Orsouw | Complexity reduction of polymorphic sequences (CRoPS): a novel approach for large-scale polymorphism discovery in complex genomes[END_REF]. Furthermore, the amplification step allows using a very small amount of DNA for the library preparation. The occurrence number of each double-tag is shown.

The major advantage of this method when compared to the gel cut RRL (Reduced Representation Library), described for example by Van Tassel in cattle [START_REF] Van Tassell | SNP discovery and allele frequency estimation by deep sequencing of reduced representation libraries[END_REF], is the possibility to multiplex several individuals in the same library preparation by using tagged PCR-primers, which was first done by Binladen and co-workers for a mitochondrial PCR fragment [START_REF] Binladen | The use of coded PCR primers enables high-throughput sequencing of multiple homolog amplification products by 454 parallel sequencing[END_REF]. The possibility offered here to identify the individual origin of each sequence and its SNP alleles allows to detect line-specific SNP, or to target directly for SNP informative in a dedicated cross, when sequencing F1 animals. These opportunities are absent for classical RRL sequencing without individual tagging. In addition, the use of 454 sequencing allowed the production of a sufficient amount of sequence flanking the SNP, which is essential for designing genotyping assays, in species where no genome draft is available [START_REF] Van Tassell | SNP discovery and allele frequency estimation by deep sequencing of reduced representation libraries[END_REF]. This would not have been the case with the Illumina technology available at the time.

cDNA fragments

For cDNA fragment sequencing, 6 quarter-plate runs (one for each tissue in each line), with an additional 1/8 of run gave a total of 399,189 reads and 154.3 Mb of sequence in total. The heterogeneity of the results (from 37,385 to 134,598 sequences per quarter-plate run) was partially due to the variable efficiency of the library preparations and we expect improved yields in the future. As previously observed [START_REF] Craft | Pyrosequencing of Mytilus galloprovincialis cDNAs: tissue-specific expression patterns[END_REF], 454 runs on cDNA produce a smaller quantity of sequences than runs on genomic DNA. These sequences were assembled into 31,010 contigs (average depth of 11, from 2 to 3049), 36,572 sequences remaining as singlets.

Our method brings two important improvements to the classical 454 cDNA library preparation protocol. First, through the use of the heat-denaturation step [START_REF] Maricic | Optimization of 454 sequencing library preparation from small amounts of DNA permits sequence determination of both DNA strands[END_REF] instead of the melting one (single-strand DNA is released from the beads through NaOH denaturation), a greater proportion of fragments is retrieved, and the use of a PCR step in the cDNA preparation becomes useless. The higher yield of heat treatment is notably due to the breaking of the biotin-streptavidin interaction.

This can be of great benefit when only a small amount of RNA is available, and when one wishes to avoid additional possible bias associated with PCR amplification: as PCR amplification from complex mixtures may generate representational differences between fragments [START_REF] Pinard | Assessment of whole genome amplification-induced bias through high-throughput, massively parallel whole genome sequencing[END_REF], we chose to avoid any PCR amplification prior to the library preparation for the cDNA experiment. This allows the observed difference between samples of sequence frequencies for a given gene, to exactly represent its level of differential expression. Second, the use of a modified oligodT primer for the Reverse-Transcription step, associated with cDNA hemimethylation and GsuI enzyme digestion, as suggested by Shibata et al [START_REF] Shibata | Removal of polyA tails from full-length cDNA libraries for high-efficiency sequencing[END_REF], dramatically decrease the loss of efficiency in 454 sequencing related to homopolymers, especially problematic in the case of cDNA due to the poly(T) tail [START_REF] Wicker | 454 sequencing put to the test using the complex genome of barley[END_REF]. In the present study, most of the 3′-end sequences were "polyA-cleaned" by the GsuI treatment with only 647 fragments displaying the modified oligodT primer. A PCR-based method to limit the 3′ homopolymer has also been described by Beldade [START_REF] Beldade | A wing expressed sequence tag resource for Bicyclus anynana butterflies, an evo-devo model[END_REF], but would then have all the disadvantages related to PCR.

A preliminary analysis allowed detecting more than 8,500 putative SNP from these data: 6,888 from the cDNA sequences and 1,695 from the genomic fragments. Their experimental validation remains to be performed.

The methods presented in this paper may be used for several 454 sequencing applications like de novo sequencing, tagged PCR fragments sequencing or long fragment sequencing of cDNA.

Table 1

 1 Primers used for AFLP amplification in 1× TBE buffer, and visualized by staining with ethidium bromide. A 200-400 bp fractionwas recovered from the gel by cutting out the corresponding band and purifying the DNA with the Nucleospin Extraction kit (NucleoSpin® Extract II, Macherey-Nagel).

	Primer Name	Sequence
	EcoApTACG	P-TACGCTGCGTTACCAATTCA
	TaqApTACG	P-TACGGATGAGTCCTGACCGAA
	EcoApTAGA	P-TAGACTGCGTTACCAATTCA
	TaqApTAGA	P-TAGAGATGAGTCCTGACCGAA
	EcoApTATC	P-TATCCTGCGTTACCAATTCA
	TaqApTATC	P-TATCGATGAGTCCTGACCGAA
	EcoApTCAG	P-TCAGCTGCGTTACCAATTCA
	TaqApTCAG	P-TCAGGATGAGTCCTGACCGAA
	EcoApTCGT	P-TCGTCTGCGTTACCAATTCA
	TaqApTCGT	P-TCGTGATGAGTCCTGACCGAA
	EcoApTCTA	P-TCTACTGCGTTACCAATTCA
	TaqApTCTA	P-TCTAGATGAGTCCTGACCGAA
	EcoApTGAT	P-TGATCTGCGTTACCAATTCA
	TaqApTGAT	P-TGATGATGAGTCCTGACCGAA
	EcoApTGCA	P-TGCACTGCGTTACCAATTCA
	TaqApTGCA	P-TGCAGATGAGTCCTGACCGAA

The 5′-ends are phosphorylated. The first 4 bases are the identification tags. electrophoresed

Table 2

 2 Representation of each individual in the 153,469 double-tagged AFLP sequences

	Tag pair	Occurrences	Proportion (%)
	TACG	16418	10.7
	TAGA	27842	18.1
	TATC	34031	22.2
	TCAG	25944	16.9
	TCGT	28595	18.6
	TCTA	20639	13.5

Acknowledgements

We thank Margot Paris and Pierre Taberlet for fruitful discussion. The research program was supported by a grant from the French Institut National de la Recherche Agronomique (AIP Bioressources INRA) and the helpful support of the Plateforme génomique (PlaGe), Génopole Toulouse-Midi-Pyrénées. The AFLP® and CRoPS® technologies are covered by patents and patent applications owned by Keygene N.V. AFLP® and CRoPS® are registered trademarks of Keygene N.V.

Author details 1 UMR INRA/ENVT Laboratoire de Génétique Cellulaire, INRA, 31326 Castanet-Tolosan, France. 2 Plateforme génomique (PlaGe), Génopole Toulouse-Midi-Pyrénées, INRA, 31326 Castanet-Tolosan, France. 3 Authors' contributions SL, KF, FV and OB carried out the molecular studies. CK, CN and FP performed the sequence analyses. DG, SRD, CA, CL, CB and FM carried out the animal design and experiments. FP and AV conceived the study, and participated in its design and coordination. FP, SL, KF and FV drafted the manuscript. All authors finalized and approved the manuscript.

Competing interests

The authors declare that they have no competing interests.


Bastien Fernandez

Lev S Tsimring

Athermal dynamics of strongly coupled stochastic three-state oscillators

Keywords:

We study the collective behavior of a globally coupled ensemble of cyclic stochastic three-state systems with transition rates from state i -1 to state i proportional to the number of systems already in state i. While the mean field theory predicts only decaying oscillations in this system, direct numerical simulations indicate that the mean field exhibits stochastic oscillations even in the limit of large number of oscillators. We characterize the regularity of oscillations by the coherence parameter which has a well-defined maximum at the coupling constant of order 1. In contrast, the order parameter characterizing the level of synchrony among oscillators, increases monotonously with the coupling strength. We derive the exact solution of the full master equation for the stationary probability distribution and find the analytical expression for the order parameter.

Interacting stochastic systems emerge in a variety of physical and biological contexts, from arrays of Josephson junctions [1] and laser arrays [2] to neural networks [START_REF] Abeles | Corticonics: Neural Circuits of the Cerebral Cortex[END_REF][START_REF] Tsodyks | [END_REF] and gene regulatory networks [5,6]. While the dynamics of individual elements can be rather complicated and non-generic, the dynamics of a large ensemble of coupled units often exhibits universal behavior. Therefore, studies of canonical models with simple individual dynamics and interaction rules have proven very useful for understanding the behavior of specific systems. Well-known examples of such canonical systems are the Desai-Zwanzig model [7] of coupled bistable systems and the Kuramoto model [START_REF] Kuramoto | Chemical oscillations, waves, and turbulence[END_REF] of coupled phase oscillators. The Kuramoto model and its many variations and generalizations (see [START_REF] Acebrón | [END_REF]) have been very successful in describing the transition to coherent oscillations in ensembles of coupled phase oscillators. Stochastic dynamics of individual elements in such models are described by coupled nonlinear Langevin equations. In the thermodynamic limit, they can be reduced to low-dimensional deterministic equations for the mean field or the order parameter characterizing global behavior of large systems.

A simpler way of describing interacting stochastic systems incorporates stochastic elements with a discrete set of states with certain transition rates. It is most often done for bistable systems which are replaced by two-state stochastic systems with suitably chosen transition rates. For example, array-enhanced stochastic resonance has been studied in a system of globally coupled two-state systems [10]. A transition to regular oscillations in an ensemble of two-state systems coupled through a delayed mean field was studied in [11].

Recently, Prager et al. [12] introduced a globally coupled three-state stochastic "oscillators" with unidirectional (1 → 2 → 3 → 1) transitions as a paradigmatic model of noise-driven excitable systems. This model is simple enough to make analytical and large-scale numerical studies of large systems feasible [12,13]. An important property is their behavior in the thermodynamic limit, when the number of units approaches infinity. Prager et al. [12] considered Markovian systems with transition rates depending on the suitably defined mean field and found no Hopf bifurcation in the thermodynamic limit. Instead, they found oscillations in this limit if the transitions between states are characterized by nonexponential waiting time distributions which imply non-Markovian dynamics. Later, Wood et al. [13] studied the dynamics of both globally and locally coupled Markovian three-state systems in the thermodynamic limit and did find a supercritical Hopf bifurcation to coherent periodic oscillations for strong enough coupling. While the individual systems considered in [12] and [13] were essentially identical, the difference between the models was in the way the coupling between the systems was introduced.

In this Letter we focus on the seemingly "less interesting" situation when the Markovian dynamics of a globally coupled ensemble of three-state systems does not exhibit a Hopf bifurcation. However, we find that in any finitesize system, quasi-regular oscillations of the mean field are present. We introduce the coherence parameter which characterizes regularity of mean field oscillations, and the order parameter which characterizes the degree of synchrony among the oscillators. We show that while the order parameter increases monotonously with the coupling strength, the coherence parameter has a maximum at a certain intermediate coupling strength. The simplicity and a high degree of symmetry in the system under study allow us to find the statistical properties of the finite ensemble analytically.

A single stochastic three-state unit with unidirectional transitions is schematically shown in the inset to Fig. 1b. We assume that in an isolated unit all three transitions from state i (i = 1, 2, 3) to state i + 1(mod3) are Markovian with identical rate a [14]. Without loss of generality we take a = 1. Statistical properties of this system have been investigated in Ref. [12]. The cyclic behavior of a single oscillator is characterized by the mean time T of an oscillator to return to the initial state after an excursion through the other two states. Since the mean time of switching from state i to state i + 1 is T s = 1, we get T = 3T s = 3. The probability for a system to be in state i = 1, 2, 3 at time t is given by the continuous-time master equation

Ṗi = -P i + P i-1 , i = 1, 2, 3 (1)
This master equation has a fixed point P s 1 = P s 2 = P s 3 = 1/3 corresponding to equipartition among the three states, and three eigenvalues λ k = -1 + e 2iπk/3 , k = 0, 1, 2. The first eigenvalue (k = 0) corresponds to the conservation of the total probability, and the other two describe equilibration of the probability distribution among the three states. Imaginary part of these eigenvalues implies that there are decaying periodic oscillations of deviations from equipartition with the mean frequency ω = √ 3/2. Globally coupled three-state oscillators. Now let us consider an ensemble of N identical three-state oscillators. The specific mechanism of coupling is the following. We assume that the probability π i,i+1 of switching of an oscillator from a state i to state i + 1 at time t is linearly proportional to the number of oscillators n i+1 (t) already at state i + 1 at time t, with the proportionality constant b (which we call coupling coefficient), π i,i+1 (t) = 1+b n i+1 (t). This type of coupling is reminiscent of the auto-catalytic transitions in gene regulatory circuits when multiple copies of a single gene are present in the cell.

Since this model is Markovian, it can be efficiently simulated using Gillespie algorithm [15]. Figure 1 shows sample stochastic trajectories for the occupation number of oscillators in states 1,2, and 3 as a function of time for different values of coupling parameter b for N = 1000. The initial condition for all cases is n 1 (0) = N, n 2,3 (0) = 0. For b = 0, the population slowly drifts toward an equilibrium state with n 1 = n 2 = n 3 = N/3 with O(N 1/2 ) stochastic fluctuations. For even very small non-zero b 1, noisy oscillations around the mean become visible. As b grows, the period becomes shorter, and the amplitude of oscillations grows until for b ∼ 1 it approaches N , i.e. almost all oscillators are simultaneously in the same state. At large b 1, the system exhibits switching behavior resembling the dynamics of a single oscillator. It is easy to understand: at very large b, once a single oscillator makes a transition from state i to state i + 1 (which occurs with rate N ), all other oscillators quickly follow. So indeed in the limit b 1 the dynamics of the ensemble becomes equivalent to the dynamics of a single oscillator with a rescaled transition rate N , a result confirmed by analytical calculations [20].

We computed the power spectrum of the time series of the occupation numbers and determined the central frequency ω and the half-width ∆ω of the spectral peak. We call the ratio CP=ω/∆ω the coherence parameter. Figure 2a shows ω, ∆ω, and CP as functions of the coupling parameter b. Both ω and ∆ω increase with b, however the coherence parameter has a distinct maximum at b ≈ 1, see Fig. 2a. This value appears to be independent of N for large enough N . Thus, we observe a manifestation of the coherence resonance [16], however the difference is that the maximum appears not at a certain noise strength but a certain value of the coupling. This coherence resonance should not be confused with synchronization among the oscillators. The degree of synchronization can be characterized by the order parameter

R = N -1 N j=1 e iφj 2 (2)
with discrete phases of oscillators φ j = 2πk/3, k = 1, 2, 3. This order parameter was introduced by [13] by analogy with coupled continuum phase oscillators in the Kuramoto model [START_REF] Kuramoto | Chemical oscillations, waves, and turbulence[END_REF]. The order parameter is zero when all oscillators are equally distributed among the three states (n 1 = n 2 = n 3 = N/3), and it approaches unity if all oscillators are perfectly synchronized, so all of them are simultaneously in the same state. As expected, the order parameter increases monotonously with b, see Fig. 2b. As Figure 2b shows, the order parameter for a given b is independent of the number of oscillators in population N .

Mean-field approximation. In the thermodynamic limit N → ∞ of globally coupled oscillators, the mean-field equations for the deterministic "concentrations" of oscillators

x i = n i /N are given by ẋi = x i-1 (1 + bN x i ) -x i (1 + bN x i+1 ), i = 1, 2, 3(mod3)
(3) From the symmetry of the underlying dynamics it immediately follows that the fixed point of this system is x 1 = x 2 = x 3 = 1/3. The associated two complex eigenvalues (the first eigenvalue is 0 as before because of the conservation law) λ 2,3 = - negative real part, which indicates the absence of Hopf bifurcation at any coupling b. This is in contrast with the model by Wood et al. [13], in which a different form of coupling was proposed (the transition rate from i to i + 1 was an exponential function of the linear combination of n i±1 , n i ), for which the mean field had a Hopf bifurcation at large enough coupling strength [START_REF]For a general nonlinear transition probability πi[END_REF].

Stochastic description. The full description of the stochastic properties of the system is given by the master equation for the probability p(n 1 , n 2 , n 3 ) that at time t there are n 1 oscillators at state 1, n 2 at state 2, and n 3 at state 3 (obviously,

n 1 + n 2 + n 3 = N ), ṗ(n 1 , n 2 , n 3 ) = (n 1 + 1)[1 + b(n 2 -1)]p(n 1 + 1, n 2 -1, n 3 ) +(n 2 + 1)[1 + b(n 3 -1)]p(n 1 , n 2 + 1, n 3 -1) +(n 3 + 1)[1 + b(n 1 -1)]p(n 1 -1, n 2 , n 3 + 1) -[N + b(n 1 n 2 + n 2 n 3 + n 3 n 1 )]p(n 1 , n 2 , n 3 )(4)
The total number of states (n 1 , n 2 , n 3 ) in this system is (N + 2)(N + 1)/2. It is convenient to depict the state space as a triangular grid, see Figure 3a.

According to the Frobenius-Perron Theorem, the master equation has a unique stationary solution. We were able to find the exact solution in a closed form,

p s (n 1 , n 2 , n 3 ) = C b G(b, n 1 )G(b, n 2 )G(b, n 3 ) n 1 !n 2 !n 3 ! (5)
where

G(x, n) = n-1 k=0
(1 + kx) and C b is the normalization constant, which can be verified by direct substitution. Expression (5) shows that the stationary solution is not only invariant with respect to cyclic permutations but also with respect to any permutation of coordinates (n 1 , n 2 , n 3 ). This property is remarkable because the equation itself does not possess this symmetry.

It is easy to check by direct substitution that (5) satisfies the relation and two other relations obtained from ( 6) by cyclic permutations (adding these 3 relations and using the rotation symmetry gives the stationary master equation equation (4) without l.h.s.).

(n 3 + 1)[1 + b(n 1 -1)]p s (n 1 -1, n 2 , n 3 + 1) = n 1 (1 + bn 3 )p s (n 1 , n 2 , n 3 ) (6) a+b (0,3,0) (0,2,1) (0,1,2) (0,0,3) (1,0,2) (2,0,1) (3,0,0) (2,1,0) (1,2,0) (1,1,1) (a)
It is straightforward to obtain convexity properties of the stationary solution (5). Indeed, according to (6), we have

p s (n 1 -1, n 2 , n 3 + 1) < p s (n 1 , n 2 , n 3 ) iff 0 < (n 3 + 1 -n 1 )(1 -b). If b < 1 (resp. b > 1)
the probability increases (resp. decreases) when one moves one step to the right in the left part of the triangular lattice and vice versa [START_REF]The left part of the lattice corresponds to points for which N1 ≤[END_REF]. Combining it with the rotation symmetry, we conclude that the distribution is convex with a maximum in the center when b < 1 and concave with a maximum in the corners for b > 1; for b = 1 the distribution is flat.

For zero coupling (b = 0), the stationary distribution is trinomial

p s (n 1 , n 2 , n 3 ) = N ! 3 N n 1 !n 2 !n 3 !
which of course could be deduced directly since oscillators are independent and in the long term limit they become uniformly distributed among the three states. The most probable state is in the middle of the triangle (n 1 = n 2 = n 3 = N/3) and the least probable states are in the corners (N, 0, 0), (0, N, 0), (0, 0, N ).

For large b, the stationary distribution is highly localized at the corners. However there is a small (O(1/b)) probability flux in and out of the corners. In the first order of 1/b, the stationary probability distribution is

p s (n, 0, N -n) = N 3bn(N -n) + O(1/b 2 ), n = 1, N -1 p s (0, 0, N ) = 1 3 - 2 3b N -1 k=1 1 k + O(1/b 2 )
(the remaining state probabilities follow from cyclic permutation) and p s (n 1 , n 2 , n 3 ) = O(1/b 2 ) for n 1 n 2 n 3 = 0. Thus the probability distribution has a deep minimum at the center of the triangle, and sharp peaks in the corners (Fig. 3e). The dynamics close to equilibrium can be approximated by the probability flow around the edges of the triangle, ignoring the influence of the inner nodes. This simplification allows us to compute the nonzero eigenvalues of the full system in the first order in 1/b [20]. As expected, for large b these eigenvalues are

λ k N + O(1/b 2 ), k = 1, 2
, where λ k are the eigenvalues of the single oscillator. It is interesting to note that the equilibration rate Re(-λ 1,2 N ) is independent of b.

For large n 1 , n 2 and n 3 one can use Stirling formula to find an asymptotic expression for the distribution (5),

p s (n 1 , n 2 , n 3 ) = C b b N Γ 3 (1/b) (n 1 n 2 n 3 ) 1/b-1 (7)
with

C b = b -N Γ(3/b)Γ -2 (1/b)N 1-2/b
. We can use this expression, replace summation by integration and compute the order parameter for large N explicitly [START_REF] When | [END_REF]. This straightforward calculation results in a surprisingly simple formula

R = b b + 3 (8)
This formula agrees very well with direct Gillespie simulations (Fig. 2b). Note that the order parameter is independent of N (at least for large N ). For arbitrary N , the order parameter can be computed from the stationary distributions at zero coupling and large coupling respectively. For zero coupling, we get R = 1/N and for large coupling, we have R

= 1 -3 b (1 -1 N ) + O(1/b 2
). Discussion. Our analysis indicates that in the system of globally coupled three-state units there are significant stochastic oscillations, and while the frequency of these oscillators scales as N , their temporal coherence reaches maximum at a finite b ∼ 1 independent of the number of oscillators. This result is counterintuitive, since the mean-field theory predicts no sustained oscillations in the thermodynamic limit N → ∞. The origin of this apparent contradiction is that for sufficiently large coupling strength, the implicit assumption of decorrelated dynamics of individual noisy units is violated. For b ∼ 1, the transition rate of the "last" oscillators remaining in state i when most of them are already in state i + 1, is large, O(N ), and so the transitions of these "last" oscillators are strongly correlated. For large b, all oscillators are strongly correlated: as soon as the first one makes a transition, the rest very quickly follows. This leads to the correlated and thus athermal behavior of the globally coupled system at large b. Of course, in any real system the transition rate should saturate as N → ∞. Then eventually the thermal behavior of the system would be recovered, however in the intermediate scaling regime of finite N the dynamics described here can be observed. Note that our results are easily generalizable to the case of arbitrary p-state oscillators with any p > 2. The order parameter for p-oscillators is simply R p = b/(b + p), and the coherence parameter reaches maximum at b ∼ 1. However, the behavior of boolean systems (p = 2) is different: while the order parameter still exhibits the same behavior (R 2 = b/(b + 2)), the quasi-regular oscillations are completely absent, and the coherence parameter remains small O(1) throughout the full range of b.

Authors are indebted to K. Lindenberg for an illuminating discussion, and to the anonymous referee for a suggestion to consider arbitrary p-state oscillators. LT is grateful to CNRS and to University of Aix-Marseille I for hospitality and support. This work was partially supported by ACI IMPBio (BF) and MURI and NIH (LT)

FIG. 1 :

 1 FIG. 1: Time series of the instantaneous occupation numbers oscillators n1, n2, n3 in states 1, 2, 3 respectively for N = 1000, and different values of the coupling parameter: (a) b = 0, (b) b = 0.1 (Inset: Transition diagram in a single unit); (c) b = 1, (d) b = 10.

4 FIG. 2 :

 42 FIG. 2: Gillespie simulations of coupled stochastic oscillators: (a) mean frequency ω (blue squares), bandwidth ∆ω (black diamonds), and the coherence parameter CP (red circles) vs. b for N = 100. (b) Order parameter R vs. b for N = 10 2 , 10 3 , 10 4 . Solid line corresponds to formula (8).

FIG. 3 :

 3 FIG. 3: (a)State space of the three-oscillator system N = 3; correspond to distinct states (n1, n2, n3) of the system, and arrows indicate transitions among the states. Expressions at the arrows show the corresponding transition rates. (b-e) Stationary probability distributions for N = 14 and b = 0.2 (b), b = 0.8 (c), b = 1 (d) , b = 2 (e).