Gilbert–Varshamov bound
= Gilbert–Varshamov bound
{c}
{wiki}
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\binom nj(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