New covering codes of radius $R$, codimension $tR$ and $tR+\frac{R}{2}$, and saturating sets in projective spaces

Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco

Published 2018-08-28Version 1

The length function $\ell_q(r,R)$ is the smallest length of a $ q $-ary linear code of codimension $r$ and covering radius $R$. In this work we obtain new constructive upper bounds on $\ell_q(r,R)$ for all $R\ge4$ and $r=tR$ with integer $t\ge2$, and also for all even $R\ge2$ and $r=tR+\frac{R}{2}$ with integer $t\ge1$. The new bounds are provided by new infinite families of covering codes with fixed $R$ and growing codimension. The new bounds improve upon the known ones. We propose a general regular construction (called `Line-Ovals') of a minimal $\rho$-saturating $((\rho+1)q+1)$-set in the projective space $\mathrm{PG}(2\rho+1,q)$ for all $\rho\ge0$. Such a set corresponds to an $[Rq+1,Rq+1-2R]_qR$ locally optimal code$^1$ of covering radius $R=\rho+1.$ In these codes, we investigate combinatorial properties regarding to spherical capsules (including the property to be a surface-covering code$^1$) and give corresponding constructions for code codimension lifting. Using the new codes as starting points in these constructions we obtained the desired infinite code families with growing $r=tR$. In addition, we obtain new 1-saturating sets in the projective plane $\mathrm{PG}(2,q^2)$ and, founding on them, construct infinite code families with fixed even radius $R\ge2$ and growing codimension $r=tR+\frac{R}{2}$, $t\ge1$. ($^1$ see the definitions at the end of Section 1.1)