Lattice paths are combinatorial objects with interesting generating functions. For lattice walks in N2 starting at the origin, the generating function is sometimes algebraic, sometimes only holonomic, and sometimes not even that. This is determined by the set of admissible steps (a subset of N, NE, E, SE, S, SW, W, NW) that are allowed during the walk. It turns out that NE, E, SW, W is a particularly nasty step set. In the talk, I will first present a proof of a conjecture about this step set raised by Ira Gessel, found jointly with Christoph Koutschan and Doron Zeilberger. In the second part, I will present the proof of a much stronger assertion, discovered together with Alin Bostan: the generating function for the step set NE, E, SW, W is algebraic.
Forschungs-