2026/08/04 by Gennian Ge, Yang Shu, Zixiang Xu
Mathematics · #math.CO
12 pages
arxiv created 2026/08/04 · arxiv updated 2026/08/05
For fixed d≥ 2, let τd(n) be the minimum size of a set S⊆\0,…,n\d such that the affine lines determined by pairs of distinct points of S cover the grid. Let σd(n) be the analogous minimum when every grid point must lie on the closed segment joining two distinct points of S. A celebrated result of Alon [GAFA, 1991] proved that τd(n) is of order between Ωd(nαd) and Od(nαdlog n), where αd=(d(d-1))/(2d-1), and asked whether the logarithm term is necessary. We prove that cd nαd≤τd(n)≤σd(n)≤ Cd nαd for every fixed d≥ 2, thereby resolving Alon's problem in a stronger form.