Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.1 — hyperedge simulation by the gadget GnG_nGn​

Proved
BunkbedFalse.hyperedge_simulation

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

combinatoricsgraph-theorypercolationprobability

Let n≥3n \ge 3n≥3 and 0<P<10 < P < 10<P<1, and consider the weighted gadget graph GnG_nGn​ on n+1n+1n+1 vertices, with b=v1b = v_1b=v1​ and c=vnc = v_nc=vn​. Then the two "mixed" partition probabilities agree,

Pab∣c  =  Pac∣b,P_{ab|c} \;=\; P_{ac|b},Pab∣c​=Pac∣b​,

and

Pabc Pa∣b∣c  −  Pab∣c Pac∣b  >  (n 1−P1+P−1)Pa∣bc.P_{abc}\,P_{a|b|c} \;-\; P_{ab|c}\,P_{ac|b} \;>\; \Bigl(n\,\frac{1-P}{1+P} - 1\Bigr) P_{a|bc}.Pabc​Pa∣b∣c​−Pab∣c​Pac∣b​>(n1+P1−P​−1)Pa∣bc​.

This is the hyperedge simulation lemma. A single 333-hyperedge cannot be simulated exactly by bond percolation on any graph, so the strategy is instead to show that GnG_nGn​ simulates one well enough: the displayed inequality says the simulation error can be driven below any prescribed threshold by increasing nnn. Taking P=1/2P = 1/2P=1/2 and n=3⋅401+1=1204n = 3 \cdot 401 + 1 = 1204n=3⋅401+1=1204 makes the right-hand side exceed the factor 400400400 demanded by the robust hyperedge lemma, which is what produces the counterexample.

Formalization Note The five partition probabilities are those of the triple a=0a = 0a=0, b=v1b = v_1b=v1​, c=vnc = v_nc=vn​ in GnG_nGn​. The symmetry Pab∣c=Pac∣bP_{ab|c} = P_{ac|b}Pab∣c​=Pac∣b​ reflects the reflection symmetry of GnG_nGn​ exchanging v1v_1v1​ and vnv_nvn​.

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

/-- **Lemma 4.1** (hyperedge simulation, p. 7). -/
theorem hyperedge_simulation (n : ℕ) (P : ℚ) (hn : 3 ≤ n) (hP0 : 0 < P) (hP1 : P < 1) :
    Pab_c (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) = Pac_b (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) ∧
    Pabc (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) * Pa_b_c (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) - Pab_c (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) * Pac_b (gadgetE n) (gadgetW n P) 0 1 (Fin.last n)
      > (n * (1 - P) / (1 + P) - 1) * Pa_bc (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) := 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. 7, Lemma 4.1 (Eq. [1]); proof p. 8.
Read-back

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

Read-back — BunkbedFalse.hyperedge_simulation

Setting and vocabulary

Fix a natural number nnn and a rational number PPP. The statement concerns a fixed finite graph GnG_nGn​ and a Bernoulli bond percolation on it.

The graph GnG_nGn​. Its vertex set is {0,1,2,…,n}\{0,1,2,\dots,n\}{0,1,2,…,n} (the type Fin (n+1)). Its edge set EnE_nEn​ consists of exactly

  • the spokes {0,j}\{0,j\}{0,j} for every jjj with 1≤j≤n1 \le j \le n1≤j≤n (all edges meeting the vertex 000), and
  • the path edges {i,i+1}\{i,i+1\}{i,i+1} for every iii with 1≤i≤n−11 \le i \le n-11≤i≤n−1.

So GnG_nGn​ is a fan: a hub 000 joined to every vertex of a path 1−2−⋯−n1 - 2 - \cdots - n1−2−⋯−n. It has ∣En∣=2n−1|E_n| = 2n-1∣En​∣=2n−1 edges. (Verified by evaluation: E3={01,02,03,12,23}E_3 = \{01,02,03,12,23\}E3​={01,02,03,12,23}, E5={01,02,03,04,05,12,23,34,45}E_5=\{01,02,03,04,05,12,23,34,45\}E5​={01,02,03,04,05,12,23,34,45}.)

The percolation measure. Each edge is open independently, with

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

Formally, a set S⊆EnS \subseteq E_nS⊆En​ of open edges carries weight ∏e∈Sw(e)⋅∏e∈En∖S(1−w(e))\prod_{e\in S} w(e)\cdot\prod_{e \in E_n\setminus S}(1-w(e))∏e∈S​w(e)⋅∏e∈En​∖S​(1−w(e)), and the probability of an event is the sum of these weights over all SSS in the power set of EnE_nEn​. Connectivity is measured in the simple graph whose edge set is exactly SSS (all n+1n+1n+1 vertices present, isolated vertices allowed), and "u↔vu \leftrightarrow vu↔v" is reachability there, which is reflexive.

The distinguished triple. a=0a = 0a=0 (the hub), b=1b = 1b=1 (one end of the path), c=nc = nc=n (the other end, Fin.last n).

The five probabilities, all in the above measure on GnG_nGn​:

Pabc=Pr⁡[ 0↔1 ∧ 1↔n ](by transitivity: all three in one cluster)Pa∣bc=Pr⁡[ 1↔n ∧ 0↮1 ]Pab∣c=Pr⁡[ 0↔1 ∧ 0↮n ]Pac∣b=Pr⁡[ 0↔n ∧ 0↮1 ]Pa∣b∣c=Pr⁡[ 0↮1 ∧ 1↮n ∧ 0↮n ]\begin{aligned} P_{abc} &= \Pr[\,0 \leftrightarrow 1 \ \wedge\ 1 \leftrightarrow n\,] && (\text{by transitivity: all three in one cluster})\\ P_{a|bc} &= \Pr[\,1 \leftrightarrow n \ \wedge\ 0 \not\leftrightarrow 1\,] \\ P_{ab|c} &= \Pr[\,0 \leftrightarrow 1 \ \wedge\ 0 \not\leftrightarrow n\,] \\ P_{ac|b} &= \Pr[\,0 \leftrightarrow n \ \wedge\ 0 \not\leftrightarrow 1\,] \\ P_{a|b|c} &= \Pr[\,0 \not\leftrightarrow 1 \ \wedge\ 1 \not\leftrightarrow n \ \wedge\ 0 \not\leftrightarrow n\,] \end{aligned}Pabc​Pa∣bc​Pab∣c​Pac∣b​Pa∣b∣c​​=Pr[0↔1 ∧ 1↔n]=Pr[1↔n ∧ 0↔1]=Pr[0↔1 ∧ 0↔n]=Pr[0↔n ∧ 0↔1]=Pr[0↔1 ∧ 1↔n ∧ 0↔n]​(by transitivity: all three in one cluster)

Note the exact literal form of each event: PabcP_{abc}Pabc​ conjoins 0↔10\leftrightarrow 10↔1 with 1↔n1\leftrightarrow n1↔n (not 0↔n0 \leftrightarrow n0↔n); Pab∣cP_{ab|c}Pab∣c​ and Pac∣bP_{ac|b}Pac∣b​ are both phrased relative to the hub aaa and each carries a single negation; Pa∣b∣cP_{a|b|c}Pa∣b∣c​ carries all three negations. These five events do partition the configuration space (numerically confirmed: the five values sum to exactly 111 at every point tested).

What the theorem asserts

For every natural number nnn and every rational PPP satisfying the three hypotheses

3≤n,0<P,P<1,3 \le n, \qquad 0 < P, \qquad P < 1,3≤n,0<P,P<1,

both of the following hold.

(i) An exact equality.

Pab∣c  =  Pac∣b,P_{ab|c} \;=\; P_{ac|b},Pab∣c​=Pac∣b​,

i.e. Pr⁡[ 0↔1 ∧ 0↮n ]  =  Pr⁡[ 0↔n ∧ 0↮1 ]\Pr[\,0 \leftrightarrow 1 \ \wedge\ 0 \not\leftrightarrow n\,] \;=\; \Pr[\,0 \leftrightarrow n \ \wedge\ 0 \not\leftrightarrow 1\,]Pr[0↔1 ∧ 0↔n]=Pr[0↔n ∧ 0↔1] in the fan GnG_nGn​ with spoke-probability 1−P1-P1−P and path-probability PPP.

(ii) A strict inequality.

Pabc⋅Pa∣b∣c  −  Pab∣c⋅Pac∣b  >  (n(1−P)1+P  −  1)⋅Pa∣bc.P_{abc}\cdot P_{a|b|c} \;-\; P_{ab|c}\cdot P_{ac|b} \;>\; \left(\frac{n(1-P)}{1+P} \;-\; 1\right)\cdot P_{a|bc}.Pabc​⋅Pa∣b∣c​−Pab∣c​⋅Pac∣b​>(1+Pn(1−P)​−1)⋅Pa∣bc​.

Here nnn on the right is the natural number cast to Q\mathbb{Q}Q, and the grouping is (n(1−P))/(1+P)\bigl(n(1-P)\bigr)/(1+P)(n(1−P))/(1+P), then minus 111, then times Pa∣bcP_{a|bc}Pa∣bc​. Since 0<P<10<P<10<P<1, the denominator 1+P1+P1+P is never zero, so no division-by-zero junk value arises. The inequality is strict (>>>), not ≥\ge≥, and (i) and (ii) are joined by conjunction, so both must hold simultaneously.

Degenerate cases silently excluded by 3≤n3 \le n3≤n: n=0n = 0n=0 (type Fin 1, where a=b=c=0a=b=c=0a=b=c=0 collapse), n=1n=1n=1 (where b=c=1b=c=1b=c=1), and n=2n=2n=2. No hypothesis beyond 3≤n3 \le n3≤n, 0<P0<P0<P, P<1P<1P<1 is imposed; these are jointly satisfiable, so the statement is not vacuous. The declaration's proof is a placeholder (sorry).

Numerical testing of both conjuncts

Computed by #eval in Lean over exact rationals (scratch file since deleted), and independently reproduced by an exact-fraction brute force in Python. The two agree digit for digit at every shared point. Total coverage: n∈{0,1,2,…,12}n \in \{0,1,2,\dots,12\}n∈{0,1,2,…,12} against P∈{1100,120,110,15,14,13,25,12,35,23,710,45,910,99100}P \in \{\tfrac1{100},\tfrac1{20},\tfrac1{10},\tfrac15,\tfrac14,\tfrac13,\tfrac25,\tfrac12,\tfrac35,\tfrac23,\tfrac7{10},\tfrac45,\tfrac9{10},\tfrac{99}{100}\}P∈{1001​,201​,101​,51​,41​,31​,52​,21​,53​,32​,107​,54​,109​,10099​} plus a tiny-PPP sweep down to P=10−9P=10^{-9}P=10−9 and a 200-point scan of P∈(0,n−1n+1)P\in(0,\tfrac{n-1}{n+1})P∈(0,n+1n−1​) for n=3,4,5n=3,4,5n=3,4,5.

Conjunct (i), Pab∣c=Pac∣bP_{ab|c} = P_{ac|b}Pab∣c​=Pac∣b​: HOLDS at every point tested, as an identity of exact rationals — including at n=0,1,2n=0,1,2n=0,1,2 outside the hypothesis. E.g. n=3,P=12n=3,P=\tfrac12n=3,P=21​: both =316=\tfrac{3}{16}=163​; n=4,P=13n=4,P=\tfrac13n=4,P=31​: both =136729=\tfrac{136}{729}=729136​; n=5,P=25n=5,P=\tfrac25n=5,P=52​: both =3974581953125=\tfrac{397458}{1953125}=1953125397458​.

Conjunct (ii), the strict inequality: HOLDS at every point tested with n≥1n \ge 1n≥1. The requested points:

nnnPPPLHS =PabcPa∣b∣c−Pab∣cPac∣b= P_{abc}P_{a\vert b\vert c}-P_{ab\vert c}P_{ac\vert b}=Pabc​Pa∣b∣c​−Pab∣c​Pac∣b​RHSverdict
31/23/128≈2.344×10−23/128 \approx 2.344\times10^{-2}3/128≈2.344×10−2000 (coefficient vanishes)HOLDS
31/3272/59049≈4.606×10−3272/59049 \approx 4.606\times10^{-3}272/59049≈4.606×10−31/486≈2.058×10−31/486 \approx 2.058\times10^{-3}1/486≈2.058×10−3HOLDS
32/5≈9.909×10−3\approx 9.909\times10^{-3}≈9.909×10−364/21875≈2.926×10−364/21875 \approx 2.926\times10^{-3}64/21875≈2.926×10−3HOLDS
41/2≈8.606×10−3\approx 8.606\times10^{-3}≈8.606×10−31/384≈2.604×10−31/384 \approx 2.604\times10^{-3}1/384≈2.604×10−3HOLDS
41/31184/1594323≈7.426×10−41184/1594323 \approx 7.426\times10^{-4}1184/1594323≈7.426×10−41/2187≈4.572×10−41/2187 \approx 4.572\times10^{-4}1/2187≈4.572×10−4HOLDS
42/5≈2.303×10−3\approx 2.303\times10^{-3}≈2.303×10−3≈1.170×10−3\approx 1.170\times10^{-3}≈1.170×10−3HOLDS
51/2≈2.815×10−3\approx 2.815\times10^{-3}≈2.815×10−31/768≈1.302×10−31/768 \approx 1.302\times10^{-3}1/768≈1.302×10−3HOLDS
51/3≈1.080×10−4\approx 1.080\times10^{-4}≈1.080×10−41/13122≈7.621×10−51/13122 \approx 7.621\times10^{-5}1/13122≈7.621×10−5HOLDS
52/5≈4.814×10−4\approx 4.814\times10^{-4}≈4.814×10−44096/13671875≈2.996×10−44096/13671875 \approx 2.996\times10^{-4}4096/13671875≈2.996×10−4HOLDS

No counterexample was found anywhere: 0 failures out of the ~130 (n,P)(n,P)(n,P) pairs tested. No critical finding to report.

Equality check. Within 3≤n3 \le n3≤n the two sides were never equal at any tested point (compared as exact rationals). The single equality observed anywhere was at n=0n = 0n=0, P=1/2P = 1/2P=1/2, where LHS === RHS =0= 0=0 (there a=b=ca=b=ca=b=c, so Pabc=1P_{abc}=1Pabc​=1 and the other four vanish); that point is excluded by 3≤n3 \le n3≤n, and the inequality already holds at n=1n=1n=1 and n=2n=2n=2.

Can the RHS be negative? Yes. The coefficient n(1−P)1+P−1\frac{n(1-P)}{1+P}-11+Pn(1−P)​−1 is negative exactly when P>n−1n+1P > \frac{n-1}{n+1}P>n+1n−1​, and exactly 000 at P=n−1n+1P = \frac{n-1}{n+1}P=n+1n−1​ (hit at rational test points: n=3,P=12n=3,P=\tfrac12n=3,P=21​; n=4,P=35n=4,P=\tfrac35n=4,P=53​; n=5,P=23n=5,P=\tfrac23n=5,P=32​). So the RHS is:

  • =0=0=0 at P=n−1n+1P=\frac{n-1}{n+1}P=n+1n−1​, where the claim degenerates to "LHS >0>0>0";
  • <0<0<0 for P>n−1n+1P>\frac{n-1}{n+1}P>n+1n−1​, where the claim is weak — e.g. n=3,P=99100n=3,P=\tfrac{99}{100}n=3,P=10099​: LHS ≈5.62×10−4\approx 5.62\times10^{-4}≈5.62×10−4 versus RHS ≈−0.937\approx -0.937≈−0.937; n=12,P=910n=12,P=\tfrac9{10}n=12,P=109​: LHS ≈4.88×10−2\approx 4.88\times10^{-2}≈4.88×10−2 versus RHS ≈−3.27×10−2\approx -3.27\times10^{-2}≈−3.27×10−2. Throughout this upper range the bound says little beyond positivity of the LHS.

Strength where the bound bites (P<n−1n+1P<\frac{n-1}{n+1}P<n+1n−1​, RHS >0>0>0). It is close to sharp, from both directions:

  • as P→0+P \to 0^+P→0+ at fixed nnn, the ratio LHS/RHS →1\to 1→1 from above, linearly in PPP: ratio −1≈1.5P-1 \approx 1.5P−1≈1.5P for n=3n=3n=3, ≈1.0P\approx 1.0P≈1.0P for n=4n=4n=4, ≈0.75P\approx 0.75P≈0.75P for n=5n=5n=5 (verified with exact fractions down to P=10−9P=10^{-9}P=10−9; always strictly >1>1>1). A 200-point scan found minimum ratios 1.00381.00381.0038 (n=3n=3n=3), 1.00301.00301.0030 (n=4n=4n=4), 1.00251.00251.0025 (n=5n=5n=5), all at small PPP.
  • at fixed PPP with growing nnn, the ratio also decreases toward 111, roughly like 1+c(P)/n1+c(P)/n1+c(P)/n: at P=110P=\tfrac1{10}P=101​, ratios for n=3,…,12n=3,\dots,12n=3,…,12 are 1.176, 1.113, 1.083, 1.066, 1.054, 1.046, 1.040, 1.036, 1.032, 1.0291.176,\,1.113,\,1.083,\,1.066,\,1.054,\,1.046,\,1.040,\,1.036,\,1.032,\,1.0291.176,1.113,1.083,1.066,1.054,1.046,1.040,1.036,1.032,1.029; at P=12P=\tfrac12P=21​ they are (from n=4n=4n=4) 3.305, 2.162, 1.777, 1.583, 1.467, 1.389, 1.333, 1.292, 1.2593.305,\,2.162,\,1.777,\,1.583,\,1.467,\,1.389,\,1.333,\,1.292,\,1.2593.305,2.162,1.777,1.583,1.467,1.389,1.333,1.292,1.259.
  • largest observed slack is near the zero of the coefficient (e.g. n=6,P=0.7n=6,P=0.7n=6,P=0.7: ratio ≈15.9\approx 15.9≈15.9).

So for large nnn the inequality is neither vacuous nor loose in relative terms — it is asymptotically tight — but both sides are exponentially small in nnn: numerically Pa∣bc=P2n−1P_{a|bc} = P^{2n-1}Pa∣bc​=P2n−1 exactly at every one of the ~130 points tested (e.g. 1/321/321/32 at n=3,P=12n=3,P=\tfrac12n=3,P=21​; 1/21871/21871/2187 at n=4,P=13n=4,P=\tfrac13n=4,P=31​; 512/1953125512/1953125512/1953125 at n=5,P=25n=5,P=\tfrac25n=5,P=52​), so the RHS equals (n(1−P)1+P−1)P2n−1\bigl(\frac{n(1-P)}{1+P}-1\bigr)P^{2n-1}(1+Pn(1−P)​−1)P2n−1 and decays geometrically.

Scratch file /Users/michael/Documents/misc/prove2me_workspace/Solutions/AuditL41.lean was created, evaluated, and deleted; its build artifacts were removed and the working tree is clean of it. (Note, unrelated to my work: Solutions/AuditL51.lean and Solutions/AuditL52.lean, present at session start as untracked files, disappeared during this session — presumably cleaned up by a concurrent process.)

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