Lattice walks at the Interface of Algebra, Analysis and Combinatorics (17w5090)

Arriving in Banff, Alberta Sunday, September 17 and departing Friday September 22, 2017


(Mathematics, Simon Fraser University)

Singer Michael (North Carolina State University)

(University of Waterloo & ENS Lyon)

Mireille Bousquet-Mélou (Université de Bordeaux/ Centre national de la recherche scientifique)


The primary goal of the workshop is to bring together researchers from different domains with a variety of expertise to address both specific problems of lattice path enumeration, and general ideas of characterizing, and manipulating D-finite functions. The focus on lattice path enumeration provides a common language, and focus for the problems. Below are four topics and some specific problems that could guide the problem solving sessions. The meeting is timely, as several relevant breakthroughs (say, in enumeration, probability theory, differential Galois theory and computer algebra) have occurred in the past three years, as noted above, and the workshop would facilitate transmission of these results.

In 1990 Christol conjectured that, under conditions that many combinatorial generating functions satisfy, a formal power series that is also D-finite could be expressed as the diagonal of a multivariate rational function. This is an analogue to a result of Furstenberg for algebraic functions, which can always be expressed as a diagonal of a bivariate rational function. This conjecture has been approached via number theoretic methods in finite characteristic; by computer algebra strategies analysing integral representations, and by examination of asymptotics results. There is not a consensus on the truth of the conjecture. The result would have a strong impact on how D-finite functions are represented both combinatorially and as data structures. Recent combinatorial arguments of Pak and Garrabrant (2015) have focused on asymptotic arguments, which will be one of the central focuses of this workshop, and hence progress on the conjecture seems likely, in particular in combination with some of the p-adic results of Bell and Adamczewski.

Ideally, we will refine the Galois theories to consider the differential behaviour of solutions of functional equations on elliptic curves. Such functional equations naturally arise in the work of Fayolle, Kurkova, Raschel and others in their analytic approach to showing that generating functions associated with certain lattice walks are not algebraic nor D-finite. Our goal is to develop algebraic tools to redo these results as well as to show generating functions of other walks satisfy no polynomial differential equations and classify the type of differential equations if they do.

The group associated to a lattice path model, as described above, appears to play a very central role in the nature of the generating function. There appears to be a natural dichtomy between the lattice models with finite group (which all have D-finite generating functions) and those with an infinite group (which appear to not be D-finite). Can this dichotomy be proved, and explained? There are traces of this in the asymptotic enumeration formulas. Furthermore, there are some additional criteria which correlate with algebraicity of generating functions. The classification of 2-D models with finite groups has recently been completed by Kauers and Yatchak (2015). They revealed models where this group is of order 10 which have not yet been studied by other techniques. The problem is to find an explicit algebraic expression for models with groups of order 10. This would help elucidate the role of the group in the generating function, but would require a very careful, and technical analysis, much as in the case of the Gessel walks.

The current models that have been studied raise obvious questions about higher dimensional walks. The systematic analysis that made the two dimensional models so appealing is hampered by the explosion in the number of models. The problem becomes how to determine which models are interesting. Recent work of Bostan, Bousquet-Mélou, Kauers and Melczer has addressed the challenges of a systematic approach towards walks 3 dimensions.