Gilbert–Varshamov Bound

An existential lower bound on the maximum size M of a q-ary block code of length n and minimum Hamming distance d: there exists a code with at least M ≥ q^n / V_q(n,d-1) codewords, where V_q(n,d-1)=∑_{i=0}^{d-1} binom(n,i)(q-1)^i (equivalently derived via a greedy construction). The bound guarantees existence (but not efficient constructibility) of codes meeting these parameters.