AFTD Auto-Formalizing Theoretical Domains

parallel_mw_transfer_pos

theoremverified

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.

  1. 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.

    line 5

      dsimp [parallel_mw_transfer]
  2. 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.

    lines 6–9

    uses Function.update_self

      by_cases hkj : k = j
      · subst hkj
        rw [Function.update_self]
        omega
  3. 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.

    lines 10–14

    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
  4. 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.

    lines 15–16

    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

/-- 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
See it in the graphDiscuss this resultChallenge it