binary_partial_word_cube_sign_sum
The sum of a coordinate sign on a partial-word cube is its cardinality times the signed incidence of that coordinate.
Statement
theorem binary_partial_word_cube_sign_sum {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) (v : V) : (∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (f v)) = (binary_partial_word_cube s b).card * binary_partial_word_sign s b v
- 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_memMembership in a partial-word cube is exactly agreement on every supported coordinate.
- binary_bool_signThe rational sign of a Boolean value: true gives one and false gives minus one.
- binary_bool_sign_notNegating a Boolean value negates its rational sign.
- binary_partial_word_signThe rational signed incidence of a coordinate in a partial word, with zero outside its support.
- binary_partial_word_cube_odd_sumA rational function which changes sign under flipping a free coordinate of a partial-word cube sums to zero on that cube.
- Used by 1
- binary_partial_word_partition_momentsFor a partition by pairwise conflicting partial-word cubes, the cardinality-weighted first signed incidences and mixed signed incidences…
The proof, explained
The proof proceeds by case analysis on whether the coordinate v belongs to the set s of constrained coordinates. When v ∈ s, every function in the partial-word cube takes the fixed value b(v) at v, so the summand is constant and the sum equals the cube's cardinality times that sign. When v ∉ s, the signed incidence is zero by definition, and the sum over the cube vanishes because bit-negation at coordinate v is a sign-reversing involution on the cube.
We split into two cases: v ∈ s and v ∉ s.
Using classical logic, we perform a case distinction on whether the coordinate v belongs to the subset s of fixed coordinates.
classical by_cases hv : v ∈ sWhen v ∈ s, the sum of signs over the cube equals the cardinality of the cube times binary_partial_word_sign s b v.
Because v ∈ s, rewriting by binary_partial_word_sign and if_pos simplifies the right-hand side to #(binary_partial_word_cube s b) * binary_bool_sign (b v). By binary_partial_word_cube_mem, every element f of the partial-word cube satisfies f v = b v. Using sum_congr, we replace f v with b v in each term of the sum, turning it into a sum of the constant binary_bool_sign (b v). Summing this constant over the cube simplifies to the cardinality of the cube times binary_bool_sign (b v), matching the right-hand side.
uses
binary_partial_word_sign,if_pos,sum_congr,binary_partial_word_cube_mem· rw [binary_partial_word_sign, if_pos hv] calc _ = ∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (b v) := by apply sum_congr rfl intro f hf rw [(binary_partial_word_cube_mem s b f).mp hf v hv] _ = _ := by simp
When v ∉ s, both sides evaluate to 0, establishing the theorem.
Since v ∉ s, rewriting with binary_partial_word_sign and if_neg sets the signed incidence to 0, and mul_zero makes the right-hand side 0. By binary_partial_word_cube_odd_sum, it suffices to show that flipping coordinate v negates the summand. For any f in the cube, updating coordinate v to !f v evaluates at v to !f v (by Function.update_self), and binary_bool_sign (!f v) = -binary_bool_sign (f v) by binary_bool_sign_not. Thus the sum is 0.
uses
binary_partial_word_sign,if_neg,mul_zero,binary_partial_word_cube_odd_sum,Function.update_self,binary_bool_sign_not· rw [binary_partial_word_sign, if_neg hv, mul_zero] apply binary_partial_word_cube_odd_sum s b v hv intro f hf simp only [Function.update_self, binary_bool_sign_not]
binary_partial_word_sign- The definition of signed incidence for coordinate v, equal to binary_bool_sign (b v) if v ∈ s and 0 otherwise.
if_pos- A conditional expression if c then t else e reduces to t when the condition c holds.
sum_congr- Two sums over the same finite set are equal if their summands agree on every element of the set.
binary_partial_word_cube_mem- A function f belongs to binary_partial_word_cube s b if and only if f agrees with b on all coordinates in s.
if_neg- A conditional expression if c then t else e reduces to e when the condition c is false.
mul_zero- Multiplying any element by zero on the right gives zero (a * 0 = 0).
binary_partial_word_cube_odd_sum- If v ∉ s and a function is odd under bit-negation at coordinate v, its sum over the partial-word cube is zero.
Function.update_self- Evaluating an updated function Function.update f a v at the updated input a gives v.
binary_bool_sign_not- Negating a boolean negates its sign: binary_bool_sign (!b) = -binary_bool_sign b.
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_cube_sign_sum {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) (v : V) : (∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (f v)) = (binary_partial_word_cube s b).card * binary_partial_word_sign s b v := by classical by_cases hv : v ∈ s · rw [binary_partial_word_sign, if_pos hv] calc _ = ∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (b v) := by apply sum_congr rfl intro f hf rw [(binary_partial_word_cube_mem s b f).mp hf v hv] _ = _ := by simp · rw [binary_partial_word_sign, if_neg hv, mul_zero] apply binary_partial_word_cube_odd_sum s b v hv intro f hf simp only [Function.update_self, binary_bool_sign_not]