Andrew Elvey Price
email: andrew.elvey@univ-tours.fr

ENUMERATION OF THREE QUADRANT WALKS WITH SMALL STEPS AND WALKS ON OTHER M-QUADRANT CONES

We address the enumeration of walks with small steps conned to a two-dimensional cone, for example the quarter plane, three-quarter plane or the slit plane. In the quarter plane case, the solutions for unweighted step-sets are already well understood, in the sense that it is known precisely for which cases the generating function is algebraic, D-nite or D-algebraic, and exact integral expressions are known in all cases. We derive similar results in a much more general setting: we enumerate walks on an M -quadrant cone for any positive integer M , with weighted steps starting at any point. The main breakthrough in this work is the derivation of an analytic functional equation which characterises the generating function of these walks, which is analogous to one now used widely for quarter-plane walks. In the case M = 3, which corresponds to walks avoiding a quadrant, we provide exact integral-expression solutions for walks with weighted small steps which determine the generating function C(x, y; t) counting these walks. Moreover, for each step-set and starting point of the walk we determine whether the generating function C(x, y; t) is algebraic, D-nite or D-algebraic as a function of x and y. In fact we provide results of this type for any M -quadrant cone, showing that this nature is the same for any odd M . For M even we nd that the generating functions counting these walks are D-nite in x and y, and algebraic if and only if the starting point of the walk is on the same axis as the boundaries of the cone. E-mail address:

Introduction

The systematic study of walks with small steps in the quarter plane was initiated by Bousquet-Mélou and Mishna in 2010 [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF], and since then there has been great progress on the model [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF][START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF][START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Dreyfus | Walks in the quarter plane: genus zero case[END_REF]. The model is dened as follows: given a step set S ⊂ {-1, 0, 1} 2 \ {(0, 0)}, determine the generating function

Q(x, y; t) = ∞ n=0 i,j≥1
q(i, j; n)t n x i y j , where q(i, j; n) is the number of walks of length n, starting at [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF][START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF], and ending at (i, j) using steps in S and staying in the strictly positive quadrant. 1 A priori, there are 256 distinct step sets S, but after removing duplicates and cases that are equivalent to half-plane models, Bousquet-Mélou and Mishna identied 79 non-trivial and combinatorially distinct models. The study of these models is now in some sense complete as it is known for each S precisely where the generating function ts into the hierarchy Algebraic ⊂ D-nite ⊂ D-Algebraic. Recall that a generating function is called Algebraic with respect to a certain variable if it is related to that variable by a non-trivial polynomial equation with coecients only depending on the other variables, and it is called D-nite (resp. D-algebraic) if it satises a linear (resp. polynomial) dierential equation with respect to that variable whose coecients are polynomial in that variable. For a multivariate series to be algebraic (resp. D-nite, D-algebraic) it must be algebraic (resp. D-nite, D-algebraic) with respect to each variable.

Of the 79 models proposed by Bousquet-Mélou and Mishna, 4 models admit an algebraic generating function [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF][START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF], 19 further models admit a D-nite generating function [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF][START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane[END_REF], 9 further models admit a D-algebraic generating function [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] and the remaining 47 models admit a generating function which is not D-algebraic [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Dreyfus | Walks in the quarter plane: genus zero case[END_REF], in which case we say that the generating function is D-transcendental. Moreover, in the 74 cases known as non-singular, an exact integral expression is known for the generating function [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF], while other exact expressions are known in the 5 singular cases [START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF]. In recent years a number of articles have focused on the equivalent question for walks in the three-quadrant cone C = {(i, j) : i > 0 or j > 0}, Shown in Figure 1. That is determining the generating function C(x, y; t) = ∞ n=0 (i,j)∈C c(i, j; n)t n x i y j , where c(i, j; n) is the number of walks of length n, starting at [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF][START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF], and ending at (i, j) using steps in S and staying in C.

Figure 1. Walks in the three-quadrant cone C. Left: A walk starting at the standard starting point (1, 1) using step set #12 from Table 1. Right: A walk starting at (4, 0) using step set #10. Even though the generating function for walks with step set #10 starting at [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF][START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF] is D-transcendental, we will show that the generating function for walks starting at (4, 0) is D-algebraic in x.

The study of walks in the three-quadrant cone was initiated by Bousquet-Mélou in [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF], where she enumerated walks with two step sets (#1 and #2 in Table 1), showing that the associated generating function is D-nite. Raschel and Trotignon [START_REF] Raschel | On walks avoiding a quadrant[END_REF] then found a transformation relating walks with any of the step sets #4-#10 to walks in the quarter plane -allowing them to deduce integral expression solutions in these cases. Building on this work Dreyfus and Trotignon [START_REF] Dreyfus | On the nature of four models of symmetric walks avoiding a quadrant[END_REF] showed that the last three of these step sets (#8 -#10) admit non-D-algebraic generating functions, while step set #7 admits a D-algebraic generating function. Subsequently, using algebraic methods, Bousquet-Mélou and Wallner [START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF] adapted the method of [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF] to enumerate walks with step set #3, again showing that these admit a D-nite generating function. Finally, in a very recent article [START_REF] Bousquet-Mélou | Enumeration of three-quadrant walks via invariants: some diagonally symmetric models[END_REF], Bousquet-Mélou used invariants to show that three cases known as the Kreweras cases (#4-#6) admit algebraic generating functions. Together these classify 10 models into the complexity hierarchy (algebraic, D-nite, D-algebraic). Walks with specied endpoints have been enumerated for 2 further models (#11-#12) by Budd [START_REF] Budd | Winding of simple walks on the square lattice[END_REF] and 2 further models by the current author (#13-#14) [START_REF] Elvey | Counting lattice walks by winding angle[END_REF], both of these results by relating the model to walks counted by winding angle. Moreover, in [START_REF] Mustapha | Non-D-nite walks in a three-quadrant cone[END_REF], Mustapha used asymptotic properties to show that C(x, y; t) is not D-nite in t for any of the 51 non-singular step sets S admitting an innite group, that is, precisely the models which are not D-nite in the quarter plane. Remarkably, in all of the cases (#1-#10) shown in Table 1, the generating function has the same nature as in the quarter plane. Dreyfus and Trotignon were the rst to conjecture that this holds more generally -that the nature is the same for any of the 74 non-singular step-sets S [START_REF] Dreyfus | Walks in the quarter plane: genus zero case[END_REF]. We note that for models (#10-#13), the (single variable) generating functions considered in [START_REF] Budd | Winding of simple walks on the square lattice[END_REF][START_REF] Elvey | Counting lattice walks by winding angle[END_REF] were found to be algebraic in t, which only coincides with the general quarter-plane case for model #10. For models #11-#13, the generating function Q(x, y; t) is D-nite but not algebraic [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]. This is perhaps explained by the fact that the walks considered in [START_REF] Budd | Winding of simple walks on the square lattice[END_REF][START_REF] Elvey | Counting lattice walks by winding angle[END_REF] for models #11-#13 start at [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF]0) rather than the standard starting point [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF][START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF].

Model #1 #2 #3 #4 #5 #6 #7
Nature of C(x, y; t) D-trans [START_REF] Dreyfus | Walks in the quarter plane: genus zero case[END_REF] D-trans [START_REF] Dreyfus | Walks in the quarter plane: genus zero case[END_REF] D-trans [START_REF] Dreyfus | Walks in the quarter plane: genus zero case[END_REF] [10] [START_REF] Budd | Winding of simple walks on the square lattice[END_REF] [17] [START_REF] Elvey | Counting lattice walks by winding angle[END_REF] Table 1. Previously solved models on the 3-quadrant cone for walks starting at [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF][START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF]. Models #11-#14 only solved for specied end-points.

Main Results. For each of the 74 distinct non-singular step-sets S, we relate the generating function C(x, y; t) to the solution of a simple analytic functional equation (Theorem 2.8), analogous to one found by Raschel for the enumeration of walks in the quadrant [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF]. Our method is also a direct generalisation of that of Raschel, which in turn is based on a method of Fayolle, Iasnogorodski and Malyshev [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF][START_REF] Fayolle | Random walks in the quarter-plane[END_REF], which they used in a probabilistic context. Using our analytic functional equation, we derive an exact integral expression solution for C(x, y; t) (Theorem 3.3), analogous to those of Raschel in the quarter-plane [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF]. We then prove that the nature of C(x, y; t) as a function of x (or y) is the same as that of Q(x, y; t), and we conjecture that these series also have the same nature as functions of t. In fact we determine the nature of the generating function C(x, y; t) with respect to x in the more general setting of walks with weighted small steps starting at any point in the cone C.

We then dene M -quadrant cones for any positive integer M and consider generating functions Q j (x, y; t) counting walks on these spaces that nish within a quadrant determined by j. For M ≤ 4 the space is already familiar: The 1-quadrant cone is the quarter plane, the 2-quadrant cone is the half plane, we already discussed the 3-quadrant cone, and the 4-quadrant cone is the slit plane studied in [START_REF] Bousquet-Mélou | Walks on the slit plane: other approaches[END_REF], [START_REF] Bousquet | Walks on the slit plane[END_REF] and [START_REF] Rubey | Transcendence of generating functions of walks on the slit plane[END_REF]. For each M , each step-set S, each value j and each starting point, we determine whether the generating function Q j (x, y; t) is algebraic, D-nite or D-algebraic as a function of x and y. We nd that the nature of these generating functions depends on the parity of M , but otherwise does not depend on its value. That is, for all odd M (and all j) we prove that Q j (x, y; t) has the same nature as C(x, y; t), whereas for M even, we nd that the generating function is always D-nite, and that it is algebraic if and only if the starting point is on the same axis as the boundaries of the cone. For M ≥ 2, we even determine the nature of the generating functions for xed t, showing that this nature still doesn't depend on the exact value of M , only its parity.

Note that by our denition of walks in the 3-quadrant cone, steps directly between (1, 0) and (0, 1) are allowed, whereas they are forbidden in [START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF], for example. We do not expect this to aect the nature of the generating function, in fact in Section 4.4 we show that in most cases the nature is the same.

Outline of the paper. In Sections 2, 3 and 4, we address the enumeration of walks in the three-quadrant cone. First, in Section 2, we relate the generating function C(x, y; t) counting these walks to meromorphic functions A(z) and B(z) on C, then in Theorem 2.8, we characterise these functions using a simple functional equation. In Section 3, we use this functional equation to derive explicit integral expressions determining A(z) and B(z), and hence implicitly determining C(x, y; t). In Section 4, we use the functional equation to determine the nature of C(x, y; t) as a function of x, that is, when it is algebraic, D-nite or D-algebraic. As an example, in Subsection 4.3 we give a more explicit solution for the case that the walk starts on the x-axis.

In Sections 5 and 6, we address the enumeration of walks on an M -quadrant cone for any positive integer M . For M = 1 this is the familiar quarter plane case, while for M = 3 this is precisely the case studied in Sections 2, 3 and 4. In Section 5 we dene the model precisely and derive analytic functional equations characterising the series involved, as in Section 2. In Section 6, we use these functional equations to determine the nature of the series involved as functions of x. To our knowledge this was not previously completed even in the quarter plane case in the full generality we consider.

Finally in Section 7, we pose a variety of questions left open by this work.

We have a number of appendices in which we prove technical results that we use throughout the article. In Appendix A, we use results from [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF] to prove Lemmas 2.3 and 2.5 which allow us to relate the generating function C(x, y; t) to the meromorphic functions A(z) and B(z). In Appendix B, we describe how the nature of the generating functions such as C(x, y; t) relates to the nature of the related analytic functions, such as A(z) and B(z). In appendix C, we dene and discuss the group of the walk. Finally in Appendix D we discuss results coming from the Galois theory of q-dierence equations that we use in the D-transcendental cases.

Functional equations for walks in the three-quadrant cone

We start with a step-set S ⊂ {-1, 0, 1} 2 \ {(0, 0)}, a weight w s > 0 for each s ∈ S and a starting point (p, q) with p > 0, q ≥ 0. Throughout this article, we assume that S is a nonsingular step-set. That is, for any line through the origin, at least one element of S lies on each side of . As explained by Bousquet-Mélou and Wallner, [9, Section 2.2], the generating function C(x, y; t) is algebraic if S is singular, as then the model can be written in terms of half-plane models.

We will determine the generating function C(x, y; t) counting walks starting at (p, q), taking steps from S with all intermediate points lying in the three-quadrant cone C and with the weight of the walk being the product of the weights w s of the steps. Note that the standard starting point is (p, q) = (1, 1) and in the unweighted case w s = 1 for each s ∈ S.

The following lemma results from considering the nal step of a walk counted by C(x, y; t):

Lemma 2.1. Dene the single step generating function P(x, y) by

P(x, y) = (α,β)∈S w (α,β) x α y β
Then there are series A 1

y ; t ∈ t y R 1 y [[t]], B 1 x ; t ∈ t x R 1 x [[t]
] and F(t) ∈ tR [[t]] which satisfy C(x, y; t) = x p y q + tP(x, y)C(x, y; t) -F(t) -B 1 x ; t -A 1 y ; t .

(1)

Moreover, this equation together with the fact that c(i, j; n) = 0 for i, j ≤ 0, characterises the generating function C(x, y; t) = t≥0 i,j∈R c(i, j; n)x i y j t n , as well as the series A, B and F.

Proof. We start by proving combinatorially that the equation holds for some series A, B and F.

Note that C(x, y; t) is the generating function counting walks restricted to C, so tP(x, y)C(x, y; t) is the generating function counting these walks with an additional step added at the end (possibly not restricted to C). To get the generating function C(x, y; t) we need to add the contribution x p y q for the empty walk and subtract the contribution H(x, y; t) to tP(x, y)C(x, y; t) from walks not ending in C. So C(x, y; t) = x p y q + tP(x, y)C(x, y; t) -H(x, y; t).

Since the walks counted by H(x, y; t) nish outside C, and have at least one step, we must have

H(x, y; t) ∈ tR 1 x , 1 y [[t]].
Moreover, since only the nal step lies outside C, the endpoint must be at some (0, k) or (k, 0) for k ≤ 0. Hence, we can write H as

H(x, y; t) = F(t) + A 1 y ; t + B 1 x ; t , (2)
completing the proof that such an equation holds. Now we will show that (1) uniquely determines the series involved. Taking the x i y j t 0 coecient on both sides of the equation yields the initial condition c(i, j; 0) = δ (i,j),(p,q) , while taking the x i y j t n coecient for n ≥ 1 and (i, j) ∈ C yields

c(i, j; n) = (α,β)∈S w (α,β) c(i -α, j -β; n -1),
which determines every value c(i, j; n) inductively. Finally the series H and therefore the series A, B and F are determined by

H(x, y; t) = x p y q + tP(x, y)C(x, y; t) -C(x, y; t). B A B A Figure 2.
Left: a walk counted by A 1 y ; t in the case where (p, q) = (1, 1) and S is the step-set shown. Right: a walk counted by B 1

x ; t in the case where (p, q) = (3, 2) and S is the step-set shown.

The equation (2) reveals a combinatorial interpretation of the series A, B and F: While H counts walks starting at (p, q) and ending just outside C whose intermediate points all lie within C, the series A, B and F each count a subset of those walks. In particular, the series A 1 y ; t counts those walks ending on the negative y-axis A := {(0, j) : j < 0}, the series B 1

x ; t counts those walks ending on the negative x-axis B := {(i, 0) : i < 0}, and F(t) counts those walks ending at (0, 0) (see Figure 2). The unusual condition that the coecients c(i, j; n) of C(x, y; t) vanish for i, j ≤ 0 makes this equation dicult to solve directly, so we follow [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF][START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF] and partition C into three quadrants Q -1 , Q0 , Q1 , dened as follows (see Figure 3)

Q -1 := {(i, j) : i > 0; j < 0}, Q0 := {(i, j) : i > 0; j ≥ 0}, Q1 := {(i, j) : i ≤ 0; j > 0}.
In fact we have shifted the quadrants Q -1 , Q0 down one space compared to those considered in [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF] so that it is impossible to step directly between Q -1 and Q1 and so that our condition on the starting point (p, q) is now that (p, q) ∈ Q0 . Note that we have Qj rather than Q j when the quadrant includes points on either the x-axis or y-axis. Now, we dene Q -1 x, 1 y ; t , Q 0 (x, y; t) and Q 1 1

x , y; t to be the generating functions counting walks in C, starting at (p, q) and ending in Q -1 , Q0 and Q1 , respectively. So

C(x, y; t) = Q -1 x, 1 y ; t + Q 0 (x, y; t) + Q 1 1 x , y; t ,
and

Q -1 ∈ x y R x, 1 y [[t]], Q 0 ∈ xR [x, y] [[t]] and Q 1 ∈ yR 1 x , y [[t]].
The following lemma rewrites (1) as three equations characterising

Q -1 x, 1 y ; t , Q 0 (x, y; t) and Q 1 1 x , y; t .
Lemma 2.2. Dene the kernel K(x, y; t) by

K(x, y; t) = tP(x, y) -1.
There are series

V 1 (y; t), V 2 (y; t) ∈ R[y][[t]] and H 1 (x; t), H 2 (x; t) ∈ R[x][[t]
] satisfying the three equations

K(x, y; t)Q -1 x, 1 y ; t = A 1 y ; t + H 1 (x; t) + 1 y H 2 (x; t) (3)
K(x, y; t)Q 0 (x, y; t) = -x p y q + F (t) -V 1 (y; t) -xV 2 (y; t) -H 1 (x; t) - 1 y H 2 (x; t) (4) K(x, y; t)Q 1 1 x , y; t = B 1 x ; t + V 1 (y; t) + xV 2 (y; t). (5)
Moreover, these three equations characterise the series

Q -1 x, 1 y ; t , Q 0 (x, y; t), Q 1 1 x , y; t , V 1 (y; t), V 2 (y; t), H 1 (x; t), H 2 (x; t), A 1 y ; t , B 1
x ; t and F(t). Proof. We can rewrite (1) as

K(x, y; t) Q -1 x, 1 y ; t + Q 0 (x, y; t) + Q 1 1 x , y; t = -x p y q + F(t) + A 1 y ; t + B 1 x ; t , (6)
which is precisely the sum of (3), ( 4) and [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF]. Rearranging yields

K(x, y; t)Q 1 1 x , y; t -B 1 x ; t = -x p y q +F(t)+A 1 y ; t -K(x, y; t) Q 0 (x, y; t) + Q -1 x, 1 y ; t .
The left hand side of this equation lies in

xR 1 x , y [[t]] while the right hand side lies in R x, y, 1 y [[t]],
so, since the sides are equal, they must lie in the intersection

xR 1 x , y [[t]] ∩ R x, y, 1 y [[t]] = R[y][[t]] + xR[y][[t]],
which means there are series [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF]. Similarly, in the equation

V 1 (y; t), V 2 (y; t) ∈ R[y][[t]] satisfying
K(x, y; t) Q 0 (x, y; t) + Q 1 1 x , y; t -B 1 x ; t +x p y q -F(t) = A 1 y ; t -K(x, y; t)Q -1 x, 1 y ; t ,
The left hand side lies in

1 y R 1 x , x, y [[t]] while the right hand side lies in R x, 1 y [[t]], so they both lie in the intersection R[x][[t]]+ 1 y R[x][[t]].
Hence there are series [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]. Finally (4) follows from subtracting (3) and ( 5) from [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF].

H 1 (x; t), H 2 (x; t) ∈ R[x][[t]] satisfying
We also note that there are combinatorial interpretations of the series V 1 , V 2 , H 1 , H 2 : they each count walks starting at (p, q) and ending either in C or just outside C with a restriction on the nal step. In particular:

• V 1 (0; t) -V 1 (y; t) counts walks whose nal step is from Q0 to Q1 ,

• V 1 (0; t) counts walks whose nal step is from Q1 to (0, 0),

• xV 2 (y; t) counts walks whose nal step is from Q1 to Q0 ,

• H 1 (x; t) counts walks whose nal step is from Q -1 to Q0 or (0, 0),

• -1 y H 2 (x; t) counts walks whose nal step is from Q0 to Q -1 or (0, -1). In section 5, we will use combinatorial interpretations of this form to generalise this section to M -quadrant cones for any positive integer M .

Parameterisation of the kernel curve

Following the method used in the quarter plane pioneered by Fayolle, Iasnogorodski and Raschel [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF][START_REF] Fayolle | Random walks in the quarter-plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF] we start by xing t ∈ 0, 1

P(1,1)
and then we consider the curve

E t = {(x, y) : K(x, y; t) = 0}.
Recall our assumption that S is a non-singular step-set. Under this assumption, the curve E t is known to have genus 1, so we will be able to parameterise it using elliptic functions X(z) and Y (z). More precisely we have the following lemma, which we prove in Lemma A.2 in Appendix A, using results from [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF]. The transformation that converts Lemma A.2 to Lemma 2.3 is described above Lemma A.2. Lemma 2.3. There are meromorphic functions X, Y : C → C ∪ {∞} and numbers γ, τ ∈ iR with (πτ ) > (2γ) > 0 satisfying the following conditions

• K(X(z), Y (z)) = 0 • X(z) = X(z + π) = X(z + πτ ) = X(-γ -z) • Y (z) = Y (z + π) = Y (z + πτ ) = Y (γ -z) • |X(-γ 2 )|, |Y ( γ 2 )| < 1
• Counting with multiplicity, the functions X(z) and Y (z) each contain two poles and two roots in each fundamental domain {z c + r 1 π + r 2 πτ : r 1 , r 2 ∈ [0, 1)}. Moreover, X(z) and Y (z) are dierentially algebraic with respect to z and t, while τ and γ are dierentially algebraic as functions of t.

In fact, it follows from Proposition A.1 that (X(z), Y (z)) parameterises E t , that is,

E t = {(X(z), Y (z)) : z ∈ C}. (7)
We intend to substitute x → X(z) and y → Y (z) into (3), ( 4) and ( 5), however we can only do this as long as the series in these equations converge, which occurs in the situations described by the following lemma Lemma 2.4. The series...

• y x Q -1 x, 1 y ; t converges absolutely for x, y satisfying |x| ≤ 1 ≤ |y| ≤ ∞, • 1
x Q 0 (x, y; t) converges absolutely for x, y satisfying |x|, |y| ≤ 1,

• 1 y Q 1 1
x , y; t converges absolutely for x, y satisfying |y| ≤ 1 ≤ |x| ≤ ∞. In fact all of the series that we consider

Q -1 , Q 0 , Q 1 , A, B and C converge absolutely for x, y satisfying |x|, |y| ∈ tP (1, 1), 1 tP (1, 1)
.

Proof. Since the weighted number of walks of length n in the entire plane is (P (1, 1)) n , the number of walks restricted to the three quarter plane must not be higher than this. Hence, the coecient [t n ]C(1, 1; t) ≤ P (1, 1) n , so for xed t < 1 P (1,1) , the series C(1, 1; t) converges. So the series Q -1 (1, 1; t), Q 0 (1, 1; t) and Q 1 (1, 1; t), whose sum is C(1, 1; t), also converge. Since

y x Q -1 x, 1 y ; t ∈ R x, 1 y [[t]],
and it has only non-negative coecients, it must converge for

|x| ≤ 1 ≤ |y| ≤ ∞. Similarly, since 1 y Q 1 1 x , y; t ∈ R 1 x , y [[t]], it must converge for |y| ≤ 1 ≤ |x| ≤ ∞. Finally, since 1 x Q 0 (x, y; t) ∈ R [x, y] [[t]],
it must converge for |x|, |y| ≤ 1. The only remaining statement to prove is the nal statement of the Lemma, which requires a bit more precision. As we discussed, the coecient [t n ]C(1, 1, t) ≤ P (1, 1) n , moreover, the polynomial [t n ]C(x, y, t) is a Laurent polynomial in x and y with degrees of x and y lying in [-n, n]. Hence for xed x, y ∈ C, the coecient

|[t n ]C(x, y, t)| ≤ [t n ]C(1, 1, t) max |xy| n , x y n , y x n , 1 |xy| n ≤ P(1, 1) max |xy|, x y , y x , 1 |xy| n . So for t ∈ 0, 1 P(1,1)
and |x|, |y| ∈ tP (1, 1), 1 tP(1,1) , the series C(x, y, t) converges, as required. We can use the same reasoning to prove the same result for all of the other series that we consider.

According to the lemma above, in order to substitute x → X(z) and y → Y (z) into the series Q j , it often suces to understand how |X(z)| and |Y (z)| compare to 1. To do this, we prove the following lemma in Appendix A, using [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF]Lemma 2.9]. Lemma 2.5. The complex plane can be partitioned into simply connected regions {Ω s } s∈Z (see Figure 4) satisfying

Ω 0 Ω 1 Ω 2 Ω 3 Ω 4 Ω -1 Ω -2 Ω -3 Ω -4 0 π -π γ 2 -γ 2 -πτ -γ 2 -πτ 2 -πτ +γ 2 -πτ + γ 2 -πτ πτ +γ 2 πτ 2 πτ -γ 2 πτ -γ 2 πτ |X(z)|, |Y (z)| < 1 |Y (z)| < 1 ≤ |X(z)| |X(z)|, |Y (z)| < 1 1 ≤ |X(z)|, |Y (z)| |X(z)|, |Y (z)| < 1 |Y (z)| < 1 ≤ |X(z)| |X(z)| < 1 ≤ |Y (z)| |X(z)| < 1 ≤ |Y (z)| 1 ≤ |X(z)|, |Y (z)|
s∈Z Ω 4s ∪ Ω 4s+1 = {z ∈ C : |Y (z)| < 1}, s∈Z Ω 4s-2 ∪ Ω 4s-1 = {z ∈ C : |Y (z)| ≥ 1}, s∈Z Ω 4s-1 ∪ Ω 4s = {z ∈ C : |X(z)| < 1}, s∈Z Ω 4s+1 ∪ Ω 4s+2 = {z ∈ C : |X(z)| ≥ 1},
moreover, the equations

π + Ω s = Ω s , sπτ + γ -Ω 2s ∪ Ω 2s+1 = Ω 2s ∪ Ω 2s+1 ⊃ sπτ + γ 2 + R, sπτ -γ -Ω 2s ∪ Ω 2s-1 = Ω 2s ∪ Ω 2s-1 ⊃ sπτ -γ 2 + R, hold for each s ∈ Z.
Proof. This is equivalent to Lemma A.3, using the transformations described in Appendix A just before Lemma A.2 and just before Lemma A.3

In some sections it will be useful to parameterise the series using the Jacobi theta function

ϑ(z, τ ) := ∞ n=0 (-1) n e iπτ n(n+1) e (2n+1)iz -e -(2n+1)iz , (8)
which is dened for all z, τ ∈ C satisfying (τ ) > 0. In the literature, the function ϑ(z, τ ) is sometimes written as ϑ 11 (z, τ ) or θ 1 (z, e iπτ ). Recall that τ is xed in this section, so we will generally think of ϑ as a function of z. Note that this function has neither π nor πτ as a period, however elliptic functions with these two periods can easily be constructed using ϑ due to the following relations

ϑ(z + π, τ ) = -ϑ(z, τ )
and

ϑ(z + πτ, τ ) = -e -2iz-iπτ ϑ(z, τ ). (9)
Moreover, ϑ(z, τ ) has no roots and its only poles are at the points z ∈ πZ + πτ Z. Using these properties allows us to parameterise X and Y using ϑ.

Proposition 2.6. There is some

α ∈ Ω 0 ∪ Ω -1 , β ∈ Ω 0 ∪ Ω 1 , δ ∈ Ω 1 ∪ Ω 2 , ε ∈ Ω -2 ∪ Ω -1 and x c , y c ∈ C \ {0} satisfying X(z) = x c ϑ(z -α, τ )ϑ(z + γ + α, τ ) ϑ(z -δ, τ )ϑ(z + γ + δ, τ ) Y (z) = y c ϑ(z -β, τ )ϑ(z -γ + β, τ ) ϑ(z -ε, τ )ϑ(z -γ + ε, τ ) .
Proof. We will prove the result for X(z) as the proof for Y (z) is identical. From Lemma 2.3, we know that X(z) contains two roots and two poles in each fundamental domain. Consider the fundamental domain

F = {z ∈ Ω -1 ∪ Ω 0 ∪ Ω 1 ∪ Ω 2 : (z) ∈ [0, π)}
and let α ∈ F and δ ∈ F be a root and pole of X(z), respectively. From Lemma 2.5, we must have

α ∈ Ω -1 ∪ Ω 0 and δ ∈ Ω 1 ∪ Ω 2 . Now, since X(z) = X(-γ -z)
, the value -γ -δ must also be a pole of X(z), so more generally, all of the point in δ + πZ + πτ Z ∪ -γ -δ + πZ + πτ Z are poles of X. In the case that δ /

∈ -γ 2 + π 2 Z + πτ
2 Z, this accounts for all poles of X(z), so X(z)ϑ(z -δ, τ )ϑ(z + γ + δ, τ ) has no poles. In the case that δ ∈ -

γ 2 + π 2 Z + πτ 2 Z, we have X(z -δ) = X(-γ -δ -z) = X(δ -z)
, so X must have a double pole at δ. Then again X(z)ϑ(z -δ, τ )ϑ(z + γ + δ, τ ) has no poles. In either case this implies that the function X(z) dened by

X(z) := X(z) ϑ(z -δ, τ )ϑ(z + γ + δ, τ ) ϑ(z -α, τ )ϑ(z + γ + α, τ )
has no poles except possibly a single pole at each z ∈ -γ -α + πZ + πτ Z. But X(z) is an elliptic function with periods π and πτ , so it cannot have only a single pole in each fundamental domain [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF]Page 8]. Therefore it must have no poles, and is therefore a constant function. Writing X(z) = x c where x c ∈ C yields the desired result. Note x c = 0 as this would imply that X(z) was the 0 function.

Example: In the case of simple walks, that is S = {(1, 0), (0, 1), (-1, 0), (0, -1)} and w (α,β) = 1 for (α, β) ∈ S, the equation relating X(z) and Y (z) is

X(z) + 1 X(z) + Y (z) + 1 Y (z) = 1 t .
One can check that if we dene

X(z) = e -iγ ϑ(z, τ )ϑ(z + γ, τ ) ϑ(z -γ, τ )ϑ(z + 2γ, τ )
and

Y (z) = e -iγ ϑ(z, τ )ϑ(z -γ, τ ) ϑ(z + γ, τ )ϑ(z -2γ, τ ) ,
where γ = πτ 4 , then X(z) + 1

X(z) + Y (z) + 1 Y (z)
has no poles, so it must be constant. Then substituting z = γ 2 yields an equation relating τ and t, which can be written as

e -iγ ϑ γ 2 , τ 2 ϑ 3γ 2 , τ 2 = 1 + 2t - √ 1 + 4t 2t .
This allows q = e iπτ 4

= e iγ to be written as a series in t with initial terms

q = t + 4t 3 + 34t 5 + 360t 7 + • • •

Analytic reformulation of functional equations

Using the results in the previous section, we can substitute x = X(z) and y = Y (z) into (3), (4) and [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF] for z in the regions Ω -1 , Ω 0 and Ω 1 , respectively, yielding [START_REF] Dreyfus | Walks in the quarter plane: genus zero case[END_REF], [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF] and [START_REF] Dreyfus | On the nature of four models of symmetric walks avoiding a quadrant[END_REF] in the following proposition: Proposition 2.7. The functions

L H (z) := H 1 (X(z); t) + 1 Y (z) H 2 (X(z); t), for z ∈ Ω 0 ∪ Ω -1 , (10)
L V (z) := V 1 (Y (z); t) + X(z)V 2 (Y (z); t), for z ∈ Ω 0 ∪ Ω 1 , (11)
A(z) := A 1 Y (z) ; t , for z ∈ Ω -1 ∪ Ω -2 , (12)
B(z) := B 1 X(z)
; t ,

for z ∈ Ω 1 ∪ Ω 2 . ( 13
)
are well dened and satisfy the equations

0 = A(z) + L H (z) for z ∈ Ω -1 , (14)
0 = -X(z) p Y (z) q + F (t) -L V (z) -L H (z) for z ∈ Ω 0 , (15)
0 = B(z) + L V (z) for z ∈ Ω 1 (16)
B(z) = B(πτ -γ -z) = B(z + π) (17)
A(z) = A(-πτ + γ -z) = A(z + π) . (18)
Proof. In the specied domain of [START_REF] Budd | Winding of simple walks on the square lattice[END_REF], |X(z)| ≤ 1, so the series H 1 (X(z); t) and H 2 (X(z); t) converge, which implies that L H (z) is well dened. Similarly the series in [START_REF] Dreyfus | Dierential algebraic generating series of weighted walks in the quarter plane[END_REF], ( 12) and ( 13) converge, as the rst parameter of each generating function has modulus at most 1. Now, ( 14), ( 15) and ( 16) follow from substituting x = X(z) and y = Y (z) into (3), ( 4) and [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF], respectively, as we always have K(X(z), Y (z)) = 0, and in each case the series Q j converges.

Finally, for z ∈ Ω 1 ∪ Ω 2 we have πτ -γ -z ∈ Ω 1 ∪ Ω 2 , so B(πτ -γ -z) is well dened. Then [START_REF] Elvey | Counting lattice walks by winding angle[END_REF] follows from X(z) = X(πτ -γ -z). Similarly, for z ∈ Ω -1 ∪ Ω -2 , the function A(-πτ + γ -z) is well dened, and so [START_REF] Elvey | The six-vertex model on random planar maps revisited[END_REF] follows from Y (z) = Y (-πτ + γ -z).

While these equations are a priori dened on dierent sets, by meromorphic extension we will be able to compare them directly, as we will see from the following theorem: Theorem 2.8. The functions A(z) and B(z) extend to meromorphic functions on C which, along with the constant F = F(t), are uniquely dened by the equations

X(z) p Y (z) q = A(z) + F + B(z), (19)
B(z) = B(πτ -γ -z), (20)
A(z) = A(-πτ + γ -z), (21)
B(z) = B(z + π), (22)
A(z) = A(z + π), [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] along with the conditions (i) A(z) has no poles in

Ω 0 ∪ Ω -1 ∪ Ω -2 , (ii) the poles of Y (z) for z ∈ Ω -1 ∪ Ω -2 are roots of A(z), (iii) B(z) has no poles in Ω 0 ∪ Ω 1 ∪ Ω 2 ,
(iv) the poles of X(z) for z ∈ Ω 1 ∪ Ω 2 are roots of B(z). Proof. From (14), we have A(z) = -L H (z) for z ∈ Ω -1 . But the right hand side is meromorphic on Ω -1 ∪Ω 0 , so we can use it to extend A to a meromorphic function on Ω -2 ∪Ω -1 ∪Ω 0 . Similarly, [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF] allows us to write A(z) as a function of L V (z) for z ∈ Ω 0 , allowing us to extend the domain of A to include Ω 1 . Finally [START_REF] Dreyfus | On the nature of four models of symmetric walks avoiding a quadrant[END_REF] allows us to write A(z) as a function of B(z) on Ω 1 , allowing us to extend A(z) to the entire domain

Ω -2 ∪ Ω -1 ∪ Ω 0 ∪ Ω 1 ∪ Ω 2 . Similarly B(z) extends to a meromorphic function on Ω -2 ∪ Ω -1 ∪ Ω 0 ∪ Ω 1 ∪ Ω 2 as do L H (z)
and L V (z). Since ( 14), ( 15) and ( 16) hold in regions with non-empty interior, they must hold on all of

Ω -2 ∪ Ω -1 ∪ Ω 0 ∪ Ω 1 ∪ Ω 2 .
Finally, adding these three equations and multiplying by X(z)Y (z)/t yields [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF].

To extend the functions to C, we use [START_REF] Elvey | Counting lattice walks by winding angle[END_REF] and [START_REF] Elvey | The six-vertex model on random planar maps revisited[END_REF] as follows: From Lemma 2.5, we know that

- 1 2 (πτ -γ) + R ⊂ Ω -2 ∪ Ω -1 and 1 2 (πτ -γ) + R ⊂ Ω 1 ∪ Ω 2 .
Hence both of these lines, and the region delimited by these lines, is contained in

Ω -2 ∪ Ω -1 ∪ Ω 0 ∪ Ω 1 ∪ Ω 2 . Now, since A(z) satises (18) for z ∈ Ω -2 ∪ Ω -1 , it extends meromorphically to the function A(z) := A(-πτ + γ -z) for z ∈ -πτ + γ -Ω -2 ∪ Ω -1 ∪ Ω 0 ∪ Ω 1 ∪ Ω 2
, which contains the region between the lines

- 3 2 (πτ -γ) + R and - 1 2 (πτ -γ) + R.
Together, these extend the denition of A(z) to the entire region containing

Ω 1 ∪ Ω 2 and -πτ + γ -Ω 1 ∪Ω 2 = Ω 1 ∪Ω 2 -2(πτ -γ)
as well as the region between these spaces. Now, for z ∈ Ω 1 ∪Ω 2 we can combine ( 17), ( 18) and ( 19), giving

A(z) = X(z) p Y (z) p -X(πτ -γ -z) p Y (πτ -γ -z) p + A(z -2(πτ -γ)).
This recursively allows us to extend A(z) meromorphically to the space between Ω 1 ∪ Ω 2 + 2k(πτ -γ) and Ω 1 ∪ Ω 2 + 2(k + 1)(πτ -γ) for any integer k. Hence A(z) is a meromorphic function on the union C of these spaces. The relations between A(z), L H (z), L V (z) and B(z) then allow these other three functions to extend meromorphically to C.

We will now show that conditions (i)-(iv) hold. The series dening B(z) for z ∈ Ω 1 ∪ Ω 2 converges, so B(z) has no poles in this region. Moreover, since the series has 1/|X(z)| as a factor, it has roots at the poles of X(z) in Ω 1 ∪ Ω 2 . In Ω 0 , we have

B(z) = -L V (z) = -V 1 (Y (z); t) -X(z)V 2 (Y (z); t).
Since |X(z)|, |Y (z)| ≤ 1 in this region, the series converge and there are still no poles. This proves the two conditions (iii) and (iv). Similarly, the conditions (i) and (ii) hold.

Finally we need to show that these conditions uniquely dene the functions B(z), A(z) and the constant F . Suppose that B(z), Â(z) and F is an arbitrary triple satisfying the same conditions. Then it suces to show that A(z) = Â(z) and B(z) = B(z). Then [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] implies that the dierence

∆(z) := A(z) -Â(z) = B(z) -B(z) + F -F, satises ∆(z) = ∆(πτ -γ -z) = ∆(-πτ + γ -z) = ∆(z + π).
Moreover, the four conditions on A(z) and B(z) imply, respectively, that (i) ∆(z) has no poles in

Ω 0 ∪ Ω 1 ∪ Ω 2 , (ii) the poles of X(z) for z ∈ Ω 1 ∪ Ω 2 are roots of ∆(z)+F -F , (iii) ∆(z) has no poles in Ω 0 ∪ Ω -1 ∪ Ω -2 , (iv) the poles of Y (z) for z ∈ Ω -1 ∪ Ω -2 are roots of ∆(z). together with ∆(z) = ∆(πτ -γ -z) = ∆(-πτ + γ -z)
, these imply that ∆(z) is an elliptic function with no poles, so it is constant. Moreover, the fourth condition implies that ∆(z) does have roots, so ∆(z) is the 0 function. The second condition then implies that F = F . Together with the denition of ∆ we have A(z) = Â(z) and B(z) = B(z).

At rst glance it may seem that [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] follows from substituting (x, y) = (X(z), Y (z)) directly into (1), however this ignores the questions of whether the series involved converge and the fact that A(z) and B(z) are dened on non-intersecting domains. So in some sense the intermediate steps are just used to understand which domains should be used to dene A(z) and B(z).

Note that combining [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF], [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane[END_REF] yields

B(2πτ -2γ + z) -B(z) = J(z), (24)
where J(z) is an elliptic function with periods π and πτ given by

J(z) := (X(z -2γ) p -X(z) p ) Y (z) q .
(25)

3. Integral expressions for walks in the three-quadrant cone

In Section 2, we reduced the problem to nding the unique meromorphic functions A, B : C → C ∪ {∞} and constant F characterised by Theorem 2.8 (for each t), as these determine A( 1 y , t) and B( 1x , t) using ( 13) and [START_REF] Dreyfus | Length derivative of the generating series of walks conned in the quarter plane[END_REF], respectively, after which C(x, y; t) is determined by ( 1). An equation analogous to [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] was found by Raschel for walks in the quarter plane [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF], the only dierence being that the transformations z → πτ -γ -z and z → -πτ + γ -z here are z → γ -z and z → -γ -z in the quarter plane. Raschel used this equation to derive an integralexpression solution determining Q(x, y; t) (in the case where the starting point (p, q) = (1, 1)), and the equation has since been used to determine precisely when Q(x, y; t) is dierentially algebraic [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Hardouin | On dierentially algebraic generating series for walks in the quarter plane[END_REF] and to determine when it is algebraic or D-nite with respect to x or y [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF].

Due to this striking similarity we can use these methods to prove the same results for C(x, y; t). In this Section we will derive an explicit integral expression for A(z) and B(z) (see Theorem 3.3). In Section 4, we will discuss the nature of the generating function C(x, y; t) in particular showing that it is algebraic, D-nite or D-algebraic with respect to x (or y) in the same cases as Q(x, y; t).

Another elliptic function

In order to solve the functional equations in Theorem 2.8, we will introduce an explicit elliptic function W (z) with periods π and 2πτ -2γ, as this will be related to B(z) due to [START_REF] Vadim | An analytical method in the theory of two-dimensional positive random walks[END_REF]. We will dene W (z) using the Jacobi theta function ϑ(z, τ ) dened in [START_REF] Bousquet | Walks on the slit plane[END_REF]. Denition 3.1. We dene the function W (z) by

W (z) := ω c ϑ(z -ε, 2τ -2γ π )ϑ(z -πτ + γ + ε, 2τ -2γ π ) ϑ(z -δ, 2τ -2γ π )ϑ(z -πτ + γ + δ, 2τ -2γ π ) , (26)
where ω c is given by

ω c = x c ϑ (0, 2τ -2γ π )ϑ(2δ -πτ + γ, 2τ -2γ π )ϑ(δ -α, τ )ϑ(δ + γ + α, τ ) ϑ(δ -ε, 2τ -2γ π )ϑ(δ -πτ + γ + ε, 2τ -2γ π )ϑ (0, τ )ϑ(2δ + γ, τ )
, unless 2δ + γ ∈ πτ + πZ, in which case the numerator and denominator are both 0 so we dene

ω c = -e iπτ x c ϑ (0, 2τ -2γ π ) 2 ϑ(δ -α, τ )ϑ(δ + γ + α, τ ) ϑ(δ -ε, 2τ -2γ π )ϑ(δ -πτ + γ + ε, 2τ -2γ π )ϑ (0, τ ) 2 .
In the following proposition we show a number of properties of W (z) which will be useful in relating it to A(z), B(z) and F : Proposition 3.2. The function W (z) satises the following properties

(i) W (z) = W (πτ -γ -z) = W (-πτ + γ -z) = W (z + π). (ii) W (z) -1 and Y (z) have exactly the same poles in Ω -2 ∪ Ω -1 . (iii) W (z) and X(z) have exactly the same poles in Ω 1 ∪ Ω 2 . (iv) W (z) -X(z) has no poles in Ω 1 ∪ Ω 2 . (v) the sets W (Ω -2 ∪ Ω -1 ), W (Ω 0 ) and W (Ω 1 ∪ Ω 2 ) are disjoint and their union is C ∪ {∞}.
Proof. Property (i) follows immediately from the quasi-periodicity conditions satised by ϑ (see [START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF]). As a consequence of (i), the function W (z) is elliptic with periods π and 2πτ -2γ. Moreover W (z) has two roots inside each fundamental domain, one coming from each ϑ in the numerator of [START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF]. As a consequence, W (z) takes each value in C ∪ ∞ exactly twice on each fundamental domain. We will now prove (v) as this will be useful for proving (ii)-(iv).

Ω 0 Ω 1 Ω 2 Ω -1 Ω -2 Ω -3 Ω -4 0 π -π -πτ -γ 2 -πτ 2 πτ 2 πτ -γ 2 πτ -γ -Ω 0 F 1 πτ -γ - 1 2 -πτ + γ - 2 2πτ -2γ + 2 Figure 5
. The space F is shaded. This is a fundamental domain of the function

W (z).
Let S denote the strip S = {z ∈ C : 0 ≤ (z) < π}. We claim that the set F dened by

F = Ω -2 ∪ Ω -1 ∪ Ω 0 ∪ Ω 1 ∪ Ω 2 ∪ (πτ -γ -Ω 0 ) F = F ∩ S
is a fundamental domain of W , and the sets involved in the union dening F are disjoint (see Figure 5). Indeed the upper border 1 of Ω 0 is the lower border of Ω 1 ∪ Ω 2 , so πτ -γ -1 is the upper border of Ω 2 and the lower border of πτ -γ -Ω 0 . Hence the sets Ω -2 , Ω -1 , Ω 0 , Ω 1 , Ω 2 and πτ -γ -Ω 0 are disjoint and their union F is a connected strip delimited by the lower border of Ω -2 and the upper border of πτ -γ -Ω 0 . Now let 2 be the lower border of Ω -2 . Then the upper border of Ω -1 , which is also the lower border of Ω 0 is -πτ + γ -2 , so the upper border of πτ -γ -Ω 0 is 2πτ -2γ + 2 . Hence the lower and upper borders of F are 2 and 2πτ -2γ + 2 . Moreover, only the lower border is contained in F. This implies that

C = n∈Z F + (2πτ -2γ)n = n,m∈Z F + (2πτ -2γ)n + πm,
where these unions are in fact disjoint unions. So F is a fundamental domain for W (z), as claimed. Hence, counting with multiplicity, W (z) takes each value in C ∪ ∞ twice on F. Now, since W (z) = W (πτ -γ -z), each value is taken either 0 or 2 times for z ∈ (Ω 1 ∪ Ω 2 )∩S and each value taken by W (z) for z ∈ Ω 0 ∩S is taken the same number of times in πτ -γ-Ω 0 ∩S. Similarly, since W (z) = W (-πτ + γ -z), each value is taken either 0 or 2 times in (Ω -2 ∪ Ω -1 ) ∩ S. This implies that each value in C is either taken twice in (Ω -2 ∪ Ω -1 ) ∩ S, once in Ω 0 ∩ S or twice in (Ω 1 ∪ Ω 2 ) ∩ S, which proves (v).

To prove (ii), it suces to prove that W (z) -1 and Y (z) have the same poles in (Ω -2 ∪ Ω -1 )∩S. Indeed, they share the poles δ and -πτ + γ -δ in this region, and since we know that this region is a subset of a fundamental domain of Y (z) and of W (z), neither of these functions can have any other poles in this region.

The proof of (iii) is similar to the proof of (ii): in this case X(z) and W (z) share the poles ε and πτ -γ -ε in the region

(Ω 1 ∪ Ω 2 ) ∩ S.
Finally to prove (iv) it suces to observe that the poles at ε and πτ -γ -ε cancel in the dierence X(z) -W (z). This is due to the choice of ω c .

Integral expression for general solution

We now give integral expressions analogous to those of Raschel [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF] which determine A(z), B(z) and F exactly: Theorem 3.3. Let z 0 ∈ Ω 0 and let L be a path from z 0 to z 0 + π contained in the closure Ω 0 of Ω 0 . Then A(z), B(z) and F are given by the integrals

B(u) = 1 2πi L X(z) p Y (z) q W (z) W (z) -W (u) dz, for u ∈ Ω 1 ∪ Ω 2 , (27)
A(u) = - 1 2πi L X(z) p Y (z) q W (u) W (z) W (z) W (z) -W (u) dz, for u ∈ Ω -1 ∪ Ω -2 , ( 28
) F = - 1 2πi L X(z) p Y (z) q W (z) W (z) dz. (29)
Proof. We will start by showing that the integrands in the denitions above are all holomorphic in Ω 0 , that is, they contain no poles in this region. A consequence is that the integrals do not depend on the contour L taken from

z 0 to z 0 + π. Since |X(z)|, |Y (z)| ≤ 1 in this region, X(z)
and Y (z) have no poles in this region. Moreover, W (z) has no roots or poles in this region, so the only way that a pole could occur in one of the integrands is if

W (z) = W (u) for some u ∈ Ω -2 ∪ Ω -1 ∪ Ω 1 ∪ Ω 2 and z ∈ Ω 0 ,
but this is impossible by Proposition 3.2, (v). this proves that the integrands are all holomorphic in Ω 0 .

We will now extend the denitions of B and A to denitions that hold in Ω 0 . Let L 1 be the contour which goes in the negative imaginary direction from z 0 until reaching a point c 1 on the boundary of Ω 0 , then travels along the boundary of Ω 0 until reaching c 1 + π then nally travels in the positive imaginary direction until reaching z 0 + π (see Figure 6). Then B can be dened by taking the integral along L 1 . In fact the rst and last sections of the integral cancel with each other, so this can be dened by taking the integral only using the section L1 of L 1 lying between c 1 and c 1 + π. With this denition it is clear that B(u) extends analytically to Ω 0 . In particular, this proves that B(z) satises condition (iii) of Theorem 2.8. Similarly (28) can be dened using the contour L 2 which travels in the positive imaginary direction until reaching a point c 2 on the boundary of Ω 0 , then travels along this boundary to c 2 + π before travelling in the negative imaginary direction to π. In particular, this proves that A(z) satises condition (i) of Theorem 2.8.

We will now show that ( 19)-( 23) hold. In fact, ( 20)-( 23) follow immediately from

W (u) = W (u + π) = W (πτ -γ -u) = W (γ -πτ -u).
To show that (19) holds, rst note that, from the denitions we have

F + A(u) = - 1 2πi L2 X(z) p Y (z) q W (z) W (z) -W (u) dz.
So, dening L 3 as the contour formed by L 1 followed by L 2 reversed, then we have, for u inside this region (and hence inside Ω 0 ),

F + A(u) + B(u) = 1 2πi L3 X(z) p Y (z) q W (z) W (z) -W (u) dz. c 1 + π Ω 0 Ω 1 Ω 2 Ω -1 Ω -2 0 π -π z 0 z 0 + π L L 2 L 1 c 1 c 2 c 2 + π Figure 6. The contours L, L 1 and L 2 from z 0 to z 0 + π.
The only pole of the integrand in the interior of this region occurs at z = u, and the residue at this point is X(u) p Y (u) q , so ( 19) follows from the residue theorem.

We will now show that conditions (ii) and (iv) of theorem 2.8 hold. First, we note that by the denition of W (z), the poles of X(z) in Ω 1 ∪ Ω 2 are exactly the poles of W (z) in this region, while the poles of Y (z) in Ω -1 ∪ Ω -2 are exactly the roots of W (z) in this region. So, condition (iv) follows from the fact that the integrand in ( 27) is 0 when W (u) = ∞, while condition (ii) follows from the fact that the integrand in ( 28) is 0 when W (u) = 0.

We have now shown that F , A(u) and B(u) as dened in ( 29), ( 28) and ( 27) satisfy all of the conditions of Theorem 2.8. This completes the proof that these are indeed the functions F , A(u) and B(u) dened in the previous section.

Nature of series in the three-quadrant cone

In the Section 2, we reduced the problem to nding the unique meromorphic functions A, B : C → C ∪ {∞} and constant F characterised by Theorem 2.8 (for each t). As we discussed, an equation analogous to [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] was found by Raschel for walks in the quarter plane [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF], and this equation has since been used to determine precisely when Q(x, y; t) is dierentially algebraic [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Hardouin | On dierentially algebraic generating series for walks in the quarter plane[END_REF] and to determine in many cases whether it is algebraic or D-nite with respect to x or y [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF].

Due to the similarity between our functional equation ( 19) and the equation widely used in the quarter plane, we can apply methods that have been used on the quarter plane functional equation to our functional equation to determine the nature of C(x, y; t). In particular, in this section we will show C(x, y; t) is algebraic, D-nite or D-algebraic with respect to x (or y) in the same cases as Q(x, y; t). We note that Fayolle and Raschel also showed that for unweighted models, Q(x, y; t) is D-nite with respect to t in the cases where it is D-nite with respect to x [START_REF] Fayolle | On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane[END_REF], however these results relied on the precise ratios πτ γ that could occur in these cases, so they do not apply so readily to our equation. Nonetheless, we expect that the same result holds for

C(x, y; t).

There are two properties of the step-set which determine the complexity of the generating function Q(x, y; t). The rst is the property that the walk model has a nite group -in our context this is equivalent to the ratio γ πτ being a rational number independent of t (see Appendix C). The second is the property that the model decouples, that is under that under the assumption that K(x, y) = 0, we can write x p y q = R 1 (x) + R 2 (y) for some rational functions R 1 and R 2 . Equivalently these are the cases where one can write

X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z))
for some rational functions R 1 and R 2 . The nature of the series C(x, y; t) as determined by these properties is shown in able 2. We make this more precise in the following Theorems which will be proved in this section.

In the following theorems we reference the functions A, B and C, that is, the functions dened by the series at values of t, x, y where they converge absolutely, as described in Lemma 2.4. Importantly, for t ∈ 0, 1

Finite group Innite group Decoupling

P(1,1)
all of these series converge absolutely to functions of x and y dened for x, y in an open, non-empty subset of C, so it makes sense to discuss the nature of these functions.

Theorem 4.1. For xed t ∈ 0, 1

P(1,1) the following are equivalent (i) The function C(x, y; t) is D-nite in x, (ii) The function C(x, y; t) is D-nite in y, (iii) The function B( 1 x ; t) is D-nite in x, (iv) The function A( 1 y ; t) is D-nite in y, (v) B(z)
satises a linear dierential equation whose coecients are elliptic functions with periods π and πτ , (vi) A(z) satises a linear dierential equation whose coecients are elliptic functions with periods π and πτ , (vii) the ratio γ πτ ∈ Q, (viii) the orbit of each point (x, y) ∈ E t under the group of the walk is nite.

We give the proof of some of these equivalences immediately, namely those which are either simple to prove, or follow easily from our general results in Appendix B:

Proof of (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv) ⇐⇒ (v) ⇐⇒ (vi). The equivalences (i) ⇐⇒ (iii) and (ii) ⇐⇒ (iv) follow from [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF]. The equivalences (iii) ⇐⇒ (v) and (iv) ⇐⇒ (vi) follow from Proposition B.8 due to the denitions ( 12) and (13) of A(z) and B(z). Finally (v) ⇐⇒ (vi) due to [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] as X(z) p Y (z) q has πτ as a period.

The proof of this theorem will be completed as follows: we dene the group of the walk in Appendix C, and the equivalence of (vii) and (viii) is shown in Proposition C.2. We show that these equivalent conditions imply the conditions (i)-(vi) in Theorem 4.11, while we show the converse in Theorem 4.13. Theorem 4.2. Assume that t ∈ 0, 1 P(1,1) . The following are equivalent

(i) The function C(x, y; t) is algebraic in x, (ii) The function C(x, y; t) is algebraic in y, (iii) The function B( 1 x ; t) is algebraic in x, (iv) The function A( 1 y ; t) is algebraic in y, (v) B(z)
has mπτ as a period for some positive integer m, (vi) A(z) has mπτ as a period for some positive integer m, (vii) The equivalent conditions of Theorem 4.1 hold and there are rational functions R 1 and R 2 satisfying x p y q = R 1 (x) + R 2 (y) for all (x, y) ∈ E t , (viii) The equivalent conditions of Theorem 4.1 hold and there are rational functions R 1 and

R 2 satisfying X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)) for all z ∈ C, (ix)
The equivalent conditions of Theorem 4.1 hold and the orbit sum of the model is 0 (for (x, y) ∈ E t ). Proof of (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv) ⇐⇒ (v) ⇐⇒ (vi) and (vii) ⇐⇒ (viii). The equivalence (vii) ⇐⇒ (viii) is due to the parameterisation ( 7) of E t . The equivalences (i) ⇐⇒ (iii) and (ii) ⇐⇒ (iv) follow from [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF]. The equivalences (iii) ⇐⇒ (v) and (iv) ⇐⇒ (vi) follow from Proposition B.7 due to the denitions ( 12) and [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF]. Finally (v) ⇐⇒ (vi) due to [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] as X(z) p Y (z) q has mπτ as a period.

To complete the proof of this Theorem, we dene the orbit sum and show that (viii) and (ix) are equivalent conditions in Proposition 4.10. We then show that equivalent conditions (i)-(vi) are equivalent to (vii)-(ix) in Theorem 4.11.

Theorem 4.3. Fix t ∈ 0, 1

P(1,1)
and assume the equivalent conditions of Theorem 4.1 do not hold. The following are equivalent

(i) The function C(x, y; t) is D-algebraic in x, (ii) The function C(x, y; t) is D-algebraic in y, (iii) The function B( 1 x ; t) is D-algebraic in x, (iv) The function A( 1 y ; t) is D-algebraic in y, (v) B(z) is D-algebraic in z, (vi) A(z) is D-algebraic in z, (vii) There are rational functions R 1 and R 2 satisfying x p y q = R 1 (x) + R 2 (y) for all (x, y) ∈ E t , (viii) There are rational functions R 1 and R 2 satisfying X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z))
for all z ∈ C. Proof of (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv) ⇐⇒ (v) ⇐⇒ (vi) and (vii) ⇐⇒ (viii). The equivalence (vii) ⇐⇒ (viii) is due to the parameterisation ( 7) of E t . The equivalences (i) ⇐⇒ (iii) and (ii) ⇐⇒ (iv) follow from (1), the equivalences (iii) ⇐⇒ (v) and (iv) ⇐⇒ (vi) follow from Proposition B.10 due to the denitions ( 12) and [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF]. Finally (v) ⇐⇒ (vi) due to [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] as

X(z) p Y (z) q is D-algebraic in z (see again the proof of Proposition B.10).
We complete the proof of this theorem later in this section, starting with Theorem 4.14 which shows that the equivalent conditions (vii) ⇐⇒ (viii) imply the equivalent conditions (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv) ⇐⇒ (v) ⇐⇒ (vi), then we show the reverse implication in Theorem 4.15.

Although the theorems above describe the nature of C(x, y; t) as a function of x and y for xed t, this implies its nature as a series in R[x, y][[t]] due to the following Lemma: Lemma 4.4. Let G(x, y; t) ∈ R[x, 1

x , y, 1 y ][[t]] be a series which converges for |x|, |y| = 1 and t ∈ 0, 1 P(1,1) . The series G(x, y; t) is algebraic (resp. D-nite, D-algebraic) in x if and only if the function G(x, y; t) of x and y is algebraic (resp. D-nite, D-algebraic) in x for all t ∈ 0, 1 P(1,1) . Proof. Let Λ 1 (x, y, t), Λ 2 (x, y, t), Λ 3 (x, y, t), . . . be an ordering of the set {x j G(x, y; t) k } j,k∈N0 .

Then the function G(x, y; t) is algebraic in x if and only if for each t, there is some integer n > 0 and functions S k (y; t) for 0 ≤ k ≤ n and S(y, t) of y satisfying

n k=0 S k (y; t)Λ k (x, y, t) = S(y, t),
with S n (y; t) = 0. A priori, n depends on t, however, as there are uncountably many possible values of t and only countably many for n, we can chose some n = N for which an equation of the form above holds for uncountably many values of t. For a given value of t, this happens if and only if for every xed x 0 , . . . , x n+1 , the matrix Moreover, for any value of t and y for which all of the series Λ j (x k , y, t) converge absolutely, the series T (y; t) will also converge absolutely to the determinant of these values. Now, Assume that the function G(x, y; t) is algebraic in x for all t. For all suciently small t, and all y satisfying |y| = 1, the series Λ j (x k , y, t) converge absolutely, so there are uncountably many values t such that the series T (y; t) converges to 0 when |y| = 1. But this is only possible if T (y; t) = 0 as a series. Now, since this determinant is 0, an equation of the form

       1 Λ 0 (x 0 , y, t) Λ 1 (x 0 , y, t) • • • Λ n (x 0 , y, t) 1 Λ 0 (x 1 , y, t) Λ 1 (x 1 , y, t) • • • Λ n (x 1 , y, t) 1 Λ 0 (x 2 , y, t) Λ 1 (x 2 , y, t) • • • Λ n (x 2 ,
n k=0 S k (y; t)Λ k (x, y, t) = S(y, t),
must hold with each S k (y; t) and S(y, t) a series in

C[y][[t]], so the series G(x, y; t) is algebraic in x.
For the converse, assume that the series G(x, y; t) is algebraic in x. Then for some n, and any x 0 , . . . , x n+1 ∈ C, the determinant T (y; t) = 0. Hence for each xed t the determinant is still 0, so the function G(x, y; t) is algebraic.

For the property D-nite, the same proof works after changing the denition of Λ 1 (x, y, t), Λ 2 (x, y, t), . . . to be the functions x j ∂ ∂x k G(x, y; t) in some order. Similarly, for the property D-algebraic, we just have to dene Λ k (x, y, t) so that the sequence Λ 0 (x, y, t), Λ 1 (x, y, t), . . . contains each product

x j p i=1 ∂ ∂x ki F(x, y; t) with p ≥ 0 and 0 ≤ k 1 ≤ • • • ≤ k p exactly once.
We now use this lemma to rewrite the theorems above to characterise the complexity of the series

C(x, y; t) ∈ R[x, y][[t]]: Theorem 4.5. The following are equivalent (i) The series C(x, y; t) ∈ R[x, y][[t]] is D-nite in x, (ii) The series C(x, y; t) ∈ R[x, y][[t]] is D-nite in y, (iii)
The equivalent conditions of Theorem 4.1 hold for all t ∈ 0,

; t) ∈ R[x, y][[t]] is D-algebraic in x, (ii) The series C(x, y; t) ∈ R[x, y][[t]] is D-algebraic in y, (iii)
The equivalent conditions of Theorem 4.3 hold for all t ∈ 0, 1 P(1,1) . Proof of Theorems 4.5-4.7. For each of these theorems, the equivalences (i) ⇐⇒ (iii) and

(ii) ⇐⇒ (iii) are both direct results of Lemma 4.4 with F(x, y; t) = C(x, y; t). Finally, the equivalence (iii) ⇐⇒ (iv) in Theorem 4.5 is due to Proposition C.3.

Finite group cases

In this section, we consider the cases in which γ πτ ∈ Q. We will show that this occurs for xed t if and only if C(x, y; t) is D-nite in x. As explained in Appendix C this occurs for all t if and only if the group of the walk is nite. This is an algebraic property of the single-step generating function P(x, y), which was shown to be equivalent to D-niteness for walks in the quarter plane. Hence in this section we are showing that if the generating function Q(x, y; t) is D-nite in x then the generating function C(x, y; t) is also D-nite in x. In the following section we will show that the converse of this statement also holds. Note that by symmetry between x and y, the analogous statements with respect to y also hold. We also show that C(x, y; t) has the more restricted property that it is algebraic in x precisely when X(z) p Y (z) q decouples, which we make precise below. Again this coincides with the nature of Q(x, y; t). Denition 4.8. For xed t, we say that an elliptic function U (z), with periods π and πτ decouples if there is a pair of rational functions R 1 and R 2 satisfying

U (z) = R 1 (X(z)) + R 2 (Y (z)).
We say that the model decouples if X(z) p Y (z) q decouples. It is often alternatively stated that the algebraic cases are those in which the orbit sum is 0, which we make precise in the following denition. Denition 4.9. For xed t satisfying 2γ πτ = M N , for integers M, N > 0, the orbit sum E(z) of an elliptic function U (z), with periods π and πτ , is given by

E(z) := N -1 k=0 U ((2k + 1)γ -z) -U (2kγ + z).
We say that the orbit sum of the model is the orbit sum of X(z) p Y (z) q .

In the following Proposition we show that the orbit sum of a function U (z) is 0 if and only if U (z) decouples. This was proven in an algebraic setting in [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF]Theorem 4.11], where decoupling functions were introduced, and essentially the same proof works here: Proposition 4.10. Let U (z) be an elliptic function with periods π and πτ , and assume that

2γ πτ = M N , with M, N ∈ Z, N > 0. The function U (z) decouples if and only if the orbit sum E(z) of U (z) is equal to 0.
Proof. In the case that U (z) decouples, let U (z) = R 1 (X(z)) + R 2 (Y (z)), where R 1 and R 2 are rational functions. Then we can write the orbit sum as

E(z) = N -1 k=0 R 1 (X((2k + 1)γ -z)) + R 2 (Y ((2k + 1)γ -z)) -R 1 (X(2kγ + z)) -R 2 (Y (2kγ + z)) = N -1 k=0 R 1 (X(-2(k + 1)γ + z)) + R 2 (Y (-2kγ + z)) -R 1 (X(2kγ + z)) -R 2 (Y (2kγ + z)).
Now, the terms R 1 (X(2kγ +z)) in the sum are a permutation of the terms R 1 (X(-2(k+1)γ +z)), because

R 1 (X(2kγ + z)) = R 1 (X(-2(j + 1)γ + z)), when j = N -k -1.
Hence these terms cancel out in the sum. The same holds for the remaining terms in the sum as

R 2 (Y (2kγ + z)) = R 2 (Y (-2jγ + z)) for j = N -k or j = k = 0, so we have E(z) = 0, as required.
We will now prove the converse, that is that if

E(z) = 0 then U (z) decouples. Dene A 1 (z) := N k=1 2k -1 2N (U (2kγ + z) + U ((2k -1)γ -z)) , A 2 (z) := N -1 k=0 - k N (U (2kγ + z) + U ((2k + 1)γ -z)).
The summand U (2kγ + z) + U ((2k -1)γ -z) is xed under the transformation z → -γ -z for any k, so we have

A 1 (-γ -z) = A 1 (z). Similarly we have A 2 (γ -z) = A 2 (z).
So by Proposition B.6, there are rational functions R 1 and

R 2 satisfying A 1 (z) = R 1 (X(z)) and A 2 (z) = R 2 (Y (z)), so it suces to show that if E(z) = 0, then U (z) = A 1 (z) + A 2 (z)
. Indeed this follows from the equation

A 1 (z) + A 2 (z) = U (z + 2N γ) + 1 2N E(z),
which follows directly from the denitions of A 1 , A 2 and E.

Theorem 4.11.

If 2γ πτ = M N ∈ Q, then C(x, y) is D-nite in x.
Moreover, under this assumption C(x, y) is algebraic in x if and only if the orbit sum

E(z) := N -1 j=0 X((2j + 1)γ -z) p Y ((2j + 1)γ -z) q -X(2jγ + z) p Y (2jγ + z) q of X(z) p Y (z) q is equal to 0.
Proof. Assume that 2γ = M N πτ for some positive M, N ∈ Z. Now consider [START_REF] Vadim | An analytical method in the theory of two-dimensional positive random walks[END_REF]:

B 2N -M N πτ + z -B(z) = J(z).
Taking a telescoping sum of N copies of this equation yields

B((2N -M )πτ + z) -B(z) = N -1 j=0 J(2jπτ -2jγ + z),
which we claim is equal to the orbit sum E(z). Indeed, since πτ is a period of J(z), we have

J(2jπτ -2jγ + z) = J(-2jγ + z) = J(2(N -j)γ + z), so the sum rearranges to N -1 j=0 J(2jγ + z),
which is equal to E(z). Hence

B((2N -M )πτ + z) -B(z) = E(z).
(30) We will now consider the cases E(z) = 0 and E(z) = 0 separately. In the case that E(z) = 0, we have

B((2N -M )πτ + z) = B(z).
Hence we have condition (v) of Theorem 4.2, so the equivalent conditions are satised, including that C(x, y) is algebraic in x.

Finally we consider the case E(z) = 0. Then from (30), we have

B((2N -M )πτ + z) E((2N -M )πτ + z) - B(z) E(z) = B((2N -M )πτ + z) E(z) - B(z) E(z) = 1, (31)
so the function

F (z) := ∂ ∂z B(z) E(z) = 1 E(z) 2 (B (z)E(z) -B(z)E (z)) (32) satises F ((2N -M )πτ + z) -F (z) = 0. Hence, B(z) = B 1 X(z)
is weakly X-D-nite (see Denition B.4), so by Proposition B.8, the function B( 1x ) is D-nite in x. Therefore the generating function C(x, y) is also D-nite in x. Finally we show that in this E(z) = 0 case, C(x, y) is not algebraic in x. Suppose the contrary, then condition (v) of Theorem 4.3 holds, that is mπτ is a period of B(z) for some positive integer m. But this is impossible as by [START_REF] Rubey | Transcendence of generating functions of walks on the slit plane[END_REF],

B(m(2N -M )πτ + z) -B(z) E(z) = B(m(2N -M )πτ + z) E(m(2N -M )πτ + z) - B(z) E(z) = m = 0.
Remark: Note that this Theorem holds for any xed t for which γ πτ ∈ Q, which can occur either in the nite group case, where this occurs for all t, or in innite group cases for specic values of t. We require that the above statement hold for all t to say that the function C(x, y; t) is D-nite in x. See Appendix C for a discussion of the group of the walk.

Infinite group cases

In this section we consider the case γ πτ / ∈ Q. the rst part of this section is dedicated to showing that C(x, y; t) is not D-nite in x in these cases, and we will subsequently analyse the D-algebraicity of C(x, y; t). We start with a lemma which essentially proves B( 1x ; t) is not rational in x, as this turns out to be a case which needs to be treated separately. Surprisingly this seems to be the most dicult result of this section, in the sense that it is the only result for which our proof does not apply systematically to walks in an M -quadrant cone for any M . In particular, for walks in the quadrant we have only able to prove the result when t is suciently small (See Lemma 6.16). Lemma 4.12. Assume that γ πτ / ∈ Q. Then B(z) is not a rational function of X(z). Proof. Assume that B(z) is a rational function of X(z). Then for z ∈ Ω -2 , we have z + πτ ∈ Ω 2 , so, by [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF],

B(z + πτ ) = B 1 X(z + πτ ) ; t .
Now since πτ is a period of both X and B, this implies that

B(z) = B 1 X(z) ; t ,
an equation that would normally only hold for z ∈ Ω 0 ∪ Ω 1 ∪ Ω 2 . By (12), we have

A(z) = A 1 Y (z)
; t .

We will show that this is a contradiction as the sum of these cannot be suciently large in absolute value to satisfy [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF].

Recall that by our choice t ∈ (0, 1 P(1,1) ), the series C(x, y; t), B( 1 x ; t) and A( 1 y ; t) all converge when |x|, |y| = 1. In particular, we can substitute x = y = 1 into (1), which yields

(1 -tP(1, 1))C(1, 1; t) = 1 -F(t) -A(1; t) -B(1; t).
Since the left hand side of this equation in positive, we must have

F(t) + A(1; t) + B(1; t) < 1.
It follows that for x, y satisfying |x|, |y| ≥ 1 we have

F(t) + A 1 y ; t + B 1 x ; t < 1.
In particular, for z ∈ Ω -2 , we have

|X(z)|, |Y (z)| ≥ 1, so |F + B(z) + A(z)| = F(t) + B 1 X(z) ; t + A 1 Y (z) ; t < 1.
However this is a contradiction as, by [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF], we have

|F + B(z) + A(z)| = |X(z) p Y (z) q | = |X(z)| p |Y (z)| q , and |X(z)|, |Y (z)| ≥ 1 because z ∈ Ω -2 .
Now we are ready to prove that B( 1 x ; t) is not D-nite in x in the case that γ πτ / ∈ Q. The idea of the proof is that if B( 1x ; t) is D-nite in x, then the poles of B(z) must be well-behaved, as described in Lemma B.9, whereas if γ πτ / ∈ Q, we can prove that its poles are not well behaved in this way. Theorem 4.13. Assume that γ πτ / ∈ Q. Then B( 1x ; t) is not D-nite in x. Proof. Suppose the contrary. Then B( 1

x ; t) is D-nite in x. Moreover, recall that B(z) = B( 1 X(z) ; t) for z ∈ Ω 1 ∪ Ω 2 ,
so by Lemma B.9, the poles z c of B(z) fall into only nitely many classes z c + πZ + πτ Z. Hence B(πτ + z) -B(z) has the same property. Now, from [START_REF] Vadim | An analytical method in the theory of two-dimensional positive random walks[END_REF], we have

B(2πτ -2γ + z) -B(z) = J(z) = J(z + πτ ) = B(3πτ -2γ + z) -B(πτ + z),
and rearranging yields

B(3πτ -2γ + z) -B(2πτ -2γ + z) = B(πτ + z) -B(z).
This implies that B(πτ + z) -B(z) is an elliptic function with periods π and 2πτ -2γ. If this function has a pole z 0 , then for every k ∈ Z, the value zk = z 0 + k(2πτ -2γ) is a pole. This is a contradiction as these points all dene dierent classes z k + πτ Z + πZ, since γ πτ ∈ R \ Q. The only remaining case to consider is when B(πτ + z) -B(z) has no poles, in which case it must be constant:

B(πτ + z) -B(z) = c.
In fact combining this with [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], we see that c = 0, as

c = B(πτ + z) -B(z) = B(-γ -z) -B(πτ -γ -z) = -c.
Hence by Proposition B.6 the function B(z) must be a rational function of X(z) since we have

B(z + πτ ) = B(z) and B(z) = B(-πτ + γ -z) = B(γ -z).
But this contradicts Lemma 4.12. 4.2.1. Decoupling cases. Recall from Denition 4.8 that we say that X(z) p Y (z) q is decoupling if there is a pair of rational functions R 1 and R 2 satisfying

X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)).
As we will show in the following theorem, this implies that C(x, y; t) is D-algebraic in x and y. The analogous result was proven in the quarter plane by Bernardi, Bousquet-Mélou and Raschel [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF], and more precisely they proved that C(x, y; t) is D-algebraic in t under the same condition. This results from the fact that all of the parameters that depend on t and all of the functions involved in the solution depend on t in a D-algebraic way. We believe that the same argument applies here, although a rigorous proof of this is outside the scope of this article. Theorem 4.14. Assume that

X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z))
holds for some rational functions R 1 and R 2 . Then C(x, y; t) is D-algebraic in x and y.

Proof. Under the assumption, ( 19) can be written as

T (z) := R 1 (X(z)) -B(z) = A(z) + C(t) -R 2 (Y (z)), ( 33
) which implies that T (z) satises T (z) = T (πτ -γ -z) = T (-πτ + γ -z) = T (z + π).
Combining these shows that T (z) is an elliptic function with periods π and 2πτ -2γ. This means T (z) is an elliptic function with the same periods so it is related to T (z) by some non-trivial algebraic equation, implying that T (z) is a D-algebraic function of z. Indeed, any elliptic functions are D-algebraic for this reason. Now, since X(z) is also D-algebraic, it follows from (33) that B(z) is also D-algebraic in z. This is precisely condition (v) of Theorem 4.3, which we showed to be equivalent to conditions (i) and (ii), that C(x, y; t) is D-algebraic in x and y.

Remark: Using (33) it can be proven that T (z) is a rational function of W (z) (see Denition 3.1) using the same idea as Proposition B.6. 4.2.2. Non-decoupling cases. In this section we show that if there is no decoupling function, then the generating function is not D-algebraic in x. The proof works along the same lines as [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Hardouin | On dierentially algebraic generating series for walks in the quarter plane[END_REF] for the quarter plane case, which relies on Galois theory of q-dierence equations. Rather than essentially rewriting these entire proofs, in Appendix D we use results from [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF] to deduce Corollary D.2, which avoids Galois theory language in its statement, and can be readily applied to show the main result of this section. For the following theorem, recall that for xed t ∈ 0, 1 P (1,1) , the series C(x, y; t) converges for |x|, |y| ≤ 1, so we can consider it to be a function of x and y.

Theorem 4.15. Fix t ∈ 0, 1 P (1,1) . Assume that there are no rational functions

R 1 , R 2 ∈ C(x) satisfying X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)).
Then the function C(x, y; t) is not D-algebraic in x or y.

Proof. It suces to prove that B(z) is not D-algebraic, as we showed below the statement of Theorem 4.3 that this is equivalent to C(x, y; t) being D-algebraic in x or y. Assume for the sake of contradiction that condition that B(z) is D-algebraic in z. We will show that this implies that there are rational functions R 1 and R 2 satisfying the equation in the theorem.

By Theorem 2.8, the functions h(z) := X(z) p Y (z) q , f 1 (z) := A(z) + F and f 2 (z) := B(z) satisfy the conditions of Corollary D.2, with γ 1 = -πτ + γ and γ 2 = πτ -γ. Hence, there are meromorphic functions a 1 , a 2 :

C → C ∪ {∞} satisfying X(z) p Y (z) q = a 1 (z) + a 2 (z), a 1 (z) = a 1 (z + π) = a 1 (z + πτ ) = a 1 (-πτ + γ -z) = a 1 (γ -z), a 2 (z) = a 2 (z + π) = a 2 (z + πτ ) = a 2 (-γ -z) = a 2 (πτ -γ -z).
Finally, by Proposition B.6, this implies that a 1 (z) is a rational function of Y (z), while a 2 (z) is a rational function of X(z). Hence we can write

X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)),
as required.

Walks starting on an axis

We will now discuss a question suggested by Kilian Raschel where the walk starts at some point (p, 0) for p > 0 (or equivalently (0, q)) rather than the traditional starting point [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF][START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF]. Trotignon and Raschel conjectured that with this starting point all nite group models admit algebraic generating functions [START_REF] Raschel | On walks avoiding a quadrant[END_REF]. This follows immediately from Theorem 4.2 as these cases decouple for any step set (by setting R 1 (x) = x p and R 2 (y) = 0). Moreover, using Theorem 4.3, the same argument proves that for any step set S, the walks starting at such a point have a generating function which is dierentially algebraic in x. In this section we go further than these results by nding an explicit, general formula for the counting function of walks starting at a point (p, 0). This formula will use the function W (z) dened in Denition 3.1. Theorem 4.16. For p ≥ 1, let A p , B p and F p denote the functions A, B and F arising in the case that the starting point of the walks is (p, 0). Then for each p, there is a degree p polynomial H p satisfying

A p (z) = H p (W (z)) -H p (0), (34)
F p (t) = H p (0), ( 35
) B p (z) = X(z) p -H p (W (z)). (36)
Moreover, H p is uniquely determined by the fact that the right hand side of (36) has a root at z = δ. Furthermore, the leading coecient of H p is 1.

Proof. We will start by proving that the polynomial H is uniquely dened by the fact that the right hand side of (36) has a root at z = δ. In the case that δ = πτ -γ -δ, both X(z) and W (z) have a simple pole at z = δ. Taking a series expansion X(z) p -H p (W (z)) = g p (x -δ) -p + g p-1 (x -δ) -p+1 + • • • + g 0 + O(x -δ), around z = δ, for an arbitrary polynomial H, the polynomial

H p (w) = h p w p + h p-1 w p-1 + • • • + h 1 w + h 0
is uniquely dened by the fact that g p = g p-1 = • • • = g 0 = 0, as h p is determined by the fact that g p = 0, then h p-1 is determined by the fact that g p-1 = 0 as so on until h 0 is determined by the fact that g 0 = 0. Moreover, by these denitions, the expression X(z) p -H p (W (z)) does indeed have a root at z = δ. We also note that h p = 1 as X(z) -W (z) does not have a pole at z = δ, so setting h p = 1 causes g p = 0. In the remaining case, where δ = πτ -γ -δ, both X(z) and W (z) have a double pole at z = δ and are xed under the transformation z → 2δ -z = πτ -γ -z. In this case we can write

X(z) p -H p (W (z)) = g p (x -δ) -2p + g p-1 (x -δ) -2p+2 + • • • + g 0 + O((x -δ) 2 ),
then as in the previous case each h j , starting with j = p, is determined by the fact that g j = 0. Now we have determined the unique polynomial H such that the right hand side of (36) has a root at z = δ. We will now show that the functions A p (z), F p and B p (z) thus dened are the unique functions satisfying the conditions of Theorem 2.8. For the equations, ( 19) holds as it is the sum of (34), ( 35) and (36) (since q = 0 in this case), ( 20) and ( 22) hold because W (z) and X(z) are also xed by these transformations while ( 21) and ( 23) hold because W (z) is xed by these transformations. For (iii) and (iv): poles of B p (z) could only occur at poles of either X(z) or W (z), and the only poles of these functions in the region Ω 0 ∪ Ω 1 ∪ Ω 2 are δ and -πτ + γ -δ. But we know that δ is a root of B p , and since B p (z) = πτ -γ -z, this means that πτ -γ -δ is also a root of B p . So (iii) and (iv) hold as B p (z) has no poles in Ω 0 ∪ Ω 1 ∪ Ω 2 , and it has roots at the poles of X(z) in this region. Finally (i) holds because W (z) has no poles in Ω 0 ∪ Ω -1 ∪ Ω -2 , moreover, (ii) holds because the poles of Y (z) in Ω -1 ∪ Ω -2 are roots of W (z), and when W (z) = 0, we clearly have A p (z) = 0. this completes the proof that the functions B p and A p determined by this theorem are the unique functions characterised by Theorem 2.8.

For p ≥ 1, let A p ( 1 y ; t), B p ( 1 x ; t) and F p (t) denote the series A( 1 y ; t), B( 1x ; t) and F(t) arising in the case that the starting point is (p, 0). We can convert the formulae for A p and B p above to formulae for A p , B p using series dened by the following lemma: Lemma 4.17. There are unique series

W B 1 x ; t ∈ xR[ 1 x ][[t]] and W A 1 y ; t ∈ 1 y R[ 1 y ][[t]] sat- isfying W B 1 X(z) ; t = W (z) for z ∈ Ω 1 ∪ Ω 2 and W A 1 Y (z) ; t = W(z) for z ∈ Ω -1 ∪ Ω -2 .
Moreover, these series are related to A 1 and B 1 by

W A 1 y ; t = A 1 1 y ; t and W B 1 x ; t = x -F 1 (t) -B 1 1 x ; t .
Proof. We dene the series W B and W A by the equations

W A 1 y ; t = A 1 y ; t W B 1 x ; t = x -F 1 (t) -B 1 1 x ; t ,
and we will prove that these are related to W (z) as described. The reason for dening them in this way is that it is now clear from the denition that W B 1

x ; t ∈ xR[ 1 x ][[t]] and W A 1 y ; t ∈ 1 y R[ 1 y ][[t]]. For xed t and z ∈ Ω 1 ∪ Ω 2 , dene W 1 (z) = W B 1 X(z) ; t and for z ∈ Ω -1 ∪ Ω -2 , dene W 2 (z) = W A 1 Y (z) ; t .
Then from the denitions of W B and W A , we have

W 1 (z) = X(z) -F 1 -B 1 (z) W 2 (z) = A 1 (z).
Combining this with Theorem 4.16, expanding the functions of

H 1 using H 1 (w) = w + h 0 yields W 1 (z) = W (z), for z ∈ Ω 1 ∪ Ω 2 , W 2 (z) = W (z), for z ∈ Ω -1 ∪ Ω -2 .
Finally the fact that the series W B and W A are unique is clear, as it would be impossible for two dierent series applied to X(z) or Y (z) in the same region to have the same result.

We can now rewrite Theorem 4.16 as the following theorem:

Theorem 4.18. For each p ≥ 1, then there is a degree p polynomial H p (with coecients depending on t) satisfying

A p 1 y = H p W A 1 y ; t -H p (0), (37)
F(t) = H p (0), (38)
B p 1 x = x p -H p W B 1 x ; t . (39)
Moreover, this polynomial is uniquely determined by the fact that the right hand side of (39) is a series in

1 x R[ 1 x ][[t]].
Proof. We dene H p to be the polynomial from Theorem 4.16. Substituting y → Y (z) for z ∈ Ω -1 ∪Ω -2 into (37) yields (34), so we know that (37) holds for y = Y (z) where z ∈ Ω -1 ∪Ω -2 . This region includes poles of Y (z), so (34) holds for 1/y in a neighbourhood of 0, therefore it must hold as an equation of formal series of 1 y for any xed t ∈ 0, 1 P(1,1) , and hence it holds as an equation of series of t and 1 y , as required. Similarly, substituting x → X(z) for z ∈ Ω 1 ∪ Ω 2 into (39) yields (36), so we know that (39) holds.

Finally the fact that the right hand side of (39) lies in

1 x R[ 1 x ][[t]
] is equivalent to the fact that the right hand side of (36) has a root at δ, so it uniquely denes the polynomial H p . Theorem 4.18 is a purely combinatorial statement, yet our proof used analytic analysis of elliptic functions.It would be nice to understand why this Theorem is true from a purely combinatorial perspective. Indeed the following corollary is even more striking in its simplicity, given that we have no purely combinatorial proof. Corollary 4.19. Fix a (weighted) step-set S. Amongst the (weighted) walks w from (2, 0) to (-1, 0) of length n using steps in S which only touch the set D = {(x, 0) : x ≤ 0}∪{(0, y) : y ≤ 0} at their end-point, exactly half touch the ray T = {(1, y) : y ≤ 0}.

Proof. The walks from (2, 0) which only touch D at their end-point are exactly the walks counted by

B 2 1 x ; t + A 2 1 y ; t + F 2 (t),
so the walks from (2, 0) to (-1, 0) are counted by [x -1 ]B 2 1 x ; t . For the walks from (2, 0) to (-1, 0) which do not touch T , shifting these walks to the left one space yields exactly the walks from (1, 0) to (-2, 0), that is the walks counted by [x -2 ]B 1 1

x ; t . So it suces to prove that

[x -1 ]B 2 1 x ; t = 2[x -2 ]B 1 1 x ; t .
(2, 0)

(-1, 0) (2, 0) (-1, 0) Figure 7.
Two paths from (2, 0) to (-1, 0) using the same steps in a dierent order and only visiting (-1, 0) at their end-point. By corollary 4.19, exactly half of all such paths pass through a blue triangle.

From Theorem 4.18 and Lemma 4.17, we have

B 2 1 x = x 2 -H 2 x -F(t) -B 1 1 x ; t , (40)
Where H 2 is the unique polynomial of degree 2, with coecients depending on t, such that the right hand side is a series in

1 x R[ 1 x ][[t]
]. This is precisely the polynomial

H 2 (w) = (w + F(t)) 2 + 2[x -1 ]B 1 1 x ; t , so (40)
becomes

B 2 1 x = 2xB 1 1 x ; t -x 0 2xB 1 1 x ; t -B 1 1 x ; t 2 .
Taking the coecient of [x -1 ] on both sides of this equation yields the desired result.

We also give a Second corollary which is perhaps a more explicit version of Theorem 4.16:

Corollary 4.20. Let I(w; t)

∈ w + Z 1 w [[t]] be the inverse of W B ( 1
x ; t) = x -F(t) -B 1 ( 1 x ; t) in the sense that I W B 1 x ; t ; t = x. (41)
Then We will show that The series A p , B p and F p as dened above along with H p satisfy the conditions of Theorem 4.18, and therefore are the series dened previously. Since I(w; t)

B p 1 x ; t = [w <0 ]I(w; t) p w=W1( 1 x ;t) A p 1 y ; t = [w >0 ]I(w; t) p w=W A ( 1 y ;t) F p (t) = [w 0 ]I(w; t) p and I(W (z)) = X(z) for z ∼ δ.

Proof. Dene

∈ w + Z 1 w [[t]],
we have I(w; t) p ∈ w p +w p-1 Z This implies that H p is the unique polynomial dened by Theorem 4.18 such that

x p -H p W B 1 x ; t ∈ 1 x Z 1 x [[t]],
Which implies that A p , B p and F p are the desired series as well.

Finally, for t xed, if z ∈ Ω 1 ∪ Ω 2 and 1 W (z) is within the radius of convergence of I(w; t) as a function of 1 w , then we can substitute x → X(z) into (41) yielding I(W (z)) = X(z). In particular, this will happen in a neighbourhood of δ as δ ∈ Ω 1 ∪ Ω 2 and δ is a pole of W (z) (see denition 3.1).

4.4.

Forbidding the steps between (0, 1) and [START_REF] Ilyich | Elements of the theory of elliptic functions[END_REF]0) In this section we prove that in most cases the nature of the generating function C(x, y; t) does not change if we forbid either or both of the steps between (0, 1) and (1, 0). To see this, let L(x, y; t) be the generating function counting walks starting at the same point (p, q), but for which it is forbidden to step directly from (0, 1) to (1, 0). Let M(x, y; t) be the generating function for walks which are forbidden to step in either direction between (1, 0) and (0, 1). We will show that C(x, y; t), L(x, y; t) and M(x, y; t) have the same nature as functions of x, except possibly in the case that C(x, y; t) is D-algebraic but not D-nite, where we do not rule out the possibility that either or both of L(x, y; t) and M(x, y; t) are D-nite. Proposition 4.21. Let C(x, y; t) count walks with the same step-set starting at (1, 0), let C 1 (t) denote the generating function counting walks ending at (0, 1) and let C1 (t) walks starting at (1, 0) and ending at (0, 1). Let L 1 (t), L(x, y; t) and L1 (t) denote the analogous series counting walks where the step from (0, 1) to (1, 0) is forbidden. Then these are related by L(x, y; t) = C(x, y; t) -ω (1,-1) tL 1 (t) C(x, y; t).

(42) Proof. Consider the walks counted by C(x, y; t) -L(x, y; t), that is, walks that do use the step from (0, 1) to (1, 0) at least once. The section prior to the rst of these steps is any walk counted by L 1 (t), as it must end at (0, 1) and must not use the step from (0, 1) to (1, 0). The step itself contributes the weight ω (1,-1) t, then the rest of the walk can be any walk starting at (1, 0), which are counted by C(x, y; t). Hence, we have

C(x, y; t) -L(x, y; t) = ω (1,-1) tL 1 (t) C(x, y; t).
Rearranging this yields the desired equation. Then using the same argument starting with L(x, y; t) and forbidding the step from (1, 0) to (0, 1), we can prove that M(x, y; t) is D-algebraic if and only if L(x, y; t) is D-algebraic.

Walks in an M -quadrant cone

In this section we consider the enumeration of walks in more general cones formed by gluing together quarters of the plane along their boundaries. The quadrants Q 0 and Q0 are dened by:

Q 0 = {(i, j) : i, j > 0}, Q0 = {(i, j) : i > 0; j ≥ 0}.
To dene the rest of the quadrants that we will glue together, we consider the function r : Z 2 → Z 2 , which rotates the plane by π/2 anticlockwise, that is r((a, b)) = (-b, a). This allows us to dene quadrants Q s and Qs for all other s ∈ Z recursively using the equations:

Q s+1 = r(Q s ) and Qs+1 = r( Qs ) for s ∈ Z. So Q s+4 = Q s and Qs+4 = Qs .
The 3-quadrant cone considered in the previous section is simply the union of three quadrants Q -1 , Q0 and Q1 . For M = 1, M = 2 and M = 4, an M -quadrant cone can be similarly dened as a union of M of these quadrants, a 4-quadrant cone being alternatively called the slit plane (see Figure 8).

Z 2 \ {(n, 0) : n ∈ Z, n ≤ 0}.
For M > 4, we have to be more careful in our denition, as the quadrants are not, a-priori, disjoint. To dene an M -quadrant cone, we start by dening the spiral quadrants

Γ s = {(s, z) : z ∈ Q s } ⊂ Γs = {(s, z) : z ∈ Qs }.
Γs is then isomorphic to Qs , but, importantly, it is disjoint from Γr for r = s. Now, rather than considering walks in the whole plane (restricted to some subspace), we will consider walks in the spiral space Π := ∪ s∈Z Γs . Recall that walks in the plane are permitted to have steps coming from some xed step-set S. In the spiral space Π, a step is allowed from

π 1 = (s 1 , (a 1 , b 1 )) to π 2 = (s 2 , (a 2 , b 2 )) if and only if (a 2 -a 1 , b 2 -b 1 ) ∈ S and |s 1 -s 2 | ≤ 1.
In Lemma 5.2, we will show that these naturally correspond to walks in Z 2 \ {(0, 0)} by projecting each point (s, (a, b)) onto (a, b). The additional value s keeps track of what is called the winding angle of the walk around (0, 0).

Q0

Q-1 Q1 Q -2 Figure 8. The slit plane Z 2 \ {(n, 0) : n ∈ Z, n ≤ 0} = Q1 ∪ Q0 ∪ Q-1 ∪ Q -2 .
Lemma 5.1. Assume p is adjacent to a point p ∈ Qs . Then p lies in exactly one of the sets Qs-1 , Qs , Qs+1 and {(0, 0)}.

Proof. Applying the transformation r -s yields a point r -s (p ) adjacent to r -s (p) ∈ Q0 , and it suces to show that r -s (p ) lies in exactly one of the sets Q-1 = {(i, j) : i ≥ 0 > j}, Q0 = {(i, j) : i > 0; j ≥ 0}, Q1 = {(i, j) : i ≤ 0 < j} and {(0, 0)}. These sets are disjoint, so r -s (p ) cannot lie in more than one of these sets. Indeed, the points adjacent to Q0 which lie outside Q0 are on the ray {(i, -1) : i ≥ 0}, which lies in Q-1 or the ray {(0, j) : j ≥ 0} of which all but the point (0, 0) lies in Q1 . Lemma 5.2. If p ∈ Qs ⊂ Z 2 , then there is a bijection between walks in Z 2 \ {(0, 0)} starting at p and walks in the spiral space Π starting at (s, p) with the same sequence of steps. Proof. for any walk (s 0 , p 0 ), (s 1 , p 1 ), . . . , (s n , p n ) in Π, with (s 0 , p 0 ) = (s, p) there is a corresponding walk p 0 , p 1 , . . . , p n in Z 2 \{(0, 0)} using the same step set S. To show that this correspondence forms a bijection, it suces to show that there is exactly one choice of the letters s j for any walk p 0 , p 1 , . . . , p n with s 0 = s xed. We will show this inductively. Assume that there is a unique choice of s k and consider the possible values of s k+1 . Since s k has been chosen, we must have (s k , p k ) ∈ Π, that is p k ∈ Qs k . Since p k+1 is adjacent to p k and p k+1 = (0, 0), from Lemma 5.1, we must have p k+1 ∈ Qs k -1 or p k+1 ∈ Qs k or p k+1 ∈ Qs k +1 , and p k+1 can only be in one of these sets as they are disjoint. Since s k+1 must satisfy |s k+1 -s k | ≤ 1, this implies that there is a unique choice of s k+1 satisfying p k+1 ∈ Qs k+1 . This completes the induction. Denition 5.3. An M -quadrant cone is a subspace Π L,K of Π dened by

Π L,K = Γ -L ∪ Γ-L+1 ∪ Γ-L+2 ∪ • • • ∪ ΓK , where 0 ≤ L, K and L + K + 1 = M .
Note that simultaneously decreasing L by 1 and increasing K by 1 simply rotates the cone anticlockwise, so all M -quadrant cones are congruent. Hence, we could consider all possible walks in an M -quadrant cone while xing L = 0. We will not do this, however, as it is more convenient to allow any value of L, but insist that the starting point of the walk is in Γ0 .

In subsection 5.1, we dene generating function Q j (x, y; t) counting walks in the M -quadrant cone Π L,M , and we derive functional equations characterising these series, then in subsection 5.2 we use these to determine an analytic functional equation, generalising Theorem 2.8. Finally in Section 6, we use this analytic functional equation to determine the complexity of the generating functions Q j (x, y; t). In a forthcoming paper we will consider walks in the complete spiral space Π and walks restricted to the half spiral space Π L = Γ -L ∪ s>-L Γs .

Functional equations for walks in an M -quadrant cone

In this section we consider walks restricted to the M -quadrant cone Π L,M starting at some point (0, (p, q)) ∈ Γ0 using (weighted) steps in S.

We will now dene the generating functions that we use to count these walks. We dene generating functions Q s (x, y; t) for -L ≤ s ≤ K as follows: Let q s (i, j; n) be the weighted number of walks of length n starting at (0, (p, q)) and ending at the point (s, (i, j)). We dene the generating function Q s (x, y; t) by

Q s (x, y; t) := n≥0 i,j∈Z q s (i, j; n)x i y j t n .
Note that for j ∈ Z we have

• Q 4j (x, y; t) ∈ xR[x, y][[t]] • Q 4j+1 (x, y; t) ∈ yR[ 1 x , y][[t]] • Q 4j+2 (x, y; t) ∈ 1 x R[ 1 x , 1 y ][[t]] • Q 4j+3 (x, y; t) ∈ 1 y R[x, 1 y ][[t]]
We can write this more concisely by dening x s and y s to be rotated versions of x and y for each s. precisely, for k ∈ Z, we dene

x 4k = y 4k-1 = x x 4k+1 = y 4k = y x 4k+2 = y 4k+1 = 1 x x 4k+3 = y 4k+2 = 1 y .
Using these variables, we have

Q j (x, y; t) ∈ x j R[x j , y j ][[t]].
Moreover, since walks counted by Q -L (x, y; t) nish in Γ -L , we must have

Q -L (x, y; t) ∈ x -L y -L R[x -L , y -L ][[t]].
We will now derive a system of functional equations characterising the series Q s (x, y; t). In order to write these functional equations we dene, for -L ≤ i, j ≤ K, the series S i,j (x, y; t) to be the generating function for walks in the spiral plane Π, whose last step is from Γi to Γj . So S i,j = 0 unless |i -j| ≤ 1. Furthermore, for -L ≤ j ≤ K, we dene T j (x, y; t) to be the generating function for walks which do not end in Π L,M , but for which the removal of the nal step yields a walk in Π L,M ending in Γj . In the following two lemmas we describe spaces in which the series S i,j (x, y; t) and T j (x, y; t) lie Lemma 5.4. The series S i,j (x, y; t) lie in

• S j,j+1 (x, y; t) ∈ y j R[y j ][[t]] • S j+1,j (x, y; t) ∈ x j R[y j ][[t]]
Proof. Let w be a walk counted by S j,j+1 (x, y; t) and let w be the same walk with the nal step removed. Then w is also counted by

Q j+1 (x, y; t) ∈ x j+1 R[x j+1 , y j+1 ][[t]] = y j R y j , 1 xj [[t]],
while w is counted by

Q j (x, y; t) ∈ x j R[x j , y j ][[t]].
Since the contributions from w and w can only dier by a factor of x α y β t, where -1 ≤ α, β ≤ 1, the contribution from w must lie in y j R[y j ][[t]], so the sum S j,j+1 (x, y; t) of the contributions from all such walks also lies in

y j R[y j ][[t]].
Similarly, if we let w be a walk counted by S j,j+1 (x, y; t) and let w be the same walk with the nal step removed, we can deduce that w and w are in the same sets as in the previous case. This implies that the contribution from w lies in x j R[y j ][[t]], so the sum S j+1,j (x, y; t) of the contributions from all such walks also lies in

x j R[y j ][[t]].
Lemma 5.5. The series T j (x, y; t) lie in

• T 0 (x, y; t) ∈ R[x][[t]] + R[y][[t]], if M = 1, • T -L (x, y; t) ∈ R[x -L ][[t]], if M ≥ 2, • T 1-L (x, y; t) ∈ y -1 1-L R[y 1-L ][[t]], if M = 2, • T 1-L (x, y; t) ∈ y -1 1-L R[[t]] + R[[t]], if M ≥ 3, • T K (x, y; t) ∈ R[y K ][[t]], if M ≥ 3, • T j (x, y; t) ∈ R[[t]], for 1 -L < j < K.
Proof. Let w be a walk counted by T j (x, y; t) and let w be the same walk with the nal step removed. Let ux a j y b j t n be the contribution from w, where u is the weight of the walk (i.e., the product of the weights of the steps). then ŵ := r -j (w) ends at (a, b) while the walk ŵ := r -j (w ) ends at some point (a -α, b -β), where α, β ∈ {-1, 0, 1}. Moreover, the endpoint (a -α, b -β) of ŵ lies in r -j ( Qj ) = Q0 , and more precisely in r L (Q -L ) = Q 0 in the case that j = -L. We will now separately consider the six cases in the statement of this lemma, and show that in each case the contribution ux a j y b j t n to T j (x, y; t) from w lies in the claimed ring. This implies the desired result as T j (x, y; t) is a sum of these contributions over all possible w, and there are only nitely many terms in this sum for each length n.

Case 1: M = 1.

In this case we necessarily have

j = L = 0. Hence (a -α, b -β) ∈ Q 0 = {(k, ) : k, > 1}, but (a, b) / ∈ Q 0 .
This is only possible if either a = 0 and b ≥ 0 or b = 0 and a ≥ 0. Hence the contribution ux a j y b j t n = x a y b t n to T 0 (x, y; t) from w lies in R

[x][[t]] + R[y][[t]].
Case 2: M ≥ 2 and j = -L.

In this case

(a-α, b-β) ∈ Q 0 = {(k, ) : k, > 1}, but (a, b) / ∈ Q 0 and (a, b) / ∈ r -j ( Q1-L ) = Q1
. As in the last case a = 0 and b > 0 or b = 0 and a ≥ 0, except that the case a = 0 and b > 0 does not occur because then (a, b) would lie in Q1 . Hence the only possibility is that b = 0 and a ≥ 0, so the contribution ux a

-L y b -L t n to T -L (x, y; t) from w lies in R[x -L ][[t]].
Case 3: M = 2 and j = K = 1 -L.

In this case

(a -α, b -β) ∈ Q0 = {(k, ) : k > 1; ≥ 0}, but (a, b) / ∈ Q0 and (a, b) / ∈ r -j (Q -L ) = Q -1 . The union Q0 ∪ Q -1 = {(i, j) : i > 1}
, so for (a, b) to be adjacent to this set but not in this set, we must have a = 0. Moreover, since (a -α, b -β) ∈ Q0 , we must have b ≥ -1. Hence, the contribution ux a

1-L y b 1-L t n to T 1-L (x, y; t) from w lies in y -1 1-L R[y 1-L ][[t]].
Case 4: M ≥ 3 and j = 1 -L.

In this case

(a -α, b -β) ∈ Q0 = {(k, ) : k > 1; ≥ 0}, but (a, b) / ∈ Q0 and (a, b) / ∈ r -j (Q -L ) = Q -1 and (a, b) / ∈ r -j ( Q2-L ) = Q1
. The only points adjacent to Q0 which do not lie in Q1 or Q -1 are (0, 0) and (0, -1), so (a, b) is one of these points. Hence, the contribution ux a

1-L y b 1-L t n to T 1-L (x, y; t) from w lies in y -1 1-L R[[t]] + R[[t]].
Case 5: M ≥ 3 and j = K.

In this case

(a-α, b-β) ∈ Q0 = {(k, ) : k > 1; ≥ 0}, but (a, b) / ∈ Q0 and (a, b) / ∈ r -j ( QK-1 ) = Q-1 .
The only points adjacent to Q0 which do not lie in Q-1 are the points (0, b) for b ≥ 0.

Hence, the contribution

ux a K y b K t n to T K (x, y; t) from w lies in R[y K ][[t]].
Case 6: 1 -L < j < K.

In this case

(a -α, b -β) ∈ Q0 = {(k, ) : k > 1; ≥ 0}, but (a, b) / ∈ Q0 and (a, b) / ∈ r -j ( Qj-1 ) = Q-1 and (a, b) / ∈ r -j ( Qj+1 ) = Q1
. The only point adjacent to Q0 which does not lie in any of these sets is the point (0, 0). Hence, the contribution ux a j y b j t n to T j (x, y; t) from w lies in R

[[t]]. have U 0 (x -L ; t) ∈ x -L R[x -L ][[t]], U 1 (t) ∈ R[[t]] and U 2 (y K ; t) ∈ y K R[y K ][[t]],
hence from the denitions (47) and (48), we have

A(x -L ; t) ∈ R[x -L ][[t]] and B(y K ; t) ∈ y K R[y K ][[t]].

Analytic reformulation of functional equations

As in the 3/4-plane case, we x t < 1/|S|, substitute x = X(z), y = Y (z) and rewrite the equations in terms of z.

Moreover, analogously to our denitions of x j and y j , we dene X j (z) and Y j (z) to be the functions such that (x, y) = (X(z), Y (z)) if and only if (x j , y j ) = (X j (z), Y j (z)). That is

X 4k (z) = Y 4k-1 (z) = X(z) X 4k+1 (z) = Y 4k (z) = Y (z) X 4k+2 (z) = Y 4k+1 (z) = 1 X(z) X 4k+3 (z) = Y 4k+2 (z) = 1 Y (z)
.

Furthermore, we dene similarly shifted versions of γ and the roots α and β of X(z) and Y (z):

Denition 5.8. For k ∈ Z, dene β 4k = β + kπτ , β 4k+1 = δ + kπτ , β 4k-1 = α + kπτ and β 4k-2 = ε+kπτ . Moreover, dene γ 2k = γ +kπτ and γ 2k-1 = -γ +kπτ , and dened

α k = β k-1 .
The reason for these denitions is so that the following simple Proposition holds for all j.

Proposition 5.9. The functions X j (z), Y j (z), the spaces Ω j and the constants α j , β j , γ j satisfy the following properties (i

) |Y j (z)| ≤ 1 for z ∈ Ω j ∪ Ω j+1 , (ii) |X j (z)| ≤ 1 for z ∈ Ω j ∪ Ω j-1 , (iii) Y j (γ j -z) = Y j (z), (iv) γ j -Ω j ∪ Ω j+1 = Ω j ∪ Ω j+1 , (
v) β j and γ j -β j are the roots of Y j in Ω j ∪ Ω j+1 , (vi) α j and γ j-1 -α j are the roots of X j in Ω j ∪ Ω j-1 .

Proof. Since X j = Y j-1 and α j = β j-1 , Conditions (i) and (ii) are equivalent, while Conditions (v) and (vi) are also equivalent, so it suces to prove (i), (iii), (iv) and (v). First, (i) and (iv) follow from Lemma 2.5. For j even, (iii) follows from

Y (z) = Y (z + πτ ) = Y (γ -z) = Y (γ j -z),
while for j odd it follows from

X(z) = X(z + πτ ) = X(-γ -z) = X(γ j -z).
Finally from Proposition 2.6, we have

• α, -γ -α ∈ Ω 0 ∪ Ω -1 are roots of X(z), so β 4k-1 , γ 4k-1 -β 4k-1 ∈ Ω 4k-1 ∪ Ω 4k are roots of Y 4k-1 (z) = X(z), • β, γ -β ∈ Ω 0 ∪ Ω 1 are roots of Y (z), so β 4k , γ 4k -β 4k ∈ Ω 4k ∪ Ω 4k+1 are roots of Y 4k (z) = Y (z), • δ, πτ -γ -δ ∈ Ω 1 ∪ Ω 2 are poles of X(z), so β 4k+1 , γ 4k+1 -β 4k+1 ∈ Ω 4k+1 ∪ Ω 4k+2 are roots of Y 4k+1 (z) = 1 X(z) , • ε, γ -πτ -ε ∈ Ω -2 ∪ Ω -1 are poles of Y (z), so β 4k-2 , γ 4k-2 -β 4k-2 ∈ Ω 4k-2 ∪ Ω 4k-1 are roots of Y 4k-2 (z) = 1 Y (z) .
Proof. We start by dening A(z) at all points z ∈ Ω j for -L < j ≤ K + 1.

A(z) := V j (z) + j k=-L (δ k,0 X(z) p Y (z) q -F k ) , for z ∈ Ω j ∪ Ω j+1 , for -L ≤ j < K, (68)
A(z) := -B(z) + X(z) p Y (z) q -F, for z ∈ Ω K ∪ Ω K+1 .
(69) We now have two denitions of A(z) in each Ω j for -L ≤ j ≤ K, noting that A(z) was previously dene only on Ω -L-1 ∪ Ω -L . So, we need to show that these denitions are equivalent in each case. For z ∈ Ω -L and M ≥ 2, the denition (68) (for j = -L) coincides with A(z) (as previously dened) due to (58). For z ∈ Ω s , where -L < s < K, and M ≥ 2, the function A(z) is dened by (68) for j = s and j = s -1, and these denitions are equivalent due to (57) at j = s. For z ∈ Ω K and M ≥ 2 the denitions (68) (for j = K -1) and ( 69) are equivalent due to (59). Finally, for M = 1, the only case to check is z ∈ Ω 0 , where (69) holds due to (60). Hence A(z) is well dened for

z ∈ Ω -L-1 ∪ Ω -L ∪ • • • ∪ Ω K ∪ Ω K+1 . Moreover, each expression dening A(z) on a set Ω j ∪ Ω j+1 is meromorphic, so A(z) is meromorphic on Ω -L-1 ∪ Ω -L ∪ • • • ∪ Ω K ∪ Ω K+1 . We can then dene A(z) on γ -L-1 -Ω -L-1 ∪ Ω -L ∪ • • • ∪ Ω K ∪ Ω K+1 using A(z) := A(γ -L-1 -z),
as this is consistent on the overlapping region

Ω -L-1 ∪ Ω -L = γ -L-1 -Ω -L-1 ∪ Ω -L by (61). Now, for z ∈ Ω K ∪ Ω K+1 , using (62) yields -A(z) + X(z) p Y (z) q = -A(γ K -z) + X(γ K -z) p Y (γ K -z) q ,
so by our extended denition,

A(γ -L-1 -γ K + z) = A(z) -X(z) p Y (z) q + X(γ K -z) p Y (γ K -z) q ,
And we can use this to extend our denition of A to all of C.

We then dene B(z) on C by B(z) = -A(z) + X(z) p Y (z) q -F , as, by (69), this is consistent with the value of B(z) in the region Ω K ∪Ω K+1 where it was already dened. From this denition of B(z), we have immediately (63). Moreover, we know that (64), ( 65), ( 66) and (67) hold on the subsets where A(z) and B(z) were originally dened, so they must hold on all of C due to the meromorphic extension. Now we will show that conditions (i)-(iv) hold. First, consider the denition (53) for j ∈ [-L, K -1]. We know that for z ∈ Ω j ∪ Ω j+1 , the series L j and R j+1 dening V j converge, so V j can only have a pole in this region at poles of X j (z) and Y j (z). In particular, V j (z) has no poles in Ω j because |X j (z)|, |Y j (z)| ≤ 1 in this region. Now, to prove (i), assume j ∈ [-L + 1, 0] is an integer and recall that for z ∈ Ω j , the function A(z) satises (68). Since j ≤ 0, we can rewrite this as

A(z) = V j (z) + δ j,0 X(z) p Y (z) q - j k=-L F k .
Now, as discussed, V j (z) does not have a pole here. Moreover, δ j,0 X(z) p Y (z) q cannot have a pole either, as either j = 0 and so this term vanishes or j = 0 and neither X(z) nor Y (z) has a pole in Ω j = Ω 0 . Hence A(z) does not a any poles in

Ω j for j ∈ [-L + 1, 0]. If j ∈ {-L -1, -L}, then A(z) is dened by (54), which converges for z ∈ Ω -L ∪ Ω -L-1 , so A(z)
has no poles in this region either. In fact, by Lemma 5.7, the series A has no constant term, so any root of

X -L (z) in Ω -L ∪ Ω -L-1 must be a root of A(z), proving (ii).
Conditions (iii) and (iv) can be proven similarly. For (iii), we consider j ∈ [0, K -1] and compare (68) to (63), which yields

F + B(z) = -V j (z) + j k=-L F k ,
so the fact that V j (z) has no poles in Ω j implies that B(z) also has no poles in Ω j . For z ∈ Ω K ∪ Ω K+1 , the function B(z) is dened by (55), which converges for z ∈ Ω K ∪ Ω K+1 , so B(z) has no poles in this region either, proving (iii). In fact, by Lemma 5.7, the series B has no constant term, so any root of Y K (z) in Ω K ∪ Ω K+1 must be a root of B(z), proving (iv). so

c j = X j (γ j -β j ) (A(β j ) -s j X(β j ) p Y (β j ) q ) -X j (β j ) (A(γ j -β j ) -s j X(γ j -β j ) p Y (γ j -β j ) q ) X j (β j ) -X j (γ j -β j ) .
This formula determines the constant for β j = γj 2 . In the case β j = γj 2 , the denominator of (74) has a double root at z = β j = γj 2 , so the numerator of (74) must also have a double root at this point. Hence, we have

0 = 2X j (β j )V j (β j ) -2X j (β j )V j (β j ), so c j = X j (β j ) X j (β j ) (A (β j ) -(s j X(z) p Y (z) q ) | z=βj ) + s j X(β j ) p Y (β j ) q -A(β j ).

Solution to functional equations in an M -quadrant cone

In this section we use the same methods as we used in Section 4 to analyse the generating function of walks in the 3-quadrant cone. In particular we characterise the nature of the series Q j (x, y; t). As we will show, for M odd this nature is exactly the same as the nature of C(x, y; t) which counts walks in the three-quadrant cone. For M even the situation is dierent: the generating function is always D-nite, and it is algebraic if and only if q = 0 and L is even or, if we allow starting points outside the rst quadrant, p = 0 and L is odd. These results are summarised in Figure 9.

In the previous section we reduced the problem to nding the unique meromorphic functions A, B : C → C ∪ {∞} and constant F(t) characterised by Theorem 5.11 (for each t). This is a generalisation of Theorem 2.8 as well as an analogous Theorem found by Raschel for walks in the quarter plane [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF], which corresponds to M = 1. A chart showing how to determine the complexity of the series Q j (x, y; t) counting walks starting at (p, q) conned to an M -quadrant cone as a series in x (or y) as proven by Theorems 6.2-6.9. Recall that L determines which M quadrants are used to dene the M -quadrant cone.

A rst general result relates the complexity of Q j (x, y; t) to that of the function A(z) and B(z) using the properties X-algebraic, X-D-nite and X-D-algebraic dened in appendix B: Lemma 6.1. Assume P is one of the properties algebraic, D-nite or D-algebraic and t ∈ 0, 1

P(1,1)
is xed. The following are equivalent: (i) The function Q j (x, y; t) has property P as a function of x, (ii) The function Q j (x, y; t) has property P as a function of y, (iii) A(z) has property X-P, (see Appendix B) (iv) B(z) has property X-P. Proof. The equivalence (iii) ⇐⇒ (iv) follows from (63), since by Proposition B.12, the property X-P is closed under addition. To show that these are equivalent to (i) and (ii), we will start by considering two further equivalent properties, thinking of Q j (x, y; t) as a function of x j and y j rather than x and y:

(i') The function Q j (x, y; t) has property P as a function of x j , (ii') The function Q j (x, y; t) has property P as a function of y j . Indeed if j is even then x j ∈ {x, 1

x } and y j ∈ {y, 1 y } so (i') ⇐⇒ (i) and (ii') ⇐⇒ (ii). If j is odd then x j ∈ {y, 1 y } and y j ∈ {x, 1

x } so (i') ⇐⇒ (ii) and (ii') ⇐⇒ (i). In either case it suces to prove that the equivalent properties (iii) and (iv) are also equivalent to (i') and (ii'). In fact we will just prove that (ii') is equivalent to (iv) as the proof that (i') is equivalent to (iii) is essentially the same.

For j < K, it follows from (49) and ( 50) that (ii') holds if and only if x j L j (y j ) + y j R j+1 (y j ) has property P as a function of y j since all other terms are linear in y j . Moreover, this occurs if and only if L j (y j ) and R j+1 (y j ) both have property P in y j . If y j ∈ {x, 1

x }, then they have this property with respect to x, while if y j ∈ {y, 1 y }, then they have this property with respect to y. Either way, by Proposition B.11, this occurs if and only if the expressions (73) and (74) determining L j (Y j (z)) and R j+1 (Y j (z)) each have property X-P. From these equations, combined with Proposition B.12, this occurs if and only if V j (z) has this property. Finally, by (72), V j (z) has property X-P if and only if A(z) has this property, which is equivalent to (iii). So we have proven that for j < K, (ii') holds if and only if (iii) holds. For j = K, (51) shows that (ii') holds if and only if B(y K ; t) has property P in y K . By Proposition B.11, this is equivalent to (iv). So we have proven (ii') ⇐⇒ (iii) ⇐⇒ (iv). Finally, proving that (i') is equivalent to (iii) and (iv) is similar (noting that X-P and Y -P are equivalent).

For M even the situation is relatively simple, as described by the following theorems. In this case the M -quadrant cone on which the walks occur could alternatively be understood as a cone constructed from M/2 half planes, perhaps partially explaining why the complexity should match the complexity of half-plane walks. Theorem 6.2. Assume M ≥ 2 is even. For any integer j ∈ [-L, K], the series Q j (x, y; t) is D-nite in x and y.

For xed t ∈ 0, 1 P(1,1) , this theorem is proven in Theorem 6.10 and Lemma 6.12. Lemma 4.4 then implies that the series

Q j (x, y; t) ∈ R[x, 1 x , y, 1 y ][[t]
] is D-nite in x and y. Theorem 6.3. Assume M ≥ 2 is even. For any integer j ∈ [-L, K] and xed t c ∈ 0, 1 P(1,1) , the following are equivalent:

(i) The series

Q j (x, y; t) is algebraic in x j (ii) The series Q j (x, y; t) is algebraic in y j (iii) The function Q j (x, y; t c ) is algebraic in x j (iv) The function Q j (x, y; t c ) is algebraic in y j (v)
L is even (so K is odd) and q = 0, that is, the walks start on the x-axis. Proof. The equivalences (iii) ⇐⇒ (v) and (iv) ⇐⇒ (v) follow from Theorem 6.10 and Lemma 6.14. So (iii) and (iv) each hold for some t c is and only if they hold for all t c . Finally by Lemma 4.4, this is equivalent to (i) and (ii).

Remark: One could alternatively consider the nature of the complete generating function K j=-L Q j (x, y; t) rather than the individual generating functions Q j , although for M > 4 this introduces some ambiguity as to how many paths end at each point in the cone. While it is clear that if each Q j (x, y; t) is algebraic then the complete generating function is algebraic, the converse does not hold, as our result implies that even for M = 2 the generating functions Q j are not algebraic, even though the complete generating function in this case is a generating function for half-plane walks, which is therefore algebraic.

Remark: The only reason why this theorem does not include the possibility that p = 0 is that we assumed that the walks start in the quadrant Q0 , where p > 0. More generally, if the walk is allowed to start at any point (s, (p, q)) ∈ Π L,K , this theorem states the following for s = 0: the generating function is algebraic if and only if (p, q) lies on the same axis as the two boundaries of the cone. But this statement is equivalent for any s as the cone and starting point can simply be rotated sending each point (k, (a, b)) → (k + 1, (-b, a)) (or the inverse of this transformation) until the starting point lies in Γ 0 . So it is true for any starting point (s, (p, q)). Hence, the generating function Q j (x, y; t) is algebraic if and only if (p, q) lies on the same axis as the two boundaries of the cone, that is, if and only if either q is 0 and L is even or p is 0 and L is odd. Theorem 6.4. Assume M ≥ 3 is odd. For xed t ∈ 0, 1

P(1,1)
and any integer j ∈ [-L, K], the following are equivalent (i) The function

Q j (x, y; t) is D-nite in x, (ii)
The function Q j (x, y; t) is D-nite in y, (iii) A(z) satises a linear dierential equation whose coecients are elliptic functions with periods π and πτ , (iv) B(z) satises a linear dierential equation whose coecients are elliptic functions with periods π and πτ , (v) the ratio γ πτ ∈ Q, (vi) the orbit of each point (x, y) ∈ E t under the group of the walk is nite.

The equivalence (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv) is precisely the statement of Lemma 6.1 where P is the property D-nite. Later in this section we complete the proof of the theorem by showing that the rst 4 conditions are equivalent to (v) and (vi). We dene the group of the walk in Appendix C, the equivalence of (v) and (vi) is shown there in Proposition C.2. We show that these equivalent conditions imply the conditions (i)-(iv) in a combination of Theorem 6.10 and Lemma 6.11, while we show the converse in Corollary 6.18.

We have not been able to show the theorem above for M = 1, meaning our classication of the complexity of Q j (x, y; t) for t xed is incomplete. Nonetheless, in Theorem 6.7, we are able to fully classify the complexity of the series

Q j (x, y; t) ∈ R[x j , y j ][[t]].
Theorem 6.5. Assume that M ≥ 1 is odd and γ πτ ∈ Q. For xed t ∈ 0, 1 P(1,1) and any integer j ∈ [-L, K], the following are equivalent (i) The function Q j (x, y; t) is algebraic in x j , (ii) The function Q j (x, y; t) is algebraic in y j , (iii) A(z) has mπτ as a period for some positive integer m, (iv) B(z) has mπτ as a period for some positive integer m, (v) There are rational functions R 1 and R 2 satisfying x p y q = R 1 (x) + R 2 (y) for all (x, y) ∈ E t , (vi) There are rational functions R 1 and R 2 satisfying X(z) p Y (z

) q = R 1 (X(z)) + R 2 (Y (z))
for all z ∈ C, (vii) The orbit sum of the model is 0.

The equivalence (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv) is precisely the statement of Lemma 6.1 where P is the property algebraic. Moreover, we already proved the equivalence (v) ⇐⇒ (vi) ⇐⇒ (vii) in Theorem 4.2. To complete the proof of this Theorem, we show that equivalent conditions (i) -(iv) are equivalent to (v) -(vii) in Theorem 6.10. Theorem 6.6. Assume that M ≥ 1 is odd. Fix t ∈ 0, 1

P(1,1)
and assume that γ πτ / ∈ Q. For any integer j ∈ [-L, K], the following are equivalent (i) The function Q j (x, y; t) is D-algebraic in x j (ii) The function Q j (x, y; t) is D-algebraic in y j (iii) A(z) is D-algebraic in z (iv) B(z) is D-algebraic in z (v) There are rational functions R 1 and R 2 satisfying x p y q = R 1 (x) + R 2 (y) for all (x, y) ∈

E t

(vi) There are rational functions R 1 and R 2 satisfying

X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)) for all z ∈ C
The equivalence (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv) is precisely the statement of Lemma 6.1 where P is the property D-algebraic. Moreover, we showed that (v) ⇐⇒ (vi) in Theorem 4.3.

We complete the proof of this theorem later in this section, starting with Theorem 6.20 which shows that the equivalent conditions (v) ⇐⇒ (vi) imply the equivalent conditions (i)-(iv), then we show the reverse implication in Theorem 6.21.

Finally, the following three Theorems characterise the nature of the series Q(x, y; t) for M odd.

Theorem 6.7. Assume that M ≥ 1 is odd. For any integer j ∈ [-L, K], the following are equivalent (i) The series

Q j (x, y; t) ∈ R[x, y][[t]] is D-nite in x, (ii) The series Q j (x, y; t) ∈ R[x, y][[t]] is D-nite in y, (iii)
Each of the conditions of Theorem 6.4 hold for all t ∈ 0, 1 P(1,1) , (iv) The group of the walk is nite.

Proof. By Lemma 4.4, Condition (i) of Theorem 6.4 holds for all t if and only if (i) holds.

Similarly condition (ii) of Theorem 6.4 holds for all t if and only if (ii) holds. Moreover, by Proposition C.3, Condition (vi) of Theorem 6.4 holds for all t if and only if (iv) holds. Hence, it suces to show that any given condition of Theorem 6.4 holds for all t if and only if any other given condition of Theorem 6.4 holds for all t. For M ≥ 3 this is true because Theorem 6.4 itself holds. So, we will assume for the remainder of this proof that M = 1. In this case the conditions (i), (ii), (iii) and (iv) of Theorem 6.4 are still equivalent due to Lemma 6.1. Moreover, Conditions (v) and (vi) are equivalent by Proposition C.2. We show that (v) and (vi) imply the conditions (i)-(iv) in a combination of Theorem 6.10 and Lemma 6.11, so it remains to prove that if the conditions (i)-(iv) of Theorem 6.4 hold for all t then condition (v) of Theorem 6.4 holds for all t. This is equivalent to the statement of Corollary 6.19. Theorem 6.8. Assume that M ≥ 1 is odd. For any integer j ∈ [-L, K], the following are equivalent (i) The series

Q j (x, y; t) ∈ R[x, y][[t]] is algebraic in x, (ii) The series Q j (x, y; t) ∈ R[x, y][[t]] is algebraic in y, (iii)
The equivalent conditions of Theorem 6.5 hold for all t ∈ 0, 1 P(1,1) . Theorem 6.9. Assume that M ≥ 1 is and the group of the walks is innite. For any integer j ∈ [-L, K], the following are equivalent (i) The series

Q j (x, y; t) ∈ R[x, y][[t]] is D-algebraic in x, (ii) The series Q j (x, y; t) ∈ R[x, y][[t]] is D-algebraic in y, (iii)
The equivalent conditions of Theorem 6.6 hold for all t ∈ 0, 1 P(1,1) .

For each of these theorems, the equivalences (i) ⇐⇒ (iii) and (ii) ⇐⇒ (iii) are both due to Lemma 4.4.

Proof. As we will show, this follows easily from the denition of γ j (see Denition 5.8). Assuming M = K + L + 1 is odd, K and L must have the same parity. If they are both even, then

γ -L-1 = -γ -πτ L 2 and γ K = γ + πτ K 2 , so τ τ = γ K -γ -L-1 πτ = 2γ πτ + K + L 2 , so τ τ ∈ Q if and only if γ πτ ∈ Q and N 2 τ τ ∈ Z if and only if N 2 2γ πτ ∈ Z.
If L and K are both odd then γ -L-1 = γ -πτ L+1 2 and γ K = -γ + πτ K+1 2 , so

τ τ = γ K -γ -L-1 πτ = - 2γ πτ + K + L + 2 2 , so τ τ ∈ Q if and only if γ πτ ∈ Q and N 2 τ τ ∈ Z if and only if N 2 2γ πτ ∈ Z.
To nish the proof of Theorem 6.2 we use the following Lemma Lemma 6.12. If M ≥ 2 is even then

τ τ = M 2 ∈ Z.
Proof. From the denition of γ j (Denition 5.8), we always have

γ j+2 = γ j + πτ 2 . Hence, if M = K + L + 1 is even, then γ K = γ -L-1 + M 2 πτ . Hence τ τ = γ K -γ -L-1 πτ = M
2 , as required. To nish the proof of Theorem 6.5 we use the following lemma Lemma 6.13. Dene F (z) := X(z) p Y (z) q . If M ≥ 1 is odd, then Ẽ(z) is equal to the orbit sum

E(z) := N2-1 j=0 F ((2j + 1)γ -z) -F (2jγ + z)
dened in Theorem 4.11 and used throughout Section 4.

Proof. Recall from (71) that J(z) that they can be written as J(z) = F (γ -z) -F (z). Hence Ẽ(z) can be written in terms of F (z) as

Ẽ(z) = N2-1 j=0 F ((j + 1)γ -L-1 -jγ K -z) -F (j(γ K -γ -L-1 ) + z).
We will now consider two cases.

Case 1: L is even.

In this case K = M -L -1 is also even, so by Denition 5.8,

γ K = γ + K 2 πτ , while γ -L-1 = -γ -L 2 πτ
. Since πτ is a period of F (z), this implies that

Ẽ(z) = N2-1 j=0 F (-(2j + 1)γ -z) -F (2jγ + z) = E(z).
Case 2: L is odd.

In this case K = M -L -1 is also odd, so by Denition 5.8, γ K = -γ + K+1 2 πτ , while

γ -L-1 = γ -L+1 2 πτ
. Since πτ is a period of F (z), this implies that

Ẽ(z) = N2-1 j=0 F ((2j + 1)γ -z) -F (-2jγ + z).
Now, since 2γN 2 ∈ πτ Z, we can rewrite this as

Ẽ(z) =   N2-1 j=0 F ((2(j -N ) + 1)γ -z)   -   N2-1 j=0 F (2(N -j)γ + z)   .
set, so the boundary of X(Γ) is X(∂Γ), where ∂Γ is the boundary of Γ. Moreover, since Γ is a connected component of X -1 (D t ), we have X(∂Γ) ⊂ ∂D t . So X(Γ) is a non-empty, open subset of the connected set D t and its boundary is a subset of the boundary of D t , which is only possible if X(Γ) = D t . In particular, there is some z 0 ∈ Γ satisfying X(z 0 ) = 0, so z 0 ∈ Ω 4m ∪ Ω 4m-1 for some m, which implies that Γ contains Ω 4m ∪ Ω 4m-1 . This completes the proof of claim 1.

We will reach a contradiction using this claim along with the equation

X(z) p Y (z) q = F + A(z) + B(z), (79)
and the related equation

X(z) p (Y (z) q -Y (-γ -z) q ) = B(z) -B(-γ -z), (80)
by comparing the possible positions of poles of X, Y , A and B for varying t. To analyse the relationship between X(z), Y (z) and t, we need to use the denition of P(x, y) and dene

P β (x) := 1 α=-1 w (α,β) x α ,
for -1 ≤ β ≤ 1, so that P(x, y) = y -1 P -1 (x) + P 0 (x) + yP 1 (x).

(81) Now, for general z ∈ C, we have P(X(z), Y (z)) -1 t = 0 so the polynomial yP (X(z), y) -y t has roots at y = Y (z) and y = Y (-γ -z). Hence it's coecients are related by

P 0 (X(z)) - 1 t = -P 1 (X(z))(Y (z) + Y (-γ -z)), (82)
P -1 (X(z)) = P 1 (X(z))Y (z)Y (-γ -z). (83)
The second consequence of (81) is the following claim:

Claim 2: There are values x 0 , x 1 , y 0 , y 1 ∈ C ∪ {∞} which do not depend on t such that, for any t, if ε is a pole of Y (z), then {X(ε), X(-γ -ε)} = {x 0 , x 1 } and if δ is a pole of X(z), then

{Y (δ), Y (γ -δ)} = {y 0 , y 1 }.
Proof of Claim 2: We will prove the claim for x 0 and x 1 as the other part of this claim is equivalent. In general, X(z) and X(-γ -z) are the two roots for x of the quadratic polynomial x Y (z) P(x, Y (z)) -x tY (z) . As z → ε, this converges to xP 1 (x), so we can simply dene {x 0 , x 1 } to be the roots of xP 1 (x), which do not depend on t. In the case the w (1,1) = 0 but w (0,1) = 0, the polynomial xP 1 (x) is linear, so it only has one root, however one of the roots of x Y (z) P(x, Y (z))x tY (z) converges to ∞ as z → δ, so we can let x 0 = ∞ and x 1 be the unique root of xP 1 (x). Finally if w (1,1) = w (0,1) = 0, we can set x 0 = x 1 = ∞. This completes the proof of Claim 2. Now, assume that t is suciently small that the values x 0 , x 1 , y 0 , y 1 that are not ∞ lie in D t .

Claim 3: If δ is a pole of X(z) but not of Y (z), then it is not a pole of B(z). Similarly, if ε is a pole of Y (z) but not of X(z), then it is not a pole of A(z).

Proof of Claim 3: Assume ε is a pole of Y (z) but not of X(z). Then by our assumption,

X(ε) = x 0 ∈ D t or X(ε) = x 1 ∈ D t .
Hence by Claim 1, A(z) does not have a pole at ε. The other part of the claim is equivalent, so this completes the proof of the claim.

We will now consider a number of cases separately regarding the nature of X and Y around a pole δ of X(z).

Case 1: w (1,1) = w (1,0) = 0, so δ is a double pole of X(z) and a simple pole of Y (z).

In this case the second pole -γ -δ of X(z) must in fact be equal to (a possibly shifted version of) δ, that is, -γ -δ ∈ δ + πZ + πτ Z. Hence, X(z) = X(-γ -z) = X(2δ -z) and Y (z) = Y (γ -z) = Y (-2δ -z). Now, since Y (z) has a pole at δ, it must have a pole at γ -δ, but X(z) cannot have a pole at this point, so by Claim 3, A(z) does not have a pole at z = γ -δ. Moreover, since A(z) = A(-γ -z), this means that A(z) does not have a pole at z = -2γ + δ either. Now taking successive dierences of (79) yields

X(-2δ-z) p Y (-2δ-z) q -X(z) p Y (z) q +X(2δ-z) p Y (2δ-z) q -X(-4δ+z) p Y (-4δ+z) q = A(γ-z)-A(2γ+z),
and as we have shown the right hand side of this equation does not a have a pole at z = δ. Now we will reach a contradiction by analysing the left hand side near z = δ. Since Y (z) has a simple pole at this point, while X(z) has a double pole and X(δ -z) = X(δ + z), we may write X(z) = c 1 (x -δ) -2 + O(1) and Y (z) = c 2 (y -δ) -1 + c 3 + O(y -δ), where c 1 , c 2 = 0. Then the left hand side of the equation above behaves as

c p 1 c q 2 (1 -(-1) q )(x -δ) -2p-q + c p 1 c q-1 2 c 3 (1 + (-1) q )(x -δ) -2p-q+1 + O (x -δ) -2p-q+2 .
Since we know that the expression must not have a pole at δ, the two leading terms must be 0, which is only possible if q is even and

c 3 = 0. But then Y (z) + Y (-γ -z) → 2c 0 = 0 as z → δ.
Comparing to (82), this implies that

1 t -P 0 (x) P 1 (x) → 0 as x → ∞.
But since w (1,1) = w (1,0) = 0, we must have

1 t -P 0 (x) P 1 (x) → 1 tw (0,1) = 0 as x → ∞, a contradiction.
Case 2: w (1,1) = w (0,1) = 0.

This is symmetric to the previous case so the same proof applies.

For the remaining cases we assume that p ≥ q, as the q ≥ p case is equivalent.

Case 3:

w (1,1) = 0 = w (0,1) , w (1,0) , so X(z) and Y (z) share a simple pole δ ∈ Ω 1 ∪ Ω 2 . In this case γ -δ is a pole of Y (z) but not X(z) while -γ -δ is a pole of X(z) but not Y (z).
Using (79), we have

X(z) p Y (z) q -X(γ -z) p Y (γ -z) q -X(-γ -z) p Y (-γ -z) q = -F -A(γ -z) -B(-γ -z).
Analysing this around z = δ yields a contradiction: The right hand side has no pole at z = δ, while the terms X(z) p Y (z) q , X(γ -z) p Y (γ -z) q and X(-γ -z) p Y (-γ -z) q have poles of orders p + q, q and p, respectively, so the left hand side has a pole of order p + q.

Case 4: w (1,1) = 0, so X(z) and Y (z) do not share any poles.

Both δ and -γ -δ are poles of X(z), so they are not poles of Y (z). Hence by Claim 3, these must also not be poles of B(z). In particular, this implies that the right hand side of (80) does not have a pole at z = δ, so the left hand side

X(z) p (Y (z) q -Y (-γ -z) q )
is also analytic at z = δ. Hence, (Y (z) q -Y (-γ-z) q ) must have a root of order at least p at z = δ. Moreover, in the case that X(z) has a double pole at z = δ, the function (Y (z) q -Y (-γ -z) q ) must have a root of order at least 2p at z = δ. We will now consider dierent values of q in separate cases.

Case 4a:

q = 1
In this case Y (z) -Y (-γ -z) has a root of order at least p ≥ 1 at z = δ, so, in particular Y (δ) = Y (-γ -δ), which implies that -γ -δ ∈ {δ, γ -δ} + πZ + πτ Z. But since γ πτ ∈ R \ Q, we do not have -2γ ∈ πZ+πτ Z, so we are left with the case -γ -δ ∈ δ +πZ+πτ Z. this implies that X(δ + z) = X(-γ -δ -z) = X(δ -z), so X(z) must have a double pole at z = δ. The function Y (z) -Y (-γ -z) has at most 4 poles in each fundamental domain (counting with multiplicity), so it must have at most 4 roots (counting with multiplicity). Since Y (z) has both π and πτ as periods, it is clear that -γ 2 , -γ+π 2 , -γ+πτ 2 , -γ+π+πτ 2 are all distinct roots of Y (z) -Y (-γ -z), so they must be the only roots and they must all be simple roots. In particular, this implies that δ cannot be a double root of Y (z) -Y (-γ -z), so it must be a pole of X(z)(Y (z) -Y (-γ -z)), and hence X(z) p (Y (z) q -Y (-γ -z) q ), a contradiction. Case 4b: q ≥ 2 and Y (δ) = 0.

By our assumption that p ≥ q, we also have p ≥ 2. We will use the product

Y (z) q -Y (-γ -z) q = q-1 m=0 (Y (z) -e miπ q Y (-γ -z)).
Since this has a root at z = δ we must have Y (-γ -δ) = 0. As in the previous case -γ -δ ∈ δ + πZ + πτ Z and so X has a double pole at δ. If Y (z) has a double root at δ then it must be the only root of Y (z), so γ -δ ∈ δ + πτ Z + πZ, which is impossible since

-γ -δ ∈ δ + πZ + πτ Z but γ πτ / ∈ Q. So Y (z) does not have a double pole at δ. Now, each function Y (z) -e miπ q Y (-γ -z) has a pole at z = δ, since Y (δ) = Y (-γ -δ) = 0. However, the derivative of this function at z = δ is Y (δ) + e miπ q Y (-γ -δ) = Y (δ) 1 + e miπ q
, so the function has a double pole if and only if e miπ q

= -1 i.e., m = q 2 . Moreover, from (82), the function

Y (z) + Y (-γ -z) = 1 t -P 0 (X(z)) P 1 (X(z)) ∼ 1 tw (1,1) X(z) ,
which has a double root but not a triple root at z = δ. Note that the expression above uses the fact that w (1,0) = 0 -if this was not the case then Y (z) + Y (-γ -z) would not have a root at z = δ. So nally, the function Y (z) -e miπ q Y (-γ -z) has a simple root at z = δ if m = q 2 , while it has a double root if m = q 2 . This implies that in the case that q is odd, Y (z) q -Y (-γ -z) q has a root of order exactly q at z = δ, while in the case that q is even Y (z) q -Y (-γ -z) q has a root of order exactly q + 1 at this point. In either case, X(z) p (Y (z) q -Y (-γ -z) q ) has a pole of order at least 2p -q -1 ≥ p -1 > 0, a contradiction. Case 4c: q ≥ 2 and Y (δ) = 0.

In this case at most one function

Y (z) -e miπ q Y (-γ -z) in the product q-1 m=0 (Y (z) -e miπ q Y (-γ -z))
can have a root at z = δ. Since we know that the product has a root at δ, there must be some such value of m, so we dene u := e miπ q for this m. Then X(z) p (Y (z) -uY (-γ -z)) has no pole at z = δ. For m = 0 (i.e., u = 1), this is equivalent to the q = 0 case, which we showed was impossible, so we are left with the case m = 0. In the case that u = -1, using (82), we have

Y (z) -uY (-γ -z) = - P 0 (X(z)) -1 t P 1 (X(z)) .
For suciently small t, the numerator lies in Ω(1) while the denominator is in O((z -δ) -1 ), so Y (z) -uY (-γ -z) = Ω(z -δ) around z = δ. This implies that X(z) p (Y (z) -uY (-γ -z)) has a pole of order at least p -1 > 0, a contradiction. If u = -1, then we must have q ≥ 3, as for q = 2 the only possibilities are u = 1 and u = -1. The function H(z) dened by

H(z) = (Y (z) -uY (-γ -z))(uY (z) -Y (-γ -z))
can be written as

H(z) = u(P 0 (X(z)) -1 t ) 2 -(u + 1) 2 P -1 (X(z)) 2 P 1 (X(z)) 2 .
The numerator of this equation lies in Ω(1) (for suciently small t), while the denominator is in O((z -δ) -2 ), So H(z) = Ω((z -δ) 2 ) and so Y (z) -uY (-γ -z) = Ω((z -δ) 2 ). This implies that X(z) p (Y (z) -uY (-γ -z)) has a pole of order at least p -2 ≥ q -2 > 0, a contradiction. Theorem 6.17. Assume that τ τ / ∈ Q and B(z) does not have πτ as a period. Then Q j (x, y; t) is not D-nite in x or y.

which implies that T (z) satises T

(z) = T (γ K -z) = T (γ -L-1 -z) = T (z + π).
Combining these shows that T (z) is an elliptic function with periods π and πτ = γ K -γ -L-1 , so it must be D-algebraic (since T (z) and T (z) must be related by a non-trivial polynomial equation). Now, since X(z) is also D-algebraic, it follows from (84) that B(z) is also D-algebraic in z. This is precisely condition (v) of Theorem 6.6, which we showed to be equivalent to conditions (i) and (ii), that Q j (x, y; t) is D-algebraic in x and y. 6.2.2. Non-decoupling cases. In this section we show that if there is no decoupling function, then the generating function is not D-algebraic in x, as in Subsection 4.2.2 for the 3-quadrant cone. The proof works along the same lines as [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Hardouin | On dierentially algebraic generating series for walks in the quarter plane[END_REF] for the quarter plane case, which relies on Galois theory of q-dierence equations. Rather than essentially rewriting these entire proofs, in Appendix D we use results from [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF] to deduce Corollary D.2, which avoids Galois theory language in its statement, and can be readily applied to show the main result of this section. Theorem 6.21. Fix t ∈ 0, 1 P (1,1) . Assume that there are no rational functions

R 1 , R 2 ∈ C(x) satisfying X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)).
Then the function Q j (x, y; t) is not D-algebraic in x or y.

Proof. It suces to prove that B(z) is not D-algebraic, as we showed below the statement of Theorem 6.6 that this is equivalent to Q j (x, y; t) being D-algebraic in x or y. Now assume for the sake of contradiction that B(z) is D-algebraic in z. We will show that this implies that there are rational functions R 1 and R 2 satisfying the equation in the theorem. Now, by (63), the functions h(z) := X(z) p Y (z) q , f 1 (z) := A(z) + F and f 2 (z) := B(z) satisfy the conditions of Corollary D.2, with γ 1 = γ -L-1 and γ 2 = γ K . Hence, there are meromorphic functions a 1 , a

2 : C → C ∪ {∞} satisfying X(z) p Y (z) q = a 1 (z) + a 2 (z), a 1 (z) = a 1 (z + π) = a 1 (z + πτ ) = a 1 (γ -L-1 -z), a 2 (z) = a 2 (z + π) = a 2 (z + πτ ) = a 2 (γ K -z).
Recall that M = K + L + 1 is odd, so K and L have the same parity. If K and L are both even then γ K = γ + K 2 πτ and γ -L-1 = -γ -L 2 πτ , so a 1 (z) = a 1 (-γ -z) and a 2 (z) = a 2 (γ -z). Hence by Proposition B.6, a 1 (z) is a rational function of X(z), while a 2 (z) is a rational function of Y (z). Hence we can write

X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)),
as required. Similarly, in the case that K and L are both odd a 1 (z) = a 1 (γ -z) and a 2 (z) = a 2 (-γ -z), so by Proposition B.6, a 1 (z) is a rational function of Y (z), while a 2 (z) is a rational function of X(z). Hence in this case we can still write

X(z) p Y (z) q = R 1 (X(z)) + R 2 (Y (z)).

Conclusion and further questions

In this article we deduced a complex analytic functional equation characterising the generating function C(x, y; t) counting three quarter plane walks, and subsequently we generalised this to count walks in the M -quadrant cone. We deduced several results using this functional equation, although there are also several questions that we have left open, which we pose below.

The most conspicuous unanswered question relates to the nature of the generating function with respect to the third variable t: Question 1. Is the nature of the generating function C(x, y; t) always the same with respect to t as with respect to x and y? Indeed from a combinatorial perspective series in t are the most natural as for example, the series C(1, 1; t) is the generating function for all walks in the three quarter plane, whereas, while xing t is convenient for the complex analytic methods used in this article, it has little interest from a combinatorial perspective. We believe that at least certain aspects of this question can be answered using the results of this article: for example proving that C(x, y; t) is D-algebraic in t exactly when it is D-algebraic in x may be provable in the same way as it was proven in the quarter plane [START_REF] Dreyfus | Length derivative of the generating series of walks conned in the quarter plane[END_REF][START_REF] Hardouin | On dierentially algebraic generating series for walks in the quarter plane[END_REF][START_REF] Dreyfus | Dierential algebraic generating series of weighted walks in the quarter plane[END_REF]. Moreover, it may be possible to prove that certain cases are algebraic or D-nite using modular properties of the solutions as functions of τ , as in [START_REF] Elvey | Counting lattice walks by winding angle[END_REF] and [START_REF] Elvey | The six-vertex model on random planar maps revisited[END_REF].

Our next two questions relate to the nature of the generating functions for xed t:

Question 2. Are there any models along with xed values of t for which

γ πτ / ∈ Q but Q(x, y; t) is a rational function of x?
This is the only missing ingredient from a complete characterisation of the nature of the generating functions Q j (x, y; t) with respect to x, as for all M -quadrant cones with M ≥ 3 odd, we showed that no such model exists (see Theorem 6.4).

Another unanswered question is the following: Question 3. Are there any models for which the presence of a decoupling function depends on the value of t?

Equivalently we could ask whether it is possible that C(x, y; t) is D-algebraic with respect to x for some values of t but not others. The analogous question of whether the group is nite is clearly yes, as it only depends on whether the parameter γ πτ ∈ Q. It seems that in most cases γ πτ varies as a function of t (perhaps in all non-D-nite cases), and so this parameter will typically be rational for t in a dense subset of its range 0, 1 P (1,1) . Despite this we do not know of an example where the existence of a decoupling function depends on t.

Another natural question is whether the results in this article also hold on subtly dierent spaces, which could also be called M -quadrant cones. We make this precise below: Denition 7.1. Partition Z 2 into four quadrants

Q 0 = {(m, n) ∈ Z 2 : m, n ≥ 0}, Q 1 = {(m, n) ∈ Z 2 : n ≥ 0 > m}, Q 2 = {(m, n) ∈ Z 2 : 0 > m, n}, Q 3 = {(m, n) ∈ Z 2 : m ≥ 0 > n},
and dene the alternative M -quadrant cone to be the gluing of M copies of these quadrants in a spiral. Say a walk in an alternative M -quadrant cone can only step between adjacent quadrants. More precisely, we extend the denitions of

Q k to any k ∈ Z by Q k = Q k-4 , then the alternative M -quadrant cone is the set of points (k, (m, n)) where (m, n) ∈ Q k , and steps are only allowed from (k 1 , (m 1 , n 1 )) to (k 2 , (m 2 , n 2 )) if k 1 -1 ≤ k 2 ≤ k 1 + 1.
Question 4. Is the nature of the series the same for walks in the alternative k-quadrant cone as in the k-quadrant cone?

For the case k = 3 this is equivalent to the question discussed in Subsection 4.4: Question 5. For walks in the three-quadrant cone, does the nature of the walk change if the steps between (0, 1) and (1, 0) are forbidden? (91)

Proof. In [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF], the Authors dene we may assume that D is the connected component containing ω2 2 . They also dene connected components Dx and Dy of Λ-1 (D x ) and Λ-1 (D y ), respectively, satisfying D = Dx ∪ Dy .

Finally they dene non-intersecting innite paths Γ+

x , Γ-

x , Γ+ y , Γ+ y , and they prove the following in and above Lemma 2.9:

• For ω ∈ Γ+ x and Γ- x are ω 1 -periodic and do not cross the vertical line through ω2 2 .

• The paths Γ+ y and Γ- y are ω 1 -periodic and do not cross the vertical line through ω2+ω3 2 .

• The domain D is delimited by a left boundary Γ+

x and a right boundary Γ+ y and it contains Γ-1

x and Γ-1 y .

• The domain Dx is delimited by Γ+

x and Γ- x , while the domain Dy is delimited by Γ- y and Γ+ y . We know that D and D + ω 2 do not intersect, as this would contradict the claim that D is a connected component of Λ-1 (D). This implies that Γ+

x + ω 2 is to the right of Γ+ y . Moreover, the fact that D is connected implies that Γ-

x is to the right of Γ- y . So the lines Γ+ x , Γ- y , Γ- x , Γ+ y and

Γ+

x + ω 2 are in that order from left to right. nally we can dene the sets D s . For s ∈ Z, we dene This equation is equivalent to (85). Moreover, (86) follows by taking the complement of both sides in (85). The equations (87) and (88) follow similarly from considering Λ-1 (D x ).

The only remaining equations to prove are (90) and (91). Recall that Dx = D -1 ∪ D 0 is a connected component of Λ-1 (D x ) = {ω ∈ C : |x(ω)| < 1}. Then since x(ω) = x(-ω) = x(ω 2 -ω), the set ω 2 -Dx is also a connected component of Λ-1 (D x ). Moreover, Dx and ω 2 -Dx both contain ω2

2 , so they must be the same set, that is Dx = ω 2 -Dx , so Γ+

x = ω 2 -Γ-

x . This implies that the transformation ω → (2s + 1)ω 2 -ω swaps the boundaries Γ+

x + sω 2 and Γ- x + sω 2 of D 4s ∪ D 4s-1 , while the transformation ω → 2sω 2 -ω swaps the boundaries Γ-

x + (s -1)ω 2 and

Γ+

x + sω 2 of D 4s ∪ D 4s-1 . Together these imply the rst part of (91). Now we will show that D 2s ∪ D 2s-1 contains the line (s+1)ω2 2 + iR. Consider the reection in this line, which is given by ω → (s + 1)ω 2 -ω. We know that the transformation ω → (s + 1)ω 2 -ω swaps the boundaries of D 2s ∪ D 2s-1 , so by symmetry in the real line, the reection ω → (s + 1)ω 2 -ω also swaps the boundaries of D 2s ∪ D 2s-1 . Hence the line (s+1)ω2 2 + iR at the centre of this reection must be contained in D 2s ∪ D 2s-1 . This completes the proof of (91). To prove (90) similarly, we just need to show that ω2+ω3 2 ∈ Dy . Note that ω2 2 < ω2+ω3 2 < ω 2 . We know that ω2 2 ∈ D -1 ∪ D 0 . Moreover, 2ω 2 -Γ - x = (ω 2 + Γ + x ), hence ω 2 must lie between the lines Γ - x = (ω 2 + Γ + x ). So, both ω2

2 and ω 2 lie between Γ + x and Γ + x + ω 2 , hence ω2+ω3 2 also lies between these lines, that is ω2+ω3 Appendix B. Nature of analytic functions of X(z) In this appendix we assume that f : C → C ∪ {∞} is a meromorphic function, with π as a period, Λ ⊂ C is a set with non-empty interior and A : X(Λ) → C ∪ {∞} is a meromorphic function satisfying A(X(z)) = f (z) for z ∈ Λ. We dene properties X-rational, X-algebraic, X-D-nite and X-D-algebraic and in each of the four cases we show that the function f (z) has the property X-P if and only if A(x) has the property P. Importantly, the properties X-P do not depend on the set Λ. Similarly, we assume g : C → C ∪ {∞} is a meromorphic function with period π and B : Y (Λ) → C ∪ {∞} is a meromorphic function satisfying B(Y (z)) = g(z) for z ∈ Λ. We then dene properties Y -P such that g(z) has the property Y -P if and only if B(y) has the property P. In fact, as we will see if P is one of the properties algebraic, D-nite or D-algebraic then the properties X-P and Y -P are the same. The results in this appendix are usually applied in the article in cases where Λ = Ω j for some j, in which case f (z) and g(z) automatically have π as a period, as this property is inherited from X and Y . Denition B.1. We say that the function f : C → C ∪ {∞} with period π is X-rational if it satises

f (z) = f (z + πτ ) = f (-γ -z),
for all z ∈ C. We say that the function g : C → C ∪ {∞} is Y -rational if it satises

f (z) = f (z + πτ ) = f (γ -z),
Denition B.2. We say that the function f : C → C ∪ {∞} with period π is X-algebraic or equivalently Y -algebraic if it has mπτ as a period for some positive integer m. Denition B.3. We say that the function f : C → C ∪ {∞} with period π is X-D-nite or equivalently Y -D-nite if it satises an equation of the form S(z) + n j=0 f (j) (z)S j (z) = 0, Corollary D.2. Let τ, γ 1 , γ 2 ∈ C such that π, πτ, γ 2 -γ 1 are linearly independent (over Z) and let f 1 , f 2 , h : C → C ∪ {∞} be meromorphic functions satisfying

h(z) = f 1 (z) + f 2 (z) h(z) = h(z + π) = h(z + πτ ) f 1 (z) = f 1 (z + π) = f 1 (γ 1 -z) f 2 (z) = f 2 (z + π) = f 2 (γ 2 -z).
If f 2 is dierentially algebraic there are meromorphic functions a 1 , a 2 : C → C ∪ {∞} satisfying h(z) = a 1 (z) + a 2 (z)

a 1 (z) = a 1 (z + π) = a 1 (z + πτ ) = a 1 (γ 1 -z) a 2 (z) = a 2 (z + π) = a 2 (z + πτ ) = a 2 (γ 2 -z). Proof. Dene b(z) = h(z) -h(γ 1 -z). Then b(z) = f 1 (z) -f 2 (z) -f 1 (γ 1 -z) + f 2 (γ 1 -z) = f 2 (γ 2 -γ 1 + z) -f 2 (z).
Hence setting f := f 2 , we have exactly the conditions of Proposition D.1, with ω 1 = π, ω 2 = πτ and ω 3 = γ 2 -γ 1 . Hence, we have the result that for any pole q 0 of b(z), the function

k i=1 b(z + n i ω 3 )
does not have a pole at q 0 , where the sum includes all integers n i such that q 0 + n i ω 3 is a pole of b (including n i = 0). In fact, this implies that for k suciently large the sum does not have a pole at q 0 . In order to construct functions a 1 and a 2 , we will determine an explicit, general form of b using the Jacobi theta function ϑ(z, τ ). In fact, it will be convenient to write it in terms of the function Now for k > 1, we dene

A k (z) := (-1) k-1 (k -1)! d dz k-1 A(z),
which satises A k (z) = A k (z + π) = A k (z + πτ ), and it's only poles are the points q ∈ πZ + πτ Z, where it satises

A k (z) ∼ (z -q) -k + O(1).
Since b is an elliptic function (with periods π and πτ ) it must have only nitely many poles in any fundamental domain. Hence, there are only nitely many sets q +πZ+πτ Z+ω 3 Z, where q is a pole of b. Let {q 0 , q 1 , . . . , q K } be a maximal set of poles of b such that each q k +πZ+piτ Z+ω 3 Z is a dierent set, and let k be suciently large that does not have a pole at any of the K + 1 points q k (a priori there is a dierent N for each q k , but we take the maximum of these). Now for each k ≤ K and n ∈ [-N, N ], let b(z) = s n,k,J (z -q k -nω 3 ) -J + s n,k,J-1 (z -q k -nω 3 ) -J+1 + • • • + s n,k,1 (z -q k -nω 3 ) -1 + O(1) as z → q k + nω 3 . As for N , we choose J suciently large for all k, n. Then the result of Proposition D.1 is that for each xed k and j, we have s n,k,j (A j (z + πτ -q k -nω 3 ) -A j (z -q k -nω 3 )) = (s n,k,j A j (z -q k + (N + 1)ω 3 ) -s n,k,j A j (z -q k -nω 3 ))

= - K k=0 N n=-N J j=1
s n,k,j A j (z -q k -nω 3 ) = -b(z).

Moreover, by the construction, p(z + π) -p(z) = 0 and p(z + πτ ) -p(z) = -2id for some constant d ∈ C .Finally, we dene a 2 (z) = p(z)+p(γ2-z) 2 and a 1 (z) = h(z) -a 2 (z). Then a 2 (z) = a 2 (γ 2 -z) = a 2 (z + π) = a 2 (z + πτ ) and h(z) = a 1 (z) + a 2 (z), so a 1 (z) = a 1 (z + π) = a 1 (z + πτ ). Hence, it suces to show that a 1 (z) = a 1 (γ 1 -z). Indeed

Q0 Q - 1 Q1Figure 3 .

 13 Figure 3. The three-quadrant cone C partitioned into three quadrants Q1 , Q0 and Q -1 .

Figure 4 .

 4 Figure 4. The complex plane partitioned into regions Ω j . For z on the blue lines, |Y (z)| = 1, while on the red lines |X(z)| = 1.

  Algebraic D-algebraic, not D-niteNon-decoupling D-nite, not algebraic not D-algebraic

H

  p (w; t) := [w ≥0 ]I(w; t) p .

Figure 9 .

 9 Figure 9. A chart showing how to determine the complexity of the series Q j (x, y; t) counting walks starting at (p, q) conned to an M -quadrant cone as a series in x (or y) as proven by Theorems 6.2-6.9. Recall that L determines which M quadrants are used to dene the M -quadrant cone.

Finally, perhaps the

  most mysterious result of this article is Corollary 4.19, relating to walks starting on an axis. The statement of this Corollary is purely combinatorial, yet it's proof in this article is far from combinatorial. this leads to the natural question of nding a bijection: Question 6. Find a bijective proof of Corollary 4.19. If this can be done, is there a directly combinatorial way to prove Theorem 4.18? and for s ∈ Z,ω 1 + D s = D s ,(89)(s + 1)ω 2 + ω 3 -D 2s ∪ D 2s+1 = D 2s ∪ D 2s+1 ⊃ (s + 1)ω 2 + ω 3 2 + iR,(90)(s + 1)ω 2 -D 2s ∪ D 2s-1 = D 2s ∪ D 2s-1 ⊃ (s + 1)ω 2 2 + iR.

  D x = {(x, y) ∈ E t : |x| < 1}, D y = {(x, y) ∈ E t : |y| < 1} and D = D x ∪ D y . Moreover in Lemma 2.8 they show that these sets are connected.Next, writing Λ(ω) := (x(ω), y(ω)), as the homeomorphism from C/(Zω 1 + Zω 2 ) to E t and Λ being the corresponding function with domain C, they dene D to be a connected component of the set Λ-1 (D). Their only other condition on D is that it intersects the fundamental parallelogram ω 1 [0, 1) + ω 2 [0, 1). Since we know ω2 2 is in this parallelogram and |x( ω22 )| < 1,

  x , we have |x(ω)| = 1 and |y(ω)| > 1 while for ω ∈ Γ- x , we have |x(ω)| = 1 and |y(ω)| < 1 • For ω ∈ Γ+ y , we have |y(ω)| = 1 and |x(ω)| > 1 while for ω ∈ Γ- y , we have |y(ω)| = 1 and |x(ω)| < 1 • The paths Γ+

2 ∈ D - 1 ∪ 2 )| < 1 , so ω2+ω3 2 ∈

 21212 D 0 ∪ D 1 ∪ D 2 . Now, we know from Lemma A.2 that |y( ω2+ω3 D 0 ∪ D 1 = D y , as required.

  + nω 3 )

A 1

 1 (z) ≡ A(z) := ϑ (z, τ ) ϑ(z, τ ) , which satises A(z) = A(z + π) = A(z + πτ ) + 2iand the only poles of A(z) are the points of the lattice πZ + πτ Z, and at each such point q we have A(z) ∼ 1 z -q .

N

  n=-N b(z + nω 3 )

  k,j A j (z -q k -nω 3 ) has poles at exactly the same points as g, and they are of the same nature, so b(z) -b(z) has no poles. Moreover b(z + π) = b(z) and b(z+πτ )-b(z) =

  -2is n,k,1 = 0.Hence b(z) -b(z) is an elliptic function with no poles, so it must be constant. Hence for some c ∈ C we have b(z) = b(z) + c. Now that we have a explicit form for b(z), we are almost ready to construct a 1 and a 2 . First we dene an auxiliary functionp(z) := s n,k,j A j (z -q k -mω 3 ), as then p(z + ω 3 ) -p(z) = s n,k,j A j (z -q k -(m -1)ω 3 ) -n m=-Ns n,k,j A j (z -q k -mω 3 )

a 1 ( 2 = 2 = 2 =

 1222 γ 1 -z) -a 1 (z) = h(γ 1 -z) -a 2 (γ 1 -z) -h(z) + a 2 (z) = -b(z) + p(z) + p(γ 2 -z) -p(γ 1 -z) -p(γ 2 -γ 1 + z) -b(z) + p(z) + p(ω 3 + γ 1 -z) -p(γ 1 -z) -p(ω 3 + z) -b(z) + b(z) -b(γ 1 -z) -b(z) -b(γ 1 -z) 2 = -h(z) + h(γ 1 -z) -h(γ 1 -z) + h(z) 2 = 0.

Table 2 .

 2 Complexity of Q(x, y; t) and C(x, y; t) as functions of x as proven more precisely by Theorems 4.1-4.7.

  Since each G(x k , y; t) can be considered to be a series in C[y][[t]], this determinant, which we denote by T (y; t) is in general a series in C[y][[t]].

	has determinant 0.
							
	. . .	. . .	. . .	. . .	. . .	y, t)	     

1 Λ 0 (x n+1 , y, t) Λ 1 (x n+1 , y, t) • • • Λ n (x n+1 , y, t)

  1 w [[t]], so H p (w; t) = [w ≥0 ]I(w; t) p lies in R[[t]][w] and has degree p as a polynomial in w. Hence

		F p (t) = H p (0; t) ∈ R[[t]]			and
	A p	1 y	; t = H p W A	1 y	; t ; t -H p (0; t) ∈	1 y	Z	1 y	[[t]],
	Because W A 1 y ; t ∈ 1 y Z 1 y [[t]]. So (37) and (38) hold. Moreover, [w <0 ]I(w; t) p ∈ 1 w Z 1 w [[t]],
	so B p 1 x ; t ∈ 1 x Z 1 x [[t]]. Finally, (39) holds because
			B p	1 x	; t + H p W B	1 x	; t ; t = I W B	1 x	; t ; t

p = x p .

  Proposition 4.22. If C(x, y; t) is D-nite with respect to x, then L(x, y; t) is also D-nite with respect to x. Moreover, in this case, C(x, y; t) is algebraic if and only if L(x, y; t) is algebraic as functions of x. Proof. Assuming that C(x, y; t) is D-nite in x, we have γ πτ ∈ Q. Since the walks counted by C(x, y; t) start on an axis, C(x, y; t) is algebraic in x. Hence by the (42), L(x, y; t) is D-nite in x. moreover, L(x, y; t) is algebraic in x if and only if C(x, y; t) is algebraic in x. Proposition 4.23. C(x, y; t) is D-algebraic with respect to x if and only if L(x, y; t) is D-algebraic with respect to x. Proof. The case where C(x, y; t) is D-nite with respect to x is covered by 4.22. So we are left with the case where C(x, y; t) is not D-nite in x, that is γ πτ / ∈ Q. Since the walks counted by C(x, y; t) start on an axis, C(x, y; t) is D-algebraic in x. Hence by the (42), L(x, y; t) is D-algebraic in x if and only if C(x, y; t) is D-algebraic in x. Proposition 4.24. If C(x, y; t) is D-nite with respect to x, then M(x, y; t) is also D-nite with respect to x. Moreover, in this case, C(x, y; t) is algebraic if and only if M(x, y; t) is algebraic as functions of x. Proof. Using 4.22, we know that L(x, y; t) is D-nite, and that it is algebraic if an only if C(x, y; t) is algebraic. Then using the same argument starting with L(x, y; t) and forbidding the step from (1, 0) to (0, 1), we can prove that M(x, y; t) is D-nite and that it is algebraic if and only if L(x, y; t) is algebraic. Proposition 4.25. C(x, y; t) is D-algebraic with respect to x if and only if M(x, y; t) is Dalgebraic with respect to x. Proof. Using 4.23, we know that L(x, y; t) is D-algebraic if and only if M(x, y; t) is D-algebraic.

  • D 4s-1 = Dx \ Dy + sω 2 , which is delimited by a left boundary Γ+ x + sω 2 (not included in D 4s-1 ) and a right boundary Γ- y + sω 2 (included in D 4s-1 ), • D 4s = Dx ∩ Dy + sω 2 , which is delimited by a left boundary Γ- y + sω 2 and a right boundary Γ- x + sω 2 , • D 4s+1 = Dy \ Dx + sω 2 , which is delimited by a left boundary Γ- x + sω 2 (included in D 4s+1 ) and a right boundary Γ+ y + sω 2 , • D 4s+2 is the closed set delimited by a left boundary Γ+ y + sω 2 and a right boundaryΓ+ x + (s + 1)ω 2 .It is clear from these denitions that these sets partition C. Moreover, since the paths Γ ±x and Γ ± y are ω 1 -periodic, we know that Dy is also ω 1 -periodic, that is, (89) holds. Now, to prove equations (85)-(88), note that since D y is connected, we must have Λ( Dy ) = D y , soΛ-1 (D y ) = Dy + Zω 1 + Zω 2 ,since Λ is a bijection from C/(Zω 1 + Zω 2 ) to E t . Hence, using (89), we have Λ-1 (D y ) = Dy + Zω 2 .

Acknowledgements. We are grateful to Kilian Raschel for suggesting that we consider the special case where walks start on an axis, as this led us to some interesting results. We also thank Mireille Bousquet-Mélou for many helpful suggestions on an early version of this article.

It will be convenient to write the series T j (x, y; t), S j,j+1 (x, y; t) and S j+1,j (x, y; t) in terms of series involving only 1 or none of the variables x, y. To do this we dene F j (t) = [x 0 y 0 ]T j (x, y; t),

-L y 0 -L ]T -L (x, y; t), U 1 (t) = [x 1 -L y 0 -L ]T 1-L (x, y; t), U 2 (y K ; t) = [x 0 K y ≥1 K ]T K (x, y; t), R j (x j ; t) = x -1 j S j-1,j (x, y; t),

L j (y j ; t) = x -1 j S j+1,j (x, y; t) + δ j,-L U 1 (t),

(44) Then from Lemma 5.5, we have in all cases T j (x, y; t) = F j (t) + δ j,-L U 0 (x -L ; t) + δ j,1-L x -L U 1 (t) + δ j,K U 2 (y K ; t) (45) and

Lemma 5.6. The series Q j (x, y; t) and T j (x, y; t) satisfy the equations K(x, y; t)Q j (x, y; t) = -δ 0,j x p y q -S j+1,j (x, y; t) + S j,j+1 (x, y; t) -S j-1,j (x, y; t) + S j,j-1 (x, y; t) + T j (x, y; t), (46) Proof. All non-trivial walks ending in Γj are counted by exactly one of S j-1,j (x, y; t), S j,j (x, y; t) and S j+1,j (x, y; t), depending on the position of the point before the nal step. the contribution of the trivial walk is x p y q , and this only contributes if j = 0. Hence we have Q j (x, y; t) = δ 0,j x p y q + S j-1,j (x, y; t) + S j,j (x, y; t) + S j+1,j (x, y; t). Now we consider non-trivial walks whose last step starts within Γj . These can be counted using the generating function Q j (x, y; t) and multiplying by tP (x, y) to account for the addition of a single arbitrary step. Alternatively we can observe that each of these walks contributes to exactly one of S j,j-1 (x, y; t), S j,j (x, y; t), S j,j+1 (x, y; t) and T j (x, y; t). This yields the equation tP(x, y)Q j (x, y; t) = S j,j-1 (x, y; t) + S j,j (x, y; t) + S j,j+1 (x, y; t) + T j (x, y; t).

Taking the dierence between these to cancel the term S j,j yields (46). Lemma 5.7. Dene the series A(x -L ; t) and B(y K ; t) by A(x -L ; t) := U 0 (x -L ; t) + x -L U 1 (t), (47) B(y K ; t) := U 2 (y K ; t).

(48) If M ≥ 2 then the series A(x -L ) and B(y K ) satisfy the equations K(x, y)Q j (x, y) = -δ j,0 x p y q -x j L j (y j ) + y j R j+1 (y j )

K(x, y)Q -L (x, y) = -δ -L,0 x p y q -x -L L -L (y -L ) + y -L R -L+1 (y -L ) + A(x -L ) + F -L , (50)

(51) If M = 1 the series A(x 0 ) and B(y 0 ) satisfy the equation K(x, y)Q 0 (x, y) = -x p y q + A(x 0 ) + B(x 0 ) + F 0 , (52) Moreover, in either case, A(x -L ; t) ∈ R[x -L ][[t]] and B(y

Proof. First, (49), (50) and (51) result from expanding (46) for dierent values of j using (45), and using (43) and (44) to write S in terms of R and L. The equation (52) follows from (46) at j = 0, as in this case there is only one quadrant so the series S j,k = 0 (since j, k are not both 0) and we have T 0 (x, y; t) = A(x 0 ; t) + B(x 0 ; t) + F 0 (t). As stated just below (45), we Proposition 5.10. Dene the functions V j (z), A(z), B(z) and constants F j by V j (z) := X j (z)L j (Y j (z); t) -Y j (z)R j+1 (Y j (z); t),

A(z) := A(X -L (z); t),

(56)

These functions are well dened. Moreover, they satisfy the equations

Proof. We start by showing that the functions are well dened and meromorphic on the domains on which they are dened. It suces to show that the series dening the functions convergent absolutely. The series x j Lj (y j ; t), x j Rj (x j ; t), A(x -L ; t), B(y K ; t) and F j (t) all count some subset of (weighted) walks in the plane starting a certain point (p, q). Since the total weighted number of walks of length t is P (1, 1) n , all series must converge absolutely when |x| = |y| = 1 and t ∈ 0, 1 P(1,1) . Hence the series dening (53) and (55) converge absolutely, as |Y j (z)| ≤ 1 for z ∈ Ω j ∪ Ω j+1 , while the series dening (54) also converges absolutely because |X j (z)| ≤ 1 for z ∈ Ω j ∪Ω j-1 . Now, (57), ( 58) and (59) follow from from substituting (x, y) → (X(z), Y (z)) into (49), (50) and (51) respectively. (60) follows from from substituting (x, y) → (X(z), Y (z)) into (52). Finally, (61) holds because, by Proposition 3.2,

Theorem 5.11. The functions A(z), B(z) extend to meromorphic functions on C which, along with the constant

are characterised by the equations

along with the conditions (i) A(z) has no poles in Ω j for 0 ≥ j ≥ -L -1, (ii) A(z) has roots at the roots α -L and γ

Finally it remains to show that these conditions uniquely dene the functions A(z), B(z) and the constant F . Suppose that Â(z), B(z) and F is an arbitrary triple satisfying the same conditions. Then it suces to show that A(z) = Â(z) and B(z) = B(z). Then [START_REF] Fayolle | Two coupled processors: the reduction to a riemann-hilbert problem[END_REF] implies that the dierence

Moreover, the four conditions on A(z) and B(z) imply, respectively, that (i) ∆(z) has no poles in

, the conditions (i) and (iii) imply that ∆(z) is an elliptic function with no poles, so it is constant. Moreover, condition (iv) implies that ∆(z) does have roots, so ∆(z) is the 0 function. Condition (ii) then implies that F = F . Together with the denition of ∆ we have B(z) = B(z) and A(z) = Â(z), as required.

For convenience we will dene τ = γ K -γ -L-1 . Note that combining (63), (64), (65) yields

where J(z) is an elliptic function with periods π and πτ given by

(71) To complete this section, we show that the series L j (y j ; t) and R j (x j ; t) are uniquely determined by A(z) and B(z). Then the generating functions Q j (x, y; t) are determined by (49), ( 50) and (51). This justies our claim that Theorem 5.11 is a restatement of the problem, and it will allow us to determine the nature of the series Q j (x, y; t) in x and y in each case. Proposition 5.12. Dene s j = 1 for j > 0 and s j = 0 for j ≤ 0. The series L j (y j ) and R j+1 (y j ) ∈ R[[y j ]] are determined from A(z) using the following equations

where

is an explicit constant.

Proof. Combining (57) and (58) yields (72). Furthermore, we know that

for z ∈ Ω j ∪ Ω j+1 . Now, from Proposition 5.9, we have Ω j ∪ Ω j+1 = γ j -Ω j ∪ Ω j+1 and Y j (γ j -z) = Y j (z), so substituting z → γ j -z into the equation above yields

Combining these two equations to solve for L j (Y j (z)) and R j+1 (Y j (z)) yields (73) and (74).

Finally, it remains to determine the constant c j . We note that R j+1 (Y j (z)) must converge for z ∈ Ω j ∪ Ω j+1 , in particular at z = β j . But Y j (β j ) = 0, so the numerator of (74) must also be 0, that is,

Finite group cases

Dene τ := γ K -γ -L-1 π . In this section, we consider the cases in which τ τ ∈ Q. We will show that this occurs for xed t if and only if Q j (x, y; t) is D-nite in x. We will also show that the nature of this restriction depends on the parity of M : If M is even then we always have τ τ ∈ Q, while if M is odd then τ τ ∈ Q if and only if γ πτ ∈ Q. We also describe precisely in which cases Q j (x, y; t) is algebraic in x. Theorem 6.10.

Moreover, under this assumption Q j (x, y) is algebraic in x if and only if the function

N2 πτ for some positive N 1 , N 2 ∈ Z. Now consider (70):

Taking a telescoping sum of N 2 copies of this equation yields

We will now consider the cases Ẽ(z) = 0 and Ẽ(z) = 0 separately. In the case that Ẽ(z) = 0, we

Hence condition (v) of Theorem 6.6 holds, so the equivalent conditions are satised, including that C(x, y) is algebraic in x.

Finally we consider the case Ẽ(z) = 0. Then from (76), we have

so the function

satises

) is weakly X-D-nite (see Denition B.4), so by proposition B.8, it is X-D-nite and B( 1x ) is D-nite in x, which is equivalent to conditions (i) -(iv) of Theorem 6.4 (most clearly (iv)). Therefore the generating function

Finally we show that in this Ẽ(z) = 0 case, C(x, y) is not algebraic in x. Suppose the contrary, then condition (v) of Theorem 6.6 holds, that is mπτ is a period of B(z) for some positive integer m. But this is impossible as by (77),

To nish the proof of Theorem 6.4, we need the following Lemma, which specically relates to the case when M is odd. We note that the Lemma below implies that for M odd, the value of N 2 in this section is the same as the value N used in Section 4.1. Lemma 6.11.

Replacing j by N -1 -j in the rst sum and N -j in the second sum yields

Lemma 6.14. If M ≥ 2 is even, then Ẽ(z) is the zero function if and only if q = 0 and L is even.

Proof. Assume M is even. From Lemma 6.12, we know that

In the case that L is even, we have

So we see immediately that if q = 0, then J(z) = 0. It remains to prove the converse. So, assume for the sake of contradiction that q = 0 but J(z) = 0 for all z. then we have

In the rst case 2γ is a period of Y which is impossible because 0 < (2γ) < (πτ ) by Lemma 2.3. So we are left with the case Y (z) = -Y (-γ -z). Now, to compare Y (z) and Y (-γ -z) in a dierent way, we consider the equation yP(X(z), y) -y t = 0, which is a quadratic equation in y with solutions y = Y (z) and y = Y (-γ -z). So, dening

we have

But in this case

which is impossible because A 0 (x) has no constant term. Finally we consider the remaining case where L is odd, so γ -L-1 = γ -L+1 2 πτ . It remains to prove that J(z) is not the zero function in this case. We have

so J(z) = 0 if and only if X(γ -z) p = X(z) p . Now, recall that in our model the starting point (p, q) must satisfy p > 0, so similarly to the previous case for Y (z), it follows that X(γ-z) = X(z) or X(γ -z) = -X(z). In the former case 2γ is a period of X, which is a contradiction since 0 < 2γ < πτ . and in the latter case we get a similar contradiction to before: 2 , which is a contradiction because the left hand side of xP(x, Y (z)) -x t has a linear term equal to w (0,1) Y (z) + w (0,-1) Y (z) -1 -1 t , which cannot be identically 0, whereas the right hand side has no linear term.

Infinite group cases

In this entire section we assume that M is odd, as the cases for M even were all handled in the previous section.

In this section we consider the case γ πτ / ∈ Q. the rst part of this section is dedicated to showing that C(x, y; t) is not D-nite in x in these cases, and we will subsequently analyse the D-algebraicity of C(x, y; t). We start with a lemma which essentially proves A H ( 1 x ; t) is not rational in x, as this turns out to be a case which needs to be treated separately. Surprising this seems to be the most dicult result of this section, in the sense that it is the only result for which our proof does not apply systematically to walks in an M -quadrant cone for any M . In particular, for walks in the quadrant we have only able to prove the result when t is suciently small (See Lemma 6.16). Lemma 6.15. Assume that γ πτ / ∈ Q and M ≥ 3 is odd. Then πτ is not a period of A(z) or B(z).

Proof. By (63), if either A(z) or B(z) has πτ as a period, then the other does as well. If L ≥ 2, then by Theorem 5.11, A(z) has no poles in Ω -3 ∪ Ω -2 ∪ Ω -1 ∪ Ω 0 . Together with the fact that πτ is a period of A(z), this implies that A has no poles at all, so it is a constant function, which will quickly lead to a contradiction. Indeed, using Theorem 5.11, this implies that X(z) p Y (z) q is xed under the shift z → γ K -z, which also xes either X(z) or Y (z), depending on the value of γ K . So, either X(z

We will assume the former as the two cases can be handled similarly.

But this is impossible as the border between Ω 1 and Ω 2 is sent to the border between Ω -1 and Ω 0 by the transformation z → γ -z, and |X(z)| > 1 on the rst of these lines while |X(z)| < 1 on the other line.

Similarly, if

, so it is constant and we get a similar contradiction.

Finally we are left with the cases where K ≤ 1 and L ≤ 1. Since K + L + 1 = M ≥ 3, the only remaining case is K = L = 1 and M = 3. This is exactly the three-quadrant cone case covered by 4.12, so this completes the proof.

In the following lemma we prove a slightly weaker result for M = 1. We suspect that the more general result above applies for M = 1, but we have not been able to prove it. Lemma 6.16. Assume that the group is not nite and that M = 1 (the quadrant case). For all suciently small t satisfying γ πτ / ∈ Q, the function A(z) does not have πτ as a period. Proof. Assume for the sake of contradiction that A(z) has πτ as a period. Then by (63), B(z) also has πτ as a period. Moreover, since we are in the case M = 1, there is only one quadrant which does not include the axes, so the starting point (p, q) of the walk cannot be on either axis. Hence p, q ≥ 1. Moreover, K = L = 0, so from Theorem 5.11, A(z) = A(-γ -z) and

Proof of Claim 1: For z 0 ∈ Ω -1 ∪ Ω 0 , we know that this result holds as it is the denition of A(z 0 ) in this region. Moreover, this extends analytically to the connected component of X -1 (D t ) containing Ω 0 ∪ Ω -1 as we know from Lemma 2.4 that A(X(z 0 ); t) converges for

Hence to complete the proof of claim 1 it suces to prove that every connected component Γ of X -1 (D t ) contains one of the sets Ω 4m ∪ Ω 4m-1 . Assume Γ is such a connected component. Then, since D t is an open set, Γ must also be an open set, so by the open mapping theorem X(Γ) is an open Proof. Suppose the contrary. Then Q j (x, y; t) is D-nite, so by Lemma 6.1, B(z) is X-D-nite in z (see Denition B.3). Then by Lemma B.9, the poles z c of B(z) fall into only nitely many classes z c + πZ + πτ Z. Hence B(πτ + z) -B(z) has the same property. Now, from (70), we have

and rearranging yields

This implies that B(πτ + z) -B(z) is an elliptic function with periods π and πτ . If this function has a pole z 0 , then for every k ∈ Z, the value zk = z 0 + kπτ is a pole. This is a contradiction as these points all dene dierent classes z k + πτ Z + πZ, since τ τ ∈ R \ Q. The only remaining case to consider is when B(πτ + z) -B(z) has no poles, in which case it must be constant:

In fact combining this with (64), we see that c = 0, as

But this contradicts the assumption that πτ is not a period of B(z). Corollary 6.18. If M ≥ 3 is odd and

Proof. By Lemma 6.15, πτ cannot be a period of B(z) for M ≥ 3. Moreover, if γ πτ / ∈ Q, then by Lemma 6.11, τ τ / ∈ Q so by Theorem 6.17, Q j (x, y; t) is not D-nite in x. Corollary 6.19. If M = 1, and the group of the walk is not nite, then there are values of t for which Q j (x, y; t) is not D-nite in x.

Proof. Since the group of the walk is not nite, there are arbitrarily small values of t satisfying γ πτ / ∈ Q. Hence, for suciently small such t, Lemma 6.16 implies that πτ is not a period of B(z). Therefore, by Theorem 6.17, these are values of t for which Q j (x, y; t) is not D-nite in x.

6.2.1. Decoupling cases. Recall from Denition 4.8 that we say that X(z) p Y (z) q is decoupling if there is a pair of rational functions R 1 and R 2 satisfying

As we will show in the following theorem, this implies that Q j (x, y; t) is D-algebraic in x and y. The analogous result was proven in the quarter plane by Bernardi, Bousquet-Mélou and Raschel [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF], and more precisely they proved that Q j (x, y; t) is D-algebraic in t under the same condition. This results from the fact that all of the parameters that depend on t and all of the functions involved in the solution depend on t in a D-algebraic way. We believe that the same argument applies here, although a rigorous proof of this is outside the scope of this article. Theorem 6.20. Assume that

holds for some rational functions R 1 and R 2 . Then Q j (x, y; t) is D-algebraic in x and y.

Proof. Since M = L + K + 1 is odd, L and K have the same parity. If they are both even then

, so either way we can write

where R1 and R2 are rational functions. Under the assumption, (63) can be written as

Appendix A. Parameterisation of the Kernel curve In this appendix, we describe a parameterisation of the Kernel curve, which we transform to prove Lemmas 2.3 and 2.5. the parameterisation was rst given by Raschel in [START_REF] Raschel | Counting walks in a quadrant: a unied approach via boundary value problems[END_REF] but we follow [15, Section 2] as they prove more results relevant to us. In this section they work under the same assumption on the step set as us -that the step-set is non-singular. They also assume that the sum of the weights w i,j is 1 and that t < 1, but by linearly rescaling t and the weights w i,j (and hence K(x, y)), this becomes equivalent to our assumption

without changing the set

We start with the parameterisation of E t given by Dreyfus and Raschel [15, Proposition 2.1] for x and (2.16) of the same article for y. These parameterisations involve the Weierstrass ℘ function

To dene the parameterisation, they start by dening rational functions A -1 (x), A 0 (x) and A 1 (x) by P(x, y) =:

and the degree 4 (or 3) polynomial

(see (1.1),(1.8) and (1.10)). By Theorem 1.11, the polynomial D(x) has 3 real roots a 1 , a 2 , a 3 satisfying -1 < a 1 < a 2 < 1 < a 3 < ∞. If D(x) has degree 4, it has a fourth root a 4 ∈ (a 3 , ∞) ∪ (-∞, -1), while in the case that D(x) only has degree 3 we take a 4 = ∞. The polynomial E(y) = 4 j=0 β j y j and its roots b 1 , b 2 , b 3 and b 4 are dened similarly by swapping the roles of x and y.

The following is proposition 2.1 in [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF], using the expression (2.16) for y(ω).

Proposition A.1. The curve E t admits a uniformisation of the form

where x(ω) is given by

and y(ω) is given by

where ω 1 ∈ iR and ω 2 , ω 3 ∈ R are given by

where K(x 4 , b 4 ) = 0. when the integrals above take the form b a with a > b, they are dened as

This is related to the parameterisation in Lemma 2.3 by

Under these transformations, and writing ω = ω2 2 + ω3 4 -ω1 π z, Lemma 2.3 is equivalent to the following lemma Lemma A.2. The numbers ω 1 ∈ iR and ω 2 , ω 3 ∈ R satisfy (-ω 2 /ω 1 ) > (-ω 3 /ω 1 ) > 0. Moreover, the meromorphic functions x(ω), y(ω) :

Counting with multiplicity, the functions x(ω) and y(ω) each contain two poles and two roots in each fundamental domain {z c -r 1 ω 1 + r 2 ω 2 : r 1 , r 2 ∈ [0, 1)}. Moreover, x(ω) and y(ω) are dierentially algebraic with respect to ω and t, while ω2 ω1 and ω3 ω1 are dierentially algebraic as functions of t.

Proof. The fact that (-ω 2 /ω 1 ) > (-ω 3 /ω 1 ) > 0 follows immediately from ω1 i > 0 and 0 < ω 3 < ω 2 , which is proven in Lemma 2.6 in [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF].

The condition (i) is part of the statement of Proposition A.1. The claims (ii) and (iii) follow from the denitions of x(ω) and y(ω) and the fact that

From Lemma 2.3 in [START_REF] Dreyfus | Dierential transcendence & algebraicity criteria for the series counting weighted quadrant walks[END_REF], we have x( ω22 ) = a 1 and y( ω2+ω3

Finally, (v) follows from the denitions of x(ω) and y(ω) as it is a well known property of the Weierstrass function ℘ that it takes each value in C∪∞ exactly twice (counting with multiplicity) in each fundamental domain.

nally we will show that all terms in the expression are D-algebraic both as functions of ω and t. This follows from results of [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF], in particular their Proposition 6.7 shows that ℘ is D-algebraic in all of it's variables, while their Lemma 6.10 shows that ω 1 , ω 2 and ω 3 are even D-nite in t.

So, we have now proven Lemma 2.3. Similarly, Lemma 2.5 is equivalent to the Lemma below, with Ω s := π ω1 ω3

-D s

Lemma A.3. The complex plane can be partitioned into simply connected regions

where S(z) and each S j (z) is an elliptic function with periods π and πτ , and S j (z) is not the zero function.

We will show that this is also equivalent to the following, seemingly weaker property: Denition B.4. We say that the function f : C → C ∪ {∞} is weakly X-D-nite if it satises an equation of the form

where S(z) and each S j (z) is an elliptic function with periods π and mπτ , for some m ∈ Z \ {0} and S j (z) is not the zero function. Denition B.5. We say that the function

for all z ∈ C, so f (z) is X-rational due to the fact that

For the converse, consider the transformation of ℘ that denes X(z) and Y (z) given in Appendix A. Under this transformation, this Proposition is equivalent to the classical result that any even elliptic function is a rational function of the Weierstrass function ℘ with the same periods (see e.g., [1, page 44]). Alternatively one could prove this directly by constructing a rational function of X(z) with poles at the same points and of the same nature as those of f (z), thereby proving that f (z) is this rational function of X(z).

Remark: An equivalent argument shows that a function h(z) is a rational function of W (z) (see Denition 3.1) if and only if

Proof. If f (z) is X-algebraic then there is a positive integer m, such that f (z) and X(z) share the periods π and mπτ . Hence A(x) is algebraic due to the classical result that any two elliptic functions with the same periods are related by some non-trivial polynomial equation

For the converse, assume that A(x) is algebraic. Then there is some non-polynomial P satisfying P (A(x), x) = 0, and hence P (f (z), X(z)) = 0 for z ∈ Λ, and by meromorphic extension we must have P (f (z), X(z)) = 0 for all z ∈ C. There can only be nitely many values z c ∈ [0, π) satisfying P (a, X(z c )) = 0 for all a, and for all the rest, there can only be nitely many values of a satisfying P (a, X(z c )) = 0, so f (z) takes only nitely many values for z ∈ z c + πτ Z. Hence for each z c there are some

Moreover, since there are only countably many choices for m 1 , m 2 , there must be innitely many values z c corresponding to the same pair m 1 , m 2 . Hence f (z + m 1 πτ ) -f (z + m 2 πτ ) = 0 for innitely many values z ∈ [0, π), and hence innitely many dierent values X(z). Moreover, both f (z + m 1 πτ ) and f (z + m 2 πτ ) are algebraic functions of X(z) (as the both satisfy P (f (z + m j πτ ), X(z)) = 0), so f (z + m 1 πτ ) -f (z + m 2 πτ ) is an algebraic function of X(z) with innitely many roots, so it must be the 0 function. Hence f (z + m 1 πτ ) = f (z + m 2 πτ ), so setting m = m 1 -m 2 yields the desired result.

Remark: Similarly B(y) is algebraic if and only if g(z) = B(Y (z)) satises the exact same condition.

Proposition B.8. The following are equivalent:

nite then it is weakly X-D-nite. We will now assume that f (z) is weakly X-D-nite and prove that A(x) is D-nite. We have

Considering this equation for z ∈ Λ, where f (z) = A(X(z)), we can apply the chain rule to write

where each T j (z) is a rational function of X(z) and its derivatives, with T k (z) = X (z) k = 0. In particular, each T j (z) is an elliptic function with periods π and πτ , so we have a new equation

where S(z) and each U j (z) is an elliptic function with periods π and mπτ , and

Moreover since U j and S have π and mπτ as periods, the functions S(x) and U j (x) are algebraic by Proposition B.7. Now for x ∈ ∆, we have

So A(x) satises a non-trivial linear dierential equation with coecients algebraic in x. It is a classical result that the existence of such an equation implies the existence of a linear dierential equation (see, for example, [START_REF] Poincaré | Mémoire sur les fonctions zéta fuchsiennes[END_REF][START_REF] Schmidt | Rational approximation to solutions of linear dierential equations with algebraic coecients[END_REF]), so A(x) is D-nite.

For the nal implication, we assume that A(x) is D-nite and we will show that f (z) is X-D-nite. We can write

where each U j (x) is a polynomial, with

Moreover, since the expression on the left hand side is meromorphic on C, the equation must hold on all of C. Using the product rule yields an equation of the form described in Denition B.3, so f (z) is X-D-nite.

Remark: Similarly

Below we prove a simple consequence of the Lemma above regarding the possible positions of poles of such a function f (z). This will be useful for proving that certain series are not D-nite. Lemma B.9. If f (z) is X-D-nite, then its poles fall into only nitely many classes z c + πZ + πτ Z.

Proof. From Proposition B.8 we can write

where S(z) and each S j (z) is an elliptic function with periods π and πτ , and S j (z) is not the zero function.

We will start by showing that any pole z c of f (z) is either a root of S n (z) or a pole of one of the functions S j (z) or S(z). Let z c be a pole of f (z) and let k be the order of the pole z c of f (z). If z c is not a root or pole of S n (z) then f (n) (z)S n (z) has a pole at z = z c of order k + n. If, in addition, z c is not a pole of any of the functions S j (z), then each term f (j) (z)S j (z) for j < n has a pole at z = z c of order at most k + j < k + n. Hence the entire sum has a pole of order k + n at z = z c , which is impossible as the sum is 0.

Hence, any pole z c of f (z) is either a root of S n (z) or a pole of one of the functions S j (z) or S(z). But each of these functions is an elliptic function with periods π and πτ , so the poles and roots fall into nitely many classes z c + πZ + πτ Z. Hence, the poles of f (z) fall into only nitely many classes.

Proposition B.10. The function A(x) is D-algebraic if and only if f (z) = A(X(z)) is a Dalgebraic function of z, that is, if and only if f (z) is X-D-algebraic. Proof. Since D-algebraic functions are closed under function composition and taking inverses, it suces to prove that X(z) is a D-algebraic function. Indeed X (z) and X(z) are elliptic functions with the same periods, so they are related by some non-trivial polynomial equation P (X(z), X (z)) = 0. This is a non-trivial dierential algebraic equation satised by X(z).

Remark: Similarly

Finally we have the main result of this appendix:

Proposition B.11. If P is one of the properties rational, algebraic, D-nite or D-algebraic, then A(x) satises the property P if and only if f (z) = A(X(z)) satises the property X-P.

Proof. The result is a combination of Propositions B.6, B.7, B.8 and B.10. Proposition B.12. Let P be one of the properties Algebraic, D-nite or D-Algebraic. If f, g : C → C ∪ {∞} are functions, each with π as a period, which have the property X-P then the functions f (z)g(z), f (z) + g(z) and f (c -z) also have the property X-P for any c ∈ C. Proof. We rst prove that X-P is closed under addition and multiplication, that is that f (z)g(z)

and f (z)+g(z) satisfy the property X-P. As we will show this is due to the fact that the property P is closed under addition and multiplication. Let ∆ ∈ C be a non-empty open set on which X is injective, then dene f 1 , g 1 : X(∆) → C∪∞ by f 1 (x) = f (X -1 (x)) and g 1 (x) = g(X -1 (x)), where we take the inverse X -1 (x) ∈ ∆. Then from Proposition B.11, our assumption that f and g satisfy X-P implies that f 1 and g 1 satisfy P. Then since P is closed under addition and multiplication of functions, this implies that f 1 (x) + g 1 (x) and f 1 (x)g 1 (x) satisfy P. Then since f (z) + g(z) = f 1 (X(z)) + g 1 (X(z)) and f (z)g(z) = f 1 (X(z))g 1 (X(z)) for z ∈ ∆, it follows from Proposition B.11 that these functions satisfy X-P.

Finally we will show that f (c -z) satises X-P. This follows directly from the denition of X-P, so we do it separately for each property P. If f (z) is X-algebraic it has mπτ as a period for some integer m, so f (c -z) also has mπτ as a period, which means it is X-algebraic, as required. If f (z) is X-D-algebraic then it is D-algebraic, so f (c -z) is also D-algebraic, which means it is X-D-algebraic, as required. nally, if f (z) is X-D-nite, then it satises an equation of the form

which has the same form. So f (c -z) is X-D-nite, as required.

Appendix C. Group of the walk In this appendix we will discuss the group of the walk, which was introduced in [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF] and is a variant on a group dened on analytic functions, previously introduced in the study of random walks in the quadrant [START_REF] Fayolle | Random walks in the quarter-plane[END_REF][START_REF] Vadim | An analytical method in the theory of two-dimensional positive random walks[END_REF]. In fact the original analytic version of this group is closer to the version we use in Section 4.1.

As in Appendix A, we dene Laurent polynomials

Then we dene transformations ψ and ϕ by

as then P(x, y) = P(ψ(x, y)) = P(ϕ(x, y)), so the Kernel K(x, y) = tP(x, y) -1 satises similar equations

Denition C.1. The group of the walk is dened as the group generated by the transformations ψ and ϕ.

It has been shown that for unweighted walks in the quarter plane, the group is nite if and only if the generating function Q(x, y; t) is D-nite [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF][START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]. Under the parametrisation (x, y) → (X(z), Y (z)), the transformations ψ and ϕ are equivalent to z → -γ -z and z → γ -z respectively, in the sense that

(93) To prove, for example, the rst of these equations, it suces to observe that Y (-γ -z) is the unique point other than Y (z) satisfying K(X(z), Y (-γ -z)) = 0, noting that the only cases where Y (-γ -z) = Y (z) are those in which y = Y (z) is a double root of K(X(z), y) and γ

This allows us to prove the following proposition:

Proposition C.2. For n ∈ N, we have 2nγ πτ ∈ Z if and only if the transformation (ψ • ϕ) n xes every element (x, y) ∈ E t . Proof. Applying equations ( 92) and (93), we see that

Hence, if 2nγ

πτ ∈ Z, then (ψ • ϕ) n xes every element (X(z), Y (z)), and hence every element of

Conversely, if (ψ • ϕ) n xes every point (X(z), Y (z)) in E t , then X(z) = X(z -2nγ) for all z, so 2nγ is a period of X. Hence 2nγ ∈ πτ Z + πZ. More precisely, since πτ and γ are both purely imaginary, this implies 2nγ ∈ πτ Z.

Proposition C.3. The group of the walk is nite if and only if γ πτ ∈ Q for all t ∈ 0, 1 P (1,1) .

Proof. If the group of the walk is nite, then let n be the order of the element (ψ • ϕ). By Proposition C.2, this implies that 2nγ πτ ∈ Z for all t, so γ πτ ∈ Q for all t. Conversely, if γ πτ ∈ Q for all t ∈ 0, 1 P (1,1) , then there is some integer n t for each t satisfying 2ntγ πτ ∈ Z. So by Proposition C.2, we have (ψ • ϕ) nt (x, y) = (x, y) for (x, y) ∈ E t . Now, since There is an integer n t for each of uncountably many values t, there must be some integer N such that N = n t for innitely many dierent values t. This implies that for each y, we have (ψ•ϕ) N (x, y) = (x, y) for innitely many values x. But, for xed y, the equation (ψ•ϕ) N (x, y) = (x, y) is two polynomial equations of x, so if it holds for innitely many values of x it must hold for all x. Hence (ψ • ϕ) N (x, y) = (x, y) for all x, y ∈ C, so the group is nite.

Appendix D. Differential transcendence criteria The purpose of this appendix is to present the following proposition, which is a restatement of results in [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF]. We will use this to prove that Certain generating functions are not dierentially algebraic in the cases where the group of the walk is innite and there is not a decoupling function. does not have a pole at q 0 , where q 0 +n 1 ω 3 , q 0 +n 2 ω 3 , . . . , q 0 +n k ω 3 are the poles of g in q 0 +ω 3 Z.

Proof. We will describe how this follows from Proposition 3.6 and Proposition B.2 from [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF].

We start by describing the application of [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF]Proposition 3.6]. In this proposition, the authors consider the triple (C(E t ), δ, τ ), as a sub-eld of (M(C), d dω , τ : ω → ω + ω 3 ), where E t is an arbitrary elliptic curve and M(C) denotes the meromorphic functions on C. In particular, C(E t ) corresponds to the elements of M(C) that are xed by two specied independent periods -we take these to be ω 1 and ω 2 . With this specication, [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF]Proposition 3.6] states that under precisely the conditions of this Proposition, there is a function g ∈ M(C) satisfying g(ω) = g(ω + ω 1 ) = g(ω + ω 2 ), an integer n ≥ 0 and c 0 , c 1 , . . . , c n-1 ∈ C satisfying In other words, there is a non-zero linear operator L ∈ C[ d dω ] satisfying L(b) = τ (g) -g. This means that b and g satisfy condition (1) of [13, Proposition B.2], and so they also satisfy condition [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF], which is equivalent to the following: For any pole q 0 of b, the function

does not have a pole at q 0 , where q 0 +n 1 ω 3 , q 0 +n 2 ω 3 , . . . , q 0 +n k ω 3 are the poles of g in q 0 +ω 3 Z.

We transform this into the following corollary, which allows us to quickly prove that when certain functions are D-algebraic in innite group cases there must be a decoupling function.