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

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\).