Higher-Order Derivatives of First-Passage Percolation with Respect to the Environment
Ivan Matić, Radoš Radoičić, Dan Stefanica · 2025
Read Higher-Order Derivatives of First-Passage Percolation with Respect to the Environment 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-08935.txt.
Introduction
Ivan Matić, Radoš Radoičić, and Dan Stefanica introduce derivative-like measures for first-passage percolation, in a paper published in two thousand twenty-five. In this model, each edge of a grid carries a random travel time, and the passage time between distant points is the fastest route's total.
Their edge weights take just two values. The derivatives record how the passage time responds to flipping individual edges, a sensitivity analysis of the random medium. The authors show the variance of the passage time can be written exactly in terms of these derivatives. They then map the derivatives' structure and prove basic properties and bounds. Bounds on the low Fourier levels raise a striking possibility. In three or more dimensions, the variance might grow slower than any positive power of distance. That would overturn the common belief in a positive fluctuation exponent, a long-standing expectation in the field.
Catalog record
| CREATOR | Ivan Matić, Radoš Radoičić, Dan Stefanica |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08935
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher-Order Derivatives of First-Passage Percolation with Respect to the Environment Ivan Matić, Radoš Radoičić, Dan Stefanica Abstract . We introduce and study derivatives in first-passage percolation with edge weights given by i.i.d. random variables supported on { a , b } \{a,b\} . We show that the variance of the passage time can be expressed in terms of these derivatives. We further analyze their structure and establish several fundamental properties and bounds. Our bounds for the lower Fourier levels on the torus model raise the prospect that, in dimensions 3 and higher, the variance may grow slower than any positive power of n n . Such growth would contradict the commonly held belief that the fluctuation exponent is positive. 1. Introduction 1.1. Definition of the model The first-passage percolation model was introduced by Hammersley and Welsh in [ 25 ] . Let p\in(0,1) and let a and b be two positive real numbers that satisfy a<b . Consider the graph whose vertices are elements of \mathbb{Z}^{d}\cap[-2n,2n]^{d} (with d\geq 2 ), where two vertices (x_{1},\dots,x_{d}) and (y_{1},\dots,y_{d}) are connected by an edge if |x_{1}-y_{1}|+\cdots+|x_{d}-y_{d}|=1 . Let W_{n} denote the set of edges of this graph. The sample space is defined as \Omega_{n}=\{a,b\}^{W_{n}} . Each edge e of the graph is independently assigned a passage time of either a or b , with probabilities \mathbb{P}(a)=p and \mathbb{P}(b)=1-p . For a fixed environment \omega\in\Omega_{n} and a path \gamma , the passage time T(\gamma,\omega) is defined as the sum of the values assigned to the edges of \gamma . For two fixed vertices u and v , the passage time f(u,v,\omega) is the random variable defined as the minimum of T(\gamma,\omega) over all paths \gamma connecting u to v . When v is fixed, we will also use the notation f_{n}(\omega) , f_{n} , or simply f , in place of f(0,nv,\omega) . For some of our results, we will only work on a simplified model from [ 13 ] that has more symmetry and fewer technical challenges: the percolation is considered on the torus \mathbb{Z}_{n}^{d} . We will use superscript \tau and write f_{n}^{\tau}(\omega) , f_{n}^{\tau} , or f^{\tau} to emphasize when we are working on this simplified torus model. Formally, a d -dimensional torus is a graph whose vertices are elements of \mathbb{Z}_{n}^{d} and two vertices u and v are connected by an edge if and only if there is exactly one coordinate k\in\{1,2,\dots,d\} such that u_{k}-v_{k}\equiv\pm 1 (mod n ) and u_{j}=v_{j} for all j\neq k . The set of admissible paths \Gamma consists of all paths that wrap around the torus in the direction x_{1} . Hence, the path (s,v_{1},\dots,v_{m},e) belongs to the set \Gamma if it is a path in the graph and if the starting and ending vertices s and e have all the coordinates the same except for the first coordinate. Their first coordinates are s_{1}=0 and e_{1}=n-1 . The random variable f^{\tau}_{n} is defined as the minimum of the passage times among all paths \gamma that consist of adjacent edges and that wrap around the torus exactly once in the direction x_{1} . The function f^{\tau}_{n} is defined as f^{\tau}_{n}(\omega)=\min\left\{T(\gamma,\omega):\gamma\in\Gamma\right\}. A path \gamma is called geodesic if the minimum f_{n}(\omega) (or f^{\tau}_{n} , depending on which problem we are studying) is attained at \gamma , i.e. if f_{n}(\omega)=T(\gamma,\omega) . 1.2. Definition of 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 outcome from \Omega whose passage time over the edge j is changed from \omega_{j} to a , regardless of what the original value \omega_{j} was. The operation \sigma_{j}^{b} is defined in an analogous way. Formally, for \delta\in\{a,b\} , we define \sigma_{j}^{\delta}:\Omega\to\Omega with \left[\sigma_{j}^{\delta}(\omega)\right]_{k}=\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 \partial_{j}\varphi=\varphi\circ\sigma_{j}^{b}-\varphi\circ\sigma_{j}^{a}. For two distinct edges i and j , we will give the name second order environment derivative to the quantity \partial_{i}\partial_{j}\varphi . In general, if S is a non-empty subset of W , the operator \partial_{S}\varphi is defined recursively as \partial_{S}\varphi=\partial_{S\setminus\{j\}}\left(\partial_{j}\varphi\right), where j is an arbitrary element of S . The definition 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 \partial_{S}\varphi=\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}}. The function \mathbf{1}_{a}:\{a,b\}\to\{0,1\} assigns the value 1 to a and 0 to b . 1.3. Variance decomposition and Fourier levels The variances of f_{n} and f_{n}^{\tau} can be written in terms of environment derivatives. Theorem 1 . Let f be a random variable on \Omega_{n} . The following equality holds \displaystyle\text{var}(f) \displaystyle=\sum_{M\subseteq W,M\neq\emptyset}\left(p(1-p)\right)^{|M|}\left(\mathbb{E}\left[\partial_{M}f\right]\right)^{2}. (1) Let us define Fourier level \Sigma_{j} as \displaystyle\Sigma_{j}(f) \displaystyle=\sum_{\begin{subarray}{c}M\subseteq W,\;|M|=j\end{subarray}}\left(\mathbb{E}\big[\partial_{M}f\big]\right)^{2}. Then, for each k , we can break ( 1 ) into the lower sum L_{k} and the remainder R_{k} \displaystyle\text{var}(f) \displaystyle=L_{k}(f)+R_{k}(f),\quad\text{where} \displaystyle\quad L_{k}(f) \displaystyle=\sum_{j=1}^{k-1}(p(1-p))^{j}\Sigma_{j}(f)\;\text{ and }\;R_{k}(f)=\sum_{j=k}^{\infty}(p(1-p))^{j}\Sigma_{j}(f). 1.4. Bound on the lower sum L_{k} On the torus model, we can prove that for fixed k and fixed \zeta\in(0,1) , the lower sum L_{k}(f^{\tau}) is at most O(n^{1+\zeta-\zeta d}) . In dimensions d\geq 3 , choosing \zeta>1/(d-1) yields 1-\zeta(d-1)<0 , so the lower sums converge to 0 . We believe this also holds for general model, not only torus model. We also believe this holds for \zeta=1 . The case \zeta<1 can be handled by a general functional analysis technique that relies on Beckner-Bonami inequality. The case \zeta=1 must be handled by combinatorics. We were able to extend the bounds for \Sigma_{1} and \Sigma_{2} to \zeta=1 [ 32 ] , but a more comprehensive combinatorial analysis would be needed for higher levels. Below is the detailed formulation of the theorem that we will prove in this paper. Theorem 2 . For every n\in\mathbb{N} , every k\in\mathbb{N} , and every \zeta\in(0,1) , the following holds \displaystyle L_{k}(f^{\tau}) \displaystyle\leq C(\zeta,k,p,a,b)\cdot n^{1+\zeta-\zeta d},\quad\text{ where } (2) \displaystyle C(\zeta,k,p,a,b) \displaystyle=p(1-p)\cdot(b-a)^{2}\cdot\left(\frac{b}{ap}\right)^{1+\zeta} \displaystyle\quad\times\frac{\left(\frac{1+\zeta}{(1-\zeta)p(1-p)}\right)^{k-1}-1}{\frac{1+\zeta}{(1-\zeta)p(1-p)}-1}. (3) 1.5. Bound on the remainder R_{k} The following result holds for general random variables. Hence, it applies both to f and f^{\tau} . Theorem 3 . For every integer k\geq 1 , there exists a real constant C and an integer n_{0} such that for n\geq n_{0} , and every random variable f on \Omega_{n} its remainder R_{k}=R_{k}(f) satisfies \displaystyle R_{k}(f) \displaystyle\leq C\cdot\sum_{M\subseteq W,|M|=k,\|\partial_{M}f\|_{1}\neq 0}\frac{\left\|\partial_{M}f\right\|_{2}^{2}}{1+\left(\log\frac{\|\partial_{M}f\|_{2}}{\|\partial_{M}f\|_{1}}\right)^{k}}, (4) where \|g\|_{p} is the L^{p} -norm of the function g defined as \|g\|_{p}=\left(\int|g|^{p}\,d\mathbb{P}\right)^{1/p}=\left(\mathbb{E}[|g|^{p}]\right)^{1/p}. 1.6. Conjectures about variance in higher dimensions Theorem 2 casts the variance conjecture in a new light, not by bringing it closer to resolution, but by making it more mysterious. In dimensions d\geq 3 , the lowest Fourier levels contribute at most O(n^{1+\zeta-\zeta d}) to the variance. The value \zeta can be chosen to make the exponent of n negative. If the widely conjectured bound \mathrm{var}(f)=O(n^{2\chi}) with \chi>0 holds in dimensions greater than or equal to 3 , then the divergence cannot come from the lowest levels. It must come entirely from higher Fourier levels. This would be a striking phenomenon: the cumulative effect of higher-order interactions produces polynomial growth. On the other hand, if higher