Linear nonbinary covering codes and saturating sets in projective spaces

Let AR,q denote a family of covering codes, inwhich the covering radius R and the size q of theunderlying Galois field are fixed, while the code length tendsto infinity. The construction of families with small asymptoticcovering densities is a classical problem in the area ofCovering Codes. In this paper, infinite sets of families AR,q,where R is fixed but q ranges over an infinite set of primepowers are considered, and the dependence on q of theasymptotic covering densities of AR,q isinvestigated. It turns out that for the upper limit μq*(R,AR,q) of the covering density ofAR,q, the best possibility isμq*(R,AR,q)=$O(q)$. The main achievement of thepresent paper is the construction of optimal infinitesets of families AR,q, that is, sets of familiessuch that relation μq*(R,AR,q)=$O(q)$holds, for any covering radius R≥ 2. We first showed that for a given R, to obtain optimalinfinite sets of families it is enough to construct Rinfinite families AR,q(0),AR,q(1), …, AR,q(R-1) such that, for all u≥ u0,the family AR,q(γ) contains codes ofcodimension ru=Ru + γ and length fq(γ)(ru)where fq(γ)$(r)=O(q$(r-R)/R$)$ andu0 is a constant. Then, we were able to construct thenecessary families AR,q(γ) for anycovering radius R≥ 2, with q ranging over the (infinite)set of R-th powers. A result of independent interest is thatin each of these families AR,q(γ), thelower limit of the covering density is bounded from above by aconstant independent of q. The key tool in our investigation is the design of new smallsaturating sets in projective spaces over finite fields, whichare used as the starting point for the qm-concatenatingconstructions of covering codes. A new concept of N-foldstrong blocking set is introduced. As a result of ourinvestigation, many new asymptotic and finite upper bounds onthe length function of covering codes and on the smallest sizesof saturating sets, are also obtained. Updated tables for theseupper bounds are provided. An analysis and a survey of theknown results are presented.