New upper bounds for binary linear covering codes

The length function ${\mathrm{\ell }}_2(r,R)$ is the smallest length of a binary linear code with codimension (redundancy) $r$ and covering radius $R$. We obtain the following new upper bounds on ${\mathrm{\ell }}_2(r,R)$, which yield a decrease $\mathrm{\Delta }(r,R)$ compared to the best previously known upper bounds: \begin{equation*} R=2,,r=2t,,r=18,20,$\text{ and }$r\ge28,,\ell_2(r,2)\le26\cdot2^{r/2-4}-1;,Δ(r,2)=2^{r/2-4}. \end{equation*} \begin{equation*} R=3,,r=3t-1,,r=26$\text{ and }$r\ge44,,\ell_2(r,3)\le819\cdot2^{(r-26)/3}-1;,Δ(r,3)=2^{(r-23)/3}. \end{equation*} \begin{equation*} R=4,,r=4t,,r=40$\text{ and }$r\ge68,,\ell_2(r,4)\le2943\cdot2^{r/4-10}-1;,Δ(r,4)=2^{r/4-10}-1. \end{equation*} To obtain these bounds we construct new infinite code families, using distinct versions of the $q^m$-concatenating constructions of covering codes; some of these versions are proposed in this paper. We also introduce new useful partitions of column sets of parity check matrices of some codes. The asymptotic covering densities $\bar{\mu }(2)\approx 1.3203$, $\bar{\mu }(3)\approx 1.3643$, $\bar{\mu }(4)\approx 2.8428$, provided by the codes of the new families, are smaller than the known ones.