AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_minimum_incidence

theoremverified

For pairwise conflicting finite partial words, if total support size plus 2^m equals the number of words times m+1, then their volume sum is one and every support size is m or m-1, expressed without truncated subtraction.

Statement

theorem binary_partial_word_cube_minimum_incidence {I V : Type*} [Fintype I] [Fintype V]
    [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) (m : ℕ)
    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)
    (hcost : (∑ i, (s i).card) + 2^m = Fintype.card I * (m+1)) :
    (∑ i, (1 : ℚ) / 2^(s i).card) = 1 ∧
      ∀ i, (s i).card = m ∨ (s i).card + 1 = m
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 proof uses a dyadic tangent line inequality: for every natural number t, the affine function m + 1 - t is bounded above by 2^m / 2^t, with equality if and only if t = m or t + 1 = m. Summing this inequality over all partial words and substituting the given cost condition yields 2^m ≤ 2^m * ∑ i, 1 / 2^(s i).card, which implies the volume sum is at least 1. Since the partial words pairwise conflict, their corresponding subcubes are disjoint, so their volume sum cannot exceed 1; combining these bounds forces the volume sum to equal exactly 1. Finally, because the sum of the lower bounds equals the sum of the upper bounds, equality must hold term-by-term, characterizing every support size as either m or m - 1.

  1. The volume sum ∑ i, 1 / 2^(s i).card is at most 1.

    Enabling classical logic, we apply the volume bound for pairwise conflicting binary partial words (`binary_partial_word_cube_volume_bound`). Because the partial words pairwise conflict on overlapping coordinates, the subcubes they define in {0, 1}^V are pairwise disjoint, so the sum of their volumes cannot exceed 1.

    lines 11–12

    uses binary_partial_word_cube_volume_bound

      classical
      have hu := binary_partial_word_cube_volume_bound s b hconflict
  2. ∑ i, ((m : ℚ) + 1 - (s i).card) = 2^m.

    We cast the cost hypothesis to rational numbers. Distributing the sum over the subtraction with `sum_sub_distrib` and evaluating the sum of the constant (m + 1) via `sum_const`, `nsmul_eq_mul`, and `card_univ`, linear arithmetic (`linarith`) rearranges the equation into ∑ i, ((m : ℚ) + 1 - (s i).card) = 2^m.

    lines 13–17

    uses sum_sub_distrib, sum_const, nsmul_eq_mul, card_univ

      have hc : (∑ i, ((s i).card : ℚ)) + 2^m = (Fintype.card I : ℚ) * (m+1) := by
        exact_mod_cast hcost
      have hsum : (∑ i, ((m : ℚ)+1-(s i).card)) = 2^m := by
        simp only [sum_sub_distrib, sum_const, nsmul_eq_mul, card_univ]
        linarith
  3. 2^m ≤ 2^m * ∑ i, 1 / 2^(s i).card.

    By the dyadic tangent inequality `dyadic_integer_tangent`, every natural number t satisfies m + 1 - t ≤ 2^m / 2^t. Summing this termwise via `sum_le_sum` and replacing the left-hand sum with 2^m, we obtain 2^m ≤ ∑ i, 2^m / 2^(s i).card. Factoring out 2^m using `mul_sum`, `div_eq_mul_inv`, and `one_mul` gives the claimed lower bound.

    lines 18–24

    uses sum_le_sum, dyadic_integer_tangent, div_eq_mul_inv, one_mul, mul_sum

      have hl : (2 : ℚ)^m ≤ 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by
        calc
          (2 : ℚ)^m = ∑ i, ((m : ℚ)+1-(s i).card) := hsum.symm
          _ ≤ ∑ i, (2 : ℚ)^m / 2^(s i).card :=
            sum_le_sum (fun i hi => dyadic_integer_tangent m (s i).card)
          _ = 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by
            simp only [div_eq_mul_inv, one_mul, mul_sum]
  4. The volume sum ∑ i, 1 / 2^(s i).card equals 1, proving the first conjunct.

    Since 2^m > 0 (by `positivity`), dividing the lower bound 2^m ≤ 2^m * ∑ i, 1 / 2^(s i).card by 2^m yields 1 ≤ ∑ i, 1 / 2^(s i).card. Non-linear arithmetic (`nlinarith`) combines this with the upper bound ∑ i, 1 / 2^(s i).card ≤ 1 to deduce that the sum is exactly 1, which establishes the first goal of the conjunction.

    lines 25–27

      have hp : (0 : ℚ) < 2^m := by positivity
      have hv : (∑ i, (1 : ℚ)/2^(s i).card) = 1 := by nlinarith
      refine ⟨hv, ?_⟩
  5. For every i, equality holds in the tangent inequality: (m : ℚ) + 1 - (s i).card = 2^m / 2^(s i).card.

    Each term satisfies (m : ℚ) + 1 - (s j).card ≤ 2^m / 2^(s j).card by `dyadic_integer_tangent`. Furthermore, the sum of the left-hand sides is 2^m, and the sum of the right-hand sides is 2^m * ∑ j, 1 / 2^(s j).card = 2^m * 1 = 2^m by `div_eq_mul_inv`, `one_mul`, `mul_sum`, and `mul_one`. By `sum_eq_sum_iff_of_le`, when a sum of smaller terms equals the sum of larger terms over a finite set, equality must hold term-by-term. Specializing to i using `mem_univ` yields the claim.

    lines 28–38

    uses dyadic_integer_tangent, div_eq_mul_inv, one_mul, mul_sum, mul_one, sum_eq_sum_iff_of_le, mem_univ

      have hterm : ∀ i, (m : ℚ)+1-(s i).card = 2^m / 2^(s i).card := by
        intro i
        have hle : ∀ j ∈ (univ : Finset I),
            (m : ℚ)+1-(s j).card ≤ 2^m / 2^(s j).card := by
          intro j hj
          exact dyadic_integer_tangent m (s j).card
        have heq : (∑ j, ((m : ℚ)+1-(s j).card)) = ∑ j, (2 : ℚ)^m / 2^(s j).card := by
          rw [hsum]
          simp only [div_eq_mul_inv, one_mul] at hv ⊢
          rw [← mul_sum, hv, mul_one]
        exact (sum_eq_sum_iff_of_le hle).mp heq i (mem_univ _)
  6. For every i, (s i).card = m or (s i).card + 1 = m.

    For any index i, termwise equality holds from the previous step. The lemma `dyadic_integer_tangent_eq_iff` states that (m : ℚ) + 1 - t = 2^m / 2^t if and only if t = m or t + 1 = m. Applying this equivalence to t = (s i).card proves the second conjunct.

    lines 39–40

    uses dyadic_integer_tangent_eq_iff

      intro i
      exact (dyadic_integer_tangent_eq_iff m (s i).card).mp (hterm i)
binary_partial_word_cube_volume_bound
for pairwise conflicting partial words, the sum of their volumes 2^(-|s i|) is at most 1
card_univ
the cardinality of Finset.univ for a finite type is the cardinality of the type
div_eq_mul_inv
division a / b is definitionally multiplication by the inverse, a * b⁻¹
dyadic_integer_tangent
for any natural numbers m and t, the affine function (m + 1) - t is bounded above by 2^m / 2^t
dyadic_integer_tangent_eq_iff
the equality (m + 1) - t = 2^m / 2^t holds for natural numbers m and t if and only if t = m or t + 1 = m
mem_univ
every element of a finite type belongs to the universal finset Finset.univ
mul_one
multiplying an element on the right by 1 leaves it unchanged
mul_sum
multiplication distributes over finite sums from the left
nsmul_eq_mul
scalar multiplication of an element by a natural number n is equal to multiplication by the coercion of n
one_mul
multiplying an element on the left by 1 leaves it unchanged
sum_const
summing a constant value over a finite set equals the cardinality of the set multiplied by that constant
sum_eq_sum_iff_of_le
if each term f(x) is at most g(x), then their sums are equal if and only if f(x) = g(x) for all terms
sum_le_sum
if f(x) ≤ g(x) for all elements in a finite set, then the sum of f is at most the sum of g
sum_sub_distrib
a sum of differences equals the difference of the sums

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_minimum_incidence {I V : Type*} [Fintype I] [Fintype V]    [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) (m : ℕ)    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)    (hcost : (∑ i, (s i).card) + 2^m = Fintype.card I * (m+1)) :    (∑ i, (1 : ℚ) / 2^(s i).card) = 1 ∧      ∀ i, (s i).card = m ∨ (s i).card + 1 = m := by  classical  have hu := binary_partial_word_cube_volume_bound s b hconflict  have hc : (∑ i, ((s i).card : ℚ)) + 2^m = (Fintype.card I : ℚ) * (m+1) := by    exact_mod_cast hcost  have hsum : (∑ i, ((m : ℚ)+1-(s i).card)) = 2^m := by    simp only [sum_sub_distrib, sum_const, nsmul_eq_mul, card_univ]    linarith  have hl : (2 : ℚ)^m ≤ 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by    calc      (2 : ℚ)^m = ∑ i, ((m : ℚ)+1-(s i).card) := hsum.symm      _ ≤ ∑ i, (2 : ℚ)^m / 2^(s i).card :=        sum_le_sum (fun i hi => dyadic_integer_tangent m (s i).card)      _ = 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by        simp only [div_eq_mul_inv, one_mul, mul_sum]  have hp : (0 : ℚ) < 2^m := by positivity  have hv : (∑ i, (1 : ℚ)/2^(s i).card) = 1 := by nlinarith  refine ⟨hv, ?_⟩  have hterm : ∀ i, (m : ℚ)+1-(s i).card = 2^m / 2^(s i).card := by    intro i    have hle : ∀ j ∈ (univ : Finset I),        (m : ℚ)+1-(s j).card ≤ 2^m / 2^(s j).card := by      intro j hj      exact dyadic_integer_tangent m (s j).card    have heq : (∑ j, ((m : ℚ)+1-(s j).card)) = ∑ j, (2 : ℚ)^m / 2^(s j).card := by      rw [hsum]      simp only [div_eq_mul_inv, one_mul] at hv ⊢      rw [← mul_sum, hv, mul_one]    exact (sum_eq_sum_iff_of_le hle).mp heq i (mem_univ _)  intro i  exact (dyadic_integer_tangent_eq_iff m (s i).card).mp (hterm i)
See it in the graphDiscuss this resultChallenge it