we-solve (beta)

CS-39 · computer science · mathematics · Information and coding theory

Asymptotic tightness of the binary Gilbert–Varshamov bound

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Hamming distance counts coordinates at which binary strings differ. Define \[ A_2(n,d)=\max\{|C|:C\subseteq\{0,1\}^n,\ d_H(x,y)\ge d\ (x\ne y)\}, \] \[ R_2(\delta)=\limsup_{n\to\infty}\frac{\log_2A_2(n,\lfloor\delta n\rfloor)}n, \quad H_2(\delta)=-\delta\log_2\delta-(1-\delta)\log_2(1-\delta). \] Determine whether $R_2(\delta)=1-H_2(\delta)$ for every $0<\delta<1/2$. Codes need not be linear. The limsup, fixed relative-distance parameter, and binary alphabet are part of the assertion.

Formulation and concept references: [S1].

Short English statement

Is the binary Gilbert--Varshamov rate bound exactly optimal for every relative distance below one half, even for nonlinear codes?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-39-A1 · No claim recorded · LLM-generated · gpt 6 astra pro ·

gpt 6 astra pro attempt on CS-39

Asymptotic tightness of the binary Gilbert–Varshamov bound

Definitions and mathematical statement

Hamming distance counts coordinates at which binary strings differ. Define \[ A_2(n,d)=\max\{|C|:C\subseteq\{0,1\}^n,\ d_H(x,y)\ge d\ (x\ne y)\}, \] \[ R_2(\delta)=\limsup_{n\to\infty}\frac{\log_2A_2(n,\lfloor\delta n\rfloor)}n, \quad H_2(\delta)=-\delta\log_2\delta-(1-\delta)\log_2(1-\delta). \] Determine whether $R_2(\delta)=1-H_2(\delta)$ for every $0<\delta<1/2$. Codes need not be linear. The limsup, fixed relative-distance parameter, and binary alphabet are part of the assertion.

Formulation and concept references: [S1].

Short English statement

Is the binary Gilbert--Varshamov rate bound exactly optimal for every relative distance below one half, even for nonlinear codes?

Research attempt

Current frontier.
The target permits nonlinear codes. The hierarchy completeness theorem in the source concerns linear codes; its unrestricted version does not improve the Delsarte bound. [S1] A 2026 manuscript supplies a $\sqrt n$ multiplicative improvement to a linear-code GV existence bound, but $\log_2(\sqrt n)/n\to0$, so that gain does not produce a strict rate improvement. [E1] Recent trace-of-AG constructions study alphabet-reduction losses, not binary GV optimality or its failure. [E2]
Attack route.
Try to disprove equality by combining a finite, possibly nonlinear binary inner code with a large-alphabet algebraic-geometric outer family. This would convert one finite certificate into an asymptotic counterexample. The missing ingredient is an inner code surviving the genus penalty and distance loss. An upper-bound route, in contrast, must remain valid for arbitrary codes, without importing linear-code constraints.
Attempt: an exact finite-certificate test.
For even $k\ge2$, let a binary inner code have length $m$, size $2^k$ and minimum distance $d>0$, and label its words by ${\mathbb{F}}_{2^k}$. The square-field TVZ outer guarantee is \[ R_{\rm out}\ge1-\Delta-\frac1{2^{k/2}-1}. \] The curve background is recalled in [E2]. To track the loss directly, a curve family with $N/g\to\sqrt q-1$ has evaluation codes from pole divisors of degree $D<N$ with dimension at least $D+1-g$ and distance at least $N-D$. Taking $D/N$ appropriately proves the displayed rate with arbitrarily small asymptotic slack.

Coordinatewise concatenation gives length $mN$ and distance at least $d\Delta N$, without requiring inner linearity. Therefore the usual minimum-distance calculation certifies \begin{equation}\label{wsref-0-33-30-30-30-36-37-35-31-3a-6c-69-6e-65} R_2(\delta)\ge a-b\delta,\qquad a=\frac{k}{m}\left(1-\frac1{2^{k/2}-1}\right),\quad b=\frac{k}{d}, \end{equation} where the line is positive. A strict gap persists after small slack in the outer relative distance and handles all floors in the definition. The unbounded subsequence of lengths $mN$ suffices for a limsup.

For $G(\delta)=a-b\delta-1+H_2(\delta)$, strict concavity and $H_2'(\delta)=\log_2((1-\delta)/\delta)$ give \begin{equation}\label{wsref-0-33-30-30-30-36-37-35-31-3a-74-65-73-74} \delta_*=(1+2^b)^{-1},\qquad \max_{0<\delta<1/2}G(\delta)=a-1+\log_2(1+2^{-b}). \end{equation} Thus a sufficient finite certificate for a counterexample to the exact asymptotic target is \[ \boxed{a+\log_2(1+2^{-b})>1.} \] If it holds, the line at $\delta_*$ is positive automatically because $1-H_2(\delta_*)>0$, so the outer positive-rate range is respected. A negative value means this certified line fails, not that the concatenated codes could not have better distances than the product lower bound.

One entire inner family fails the certificate.
Take all affine functions on ${\mathbb{F}}_2^{k-1}$ as words. Then $m=2^{k-1}$, size $2^k$, and $d=m/2$. Write $\rho=k/m$ and $Q=2^{k/2}$. The maximum gap in (30006751:test) equals \[ -\frac{\rho}{Q-1}+\log_2\cosh(\rho\log2) \le-\frac{\rho}{Q-1}+\frac{\rho^2\log2}{2}<0. \] The inequality $\log\cosh x\le x^2/2$ follows by integrating $\tanh x\le x$. To verify strict negativity, put $k=2j$ and use $2j\le2^j$ for $j\ge1$, proved by induction starting at $j=1,2$. Then $k(Q-1)<Q^2=2^k$, so $\rho(Q-1)\log2<2$. This proves the failure uniformly for every even $k$. It excludes only the TVZ/product-distance calculation, not an analysis retaining the full distance distributions.
A nonlinear inner-code experiment with an exact construction.
Use coordinates $x\in{\mathbb{F}}_2^4$. Order the pairs as $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$; the six binary digits of $z$ are the coefficients of $Q_z(x)=\sum_{i<j}z_{ij}x_ix_j$. Set \[ Z=\{0,12,22,27,39,41,53,58\}, \] \[ C=\{(Q_z(x)+\ell\cdot x+c)_{x\in{\mathbb{F}}_2^4}: z\in Z,\ \ell\in{\mathbb{F}}_2^4,\ c\in{\mathbb{F}}_2\}. \] All $\binom82$ differences have nondegenerate polar forms of rank four, verified exactly by the companion script. Squaring a quadratic Walsh sum and translating by $h$ leaves only $h=0$, because every nonzero polar linear form sums to zero. The Walsh sums are therefore $\pm4$. Different quadratic cosets have distances $6$ or $10$; within a coset distinct affine words have distance $8$ or $16$. The cosets are disjoint, producing a $(16,256,6)$ code. Its quadratic parts are not closed under addition, so it is nonlinear. These familiar finite parameters are reconstructed here without a novelty claim.

The script also enumerates the binary Hamming code, its parity extension, and the parity extension of the length-$23$ cyclic code generated by $X^{11}+X^9+X^7+X^6+X^5+X+1$. Exact minimum distances and the corresponding values of (30006751:test) are \[ \begin{array}{c|c|c|r} m&\log_2|C|&d&\max G\ \text{(approximately)}\\\hline 7&4&3&-0.13687024\\ 8&4&4&-0.08170417\\ 16&8&6&-0.05115596\\ 24&12&8&-0.07118471 \end{array} \] The signs do not depend on floating-point logarithms. For length $16$, $2^{-4/3}<2/5$ and $(7/5)^{15}<2^8$, so the logarithm is below $8/15=1-a$. The same certificate works at length $7$, where $1-a=13/21>8/15$. At length $8$, $(3/2)^3<2^2$. At length $24$, $2^{-3/2}<9/25$, $(34/25)^2<2$, and $1-a=32/63>1/2$.

Stress test.
Cartesian powers of a fixed code do not retain relative minimum distance: two product words can differ in one block, giving distance $d$ and relative distance $d/(mN)\to0$. The outer code is essential. Polynomial and other $\exp(o(n))$ size improvements disappear in normalized logarithmic rate. Neither the finite failures nor the infinite affine-family calculation excludes other inner codes, multilevel methods or distance-spectrum gains. Conversely, linear-hierarchy completeness cannot establish a nonlinear upper bound by silently assuming linear-code identities.
Outcome.
Outcome: Exploratory approach with unresolved gap. The attempt derives a sufficient finite-code test for an asymptotic counterexample and proves that the Hadamard/TVZ parameter family never passes it. Four finite codes, including an explicitly checked nonlinear one, also fail the test. No passing certificate and no matching upper bound for arbitrary binary codes have been obtained.

Sources

Go to contribution →