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

References:

    erdosproblems.com/210

    [Mo51] Motzkin, T. S., The lines and planes connecting the points of a finite set. Transactions of the American Mathematical Society 70 (1951), 451–464.

    [KeMo58] Kelly, L. M. and Moser, W. O. J., On the number of ordinary lines determined by n points. Canadian Journal of Mathematics 10 (1958), 210–219.

    [CsSa93] Csima, J. and Sawyer, E. T., There exist 6n/13 ordinary points. Discrete & Computational Geometry 9 (1993), 187–202.

    [GrTa13] Green, B. and Tao, T., On sets defining few ordinary lines. Discrete & Computational Geometry 50 (2013), 409–468.

@[expose] public sectionnamespace Erdos210open EuclideanGeometry Filter

The sharp ordinary-line guarantee for noncollinear sets of $n$ points. For $n<3$, there are no such configurations, and the infimum is $0$.

noncomputable def f (n : ℕ) : ℕ := sInf {m : ℕ | ∃ s : Finset ℝ², s.card = n ∧ ¬ Collinear ℝ (s : Set ℝ²) ∧ (ordinaryLines s).card = m}

Let $f(n)$ be the sharp guarantee such that, for any $n$ points in $\mathbb R^2$, not all on a line, there are at least $f(n)$ lines which contain exactly two points (called ordinary lines). Does $f(n)\to\infty$? That $f(n)\to\infty$ was proved by Motzkin [Mo51].

@[category research solved, question, AMS 5 51] theorem erdos_210.parts.i : Tendsto f atTop atTop := ⊢ Tendsto f atTop atTop All goals completed! 🐙

Kelly and Moser [KeMo58] proved that $f(n)\geq 3n/7$ for all $n$. Only $n\geq3$ have noncollinear configurations.

@[category research solved, AMS 5 51] theorem erdos_210.lower_bound : ∀ n : ℕ, 3 ≤ n → 3 * n ≤ 7 * f n := ⊢ ∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n All goals completed! 🐙

Csima and Sawyer [CsSa93] proved $f(n)\geq6n/13$ when $n\geq8$.

@[category research solved, AMS 5 51] theorem erdos_210.variants.csima_sawyer : ∀ n : ℕ, 8 ≤ n → 6 * n ≤ 13 * f n := ⊢ ∀ (n : ℕ), 8 ≤ n → 6 * n ≤ 13 * f n All goals completed! 🐙

Green and Tao [GrTa13] proved $f(n)\geq n/2$ for sufficiently large $n$.

@[category research solved, AMS 5 51] theorem erdos_210.variants.green_tao : ∀ᶠ n : ℕ in atTop, n ≤ 2 * f n := ⊢ ∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n All goals completed! 🐙

Green and Tao [GrTa13] proved $f(n)\geq3\lfloor n/4\rfloor$ for sufficiently large odd $n$ [GrTa13, Theorem 2.2].

@[category research solved, AMS 5 51] theorem erdos_210.variants.green_tao_odd : ∀ᶠ n : ℕ in atTop, Odd n → 3 * (n / 4) ≤ f n := ⊢ ∀ᶠ (n : ℕ) in atTop, Odd n → 3 * (n / 4) ≤ f n All goals completed! 🐙

Green and Tao [GrTa13, Proposition 2.1] give configurations attaining $n/2$ ordinary lines for sufficiently large even $n$.

@[category research solved, AMS 5 51] theorem erdos_210.variants.even_upper_bound : ∀ᶠ n : ℕ in atTop, Even n → 2 * f n ≤ n := ⊢ ∀ᶠ (n : ℕ) in atTop, Even n → 2 * f n ≤ n All goals completed! 🐙

Kelly and Moser [KeMo58] give a seven-point configuration with three ordinary lines, attaining their lower bound at $n=7$.

@[category research solved, AMS 5 51] theorem erdos_210.variants.seven : f 7 = 3 := ⊢ f 7 = 3 All goals completed! 🐙

A configuration bounds the sharp guarantee from above.

@[category API, AMS 5 51] theorem f_le {n : ℕ} {s : Finset ℝ²} (hn : s.card = n) (hs : ¬ Collinear ℝ (s : Set ℝ²)) : f n ≤ (ordinaryLines s).card := csInf_le ⟨0, fun _ _ => Nat.zero_le _⟩ ⟨s, hn, hs, rfl⟩

A right triangle is noncollinear.

h:Collinear ℝ {!₂[0, 0], !₂[1, 0], !₂[0, 1]}heq:!₂[0, 0] ≠ !₂[1, 0]hm:!₂[0, 1] ∈ line[ℝ, !₂[0, 0], !₂[1, 0]]⊢ False h:Collinear ℝ {!₂[0, 0], !₂[1, 0], !₂[0, 1]}heq:!₂[0, 0] ≠ !₂[1, 0]hm:!₂[0, 1] ∈ line[ℝ, !₂[0, 0], !₂[1, 0]]t:ℝht:(AffineMap.lineMap !₂[0, 0] !₂[1, 0]) t = !₂[0, 1]⊢ False h:Collinear ℝ {!₂[0, 0], !₂[1, 0], !₂[0, 1]}heq:!₂[0, 0] ≠ !₂[1, 0]hm:!₂[0, 1] ∈ line[ℝ, !₂[0, 0], !₂[1, 0]]t:ℝht:(AffineMap.lineMap !₂[0, 0] !₂[1, 0]) t = !₂[0, 1]this:((AffineMap.lineMap !₂[0, 0] !₂[1, 0]) t).ofLp 1 = !₂[0, 1].ofLp 1⊢ False All goals completed! 🐙

Every cardinality at least three has a noncollinear configuration.

n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}ht:t.card ≤ n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}ht:t.card ≤ ns:Finset ℝ²hts:t ⊆ shsn:s.card = n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}ht:t.card ≤ ns:Finset ℝ²hts:t ⊆ shsn:s.card = nhs:Collinear ℝ ↑s⊢ {!₂[0, 0], !₂[1, 0], !₂[0, 1]} ⊆ ↑s n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}ht:t.card ≤ ns:Finset ℝ²hts:t ⊆ shsn:s.card = nhs:Collinear ℝ ↑sp:ℝ²hp:p ∈ {!₂[0, 0], !₂[1, 0], !₂[0, 1]}⊢ p ∈ ↑s n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}ht:t.card ≤ ns:Finset ℝ²hts:t ⊆ shsn:s.card = nhs:Collinear ℝ ↑sp:ℝ²hp:p ∈ {!₂[0, 0], !₂[1, 0], !₂[0, 1]}⊢ p ∈ t All goals completed! 🐙

The infimum defining $f(n)$ is attained when $n\geq3$.

@[category API, AMS 5 51] theorem f_attained {n : ℕ} (hn : 3 ≤ n) : ∃ s : Finset ℝ², s.card = n ∧ ¬ Collinear ℝ (s : Set ℝ²) ∧ (ordinaryLines s).card = f n := n:ℕhn:3 ≤ n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = f n n:ℕhn:3 ≤ ns:Finset ℝ²hs:s.card = nhcol:¬Collinear ℝ ↑s⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = f n n:ℕhn:3 ≤ ns:Finset ℝ²hs:s.card = nhcol:¬Collinear ℝ ↑s⊢ {m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m}.Nonempty All goals completed! 🐙

The infimum is exactly the largest uniform lower bound over all configurations.

@[category API, AMS 5 51] theorem le_f_iff {n m : ℕ} (hn : 3 ≤ n) : m ≤ f n ↔ ∀ s : Finset ℝ², s.card = n → ¬ Collinear ℝ (s : Set ℝ²) → m ≤ (ordinaryLines s).card := n:ℕm:ℕhn:3 ≤ n⊢ m ≤ f n ↔ ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card n:ℕm:ℕhn:3 ≤ n⊢ m ≤ f n → ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).cardn:ℕm:ℕhn:3 ≤ n⊢ (∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card) → m ≤ f n n:ℕm:ℕhn:3 ≤ n⊢ m ≤ f n → ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card All goals completed! 🐙 n:ℕm:ℕhn:3 ≤ n⊢ (∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card) → m ≤ f n n:ℕm:ℕhn:3 ≤ nh:∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card⊢ m ≤ f n n:ℕm:ℕhn:3 ≤ nh:∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).cards:Finset ℝ²hs:s.card = nhc:¬Collinear ℝ ↑shcard:(ordinaryLines s).card = f n⊢ m ≤ f n All goals completed! 🐙

The Sylvester–Gallai theorem states that $f(n)\geq1$.

@[category research solved, AMS 5 51] theorem erdos_210.variants.sylvester_gallai {n : ℕ} (hn : 3 ≤ n) : 1 ≤ f n := n:ℕhn:3 ≤ n⊢ 1 ≤ f n n:ℕhn:3 ≤ n⊢ ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → 1 ≤ (ordinaryLines s).card n:ℕhn:3 ≤ ns:Finset ℝ²a✝:s.card = nhs:¬Collinear ℝ ↑s⊢ 1 ≤ (ordinaryLines s).card All goals completed! 🐙

The bound of Kelly–Moser implies the positive answer to the divergence question.

@[category API, AMS 5 51] theorem tendsto_of_kelly_moser (h : ∀ n : ℕ, 3 ≤ n → 3 * n ≤ 7 * f n) : Tendsto f atTop atTop := h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ Tendsto f atTop atTop h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ ∀ (b : ℕ), ∀ᶠ (a : ℕ) in atTop, b ≤ f a h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nm:ℕ⊢ ∀ᶠ (a : ℕ) in atTop, m ≤ f a filter_upwards [eventually_ge_atTop (max 3 (7 * m))] with n h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nm:ℕn:ℕhn:max 3 (7 * m) ≤ n⊢ m ≤ f n h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nm:ℕn:ℕhn:max 3 (7 * m) ≤ nhbound:3 * n ≤ 7 * f n⊢ m ≤ f n h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nm:ℕn:ℕhn:max 3 (7 * m) ≤ nhbound:3 * n ≤ 7 * f nhn':7 * m ≤ n⊢ m ≤ f n All goals completed! 🐙

The sufficiently-large $n/2$ bound implies divergence.

@[category API, AMS 5 51] theorem tendsto_of_green_tao (h : ∀ᶠ n : ℕ in atTop, n ≤ 2 * f n) : Tendsto f atTop atTop := h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ Tendsto f atTop atTop h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ ∀ (b : ℕ), ∀ᶠ (a : ℕ) in atTop, b ≤ f a h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nm:ℕ⊢ ∀ᶠ (a : ℕ) in atTop, m ≤ f a filter_upwards [h, eventually_ge_atTop (2 * m)] with n h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nm:ℕn:ℕhn:n ≤ 2 * f n⊢ 2 * m ≤ n → m ≤ f n h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nm:ℕn:ℕhn:n ≤ 2 * f nhm:2 * m ≤ n⊢ m ≤ f n All goals completed! 🐙

Points used for a configuration with all but one point on a single line.

def axisPoint (i : ℕ) : ℝ² := !2[(i : ℝ), 0]

The point off that line.

def apex : ℝ² := !2[(0 : ℝ), 1]

The near-pencil configuration consists of $n-1$ points on the horizontal axis and an apex.

noncomputable def nearPencil (n : ℕ) : Finset ℝ² := n:ℕ⊢ Finset ℝ² classical All goals completed! 🐙

Distinct indices give distinct axis points.

@[category API, AMS 5 51] theorem axisPoint_injective : Function.Injective axisPoint := ⊢ Function.Injective axisPoint i:ℕj:ℕh:axisPoint i = axisPoint j⊢ i = j i:ℕj:ℕh:axisPoint i = axisPoint jthis:(axisPoint i).ofLp 0 = (axisPoint j).ofLp 0⊢ i = j All goals completed! 🐙

The apex is distinct from every axis point.

@[category API, AMS 5 51] theorem apex_ne_axisPoint (i : ℕ) : apex ≠ axisPoint i := i:ℕ⊢ apex ≠ axisPoint i i:ℕh:apex = axisPoint i⊢ False i:ℕh:apex = axisPoint ithis:apex.ofLp 1 = (axisPoint i).ofLp 1⊢ False All goals completed! 🐙

Each axis point is on the horizontal line.

@[category API, AMS 5 51] theorem axisPoint_mem (i : ℕ) : axisPoint i ∈ line[ℝ, axisPoint 0, axisPoint 1] := i:ℕ⊢ axisPoint i ∈ line[ℝ, axisPoint 0, axisPoint 1] i:ℕ⊢ ∃ r, (AffineMap.lineMap (axisPoint 0) (axisPoint 1)) r = axisPoint i i:ℕ⊢ (AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i = axisPoint i i:ℕj:Fin 2⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp j = (axisPoint i).ofLp j i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩)i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩)i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) All goals completed! 🐙

The near-pencil construction has the requested cardinality.

n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ n - 1 + 1 = n All goals completed! 🐙

For $n\geq3$, the near-pencil construction contains a noncollinear triangle.

n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)p:ℝ²hp:p = !₂[0, 0] ∨ p = !₂[1, 0] ∨ p = !₂[0, 1]haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ p ∈ ↑(nearPencil n) n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 0] ∈ ↑(nearPencil n)n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[1, 0] ∈ ↑(nearPencil n)n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 1] ∈ ↑(nearPencil n) n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 0] ∈ ↑(nearPencil n) simpa [axisPoint] using haxis 0 (n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ 0 < n - 1 All goals completed! 🐙) n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[1, 0] ∈ ↑(nearPencil n) simpa [axisPoint] using haxis 1 (n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ 1 < n - 1 All goals completed! 🐙) n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 1] ∈ ↑(nearPencil n) n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ apex ∈ nearPencil n All goals completed! 🐙open scoped Classical in

Every ordinary line of a near-pencil is either horizontal or joins an axis point to the apex.

@[category API, AMS 5 51] theorem ordinaryLines_nearPencil_subset (n : ℕ) : ordinaryLines (nearPencil n) ⊆ insert (line[ℝ, axisPoint 0, axisPoint 1]) (((Finset.range (n - 1)).image axisPoint).image fun p => line[ℝ, apex, p]) := n:ℕ⊢ ordinaryLines (nearPencil n) ⊆ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕL:AffineSubspace ℝ ℝ²hL:L ∈ ordinaryLines (nearPencil n)⊢ L ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕa:ℝ²ha:a ∈ nearPencil nb:ℝ²hb:b ∈ nearPencil nhab:a ≠ bhL:line[ℝ, a, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, b]}.card = 2⊢ line[ℝ, a, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕa:ℝ²b:ℝ²hab:a ≠ bhL:line[ℝ, a, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, b]}.card = 2ha:a = apex ∨ a ∈ Finset.image axisPoint (Finset.range (n - 1))hb:b = apex ∨ b ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, a, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕb:ℝ²hb:b = apex ∨ b ∈ Finset.image axisPoint (Finset.range (n - 1))hab:apex ≠ bhL:line[ℝ, apex, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, apex, b]}.card = 2⊢ line[ℝ, apex, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1))))n:ℕa:ℝ²b:ℝ²hab:a ≠ bhL:line[ℝ, a, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, b]}.card = 2hb:b = apex ∨ b ∈ Finset.image axisPoint (Finset.range (n - 1))ha:a ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, a, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕb:ℝ²hb:b = apex ∨ b ∈ Finset.image axisPoint (Finset.range (n - 1))hab:apex ≠ bhL:line[ℝ, apex, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, apex, b]}.card = 2⊢ line[ℝ, apex, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕhab:apex ≠ apexhL:line[ℝ, apex, apex] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, apex, apex]}.card = 2⊢ line[ℝ, apex, apex] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1))))n:ℕb:ℝ²hab:apex ≠ bhL:line[ℝ, apex, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, apex, b]}.card = 2hb:b ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, apex, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕhab:apex ≠ apexhL:line[ℝ, apex, apex] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, apex, apex]}.card = 2⊢ line[ℝ, apex, apex] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) All goals completed! 🐙 n:ℕb:ℝ²hab:apex ≠ bhL:line[ℝ, apex, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, apex, b]}.card = 2hb:b ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, apex, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) All goals completed! 🐙 n:ℕa:ℝ²b:ℝ²hab:a ≠ bhL:line[ℝ, a, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, b]}.card = 2hb:b = apex ∨ b ∈ Finset.image axisPoint (Finset.range (n - 1))ha:a ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, a, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕa:ℝ²ha:a ∈ Finset.image axisPoint (Finset.range (n - 1))hab:a ≠ apexhL:line[ℝ, a, apex] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, apex]}.card = 2⊢ line[ℝ, a, apex] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1))))n:ℕa:ℝ²b:ℝ²hab:a ≠ bhL:line[ℝ, a, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, b]}.card = 2ha:a ∈ Finset.image axisPoint (Finset.range (n - 1))hb:b ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, a, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕa:ℝ²ha:a ∈ Finset.image axisPoint (Finset.range (n - 1))hab:a ≠ apexhL:line[ℝ, a, apex] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, apex]}.card = 2⊢ line[ℝ, a, apex] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) All goals completed! 🐙 n:ℕa:ℝ²b:ℝ²hab:a ≠ bhL:line[ℝ, a, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, a, b]}.card = 2ha:a ∈ Finset.image axisPoint (Finset.range (n - 1))hb:b ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, a, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕb:ℝ²hb:b ∈ Finset.image axisPoint (Finset.range (n - 1))i:ℕleft✝:i ∈ Finset.range (n - 1)hab:axisPoint i ≠ bhL:line[ℝ, axisPoint i, b] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, axisPoint i, b]}.card = 2ha:axisPoint i ∈ Finset.image axisPoint (Finset.range (n - 1))⊢ line[ℝ, axisPoint i, b] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕi:ℕleft✝¹:i ∈ Finset.range (n - 1)ha:axisPoint i ∈ Finset.image axisPoint (Finset.range (n - 1))j:ℕleft✝:j ∈ Finset.range (n - 1)hb:axisPoint j ∈ Finset.image axisPoint (Finset.range (n - 1))hab:axisPoint i ≠ axisPoint jhL:line[ℝ, axisPoint i, axisPoint j] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, axisPoint i, axisPoint j]}.card = 2⊢ line[ℝ, axisPoint i, axisPoint j] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) n:ℕi:ℕleft✝¹:i ∈ Finset.range (n - 1)ha:axisPoint i ∈ Finset.image axisPoint (Finset.range (n - 1))j:ℕleft✝:j ∈ Finset.range (n - 1)hb:axisPoint j ∈ Finset.image axisPoint (Finset.range (n - 1))hab:axisPoint i ≠ axisPoint jhL:line[ℝ, axisPoint i, axisPoint j] ∈ ordinaryLines (nearPencil n)right✝:{p ∈ nearPencil n | p ∈ line[ℝ, axisPoint i, axisPoint j]}.card = 2heq:line[ℝ, axisPoint i, axisPoint j] = line[ℝ, axisPoint 0, axisPoint 1]⊢ line[ℝ, axisPoint i, axisPoint j] ∈ insert line[ℝ, axisPoint 0, axisPoint 1] (Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1)))) All goals completed! 🐙

The near-pencil construction has at most $n$ ordinary lines.

n:ℕhn:1 ≤ n⊢ n - 1 + 1 = n; All goals completed! 🐙

An explicit near-pencil gives the linear upper bound $f(n)\leq n$.

@[category research solved, AMS 5 51] theorem erdos_210.upper_bound {n : ℕ} (hn : 3 ≤ n) : f n ≤ n := (f_le (nearPencil_card (n:ℕhn:3 ≤ n⊢ 1 ≤ n All goals completed! 🐙)) (nearPencil_not_collinear hn)).trans (ordinaryLines_nearPencil_le (n:ℕhn:3 ≤ n⊢ 1 ≤ n All goals completed! 🐙))

How fast does $f(n)$ tend to infinity? Kelly–Moser [KeMo58] and the near-pencil construction show that its growth is linear.

@[category research solved, AMS 5 51] theorem erdos_210.parts.ii : (fun n : ℕ => (f n : ℝ)) =Θ[atTop] (fun n : ℕ => (n : ℝ)) := ⊢ (fun n ↦ ↑(f n)) =Θ[atTop] fun n ↦ ↑n All goals completed! 🐙

The proved upper bound is the upper half of the linear-growth assertion.

@[category API, AMS 5 51] theorem f_isBigO : (fun n : ℕ => (f n : ℝ)) =O[atTop] (fun n : ℕ => (n : ℝ)) := ⊢ (fun n ↦ ↑(f n)) =O[atTop] fun n ↦ ↑n ⊢ ∀ᶠ (x : ℕ) in atTop, ‖↑(f x)‖ ≤ 1 * ‖↑x‖ filter_upwards [eventually_ge_atTop 3] with n n:ℕhn:3 ≤ n⊢ ‖↑(f n)‖ ≤ 1 * ‖↑n‖ All goals completed! 🐙

Kelly–Moser and the explicit upper construction together imply linear growth.

h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nn:ℕhn:3 ≤ nhb:3 * n ≤ 7 * f nhb':n ≤ 7 * f nhr:↑n ≤ 7 * ↑(f n)⊢ ‖↑n‖ ≤ 7 * ‖↑(f n)‖ All goals completed! 🐙

The Green–Tao bound likewise implies linear growth.

h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nn:ℕhn:n ≤ 2 * f nhr:↑n ≤ 2 * ↑(f n)⊢ ‖↑n‖ ≤ 2 * ‖↑(f n)‖ All goals completed! 🐙

Fewer than three points are collinear.

s:Finset ℝ²hs:s.card < 3hc:s.card = 0 ∨ s.card = 1 ∨ s.card = 2⊢ Collinear ℝ ↑s s:Finset ℝ²hs:s.card < 3hc:s.card = 0⊢ Collinear ℝ ↑ss:Finset ℝ²hs:s.card < 3hc:s.card = 1⊢ Collinear ℝ ↑ss:Finset ℝ²hs:s.card < 3hc:s.card = 2⊢ Collinear ℝ ↑s s:Finset ℝ²hs:s.card < 3hc:s.card = 0⊢ Collinear ℝ ↑s s:Finset ℝ²hs:s.card < 3hc:s.card = 0he:s = ∅⊢ Collinear ℝ ↑s All goals completed! 🐙 s:Finset ℝ²hs:s.card < 3hc:s.card = 1⊢ Collinear ℝ ↑s a:ℝ²hs:{a}.card < 3hc:{a}.card = 1⊢ Collinear ℝ ↑{a} All goals completed! 🐙 s:Finset ℝ²hs:s.card < 3hc:s.card = 2⊢ Collinear ℝ ↑s a:ℝ²b:ℝ²left✝:a ≠ bhs:{a, b}.card < 3hc:{a, b}.card = 2⊢ Collinear ℝ ↑{a, b} All goals completed! 🐙

The definition uses the default value zero where no noncollinear configuration exists.

n:ℕhn:n < 3he:{m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m} = ∅⊢ f n = 0 All goals completed! 🐙

Kelly–Moser's extremal-function formulation is equivalent to its configuration formulation.

h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f ns:Finset ℝ²hs:¬Collinear ℝ ↑shn:3 ≤ s.card⊢ 3 * s.card ≤ 7 * (ordinaryLines s).card All goals completed! 🐙 ⊢ (∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).card) → ∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n h:∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).cardn:ℕhn:3 ≤ n⊢ 3 * n ≤ 7 * f n h:∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).cardn:ℕhn:3 ≤ ns:Finset ℝ²hs:s.card = nhc:¬Collinear ℝ ↑shf:(ordinaryLines s).card = f n⊢ 3 * n ≤ 7 * f n All goals completed! 🐙

The eventual Green–Tao bound has a single threshold uniform over all configurations.

@[category API, AMS 5 51] theorem green_tao_iff : (∀ᶠ n : ℕ in atTop, n ≤ 2 * f n) ↔ ∃ N : ℕ, 3 ≤ N ∧ ∀ s : Finset ℝ², N ≤ s.card → ¬ Collinear ℝ (s : Set ℝ²) → s.card ≤ 2 * (ordinaryLines s).card := ⊢ (∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n) ↔ ∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card ⊢ (∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n) → ∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card⊢ (∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card) → ∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n ⊢ (∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n) → ∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ ∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nN:ℕhN:∀ (b : ℕ), N ≤ b → b ≤ 2 * f b⊢ ∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nN:ℕhN:∀ (b : ℕ), N ≤ b → b ≤ 2 * f b⊢ ∀ (s : Finset ℝ²), max 3 N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nN:ℕhN:∀ (b : ℕ), N ≤ b → b ≤ 2 * f bs:Finset ℝ²hs:max 3 N ≤ s.cardhc:¬Collinear ℝ ↑s⊢ s.card ≤ 2 * (ordinaryLines s).card All goals completed! 🐙 ⊢ (∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card) → ∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card⊢ ∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card⊢ ∃ a, ∀ (b : ℕ), a ≤ b → b ≤ 2 * f b N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card⊢ ∀ (b : ℕ), N ≤ b → b ≤ 2 * f b N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).cardn:ℕhn:N ≤ n⊢ n ≤ 2 * f n N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).cardn:ℕhn:N ≤ ns:Finset ℝ²hs:s.card = nhc:¬Collinear ℝ ↑shf:(ordinaryLines s).card = f n⊢ n ≤ 2 * f n simpa [hs, hf] using h s (N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).cardn:ℕhn:N ≤ ns:Finset ℝ²hs:s.card = nhc:¬Collinear ℝ ↑shf:(ordinaryLines s).card = f n⊢ N ≤ s.card All goals completed! 🐙) hc

A sharp extremal guarantee is uniquely characterized by uniform validity and attainment.

@[category API, AMS 5 51] theorem f_unique {n m : ℕ} (hn : 3 ≤ n) (hlower : ∀ s : Finset ℝ², s.card = n → ¬ Collinear ℝ (s : Set ℝ²) → m ≤ (ordinaryLines s).card) (hattain : ∃ s : Finset ℝ², s.card = n ∧ ¬ Collinear ℝ (s : Set ℝ²) ∧ (ordinaryLines s).card = m) : m = f n := n:ℕm:ℕhn:3 ≤ nhlower:∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).cardhattain:∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m⊢ m = f n n:ℕm:ℕhn:3 ≤ nhlower:∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).cardhattain:∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m⊢ f n ≤ m n:ℕm:ℕhn:3 ≤ nhlower:∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).cards:Finset ℝ²hs:s.card = nhc:¬Collinear ℝ ↑shm:(ordinaryLines s).card = m⊢ f n ≤ m All goals completed! 🐙

The two sharp eventual bounds imply the exact value on sufficiently large even inputs.

@[category API, AMS 5 51] theorem eventually_even_exact (hl : ∀ᶠ n : ℕ in atTop, n ≤ 2 * f n) (hu : ∀ᶠ n : ℕ in atTop, Even n → 2 * f n ≤ n) : ∀ᶠ n : ℕ in atTop, Even n → 2 * f n = n := hl:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nhu:∀ᶠ (n : ℕ) in atTop, Even n → 2 * f n ≤ n⊢ ∀ᶠ (n : ℕ) in atTop, Even n → 2 * f n = n filter_upwards [hl, hu] with n hl✝:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nhu:∀ᶠ (n : ℕ) in atTop, Even n → 2 * f n ≤ nn:ℕhl:n ≤ 2 * f n⊢ (Even n → 2 * f n ≤ n) → Even n → 2 * f n = n hl✝:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nhu✝:∀ᶠ (n : ℕ) in atTop, Even n → 2 * f n ≤ nn:ℕhl:n ≤ 2 * f nhu:Even n → 2 * f n ≤ n⊢ Even n → 2 * f n = n hl✝:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nhu✝:∀ᶠ (n : ℕ) in atTop, Even n → 2 * f n ≤ nn:ℕhl:n ≤ 2 * f nhu:Even n → 2 * f n ≤ nhn:Even n⊢ 2 * f n = n All goals completed! 🐙end Erdos210