Combinatorial Theory

The enumeration of walks confined to the first quadrant has attracted a lot of attention over the past fifteen years. The generating functions associated to small steps models satisfy a functional equation in two catalytic variables. For such models, Bousquet-Mélou and Mishna defined a group called the group of the walk which turned out to be central in the classification of small steps models. In particular, its action on the catalytic variables yields a set of change of variables compatible with the structure of the functional equation. This particular set called the orbit has been generalized to models with arbitrarily large steps by Bostan, Bousquet-Mélou and Melczer. However, the orbit had till now no underlying group.

In this article, we endow the orbit with the action of a Galois group, which extends the group of the walk to models with large steps. Within this Galoisian framework, we generalize the notions of invariants and decoupling. This enables us to develop a general strategy to prove the algebraicity of models with small backward steps. Our constructions lead to the first proofs of algebraicity of weighted models with large steps, proving in particular a conjecture of Bostan, Bousquet-Mélou and Melczer, and allowing us to find new algebraic models with large steps.

Mathematics Subject Classifications: 05A15, 11S20, 34K06, 39A06

Keywords: Galois theory, Enumeration, Quadrant walks, Catalytic variable equations