no. 16 · Tuesday 17 November 2026
On small-step quarter plane lattice walks with a non D-finite univariate generating function
Abstract
We report on the status of the conjecture of Bousquet-Mélou and Mishna that the univariate counting generating function of a small-step quarter-plane lattice model is D-finite if and only if a particular group associated to the walk is finite. While the finite-group case is fully resolved, the infinite-group case remains incomplete. First we survey the known cases. By invoking asymptotics results from probability theory and a case analysis completed by Bostan, Raschel and Salvy (2014), we establish that the generating functions of 14 infinite-group models are not D-finite, and that for an additional 18 models the generating function for walks that end on an axis is not D-finite. We conclude with a discussion of limitations of asymptotic arguments to resolve the remaining cases.
- comments
- 17 pages; A Conjecture about the non D-finiteness of Q(1,0;t) for several versions in v1 is proved in this version. Lucas Pannier is added as a co-author
- fields
- Combinatorics, Probability