zmod3_perm_is_affine
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
- latin_hypercube_is_affineEvery order-3 Latin hypercube f : (Fin m → ZMod 3) → ZMod 3 (a function whose restriction to every 1D coordinate line is a bijection) is…
- ternary_minimal_line_cover_minimum_card_eq_hyperplaneFor every natural number n ≥ 1 and every inclusion-minimal ternary line cover B in (Fin n → ZMod 3) with cardinality 3^(n - 1), B is an…
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.
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.
revert f
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.
decide
- The entire proof is executed by computational reflection (`decide`), which checks all cases by brute force rather than through a paper-style algebraic argument (such as counting that both the group of permutations and the group of affine transformations have size 6).
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.
/-- 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