Hypergeometric Expressions for Generating Functions of Walks with Small\n Steps in the Quarter Plane

Abstract

We study nearest-neighbors walks on the two-dimensional square lattice, that\nis, models of walks on $\\mathbb{Z}^2$ defined by a fixed step set that is a\nsubset of the non-zero vectors with coordinates 0, 1 or $-1$. We concern\nourselves with the enumeration of such walks starting at the origin and\nconstrained to remain in the quarter plane $\\mathbb{N}^2$, counted by their\nlength and by the position of their ending point. Bousquet-M\\'elou and Mishna\n[Contemp. Math., pp. 1--39, Amer. Math. Soc., 2010] identified 19 models of\nwalks that possess a D-finite generating function; linear differential\nequations have then been guessed in these cases by Bostan and Kauers [FPSAC\n2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201--215, 2009]. We give\nhere the first proof that these equations are indeed satisfied by the\ncorresponding generating functions. As a first corollary, we prove that all\nthese 19 generating functions can be expressed in terms of Gauss'\nhypergeometric functions that are intimately related to elliptic integrals. As\na second corollary, we show that all the 19 generating functions are\ntranscendental, and that among their $19 \\times 4$ combinatorially meaningful\nspecializations only four are algebraic functions.\n