AFTD Auto-Formalizing Theoretical Domains

good_slopes_mem_iff

theoremverified

A slope m is good for the permutation f of ℤ/nℤ exactly when x ↦ f(x) + m·x is a bijection of ℤ/nℤ: m ∈ D_n(f) ↔ Function.Bijective (fun x => f x + m * x).

Statement

theorem good_slopes_mem_iff (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) (m : ZMod n) : m ∈ good_slopes n f ↔ Function.Bijective (fun x => f x + m * x)
Source
step towards good_slopes_gap_mod_105
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…
  • prime_shift_multiples_bijectiveIn the finite field ZMod n where n is prime, multiplication by any non-zero element s induces a bijection on ZMod n.
Used by 4
  • good_slopes_missing_prime_squarefreeLet n be squarefree and nonzero, let the prime p divide n, and let f be a permutation modulo n. Then some residue modulo p is missed by…
  • good_slopes_gap_mod_105Every non-extremal permutation f of ℤ/105ℤ satisfies |D_{105}(f)| ≤ 40: (good_slopes 105 f).card ≤ 40.
  • zero_mem_good_slopesZero is always a good slope of every permutation of ℤ/nℤ, since x ↦ f(x) + 0·x = f(x) is a permutation; in particular D_n(f) is nonempty:…
  • 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…

The proof, explained

The equivalence follows immediately from the definition of the set of good slopes. By definition, `good_slopes n f` is the sub-finset of ℤ/nℤ consisting of those m for which the map x ↦ f(x) + m · x is bijective. Unfolding this definition reduces the membership claim to a tautology, which is discharged by the simplifier.

  1. m ∈ good_slopes n f ↔ Function.Bijective (fun x => f x + m * x) automation

    The script tries several automated strategies using `first`. It unfolds the definition of `good_slopes n f`, which is defined as the subset of elements m in ℤ/nℤ for which the map x ↦ f(x) + m · x is bijective. Once this definition is unfolded, testing membership in the filtered finset is definitionally equivalent to the bijectivity condition itself, which the simplifier reduces and solves.

    line 2

    uses prime_shift_multiples_bijective

    theorem good_slopes_mem_iff (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) (m : ZMod n) : m ∈ good_slopes n f ↔ Function.Bijective (fun x => f x + m * x) := by first | exact prime_shift_multiples_bijective | (apply prime_shift_multiples_bijective <;> assumption) | (apply prime_shift_multiples_bijective <;> simp_all) | simpa using prime_shift_multiples_bijective | (simp only [good_slopes] at *; first | exact prime_shift_multiples_bijective | (apply prime_shift_multiples_bijective <;> assumption) | (apply prime_shift_multiples_bijective <;> simp_all) | simpa using prime_shift_multiples_bijective)
prime_shift_multiples_bijective
For a prime n and any non-zero element s in ℤ/nℤ, the scaling map k ↦ k · s is bijective.

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

/-- Membership characterization of the good-slope set, unfolding the definition. -/theorem good_slopes_mem_iff (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) (m : ZMod n) : m ∈ good_slopes n f ↔ Function.Bijective (fun x => f x + m * x) := by first | exact prime_shift_multiples_bijective | (apply prime_shift_multiples_bijective <;> assumption) | (apply prime_shift_multiples_bijective <;> simp_all) | simpa using prime_shift_multiples_bijective | (simp only [good_slopes] at *; first | exact prime_shift_multiples_bijective | (apply prime_shift_multiples_bijective <;> assumption) | (apply prime_shift_multiples_bijective <;> simp_all) | simpa using prime_shift_multiples_bijective)
See it in the graphDiscuss this resultChallenge it