The optimal asymptotic rate of binary error-correcting codes
For integers $1 \le d \le n$ let $A_2(n,d)$ be the largest size of a binary code $C \subseteq \{0,1\}^n$, linear or not, in which any two distinct words are at Hamming distance at least $d$. For $0 < \delta < 1/2$ let $$R_2(\delta) = \limsup_{n \to \infty} \frac{1}{n} \log_2 A_2\bigl(n, \lceil \delta n \rceil\bigr).$$ The Gilbert–Varshamov bound gives $R_2(\delta) \ge 1 - h_2(\delta)$, where $h_2(t) = -t \log_2 t - (1-t) \log_2 (1-t)$. McEliece, Rodemich, Rumsey and Welch proved $R_2(\delta) \le h_2\bigl(1/2 - \sqrt{\delta(1-\delta)}\bigr)$ and a second, stronger linear programming bound for small $\delta$ (1977). Alrabiah and Guruswami improved both of these upper bounds strictly for every $0 < \delta < 1/2$ (2026).
Problem. Determine $R_2(\delta)$ for every $0 < \delta < 1/2$.
Source: Classical, as the gap between the lower bound of Gilbert (1952) and Varshamov (1957) and the upper bounds of McEliece, Rodemich, Rumsey and Welch (1977); stated in this form, with ⌊δn⌋, by Coregliano, Jeronimo and Jones (2022), §1. Stated by AIM — Open Applied Problems with ⌈δn⌉.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- IT — Information Theory
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, error-correcting codes, Gilbert–Varshamov bound, linear programming bounds
References
@article{gilbert1952,
author = {Gilbert, E. N.},
title = {A comparison of signalling alphabets},
journal = {Bell System Tech. J.},
volume = {31},
number = {3},
year = {1952},
pages = {504--522},
doi = {10.1002/j.1538-7305.1952.tb01393.x},
}
@article{varshamov1957,
author = {Varshamov, R. R.},
title = {Estimate of the number of signals in error correcting codes},
journal = {Dokl. Akad. Nauk SSSR},
volume = {117},
year = {1957},
pages = {739--741},
note = {In Russian},
}
@article{mceliece1977,
author = {McEliece, Robert J. and Rodemich, Eugene R. and Rumsey, Jr., Howard and Welch, Lloyd R.},
title = {New upper bounds on the rate of a code via the {D}elsarte--{M}ac{W}illiams inequalities},
journal = {IEEE Trans. Inform. Theory},
volume = {23},
number = {2},
year = {1977},
pages = {157--166},
doi = {10.1109/TIT.1977.1055688},
}
@inproceedings{coregliano2022,
author = {Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris},
title = {A complete linear programming hierarchy for linear codes},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
series = {LIPIcs},
volume = {215},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2022},
pages = {51:1--51:22},
doi = {10.4230/LIPIcs.ITCS.2022.51},
eprint = {2112.09221},
archivePrefix = {arXiv},
}
@misc{alrabiah2026,
author = {Alrabiah, Omar and Guruswami, Venkatesan},
title = {Binary code rate bounds via classical--quantum channels},
year = {2026},
eprint = {2608.09347},
archivePrefix = {arXiv},
}
@misc{aim-binary-code-asymptotic-rate,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The optimal asymptotic rate of binary error-correcting codes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/331-binary-code-asymptotic-rate.md},
note = {Entry 331 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00501, "The optimal asymptotic rate of binary error-correcting codes", clopen.solutions.