/-
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 211
References:
[Be83] Beck, József, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry. Combinatorica (1983), 281-297.
[SzTr83] Szemerédi, Endre and Trotter, Jr., William T., Extremal problems in discrete geometry. Combinatorica (1983), 381-392.
[Er84] Erdős, P., Research problems. Period. Math. Hungar. (1984), 101-103.
[BGS74] Burr, Stefan A. and Grünbaum, Branko and Sloane, N. J. A., The orchard problem. Geometriae Dedicata (1974), 397-424.
[FuPa84] Füredi, Z. and Palásti, I., Arrangements of lines with a large number of triangles. Proc. Amer. Math. Soc. (1984), 561-566.
@[expose] public sectionnamespace Erdos211open EuclideanGeometry Filteropen scoped Classical inDistinct lines containing two distinct points of the configuration.
noncomputable def determinedLines (s : Finset ℝ²) : Finset (AffineSubspace ℝ ℝ²) :=
s.offDiag.image fun p => line[ℝ, p.1, p.2]open scoped Classical inThe uniform Erdős–Beck lower bound.
def MainBound : Prop :=
∃ c : ℝ, 0 < c ∧ ∀ (n k : ℕ), 1 ≤ k → k < n →
∀ s : Finset ℝ², s.card = n →
(∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ n - k) →
c * (k : ℝ) * (n : ℝ) ≤ ((determinedLines s).card : ℝ)open scoped Classical inThe quadratic lower bound for configurations with at most half the points on a line.
def QuadraticBound : Prop :=
∃ c : ℝ, 0 < c ∧ ∀ n : ℕ, 1 ≤ n →
∀ s : Finset ℝ², s.card = 2 * n →
(∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ n) →
c * (n : ℝ) ^ 2 ≤ ((determinedLines s).card : ℝ)open scoped Classical inErdős speculates that there are at least $(1+o(1))kn/6$ determined lines [Er84]. The asymptotic bound is uniform over $1 \leq k < n$.
@[category research open, AMS 5 52]
theorem erdos_211.variants.one_sixth :
∀ ε : ℝ, 0 < ε → ∃ N : ℕ, ∀ (n k : ℕ), N ≤ n → 1 ≤ k → k < n →
∀ s : Finset ℝ², s.card = n →
(∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ n - k) →
(1 - ε) / 6 * (k : ℝ) * (n : ℝ) ≤ ((determinedLines s).card : ℝ) := ⊢ ∀ (ε : ℝ),
0 < ε →
∃ N,
∀ (n k : ℕ),
N ≤ n →
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
(1 - ε) / 6 * ↑k * ↑n ≤ ↑(determinedLines s).card
All goals completed! 🐙open scoped Classical inThere are arbitrarily large configurations with no four collinear points and $\sim n^2/6$ three-point lines, constructed by Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84]. The index need not equal the number of points.
@[category research solved, AMS 5 52]
theorem erdos_211.variants.sharpness :
∃ s : ℕ → Finset ℝ²,
Tendsto (fun i => (s i).card) atTop atTop ∧
(∀ (i : ℕ) (L : AffineSubspace ℝ ℝ²), IsLine L →
((s i).filter fun p => p ∈ L).card ≤ 3) ∧
Tendsto (fun i =>
(((determinedLines (s i)).filter fun L => ((s i).filter fun p => p ∈ L).card = 3).card : ℝ) /
((s i).card : ℝ) ^ 2) atTop (nhds (1 / 6 : ℝ)) := ⊢ ∃ s,
Tendsto (fun i ↦ (s i).card) atTop atTop ∧
(∀ (i : ℕ) (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s i | p ∈ L}.card ≤ 3) ∧
Tendsto (fun i ↦ ↑{L ∈ determinedLines (s i) | {p ∈ s i | p ∈ L}.card = 3}.card / ↑(s i).card ^ 2) atTop
(nhds (1 / 6))
All goals completed! 🐙Membership means that two distinct points of the configuration generate the line.
@[category API, AMS 5 52]
theorem mem_determinedLines {s : Finset ℝ²} {L : AffineSubspace ℝ ℝ²} :
L ∈ determinedLines s ↔ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L := s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ L ∈ determinedLines s ↔ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L
classical
s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ (∃ a, (a.1 ∈ s ∧ a.2 ∈ s ∧ a.1 ≠ a.2) ∧ line[ℝ, a.1, a.2] = L) ↔ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L
All goals completed! 🐙A span of two distinct points is a geometric line.
a:ℝ²b:ℝ²hab:a ≠ b⊢ Module.finrank ℝ ↥(ℝ ∙ (a -ᵥ b)) = 1
exact finrank_span_singleton (vsub_ne_zero.mpr hab) All goals completed! 🐙Two distinct points on a geometric line span the whole line.
@[category API, AMS 5 52]
theorem line_pair_eq {a b : ℝ²} {L : AffineSubspace ℝ ℝ²}
(hL : IsLine L) (ha : a ∈ L) (hb : b ∈ L) (hab : a ≠ b) :
line[ℝ, a, b] = L := by a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b] = L
apply (AffineSubspace.eq_iff_direction_eq_of_mem (left_mem_affineSpan_pair ℝ a b) ha).mpr a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b].direction = L.direction
apply Submodule.eq_of_le_of_finrank_eq hle a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b].direction ≤ L.directionhd a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ Module.finrank ℝ ↥line[ℝ, a, b].direction = Module.finrank ℝ ↥L.direction
· hle a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ line[ℝ, a, b].direction ≤ L.direction exact AffineSubspace.direction_le (affineSpan_pair_le_of_mem_of_mem ha hb) All goals completed! 🐙
· hd a:ℝ²b:ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lha:a ∈ Lhb:b ∈ Lhab:a ≠ b⊢ Module.finrank ℝ ↥line[ℝ, a, b].direction = Module.finrank ℝ ↥L.direction exact (isLine_pair hab).trans hL.symm All goals completed! 🐙Every determined line is one-dimensional.
@[category API, AMS 5 52]
theorem isLine_of_mem_determinedLines {s : Finset ℝ²} {L : AffineSubspace ℝ ℝ²}
(hL : L ∈ determinedLines s) : IsLine L := by s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines s⊢ IsLine L
obtain ⟨a, _, b, _, hab, rfl⟩ := mem_determinedLines.mp hL s:Finset ℝ²a:ℝ²left✝¹:a ∈ sb:ℝ²left✝:b ∈ shab:a ≠ bhL:line[ℝ, a, b] ∈ determinedLines s⊢ IsLine line[ℝ, a, b]
exact isLine_pair hab All goals completed! 🐙The finite image counts precisely all geometric lines containing at least two points.
@[category API, AMS 5 52]
theorem determinedLines_eq {s : Finset ℝ²} {L : AffineSubspace ℝ ℝ²} :
L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ ((s : Set ℝ²) ∩ (L : Set ℝ²)).ncard := by s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ (↑s ∩ ↑L).ncard
classical
have hcard : ((s : Set ℝ²) ∩ (L : Set ℝ²)).ncard =
(s.filter fun p => p ∈ L).card := by
rw [← Set.ncard_coe_finset s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ (↑s ∩ ↑L).ncard = (↑({p ∈ s | p ∈ L})).ncard s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ (↑s ∩ ↑L).ncard = (↑({p ∈ s | p ∈ L})).ncard s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ (↑s ∩ ↑L).ncard] s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ (↑s ∩ ↑L).ncard = (↑({p ∈ s | p ∈ L})).ncard s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ (↑s ∩ ↑L).ncard
congr 1 s:Finset ℝ²L:AffineSubspace ℝ ℝ²⊢ ↑s ∩ ↑L = ↑({p ∈ s | p ∈ L}) s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ (↑s ∩ ↑L).ncard
ext p s:Finset ℝ²L:AffineSubspace ℝ ℝ²p:ℝ²⊢ p ∈ ↑s ∩ ↑L ↔ p ∈ ↑({p ∈ s | p ∈ L}) s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ (↑s ∩ ↑L).ncard
simp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ (↑s ∩ ↑L).ncard s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ (↑s ∩ ↑L).ncard
rw [hcard s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card] s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s ↔ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card
constructor mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s → IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.cardmpr s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card → L ∈ determinedLines s
· mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s → IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card intro h mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines s⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card
obtain ⟨a, ha, b, hb, hab, heq⟩ := mem_determinedLines.mp h mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card
refine ⟨isLine_of_mem_determinedLines h, ?_⟩ mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ 2 ≤ {p ∈ s | p ∈ L}.card
apply Nat.succ_le_iff.mpr mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ 1 < {p ∈ s | p ∈ L}.card
apply Finset.one_lt_card.mpr mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardh:L ∈ determinedLines sa:ℝ²ha:a ∈ sb:ℝ²hb:b ∈ shab:a ≠ bheq:line[ℝ, a, b] = L⊢ ∃ a ∈ {p ∈ s | p ∈ L}, ∃ b ∈ {p ∈ s | p ∈ L}, a ≠ b
exact ⟨a, Finset.mem_filter.mpr ⟨ha, heq ▸ left_mem_affineSpan_pair ℝ a b⟩,
b, Finset.mem_filter.mpr ⟨hb, heq ▸ right_mem_affineSpan_pair ℝ a b⟩, hab⟩ All goals completed! 🐙
· mpr s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ IsLine L ∧ 2 ≤ {p ∈ s | p ∈ L}.card → L ∈ determinedLines s rintro ⟨hL, hcard⟩ mpr s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard✝:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardhL:IsLine Lhcard:2 ≤ {p ∈ s | p ∈ L}.card⊢ L ∈ determinedLines s
obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp (Nat.lt_of_succ_le hcard) mpr s:Finset ℝ²L:AffineSubspace ℝ ℝ²hcard✝:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardhL:IsLine Lhcard:2 ≤ {p ∈ s | p ∈ L}.carda:ℝ²ha:a ∈ {p ∈ s | p ∈ L}b:ℝ²hb:b ∈ {p ∈ s | p ∈ L}hab:a ≠ b⊢ L ∈ determinedLines s
exact mem_determinedLines.mpr ⟨a, (Finset.mem_filter.mp ha).1,
b, (Finset.mem_filter.mp hb).1,
hab, line_pair_eq hL (Finset.mem_filter.mp ha).2 (Finset.mem_filter.mp hb).2 hab⟩ All goals completed! 🐙open scoped Classical inThe fiber over a geometric line consists of the ordered pairs of distinct incident points.
@[category API, AMS 5 52]
theorem pair_fiber_eq {s : Finset ℝ²} {L : AffineSubspace ℝ ℝ²} (hL : IsLine L) :
(s.offDiag.filter fun p => line[ℝ, p.1, p.2] = L) =
(s.filter fun p => p ∈ L).offDiag := by s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine L⊢ {p ∈ s.offDiag | line[ℝ, p.1, p.2] = L} = {p ∈ s | p ∈ L}.offDiag
classical
ext p s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ p ∈ {p ∈ s.offDiag | line[ℝ, p.1, p.2] = L} ↔ p ∈ {p ∈ s | p ∈ L}.offDiag
simp only [Finset.mem_filter, Finset.mem_offDiag] s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L ↔ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2
constructor mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L → (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2mpr s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 → (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L
· mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L → (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 rintro ⟨⟨ha, hb, hab⟩, heq⟩ mp s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²heq:line[ℝ, p.1, p.2] = Lha:p.1 ∈ shb:p.2 ∈ shab:p.1 ≠ p.2⊢ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2
exact ⟨⟨ha, heq ▸ left_mem_affineSpan_pair ℝ p.1 p.2⟩,
⟨hb, heq ▸ right_mem_affineSpan_pair ℝ p.1 p.2⟩, hab⟩ All goals completed! 🐙
· mpr s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²⊢ (p.1 ∈ s ∧ p.1 ∈ L) ∧ (p.2 ∈ s ∧ p.2 ∈ L) ∧ p.1 ≠ p.2 → (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L rintro ⟨⟨ha, haL⟩, ⟨hb, hbL⟩, hab⟩ mpr s:Finset ℝ²L:AffineSubspace ℝ ℝ²hL:IsLine Lp:ℝ² × ℝ²ha:p.1 ∈ shaL:p.1 ∈ Lhab:p.1 ≠ p.2hb:p.2 ∈ shbL:p.2 ∈ L⊢ (p.1 ∈ s ∧ p.2 ∈ s ∧ p.1 ≠ p.2) ∧ line[ℝ, p.1, p.2] = L
exact ⟨⟨ha, hb, hab⟩, line_pair_eq hL haL hbL hab⟩ All goals completed! 🐙open scoped Classical inExact double counting: each ordered pair belongs to its unique determined line.
@[category API, AMS 5 52]
theorem ordered_pair_count (s : Finset ℝ²) :
s.card * (s.card - 1) = ∑ L ∈ determinedLines s,
(s.filter fun p => p ∈ L).card * ((s.filter fun p => p ∈ L).card - 1) := by s:Finset ℝ²⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)
classical
have h := Finset.card_eq_sum_card_image (fun p : ℝ² × ℝ² => line[ℝ, p.1, p.2]) s.offDiag s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.card⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)
have hoff : s.offDiag.card = s.card * (s.card - 1) := by s:Finset ℝ²⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)
rw [Finset.offDiag_card, s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.card⊢ s.card * s.card - s.card = s.card * (s.card - 1) s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) Nat.mul_sub_left_distrib, s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.card⊢ s.card * s.card - s.card = s.card * s.card - s.card * 1 s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) Nat.mul_one s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.card⊢ s.card * s.card - s.card = s.card * s.card - s.card s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)] s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) s:Finset ℝ²h:s.offDiag.card = ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)
rw [hoff s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)] at h s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ s.card * (s.card - 1) = ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)
calc
s.card * (s.card - 1) = _ := h
_ = _ := by s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ ∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.card =
∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)
apply Finset.sum_congr rfl s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)⊢ ∀ x ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag,
{a ∈ s.offDiag | line[ℝ, a.1, a.2] = x}.card = {p ∈ s | p ∈ x}.card * ({p ∈ s | p ∈ x}.card - 1)
intro L hL s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)L:AffineSubspace ℝ ℝ²hL:L ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag⊢ {a ∈ s.offDiag | line[ℝ, a.1, a.2] = L}.card = {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1)
rw [pair_fiber_eq (isLine_of_mem_determinedLines hL), s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)L:AffineSubspace ℝ ℝ²hL:L ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag⊢ {p ∈ s | p ∈ L}.offDiag.card = {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) All goals completed! 🐙 Finset.offDiag_card, s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)L:AffineSubspace ℝ ℝ²hL:L ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag⊢ {p ∈ s | p ∈ L}.card * {p ∈ s | p ∈ L}.card - {p ∈ s | p ∈ L}.card = {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) All goals completed! 🐙 Nat.mul_sub_left_distrib, s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)L:AffineSubspace ℝ ℝ²hL:L ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag⊢ {p ∈ s | p ∈ L}.card * {p ∈ s | p ∈ L}.card - {p ∈ s | p ∈ L}.card =
{p ∈ s | p ∈ L}.card * {p ∈ s | p ∈ L}.card - {p ∈ s | p ∈ L}.card * 1 All goals completed! 🐙 Nat.mul_one s:Finset ℝ²h:s.card * (s.card - 1) =
∑ b ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag, {a ∈ s.offDiag | line[ℝ, a.1, a.2] = b}.cardhoff:s.offDiag.card = s.card * (s.card - 1)L:AffineSubspace ℝ ℝ²hL:L ∈ Finset.image (fun p ↦ line[ℝ, p.1, p.2]) s.offDiag⊢ {p ∈ s | p ∈ L}.card * {p ∈ s | p ∈ L}.card - {p ∈ s | p ∈ L}.card =
{p ∈ s | p ∈ L}.card * {p ∈ s | p ∈ L}.card - {p ∈ s | p ∈ L}.card All goals completed! 🐙] All goals completed! 🐙open scoped Classical in
Elementary bound when no line contains more than $r$ points.
This is weaker than the Erdős–Beck bound and is not a proof of erdos_211.
@[category API, AMS 5 52]
theorem pair_count_bound {s : Finset ℝ²} {r : ℕ}
(hr : ∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ r) :
s.card * (s.card - 1) ≤ (determinedLines s).card * (r * (r - 1)) := by s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ s.card * (s.card - 1) ≤ (determinedLines s).card * (r * (r - 1))
classical
rw [ordered_pair_count s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ (determinedLines s).card * (r * (r - 1)) s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ (determinedLines s).card * (r * (r - 1))] s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ (determinedLines s).card * (r * (r - 1))
calc
_ ≤ ∑ _L ∈ determinedLines s, r * (r - 1) := by s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ ∑ _L ∈ determinedLines s, r * (r - 1)
apply Finset.sum_le_sum s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∀ i ∈ determinedLines s, {p ∈ s | p ∈ i}.card * ({p ∈ s | p ∈ i}.card - 1) ≤ r * (r - 1)
intro L hL s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ rL:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines s⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ r * (r - 1)
have h := hr L (isLine_of_mem_determinedLines hL) s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ rL:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines sh:{p ∈ s | p ∈ L}.card ≤ r⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) ≤ r * (r - 1)
exact Nat.mul_le_mul h (Nat.sub_le_sub_right h 1) All goals completed! 🐙
_ = _ := by s:Finset ℝ²r:ℕhr:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ r⊢ ∑ _L ∈ determinedLines s, r * (r - 1) = (determinedLines s).card * (r * (r - 1)) simp All goals completed! 🐙open scoped Classical inIn a configuration with no three collinear points, every unordered pair gives a line.
@[category API, AMS 5 52]
theorem line_count_no_three {s : Finset ℝ²}
(hs : ∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ 2) :
s.card * (s.card - 1) = 2 * (determinedLines s).card := by s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ s.card * (s.card - 1) = 2 * (determinedLines s).card
classical
rw [ordered_pair_count s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2 * (determinedLines s).card s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2 * (determinedLines s).card] s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2 * (determinedLines s).card
calc
_ = ∑ _L ∈ determinedLines s, 2 := by s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = ∑ _L ∈ determinedLines s, 2
apply Finset.sum_congr rfl s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∀ x ∈ determinedLines s, {p ∈ s | p ∈ x}.card * ({p ∈ s | p ∈ x}.card - 1) = 2
intro L hL s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines s⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
have hlo := (determinedLines_eq.mp hL).2 s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncard⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
have hc : ((s : Set ℝ²) ∩ (L : Set ℝ²)).ncard =
(s.filter fun p => p ∈ L).card := by s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∑ L ∈ determinedLines s, {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = ∑ _L ∈ determinedLines s, 2 s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
rw [← Set.ncard_coe_finset s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncard⊢ (↑s ∩ ↑L).ncard = (↑({p ∈ s | p ∈ L})).ncard s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncard⊢ (↑s ∩ ↑L).ncard = (↑({p ∈ s | p ∈ L})).ncard s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2] s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncard⊢ (↑s ∩ ↑L).ncard = (↑({p ∈ s | p ∈ L})).ncard s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
congr 1 s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncard⊢ ↑s ∩ ↑L = ↑({p ∈ s | p ∈ L}) s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
ext p s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardp:ℝ²⊢ p ∈ ↑s ∩ ↑L ↔ p ∈ ↑({p ∈ s | p ∈ L}) s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
simp s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2 s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ (↑s ∩ ↑L).ncardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
rw [hc s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ {p ∈ s | p ∈ L}.cardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2 s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ {p ∈ s | p ∈ L}.cardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2] at hlo s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ {p ∈ s | p ∈ L}.cardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.card⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
have heq := Nat.le_antisymm (hs L (isLine_of_mem_determinedLines hL)) hlo s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2L:AffineSubspace ℝ ℝ²hL:L ∈ determinedLines shlo:2 ≤ {p ∈ s | p ∈ L}.cardhc:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardheq:{p ∈ s | p ∈ L}.card = 2⊢ {p ∈ s | p ∈ L}.card * ({p ∈ s | p ∈ L}.card - 1) = 2
simp [heq] All goals completed! 🐙
_ = _ := by s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2⊢ ∑ _L ∈ determinedLines s, 2 = 2 * (determinedLines s).card simp [Nat.mul_comm] All goals completed! 🐙open scoped Classical inWith at most three points on each line, double counting gives the sharp leading coefficient $1/6$ in a quadratic lower bound.
@[category API, AMS 5 52]
theorem six_mul_lines_no_four {s : Finset ℝ²}
(hs : ∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ 3) :
s.card * (s.card - 1) ≤ 6 * (determinedLines s).card := by s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3⊢ s.card * (s.card - 1) ≤ 6 * (determinedLines s).card
simpa [Nat.mul_comm] using pair_count_bound hs All goals completed! 🐙open scoped Classical inThe real-valued form of the preceding bound, including empty configurations.
@[category API, AMS 5 52]
theorem real_lower_bound_no_four {s : Finset ℝ²}
(hs : ∀ L : AffineSubspace ℝ ℝ², IsLine L → (s.filter fun p => p ∈ L).card ≤ 3) :
(s.card : ℝ) * ((s.card : ℝ) - 1) / 6 ≤ ((determinedLines s).card : ℝ) := by s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card
have h := six_mul_lines_no_four hs s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).card⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card
by_cases hzero : s.card = 0 pos s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:s.card = 0⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).cardneg s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:¬s.card = 0⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card
· pos s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:s.card = 0⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card simp [hzero] All goals completed! 🐙
· neg s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:¬s.card = 0⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card have hone : 1 ≤ s.card := by omega neg s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:¬s.card = 0hone:1 ≤ s.card⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card neg s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:¬s.card = 0hone:1 ≤ s.card⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card
have hreal : (s.card : ℝ) * ((s.card : ℝ) - 1) ≤
6 * ((determinedLines s).card : ℝ) := by
exact_mod_cast h neg s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:¬s.card = 0hone:1 ≤ s.cardhreal:↑s.card * (↑s.card - 1) ≤ 6 * ↑(determinedLines s).card⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).cardneg s:Finset ℝ²hs:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 3h:s.card * (s.card - 1) ≤ 6 * (determinedLines s).cardhzero:¬s.card = 0hone:1 ≤ s.cardhreal:↑s.card * (↑s.card - 1) ≤ 6 * ↑(determinedLines s).card⊢ ↑s.card * (↑s.card - 1) / 6 ≤ ↑(determinedLines s).card
linarith All goals completed! 🐙The quadratic special case follows with twice the constant in the main bound.
@[category API, AMS 5 52]
theorem quadratic_of_erdos_211 (h : MainBound) : QuadraticBound := by h:MainBound⊢ QuadraticBound
obtain ⟨c, hc, h⟩ := h c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).card⊢ QuadraticBound
refine ⟨2 * c, by c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).card⊢ 0 < 2 * c positivity All goals completed! 🐙, ?_⟩
intro n hn s hs hcap c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card
have hkn : n < 2 * n := by h:MainBound⊢ QuadraticBound c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * n⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card omega c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * n⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * n⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card
have hb := h (2 * n) n hn hkn s hs (by c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * n⊢ ∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ 2 * n - n c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * ↑(2 * n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card
intro L hL c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nL:AffineSubspace ℝ ℝ²hL:IsLine L⊢ {p ∈ s | p ∈ L}.card ≤ 2 * n - n c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * ↑(2 * n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card
have := hcap L hL c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nL:AffineSubspace ℝ ℝ²hL:IsLine Lthis:{p ∈ s | p ∈ L}.card ≤ n⊢ {p ∈ s | p ∈ L}.card ≤ 2 * n - n c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * ↑(2 * n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card
omega All goals completed! 🐙 c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * ↑(2 * n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card) c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * ↑(2 * n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card
push_cast at hb c:ℝhc:0 < ch:∀ (n k : ℕ),
1 ≤ k →
k < n →
∀ (s : Finset ℝ²),
s.card = n →
(∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ n - k) →
c * ↑k * ↑n ≤ ↑(determinedLines s).cardn:ℕhn:1 ≤ ns:Finset ℝ²hs:s.card = 2 * nhcap:∀ (L : AffineSubspace ℝ ℝ²), IsLine L → {p ∈ s | p ∈ L}.card ≤ nhkn:n < 2 * nhb:c * ↑n * (2 * ↑n) ≤ ↑(determinedLines s).card⊢ 2 * c * ↑n ^ 2 ≤ ↑(determinedLines s).card
nlinarith All goals completed! 🐙Let $1\leq k<n$. Given $n$ points in $\mathbb{R}^2$, at most $n-k$ on any line, there are $\gg kn$ many lines which contain at least two points. Solved by Beck [Be83] and Szemerédi and Trotter [SzTr83].
@[category research solved, AMS 5 52,
formal_proof using lean4 at "https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos211.lean#L900"]
theorem erdos_211 : MainBound := by ⊢ MainBound
sorry All goals completed! 🐙Given any $2n$ points with at most $n$ on a line there are $\gg n^2$ many lines formed by the points. Solved by Beck [Be83] and Szemerédi and Trotter [SzTr83].
@[category research solved, AMS 5 52]
theorem erdos_211.variants.quadratic : QuadraticBound :=
quadratic_of_erdos_211 erdos_211end Erdos211