2025/08/11 by Benedek Kovács, Zoltán Lóránt Nagy, Kovács, Benedek +3 · 2 citations
#math.CO
paper · pdf · doi:10.19086/aic.2026.7
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-\tfrac2k)kn ≤ fk(n)≤ kn and (1-\tfrac3k)kn ≤ fk(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 fk(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.