AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_packing

theoremverified

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
Used by 1

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.

  1. 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.

    lines 9–13

    uses binary_partial_word_cube_disjoint

      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)
  2. 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|}$.

    lines 14–18

    uses Finset.card_le_card, subset_univ, Finset.card_biUnion, binary_partial_word_cube_card, card_univ, Fintype.card_fun, Fintype.card_bool

      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
  3. The inequality holds over the rational numbers.

    Casting the natural-number inequality established in the previous step into $\mathbb{Q}$ completes the proof.

    line 19

      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.

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

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
See it in the graphDiscuss this resultChallenge it