10 Lectures and 42 Open Problems — Gilbert-Varshamov bound

Binary Gilbert--Varshamov targets: derandomization cost and rate normalization

Definitions and mathematical statement

A binary code of block length $n$ is a subset $C\subseteq\{0,1\}^n$. Its minimum distance is the least Hamming distance between distinct codewords, where Hamming distance counts differing coordinates. Write $A_2(n,d)$ for the largest size of a binary code with minimum distance at least $d$, and define \[ R_2(\delta)=\limsup_{n\to\infty} \frac1n\log_2 A_2(n,\lceil\delta n\rceil), \qquad 0<\delta<\tfrac12. \] The binary entropy function is $H_2(\delta)=-\delta\log_2\delta-(1-\delta)\log_2(1-\delta)$. The Gilbert--Varshamov bound asserts $R_2(\delta)\ge1-H_2(\delta)$.

The source asks two distinct questions. First, construct deterministic explicit code families attaining this rate: for each fixed $\delta$ and $\varepsilon>0$, obtain arbitrarily large block lengths with relative distance at least $\delta$ and rate at least $1-H_2(\delta)-\varepsilon$, together with a construction and encoding procedure polynomial in the block length. A linear construction can be specified by a generator matrix; nonlinear codes require another succinct, efficiently evaluable encoder.

Second, is $R_2(\delta)=1-H_2(\delta)$ throughout this interval, or can binary codes asymptotically exceed the bound? This extremal question allows nonlinear codes and places no computational restriction on them. Efficient decoding is a separate desirable property, not an extra hypothesis of the two stated questions. Exponential enumeration of all codewords does not supply the requested efficient explicitness.

Short English statement

Construct explicit binary codes attaining the Gilbert–Varshamov rate, and determine whether that rate is optimal among all binary codes.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2800701 (AMR-027-0701), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Bandeira - 42 Open Problems in Data Science $2016$, Open Problem 7.1. Original source indexed by AMR-027-0701. https://afonsobandeira.wordpress.com/2015/11/27/10l42grouptesting/.
• S3 A. S. Bandeira, Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science, corresponding numbered problem and surrounding definitions. https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf.

Verbatim supplied catalogue question

Explicit deterministic constructions of codes achieving the GV bound Is the GV bound tight?

Attempt and results

The two questions have different quantifiers. An efficiently explicit family requires a polynomial-time construction and encoder at arbitrarily large lengths for each fixed $0<\delta<1/2$ and $\varepsilon>0$. The extremal rate question permits every binary code, linear or nonlinear. Neither question is settled by enumerating exponentially many words.

Random linear coding and the attempted conditional-expectation route.

Let $G\in\mathbb F_2^{k\times n}$ have independent uniform entries. For each nonzero message $u\in\mathbb F_2^k$, the word $uG$ is uniform on $\mathbb F_2^n$: each column has a nonzero linear functional applied to it, so its output bit is uniform, and columns are independent. Let $B$ count nonzero $u$ with $w(uG)<d$. Then \[ \mathbb EB=(2^k-1)2^{-n}\sum_{j=0}^{d-1}\binom nj. \] If this is less than one, some $G$ has $B=0$. Such $G$ is injective on messages, since $d\ge1$ excludes a nonzero message mapping to zero, and its code has $2^k$ words and minimum distance at least $d$ by linearity. One can make this existence proof deterministic by revealing matrix entries and choosing the value that does not increase $\mathbb E[B\mid\text{revealed entries}]$. At each step the two conditional expectations average to the previous one. The final nonnegative integer $B$ is less than one, hence zero. However, the direct evaluator sums over $2^k-1$ messages. For each message, the revealed entries determine some output parities while the remaining random output coordinates are independent unbiased bits, allowing an exact binomial-tail computation. This gives an exponential-size straightforward algorithm, not the requested polynomial-time construction when $k=\Theta(n)$. The attempted derandomization lacks a polynomial-time representation and evaluation of that sum. No lower bound on all possible evaluators is claimed.

Entropy scale and why a polynomial factor does not settle it.

For $0<q<1/2$ and $r=\lfloor qn\rfloor$, put $t=q/(1-q)<1$. For $j\le r$, $t^j\ge t^r$, so the binomial theorem gives \[ \sum_{j=0}^{r}\binom nj\le t^{-r}(1+t)^n \le t^{-qn}(1+t)^n=2^{nH_2(q)}. \] This rederives the entropy exponent in the existence argument (with any fixed rate slack absorbing integer rounding). If a lower bound on code size is multiplied by a factor $f(n)$ with $1\le f(n)\le Cn^a$, the normalized base-two logarithm changes by at most $(\log_2 C+a\log_2 n)/n\to0$. Thus such an improvement of cardinality alone does not prove $R_2(\delta)>1-H_2(\delta)$.

A finite illustration, not an asymptotic construction.

Let $H$ be the $3$ by $7$ matrix whose columns are the seven distinct nonzero binary triples. Its rank is three, so $\ker H$ has dimension four. No word of weight one or two is in the kernel, since no column is zero and no two columns agree. Three columns $e_1,e_2,e_1+e_2$ sum to zero, so the minimum distance is exactly three. This code has sixteen words, while the elementary volume expression is $2^7/(1+7+21)=128/29$. The strict finite improvement says nothing by itself about a positive asymptotic rate gap.

Context and adversarial audit

Jiang and Vardy's primary abstract, arXiv:math/0404325, was consulted on 11 October 2026. Its extra factor is proportional to the logarithm of a Hamming-ball volume, hence at most linear in block length. We do not adopt the source-row summary's inference that this settles asymptotic optimality of the binary entropy rate. Its finite-size improvement and the target rate question are kept separate. The calculations here are classical, reproduced to expose the failed inference and computational gap. The audit checked encoder succinctness, injectivity, fixed-rate slack, and linear versus nonlinear scope. No actual code enumeration or theorem prover was used.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. No polynomial-time conditional-expectation evaluator or explicit GV family is obtained, and no positive asymptotic rate gap or matching upper bound is proved for all binary codes.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Bandeira, lecture notes $2016$, Open Problem 7.1; both source questions inspected. https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf.
• Tao Jiang and Alexander Vardy, Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes $2004$; primary abstract and its multiplicative factor inspected. https://arxiv.org/abs/math/0404325.

Final status

Unresolved in this attempt. No polynomial-time conditional-expectation evaluator or explicit GV family is obtained, and no positive asymptotic rate gap or matching upper bound is proved for all binary codes.