Covering sets

Arne Winterhof
RICAM, Linz, Austria

Date(s) : 21/10/2014   iCal
11 h 05 min - 12 h 00 min

For a set
$\cM=\{-\mu,-\mu+1,\ldots, \lambda\}\setminus\{0\}$ with non-negative integers λ,μ<q not both 0, a subset $\cS$ of the residue class ring $\Z_q$ modulo an integer q1 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 q1+o(1)max{λ,μ}1/2 for almost all integers q1 and of optimal size pmax{λ,μ}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


for any integer q1, however the proof of this bound is not constructive.


Retour en haut