Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5.4 — partition-probability bound for GnG_nGn​

Proved
BunkbedFalse.gadget_partition_bound

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

combinatoricsgraph-theorypercolationprobability

Combining the three preceding computations for the gadget graph GnG_nGn​ (n≥3n \ge 3n≥3, 0<P<10 < P < 10<P<1): first,

Pa∣bc  =  P2n−1,P_{a|bc} \;=\; P^{2n-1},Pa∣bc​=P2n−1,

and second, the quantity controlling how faithfully GnG_nGn​ simulates a hyperedge satisfies

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

Here the five quantities are the probabilities that the percolation partitions the triple a=0a = 0a=0, b=v1b = v_1b=v1​, c=vnc = v_nc=vn​ in each of the five possible ways. The point of the bound is that the left-hand side can be made arbitrarily large relative to Pa∣bcP_{a|bc}Pa∣bc​ by taking nnn large, which is exactly what the robust hyperedge lemma requires.

Formalization Note The inequality is stated with ≥\ge≥, as in the source; Lemma 4.1 then derives the strict form.

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

/-- **Proposition 5.4** (p. 8). -/
theorem gadget_partition_bound (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) ∧
    Pabc (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) * Pa_b_c (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) - Pac_b (gadgetE n) (gadgetW n P) 0 1 (Fin.last n) * Pab_c (gadgetE n) (gadgetW n P) 0 1 (Fin.last n)
      ≥ (n * (1 - P) / (1 + P) - 1) * 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, Proposition 5.4.
Read-back

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

Read-back: BunkbedFalse.gadget_partition_bound

The ambient objects

All vocabulary is drawn from the percolation bundle, which builds everything from scratch over Q\mathbb{Q}Q (nothing here is Mathlib's; there is no measure theory involved).

Weighted Bernoulli bond percolation. For a finite vertex type VVV with decidable equality, a finite edge set E⊆(V2)E \subseteq \binom{V}{2}E⊆(2V​) (unordered pairs), and a weight function www on unordered pairs, the weight of a configuration S⊆ES \subseteq ES⊆E is

wt(S)  =  (∏e∈Sw(e))(∏e∈E∖S(1−w(e))),\mathrm{wt}(S) \;=\; \Big(\prod_{e \in S} w(e)\Big)\Big(\prod_{e \in E \setminus S} (1 - w(e))\Big),wt(S)=(e∈S∏​w(e))(e∈E∖S∏​(1−w(e))),

and for a decidable event AAA on configurations, P[A]=∑S⊆E1[S∈A] wt(S)\mathbb{P}[A] = \sum_{S \subseteq E} \mathbf{1}[S \in A]\,\mathrm{wt}(S)P[A]=∑S⊆E​1[S∈A]wt(S) — a finite sum over the full power set of EEE. Connectivity "u↔vu \leftrightarrow vu↔v in SSS" means uuu and vvv lie in the same component of the graph whose edge set is exactly SSS (reflexive: every vertex is connected to itself). Note that wt\mathrm{wt}wt is a formal polynomial in the weights; it is a probability distribution only because the weights used below happen to lie in (0,1)(0,1)(0,1).

The gadget GnG_nGn​. For n∈Nn \in \mathbb{N}n∈N the vertex set is {0,1,…,n}\{0, 1, \dots, n\}{0,1,…,n} (i.e. Fin(n+1)\mathrm{Fin}(n+1)Fin(n+1)), written a=0a = 0a=0 and v1,…,vn=1,…,nv_1, \dots, v_n = 1, \dots, nv1​,…,vn​=1,…,n. Its edge set E(Gn)E(G_n)E(Gn​) consists of

  • the nnn spokes {0,j}\{0, j\}{0,j} for j=1,…,nj = 1, \dots, nj=1,…,n, and
  • the n−1n-1n−1 path edges {i,i+1}\{i, i+1\}{i,i+1} for i=1,…,n−1i = 1, \dots, n-1i=1,…,n−1,

so ∣E(Gn)∣=2n−1|E(G_n)| = 2n - 1∣E(Gn​)∣=2n−1 (verified computationally: 5,7,95, 7, 95,7,9 for n=3,4,5n = 3, 4, 5n=3,4,5). The graph is a star centred at 000 with a Hamiltonian path threaded through the leaves; there is no edge {vn,v1}\{v_n, v_1\}{vn​,v1​}.

The weights wn,Pw_{n,P}wn,P​. An edge gets weight 1−P1 - P1−P if it contains the vertex 000 (exactly the spokes) and weight PPP otherwise (exactly the path edges). So each spoke is open with probability 1−P1-P1−P and closed with probability PPP; each path edge is open with probability PPP.

The five partition probabilities of a triple (a,b,c)(a,b,c)(a,b,c). Each is the probability, in the above percolation, of one of the five ways {a,b,c}\{a,b,c\}{a,b,c} can be partitioned by the component structure:

Pabc=P[ a↔b ∧ b↔c ](all three in one component)Pa∣bc=P[ b↔c ∧ a↮b ](b,c together, a apart)Pab∣c=P[ a↔b ∧ a↮c ](a,b together, c apart)Pac∣b=P[ a↔c ∧ a↮b ](a,c together, b apart)Pa∣b∣c=P[ a↮b ∧ b↮c ∧ a↮c ](all three separate)\begin{aligned} P_{abc} &= \mathbb{P}[\,a \leftrightarrow b \ \wedge\ b \leftrightarrow c\,] && \text{(all three in one component)}\\ P_{a|bc} &= \mathbb{P}[\,b \leftrightarrow c \ \wedge\ a \not\leftrightarrow b\,] && \text{($b,c$ together, $a$ apart)}\\ P_{ab|c} &= \mathbb{P}[\,a \leftrightarrow b \ \wedge\ a \not\leftrightarrow c\,] && \text{($a,b$ together, $c$ apart)}\\ P_{ac|b} &= \mathbb{P}[\,a \leftrightarrow c \ \wedge\ a \not\leftrightarrow b\,] && \text{($a,c$ together, $b$ apart)}\\ P_{a|b|c} &= \mathbb{P}[\,a \not\leftrightarrow b \ \wedge\ b \not\leftrightarrow c \ \wedge\ a \not\leftrightarrow c\,] && \text{(all three separate)} \end{aligned}Pabc​Pa∣bc​Pab∣c​Pac∣b​Pa∣b∣c​​=P[a↔b ∧ b↔c]=P[b↔c ∧ a↔b]=P[a↔b ∧ a↔c]=P[a↔c ∧ a↔b]=P[a↔b ∧ b↔c ∧ a↔c]​​(all three in one component)(b,c together, a apart)(a,b together, c apart)(a,c together, b apart)(all three separate)​

These five events are mutually exclusive and exhaustive, and I confirmed numerically that the five values sum to exactly 111 at every tested point.

What the theorem asserts

For every natural number nnn and every rational PPP satisfying 3≤n3 \le n3≤n, 0<P0 < P0<P, and P<1P < 1P<1, the following two statements both hold, taken with respect to the gadget GnG_nGn​ with the spoke/path weights wn,Pw_{n,P}wn,P​ and the distinguished triple

a=0,b=v1=1,c=vn=n(the last element of Fin(n+1)).a = 0, \qquad b = v_1 = 1, \qquad c = v_n = n \quad (\text{the last element of } \mathrm{Fin}(n+1)).a=0,b=v1​=1,c=vn​=n(the last element of Fin(n+1)).

Conjunct 1 (an exact identity, using only Pa∣bcP_{a|bc}Pa∣bc​):

Pa∣bc  =  P 2n−1.P_{a|bc} \;=\; P^{\,2n-1}.Pa∣bc​=P2n−1.

Spelled out: the probability that v1v_1v1​ and vnv_nvn​ are connected while the hub 000 is not connected to v1v_1v1​ equals P2n−1P^{2n-1}P2n−1. (Combinatorially this is the event that all n−1n-1n−1 path edges are open and all nnn spokes are closed, of probability Pn−1⋅Pn=P2n−1P^{n-1}\cdot P^{n} = P^{2n-1}Pn−1⋅Pn=P2n−1; any other route from v1v_1v1​ to vnv_nvn​ passes through 000 and so violates 0↮v10 \not\leftrightarrow v_10↔v1​.)

Conjunct 2 (a non-strict lower bound on a 2×22 \times 22×2 determinant-shaped expression, using the other four quantities):

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

The left side is det⁡(PabcPab∣cPac∣bPa∣b∣c)\det\begin{pmatrix} P_{abc} & P_{ab|c} \\ P_{ac|b} & P_{a|b|c}\end{pmatrix}det(Pabc​Pac∣b​​Pab∣c​Pa∣b∣c​​). On the order of factors: the first product is written Pabc⋅Pa∣b∣cP_{abc}\cdot P_{a|b|c}Pabc​⋅Pa∣b∣c​ and the subtracted product is written Pac∣b⋅Pab∣cP_{ac|b}\cdot P_{ab|c}Pac∣b​⋅Pab∣c​ (the "ac∣bac|bac∣b" factor first). Since these are rational numbers, multiplication is commutative and the written order carries no mathematical content; the only substantive choices are which four quantities are paired against which. As it happens, GnG_nGn​ has a graph automorphism reversing the path (vi↦vn+1−iv_i \mapsto v_{n+1-i}vi​↦vn+1−i​, fixing 000) which swaps the roles of bbb and ccc and preserves the weights, so Pab∣c=Pac∣bP_{ab|c} = P_{ac|b}Pab∣c​=Pac∣b​ identically here — confirmed numerically at every tested point — making the subtracted term a perfect square Pab∣c2P_{ab|c}^2Pab∣c2​ and rendering any b/cb/cb/c asymmetry in that product moot for this particular graph.

On the distribution of the five quantities across the statement: Pa∣bcP_{a|bc}Pa∣bc​ occurs only in Conjunct 1 and not in Conjunct 2; Conjunct 2 uses the remaining four and none of them appears in Conjunct 1. So all five occur across the conjunction, but no quantity occurs in both conjuncts.

On the right-hand side: n(1−P)1+P\frac{n(1-P)}{1+P}1+Pn(1−P)​ is exact rational division (1+P>01+P > 01+P>0 under the hypotheses, so no division-by-zero junk value arises), nnn is the natural number nnn cast into Q\mathbb{Q}Q, and the exponent 2n−12n-12n−1 is truncated natural-number subtraction — harmless here because 3≤n3 \le n3≤n forces 2n−1≥52n-1 \ge 52n−1≥5. The bracketed coefficient is negative whenever n(1−P)<1+Pn(1-P) < 1+Pn(1−P)<1+P, i.e. whenever P>n−1n+1P > \frac{n-1}{n+1}P>n+1n−1​; in that regime the whole right-hand side is negative and the inequality is a weak (and for large PPP, essentially vacuous) bound. Degenerate readings excluded by the hypotheses: n∈{0,1,2}n \in \{0,1,2\}n∈{0,1,2} (where bbb and ccc could coincide, or the triple could degenerate — at n=1n=1n=1 one has c=v1=bc = v_1 = bc=v1​=b, and at n=0n=0n=0 one has b=c=a=0b = c = a = 0b=c=a=0), and the boundary weights P=0P = 0P=0 and P=1P = 1P=1. The theorem is stated with its proof left as sorry, so nothing is verified by the Lean kernel; what follows is my own independent numerical check.

Numerical verification (both conjuncts, computed exactly over Q\mathbb{Q}Q)

I evaluated both sides exactly for n∈{3,4,5}n \in \{3,4,5\}n∈{3,4,5} and P∈{1/2,1/3,2/5}P \in \{1/2, 1/3, 2/5\}P∈{1/2,1/3,2/5} as instructed, then extended the sweep to P∈{1/1000,1/200,1/50,1/20,1/10,1/5,1/4,1/3,2/5,1/2,3/5,7/10,4/5,9/10,19/20,99/100}P \in \{1/1000, 1/200, 1/50, 1/20, 1/10, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 7/10, 4/5, 9/10, 19/20, 99/100\}P∈{1/1000,1/200,1/50,1/20,1/10,1/5,1/4,1/3,2/5,1/2,3/5,7/10,4/5,9/10,19/20,99/100} and nnn up to 666.

Conjunct 1: HOLDS exactly at every tested point, with no slack — it is an identity, as claimed. Representative values:

nnnPPPPa∣bcP_{a\mid bc}Pa∣bc​P2n−1P^{2n-1}P2n−1verdict
31/21/21/21/321/321/321/321/321/32HOLDS (equality)
41/21/21/21/1281/1281/1281/1281/1281/128HOLDS (equality)
51/21/21/21/5121/5121/5121/5121/5121/512HOLDS (equality)
31/31/31/31/2431/2431/2431/2431/2431/243HOLDS (equality)
41/31/31/31/21871/21871/21871/21871/21871/2187HOLDS (equality)
51/31/31/31/196831/196831/196831/196831/196831/19683HOLDS (equality)
32/52/52/532/312532/312532/312532/312532/312532/3125HOLDS (equality)
42/52/52/5128/78125128/78125128/78125128/78125128/78125128/78125HOLDS (equality)
52/52/52/5512/1953125512/1953125512/1953125512/1953125512/1953125512/1953125HOLDS (equality)

Conjunct 2: HOLDS at every tested point, never tight (always strictly slack). Representative values:

nnnPPPLHSRHSverdict
31/21/21/23/1283/1283/128000HOLDS, slack 3/1283/1283/128
41/21/21/2141/16384141/16384141/163841/3841/3841/384HOLDS, slack 295/49152295/49152295/49152
51/21/21/2369/131072369/131072369/1310721/7681/7681/768HOLDS, slack 595/393216595/393216595/393216
31/31/31/3272/59049272/59049272/590491/4861/4861/486HOLDS, slack 301/118098301/118098301/118098
41/31/31/31184/15943231184/15943231184/15943231/21871/21871/2187HOLDS, slack 455/1594323455/1594323455/1594323
51/31/31/341824/38742048941824/38742048941824/3874204891/131221/131221/13122HOLDS, slack 24599/77484097824599/77484097824599/774840978
32/52/52/596768/976562596768/976562596768/976562564/2187564/2187564/21875HOLDS, slack 477376/68359375477376/68359375477376/68359375
42/52/52/514055552/610351562514055552/610351562514055552/6103515625128/109375128/109375128/109375HOLDS, slack 48388864/4272460937548388864/4272460937548388864/42724609375
52/52/52/51836205056/38146972656251836205056/38146972656251836205056/38146972656254096/136718754096/136718754096/13671875HOLDS, slack 4853435392/267028808593754853435392/267028808593754853435392/26702880859375

No counterexample was found anywhere in the tested range. Two further observations relevant to the strength of the bound:

  • The right-hand side does go negative, exactly as the algebra predicts, whenever P>n−1n+1P > \frac{n-1}{n+1}P>n+1n−1​: e.g. n=3,P=3/5n=3, P=3/5n=3,P=3/5 gives RHS =−243/12500<0= -243/12500 < 0=−243/12500<0 against LHS =412128/9765625>0= 412128/9765625 > 0=412128/9765625>0; n=3,P=99/100n=3, P=99/100n=3,P=99/100 gives RHS ≈−0.937\approx -0.937≈−0.937 against LHS ≈5.6×10−4\approx 5.6\times 10^{-4}≈5.6×10−4. In that whole regime the bound is essentially vacuous, since the left side is empirically non-negative at every point tested while the right side is negative. The inequality has real content only for P<n−1n+1P < \frac{n-1}{n+1}P<n+1n−1​ (RHS =0= 0=0 exactly at P=n−1n+1P = \frac{n-1}{n+1}P=n+1n−1​, e.g. n=3,P=1/2n=3, P=1/2n=3,P=1/2 and n=4,P=3/5n=4, P=3/5n=4,P=3/5).
  • The bound is asymptotically tight as P→0+P \to 0^+P→0+, and this is where it is least slack. Normalising by P2n−1P^{2n-1}P2n−1: the LHS ratio and the RHS coefficient n(1−P)1+P−1\frac{n(1-P)}{1+P}-11+Pn(1−P)​−1 both tend to n−1n-1n−1, with the LHS ratio staying just above. For n=3n=3n=3: at P=1/1000P=1/1000P=1/1000, ratio 1.9970011.9970011.997001 vs coefficient 1.9940061.9940061.994006; at P=1/50P=1/50P=1/50, 1.9404081.9404081.940408 vs 1.8823531.8823531.882353. For n=5n=5n=5: at P=1/1000P=1/1000P=1/1000, 3.9930053.9930053.993005 vs 3.9900103.9900103.990010. For n=6n=6n=6: at P=1/1000P=1/1000P=1/1000, 4.9910074.9910074.991007 vs 4.9880124.9880124.988012. So the margin shrinks toward zero as P→0P \to 0P→0 but I found no crossing; the inequality is never an equality at any point I tested, so the non-strict ≥\ge≥ is not attained in the tested range (it is only approached in the P→0P \to 0P→0 limit, which the hypothesis 0<P0 < P0<P excludes).

Degenerate-nnn note (outside the hypotheses, reported only for completeness): at n=0n = 0n=0 Conjunct 1 is false — Pa∣bc=0P_{a|bc} = 0Pa∣bc​=0 while P2⋅0−1=P0=1P^{2\cdot 0 - 1} = P^{0} = 1P2⋅0−1=P0=1 by truncated subtraction — so the hypothesis 3≤n3 \le n3≤n is doing real work and is not merely cosmetic. At n=1,2n = 1, 2n=1,2 both conjuncts happen to hold at every point I tested. The hypotheses 3≤n3 \le n3≤n, 0<P0 < P0<P, P<1P < 1P<1 are all satisfiable (all nine primary test points satisfy them), so the theorem is not vacuous.

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