AFTD Auto-Formalizing Theoretical Domains

op1525_flip_imbalance_square_sum

theoremverified

For signs on a finite set, the sum over vertices of the squared total sign after flipping that vertex is (n−4) times the original squared total sign plus 4n.

Statement

theorem op1525_flip_imbalance_square_sum {V : Type*} [Fintype V]
    (f : V → ℤ) (h : ∀ v, f v = 1 ∨ f v = -1) :
    (∑ v : V, ((∑ u : V, f u) - 2 * f v)^2) =
      ((Fintype.card V : ℤ) - 4) * (∑ u : V, f u)^2 +
        4 * (Fintype.card V : ℤ)
Source
A switching-deck imbalance identity for OP-1525 and arXiv:2611.13901, Section 4.1.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

We denote the total sign sum ∑ u, f(u) by S and expand each squared term (S - 2f(v))² into S² - 4S f(v) + 4f(v)². Since each sign is ±1, we have f(v)² = 1, so each summand simplifies to S² - 4S f(v) + 4. Distributing the sum over all vertices yields |V|S² - 4S ∑ v, f(v) + 4|V|, which simplifies algebraically to (|V| - 4)S² + 4|V| because ∑ v, f(v) = S.

  1. For every vertex v, f(v)² = 1, and the goal reduces to showing ∑ v, (S - 2f(v))² = (|V| - 4)S² + 4|V|, where S = ∑ u, f(u).

    We define the shorthand S = ∑ u, f(u) for the total sum of signs. Since f(v) is either 1 or -1 for every vertex v, its square is 1² = 1 or (-1)² = 1, hence f(v)² = 1. We then rewrite the target identity in terms of S.

    lines 6–11

      classical
      let S : ℤ := ∑ u : V, f u
      have hf (v : V) : f v ^ 2 = 1 := by
        rcases h v with hv | hv <;> rw [hv] <;> norm_num
      change (∑ v : V, (S - 2 * f v)^2) =
        ((Fintype.card V : ℤ) - 4) * S^2 + 4 * (Fintype.card V : ℤ)
  2. ∑ v, (S - 2f(v))² = ∑ v, (S² - 4S f(v) + 4)

    By congruence of sums (Finset.sum_congr), it suffices to equate the summands pointwise. For any vertex v, expanding the square gives (S - 2f(v))² = S² - 4S f(v) + 4f(v)², and substituting f(v)² = 1 yields S² - 4S f(v) + 4.

    lines 12–18

    uses Finset.sum_congr

      calc
        (∑ v : V, (S - 2 * f v)^2) = ∑ v : V, (S^2 - 4 * S * f v + 4) := by
          apply Finset.sum_congr rfl
          intro v _
          calc
            (S - 2 * f v)^2 = S^2 - 4 * S * f v + 4 * f v^2 := by ring
            _ = S^2 - 4 * S * f v + 4 := by rw [hf]; ring
  3. ∑ v, (S² - 4S f(v) + 4) = (|V| - 4)S² + 4|V|

    Distributing the summation over addition and subtraction (Finset.sum_add_distrib, Finset.sum_sub_distrib) splits the sum into ∑ v, S² - ∑ v, 4S f(v) + ∑ v, 4. Evaluating the constant sums over the universe of size |V| (Finset.sum_const, Finset.card_univ, nsmul_eq_mul) gives |V|S² and 4|V|, while factoring 4S out of the middle sum (Finset.mul_sum) leaves 4S ∑ v, f(v). Since ∑ v, f(v) = S, the expression becomes |V|S² - 4S² + 4|V|, which ring arithmetic rearranges to (|V| - 4)S² + 4|V|.

    lines 19–24

    uses Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, Finset.mul_sum

        _ = ((Fintype.card V : ℤ) - 4) * S^2 + 4 * (Fintype.card V : ℤ) := by
          rw [Finset.sum_add_distrib, Finset.sum_sub_distrib]
          simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, ← Finset.mul_sum]
          have hh : (∑ v : V, f v) = S := rfl
          rw [hh]
          ring
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their summands agree on every element of the set.
Finset.sum_add_distrib
Summing the sum of two functions over a finite set distributes into the sum of the two separate sums.
Finset.sum_sub_distrib
Summing the difference of two functions over a finite set distributes into the difference of the two separate sums.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set multiplied (as an action) by that constant.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
nsmul_eq_mul
Natural number scalar multiplication in a semiring is equal to multiplication by the coerced natural number.
Finset.mul_sum
Multiplication by a factor distributes over a finite sum.

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

theorem op1525_flip_imbalance_square_sum {V : Type*} [Fintype V]    (f : V → ℤ) (h : ∀ v, f v = 1 ∨ f v = -1) :    (∑ v : V, ((∑ u : V, f u) - 2 * f v)^2) =      ((Fintype.card V : ℤ) - 4) * (∑ u : V, f u)^2 +        4 * (Fintype.card V : ℤ) := by  classical  let S : ℤ := ∑ u : V, f u  have hf (v : V) : f v ^ 2 = 1 := by    rcases h v with hv | hv <;> rw [hv] <;> norm_num  change (∑ v : V, (S - 2 * f v)^2) =    ((Fintype.card V : ℤ) - 4) * S^2 + 4 * (Fintype.card V : ℤ)  calc    (∑ v : V, (S - 2 * f v)^2) = ∑ v : V, (S^2 - 4 * S * f v + 4) := by      apply Finset.sum_congr rfl      intro v _      calc        (S - 2 * f v)^2 = S^2 - 4 * S * f v + 4 * f v^2 := by ring        _ = S^2 - 4 * S * f v + 4 := by rw [hf]; ring    _ = ((Fintype.card V : ℤ) - 4) * S^2 + 4 * (Fintype.card V : ℤ) := by      rw [Finset.sum_add_distrib, Finset.sum_sub_distrib]      simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, ← Finset.mul_sum]      have hh : (∑ v : V, f v) = S := rfl      rw [hh]      ring
See it in the graphDiscuss this resultChallenge it