# Walks in the Quarter Plane with Multiple Steps

Manuel Kauers¹† and Rika Yatchak¹‡

¹RISC, Johannes Kepler University, Linz, Austria

**Abstract.** We extend the classification of nearest neighbour walks in the quarter plane to models in which multiplicities are attached to each direction in the step set. Our study leads to a small number of infinite families that completely characterize all the models whose associated group is D4, D6, or D8. These families cover all the models with multiplicites 0, 1, 2, or 3, which were experimentally found to be D-finite — with three noteworthy exceptions.

**Résumé.** Nous étendons la classification des marches aux plus proches voisins dans le quart de plan à des modèles dans lesquels une multiplicité est attachée à chaque direction de l'ensemble des pas. Notre étude identifie un petit nombre de familles infinies qui caractérisent complétement tous les modèles dont le groupe est D4, D6 ou D8. Ces familles contiennent tous les modèles à multiplicités 0, 1, 2 ou 3 dont il a été prouvé expérimentalement qu'ils étaient D-finis — avec trois exceptions notables.

**Keywords:** Lattice Walks, D-finiteness, Computer Algebra

## 1 Introduction

We consider quadrant walk models where step sets may contain several distinguishable steps pointing into the same direction. For example, the step sets {$\leftarrow, \downarrow, \nearrow$} and {$\leftarrow', \downarrow, \nearrow$} are considered different, as the latter contains two different ways of going to the left. The objects being counted are then walks in the quarter plane starting at the origin, consisting of $n$ consecutive steps taken from the step set in such a way that the walk never leaves the first quadrant, ending at a point $(i, j) \in \mathbb{N}^2$ (with the convention $0 \in \mathbb{N}$), and one of $k$ different colors is attached to each step in the walk whose multiplicity in the step set is $k$. For each model (viz., for each multiset of admissible directions), we want to know whether the corresponding generating function $f(x, y, t) = \sum_{n=0}^{\infty} \sum_{i,j} f_{i,j,n} x^i y^j t^n$ which counts the number $f_{i,j,n}$ of walks of length $n$ ending at $(i, j)$ is D-finite. As usual, a power series in $t$ is D-finite if it satisfies an ordinary linear differential equation with polynomial coefficients. If we let $a_{u,v}$ denote the multiplicity of the direction $(u, v) \in \{-1, 0, 1\}^2 \setminus \{(0, 0)\}$, then the number $f_{i,j,n}$ of walks of length $n$ ending at $(i, j)$ is uniquely determined by the recurrence equation

$$f_{i,j,n+1} = \sum_{u,v} a_{u,v} f_{i-u,j-v,n} \quad (n \in \mathbb{N}, i, j \in \mathbb{N})$$

<footnote>†Email: mkauers@risc.jku.at. Partially supported by the Austria FWF grants Y464-N18 and F50-04.</footnote>

<footnote>‡Email: ryatchak@risc.jku.at. Partially supported by the Austria FWF grant F50-04</footnote>
together with the initial values $f_{0,0,0} = 1$, $f_{i,j,0} = 0$ for $(i,j) \neq (0,0)$, and the boundary conditions $f_{-1,j,n} = f_{i,-1,n} = 0$ for all $i,j,n$. Equivalently, we can say that the generating function $f(x, y, t) = \sum_{n=0}^{\infty} \sum_{i,j} f_{i,j,n} x^i y^j t^n \in \mathbb{Q}[x, y][[t]]$ satisfies the functional equation

$$ \left(1 - t \sum_{u,v} a_{u,v} x^u y^v\right) f(x, y, t) = 1 - \frac{t}{y} \left(\sum_u a_{u,-1} x^u\right) f(x, 0, t) - \frac{t}{x} \left(\sum_v a_{-1,v} y^v\right) f(0, y, t) + \frac{t a_{-1,-1}}{xy} f(0, 0, t). \quad (1) $$

For the models where all multiplicities $a_{u,v}$ are in $\{0, 1\}$, a complete classification is available: among the $2^8 = 256$ different models, Bousquet-Mélou and Mishna (2010) identified 79 nontrivial cases. For 22 of them they prove that the generating function is D-finite using certain groups $G$ associated to each of the models. For a 23rd model, the notorious Gessel model $\{\leftarrow, \to, \nearrow, \swarrow\}$, their techniques do not apply but a proof by a different method based on computer algebra was found by Bostan and Kauers (2010). A computer-free proof was later found by Bostan et al. (2013). The remaining 56 models are not D-finite: Mishna and Rechnitzer (2009) and Melczer and Mishna (2013) showed that the generating functions of five of these models have infinitely many singularities and therefore are not D-finite. For the remaining models, Bostan et al. (2014b) proved that the counting sequences $f_{0,0,n}$ for walks returning to the origin have asymptotic behaviour for $n \to \infty$ that D-finite functions cannot possibly have.

The need for a classification of quarter plane models with multiplicities arose in the classification project for octant models in 3D (Bostan et al., 2014a), as it turns out that some models in 3D can be reduced by projection to 2D models with multiplicities. For example, it is easy to see that the generating function for the octant model with step set $\{(\begin{pmatrix} -1 \\ 0 \end{pmatrix}, \begin{pmatrix} -1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ -1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \end{pmatrix}\}$ is D-finite if and only if the quadrant model with step set $\{\leftarrow, \leftarrow', \downarrow, \nearrow\}$ is. Bostan et al. (2014a) have classified only the 527 models that they needed for their study, and point out that the classification problem for models with multiplicities is of interest in its own right. If the multiplicities are real numbers in the interval $[0, 1]$ whose sum is 1, they can be interpreted as probabilities of random walks. If the multiplicities $a_{i,j}$ are left symbolic, then $f_{i,j,n}$ is a polynomial in which the coefficient of $\prod_{u,v} a_{u,v}^{e_{u,v}} \cdots a_{1,1}^{e_{1,1}}$ indicates how many walks there are in which the direction $(u, v)$ is used $e_{u,v}$ many times, for all $u, v$.

For the present paper we carried out a systematic search over all the $4^8 = 65536$ models where each of the eight directions may have any of the four multiplicities 0, 1, 2, 3. Of these, 30307 are nontrivial and essentially different. Of these nontrivial models, 1457 turn out to be D-finite. 79 of the D-finite models are even algebraic. Going one step further, we have identified families of D-finite models in which some or all of the “multiplicities” are arbitrary complex numbers. Rather than asking for a fixed model what the corresponding group is, we ask for a fixed group what all the models leading to this group are. In this way we obtain a small number of families that completely characterize all the models which lead to groups with at most eight elements. This characterization covers 1454 of the 1457 D-finite cases we discovered for multiplicities in $\{0, 1, 2, 3\}$. The remaining three models have a group of order 10, which was too hard for us to analyze in full generality. In view of the fact that all models previously considered had either a finite group of order at most eight or an infinite group, the appearance of these models was a surprise to us. We were less surprised to find, after spending some 6.5 years of computation time, that none of the models with a (probably) infinite group appears to be D-finite based on the inspection of the first 5000 terms.
## 2 Models of Interest

Our reasoning largely follows that of Bousquet-Mélou and Mishna (2010). Their first step is to identify the interesting models. By a model, we understand here a particular choice of multiplicities $a_{u,v} \in \mathbb{C}$ (not necessarily integers). For each such model, there is a corresponding generating function $f(x, y, t) \in \mathbb{C}[x, y][[t]]$, and we want to identify the models whose generating functions are D-finite.

A model is uninteresting if $a_{1,-1} = a_{1,0} = a_{1,1} = 0$ or $a_{-1,1} = a_{0,1} = a_{1,1} = 0$ or $a_{-1,-1} = a_{-1,0} = a_{-1,1} = 0$ or $a_{-1,-1} = a_{0,-1} = a_{1,-1} = 0$, because in either of these cases the corresponding generating function is algebraic and it is well-understood why (Flajolet and Sedgewick, 2009, Section VII.8). Secondly, if two models can be obtained from one another by reflecting the step set about the diagonal $x = y$, then the corresponding generating functions can be obtained from one another by exchanging the variables $x \leftrightarrow y$, and therefore either both are D-finite or neither is. Similarly, if one model can be obtained from another by multiplying all multiplicities by a nonzero constant $\lambda$, then its generating function can be obtained from the generating function of the other by sending $t$ to $\lambda t$, and therefore again either both are D-finite or neither is.

Applying all these filters to the $4^8 = 65536$ models with possible multiplicities $a_{u,v} \in \{0, 1, 2, 3\}$ leaves us with 30307 nontrivial models (including, for the sake of completeness, the 79 interesting models with $a_{u,v} \in \{0, 1\}$ that have already been completely classified).

## 3 The Group of the Model

For a fixed model, i.e., for a fixed choice of multiplicities $a_{u,v} \in \mathbb{C}$, consider the functional equation (1). The group associated to the model acts on this equation. Its elements map the variables $x$ and $y$ to certain rational functions in $x$ and $y$, which are chosen in such a way that all the group elements leave the kernel polynomial

$$K(x, y, t) := 1 - t \sum_{u,v} a_{u,v} x^u y^v$$

fixed. It is easy to check that the two particular transformations $\Phi, \Psi: \mathbb{C}(x, y) \to \mathbb{C}(x, y)$ defined by

$$\Phi: (x, y) \mapsto \left( \frac{1}{x} \frac{\sum_v a_{-1,v} y^v}{\sum_v a_{1,v} y^v}, y \right), \quad \Psi: (x, y) \mapsto \left( x, \frac{1}{y} \frac{\sum_u a_{u,-1} x^u}{\sum_u a_{u,1} x^u} \right)$$

have this property. It is also easy to check that $\Phi$ and $\Psi$ are involutions, i.e., $\Phi^2 = \Psi^2 = \text{id}$.

The group $G$ is defined as the group generated by $\Phi$ and $\Psi$ under composition.

Note that we do not need to worry that one of the denominators $\sum_u a_{u,1}x^u$ or $\sum_v a_{1,v}y^v$ is identically zero, because this only happens for models that are uninteresting in the sense of the previous section. For the same reason, we may also assume that the numerators $\sum_u a_{u,-1}x^u$ and $\sum_v a_{-1,v}y^v$, respectively, are nonzero polynomials. In order to argue that the composition of rational functions into the power series of equation (1) is algebraically meaningful, recall that the series in question belong to $\mathbb{Q}[x, y][[t]]$, so the result of the composition can be naturally interpreted as an element of $\mathbb{C}(x, y)[[t]]$.

The group $G$ is finite if and only if $(\Phi\Psi)^n = \text{id}$ for some $n \in \mathbb{N}$, and this is the case if and only if $G$ is the dihedral group with $2n$ elements. The sign $\operatorname{sgn}(g)$ of an element $g \in G$ is defined to be 1 if $g = (\Phi\Psi)^k$ for some $k$, and $-1$ otherwise.

Our definition for $G$ corresponds to the notion of the “group of the walk” in Bousquet-Mélou and Mishna (2010). This notion was in turn inspired by the “group of the random walk”, a well-known tool
in the probabilistic context that was introduced by Malyshev and further detailed in Fayolle et al. (1999). The two definitions are not identical, but the group of the random walk can be interpreted as a quotient group of G. Recent results regarding the finiteness of the group of the random walk can be found in Fayolle and Raschel (2011); Fayolle and Iasnogorodski (2014).

## 4 Models with Group D4

As there is obviously no way to choose $a_{u,v}$ such that $\Phi\Psi = (\frac{1}{x}r(y), \frac{1}{y}s(x)) = (x, y) = \text{id}$, the smallest possible $n \in \mathbb{N}$ with $(\Phi\Psi)^n = \text{id}$ is 2. The group with $(\Phi\Psi)^2 = \text{id}$ is the dihedral group D4 with four elements. In order to determine the models which lead to this group, regard the $a_{u,v}$ as variables and compute $(p, q) := \Phi(\Psi(x, y)) - \Psi(\Phi(x, y))$. This is a pair of rational functions in $x, y$ whose coefficients are rational functions in the $a_{u,v}$ over the rational numbers. Write $p, q$ as quotients of polynomials in $x, y$ whose coefficients are polynomials in $a_{u,v}$ with integer coefficients. We want to know the possible choices of $a_{u,v}$ for which $p$ and $q$ become zero. (Note that $\Phi\Psi = \Psi\Phi \iff (\Phi\Psi)^2 = \text{id}$ because $\Phi$ and $\Psi$ are involutions.) In order to find these $a_{u,v}$, consider the ideal in $\mathbb{Q}[a_{-1,-1}, \dots, a_{1,1}]$ generated by the coefficients of all monomials $x^i y^j$ in the numerator of $p$ and the coefficients of all monomials $x^i y^j$ in the numerator of $q$. This ideal basis consists of 36 homogeneous polynomials of degree 4, which we don't reproduce here because of its length. Using Gröbner basis techniques (Becker et al., 1993), we can determine the irreducible components of the radical of this ideal. We have used the commands `facstd` and `minAssGTZ` of the software package Singular (Greuel and Pfister, 2002) for this step. It turns out that the two irreducible components are generated by

$$ \{ a_{0,1}a_{1,-1} - a_{0,-1}a_{1,1}, a_{-1,1}a_{1,-1} - a_{-1,-1}a_{1,1}, a_{-1,1}a_{0,-1} - a_{-1,-1}a_{0,1} \}, \text{ and} $$

$$ \{ a_{1,0}a_{-1,1} - a_{-1,0}a_{1,1}, a_{1,-1}a_{-1,1} - a_{-1,-1}a_{1,1}, a_{1,-1}a_{-1,0} - a_{-1,-1}a_{1,0} \}. $$

As the latter is obtained from the former by replacing all $a_{u,v}$ by $a_{v,u}$, it suffices to consider one of the two components, say the first. The equations in this component are equivalent to saying that the vectors $(a_{-1,-1}, a_{0,-1}, a_{1,-1})$ and $(a_{-1,1}, a_{0,1}, a_{1,1})$ are linearly dependent. Since the models where one or both of these vectors are zero are uninteresting, the interesting models leading to the group D4 are precisely those for which there exists a constant $\lambda \neq 0$ such that $a_{-1,v} = \lambda a_{1,v}$ for $v = -1, 0, 1$. We then have

$$ \Phi(x, y) = \left( \frac{\lambda}{x}, y \right) \quad \text{and} \quad \Psi(x, y) = \left( x, \frac{1}{y} \frac{\lambda a_{1,-1} x^{-1} + a_{0,-1} + a_{1,-1} x}{\lambda a_{1,1} x^{-1} + a_{0,1} + a_{1,1} x} \right). $$

At this point, we can proceed analogously to Bousquet-Mélou and Mishna (cf. their Proposition 5): multiplying (1) on both sides by $xy/K(x, y, t)$ and forming the orbit sum gives the general relation

$$ \sum_{g \in G} \operatorname{sgn}(g) g(xy f(x, y, t)) = \frac{1}{K(x, y, t)} \sum_{g \in G} \operatorname{sgn}(g) g(xy), $$

which holds whenever the group is finite. For the special case under consideration, the right hand side evaluates to

$$ \frac{1}{K(x, y, t)} \left( xy - \frac{y\lambda}{x} - \frac{x\lambda a_{1,-1} x^{-1} + a_{0,-1} + a_{1,-1} x}{y\lambda a_{1,1} x^{-1} + a_{0,1} + a_{1,1} x} + \frac{\lambda}{xy} \frac{\lambda a_{1,-1} x^{-1} + a_{0,-1} + a_{1,-1} x}{\lambda a_{1,1} x^{-1} + a_{0,1} + a_{1,1} x} \right) \\ = \frac{(x^2 - \lambda)(a_{0,1}xy^2 - a_{0,-1}x - (\lambda + x^2)(a_{1,-1} - a_{1,1}y^2))}{xy(a_{1,1}(\lambda + x^2) + a_{0,1}x)K(x, y, t)}. $$
For the left hand side, we have

$$xy f(x, y, t) - \frac{\lambda y}{x} f\left(\frac{\lambda}{x}, y, t\right) - \frac{x}{y} s(x) f\left(x, \frac{1}{y} s(x), t\right) + \frac{\lambda}{xy} s(x) f\left(\frac{\lambda}{x}, \frac{1}{y} s(x), t\right),$$

where we abbreviate $s(x) = \frac{\lambda a_{1,-1} x^{-1} + a_{0,-1} + a_{1,-1} x}{\lambda a_{1,1} x^{-1} + a_{0,1} + a_{1,1} x}$. The identity holds in $\mathbb{Q}(x, y)[[t]]$, but it can be seen that all quantities actually belong to $\mathbb{Q}(x)[y, y^{-1}][[t]]$. The last two terms of the equation involve only negative exponents with respect to $y$, so taking the positive part $[y^>]$ will kill them. The remaining terms happen to belong to $\mathbb{Q}[x, x^{-1}][[t]]$, and since the second term only has negative exponents with respect to $x$, taking the positive part $[x^>]$ will eliminate it and only leave the first. It follows that

$$f(x, y, t) = \frac{1}{xy}[x^>][y^>]\frac{(x^2 - \lambda)(a_{0,1}xy^2 - a_{0,-1}x - (\lambda + x^2)(a_{1,-1} - a_{1,1}y^2))}{xy(a_{1,1}(\lambda + x^2) + a_{0,1}x)K(x, y, t)}.$$

Alternatively, we could interpret the elements of $\mathbb{Q}(x, y)[[t]]$ as elements of multivariate formal Laurent series field $\mathbb{Q}_<((x, y, t))$ for a term order $\le$ with $x, y \le 1 \le t$ and do the positive part extraction with respect to $x$ and $y$ simultaneously. See Aparicio Monforte and Kauers (2013) for a discussion of formal Laurent series in several variables. In any case, we can summarize the result of this section as the following theorem. A similar characterization already appears as Lemma 4.1.1 in Fayolle et al. (1999).

**Theorem 1** The interesting quarter plane models whose group is D4 are precisely those where $a_{-1,v} = \lambda a_{1,v}$ for $v = -1, 0, 1$ and some $\lambda \neq 0$. All these models are D-finite.

### Family 0

Defining equations:

$$a_{1,0}a_{-1,1} = a_{-1,0}a_{1,1},$$

$$a_{1,-1}a_{-1,1} = a_{-1,-1}a_{1,1},$$

$$a_{-1,1}a_{-1,0} = a_{-1,-1}a_{1,0}$$

Example:

<figure><img src="image_1.png" /></figure>

## 5 Models with Group D6

We now determine all the choices for $a_{u,v}$ such that $(\Phi\Psi)^3 = \text{id}$. As before, we compute $(p, q) := \Psi(\Phi(\Psi(x, y))) - \Phi(\Psi(\Phi(x, y)))$ and consider the ideal generated by the coefficients of the numerators with respect to $x, y$. The basis consists of 210 homogeneous polynomials of degree 9. The ideal has 34 irreducible components, 18 of which turn out to contain only uninteresting models. Of the remaining 16 components, 6 can be discarded because their solution sets are properly contained in the solution set of others. Of the remaining 10 components, 4 can be discarded because they are reflections of others. This leaves us with the following 6 families:
<table><thead><tr><th>Family 1a</th><th>Example:</th><th>Family 1b</th><th>Example:</th></tr></thead><tbody><tr><td>Defining equations:<br>a<sub>1,1</sub> = a<sub>-1,-1</sub> = 0,<br>a<sub>-1,1</sub>a<sub>1,-1</sub> = a<sub>-1,0</sub>a<sub>1,0</sub> = a<sub>0,1</sub>a<sub>0,-1</sub></td><td>3<br>5<br>1/2</td><td>Defining equations:<br>a<sub>-1,-1</sub> = a<sub>-1,1</sub> = 0,<br>a<sub>-1,0</sub>a<sub>1,0</sub> = a<sub>-1,-1</sub>a<sub>1,1</sub> = a<sub>0,-1</sub>a<sub>0,1</sub></td><td>1/2<br>1/3<br>1/5<br>2</td></tr><tr><td>Family 2a</td><td>7<br>5<br>1 2 1</td><td>Family 2b</td><td>1 2 1<br>5<br>7 7</td></tr><tr><td>Defining equations:<br>a<sub>1,0</sub> = a<sub>1,1</sub> = 0,<br>a<sub>0,-1</sub>a<sub>-1,1</sub> = 2a<sub>0,1</sub>a<sub>-1,-1</sub>,<br>a<sub>0,-1</sub><sup>2</sup> = 4a<sub>1,-1</sub>a<sub>-1,-1</sub>,<br>a<sub>0,-1</sub>a<sub>0,1</sub> = 2a<sub>-1,1</sub>a<sub>1,-1</sub></td><td>7 7<br>1 2 1</td><td>Defining equations:<br>a<sub>1,0</sub> = a<sub>-1,-1</sub> = 0,<br>a<sub>0,1</sub>a<sub>-1,-1</sub> = 2a<sub>0,-1</sub>a<sub>-1,1</sub>,<br>a<sub>0,1</sub><sup>2</sup> = 4a<sub>1,1</sub>a<sub>-1,1</sub>,<br>a<sub>0,1</sub>a<sub>0,-1</sub> = 2a<sub>-1,-1</sub>a<sub>1,1</sub></td><td>1 2 1<br>5<br>7 7</td></tr><tr><td>Family 3a</td><td>1 2 1<br>7 7</td><td>Family 3b</td><td>7 7<br>1 2 1</td></tr><tr><td>Defining equations:<br>a<sub>-1,0</sub> = a<sub>-1,-1</sub> = 0,<br>a<sub>0,1</sub>a<sub>1,-1</sub> = 2a<sub>0,-1</sub>a<sub>1,1</sub>,<br>a<sub>0,1</sub><sup>2</sup> = 4a<sub>-1,1</sub>a<sub>1,1</sub>,<br>a<sub>0,1</sub>a<sub>0,-1</sub> = 2a<sub>-1,-1</sub>a<sub>-1,1</sub></td><td>1 2 1<br>5<br>7 7</td><td>Defining equations:<br>a<sub>-1,0</sub> = a<sub>-1,1</sub> = 0,<br>a<sub>0,-1</sub>a<sub>1,1</sub> = 2a<sub>0,1</sub>a<sub>-1,-1</sub>,<br>a<sub>0,-1</sub><sup>2</sup> = 4a<sub>-1,-1</sub>a<sub>-1,1</sub>,<br>a<sub>0,-1</sub>a<sub>0,1</sub> = 2a<sub>1,1</sub>a<sub>-1,-1</sub></td><td>7 7<br>5<br>1 2 1</td></tr></tbody></table>

Note that the families on the right can be obtained from those on the left by reflection about the horizontal axis and the families in the third row can be obtained from those in the second row by reversing all arrows. The families in the first row are closed under reversing arrows.

**Theorem 2** The interesting quarter plane models whose group is D6 are precisely those that belong to one or more of the families described in the table above. All these models are D-finite.

The remainder of this section is devoted to the D-finiteness claim of this theorem.

## 5.1 Families 1a, 2a, 3a

These families can be handled very much like the family in Section 4 above. Without going into further details, we just report the resulting formulas for the generating functions.

For family 1a, let $\lambda = a_{-1,1}a_{1,-1} = a_{-1,0}a_{1,0} = a_{0,1}a_{0,-1}$. If $\lambda \neq 0$, then all the $a_{u,v}$ are nonzero (except $a_{1,1}$ and $a_{-1,-1}$ of course). In this case, the resulting formula for the generating function is

$$f(x, y, t) = \frac{1}{xy}[x>y^2] \frac{(a_{-1,1} - a_{0,-1}xy^{-2})(a_{1,-1} - a_{-1,0}yx^{-2})(\lambda xy - a_{-1,0}a_{0,-1})}{\lambda^2 K(x, y, t)}.$$

Otherwise, if $\lambda = 0$ and $a_{-1,1} = 0$, then $a_{-1,0} \neq 0$ and $a_{0,1} \neq 0$ (otherwise the model is not interesting), but then $a_{1,0} = 0$ and $a_{0,-1} = 0$ (by the defining equations), and then $a_{1,-1} \neq 0$ (otherwise again the model is not interesting). In this case, the resulting formula for the generating function is

$$f(x, y, t) = \frac{1}{xy}[x>y^2] \frac{(a_{0,1} - a_{1,-1}xy^{-2})(a_{1,-1} - a_{-1,0}x^{-2}y)(a_{0,1}xy - a_{-1,0})}{a_{0,1}^2 a_{1,-1} K(x, y, t)}.$$
Finally, if $\lambda = 0$ and $a_{-1,1} \neq 0$, then $a_{1,-1} = 0$ and the only interesting cases have $a_{1,0} \neq 0$, $a_{0,-1} \neq 0$, and $a_{-1,0} = a_{0,1} = 0$. This case is symmetric to the previous case and therefore not interesting.

For family 2a, we may assume that $a_{-1,1} \neq 0$, because otherwise the model is uninteresting. Then we can also assume $a_{0,1} \neq 0$, because if $a_{0,1} = 0$, then the last defining equation would imply $a_{-1,1} = 0$, which together with $a_{1,1} = 0$ would also render the model not interesting. Under the assumption $a_{1,-1} \neq 0$, $a_{0,1} \neq 0$, the generating function can be expressed as

$$f(x, y, t) = \frac{1}{xy[x>y]} \frac{P(x, y)(a_{-1,-1} - a_{1,-1}x^2 + a_{-1,1}y^2 + a_{-1,0}y)(2a_{0,1}y^2 - 2a_{1,-1}x - a_{0,-1})}{4x^2y^3a_{0,1}^2a_{1,-1}K(x, y, t)}$$

where $P(x, y) = 2a_{-1,-1} - 2a_{0,1}xy^2 + a_{0,-1}x + 2a_{-1,1}y^2 + 2a_{-1,0}y$.

For family 3a, models are interesting only when $a_{-1,1} \neq 0$ and $a_{0,-1} \neq 0$ and $(a_{1,-1}, a_{1,0}, a_{1,1}) \neq (0, 0, 0)$. Under these assumptions, we obtain the following expression for the generating function:

$$f(x, y, t) = \frac{1}{xy[x>y]} \frac{Q(x, y)(a_{0,1}y^2 - 2a_{0,-1} + 2a_{-1,1}y^2/x)(a_{1,1}x^2y + a_{1,0}x^2 + a_{1,-1}x^2/y - a_{-1,1}y)}{(a_{1,-1} + a_{1,0}y + a_{1,1}y^2)(4a_{-1,1}a_{0,-1} + (2a_{-1,1} + a_{0,1}x)Q(x, y))K(x, y, t)}$$

where $Q(x, y) = 2a_{1,1}xy^2 + 2a_{1,0}xy + 2a_{-1,1}x + a_{0,1}y^2 - 2a_{0,-1}$. Note that in this case the denominator contains nontrivial factors involving both $x$ and $y$, so the ad-hoc reasoning used in Section 4, which also works for the families 1a and 2a, does not work here. However, there is no problem if we take the viewpoint of multivariate Laurent series (Aparicio Monforte and Kauers, 2013), because all that is needed for the argument to go through is the property that there exists a term order $\le$ so that for all $g \in G \setminus \{\text{id}\}$ and all positive integers $i, j$ the expansion of $g(x)^i g(y)^j \in \mathbb{C}(x, y)$ in the multivariate Laurent series field $\mathbb{C}_\le((x, y))$ contains no terms $x^k y^\ell$ where both $k$ and $\ell$ are positive. This turns out to be the case.

## 5.2 Family 1b

For the family 1b there are three cases to distinguish. First, when $a_{-1,-1} = a_{1,0} = a_{0,1} = 0$, then $a_{1,1}, a_{-1,0}, a_{0,-1}$ all must be nonzero in order for the model to be interesting. In this case, the generating function is

$$f(x, y, t) = k \left( \sqrt[3]{a_{0,-1}a_{1,1}/a_{-1,0}^2} x, \sqrt[3]{a_{-1,0}a_{1,1}/a_{0,-1}^2} y, \sqrt[3]{a_{-1,0}a_{0,-1}a_{1,1}} t \right),$$

where $k(x, y, t)$ is the generating function for classical Kreweras walks (i.e., $a_{1,1} = a_{-1,0} = a_{0,-1} = 1$), which is known to be algebraic (Kreweras, 1965; Bousquet-Mélou, 2005). Secondly, when $a_{1,1} = a_{-1,0} = a_{0,-1} = 0$, algebraicity of the generating function can be established by a similar argument. The third case is when $a_{1,1}, a_{-1,-1}, a_{1,0}, a_{-1,0}, a_{0,1}, a_{0,-1}$ are all nonzero. In this case it is impossible to express the generating function in terms of the generating function for the corresponding model without multiplicities, known as the double Kreweras model. However, if we let $f_\lambda(x, y, t)$ be the generating function for the family where $a_{-1,-1} = a_{-1,0} = a_{0,-1} = 1$ and $a_{1,1} = a_{1,0} = a_{0,1} = \lambda \neq 0$, then

$$f(x, y, t) = f_{a_{0,1}a_{1,0}^2/(a_{0,-1}a_{1,1}^2)} \left( \frac{a_{1,1}}{a_{0,1}}, \frac{a_{1,1}}{a_{1,0}}, \frac{a_{-1,-1}a_{1,1}^2}{a_{0,1}a_{1,0}} t \right)$$

is the generating function of an arbitrary model of family 1b with $a_{1,1}a_{-1,-1} \neq 0$. It therefore suffices to show that $f_\lambda(x, y, t)$ is D-finite. We will show that it is in fact algebraic, following the treatment in Section 6.3 of Bousquet-Mélou and Mishna (2010) with the added parameter $\lambda$. Since the orbit sum is zero,
we sum (1) over only half the orbit to obtain a nonzero expression on both sides. This new expression will be more complicated than in the orbit sum case: it will involve the unknown series $f_\lambda(x, y, t)$, $f_\lambda(x, 0, t)$ and $f_\lambda(0, 0, t)$. Using careful coefficient extraction, we will obtain the algebraicity result.

Writing $A_v = \sum_u a_{u,v} x^u$ for $v = -1, 0, 1$, the half-orbit sum equation reads

$$xy f_{\lambda}(x, y, t) - \frac{1}{\lambda x} f_{\lambda}\left(\frac{1}{\lambda x y}, y\right) + \frac{1}{\lambda y} f_{\lambda}\left(\frac{1}{\lambda x y}, x\right) = \frac{xy - \frac{1}{\lambda x} + \frac{1}{\lambda y} - 2txA_{-1}f_{\lambda}(x, 0, t) + tf_{\lambda}(0, 0, t)}{K(x, y, t)}.$$

Next we extract the coefficient of $y^0$ using Lemma 7 from Bousquet-Mélou and Mishna (2010). We solve $K(x, y, t) = 0$ for $y$ in terms of $x$ and $t$: writing $\Delta(x) := t^2 x^{-2} - 2(t+2\lambda t^2)x^{-1} + (1-6\lambda t^2) - 2\lambda t(1+2t)x + \lambda^2 t^2 x^2$ for the discriminant of $K(x, y, t)$, the two solutions are $Y_0 = (1-tA_0 - \sqrt{\Delta(x)})/(2tA_0)$ and $Y_1 = 1/(\lambda x Y_0)$. The coefficient of $y^n$ in $1/K(x, y, t)$ can be expressed in terms of $Y_0$, $Y_1$, and $\Delta(x)$:

$$[y^n] \frac{1}{K(x, y, t)} = \frac{1}{\sqrt{\Delta(x)}} \times \begin{cases} Y_0^{-n} & \text{if } n \le 0 \\ Y_1^{-n} & \text{if } n \ge 0 \end{cases}.$$

Using these facts, extracting the coefficient of $y^0$ on both sides of the half-orbit sum equation leads to

$$-\frac{1}{\lambda x} d_{\lambda}\left(\frac{1}{\lambda x}, t\right) = \frac{1}{\sqrt{\Delta(x)}}\left(xY_0 - \frac{1}{\lambda x} + \frac{1}{\lambda Y_1} - 2txA_{-1}f_{\lambda}(x, 0, t) + tf_{\lambda}(0, 0, t)\right), \quad (2)$$

where $d_\lambda(x, t) := \sum_{i,n} (f_\lambda)_{i,i,n} x^i t^n$ is the generating function for walks ending on the diagonal.

Now we write $\Delta(x) = \frac{t^2}{Z^2} \Delta_-(x) \Delta_+(x)$, where

$$\Delta_+(x) = 1 - \frac{2\lambda Z(1 + 2Z + 2\lambda Z^2 + 2\lambda^2 Z^3 + \lambda^2 Z^4)}{(1 - \lambda Z^2)^2} x + \lambda^2 Z^2 x^2, \quad \Delta_-(x) = \Delta_+(\frac{1}{x}),$$

and where $Z \in \mathbb{Q}[\lambda][t]$ is defined through $Z = \frac{t(1+3\lambda Z^2+4\lambda(1+\lambda)Z^3+3\lambda^2 Z^4+\lambda^3 Z^6)}{(1-\lambda Z^2)^2}$ and $Z(0) = 0$.

Multiplying (2) by $A_1 \sqrt{\Delta_-(x)}$ and using the explicit expressions for $Y_0$ and $Y_1$ given above, we obtain

$$\sqrt{\Delta_-(x)} \left( \frac{x}{t} - \frac{1}{\lambda x} A_1 d_\lambda \left( \frac{1}{\lambda x}, t \right) \right) = \frac{ZA_1}{t\sqrt{\Delta_+(x)}} \left( \frac{x(1-tA_0)}{tA_1} - \frac{1}{x\lambda} - 2tA_{-1}f_\lambda(x, 0, t) + tf_\lambda(0, 0, t) \right).$$

From this equation, we extract the coefficient of $x^0$. Using $[x^0]d_\lambda(\frac{1}{\lambda x}, t) = [x^0]f_\lambda(x, 0, t) = f_\lambda(0, 0, t)$, we find

$$f_{\lambda}(0, 0, t) = \frac{Z - 4\lambda Z^3 - 2\lambda Z^4 - 2\lambda^2 Z^4 - \lambda^2 Z^5}{t(1 - \lambda Z^2)^2}.$$

We can now extract the positive part in $x$ on both sides of the same equation to obtain

$$f_{\lambda}(x, 0, t) = \frac{x^2(\lambda Z^2 - 1) + 2xZ(\lambda Z + 1) - \lambda Z^3 + Z}{2\lambda tx(x+1)^2Z(1-\lambda Z^2)} \sqrt{\Delta_+(x)} \\ - \frac{Z}{2t(1+x)} \left( \frac{\lambda tx^3 + 2tx + t - x^2}{\lambda tx(x+1)Z} + \frac{2(\lambda^2 Z^3 + \lambda(Z+3)Z^2 - 1)}{(1-\lambda Z^2)^2} + 1 \right).$$

Noting that $f_\lambda(0, y, t) = f_\lambda(y, 0, t)$, we conclude from equation (1) that $f_\lambda(x, y, t)$ is algebraic.
## 5.3 Families 2b, 3b

The orbit sum argument also fails for these families. For the models in family 2b the orbit sum is zero, while in family 3b the orbit sum is nonzero but the desired term $f(x, y, t)$ cannot be isolated by taking the positive part because there are group elements $g \neq id$ for which $f(g(x), g(y), t)$ also contributes terms with positive exponents to the orbit sum. Because of the lack of symmetry, the half orbit sum argument used for family 1b does not seem to apply either.

One model from each of these two families were already encountered by Bostan et al. (2014a), and computer proofs have been given there that the generating function for the model belonging to family 2b is algebraic and the model belonging to family 3b is (transcendental) D-finite. The models considered by Bostan et al. (2014a) are $a_{1,0} = a_{1,-1} = a_{-1,0} = 0$, $a_{-1,1} = \frac{1}{2}a_{0,1} = a_{1,1} = a_{-1,-1} = a_{0,-1} = 1$ (case 2b), and its reverse $a_{-1,0} = a_{-1,1} = a_{1,0} = 0$, $a_{1,-1} = \frac{1}{2}a_{0,-1} = a_{-1,-1} = a_{1,1} = a_{0,1} = 1$ (case 3b).

We were able to extend these computer proofs to the more general cases where $a_{-1,0} = \lambda$ (case 2b), and $a_{1,0} = \lambda$ (case 3b), respectively, are formal parameters. From here, every other model of the respective family can be reached by an appropriate algebraic substitution: if $f_\lambda(x, y, t)$ is the generating function for the model $a_{1,0} = a_{1,-1} = a_{-1,0} = 0$, $a_{-1,1} = \frac{1}{2}a_{0,1} = a_{1,1} = a_{-1,-1} = a_{0,-1} = 1$, $a_{-1,0} = \lambda$, then

$$f(x, y, t) = f_{a_{-1,0}/\sqrt{a_{-1,-1}a_{-1,1}}} \left( \frac{a_{0,-1}}{a_{-1,-1}} x, \sqrt{\frac{a_{-1,1}}{a_{-1,-1}}} y, \frac{1}{2} \sqrt{\frac{a_{-1,-1}}{a_{-1,1}}} t \right)$$

is the generating function for an arbitrary model of family 2b, and likewise for family 3b.

The computational techniques we used were introduced by Kauers and Zeilberger (2008); Kauers et al. (2009); Bostan and Kauers (2010), and they have been described for the cases $\lambda = 0$ in the paper of Bostan et al. (2014a). We do not repeat these explanations again but only remark that the additional symbolic parameter $\lambda$ has made the calculations considerably more expensive. The computations were done using software of Kauers (2009) and Koutschan (2010). The bottleneck was the construction of a certified recurrence for $(f_\lambda)_{0,0,n}$. The (nonminimal) recurrence we found has order 14 and degrees 30, 26 in $n$, $\lambda$, respectively; the certificate for this recurrence is 16 gigabytes long! From this recurrence it can be deduced that $f_\lambda(0, 0, t)$ is the unique formal power series $T \in \mathbb{Q}[\lambda][[t]]$ with $T(0) = 1$ and

$$t^4 T^2 + (2t\lambda + 1)t^2 T + t(4t + 1) - (3t^2(\lambda - 4) + 3t + 1)Z + t(6t + 1)(\lambda + 2)Z^2 = 0,$$

where $Z \in \mathbb{Q}[\lambda][[t]]$ is the unique formal power series with $Z(0) = 0$ and $t = \frac{Z(4Z+1)}{1+6Z+12Z^2+4(2+\lambda)Z^3}$. Using this equation and the functional equation (1) (with $f_\lambda$ in place of $f$), we could then prove the correctness of guessed polynomial equations $P(x, t, \lambda, f_\lambda(x, 0, t)) = Q(y, t, \lambda, f_\lambda(0, y, t)) = 0$, which in turn can be used to deduce that $f_\lambda(x, 0, t)$ is the unique formal power series $U \in \mathbb{Q}[x, \lambda][[t]]$ with $U(0) = 1$ and

$$(x+1)^2 t^4 U^2 + (2t\lambda - x + 1)t^2 U + t(t(x+4)+1) - (3t^2(\lambda - 4) + 3t + 1)Z + t(6t+1)(\lambda+2)Z^2 = 0$$
and that $f_\lambda(0, y, t)$ is $(-1 + \sqrt{1 + tyV})/(ty)$ where $V$ is the unique formal power series $V \in \mathbb{Q}[y, \lambda][[t]]$ with $V(0) = 1$ and

$$(\lambda y + y^2 + 1)^2 t^4 V^2 + (4t^2(6t+1)(\lambda+2)yZ^2 - 4ty(3t^2\lambda - 12t^2 + 3t+1)Z + t(6t^2\lambda y^2 + 4t^2\lambda + 2t^2y^3 + 18t^2y - 2t\lambda y + 2ty^2 + 4ty + 2t - y))V + t(4t\lambda y + ty^2 + 16t + 2y + 4) - 4(3t^2\lambda - 12t^2 + 3t+1)Z + 4(6t+1)t(\lambda+2)Z^2 = 0.$$
Together with the functional equation, it finally follows that $f_{\lambda}(x, y, t)$ is algebraic.

For the generating function $\tilde{f}_{\lambda}(x, y, t)$ of the model with $a_{-1,0} = a_{-1,1} = a_{0,1} = 0$, $a_{-1,-1} = \frac{1}{2}a_{0,-1} = a_{1,-1} = a_{1,1} = a_{0,1} = 1$, $a_{1,0} = \lambda$ from family 3b, we have that $\tilde{f}_{\lambda}(0, 0, t) = f_{\lambda}(0, 0, t)$ (for combinatorial reasons), and we can use this and the functional equation to certify guessed systems of partial linear differential equations for $\tilde{f}_{\lambda}(x, 0, t)$ and $\tilde{f}_{\lambda}(0, y, t)$ which then together with the function equation (1) (now with $\tilde{f}_{\lambda}$ in place of $f$) imply that $f_{\lambda}(x, y, t)$ is D-finite. The equations are somewhat too large to be included here: $\tilde{f}_{\lambda}(x, 0, t)$ satisfies a differential equation of order 11 with respect to $t$ with polynomial coefficients of respective degrees 82, 90, 110 in $x$, $\lambda$ and $t$, while $\tilde{f}_{\lambda}(0, y, t)$ satisfies a differential equation of order 11 with respect to $t$ with polynomial coefficients of respective degrees 70, 58, 90 in $y$, $\lambda$ and $t$.

# 6 Models with Group D8

For the possible values of $a_{u,v}$ such that $(\Phi\Psi)^4 = \text{id}$, we obtain three essentially different prime ideals after discarding uninteresting or redundant components. One of them is the ideal from Section 4, which appears again because $(\Phi\Psi)^2 = \text{id}$ implies $(\Phi\Psi)^4 = \text{id}$. The other two define the following families:

Family 4a

Defining equations:

$$a_{1,-1}a_{-1,1} = a_{1,0}a_{-1,0},$$

$$a_{1,1} = a_{0,1} = a_{0,-1} = a_{-1,-1} = 0$$

Example:

$$\xleftarrow{3} \xrightarrow{6} \xrightarrow{2} \xleftarrow{4}$$

Family 4b

Defining equations:

$$a_{1,1}a_{-1,-1} = a_{1,0}a_{-1,0},$$

$$a_{1,-1} = a_{0,1} = a_{0,-1} = a_{-1,1} = 0$$

Example:

$$\xleftarrow{6} \xrightarrow{4} \xleftarrow{2}$$

In family 4a, we must have $a_{1,-1} \neq 0$ and $a_{-1,1} \neq 0$ for a model to be interesting. But then $a_{1,-1}a_{-1,1} \neq 0$ implies also $a_{1,0} \neq 0$ and $a_{-1,0} \neq 0$ through the first defining equation. Similarly, we can assume for the models in family 4b that $a_{1,0}, a_{-1,0}, a_{1,1}a_{-1,-1}$ all are nonzero.

For family 4a, the orbit sum argument applies and yields

$$f(x, y, t) = \frac{1}{xy} [x>y] \frac{(a_{1,-1}x/y - a_{-1,1}y/x)(a_{1,-1}/y - a_{1,0})(a_{1,0}x - a_{-1,0}/x)(a_{1,0}x - a_{-1,1}y/x)}{a_{-1,1}a_{1,0}^3 K(x, y, t)}$$

For family 4b the orbit sum is zero, but it was pointed out by Bostan et al. (2014a) in their Section 6.2 that its D-finiteness can be deduced from the D-finiteness of the corresponding model without multiplicities. If $g(x, y, t)$ denotes the generating function for the Gessel model without multiplicities, we have

$$f(x, y, t) = g\left(\sqrt{\frac{a_{1,0}}{a_{-1,0}}} x, \frac{a_{1,1}}{a_{1,0}} y, \sqrt{a_{1,0}a_{-1,0}} t\right)$$

for the general generating function of models of family 4b. Since $g(x, y, t)$ is known to be algebraic (Bostan and Kauers, 2010; Bostan et al., 2013), it follows that all the models of family 4b are algebraic.

**Theorem 3** The interesting quarter plane models whose group is D8 are precisely those that belong to one of the families described in the table above. All these models are D-finite.
# 7 Models with Larger Groups

For $n \ge 5$ we failed to compute the prime decomposition of the ideal of relations among the $a_{u,v}$ that ensures $(\Phi\Psi)^n = \text{id}$, as the required calculations become too expensive. However, in our search over all the 30307 quarter plane models with multiplicites in $\{0, 1, 2, 3\}$ we did encounter, much to our surprise, the following three models that do not belong to any of the families discussed so far. Their group is D10.

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

The orbit sum is zero for all three models. By guessing, we found that they seem to be algebraic. According to Raschel (2015), they indeed are.

The models on the left and in the middle can be obtained from one another by reversing arrows, so these two models have the same number of walks returning to the origin. We previously conjectured that these two models could be proven to be algebraic using half-orbit sum techniques. Bousquet-Mélou (2015) confirms this.

For the model on the right, $f(x, 0, t)$ seems to satisfy an algebraic equation $P(x, t, f(x, 0, t)) = 0$ for some irreducible polynomial $P \in \mathbb{Z}[x, t, T]$ of respective degrees 40, 45, 24 in $x, t, T$, and $f(0, y, t)$ seems to satisfy an algebraic equation $Q(y, t, f(0, y, t)) = 0$ for some irreducible polynomial $Q \in \mathbb{Z}[y, t, T]$ of respective degrees 64, 45, 24 in $y, t, T$. We expect that these algebraic equations can be proven by computer algebra in a similar way as the models of family 2b in Section 5.3 above, but this would require immense calculations which we have not carried out.

Using substitutions like in earlier sections, the three models can be used to generate three families of models, which we call Family 5a, 5b, and 5c. The corresponding ideals of defining relations for the $a_{u,v}$ have dimension three. We do not know whether these families completely characterize all the interesting models whose group is D10, nor do we know anything about models for even larger groups. Does there exist for every $n \ge 2$ a quarter plane model with multiplicities whose group is $D2n$?

# References

A. Aparicio Monforte and M. Kauers. Formal Laurent series in several variables. *Expositiones Mathematicae*, 31(4):350–367, 2013.

T. Becker, V. Weispfenning, and H. Kredel. *Gröbner Bases*. Springer, 1993.

A. Bostan and M. Kauers. The complete generating function for Gessel walks is algebraic. *Proceedings of the AMS*, 138(9):3063–3078, 2010. with an appendix by Mark van Hoeij.

A. Bostan, I. Kurkova, and K. Raschel. A human proof of Gessel’s lattice path conjecture. Technical Report 1309.1023, ArXiv, 2013.

A. Bostan, M. Bousquet-Mélou, M. Kauers, and S. Melczer. On 3-dimensional lattice walks confined to the positive octant. *Annals of Combinatorics*, 2014a. to appear.

A. Bostan, K. Raschel, and B. Salvy. Non-D-finite excursions in the quarter plane. *Journal of Combinatorial Theory Series A*, 121, 2014b.
M. Bousquet-Mélou. Walks in the quarter plane: Kreweras' algebraic model. *The Annals of Applied Probability*, 15(2):1451–1491, 2005.

M. Bousquet-Mélou. An elementary solution of Gessel's walks in the quadrant. Technical Report 1503.08573, ArXiv, 2015.

M. Bousquet-Mélou and M. Mishna. Walks with small steps in the quarter plane. *Contemporary Mathematics*, 520:1–40, 2010.

G. Fayolle and R. Iasnogorodski. Random walks in the quarter-plane: Advances in explicit criterions for the finiteness of the associated group in the genus 1 case. Technical Report 1408.3339, ArXiv, 2014.

G. Fayolle and K. Raschel. Random walks in the quarter-plane with zero drift: an explicit criterion for the finiteness of the associated group. *Markov Process. Related Fields*, 17(4):619–636, 2011.

G. Fayolle, R. Iasnogorodski, and V. Malyshev. *Random walks in the quarter-plane*, volume 40 of *Applications of Mathematics (New York)*. Springer-Verlag, Berlin, 1999. Algebraic methods, boundary value problems and applications.

P. Flajolet and R. Sedgewick. *Analytic Combinatorics*. Cambridge University Press, 2009.

G.-M. Greuel and G. Pfister. *A Singular Introduction to Commutative Algebra*. Springer, 2002.

M. Kauers. Guessing handbook. Technical Report 09-07, RISC-Linz, 2009.

M. Kauers and D. Zeilberger. The quasi-holonomic ansatz and restricted lattice walks. *Journal of Difference Equations and Applications*, 14(10):1119–1126, 2008.

M. Kauers, C. Koutschan, and D. Zeilberger. Proof of Ira Gessel's lattice path conjecture. *Proceedings of the National Academy of Sciences*, 106(28):11502–11505, July 2009.

C. Koutschan. HolonomicFunctions (User's Guide). Technical Report 10-01, RISC Report Series, University of Linz, Austria, January 2010. URL http://www.risc.uni-linz.ac.at/research/combinat/software/HolonomicFunctions/.

G. Kreweras. Sur une classe de problèmes liés au treillis des partitions d'entiers. *Cahiers du B.U.R.O.*, 6:5–105, 1965.

S. Melczer and M. Mishna. Singularity analysis via the iterated kernel method. *Combinatorics, Probability and Computing*, 2013. to appear. (Also in Proceedings of FPSAC'13).

M. Mishna and A. Rechnitzer. Two non-holonomic lattice walks in the quarter plane. *Theoretical Computer Science*, 410(38–40):3616–3630, 2009.

K. Raschel. Personal communication, 2015.