binary_partial_word_cube_packing
Pairwise conflicting partial words pack disjoint cubes into the full Boolean cube, bounding the sum of their cardinalities.
Statement
theorem binary_partial_word_cube_packing {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, (2 : ℚ) ^ (Fintype.card V - (s i).card) ≤ 2 ^ Fintype.card V
- 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
- binary_partial_word_cube_volume_boundThe sum of 2 to the negative support sizes of pairwise conflicting finite partial words is at most one.
The proof, explained
Each partial word defines a subcube in the Boolean cube $\{0, 1\}^V$ of size $2^{|V| - |s(i)|}$. Since any two distinct partial words conflict at some coordinate, their corresponding subcubes are pairwise disjoint. The union of these disjoint subcubes is contained in the full cube of functions $V \to \{0, 1\}$, whose total size is $2^{|V|}$. Summing the sizes of the disjoint subcubes and casting from $\mathbb{N}$ to $\mathbb{Q}$ yields the bound.
The subcubes associated with distinct indices are pairwise disjoint.
Working classically, for any distinct indices $i \neq j \in I$, the conflict hypothesis `hconflict` provides a coordinate $v \in s(i) \cap s(j)$ on which $b(i)(v) \neq b(j)(v)$. By `binary_partial_word_cube_disjoint`, the corresponding subcubes are disjoint, establishing that the family of subcubes indexed by $I$ is pairwise 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)
The sum of the subcube cardinalities over all indices is at most $2^{|V|}$ in $\mathbb{N}$.
The union of all subcubes is contained in the universal set of functions $V \to \text{Bool}$ by `subset_univ`, so by `Finset.card_le_card`, the cardinality of the union is bounded by the cardinality of the full universe. Because the subcubes are pairwise disjoint, `Finset.card_biUnion` rewrites the cardinality of the union as the sum of their individual cardinalities. Finally, `binary_partial_word_cube_card` evaluates each subcube's size to $2^{|V| - |s(i)|}$, while `card_univ`, `Fintype.card_fun`, and `Fintype.card_bool` evaluate the size of the full Boolean cube to $2^{|V|}$.
uses
Finset.card_le_card,subset_univ,Finset.card_biUnion,binary_partial_word_cube_card,card_univ,Fintype.card_fun,Fintype.card_boolhave hc := Finset.card_le_card (show (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) ⊆ univ from subset_univ _) rw [Finset.card_biUnion hdis] at hc simp only [binary_partial_word_cube_card, card_univ, Fintype.card_fun, Fintype.card_bool] at hc
The inequality holds over the rational numbers.
Casting the natural-number inequality established in the previous step into $\mathbb{Q}$ completes the proof.
exact_mod_cast hc
binary_partial_word_cube_disjoint- Two subcubes defined by partial words $(s, b)$ and $(t, c)$ are disjoint if there is some variable in $s \cap t$ on which $b$ and $c$ assign different values.
Finset.card_le_card- If a finite set $s$ is a subset of $t$, then the cardinality of $s$ is at most the cardinality of $t$.
subset_univ- Every finite set of elements from a finite type is a subset of the universal finset `univ`.
Finset.card_biUnion- The cardinality of a union of pairwise disjoint finite sets is the sum of their individual cardinalities.
binary_partial_word_cube_card- The cardinality of the subcube determined by fixing the values of a partial word on a subset of coordinates $s \subseteq V$ is $2^{|V| - |s|}$.
card_univ- The cardinality of the universal finset `univ` of a finite type is the cardinality of the underlying type.
Fintype.card_fun- The number of functions from a finite type $\alpha$ to a finite type $\beta$ is $|\beta|^{|\alpha|}$.
Fintype.card_bool- The type `Bool` has cardinality 2.
- The theorem inequality is stated over the rational numbers $\mathbb{Q}$ rather than the natural numbers $\mathbb{N}$; the final step is a purely formal cast between numeric types.
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_packing {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, (2 : ℚ) ^ (Fintype.card V - (s i).card) ≤ 2 ^ Fintype.card V := 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) have hc := Finset.card_le_card (show (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) ⊆ univ from subset_univ _) rw [Finset.card_biUnion hdis] at hc simp only [binary_partial_word_cube_card, card_univ, Fintype.card_fun, Fintype.card_bool] at hc exact_mod_cast hc