Randomised algebraic constructions for the no-\((k+1)\)-in-line problem

A set of points in the plane is said to be in general position if no three of the points lie on a common line. It is a celebrated, long-standing open problem to determine the maximum number of grid points of an \(n \times n\) grid so that the points are in general position. This problem was first posed more than 100 years ago and has remained open ever since.

A natural generalization of this problem for \(k\geq 2\), the no-\((k+1)\)-in-line problem seeks the maximum number of points (denoted by \(f_k(n)\)) that can be selected from an \(n \times n\) grid such that no \(k+1\) of them are collinear. This generalized problem was recently resolved in the case \(k\) is not too small compared to \(n\), as the present authors proved in a breakthrough paper that the upper bound \(kn\) can be attained, provided that \(k>C\sqrt{n\log{n}}\) for an absolute constant \(C\). In this follow-up paper, the authors
extend the range of \(k = k(n)\) where \(f_k(n) = (1 - o(1))kn\) holds. More precisely, they show that \(\left(1-\frac{2}{k}\right)kn \leq f_k(n)\leq kn\) and \(\left(1-\frac{3}{k}\right)kn \leq f_k(n)\leq kn\) hold for every even \(k\) and odd \(k\), respectively, provided that \(n\) is large enough. This is asymptotically tight as \(k\to \infty\). Previously, only \(f_k(n)=\Omega(kn)\) was known due to Lefmann. They present further improvements on the lower bounds for constant values of \(k\) when \(k<23\) holds. All these bounds are based on randomised algebraic constructions.

We remark that since then these results have been extended significantly by other authors; in fact the problem has been resolved for all \(k\geq 3\) and sufficiently large \(n\). Nevertheless, this paper is an important step forward in this line of research.