Gaps between roots in ballistic deposition on a strip: linear variance, Gaussian limits and a Poisson regime
Mateo Matijasevick
math.PR
Oct 15, 2026 · v1
TL;DR
Several deterministic combinatorial lemmas (root criterion, gap locality, valley patterns, profile comparison) were formalized and machine-checked in Lean 4.
Abstract
Mansour, Rastegar and Roitershtein studied the roots of ballistic deposition on a cyclic strip of $K$ sites, namely the sites that receive a particle at height one, and the number $D_{i,K}$ of pairs of consecutive roots at distance $i+1$. They computed the first two moments of $D_{i,K}$ for $i\le7$. They conjectured that for every $i$ the mean and the variance are exactly linear in $K$, that $D_{i,K}$ satisfies a central limit theorem, and that the standardized vector $(D_{i,K})_{i\ge1}$ converges to a Gaussian process. We prove these conjectures. The key observation is that the roots are exactly the valleys of a uniformly random circular arrangement, so that $D_{i,K}$ counts occurrences of a family of consecutive patterns. We determine sizes from which the moments are exactly linear, which cannot be lowered in any case we checked, and give closed forms for the mean and variance constants and for the limiting covariance. We also prove a Wasserstein bound of order $(\mathbb{E} D_{i,K})^{-1/2}$ that is uniform in $i$, and a local limit theorem. Finally we describe the limit completely when $i$ grows with $K$: it is degenerate, Poisson or Gaussian according as $\mathbb{E} D_{i,K}$ tends to zero, to a positive constant, or to infinity.
Problem
Mansour, Rastegar and Roitershtein conjectured that the number D_{i,K} of consecutive root pairs at distance i+1 in ballistic deposition on a cyclic strip has mean and variance exactly linear in K. They also conjectured a central limit theorem for D_{i,K} and Gaussian-process convergence of the standardized vector.
Approach
The roots are identified exactly with the valleys of a uniformly random circular arrangement, via a root criterion and Poissonization. D_{i,K} then becomes a count of locally dependent consecutive patterns. Exact moments follow from locality, and closed forms come from an excursion kernel for unimodal sequences. Stein's method and Chen–Stein bounds give normal and Poisson approximations. Several deterministic lemmas were machine-checked in Lean 4.
Results
All three conjectures are proved, with variance linear in K replacing the standard deviation in the original statement. The paper gives sharp thresholds for exact linearity, closed-form constants, a uniform Wasserstein bound 133/sqrt(a_i K), and a local limit theorem. For growing i, the limit is degenerate, Poisson or Gaussian according as the mean tends to 0, a constant, or infinity.