/-
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.
-/modulepublicimportFormalConjecturesUtil
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$.
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.
$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.
$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.
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.
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.
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).$$
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).$$