binary_partial_word_cube_odd_sum
A rational function which changes sign under flipping a free coordinate of a partial-word cube sums to zero on that cube.
Statement
theorem binary_partial_word_cube_odd_sum {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) (v : V) (hv : v ∉ s) (F : (V → Bool) → ℚ) (hodd : ∀ f ∈ binary_partial_word_cube s b, F (Function.update f v (!f v)) = -F f) : ∑ f ∈ binary_partial_word_cube s b, F f = 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 2
- 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.
- Used by 2
- 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.
The proof, explained
The proof uses the finite sum involution principle (sum_involution) by pairing each function in the partial-word cube with the function obtained by flipping its value at the free coordinate v. Because v is not in the set of fixed coordinates s, this flipping operation preserves the cube, and flipping twice is the identity map with no fixed points. By the anti-symmetry hypothesis, the terms in each pair cancel to zero, so the total sum across the cube is zero.
The operation flip that negates coordinate v is an involution on V → Bool.
We define flip(f) to be the function that agrees with f away from v and negates the value at v. To see that flip is an involution (flip (flip f) = f), we check coordinatewise: at coordinate v, negating twice returns the original boolean value; at any other coordinate w ≠ v, neither flip changes the value.
classical let flip : (V → Bool) → (V → Bool) := fun f => Function.update f v (!f v) have hflip (f : V → Bool) : flip (flip f) = f := by funext w by_cases hw : w = v · subst w simp [flip] · simp [flip, hw]
The partial-word cube binary_partial_word_cube s b is invariant under flip.
By binary_partial_word_cube_mem, membership in the cube requires agreeing with b at all coordinates in s. Since v ∉ s, every coordinate w ∈ s satisfies w ≠ v, so flipping coordinate v does not affect the values on s. Hence if f is in the cube, so is flip(f).
uses
binary_partial_word_cube_memhave hmem (f : V → Bool) (hf : f ∈ binary_partial_word_cube s b) : flip f ∈ binary_partial_word_cube s b := by rw [binary_partial_word_cube_mem] at hf ⊢ intro w hw have hne : w ≠ v := by rintro rfl; exact hv hw simpa [flip, hne] using hf w hw
By the sum involution principle, it suffices to show that paired values cancel and that flip has no fixed points with non-zero value.
We apply sum_involution with the involution flip. Because flip preserves membership in the cube and satisfies flip (flip f) = f, the sum ∑_{f} F(f) over the cube vanishes once we verify two conditions: F(f) + F(flip(f)) = 0 for all f in the cube, and flip(f) ≠ f whenever F(f) ≠ 0.
uses
sum_involutionrefine sum_involution (fun f hf => flip f) ?_ ?_ hmem (fun f hf => hflip f)
For every f in the partial-word cube, F(f) + F(flip(f)) = 0.
By the odd-symmetry hypothesis hodd, F(flip(f)) = -F(f). Adding F(f) to both sides yields F(f) + (-F(f)) = 0.
· intro f hf change F f + F (Function.update f v (!f v)) = 0 rw [hodd f hf] ring
The involution flip has no fixed points on functions V → Bool.
If flip(f) = f, then evaluating both sides at coordinate v using congrArg gives flip(f)(v) = f(v). By Function.update_self, flip(f)(v) = !f(v), so !f(v) = f(v). Considering the two cases f(v) = false and f(v) = true, both lead immediately to a contradiction, so no function can be fixed by flip.
uses
congrArg,Function.update_self· intro f hf hF h have he := congrArg (fun g : V → Bool => g v) h simp only [flip, Function.update_self] at he cases hfv : f v <;> simp [hfv] at he
binary_partial_word_cube_mem- A function f belongs to the partial-word cube defined by s and b if and only if f agrees with b on all coordinates in s.
congrArg- If x = y, then g(x) = g(y) for any function g.
Function.update_self- Evaluating an updated function at the updated coordinate yields the new value.
sum_involution- A finite sum ∑_{x ∈ s} f(x) vanishes if there is an involution g on s such that f(x) + f(g(x)) = 0 for all x ∈ s, and g has no fixed points on the support of f.
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_odd_sum {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) (v : V) (hv : v ∉ s) (F : (V → Bool) → ℚ) (hodd : ∀ f ∈ binary_partial_word_cube s b, F (Function.update f v (!f v)) = -F f) : ∑ f ∈ binary_partial_word_cube s b, F f = 0 := by classical let flip : (V → Bool) → (V → Bool) := fun f => Function.update f v (!f v) have hflip (f : V → Bool) : flip (flip f) = f := by funext w by_cases hw : w = v · subst w simp [flip] · simp [flip, hw] have hmem (f : V → Bool) (hf : f ∈ binary_partial_word_cube s b) : flip f ∈ binary_partial_word_cube s b := by rw [binary_partial_word_cube_mem] at hf ⊢ intro w hw have hne : w ≠ v := by rintro rfl; exact hv hw simpa [flip, hne] using hf w hw refine sum_involution (fun f hf => flip f) ?_ ?_ hmem (fun f hf => hflip f) · intro f hf change F f + F (Function.update f v (!f v)) = 0 rw [hodd f hf] ring · intro f hf hF h have he := congrArg (fun g : V → Bool => g v) h simp only [flip, Function.update_self] at he cases hfv : f v <;> simp [hfv] at he