AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_moments

theoremverified

For a partition by pairwise conflicting partial-word cubes, the cardinality-weighted first signed incidences and mixed signed incidences at distinct coordinates all sum to zero.

Statement

theorem binary_partial_word_partition_moments {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) :
    (∀ v, (∑ i, (binary_partial_word_cube (s i) (b i)).card *
      binary_partial_word_sign (s i) (b i) v) = 0) ∧
    (∀ u v, u ≠ v → (∑ i, (binary_partial_word_cube (s i) (b i)).card *
      binary_partial_word_sign (s i) (b i) u * binary_partial_word_sign (s i) (b i) v) = 0)
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 7
Used by 1

The proof, explained

The theorem shows that for any partition of the space of binary words by conflicting partial-word cubes, both the first and second moments of the cube signs vanish when weighted by cube size. Because the cubes pairwise conflict on at least one coordinate, they are pairwise disjoint and therefore partition the entire space of words. Using character summation identities on cubes, the sum over all cubes is rewritten as the total sum of signs over the entire universe. This total sum is in turn evaluated as the moment of the empty-restriction cube, which vanishes identically because the empty set fixes no coordinates.

  1. The partial-word cubes indexed by I are pairwise disjoint.

    We enable classical reasoning and consider distinct indices i ≠ j. By the conflict hypothesis (hconflict), there exists a coordinate v ∈ s(i) ∩ s(j) on which b(i)(v) ≠ b(j)(v). By `binary_partial_word_cube_disjoint`, the corresponding cubes are disjoint.

    lines 13–17

    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 partial-word cube with an empty defining set is the entire set of binary words univ.

    For any binary word f, the condition that f agrees with the prescribed values on all coordinates in the empty set is vacuously true. By `binary_partial_word_cube_mem`, every binary word belongs to this cube.

    lines 18–20

    uses binary_partial_word_cube_mem

      have hempty : binary_partial_word_cube (∅ : Finset V) (fun _ => false) = univ := by
        ext f
        simp [binary_partial_word_cube_mem]
  3. It suffices to prove the first-moment identity and the second-moment identity separately.

    The theorem is a conjunction of two universal statements; splitting the goal produces two independent subgoals.

    line 21

      constructor
  4. For every coordinate v, the cardinality-weighted sum of the signs at v across all cubes is zero.

    Given a coordinate v, `binary_partial_word_cube_sign_sum` converts each term |cube| · sign into the sum of the signs of f(v) over all words f in that cube. Using pairwise disjointness (hdis) via `sum_biUnion` and the covering assumption (hcover), this sum over all cubes becomes the sum of the signs of f(v) over all binary words in univ. The identity `binary_partial_word_cube_sign_sum` applied to the empty cube (which equals univ via `hempty`) shows this total sum equals |univ| · sign(∅, false, v). Since v ∉ ∅ (`Finset.notMem_empty` and `if_false`), the sign of the empty cube at v is 0 (`binary_partial_word_sign`), so the product vanishes (`mul_zero`).

    lines 22–26

    uses binary_partial_word_cube_sign_sum, sum_biUnion, binary_partial_word_sign, Finset.notMem_empty, if_false, mul_zero

      · intro v
        simp_rw [← binary_partial_word_cube_sign_sum]
        rw [← sum_biUnion hdis, hcover]
        have he := binary_partial_word_cube_sign_sum (∅ : Finset V) (fun _ => false) v
        simpa only [hempty, binary_partial_word_sign, Finset.notMem_empty, if_false, mul_zero] using he
  5. For any distinct coordinates u and v, the cardinality-weighted sum of the product of signs at u and v across all cubes is zero.

    Given distinct coordinates u ≠ v, `binary_partial_word_cube_sign_pair_sum` converts each cube's term into the sum of sign products over that cube. By disjointness and the cover hypothesis, `sum_biUnion` merges these into the sum of sign products over the entire space univ. Applying `binary_partial_word_cube_sign_pair_sum` to the empty cube, the total sum is |univ| times the product of the empty cube's signed incidences at u and v. Since u ∉ ∅, this factor evaluates to 0 (`Finset.notMem_empty`, `if_false`, `binary_partial_word_sign`), and the product vanishes (`mul_zero`, `zero_mul`).

    lines 27–31

    uses binary_partial_word_cube_sign_pair_sum, sum_biUnion, binary_partial_word_sign, Finset.notMem_empty, if_false, mul_zero, zero_mul

      · intro u v huv
        simp_rw [← binary_partial_word_cube_sign_pair_sum _ _ u v huv]
        rw [← sum_biUnion hdis, hcover]
        have he := binary_partial_word_cube_sign_pair_sum (∅ : Finset V) (fun _ => false) u v huv
        simpa only [hempty, binary_partial_word_sign, Finset.notMem_empty, if_false, mul_zero, zero_mul] using he
binary_partial_word_cube_disjoint
Two partial-word cubes are disjoint if there is a coordinate in the intersection of their defining sets where their prescribed Boolean values disagree.
binary_partial_word_cube_mem
A binary word belongs to a partial-word cube if and only if it matches the cube's prescribed values on all coordinates in the cube's defining set.
binary_partial_word_cube_sign_sum
The sum over a partial-word cube of the sign of a coordinate v equals the cardinality of the cube times the cube's signed incidence at v.
binary_partial_word_cube_sign_pair_sum
For distinct coordinates u and v, the sum over a partial-word cube of the product of signs at u and v equals the cube's cardinality times the product of its signed incidences at u and v.
binary_partial_word_sign
The signed incidence of a partial-word cube at coordinate v: the sign of the prescribed bit at v if v is in the defining set, and 0 otherwise.
sum_biUnion
The sum of a function over a pairwise disjoint union of finite sets equals the iterated sum over each constituent set.
Finset.notMem_empty
No element belongs to the empty set.
if_false
An if-then-else expression whose condition is false simplifies to the else branch.
mul_zero
Multiplying any element by zero on the right gives zero.
zero_mul
Multiplying zero by any element on the left gives zero.

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_moments {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) :    (∀ v, (∑ i, (binary_partial_word_cube (s i) (b i)).card *      binary_partial_word_sign (s i) (b i) v) = 0) ∧    (∀ u v, u ≠ v → (∑ i, (binary_partial_word_cube (s i) (b i)).card *      binary_partial_word_sign (s i) (b i) u * binary_partial_word_sign (s i) (b i) v) = 0) := 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 hempty : binary_partial_word_cube (∅ : Finset V) (fun _ => false) = univ := by    ext f    simp [binary_partial_word_cube_mem]  constructor  · intro v    simp_rw [← binary_partial_word_cube_sign_sum]    rw [← sum_biUnion hdis, hcover]    have he := binary_partial_word_cube_sign_sum (∅ : Finset V) (fun _ => false) v    simpa only [hempty, binary_partial_word_sign, Finset.notMem_empty, if_false, mul_zero] using he  · intro u v huv    simp_rw [← binary_partial_word_cube_sign_pair_sum _ _ u v huv]    rw [← sum_biUnion hdis, hcover]    have he := binary_partial_word_cube_sign_pair_sum (∅ : Finset V) (fun _ => false) u v huv    simpa only [hempty, binary_partial_word_sign, Finset.notMem_empty, if_false, mul_zero, zero_mul] using he
See it in the graphDiscuss this resultChallenge it