good_slopes_fiber35_bad_neighbors
For any 35 points modulo 35 and any bad unit direction, at least three of its eight unit directions sharing a residue modulo 5 or modulo 7 are also bad.
Statement
theorem good_slopes_fiber35_bad_neighbors (S : Finset (ZMod 35 × ZMod 35)) (hcard : S.card = 35) (a : ZMod 35) (ha : IsUnit a) (hbad : a ∉ good_slopes_point_directions 35 S) : ((good_slopes_point_directions 35 S).filter (fun b => b ≠ a ∧ (b.val % 5 = a.val % 5 ∨ b.val % 7 = a.val % 7))).card ≤ 5
- Source
- A normalization and counting consequence of good_slopes_fiber35_anchored_neighbors; tested in experiment 22001.
- Verified
- 11 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_fiber35_anchored_neighborsA point set over residues modulo 35 containing (0,0) and (1,34) cannot have six or more injective and surjective directions among 6, 8,…
- Used by 2
- good_slopes_fiber35_unit_gapFor any 35 points over the residues modulo 35, if at least one unit direction fails to be injective, then at most 20 of the 24 unit…
- good_slopes_fiber35_colored_gapLet S be a set of 35 points over the residues modulo 35, colored with three colors. Suppose that within each color both the first…
The proof, explained
The proof proceeds by contradiction: assuming that more than 5 neighbors of a sharing a residue modulo 5 or 7 are good directions, any subset of bad neighbors in Nb(a) can have size at most 2. Because a is bad, the projection along a produces colliding points p ≠ q with difference vector (d₁, d₂) satisfying d₂ = -(a d₁). If d₁ is a unit, an affine coordinate change maps S to an anchored set at (0,0) and (1,34), where a classification theorem shows that at least three bad directions must exist, contradicting the size bound. If d₁ is a non-zero non-unit, finite ring arithmetic directly yields at least 3 bad neighbors that collide on p and q, which likewise contradicts the size bound.
An element of ℤ/35ℤ is a unit if and only if it belongs to the explicit 24-element set U35. automation
We rewrite unit-hood using isUnit_iff_exists_inv (the existence of a multiplicative inverse) and exhaustively verify the equivalence for every element of ℤ/35ℤ via the decide tactic.
uses
isUnit_iff_exists_invnamespace Gs35Nb def U35 : Finset (ZMod 35) := {1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34} theorem isUnit_iff_U (x : ZMod 35) : IsUnit x ↔ x ∈ U35 := by rw [isUnit_iff_exists_inv]; revert x; decide
Preliminary finite ring properties of units and residue subsets in ℤ/35ℤ. automation
Using exhaustive computational evaluation (decide), we establish several facts: multiplying any non-unit d₁ ≠ 0 by elements of U35 collides with at least 4 units; the subset {6, 8, 11, 16, 22, 26, 29, 31} consists of units and does not contain 1; and -1 equals 34 in ℤ/35ℤ.
theorem nonunit_four : ∀ a0 ∈ U35, ∀ d1 : ZMod 35, d1 ∉ U35 → d1 ≠ 0 → 4 ≤ (U35.filter (fun b => -(a0 * d1) + b * d1 = 0)).card := by decide theorem eight_sub : ({6,8,11,16,22,26,29,31} : Finset (ZMod 35)) ⊆ U35 := by decide theorem one_not_eight : (1 : ZMod 35) ∉ ({6,8,11,16,22,26,29,31} : Finset (ZMod 35)) := by decide theorem neg_one_eq : (-1 : ZMod 35) = 34 := by decide
Properties of the neighbor set Nb(a0) sharing a residue modulo 5 or 7 with a unit a0. automation
For each unit a0 ∈ U35, the set Nb(a0) consists of all units b ≠ a0 sharing a residue modulo 5 or 7 with a0. Exhaustive finite checking (decide) confirms that |Nb(a0)| = 8, that multiplying a0 by each element of {6, 8, 11, 16, 22, 26, 29, 31} produces an element of Nb(a0), and that any non-zero non-unit d₁ has at least 3 colliding neighbors b ∈ Nb(a0) with -(a0 d₁) + b d₁ = 0.
def Nb (a0 : ZMod 35) : Finset (ZMod 35) := U35.filter (fun b => b ≠ a0 ∧ (b.val % 5 = a0.val % 5 ∨ b.val % 7 = a0.val % 7)) theorem Nb_card : ∀ a0 ∈ U35, (Nb a0).card = 8 := by decide theorem nonunit_three : ∀ a0 ∈ U35, ∀ d1 : ZMod 35, d1 ∉ U35 → d1 ≠ 0 → 3 ≤ ((Nb a0).filter (fun b => -(a0 * d1) + b * d1 = 0)).card := by decide theorem eight_Nb : ∀ a0 ∈ U35, ∀ x ∈ ({6,8,11,16,22,26,29,31} : Finset (ZMod 35)), a0 * x ∈ Nb a0 := by decide end Gs35Nb
Assume for contradiction that strictly more than 5 neighbors of a sharing a residue modulo 5 or 7 are good directions, and characterize good directions.
We argue by contradiction, supposing that the number of good directions b ≠ a sharing a residue modulo 5 or 7 with a exceeds 5. Setting a0 = a, the hypothesis that a is a unit implies a0 ∈ U35. Unfolding the definition of good directions, a slope is good if and only if it is a unit and the projection p ↦ p₂ + a p₁ is injective on S.
uses
Gs35Nb.isUnit_iff_Utheorem good_slopes_fiber35_bad_neighbors (S : Finset (ZMod 35 × ZMod 35)) (hcard : S.card = 35) (a : ZMod 35) (ha : IsUnit a) (hbad : a ∉ good_slopes_point_directions 35 S) : ((good_slopes_point_directions 35 S).filter (fun b => b ≠ a ∧ (b.val % 5 = a.val % 5 ∨ b.val % 7 = a.val % 7))).card ≤ 5 := by classical by_contra hlt push Not at hlt set a0 := a with ha0def have ha0u : IsUnit a0 := ha have ha0 := hbad have hmem : ∀ a, a ∈ good_slopes_point_directions 35 S ↔ IsUnit a ∧ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) S := by intro a; unfold good_slopes_point_directions; simp -- three bad neighbours are impossible have hU0 : a0 ∈ Gs35Nb.U35 := (Gs35Nb.isUnit_iff_U a0).1 ha0u
Any subset B of the neighbor set Nb(a0) consisting of bad directions has cardinality at most 2.
Let B ⊆ Nb(a0) be any set of bad directions (directions along which the projection is not injective). Every good neighbor of a0 must belong to Nb(a0) \ B, because no element of B is good. Since the total number of neighbors is |Nb(a0)| = 8, the number of good neighbors is bounded above by 8 - |B|. Under the contradictory assumption that there are strictly more than 5 good neighbors, we obtain 5 < 8 - |B|, which implies |B| ≤ 2.
uses
Finset.mem_filter,Finset.mem_sdiff,Gs35Nb.isUnit_iff_U,Finset.card_le_card,Finset.card_sdiff_of_subset,Gs35Nb.Nb_cardhave key : ∀ B : Finset (ZMod 35), B ⊆ Gs35Nb.Nb a0 → (∀ b ∈ B, ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + b * p.1) S) → B.card ≤ 2 := by intro B hBN hB have hsub : (good_slopes_point_directions 35 S).filter (fun b => b ≠ a0 ∧ (b.val % 5 = a0.val % 5 ∨ b.val % 7 = a0.val % 7)) ⊆ Gs35Nb.Nb a0 \ B := by intro b hb rw [Finset.mem_filter, hmem] at hb rw [Finset.mem_sdiff] refine ⟨?_, fun hbB => hB b hbB hb.1.2⟩ unfold Gs35Nb.Nb; rw [Finset.mem_filter] exact ⟨(Gs35Nb.isUnit_iff_U b).1 hb.1.1, hb.2⟩ have h1 := Finset.card_le_card hsub rw [Finset.card_sdiff_of_subset hBN, Gs35Nb.Nb_card a0 hU0] at h1 omega
There exist distinct colliding points p, q ∈ S along direction a0, and any direction b satisfying (q₂ - p₂) + b(q₁ - p₁) = 0 is also bad.
Because a0 is bad, the map p ↦ p₂ + a0 p₁ is not injective on S, producing two distinct points p, q ∈ S with p₂ + a0 p₁ = q₂ + a0 q₁. Defining the difference vector (d₁, d₂) = (q₁ - p₁, q₂ - p₂), this collision rearranges to d₂ = -(a0 d₁). For any direction b satisfying d₂ + b d₁ = 0, substitution gives p₂ + b p₁ = q₂ + b q₁, so the projection along b also collides on p and q, meaning b is not injective on S.
uses
not_forallhave hni : ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + a0 * p.1) S := by intro h; exact ha0 ((hmem a0).2 ⟨ha0u, h⟩) obtain ⟨p, hp, q, hq, hpq, hne⟩ : ∃ p ∈ S, ∃ q ∈ S, p.2 + a0 * p.1 = q.2 + a0 * q.1 ∧ p ≠ q := by simp only [Set.InjOn, not_forall] at hni obtain ⟨p, hp, q, hq, h, hne⟩ := hni exact ⟨p, hp, q, hq, h, hne⟩ set d1 := q.1 - p.1 with hd1 set d2 := q.2 - p.2 with hd2 have hd : d2 = -(a0 * d1) := by rw [hd1, hd2]; linear_combination -hpq have bad_of : ∀ b, d2 + b * d1 = 0 → ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + b * p.1) S := by intro b hb hinj exact hne (hinj hp hq (by simp only; rw [hd1, hd2] at hb; linear_combination -hb))
Case 1: When d₁ is a unit, an affine transformation maps S to a 35-point set S' containing (0,0) and (1,34).
We split into cases on whether d₁ is a unit in ℤ/35ℤ. When d₁ is a unit, d₂ = -(a0 d₁) is also a unit, since a0 is a unit. Setting s = d₁⁻¹ and r = -d₂⁻¹, both s and r are units with s d₁ = 1 and r d₂ = -1 = 34 in ℤ/35ℤ. The coordinate transformation φ(u) = (s(u₁ - p₁), r(u₂ - p₂)) is injective, so the transformed set S' = φ(S) has size 35 and contains the images φ(p) = (0,0) and φ(q) = (1, 34).
uses
ZMod.mul_inv_of_unit,isUnit_iff_exists_inv,Prod.ext,Finset.card_image_of_injective,Finset.mem_image,Gs35Nb.neg_one_eqby_cases hu1 : IsUnit d1 · -- normalise the collision to (0,0), (1,34) have hd2u : IsUnit d2 := by rw [hd]; exact (ha0u.mul hu1).neg set s := d1⁻¹ with hs set r := -d2⁻¹ with hr have hsd : s * d1 = 1 := by rw [hs, mul_comm]; exact ZMod.mul_inv_of_unit d1 hu1 have hrd : r * d2 = -1 := by rw [hr, neg_mul, mul_comm, ZMod.mul_inv_of_unit d2 hd2u] have hsu : IsUnit s := isUnit_iff_exists_inv.2 ⟨d1, hsd⟩ have hru : IsUnit r := isUnit_iff_exists_inv.2 ⟨-d2, by rw [mul_neg, hrd, neg_neg]⟩ let φ : ZMod 35 × ZMod 35 → ZMod 35 × ZMod 35 := fun u => (s * (u.1 - p.1), r * (u.2 - p.2)) have hφ : Function.Injective φ := by intro u v h simp only [φ, Prod.mk.injEq] at h have e1 := hsu.mul_left_cancel h.1 have e2 := hru.mul_left_cancel h.2 exact Prod.ext (by linear_combination e1) (by linear_combination e2) set S' := S.image φ with hS' have hcard' : S'.card = 35 := by rw [hS', Finset.card_image_of_injective _ hφ, hcard] have h0 : ((0 : ZMod 35), (0 : ZMod 35)) ∈ S' := Finset.mem_image.2 ⟨p, hp, by simp [φ]⟩ have h1 : ((1 : ZMod 35), (34 : ZMod 35)) ∈ S' := Finset.mem_image.2 ⟨q, hq, by simp only [φ, Prod.mk.injEq] refine ⟨?_, ?_⟩ · rw [← hd1]; exact hsd · rw [← hd2, hrd, Gs35Nb.neg_one_eq]⟩ -- a direction b bad on S' gives the direction a0 * b bad on S
Any direction b that is bad on S' transfers to a bad direction a0 * b on the original set S.
Using r a0 = s (which follows from r d₂ = -1 and s d₁ = 1), expanding the projection on S' shows that (φ(w))₂ + b (φ(w))₁ = r (w₂ + (a0 * b) w₁) - C for a constant C. Because r is a unit, if the linear projection along direction a0 * b were injective on S, the projection along direction b would be injective on S'. By contraposition, if b is bad on S', then a0 * b must be bad on S.
uses
Finset.mem_imagehave transfer : ∀ b, ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + b * p.1) S' → ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + (a0 * b) * p.1) S := by intro b hb hinj apply hb intro u' hu' v' hv' huv obtain ⟨u, hu, rfl⟩ := Finset.mem_image.1 hu' obtain ⟨v, hv, rfl⟩ := Finset.mem_image.1 hv' have hrel : ∀ w : ZMod 35 × ZMod 35, (φ w).2 + b * (φ w).1 = r * (w.2 + (a0 * b) * w.1) - (r * p.2 + b * s * p.1) := by intro w simp only [φ] have hrs : r * a0 = s := by have : r * a0 * d1 = s * d1 := by rw [hsd, mul_assoc, ← neg_neg (a0 * d1), ← hd, mul_neg, hrd, neg_neg] exact hu1.mul_right_cancel this linear_combination (-(b * w.1)) * hrs have e : r * (u.2 + (a0 * b) * u.1) = r * (v.2 + (a0 * b) * v.1) := by have := huv; simp only at this; rw [hrel u, hrel v] at this; linear_combination this rw [hinj hu hv (hru.mul_left_cancel e)]
The classification of anchored configurations rules out having at most two bad directions in the transformed neighbor set.
We invoke good_slopes_fiber35_anchored_neighbors on S'. For any direction on the 35-point set S', injectivity of the projection implies surjectivity onto ℤ/35ℤ by cardinality. The theorem states that no anchored set containing (0,0) and (1,34) can have at most two bad directions among {6, 8, 11, 16, 22, 26, 29, 31}. If three distinct directions a, b, c in this set were bad on S', their transfers a0 * a, a0 * b, a0 * c would be three distinct bad directions in Nb(a0) by Gs35Nb.eight_Nb, contradicting the bound that any set of bad neighbors has size at most 2.
uses
good_slopes_fiber35_anchored_neighbors,Finset.eq_univ_of_card,Finset.card_image_of_injOn,ZMod.card,Finset.mem_univ,Finset.mem_image,Finset.card_eq_three,Gs35Nb.eight_Nb,Finset.card_image_of_injectiveapply good_slopes_fiber35_anchored_neighbors S' (fun a => Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) S') h0 h1 · intro a _ ha; exact ha · intro a _ ha t have himg : S'.image (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn ha, hcard', ZMod.card] have ht : t ∈ S'.image (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) := by rw [himg]; exact Finset.mem_univ t obtain ⟨x, hx, hxt⟩ := Finset.mem_image.1 ht exact ⟨x, hx, hxt⟩ · intro a b c ha hb hc hab hac hbc by_contra hall push Not at hall obtain ⟨hga, hgb, hgc⟩ := hall have hT : ({a, b, c} : Finset (ZMod 35)).card = 3 := Finset.card_eq_three.2 ⟨a, b, c, hab, hac, hbc, rfl⟩ have hB := key (({a, b, c} : Finset (ZMod 35)).image (a0 * ·)) (by intro x hx obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hx simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with rfl | rfl | rfl · exact Gs35Nb.eight_Nb a0 hU0 _ ha · exact Gs35Nb.eight_Nb a0 hU0 _ hb · exact Gs35Nb.eight_Nb a0 hU0 _ hc) (by intro x hx obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hx simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with rfl | rfl | rfl · exact transfer _ hga · exact transfer _ hgb · exact transfer _ hgc) rw [Finset.card_image_of_injective _ ha0u.mul_right_injective, hT] at hB omega · -- a nonunit difference: four bad directions at once
Case 2: When d₁ is not a unit, finite ring arithmetic produces at least 3 bad neighbors, contradicting the size bound.
When d₁ is not a unit, it cannot be zero: if d₁ = 0 then d₂ = -(a0 d₁) = 0, which would contradict p ≠ q. For any non-zero non-unit d₁, the arithmetic lemma Gs35Nb.nonunit_three guarantees that at least 3 elements b ∈ Nb(a0) satisfy -(a0 d₁) + b d₁ = 0. Since d₂ = -(a0 d₁), each such b satisfies d₂ + b d₁ = 0 and is therefore bad on S. This produces a subset of bad neighbors in Nb(a0) of cardinality at least 3, contradicting the established bound that any such subset has cardinality at most 2.
uses
mul_zero,neg_zero,Prod.ext,Gs35Nb.nonunit_three,Gs35Nb.isUnit_iff_U,Finset.filter_subset,Finset.mem_filterhave hd10 : d1 ≠ 0 := by intro h0 apply hne have h2 : d2 = 0 := by rw [hd, h0, mul_zero, neg_zero] exact Prod.ext (by linear_combination -h0) (by linear_combination -h2) have h3 := Gs35Nb.nonunit_three a0 hU0 d1 (fun h => hu1 ((Gs35Nb.isUnit_iff_U d1).2 h)) hd10 have := key ((Gs35Nb.Nb a0).filter (fun b => -(a0 * d1) + b * d1 = 0)) (Finset.filter_subset _ _) (by intro b hb rw [Finset.mem_filter] at hb exact bad_of b (by rw [hd]; exact hb.2)) omega
Finset.card_eq_three- A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements.
Finset.card_image_of_injOn- If a function is injective on a finite set s, then the image of s under f has the same cardinality as s.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_le_card- If s is a subset of t for finite sets, then the cardinality of s is at most that of t.
Finset.card_sdiff_of_subset- If s is a subset of t for finite sets, then the cardinality of t \ s equals the cardinality of t minus the cardinality of s.
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals that of the entire type is the universal finset.
Finset.filter_subset- Filtering a finite set by a predicate yields a subset of the original set.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the set and satisfies the filter predicate.
Finset.mem_image- An element y belongs to the image of s under f if and only if y = f(x) for some x in s.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Gs35Nb.eight_Nb- For any unit a0 in U35 and any x in {6, 8, 11, 16, 22, 26, 29, 31}, the product a0 * x belongs to the neighbor set Nb(a0).
Gs35Nb.isUnit_iff_U- An element of ℤ/35ℤ is a unit if and only if it belongs to the explicit 24-element set U35 of coprime residues.
Gs35Nb.Nb_card- For every unit a0 in U35, its neighbor set Nb(a0) has exactly 8 elements.
Gs35Nb.neg_one_eq- In ℤ/35ℤ, -1 equals 34.
Gs35Nb.nonunit_three- For any unit a0 in U35 and any non-zero non-unit d1, at least 3 elements b in Nb(a0) satisfy -(a0 * d1) + b * d1 = 0.
good_slopes_fiber35_anchored_neighbors- There is no 35-point subset of (ℤ/35ℤ)² containing (0,0) and (1,34) for which at most two directions among {6, 8, 11, 16, 22, 26, 29, 31} fail to be good (injective).
isUnit_iff_exists_inv- An element of a monoid is a unit if and only if it has a multiplicative inverse.
mul_zero- Multiplying any ring element by zero yields zero.
neg_zero- The negation of zero is zero: -0 = 0.
not_forall- The negation of a universal statement is equivalent to an existential statement of the negated predicate.
Prod.ext- Two pairs are equal if their respective first and second components are equal.
ZMod.card- The cardinality of ℤ/nℤ as a finite type is n.
ZMod.mul_inv_of_unit- If a is a unit in ℤ/nℤ, then multiplying a by its inverse yields 1.
- Precomputed facts about the unit group and residue neighborhoods of ℤ/35ℤ in namespace Gs35Nb are proved by exhaustive finite evaluation using the decide tactic.
- The case where d₁ is a unit normalizes S to an anchored configuration via affine scaling and invokes the classification theorem good_slopes_fiber35_anchored_neighbors.
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.
namespace Gs35Nbdef U35 : Finset (ZMod 35) := {1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34}theorem isUnit_iff_U (x : ZMod 35) : IsUnit x ↔ x ∈ U35 := by rw [isUnit_iff_exists_inv]; revert x; decidetheorem nonunit_four : ∀ a0 ∈ U35, ∀ d1 : ZMod 35, d1 ∉ U35 → d1 ≠ 0 → 4 ≤ (U35.filter (fun b => -(a0 * d1) + b * d1 = 0)).card := by decidetheorem eight_sub : ({6,8,11,16,22,26,29,31} : Finset (ZMod 35)) ⊆ U35 := by decidetheorem one_not_eight : (1 : ZMod 35) ∉ ({6,8,11,16,22,26,29,31} : Finset (ZMod 35)) := by decidetheorem neg_one_eq : (-1 : ZMod 35) = 34 := by decidedef Nb (a0 : ZMod 35) : Finset (ZMod 35) := U35.filter (fun b => b ≠ a0 ∧ (b.val % 5 = a0.val % 5 ∨ b.val % 7 = a0.val % 7))theorem Nb_card : ∀ a0 ∈ U35, (Nb a0).card = 8 := by decidetheorem nonunit_three : ∀ a0 ∈ U35, ∀ d1 : ZMod 35, d1 ∉ U35 → d1 ≠ 0 → 3 ≤ ((Nb a0).filter (fun b => -(a0 * d1) + b * d1 = 0)).card := by decidetheorem eight_Nb : ∀ a0 ∈ U35, ∀ x ∈ ({6,8,11,16,22,26,29,31} : Finset (ZMod 35)), a0 * x ∈ Nb a0 := by decideend Gs35Nbtheorem good_slopes_fiber35_bad_neighbors (S : Finset (ZMod 35 × ZMod 35)) (hcard : S.card = 35) (a : ZMod 35) (ha : IsUnit a) (hbad : a ∉ good_slopes_point_directions 35 S) : ((good_slopes_point_directions 35 S).filter (fun b => b ≠ a ∧ (b.val % 5 = a.val % 5 ∨ b.val % 7 = a.val % 7))).card ≤ 5 := by classical by_contra hlt push Not at hlt set a0 := a with ha0def have ha0u : IsUnit a0 := ha have ha0 := hbad have hmem : ∀ a, a ∈ good_slopes_point_directions 35 S ↔ IsUnit a ∧ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) S := by intro a; unfold good_slopes_point_directions; simp -- three bad neighbours are impossible have hU0 : a0 ∈ Gs35Nb.U35 := (Gs35Nb.isUnit_iff_U a0).1 ha0u have key : ∀ B : Finset (ZMod 35), B ⊆ Gs35Nb.Nb a0 → (∀ b ∈ B, ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + b * p.1) S) → B.card ≤ 2 := by intro B hBN hB have hsub : (good_slopes_point_directions 35 S).filter (fun b => b ≠ a0 ∧ (b.val % 5 = a0.val % 5 ∨ b.val % 7 = a0.val % 7)) ⊆ Gs35Nb.Nb a0 \ B := by intro b hb rw [Finset.mem_filter, hmem] at hb rw [Finset.mem_sdiff] refine ⟨?_, fun hbB => hB b hbB hb.1.2⟩ unfold Gs35Nb.Nb; rw [Finset.mem_filter] exact ⟨(Gs35Nb.isUnit_iff_U b).1 hb.1.1, hb.2⟩ have h1 := Finset.card_le_card hsub rw [Finset.card_sdiff_of_subset hBN, Gs35Nb.Nb_card a0 hU0] at h1 omega have hni : ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + a0 * p.1) S := by intro h; exact ha0 ((hmem a0).2 ⟨ha0u, h⟩) obtain ⟨p, hp, q, hq, hpq, hne⟩ : ∃ p ∈ S, ∃ q ∈ S, p.2 + a0 * p.1 = q.2 + a0 * q.1 ∧ p ≠ q := by simp only [Set.InjOn, not_forall] at hni obtain ⟨p, hp, q, hq, h, hne⟩ := hni exact ⟨p, hp, q, hq, h, hne⟩ set d1 := q.1 - p.1 with hd1 set d2 := q.2 - p.2 with hd2 have hd : d2 = -(a0 * d1) := by rw [hd1, hd2]; linear_combination -hpq have bad_of : ∀ b, d2 + b * d1 = 0 → ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + b * p.1) S := by intro b hb hinj exact hne (hinj hp hq (by simp only; rw [hd1, hd2] at hb; linear_combination -hb)) by_cases hu1 : IsUnit d1 · -- normalise the collision to (0,0), (1,34) have hd2u : IsUnit d2 := by rw [hd]; exact (ha0u.mul hu1).neg set s := d1⁻¹ with hs set r := -d2⁻¹ with hr have hsd : s * d1 = 1 := by rw [hs, mul_comm]; exact ZMod.mul_inv_of_unit d1 hu1 have hrd : r * d2 = -1 := by rw [hr, neg_mul, mul_comm, ZMod.mul_inv_of_unit d2 hd2u] have hsu : IsUnit s := isUnit_iff_exists_inv.2 ⟨d1, hsd⟩ have hru : IsUnit r := isUnit_iff_exists_inv.2 ⟨-d2, by rw [mul_neg, hrd, neg_neg]⟩ let φ : ZMod 35 × ZMod 35 → ZMod 35 × ZMod 35 := fun u => (s * (u.1 - p.1), r * (u.2 - p.2)) have hφ : Function.Injective φ := by intro u v h simp only [φ, Prod.mk.injEq] at h have e1 := hsu.mul_left_cancel h.1 have e2 := hru.mul_left_cancel h.2 exact Prod.ext (by linear_combination e1) (by linear_combination e2) set S' := S.image φ with hS' have hcard' : S'.card = 35 := by rw [hS', Finset.card_image_of_injective _ hφ, hcard] have h0 : ((0 : ZMod 35), (0 : ZMod 35)) ∈ S' := Finset.mem_image.2 ⟨p, hp, by simp [φ]⟩ have h1 : ((1 : ZMod 35), (34 : ZMod 35)) ∈ S' := Finset.mem_image.2 ⟨q, hq, by simp only [φ, Prod.mk.injEq] refine ⟨?_, ?_⟩ · rw [← hd1]; exact hsd · rw [← hd2, hrd, Gs35Nb.neg_one_eq]⟩ -- a direction b bad on S' gives the direction a0 * b bad on S have transfer : ∀ b, ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + b * p.1) S' → ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + (a0 * b) * p.1) S := by intro b hb hinj apply hb intro u' hu' v' hv' huv obtain ⟨u, hu, rfl⟩ := Finset.mem_image.1 hu' obtain ⟨v, hv, rfl⟩ := Finset.mem_image.1 hv' have hrel : ∀ w : ZMod 35 × ZMod 35, (φ w).2 + b * (φ w).1 = r * (w.2 + (a0 * b) * w.1) - (r * p.2 + b * s * p.1) := by intro w simp only [φ] have hrs : r * a0 = s := by have : r * a0 * d1 = s * d1 := by rw [hsd, mul_assoc, ← neg_neg (a0 * d1), ← hd, mul_neg, hrd, neg_neg] exact hu1.mul_right_cancel this linear_combination (-(b * w.1)) * hrs have e : r * (u.2 + (a0 * b) * u.1) = r * (v.2 + (a0 * b) * v.1) := by have := huv; simp only at this; rw [hrel u, hrel v] at this; linear_combination this rw [hinj hu hv (hru.mul_left_cancel e)] apply good_slopes_fiber35_anchored_neighbors S' (fun a => Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) S') h0 h1 · intro a _ ha; exact ha · intro a _ ha t have himg : S'.image (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn ha, hcard', ZMod.card] have ht : t ∈ S'.image (fun p : ZMod 35 × ZMod 35 => p.2 + a * p.1) := by rw [himg]; exact Finset.mem_univ t obtain ⟨x, hx, hxt⟩ := Finset.mem_image.1 ht exact ⟨x, hx, hxt⟩ · intro a b c ha hb hc hab hac hbc by_contra hall push Not at hall obtain ⟨hga, hgb, hgc⟩ := hall have hT : ({a, b, c} : Finset (ZMod 35)).card = 3 := Finset.card_eq_three.2 ⟨a, b, c, hab, hac, hbc, rfl⟩ have hB := key (({a, b, c} : Finset (ZMod 35)).image (a0 * ·)) (by intro x hx obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hx simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with rfl | rfl | rfl · exact Gs35Nb.eight_Nb a0 hU0 _ ha · exact Gs35Nb.eight_Nb a0 hU0 _ hb · exact Gs35Nb.eight_Nb a0 hU0 _ hc) (by intro x hx obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hx simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with rfl | rfl | rfl · exact transfer _ hga · exact transfer _ hgb · exact transfer _ hgc) rw [Finset.card_image_of_injective _ ha0u.mul_right_injective, hT] at hB omega · -- a nonunit difference: four bad directions at once have hd10 : d1 ≠ 0 := by intro h0 apply hne have h2 : d2 = 0 := by rw [hd, h0, mul_zero, neg_zero] exact Prod.ext (by linear_combination -h0) (by linear_combination -h2) have h3 := Gs35Nb.nonunit_three a0 hU0 d1 (fun h => hu1 ((Gs35Nb.isUnit_iff_U d1).2 h)) hd10 have := key ((Gs35Nb.Nb a0).filter (fun b => -(a0 * d1) + b * d1 = 0)) (Finset.filter_subset _ _) (by intro b hb rw [Finset.mem_filter] at hb exact bad_of b (by rw [hd]; exact hb.2)) omega