Lemma 4.1 — hyperedge simulation by the gadget
ProvedBunkbedFalse.hyperedge_simulationLet and , and consider the weighted gadget graph on vertices, with and . Then the two "mixed" partition probabilities agree,
and
This is the hyperedge simulation lemma. A single -hyperedge cannot be simulated exactly by bond percolation on any graph, so the strategy is instead to show that simulates one well enough: the displayed inequality says the simulation error can be driven below any prescribed threshold by increasing . Taking and makes the right-hand side exceed the factor demanded by the robust hyperedge lemma, which is what produces the counterexample.
Formalization Note The five partition probabilities are those of the triple , , in . The symmetry reflects the reflection symmetry of exchanging and .
import Definitions.Def_BunkbedHypergraph open Bunkbed Bunkbed.Hyper SimpleGraph Finset
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 BunkbedFalseRead-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 and a rational number . The statement concerns a fixed finite graph and a Bernoulli bond percolation on it.
The graph . Its vertex set is (the type Fin (n+1)). Its edge set consists of exactly
- the spokes for every with (all edges meeting the vertex ), and
- the path edges for every with .
So is a fan: a hub joined to every vertex of a path . It has edges. (Verified by evaluation: , .)
The percolation measure. Each edge is open independently, with
Formally, a set of open edges carries weight , and the probability of an event is the sum of these weights over all in the power set of . Connectivity is measured in the simple graph whose edge set is exactly (all vertices present, isolated vertices allowed), and "" is reachability there, which is reflexive.
The distinguished triple. (the hub), (one end of the path), (the other end, Fin.last n).
The five probabilities, all in the above measure on :
Note the exact literal form of each event: conjoins with (not ); and are both phrased relative to the hub and each carries a single negation; carries all three negations. These five events do partition the configuration space (numerically confirmed: the five values sum to exactly at every point tested).
What the theorem asserts
For every natural number and every rational satisfying the three hypotheses
both of the following hold.
(i) An exact equality.
i.e. in the fan with spoke-probability and path-probability .
(ii) A strict inequality.
Here on the right is the natural number cast to , and the grouping is , then minus , then times . Since , the denominator is never zero, so no division-by-zero junk value arises. The inequality is strict (), not , and (i) and (ii) are joined by conjunction, so both must hold simultaneously.
Degenerate cases silently excluded by : (type Fin 1, where collapse), (where ), and . No hypothesis beyond , , 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: against plus a tiny- sweep down to and a 200-point scan of for .
Conjunct (i), : HOLDS at every point tested, as an identity of exact rationals — including at outside the hypothesis. E.g. : both ; : both ; : both .
Conjunct (ii), the strict inequality: HOLDS at every point tested with . The requested points:
| LHS | RHS | verdict | ||
|---|---|---|---|---|
| 3 | 1/2 | (coefficient vanishes) | HOLDS | |
| 3 | 1/3 | HOLDS | ||
| 3 | 2/5 | HOLDS | ||
| 4 | 1/2 | HOLDS | ||
| 4 | 1/3 | HOLDS | ||
| 4 | 2/5 | HOLDS | ||
| 5 | 1/2 | HOLDS | ||
| 5 | 1/3 | HOLDS | ||
| 5 | 2/5 | HOLDS |
No counterexample was found anywhere: 0 failures out of the ~130 pairs tested. No critical finding to report.
Equality check. Within the two sides were never equal at any tested point (compared as exact rationals). The single equality observed anywhere was at , , where LHS RHS (there , so and the other four vanish); that point is excluded by , and the inequality already holds at and .
Can the RHS be negative? Yes. The coefficient is negative exactly when , and exactly at (hit at rational test points: ; ; ). So the RHS is:
- at , where the claim degenerates to "LHS ";
- for , where the claim is weak — e.g. : LHS versus RHS ; : LHS versus RHS . Throughout this upper range the bound says little beyond positivity of the LHS.
Strength where the bound bites (, RHS ). It is close to sharp, from both directions:
- as at fixed , the ratio LHS/RHS from above, linearly in : ratio for , for , for (verified with exact fractions down to ; always strictly ). A 200-point scan found minimum ratios (), (), (), all at small .
- at fixed with growing , the ratio also decreases toward , roughly like : at , ratios for are ; at they are (from ) .
- largest observed slack is near the zero of the coefficient (e.g. : ratio ).
So for large the inequality is neither vacuous nor loose in relative terms — it is asymptotically tight — but both sides are exponentially small in : numerically exactly at every one of the ~130 points tested (e.g. at ; at ; at ), so the RHS equals 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.)
Confirmed by the mission captain (proposal self-audit).