Gilbert-Varshamov Bound

In coding theory, the Gilbert-Varshamov bound is a lower bound on the size of a code, not necessarily a linear one. It is due to Edgar Gilbert and, independently, Rom Varshamov, and is occasionally called the Gilbert-Shannon-Varshamov bound or the GSV bound, though the first name is by far the most popular. It states that the maximum possible size of a q-ary code of length n and minimum Hamming distance d is at least q to the power n divided by the number of words in a Hamming ball of radius d minus one. The argument takes a code of maximal size and observes that balls of that radius around its codewords must cover the whole space, since otherwise another word could be added. Varshamov proved the bound by the probabilistic method for linear codes, and for a prime power q the bound can be improved.