Upper bounds on the length function for covering codes with covering radius $ R $ and codimension $ tR+1 $
Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco · Advances in Mathematics of Communications · 2022
The length function $ \ell_q(r,R) $ is the smallest length of a $ q $-ary linear code with codimension (redundancy) $ r $ and covering radius $ R $. In this work, new upper bounds on $ \ell_q(tR+1,R) $ are obtained in the following forms:$ \begin{equation*} \begin{split} &(a)\; \ell_q(r,R)\le cq^{(r-R)/R}\cdot\sqrt[R]{\ln q},\; R\ge3,\; r = tR+1,\; t\ge1,\\ &\phantom{(a)\; } q\;{\rm{ is \;an\; arbitrary \;prime\; power}},\; c{\rm{ \;is\; independent \;of\; }}q. \end{split} \end{equation*} $$ \begin{equation*} \begin{split} &(b)\; \ell_q(r,R)< 3.43Rq^{(r-R)/R}\cdot\sqrt[R]{\ln q},\; R\ge3,\; r = tR+1,\; t\ge1,\\ &\phantom{(b)\; } q\;{\rm{ is \;an\; arbitrary\; prime \;power}},\; q\;{\rm{ is \;large\; enough}}. \end{split} \end{equation*} $In the literature, for $ q = (q')^R $ with $ q' $ a prime power, smaller upper bounds are known; however, when $ q $ is an arbitrary prime power, the bounds of this paper are better than the known ones.For $ t = 1 $, we use a one-to-one correspondence between $ [n,n-(R+1)]_qR $ codes and $ (R-1) $-saturating $ n $-sets in the projective space $ \mathrm{PG}(R,q) $. A new construction of such saturating sets providing sets of small size is proposed. Then the $ [n,n-(R+1)]_qR $ codes, obtained by geometrical methods, are taken as the starting ones in the lift-constructions (so-called '$ q^m $-concatenating constructions') for covering codes to obtain infinite families of codes with growing codimension $ r = tR+1 $, $ t\ge1 $.