AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_dimension_bound

theoremverified

A finite partition of a Boolean cube by pairwise conflicting partial words, mentioning every coordinate, has at least one more part than coordinates.

Statement

theorem binary_partial_word_partition_dimension_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)
    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)
    (hessential : ∀ v, ∃ i, v ∈ s i) :
    Fintype.card V + 1 ≤ Fintype.card I
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 6
  • 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_bool_signThe rational sign of a Boolean value: true gives one and false gives minus one.
  • binary_partial_word_signThe rational signed incidence of a coordinate in a partial word, with zero outside its support.
  • binary_partial_word_partition_momentsFor a partition by pairwise conflicting partial-word cubes, the cardinality-weighted first signed incidences and mixed signed incidences…
  • weighted_orthogonal_card_boundA finite family of vectors with nonzero weighted squared norms and zero off-diagonal weighted pair products has size at most its ambient…
Used by 1

The proof, explained

The theorem is proved by constructing an orthogonal system of |V| + 1 non-zero vectors in the weighted space Q^I, where each index i is weighted by the size of its corresponding subcube w_i = 2^(|V| - |s i|). The system consists of the constant-one vector (indexed by none) together with the coordinate sign vectors (indexed by each v ∈ V), which are shown to be pairwise orthogonal using the partition moments theorem. Because every coordinate is essential, each vector has strictly positive weighted norm, and the bound |V| + 1 ≤ |I| follows from the standard linear algebraic bound on the size of an orthogonal system.

  1. Define the subcube weights w on I and the test vectors y on Option V.

    Working classically, each partition element i ∈ I is assigned the weight w(i) equal to the size of its subcube in the Boolean cube. A family of vectors y_a ∈ Q^I indexed by a ∈ Option V is defined: the extra element none gives the constant-one vector y_{none}(i) = 1, while each coordinate v ∈ V gives the sign vector y_v(i), which is 1 if the i-th partial word fixes v to true, -1 if it fixes v to false, and 0 if v is unassigned.

    lines 11–16

      classical
      let w : I → ℚ := fun i => (binary_partial_word_cube (s i) (b i)).card
      let y : Option V → I → ℚ := fun a i =>
        match a with
        | none => 1
        | some v => binary_partial_word_sign (s i) (b i) v
  2. Every weight w(i) is strictly positive.

    Unfolding the definition of w and rewriting with binary_partial_word_cube_card, the size of subcube i is 2^(|V| - |s i|). The positivity tactic verifies that this power of two is strictly positive.

    lines 17–20

    uses binary_partial_word_cube_card

      have hw (i : I) : 0 < w i := by
        dsimp [w]
        rw [binary_partial_word_cube_card]
        positivity
  3. The index set I is non-empty.

    The all-false assignment belongs to the universal set of assignments (mem_univ). Since the subcubes cover the universal set (hcover), the all-false assignment lies in the union of all subcubes, so by mem_biUnion there exists at least one index i ∈ I containing it.

    lines 21–27

    uses mem_univ, mem_biUnion

      have hex : ∃ i : I, True := by
        have hf : (fun _ : V => false) ∈
            univ.biUnion (fun i => binary_partial_word_cube (s i) (b i)) := by
          rw [hcover]
          exact mem_univ _
        rcases mem_biUnion.mp hf with ⟨i, hi, hf⟩
        exact ⟨i, trivial⟩
  4. The weighted first and second moments of the sign vectors vanish.

    Because the subcubes pairwise conflict (hconflict) and cover the entire Boolean cube (hcover), binary_partial_word_partition_moments supplies the two moment conditions: the weighted sum of y_v is 0 for every coordinate v, and the weighted sum of products y_u * y_v is 0 for any distinct coordinates u ≠ v.

    line 28

    uses binary_partial_word_partition_moments

      have hm := binary_partial_word_partition_moments s b hconflict hcover
  5. The family of vectors {y_a} is pairwise orthogonal with respect to the weights w.

    Given distinct a, c ∈ Option V, we case-split on whether each is none or some coordinate. If both are none, they cannot be distinct. If one is none and the other is some v, the weighted inner product reduces to the first moment condition ∑_i w_i y_v(i) = 0. If they are some u and some v, then u ≠ v by congrArg, so the weighted inner product vanishes by the second moment condition.

    lines 29–40

    uses congrArg

      have horth (a c : Option V) (hac : a ≠ c) :
          (∑ i, w i * y a i * y c i) = 0 := by
        cases a with
        | none =>
          cases c with
          | none => exact (hac rfl).elim
          | some v => simpa [w, y] using hm.1 v
        | some u =>
          cases c with
          | none => simpa [w, y] using hm.1 u
          | some v =>
            exact hm.2 u v (fun he => hac (congrArg some he))
  6. Every vector y_a has strictly positive, hence non-zero, weighted norm-squared.

    By ne_of_gt, it suffices to show that ∑_i w_i (y_a(i))^2 > 0. Every summand is non-negative because w_i > 0 and squares are non-negative (sq_nonneg). By sum_pos', it suffices to exhibit a single index where the term is strictly positive. For a = none, y_{none}(i) = 1, and any index in I (which is non-empty) gives w_i > 0. For a = some v, the essentiality hypothesis hessential guarantees an index i where v ∈ s i; at this index, if_pos simplifies y_v(i) to ±1, making the summand w_i * (±1)^2 = w_i > 0.

    lines 41–57

    uses ne_of_gt, sum_pos', mem_univ, sq_nonneg, if_pos

      have hnorm (a : Option V) : (∑ i, w i * y a i * y a i) ≠ 0 := by
        apply ne_of_gt
        cases a with
        | none =>
          obtain ⟨i, hi⟩ := hex
          simpa [y] using (sum_pos' (fun j hj => (hw j).le)
            ⟨i, mem_univ _, hw i⟩)
        | some v =>
          obtain ⟨i, hi⟩ := hessential v
          apply sum_pos'
          · intro j hj
            have hq := sq_nonneg (y (some v) j)
            nlinarith [hw j]
          · refine ⟨i, mem_univ _, ?_⟩
            dsimp [y, binary_partial_word_sign]
            rw [if_pos hi]
            cases hbit : b i v <;> simpa [binary_bool_sign, hbit] using hw i
  7. The number of parts is at least one more than the dimension: |V| + 1 ≤ |I|.

    The lemma weighted_orthogonal_card_bound implies that any family of non-zero pairwise orthogonal vectors in Q^I has cardinality at most |I|. Since the family is indexed by Option V, whose cardinality is |V| + 1 by Fintype.card_option, the desired inequality follows immediately.

    line 58

    uses Fintype.card_option, weighted_orthogonal_card_bound

      simpa only [Fintype.card_option] using weighted_orthogonal_card_bound w y horth hnorm
binary_partial_word_cube_card
The cardinality of the subcube defined by a partial word specifying coordinates s is 2^(|V| - |s|).
mem_univ
Every element of a finite type belongs to its universal finset.
mem_biUnion
An element belongs to a finset union ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
binary_partial_word_partition_moments
For any partition of the Boolean cube by pairwise conflicting partial words, the weighted first moment of coordinate signs is zero for every coordinate, and the weighted second moment is zero for any pair of distinct coordinates.
congrArg
If two arguments are equal, applying any function to them yields equal results.
ne_of_gt
If b < a in a preorder, then a ≠ b.
sum_pos'
A finite sum of non-negative elements is strictly positive if at least one term is strictly positive.
sq_nonneg
The square of any element in an ordered semiring is non-negative.
if_pos
A conditional expression if c then t else e reduces to t whenever the condition c is true.
Fintype.card_option
For any finite type α, the cardinality of Option α is |α| + 1.
weighted_orthogonal_card_bound
A family of pairwise orthogonal non-zero vectors in a weighted space Q^I has cardinality at most |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_partition_dimension_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)    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)    (hessential : ∀ v, ∃ i, v ∈ s i) :    Fintype.card V + 1 ≤ Fintype.card I := by  classical  let w : I → ℚ := fun i => (binary_partial_word_cube (s i) (b i)).card  let y : Option V → I → ℚ := fun a i =>    match a with    | none => 1    | some v => binary_partial_word_sign (s i) (b i) v  have hw (i : I) : 0 < w i := by    dsimp [w]    rw [binary_partial_word_cube_card]    positivity  have hex : ∃ i : I, True := by    have hf : (fun _ : V => false) ∈        univ.biUnion (fun i => binary_partial_word_cube (s i) (b i)) := by      rw [hcover]      exact mem_univ _    rcases mem_biUnion.mp hf with ⟨i, hi, hf⟩    exact ⟨i, trivial⟩  have hm := binary_partial_word_partition_moments s b hconflict hcover  have horth (a c : Option V) (hac : a ≠ c) :      (∑ i, w i * y a i * y c i) = 0 := by    cases a with    | none =>      cases c with      | none => exact (hac rfl).elim      | some v => simpa [w, y] using hm.1 v    | some u =>      cases c with      | none => simpa [w, y] using hm.1 u      | some v =>        exact hm.2 u v (fun he => hac (congrArg some he))  have hnorm (a : Option V) : (∑ i, w i * y a i * y a i) ≠ 0 := by    apply ne_of_gt    cases a with    | none =>      obtain ⟨i, hi⟩ := hex      simpa [y] using (sum_pos' (fun j hj => (hw j).le)        ⟨i, mem_univ _, hw i⟩)    | some v =>      obtain ⟨i, hi⟩ := hessential v      apply sum_pos'      · intro j hj        have hq := sq_nonneg (y (some v) j)        nlinarith [hw j]      · refine ⟨i, mem_univ _, ?_⟩        dsimp [y, binary_partial_word_sign]        rw [if_pos hi]        cases hbit : b i v <;> simpa [binary_bool_sign, hbit] using hw i  simpa only [Fintype.card_option] using weighted_orthogonal_card_bound w y horth hnorm
See it in the graphDiscuss this resultChallenge it