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

Abstract

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\ge 4$, $r=tR$, $t\ge 2$, and also for all even $R\ge 2$, $r=tR+\frac{R}{2}$, $t\ge 1$. The new bounds are provided by infinite families of new covering codes with fixed R and increasing 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 \ge 0$. Such a set corresponds to an $[Rq+1,Rq+1-2R,3]_qR$ locally optimal code of covering radius $R=\rho +1$. Basing on combinatorial properties of these codes regarding to spherical capsules, we give constructions for code codimension lifting and obtain infinite families of new surface-covering codes with codimension $r=tR$, $t\ge 2$. In addition, we obtain new 1-saturating sets in the projective plane $\mathrm {PG}(2,q^2)$ and, basing on them, construct infinite code families with fixed even radius $R\ge 2$ and codimension $r=tR+\frac{R}{2}$, $t\ge 1$.