J Courtiel
email: courtiel@lipn.univ-paris13.fr

Stephen Melczer
email: smelczer@uwaterloo.ca

Marni Mishna
email: mmishna@sfu.ca

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

Weighted Lattice Walks and Universality Classes

Keywords: k, n

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Enumeration of walks in cones

In recent years many enumeration formulas for lattice walks in cones have been discovered. These results have focused largely on unweighted quadrant walks with small steps, and a wide variety of techniques have been developed and adapted to treat them [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF][START_REF] Fayolle | Some exact asymptotics in the counting of walks in the quarter plane[END_REF][START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF][START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF]. Ongoing works consider generalizations of this model, such as walks in higher dimensions [START_REF] Bostan | On 3-Dimensional Lattice Walks Confined to the Positive Octant[END_REF], walks with longer steps [START_REF] Fayolle | About a possible analytic approach for walks in the quarter plane with arbitrary big jumps[END_REF][START_REF] Bostan | Walks with large steps in the quadrant[END_REF], and walks with weights [START_REF] Feierl | Asymptotics for the number of walks in a Weyl chamber of type B[END_REF][START_REF] Kauers | Walks in the quarter plane with multiple steps[END_REF]. A lattice path model is comprised of a finite set of vectors, or steps, denoted S, and a cone in which the walks are contained, very often R 2 0 . An important quantity here is the drift of the model, which is the vector sum of the step set; in dimension two the drift is given by d = (s 1 ,s 2 )∈S (s 1 , s 2 ).

Early studies of walks on lattices [START_REF] Kreweras | Sur une classe de problémes liés au treillis des partitions d'entiers[END_REF][START_REF] Gessel | A probabilistic method for lattice path enumeration[END_REF] used ad hoc techniques, in the sense that the arguments presented were confined to a specific model or small collection of models. More recently, most analyses start from the multivariate generating function tracking the length of a walk and its end point. For some fixed cone and given model S, we define e (i,j)→(k, ) (n) to be the number of walks

The combinatorial decomposition of a walk into a shorter walk followed by a permissible step translates into a useful generating function equation. Several different approaches have been successfully applied to analyze this equation, including techniques from computer algebra, complex analytic methods, and skillful direct algebraic manipulation of the generating function equations.

Our main focus is on the asymptotic enumeration of these walks. Using probabilistic techniques, Denisov and Wachtel [START_REF] Denisov | Random walks in cones[END_REF] recently determined formulas for walks in general cones that can be adapted to determine asymptotic behaviour in the case of models with zero drift (that is, when each coordinate of the drift is zero). When the drift is non-zero, asymptotic estimates of the total number of walks are not known at the same level of generality, although there has been much recent activity for models in the quarter plane. Singularity analysis of generating function expressions has led to new results [START_REF] Fayolle | Some exact asymptotics in the counting of walks in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF], in addition to advances on the work of Denisov and Wachtel [START_REF] Denisov | Random walks in cones[END_REF][START_REF] Duraj | Random walks in cones: the case of nonzero drift[END_REF][START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF]. The techniques of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF] on analytic combinatorics in several variables, combined with expressions for walk generating functions as rational diagonals, have yielded explicit asymptotics for a large collection of models [START_REF] Melczer | Asymptotic lattice path enumeration using diagonals[END_REF][START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF], and we take a similar approach to weighted models in this work.

Weighted walks in cones

Given any (unweighted) model defined by a set of steps S, one can add weights associated to each step and ask what happens to asymptotic growth, the analytic or algebraic nature of the generating function, and other related questions. Formally, if we assign a weight a s 1 ,s 2 to each step (s 1 , s 2 ) belonging to a model S, then the weighted analogues of Equations ( 1) and (2) are Q a (x, y; t) = w walk starting at (0,0) ending at (k, ) of length n staying in the cone (s 1 ,s 2 ) step in w (with multiplicity)

a s 1 ,s 2 x k y t n , (3)
Q i,j a (x, y; t) = w walk starting at (i,j) ending at (k, ) of length n staying in the cone (s 1 ,s 2 ) step in w (with multiplicity)

a s 1 ,s 2 x k y t n . (4)
Generally speaking, assigning weights to steps enables a better understanding of the different types of model behaviour. In fact, by continuously varying these weights one can often illustrate sharp transitions (or phase changes) in asymptotic behaviour.

Initially, this framework-which is close to a probabilistic viewpoint [START_REF] Fayolle | Random walks in the quarter-plane[END_REF] in which the weights are interpreted as transition probabilities-does not force a restriction on any particular choice of weights. In order to obtain a detailed analysis, however, some restriction on the model weighting is currently necessary. Here we focus on central weights: by definition, a weighting is central if all paths with the same length, start and end points have the same weight. Uniformly weighting each step gives a central weighting, but non-trivial examples also exist. For instance, if we respectively assign the weights 1/a, a, b/a, a/b to the step set {(-1, 0), (1, 0), (-1, 1), (1, -1)}, as prescribed in Figure 1, then we have defined a central weighting. In Section 5 we show that every central weighting on this set of steps has this form, up to a uniform scaling of weights.

Central weightings have nice properties, including allowing one to express the generating function of a generic weighted model in terms of the generating function of the underlying unweighted model with weighted variables. Central weights are also related to the probabilistic notion of Cramér transform (which corresponds to an exponential change of measure).

Article structure

This article is organized into two parts. The first part is dedicated to the determination of exact asymptotic formulas for Gouyou-Beauchamps models (GB models for short) with central weightings. Our main result is Theorem 1, which we announce in the next section before considering some important consequences; Section 3 contains the proof of Theorem 1. Dominant asymptotic behaviour of a weighted GB model falls into one of several templates, depending on some simple relations between a and b. We group the weighted models into universality classes of models that share the same critical exponent. Figure 2 illustrates the universality classes as a function of the weight parameters.

Our results concerning general central weightings may be found in Part II, and can be summarized as follows.

(i) For any model we determine which weightings of its steps are central; the number of parameters defining a central weighting is always equal to the dimension plus one. (One of these parameters corresponds to a uniform scaling of weights, meaning it can be specialized to 1 since all of the properties we are interested in are preserved by scaling and one can recover asymptotics after this specialization.) One should compare these results to the work of Kauers and Yatchak [START_REF] Kauers | Walks in the quarter plane with multiple steps[END_REF] which computationally determined families of weights leading to a D-finite generating function. Except for one case, the weighted D-finite models they found correspond to central weights associated to specific D-finite models.

(ii) For these particular weights, we express (exactly and asymptotically) the numbers of weighted excursions in terms of the unweighted ones. These relations have strong consequences at the generating function level, and connect the (relatively unstudied) weighted and (well studied) unweighted generating functions. This is developed in Section 5.

(iii) For different weightings of the same underlying step set, one can determine information about the sub-families that have a common sub-exponential growth in the asymptotic formulas.

The classes that we consider here are completely defined by drift. Studying these univer- sality classes permits a direct connection between the ACSV enumerative approach and the probabilistic approach. This is developed in Section 6.

(iv) Finally, thanks to the above systematic construction of central weights, we are able to identify an infinite number of new models with non-D-finite generating functions.

Part I

The asymptotic enumeration of weighted Gouyou-Beauchamps walks 2 The main result and its consequences

Theorem statement

We begin with a close study of the centrally weighted models whose underlying step set is the Gouyou-Beauchamps model of Figure 1. Applying our construction (to be given in Part II) of central weights to this particular model we obtain the weights in Figure 1, which can be expressed with two parameters a and b:

(-1, 0) -→ 1/a, (1, 0) -→ a, (-1, 1) -→ b/a, (1, -1) -→ a/b. ( 5
) Class Condition ρ α Balanced a = b = 1 4 2 Free √ b < a < b (1+b)(a 2 +b) ab 0 Reluctant a < 1 and b < 1 4 5 Directed b > 1 and √ b > a 2(b+1) √ b 3/2 a > 1 and a > b (1+a) 2 a 3/2 Axial b = a 2 > 1 2(b+1) √ b 1/2 a = b > 1 (1+a) 2 a 1/2 Transitional a = 1, b < 1 or b = 1, a < 1 4 3
Table 1: The six different universality classes for weighted GB walks, under the weighting [START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF].

The generic weighted model S has corresponding drift

d = (d x , d y ) = (1 + b)(a 2 -b) ab , (a + b)(b -a) ab . ( 6
)
The drift is an important predictor of a model's asymptotics. For non-negative integers i and j, recall that Q i,j a (x, y; t) is the generating function (4) of a GB walk starting from (i, j).

Theorem 1. Fix constants a, b > 0.
As n → ∞ the number of weighted GB walks of length n, starting from (i, j) and ending anywhere while staying in R 2 + , satisfies

[t n ]Q i,j a (1, 1; t) = κ • V [n] (i, j) • ρ n • n -α • 1 + O 1 n , (7)
where the exponential growth ρ and the critical exponent α are given by Table 1. The universal constant κ and the harmonic function V [n] (i, j) are presented in Appendix A; the harmonic function V [n] (i, j) can depend on the parity [n] of n but is otherwise constant with respect to n.

We give names to the six regions in which the exponent α is constant, inducing six different universality classes for the central GB walks. The free region corresponds to walks where the drift is in the interior of the first quadrant, translating the idea that the walks behave as if they were unrestricted. The reluctant case corresponds to the domain where a < 1 and b < 1, when the walks have the smallest exponential growth. The transitional domain is the boundary of the reluctant region, while the axial domain is the boundary of the free region. The drift being (0, 0) corresponds to the balanced model, and what remains are the directed models. All these regions are defined more generally for other models in Section 6.

Main features and applications of Theorem 1

We now give a list of remarks around Theorem 1, illustrating applications in enumerative combinatorics, analytic combinatorics, probability theory and potential theory.

Combinatorial enumeration and uniform generation

Most plainly, Theorem 1 is a combinatorial result. It gives the asymptotics of the total number of walks confined to the quarter plane for the weighted Gouyou-Beauchamps model. This model is so-named because Gouyou-Beauchamps [START_REF] Gouyou-Beauchamps | Chemins sous-diagonaux et tableaux de Young[END_REF] discovered a simple hypergeometric formula for the (unweighted) walks that return to an axis. As shown by Gouyou-Beauchamps [START_REF] Gouyou-Beauchamps | Standard Young tableaux of height 4 and 5[END_REF], this lattice path model encodes several combinatorial classes: the set of walks ending anywhere are in bijection with pairs of non-intersecting prefixes of Dyck paths, and the walks ending on the axis are in bijection with Young tableaux of height at most 4. This quarter plane lattice path model is also in bijection with the lattice path model having step set S = {(±1, 0), (0, ±1)} which is restricted to the region {(x, y) : 0

x y}. Thus, the GB model can be considered as a walk in a Weyl chamber (see Gessel and Zeilberger [START_REF] Gessel | Random walk in a Weyl chamber[END_REF] for information on Weyl chamber walks).

Asymptotic results are also key in random generation of structures. Lumbroso, Mishna and Ponty [START_REF] Lumbroso | Taming reluctant random walks in the positive quadrant[END_REF] describe an algorithm for randomly sampling lattice path models, with the expected running time of the algorithm dependent on the polynomial exponent α; thus, models in the same universality class have the same cost of random generation. Uniformly sampled walks give a picture of how the weights impact the shape of the walk, and two examples from this algorithm are given in Figure 3. In the same vein, Bacher and Sportiello [START_REF] Bacher | Complexity of anticipated rejection algorithms and the darlingmandelbrot distribution[END_REF] have described an anticipated rejection random sampling algorithm with linear complexity when the expected first exit time is equivalent to Cn -α with α ∈ [0, 1). We can see that this occurs in our context for the axial and free cases.

Analytic Combinatorics of Several Variables

Our results demonstrate the theory of analytic combinatorics in several variables (ACSV). Mainly developed by Pemantle and Wilson [START_REF] Pemantle | Asymptotics of multivariate sequences. I. Smooth points of the singular variety[END_REF][START_REF] Pemantle | Asymptotics of multivariate sequences. II. Multiple points of the singular variety[END_REF][START_REF] Pemantle | Twenty combinatorial examples of asymptotics derived from multivariate generating functions[END_REF][START_REF] Pemantle | Asymptotic expansions of oscillatory integrals with complex phase[END_REF][START_REF] Pemantle | Analytic combinatorics in several variables[END_REF], and collaborators, this theory is used to determine asymptotic formulas of the coefficients of a class of multivariate power series. Although several examples of applications to lattice path combinatorics have already been given in the literaturesee, for example, Bressler et al. [START_REF] Bressler | Quantum random walk on the integer lattice: examples and phenomena[END_REF] or Melczer and Wilson [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF]-our study provides a continuous 2-parameter family of examples, with many phase transitions (exhibited by the variety of exponents α that we obtain). We believe this offers a concrete and rich framework for ACSV, and sheds light on how the intermediary geometric objects drive the asymptotic behaviour.

Excursions

Theorem 1 also has consequences in probability theory. Indeed, for random walks with drift in cones, a general derivation of asymptotic expressions for the probability of a random walk to stay in a given cone up to a fixed time is still an open problem (see Garbit, Mustapha and Raschel [START_REF] Garbit | Random walks with drift in cones[END_REF] for work in this direction).

Generally speaking, (combinatorial) asymptotic results on excursions1 can be turned into (probabilistic) local limit theorems by the formula

P[(i, j) + S n = (k, ), τ > n] = e (i,j)→(k, ) (n) #S n , (8)
where τ denotes the first exit time of the random walk (S n ) from the quadrant:

τ = inf{n 0 : S n / ∈ N 2 }. (9)
In the same way, results on walks with prescribed length can be written as

P (i,j) [τ > n] = e (i,j)→N 2 (n) #S n = (k, )∈N 2 e (i,j)→(k, ) (n) #S n . ( 10
)
Denisov and Wachtel [START_REF] Denisov | Random walks in cones[END_REF] prove a local limit theorem for random walks in cones, giving the asymptotics [START_REF] Bouaziz | Discrete harmonic functions on an orthant in Z d[END_REF] and, in the case of zero drift, obtain a precise estimate of the non-exit probability [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. Duraj [START_REF] Duraj | Random walks in cones: the case of nonzero drift[END_REF] established an asymptotic estimate of the non-exit probability for the walks in the reluctant universality class (roughly speaking for the general case, the ones with negative drift). Furthermore, the exponential growth ρ in Equation ( 7) is computed by Garbit and Raschel [START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF]: for a large class of cones and dimensions it is equal to the minimum of the Laplace transform of the increments of the random walk on the dual cone (note that the quarter plane is self dual). Further discussion on this topic occurs in Subsection 6.2.

Our contribution in this area is as follows. For a continuous family of processes-whose drift can be equal to any prescribed value-we find the exponents α in Equation [START_REF] Bostan | Hypergeometric expressions for generating functions of walks with small steps in the quarter plane[END_REF]. Interestingly, α can be equal to six different values: 0, 1/2, 3/2, 2, 3, or 5.

We further observe a correspondence between the direction of the drift and the value of α, as shown in Figure 6; this correlation between the drift and value of the exponent seems to become slightly more complex in the general case [START_REF] Garbit | Random walks with drift in cones[END_REF]. We discuss conditions which induce the correspondence in Section 6.

Periodicity of leading terms

Interestingly, the leading term of the asymptotic expansion [START_REF] Bostan | Hypergeometric expressions for generating functions of walks with small steps in the quarter plane[END_REF] can have periodic behaviour. More specifically, the term V [n] depends on the parity of n in the directed, transitional and reluctant cases. For general walks in cones, the periodicity of the leading term often exists for excursions-in periodic random walks, for instance-however when the drift is zero the leading term of the non-exit probability [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] is not periodic [START_REF] Denisov | Random walks in cones[END_REF].

This phenomenon of periodicity, which only occurs in the case of a drift with at least one negative coordinate, is not fully understood. The reader can refer to Bostan et al. [START_REF] Bostan | Hypergeometric expressions for generating functions of walks with small steps in the quarter plane[END_REF]] or Melczer and Wilson [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF] for examples of periodic constants in the unweighted small step case.

Discrete harmonic functions

An additional corollary of our results is a formula for a family of discrete harmonic functions. Indeed, the quantity V [n] (i, j) in Equation ( 7) satisfies a property of discrete ρ-harmonicity, since

ρ • V [n+1] (i, j) = (1/a)V [n] (i -1, j) + (b/a)V [n] (i -1, j + 1)
+ aV [n] (i + 1, j) + (a/b)V [n] (i + 1, j -1).

Equation [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF] follows from the recurrence relations satisfied by the numbers of walks e (i,j)→N 2 (n), as well as the asymptotic estimate given in Theorem 1.

Two different cases should be mentioned. If V [n] does not depend on n (which is typically the situation), then V = V [n] is called a discrete harmonic function. Such discrete harmonic functions are of paramount interest: via the standard procedure of a Doob transform they are used to construct processes conditioned never to leave cones [START_REF] Denisov | Random walks in cones[END_REF][START_REF] Despax | A family of centered random walks on weight lattices conditioned to stay in Weyl chambers[END_REF][START_REF] Duraj | Random walks in cones: the case of nonzero drift[END_REF][START_REF] Lecouvey | t-Martin boundary of killed random walks in the quadrant[END_REF]. These processes are important in probability theory, appearing in non-colliding processes and eigenvalues of certain random matrices, among other areas. See Section 2.2.6 for more details. In the second case, when V [n] depends on n, V [n] is called a caloric function [START_REF] Bouaziz | Discrete harmonic functions on an orthant in Z d[END_REF].

Although the discrete recurrence [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF] is reminiscent of the one counting walks [START_REF] Fayolle | Random walks in the quarter-plane[END_REF], the solution space of Equation ( 11) is rather different. In particular, there exist a priori infinitely many different harmonic functions solving the discrete recurrence [START_REF] Lecouvey | t-Martin boundary of killed random walks in the quadrant[END_REF] while Equation [START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF] uniquely defines a model's generating function.

Thanks to our asymptotic results we indirectly find discrete harmonic/caloric functions, listed in Appendix A, with particularly nice exponential and polynomial expressions. As an example, in the zero drift case a = b = 1 one has

V (i, j) = (i + 1)(j + 1)(i + j + 2)(i + 2j + 3) 6 . (12)
This is a polynomial expression of degree four, homogeneous in the variables i+1, j +1. Additionally, discrete harmonic functions seem promising for the random generation of random walks confined to cones [21].

Conditioning random walks

A typical question in probability theory [START_REF] Denisov | Random walks in cones[END_REF][START_REF] Despax | A family of centered random walks on weight lattices conditioned to stay in Weyl chambers[END_REF][START_REF] Duraj | Random walks in cones: the case of nonzero drift[END_REF][START_REF] Lecouvey | t-Martin boundary of killed random walks in the quadrant[END_REF] is to compare two different ways of conditioning a random walk (S n ) to never leave a cone:

• The first way is to condition on the event {τ > n}, with τ being the first exit time (9) from the cone, and to let n go to infinity; the law of the conditioned Markov chain is characterized by

P (i,j) [S 1 = (k, )] = lim n→∞ P (i,j) [S 1 = (k, )|τ > n]. (13)
This definition of conditioned random walks has a clear and natural probabilistic interpretation. However, except in the free case, the limit event {τ = ∞} has zero probability so that it is a priori unclear that the limit in the right-hand side of Equation ( 13) exists.

• The second way consists in using a (discrete) harmonic function and the procedure of Doob transformation (see Section 13 in Doob [START_REF] Doob | Classical potential theory and its probabilistic counterpart[END_REF]Chapter 6]). If V is a z-harmonic function-i.e.,

z • V (i, j) = E (i,j) [V (S 1 ), τ > 1]
-which is zero on the exterior of the cone2 , then

P V (i,j) [S 1 = (k, )] = P (i,j) [S 1 = (k, ), τ > 1] V (k, ) z • V (i, j) (14)
defines a Markov chain which by construction stays in the cone. In Equation ( 14) the transition probabilities P (i,j) [S 1 = (k, ), τ > 1] are obtained from Equation [START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF].

For random walks in cones with no drift, Denisov and Wachtel [START_REF] Denisov | Random walks in cones[END_REF] showed that these two approaches coincide: P = P V . Similar considerations for negative drift (reluctant) random walks are given by Duraj [START_REF] Duraj | Random walks in cones: the case of nonzero drift[END_REF].

To link back to our results, we compare these two approaches under the additional assumption that our harmonic function V [n] does not depend on the parity of n. To show that the two viewpoints coincide for centrally weighted GB models we note that

lim n→∞ P (i,j) [S 1 = (k, )|τ > n] = lim n→∞ P (i,j) [S 1 = (k, ), τ > 1] P (k, ) [τ > n -1] P (i,j) [τ > n] = P V (i,j) [S 1 = (k, )]. (15)
The first equality in Equation ( 15) is simple and comes from the definition of a conditional probability together with the Markov property; the second equality follows from using Equations ( 7) and [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] with z = ρ/#S. There are more subtleties in the case where V [n] depends on the parity of n, which we do not cover here.

A second interesting aspect of conditioned random walks is to prove that the following operations commute:

• n → ∞ in the conditioning by {τ > n},

• the drift d converges to a fixed drift d 0 .

Precisely, this amounts to proving that

lim d→ d 0 lim n→∞ P (i,j) [S 1 = (k, )|τ > n] = lim n→∞ lim d→ d 0 P (i,j) [S 1 = (k, )|τ > n]. (16)
Equation ( 16) can be interpreted as the continuity of the law of conditioned random walks with respect to the drift of the step set. Despax [START_REF] Despax | A family of centered random walks on weight lattices conditioned to stay in Weyl chambers[END_REF] considers, in any dimension but for a particular family of random walks, the case d 0 = 0 and proves the above identity when d → d 0 while remaining in the cone.

Using our results we can prove, for the GB model, equality in Equation ( 16) for any value of the drift d 0 ∈ R 2 (not necessarily in the cone). This is an easy consequence of the explicit expression of the harmonic function and Equation [START_REF] Doob | Classical potential theory and its probabilistic counterpart[END_REF]. Notice in particular that lim d→(0,0)

V (i, j) V (0, 0) = lim (a,b)→(1,1)
V (i, j) V (0, 0) = (i + 1)(j + 1)(i + j + 2)(i + 2j + 3) 6 exists (i.e., does not depend on the way that (a, b) → (1, 1)). The right-hand side of the identity above, corresponding to Equation [START_REF] Bressler | Quantum random walk on the integer lattice: examples and phenomena[END_REF], can thus be viewed as a universal harmonic function for the GB model.

The generating function as a diagonal

As mentioned above, we will derive our asymptotic results by representing the combinatorial sequences under consideration in terms of coefficient extractions of explicit rational functions. In order to derive these representations we use an approach called the algebraic kernel method3 which has been applied widely to lattice path problems in recent years [START_REF] Bousquet-Mélou | Counting walks in the quarter plane[END_REF][START_REF] Bousquet-Mélou | Walks confined in a quadrant are not always D-finite[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF][START_REF] Bostan | On 3-Dimensional Lattice Walks Confined to the Positive Octant[END_REF]; our presentation closely follows that of Bousquet-Mélou and Mishna [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], which is now standard.

A lattice path model is said to have small steps if its set S of allowable steps is a subset of {0, ±1} 2 . In their work, Bousquet-Mélou and Mishna proved that there are 79 non-trivial distinct small step quarter plane models (which are not equivalent to half plane models) and provided many expressions for their generating functions. A model is called singular if there is a half-plane which contains all of its allowable steps; for instance the step set S = {(-1, 1), (1, 1), (1, -1)} is non-trivial and singular.

The kernel equation

As noted in the introduction, a straightforward functional equation for the generating function Q(x, y; t) arises from the basic fact that a walk of length n is either empty or a walk of length n -1 plus a valid step. In order to express this recurrence on the level of generating functions, we define the inventory S(x, y) = (s 1 ,s 2 )∈S x s 1 y s 2 and the kernel K(x, y; t) = xy(1 -tS(x, y)). Note that for a non-trivial model with small steps the kernel is a polynomial. Translating the recursive decomposition of a walk, and taking into consideration the boundary conditions, one obtains the functional equation

K(x, y; t)Q(x, y; t) = xy + K(x, 0; t)Q(x, 0; t) + K(0, y; t)Q(0, y; t) -K(0, 0; t)Q(0, 0; t), (17)
which is proven in Bousquet-Mélou and Mishna [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. This functional equation is known as the kernel equation and is easily modified to handle walks with different starting position: the term xy is replaced by x i+1 y i+1 when the walk begins at (i, j) instead of the origin. The subsequent analysis is robust enough to handle this modification, but as it becomes notationally heavy we mainly detail the case i = j = 0.

Series extractions and diagonals

The kernel method associates to each step set a specific group G(S) of bi-rational transformations, generated by involutions, which fixes the kernel. Remarkably, for models with small steps the finiteness of this group is perfectly correlated to the nature of the multivariate generating functions Q(x, y; t). In particular, for the 79 distinct non-trivial models with small steps G(S) is finite if and

only if Q(x, y; t) is D-finite.
The group associated to the unweighted Gouyou-Beauchamps model has order eight and is generated by the two involutions

Ψ : (x, y) → y x , y , Φ : (x, y) → x, x 2 y .
We shall see that this group does not substantially change under a central weighting, which is what allows a uniform diagonal expression for models under such weightings. The kernel method applies the transformations of G(S) to Equation ( 17) in order to generate new functional equations, which are then manipulated into an expression for Q(x, y; t). Consider the ring R := Q((x, y))[[t]] of power series in t whose coefficients are multivariate Laurent series in x and y, with a generic element having the form

F (x, y; t) = n 0   i,j kn f i,j (n)x i y j   t n (18)
for integers k 0 , k 1 , k 2 , . . . . The expression for Q(x, y; t) obtained by the kernel method uses the series extraction operator [x 0 y 0 ], which takes F (x, y; t) ∈ R defined by Equation ( 18) and returns the multivariate power series

[x y ]F (x, y; t) = i,j,n 0 f i,j (n)x i y j t n .
Proposition 11 of Bousquet-Mélou and Mishna [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] gives that the generating function for the GB model satisfies

Q(x, y; t) = [x y ] (1 -x) (1 + x) (1 -y) 1 -x 2 y (1 -xy) (1 + xy) 1 -t(x + x + xy + xy) , (19)
where we write x = 1/x and y = 1/y to simplify notation. In order to determine the asymptotic behaviour of the number of lattice walks in a model we convert this expression for the multivariate generating function Q(x, y; t) into one for the univariate generating function Q(1, 1; t). The diagonal operator ∆ takes F (x, y; t) ∈ R defined by Equation ( 18) and returns the univariate power series

(∆F )(t) = n 0 f n,n (n)t n
whose coefficients are determined by the terms of F (x, y; t) where the exponents of each variable are equal. Equation ( 19) can be used to give a diagonal expression for Q(1, 1; t) as

[x y ]F (x, y; t) x=1,y=1 = ∆ F (x, y, xyt) (1 -x)(1 -y)
whenever F (x, y, xyt) is a well-defined element of R (this fact follows from a straightforward manipulation of the power series in question; see Proposition 2.6 of Melczer and Mishna [START_REF] Melczer | Asymptotic lattice path enumeration using diagonals[END_REF] for more information). In the end, one obtains

Q(1, 1; t) = ∆ (x + 1)(x 2 -y)(x -y)(x + y) 1 -xyt(x + xy + yx + x) .
Following the same argument with weighted steps, where the weighted inventory

S(x, y) = (s 1 ,s 2 )∈S (a s 1 b s 2 )x s 1 y s 2 = ax + 1 ax + ax by + by ax is used, results in the diagonal expression Q a (1, 1; t) = ∆ (y -b)(a -x)(a + x)(a 2 y -bx 2 )(ay -bx)(ay + bx) a 4 b 3 x 2 y(1 -txyS(x, y))(1 -x)(1 -y) , (20)
which is valid for any non-zero constants a and b (although we only consider the case when a and b are positive below). We can similarly deduce an expression for weighted walks parametrized by start point (i, j) by modifying the kernel equation to account for these new starting points, as discussed above; only the numerator of the resulting rational diagonal depends on i and j. A weighted version of Equation ( 19) was also derived by Kauers and Yatchak [START_REF] Kauers | Walks in the quarter plane with multiple steps[END_REF] during their computational investigation into the analytic nature of weighted lattice path generating functions.

In order to determine asymptotics through analytic techniques, it is easiest to consider diagonals of rational functions with power series expansions. As

∆ (xyt) -k F (x, y, t) = t -k ∆F (x, y, t)
for any natural number k and F ∈ R, we can modify Equation ( 20) to obtain

Q a (1, 1; t) = 1 a 4 b 3 t 2 ∆ yt 2 (y -b)(a -x)(a + x)(a 2 y -bx 2 )(ay -bx)(ay + bx) (1 -txyS(x, y))(1 -x)(1 -y) . (21)
We prove Theorem 1 by representing the coefficients of this diagonal as a multivariate complex integral, and asymptotically approximating the integral expression. This is possible due to a multivariate generalization of Cauchy's Integral Formula (CIF).

Theorem 2 (Multivariate CIF). Suppose that F (x, y, t) ∈ Q(x, y, t) is analytic at (0, 0, 0) with a power series expansion F (x, y, t) = i,j,n 0 f i,j (n)x i y j t k at the origin. Then for all n 0,

f n,n (n) = 1 (2πi) 3 T F (x, y, t) (xyt) n • dx dy dt xyt , ( 22
)
where T is any poly-disk defined by {|x| = ε 1 , |y| = ε 2 , |z| = ε 3 }, with each ε j sufficiently small.

The proof follows from the standard Cauchy Integral Formula by induction on the number of variables; see Section 7.2 of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF] or a standard book on complex analysis in several variables for details.

Proof of Theorem 1

This section describes how to apply the theory of analytic combinatorics in several variables (ACSV) to the enumeration of centrally weighted GB models. We focus only on the results of ACSV which we require, and specialize them to our context. For a general presentation of ACSV we refer the reader to the text of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF] or the doctoral thesis of Melczer [START_REF] Melczer | Analytic Combinatorics in Several Variables: Effective Asymptotics and Lattice Path Enumeration[END_REF]. To see additional applications of ACSV to lattice path enumeration, see Melczer and Mishna [START_REF] Melczer | Asymptotic lattice path enumeration using diagonals[END_REF] or Melczer and Wilson [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF].

Minimal points

To find an asymptotic estimate of the coefficients of a univariate generating function using classical methods of (univariate) analytic combinatorics, one typically proceeds by first identifying a finite set of singularities-called the dominant singularities-of the generating function, and then summing asymptotic contributions of each singularity which are determined by their location and nature. In the study of analytic combinatorics in several variables, the generating function of interest-for us Q a (1, 1; t)-is represented indirectly as the diagonal of a rational function F (x, y, t); the strategy is then to determine asymptotic behaviour from the analytic properties of F .

Recall from Equation ( 21) that our rational function F (x, y, t) = i,j,n 0 f i,j (n)x i y j t n can be written as the ratio of two polynomials G(x, y, t) and H(x, y, t) with

H(x, y, t) = (1 -txyS(x, y))(1 -x)(1 -y);
for most choices of weights a and b these polynomials are co-prime. We define the singular variety V of F to be the algebraic set composed of its singularities, which is

V = (x, y, t) ∈ C 3 : H(x, y, t) = 0
when G and H are co-prime. Let D denote the open domain of convergence of the power series representation of F (x, y, t) at the origin. Similar to the univariate case, where dominant singularities lie on a generating function's disk of convergence, the singularities in the set D ∩ V, which are called minimal points, are crucial to the analysis (D denotes the closure of D). The simple form of the denominator H in the diagonal expression for GB walks makes it easy to identify minimal points. Lemma 3. For the rational function F (x, y, t) described by Equation (21), when G and H are co-prime the point (x, y, t) ∈ V is minimal if and only if

|x| 1, |y| 1, |t| 1 |xy|S(|x|, |y|)
,

where these three strict inequalities do not occur simultaneously.

Proof. When the polynomials G and H are co-prime the set of minimal points coincides with the minimal points of the rational function 1/H(x, y, t), which is the product of three geometric series. The domain of convergence D is then obtained by intersecting the domains of convergence of the rational functions 1/(1x), 1/(1y), and 1/(1 -txyS(x, y)). The domain of convergence of the last rational function is {(x, y, t) : |t| < |xy| -1 S(|x|, |y|) -1 } as the polynomial xyS(x, y) has non-negative coefficients so that the point (x, y, t) is in its domain of convergence only if (|x|, |y|, |t|) is.

Similar arguments show that when the weights are such that the factor (1x), and not (1y), is canceled by the numerator then the minimal points are described by |y| 1 and |t|

Critical points

Intuitively, minimal points are the singularities of F which the cycle of integration T in the Cauchy integral of Equation ( 22) can be made arbitrarily close to. The goal is to find a finite set of points such that we can replace the Cauchy integral over T with a sum of integrals over domains local4 to these points. With this in mind, Pemantle and Wilson define critical points, which roughly correspond to points where saddle point methods can be applied to local integrals in order to obtain asymptotic estimates.

We will not describe critical points in full generality, instead relying on a proposition which determines critical points for a large class of rational functions (and for our purposes define critical points). First, one must partition the singular variety V into a collection of smooth manifolds called strata, with certain conditions on how the strata sit inside V relative to each other. Define

H 1 = 1 -txyS(x, y), H 2 = 1 -x, H 3 = 1 -y,
and for polynomials f 1 , . . . , f r let V(f 1 , . . . , f r ) denote the points (x, y, t) such that

f 1 (x, y, t) = • • • = f r (x, y, t) = 0.
For the rational function we consider, defined in Equation ( 21), the set V can be stratified into 7 components:

V 1 := V(H 1 ) \ V(H 2 H 3 ), V 2 := V(H 2 ) \ V(H 1 H 3 ), V 3 := V(H 3 ) \ V(H 1 H 2 ), V 12 := V(H 1 , H 2 ) \ V(H 3 ), V 13 := V(H 1 , H 3 ) \ V(H 2 ), V 23 := V(H 2 , H 3 ) \ V(H 1 ), V 123 := V(H 1 , H 2 , H 3 ).
Note that this collection of sets partitions V, and that each defines a smooth manifold (there are additional requirements for this to be a stratification, but they are trivially satisfied). The following result is sufficient to characterize the critical points for us.

Proposition 4 (Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF]Section 8.3]). Suppose that X is a stratum of V defined as X = V(f 1 , . . . , f r ) \ W, where W is an algebraic set of lower dimension than V(f 1 , . . . , f r ), each V(f i ) is a complex manifold and the tangent planes of the V(f i ) are linearly independent where they intersect. Then (x, y, t) ∈ X is a critical point if and only if the vector (1, 1, 1) can be written as a linear combination of the vectors

x ∂f i ∂x , y ∂f i ∂y , t ∂f i ∂t , i = 1, . . . , r.
Remark 5. This proposition is reminiscent of the classical method of Lagrange multipliers, and we now give a rough idea of this connection. Because F (x, y, t) is absolutely convergent on (x, y, t) ∈ D, the same property holds for

Q a (1, 1; xyt) = n 0 f n,n (n) x n y n t n . Hence, the radius of convergence ρ of Q a (1, 1; t) satisfies ρ sup (x,y,t)∈D |xyt|.
It is not obvious, but true in our context, that this inequality is actually an equality, and the supremum is reached on a point of the variety V:

ρ = sup (x,y,t)∈D∩V |xyt|. ( 23
) Stratum Critical Points Exponential Growth V 1 c ± 1 = (±a, b) e 1 = 4 V 12 c 12 = 1, b a e 12 = (a+1) 2 a V 13 c ± 13 = ± a √ b , 1 e 13 = 2(b+1) √ b V 123 c 123 = (1, 1) e 123 = (b+1)(a 2 +b)
ab Table 2: The (x, y)-coordinates of the critical points; for each, t = xyS(x, y) -1 .

Thus, the finite set of singularities we seek to find corresponds to the maximizers of |xyt| on D ∩ V, while the critical points are the candidates for the maximization. Proposition 4 encapsulates the fact that the critical points give the possible locations of local extrema of |xyt| on each stratum.

In our application the only polynomial containing the t variable is H 1 , meaning that the only strata that can have critical points are V 1 , V 12 , V 13 and V 123 . Using Proposition 4 it is then easy to determine the critical points of V. Substituting the definition of the inventory S(x, y) = ax + (ax) -1 + ax(by) -1 + by(ax) -1 into this system of equations implies there are two critical points defined uniquely by their (x, y)-coordinates:

c ± 1 = (±a, b).
We repeat this computation for each case to determine the following result.

Proposition 7. The set of critical points on each strata is given in Table 2.

Contributing points

The methods of ACSV are well suited to our weighted models because they always a finite set of minimal critical points (which also satisfy some additional technical conditions). The integral over the cycle T in Equation ( 22) can be replaced by the sum of integrals over cycles which are arbitrarily close to each contributing point while introducing an error that grows exponentially smaller than the diagonal sequence. To calculate an asymptotic estimate of the diagonal sequence, we compute the asymptotic contribution for each contributing point and sum the results; the function |xyt| -1 determines the exponential growth of the diagonal sequence.

The next result shows that the function |xyt| -1 is always minimized at a minimal critical point.

Lemma 8. A minimizer (x 0 , y 0 , t 0 ) of |xyt| -1 in D is a minimal critical point.
Proof. Assume first that the weights a and b are such that the factors for (x, y) ∈ (0, 1] 2 occurs at the (x, y)-coordinates of a minimal critical point. As touched on in Remark 5, the theory of Lagrange multipliers implies this is true whenever the minimum of S(x, y) is achieved in (0, 1] 2 . The minimum is achieved because S(x, y) tends to infinity as either x or y (or both) stay positive and tend to 0: the form of S(x, y) implies this holds as x → 0 but then it also holds as y → 0 because x bounded away from 0 implies x/y → ∞. Similar arguments show that when one or both of the factors 1x and 1y in the denominator are canceled then the result holds as long as the minimum of S(x, y) is achieved on (0, 1] × (0, ∞), (0, ∞)×(0, 1] or (0, ∞) 2 , depending on which factors have canceled. Again the minimum is achieved, as S(x, y) approaches infinity as either x or y (or both) approach infinity.

It is now easy to characterize the contributing points using our explicit characterization of minimal points in Lemma 3. Note that on the boundaries of these case distinctions the contributing points with positive coordinates coincide.

Proof. The result follows from Proposition 10.3.6 of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF], which characterizes the set of critical points when V has the type of geometry that we encounter here. Aside from some easily checked technical conditions, we need to show that the points described above in each case are minimal points which (by Lemma 8) minimize |xyt| -1 among the finite set of minimal critical points on D.

The values of the exponential growth |xyt| -1 for each set of critical points are listed in the final column of Table 2. Note that the AM-GM inequality implies that e 1 e 12 , e 13 e 123 , so that the set of critical points consists of c ± 1 as long as these points are minimal. Similarly, the points c 12 or c ± 13 contribute as long as they are minimal and c ± 1 is not (note that if c ± 1 is not minimal then it can't happen that both c 12 and the c ± 13 are minimal). Finally, the conditions listed above come from the characterization of minimal points in Lemma 3.

Note that the factors (1x) and (1y) in the denominator cancel only when a = 1 or b = 1, respectively. Such models are either Transitional or Directed, and the conclusion can be verified separately for each case.

At this point we have determined, for all possible choices of weights a and b, the points where a local analysis of the rational function F (x, y, t) determines asymptotics of the diagonal sequence up to an exponentially smaller error. It remains only to calculate the asymptotic contribution of each contributing point and sum the results in each case. The different strata containing critical points correspond to different exponential growths, but do not completely determine universality classes: the critical exponents depend on several factors, including the degree of vanishing of G(x, y, t) at the contributing points.

We now complete the proof of Theorem 1 by showing how to compute the asymptotic contributions of the critical points.

Asymptotic contributions

Making the change of variables (x, y, t) → ε 1 e iθ 1 , ε 2 e iθ 2 , ε 3 e iθ 3 converts the Cauchy Integral representation [START_REF] Garbit | Random walks with drift in cones[END_REF] into

f n,n (n) = (ε 1 ε 2 ε 3 ) -n (2π) 3 (-π,π) 3 F ε 1 e iθ 1 , ε 2 e iθ 2 , ε 3 e iθ 3 e -n(θ 1 +θ 2 +θ 3 ) dθ 1 dθ 2 dθ 3 . ( 24
)
This new representation is an example of a Fourier-Laplace integral : that is, it has the form

A(θ 1 , θ 2 , θ 3 )e -nφ(θ 1 ,θ 2 ,θ 3 ) dθ 1 dθ 2 dθ 3 ,
with the functions A and φ analytic over their domain of integration. Asymptotics of a large class of Fourier-Laplace integrals can be obtained through the following result. • φ has a critical point at θ = 0, i.e., that (∇φ)(0) = 0, and that the origin is the only critical point of φ in N ;

• the Hessian H of φ at θ = 0 is non-singular;

• φ(0) = 0;

• the real part of φ(θ) is non-negative on N .

Then for any integer M > 0 there exist effective constants C 0 , . . . , C M such that

N A(θ) e -nφ(θ) dθ = 2π n d/2 det(H) -1/2 • M k=0 C k n -k + O n -M -1 . ( 25
)
The constant C 0 is equal to A(0). Moreover, if A(θ) vanishes to order L at the origin then (at least) the constants C 0 , . . . , C L 2 are all zero.

The constants C k are determined by evaluating the application of powers of an explicit differential operator to a sequence of explicit functions depending on φ and A. As the formulas get quite involved, we refer the reader to Hörmander [28, Theorem 7.7.5] or Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF]Lemma 13.3.2]. For our results we calculated the constants by writing a simple program in the Maple computer algebra system 5 .

Unfortunately we cannot directly apply Proposition 10 to Equation [START_REF] Gessel | A probabilistic method for lattice path enumeration[END_REF] as the function φ = θ 1 + θ 2 + θ 3 admits no critical points (in the usual calculus sense). The importance of critical points in the context of ACSV comes from the fact that localizing the Cauchy Integral around the critical points results in an integral expression-or sum of expressions-to which Proposition 10 can be applied. We now see how this can be achieved for the different cases laid out in Proposition 9.

The Balanced Case

This is the unweighted model, whose asymptotics have been previously computed [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. Still, the solution via ACSV initiates us to the weighted models, so we present it here.

When a = b = 1, the rational function under consideration simplifies to

F (x, y, t) = yt 2 (1 + x)(y -x 2 )(x -y)(y + x) 1 -txyS(x, y) ,
although we keep a and b as symbolic parameters below as this helps illustrate the form of the general argument. From Proposition 9 we know that the growth of the coefficient is determined by the singular behaviour of F near the points c ± 1 = ±a, b, ±abS(a, b) -1 , and we derive this again in the course of estimating integrals. Consider the chains of integration

T -= {(x, y, t) : |x| = a, |y| = b, |t| = abS(a, b) -1 -ε}, T + = {(x, y, t) : |x| = a, |y| = b, |t| = abS(a, b) -1 + ε},
for ε arbitrarily small. By the Cauchy Integral Formula and minimality of c ± 1 (see Lemma 3),

f n,n (n) = 1 (2πi) 3 T - F (x, y, t) (xyt) n dx dy dt xyt .
As every point on T + lies outside the domain of convergence of the generating function F (x, y, t), one can show that 1 (2πi) 3

T + F (x, y, t) (xyt) n
dx dy dt xyt grows exponentially smaller than the diagonal sequence as n approaches infinity. Defining

D ± := {z : |z| = abS(a, b) -1 ± ε}, it follows that fn,n(n) = 1 (2πi) 3 |x|=a |y|=b D + yt 2 (1 + x)(y -x 2 )(x -y)(y + x) 1 -txyS(x, y) dt (xyt) (n+1) - D - yt 2 (1 + x)(y -x 2 )(x -y)(y + x) 1 -txyS(x, y) dt (xyt) (n+1) dx dy + O(K n )
for some constant K > 0 with K < lim sup n→∞ |f n,n (n)| 1/n . The inner difference of integrals can then be determined by a residue computation.

By design, for ε sufficiently small, dominant asymptotics only depend on integration around arbitrarily small neighbourhoods N + and N -of the critical points c ± 1 in the set {(x, y) : |x| = a, |y| = b}, so

f n,n (n) = 1 (2πi) 2 j∈{+,-} Nj x 2 yS(x, y) -2 (1 + x)(y -x 2 )(x -y)(y + x)S(x, y) n dxdy + O(K n ) = S(a, b) n (2π) 2 j∈{+,-} (-ε ,ε ) 2 A j (θ 1 , θ 2 )e -nφj (θ1,θ2) + O(K n ), (26)
with

A j (θ 1 , θ 2 ) = G jae iθ 1 , br 2 e iθ 2 , φ j (θ 1 , θ 2 ) = -log S jae -iθ 1 , be -iθ 2 + log S a, b .
By the definition of minimal critical points, the conditions of Proposition 10 are satisfied by these integrals at c ± 1 , and applying the proposition gives the asymptotic estimate

f n,n (n) = 8 π • 4 n n 2 1 + O 1 n .

The Reluctant Case

The integral expression for the reluctant case is roughly the same as in the balanced case, except that now the factors (1x) and (1y), which canceled with factors in the numerator when a = b = 1, appear in the denominator of F (x, y, t). In this case, when a < 1 and b < 1, Proposition 9 shows that the contributing points have xand y-coordinates of modulus less than 1. The argument for the balanced case can then be applied to obtain an expression of the same form as Equation ( 26), since the domain of integration avoids the zero set of (1x)(1y). In particular, we can apply Proposition 10 to the integrals in Equation ( 26) where now

A j = G jae iθ 1 , br 2 e iθ 2 (1 -jae iθ 1 )(1 -br 2 e iθ 2 )
,

and the φ j are unchanged from the balanced case. Shifting the asymptotics to take the relationship in Equation ( 21) between the diagonal sequence and the number of lattice walks into account gives the asymptotics listed in Theorem 1.

The Transitional Cases

The transitional cases are on the boundary between being reluctant and directed. When a = 1 and b < 1, the contributing points c ± 1 have x-coordinate of modulus 1, however the factor of 1x cancels with a factor of 1x which becomes present in the numerator when specializing a to 1. When b = 1 and a < 1, the contributing points c ± 1 have a y-coordinate of 1, however the factor of 1y cancels with a factor of 1y which becomes present in the numerator when specializing b to 1. After this simplification, the same argument as in the balanced and reluctant cases applies.

Note also that this cancellation shows why the balanced, transitional and reluctant cases have the same exponential growth but critical exponents α differing by 1. The contributing points are the same for each, but the order of vanishing of the numerator G at the critical points is 2, 3 and 4 for balanced, transitional and reluctant, respectively. Proposition 10 shows that when the order of vanishing of the numerators increases one expects the critical exponents to decrease.

The Directed Cases

In the directed cases, the contributing points lie on the intersection of the zero set of two factors in the denominator of F (x, y, t). This requires a slightly different argument, but the general approach is the same.

Suppose first that we are in the case when a > 1 and a > b, so that the unique contributing point has (x, y)-coordinates c 12 = (1, b/a) and lies on V 12 . If we define

G(x, y) := G(x, y, t) t 2 = y(y -b)(a -x)(a + x)(a 2 y -bx 2 )(ay -bx)(ay + bx)
then the Cauchy Integral Formula implies that we want asymptotics of

[t n+2 ][x n+2 ][y n+2 ] t 2 G(x, y) a 4 b 3 (1 -txyS(x, y))(1 -x)(1 -y) = [x 2 ][y 2 ] G(x, y)S(x, y) n a 4 b 3 (1 -x)(1 -y) = 1 a 4 b 3 (2πi) 2 |y|=b/a |x|=1-ε G(x, y)S(x, y) n (1 -x)(1 -y) dxdy x 3 y 3 I ,
for any fixed 0 < ε < 1. Furthermore, standard integral bounds imply the existence of constants C > 0 and M ∈ (0, 2 + a + 1/a) such that

1 a 4 b 3 (2πi) 2 |y|=b/a |x|=1+ε G(x, y)S(x, y) n (1 -x)(1 -y) dxdy x 3 y 3 C • M n .
Thus, as n → ∞,

I = 1 a 4 b 3 (2πi) 2 |y|=b/a |x|=1-ε G(x, y)S(x, y) n (1 -x)(1 -y) dxdy x 3 y 3 - |x|=1+ε G(x, y)S(x, y) n (1 -x)(1 -y) dxdy x 3 y 3 dy + O(M n ).
Cauchy's residue theorem then implies

I = 1 a 4 b 3 (2πi) |y|=b/a G(1, y)S(1, y) n 1 -y dy y 3 + O(M n ) = (2 + a + 1/a) n a 4 b 3 (2π) π -π A(θ)e -kφ(θ) dθ + O(M n ), (27)
where Since c 12 is a contributing singularity, it can be shown that the integral in Equation ( 27) has a single critical point at θ = 0, to which Proposition 10 (which is classical in the univariate case) can be applied. In the other directed case, when b > 1 and √ b > a, the analysis is the same except that the existence of two contributing points, with (x, y)-coordinates c ± 13 , implies that asymptotics are ultimately obtained from a sum of two univariate Fourier-Laplace integrals.

A(θ) = G(
Comparison to the Method of Multivariate Residues Above we have adapted the tools of saddle-point analysis in order to determine asymptotics when our contributing points lie on a strata defined by the intersection of two smooth manifolds. The theory of analytic combinatorics in several variables, as developed in Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF], takes a more uniform (but less elementary) approach to such integrals using the theory of multivariate residues. The theoretical groundwork for multivariate complex residues dates back to Leray, and is well presented in the text of Aȋzenberg and Yuzhakov [START_REF] Aȋzenberg | Integral representations and residues in multidimensional complex analysis[END_REF]. Instead of detailing the theory here we refer the reader to Section 10.2 of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF], which describes how to calculate the multivariate residue of a rational function over a fixed strata.

Consider again the case when a > 1 and a > b, so that the unique contributing point has (x, y)coordinates c 12 = (1, b/a) and lies on V 12 . As c 12 defines the unique contributing point, Theorem 10.2.2 of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF] implies that diagonal asymptotics are determined by the integral

1 2πi σ G(1, y)S(1, y) n 1 -y dy y 3 ,
where σ is a one-dimensional curve of integration in V 12 containing the contributing point. Unfortunately, it can be difficult in general to obtain an explicit description of the possible domains of integration σ using this approach. When the numerator G of the rational function under consideration does not vanish at a contributing point, Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF]Theorem 10.3.4] give an explicit formula for its dominant asymptotic contribution using the multivariate residue approach.

The Free Case

In the free case √ b < a < b there is exactly one contributing point, whose (x, y)-coordinates are (1, 1). This point lies on the strata determined by the intersection of the three varieties V 1 , V 2 , V 3 ; when the co-dimension of a strata equals the dimension of the ambient space, as it does here, the intersection of varieties is called a complete intersection. Complete intersections have an interesting property: the three dimensional (multivariate) residue, when defined, is a constant! This means that for a complete intersection one can determine dominant asymptotics up to an exponentially smaller error term (instead of a polynomial error term as in most cases above).

Indeed, Theorem 10.3.1 of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF] explicitly gives the dominant asymptotics when the contributing point lies on a complete intersection and the numerator G does not vanish at this point. This faster, exponential, decrease in the relative error can be observed numerically while examining terms of modest size (less than 100).

The Axial Cases

The axial cases are on the boundary of the directed cases and the free case. Unfortunately, the above approaches cannot be directly used for these cases as the numerator G vanishes at the contributing points and V is locally a complete intersection at these points. Luckily, we can decompose the rational function under consideration into two simpler rational functions and analyze them.

Consider the case when a = b > 1, so that we have the generating function relationship

Q a (1, 1; t) = 1 a 4 t 2 ∆F (x, y, t) with F (x, y, t) = yt 2 (y -a)(a -x)(a + x)(ay -x 2 )(y -x)(y + x) (1 -txyS(x, y))(1 -x)(1 -y) ,
and contributing point (1, 1, 1/S(1, 1)). Because we cannot analyze the above diagonal we use a trick, also employed by Melczer and Wilson [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF], to write yx = (1x) -(1y) and see that

F (x, y, t) = yt 2 (y -a)(a -x)(a + x)(ay -x 2 )(y + x) (1 -txyS(x, y))(1 -y) F1(x,y,t) - yt 2 (y -a)(a -x)(a + x)(ay -x 2 )(y + x) (1 -txyS(x, y))(1 -x) F2(x,y,t)
.

As the diagonal operator is linear, we can obtain the desired walk asymptotics by studying ∆F 1 and ∆F 2 . Applying the same arguments as Section 4.3 shows that F 1 admits contributing points with (x, y)-coordinates c ± 13 = (± √ a, 1) while F 2 admits the contributing point with (x, y)-coordinates c 12 = c 123 . The diagonal of F 2 has larger exponential growth, and its numerator does not vanish at the contributing point, meaning Theorem 10.3.4 of Pemantle and Wilson [START_REF] Pemantle | Analytic combinatorics in several variables[END_REF] can be used to determine dominant asymptotics. When b = a 2 the argument is analogous except the numerator contains yx 2 = (1x)(1 + x) -(1y) as a factor and this is used to decompose the diagonal into a sum of two simpler diagonals, which are then analyzed.

Excursion asymptotics

The diagonal expression in Equation ( 21) was obtained through a power series extraction in Equation [START_REF] Fayolle | About a possible analytic approach for walks in the quarter plane with arbitrary big jumps[END_REF]. The reason for the factors (1x) and (1y) in the denominator of the expression to convert the series extraction into a diagonal is to account for terms corresponding to all nonnegative powers of x and y. Thus, the generating function Q a (0, 0; t) = n 0 e (0,0)→(0,0) t n for walks beginning and ending at the origin can be expressed as the diagonal

Q a (0, 0; t) = ∆ (y -b)(a -x)(a + x)(a 2 y -bx 2 )(ay -bx)(ay + bx) a 4 b 3 x 2 y(1 -txyS(x, y)) , (28)
which is the diagonal in Equation ( 20) except for a factor of (1x)(1y) in the denominator. This means that excursion asymptotics are easy to calculate: the singular variety is now smooth and the smooth critical points with (x, y)-coordinates c ± 1 = (±a, b) are always contributing for any non-negative choice of weights a and b. The arguments detailed above then yield the following result.

Theorem 11. For any non-negative weights a, b > 0, the number of excursions e (i,j)→(0,0) (n) has dominant asymptotics

e (i,j)→(0,0) (n) = 4 n n 5 128(j+1)(1+i)(3+i+2j)(2+i+j) a i b j π + O 1 n if n + i ≡ 0 (mod 2), 0 if n + i ≡ 1 (mod 2).
By suitably modifying the diagonal expression one can also calculate asymptotics for walks beginning at any point and ending at any point or axis using the above arguments.

General ending point

As mentioned above, the denominator H(x, y, t) of the diagonal expression obtained for the generating function Q i,j a (x, y; t) for walks ending at (i, j) is the same as the denominator for the walks ending at the origin. This means that all the above results about minimal and critical points continue to hold when i and j are included as parameters. In fact, the degree of vanishing of the numerator at each contributing point is independent of the starting point (i, j), which is why the critical exponents α depend only on the weights a and b. Repeating the above analysis with the numerator G(x, y) replaced by the new expression parametrized by i and j yields the formulas in Appendix A.

Part II

General considerations for weighted models

Restricting ourselves to central weightings results in models that are well suited to an analysis through generating functions, and we begin our discussions in this section by providing different characterizations of central weightings. The characterizations we derive have significant consequences, and we illustrate several of them using our results on GB walks in Section 6. We conclude with some remarks on related properties of the generating functions under consideration.

5 Central weightings

Characterizing central weights

In the first part of this article we considered the GB model under the particular assignment of weights in Equation ( 5). This section gives insights on general weighted models, illustrating our choice of these weights. Here we consider step sets S ⊂ Z d in arbitrary dimension d and given s ∈ S we denote the kth coordinate of s by π k (s). Weights assigned to steps will always be positive.

Recall the following definition of central weights.

Definition 12. A weighting is central if all paths with the same length, start and end points have the same weight.

We give other characterizations of this definition, and see that this is a good framework in which to study weighted models. It leads to natural generating function relations, and permits us to study the asymptotic behaviour in a unified way. A step set S ⊂ Z d is called non-singular if it is not contained in a half-space of R d . Theorem 13. Let S ⊂ Z d be a set of non-singular integer steps of dimension d. A weighting is central if and only if any of the following equivalent statements holds:

(i) For every point (i 1 , . . . , i d ) and number n, each walk starting at the origin and ending at (i 1 , . . . , i d ) in n steps, while staying in R d 0 , has the same weight;

(ii) There exist constants α 1 , . . . , α d and β such that the weight assigned to each step s ∈ S is of the form a s = β d k=1 α π k (s) k ;

(iii) There exist constants α 1 , . . . , α d and β such that

K a (x 1 , . . . , x d ; t) = K(α 1 x 1 , . . . , α d x d ; βt),
where K a (x 1 , . . . , x d ; t) denotes the kernel for a model of walks with a weight a s for each step s ∈ S, and K(x 1 , . . . , x d ; t) the kernel for the unweighted model:

K a (x 1 , . . . , x d ; t) = 1 -t s∈S a s d i=1 x π k (s) k , K(x 1 , . . . , x d ; t) = 1 -t s∈S d i=1 x π k (s) k .
Although most of the induced implications are quite straightforward to show, the proof of this theorem will be postponed to the next subsection; the implications (i) ⇒ (ii) and (i) ⇒ (iii) are quite delicate to prove and require an intermediate definition which is quite long to state (see Proposition 16). In probability theory, the weights a s given in Condition (ii) constitute an exponential change (sometimes called a Cramér transform) of the uniform weights on S.

Example. For the Gouyou-Beauchamps model with weight assignment [START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF], we recover the definition of central weighting via the substitutions α 1 = a, α 2 = b and β = 1. We have lost a degree of freedom by setting β = 1 but it can be simply restored by multiplying the numbers of walks of length n by β n .

Note that Condition (ii) can be expressed in a matrix form. Let M S be the matrix

M S =      π 1 (s 1 ) π 2 (s 1 ) • • • π d (s 1 ) 1 π 1 (s 2 ) π 2 (s 2 ) • • • π d (s 2 ) 1 . . . . . . . . . . . . π 1 (s m ) π 2 (s m ) • • • π d (s m ) 1      , (29)
where S = {s 1 , s

A :=    d j=1 q j t j (q 1 , . . . , q d ) ∈ Q d with d j=1 q j = 1    .
The set A is an affine hyperplane contained in the linear span of {t j } j∈{1,...,d} , so it is an affine subspace of R d with dimension at most d -1. Therefore A, and a fortiori S, is contained in a half-space so the model is singular. Thus, since M S has d + 1 columns, if S is non-singular then the rank of M S equals d + 1.

A combinatorial interpretation of the relations

We now combinatorially interpret the result of Lemma 14 in terms of paths.

Proposition 15. Given a non-singular integer step set S, there exists a subset T of S with d + 1 steps such that for every s ∈ S \ T there are two paths p s and p s in R d (not necessarily R d 0 ) such that:

• p s and p s begin at the origin, and have the same length and the same endpoint;

• p s contains s as a step, with all its other steps belonging to T ;

• p s only uses steps in T .

Example. Consider the Gouyou-Beauchamps model with the set T = {(1, 0), (-1, 0), (1, -1)}. For s = (-1, 1) we can choose p s to be the concatenation of (-1, 1) and (1, -1), and p s to be the concatenation of (1, 0) and (-1, 0).

Proof. By Lemma 14, the rank of M S is d + 1, hence we can find a set T of d + 1 steps such that (π 1 (t), . . . , π d (t), 1) t∈T spans every other vector (π 1 (s), . . . , π d (s), 1). Given a step s ∈ S \ T , the vector (π 1 (s), . . . , π d (s), 1) is then a linear combination of (π 1 (t), . . . , π d (t), 1) t∈T with rational coefficients. Thus, we can multiply this linear combination by the coefficients' common denominator to obtain a relation with only integer numbers. Reorganizing terms according to their signs induces a relation of the form

n s (π 1 (s), . . . , π d (s), 1) + j=1 n s,tj (π 1 (t j ), . . . , π d (t j ), 1) = j=1 n s,t j (π 1 (t j ), . . . , π d (t j ), 1), ( 30
)
where t 1 , . . . , t , t 1 , . . . , t are steps of T and n s , n s,t 1 , . . . , n s,t , n s,t 1 , . . . , n s,t are positive integers.

We prove the proposition by considering p s as any path formed by n s steps of the type s and n s,t j steps of the type t j , and p s as any path formed by n s,t j steps of the type t j .

We can now give a last equivalent definition of central weighting. (iv) for every s ∈ S \ T , the weights (a r ) r∈S satisfy

r∈ps a r = r ∈p s a r , (31)
where the steps are considered with multiplicity inside each product.

Example. We continue the GB example with the aforementioned set T , and paths p s , p s ; Proposition 16 gives

a -1,1 × a 1,-1 = a 1,0 × a -1,0 .
In fact, this relation does not depend (after potential simplification) on the choice of T , p s , or p s .

We can now provide a combined proof of Theorem 13 and Proposition 16.

Proof of Theorem 13 and Proposition 16.

(ii) ⇔ (iii). This equivalence translates an identification of coefficients between polynomials.

Definition 12 ⇒ (i). Obvious: we constrain the starting point to be the origin.

(i) ⇒ (iv). Since S is non-singular, we can find a path starting from the origin and ending at a point arbitrarily far from both the xand y-axes. Thus, we can pick some path p using the steps S such that for every s ∈ S \ T the concatenation of p and p s and the concatenation of p and p s stay in R d 0 . The weighting being central, the weights of these two walks are equal, giving Equation (31) after some simplification.

(iv) ⇒ (ii). Assume that Equation (31) holds. We will prove that the image of the matrix M S defined by Equation ( 29) is equal to the set

E =    (y s ) s∈S ∀s ∈ S \ T , r∈ps y r = r ∈p s y r (considered with multiplicity)    .
A vector (y s ) s∈S in Im(M S ) can be parametrized as

y s = x d+1 + d i=1 π i (s)x i
for s ∈ S and indeterminates x i . For any path q the coefficient of x d+1 in the sum r∈q y r is the length of q, while the coefficient of x k for 1 k d is the kth coordinate of the endpoint of q. As the paths p s and p s coincide at their endpoints and have the same length for every s ∈ S \ T , we see that (y s ) belongs to E. In other words, Im (M S ) ⊆ E.

The equality Im (M S ) = E follows from considering the dimensions of these linear spaces. On one hand, the dimension of Im (M S ) is d + 1 by Lemma 14. On the other hand, the dimension of E is also d + 1 since E is the intersection of |S|d -1 disjoint hyperplanes: the hyperplanes of equations r∈ps y r = r ∈p s y r for s ∈ S \ T . (These hyperplanes are disjoint because r∈ps y r is the only sum involving the coordinate y s , as per the second condition of Proposition 15.) Therefore, Im (M S ) = E. Applying logarithms to [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] shows that (log(a s )) s∈S belongs to E, and thus to Im (M S ), so that there exist constants α 1 , . . . , α d and β satisfying condition (ii) of Theorem 13.

(ii) ⇒ Definition 12. For s ∈ S and a walk w, we denote by n s (w) the number of steps of type s contained in w. The weight of a walk w of length n starting at (i 1 , . . . , i d ), ending at (j 1 , . . . , j d ) and staying in

R d 0 is s∈S a ns(w) s = β s∈S ns(w) d k=1 α s∈S π k (s) ns(w) k = β n d k=1 α j k -i k k .
This number does not depend on w, so the weighting is central. Summarizing example. We illustrate how these results allow one to efficiently characterize central weightings by considering the (non-small) step set S = {(2, 2), (1, 1), (-1, 0), (0, -1)}. First, one finds a pair of paths satisfying Proposition 15. In this case, we can take p as the sequence of steps (

, and p as the path formed of five times the step (1, 1). Thus, thanks to Proposition 16, all central weightings satisfy

a -1,0 a 3 2,2 a 0,-1 = a 5 1,1 . (32)
In Figure 4, the left-hand side of this equation is encoded by a lattice path in black, while the right-hand side is encoded by a path in white. We can compute α 1 , α 2 and β in terms of a 2 2,2 , a 0,-1 and a 1,1 by solving the system

    2 2 1 1 1 1 -1 0 1 0 -1 1       log(α 1 ) log(α 2 ) log(β)   =     log(a 2,2 ) log(a 1,1 ) log(a -1,0 ) log(a 0,-1 )     We find α 1 = a 2 2,2 a 0,-1 /a 3 1,1 , α 2 = a 2 1,1 /a 2,2 a 0,-1 and β = a 2 1,1 /a 2,2 .

Equivalence classes of weightings

Theorem 13 can be generalized to models where the original step set is weighted, enabling us to define equivalence classes among weighted models of walks. Let W (i 1 ,...,i d )→(j 1 ,...,j d ) (n) be the set of walks of length n starting at (i 1 , . . . , i d ), ending at (j 1 , . . . , j d ) and staying in R d 0 . For s ∈ S and a walk w, we denote by n s (w) the number of steps of type s contained in w. The probability of a given walk w ∈ W

(i 1 ,...,i d )→(j 1 ,...,j d ) (n) among the walks of length n is s∈S a ns(w) s   w ∈W (i 1 ,...,i d )→(j 1 ,...,j d ) (n) s∈S a ns(w ) s   .
Theorem 17. Let S be a set of non-singular integer steps of dimension d. Consider two weightings (a s ) s∈S and (a s ) s∈S on this step set. Then the following statements are equivalent:

(i) The probability of any path (starting at the origin, staying in R d 0 , with fixed length) on the steps in S is the same when weighted according to (a s ) or (a s );

(ii) There exist constants α 1 , . . . , α d and β such that the weight assigned to each step s ∈ S is of the form a s = a s β d k=1 α π k (s) k ;

(iii) There exist constants α 1 , . . . , α d and β such that

K a (x 1 , . . . , x d ; t) = K a (α 1 x 1 , . . . , α d x d ; βt),
where K a (x 1 , . . . , x d ; t) denotes the kernel for the weighting a s , and K a (x 1 , . . . , x d ; t) the kernel for the weighting (a s );

(iv) If (p s , p s ) s∈S\T denote pairs of paths satisfying Proposition 15 then, for every s ∈ S \ T ,

r∈ps a r a r = r ∈p s a r a r , (33)
where the steps are considered with multiplicity.

Two weightings are said to be equivalent if they satisfy one of the above statements.

Thus, a central weighting is a weighting that is equivalent to the unweighted model (1) s∈S (note that condition (i) is equivalent to Definition 12 because every walk of length n has the same probability of occurring in the unweighted case). The proof of the previous theorem is analogous to the proofs discussed above. Furthermore, the theorems in the next subsection can be easily generalized to pairs of equivalent (not necessarily central) weightings.

Generating function relations

One of our motivations for central weightings is that they induce very simple relations between the generating functions of a centrally weighted model and an unweighted model. Generalizing from the bivariate case, we define

Q(x 1 , . . . , x d ; t) := w walk starting at (0,...,0) ending at (i 1 ,...,i d ) with n steps staying in N d x i 1 1 . . . x i d d t n (34)
and

Q a (x 1 , . . . , x d ; t) :=
w walk starting at (0,...,0) ending at (i 1 ,...,i d ) with n steps staying in N d s∈S a ns(w)

s x i 1 1 . . . x i d d t n , (35)
where n s (w) denotes the number of steps s used by the walk w.

α -i 1 1 . . . α -i d d β -n .
But we know that n = s∈S n s (w) and that i k = s∈S π k (s) for every k ∈ {1, . . . , d}. Hence, by reorganizing the factors, we observe that this coefficient is equal to w) .

w walk ending at (i 1 ,...,i d ) with n steps s∈S a s α -π 1 (s) 1 α -π 2 (s) 2 . . . α -π d (s) d β -1 ns(
If the weights a s form a central weighting, then this is equal to the number of walks ending at (i 1 , . . . , i d ) with n steps, which is the coefficient of

x i 1 1 . . . x i d d t n in Q a (x 1 , . . . , x d ; t).
From this quick observation, and the closure of D-finite functions under algebraic substitution, we obtain the following result. It is interesting to compare this corollary and point (iv) of Theorem 17 with the works of Kauers and Yatchak [START_REF] Kauers | Walks in the quarter plane with multiple steps[END_REF]. Indeed, the models which they show to have finite group (and D-finite generating function) obey relations of the form appearing in Equation [START_REF] Lecouvey | Central measures on multiplicative graphs, representations of Lie algebras and weight polytopes[END_REF]. This means that the families of walks described in their paper actually correspond to equivalence classes associated to fixed models, with the exception of their Family 0 which contains an uncountable number of equivalence classes. The representatives of the families of walks appearing in Kauers and Yatchak [START_REF] Kauers | Walks in the quarter plane with multiple steps[END_REF] are shown in Figure 5.

Excursions

We can also easily deduce from Proposition 18 the following property on excursions, which shows in particular that the subexponential behaviours for the number of excursions for central weightings must all coincide. 5.6 Conjectures about the converse

; t) = Q(α 1 x 1 , . . . , α d x d ; βt),
then the weighting a is central and

a s = β d k=1 α π k (s) k .
In the particular case of random walks coming from root systems of Lie algebras, Conjecture 21 was proven by Lecouvey and Tarrago [START_REF] Lecouvey | Central measures on multiplicative graphs, representations of Lie algebras and weight polytopes[END_REF].

Conjecture 21 would imply that there is only one function K satisfying the kernel equation for any model. In dimension d = 2 this would imply that the kernel equation K(x, y; t)Q(x, y; t) = xy + K(x, 0; t)Q(x, 0; t) + K(0, y; t)Q(0, y; t) -K(0, 0; t)Q(0, 0; t) admits a unique solution K = K, demonstrating an inherent connection between kernels and generating functions of lattice path models.

The conjecture can be reformulated purely in terms of the unweighted model.

Conjecture 22.

Let w i 1 ,...,i d (n) be the number of (unweighted) walks with n steps starting at the origin, ending at (i 1 , . . . , i d ) and staying in N d . Assume that there exists a family of constants (µ s ) s∈S such that for every (d + 1)-tuple (i 1 , . . . , i d , n) the relation

s∈S µ s w i 1 -π 1 (s),...,i d -π d (s) (n -1) = 0 (37)
holds. Then for every s ∈ S, µ s = 0. Proof. The idea is to inject the recurrence relations satisfied by the numbers of walks, such as

w i 1 ,...,i d (n) = s∈S w i 1 -π 1 (s),...,i d -π d (s) (n -1),
into Equation [START_REF] Melczer | Asymptotic lattice path enumeration using diagonals[END_REF]. Some basic calculations then show that Equation [START_REF] Melczer | Asymptotic lattice path enumeration using diagonals[END_REF] implies Equation [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF] with

µ s = a s -β d k=1 α π k (s) k
. Thus, if Conjecture 22 holds µ s = 0 for every s ∈ S, which proves Conjecture 21.

In practice, given a particular model of walks it is easy to verify Conjecture 22. We can compute the numbers w i 1 ,...,i d (n) and build the system of equations s∈S w i 1 -π 1 (s),...,i d -π d (s) (n -1) × µ s = 0 with unknowns µ s , indexed by (i 1 , . . . , i d , n). This system is infinite, but in practice we restrict it to small values of n. The null vector is always a solution. If it is the only one, then Conjecture 22 holds for the model under consideration.

We have computationally verified that this conjecture is satisfied for all the 2D models with small steps in the quadrant. This conjecture can also be proven for certain families of configurations.

Proposition 24. Let S be a set of small steps such that (1, 1, . . . , 1) ∈ S. Then Conjecture 22 holds for that particular model. Proof. We prove by induction on j 0 that for every step s ∈ S,

d k=1 π k (s) n -j ⇒ µ s = 0.
When j = 0 the only step satisfying this inequality is s = (1, 1, . . . , 1). By setting (i 1 , . . . , i d , n) = (1, . . . , 1, 1), Equation (37) becomes µ (1,1,...,1) = 0.

We now assume that the induction hypothesis is true for j -1 and let s 0 ∈ S be a step such that d k=1 π k (s 0 ) = nj. We will consider Equation ( 37) with (i 1 , . . . , i d , n) = (1 + π 1 (s 0 ), 1 + π 2 (s 0 ), . . . , 1 + π d (s 0 ), 2).

In order to efficiently index the sum in Equation [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF], we let T denote the set of steps s ∈ S such that w 1+π 1 (s 0 )-π 1 (s),...,1+π d (s 0 )-π d (s),2 = 0.

For every s ∈ T , there exists s ∈ S such that π k (s ) = 1 + π k (s 0 )π k (s) for all k ∈ {1, . . . , d}. In particular, by summing the previous identity over all k ∈ {1, . . . , d}, we get

d k=1 π k (s) = n + (n -j) - d k=1 π k (s ).
If s = s 0 , then s = (1, 1, . . . , 1). In that case d k=1 π k (s ) < n and d k=1 π k (s) > nj, so we can use the induction hypothesis on s to prove that µ s = 0. Therefore every term that is not indexed by s = s 0 in Equation [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF] vanishes for the evaluation (1 + π 1 (s 0 ), 1 + π 2 (s 0 ), . . . , 1 + π d (s 0 ), 2). As a consequence we obtain µ s 0 = 0, which proves the induction hypothesis.

The minimal number of steps to prove the conjecture

If Conjecture 22 turns out to be true, it is also natural to wonder about the minimal bound N S on n such that Equation [START_REF] Melczer | Asymptotics of lattice walks via analytic combinatorics in several variables[END_REF] holding for n up to N S implies that µ s = 0 for all s ∈ S. In terms of generating functions, N S is the minimal integer n such that when the equality in Conjecture 21 holds up to order n then the conclusion in the conjecture holds.

For example, for the Gouyou-Beauchamps model we can prove that N S = 3. Indeed, with n = 1 we can only prove that µ (1,0) = 0; then with n = 2 we only have the restriction µ (-1,1) = µ (-1,0) = 0. The equality µ (1,-1) = 0 comes at n = 3. This is due to the fact that a path in R 2 0 that contains (1, -1) must have a length at least equal to 3. If S has only small steps and (1, 1, . . . , 1) ∈ S, we refer to the proof of Proposition 24 to see that N S = 2.

We have verified that N S 4 for every 2D model with small steps. Each time that N S = 4, like for S = {(1, 0), (-1, 1), (-1, -1)}, this particular value of N S is forced by the fact that a particular step must be included in paths of length at least 4; for {(1, 0), (-1, 1), (-1, -1)} this step is (-1, -1).

It can be shown that N S = 2 d is reached for some models with small steps in dimension d, such as S = {(1, 0, . . . , 0), (-1, 1, 0, . . . , 0), . . . , (-1, -1, -1, . . . , 1), (-1, -1, -1, . . . , -1)}.

It thus seems reasonable that N S 2 d for every model S with small steps in dimension d. Unfortunately, the number N S does not appear to be related to the maximal value over all elements s ∈ S of min{ 0 | there exists a path of length containing s}.

Indeed, there exist some models with a high number of symmetries where N S exceeds that value. It is also for these particular models that Conjecture 22 seems hard to prove. For example, the 16-step model S # in dimension 4 composed of the 4 base steps (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1) and the 12 coordinates permutations of the vector (-1, 1, 1, 0) has N S # = 4, although every step in S # can be used in a path of length 2.

6 When does drift define a universality class?

Introduction

It is natural to ask how the drift of a step set affects the asymptotic behaviour of a model, and weighted models provide a good environment to explore this question since the weight parameters can vary continuously and sweep across drift profiles. One consequence of Theorem 13 is that in two dimensions every generic central weighting can be defined by only two parameters up to a uniform scaling of weights. In this section, as in Part I, the scaling is chosen in such a way that the constant β defined in Theorem 13 is equal to 1. Here we study how, for a given unweighted two dimensional model, the asymptotic formulas of the model endowed with central weights depends on these two parameters. This allows us to visualize universality classes defined by a model. As discussed above, there are known and conjectured formulas for the exponential growth and critical exponent of different lattice path models. They depend to some extent on the drift of the step set, although in general the critical exponent is not completely determined by the drift.

In the case of equivalence classes of models defined by (scaled) central weights, however, the drift alone is enough to decide the form of the first term of the asymptotic expansion. That is, in these cases, the drift (as a function of the weights) defines the regions of universality classes. Considering for example the GB model, Figure 6 shows this correlation between drift and universality class.

n -5 n -3 2 n 0 n -3 2 n -3 2 n -1 2 n -1 2 n -3 n -3
The exact formulas for exponential growth given by Garbit and Raschel [START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF] depend on the minimum of a Laplace transform, defined below, in the cone dual to the cone in which the walks lie. Building on this work, Garbit, Mustapha and Raschel [START_REF] Garbit | Random walks with drift in cones[END_REF] have a conjecture for the critical exponent. We consider their conjectures in the case of the GB model, and in the next subsection show that these are the same conditions which distinguish cases in the ACSV analysis. This family of examples provides strong support for their conjecture.

The ACSV approach given in Part 1 is applicable to many of the lattice path models with Dfinite generating functions. The connection between these two approaches is interesting because the results of Garbit, Mustapha and Raschel are conjectured to hold for any (non-singular) model. This suggests that the structure of the generating functions of the non-D-finite models might resemble the D-finite models: for instance they may be positive parts of (non-rational) meromorphic functions which can be described "simply" in terms of each model's steps.

The conjecture of Garbit, Mustapha and Raschel

We now present the conjecture of Garbit, Mustapha and Raschel (specialized for our setting). We begin by introducing some notation. Let a s 1 ,s 2 be the weight of the step (s 1 , s 2 ), and S(x, y) be the inventory S(x, y)

= (s 1 ,s 2 )∈S a s 1 ,s 2 x s 1 y s 2 .
Remark 25. Although the conjecture of Garbit, Mustapha and Raschel is formulated in terms of the Laplace transform L(x, y) = (s 1 ,s 2 )∈S a s 1 ,s 2 e s 1 x+s 2 y , in order to be consistent with our previous notation we state it in terms of the inventory S(x, y). Observe that both functions are linked by the relation S(x, y) = L(ln(x), ln(y)), so the translation is quite straightforward.

∇S(x * , y * ) = 0 (i.e., (x * , y * ) = (x s , y s ))

S x (x * , y * ) = 0 or S y (x * , y * ) = 0 S x (x * , y * ) > 0 and S y (x * , y * ) > 0 (x * , y * ) = (1, 1) S(1, 1) n n -p 1 /2 balanced S(1, 1) n n -1/2 axial S(1, 1) n n 0 free x * = 1 or y * = 1 S(x s , y s ) n n -p 1 /2-1 transitional min{S(x 1 , 1), S(1, y 1 )} n n -3/2 directed (not possible)
x * > 1 and y * > 1 S(x s , y s ) n n -p 1 -1 reluctant (not possible) (not possible)

Table 3: Conjectured value of the exponential growth and connective constant for two dimensional models in the cone R 2 0 . Here (x s , y s ) is the unique positive critical point of the inventory S(x, y), S(x, 1) is minimized at x 1 , S(1, y) is minimized at y 1 and p 1 = π/ arccos(-c) where c is the covariance factor. Observe that when (x * , y * ) = (1, 1), the vector (S x (x * , y * ), S y (x * , y * )) is the drift of the model. 3 gives a formal definition of the six different classes of walks we mentioned in Part I for the GB walks: balanced, reluctant, transitional, directed, axial and free walks. These adjective describe the qualitative nature of the walks, for example a free walk behaves as if it is unrestrained whereas a reluctant walk behaves like an excursion ending at the origin. In practice, for a central weighting of the form a i,j = a i b j , it is quite easy to describe these six regions. The free region always corresponds to the walks where the drift is doubly positive; the axial region corresponds to the case where the drift is positive on one coordinate, null on the other one; and the balanced case corresponds to the walk with a zero drift. For the reluctant case, one has to compute the minimum (x s 0 , y s 0 ) of the unweighted inventory S 0 (x, y) = (s 1 ,s 2 )∈S x s 1 y s 2 . The reluctant region is defined by a < x s 0 and b < y s 0 , while the transitional region is defined by a < x s 0 and b = y s 0 , or a = x s 0 and b < y s 0 . Finally, the remaining region corresponds to the directed case.

Moreover, Table

Connecting back to ACSV

As we saw in Section 3 the generating function of the GB model has a strong structure coming from its representation as a rational diagonal, which allows for a detailed analysis. There exists a close relationship between the ACSV and probabilistic approaches for all models with small steps where such a diagonal representation is possible. Conjecture 29. If S is one of the 19 small step lattice path models with a finite non-zero orbit sum then the divisions for the universality classes of centrally weighted walk models are given by Conjecture 27.

Although the tools of ACSV should allow one to prove Conjecture 29, there are technical difficulties which can arise. Additionally, one must find the smallest non-zero constant C k when Proposition 10 is used to compute asymptotics around minimal critical points under different weight regimes, which can be a tedious computation for each of the 19 weighted models. Instead, we highlight the connection between Conjecture 27 and ACSV, and mention the ingredients necessary for a proof of Conjecture 29.

Recall Equation [START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF] and Lemma 8, which imply that the radius of convergence of the GB generating function Q a (t) is the supremum of |xyt| over all minimal critical points. It is easy to verify this for most7 of the 19 models with small steps, since their generating functions can be usually be expressed as the diagonal part of a rational function of the form G(x, y, t) (1 -xytS(x, y))(1x) (1y) ,

where S is the inventory of the walk model. By Proposition 4, a critical point must belong to the variety 1 -xytS(x, y) = 0. Hence, by eliminating t we reduce the problem to the study of the supremum of |S(x, y) -1 | over all minimal points; i.e., points satisfying 0 < |x| 1 and 0 < |y| 1.

For non-singular models this supremum is actually achieved at a point (x, y) = ((x * ) -1 , (y * ) -1 ) in Q. We then observe a correspondence between the different regions of universality (see Table 3) and the different strata (see Subsection 4.2):

• If the minimum of S is achieved in the interior of Q, the walk model is reluctant. Thus, since S(x, y) -1 is maximized over all minimal critical points at a point (x, y) satisfying |x| < 1 and |y| < 1, the contributing points must belong to V 1 .

• If the minimum of S is achieved at a point such that x = 1 or y = 1 (but not both), then the walk model is either directed, or transitional. Similarly, the two corresponding strata are V 12 or V 13 , depending whether the maximum is achieved on the x-axis, or the y-axis.

• Finally, if the minimum is achieved at (1, 1), then we are either in the free, axial, or balanced case. The contributing point belongs thus to V 123 .

By this reasoning we recover the exponential growths in Table 3. To find the critical exponents we must follow the approach described in Subsection 4.4 and apply Proposition 10. This is the step that permits the distinction between the directed and transitional cases, and between the free, axial and balanced cases. As in the GB case, there may be simplifications between numerator and denominator in the borderline cases (i.e., transitional, axial and balanced). In summary, ACSV allows one to verify Conjecture 27 with explicit computations, including leading asymptotic constants. There is also a strong connection between the three rows of Table 3 and the different strata. However, it is hard to predict from ACSV without doing the actual calculations the values of the critical exponents, and the distinction induced by the three columns of Table 3. It is our hope to understand Conjecture 27 better via a more advanced ACSV approach, and extend the proof to non-D-finite generating functions.

Drift diagrams for universality classes

We end with some additional examples of diagrams for universality classes, to compare against the Gouyou-Beauchamps model.

Example. Consider the model defined by the step set {(1, 0), (-1, 1), (0, -1)}, dubbed the Tandem model due to its applications in queuing theory. As it has only three steps, all positive weightings are central. We consider the following family of central weightings: As in the GB model, there is a breakdown of cases for the contributing singularities based on where one finds critical minimal points. The drift of the weighted model is (ab/a, b/a -1/b), and the critical exponent of the model can be determined directly from it. Of note is that the region defining the reluctant universality class is not a cone.

Although the drift diagram for the Tandem model does not separate into regions which are cones, there are models where this occurs. Consider for example the Gessel model with weights

(-1, 0) → a -1 ,
(1, 0) → a, (1, 1) → ab, (-1, -1) → a -1 b -1 .

It can be shown that this model is reluctant if and only if a < 1 and b < 1. In terms of the drift (d x , d y ), this means that the reluctant region is defined by the cone 2d yd x < 0 and 2d xd y < 0. Gouyou-Beauchamps and Gessel walks in the quarter plane are in bijection with simple walks (i.e., walks with step set {(1, 0), (-1, 0), (0, 1), (0, -1)}) staying in cones of angles π/4 and 3π/4, respectively. When examining the drift diagram of these models in these new cones (see Figure 8) one observes that the reluctant region has an angle equal to 3π/4 and π/4, respectively. This means that the regions corresponding to directed walks are cones of angle π/2, a phenomenon which also occurs for the simple walk itself. The reluctant region is thus the polar cone to the free region. We do not know any simple explanation of this fact, however we can prove that these three models are the only models of simple walks (on a square lattice) in a two dimensional cone that have this structure.

Nice decompositions into cones also occur for the drift diagram of Double Tandem and Double Kreweras models of Bousquet-Mélou and Mishna [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF], when we describe them as simple walks on a triangular lattice in cones of angles π/3, and 2π/3. As an open question, we wonder if there exists a general explanation to this phenomenon of simple walks in different cones. For example, can it happen in higher dimensions?

Conclusion

Central weightings provide a simple but efficient way to understand the shifts in asymptotic behaviour of weighted lattice path models. They put the conjecture of Garbit, Mustapha and Raschel in a new light, and have strong connections to areas of combinatorics, probability theory, and the random generation of discrete structures.

All of the small step weighted D-finite models in two dimensions found by Kauers and Yatchak [29] consist of a centrally weighted equivalence class, except for their family 0 (which consists of an infinite number of equivalence classes). It is thus natural to wonder how many equivalence classes of D-finite models-with larger steps or in higher dimensions-exist, and how many equivalence classes contain an unweighted model (families 2 and 3 of Kauers and Yatchak do not contain an unweighted model).

Furthermore, there are still many open problems for walks with small steps in a quadrant. For example, it is still unknown for many unweighted lattice path models whether the univariate generating function Q(1, 1; t) of walks with no constraint on the endpoint is D-finite. For the models in which this question is still open, one would expect the univariate generating function to be non-D-finite, since the trivariate generating function Q(x, y; t) is not [START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF]. With our formalism we can see that there exist models with an infinite number of non-D-finite evaluations Q(α 1 , α 2 ; t) of the generating function. Indeed, any central weighting of a model such that arccos(-c) is not commensurate with π (see [START_REF] Pemantle | Asymptotics of multivariate sequences. I. Smooth points of the singular variety[END_REF] for the definition of c) will work by a result of Duraj [START_REF] Duraj | Random walks in cones: the case of nonzero drift[END_REF], which implies that the critical exponent for the model is not rational8 . Proposition 18 relates the non-Dfinite generating function of the weighted model and the evaluated unweighted generating function Q(α 1 , α 2 ; t). Corollary 30. There are an infinite number of two dimensional weighted lattice models with non-D-finite generating function.

Finally, the present work could be useful for the studies of specific models of walks. As an example, it would be interesting to understand the model with simple steps ((±1, 0), (0, ±1)) in cones with an angle θ, potentially not commensurable with π. When is such a model D-finite and what are the different universality classes?

Figure 1 :

 1 Figure 1: Generic central weighting of the Gouyou-Beauchamps step set. Note that (b/a)(a/b) = 1 = a/a.

FreeFigure 2 :

 2 Figure 2: The polynomial growth (n -α in Theorem 1) for the weighted GB model given as a function of the weight parameters a and b. Each region corresponds to a universality class. The boundaries of the 2-dimensional regions, and their intersection form distinct regions.

Figure 3 : 1 √ 2

 312 Figure 3: Two uniformly sampled GB walks on 800 steps: an unweighted (balanced) model (left) and a weighted (reluctant) model with parameters a = 1 √ 2 and b = 1 (right).

1

  |xy|S(|x|,|y|) ; the cases when only (1y) or both (1x) and (1y) are canceled are analogous.

Example 6 . 1 ∂x y ∂H 1 ∂y

 611 On the stratum V 1 , Proposition 4 implies that the critical points are those where the matrix x ∂H is rank deficient. Calculating the 2 × 2 minors of this matrix implies that (x, y, t) is a critical point if and only if yt(∂S/∂x)(x, y) -xytS(x, y) = -xytS(x, y) and xt(∂S/∂y)(x, y) -xytS(x, y) = -xytS(x, y).

Proposition 9 .

 9 For given weights a, b > 0, the set of contributing points consists of the unique points (x, y, t) whose (x, y)-coordinates are • c ± 1 when a 1 and b 1; • c 12 when a > 1 and a b; • c ± 13 when b > 1 and b a 2 ; • c 123 when b > a > √ b > 1.

Proposition 10 (

 10 Hörmander [28, Theorem 7.7.5] & Pemantle and Wilson [43, Lemma 13.3.2]). Suppose that the functions A(θ) and φ(θ) in d variables are smooth in a neighbourhood N of the origin and that

1 ,

 1 (b/a)e iθ ) (b/a) 2 e 2iθ (1 -(b/a)e iθ ) and φ(x, y) = log S(1, a/b)log S 1, (a/b)e -iθ .

Proposition 16 .

 16 Consider a non-singular integer step set S in R d , along with a set T and the corresponding |S| -|T | = |S|d -1 pairs of paths (p s , p s ) s∈S\T described in Proposition 15.A weighting is central if and only if

Figure 4 :

 4 Figure 4: Given the step set S = {(2, 2), (1, 1), (-1, 0), (0, 1)}, the path in black and the path in white satisfy the conditions of Proposition 15. Remark that they encode the left-and right-hand sides of Equation (32), respectively.

Corollary 19 .

 19 The multivariate generating functions for an unweighted model and any weighted version with a rational central weighting are either both D-finite or both non-D-finite.

Corollary 20 .

 20 Given a central weighting of the form a s = β d k=1 α π k (s) k , the number of excursions e a (n) in the weighted model is related to the number of excursions e(n) in the unweighted model by the relation e a (n) = β n e(n).Proof. The generating function of excursions is obtained from the generating function of general walks by settingx 1 = • • • = x d = 0.The corollary can then be deduced from Theorem 13.

Figure 5 :

 5 Figure 5: Equivalence class representatives corresponding to the families of walks with D-finite generating functions given by Kauers and Yatchak [29]; unlabeled steps have weight 1.

Proposition 23 .

 23 Conjecture 22 implies Conjecture 21.

Figure 6 :

 6 Figure 6: The universality classes as a function of drift for the centrally weighted family of the GB model given by (5): (1, 0) → a, (-1, 0) → a -1 , (-1, 1) → a -1 b, (1, -1) → ab -1 . Because the regions are cones the diagram does not change when each weight is multiplied by a constant, meaning this diagram holds for every central weighting.

2 Figure 7 : 2 Figure 8 : 4 (

 27284 Figure 7: The universality classes as a function of drift for the centrally weighted family of the Tandem model given by (40): (1, 0) → a, (-1, 1) → a -1 b, (0, -1) → b -1 .

  1x and 1y in H(x, y, t) do not cancel with factors in the numerator G(x, y, t). By the definition of absolute convergence, the point (x, y, t) ∈ D if and only if (|x|, |y|, |t|) ∈ D. Furthermore, |xyt| -1 decreases as |t| grows, hence by Lemma 3 the function |xyt| -1 is minimized on D ∩ R 3 + at points of the form (x, y, xyS(x, y) -1 ) with 0 < x, y 1. Thus, it is sufficient to show

	that the minimizer of	S(x, y) =	a x	+	ay bx	+	bx ay	+	x a

  Proposition 18. Let Q a (x 1 , . . . , x d ; t) be the generating function of a model under a central weighting a s = β d k=1 α π k (s) k , and Q(x 1 , . . . , x d ; t) the generating function of unweighted walks with the same set of steps. Then Q a (x 1 , . . . , x d ; t) = Q(α 1 x 1 , . . . , α d x d ; βt). Proof. Let (i 1 , . . . , i d , n) be a (d + 1)-tuple of non-negative integers. Extracting the coefficient of x i 1 1 . . . x i d d t n in the series Q a (x 1 /α 1 , . . . , x d /α d ; t/β) gives

		(36)
		a ns(w) s
	w walk ending	s∈S
	at (i 1 ,...,i d ) with n steps

  It is natural to ask if the converse of Proposition 18 is also true: are the central weightings the only weightings that satisfy Equation (36)? This is not clear, and we formulate the following conjecture.Conjecture 21. Let S be any step set and a be any positive weighting. If there exist constants α 1 , . . . , α d , β such that Q a (x 1 , . . . , x d

	5.6.1 Statement of the conjectures

An excursion is a walk starting and ending at precise points. Very often it implies starting and ending at the origin.

In the quadrant case, V (i, j) = 0 whenever i < 0 or j < 0.

The algebraic kernel method, which relies on rational maps fixing a certain Laurent polynomial related to a lattice path model, is closely related to the more classical kernel method in which one manipulates roots of a Laurent polynomial (see Banderier and Flajolet[START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF] for a modern illustration of the classical kernel method).

Technically, the chains of integration used can be quasi-local chains, meaning they are homologous to chains which can be taken to be arbitrarily close to the points we consider, except at points which will not matter in the calculation of dominant asymptotics. A rigorous definition of these quasi-local cycles in the framework of Morse theory is given in Lemma 8.2.4 of Pemantle and Wilson[START_REF] Pemantle | Analytic combinatorics in several variables[END_REF].

The computations are available for download at at http://weighted-walks.gforge.inria.fr

The set Q is the image of the quarter plane (R 0 ) 2 under the transformation (x, y) → (e x , e y ), coming from the fact that the results of Garbit and Raschel[START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF] and Garbit et al.[START_REF] Garbit | Random walks with drift in cones[END_REF] minimize the Laplace transform L(x, y) instead of the characteristic polynomial S(x, y). For a walk confined to a more general cone K, one must compute the minimum of the characteristic polynomial on the image of the dual cone K * under the map (x, y) → (e x , e y ). Note that the quarter plane is self-dual.

The rational functions corresponding to some models have denominators which additionally contain one of the polynomials x 2 + a 2 and x 2 + ax + a 2 as factors. These polynomials do not introduce new critical points but may affect minimality of existing critical points for certain values of a, complicating the analysis.

Any D-finite lattice path generating function is an example of a G-function, meaning in particular that the number of lattice walks cannot have asymptotic growth of the form Cρ n n α , with α irrational. More details can be found in the work of Bostan, Raschel and Salvy[START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF] which used this argument to show the non-D-finiteness of excursion generating functions Q(0, 0; t).

Acknowledgments KR would like to thank C. Lecouvey and P. Tarrago for interesting discussions concerning their work [33]. KR would also like to thank R. Garbit for enlightening discussions. MM and JC were partially supported by Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant 31-611453. JC was also supported by the Pacific Institute for the Mathematical Sciences and by the French "Agence Nationale de la Recherche", project A3 ANR-08-BLAN-0190. SM was partially supported by an NSERC Canadian Graduate Scholarship and a David R. Cheriton Graduate Scholarship. Finally, the authors would like to thank the anonymous reviewers for their valuable comments.

For a non-singular model, S(x, y) has a unique positive critical point (x s , y s ) that satisfies S x (x s , y s ) = S y (x s , y s ) = 0; note that this critical point is a function of the weights. For the GB model with weights given by Figure 1 we have

We define the covariance factor

The value of c is used to determine the exponential growth, and also appears in the formula for the critical exponent. When we consider only central weightings, the value of c in Equation ( 39) does not depend on the weights a i,j . For example, every centrally weighted GB model has c = -

2 . Lemma 26. For any centrally weighted model, the covariance factor c in [START_REF] Pemantle | Asymptotics of multivariate sequences. I. Smooth points of the singular variety[END_REF] does not depend on the weights.

Lemma 26 follows from straightforward calculations after using Theorem 13 to write the weight assigned to (s 1 , s 2 ) ∈ S in the form βa s 1 b s 2 . We remark that the exponential growth in the reluctant case is given by S(x s , y s ) and, evaluating this, it is clear how cancellation gives a value independent of the weights.

Let Q be the quarter plane defined by

Their conjecture states that the universality classes are defined by (x * , y * ), the minimum of the inventory S on the cone 6 Q: S(x * , y * ) = min (x,y)∈Q

S(x, y).

The minimizing point is unique by the strict convexity of the Laplace transform. The minimum is achieved at the critical point (x s , y s ) when this point is in the region, otherwise it is achieved on the boundary of Q.

Conjecture 27 (Garbit, Mustapha and Raschel [START_REF] Garbit | Random walks with drift in cones[END_REF]). Suppose that S is a non-singular step set. Then [t n ]Q(1, 1; t) has critical exponent defined by Table 3.

Remark 28. The exponential growths stated here have been proven by Garbit and Raschel [START_REF] Garbit | On the exit time from a cone for random walks with drift[END_REF]. Moreover, Duraj [START_REF] Duraj | Random walks in cones: the case of nonzero drift[END_REF] established exact asymptotic estimates in the case of an interior point (x * , y * ), which corresponds to a reluctant universality class.

Theorem 1 verifies the conjecture for GB walks with a central weighting. For these models, p 1 = π/ arccos( √ 2/2) = 4 and the different regions of universality classes depend either on the drift, or on the signs of x -1 = a -1 -1 and y -1 = b -1 -1. For instance, ∇S(x * , y * ) = (0, 0) is true if and only if a 1 and b 1.

A Values of the harmonic function

We now give the values of the universal constant κ and harmonic function V [n] (i, j) for the various models.

Balanced a = b = 1 Here κ = 8 π and

Here κ = 1 and V [n] (i, j) = (j + 1)(i + 1)(i + 3 + 2j)(i + 2 + j)b -j .

Transitional 2 (b = 1, a > 1) Here κ = 8 3π and V [n] (i, j) = a -i (j + 1)(i + 1)(i + 3 + 2j)(i + 2 + j) 1 (1a) 2 + (-1) n+i (1 + a) 2 .