Classifying lattice walks restricted to the quarter plane (Q1003654)

The paper is concerned with the nature of generating functions of random lattice walks restricted to the first quadrant. It discusses ways to decide if these functions (series) are algebraic, transcendental holonomic or not holonomic. The focus is restricted to step sets which are subsets of \( \{-1,0,1\}^2\backslash\{(0,0)\} \), the so called compass steps. Section 0 gives an introduction to the problem. Section 1 introduces the notions of walks, generating function, fundamental equation, kernel and its associated group. The concept of symmetry w.r.t. the \(x\)-axis and \(y\)-axis introduced below Theorem 1.2 is a little bit odd. I would call a set \(Y\) satisfying the property that it always contains both points \((i,j)\) and \((i,-j)\) symmetric w.r.t. the \(x\)-axis and not the way it is defined in the paper. Section 1.1 of the paper discusses the connection between walks and formal languages. In Section 1.2 the fundamental equation is given which is a recurrence relation for the generating function in terms of the step set. Section 1.3. classifies formal power series in terms of algebraicity, transcendental holonomicity and non holonomicity. It is a somewhat sloppy section in which notations are not introduced properly and Theorems are quoted without introducing notation at all. Section 1.4 introduces some operations on step sets. The operation of flipping a step set across the line \(x=y\) preserves the nature of generating functions. The effect of the operation of reversing the direction of the steps in a step set, on the generating function is undecided (unknown). Section 1.5 gives some techniques for the enumeration of walks. Using the fundamental equation as a starting point the notion of the rational kernel is introduced, and a group associated to this kernel is defined, which is generated by two generators \( \tau_x \) and \(\tau_y \), that are defined in Definition 1.2. Table 1 gives all compass step sets where the group generated by the two generators is finite. As a general remark on Table 1 I would like to state that the two generators are interchanged in this Table, since \( \tau_x \) should fix the \(x\)-coordinate according to Definition 1.2 and not the \(y\)-coordinate as in Table 1. Furthermore in the second picture of the sixth line of Table 1 the horizontal arrows corresponding to the W and E directions should be added. Section 2 restricts the attention to compass step sets of cardinality 3. It starts with a discussion in which the 56 possible step sets are grouped together into 11 isomorphy classes. Different from what is stated, only for 9 of the 11 classes explicit generating functions are given in Table 2. Section 2.1. is devoted to the first four classes of Table 2, the singular algebraic ones. The Section starts by introducing the notion of singular step set and it is stated that there is a link between singularity and degeneracy of the group of the walk. This link is however not made explicit. In the definition of Singular step sets the last entity mentioned under 1 should be reflect(rev(\(S_1\))) instead of reflect(\(S_1\)). The fourth picture of figure 1, that is corresponding to this entity is missing the arrow (vector) corresponding to the W direction. The proof of proposition 2.1 contains a lot of unclear notation if one is not familiar with the terminology of formal languages. Moreover the expression for \(S(x,y,t)\) is false it should be: \[ S(x,y,t)= \frac{M(x,y,t)}{1-M(x,y,t)A(x,y,t)} . \] In determining the formula for \(Q(x,y,t)\) when the step set is \(\{\text{N,NE,SW}\}\), the definition of \(C(x,y,t)\) is false. It should be: \(C(x,y,t)=yt\). The solution for \(S\) is attained by solving the quadratic equation for \(M\). In general such a quadratic equation has two solutions and it is not explained how in the expression for \(Q\) the choice is made for one of the solutions. Further on in the paper it is mentioned somewhere that the sign is determined such that \(M\) vanishes for \(t=0\). Nevertheless from the given formula for \(Q\) the function \(W\) in the second line of Table 2 can easily be determined by taking \(x=y=1\). The singular step sets are divided into four classes corresponding to the first four lines of Table 2. The author should have pointed out that different elements of those classes have the same \(W\) but not necessarily the same \(Q\). Section 2.2 gives an outline for the rest of the paper devoted to the nonsingular walks. In Section 2.3 the remaining algebraic walks are treated. Section 2.4 is devoted to holonomic walks and Section 2.5 to non holonomic walks. Section 2.3 is a very sloppy section. It starts with a formula for \( Q_5 \) in Theorem 2.2 which should have a factor \(x\) in front of \( Q_5(x,0,t) \) and a factor \(y\) in front of \( Q_5(y,0,t) \) (in stead of \( Q_5(0,y,t) \). The formula 2.3 contains an \(R\) at the left hand side which should be a \(Q\). In the expression of \( K_r^{-1}\) the second term is inaccurate. The factoring of \(\delta\) into \(\delta+\), \(\delta0\) and \(\delta-\) I take for granted but unfortunately the author does not give an explicit formula for \(\delta+\), nevertheless it is needed further on. The formula below 2.5 should have as a final RHS \( x/\delta0 (1+\bar{x}X + O())\) in stead of a minus sign. The formula below this one is totally unclear. Also the last formula on page 469 is unclear since no formula for \(\delta+\) is given (maybe it can also be obtained from Bousquet-Milou?). Finally I do not trust the first formula on page 420. The results given in Theorems 2.3 and 2.4 might still be correct, but in the derivation too much is shoveled under the carpet. The W for step set 6 in Table 2 is in accordance with Theorems 2.3 and 2.4. For the step set number 7 walks are linked to certain Young Tableaux, \(n_1\) is the number of \(N\)-steps, \(n_2\) is the number of \(E\) steps and \(n_3\) is the number of SW steps. According to me the \(x\)-coordinate of such a walk equals \(n_2-n_3\) and the \(y\)-coordinate equals \(n_1-n_2\) and not as is stated at the last line of page 470, and the first line of page 471. Also in the formula for \(a_{ij}(n)\) the i and the j should be interchanged. In Section 2.4. formulas for \(Q_8\) and \(Q_9\) are determined. The derivation for \(Q_8\) seems to be correct however in the result stated in Theorem 2.5 there is missing a factor \(y\) in front of the sole \(X\). The derivation for \(Q_9\) is omitted (left to the reader?). I did not go through the details but can imagine that the formula for \(Q_9\) contains the same omission as the one for \(Q_8\), i.e.. probably there should be a factor \(x\) in front of the sole \(Y\) in the function for \(Q_9\). The functions for \(W\) in Table 2 for the step sets 8 and 9 are according to the derived \(Q\)'s. Section 2.5 is concerned with step sets number 10 and 11 of Table 2. It contains only a rough sketch for the results that are actually derived in a forthcoming paper of the author. No explicit enumerative expressions are determined. The paper finishes with Section 3, that contains quite a few conjectures and directions for future work. Concerning the acknowledgments in view of my review I have some doubts on the carefulness of the anonymous referees (or the first version of the paper must have been even worse). My conclusion is that I have the impression that the given results are more or less correct, the material presented is interesting, the author did a lot of good work, but the proofs need careful revision.