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