Lattice walks at the Interface of Algebra, Analysis and Combinatorics (17w5090)
Marni Mishna (Mathematics, Simon Fraser University)
Singer Michael (North Carolina State University)
Stephen Melczer (University of Waterloo & ENS Lyon)
Mireille Bousquet-Mélou (Université de Bordeaux/ Centre national de la recherche scientifique)
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.