Packing Numbers and Covering Numbers

Why Compare Packings and Covers?

A finite collection of prediction rules can be large while still containing many rules that behave almost identically on the observed sample. To describe how many meaningfully different prediction patterns it contains, we can ask two related questions. How many well-separated patterns can be selected? And how many representative patterns are needed to approximate the entire collection to a specified accuracy?

These questions give the packing number and the covering number. Their relationship is useful because either quantity can bound the other at a nearby radius. The exact radius matters: confusion about it, or about whether the distance condition is strict, can make a correct-looking inequality false.

Definitions and Conventions

Let $(A,d)$ be a nonempty finite metric space. For $a\in A$ and $r>0$, the closed ball of radius $r$ centered at $a$ is $\{x\in A:d(x,a)\le r\}$. In this tutorial, covering centers are required to belong to $A$, and covering balls are closed. We use strict separation for packings.

Definition: A radius-$r$ cover of $A$ is a collection of closed radius-$r$ balls, with centers in $A$, whose union contains $A$. The covering number $N(A,d,r)$ is the smallest number of such balls in a cover. A subset $P\subseteq A$ is strictly $r$-separated if $d(x,y)>r$ for every distinct $x,y\in P$. The packing number $M(A,d,r)$ is the largest cardinality of a strictly $r$-separated subset.

Both numbers exist and are finite because $A$ is finite. The definitions also make the boundary convention explicit: points at distance exactly $r$ are not allowed together in a strictly $r$-separated set, while a point at distance exactly $r$ from a cover center is covered.

A packing is maximal if no additional point of $A$ can be added while preserving strict $r$-separation. It is maximum if it has the largest cardinality among all such packings. Every maximum packing is maximal, but a maximal packing need not be maximum. This distinction matters when a greedy selection procedure is used.

The Basic Packing–Covering Inequalities

Theorem: For every nonempty finite metric space $(A,d)$ and every $r>0$, $$ N(A,d,r)\le M(A,d,r)\le N(A,d,r/2). $$

The first inequality says that a maximum $r$-separated set is already a cover at radius $r$. The second says that a radius-$r/2$ ball cannot contain two points of a strictly $r$-separated set. The proofs use only maximality and the triangle inequality.

Proof of the first inequality. Choose a maximum strictly $r$-separated subset $P$ of $A$, so $|P|=M(A,d,r)$. Suppose there were a point $x\in A$ whose distance from every point of $P$ were greater than $r$. Then $P\cup\{x\}$ would still be strictly $r$-separated and would have more elements than $P$, contradicting the fact that $P$ has maximum cardinality. Therefore, for every $x\in A$, some $p\in P$ satisfies $d(x,p)\le r$. The radius-$r$ balls centered at the points of $P$ cover $A$, so $N(A,d,r)\le |P|=M(A,d,r)$. $\square$

This argument also proves a slightly more general fact: any maximal strictly $r$-separated subset covers $A$ at radius $r$. The proof does not require it to have maximum cardinality. A greedy procedure that adds points until no further point can be added therefore produces an $r$-cover, even if its packing size is not optimal.

Proof of the second inequality. Let $C_1,\ldots,C_k$ be a cover of $A$ by closed balls of radius $r/2$, where $k=N(A,d,r/2)$. Take any strictly $r$-separated subset $P$ of $A$. Assign each point of $P$ to one covering ball that contains it. If two distinct points $x,y\in P$ were assigned to the same ball with center $c$, the triangle inequality would give $$ d(x,y)\le d(x,c)+d(c,y)\le r/2+r/2=r. $$ That contradicts $d(x,y)>r$. Thus each covering ball contains at most one point of $P$, and $|P|\le k$. This holds for every strictly $r$-separated subset, so $M(A,d,r)\le N(A,d,r/2)$. $\square$

The factor of two comes directly from the triangle inequality: two points in the same ball of radius $r/2$ are at distance at most $r$. With the conventions above, “at most $r$” is exactly what is needed to rule out strict separation by more than $r$.

Binary Prediction Vectors and Empirical Distance

Fix a sample of $n$ inputs. A binary prediction rule gives a vector in $\{0,1\}^n$, with one coordinate for each input. For two such vectors $u$ and $v$, define their empirical distance as the fraction of sample inputs on which their predictions differ:

d_n(u,v)=\frac{1}{n}\sum_{i=1}^{n}|u_i-v_i|.

For binary vectors, each summand is 1 when the coordinates disagree and 0 when they agree. Thus $d_n$ is Hamming distance divided by $n$. On a finite set of distinct prediction vectors it is a metric. If different rules give the same vector on the sample, they are at distance zero; they can be identified as one vector for these calculations.

Worked Example: Two Coordinates and a Boundary Case

Consider $A=\{00,01,10,11\}$ and use $d_2$, the fraction of the two coordinates on which vectors differ. The distance between vectors differing in one coordinate is $1/2$; the distance between complementary vectors is $1$. Find $M(A,d_2,1/2)$ and $N(A,d_2,1/2)$.

For a strictly $1/2$-separated packing, every pair must have distance greater than $1/2$. Therefore, no pair differing in just one coordinate can be selected together. The complementary pairs $\{00,11\}$ and $\{01,10\}$ each have distance $1$, so a packing of size 2 exists. A packing of size 3 is impossible: among any three vertices of this square, at least two differ in exactly one coordinate. Hence $M(A,d_2,1/2)=2$.

A closed ball of radius $1/2$ around $00$ contains $00,01,10$, and a ball around $11$ contains $11,01,10$. These two balls cover $A$, so $N(A,d_2,1/2)\le2$. One ball cannot cover all four vectors: its center is one of the four vectors, and the vector opposite that center is at distance $1$. Thus $N(A,d_2,1/2)=2$. In this example both quantities at radius $1/2$ equal 2, and the strict boundary convention is essential: pairs at distance exactly $1/2$ do not belong together in a packing at this radius.

Applying the Inequalities to Finite Prediction Classes

Worked Example: A Chain of Predictions

On a sample of five inputs, consider the prediction vectors $A=\{00000,10000,11000,11100,11110\}$. Index them by $j=0,1,2,3,4$, in the order written. The vector with index $j$ has its first $j$ coordinates equal to 1 and the rest equal to 0. For indices $i$ and $j$, the vectors differ in $|i-j|$ coordinates, so their empirical distance is $|i-j|/5$. Calculate the packing and covering numbers at radius $r=1/5$.

Strict separation by more than $1/5$ requires $|i-j|/5>1/5$, or $|i-j|>1$. Thus selected indices cannot be adjacent. The indices $0,2,4$ give a packing of size 3. Four indices from $\{0,1,2,3,4\}$ must include two adjacent indices: there are only three nonadjacent positions available if every chosen pair must have a gap of at least 2. Therefore $M(A,d_5,1/5)=3$.

For a cover at radius $1/5$, a center with index $j$ covers every index $i$ satisfying $|i-j|/5\le1/5$, or $|i-j|\le1$. Centers with indices 1 and 3 cover, respectively, the index sets $\{0,1,2\}$ and $\{2,3,4\}$. Hence $N(A,d_5,1/5)\le2$. One center covers at most three indices, so it cannot cover all five; therefore $N(A,d_5,1/5)=2$.

The theorem gives $2\le3\le N(A,d_5,1/10)$. At radius $1/10$, a ball contains only its center, since the smallest positive distance in this set is $1/5$. Thus $N(A,d_5,1/10)=5$, and the full comparison is $2\le3\le5$.

Worked Example: A Nonuniform Set of Binary Vectors

Let $A=\{0000,0001,0011,1111\}$, with distance equal to the fraction of coordinates that differ. The distances between the six pairs, in the order $(0000,0001)$, $(0000,0011)$, $(0000,1111)$, $(0001,0011)$, $(0001,1111)$, and $(0011,1111)$, are $1/4,1/2,1,1/4,3/4,1/2$, respectively. Find the packing and covering numbers at radius $1/4$, and check the theorem.

A strictly $1/4$-separated set cannot contain both $0000$ and $0001$, nor both $0001$ and $0011$, because each such pair is at distance exactly $1/4$. The three vectors $0000,0011,1111$ have pairwise distances $1/2,1,1/2$, all greater than $1/4$. Hence a packing of size 3 exists. No set of all four is separated, so $M(A,d_4,1/4)=3$.

For the cover, the radius-$1/4$ ball centered at $0001$ contains $0000,0001,0011$, since the distances from $0001$ to those vectors are $1/4,0,1/4$. A ball centered at $1111$ contains $1111$. These two balls cover $A$. One ball cannot cover all four: the vector $1111$ is at distance greater than $1/4$ from each of the other three vectors, so any cover must include a ball centered at $1111$, and that ball covers no other member of $A$. The remaining three vectors cannot all fit in one radius-$1/4$ ball: no center in $A$ is within $1/4$ of all three. Thus $N(A,d_4,1/4)=2$.

At radius $1/8$, the smallest positive distance, $1/4$, exceeds the radius. Every ball contains only its center, giving $N(A,d_4,1/8)=4$. The inequality is $2\le3\le4$, as required.

Using the Results Carefully

For prediction vectors on a fixed sample, the packing number counts how many patterns can be selected so that every pair disagrees on a sufficiently large fraction of the sample. The covering number counts how many representative patterns suffice so that every pattern is close to at least one representative. A maximal separated collection is useful even when it is not the largest possible: its points still cover the class at the separation radius. A maximum packing gives the largest possible such collection.

These comparisons are finite-set statements here, and their usefulness does not depend on the origin of the vectors. The distance could be normalized Hamming distance or any other metric. For prediction classes, the fixed-sample distance focuses attention on the predictions actually observed on that sample; it does not by itself assert that two rules behave similarly away from the sample.

Common mistake: dropping the radius factor or changing a strict inequality without checking the boundary. It is generally incorrect to claim $M(A,d,r)\le N(A,d,r)$ from the triangle inequality. A radius-$r$ ball can contain two points at distance as large as $2r$, so it may contain a pair that is strictly $r$-separated. The proof only guarantees at most one packed point per ball of radius $r/2$. Another error is to say that a maximum $r$-separated set must have pairwise distances at least $r$ under these conventions. The definition requires distances strictly greater than $r$; a pair at distance exactly $r$ is excluded. State the conventions first, then use the matching inequality.

Key takeaway: With closed covering balls and strict separation by distances greater than $r$, the standard comparison is $N(A,d,r)\le M(A,d,r)\le N(A,d,r/2)$. The first bound follows because a maximum separated set is maximal; the second follows from the triangle inequality.

Check Your Understanding

Use the definitions and radius conventions from this tutorial.

Why does a maximum strictly $r$-separated subset necessarily cover $A$ at radius $r$?
In the proof of $M(A,d,r)\le N(A,d,r/2)$, where exactly is the triangle inequality used?
For binary vectors of length $n$, what does empirical distance $d_n(u,v)=2/n$ say about the predictions?
Explain why a pair at distance exactly $r$ cannot belong to the same strictly $r$-separated packing, but can lie in one closed radius-$r$ ball if one point is its center.
Can a maximal packing be smaller than a maximum packing? Which part of the first inequality still holds for a maximal packing?