New covering codes of radius R, codimension tR and tR+R/2 , and saturating sets in projective spaces

The length function l_q(r, R) is the smallest length of a q-ary linear code of codimension r and coverin gradius R. In this work we obtain new constructive upper bounds on l_q(r, R) for all R ≥4,r =tR,t ≥2, and also for all even R ≥2,r =tR+R 2 ,t ≥1.The new bounds are provided byi nfinite 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 ρ-saturating ((ρ +1)q +1)-set in the projective space PG(2ρ+1,q) for allρ ≥0. Such a set corresponds to an [Rq+1, Rq+1−2R,3]qR locally optimal code of covering radius R = ρ +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 ≥2. In addition, we obtain new 1-saturating sets in the projective plane PG(2,q2) and, basing on them, construct infinite code families with fixed even radius R ≥ 2 and codimension r =tR+ R/2, t ≥1.