Source-linked AI summary
The complete Generating Function for Gessel Walks is Algebraic
Alin Bostan, Manuel Kauers
TL;DR
Whether the complete Gessel-walk generating function was D-finite in t was unknown, and even its excursion specialization was generally thought transcendental. The paper lifts the excursion result to the full generating function, proving G(t;x,y) algebraic.
Problem
Before this work, it was unknown whether G(t;x,y) was D-finite in t, while G(t;0,0) was generally thought transcendental.
Source: §1 · p. 3, §3.1 · p. 9Method
The paper lifts the excursion-series result by keeping x and y as parameters and proving algebraicity for the complete generating function.
Source: §1 · p. 3Results
G(t;x,y) is algebraic, implying D-finiteness in each variable and P-finite endpoint sequences for every (i,j).
Source: §1 · p. 3Takeaways & Limitations
The result settles several conjectures made by Petkovšek and Wilf [26, §2].
Source: §1 · p. 3The existence proof cannot use the implicit function theorem or rational parametrization, because the relevant curves have positive genus.
Source: §3.2.1 · p. 11
Abstract
from arXiv · showhide
Gessel walks are lattice walks in the quarter plane $\set N^2$ which start at the origin $(0,0)\in\set N^2$ and consist only of steps chosen from the set $\{\leftarrow,\swarrow,\nearrow,\to\}$. We prove that if $g(n;i,j)$ denotes the number of Gessel walks of length $n$ which end at the point $(i,j)\in\set N^2$, then the trivariate generating series $G(t;x,y)=\sum_{n,i,j\geq 0} g(n;i,j)x^i y^j t^n$ is an algebraic function.
1. Introduction
The paper proves that the complete generating function for quarter-plane Gessel walks is algebraic, extending the known algebraicity of the excursion series. This resolves an open case among quarter-plane walk step sets and yields recurrence consequences for counts ending at arbitrary points.
1. Introduction
- Among the 79 inherently different quarter-plane step sets studied in [7], this was the single case that resisted their analyses.That study proved 22 cases D-finite and gave evidence that 56 are not D-finite; the Gessel step set is {←, ↙, ↗, →}.Source: §1 · p. 1
- The excursion series G(t; 0, 0) was known to be D-finite, and its algebraicity was less obvious despite the earlier proof of the Gessel conjecture.The conjecture concerned a hypergeometric closed form for the excursion counts.Source: §1 · p. 2
- G(t; x, y) is algebraic, extending the algebraicity result for G(t; 0, 0) to the complete generating function.The authors avoid exhibiting a polynomial for the full series because its minimal polynomial is estimated to be about 30Gb.Source: §1 · pp. 2–3
- Algebraicity implies that G(t; x, y) is D-finite in each variable and that g(n; i, j) is P-finite for every endpoint, settling conjectures in [26, §2].The paper notes that some endpoint sequences, unlike the excursion sequence, are not hypergeometric.Source: §1 · p. 3
- The proof uses automated guessing and computer algebra, manipulating annihilating polynomials for G(t; x, 0) and G(t; 0, y) rather than for the full series.The expressions required specialized algorithms and substantial computing resources, and the computations used Magma.Source: §1 · p. 3
2. A Dry Run: Kreweras walks
The Kreweras-walk example proves algebraicity by guessing an equation for a boundary generating series and then rigorously identifying and verifying its solution. This dry run illustrates a strategy later used for Gessel walks, where the computations are too large to reproduce in print.
2. A Dry Run: Kreweras walks
- The Kreweras calculation is presented as a more reproducible example of the reasoning used for Theorem 3, whose intermediate expressions are too large to print.Theorem 3’s computations required special-purpose software and fast hardware.Source: §2 · p. 3
- The kernel method couples x and y to reduce the functional equation, extracting an equation for the boundary series; a valuation argument gives its unique power-series solution.The reduced equation’s unique solution in Q[[x, t]] is U = F(t; x, 0).Source: §2 · p. 4
2.2. Proving.
- The computer-assisted proof guesses an equation for F(t; x, 0), then proves its candidate is the unique solution of the reduced kernel equation.Uniqueness identifies the candidate with the actual boundary series, which certifies the guessed equation.Source: §2 · p. 4
2. A Dry Run: Kreweras walks
- F(t; x, y) is algebraic: the proof establishes an algebraic equation for F(t; x, 0), then uses the functional equation to obtain algebraicity of the full generating function.The result is stated as Theorem 5.Source: §2 · p. 4
2.1. Guessing.
- Automated guessing derives candidate equations from initial power-series terms, but rigorous results require independent proof, and very high precision can make guessing extremely slow with traditional software.The reported Maple12 guessing computation used about 80Mb of memory and took less than 20 seconds on a modern laptop.Source: §2.1 · p. 5
2.2.1. Existence and Uniqueness.
- A genus-zero rational parameterization constructs the candidate boundary series in Q[[x, t]], resolving the obstacle that the implicit function theorem does not directly establish its existence there.The parameterization yields the unique power-series solution of the guessed polynomial.Source: §2.2.1 · p. 6
2.2.2. Compatibility with the reduced kernel equation.
- Resultant computations show the substituted candidate is a root of the guessed polynomial; uniqueness then makes it satisfy the reduced kernel equation.This verifies compatibility without relying on another guessing routine.Source: §2.2.2 · pp. 6–7
2.3. Consequences.
- Setting x to 0 gives an algebraic equation for the Kreweras excursion series and a coefficient recurrence, providing an alternative proof that the series is algebraic and hypergeometric.The recurrence relates a_(n+3) to a_n.Source: §2.3 · p. 7
3. Gessel walks
The section proves algebraicity of the full Gessel-walk generating function by identifying algebraic boundary series that satisfy the reduced kernel equations. It also presents consequences for D-finiteness, coefficient computation, endpoint-sequence conjectures, radical representations, and minimal-polynomial degree patterns, while noting limits on explicit formulas.
3. Gessel walks
- The asymmetric Gessel step set yields two equations for unknown series U and V, both containing G(t; 0, 0); Lemma 7 equates the candidates with U and V, and (KG) implies G(t; x, y) is algebraic.Source: §3 · pp. 8–9
3.1. Guessing.
- Zero p-curvature for the guessed order-11 differential operators at every tested prime p < 100 motivated the conjecture that the Gessel generating function is algebraic, in light of Grothendieck’s conjecture.The operators even right-divided D_t^p for the tested primes.Source: §3.1 · p. 10
- Using an interpolation scheme, the authors discovered P1 and P2, which vanish when evaluated at U(t, x) and V(t, y), respectively, modulo t^1200; both passed heuristic plausibility tests.P1 has degrees 24, 44, and 32 in T, t, and x, respectively; P2 has degrees 24, 46, and 56 in T, t, and y, respectively.Source: §3.1 · p. 11
3.2.1. Existence and Uniqueness.
- Because the guessed polynomials define positive-genus curves, the authors used McDonald’s existence result, coefficient recurrences, and Puiseux analysis to establish power-series solutions.The analysis rules out fractional and negative integral exponents for a partial solution, leaving a power series.Source: §3.2.1 · p. 11
3.2.2. Compatibility with the reduced kernel equation.
- Special-purpose resultant computations produced identical minimal polynomials for both sides of the reduced kernel equation, and matching initial terms established compatibility and completed the proof of Theorem 3.Maple and Mathematica could not handle the required resultants, so the authors used their Magma implementation of specialized algorithms.Source: §3.2.2 · p. 12
3.3. Consequences.
- Corollary 8 states that the listed series are algebraic.Source: §3.3 · p. 12
- The arbitrary-endpoint series, the x- and y-axis endpoint series, and G(t; 0, 0) have representations in nested radicals; the more involved representations and minimal polynomials are available online.Source: §3.3 · p. 12
- The conjecture that g(n; 0, j) for fixed j and g(n; 1, 0) are P-finite is correct, but the conjecture that g(n; 2, 0) is not P-finite is false [26].Source: §3.3 · p. 12
- The authors empirically observed piecewise degree formulas for minimal polynomials of G_i,j(t), but could not prove them in general.Source: §3.3 · p. 13
- The proof does not yield the minimal polynomial of G(t; x, y), whose estimated degrees in T, t, x, and y are 72, 141, 263, and 287, implying over 750 million terms.Source: §3.3 · p. 13
- For fixed i, j, g(n; i, j) is computable with O(n) arithmetic operations; for fixed x, y, so is [t^n]G(t; x, y).Source: §3.3 · p. 13