Fourier Levels and Almost Sure Bounds on Higher-Order Derivatives in First-Passage Percolation

Ivan Matić, Radoš Radoičić, Dan Stefanica · 2025

Read Fourier Levels and Almost Sure Bounds on Higher-Order Derivatives in First-Passage Percolation by Ivan Matić, Radoš Radoičić, Dan Stefanica (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08938.txt.

Introduction

Ivan Matić, Radoš Radoičić, and Dan Stefanica study how tiny local nudges accumulate into the randomness of a famous growth model, in this 2025 paper. First-passage percolation imagines a landscape of random travel times and asks for the fastest route across it. The route's total time fluctuates, and its variance splits, by Fourier analysis, into contributions from changes of each order in the environment.

The authors examine the derivatives that measure how the fastest time responds to perturbations of order two, three, and four. They prove these derivatives are almost surely trapped between two exact bounds built from binomial coefficients, symmetric around zero. Explicit landscapes show the extreme values really occur, so the bounds cannot be improved. For higher orders they conjecture the same pattern. Such control over sensitivity is a step toward understanding why the fluctuations take the shape they do.

Catalog record

CREATORIvan Matić, Radoš Radoičić, Dan Stefanica
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08938

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fourier Levels and Almost Sure Bounds on Higher-Order Derivatives in First-Passage Percolation Ivan Matić, Radoš Radoičić, Dan Stefanica Abstract . The variance of first-passage percolation admits a decomposition into Fourier levels indexed by the order of environment derivatives. These Fourier levels capture how local perturbations of different orders contribute to global fluctuations. In this paper, we investigate higher-order environment derivatives and their Fourier-level structure. We prove that derivatives of orders k ∈ { 2 , 3 , 4 } k\in\{2,3,4\} are almost surely bounded below by − ( k − 2 ⌈ k − 2 2 ⌉ ) -\binom{k-2}{\lceil\frac{k-2}{2}\rceil} and above by ( k − 2 ⌈ k − 2 2 ⌉ ) \binom{k-2}{\lceil\frac{k-2}{2}\rceil} . We conjecture that these are the correct bounds for all k k , and we construct explicit environments showing that these extreme values can indeed be attained. 1. Introduction 1.1. Model We use the same model and definitions as in [ 24 ] . We refer the reader to that paper for a more comprehensive historical discussion and overview of the literature. For completeness, we briefly recall the model and state the results needed for our proofs. Let a<b be two fixed positive real numbers, and let p\in(0,1) be fixed. We consider the finite subgraph of the integer lattice \mathbb{Z}^{d} (with d\geq 2 ) induced by the box [-2n,2n]^{d} . Two vertices (x_{1},\dots,x_{d}) and (y_{1},\dots,y_{d}) are connected by an edge if and only if they are nearest neighbors, that is, |x_{1}-y_{1}|+\cdots+|x_{d}-y_{d}|=1. Each edge e is independently assigned a random passage time, equal to a with probability p and to b with probability 1-p . Let W_{n} denote the set of all edges in this graph, and define the sample space \Omega_{n}=\{a,b\}^{W_{n}} , whose elements \omega\in\Omega_{n} represent configurations of passage times. Given a configuration \omega and a path \gamma (a sequence of adjacent edges), the passage time T(\gamma,\omega) is defined as the sum of the passage times of the edges in \gamma . For vertices u,v , we write f(u,v,\omega) for the minimal passage time among all paths connecting u to v in the environment \omega . When the destination vertex is fixed, we write f_{n}(\omega) , or simply f_{n} , for f(0,nv,\omega) . A path \gamma is called a geodesic if the minimum f_{n}(\omega) is attained at \gamma , that is, if f_{n}(\omega)=T(\gamma,\omega) . 1.2. The torus model For some of our results, we work with a simplified and more symmetric model introduced in [ 11 ] , in which first-passage percolation is considered on the discrete torus \mathbb{Z}_{n}^{d} . We use the superscript \tau to indicate this setting, writing f_{n}^{\tau}(\omega) , f_{n}^{\tau} , or simply f^{\tau} when the dependence on n is clear. The d -dimensional discrete torus is the graph with vertex set \mathbb{Z}_{n}^{d} , in which two vertices u and v are connected by an edge if and only if they differ by \pm 1 modulo n in exactly one coordinate. Let \Gamma denote the collection of all nearest-neighbor paths on \mathbb{Z}_{n}^{d} that wrap once around the torus in the x_{1} -direction. More precisely, \gamma=(v_{0},\dots,v_{m})\in\Gamma if v_{0} and v_{m} have identical coordinates except possibly in the first coordinate, with (v_{0})_{1}=0 and (v_{m})_{1}=n-1 . We define f_{n}^{\tau} to be the minimal passage time among all such paths, \displaystyle f_{n}^{\tau}(\omega)=\min\left\{T(\gamma,\omega):\gamma\in\Gamma\right\}. 1.3. Environment derivatives If we denote by W_{n} the set of all edges, then the sample space is \Omega_{n}=\{a,b\}^{W_{n}} . We will often omit the subscript n , when there is no danger of confusion. For each edge j and each \omega\in\Omega , we define \sigma_{j}^{a}(\omega) as the element of \Omega whose j -th coordinate is changed from \omega_{j} to a , regardless of what the original value \omega_{j} was. The operation \sigma_{j}^{b} is defined in analogous way. Formally, for \delta\in\{a,b\} , we define \sigma_{j}^{\delta}:\Omega\to\Omega with \displaystyle\left[\sigma_{j}^{\delta}(\omega)\right]_{k} \displaystyle= \displaystyle\left\{\begin{array}[]{ll}\omega_{k},&k\neq j,\\ \delta,&k=j.\end{array}\right. If \varphi:\Omega\to\mathbb{R} is any random variable, then the first order environment derivative \partial_{j}\varphi is the random variable defined as \displaystyle\partial_{j}\varphi \displaystyle= \displaystyle\varphi\circ\sigma_{j}^{b}-\varphi\circ\sigma_{j}^{a}. For two distinct vertices k and l , we will give the name second order environment derivative to the quantity \partial_{k}\partial_{l}\varphi . In general, if S is a non-empty subset of W , the operator \partial_{S}\varphi is defined recursively as \displaystyle\partial_{S}\varphi \displaystyle= \displaystyle\partial_{S\setminus\{j\}}\left(\partial_{j}\varphi\right), (2) where j is an arbitrary element of S . The definition ( 2 ) is independent on the choice of j , since a simple induction can be used to prove that for S=\{s_{1},\dots,s_{m}\} , the following holds \displaystyle\partial_{S}\varphi \displaystyle= \displaystyle\sum_{\theta_{1}\in\{a,b\}}\cdots\sum_{\theta_{m}\in\{a,b\}}(-1)^{\mathbf{1}_{a}(\theta_{1})+\cdots+\mathbf{1}_{a}(\theta_{m})}\varphi\circ\sigma_{s_{1}}^{\theta_{1}}\circ\cdots\circ\sigma_{s_{m}}^{\theta_{m}}. (3) The function \mathbf{1}_{a}:\{a,b\}\to\{0,1\} in ( 3 ) assigns the value 1 to a and 0 to b . 1.4. Variance decomposition and Fourier levels A thorough understanding of environment derivatives would lead to a complete understanding of the variance. As shown in [ 24 ] , the variance admits the decomposition \displaystyle\mathrm{var}(f) \displaystyle= \displaystyle\sum_{M\subseteq W,\,M\neq\emptyset}\left(p(1-p)\right)^{|M|}\left(\mathbb{E}\left[\partial_{M}f\right]\right)^{2}, (4) which highlights the central role of the L^{2} norms of the derivatives \partial_{M}f in determining fluctuation behavior. Despite their importance, general bounds for these quantities are not yet available. We rewrite ( 4 ) as \displaystyle\mathrm{var}(f)=\sum_{k=1}^{\infty}(p(1-p))^{k}\,\Sigma_{k}(f), (5) where \Sigma_{k}(f) is the level- k Fourier sum of f , defined by \displaystyle\Sigma_{k}(f)=\sum_{\begin{subarray}{c}M\subseteq W\\ |M|=k\end{subarray}}\left(\mathbb{E}\big[\partial_{M}f\big]\right)^{2}. In this paper, we prove the following theorem, which provides bounds on the first and second Fourier levels in the torus model. Theorem 1.1 . If a is an integer multiple of b-a , then there exists a constant C , depending only on a , b , p , and d , such that the level- 1 and level- 2 Fourier sums of f^{\tau} satisfy \displaystyle\Sigma_{1}(f^{\tau}) \displaystyle\leq \displaystyle Cn^{2-d}, (6) \displaystyle\Sigma_{2}(f^{\tau}) \displaystyle\leq \displaystyle Cn^{3-d}. (7) The variance decomposition ( 4 ) is essentially Parseval’s identity for the Walsh–Fourier expansion of f ; the Fourier coefficients can be expressed in terms of environment derivatives via a discrete integration by parts, as noted in [ 44 ] and made explicit in [ 24 ] . The companion paper [ 24 ] further establishes a generalization of Talagrand’s and Tanguy’s inequalities [ 45 , 46 ] . 1.5. What the Fourier-level bounds suggest Theorem 1.1 casts the variance conjecture in a new light, not by bringing it closer to resolution, but by making it more mysterious. In dimension d=3 , the first two Fourier levels contribute at most O(1) to the variance. If the widely conjectured bound \mathrm{var}(f)=O(n^{2\chi}) with \chi>0 holds in dimension 3 , then the divergence cannot come from the first two levels. It must come entirely from higher Fourier levels. This would be a striking phenomenon: the contributions of individual edges and pairs of edges to the variance are negligible, yet the cumulative effect of higher-order interactions produces polynomial growth. On the other hand, if higher Fourier levels are also well-controlled, as we conjecture, particularly in dimensions d\geq 3 where the L^{2} norms \|\partial_{M}f\|_{2} may decay exponentially in k , then the variance itself would be O(1) , implying \chi=0 in dimension 3 . Either conclusion would be remarkable, and both remain out of reach. 1.6. Almost sure bounds on environment derivatives The sequence (\mathcal{U}_{1} , \mathcal{U}_{2} , \dots) represents the optimal upper bounds for environment derivatives. The number \mathcal{U}_{k} is defined as the best upper bound on the k -th order environment derivative, i.e.

Read the complete text