For k≥3 and sufficiently large n, the maximum number of points in an n×n grid with no k+1 collinear is exactly kn.
On subsets of lattice cubes avoiding affine and spherical degeneracies
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
For integers $1 < k < d-1$ and $r \ge k+2$, we establish new lower bounds on the maximum number of points in $[n]^d$ such that no $r$ lie in a $k$-dimensional affine (or linear) subspace. These bounds improve on earlier results of Sudakov-Tomon and Lefmann. Further, we provide a randomised construction for the no-four-on-a-circle problem posed by Erd\H{o}s and Purdy, improving Thiele's bound. We also consider the random construction in higher dimensions, and improve the bound of Suk and White for $d \geq 4$. In each case, we apply the deletion method, using results from number theory and incidence geometry to solve the associated counting problems.
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Stability versions of the inverse theorem for subset sums are proved: n-element positive real sets with at most binom(n+1,2)+1+M subset sums are characterized for M up to n-4, and sets with O(n^2) subset sums are characterized up to constants.
A random construction produces a no-three-collinear set in Z squared with Omega(n over square root of log n) points inside [n] squared, improving the prior lower bound by a square root of log n factor.
AlphaEvolve rediscovered best-known solutions for most of 67 tested math problems and found improved solutions in several cases using LLM-guided evolutionary search.
citing papers explorer
-
No-$(k+1)$-in-line problem for $k \geqslant 3$
For k≥3 and sufficiently large n, the maximum number of points in an n×n grid with no k+1 collinear is exactly kn.
-
Sets with Few Subset Sums
Stability versions of the inverse theorem for subset sums are proved: n-element positive real sets with at most binom(n+1,2)+1+M subset sums are characterized for M up to n-4, and sets with O(n^2) subset sums are characterized up to constants.
-
A note on the extensible no-three-in-line problem
A random construction produces a no-three-collinear set in Z squared with Omega(n over square root of log n) points inside [n] squared, improving the prior lower bound by a square root of log n factor.
-
Mathematical exploration and discovery at scale
AlphaEvolve rediscovered best-known solutions for most of 67 tested math problems and found improved solutions in several cases using LLM-guided evolutionary search.