UPPER BOUNDS ON THE LENGTH FUNCTION FOR COVERING CODES WITH COVERING RADIUS R AND CODIMENSION tR + 1

The length function ℓq(r, R) is the smallest length of a q-ary linear code with codimension (redundancy) r and covering radius R. In this work, new upper bounds on ℓq(tR + 1, R) are obtained in the following forms: (a) ℓq(r, R) ≤ cq(r−R)/R ·R√ln q, R ≥ 3, r = tR + 1, t ≥ 1, q is an arbitrary prime power, c is independent of q. (b) ℓq(r, R) < 3.43Rq(r−R)/R ·R√ln q, R ≥ 3, r = tR + 1, t ≥ 1, q is an arbitrary prime power, q is large enough. In the literature, for q = (q′ )R with q′ a prime power, smaller upper bounds are known; however, when q is an arbitrary prime power, the bounds of this paper are better than the known ones. For t = 1, we use a one-to-one correspondence between [n, n − (R + 1)]qR codes and (R − 1)-saturating n-sets in the projective space PG(R, q). A new construction of such saturating sets providing sets of small size is proposed. Then the [n, n − (R + 1)]qR codes, obtained by geometrical methods, are taken as the starting ones in the lift-constructions (so-called “qm-concatenating con-structions”) for covering codes to obtain infinite families of codes with growing codimension r = tR + 1, t ≥ 1.