In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert[1] and independently Rom Varshamov[2]) is a bound on the size of a (not necessarily linear) code.
Varshamov proved this bound by using the probabilistic method for linear codes.
For more about that proof, see Gilbert–Varshamov bound for linear codes.
Recall that a code has a minimum distance
of any two elements in the code are at least a distance
Let denote the maximum possible size of a q-ary code
with length n and minimum Hamming distance d (a q-ary code is a code over the field
and minimum Hamming distance
having maximal size: Then for all
such that the Hamming distance
satisfies since otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance
– a contradiction on the maximality of
is contained in the union of all balls of radius
: Now each ball has size since we may allow (or choose) up to
components of a codeword to deviate (from the value of the corresponding component of the ball's centre) to one of
possible other values (recall: the code is q-ary: it takes values in
Hence we deduce That is: For q a prime power, one can improve the bound to