AFTD Auto-Formalizing Theoretical Domains

is_extremal_perm

def

Given n with [NeZero n], a permutation f of ℤ/nℤ is extremal if the number of its good slopes (the cardinality of good_slopes n f) equals φ(n), where φ is Euler's totient function (Nat.totient n).

Statement

def is_extremal_perm (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) : Prop
Defined in
arXiv:2611.04551 Section 2
Verified
04 Nov 2026
Axioms
none listed
Built on 1
  • good_slopesGiven a natural number n with n ≠ 0 (via [NeZero n]) and a permutation f of ℤ/nℤ, good_slopes n f is the finite set (Finset) of elements m…
Used by 4
  • good_slopes_gap_tight_mod_45There exists a non-extremal permutation f of ℤ/45ℤ with exactly 18 good slopes, demonstrating that the gap bound φ(45)(q - 2)/(q - 1) = 18…
  • good_slopes_gap_mod_105Every non-extremal permutation f of ℤ/105ℤ satisfies |D_{105}(f)| ≤ 40: (good_slopes 105 f).card ≤ 40.
  • good_slopes_gap_three_coprime_from_fiber_boundsLet k be a nonzero natural number coprime to 3 and let f be a non-extremal permutation modulo 3k. Suppose there are L units modulo k and 0…
  • good_slopes_gap_tight_mod_15There exists a non-extremal permutation f of ℤ/15ℤ with exactly 6 good slopes, demonstrating that the gap bound φ(15)(q - 2)/(q - 1) = 6…

Read back from the Lean

Given a non-zero natural number $n$ and a permutation $f$ of $\mathbb{Z}/n\mathbb{Z}$, is_extremal_perm n f asserts that the cardinality of good_slopes n f is equal to Euler's totient of $n$ (Nat.totient n).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A permutation f of ZMod n is extremal if its number of good slopes attains Euler's totient function. -/
def is_extremal_perm (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) : Prop :=
  (good_slopes n f).card = Nat.totient n
See it in the graphDiscuss this resultChallenge it