Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 669

claims/: The 2 claim pages of Problem 669, one per claimant's result; the problem's standing derives from them.

Statement. 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$ .

Status. Open. The site labels the problem OPEN (page last edited 27 December 2025). The instance $k=3$ is settled by the accepted partial claims on Burr, Grünbaum and Sloane's construction and Green and Tao's exact bound.

Source. erdosproblems.com/669, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #669, https://www.erdosproblems.com/669.

References.

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

Formalization. None recorded.

Current assessment

Trivially $f_k(n)\le F_k(n)$ and $f_2(n)=F_2(n)=\binom n2$ . A line through at least $k$ of the points contains at least $\binom k2$ of the $\binom n2$ pairs, and no pair lies on two lines, so $F_k(n)\le\binom n2/\binom k2$ and $\limsup F_k(n)/n^2\le1/(k(k-1))$ . The case $k=3$ is Sylvester's orchard problem. Burr, Grünbaum and Sloane's cubic-curve construction, with the pair count, gives $f_3(n)=n^2/6-O(n)$ and $F_3(n)=n^2/6-O(n)$ , so both limits equal $1/6$ for $k=3$ (claim page). Green and Tao's upper bound, with that construction, gives $f_3(n)=\lfloor n(n-3)/6\rfloor+1$ for all large $n$ (claim page). For $k\ge4$ the cited sources give only the trivial upper bound, so the limits for $k\ge4$ are open as far as they show. The site also points to Problem 101. The literature search behind this account covered the site's page, the two papers above and the formal-conjectures repository.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (18)

Burr, Grünbaum and Sloane's orchard bound for k = 3 Green and Tao's exact orchard bound for large n problems/discrete_geometry/E0669/claims Discrete and Convex Geometry discrete_geometry/burr_1974_orchard_problem Remark (4) (p. 419): conjecture that t(p) = 1 + floor(p(p-3)/6) for p other than 7, 11, 16, 19 Theorem 1 (p. 397): t(p) >= 1 + floor(p(p-3)/6) for every p >= 3, by points on a cubic curve Theorem 2 (p. 403): t(7) >= 6, t(11) >= 16, t(16) >= 37 and t(19) >= 52 Theorem 3 (p. 409): t(p) <= floor((p/3) floor((p-1)/2)) for every p >= 3 Theorem 4 (p. 409): t(p) <= floor((binom(p,2) - ceil(3p/7))/3) for every p >= 3 Theorem 5 (p. 409): an (8,8)-arrangement is impossible, so t(8) = 7 Theorem 6 (p. 410): a (10,13)-arrangement is impossible, so t(10) = 12 Theorem 7 (p. 412): a (12,20)-arrangement is impossible, so t(12) = 19 Theorem 8 (p. 414): a (14,28)-arrangement is impossible, so t(14) <= 27 discrete_geometry/green_2013_sets_defining_few_ordinary_lines Proposition 2.6 (pp. 18-19): Sylvester's cubic-curve examples have floor(n(n-3)/6)+1 three-point lines Theorem 1.3 (p. 3): at most floor(n(n-3)/6)+1 lines through exactly three of n points, for large n Theorem 1.5 (p. 6): full structure theorem for sets with at most Kn ordinary lines

Graph