pith. sign in

arxiv: 2605.16688 · v1 · pith:4MFPJVAWnew · submitted 2026-05-15 · 🧮 math.CO · math.PR

On the small-step quarter plane lattice walks with a non D-finite univariate generating function

Marni Mishna , Juan Pulido This is my paper

Pith reviewed 2026-05-20 15:36 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords quarter-plane walksD-finite generating functionslattice pathsinfinite groupsasymptotic analysiscombinatorial enumerationdecoupling functions
0
0 comments X

The pith

Twenty-one infinite-group quarter-plane walks have non-D-finite univariate generating functions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper advances the Bousquet-Mélou and Mishna conjecture by proving that the univariate generating function fails to be D-finite for 21 of the 56 small-step quarter-plane models whose groups are infinite. It handles the five singular models by direct arguments, then applies known asymptotic expansions together with probabilistic estimates to establish the result for three zero-drift models and thirteen models with polar interior drift. Nine further infinite-group models are shown to possess differentially algebraic endpoint series via decoupling functions, while numerical singular-exponent checks lead to a conjecture of non-D-finiteness for boundary series in 21 additional cases. A reader cares because these results tighten the classification of which lattice-path counting problems admit solutions by linear differential equations.

Core claim

The authors establish non-D-finiteness of the univariate counting generating function for the five singular infinite-group models, the three zero-drift models, and the thirteen polar-interior-drift models among the 56 infinite-group small-step quarter-plane walks. They further show that nine infinite-group models have differentially algebraic series for the endpoint counts Q(1,0;t) or Q(0,1;t) through the use of decoupling functions, and they formulate a conjecture that numerical singular-exponent data indicate non-D-finiteness of one boundary series for each of 21 remaining models.

What carries the argument

The group of the walk, which is finite or infinite and governs the functional equation satisfied by the generating function Q(x,y;t).

If this is right

  • The univariate generating functions of these 21 walks cannot be solutions to linear differential equations with polynomial coefficients.
  • Their asymptotic growth rates follow forms, such as specific singular exponents or logarithmic factors, that are incompatible with D-finite functions.
  • The conjecture that D-finiteness holds if and only if the group is finite is verified for these 21 infinite-group models.
  • Decoupling functions produce differentially algebraic endpoint series even when the full bivariate generating function remains non-D-finite.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same asymptotic-plus-probabilistic approach could be tested on the remaining unresolved infinite-group models to gather further evidence.
  • The appearance of differentially algebraic endpoint series in some infinite-group cases suggests that partial algebraicity may occur without full D-finiteness of the bivariate series.
  • Numerical singular-exponent estimation offers a practical way to conjecture non-D-finiteness for models where closed-form proofs are not yet available.

Load-bearing premise

The asymptotic results of Bostan–Raschel–Salvy together with the probabilistic estimates of Denisov–Wachtel and Duraj apply directly to the zero-drift and polar-interior-drift models under consideration.

What would settle it

An explicit linear differential equation with polynomial coefficients satisfied by the generating function of any one of the 21 models would falsify the non-D-finiteness claim for that model.

Figures

Figures reproduced from arXiv: 2605.16688 by Juan Pulido, Marni Mishna.

Figure 1
Figure 1. Figure 1: The five singular models The non-D-finiteness of QS(t) was initially established in a case by case analysis [18, 16] demonstrating that the generating function had an infinite number of singularities, a property inconsistent with D-finiteness. Theorem 4 (Mishna and Rechnitzer 2009, Melczer and Mishna 2014, [18, 16]). All five of small-step singular models have a non D-finite counting series. Subsequently, … view at source ↗
Figure 2
Figure 2. Figure 2: The nine infinite-group models which are decoupled for walks starting at the origin. 5A multivariate series F(x, y;t) is differentially algebraic in t if there exist an integer r ≥ 0 and a nonzero polynomial Φ ∈ Q(x, y, t)[z0, z1, . . . , zr] such that Φ [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: infinite-group models which admit decoupling functions for walks starting away from the origin. Returning to walks starting at the origin, Theorem 8 does not settle the D-finiteness of the total counting series Q(1, 1;t) : every D-finite series is differentially algebraic, but the converse does not hold in general. From the perspective of the Bousquet-M´elou–Mishna conjecture, these nine models are therefo… view at source ↗
read the original abstract

We report on the status of the conjecture of Bousquet-M\'elou and Mishna that the univariate counting generating function of a small-step quarter-plane lattice model is D-finite if and only if the group of the walk is finite. While the finite-group case is fully resolved, the infinite-group case remains incomplete. We list the arguments for the non-D-finiteness for 21 of the 56 infinite-group models: the five singular models, three models with zero drift and thirteen models with polar interior drift. The proof of the latter two families uses asymptotic results of Bostan--Raschel--Salvy combined with probabilistic estimates of Denisov--Wachtel and Duraj. We further identify nine infinite-group models whose endpoint counting series are differentially algebraic via decoupling functions, though this does not settle their D-finiteness. For 21 of the remaining models, numerical estimation of singular exponents suggests non-D-finiteness of one of its the boundary series $Q(1,0;t)$ or $Q(0,1;t)$, and we state a conjecture to this effect.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. This manuscript reports on the status of the Bousquet-Mélou–Mishna conjecture that the univariate generating function of small-step quarter-plane lattice walks is D-finite if and only if the associated group is finite. While the finite-group case is settled, for the 56 infinite-group models the authors provide explicit non-D-finiteness arguments for 21 models: the five singular models, three with zero drift, and thirteen with polar interior drift, relying on asymptotic results from Bostan–Raschel–Salvy combined with probabilistic estimates from Denisov–Wachtel and Duraj. They further identify nine infinite-group models whose endpoint counting series are differentially algebraic using decoupling functions. For the remaining 21 models, numerical estimation of singular exponents is used to suggest non-D-finiteness of boundary series Q(1,0;t) or Q(0,1;t), accompanied by a conjecture.

Significance. If the non-D-finiteness arguments hold, the paper advances the classification by handling 21 of the 56 infinite-group cases and isolates a clean conjecture for the rest. The explicit identification of nine differentially algebraic endpoint series via decoupling functions is a concrete positive contribution. The work functions effectively as a status report that narrows the remaining open cases.

major comments (3)
  1. [§4] §4 (zero-drift models): the non-D-finiteness argument for the three zero-drift models invokes Bostan–Raschel–Salvy singular expansions together with Denisov–Wachtel tail estimates but supplies no per-model verification that the kernel singularity is dominant, that there are no competing boundary singularities, and that the drift and positivity hypotheses of the cited theorems hold for each of the three specific step sets.
  2. [§5] §5 (polar-interior-drift models): the non-D-finiteness claim for the thirteen polar-interior-drift models likewise rests on direct applicability of Bostan–Raschel–Salvy, Denisov–Wachtel and Duraj results; the manuscript asserts applicability without explicit checks for each model that the interior-drift condition, step-set positivity, and absence of unexpected polar singularities are satisfied, any one of which would invalidate the argument for that model.
  3. [Numerical section] Numerical section (21 remaining models): the singular-exponent estimates are offered only as suggestive numerical support for the stated conjecture on non-D-finiteness of Q(1,0;t) or Q(0,1;t); without reported precision, error bounds, or a rigorous justification of the extrapolation procedure, the evidence remains too weak to be load-bearing for any firm claim.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'one of its the boundary series' contains a typographical error and should read 'one of its boundary series'.
  2. The paper would benefit from a short table summarizing, for each of the 56 infinite-group models, which argument (singular, zero-drift, polar, decoupling, or numerical) is used; this would improve readability of the status report.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough and constructive report. We address each major comment in turn and indicate planned revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (zero-drift models): the non-D-finiteness argument for the three zero-drift models invokes Bostan–Raschel–Salvy singular expansions together with Denisov–Wachtel tail estimates but supplies no per-model verification that the kernel singularity is dominant, that there are no competing boundary singularities, and that the drift and positivity hypotheses of the cited theorems hold for each of the three specific step sets.

    Authors: We acknowledge that explicit per-model verification is not provided in the current text. The three zero-drift models satisfy the general hypotheses of the cited theorems (kernel singularity dominance, no competing boundary singularities, and the required drift/positivity conditions), but we agree that case-by-case confirmation would improve clarity and rigor. In the revised version we will add an appendix or subsection containing these explicit checks for each of the three step sets. revision: yes

  2. Referee: [§5] §5 (polar-interior-drift models): the non-D-finiteness claim for the thirteen polar-interior-drift models likewise rests on direct applicability of Bostan–Raschel–Salvy, Denisov–Wachtel and Duraj results; the manuscript asserts applicability without explicit checks for each model that the interior-drift condition, step-set positivity, and absence of unexpected polar singularities are satisfied, any one of which would invalidate the argument for that model.

    Authors: We thank the referee for this observation. The thirteen models were selected precisely because they meet the interior-drift, positivity, and singularity conditions of the cited results, yet we concede that the manuscript does not display the verification for each individual model. We will revise §5 to include a compact table or set of short paragraphs confirming these conditions model by model, thereby making the applicability fully transparent. revision: yes

  3. Referee: [Numerical section] Numerical section (21 remaining models): the singular-exponent estimates are offered only as suggestive numerical support for the stated conjecture on non-D-finiteness of Q(1,0;t) or Q(0,1;t); without reported precision, error bounds, or a rigorous justification of the extrapolation procedure, the evidence remains too weak to be load-bearing for any firm claim.

    Authors: We agree that the numerical evidence is heuristic and is presented only to motivate the conjecture, not to prove it. The manuscript already qualifies the estimates as “suggestive.” To address the referee’s concern we will expand the section with explicit statements of the observed precision, conservative error bounds derived from the fitting procedure, and a brief description of the extrapolation method, while reiterating that these data support but do not establish the conjecture. revision: partial

Circularity Check

0 steps flagged

No circularity: non-D-finiteness arguments for infinite-group models rest on external asymptotic and probabilistic results from independent authors

full rationale

The paper's central claims for the 21 models invoke the asymptotic expansions of Bostan–Raschel–Salvy and the tail estimates of Denisov–Wachtel and Duraj. These are results by authors with no overlap to Mishna or Pulido, and the manuscript treats them as established external theorems whose hypotheses are asserted to hold for the listed walk models. No derivation step reduces a claimed non-D-finiteness statement to a quantity defined inside the paper, to a fitted parameter, or to a self-citation chain. The reference to the Bousquet-Mélou–Mishna conjecture is merely contextual and does not serve as a load-bearing premise for the new arguments. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper depends on the prior complete classification of all 79 models into finite- and infinite-group cases and on the applicability of two external asymptotic/probabilistic theorems; no new free parameters or postulated entities are introduced.

axioms (2)
  • domain assumption The prior classification of the 79 small-step quarter-plane models into 23 finite-group and 56 infinite-group cases is exhaustive and correct.
    The paper treats the list of 56 infinite-group models as given and works case-by-case within it.
  • domain assumption The asymptotic formulas of Bostan–Raschel–Salvy and the probabilistic tail estimates of Denisov–Wachtel and Duraj apply without modification to the zero-drift and polar-interior-drift walk models studied here.
    These external results are invoked to conclude non-D-finiteness for the 16 models in those families.

pith-pipeline@v0.9.0 · 5723 in / 1583 out tokens · 46494 ms · 2026-05-20T15:36:05.637792+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Counting quadrant walks via Tutte’s invariant method

    O. Bernardi, M. Bousquet-M´ elou, and K. Raschel. “Counting quadrant walks via Tutte’s invariant method”. In:Combinatorial Theory1 (2021), Paper No. 3, 77.doi:10.5070/C61055360

    work page doi:10.5070/c61055360 2021

  2. [2]

    Differential transcendence of Bell numbers and relatives: a Galois theoretic approach

    A. Bostan, L. Di Vizio, and K. Raschel. “Differential transcendence of Bell numbers and relatives: a Galois theoretic approach”. In:American Journal of Mathematics146.6 (2024)

    work page 2024

  3. [3]

    On crossings of arbitrary curves by certain Gaussian processes

    A. Bostan and M. Kauers. “The complete generating function for Gessel walks is algebraic”. In:Pro- ceedings of the American Mathematical Society138.9 (2010), pp. 3063–3078.doi:10.1090/S0002- 9939-2010-10398-2

    work page doi:10.1090/s0002- 2010

  4. [4]

    Non-D-finite excursions in the quarter plane

    A. Bostan, K. Raschel, and B. Salvy. “Non-D-finite excursions in the quarter plane”. In:Journal of Combinatorial Theory. Series A121 (2014), pp. 45–63.doi:10.1016/j.jcta.2013.09.005.url: http://dx.doi.org/10.1016/j.jcta.2013.09.005

    work page doi:10.1016/j.jcta.2013.09.005.url: 2014

  5. [5]

    Walks with small steps in the quarter plane

    M. Bousquet-M´ elou and M. Mishna. “Walks with small steps in the quarter plane”. In:Algorithmic probability and combinatorics. Vol. 520. Contemp. Math. Amer. Math. Soc., Providence, RI, 2010, pp. 1–39.doi:10.1090/conm/520/10252

    work page doi:10.1090/conm/520/10252 2010

  6. [6]

    Random walks in cones

    D. Denisov and V. Wachtel. “Random walks in cones”. In:The Annals of Probability43.3 (2015), pp. 992–1044.doi:10.1214/13-AOP867.url:https://doi.org/10.1214/13-AOP867

    work page doi:10.1214/13-aop867.url:https://doi.org/10.1214/13-aop867 2015

  7. [7]

    On the nature of the generating series of walks in the quarter plane

    T. Dreyfus, C. Hardouin, J. Roques, and M. F. Singer. “On the nature of the generating series of walks in the quarter plane”. In:Inventiones Mathematicae213.1 (2018), pp. 139–203.doi:10.1007/s00222- 018-0787-z

    work page doi:10.1007/s00222- 2018

  8. [8]

    Walks in the quarter plane: genus zero case

    T. Dreyfus, C. Hardouin, J. Roques, and M. F. Singer. “Walks in the quarter plane: genus zero case”. In:Journal of Combinatorial Theory. Series A174 (2020), pp. 105251, 25.doi:10.1016/j.jcta. 2020.105251

    work page doi:10.1016/j.jcta 2020

  9. [9]

    Enumeration of weighted quadrant walks: criteria for alge- braicity and D-finiteness

    T. Dreyfus, A. E. Price, and K. Raschel. “Enumeration of weighted quadrant walks: criteria for alge- braicity and D-finiteness”. In:arXiv preprint arXiv:2409.12806(2024)

    work page arXiv 2024

  10. [10]

    Random walks in cones: the case of nonzero drift

    J. Duraj. “Random walks in cones: the case of nonzero drift”. In:Stochastic Processes and their Applications124.4 (2014), pp. 1503–1518.doi:10.1016/j.spa.2013.12.003.url:https://doi. org/10.1016/j.spa.2013.12.003

    work page doi:10.1016/j.spa.2013.12.003.url:https://doi 2014

  11. [11]

    Fayolle, R

    G. Fayolle, R. Iasnogorodski, and V. Malyshev.Random walks in the quarter-plane. Vol. 40. Applica- tions of Mathematics (New York). Springer-Verlag, Berlin, 1999.doi:10.1007/978-3-642-60001-2

    work page doi:10.1007/978-3-642-60001-2 1999

  12. [12]

    Gohier, E

    L. Gohier, E. Humbert, and K. Raschel.Enumeration of walks in multidimensional orthants and re- flection groups. 2025.doi:10.48550/ARXIV.2501.05654.url:https://arxiv.org/abs/2501.05654 (visited on 05/15/2026)

    work page doi:10.48550/arxiv.2501.05654.url:https://arxiv.org/abs/2501.05654 2025

  13. [13]

    On the D-finiteness of generating functions counting small steps walks in the quadrant

    C. Hardouin. “On the D-finiteness of generating functions counting small steps walks in the quadrant”. In:arXiv preprint arXiv:2509.22464(2025). 10

    work page arXiv 2025

  14. [14]

    Spherical Lagrangians via ball packings and symplectic cutting

    C. Hardouin and M. F. Singer. “On differentially algebraic generating series for walks in the quarter plane”. en. In:Selecta Mathematica27.5 (Nov. 2021), p. 89.doi:10.1007/s00029- 021- 00703- 9. url:https://link.springer.com/10.1007/s00029-021-00703-9(visited on 05/15/2026)

    work page doi:10.1007/s00029- 2021

  15. [15]

    On the functions counting walks with small steps in the quarter plane

    I. Kurkova and K. Raschel. “On the functions counting walks with small steps in the quarter plane”. In:Publications Math´ ematiques. Institut de Hautes ´Etudes Scientifiques116 (2012), pp. 69–114.doi: 10.1007/s10240-012-0045-7

    work page doi:10.1007/s10240-012-0045-7 2012

  16. [16]

    Singularity analysis via the iterated kernel method

    S. Melczer and M. Mishna. “Singularity analysis via the iterated kernel method”. In:Combinatorics, Probability and Computing23.5 (2014), pp. 861–888.doi:10.1017/S0963548314000145

    work page doi:10.1017/s0963548314000145 2014

  17. [17]

    Classifying lattice walks restricted to the quarter plane

    M. Mishna. “Classifying lattice walks restricted to the quarter plane”. In:Journal of Combinatorial Theory. Series A116.2 (2009), pp. 460–477.doi:10.1016/j.jcta.2008.06.011

    work page doi:10.1016/j.jcta.2008.06.011 2009

  18. [18]

    Two non-holonomic lattice walks in the quarter plane

    M. Mishna and A. Rechnitzer. “Two non-holonomic lattice walks in the quarter plane”. In:Theoretical Computer Science410.38-40 (2009), pp. 3616–3630.doi:10.1016/j.tcs.2009.04.008

    work page doi:10.1016/j.tcs.2009.04.008 2009

  19. [19]

    Wasow.Asymptotic expansions for ordinary differential equations

    W. Wasow.Asymptotic expansions for ordinary differential equations. Vol. Vol. XIV. Pure and Applied Mathematics. Interscience Publishers John Wiley & Sons, Inc., New York-London-Sydney, 1965. 11 AppendixA.Estimated singular exponents In the tables that followα i,j is the estimated singular exponent forQ(i, j;t) based on values ofa(i, j, n) up ton= 500. Th...

    work page 1965