Tricki

## Finding small nets

### 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 .

Instead, let us try to prove the following.

• For every in an -net of there is an in the ball of radius about .

Let be the size of and let . Then the probability that no lies in the ball of radius about a given point is around , so if is less than 1, then there is a positive probability that every point in is within of some . Thus, we will be done if .

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 .