good_slopes_unit_cover_squarefree
For every nonzero squarefree modulus and permutation, some unit can be added to all its good slopes to make them units.
Statement
theorem good_slopes_unit_cover_squarefree (n : ℕ) [NeZero n] (hn : Squarefree n) (f : Equiv.Perm (ZMod n)) : ∃ c : ZMod n, IsUnit c ∧ ∀ m ∈ good_slopes n f, IsUnit (m+c)- Source
- Squarefree specialization of the unit-cover part of arXiv:2611.01465 Theorem 3.1, using good_slopes_missing_prime_squarefree.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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…
- 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:…
The proof, explained
To find a unit c in ℤ/nℤ such that m + c is a unit for every good slope m, we use the fact that an element of ℤ/nℤ is invertible if and only if its reduction modulo each prime divisor of n is nonzero. Because n is squarefree, the reduction of good slopes modulo any prime factor p of n misses at least one residue a_p in ℤ/pℤ. Using the Chinese Remainder Theorem, we construct an element c in ℤ/nℤ such that c ≡ -a_p (mod p) for every prime divisor p of n, which guarantees that (m + c) mod p = m - a_p ≠ 0 for all good slopes m and primes p ∣ n. Finally, since 0 is always a good slope, c = 0 + c is itself a unit.
An element x ∈ ℤ/nℤ is a unit if and only if its reduction modulo every prime divisor p of n is nonzero.
An element x is a unit if and only if its representative x.val is coprime to n (ZMod.isUnit_iff_coprime). If x.val and n are coprime, then no prime divisor p of n can divide x.val, so x cannot reduce to 0 modulo p (Nat.Prime.not_coprime_iff_dvd.mpr). Conversely, if x.val is not coprime to n, there exists a common prime factor p dividing both x.val and n (Nat.Prime.not_coprime_iff_dvd.mp), which makes the reduction of x modulo p equal to zero.
uses
ZMod.isUnit_iff_coprime,ZMod.natCast_zmod_val,map_natCast,ZMod.natCast_eq_zero_iff,Nat.Prime.not_coprime_iff_dvd.mpr,Nat.Prime.not_coprime_iff_dvd.mphave isUnit_iff_forall_prime (x : ZMod n) : IsUnit x ↔ ∀ (p : ℕ) (hp : Nat.Prime p) (hd : p ∣ n), ZMod.castHom hd (ZMod p) x ≠ 0 := by have hunit : IsUnit x ↔ Nat.Coprime x.val n := by simpa only [ZMod.natCast_zmod_val] using (ZMod.isUnit_iff_coprime x.val n) rw [hunit] constructor · intro hcop p hp hd hz have hcast : ZMod.castHom hd (ZMod p) x = (x.val : ZMod p) := by conv_lhs => rw [← ZMod.natCast_zmod_val x] exact map_natCast _ _ rw [hcast] at hz have hdvd : p ∣ x.val := (ZMod.natCast_eq_zero_iff x.val p).mp hz have : ∃ q, Nat.Prime q ∧ q ∣ x.val ∧ q ∣ n := ⟨p, hp, hdvd, hd⟩ exact Nat.Prime.not_coprime_iff_dvd.mpr this hcop · intro h by_contra hnc obtain ⟨p, hp, hpx, hpn⟩ := Nat.Prime.not_coprime_iff_dvd.mp hnc have hz : (x.val : ZMod p) = 0 := (ZMod.natCast_eq_zero_iff x.val p).mpr hpx have hcast : ZMod.castHom hpn (ZMod p) x = (x.val : ZMod p) := by conv_lhs => rw [← ZMod.natCast_zmod_val x] exact map_natCast _ _ exact (h p hp hpn) (hcast.trans hz)
For each prime factor p of n, there exists a residue a(p) ∈ ℤ/pℤ that is not the reduction of any good slope of f.
Because n is squarefree, an existing theorem (good_slopes_missing_prime_squarefree) ensures that for each prime p ∣ n, the image of the good slopes under reduction modulo p is not surjective on ℤ/pℤ. We apply the axiom of choice (choose) to associate to each prime factor p a missing residue class a(p).
uses
Nat.prime_of_mem_primeFactors,Nat.dvd_of_mem_primeFactors,good_slopes_missing_prime_squarefreehave h (p : ℕ) (hp : p ∈ n.primeFactors) : ∃ a : ZMod p, ∀ m ∈ good_slopes n f, ZMod.castHom (Nat.dvd_of_mem_primeFactors hp) (ZMod p) m ≠ a := by have hp_prime := Nat.prime_of_mem_primeFactors hp have : NeZero p := ⟨hp_prime.ne_zero⟩ exact good_slopes_missing_prime_squarefree n p hn hp_prime (Nat.dvd_of_mem_primeFactors hp) f choose a ha using h
There exists an integer k such that k ≡ -a(p) (mod p) for every prime factor p of n.
We define a remainder function mapping each prime factor p of n to (-a(p)).val, and verify that its reduction in ℤ/pℤ is -a(p) (dif_pos, ZMod.natCast_zmod_val). The prime factors of n are nonzero and pairwise distinct, hence pairwise coprime (Nat.coprime_primes). Applying the Chinese Remainder Theorem (Nat.chineseRemainderOfFinset) yields an integer k satisfying the required congruences for all prime factors simultaneously.
uses
Nat.prime_of_mem_primeFactors,dif_pos,ZMod.natCast_zmod_val,Nat.coprime_primes,Nat.chineseRemainderOfFinsetlet rem : ℕ → ℕ := fun p => if hp : p ∈ n.primeFactors then (- a p hp).val else 0 have hrem (p : ℕ) (hp : p ∈ n.primeFactors) : (rem p : ZMod p) = - a p hp := by have hp_prime := Nat.prime_of_mem_primeFactors hp have : NeZero p := ⟨hp_prime.ne_zero⟩ dsimp [rem] rw [dif_pos hp] exact ZMod.natCast_zmod_val (- a p hp) have hs : ∀ p ∈ n.primeFactors, p ≠ 0 := by intro p hp exact (Nat.prime_of_mem_primeFactors hp).ne_zero have hpp : (↑n.primeFactors : Set ℕ).Pairwise (Function.onFun Nat.Coprime id) := by intro p hp q hq hpq exact (Nat.coprime_primes (Nat.prime_of_mem_primeFactors hp) (Nat.prime_of_mem_primeFactors hq)).mpr hpq obtain ⟨k, hk⟩ := Nat.chineseRemainderOfFinset rem id n.primeFactors hs hpp
The element c = (k : ℤ/nℤ) reduces to -a(p) in ℤ/pℤ for every prime factor p of n.
Under the reduction homomorphism from ℤ/nℤ to ℤ/pℤ, the image of c is k modulo p (map_natCast). By the congruence satisfied by k, this reduction equals the target residue -a(p) in ℤ/pℤ (ZMod.natCast_eq_natCast_iff').
uses
ZMod.natCast_eq_natCast_iff',map_natCastlet c : ZMod n := (k : ZMod n) have hc_cast (p : ℕ) (hp : p ∈ n.primeFactors) (hd : p ∣ n) : ZMod.castHom hd (ZMod p) c = - a p hp := by have hk_mod : (k : ZMod p) = (rem p : ZMod p) := (ZMod.natCast_eq_natCast_iff' k (rem p) p).mpr (hk p hp) calc ZMod.castHom hd (ZMod p) c = (k : ZMod p) := map_natCast (ZMod.castHom hd (ZMod p)) k _ = (rem p : ZMod p) := hk_mod _ = - a p hp := hrem p hp
For every good slope m, the shifted slope m + c is a unit in ℤ/nℤ.
By the prime-reduction criterion established earlier, m + c is a unit if its reduction modulo every prime divisor p of n is nonzero. The reduction of m + c modulo p is (m mod p) + (c mod p) = (m mod p) - a(p). If this were zero, m would reduce to a(p) modulo p (sub_eq_zero.mp), contradicting the fact that a(p) was chosen to be omitted by all good slopes.
uses
Nat.mem_primeFactors.mpr,NeZero.ne,map_add,sub_eq_add_neg,sub_eq_zero.mphave hshift (m : ZMod n) (hm : m ∈ good_slopes n f) : IsUnit (m + c) := by rw [isUnit_iff_forall_prime] intro p hp hd have hp_mem : p ∈ n.primeFactors := Nat.mem_primeFactors.mpr ⟨hp, hd, NeZero.ne n⟩ rw [map_add, hc_cast p hp_mem hd] intro hzero apply ha p hp_mem m hm have : ZMod.castHom hd (ZMod p) m - a p hp_mem = 0 := by simpa only [sub_eq_add_neg] using hzero exact sub_eq_zero.mp this
c is a unit, and thus c witnesses the theorem.
The zero slope 0 is always a good slope (zero_mem_good_slopes). Applying the previous step to m = 0 shows that 0 + c = c is a unit. Hence c is a unit in ℤ/nℤ whose addition to any good slope yields a unit.
uses
zero_mem_good_slopesrefine ⟨c, ?_, hshift⟩ have hz := zero_mem_good_slopes n f simpa using hshift 0 hz
ZMod.isUnit_iff_coprime- In ℤ/nℤ, the residue of an integer m is a unit if and only if m is coprime to n.
ZMod.natCast_zmod_val- Casting the canonical integer representative of an element of ℤ/nℤ back to ℤ/nℤ yields the element itself.
map_natCast- A ring homomorphism preserves the canonical cast from ℕ: f(↑n) = ↑n.
ZMod.natCast_eq_zero_iff- In ℤ/bℤ, the natural cast ↑a equals 0 if and only if b divides a.
Nat.Prime.not_coprime_iff_dvd.mpr- If two natural numbers share a prime factor, they are not coprime.
Nat.Prime.not_coprime_iff_dvd.mp- If two natural numbers are not coprime, there exists a prime dividing both.
Nat.prime_of_mem_primeFactors- Every element of the prime factor set of n is a prime number.
Nat.dvd_of_mem_primeFactors- Every prime factor of n divides n.
good_slopes_missing_prime_squarefree- For a squarefree modulus n, any prime p ∣ n, and any permutation f, the reduction of the good slopes of f modulo p omits at least one residue in ℤ/pℤ.
dif_pos- A dependent if-then-else expression evaluates to its positive branch when the condition holds.
Nat.coprime_primes- Two prime numbers are coprime if and only if they are distinct.
Nat.chineseRemainderOfFinset- The Chinese Remainder Theorem: given a finite set of pairwise coprime positive moduli and target remainders, there exists an integer simultaneously congruent to each remainder modulo each modulus.
ZMod.natCast_eq_natCast_iff'- Two natural numbers cast to the same element in ℤ/cℤ if and only if they are congruent modulo c.
Nat.mem_primeFactors.mpr- A prime p dividing a nonzero natural number n belongs to the prime factors of n.
NeZero.ne- A term with a NeZero typeclass instance is not equal to zero.
map_add- An additive homomorphism preserves addition: f(x + y) = f(x) + f(y).
sub_eq_add_neg- Subtraction equals addition of the negation: a - b = a + (-b).
sub_eq_zero.mp- If a - b = 0, then a = b.
zero_mem_good_slopes- The zero slope is always a good slope for any permutation.
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.
open scoped Functiontheorem good_slopes_unit_cover_squarefree (n : ℕ) [NeZero n] (hn : Squarefree n) (f : Equiv.Perm (ZMod n)) : ∃ c : ZMod n, IsUnit c ∧ ∀ m ∈ good_slopes n f, IsUnit (m+c) := by have isUnit_iff_forall_prime (x : ZMod n) : IsUnit x ↔ ∀ (p : ℕ) (hp : Nat.Prime p) (hd : p ∣ n), ZMod.castHom hd (ZMod p) x ≠ 0 := by have hunit : IsUnit x ↔ Nat.Coprime x.val n := by simpa only [ZMod.natCast_zmod_val] using (ZMod.isUnit_iff_coprime x.val n) rw [hunit] constructor · intro hcop p hp hd hz have hcast : ZMod.castHom hd (ZMod p) x = (x.val : ZMod p) := by conv_lhs => rw [← ZMod.natCast_zmod_val x] exact map_natCast _ _ rw [hcast] at hz have hdvd : p ∣ x.val := (ZMod.natCast_eq_zero_iff x.val p).mp hz have : ∃ q, Nat.Prime q ∧ q ∣ x.val ∧ q ∣ n := ⟨p, hp, hdvd, hd⟩ exact Nat.Prime.not_coprime_iff_dvd.mpr this hcop · intro h by_contra hnc obtain ⟨p, hp, hpx, hpn⟩ := Nat.Prime.not_coprime_iff_dvd.mp hnc have hz : (x.val : ZMod p) = 0 := (ZMod.natCast_eq_zero_iff x.val p).mpr hpx have hcast : ZMod.castHom hpn (ZMod p) x = (x.val : ZMod p) := by conv_lhs => rw [← ZMod.natCast_zmod_val x] exact map_natCast _ _ exact (h p hp hpn) (hcast.trans hz) have h (p : ℕ) (hp : p ∈ n.primeFactors) : ∃ a : ZMod p, ∀ m ∈ good_slopes n f, ZMod.castHom (Nat.dvd_of_mem_primeFactors hp) (ZMod p) m ≠ a := by have hp_prime := Nat.prime_of_mem_primeFactors hp have : NeZero p := ⟨hp_prime.ne_zero⟩ exact good_slopes_missing_prime_squarefree n p hn hp_prime (Nat.dvd_of_mem_primeFactors hp) f choose a ha using h let rem : ℕ → ℕ := fun p => if hp : p ∈ n.primeFactors then (- a p hp).val else 0 have hrem (p : ℕ) (hp : p ∈ n.primeFactors) : (rem p : ZMod p) = - a p hp := by have hp_prime := Nat.prime_of_mem_primeFactors hp have : NeZero p := ⟨hp_prime.ne_zero⟩ dsimp [rem] rw [dif_pos hp] exact ZMod.natCast_zmod_val (- a p hp) have hs : ∀ p ∈ n.primeFactors, p ≠ 0 := by intro p hp exact (Nat.prime_of_mem_primeFactors hp).ne_zero have hpp : (↑n.primeFactors : Set ℕ).Pairwise (Function.onFun Nat.Coprime id) := by intro p hp q hq hpq exact (Nat.coprime_primes (Nat.prime_of_mem_primeFactors hp) (Nat.prime_of_mem_primeFactors hq)).mpr hpq obtain ⟨k, hk⟩ := Nat.chineseRemainderOfFinset rem id n.primeFactors hs hpp let c : ZMod n := (k : ZMod n) have hc_cast (p : ℕ) (hp : p ∈ n.primeFactors) (hd : p ∣ n) : ZMod.castHom hd (ZMod p) c = - a p hp := by have hk_mod : (k : ZMod p) = (rem p : ZMod p) := (ZMod.natCast_eq_natCast_iff' k (rem p) p).mpr (hk p hp) calc ZMod.castHom hd (ZMod p) c = (k : ZMod p) := map_natCast (ZMod.castHom hd (ZMod p)) k _ = (rem p : ZMod p) := hk_mod _ = - a p hp := hrem p hp have hshift (m : ZMod n) (hm : m ∈ good_slopes n f) : IsUnit (m + c) := by rw [isUnit_iff_forall_prime] intro p hp hd have hp_mem : p ∈ n.primeFactors := Nat.mem_primeFactors.mpr ⟨hp, hd, NeZero.ne n⟩ rw [map_add, hc_cast p hp_mem hd] intro hzero apply ha p hp_mem m hm have : ZMod.castHom hd (ZMod p) m - a p hp_mem = 0 := by simpa only [sub_eq_add_neg] using hzero exact sub_eq_zero.mp this refine ⟨c, ?_, hshift⟩ have hz := zero_mem_good_slopes n f simpa using hshift 0 hz