Gilbert–Varshamov bound

The Gilbert–Varshamov bound guarantees the existence of error-correcting codes whose size is at least the ambient space divided by the volume of a Hamming ball of radius one less than their minimum distance.

Greedy algorithm: An algorithm that repeatedly makes a locally optimal choice to build a solution. The Gilbert–Varshamov argument greedily selects codewords and removes nearby candidates.
Error-correcting code: A set of encoded messages designed so that transmission errors can be detected or corrected. The bound describes how many codewords can exist at a given length and distance.
Asymptotic coding theory: The study of coding parameters as block length tends to infinity. The bound becomes a rate-versus-distance guarantee in the long-code limit.
Plotkin bound: An upper bound on code size when the relative minimum distance is sufficiently large. It limits code size in a high-distance regime where the Gilbert–Varshamov guarantee is weaker.
Hamming distance: The number of coordinate positions in which two strings of equal length differ. Codewords must be separated by at least the prescribed minimum Hamming distance.
Code rate: The ratio of a code’s information content to its block length, often measured in bits per symbol. Taking logarithms of the size bound yields an asymptotic lower bound on achievable rate.
Binary symmetric channel: A communication channel that independently flips each transmitted bit with a fixed probability. Codes meeting the bound can be assessed against error rates in this standard channel model.
Elias–Bassalygo bound: An upper bound on code size derived by averaging codewords inside Hamming balls. It sharpens sphere-packing-style limits and can narrow the gap above the existence bound.
Hamming ball: The set of strings within a specified Hamming distance of a fixed string. The bound counts how many candidate strings each selected codeword rules out.
Code distance: A measure of the separation between distinct codewords, commonly the minimum Hamming distance. The distance constraint sets the error-correction capability and the bound’s excluded-ball radius.

Linked from 2 pages

Hamming boundCompared with: It provides an existence guarantee, complementing the Hamming bound's upper limit.