fin_sub_rev_comm
In Fin m (m > 0), i - (m - 1 - j) = j - (m - 1 - i), both being i + j + 1 mod m.
Statement
theorem fin_sub_rev_comm {m : ℕ} [NeZero m] (i j : Fin m) : i - j.rev = j - i.rev- Source
- helper for X R = R Xᵀ for circulant X, arXiv:2610.27175 Theorem 3/5
- Verified
- 22 Oct 2026
- Axioms
Quot.soundpropext- Used by 1
- circulant_mul_back_identity_matrixFor a circulant integer matrix X of order m > 0 and the back-identity matrix R, X R = R Xᵀ.
The proof, explained
The theorem states that in Fin m, i - j.rev = j - i.rev. By unfolding the definitions of subtraction and reversal in Fin m, the equality reduces to showing that (m - (m - (j + 1)) + i) % m equals (m - (m - (i + 1)) + j) % m. Because i < m and j < m, the double subtractions simplify to j + 1 and i + 1, respectively. Consequently, both expressions evaluate to i + j + 1 before reduction modulo m, so their remainders modulo m are identical.
Equality in Fin m reduces to the modular identity (m - (m - (j + 1)) + i) % m = (m - (m - (i + 1)) + j) % m.
By Fin.ext_iff, equality in Fin m is equivalent to equality of the underlying natural numbers. Rewriting with Fin.sub_def replaces subtraction with its definition (m - b + a) % m, and simplifying with Fin.val_rev substitutes n - (k + 1) for each reversal k.rev and strips the subtype coercions.
uses
Fin.ext_iff,Fin.sub_def,Fin.val_revrw [Fin.ext_iff, Fin.sub_def, Fin.sub_def] simp only [Fin.val_rev]
The expressions before reduction modulo m are equal, completing the proof.
Because i and j belong to Fin m, their values satisfy i < m and j < m (recorded as hi and hj). For any k < m, natural subtraction satisfies m - (m - (k + 1)) = k + 1, so both sides simplify to i + j + 1. The linear arithmetic tactic omega verifies this to establish h1 : m - (m - (j + 1)) + i = m - (m - (i + 1)) + j, and rewriting the goal by h1 makes both sides identical.
have hi := i.isLt have hj := j.isLt have h1 : m - (m - (j + 1)) + i = m - (m - (i + 1)) + j := by omega rw [h1]
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural values are equal.
Fin.sub_def- Subtraction a - b in Fin n is defined by taking (n - b + a) % n as the underlying value.
Fin.val_rev- The underlying natural value of the reversal i.rev in Fin n is n - (i + 1).
- In Lean, subtraction on Fin m is defined on natural numbers as (m - b + a) % m to avoid negative values.
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.
theorem fin_sub_rev_comm {m : ℕ} [NeZero m] (i j : Fin m) : i - j.rev = j - i.rev := by rw [Fin.ext_iff, Fin.sub_def, Fin.sub_def] simp only [Fin.val_rev] have hi := i.isLt have hj := j.isLt have h1 : m - (m - (j + 1)) + i = m - (m - (i + 1)) + j := by omega rw [h1]