AFTD Auto-Formalizing Theoretical Domains

good_slopes_fiber35_crt_rectangle_exclusion

theoremverified

A 35-point set with x-width at most three cannot have all unit directions good outside a rectangle whose mod-5 coordinates are two nonzero residues and whose mod-7 coordinates form a nonzero multiple of {1,2,4}, while any unit direction is bad.

Statement

theorem good_slopes_fiber35_crt_rectangle_exclusion (S : Finset (ZMod 35 × ZMod 35)) (hcard : S.card = 35) (hwidth : ∀ x : ZMod 35, (S.filter fun p => p.1 = x).card ≤ 3) (a₁ a₂ : ZMod 5) (t : ZMod 7) (ha₁ : a₁ ≠ 0) (ha₂ : a₂ ≠ 0) (ha : a₁ ≠ a₂) (ht : t ≠ 0) (hgood : ∀ b : ZMod 35, IsUnit b → (((ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b ≠ a₁) ∧ (ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b ≠ a₂)) ∨ ((ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ t) ∧ (ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ 2*t) ∧ (ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ 4*t))) → b ∈ good_slopes_point_directions 35 S) (hbad : ∃ b : ZMod 35, IsUnit b ∧ b ∉ good_slopes_point_directions 35 S) : False
Source
CRT normalization of the three checked 35-point rectangle obstructions in the reduction for OP-1027.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_unanchored_rectFor any 35-point set of x-width at most three, injectivity in the 18 directions outside any of the three normalized two-by-three…
  • good_slopes_35_rectangle_tableThe three normalized missing-direction lists are exactly the 2-by-3 CRT rectangles with mod-5 ratios 2, 3 and 4 and mod-7 coordinates 1, 2…
Used by 1
  • good_slopes_gap105_from_rectangleA permutation modulo 105 has at most 40 good slopes if any hypothetical excess produces a 35-point fiber with the stated rectangle and…

Lean source view module on GitHub

set_option maxHeartbeats 4000000
private def aftd_crt35_good (r : Fin 3) : Finset (ZMod 35) :=
  if r = 0 then {3,4,6,8,9,12,13,17,18,19,23,24,26,27,29,31,33,34}
  else if r = 1 then {2,3,4,6,9,12,13,17,19,22,24,26,27,29,31,32,33,34}
  else {2,3,6,8,12,13,17,18,19,22,23,24,26,27,31,32,33,34}

private def aftd_crt35_unit : 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}

private theorem aftd_crt35__good_units : ∀ r : Fin 3, aftd_crt35_good r ⊆ aftd_crt35_unit := by decide

private theorem aftd_crt35__unit_table : ∀ b : ZMod 35, Nat.Coprime b.val 35 ↔ b ∈ aftd_crt35_unit := by decide

private def aftd_crt35_ratio (r : Fin 3) : ZMod 5 := (r.val + 2 : ℕ)

private theorem aftd_crt35__ratio5_table : ∀ (a₁ a₂ x : ZMod 5),
    a₁ ≠ 0 → a₂ ≠ 0 → a₁ ≠ a₂ → (x = a₁ ∨ x = a₂) →
    ∃ r : Fin 3, ∀ z : ZMod 5, z ≠ 1 → z ≠ aftd_crt35_ratio r → x*z ≠ a₁ ∧ x*z ≠ a₂ := by decide

private theorem aftd_crt35__coset7_table : ∀ (t y : ZMod 7), t ≠ 0 →
    (y = t ∨ y = 2*t ∨ y = 4*t) → ∀ z : ZMod 7, z ≠ 1 → z ≠ 2 → z ≠ 4 →
    y*z ≠ t ∧ y*z ≠ 2*t ∧ y*z ≠ 4*t := by decide

private theorem aftd_crt35__mask_table : ∀ (r : Fin 3) (b : ZMod 35), b ∈ aftd_crt35_good r →
    ((ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b ≠ 1) ∧
     (ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b ≠ aftd_crt35_ratio r)) ∨
    ((ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ 1) ∧
     (ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ 2) ∧
     (ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ 4)) := by decide

private theorem aftd_crt35__rectangle_normalization_table :
    ∀ (a₁ a₂ x : ZMod 5) (t y : ZMod 7),
      a₁ ≠ 0 → a₂ ≠ 0 → a₁ ≠ a₂ → t ≠ 0 → (x = a₁ ∨ x = a₂) →
      (y = t ∨ y = 2*t ∨ y = 4*t) →
      ∃ r : Fin 3, ∀ b ∈ aftd_crt35_good r,
        ((x*(ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b) ≠ a₁) ∧
         (x*(ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b) ≠ a₂)) ∨
        ((y*(ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b) ≠ t) ∧
         (y*(ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b) ≠ 2*t) ∧
         (y*(ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b) ≠ 4*t)) := by
  intro a₁ a₂ x t y h1 h2 hne ht hx hy
  obtain ⟨r,hr⟩ := aftd_crt35__ratio5_table a₁ a₂ x h1 h2 hne hx
  refine ⟨r,?_⟩
  intro b hb
  rcases aftd_crt35__mask_table r b hb with h5 | h7
  · exact Or.inl (hr _ h5.1 h5.2)
  · exact Or.inr (aftd_crt35__coset7_table t y ht hy _ h7.1 h7.2.1 h7.2.2)

theorem good_slopes_fiber35_crt_rectangle_exclusion (S : Finset (ZMod 35 × ZMod 35)) (hcard : S.card = 35) (hwidth : ∀ x : ZMod 35, (S.filter fun p => p.1 = x).card ≤ 3) (a₁ a₂ : ZMod 5) (t : ZMod 7) (ha₁ : a₁ ≠ 0) (ha₂ : a₂ ≠ 0) (ha : a₁ ≠ a₂) (ht : t ≠ 0) (hgood : ∀ b : ZMod 35, IsUnit b → (((ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b ≠ a₁) ∧ (ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5) b ≠ a₂)) ∨ ((ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ t) ∧ (ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ 2*t) ∧ (ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7) b ≠ 4*t))) → b ∈ good_slopes_point_directions 35 S) (hbad : ∃ b : ZMod 35, IsUnit b ∧ b ∉ good_slopes_point_directions 35 S) : False := by
  classical
  obtain ⟨a,hau,habad⟩ := hbad
  let c5 : ZMod 35 →+* ZMod 5 := ZMod.castHom (by decide : 5 ∣ 35) (ZMod 5)
  let c7 : ZMod 35 →+* ZMod 7 := ZMod.castHom (by decide : 7 ∣ 35) (ZMod 7)
  have h5 : c5 a = a₁ ∨ c5 a = a₂ := by
    by_contra hh
    have h1 : c5 a ≠ a₁ := fun h => hh (Or.inl h)
    have h2 : c5 a ≠ a₂ := fun h => hh (Or.inr h)
    exact habad (hgood a hau (Or.inl ⟨h1,h2⟩))
  have h7 : c7 a = t ∨ c7 a = 2*t ∨ c7 a = 4*t := by
    by_contra hh
    have h1 : c7 a ≠ t := fun h => hh (Or.inl h)
    have h2 : c7 a ≠ 2*t := fun h => hh (Or.inr (Or.inl h))
    have h3 : c7 a ≠ 4*t := fun h => hh (Or.inr (Or.inr h))
    exact habad (hgood a hau (Or.inr ⟨h1,h2,h3⟩))
  obtain ⟨r,hr⟩ := aftd_crt35__rectangle_normalization_table a₁ a₂ (c5 a) t (c7 a) ha₁ ha₂ ha ht h5 h7
  let au : (ZMod 35)ˣ := hau.unit
  have hav : (au : ZMod 35) = a := hau.unit_spec
  let aftd_crt_scale_map : ZMod 35 × ZMod 35 → ZMod 35 × ZMod 35 := fun p => (p.1,((au⁻¹ : (ZMod 35)ˣ) : ZMod 35)*p.2)
  have hH : Function.Injective aftd_crt_scale_map := by
    intro p q heq
    have hx := congrArg Prod.fst heq
    have hy := congrArg Prod.snd heq
    change p.1 = q.1 at hx
    change ((au⁻¹ : (ZMod 35)ˣ) : ZMod 35)*p.2 = ((au⁻¹ : (ZMod 35)ˣ) : ZMod 35)*q.2 at hy
    exact Prod.ext hx ((au⁻¹).isUnit.mul_right_injective hy)
  have hscale (p : ZMod 35 × ZMod 35) (b : ZMod 35) :
      a*((aftd_crt_scale_map p).2+b*(aftd_crt_scale_map p).1) = p.2+(a*b)*p.1 := by
    have haa : a*((au⁻¹ : (ZMod 35)ˣ) : ZMod 35) = 1 := by rw [← hav]; simp
    change a*(((au⁻¹ : (ZMod 35)ˣ) : ZMod 35)*p.2+b*p.1) = _
    calc
      _ = (a*((au⁻¹ : (ZMod 35)ˣ) : ZMod 35))*p.2+(a*b)*p.1 := by ring
      _ = _ := by rw [haa]; ring
  let T := S.image aftd_crt_scale_map
  have hTc : T.card = 35 := by rw [Finset.card_image_of_injective _ hH,hcard]
  have hTwidth : ∀ x : ZMod 35, (T.filter fun p => p.1=x).card ≤ 3 := by
    intro x
    have heq : T.filter (fun p => p.1=x) = (S.filter fun p => p.1=x).image aftd_crt_scale_map := by
      ext p
      simp only [T,Finset.mem_filter,Finset.mem_image]
      constructor
      · rintro ⟨⟨q,hq,rfl⟩,hx⟩
        exact ⟨q,⟨hq,hx⟩,rfl⟩
      · rintro ⟨q,⟨hq,hx⟩,rfl⟩
        exact ⟨⟨q,hq,rfl⟩,hx⟩
    rw [heq,Finset.card_image_of_injective _ hH]
    exact hwidth x
  have hTbad : ¬ Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2+p.1) T := by
    intro hi
    apply habad
    have haform : Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2+a*p.1) S := by
      intro p hp q hq heq
      apply hH
      apply hi (Finset.mem_image_of_mem _ hp) (Finset.mem_image_of_mem _ hq)
      apply hau.mul_right_injective
      calc
        _ = p.2+a*p.1 := by simpa using hscale p 1
        _ = q.2+a*q.1 := heq
        _ = _ := by symm; simpa using hscale q 1
    simp [good_slopes_point_directions,hau,haform]
  have hTgood : ∀ b ∈ aftd_crt35_good r,
      Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2+b*p.1) T := by
    intro b hb p hp q hq heq
    have hbu : IsUnit b := by
      have hh : Nat.Coprime b.val 35 := (aftd_crt35__unit_table b).mpr (aftd_crt35__good_units r hb)
      simpa only [ZMod.natCast_zmod_val] using (ZMod.isUnit_iff_coprime b.val 35).mpr hh
    have hout := hr b hb
    have hout' : ((c5 (a*b) ≠ a₁) ∧ (c5 (a*b) ≠ a₂)) ∨
        ((c7 (a*b) ≠ t) ∧ (c7 (a*b) ≠ 2*t) ∧ (c7 (a*b) ≠ 4*t)) := by
      simpa only [map_mul] using hout
    have hg := hgood (a*b) (hau.mul hbu) hout'
    have hi : Set.InjOn (fun p : ZMod 35 × ZMod 35 => p.2+(a*b)*p.1) S :=
      (Finset.mem_filter.mp hg).2.2
    obtain ⟨x,hx,hxp⟩ := Finset.mem_image.mp hp
    obtain ⟨y,hy,hyq⟩ := Finset.mem_image.mp hq
    have heq' : (aftd_crt_scale_map x).2+b*(aftd_crt_scale_map x).1 = (aftd_crt_scale_map y).2+b*(aftd_crt_scale_map y).1 := by simpa [hxp,hyq] using heq
    have hh := congrArg (fun z : ZMod 35 => a*z) heq'
    rw [hscale,hscale] at hh
    have hxy : x = y := hi hx hy hh
    exact hxp.symm.trans ((congrArg aftd_crt_scale_map hxy).trans hyq)
  apply good_slopes_fiber35_unanchored_rect T hTc hTwidth r
  · exact hTgood
  · exact hTbad
See it in the graphDiscuss this resultChallenge it