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>Cnn for an absolute constant C. In this paper, we show that (1-2k) kn fₖ (n) kn and (1-3k) 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.