AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_sign_pair_sum

theoremverified

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

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.

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

    lines 10–21

    uses if_pos, sum_congr, binary_partial_word_cube_mem, mul_assoc

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

    lines 22–26

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

    lines 27–31

    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

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