The distribution of sequences in residue classes

Abstract:

We prove that any set of integers ${\mathcal A}\subset [1,x]$ with $\vert {\mathcal A} \vert \gg (\log x)^r$ lies in at least $\nu _{\mathcal A}(p) \gg p^{\frac {r}{r+1}}$ many residue classes modulo most primes $p \ll (\log x)^{r+1}$. (Here $r$ is a positive constant.) This generalizes a result of Erdős and Ram Murty, who proved in connection with Artin’s conjecture on primitive roots that the integers below $x$ which are multiplicatively generated by the coprime integers $a_1, \ldots , a_r$ (i.e. whose counting function is also $c ( \log x)^r$) lie in at least $p^{\frac {r}{r+1} + \varepsilon (p)}$ residue classes, modulo most small primes $p$, where $\varepsilon (p) \rightarrow 0,$ as $p \rightarrow \infty$.