AFTD Auto-Formalizing Theoretical Domains

zmod3_perm_is_affine

theoremverified

Every bijection f : ZMod 3 → ZMod 3 is affine: there exist a, b ∈ ZMod 3 with a ≠ 0 such that f(t) = a * t + b for all t ∈ ZMod 3.

Statement

theorem zmod3_perm_is_affine (f : ZMod 3 → ZMod 3) (hf : Function.Bijective f) : ∃ (a b : ZMod 3), a ≠ 0 ∧ ∀ t, f t = a * t + b
Source
step towards ternary_minimal_line_cover_minimum_card_eq_hyperplane
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

The proof, explained

Every permutation of the three-element field ℤ/3ℤ is affine because there are only 3! = 6 permutations, and exactly 2 × 3 = 6 non-constant affine maps t ↦ a * t + b (with a ≠ 0). The proof generalizes the goal to all functions f : ℤ/3ℤ → ℤ/3ℤ and then dispatches the theorem by exhaustive finite computation using the `decide` tactic.

  1. It suffices to show that every function f : ℤ/3ℤ → ℤ/3ℤ that is bijective has an affine representation.

    Reverting the function f (along with the assumption that f is bijective) transforms the goal into a universally quantified sentence over all functions from ℤ/3ℤ to ℤ/3ℤ. Because ℤ/3ℤ is a finite type, this universal quantification ranges over a finite domain of 3³ = 27 functions.

    line 3

      revert f
  2. Every bijection on ℤ/3ℤ is affine: there exist a, b ∈ ℤ/3ℤ with a ≠ 0 such that f(t) = a * t + b for all t. automation

    Because both the domain ℤ/3ℤ → ℤ/3ℤ and the existential search space for parameters a, b ∈ ℤ/3ℤ are finite, the statement is purely decidable. The `decide` tactic checks the claim by finite exhaustion, verifying for each of the 6 permutations of ℤ/3ℤ that an appropriate choice of a ≠ 0 and b exists.

    line 4

      decide

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

/-- Every permutation of ZMod 3 is an affine map t ↦ a * t + b with a ≠ 0. -/theorem zmod3_perm_is_affine (f : ZMod 3 → ZMod 3) (hf : Function.Bijective f) : ∃ (a b : ZMod 3), a ≠ 0 ∧ ∀ t, f t = a * t + b := by  revert f  decide
See it in the graphDiscuss this resultChallenge it