AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_odd_sum

theoremverified

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
Used by 2

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.

  1. 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.

    lines 11–18

      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]
  2. 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).

    lines 19–24

    uses binary_partial_word_cube_mem

      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
  3. 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.

    line 25

    uses sum_involution

      refine sum_involution (fun f hf => flip f) ?_ ?_ hmem (fun f hf => hflip f)
  4. 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.

    lines 26–29

      · intro f hf
        change F f + F (Function.update f v (!f v)) = 0
        rw [hodd f hf]
        ring
  5. 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.

    lines 30–33

    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

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
See it in the graphDiscuss this resultChallenge it