Hitting Arithmetic Progressions at the Square-Root Scale

Abstract

Let $f(N,k)$ be the minimum size of a subset of $\{0,\dots ,N-1\}$ meeting every $k$-term arithmetic progression of positive difference contained in that interval. Improving on a bound of Truss, we prove that \[ f(n^2,n)\ge n+n^{1-o(1)} \] as $n\to \infty$. Improving on a bound of Xu, for primes $p$ we prove that \[ f(p^2,p)\le2p-(\sqrt2-o(1))\sqrt{\frac p{\log p}}. \]

arXiv commentImproved bounds over the v1