Proposition 5.4 — partition-probability bound for
ProvedBunkbedFalse.gadget_partition_boundCombining the three preceding computations for the gadget graph (, ): first,
and second, the quantity controlling how faithfully simulates a hyperedge satisfies
Here the five quantities are the probabilities that the percolation partitions the triple , , 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 by taking large, which is exactly what the robust hyperedge lemma requires.
Formalization Note The inequality is stated with , as in the source; Lemma 4.1 then derives the strict form.
import Definitions.Def_BunkbedHypergraph open Bunkbed Bunkbed.Hyper SimpleGraph Finset
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 BunkbedFalseRead-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 (nothing here is Mathlib's; there is no measure theory involved).
Weighted Bernoulli bond percolation. For a finite vertex type with decidable equality, a finite edge set (unordered pairs), and a weight function on unordered pairs, the weight of a configuration is
and for a decidable event on configurations, — a finite sum over the full power set of . Connectivity " in " means and lie in the same component of the graph whose edge set is exactly (reflexive: every vertex is connected to itself). Note that is a formal polynomial in the weights; it is a probability distribution only because the weights used below happen to lie in .
The gadget . For the vertex set is (i.e. ), written and . Its edge set consists of
- the spokes for , and
- the path edges for ,
so (verified computationally: for ). The graph is a star centred at with a Hamiltonian path threaded through the leaves; there is no edge .
The weights . An edge gets weight if it contains the vertex (exactly the spokes) and weight otherwise (exactly the path edges). So each spoke is open with probability and closed with probability ; each path edge is open with probability .
The five partition probabilities of a triple . Each is the probability, in the above percolation, of one of the five ways can be partitioned by the component structure:
These five events are mutually exclusive and exhaustive, and I confirmed numerically that the five values sum to exactly at every tested point.
What the theorem asserts
For every natural number and every rational satisfying , , and , the following two statements both hold, taken with respect to the gadget with the spoke/path weights and the distinguished triple
Conjunct 1 (an exact identity, using only ):
Spelled out: the probability that and are connected while the hub is not connected to equals . (Combinatorially this is the event that all path edges are open and all spokes are closed, of probability ; any other route from to passes through and so violates .)
Conjunct 2 (a non-strict lower bound on a determinant-shaped expression, using the other four quantities):
The left side is . On the order of factors: the first product is written and the subtracted product is written (the "" 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, has a graph automorphism reversing the path (, fixing ) which swaps the roles of and and preserves the weights, so identically here — confirmed numerically at every tested point — making the subtracted term a perfect square and rendering any asymmetry in that product moot for this particular graph.
On the distribution of the five quantities across the statement: 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: is exact rational division ( under the hypotheses, so no division-by-zero junk value arises), is the natural number cast into , and the exponent is truncated natural-number subtraction — harmless here because forces . The bracketed coefficient is negative whenever , i.e. whenever ; in that regime the whole right-hand side is negative and the inequality is a weak (and for large , essentially vacuous) bound. Degenerate readings excluded by the hypotheses: (where and could coincide, or the triple could degenerate — at one has , and at one has ), and the boundary weights and . 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 )
I evaluated both sides exactly for and as instructed, then extended the sweep to and up to .
Conjunct 1: HOLDS exactly at every tested point, with no slack — it is an identity, as claimed. Representative values:
| verdict | ||||
|---|---|---|---|---|
| 3 | HOLDS (equality) | |||
| 4 | HOLDS (equality) | |||
| 5 | HOLDS (equality) | |||
| 3 | HOLDS (equality) | |||
| 4 | HOLDS (equality) | |||
| 5 | HOLDS (equality) | |||
| 3 | HOLDS (equality) | |||
| 4 | HOLDS (equality) | |||
| 5 | HOLDS (equality) |
Conjunct 2: HOLDS at every tested point, never tight (always strictly slack). Representative values:
| LHS | RHS | verdict | ||
|---|---|---|---|---|
| 3 | HOLDS, slack | |||
| 4 | HOLDS, slack | |||
| 5 | HOLDS, slack | |||
| 3 | HOLDS, slack | |||
| 4 | HOLDS, slack | |||
| 5 | HOLDS, slack | |||
| 3 | HOLDS, slack | |||
| 4 | HOLDS, slack | |||
| 5 | HOLDS, slack |
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 : e.g. gives RHS against LHS ; gives RHS against LHS . 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 (RHS exactly at , e.g. and ).
- The bound is asymptotically tight as , and this is where it is least slack. Normalising by : the LHS ratio and the RHS coefficient both tend to , with the LHS ratio staying just above. For : at , ratio vs coefficient ; at , vs . For : at , vs . For : at , vs . So the margin shrinks toward zero as but I found no crossing; the inequality is never an equality at any point I tested, so the non-strict is not attained in the tested range (it is only approached in the limit, which the hypothesis excludes).
Degenerate- note (outside the hypotheses, reported only for completeness): at Conjunct 1 is false — while by truncated subtraction — so the hypothesis is doing real work and is not merely cosmetic. At both conjuncts happen to hold at every point I tested. The hypotheses , , are all satisfiable (all nine primary test points satisfy them), so the theorem is not vacuous.
Confirmed by the mission captain (proposal self-audit).