Almost optimum $\ell$-covering of ${\mathbb{Z}}_n$

Abstract

A subset $B$ of the ring ${\mathbb{Z}}_n$ is referred to as a $\ell$-covering set if $\{ab(\mathrm{mod}n)|0\le a\le \ell ,b\in B\}={\mathbb{Z}}_n$. We show that there exists a $\ell$-covering set of ${\mathbb{Z}}_n$ of size $O(\frac{n}{\ell }\log n)$ for all $n$ and $\ell$, and how to construct such a set. We also provide examples where any $\ell$-covering set must have a size of $\Omega (\frac{n}{\ell }\frac{\log n}{\log \log n})$. The proof employs a refined bound for the relative totient function obtained through sieve theory and the existence of a large divisor with a linear divisor sum. The result can be used to simplify a modular subset sum algorithm.