AFTD Auto-Formalizing Theoretical Domains

fin_sub_rev_comm

theoremverified

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

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.

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

    lines 2–3

    uses Fin.ext_iff, Fin.sub_def, Fin.val_rev

      rw [Fin.ext_iff, Fin.sub_def, Fin.sub_def]
      simp only [Fin.val_rev]
  2. 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.

    lines 4–7

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

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

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