AFTD Auto-Formalizing Theoretical Domains

good_slopes_unit_cover_squarefree

theoremverified

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.

  1. 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.

    lines 4–25

    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.mp

      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)
  2. 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).

    lines 26–31

    uses Nat.prime_of_mem_primeFactors, Nat.dvd_of_mem_primeFactors, good_slopes_missing_prime_squarefree

      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
  3. 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.

    lines 32–45

    uses Nat.prime_of_mem_primeFactors, dif_pos, ZMod.natCast_zmod_val, Nat.coprime_primes, Nat.chineseRemainderOfFinset

      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
  4. 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').

    lines 46–54

    uses ZMod.natCast_eq_natCast_iff', map_natCast

      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
  5. 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.

    lines 55–64

    uses Nat.mem_primeFactors.mpr, NeZero.ne, map_add, sub_eq_add_neg, sub_eq_zero.mp

      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
  6. 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.

    lines 65–67

    uses zero_mem_good_slopes

      refine ⟨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

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
See it in the graphDiscuss this resultChallenge it