Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.3 — PP(a↮v1↔vn)=P2n−1\mathbb{P}_P(a \nleftrightarrow v_1 \leftrightarrow v_n) = P^{2n-1}PP​(a↮v1​↔vn​)=P2n−1

Proved
BunkbedFalse.gadget_sep

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

combinatoricsgraph-theorypercolationprobability

In the gadget graph GnG_nGn​, for n≥3n \ge 3n≥3 and 0<P<10 < P < 10<P<1,

PP(a↮v1↔vn)  =  P2n−1.\mathbb{P}_P\bigl(a \nleftrightarrow v_1 \leftrightarrow v_n\bigr) \;=\; P^{2n-1}.PP​(a↮v1​↔vn​)=P2n−1.

In words: the probability that v1v_1v1​ and vnv_nvn​ lie in a common component which does not contain aaa. Such a component must contain the whole path v1→v2→⋯→vnv_1 \to v_2 \to \dots \to v_nv1​→v2​→⋯→vn​, which requires its n−1n-1n−1 edges to be open, and every one of the nnn spokes at aaa must be closed; these events have probabilities Pn−1P^{n-1}Pn−1 and PnP^{n}Pn respectively.

Formalization Note This is the partition probability Pa∣bcP_{a|bc}Pa∣bc​ for a=0a = 0a=0, b=v1b = v_1b=v1​, c=vnc = v_nc=vn​. Note 2n−12n - 12n−1 is natural-number subtraction, which is harmless since n≥3n \ge 3n≥3.

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

/-- **Lemma 5.3** (p. 8). `ℙ_P(a ↮ v₁ ↔ vₙ) = P^{2n-1}`. -/
theorem gadget_sep (n : ℕ) (P : ℚ) (hn : 3 ≤ n) (hP0 : 0 < P) (hP1 : P < 1) :
    Pa_bc (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) = P ^ (2 * n - 1) := 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.3.
Read-back

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

Read-back — BunkbedFalse.gadget_sep

Setting and vocabulary. Fix a natural number nnn and a rational number PPP. The declaration concerns a fixed finite graph GnG_nGn​, the gadget, whose vertex set is Fin(n+1)={0,1,…,n}\mathrm{Fin}(n+1) = \{0, 1, \dots, n\}Fin(n+1)={0,1,…,n}. Write a:=0a := 0a:=0 and vi:=iv_i := ivi​:=i for 1≤i≤n1 \le i \le n1≤i≤n. Its edge set EnE_nEn​ (gadgetE n) consists of exactly the unordered pairs

En  =  { {a,vj}:1≤j≤n }⏟the n "spokes"  ∪  { {vi,vi+1}:1≤i≤n−1 }⏟the n−1 "path" edges,E_n \;=\; \underbrace{\{\,\{a, v_j\} : 1 \le j \le n\,\}}_{\text{the } n \text{ "spokes"}} \;\cup\; \underbrace{\{\,\{v_i, v_{i+1}\} : 1 \le i \le n-1\,\}}_{\text{the } n-1 \text{ "path" edges}},En​=the n "spokes"{{a,vj​}:1≤j≤n}​​∪the n−1 "path" edges{{vi​,vi+1​}:1≤i≤n−1}​​,

so GnG_nGn​ is a fan: a path v1−v2−⋯−vnv_1 - v_2 - \cdots - v_nv1​−v2​−⋯−vn​ together with a hub aaa joined to every vjv_jvj​. (Verified: ∣En∣=2n−1|E_n| = 2n - 1∣En​∣=2n−1, e.g. E3={{0,1},{0,2},{0,3},{1,2},{2,3}}E_3 = \{\{0,1\},\{0,2\},\{0,3\},\{1,2\},\{2,3\}\}E3​={{0,1},{0,2},{0,3},{1,2},{2,3}}.)

Each edge eee carries the weight (gadgetW n P)

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

For a subset S⊆EnS \subseteq E_nS⊆En​ of open edges, the configuration weight is   wt(S)=(∏e∈Sw(e))(∏e∈En∖S(1−w(e)))\;\mathrm{wt}(S) = \big(\prod_{e \in S} w(e)\big)\big(\prod_{e \in E_n \setminus S} (1 - w(e))\big)wt(S)=(∏e∈S​w(e))(∏e∈En​∖S​(1−w(e))), and for a decidable event E\mathcal{E}E on subsets,   P[E]=∑S⊆En1[E(S)]⋅wt(S)\;\mathbb{P}[\mathcal{E}] = \sum_{S \subseteq E_n} \mathbf{1}[\mathcal{E}(S)] \cdot \mathrm{wt}(S)P[E]=∑S⊆En​​1[E(S)]⋅wt(S). This is ordinary independent Bernoulli bond percolation on GnG_nGn​ in which each spoke is open with probability 1−P1 - P1−P and each path edge is open with probability PPP; no hypothesis forces these to be probabilities, and there is no internal normalisation. Reachability "x↔Syx \leftrightarrow_S yx↔S​y" means xxx and yyy lie in the same connected component of the graph on Fin(n+1)\mathrm{Fin}(n+1)Fin(n+1) whose edge set is exactly SSS (so x↔Sxx \leftrightarrow_S xx↔S​x always holds).

The quantity Pa_bc E w a b c is, by definition, the probability of the event

{ b↔Sc  and  ¬ (a↔Sb) }.\big\{\,b \leftrightarrow_S c\ \textbf{ and }\ \neg\,(a \leftrightarrow_S b)\,\big\}.{b↔S​c  and  ¬(a↔S​b)}.

Note precisely which relations occur: the asserted reachability is between the second and third arguments, and the negated one is between the first and second. The pair (a,c)(a, c)(a,c) is not mentioned. (Logically the negation of a↔ca \leftrightarrow ca↔c follows by transitivity, and numerically the variant negating a↔ca \leftrightarrow ca↔c instead gives identical values — e.g. 1/2431/2431/243 for n=3n = 3n=3, P=1/3P = 1/3P=1/3 — but literally the statement negates a↔ba \leftrightarrow ba↔b only.)

The assertion. With the three distinguished vertices instantiated as a=0a = 0a=0, b=1=v1b = 1 = v_1b=1=v1​, c=Fin.last n=n=vnc = \mathrm{Fin.last}\,n = n = v_nc=Fin.lastn=n=vn​, the theorem states: for every natural number nnn and every rational PPP such that

  • 3≤n3 \le n3≤n,
  • 0<P0 < P0<P,
  • P<1P < 1P<1,

one has the exact closed-form identity

P[ v1↔vn  and  a↮v1 ]  =  P 2n−1,\mathbb{P}\Big[\,v_1 \leftrightarrow v_n\ \text{ and }\ a \not\leftrightarrow v_1\,\Big] \;=\; P^{\,2n - 1},P[v1​↔vn​  and  a↔v1​]=P2n−1,

where the exponent 2n−12n - 12n−1 is truncated natural-number subtraction.

Degenerate cases and hypothesis usage.

  • The exponent's natural subtraction is safe under the stated hypotheses: 3≤n3 \le n3≤n forces 2n−1≥52n - 1 \ge 52n−1≥5, so no truncation occurs. Truncation happens only at n=0n = 0n=0, where 2⋅0−12 \cdot 0 - 12⋅0−1 evaluates to 000.
  • n=0n = 0n=0 is genuinely excluded by 3≤n3 \le n3≤n and the identity fails there: the vertex type collapses to a single point, so a=b=ca = b = ca=b=c, the event becomes 0↔0∧¬(0↔0)0 \leftrightarrow 0 \wedge \neg(0 \leftrightarrow 0)0↔0∧¬(0↔0), which is unsatisfiable, and the left side is 000 while the right side is P0=1P^0 = 1P0=1. Numerically, at P=1/2P = 1/2P=1/2: (0,1)(0, 1)(0,1).
  • The hypothesis 3≤n3 \le n3≤n is nevertheless stronger than necessary: the identity also holds at n=1n = 1n=1 (left =1/2== 1/2 ==1/2= right at P=1/2P = 1/2P=1/2; here b=c=v1b = c = v_1b=c=v1​, so the asserted reachability is trivial) and at n=2n = 2n=2 (both sides 1/81/81/8 at P=1/2P = 1/2P=1/2).
  • The hypotheses 0<P0 < P0<P and P<1P < 1P<1 appear to be unused: both sides are polynomials in PPP, and the identity was confirmed numerically at P=0P = 0P=0 (both 000), P=1P = 1P=1 (both 111), P=3/2P = 3/2P=3/2 (both 243/32243/32243/32) and P=−1/2P = -1/2P=−1/2 (both −1/32-1/32−1/32), i.e. outside the stated range in each direction. Note also that at P=0P = 0P=0 or P=1P = 1P=1 one of the two edge weights is 000 and at P∉[0,1]P \notin [0,1]P∈/[0,1] the "weights" are not probabilities, but the identity is insensitive to this.
  • No connectivity, distinctness, or non-degeneracy hypothesis is imposed on the three vertices beyond what 3≤n3 \le n3≤n implies; GnG_nGn​ is connected as a graph by construction.

Numerical verification. HOLDS. A scratch file evaluated both sides for all of (n,P)(n, P)(n,P) with n∈{3,4,5,6}n \in \{3,4,5,6\}n∈{3,4,5,6} and P∈{1/2,1/3,2/5,3/7,7/10}P \in \{1/2, 1/3, 2/5, 3/7, 7/10\}P∈{1/2,1/3,2/5,3/7,7/10} (13 combinations); the list of mismatches was empty and the conjunction of all equality tests returned true. Representative values:

nnnPPPleft sideP2n−1P^{2n-1}P2n−1
31/21/21/21/321/321/321/321/321/32
31/31/31/31/2431/2431/2431/2431/2431/243
32/52/52/532/312532/312532/312532/312532/312532/3125
33/73/73/7243/16807243/16807243/16807243/16807243/16807243/16807
41/21/21/21/1281/1281/1281/1281/1281/128
41/31/31/31/21871/21871/21871/21871/21871/2187
42/52/52/5128/78125128/78125128/78125128/78125128/78125128/78125
51/21/21/21/5121/5121/5121/5121/5121/512
51/31/31/31/196831/196831/196831/196831/196831/19683
52/52/52/5512/1953125512/1953125512/1953125512/1953125512/1953125512/1953125

No counterexample was found in the range permitted by the hypotheses. The mechanism is transparent from the edge count: the event forces every one of the 2n−12n-12n−1 edges into a determined state — all n−1n-1n−1 path edges open (each probability PPP) and all nnn spokes closed (each probability 1−(1−P)=P1 - (1-P) = P1−(1−P)=P) — giving Pn−1⋅Pn=P2n−1P^{n-1} \cdot P^n = P^{2n-1}Pn−1⋅Pn=P2n−1.

For contrast, the sibling quantities at n=3n = 3n=3, P=1/2P = 1/2P=1/2 are P[a↔b∧¬a↔c]=3/16\mathbb{P}[a{\leftrightarrow}b \wedge \neg a{\leftrightarrow}c] = 3/16P[a↔b∧¬a↔c]=3/16, P[a↔c∧¬a↔b]=3/16\mathbb{P}[a{\leftrightarrow}c \wedge \neg a{\leftrightarrow}b] = 3/16P[a↔c∧¬a↔b]=3/16, P[a↔b∧b↔c]=15/32\mathbb{P}[a{\leftrightarrow}b \wedge b{\leftrightarrow}c] = 15/32P[a↔b∧b↔c]=15/32 and P[all three separated]=1/8\mathbb{P}[\text{all three separated}] = 1/8P[all three separated]=1/8, none of which equals 1/321/321/32.

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