Every error-correcting code bound
The four ceiling-and-floor bounds on (n, M, d), and what each one's argument actually proves.
Reach for this when checking whether a proposed code's parameters are even possible, or when comparing how close an actual construction (like a Hamming code) comes to the best achievable.
Ceilings — M can never exceed these
For a binary code with M codewords, length n, and minimum distance d_{min}=d:
Hamming (sphere-packing) bound, an upper bound on M: M \leq \frac{2^n}{\sum_{i=0}^{t}\binom{n}{i}}, \qquad t=\left\lfloor\frac{d-1}2\right\rfloor.
Singleton bound, an upper bound on M: M \leq 2^{n-d+1}.
Plotkin bound, an upper bound on M (valid for d>n/2): M \leq 2\left\lfloor\frac{d}{2d-n}\right\rfloor.
Gilbert-Varshamov bound, a LOWER bound: a code with these parameters is guaranteed to EXIST whenever M \geq \frac{2^n}{\sum_{i=0}^{d-1}\binom{n}{i}}.
Example
All four bounds together, with each one's proof.
Show proof
Hamming bound. Around each codeword, a "sphere" of radius t (every vector within Hamming distance t) contains \sum_{i=0}^{t}\binom{n}{i} vectors. Since d\geq2t+1, any two distinct codewords' spheres are disjoint (a vector within t of two different codewords would put those codewords within 2t<d of each other, contradicting the minimum distance). M disjoint spheres, each of that size, must fit inside the full space of 2^n vectors, giving the bound.
Singleton bound. Take any code \mathcal{C} with M codewords and minimum distance d. Deleting any d-1 fixed coordinate positions from every codeword cannot make two DISTINCT codewords collide — if it did, the two original codewords would already agree everywhere outside those d-1 positions, differing in at most d-1 places, contradicting d_{min}=d. So the M shortened codewords, now length n-d+1, are still all distinct, and there are only 2^{n-d+1} possible vectors of that length to be distinct among.
Plotkin bound. Sum the Hamming distance between every pair of the M codewords two ways. Directly, each of the \binom{M}2 pairs contributes at least d, for a total of at least d\binom{M}2. Counted column by column instead: in column j, if w_j codewords have a 1 there, that column contributes w_j(M-w_j) to the pairwise-distance sum (each of the w_j ones pairs with each of the M-w_j zeros), maximized at M^2/4 when w_j=M/2 — so the total across all n columns is at most nM^2/4. Combining, d\binom{M}2 \leq nM^2/4, which rearranges (using 2d>n) to the stated bound.
Gilbert-Varshamov bound. A greedy argument: build a code one codeword at a time, always adding a new vector at distance \geq d from every codeword chosen so far. Adding a codeword "forbids" every vector within distance d-1 of it — a sphere of size \sum_{i=0}^{d-1}\binom{n}{i} — from ever being chosen later. As long as already-chosen codewords' forbidden spheres haven't covered the entire space of 2^n vectors, another codeword can still be added. This process is guaranteed to reach at least M=2^n/\sum_{i=0}^{d-1}\binom{n}{i} codewords before every vector is forbidden.