Nondifferentiability of the time constants of first-passage percolation (Q1394538)

This paper studies the time constant in the first-passage percolation (FPP) problem on \(\mathbb{Z}^2\), introduced in 1965 by Hammersley and Welsh, and answer negatively to an open conjecture of this field. The model studied here on \(\mathbb{Z}^2\) is this of the general FPP problem but the main result concerns the Bernoulli case. On the lattice \(\mathbb{Z}^2\), one considers a random field \(x=(x(e))_{e \in\mathbb{Z}^2}\) of i.i.d. random variables, with a marginal distribution \(F\) of finite mean. When \(e=(u,v)\), this random variable \(x(e)\) can be viewed as the amount of time needed to go from \(u\) to \(v\). In the simplest Bernoulli case, this amount is either \(0\) or \(1\) with probability \(p\) and \(1-p\). To study the stream along the lattice, one also considers paths along edges \(\gamma = \{v_0,e_1,v_1,\dots,e_n,v_n\}\) and defines the passage time of \(\gamma\) to be \(\tau(\gamma)=\sum_{e \in \gamma} x(e)\). Hammersley and Welsh had first studied the first passage time (FPT) \(a_{0,n}\) from the origin and the point \(u(n,0)\) of the horizontal axis, and proved by subbadditivity that there exists a finite constant \(\mu(F)\) such that the ratio \(a_{0,n}/n\) converges (a.s. and in \(L^1\)) to \(F\) when \(n\) goes to infinity. This so-called time constant \(\mu(F)\) has been studied intensively and is a central object of this paper. Depending on the configuration, different paths can lead to the FPT \(a_{0,n}\) (these paths are then called routes. Another object of interest, because it provides information on the FPT, is the length \(N_n\) of the shortest route. This length behaves differently depending on the percolation regime of the model. In the supercritical case, Zhang and Zhang (1984) proved that \(N_n/n\) converges a.s. and in \(L^1\) to another finite time constant \(\lambda(F)\), but this problem is still open in other regimes. Hammersley and Welsh had already studied this question and transformed it into a problem of smoothness of the first time constant \(\mu(F \otimes t)\) of the shifted distribution \(F \otimes t\) as a function of the shift parameter \(t\) (For the Bernoulli case, the shifted Bernoulli r.v.'s \(x'(e)=x(e)+t\) take values \(t\) and \(t+1\) with probability \(p\) and \(1-p\)). This approach has later on been carried on by Smythe and Wierman (1978) and Kesten (1980) who obtained a new criterion for this convergence in the subcritical case : the ratio \(N_n/n\) must converge with probability one if the time constant \(\mu(F \otimes t)\) is differentiable at \(t=0\). The main result of this paper closes the door of this approach : Theorem 1 proves that this differentiability condition does not hold for the basic Bernoulli percolation problem in the subcritical case (\(F(0)=p<1/2\)). According to the authors, it is likely that the convergence still holds for subcritical percolation but the proof must be more subtle : a conjecture of Kesten about the divergence in the critical case suggests that the analysis of the sub- and super critical case may be different. The proof of the main theorem (Theorem 1) is achieved after a careful preparation relying on combinatorial, topological and geometrical techniques. The FPP \(a_{0,n}\) is first related to the length \(N_n\) of the shortest route and graph theory is used to restrict the attention on finite volume analysis of the dual lattice. The non-differentiability of the time constant is proved after some probabilistic comparaisons between the longest and the shortest route at \(t=0\). The authors also indicate in their conclusion alternative routes to prove the convergence of \(N_n /n \) in the subcritical case.