AFTD Auto-Formalizing Theoretical Domains

good_slopes_fiber55_eleven_collision_gap

theoremverified

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

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.

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

    lines 1–5

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

    lines 6–19

    uses ZMod.castHom_apply, ZMod.cast_eq_val, ZMod.natCast_eq_zero_iff, ZMod.natCast_zmod_val

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

    lines 20–27

    uses good_slopes_fiber55_nonunit_collision_gap_card_units, Finset.mem_filter, Finset.mem_univ, true_and

      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⟩
  4. 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.

    lines 28–34

    uses ZMod.isUnit_iff_coprime, ZMod.natCast_zmod_val, good_slopes_fiber55_eleven_collision_gap_ten

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

    lines 35–44

    uses Finset.mem_filter, Finset.mem_univ, ZMod.isUnit_iff_coprime, ZMod.natCast_zmod_val

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

    lines 45–65

    uses Finset.mem_filter, Finset.mem_image, ZMod.natCast_self, zero_mul

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

    lines 66–76

    uses Finset.disjoint_left, Finset.card_union_eq_card_add_card, Finset.card_le_card, Finset.union_subset

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

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

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