Quick description
A -net of a metric space
is a subset
such that for every
there exists
such that
. It is often useful to have a small
-net for a metric space: see Prove the result on a
-net first for an explanation of why. This article discusses a few techniques for finding them, giving particular reference to an idea that can be summarized by the following slogan: a maximal separated set is a net.
Preliminary remark
This article needs to be categorized. The tricks discussed are useful ones, but more emphasis needs to be placed on when they are useful. And some thought needs to go into the question of how someone who might benefit from them would be led to this article.
Example 1
Let be the closed unit ball of an
-dimensional normed space. Several results in the local theory of Banach spaces make use of the following lemma: for every
contains a
-net of size at most
.
Here is the proof. Let be a maximal
-separated subset of
. That is, let
be a subset of
such that if
and
are any two distinct elements of
then
, and such that it is impossible to add an element to
while preserving this property. It is easy to prove that such a set exists. One not very sensible proof is to use Zorn's lemma, from which the statement follows almost trivially. A better argument is to observe that
is compact and therefore totally bounded, so we can cover
with finitely many balls of radius
, and each one of these balls contains at most one element of
. A third argument is implicit in what we are about to say next.
How big can be? One can put a bound on its size using a volume argument. If
and
are distinct points in
, then the open balls
and
are disjoint, except perhaps on their boundaries. (The set
is just the closed ball of radius
about
, and similarly for
.) These balls are also contained in
. But
has volume
, and the essentially disjoint sets
have volume
, so there cannot be more than
of them. Thus,
cannot contain more than
points.
It remains to make the observation that a maximal -separated subset
of any metric space
is also a
-net, since if you could find an element of
that was not within
of a point in
then you could add that point to
, contradicting maximality.
Example 2
This is a very similar argument to the one above, known as Ruzsa's covering argument. Let be a set of integers. For some purposes in additive combinatorics it is useful to be able to ``cover'' the set
by a small number of translates of
. Here,
is the set
and
is the set
. Our task is to find points
such that
is reasonably small and
is contained in the union of the sets
. We cannot expect to do this in general, so let us try to imitate the proof in Example 1, and watch a suitable condition emerge.
If we imitate Example 1, then we want to pick a maximal separated set. But what could this mean? Well, in the proof of Example 1, each point
in our separated set was contained in a ball
, and these balls were disjoint because if not then we would find two points
and
with
, which implied that
was at most
. This suggests that we should pick
such that the sets
are disjoint. But the statement that
and
are disjoint is equivalent to the statement that
. Therefore, a maximal subset of
that is separated in this sense will have the property that for any other point
there exists
such that
. Therefore, the sets
do indeed cover
.
What about the size of ? Here we need some kind of ``volume argument'', and this is where our hypothesis will make itself clear. If
, then what can we say about
? The one obvious thing we can say is that it is contained in
. So
cannot be bigger than the size of
divided by the size of
. So we would like the ratio
to be small. And there are indeed circumstances in additive combinatorics where such sets arise.
A little further thought makes it clear that we could have a slightly neater condition if we ask for the sets
to be disjoint instead. Then the argument is virtually identical, but now we know that
is contained in
, so the ratio we want to be small is
.
One can of course use variants of this argument to prove many similar covering results.
Example 3
Sometimes one can construct good explicit nets. For example, if is small and
is a reasonably nice subset of
such as a disc of radius 1, then an obvious construction is to take a grid of points: that is, one could take the intersection of the circle with a set such as
. This minimizes the size of the net up to a constant. If one is keen even to minimize the constant, then taking a triangular lattice instead of a square lattice will be better.
In general, taking an obvious grid will tend to give a best possible result up to a constant that depends on the dimension. If the dimension is , then this dependence will usually be something like
, which is often too expensive if
is large, but is just an absolute constant if
is fixed.
Another circumstance where explicit grids work well is when the norm is particularly well tailored to such grids. In particular, this is true of the norm
. An obvious net of the unit ball of
with this norm is obtained by taking an integer
and taking the set of all points
such that every
is of the form
with
an integer between
and
. One can approximate any number in
by a number
to within
, which is at most
, which proves that this is indeed a
-net.
One could generalize this to other norms of the form with small
.
For the sake of comparison, let us see what taking an obvious grid can achieve for norms that are not well suited to this technique. Suppose that is the unit sphere of an
-dimensional normed space
and that
for every
. (Here we write
for
.) Then if
is an integer greater than
, we can approximate any point
in
uniformly to within
by a point
with coordinates of the form
with
, and by the triangle inequality
will be at most
. This is because
This gives us a net of size
, which is at most
. This is bigger than the bound obtained in Example 1 by a factor comparable to
.
Example 4
It is interesting to note that the probabilistic method can be used to obtain a better bound in Example 1. Once again, let be the unit ball of an
-dimensional normed space. Now choose
points
uniformly at random from
. Let
be any point in
. Then the probability that a given
lies in the ball of radius
about
is
. This is because
is the ratio of the volume of the ball of radius
about
to the volume of the ball from which
is chosen at random. Therefore, the probability that no
lies in this ball is
, which is around
. This becomes very small when
is significantly bigger than
.
Let us try to be precise about this last statement. At the moment, we seem to have infinitely many events that we want to hold simultaneously, but we can make it finite in the following way. Let be a parameter to be chosen later. Up to now we have been trying to prove the following statement.
-
For every
there is an
in the ball of radius
about
.
For every
in an
-net
of
there is an
in the ball of radius
about
.












Now we know that we can get to be around
, or if we don't want to use that technique then we can get it to be at most
. Let's use the second bound. So then we obtain a bound of
. If we choose
to be
, then the first term in this product differs from
by a fixed multiplicative factor, so the whole thing is at most
, say. For large
this improves on the bound obtained in Example 1.
One cannot do significantly better than this for a general normed space, since if is the unit ball of
and you let
be just smaller than
for some positive integer
, then no two distinct points where all coordinates are of the form
for some
can belong to the same ball of radius
, and there are
such points, which we can get to be arbitrarily close to
.
Example 5
Sometimes all we care about is that a net is finite. Then what we are asking for is that our space should be totally bounded, which is true if it is compact. Similarly, sometimes what we are looking for is a countable dense subset: these, when they exist, tend to be fairly easy to construct. One can think of them as "small
-nets". For instance, if
, the set of all sequences with rational entries all but finitely many of which are
is dense in the Banach space
.