Covering sets

Arne Winterhof
RICAM, Linz, Austria
https://www.ricam.oeaw.ac.at/people/member/?firstname=Arne&lastname=Winterhof

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

ωλ,μ(q)q1+o(1)max{λ,μ}1/2,

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

https://arxiv.org/abs/1310.0120

Catégories



Retour en haut