ALgebraic COmbinatorics for Hikes On Lattices – ALCOHOL

This project aims at studying advanced algebraic and combinatorial structures associated with walks and heaps of cycles on graph. The outstanding goal here is to calculate the connective and universal constants which dictate the asymptotic growth of the number of self-avoiding walks (SAWs) and polygons (SAPs) on infinite lattices. So far this problem, open since 70 years, has only been approached with the tools of probability theory and conformal field theory. We study this question from the point of view of number theory, for which heaps of cycles constitute a very natural semi commutative extension. In this framework, the problem of determining the connective and universal constants is equivalent to the prime number theorem.

The two main research themes of the project are, first, to extend the Brun and Selberg sieves to the semi commutative setting relevant to SAPs; and second, to establish the theory for a novel type of closely related arborescent algebraic structures. The objectives of the first theme is to use number-theoretic sieve techniques to calculate exponents related to the asymptotic density of walks multiples of a SAP. This first result then appears in turn in a second sifting identity capable of bridging between different universality classes, i.e. models of random generation of SAWs and SAPs yielding different growth exponents. In technical terms, the sifting identity is capable of relating different realisations of the Schramm-Loewner Evolution (SLE) algebraically, here SLE2 and SLE8/3. For this to work, error terms generated by the first sieve counting walk multiples will have to be controlled by adapting Brun’s and Selberg’s techniques to the case of walks and hikes. During a second research phase, we will generalise these constructions to “sufficiently regular” partially ordered sets (posets). For such posets sieves permit a reduction of asymptotic enumeration problems to the study of the zeroes of well-chosen functions. A particular goal here will be to relate the connective constant to the constant dictating the growth of the number of polyominos as a function of their area.

The second theme of the project concerns a novel type of algebraic structure associated to heaps of cycles on graphs, which formalises Lawler’s loop erasing procedure. This procedure consists in removing loops from an ordinary random walk in chronological order. Remarkably, this yields the prime factors of the walk as per the extension of number-theory to heaps of cycles. Then, combinatorial arguments show that there exists a non associative, non commutative coloured arborescence of Hopf algebras which describes: i) the generation of walks from cycles, i.e. an inverse to Lawler’s procedure; ii) the combinatorial properties of continued fractions; iii) a universal continued fraction form for all generating functions for any type of hikes on any graph; and iv) the solutions of systems of coupled linear differential equations with non constant coefficients. In this last case, the resulting method is the only non perturbative approach to calculate the time- and path-ordered exponentials commonly encountered in quantum dynamics. These kinds of algebras have been largely ignored so far owing to their perceived complexity and the fact that their applications were not understood. A particular objective of the algebraic machinery here, will be to obtain the idempotents of the algebra. These can distinguish the fundamental processes generating a quantum dynamics, or can count the graph cycles from its walks, thereby providing the starting points of novel sieving techniques on graphs.

A team of 5 young researchers and one distinguished Professor of international stature accompany the coordinator on this project. The members of the team bring mutually complementary expertises in the fields of heaps of pieces, probability theory, combinatorial Hopf algebras, posets and operads.