Motivation
A code trades the number of possible messages for separation between its words. Packing balls explains why reliable correction consumes space. Covering by larger balls explains why reasonably large separated sets exist. Counting pairs of words supplies a different obstruction when the requested relative distance is very large.
These arguments answer different questions. An upper bound limits every code. A lower existence bound guarantees at least one code, often without a useful decoder. An explicit construction may outperform that lower guarantee without contradicting it. We will keep those directions visible, including when passing from finite block lengths to asymptotic rates.
The counting arguments initially require only a finite alphabet. The linear existence proof additionally requires a finite field, but it will not assume independent nonzero codewords, full-rank random matrices or an efficient search algorithm.
Definitions
Definition 1.3.1
(Codes, balls and rate)
Let an alphabet have symbols. A length- code is a subset of its -fold Cartesian power, with size . For its minimum Hamming distance is the smallest distance between distinct codewords. We restrict the finite parameter statements to integers and codes with distance at least .
Write
This is the number of words in a radius- ball: choose the changed positions and one of replacement symbols at each. Every center has the same ball size. The rate is . For a linear code over with dimension , this becomes .
Definition 1.3.2
(The -ary entropy function)
For , define
with endpoint values by continuity. Its derivative is , so it increases on and reaches one at the right endpoint. This monotonicity restriction matters in volume estimates.
Theorem/proposition
Theorem 1.3.3
(Finite packing and covering bounds)
Every length- distance-at-least- code satisfies
There exists a code of distance at least with . The first statement is the Hamming bound, the second is Singleton's bound, and the existence statement is the Gilbert covering argument.
Theorem 1.3.4
(A linear existence guarantee)
When is a prime power, put . For any integer with , there is a linear code over of dimension at least and distance at least . For the sum is zero and is allowed.
Theorem 1.3.5
(Plotkin's pair-counting bound)
Put . If , every such code has
The integer size may be bounded by the floor of the right-hand side. The hypothesis is strict: at equality the displayed denominator vanishes and this argument supplies no finite size bound.
Proof sketch or proof idea
Disjoint small balls and covering large balls
Proof
(Disjoint balls, puncturing and a maximal code)
Set . If a word belonged to radius- balls about two distinct codewords, the triangle inequality would place their distance at most . Thus these balls are disjoint and their total size cannot exceed , proving Hamming's bound. The counting proves a restriction; it does not implement a decoder.
For Singleton's bound, delete any coordinate positions. Two codewords with the same remaining coordinates would differ in at most the deleted positions, contradicting distance at least . The puncturing map is therefore injective into the remaining words. This argument does not require linearity.
For existence, start with no words and repeatedly add a word at distance at least from every selected word until this is impossible. Finiteness guarantees termination. The resulting code is maximal under inclusion. Every ambient word must then lie within distance of a selected center, since otherwise it could be added. The balls cover the ambient space; overlapping is allowed. Their total size is at least the size of their union, giving .
Proof X-ray
The same union comparison points in two directions
For small disjoint balls, the sum of sizes equals the union and is at most the ambient size. For larger covering balls, the sum is at least the union, which equals the ambient space. The existence proof relies on maximality under inclusion, not on finding a largest possible code. Enumerating the whole ambient space would generally cost exponentially many steps in block length.
Random checks exclude projective low-weight directions
Proof
(A union bound over low-weight directions)
Now use . Choose an by matrix with independent uniform entries. For each fixed nonzero vector , a row dot product with is uniform in : choose a nonzero coordinate of , condition on the other row entries and use the bijection in the remaining entry. Independent rows give .
Nonzero scalar multiples of have exactly the same vanishing event. Nonzero vectors of weight less than split into one-dimensional subspaces, each containing nonzero vectors of that same weight. There are exactly such directions. Pick one representative per direction. A union bound shows that the probability some direction is killed is at most . Therefore at least one kills none, and its kernel has no nonzero vector of weight less than .
The kernel is a linear code with dimension . No full-rank assumption was used. The events for different representatives need not be independent; the union bound does not require that. Also , so some permitted always exists, although a weak choice may guarantee only the zero-dimensional code. For a one-word linear code, the distance statement means directly that there is no nonzero word of weight below .
A successful existence argument still leaves an algorithmic task
Suppose we actually sample a matrix. Testing its rank is easy by elimination, but that does not test the distance condition. To verify the property used in the union bound directly, we would need to check that no low-weight projective representative lies in its kernel. Their number is the very quantity counted by , which can grow exponentially in block length. The proof therefore supplies a positive chance of a good matrix without supplying a cheap certificate that an observed matrix is good.
Repeating the experiment does not remove this distinction. If a stronger choice of made the union-bound failure estimate at most one half, independent matrices would make it likely that at least one of several samples was good. Recognizing which sample has the required minimum distance would remain an additional computational problem. An efficient encoder also does not settle that problem: once a basis of the kernel is found, encoding is just a linear combination, while nearest-word decoding asks a different search question.
There is a useful structural monotonicity here. Any subcode of a good linear kernel retains the same lower distance guarantee, because removing words cannot introduce a new low-weight nonzero word. If its dimension exceeds a desired message dimension, one may select a smaller basis span. That observation lets an existence proof offer a convenient rate without pretending that all redundant checks are independent or that a particular dimension is forced exactly.
Concept lensAlgebraic
Singleton's bound as a rank count for linear codes
For a linear code over with parity-check matrix of rank , a nonzero codeword of weight is a nontrivial dependency among columns of . Distance at least therefore says that every columns are linearly independent, which forces . This is again, now read as a statement about column rank rather than about puncturing.
Count all coordinate disagreements
Proof
(Counting disagreements coordinate by coordinate)
For a fixed coordinate let count codewords carrying symbol . The number of unordered pairs disagreeing at that coordinate is
because and Cauchy–Schwarz gives . Sum over the coordinates. On the other hand, each of the distinct pairs disagrees in at least coordinates. Hence . Canceling positive and rearranging gives . Division is justified precisely when .
Proof X-ray
Two counts of one quantity
The proof counts one quantity twice: pairs of codewords together with a coordinate where they disagree. The upper count uses only that the symbol frequencies at a coordinate sum to ; Cauchy–Schwarz says disagreements are largest when the symbols are balanced. The lower count uses only the distance. The comparison has on the right but on the left, and that difference of order is all that bounds . When the inequality holds for every and nothing follows. In the sharp example both counts are exact: every coordinate is balanced and every pair of codewords is at distance exactly four.
Convert ball sizes to entropy exponents
For put . The term is a largest term of the binomial probability distribution with parameter , as the ratio of consecutive terms shows. Among its terms one maximum has probability at least . Consequently
For the reverse estimate assume additionally . For , the ratio is at most its value at . Expressing each volume summand as its binomial probability times this ratio and , then summing probabilities to at most one, gives . At both useful estimates follow directly from volume one.
Fix and a target relative distance . Set . The covering estimate and the volume upper bound yield codes of rate at least . The linear bound does too: choose the smallest with , then , apart from the already trivial zero-sum case. Thus for a sequence of linear codes.
Conversely, for any codes whose relative minimum distance tends to , the ball lower bound in Hamming's inequality gives . The terms vanish with block length; they do not license dropping the finite-length floors or claiming that either boundary is the exact optimal rate. If a fixed relative distance is strictly above , Plotkin gives bounded code size and hence rate tending to zero. The equality case requires further argument and is not established by division by zero.
Worked examples
Worked example 1.3.6
(Bounds can leave a real gap)
For binary length seven and distance three, and , so Hamming gives . The covering existence bound uses and guarantees . The linear argument has , so guarantees dimension at least two, or four words. The binary Hamming code has sixteen words and attains the upper bound. Its existence improves on both lower guarantees; it does not invalidate them.
Worked example 1.3.7
(A sharp high-distance pair count)
Evaluate the eight binary linear forms on the seven nonzero vectors of . A nonzero linear form is one on four of those vectors, so the resulting linear code has length seven, eight words and distance four. Plotkin gives , which is attained. The coordinate balance in the pair proof is exact here: each nonzero evaluation point sees four zero and four one values across the codewords.
Worked example 1.3.8
(An asymptotic guarantee is not a construction speed)
At binary relative distance , the entropy is approximately . The proved existence argument gives linear codes with rates approaching at least . Hamming's asymptotic upper bound is approximately . These are lower and upper constraints with a gap, not two estimates of an already determined optimum. The random-check proof does not by itself provide a polynomial-time verifier for every candidate matrix or an efficient decoder.
Counterexamples and misconceptions
Counterexample mode
Maximal is weaker than maximum
For binary length three and required distance two, is maximal: every other word lies within distance one of one of its members. But has four words and the same required distance. Thus the greedy argument may stop at a smaller code than an optimum. Its covering proof still applies to the smaller code.
Common mistake
(The linear guarantee needs a field)
The linear existence theorem requires a field; an alphabet of composite size with modular arithmetic is not one, and the uniform-dot-product step then fails. With the integers mod , the product takes only the values and , so for a vector whose only nonzero entry is , the dot product of a uniform row with is not uniform.
Common mistake
(Using the covering radius in the Hamming bound)
The Hamming upper bound uses balls of radius ; radius belongs to the existence bound, where the inequality points the other way. Mixing them gives false limits. For binary length seven and distance three, would give , yet the binary Hamming code has sixteen words and distance three.
A distance guarantee controls worst-case correction only through disjoint balls. It does not turn a maximal packing construction into a fast nearest-codeword procedure.
Practice
Quick check
(For a ternary length-four distance-three code, compute Hamming and Singleton upper bounds.)
Solution · Answer
The correction radius is one and the ball size is . Hamming gives . Singleton gives . Equality of upper bounds is not an existence proof, although the ternary Hamming code of length four, with nine words and distance three, does attain them.
Quick check
(Explain why covering by radius balls does not contradict disjoint radius- balls.)
Solution · Answer
The disjoint-ball radius has twice its value strictly below . The covering radius is generally larger; balls at that radius may overlap heavily. Maximality ensures their union covers all words, and no disjointness was used in that comparison.
Quick check
(In the random-check proof, why should nonzero scalar multiples be grouped, and why is pairwise independence unnecessary?)
Solution · Answer
Nonzero scalar multiples have the same kernel-membership event, so counting their whole direction once improves the sufficient bound. For any finite events, the probability of their union is at most the sum of their probabilities regardless of dependencies. Only the row independence used to compute the one-vector probability was needed.
Quick check
(Apply Plotkin to binary length ten with distance six. What fails if distance is five?)
Solution · Answer
Here and the positive denominator is , giving . At distance five the denominator is zero; the rearranged inequality reads only and bounds no size. Substituting into the displayed fraction would be invalid.
Quick check
(Does a lower bound assert that every sufficiently large code of that distance has that rate?)
Solution · Answer
The argument constructs or proves existence of at least one suitable sequence of codes. Smaller subsets retain the distance and can have much lower rate. Therefore the existence lower bound cannot be read as a lower rate bound for every code with the same minimum separation.