Lattice walks in the quarter plane

Abstract

Das Hauptthema dieser Masterarbeit sind zufällige Gitterpfade mit kleinen Schritten in der Viertelebene, insbesondere die Frage, ob die entsprechenden Erzeugungsfunktionen differentiell endlich sind (holonom). Solche Gitterpfade haben nach einem Artikel von M. Bousquet-Mélou und M. Mishna im Jahr 2010 an Interesse gewonnen. Bereits zuvor war bekannt, dass man mit solchen Gitterpfaden eine Gruppe verbinden kann, die entweder endlich oder unendlich sein kann. In der vorgenannten Veröffentlichung wurde vermutet, dass die Endlichkeit der Gruppe der D-Finitheit der Erzeugungsfunktion entspricht. Nach einigen Fortschritten verschiedener Autoren wurde diese Vermutung inzwischen bewiesen. Diese Arbeit soll einen Überblick über das Problem sowie die Ansätze und Methoden zur Lösung des Problems geben.Etwa in der ersten Hälfte wird eine Einführung in holonome Funktionen sowie in zufällige Gitterpfade im Allgemeinen gegeben. Es wird eine Funktionsgleichung abgeleitet, die die Erzeugungsfunktion erfüllen muss, sowie die Kernelmethode, die direkt nur für Gitterpfade auf der Halbebene funktioniert, und die Gruppe eines Gitterpfads. Unter Verwendung der Gruppe des Gitterpfads kann die Holonomie von Gitterpfaden mit endlichen Gruppen durch meist elementare algebraische Methoden unter Verwendung von Umlaufbahnsummen und Halbumlaufbahnsummen gezeigt werden.Die zweite Hälfte wird insbesondere die Gitterpfade mit unendlicher Gruppe behandeln. Dies erfordert mehr technische Voraussetzungen, da ein Hauptteil darin besteht, dem Kernel eine Riemann-Oberfläche oder eine elliptische Kurve zuzuordnen, wo wir dann die bereits entwickelte umfangreiche Theorie nutzen können. Es ist besonders bemerkenswert, dass man entweder direkt an der Riemann-Oberfläche arbeiten, meromorphe Fortsetzungen untersuchen und dort die Pole betrachten oder stattdessen algebraischer an der elliptischen Kurve arbeiten kann, indem man die Galois-Theorie der Differenzgleichung verwendet und erneut die Anordnung der Pole in der richtigen Reihenfolge betrachtet Nicht-Holonomie oder sogar Hypertranszendenz zu beweisen.

The main topic of this master thesis are random walks with small steps in the quarter plane, in particular the question of whether or not the corresponding generating functions are differentially finite (holonomic). Such walks have risen in interest following a paper by M. Bousquet-Mélou and M. Mishna in 2010. Already before that, it had been known that one can associate with such walks a group, which may be either finite or infinite. In the aforementioned paper, it was conjectured that finiteness of the group is equivalent to D-finiteness of the generating function. After some progress by various authors, this conjecture has since been proven. This thesis aims to give an overview of the problem, and the approaches and methods used to solve it. Roughly the first half will give an introduction to holonomic functions, as well as to random walks in general. A functional equation the generating function must satisfy is derived, as well as the kernel method, which works directly only for walks on the half plane, and the group of a walk. Using the group of the walk, holonomy of walks with finite groups can be shown by mostly elementary algebraic methods, using orbit sums and half orbit sums. The second half will in particular treat the walks with infinite group. This turns out to require more technical prerequisites, as a main part consists of associating with the kernel a Riemann surface or an elliptic curve, where we can then make use of the vast theory already developed. It is particularly remarkable that one can work either on the Riemann surface directly, examine meromorphic continuations and looking at poles there, or work more algebraically on the elliptic curve instead, using Galois theory of difference equation and again look at the placement of poles in order to prove non-holonomy or even hypertranscendancy.