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

References:

    erdosproblems.com/669

    [BGS74] Burr, Stefan A. and Grünbaum, Branko and Sloane, N. J. A., The orchard problem. Geometriae Dedicata (1974), 397-424.

    [Er97f] Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10.

@[expose] public sectionopen Filteropen scoped Topology EuclideanGeometrynamespace Erdos669

The set of lines in $\mathbb{R}^2$ containing at least $k$ points of $S$. It is the analogue of EuclideanGeometry.linesWithPointsFor, which asks for exactly $k$ points. Only lines spanned by two distinct points of $S$ are counted, so the definition is meant for $k \geq 2$.

noncomputable def linesWithAtLeastPointsFor (k : ℕ) (S : Set ℝ²) : Set (AffineSubspace ℝ ℝ²) := let determined_lines := { affineSpan ℝ {p, q} | (p ∈ S) (q ∈ S) (_ : p ≠ q) } { L ∈ determined_lines | k ≤ (↑L ∩ S).ncard }

The set of numbers of distinct lines through at least $k$ points, taken over all sets of $n$ points in $\mathbb{R}^2$.

noncomputable def lineCountsAtLeast (k n : ℕ) : Set ℕ := {m | ∃ S : Finset ℝ², S.card = n ∧ (linesWithAtLeastPointsFor k (S : Set ℝ²)).ncard = m}

The set of numbers of distinct lines through exactly $k$ points, taken over all sets of $n$ points in $\mathbb{R}^2$.

noncomputable def lineCountsExactly (k n : ℕ) : Set ℕ := {m | ∃ S : Finset ℝ², S.card = n ∧ (EuclideanGeometry.linesWithPointsFor k (S : Set ℝ²)).ncard = m}

A set of lines, each spanned by two points of S, has at most S.card ^ 2 elements.

S:Finset ℝ²T:Set (AffineSubspace ℝ ℝ²)hT:∀ L ∈ T, ∃ p ∈ S, ∃ q ∈ S, line[ℝ, p, q] = Lhfin:(↑S ×ˢ ↑S).Finitehcard:(↑S ×ˢ ↑S).ncard = S.card ^ 2hsub:T ⊆ (fun pq ↦ line[ℝ, pq.1, pq.2]) '' ↑S ×ˢ ↑S⊢ T.ncard ≤ S.card ^ 2 All goals completed! 🐙

The counts are bounded: a line through two or more points of an $n$-point set is spanned by an ordered pair of its points, and there are at most $n^2$ ordered pairs. The set is also nonempty, since $n$-point sets exist, so the sSup in Erdos669.maxLinesAtLeast is attained.

@[category test, AMS 52] theorem lineCountsAtLeast_bddAbove (k n : ℕ) : BddAbove (lineCountsAtLeast k n) := k:ℕn:ℕ⊢ BddAbove (lineCountsAtLeast k n) k:ℕn:ℕ⊢ n ^ 2 ∈ upperBounds (lineCountsAtLeast k n) k:ℕS:Finset ℝ²⊢ (linesWithAtLeastPointsFor k ↑S).ncard ≤ S.card ^ 2 k:ℕS:Finset ℝ²⊢ ∀ L ∈ linesWithAtLeastPointsFor k ↑S, ∃ p ∈ S, ∃ q ∈ S, line[ℝ, p, q] = L k:ℕS:Finset ℝ²p:ℝ²hp:p ∈ ↑Sq:ℝ²hq:q ∈ ↑S⊢ ∃ p_1 ∈ S, ∃ q_1 ∈ S, line[ℝ, p_1, q_1] = line[ℝ, p, q] All goals completed! 🐙

The same bound for lines through exactly $k$ points, so the sSup in Erdos669.maxLinesExactly is attained as well.

@[category test, AMS 52] theorem lineCountsExactly_bddAbove (k n : ℕ) : BddAbove (lineCountsExactly k n) := k:ℕn:ℕ⊢ BddAbove (lineCountsExactly k n) k:ℕn:ℕ⊢ n ^ 2 ∈ upperBounds (lineCountsExactly k n) k:ℕS:Finset ℝ²⊢ (EuclideanGeometry.linesWithPointsFor k ↑S).ncard ≤ S.card ^ 2 k:ℕS:Finset ℝ²⊢ ∀ L ∈ EuclideanGeometry.linesWithPointsFor k ↑S, ∃ p ∈ S, ∃ q ∈ S, line[ℝ, p, q] = L k:ℕS:Finset ℝ²p:ℝ²hp:p ∈ ↑Sq:ℝ²hq:q ∈ ↑S⊢ ∃ p_1 ∈ S, ∃ q_1 ∈ S, line[ℝ, p_1, q_1] = line[ℝ, p, q] All goals completed! 🐙

A line through exactly $k$ points of $S$ is a line through at least $k$ points of $S$.

@[category test, AMS 52] theorem linesWithPointsFor_subset_linesWithAtLeastPointsFor (k : ℕ) (S : Set ℝ²) : EuclideanGeometry.linesWithPointsFor k S ⊆ linesWithAtLeastPointsFor k S := k:ℕS:Set ℝ²⊢ EuclideanGeometry.linesWithPointsFor k S ⊆ linesWithAtLeastPointsFor k S k:ℕS:Set ℝ²L:AffineSubspace ℝ ℝ²hL:L ∈ {x | ∃ p ∈ S, ∃ q ∈ S, ∃ (_ : p ≠ q), line[ℝ, p, q] = x}hk:(↑L ∩ S).ncard = k⊢ L ∈ linesWithAtLeastPointsFor k S All goals completed! 🐙

$F_k(n)$: the largest number of distinct lines passing through at least $k$ of the points, over all sets of $n$ points in $\mathbb{R}^2$. This is the least $m$ such that any $n$ points have at most $m$ such lines. See Erdos669.lineCountsAtLeast_bddAbove.

noncomputable def maxLinesAtLeast (k n : ℕ) : ℕ := sSup (lineCountsAtLeast k n)

$f_k(n)$: the largest number of distinct lines passing through exactly $k$ of the points, over all sets of $n$ points in $\mathbb{R}^2$. This is the least $m$ such that any $n$ points have at most $m$ such lines. See Erdos669.lineCountsExactly_bddAbove.

noncomputable def maxLinesExactly (k n : ℕ) : ℕ := sSup (lineCountsExactly k n)def erdos_669.parts.i.answer : ℕ → Option ℝ := sorry

Let $F_k(n)$ be minimal such that for any $n$ points in $\mathbb{R}^2$ there exist at most $F_k(n)$ many distinct lines passing through at least $k$ of the points, and $f_k(n)$ similarly but with lines passing through exactly $k$ points.

Estimate $f_k(n)$ and $F_k(n)$ - in particular, determine $\lim F_k(n)/n^2$ and $\lim f_k(n)/n^2$.

This part asks for $\lim F_k(n)/n^2$ for $k \geq 3$ (the case $k = 2$ is trivial). The original question [Er97f, Problem 16] asks for the limits "if they exist", so the answer allows nonexistence: the answer at $k$ is some x if the limit exists and equals $x$, and none otherwise.

@[category research open, question value, AMS 52] theorem erdos_669.parts.i : ∀ k : ℕ, 3 ≤ k → ∀ x : ℝ, erdos_669.parts.i.answer k = some x ↔ Tendsto (fun n : ℕ => (maxLinesAtLeast k n : ℝ) / (n : ℝ) ^ 2) atTop (𝓝 x) := ⊢ ∀ (k : ℕ), 3 ≤ k → ∀ (x : ℝ), i.answer k = some x ↔ Tendsto (fun n ↦ ↑(maxLinesAtLeast k n) / ↑n ^ 2) atTop (𝓝 x) All goals completed! 🐙def erdos_669.parts.ii.answer : ℕ → Option ℝ := sorry

Let $F_k(n)$ be minimal such that for any $n$ points in $\mathbb{R}^2$ there exist at most $F_k(n)$ many distinct lines passing through at least $k$ of the points, and $f_k(n)$ similarly but with lines passing through exactly $k$ points.

Estimate $f_k(n)$ and $F_k(n)$ - in particular, determine $\lim F_k(n)/n^2$ and $\lim f_k(n)/n^2$.

This part asks for $\lim f_k(n)/n^2$ for $k \geq 3$ (the case $k = 2$ is trivial). The original question [Er97f, Problem 16] asks for the limits "if they exist", so the answer allows nonexistence: the answer at $k$ is some x if the limit exists and equals $x$, and none otherwise.

@[category research open, question value, AMS 52] theorem erdos_669.parts.ii : ∀ k : ℕ, 3 ≤ k → ∀ x : ℝ, erdos_669.parts.ii.answer k = some x ↔ Tendsto (fun n : ℕ => (maxLinesExactly k n : ℝ) / (n : ℝ) ^ 2) atTop (𝓝 x) := ⊢ ∀ (k : ℕ), 3 ≤ k → ∀ (x : ℝ), ii.answer k = some x ↔ Tendsto (fun n ↦ ↑(maxLinesExactly k n) / ↑n ^ 2) atTop (𝓝 x) All goals completed! 🐙

Trivially $f_k(n)\leq F_k(n)$.

k:ℕn:ℕS:Finset ℝ²hS:S.card = nhfin:(linesWithAtLeastPointsFor k ↑S).Finite⊢ (EuclideanGeometry.linesWithPointsFor k ↑S).ncard ≤ maxLinesAtLeast k n All goals completed! 🐙

$f_2(n)=F_2(n)=\binom{n}{2}$.

@[category research solved, AMS 52] theorem erdos_669.variants.k_two (n : ℕ) : maxLinesExactly 2 n = n.choose 2 ∧ maxLinesAtLeast 2 n = n.choose 2 := n:ℕ⊢ maxLinesExactly 2 n = n.choose 2 ∧ maxLinesAtLeast 2 n = n.choose 2 All goals completed! 🐙

The problem with $k=3$ is the classical 'Orchard problem' of Sylvester. Burr, Grünbaum, and Sloane [BGS74] have proved that $$f_3(n)=\frac{n^2}{6}-O(n)$$ and $$F_3(n)=\frac{n^2}{6}-O(n).$$

This is the statement for $f_3$.

@[category research solved, AMS 52] theorem erdos_669.variants.burr_grunbaum_sloane_exactly : (fun n : ℕ => (maxLinesExactly 3 n : ℝ) - (n : ℝ) ^ 2 / 6) =O[atTop] (fun n : ℕ => (n : ℝ)) := ⊢ (fun n ↦ ↑(maxLinesExactly 3 n) - ↑n ^ 2 / 6) =O[atTop] fun n ↦ ↑n All goals completed! 🐙

The problem with $k=3$ is the classical 'Orchard problem' of Sylvester. Burr, Grünbaum, and Sloane [BGS74] have proved that $$f_3(n)=\frac{n^2}{6}-O(n)$$ and $$F_3(n)=\frac{n^2}{6}-O(n).$$

This is the statement for $F_3$.

@[category research solved, AMS 52] theorem erdos_669.variants.burr_grunbaum_sloane_atLeast : (fun n : ℕ => (maxLinesAtLeast 3 n : ℝ) - (n : ℝ) ^ 2 / 6) =O[atTop] (fun n : ℕ => (n : ℝ)) := ⊢ (fun n ↦ ↑(maxLinesAtLeast 3 n) - ↑n ^ 2 / 6) =O[atTop] fun n ↦ ↑n All goals completed! 🐙

There is a trivial upper bound of $F_k(n) \leq \binom{n}{2}/\binom{k}{2}$.

@[category research solved, AMS 52] theorem erdos_669.variants.upper_bound (k n : ℕ) (hk : 2 ≤ k) : (maxLinesAtLeast k n : ℝ) ≤ (n.choose 2 : ℝ) / (k.choose 2 : ℝ) := k:ℕn:ℕhk:2 ≤ k⊢ ↑(maxLinesAtLeast k n) ≤ ↑(n.choose 2) / ↑(k.choose 2) All goals completed! 🐙

There is a trivial upper bound of $F_k(n) \leq \binom{n}{2}/\binom{k}{2}$, and hence $$\lim F_k(n)/n^2 \leq \frac{1}{k(k-1)}.$$ See also 101.

Here the limit is assumed to exist and is called L.

@[category research solved, AMS 52] theorem erdos_669.variants.limit_le (k : ℕ) (hk : 2 ≤ k) (L : ℝ) (hL : Tendsto (fun n : ℕ => (maxLinesAtLeast k n : ℝ) / (n : ℝ) ^ 2) atTop (𝓝 L)) : L ≤ 1 / ((k : ℝ) * ((k : ℝ) - 1)) := k:ℕhk:2 ≤ kL:ℝhL:Tendsto (fun n ↦ ↑(maxLinesAtLeast k n) / ↑n ^ 2) atTop (𝓝 L)⊢ L ≤ 1 / (↑k * (↑k - 1)) All goals completed! 🐙end Erdos669