Source-linked AI summary
Further results on binary codes of covering radius 2 and saturating sets in projective spaces
Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco, Stephen Wu
TL;DR
Binary covering codes and saturating sets are linked, and the paper seeks improved bounds for radius-2 code lengths and covering density. It constructs an infinite code family using q^m-concatenating constructions and obtains improved length and density bounds, including a new upper bound for f(2).
Problem
The paper targets improved radius-2 length bounds and a smaller asymptotic covering density than the previously reported f(2) upper bound of 1.32031.
Source: §1 · p. 4Method
The authors construct new infinite code families and sporadic codes using new versions of q^m-concatenating constructions.
Source: §2 · p. 5Results
For r = 2t with r = 10, 18, 20, or r ≥ 28, ℓ_2(r, 2) = s_2(r − 1, 1) ≤ 51 · 2^(r/2−5) − 1 and μ(2) ≤ 1.27002.
Source: §2 · p. 5Takeaways & Limitations
The new family provides the upper bound f(2) ≤ 1.27002 for Green’s Open Problem 40.
Source: §1 · p. 4The examined codes have minimum distance d ≥ 3.
Source: §3 · p. 6
Abstract
from arXiv · showhide
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\ge28,\ell_2(r,2)=s_2(r-1,1)\le51\cdot2^{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)\le1.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)\le1.27002$ on the constant $f(2)$ of the Green's Open Problem 40.
1 Introduction, notations, and background
The introduction defines binary covering codes and relates them to saturating sets in binary projective spaces. It motivates improved covering-code bounds through Green’s Open Problem 40 and introduces the paper’s new constructions.
1 Introduction, notations, and background
- A binary code has covering radius R when every vector is within Hamming distance R of a codeword; equivalently, every vector is a sum of at most R parity-check columns.The length function ℓ_2(r, R) is the smallest length of a binary linear code with redundancy r and covering radius R.Source: §1 · pp. 2–3
- A set is ρ-saturating when every point of PG(N, 2) is a sum of at most ρ + 1 of its points, and code parity-check columns give a one-to-one correspondence with such sets.Minimal saturating sets correspond to locally optimal covering codes.Source: §1 · p. 3
- Green’s Open Problem 40 asks whether f(R) tends to infinity, and f(R) can be bounded using the asymptotic covering density of infinite code families.The introduction reports a previously known upper bound f(2) ≤ 1.32031.Source: §1 · p. 4
- The paper proposes new q^m-concatenating constructions and parity-check-column partitions to obtain improved bounds on ℓ_2(r, 2) and asymptotic covering density.A new [50, 40, 3]_2^2 code and a partition of its parity-check columns into 10 subsets serve as a seed in the constructions.Source: §1 · p. 4
2 The main results
The main results give improved upper bounds on binary covering-code lengths, including an infinite family with smaller asymptotic covering density and a decrease in known length bounds.
2 The main results
- The new infinite family and sporadic codes decrease the known upper bounds on ℓ_2(r, 2) by Δ(r, 2) = 2^(r/2−5).The paper attributes the family’s parameters to Theorems 5.2, 5.5, 5.6, and 5.8, and the sporadic codes to Theorem 5.4.Source: §2 · p. 5
- For R=2 and r=2t, with r=10, 18, 20, or r≥28, ℓ₂(r, 2)=s₂(r−1, 1)≤51·2^(r/2−5)−1 and μ(2)≤1.27002.Source: §2 · p. 5
- The new infinite family gives the upper bound f(2) ≤ 1.27002 for Green’s Open Problem 40.The paper links upper bounds on f(R) to asymptotic covering densities of infinite code families.Source: §2 · p. 5
- The new versions of the q^m-concatenating constructions are used to obtain the new codes.The paper also reports a sporadic bound ℓ_2(r, 2) = s_2(r − 1, 1) ≤ 52 · 2^(r/2−5) − 3.Source: §2 · p. 5
3 Basic qm-concatenating Construction QM for q = 2
Construction QM builds a new parity-check matrix from a starting code and auxiliary blocks; with suitable choices, the new code retains the starting code’s covering radius. Its partition-based setup supports parameter improvements in later constructions.
3 Basic qm-concatenating Construction QM for q = 2
- An (R, ℓ)-partition represents every vector, including zero, as a sum of between ℓ and R columns from distinct subsets, and ℓ ≥ 1 can improve parameters in later constructions.The number of subsets p(H, ℓ; P) is at least R and at most n; the trivial partition places each column in its own subset.Source: §3 · p. 6
- The paper considers covering-radius-2 codes with minimum distance d ≥ 3 and uses their associated short notation for codes, objects, and partitions.The construction begins with a parity-check matrix H0 of a starting code C0.Source: §3 · pp. 6–7
- The construction builds on earlier qm-concatenating work and, when iterated, yields infinite code families as m ranges over an infinite set of integers.For q = 2, θm,2 = 2^m − 1; the paper uses several versions of Construction QM.Source: §3 · pp. 7–8
- Each starting column receives an indicator in F2^m ∪ {∗}, with distinct indicators required for columns in different partition subsets and |B| ≥ p(H0, ℓ0).Within one subset, indicators may be equal or distinct.Source: §3 · p. 7
- QM constructs binary codes with length n = 2^m n0 + Nm and redundancy r0 + Rm, preserving the starting code’s covering radius R when m, D, and B are carefully chosen.The condition is Nm ≤ Rθm,2; the new codes’ covering density is almost the same, but slightly greater, than the starting code’s.Source: §3 · pp. 7–8
- The new parity-check matrix HC concatenates an auxiliary matrix D with blocks A(hj, βj), each built from a starting column and its indicator.Each block has 2^m columns, and its top r0 rows repeat hj; D has zero top rows.Source: §3 · p. 7
4 The known results on binary linear codes of covering radius 2 and 1-saturating sets
The section reports known upper bounds for binary covering-radius-2 codes and related saturating sets, including infinite families and sporadic cases. It also gives parameters for two QM constructions that produce new codes.
4 The known results on binary linear codes of covering radius 2 and 1-saturating sets
- The code family in (4.7) gives f(2) ≤ 1.32031 for Green’s Open Problem 40, while the section also identifies earlier results and their cited sources.The notation ϑ(r) differs from the f(r) notation used in [16] to avoid confusion with f(R).Source: §4 · pp. 8–9
- For r = 2t with r = 10, 18, 20 or r ≥ 28, ℓ2(r, 2) = s2(r − 1, 1) ≤ Φ(r) = 26 · 2^(r/2−4) − 1, with μ(2) ≤ 1.32031.The bound is given for t = 5, 9, 10, and t ≥ 14.Source: §4 · pp. 8–9
- For odd r = 2t − 1 ≥ 3, the section gives ℓ2(r, 2) = s2(r − 1, 1) ≤ 5 · 2^((r−3)/2) − 1 and μ(2) ≤ 1.5625.This family is denoted ϑ(r).Source: §4 · pp. 8–9
- For r = 22, 24, 26, ℓ2(r, 2) = s2(r − 1, 1) ≤ 26.5 · 2^(r/2−4) − 3, with respective density bounds 1.36956, 1.37057, and 1.37107.These cases are denoted bΦ(r).Source: §4 · pp. 8–9
- Construction QM 2_1 yields a radius-2 code of length 2^m(n0 + 2) − 3 and redundancy r0 + 2m.The resulting code has minimum distance 3.Source: §4 · p. 9
- Construction QM 2_2 yields a radius-2 code of length 2^m(n0 + 1) − 1 and redundancy r0 + 2m, with p(HC) ≤ 2^m + 1.Its setup specifies B = F2^m, n0 ≥ 2^m ≥ p(H0), and D = D1.Source: §4 · p. 9
5 New results on binary linear codes of covering radius 2 and 1-saturating sets
This section presents new upper bounds for binary covering-radius-2 codes and 1-saturating sets, including an infinite code family built using new codes and 2-partitions of parity-check matrix columns. It derives bounds on asymptotic covering density and on f(2).
Theorem 5.2
- At r=10, the [50, 40, 3]₂ code has covering radius 2 and gives ℓ2(10, 2)=s2(9, 1)≤50, Δ(10, 2)=1, and covering density 1.24609375.Its parity-check matrix has a 2-partition into 10 subsets, including three distinct subsets containing a linearly dependent triple of columns.Source: §5 · pp. 10–11
Theorem 5.4
- For r=22, 24, 26, ℓ2(r, 2)=s2(r−1, 1)≤52·2^(r/2−5)−3, with Δ(r, 2)=2^(r/2−5) and μ(22, 2)≤1.31833, μ(24, 2)≤1.31933, μ(26, 2)≤1.31982.These are three new binary linear codes of covering radius 2.Source: §5 · p. 11
Theorems 5.5–5.6
- For r=18, ℓ2(18, 2)=s2(17, 1)≤815 with Δ(18, 2)=24, while for r=28 the corresponding bound is 26111 with Δ(28, 2)=29.The r=18 code has a 2-partition into 25+1 subsets with three singleton columns forming a linearly dependent triple.Source: §5 · pp. 11–12
Theorem 5.7
- For r=2t with t=t₀+m and t₀≥m≥λ₀+1, the construction has n=51·2^(r/2−5)−1=Θ(r), and Δ(r,2)=2^(r/2−5).The starting code has n₀=Θ(2t₀) and p(H₀)≤2λ₀+2; the condition n₀≥2m≥p(H₀) holds when t₀≥m≥λ₀+1.Source: §5 · p. 13
Theorem 5.8
- For even r=10, 18, 20, and r≥28, ℓ2(r, 2)=s2(r−1, 1)≤51·2^(r/2−5)−1, with Δ(r, 2)=2^(r/2−5); the family also gives μ(2)≤1.27002 and f(2)≤1.27002.Theorem 5.8 states that these bounds are provided by an infinite family of binary linear [n, n−r, 3]₂ codes of covering radius 2.Source: §5 · p. 14
Theorem 5.8 construction process
- Choosing m=5 under t0≥m≥λ0+1 gives Δ(20,2)=25; (5.11) then yields codes for every even r=30, 32, …, 76 with Δ(r,2)=2^(r/2−5).The listed constructions start from r0=18 for r=30, 32; r0=20 for r=34–40; r0=28 for r=42, 44; and r0=30, 32, …, 44 for r=46, 48, …, 76.Source: §5 · p. 17
5 New results on binary linear codes of covering radius 2 and 1-saturating sets
- The iterative process can continue indefinitely, producing the infinite code family of (5.12) and (5.13).Source: §5 · p. 17
- 1.27002 is an upper bound on μ(2), yielding f(2) ≤ 1.27002.The upper bound on μ(2) follows directly from (1.2).Source: §5 · p. 17