×

Infinite orders and non-\(D\)-finite property of 3-dimensional lattice walks. (English) Zbl 1344.05013

Summary: Recently, A. Bostan et al. [“On 3-dimensional lattice walks confined to the positive octant”, Preprint, arXiv:1409.3669] investigated lattice walks restricted to the non-negative octant \(\mathbb{N}^3\). For the 35548 non-trivial models with at most six steps, they found that many models associated to a group of order at least 200 and conjectured these groups were in fact infinite groups. In this paper, we first confirm these conjectures and then consider the non-\(D\)-finite property of the generating function for some of these models.

MSC:

05A15 Exact enumeration problems, generating functions
60G50 Sums of independent random variables; random walks

Software:

Epsilon
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] A. Bostan, M. Bousquet-M´elou, M. Kauers and S. Melczer, On 3-dimensional lattice walks confined to the positive octant, Ann. Comb. 2015.arXiv:1409.3669. the electronic journal of combinatorics 23(3) (2016), #P3.3812 · Zbl 1354.05006
[2] A. Bostan and M. Kauers, The complete generating function for Gessel walks is algebraic, Proc. Amer. Math. Soc. 138(9), 3063-3078 (2010). With an appendix by Mark van Hoeij. · Zbl 1206.05013
[3] A. Bostan, K. Raschel and B. Salvy, Non-D-finite excursions in the quarter plane, J. Combin. Theory Ser. A.121, 45-63 (2014). · Zbl 1279.05003
[4] M. Bousquet-M´elou and M. Mishna, Walks with small steps in the quarter plane, In Algorithmic probability and combinatorics, Contemp. Math. 520, 1-39 (2010). · Zbl 1209.05008
[5] B. Buchberger, Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symbolic Compt. 41(3), 475-511 (2006). · Zbl 1158.01307
[6] D. Cox, J. Little and D. O’shea, Ideals, Varieties, and Algorithms, 3rd ed. Springer, New York, 2013. · Zbl 0861.13012
[7] D. Denisov and V. Wachtel, Random walks in cones. Ann.Probab. 43(3), 992-1044 (2015). · Zbl 1332.60066
[8] I.M. Gessel and D. Zeilberger, Random walk in a Weyl chamber, Proc. Amer. Math. Soc. 115(1), 27-31 (1992). · Zbl 0792.05148
[9] I. Kurkova and K. Raschel, Explicit expression for the generating function counting Gessel’s walks, Adv. in Appl. Math. 47(3), 414-433 (2011). · Zbl 1234.05027
[10] M.A. Maher, Random walks on the positive quadant, ProQuest LLC, Ann Arbor, MI, 1978. Thesis (Ph.D.)–University of Rochester.
[11] S. Melczer and M. Mishna,Singularity analysis via the iterated kernel method, Combin. Probab. Comput. 23(5), 861-888 (2014). · Zbl 1298.05026
[12] M. Mishna, Classifying lattice walks restricted to the quarter plane, J. Combin. Theory Ser. A. 116(2), 460-477 (2009). · Zbl 1183.05004
[13] M. Mishna and A. Rechnitzer, Two non-holonomic lattice walks in the quarter plane. Theoret. Comput. Sci. 410(38-40), 3616-3630 (2009). · Zbl 1228.05038
[14] S.G. Mohanty, Lattice path counting and applications, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1979. Probability and Mathematical Statistics. · Zbl 0455.60013
[15] T.V. Narayana, Lattice path combinatorics with statistical applications, Mathematical Expositions Ser. University of Toronto Press, Toronto, Ont., 1979. · Zbl 0437.05001
[16] K. Raschel, Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc.14(3), 749-777 (2012). · Zbl 1238.05014
[17] R.P. Stanley, Differentiably finite power series, European J. Combin. 1(2), 175-188 (1980). · Zbl 0445.05012
[18] D. M. Wang, Epsilon: A Library of Software Tools for Polynomial Elimination. A. M. Cohen, X.-S. Gao, N. Takayama. Proceedings of the First International Congress of Mathematical Software - ICMS 2002, Aug 2002, P´ekin, Chine, World Scientific, pp.379-389 (2002). · Zbl 1012.68232
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.