binary_partial_word_partition_moments
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
- 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_memMembership in a partial-word cube is exactly agreement on every supported coordinate.
- binary_partial_word_cube_disjointTwo partial-word cubes with a conflicting supported coordinate are disjoint.
- binary_partial_word_signThe rational signed incidence of a coordinate in a partial word, with zero outside its support.
- binary_partial_word_cube_sign_sumThe sum of a coordinate sign on a partial-word cube is its cardinality times the signed incidence of that coordinate.
- binary_partial_word_cube_sign_pair_sumFor distinct coordinates, their sign product summed on a partial-word cube equals its cardinality times the two signed incidences.
- binary_bool_signThe rational sign of a Boolean value: true gives one and false gives minus one.
- Used by 1
- binary_partial_word_partition_dimension_boundA finite partition of a Boolean cube by pairwise conflicting partial words, mentioning every coordinate, has at least one more part than…
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.
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.
uses
binary_partial_word_cube_disjointclassical 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)
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.
uses
binary_partial_word_cube_memhave hempty : binary_partial_word_cube (∅ : Finset V) (fun _ => false) = univ := by ext f simp [binary_partial_word_cube_mem]
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.
constructorFor 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`).
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
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`).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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