Asymptotically unit-rate storage codes from binary BCH codes
Abstract
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 𝔽2m, we prove that the storage deficiency is Θ(((1+√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.
Related
- Asymptotically good binary triorthogonal codes and higher-level transversal gates
- Asymptotically Tight Bounds for Generalized Covering Radii of Binary Primitive BCH Codes at All Higher Orders
- The Rate of the Delsarte Bound for Binary Codes and Spheres
- The half-rate linear programming bound for binary codes is 1/2−1/π
- Explicit and asymptotically good constructions of Algebraic Geometry codes in the sum-rank metric
BibTeX
@misc{zabokritskiy2026asymptotically,
title = {{Asymptotically unit-rate storage codes from binary BCH codes}},
author = {Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01733},
eprint = {2610.01733},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01733},
}
RIS
TY - UNPB
TI - Asymptotically unit-rate storage codes from binary BCH codes
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01733
UR - https://arxiv.org/abs/2610.01733
AB - 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 𝔽_2^m, we prove that the storage deficiency is Θ(((1+√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.
ER -