8 Gilbert–Varshamov Bound
8.1 Overview
This chapter proves the Gilbert–Varshamov (GV) existence bound: for any block-length \(n\), dimension \(k\), and distance \(d\), if
\[ k \; \le \; n - \lceil \log _q \mathrm{Vol}(n,d-1)\rceil - 1, \]
then there exists an \(n\times k\) generator matrix whose associated linear code has minimum distance at least \(d\).
The proof is a probabilistic (union-bound) counting argument over random generator matrices.
8.2 Probabilistic bound on low-weight outputs
For any nonzero \(x\in \alpha ^k\),
\[ \frac{|\{ G : \mathrm{wt}(Gx) \lt d\} |}{|\alpha |^{nk}} \; \le \; \frac{|B_{d-1}(\mathbf{0})|}{|\alpha |^n}. \]
8.3 Union bound over bad matrices
The number of \(n\times k\) matrices that send some nonzero message to a codeword of weight \(\lt d\) is at most
\[ (|\alpha |^k-1)\cdot |\alpha |^{nk-n}\cdot |B_{d-1}(\mathbf{0})|. \]
8.4 Gilbert–Varshamov bound
If \(k \le n - \lceil \log _q|B_{d-1}(\mathbf{0})|\rceil - 1\), then there exists a generator matrix \(G\) such that every nonzero message is mapped to a codeword of Hamming weight at least \(d\).