ALCOHOL
Algebraic Combinatorics of Hikes on Lattices
ALgebraic COmbinatorics of Hikes On Lattices
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.
Left: an innocent looking self-avoiding polygon on the infinite square lattice. Right: exact fraction of all closed walks whose last erased loop is the SAP on the left as calculated by a number theoretic sieve. In other terms, about 0.000000078% of all walks from a point to itself on the infinite square lattice erase this SAP last following Lawlers' procedure. Sieves establish that irrespectively of the SAP the fraction will always by in ℚ[1/π] on the square lattice.
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.