good_slopes_unit_cover_mod105
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.
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.
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)
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.
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
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.
private theorem unit105 : ∀ x : ZMod 105, Nat.Coprime x.val 105 ↔ c3 x ≠ 0 ∧ c5 x ≠ 0 ∧ c7 x ≠ 0 := by decide +revert
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.
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
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.
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