Alin Bostan
email: alin.bostan@inria.fr

Pierre Lairez
email: pierre@lairez.fr

Bruno Salvy
email: bruno.salvy@inria.fr

Multiple binomial sums

Keywords: Mathematics Subject Classification. 05A10 (33F10 68W30) Binomial sum, multiple sum, symbolic computation, diagonal, integral representation

published or not. The documents may come

Introduction

The computation of definite sums in computer algebra is classically handled by the method of creative telescoping initiated in the 1990s by Zeilberger [START_REF] Zeilberger | A holonomic systems approach to special functions identities[END_REF](Zeilberger , 1991a;;[START_REF] Wilf | An algorithmic proof theory for hypergeometric (ordinary and "q") multisum/integral identities[END_REF]. For example, it applies to sums like In order to compute a sum k u(n, k) of a bivariate sequence u, this method computes an identity of the form

a p (n)u(n + p, k) + • • • + a 0 (n)u(n, k) = v(n, k + 1) -v(n, k).
Provided that it is possible to sum both sides over k and that the sequence v vanishes at the endpoints of the domain of summation, the left-hand side-called a telescoper-gives a recurrence for the sum. The sequence v is then called the certificate of the identity.

In the case of multiple sums, this idea leads to searching for a telescoping identity of the form [START_REF] Furstenberg | Algebraic Functions over Finite Fields[END_REF]

a p (n)u(n + p, k 1 , . . . , k m ) + • • • + a 0 (n)u(n, k 1 , . . . , k m ) = v 1 (n, k 1 + 1, k 2 , . . . , k m ) -v 1 (n, k 1 , . . . , k m ) + • • • + v m (n, k 1 , . . . , k m + 1) -v m (n, k 1 , . . . , k m ) .
Again, under favorable circumstances the sums of the sequences on the right-hand side telescope, leaving a recurrence for the sum on the left-hand side. This high-level presentation hides practical difficulties. It is important to check that the sequences on both sides of the identities above are defined over the whole range of summation [START_REF] Abramov | On the summation of P -recursive sequences[END_REF][START_REF] Abramov | Gosper's algorithm, accurate summation, and the discrete Newton-Leibniz formula[END_REF]. More often than not, singularities do appear. To the best of our knowledge, no algorithm based on creative telescoping manages to work around this difficulty; they all let the user handle it. As a consequence, computing the certificate is not merely a useful by-product of the algorithm, but indeed a necessary part of the computation. Unfortunately, the size of the certificate may be much larger than that of the final recurrence and thus costly in terms of computational complexity.

The computation of multiple integrals of rational functions has some similarities with the computation of discrete sums and the method of creative telescoping applies there too. It may also produce extra singularities in the certificate, but in the differential setting this is not an issue anymore: for the integrals we are interested in, the integration path can always be moved to get around any extra singularity. Moreover, we have showed (Bostan et al. 2013a;Lairez 2016) that integration of multivariate rational functions over cycles can be achieved efficiently without computing the corresponding certificate and without introducing spurious singularities. In that case, the algorithm computes a linear differential equation for the parameterized integral. It turns out that numerous multiple sums can be cast into problems of rational integration by passing to generating functions. The algorithmic consequences of this observation form the object of the present work.

Content.

In §1, we define a class of multivariate sequences, called (multiple) binomial sums, that contains the binomial coefficient sequence and that is closed under pointwise addition, pointwise multiplication, linear change of variables and partial summation. Not every sum that creative telescoping can handle is a binomial sum: for example, among the three sums in Eq. ( 1), the second one and the third one are binomial sums but the first one is not, since it contains the inverse of a binomial coefficient; moreover, it cannot be rewritten as a binomial sum (see §1.2). Yet many sums coming from combinatorics and number theory are binomial sums. In §2, we explain how to compute integral representations of the generating function of a binomial sum in an automated way. The outcome is twofold. Firstly, in §3, we work further on these integral representations to show that the generating functions of univariate binomial sums are exactly the diagonals of rational power series. This equivalence characterizes binomial sums in an intrinsic way which dismisses the arbitrariness of the definition. All the theory of diagonals transfers to univariate binomial sums and gives many interesting arithmetic properties. Secondly, in §4, we show how to use integral representations to actually compute with binomial sums (e.g. find recurrence relations or prove identities automatically) via the computation of Picard-Fuchs equations. The direct approach leads to integral representations that involve far too many variables to be efficiently handled. In §5, we propose a general method, that we call geometric reduction, to reduce tremendously the number of variables in practice. In §6, we describe some variants with the purpose of implementing the algorithms, and finally, in §7, we show how the method applies to some classical identities and more recent ones that were conjectural so far.

All the algorithms that are presented here are implemented in Maple and are available at https://github.com/lairez/binomsums.

Example.

The following proof of an identity of [START_REF] Dixon | On the sum of the cubes of the coefficients in a certain expansion by the binomial theorem[END_REF],

(3)

2n k=0 (-1) k 2n k 3 = (-1) n (3n)! n! 3 ,
illustrates well the main points of the method. The strategy is as follows: find an integral representation of the generating function of the left-hand side; simplify this integral representation using partial integration; use the simplified integral representation to compute a differential equation of which the generating function is solution; transform this equation into a recurrence relation; solve this recurrence relation.

First of all, the binomial coefficient n k is the coefficient of x k in (1+x) n . Cauchy's integral formula ensures that

n k = 1 2πi γ (1 + x) n x k dx x ,
where γ is the circle x ∈ C |x| = 1 2 . Therefore, the cube of a binomial coefficient can be represented as a triple integral

2n k 3 = 1 (2πi) 3 γ×γ×γ (1 + x 1 ) 2n x k 1 (1 + x 2 ) 2n x k 2 (1 + x 3 ) 2n x k 3 dx 1 x 1 dx 2 x 2 dx 3 x 3 .
As a result, the generating function of the left-hand side of Equation ( 3) is

y(t) def = ∞ n=0 t n 2n k=0 (-1) k 2n k 3 = 1 (2iπ) 3 γ 3 ∞ n=0 2n k=0 t 3 i=1 (1 + x i ) 2 n -1 x 1 x 2 x 3 k dx 1 x 1 dx 2 x 2 dx 3 x 3 = 1 (2iπ) 3 γ 3 ∞ n=0 t 3 i=1 (1 + x i ) 2 n 1 - -1 x1x2x3 2n+1 1 + 1 x1x2x3 dx 1 x 1 dx 2 x 2 dx 3 x 3 = 1 (2iπ) 3 γ 3 x 1 x 2 x 3 -t 3 i=1 (1 + x i ) 2 dx 1 dx 2 dx 3 x 2 1 x 2 2 x 2 3 -t 3 i=1 (1 + x i ) 2 1 -t 3 i=1 (1 + x i ) 2
.

The partial integral with respect to x 3 along the circle |x 3 | = 1 2 is the sum of the residues of the rational function being integrated at the poles whose modulus is less than 1 2 . When |t| is small and |x 1 | = |x 2 | = 1 2 , the poles coming from the factor x 2 1 x 2 2 x 2 3 -t 3 i=1 (1 + x i ) 2 all have a modulus that is smaller than 1 2 : they are asymptotically proportional to |t| 1/2 . In contrast, the poles coming from the factor 1 -t 3 i=1 (1 + x i ) 2 behave like |t| -1/2 and have all a modulus that is bigger than 1 2 . In particular, any two poles that come from the same factor are either both asymptotically small or both asymptotically large. This implies that the partial integral is a rational function of t, x 1 and x 2 ; and we compute that

y(t) = 1 (2iπ) 2 γ×γ x 1 x 2 dx 1 dx 2 x 2 1 x 2 2 -t(1 + x 1 ) 2 (1 + x 2 ) 2 (1 -x 1 x 2 )
2 . This formula echoes the original proof of [START_REF] Dixon | On the sum of the cubes of the coefficients in a certain expansion by the binomial theorem[END_REF] in which the left-hand side of (3) is expressed as the coefficient of (xy

) 4n in ((1 -y 2 )(1 -z 2 )(1 -y 2 z 2 )) 2n .
Using any algorithm that performs definite integration of rational functions [START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF][START_REF] Koutschan | A fast approach to creative telescoping[END_REF]Lairez 2016) reveals a differential equation satisfied by y(t): t(27t + 1)y + (54t + 1)y + 6y = 0.

Looking at the coefficient of t n in this equality leads to the recurrence relation 3(3n + 2)(3n + 1)u n + (n + 1) 2 u n+1 = 0, where u n = 2n k=0 (-1) k 2n k 3 . Since u 0 = 1, it leads to a proof of Dixon's identity by induction on n. The treatment above differs in one important aspect from what follows: the use of genuine integrals and explicit integration paths rather than formal residues that will be introduced in §2.

Comparison with creative telescoping. As mentioned above, the computation of multiple binomial sums can be handled by the method of creative telescoping. The amount of work in this direction is considerable and we refer the reader to surveys [START_REF] Chyzak | A Computer-Algebra-Based Formal Proof of the Irrationality of ζ(3)[END_REF]Koutschan 2013). In the specific context of multiple sums, the most relevant works are those of [START_REF] Wegschaider | Computer Generated Proofs of Binomial Multi-Sum Identities[END_REF], [START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF], [START_REF] Apagodu | Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory[END_REF], and [START_REF] Garoufalidis | A new algorithm for the recursion of hypergeometric multisums with improved universal denominator[END_REF]. We show on the example of Dixon's identity how the method of creative telescoping and the method of generating functions differ fundamentally even on a single sum.

Let u n,k = (-1) k 2n k 3 . This bivariate sequence satisfies the recurrence relations

(4) (2n + 2 -k) 3 (2n + 1 -k) 3 u n+1,k -8(1 + n) 3 (1 + 2n) 3 u n,k = 0 and (k + 1) 3 u n,k+1 + (2n -k) 3 u n,k = 0.
With these relations as input, Zeilberger's algorithm finds the sequence

v n,k = P (n, k) 2(2n + 2 -k) 3 (2n + 1 -k) 3 u n,k , where P (n, k) = k 3 (9k 4 n -90k 3 n 2 + 348k 2 n 3 -624kn 4 + 448n 5 + 6k 4 -132k 3 n + 792k 2 n 2 -1932kn 3 + 1760n 4 -48k 3 + 594k 2 n -2214kn 2 + 2728n 3 + 147k 2 -1113kn + 2084n 2 -207k + 784n + 116), that satisfies (5) 3(3n + 2)(3n + 1)u n,k + (n + 1) 2 u n+1,k = v n,k+1 -v n,k .
Whatever the way the sequence v n,k is found, it is easy to check the telescopic relation (5): using the recurrence relations for u n,k , each of the four terms in (5) rewrites in the form R(n, k)u n,k , for some rational function R(n, k). However, for some specific values of n and k, the sequence v n,k is not defined, due to the denominator.

To deduce a recurrence relation for a n = 2n k=0 u n,k , it is desirable to sum the telescopic relation (5), over k, from 0 to 2n + 2. Unfortunately, that would hit the forbidden set where v n,k is not defined. We can only safely sum up to k = 2n -1. Doing so, we obtain that 3(3n + 2)(3n + 1)

2n-1 k=0 u n,k + (n + 1) 2 2n-1 k=0 u n+1,k = v n,2n -v n,0 ,
and then

3(3n + 2)(3n + 1)(a n -u n,2n ) + (n + 1) 2 (a n+1 -u n+1,2n+2 -u n+1,2n+1 -u n+1,2n ) = n 3 (8n 5 + 52n 4 + 146n 3 + 223n 2 + 185n + 58).
It turns out that 3(3n + 2)(3n + 1)u n,2n + (n + 1) 2 (u n+1,2n+2 + u n+1,2n+1 + u n+1,2n ) evaluates exactly to the right-hand side of the above identity, and this leads to Dixon's identity.

In this example, spurious singularities clearly appear in the range of summation. Thus, deriving an identity such as Dixon's from a telescopic identity such as ( 5) is not straightforward and involves the certificate. A few works address this issue for single sums [START_REF] Abramov | Gosper's algorithm, accurate summation, and the discrete Newton-Leibniz formula[END_REF][START_REF] Abramov | On the summation of P -recursive sequences[END_REF]), but none for the case of multiple sums: existing algorithms [START_REF] Wegschaider | Computer Generated Proofs of Binomial Multi-Sum Identities[END_REF][START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF][START_REF] Garoufalidis | A new algorithm for the recursion of hypergeometric multisums with improved universal denominator[END_REF] only give the telescopic identity without performing the summation. A recent attempt by [START_REF] Chyzak | A Computer-Algebra-Based Formal Proof of the Irrationality of ζ(3)[END_REF] to check the recurrence satisfied by Apéry's sequence in the proof assistant Coq has shown how difficult it is to formalize this summation step. Note that because of this issue, even the existence of a linear recurrence for such sums can hardly be inferred from the fact that the algorithm of creative telescoping always terminates with success.

This issue is rooted in the method of creative telescoping by the fact that sequences are represented through the linear recurrence relations that they satisfy. Unfortunately, this representation is not very faithful when the leading terms of the relations vanish for some values of the indices. The method of generating functions avoids this issue. For example, the binomial coefficient n k is represented unambiguously as the coefficient of x k in (1 + x) n (to be understood as a power series when n < 0), rather than as a solution to the recurrence relations (n-k

) n k = n n-1 k and k n k = n n-1 k-1 .
Related work. The method of generating functions is classical and has been largely studied, in particular for the approach described here by [START_REF] Egorychev | Integral representation and the computation of combinatorial sums[END_REF], see also [START_REF] Egorychev | Integral representation and algorithms for closed form summation[END_REF]). Egorychev's method is a general approach to summation, but not quite an algorithm. In this work, we make it completely effective and practical for the class of binomial sums.

The special case when the generating functions are differentially finite (D-finite) has been studied by Lipshitz (1989). From the effectivity point of view, the starting point is his proof that diagonals of D-finite power series are D-finite [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]. The argument, based on linear algebra, is constructive but does not translate into an efficient algorithm because of the large dimensions involved. This led Wilf and Zeilberger (1992, p. 596) to comment that "This approach, while it is explicit in principle, in fact yields an infeasible algorithm." Still, using this construction of diagonals, many closure properties of the sequences under consideration (called P-recursive) can be proved (and, in principle, computed). Then, the representation of a convergent definite sum amounts to evaluating a generating series at 1 and this proves the existence of linear recurrences for the definite sums of all P-recursive sequences. Abramov and Petkovšek (2002) showed that in particular the so-called proper hypergeometric sequences are P-recursive in the sense of Lipshitz. The proof is also constructive, relying on Lipshitz's construction of diagonals to perform products of sequences.

While we are close to Lipshitz's approach, three enhancements make the method of generating functions presented here efficient: we use more efficient algorithms for computing multiple integrals and diagonals that have appeared in the last twenty years [START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF][START_REF] Koutschan | A fast approach to creative telescoping[END_REF]Bostan et al. 2013a;Lairez 2016); we restrict ourselves to binomial sums, which makes it possible to manipulate the generating functions through rational integral representations (see §2.2 and §2.3); and a third decisive improvement comes with the geometric reduction procedure for simplifying integral representations (see §5).

Creative telescoping is another summation algorithm developed by Zeilberger (1991b) and proved to work for all proper hypergeometric sequences [START_REF] Wilf | An algorithmic proof theory for hypergeometric (ordinary and "q") multisum/integral identities[END_REF]. This method has the advantage of being applicable and often efficient in practice. However, as already mentioned, it relies on certificates whose size grows fast with the number of variables (Bostan et al. 2013a) and, more importantly, whose summation is not straightforward, making the complete automation of the method problematic. For proper hypergeometric sums, a different effective approach developed by [START_REF] Takayama | An algorithm for finding recurrence relations of binomial sums and its complexity[END_REF] does not suffer from the certificate problem. It consists in expressing the sum as the evaluation of a hypergeometric series and reducing its shifts with respect to a non-commutative Gröbner basis of the contiguity relations of the series, reducing the question to linear algebra in the finite-dimensional quotient.

The class of sums we consider is a subclass of the sums of proper hypergeometric sequences. We give an algorithm that avoids the computation of certificates in that case, and relies on an efficient method to deal with the integral representations of sums. The same approach has been recently used by Bostan et al. (2013b) on various examples, though in a less systematic manner. Examples in §7 give an idea of the extent of the class we are dealing with. It is a subclass of the balanced multisums, shown by [START_REF] Garoufalidis | G-functions and multisum versus holonomic sequences[END_REF] to possess nice asymptotic properties. More recently, a smaller family of binomial multisums was studied by [START_REF] Garrabrant | Counting with irrational tiles[END_REF]: they are further constrained to be diagonals of N-rational power series.

1. The algebra of binomial sums 1.1. Basic objects. For all n, k ∈ Z, the binomial coefficient n k is considered in this work as defined to be the coefficient of x k in the formal power series (1 + x) n . In other words, Let K be a field of characteristic zero, and let d 1. We denote by S d the Kalgebra of sequences Z d → K, where addition and multiplication are performed component-wise. Elements of Z d are denoted using underlined lower case letters, such as n. The algebra S d may be embedded in the algebra of all functions Z N → K by sending a sequence u : Z d → K to the function ũ defined by ũ(n 1 , n 2 , . . . ) = u(n 1 , . . . , n d ).

n k = n(n -1)(n -2) • • • (n -k + 1) k! for k 0 and n k = 0 for k < 0.
u k def =        b k=a u k if a b, 0 if a = b + 1, - a-1 k=b+1 u k if a > b + 1,
Let S be the union of the S d 's in the set of all functions Z N → K. For u ∈ S and n ∈ Z d , the notation u n represents u n,0,0,... . These conventions let us restrict or extend the number of indices as needed without keeping track of it.

Definition 1.1. The algebra of binomial sums over the field K, denoted B, is the smallest subalgebra of S such that:

(a) The Kronecker delta sequence n ∈ Z → δ n , defined by δ 0 = 1 and By combining the rules (d) and (e) of the definition, we also obtain the closure of B under sums whose bounds depend linearly on the parameter: if u ∈ B and if λ and µ are affine maps :

δ n = 0 if n = 0, is in B. (b) The geometric sequences n ∈ Z → C n , for all C ∈ K \ {0}, are in B. (c) The binomial sequence (n, k) → n k (an element of S 2 ) is in B. (d) If λ : Z d → Z e is an affine map and if u ∈ B, then n ∈ Z d → u λ( n) is in B. (e) If u ∈ B, then the following directed indefinite sum is in B: ( n, m) ∈ Z d × Z →
Z d → Z, then the sequence (6) n ∈ Z d → µ( n) k=λ( n) u n,k
is a binomial sum. See also Figure 1 for an example of a classical binomial sum.

1.2. Characterization of binomial sums. A few simple criteria make it possible to prove that a given sequence is not a binomial sum. For example:

• The sequence (n!) n 0 is not a binomial sum. Indeed, the set of sequences that grow at most exponentially is closed under the rules that define binomial sums. Since n k 2 |n|+|k| , every binomial sum grows at most exponentially; but this is not the case for the sequence (n!) n 0 . • The sequence of all prime integers is not a binomial sum because it does not satisfy any nonzero linear recurrence relation with polynomial coefficients [START_REF] Flajolet | On the Non-Holonomic Character of Logarithms, Powers, and the nth Prime Function[END_REF], whereas every binomial sum does, see Corollary 3.6. • The sequence (1/n) n 1 is not a binomial sum. To prove this, we can easily reduce to the case where K is a number field and then study the denominators that may appear in the elements of a binomial sum. One may introduce new prime divisors in the denominators only by multiplying with a scalar or with rule (b), so that the denominators of the elements of a given binomial sum contain only finitely many prime divisors. This is clearly not the case for the sequence (1/n) n 1 .

n k=0 n k n + k k k j=0 k j 3 H n δ n (e) n k=0 n k n + k k k j=0 k j 3 m k=0 n k n + k k k j=0 k j 3 n k n + k k k j=0 k j 3 n k n + k k n k (d) n → n + k k j=0 k j 3 m j=0 k j 3 k j 3 k j k j k j (e) (d) m → k (e) (d) m → n
By the same argument, the first sum of Eq. ( 1) is not a binomial sum. Indeed, by creative telescoping, it can be shown to equal (2n + 1)4 n+1 / 2n+2 n+1 + 1/3 and thus all prime numbers appear as denominators.

• The sequence (u n ) n 0 defined by u 0 = 0, u 1 = 1 and by the recurrence (2n + 1)u n+2 -(7n + 11)u n+1 + (2n + 1)u n = 0 is not a binomial sum. This follows from the asymptotic estimate

u n ∼ C • (4/(7 - √ 33)) n • n √ 75/44
, with C ≈ 0.56, and the fact that 75/44 is not a rational number (Garoufalidis 2009, Theorem 5).

These criteria are, in substance, the only ones that we know to prove that a given sequence is not a binomial sequence. Conjecturally, they characterize univariate binomial sums. Indeed, we will see that the equivalence between univariate binomial sums and diagonals of rational functions (Theorem 3.5) leads, among many interesting corollaries, to the following reformulation of a conjecture due to Christol (1990, Conjecture 4): "any sequence (u n ) n 0 of integers that grows at most exponentially and that is solution of a linear recurrence equation with polynomial coefficients is a binomial sum."

Generating functions

To go back and forth between sequences and power series, one can use convergent power series and Cauchy's integrals to extract coefficients, as shown in the introduction with Dixon's identity, or one can use formal power series. Doing so, the theory keeps close to the actual algorithms and we avoid the tedious tracking of convergence radii. However, this requires the introduction of a field of multivariate formal power series that makes it possible, by embedding the rational functions into it, to define what the coefficient of a given monomial is in the power series expansion of an arbitrary multivariate rational function. We choose here to use the field of iterated Laurent series. It is an instance of the classical field of Hahn series when the value group is Z n with the lexicographic order. We refer to [START_REF] Xin | The ring of Malcev-Neumann series and the residue theorem[END_REF] for a complete treatment of this field and we simply gather here the main definitions and results.

2.1. Iterated Laurent series. For a field A, let A((t)) be the field of univariate formal Laurent power series with coefficients in A. For d 0, let L d be the field of iterated formal Laurent power series K((

z d ))((z d-1 )) • • • ((z 1 )). It naturally contains the field of rational functions in z 1 , . . . , z d . For n = (n 1 , . . . , n d ) ∈ Z d , let zn denote the monomial z n1 1 • • • z n d d , and for f ∈ L d , let [ zn ]f denote the coefficient of zn in f , that is the coefficient of z n d d in the coefficient of z n d-1 d-1 in [. . . ] in the coefficient of z n1 1 of f . An element of f ∈ L d is entirely characterized by its coefficient function n ∈ Z d → [ zn ]f . On occasion, we will write [z n 1 ]f , this means [z n 1 z 0 2 • • • z 0 d ]f , e.g., [1]f means [z 0 1 • • • z 0 d ]f ; more generally we write [m]f
, where m is a monomial. In any case, the bracket notation always yields an element of K.

Let ≺ denote the lexicographic ordering on Z d . For n, m ∈ Z d we write zn ≺ z m if m ≺ n (mind the inversion: a monomial is larger when its exponent is smaller). In particular

z 1 ≺ • • • ≺ z d ≺ 1.
With an analytic point of view, we work in an infinitesimal region where z d is infinitesimally small and where z i is infinitesimally small compared to z i+1 . The relation zn ≺ Xin 2004, Prop. 2-1.2) that a function ϕ :

z m means that | zn | is smaller than | z m| in this region. For f ∈ L d , the support of f , denoted supp(f ), is the set of all n ∈ Z d such that [ zn ]f is not zero. It is well-known (e.g.
Z d → K is the coefficient function of an element of L d if and only if the support of ϕ is well-ordered for the order ≺ (that is to say every subset of the support of ϕ has a least element). The valuation of a non zero

f ∈ L d , denoted v(f ), is the smallest element of supp(f ) ⊂ Z d for the ordering ≺. Since supp(f ) is well-ordered, v(f ) does exist.
The leading monomial of f , denoted lm(f ), is zv(f) ; it is the largest monomial that appears in f .

For 1 i d, the partial derivative ∂ i = ∂/∂z i with respect to the variable z i , defined for rational functions, extends to a derivation in

L d such that [ zn ]∂ i f = (n i + 1)[ zn ](f /z i ) for any f ∈ L d .
Let w 1 , . . . , w d be monomials in the variables z 1 , . . . , z e . When f is a rational function, the substitution f (w 1 , . . . , w d ) is defined in a simple way. For elements of L d , it is slightly more technical. Let ϕ : Z d → Z e be the additive map defined by ϕ( n) = v( wn ) (recall that v denotes the valuation). Conversely, this map entirely determines the monomials w 1 , . . . , w d . When ϕ is strictly increasing (and thus injective) with respect to the lexicographic ordering, we define f ϕ as the unique element of L e such that

[ zn ]f ϕ = [ zϕ -1 ( n) ]f if n ∈ ϕ(Z d ), 0 otherwise. The map f ∈ L d → f ϕ ∈ L e is a field morphism.
In particular, for a monomial zn , we check that ( zn

) ϕ = zϕ( n) . When f is a rational function, f ϕ coincides with the usual substitution f (w 1 , . . . , w d ).
Another important construction is the sum of geometric sequences. Let f ∈ L d be a Laurent power series with lm(f ) ≺ 1. The set of all n ∈ Z d such that there is at least one k ∈ N such that [ zn ]f k = 0 is well-ordered (Neumann 1949, Theorem 3.4). Moreover, for any n ∈ Z d , the coefficient [ zn ]f k vanishes for all but finitely many k ∈ N (Neumann 1949, Theorem 3.5). The following result is easily deduced.

Lemma 2.1. Let f ∈ L d and let

zn be a monomial. If lm(f ) ≺ 1, then [ zn ]f k = 0 for all but finitely many k ∈ N and moreover

[ zn ] 1 1 -f = k 0 [ zn ]f k .
In what follows, there will be variables z 1 , . . . , z d , denoted z 1 d (and sometimes under different names) and we will denote z 1 ≺ • • • ≺ z d the fact that we consider the field L d with this ordering to define coefficients, residues, etc. The variables are always ordered by increasing index, and

t 1 d ≺ z 1 e denotes t 1 ≺ • • • ≺ t d ≺ z 1 ≺ • • • ≺ z e . An element of L d ∩ K(z 1 d ) is called a rational Laurent series, and an element of K z 1 d ∩ K(z 1 d ) is called a rational power series.
Example 1. Since L d is a field containing all the rational functions in the variables z 1 , . . . , z d , one may define the coefficient of a monomial in a rational function. However, it strongly depends on the ordering of the variables. For example, in

L 2 = K((z 2 ))((z 1 )), the coefficient of 1 in z 2 /(z 1 + z 2 ) is 1 because z 2 z 1 + z 2 = 1 - 1 z 2 z 1 + O(z 2 1 ), whereas the coefficient of 1 in z 1 /(z 1 + z 2 ) is 0 because z 1 z 1 + z 2 = 1 z 2 z 1 + O(z 2 1 ).
2.2. Binomial sums and coefficients of rational functions. Binomial sums can be obtained as certain extractions of coefficients of rational functions. We will make use of sequences of the form u :

n ∈ Z d → [1] (R 0 R n1 1 • • • R n d d )
, where R 0 d are rational functions of ordered variables z 1 r . They generalize several notions. For example if R 0 ∈ K(z 1 , . . . , z r ) and

R i = 1/z i , then u is simply the coefficient function of R 0 ; and if d = 1, R 0 ∈ K(z 1 , . . . , z r ) and R 1 = 1/(z 1 • • • z r ), then u is the sequence of the diagonal coefficients of R 0 .

Theorem 2.2. Every binomial sum is a linear combination of finitely many sequences of the form

n ∈ Z d → [1] (R 0 R n1 1 • • • R n d d )
, where R 0 d are rational functions of ordered variables z 1 r , for some r ∈ N.

Proof. It is clear that δ n = [1]z n , that C n = [1]C n and that n k = [1](1 + z) n z -k , for all n, k ∈ Z.
Thus, it is enough to prove that the vector space generated by the sequences of the form

[1] (R 0 R n1 1 • • • R n d d
) is a subalgebra of S which is closed by the rules defining binomial sums, see §1.1.

First, it is closed under product: if R 0 d and R 0 d are rational functions in the variables z 1 r and z 1 r respectively, then

[1] R 0 d i=1 R ni i [1] R 0 d i=1 R i ni = [1] R 0 R 0 d i=1 (R i R i ) ni ,
with the ordering z 1 r ≺ z 1 r , for example. Then, to prove the closure under change of variables, it is enough to reorder the factors:

[1] R 0 d i=1 R e j=1 aij nj +bi i = [1]   R 0 d i=1 R bi i e j=1 d i=1 R aij i nj   .
Only the closure under partial sum remains. Let u be a sequence of the form

( n, k) ∈ Z d × Z → [1] T k R 0 d i=1 R ni i , where T and R 0 d are rational functions. If T = 1, then m k=0 u n,k = [1] (m + 1)R 0 d i=1 R ni i = [1] (1 + v)R 0 v (1 + v) m d i=1 R ni i , where v is a new variable, because [v](1 + v) m+1 = m + 1. If T = 1, then m k=0 u n,k = [1] R 0 1 -T d i=1 R ni i -[1] R 0 T 1 -T T m d i=1 R ni i ,
which concludes the proof.

The previous proof is algorithmic and Algorithm 1 p. 14 proposes a variant which is more suitable for actual computations-see §2.4. It is a straightforward rewriting procedure and often uses more terms and more variables than necessary. The geometric reduction procedure, see §5, handles this issue.

Example 2. Following step by step the proof of Theorem 2.2, we obtain that

n k=0 n k n + k k = [1] 1 + z 2 1 + z 1 -z 1 z 2 (1 + z 1 )(1 + z 2 ) 2 z 1 z 2 n -[1] z 1 z 2 1 + z 1 -z 1 z 2 ((1 + z 1 )(1 -z 2 )) n .
We notice that the second term is always zero.

Corollary 2.3. For any binomial sum u :

Z d → K, there exist r ∈ N and a rational function R(t 1 d , z 1 r ), with t 1 d ≺ z 1 r , such that for any n ∈ Z d , [ tn z0 ]R = u n if n 1 , . . . , n d 0, 0 otherwise.
(See Proposition 3.10 below for a converse.)

Proof. It is enough to prove the claim for a generating set of the vector space of all binomial sums. In accordance with Theorem 2.2, let u :

Z d → K be a sequence of the form n ∈ Z d → [1] (S 0 S n1 1 • • • S n d d )
, where S 0 d are rational functions of ordered variables z 1 r . Let R(t 1 d , z 1 r ) be the rational function

R = S 0 d i=1 1 1 -t i S i . Lemma 2.1 implies that for any n ∈ Z d [ tn z0 ]R = k1,...,k d 0 [ tn z0 ] S 0 • (t 1 S 1 ) k1 • • • (t d S d ) k d .
Since the variables t i do not appear in the S i 's, the coefficient in the sum is not zero

only if n = k. In particular, if n is not in N d , then [ tn z0 ]R = 0. And if n ∈ N d , then [ tn z0 ]R = [ tn z0 ] (S 0 • (t 1 S 1 ) n1 • • • (t d S d ) n d ) = [1] (S 0 S n1 1 • • • S n d d ) = u n,
which concludes the proof.

2.3.

Residues. The notion of residue makes it possible to represent the full generating function of a binomial sum. It is a key step toward their computation.

For f ∈ L d and 1 i d, the formal residue of f with respect to z i , denoted res zi f , is the unique element of L d such that

[ zn ](res zi f ) = [ zn ](z i f ) if n i = 0, 0 otherwise.
This is somehow the coefficient of 1/z i in f , considered as a power series in z i (though f is not a Laurent series in z i since it may contain infinitely many negative powers of z i ). When f is a rational function, care should be taken not to confuse the formal residue with the classical residue at z i = 0, which is the coefficient of 1/z i in the partial fraction decomposition of f with respect to z i . However, the former can be expressed in terms of classical residues, see §5, and like the classical residues, it vanishes on derivatives:

Lemma 2.4. res zi ∂ i f = 0 for all f ∈ L d .
If α is a set of variables {z i1 , . . . , z ir }, let res α f denote the iterated residue res zi 1 • • • res zi r f . It is easily checked that this definition does not depend on the order in which the variables appear. This implies, together with Lemma 2.4, the following lemma:

Lemma 2.5. res α v∈α ∂ v f v = 0, for any family (f v ) v∈α of elements of L d .
The following lemma will also be useful: Proof.

res α∪β f g = res α res β f g = res α f res β g = res α f res β g .
The order on the variables matters. For example, let F (x, y) be a rational function, with x ≺ y. The residue res x F is a rational function of y. Indeed, if -n is the exponent of x in lm(F ), which we assume to be negative, then

res x F = 1 (n -1)! ∂ n-1 ∂x n-1 x n F x=0 .
In contrast, the residue with respect to y (or any other variable which is not the smallest) is not, in general, a rational function. It is an important point because we will represent generating series of binomial sums-which need be neither rational nor algebraic-as residues of rational functions.

Example 3. Let F = 1 xy(y 2 +y-x) . Assume that y ≺ x, that is to say, we work in the field K((x))((y)). We compute that res

y F = -1 x 2 because F = - 1 x 2 y + (y + 1) x 2 (y 2 + y -x)
and the second term does not contain any negative power of y.

On the other hand, if we assume that x ≺ y, then res y F is not a rational function anymore. Using Proposition 5.2, we can compute that res

y F = - 1 x 2 + 2 x + 4x 2 -x(1 + 4x) 1/2 = - 1 x + 3 -10x + 35x 2 + O(x 3 ).
Residues of rational functions can be used to represent any binomial sum; it is the main point of the method and it is the last corollary of Theorem 2.2. Following Egorychev we call them integral representations, or formal integral representations, to emphasize the use of formal power series and residues rather than of analytic objects.

Corollary 2.7 (Integral representations). For any binomial sum

u : Z d → K, there exist r ∈ N and a rational function R(t 1 d , z 1 r ), with t 1 d ≺ z 1 r , such that n∈N d u nt n = res z1 r R.
In other words, the generating function of the restriction to N d of a binomial sum is a residue of a rational function.

Proof. By Corollary 2.3, there exist r ∈ N and a rational function R(t

1 d , z 1 r ) such that u n = [ tn z0 ] R for all n ∈ N d . Let R be R/(z 1 • • • z r ). Then n∈N d u nt n = n∈N d [ tn z0 ] R tn = res z1 r R.
Algorithm 1. Constant term representation of a binomial sum Input: A binomial sum u : Z d → K given as an abstract syntax tree Output: P (n 1 d ; z 1 r ) a linear combination of expressions of the form nᾱR0R

n 1 1 • • • R n d d
where ᾱ ∈ N d and R 0 d are rational functions of z 1 r . Specification:

u n = [1]P (n 1 d ; z 1 r ) for any n ∈ Z d . function SumToCT(u) if u n = δ n1 then return z n1 1 else if u n = a n1 for some a ∈ K then return a n1 else if u n = n1 n2 then return (1 + z 1 ) n1 /z n2 1 else if u n = v n + w n then return SumToCT(v) + SumToCT(w) else if u n = v nw n then P (n 1 d ; z 1 r ) ← SumToCT(v) Q(n 1 e ; z 1 s ) ← SumToCT(w) return P (n 1 d ; z 1 r )Q(n 1 e ; z r+1 r+s ) else if u n = v λ( n) for some affine map λ : Z d → Z e then P (n 1 d ; z 1 r ) ← SumToCT(v) return P (λ(n 1 d ); z 1 r ) else if u n1,n2,... = n1 k=0 v k,n2,... then P (n 1 d ; z 1 r ) ← SumToCT(v) Compute Q(n 1 d ; z 1 r ) s.t. Q(n 1 + 1, n 2 d ; z 1 r ) -Q(n 1 d ; z 1 r ) = P See Lemma 2.8. return Q(n 1 + 1, n 2 d ; z 1 r ) -Q(0, n 2 d ; z 1 r )
In §3, we prove an equivalence between univariate binomial sums and diagonals of rational functions that are a special kind of residues.

2.4. Algorithms. The proofs of Theorem 2.2 and its corollaries are constructive, but in order to implement them, it is useful to consider not only sequences of the form [1](R 0 Rn ) but also sequences of the form [1]( nᾱ R 0 Rn ), for some rational functions R 0 d and ᾱ ∈ N d . They bring two benefits. First, polynomial factors often appear in binomial sums and it is convenient to be able to represent them without adding new variables. Second, we can always perform sums without adding new variables, contrary to what is done in the case T = 1 of the proof of Theorem 2.2. Lemma 2.8. For any A = 0 in some field k, and any α ∈ N, there exists a polynomial P ∈ k[n] of degree at most α + 1 such that for all n ∈ Z,

n α A n = P (n + 1)A n+1 -P (n)A n .
Proof. It is a linear system of α + 2 equations, one for each monomial 1, n, . . . , n α+1 , in the α + 2 coefficients of P . If A = 1, the homogeneous equation P (n + 1)A = P (n) has no solutions, so the system is invertible and has a solution. If A = 1, then the equation P (n + 1)A = P (n) has a one-dimensional space of solutions but the equation corresponding to the monomial n α+1 reduces to 0 = 0, so the system again has a solution.

Algorithm 1 implements Theorem 2.2 in this generalized setting. The input data, a binomial sum, is given as an expression considered as an abstract syntax tree, as depicted in Figure 1. The implementation of Corollaries 2.3 and 2.7 must also be adjusted to handle the monomials in n.

Algorithm 2. Integral representation of a binomial sum

Input: A binomial sum u : Z d → K given as an abstract syntax tree Output: A rational function R(t 1 d , z 1 r ) Specification:

n∈N d u ntn = resz 1 r R, where t 1 d ≺ z 1 r function SumToRes(u) m k=1 nᾱ k R k,0 R n1 k,1 • • • R n d k,d ← SumToCT(u) return 1 z 1 . . . z r m k=1 R k,0 F α1 (t 1 R k,1 ) • • • F α d (t d R k,d )
where

F 0 (z) = 1 1-z and F α+1 (z) = zF α (z)
To this effect, for α ∈ N, let

F α (z) def = n 0 n α z n = z d dz α • 1 1 -z . Now let us consider a sequence u : n ∈ Z d → [1] ( nᾱ S 0 S n1 1 • • • S n d d )
, where S 0 d are rational functions of ordered variables z 1 r and ᾱ

∈ N d Let R = S 0 d i=1 1 1 -t i S i and R = S 0 d i=1 F αi (t i S i ),
where t 1 d ≺ z 1 r . By definition of the F α 's, we check that 2.5. Analytic integral representations. When K is a subfield of C, then formal residues can be written as integrals. Proposition 2.9. Let R(t 1 d , z 1 e ) be a rational function whose denominator does not vanish when t 1 = • • • = t d = 0. There exist positive real numbers s 1 d and r 1 e such that on the set

R = t 1 ∂ ∂t 1 α1 • • • t d ∂ ∂t d α d • R, so that [ tn z0 ]R = nᾱ [ tn z0 ] R, for n ∈ Z d ,
(t 1 d ) ∈ C d ∀i, |t i | s i , the power series res z1 e R ∈ C t 1 d converges and res z1 e R = 1 (2πi) e γ R(t 1 d , z 1 e )dz 1 e , where γ = {z ∈ C e | ∀1 i e, |z i | = r i }.
Proof. When R is a Laurent monomial, the equality follows from Cauchy's integral formula. By linearity, it still holds when R is a Laurent polynomial.

In the general case, let R be written as a/f , where a and f are polynomials. We may assume that the leading coefficient of f is 1 and so f decomposes as lm(f )(1 -g) where g is a Laurent polynomial with monomials ≺ 1. The hypothesis that f does not vanish when t 1 = • • • = t d = 0 implies that lm(f ) depends only on the variables z 1 e and that g contains no negative power of the variables t 1 d . This and the fact that all monomials of g are ≺ 1 imply that there exist positive real numbers s 1 d and r 1 e such that |g(t

1 d , z 1 e )| 1 2 if |t i | s i and |z i | = r i .
For example, we can take s i = exp(-exp(N/i)) and r i = exp(-exp(N/(d + i))), for some large enough N , because exp(-exp(N/i)) p = o (exp(-exp(N/j)) q ) , N → ∞, for any p, q > 0 and i < j. On the one hand res

z1 e R = k 0 res z1 e ag k lm(f )
, by Lemma 2.1, and on the other hand, if

|t i | s i , for 1 i d then γ R(t 1 d , z 1 e )dz 1 e = k 0 γ ag k lm(f ) dz 1 e .
where γ = {z ∈ C e | ∀1 i e, |z i | = r i }, because the sum k 0 g k converges uniformly on γ, since |g| 1 2 . And the lemma follows from the case where R is a Laurent polynomial.

Diagonals

Let R(z 1 d ) = n∈N d a nz n be a rational power series in K(z 1 , . . . , z d ). The diagonal of R is the univariate power series diag R def = n 0 a n,...,n t n .
Diagonals have be introduced to study properties of the Hadamard product of power series [START_REF] Cameron | Analytic continuation of diagonals and Hadamard compositions of multiple power series[END_REF][START_REF] Furstenberg | Algebraic Functions over Finite Fields[END_REF]. They also appear in the theory of G-functions (Christol 1988). They can be written as residues: with t ≺ z 2 d , it is easy to check that

(7) diag R = res z2,...,z d 1 z 2 • • • z d R t z 2 • • • z d , z 2 , . . . , z d .
Despite their simplistic appearance, diagonals have very strong properties, the first of which is differential finiteness:

Theorem 3.1 [START_REF] Christol | Diagonales de fractions rationnelles et équations de Picard-Fuchs[END_REF][START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]. Let R(z 1 d ) be a rational power series in K(z 1 , . . . , z d ). There exist polynomials p 0 r ∈ K[t], not all zero, such that p r f

(r) + • • • + p 1 f + p 0 f = 0, where f = diag R.
We recall that a power series f ∈ K t is called algebraic if there exists a nonzero polynomial P ∈ K[x, y] such that P (t, f ) = 0. Theorem 3.2 [START_REF] Furstenberg | Algebraic Functions over Finite Fields[END_REF]. A power series f ∈ K t is algebraic if and only if f is the diagonal of a bivariate rational power series.

Diagonals of rational power series in more than two variables need not be algebraic, as shown by

n 0 (3n)! n! 3 t n = diag 1 1 -z 1 -z 2 -z 3 .
However, the situation is simpler modulo any prime number p. The following result is stated by Furstenberg (1967, Theorem 1) over a field of finite characteristic; since reduction modulo p and diagonal extraction commute, we obtain the following statement:

Theorem 3.3 [START_REF] Furstenberg | Algebraic Functions over Finite Fields[END_REF]. Let f ∈ Q t be the diagonal of a rational power series with rational coefficients. Finitely many primes may divide the denominator of a coefficient of f . For all prime p except those, the power series f (mod p) ∈ F p t is algebraic.

Example 4. It is easy to check that the series

f = n 0 (3n)! n! 3 t n satisfies f ≡ (1 + t) -1 4 mod 5, f ≡ 1 + 6t + 6t 2 -1 6 mod 7, f ≡ 1 + 6t + 2t 2 + 8t 3 -1 10 mod 11, etc.
The characterization of diagonals of rational power series remains largely an open problem, despite very recent attempts (Christol 2015). A natural measure of the complexity of a power series f ∈ Q t is the least integer n, if any, such that f is the diagonal of a rational power series in n variables. Let N (f ) be this number, or

N (f ) = ∞ if there is no such n. 1 It is clear that N (f ) = 1 if and only if f is rational. According to Theorem 3.2, N (f ) = 2 if
and only if f is algebraic and not rational. It is easy to find power series f with N (f ) = 3, for example N n (3n)! n! 3 t n = 3 because it is the diagonal of a trivariate rational power series but it is not algebraic. However, we do not know of any power series f such that N (f ) > 3.

Conjecture 3.4 (Christol 1990). Let f ∈ Z t be a power series with integer coefficients, positive radius of convergence and such that p r f (r)

+ • • • + p 1 f + p 0 f = 0 for some polynomials p 0 r ∈ Q[t]
, not all zero. Then f is the diagonal of a rational power series.

In this section, we prove the following equivalence: Theorem 3.5. A sequence u : N → K is a binomial sum if and only if the generating function n 0 u n t n is the diagonal of a rational power series.

In §3.1, we prove that the generating function of a binomial sum is a diagonal and in §3.3, we prove the converse. When writing that a sequence u : N → K is a binomial sum, we mean that there exists a binomial sum v : Z → K whose support in contained in N and which coincides with u on N. Theorem 3.5 can be stated equivalently without restriction on the support: a sequence u : Z → K is a binomial sum if and only if the generating functions n 0 u n t n and n 0 u -n t n are diagonals of rational power series.

Note that Garrabrant and Pak (2014, Theorem 1.3) proved a similar, although essentially different, result: the subclass of binomial multisums they consider corresponds to the subclass of diagonals of N-rational power series.

Theorem 3.5 and the theory of diagonals of rational functions imply right away interesting corollaries.

Corollary 3.6. If u : Z → K is a binomial sum, then there exist polynomials p 0 r in K[t], not all zero, such that p r (n

)u n+r + • • • + p 1 (n)u n+1 + p 0 (n)u n = 0 for all n ∈ Z.
As mentioned in the introduction, this is a special case of a more general result for proper hypergeometric sums that can alternately be obtained as a consequence of the results of Lipshitz (1989) and Abramov and Petkovšek (2002).

Corollary 3.7 [START_REF] Flajolet | Coefficients of algebraic series[END_REF]. If the generating function n u n t n of a sequence u : N → K is algebraic, then u is a binomial sum.

Corollary 3.8. Let u : N → Q be a binomial sum. Finitely many primes may divide the denominators of values of u. For all primes p except those, the generating function of a binomial sum is algebraic modulo p.

Moreover, Christol's conjecture is equivalent to the following: Conjecture 3.9. If an integer sequence u : N → Z grows at most exponentially and satisfies a recurrence p r (n)u n+r + • • • + p 0 (n)u n = 0, for some polynomials p 0 r with integer coefficients, not all zero, then u is a binomial sum.

The proof of Theorem 3.5 also gives information on binomial sums depending on several indices, in the form of a converse of Corollary 2.3.

n = [ tn z0 ]R, for n ∈ Z d . We assume that u n = 0 if n / ∈ N d .
Using the same technique as in §3.1, we show that there exist a rational power series S(z 1 d+r ) and monomials w 1 d in the variables z 1 d+r such that u n = [ wn ]S. Then, with the same technique as in §3.3, we write u n as a binomial sum.

In other words, binomial sums are exactly the constant terms of rational power series, where the largest variables, for the order ≺, are eliminated.

3.1. Binomial sums as diagonals. Corollary 2.7 and Equation ( 7) provide an expression of the generating function of a binomial sum (of one free variable) as the diagonal of a rational Laurent series, but more is needed to obtain it as the diagonal of a rational power series and obtain the "only if" part of Theorem 3.5.

Let u : N → K be a binomial sum. In this section, we aim at constructing a rational power series S such that n 0 u n t n = diag S. By Corollary 2.3, there exists a rational function R(z

0 r ) = a f such that u n = [z n 0 z 0 1 • • • z 0 r ] R for all n ∈ Z. Recall the notation f ϕ , for f ∈ L r+1 and ϕ an increasing endomorphism of Z r+1 , introduced in §2.1. For example, if f = z 1 + z 2 ∈ L 2 and ϕ(n 1 , n 2 ) = (n 1 , n 1 + n 2 ) then f ϕ = z 1 z 2 + z 2 = z 2 (1 + z 1 ). Lemma 3.11. For any polynomial f ∈ K[z 0 r ] there exists an increasing endomor- phism ϕ of Z r+1 such that f ϕ = C z m(1 + g), for some m ∈ N r+1 , C ∈ K \ {0} and g ∈ K[z 0 r ] with g(0, . . . , 0) = 0.
Proof. Let zā and zb be monomials of f such that zā ≺ zb . Let i be the smallest integer such that a i = b i . By definition a i > b i . For k ∈ N, let ϕ k : Z r+1 → Z r+1 be defined by

ϕ k : (n 0 , . . . , n r ) ∈ Z r+1 → (n 0 , . . . , n i , n i+1 + kn i , . . . , n r + kn i ) ∈ Z r+1 .

It is strictly increasing and if

k is large enough then ϕ k ( ā) ϕ k ( b) componentwise, that is ( zb ) ϕ k divides ( zā ) ϕ k .
We may apply repeatedly this argument to construct an increasing endomorphism ϕ of Z r+1 such that the leading monomial of f ϕ divides all the monomials of f ϕ , which proves the Lemma.

Let ϕ be the endomorphism given by the lemma above applied to the denominator of R. For 0 0 r, let

w i = z ϕ i . Then R(w 0 r ) = Rϕ = a ϕ C z m(1 + g) , because
• ϕ is a field morphism, as explained in §2.1. And by definition of R, we have u n = [w n 0 ] R(w 0 r ) for all n ∈ Z. Let R be the rational power series a ϕ C(1+g) , so that u n = [w n 0 ](R/ z m). We now prove that we can reduce to the case where m = 0. If m = 0, let i be the smallest integer such that m i = 0. The specialization R| zi=0 is a rational power series and R -R |zi=0 = z i T for some rational power series T . For all n 0, the coefficient of

w n 0 in R| zi=0 / z m is zero because the exponent of z i in w n 0 is nonnegative while the exponent of z i in every monomial in R| zi=0 / z m is -m i < 0. Thus u n = [w n 0 ] T z m/zi
, and we can replace R by T and subtract 1 to the first nonzero coordinate of m, which makes m decrease for the lexicographic ordering. Iterating this procedure leads to m = 0 and thus u n = [w n 0 ]T for some rational power series T .

Let us write w 0 as z a0 0 • • • z ar r , with a 0 r ∈ N r+1 . If all the a i 's were equal to 1, then n u n t n would be the diagonal of T . First, we reduce to the case where all the a i 's are positive. If some a i is zero, then

[w n 0 ]T = [z a0 0 • • • z ai-1 i-1 z ai+1 i+1 • • • z ar r ]
T | zi=0 and we can simply remove the variable z i .

Second, we reduce further to the case where all the a i 's are 1. Let us consider the following rational power series:

U = 1 a 0 • • • a r ε a 0 0 =1 • • • ε ar r =1
T (ε 0 z 0 , . . . , ε r z r ),

where the ε i ranges over the a i -th roots of unity. By construction, if m is a monomial in the z ai i , then [m]U = [m]T . In particular u n = [w n 0 ]U . We may consider T and U as elements of the extension of the field K(z a0 0 , . . . , z ar r ) by the roots of the polynomials X ai -z i , for 0 i r. By construction, the rational function U is left invariant by the automorphisms of this extension. Thus U ∈ K(z a0 0 , . . . , z ar r ). Let S(z 0 r ) be the unique rational function such that U = S(z a0 0 , . . . , z ar r ). It is a rational power series and

u n = [z n 0 • • • z n r ]S.

Thus

n 0 u n t n = diag S, which concludes the proof that binomial sums are diagonals of rational functions, the "only if" part of Theorem 3.5.

Summation over a polyhedron.

To prove that, conversely, diagonals of rational power series are generating functions of binomial sums, we prove a property of closure of binomial sums under certain summations that generalize the indefinite summation of rule (e) of Definition 1.1. Let u : Z d+e → K be a binomial sum and let Γ ⊂ R d+e be a rational polyhedron, that is to say

Γ = λ∈Λ x ∈ R d+e λ(x) 0 ,
for a finite set Λ of linear maps R d+e → R with integer coefficients in the canonical bases. This section is dedicated to the proof of the following:

Proposition 3.12. If for all n ∈ Z d the set { m ∈ R e | ( n, m) ∈ Γ} is bounded, then the sequence v : n ∈ Z d → m∈Z e u n, m1 Γ ( n, m)
is a binomial sum, where 1 Γ ( n, m) = 1 if ( n, m) ∈ Γ and 0 otherwise.

Recall that H : Z → K is the sequence defined by H n = 1 if n 0 and 0 otherwise; it is a binomial sum, see

§1.1. Thus 1 Γ is a binomial sum, because 1 Γ ( n) = λ∈Λ H λ( n)
and each factor of the product is a binomial sum, thanks to rule (d) of the definition of binomial sums. However, the summation defining v ranges over an infinite set, rule (e) is not enough to conclude directly, neither is the generalized summation of Equation ( 6).

For

m ∈ R e , let | m| ∞ denote max 1 i e |m i |. For n ∈ Z d , let B( n) be B( n) def = sup {| m| ∞ | m ∈ R e and ( n, m) ∈ Γ} ∪ {-∞} . By hypothesis on Γ, B( n) < ∞ for all n ∈ Z d .
Lemma 3.13. There exists

C > 0 such that B( n) C(1 + |n| ∞ ), for all n ∈ Z d .
Proof. By contradiction, let us assume that such a C does not exist, that is there exists a sequence pk

= ( nk , mk ) of elements of Γ such that | mk | ∞ / | nk | ∞ and | nk | ∞ tend to ∞.
Up to considering a subsequence, we may assume that mk / | mk | ∞ has a limit ∈ R e , which is nonzero. For all α ∈ [0, 1] and k 0, the point p0

+ α( pk - p0 ) is in Γ, because Γ is convex. Let u > 0 and let α k = u/ | mk | ∞ . If k is large enough, then 0 α k 1. Moreover p0 + α k ( pk - p0 ) → k→∞ ( n0 , m0 + u ). Yet Γ is closed so ( n0 , m0 + u ) ∈ Γ. By definition | m0 + u | ∞ B( n0 ) < ∞.
This is a contradiction because = 0 and u is arbitrarily large.

Thus, for all n ∈ Z d , ( 8)

v n = m∈Z e | m| C(1+| n|∞) u n, m1 Γ ( n, m).
For 1 i d, let w i,+ be the sequence

w i,+ n def = H ni i-1 j=1 (H ni-nj -1 H ni+nj -1 ) d j=i+1 (H ni-nj H ni+nj ).
After checking that for any a, b ∈ Z, H a+b H a-b = 1 if a |b| and 0 otherwise, we see that

w i,+ n = 1 if n i = |n| ∞ and |n j | < |n i |
for all j < i ; and 0 otherwise. Likewise, let w i,-be the sequence

w i,- n def = H -ni-1 i-1 j=1 (H -ni-nj -1 H -ni+nj -1 ) d j=i+1 (H -ni-nj H -ni+nj ), so that w i,- n = 1 if n i = -|n| ∞ < 0 and |n j | < |n i |
for all j < i ; and 0 otherwise. The 2d sequences w i,+ and w i,-are binomial sums that partition 1: for all

n ∈ Z d 1 = d i=1 w i,+ n + d i=1 w i,- n .
By design, the sum in Equation ( 8) rewrites as

v n = d i=1 w i,+ n C(1+ni) m1=-C(1+ni) • • • C(1+ni) me=-C(1+ni) u n, m1 Γ ( n, m) + d i=1 w i,- n C(1-ni) m1=-C(1-ni) • • • C(1-ni) me=-C(1-ni) u n, m1 Γ ( n, m),
which concludes the proof of Proposition 3.12, because now the summation bounds are affine functions with integer coefficients of n. From a practical point of view, summations over polyhedra can be handled in a very different way, see §6.3.

Diagonals as binomial sums.

We now prove the second part of Theorem 3.5: the diagonal of a rational function is the generating function of a binomial sum. Let R(z 1 d ) be a rational power series and let us prove that the sequence defined by

u n = [z n 1 • • • z n d ]R is a binomial sum.
Since the binomial sums are closed under linear combinations, it is enough to consider the case where the numerator of R is a monomial and where the constant term of its denominator is 1. (It cannot be zero since R is a power series.) Thus R has the form

R = z m0 1 + e k=1 a k z mk ,
where the mk 's have nonnegative coordinates and mk = 0 if k = 0. Let y 0 e be new variables and let S be the rational power series

S(y 0 e ) def = y 0 1 + e k=1 a k y k = y 0 k∈N e k 1 + • • • + k e k 1 , . . . , k e a k1 1 • • • a ke e C k y k1 1 • • • y ke e .
The coefficient sequence C k of this power series is a binomial sum because the multinomial coefficient is a product of binomial coefficients:

k 1 + • • • + k e k 1 , . . . , k e = k 1 + • • • + k e k 1 k 2 + • • • + k e k 2 • • • k e-1 + k e k e-1 .
Let Γ ⊂ R × R e be the rational polyhedron defined by

Γ def = (n, k) ∈ R × R e k 1 0, . . . , k e 0 and m0 + e i=1 k i mi = (n, . . . , n) .
By construction R(z 1 d ) = S( z m0 , . . . , z me ), and the image of a monomial

y 0 y k1 1 • • • y ke e is a diagonal monomial z n 1 • • • z n d if and only if (n, k) ∈ Γ. Thus [z n 1 • • • z n d ]R = k∈Z e C k1 Γ (n, k).
Thanks to the positivity conditions on the mk 's, it is obvious that Γ satisfies the finiteness hypothesis of Proposition 3.12. Thus the sequence u n is a binomial sum.

Computing binomial sums

Computing may have different meanings. When manipulating sequences like binomial sums, one may want, for example, to compute recurrence relations that they satisfy, to decide their equality, to compute their asymptotic behavior or to find simple closed-form formulas for them. The representation of the generating series of binomial sums as residues or diagonals of rational functions gives an interesting tool to tackle these goals for binomial sums, though some questions remain open.

While the customary tool to compute recurrence relations satisfied by binomial sums is creative telescoping, integral representations of binomial sums give another approach: given a binomial sum we first compute an integral representation (this is fast and easy, see Algorithm 1), and next we compute a differential equation satisfied by the integral, which translates immediately into a recurrence relation for the binomial sum. The decision problem A = B can be solved by computing recurrence relations for A -B and checking sufficiently many initial conditions, see §4.4 for more details.

A recurrence relation is also a good starting point for deriving the asymptotic behavior of a univariate binomial sum (e.g. [START_REF] Mezzarobba | Effective bounds for P-recursive sequences[END_REF]. However, some constants that determine the asymptotic behavior can be computed numerically but it is not known how to decide their nullity, which makes it difficult to catch the subdominant behavior. A more direct method is possible in many cases once the generating function has been written as the diagonal of a rational power series [START_REF] Pemantle | Analytic Combinatorics in Several Variables[END_REF][START_REF] Salvy | Symbolic-numeric tools for analytic combinatorics in several variables[END_REF].

The problem of simplifying binomial sums is still largely open: for example, given the left-hand side of Strehl's identity (see §7.2.1), it is not known how to discover automatically the right-hand side. The only known automatic simplification procedures consist in computing a recurrence relation and applying the algorithm of [START_REF] Petkovšek | Hypergeometric solutions of linear recurrences with polynomial coefficients[END_REF] to find hypergeometric solutions or the algorithm of [START_REF] Abramov | D'Alembertian solutions of linear differential and difference equations[END_REF] to find D'Alembertian solutions. See §7.2 and §7.3 for numerous examples.

The computation of a recurrence relation for a binomial sum is done in two steps. Firstly, an integral representation is found and then a Picard-Fuchs equation is computed.

4.1. Picard-Fuchs equations. Let L be a field of characteristic zero and let R(z 1 r ) be a rational function with coefficients in L, written as R = P F where P and F are polynomials. Let A F be the localized ring L[z 1 r , F -1 ]. It is known that the L-linear quotient space [START_REF] Grothendieck | On the de Rham cohomology of algebraic varieties[END_REF]. Let us assume that there is a derivation ∂ defined on L. It extends naturally, with ∂z i = 0, to a derivation on A F that commutes with the derivations ∂ ∂zi , so that ∂ defines a derivation on the L-linear space

H F def = A F / ∂ ∂z1 A F + • • • + ∂ ∂zr A F is finite-dimensional
H F . Since H F is finite-dimensional, there exist c 0 m ∈ L, not all zero, such that c m ∂ m R + • • • + c 1 ∂R + c 0 R ∈ ∂ ∂z1 A F + • • • + ∂ ∂zr A F . Now let
us assume that L is the field of rational functions K(t 1 d ) and that ∂ is the derivation ∂ ∂ti for some i. Then the operator ∂ commutes with the operator res z1 r , as do the multiplications by elements of L, and Lemma 2.5 implies that

c m ∂ m ∂t m i f + • • • + c 1 ∂ ∂ti f + c 0 f = 0,
where f = res z1 r R, with t 1 d ≺ z 1 r . Differential equations that arise in this way are called Picard-Fuchs equations.

Recall that L d is the field of iterated Laurent series introduced in §2.

1. A series f (t 1 d ) ∈ L d is called differentially finite if the K(t 1 d )-linear subspace of L d generated by the derivatives ∂ n1+•••+n d f /∂t n1 1 • • • ∂t n d d , for n 1 d 0, is finite- dimensional.
In particular, a univariate Laurent series f ∈ L 1 is differentially finite if and only if there exist m 0 and polynomials p 0 m ∈ K[t], not all zero, such that p m f (m) + • • • + p 1 f + p 0 f = 0. In that case, we say that f is solution of a differential equation of order m and degree max k deg p k . The above argument implies the following classical theorem of which [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF] gave an elementary proof.

Theorem 4.1. For any rational function R(t 1 d , z 1 r ) with t 1 d ≺ z 1 r , the residue res z1 r R is differentially finite.

In previous work (Bostan et al. 2013a, Theorem 12;Lairez 2014, §I.35.3), we proved the following quantitative result about the size of Picard-Fuchs equations and the complexity of their computation. We also described an efficient algorithm to compute Picard-Fuchs equations (Lairez 2016).

Theorem 4.2. Let R ∈ K(t, z 1 r ) be a rational function, written as R = P F , with P and F polynomials. Let

N = max(deg z1 r P + r + 1, deg z1 r F ) and d t = max(deg t P, deg t F ).
Then res z1 r R, with t ≺ z 1 r , is solution of a linear differential equation of order at most N r and degree at most ( 5 8 N 3r + N r ) exp(r)d t . Moreover, this differential equation can be computed with O(exp(5r)N 8r d t ) arithmetic operations in K, uniformly in all the parameters. 4.2. Power series solutions of differential equations. When a power series satisfies a given linear differential equation with polynomial coefficients, one only needs a few initial conditions to determine entirely the power series.

Let L ∈ K[t] ∂ t be a linear differential operator in ∂ t with polynomial coefficients in t. There exists a unique n ∈ Z and a unique b L ∈ K[a] such that L(t a ) = b L (a)t a+n + o(t a+n ) for all a ∈ Z and t → 0. The polynomial b L is the indicial polynomial of L at t = 0. For more details about the indicial polynomial, see Ordinary Differential Equations [START_REF] Ince | Ordinary Differential Equations[END_REF]. It is easy to check that if f ∈ K t is annihilated by L, then its leading monomial

t n satisfies b L (n) = 0. Proposition 4.3. Let f ∈ K t . If L(f ) = 0 and if [t n ]f = 0 for all n ∈ N such that b L (n) = 0, then f = 0.
It is worth noting that the indicial equation of a Picard-Fuchs equation is very special: Theorem 4.4 [START_REF] Katz | Nilpotent connections and the monodromy theorem: Applications of a result of Turrittin[END_REF]. If L is a Picard-Fuchs equation, then the degree of b L equals the order of L and all the roots of b L are rational.

The data of a differential operator L and elements of K for each nonnegative integer root of b L (that we will call here sufficient initial conditions) determines entirely an element of K t . It is an excellent data structure for manipulating power series [START_REF] Salvy | Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable[END_REF]. For example, it lets one compute efficiently the coefficients of the power series n u n t n : the differential equation translates into a recurrence relation

p r (n)u n+r + . . . + p 1 (n)u n+1 + p 0 (n)u n = 0
for some polynomials p 0 r ∈ K[n] and the sufficient initial conditions translate into initial conditions for the recurrence, exactly where we need them. 4.3. Equality test for univariate differentially finite power series. Let f ∈ K t be a power series given by a differential operator L ∈ K[t] ∂ t such that L(f ) = 0, and by sufficient initial conditions. Let M be another differential operator. We may decide if M(f ) = 0 in the following way. Firstly, we compute the right g.c.d. of M and L: this is the operator D of the largest order such that M = M D and L = L D for some operators M and L in K(t) ∂ t . Then, it is enough to compute the indicial equation b L and to compute [t n ]D(f ) for each nonnegative integer root n of b L . We will find only zeros if and only if M(f ) = 0. Indeed, M(f ) = 0 if and only if D(f ) = 0 and since L (D(f )) = 0, we may apply Proposition 4.3 to check whether D(f ) = 0 or not. Now, let g ∈ K t be another power series given by a differential operator M ∈ K[t] ∂ t and sufficient initial conditions. To decide if f = g, it is enough to check that M(f ) = 0, with the above method, and to check that the coefficients of f and g corresponding to the nonnegative integer roots of b M are the same.

4.4. Equality test for binomial sums. Let u : Z → K be a binomial sum. Up to considering separately the binomial sums H n u n and H n u -n , it is enough to look at the case where u n = 0 for n < 0. In this case u is entirely determined by its generating function f = n 0 u n t n . Using Algorithm 1 we obtain an integral representation of f , and then, as explained in §4.1, we obtain a differential operator L that annihilates f . Since u is a binomial sum given explicitly, we can compute sufficient initial conditions. Given another binomial sum v : N → K, we can check that u = v by computing a differential operator annihilating the generating function g of v together with sufficient initial conditions and by checking that f = g with the method explained in §4.3.

Let us now consider the multivariate case. As above, we can reduce the equality test for binomial sums Z d → K to the equality test for binomial sums N d → K. And this equality test can be reduced to the equality test for binomial sums N d-1 → K as follows. Let u : N d → K be a binomial sum. It is determined by its generating function f (t

1 d ) = n∈N d u nt n ∈ L d . With Algorithm 1, we compute a rational function R(t 1 d , z 1 r ) such that f = res z1 r f . Let K be the field K(t 1 d-1 ). Following §4.1, we can compute an operator L ∈ K [t d ] ∂ t d such that L(f ) = 0.
This gives a differential equation for f considered as a power series in t d with coefficients in L d-1 . The sufficient initial conditions to determine f are given by the power series n∈N d-1 u n,k tn , where k ranges over the nonnegative integer roots of b L . These power series are the generating functions of binomial sums in d -1 variables. This reduces the equality test for binomial sums in d variables to the equality test for binomial sums in d -1 variables.

Geometric reduction

Putting into practice the computation of binomial sums through integral representations shows immediately that the number of integration variables is high and makes the computation of the Picard-Fuchs equations slow. However, the rational functions obtained this way are very peculiar. For example, their denominator often factors into small pieces. This section presents a sufficient condition under which a residue res v F of a rational function F is rational. This leads to rewriting an iterated residue of a rational function, like the ones given by Corollary 2.7, into another one with one or several variables less. This simplification procedure is very efficient on the residues we are interested in and reduces the number of variables significantly.

Conceptually the simplification procedure is simple: in terms of integrals it boils down to computing partial integrals in specific cases where we know that they are rational. The rational nature of a partial integral depends on the integration cycle and integration algorithms usually forget about this cycle. Instead, they compute the Picard-Fuchs equations-see §4.1-that annihilate a given integral for any integration cycle. In our setting, the integration cycle underlies the notion of residue-see §2.5. This provides a symbolic treatment that we call geometric reduction since it takes into account the geometry of the cycle and decreases the number of variables for which the general integration algorithm above is actually needed. The time required by the computation is dramatically reduced by this symbolic treatment. 5.1. Rational poles. Let us consider variables v and z 1 d , where v can appear anywhere in the variable ordering. Let F (v, z 1 d ) = a/f be a rational function. In general, res v F is not a rational function-except if v is the smallest variable, see §2.3.

Let ρ ∈ L d be a power series in the variables z 1 d . The classical residue of F at v = ρ, denoted Res v=ρ F , is the coefficient of 1/(v -ρ) in the partial fraction decomposition of F as an element of L d (v). Contrary to the formal residue res v F , the classical residue is always in the field generated by ρ and the coefficients of F . Similarly to the formal residues, the classical residues of a derivative ∂G/∂v are all zero.

Classical residues can be computed in a simple way: if ρ is not a pole of F , then Res v=ρ F = 0; if ρ is a pole of order 1, then Res v=ρ F = ((v -ρ)F ) | v=ρ ; and if ρ is a pole of order r > 1, then

Res v=ρ F = 1 (r -1)! ∂ r-1 (v -ρ) r F ∂ r-1 v v=ρ .
In its simplest form, the geometric reduction applies when f factors over K(z 1 d ) as a product of factors of degree 1:

f = C(z 1 d ) ρ∈U (v -ρ) nρ ,
where U is a finite subset of K(z 1 d ). Then the partial fraction decomposition of F writes as

F = ρ∈U a ρ v -ρ + k>1 b ρ,k (v -ρ) k + P (v), where a ρ ∈ K(z 1 d ) is Res v=ρ F , where b ρ,k ∈ K(z 1 d ) and where P ∈ K(z 1 d )[v].
The terms with multiple poles and the polynomial term are derivatives and thus their formal residue with respect to v are zero. Hence

res v F = ρ∈U res v a ρ v -ρ .
Let ρ ∈ U . Depending on the leading monomial lm(ρ) of ρ, as an element of L d , two situations may occur. Either lm(ρ) ≺ v, in which case

a ρ v -ρ = a ρ v ∞ n=0 ρ v n ,
and res v aρ v-ρ = a ρ ; or lm(ρ) v, in which case

a ρ v -ρ = - a ρ ρ ∞ n=0 v ρ n ,
hence res v aρ v-ρ = 0. Since the variable v does not appear in ρ, the equality lm(ρ) = v cannot happen. In the end, we obtain that ( 9)

res v F = ρ∈U [lm(ρ) ≺ v] Res v=ρ F,
where the bracket is 1 if the inequality inside is true and 0 otherwise. In particular, the right-hand side is a rational function that we can compute.

Example 5. Let d > 0 be an integer and let us consider the binomial sum

u n = n k=0 (-1) k n k dk n .
We will show that u n = (-d) n . This example is interesting because the geometric reduction procedure alone is able to compute entirely the double integral representing the generating function of u, whereas Zeilberger's algorithm finds a recurrence relation of order d -1 (Paule and Schorn 1995), far from the minimal recurrence relation u n+1 + du n = 0. Algorithm 1 computes that n 0

u n t n = res z1,z2 z 2 (z 2 -t(1 + z 1 ))(z 1 z 2 + t(1 + z 1 )(1 + z 2 ) d ) , with t ≺ z 1 ≺ z 2 .
Let F denote the rational function on the right-hand side. Each factor of the denominator of F has degree 1 with respect to z 1 . Thus Equation ( 9) applies. The roots of the denominator are

ρ 1 = z 2 t -1 and ρ 2 = -1 1 + z2 t(1+z2) d
, moreover lm(ρ 1 ) = z 2 /t z 1 and lm(ρ 2 ) = t/z 2 ≺ z 1 . Thus res z1 F = Res z1=ρ2 F and we obtain n 0

u n t n = res z2 res z1 F = res z2 1 t(1 + z 2 ) d + z 2 -t .
If d > 2, the denominator of the latter rational function does not split into factors of degree 1 and Equation ( 9) does not apply. However, the study of nonrational poles can lead to a further reduction.

5.2. Arbitrary poles. Equation ( 9) extends to the general case. To describe this generalization, we need an algebraic closure of L d . Let L d,N be the field

L d,N def = K((z 1/N d ))((z 1/N d-1 )) . . . ((z 1/N 2
))((z

1/N 1
)).

It is the algebraic extension of L d generated by the z 1/N i . Let L d,∞ be the union of all L d,N , N > 0, and let K ⊗ K L d,∞ be the compositum of L d,∞ and K, where K is an algebraic closure of K. The following is classical (e.g. [START_REF] Rayner | Algebraically closed fields analogous to fields of Puiseux series[END_REF]).

ρ 1 = - 1 2 + √ 1 + 4x 2 and ρ 2 = - 1 2 - √ 1 + 4x 2 .
Only 0 and ρ 1 are small. Thus

res y F = Res y=0 F + Res y=ρ1 F = - 1 x 2 + 2 x + 4x 2 -x √ 1 + 4x .
Equation ( 10) does not look as interesting as Equation ( 9) because the right-hand side is algebraic and need not be a rational function. However, if all roots are large, then the residue is zero, which is interesting. On the contrary, if they are all small, then res v F is the sum of all the classical residues of F , which equals the residue at infinity:

res v F = Res v=∞ F def = Res v=0 - 1 v 2 F | v←1/v
, which is a rational function. Thus, in the case where the poles are either all small or all large, Equation (10) shows that the residue res v F is rational and shows how to compute it.

Actually it is enough to check that any two conjugate poles (two poles are conjugate if they annihilate the same irreducible factor of the denominator of F ) are simultaneously large or small. Indeed, we can write f = r k=1 f n k k where f 1 r are irreducible polynomials in K(z 1 d ) [v], and the partial fraction decomposition leads to

F = r k=1 a k f n k k
for some polynomials a 1 r . Equation (10) applies to each term of this sum. If U k denotes the set of all the roots of f k , then

res v F = r k=1 ρ∈U k [lm(ρ) ≺ v] Res v=ρ a k f n k k ,
and we can apply the all large or all small criterion to each subsum separately.

Proposition 5.2. With the notations above, if for all k, there exists

ε k ∈ {0, 1} such that [lm(ρ) ≺ v] = ε k for all ρ ∈ U k , then res v F = r k=1 ε k Res v=∞ a k f n k k .
It remains to explain how to compute the leading monomials of the roots of a polynomial f ∈ K(z 1 d ) [v]. If d = 1, then it is the classical method of Newton's polygon for the resolution of bivariate polynomial equations using Puiseux series (e.g. [START_REF] Walker | Algebraic Curves[END_REF][START_REF] Cutkosky | Resolution of singularities[END_REF]). When d 2, we may apply this method recursively by considering L d as a subfield of the field of Puiseux series with coefficients in L d-1 . Based on this idea, Algorithm 3 proposes an implementation which avoids all function AllLargeOrAllSmall(S, k) if

max m∈S m k = min m∈S m k then return ∅ if k = 1 then return {out} µ ← min m∈S m 1 M ← (m 2 n ) ∈ N d-1 m ∈ S and m 1 = µ r ← AllLargeOrAllSmall(M, k -1) if max m∈S m k > max m∈M m k then r ← r ∪ {out} if min m∈S m k < min m∈M m k then r ← r ∪ {in} return r
technicalities. Algorithm 4 sums up the geometric reduction procedure with respect to the variable v. Of course one should apply the procedure iteratively with every variable until no further reduction is possible. The success of the reduction may depend on the order in which we eliminate all the variables. It is possible to try every possible order efficiently thanks to the following compatibility property: if both GeomRed(GeomRed(R, u), v) and GeomRed(GeomRed(R, v), u) do not fail, then they are both equal to res u,v (R).

Example 7. Continuing Example 5, let us consider res z F 1 , where F 1 = 1/(t(1 + z) d +z-t), with t ≺ z. The denominator factors as zg, where g = 1+t

d-1 k=0 d k+1 z k . Thus, the leading monomial of any root of f is t -1 d-1 , which it not ≺ z. All the roots of g are large, so only the pole z = 0 remains and res z F 1 = Res z=0 F 1 , by Proposition 5.2. Thus res z F 1 = 1 1+dt and it follows that

n k=0 (-1) k n k dk n = (-d) n .
If we computed the Picard-Fuchs equation of F 1 , we would find a differential equation of order d because the Picard-Fuchs operator annihilates all the periods, and the periods associated to the roots of g are algebraic of degree d -1.

6. Optimizations 6.1. Infinite sums. So far, we have only considered binomial sums in which the bounds of the symbols are finite and explicit. It is possible and desirable to consider infinite sums, or more exactly syntactically infinite sums which in fact reduce to finite sums but whose summation bounds are implicit. This often leads to simpler integral representations.

For example, in the sum n k=0 n k , the upper summation bound n is not really useful when n 0, we could as well write one may add the new building block

M n = [1] (1 -x)(1 + x) 2 x 1 + x + x 2 x n .
In the applications below, we made use of alternative definitions of the binomial coefficient and their corresponding representations:

n k def = H n H k n k = [1] x k-n y -k 1 -x -y , (11) n k def = n n -k = [1] 1 (1 -z) k+1 z n-k . ( 12
)
They differ from the binomial coefficient, as defined in §1, only when n < 0 and agree on their non zero values (see also Figure 2). 6.3. Summation over a polyhedron. As in §3.2, let Γ ⊂ R d+e be a rational polyhedron and u : Z d+e → K be a binomial sum. Let us consider the sequence

v : n ∈ N d → m∈Z e u n, m1 Γ ( n, m),
where 1 Γ ( n, m) = 1 if ( n, m) ∈ Γ and 0 otherwise. Proposition 3.12 shows that v is a binomial sum under an additional finiteness hypothesis on Γ, and according to Corollary 2.7, there exists a rational function R(t

1 d , z 1 r ) such that n∈N d v nt n = res z1 r R.
It is possible to circumvent the construction used in the proof of Proposition 3.12 and compute directly such a rational function R given two ingredients: firstly, the generating function of Γ

ϕ Γ (t 1 d , s 1 e ) def = ( n, m)∈Z d+e 1 Γ ( n, m) tn s m,
which is known to be a rational function (e.g. [START_REF] Brion | Points entiers dans les polyèdres convexes[END_REF]; and secondly, a representation of the binomial sum u as

u n, m = [1]RT n1 1 • • • T n d d S m1 1 • • • S me e
for some rational functions R, T 1 d and S 1 e ∈ K(z 1 r ). Then, with t 1 e ≺ z 1 d ,

n∈N d v nt n = [1]R ( n, m)∈Z d+e 1 Γ ( n, m)(t 1 T 1 ) n1 • • • (t d T d ) n d S m1 1 • • • S me e = res z1 r R • ϕ Γ (t 1 T 1 , . . . , t d T d , S 1 , . . . , S d ) z 1 • • • z d ,
provided that the sums converge in L d+e . This method is interesting because it is known how to compute efficiently compact representations of the rational function ϕ Γ [START_REF] Barvinok | Integer points in polyhedra[END_REF].

7. Applications 7.1. Andrews-Paule identity. We detail the proof of the following identity:

(13)

n i=0 n j=0 i + j j 2 4n -2i -2j 2n -2i = (2n + 1) 2n n 2 .
This identity appeared first as a problem in the American Mathematical Monthly [START_REF] Blodgett | Problem E3376[END_REF]) and was subsequently proved by [START_REF] Andrews | Some questions concerning computer-generated proofs of a binomial double-sum identity[END_REF] and [START_REF] Wegschaider | Computer Generated Proofs of Binomial Multi-Sum Identities[END_REF] using various tools from the method of creative telescoping. It attracted attention because the theory of creative telescoping was unable to give a complete automated proof at that time.

Let u n denote the left-hand side. It can be written as an infinite sum

u n = ∞ i=0 ∞ j=0 i + j j 2 (2n -2i) + (2n -2j) 2n -2i ,
where n k is the natural binomial defined by

n k = H n H k n k , see §6.2.
Of course, we could have stuck to the former definition and used finite sums, but while the natural binomials introduce two variables instead of one in the integral representation-see Equation ( 11)-the integral representation obtained after the geometric reduction step is often simpler when using the natural binomial.

So we obtain the following integral representation:

n 0 u n t n = res z1 6 z1z2 (z 2 1 z 2 2 -t)(z4z6-z 2 1 )(z3z5-z 2 2 )(1-z3-z4)(1-z5-z6)(1-z1-z2) , with the ordering t ≺ z 1 ≺ z 2 ≺ z 3 ≺ z 4 ≺ z 5 ≺ z 6 .
As expected, each binomial coefficient brings two extra variables so we end up with six variables in addition to the parameter t. Geometric reduction applies successively with respect to the variables z 1 , z 3 , z 4 and z 5 . For example, the poles w.r.t. the variable z 1 , are {±tz

-1/2 2 }, {±z 1/2 4 z 1/2
6 } and {1 -z 2 }, gathered by conjugacy classes. The first pair of conjugate poles is ≺ z 1 whereas the second one is z 1 . The rational root 1 -z 2 is z 1 . Thus, by application of Proposition 5.2, n 0

u n t n = res z2 6 (1 -z 2 )z 3 2 (t -(1 -z 2 ) 2 z 2 2 ) (1 -z 3 -z 4 ) (z 2 2 -z 3 z 5 ) (1 -z 5 -z 6 ) (t -z 2 2 z 4 z 6 )
.

In the end, repeated application of Algorithm 4 leads to n 0

u n t n = res z4,z6 (z 6 -1)z 3 6 (t -z 2 6 (z 6 -1) 2 )((z 4 -1)t -z 4 z 2 6 (z 2 6 + z 4 -1))
.

Using the algorithm of Lairez (2016), we obtain (in about one second) a differential operator annihilating n 0 u n t n :

16t 4 (256t 2 + 736t + 81)(16t -1) 2 ∂ 6 t + 16t 3 (16t -1)(86016t 3 + 256256t 2 + 20976t -1053)∂ 5 t + 4t 2 (36601856t 4 + 113760256t 3 + 6103168t 2 -908088t + 14823)∂ 4 t + 16t(22691840t 4 + 75716608t 3 + 6677824t 2 -459552t + 3645)∂ 3 t + (305827840t 4 + 1109626112t 3 + 139138736t 2 -4247073t + 9720)∂ 2 t +(60272640t 3 +244005120t 2 +42117840t-374625)∂ t +691200t 2 +3369600t+996300
The roots of the indicial equation are 0, 1, -1 2 et 1 2 . This differential operator corresponds to the Picard-Fuchs equation associated to the integral representation, but it is not the minimal-order operator annihilating n 0 u n t n . This may happen because the differential operator that we compute annihilates more that simply the residue in which we ar interested: it annihilates every period of the integral of the rational function inside the residue. Of course, this is not a issue as long as we do obtain a differential equation.

Concerning the right-hand side, we find the integral representation

n 0 (2n + 1) 2n n 2 t n = res z1,z2 t + u 2 (u 2 -1)u 1 (u 1 -1) (t -u 2 (u 2 -1)u 1 (u 1 -1)) 2 ,
which cannot be simplified further with the geometric reduction. We compute (in about 0.1s) the annihilating operator: t(16t -1)∂2 t + (48t -1)∂ t + 12. The Andrews-Paule identity follows with the equality test described in §4.2.

In this case the right-hand side is a hypergeometric sequence, so it can be discovered automatically: the differential equation of order 6 leads to a recurrence relation of order 4 for u n from which the algorithm of [START_REF] Petkovšek | Hypergeometric solutions of linear recurrences with polynomial coefficients[END_REF] finds the hypergeometric solutions and the initial conditions are enough to identify the right-hand side. 7.2. Several known identities. This section shows the integral representations and the Picard-Fuchs equations appearing in the proofs of known identities. The integral representations have been obtained with the method presented in this article and the variants presented in §6. Note that the computation of the annihilating operator never takes longer than 4 seconds. 7. 2.1. Strehl (1994). This identity relates the Apéry numbers (left) and Franel numbers (the inner sum in the right-hand side). g.f.l.h.s 2 = res z1 3 1 (1 -z 1 )(1 -z 2 )(1 -z 3 )z 1 z 2 z 3 -t(z 1 + z 2 z 3 -z 1 z 2 z 3 ) g.f.r.h.s3 = res ann. op. 4 = t 2 (t 2 -34t + 1)∂ 3 t + 3t(2t 2 -51t + 1)∂ 2 t + (7t 2 -112t + 1)∂ t + t -5 7.2.2. Graham et al. (1989, p. 33) and Wegschaider (1997, §5.7.6). 1 (1 -z 1 )(1 -z 2 )(1 -z 3 )z 1 z 2 z 3 + (z 2 -z 3 )(z 1 -z 3 )t g.f.r.h.s = res

z1 3 1 (1 -z 1 )(1 -z 2 )(1 -z 3 )z 1 z 2 z 3 + (1 -z 1 -z 2 )z 3 t -(1 -z 1 )(1 -z 2 )t
ann. op. = t 2 (4t+1)(16t-1)∂ 3 t +3t(128t 2 +18t-1)∂ 2 t t+(444t 2 +40t-11)∂ t +60t+2 7.2.3. Dent. The following identity is due to Dent and used as an example by Wegschaider (1997, p. 90): n1+2n2 k=0 j 0 (-1) j k j

2n 2 + n 1 -k 2n 2 -j n 1 k -j = 2 n1 n 1 + n 2 n 1 , with n 1 , n 2 0.
g.f.l.h.s = g.f.r.h.s = 1 1 -2t 1 -t 2 Here, the generating series is rational and geometric reduction performs the entire computation, there is no need to compute a Picard-Fuchs equation. (1 -z 2 )(1 -z 1 )z 1 z 2 z 2 1 z 2 2 (1 -z 2 ) 2 (1 -z 1 ) 2 -(1 -z 1 -z 2 ) 2 t g.f.r.h.s = res

z1 3 1 t + z 1 z 2 (1 -z 1 -z 2 )
ann. op. = t(27t + 1)∂ 2 t + (54t + 1)∂ t + 6 7.2.5. Moriarty (see Egorychev 1984, p. 11). Because of the division by n + m, the right-hand side is not obviously a binomial sum. However, it becomes obvious after observing that

n n + k n + k 2k = n + k -1 2k + 1 2 n + k -1 2k -1 .
g.f.l.h.s = g.f.r.h.s = 1 2

(1 -t 1 )(1 + t 1 ) t 2 1 + 4t 1 t 2 + 2t 1 + 1 Here again it is a rational power series and the geometric reduction finds it. 7.2.6. Davletshin et al. (2015, Theorem 1.2).

1 + ∞ q=1 2 q-1 n 2 q   n1/2 m=1 m -1 q -1 + n1 m=1 m -1 q -1   = ∞ q=1
2 q-1 n 2 q n 1 q + n 1 /2 q g.f.l.h.s = g.f.r.h.s =

t 1 t 2 (1 + t 1 -t 2 -t 1 t 2 -2t 2 1 -2t 2 1 t 2 ) (1 -t 2 )(1 -t 1 )(1 -t 2 -t 2 1 t 2 -t 2 1 )(1 -t 1 -t 2 -t 1 t 2 )
The summation bound n 1 /2 and the integer part n 1 /2 may look problematic, until we observe that

n/2 m=1 m -1 q -1 = ∞ m=1 m -1 q -1 H n-2m
and n/2 q = ∞ k=0 k q (δ 2k-n + δ 2k+1-n ) , using the binomial sums δ and H defined in §1.

7.2.7. Davletshin et al. (2015, Theorem 1.1).

2 + ∞ q=1 n 2 q   n1/2 m=1 m -1 q -1 + ∞ k1=1 • • • ∞ kq=1 δ k1+•••+kq-m q i=1 (k i + 1)   = n 1 + 2n 2 2n 2 + n 1 /2 + n 2 n 2
g.f.l.h.s = g.f.r.h.s =

t 1 t 2 (1 -t 2 -2t 2 1 + t 3 1 -2t 2 1 ) (1 -t 2 )(1 -t 1 )(1 -t 2 -t 2 1 )(1 -t 2 -2t 1 + t 2 1
) Again, the left-hand side does not have the appearance of a binomial sum until we remark that

∞ k1=1 • • • ∞ kq=1 δ k1+•••+kq-m q i=1 (k i + 1) = [1] t(2 -t) (1 -t) 2 q 1 t m .
7.2.8. [START_REF] Chapman | Problem 11914[END_REF]. where we consider the binomial coefficient as defined in §1.1 and not one of the variants of §6.2. This is an important clarification because negative values may appear in the upper arguments of the binomial coefficients. The geometric reduction is enough to prove this equality, no integration step is required.

7.3. Proof of some conjectures.

7.3.1. Le Borgne's identity. The following identity for Baxter's numbers arises as a conjecture in an unpublished work by Yvan Le Borgne. With the methods presented here we can prove it automatically.

1 + F -1,-1 n + 2F 0,0 n -F 0,1 n + F 1,0 n -3F 1,1 n + F 1,2 n -F 3,1 n + 3F The sum in the right-hand side does not have the appearance of a binomial sum (even if it is such), but the identity becomes clearly an identity between binomial sums after multiplication by n+2 1 n+2 2 . Alternatively, one can use the following equality to write the right-hand side as a binomial sum: [START_REF] Brent | Some binomial sums involving absolute values[END_REF]. We have been able to prove the following identities conjectured by [START_REF] Brent | Some binomial sums involving absolute values[END_REF]. The left-hand sides involve absolute values of nonlinear polynomials. They are nevertheless binomial sums for two reasons. The first one is that all the nonlinear polynomials under consideration split into linear or positive factors. For example |i 3 -j 3 | = |i -j|(i 2 + ij + j 2 ) and |i -j| = (i -j)(H i-j -H j-i ) is a binomial sum.

The second reason, which we used for the computation, is that we can eliminate the absolute values by using the symmetries of the sums. For example The integral representations obtained are too lengthy to be presented here, they can be found online5 . Since the right-hand sides are hypergeometric sequences, they can be computed from the recurrence relations satisfied by the left-hand sides with the algorithm of [START_REF] Petkovšek | Hypergeometric solutions of linear recurrences with polynomial coefficients[END_REF]. (Brent et al. 2014, Eq. 5.7) i,j 2n n + i 2n n + j |i 3 -j 3 | = 2n 2 (5n -2) 4n -1 4n 2n (Brent et al. 2014, Eq. 5.8) i,j 2n n + i 2n n + j |i 5 -j 5 | = 2n 2 (43n 3 -70n 2 + 36n -6) (4n -1)(4n -3) 4n 2n (Brent et al. 2014, Eq. 5.9) i,j 2n n + i 2n n + j |i 7 -j 7 | = 2n 2 (531n 5 -1960n 4 +2800n 3 -1952n 2 +668n-90) (4n-1)(4n-3)(4n-5) 4n 2n (Brent et al. 2014, Eq. 5.12) i,j The integral representation of the right-hand side is more complicated ant still has five variables, in addition to the parameter. The computation requires several hours with the current algorithms. Without the geometric reduction, it involves nine variables and a parameter.

For

  all a, b ∈ Z, we define the directed sum b k=a as b k=a

  in contrast with the usual convention that b k=a u k = 0 when a > b. This implies the following flexible summation rule for directed sums: for all a, b, c ∈ Z, and also the geometric summation formula b k=a r k = r a -r b+1 1 -r for any r = 1, valid independently of the relative position of a and b.

  Let us give a few useful examples. All polynomial sequences Z d → K are in B, because B is an algebra and because the sequence n → n 1 = n is in B, thanks to points (c) and (d) of the definition. Let (H n ) n∈Z be the sequence defined by H n = 1 if n 0 and H n = 0 if n < 0. It is a binomial sum since H n = n k=0 δ k . As a consequence, we obtain the closure of B by usual (indefinite) sums since

Figure 1 .

 1 Figure 1. Construction of a binomial sum. The last step replaces the directed sum by a usual sum in order to have nonzero values for n 0 only.

Lemma 2 . 6 .

 26 Let α, β ⊂ {z 1 d } be disjoint sets of variables. If f ∈ L d does not depend on the variables in β and if g ∈ L d does not depend on the variables in α,

  by definition of the differentiation in L r . In the proof of Corollary 2.3, we checked that [ tn z0 ] R = [1]S 0 S n1 1 • • • S n d d , for n ∈ N d , and 0 otherwise. Therefore, u n = [ tn z0 ]R, for n ∈ N d . This gives an implementation of Corollaries 2.3 and 2.7 in the generalized setting. Algorithm 2 sums up the procedure for computing integral representations.

Lemma 5. 1 (

 1 Iterated Puiseux theorem). The field K ⊗ K L d,∞ is an algebraic closure of L d . The field K ⊗ K L d,∞ is thus simply denoted L d . The valuation defined on L d is extended to a valuation defined on L d with values in the group Q d , ordered lexicographically. The leading monomial lm(ρ) of an f ∈ L d is also defined as zv(f) . The argument of §5.1 applies and shows that , the poles are in L d . A root ρ is called small if ρ = 0 or lm(ρ) ≺ v and large otherwise. Example 6. Let F = 1 xy(y 2 +y-x) , with x ≺ y. With respect to y, the poles of F are 0, and

Algorithm 3 .

 3 Computation of the all large or all small criterion Input: S ⊂ N d finite; an integer 1 k d. Output: A subset of {in, out}. Specification:Let P = n∈N d a nzn ∈ K[z 1 d ] be a polynomial. If S = { n ∈ N d | a n = 0}then AllLargeOrAllSmall(S, k) contains out (resp. in) if and only if there exists a nonzero ρ ∈ L d in which z k does not appear such that P (z1, . . . , z k-1 , ρ, z k+1 , . . . , z d ) = 0 and lm(ρ) z k (resp. lm(ρ) ≺ z k ).

Figure 2 .

 2 Figure 2. Supports of some variants of the binomial coefficient.

  z1)(1-z2)(1-z3)z1z2z3-t(1-z3-z2(1-(2+z1(1-z2)(1-z3))z3))

7. 2

 2 .4.[START_REF] Dixon | On the sum of the cubes of the coefficients in a certain expansion by the binomial theorem[END_REF].

.

2 .

 2 Identities from

  Computational limitations. The method is mainly limited by the integration step. When the integral representation has more than four variables (in addition to the parameter and after the geometric reduction), then computation of the Picard-Fuchs equation becomes challenging. For example, in Strehl's second identity of the generating function of each side has five variables and a parameter. For the left-hand side, we obtain res z1z2z3z4z5-z3z4z5+z1z2)t+z1z2z3z4z5(1-z1)(1-z2)(1-z3)(1-z4)(1-z5) .

  Proposition 3.10. A sequence N d → K is a binomial sum if and only if there exists a rational function R(t 1 d , z 1 r ), with t 1 d ≺ z 1 r , such that u The "only if" part is Corollary 2.3. Conversely, let R(t 1 d , z 1 r ) be a rational function and let u

	for all	n ∈ Z d .	n = [ tn z0 ]R
	Sketch of the proof.

This notion is closely related to the grade of a power series(Allouche and Mendès France

2011).

Generating function of the left-hand side

Generating function of the right-hand side

Annihilating operator of both right and left-hand sides

https://github.com/lairez/binomsums

Acknowledgments. We thank Marko Petkovšek for orienting us in some of the literature. This work has been supported in part by FastRelax ANR-14-CE25-0018-01 and by the research grant BU 1371/2-2 of the Deutsche Forschungsgemeinschaft.

Algorithm 4. Geometric reduction Input: F (z 1 d ), a rational function; an integer 1 k d. Output: Fail or a rational function S(z 1 k-1 , z k+1 d ). Specification: If a rational function S is returned and then resz k F = S.

To compute an integral representation of binomial sums involving infinite summations, the principle is to proceed as in §2.2 except when an infinite geometric sum n 0 f in L d shows up, where we check that lm(f ) ≺ 1 so that Lemma 2.1 applies. If it does, then the summation is performed and the computation continues. If it does not, then the binomial sum is simply rejected.

We proceed as in §2.2 except that infinite geometric sums in L d are valid when Lemma 2.1 applies. Firstly n k = [1](1 + z) n z -k . Then we consider the infinite sum ∞ k=0 (1 + z) n z -k . Since 1/z 1, it does not converge, so the binomial sum is rejected. And indeed, when n < 0 the sum ∞ n=0 n k has infinitely many non zero terms. If we change n k into n n-k , which is the same when n 0, we obtain

where this time the sum converges.

Building blocks. Besides the binomial coefficient

, we have found useful to have additional building blocks to extend Algorithms 1 and 2 that contruct integral representations. Without enlarging the class of binomial sums, one can add any sequence of the form

where R 0 d are rational functions, as a new building block. Judicious extra building blocks may give simpler integral representations or speed up the computation. For example, when working with Motzkin numbers