Linear nonbinary covering codes and saturating sets in projective spaces

Pages: 119 - 147,
Volume 5,
Issue 1,
February
2011 doi:10.3934/amc.2011.5.119

Alexander A. Davydov - Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, GSP-4, Moscow, 127994, Russian Federation (email)

Massimo Giulietti - Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, 06123, Perugia, Italy (email)

Stefano Marcugini - Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, 06123, Perugia, Italy (email)

Fernanda Pambianco - Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, 06123, Perugia, Italy (email)

Abstract:
Let $\mathcal A$_{R,q} denote a family of covering codes, in
which the covering radius $R$ and the size $q$ of the
underlying Galois field are fixed, while the code length tends
to infinity. The construction of families with small asymptotic
covering densities is a classical problem in the area of
Covering Codes.

In this paper, infinite sets of families $\mathcal A$_{R,q},
where $R$ is fixed but $q$ ranges over an infinite set of prime
powers are considered, and the dependence on $q$ of the
asymptotic covering densities of $\mathcal A$_{R,q} is
investigated. It turns out that for the upper limit
$\mu$_{q}^{*}(R,$\mathcal A$_{R,q}) of the covering density of
$\mathcal A$_{R,q}, the best possibility is
$\mu$_{q}^{*}(R,$\mathcal A$_{R,q})=$O(q)$. The main achievement of the
present paper is the construction of *optimal* infinite
sets of families $\mathcal A$_{R,q}, that is, sets of families
such that relation $\mu$_{q}^{*}(R,$\mathcal A$_{R,q})=$O(q)$
holds, for any covering radius $R\geq 2$.

We first showed that for a given $R$, to obtain optimal
infinite sets of families it is enough to construct $R$
infinite families $\mathcal A$_{R,q}^{(0)},
$\mathcal A$_{R,q}^{(1)}, $\ldots$,
$\mathcal A$_{R,q}^{(R-1)} such that,
for all $u\geq u$_{0},
the family $\mathcal A$_{R,q}^{($\gamma$)} contains codes of
codimension $r$_{u}$=Ru + \gamma$ and length
$f$_{q}^{($\gamma$)}($r$_{u})
where $f$_{q}^{($\gamma$)}$(r)=O(q$^{(r-R)/R}$)$ and
$u$_{0} is a constant. Then, we were able to construct the
necessary families $\mathcal A$_{R,q}^{($\gamma$)} for any
covering radius $R\geq 2$, with $q$ ranging over the (infinite)
set of $R$-th powers. A result of independent interest is that
in each of these families $\mathcal A$_{R,q}^{($\gamma$)}, the
lower limit of the covering density is bounded from above by a
constant independent of $q$.

The key tool in our investigation is the design of new small
saturating sets in projective spaces over finite fields, which
are used as the starting point for the $q$^{m}-concatenating
constructions of covering codes. A new concept of $N$-fold
strong blocking set is introduced. As a result of our
investigation, many new asymptotic and finite upper bounds on
the length function of covering codes and on the smallest sizes
of saturating sets, are also obtained. Updated tables for these
upper bounds are provided. An analysis and a survey of the
known results are presented.

Keywords: Linear covering codes, nonbinary codes, saturating sets in projective spaces, covering density.

Mathematics Subject Classification: Primary: 94B05, 51E22; Secondary: 94B25, 94B27, 94B65, 51E21.

Received: September 2010;
Available Online: February 2011.

References