Math Conjectures

Binary asymptotic rate–distance improvement problem

OPENMajorOpen problemProposed 1952–1957 · Standard version

Canonical statement

For 0<δ<1/20<\delta<1/2, let A2(n,d)A_2(n,d) be the largest cardinality of a set C⊆{0,1}nC\subseteq\{0,1\}^n whose distinct words have Hamming distance at least dd, and define
R2(δ)=lim sup⁡n→∞1nlog⁡2A2(n,⌈δn⌉). R_2(\delta)=\limsup_{n\to\infty}\frac1n\log_2 A_2(n,\lceil\delta n\rceil).
Decide whether there exists δ∈(0,1/2)\delta\in(0,1/2) for which
R2(δ)>1−H2(δ),H2(t)=−tlog⁡2t−(1−t)log⁡2(1−t). R_2(\delta)>1-H_2(\delta),\qquad H_2(t)=-t\log_2t-(1-t)\log_2(1-t).
View source LaTeX
For \(0<\delta<1/2\), let \(A_2(n,d)\) be the largest cardinality of a set \(C\subseteq\{0,1\}^n\) whose distinct words have Hamming distance at least \(d\), and define
\[
R_2(\delta)=\limsup_{n\to\infty}\frac1n\log_2 A_2(n,\lceil\delta n\rceil).
\]
Decide whether there exists \(\delta\in(0,1/2)\) for which
\[
R_2(\delta)>1-H_2(\delta),\qquad H_2(t)=-t\log_2t-(1-t)\log_2(1-t).
\]
INFO-003:[Gilbert1952Comparison][Varshamov1957Codes][McElieceEtAl1977Bounds][OpenAI2026TenAdvances]
Information theoryCombinatorics

Notes

For relative distance δ∈(0,1/2)\delta\in(0,1/2), let R2(δ)R_2(\delta) denote the best asymptotic rate of binary codes with minimum Hamming distance δn\delta n. The Gilbert–Varshamov bound, originating in Gilbert's 1952 comparison of signalling alphabets [Gilbert1952Comparison] and Varshamov's 1957 estimate of the number of signals in error-correcting codes [Varshamov1957Codes], shows R2(δ)≥1−H2(δ)R_2(\delta)\ge 1-H_2(\delta) by a greedy or random-choice argument. The problem asks whether any binary code family beats this curve at some fixed δ\delta.

Despite some seventy years of constructions, no improvement is known at any positive relative distance. From above, the best known upper bounds, including the linear-programming bounds of McEliece, Rodemich, Rumsey and Welch, remain strictly above the Gilbert–Varshamov curve [McElieceEtAl1977Bounds], so the truth is undetermined in either direction. Over sufficiently large non-binary alphabets, algebraic-geometry codes do exceed the corresponding qq-ary bound, and recent work investigates whether algebraic-geometry techniques can be brought to bear on meeting the binary bound [CohenEtAl2026Tracing].

The question is open both ways: a resolution requires either a family of binary codes with rate exceeding 1−H2(δ)1-H_2(\delta) at some fixed δ\delta, or upper-bound methods strong enough to prove R2(δ)=1−H2(δ)R_2(\delta)=1-H_2(\delta) everywhere.

Proof-claim watch (1)

Exponential improvements for binary and spherical code upper bounds

Grade C

Substantive progress claim pending verification; it does not settle either exact rate function or beat the binary Gilbert–Varshamov lower curve.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.