Walks confined in a quadrant are not always D-finite

Mireille Bousquet-Mélou^{∗}

CNRS, LaBRI, Université Bordeaux 1 351 cours de la Libération 33405 Talence Cedex, France

   mireille.bousquet@labri.fr

Marko Petkovšek^{†}

Department of Mathematics University of Ljubljana Jadranska 19, SI-1000 Ljubljana, Slovenia

                                            Marko.Petkovsek@fmf.uni-lj.si

Abstract

We consider planar lattice walks that start from a prescribed position, take their steps in a given finite subset of ℤ^{2}, and always stay in the quadrant x ≥ 0, y ≥ 0. We first give a criterion which guarantees that the length generating function of these walks is D-finite, that is, satisfies a linear differential equation with polynomial coefficients. This criterion applies, among others, to the ordinary square lattice walks. Then, we prove that walks that start from (1, 1), take their steps in {(2, −1), (−1, 2)} and stay in the first quadrant have a non-D-finite generating function. Our proof relies on a functional equation satisfied by this generating function, and on elementary complex analysis.

1 Introduction

The enumeration of lattice walks is one of the most venerable topics in enumerative combinatorics, which has numerous applications in probabilities [12, 22, 34]. These walks take their steps in a finite subset 𝔖 of ℤ^{d}, and might be constrained in various ways. One can only cite a small percentage of the relevant litterature, which dates back at least to the next-to-last century [1, 11, 14, 19, 27, 28]. Many recent publications show that the topic is still active [4, 6, 8, 16, 17, 29, 30].

After the solution of many explicit problems, certain patterns have emerged, and a more recent trend consists in developing methods that are valid for generic sets of steps. Special attention is being paid to the nature of the generating function of the walks under consideration. For instance, the generating function for unconstrained walks on the line ℤ is rational, while the generating function for walks constrained to stay in the half-line ℕ is always algebraic [3]. This result has often been described in terms of partially directed 2-dimensional walks confined in a quadrant (or generalized Dyck walks [10, 15, 20, 21]), but is, essentially, of a 1-dimensional nature.

∗Partially supported by the INRIA, via the cooperative research action Alcophys.

†Partially supported by MZT RS under grant P0-0511-0101.

Similar questions can be addressed for real 2-dimensional walks. Again, the generating function for unconstrained walks starting from a given point is clearly rational. Moreover, the argument used for 1-dimensional walks confined in ℕ can be recycled to prove that the generating function for the walks that stay in the half-plane x ≥ 0 is always algebraic. What about doubly-restricted walks, that is, walks that are confined in the quadrant x ≥ 0, y ≥ 0? It would be satisfactory if the hierarchy unconstrained walks / mono-constrained walks / bi-constrained walks could match the classical hierarchy of generating functions: rational series, algebraic series, D-finite series^{1} (also called holonomic series). A rapid inspection of the most standard cases only corroborates this hope. For instance, the generating function for walks on the square lattice (with North, East, South and West steps) that start from the origin and stay in the first quadrant is

∑_{m,n≥0} \binom{m + n}{m}\binom{m}{⌊m/2⌋}\binom{n}{⌊n/2⌋}t^{m+n} = ∑_{n≥0} \binom{n}{⌊n/2⌋}\binom{n + 1}{⌈n/2⌉}t^{n},

which is a D-finite series. The first expression comes from the fact that these walks are shuffles of two prefixes of Dyck walks, and the Chu-Vandermonde identity transforms it into the second simpler expression.

Figure 1: A walk on the diagonal square lattice confined in the first quadrant.

The case of the diagonal square lattice, where the steps are North-East, South-East, North-West and South-West (Figure 1) is even simpler: by projecting the walks on the xand y-axes, we obtain two decoupled prefixes of Dyck paths, so that the generating function for walks in the first quadrant is now

∑_{n≥0} \binom{n}{⌊n/2⌋}^{2}t^{n},

another D-finite series. In both cases, the number of n-step walks can be shown to grow asymptotically like 4^{n}/n, which prevents the corresponding generating function from being algebraic (see [13] for the possible asymptotic behaviours of coefficients of algebraic series).

1A series F (t) is D-finite if it satisfies a linear differential equation with polynomial coefficients in t.

In Section 2 of this paper, we shall generalize this result by proving that, if the set of steps 𝔖 is symmetric with respect to the x-axis and satisfies a small height variation condition, then the generating function for walks with steps in 𝔖, starting from any given point (i_{0}, j_{0}), is D-finite. This result covers the above two cases.

However, and most importantly, we shall also prove in Section 3 that this holonomy result does not hold for any set of steps: walks that start from (1, 1), take their steps in 𝔖 = {(2, −1), (−1, 2)} and always stay in the first quadrant have a non-D-finite generating function. The central point of our proof is the study of a series G(x), defined by an equation of the form

G(x) + G(ξ(x)) = A(x),

where ξ(x) and A(x) are explicit algebraic series in x. We consider the solution G(x) to this equation as a function of a complex variable x, and prove that it has infinitely many singularities, which prevents it from being D-finite. Hence our proof is based on complex analysis. To our knowledge, there is no classification of the solutions to this type of equation. In some very specific cases (like ξ(x) = x^{p} or ξ(x) = cx) some hypertranscendence results^{2} have been obtained, either by some ad hoc methods [18, 26, 31], or via general results about “very” lacunary series [25].

These two sections raise the question of a classification of the sets 𝔖 according to the nature of the generating function for walks in a quadrant that take their steps in 𝔖. Let us mention that some sets of steps, like 𝔖 = {(1, 1), (0, −1), (−1, 0)} yield, for non-trivial reasons, algebraic generating functions [5, 14, 19, 29].

Finally, in Section 4, we say a few words about the closely related topic of multidimensional linear recurrences with constant coefficients, and prove a non-holonomy result that was announced (but not proven) in [7].

Let us conclude this introduction with a few more formal definitions on walks and power series.

Let 𝔖 be a finite subset of ℤ^{2}. A walk with steps in 𝔖 is a finite sequence w = (w_{0}, w_{1}, …, w_{n}) of vertices of ℤ^{2} such that w_{i} − w_{i−1} ∈ 𝔖 for 1 ≤ i ≤ n. The number of steps, n, is the length of w. The starting point of w is w_{0}, and its endpoint is w_{n}. The complete generating function for a set A of walks starting from a given point w_{0} is the series

A(x, y; t) = ∑_{n≥0} t^{n} ∑_{i,j∈ℤ} a_{i,j}(n)x^{i}y^{j},

where a_{i,j}(n) is the number of walks of A that have length n and end at (i, j). This series is a formal power series in t whose coefficients are polynomials in x, y, 1/x, 1/y. We shall often denote x̄ = 1/x and ȳ = 1/y. The length generating function for walks of A is simply

A(t) = ∑_{n≥0} a(n)t^{n}

where a(n) is the number of walks of A that have length n. Note that A(t) = A(1, 1; t).

2A series is hypertranscendental if it does not satisfy any polynomial differential equation of the type P (x, F (x), F′(x), …, F^{(k)}(x)) = 0, where P is a polynomial.

Given a ring 𝕃 and k indeterminates x_{1}, …, x_{k}, we denote by 𝕃[x_{1}, …, x_{k}] (resp. 𝕃[[x_{1}, …, x_{k}]]) the ring of polynomials (resp. formal power series) in x_{1}, …, x_{k} with coefficients in 𝕃. If 𝕃 is a field, we denote by 𝕃(x_{1}, …, x_{k}) the field of rational functions in x_{1}, …, x_{k} with coefficients in 𝕃.

Assume 𝕃 is a field. A series F in 𝕃[[x_{1}, …, x_{k}]] is rational if there exist polynomials P and Q in 𝕃[x_{1}, …, x_{k}], with Q ≠ 0, such that QF = P. It is algebraic (over the field 𝕃(x_{1}, …, x_{k})) if there exists a non-trivial polynomial P with coefficients in 𝕃 such that P (F, x_{1}, …, x_{k}) = 0. The sum and product of algebraic series is algebraic.

The series F is D-finite (or holonomic) if the partial derivatives of F span a finite dimensional vector space over the field 𝕃(x_{1}, …, x_{k}) (this vector space is a subspace of the fraction field of 𝕃[[x_{1}, …, x_{k}]]); see [35] for the one-variable case, and [23, 24] otherwise. In other words, for 1 ≤ i ≤ k, the series F satisfies a non-trivial partial differential equation of the form

∑_{ℓ=0}^{d_{i}} P_{ℓ,i} \frac{∂^{ℓ}F}{∂x_{i}^{ℓ}} = 0,

where P_{ℓ,i} is a polynomial in the x_{j}. Any algebraic series is holonomic. The sum and product of two holonomic series is still holonomic. The specializations of an holonomic series (obtained by giving values from 𝕃 to some of the variables) are holonomic, if well-defined. Moreover, if F is an algebraic series and G(t) is a holonomic series of one variable, then the substitution G(F) (if well-defined) is holonomic [24, Prop. 2.3].

2 A sufficient condition for holonomy

Let 𝔖 be a finite subset of ℤ^{2}. We say that 𝔖 is symmetric with respect to the x-axis if

(i, j) ∈ 𝔖 ⇒ (i, −j) ∈ 𝔖.

We say that 𝔖 has small height variation if

(i, j) ∈ 𝔖 ⇒ |j| ≤ 1.

The usual square lattice steps satisfy these two conditions. So do the steps of the diagonal square lattice (Figure 1).

Theorem 1 Let 𝔖 be a finite subset of ℤ^{2} that is symmetric with respect to the x-axis and has small height variations. Let (i_{0}, j_{0}) ∈ ℕ^{2}. Then the length generating function for walks that start from (i_{0}, j_{0}), take their steps in 𝔖 and stay in the first quadrant is D-finite.

We shall need the following preliminary result, which does not require any property on 𝔖.

Proposition 2 Let 𝔖 be a finite subset of ℤ^{2}. Let (i_{0}, j_{0}) ∈ ℕ × ℤ. Then the complete generating function for walks that start from (i_{0}, j_{0}), take their steps in 𝔖 and stay in the right half-plane x ≥ 0 is algebraic.

Proof. The problem being invariant by any vertical translation, we can assume j_{0} = 0. Let us also assume that i_{0} = 0. The argument is easily adapted when i_{0} > 0.

Projecting the walks on the x-axis reduces the problem to the enumeration of 1dimensional walks on the half-line ℕ, starting from 0, in which each step of size i is weighted by a Laurent polynomial in y:

∑_{j:(i,j)∈𝔖}y^{j}.

The weight of a walk is taken to be the product of the weights of its steps. We can now invoke some 1-dimensional results, like those of [3], and conclude that the complete generating function for walks in the right-half plane is algebraic over ℚ(x, y, t).

Proof of Theorem 1. Let Q denote the set of walks that start from (i_{0}, j_{0}), take their steps in 𝔖 and stay in the first quadrant. We shall prove that walks of Q are, roughly speaking, “equivalent to” walks in the right half-plane ending on the x-axis.

We claim that it suffices to prove that the subset of Q consisting of the walks that hit the x-axis at some point has a D-finite generating function. Indeed, the remaining walks are, by a vertical translation, in one-to-one correspondence with walks that start from (i_{0}, j_{0} − k), for some k ∈ [1, j_{0}], stay in the first quadrant and hit the x-axis.

Let us first focus on the set Q_{e}^{(0)} of walks in the first quadrant that start from (i_{0}, j_{0}), hit the x-axis and end at an even ordinate. These walks are in bijection with the set H_{0} of walks that start from (i_{0}, j_{0}), stay in the right half-plane and end on the x-axis. This bijection, illustrated by Figure 2, is a mere adaptation of a classical 1-dimensional correspondence, which establishes that Dyck prefixes ending at an even ordinate are equivalent to bilateral Dyck walks (see the Catalan factorisation in [9].) Starting from a walk w of Q_{e}^{(0)}, ending at level 2k, we denote by s_{1}, …, s_{k} the steps that follow the last visit of w to a point of level (ordinate) 0, …, k − 1. Replacing these k steps by their symmetric steps with respect to the x-axis yields a walk w̄ that belongs to H_{0}. The ordinate of the lowest point(s) visited by w̄ is −k. Conversely, the steps s̄_{1}, …, s̄_{k} of w̄ that we have to flip back to recover w are the first steps of w that lead to level −j, for 1 ≤ j ≤ k.

Let H(x, y; t) be the complete generating function for walks in the right half-plane. The length generating function for walks of H_{0} is obtained by extracting the coefficient of y^{0} in the generating function H(1, y; t). Extracting the constant term of a D-finite series is known to give another D-finite series [23]: thus the generating function for walks of H_{0}, and hence of Q_{e}^{(0)}, is D-finite.

A similar argument holds for the set Q_{o}^{(0)} of walks in the first quadrant that start from (i_{0}, j_{0}), hit the x-axis and end at an odd ordinate: they are in one-to-one correspondence with the set H_{−1} of walks that start from (i_{0}, j_{0}), stay in the right half-plane and end at level −1. The generating function for walks of H_{−1} is the coefficient of y^{0} in yH(1, y; t), and hence is D-finite. Given that the sum of D-finite series is D-finite, this concludes the proof of Theorem 1.

i_{0}  s̄_{2} j_{0}  j_{0} 42 1  s_{2} s_{1}  s̄_{1} i_{0}

Figure 2: The bijection between some walks in the quadrant and walks in the right half-plane ending on the x-axis.

3 The knight walk is not holonomic

3.1 The main result

We study walks that start at (1, 1), take their steps in {(−1, 2), (2, −1)} and stay in the first quadrant. We call them knight walks, since their steps correspond to two of the knight moves on a chessboard (Figure 3). We note that a walk ending at (i, j) has always i + j − 2 steps: hence the information contained in the complete generating function is actually already contained in the following bivariate series:

Q(x, y) = ∑_{i≥0,j≥0} Q_{i,j} x^{i}y^{j},

where Q_{i,j} denotes the number of knight walks ending at (i, j).

Figure 3: A knight walk.

The coefficients Q_{i,j} satisfy the following recurrence relation:

Q_{i,j} = \{ \begin{matrix}0 & if i < 0 or j < 0, \\ 1 & if i = j = 1, \\ Q_{i+1,j−2} + Q_{i−2,j+1} & otherwise. \end{matrix}  (1)

This recurrence allows us to compute the numbers Q_{i,j} inductively, for instance diagonal by diagonal. The first few values are given in Table 1 below, in which the zero entries are left out. The non-zero entries lie on the lines i = j mod 3.

j
↑
12 24
11  108
10  24  312
9 6  84  720
8  24  204  1440
7  6  60  408
6 2  18  120  720
5  6  36  204
4  2  12  60  312
3 1  4  18  84
2  2  6  24  108
1  1  2  6  24
0  1  2  6  24
0 1 2 3 4 5 6 7  8  9 10 11 12 → i

Table 1: The number Q_{i,j} of knight walks ending at (i, j).

Applying the transformation (i, j) → ((2i + j)/3, (i + 2j)/3) shows that Q_{i,j} is also the number of walks made of North and East steps, that start from (1, 1), end at ((2i+j)/3, (i+ 2j)/3) and always stay above the line 2y = x and below the line 2x = y (see Figure 4). Ignoring these two conditions gives the following simple bound:

Q_{i,j} ≤ \binom{i + j − 2}{(2i + j − 3)/3}.

In particular,

Q_{3i,0} ≤ \binom{3i − 2}{i − 1}.  (2)

This bound could be sharpened by counting walks that stay above the line 2y = x (see e.g. [11] or [7, Example 4]), but the above bound will be enough for our purpose.

By summing the recurrence relation we obtain:

Q(x, y) = ∑_{i,j≥0} Q_{i,j}x^{i}y^{j} = xy + ∑_{i,j≥0}(Q_{i+1,j−2} + Q_{i−2,j+1})x^{i}y^{j}
= xy + y^{2}/x(Q(x, y) − Q(0, y)) + x^{2}/y(Q(x, y) − Q(x, 0)),

Figure 4: Another description of the knight walk.

that is

(xy − x^{3} − y^{3})Q(x, y) = x^{2}y^{2} − G(x) − G(y)  (3)

where

G(x) = x^{3} ∑_{i≥0} Q_{i,0}x^{i} = x^{3}Q(x, 0)  (4)

counts knight walks ending on the x-axis. (We have used the symmetry of the problem in x and y.) Note that the length generating function for all knight walks is t^{−2}Q(t, t). The above equation, combined with the elementary properties of D-finite series, imply that the following three statements are equivalent:

— the bivariate generating function Q(x, y) for knight walks is D-finite,

— the generating function Q(x, 0) for knight walks ending on the x-axis is D-finite,

— the length generating function t^{−2}Q(t, t) for knight walks is D-finite. Our main result asserts that none of these statements hold.

Theorem 3 The length generating function for walks that start from (1, 1), take their steps in {(−1, 2), (2, −1)} and always stay in the first quadrant (knight walks) is not D-finite. Nor is the generating function for knight walks that end on the x-axis.

Looking at Table 1, one might still have some hope that the numbers Q_{i,j} are not so bad. In particular, they seem to have small prime factors. This pattern actually does not go on, and, in case there would still be a doubt, the following proposition reinforces the non-holonomic character of these numbers.

Proposition 4 The length generating function for knight walks ending on the main diagonal x = y is not D-finite.

3.2 The kernel method

The so-called kernel method solves completely the functional equation (3). This method has been around since, at least, the 70’s, and is currently the subject of a certain rebirth (see the references in [2, 3, 7]).

Applied to our equation, this method consists in coupling the variables x and y so as to cancel the kernel xy − x^{3} − y^{3}; this yields the missing information about the series G(x). More precisely, let ξ(x) be the unique formal power series in x satisfying

xξ − x^{3} − ξ^{3} = 0.

The Lagrange inversion formula, applied to ξ(x)/x, provides an explicit expression for ξ(x):

ξ(x) = x^{2} ∑_{m≥0} \frac{x^{3m}}{2m + 1}\binom{3m}{m} = O(x^{2}).  (5)

Replacing y by ξ(x) in (3) gives a functional equation that defines the power series G(x):

G(x) + G(ξ(x)) = x^{2}ξ(x)^{2}.  (6)

Indeed we obtain, after iterating this equation infinitely many times:

G(x) = ∑_{i≥0}(−1)^{i} (ξ^{(i)}(x)ξ^{(i+1)}(x))^{2}

where ξ^{(i)} = ξ ∘ ⋯ ∘ ξ is the ith iterate of ξ. Note that ξ^{(i)}(x) = O(x^{2^{i}}), so that the sum is convergent in the ring ℂ[[x]]. Replacing G(x) by the above explicit value in (3) would give an expression for Q(x, y).

However, we shall not exploit these expressions, but rather the functional equation (6), to prove that G(x), hence Q(x, y), is not D-finite. Our proof will be of an analytic nature. The idea is to consider G(x) as a function of a complex variable x and study its singularities. Using functional equations like (6), we shall build new singularities of G from old ones – and end up with infinitely many singularities, thus proving that G cannot be holonomic.

However, even though (6) defines G(x) uniquely, this equation itself is not sufficient for our purpose: we shall introduce the other two roots ξ_{1}(x) and ξ_{2}(x) of the kernel, and the corresponding analogues of (6), to obtain enough singularities.

3.3 The roots of x^{3} + y^{3} = xy

As a polynomial in y, the kernel xy −x^{3} −y^{3} has three roots. Only one of them, given by (5), is a power series in x. We shall denote it, from now on, by ξ_{0}:

ξ_{0}(x) = x^{2} + x^{5} + 3x^{8} + 12x^{11} + 55x^{14} + 273x^{17} + ⋯

The other two roots are power series in \sqrt{x}, and their expansion can be computed inductively:

ξ_{1}(x) = +\sqrt{x} − \frac{x^{2}}{2} − \frac{3}{8}x^{3}\sqrt{x} − \frac{x^{5}}{2} − \frac{105}{128}x^{6}\sqrt{x} − ⋯

ξ_{2}(x) = −\sqrt{x} − \frac{x^{2}}{2} + \frac{3}{8}x^{3}\sqrt{x} − \frac{x^{5}}{2} + \frac{105}{128}x^{6}\sqrt{x} − ⋯

Of course, ξ_{2}(x) is derived from ξ_{1}(x) by replacing \sqrt{x} by −\sqrt{x}. Guided by the above expressions, let us write

ξ_{1}(x) = +\sqrt{x} ψ(x) − ϕ(x)  (7)
ξ_{2}(x) = −\sqrt{x} ψ(x) − ϕ(x)

where ψ and ϕ are formal power series in x. As the three roots sum to zero, one has

ϕ(x) = ξ_{0}(x)/2.  (8)

In order to compute the coefficients of ψ, we shall use again the Lagrange inversion formula (LIF). Let χ(x) be defined by

ξ_{1}(x) = \sqrt{x}(1 − χ(x)).  (9)

Then

χ = \frac{x\sqrt{x}}{(1 − χ)(2 − χ)},

so that the LIF gives, for n ≥ 1,

a_{n} := [x^{3n/2}]χ(x) = \frac{1}{n2^{n}} ∑_{k=0}^{n−1} \frac{1}{2^{k}} \binom{n + k − 1}{k}\binom{2n − k − 2}{n − 1}.  (10)

Using the package ekhad [33], we prove that the sequence a_{n} satisfies, for n ≥ 1,

a_{n+2} = \frac{3(3n + 1)(3n − 1)}{4(n + 2)(n + 1)} a_{n}.

When n is odd, say n = 2m + 1, we derive from (9) and (7) that the coefficient a_{n} is [x^{3m+2}]ϕ(x), and the above recursion yields a_{n} = \binom{3m}{m}/(4m + 2). We thus recover (8). Similarly, when n = 2m, the coefficient a_{n} is −[x^{3m}]ψ(x) and the above recursion now gives

ψ(x) = − ∑_{m≥0} \frac{m!(6m)!}{(6m − 1)(2m)!^{2}(3m)!} \frac{x^{3m}}{16^{m}} .

Let us summarize the results we have obtained.

Lemma 5 Let ξ and ψ be the following power series in x:

ξ = x^{2} ∑_{m≥0} \frac{x^{3m}}{2m + 1}\binom{3m}{m},

ψ = − ∑_{m≥0} \frac{m!(6m)!}{(6m − 1)(2m)!^{2}(3m)!} \frac{x^{3m}}{16^{m}} .

Then the three roots of x^{3} + y^{3} = xy are

ξ_{0}(x) = ξ
ξ_{1}(x) = \sqrt{x} ψ − ξ/2
ξ_{2}(x) = −\sqrt{x} ψ − ξ/2.

Both ξ(x) and ψ(x) have radius of convergence x_{c} = 4^{1/3}/3.

The last statement is obtained using the Stirling formula. Note that one also has the following closed form expressions:

ξ(x) = 2\sqrt{\frac{x}{3}} sin (\frac{arcsin ((3x)^{3/2}/2)}{3}) ,

ψ(x) = cos (\frac{arcsin ((3x)^{3/2}/2)}{3}) .

We shall now consider the ξ_{i}(x) as functions of a complex variable x. We choose a determination of the square root that coincides with the usual determination on ℝ^{+}:

\sqrt{re^{iθ}} = \sqrt{r}e^{iθ/2} for − π < θ < π.

Figure 5 shows the (real) values of the functions ξ_{i} for real values of x. When x is positive, the plots show, from bottom to top, ξ_{2}(x), ξ_{0}(x) and ξ_{1}(x). When x is negative, the only real branch is ξ_{0}.

The implicit function theorem implies that the singularities of the functions ξ_{i} are to be found among the complex numbers x such that the pair (x, y) ≡ (x, ξ_{i}(x)) satisfies 3y^{2} = x (and, of course, x^{3} + y^{3} = xy); that is,

(x, y) ∈ {(0, 0), (x_{c}, y_{c}), (jx_{c}, j^{2}y_{c}), (j^{2}x_{c}, jy_{c})}  (11)

where x_{c} = 2^{2/3}/3, y_{c} = 2^{1/3}/3 and j = exp(2iπ/3). A more detailed investigation gives the following result.

Lemma 6 The singularities of the functions ξ_{i} are given by:

Sing(ξ_{0}) = {x_{c}, jx_{c}, j^{2}x_{c}}, Sing(ξ_{1}) = {0, x_{c}} and Sing(ξ_{2}) = {0, jx_{c}, j^{2}x_{c}}.

In particular, ξ_{2} is not singular at x_{c}, as suggested by Figure 5. All the above singularities are of the square root type.

Figure 5: The real values of ξ_{i}(x) for a real x.

Proof. For each of the values of x given by (11), we first have to compute the values ξ_{i}(x), 0 ≤ i ≤ 2, in order to determine which pairs (x, ξ_{i}(x)) are actually critical, and then, to check the existence and nature of the singularity.

At x = 0, all the ξ_{i}(x) are zero. The explicit expansion of Lemma 5, combined with the fact that ψ and ξ have a positive radius of convergence, shows that only ξ_{1} and ξ_{2} are singular — their singularity being obviously of a square root type.

When x = x_{c}, factoring the polynomial x^{3} + y^{3} − xy shows that the multiset {ξ_{0}(x_{c}), ξ_{1}(x_{c}), ξ_{2}(x_{c})} equals {y_{c}, y_{c}, −2y_{c}}. The functions ξ_{i}(x) are real and continuous on [0, x_{c}], and the expansions of Lemma 5 show that ξ_{0}(x) and ξ_{1}(x) are positive as x → 0^{+}, while ξ_{2}(x) is negative. As the ξ_{i} can only vanish at 0, this sign pattern must go on until x_{c}, so that

ξ_{0}(x_{c}) = ξ_{1}(x_{c}) = y_{c} and ξ_{2}(x_{c}) = −2y_{c}.  (12)

In view of (11), x_{c} cannot be a singularity of ξ_{2}. Now a local expansion of x^{3} + y^{3} − xy around (x_{c}, y_{c}) shows that as x approaches x_{c}^{−},

ξ_{0,1}(x) = y_{c} ∓ \frac{1}{\sqrt{3}}\sqrt{x_{c} − x}(1 + o(1)),  (13)

which confirms that the singularity of ξ_{0} and ξ_{1} at x_{c} is of the square root type. The values (12) imply in particular that

\sqrt{x_{c}} ψ(x_{c}) = 3y_{c}/2 = 2^{−2/3}.

Using this result, the fact that ψ and ξ are essentially functions of x^{3}, and the values

\sqrt{j} = −j^{2} and \sqrt{j^{2}} = −j,

we now compute

\begin{aligned}ξ_{0}(jx_{c}) & = & j^{2}y_{c} & ξ_{0}(j^{2}x_{c}) & = & jy_{c} \\ ξ_{1}(jx_{c}) & = & −2j^{2}y_{c} & ξ_{1}(j^{2}x_{c}) & = & −2jy_{c} \\ ξ_{2}(jx_{c}) & = & j^{2}y_{c} & ξ_{2}(j^{2}x_{c}) & = & jy_{c} \end{aligned}

so that ξ_{1} cannot be singular at jx_{c} or j^{2}x_{c}. Finally, local expansions of x^{3} + y^{3} − xy confirm as above the existence of square roots singularities of ξ_{0} and ξ_{2} at jx_{c} and j^{2}x_{c}.

Each of the functions ξ_{i} has a unique analytic continuation on any simply connected domain avoiding Sing(ξ_{i}), for instance the domain obtained by removing from ℂ the four half-lines of Figure 6.

x_{c}

Figure 6: A domain on which all the functions ξ_{i} are holomorphic.

Observe that the series ξ_{1} and ξ_{2} can also be substituted for y in the functional equation (3); thus for i ∈ {0, 1, 2}, the following equation holds

G(x) + G(ξ_{i}(x)) = x^{2}ξ_{i}(x)^{2},  (14)

at least as an identity between power series.

We end this subsection with a lemma that will be useful to build large singularities from small ones.

Lemma 7 Let x ∈ ℂ, x ≠ 0. Then one of the roots of x^{3} + y^{3} − xy = 0 has modulus larger than |x|.

Proof. Let y_{0}, y_{1}, y_{2} denote the three roots, and assume none of then has modulus larger than |x|. The relation y_{0}y_{1}y_{2} = −x^{3} forces |y_{0}| = |y_{1}| = |y_{2}| = |x|. Then, the relation y_{0} + y_{1} + y_{2} = 0 implies {y_{1}, y_{2}} = {jy_{0}, j^{2}y_{0}}. Finally, the relation y_{0}y_{1} + y_{0}y_{2} + y_{1}y_{2} = −x yields x = 0.

3.4 The series G(x) is not D-finite

We now turn our attention to the series G(x) defined by (4).

Proposition 8 The series G(x) has radius of convergence x_{c} = 4^{1/3}/3. It is singular at x_{c}, with

G(x) = A − B\sqrt{1 − x/x_{c}}(1 + o(1)),

where A and B are non-zero real numbers.

Proof. We start from the functional equation defining G:

G(x) + G(ξ_{0}(x)) = x^{2}ξ_{0}(x)^{2}.

Recall that G(x) and ξ_{0}(x) have nonnegative coefficients (G(x) counts walks, and ξ_{0}(x) ≡ ξ(x) is given explicitly by (5)). Hence G(ξ_{0}(x)) and x^{2}ξ_{0}(x)^{2} also have nonnegative coefficients. The radius of convergence of ξ_{0}(x) being x_{c}, the series G(x) and G(ξ_{0}(x)) have radius at least x_{c}. The fact that G(x) has radius at least x_{c} can also be directly derived from the upper bound (2).

For |x| < x_{c}, one has |ξ_{0}(x)| < ξ_{0}(x_{c}) = y_{c}, and y_{c} is smaller than x_{c}. This means that the above functional equation now holds as an identity between analytic functions of x in the disk |x| < x_{c}. As x approaches x_{c} inside this disk, a local expansion gives, thanks to (13),

G(x) = x_{c}^{2}y_{c}^{2} − G(y_{c}) − \frac{1}{\sqrt{3}}\sqrt{x_{c} − x} (2x_{c}^{2}y_{c} − G′(y_{c})) + O(x_{c} − x).

The upper bound (2) yields

G′(y_{c}) ≤ ∑_{i≥1} \binom{3i − 2}{i − 1}y_{c}^{3(i+1)}.

This sum can be evaluated numerically, and is found to be smaller than 0.16. Comparing with 2x_{c}^{2}y_{c} ≈ 0.23 gives the announced result.

Observe that (14) now holds as an identity between functions of x, as long as |x| < x_{c} and |ξ_{i}(x)| < x_{c} (and x ∉ ℝ^{−} if i = 1 or 2).

Proposition 9 The series G(x) that counts knight walks ending on the x-axis is not D-finite.

Proof. Assume G is D-finite. Then, it has a finite number of singularities, and has a unique analytic continuation on any simply connected domain avoiding these singularities. For i ∈ {0, 1, 2}, the series G(ξ_{i}) are also D-finite (since ξ_{i} is algebraic). Moreover, by analytic continuation of (14),

G(x) + G(ξ_{i}(x)) = x^{2}ξ_{i}(x)^{2}  (15)

for all x in any domain where all our functions are analytically defined. Let us consider the identity (15) for i = 2. As x approaches x_{c}, the function G(x) becomes singular, while ξ_{2}(x) does not: this shows that ξ_{2}(x_{c}) = −2y_{c} is a singularity of G.

Now let x_{s} be a singularity of G of maximal modulus. According to Lemma 7, there exists i such that |ξ_{i}(x_{s})| > |x_{s}|. By assumption, G(x) is singular at x_{s}. But |x_{s}| ≥ 2y_{c} > x_{c}, so that x_{s} is not a singularity of ξ_{i}. Hence (15) implies that G is singular at ξ_{i}(x_{s}). But |ξ_{i}(x_{s})| > |x_{s}|, which contradicts the maximality of |x_{s}|.

Remarks

1. The only property of D-finite series we have really used is the fact that these series have finitely many singularities. Hence, what we have actually proved is that G cannot have finitely many singularities.

2. The principle of the proof can be applied to other functional equations of the same type. We apply it in the next section to a (minor) variation of the knight walks.

There remains to prove Proposition 4: the generating function for knight walks ending on the diagonal is not D-finite. Proof of Proposition 4. The length generating function for walks ending on the diagonal is the coefficient of x^{0} in the series t^{−2}Q(tx, tx̄), where x̄ = 1/x. This series is a power series in t whose coefficients are Laurent polynomials in x. Let us denote u = x^{3} and ū = 1/u. Then, by Eq. (3),

t^{2}Q(tx, tx̄) = \frac{t^{4} − S(t^{3}u) − S(t^{3}ū)}{1 − t(u + ū)},  (16)

where the series S(z) is defined by S(z^{3}) = G(z). Let us convert 1/(1 − t(u + ū)) in partial fractions of u. We obtain

\frac{1}{1 − t(u + ū)} = \frac{1}{\sqrt{1 − 4t^{2}}} (\frac{1}{1 − uU(t)} + \frac{1}{1 − ūU(t)} − 1) ,

where

U(t) = \frac{1 − \sqrt{1 − 4t^{2}}}{2t} .

We can now extract the constant term in x from (16):

[x^{0}]t^{2}Q(tx, tx̄) = \frac{1}{\sqrt{1 − 4t^{2}}} (t^{4} − [u^{0}]\frac{S(t^{3}u)}{1 − ūU(t)} − [u^{0}]\frac{S(t^{3}ū)}{1 − uU(t)})
= \frac{1}{\sqrt{1 − 4t^{2}}} (t^{4} − 2S(t^{3}U(t))) .

Assume this series is D-finite: then the series D(t) defined by D(t) = S(t^{3}U(t)) is D-finite in t too. Let T (s) be the unique power series in s such that T (0) = 0, T′(0) = 1 and T^{6} −s^{4}T^{2} +s^{8} = 0. Then the fact that D-finite series are stable by any algebraic substitution tells us that D(T (s)) = S(T^{3}U(T)) is D-finite. But T^{3}U(T) = s^{4}, so that S(s^{4}) itself, and hence S(s) and G(s), are D-finite too, which we have proved to be wrong.

4 A link with multidimensional linear recurrences with constant coefficients

In [7], we considered d-dimensional sequences of complex numbers, denoted a_{n} = a_{n_{1},n_{2},...n_{d}}, defined by recurrence relations of the following form:

a_{n} = ∑_{h∈H} c_{h}a_{n+h} for n ≥ s,  (17)

where H = {h_{1}, h_{2}, …, h_{k}} ⊆ ℤ^{d} is the set of shifts, (c_{h})_{h∈H} are given nonzero constants, and s ∈ ℕ^{d} is the starting point satisfying s + H ⊆ ℕ^{d}. We think of the h_{i} as having mostly (but not necessarily only) negative coordinates, and of the point n as depending on the points n + h_{1}, n + h_{2}, …, n + h_{k} as far as the value of a_{n} is concerned. A given function φ specifies the initial conditions:

a_{n} = φ(n) for n ≥ 0, n ≱ s .  (18)

The convex hull of the set H is assumed not to intersect the first orthant (i.e., n ≥ 0). This condition, as shown in [7], guarantees that the numbers a_{n} can be computed recursively using (17).

The enumeration of walks in a quadrant fits exactly in this framework, with d = 3. Indeed, denoting Q_{i,j}(n) the number of walks that start from a given point (i_{0}, j_{0}), end at (i, j) and have length n, we have

Q_{i,j}(n) = \{ \begin{matrix}1 & if (i, j, n) = (i_{0}, j_{0}, 0) \\ 0 & if i < 0 or j < 0 or n < 0 \\ ∑_{(h,k)∈𝔖}Q_{i−h,j−k}(n − 1) & otherwise, \end{matrix}

where 𝔖 is the set of steps. A translation of the indices i and j transforms this recursion into one of the above type, with d = 3 and H = {(−h, −k, −1), (h, k) ∈ 𝔖}.

The paper [7] mostly dealt with the algebraic nature of the generating function of the solution of such recurrences, and we started a classification, based on the apex of the recurrence, defined as the componentwise maximum of the points in H ∪ {0}. We proved that when the initial conditions have rational generating functions and the apex is 0, the generating function of the solution is rational. Next, when the initial conditions have algebraic generating functions and the apex has at most one positive coordinate, the generating function of the solution is algebraic.

When the apex has two positive coordinates, and d = 3, our study of walks in a quadrant shows that the solution might be, or not, D-finite. For 2-dimensional sequences, the “simplest” example with apex (1, 1) was introduced in [32]: For i, j ≥ 0, let

a_{i,j} = \{ \begin{matrix}a_{i+1,j−2} + a_{i−2,j+1} & if i, j ≥ 2, \\ 1 & otherwise. \end{matrix}  (19)

This recurrence is obviously closely connected to the knight walk. Again, it has a unique solution whose terms can be computed inductively. The first few values are given in the following array.

j
↑
6 1 1 5 7 ⋯
5 1 1 3 5 10 14 ·
4 1 1 3 4 6 10 ·
3 1 1 2 2 4 5 7
2 1 1 2 2 3 3 5
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 1 2 3 4 5 6 → i

Defining the generating function

A(x, y) = ∑_{i,j≥2} a_{i,j}x^{i−2}y^{j−2},

we obtain, by summing the recurrence relation over i, j ≥ 2, the following functional equation:

(xy − x^{3} − y^{3})A(x, y) = R(x, y) − F (x) − F (y)  (20)

where

R(x, y) = xy (\frac{1 + y}{1 − x} + \frac{1 + x}{1 − y}) and F (x) = ∑_{i≥2} a_{i,2}x^{i+1} = x^{3}A(x, 0).

We have used the symmetry of the problem in i and j. It was first proved in [32] that F (x) and A(x, y) are irrational. Then, we claimed in [7, p. 74] that they are even not D-finite, but without giving a proof. The tools developed above for the knight walk apply perfectly to this problem.

Proposition 10 The series F (x) and A(x, y) are not D-finite.

Proof. The argument is very close to the knight one. The kernel method first gives

F (x) + F (ξ_{i}(x)) = R(x, ξ_{i}(x)),  (21)

for any of the three roots ξ_{i} of the kernel.

The only difference with the knight treatment comes from the fact that R(x, ξ_{i}(x)) might have — and indeed, has — more singularities than ξ_{i}. They can be determined exactly, but we shall only use the following obvious information

Sing(R(x, ξ_{i}(x))) ⊂ Sing(ξ_{i}) ∪ {1} ∪ {x : x^{3} − x + 1 = 0}.  (22)

In particular, all singularities of R(x, ξ_{i}(x)) have modulus at most 1.33 (an upper bound for the modulus of the largest root of x^{3} − x + 1).

We start from Eq. (21), in the case i = 0. As R(x, ξ_{0}(x)) has radius x_{c}, we find again that the radius of F (x) is at least x_{c}. Moreover, comparing the recurrence relations (1) and (19), and the corresponding tables, shows that for i, j ≥ 2, one has a_{i,j} ≥ Q_{i−2,j−2}. This implies that the radius of F (x) is bounded from above by the radius of G(x), which was proved to be exactly x_{c}. Hence F (x) has radius x_{c}.

Assume F (x) is D-finite. As in the proof of Proposition 9, we first construct large singularities of F (here, large means larger than 1.33). Let us start from x_{0} = x_{c} = 4^{1/3}/3 ≈ 0.53, which is a singularity of F. As it is not a singularity of R(x, ξ_{2}(x)), Eq. (21) implies that x_{1} := ξ_{2}(x_{c}) = −2y_{c} ≈ −0.84 is singular for F.

But x_{1} is singular for none of the R(x, ξ_{i}(x)). Moreover,

{ξ_{0}(x_{1}), ξ_{1}(x_{1}), ξ_{2}(x_{1})} = {x_{0}, −0.26... ± 1.02...i}.

Using the same trick as above, we see that x_{2} ≈ −0.26 − 1.02i is singular for F.

One more step: Among the ξ_{i}(x_{2}), one is x_{3} ≈ 0.92 − 1.02i, which has modulus larger than 1.33. As x_{2} is not singular for any of the R(x, ξ_{i}(x)), the ξ_{i}(x_{2}) are singularities of F. In particular, x_{3} is singular for F.

We conclude as above, by considering the largest singularity x_{s} of F (in modulus), showing that one of the ξ_{i}(x_{s}) is singular for F and larger than |x_{s}| in modulus.

References

[1] D. André, Solution directe du problème résolu par M. Bertrand, C. R. Acad. Sci. Paris 105 (1887) 436–437.

[2] C. Banderier, M. Bousquet-Mélou, A. Denise, D. Gardy, D. Gouyou-Beauchamps and P. Flajolet, Generating functions for generating trees, to appear in Discrete Math.

[3] C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths, to appear in Theoret. Comput. Sci.

[4] E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, A bijection for some paths on the slit plane, Adv. in Appl. Math. 26, no. 2 (2001) 89–96.

[5] M. Bousquet-Mélou, Walks in the quarter plane: Kreweras’ algebraic model, in preparation.

[6] M. Bousquet-Mélou, Walks on the slit plane: other approaches, Adv. in Appl. Math. 27, no. 2-3 (2001) 243–288.

[7] M. Bousquet-Mélou and M. Petkovšek, Linear recurrences with constant coefficients: the multivariate case, Discrete Math. 225 (2000) 51–75.

[8] M. Bousquet-Mélou and G. Schaeffer, Walks on the slit plane, preprint 2000, arXiv:math.CO/0012230. To appear in Probab. Theory Related Fields.

[9] R. Cori and L. Chottin, Une preuve combinatoire de la rationalité d’une série génératrice associée aux arbres, RAIRO Inform. Théor. 16, no. 2 (1982) 113–128.

[10] P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Math. 225 (2000) 121–135.

[11] A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947) 305–313.

[12] W. Feller, An Introduction to Probability Theory and its Applications, Vol.1, John Wiley and Sons, New York, 1950.

[13] P. Flajolet, Analytic models and ambiguity of context-free languages, Theoret. Comput. Sci. 49 (1987) 283–309.

[14] I. M. Gessel, A probabilistic method for lattice path enumeration, J. Statist. Plann. Infererence 14 (1986) 49–58.

[15] I. M. Gessel, A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory. Ser. A 28 (1980) 321–337.

[16] I. M. Gessel and D. Zeilberger, Random walk in a Weyl chamber, Proc. Amer. Math. Soc. 115 (1992) 27-31.

[17] D. J. Grabiner, Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval, Proceedings of FPSAC 2001, Tempe, Arizona, pp. 217– 225.

[18] K. Ishizaki, Hypertranscendency of meromorphic solutions of a linear functional equation, Aequationes Math. 56 (1998) 271–283.

[19] G. Kreweras, Sur une classe de problèmes liés au treillis des partitions d’entiers, Cahiers du B.U.R.O. 6 (1965) 5–105.

[20] J. Labelle, Langages de Dyck généralisés, Ann. Sci. Math. Québec 17 (1993) 53–64.

[21] J. Labelle and Y.-N. Yeh, Generalized Dyck paths, Discrete Math. 82 (1990) 1–6.

[22] G. F. Lawler, Intersections of Random Walks, Probabilities and its applications, Birkhäuser Boston, 1991.

[23] L. Lipshitz, The diagonal of a D-finite power series is D-finite, J. Algebra 113 (1988) 373–378.

[24] L. Lipshitz, D-finite power series, J. Algebra 122 (1989) 353–373.

[25] L. Lipshitz and L. A. Rubel, A gap theorem for power series solutions of algebraic differential equations, Amer. J. Math. 108, no. 2 (1986) 1193–1213.

[26] J. H. Loxton and A. J. van der Poorten, A class of hypertranscendental functions, Aequationes Math. 16 (1977) 93–106.

[27] S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, 1979.

[28] T. V. Narayana, A partial order and its applications to probability theory, Sankhya 21 (1959) 91–98.

[29] H. Niederhausen, The ballot problem with three candidates, Europ. J. Combin. 4 (1983) 161-167.

[30] H. Niederhausen, Lattice paths between diagonal boundaries, Electronic J. Combinatorics 5 (1998) R30.

[31] K. Nishioka, Mahler Functions and Transcendence, Lect. Notes Math. 1631, Springer-Verlag, Berlin, Heidelberg, 1996.

[32] M. Petkovšek, The irrational chess knight, in: Proceedings of the 10^{th} Conference “Formal Power Series and Algebraic Combinatorics”, pp. 513–522, Toronto, June 1998.

[33] M. Petkovšek, H. S. Wilf, and D. Zeilberger, A = B, A. K. Peters, Wellesley, Massachusetts, 1996.

[34] F. Spitzer, Principles of Random Walk, The University Series in Higher Mathematics, Van Nostrand Company, Princeton, 1964.

[35] R. P. Stanley, Differentiably finite power series, Europ. J. Combin. 1 (1980) 175–188.