Finding small nets

Quick description

A $\delta$ -net of a metric space $X$ is a subset $\Delta\subset X$ such that for every $x\in X$ there exists $y\in\Delta$ such that $d(x,y)\leq\delta$ . It is often useful to have a small $\delta$ -net for a metric space: see Prove the result on a $\delta$ -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 $X$ be the closed unit ball of an $n$ -dimensional normed space. Several results in the local theory of Banach spaces make use of the following lemma: for every $\delta>0$ $X$ contains a $\delta$ -net of size at most $(1+2/\delta)^n$ .

Here is the proof. Let $\Delta$ be a maximal $\delta$ -separated subset of $X$ . That is, let $\Delta$ be a subset of $X$ such that if $y$ and $z$ are any two distinct elements of $\Delta$ then $d(x,y)\geq\delta$ , and such that it is impossible to add an element to $\Delta$ 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 $X$ is compact and therefore totally bounded, so we can cover $X$ with finitely many balls of radius $\delta/3$ , and each one of these balls contains at most one element of $\Delta$ . A third argument is implicit in what we are about to say next.

How big can $\Delta$ be? One can put a bound on its size using a volume argument. If $x$ and $y$ are distinct points in $\Delta$ , then the open balls $x+(\delta/2)X$ and $y+(\delta/2)X$ are disjoint, except perhaps on their boundaries. (The set $x+(\delta/2)X$ is just the closed ball of radius $\delta/2$ about $x$ , and similarly for $y$ .) These balls are also contained in $(1+\delta/2)X$ . But $(1+\delta/2)X$ has volume $(1+\delta/2)^n$ , and the essentially disjoint sets $x+(\delta/2)X$ have volume $(\delta/2)^n$ , so there cannot be more than $(1+\delta/2)^n/(\delta/2)^n=(1+2/\delta)^n$ of them. Thus, $\Delta$ cannot contain more than $(1+2/\delta)^n$ points.

It remains to make the observation that a maximal $\delta$ -separated subset $A$ of any metric space $Z$ is also a $\delta$ -net, since if you could find an element of $Z$ that was not within $\delta$ of a point in $A$ then you could add that point to $A$ , contradicting maximality.

Example 2

This is a very similar argument to the one above, known as Ruzsa's covering argument. Let $A$ be a set of integers. For some purposes in additive combinatorics it is useful to be able to ``cover'' the set $A+A-A$ by a small number of translates of $A-A$ . Here, $A-A$ is the set $x,y\in A\}$ and $A+A-A$ is the set $x,y,z\in A\}$ . Our task is to find points $x_1,x_2,\dots,x_k$ such that $k$ is reasonably small and $A+A-A$ is contained in the union of the sets $x_i+A-A$ . 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 $x$ in our separated set was contained in a ball $x+B$ , and these balls were disjoint because if not then we would find two points $x$ and $y$ with $x-y\in B-B$ , which implied that $d(x,y)$ was at most $\delta$ . This suggests that we should pick $\{x_1,x_2,\dots,x_k\}$ such that the sets $x_i+A$ are disjoint. But the statement that $x_i+A$ and $x_j+A$ are disjoint is equivalent to the statement that $x_i\notin x_j+A-A$ . Therefore, a maximal subset of $2A-A$ that is separated in this sense will have the property that for any other point $x\in 2A-A$ there exists $j$ such that $x\in x_j+A-A$ . Therefore, the sets $x_j+A-A$ do indeed cover $2A-A$ .

What about the size of $k$ ? Here we need some kind of ``volume argument'', and this is where our hypothesis will make itself clear. If $x_j\in 2A-A$ , then what can we say about $x_j+A$ ? The one obvious thing we can say is that it is contained in $3A-A$ . So $k$ cannot be bigger than the size of $3A-A$ divided by the size of $A$ . So we would like the ratio $|3A-A|/|A|$ 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 $x_i-A$ to be disjoint instead. Then the argument is virtually identical, but now we know that $x_j-A$ is contained in $2A-2A$ , so the ratio we want to be small is $|2A-2A|/|A|$ .

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 $\delta$ is small and $X$ is a reasonably nice subset of $\mathbb{R}^2$ 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 $(\delta/2)\mathbb{Z}^2$ . 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 $d$ , then this dependence will usually be something like $d^d$ , which is often too expensive if $d$ is large, but is just an absolute constant if $d$ 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 $\ell_\infty$ norm $\|x\|_\infty=\max_i|x_i|$ . An obvious net of the unit ball of $\mathbb{R}^n$ with this norm is obtained by taking an integer $k\geq(\delta/2)^{-1}$ and taking the set of all points $x$ such that every $x_i$ is of the form $j/k$ with $j$ an integer between $-k$ and $k$ . One can approximate any number in $[-1,1]$ by a number $j/k$ to within $1/2k$ , which is at most $\delta$ , which proves that this is indeed a $\delta$ -net.

One could generalize this to other norms of the form $\phi\in\Phi\}$ with small $\Phi$ .

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 $X$ is the unit sphere of an $n$ -dimensional normed space $(\mathbb{R}^n,\|.\|)$ and that $\|x\|_\infty\leq\|x\|\leq\|x\|_1$ for every $x\in\mathbb{R}^n$ . (Here we write $\|x\|_1$ for $\sum_i|x_i|$ .) Then if $k$ is an integer greater than $n/\delta$ , we can approximate any point $x$ in $X$ uniformly to within $\delta/n$ by a point $y$ with coordinates of the form $j/k$ with $-k\leq j\leq k$ , and by the triangle inequality $\|x-y\|$ will be at most $\delta$ . This is because $\|x-y\|=\|\sum_i(x_i-y_i)e_i\|\leq\sum_i|x_i-y_i|\|e_i\|\leq n(\delta/n).$ This gives us a net of size $(2k+1)^n$ , which is at most $(3n/\delta)^n$ . This is bigger than the bound obtained in Example 1 by a factor comparable to $n^n$ .

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 $X$ be the unit ball of an $n$ -dimensional normed space. Now choose $N$ points $x_1,x_2,\dots,x_N$ uniformly at random from $(1+\delta)X$ . Let $x$ be any point in $X$ . Then the probability that a given $x_i$ lies in the ball of radius $\delta$ about $x$ is $p=\delta^n/(1+\delta)^n=(1+1/\delta)^n$ . This is because $p$ is the ratio of the volume of the ball of radius $\delta$ about $x$ to the volume of the ball from which $x_i$ is chosen at random. Therefore, the probability that no $x_i$ lies in this ball is $(1-p)^N$ , which is around $e^{-pN}$ . This becomes very small when $N$ is significantly bigger than $1/p$ .

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 $\epsilon>0$ be a parameter to be chosen later. Up to now we have been trying to prove the following statement.

For every $x\in X$ there is an $x_i$ in the ball of radius $\delta$ about $x$ .

Instead, let us try to prove the following.

For every $x$ in an $\epsilon$ -net $\Gamma$ of $X$ there is an $x_i$ in the ball of radius $\delta-\epsilon$ about $x$ .

Let $M$ be the size of $\Gamma$ and let $q=(\delta-\epsilon)^n/(1+\delta-\epsilon)^n$ . Then the probability that no $x_i$ lies in the ball of radius $\delta-\epsilon$ about a given point $x$ is around $e^{-qN}$ , so if $Me^{-qN}$ is less than 1, then there is a positive probability that every point in $\Gamma$ is within $\delta-\epsilon$ of some $x_i$ . Thus, we will be done if $N>q^{-1}\log M$ .

Now we know that we can get $M$ to be around $(1+2/\epsilon)^n$ , or if we don't want to use that technique then we can get it to be at most $(3/\epsilon n)^n$ . Let's use the second bound. So then we obtain a bound of $(1+1/(\delta-\epsilon))^nn\log(3/\epsilon n)$ . If we choose $\epsilon$ to be $\delta/n$ , then the first term in this product differs from $(1+1/\delta)^n$ by a fixed multiplicative factor, so the whole thing is at most $Cn\log n(1+1/\delta)^n$ , say. For large $n$ this improves on the bound obtained in Example 1.

One cannot do significantly better than this for a general normed space, since if $X$ is the unit ball of $\ell_\infty^n$ and you let $\delta$ be just smaller than $1/k$ for some positive integer $k$ , then no two distinct points where all coordinates are of the form $(2j-k)/k$ for some $j\in\{0,1,2,\dots,k\}$ can belong to the same ball of radius $\delta$ , and there are $(k+1)^n$ such points, which we can get to be arbitrarily close to $(1+1/\delta)^n$ .

Example 5

Sometimes all we care about is that a net is finite. Then what we are asking for is that our space $X$ 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 $0$ -nets". For instance, if $1\leq p<\infty$ , the set of all sequences with rational entries all but finitely many of which are $0$ is dense in the Banach space $\ell_p$ .