good_slopes_prime7_anchored_line
Let e be one of 2, 3, 4, 5, 6. A set of seven points over the field with seven elements that contains (0,0) and (1,6), and on which y+ax is injective for every a among 2, 3, 4, 5, 6 except e, lies on the line y+x=0.
Statement
theorem good_slopes_prime7_anchored_line (S : Finset (ZMod 7 × ZMod 7)) (e : ZMod 7) (hcard : S.card = 7) (h0 : (0,0) ∈ S) (h1 : (1,6) ∈ S) (he : e ∈ ({2,3,4,5,6} : Finset (ZMod 7))) (hinj : ∀ a : ZMod 7, a ∈ ({2,3,4,5,6} : Finset (ZMod 7)) → a ≠ e → Set.InjOn (fun p : ZMod 7 × ZMod 7 => p.2 + a * p.1) S) : ∀ p ∈ S, p.2 + p.1 = 0
- Source
- Finite prime-plane direction lemma for the 35-point fiber route to OP-1027; compare arXiv:2611.01465, Lemma 4.7.
- 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
We prove by contradiction that every point $p \in S$ satisfies $p.2 + p.1 = 0$. If some $p \in S$ does not lie on this line, then because the linear forms $y + ax$ are injective on $S$, every element of $S$ must be mutually compatible with $(0,0)$, $(1,6)$, and $p$, so $S \subseteq \text{candidates7}(e, p)$. By a finite exhaustive search (`prime7_candidate_table`), this candidate set has at most 7 elements, and any candidate set of size 7 must contain an incompatible pair. Since $|S| = 7$, we must have $S = \text{candidates7}(e, p)$, forcing $S$ to contain an incompatible pair, which contradicts the injectivity of the forms on $S$.
Compatibility between any two points is decidable.
We unfold the definition of `compatible7` into a bounded universal quantification over the finite set $\{2,3,4,5,6\}$, allowing Lean's typeclass inference to synthesize a decision procedure for compatibility.
unfold compatible7 infer_instance
For every valid choice of slope $e$ and point $p$ not on $y+x=0$ that is compatible with $(0,0)$ and $(1,6)$, the candidate set has size at most 7, and if it has size 7, it contains an incompatible pair. automation
Because $\mathbb{F}_7$ is finite, there are only 5 possible values for $e$ and 49 possible points $p$. The statement is proved by exhaustive evaluation of all cases using the `decide` tactic.
(((candidates7 e p).product (candidates7 e p)).filter fun qr => ¬ compatible7 e qr.1 qr.2).Nonempty) := by decide
Suppose for contradiction that some point $p \in S$ does not satisfy $p.2 + p.1 = 0$.
We enable classical reasoning, fix an arbitrary point $p \in S$, and assume for contradiction that $p$ does not lie on the line $y+x=0$, that is, $p.2 + p.1 \neq 0$.
classical intro p hp by_contra hpbad
The point $p$ is compatible with $(0,0)$.
Since $(0,0) \in S$ and $p \in S$, the injectivity of the linear forms $y + ax$ on $S$ for every $a \in \{2,3,4,5,6\} \setminus \{e\}$ implies that $p$ and $(0,0)$ cannot agree on any such form unless $p = (0,0)$. Thus $p$ and $(0,0)$ are compatible.
have hp0 : compatible7 e p (0,0) := by intro a ha hne h exact hinj a ha hne hp h0 h
The point $p$ is compatible with $(1,6)$.
Similarly, since $(1,6) \in S$ and $p \in S$, injectivity of each allowed linear form on $S$ implies that $p$ and $(1,6)$ are compatible.
have hp1 : compatible7 e p (1,6) := by intro a ha hne h exact hinj a ha hne hp h1 h
The set $S$ is a subset of the candidate set $\text{candidates7}(e, p)$.
For any $q \in S$, the injectivity hypothesis applied to pairs $(q, (0,0))$, $(q, (1,6))$, and $(q, p)$ shows that $q$ is compatible with $(0,0)$, with $(1,6)$, and with $p$. Unfolding the definition of `candidates7`, this shows $q \in \text{candidates7}(e, p)$.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hsub : S ⊆ candidates7 e p := by intro q hq simp only [candidates7, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_⟩ · intro a ha hne h; exact hinj a ha hne hq h0 h · intro a ha hne h; exact hinj a ha hne hq h1 h · intro a ha hne h; exact hinj a ha hne hq hp h
The candidate set has at most 7 points, and if its size is 7, it contains an incompatible pair of points.
We apply the precomputed lemma `prime7_candidate_table` to $e$ and $p$, using the assumptions $e \in \{2,3,4,5,6\}$, $p.2 + p.1 \neq 0$, and the compatibility of $p$ with $(0,0)$ and $(1,6)$.
uses
prime7_candidate_tableobtain ⟨hupper, hconflict⟩ := prime7_candidate_table e p he hpbad hp0 hp1The candidate set $\text{candidates7}(e, p)$ has cardinality exactly 7.
Since $S \subseteq \text{candidates7}(e, p)$ and $|S| = 7$, `Finset.card_le_card` gives $7 \le |\text{candidates7}(e, p)|$. Together with the upper bound $|\text{candidates7}(e, p)| \le 7$, linear arithmetic (`omega`) forces the cardinality to be 7.
uses
Finset.card_le_cardhave hc : (candidates7 e p).card = 7 := by have hle := Finset.card_le_card hsub omega
$S$ is equal to the candidate set $\text{candidates7}(e, p)$.
Because $S \subseteq \text{candidates7}(e, p)$ and both sets have cardinality 7, they must be equal by `Finset.eq_of_subset_of_card_le`.
uses
Finset.eq_of_subset_of_card_lehave hEq : S = candidates7 e p := Finset.eq_of_subset_of_card_le hsub (by omega)
There exists a pair of points in $S$ that are incompatible with each other.
Since the candidate set has size 7, the conflict property from `prime7_candidate_table` yields an incompatible pair $qr = (q, r)$ in $\text{candidates7}(e, p) \times \text{candidates7}(e, p)$. Because $S = \text{candidates7}(e, p)$, both $q$ and $r$ belong to $S$.
uses
Finset.mem_filter.mp,Finset.mem_product.mpobtain ⟨qr, hqr⟩ := hconflict hc have hh := Finset.mem_filter.mp hqr have hprod := Finset.mem_product.mp hh.1 have hq : qr.1 ∈ S := by rw [hEq]; exact hprod.1 have hr : qr.2 ∈ S := by rw [hEq]; exact hprod.2
Contradiction: any two points in $S$ must be compatible.
Because $q, r \in S$, the injectivity of the linear forms on $S$ implies that $q$ and $r$ are compatible, contradicting the fact that $(q, r)$ was an incompatible pair. This completes the proof by contradiction.
apply hh.2 intro a ha hne h exact hinj a ha hne hq hr h
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the ambient finset and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The conjunction of `True` and any proposition $p$ is equivalent to $p$.
prime7_candidate_table- For any excluded slope $e \in \{2,3,4,5,6\}$ and any point $p$ off the line $y+x=0$ compatible with $(0,0)$ and $(1,6)$, the candidate set has at most 7 elements, and if it has exactly 7 elements, it contains an incompatible pair.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to that of the other.
Finset.eq_of_subset_of_card_le- A subset of a finite set with at least the same cardinality is equal to the whole set.
Finset.mem_filter.mp- If an element belongs to a filtered finset, then it belongs to the ambient finset and satisfies the predicate.
Finset.mem_product.mp- If a pair belongs to the Cartesian product of two finsets, its components belong to the respective factor finsets.
- The lemma `prime7_candidate_table`, which establishes the cardinality bound and existence of incompatible pairs for candidate sets off the line, is verified by computational exhaustion using `decide` on the finite field $\mathbb{F}_7$.
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.
set_option maxRecDepth 10000set_option maxHeartbeats 15000000private def form7 (a : ZMod 7) (p : ZMod 7 × ZMod 7) : ZMod 7 := p.2 + a * p.1private def compatible7 (e : ZMod 7) (p q : ZMod 7 × ZMod 7) : Prop := ∀ a : ZMod 7, a ∈ ({2,3,4,5,6} : Finset (ZMod 7)) → a ≠ e → form7 a p = form7 a q → p = qprivate instance (e : ZMod 7) (p q : ZMod 7 × ZMod 7) : Decidable (compatible7 e p q) := by unfold compatible7 infer_instanceprivate def candidates7 (e : ZMod 7) (p : ZMod 7 × ZMod 7) : Finset (ZMod 7 × ZMod 7) := Finset.univ.filter fun q => compatible7 e q (0,0) ∧ compatible7 e q (1,6) ∧ compatible7 e q pprivate theorem prime7_candidate_table : ∀ (e : ZMod 7) (p : ZMod 7 × ZMod 7), e ∈ ({2,3,4,5,6} : Finset (ZMod 7)) → p.2 + p.1 ≠ 0 → compatible7 e p (0,0) → compatible7 e p (1,6) → (candidates7 e p).card ≤ 7 ∧ ((candidates7 e p).card = 7 → (((candidates7 e p).product (candidates7 e p)).filter fun qr => ¬ compatible7 e qr.1 qr.2).Nonempty) := by decidetheorem good_slopes_prime7_anchored_line (S : Finset (ZMod 7 × ZMod 7)) (e : ZMod 7) (hcard : S.card = 7) (h0 : (0,0) ∈ S) (h1 : (1,6) ∈ S) (he : e ∈ ({2,3,4,5,6} : Finset (ZMod 7))) (hinj : ∀ a : ZMod 7, a ∈ ({2,3,4,5,6} : Finset (ZMod 7)) → a ≠ e → Set.InjOn (fun p : ZMod 7 × ZMod 7 => p.2 + a * p.1) S) : ∀ p ∈ S, p.2 + p.1 = 0 := by classical intro p hp by_contra hpbad have hp0 : compatible7 e p (0,0) := by intro a ha hne h exact hinj a ha hne hp h0 h have hp1 : compatible7 e p (1,6) := by intro a ha hne h exact hinj a ha hne hp h1 h have hsub : S ⊆ candidates7 e p := by intro q hq simp only [candidates7, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_⟩ · intro a ha hne h; exact hinj a ha hne hq h0 h · intro a ha hne h; exact hinj a ha hne hq h1 h · intro a ha hne h; exact hinj a ha hne hq hp h obtain ⟨hupper, hconflict⟩ := prime7_candidate_table e p he hpbad hp0 hp1 have hc : (candidates7 e p).card = 7 := by have hle := Finset.card_le_card hsub omega have hEq : S = candidates7 e p := Finset.eq_of_subset_of_card_le hsub (by omega) obtain ⟨qr, hqr⟩ := hconflict hc have hh := Finset.mem_filter.mp hqr have hprod := Finset.mem_product.mp hh.1 have hq : qr.1 ∈ S := by rw [hEq]; exact hprod.1 have hr : qr.2 ∈ S := by rw [hEq]; exact hprod.2 apply hh.2 intro a ha hne h exact hinj a ha hne hq hr h