First-passage percolation: bigeodesics and shape regularity

Source and verification

This article explains family 212 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

First-passage percolation turns independent edge costs into a random metric. Family 212 concerns two questions about its large-scale geometry: whether a minimizing path can extend forever in both directions, and whether the limiting unit ball has corners or flat sides.

🏷️ Preliminaries: passage times and the limit shape

Give each nearest-neighbor edge of ${\mathbb{Z}}^2$ a nonnegative random weight ${\tau }_e$. For vertices $x,y$, define

$$T(x,y)=\underset{\pi :x\to y}{\inf }\sum _{e\in \pi }{\tau }_e.$$

A geodesic attains this infimum; with a continuous common weight law, ties between distinct finite simple paths have probability zero. A bigeodesic is a doubly infinite path every finite segment of which minimizes passage time between its endpoints. Having arbitrarily long finite geodesics does not supply such a path through a fixed bounded region.

Under the usual nondegeneracy and integrability assumptions, the rescaled random balls approach the unit ball of a deterministic norm $\mu$. Two regularity properties should be separated. Strict convexity excludes line segments in the unit sphere. Differentiability of $\mu$ away from zero excludes multiple supporting linear functionals at a boundary point, hence corners. One property does not imply the other for a general norm.

🏷️ The two claimed results

Claims and hypotheses

For iid nonnegative nonatomic weights satisfying the second-moment assumption on the minimum of the four edges incident to a vertex, the first companion claims that almost surely there are no bigeodesics anywhere in the lattice. It imposes no differentiability or strict-convexity assumption on the limit shape. (OpenAI, 2026)

For exponential weights of any positive rate, the second companion claims both a strictly convex limit shape and differentiability of the norm away from zero. For Gamma weights of every positive shape and rate, it claims differentiability; its strict-convexity conclusion is restricted to the exponential case. (OpenAI, 2026b)

The first moment condition is deliberately weaker than a second moment for one edge. If ${\tau }_1,\dots ,{\tau }_4$ are independent copies and $Y={\min }_i{\tau }_i$, then

$$\mathbb{P}(Y>t)=\mathbb{P}({\tau }_e>t{)}^4.$$

Thus $\mathbb{E}{Y}^2={\int }_0^{\infty }2t\mathbb{P}({\tau }_e>t{)}^{4}dt$ may be finite even when the individual edge mean is infinite. Local detours, rather than a single prescribed edge, are what make this condition natural.

🏷️ Excluding a path with two infinite ends

A Busemann difference compares passage times from two starting points to a distant target. When a limit exists, it behaves like an additive potential and labels directed minimizing rays. The crucial quantifier is simultaneous exclusion: a statement for each fixed deterministic direction need not exclude a geodesic whose direction is itself selected by the random environment.

The bigeodesic manuscript marks paths after finitely increasing edge weights. It groups their asymptotic labels into narrow intervals and compares neighboring marked paths using planarity. A local modification charges a positive passage-time cost whenever a marked path uses the modified region. Adding the differences along ordered paths telescopes, while narrow label intervals restrict the total boundary contribution. The contradiction requires the charge to survive conditioning and the path selection to cover random labels. These are the main tasks beyond an argument for a preassigned direction.

🏷️ Corners and flat sides require different contradictions

For a hypothetical corner, two distinct supporting functionals impose a transverse passage penalty. The manuscript constructs cheap crossings of narrow strips by changing the edge law, then compares the changed law with the original one. A useful Gamma calculation makes the cost explicit.

Let $P$ have Gamma shape $k$ and rate $\lambda$, and let $Q$ have rate $\lambda (1+\delta )$, with $0<\delta <1$. For $L=dP/dQ$,

$${\mathbb{E}}_Q{L}^2=(1-{\delta }^2{)}^{-k}.$$

Indeed, insert the two Gamma densities into $\int p^2/q$. For $m$ independent changed edges the second moment is this quantity to the power $m$. Consequently, $m{\delta }^2=O(1)$ keeps the change of measure controlled. In the source’s strip choice, $m$ is of order $ns$ and $\delta$ of order $s/n$, so choosing $n$ of order $s^3$ gives precisely that balance. Disjoint-witness estimates extend the comparison from selected crossings to competing paths.

For a flat side, the exponential argument instead produces a nonnegative additive defect. A hypothetical flat segment forces a positive lower bound for a suitable mean excess cost, while a repeated spatial comparison contracts that same excess by a fixed factor. Iteration would drive it to zero. The construction of this contraction is the new input; it is not implied by the corner argument.

🏷️ Key steps and proof outlines

The two manuscripts use different contradictions. Bigeodesic exclusion compares a finite budget of asymptotic labels with arbitrarily large local perturbation gains. Shape differentiability compares rare local path witnesses with the shape theorem. Strict convexity additionally requires a contraction that preserves the class of paths being optimized.

A pathwise budget covers random geodesic labels

In one directional chart, let $r(\rho )$ be the horizontal coordinate of a supporting-functional label $\rho$. Choose deterministic labels $\alpha ,\beta$ bracketing a marked bigeodesic label. Suppose a finite increase of weights adds cost at least $b$ along initial portions of its two arms through $k$. Comparator rays from a sufficiently distant site $y$ avoid the changed region and cross the two arms by planar ordering. They remain minimizing in the increased metric because their own weights are unchanged and all other weights only increased.

Following the comparator rays through $y$ gives a competing walk between the crossing points. Their costs are calibrated by the fixed-label Busemann functions. Additivity cancels the portions ending at the crossing points and gives

$$b\le B_{\alpha }(y,k)+B_{-\beta }(y,k).$$

This inequality is pathwise and does not require the selected labels to be deterministic. On a horizontal grid of spacing $l$, sum it between successive marks in the same label bin. Busemann asymptotics leave only the bin width $r(\beta )-r(\alpha )$ times the interval length, plus a sublinear endpoint error. The maximum of the first $N$ endpoint errors is still $o(Nl)$, so it also controls random first and last marks. If each grid site has marginal marking probability $q_{\alpha ,\beta }$, bounded reverse Fatou and linearity of expectation yield

$$\frac{b}{l}{q}_{\alpha ,\beta }\le r(\beta )-r(\alpha ).$$

No independence or ergodicity of the marks is needed (OpenAI, 2026a).

Finite changes can have bounded law cost and divergent gain

The perturbation raises low edges to a separated high-weight range with probability proportional to

$${\delta }_h=\frac{\eta }{(h+2)\log (h+2)},$$

where $h$ is the edge’s height. In a cone there are $O(h+1)$ eligible edges at height $h$. The one-edge likelihood second moment is $1+C{\delta }_h^2$, so the product likelihood is bounded by

$$\exp \left(C\sum _h(h+1){\delta }_h^2\right)<\infty .$$

Yet the sum of the raising probabilities along sufficiently many usable edges of a ray diverges. The distinction is a summable squared law cost versus a divergent linear gain. The source makes this valid even after choosing a path from the perturbed environment: conditional on that entire output, the raising indicators are independent with probability

$$1_{\{Y_e\ge b_0\}}\frac{{\delta }_{h(e)}}{p_b+{\delta }_{h(e)}},$$

where $p_b$ is the original probability of the high-weight range. Thus path selection does not silently reuse an unconditional independence assertion.

For each gain target $M$, the construction supplies marks with probability bounded below independently of $M$. A separate fixed-radius raised edge ensures distinct marks have distinct labels. Although the required comparison distance may grow with $M$, the grid spacing stays fixed. For fixed $M$, refine the deterministic label partition until any given mark is separated from the finitely many nearby marked labels. The discarded probability tends to zero. Summing the label budgets over bins of total width $W_I$ then gives

$$0<p/8\le q_M\le l{W}_I/M.$$

Only after refinement does $M$ increase, producing the contradiction. This order of limits is what handles environment-selected labels.

A corner forces many disjoint rare witnesses

For the Gamma companion, suppose the norm has two extreme supporting functionals at $u=(1,b)$. Their transverse slopes differ by $2c>0$. Let $f$ be their midpoint and define the additive defect of a path by $H(P)=\mathrm{cost}(P)-f(\Delta P)$.

The strip and change-of-measure estimates supply one fixed large scale with longitudinal size $L$ and transverse size $s$. At this scale, a local event consisting of either a sufficiently negative support defect or an unusually cheap forward crossing has probability at most $2q_0$, with $q_0$ as small as required. Break any simple path into chunks when its longitudinal displacement reaches $2L$ or its transverse displacement reaches $s$.

A cheap transverse chunk contradicts one extreme support unless it supplies a negative-defect witness. A backward chunk cannot be cheap because weights are nonnegative. A cheap forward chunk either has a negative-defect outer piece or contains the prescribed cheap crossing. Repeatedly cut off negative-defect prefixes; the bounded negative defect of a single step controls the overshoot at each cut. If $N$ is the number of full chunks and $M_{\mathrm{tot}}$ the total number of edge-disjoint witnesses from those full chunks and the final remainder, the resulting deterministic estimate is

$$H(P)\ge (N-1)\eta s-4\eta s{M}_{\mathrm{tot}},$$

for fixed $\eta >0$. Hence an abnormally low-defect path has at least $\lfloor N/16\rfloor$ witnesses for large $N$.

There are at most $49^N$ coarse itineraries and $4^N$ allocations of these witnesses among the itinerary positions. The disjoint-occurrence inequality bounds a specified event list by $(2q_0{)}^{\lfloor N/16\rfloor }$, even when a coarse box is revisited. For continuous Gamma weights the source proves this by monotone dyadic quantile approximation and finite Bernoulli certificates, so no boundedness of the Gamma density is required. Thus

$$\mathbb{P}(\exists \text{ a low-defect path with }N\text{ chunks})\le 196^N(2q_0{)}^{\lfloor N/16\rfloor }.$$

Choose $q_0$ to make this summable. Borel–Cantelli yields $H(P)\ge N\eta s/2$ for every sufficiently long path. Approximate minimizers toward $tu$ have $N+1\ge t/(2L)$, whereas the shape theorem says $H(P)/t\to 0$. The positive lower bound $\eta s/(4L)$ contradicts this. The scale is fixed before $t\to \infty$ (OpenAI, 2026b).

A flat face requires a stable improvement procedure

In the exponential case, let $b(n)$ be the infimum of mean period excess over the manuscript’s admissible local roads at scale $n$. Under a hypothetical flat face, its preliminary bounds give $0<c_0\le b(n)\le C_s{n}^{3/4}$. The improvement theorem constructs a road in the same class, after a fixed scale enlargement, with

$$b(Dn)\le \rho b(n),\rho <1.$$

Its main issue is removing clipping: a small clipped mean alone does not bound the full mean. The source chooses the cheaper of a baseline piece and a crossing with common endpoints, uses a matched truncation level to control both clipped costs and large-positive-cost probabilities, then replaces exceptional clusters by an independent spare road. Endpoint gauge corrections telescope, and fixed support radii preserve locality after rescaling. The independence comes from disjoint retained tubes and private exterior completions, while traveled edges keep their actual weights.

Iteration now gives $c_0\le b(D^k{n}_0)\le {\rho }^{k}b(n_0)\to 0$, a contradiction. The closure of the road class under this construction is essential to repeating the inequality; a one-time improvement with growing dependence would not suffice.

See Also

• Family 220 also uses paths that revisit the same random medium, but its paths are sampled dynamically rather than chosen to minimize cost.
• Family 211 studies limiting random metrics when the graph itself is random.

🏷️ Manuscripts and verification scope

• No bigeodesics in planar first-passage percolation — pinned manuscript and companion source.
• Strict convexity and differentiability of the planar exponential first-passage limit shape — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The documented selection covers differentiability for Gamma weights, including exponential weights. It does not cover the bigeodesic exclusion or the additional exponential strict-convexity claim. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. No bigeodesics in planar first-passage percolation.

🐻  OpenAI 2026b. Strict convexity and differentiability of the planar exponential first-passage limit shape.