AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_volume_bound

theoremverified

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

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.

  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.

    line 9

    uses binary_partial_word_cube_packing

      have hpack := binary_partial_word_cube_packing s b hconflict
  2. For 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)|.

    lines 10–13

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

    lines 14–15

    uses mul_sum

      simp_rw [he] at hpack
      rw [← mul_sum] at hpack
  4. 2^|V| > 0 in ℚ. automation

    The power 2^|V| is strictly positive because 2 > 0, which `positivity` establishes automatically.

    line 16

      have hp : (0 : ℚ) < 2 ^ Fintype.card V := by positivity
  5. ∑ 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.

    line 17

      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

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