Linear nonbinary covering codes and saturating sets in projective spaces (Q534526)

The covering radius of an \([n,n-r]_q\) code is the smallest integer \(R\) such that the space \(\mathbb F_q^n\) is covered by the spheres of radius \(R\) centered at the codewords of the code. The covering problem for linear codes is the problem of finding linear codes with small covering radius with respect to their length and dimension. Linear codes investigated from the point of view of the covering problem are called covering codes. The covering problem for linear codes is closely related to the problem of saturating sets in finite projective spaces. This link is used by the authors. They concentrate on finding families \({\mathcal A}_{R,q}\) of covering codes in which the covering radius \(R\) and the size \(q\) of the underlying finite field are fixed while the code length tends to infinity, and which have small asymptotic covering densities. The key method of the authors is the design of new small saturating sets in finite projective spaces, which are then used as the starting point for the \(q^m\)-concatenating constructions of covering codes. In particular, the concept of \(N\)-fold strong blocking sets is introduced in this study. The authors also provide new tables of the upper bounds on the covering radius of linear codes.