good_slopes_gap_tight_mod_15
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.
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.
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 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.
uses
good_slopes_gap_tight_mod_15_fhave hc : (good_slopes 15 good_slopes_gap_tight_mod_15_f).card = 6 := by decide refine ⟨good_slopes_gap_tight_mod_15_f, ?_, hc⟩
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.
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
- The invertibility of the candidate permutation and the count of its good slopes are verified by Lean's kernel via exhaustive finite computation (`decide`) over ℤ/15ℤ rather than through an algebraic derivation.
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.
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