binary_partial_word_cube_cover_of_volume_eq
Pairwise conflicting partial words whose rational volume sum is one cover the entire finite Boolean cube.
Statement
theorem binary_partial_word_cube_cover_of_volume_eq {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v) (hvolume : (∑ i, (1 : ℚ) / 2^(s i).card) = 1) : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ
- Source
- Reusable finite-cube and ordered-biclique helpers for the uniform OP-205 / RT-1 full-root-gap reduction following arXiv:2610.15635. The deficiency-one singular-coordinate/tree argument formalizes the Boolean setting of arXiv:1103.3693 Lemma 2.5.4 and Corollary 2.5.6; arXiv:2212.14685 Section 2.3 gives a related partition-size discussion. These are helper formalizations, not an original graph covering result; no advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- binary_partial_word_cubeThe finite Boolean cube determined by fixing the coordinates of a finite support to the values of a Boolean word.
- binary_partial_word_cube_cardA partial-word cube on a finite coordinate type has cardinality two to the number of coordinates outside its support.
- binary_partial_word_cube_disjointTwo partial-word cubes with a conflicting supported coordinate are disjoint.
- Used by 1
- ordered_biclique_minimum_incidence_intervalsLet g be positive and take g-1 bicliques indexed by cuts r+1 of the ordered set Fin g, with the first side strictly above r and the second…
The proof, explained
The theorem shows that pairwise conflicting partial words whose rational volumes sum to 1 cover the entire Boolean cube {0, 1}^V. Because distinct partial words conflict on some coordinate, their induced subcubes are mutually disjoint. To show their union is the entire space, it suffices to check that the sum of their cardinalities equals 2^|V|. Factoring 2^|V| out of the sum of sizes 2^(|V| - |s_i|) leaves 2^|V| times the sum of volumes, which equals 2^|V| * 1 = 2^|V| by the volume hypothesis.
The partial word cubes corresponding to distinct indices are pairwise disjoint.
By the hypothesis `hconflict`, any two distinct indices i ≠ j have some coordinate v in s i ∩ s j where their bit assignments b i v and b j v disagree. Applying `binary_partial_word_cube_disjoint` shows that the corresponding subcubes are disjoint.
uses
binary_partial_word_cube_disjointclassical have hdis : (↑(univ : Finset I) : Set I).PairwiseDisjoint (fun i => binary_partial_word_cube (s i) (b i)) := by intro i hi j hj hij exact binary_partial_word_cube_disjoint _ _ _ _ (hconflict i j hij)
To show the cubes cover the universe, it suffices to prove that ∑ i, 2^(|V| - |s i|) = 2^|V|.
By `eq_univ_of_card`, a subset of the Boolean cube (V → Bool) equals the entire universe if their cardinalities match. Since the cubes are pairwise disjoint, `card_biUnion` expresses the size of their union as the sum of their sizes. Each subcube has size 2^(|V| - |s i|) by `binary_partial_word_cube_card`, and the total space has size 2^|V| by `Fintype.card_fun` and `Fintype.card_bool`.
uses
eq_univ_of_card,card_biUnion,binary_partial_word_cube_card,Fintype.card_fun,Fintype.card_boolapply eq_univ_of_card rw [card_biUnion hdis] simp only [binary_partial_word_cube_card, Fintype.card_fun, Fintype.card_bool]
For each index i, 2^(|V| - |s i|) = 2^|V| * (1 / 2^|s i|) in the rational numbers.
Using `pow_sub₀` with exponent inequality |s i| ≤ |V| from `card_le_univ` and 2 ≠ 0, 2^(|V| - |s i|) rewrites to 2^|V| * (2^|s i|)⁻¹. Applying `one_div` replaces the inverse with 1 / 2^|s i|.
uses
pow_sub₀,card_le_univ,one_divhave he (i : I) : (2 : ℚ) ^ (Fintype.card V - (s i).card) = 2 ^ Fintype.card V * (1 / 2 ^ (s i).card) := by rw [pow_sub₀ _ (by norm_num) (card_le_univ _)] simp only [one_div]
The sum of subcube sizes equals 2^|V| in the rational numbers.
Substituting the rewritten form of each term into the sum and factoring out 2^|V| via `mul_sum` gives 2^|V| * ∑ i, (1 / 2^|s i|). By the volume hypothesis `hvolume`, the sum of fractions is 1, so the product evaluates to 2^|V| by `mul_one`.
uses
mul_sum,mul_onehave hq : (∑ i, (2 : ℚ)^(Fintype.card V - (s i).card)) = 2^Fintype.card V := by simp_rw [he] rw [← mul_sum, hvolume, mul_one]
The sum equality holds in the natural numbers, concluding the proof.
The tactic `exact_mod_cast` coerces the equality proved over ℚ back to the natural numbers, fulfilling the cardinality requirement.
exact_mod_cast hq
binary_partial_word_cube_disjoint- Two partial word cubes are disjoint if there is a coordinate in both their domains where their assigned bit values disagree.
eq_univ_of_card- A subset of a finite type equals the entire universe if and only if its cardinality equals the cardinality of the type.
card_biUnion- The cardinality of a disjoint union of finite sets is the sum of their individual cardinalities.
binary_partial_word_cube_card- The cardinality of the partial word cube defined on a subset of coordinates s is 2^(|V| - |s|).
Fintype.card_fun- The cardinality of the function type α → β is |β|^|α|.
Fintype.card_bool- The boolean type Bool has cardinality 2.
pow_sub₀- In a group with zero, a^(m - n) = a^m * (a^n)⁻¹ whenever a ≠ 0 and n ≤ m.
card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the entire type.
one_div- Division 1 / a equals the multiplicative inverse a⁻¹.
mul_sum- Multiplication distributes over finite sums from the left: a * ∑ i, f i = ∑ i, a * f i.
mul_one- Multiplying any element by 1 leaves it unchanged.
- The summation is evaluated over the rational numbers ℚ to express subcube sizes as fractional volumes and invoke the hypothesis, after which `exact_mod_cast` translates the result back to natural number cardinality.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem binary_partial_word_cube_cover_of_volume_eq {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v) (hvolume : (∑ i, (1 : ℚ) / 2^(s i).card) = 1) : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ := by classical have hdis : (↑(univ : Finset I) : Set I).PairwiseDisjoint (fun i => binary_partial_word_cube (s i) (b i)) := by intro i hi j hj hij exact binary_partial_word_cube_disjoint _ _ _ _ (hconflict i j hij) apply eq_univ_of_card rw [card_biUnion hdis] simp only [binary_partial_word_cube_card, Fintype.card_fun, Fintype.card_bool] have he (i : I) : (2 : ℚ) ^ (Fintype.card V - (s i).card) = 2 ^ Fintype.card V * (1 / 2 ^ (s i).card) := by rw [pow_sub₀ _ (by norm_num) (card_le_univ _)] simp only [one_div] have hq : (∑ i, (2 : ℚ)^(Fintype.card V - (s i).card)) = 2^Fintype.card V := by simp_rw [he] rw [← mul_sum, hvolume, mul_one] exact_mod_cast hq