Open problem, Combinatorics and discrete mathematics, Geometry, posed 1917

No-three-in-line problem

Open

For each integer $n \ge 2$ , determine the maximum number $f(n)$ of lattice points that can be selected from the $n \times n$ grid $\{1, 2, \dots, n\}^2$ so that no three selected points are collinear on any line of any slope, and in particular determine whether $f(n) = 2n$ for all $n$ or whether $\lim_{n \to \infty} f(n)/n < 2$ .

Research frontier as of 2026

As of 2026, the asymptotic ratio $\lim_{n \to \infty} f(n)/n$ remains unknown, trapped between the 1975 Hall–Jackson–Sudbery–Wild algebraic lower bound $\frac{3}{2} = 1.5$ and the trivial pigeonhole upper bound $2$ . Computer searches (by Flammenkamp, Prellberg, Heule, and others) have found configurations of $2n$ points with no three in line for every $n \le 74$ , yet the number of symmetric $2n$ -point solutions decreases for larger $n$ , lending empirical support to the Guy–Kelly heuristic $f(n) \sim \frac{\pi}{\sqrt{3}} n \approx 1.8138n$ .

Best known results

For every $n \ge 2$ , $(\frac{3}{2} - o(1))n \le f(n) \le 2n$ (Hall, Jackson, Sudbery, and Wild, 1975).
Exact equality $f(n) = 2n$ holds for all $2 \le n \le 74$ by explicit computer-constructed configurations.

Tools and where they stop

Tool	Achieved	Where it stops
Algebraic curves over $\mathbb{F}_p$ (Erdős, Hall–Jackson–Sudbery–Wild)	Uses Bézout's theorem over $\mathbb{F}_p$ —that a line intersects an irreducible conic such as $y \equiv x^2 \pmod p$ or $xy \equiv k \pmod p$ in at most $2$ points modulo $p$ , hence at most $2$ points in $\mathbb{Z}^2$ —to build $(3/2 - o(1))n$ points.	Curves of degree $d \ge 3$ over $\mathbb{F}_p$ can intersect a line in $3$ or more points, while tiling multiple shifted conics creates collinear triples across different tiles once density exceeds $3n/2$ .

Open questions

Does there exist an integer $n \ge 2$ for which $f(n) < 2n$ ?
Does the limit $\lim_{n \to \infty} f(n)/n$ exist, and is it strictly less than $2$ (for instance $\pi/\sqrt{3} \approx 1.8138$ )?

References

Klaus Friedrich Roth (with an appendix by Paul Erdős) (1951). On a problem of formal logic · DOI:10.1112/jlms/s1-26.3.198
Richard K. Guy, Patrick A. Kelly (1968). The no-three-in-line problem · DOI:10.4153/CMB-1968-062-3
R. R. Hall, T. H. Jackson, A. Sudbery, K. Wild (1975). Some advances in the no-three-in-line problem · DOI:10.1016/0097-3165(75)90043-6