Alin Bostan
email: alin.bostan@inria.fr

Irina Kurkova
email: irina.kourkova@upmc.fr

Kilian Raschel
email: kilian.raschel@lmpt.univ-tours.fr

A human proof of Gessel's lattice path conjecture

Keywords: 1991 Mathematics Subject Classification. Primary 05A15, Secondary 30F10, 30D05 Enumerative combinatorics, lattice paths, Gessel walks, generating functions, algebraic functions, elliptic functions

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

Introduction

Main results. Gessel walks are lattice paths confined to the quarter plane N 2 = {0, 1, 2, . . .} × {0, 1, 2, . . .}, that start at the origin (0, 0) and move by unit steps in one of the following directions: West, East, South-West and North-East, see Figure 1. Gessel excursions are those Gessel walks that return to the origin. For (i , j) ∈ N 2 and n 0, let q(i, j; n) be the number of Gessel walks of length n ending at the point (i , j). Gessel walks have been puzzling the combinatorics community since 2001, when Ira Gessel conjectured:

(A) For all n 0, the following closed-form expression holds for the number of Gessel excursions of even length 2n q(0, 0; 2n) = 16 n (5/6) n (1/2) n (2) n (5/3) n ,

where (a) n = a(a + 1) • • • (a + n -1) denotes the Pochhammer symbol.

Note that obviously there are no Gessel excursions of odd length, that is q(0, 0; 2n + 1) = 0 for all n 0. In 2008, Kauers, Koutschan and Zeilberger [START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF] provided a computer-aided proof of this conjecture.

A second intriguing question was to decide whether or not: On the left: allowed steps for Gessel walks. Note that on the boundary of N 2 , the steps that would take the walks out of N 2 are discarded. On the right: an equivalent formulation of Gessel walks as the simple walks evolving in the cone with opening 135 • .

(B) Is the complete generating function (GF) of Gessel walks Q(x, y ; z) = i,j,n 0 q(i , j; n)x i y j z n

(2) D-finite 1 , or even algebraic (i.e., root of a non-zero polynomial in Q(x, y , z) [T ])?

The answer to this question -namely, the (initially unexpected) algebraicity of Q(x, y ; z)was finally obtained by Bostan and Kauers [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF], using computer algebra techniques.

In summary, the only existing proofs for Problems (A) and (B) used heavy computer calculations in a crucial way. In this article we obtain a new explicit expression for Q(x, y ; z), from which we derive the first "human proofs" of (A) and (B).

Context of Gessel's conjecture. In 2001, the motivation for considering Gessel's model of walks was twofold. First, by an obvious linear transformation, Gessel's walk can be viewed as the simple walk (i.e., with allowed steps to the West, East, South and North) constrained to lie in a cone with angle 135 • , see Figure 1. It turns out that before 2001, the simple walk was well studied in different cones. Pólya [START_REF] Pólya | Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz[END_REF] first considered the simple walk in the whole plane ("drunkard's walk"), and remarked that the probability that a simple random walk ever returns to the origin is equal to 1. This is a consequence of the fact that there are exactly is the Catalan number [START_REF] Arquès | Dénombrements de chemins dans R 2 soumis à contraintes[END_REF]. Gouyou-Beauchamps [START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF] found a similar formula C n C n+2 -C 2 n+1 for the number of simple excursions of length 2n in the cone with angle 45 • (the first octant). It was thus natural to consider the cone with angle 135 • , and this is what Gessel did.

The second part of the motivation is that Gessel's model is a particular instance of walks in the quarter plane. In 2001 there were already several famous examples of such models: Kreweras' walk [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF][START_REF] Flatto | Two parallel queues created by arrivals with two demands[END_REF][START_REF] Flatto | Two parallel queues created by arrivals with two demands[END_REF][START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF] (with allowed steps to the West, North-East and South) for which the GF (2) is algebraic; Gouyou-Beauchamps's walk [START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF]; the simple walk [START_REF] Guy | Lattice paths, reflections and dimension-changing bijections[END_REF]. 1 The function Q(x, y ; z) is called D-finite if the vector space over Q(x, y , z)-the field of rational functions in the three variables x, y , z-spanned by the set of all partial derivatives of Q(x, y ; z) is finite-dimensional, see for instance [START_REF] Lipshitz | D-finite power series[END_REF].

Further, around 2000, walks in the quarter plane were brought up to date, notably by Bousquet-Mélou and Petkovšek [START_REF] Bousquet-Mélou | Linear recurrences with constant coefficients: the multivariate case[END_REF][START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF]. Indeed, they were used to illustrate the following phenomenon: although the numbers of walks satisfy a (multivariate) linear recurrence with constant coefficients, their GF (2) might be non-D-finite; see [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF] for the example of the knight walk.

Existing results in the literature. After 2001, many approaches appeared for the treatment of walks in the quarter plane. Bousquet-Mélou and Mishna initiated a systematic study of such walks with small steps (this means that the step set, i.e., the set of allowed steps for the walk, is a subset of the set of the eight nearest neighbors). Mishna [START_REF] Mishna | Classifying lattice walks restricted to the quarter plane[END_REF][START_REF] Mishna | Classifying lattice walks restricted to the quarter plane[END_REF] first considered the case of step sets of cardinality three. She presented a complete classification of the GF (2) of these walks with respect to the classes of algebraic, transcendental D-finite and non-D-finite power series. Bousquet-Mélou and Mishna [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] then explored all the 79 small step sets 2 . They considered a functional equation for the GF that counts walks in such a model leading to a group 3 of birational transformations of C 2 . In 23 cases out of 79 this group turns out to be finite, and the corresponding functional equations were solved in 22 out of 23 cases (the finiteness of the group being a crucial feature in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]). The remaining case was precisely Gessel's. In 2008, a method using computer algebra techniques was proposed by Kauers, Koutschan and Zeilberger [START_REF] Kauers | The quasi-holonomic ansatz and restricted lattice walks[END_REF][START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF]. Kauers and Zeilberger [START_REF] Kauers | The quasi-holonomic ansatz and restricted lattice walks[END_REF] first obtained a computeraided proof of the algebraicity of the GF counting Kreweras' walks. A few months later, this approach was enhanced to cover Gessel's case, and the conjecture (Problem (A)) was proved [START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF]. At the same time, Bostan and Kauers [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF] showed, again using heavy computer calculations, that the complete GF counting Gessel walks is algebraic (Problem (B)). Using the minimal polynomials obtained by Bostan and Kauers, van Hoeij [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]Appendix] managed to obtain an explicit and compact expression for the complete GF of Gessel walks.

Since the computerized proofs [START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF][START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF], several computer-free analyses of the GF of Gessel walks have been proposed [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF][START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF][START_REF] Ayyer | Towards a human proof of Gessel's conjecture[END_REF][START_REF] Petkovšek | On a conjecture of Ira Gessel[END_REF][START_REF] Sun | Proof of two conjectures of Petkovšek and Wilf on Gessel walks[END_REF][START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF], but none of them solved Gessel's conjecture (Problem (A)), nor proved the algebraicity of the complete GF (Problem (B)). We briefly review the contributions of these works. Kurkova and Raschel [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF] obtained an explicit integral representation (a Cauchy integral) for Q(x, y ; z). This was done by solving a boundary value problem, a method inspired by the book [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]. It can be deduced from [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF] that the generating function ( 2) is D-finite, since the Cauchy integral of an algebraic function is D-finite [START_REF] Picard | Sur les périodes des intégrales doubles et sur une classe d'équations différentielles linéaires[END_REF][START_REF] Roytvarf | Analytic continuation of Cauchy-type integrals[END_REF]. This partially solves Problem (B). Nevertheless, the representation of [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF] seems to be hardly accessible for further analyses, such as for expressing the coefficients q(i, j; n) in any satisfactory manner, and in particular for providing a proof of Gessel's conjecture. This approach has been generalized subsequently for all models of walks with small steps in the quarter plane, see [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF]. In [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF], Fayolle and Raschel gave a proof of the algebraicity of the bivariate GF (partially solving Problem (B)), using probabilistic and algebraic methods initiated in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Ch. 4]: more specifically, they proved that for any fixed value z 0 ∈ (0, 1/4), the bivariate generating function Q(x, y ; z 0 ) for Gessel walks is algebraic over R(x, y ), hence over Q(x, y ). The same approach gives the nature of the bivariate GF in all the other 22 models with finite group. It is not possible to deduce Gessel's conjecture using the approach in [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF], since it only uses the structure of the solutions of the functional equation (3) satisfied by the generating function ( 2), but does not give access to any explicit expression. Ayyer [START_REF] Ayyer | Towards a human proof of Gessel's conjecture[END_REF] proposed a combinatorial approach inspired by representation theory. He interpreted Gessel walks as words on certain alphabets. He then reformulated q(i , j; n) as numbers of words, and expressed very particular numbers of Gessel walks. Petkovšek and Wilf [START_REF] Petkovšek | On a conjecture of Ira Gessel[END_REF] stated new conjectures, closely related to Gessel's. They found an expression for Gessel's numbers in terms of determinants of matrices, by showing that the numbers of walks are solution to an infinite system of equations. Ping [START_REF] Sun | Proof of two conjectures of Petkovšek and Wilf on Gessel walks[END_REF] introduced a probabilistic model for Gessel walks, and reduced the computation of q(i , j; n) to the computation of a certain probability. Using then probabilistic methods (such as the reflection principle) he proved two conjectures made by Petkovšek and Wilf in [START_REF] Petkovšek | On a conjecture of Ira Gessel[END_REF]. Very recently, using the Mittag-Leffler theorem in a constructive way, Kurkova and Raschel [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF] obtained new series expressions for the GFs of all models of walks with small steps in the quarter plane, and worked out in detail the case of Kreweras' walks. The present article is strongly influenced by [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF] and can be seen as a natural prolongation of it.

Presentation of our method and organization of the article. We fix z ∈ (0, 1/4). To solve Problems (A) and (B), we start from the GFs Q(x, 0; z) and Q(0, y ; z) and from the functional equation (see e.g. [7, §4.1])

K(x, y ; z)Q(x, y ; z) = K(x, 0; z)Q(x, 0; z) + K(0, y ; z)Q(0, y ; z) -K(0, 0; z)Q(0, 0; z) -xy , ∀|x|, |y | < 1. (3)
Above, K(x, y ; z) is the kernel of the walk, given by

K(x, y ; z) = xy z   (i,j)∈G x i y j -1/z   = xy z(xy + x + 1/x + 1/(xy ) -1/z), (4)
where G = {(1, 1), (1, 0), (-1, 0), (-1, -1)} denotes Gessel's step set (Figure 1). Rather than deriving an expression directly for the GFs Q(x, 0; z) and Q(0, y ; z), we shall (equivalently) obtain expressions for Q(x(ω), 0; z) and Q(0, y (ω); z) for all ω ∈ C ω , where C ω denotes the complex plane, and where the functions x(ω) and y (ω) arise for reasons that we now present. This idea of introducing the ω-variable might appear unnecessarily complicated; in fact it is very natural, in the sense that many technical aspects of the reasonings will appear simple on the complex plane C ω (in particular, the group of the walk, the continuation of the GFs, their regularity, their explicit expressions, etc.).

We shall see in Section 2 that the elliptic curve defined by the zeros of the kernel

T z = {(x, y ) ∈ (C ∪ {∞}) 2 : K(x, y ; z) = 0} (5)
is of genus 1. This is a torus (constructed from two complex spheres properly glued together), or, equivalently, a parallelogram ω 1 [0, 1] + ω 2 [0, 1] whose opposite edges are identified. It can be parametrized by where the complex number ω 1 ∈ i R and the real number ω 2 ∈ R are given in [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF], and the functions x(ω), y (ω) are made explicit in [START_REF] Flajolet | Analytic combinatorics[END_REF] in terms of the Weierstrass elliptic function ℘ with periods ω 1 , ω 2 . By construction, K(x(ω), y (ω); z) is identically zero.

T z = {(x(ω), y (ω)) : ω ∈ C/(ω 1 Z + ω 2 Z)}, (6)
• • • • • • • -ω 2 0 ω 1 -ω 1 2ω 1 ω 2 2ω 2 • • • 0 ω 1 ω 2 E ' 7ω 2 /8 > ω 3 ∆ x ∆ y
Equation [START_REF] Flajolet | Analytic combinatorics[END_REF] and the periodicity of ℘ imply that the functions x(ω) and y (ω) are elliptic functions on C ω with periods ω 1 , ω 2 . The complex plane C ω can thus be considered as the universal covering of T z and can be viewed as the union ∪ n,m∈Z {ω 1 [n, n + 1) + ω 2 [m, m + 1)} of infinitely many parallelograms, with the natural projection C ω → C/(ω 1 Z + ω 2 Z) (see Figure 2). Our first aim is to lift on it the unknown functions Q(x, 0; z) and Q(0, y ; z), initially defined on their respective unit disk.

The domain of ω 1 [0, 1) + ω 2 [0, 1) where |x(ω)| < 1 is delimited by two vertical lines (see Figure 2). Due to the ellipticity of x(ω), the corresponding domain {ω ∈ C ω : |x(ω)| < 1} on the universal covering C ω consists of infinitely many vertical strips. One of them, denoted by ∆ x , belongs to the strip i R + ω 2 [0, 1); the other ones are its shifts by multiples of ω 2 > 0.

Next, we lift Q(x, 0; z) to the strip ∆ x ⊂ C ω putting Q(x(ω), 0; z) = Q(x, 0; z) for any ω ∈ ∆ x such that x(ω) = x. This defines an analytic and ω 1 -periodic-but yet unknownfunction. In the same way, Q(0, y ; z) is lifted to the corresponding strip ∆ y on C ω . The intersection ∆ x ∩∆ y is a non-empty strip (Figure 2), where both functions are analytic. Since K(x(ω), y (ω); z) = 0, it follows from the main equation (3) that K(x(ω), 0; z)Q(x(ω), 0; z)+K(0, y (ω); z)Q(0, y (ω); z)-K(0, 0; z)Q(0, 0; z)-x(ω)y (ω)=0

for any ω ∈ ∆ x ∩ ∆ y .
This equation allows to continue Q(x(ω), 0; z) to ∆ y and Q(0, y (ω); z) to ∆ x , so that both functions become meromorphic and ω 1 -periodic on the strip ∆ = ∆ x ∪ ∆ y .

The crucial point of our approach is the following: letting r x (ω) = K(x(ω), 0; z)Q(x(ω), 0; z), we have the key-identity

r x (ω -ω 3 ) = r x (ω) + f x (ω), ∀ω ∈ C ω , (7)
where the shift vector ω 3 = 3ω 2 /4 (real positive) and the function f x are explicit (and relatively simple, see ( 14) and ( 23)). Equation ( 7) has many useful consequences:

(I) Due to (a repeated use of) [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], the function r x (ω) can be meromorphically continued from its initial domain of definition ∆ to the whole plane

C ω = n∈Z {∆ + nω 3 }, (8)
see Section 2. By projecting back on C x , we shall recover all branches of Q(x, 0; z). (II) We shall apply four times [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] and prove the identity f x (ω) + f x (ω + ω 3 ) + f x (ω + 2ω 3 )+f x (ω +3ω 3 ) = 0 (as we remark in Section 3, it exactly corresponds to the fact that the orbit sum of Gessel's walks is zero, which was noticed in [7, Section 4.2]), from where we shall derive that r x is elliptic with periods (ω 1 , 4ω 3 ), see Section 3. (III) Since by (15) 4ω 3 = 3ω 2 (which is a non-trivial fact, and means that the group-to be defined in Section 2-of Gessel's model has order 8), the theory of transformations of elliptic functions will imply that r x is algebraic in the Weierstrass function ℘ with periods ω 1 , ω 2 . This will eventually yield the algebraicity of the GF Q(x, 0; z). Using a similar result for Q(0, y ; z) and the functional equation (3), we shall derive in this way the solution to Problem (B), see Section 5. (IV) From [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] we shall also find the poles of r x and the principal parts at them. In general, it is clearly impossible to deduce the expression of a function from the knowledge of its poles. A notable exception is constituted by elliptic functions, which is the case of the function r x for Gessel walks, see (II) above. From this fact we shall deduce an explicit expression of r x in terms of elliptic ζ-functions. By projection on C x , this will give a new explicit expression of Q(x, 0; z) for Gessel walks as an infinite series.

An analogous result will hold for Q(0, y ; z), and (3) will then lead to a new explicit expression for Q(x, y ; z), see Section 3. This part of the article is inspired by [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF]. However, it does not rely on results from [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF], and it is more elementary. (V) Evaluating the so-obtained expression of Q(x, 0; z) at x = 0 and performing further simplifications (based on several identities involving special functions [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF], and on the theory of the Darboux coverings for tetrahedral hypergeometric equations [START_REF] Vidūnas | Transformations of algebraic Gauss hypergeometric functions[END_REF]), we shall obtain the solution of Problem (A), and, in this way, the first human proof of Gessel's conjecture, see Section 4.

Meromorphic continuation of the generating functions

Roadmap. The aim of Section 2 is to prove equation [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], which, as we have seen just above, is the fundamental starting tool for our analysis. In passing, we shall also introduce some useful tools for the next sections. Though crucial, this section does not contain any new result. We thus choose to state the results and to give some intuition, without proof, and we refer to [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] and to [24, Section 2] for full details. We first properly define the Riemann surface T z in ( 5), then we connect it to elliptic functions (in particular, we obtain the expressions of the functions x(ω) and y (ω) in terms of the Weierstrass elliptic function ℘). We next introduce the universal covering of T z (the plane C ω ) and the group of the walk. We lift the GFs to the universal covering (this allows us to define the function r x (ω) in ( 7)). Finally we show how to meromorphically continue r x (ω), and we prove the key-equation [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF].

For brevity, we drop the variable z (which is kept fixed in (0, 1/4)) from the notation when no ambiguity arises, writing for instance Q(x, y ) instead of Q(x, y ; z) and T instead of T z . In Appendix A, we gather together a few useful results on the Weierstrass functions ℘(z) and ζ(z).

Branch points and Riemann surface T. The kernel K(x, y ) defined in ( 4) is a quadratic polynomial with respect to both variables x and y . The algebraic function X(y ) defined by K(X(y ), y ) = 0 has thus two branches, and four branch points that we call y i , i ∈ {1, . . . , 4}4 . They are the roots of the discriminant with respect to x of the polynomial K(x, y ):

d(y ) = (-y ) 2 -4z 2 (y 2 + y )(y + 1).
We have y 1 = 0, y 4 = ∞ = 1/y 1 , and

y 2 = 1 -8z 2 - √ 1 -16z 2 8z 2 , y 3 = 1 -8z 2 + √ 1 -16z 2 8z 2 = 1/y 2 ,
so that y 1 < y 2 < y 3 < y 4 . Since there are four distinct branch points, the Riemann surface of X(y ), which has the same construction as the Riemann surface of the algebraic function

d(y ) = -4z 2 (y -y 1 )(y -y 2 )(y -y 3 ), (9)
is a torus T y (i.e., a Riemann surface of genus 1). We refer to [18, Section 4.9] for the construction of the Riemann surface of the square root of a polynomial, and to [23, Section 2] for this same construction in the context of models of walks in the quarter plane.

The analogous statement holds for the algebraic function Y (x) defined by K(x, Y (x)) = 0. Its four branch points x i , i ∈ {1, . . . , 4}, are the roots of

d(x) = (zx 2 -x + z) 2 -4z 2 x 2 . ( 10
)
They are all real, and numbered so that x 1 < x 2 < x 3 < x 4 :

x 1 = 1 + 2z - √ 1 + 4z 2z , x 2 = 1 -2z - √ 1 -4z 2z , x 3 = 1/x 2 , x 4 = 1/x 1 .
The Riemann surface of Y (x) is also a torus T x . Since T x and T y are conformally equivalent (there are two different views of the same surface), in the remainder of our work we shall consider a single Riemann surface T with two different coverings x : T → C x and y : T → C y ; see Figure 3.

Connection with elliptic functions. The torus T, like any compact Riemann surface of genus 1, is isomorphic to a quotient space C/(ω 1 Z+ω 2 Z), where ω 1 , ω 2 are complex numbers linearly independent on R, see [START_REF] Jones | Complex Functions[END_REF]. This set can obviously be thought as the (fundamental) parallelogram [0, ω 1 ] + [0, ω 2 ], whose opposed edges are identified (here, all parallelograms

C ω [r x (ω)] [r y (ω)] c T z [Q(x(s), 0)] [Q(0, y (s))] d d d d © x(s) y (s) λ(ω) C x C y [Q(x, 0)] [Q(0, y )] Figure 3. The GF Q(x, 0
) is defined on (a subdomain of) the complex plane C x . It will be lifted on the Riemann surface T as s → Q(x(s), 0), and on the universal covering C ω as r x (ω) = K(x(ω), 0)Q(x(ω), 0). The same holds for Q(0, y ). We have also represented the projections between the different levels.

will be rectangles). The periods ω 1 , ω 2 are unique (up to a unimodular transform) and are found in [10, Lemma 3.3.2]5 :

ω 1 = i x 2 x 1 dx -d(x) , ω 2 = x 3 x 2 dx d(x) . (11)
The expression of the periods above cannot be considerably simplified, but could be written in terms of elliptic integrals, see e. The algebraic curve defined by the kernel K(x, y ) can be parametrized using the following uniformization formulae, in terms of the Weierstrass elliptic function ℘ with periods ω 1 , ω 2 (whose expansion is given in equation ( 53)):

       x(ω) = x 4 + d (x 4 ) ℘(ω) -d (x 4 )/6 , y (ω) = 1 2a(x(ω)) -b(x(ω)) + d (x 4 )℘ (ω) 2(℘(ω) -d (x 4 )/6) 2 . ( 12
)
Here a(x) = z x 2 and b(x) = z x 2 -x + z are the coefficients of K(x, y ) = a(x)y 2 + b(x)y + c(x), and d(x) is defined in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF] [START_REF] Flajolet | Analytic combinatorics[END_REF], the functions x(ω), y (ω) are elliptic functions on the whole C with periods ω 1 , ω 2 . By construction

as d(x) = b(x) 2 -4a(x)c(x). Due to
K(x(ω), y (ω)) = 0, ∀ω ∈ C. (13)
We shall not prove equation ( 12) here (we refer to [10, Lemma 3.3.1] for details). Let us simply point out that it corresponds to the rewriting of K(x, y

) = 0 as (2a(x)y + b(x)) 2 = d(x), then as w 2 = z 2 (x -x 1 )(x -x 2 )(x -x 3 )(x -x 4 )
, and finally as the classical identity involving elliptic functions (℘ )

2 = 4℘ 3 -g 2 ℘ -g 3 = 4(℘ -e 1 )(℘ -e 2 )(℘ -e 3 ).
Universal covering. The universal covering of T has the form (C, λ), where C is the complex plane that can be viewed as the union of infinitely many parallelograms

Π m,n = ω 1 [m, m + 1) + ω 2 [n, n + 1), m, n ∈ Z,
which are glued together and λ : C → T is a non-branching covering map (Figure 3). This is a standard fact on Riemann surfaces, see, e.g., [START_REF] Jones | Complex Functions[END_REF]Section 4.19]. For any ω ∈ C such that λω = s ∈ T, we have x(ω) = x(s) and y (ω) = y (s). The expression of λω is very simple: it equals the unique s in the rectangle [0, ω 1 ) + [0, ω 2 ) such that ω = s + mω 1 + nω 2 with some m, n ∈ Z. Furthermore, since each parallelogram Π m,n represents a torus T composed of two complex spheres, the function x(ω) (resp. y (ω)) takes each value of C ∪ {∞} twice within this parallelogram, except for the branch points x i , i ∈ {1, . . . , 4} (resp. y i , i ∈ {1, . . . , 4}). The points ω x i ∈ Π 0,0 such that x(ω x i ) = x i , i ∈ {1, . . . , 4}, are represented in Figure 4. They are equal to

ω x 1 = ω 2 /2, ω x 2 = (ω 1 + ω 2 )/2, ω x 3 = ω 1 /2, ω x 4 = 0.
The points ω y i such that y (ω y i ) = y i are just the shifts of ω x i by a real vector ω 3 /2 (to be defined below, in equation ( 14)): ω y i = ω x i + ω 3 /2 for i ∈ {1, . . . , 4}, see also Figure 4. We refer to [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Chapter 3] and to [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] for proofs of these facts. The vector ω 3 is defined as in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Lemma 3.3.3]:

ω 3 = x 1 -∞ dx d(x) . (14)
For Gessel's model we have the following relation [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Proposition 14], which holds for all z ∈ (0, 1/4):

ω 3 /ω 2 = 3/4. (15)
The identity above contains a lot of informations: it turns out that for any model of walks in the quarter plane, the quantity ω 3 /ω 2 is a rational number (independent of z) if and only if a certain group (to be defined in the next section) is finite, see [ Galois automorphisms and group of the walk. It is easy to see that the birational transformations ξ and η of C 2 defined by

ξ(x, y ) = x, 1 x 2 y , η(x, y ) = 1 xy , y (16)
leave invariant the quantity (i,j)∈G x i y j (and therefore also the set T in (5) for any fixed z ∈ (0, 1/4)). They span a group ξ, η of birational transformations of C 2 , which is a dihedral group, since

ξ 2 = η 2 = id. ( 17
)
It is of order 8, see [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. This group was first defined in a probabilistic context by Malyshev [START_REF] Malyshev | Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms[END_REF][START_REF] Malyshev | Positive random walks and Galois theory[END_REF][START_REF] Malyshev | An analytical method in the theory of two-dimensional positive random walks[END_REF]; it was introduced for the combinatorics of walks with small steps in the quarter plane by Bousquet-Mélou [START_REF] Bousquet-Mélou | Walks in the quarter plane: a functional equation approach[END_REF][START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF], and more systematically by Bousquet-Mélou and Mishna [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. In [START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF], it is defined as a group on C 2 = C x × C y , i.e., at the bottom level of Figure 3. We now lift it

• • • • • • • • ω x 4 ω y 4 ω x 1 ω y 1 ω x 3 ω y 3 ω x 2 ω y 2 E ' ω 3 /2 E ' ω 3 /2 E ' ω 2 T c ω 1 ω 3 /2 E ' ∆ x ∆ y Figure 4
. The fundamental parallelograms for the functions r x (ω) and r y (ω), namely,

Π 0,0 = ω 1 [0, 1) + ω 2 [0, 1) (in grey) and Π 0,0 + ω 3 /2 = ω 1 [0, 1) + ω 2 [0, 1) + ω 3 /2
, and some important points and domains on them.

to the upper levels of Figure 3, that is, to T z and C ω . Our final objective is to demonstrate the following result:

ξω = -ω + ω 1 + ω 2 , ηω = -ω + ω 1 + ω 2 + ω 3 , ∀ω ∈ C. ( 18
)
This equation illustrates the fact that the universal covering is a natural object: while the expressions of the elements of the group were rather complicated in [START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF], they are now just affine functions.

Proof of Equation [START_REF] Jones | Complex Functions[END_REF]. First, we lift the elements of the group to the intermediate level T as the restriction of ξ, η on T. Namely, any point s ∈ T admits the two "coordinates" (x(s), y (s)), which satisfy K(x(s), y (s)) = 0 by construction. For any s ∈ T, there exists a unique s (resp. s ) such that x(s ) = x(s) (resp. y (s ) = y (s)). The values x(s), x(s ) (resp. y (s), y (s )) are the two roots of the second degree equation K(x, y (s)) = 0 (resp. K(x(s), y ) = 0) in x (resp. y ). The automorphism ξ : T → T (resp. η : T → T) is defined by the identity ξs = s (resp. ηs = s ) and is called a Galois automorphism, following the terminology of [START_REF] Malyshev | Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms[END_REF][START_REF] Malyshev | Positive random walks and Galois theory[END_REF][START_REF] Malyshev | An analytical method in the theory of two-dimensional positive random walks[END_REF][START_REF] Fayolle | Random walks in the quarter-plane[END_REF]. Clearly by ( 16) and ( 17), we have, for any s ∈ T,

x(ξs) = x(s), y (ξs) = 1 x 2 (s)y (s) , x(ηs) = 1 y (s)x(s) , y (ηs) = y (s), ξ 2 (s) = η 2 (s) = s.
Finally ξs = s (resp. ηs = s) if and only if x(s) = x i , i ∈ {1, . . . , 4} (resp. y (s) = y i , for some i ∈ {1, . . . , 4}).

There are many ways to lift ξ and η from T to the universal covering C. For any of them ξ(ω x i ) = ω x i + nω 1 + mω 2 , η(ω y i ) = ω y i + kω 1 + lω 2 for some n, m, k, l ∈ Z. There should also exist constants p, q, r, s ∈ Z such that ξ 2 = id + pω 1 + qω 2 and η 2 = id + r ω 1 + sω 2 .

We follow the way of [START_REF] Fayolle | Random walks in the quarter-plane[END_REF] and [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF], lifting them on C in such a way that ω x 2 and ω y 2 are their fixed points, respectively (see Figure 4). It follows immediately that p, q, r, s = 0. Since any automorphism of C ω has the form αω + β with α, β ∈ C, the relations ξ 2 = id and ξ(ω x 2 ) = ω x 2 (resp. η 2 = id and η(ω y 2 ) = ω y 2 ), lead to α = -1 and β = 2ω x 2 (resp. α = -1 and β = 2ω y 2 ). We obtain equation [START_REF] Jones | Complex Functions[END_REF], recalling that ω 1 + ω 2 = 2ω x 2 and that ω 1 + ω 2 + ω 3 = 2ω y 2 . The proof of equation ( 18) is thus completed.

By construction the elements of the group satisfy

x(ξω) = x(ω), y (ηω) = y (ω), ∀ω ∈ C.
Finally, by ( 18)

ηξω = ω + ω 3 , ξηω = ω -ω 3 , ∀ω ∈ C. ( 19
)
Lifting of the GFs on the universal covering. The functions Q(x, 0) and Q(0, y ) can be lifted on their respective natural domains of definition on T and next on the corresponding domains of the universal covering C,

namely {ω ∈ C : |x(ω)| < 1} and {ω ∈ C : |y (ω)| < 1}.
This lifting procedure is illustrated in Figure 3. The first level (at the bottom) represents the complex planes C x and C y , where Q(x, 0) and Q(0, y ) are defined in {|x| < 1} and {|y | < 1}. The second level, where the variables x and y are not independent anymore, is given by T. The third level is C, the universal covering of T. All this construction has been first elaborated by Malyshev [START_REF] Malyshev | Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms[END_REF] for stationary probability GFs of random walks in N 2 , and has been further developed in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF] and in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] in a combinatorial context. The domains

{ω ∈ C : |x(ω)| < 1}, {ω ∈ C : |y (ω)| < 1}
consist of infinitely many curvilinear strips, which differ from translations by multiples of ω 2 . We denote by ∆ x (resp. ∆ y ) the strip that is within ∪ m∈Z Π m,0 (resp. ∪ m∈Z Π m,0 + ω 3 /2).

The domain ∆ x (resp. ∆ y ) is delimited by vertical lines, see [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Proposition 26], and is represented in Figure 4. We notice that the function Q(x(ω), 0) (resp. Q(0, y (ω))) is well defined in ∆ x (resp. ∆ y ), by its expression (2) as a GF. Let us define

r x (ω) = K(x(ω), 0)Q(x(ω), 0), ∀ω ∈ ∆ x , r y (ω) = K(0, y (ω))Q(0, y (ω)), ∀ω ∈ ∆ y . (20)
The domain ∆ x ∩ ∆ y is a non-empty open strip, see Figure 4. It follows from ( 3) and ( 13) that

r x (ω) + r y (ω) -K(0, 0)Q(0, 0) -x(ω)y (ω) = 0, ∀ω ∈ ∆ x ∩ ∆ y . ( 21
)
Meromorphic continuation of the GFs on the universal covering. Let ∆ = ∆ x ∪ ∆ y . Due to [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF], the functions r x (ω) and r y (ω) can be continued as meromorphic functions on the whole domain ∆, by setting

r x (ω) = -r y (ω) + K(0, 0)Q(0, 0) + x(ω)y (ω), ∀ω ∈ ∆ y , r y (ω) = -r x (ω) + K(0, 0)Q(0, 0) + x(ω)y (ω), ∀ω ∈ ∆ x . (22)
To continue the functions from ∆ to the whole complex plane C, we first notice that ∪ n∈Z (∆ + nω 3 ) = C (see [START_REF] Bousquet-Mélou | Linear recurrences with constant coefficients: the multivariate case[END_REF]), as proved in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] and illustrated in Figure 4. Let us define

f x (ω) = y (ω)[x(-ω + ω 1 + ω 2 + ω 3 ) -x(ω)], f y (ω) = x(ω)[y (-ω + ω 1 + ω 2 ) -y (ω)]. (23)
Lemma 1 ( [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]). The functions r x (ω) and r y (ω) can be continued meromorphically to the whole of C. Further, for any ω ∈ C, we have

r x (ω) + r y (ω) -K(0, 0)Q(0, 0) -x(ω)y (ω) = 0, (24)
r x (ω -ω 3 ) = r x (ω) + f x (ω), r y (ω + ω 3 ) = r y (ω) + f y (ω), (25)
r x (ξω) = r x (ω), r y (ηω) = r y (ω), (26)
r x (ω + ω 1 ) = r x (ω), r y (ω + ω 1 ) = r y (ω). ( 27
)
Sketch of the proof. We shall not prove Lemma 1 above in full details (for that we refer to the proof of [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Theorem 4]). However, we give some intuitions on the above identities. First, ( 24) is simply the translation of the functional equation (3). Second, (26) comes from the fact that x(ω) (resp. y (ω)) is invariant by ξ (resp. η). Equation ( 27) follows from the ω 1 -periodicity of the functions x(ω) and y (ω). Let us give some more details for [START_REF] Lipshitz | D-finite power series[END_REF]. Evaluate [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF] at ω and ξω, and make the subtraction of the two identities so obtained. We deduce that r y (ξω) -r y (ω) = x(ω)[y (ξω) -y (ω)]. We conclude by [START_REF] Malyshev | Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms[END_REF], since r y (ξω) = r y (ηξω) = r y (ω + ω 3 ), where the last equality follows from [START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF].

Generating functions in terms of Weierstrass zeta functions

Statements of results. The aim of this section is to prove that the generating function for Gessel walks can be expressed in terms of the Weierstrass zeta function (Theorems 2 and 3 below). To formulate them, we need to recall some notation: let ω 1 , ω 2 be the periods defined in [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF], and let ζ 1,3 be the Weierstrass zeta function with periods ω 1 , 3ω 2 , see Appendix A for its definition and some of its properties. We shall prove the following results:

Theorem 2. For any z ∈ (0, 1/4) we have

Q(0, 0; z) = (28)
ζ 1,3 (ω 2 /4) -3ζ 1,3 (2ω 2 /4) + 2ζ 1,3 (3ω 2 /4) + 3ζ 1,3 (4ω 2 /4) -5ζ 1,3 (5ω 2 /4) + 2ζ 1,3 (6ω 2 /4) 2z 2 .
Theorem 3. We have, for all ω ∈ C,

r y (ω) = c + 1 2z ζ 1,3 (ω -(1/8)ω 2 ) - 1 2z ζ 1,3 (ω -(3/8)ω 2 ) + 1 2z ζ 1,3 (ω -(1 + 3/8)ω 2 ) - 1 2z ζ 1,3 (ω -(1 + 5/8)ω 2 ) - 1 2z ζ 1,3 (ω -(1 + 7/8)ω 2 ) + 1 z ζ 1,3 (ω -(2 + 1/8)ω 2 ) - 1 z ζ 1,3 (ω -(2 + 5/8)ω 2 ) + 1 2z ζ 1,3 (ω -(2 + 7/8)ω 2 ), ( 29
)
where c is a constant (depending only on z).

Note that the constant c in the statement of Theorem 3 can be made explicit. In fact, the point ω y 0 = 7ω 2 /8 ∈ ∆ y is such that y (ω y 0 ) = 0 (see Lemma 5 below). Hence the value of r y (7ω 2 /8) = K(0, y (7ω 2 /8))Q(0, y (7ω 2 /8)) is equal to K(0, 0)Q(0, 0) = z Q(0, 0) which is given by Theorem 2. Thus c is equal to z Q(0, 0) -ζ 1,3 (7ω 2 /8), where ζ 1,3 (ω) is the sum of the eight ζ-functions in ( 29). An expression similar to (29) holds for r x (ω) (for a different constant c). There are two ways to obtain this expression: the first one consists in doing the same analysis as for r y ; the second one is to express r x from equation [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF] in terms of r y and to apply Theorems 2 and 3. In terms of ζ-functions, the results of both approaches are rigorously the same.

Theorems 2 and 3 are crucial for the remainder of the article. We shall explain in Section 4 how to deduce from Theorem 2 a proof of Gessel's conjecture (Problem (A)). Then, in Section 5, we deduce from Theorem 3 the algebraicity of Q(0, y ; z) and Q(x, 0; z). Using the functional equation (3), we shall then obtain the algebraicity of the complete generating function Q(x, y ; z) (Problem (B)).

Preliminary results. The poles of the function f y defined in equation ( 23) will play a crucial role in our analysis. They are given in the lemma hereafter. Lemma 4. In the fundamental parallelogram ω 1 [0, 1) + ω 2 [0, 1), the function f y has poles at ω 2 /8, 3ω 2 /8, 5ω 2 /8 and 7ω 2 /8. These poles are simple, with residues equal to -1/(2z), 1/(2z), 1/(2z) and -1/(2z), respectively.

Before proving Lemma 4, we recall from [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Lemma 28] the following result, dealing with the zeros and poles of x(ω) and y (ω): Lemma 5 ( [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]). In the fundamental parallelogram ω 1 [0, 1) + ω 2 [0, 1), the only poles of x (of order one) are at ω 2 /8, 7ω 2 /8, and its only zeros (of order one) are at 3ω 2 /8, 5ω 2 /8. The only pole of y (of order two) is at 3ω 2 /8, and its only zero (of order two) is at 7ω 2 /8. Sketch of the proof of Lemma 5. Expressions for x(ω) and y (ω) are written down in [START_REF] Flajolet | Analytic combinatorics[END_REF]. To show that x has a pole of order 1 at ω 2 /8 it is enough to prove that ℘(ω 2 /8) = d (x 4 )/6, see again [START_REF] Flajolet | Analytic combinatorics[END_REF]. Such computations follow from the fact that both quantities are known in terms of the variable z. This is clear for the right-hand side. For ℘(ω 2 /8) we can use ℘(ω 2 /4) = (1 + 4z 2 )/3 (see the proof of Lemma 10) and then the bisection formula (P10). We do not pursue the computations in more details. We would proceed similarly for the other poles and zeros.

Proof of Lemma 4. Using the definition (23) of the function f y (ω) and formulas [START_REF] Flajolet | Analytic combinatorics[END_REF], we derive that

f y (ω) = 1 2z
x (ω) x(ω) .

Indeed, we have

f y (ω) = x(ω)[y (-ω) -y (ω)] = x(ω) 2a(x(ω)) - d (x 4 )℘ (ω) (℘(ω) -d (x 4 )/6) 2 = 1 2z x (ω) x(ω)
.

Above, we have used the identities y (-ω +

ω 1 + ω 2 ) = y (-ω), x(-ω) = -x(ω), ℘ (-ω) = -℘ (ω) and a(x) = z x 2 .
Accordingly, if x(ω) has a simple zero (resp. a simple pole) at ω 0 , then f y (ω) has a simple pole at ω 0 , with residue 1/(2z) (resp. -1/(2z)). Lemma 4 then follows from Lemma 5.

The following lemma will shorten the proof of Theorem 3. Lemma 6. The function r y is elliptic with periods ω 1 , 3ω 2 .

Proof. The function r y is meromorphic and ω 1 -periodic due to [START_REF] Malyshev | Positive random walks and Galois theory[END_REF]. Further, by Lemma 1,

r y (ω + 4ω 3 ) -r y (ω) = f y (ω) + f y (ω + ω 3 ) + f y (ω + 2ω 3 ) + f y (ω + 3ω 3 ), ∀ω ∈ C. ( 30
)
We start by showing that the elliptic function

O(ω) = 3 k=0 f y (ω + kω 3 )
has no poles on C. As O(ω) is (ω 1 , ω 2 )-periodic, it suffices to verify this on the parallelogram [0, ω 1 ) + [0, ω 2 ). Since O(ω) is also ω 3 -periodic (this follows immediately from 4ω 3 = 3ω 2 and the ω 2 -periodicity of f y (ω)), it is enough to check that the poles of f y (ω) are not those of O(ω). The function f y (ω) has four poles in the main parallelogram, at ω 2 /8, 3ω 2 /8, 5ω 2 /8 and 7ω 2 /8 (Lemma 4). Since O(ω) is also ω 2 -ω 3 = ω 2 /4-periodic, it remains to check that ω 2 /8 is a removable singularity. This is an elementary verification using the residues of f y (ω) at its poles, which are given in Lemma 4. Hence, with property (P2) of Lemma 15, O(ω) must be a constant c, so that with (30) r y (ω+4ω 3 ) = r y (ω)+c for all ω ∈ C. In particular, evaluating the previous equality at ω y 2 and ω y 2 -4ω 3 and summing the two identities so obtained gives r y (ω y 2 -4ω 3 )+2c = r y (ω y 2 +4ω 3 ). But in view of (26), r y (ω y 2 -4ω 3 ) = r y (ω y 2 + 4ω 3 ), since ηω = -ω + 2ω y 2 , and then c = 0.

It follows that r y (ω) is also 4ω 3 = 3ω 2 -periodic, and thus elliptic with periods ω 1 , 3ω 2 .

Remark 7. Note that the fact that O(ω) is identically zero also follows from [24, Proposition 10], which gives an easy necessary and sufficient condition for O(ω) to be zero (equivalently, for r x and r y to be elliptic, or for the orbit sum of Bousquet-Mélou and Mishna to be zero): the poles of x(ω) and y (ω) in the fundamental parallelogram should not be poles of O(ω).

In the case of Gessel's walks, by Lemma 5, it is reduced to checking that the points ω 2 /8, 3ω 2 /8 and 7ω 2 /8 are not poles of O(ω). This is immediate by Lemma 4. Finally, Lemma 6 is proved in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Proposition 11] as well, using the representation of O(ω) as the so-called orbit-sum:

O(ω) = 1 k 4 (xy )(ω + kω 3 ) -(xy )(η(ω + kω 3 )) = 1 k 4 (xy )((ηξ) k ω) -(xy )(ξ(ηξ) k-1 ω) = θ∈ ξ,η (-1) θ xy (θ(ω)),
where (-1) θ is the signature of θ, i.e., (-1) θ = (-1) (θ) , where (θ) is the smallest for which we can write θ = θ 1 • • • • • θ , with θ 1 , . . . , θ equal to ξ or η.

Proof of Theorems 2 and 3. In order to prove Theorem 3, we could use [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF]Theorem 6], which gives the poles and the principal parts at these poles of r y in terms of the function f y , for any model of walks with small steps in the quarter plane (and rational ω 2 /ω 3 -which is the case here, see (15)). However, we prefer adopting a simpler and more direct approach, which is based on our key-equation [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. We shall then deduce Theorem 2 from Theorem 3.

Proof of Theorem 3. Since r y is elliptic with periods ω 1 , 3ω 2 (Lemma 6), and since any elliptic function is characterized by its poles in a fundamental parallelogram, it suffices to find the poles of r y in ω 1 [-1/2, 1/2) + ω 2 [1/8, 25/8). We shall consider the decomposition

ω 1 2 [-1, 1) + ω 2 8 [1, 25) = ω 1 2 [-1, 1) + ω 2 8 [5, 9) ∪ ω 1 2 [-1, 1) + ω 2 8 [2, 5) ∪ ω 1 2 [-1, 1) + ω 2 8 [9, 15) ∪ ω 1 2 [-1, 1) + ω 2 8 [15, 21) ∪ ω 1 2 [-1, 1) + ω 2 8 [21, 25) ∪ ω 1 2 [-1, 1) + ω 2 8 [1, 2) , (31)
and we shall study successively the six domains in the right-hand side of [START_REF] Picard | Sur les périodes des intégrales doubles et sur une classe d'équations différentielles linéaires[END_REF]. The function r y cannot have poles in the first domain, since the latter is equal to ∆ y (Figure 4), where r y is defined through its GF, see [START_REF] Kauers | The quasi-holonomic ansatz and restricted lattice walks[END_REF]. In the second domain, r y is defined thanks to r y (ω) = -r x (ω) + K(0, 0)Q(0, 0) + x(ω)y (ω), see [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]. The second domain being included in ∆ x (Figure 4), the function r x has no poles there, and the possible singularities of r y necessarily come from the term x(ω)y (ω). Using Lemma 5, we find only one pole in that domain, namely at 3ω 2 /8, of order 1. To compute its residue we notice that the function x(ω)y (ω) has the same principal part as the function -f y (ω) at 3ω 2 /8 due to the expression [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]: in fact, by Lemma 5, the point 3ω 2 /8 is not a pole of x(ω) and the point -3ω 2 /8 + ω 1 + ω 2 is not a pole of y (ω). By Lemma 4 the point 3ω 2 /8 is a simple pole of -f y with residue -1/(2z), and hence of x(ω)y (ω) as well. We record this information in Table 1 We now consider the third domain. We use the equation

r y (ω + 6ω 2 /8) = r y (ω) + f y (ω), (32)
see [START_REF] Lipshitz | D-finite power series[END_REF] together with (15). Since r y and f y both have a pole at 3ω 2 /8 (see just above for r y and Lemma 4 for f y ), r y has a priori a pole at 9ω 2 /8. The residue is the sum of residues of r y and f y at 3ω 2 /8: -1/(2z) + 1/(2z) = 0, so that the singularity 9ω 1.

For the fourth and the fifth domains, we use exactly the same arguments, namely equation [START_REF] Pólya | Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz[END_REF] and the knowledge of the poles in the previous domains. For the fourth domain ω 1 [-1/2, 1/2) + ω 2 [15/8, 21/8), by [START_REF] Pólya | Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz[END_REF], the poles of r y can arise from 9ω 2 /8 where f y has a pole, and from 11ω 2 /8, 13ω 2 /8 were both r y and f y have poles. Then the residue at 15ω 2 /8 is -1/(2z), the one at 17ω 2 /8 is 1/(2z) + 1/(2z) = 1/z, the residue at 19ω 2 /8 is -1/(2z) + 1/(2z) = 0, so that 19ω 2 /8 is a removable singularity. For the fifth domain ω 1 [-1/2, 1/2) + ω 2 [21/8, 25/8), by [START_REF] Pólya | Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz[END_REF], the poles may come from 15ω 2 /8 and 17ω 2 /8 where both r y and f y have poles. The residue at 21ω 2 /8 is -1/(2z) -1/(2z) = -1/z, the one at 23ω 2 /8 is 1/z -1/(2z) = 1/(2z).

As for the last domain, we can use equation [START_REF] Pólya | Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz[END_REF] under the form r y (ω) = r y (ω + 6ω 2 /8)f y (ω). As already proven, r y has no poles at [7ω 2 /8, ω 2 ), hence, the only poles of r y in this domain are those of -f y . By Lemma 4 this is ω 2 /8 with the residue 1/(2z).

The proof of Table 1 is complete.

To conclude the proof of Theorem 3 we use Property (P6) of Appendix A. This property allows to express r y as a sum of a constant c and of eight ζ-functions (eight because there are eight poles in Table 1), exactly as in equation [START_REF] Mishna | Classifying lattice walks restricted to the quarter plane[END_REF].

Proof of Theorem 2. Equation ( 24) yields r x (ω) = x(ω)y (ω) -r y (ω) + K(0, 0)Q(0, 0). We compute the constant K(0, 0)Q(0, 0) as r y (ω y 0 ) = K(0, y (ω y 0 ))Q(0, y (ω y 0 )), where ω y 0 ∈ ∆ y is such that y (ω y 0 ) = 0. Lemma 5 gives a unique possibility for ω y 0 , namely, ω y 0 = 7ω 2 /8. Hence r x (ω) = x(ω)y (ω)-r y (ω)+r y (7ω 2 /8). Let us substitute ω = 5ω 2 /8 in this equation. The point 5ω 2 /8 is a zero of x(ω) that lies in ∆ x , so that

r x (5ω 2 /8) = K(x(5ω 2 /8), 0)Q(x(5ω 2 /8), 0) = K(0, 0)Q(0, 0) = z Q(0, 0).
This point is not a pole of y (ω), in such a way that x(5ω 2 /8)y (5ω 2 /8) = 0. We obtain

z Q(0, 0) = r y (7ω 2 /8) -r y (5ω 2 /8). (33)
Note in particular that in order to obtain the expression (33) of Q(0, 0), there is no need to know the constant c in Theorem 3. With Theorem 3 and (33), Q(0, 0) can be written as a sum of 16 Weierstrass ζ 1,3 -functions (each of them being evaluated at a rational multiple of ω 2 ). Using the fact that ζ 1,3 is an odd function and using property (P8), we can perform many easy simplifications in [START_REF] Petkovšek | On a conjecture of Ira Gessel[END_REF], and, this way, we obtain [START_REF] Malyshev | An analytical method in the theory of two-dimensional positive random walks[END_REF].

We shall see in Section 5 how to deduce from Theorem 3 the expression of Q(0, y ; z) (and in fact, the expression of all its algebraic branches).

Proof of Gessel's conjecture (Problem (A))

In this section, we shall prove Gessel's formula (1) for the number of Gessel excursions. The starting point is Theorem 2, which expresses the generating function of Gessel excursions as a linear combination of (evaluations at multiples of ω 2 /4 of) the Weierstrass zeta function ζ 1,3 with periods ω 1 , 3ω 2 . The individual terms of this linear combination are (possibly) transcendental functions; our strategy is to group them in a way that brings up a linear combination of algebraic hypergeometric functions, from which Gessel's conjecture follows by telescopic summation.

Roadmap of the proof. More precisely, Gessel's formula ( 1) is equivalent to 6

Q(0, 0; z) = 1 2z 2 2 F 1 - 1 2 , - 1 6 , 2 3 , 16z 2 -1 .
Here, we use the notation 2 F 1 ([a, b], [c], z) for the Gaussian hypergeometric function

2 F 1 ([a, b], [c], z) = ∞ n=0 (a) n • (b) n (c) n z n n! . (34)
In view of Theorem 2, Gessel's conjecture is therefore equivalent to

L 1 -3L 2 + 2L 3 + 3L 4 -5L 5 + 2L 6 = G -1, (35)
where

G = G(z) is the algebraic hypergeometric function 2 F 1 ([-1/2, -1/6], [2/3], 16z 2 ),
and where L k denotes the function ζ 1,3 (kω 2 /4) for 1 k 6. Let us denote by V i,j,k the function

L i + L j -L k . Then, the left-hand side of equality (35) rewrites 4V 1,4,5 -V 2,4,6 -V 1,5,6 -2V 1,2,3 .
To prove [START_REF] Roytvarf | Analytic continuation of Cauchy-type integrals[END_REF], our key argument is encapsulated in the following identities:

V 1,4,5 = (2G + H)/3 -K/2, (36)
V 2,4,6 = (2G + H)/3 -K, (37)
V 1,5,6 = (J + 1)/2, ( 38
) V 1,2,3 = (2G + 2H -J -2K + 1)/4. (39)
Here H, J and K are auxiliary algebraic functions, defined in the following way:

H is the hypergeometric function 2 F 1 ([-1/2, 1/6], [1/3], 16z 2 ), and J stands for (G -K) 2 , where K is equal to z G = 4z 2 2 F 1 ([1/2, 5/6], [5/3], 16z 2 )
. Gessel's conjecture is a consequence of the equalities ( 36)- [START_REF] Watson | A course of modern analysis[END_REF]. Indeed, by summation, these equalities imply that 4V 1,4,5 -V 2,4,6 -V 1,5,6 -2V 1,2,3 is equal to G -1, proving [START_REF] Roytvarf | Analytic continuation of Cauchy-type integrals[END_REF].

It then remains to prove equalities (36)- [START_REF] Watson | A course of modern analysis[END_REF]. To do this, we use the following strategy. Instead of proving the equalities of functions of the variable z, we rather prove that their evaluations at z = (x(x + 1) 3 /(4x + 1) 3 ) 1/2 are equal. This is sufficient, since the map ϕ : x → (x(x + 1) 3 /(4x + 1) 3 ) 1/2 is a diffeomorphism between (0, 1/2) onto (0, 1/4). The choice of this algebraic transformation is inspired by the Darboux covering for tetrahedral hypergeometric equations of the Schwarz type (1/3, 1/3, 2/3) [37, §6.1].

First, we make use of a corollary of the Frobenius-Stickelberger identity (P9) ([39, page 446]), which implies that V i,j,k is equal to the algebraic function T i + T j + T k as soon as k = i + j. Here, T denotes the algebraic function ℘ 1,3 ( ω 2 /4). Second, using classical properties of the Weierstrass functions ℘ and ζ, we explicitly determine T (ϕ(x)) for 1 6, then use them to compute V 1,4,5 , V 2,4,6 , V 1,5,6 and V 1,2,3 evaluated at z = ϕ(x). Finally, equalities (36)-( 39) are proved by checking that they hold when evaluated at z = ϕ(x).

Preliminary results. We shall deal with elliptic functions with different pairs of periods. We shall denote by ζ, ℘ the elliptic functions with periods ω 1 , ω 2 , and by ζ 1,3 , ℘ 1,3 the elliptic functions with periods ω 1 , 3ω 2 , see Appendix A for their definition and properties. Further, we recall that elliptic functions are alternatively characterized by their periods (see equation ( 53)) or by their invariants. The invariants of ℘ are denoted by g 2 , g 3 . They are such that

℘ (ω) 2 = 4℘(ω) 3 -g 2 ℘(ω) -g 3 , ∀ω ∈ C. (40)
We recall from [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Lemma 12] the following result that provides explicit expressions for the invariants g 2 , g 3 .

Lemma 8 ([22]

). We have

g 2 = (4/3)(1 -16z 2 + 16z 4 ), g 3 = -(8/27)(1 -8z 2 )(1 -16z 2 -8z 4 ). (41)
Likewise, we define the invariants g 1,3 2 , g 1,3 3 of ℘ 1,3 . To compute them, it is convenient to first introduce an algebraic function denoted R, which is the unique positive root of

X 4 -2g 2 X 2 + 8g 3 X -g 2 2 /3 = 0. (42)
To prove that (42) has a unique positive root, we need to introduce the discriminant of the fourth-degree polynomial P (X) defined by (42). Since deg P (X) = 4 and since the leading coefficient of P (X) is 1, its discriminant equals the resultant of P (X) and P (X). Some elementary computations give that it equals cz 16 (1-16z 2 ) 2 , where c is a negative constant.

The discriminant is thus negative (for any z ∈ (0, 1/4)). On the other hand, the discriminant can be interpreted as

1 i<j 4 (R i -R j ) 2
, where the R i , i ∈ {1, . . . , 4}, are the roots of P (X). The negative sign of the discriminant implies that P (X) has two complex conjugate roots and two real roots. Further, the product of the roots is clearly negative, see (42), so that one of the two real roots is negative while another one is positive. Using equations ( 41) and (42), we obtain the local expansion R(z) = 2 -16z 2 -48z 4 + O(z 6 ) in the neighborhood of 0.

The algebraic function R will play an important role in determining the algebraic functions T = ℘ 1,3 ( ω 2 /4). To begin with, the next lemma expresses T 4 , as well as the invariants g 1, 3 2 , g 1,3 3 , in terms of R.

Lemma 9. One has

T 4 = ℘ 1,3 (ω 2 ) = R/6,
g 1,3 2 = -g 2 /9 + 10R 2 /27, g 1,3 3 = -35R 3 /729 + 7g 2 R/243 -g 3 /27, where expressions for g 2 and g 3 are given in (41).

Proof. Using the properties (P4) and (P7) from Lemma 15, one can write,

℘(ω) = -4℘ 1,3 (ω 2 ) -℘ 1,3 (ω) + ℘ 1,3 (ω) 2 + ℘ 1,3 (ω 2 ) 2 2(℘ 1,3 (ω) -℘ 1,3 (ω 2 )) 2 , ∀ω ∈ C. (43)
We then make a local expansion at the origin of the both sides of the equation above, using property (P3) from Lemma 15. We obtain

1 ω 2 + g 2 20 ω 2 + g 3 28 ω 4 + O(ω 6 ) = 1 ω 2 + 6℘ 1,3 (ω 2 ) 2 - 9g 1,3 2 20 ω 2 + 10℘ 1,3 (ω 2 ) 3 - 3g 1,3 2 ℘ 1,3 (ω 2 ) 2 - 27g 1,3 3 28 ω 4 + O(ω 6 ).
Identifying the expansions above, we obtain two equations for the three unknowns ℘ 1,3 (ω 2 ), g 1,3 2 and g 1,3 3 (remember that its invariants g 2 and g 3 are known from Lemma 8). We add a third equation by noticing that ℘ 1,3 (ω 2 ) is the only real positive solution to (see, e.g., [22, Proof of Lemma 22])

X 4 - g 1,3 2 2 X 2 -g 1,3 3 X - (g 1, 3
2 ) 2 48 = 0.

We then have a (non-linear) system of three equations with three unknowns. A few easy computations finally lead to the expressions of ℘ 1,3 (ω 2 ), g 1,3 2 and g 1,3 3 of Lemma 9. The next result expresses the algebraic functions T 1 , T 2 , T 3 , T 5 and T 6 in terms of the algebraic function R, and of the invariants g 2 and g 3 (the quantity T 4 has already been found in Lemma 9). Lemma 10. One has the following formulae:

(i) T 1 = ℘ 1,3 (ω 2 /4) is the unique solution of X 3 - R 3 + 1 + 4z 2 3 X 2 + R(1 + 4z 2 ) 9 + R 2 108 + g 2 18 X + 23R 3 2916 - R 2 (1 + 4z 2 ) 108 + g 3 27 - 19Rg 2 972 = 0 (44)
such that in the neighborhood of 0,

T 1 = 1/3 + 4z 2 /3 -4z 6 -56z 8 + O(z 10 ). (ii) T 2 = ℘ 1,3 (2ω 2 /4) is equal to T 2 = R + 1 -8z 2 6 - T 6 2 . ( 45
) (iii) T 3 = ℘ 1,3 (3ω 2 /4
) is the unique solution of (44) such that in the neighborhood of 0,

T 3 = 1/3 -8z 2 /3 -8z 4 -60z 6 + O(z 8 ). (iv) T 5 = ℘ 1,3 (5ω 2 /4
) is the unique solution of (44) such that in the neighborhood of 0,

T 5 = 1/3 -8z 2 /3 -8z 4 -64z 6 + O(z 8 ). (v) T 6 = ℘ 1,3 (6ω 2 /4) is equal to T 6 = R + 1 -8z 2 -3R 2 -4R(1 -8z 2 ) + 4(1 -8z 2 ) 2 -6g 2 9 . (46)
Proof. We first prove that for a given value of ω (and thus for a given value of ℘(ω)), the three solutions of

X 3 - R 3 + ℘(ω) X 2 + R℘(ω) 3 + R 2 108 + g 2 18 X + 23R 3 2916 - ℘(ω)R 2 36 + g 3 27 - 19Rg 2 972 = 0 (47) are {℘ 1,3 (ω), ℘ 1,3 (ω + ω 2 ), ℘ 1,3 (ω + 2ω 2 )}.
By property (P7) we find

℘(ω) = -4℘ 1,3 (ω 2 ) -℘ 1,3 (ω) + ℘ 1,3 (ω) 2 + ℘ 1,3 (ω 2 ) 2 2(℘ 1,3 (ω) -℘ 1,3 (ω 2 )) 2 , ∀ω ∈ C,
where by Lemma 9, one has ℘ 1,3 (ω 2 ) = R/6. Then ℘ 1,3 (ω 2 ) 2 = 4(R/6) 3 -g 1,3 2 R/6 -g 1,3 3 , and following this way, we obtain that ℘ 1,3 (ω) satisfies (47).

We start the proof of the lemma by showing (i). Using [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Lemma 19] one has that ℘(ω 2 /4) = ℘(3ω 2 /4) = (1 + 4z 2 )/3. Then the equation (44) is exactly (47) with ω = ω 2 /4. The three roots of (44) are ℘ 1,3 (ω 2 /4), ℘ 1,3 (5ω 2 /4) and ℘ 1,3 (9ω 2 /4) = ℘ 1,3 (3ω 2 /4). By using standard properties of the Weierstrass function ℘, we see that ℘ 1,3 (ω 2 /4) is the largest of the three quantities (and this for any z ∈ (0, 1/4)). Further, since (47) is a polynomial of degree 3, we can easily find its roots in terms of the variable z. This way, we find that the three solutions admit the expansions

1/3 + 4z 2 /3 -4z 4 -56z 6 + O(z 8 ), 1/3 -8z 2 /3 -8z 4 -60z 6 + O(z 8 ), 1/3 -8z 2 /3 -8z 4 -64z 6 + O(z 8 ).
Accordingly, T 1 = ℘ 1,3 (ω 2 /4) corresponds to the first one, T 3 = ℘ 1,3 (3ω 2 /4) to the second one and T 5 = ℘ 1,3 (5ω 2 /4) to the last one.

We now prove (ii) and (v). Using again [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Lemma 19], one derives that ℘(2ω 2 /4) = (1-8z 2 )/3. The three roots of equation ( 47) with ω = 2ω 2 /4 are ℘ 1,3 (2ω 2 /4), ℘ 1,3 (6ω 2 /4) and ℘ 1,3 (10ω 2 /4). Since ℘ 1,3 (10ω 2 /4) = ℘ 1,3 (2ω 2 /4), (47) with ω = 2ω 2 /4 has a double root (that we call t 1 ) and a simple root (t 2 ). It happens to be simpler to deal now with the derivative of the polynomial in the left-hand side of (47). It is an easy exercise to show that the roots of the derivative of a polynomial of degree 3 with a double root at t 1 and a simple root at t 2 are t 1 and (t 1 + 2t 2 )/3. This way, we obtain expressions for ℘ 1,3 (2ω 2 /4) and (℘ 1,3 (2ω 2 /4) + 2℘ 1,3 (6ω 2 /4))/3, which are equal to

R + 1 -8z 2 ± 3R 2 -4R(1 -8z 2 ) + 4(1 -8z 2 ) 2 -6g 2 9 . (48)
Since ℘ 1,3 (2ω 2 /4) > ℘ 1,3 (6ω 2 /4), the root ℘ 1,3 (2ω 2 /4) corresponds to the sign + in (48). This way we immediately find expressions for ℘ 1,3 (2ω 2 /4) and ℘ 1,3 (6ω 2 /4), and this finishes the proof of the lemma.

Let ϕ : (0, 1/2) → (0, 1/4) be the diffeomorphism defined by ϕ(x) = x(x + 1) 3 /(4x + 1) 3 . The next result derives explicit expressions of T (z) when evaluated at z = ϕ(x).

Lemma 11. Define M(x) = 4x 4 + 28x 3 + 30x 2 + 10x + 1 3(4x + 1) 3 and N(x) = 2x(x + 1)(2x + 1) (4x + 1) 5/2 .
For any x ∈ (0, 1/2), the following formulae hold:

T 1 (ϕ(x)) = M(x) + N(x), T 2 (ϕ(x)) = M(x) - 2x(x + 1)(2x + 1) (4x + 1) 3 , T 3 (ϕ(x)) = M(x) - 2x(x + 1) (4x + 1) 2 , T 4 (ϕ(x)) = M(x) - 2x(2x + 1)(3x + 1) (4x + 1) 3 , T 5 (ϕ(x)) = M(x) -N(x), T 6 (ϕ(x)) = 2x + 1 4x + 1 2 -2M(x).
Proof. All equalities are consequences of Lemma 10. We begin with R: we replace z by ϕ(x) in equation ( 42), factor the result, and identify the corresponding minimal polynomial of R(ϕ(x)) in Q(x)[T ]. To do this, we use that the local expansion of R(ϕ(x)) at x = 0 is equal to 2 -16x + O(x 2 ). The minimal polynomial has degree 1, proving the equality

R (ϕ(x)) = 2(2x 2 -2x -1) 2 (4x + 1) 3 .
From R, we directly deduce T 4 = R/6. Now, replacing z by ϕ(x) in Lemma 10 (v) provides the expression of T 6 (ϕ(x)). Then T 2 is treated in a similar way using Lemma 10 (ii). Finally, an annihilating polynomial for T 1 (ϕ(x)), T 3 (ϕ(x)), T 5 (ϕ(x)) is deduced in a similar manner using Lemma 10 (i). This polynomial in Q(x)[T ] factors as a product of a linear factor and a quadratic factor. Using the local expansions

1/3 + 4/3x -12x 2 + 80x 3 + O(x 4 ), 1/3 - 8/3x + 16x 2 -84x 3 + O(x 4 ) and 1/3 -8/3x + 16x 2 -88x 3 + O(x 4
) allows to conclude.

The following Corollary is a direct consequence of the previous lemma and of the Frobenius-Stickelberger identity (P9).

Corollary 12. The algebraic functions V 1,4,5 , V 2,4,6 , V 1,5,6 and V 1,2,3 defined in (36)-( 39) satisfy the following equalities for any x ∈ (0, 1/2):

V 1,4,5 (ϕ(x)) = 2x 2 + 4x + 1 (4x + 1) 3/2 , V 2,4,6 (ϕ(x)) = 2x + 1 (4x + 1) 3/2 , V 1,5,6 (ϕ(x)) = 2x + 1 4x + 1 , V 1,2,3 (ϕ(x)) = x 4x + 1 + (x + 1)(2x + 1) (4x + 1) 3/2 .
Completing the proof of Gessel's conjecture. The last step consists in proving the four equalities (36)- [START_REF] Watson | A course of modern analysis[END_REF]. The starting point is that the hypergeometric power series

G = 2 F 1 ([-1/2, -1/6], [2/3], 16z 2 ), H = 2 F 1 ([-1/2, 1/6], [1/3], 16z 2 ), K = z • G and J = (G -K) 2
are algebraic and satisfy the equations displayed in the following lemma.

Lemma 13. For any x ∈ (0, 1/2), one has the following formulae:

G (ϕ(x)) = 4x 2 + 8x + 1 (4x + 1) 3/2 , H (ϕ(x)) = 4x 2 + 2x + 1 (4x + 1) 3/2 , K (ϕ(x)) = 4x(x + 1) (4x + 1) 3/2 , J (ϕ(x)) = 1 4x + 1 .
Proof.

2 F 1 ([-1/2, -1/6], [2/3], z) = 2• 2 F 1 ([1/2, -1/6], [2/3], z)+(z -1)• 2 F 1 ([1/2, 5/6], [2/3], z), that we evaluate at z = ψ(x) = 16ϕ(x) 2 . It follows that G(ϕ(x)) = 2 • 2 F 1 ([1/2, -1/6], [2/3], ψ(x)) + (ψ(x) -1) • 2 F 1 ([1/2, 5/6], [2/3], ψ(x)).
function of ℘(ω), and finally by [START_REF] Flajolet | Analytic combinatorics[END_REF], ℘(ω) is algebraic in y (ω). This eventually implies that r y (ω) is algebraic in y (ω), or equivalently that Q(0, y ) is algebraic in y , see [START_REF] Kauers | The quasi-holonomic ansatz and restricted lattice walks[END_REF].

The second proof is based on the meromorphic continuation of the GFs on the universal covering, which was recalled in Section 2. The restrictions of r y (ω)/K(0, y (ω)) to the half parallelogram

D k, = ω 3 /2 + ω 1 [ , + 1) + ω 2 (k/2, (k + 1)/2]
for k, ∈ Z provide all branches of Q(0, y ) on C \ ([y 1 , y 2 ] ∪ [y 3 , y 4 ]) as follows:

Q(0, y ) = {r y (ω)/K(0, y (ω)) : ω is the (unique) element of D k, such that y (ω) = y }, see [23, Section 5.2] for more details. Due to the ω 1 -periodicity of r y (ω) and y (ω) (see [START_REF] Malyshev | Positive random walks and Galois theory[END_REF] and ( 12), respectively), the restrictions of these functions on D k, do not depend on ∈ Z, and therefore determine the same branch as on D k,0 for any . Furthermore, due to equation ( 26), the restrictions of r y (ω)/K(0, y (ω)) on D -k+1,0 and on D k,0 lead to the same branches for any k ∈ Z. Hence, the restrictions of r y (ω)/K(0, y (ω)) on D k,0 with k 1 provide all different branches of this function. In addition, Lemma 6 says that r y is 3ω 2 -periodic. This fact yields that Q(0, y ) has (at most) six branches, and is thus algebraic.

An analogous statement holds for (the restrictions of) the function r x (ω)/K(x(ω), 0) and then for Q(x, 0). Using the functional equation ( 3), we conclude that Q(x, y ) is algebraic in the two variables x, y .

In the next section, we refine the previous statement, and prove that Q(x, y ) is algebraic in x, y , z (Problem (B)).

Proof of the algebraicity of the complete GF. We start by proving the algebraicity of Q(0, y ) as a function of y , z. We consider the representation of r y (ω) given in Theorem 3 and apply eight times the addition theorem (P4) for ζ-functions, namely

We then make the weighted sum of the eight identities above (corresponding to the appropriate values of k in (29)); this way, we obtain

Since the sum of the residues in the formula (29) equals 0, the coefficient in front of ζ 1,3 (ω) is 0, so that U 1 (ω) is identically zero. To prove that U 2 is algebraic in z, it suffices to use similar arguments as we did to prove that Q(0, 0) is algebraic (we group together different ζ-functions and we use standard identities as the Frobenius-Stickelberger equality (P9) or the addition formula for the ζ-function (P4), see Section 4); we do not repeat the arguments here. Finally, we show that U 3 (ω) is algebraic in y (ω) over the field of algebraic functions in z. In other words, we show that there exists a non-zero bivariate polynomial P such that P (U 3 (ω), y (ω)) = 0, where the coefficients of P are algebraic functions in z. This is enough to conclude the algebraicity of Q(0, y ) as a function of y and z.

To prove the latter fact, we shall prove that each term (50) for k as in (49) satisfies the property above (with different polynomials P , of course). First, Lemma 14 below implies that ℘ 1,3 (kω 2 /8) and ℘ 1,3 (kω 2 /8) are both algebraic in z. Further, it follows from (P7) that the function ℘ 1,3 (ω) is algebraic in ℘(ω) over the field of algebraic functions in z. It is thus also algebraic (over the field of algebraic functions in z) in y (ω), thanks to [START_REF] Flajolet | Analytic combinatorics[END_REF]. The same property holds for ℘ 1,3 (ω): this comes from the differential equation (40) satisfied by the Weierstrass elliptic functions.

The proof of the algebraicity of Q(x, 0) as a function of x and z is analogous. With equation (3) the algebraicity of Q(x, y ) as a function of x, y , z is proved.

To conclude this section it remains to prove the following lemma. It is important to notice that it suffices to prove the result for = 0. Indeed, all the invariants g 2 , g 3 , g 1, 3 2 and g 1,3 3 are algebraic functions of z (see Lemmas 8 and 9), so that using inductively the differential equation (40), we obtain the algebraicity for values of 1 from the algebraicity for = 0.

We first consider ℘ = ℘ (0) . It is demonstrated in [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Lemma 19] that ℘(kω 2 /8) is algebraic for k = 2 and k = 4. For k = 1 this follows from the bisection formula (P10) and from the case k = 2 (note that ℘(ω 1 /2), ℘(ω 2 /2) and ℘((ω 1 + ω 2 )/2) are algebraic in z, see [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]Lemma 12]). For k = 3, this is a consequence of the addition formula (P4).

We now deal with ℘ 1,3 . Let k ∈ {1, . . . , 12}. Using (43), we easily derive that ℘ 1,3 (ω 0 ) is algebraic in z as soon as ℘(ω 0 ) is algebraic in z: indeed, in (43) the functions ℘ 1,3 (ω 2 ) and ℘ 1,3 (ω 2 ) are algebraic in z, as a consequence of Lemma 9. This remark applies to all ω 0 = kω 2 /8, except for k = 8, since then ℘(kω 2 /8) = ∞. In fact, for k = 8 the situation is also simple, as ℘ 1,3 (kω 2 /8) = R/6 (see Lemma 9) is already known to be algebraic.

Conclusion

Application of our results to other end points. In this article we have presented the first human proofs of Gessel conjecture (Problem (A)) and of the algebraicity of the complete GF counting Gessel walks (Problem (B)). We have deduced the closed-form expression (1) of the numbers of walks q(0, 0; n) from a new algebraic expression of the GF n 0 q(0, 0; n)z n .

With a very similar analysis, we could obtain an expression for the series n 0 q(i , j; n)z n , for any fixed couple (i , j) ∈ N 2 . Let us illustrate this fact with the example (i , j) = (0, j),

Figure 1 .

 1 Figure1. On the left: allowed steps for Gessel walks. Note that on the boundary of N 2 , the steps that would take the walks out of N 2 are discarded. On the right: an equivalent formulation of Gessel walks as the simple walks evolving in the cone with opening 135 • .

2n n 2

 2 simple excursions of length 2n in the plane Z 2 . There also exist formulae for simple excursions of length 2n evolving in other regions of Z 2 : 2n+1 n C n for the half plane Z × N, and C n C n+1 for the quarter plane N 2 , where C n = 1 n+1 2n n

Figure 2 .

 2 Figure 2. Left: the subdomains of the fundamental parallelogram [0, ω 1 ) + [0, ω 2 ) where |x(ω)| < 1 (blue), |y (ω)| < 1 (red) and |x(ω)|, |y (ω)| < 1 (grey). Right: corresponding domains ∆ x (blue) and ∆ y (red) on the universal covering C ω . The intersection ∆ x ∩ ∆ y is represented in grey. The domain ∆ = ∆ x ∪ ∆ y has length 7ω 2 /8, which is larger than ω 3 = 3ω 2 /4.

  g. [23, Eqs. (7.20)-(7.25)].

ζ 1 , 3 2 ℘ 1 , 3

 13213 (ωkω 2 /8) = ζ 1,3 (ω) -ζ 1,3 (kω 2 /8) + 1 (ω) + ℘ 1,3 (kω 2 /8) ℘ 1,3 (ω) -℘ 1,3 (kω 2 /8) ,for suitable values of k ∈ Z that can be deduced from[START_REF] Mishna | Classifying lattice walks restricted to the quarter plane[END_REF]:k ∈ {1,3, 11, 13, 15, 17, 21, 23}.

r 2 ℘ 1 , 3

 213 y (ω) = U 1 (ω) + U 2 + U 3 (ω),where U 1 (ω) is the weighted sum of the eight functions ζ 1,3 (ω), U 2 is the sum of c and of the weighted sum of the eight quantities -ζ 1,3 (kω 2 /8), and U 3 (ω) is the weighted sum of the eight quantities 1 (ω) + ℘ 1,3 (kω 2 /8) ℘ 1,3 (ω) -℘ 1,3 (kω 2 /8) .

Lemma 14 .

 14 For any k ∈ Z and any ∈ N, ℘ ( ) (kω 2 /8) and ℘ ( ) 1,3 (kω 2 /8) are (infinite or) algebraic functions of z. Proof. First, for any ∈ N and k∈ 8Z (resp. k ∈ 24Z), ℘ ( ) (kω 2 /8) (resp. ℘ ( ) 1,3 (kω 2 /8)) is infinite.For other values of k, they are finite. By periodicity and parity, it is enough to prove the algebraicity for k ∈ {1, . . . , 4} (resp. k ∈ {1, . . . , 12}).

Table 1 .

 1 below. The points of the domain ω

	Point	ω 2 /8	3ω 2 /8 11ω 2 /8 13ω 2 /8 15ω 2 /8 17ω 2 /8 21ω 2 /8 23ω 2 /8
	Residue 1/(2z) -1/(2z) 1/(2z) -1/(2z) -1/(2z)	1/z	-1/z	1/(2z)

1 [-1/2, 1/2) + ω 2 [1/8, 25/8) where the function r y has poles and the residues at these poles

  2 /8 is removable. The point 3ω 2 /8 is the unique pole of r y on ω 1 [-1/2, 1/2) + ω 2 [3/8, 9/8) by the previous analysis. It follows that, except for 9ω 2 /8, the poles of r y on the third domain ω 1 [-1/2, 1/2) + ω 2 [9/8, 15/8) necessarily arise by[START_REF] Pólya | Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz[END_REF] from those of f y on ω 1 [-1/2, 1/2) + ω 2 [3/8, 9/8), that is 5ω 2 /8 and 7ω 2 /8. Lemma 4 thus implies that r y has poles at 11ω 2 /8 and 13ω 2 /8, with respective residues 1/(2z) and -1/(2z). These results are summarized in Table

  The first two equalities are consequences of identities (46)-(49) in[START_REF] Vidūnas | Transformations of algebraic Gauss hypergeometric functions[END_REF] Section 6.1]. Let us prove the first equality. We start with the contiguity relation[START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF] Eq. 15.2.15]

A priori, there are 2 8 = 256 step sets, but the authors of[START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] showed that, after eliminating trivial cases, and also those which can be reduced to walks in a half plane, there remain 79 inherently different models.

By definition, a branch point y i is a point y ∈ C such that the two roots X(y ) are equal.

Note a small misprint in Lemma 3.3.2 in[START_REF] Fayolle | Random walks in the quarter-plane[END_REF], namely a (multiplicative) factor of 2 that should be 1; the same holds for[START_REF] Flatto | Two parallel queues created by arrivals with two demands[END_REF].

Acknowledgments

We thank the two anonymous referees for their useful and insightful comments and suggestions, which led us to improve the presentation of the paper.

Identities (46)-(47) in [START_REF] Vidūnas | Transformations of algebraic Gauss hypergeometric functions[END_REF]Section 6.1] write 2 F 1 ([1/2, -1/6], [2/3], ψ(x)) = (1 + 4x) -1/2 , and 2 F 1 ([1/2, 5/6], [2/3], ψ(x)) = (1 + 4x) 3/2 /(1 -2x) 2 . Therefore, G(ϕ(x)) is equal to

To prove the second equality, we start from Euler's formula [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF]Eq. 15.3.3] 2 F 1 ([-1/2, 1/6], [1/3], z) = (1 -z) 2/3 • 2 F 1 ([5/6, 1/6], [1/3], z) and from the contiguity relation [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF]Eq. 15.2.25] 2 F 1 ([5/6, 1/6], [1/3]

Putting them together, evaluating the result at z = ψ(x) and using identities (48)-( 49) in [START_REF] Vidūnas | Transformations of algebraic Gauss hypergeometric functions[END_REF]Section 6.1] shows that H(ϕ(x)) is equal to

which further simplifies to (4x 2 + 2x + 1)/(4x + 1) 3/2 for x ∈ (0, 1/2).

The last two equalities are easy consequences of the first two. Now, equalities ( 36)-( 39) evaluated at z = ϕ(x) = (x(x + 1) 3 /(4x + 1) 3 ) 1/2 are easily proven using Lemmas 12 and 13. For instance, equality [START_REF] Sun | Proof of two conjectures of Petkovšek and Wilf on Gessel walks[END_REF] evaluated at z = ϕ(x) reads:

Similarly, equality (39) evaluated at z = ϕ(x) reads:

The proof of Gessel's formula [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF] for the number of Gessel excursions is thus completed. Note that incidentally we have proved that the generating series Q(0, 0; z) for Gessel excursions is algebraic. The next section is devoted to the proof that the complete generating series of Gessel walks is also algebraic.

Proof of the algebraicity of the GF (Problem (B))

Branches of the GFs and algebraicity of Q(x, y ) in the variables x, y . In this section we prove a weakened version of Problem (B): we show that Q(x, y ) is algebraic in x, y (we shall prove in the next section that the latter function is algebraic in x, y , z, which is much stronger). This is not necessary for our analysis, but this illustrates that our approach easily yields algebraicity results.

We first propose two proofs of the algebraicity of Q(0, y ) as a function of y . The first proof is an immediate application of property (P5). The sum of the residues (i.e., the multiplicative factors in front of the ζ-functions) in the formula (29) of Theorem 3 is clearly 0, so that r y (ω) is an algebraic function of ℘ 1,3 (ω), by (P5). Further, by (P7), ℘ 1,3 (ω) is an algebraic j 0. Let g j (z) = n 0 q(0, j; 2n)z 2n be the function counting walks ending at the point (0, j) of the vertical axis. We obviously have Q(0, y ) = j 0 y j g j (z).

In particular, up to a constant factor j!, the functions g j (z) are exactly the successive derivatives of Q(0, y ) w.r.t. the variable y evaluated at y = 0. First, g 0 (z) = Q(0, 0). Further, one has r y (ω) = z(y (ω) + 1)Q(0, y (ω)). Differentiating w.r.t. ω and evaluating at ω y 0 (which is such that y (ω y 0 ) = 0), we find

All quantities above can be computed, and a similar analysis as in Section 4 could lead to a closed-form expression for the GF of the numbers of walks q(0, 1; 2n), n 0. Similarly, one could compute g 2 (z), g 3 (z), etc.

New Gessel conjectures. For any j 0, define

With this notation, the closed-form expression (1) for the q(0, 0; 2n) is equivalent to (see [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]15])

On March 2013, Ira Gessel [15] proposed the following new conjectures: for any j 1,

where p j (z) is a polynomial of degree 3j + 2 with positive coefficients (due to (51), these new conjectures generalize the original one). We shall not prove these conjectures in the present article. However, we do think that following the method sketched in the first part of Section 6, it could be possible to prove them, at least for small values of j 0.

Appendix A. Some properties of elliptic functions

In this appendix, we bring together useful results on the Weierstrass functions ℘ and ζ. First, they are defined as follows for all ω ∈ C:

The next lemma displays a collection of useful properties of the functions ℘ and ζ. These properties are very classical; they can be found in [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF][START_REF] Jones | Complex Functions[END_REF][START_REF] Watson | A course of modern analysis[END_REF] (see also the references in [START_REF] Kurkova | New steps in walks with small steps in the quarter plane[END_REF]).

).

(P4) We have the addition theorems, for any ω, ω ∈ C:

The function f above is elliptic if and only if 1 p r = 0. (P6) Let f be an elliptic function with periods ω, ω such that in the fundamental parallelogram [0, ω)+[0, ω), f has only poles of order 1, at ω 1 , . . . , ω p , with residues r 1 , . . . , r p , respectively. Then there exists a constant c such that (55) holds. (P7) Let p be some positive integer. The Weierstrass elliptic function with periods ω, ω/p can be written in terms of ℘ as ℘(ω) +