AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_sign_sum

theoremverified

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

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.

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

    lines 9–10

      classical
      by_cases hv : v ∈ s
  2. When 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.

    lines 11–17

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

    lines 18–21

    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

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