op1525_flip_imbalance_square_sum
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.
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.
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 : ℤ)
∑ 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.
uses
Finset.sum_congrcalc (∑ 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
∑ 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|.
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
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.
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