good_slopes_fiber55_eleven_collision_gap
Let S be any finite set of points over Z/55Z. If a unit direction has a collision between distinct points whose first-coordinate difference is divisible by 11, then S has at most 30 good unit directions.
Statement
theorem good_slopes_fiber55_eleven_collision_gap (S : Finset (ZMod 55 × ZMod 55)) (a : ZMod 55) (ha : IsUnit a) (p q : ZMod 55 × ZMod 55) (hp : p ∈ S) (hq : q ∈ S) (hpq : p ≠ q) (hcollision : p.2 + a*p.1 = q.2 + a*q.1) (hdiv : ZMod.castHom (by decide : 11 ∣ 55) (ZMod 11) (q.1-p.1) = 0) : (good_slopes_point_directions 55 S).card ≤ 30
- Source
- CRT collision reduction for the local fiber approach to OP-1027; the normalized case was observed in experiment 27539.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- good_slopes_point_directionsThe unit directions a for which the linear form y + a x is injective on a finite set of points over the residues modulo n.
- good_slopes_fiber55_nonunit_collision_gapLet S be any finite set of points over Z/55Z. If a unit direction has a collision between distinct points whose first-coordinate…
The proof, explained
There are φ(55) = 40 unit directions in ℤ/55ℤ. Given a collision between distinct points p and q in direction a with first-coordinate difference d divisible by 11, any direction of the form a + 5k (for 0 ≤ k < 11) also causes p and q to collide because (5k)d is divisible by 55. An auxiliary computational check shows that at least 10 of these 11 colliding directions are units coprime to 55, yielding a set of at least 10 bad unit directions. Since these bad units are disjoint from the good slopes within the 40 total units, S can have at most 40 - 10 = 30 good unit directions.
For any unit a ∈ ℤ/55ℤ, the arithmetic progression {a + 5k (mod 55) | 0 ≤ k < 11} contains at least 10 units. automation
We prove the helper lemma good_slopes_fiber55_eleven_collision_gap_ten for an arbitrary direction a coprime to 55. After generalizing over a, Lean evaluates the finite statement by exhaustive computation (`decide`).
theorem good_slopes_fiber55_eleven_collision_gap_ten (a : ZMod 55) (ha : a.val.Coprime 55) : 10 ≤ (((Finset.range 11).image (fun k : ℕ => a + (5:ZMod 55)*(k:ZMod 55))).filter (fun b => b.val.Coprime 55)).card := by revert a decide
The first-coordinate difference d = q.1 - p.1 is a multiple of 11 in ℤ/55ℤ.
Let d = q.1 - p.1. The hypothesis hdiv states that the canonical projection of d to ℤ/11ℤ is 0 (where 11 ∣ 55 is checked by `decide`). Expanding the homomorphism using ZMod.castHom_apply and ZMod.cast_eq_val shows that the integer representative d.val vanishes modulo 11, which by ZMod.natCast_eq_zero_iff means 11 ∣ d.val. Writing d.val = 11k and casting back to ℤ/55ℤ via ZMod.natCast_zmod_val provides an element m such that d = 11 * m.
uses
ZMod.castHom_apply,ZMod.cast_eq_val,ZMod.natCast_eq_zero_iff,ZMod.natCast_zmod_valtheorem good_slopes_fiber55_eleven_collision_gap (S : Finset (ZMod 55 × ZMod 55)) (a : ZMod 55) (ha : IsUnit a) (p q : ZMod 55 × ZMod 55) (hp : p ∈ S) (hq : q ∈ S) (hpq : p ≠ q) (hcollision : p.2 + a*p.1 = q.2 + a*q.1) (hdiv : ZMod.castHom (by decide : 11 ∣ 55) (ZMod 11) (q.1-p.1) = 0) : (good_slopes_point_directions 55 S).card ≤ 30 := by classical set d : ZMod 55 := q.1 - p.1 with hd have h11 : 11 ∣ d.val := by rw [hd] rw [ZMod.castHom_apply, ZMod.cast_eq_val] at hdiv exact (ZMod.natCast_eq_zero_iff d.val 11).mp hdiv obtain ⟨m, hm⟩ : ∃ m : ZMod 55, d = 11 * m := by obtain ⟨k, hk⟩ := h11 use k conv_lhs => rw [← ZMod.natCast_zmod_val d] rw [hk] push_cast ring
The set U of units in ℤ/55ℤ has size 40, and every good slope belongs to U.
We define U as the finset of units in ℤ/55ℤ; its cardinality is 40 by good_slopes_fiber55_nonunit_collision_gap_card_units. By definition, any good slope for S must be a unit, so the set of good slopes is a subset of U.
uses
good_slopes_fiber55_nonunit_collision_gap_card_units,Finset.mem_filter,Finset.mem_univ,true_andset U : Finset (ZMod 55) := Finset.univ.filter (fun b => IsUnit b) with hU have hUcard : U.card = 40 := by rw [hU]; exact good_slopes_fiber55_nonunit_collision_gap_card_units have hgoodU : good_slopes_point_directions 55 S ⊆ U := by intro b hb rw [good_slopes_point_directions] at hb simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb rw [hU] exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hb.1⟩
The direction a is coprime to 55, and the candidate set T = {a + 5k | 0 ≤ k < 11 and gcd(a + 5k, 55) = 1} contains at least 10 elements.
Since a is a unit, ZMod.isUnit_iff_coprime and ZMod.natCast_zmod_val establish that a.val is coprime to 55. Defining T as the set of values a + 5k (for 0 ≤ k < 11) that are coprime to 55, the helper lemma good_slopes_fiber55_eleven_collision_gap_ten guarantees that |T| ≥ 10.
uses
ZMod.isUnit_iff_coprime,ZMod.natCast_zmod_val,good_slopes_fiber55_eleven_collision_gap_tenhave ha_coprime : a.val.Coprime 55 := by have h := (ZMod.isUnit_iff_coprime a.val 55).mp have heq : ((a.val : ℕ) : ZMod 55) = a := ZMod.natCast_zmod_val a rw [heq] at h exact h ha set T : Finset (ZMod 55) := (((Finset.range 11).image (fun k : ℕ => a + (5:ZMod 55)*(k:ZMod 55))).filter (fun b => b.val.Coprime 55)) with hT have hTc : 10 ≤ T.card := by rw [hT]; exact good_slopes_fiber55_eleven_collision_gap_ten a ha_coprime
The set T is a subset of the units U.
Each element b ∈ T satisfies gcd(b.val, 55) = 1 by definition of T. Using ZMod.isUnit_iff_coprime and ZMod.natCast_zmod_val, this coprimality implies b is a unit in ℤ/55ℤ, so b ∈ U.
uses
Finset.mem_filter,Finset.mem_univ,ZMod.isUnit_iff_coprime,ZMod.natCast_zmod_valhave hTsub : T ⊆ U := by intro b hb rw [hT] at hb simp only [Finset.mem_filter] at hb rw [hU] refine Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩ have h := (ZMod.isUnit_iff_coprime b.val 55).mpr hb.2 have heq : ((b.val : ℕ) : ZMod 55) = b := ZMod.natCast_zmod_val b rw [heq] at h exact h
No direction in T is a good slope for S.
Let b ∈ T, so b = a + 5k for some 0 ≤ k < 11. Then (b - a) * d = (5k) * (11m) = 55 * (km) = 0 in ℤ/55ℤ, using ZMod.natCast_self and zero_mul. Subtracting this from the assumed collision p.2 + a * p.1 = q.2 + a * q.1 yields p.2 + b * p.1 = q.2 + b * q.1. Were b a good slope, the projection in direction b would be injective on S, forcing p = q, which contradicts p ≠ q.
uses
Finset.mem_filter,Finset.mem_image,ZMod.natCast_self,zero_mulhave hTbad : ∀ b ∈ T, b ∉ good_slopes_point_directions 55 S := by intro b hb rw [hT] at hb simp only [Finset.mem_filter] at hb obtain ⟨hbimg, -⟩ := hb rw [Finset.mem_image] at hbimg obtain ⟨k, hk, hkb⟩ := hbimg intro hbgood rw [good_slopes_point_directions] at hbgood simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hbgood obtain ⟨-, hbinj⟩ := hbgood have hzero : (b - a) * d = 0 := by rw [← hkb] have hsub : (a + (5:ZMod 55)*(k:ZMod 55)) - a = (5:ZMod 55)*(k:ZMod 55) := by ring rw [hsub, hm] have heq : (5:ZMod 55)*(k:ZMod 55)*(11*(m:ZMod 55)) = ((55:ℕ):ZMod 55) * ((k:ZMod 55)*(m:ZMod 55)) := by ring rw [heq, ZMod.natCast_self 55, zero_mul] have hval : p.2 + b * p.1 = q.2 + b * q.1 := by rw [hd] at hzero linear_combination hcollision - hzero exact hpq (hbinj (Finset.mem_coe.mpr hp) (Finset.mem_coe.mpr hq) hval)
The set of good directions for S has cardinality at most 30. automation
Because no element of T is a good slope, Finset.disjoint_left shows the good slopes and T are disjoint. Thus the cardinality of their union is the sum of their cardinalities (Finset.card_union_eq_card_add_card). Since both are subsets of U, their union is also a subset of U (Finset.union_subset), giving |good_slopes| + |T| ≤ |U| = 40 (Finset.card_le_card). Since |T| ≥ 10, linear integer arithmetic (`omega`) deduces |good_slopes| ≤ 30.
uses
Finset.disjoint_left,Finset.card_union_eq_card_add_card,Finset.card_le_card,Finset.union_subsethave hdisj : Disjoint (good_slopes_point_directions 55 S) T := by rw [Finset.disjoint_left] intro x hx hxt exact hTbad x hxt hx have hunion_card : (good_slopes_point_directions 55 S ∪ T).card = (good_slopes_point_directions 55 S).card + T.card := (Finset.card_union_eq_card_add_card).mpr hdisj have hle : (good_slopes_point_directions 55 S ∪ T).card ≤ 40 := by rw [← hUcard] exact Finset.card_le_card (Finset.union_subset hgoodU hTsub) omega
ZMod.castHom_apply- The canonical ring homomorphism between modular rings evaluates by casting the element.
ZMod.cast_eq_val- Casting an element of ℤ/nℤ into another ring equals casting its canonical representative in {0, …, n - 1}.
ZMod.natCast_eq_zero_iff- A natural number casts to 0 in ℤ/bℤ if and only if b divides it.
ZMod.natCast_zmod_val- Casting the integer representative a.val back into ℤ/nℤ recovers the element a.
good_slopes_fiber55_nonunit_collision_gap_card_units- The total number of units in ℤ/55ℤ is φ(55) = 40.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
true_and- Conjunction with True simplifies to the proposition itself: (True ∧ p) = p.
ZMod.isUnit_iff_coprime- An element of ℤ/nℤ represented by m ∈ ℕ is a unit if and only if m is coprime to n.
good_slopes_fiber55_eleven_collision_gap_ten- For any element a ∈ ℤ/55ℤ coprime to 55, at least 10 of the values a + 5k (for 0 ≤ k < 11) are coprime to 55.
Finset.mem_image- An element belongs to the image of a finset under a function if and only if it is the image of some element in the finset.
ZMod.natCast_self- In ℤ/nℤ, the modulus n cast as an element equals 0.
zero_mul- Zero multiplied by any element is zero.
Finset.disjoint_left- Two finsets are disjoint if and only if no element of the first belongs to the second.
Finset.card_union_eq_card_add_card- The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
Finset.card_le_card- If one finset is a subset of another, its cardinality is at most the other's.
Finset.union_subset- If two finsets are both subsets of a third, their union is also a subset of the third.
- The auxiliary lemma `good_slopes_fiber55_eleven_collision_gap_ten` is established by the `decide` tactic, which exhaustively checks the claim for all 40 units modulo 55 by finite computation.
- The divisibility condition on the first-coordinate difference is formally formulated as the kernel condition `ZMod.castHom (by decide : 11 ∣ 55) (ZMod 11) (q.1 - p.1) = 0`.
- The final arithmetic deduction bounding the number of good slopes by 30 is automated by `omega`.
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.
theorem good_slopes_fiber55_eleven_collision_gap_ten (a : ZMod 55) (ha : a.val.Coprime 55) : 10 ≤ (((Finset.range 11).image (fun k : ℕ => a + (5:ZMod 55)*(k:ZMod 55))).filter (fun b => b.val.Coprime 55)).card := by revert a decidetheorem good_slopes_fiber55_eleven_collision_gap (S : Finset (ZMod 55 × ZMod 55)) (a : ZMod 55) (ha : IsUnit a) (p q : ZMod 55 × ZMod 55) (hp : p ∈ S) (hq : q ∈ S) (hpq : p ≠ q) (hcollision : p.2 + a*p.1 = q.2 + a*q.1) (hdiv : ZMod.castHom (by decide : 11 ∣ 55) (ZMod 11) (q.1-p.1) = 0) : (good_slopes_point_directions 55 S).card ≤ 30 := by classical set d : ZMod 55 := q.1 - p.1 with hd have h11 : 11 ∣ d.val := by rw [hd] rw [ZMod.castHom_apply, ZMod.cast_eq_val] at hdiv exact (ZMod.natCast_eq_zero_iff d.val 11).mp hdiv obtain ⟨m, hm⟩ : ∃ m : ZMod 55, d = 11 * m := by obtain ⟨k, hk⟩ := h11 use k conv_lhs => rw [← ZMod.natCast_zmod_val d] rw [hk] push_cast ring set U : Finset (ZMod 55) := Finset.univ.filter (fun b => IsUnit b) with hU have hUcard : U.card = 40 := by rw [hU]; exact good_slopes_fiber55_nonunit_collision_gap_card_units have hgoodU : good_slopes_point_directions 55 S ⊆ U := by intro b hb rw [good_slopes_point_directions] at hb simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb rw [hU] exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hb.1⟩ have ha_coprime : a.val.Coprime 55 := by have h := (ZMod.isUnit_iff_coprime a.val 55).mp have heq : ((a.val : ℕ) : ZMod 55) = a := ZMod.natCast_zmod_val a rw [heq] at h exact h ha set T : Finset (ZMod 55) := (((Finset.range 11).image (fun k : ℕ => a + (5:ZMod 55)*(k:ZMod 55))).filter (fun b => b.val.Coprime 55)) with hT have hTc : 10 ≤ T.card := by rw [hT]; exact good_slopes_fiber55_eleven_collision_gap_ten a ha_coprime have hTsub : T ⊆ U := by intro b hb rw [hT] at hb simp only [Finset.mem_filter] at hb rw [hU] refine Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩ have h := (ZMod.isUnit_iff_coprime b.val 55).mpr hb.2 have heq : ((b.val : ℕ) : ZMod 55) = b := ZMod.natCast_zmod_val b rw [heq] at h exact h have hTbad : ∀ b ∈ T, b ∉ good_slopes_point_directions 55 S := by intro b hb rw [hT] at hb simp only [Finset.mem_filter] at hb obtain ⟨hbimg, -⟩ := hb rw [Finset.mem_image] at hbimg obtain ⟨k, hk, hkb⟩ := hbimg intro hbgood rw [good_slopes_point_directions] at hbgood simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hbgood obtain ⟨-, hbinj⟩ := hbgood have hzero : (b - a) * d = 0 := by rw [← hkb] have hsub : (a + (5:ZMod 55)*(k:ZMod 55)) - a = (5:ZMod 55)*(k:ZMod 55) := by ring rw [hsub, hm] have heq : (5:ZMod 55)*(k:ZMod 55)*(11*(m:ZMod 55)) = ((55:ℕ):ZMod 55) * ((k:ZMod 55)*(m:ZMod 55)) := by ring rw [heq, ZMod.natCast_self 55, zero_mul] have hval : p.2 + b * p.1 = q.2 + b * q.1 := by rw [hd] at hzero linear_combination hcollision - hzero exact hpq (hbinj (Finset.mem_coe.mpr hp) (Finset.mem_coe.mpr hq) hval) have hdisj : Disjoint (good_slopes_point_directions 55 S) T := by rw [Finset.disjoint_left] intro x hx hxt exact hTbad x hxt hx have hunion_card : (good_slopes_point_directions 55 S ∪ T).card = (good_slopes_point_directions 55 S).card + T.card := (Finset.card_union_eq_card_add_card).mpr hdisj have hle : (good_slopes_point_directions 55 S ∪ T).card ≤ 40 := by rw [← hUcard] exact Finset.card_le_card (Finset.union_subset hgoodU hTsub) omega