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

The no-(k+1)-in line problem seeks the maximum number of points that can be selected from an n × n square lattice such that no $k+1$ of them are collinear. The problem was first posed more than $100$ years ago for the special case $k=2$ and has remained open ever since. The general problem was recently resolved in the case k is not small compared to n, as Kovács, Nagy and Szabó proved that the upper bound $kn$ can be attained, provided that k>C√nlogn for an absolute constant C. In this paper, we show that (1-2/k)kn ≤ fₖ(n)≤ kn and (1-3/k)kn ≤ fₖ(n)≤ kn hold for every even k and odd k, respectively, provided that n is large enough. This is asymptotically tight as k→ ∞. Previously, only fₖ(n)=Ω(kn) was known due to Lefmann. We 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.