Economical lattice coverings by determined segments

Abstract

For fixed $d\ge 2$, let ${\tau }_d(n)$ be the minimum size of a set $S\subseteq \{0,\dots ,n{\}}^d$ such that the affine lines determined by pairs of distinct points of $S$ cover the grid. Let ${\sigma }_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 ${\tau }_d(n)$ is of order between ${\Omega }_d(n^{{\alpha }_d})$ and $O_d(n^{{\alpha }_d}\log n)$, where ${\alpha }_d=\frac{d(d-1)}{2d-1}$, and asked whether the logarithm term is necessary. We prove that $$c_d{n}^{{\alpha }_d}\le {\tau }_d(n)\le {\sigma }_d(n)\le C_d{n}^{{\alpha }_d}$$ for every fixed $d\ge 2$, thereby resolving Alon's problem in a stronger form.

arXiv comment12 pages