NEW BOUNDS FOR COVERING CODES OF RADIUS 3 AND CODIMENSION 3t+1

The smallest possible length of a q-ary linear code of covering radius R and codimension (redundancy) r is called the length function and is denoted by l(q)(r, R). In this work, for q an arbitrary prime power, we obtain the following new constructive upper bounds on l(q)(3t + 1, 3): l(q)(r, 3) (sic) 3 root k . q((r-3)/3) . 3 root ln q, r = 3t + 1, t >= 1, q >= [W(k)], 18 < k <= 20.339, W(k) is a decreasing function of k; l(q)(r, 3) (sic) 3 root 18 . q((r-3)/3) . 3 root ln q, r = 3t + 1, t >= 1, q large enough. For t = 1, we use a one-to-one correspondence between codes of covering radius 3 and codimension 4, and 2-saturating sets in the projective space PG(3, q). A new construction providing sets of small size is proposed. The codes, obtained by geometrical methods, are taken as the starting ones in the lift-constructions (so-called "q(m)-concatenating constructions") to obtain infinite families of codes with radius 3 and growing codimension r = 3t+ 1, t >= 1. The new bounds are essentially better than the known ones.