parallel_mw_transfer_pos
For any natural number n, any function q : Fin n → ℕ such that 0 < q k for all k : Fin n, and any indices i, j : Fin n with q i + 2 ≤ q j, 0 < parallel_mw_transfer q i j k for every k : Fin n.
Statement
theorem parallel_mw_transfer_pos {n : ℕ} (q : Fin n → ℕ) (hq : ∀ k, 0 < q k)
(i j : Fin n) (hij : q i + 2 ≤ q j) (k : Fin n) :
0 < parallel_mw_transfer q i j k- Source
- folklore
- Verified
- 30 Oct 2026
- Axioms
Quot.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 : \text{Fin } n \to \mathbb{N}$ such that $0 < q(k)$ for all $k \in \text{Fin } n$, any elements $i, j \in \text{Fin } n$ such that $q(i) + 2 \le q(j)$, and any $k \in \text{Fin } n$, the value $\text{parallel\_mw\_transfer}(q, i, j)(k)$ is strictly greater than $0$.
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 theorem is proved by unfolding the definition of parallel_mw_transfer—which decreases component j by 1 and increases component i by 1—and analyzing the three possible positions of index k relative to i and j. If k = j, the entry becomes q j - 1, which remains positive since q j ≥ q i + 2 ≥ 3. If k = i, the entry becomes q i + 1 > 0. If k is distinct from both indices, the entry is unchanged and therefore positive by assumption.
Expanding the definition of the transfer operation expresses the goal in terms of function updates.
Unfolding the definition of `parallel_mw_transfer` rewrites the goal into showing that the doubly updated function (incrementing at index i and decrementing at index j) has a positive value at index k.
dsimp [parallel_mw_transfer]If k = j, the updated value is strictly positive.
Assuming k = j, the outer update evaluates to q j - 1 by Function.update_self. Since q i ≥ 1 and q j ≥ q i + 2, we have q j ≥ 3, which implies q j - 1 > 0 by linear integer arithmetic.
uses
Function.update_selfby_cases hkj : k = j · subst hkj rw [Function.update_self] omega
If k ≠ j and k = i, the updated value is strictly positive.
Because k ≠ j, Function.update_of_ne shows the outer update at j leaves index k unaffected, leaving the inner update at i. In the case k = i, Function.update_self evaluates this to q i + 1, which is strictly positive by linear integer arithmetic.
uses
Function.update_of_ne,Function.update_self· rw [Function.update_of_ne hkj] by_cases hki : k = i · subst hki rw [Function.update_self] omega
If k ≠ j and k ≠ i, the updated value is strictly positive.
Because k ≠ i, Function.update_of_ne reduces the remaining update to q k. The assumption that all entries of q are strictly positive immediately yields 0 < q k.
uses
Function.update_of_ne· rw [Function.update_of_ne hki] exact hq k
Function.update_self- Evaluating an updated function at the updated point yields the new value.
Function.update_of_ne- Evaluating a function updated at a point a' at a different point a ≠ a' yields the original function value at a.
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 classes with q_j ≥ q_i + 2 preserves positivity of all entries. -/theorem parallel_mw_transfer_pos {n : ℕ} (q : Fin n → ℕ) (hq : ∀ k, 0 < q k) (i j : Fin n) (hij : q i + 2 ≤ q j) (k : Fin n) : 0 < parallel_mw_transfer q i j k := by dsimp [parallel_mw_transfer] by_cases hkj : k = j · subst hkj rw [Function.update_self] omega · rw [Function.update_of_ne hkj] by_cases hki : k = i · subst hki rw [Function.update_self] omega · rw [Function.update_of_ne hki] exact hq k