I Kurkova
email: irina.kourkova@upmc.fr

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

NEW STEPS IN WALKS WITH SMALL STEPS IN THE QUARTER PLANE SERIES EXPRESSIONS FOR THE GENERATING FUNCTIONS

Keywords: 1991 Mathematics Subject Classification. Primary 05A15, Secondary 30F10, 30D05 Walks in the quarter plane, Counting generating function, Holonomy, Group of the walk, Riemann surface, Elliptic functions, Uniformization, Universal covering. 1

In this article we obtain new expressions for the generating functions counting (non-singular) walks with small steps in the quarter plane. Those are given in terms of infinite series, while in the literature, the standard expressions use solutions to boundary value problems. We illustrate our results with three examples (an algebraic case, a transcendental D-finite case, and an infinite group model).

1. Introduction 1.1. Context. In the field of enumerative combinatorics, much progress has been recently made in the study of walks in the quarter plane Z 2 + = {0, 1, . . .} 2 . The general aim is the following: given a set S of allowed steps (or jumps), it is a matter of counting the number of walks constructed from these steps, which start from a given point and end at a given point or subdomain of the quarter plane. Without hypotheses on S, this problem is, still today, out of reach. In this article, following the seminal work of Bousquet-Mélou and Mishna [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], we shall assume that the steps are small: in other words, S ⊂ {-1, 0, 1} 2 \ {(0, 0)}. See Figures 1, 2, 3, 7 and 8 for examples. There are obviously 2 8 = 256 models. But one is easily convinced that some models are trivial; some models are equivalent (by diagonal symmetry) to other ones; and finally, some models are equivalent to models of walks confined in a half-plane, for which the general theory already exists [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF]. It happens that out of the 256 models, only 79 inherently different ones remain to be studied [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. Let q(i, j; n) denote the number of paths in Z 2 + having length n, starting from (0, 0) and ending at (i, j). Define their generating function (GF) as [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF] Q(x, y; z) = i,j,n 0 q(i, j; n)x i y j z n .

There are then three usual key challenges:

(I) Finding an expression for the numbers q(i, j; n), or for Q(x, y; z); (II) Determining the nature of Q(x, y; z): is it holonomic? 1 In that event, is it algebraic, or even rational?

✲ ✻ ✲ ✛ ❄ ✻ ❅ ❅ ■ ✲ ✛ ✻ ❅ ❅ ■ ✲ ❄ ✻ ✲ ✻ Figure 1.
Example of model (with an infinite group) considered in this article (note that on the boundary, the jumps are the natural ones: those that would take the walk out Z 2 + are discarded)

(III) What is the asymptotic behavior, as their length goes to infinity, of the number of walks ending at some given point or domain (for instance one axis)?

The functional equation ( 2) below served as the basis for all previous analyses [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF][START_REF] Fayolle | Random walks in the quarter-plane[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] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF][START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF]. It determines Q(x, y; z) through the boundary functions Q(x, 0; z), Q(0, y; z) and Q(0, 0; z), as follows:

(2) 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, where

K(x, y; z) = xyz[ (i,j)∈S x i y j -1/z] (3)
is called the kernel of the walk. We refer to [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] for the (short and intuitive) proof of Equation [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]. It has been anticipated in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] and confirmed in the articles [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[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] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF][START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] that the analysis of both problems (I) and (II) highlights the notion of the group of the walk, introduced 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]. This is the group (4) ξ, η of birational transformations of (C ∪ {∞}) 2 , which is generated by [START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF] ξ(x, y) = x, 1 y (i,-1)∈S x i (i,+1)∈S x i , η(x, y) = 1 x

(-1,j)∈S y j (+1,j)∈S y j , y .

Each element of ξ, η leaves invariant (i,j)∈S x i y j , the GF of the step set S. Further, ξ 2 = η 2 = id, and ξ, η is a dihedral group of order even and larger than or equal to four. It has been proved in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] that 23 of the 79 walks have a finite group, while the 56 others admit an infinite group. 2 2 Proving that a given model has a finite group is easy: it suffices to compute the group defined in [START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF].

As examples, the models of Figure 2 all have finite groups, of order 4, 6, 8 and 8, respectively. On the other hand, it is much more complicated to prove that a model has an infinite group (examples are proposed in Figures 1 and8). To that purpose, methods are presented in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]; see also [START_REF] Fayolle | Random walks in the quarter-plane[END_REF][START_REF] Fayolle | Random walks in the quarter plane with zero drift: an explicit criterion for the finiteness of the associated group. Markov Process[END_REF].

✲ ✻ ✲ ✛ ❄ ✻ ✲ ✻ ✒ ✛ ❄ ✲ ✻ ✒ ✠ ✲ ✛ ✲ ✻ ✲ ❅ ❅ ■ ✛ ❅ ❅ | Figure 2.
Four famous examples, known as simple, Kreweras', Gessel's and Gouyou-Beauchamps' walks, respectively

✲ ✻ ❅ ❅ | ❅ ❅ ■ ✒ ✲ ✻ ❅ ❅ | ❅ ❅ ■ ✻ ✲ ✻ ❅ ❅ | ❅ ❅ ■ ✒ ✲ ✻ ✲ ✻ ❅ ❅ | ❅ ❅ ■ ✒ ✲ ✻ ❅ ❅ | ❅ ❅ ■ ✒ ✻ Figure 3
. The 5 singular walks studied in [START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF][START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF] 1.2. Existing results in the literature. For 22 of the 23 models with finite group, GFs Q(x, 0; z), Q(0, y; z) and Q(0, 0; z)-and hence Q(x, y; z) by ( 2)-have been computed in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] by means of certain (half-)orbit sums of the functional equation [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]. For the 23rd model with finite group, known as Gessel's walks (see Figure 2), the GFs have been expressed by radicals in [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF] thanks to a guessing-proving method using computer calculations; they were also found in [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF] by solving some boundary value problems. All 23 finite group models admit a holonomic GF: 19 walks turn out to have a holonomic but non-algebraic GF, while for 4 walks (among which Kreweras' and Gessel's models), Q(x, y; z) is algebraic. This was first proved in [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]; see also [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] for alternative proofs. The 5 models with infinite group on Figure 3 are commonly known as singular walks. They are notably distinct from the others, since they have no jumps to the West, South-West and South. These 5 models are studied in detail in [START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF][START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF]; they all have nonholonomic GFs.

At this step, there remain 51 = 79 -23 -5 models. In [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] the problem (I) was resolved for all these 51 models-and in fact for all the 74 non-singular walks. This was done via a unified approach: integral representations were obtained for GFs Q(x, 0; z), Q(0, y; z) and Q(0, 0; z) in certain domains, by solving boundary value problems (of Riemann-Carleman type). However, these complicated explicit expressions have not been helpful for solving problem (II), that is for determining the nature of the GFs for the 51 non-singular walks with infinite group.

This problem has been finally solved in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF], as follows. Since the transformations ξ and η of (C ∪ {∞}) 2 leave (i,j)∈S x i y j invariant, one can consider a group ξ, η |Tz of automorphisms of the elliptic curve [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] T z = {(x, y) ∈ (C ∪ {∞}) 2 : K(x, y; z) = 0} generated by its automorphisms ξ and η. Due to the obvious inclusion T z ⊂ (C ∪ {∞}) 2 , it may happen that the group ξ, η |Tz is finite for some z, while the group ξ, η on (C ∪ {∞}) 2 be infinite. Let [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF] H = {z ∈ (0, 1/|S|) : | ξ, η |Tz | < ∞}.

Clearly H = (0, 1/|S|) for any of the 23 models with finite group ξ, η . The following result was proved in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]: 3

Theorem ( [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]). For all 51 non-singular models with infinite group:

(i)
The subsets H and (0, 1/|S|) \ H are both dense in (0, 1/|S|);

(ii) For all z ∈ H, the GFs x → Q(x, 0; z) and y → Q(0, y; z) are holonomic;

(iii) For all z ∈ (0, 1/|S|) \ H, x → Q(x, 0; z) and y → Q(0, y; z) are non-holonomic.

Assertion (iii) of this theorem combined with usual properties of holonomic functions (see, e.g., [START_REF] Flajolet | Analytic combinatorics[END_REF]Appendix B.4]) implies the non-holonomy of the trivariate GF Q(x, y; z) for all 51 models and therefore proves Bousquet-Mélou's and Mishna's conjecture stated in [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. On the other hand, it seems not possible to deduce from this theorem any information on the holonomy of Q(0, 0; z) or Q(1, 1; z), or more generally of Q(x, y; z) as a function of the variable z. Moreover, it has been remarked in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] that assertion (ii) above suggests a promising start in order to achieve better understanding and easier representations of the GFs, than those in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] mentioned above. This is the subject of the present paper. 1.3. Main results. We analyze the GFs Q(x, 0; z) and Q(0, y; z) for all 74 non-singular models and all z ∈ H.

For any fixed z ∈ (0, 1/|S|), thus in particular for any z ∈ H, the elliptic curve T z is of genus 1. The universal covering C of T z can be considered as a union of an infinite number of parallelograms glued together, see Figure 5, with some periods ω 1 ∈ iR and ω 2 ∈ R, and uniformisation formulas {(x(ω), y(ω)) : ω ∈ C}. The exact expression of these periods (depending on z) is given in [START_REF] Jones | Complex Functions[END_REF], the uniformisation functions x(ω) and y(ω) are written down in [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF] in terms of a ℘-Weierstrass function ℘(ω; ω 1 , ω 2 ) with periods ω 1 and ω 2 .

Rather than deriving an expression directly for the GFs Q(x, 0; z) and Q(0, y; z), we shall obtain Q(x(ω), 0; z) and Q(0, y(ω); z) for all ω ∈ C.

Our main result is an expression for the functions Q(x(ω), 0; z) and Q(0, y(ω); z) as infinite series in ω, each term of the series being a simple rational function in ω. To state it we need to introduce some notation. Define [START_REF] Chabat | Introduction à l'analyse complexe[END_REF] f y (ω) = 1 2z

x ′ (ω)

δ 1,1 x(ω) + δ 0,1 + δ -1,1 /x(ω) ,
which is an elliptic function with periods ω 1 , ω 2 , where we have noted

δ i,j = 1 if (i, j) ∈ S, 0 if (i, j) / ∈ S.
3

The key tool for the proof in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] is the following: for any z ∈ (0, 1/|S|), GFs Q(x, 0; z) and Q(0, y; z) can be continued on the whole of C as multi-valued functions with infinitely many (and explicit) meromorphic branches. Then the set of poles of all these branches is proved to be infinite for any z ∈ (0, 1/|S|) \ H , which leads to the non-holonomy of the GFs.

• • • • • • • 0 ω 1 ω 1 /2 ω 2 ω x 1 ω x 2 ω y 2 Figure 4. The rectangle ω 1 [0, 1) + ω 2 [0, 1
) is a fundamental parallelogram for the Weierstrass elliptic function ℘(ω; ω 1 , ω 2 ), in terms of which x(ω) and y(ω) are expressed. We have also represented the points ω x 1 , ω x 2 and ω y 2 .

The function f y (ω) has at most six poles in the fundamental parallelogram Π 0,0 = ω 1 [0, 1) + ω 2 [0, 1), see Figure 4. Let ω 3 be defined in [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF]. We have z ∈ H if and only if ω 3 /ω 2 is rational, see [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]. Then for any z ∈ H (9)

ω 3 = k ℓ ω 2
for some k, ℓ ∈ Z with ℓ > k > 0 (k and ℓ depend on z in the infinite group case, but not in the finite group case). Finally we introduce ω

x 1 = ω 1 /2, ω x 2 = (ω 1 + ω 2 )/2 as well as ω y 2 = (ω 1 + ω 2 + ω 3 )/2.
Definition. Let g(ω) be a function meromorphic in the neighborhood of ω 0 ∈ C, where it has a pole of order p, such that g(ω) = ∞ k=-p g k (ωω 0 ) k . Its principal part at ω 0 is given by -1 k=-p g k (ωω 0 ) k .

Theorem 1. For any of the 74 models of non-singular walks in the quarter plane and any z ∈ H (see [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF]), let the f y i 's be the poles of the function f y (ω), and let F f y i ,y (ω) be the principal parts of this function at them. We have

K(0, y(ω); z)Q(0, y(ω); z) -K(0, y(ω y 2 ); z)Q(0, y(ω y 2 ); z) = ∞ p=-∞ ∞ n=0 k-1 s=0 f y i ∈Π 0,0 -ωx 1 A f y i s,p,n (ω),
where

A f y i s,p,n (ω) = -(⌊n/ℓ⌋ + 1)F f y i ,y (ω + sω 2 + nω 3 + pω 1 ) (10) -(⌊n/ℓ⌋ + 1)F f y i ,y (-ω + 2ω y 2 + sω 2 + nω 3 + pω 1 ) +2(⌊n/ℓ⌋ + 1)F f y i ,y (ω y 2 + sω 2 + nω 3 + pω 1 ).

The series of terms

( f y i ∈Π 0,0 -ωx 1 A f y i s,p,n (ω)) is absolutely convergent.
A similar expression holds for Q(x(ω), 0; z) and will be given in Theorem 9. Let ω x 0 ∈ Π 0,0 and ω y 0 ∈ Π 0,0 + ω 3 /2 be such that x(ω x 0 ) = 0 and y(ω y 0 ) = 0. Then the functions r x (ω) = K(x(ω), 0; z)Q(x(ω), 0; z) and r y (ω) = K(0, y(ω); z)Q(0, y(ω); z) can be found from the above expressions as follows:

r y (ω) = (r x (ω x 0 ) -r x (ω x 2 )) -(r x (ω) -r x (ω x 2 )) + x(ω)y(ω), (11)
r x (ω) = (r y (ω y 0 ) -r y (ω y 2 )) -(r y (ω) -r y (ω y 2 )) + x(ω)y(ω). ( 12
)
We now give some remarks around Theorem 1 (we refer to Theorem 9 for the complete statement).

• First, this theorem applies both in the finite and infinite group cases and gives series expressions for the GFs in a unified way for all 74 non-singular models. This result provides an alternative and completely different representation of these functions than the one given in [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] in terms of solutions to boundary value problems. It seems us more explicit and in this sense more satisfactory. As opposed to [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF], this approach provides expressions for the unknown functions thanks to the set of all their algebraic branches. • Second, natural questions are: How to apply this theorem? How explicit is it?

Here are the concrete things to do, and where to find them in the article.

-First, compute x(ω) -→ [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF].

-Then f y (ω) -→ (8).

-Then its poles and principal parts at them -→ no formula, since a priori this is a case by case analysis. Theoretically this is not difficult, since zeroes and poles of elliptic functions are well understood. We refer to Section 4 for an analysis of the poles of f y (ω), which are of order 1, 2 or 3. -Compute ω 1 , ω 2 and ω 3 -→ (15) and [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF].

-Deduce k and ℓ -→ (9).

-Compute A f y i s,p,n (ω) -→ [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF].

-Make the sum as in Theorem 1.

• One can in some cases deduce an expression of Q(x, 0; z) in terms of x and z. This will be further commented in Section 9. • The function Q(0, y; z) is algebraic in y if and only if the function Q(0, y(ω); z) is elliptic on C, with periods ω 1 and ω 2 which are rational multiples of ω 1 and ω 2 .

We shall give a simple necessary and sufficient condition for this in terms of the principal parts of f y (ω) at their poles, see Section 8. There will be cancellations or considerable simplifications between the different terms [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF] in this case.

We shall give in Part 2 three examples to illustrate our approach (in particular, how to work out and simplify the expressions given in Theorem 1), namely Kreweras' walk, the simple walk, and an infinite group case model. Further, our approach is also successfully applied in [START_REF] Bostan | A human proof of Gessel's lattice path conjecture[END_REF], so as to obtain a human proof of Gessel's conjecture.

Although our starting point in this article is the main equation ( 2) and the study of the kernel (3) as in the recent papers [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF][START_REF] Fayolle | Random walks in the quarter plane with zero drift: an explicit criterion for the finiteness of the associated group. Markov Process[END_REF][START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF], our approach is deeply different. It has been first suggested by Malyshev in [START_REF] Malyshev | Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms[END_REF]§6 in Chapter 5], at that time for studying the stationary probabilities generating functions of ergodic random walks in Z 2 + . The main idea consists in using, in a constructive way, Mittag-Leffler's theorem. 4 Specifically, we first find the poles (and the principal parts at these poles) of the lifted GFs on the universal covering C of T z ; then we show how to express the GFs as an infinite series of principal parts at its poles. Another possible method for obtaining the GFs for z ∈ H is based on [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Chapter 4]. It is commented in Appendix A.

This article closes our study of the walks with small steps in the quarter plane. Below we mention some open problems:

(i) In this article, we find expressions as infinite series for Q(x, 0; z) and Q(0; y; z)

for a dense set of values of z (namely, z ∈ H). By continuity this must provide an expression for the GFs for all values of z ∈ (0, 1/|S|).

It is an open problem to determine whether there exists an expression as an infinite series for the GFs when z ∈ (0, 1/|S|) \ H. (ii) We know from [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] that (as functions of the variables x and y) the functions Q(x, 0; z) and Q(0, y; z) are non-holonomic for all z ∈ (0, 2). We shall obtain that (this result is the subject of Proposition 15 in Part 2) 5

x(ω)zQ(x(ω), 0

; z) = 1 2z (ζ 1,2 (ω 2 /3) -ζ 1,2 (4ω 2 /3)) + 1 z (ζ 1,2 (ω 2 ) -ζ 1,2 (2ω 2 /3)) + 1 2z ζ 1,2 (ω + ω 2 /3) - 1 z ζ 1,2 (ω) + 1 z ζ 1,2 (ω -ω 2 /3) - 1 2z ζ 1,2 (ω -2ω 2 /3), ∀ω ∈ C,
where ζ 1,2 is the ζ-elliptic function with periods ω 1 , 2ω 2 (see Property (P1) in Appendix B for its definition). The periods ω 1 and ω 2 are defined in [START_REF] Jones | Complex Functions[END_REF]. (The dependency on z of the RHS above is precisely in the periods.) Further, one has (for this model)

x(ω) = ℘(ω) -1/3 -4z 2 ,
where ℘ is the ℘-elliptic function with periods ω 1 , ω 2 (see Equation [START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF] for its definition).

Using the transformation theory of elliptic functions (which typically allows to link elliptic functions with different couples of periods), we shall be able to deduce from the two above equations the following classical result [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF][START_REF] Fayolle | Random walks in the quarter-plane[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] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF]:

Q(x, 0; z) = 1 zx 1 2z - 1 x - 1 W - 1 x 1 -xW 2 ,
4 Roughly speaking, Mittag-Leffler's theorem states that it is possible to construct a meromorphic function with prescribed (discrete) set of poles and prescribed principal parts at these poles, see [START_REF] Sansone | Lectures on the theory of functions of a complex variable. I. Holomorphic functions[END_REF]Section 4.13]. 5 This comes indeed from Proposition 15 because we have y(ω) = x(ω + ω3/2), and for this reason

K(x(ω), 0; z)Q(x(ω), 0; z) = K(0, x(ω); z)Q(0, x(ω); z) = K(0, y(ω -ω3/2); z)Q(0, y(ω -ω3/2); z).
the function W being the only power series in z satisfying W = z(2 + W 3 ).

1.5. Structure of this article. Our paper has the following organization: Part 1 is concerned with the general theory. In Section 2 we introduce the general framework in which we shall work throughout the article: we do the construction of the elliptic curve T z and of its universal covering C. In Section 3, functions Q(x, 0; z) and Q(0, y; z) are lifted on T z , and then on its universal covering C. They are then continued as meromorphic functions on the whole of C. This continuation procedure, which is described in detail in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF], is based on ideas of [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]. We only sketch it here, restricting ourselves with notation and details necessary for the next sections. The function f y (ω) in ( 8), which appears in the statement of our main result (Theorem 1), plays a crucial role in it. Section 4 is devoted to the detailed study of the poles of f y (ω) and the principal parts at them, that figure out in the series expression [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF] of Theorem 1. In Sections 5-7 we prove the main result of the paper: for all 74 models and any z ∈ H, all branches of Q(x, 0; z) and Q(0, y; z) are computed as the sums of absolutely convergent series announced in Theorem 1. In Section 8 we identify the algebraic nature of the functions Q(x, 0) and Q(0, y) (question (II) stated at the very beginning of this paper) in terms of the principal parts of functions f x (ω) and f y (ω) (the function f x (ω) is the analogue of f y (ω) but for the function r x (ω)) at their poles in a parallelogram of periods. In Section 9 we explain how to obtain expressions of Q(x, 0; z) and Q(0, y; z) in terms of x and y (which can be more convenient than expressions of r x (ω) and r y (ω) in terms of ω).

In Part 2 we illustrate our results with three examples (finite group and algebraic, finite group and holonomic but non-algebraic, infinite group). The first example, which we treat in full detail, is that of Kreweras (see Figure 2). In Section 10 we obtain an expression for the generating function in terms of Weierstrass ζ-functions. In Sections 11-12 we show how to derive the well-known expressions for Q(0, 0; z) and Q(x, 0; z) = Q(0, x; z) by the theory of transformation of elliptic functions. The second example is the simple walk, in Section 13. We close Part 2 by Section 14, which is devoted to an example of walk having an infinite group.

Finally, in Appendix A we present another possible approach following [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], and in Appendix B we recall needed properties of elliptic functions.

In what follows, most of the time, we shall drop the dependence of all quantities with respect to the variable z, writing, for example, Q(0, 0) instead of Q(0, 0; z). Part 1. GFs for all non-singular models of walks

Universal covering and uniformization

In this section we introduce the general framework in which we shall work throughout the article: this mainly consists in defining a unifomization of the set {(x, y) ∈ (C∪{∞}) 2 : K(x, y) = 0}, where K(x, y) is defined in (3).

Branch points. Let us fix z ∈ (0, 1/|S|). The kernel K(x, y) is a polynomial of the second degree in both x and y. The algebraic function X(y) defined by K(X(y), y) = 0 has thus

M 0,0 M 1,0 M 0,1 M 1,1 • • • • • • -ω 2 0 ω 1 ω 2 /2 ω 2 2ω 2
Figure 5. The universal covering and the location of Π 0,0 = M 0,0 ∪ M 1,0 on it two branches and four branch points, that we call y i , i ∈ {1, . . . , 4}. 6 The latter are the roots of the discriminant of the second degree equation K(x, y) = 0 in the variable x:

(13) d(y) = (zy 2 δ 0,1 -y + zδ 0,-1 ) 2 -4z 2 (y 2 δ 1,1 + yδ 1,0 + δ 1,-1 )(y 2 δ -1,1 + yδ -1,0 + δ -1,-1 ).
We refer to [19, Section 2.1] for the numbering and for further properties of the y i 's. For any non-singular model, the Riemann surface of X(y) is a torus (i.e., a Riemann surface of genus 1) T y composed of two complex spheres C ∪ {∞} which are properly glued together along the cuts [y 1 , y 2 ] and [y 3 , y 4 ]. The analogous statement is true for the algebraic function Y (x) defined by K(x, Y (x)) = 0, and for its four branch points that are roots of ( 14)

d(x) = (zx 2 δ 1,0 -x + zδ -1,0 ) 2 -4z 2 (x 2 δ 1,1 + xδ 0,1 + δ -1,1 )(x 2 δ 1,-1 + xδ 0,-1 + δ -1,-1 ),
and its Riemann surface which is a torus T x . Since T x and T y are equivalent, in what follows we consider a single Riemann surface T with two different coverings x, y : T → S.

Galois automorphisms. Any point s ∈ T admits the two coordinates (x(s), y(s)), which by construction satisfy K(x(s), y(s)) = 0. 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 equation of the second degree K(x, y(s)) = 0 (resp. K(x(s), y) = 0) in x (resp. y). We define the automorphisms ξ : T → T (resp. η : T → T) such that ξs = s ′ (resp. ηs = s ′′ ) and call them Galois automorphisms, following the terminology of [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]. Clearly ξ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}).

Universal covering and uniformization. The torus T is isomorphic to a certain quotient space C/(ω 1 Z + ω 2 Z), where ω 1 , ω 2 are complex numbers linearly independent on R. This set can obviously be thought as the (fundamental) parallelogram [0,

ω 1 ] + [0, ω 2 ],
whose opposed edges are identified. Up to a unimodular transform, ω 1 , ω 2 are unique and are found in [9, Lemma 3.3.2]:

(15)

ω 1 = i x 2 x 1 dx -d(x) , ω 2 = x 3 x 2 dx d(x) .
For an upcoming use, we define

g x (t) = d ′′ (x 4 )/6 + d ′ (x 4 )/[t -x 4 ] if x 4 = ∞, d ′′ (0)/6 + d ′′′ (0)t/6 if x 4 = ∞,
as well as

g y (t) = d ′′ (y 4 )/6 + d ′ (y 4 )/[t -y 4 ] if y 4 = ∞, d ′′ (0)/6 + d ′′′ (0)t/6 if y 4 = ∞,
and finally we introduce ℘(ω; ω 1 , ω 2 ), the Weierstrass elliptic function with periods ω 1 , ω 2 . Throughout, we shall write ℘(ω) for ℘(ω; ω 1 , ω 2 ). By definition (see, e.g., [START_REF] Jones | Complex Functions[END_REF][START_REF] Watson | A course of modern analysis[END_REF]), we have ( 16)

℘(ω) = 1 ω 2 + (ℓ 1 ,ℓ 2 )∈Z 2 \{(0,0)} 1 (ω -ℓ 1 ω 1 -ℓ 2 ω 2 ) 2 - 1 (ℓ 1 ω 1 + ℓ 2 ω 2 ) 2 .
The universal covering of T has the form (C, λ), where C is the usual complex plane (that can be viewed as the union of infinitely many parallelograms Π m,n = ω 1 [m, m + 1) + ω 2 [n, n + 1) glued together for m, n ∈ Z) and λ : C → T is a non-branching covering map; see Figure 5. For any ω ∈ C such that λω = s ∈ T, we have x(λω) = x(s) and y(λω) = y(s). The uniformization formulas [9, Lemma 3.3.1] are [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF] x(λω

) = g -1 x (℘(ω)), y(λω) = g -1 y (℘(ω -ω 3 /2))
, where ( 18)

ω 3 = x 1 X(y 1 ) dx d(x) .
Throughout, we shall write x(λω) = x(ω) and y(λω) = y(ω). These are elliptic functions on C with periods ω 1 , ω 2 . Clearly

(19) K(x(ω), y(ω)) = 0, ∀ω ∈ C.
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}).

Points ω x i ∈ Π 0,0 such that x(ω x i ) = x i , i ∈ {1, . . . , 4} are pictured on Figure 6. They are equal to ω x 4 = 0, ω

x 1 = ω 2 /2, ω x 3 = ω 1 /2 and ω x 2 = (ω 1 + ω 2 )/2.
Points ω y i such that y(ω y i ) = y i are just the shifts of ω x i by the real vector ω 3 /2: ω y i = ω x i + ω 3 /2 for i ∈ {1, . . . , 4}, see also Figure 6.

The automorphisms ξ and η on T are lifted on the universal covering C in such a way that ω x 2 and ω y 2 stay their fixed points, respectively:

(20) ξω = -ω + 2ω x 2 , ηω = -ω + 2ω y 2 , ∀ω ∈ C.
Clearly, one has [START_REF] Malyshev | Positive random walks and Galois theory[END_REF] x( ξω) = x(ω), y( ηω) = y(ω), ∀ω ∈ C. ), and important points and domains on it

• • • • • • • • ω x 4 ω y 4 ω x 1 ω y 1 ω x 3 ω y 3 ω x 2 ω y 2 ✲ ✛ ω 3 /2 ✲ ✛ ω 3 /2 ✲ ✛ ω 2 ✻ ❄ ω 1 L x 2 x 1 L y 2 y 1 ∆ x ∆ y Figure 6. The fundamental parallelogram Π 0,0 = ω 1 [0, 1) + ω 2 [0, 1

Meromorphic continuation of the GFs on the universal covering

Meromorphic continuation of the GFs. The domains

{ω ∈ C : |x(ω)| < 1}, {ω ∈ C : |y(ω)| < 1}
consist of infinitely many curvilinear strips, which differ from translations by a multiple of ω 2 . We denote by ∆ x (resp. ∆ y ) the strip that is within ∪ n∈Z Π 0,n (resp. ∪ n∈Z Π 0,n + ω 3 /2). The domain ∆ x (resp. ∆ y ) is centered around the straight line L x 2 x 1 = {ω ∈ C : ℜω = ℜω x 2 } (resp. L y 2 y 1 = {ω ∈ C : ℜω = ℜω y 2 }), see Figure 6. Note that the function Q(x(ω), 0) (resp. Q(0, y(ω))) is well defined in ∆ x (resp. ∆ y ), by [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF]. Let us put [START_REF] Malyshev | An analytical method in the theory of two-dimensional positive random walks[END_REF] r

x (ω) = K(x(ω), 0)Q(x(ω), 0), ∀ω ∈ ∆ x , r y (ω) = K(0, y(ω))Q(0, y(ω)), ∀ω ∈ ∆ y .
The domain ∆ x ∩ ∆ y is a non-empty open strip. It follows from ( 2), ( 19) and ( 22) that ( 23)

r x (ω) + r y (ω) -Q(0, 0)K(0, 0) -x(ω)y(ω) = 0, ∀ω ∈ ∆ x ∩ ∆ y . Let (24) ∆ = ∆ x ∪ ∆ y .
Then the functions r x (ω) and r y (ω) can be continued as meromorphic functions on the whole of ∆, setting

r x (ω) = -r y (ω) + Q(0, 0)K(0, 0) + x(ω)y(ω), ∀ω ∈ ∆ y , (25)
r y (ω) = -r x (ω) + Q(0, 0)K(0, 0) + x(ω)y(ω), ∀ω ∈ ∆ x . (26)
The following theorem holds true, see [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] or [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]. Theorem 2 ([19], [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]). We have [START_REF] Stanley | Enumerative Combinatorics[END_REF] n∈Z

(∆ + nω 3 ) = C.
The functions r x (ω) and r y (ω) can be continued meromorphically from ∆ to the whole of C via the following formulas:

r x (ω -ω 3 ) = r x (ω) + y(ω)[x(-ω + 2ω y 2 ) -x(ω)], ∀ω ∈ C, (28)
r y (ω + ω 3 ) = r y (ω) + x(ω)[y(-ω + 2ω x 2 ) -y(ω)], ∀ω ∈ C. (29)
Further, we have, for any ω ∈ C,

r x (ω) + r y (ω) -K(0, 0)Q(0, 0) -x(ω)y(ω) = 0, (30) r x ( ξω) = r x (ω), (31)
r y ( ηω) = r y (ω), (32)
r x (ω + ω 1 ) = r x (ω), (33)
r y (ω + ω 1 ) = r y (ω). (34) The restrictions of r x (ω)/K(x(ω), 0) on (35) M k,0 = ω 1 [0, 1) + ω 2 [k/2, (k + 1)/2) for k ∈ {1, 2, . . .} provide all branches on C \ ([x 1 , x 2 ] ∪ [x 3 , x 4 ]) of Q(x, 0) as follows: (36) Q(x, 0) = {r x (ω)/K(x(ω), 0) : ω is the (unique) element of M k,0 such that x(ω) = x}.
Indeed, due to the ω 1 -periodicity of r x (ω) and x(ω), the restrictions of these functions on

M k,ℓ = ω 1 [ℓ, ℓ + 1) + ω 2 [k/2, (k + 1)/2)
do not depend on ℓ ∈ Z, and therefore determine the same branch as on M k,0 for any ℓ. Further, by (31) the restrictions of r x (ω)/K(x(ω), 0) on M -k+1,0 and on M k,0 lead to the same branches for any k ∈ Z. See Figure 5. The analogous statement holds for the restrictions of r y (ω)/K(0, y(ω)) on (37)

N k,0 = ω 3 /2 + ω 1 [0, 1) + ω 2 [k/2, (k + 1)/2) for k ∈ {1, 2, . . .}.
The continuation formulas ( 28) and (29) for r x (ω) and r y (ω) involve the functions

(38) f x (ω) = y(ω)[x(-ω + 2ω y 2 ) -x(ω)], f y (ω) = x(ω)[y(-ω + 2ω x 2 ) -y(ω)].
We close this section by showing that they admit alternative expressions, namely as in [START_REF] Chabat | Introduction à l'analyse complexe[END_REF] used in Theorem 1 and its analogue for the other coordinate.

Lemma 3. The following formulas hold, for any ω ∈ C:

f x (ω) = y(ω)[x(-ω + 2ω y 2 ) -x(ω)] = 1 2z y ′ (ω) δ 1,1 y(ω) + δ 1,0 + δ 1,-1 /y(ω) , f y (ω) = x(ω)[y(-ω + 2ω x 2 ) -y(ω)] = 1 2z x ′ (ω) δ 1,1 x(ω) + δ 0,1 + δ -1,1 /x(ω) . ( 39
)
Proof. By symmetry, it is enough to prove (39). We first take some notation: we write the kernel (3) under the form

K(x, y) = a(x)y 2 + b(x)y + c(x),
where for instance a(x) = z(δ 1,1 x 2 + δ 0,1 x + δ -1,1 ). The next point is the equality (see [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Equations (3.3.3) and(3.3

.4)]) 2a(x(ω))y(ω) + b(x(ω)) = -x ′ (ω)/2, ∀ω ∈ C.
On the other hand, one has (thanks to the root-coefficient relationships)

y(-ω + 2ω x 2 ) -y(ω) = - b(x(ω)) a(x(ω)) -2y(ω) = - 2a(x(ω))y(ω) + b(x(ω)) a(x(ω)) = x ′ (ω) 2a(x(ω))
.

The proof is concluded.

4. Properties of the poles of f y (ω) and of the principal parts at them

In this section we focus on function f y (ω) defined in (38). There are generally six poles of the function f y (ω) in any parallelogram of periods ω 1 , ω 2 on C. The number 6 comes from the fact that each function x(ω), y(-ω + 2ω x 2 ) and y(ω) has two poles in a fundamental parallelogram. (It is worth noting that for some of the 74 non-singular models, some of these poles may coincide, so that their number may be smaller-see [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Section 7] and also Remark 13 in this article.) We call f y i , i ∈ {1, . . . , 6}, the poles in Π 0,0ω x 2 . We denote by (40)

f y 1 = (x * , ∞), f y 2 = (x * * , ∞) those where y = ∞, by (41) f y 3 = (∞, y ′ ), f y 4 = (∞, y ′′
) those where x = ∞, and by (42)

f y 5 = (x * , y * ) = ξf y 1 -ω 2 , f y 6 = (x * * , y * * ) = ξf y 2
ω 2 the remaining ones. The location of these poles heavily depends on the signs of the branch points x 4 and y 4 , see [19, Cases I, II et III in Section 7] or the proof of Lemma 7 in this article. The signs of x 4 and y 4 can be expressed in terms of the geometry of the step set S, see [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Remark 24].

In this section we are interested in the computation of the functions F f y i ,y (ω) determining our main result, that is the series of Theorem 1. We first (Proposition 5 and its proof) compute the degree of F f y i ,y (ω) (i.e., the order of the pole f y i of the function f y (ω)). Then (below Proposition 5) we explain how concretely to compute the functions F f y i ,y (ω). First of all, we need the following technical lemma: Lemma 4. On the fundamental rectangle ω 1 [0, 1) + ω 2 [0, 1), x has one double pole or two simple poles. It has one double pole if and only if

(43) δ 1,0 = δ 1,1 = 0 or δ 1,0 = δ 1,-1 = 0,
and two simple poles if and only if the two conditions in (43) are not satisfied.

Proof. The uniformization formulas [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF] show that on ω 1 [0, 1) + ω 2 [0, 1), x has one double pole (if and only if x 4 = ∞) or two simple poles (if and only if

x 4 = ∞). Moreover, it is shown in [9, Lemma 2.3.8] that x 4 = ∞ if and only if δ 2 1,0 -4δ 1,1 δ 1,-1 = 0. Lemma 4 follows.
Proposition 5. The order of the poles of f y (ω) is 1, 2 or 3.

Proof. We use the alternative representation of f y (ω) given in Lemma 3:

f y (ω) = x ′ (ω)x(ω) 2a(x(ω)) , where a(x)/z = δ 1,1 x 2 + δ 0,1 x + δ -1,1 .
To be complete, we have the following cases to consider (for the non-singular walks):

1. a(x)/z = x 2 ; 2. a(x)/z = x; 3. a(x)/z = 1; 4. a(x)/z = x 2 + x; 5. a(x)/z = x 2 + 1; 6. a(x)/z = x + 1; 7. a(x)/z = x 2 + x + 1.
In the cases 1 and 4, the poles are simple. Indeed, we have, respectively,

f y (ω) = 1 2z x ′ (ω) x(ω) , f y (ω) = 1 2z (x(ω) + 1) ′ x(ω) + 1 .
Case 1 in particular covers Kreweras' and Gessel's models.

In the cases 5 and 7, we have (with δ = 0 and 1, respectively)

f y (ω) = 1 2z x ′ (ω) x(ω) + δ + 1/x(ω)
.

If ω 0 is a simple pole of x(ω), then it is obviously also a simple pole of f y (ω). If ω 0 is such that x(ω 0 ) + δ + 1/x(ω 0 ) = 0, then it can be a zero of order one or two (remember that x(ω) is an elliptic function of order two). In both cases, an expansion in the expression of f y (ω) above shows that f y (ω) has a pole of order one at ω 0 . In case 2, f y (ω) = x ′ (ω)/(2z). Therefore, if x(ω) has one simple (resp. double) pole, then f y (ω) has a double (resp. triple) pole. Both situations can happen: the simple walk (Figure 2) is such that the pole is simple, and the walk on the left on Figure 7 has a double pole.

In case 3, one has

f y (ω) = x ′ (ω)x(ω) 2z .
Therefore, if x(ω) has one simple (resp. double) pole, then f y (ω) has a triple (resp. quintuple) pole. By definition of case 3, one has δ 1,1 = δ 0,1 = 0. Further, if the pole of x(ω) is double, one of the two conditions in (43) must hold. This would imply that the walk is singular; this is a contradiction, since we do not consider these models here.

✲ ✻ ✻ ✛ ❅ ❅ | ✲ ✻ ✠ ❅ ❅ | ❅ ❅ ■ ✲ ✻ ✲ ✻ ❅ ❅ | ❄ ✛❅ ❅ ■ ✻ Figure 7.
Examples in the proof of Proposition 5

It remains to consider case 6. For similar reasons as for cases 5 and 7, if x(ω 0 ) + 1 = 0 then ω 0 is a pole of order one of f y (ω). If x(ω) has a simple (resp. double) pole, then obviously f y (ω) has a double (resp. triple) pole. The two situations can happen, as the second and third examples on Figure 7 illustrate. We now explain in which extent it is possible to find explicit expressions for the functions F f y i ,y (ω). In fact, this heavily depends on the model under consideration. For instance, in the cases 1 and 4, we do not need to simplify the uniformization [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF]: if ω 0 is a pole (resp. zero) of order p of x(ω), then the residue of f y (ω) at ω 0 is -p/(2z) (resp. p/(2z)). For the other cases, one needs more information on [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF]. For example, in case 2, we clearly need to know the principal parts of x(ω) at its poles in order to deduce the principal parts of f y (ω) at its poles. Unfortunately, there is no general formula, and this should be done model by model.

Expression of the GFs in terms of the principal parts at their poles

Although the dynamic of the meromorphic continuation procedure (see [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF], ( 26), [START_REF] Watson | A course of modern analysis[END_REF] and ( 29)) is fairly easy, the initial values [START_REF] Malyshev | An analytical method in the theory of two-dimensional positive random walks[END_REF] of r x (ω) in ∆ x and of r y (ω) in ∆ y can be obtained only via complicated integral representations of Q(x, 0) and Q(0, y) given in [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF], by solving certain boundary value problems. In this section we give another representation of r x (ω) and r y (ω) for any ω ∈ C. It is valid for any z ∈ H (see [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF] for its definition). We remind that for all 23 models with finite group, H = (0, 1/|S|), while for all 51 non-singular models with infinite group, H is dense in (0, 1/|S|), but not equal to the latter, see [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Theorem 1]. In [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF], the set H has been also characterized as

H = {z ∈ (0, 1/|S|) : ω 3 /ω 2 is rational}.
Therefore, for any fixed z ∈ H, one has (9), namely that ω 3 /ω 2 = k/ℓ for some integers ℓ > k > 0 without common divisors. In what follows we work under this assumption.

The other representation of the GFs r x (ω) and r y (ω) that we shall obtain here is based on a constructive application of Mittag-Leffler's theorem. Specifically, the latter theorem states that it is possible to construct a meromorphic function with prescribed (discrete) set of poles and prescribed principal parts at these poles (for the definition see Section 1.3), see [START_REF] Sansone | Lectures on the theory of functions of a complex variable. I. Holomorphic functions[END_REF]Section 4.13]. Our main result in this section (Theorem 6) states that the GFs are the limits of the sums of the principal parts at their poles along certain sequences of parallelograms.

We first construct a sequence of parallelograms (P m ) m 1 on the universal covering C with the following properties:

(i) P 1 ⊂ P 2 ⊂ • • • ; (ii) ∪ m 1 P m = C; (iii) All the P m 's are centered around ω y 2 ; (iv) There exist constants C 1 , C 2 > 0 such that for all m 1, sup ω∈∂Pm |r y (ω)| C 1 m, (44) inf ω∈∂Pm |ω -ω y 2 | C 2 m, (45)
where ∂P m denotes the boundary of P m .

The angle stone of this construction is the equality [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], under which there are many possibilities to perform it; below we just give one.

Construction of a family (P m ) m 1 satisfying (i), (ii), (iii) and (iv). Let f y (ω) be the function defined in (38). It has been used in the meromorphic continuation procedure (29). We recall that it has at most six distinct poles in the main parallelogram Π 0,0 + ω 3 /2 for r y (ω), we denote them by p (0) 1 , . . . , p (0) 6 . Let n ∈ {1, . . . , ℓ -1}, i ∈ {1, . . . , 6}, and consider p

(0) i -nω 3 . There exists a unique m i,n ∈ Z + such that p (n) i = p (0) i -nω 3 + m i,n ω 2 ∈ Π 0,0 + ω 3 /2. Let R = {ω ∈ Π 0,0 + ω 3 /2 : ℜω = p (n) i , ∀i ∈ {1, . . . , 6}, ∀n ∈ {1, . . . , ℓ -1}}.
In other words, R is the domain Π 0,0 + ω 3 /2 without the set of at most 6(ℓ -1) vertical segments. With (29) combined with [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], one deduces that for any ω ∈ R and any m ∈ Z, ω + mω 3 is not a pole of r y (ω).

Let us now fix ω + , ω -∈ R symmetric with respect to ω y 2 and such that ℜω + > ℜω -, and define the vertical straight lines

V + m = {ω ∈ C : ℜω = ℜω + + mω 3 }, V - m = {ω ∈ C : ℜω = ℜω --mω 3 }.
Then by Equations ( 29) and (34), and by the assumption (9) the function |r y (ω)| on them can be estimated as follows:

(46) sup

ω∈V + m ∪V - m |r y (ω)| C 3 + mC 4 ,
where (47)

C 3 = sup ω∈Π 0,0 +ω 3 /2 ℜω=ω + or ℜω=ω - |r y (ω)| < ∞ and C 4 = max n∈{0,...,ℓ-1}      sup ω∈Π 0,0 +ω 3 /2, ℜω=ω + |f y (ω + nω 3 )|, sup ω∈Π 0,0 +ω 3 /2, ℜω=ω - |f y (ω -nω 3 )|      < ∞.
Let us fix any ω * , ω * * ∈ Π 0,0 + ω 3 /2 symmetric with respect to ω y 2 , ℑω * > ℑω * * , and such that for all i ∈ {1, . . . , 6}, ℑω * = ℑp Define now the horizontal straight lines 46) and (50). Note that (9) was crucial to make (46) valid. Furthermore,

H * p = {ω ∈ C : ℑω = ℑω * + p|ω 1 |}, H * * p = {ω ∈ C : ℑω = ℑω * * -
inf ω∈∂Pm |ω -ω y 2 | m min{ω 3 , |ω 1 |},
which shows the estimate (45). This concludes the construction of the P m 's with required properties (i), (ii), (iii) and (iv).

We are now ready to state and prove the main result of this section. Theorem 6. Let d i be the poles of the function r y (ω) on C and let R d i ,y (ω) be the principal parts of r y (ω) at these poles. Then for any family of parallelograms (P m ) m 1 satisfying (i), (ii), (iii) and (iv), one has

(51) r y (ω) -r y (ω y 2 ) = lim m→∞ d i ∈Pm {R d i ,y (ω) -R d i ,y (ω y 2 )} , ∀ω ∈ C.
Proof. We follow [8, Chapter V, proof of Theorem 2], as suggested in [20, page 163]. We have (52)

1 2πi ∂Pm r y (ζ) ζ -ω dζ = res ω r y (ζ) ζ -ω + d i ∈Pm res d i r y (ζ) ζ -ω = r y (ω) + d i ∈Pm res d i d i ∈Pm R d i ,y (ζ) ζ -ω .
The rational function

G(ζ) = d i ∈Pm R d i ,y (ζ) ζ -ω
has a residue at infinity equal to zero (if there is at least one pole of r y (ω) in P m , that holds for all m large enough). Then

d i ∈Pm res d i G(ζ) + res ω G(ζ) = 0. Hence d i ∈Pm res d i G(ζ) = -res ω G(ζ) = - d i ∈Pm R d i ,y (ω), so that (53) 1 2πi ∂Pm r y (ζ) ζ -ω dζ = r y (ω) - d i ∈Pm R d i ,y (ω).
In particular, for ω = ω y 2 we have

(54) 1 2πi ∂Pm r y (ζ) ζ -ω y 2 dζ = r y (ω y 2 ) - d i ∈Pm R d i ,y (ω y 2 ).
Moreover, taking the derivative in (53) at ω = ω y 2 leads to (55)

1 2πi ∂Pm r y (ζ) (ζ -ω y 2 ) 2 dζ = r ′ y (ω y 2 ) - d i ∈Pm R ′ d i ,y (ω y 2 ).
Note that since r y (ω) = r y (-ω +2ω y 2 ) by ( 31), then for each d i pole of r y , -d i +2ω y 2 is also a pole of r y , and furtherR

′ d i ,y (ω y 2 ) = -R ′ -d i +2ωy 2 ,y (ω y 2 ). Since P m is centered in ω y 2 , then either both d i , -d i + 2ω y 2 belong to P m , or both do not. Hence d i ∈Pm R ′ d i ,y (ω y 2 ) = 0.
Subtracting from (53) the identity (54) and also (55) multiplied by the quantity (ω-ω y 2 ), we find (56)

1 2πi Pm r y (ζ) (ω -ω y 2 ) 2 (ζ -ω y 2 ) 2 (ζ -ω) dζ = r y (ω) - d i ∈Pm R d i ,y (ω) -   r y (ω y 2 ) - d i ∈Pm R d i ,y (ω y 2 )   -r ′ y (ω y 2 )(ω -ω y 2 ).
By the assumption (44), one has (57)

1 2πi Pm r y (ζ) (ω -ω y 2 ) 2 (ζ -ω y 2 ) 2 (ζ -ω) dζ |ω -ω y 2 | 2 2π C 1 m inf ζ∈∂Pm |ζ -ω| ∂Pm 1 |ζ -ω y 2 | 2 dζ.
By the assumption (45), one has

inf ζ∈∂Pm |ζ -ω| inf ζ∈∂Pm |ζ -ω y 2 | -|ω y 2 -ω| C 2 m -|ω y 2 -ω|.
We can also estimate

∂Pm 1 |ζ -ω y 2 | 2 dζ 4π inf ζ∈∂Pm |ζ -ω y 2 | 4π C 2 m . It follows that (57) equals O(1/m) as m → ∞. Thus r y (ω) -r y (ω y 2 ) = lim m→∞   d i ∈Pm R d i ,y (ω) - d i ∈Pm R d i ,y (ω y 2 )   + r ′ y (ω y 2 )(ω -ω y 2 ).
The identity r y (ω) = r y (-ω +2ω y 2 ) due to (31

) implies R d i ,y (ω) = R -d i +2ωy 2 ,y (-ω +2ω y 2 ).
Hence for any m 1,

d i ∈Pm R d i ,y (ω) = d i ∈Pm R d i ,y (-ω + 2ω y 2 ).
Then for any ω ∈ C, r ′ y (ω y 2 )(ωω y 2 ) = r ′ y (ω y 2 )(-ω + ω y 2 ), thus r ′ y (ω y 2 ) = 0. This finishes the proof of the theorem.

The result of Theorem 6 has to be improved for several reasons: first, it would be important to identify the poles of r y (ω) and the principal parts at them; second, it would be more convenient to represent r y (ω) as an absolutely convergent series, independent of the parallelograms P m 's; third, it would be useful to find the unknown constant r y (ω y 2 ). These remarks give the structure of the following sections. In Section 6 we compute the principal parts at the poles of r y (ω) in terms of the principal parts at the poles of f y (ω). In Section 7 we represent r y (ω) as the sum of an absolutely convergent series, where all terms are expressed via the principal parts at the (at most) six poles of f y (ω) in the parallelogram Π 0,0ω x 1 . In Section 7 we also compute r y (ω y 2 ).

Computation of the poles of the GFs and of the principal parts at them

In this section we study the poles of r y (ω) and the principal parts at them. The first lemma deals with the poles of r y (ω) in the domain ∆, which is defined in [START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF]. Let f y (ω) be the function defined in (38). We denote by F d,y (ω) the principal part of f y (ω) at the pole d. Proof. We first prove the following facts:

(i) ∆ ∩ {ω ∈ C : y(ω) = ∞} ⊂ {ω ∈ C : ℜω < ℜω x 1 } ∪ (ω x 1 + ω 1 Z); (ii) ∆ ∩ {ω ∈ C : y( ξω) = ∞} ⊂ {ω ∈ C : ℜω > ℜω x 1 } ∪ (ω x 1 + ω 1 Z); (iii) ∆ ∩ {ω ∈ C : x(ω) = ∞} ⊂ {ω ∈ C : ℜω > ℜω x 1 }.
Consider first the models with y 4 < 0. For them, points ω ∈ C such that y(ω) = ∞ are located on the vertical lines {ω ∈ C : ℜω = ℜω y 4 + mω 2 }, m ∈ Z. Only those on the line {ω ∈ C : ℜω = ℜω y 4 } can be in ∆, and on this line we have ℜω y 4 < ℜω x 1 . This proves (i) for these models. Points ω with y( ξω) = ∞ are on the lines ξ{ω ∈ C : ℜω = ℜω y 4 + mω 2 }, m ∈ Z. None of them can be in ∆, except for those on ξ{ω ∈ C : ℜω = ℜω y 4 }. But we have ℜ ξω y 4 > ℜω x 1 . This concludes the proof of (ii) for these models.

Consider models with y 4 > 0 or y 4 = ∞. It is proved in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] that points ω with y(ω) = ∞ are located as follows: one of them, say f 1 , is such that ℑf 1 = 0 and ℜω x 4 ℜf 1 ℜω y 4 < ℜω x 1 ; the other, say f 2 , is symmetric to f 1 w.r.t. ω y 4 . Furthermore ℑf 2 = 0 and ℜω y 4 ℜf 2 ℑω x 1 (in the limit case y 4 = ∞, one has f 1 = f 2 = ω y 4 ). All other points where y(ω) = ∞ are the shifts of f 1 , f 2 by mω 2 + pω 1 , for m, p ∈ Z. Only points of type f 1 +pω 1 and f 2 +pω 1 with p ∈ Z can be in ∆. We have for them ℜ(f i +pω 1 ) = ℜf i ℜω x 1 , i ∈ {1, 2}. Then either ℜ(f i + pω 1 ) < ℜω x 1 or ℜ(f i + pω 1 ) = ℜω x 1 = ℜ(ω x 1 + pω 1 ). In the last case the observation ℑ(f i + pω 1 ) = pω 1 = ℑ(ω x 1 + pω 1 ), i ∈ {1, 2}, leads to f i + pω 1 = ω x 1 + pω 1 and finishes the proof of (i) for this class of models. Points ω such that y( ξω) = ∞ are ξ(f 1 + mω 2 + pω 1 ) and ξ(f 2 + mω 2 + pω 1 ), for m, p ∈ Z. Only points

ξ(f i + pω 1 ) , i ∈ {1, 2}, can be in ∆. If ℜ(f i + pω 1 ) < ℜω x 1 , then ℜ ξ(f i + pω 1 ) > ℜω x 1 . If f i + pω 1 = ω x 1 + pω 1 , then ξ(f i + pω 1 ) = ω x 1 + (-p + 1)ω 1 .
This proves assertion (ii) for all these models.

It remains to prove (iii). Consider ω with x(ω) = ∞ first for models with x 4 < 0. Then the points of C with x(ω) = ∞ lie on the vertical lines {ω ∈ C : ℜω = ℜω x 4 + mω 2 }, m ∈ Z. Only those on the line {ω ∈ C : ℜω = ℜω x 4 + ω 2 } can be in ∆, where we have

ℜω x 4 + ω 2 > ℜω x 1 .
Let us finally prove (iii) for models such that x 4 > 0 or x 4 = ∞. It has been proved in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] that points ω with x(ω) = ∞ are located as follows: one of them, say f 3 , is such that ℑf 3 = 0 and ℜω x 1 < ℜω x 4 + ω 2 ℜf 3 < ℜω y 4 + ω 2 ; the other, f 4 , is symmetric to

f 3 w.r.t. ω x 4 + ω 2 and ℜω x 1 < ℜω y 2 ℜf 4 ℜω x 4 + ω 2 (in the limit case x 4 = ∞, one has f 3 = f 4 = ω x 4 + ω 2 )
. All other points with x(ω) = ∞ are their shifts by mω 2 + pω 1 , where m, p ∈ Z. Only points f 3 + pω 1 and f 4 + pω 1 with p ∈ Z can be in ∆. We have

ℜ(f 3 + pω 1 ) = ℜf 3 > ℜω x 1 and ℜ(f 4 + pω 1 ) = ℜf 4 > ℜω x 1 , that finishes the proof of item (iii). Let d be a pole of r y (ω) in ∆. Since r y (ω) is holomorphic in ∆ y , then d ∈ ∆ x with |x(d)| < 1 and r x (d) = ∞.
r y (ω) = -r x (ω) + K(0, 0) -f y (ω) + x(ω)y( ξω),
from where (58) follows.

Let d be a pole of f y (ω) in ∆ such that ℜd < ℜω x 1 . Then necessarily one of the three following equalities holds: It follows from (60) that any pole d of f y (ω) in ∆ such that ℜd < ℜω x 1 (or equivalently, any pole d of r y (ω) in ∆) is not a pole of r y (ω) + f y (ω) in ∆. It was proved that any pole d ′ of f y (ω) in ∆ with ℜd > ℜω x 1 is not a pole of r y (ω) in ∆. Then d ′ must be a pole of r y (ω) + f y (ω) in ∆. Finally, let us show that f y (ω) cannot have a pole d ′′ in ∆ with ℜd ′′ = ℜω x 1 . In fact, for any pole d ′′ of f y (ω), one of the three equalities holds:

y(d) = ∞, y( ξd) = ∞, or x(d) = ∞. By (i), (ii) and (iii), y(d) = ∞, so that d ∈ ∆ x and r x (d) = ∞. Thus |x(d)| = |x( ξd)| < 1, ξd ∈ ∆ x ⊂ ∆ and ℜ( ξd) > ℜω
y(d ′′ ) = ∞, y( ξd ′′ ) = ∞, or x(d ′′ ) = ∞. Assumption ℜd ′′ = ℜω x 1 combined with (i), (ii) and (iii) yields d ′′ = ω x 1 + pω 1 , with p ∈ Z. In particular, y(d ′′ ) = ∞. Then x 1 should be a branch point of Y (x) with |x 1 | < 1, lim x→x 1 Y (x) = ∞ and lim x→x 1 x(Y 0 (x)-Y 1 (x)) = ∞,
which is true for none of the models. Hence f y (ω) has no poles d ′′ with ℜd ′′ = ℜω x 1 , and Lemma 7 is proved.

Our ultimate goal is to obtain explicit expressions for r x (ω) and r y (ω) from Theorem 6. The theorem which immediately follows is a key preliminary result: it gives expressions for the principal parts R d i ,y (ω) of r y (ω) in terms of the principal parts of the elliptic function f y (ω) at its poles. The main tool for that are the meromorphic continuation formulas [START_REF] Watson | A course of modern analysis[END_REF] and (29).

In what follows, we extend our notation R d,y (ω) of Theorem 6 for any d ∈ C, as follows: R d,y (ω) will be the principal part of r y (ω) at d (see Section 1.3 for the definition) if d is a pole of r y (ω), and R d,y (ω) = 0 if d is not a pole of r y (ω). Further, we shall denote throughout by ⌊x⌋ (resp. ⌈x⌉) the lower integer part (resp. the upper integer part) of x ∈ R. Theorem 8. Assume the assertion [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]. Denote by F f,y (ω) the principal part of f y (ω) at a pole f .

(i) Let d ∈ C with ℜd < ℜω y 1 . Let N - d = {n 0 : d + nω 3 is a pole of f y (ω) with ℜω x 1 -kω 2 < ℜd + nω 3 < ℜω x 1 }.
If d is a pole of r y (ω), then N - d = ∅. Furthermore, for any d ∈ C with ℜd < ℜω y 1 and N - d = ∅, we have:

(61) R d,y (ω) = n∈N - d -(⌊n/ℓ⌋ + 1)F d+nω 3 ,y (ω + nω 3 ). (ii) Let d ∈ C with ℜd > ℜω y 1 . Let N + d = {n 1 : d -nω 3 is a pole of f y (ω) with ℜω x 1 < ℜd -nω 3 < ℜω x 1 + kω 2 }.
If d is a pole of r y (ω), then N + d = ∅. Furthermore, for any d ∈ C with ℜd > ℜω y 1 and N - d = ∅, we have:

(62) R d,y (ω) = n∈N + d (⌊(n -1)/ℓ⌋ + 1)F d-nω 3 ,y (ω -nω 3 ).
r y (ω) = r y (ω + nω 3 ) -f y (ω + (n -1)ω 3 ) -f y (ω + (n -2)ω 3 ) -• • • -f y (ω),
where n is such that ω + nω 3 ∈ ∆, while ω + (n -1)ω 3 , ω + (n -2)ω 3 , . . . , ω ∈ ∆. If d ∈ D - is a pole of r y (ω), then either d + tω 3 is a pole of f y (ω) for some t ∈ {0, . . . , n -1} (then of course ℜ(d + tω 3 ) < ℜω x 1 since d + tω 3 ∈ D -), or d + nω 3 is a pole of r y (ω) in ∆, that is (by Lemma 7) a pole of f y (ω) in ∆ with ℜd + nω 3 < ℜω x 1 . This proves that N - d = ∅. Let us note that by [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], for any ω pole of f y (ω), ωℓω 3 = ωkω 2 is also a pole of f y (ω), since this function is ω 2 -periodic, and so is ωmℓω 3 , for any m 1. Then (61) follows from Lemma 7, Equations ( 58) and (63).

Let d be a pole of r y (ω) with ℜd > ℜω y 1 . Then ℜd > ℜω y 1 > ℜω x 1 and, by Lemma 7, d ∈ ∆. Then d ∈ D + . By (29), we have that for any ω ∈ D + , (64)

r y (ω) = r y (ω -nω 3 ) + f y (ω -nω 3 ) + f y (ω -(n -1)ω 3 ) + • • • + f y (ω -ω 3 ),
where n is chosen such that ω - 9), for any ω pole of f y (ω) and any m 1, ω + mℓω 3 = ω + mkω 2 is also a pole of f y (ω), due to ω 2 -periodicity of f y (ω). Then (62) follows from Lemma 7 and Equation (64).

nω 3 ∈ ∆, but ω -(n -1)ω 3 , ω -(n -2)ω 3 , . . . , ω ∈ ∆. If d ∈ D + is
We remark that a point d such that ℜd < ℜω y 1 (resp. ℜd > ℜω y 1 ) and

N - d = ∅ (resp. N + d = ∅)
is not necessarily a pole of r y (ω), since in the sum (63) (resp. ( 64)), terms producing poles of r y (ω) can compensate each other. However, the formula (61) (resp. (62)) is valid for any such d; if d is not a pole, then obviously the RHS in the latter equation equals 0.

Representation of the GFs in terms of convergent series

Using Theorem 6 and the analysis of poles and principal parts of r y (ω) in Section 6, we now compute the GFs r x (ω) and r y (ω) independently of the construction of the parallelograms (P m ) m 1 . In the next theorem the GFs are expressed in terms of the principal parts of function f y (ω) (resp. f x (ω)) in (38) at their (at most six) poles in the parallelogram Π 0,0ω x 1 (resp. Π 0,0 + ω y 1 ). This is the main result of the present paper; it is valid for any of 74 non-singular models of walks and any z ∈ H. It has been announced in Theorem 1.

Theorem 9. Assume the assertion [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]. Let the f y i 's be the poles of the function f y (ω), and let F f y i ,y (ω) be the principal parts of this function at them. We have

(65) r y (ω) -r y (ω y 2 ) = ∞ p=-∞ ∞ n=0 k-1 s=0 f y i ∈Π 0,0 -ωx 1 A f y i s,p,n (ω),
where

A f y i s,p,n (ω) = -(⌊n/ℓ⌋ + 1)F f y i ,y (ω + sω 2 + nω 3 + pω 1 ) (66)
-(⌊n/ℓ⌋ + 1)F f y i ,y (-ω + 2ω y 2 + sω 2 + nω 3 + pω 1 ) +2(⌊n/ℓ⌋ + 1)F f y i ,y (ω y 2 + sω 2 + nω 3 + pω 1 ).

The series (65) of terms

( f y i ∈Π 0,0 -ωx 1 A f y i s,p,n (ω)
) is absolutely convergent. Let the f x i 's be the poles of the function f x (ω), and let F f x i ,x (ω) be the principal parts of this function at them. We have

(67) r x (ω) -r x (ω x 2 ) = ∞ p=-∞ ∞ n=0 k-1 s=0 f y i ∈Π 0,0 +ωy 1 B f x i s,p,n (ω),
where

B f x i s,n,p (ω) = -(⌊n/ℓ⌋ + 1)F f x i ,x (ω -sω 2 -nω 3 -pω 1 ) (68) -(⌊n/ℓ⌋ + 1)F f x i ,x (-ω + 2ω x 2 -sω 2 -nω 3 -pω 1 ) +2(⌊n/ℓ⌋ + 1)F f x i ,x (ω x 2 -sω 2 -nω 3 -pω 1 ).
The series (67) of terms

( f y i ∈Π 0,0 +ω 3 /2+ωy 1 B f x i s,p,n (ω)
) is absolutely convergent. Let ω x 0 ∈ ∆ x be such that x(ω x 0 ) = 0 and let ω y 0 ∈ ∆ y be such that y(ω y 0 ) = 0. Then r x (ω) and r y (ω) can be found from (65) and (67) as follows:

r y (ω) = (r x (ω 0 x ) -r x (ω x 2 )) -(r x (ω) -r x (ω x 2 )) + x(ω)y(ω), (69)
F f y i ,y (ω) = t n=1 r i,n (ω -f y i ) n
the principal part (see Section 1.3 for the definition) of f y (ω) at the pole f y i . Since f y (ω) is an elliptic function with periods ω 1 , ω 2 , it follows that 6 i=1 r i,1 = 0 (it is a classical property of elliptic functions that the sum of the residues in a fundamental parallelogram is zero, see (P12), Lemma 27 in Appendix B, where we have gathered all needed properties of elliptic functions). This fact implies the convergence of the series

∞ p=-∞ ∞ n=0 k-1 s=0 f y i ∈Π 0,0 -ωx 1 A f y i s,p,n (ω) .
We use the construction of the parallelograms P m 's in Section 5 bounded by V + m , V - m , H * pm and H * * pm . They are all centered in ω y 2 , so that d ∈ P m is equivalent to ηd ∈ P m . Since r y (ω) = r y ( ηω), then for any pole d of r y (ω), R ηd,y (ω) = R d,y ( ηω) = R d,y (-ω + 2ω y 2 ). For any d ∈ P m with ℜd < ℜω y 2 = ℜω y 1 , there corresponds ηd ∈ P m with ℜ ηd > ℜω y 1 and vice versa. Points with real part equal to ℜω y 1 belong to ∆ y and therefore cannot be poles of r y (ω). Then by Theorem 6, r y (ω)r y (ω y 2 ) = lim

R d i ,y (ω) = d i ∈Pm ℜd i <ℜωy 1 and N - d i =∅ R d i ,y (ω),
where the sum in the RHS above is taken over all points of P m (not only the poles) with ℜd < ℜω y 1 and N - d = ∅. For any d with ℜd < ℜω y 1 and N - d = ∅, there exist n 0 and f y i pole of f y (ω) with ℜω

x 1 -kω 2 < ℜf y i < ℜω x 1 such that d + nω 3 = f y i . If in addition d ∈ P m , then ℜd ℜω --mω 3 , so that n m -ℜ(ω --f y i )/ω 3 and also * -p m ω 1 ) ℑd = ℑf y i ℑ(ω * * + p m ω 1
). On the other hand, for any f y i with real and imaginary parts bounded as above and for any non-negative integer n m-ℜ(ω --f y i )/ω 3 , the point f y i -nω 3 belongs to P m and it is such that N - d = ∅. Therefore by (61) of Theorem 8, the quantity in the RHS of (72) equals (73)

f y i :ℑ(ω * -pmω 1 ) ℑf y i ℑ(ω * * +pmω 1 ) ℜωx 1 -kω 2 <ℜf y i <ℜωx 1 ⌊m-ℜ(ω --f y i )/ω 3 ⌋ n=0 -(⌊n/ℓ⌋ + 1)F f y i ,y (ω + nω 3 ).
For any f y i in the sum above, there exist unique s ∈ {0, 1, . . . , k -1} and p ∈ Z such that f y i = f y isω 2pω 1 , where f y i ∈ Π 0,0ω x 1 is a pole of f y (ω). Furthermore, the bounds for ℑf y i are equivalent to -p m + ℑ(

f y i -ω * * )/|ω 1 | p p m + ℑ( f y i -ω * )/|ω 1 |.
We deduce that for any ω ∈ C, the sum in (73) equals (74)

f y i ∈Π 0,0 -ωx 1 k-1 s=0 ⌊pm+ℑ(ω * -f y i )/|ω 1 |⌋ p=⌈-pm+ℑ(ω * * -f y i )/|ω 1 |⌉ ⌊m-ℜ(ω --f y i )/ω 3 ⌋ n=0 -(⌊n/ℓ⌋+1)F f y i ,y (ω+nω 3 +sω 2 +pω 1 )
.

By (66), (71), ( 72) and (74), we obtain (75)

r y (ω) -r y (ω y 2 ) = lim m→∞ f y i ∈Π 0,0 -ωx 1 k-1 s=0 ⌊pm+ℑ(ω * -f y i )/|ω 1 |⌋ p=⌈-pm+ℑ(ω * * -f y i )/|ω 1 |⌉ ⌊m-ℜ(ω --f y i )/ω 3 ⌋ n=0 A f i y s,n,p (ω).
To conclude the proof of (65), it remains to show that the difference (76)

f y i ∈Π 0,0 -ωx 1 k-1 s=0 ⌊pm+ℑ(ω * -f y i )/|ω 1 |⌋ p=⌈-pm+ℑ(ω * * -f y i )/|ω 1 |⌉ ⌊m-ℜ(ω --f y i )/ω 3 ⌋ n=0 A f i y s,n,p (ω) - pm p=-pm m n=0 k-1 s=0 f y i ∈Π 0,0 -ωx 1 A f i y s,n,p (ω)
converges to zero as m → ∞. To that purpose, it is sufficient to prove that for any fixed f y i ∈ Π 0,0ω x 1 and s ∈ {0, 1, . . . , k -1}, the limit of ( 77)

⌊pm+ℑ(ω * -f y i )/|ω 1 |⌋ p=⌈-pm+ℑ(ω * * -f y i )/|ω 1 |⌉ ⌊m-ℜ(ω --f y i )/ω 3 ⌋ n=0 A f i y s,n,p (ω) - pm p=-pm m n=0 A f i y s,n,p (ω)
is 0 as m → ∞. Using the definition (66), it is easy to show that for any f y i and any s ∈ {0, 1, . . . , k -1},

(78) ∞ p=-∞ |A f i y s,n,p (ω)| = O(1/n), n → ∞, ∞ n=0 |A f i y s,n,p (ω)| = O(1/p), p → ∞,
from where (77) follows. Hence (65) is proved. The proof of (67) for r x (ω) is completely analogous and is omitted. In order to show (69) and (70), we notice that Q(0, 0)K(0, 0) = r x (ω x 0 ) = r y (ω y 0 ). This way, (69) and (70) are immediate corollaries of (30).

Algebraicity and holonomy of the GFs

Theorem 9 determines the GFs Q(x, 0) and Q(0, y) in terms of the principal parts of functions f x (ω) and f y (ω) at their poles in a parallelogram of periods. We would like now to identify the algebraic nature of these functions (question (II) stated at the very beginning of this paper) in the same terms.

Given a pole f y i ∈ Π 0,0ω x 1 , consider the sum

F y f y i (ω) = F f y i ,y (ω) + F f y i +ω 3 ,y (ω + ω 3 ) + • • • + F f y i +(ℓ-1)ω 3 ,y (ω + (ℓ -1)ω 3 ).
(We recall that above, for t ∈ {0, . . . , ℓ -1}, F f y i +tω 3 ,y is the principal part of f y (ω) at f y i + tω 3 . In particular, for t such that f y i + tω 3 is not a pole of f y (ω), the corresponding term F f y i +tω 3 ,y is identically zero.) Proposition 10. Under the assumption (9), the functions x → Q(x, 0) and y → Q(0, y) are algebraic functions with 2k branches if and only if

(79) F y f y i (ω) = 0, ∀ω ∈ C, ∀i ∈ {1, . . . , 4},
with the numbering of the poles (40)-(42) as above.

Proof. Under the assumption (79), for all i ∈ {1, . . . , 4}, there exists j ∈ {1, . . . , 6} (with an appropriate F f y j (ω)) such that f y i + nω 3 = f y j + sω 2 for some n ∈ {1, . . . , ℓ -1} and s ∈ {0, . . . , k -1}. Since

f y 5 = ξ ηf y 1 = f y 1 -ω 3 , f y 6 = ξ ηf y 2 = f y 2 -ω 3
, then under (79), the sum F y f y i (ω) is also zero for i ∈ {5, 6} and for all ω ∈ C. Therefore, under (79), the elliptic function (which in some sense is an orbit sum, see [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF])

(80) O(ω) = f y (ω) + f y (ω + ω 3 ) + • • • + f y (ω + (ℓ -1)ω 3 ), ∀ω ∈ C,
has no poles in C and thus, by a well-known property of elliptic functions (see Property (P2)) it is a constant: there exists C ∈ C such that O(ω) = C, for all ω ∈ C. We now prove that C = 0. One has in particular O(ω y 2 + ω 3 ) = O(ω y 2ℓω 3 ) = C, and thus, by Equations ( 63) and (64),

r y (ω y 2 -ℓω 3 ) = r y (ω y 2 ) -O(ω y 2 -ℓω 3 ) = r y (ω y 2 ) -C, r y (ω y 2 + ℓω 3 ) = r y (ω y 2 ) + O(ω y 2 + ω 3 ) = r y (ω y 2 ) + C.
Moreover, it follows from (31) that r y (ω y 2ℓω 3 ) = r y (ω y 2 + ℓω 3 ), from where C = 0. Hence, under (79), we conclude that O(ω) = 0 for all ω ∈ C. It follows again from ( 63) and ( 64) that the function r y (ω) is ℓω 3 = kω 2 -periodic, and then by (30), so is r x (ω). By Property (P7), r x (ω) and r y (ω) are algebraic in x(ω) and y(ω) respectively. On the other hand, if (79) is not satisfied, then O(ω) is not identically zero. It has been shown in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Section 6] that under this last condition, the functions x → Q(x, 0) and y → Q(0, y) are holonomic, but not algebraic.

It is worth noting that the condition (79), which is stated for f y (ω), is equivalent to its analogue for the function f x (ω). Further, it is immediate from Proposition 10 that under (79), the residues at the poles of r x (ω) and r y (ω) are bounded on C. Moreover, under (79), the terms A f y i s,n,p (ω) defined in (66) can be permuted and regrouped in their sum over

p ∈ Z, n 0, s ∈ {0, . . . , k -1}, f y i ∈ Π 0,0 -ω x 1
, in such a way that the coefficients in front of F f y i ,y are bounded and this infinite sum stays equal to the one of (65). This condition can never hold true for models where x 4 > 0 or y 4 > 0 because of the position of the poles of f y (ω), see [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]. We do not know if for models with infinite group and such that x 4 ∈ (-∞, 0] ∪ {∞} and y 4 ∈ (-∞, 0] ∪ {∞}, there exist values of z ∈ H such that (79) is satisfied. But among the 23 models with finite group, it is satisfied exactly for 4 models, and in particular for Kreweras' and Gessel's walks. 9. Expressions of Q(x, 0) and Q(0, y) in terms of the variables x and y Our main result (Theorem 1, restated in full detail in Theorem 9) gives expressions for the functions r x (ω) and r y (ω) as infinite series of rational functions of ω. The functions x(ω) and y(ω) being themselves expressed with Weierstrass ℘-functions, our results provide expressions for Q(x, 0) and Q(0, y) as infinite series of rational functions of inverse Weierstrass functions. Though explicit, these expressions may appear complicated, and it is natural to search for simpler expressions of Q(x, 0) and Q(0, y). Furthermore, in some particular cases (as Kreweras' one, see Proposition 11, taken from [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF][START_REF] Fayolle | Random walks in the quarter-plane[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] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF], which gives a very simple expression of Q(x, 0) = Q(0, x)), we know that there are simple algebraic or holonomic expressions for the GFs.

In this section we explain how to obtain such expressions of Q(x, 0) and Q(0, y) in terms of x and y. We shall not state a general result (which, in some sense, is not reachable), but we shall explain how, model by model, it is possible to obtain such expressions. As we shall see, this reasoning has some algorithmic insights. We shall consider two different cases, according to whether the orbit-sum ( 80)

O(ω) = f y (ω) + f y (ω + ω 3 ) + • • • + f y (ω + (ℓ -1)ω 3 ), ∀ω ∈ C,
is identically zero or not. We already know (see Section 8) that the orbit-sum if identically zero if and only if the GFs are algebraic. We recall that r y (ω + ω 3 ) = r y (ω) + f y (ω) (see ( 29)), from where (with

ω 3 /ω 2 = k/ℓ) (81) r y (ω + kω 2 ) = r y (ω) + O(ω), ∀ω ∈ C.
9.1. Algebraic case. We first assume that O(ω) is identically equal to zero. It follows from (81) that the function r y (ω) is elliptic with periods ω 1 , kω 2 . We now describe the three things to do so as to obtain an expression of Q(0, y) in terms of y (up to an additive constant7 ):

• Find the poles ω i of r y (ω) in a parallelogram of size ω 1 , kω 2 ;

• Deduce an expression of r y (ω) in terms of the functions ζ(ωω i ; ω 1 , kω 2 ) and its derivatives (we recall that ζ ′ (ω; ω 1 , kω 2 ) = -℘(ω; ω 1 , kω 2 )); • Deduce an expression of r y (ω) in terms of y(ω), and finally an expression of K(0, y)Q(0, y) in terms of the variable y.

Here are more details. The first point is sufficient to determine r y (ω) up to an additive constant, thanks to standard properties of elliptic functions, see, e.g., (P6) (this is here that we use the fact that the orbit-sum is zero). To find the poles of r y (ω) we can use Theorem 8 (and more generally the results of Section 6), which precisely gives the poles of r y (ω) in any domain. All results of Section 6 are based on the simple relation r y (ω + ω 3 ) = r y (ω) + f y (ω). For the second point there are general theorems, such as (P6), which give an expression for an elliptic function with prescribed poles. Concerning the last point, we can use in a constructive way Property (P7), saying that if f (ω) and g(ω) are non-constant elliptic functions with the same periods, there exists a non-zero polynomial P such that P (f (ω), g(ω)) = 0, for all ω ∈ C. (The function y(ω), being elliptic with periods ω 1 , ω 2 , is of course also elliptic for the periods ω 1 , kω 2 .) This part will be illustrated in Part 2, by the detailed example of Kreweras' model. 9.2. Holonomic case. The main point here consists in introducing a function φ(ω) such that

(1 φ ) φ(ω) is meromorphic on C; (2 φ ) φ(ω) is ω 1 -periodic; (3 φ ) φ(ω + kω 2 ) = φ(ω) + 1, for all ω ∈ C.
An example of such functions is given by (this is simply verified, and this can be found in [9, Equation (4.3.7)])

(82) φ(ω) = ω 1 2iπ ζ(ω; ω 1 , kω 2 ) - ω iπ ζ(ω 1 /2; ω 1 , kω 2 ), ∀ω ∈ C.
The reason of introducing φ(ω) is the following: Equation ( 81) is equivalent to saying that the function r y (ω+kω 2 )-φ(ω)O(ω) is kω 2 -periodic, and hence elliptic with periods ω 1 , kω 2 .

We are then faced with the same problem as in the algebraic case (Section 9.1), namely, to find the expression in terms of y(ω) of a function (namely, r y (ω + kω 2 )φ(ω)O(ω)) elliptic with periods ω 1 , kω 2 , with known poles (the poles are known since we know the poles of r y (ω) with Section 6, we also know those of the orbit-sum with the formula (80), and those of φ(ω) via ( 82)). We thus refer to the algebraic case for the details. There is, however, an additional difficulty around the function φ(ω): how to obtain an expression of it in terms of y(ω)? In fact, the function φ ′ (ω) is easily found in terms of y(ω), since it is an elliptic function. The function φ ′ (ω) is thus an algebraic function of y(ω), and the function φ(ω) turns out to be the primitive of an algebraic function of y(ω), which needs not to be (and in fact, which is not) algebraic.

To conclude we comment on functions φ(ω) satisfying to (1 φ ), (2 φ ) and (3 φ ). If φ(ω) and ψ(ω) both satisfy (1 φ ), (2 φ ) and (3 φ ), then the function φ(ω)ψ(ω) is elliptic with periods ω 1 , kω 2 . This means that it essentially suffices to find one good function φ(ω). Let us show that (82) is suitable. That φ(ω + ω 1 ) = φ(ω) simply follows from Property (P10) in Appendix B. Finally, the identity φ(ω + ω 2 ) = φ(ω) + 1 comes from Property (P11) (known as Legendre's identity).

In a fundamental parallelogram the function φ(ω) has a unique pole, at 0, of order 1 and with residue 1. In some sense, the function φ(ω) in ( 82) is thus the minimal function (i.e., with the smallest order) satisfying (1 φ ), (2 φ ) and (3 φ ).

Part 2. Examples

In Part 2 we illustrate our results, with three examples (finite group and algebraic, finite group and holonomic but non-algebraic, infinite group). The first example, which we treat in full detail, is that of Kreweras (see Figure 2). In Section 10 we obtain an expression for the GF in terms of Weierstrass ζ-functions. In Sections 11 and 12 we show how to derive the well-known expressions for Q(0, 0; z) and Q(x, 0; z) = Q(0, x; z) by the theory of transformation of elliptic functions. The second example is the simple walk (Figure 2), in Section 13. We close Part 2 by Section 14, which is devoted to an example of walk having an infinite group (Figure 8).

Proof. Observe that with (38), (85), and with the equalities

℘(-ω) = ℘(ω), ℘ ′ (-ω) = -℘ ′ (ω), we can write (86) f y (ω) = ℘ ′ (ω) 2z(℘(ω) -1/3)
.

The latter has a simple pole at 0, with residue -1/z (remember that in the neighborhood of 0, ℘(ω) = 1/ω 2 + O(ω 2 )). It has also poles at points where ℘(ω) -1/3 = 0. For the model under consideration, one has ℘(ω 2 /3) = 1/3, see [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF]Page 773]. Accordingly, ℘(2ω 2 /3) = 1/3 as well, and one concludes that ω 2 /3 and 2ω 2 /3 are the two remaining poles of f y (ω) on the fundamental rectangle. Making an expansion in (86), we deduce that the residues at ω 2 /3 and 2ω 2 /3 are equal to 1/(2z).

Remark 13. The function f y (ω) has a priori 6 poles (see Section 4). Lemma 12 shows that it may have strictly less than 6 poles.

The Weierstrass ℘-function with periods ω 1 , ω 2 can alternatively be characterized by its periods ω 1 , ω 2 (see ( 16)), or by its invariants g 2 , g 3 , by the formula

(87) ℘ ′ (ω) 2 = 4℘(ω) 3 -g 2 ℘(ω) -g 3 .
Lemma 14. For Kreweras' model, we have

(88) g 2 = 4/3 -32z 3 , g 3 = -8/27 + 32z 3 /3 -64z 6 .
Proof. The construction of the uniformization (see [START_REF] Fayolle | Random walks in the quarter-plane[END_REF] or [25, Page 770], and [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF] in this paper) is the following: with (85) one has ℘(ω) = g(x(ω)), where g(x) = 1/3 -4z 2 x. Then

g 2 = -4[g(x 1 )g(x 2 ) + g(x 1 )g(x 3 ) + g(x 2 )g(x 3 )], g 3 = 4g(x 1 )g(x 2 )g(x 3 ).
One concludes by computing the branch points above (which are the roots of the polynomial ( 14)) in terms of z.

r y (ω) = c+ 1 2z ζ 1,2 (ω +2ω 2 /3)- 1 z ζ 1,2 (ω +ω 2 /3)+ 1 z ζ 1,2 (ω)- 1 2z ζ 1,2 (ω -ω 2 /3), ∀ω ∈ C.
Theorem 9 also gives the expression of the constant c in (89), but we shall compute it in Section 12 only.

Proof. There are several ways to deduce Proposition 15. A first one is to use Theorem 9, which gives an expression for r y (ω): one should group some terms of (65) together in order to deduce ζ-functions and to exploit (78).

The second one is to apply Theorem 8, which only concerns the poles of the GF (and not its expression), combined with the ellipticity of r y (ω) proper to Kreweras' model. Namely, it is elementary to check the condition (79) of Proposition 10 using our analysis of poles of f y (ω) above. Then by Proposition 10 (see also [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Section 6]) r y (ω) is algebraic with 2k = 4 branches and hence elliptic with periods ω 1 , 2ω 2 . This remark allows us to study the poles of r y (ω) only in the parallelogram ω 1 [-1/2, 1/2) + ω 2 [-3/2, 1/2). According to Theorem 8, the poles of r y (ω) must satisfy N - d = ∅, where (we recall that ℜω

x 1 = ω 2 /2) N - d = {n 0 : d + nω 3 is a pole of f y (ω) with ω 2 /2 -kω 2 < ℜd + nω 3 < ω 2 /2}
. For Kreweras' model, one has ω 2 /ω 3 = 3/2, so that k = 2, and the only poles d of f y (ω) with -3ω 2 /2 < ℜd + nω 3 < ω 2 /2 and |ℑd| |ω 1 /2| are the points of the set

P = {-4ω 2 /3, -ω 2 , -2ω 2 /3, -ω 2 /3, 0, ω 2 /3}.
We thus have N - d = {n 0 : d + nω 3 ∈ P }, and it is obvious that the points of the parallelogram

ω 1 [-1/2, 1/2) + ω 2 [-3/2, 1/2) such that N - d = ∅
are among the points of P . Let us study closer each of them. We start with d ∈ {0, ω 2 /3}. We have N - d = {0}, and according to Theorem 8 and Lemma 12, we find the following principal parts of r y (ω):

R ω 2 /3,y (ω) = -F ω 2 /3,y (ω) = -1/(2z) ω -ω 2 /3 , R 0,y (ω) = -F 0,y (ω) = 1/z ω .
Consider now the cases d ∈ {-2ω 2 /3, -ω 2 /3}, for which one has

N - d = {0, 1}. Then R -ω 2 /3,y (ω) = -F -ω 2 /3,y (ω) -F ω 2 /3,y (ω + 2ω 2 /3) = -1/z ω + ω 2 /3 , R -2ω 2 /3,y (ω) = -F -2ω 2 /3,y (ω) -F 0,y (ω + 2ω 2 /3) = 1/(2z) ω + 2ω 2 /3 .
For the two remaining cases d ∈ {-4ω 2 /3, -ω 2 }, one has N - d = {0, 1, 2}, and similar computations as above show that

R -ω 2 ,y (ω) = R -4ω 2 /3,y (ω) = 0.
In other words, the points -4ω 2 /3 and -ω 2 are removable singularities of the GF r y (ω).

To conclude, we notice that the elliptic function r y (ω) with periods ω 1 , 2ω 2 has in the fundamental parallelogram ω 1 [-1/2, 1/2) + ω 2 [-3/2, 1/2) four poles, with principal parts given above. It is immediate from the theory of elliptic functions (in particular Property (P5)) that Equation (89) holds. The proof is completed.

Remark 16. Starting from (89), we can recover (29). Introduce

k(ω) = 1 2z ζ 1,2 (ω + ω 2 /3) - 1 z ζ 1,2 (ω) + 1 2z ζ 1,2 (ω -ω 2 /3).
An easy computation starting from (89) yields

r y (ω + ω 3 ) -r y (ω) = k(ω) + k(ω + ω 2 ). Since k(ω) is ω 1 , 2ω 2 elliptic (see Property (P4)), we deduce that k(ω) + k(ω + ω 2 ) is ω 1 , ω 2 elliptic, hence r y (ω + ω 3 ) -r y (ω) is ω 1 , ω 2 elliptic.
We first show that r y (ω + ω 3 )r y (ω) has the same poles as f y (ω) in ω 1 [0, 1) + ω 2 [0, 1). Since in ω 1 [0, 1) + ω 2 [0, 1), ζ 1,2 has only one pole (which is of order 1, at 0 and with residue 1, see Property (P1)), we obtain that in ω 1 [0, 1) + ω 2 [0, 1), r y (ω + ω 3 )r y (ω) has only simple poles, at 0, ω 2 /3 and 2ω 2 /3, with respective residues -1/z, 1/(2z) and 1/(2z). The same holds for f y (ω) (Lemma 12). Thus, there exists a constant c such that (90)

r y (ω + ω 3 ) -r y (ω) = c + f y (ω), ∀ω ∈ C.
Evaluating (90) at ω = ω 2 /2 and using that f y (ω 2 /2) = 0 (see Equation ( 86)), we obtain that c = r y (ω 2 /2 + ω 3 )r y (ω 2 /2) = k(ω/2) + k(3ω 2 /2). Using the fact that ζ 1,2 is odd and 2ω 2 -periodic, we obtain that c = 0, which yields (29).

Finding an algebraic expression for the Kreweras' GF of the excursions

In this section we prove the first part of Proposition 11 (Equation ( 83)). Surprisingly, we shall do it without finding the value of the additive constant c in (89).

11.1. Beginning of the proof. One has from (30) that

r x (ω) + r y (ω) -K(0, 0)Q(0, 0) -x(ω)y(ω) = 0, ∀ω ∈ C.
Setting ω y 0 = 2ω 2 /3, one has y(ω y 0 ) = 0; further, it turns out that x(ω y 0 ) = 0 (see ( 17) and (85)). Since K(0, 0) = 0 for Kreweras' model, one deduces that

r x (ω) x(ω) = y(ω) - r y (ω) -r y (ω y 0 ) x(ω) = y(ω) - r y (ω) -r y (ω y 0 ) ω -ω y 0 ω -ω y 0 x(ω) -x(ω y 0 )
.

Then, if ω → ω y 0 , one finds zQ(0, 0) = - r ′ y (ω y 0 ) x ′ (ω y 0 )
. By (85), x ′ (ω y 0 ) = ℘ ′ (2ω 2 /3)/(d ′′′ (0)/6). Since ℘(2ω 2 /3) = 1/3, using (87) and (88) leads to ℘ ′ (2ω 2 /3) = ±8z 3 . But ℘ ′ (ω) is positive on (ω 2 /2, ω 2 ), so that finally ℘ ′ (2ω 2 /3) = 8z 3 . Since d ′′′ (0)/6 = -4z 2 , we reach the conclusion that x ′ (ω y 0 ) = -2z. Finally, one finds

(91) Q(0, 0) = 1 4z 3 [℘ 1,2 (ω 2 /3) -℘ 1,2 (4ω 2 /3) + 2(℘ 1,2 (ω 2 ) -℘ 1,2 (2ω 2 /3))].
The difficulty now consists in transforming the above expression in an algebraic function of z. So far, we have already computed the values of ℘(ω) for some particular ω (e.g., we saw that ℘(ω 2 /3) = ℘(2ω 2 /3) = 1/3, and that ℘(0) = ℘(ω 2 ) = ∞). On the other hand, we never computed ℘ 1,2 (ω) for some given ω. To do so, the simplest thing is to express ℘ 1,2 (with periods ω 1 , 2ω 2 ) in terms of ℘ (with periods ω 1 , ω 2 ). This is the aim of the next section.

11.2. Intermezzo: transformation theory of elliptic functions. Let ℘ 1,2 be the Weierstrass elliptic function with periods ω 1 , 2ω 2 . Denote its invariants by g 1,2

2 and g 1,2 3 . We also define e 1,2 2 = ℘ 1,2 (ω 2 ), e 1,2 1 = ℘ 1,2 (ω 1 /2) and e 1,2 1+2 = ℘ 1,2 (ω 1 /2+ω 2 ). Note that the latter are the three solutions of 4X 3g 1,2 2 Xg 1,2 3 = 0. To compute the latter quantities, it is convenient to introduce r, r and r as the roots of (92) 4X 3g 2 X + g 3 = 0, with g 2 , g 3 defined as in Lemma 14. 8 We enumerate them in the following way: only one solution of (92) is a power series in z (see [START_REF] Stanley | Enumerative Combinatorics[END_REF]Proposition 6.1.8]), we call it r. It admits the expansion r = 2/3 -8z 3 -48z 6 -640z 9 + O(z 12 ).

Lemma 17. One has e 1,2 2 = r/2, g 1,2 2 = 15r 2 /4g 2 /4, g 1,2 3 = 11g 3 /32 -7rg 2 /32. Proof. Using the properties (P3) and (P9), one can write, for any ω ∈ C,

(93) ℘(ω) = ℘ 1,2 (ω) + ℘ 1,2 (ω + ω 2 ) -℘ 1,2 (ω 2 ) = -2℘ 1,2 (ω 2 ) + ℘ ′ 1,2 (ω) ℘ 1,2 (ω) -℘ 1,2 (ω 2 ) 2 .
We then make an expansion of the LHS and the RHS of the above equation in the neighborhood of 0; we obtain

1 ω 2 + g 2 20 ω 2 + g 3 28 ω 4 + O(ω 6 ) = 1 ω 2 + 3(e 1,2 2 ) 2 - g 1,2 2 5 ω 2 + 4(e 1,2 2 ) 3 - g 1,2 2 e 1,2 2 2 - 3g 1,2 3 14 ω 4 + O(ω 6 ).
Identifying the expansions above, we obtain two equations for the three unknowns e 1,2 2 , g 1,2 2 and g 1,2 3 (remember that g 2 and g 3 are known from Lemma 14). We add a third equation by noticing that e 1,2 2 is a root of 4X 3g 1,2 2 Xg 1,2 3 = 0. We then have a (non-linear) system of three equations with three unknowns. Some computations finally lead to the expressions of e 1,2 2 , g 1,2 2 and g 1,2 3 given in Lemma 17.

Remark 18. Contrary to g 2 and g 3 , g 1,2 2 and g 1,2 3 are not rational functions of z. However, they are algebraic (and so is e 1,2

2 ). Thanks to Lemma 17, one can consider that the function ℘ 1,2 is completely known, as its periods and its invariants are expressed in the variable z in an explicit way. The next result proposes an expression of ℘ 1,2 in terms of ℘.

Lemma 19. One has

2℘ 1,2 (ω) = ℘(ω) + e 1,2 2 ± (℘(ω) -e 1,2 2 ) 2 + g 1,2 2 -12(e 1,2 2 ) 2 , ∀ω ∈ C,
where e 1,2 2 and g 1,2 2 are as in Lemma 17. 9

Proof. We start from Equation (93), which can be rewritten as

(94) ℘(ω) = -2e 1,2 2 + (℘ 1,2 (ω) -e 1,2 1 )(℘ 1,2 (ω) -e 1,2 1+2 ) ℘ 1,2 (ω) -e 1,2 2 , ∀ω ∈ C.
8 It is worthwhile comparing these roots with ℘(ω2/2), ℘((ω2 + ω1)/2) and ℘(ω1/2), which are solutions to 4X 3 -g2X -g3 = 0. 9 The sign ± above depends on which half-parallelogram ω is located.

Further, we have the equalities (95) e 1,2 1 + e 1,2 1+2 + e 1,2 2 = 0, e 1,2 1 e 1,2 1+2 + e 1,2 1 e 1,2 2 + e 1,2 1+2 e 1,2 2 = -

g 1,2 2 4 .
To conclude, we solve Equation (94) as an equation (of the second order) in ℘ 1,2 (ω).

Making use of the identities (95), we obtain Lemma 19.

11.3. End of the proof. Using Lemma 19 and the fact that ℘(ω 2 /3) = ℘(2ω 2 /3) = 1/3, we obtain that

℘ 1,2 (ω 2 /3) = 1 2 (1/3 + r/2 + -2/9 -r/3 + r 2 + 8z 3 ), ℘ 1,2 (2ω 2 /3) = ℘ 1,2 (4ω 2 /3) = 1 2 (1/3 + r/2 --2/9 -r/3 + r 2 + 8z 3 ).
By (91), it follows that (96) Q(0, 0) = 1 4z 3 (-1/3 + r/2 + 2 -2/9r/3 + r 2 + 8z 3 ).

The GF Q(0, 0) is now expressed as an algebraic function of z (in (91) it was not clear).

To conclude, we notice that we can express r with W as follows (this can be achieved by computing the minimal polynomial of W + W 4 /4 starting from the minimal polynomial of W ):

r = 2 3 -4z 2 (W + W 4 /4).
It is now obvious that (96) implies (83).

Algebraic expression for the Kreweras' GF of walks ending on one axis

In what follows, we would like to express r y (ω) in terms of y(ω) (to eventually find (84)). To that purpose we notice that the function x(ω) is simpler than y(ω), see (85). Further, due to [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF]Equation (3.3)] and the symmetry of the model, we have y(ω) = x(ωω 3 /2). In other words, it is equivalent to express r y (ω) in terms of y(ω), or to express r y (ω + ω 3 /2) in terms of x(ω). Since ω 3 /2 = ω 2 /3, (89) implies that (97)

r y (ω + ω 3 /2) = c + 1 2z ζ 1,2 (ω -ω 2 ) - 1 2z ζ 1,2 (ω -2ω 2 ) + 1 z ζ 1,2 (ω -5ω 2 /3) - 1 z ζ 1,2 (ω -4ω 2 /3).
We shall then structure the proof as follows: in Section 12.1 we find the constant c in (89) (or equivalently in (97)). In Section 12.2, for computational reasons, we replace ζ 1,2functions by ℘ 1,2 -functions. In Section 12.3 we are interested in (needed) technical lemmas. Finally, in Section 12.4 we give the proof of Equation (84) of Proposition 11. 10 10 In Section 11, we have shown how our theoretical results work for finding an expression for Q(0, 0) in Kreweras' case. In Section 12 we now show how our methods also provide an expression for Q(x, 0) or Q(0, y). For conciseness, we decided to state all necessary intermediate results to obtain such an expression, but not to prove all of them.

12.1. Finding the constant. To find the constant c in (89), we could use Theorem 9, which gives the exact expression for r y (ω)r y (ω y 2 ). It is also possible to use the following property of Kreweras' model: for ω such that y(ω) = 0, we must have r y (ω) = 0. Indeed, remember that one has r y (ω) = zy(ω)Q(0, y(ω)). Since in this case y(2ω 2 /3) = y(ω 2 ) = 0, we immediately find

(98) c = 1 2z (ζ 1,2 (ω 2 /3) -ζ 1,2 (4ω 2 /3)) + 1 z (ζ 1,2 (ω 2 ) -ζ 1,2 (2ω 2 /3)).
12.2. Replacing the Zeta-functions by Pe-functions. With (97) and (98), the function r y (ω) is completely known. However, it would be more convenient to have ℘ 1,2functions instead of ζ 1,2 -functions in (97). To do so, we shall use (four times) the addition theorem (P3) in (89). Following this way, we obtain

r y (ω + ω 3 /2 -ω 2 /2) = r y (ω + ω 3 /2 + 3ω 2 /2) (99) = c + 1 2z (ζ 1,2 (ω + ω 2 /2) -ζ 1,2 (ω -ω 2 /2)) + 1 z (ζ 1,2 (ω -ω 2 /6) -ζ 1,2 (ω + ω 2 /6)) = c + ζ 1,2 (ω 2 /2) z - ℘ ′ 1,2 (ω 2 /2)/(2z) ℘ 1,2 (ω) -℘ 1,2 (ω 2 /2) - 2ζ 1,2 (ω 2 /6) z + ℘ ′ 1,2 (ω 2 /6)/z ℘ 1,2 (ω) -℘ 1,2 (ω 2 /6) .
12.3. Some technical computations. Equation (99) expresses r y (ω + ω 3 /2) in terms of one single function, namely, ℘ 1,2 (ω + ω 2 /2). This is why we now need to compute ℘ 1,2 (ω + ω 2 /2) in terms of x(ω). This will be done in Lemma 21. But before stating and proving this result, we first express x(ω + ω 2 /2) in terms of x(ω).

Lemma 20. One has

x(ω + ω 2 /2) = √ x 1 √ x 1 x(ω) + 1 x(ω) -x 1 , ∀ω ∈ C.
Proof. Introduce, as in the proof of Lemma 14, the function g(x) = 1/3 -4z 2 x. We have, for any ω ∈ C, ℘(ω + ω 2 /2) = e 2 + (e 2e 1 )(e 2e 1+2 ) ℘(ω)e 2 = g(x 1 ) + (g(x 1 )g(x 2 ))(g(x 1 )g(x 3 )) g(x(ω))g(x 1 ) .

Using the facts that x 1 + x 2 + x 3 = 1/(4z 2 ), x 1 x 2 x 3 = 1/4 and d(x 1 ) = 0, and after some computations, we obtain that

℘(ω + ω 2 /2) = (1/3 -4z 2 x 1 )x(ω) + (-x 1 /3 + 2z -2z 2 /x 1 ) 3(x(ω) -x 1 ) , ∀ω ∈ C.
Finally, using that x(ω + ω 2 /2) = g -1 (℘(ω + ω 2 /2)), we obtain Lemma 20.

In Section 11, we introduced r to be the only power series solution to 4X 3 -g 2 X +g 3 = 0 (Equation ( 92)). The two other solutions of (92) are Puiseux series, and we set r = -1/3 + 4z 3 -8z 9/2 + 24z 6 -84z 15/2 + 320z 9 + O(z 21/2 ), r = -1/3 + 4z 3 + 8z 9/2 + 24z 6 + 84z 15/2 + 320z 9 + O(z 21/2 ). Lemma 21. One has

(100) ℘ 1,2 (ω + ω 2 /2) = B 0 + B 1 x(ω) + √ A 0 1 -x(ω)W 2 12(x(ω) -x 1 )
, ∀ω ∈ C, where

(101) B 0 = -(2x 1 + 24z 2 √ x 1 + 3rx 1 ), B 1 = 3(r -r), A 0 = (B 0 + B 1 x 1 ) 2 1 -x 1 W 2 .
Proof. The first step of the proof of (100) consists in evaluating at ω + ω 2 /2 the expression in Lemma 19. Together with Lemma 20, this gives an expression of ℘ 1,2 (ω + ω 2 /2) in terms of x(ω). Some simplifications (that we do not write down here) eventually lead to (100).

Corollary 22. One has

(102) ℘ 1,2 (ω 2 /2) = B 1 12 , ℘ 1,2 (ω 2 /6) = √ A 0 -B 0 12x 1 .
Proof. We evaluate at ω = 0 the expression (100) of Lemma 21. Since x(ω) has a pole of order 2 at 0, the first part of Corollary 22 follows. We then evaluate (100) at ω = ω 2 /3. Since x(ω 2 /3) = 0, we obtain the second part of Corollary 22.

Because of Equation (99), we also need to have an expression of 1

/(℘ 1,2 (ω + ω 2 /2) - ℘ 1,2 (ω 2 /2)) and 1/(℘ 1,2 (ω + ω 2 /2) -℘ 1,2 (ω 2 /6)) in terms of x(ω). Lemma 23. One has (103) 1 ℘ 1,2 (ω + ω 2 /2) -℘ 1,2 (ω 2 /2) = 12 A 0 W 2 (B 0 + B 1 x 1 -A 0 1 -x(ω)W 2 ), ∀ω ∈ C,
as well as

(104) 1 ℘ 1,2 (ω + ω 2 /2) -℘ 1,2 (ω 2 /6) = 12x 1 C 1 x(ω) ( A 0 x 1 + (B 0 -A 0 + B 1 x 1 )x(ω) -x 1 A 0 1 -x(ω)W 2 ), ∀ω ∈ C, with (105) C 1 = 2x 1 B 1 B 0 -2B 1 A 0 x 1 -2 A 0 B 0 + x 2 1 B 2 1 + A 0 + B 2 0 .
Proof. The proof of both ( 103) and ( 104) is immediate, and just uses Lemma 21 and Corollary 22.

12.4. Conclusion. Using the expression (99) of r y (ω + ω 3 /2ω 2 /2), we obtain that with c defined as in (98), one has

r y (ω + ω 3 /2) = c+ ζ 1,2 (ω 2 /2) z - ℘ ′ 1,2 (ω 2 /2)/(2z) ℘ 1,2 (ω + ω 2 /2) -℘ 1,2 (ω 2 /2) - 2ζ 1,2 (ω 2 /6) z + ℘ ′ 1,2 (ω 2 /6)/z ℘ 1,2 (ω + ω 2 /2) -℘ 1,2 (ω 2 /6)
.

Using ( 103) and (104), we obtain that (106)

r y (ω + ω 3 /2) = α + β x(ω) + γ + δ x(ω) 1 -x(ω)W 2 ,
where

α = c + ζ 1,2 (ω 2 /2) z - 2ζ 1,2 (ω 2 /6) z - 6℘ ′ 1,2 (ω 2 /2)(B 0 + B 1 x 1 ) zA 0 W 2 (107) + 12x 1 ℘ ′ 1,2 (ω 2 /6)(B 0 - √ A 0 + B 1 x 1 ) C 1 z , β = 12x 2 1 √ A 0 ℘ ′ 1,2 (ω 2 /6) C 1 z , (108) γ = 6℘ ′ 1,2 (ω 2 /2) z √ A 0 W 2 , (109) δ = -12x 2 1 √ A 0 ℘ ′ 1,2 (ω 2 /6) C 1 z . (110) Lemma 24. One has α = 1/(2z), β = -1, γ = -1/W and δ = 1.
Proof. The proof of Lemma 24 is long, and is based on arguments similar to those already used in other proofs of Sections 10-12. For brevity, we omit it.

With Equation (106), Lemma 24, and since y(ω) = x(ω -ω 3 /2), the proof of Proposition 11 is completed.

A holonomic non-algebraic example: the simple walk

In this section we consider the simple walk (see on the left in Figure 2). This is an example of non-algebraic but holonomic model [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. We would like to illustrate the main theorem in this case. At the end of the section we will comment on the result given by the alternative approach (based on Section 9). 13.1. First derivation of the simple walk GF. We thus start by applying the formula (65) of Theorem 9. The most important quantity in (65) is the function f y (ω). The simple walk belongs to case 2 (classification of Section 4), so that f y (ω) has the following particularly simple expression f y (ω) =

x ′ (ω) 2z .

Lemma 25. For the simple walk, the poles of f y (ω) in the rectangle ω 1 [0, 1) + ω 2 [0, 1) are at ω 2 /8 and 7ω 2 /8. These poles are double, with respective principal parts equal to

1 4z 2 1 (ω -ω 2 /8) 2 , -1 4z 2 1 (ω -7ω 2 /8) 2 .
Proof. Our starting point is the formula

(111) x(ω) = x 4 + d ′ (x 4 ) ℘(ω) -d ′′ (x 4 )/6
, which is an immediate consequence of [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF]. The order of the Weierstrass function being equal to two, the function x(ω) has one pole of order two or two poles of order one in the fundamental rectangle ω 1 [0, 1) + ω 2 [0, 1). Let us first show that (112) ℘(ω 2 /8) = d ′′ (x 4 )/6.

We know that ℘(ω 2 /2) = g x (x 1 ). It remains to use the dissection formula twice and to simplify. It follows that ℘(7ω 2 /8) = d ′′ (x 4 )/6. Using (111) the function x(ω) has two simple poles in the fundamental rectangle. Then the residue at ω 2 /8 is given by d ′ (x 4 )/℘ ′ (ω 2 /8).

After simplifications we find -1/(2z). The first part of Lemma 25 follows. The second part of the lemma follows from the parity of x(ω).

Since ω 3 /ω 2 = 1/2 we have k = 1 and ℓ = 2 in (9). Moreover, with Lemma 25, the function f y (ω) has two poles f y i in the parallelogram Π 0,0ω x 1 , namely ±ω 2 /8, with corresponding principal part

±1 4z 2 1 (ω ∓ ω 2 /8) 2 .
We then deduce from Theorem 9 that (we recall that r y (ω) = y(ω)zQ(0, y(ω)) for the simple walk)

r y (ω) -r y (ω y 2 ) = ∞ p=-∞ ∞ n=0 - ⌊n/2⌋ + 1 4z 2 1 (ω + (n/2 -1/8)ω 2 + pω 1 ) 2 - ⌊n/2⌋ + 1 4z 2 1 (-ω + (n/2 -1/8 + 3/2)ω 2 + (p + 1)ω 1 ) 2 +2 ⌊n/2⌋ + 1 4z 2 1 (ω y 2 + (n/2 -1/8)ω 2 + pω 1 ) 2 + ⌊n/2⌋ + 1 4z 2 1 (ω + (n/2 + 1/8)ω 2 + pω 1 ) 2 + ⌊n/2⌋ + 1 4z 2 1 (-ω + (n/2 + 1/8 + 3/2)ω 2 + (p + 1)ω 1 ) 2 -2 ⌊n/2⌋ + 1 4z 2 1 (ω y 2 + (n/2 + 1/8)ω 2 + pω 1 ) 2 .
In particular we deduce from the above formula that the function r y (ω) has poles at any point of the form ω 2 /8 + nω 2 /4 + pω 1 , ∀n, p ∈ Z, except for n ∈ {1, 2, 3, 4}. All these poles are of order two. It is interesting to note that the coefficients in front of the principal parts (typically the ±(⌊n/2⌋ + 1)/(4z 2 )) are not bounded (they grow linearly in n). As a straightforward consequence, it is impossible for the function r y (ω) to be elliptic; this is directly related to the fact that the model is not algebraic. However, the linearity in n of the coefficients ±(⌊n/2⌋ + 1)/(4z 2 ) would allow us to express r y (ω) in terms of the quasi-elliptic function φ(ω) defined in (82), which is holonomic but not algebraic in y(ω). We shall not simplify the above expression so as to obtain an expression of Q(0, y) in terms of y: this is first because such expressions already exist in the literature, second because we have already illustrated in full detail our approach with Kreweras' example, the last reason is that the second approach (see below) would be more appropriate for this. 13.2. Second derivation of the simple walk GF. We now pass to the second approach, that of Section 9. The starting point is Equation (29), which says that r y (ω + ω 3 ) = r y (ω) + f y (ω). Applying it twice, we obtain

r y (ω + ω 2 ) = r y (ω) + f y (ω) + f y (ω + ω 2 /2), ∀ω ∈ C.
The above equation can be rewritten as (for all ω ∈ C), with φ(ω) as in (82),

r y (ω + ω 2 ) -φ(ω + ω 2 )[f y (ω + ω 2 ) + f y (ω + 3ω 2 /2)] = r y (ω) -φ(ω)[f y (ω) + f y (ω + ω 2 /2)].
In other words, the function

(113) r y (ω) -φ(ω)[f y (ω) + f y (ω + ω 2 /2)]
is elliptic with periods ω 1 , ω 2 . To find it, it is therefore enough to find its poles in the rectangle ω 1 [0, 1) + ω 2 [0, 1). First, thanks to Theorem 8, the function r y (ω) has only one pole in ω 1 [0, 1) + ω 2 [0, 1); it is double, with principal part equal to

-1 4z 2 1 (ω -ω 2 /8) 2 .
The function (113) has also poles due to the functions φ(ω), f y (ω) and f y (ω + ω 2 /2). It follows that (113) has poles at 0, ω 2 /8, 3ω 2 /8, 5ω 2 /8, 7ω 2 /8. At 0 in fact there is no pole. At ω 2 /8 the principal part is

-(1 + φ(ω 2 /8)) 4z 2 1 (ω -ω 2 /8) 2 + -φ ′ (ω 2 /8) 4z 2 1 ω -ω 2 /8 . At 3ω 2 /8 the principal part is φ(3ω 2 /8) 4z 2 1 (ω -3ω 2 /8) 2 + φ ′ (3ω 2 /8) 4z 2 1 ω -3ω 2 /8 .
At the point 5ω 2 /8 the principal part is equal to

-φ(5ω 2 /8) 4z 2 1 (ω -5ω 2 /8) 2 + -φ ′ (5ω 2 /8) 4z 2 1 ω -5ω 2 /8 .
With the same reasoning, the principal part at 7ω 2 /8 is Section 14 We conclude that the function ( 113) is equal to the following function (up to an additive constant), that we denote by R(ω):

φ(7ω 2 /8) 4z 2 1 (ω -7ω 2 /8) 2 + φ ′ (7ω 2 /8) 4z 2 1 ω -7ω 2 /8 . ✲ ✻ ✒ ✛ ❄ ✠ ✒ ✛ ✒ ❄ ✒ Figure 8. Model analyzed in
R(ω) = - (1 + φ(ω 2 /8)) 4z 2 ℘(ω -ω 2 /8) - φ ′ (ω 2 /8) 4z 2 ζ(ω -ω 2 /8) + φ(3ω 2 /8) 4z 2 ℘(ω -3ω 2 /8) + φ ′ (3ω 2 /8) 4z 2 ζ(ω -3ω 2 /8) - φ(5ω 2 /8) 4z 2 ℘(ω -5ω 2 /8) - φ ′ (5ω 2 /8) 4z 2 ζ(ω -5ω 2 /8) + φ(7ω 2 /8) 4z 2 ℘(ω -7ω 2 /8) + φ ′ (7ω 2 /8) 4z 2 ζ(ω -7ω 2 /8),
where all elliptic functions above have the periods ω 1 , ω 2 . Finally, Equation (113) says that (up to an additive constant)

r y (ω) = φ(ω)[f y (ω) + f y (ω + ω 2 /2)] + R(ω), ∀ω ∈ C.
We do not pursue the computations which would allow us to obtain an expression of Q(0, y) in terms of y. This would follow from similar computations as those done concerning Kreweras' case.

To conclude, let us mention that the fact-already observed-that the function r y (ω) has no bounded coefficients in the principal parts comes from the identity φ(ω + nω 2 ) = n + φ(ω), see (3 φ ).

An infinite group case example

In this section we treat the infinite group case S = {(-1, 0), (-1, -1), (0, -1), (1, 1)}, as on Figure 8. We use the formula (65) of Theorem 9, so we first need to study the poles of f y (ω).

Lemma 26. For the walk of Figure 8, the poles of f y (ω) in the rectangle ω 1 [0, 1) + ω 2 [0, 1) are at 0, ω 3 /2 ∈ (0, ω 2 /2) and ω 2 -ω 3 /2 ∈ (ω 2 /2, ω 2 ). These poles are simple, with residues equal to -1/z, 1/(2z) and 1/(2z), respectively.

Proof. The poles of f y (ω) = x(ω)[y(-ω + 2ω x 2 )y(ω)] can be only at points ω such that x(ω) = ∞, y(ω) = ∞ or y( ξω) = y(-ω + 2ω x 2 ) = ∞. Since the degree of d(x) in ( 14) is three in this example, we have x 4 = ∞, so that there is only one point in the fundamental parallelogram for which x(ω) = ∞, this is ω x 4 . We have x(ω x 4 ) = ∞ and y(ω x 4 ) = 0. It comes from similar arguments that the only point with y(ω) = ∞ is ω y 4 = ω x 4 + ω 3 /2. At this point the equalities y(ω y 4 ) = ∞ and x(ω y 4 ) = 0 hold.

If now y( ξω) = ∞, then x( ξω) = x(ω) = 0, and then either y(ω) = ∞ or y(ω) = -1, so that ω y 4 -ω 3 = ω x 4 -ω 3 /2 is the unique point with y( ξω) = ∞. We have x(ω x 4 -ω 3 /2) = 0 and y(ω x 4ω 3 /2) = -1.

It is easy to verify that all three points ω x 4ω 3 /2, ω x 4 , ω x 4 + ω 3 /2 = ω y 4 are poles of f y (ω) and by the alternative formula (according to the classification of Section 4, the model on Figure 8 belongs to case 1)

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

x(ω)

of Lemma 3, they are of the first order, and have the residues as given in the statement of the lemma.

There are three poles in Π 0,0ω x 1 , namely ±ω 3 /2 and 0. Let us call them f y ± and f y 0 . We have by ( 65 It is possible to make some simplifications in the above formulas, for instance thanks to the fact that A f y + s,p,n+1 (ω) and A f y s,p,n (ω) are very similar. However, there are no major simplifications or cancellations, and it is difficult to say more, since k and ℓ in the formula ω 3 /ω 2 = k/ℓ vary with z in a complicated way.

In the same way the poles of f x (ω) in the rectangle ω 1 [0, 1) + ω 2 [0, 1) are at 0, ω 3 /2 ∈ (0, ω 2 /2) and ω 3 ∈ (0, ω 2 ). These poles are simple, with residues equal to 1/2z, -1/z and 1/2z, respectively. Then there are three poles in Π 0,0 + ω y 1 , namely ω 2 + ω 3 /2 ± ω 3 /2 and ω 2 + ω 3 /2 that we call f x ± and f x 0 . We have that for the 51 non-singular walks with an infinite group (4), the GFs are holonomic for all z ∈ H (though the trivariate GF Q(x, y; z) is not holonomic).

In these two examples of use, [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Theorem 4.4.1] was used to answer to Problem (II), stated at the very beginning of this article (i.e., to give some qualitative informations on the GFs). Later on, we realized that the same theorem could also be used to solve Problem (I), on an explicit expression for the GFs. The idea consists in using the two following facts simultaneously:

• With the exception of w, all the functions in (116) could be found (in particular, their poles could be computed) by using the same approach (via Galois theory) as in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Chapter 4]. As for w, its only known properties are that for all ω ∈ C, w(ω) = w(ω + ω 1 ), (117)

w(ω) = w(ω 2 -ω), (118)
w(ω) = w(ωω 3 ). (119) Equations ( 117), ( 118) and (119) are proved in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Lemma 4.3.3], [9, Theorem 4.3.1] and [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Lemma 4.3.3], respectively. Below we shall give some consequences of these three equations, but before we pass to the second fact.

• For z ∈ (0, 1/|S|), r x (ω) is a GF which is analytic on {ω ∈ C : |x(ω)| < 1}, see [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF]. Therefore, it cannot have any singularities in the part of the fundamental parallelogram Π 0,0 where |x(ω)| < 1.

For these reasons, the role of the function w(ω) is to compensate for the possible poles which appear because of w 1 (ω), Φ(ω)φ(ω) and 1/s(ω) in (116). We now show how this compensation property of w(ω) can lead to eventually determine it. The function w(ω) is ω 1 , ω 3 elliptic ((117) and (119)). Further, with (118), we obtain that the function v(ω) = w(ω + ω 2 /2) is even and ω 1 , ω 3 elliptic. Using Property (P8), we reach the conclusion that there exists a rational function R such that v(ω) = R(℘(ω; ω 1 , ω 3 )). This way, we obtain the existence of a rational function R such that (120) w(ω) = R(℘(ωω 2 /2; ω 1 , ω 3 )), ∀ω ∈ C.

Next, instead of finding an expression for r x (ω) given in (116), we can be interested in the following weaker problem: finding a rational function R such that, with w(ω) defined as in (120), the function r x (ω) has no pole in the domain {ω ∈ C : |x(ω)| < 1} ∩ Π 0,0 . To be able to find R, we need to overcome three difficulties: The function f above is elliptic if and only if 1 ℓ p r ℓ = 0. (P5) Let f be an elliptic function with periods ω, ω such that in the fundamental rectangle ω[0, 1) + ω[0, 1), 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 (121) holds. (P6) Let f be an elliptic function with periods ω, ω such that in the fundamental rectangle ω[0, 1)+ ω[0, 1), f has poles at ω 1 , . . . , ω p , with principal parts F 1 , . . . , F p :

F i (ω) = n i k=1 r i,k (ω -ω i ) k ,
∀i ∈ {1, . . . , p}, ∀ω ∈ C.

Then up to an additive constant, we have the equality

f (ω) =

i

  and ℑω * * = ℑp (0) i . Then due to ω 2 -periodicity of f y (ω), (48) C 5 = sup ℑω=ℑω * or ℑω=ℑω * * |f y (ω)| < ∞. It follows from (29) that r y (ω) does not have poles at points ω ∈ C such that ℑω ∈ {ℑω * , ℑω * * }, and in particular (49) C 6 = sup ℑω=ℑω * or ℑω=ℑω * * , ℜω -ℜω ℜω + |r y (ω)| < ∞.

Lemma 7 .

 7 A point d is a pole of r y (ω) in ∆ if and only if it is a pole of the function f y (ω) in ∆ with ℜd < ℜω x 1 . Furthermore, at such a point d, (58) R d,y (ω) = -F d,y (ω), ∀ω ∈ C. A point d ′ is a pole of r y (ω) + f y (ω) in ∆ if and only if it is a pole of f y (ω) in ∆ with ℜd ′ > ℜω x 1 .

  Furthermore by (30), at ω = d, (59) r y (ω) = -r x (ω) + Q(0, 0)K(0, 0) + x(ω)y(ω). Then necessarily x(d)y(d) = ∞, from where y(d) = ∞. By assertion (i) above, we have either ℜd < ℜω x 1 or d = ω x 1 + pω 1 with some p ∈ Z. The last fact is impossible since for none of the models, lim x→x 1 Y (x) = ∞ and simultaneously lim x→x 1 xY (x) = ∞ (remember that x 1 is a branch point of Y (x) with |x 1 | < 1). Hence ℜd < ℜω x 1 . Consider now ξd. We have |x( ξd)| = |x(d)| < 1, so that ξd ∈ ∆ x ⊂ ∆ and ℜ( ξd) = ℜ(-d + 2ω x 2 ) > ℜω x 1 . Then again by (i), y( ξd) = ∞, so that x(d)y( ξd) = ∞. Then f y (ω) = x(ω)[y( ξω)y(ω)] has a pole at ω = d. Furthermore by (59), one has (60)

x 1 .

 1 By (i) one has y( ξd) = ∞, so that x(d)y( ξd) = ∞. The point d being a pole of f y (ω), it follows that x(d)y(d) = ∞. By (59), d is a pole of r y (ω) in ∆. Finally, (60) implies (58).

Proof.

  Let d be a pole of r y (ω) with ℜd < ℜω y 1 . Let us first prove that N - d = ∅. Assume first that in addition d ∈ ∆. By Lemma 7, d is a pole of f y (ω) in ∆ and ℜd < ℜω x 1 , so that N - d = ∅. Let now d be a pole of r y (ω) with ℜd < ℜω y 1 , but d ∈ ∆. In what follows, we shall denote the domains of C on the left of ∆ by D -and on the right of ∆ by D + . Then d ∈ D -. By (29), we have that for any ω ∈ D -, (63)

  r x (ω) = (r y (ω 0 y )r y (ω y 2 )) -(r y (ω)r y (ω y 2 )) + x(ω)y(ω). (70) Proof. Denote by

m→∞ d i

  ∈Pm poles of ry{R d i ,y (ω) -R d i ,y (ω y 2 )} = lim m→∞ d i ∈Pm poles of ry ℜd i <ℜωy 1 {R d i ,y (ω) + R d i ,y (-ω + 2ω y 2 ) -2R d i ,y (ω y 2 )} . (71) By Theorem 8 (i), for any d pole of r y (ω) with ℜd < ℜω y 1 , we have N - d = ∅. Then for any ω ∈ C, (72) d i ∈Pm poles of ry ℜd i <ℜωy 1

10. 3 .

 3 Expression of the GFs. Applying Theorem 9 to Kreweras' walks, we first obtain an expression of r y (ω) in terms of special functions. In what follows, we denote by ζ 1,2 and ℘ 1,2 the Weierstrass ζ-and ℘-functions with periods ω 1 , 2ω 2 . Proposition 15. One has (89)

1 +2 1 .

 11 )r y (ω)r y (ω y 2 ) = ∞ ,n (ω) + A f y s,p,n (ω) + A f y 0 s,p,n (ω) ,where (using the fact that (ω1 + ω 2 + ω 3 )/2 = ω y 2 ) A f y + s,p,n (ω) = -⌊n/ℓ⌋ + 1 2z 1 ω + sω 2 + (n -1/2)ω 3 + pω 1 (s + 1)ω 2 + (n + 1/2)ω 3 + (p + 1)ω 1/2)ω 2 + nω 3 + (p + 1/2)ωThe formula for A f y s,p,n (ω) is the same as (114) with the n in the denominator (and only there!) be replaced by n + 1. The formula for A f y 0 s,p,n (ω) is the same as (114) provided that the n in the denominator be replaced by n + 1/2 and (2z) by (-z). The function r y (ω) has thus poles at any point of the form sω 2 + nω 3 /2 + pω 1 , ∀s, n, p ∈ Z.

r x (ω) -r y (ω x 2

 2

( i )

 i We first have to compare the domain {ω ∈ C : |x(ω)| < 1} ∩ Π 0,0 with a translated fundamental parallelogram ω 1 [0, 1) + ω 3 [0, 1). Indeed, since w(ω) is elliptic with periods ω 1 , ω 3 , to determine it we need to know its poles in a translated parallelogram of ω 1 [0, 1) + ω 3 [0, 1).(ii) If, in point (i), {ω ∈ C : |x(ω)| < 1} ∩ Π 0,0 contains a translated fundamental parallelogram ω 1 [0, 1) + ω 3 [0, 1), then we have to deduce from the expressions of w 1 (ω), Φ(ω)φ(ω) and 1/s(ω) the zeros and poles that w(ω) should have in a translated parallelogram of ω 1 [0, 1) + ω 3 [0, 1). (P4) For given ω 1 , . . . , ω p ∈ C, define (121) f (ω) = c + 1 ℓ p r ℓ ζ(ωω ℓ ), ∀ω ∈ C.

  1 ζ(ωω i ) + p i=1 n i k=2 r i,k ℘ (k-1) (ωω i ), ∀ω ∈ C,where ℘ (k) means the k-th derivative of ℘, and where the ζ and ℘ functions above have the same periods ω, ω. (P7) Let f and g be non-constant elliptic functions with the same periods ω, ω. Then there exists a non-zero polynomial P such that P (f (ω), g(ω)) = 0, for all ω ∈ C. (P8) Let f be an even elliptic function with periods ω, ω, and let ℘ be the Weierstrass elliptic function with periods ω, ω. Then there exists a rational function F such that f (ω) = F (℘(ω)), for all ω ∈ C. (P9) Let p be some positive integer. The Weierstrass elliptic function with periods ω, ω/p can be written in terms of ℘ as℘(ω) + 1 ℓ p-1 {℘(ω + ℓ ω/p) -℘(ℓ ω/p)}, ∀ω ∈ C. (P10) The function ζ is quasi-periodic, in the sense that ζ(ω + ω) = ζ(ω) + 2ζ(ω/2), ζ(ω + ω) = ζ(ω) + 2ζ( ω/2), ∀ω ∈ C.(P11) Assume that ω is real and ω purely imaginary. We haveζ(ω/2) ωζ( ω/2)ω = iπ. (P12) The sum of the residues of an elliptic function in a fundamental parallelogram is zero. Proof. Property (P1) is proved in [28, Sections 20.2 and 20.4]. (P2) is known as Liouville's theorem, and can be found in [28, Section 20.1]. The addition theorems (P3) are stated in [26, Equations (5.5.3) and (5.5.16)]. For Properties (P4) and (P5), we refer to [28, Section 20.52]. (P6) is the subject of [15, Theoerem 3.14.4]. (P7) is shown in [28, Section 20.54], and (P8) in [28, Section 20.51]. (P9) can be found in [28, Example 9 in page 456]. Property (P11) is demonstrated in [26, Equation (5.5.19]. Finally, (P10) is proved in [28, Section 20.41], and (P12) is proved in [28, Section 20.12].

  p|ω 1 |} for any p ∈ Z + . Let us estimate |r y (ω)| on their segments bounded by the intersection points with V + m and V - m . By (29), (34), (48) and (49) the following bound holds true for any p ∈ Z + :

	(50)	sup ω∈H * p ∪H * * ℜω --mω 3 ℜω ℜω + +mω 3 p ,	|r y (ω)| =	sup

ℑω=ℑω * or ℑω=ℑω * * , ℜω --mω 3 ℜω ℜω + +mω 3

|r y (ω)| C 6 + mC 5 < ∞.

Let (p m ) m 1 be any sequence of integers strictly increasing to infinity as m → ∞ and such that p m m. Let us construct the parallelograms P m 's bounded by V + m , V - m , H * pm and H * * pm , which are defined above. Properties (i), (ii) and (iii) are trivially satisfied for these P m 's. The estimate (44) is ensured by (

  a pole of r y (ω), then either dtω 3 is a pole of f y (ω) for some t ∈ {1, . . . , n -1} (then of course ℜdtω 3 > ℜω x 1 , since dtω 3 ∈ D

+ ), or dnω 3 is a pole of f y (ω) + r y (ω). By Lemma 7, the last fact is possible if and only if dnω 3 is a pole of f y (ω) in ∆ with ℜ(dnω 3 ) > ℜω x 1 . Hence N + d = ∅. By (

That is, four points such that the two branches of X(y) are equal.

This additive constant is not a problem, since we can use the duality of Q(x, 0) and Q(0, y) to find it; see Theorem 1, where we already used this idea.

Acknowledgments

We would like to thank Alin Bostan for interesting discussions and an anonymous referee for very useful comments and suggestions.

10. Expression of Kreweras' GF in terms of Weierstrass elliptic functions 10.1. A guide for the next three sections. In Sections 10, 11 and 12, we illustrate our computational results on the example of Kreweras' model. The step set S of this model can be seen on Figure 2. We decompose this illustration into three steps. The first one (Section 10) consists in deriving from Theorems 8 and 9 an expression for the function r y (ω) = zy(ω)Q(0, y(ω)) in terms of Weierstrass ζ-functions, see Proposition 15. This expression is new, up to our knowledge. The second step (Section 11) is to show how obtaining from this expression an algebraic function of the series of the excursions Q(0, 0). Finally (Section 12), we explain how to find an algebraic expression for Q(y, 0) = Q(0, y).

Proposition 11 ([2, 5, 6, 9, 13, 14, 17]). Consider Kreweras' walks. Let W be the only power series in z satisfying

Further, one has

(Of course, ( 83) is an immediate consequence of (84), but in order to illustrate our approach, we shall first prove (83), and then (84).) There already exist many proofs of Proposition 11. The first one was proposed by Kreweras himself [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF]. See also Flatto and Hahn [START_REF] Flatto | Two parallel queues created by arrivals with two demands[END_REF] and Flatto [START_REF] Flatto | Two parallel queues created by arrivals with two demands[END_REF], where methods using elliptic functions were used (see also [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Section 4.6], where similar ideas are used). More recently, proofs were done in [START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], using an extension of the well-known kernel method. Finally, in [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF], there is a proof based on a guessing-proving approach (which is also applied to Gessel's walks). 10.2. Uniformization in Kreweras' case. The function f y (ω) defined in (38)-which appears in the meromorphic continuation procedure (29)-will be particularly important. To compute it, we need to simplify the coordinates of the uniformization x(ω), y(ω) in [START_REF] Kreweras | Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers[END_REF]. In the case of Kreweras, x 4 = y 4 = ∞, and one has (85) [START_REF] Flatto | Two parallel queues created by arrivals with two demands[END_REF]. We recall that in (85), ℘(ω) denotes the Weierstrass elliptic function with periods ω 1 , ω 2 , see ( 15) and ( 16). We shall sometimes write, instead, ℘(ω; ω 1 , ω 2 ). Finally, we recall that with ω 3 defined as in [START_REF] Kurkova | Explicit expression for the generating function counting Gessel's walks[END_REF], in the case of Kreweras one has ω 3 /ω 2 = 2/3 (this in particular implies that the group (4) has order 6). To apply our main results (Theorems 8 and 9), we need to know where the poles of f y (ω) are located.

Lemma 12. In the fundamental rectangle ω 1 [0, 1) + ω 2 [0, 1), the function f y (ω) has poles at 0, ω 2 /3 and 2ω 2 /3. These poles are simple, with residues equal to -1/z, 1/(2z) and 1/(2z), respectively.

where

The formula for B

is the same as (115) provided that the n in the denominator be replaced by n + 1. The formula for B f 0 x s,p,n (ω) is the same as (115) provided that the n in the denominator be replaced by n + 1/2 and (2z) by (-z).

Finally, there are two points ω 0 x ∈ Π 0,0 such that x(ω x 0 ) = 0, these are ω 3 /2 and ω 2 -ω 3 /2. There are also two points ω 0 y ∈ Π 0,0 + ω 3 /2 such that y(ω y 0 ) = 0, these are ω 3 and ω 2 . Due to [START_REF] Fayolle | Random walks in the quarter plane with zero drift: an explicit criterion for the finiteness of the associated group. Markov Process[END_REF], [START_REF] Flajolet | Analytic combinatorics[END_REF] with any of these two points ω 0

x and any of these two ω 0 y , we obtain Q(x(ω), 0, z) and Q(0, y(ω), z).

Appendix A. Another possible approach

In this section we discuss another approach which could also lead to expressions for r x (ω) and r y (ω) on the universal covering. Contrary to the representations in terms of infinite series of meromorphic functions we obtain in Theorem 9, the expressions for the GFs we could obtain following this alternative approach would be directly in terms of elliptic functions. This other approach is based on methods proposed in [9, Chapter 4], and it could be applied in principle to any model of walks with non-singular set of increments S and any z ∈ H. The difficulty of obtaining in this way closed formulas substantially depends on the values of S and z. Moreover, this method does not produce explicit representations that can be unified for all models and all z ∈ H, contrary to the one preferred in this paper.

We sketch this alternative approach below. It heavily relies on [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Theorem 4.4.1] . This theorem states that if ω 2 /ω 3 is rational, the function r x (ω) can be written as

where w 1 (ω) and s(ω) are rational functions in the variable x(ω), while φ(ω) and w(ω) are algebraic in x(ω). Further, in [10, Lemma 2.1] it is shown that Φ(ω) is holonomic (but not algebraic) in x(ω). Notice that [9, Theorem 4.4.1] is proved for z = 1/|S| only, but in [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF] it is observed that this result also holds for all z ∈ (0, 1/|S|). Theorem 4.4.1 of [START_REF] Fayolle | Random walks in the quarter-plane[END_REF] has already been used in [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF] to give another proof, after [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], that the 23 walks having a finite group of the walk have holonomic GFs. It has also been shown in [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF] that for the five models with a finite group and a positive covariance

(including Kreweras' and Gessel's models), Φ(ω) is identically zero. This implies that these models have algebraic GFs. Finally, [9, Theorem 4.4.1] was also applied in [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] to show (iii) Finally, we have to deduce from (ii) an expression for the rational function R and an expression for ℘(ωω 2 /3; ω 1 , ω 3 ) in terms of x(ω).

Item (i) is difficult to prove-though purely technical. The difficulty of item (ii) depends on the expression of the functions w 1 (ω), Φ(ω)φ(ω) and 1/s(ω) in (116). In the general case they are quite complicated, so that it is almost impossible to obtain an expression for R (this explains why we chose another approach in this article). However, in some particular cases, it may happen that these functions are simple to deal with, see just below for Kreweras' example. Item (iii) is doable, and similar computations are done for Kreweras' case (Sections 10-12).

To conclude Section A, we have a closer look at Kreweras' example. One could show that the following choices 11 are suitable: w 1 (ω) = -1/x(ω), Φ(ω)φ(ω) = 0 and 1/s(ω) = 1. We could then show that the function R has the following simple form

To find β, we could use the same idea as in Theorem 9. Then it would remain to express ℘(ωω 2 /3; ω 1 , ω 3 ) in terms of x(ω). For this we could use the same ideas and techniques as in Sections 10-12.

Appendix B. Some properties of elliptic functions

In this appendix, we gather the results we used on Weierstrass ℘-and ζ-functions.

Lemma 27. Let ζ and ℘ be the Weierstrass functions with certain periods ω, ω.

(P1) We have the expansion

As for the expansion of ℘(ω), it is given in [START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF]. In particular, in the fundamental rectangle ω[0, 1) + ω[0, 1), ζ (resp. ℘) has a unique pole. It is of order 1 (resp. 2), at 0, and has residue 1 (resp. 0, and principal part 1/ω 2 ). (P2) An elliptic function with no poles in the fundamental rectangle ω[0, 1) + ω[0, 1) is constant. (P3) We have the addition theorems

11 It is worth noting that there is no uniqueness of w1(ω) and 1/s(ω), as if we add some constants to the latter, we can subtract them in w(ω).