CS Paper Radar

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

Zeev Vladimir Belinsky, Aryeh Lev Zabokritskiy

cs.IT ·submitted 2026-08-24 21:21 UTC · v2
theoryhighly cited

Abstract

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.

Comment
56 pages. Revised version with a componentwise degree bound improving the sufficient field-size threshold for the known common-core support bound; full second-order results and proofs retained

Closest papers

Nearest neighbours by meaning across the whole index.

Auxiliary Codes and the Generalized Packing-Covering Conjecture

cs.IT ·2026-09-16 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
theory similarity 0.76
Abstract · 10 pages, 2 tables. Revised exposition and references; clarified the auxiliary-code method and improved presentation

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.

0.37

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.75
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

Subspace coverings and generalized covering radii of generalized Zetterberg codes

cs.IT math.CO ·2026-09-20 ·Shitao Li, Yang Li, Gaojun Luo, Zhonghua Sun
theory similarity 0.70
Abstract

Generalized covering radii measure how many columns of a parity-check matrix are needed to generate several syndromes simultaneously. Their finite-geometric counterparts are $(ρ,t)$-saturating sets, for which every $t$-dimensional subspace is contained in a subspace generated by at most $ρ$ prescribed vectors. We investigate this covering problem for the norm-one configurations associated with generalized Zetterberg codes. We establish the upper bound $2t+1$ over every nonbinary finite field and in an explicit binary range, together with complementary lower bounds obtained by counting subspaces and constructing subfield obstructions. For an explicit range of large $t$, these configurations are $t$-strong blocking sets, and the $t^{\rm th}$ generalized covering radius attains its minimum possible value $t$. For binary Zetterberg codes, we determine the second generalized covering radius in every extension degree and prove that the third radius is seven for an infinite subfamily.

0.36

Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields

cs.IT cs.CC ·2026-10-11 ·Minshen Zhu
similarity 0.69
Abstract

Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate $0<R<1$, there exists $\varepsilon_R>0$ such that, for all sufficiently large $h$, the full-field Reed--Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{Ω_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_R$. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.

0.36

Asymptotically unit-rate storage codes from binary BCH codes

cs.IT math.CO ·2026-10-01 ·Aryeh Lev Zabokritskiy
theory similarity 0.69
Abstract · 11 pages, no figures

A storage code on a graph assigns a symbol to each vertex so that the symbol can be recovered from its neighbors. We prove that the binary full-parity storage codes on triangle-free coset graphs of primitive BCH codes have rate tending to one for every fixed error-correction capability of at least two. The conclusion also holds for an increasing error budget under an explicit growth condition. The proof bounds the binary rank of convolution matrices associated with polynomial maps. Low coordinate degree forces cancellation in the polynomial representing the image, and a polynomial rank bound converts this cancellation into a quantitative estimate for the storage rate. For the double-error-correcting family over $\mathbb{F}_{2^m}$, we prove that the storage deficiency is $Θ(((1+\sqrt{5})/4)^m)$. This refinement follows from an exact Fibonacci formula for a polynomial coefficient rank and a matching exponential lower bound after finite-field evaluation.

0.12

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.69
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Hamming and Johnson-Type Bounds for Joint Error Correction and Detection

cs.IT ·2026-11-13 ·Yulin Chen, Raymond W. Yeung
similarity 0.68
Abstract · This manuscript is a preliminary draft and is currently being revised. The final version will be posted once the revisions are complete. Com…

We derive upper bounds on the size of codes for joint error correction and detection over classical $q$-ary Hamming spaces. A $(c,c')$ joint error correcting and detecting code corrects every error of weight at most $c$ and detects every error whose weight lies between $c+1$ and $c+c'$. We establish equivalent conditions for this decoding requirement using Hamming balls and Hamming rings, and derive a joint bound that reduces to the Hamming bound when $c'=0$. We introduce joint perfect codes and show that binary repetition codes attain the joint bound whenever $n=2c+c'+1$. For codes satisfying $d_{\min}=2c+c'+1$, we investigate an alternative joint bound based on ring multiplicity and constant-weight code bounds. A further argument using the Cauchy-Schwarz inequality and pairwise ring intersections yields a refined joint bound that is always at least as strong as the original joint bound. We then incorporate an additional outer Hamming shell to obtain a Johnson-type extension. This extension provides a strict improvement for binary codes with $c'=1$, $d_{\min}=2c+2$, $c\geq2$, and $d_{\min}+2\leq n\leq3d_{\min}/2-1$. These results connect sphere-packing bounds with the geometry of joint error correction and detection.

0.12

Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size

cs.IT cs.DSmath.CO ·2026-09-04 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.67
Abstract

We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed--Muller codes. We then recover the result that random Reed--Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap $\varepsilon$ from $2^{O(1/\varepsilon^2)}$ to $2^{O(1/\varepsilon)}$. Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.

0.35