/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 102
Reference: erdosproblems.com/102
@[expose] public sectionnamespace Erdos102open EuclideanGeometry Filteropen scoped Classical in
The number of points of P that lie on L.
noncomputable def pointsOn (P : Finset ℝ²) (L : AffineSubspace ℝ ℝ²) : ℕ :=
(P.filter (· ∈ L)).card
The number of lines that contain more than three points of P.
noncomputable def richLineCount (P : Finset ℝ²) : ℕ :=
{L : AffineSubspace ℝ ℝ² | IsLine L ∧ 3 < pointsOn P L}.ncard
P has $n$ points and at least $c n^2$ lines that each contain more than three points
of P.
def Admissible (c : ℝ) (n : ℕ) (P : Finset ℝ²) : Prop :=
P.card = n ∧ c * (n : ℝ) ^ 2 ≤ richLineCount P
The largest number of points of P on a single line.
noncomputable def maxCollinear (P : Finset ℝ²) : ℕ :=
sSup {k : ℕ | ∃ L, IsLine L ∧ pointsOn P L = k}
$h_c(n)$: the minimum of maxCollinear P over all admissible P. It is ⊤ when no
admissible configuration exists.
Two distinct lines share at most one pair of points, and a line with more than three points of
P contains at least $\binom{4}{2} = 6$ pairs. Hence richLineCount P $< n^2 / 12$, so for
$c \geq 1/12$ and $n \geq 1$ no configuration is admissible and $h_c(n) = \top$. The problem is
only meaningful for small $c > 0$; the statements below either quantify over all $c > 0$ (where
small $c$ govern the truth value) or restrict to sufficiently small $c$.
noncomputable def h (c : ℝ) (n : ℕ) : ℕ∞ :=
⨅ (P : Finset ℝ²) (_ : Admissible c n P), (maxCollinear P : ℕ∞)The plane contains a line.
⊢ Module.finrank ℝ ↥(ℝ ∙ EuclideanSpace.single 0 1) = 1
apply finrank_span_singleton ⊢ EuclideanSpace.single 0 1 ≠ 0
simp All goals completed! 🐙
M ≤ maxCollinear P exactly when some line contains at least M points of P.
@[category API, AMS 52]
theorem le_maxCollinear_iff (P : Finset ℝ²) (M : ℕ) :
M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L := by P:Finset ℝ²M:ℕ⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L
have hbdd : BddAbove {k : ℕ | ∃ L, IsLine L ∧ pointsOn P L = k} := by
refine ⟨P.card, ?_⟩ P:Finset ℝ²M:ℕ⊢ P.card ∈ upperBounds {k | ∃ L, IsLine L ∧ pointsOn P L = k} P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L
rintro k ⟨L, -, rfl⟩ P:Finset ℝ²M:ℕL:AffineSubspace ℝ ℝ²⊢ pointsOn P L ≤ P.card P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L
classical
exact Finset.card_filter_le _ _ P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L
have hne : {k : ℕ | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty := by
obtain ⟨L, hL⟩ := exists_line P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}L:AffineSubspace ℝ ℝ²hL:IsLine L⊢ {k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L
exact ⟨_, L, hL, rfl⟩ P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L
constructor mp P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty⊢ M ≤ maxCollinear P → ∃ L, IsLine L ∧ M ≤ pointsOn P Lmpr P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty⊢ (∃ L, IsLine L ∧ M ≤ pointsOn P L) → M ≤ maxCollinear P
· mp P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty⊢ M ≤ maxCollinear P → ∃ L, IsLine L ∧ M ≤ pointsOn P L intro hM mp P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.NonemptyhM:M ≤ maxCollinear P⊢ ∃ L, IsLine L ∧ M ≤ pointsOn P L
obtain ⟨L, hL, hk⟩ := Nat.sSup_mem hne hbdd mp P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.NonemptyhM:M ≤ maxCollinear PL:AffineSubspace ℝ ℝ²hL:IsLine Lhk:pointsOn P L = sSup {k | ∃ L, IsLine L ∧ pointsOn P L = k}⊢ ∃ L, IsLine L ∧ M ≤ pointsOn P L
exact ⟨L, hL, hk ▸ hM⟩ All goals completed! 🐙
· mpr P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.Nonempty⊢ (∃ L, IsLine L ∧ M ≤ pointsOn P L) → M ≤ maxCollinear P rintro ⟨L, hL, hM⟩ mpr P:Finset ℝ²M:ℕhbdd:BddAbove {k | ∃ L, IsLine L ∧ pointsOn P L = k}hne:{k | ∃ L, IsLine L ∧ pointsOn P L = k}.NonemptyL:AffineSubspace ℝ ℝ²hL:IsLine LhM:M ≤ pointsOn P L⊢ M ≤ maxCollinear P
exact hM.trans (le_csSup hbdd ⟨L, hL, rfl⟩) All goals completed! 🐙
M ≤ h c n exactly when every admissible configuration of $n$ points has a line that
contains at least M of its points.
@[category API, AMS 52]
theorem le_h_iff (c : ℝ) (n M : ℕ) :
(M : ℕ∞) ≤ h c n ↔
∀ P : Finset ℝ², Admissible c n P → ∃ L, IsLine L ∧ M ≤ pointsOn P L := by c:ℝn:ℕM:ℕ⊢ ↑M ≤ h c n ↔ ∀ (P : Finset ℝ²), Admissible c n P → ∃ L, IsLine L ∧ M ≤ pointsOn P L
simp only [h, le_iInf_iff, Nat.cast_le] c:ℝn:ℕM:ℕ⊢ (∀ (i : Finset ℝ²), Admissible c n i → M ≤ maxCollinear i) ↔
∀ (P : Finset ℝ²), Admissible c n P → ∃ L, IsLine L ∧ M ≤ pointsOn P L
refine forall_congr' fun P => imp_congr_right fun _ => ?_ c:ℝn:ℕM:ℕP:Finset ℝ²x✝:Admissible c n P⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L
exact le_maxCollinear_iff P M All goals completed! 🐙The statement $h_c(n) \to \infty$, written without $h_c$.
@[category API, AMS 52]
theorem tendsto_h_iff (c : ℝ) :
(∀ M : ℕ, ∀ᶠ n in atTop, (M : ℕ∞) ≤ h c n) ↔
∀ M : ℕ, ∀ᶠ n in atTop, ∀ P : Finset ℝ², P.card = n →
c * (n : ℝ) ^ 2 ≤ richLineCount P → ∃ L, IsLine L ∧ M ≤ pointsOn P L := by c:ℝ⊢ (∀ (M : ℕ), ∀ᶠ (n : ℕ) in atTop, ↑M ≤ h c n) ↔
∀ (M : ℕ),
∀ᶠ (n : ℕ) in atTop,
∀ (P : Finset ℝ²), P.card = n → c * ↑n ^ 2 ≤ ↑(richLineCount P) → ∃ L, IsLine L ∧ M ≤ pointsOn P L
refine forall_congr' fun M => eventually_congr (Eventually.of_forall fun n => ?_) c:ℝM:ℕn:ℕ⊢ ↑M ≤ h c n ↔ ∀ (P : Finset ℝ²), P.card = n → c * ↑n ^ 2 ≤ ↑(richLineCount P) → ∃ L, IsLine L ∧ M ≤ pointsOn P L
rw [le_h_iff c:ℝM:ℕn:ℕ⊢ (∀ (P : Finset ℝ²), Admissible c n P → ∃ L, IsLine L ∧ M ≤ pointsOn P L) ↔
∀ (P : Finset ℝ²), P.card = n → c * ↑n ^ 2 ≤ ↑(richLineCount P) → ∃ L, IsLine L ∧ M ≤ pointsOn P L c:ℝM:ℕn:ℕ⊢ (∀ (P : Finset ℝ²), Admissible c n P → ∃ L, IsLine L ∧ M ≤ pointsOn P L) ↔
∀ (P : Finset ℝ²), P.card = n → c * ↑n ^ 2 ≤ ↑(richLineCount P) → ∃ L, IsLine L ∧ M ≤ pointsOn P L] c:ℝM:ℕn:ℕ⊢ (∀ (P : Finset ℝ²), Admissible c n P → ∃ L, IsLine L ∧ M ≤ pointsOn P L) ↔
∀ (P : Finset ℝ²), P.card = n → c * ↑n ^ 2 ≤ ↑(richLineCount P) → ∃ L, IsLine L ∧ M ≤ pointsOn P L
exact forall_congr' fun P => ⟨fun hP hcard hrich => hP ⟨hcard, hrich⟩,
fun hP hadm => hP hadm.1 hadm.2⟩ All goals completed! 🐙Let $c > 0$ and let $h_c(n)$ be such that for any $n$ points in $\mathbb{R}^2$ with at least $cn^2$ lines that each contain more than three of the points, some line contains $h_c(n)$ of the points. Is it true that, for fixed $c > 0$, $h_c(n) \to \infty$?
@[category research open, question, AMS 52]
theorem erdos_102 :
∀ c > 0, ∀ M : ℕ, ∀ᶠ n in atTop, (M : ℕ∞) ≤ h c n := by ⊢ ∀ c > 0, ∀ (M : ℕ), ∀ᶠ (n : ℕ) in atTop, ↑M ≤ h c n
sorry All goals completed! 🐙It is not known whether $h_c(n) \geq 5$ for all sufficiently large $n$.
@[category research open, question, AMS 52]
theorem erdos_102.variants.five :
∀ c > 0, ∀ᶠ n in atTop, (5 : ℕ∞) ≤ h c n := by ⊢ ∀ c > 0, ∀ᶠ (n : ℕ) in atTop, 5 ≤ h c n
sorry All goals completed! 🐙It is easy to see that $h_c(n) \ll_c n^{1/2}$: for all sufficiently small $c > 0$ there are admissible configurations (e.g. grids) in which no line contains more than $C_c n^{1/2}$ points.
@[category research solved, AMS 52, formal_proof using lean4 at "https://github.com/anatoliiohorodnyk/lean-fc-proofs/blob/eee8e904a0eb8511302bc809b9486116ec079e69/Proofs/T_Erdos102_erdos_102_variants_upper_sqrt.lean#L1100"]
theorem erdos_102.variants.upper_sqrt :
∃ c₀ > (0 : ℝ), ∀ c ∈ Set.Ioc 0 c₀, ∃ C : ℝ, ∀ᶠ n in atTop,
h c n ≤ (⌈C * Real.sqrt n⌉₊ : ℕ∞) := by ⊢ ∃ c₀ > 0, ∀ c ∈ Set.Ioc 0 c₀, ∃ C, ∀ᶠ (n : ℕ) in atTop, h c n ≤ ↑⌈C * √↑n⌉₊
sorry All goals completed! 🐙Erdős [Er95] suggested that perhaps $h_c(n) \gg_c n^{1/2}$. Zach Hunter pointed out that this is false: the points of ${1, \dots, m}^d$ with $n \approx m^d$, randomly projected to $\mathbb{R}^2$, meet every line in $\ll_d n^{1/d}$ points and determine $\gg_d n^2$ lines with more than three points. This gives $h_c(n) \ll n^{1 / \log(1/c)}$; we state the underlying form: for every $d \geq 1$ there is $c > 0$ with $h_c(n) \ll_d n^{1/d}$.
@[category research solved, AMS 52, formal_proof using lean4 at "https://github.com/anatoliiohorodnyk/lean-fc-proofs/blob/eee8e904a0eb8511302bc809b9486116ec079e69/Proofs/T_Erdos102_erdos_102_variants_hunter.lean#L1113"]
theorem erdos_102.variants.hunter :
∀ d : ℕ, 1 ≤ d → ∃ c > (0 : ℝ), ∃ C : ℝ, ∀ᶠ n in atTop,
h c n ≤ (⌈C * (n : ℝ) ^ (1 / (d : ℝ))⌉₊ : ℕ∞) := by ⊢ ∀ (d : ℕ), 1 ≤ d → ∃ c > 0, ∃ C, ∀ᶠ (n : ℕ) in atTop, h c n ≤ ↑⌈C * ↑n ^ (1 / ↑d)⌉₊
sorry All goals completed! 🐙end Erdos102