binary_partial_word_cube_sign_pair_sum
For distinct coordinates, their sign product summed on a partial-word cube equals its cardinality times the two signed incidences.
Statement
theorem binary_partial_word_cube_sign_pair_sum {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) (u v : V) (huv : u ≠ v) : (∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (f u) * binary_bool_sign (f v)) = (binary_partial_word_cube s b).card * binary_partial_word_sign s b u * 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 coordinates u and v belong to the index set s. When both belong to s, all functions in the partial-word cube fix u and v to b u and b v, so the summand is constant and sums to the cube's cardinality times the product of the two signs. When at least one coordinate is outside s, the right-hand side vanishes because the corresponding partial word sign is zero, while on the left-hand side flipping that unconstrained coordinate negates the summand (since u ≠ v), so the sum over the cube cancels out to zero.
When both u ∈ s and v ∈ s, the sum equals the cube's cardinality times the product of the two signs.
Using classical logic, we branch on whether u ∈ s and whether v ∈ s. When both u ∈ s and v ∈ s, rewriting with if_pos simplifies binary_partial_word_sign on u and v to binary_bool_sign (b u) and binary_bool_sign (b v). By binary_partial_word_cube_mem, every function f in the cube satisfies f u = b u and f v = b v, so sum_congr replaces the summand with the constant binary_bool_sign (b u) * binary_bool_sign (b v). Summing this constant over the cube yields the cardinality times the two signs (using mul_assoc).
uses
if_pos,sum_congr,binary_partial_word_cube_mem,mul_assocclassical by_cases hu : u ∈ s · by_cases hv : v ∈ s · simp only [binary_partial_word_sign, if_pos hu, if_pos hv] calc _ = ∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (b u) * binary_bool_sign (b v) := by apply sum_congr rfl intro f hf rw [(binary_partial_word_cube_mem s b f).mp hf u hu, (binary_partial_word_cube_mem s b f).mp hf v hv] _ = _ := by simp [mul_assoc]
When u ∈ s and v ∉ s, both sides evaluate to 0.
Since v ∉ s, rewriting with if_neg evaluates binary_partial_word_sign s b v to 0, so the right-hand side is 0 by mul_zero. On the left-hand side, since v ∉ s, we apply binary_partial_word_cube_odd_sum at coordinate v. For any f in the cube, updating f at v with !f v leaves coordinate u unchanged by Function.update_of_ne (since u ≠ v), while evaluating to !f v at v by Function.update_self. By binary_bool_sign_not, the sign at v is negated, so the whole summand changes sign. Ring arithmetic verifies this odd-symmetry condition, ensuring the sum over the cube is 0.
uses
if_pos,if_neg,mul_zero,binary_partial_word_cube_odd_sum,Function.update_of_ne,Function.update_self,binary_bool_sign_not· simp only [binary_partial_word_sign, if_pos hu, if_neg hv, mul_zero] apply binary_partial_word_cube_odd_sum s b v hv intro f hf simp only [Function.update_of_ne huv, Function.update_self, binary_bool_sign_not] ring
When u ∉ s, both sides evaluate to 0.
Since u ∉ s, rewriting with if_neg evaluates binary_partial_word_sign s b u to 0, which makes the right-hand side 0 by zero_mul and mul_zero. For the left-hand side, since u ∉ s, we apply binary_partial_word_cube_odd_sum at coordinate u. Flipping the value at u negates binary_bool_sign (f u) by Function.update_self and binary_bool_sign_not, while leaving the value at v unchanged by Function.update_of_ne (as v ≠ u from u ≠ v). Ring arithmetic confirms the summand is negated, so the sum over the cube vanishes.
uses
if_neg,mul_zero,zero_mul,binary_partial_word_cube_odd_sum,Function.update_self,Function.update_of_ne,binary_bool_sign_not· simp only [binary_partial_word_sign, if_neg hu, mul_zero, zero_mul] apply binary_partial_word_cube_odd_sum s b u hu intro f hf simp only [Function.update_self, Function.update_of_ne huv.symm, binary_bool_sign_not] ring
if_pos- If a condition is true, an if-then-else expression evaluates to the then-branch: if c then t else e = t.
sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the set.
binary_partial_word_cube_mem- A function f belongs to the partial-word cube defined by (s, b) if and only if f agrees with b on all coordinates in s.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
if_neg- If a condition is false, an if-then-else expression evaluates to the else-branch: if c then t else e = e.
mul_zero- Multiplying by zero on the right yields zero: a * 0 = 0.
binary_partial_word_cube_odd_sum- If a coordinate v does not belong to s and a function F is odd under flipping the value at v, then the sum of F over the partial-word cube is zero.
Function.update_of_ne- Updating a function at coordinate a' does not change its value at any distinct coordinate a ≠ a'.
Function.update_self- Updating a function at coordinate a with value v evaluates to v at a.
binary_bool_sign_not- Negating a boolean inverts its sign: binary_bool_sign (!b) = -binary_bool_sign b.
zero_mul- Multiplying by zero on the left yields zero: 0 * a = 0.
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_pair_sum {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) (u v : V) (huv : u ≠ v) : (∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (f u) * binary_bool_sign (f v)) = (binary_partial_word_cube s b).card * binary_partial_word_sign s b u * binary_partial_word_sign s b v := by classical by_cases hu : u ∈ s · by_cases hv : v ∈ s · simp only [binary_partial_word_sign, if_pos hu, if_pos hv] calc _ = ∑ f ∈ binary_partial_word_cube s b, binary_bool_sign (b u) * binary_bool_sign (b v) := by apply sum_congr rfl intro f hf rw [(binary_partial_word_cube_mem s b f).mp hf u hu, (binary_partial_word_cube_mem s b f).mp hf v hv] _ = _ := by simp [mul_assoc] · simp only [binary_partial_word_sign, if_pos hu, if_neg hv, mul_zero] apply binary_partial_word_cube_odd_sum s b v hv intro f hf simp only [Function.update_of_ne huv, Function.update_self, binary_bool_sign_not] ring · simp only [binary_partial_word_sign, if_neg hu, mul_zero, zero_mul] apply binary_partial_word_cube_odd_sum s b u hu intro f hf simp only [Function.update_self, Function.update_of_ne huv.symm, binary_bool_sign_not] ring