Economical lattice coverings by determined segments

Abstract

For fixed $d\geq 2$, let $\tau_d(n)$ be the minimum size of a set $S\subseteq\{0,\ldots,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}\leq\tau_d(n)\leq\sigma_d(n)\leq C_d n^{\alpha_d}$$ for every fixed $d\geq 2$, thereby resolving Alon's problem in a stronger form.