A limit law for the cover time of the two-dimensional discrete torus
Yechi Zhou
math.PR
Oct 1, 2026 · v1
TL;DR
The main cover-time limit theorem (Theorem VIII.7) is formalized in Lean 4, with code released on GitHub and partly AI-generated via Codex.
Abstract
We determine the limiting distribution of the cover time of simple random walk on the two-dimensional discrete torus. For the continuous-time walk with total jump rate one on $(\mathbb Z/N\mathbb Z)^2$, let $T_N$ denote its cover time. We prove that $\frac{T_N}{(2/π)N^2\log N}-2\log N+\log\log N \Longrightarrow G+\log(κZ)$, where $G$ is a standard Gumbel random variable, $Z$ is the total mass of the critical Gaussian multiplicative chaos associated with the zero-average Gaussian free field on the unit torus, $G$ and $Z$ are independent, and $κ>0$ is deterministic. This answers the limit-law question suggested by Aldous and recorded by Dembo, Peres, Rosen and Zeitouni. The proof identifies the random fluctuations in the number of small, well-separated unvisited components at a deterministic time before coverage, and then estimates the time needed to visit the remaining components.
Problem
The limiting distribution of the cover time of simple random walk on the two-dimensional discrete torus was open. The question was suggested by Aldous and recorded by Dembo, Peres, Rosen and Zeitouni, and Bramson and Zeitouni conjectured tightness and nondegeneracy of the fluctuations.
Approach
The proof identifies the random fluctuations in the number of small, well-separated unvisited components at a deterministic time before coverage. It then estimates the time needed to visit the remaining components. Critical Gaussian multiplicative chaos of the zero-average Gaussian free field on the unit torus describes the random shift. The main theorem is formalized in Lean 4, with AI tools assisting in code generation.
Results
The rescaled cover time (T_N - a_N)/b_N, with b_N = (2/π)N² log N, converges in distribution to G + log(κZ). Here G is an independent standard Gumbel variable, Z is the total GMC mass, and κ > 0 is deterministic. This also resolves the Bramson–Zeitouni conjecture.
