Further results on binary linear covering codes and saturating sets in projective spaces

Abstract

The binary 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 binary projective space $\mathrm{PG}(N,2)$. It is known that the binary length function satisfies $\ell_2(r,R)=s_2(r-1,R-1)$. We obtain the following new upper bounds on $\ell_2(r,R)$, improving the previously known upper bounds by $\Delta(r,R)$: $R=2,r=2t\ge28$, and $r=10,18,20$, $\ell_2(r,2)=s_2(r-1,1)\le51\cdot2^{r/2-5}-1,\Delta(r,2)=2^{r/2-5}$; $R=3,r=3t-1\ge41$ and $r=26$, $\ell_2(r,3)=s_2(r-1,2)\le818\cdot2^{(r-26)/3}-1$, $\Delta(41,3)=63,\Delta(r,3)=2^{(r-26)/3}$ if $r\ge44$. To obtain these bounds, we construct new infinite code families, using distinct versions of the $q^m$-concatenating constructions of covering codes, including new versions proposed in this paper. We also obtain new useful partitions of column sets of parity check matrices of some codes. The new code families provide the asymptotic covering-density bounds $\overline{\mu}(2)\le2601/2048<1.27002$, $\overline{\mu}(3)\le1.35935$, improving the previously known bounds and giving rise to the new upper bounds $f(2)\le2601/2048<1.27002$, $f(3)\le1.35935$ on the constants $f(2),f(3)$ of the Green's Open Problem 40.