Benjamini-Schramm conjecture p_c<p_u for non-amenable Cayley graphs

Benjamini-Schramm conjecture p_c<p_u for non-amenable Cayley graphs

OpenAI's claim

OpenAI presents a proof in the selected manuscript. Every nonamenable locally finite quasi-transitive graph is claimed to satisfy $p_c<p_{2\to2}\leq p_u$, yielding a nonempty phase with infinitely many infinite clusters.

Mathematical statement of the claimed result

Result 1.

Let $G=(V,E)$ have infinitely many vertices, finite degrees, connectedness and quasi-transitivity, with positive vertex Cheeger constant \[ h_V(G)=\inf_{0<|A|<\infty}|\partial_VA|/|A|>0. \] For independent bond percolation, let $T_p(x,y)=\mathbb P_p(x\leftrightarrow y)$, acting on $\ell^2(V)$ with counting measure, and $p_2=\sup\{p:\|T_p\|_{2\to2}<\infty\}$. With $p_c$ and $p_u$ the appearance and uniqueness thresholds, the source claims \[ \sup_{p<p_c}\|T_p\|_{2\to2}=\|T_{p_c}\|_{2\to2}<\infty, \qquad p_c<p_2\le p_u. \] It further supplies $p_c<p_1<p_2'<1$ such that the uniform-edge-label coupling almost surely has infinitely many infinite clusters simultaneously at every $p\in[p_1,p_2']$.

Outline of the argument

For the new unimodular case, local endpoint maps control moments of finite critical clusters. A deformation lowers susceptibility while retaining a large connectivity-operator norm, thereby proving the strict operator-threshold separation; the nonunimodular case uses the established operator result.

Formal verification

For family 214, the documented statements include the strict operator-threshold separation, the nonunique percolation interval, and selected critical moment and tail bounds, with a Cayley-graph specialization. The listed Comparator files are BenjaminiSchramm.lean, CayleyPercolation.lean. The inventory does not supply a named declaration for these Comparator entries. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

• OpenAI, Nonuniqueness of percolation on nonamenable quasi-transitive graphs, 2026-09-24; citation key OAI:Nonuniqueness-of-percolation-on-nonamenable-quasi-transitive-graphs-September-24-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• Family 214: Lean scope.
• Comparator BenjaminiSchramm.json.
• Comparator BenjaminiSchramm.lean.
• Comparator CayleyPercolation.json.
• Comparator CayleyPercolation.lean.
• OpenAI catalogue entry.

Benjamini-Schramm conjecture p_c<p_u for non-amenable Cayley graphs

Definitions and mathematical statement

For a locally finite Cayley graph $G$, Bernoulli bond percolation independently retains each edge with probability $p$. Let $N_\infty$ be the number of infinite open clusters and let $o$ be a fixed vertex. Define \[ p_c=\inf\{p:{\mathbb{P}}_p(o\leftrightarrow\infty)>0\},\qquad p_u=\inf\{p:{\mathbb{P}}_p(N_\infty=1)=1\}. \] A finitely generated group is amenable if it has a translation-invariant mean, equivalently a Følner sequence of finite sets; nonamenability is failure of this property. The selected assertion is $p_c(G)<p_u(G)$ exactly when the infinite underlying group is nonamenable, for every finite generating set defining a Cayley graph. The thresholds are infima, so the statement does not prescribe cluster behavior at either endpoint. Site percolation and arbitrary nontransitive graphs are not silently substituted.

Formulation and concept references: [S1].

Short English statement

Does a Cayley graph have a nonempty percolation phase with multiple infinite clusters exactly when its group is nonamenable?

Research attempt

The fixed generating set matters.

The inspected formulation in [S1, Conjecture 2] is about every finite generating set of the given infinite group. Its discussion of special generating systems does not establish that quantifier. Likewise, a planar site-percolation result or a nontransitive graph example is not silently transferred to Bernoulli bond percolation on an arbitrary Cayley graph.

We prove the complete regular-tree subcase, then derive an explicit isoperimetric/spectral sufficient condition for a nonuniqueness interval on a regular graph. The latter condition is stronger than nonamenability. Identifying that extra quantitative requirement pinpoints the limitation of this approach.

Assume the Cayley graph is undirected, connected and locally finite, of degree $d$. Edges are independently open with probability $p$. An infinite cluster contains an infinite simple ray from each of its vertices: apply the elementary infinite-branching-path lemma to the locally finite tree of finite simple paths in the cluster. This observation connects infinite connectivity with the finite-path estimates used below.

A universal elementary lower bound on criticality.

The number of simple paths of length $n\geq1$ starting at $o$ is at most $d(d-1)^{n-1}$. Each has $n$ distinct edges and is open with probability $p^n$. The union bound gives \[ \mathbb P_p(o\hbox{ has an open simple path of length }n) \leq d p\,[p(d-1)]^{n-1}. \] If $p(d-1)<1$, the right side tends to zero, while an infinite cluster would supply every such length. Therefore \[ p_c\geq\frac1{d-1}. \tag{360.1} \] This does not decide the endpoint, and the target only concerns the threshold infimum. Replacing the simple-path count by an exact tree count in a graph with cycles would not be legitimate.

Exact criticality on the regular tree.

Let $\mathbb T_d$ be the $d$-regular tree with $d\geq3$. After one oriented edge, each vertex has $d-1$ forward neighbors. Its forward open descendants form a Galton--Watson process with offspring distribution $\operatorname{Bin}(d-1,p)$. If $q$ is its extinction probability, independence gives \[ q=(1-p+pq)^{d-1}, \tag{360.2} \] where $q$ is the smallest fixed point in $[0,1]$. This last qualification follows by iterating the offspring generating function from zero: the $n$-th iterate is extinction by generation $n$.

For $0<p<1$, the generating function is strictly convex. If its derivative at one, $(d-1)p$, is at most one, its graph lies strictly above the diagonal before one, except for the irrelevant degenerate cases; hence $q=1$. If the derivative is greater than one, the function minus the diagonal is negative just to the left of one and positive at zero, so it has a fixed point below one. This proves survival exactly when $p>1/(d-1)$. At the root, the survival probability is \[ \theta(p)=1-(1-p+pq)^d, \tag{360.3} \] and consequently $p_c(\mathbb T_d)=1/(d-1)$.

Infinitely many infinite clusters for every subunit supercritical p.

Fix $p\in(1/(d-1),1)$. Choose an infinite ray in the tree and, at each successive vertex, choose a branch pointing off the ray. The corresponding forward rooted subtrees are pairwise disjoint; for $d\geq3$ there is at least one such branch at every vertex. For each chosen subtree require its attaching edge to be closed and its root's forward cluster to be infinite.

These events depend on pairwise disjoint edge sets. They are independent and each has the same positive probability $(1-p)(1-q)$. The probability that only finitely many occur is zero: for any tail, the probability that none occurs in its first $m$ branches is $(1-(1-p)(1-q))^m\to0$, and take a countable union over possible last occurrences. When an event occurs, its infinite cluster is separated from the rest of the tree by the closed attaching edge. Distinct successful branches therefore supply distinct infinite clusters. We have proved \[ N_\infty=\infty\quad\hbox{almost surely for } 1/(d-1)<p<1. \tag{360.4} \] For $p\leq1/(d-1)$ there are no infinite clusters, by the branching argument and a countable union over vertices. At $p=1$ the whole tree is connected. Hence $p_u(\mathbb T_d)=1$ and $p_c<p_u$ exactly as requested in this subcase.

The tree is nonamenable directly: for a finite nonempty vertex set $F$, its induced forest has at most $|F|-c$ edges, where $c\geq1$ is its number of components. The edge boundary therefore has size \[ |\partial_EF|=d|F|-2|E(F)|\geq(d-2)|F|+2c. \] In particular its isoperimetric constant is positive. Even-degree regular trees are the standard Cayley graphs of free groups, so this yields actual instances of the catalogue statement, not just an unrelated nontransitive branching model.

An isoperimetric upper bound on p_c, with exploration proof.

For a general graph define the edge constant \[ h=\inf_{\varnothing\ne F\text{ finite}} \frac{|\partial_EF|}{|F|}. \] We prove \[ p_c\leq\frac1{1+h}\quad\hbox{if }h>0. \tag{360.5} \] Explore the cluster of $o$ by testing an unexamined edge with one endpoint in the discovered cluster and one outside. On an open test add the new endpoint; on a closed test add none. Discard unexamined edges whose endpoints have both become discovered, since they need not be tested. After $t$ tests, let $O_t,C_t$ be the open and closed counts. The discovered vertex set has $1+O_t$ vertices, and the number of its still untested outgoing edges is at least \[ h(1+O_t)-C_t=h+(h+1)O_t-t. \tag{360.6} \] Every already tested edge in this boundary was closed, so subtracting $C_t$ is a valid, possibly wasteful bound. The adaptive order of testing does not change the fact that each fresh edge is an independent Bernoulli-$p$ variable.

Imagine an infinite independent sequence of test results, and put $S_t=h+(h+1)O_t-t$. Its increment is $h$ on an open result and $-1$ on a closed result. If $p>1/(h+1)$, its mean increment is positive. This random walk has positive probability to remain strictly positive forever. To see this without assuming a ruin formula, the strong law makes an independent future walk tend to $+\infty$, so its infimum is finite almost surely. For a sufficiently large integer $K$, its infimum exceeds $-Kh$ with positive probability. Force the first $K+1$ results to be open, an event of positive probability independent of the future. Their reserve then keeps $S_t$ positive at all times on that future event.

Whenever $S_t>0$, $360.6$ guarantees a further edge to test, so the actual exploration cannot stop. Infinitely many tests with the positive open density then discover infinitely many vertices. This proves positive survival probability and hence $360.5$.

A spectral obstruction to uniqueness.

Let $P$ be the simple-random-walk operator on $\ell^2(V)$, $Pf(x)=d^{-1}\sum_{y\sim x}f(y)$, and let $\rho=\|P\|_{2\to2}$. It is self-adjoint for an undirected regular graph. Write $\tau_p(x,y)=\mathbb P_p(x\leftrightarrow y)$. A connection contains a simple path, so the path union bound gives \[ \tau_p(x,y)\leq\sum_{n\geq0}(pd)^nP^n(x,y). \tag{360.7} \] Indeed simple paths of length $n$ are bounded in number by all walks of length $n$, namely $d^nP^n(x,y)$. We do not assign probability $p^n$ to a repeated-edge walk; it is only an upper bound on the number of simple paths.

If $pd\rho<1$, the operator series on the right converges on $\ell^2$ to $(I-pdP)^{-1}$. Its row at $o$ is an $\ell^2$ sequence, since the operator is bounded and self-adjoint. By nonnegativity and $360.7$, $\tau_p(o,\cdot)$ is also in $\ell^2$. In particular it cannot be bounded below by a positive constant on infinitely many vertices.

Suppose instead that there is almost surely a unique infinite cluster. Its existence implies $\theta(p)>0$: if every vertex had zero chance of belonging to it, a countable union would give zero chance of any infinite cluster. Transitivity makes the chance the same at every vertex. The increasing events that $o$ and $x$ belong to infinite clusters are positively correlated under product measure, by the Bernoulli correlation inequality. If both occur, uniqueness connects them. Thus \[ \tau_p(o,x)\geq\mathbb P_p(o\leftrightarrow\infty, x\leftrightarrow\infty) \geq\theta(p)^2>0 \tag{360.8} \] for every $x$, a contradiction. The correlation inequality follows first for increasing finite-coordinate events by induction on the independent bits, then for these events by limits. We conclude \[ p_u\geq\frac1{d\rho}. \tag{360.9} \] For the connected infinite regular graphs under discussion $d\rho$ is greater than one; the displayed bound is used only in its meaningful probability range.

A rigorous quantitative subcase of the conjecture.

Combining $360.5$ and $360.9$ proves \[ 1+h>d\rho\quad\Longrightarrow\quad p_c\leq\frac1{1+h}<\frac1{d\rho}\leq p_u. \tag{360.10} \] This gives a complete sufficient condition for the selected strict inequality. Its proof establishes a positive interval, rather than inferring strictness from two non-strict bounds with the same endpoint.

Nonamenability supplies positive isoperimetry, but it does not give the stronger numerical comparison $1+h>d\rho$ by any argument above. The two estimates can leave overlapping ranges. Nor may one change the generating set to improve $d,h,\rho$ and then declare the original graph settled. Those parameters and both thresholds depend on the chosen graph, whereas the requested quantifier is over every generating set.

The tree proof illustrates a further limitation of $360.10$: the disjoint-branch argument supplies nonuniqueness directly and can work when a crude combination of numerical bounds does not. For a graph with cycles, closing one attaching edge need not isolate an infinite branch, so the same construction cannot be copied without checking all alternative connections.

Diagnostics and outcome.

The finite computation iterates the branching generating function from zero for selected $d,p$, checks the explicit fixed points where available, and enumerates small finite subtrees to verify the edge-boundary identity. It records the formula for criterion $360.10$, without testing parameter triples. Finite-depth survival probabilities decrease toward the infinite survival probability; positive values at finite depth alone do not prove supercriticality, so the exact convexity argument remains essential.

The complete regular-tree result and the quantitative criterion are proved. The first missing step for arbitrary nonamenable Cayley graphs is a nonuniqueness mechanism beyond $360.10$, or a stronger bound that forces a strict interval for every generating set. The reverse amenable direction requires the established uniqueness theory rather than a tree computation; it is not reproved here. The full equivalence remains unresolved by this attempt.

Sources

• S1 H. Duminil-Copin, "Sixty years of percolation", Proc. International Congress of Mathematicians 2018, vol. IV, pp. 639-672; arXiv:1712.04651. https://ar5iv.labs.arxiv.org/html/1712.04651. Formulation source.