AFTD Auto-Formalizing Theoretical Domains

op1525_flip_mono_pair_sum

theoremverified

For a finite set of pairs with c marked monochromatic, the sum over all individual-vertex flips of the resulting monochromatic-pair count is (2m−4)c+2m, where m is the number of pairs.

Statement

theorem op1525_flip_mono_pair_sum {I : Type*} [Fintype I] (s : I → Bool) :
    let c : ℤ := ∑ i : I, if s i then 1 else 0
    (∑ i : I, 2 * (if s i then c - 1 else c + 1)) =
      (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ)
Source
The monochromatic-pair deck average in the complete pair-part route to OP-1525.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

We compute the sum of the updated monochromatic-pair counts over all individual-vertex flips. For each pair $i$, the term $2(\text{if } s(i) \text{ then } c - 1 \text{ else } c + 1)$ is rewritten pointwise as $2(c+1) - 4 \cdot \mathbf{1}_{s(i)}$. Summing across all pairs, the constant part evaluates to $2|I|(c+1)$ and the indicator part sums to $4c$ by the definition of $c$. Expanding and rearranging terms in $c$ yields $(2|I| - 4)c + 2|I|$.

  1. Define $c$ as the count of monochromatic pairs and set up the target equation.

    We introduce the local definition $c = \sum_{i \in I} (\text{if } s(i) \text{ then } 1 \text{ else } 0)$, representing the number of monochromatic pairs, and restate the theorem's goal using this abbreviation.

    lines 5–8

      classical
      let c : ℤ := ∑ i : I, if s i then 1 else 0
      change (∑ i : I, 2 * (if s i then c - 1 else c + 1)) =
        (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ)
  2. Each term $2(\text{if } s(i) \text{ then } c - 1 \text{ else } c + 1)$ in the sum is algebraically equal to $2(c + 1) - 4(\text{if } s(i) \text{ then } 1 \text{ else } 0)$.

    Using `Finset.sum_congr`, we reduce the equality of the two sums over $I$ to checking that their summands agree for each $i \in I$. A case analysis on the boolean value of $s(i)$ resolves this: if $s(i) = \text{false}$, both sides simplify to $2(c+1)$; if $s(i) = \text{true}$, the left-hand side is $2(c-1)$ and the right-hand side is $2(c+1) - 4$, which are equal by ring arithmetic.

    lines 9–14

    uses Finset.sum_congr

      calc
        (∑ i : I, 2 * (if s i then c - 1 else c + 1)) =
            ∑ i : I, (2 * (c + 1) - 4 * (if s i then 1 else 0)) := by
          apply Finset.sum_congr rfl
          intro i _
          cases h : s i <;> simp [h] <;> ring
  3. The sum $\sum_{i \in I} (2(c + 1) - 4(\text{if } s(i) \text{ then } 1 \text{ else } 0))$ evaluates to $(2|I| - 4)c + 2|I|$.

    Applying `Finset.sum_sub_distrib` splits the sum into $\sum_{i \in I} 2(c+1) - \sum_{i \in I} 4(\text{if } s(i) \text{ then } 1 \text{ else } 0)$. By `Finset.sum_const`, `Finset.card_univ`, and `nsmul_eq_mul`, the sum of the constant $2(c+1)$ over all elements evaluates to $|I| \cdot 2(c+1)$. Factoring out 4 via `Finset.mul_sum` leaves $4 \sum_{i \in I} (\text{if } s(i) \text{ then } 1 \text{ else } 0)$, which equals $4c$ by the definition of $c$. Expanding and collecting terms via ring arithmetic yields $|I| \cdot 2(c+1) - 4c = (2|I| - 4)c + 2|I|$.

    lines 15–20

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

        _ = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ) := by
          rw [Finset.sum_sub_distrib]
          simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, ← Finset.mul_sum]
          have hh : (∑ i : I, if s i then (1 : ℤ) else 0) = c := rfl
          rw [hh]
          ring
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.sum_sub_distrib
The sum of a difference over a finite set equals the difference of the sums: $\sum_{x \in s} (f(x) - g(x)) = \sum_{x \in s} f(x) - \sum_{x \in s} g(x)$.
Finset.sum_const
The sum of a constant value $b$ over a finite set $s$ equals the cardinality of $s$ times $b$ (as natural scalar multiplication).
Finset.card_univ
The cardinality of the universal finset `Finset.univ` of a finite type is the cardinality of the type.
nsmul_eq_mul
Scalar multiplication of a ring element by a natural number $n$ equals multiplication by $n$ cast into the ring: $n • a = ↑n * a$.
Finset.mul_sum
A common factor outside a finite sum distributes across each summand: $a \cdot \sum_{i \in s} f(i) = \sum_{i \in s} a \cdot f(i)$.

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_mono_pair_sum {I : Type*} [Fintype I] (s : I → Bool) :    let c : ℤ := ∑ i : I, if s i then 1 else 0    (∑ i : I, 2 * (if s i then c - 1 else c + 1)) =      (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ) := by  classical  let c : ℤ := ∑ i : I, if s i then 1 else 0  change (∑ i : I, 2 * (if s i then c - 1 else c + 1)) =    (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ)  calc    (∑ i : I, 2 * (if s i then c - 1 else c + 1)) =        ∑ i : I, (2 * (c + 1) - 4 * (if s i then 1 else 0)) := by      apply Finset.sum_congr rfl      intro i _      cases h : s i <;> simp [h] <;> ring    _ = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ) := by      rw [Finset.sum_sub_distrib]      simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, ← Finset.mul_sum]      have hh : (∑ i : I, if s i then (1 : ℤ) else 0) = c := rfl      rw [hh]      ring
See it in the graphDiscuss this resultChallenge it