Gilbert–Varshamov bound

For codes over an alphabet of size $q$, the greedy packing argument gives $A_q(n,d)\ge q^n/V_q(n,d-1)$, where $V_q(n,r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)(q-1{)}^j$. A maximal distance-$d$ code has radius-$(d-1)$ Hamming balls covering the entire space; counting their union proves the lower bound. The linear refinement is the Varshamov bound for linear codes.

// Target: algebra.bigb

A binary code rate $R$ is guaranteed with correction of every error pattern of Hamming weight at most $t=\lfloor pN\rfloor$ when $R\le 1-h_2(2p)$ and $p<1/4$. Choose minimum Hamming distance $2t+1$. The Gilbert–Varshamov bound and entropy bound for a Hamming ball give at least $2^{N(1-h_2(2p))}$ codewords. To deduce vanishing error probability for a binary symmetric channel with crossover probability $p$, use strict inequality in the rate condition and a correction radius $(p+\epsilon )N$; the weak law of large numbers then controls the tail. Correcting exactly the mean number of errors does not by itself ensure reliable transmission.

// Target: algebra.bigb

For $0\le \delta \le 1-1/q$, take logarithms of the Gilbert–Varshamov bound and apply the Hamming ball volume exponent. The Varshamov bound for linear codes gives the same achievable lower bound within linear codes for prime-power $q$.

// Target: algebra.bigb

For a prime-power alphabet size $q$, a linear $[n,k,\ge d]$ code exists if $V_q(n-1,d-2)<q^{n-k}$. Choose parity-check columns successively, avoiding combinations of at most $d-2$ earlier columns. Fewer than $q^{n-k}$ vectors are forbidden, so such a choice is possible. No set of at most $d-1$ columns is dependent, and the resulting kernel has dimension at least $k$.

// Target: probability-and-statistics.bigb