FR ÉD ÉRIC Alin Bostan

MARK VAN HOEIJ Manuel Chyzak

AND Lucien Kauers

Pech

HYPERGEOMETRIC EXPRESSIONS FOR GENERATING FUNCTIONS OF WALKS WITH SMALL STEPS IN THE QUARTER PLANE

Keywords: Walks in the quarter plane, Generating functions, Hypergeometric functions MSC2010: Primary 05A15, 14N10, 33F10, 68W30, Secondary 33C05, 97N80, 11J89

We study nearest-neighbors walks on the two-dimensional square lattice, that is, models of walks on Z 2 defined by a fixed step set that is a subset of the non-zero vectors with coordinates 0, 1 or -1. We concern ourselves with the enumeration of such walks starting at the origin and constrained to remain in the quarter plane N 2 , counted by their length and by the position of their ending point. Bousquet-Mélou and Mishna [Contemp. Math., pp. 1-39, Amer. Math. Soc., 2010] identified 19 models of walks that possess a D-finite generating function; linear differential equations have then been guessed in these cases by Bostan and Kauers [FPSAC 2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201-215, 2009]. We give here the first proof that these equations are indeed satisfied by the corresponding generating functions. As a first corollary, we prove that all these 19 generating functions can be expressed in terms of Gauss' hypergeometric functions that are intimately related to elliptic integrals. As a second corollary, we show that all the 19 generating functions are transcendental, and that among their 19 × 4 combinatorially meaningful specializations only four are algebraic functions.

Introduction

Context. An important problem in enumerative combinatorics is the study of lattice walks in restricted lattices. Many efforts have been deployed in recent years for classifying them, see e.g. the surveys [START_REF] Humphreys | A history and a survey of lattice path enumeration[END_REF] and [START_REF] Krattenthaler | Lattice path enumeration[END_REF] and the references therein. The generating functions of lattice walks are not only intriguing for combinatorial reasons, but also from the perspective of computer algebra. For combinatorial reasons they are interesting because, depending on the choice of admissible steps, the generating functions may have quite different algebraic and analytic properties. For computational reasons they are interesting because their descriptions (whether by a polynomial or by a linear differential equation, as we will see below) are sometimes so large in size that it becomes difficult to handle them with a reasonable efficiency.

In the present article, we consider small step walks restricted to the quarter plane, defined as follows. Let S = ∅ be a fixed subset of {-1, 0, 1} 2 \ {(0, 0)}, which will contain all steps allowed in the walks. An S-walk of length n starts at the origin (0, 0) and consists of n consecutive steps, where a step from a point A to a point B is admitted if B -A ∈ S, and both A and B belong to the quarter plane N 2 . These walks are called restricted to the quarter plane because they are not allowed to step out of it, and with small steps because a single step changes the position by no more than 1 in each coordinate. As an example, for S = {(1, 1), (-1, 0), (0, -1)} (Kreweras walks), a possible walk of length six is (0, 0) → (1, 1) → (2, 2) → (1, 2) → (2, 3) → (2, 2) → (2, 1).

A brute-force enumeration with rejection shows that, altogether, there are 125 different walks of length six for this particular step set. In the general case of an arbitrary step set S, with q n denoting the number of different S-walks of length n, we are interested in the generating function

Q(t) := ∞ n=0 q n t n ∈ Q[[t]].
The generating function Q(t) corresponding to the example step set S above is algebraic [START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF][START_REF] Gessel | A probabilistic method for lattice path enumeration[END_REF][START_REF] Kreweras | Sur une classe de problèmes liés au treillis des partitions d'entiers[END_REF], i.e., it satisfies a polynomial equation P (t, Q(t)) = 0 for some P ∈ Q[t, T ] \ {0}. But this is not the case for all other step sets. Still, among those step sets that induce a transcendental (i.e., non-algebraic) generating function Q(t), some have a Q(t) that is D-finite, i.e., that satisfies a linear differential equation with polynomial coefficients. The step set S = {(1, 1), (-1, 1), (0, -1)} is an example for this case [START_REF] Bousquet-Mélou | Counting walks in the quarter plane[END_REF][START_REF] Bousquet | Walks confined in a quadrant are not always D-finite[END_REF]. Finally, there are also step sets whose corresponding generating function is not even D-finite; Mishna and Rechnitzer [START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF] proved that this is the case for example when S = {(-1, 1), [START_REF] Andrews | Special functions, volume 71 of Encyclopedia of Mathematics and its Applications[END_REF][START_REF] Andrews | Special functions, volume 71 of Encyclopedia of Mathematics and its Applications[END_REF], (1, -1)}.

More generally, for a fixed step set S, one is interested in the study of the trivariate power series

Q(x, y; t) = ∞ n=0 ∞ i,j=0
q i,j;n x i y j t n , where q i,j;n denotes the number of S-walks of length n starting at (0, 0) and ending at (i, j). The power series Q(x, y; t) is called the complete generating function for S-walks. Note that the counting series Q(t) introduced before is nothing but the specialization Q(1, 1; t) of Q(x, y; t) at (x, y) = (1, 1). Other combinatorially meaningful specializations are Q(0, 0; t), the generating function of S-walks returning to the origin (also called excursions), Q(1, 0; t), the generating function of S-walks ending on the horizontal axis, and Q(0, 1; t), the generating function of S-walks ending on the vertical axis.

Bousquet-Mélou and Mishna [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF] have undertaken a systematic classification of the 256 step sets S ⊆ {-1, 0, 1} 2 \ {(0, 0)}, from the viewpoint of structural properties of the generating function Q(x, y; t). Again, the concerned properties are algebraicity and D-finiteness, yet applied to a multivariate setting 1 . They found out that there are 79 inherently different and nontrivial models to consider, of which they recognized 22 models for which Q(x, y; t) is D-finite; a 23rd model, of the so-called Gessel walks, was proved to be D-finite (and even algebraic) by Bostan and Kauers [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]. These 23 models share the feature that a certain group associated to S is finite. In the remaining 56 cases, it has been proved that the groups are infinite [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF], and that the complete generating functions Q(x, y; t) are not D-finite [START_REF] Bostan | Non-D-finite excursions in the quarter plane[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].

Of the 23 D-finite generating functions, 4 were recognized to be algebraic [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]: one corresponds to the Kreweras model S = {(1, 1), (-1, 0), (0, -1)}, one to its reverse S rev = {(-1, -1), (1, 0), (0, 1)}, one to S ∪ S rev , and one to Gessel's. All the other 19 generating functions were proved to be transcendental [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF], although some of their specializations are algebraic, e.g., for S = {(-1, 0), (0, 1), (1, -1)} [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]. These 19 models form the main object of this article; they are depicted in the third column of Table 1.

OEIS [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF] S N (x, y) S(x, y) 1 A005566 (x -x) (y -ȳ) y + (x + x) + ȳ 2 A018224 (x + x)y + (x + x)ȳ 3 A151312 (x + 1 + x)y + (x + 1 + x)ȳ 4 A151331 (x + 1 + x)y + (x + x) + (x + 1 + x)ȳ 5 A151266

(x -x) y -1 x +

x ȳ (x + x)y + ȳ 6 A151307 (x + x)y + (x + x) + ȳ 7 A151291

(x -x) y - 1. The 19 models (x = x -1 , ȳ = y -1 ) and the corresponding rational functions N and S in Eq. [START_REF] Arquès | Dénombrements de chemins dans R 2 soumis à contraintes[END_REF]. Cases 1-16 are numbered as in [11, Table 1]. Cases 17 and 18 are #1 and #2 in [11, Table 2]. Case 19 is #1 in [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]Table 3]. The OEIS tags correspond to coefficient sequences of the length generating function Q(t) = Q(1, 1; t). 2 F 1 ( 1 2 , 1 2 ; 1; w)

16t 2 10 2 F 1 ( 1 4 , 3 4 ; 1; w) 64t 2 (t 2 +t+1) (12t 2 +1) 2
Table 2. Hypergeometric series occurring in explicit expressions for Q(x, y; t). The 2 F 1 are given up to contiguity and derivation, that is, up to integer shifts of the parameters.

The proofs of D-finiteness given by Bousquet-Mélou and Mishna are implicit (i.e., qualitative): the existence of differential equations satisfied by the generating functions Q(x, y; t) was shown without obtaining the differential equations explicitly. On the other hand, Bostan and Kauers [5,[START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF] provided explicit differential equations for (specializations of) the 23 D-finite generating functions, but these equations were determined only experimentally and, in most of the transcendental cases, they still lack formal proofs (in the 4 algebraic cases, differential equations are easily proved, starting from algebraic equations). Therefore, the following problems were left unsolved by Bousquet-Mélou and Mishna:

(i) prove differential equations satisfied by Q(0, 0; t) and Q(t) = Q(1, 1; t) [11, §7.5];

(ii) find closed form expressions for them [11, §7.3];

(iii) classify models with algebraic generating function Q(t) [11, §7.3]. Contributions. The original goal of the present paper was to answer question (i). In this regard, we rigorously prove the differential equations for Q(0, 0; t) and Q(1, 1; t) guessed by Bostan and Kauers [5,[START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF] for the 19 models with D-finite transcendental complete generating function. We actually do more, that is we also find and prove differential equations for Q(x, 0; t) and for Q(0, y; t), that specialize to equations for Q(1, 0; t) and Q(0, 1; t).

By solving these differential equations, we answer (ii) in the following sense: for all the 19 models mentioned above we uniformly find closed form expressions for Q(x, y; t) in terms of Gauss' hypergeometric series 2 F 1 with parameters a, b, c ∈ Q, with -c / ∈ N, defined by

(1) 2 F 1 a b c t = ∞ n=0 (a) n (b) n (c) n t n n! ,
where (x) n denotes the Pochhammer symbol (x) n = x(x + 1) • • • (x + n -1) for n ∈ N.

More precisely, we obtain the following structure result, that has been conjectured in [6, §3.2]. Note that a similar expression also appears in a related combinatorial context [START_REF] Bostan | Explicit formula for the generating series of diagonal 3D rook paths[END_REF] for rook paths on a threedimensional chessboard.

Theorem 1. Let S be one of the 19 models of small step walks in the quarter plane (see Table 1). The complete generating function Q(x, y; t) is expressible as a finite sum of iterated integrals of products of algebraic functions in x, y, t and of expressions of the form 2 F 1 (a, b; c; w(t)), where c ∈ N and w(t) ∈ Q(t).

The parameters a, b, c of the occurring 2 F 1 's as well as the rational functions w(t) are explicitly given in Table 2. The full expressions of the generating functions Q(0, 0; t), Q(0, 1; t), Q(1, 0; t), Q(1, 1; t), Q(x, 0; t), Q(0, y; t) and Q(x, y; t) are too large to be displayed in this paper, and are available on-line at http://specfun.inria.fr/chyzak/ssw/closed_forms.html. It turns out by inspection that the involved hypergeometric functions have a very particular form: they are intimately related to elliptic integrals, namely to the complete elliptic integrals of first and second kinds,

K(k) = π/2 0 (1 -k 2 sin 2 θ) -1/2 dθ = π 2 2 F 1 1 2 1 2 1 k 2 , E(k) = π/2 0 (1 -k 2 sin 2 θ) 1/2 dθ = π 2 2 F 1 -1 2 1 2 1 k 2 .
For instance, for the step set {(1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0)} of the so-called king walks (case 4 in Table 1), we prove that (2)

Q(t) = 1 t t 0 1 (1 + 4x) 3 • 2 F 1 3 2 3 2 2 16x(1 + x) (1 + 4x) 2 dx.
See Section 2 for a detailed presentation of this example. Alternatively, an expression of Q(t) in terms of elliptic integrals is

Q(t) = 1 t t 0 1 π(1 + 4x) 2 x(1 + x) • K 4 x(1 + x) 1 + 4x dx.
The relationship to elliptic integrals appears to hold true in a far more general setting. Indeed, taking Theorem 1 as starting point, one of us (van Hoeij) has checked that for many (more than 100) integer sequences (a n ) n≥0 in the OEIS whose generating function A(t) = n≥0 a n t n is both D-finite and convergent in a small neighborhood of t = 0, all second-order irreducible factors of the minimalorder linear differential operator annihilating A(t) are solvable either in terms of algebraic functions, or in terms of complete elliptic integrals. This surprisingly general feature, reminiscent of Dwork's conjecture mentioned in [6, §3.2], begs for a combinatorial explanation. See also [START_REF] Van Hoeij | Classifying (near)-Belyi maps with five exceptional points[END_REF]Section 8] for a similar discussion.

In Theorem 1 and in representations of generating functions like (2), all "functions" bear a combinatorial meaning: they have to be understood as denoting formal series at 0, potentially with a (finite) polar part. Correspondingly, integration has to be viewed as a linear operator from the set of formal Laurent series without term in t -1 to the whole field C((t)) of formal Laurent series. By the natural growth of the number of walks counted by length, all series considered can also be viewed as analytic series that converge at least on an annulus around 0. This alternative interpretation will be used in Section 4.3 only, for asymptotic considerations.

Finally, concerning question (iii), we start from the explicit differential equations and we exhaustively classify the algebraic cases among all the specializations of the generating function Q(x, y; t) at points (x, y) ∈ {(0, 0), (1, 0), (0, 1), (1, 1)}. As a corollary, we reprove the transcendence of Q(x, y; t). More precisely, we prove: Theorem 2. Let S be one of the 19 models of small step walks in the quarter plane (see Table 1), with complete generating function Q(x, y; t). For any (α, β) ∈ {(0, 0), (1, 0), (0, 1), (1, 1)}, the power series Q(α, β; t) is transcendental, except in the following four cases:

• Case 18 at (α, β) = (1, 0) and at (α, β) = (0, 1), • Cases 17 and 18 at (α, β) = (1, 1).

As a consequence, the power series Q(x, y; t), Q(x, 0; t), and Q(0, y; t) are transcendental for all the 19 models. Additionally, the generating functions of the four algebraic cases are equal to:

• Q(1, 1) = 1 2t 2 1 -t -(1 + t)(1 -3t) in case 17, • Q(1, 1) = 1 8t 2 1 -2t -(1 + 2t)(1 -6t) in case 18, • Q(1, 0) = Q(0, 1) = 1 32t 3 (1 -6t) 3/2 (1 + 2t) 1/2 -4t 2 + 8t -1 in case 18.
As an aside, starting from the explicit expressions in terms of hypergeometric functions, we use singularity analysis and transfer theorems that are classical in Analytic Combinatorics to get some asymptotic formulas for the nth coefficient of Q(0, 0; t), Q(1, 0; t), Q(0, 1; t) and Q(1, 1; t). Methodology. Our proofs of Theorems 1 and 2 are computer-driven and crucially rely on the use of several modern computer algebra algorithms. The starting point is a result by Bousquet-Mélou and Mishna [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF], stating that for the 19 models in Table 1 the complete generating function Q(x, y; t) can be expressed as the positive part of a certain rational function in three variables. The notion of positive part is one of the key mathematical ingredients in what follows. In one variable, extraction of the positive part is an operator, denoted [x > ], which acts on formal Laurent series by cutting away all the terms with zero or negative exponents, leaving a formal power series with no constant term as a result. For example,

[x > ] 1 x 2 (1 -x) 2 = [x > ] ∞ n=-2 (n + 3)x n = ∞ n=1 (n + 3)x n = x(4 -3x) (1 -x) 2 .
Note that interpreting the rational function as a formal Laurent series in x -1 instead of x would lead to a different extraction map. Indeed, for this other definition of positive-part extraction, we would have

[x > ] 1 x 2 (1 -x) 2 = [x > ] ∞ n=0 n 1 x n+3 = [x > ] -3 n=-∞ -(n + 3)x n = 0.
Things get more complicated in the multivariate setting. Using the kernel method, Bousquet-Mélou and Mishna showed in [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]Prop. 8] that the generating function Q(x, y; t), can be written in the form

(3) Q(x, y; t) = 1 xy [x > ][y > ] N (x, y) 1 -tS(x, y)
where N (x, y) and S(x, y) are certain (structured) Laurent polynomials in y with coefficients that are rational functions in x. These quantities depend on S and are listed in Table 1. Since there is no unique natural way of mapping rational functions in several variables to multivariate formal Laurent series, it is a priori not clear how the positive-part extraction is defined in this context. Here is the intended reading of (3): first interpret N (x, y)/(1 -tS(x, y)) as an element of Q(x)[y, As pointed out by Bousquet-Mélou and Mishna, Equation (3) already implies the D-finiteness of Q(x, y; t), since positive parts can be encoded as diagonals, and diagonals of D-finite power series are again D-finite [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]. This argument also implies an algorithm for computing linear differential equations satisfied by Q(x, y; t), since the D-finiteness proof in [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF] is effective and basically amounts to linear algebra. Therefore, from (3) one could, in principle, determine differential equations for Q(x, y; t). To be more specific, the positive part of a formal power series

R ∈ Q[[x, y, t]] can be encoded as (4) [x > ][y > ]R(x, y; t) = x 1 -x y 1 -y x,y R(x, y; t) = Diag x,x Diag y,y x 1 -x y 1 -y R(x , y ; t),
where the Hadamard product denoted x,y is the term-wise product of two series, while the diagonal operator Diag x,x selects those terms with equal exponents of x and x . However, the direct use of (4) in our context leads to infeasible computations; worse, the intermediate algebraic objects involved in the calculations would probably have too large sizes to be merely written and stored. This is really unfortunate, since our need is mere evaluations of the diagonals in (4) at specific values for x and y.

To bypass this computational obstacle, we use two ingredients. The first one is our main theoretical innovation: we reformulate the generating function Q(x, y; t) in terms of formal residues. This idea is classical (and in fact already used in Lipshitz' proof [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]): we encode diagonals as residues, with the added advantage that early specialization of the variables x and/or y becomes possible. Additionally, our derivation bases on a positive-part extraction that differs from Bousquet-Mélou and Mishna's iterated operator [x > ][y > ]: we use a theory [START_REF] Aparicio | Formal Laurent series in several variables[END_REF] of series with exponents that may be arbitrarily large in negative directions, but are restricted to fixed cones, together with a different, direct positive-part operator, [x > y > ], to be defined in Section 3. The outcome of this reformulation is the ability to compute linear differential equations with polynomial coefficients for the specializations Q(x, 0; t) and Q(0, y; t).

To perform these computations, we use a second ingredient, creative telescoping, an efficient algorithmic technique for the symbolic integration of multivariate functions. Indeed, a direct application of Lipshitz' linear-algebra algorithm (even with specialized variables) still leads to too large systems, while creative telescoping succeeds in our cases of application; see [4, §2.3] for a related discussion. By specialization and recombination, the equations thus obtained give rise to rigorously proved differential equations for Q(0, 0; t), Q(1, 0; t), Q(0, 1; t) and Q(1, 1; t), thus answering question (i). The analysis of these differential equations combined with Kovacic's algorithm [START_REF] Kovacic | An algorithm for solving second order linear homogeneous differential equations[END_REF] allows to answer question (iii) and to prove Theorem 2. Moreover, these differential equations are solved in explicit terms using symbolic algorithms for ODE factorization and ODE solving, leading to the proof of Theorem 1 and to the answer of question (ii).

The remarkable property that the differential equations in the 19 × 4 cases could all be solved in terms of hypergeometric functions relies on the fact that these operators share a very peculiar factorization pattern: they factor into factors that all have order 1 with the exception of the left-most one that can have order 1 or 2. The origin of this common mathematical feature deserves to be better understood. Previous work. We conclude this introduction by mentioning previous contributions on the main topics of the article: D-finiteness, transcendence and explicit expressions for Q(x, y; t) and its specializations. D-finiteness. For the simplest models, the square walk (case 1) and the diagonal walk (case 2), D-finiteness is classical (e.g., [START_REF] Arquès | Dénombrements de chemins dans R 2 soumis à contraintes[END_REF]). Some more involved models have been considered sporadically: for case 19, Gouyou-Beauchamps [START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF] proved bijectively that Q(1, 0; t) is D-finite; for cases 5 and 15 Mishna [39,§2.4.1,§2.4.2] showed that Q(x, y; t) is D-finite using the kernel method; and for case 17 she proved [39, §2.3.3] that Q(x, y; t) is D-finite by using a bijection with Young tableaux of height at most 3.

Several methods have been proposed to capture D-finiteness in a uniform way. For models with a vertical symmetry (cases 1-16), Bousquet-Mélou and Petkovšek [12, §2] proved that Q(t) = Q(1, 1; t) is D-finite by a combinatorial argument, and Bousquet-Mélou [9, §3] proved D-finiteness of Q(x, y; t) by an algebraic argument (a variation of the kernel method). For cases 17-19, Gessel and Zeilberger [START_REF] Gessel | Random walk in a Weyl chamber[END_REF] proved D-finiteness of Q(x, y; t) by using an algebraic version of the reflection principle; their argument works more generally when the step set is left invariant by a Weyl group and the walks are confined to a corresponding Weyl chamber. Bousquet-Mélou and Mishna [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF] reproved D-finiteness of Q(x, y; t) in all 19 cases by using the kernel equation and the group of the walk borrowed from [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]; their method generalizes the previous ones from [START_REF] Gessel | Random walk in a Weyl chamber[END_REF] and [START_REF] Bousquet-Mélou | Counting walks in the quarter plane[END_REF]. Raschel [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] uses boundary value problems to get integral representations for Q(x, y; t) that imply its D-finiteness in all 19 cases. By using methods from the book [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], Fayolle and Raschel reproved in [17, Theorem 1.1] that (x, y) → Q(x, y; t 0 ) is D-finite for each t 0 ∈ (0, #S -1 ] and in all 19 cases.

Transcendence. Algebraicity/transcendence proofs were first considered in some isolated cases: in case 15, Q(x, y; t) was proved transcendental by Mishna [39,Th. 2.5] [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]. They actually proved more, namely that Q(x, y; t 0 ) is transcendental for each t 0 ∈ (0, #S -1 ], using the approach in [START_REF] Fayolle | Random walks in the quarter-plane[END_REF]Chap. 4]. However, this result does not provide any transcendence information about specializations at x, y ∈ {0, 1}.

Explicit equations and formulas. For the simplest models (cases 1-2), simple formulas exist, see e.g. [START_REF] Bousquet-Mélou | Counting walks in the quarter plane[END_REF]; some of them admit bijective proofs, see e.g. [START_REF] Guy | Lattice paths, reflections, & dimension-changing bijections[END_REF]. For models 5 and 15, Mishna [39, Th. 2.5 and 2.6] gives explicit expressions of Q(x, y; t) in terms of some auxiliary series. For model 17, basing on earlier work by Regev [START_REF] Regev | Asymptotic values for degrees associated with strips of Young diagrams[END_REF] and using a bijection with Young tableaux of height at most 3, Mishna [39, §2.3.3] shows that q i,j;n has a nice hypergeometric expression and that Q(1, 1; t) is the (algebraic) generating function of Motzkin numbers. In cases 17-18, Bousquet-Mélou and Mishna [11, §5.2] gave explicit expressions for Q(1, 1; t) (and more generally for Q(x, 1/x; t)). For model 19, it was proved by Gouyou-Beauchamps [START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF] that the number of n-step walks ending on the x-axis is a product of Catalan numbers; hypergeometric expressions for the total number of walks are derived in [11, §5.3], and for those ending at an arbitrary point (i, j). Bostan and Kauers [5,[START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF] empirically determined differential equations for Q(1, 1; t) and Q(0, 0; t) for all 19 models. For the "highly symmetric" models (cases 1-4), Melczer and Mishna [START_REF] Melczer | Enumerating lattice paths with symmetries through multivariate diagonals[END_REF] proved differential equations for Q(1, 1; t) conjectured by Bostan and Kauers [START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF]. Raschel [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] provides explicit integral representations of the complete generating function using a uniform analytic approach.

Before we enter into the details, Section 2 goes through the whole process on one concrete example. From now on, we more simply write x and ȳ, respectively, for x -1 and y -1 .

A Worked Example: King Walks in the Quarter Plane

We illustrate our approach on an example. We choose the so-called king walks in the quarter plane (case 4 in Table 1), with step set S = {(1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0)}. The first terms of the generating function Q(1, 1; t) of king walks with prescribed length and arbitrary endpoint read (see http://oeis.org/A151331)

Q(1, 1; t) = 1 + 3t + 18t 2 + 105t 3 + 684t 4 + 4550t 5 + 31340t 6 + 219555t 7 + 1564080t 8 + • • • ,
and the methods of the present article allow to obtain the above-mentioned closed formula (2) for it.

Here are the main steps of our approach. First, the classical kernel equation [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]Lemma 4] relates Q(x, y; t) to Q(x, 0; t), Q(0, y; t), and Q(0, 0; t):

(5) Q(x, y; t) = 1 + t S(x, y)Q(x, y; t) -ȳ(x + 1 + x)Q(x, 0; t) -x(y + 1 + ȳ)Q(0, y; t) + xȳQ(0, 0; t) , where S(x, y) is the generating polynomial of the step set: S(x, y) = (i,j)∈S

x i y j = xy + y + xy + x + x + xȳ + ȳ + xȳ.

A simple but important observation is that the kernel K(x, y; t) = 1 -tS(x, y) remains unchanged under the change of variables (x, y) ← (x, ȳ), (x, y) ← (x, y) and (x, y) ← (x, ȳ). (Other step sets could require different changes of variables to provide the same property.)

Applying these rational transformations to the kernel equation ( 5) yields the four relations:

xyK(x, y; t)Q(x, y; t) = xy -tx(x + 1 + x)Q(x, 0; t) -ty(y + 1 + ȳ)Q(0, y; t) + tQ(0, 0; t), -xyK(x, y; t)Q(x, y; t) = -xy + tx(x + 1 + x)Q(x, 0; t) + ty(y + 1 + ȳ)Q(0, y; t) -tQ(0, 0; t), xȳK(x, y; t)Q(x, ȳ; t) = xȳ -tx(x + 1 + x)Q(x, 0; t) -tȳ(y + 1 + ȳ)Q(0, ȳ; t) + tQ(0, 0; t),

-xȳK(x, y; t)Q(x, ȳ; t) = -xȳ + tx(x + 1 + x)Q(x, 0; t) + tȳ(y + 1 + ȳ)Q(0, ȳ; t) -tQ(0, 0; t).
Upon adding up these equations, all terms in the right-hand side involving Q disappear, resulting in

xyQ(x, y; t) -xyQ(x, y; t) + xȳQ(x, ȳ; t) -xȳQ(x, ȳ; t) = K(x, y; t) -1 (xy -xy + xȳ -xȳ) .
Now, the main observation is that on the left-hand side, all terms except the first one involve negative powers either of x or of y. Therefore, extracting positive parts expresses the generating series xyQ(x, y; t) as the positive part (w.r.t. x and y) of a trivariate rational function:

(6) xyQ(x, y; t) = [x > ][y > ] xy -xy + xȳ -xȳ 1 -t(xy + y + yx + x + xȳ + ȳ + xȳ + x)
.

Up to this point, our reasoning is borrowed from Bousquet-Mélou's and Mishna's article [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]. Combined with Lipshitz's result [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF] that positive parts of D-finite functions are D-finite, it already implies that Q(x, y; t) is D-finite; in particular, Q(1, 1; t) is also D-finite. Our aim is to refine this qualitative result, and explicitly obtain a linear differential equation satisfied by Q(1, 1; t). Such a differential equation was algorithmically guessed in [START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF] starting from the first terms in the power series expansion of Q(1, 1; t); however the methods in [START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF] do not provide a rigorous proof of the correctness of that equation.

Starting from ( 6) and following more closely Lipshitz' encoding [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF], a first observation is that Q(x, y; t) is equal to the iterated diagonal [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF] Diag x1,x2 Diag y1,y2

x 2 y 2 (x 1 y 1 -x1 y 1 + x1 ȳ1 -x 1 ȳ1 ) (1 -x 2 )(1 -y 2 )(1 -t(x 1 y 1 + y 1 + y 1 x1 + x1 + x1 ȳ1 + ȳ1 + x 1 ȳ1 + x 1 ))
.

There exist algorithms that take as input a rational function and compute a system of partial differential equations satisfied by its diagonal [START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF][START_REF] Koutschan | A fast approach to creative telescoping[END_REF][START_REF] Lairez | Computing periods of rational integrals[END_REF][START_REF] Zeilberger | The method of creative telescoping[END_REF]. However, in our case, these computations are too difficult, and exceed by far the limits of the best existing algorithms. The reason is that differential equations w.r.t. t and with polynomial coefficients in x, y, t are really huge, so the main limitation of algorithms computing [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF] already comes from the size of the output. Another weakness of the diagonal encoding [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF] is that it does not provide direct access to the univariate series Q(1, 1; t), since taking diagonals and specializing variables are operations that do not commute.

To circumvent these difficulties and to make the computation feasible, our key idea is to encode the positive part in (6) as a formal residue:

(8) Q(α, β; t) = Res x,y xy -xy + xȳ -xȳ (1 -αx)(1 -βy)(1 -t(xy + y + yx + x + xȳ + ȳ + xȳ + x))
.

The formal proof of this encoding is delicate and is the topic of Section 3. The advantage of ( 8) over ( 7) is twofold. On the one hand, the residue computation can be carried out by using a single call to the creative-telescoping algorithm for rational functions, while the diagonal computation [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF] has two steps, the first for a rational function in five variables, the second for an algebraic function in four variables.

On the other hand, and more importantly, taking residues commutes with specialization, contrarily to positive parts and diagonals. Therefore, the generating series for walks Q(1, 1; t) is equal to

Q(1, 1; t) = Res x,y xy -xy + xȳ -xȳ (1 -x)(1 -y)(1 -t(xy + y + yx + x + xȳ + ȳ + xȳ + x))
.

A nice property of residues is that pure derivatives in x and y have zero residue. In order to compute a linear differential equation satisfied by Q(1, 1; t) it thus suffices to find U, V ∈ Q(x, y; t) and a differential operator

L in Q(t) ∂ t such that (9) L xy -xy + xȳ -xȳ (1 -x)(1 -y)(1 -t(xy + y + yx + x + xȳ + ȳ + xȳ + x)) = ∂ x (U ) + ∂ y (V ),
where ∂ t , ∂ x , and ∂ y stand for the derivation operators d/dt, d/dx, and d/dy, respectively. Indeed, since L depends neither on x nor on y, it commutes with the extraction of the residue with respect to x and y.

The fact that the residue of

∂ x (U ) + ∂ y (V ) is zero then proves that L(Q(1, 1; t)) = 0.
However, this last implication is more subtle than it looks: Equation ( 9) really is a relation between rational functions; the conclusion about Q(t) is a conclusion about series. Owing to the ambiguity inherent to series expansions of rational functions, it is not clear a priori that the rational function in the left-hand side of ( 9) and U and V in its right-hand side can be expanded consistently and in accordance with the combinatorial interpretation for Q(t). Describing the right expansion is the topic of Section 3: Theorem 5 provides the wanted implication. Now, the existence of a non trivial (L, U, V ) satisfying ( 9) is guaranteed by the theory of holonomic D-modules, which was first used in this context by Zeilberger [START_REF] Zeilberger | A holonomic systems approach to special functions identities[END_REF] (see also [START_REF] Cartier | Démonstration "automatique" d'identités et fonctions hypergéométriques (d'après D. Zeilberger)[END_REF]). The explicit form of a solution (L, U, V ) can be determined using creative telescoping [START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF][START_REF] Koutschan | A fast approach to creative telescoping[END_REF][START_REF] Zeilberger | The method of creative telescoping[END_REF]; a detailed description of the algorithm is presented in [4, §2.4.2].

In our case, we find

(10) L = t 2 (1 + 4t)(8t -1)(2t -1)(1 + t)∂ 3 t + t(200t 3 + 576t 4 -33t -252t 2 + 5)∂ 2 t + 4(22t 3 -117t 2 -12t + 288t 4 + 1)∂ t + 384t 3 -12 -144t -72t 2 .
Note that this is precisely the differential operator guessed in [START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF]. Moreover, factorization algorithms for linear differential operators [START_REF] Mark Van Hoeij | Factorization of differential operators with rational functions coefficients[END_REF] can be used to prove that

L = L 2 L 1 , where L 1 = ∂ t + 1/t and (11) L 2 = t 2 (1 + 4t)(1 -8t)(1 -2t)(1 + t)∂ 2 t + 2t(256t 4 + 80t 3 -111t 2 -14t + 2)∂ t + 768t 4 + 8t 3 -306t 2 -30t + 2.
It follows that the Laurent power series

f (t) = dQ dt (1, 1; t) + Q(1, 1; t) t = t -1 + 6 + 54t + 420t 2 + 3420t 3 + 27300t 4 + 219380t 5 + O(t 6 )
is a solution of L 2 . Starting from the second order operator L 2 , algorithmic methods explained in [4, §2.6] (see also [START_REF] Fang | 2-descent for second order linear differential equations[END_REF]) allow to express f (t) in terms of a 2 F 1 hypergeometric function:

f (t) = 1 t(1 + 4t) 3 • 2 F 1 3 2 3 2 2 16t(1 + t) (1 + 4t) 2 .
Finally, solving the equation d/dt Q(1, 1; t) + Q(1, 1; t)/t = f (t) yields formula [START_REF] Aparicio | Formal Laurent series in several variables[END_REF]. Similarly, by deriving variants of (9) parametrized by indeterminate α and β we obtain the representations

Q(α, 0; t) = Res x,y xy -xy + xȳ -xȳ (1 -αx)(1 -t(xy + y + yx + x + xȳ + ȳ + xȳ + x)) and Q(0, β; t) = Res x,y xy -xy + xȳ -xȳ (1 -βy)(1 -t(xy + y + yx + x + xȳ + ȳ + xȳ + x))
.

Creative-telescoping techniques still allow the effective computation of differential operators in

Q(α; t) ∂ t for Q(α, 0; t), resp. in Q(β; t) ∂ t for Q(0, β; t).
Owing to the additional symbolic indeterminate, the computations are much harder than for Q(1, 1; t), but still feasible. Each of the resulting differential operators factors again, this time as a product of an order-two operator and of three order-one operators. Moreover, the second-order operators are again solvable in terms of 2 F 1 functions. Finally, a closed formula for Q(α, β; t) is obtained from the closed formulas for Q(α, 0; t) and Q(0, β; t) via the kernel equation ( 5). This detour is computationally crucial, since performing creative telescoping directly on the five-variable rational function from ( 8) is not feasible even using today's best algorithms.

Computing Positive Parts as Formal Residues

We will now put the assertions made in the previous section for one particular case on solid algebraic grounds by clarifying to which series domains we map our rational functions, by introducing formal notions of residue, Hadamard product, and positive part for the objects in these domains, and by showing that the differential equations we obtain from creative telescoping indeed annihilate the positive parts.

To this end, we study vector spaces of "series" that are just bilateral infinite arrays in Section 3.1, before elaborating in Section 3.2 on a theory of rings and fields of series with exponents in cones [START_REF] Aparicio | Formal Laurent series in several variables[END_REF]. We are then able to represent positive parts as residues of suitable products in those rings in Section 3.3.

In Section 3.4, a notion of cones in opposition is introduced to refine this representation and allow the early specialization we need for efficiency in computations. The connection to our application is done in Section 3.5, before we justify the use of creative telescoping in Section 3.6.

As the present section is of a more general nature than the application to small-step walks, we develop the theory here over a general field K of characteristic 0.

3.1. Linear operations on infinite arrays. The set K Z n consisting of all the series [START_REF] Bousquet | Walks confined in a quadrant are not always D-finite[END_REF] i1,...,in∈Z

a i1,...,in x i1 1 • • • x in n is a K-vector space.
Here, we use the word "series" and the notation just for convenience, disregarding any question of convergence. The set K Z n is not a ring, but we can endow it with well-defined operations of residue (from K Z n to K) and positive part (from K Z n to K N n ): for a given series f , the residue Res x1,...,xn f and positive part

[x > 1 • • • x > n ]
f are defined in the natural way as a -1,...,-1 and i1,...,in>0

a i1,...,in x i1 1 • • • x in n ,
respectively. More generally, we may consider residue and positive-part extractions with respect to some of the variables only, and this will be obvious from the notation. This way, positive-part extractions compose nicely, e.g., [

x > 1 ][x > 2 ] = [x > 2 ][x > 1 ] = [x > 1 x > 2 ]
. The vector space K Z n also possesses an internal law of Hadamard product, defined for two series f and g with respective coefficients a i1,...,in and b i1,...,in by

f g = i1,...,in∈Z a i1,...,in b i1,...,in x i1 1 • • • x in n .
Finally, for k ≤ n, we will need more operations for series in different variable sets:

• for f ∈ K Z k and g ∈ K Z n , we define (13) f k≤n g = i1,...,in∈Z a i1,...,i k b i1,...,in x i1 1 • • • x in n ; • for f ∈ K Z n and g ∈ K Z k , we define (14) f n≥k g = i1,...,in∈Z a i1,...,in b i1,...,i k x i1 1 • • • x in n .
Beware that, despite the natural embedding of 13) is generally not equal to (f x 0 k+1 • • • x 0 n ) g and similarly f n≥k g in ( 14) is generally not equal to f (gx 0 k+1 • • • x 0 n ). The vector space K Z n also has a (linear-)differential structure: it can be endowed with a derivation operator ∂ 1 that maps a series (12) to i1,...,in∈Z

K Z k into K Z n mapping f ∈ K Z k to f x 0 k+1 • • • x 0 n ∈ K Z n , f k≤n g in (
i 1 a i1,...,in x i1-1 1 x i2 2 • • • x in n ,
and with operators ∂ 2 , . . . , ∂ n defined similarly. The following result is then obvious.

Lemma 1. For any series f ∈ K Z n and any j satisfying

1 ≤ j ≤ n, Res x1,...,xn ∂ j f = 0.
Additionally, as Laurent polynomials are finite sums, K Z n admits well-defined operations of multiplication by a Laurent polynomial. Together with closure under derivation, this makes it meaningful to consider differential equations in series of K Z n .

Series expansions with respect to a cone.

In what follows, we introduce a family of rings of series with support restricted to cones of Z n . This extends to rings of series whose support enjoys a certain compatibility condition with a fixed monomial ordering. This discussion is mostly borrowed from [START_REF] Aparicio | Formal Laurent series in several variables[END_REF]. See the introduction in that article for the comparison to the theory of Hahn series (later developed by Mal'cev, Neumann, and recently Xin) and to the theory of MacDonald series (recently developed by Aroca, Cano, and Jung).

In order to highlight the names and number of indeterminates in the notation for various rings and fields of polynomials, series, etc, in what follows, we will compactly write U m to denote m indeterminates u 1 , . . . , u m in notations like

K[U m ], K(U m ), K[[U m ]
], etc. To refer to only the last m -p indeterminates u p+1 , . . . , u m of U m , we will write U m\p . We will use similar notation for inverses and combinations of names of indeterminates, e.g.,

K[X n , Y n\k , Y -1 k ] denotes K[x 1 , . . . , x n , y k+1 , . . . , y n , y -1 1 , . . . , y -1 k ]. Definition 1. A topologically closed set C ⊆ R n is called a cone if for all u, v ∈ C and λ, µ ≥ 0, λu + µv ∈ C. A cone C is called line-free if u, -u ∈ C implies u = 0.
If C is a line-free cone, then the set consisting of all the series of the form [START_REF] Bousquet | Walks confined in a quadrant are not always D-finite[END_REF] with a i1,...,in = 0 whenever (i 1 , . . . , i n ) ∈ C forms a ring together with the natural addition and multiplication. We denote it by K

C [[x 1 , . . . , x n ]] or K C [[X n ]]. It is a K-algebra. For the trivial cone C = {0}, this is simply K. The set K C X n := (i1,...,in)∈Z n x i1 1 • • • x in n K C [[X n ]], forms another ring, in fact just K C [[X n ]][X n , X -1 n ]
. Its elements are series whose supports are contained in a finite union of translated copies (i 1 , . . . , i n ) + C of C. For the trivial cone C = {0}, this is simply the ring of Laurent polynomials, K[X n , X -1 n ]. The ring K C X n inherits the operations of residue and positive part, the internal law of Hadamard product, and the derivation operations. Observe as well that the Hadamard product f 1 f 2 of series f 1 ∈ K C1 X n and f 2 ∈ K C2 X n for different C 1 and C 2 belongs to both rings, because the support of f g is the intersection of the supports of f and g.

Observe that rational functions from K(x 1 , . . . , x n ), henceforth denoted K(X n ), can often be expanded as elements of different rings K C1 X n and K C2 X n , potentially with trivial intersection C 1 ∩ C 2 = {0}. This should not be understood as implying that the rational function is part of the intersection of both rings. In fact, we should refrain from viewing rational functions as elements of series rings: they only have images in those rings. As a consequence, residue and positive-part extractions of a rational function only make sense with respect to a given cone expansion. On the other hand, given two line-free cones C ⊆ C , we can safely identify

K C [[X n ]] as a subring of K C [[X n ]]
, each given series having the same coefficient family with regard to both expansions. The situation is the same with K C X n that we identify as a subring of K C X n . Similar identifications occur when extending the variable set: for instance, we will freely identify

K C [[X n ]] and K C×{0} m [[X n+m ]].
To avoid blind identification of a rational function with a series, as the latter must depend on the cone used, we introduce the following notation: for a rational function P/Q ∈ K(X n ) which admits an expansion with respect to a line-free cone C, we write [P/Q] C for this expansion in K C X n . As a consequence of [2, Thm 12], such an expansion exists if and only if Q can be factored in the form

x i1 1 • • • x in n Q for Q ∈ K C [[X n ]
] with non-zero constant term. There will be situations where we need to know the existence of a cone C with respect to which a certain rational function can be expanded without having to know the exact cone C. This will be the case in Section 3.6 below, when we link creative telescoping to series expansions: we will want to know that certificates of creative telescoping can be expanded over some cone C without having to observe them to be able to make the cone C explicit. To this end, we borrow from [START_REF] Aparicio | Formal Laurent series in several variables[END_REF] the definition of more rings and fields, defined with respect to a monomial order.

We start with a fixed monomial order on the monomials in x 1 , . . . , x n (with exponents in Z), that is, with a total order that is monotonic with respect to product: for all a, b, and c, a b implies ac bc. Definition 2. A cone C is compatible with the monomial order if the apex of C coincides with its minimal element with respect to .

Given , the union over all cones C compatible with of the rings

K C [[X n ]] is a ring, denoted K [[X n ]] in what follows. The set K ((X n )) := (i1,...,in)∈Z n x i1 1 • • • x in n K [[X n ]
] now forms another ring. This ring is even a field [2, Thm 15]. Now, for a fixed cone C compatible with the monomial order , the ring

K C [[X n ]] is a subring of both K C X n and K [[X n ]]
, and both of these rings are subrings of the field K ((X n )). All those inclusions are canonical, in the sense that they preserve the coefficients. In particular, a rational function F of the field K(X n ) maps to a well-defined series of K ((X n )), which we will denote [F ] . When C is compatible with , we will do the identification

[F ] C = [F ] . As a consequence, the field [K(X n )] = {[F ] : F ∈ K(X n )} is a subfield of K ((X n )).

Positive parts as residues. For a given series

f ∈ K C X n , the positive part [x > 1 • • • x > n ]
f can be obtained by taking the Hadamard product with the expansion as a geometric series in

K R n ≥0 [[X n ]] of x1•••xn (1-x1)•••(1-xn)
. We will argue that the usual residue formula for computing Hadamard products holds in this setting.

Lemma 2. Let π 1 : R n → R k and π 2 : R n → R n-k be the projections to the first k and last n -k coordinates, respectively, so that we have u = (π 1 (u), π 2 (u)) for every u ∈ R n . Each of the following constructions is a line-free cone:

(1) the set C 1 C 2 := (u, v -u) : u ∈ C 1 , v ∈ C 2 ⊆ R 2n for line-free cones C 1 , C 2 ⊆ R n , ( 2
) the set C 1 k≤n C 2 := (u, π 2 (v), π 1 (v) -u) : u ∈ C 1 , v ∈ C 2 ⊆ R k+n for line-free cones C 1 ⊆ R k and C 2 ⊆ R n , (3) the set C 1 n≥k C 2 := (u, v -π 1 (u)) : u ∈ C 1 , v ∈ C 2 ⊆ R n+k for line-free cones C 1 ⊆ R n and C 2 ⊆ R k .
Proof. For the first construction, given

u 1 , u 2 ∈ C 1 , v 1 , v 2 ∈ C 2 ,
, v 1 -u 1 ) + µ(u 2 , v 2 -u 2 ) = (u, v -u) is in C 1 C 2 , and the latter is a cone. Next, given (u, v -u) in C 1 C 2 , if -(u, v -u) is in C 1 C 2 , too, then it can be written (u , v -u ). From (u, v -u) = -(u , v -u ) follows u = -u , which implies u = u = 0 because C 1 is line-free. This, in turn, implies that v = -v , which implies that v = v = 0 because C 2 is line-free. Therefore, C 1 C 2 is line-free.
The same argument applies with minor changes to the two other constructions.

As a consequence, each of

K C1 C2 X n , Y n , K C1 k≤n C2 X n , Y k , and K C1 n≥k C2
X n , Y k is a bona fide ring for any two line-free cones C 1 , C 2 of R n or R k (as required). Remark the intended choice to use X n in the case C 1 ⊆ Z k as well, and not X k , in accordance to Equation ( 16) below. As well, observe

C 1 C 2 = C 1 n≤n C 2 = C 1 n≥n C 2 ,
and similar identities on the level of rings.

Lemma 3. (i) Let C 1 , C 2 ⊆ R n be two line-free cones. Then, for any f ∈ K C1 X n and g ∈ K C2 X n , (15)
f g = Res y1,...,yn 1

y 1 • • • y n f x 1 y 1 , . . . , x n y n g(y 1 , . . . , y n ),
where the argument of the residue is understood as a product in

K C1 C2 X n , Y n . (ii) For k ≤ n, let C 1 ⊆ R k and C 2 ⊆ R n be two line-free cones. Then, for any f ∈ K C1 X k and g ∈ K C2 X n , (16)
f k≤n g = Res y1,...,y k 1 y 1 • • • y k f x 1 y 1 , . . . , x k y k g(y 1 , . . . , y k , x k+1 , . . . , x n ),
where the argument of the residue is understood as a product in

K C1 k≤n C2 X n , Y k . (iii) For k ≤ n, let C 1 ⊆ R n and C 2 ⊆ R k be two line-free cones. Then, for any f ∈ K C1 X n and g ∈ K C2 X k , (17)
f n≥k g = Res y1,...,y k 1 y 1 • • • y k f x 1 y 1 , . . . , x k y k , x k+1 , . . . , x n g(y 1 , . . . , y k ),
where the argument of the residue is understood as a product in

K C1 n≥k C2 X n , Y k .
Before the proof, observe that ( 16) and ( 17) cannot just be obtained as specializations of [START_REF] Denisov | Random walks in cones[END_REF].

Proof. We start by proving [START_REF] Denisov | Random walks in cones[END_REF]. Set

C := C 1 C 2 ⊆ R 2n
, which is a line-free cone by Lemma 2. Now, observe that f (x 1 /y 1 , . . . , x n /y n ) and g(y 1 , . . . , y n ) are in

K C X n , Y n , respectively because (u, -u) : u ∈ C 1 ⊆ C and because (0, v) : v ∈ C 2 ⊆ C.
So, the argument of the residue in ( 15) is a well-defined product. Call it h. To see that Res y1,...,yn h = f g, calculate: f u1,...,un g v1,...,vn

(18) h = 1 y 1 • • • y n u1,...,un f u1,...,un x u1 1 • • • x un n y u1 1 • • • y un n v1,...,vn g
x u1 1 • • • x un n y i1-1 1 • • • y in-1 n ,
where the sums are meant to extend over all integers with the understanding that f u1,...,un and g v1,...,vn are zero outside of the respective finite unions of translated cones. Applying Res y1,...,yn to this identity selects the term for which

i 1 = • • • = i n = 0, forcing (v 1 , . . . , v n ) = (u 1 , . . . , u n ).
) are in K C X n , Y k , respectively because (u, 0, -u) : u ∈ C 1 ⊆ C and because (0, π 2 (v), π 1 (v)) : v ∈ C 2 ⊆ C .
So, the argument of the residue in ( 16) is a well-defined product. The proof of ( 16) then follows calculations analogous to [START_REF] Fayolle | Random walks in the quarter-plane[END_REF].

To prove [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF], set

C := C 1 n≥k C 2 ⊆ R n+k
, which is a line-free cone by Lemma 2. Now, observe that f (x 1 /y 1 , . . . , x k /y k , x k+1 , . . . , x n ) and g(y 1 , . . . , y k ) are in

K C X n , Y k , respectively because (u, -π 1 (u)) : u ∈ C 1 ⊆ C and because (0, v) : v ∈ C 2 ⊆ C .
So, the argument of the residue in ( 17) is a well-defined product. The proof of [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF] then follows calculations analogous to [START_REF] Fayolle | Random walks in the quarter-plane[END_REF].

Recall the notation [P/Q] C to denote the expansion of a rational function with respect to a cone. Lemma 4. For every line-free cone C ⊆ R n , every φ ∈ K C X n , and every k ∈ {1, . . . , n}, we have:

[x > 1 • • • x > k ]φ = Res y1,...,y k 1 y 1 • • • y k x1 y1 • • • x k y k (1 -x1 y1 ) • • • (1 -x k y k ) R k ≥0 ×R k ≤0 φ(y 1 , . . . , y k , x k+1 , . . . , x n ) (19) = Res y1,...,y k 1 y 1 • • • y k φ x 1 y 1 , . . . , x k y k , x k+1 , . . . , x n y 1 • • • y k (1 -y 1 ) • • • (1 -y k ) R k ≥0 , ( 20
)
where the brackets around rational functions in [START_REF] Flajolet | Analytic models and ambiguity of context-free languages[END_REF] and (20) denote taking their expansions in, respectively,

K R k ≥0 ×R k ≤0 X k , Y k and K R k ≥0 Y k . Proof. Fix C to R k ≥0 and ψ ∈ K C X k to the geometric-series expansion of x1•••x k (1-x1)•••(1-x k )
. The desired positive part can then be represented in two ways as variants of Hadamard products:

[x > 1 • • • x > k ]φ = ψ k≤n φ = φ n≥k ψ.
We then use Lemma 3 twice:

• Firstly, by [START_REF] Fang | 2-descent for second order linear differential equations[END_REF] [START_REF] Flajolet | Analytic models and ambiguity of context-free languages[END_REF] and the announced expansion.

, [x > 1 • • • x > k ]φ = Res y1,...,y k 1 y1•••y k ψ x1 y1 , . . . , x k y k φ(y 1 , . . . , y k , x k+1 , . . . , x n ), where the product is in K C k≤n C X n , Y k . More specifically, ψ x1 y1 , . . . , x k y k is in K C k≤n {0} n X n , Y k , and with the proper identification in K R k ≥0 {0} k X k , Y k , hence
• Secondly, by [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process[END_REF]

, [x > 1 • • • x > k ]φ = Res y1,...,y k 1 y1•••y k φ x1 y1 , . . . , x k y k , x k+1 , . . . , x n ψ(y 1 , . . . , y k ), where the product is in K C n≥k C X n , Y n . More specifically, ψ(y 1 , . . . , y k ) is in K {0} n n≥k C X n , Y k ,
and with the proper identification in K C Y k , hence [START_REF] Flajolet | Singularity analysis of generating functions[END_REF] and the announced expansion.

3.4. Specializations of positive parts. Next, we would like to justify a formula to represent the series

[x > 1 • • • x > k ]f x1=α1,.
..,x k =α k as a Hadamard product, where α 1 , . . . , α k are fixed elements of K. For the evaluation of the positive part at some arbitrary field elements to make sense, we need to impose a restriction on the cones, which we will express using the following notion. Definition 3. Let π 2 : R n → R n-k be the projection to the last n -k coordinates. We say that two line-free cones C 1 , C 2 ⊆ R n are in opposition with respect to the first k variables if π 2 (C 1 ), π 2 (C 2 ) are line-free cones and

C 1 ∩ C 2 ∩ (R k × {0} n-k ) = {0} n .
Lemma 5. Let C 1 and C 2 in R n be in opposition with respect to the first k ≤ n variables, and let u, v ∈ R n . Then, the set

(C 1 + u) ∩ (C 2 + v) ∩ (R k × {0} n-k ) is bounded.
Proof. Given w, d ∈ R n , denote by R w,d the set {w + cd : c ≥ 0}. We recall without proof that: (i) for any R w,d contained in a cone C, both w and d are in C; (ii) any unbounded convex set K contains some R w,d with nonzero d; (iii) as a consequence, for any cone C,

any time R w,d ⊆ w + C, we have w -w , d ∈ C. Now, if the (convex) set (C 1 +u)∩(C 2 +v)∩(R k ×{0} n-k
) was unbounded, it would contain some R w,d for a nonzero d. We would have in particular that d would be in C 1 , C 2 , and R k × {0} n-k , implying d = 0. This would contradict that C 1 and C 2 are in opposition with respect to the first k variables.

Lemma 6 below gives a sufficient condition that allows a Hadamard product to specialize at x 1 = α 1 , . . . , x k = α k in a well defined way. Two potential obstructions to this are: (i) situations in which f g involves either of x 1 , . . . , x k with a negative exponent; (ii) situations in which the supports of f and g make it possible that the Hadamard product should involve some monomial in x k+1 , . . . , x n having as coefficient an infinite sum in x 1 , . . . , x k that does not converge as a series at x 1 = α 1 , . . . , x k = α k . In the lemma, the cones being in opposition ensures the finiteness of all sums under consideration in (ii), while case (i) is excluded by imposing α j = 0 when necessary. To state conditions for the latter point, for 1 ≤ j ≤ k ≤ n, for a series s in x 1 , . . . , x k and a series t in x 1 , . . . , x n , we introduce two predicates H n j (t) and H k≤n j (s, t) that express, respectively, that t cannot be evaluated at x j = 0 and that the (generally asymmetric) Hadamard product of s and t cannot be evaluated at x j = 0; they read:

H n j (t): : There exists a monomial in x 1 , . . . , x n with negative exponent of x j that occurs with non-zero coefficient in the series t.

H k≤n j (s, t): : There exists a monomial m in x 1 , . . . , x k with negative exponent of x j and a monomial m in x k+1 , . . . , x n , such that m occurs with non-zero coefficient in the series s and mm occurs with non-zero coefficient in the series t.

Note that H k≤n j (s, t) implies H k j (s) and H n j (t).

Lemma 6. (i) Let C 1 , C 2 ⊆ R n be in opposition with respect to the first k variables. Further, let f ∈ K C1 X n and g ∈ K C2 X n . Then, (f g)| x1=α1,...,x k =α k is well-defined for every α 1 , . . . , α k ∈ K, provided that for each

1 ≤ j ≤ k, α j = 0 if H n≤n j (f, g). (ii) Let C 1 ⊆ R k and C 2 ⊆ R n be such that C 1 × {0} n-k and C 2 are in opposition with respect to the first k variables. Further, let f ∈ K C1 X k and g ∈ K C2 X n . Then, (f k≤n g)| x1=α1,...,x k =α k is well-defined for every α 1 , . . . , α k ∈ K, provided that for each 1 ≤ j ≤ k, α j = 0 if H k≤n j (f, g). (iii) Let C 1 ⊆ R n and C 2 ⊆ R k be such that C 1 and C 2 × {0} n-k are in opposition with respect to the first k variables. Further, let f ∈ K C1 X n and g ∈ K C2 X k . Then, (f n≥k g)| x1=α1,...,x k =α k is well-defined for every α 1 , . . . , α k ∈ K, provided that for each 1 ≤ j ≤ k, α j = 0 if H k≤n j (g, f ).
Proof. (i) Suppose first that there are vectors e 1 , e 2 ∈ R n such that the support of f is contained in e 1 + C 1 and the support of g is contained in e 2 + C 2 . Fix i = (i k+1 , . . . , i n ) ∈ Z n-k and introduce i = (0, . . . , 0, i k+1 , . . . , i n ) ∈ Z n . From C 1 and C 2 being in opposition with respect to the first k variables, it follows by Lemma 5 that (e

1 -i + C 1 ) ∩ (e 2 -i + C 2 ) ∩ (R k × {0} n-k ) is bounded. In other words, (e 1 -i + C 1 ) ∩ (e 2 -i + C 2 ) ∩ π -1
2 (0) is bounded, and, after shifting by i , so is the set (e 1 + C 1 ) ∩ (e 2 + C 2 ) ∩ π -1 2 (i). Hence, there are at most finitely many vectors (i 1 , . . . , i k ) ∈ Z k such that the coefficient of x i1 1 . . . x in n in f g is nonzero. In the general case, there exist finite families e 2 + C 2 . Given a fixed i = (i k+1 , . . . , i n ) ∈ Z n-k again, the finiteness of the number of vectors (i 1 , . . . , i k ) ∈ Z k such that the coefficient of x i1 1 . . . x in n in f g is nonzero still holds, by distributivity and the previous argument. The constraints on the α i for a well-defined substitution follow in all cases. (ii) The proof is like the case (i), with minimal changes: considering e 1 ∈ R k instead of e 1 ∈ R n , replacing C 1 by C 1 × {0} n-k in the use of Lemma 5, and replacing f g by f k≤n g in the conclusion.

(iii) The proof is like the case (i), with minimal changes: considering e 2 ∈ R k instead of e 2 ∈ R n , replacing C 2 by C 2 × {0} n-k in the use of Lemma 5, and replacing f g by f n≥k g in the conclusion.

The following lemma generalizes Lemma 2 to cones in opposition.

Lemma 7. For any m ≥ k ≥ 0, let τ : R m → R m-k be the projection to the last m -k coordinates.

(i) Given two cones C 1 , C 2 ⊆ R n that are in opposition with respect to the first k variables, the set

τ (C 1 C 2 ) = (π 2 (u), v -u) : u ∈ C 1 , v ∈ C 2 ⊆ R (n-k)+n is a line-free cone. (ii) Given two cones C 1 ⊆ R k and C 2 ⊆ R n such that C 1 × {0} n-k and C 2 are in opposition with respect to the first k variables, the set τ (C 1 k≤n C 2 ) = (π 2 (v), π 1 (v) -u) : u ∈ C 1 , v ∈ C 2 ⊆ R k+n is a line-free cone. (iii) Given two cones C 1 ⊆ R n and C 2 ⊆ R k such that C 1 and C 2 × {0} n-k are in opposition with respect to the first k variables, the set τ (C 1 n≥k C 2 ) = (π 2 (u), v -π 1 (u)) : u ∈ C 1 , v ∈ C 2 ⊆ R n+k is a line-free cone.
Proof. (i) The proof that τ (C 1 C 2 ) is a cone is similar to the proof for the case of C 1 C 2 in Lemma 2. We show that it is line-free: assume there is w ∈ τ (C 1 C 2 ) such that -w ∈ τ (C 1 C 2 ); we proceed to prove that w = 0. By assumption, there exist u, u ∈ C 1 and v, v ∈ C 2 such that w = (π 2 (u), v -u) and -w = (π 2 (u ), v -u ), and therefore such that (π

2 (u), v -u) = -(π 2 (u ), v -u ). Then π 2 (u) = -π 2 (u ) implies π 2 (u) = π 2 (u ) = 0, because π 2 (C 1 ) is line-free. Next, v -u = -(v -u ) implies π 2 (v -u) = π 2 (-(v -u )), and therefore π 2 (v) = -π 2 (v ), because π 2 (u) = π 2 (u ) = 0. It follows that π 2 (v) = π 2 (v ) = 0 because π 2 (C 2 ) is line-free. Next, observe that v + v ∈ C 2 ∩ (R k × {0} n-k ), because π 2 (v) = π 2 (v ) = 0, and that u + u ∈ C 1 ∩ (R k × {0} n-k ), because π 2 (u) = π 2 (u ) = 0. From v -u = -(v -u ) follows v + v = u + u ∈ C 1 ∩ C 2 ∩ (R k × {0} n-k ).
As C 1 and C 2 are in opposition with respect to the first k variables, both v + v and u + u are zero. Since C 1 , resp. C 2 , is line-free, this finally implies that u = u = 0, resp. that v = v = 0, thus that w = 0.

(ii) The proof that τ (C 1 k≤n C 2 ) is a cone is similar to the proof for the case of

C 1 k≤n C 2 in Lemma 2.
We show that it is line-free: assume there is w ∈ τ (C 1 k≤n C 2 ) such that -w ∈ τ (C 1 k≤n C 2 ); we proceed to prove that w = 0. By assumption, there exist u, u ∈ C 1 and v, v ∈ C 2 such that w = (π 2 (v), π 1 (v)-u) and -w = (π 2 (v ), π 1 (v ) -u ), and therefore such that (π

2 (v), π 1 (v) -u) = -(π 2 (v ), π 1 (v ) -u ). Then π 2 (v) = -π 2 (v ) implies π 2 (v) = π 2 (v ) = 0, because π 2 (C 2 ) is line-free. Next, π 1 (v) -u = -(π 1 (v ) -u ) implies π 1 (v + v ) = u + u . Therefore, v + v = π 1 (v + v ) + π 2 (v + v ) = (u + u ) + 0. As C 1 × {0} n-k
and C 2 are in opposition with respect to the first k variables, both v + v and u + u are zero. Since C 1 , resp. C 2 , is line-free, this finally implies that u = u = 0, resp. that v = v = 0, thus that w = 0.

(iii) The proof that τ (C 1 n≥k C 2 ) is a cone is similar to the proof for the case of

C 1 n≥k C 2 in Lemma 2.
We show that it is line-free: assume there is

w ∈ τ (C 1 n≥k C 2 ) such that -w ∈ τ (C 1 n≥k C 2 )
; we proceed to prove that w = 0. By assumption, there exist u, u ∈ C 1 and v, v ∈ C 2 such that w = (π 2 (u), v -π 1 (u)) and -w = (π 2 (u ), v -π 1 (u )), and therefore such that (π

2 (u), v -π 1 (u)) = -(π 2 (u ), v -π 1 (u )). Then π 2 (u) = -π 2 (u ) implies π 2 (u) = π 2 (u ) = 0, because π 2 (C 1 ) is line-free. Next, v -π 1 (u) = -(v -π 1 (u )) implies π 1 (u+u ) = v+v . Therefore, u+u = π 1 (u+u )+π 2 (u+u ) = (v+v )+0. As C 1 and C 2 ×{0} n-k
are in opposition with respect to the first k variables, both u + u and v + v are zero. Since C 1 , resp. C 2 , is line-free, this finally implies that u = u = 0, resp. that v = v = 0, thus that w = 0.

Hence, for any two line-free cones C 1 , C 2 of R n or R k and with the relevant cones in opposition with respect to the first k variables (as required), each of

K τ (C1 C2) X n\k , Y n , K τ (C1 k≤n C2) X n\k , Y k , and K τ (C1 n≥k C2) X n\k , Y k
is a well-defined ring, and a subring of, respectively,

K C1 C2 X n , Y n , K C1 k≤n C2 X n , Y k , or K C1 n≥k C2 X n , Y k .
The following lemma can now be viewed as a generalization of Lemma 3 above. where the argument of the residue is understood as a product in

Lemma 8. (i) Let C 1 , C 2 ⊆ R n be two cones that are in opposition with respect to the first k variables. Let f ∈ K C1 X n , g ∈ K C2 X n , and α 1 , . . . , α k , β 1 , . . . , β k ∈ K satisfy: for each 1 ≤ j ≤ k, α j = 0 if H n j (f ) and β j = 0 if H n j (g). Then, (21)
K τ (C1 C2) X n\k , Y n . (ii) For k ≤ n, let C 1 ⊆ R k and C 2 ⊆ R n be two line-free cones, such that C 1 × {0} n-k and C 2 are in opposition with respect to the first k variables. Let f ∈ K C1 X k , g ∈ K C2 X n , and α 1 , . . . , α k , β 1 , . . . , β k ∈ K satisfy: for each 1 ≤ j ≤ k, α j = 0 if H k j (f ) and β j = 0 if H n j (g). Then, ( 22
) (f k≤n g) x1=α1β1,...,x k =α k β k = Res y1,...,y k 1 y 1 • • • y k f α 1 y 1 , . . . , α k y k g(β 1 y 1 , . . . , β k y k , x k+1 , . . . , x n ),
where the argument of the residue is understood as a product in

K τ (C1 k≤n C2) X n\k , Y k . (iii) For k ≤ n, let C 1 ⊆ R n and C 2 ⊆ R k be two line-free cones, such that C 1 and C 2 × {0} n-k are in opposition with respect to the first k variables. Let f ∈ K C1 X n , g ∈ K C2 X k , and α 1 , . . . , α k , β 1 , . . . , β k ∈ K satisfy: for each 1 ≤ j ≤ k, α j = 0 if H n j (f ) and β j = 0 if H k j (g). Then, ( 23
) (f n≥k g) x1=α1β1,...,x k =α k β k = Res y1,...,y k 1 y 1 • • • y k f α 1 y 1 , . . . , α k y k , x k+1 , . . . , x n g(β 1 y 1 , . . . , β k y k ),
where the argument of the residue is understood as a product in

K τ (C1 n≥k C2) X n\k , Y k .
Before the proof, observe that ( 22) and ( 23) cannot just be obtained as specializations of [START_REF] Flajolet | Analytic combinatorics[END_REF].

Proof. To prove [START_REF] Flajolet | Analytic combinatorics[END_REF], assume that α 1 , . . . , α k , β 1 , . . . , β k ∈ K satisfy: for each 1 ≤ j ≤ k, α j = 0 if H n j (f ) and β j = 0 if H k j (g). As a first consequence, for each 1 ≤ j ≤ k, α j β j = 0 if H n≤n j (f, g), so that by Lemma 6, the left-hand side of ( 21) is well-defined. As a second consequence, f α1 y1 , . . . , α k y k , x k+1 y k+1 , . . . , xn yn and g(β 1 y 1 , . . . , β k y k , y k+1 , . . . , y n ) are well defined, too, and are thus in K τ (C1 C2) X n\k , Y n . In a way similar to [START_REF] Fayolle | Random walks in the quarter-plane[END_REF] in the proof of Lemma 3, we reformulate their product h in the form:

h = 1 y 1 • • • y n u1,...,un f u1,...,un α u1 1 • • • α u k k x u k+1 k+1 • • • x un n y u1 1 • • • y un n v1,...,vn g v1,...,vn β v1 1 • • • β v k k y v1 1 • • • y vn n = i1,.
..,in (v1,...,vn)-(u1,...,un)=(i1,...,in) f u1,...,un g v1,...,vn (α u1

1 β v1 1 ) • • • (α u k k β v k k )x u k+1 k+1 • • • x un n y i1-1 1 • • • y in-1 n .
Like in Lemma 3, extracting residues with respect to y 1 , . . . , y n selects the term for which

i 1 = • • • = i n = 0, forcing (v 1 , . . . , v n ) = (u 1 , .
. . , u n ), which yields [START_REF] Flajolet | Analytic combinatorics[END_REF]. The proofs or ( 22) and ( 23) are similar, basing on analogous calculations.

Likewise, the following theorem can now be viewed as a generalization of Lemma 4 above. For the proof, we proceed like for the proof of that lemma, invoking Lemma 8 in place of Lemma 3.

Theorem 3. For every line-free cone C ⊆ R n that is in opposition to R n ≥0 with respect to the first k coordinates, for every φ ∈ K C X n , and for every λ 1 , . . . , λ k ∈ K, we have:

[x > 1 • • • x > k ]φ x1=λ1,...,x k =λ k = Res y1,...,y k 1 y 1 • • • y k λ1 y1 • • • λ k y k (1 -λ1 y1 ) • • • (1 -λ k y k ) R k ≤0 φ(y 1 , . . . , y k , x k+1 , . . . , x n ) (24) = Res y1,...,y k 1 y 1 • • • y k φ 1 y 1 , . . . , 1 y k , x k+1 , . . . , x n λ 1 y 1 • • • λ k y k (1 -λ 1 y 1 ) • • • (1 -λ k y k ) R k ≥0 , ( 25
)
where the brackets around rational functions in [START_REF] Goursat | Sur l'équation différentielle linéaire qui admet pour intégrale la série hypergéométrique[END_REF] and (25) denote taking their expansions in, respec-

tively, K R k ≤0 Y k and K R k ≥0 Y k . Proof. Fix C to R k ≥0 and ψ ∈ K C X k to the geometric series expansion of x1•••x k (1-x1)•••(1-x k )
. The desired positive part can then be represented in two ways as variants of Hadamard products:

[x > 1 • • • x > k ]φ x1=λ1,...,x k =λ k = ψ k≤n φ x1=λ1,...,x k =λ k = φ n≥k ψ x1=λ1,...,x k =λ k .
We then use Lemma 8 twice, which applies as C is in opposition to R n ≥0 with respect to the first k coordinates, thus to C × {0} n-k as well:

• Firstly, Lemma 8 (ii) can be used with

C 1 = C , C 2 = C, f = ψ, g = φ, α i = λ i , β i = 1, without
restriction on λ i ∈ K as ψ involves no monomial with negative exponent. Equation [START_REF] Gessel | A probabilistic method for lattice path enumeration[END_REF] then reads

[x > 1 • • • x > k ]φ x1=λ1,...,x k =λ k = Res y1,...,y k 1 y 1 • • • y k ψ λ 1 y 1 , . . . , λ k y k φ(y 1 , . . . , y k , x k+1 , . . . , x n ),
where ψ λ1 y1 , . . . , 24) and the announced expansion.

λ k y k is in K τ ((C ×{0} n-k ) k≤n {0} n ) X n\k , Y k , and thus in K -C Y k , hence (
• Secondly, Lemma 8 (iii) can be used with

C 1 = C, C 2 = C , f = φ, g = ψ, α i = 1, β i = λ i ,
without restriction on λ i ∈ K as ψ involves no monomial with negative exponent. Equation [START_REF] Gessel | A probabilistic method for lattice path enumeration[END_REF] then reads The following variant formulation of Theorem 3 avoids to potentially get a tautology when some of the specialization point is zero. Theorem 4. For every line-free cone C ⊆ R n that is in opposition to R n ≥0 with respect to the first k coordinates, for every φ ∈ K C X n , and for every λ 1 , . . . , λ k ∈ K, we have:

[x > 1 • • • x > k ]φ x1=λ1,...,x k =λ k = Res y1,...,y k 1 y 1 • • • y k φ 1 y 1 , . . . , 1 y k , x k+1 , . . . , x n ψ(λ 1 y 1 , . . . , λ k y k ), where ψ(λ 1 y 1 , . . . , λ k y k ) is in K τ (0 n≥k (C ×{0} n-k )) X n\k , Y k ,
1 x 1 . . . x k [x > 1 • • • x > k ]φ x1=λ1,...,x k =λ k = Res y1,...,y k 1 y 1 • • • y k 1 y1•••y k (1 -λ1 y1 ) • • • (1 -λ k y k ) R k ≤0 φ(y 1 , . . . , y k , x k+1 , . . . , x n ) (26) = Res y1,...,y k 1 y 1 • • • y k φ 1 y 1 , . . . , 1 y k , x k+1 , . . . , x n y 1 • • • y k (1 -λ 1 y 1 ) • • • (1 -λ k y k ) R k ≥0 , ( 27
)
where the brackets around rational functions in [START_REF] Guy | Lattice paths, reflections, & dimension-changing bijections[END_REF] and ( 27) denote taking their expansions in, respectively,

K R k ≤0 Y k and K R k ≥0 Y k .
Proof. In a way very similar to the proof of Theorem 3, fix C to R k ≥0 and ψ ∈ K C X k to the geometric series expansion of

1 (1-x1)•••(1-x k )
. Introduce as well φ = φ/(x 1 . . . x k ). The desired positive part can then be represented in two ways as variants of Hadamard products:

1 x 1 . . . x k [x > 1 • • • x > k ]φ x1=λ1,...,x k =λ k = ψ k≤n φ x1=λ1,...,x k =λ k = φ n≥k ψ x1=λ1,...,x k =λ k .
The proof now follows the same lines as for Theorem 3, using Lemma 8 twice: Equations ( 26) and ( 27) follow after observing that all specializations of any λ i (in particular, to 0) are well defined and that a factor y 1 . . . y k can move freely into or out of a bracket.

3.5.

Generating series of walks as residues. Now, we want to apply Theorem 4 to find representations as residues of the specializations of a walk series Q(x, y; t) at x = α and y = β for numbers α and β: we need this in particular for (α, β) ∈ {0, 1} 2 . For technical reasons, below we will in fact need such representations for more general α and β, namely elements of a field K of characteristic zero whose elements have zero derivative with respect to x and y.

We will obtain a formula of the form

(28) Q(α, β; t) = 1 xy [x > y > ]φ x=α,y=β = Res x,y 1 xy xȳ (1 -αx)(1 -β ȳ) R 2 ≤0 φ(x, y; t) = Res x,y 1 xy φ(x, ȳ; t) xy (1 -αx)(1 -βy) R 2 ≥0
, for some series φ to be determined and for residues that are residues of rational functions in K(x, y, t). Our first step is to express Q(x, y; t) as a positive-part extraction. To this end, Bousquet-Mélou and Mishna provide an appealing formula [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]Prop. 8], [START_REF] Kovacic | An algorithm for solving second order linear homogeneous differential equations[END_REF] xyQ(x, y; t) = [x > ][y > ]R(x, y; t), which represents the walk series as an extraction from the rational function R(x, y; t) = N (x, y)/(1 -tS(x, y)). Thus, their formula requires some care to be used in our context: we know that rational functions potentially admit several (distinct) positive parts in Q[[x, y; t]], depending on the cone used to expand it in Q Z 3 . So we need to determine a cone that results in the proper combinatorial representation of Q. Additionally, instead of our direct positive-part extraction [x > y > ] over Q Z 3 (and more generally K Z 3 after we specialize at x = α and y = β), they use iterated positive-part extractions: a first that operates coefficient-wise on series in t, namely [y > ] :

Q(x)[y, ȳ][[t]] → Q(x)[y][[t]
]; a second that operates coefficient-wise on series in y and t, namely

[x > ] : Q[x, x][y][[t]] → Q[x, y][[t]].
Then, they make the crucial observation that the (unambiguously defined) coefficients of [y > ]R with respect to y and t are not only in Q(x), but in fact for the set of R under consideration more specifically in Q[x, x], so that [x > ] can be applied. At this point, it will be sufficient for us to determine a cone C such that

(30) [x > y > ]φ = [x > ][y > ]R(x, y; t)
for the series expansion φ of R in Q C x, y, t . The cone C that will do is the cone Γ generated by the vectors (1, 1, 1), (1, -1, 1), (-1, 0, 0), so that elements of the ring Q Γ [[x, y; t]] can only involve monomials x k y m t n for k, m, n ∈ N satisfying -n ≤ m ≤ n and k ≤ n. This cone is line-free, making S Γ := Q Γ x, y; t a well-defined ring. Now, for each step set in Table 1, the product tS(x, y) involves only monomials x k y m t satisfying -1 ≤ k, m ≤ 1, making the rational function 1/ 1-tS(x, y) admit the expansion n≥0 S(x, y) n t n in S Γ . In addition, the coefficients 1/(x + x) and 1/(x + 1 + x) that occur in N for some of the step sets admit expansions in S Γ , so that by ring operations, the rational function R admits an expansion in S Γ , henceforth denoted φ = [R] Γ . Set Γ = R ≤0 ×{0}, another line-free cone, so that we can introduce the ring

S Γ = Q Γ x, y = Q[[x]][x, y, ȳ].
As vector spaces, we have S Γ ⊂ j∈Z S Γ t j . With this observation, φ = j∈N [N S j ] Γ t j , where the brackets are taken in S Γ . Therefore, our [x > y > ]φ equals Bousquet-Mélou and Mishna's

[x > ][y > ]R if and only if for any j ≥ 0, our [x > y > ][N S j ] Γ equals their [x > ][y > ](N S j ).
We now fix j ≥ 0. There are two cases, depending on the step set in Table 1:

• Cases 1 to 16. The assumptions of Lemma 9 below are satisfied. The lemma proves that equality holds. • Cases 17 to 19. Both N and S are finite sums in Q[x, x, y, ȳ], so [N S j ] Γ is just N S j , and the equality [

x > y > ][N S j ] Γ = [x > ][y > ](N S j ) holds. Lemma 9. Let N (x, y) = N 1 (x)y + N -1 (x)ȳ and S(x, y) = A 1 (x)y + A 0 (x) + A -1 (x)ȳ be given by Laurent polynomials N 1 , A 1 , A 0 , and A -1 of Q[x, x],
and by a rational function N -1 of Q(x). Under the additional assumption that the denominator of

N -1 divides A 1 in Q[x, x], then for all j ∈ N, [y > ]N S j ∈ Q[x, x, y] and [x > y > ][N S j ] Γ = [x > ][y > ](N S j )
, where the brackets on the left-hand side are taken with respect to the cone Γ = R ≤0 × {0} and the parentheses on the right-hand side are in Q(x)[y, ȳ].

Proof. Write S = A 1 y + à where à ∈ Q[x, x, ȳ] and set P = N -1 A 1 ∈ Q[x, x]. Writing brackets for expansions in Q Γ x, y , we observe that [N ] Γ = N 1 y + [N -1 ] Γ ȳ, [S] Γ = S, and [N -1 ] Γ A 1 is in Q[x, x], implying [N -1 ] Γ A 1 = N -1 A 1 = P . Given j ∈ N, a computation yields N S j = (N 1 y + N -1 ȳ)(A 1 y + Ã) j = N 1 y(A 1 y + Ã) j + P j =1 j A -1 1 y -1 Ãj-+ N -1 ȳ Ãj .
The large parenthesis in the right-hand side is in Q[x, x, y, ȳ]; we call it L. The last term N -1 ȳ Ãj is a polynomial in ȳ with no non-negative powers of y, and it is thus in

Q(x)[ȳ]. Consequently, [x > ][y > ](N S j ) = [x > ][y > ]L. A similar computation delivers [N S j ] Γ = L + [N -1 ] Γ ȳ Ãj , where the Lau- rent polynomial L is viewed in Q Γ x, t . Applying our operator [x > y > ] kills the last term, returning [x > y > ][N S j ] Γ = [x > y > ]L = [x > ][y > ]L.
The result is proved.

The following lemma summarizes our discussion.

Lemma 10. For any field K of characteristic zero whose elements have zero derivative with respect to x and y, for any (α, β) ∈ K 2 , and for any step set in Table 1, Equation (28) above holds when φ is set to the expansion of R = N/(1 -tS) in Q Γ x, y; t , for the cone Γ generated by the vectors (1, 1, 1), (1, -1, 1), and (-1, 0, 0).

Proof. Set K, α, β, Γ, and φ as in the statement. The first identity in [START_REF] Koutschan | A fast approach to creative telescoping[END_REF] follows from ( 29) and [START_REF] Krattenthaler | Lattice path enumeration[END_REF]; the other identities are proven by Theorem 4, used with the field K of the present lemma, provided we prove that Γ is in opposition to R 3 ≥0 with respect to the first two variables. To see this, note: (i) that both π 2 (Γ) and π 2 (R 3 ≥0 ) equal R ≥0 and are thus line-free cones; (ii) that Γ ∩ R 3 ≥0 is generated by (1, 1, 1), (1, 0, 1), (0, 1, 1), and (0, 0, 1), so that its intersection with R 2 × {0} reduces to {(0, 0, 0)}.

3.6.

Annihilating generating series of walks by creative telescoping. Our general goal is to justify via creative telescoping the computation of a differential equation in t satisfied by the residue with respect to x and y. The objects manipulated during the computation are rational functions, and it is usually taken for granted that results of these calculations can be ported without difficulties to other domains. Here, we want to formally prove this for the present situation. For this section again, K is a field satisfying the conditions of Lemma 10.

Lemma 11. Let F ∈ K(x, y, t). If there exist U, V ∈ K(x, y, t) such that F = ∂ x U + ∂ y V , then for any cone C for which F, U, V all admit an expansion, Res x,y [F ] C = 0.

Proof. From the hypothesis, it follows [F ]

C = ∂ x [U ] C + ∂ y [V ] C .
As the residue of a derivative is zero by Lemma 1, the result is proved by linearity.

As in our applications the creative-telescoping certificates U and V will be large and messy expressions, whose manipulation can be costly, it is comfortable to state a refinement of the previous lemma that avoids the need to inspect U and V so as to determine a cone C for which they admit expansions. Lemma 12. Let F ∈ K(x, y, t). If there exist U, V ∈ K(x, y, t) such that F = ∂ x U + ∂ y V , then for any line-free cone C for which F admits an expansion, Res x,y [F ] C = 0.

Proof. Since C is line free, there exists a monomial order such that C is compatible with . As F , U and V now admit expansions in the field K ((x, y, t)), there is a cone C containing C so that all three rational functions admit expansions in K C x, y; t . Finally applying Lemma 11 proves the result. Theorem 5. For some fixed step set S, let N (x, y) and S(x, y) be as in Table 1, let R(x, y; t) denote N (x, y)/(1 -tS(x, y)) ∈ Q(x, y; t), and let Q(x, y; t) = ∞ n,i,j=0 q i,j;n x i y j t n ∈ Q[x, y][[t]] be the corresponding generating function of walks. Let Γ be the cone generated by the vectors (1, 1, 1), (1, -1, 1), and (-1, 0, 0), so that the expansion [R] Γ exists in Q Γ x, y; t and Q can be identified with its expansion there. For K a field containing Q, whose elements have zero derivative with respect to x and y, let (α, β) ∈ K2 and set F to either of

F 1 = 1 xy R(x, y; t) (α -x)(β -y)
and

F 2 = R(1/x, 1/y; t) (1 -αx)(1 -βy) . Suppose L ∈ K[t] ∂ t and F, U, V ∈ K(x, y, t) are such that L(F ) = ∂ x U + ∂ y V . Then L(Q(α, β; t)) = 0.
Proof. The line-free cones

C 1 = τ (R 2 ≥0 × {0}) 2≤3 Γ and C 2 = τ Γ 3≥2 (R 2 ≥0 × {0}
) are, by the construction of Lemma 10, the cones such that the product in the left-hand residue in [START_REF] Koutschan | A fast approach to creative telescoping[END_REF] takes place in K C1 t, x, y (with indeterminates in this order) while the product in the right-hand residue takes place in K C2 t, x, y (same order). With this notation, Equation ( 28) rewrites ( 31)

Q(α, β; t) = Res x,y [F 1 ] C1 = Res x,y [F 2 ] C2 .
Set i to either of 1 and 2 so that F = F i , then set C to C i . By Lemma 11 and the expression of L(F ) in terms of U and V , we have Res

x,y L([F ] C ) = Res x,y [L(F )] C = 0. Since L is free of x, y, we have Res x,y L([F ] C ) = L(Res x,y [F ] C ). By (31), we have L(Q(α, β; t)) = L(Res x,y [F ] C ) = 0, as claimed.
4. Results

4.1.

Obtaining proved hypergeometric formulas. Let K be a field of characteristic zero whose elements have zero derivative with respect to x and y. To obtain a proven expression for the specialization

Q(α, β; t) of Q(x, y; t) at (x, y) = (α, β) ∈ K 2 , it is sufficient to find: (1) a nonzero operator L ∈ K[t] ∂ t for which L(Q(α, β; t)) is proved to be 0, (2)
a closed-form solution f (t) of L that agrees with Q(α, β; t) to a sufficiently high order. Concerning point 1, Theorem 5 provides such a L by applying creative telescoping. The rational functions U and V that are also part of the output can be discarded, as they are not needed for our application to positive-part extraction. Taking K = Q, this is already sufficient to obtain formally proved differential equations for the generating functions Q(t) = Q(1, 1; t), which was the initial goal of our work.

To obtain a proven equation for Q(x, y; t), one could in principle follow the same strategy: introduce the bivariate function field K = Q(α, β), for indeterminates α and β; use Theorem 5 for this K; then replace α and β by x and y at the end. However, this computation would be too slow to work in practice. One could instead consider computing operators L α,β ∈ Q[t] ∂ t for sufficiently many points (α, β) ∈ Q 2 and then interpolate into L ∈ Q(x, y)[t] ∂ t . This would raise the delicate problem of determining how many interpolation points need to be taken to prove that L is correct.

What does work in practice is to refrain from computing an annihilator L for the complete generating function Q(x, y; t). Instead, we obtain two formally proved differential equations: a first one for Q(x, 0; t), by using creative telescoping over K = Q(α) and substituting x for α; a second one for Q(0, y; t), by using creative telescoping over K = Q(β) and substituting y for β. In either case, the ground field K to be used is a univariate rational-function field, which permits calculations to terminate in reasonable time. Although these operators do not lead to an annihilator for Q(x, y; t), they are used below to get a closed form for it.

For all instances of creative telescoping, we effectively used Koutschan's package 2 HolonomicFunctions for Mathematica, then double-checked with Chyzak and Pech's package3 Mgfun for Maple.

Concerning point 2, the operators obtained by point 1 all factor miraculously into factors that have order 1 with the exception of the left-most one that can have order 1 or 2, as we could verify using Maple's DEtools [DFactor]. At this point, we can capitalize on the work in [START_REF] Fang | 2-descent for second order linear differential equations[END_REF] and obtain 2 F 1 formulas for Q(1, 1; t), Q(x, 0; t), and Q(0, y; t) by the method already used in [START_REF] Bostan | Explicit formula for the generating series of diagonal 3D rook paths[END_REF]. To this end, we appealed to Imamoglu's implementation 4 for Maple. 4.2. Algebraic nature of the counting series. To prove the transcendence of one of our trivariate counting series Q(x, y; t), it is sufficient to prove the transcendence of one of its evaluations for specific values α of x and β of y-and indeed, the complete generating functions for all cases listed in Table 1 are transcendental as a consequence of Q(0, 0; t) being transcendental. The same holds true for the bivariate series Q(x, 0; t) and Q(0, y; t).

We now turn to the case of univariate enumerating series Q(α, β; t), that is, specializations of Q(x, y; t) at specific numerical values α and β for x and y, and we describe how we prove transcendence of a given Q(α, β; t) after having computed an annihilating operator L for it. Remember from the discussion in Section 4.1 that L factors in the form L L , where L has order 1 or 2. Define Q(t) = L (Q(α, β; t)), which has to be algebraic if Q(α, β; t) is algebraic. In each choice of a step set and of α, β in {0, 1}, the computation of a few terms of the series expansion of Q proves, upon applying L , that Q is non-zero. Now, if L has order 2, Kovacic's algorithm [START_REF] Kovacic | An algorithm for solving second order linear homogeneous differential equations[END_REF] decides if it has (non-zero) algebraic solutions: if not, this proves that Q cannot be algebraic. The case when L has order 1 is similar, and simpler as solving a first-order linear ODE is very elementary. In our calculations, we used Maple's DEtools[kovacicsols] in the second-order case and DEtools[expsols] in the first-order case for this test of existence of algebraic solutions of the operators L. This proves the first part of Theorem 2, namely that among the 19 × 4 combinatorially meaningful specializations Q(α, β; t) (α, β ∈ {0, 1}) of the complete generating function Q(x, y; t), only four cases could possibly be algebraic functions: Case 17 for x and y specialized to 1, and Case 18 for (x, y) specialized to (0, 1), (1, 0), and [START_REF] Andrews | Special functions, volume 71 of Encyclopedia of Mathematics and its Applications[END_REF][START_REF] Andrews | Special functions, volume 71 of Encyclopedia of Mathematics and its Applications[END_REF].

In these four cases, we indeed prove the algebraicity of the corresponding counting series. The procedure we followed was simply to use specific algorithms when solving the relevant differential equation L(y) = 0, and note that it admits a basis of algebraic solutions. Explicit expressions in these four cases are then found using the initial terms of the counting series. For instance, in case 18 for (α, β) = (1, 0) and for (α, β) = (0, 1), the operator L proved to annihilate Q(1, 0; t) and Q(0, 1; t) is

L = t 3 (2t + 1)(6t -1)∂ 4 t + 4t 2 (48t 2 + 13t -3)∂ 3 t + 36t(3t + 1)(8t -1)∂ 2 t + (1152t 2 + 168t -24)∂ t + 288t + 24,
which admits the basis of solutions

s 1 = 1 t , s 2 = 4t 2 -8t + 1 t 3 , s 3 = 12t 2 -1 t 3 , s 4 = (2t + 1) 1/2 (1 -6t) 3/2 t 3 .
Therefore, Q(1, 0; t) is equal to a linear combination c 1 s 1 +c 2 s 2 +c 3 s 3 +c 4 s 4 for some constants c 1 , c 2 , c 3 , c 4 . Identification of initial terms using Q(1, 0; t) = 1 + t + 4t 2 + 12t 3 + O(t 4 ) provides a linear system in the c i 's, finally proving that Q(1, 0; t) is equal to s 4 -s 2 . This concludes the proof of Theorem 2. Note that, for any of the 19 models, the excursions generating functions Q(0, 0; t) could alternatively be proved transcendental by an argument based on asymptotics, similar to the one in [START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF]: using [START_REF] Denisov | Random walks in cones[END_REF] the coefficient of t 12n in Q(0, 0; t) grows like κρ n /n γ for γ ∈ {3, 4, 5} (see Table 3), and this implies transcendence of Q(0, 0; t) by [START_REF] Flajolet | Analytic models and ambiguity of context-free languages[END_REF]Theorem D]. By contrast, note that this asymptotic argument is not sufficient to prove the transcendence of all the other transcendental specializations, as showed for instance by Case 7 at (0, 1) (γ = 3/2) and at (1, 1) (γ = 1/2), and by Case 17 at (1, 0) (γ = 5/2), see Tables 4, 5 and6. 4.3. Asymptotic formulas for coefficients. This section discusses how to develop asymptotic estimates on the counting coefficients from the closed forms for the generating series, in each of the 19 walk models with prescribed length (and unprescribed endpoint). This bases on asymptotics-transfer theorems (developed in Analytic Combinatorics) to get the results. Not all asymptotic formulas could be proved by our approach, so we report here on a reduction of the proofs of asymptotic formulas to the proof of a number of integral representation of rational constants, some of which remain conjectural. What is most difficult is proving the constants (κ below) in front of the asymptotic pattern ρ n /n γ , which were initially heuristically discovered by numerical calculations (number recognition) [START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF].

All of our generating series consist of hypergeometric functions, rational or algebraic factors, and iterated primitivations. As was explained in the introduction, so far all these mathematical ingredients have been viewed as formal Laurent series in the field C((t)) and operators on them, but the same series are convergent as expansions of functions meromorphic in disks centered at 0. This analytic interpretation is crucial to the method of the present section.

A subtle point in this regard is the interpretation of the primitivation operator in the context of series of functions. To match the fact that the (formal) primitive A of a (formal) series A(t) = n≥m, n =-1 a n t n of C((t)) is ( A)(t) = n≥m, n =-1 a n t n+1 /(n + 1) and has a zero constant term, we introduce an operator pp of polar part, defined by pp(A)(t) = n<0 a n t n , and we interpret analytically by the integral representation

(32) ( A)(t) = - ∞ t pp(A)(u) du + t 0 (A -pp(A))(u) du.
This split is needed, as the meromorphic function that expands as A is in general not integrable at 0. The integral representation [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] will occur implicitly in the proofs of Theorems 8 and 9 below. In the generating functions, hypergeometric terms take the form 2 F 1 (a, b; c; w), with good constraints on a, b, and c, so that enough of their asymptotic behavior (e.g., at w = 1) can be derived easily, and where w is a rational or algebraic term in t. Singularities of the generating series can occur at poles or branch point of the cofactors, or at values of t where w = w(t) becomes one of the singularities of the 2 F 1 , namely 0, 1, and ∞.

We first expected that the problem of proving all coefficient asymptotics would be just a problem of Analytic Combinatorics (in the sense of the theory well exposed by Flajolet and Sedgewick in [21, Chap. VI], largely basing on transfer theorems by Flajolet and Odlyzko [START_REF] Flajolet | Singularity analysis of generating functions[END_REF]). It turned out that the part of these theories to extract asymptotics is minimal, most of the difficulties being in computing asymptotic expansions of non-standard representations of functions. (These expansions are then input to transfer theorems.)

What also made the problem more difficult is a broad spectrum of the possible asymptotic phenomenons/asymptotic patterns (i.e., what ingredient of the function contributes to the asymptotics). A recurrent situation is when the dominant singularity is caused by an algebraic factor between two primitivation operators. In some cases, this is worsened by a polar part of the integrand in the inner primitivation: this part is necessary and disappears in the expansion as a formal power series, owing to the alternation of primitivations and multiplications by specific algebraic factors; but to get the constants κ by analytic means, it is easier to remove this polar part in calculations of asymptotic estimates.

In view of this, we have in fact formally proved only some of the constants κ. However, in all the cases, those κ-as well as other auxilliary constants that appear in the asymptotic study-can be formulated as definite integrals of univariate functions obtained from Q(x, y; t). Proving the asymptotic formulas up to the constants κ is equivalent to proving closed-form evaluations of those integrals. This is exemplified and described now in four typical cases that cover all difficulties that may occur. Theorem 6. The number of walks of length n in the quarter plane that use steps from the step set , start at the origin, and end anywhere is asymptotically equivalent to 8 3π 8 n . Proof. For this case, the generating series is proved by the method of Section 4.1 to be

Q(1, 1; t) = 1 t t 0 1 (1 + 4u) 3 2 F 1 3 2 3 2 2 16u(1 + u) (1 + 4u) 2 du.
The possible singularities of the integrand in Q(1, 1; t) are the pole of the rational factor and the values of u for which the argument w of the hypergeometric function is either 1 or ∞. These are u = -1/4 and u = 1/8, and the dominant singularity is indeed at 1/8, where w = 1. The asymptotic analysis of the 2 F 1 at 1 (using normalization by (15.8.12) in [START_REF] Frank | NIST handbook of mathematical functions[END_REF] before using (15.8.10) in [START_REF] Frank | NIST handbook of mathematical functions[END_REF] 5 ) delivers the following asymptotic equivalent of the coefficient c n of t n in the integrand:

c n = [t n ] 1 (1 + 4t) 3 2 F 1 3 2 3 2 2 16t(1 + t) (1 + 4t) 2 ∼ 8 3π 8 n .
Then, making explicit the action on coefficients of integrating and dividing by t leads to

[t n ] Q(1, 1; t) = [t n+1 ] m c m m + 1 t m+1 = c n n + 1 ∼ 8 3π 8 n n .
This is the announced result, including a proved constant κ = 8/(3π). n . Proof. The generating series is proved by the method of Section 4.1 to be

Q(1, 1; t) = 1 t t 0 1 -2u ((1 + 2u)(1 + 6u)) 3/2 2 F 1 3 2 3 2 2 16u (1 + 2u)(1 + 6u) du.
Potential singularities of the integrand are singularities of the algebraic factor (u = -1/2 and u = -1/6) and points where the argument w of the hypergeometric function becomes infinite (same values for u) or tends to 1 (u = 1/6). There are two dominant singularities: at +1/6, where w = 1, and at -1/6, where w = -∞. Following the principles of Analytic Combinatorics, asymptotic terms contributed by both points have to be considered and added. The same approach as for the proof of Theorem 6, replicated in parallel, delivers two respective contributions n . However, the first one dominates and is the only one to remain in an asymptotic equivalent for the coefficient of t n in the series expansion of the integrand. As in the proof of Theorem 6, the operator

I = 1/4 0 (1 -4v) 1/2 ( 1 2 + v) v 2 1 + 1 2v(1 + 2v)(1 + 4v 2 ) 1/2 × (1 -v) 2 F 1 3 2 1 2 1 16v 2 1 + 4v 2 -(1 + v)(1 -4v + 8v 2 ) 2 F 1 1 2 1 2 1 16v 2 (1 + 4v 2 ) - 1 v 2 dv.
If I = -2, then Conjecture 1 holds.

Proof. The generating series is proved by the method of Section 4.1 to be

Q(1, 1; t) = 1 t(t -1) t 0 u (1 -4u) 3/2 4 + u 0 (1 -4v) 1/2 ( 1 2 + v) v 2 1 + 1 2v(1 + 2v)(1 + 4v 2 ) 1/2 × (1 -v) 2 F 1 3 2 1 2 1 16v 2 1 + 4v 2 -(1 + v)(1 -4v + 8v 2 ) 2 F 1 1 2 1 2 1 16v 2 (1 + 4v 2 )
dv du.

Here, we have a linear combination of hypergeometric functions, but this is no problem: the dominant singularity is at t = 1/4, and dominates ± 1 2 √

3 , where w = 16t 2 /(1 + 4t 2 ) = 1, as well as

± √ - 1
2 , where |w| = ∞. Call f the innermost integrand. It proves successful to remove from f its singular part at the origin, whose contribution after double integration can be obtained by an easy use of the theory. Near 0, f behaves indeed as 1/t 2 -9 + O(t). Proceeding by linearity after defining g(t) = f (t) -1/t 2 , which is analytic on [0, 1/4], we get

Q(1, 1; t) = √ 1 -4t 2t(t -1) + 1 t(t -1) t 0 u u 0 g(v) dv (1 -4u) 3/2 du. Near 1/4, g(v) behaves as -16 + Θ( √ 1 -4v), so that 1/4 v g(v) dv = -4(1 -4v) + Θ((1 -4v) 3/2 ). As I = 1/4 0 g(v) dv, we have u u 0 g(v) dv = I/4 + Θ(1 -4u). Next, integrating with respect to u yields t 0 u u 0 g(v) dv (1 -4u) 3/2 du = I 8 √ 1 -4t + O(1), so that Q(1, 1; t) = -2I 3 √ 1 -4t + O(1).
Finally, by a transfer theorem, the number of walks of length n in Conjecture 1 is proved to be asymptotically equivalent to -2I 3 √ π 4 n √ n provided I = 0, and the announced asymptotic formula of the conjecture holds if and only if the constant identity I = -2 holds.

Note that the constant identity I = -2 can be checked numerically (for instance up to 100 digits). In particular, proving I = 0 would be sufficient to prove that the wanted asymptotic expansion is of the form κ 4 n √ n . In this regard, a plot of g suggests that g(t) < -7 for t ∈ [0, 1/4], therefore that I < -7/4.

I = 1/3 0 (1 -3v) 1/2 v 3 (1 + v) 1/2 × 1 + (1 -10v 3 ) 2 F 1 3 4 5 4 1 64v 4 + 6v 3 (3 -8v + 14v 2 ) 2 F 1 5 4 7 4 2 64v 4 - 2 v 3 + 4 v 2 dv.
If I = 1, then Conjecture 2 holds.

Proof. The generating series is proved by the method of Section 4.1 to be

Q(1, 1; t) = 1 t(t -1) t 0 u 2 (1 + u) 1/2 (1 -3u) 3/2 -7 + u 0 (1 -3v) 1/2 v 3 (1 + v) 1/2 × 1 + (1 -10v 3 ) 2 F 1 3 4 5 4 1 64v 4 + 6v 3 (3 -8v + 14v 2 ) 2 F 1 5 4 7 4 2 64v 4 dv du.
The situation is similar to Case 7, starting with a dominant singularity at t = 1/3, close to but below 1 √ 8 , where w = 64t 4 = 1. In this case, removing the polar part of the innermost integrand f at the origin, namely 2 t 3 -4 t 2 , is again enough to find an equivalent formulation of the result as a numerical integral. This time,

g(t) = f (t) -2 t 3 + 4 t 2 = -18 + Θ( √ 1 -3v) near t = 1/3, so that 1/3 v g(v) dv = -6(1 -3v) + Θ((1 -3v) 3/2
). Continuing by linearity and using I = 1/3 0 g(v) dv, we get the local expansion Again, the constant identity I = 1 can be checked numerically, and proving I = 4 would be sufficient to prove that the wanted asymptotic expansion is of the form κ 3 n √ n . 4.3.5. Other cases. In all 19 × 4 cases, our hypergeometric expressions for the counting functions produce similar equalities of integrals. While most of these constant equalities remain conjectural, proving their correctness would imply the asymptotics in Tables 3,4, 5, and 6 in the Appendix. In some cases, proving equality with limited numerical error is sufficient to prove the constants ρ and γ in the asymptotic behavior of the form κρ n /n γ , but not the constant κ, which is just proved to be nonzero. 4.4. Additional tables. The results of our computations are described in this section, where the most characteristic features of the computed data are provided as tables. For the data in full, we refer our readers to the web page of this article http://specfun.inria.fr/chyzak/ssw/.

Q(1, 1; t) = (4 -I) 3 √ 3 2 1 √ 1 -3t + O (1)
The hypergeometric series occurring in explicit expressions for Q(1, 1; t) and for Q(x, y; t) are respectively given in Table 2, together with the rational-function substitution in those series. The complete closed forms we obtained for Q(0, 0; t), Q(0, 1; t), Q(1, 0; t), Q(1, 1; t), Q(x, 0; t), Q(0, y; t), and Q(x, y; t) are given on the web site.

Various degrees, the differential order with respect to t, and the maximal size of integers in the annihilating operator and certificates that we computed for each step set can be obtained from the web site as well. Thus, the annihilators-the same as in [START_REF] Bostan | Automatic classification of restricted lattice walks[END_REF]-are finally proved. Annihilators and certificates can also be downloaded in full form from the web site, both as human-readable Maple sources and as a pre-digested Maple library.

For each of the step set in Table 1, the algebraic or transcendental nature of the series Q(0, 0; t), Q(0, 1; t), Q(1, 0; t), and Q(1, 1; t), as well as asymptotic equivalent for the coefficients of t n in these series, are respectively given in Tables 3, 4, 5, and 6 in the Appendix. There, 'N' denotes a transcendental series and 'Y' an algebraic one, and the result has been proved by the method of Section 4.2. Regarding the status of asymptotic equivalents, the constants in the tables (named κ in Section 4.3) refine (and correct) those provided in [5].

The possibility of several interlaced regimes with same parameters ρ and γ but non-zero different κ was first observed and suggested to us by Melczer. By redoing the calculations as in [5], using convergence acceleration of (subsequences of) the sequences (q x,y;n ) and (q n ) and using the PSLQ algorithm, we numerically guessed those constants κ, confirming the known ones and obtaining the new ones. That [5] could overlook those constants is explained by the nature of the method of convergence acceleration, which in its native form considers values at powers of 2 only, and is thus not able to distinguish regimes for odd vs even n, let alone for various residues modulo 3 or 4. In their recent manuscript [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF], Melczer and Wilson proved our guessed constants in all 19×4 cases via analytic combinatorics in several variables. (n = 2p) 0 (n = 2p + 1)

Table 3. Nature of the generating series for (x, y) = (0, 0) and coefficient asymptotics (n = 2p) 0 (n = 2p + 1) Table 4. Nature of the generating series for (x, y) = (0, 1) and coefficient asymptotics

A = 1 + √ 2, B = 1 + √ 3, C = 1 + √ 6, λ = 7 + 3 √ 6, µ = 4 √ 6-
A = 1 + √ 2, B = 1 + √ 3, C =

64t 2 (t 2

 22 +1) (16t 2 +1) 2

19

 19

  v1,...,vn y v1 1 • • • y vn n = i1,...,in (v1,...,vn)-(u1,...,un)=(i1,...,in)

1 +

 1 C 1 and such that the support of g is contained in

  and thus in K C Y k , hence[START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF] and the announced expansion.

4. 3 . 1 .

 31 Case 4: walks with steps from .

4. 3 . 4 .Conjecture 2 . 9 .

 3429 Case 5: walks with steps from . The number of walks of length n in the quarter plane that use steps from the step set , start at the origin, and end anywhere is asymptotically equivalent to Define the real number

,n

  from which follows, by a transfer theorem, that the number of walks of length n in Conjecture 2 is asymptotically equivalent to 4provided I = 4, and the announced asymptotic formula of the conjecture holds if and only if the constant identity I = 1 holds.

  + x3 y 2 -x3 y + xȳ -xȳ 2 + x 3 ȳ2 -x 3 ȳ xy + (x + x) + xȳ Table

	8 A151326		1 x + 1 +	x ȳ	(x + 1 + x)y + (x + 1 + x)y + (x + x) + ȳ	ȳ
	9 A151302 10 A151329	(x -x) y -	x + x + 1 + x	x ȳ	(x + 1 + x)y + (x + x)ȳ (x + 1 + x)y + (x + x) + (x + x)ȳ
	11 A151261 12 A151297	(x -x) (y -(x + 1 + x) ȳ)	y + (x + 1 + x)ȳ y + (x + x) + (x + 1 + x)ȳ
	13 A151275 14 A151314	(x -x) y -	x + 1 + x + x ȳ x	(x + x)y + (x + 1 + x)ȳ (x + x)y + (x + x) + (x + 1 + x)ȳ
	15 A151255 16 A151287	(x -x) (y -(x + x) ȳ)	y + (x + x)ȳ y + (x + x) + (x + x)ȳ
	17 A001006 18 A129400	xy -xy 2 + x2 y -xȳ + xȳ 2 -x 2 ȳ	y + x + xȳ (1 + x)y + (x + x) + (1 + x)ȳ
	19 A005558	xy -xy 2

  1/y][[t]], owing to particular properties of N and S (see Lemma 9 below); let [y > ] act term by term, obtaining a series in Q(x)[y][[t]] that can be shown to actually belong to Q[x, 1/x][y][[t]] for all cases in Table 1; then let [x > ] act term by term, finally obtaining an element of Q[x][y][[t]]. In this reading, the composition [x > ][y > ] of positive-part operators is only applied to Laurent polynomials, for which it is certainly well-defined, in a unique way.

  and λ, µ ≥ 0, u := λu 1 + µu 2 and v := λv 1 + µv 2 are in C 1 and C 2 , respectively, because C 1 , C 2 are cones. Consequently, λ(u 1

  Hence we have:

	Res y1,...,yn h =	f u1,...,un g u1,...,un x u1 1 • • • x un n = f g,
	(u1,...,un)
	as was to be proved to justify (15).
	To prove (16), set C := C 1

k≤n

C 2 ⊆ R k+n , which is a line-free cone by Lemma 2. Now, observe that f (x 1 /y 1 , . . . , x k /y k ) and g(y 1 , . . . , y k , x k+1 , . . . , x n

  4.3.2. Case 3: walks with steps from .Theorem 7. The number of walks of length n in the quarter plane that use steps from the step set , start at the origin, and end anywhere is asymptotically equivalent to

	√	6	6 n
	π

  The number of walks of length n in the quarter plane that use steps from the step set , start at the origin, and end anywhere is asymptotically equivalent to4

		1 t	translates in just a division by n.
	4.3.3. Case 7: walks with steps from	.
	Conjecture 1. 3 √	π	4 n √ n .
	Theorem 8. Define the real number

Table 5 .

 5 Nature of the generating series for (x, y) = (1, 0) and coefficient asymptotics

	1 +	√	6, λ = 7 + 3	√	6, µ = 4	√ 6-1 19

Table 6 .

 6 Nature of the generating series for (x, y) = (1, 1) and coefficient asymptotics

	A = 1 +	√	2, B = 1 +	√ 3, C = 1 +	√	6, λ = 7 + 3	√	6, µ = 4	√ 6-1 19

http://www.risc.jku.at/research/combinat/software/ergosum/RISC/HolonomicFunctions.html

http://algo.inria.fr/chyzak/mgfun.html

http://www.math.fsu.edu/ ~eimamogl/hypergeometricsols

Alternative references are http://dlmf.nist.gov/15.8.E12 and http://dlmf.nist.gov/15.8.E10, respectively.

M. van Hoeij's work was supported by NSF grant 1319547. M. Kauers's work was supported by FWF grants Y464-N18, F5004 and W1214. L. Pech's work was supported in part by the Microsoft Research -INRIA Joint Centre and by INRIA. c 2016. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/ licenses/by-nc-nd/4.0/.http://

Finally, the kernel equation (first equation in Lemma 4 of [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF], which we reproduce here)

xy(1 -tS(x, y))Q(x, y; t) = xy -txA -1 (x)Q(x, 0; t) -tyB -1 (y)Q(0, y; t) + tQ(0, 0; t), where A -1 and B -1 are defined as in Lemma 9 and is 1 if and only if (-1, -1) ∈ S and 0 otherwise, expresses Q(x, y; t) in terms of the obtained formulas for Q(x, 0; t) and Q(0, y; t). As observed in the introduction, all 2 F 1 functions appearing in formulas can be expressed in terms of complete elliptic integrals. Furthermore, for each of the 19 step sets, those functions do not depend on the choice of specialization points α and β, so that Q(x, y; t) involves a single hypergeometric function (up to variations under contiguity and derivatives).

We remark that the nature of the generating functions for our walk models is even more rigid: not only can each model be expressed in terms of a single 2 F 1 function, but, if one can afford increasing degrees and/or algebraic extensions, all models can be expressed in terms of the same single 2 F 1 function, namely

12 ; 1; u). The emergence of this function is no surprise, owing to Takeuchi's classification [START_REF] Takeuchi | Commensurability classes of arithmetic triangle groups[END_REF]. This classification establishes connected components in the class of 2 F 1 functions, under simple kinds of transformations. One of the connected components is well represented as the following diagram (see [START_REF] Vidūnas | Transformations of some Gauss hypergeometric functions[END_REF]

( 1 2 , 1 2 ; 1) for some positive integer m, a rational function w(t) of degree d, and another rational function r(t). Up to integer shifts, all entries in our table are written in terms of 2 F 1 functions involving the boxed parameters of our diagram. If we do not mind increasing the degree of w by a factor 3, 4, or 6, they can all be rewritten in terms of 2 F 1 ( 1 12 , 5 12 ; 1; w), itself related to elliptic curves and modular forms (see, e.g., [START_REF] Stienstra | On the Picard-Fuchs equation and the formal Brauer group of certain elliptic K3surfaces[END_REF] or [START_REF] Stiller | Classical automorphic forms and hypergeometric functions[END_REF]). Alternatively, all of our formulas can be expressed up to algebraic extensions in terms of 2 F 1 ( 1 2 , 1 2 ; 1; w), itself related to the complete elliptic function K(k). The connections mentioned above can be made explicit by providing formulas for the main edges in Takeuchi's diagram:

• The hypergeometric series 2 F 1 ( 1 2 , 1 2 ; 1; w) and 2 F 1 ( 1 4 , 3 4 ; 1; w) are related by the well-known duplication formula [1, Eq. (3.1.7)]:

• Less well-known formulas [24, Eq. ( 119) & (126)] result, upon evaluating at η = 1/12, into

This relates 2 F 1 ( 1 4 , 3 4 ; 1; t) and 2 F 1 ( 1 3 , 2 3 ; 1; t) via a degree-4 algebraic transformation. Combining these formulas shows that 2 F 1 ( 1 3 , 2 3 ; 1; t) can be expressed in terms of 2 F 1 ( 1 2 , 1 2 ; 1; t) via a degree-4 function in a degree-6 algebraic extension, as indicated in the diagram.

Appendix

The tables on the next pages gather information described in Section 4.4.

INRIA, Université Paris-Saclay, 91120 Palaiseau, France E-mail address: alin.bostan@inria.fr