New upper bounds for binary linear covering codes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915604703739904 |
|---|---|
| author | Davydov, Alexander A. Marcugini, Stefano Pambianco, Fernanda |
| author_facet | Davydov, Alexander A. Marcugini, Stefano Pambianco, Fernanda |
| contents | The length function $\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 $\ell_2(r,R)$, which yield a decrease $Δ(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 $\overlineμ(2)\thickapprox1.3203$, $\overlineμ(3)\thickapprox1.3643$, $\overlineμ(4)\thickapprox2.8428$, provided by the codes of the new families, are smaller than the known ones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02542 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New upper bounds for binary linear covering codes Davydov, Alexander A. Marcugini, Stefano Pambianco, Fernanda Combinatorics 94B65, 94B25, 94B60, 94B05 The length function $\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 $\ell_2(r,R)$, which yield a decrease $Δ(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 $\overlineμ(2)\thickapprox1.3203$, $\overlineμ(3)\thickapprox1.3643$, $\overlineμ(4)\thickapprox2.8428$, provided by the codes of the new families, are smaller than the known ones. |
| title | New upper bounds for binary linear covering codes |
| topic | Combinatorics 94B65, 94B25, 94B60, 94B05 |
| url | https://arxiv.org/abs/2511.02542 |