Further results on binary linear covering codes and saturating sets in projective spaces
Abstract
The binary length function ℓ2(r,R) is the smallest length of a binary linear code with codimension (redundancy) r and covering radius R. Let s2(N,ρ) be the smallest size of a ρ-saturating set in the binary projective space PG(N,2). It is known that the binary length function satisfies ℓ2(r,R)=s2(r−1,R−1). We obtain the following new upper bounds on ℓ2(r,R), improving the previously known upper bounds by Δ(r,R): R=2,r=2t≥28, and r=10,18,20, ℓ2(r,2)=s2(r−1,1)≤51·2r/2−5−1,Δ(r,2)=2r/2−5; R=3,r=3t−1≥41 and r=26, ℓ2(r,3)=s2(r−1,2)≤818·2(r−26)/3−1, Δ(41,3)=63,Δ(r,3)=2(r−26)/3 if r≥44. To obtain these bounds, we construct new infinite code families, using distinct versions of the qm-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 μ̅(2)≤2601/2048<1.27002, μ̅(3)≤1.35935, improving the previously known bounds and giving rise to the new upper bounds f(2)≤2601/2048<1.27002, f(3)≤1.35935 on the constants $f(2),f(3)$ of the Green's Open Problem 40.
Related
- Further Results on Sum-Freedom of Binary and q-ary Functions
- Covering Projective Height Balls by Subspaces in Rigid Adelic Spaces
- Further results on the paramodular Hecke algebra
- Further results on non-negativity conjectures for copartition products
- Further Results on the Isometric Embeddability of Sqm into Spn
BibTeX
@misc{davydov2026further,
title = {{Further results on binary linear covering codes and saturating sets in projective spaces}},
author = {Alexander A. Davydov and Stefano Marcugini and Fernanda Pambianco and Stephen Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.16078},
eprint = {2609.16078},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16078},
}
RIS
TY - UNPB
TI - Further results on binary linear covering codes and saturating sets in projective spaces
AU - Alexander A. Davydov
AU - Stefano Marcugini
AU - Fernanda Pambianco
AU - Stephen Wu
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2609.16078
UR - https://arxiv.org/abs/2609.16078
AB - The binary length function ℓ_2(r,R) is the smallest length of a binary linear code with codimension (redundancy) r and covering radius R. Let s_2(N,ρ) be the smallest size of a ρ-saturating set in the binary projective space PG(N,2). It is known that the binary length function satisfies ℓ_2(r,R)=s_2(r−1,R−1). We obtain the following new upper bounds on ℓ_2(r,R), improving the previously known upper bounds by Δ(r,R): R=2,r=2t≥28, and r=10,18,20, ℓ_2(r,2)=s_2(r−1,1)≤51·2^r/2−5−1,Δ(r,2)=2^r/2−5; R=3,r=3t−1≥41 and r=26, ℓ_2(r,3)=s_2(r−1,2)≤818·2^(r−26)/3−1, Δ(41,3)=63,Δ(r,3)=2^(r−26)/3 if r≥44. 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 μ̅(2)≤2601/2048<1.27002, μ̅(3)≤1.35935, improving the previously known bounds and giving rise to the new upper bounds f(2)≤2601/2048<1.27002, f(3)≤1.35935 on the constants $f(2),f(3)$ of the Green's Open Problem 40.
ER -