No-$(k+1)$-in-line problem for large constant $k$

Abstract

How many points can be placed in an $n\times n$ grid so that every (affine) line contains at most $k$ points? We prove that for $n\ge k\ge 10^{37}$ the maximum number of points is exactly $kn$. Our proof builds on the recent work of Kovács, Nagy, and Szabó (who proved an analogous result when $k$ is at least about $\sqrt{n\log n}$), incorporating ideas of Jain and Pham. Using the same approach, we also obtain new bounds for higher-dimensional extensions of this problem.

13 pages