No- ( k + 1 ) (k+1) -in-line problem for large constant k k
Alexandr Grebennikov and Matthew Kwan · 2025
Read No- ( k + 1 ) (k+1) -in-line problem for large constant k k by Alexandr Grebennikov and Matthew Kwan (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-2510-17743.txt.
Introduction
Alexandr Grebennikov and Matthew Kwan solve a grid puzzle about points and lines. How many points can sit in a square grid with few on any line? Each straight line may hold at most k points, where k is fixed. Earlier work settled the question only for much larger k values.
For large constant k, the pair proves the best count is exactly k times n. Here n is the side length of the square grid. Their proof builds on recent work by three other researchers. It also borrows ideas from Jain and Pham. The same approach gives new bounds for higher-dimensional versions.
Catalog record
| CREATOR | Alexandr Grebennikov and Matthew Kwan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-17743
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
No- ( k + 1 ) (k+1) -in-line problem for large constant k k Thanks: Both authors are supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Alexandr Grebennikov and Matthew Kwan Abstract . How many points can be placed in an n × n n\times n grid so that every (affine) line contains at most k k points? We prove that for n ⩾ k ⩾ 10 37 n\geqslant k\geqslant 10^{37} the maximum number of points is exactly k n kn . Our proof builds on the recent work of Kovács, Nagy, and Szabó (who proved an analogous result when k k is at least about n log n \sqrt{n\log n} ), incorporating ideas of Jain and Pham. Using the same approach, we also obtain new bounds for higher-dimensional extensions of this problem. 1. Introduction The no-three-in-line problem, posed by Dudeney at the beginning of the 20th century [ 7 ] , asks for the maximum number of points that can be placed on an n\times n grid such that no three points are collinear. Despite significant attention over the years, the problem remains open: the best known upper bound 2n comes from the observation that each of the n horizontal lines can contain at most two points, while the best known lower bound (1.5-o(1))n comes from the modular hyperbola construction of Hall, Jackson, Sudbery, and Wild [ 17 ] . For more history and background, see for example the surveys by Brass, Moser, and Pach [ 5 ] and Eppstein [ 8 ] , and Green’s list of open problems [ 14 ] . Several different conjectures were made concerning the asymptotic behaviour of the answer to the no-three-in-line problem, including suggestions that it could be roughly 1.5n [ 14 ] , roughly 2n [ 5 ] , or somewhere in between [ 8 , 15 ] . For small values of n , examples attaining the trivial upper bound 2n are known [ 2 , 10 , 11 ] . A natural generalisation of this problem, first studied by Brass and Knauer [ 4 ] in a more general context, is to ask for the maximum size of a subset of the n\times n grid containing at most k points on each line. Denoting this maximum by f_{k}(n) , the trivial upper bound is f_{k}(n)\leqslant kn . Lefmann [ 25 , Proposition 2] proved that f_{k}(n)=\Omega(kn) for every k\geqslant 2 . Recently, Kovács, Nagy, and Szabó [ 24 ] showed that f_{k}(n)=kn for each k\geqslant C\sqrt{n\log n} (when C>12.5 and n is sufficiently large in terms of C ). They also noted [ 24 , Section 4] that, conditionally on some strong results about random regular graphs (i.e., the bipartite version of the Kim–Vu sandwich conjecture [ 21 ] ; see [ 3 , 12 , 22 ] for recent progress), their approach could yield an analogous statement for k of order at least \log n . We strengthen these results by proving that f_{k}(n)=kn for every n\geqslant k\geqslant K_{0} , for some absolute constant K_{0} (our proof gives K_{0}=10^{37} , but we did not attempt to optimise it). Theorem 1.1 . Let n,k be integers such that 10^{37}\leqslant k\leqslant n . Then there exists a subset S of the n\times n grid of size kn such that every line contains at most k points of S . In a different work, Kovács, Nagy, and Szabó [ 23 ] studied this problem in the regime when k is small compared to n , using randomised algebraic constructions. In particular, they demonstrated that f_{k}(n)\geqslant(k-3)n when n is sufficiently large in terms of k , and conjectured that f_{k}(n)=kn+o(n) when k=k(n)=\omega(1) and n\to\infty . Theorem 1.1 confirms this conjecture in a strong sense. Interestingly, all known linear-size constructions for the no-three-in-line problem are algebraic in nature (though there are random constructions [ 9 , 13 ] of size about n/\sqrt{\log n} ). In a related question, Green [ 14 ] asked whether every “large” no-three-in-line set reduces to an algebraic curve modulo some prime. Although Theorem 1.1 only gives no- (k+1) -in-line sets for large k , we remark that our constructions are purely probabilistic and do not exhibit any algebraic structure. 1.1. Proof ideas Let \mathcal{L} be the set of lines intersecting the n\times n grid in at least two points. For each line L\in\mathcal{L} , define its weight as w(L):=\frac{|[n]^{2}\cap L|}{n}\in[2/n,1]. The framework of Kovács, Nagy, and Szabó [ 24 ] allows us to reduce Theorem 1.1 to Theorem 1.2 below, which permits a 0.01k excess over the expected number of points on the lines that are not horizontal or vertical. Therefore, the main content of this paper is the proof of Theorem 1.2 (though, for the reader’s convenience, we also present a deduction of Theorem 1.1 in Section 5 ). Theorem 1.2 . Let n,k be integers such that 10^{36}\leqslant k\leqslant 0.9\cdot n . Then there exists a subset S\subseteq[n]^{2} that contains exactly k points on each horizontal and each vertical line, and at most k\cdot(w(L)+0.01) points on every other line L\in\mathcal{L} . Kovács, Nagy, and Szabó [ 24 ] were able to prove a result along the lines of Theorem 1.2 under the much stronger assumption that k is at least about \sqrt{n\log n} . They did this by choosing the desired point set randomly , using concentration inequalities to show that the number of points on each line is unlikely to deviate much from its expectation. This works when k grows sufficiently fast as a function of n but breaks down for constant k : the main issue is that a union bound over all lines becomes too inefficient. To overcome this issue, we build on ideas from the work of Jain and Pham [ 18 ] on optimal thresholds for Latin squares in random hypergraphs. Namely, we design an iterative subsampling procedure that uses the Lovász Local Lemma at each step, maintaining control over the number of points on each line (roughly speaking, we maintain tight control over the number of points on lines whose weight exceeds some threshold, gradually raising this threshold as the procedure continues and the light lines become increasingly unimportant). Moreover, at each step of the procedure, instead of constructing a single configuration of points, we construct a “spread” probability distribution over suitable configurations. We then use this spread property to show that a sample from the final distribution obtained from our procedure is likely to satisfy a certain Hall-type condition, which provides a subset containing exactly k points on each horizontal and each vertical line. 1.2. Higher dimensions A further generalisation of this problem, introduced by Brass and Knauer [ 4 ] , is to ask for the maximum size of a subset of the d -dimensional grid [n]^{d} that contains at most k points in each affine subspace of dimension t (where 1\leqslant t\leqslant d-1 ). Denoting this maximum by f_{k,d,t}(n) , the trivial upper bound is f_{k,d,t}(n)\leqslant kn^{d-t} . Brass and Knauer [ 4 , Lemma 8] proved that f_{k,d,t}(n)=\Omega(n^{d-t-(d(t+1))/k}) , which was slightly sharpened by Lefmann [ 25 , Lemma 2] to \Omega(n^{d-t-(t(d+1))/k}) . Later, Sudakov and Tomon [ 29 , Theorem 1.4]