AFTD Auto-Formalizing Theoretical Domains

good_slopes_prime7_five_on_line

theoremverified

Let S be a finite set of points over the field with seven elements. If it contains a point off y+x=0 and three distinct directions chosen from 2, 3, 4, 5, 6 are injective on S, then at most four points of S lie on y+x=0.

Statement

theorem good_slopes_prime7_five_on_line (S : Finset (ZMod 7 × ZMod 7))
    (A : Finset (ZMod 7)) (hA : A ⊆ ({2,3,4,5,6} : Finset (ZMod 7)))
    (hAc : A.card = 3) (hinj : ∀ a ∈ A, Set.InjOn (fun p : ZMod 7 × ZMod 7 => p.2 + a * p.1) S)
    (p : ZMod 7 × ZMod 7) (hp : p ∈ S) (hpbad : p.2 + p.1 ≠ 0) :
    (S.filter fun q => q.2 + q.1 = 0).card ≤ 4
Source
Elementary prime-field line-counting step for the 35-point fiber route to OP-1027.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • 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…

The proof, explained

The proof bounds the number of points of $S$ on the line $y+x=0$ by comparing them to an explicitly defined set of candidate points, $\mathrm{diagCandidates7}(A, p)$, which consists of points on the line that share no projection value along any slope $a \in A$ with the given off-line point $p$. Because each slope in $A$ defines an injective map on $S$ and $p$ is not on the line, no point of $S$ on the line can share a projection value with $p$, showing that the points of $S$ on the line form a subset of the candidates. An exhaustive finite check (`prime7_line_table`) establishes that any such candidate set has size at most 4, which immediately bounds the number of collinear points in $S$.

  1. For any point off the line $y+x=0$ and any three chosen directions, at most 4 points on the line share no projection value with that point. automation

    Because $\mathbb{Z}/7\mathbb{Z}$ is finite, the claim that $|\mathrm{diagCandidates7}(A, p)| \le 4$ for all $p$ off the line and all $3$-element subsets $A \subseteq \{2,3,4,5,6\}$ is verified by exhaustive computation over all possibilities.

    line 11

        (diagCandidates7 A p).card ≤ 4 := by decide
  2. Every point in $S$ lying on $y+x=0$ belongs to the candidate set $\mathrm{diagCandidates7}(A, p)$.

    Let $q \in S$ be a point on the line $y+x=0$. To show $q \in \mathrm{diagCandidates7}(A, p)$, we must show that no direction $a \in A$ gives $p.2 + a \cdot p.1 = q.2 + a \cdot q.1$. If such an $a$ existed, then since the map $p' \mapsto p'.2 + a \cdot p'.1$ is injective on $S$ and both $p, q \in S$, it would follow that $p = q$. But $p$ does not lie on the line $y+x=0$, whereas $q$ does, a contradiction. Thus no such $a$ exists, so the number of matching directions is zero, meaning $q$ is indeed in $\mathrm{diagCandidates7}(A, p)$.

    lines 18–29

    uses Finset.mem_filter.mp, Finset.card_eq_zero.mpr, Finset.filter_eq_empty_iff.mpr

      classical
      have hsub : (S.filter fun q => q.2 + q.1 = 0) ⊆ diagCandidates7 A p := by
        intro q hq
        have ⟨hqS,hqdiag⟩ := Finset.mem_filter.mp hq
        simp only [diagCandidates7, Finset.mem_filter, Finset.mem_univ, true_and]
        refine ⟨hqdiag, ?_⟩
        apply Finset.card_eq_zero.mpr
        apply Finset.filter_eq_empty_iff.mpr
        intro a ha heq
        have hpq : p = q := hinj a ha hp hqS heq
        subst p
        exact hpbad hqdiag
  3. At most four points of $S$ lie on the line $y+x=0$.

    The number of points of $S$ on the line is bounded by the cardinality of $\mathrm{diagCandidates7}(A, p)$ via the inclusion $h_{\mathrm{sub}}$, and this cardinality is at most 4 by `prime7_line_table`.

    line 30

    uses Finset.card_le_card, prime7_line_table

      exact (Finset.card_le_card hsub).trans (prime7_line_table p A hpbad hA hAc)
Finset.card_le_card
The cardinality of a sub-finset is less than or equal to the cardinality of the ambient finset.
prime7_line_table
For any point $p$ off the line $y+x=0$ and any 3-element subset $A \subseteq \{2,3,4,5,6\}$, the set of candidate points on $y+x=0$ has size at most 4.
Finset.mem_filter.mp
An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
Finset.card_eq_zero.mpr
A finset has cardinality zero if and only if it is empty.
Finset.filter_eq_empty_iff.mpr
A filtered finset is empty if and only if none of its elements satisfy the predicate.

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

set_option maxRecDepth 10000set_option maxHeartbeats 15000000private def form7x (a : ZMod 7) (p : ZMod 7 × ZMod 7) : ZMod 7 := p.2 + a * p.1private def diagCandidates7 (A : Finset (ZMod 7)) (p : ZMod 7 × ZMod 7) : Finset (ZMod 7 × ZMod 7) :=  Finset.univ.filter fun q => q.2 + q.1 = 0 ∧ (A.filter fun a => form7x a p = form7x a q).card = 0private theorem prime7_line_table : ∀ (p : ZMod 7 × ZMod 7) (A : Finset (ZMod 7)),    p.2 + p.1 ≠ 0 → A ⊆ ({2,3,4,5,6} : Finset (ZMod 7)) → A.card = 3 →    (diagCandidates7 A p).card ≤ 4 := by decidetheorem good_slopes_prime7_five_on_line (S : Finset (ZMod 7 × ZMod 7))    (A : Finset (ZMod 7)) (hA : A ⊆ ({2,3,4,5,6} : Finset (ZMod 7)))    (hAc : A.card = 3) (hinj : ∀ a ∈ A, Set.InjOn (fun p : ZMod 7 × ZMod 7 => p.2 + a * p.1) S)    (p : ZMod 7 × ZMod 7) (hp : p ∈ S) (hpbad : p.2 + p.1 ≠ 0) :    (S.filter fun q => q.2 + q.1 = 0).card ≤ 4 := by  classical  have hsub : (S.filter fun q => q.2 + q.1 = 0) ⊆ diagCandidates7 A p := by    intro q hq    have ⟨hqS,hqdiag⟩ := Finset.mem_filter.mp hq    simp only [diagCandidates7, Finset.mem_filter, Finset.mem_univ, true_and]    refine ⟨hqdiag, ?_⟩    apply Finset.card_eq_zero.mpr    apply Finset.filter_eq_empty_iff.mpr    intro a ha heq    have hpq : p = q := hinj a ha hp hqS heq    subst p    exact hpbad hqdiag  exact (Finset.card_le_card hsub).trans (prime7_line_table p A hpbad hA hAc)
See it in the graphDiscuss this resultChallenge it