No three in line: more than 1.5n points in the n × n grid

How many points of an $n \times n$ grid can be chosen with no three on a line? At most $2n$, since each row holds at most two, and $2n$ is achievable for every $n$ from 2 to 74. For large $n$, though, the best construction, from 1975, gives only about $1.5n$, while a heuristic predicts about $1.81n$; the task is to beat $1.5n$ by a constant factor.

Problem

Let $t(n)$ be the largest size of a set $S \subseteq \{1, \dots, n\}^2$ with no three points on a common line. The pigeonhole principle gives $t(n) \le 2n$, and a 1975 construction gives $t(n) \ge (\tfrac{3}{2} - o(1))\,n$ [1].

Task. Give an explicit family of no-three-in-line sets with more than $1.8n$ points in the $n \times n$ grid, for arbitrarily large $n$. Any family with at least $(\tfrac{3}{2} + c)\,n$ points, for a constant $c > 0$, would already improve the asymptotic lower bound.

Background

Special cases go back to Dudeney's puzzles more than a century ago. Hall, Jackson, Sudbery and Wild obtained $(\tfrac{3}{2} - o(1))\,n$ points with a construction modulo a prime [1], and nothing better is known asymptotically. Guy and Kelly gave a heuristic suggesting that $t(n) \sim c\,n$ with $c = (2\pi^2/3)^{1/3} \approx 1.87$ [2]; in 2004 Gábor Ellmann found an error in their derivation, and the corrected heuristic gives $c = \pi/\sqrt{3} \approx 1.814$ [3]. Not everyone believes the heuristic: Ben Green's list of open problems (Problem 72) records his suspicion that $\tfrac{3}{2}$ is optimal.

What is known

• $t(n) = 2n$ for every $2 \le n \le 74$ and for $n = 76$, according to Achim Flammenkamp's record page (updated 15 October 2026), with several of the largest cases found in 2026 [3].
• Asymptotically, the best lower bound is $(\tfrac{3}{2} - o(1))\,n$ [1].
• For the analogous no-$(k+1)$-in-line problem with $k \ge 3$, the maximum is exactly $kn$ for large $n$ (Ghosal, Goenka, Grebennikov, Keevash, Kwan and Pham, 2026), but their method does not reach $k = 2$ [4].
• formal-conjectures states Green's question (whether $2n$ points become impossible for all large $n$) in Lean as green_72 in GreensOpenProblems/72.lean, with the opposite question as a variant.

What would count as progress

• A program that, given $m$, returns some $n$ with $m \le n \le 2m$ and more than $1.8n$ points of $\{1, \dots, n\}^2$ with no three collinear. Collinearity among $N$ points can be checked in $O(N^2 \log N)$ time by sorting slopes from each point.
• Epoch scores submissions with its own verifier, which calls such a function solution(min_n) for increasing lower bounds and requires strictly increasing $n$.
• As Epoch warns, a construction with $1.5n + C$ points can pass finitely many tests without improving the ratio; the real goal is a family with a provable constant-factor gain over $1.5n$.

References

1. R. R. Hall, T. H. Jackson, A. Sudbery and K. Wild, Some advances in the no-three-in-line problem, J. Combin. Theory Ser. A 18 (1975), 336–341. doi:10.1016/0097-3165(75)90043-6
2. R. K. Guy and P. A. Kelly, The no-three-in-line problem, Canad. Math. Bull. 11 (1968), 527–531. doi:10.4153/CMB-1968-062-3
3. A. Flammenkamp, The no-three-in-line problem (record page). wwwhomes.uni-bielefeld.de/achim/no3in/readme.html
4. A. Ghosal, R. Goenka, A. Grebennikov, P. Keevash, M. Kwan and H. T. Pham, No-$(k+1)$-in-line problem for $k \ge 3$, 2026. arXiv:2607.05255

Source

Imported from FrontierMath: Open Problems, no-three-in-line, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.