/- 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 FormalConjecturesUtil

Erdő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 ⊢ EuclideanSpace.single 0 1 ≠ 0 All goals completed! 🐙

M ≤ maxCollinear P exactly when some line contains at least M points of P.

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 LP: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 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}.NonemptyhM: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}.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 All goals completed! 🐙 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 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 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 := c:ℝn:ℕM:ℕ⊢ ↑M ≤ h c n ↔ ∀ (P : Finset ℝ²), Admissible c n P → ∃ L, IsLine L ∧ M ≤ pointsOn P L 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 c:ℝn:ℕM:ℕP:Finset ℝ²x✝:Admissible c n P⊢ M ≤ maxCollinear P ↔ ∃ L, IsLine L ∧ M ≤ pointsOn P L All goals completed! 🐙

The statement $h_c(n) \to \infty$, written without $h_c$.

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 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 := ⊢ ∀ c > 0, ∀ (M : ℕ), ∀ᶠ (n : ℕ) in atTop, ↑M ≤ h c n 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 := ⊢ ∀ c > 0, ∀ᶠ (n : ℕ) in atTop, 5 ≤ h c n 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⌉₊ : ℕ∞) := ⊢ ∃ c₀ > 0, ∀ c ∈ Set.Ioc 0 c₀, ∃ C, ∀ᶠ (n : ℕ) in atTop, h c n ≤ ↑⌈C * √↑n⌉₊ 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 : ℝ))⌉₊ : ℕ∞) := ⊢ ∀ (d : ℕ), 1 ≤ d → ∃ c > 0, ∃ C, ∀ᶠ (n : ℕ) in atTop, h c n ≤ ↑⌈C * ↑n ^ (1 / ↑d)⌉₊ All goals completed! 🐙end Erdos102