Abstract
Many recent papers deal with the enumeration of 2-dimensional walks with prescribed steps confined to the positive quadrant. The classification is now complete for walks with steps in \({\{0, \pm 1\}^{2}}\): the generating function is D-finite if and only if a certain group associated with the step set is finite. We explore in this paper the analogous problem for 3- dimensional walks confined to the positive octant. The first difficulty is their number: we have to examine no less than 11074225 step sets in \({\{0, \pm 1\}^{3}}\) (instead of 79 in the quadrant case). We focus on the 35548 that have at most six steps. We apply to them a combined approach, first experimental and then rigorous. On the experimental side, we try to guess differential equations. We also try to determine if the associated group is finite. The largest finite groups that we find have order 48 — the larger ones have order at least 200 and we believe them to be infinite. No differential equation has been detected in those cases. On the rigorous side, we apply three main techniques to prove D-finiteness. The algebraic kernel method, applied earlier to quadrant walks, works in many cases. Certain, more challenging, cases turn out to have a special Hadamard structure which allows us to solve them via a reduction to problems of smaller dimension. Finally, for two special cases, we had to resort to computer algebra proofs. We prove with these techniques all the guessed differential equations. This leaves us with exactly 19 very intriguing step sets for which the group is finite, but the nature of the generating function still unclear.
Similar content being viewed by others
References
Abramov, S.A., van Hoeij, M.: Desingularization of linear difference operators with polynomial coefficients. In: Dooley, S. (ed.) Proceedings of ISSAC’99, pp. 269–275. ACM New York, NY (1999)
Banderier C., Flajolet P.: Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci. 281(1-2), 37–80 (2002)
Bertrand D., Beukers F.: Équations différentielles linéaires et majorations de multiplicités. Ann. Sci. École Norm. Sup. 4, 18(1), 181–192 (1985)
Bostan, A., Chyzak, F., van Hoeij, M. Kauers, M., Pech, L.: Explicit differentiably finite generating functions of walks with small steps in the quarter plane. Priprint. Available at https://arxiv.org/abs/1606.02982 (2016)
Bostan, A., Kauers, M.: Automatic classification of restricted lattice walks. In: Krattenthaler, C., Strehl, V., Kauers, M. (eds.) 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Discrete Math. Theor. Comput. Sci. Proc., AK, pp. 201–215. Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2009)
Bostan A., Kauers M.: The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc. 138(9), 3063–3078 (2010)
Bostan, A., Kurkova, I., Raschel, K.: A human proof of Gessel’s lattice path conjecture. Trans. Amer. Math. Soc. (to appear)
Bostan A., Raschel K., Salvy B.: Non-D-finite excursions in the quarter plane. J. Combin. Theory Ser. A 121, 45–63 (2014)
Bousquet-Mélou, M.: Counting walks in the quarter plane. In: Chauvin, B., Flajolet, P., Gardy, D.,Mokkadem, A. (eds.) Mathematics and Computer Science, II (Versailles, 2002), Trends Math., pp. 49–67. Birkhäuser, Basel (2002)
Bousquet-Mélou M.: Walks in the quarter plane: Kreweras’ algebraic model. Ann. Appl. Probab. 15(2), 1451–1491 (2005)
Bousquet-Mélou, M., Mishna, M.: Walks with small steps in the quarter plane. In: Lladser, M.E., Maier, R.S., Mishna, M., Rechnitzer, A. (eds.) Algorithmic Probability and Combinatorics. Contemp. Math., Vol. 520, pp. 1–39. Amer. Math. Soc., Providence, RI (2010)
Bousquet-Mélou M., Petkovšek M.: Linear recurrences with constant coefficients: the multivariate case. Discrete Math. 225(1-3), 51–75 (2000)
Bousquet-Mélou M., Petkovšek M.: Walks confined in a quadrant are not always D-finite. Theoret. Comput. Sci. 307(2), 257–276 (2003)
Chudnovsky, G.V.: Rational and Padé approximations to solutions of linear differential equations and the monodromy theory. In: Iagolnitzer, D. (ed.) Complex Analysis, Microlocal Calculus and Relativistic Quantum Theory (Proc. Internat. Colloq., Centre Phys., Les Houches, 1979), Lecture Notes in Phys., Vol. 126, pp. 136–169. Springer, Berlin-New York (1980)
Cormier O., Singer M.F., Trager B.M., Ulmer F.: Linear differential operators for polynomial equations. J. Symbolic Comput. 34(5), 355–398 (2002)
Duchon P.: On the enumeration and generation of generalized Dyck words. Discrete Math. 225(1-3), 121–135 (2000)
Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter-Plane. Applications of Mathematics (New York), Vol. 40. Springer-Verlag, Berlin (1999)
Fayolle G., Raschel K.: On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane. Markov Process. Related Fields 16(3), 485–496 (2010)
Flajolet P.: Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci. 49(2-3), 283–309 (1987)
Gessel I.M.: A factorization for formal Laurent series and lattice path enumeration. J. Combin. Theory Ser. A 28(3), 321–337 (1980)
Gessel I.M.: A probabilistic method for lattice path enumeration. J. Statist. Plann. Inference 14(1), 49–58 (1986)
van Hoeij M.: Factorization of differential operators with rational functions coefficients. J. Symbolic Comput. 24(5), 537–561 (1997)
Kauers, M.: Guessing handbook. Technical Report RISC 09-07. Johannes Kepler Universität Linz, Linz (2009) Available at http://www.risc.jku.at/publications/download/risc_3814/demo.nb.pdf
Kauers M., Koutschan C., Zeilberger D.: Proof of Ira Gessel’s lattice path conjecture. Proc. Natl. Acad. Sci. USA 106(28), 11502–11505 (2009)
Kauers M., Zeilberger D.: The quasi-holonomic ansatz and restricted lattice walks. J. Difference Equ. Appl. 14(10-11), 1119–1126 (2008)
Koutschan, C.: HolonomicFunctions (User’s Guide). Technical report no. 10-01 in the RISC Report Series. Johannes Kepler University, Linz (2010) Available at http://www.risc.jku.at/publications/download/risc_3934/hf.pdf
Kurkova I., Raschel K.: Explicit expression for the generating function counting Gessel’s walks. Adv. Appl. Math. 47(3), 414–433 (2008)
Lipshitz L.: D-finite power series. J. Algebra 122(2), 353–373 (1989)
Lipshitz L.: The diagonal of a D-finite power series is D-finite. J. Algebra 113(2), 373–378 (1988)
Mallinger, C.: Algorithmic manipulations and transformations of univariate holonomic functions and sequences. PhD thesis, J. Kepler University, Linz (1996)
Melczer S., Mishna M.: Singularity analysis via the iterated kernel method. Combin. Probab. Comput. 23(5), 861–888 (2014)
Mishna M., Rechnitzer A.: Two non-holonomic lattice walks in the quarter plane. Theoret. Comput. Sci. 410(38-40), 3616–3630 (2009)
Ohtsuki M.: On the number of apparent singularities of a linear differential equation. Tokyo J. Math. 5(1), 23–29 (1982)
Poole E.G.C.: Introduction to the Theory of Linear Differential Equations. Oxford Univ. Press, London (1936)
van der Put, M., Singer, M.F.: Galois Theory of Linear Differential Equations. Grundlehren der Mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences). Vol. 328. Springer-Verlag, Berlin (2003)
Salvy B., Zimmermann P.: Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Trans. Math. Software 20(2), 163–177 (1994)
Schrijver, A.: Theory of Linear and Integer Programming. JohnWiley & Sons Ltd., Chichester (1986)
Singer, M.F.: Algebraic solutions of nth order linear differential equations. In: Ribenboim, P. (ed.) Proceedings of the Queen’s Number Theory Conference, 1979 (Kingston, Ont., 1979), Queen’s Papers in Pure and Appl. Math., Vol. 54, pp. 379–420. Queen’s Univ., Kingston, Ont. (1980)
Singer, M. F.: Private communication. (2014)
Stanley, R.P.: Enumerative Combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics. Vol. 62. Cambridge University Press, Cambridge (1999)
Stein, W.A., et al.: Sage Mathematics Software. http://www.sagemath.org (2013)
Takayama, N.: An algorithm of constructing the integral of a module–an infinite dimensional analog of Gröbner basis. In: Watanabe, S., Nagata, M. (eds.) ISSAC ’90 Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 206–211. ACM New York, NY (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
A.B. was supported by the Microsoft Research—Inria Joint Centre.
M.K. was supported by FWF Grants Y464N18 and F5004.
S.M. was supported by Inria, the Embassy of France in Canada, and an NSERC MSFSS.
Rights and permissions
About this article
Cite this article
Bostan, A., Bousquet-Mélou, M., Kauers, M. et al. On 3-Dimensional Lattice Walks Confined to the Positive Octant. Ann. Comb. 20, 661–704 (2016). https://doi.org/10.1007/s00026-016-0328-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-016-0328-7