Generalized orchard problem: determine $\lim F_k(n)/n^2$ and $\lim f_k(n)/n^2$ for $k$-rich lines (Erdős #669)
Statement
For $n$ points in $\mathbb{R}^2$, let $F_k(n)$ be minimal such that there are always at most $F_k(n)$ distinct lines passing through at least $k$ of the points, and let $f_k(n)$ be defined the same way but counting lines passing through exactly $k$ of the points. Estimate $f_k(n)$ and $F_k(n)$; in particular, determine the limits $$\lim_{n\to\infty}\frac{F_k(n)}{n^2}\qquad\text{and}\qquad\lim_{n\to\infty}\frac{f_k(n)}{n^2}.$$
Acceptance. FULLY RESOLVES: determine both limits $\lim_n F_k(n)/n^2$ and $\lim_n f_k(n)/n^2$ for all $k$ (or determine the exact asymptotic order of $F_k(n)$ and $f_k(n)$), with proof — machine-checkable preferred, else a complete written proof. ADVANCES: for a fixed $k\ge4$, prove a lower or upper bound on $\lim_n F_k(n)/n^2$ or $\lim_n f_k(n)/n^2$ that strictly improves the trivial bound $\tfrac{1}{k(k-1)}$ stated in the background, with proof; OR extend the exact extremal values (OEIS A003035 / A006065 / A008997) to new record $n$ with a reproducible search and an optimality certificate; OR give an improved explicit construction for a fixed $k$. Deliver the proof, or the search code plus the point configurations and certified extremal counts.
Background
Posed by Erdős [Er97f]; listed as open on erdosproblems.com/669 (fetched 2026-07-13, status 'open', tagged 'geometry'). No prize. Trivially $f_k(n)\le F_k(n)$, and $f_2(n)=F_2(n)=\binom{n}{2}$. The case $k=3$ is the classical Orchard problem of Sylvester: Burr–Grünbaum–Sloane [BGS74] proved $f_3(n)=\tfrac{n^2}{6}-O(n)$ and $F_3(n)=\tfrac{n^2}{6}-O(n)$. For general $k$ there is a trivial upper bound $F_k(n)\le\binom{n}{2}/\binom{k}{2}$, and hence $\lim_n F_k(n)/n^2\le\tfrac{1}{k(k-1)}$; the corresponding leading constants for $k\ge4$ are not known. Extremal small-$n$ values are tabulated in OEIS: A003035 (maximal number of 3-point 'rows', the orchard problem), A006065 ($k=4$ rows), and A008997 ($k=5$ rows). The problem generalises Erdős #101 (erdosproblems.com/101) and is a close sibling of the venue's Erdős #588, which instead imposes a no-$(k+1)$-collinear restriction and asks whether that restricted count is $o(n^2)$ for $k\ge4$. Attacker's tool: computational search for extremal point configurations (grids and cubic-curve / elliptic-curve group-law constructions) to extend the OEIS tables and pin down the leading constants, combined with incidence-geometry upper bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #669 (T. F. Bloom) | website |
| REF-02 | OEIS A003035 — Maximal number of 3-tree rows in the n-tree orchard problem | website |
| REF-03 | OEIS A006065 — Maximal number of 4-tree rows in the n-tree orchard problem | website |
| REF-04 | OEIS A008997 — Orchard problem with 5 trees in a row | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.