AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_cover_of_volume_eq

theoremverified

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

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.

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

    lines 10–14

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

    lines 15–17

    uses eq_univ_of_card, card_biUnion, binary_partial_word_cube_card, Fintype.card_fun, Fintype.card_bool

      apply eq_univ_of_card
      rw [card_biUnion hdis]
      simp only [binary_partial_word_cube_card, Fintype.card_fun, Fintype.card_bool]
  3. 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|.

    lines 18–21

    uses pow_sub₀, card_le_univ, one_div

      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]
  4. 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`.

    lines 22–24

    uses mul_sum, mul_one

      have hq : (∑ i, (2 : ℚ)^(Fintype.card V - (s i).card)) = 2^Fintype.card V := by
        simp_rw [he]
        rw [← mul_sum, hvolume, mul_one]
  5. 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.

    line 25

      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.

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