AFTD Auto-Formalizing Theoretical Domains

good_slopes_gap_tight_mod_15

theoremverifiedformalization

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

Statement

theorem good_slopes_gap_tight_mod_15 : ∃ f : Equiv.Perm (ZMod 15), ¬ is_extremal_perm 15 f ∧ (good_slopes 15 f).card = 6
Formalizes
arXiv:2611.04551 Proposition 9.6
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}/15\mathbb{Z}$ such that $f$ is not an extremal permutation for $n = 15$ (i.e., its number of good slopes is not equal to $\varphi(15) = 8$) and the number of good slopes of $f$ in $\mathbb{Z}/15\mathbb{Z}$ is equal to 6.

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

The theorem is proved by exhibiting an explicit permutation f of ℤ/15ℤ that doubles elements divisible by 3 and fixes all other elements. An exhaustive finite check shows that f has exactly 6 good slopes. Because an extremal permutation on ℤ/15ℤ would have φ(15) = 8 good slopes, f is non-extremal, demonstrating that the gap bound of 6 good slopes is attained.

  1. The map f on ℤ/15ℤ that doubles multiples of 3 and fixes all other elements is an invertible permutation. automation

    We define candidate forward and inverse functions on ℤ/15ℤ: the forward function doubles elements whose representative is divisible by 3 and fixes others, while the inverse function multiplies elements divisible by 3 by 8 (since 2 * 8 = 16 ≡ 1 mod 15) and fixes others. The left and right inverse properties are verified by finite exhaustive case checking via decide.

    lines 1–5

    def good_slopes_gap_tight_mod_15_f : Equiv.Perm (ZMod 15) where
      toFun x := if x.val % 3 == 0 then 2 * x else x
      invFun y := if y.val % 3 == 0 then 8 * y else y
      left_inv := by decide
      right_inv := by decide
  2. The permutation f has exactly 6 good slopes, reducing the existential claim to showing that f is not extremal.

    Lean's decide tactic checks bijectivity of x ↦ f(x) + mx for all 15 candidate slopes m ∈ ℤ/15ℤ by exhaustive computation, establishing that exactly 6 slopes are good (hc). Supplying f as the existential witness and hc for the cardinality conjunct reduces the goal to showing that f is not an extremal permutation.

    lines 9–10

    uses good_slopes_gap_tight_mod_15_f

      have hc : (good_slopes 15 good_slopes_gap_tight_mod_15_f).card = 6 := by decide
      refine ⟨good_slopes_gap_tight_mod_15_f, ?_, hc⟩
  3. The permutation f is not extremal, which completes the proof.

    We assume for contradiction that f is extremal. Unfolding the definition of is_extremal_perm, this assumption means that the number of good slopes equals φ(15). Rewriting with the previously established count of 6 yields 6 = φ(15). Since φ(15) = 8 ≠ 6, this is an immediate arithmetic contradiction, which decide evaluates to complete the proof.

    lines 11–15

      intro h
      change (good_slopes 15 good_slopes_gap_tight_mod_15_f).card = Nat.totient 15 at h
      rw [hc] at h
      revert h
      decide
good_slopes_gap_tight_mod_15_f
the permutation of ℤ/15ℤ that maps x to 2x when x ≡ 0 (mod 3) and fixes x otherwise

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_15_f : Equiv.Perm (ZMod 15) where  toFun x := if x.val % 3 == 0 then 2 * x else x  invFun y := if y.val % 3 == 0 then 8 * y else y  left_inv := by decide  right_inv := by decide/-- The gap bound φ(15)(5 - 2)/(5 - 1) = 6 for good slopes on ℤ/15ℤ is sharp: there exists a non-extremal permutation of ℤ/15ℤ with exactly 6 good slopes. -/theorem good_slopes_gap_tight_mod_15 : ∃ f : Equiv.Perm (ZMod 15), ¬ is_extremal_perm 15 f ∧ (good_slopes 15 f).card = 6 := by  have hc : (good_slopes 15 good_slopes_gap_tight_mod_15_f).card = 6 := by decide  refine ⟨good_slopes_gap_tight_mod_15_f, ?_, hc⟩  intro h  change (good_slopes 15 good_slopes_gap_tight_mod_15_f).card = Nat.totient 15 at h  rw [hc] at h  revert h  decide
See it in the graphDiscuss this resultChallenge it