AFTD Auto-Formalizing Theoretical Domains

good_slopes_unit_cover_mod105

theoremverified

For every permutation modulo 105, a unit c exists such that adding c to each good slope yields a unit modulo 105.

Statement

theorem good_slopes_unit_cover_mod105 (f : Equiv.Perm (ZMod 105)) : ∃ c : ZMod 105, IsUnit c ∧ ∀ m ∈ good_slopes 105 f, IsUnit (m+c)
Source
The modulus 105 instance of arXiv:2611.01465, Theorem 3.1(i), used for OP-1027.
Verified
15 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…
  • good_slopes_missing_prime105For a permutation modulo 105 and each prime divisor p, some residue modulo p is not attained by any good slope.
Used by 1
  • good_slopes_gap_mod_105Every non-extremal permutation f of ℤ/105ℤ satisfies |D_{105}(f)| ≤ 40: (good_slopes 105 f).card ≤ 40.

The proof, explained

We find residues a, b, d modulo 3, 5, 7 that are never attained by the good slopes of f, using good_slopes_missing_prime105. By the Chinese Remainder Theorem, we define c modulo 105 such that c ≡ -a mod 3, c ≡ -b mod 5, and c ≡ -d mod 7. Then for every good slope m, m + c is non-zero modulo 3, 5, and 7, hence m + c is coprime to 105 and therefore a unit. Since 0 is always a good slope, setting m = 0 also shows that c itself is a unit.

  1. The prime factors 3, 5, and 7 divide 105, giving reduction homomorphisms to ZMod 3, ZMod 5, and ZMod 7. automation

    Lean verifies by direct computation that 3, 5, and 7 divide 105, allowing the construction of canonical reduction ring homomorphisms c3, c5, and c7.

    lines 3–5

    private def c3 : ZMod 105 →+* ZMod 3 := ZMod.castHom (by decide : 3 ∣ 105) (ZMod 3)
    private def c5 : ZMod 105 →+* ZMod 5 := ZMod.castHom (by decide : 5 ∣ 105) (ZMod 5)
    private def c7 : ZMod 105 →+* ZMod 7 := ZMod.castHom (by decide : 7 ∣ 105) (ZMod 7)
  2. The explicit CRT formula correctly projects to each residue component modulo 3, 5, and 7. automation

    By exhaustive checking over all finite inputs, the linear combination crt a b c = 70 a + 21 b + 15 c reduces to a mod 3, b mod 5, and c mod 7.

    lines 6–10

    private def crt (a : ZMod 3) (b : ZMod 5) (c : ZMod 7) : ZMod 105 :=
      70 * a.val + 21 * b.val + 15 * c.val
    private theorem crt3 : ∀ a : ZMod 3, ∀ b : ZMod 5, ∀ c : ZMod 7, c3 (crt a b c) = a := by decide +revert
    private theorem crt5 : ∀ a : ZMod 3, ∀ b : ZMod 5, ∀ c : ZMod 7, c5 (crt a b c) = b := by decide +revert
    private theorem crt7 : ∀ a : ZMod 3, ∀ b : ZMod 5, ∀ c : ZMod 7, c7 (crt a b c) = c := by decide +revert
  3. An element in ZMod 105 is coprime to 105 if and only if its reductions modulo 3, 5, and 7 are all non-zero. automation

    Lean verifies the equivalence by finite computation over all 105 elements of ZMod 105.

    line 11

    private theorem unit105 : ∀ x : ZMod 105, Nat.Coprime x.val 105 ↔ c3 x ≠ 0 ∧ c5 x ≠ 0 ∧ c7 x ≠ 0 := by decide +revert
  4. For any permutation f, there exists a unit c such that m + c is a unit for all good slopes m.

    We obtain missing residues a, b, d mod 3, 5, 7 from good_slopes_missing_prime105, set c = crt (-a) (-b) (-d), and show m + c is never 0 mod 3, 5, 7 for any good slope m. Since 0 is a good slope, c is also a unit.

    lines 13–44

    theorem good_slopes_unit_cover_mod105 (f : Equiv.Perm (ZMod 105)) : ∃ c : ZMod 105, IsUnit c ∧ ∀ m ∈ good_slopes 105 f, IsUnit (m+c) := by
      obtain ⟨a, ha⟩ := good_slopes_missing_prime105 3 (Or.inl rfl) (by decide) f
      obtain ⟨b, hb⟩ := good_slopes_missing_prime105 5 (Or.inr (Or.inl rfl)) (by decide) f
      obtain ⟨d, hd⟩ := good_slopes_missing_prime105 7 (Or.inr (Or.inr rfl)) (by decide) f
      let c := crt (-a) (-b) (-d)
      have hc3 : c3 c = -a := crt3 _ _ _
      have hc5 : c5 c = -b := crt5 _ _ _
      have hc7 : c7 c = -d := crt7 _ _ _
      have hzero : (0 : ZMod 105) ∈ good_slopes 105 f := by
        unfold good_slopes
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, zero_mul, add_zero]
        exact f.bijective
      have hunit (z : ZMod 105) : IsUnit z ↔ Nat.Coprime z.val 105 := by
        simpa only [ZMod.natCast_zmod_val] using (ZMod.isUnit_iff_coprime z.val 105)
      have hshift (m : ZMod 105) (hm : m ∈ good_slopes 105 f) : IsUnit (m+c) := by
        apply (hunit _).2
        apply (unit105 _).2
        have h3 : c3 (m+c) ≠ 0 := by
          intro h; apply ha m hm
          have : c3 m - a = 0 := by simpa only [map_add, hc3, sub_eq_add_neg] using h
          exact sub_eq_zero.mp this
        have h5 : c5 (m+c) ≠ 0 := by
          intro h; apply hb m hm
          have : c5 m - b = 0 := by simpa only [map_add, hc5, sub_eq_add_neg] using h
          exact sub_eq_zero.mp this
        have h7 : c7 (m+c) ≠ 0 := by
          intro h; apply hd m hm
          have : c7 m - d = 0 := by simpa only [map_add, hc7, sub_eq_add_neg] using h
          exact sub_eq_zero.mp this
        exact ⟨h3, h5, h7⟩
      refine ⟨c, ?_, hshift⟩
      simpa using hshift 0 hzero

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

set_option maxHeartbeats 4000000set_option maxRecDepth 10000private def c3 : ZMod 105 →+* ZMod 3 := ZMod.castHom (by decide : 3 ∣ 105) (ZMod 3)private def c5 : ZMod 105 →+* ZMod 5 := ZMod.castHom (by decide : 5 ∣ 105) (ZMod 5)private def c7 : ZMod 105 →+* ZMod 7 := ZMod.castHom (by decide : 7 ∣ 105) (ZMod 7)private def crt (a : ZMod 3) (b : ZMod 5) (c : ZMod 7) : ZMod 105 :=  70 * a.val + 21 * b.val + 15 * c.valprivate theorem crt3 : ∀ a : ZMod 3, ∀ b : ZMod 5, ∀ c : ZMod 7, c3 (crt a b c) = a := by decide +revertprivate theorem crt5 : ∀ a : ZMod 3, ∀ b : ZMod 5, ∀ c : ZMod 7, c5 (crt a b c) = b := by decide +revertprivate theorem crt7 : ∀ a : ZMod 3, ∀ b : ZMod 5, ∀ c : ZMod 7, c7 (crt a b c) = c := by decide +revertprivate theorem unit105 : ∀ x : ZMod 105, Nat.Coprime x.val 105 ↔ c3 x ≠ 0 ∧ c5 x ≠ 0 ∧ c7 x ≠ 0 := by decide +reverttheorem good_slopes_unit_cover_mod105 (f : Equiv.Perm (ZMod 105)) : ∃ c : ZMod 105, IsUnit c ∧ ∀ m ∈ good_slopes 105 f, IsUnit (m+c) := by  obtain ⟨a, ha⟩ := good_slopes_missing_prime105 3 (Or.inl rfl) (by decide) f  obtain ⟨b, hb⟩ := good_slopes_missing_prime105 5 (Or.inr (Or.inl rfl)) (by decide) f  obtain ⟨d, hd⟩ := good_slopes_missing_prime105 7 (Or.inr (Or.inr rfl)) (by decide) f  let c := crt (-a) (-b) (-d)  have hc3 : c3 c = -a := crt3 _ _ _  have hc5 : c5 c = -b := crt5 _ _ _  have hc7 : c7 c = -d := crt7 _ _ _  have hzero : (0 : ZMod 105) ∈ good_slopes 105 f := by    unfold good_slopes    simp only [Finset.mem_filter, Finset.mem_univ, true_and, zero_mul, add_zero]    exact f.bijective  have hunit (z : ZMod 105) : IsUnit z ↔ Nat.Coprime z.val 105 := by    simpa only [ZMod.natCast_zmod_val] using (ZMod.isUnit_iff_coprime z.val 105)  have hshift (m : ZMod 105) (hm : m ∈ good_slopes 105 f) : IsUnit (m+c) := by    apply (hunit _).2    apply (unit105 _).2    have h3 : c3 (m+c) ≠ 0 := by      intro h; apply ha m hm      have : c3 m - a = 0 := by simpa only [map_add, hc3, sub_eq_add_neg] using h      exact sub_eq_zero.mp this    have h5 : c5 (m+c) ≠ 0 := by      intro h; apply hb m hm      have : c5 m - b = 0 := by simpa only [map_add, hc5, sub_eq_add_neg] using h      exact sub_eq_zero.mp this    have h7 : c7 (m+c) ≠ 0 := by      intro h; apply hd m hm      have : c7 m - d = 0 := by simpa only [map_add, hc7, sub_eq_add_neg] using h      exact sub_eq_zero.mp this    exact ⟨h3, h5, h7⟩  refine ⟨c, ?_, hshift⟩  simpa using hshift 0 hzero
See it in the graphDiscuss this resultChallenge it