Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.1 — PP(a↔vn)\mathbb{P}_P(a \leftrightarrow v_n)PP​(a↔vn​) in the gadget GnG_nGn​

Proved
BunkbedFalse.gadget_conn

by burkh4rt · Sep 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theorypercolationprobability

Consider the gadget graph GnG_nGn​ of Fig. 2: vertices aaa and v1,…,vnv_1, \dots, v_nv1​,…,vn​, where each spoke aaa–viv_ivi​ is retained with probability 1−P1-P1−P and each path edge viv_ivi​–vi+1v_{i+1}vi+1​ is retained with probability PPP. For n≥3n \ge 3n≥3 and 0<P<10 < P < 10<P<1,

PP(a↔vn)  =  1−P2n1+P.\mathbb{P}_P\bigl(a \leftrightarrow v_n\bigr) \;=\; \frac{1 - P^{2n}}{1 + P}.PP​(a↔vn​)=1+P1−P2n​.

The proof is a two-case recurrence on whether the spoke (a,vn)(a, v_n)(a,vn​) is open, giving Pn=(1−P)+P2Pn−1P_n = (1-P) + P^2 P_{n-1}Pn​=(1−P)+P2Pn−1​ with P0=0P_0 = 0P0​=0, solved by induction.

This is the first of three elementary computations that together determine how well the gadget GnG_nGn​ simulates a single hyperedge, which is the quantitative heart of the refutation.

Formalization Note Vertices are Fin (n+1) with a=0a = 0a=0 and vi=iv_i = ivi​=i, so vnv_nvn​ is Fin.last n. The weight function assigns 1−P1-P1−P to any edge meeting 000 and PPP to the rest.

Preamble
import Definitions.Def_BunkbedHypergraph
open Bunkbed Bunkbed.Hyper SimpleGraph Finset
Formal statement
namespace BunkbedFalse

/-- **Lemma 5.1** (Gladkov–Pak–Zimin, PNAS 122 (2025) e2420725122, p. 8). For the gadget
graph `Gₙ` of Fig. 2, `ℙ_P(a ↔ vₙ) = (1 - P^{2n})/(1 + P)`. -/
theorem gadget_conn (n : ℕ) (P : ℚ) (hn : 3 ≤ n) (hP0 : 0 < P) (hP1 : P < 1) :
    connProb (gadgetE n) (gadgetW n P) 0 (Fin.last n) = (1 - P ^ (2 * n)) / (1 + P) := by sorry

end BunkbedFalse
Source
N. Gladkov, I. Pak, A. Zimin, "The bunkbed conjecture is false", Proc. Natl. Acad. Sci. USA 122 (2025), no. 24, e2420725122, https://doi.org/10.1073/pnas.2420725122 - p. 8, Lemma 5.1.
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back — BunkbedFalse.gadget_conn

What the statement is about

The declaration fixes a natural number nnn and a rational number PPP, together with three hypotheses: n≥3n \ge 3n≥3, 0<P0 < P0<P, and P<1P < 1P<1. It then asserts a closed-form value for a single Bernoulli-bond-percolation connection probability on one explicit finite graph.

The graph

The vertex set is {0,1,2,…,n}\{0, 1, 2, \dots, n\}{0,1,2,…,n} (n+1n+1n+1 vertices). The edge set GnG_nGn​ consists of exactly two families:

  • Spokes: {0,j}\{0, j\}{0,j} for every j∈{1,…,n}j \in \{1, \dots, n\}j∈{1,…,n} — i.e. vertex 000 is joined to every other vertex. (nnn edges.)
  • Path edges: {i,i+1}\{i, i+1\}{i,i+1} for every i∈{1,…,n−1}i \in \{1, \dots, n-1\}i∈{1,…,n−1} — a path running 1−2−3−⋯−n1 - 2 - 3 - \cdots - n1−2−3−⋯−n, not touching vertex 000. (n−1n-1n−1 edges.)

So the graph is a fan/wheel-like graph on 2n−12n-12n−1 edges: a path on {1,…,n}\{1,\dots,n\}{1,…,n} plus a hub 000 adjacent to all path vertices. (Verified by evaluation: for n=5n = 5n=5 the edge set is exactly {01,02,03,04,05,12,23,34,45}\{01,02,03,04,05,12,23,34,45\}{01,02,03,04,05,12,23,34,45}.)

The weights

Each edge is retained independently, with retention probability

w(e)  =  {1−Pif 0∈e(the spokes),Potherwise(the path edges).w(e) \;=\; \begin{cases} 1 - P & \text{if } 0 \in e \quad (\text{the spokes}),\\[2pt] P & \text{otherwise} \quad (\text{the path edges}).\end{cases}w(e)={1−PP​if 0∈e(the spokes),otherwise(the path edges).​

Note the spokes carry 1−P1-P1−P and the path edges carry PPP, not the other way round. (Verified: at P=1/3P = 1/3P=1/3 the three spokes of G3G_3G3​ have weight 2/32/32/3 and the two path edges have weight 1/31/31/3.)

The probability is defined in the fully elementary way: sum over all 22n−12^{2n-1}22n−1 subsets SSS of the edge set, weighting SSS by (∏e∈Sw(e))(∏e∈Gn∖S(1−w(e)))\left(\prod_{e \in S} w(e)\right)\left(\prod_{e \in G_n \setminus S} (1 - w(e))\right)(∏e∈S​w(e))(∏e∈Gn​∖S​(1−w(e))), and keeping those SSS for which the two distinguished vertices lie in the same component of the graph with vertex set {0,…,n}\{0,\dots,n\}{0,…,n} and edge set SSS.

The two vertices

The connection event is between:

  • u=0u = 0u=0 — the hub, the vertex incident to all nnn spokes; and
  • v=nv = nv=n (written Fin.last n) — the far endpoint of the path, which is also the unique path-endpoint of largest index. Note nnn is itself adjacent to the hub via a spoke, so the two vertices are neighbours.

The claim

Pr⁡[ 0↔n ]  =  1−P2n1+P.\Pr\big[\,0 \leftrightarrow n \,\big] \;=\; \frac{1 - P^{2n}}{1 + P}.Pr[0↔n]=1+P1−P2n​.

Since (1+P)(1+P)(1+P) divides 1−P2n1 - P^{2n}1−P2n, the right-hand side is in fact the polynomial 1−P+P2−⋯−P2n−11 - P + P^2 - \cdots - P^{2n-1}1−P+P2−⋯−P2n−1; the identity is therefore an identity of polynomials in PPP, not merely of numbers on (0,1)(0,1)(0,1).

Numerical verification

I built a scratch file evaluating both sides. The identity HOLDS at every tested point (exact rational equality):

nnnPPPboth sides
31/21/21/221/3221/3221/32
31/31/31/3182/243182/243182/243
32/52/52/52223/31252223/31252223/3125
39/109/109/1024661/10000024661/10000024661/100000
31/1001/1001/1009900990099/10109900990099/10^{10}9900990099/1010
41/21/21/285/12885/12885/128
41/31/31/31640/21871640/21871640/2187
42/52/52/555767/7812555767/7812555767/78125
47/87/87/8734161/2097152734161/2097152734161/2097152
51/21/21/2341/512341/512341/512
51/31/31/314762/1968314762/1968314762/19683
52/52/52/51394943/19531251394943/19531251394943/1953125
53/73/73/728241620/4035360728241620/4035360728241620/40353607

(The value P=1/2P = 1/2P=1/2 is a poor test point on its own, since there 1−P=P1 - P = P1−P=P and the spoke/path weight distinction vanishes; the asymmetric values 1/3,2/5,9/10,7/8,3/7,1/1001/3, 2/5, 9/10, 7/8, 3/7, 1/1001/3,2/5,9/10,7/8,3/7,1/100 do distinguish them and all match.)

Hypotheses: used, needed, degenerate cases

  • n≥3n \ge 3n≥3 is stronger than needed, but is not vacuous. The identity also holds at n=1n = 1n=1 (2/3=2/32/3 = 2/32/3=2/3 at P=1/3P=1/3P=1/3) and n=2n = 2n=2 (20/27=20/2720/27 = 20/2720/27=20/27 at P=1/3P=1/3P=1/3). It fails at n=0n = 0n=0: there the graph has the single vertex 000, no edges, the left side is 111 (a vertex is reachable from itself), and the right side is (1−P0)/(1+P)=0(1 - P^0)/(1+P) = 0(1−P0)/(1+P)=0. So n≥3n \ge 3n≥3 excludes the one failing nnn, with n∈{1,2}n \in \{1,2\}n∈{1,2} excluded gratuitously.
  • P<1P < 1P<1 is not needed. At P=1P = 1P=1 both sides are 000; at P=3/2P = 3/2P=3/2 both sides equal −133/32-133/32−133/32 (for n=3n=3n=3) — the identity persists outside [0,1][0,1][0,1], where neither side is a probability.
  • 0<P0 < P0<P excludes exactly one genuinely bad point. At P=0P = 0P=0 both sides are 111, so positivity is not needed there; but at P=−1P = -1P=−1 the left side is 666 (for n=3n=3n=3) while the right side is 000, because rational division by zero returns 000. So 0<P0 < P0<P is doing work only at the single point P=−1P = -1P=−1.
  • The claim is not trivial for any admissible nnn or PPP: under n≥3n\ge 3n≥3, 0<P<10<P<10<P<1 both sides are strictly between 000 and 111 and depend on nnn (at P=1/3P=1/3P=1/3: 182/243182/243182/243, 1640/21871640/21871640/2187, 14762/1968314762/1968314762/19683 for n=3,4,5n = 3,4,5n=3,4,5).

Indexing remark

The pair of vertices is (hub, path-endpoint-nnn). The closed form is specific to a path endpoint: at n=5n=5n=5, P=1/3P=1/3P=1/3 the hub-to-kkk probabilities are

k=1: 1476219683,k=2: 1585419683,k=3: 1596219683,k=4: 1585419683,k=5: 1476219683,k=1:\ \tfrac{14762}{19683},\quad k=2:\ \tfrac{15854}{19683},\quad k=3:\ \tfrac{15962}{19683},\quad k=4:\ \tfrac{15854}{19683},\quad k=5:\ \tfrac{14762}{19683},k=1: 1968314762​,k=2: 1968315854​,k=3: 1968315962​,k=4: 1968315854​,k=5: 1968314762​,

and (1−P10)/(1+P)=14762/19683(1-P^{10})/(1+P) = 14762/19683(1−P10)/(1+P)=14762/19683. So the formula matches the two path endpoints k=1k=1k=1 and k=nk=nk=n (which are interchangeable by the path's reflection symmetry) and not the interior vertices. Also k=0k = 0k=0 gives 111 trivially.

Other literal features

  • The declaration lives in namespace BunkbedFalse and is stated with sorry (no proof).
  • It imports the hypergraph-percolation file, but every symbol it uses (GnG_nGn​, the weights, the connection probability) comes from the Bernoulli-percolation file; nothing from the hypergraph/Wierman–Ziff layer, and nothing about two-level "bunkbed" graphs, posts, or transversal sets, appears in the statement. The statement concerns a single-level graph only.
Human review
  • Endorsed by Shuze Chen · Sep 11, 2026

  • Endorsed by burkh4rt · Sep 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me