Three Improved Lower Bounds for Binary Error-Correcting Codes
Abstract
Error-correcting codes are a foundational technology for representing information robustly against noise in communication and data storage. The binary code packing problem, which seeks to maximize the number of codewords at a fixed code length and minimum distance, is a fundamental problem in coding theory that remains open for many parameter choices. We give explicit binary codes with parameters (n,M,d)=(22,84,9), $(24,196,9)$, and $(25,65,11)$, where n, M, and d denote the code length, number of codewords, and minimum distance, respectively. These establish the lower bounds A2(22,9)≥84, A2(24,9)≥196, and A2(25,11)≥65, where A2(n,d) denotes the maximum possible number of codewords, improving the respective lower bounds 80, 192, and 64 in the public table of general binary codes. Most notably, the third result improves the lower bound supplied by a lexicographic construction for the first time in 66 years, while the first two improve bounds that have stood for 21 years. The new codes represent more messages without changing the code length or error-correction guarantees, with gains compounding multiplicatively across blocks. We release all codewords and an exhaustive verifier to enable independent verification.
Related
- Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
- Improved bounds for constant-power and low-power error-correcting cooling codes
- Improved Explicit and Algorithmic Lower Bounds for r(5,t)
- Stability for the adjoint Finner inequality and improved lower bounds on the k-plane transform
- Improved Gradient Descent Lower Bounds Beyond Nesterov
BibTeX
@misc{ota2026three,
title = {{Three Improved Lower Bounds for Binary Error-Correcting Codes}},
author = {Kazuki Ota and Takayuki Osa and Tatsuya Harada},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11609},
eprint = {2610.11609},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11609},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Three Improved Lower Bounds for Binary Error-Correcting Codes
AU - Kazuki Ota
AU - Takayuki Osa
AU - Tatsuya Harada
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11609
UR - https://arxiv.org/abs/2610.11609
AB - Error-correcting codes are a foundational technology for representing information robustly against noise in communication and data storage. The binary code packing problem, which seeks to maximize the number of codewords at a fixed code length and minimum distance, is a fundamental problem in coding theory that remains open for many parameter choices. We give explicit binary codes with parameters (n,M,d)=(22,84,9), $(24,196,9)$, and $(25,65,11)$, where n, M, and d denote the code length, number of codewords, and minimum distance, respectively. These establish the lower bounds A_2(22,9)≥84, A_2(24,9)≥196, and A_2(25,11)≥65, where A_2(n,d) denotes the maximum possible number of codewords, improving the respective lower bounds 80, 192, and 64 in the public table of general binary codes. Most notably, the third result improves the lower bound supplied by a lexicographic construction for the first time in 66 years, while the first two improve bounds that have stood for 21 years. The new codes represent more messages without changing the code length or error-correction guarantees, with gains compounding multiplicatively across blocks. We release all codewords and an exhaustive verifier to enable independent verification.
ER -