AFTD Auto-Formalizing Theoretical Domains

parallel_mw_transfer_sum_eq

theoremverified

For any natural number n, any function q : Fin n → ℕ, and any indices i, j : Fin n with i ≠ j and 1 ≤ q j, the sum of parallel_mw_transfer q i j k over all k : Fin n equals the sum of q k over all k : Fin n.

Statement

theorem parallel_mw_transfer_sum_eq {n : ℕ} (q : Fin n → ℕ) (i j : Fin n)
    (hij : i ≠ j) (hj : 1 ≤ q j) :
    ∑ k : Fin n, parallel_mw_transfer q i j k = ∑ k : Fin n, q k
Source
folklore
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • parallel_mw_transferFor a natural number n, a function q : Fin n → ℕ, and indices i, j : Fin n, parallel_mw_transfer q i j is the function Fin n → ℕ defined…

Read back from the Lean

For any natural number $n$, any function $q : \mathrm{Fin}\ n \to \mathbb{N}$, and any two distinct indices $i, j : \mathrm{Fin}\ n$ (i.e., $i \neq j$) such that $1 \le q(j)$, the sum over all $k : \mathrm{Fin}\ n$ of $\mathrm{parallel\_mw\_transfer}(q, i, j)(k)$ equals the sum over all $k : \mathrm{Fin}\ n$ of $q(k)$, where $\mathrm{parallel\_mw\_transfer}(q, i, j)$ is the function obtained by incrementing $q(i)$ by 1 and decrementing $q(j)$ by 1.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof isolates the terms at indices j and i from the sums on both sides of the equation. On the left-hand side, expanding the definition of the transfer and extracting indices j and i produces (q(j) - 1) + (q(i) + 1) plus the sum over the remaining indices. Decomposing the right-hand side identically produces q(j) + q(i) plus the same remaining sum; the two expressions are equal by linear arithmetic since q(j) ≥ 1.

  1. The left-hand sum is expanded and the term at index j is extracted.

    We unfold the definition of parallel_mw_transfer, which updates q at index i to q(i) + 1 and at index j to q(j) - 1. Because j is in the universe of all indices (Finset.mem_univ j), Finset.sum_update_of_mem extracts the value at j, namely q(j) - 1, leaving a sum over all remaining indices Finset.univ \ {j}.

    lines 5–6

    uses Finset.sum_update_of_mem, Finset.mem_univ

      dsimp [parallel_mw_transfer]
      rw [Finset.sum_update_of_mem (Finset.mem_univ j)]
  2. The left-hand sum is separated into the values at j and i plus the sum over the remaining indices.

    Since i ≠ j (hypothesis hij), index i belongs to Finset.univ \ {j}, established by simp. Using Finset.sum_update_of_mem with this membership fact extracts the updated value at i, which is q(i) + 1, leaving the sum of the unmodified function q over (Finset.univ \ {j}) \ {i}.

    lines 7–8

    uses Finset.sum_update_of_mem

      have hi : i ∈ Finset.univ \ {j} := by simp [hij]
      rw [Finset.sum_update_of_mem hi]
  3. The right-hand sum is decomposed into q(j), q(i), and the sum of q over the remaining indices.

    Focusing on the right-hand side with conv_rhs, we view q as an update of itself at j (using Function.update_eq_self) and extract q(j) using Finset.sum_update_of_mem. We then navigate to the remaining sum over Finset.univ \ {j}, view q as an update of itself at i, and extract q(i) via Finset.sum_update_of_mem.

    lines 9–14

    uses Function.update_eq_self, Finset.sum_update_of_mem, Finset.mem_univ

      conv_rhs =>
        rw [← Function.update_eq_self j q]
        rw [Finset.sum_update_of_mem (Finset.mem_univ j)]
        right
        rw [← Function.update_eq_self i q]
        rw [Finset.sum_update_of_mem hi]
  4. The two sums are equal. automation

    Both sides now consist of the sum of q over (Finset.univ \ {j}) \ {i} plus the terms at j and i: the LHS has (q(j) - 1) + (q(i) + 1), while the RHS has q(j) + q(i). Since 1 ≤ q(j) (hypothesis hj), these two quantities are equal by linear integer arithmetic over ℕ, which omega solves.

    line 15

      omega
Finset.sum_update_of_mem
If an element i belongs to a finite set s, then the sum of Function.update f i b over s equals b plus the sum of the original function f over s \ {i}.
Finset.mem_univ
Every element of a finite type belongs to its universal finite set Finset.univ.
Function.update_eq_self
Updating a function f at an argument a with its existing value f(a) returns f itself.

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

/-- A transfer between distinct indices preserves the sum of parallel-class sizes. -/theorem parallel_mw_transfer_sum_eq {n : ℕ} (q : Fin n → ℕ) (i j : Fin n)    (hij : i ≠ j) (hj : 1 ≤ q j) :    ∑ k : Fin n, parallel_mw_transfer q i j k = ∑ k : Fin n, q k := by  dsimp [parallel_mw_transfer]  rw [Finset.sum_update_of_mem (Finset.mem_univ j)]  have hi : i ∈ Finset.univ \ {j} := by simp [hij]  rw [Finset.sum_update_of_mem hi]  conv_rhs =>    rw [← Function.update_eq_self j q]    rw [Finset.sum_update_of_mem (Finset.mem_univ j)]    right    rw [← Function.update_eq_self i q]    rw [Finset.sum_update_of_mem hi]  omega
See it in the graphDiscuss this resultChallenge it