Paper detail

Covering sets for limited-magnitude errors

For a set $\cM=\{-μ,-μ+1,\ldots, λ\}\setminus\{0\}$ with non-negative integers $λ,μ<q$ not both 0, a subset $\cS$ of the residue class ring $\Z_q$ modulo an integer $q\ge 1$ is called a $(λ,μ;q)$-\emph{covering set} if $$ \cM \cS=\{ms \bmod q : m\in \cM,\ s\in \cS\}=\Z_q. $$ Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a $(λ,μ;q)$-covering set $\cS$ which is of the size $q^{1 + o(1)}\max\{λ,μ\}^{-1/2}$ for almost all integers $q\ge 1$ and of optimal size $p\max\{λ,μ\}^{-1}$ if $q=p$ is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi we prove the bound $$ω_{λ,μ}(q)\le q^{1+o(1)}\max\{λ,μ\}^{-1/2},$$ for any integer $q\ge 1$, however the proof of this bound is not constructive.