parallel_mw_transfer_sum_eq
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.
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}.
uses
Finset.sum_update_of_mem,Finset.mem_univdsimp [parallel_mw_transfer] rw [Finset.sum_update_of_mem (Finset.mem_univ j)]
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}.
uses
Finset.sum_update_of_memhave hi : i ∈ Finset.univ \ {j} := by simp [hij] rw [Finset.sum_update_of_mem hi]
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.
uses
Function.update_eq_self,Finset.sum_update_of_mem,Finset.mem_univconv_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]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.
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.
- On paper, one would simply note that transferring 1 from q(j) to q(i) preserves the sum because (q(j) - 1) + (q(i) + 1) = q(j) + q(i). Formally, the proof uses `conv_rhs` and `Function.update_eq_self` to rewrite the RHS sum into the exact same shape as the LHS sum before finishing with `omega`.
- The assumption `1 ≤ q j` (hj) is essential for `omega` because subtraction on `ℕ` truncates at zero: without it, `q j - 1 + 1` would not necessarily equal `q j`.
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.
/-- 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