The shape of random travel times and the absence of infinite shortest lines

← All digests

Family 212 · Probability and statistical mechanics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Imagine a square street grid in which every street segment takes a random amount of time to traverse. The fastest route between two places need not be the route with the fewest blocks. As the scale grows, two natural geometric questions arise.

First, could there be a route stretching infinitely in both directions such that every finite piece of it is a fastest route between its endpoints? Such a path would be a random counterpart of a straight line in Euclidean geometry.

Second, if a traveler starts at the origin and can use every route at once, what is the large-scale shape of the region reachable by a given time? A classical theorem gives a deterministic convex limiting shape, but convexity alone permits both flat sides and sharp corners.

The two manuscripts in this family claim progress on both questions. One excludes all doubly infinite shortest paths for a broad class of continuous edge-weight laws. The other rules out corners and flat sides for exponential weights, and rules out corners for the larger Gamma family. The path theorem does not depend on assuming the shape regularity established in the companion.

2. Background and essential definitions

A random metric on the square lattice

The square lattice $\mathbb Z^2$ has vertices with integer coordinates. Two vertices are joined when they differ by one in exactly one coordinate. Assign each unoriented edge $e$ a random nonnegative travel time $t_e$, independently and with the same distribution.

For a finite path $P$, its passage time is the sum of its edge weights. The random distance between vertices is

$$T(x,y)=\inf_{P:x\to y}\sum_{e\in P}t_e,$$

with repeated traversals charged repeatedly. Paths are undirected: motion is allowed along an edge in either direction. This is first-passage percolation.

A geodesic is a path achieving the smallest passage time. An infinite geodesic ray has the property that every finite segment is a geodesic. A bigeodesic is a path $(v_i)_{i\in\mathbb Z}$, with distinct vertices and adjacent consecutive vertices, satisfying

$$\sum_{k=i}^{j-1}t_{\{v_k,v_{k+1}\}}=T(v_i,v_j) \quad\text{for every }i<j.$$

It must minimize between every pair of its own vertices, not merely look straight or have a limiting direction. Two infinite rays coalesce when they eventually join and thereafter follow the same route.

A distribution is nonatomic if no single value has positive probability. It need not have a density. Independent nonatomic edge weights remove ties between distinct finite routes almost surely.

The limit shape and its two kinds of regularity

For suitable edge laws, a shape theorem gives a deterministic norm $\mu$ on $\mathbb R^2$, with

$$\frac{T(0,\lfloor tv\rfloor)}{t}\longrightarrow\mu(v)$$

for each fixed vector $v$. The rounding symbol chooses nearby lattice coordinates. The unit ball

$$\mathcal B=\{v:\mu(v)\le1\}$$

describes the scaled region reachable by a large time.

A strictly convex boundary has no nontrivial straight segment. A differentiable boundary has a unique tangent or supporting line at each point, hence no corner. These are different properties: a smooth convex shape can have a flat side, and a strictly convex shape can still have a corner. A $C^1$ boundary has a continuously varying tangent.

The exponential law of rate $\lambda>0$ has density $\lambda e^{-\lambda t}$ for $t>0$. It is the shape-one member of the Gamma family, whose density is

$$p_{\kappa,\lambda}(t)=\frac{\lambda^\kappa}{\Gamma(\kappa)}t^{\kappa-1}e^{-\lambda t}, \qquad t>0.$$

Here $\kappa>0$ is the shape parameter, $\lambda>0$ the rate, and $\Gamma(\kappa)=\int_0^\infty s^{\kappa-1}e^{-s}\,ds$ is the normalizing Gamma function.

3. Development history and previous partial results

Hammersley and Welsh introduced first-passage percolation in 1965. Subadditive methods, including Kingman’s ergodic theorem, and work of Richardson and Cox–Durrett established deterministic asymptotic shapes. The difficulty then shifted from the existence of a shape to its fine geometry and the structure of infinite shortest paths.

The no-bigeodesics question is attributed to Furstenberg in Kesten’s account. Licea and Newman obtained coalescence for each direction in a deterministic set of full angular measure, together with exclusions for prescribed end directions. Related conclusions that every ray has a direction required stronger moment and curvature assumptions in Newman’s work.

Damron and Hanson developed stationary Busemann functions and excluded paths in specified supporting sectors under differentiability conditions. Other work treated the half-plane metric, selected geodesic graphs, or simultaneous absence under additional quantitative hypotheses. These results were important but did not exclude every possible bigeodesic in a general environment under M1’s assumptions.

Ahlberg and Hoffman supplied structural results on random coalescing geodesics without assuming regularity of the limiting shape. M1 uses that framework. Its stated remaining obstacle is a quantifier problem: a probability-one statement for each fixed direction or label need not hold simultaneously for a label chosen after seeing the entire random environment. Their work is a principal input to the new argument.

Shape regularity developed along a parallel track. Sufficient conditions for strict convexity were known, and distributions with an atom at their smallest weight can produce flat segments. Marchand determined such flat portions in an oriented-percolation regime, while Auffinger and Damron proved differentiability at their endpoints. Those edge laws differ substantially from the nonatomic exponential law, whose support extends down to zero.

M2 claims regularity for the basic planar exponential model itself. It also extends the differentiability conclusion to every positive Gamma shape and rate. The manuscript distinguishes these claims from existing qualitative midpoint results, which do not require shape regularity.

4. What the new manuscripts claim

M1: no bigeodesic in any direction

Let $X_1,X_2,X_3,X_4$ be independent samples from the common nonnegative edge-weight law. M1 assumes that the law is nonatomic and

$$\mathbb E\left[\min\{X_1,X_2,X_3,X_4\}^2\right]<\infty.$$

Under these assumptions, it states that almost surely no bigeodesic exists anywhere in the planar lattice.

The four-variable minimum is important. The assumption is not that an individual edge weight has finite second moment, or even finite mean. A minimum can have a much lighter tail than one sample. The statement allows bounded-support and singular continuous laws as well.

The conclusion is simultaneous: the probability-one event excludes every bigeodesic, including any whose end directions depend on the environment. M1 imposes no differentiability, strict convexity, or curvature assumption on the limit shape. It does not claim the version with no moment assumption at all.

M2: regularity of exponential and Gamma shapes

For independent exponential weights of any fixed rate $\lambda>0$, M2 claims that $\mu$ is differentiable at every nonzero vector and that $\mathcal B$ is strictly convex. In particular, for distinct boundary points $x,y$ and $0<s<1$,

$$\mu((1-s)x+sy)<1.$$

The boundary is a $C^1$ curve with a unique supporting line everywhere. This does not identify the shape with a circle or give an explicit formula for the norm.

For every fixed Gamma shape $\kappa>0$ and rate $\lambda>0$, M2 claims differentiability of $\mu$ away from zero and a $C^1$ boundary. Strict convexity is asserted for exponential weights, not for the whole Gamma family. The two parts use separate arguments.

5. Why the advance matters

Importance: 4/5. The claims would settle major geometric questions in a standard random-growth model. They describe both the impossibility of a globally minimizing infinite line and the regularity of the macroscopic growth boundary.

The no-bigeodesics theorem is particularly strong because it addresses all random directions simultaneously. Excluding one direction selected in advance would leave room for an exceptional route whose direction is chosen by the disorder itself.

The shape theorem addresses a different gap between basic existence and geometric understanding. Convexity follows from general averaging principles, but excluding every corner and flat side in the exponential model requires information about how alternative routes compete.

The two conclusions reinforce a coherent picture of planar random geometry without being interchangeable. M1’s broad distributional scope is not a consequence of M2’s results for special laws.

6. The main idea

Compare travel times toward infinity

For a geodesic ray $p=(p_0,p_1,\ldots)$, a Busemann function compares starting points while sending the destination far away:

$$B_p(x,y)=\lim_{j\to\infty}\bigl(T(x,p_j)-T(y,p_j)\bigr).$$

It records an asymptotic travel-time advantage. Its large-scale linear behavior gives the ray a directional label. The two ends of a hypothetical bigeodesic carry opposite labels.

M1 combines planar ordering and coalescence information with controlled increases of finitely many edge weights. A selected path is forced to acquire extra passage cost, while the probability law changes only mildly. The changes are spread across a growing region: their cumulative effect along a path can diverge even though their total probabilistic cost stays controlled.

A comparison along a horizontal line then limits how much extra cost many selected paths can absorb. Schematically, the manuscript obtains a finite budget

$$Mq\le lW,$$

where $M$ is the forced cost increase, $q$ the probability of a marked site, $l$ a fixed spacing, and $W$ the width of a bounded label sector. Here $q$ is local notation for a probability, unrelated to the FK parameter in family 211.

The construction keeps the marking probability positive and the spacing fixed while increasing $M$, giving the contradiction. A substantial part of the argument handles environment-dependent labels directly, rather than taking an invalid intersection of uncountably many probability-one events.

Corners and flat sides lead to different contradictions

For differentiability, suppose the norm had a corner. Two different supporting linear functionals would touch it in the same direction. Their separation penalizes sideways travel. M2 turns this into a positive excess cost for every sufficiently long path, conflicting with the asymptotic passage time in that direction.

The Gamma law permits a controlled local change of scale with an explicit likelihood estimate. Local crossing bounds and disjoint witnesses then extend the argument from prescribed strips to all relevant paths. This is why the differentiability part extends beyond exponential weights.

For strict convexity, a hypothetical flat side gives two distinct directions sharing one supporting functional. The exponential argument builds local routes following these directions and measures their excess over the supporting cost. It claims both a positive lower bound on that excess and an improvement procedure that contracts it by a fixed factor on larger scales. Iterating the improvement contradicts the lower bound.

These are geometric explanations of the two mechanisms. Neither identifies the limit shape explicitly, and the strict-convexity argument is not presented as a consequence of differentiability alone.

7. Scope, limitations, and open questions

The theorems concern independent identically distributed weights on the undirected nearest-neighbor square lattice. They do not automatically apply to directed models, dependent environments, or higher dimensions.

M1 retains its minimum-of-four moment assumption. M2 retains its specific distributional assumptions, with the stronger conclusion restricted to exponentials. Removing those restrictions would require further results.

A $C^1$, strictly convex boundary need not have a known positive curvature lower bound, and it need not be twice differentiable. No exact shape, fluctuation exponent, or convergence rate is supplied by the headline statements.

The directional consequences in M2 also retain their fixed-direction probability conventions. M1’s simultaneous exclusion of all bigeodesics is a separate statement. Further questions include finer curvature, the size of passage-time fluctuations, and comparable geometric results for more general edge laws.

8. Sources and further reading

• Hammersley and Welsh, First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory, for the model’s origin.
• Licea and Newman, Geodesics in two-dimensional first-passage percolation, for early directional results.
• Ahlberg and Hoffman, Random coalescing geodesics in first-passage percolation, for the structural framework used by M1.
• Damron and Hanson, Bigeodesics in first-passage percolation, for earlier shape-dependent exclusions.

M1 and M2 give their precise assumptions, separate arguments, and further primary references for the shape theory.

Source manuscripts

• M1. OpenAI, No bigeodesics in planar first-passage percolation (September 24, 2026).
• M2. OpenAI, Strict convexity and differentiability of the planar exponential first-passage limit shape (September 24, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.