LOWER BOUNDS FOR Q-ARY COVERINGS BY SPHERES OF RADIUS ONE

Let C be a q-ary covering code with covering radius one. We give lower and upper bounds for the number of elements of C that lie in a fixed subspace of {0,..., q - 1}n. These inequalities lead to lower bounds for the cardinality of C that improve on the sphere covering bound. More precisely, we show that, if (q - 1) n + 1 does not divide q(n) and if (q, n) is-not-an-element-of {(2, 2), (2,4)), the sphere covering bound is never reached. This enables us to characterize the cases where the sphere covering bound is attained, when q is a prime power. We also present some improvements of the already known lower bounds for binary and ternary codes. (C) 1994 Academic Press, Inc.