Further results on binary codes of covering radius 2 and saturating sets in projective spaces

Abstract

The length function ${\ell }_2(r,R)$ is the smallest length of a binary linear code with codimension (redundancy) $r$ and covering radius $R$. Let $s_2(N,\rho )$ be the smallest size of a $\rho$-saturating set in the projective space $\mathrm{PG}(N,2)$. It is known that ${\ell }_2(r,R)=s_2(r-1,R-1)$. We obtain the following new upper bounds on ${\ell }_2(r,2)$, which yield a decrease $\Delta (r,2)$ compared to the best previously known upper bounds: $r=2t,r=10,18,20$ and $r\ge 28,{\ell }_2(r,2)=s_2(r-1,1)\le 51\cdot 2^{r/2-5}-1;\Delta (r,2)=2^{r/2-5}$. To obtain these bounds, we construct a new infinite code family, using distinct versions of the $q^m$-concatenating constructions of covering codes; some of these versions are proposed in this paper. We also obtain new useful partitions of column sets of parity check matrices of some codes. The asymptotic covering density $\overline{\mu }(2)\le 1.27002$, provided by the codes of the new family, is smaller than previously known one and gives rise to the new upper bound $f(2)\le 1.27002$ on the constant $f(2)$ of the Green's Open Problem 40.

21 pages