/-
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 210
References:
[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 FilterThe 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
obtain ⟨t, ht⟩ := mem_affineSpan_pair_iff_exists_lineMap_eq.mp hm 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
have := congrArg (fun p : ℝ² => p 1) ht 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
norm_num [AffineMap.lineMap_apply] at this All goals completed! 🐙Every cardinality at least three has a noncollinear configuration.
@[category API, AMS 5 51]
theorem exists_configuration {n : ℕ} (hn : 3 ≤ n) :
∃ s : Finset ℝ², s.card = n ∧ ¬ Collinear ℝ (s : Set ℝ²) := by n:ℕhn:3 ≤ n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s
classical
let t : Finset ℝ² := {!2[(0 : ℝ), 0], !2[(1 : ℝ), 0], !2[(0 : ℝ), 1]} n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s
have ht : t.card ≤ n := by n:ℕhn:3 ≤ n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}ht:t.card ≤ n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s
calc
t.card ≤ 3 := Finset.card_le_three
_ ≤ n := hn n:ℕhn:3 ≤ nt:Finset ℝ² := {!₂[0, 0], !₂[1, 0], !₂[0, 1]}ht:t.card ≤ n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s
obtain ⟨s, hts, hsn⟩ := Infinite.exists_superset_card_eq t n ht 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
refine ⟨s, hsn, fun hs => triangle_not_collinear (hs.subset ?_)⟩ 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
intro p hp 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
apply hts 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
simpa [t] using hp 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 := by n:ℕhn:3 ≤ n⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = f n
obtain ⟨s, hs, hcol⟩ := exists_configuration hn n:ℕhn:3 ≤ ns:Finset ℝ²hs:s.card = nhcol:¬Collinear ℝ ↑s⊢ ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = f n
apply csInf_mem (s := {m : ℕ | ∃ s : Finset ℝ²,
s.card = n ∧ ¬ Collinear ℝ (s : Set ℝ²) ∧ (ordinaryLines s).card = m}) n:ℕhn:3 ≤ ns:Finset ℝ²hs:s.card = nhcol:¬Collinear ℝ ↑s⊢ {m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m}.Nonempty
exact ⟨(ordinaryLines s).card, s, hs, hcol, rfl⟩ 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 := by n:ℕm:ℕhn:3 ≤ n⊢ m ≤ f n ↔ ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card
constructor mp n:ℕm:ℕhn:3 ≤ n⊢ m ≤ f n → ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).cardmpr n:ℕm:ℕhn:3 ≤ n⊢ (∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card) → m ≤ f n
· mp n:ℕm:ℕhn:3 ≤ n⊢ m ≤ f n → ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card exact fun h s hs hc => h.trans (f_le hs hc) All goals completed! 🐙
· mpr n:ℕm:ℕhn:3 ≤ n⊢ (∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card) → m ≤ f n intro h mpr n:ℕm:ℕhn:3 ≤ nh:∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → m ≤ (ordinaryLines s).card⊢ m ≤ f n
obtain ⟨s, hs, hc, hcard⟩ := f_attained hn mpr 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
simpa [hcard] using h s hs hc 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 := by n:ℕhn:3 ≤ n⊢ 1 ≤ f n
apply (le_f_iff hn).mpr n:ℕhn:3 ≤ n⊢ ∀ (s : Finset ℝ²), s.card = n → ¬Collinear ℝ ↑s → 1 ≤ (ordinaryLines s).card
intro s _ hs n:ℕhn:3 ≤ ns:Finset ℝ²a✝:s.card = nhs:¬Collinear ℝ ↑s⊢ 1 ≤ (ordinaryLines s).card
exact (ordinaryLines_nonempty hs).card_pos 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 := by h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ Tendsto f atTop atTop
apply tendsto_atTop.mpr h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ ∀ (b : ℕ), ∀ᶠ (a : ℕ) in atTop, b ≤ f a
intro m 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 hn h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nm:ℕn:ℕhn:max 3 (7 * m) ≤ n⊢ m ≤ f n
have hbound := h n (le_trans (le_max_left _ _) hn) h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nm:ℕn:ℕhn:max 3 (7 * m) ≤ nhbound:3 * n ≤ 7 * f n⊢ m ≤ f n
have hn' := le_trans (le_max_right _ _) hn 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
omega 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 := by h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ Tendsto f atTop atTop
apply tendsto_atTop.mpr h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ ∀ (b : ℕ), ∀ᶠ (a : ℕ) in atTop, b ≤ f a
intro m h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nm:ℕ⊢ ∀ᶠ (a : ℕ) in atTop, m ≤ f a
filter_upwards [h, eventually_ge_atTop (2 * m)] with n hn h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nm:ℕn:ℕhn:n ≤ 2 * f n⊢ 2 * m ≤ n → m ≤ f n hm h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nm:ℕn:ℕhn:n ≤ 2 * f nhm:2 * m ≤ n⊢ m ≤ f n
omega 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 ℝ² := by n:ℕ⊢ Finset ℝ²
classical
exact insert apex ((Finset.range (n - 1)).image axisPoint) All goals completed! 🐙Distinct indices give distinct axis points.
@[category API, AMS 5 51]
theorem axisPoint_injective : Function.Injective axisPoint := by ⊢ Function.Injective axisPoint
intro i j h i:ℕj:ℕh:axisPoint i = axisPoint j⊢ i = j
have := congrArg (fun p : ℝ² => p 0) h i:ℕj:ℕh:axisPoint i = axisPoint jthis:(axisPoint i).ofLp 0 = (axisPoint j).ofLp 0⊢ i = j
simpa [axisPoint] using this All goals completed! 🐙The apex is distinct from every axis point.
@[category API, AMS 5 51]
theorem apex_ne_axisPoint (i : ℕ) : apex ≠ axisPoint i := by i:ℕ⊢ apex ≠ axisPoint i
intro h i:ℕh:apex = axisPoint i⊢ False
have := congrArg (fun p : ℝ² => p 1) h i:ℕh:apex = axisPoint ithis:apex.ofLp 1 = (axisPoint i).ofLp 1⊢ False
norm_num [apex, axisPoint] at this 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] := by i:ℕ⊢ axisPoint i ∈ line[ℝ, axisPoint 0, axisPoint 1]
apply mem_affineSpan_pair_iff_exists_lineMap_eq.mpr i:ℕ⊢ ∃ r, (AffineMap.lineMap (axisPoint 0) (axisPoint 1)) r = axisPoint i
refine ⟨(i : ℝ), ?_⟩ i:ℕ⊢ (AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i = axisPoint i
ext j i:ℕj:Fin 2⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp j = (axisPoint i).ofLp j
fin_cases j «0» i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩)«1» i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) <;> «0» i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨0, ⋯⟩)«1» i:ℕ⊢ ((AffineMap.lineMap (axisPoint 0) (axisPoint 1)) ↑i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) = (axisPoint i).ofLp ((fun i ↦ i) ⟨1, ⋯⟩) simp [axisPoint, AffineMap.lineMap_apply] All goals completed! 🐙The near-pencil construction has the requested cardinality.
@[category API, AMS 5 51]
theorem nearPencil_card {n : ℕ} (hn : 1 ≤ n) : (nearPencil n).card = n := by n:ℕhn:1 ≤ n⊢ (nearPencil n).card = n
classical
have hap : apex ∉ (Finset.range (n - 1)).image axisPoint := by
simp only [Finset.mem_image] n:ℕhn:1 ≤ n⊢ ¬∃ a ∈ Finset.range (n - 1), axisPoint a = apex n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ (nearPencil n).card = n
rintro ⟨i, _, hi⟩ n:ℕhn:1 ≤ ni:ℕleft✝:i ∈ Finset.range (n - 1)hi:axisPoint i = apex⊢ False n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ (nearPencil n).card = n
exact apex_ne_axisPoint i hi.symm n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ (nearPencil n).card = n n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ (nearPencil n).card = n
rw [nearPencil, n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ (insert apex (Finset.image axisPoint (Finset.range (n - 1)))).card = n n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ n - 1 + 1 = n Finset.card_insert_of_notMem hap, n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ (Finset.image axisPoint (Finset.range (n - 1))).card + 1 = n n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ n - 1 + 1 = n Finset.card_image_of_injective _
axisPoint_injective, n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ (Finset.range (n - 1)).card + 1 = n n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ n - 1 + 1 = n Finset.card_range n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ n - 1 + 1 = n n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ n - 1 + 1 = n] n:ℕhn:1 ≤ nhap:apex ∉ Finset.image axisPoint (Finset.range (n - 1))⊢ n - 1 + 1 = n
omega All goals completed! 🐙For $n\geq3$, the near-pencil construction contains a noncollinear triangle.
@[category API, AMS 5 51]
theorem nearPencil_not_collinear {n : ℕ} (hn : 3 ≤ n) :
¬ Collinear ℝ (nearPencil n : Set ℝ²) := by n:ℕhn:3 ≤ n⊢ ¬Collinear ℝ ↑(nearPencil n)
classical
intro h n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)⊢ False
apply triangle_not_collinear n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)⊢ Collinear ℝ {!₂[0, 0], !₂[1, 0], !₂[0, 1]}
apply h.subset n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)⊢ {!₂[0, 0], !₂[1, 0], !₂[0, 1]} ⊆ ↑(nearPencil n)
intro p hp n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)p:ℝ²hp:p ∈ {!₂[0, 0], !₂[1, 0], !₂[0, 1]}⊢ p ∈ ↑(nearPencil n)
simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hp n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)p:ℝ²hp:p = !₂[0, 0] ∨ p = !₂[1, 0] ∨ p = !₂[0, 1]⊢ p ∈ ↑(nearPencil n)
have haxis (i : ℕ) (hi : i < n - 1) : axisPoint i ∈ nearPencil n := by n:ℕhn:3 ≤ n⊢ ¬Collinear ℝ ↑(nearPencil n) 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)
simp only [nearPencil, Finset.mem_insert, Finset.mem_image] n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)p:ℝ²hp:p = !₂[0, 0] ∨ p = !₂[1, 0] ∨ p = !₂[0, 1]i:ℕhi:i < n - 1⊢ axisPoint i = apex ∨ ∃ a ∈ Finset.range (n - 1), axisPoint a = axisPoint i 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)
exact Or.inr ⟨i, Finset.mem_range.mpr hi, rfl⟩ 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)p:ℝ²hp:p = !₂[0, 0] ∨ p = !₂[1, 0] ∨ p = !₂[0, 1]haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ p ∈ ↑(nearPencil n)
rcases hp with rfl | rfl | rfl inl n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 0] ∈ ↑(nearPencil n)inr.inl n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[1, 0] ∈ ↑(nearPencil n)inr.inr n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 1] ∈ ↑(nearPencil n)
· inl n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 0] ∈ ↑(nearPencil n) simpa [axisPoint] using haxis 0 (by n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ 0 < n - 1 omega All goals completed! 🐙)
· inr.inl n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[1, 0] ∈ ↑(nearPencil n) simpa [axisPoint] using haxis 1 (by n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ 1 < n - 1 omega All goals completed! 🐙)
· inr.inr n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ !₂[0, 1] ∈ ↑(nearPencil n) change apex ∈ nearPencil n inr.inr n:ℕhn:3 ≤ nh:Collinear ℝ ↑(nearPencil n)haxis:∀ i < n - 1, axisPoint i ∈ nearPencil n⊢ apex ∈ nearPencil n
simp [nearPencil] All goals completed! 🐙open scoped Classical inEvery 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]) := by n:ℕ⊢ ordinaryLines (nearPencil n) ⊆
insert line[ℝ, axisPoint 0, axisPoint 1]
(Finset.image (fun p ↦ line[ℝ, apex, p]) (Finset.image axisPoint (Finset.range (n - 1))))
intro L hL 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))))
obtain ⟨⟨a, ha, b, hb, hab, rfl⟩, _⟩ := mem_ordinaryLines.mp hL 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))))
simp only [nearPencil, Finset.mem_insert] at ha hb 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))))
rcases ha with rfl | ha inl 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))))inr 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))))
· inl 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)))) rcases hb with rfl | hb inl.inl 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))))inl.inr 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))))
· inl.inl 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)))) exact (hab rfl).elim All goals completed! 🐙
· inl.inr 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)))) exact Finset.mem_insert_of_mem (Finset.mem_image.mpr ⟨b, hb, rfl⟩) All goals completed! 🐙
· inr 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)))) rcases hb with rfl | hb inr.inl 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))))inr.inr 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))))
· inr.inl 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)))) exact Finset.mem_insert_of_mem
(Finset.mem_image.mpr ⟨a, ha, AffineSubspace.affineSpan_pair_comm⟩) All goals completed! 🐙
· inr.inr 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)))) obtain ⟨i, _, rfl⟩ := Finset.mem_image.mp ha inr.inr 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))))
obtain ⟨j, _, rfl⟩ := Finset.mem_image.mp hb inr.inr 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))))
have heq := affineSpan_pair_eq_of_mem_of_mem_of_ne
(axisPoint_mem i) (axisPoint_mem j) hab inr.inr 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))))
exact Finset.mem_insert.mpr (Or.inl heq) All goals completed! 🐙The near-pencil construction has at most $n$ ordinary lines.
@[category API, AMS 5 51]
theorem ordinaryLines_nearPencil_le {n : ℕ} (hn : 1 ≤ n) :
(ordinaryLines (nearPencil n)).card ≤ n := by n:ℕhn:1 ≤ n⊢ (ordinaryLines (nearPencil n)).card ≤ n
classical
calc
(ordinaryLines (nearPencil n)).card ≤ _ := Finset.card_le_card (ordinaryLines_nearPencil_subset n)
_ ≤ (((Finset.range (n - 1)).image axisPoint).image
fun p => line[ℝ, apex, p]).card + 1 := Finset.card_insert_le _ _
_ ≤ ((Finset.range (n - 1)).image axisPoint).card + 1 :=
Nat.add_le_add_right Finset.card_image_le 1
_ ≤ (Finset.range (n - 1)).card + 1 := Nat.add_le_add_right Finset.card_image_le 1
_ = n := by n:ℕhn:1 ≤ n⊢ (Finset.range (n - 1)).card + 1 = n rw [Finset.card_range n:ℕhn:1 ≤ n⊢ n - 1 + 1 = n n:ℕhn:1 ≤ n⊢ n - 1 + 1 = n] n:ℕhn:1 ≤ n⊢ n - 1 + 1 = n; omega 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 (by n:ℕhn:3 ≤ n⊢ 1 ≤ n omega All goals completed! 🐙)) (nearPencil_not_collinear hn)).trans
(ordinaryLines_nearPencil_le (by n:ℕhn:3 ≤ n⊢ 1 ≤ n omega 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 : ℝ)) := by ⊢ (fun n ↦ ↑(f n)) =Θ[atTop] fun n ↦ ↑n
sorry 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 : ℝ)) := by ⊢ (fun n ↦ ↑(f n)) =O[atTop] fun n ↦ ↑n
apply Asymptotics.IsBigO.of_bound 1 ⊢ ∀ᶠ (x : ℕ) in atTop, ‖↑(f x)‖ ≤ 1 * ‖↑x‖
filter_upwards [eventually_ge_atTop 3] with n hn n:ℕhn:3 ≤ n⊢ ‖↑(f n)‖ ≤ 1 * ‖↑n‖
simpa using (Nat.cast_le.mpr (erdos_210.upper_bound hn) : (f n : ℝ) ≤ (n : ℝ)) All goals completed! 🐙Kelly–Moser and the explicit upper construction together imply linear growth.
@[category API, AMS 5 51]
theorem linear_growth_of_kelly_moser (h : ∀ n : ℕ, 3 ≤ n → 3 * n ≤ 7 * f n) :
(fun n : ℕ => (f n : ℝ)) =Θ[atTop] (fun n : ℕ => (n : ℝ)) := by h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ (fun n ↦ ↑(f n)) =Θ[atTop] fun n ↦ ↑n
refine ⟨f_isBigO, Asymptotics.IsBigO.of_bound 7 ?_⟩ h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ ∀ᶠ (x : ℕ) in atTop, ‖↑x‖ ≤ 7 * ‖↑(f x)‖
filter_upwards [eventually_ge_atTop 3] with n hn h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nn:ℕhn:3 ≤ n⊢ ‖↑n‖ ≤ 7 * ‖↑(f n)‖
have hb := h n hn h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nn:ℕhn:3 ≤ nhb:3 * n ≤ 7 * f n⊢ ‖↑n‖ ≤ 7 * ‖↑(f n)‖
have hb' : n ≤ 7 * f n := by h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ (fun n ↦ ↑(f n)) =Θ[atTop] fun n ↦ ↑n h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nn:ℕhn:3 ≤ nhb:3 * n ≤ 7 * f nhb':n ≤ 7 * f n⊢ ‖↑n‖ ≤ 7 * ‖↑(f n)‖ omega h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nn:ℕhn:3 ≤ nhb:3 * n ≤ 7 * f nhb':n ≤ 7 * f n⊢ ‖↑n‖ ≤ 7 * ‖↑(f n)‖ h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f nn:ℕhn:3 ≤ nhb:3 * n ≤ 7 * f nhb':n ≤ 7 * f n⊢ ‖↑n‖ ≤ 7 * ‖↑(f n)‖
have hr : (n : ℝ) ≤ 7 * (f n : ℝ) := by h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n⊢ (fun n ↦ ↑(f n)) =Θ[atTop] fun n ↦ ↑n 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)‖ exact_mod_cast hb' 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)‖ 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)‖
simpa using hr All goals completed! 🐙The Green–Tao bound likewise implies linear growth.
@[category API, AMS 5 51]
theorem linear_growth_of_green_tao (h : ∀ᶠ n : ℕ in atTop, n ≤ 2 * f n) :
(fun n : ℕ => (f n : ℝ)) =Θ[atTop] (fun n : ℕ => (n : ℝ)) := by h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ (fun n ↦ ↑(f n)) =Θ[atTop] fun n ↦ ↑n
refine ⟨f_isBigO, Asymptotics.IsBigO.of_bound 2 ?_⟩ h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ ∀ᶠ (x : ℕ) in atTop, ‖↑x‖ ≤ 2 * ‖↑(f x)‖
filter_upwards [h] with n hn h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nn:ℕhn:n ≤ 2 * f n⊢ ‖↑n‖ ≤ 2 * ‖↑(f n)‖
have hr : (n : ℝ) ≤ 2 * (f n : ℝ) := by h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ (fun n ↦ ↑(f n)) =Θ[atTop] fun n ↦ ↑n h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nn:ℕhn:n ≤ 2 * f nhr:↑n ≤ 2 * ↑(f n)⊢ ‖↑n‖ ≤ 2 * ‖↑(f n)‖ exact_mod_cast hn h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nn:ℕhn:n ≤ 2 * f nhr:↑n ≤ 2 * ↑(f n)⊢ ‖↑n‖ ≤ 2 * ‖↑(f n)‖ h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f nn:ℕhn:n ≤ 2 * f nhr:↑n ≤ 2 * ↑(f n)⊢ ‖↑n‖ ≤ 2 * ‖↑(f n)‖
simpa using hr All goals completed! 🐙Fewer than three points are collinear.
@[category API, AMS 5 51]
theorem collinear_of_card_lt_three {s : Finset ℝ²} (hs : s.card < 3) :
Collinear ℝ (s : Set ℝ²) := by s:Finset ℝ²hs:s.card < 3⊢ Collinear ℝ ↑s
classical
have hc : s.card = 0 ∨ s.card = 1 ∨ s.card = 2 := by omega 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 ∨ s.card = 1 ∨ s.card = 2⊢ Collinear ℝ ↑s
rcases hc with hc | hc | hc inl s:Finset ℝ²hs:s.card < 3hc:s.card = 0⊢ Collinear ℝ ↑sinr.inl s:Finset ℝ²hs:s.card < 3hc:s.card = 1⊢ Collinear ℝ ↑sinr.inr s:Finset ℝ²hs:s.card < 3hc:s.card = 2⊢ Collinear ℝ ↑s
· inl s:Finset ℝ²hs:s.card < 3hc:s.card = 0⊢ Collinear ℝ ↑s have he : s = ∅ := Finset.card_eq_zero.mp hc inl s:Finset ℝ²hs:s.card < 3hc:s.card = 0he:s = ∅⊢ Collinear ℝ ↑s
simpa [he] using collinear_empty ℝ ℝ² All goals completed! 🐙
· inr.inl s:Finset ℝ²hs:s.card < 3hc:s.card = 1⊢ Collinear ℝ ↑s obtain ⟨a, rfl⟩ := Finset.card_eq_one.mp hc inr.inl a:ℝ²hs:{a}.card < 3hc:{a}.card = 1⊢ Collinear ℝ ↑{a}
simpa using collinear_singleton ℝ a All goals completed! 🐙
· inr.inr s:Finset ℝ²hs:s.card < 3hc:s.card = 2⊢ Collinear ℝ ↑s obtain ⟨a, b, _, rfl⟩ := Finset.card_eq_two.mp hc inr.inr a:ℝ²b:ℝ²left✝:a ≠ bhs:{a, b}.card < 3hc:{a, b}.card = 2⊢ Collinear ℝ ↑{a, b}
simpa using collinear_pair ℝ a b All goals completed! 🐙The definition uses the default value zero where no noncollinear configuration exists.
@[category API, AMS 5 51]
theorem f_eq_zero_of_lt_three {n : ℕ} (hn : n < 3) : f n = 0 := by n:ℕhn:n < 3⊢ f n = 0
have he : {m : ℕ | ∃ s : Finset ℝ²,
s.card = n ∧ ¬ Collinear ℝ (s : Set ℝ²) ∧ (ordinaryLines s).card = m} = ∅ := by
apply Set.eq_empty_iff_forall_notMem.mpr n:ℕhn:n < 3⊢ ∀ (x : ℕ), x ∉ {m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m} n:ℕhn:n < 3he:{m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m} = ∅⊢ f n = 0
rintro m ⟨s, hs, hc, _⟩ n:ℕhn:n < 3m:ℕs:Finset ℝ²hs:s.card = nhc:¬Collinear ℝ ↑sright✝:(ordinaryLines s).card = m⊢ False n:ℕhn:n < 3he:{m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m} = ∅⊢ f n = 0
exact hc (collinear_of_card_lt_three (by n:ℕhn:n < 3m:ℕs:Finset ℝ²hs:s.card = nhc:¬Collinear ℝ ↑sright✝:(ordinaryLines s).card = m⊢ s.card < 3 n:ℕhn:n < 3he:{m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m} = ∅⊢ f n = 0 omega All goals completed! 🐙 n:ℕhn:n < 3he:{m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m} = ∅⊢ f n = 0)) n:ℕhn:n < 3he:{m | ∃ s, s.card = n ∧ ¬Collinear ℝ ↑s ∧ (ordinaryLines s).card = m} = ∅⊢ f n = 0
simp [f, he] All goals completed! 🐙Kelly–Moser's extremal-function formulation is equivalent to its configuration formulation.
@[category API, AMS 5 51]
theorem kelly_moser_iff : (∀ n : ℕ, 3 ≤ n → 3 * n ≤ 7 * f n) ↔
∀ s : Finset ℝ², ¬ Collinear ℝ (s : Set ℝ²) →
3 * s.card ≤ 7 * (ordinaryLines s).card := by ⊢ (∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n) ↔ ∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).card
constructor mp ⊢ (∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n) → ∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).cardmpr ⊢ (∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).card) → ∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n
· mp ⊢ (∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n) → ∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).card intro h s hs mp h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f ns:Finset ℝ²hs:¬Collinear ℝ ↑s⊢ 3 * s.card ≤ 7 * (ordinaryLines s).card
have hn : 3 ≤ s.card := by ⊢ (∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n) ↔ ∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).card mp h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f ns:Finset ℝ²hs:¬Collinear ℝ ↑shn:3 ≤ s.card⊢ 3 * s.card ≤ 7 * (ordinaryLines s).card
by_contra! hn h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f ns:Finset ℝ²hs:¬Collinear ℝ ↑shn:s.card < 3⊢ False mp h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f ns:Finset ℝ²hs:¬Collinear ℝ ↑shn:3 ≤ s.card⊢ 3 * s.card ≤ 7 * (ordinaryLines s).card
exact hs (collinear_of_card_lt_three hn)mp h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f ns:Finset ℝ²hs:¬Collinear ℝ ↑shn:3 ≤ s.card⊢ 3 * s.card ≤ 7 * (ordinaryLines s).cardmp h:∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f ns:Finset ℝ²hs:¬Collinear ℝ ↑shn:3 ≤ s.card⊢ 3 * s.card ≤ 7 * (ordinaryLines s).card
exact (h s.card hn).trans (Nat.mul_le_mul_left 7 (f_le rfl hs)) All goals completed! 🐙
· mpr ⊢ (∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).card) → ∀ (n : ℕ), 3 ≤ n → 3 * n ≤ 7 * f n intro h n hn mpr h:∀ (s : Finset ℝ²), ¬Collinear ℝ ↑s → 3 * s.card ≤ 7 * (ordinaryLines s).cardn:ℕhn:3 ≤ n⊢ 3 * n ≤ 7 * f n
obtain ⟨s, hs, hc, hf⟩ := f_attained hn mpr 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
simpa [hs, hf] using h s hc 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 := by ⊢ (∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n) ↔
∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card
constructor mp ⊢ (∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n) →
∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).cardmpr ⊢ (∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card) →
∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n
· mp ⊢ (∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n) →
∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card intro h mp h:∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n⊢ ∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card
obtain ⟨N, hN⟩ := eventually_atTop.mp h mp 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
refine ⟨max 3 N, le_max_left _ _, ?_⟩ mp 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
intro s hs hc mp 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
exact (hN s.card ((le_max_right _ _).trans hs)).trans
(Nat.mul_le_mul_left 2 (f_le rfl hc)) All goals completed! 🐙
· mpr ⊢ (∃ N, 3 ≤ N ∧ ∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card) →
∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n rintro ⟨N, hN, h⟩ mpr N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card⊢ ∀ᶠ (n : ℕ) in atTop, n ≤ 2 * f n
apply eventually_atTop.mpr mpr 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
refine ⟨N, ?_⟩ mpr N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).card⊢ ∀ (b : ℕ), N ≤ b → b ≤ 2 * f b
intro n hn mpr N:ℕhN:3 ≤ Nh:∀ (s : Finset ℝ²), N ≤ s.card → ¬Collinear ℝ ↑s → s.card ≤ 2 * (ordinaryLines s).cardn:ℕhn:N ≤ n⊢ n ≤ 2 * f n
obtain ⟨s, hs, hc, hf⟩ := f_attained (hN.trans hn) mpr 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 (by 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 simpa [hs] using hn All goals completed! 🐙) hcA 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 := by 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
apply Nat.le_antisymm ((le_f_iff hn).mpr hlower) 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
obtain ⟨s, hs, hc, hm⟩ := hattain 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
simpa [hm] using f_le hs hc 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 := by 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 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 hu 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
intro hn 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
exact Nat.le_antisymm (hu hn) hl All goals completed! 🐙end Erdos210