binary_partial_word_cube_volume_bound
The sum of 2 to the negative support sizes of pairwise conflicting finite partial words is at most one.
Statement
theorem binary_partial_word_cube_volume_bound {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) : ∑ i, (1 : ℚ) / 2 ^ (s i).card ≤ 1
- 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 1
- binary_partial_word_cube_packingPairwise conflicting partial words pack disjoint cubes into the full Boolean cube, bounding the sum of their cardinalities.
- Used by 1
- binary_partial_word_cube_minimum_incidenceFor pairwise conflicting finite partial words, if total support size plus 2^m equals the number of words times m+1, then their volume sum…
The proof, explained
The pairwise conflicting partial words define pairwise disjoint subcubes within the boolean hypercube {0, 1}^V. By the packing theorem `binary_partial_word_cube_packing`, the sum of their cardinalities ∑ i, 2^(|V| - |s(i)|) is at most the total hypercube size 2^|V|. Factoring out 2^|V| expresses each term as 2^|V| * 2^(-|s(i)|). Dividing both sides of the inequality by the strictly positive factor 2^|V| yields ∑ i, 1 / 2^|s(i)| ≤ 1.
The sum of the subcube sizes is at most 2^|V|: ∑ i, 2^(|V| - |s(i)|) ≤ 2^|V|.
Apply the cube packing theorem `binary_partial_word_cube_packing` to the conflicting partial words, which guarantees that their disjoint subcubes cannot cover more vertices than the full hypercube {0, 1}^V.
uses
binary_partial_word_cube_packinghave hpack := binary_partial_word_cube_packing s b hconflictFor each index i, 2^(|V| - |s(i)|) = 2^|V| * (1 / 2^|s(i)|).
Since 2 ≠ 0 and |s(i)| ≤ |V| by `card_le_univ`, the power rule `pow_sub₀` splits 2^(|V| - |s(i)|) into 2^|V| * (2^|s(i)|)⁻¹. Then `one_div` rewrites the multiplicative inverse as 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 packing bound simplifies to 2^|V| * ∑ i, (1 / 2^|s(i)|) ≤ 2^|V|.
Substitute the identity 2^(|V| - |s(i)|) = 2^|V| * (1 / 2^|s(i)|) into the packing sum, and factor out the common multiplier 2^|V| from the sum using `mul_sum`.
uses
mul_sumsimp_rw [he] at hpack rw [← mul_sum] at hpack
2^|V| > 0 in ℚ. automation
The power 2^|V| is strictly positive because 2 > 0, which `positivity` establishes automatically.
have hp : (0 : ℚ) < 2 ^ Fintype.card V := by positivity
∑ i, 1 / 2^|s(i)| ≤ 1. automation
Dividing both sides of 2^|V| * ∑ i, (1 / 2^|s(i)|) ≤ 2^|V| by the strictly positive quantity 2^|V| proves the desired inequality. The tactic `nlinarith` verifies this step of linear arithmetic.
nlinarith
binary_partial_word_cube_packing- For pairwise conflicting binary partial words on a finite coordinate type V, the sum of the subcube sizes 2^(|V| - |s(i)|) is at most the total hypercube size 2^|V|.
pow_sub₀- In a group with zero (such as ℚ), 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 α.
one_div- In a division monoid, 1 / a = a⁻¹.
mul_sum- Multiplication distributes over finite sums: a * ∑ i, f(i) = ∑ i, (a * f(i)).
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_volume_bound {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) : ∑ i, (1 : ℚ) / 2 ^ (s i).card ≤ 1 := by have hpack := binary_partial_word_cube_packing s b hconflict 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] simp_rw [he] at hpack rw [← mul_sum] at hpack have hp : (0 : ℚ) < 2 ^ Fintype.card V := by positivity nlinarith