AFTD Auto-Formalizing Theoretical Domains

good_slopes_gap_tight_mod_45

theoremverifiedformalization

There exists a non-extremal permutation f of ℤ/45ℤ with exactly 18 good slopes, demonstrating that the gap bound φ(45)(q - 2)/(q - 1) = 18 is attained for n = 45.

Statement

theorem good_slopes_gap_tight_mod_45 : ∃ f : Equiv.Perm (ZMod 45), ¬ is_extremal_perm 45 f ∧ (good_slopes 45 f).card = 18
Formalizes
arXiv:2611.04551 Section 9, lines 4426-4443
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • is_extremal_permGiven 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…

Read back from the Lean

There exists a permutation $f$ of $\mathbb{Z}/45\mathbb{Z}$ such that $f$ is not an extremal permutation (meaning the cardinality of its set of good slopes is not equal to $\phi(45)$) and the cardinality of the set of good slopes of $f$ is equal to 18.

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

The proof, explained

We show 18 is attained.

  1. The function f is a valid permutation. automation

    Both left and right invertibility are verified by finite check over ZMod 45.

    lines 4–7

      left_inv x := by
        revert x; decide
      right_inv y := by
        revert y; decide
  2. The number of good slopes of f is 18. automation

    Decide by computation.

    line 11

      have hc : (good_slopes 45 good_slopes_gap_tight_mod_45_f).card = 18 := by decide
  3. We choose f as witness.

    We provide f.

    line 12

      refine ⟨good_slopes_gap_tight_mod_45_f, ?_, hc⟩
  4. Assume f is extremal to derive a contradiction.

    Contradiction.

    lines 13–16

      intro h
      change (good_slopes 45 good_slopes_gap_tight_mod_45_f).card = Nat.totient 45 at h
      rw [hc] at h
      revert h
  5. Contradiction because 18 != 24. automation

    Computation.

    line 17

      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

def good_slopes_gap_tight_mod_45_f : Equiv.Perm (ZMod 45) where  toFun x := if x.val % 9 == 0 then 2 * x else x  invFun y := if y.val % 9 == 0 then 23 * y else y  left_inv x := by    revert x; decide  right_inv y := by    revert y; decide/-- The gap bound φ(45)(5 - 2)/(5 - 1) = 18 for good slopes on ℤ/45ℤ is sharp: there exists a non-extremal permutation of ℤ/45ℤ with exactly 18 good slopes. -/theorem good_slopes_gap_tight_mod_45 : ∃ f : Equiv.Perm (ZMod 45), ¬ is_extremal_perm 45 f ∧ (good_slopes 45 f).card = 18 := by  have hc : (good_slopes 45 good_slopes_gap_tight_mod_45_f).card = 18 := by decide  refine ⟨good_slopes_gap_tight_mod_45_f, ?_, hc⟩  intro h  change (good_slopes 45 good_slopes_gap_tight_mod_45_f).card = Nat.totient 45 at h  rw [hc] at h  revert h  decide
See it in the graphDiscuss this resultChallenge it