CS Paper Radar

Auxiliary Codes and the Generalized Packing-Covering Conjecture

Isaac Barouch Essayag, Aryeh Lev Zabokritskiy

cs.IT ·submitted 2026-09-16 17:31 UTC · v2
theory

Abstract

The generalized packing--covering conjecture asks whether, at every order, the packing radius of a linear code is at most its covering radius. We prove the conjecture for every linear code of redundancy at most fourteen over every finite field, extending the previously established range of redundancies at most seven. We also prove the bound on generalized Hamming weights $d_t(C)\le2R_t(C)+1$ whenever the alphabet size $q$ satisfies $q\ge R_t(C)$. Both results use an auxiliary-code criterion that converts a covering property in the syndrome space into a weight bound. For binary primitive BCH codes, the packing radius is strictly smaller than the covering radius for every fixed error parameter and order, both at least two, once the extension degree is sufficiently large; this follows from existing covering bounds.

Comment
10 pages, 2 tables. Revised exposition and references; clarified the auxiliary-code method and improved presentation

Closest papers

Nearest neighbours by meaning across the whole index.

On the Generalized Packing and Covering Radii of Codes

cs.IT math.CO ·2026-09-13 ·Wenjun Yu, Moshe Schwartz
theory similarity 0.82
Abstract

The minimum distance and the covering radius are two fundamental properties of the code. Both have been extended: the former to the generalized Hamming weights hierarchy, and the latter to the generalized covering radii hierarchy. In both cases, the lowest level of the hierarchies corresponds to the classical minimum distance and covering radius, respectively. From a geometric point of view, the minimum distance of the code determines the packing radius, which is upper bounded by the covering radius. It was conjectured this relation extends to all other orders of the hierarchy, namely, that the generalized packing radii are upper bounded by the generalized covering radii of the same order. In this paper we prove this conjecture is true for the second order radii. We also prove the conjecture holds for all orders when the code rate is at most $3/5$. Finally, we show that for any code rate in $(0,1)$, for all sufficiently long codes the conjecture holds for all orders.

0.37

A proof of the generalized packing-covering conjecture

cs.IT math.CO ·2026-09-28 ·Gianira N. Alfarano, Giuseppe Marino, Alessandro Neri, Rocco Trombetti
similarity 0.81
Abstract

The generalized packing--covering conjecture of Elimelech, Firer and Schwartz asserts that, for every linear code $\mathcal{C}$ and every admissible order $t$, the $t$-th generalized Hamming weight $d_t(\mathcal{C})$ and the $t$-th generalized covering radius $R_t(\mathcal{C})$ satisfy $d_t(\mathcal{C})\le 2R_t(\mathcal{C})+2$. We give a computer-assisted proof of the conjecture for every linear code over every finite field and every admissible order. Combining a parity-check reformulation of the conjecture, bounds on the length of putative counterexamples, and successive puncturing arguments, we settle all orders $t\ge 32$ and reduce the remaining orders to finitely many parameter tuples, which we exclude by an exact computer verification.

0.03

Solutions to Three Conjectures and an Open Problem on Binary BCH Codes

cs.IT ·2026-09-01 ·Xiaoqiang Wang, Jiawei He, Boru Yi, Dabin Zheng
theory similarity 0.77
Abstract

BCH codes are among the most important classes of cyclic codes and have played a central role in coding theory and its applications. One of the fundamental problems in the study of BCH codes is to determine their exact minimum distances, which directly govern their error-correcting capability. Although the BCH bound provides a general lower bound, determining the exact minimum distance is often difficult, and many parameter families remain unresolved. In this paper, we investigate three conjectures and an open problem on binary BCH codes proposed by Chen, Xie, and Ding in \cite{Chen59}. We settle these conjectures on the exact minimum distances of three families of binary BCH codes by constructing codewords attaining the BCH bound. Beyond these conjectures, we further study the more difficult family codes and determine its minimum distance for some cases. We further study Open Problem 8.4: affirmative answers are obtained for the first two length families, while for the third family a sufficient condition is established and a counterexample shows that the unrestricted assertion does not hold in general.

0.20

Asymptotic Bounds on Generalized Covering Radii of Binary Primitive BCH Codes

cs.IT math.CO ·2026-08-31 ·Maosheng Xiong, Chi Hoi Yip, Ferdinando Zullo
theoryhighly cited similarity 0.76
Abstract

Fix integers $e\ge2$ and $r\ge1$. In this paper we study the $r$-th generalized covering radius $ρ_r\left(BCH(e,m)\right)$ of the binary primitive $e$-error-correcting BCH code $BCH(e,m)$. By using an algebraic-geometric reformulation of the covering problem together with an explicit Lang-Weil estimate, we prove that \[ρ_r\bigl(\BCH(e,m)\bigr)\le(r+1)e-1\] for all sufficiently large $m$. For $e\ge7$, this improves a recent result of Belinsky--Zabokritskiy. Our proof gives a substantially simpler geometric approach to this upper bound. In particular it implies that \[ρ_2\bigl(BCH(e,m)\bigr)=3e-1\] for all sufficiently large $m$. Previously it was only known that \[ρ_2\bigl(\BCH(e,m)\bigr) \in \left\{3e-1,3e\right\}\] for all sufficiently large $m$.

0.44

Asymptotically Tight Bounds for Generalized Covering Radii of Binary Primitive BCH Codes at All Higher Orders

cs.IT ·2026-08-24 ·Zeev Vladimir Belinsky, Aryeh Lev Zabokritskiy
theoryhighly cited similarity 0.76
Abstract · 56 pages. Revised version with a componentwise degree bound improving the sufficient field-size threshold for the known common-core support …

We study the generalized covering radii of binary primitive BCH codes, which measure how many parity-check columns suffice to span several prescribed syndromes. For the four-error-correcting family of length $2^m-1$, the second radius is exactly $11$ for $m\geq55$, and it is either $11$ or $12$ for $m\geq16$. For every fixed error parameter at least two, we give an explicit stable bound with two adjacent possible values for the second radius and an arithmetic criterion for exactness. At every higher order, we obtain explicit lower and upper bounds whose additive gap is bounded independently of the order for each fixed error parameter, once explicit field-size conditions hold. The bounds are therefore asymptotically tight as the order grows. The higher-order upper bound retains the common-core support count established by Xiong, Yip, and Zullo; our refinement reduces its sufficient field-size threshold at large order. The refinement combines componentwise mixed degrees with the ordinary degree of a multicone. The upper bounds come from constructing syndrome representations with a common set of parity-check columns.

0.50

Quantitative Tiling Stability From Quadratic Discrepancy In Hamming Spaces

cs.IT math.CO ·2026-08-26 ·Valery, Grishin, Aryeh Lev Zabokritskiy
theory similarity 0.75
Abstract · 39 pages; no figures. Revised exposition and reference locators. Exact-arithmetic verification companion: https://doi.org/10.5281/zenodo.221…

Quadratic ball discrepancy measures how uniformly a code meets Hamming balls over all centers and radii. Perfect codes minimize this quantity among codes of the same cardinality. We prove a quantitative refinement: at the parameters of every perfect code other than a one-word code or the full space, the discrepancy excess over the minimum is at least an explicit positive multiple of the discrepancy at the packing radius. The latter equals the tiling defect divided by the square of the code cardinality. This defect is the total squared deviation of the covering multiplicity from one. The comparison applies to all codes of that cardinality. For one-error perfect codes, the coefficient is at least one, and no larger constant holds for all such codes; explicit coefficients depending on the parameters can be much larger. The tiling defect also measures the failure of uniform ball noise to smooth a code distribution. Consequently, the same discrepancy excess gives explicit bounds on holes, overlaps, and divergence from the uniform distribution.

0.52

On Nearly-Perfect Covering Codes Beyond Radius One

cs.IT math.CO ·2026-08-12 ·Gabriel Sac Himelfarb, Moshe Schwartz
theory similarity 0.73
Abstract · 26 pages

We study (binary) nearly-perfect covering codes, which are codes that attain the Van Wee bound with equality. They act as the covering counterparts to nearly-perfect error-correcting codes, which attain the Johnson bound with equality. These codes have been completely classified for covering radius $R=1$. We prove that no code with $R\geq 2$ can attain the original Van Wee bound with equality, since it omits the dependence on the minimum distance of the code. We refine the bound to account for the minimum distance and show some nearly-perfect covering codes. By proving some structural properties of such codes, we prove all nearly-perfect covering codes with $R=2,3$ must be equivalent to the codes we showed. We also prove that for any $R\geq 3$, there are at most a finite number of nearly-perfect covering codes.

0.38

Asymptotic Bounds for Codes in Toroidal Distance

cs.IT ·2026-11-19 ·Pengjie Zhong, Jinquan Luo
theory similarity 0.73
Abstract

The toroidal distance naturally describes the geometry of codes over \(\mathbb Z_q\), where distances are measured modulo \(q\). In this paper, we study asymptotic bounds for codes in \(\mathbb Z_q^n\) under the toroidal metric. We first derive an explicit asymptotic lower bound from the classical Gilbert--Varshamov bounds for the Hamming and Lee metrics, which serves as a baseline for comparison. We then develop a saddle-point approach for the toroidal metric, which yields an asymptotic Gilbert--Varshamov lower bound and an asymptotic Hamming-type upper bound. For \(3\mid q\), we embed ternary Hamming codes into \(\mathbb Z_q^n\) and obtain another asymptotic lower bound for the toroidal metric. In addition, we derive an asymptotic lower bound for Maximum Toroidal Distance (MTD) codes. We compare these lower bounds with the baseline and prove that they are nontrivial in the corresponding parameter ranges. Finally, we compare the asymptotic bounds numerically.

0.15