AFTD Auto-Formalizing Theoretical Domains

good_slopes_fiber35_anchored_width_gap

theoremverified

A 35-point set modulo 35 containing (0,0) and (d,-d), with d equal to 1, 5 or 7, has at most 16 good unit directions if each x-fiber and the collision line have at most three points and every bad unit direction has at least three bad neighbors.

Statement

theorem good_slopes_fiber35_anchored_width_gap (S : Finset (ZMod 35 × ZMod 35)) (hcard : S.card = 35)
  (d : ZMod 35) (hd : d = 1 ∨ d = 5 ∨ d = 7)
  (h0 : (0,0) ∈ S) (h1 : (d,-d) ∈ S)
  (hx : ∀ x : ZMod 35, (S.filter (fun p => p.1 = x)).card ≤ 3)
  (hline : (S.filter (fun p => p.2 + p.1 = 0)).card ≤ 3)
  (hneighbors : ∀ a : ZMod 35, IsUnit a → 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) :
  (good_slopes_point_directions 35 S).card ≤ 16
Source
A finite reduction of the colored-fiber lemma for OP-1027, exhaustively checked by CP-SAT in experiment 22119 and independently encoded into UNSAT CNF for d=1 and d=5; the SAT certificates are not yet checked in Lean.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 1
  • 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 splits into cases based on the anchor parameter d ∈ {1, 5, 7}, which determines the coordinates of the known point (d, -d) ∈ S. When d = 5 or d = 7, the point simplifies to (5, 30) or (7, 28) modulo 35, and the bound is dispatched by dedicated auxiliary theorems. When d = 1, so the point is (1, 34), the proof performs a decision-tree case analysis on whether unit directions 2, 29, 4, and 8 belong to the set of good directions, with each of the six resulting subcases resolved by a specialized width-gap lemma.

  1. It suffices to establish the bound in the three cases d = 1, d = 5, and d = 7.

    We perform a case split on the assumption hd, which asserts that d is either 1, 5, or 7.

    line 9

      rcases hd with rfl | rfl | rfl
  2. When d = 1, the set S has at most 16 good unit directions.

    When d = 1, we first rewrite -(1) = 34 in ℤ/35ℤ by computation, so that the hypothesis (d, -d) ∈ S becomes (1, 34) ∈ S. The bound is then resolved by an exhaustive case tree on whether certain unit directions are good directions: first testing whether 2 is good, then whether 29 is good, and in the case where 2 is good but 29 is bad, further testing 4 and 8. The six branches are closed by good_slopes_fiber35_width_gap_case_d1pp, good_slopes_fiber35_width_gap_case_d1pmpp, good_slopes_fiber35_width_gap_case_d1pmpm, good_slopes_fiber35_width_gap_case_d1pmm, good_slopes_fiber35_width_gap_case_d1mp, and good_slopes_fiber35_width_gap_case_d1mm respectively.

    lines 10–22

    uses good_slopes_fiber35_width_gap_case_d1pp, good_slopes_fiber35_width_gap_case_d1pmpp, good_slopes_fiber35_width_gap_case_d1pmpm, good_slopes_fiber35_width_gap_case_d1pmm, good_slopes_fiber35_width_gap_case_d1mp, good_slopes_fiber35_width_gap_case_d1mm

      · have e : (-(1 : ZMod 35)) = 34 := by decide
        rw [e] at h1
        by_cases h2 : (2 : ZMod 35) ∈ good_slopes_point_directions 35 S
        · by_cases h29 : (29 : ZMod 35) ∈ good_slopes_point_directions 35 S
          · exact good_slopes_fiber35_width_gap_case_d1pp S hcard h0 h1 hx hline hneighbors h2 h29
          · by_cases h4 : (4 : ZMod 35) ∈ good_slopes_point_directions 35 S
            · by_cases h8 : (8 : ZMod 35) ∈ good_slopes_point_directions 35 S
              · exact good_slopes_fiber35_width_gap_case_d1pmpp S hcard h0 h1 hx hline hneighbors h2 h4 h8 h29
              · exact good_slopes_fiber35_width_gap_case_d1pmpm S hcard h0 h1 hx hline hneighbors h2 h4 h29 h8
            · exact good_slopes_fiber35_width_gap_case_d1pmm S hcard h0 h1 hx hline hneighbors h2 h29 h4
        · by_cases h29 : (29 : ZMod 35) ∈ good_slopes_point_directions 35 S
          · exact good_slopes_fiber35_width_gap_case_d1mp S hcard h0 h1 hx hline hneighbors h29 h2
          · exact good_slopes_fiber35_width_gap_case_d1mm S hcard h0 h1 hx hline hneighbors h2 h29
  3. When d = 5, the set S has at most 16 good unit directions.

    When d = 5, we evaluate -(5) = 30 in ℤ/35ℤ by computation, converting the hypothesis (d, -d) ∈ S to (5, 30) ∈ S. The bound is then established directly by good_slopes_fiber35_width_gap_case_d5.

    lines 23–25

    uses good_slopes_fiber35_width_gap_case_d5

      · have e : (-(5 : ZMod 35)) = 30 := by decide
        rw [e] at h1
        exact good_slopes_fiber35_width_gap_case_d5 S hcard h0 h1 hx hline hneighbors
  4. When d = 7, the set S has at most 16 good unit directions.

    When d = 7, we evaluate -(7) = 28 in ℤ/35ℤ by computation, converting the hypothesis (d, -d) ∈ S to (7, 28) ∈ S. The bound is then established directly by good_slopes_fiber35_width_gap_case_d7.

    lines 26–28

    uses good_slopes_fiber35_width_gap_case_d7

      · have e : (-(7 : ZMod 35)) = 28 := by decide
        rw [e] at h1
        exact good_slopes_fiber35_width_gap_case_d7 S hcard h0 h1 hx hline hneighbors
good_slopes_fiber35_width_gap_case_d1pp
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (1,34) that satisfies the fiber, collision line, and neighbor bounds, if both 2 and 29 are good directions, then S has at most 16 good unit directions.
good_slopes_fiber35_width_gap_case_d1pmpp
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (1,34) satisfying the given bounds, if 2, 4, and 8 are good directions but 29 is not, then S has at most 16 good unit directions.
good_slopes_fiber35_width_gap_case_d1pmpm
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (1,34) satisfying the given bounds, if 2 and 4 are good directions but 29 and 8 are not, then S has at most 16 good unit directions.
good_slopes_fiber35_width_gap_case_d1pmm
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (1,34) satisfying the given bounds, if 2 is a good direction but 29 and 4 are not, then S has at most 16 good unit directions.
good_slopes_fiber35_width_gap_case_d1mp
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (1,34) satisfying the given bounds, if 29 is a good direction but 2 is not, then S has at most 16 good unit directions.
good_slopes_fiber35_width_gap_case_d1mm
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (1,34) satisfying the given bounds, if neither 2 nor 29 is a good direction, then S has at most 16 good unit directions.
good_slopes_fiber35_width_gap_case_d5
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (5,30) satisfying the given bounds, S has at most 16 good unit directions.
good_slopes_fiber35_width_gap_case_d7
For a 35-point set S ⊆ ℤ/35ℤ × ℤ/35ℤ containing (0,0) and (7,28) satisfying the given bounds, S has at most 16 good unit directions.

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_fiber35_anchored_width_gap (S : Finset (ZMod 35 × ZMod 35)) (hcard : S.card = 35)  (d : ZMod 35) (hd : d = 1 ∨ d = 5 ∨ d = 7)  (h0 : (0,0) ∈ S) (h1 : (d,-d) ∈ S)  (hx : ∀ x : ZMod 35, (S.filter (fun p => p.1 = x)).card ≤ 3)  (hline : (S.filter (fun p => p.2 + p.1 = 0)).card ≤ 3)  (hneighbors : ∀ a : ZMod 35, IsUnit a → 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) :  (good_slopes_point_directions 35 S).card ≤ 16 := by  rcases hd with rfl | rfl | rfl  · have e : (-(1 : ZMod 35)) = 34 := by decide    rw [e] at h1    by_cases h2 : (2 : ZMod 35) ∈ good_slopes_point_directions 35 S    · by_cases h29 : (29 : ZMod 35) ∈ good_slopes_point_directions 35 S      · exact good_slopes_fiber35_width_gap_case_d1pp S hcard h0 h1 hx hline hneighbors h2 h29      · by_cases h4 : (4 : ZMod 35) ∈ good_slopes_point_directions 35 S        · by_cases h8 : (8 : ZMod 35) ∈ good_slopes_point_directions 35 S          · exact good_slopes_fiber35_width_gap_case_d1pmpp S hcard h0 h1 hx hline hneighbors h2 h4 h8 h29          · exact good_slopes_fiber35_width_gap_case_d1pmpm S hcard h0 h1 hx hline hneighbors h2 h4 h29 h8        · exact good_slopes_fiber35_width_gap_case_d1pmm S hcard h0 h1 hx hline hneighbors h2 h29 h4    · by_cases h29 : (29 : ZMod 35) ∈ good_slopes_point_directions 35 S      · exact good_slopes_fiber35_width_gap_case_d1mp S hcard h0 h1 hx hline hneighbors h29 h2      · exact good_slopes_fiber35_width_gap_case_d1mm S hcard h0 h1 hx hline hneighbors h2 h29  · have e : (-(5 : ZMod 35)) = 30 := by decide    rw [e] at h1    exact good_slopes_fiber35_width_gap_case_d5 S hcard h0 h1 hx hline hneighbors  · have e : (-(7 : ZMod 35)) = 28 := by decide    rw [e] at h1    exact good_slopes_fiber35_width_gap_case_d7 S hcard h0 h1 hx hline hneighbors
See it in the graphDiscuss this resultChallenge it