Randomised algebraic constructions for the no- ( k + 1 ) (k+1) -in line problem
Benedek Kovács, Zoltán Lóránt Nagy, Dávid R. Szabó · 2025
Read Randomised algebraic constructions for the no- ( k + 1 ) (k+1) -in line problem by Benedek Kovács, Zoltán Lóránt Nagy, Dávid R. Szabó (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-07632.txt.
Introduction
Benedek Kovács, Zoltán Lóránt Nagy, and Dávid Szabó revisit a century-old puzzle about points and lines, in a 2025 mathematics paper. The problem asks how many points can be picked from a square grid so that no straight line passes through a fixed number of them. The simplest case dates back more than a hundred years and is still open.
Recent work settled the problem when the forbidden count is large relative to the grid. The new paper pushes the other direction. Using randomized algebraic constructions, the authors prove lower bounds that come within a small fraction of the absolute upper limit, for both even and odd cases, once the grid is large enough. The bounds are nearly tight as the forbidden count grows. They also improve the known bounds for small fixed values of the count, below twenty-three.
Catalog record
| CREATOR | Benedek Kovács, Zoltán Lóránt Nagy, Dávid R. Szabó |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-07632
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Randomised algebraic constructions for the no- ( k + 1 ) (k+1) -in line problem Benedek Kovács, Zoltán Lóránt Nagy, Dávid R. Szabó Abstract The no- ( k + 1 ) (k+1) -in line problem seeks the maximum number of points that can be selected from an n × n n\times n square lattice such that no k + 1 k+1 of them are collinear. The problem was first posed more than 100 100 years ago for the special case k = 2 k=2 and has remained open ever since. The general problem was recently resolved in the case k k is not small compared to n n , as Kovács, Nagy and Szabó proved that the upper bound k n kn can be attained, provided that k > C n log n k>C\sqrt{n\log{n}} for an absolute constant C C . In this paper, we show that ( 1 − 2 k ) k n ≤ f k ( n ) ≤ k n \left(1-\tfrac{2}{k}\right)kn\leq f_{k}(n)\leq kn and ( 1 − 3 k ) k n ≤ f k ( n ) ≤ k n \left(1-\tfrac{3}{k}\right)kn\leq f_{k}(n)\leq kn hold for every even k k and odd k k , respectively, provided that n n is large enough. This is asymptotically tight as k → ∞ k\to\infty . Previously, only f k ( n ) = Ω ( k n ) f_{k}(n)=\Omega(kn) was known due to Lefmann. We present further improvements on the lower bounds for constant values of k k when k < 23 k<23 holds. All these bounds are based on randomised algebraic constructions. 1 Introduction 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. Following the riddle of Dudeney concerning the placement of 16 chess pieces on the chessboard in general position, the no-three-in-line problem was formulated, asking to determine the maximum number of grid points of an n\times n grid so that the points are in general position. For the history and background of this celebrated problem, we refer to the excellent book of Brass, Moser, and Pach [ Brass2005 ] and that of Eppstein [ Eppstein:2018 ] . It is easy to see using the pigeonhole principle that 2n is an upper bound. This theoretical upper bound can be attained when n is small [ anderson1979update , flammenkamp1998progress ] . Surprisingly, although it has been studied extensively, no progress has been reported concerning the lower bound, up to our best knowledge, since the result of Hall, Jackson, Sudbery, and Wild [ hall1975some ] . They showed fifty years ago that one can choose 1.5n-o(n) points in general position from the n\times n grid. Several conjectures were formulated concerning the asymptotical value of the answer to the no-three-in-line problem, and it is far from clear whether it is 1.5n , 2n or somewhere in between [ Brass2005 , Eppstein:2018 , green100 , Guy/Kelly:1968 ] . Our main focus is to continue the investigation of the generalization of this problem. Definition 1.1 . Let f_{k}(n) denote the maximum size of a point set chosen from the points of the n\times n grid {\mathcal{G}}=[1,n]\times[1,n] in which at most k points lie on any line. Using this notation, the aforementioned cornerstone result is the following. Theorem 1.2 (Hall, Jackson, Sudbery, and Wild [ hall1975some ] ) . 1.5n-o(n)\leq f_{2}(n)\leq 2n. Their construction relies on a well-chosen subset of the modular hyperbola \{xy\equiv c\pmod{p},(x,y)\in\mathbb{Z}^{2}\} where p denotes a prime number close to n/2 , and c is a nonzero \pmod{p} residue. This construction, which we call the HJSW construction for short, will play a central role in our paper and will be discussed in detail in Section 2 . Later Lefmann, using graph-theoretic tools, proved that for fixed k , f_{k}(n)=\Omega(kn) holds for the general case [ lefmann2012extensions ] . Here we note that actually, simply taking the disjoint union of \left\lfloor k/2\right\rfloor distinct constructions of HJSW type where p\in\left[\left(\frac{1}{2}-o(1)\right)n,\frac{1}{2}n\right] is fixed and c varies, we can obtain the following stronger observation for free from Theorem 1.2 . Proposition 1.3 (Multiplicativity) . Let k\geq 2 be a fixed integer. Then as n\to\infty , we have \displaystyle(\tfrac{3}{4}-o(1))\cdot kn \displaystyle\leq f_{k}(n), \displaystyle\text{ if\hskip 10.22217pt}2\mid k, \displaystyle\left(\tfrac{3}{4}-\tfrac{3}{4k}-o(1)\right)\cdot kn \displaystyle\leq f_{k}(n), \displaystyle\text{ if\hskip 10.22217pt}2\nmid k. However, the present authors were recently able to show much stronger results, as we determined the precise value of f_{k}(n) when k is not too small. Theorem 1.4 (Kovács, Nagy, Szabó [ kovacs2025settling ] ) . For every C>12.5 , there exists an integer N_{C} such that whenever n\geq N_{C} and k\geq C\sqrt{n\log n} , we have f_{k}(n)=kn. In this paper, we have two main objectives. First, we wish to extend the range of k=k(n) where f_{k}(n)=(1-o(1))kn holds. In this direction, our main result is the following. Theorem 1.5 . For every k\geq 2 , there exists N_{k} such that whenever n\geq N_{k} , we have \displaystyle kn-2n<\left(1-\frac{2}{k}+\frac{6}{k\sqrt{\pi k+14}}-\frac{2}{k(k+2)}\right)kn \displaystyle\leq f_{k}(n)\leq kn, \displaystyle\text{ if\hskip 10.22217pt}2\mid k, \displaystyle kn-3n<\left(1-\frac{3}{k}+\frac{10}{k\sqrt{\pi k+7}}-\frac{6}{k(k+1)}\right)kn \displaystyle\leq f_{k}(n)\leq kn, \displaystyle\text{ if\hskip 10.22217pt}2\nmid k. We prove a slightly stronger result in 3.11 . Note that for fixed k , Theorem 1.4 determines the exact value of f_{k}(n) for small values of n , while Theorem 1.5 gives a near-optimal estimate for all large enough values of n . While Theorem 1.2 and its consequence, 1.3 relied on a purely algebraic construction, namely the line intersection patterns of conics over a finite field, the recently proved exact result of Theorem 1.4 was essentially purely probabilistic in nature, as its construction was built from carefully constructed blockwise uniform random bipartite graphs. To obtain Theorem 1.5 , we apply the combination of the two techniques. 1.3 and the construction of Hall et al. [ hall1975some ] indicate that obtaining good lower bounds might depend on the parity of k . We investigate the case k=3 in detail, in addition to the cases when k is a small constant, and improve upon the previous general lower bound. Theorem 1.6 . f_{3}(n)\geq 1.973n for n sufficiently large. Theorem 1.7 . f_{k}(n)\geq(C_{k}-o(1))kn holds for k\in\{2,\dots,22\} with coefficients C_{k} presented in Table 1.1 . k C_{k} proof 2 \frac{3}{4} {}\approx{} 0.75000 § 2 [ hall1975some ] 3 \frac{26521}{40320} {}\approx{} 0.65776 § 4 \frac{3}{4} {}\approx{} 0.75000 § 3 5 \frac{41}{60} {}\approx{} 0.68333 § 3 6 \frac{59}{72} {}\approx{} 0.81944 § 4 7 \frac{171}{224} {}\approx{} 0.76339 § 3 8 \frac{109}{128} {}\approx{} 0.85156 § 3 k C_{k} proof 9 \frac{193}{240} {}\approx{} 0.80417 § 3 10 \frac{559}{640} {}\approx{} 0.87344 § 3 11 \frac{5}{6} {}\approx{} 0.83333 § 3 12 \frac{229}{256} {}\approx{} 0.89453 § 3 13 \frac{4969}{5824} {}\approx{} 0.85319 § 3 14 \frac{1621}{1792} {}\approx{} 0.90458 § 3 15 \frac{13379}{15360} {}\approx{} 0.87103 § 3 k C_{k} proof 16 \frac{11255}{12288} {}\approx{} 0.91593 § 3 17 \frac{34559}{39168} {}\approx{} 0.88233 § 3 18 \frac{2837}{3072} {}\approx{} 0.92350 § 3 19 \frac{43457}{48640} {}\approx{} 0.89344 § 3 20 \frac{4763}{5120} {}\approx{} 0.93027 § 3 21 \frac{17775}{19712} {}\approx{} 0.90173 § 3 22 \frac{42307}{45056} {}\approx{} 0.93899 § 3 Table 1.1 : The values of C_{k} , together with the Section number where the corresponding bound is proved. In this statement, the