# Has anyone studied “polynomially compact” metric spaces?

A subspace $S$ of a metric space $A$ is compact if it is complete and totally bounded. Here, complete means that every Cauchy sequence in $S$ has a limit also in $S$. For $S$ to be totally bounded, we must have for every radius $r$, that there is a finite set $U$ of open balls of radius $r$ whose union covers $S$.

I would like to know if anyone has studied spaces where the size of $U$ is bounded by a function of $r$ -- for example, where $U(r)$ is $O(\frac{1}{r}^k)$ for some $k$.

The reason I am curious is that I am investigating models of reactive programming (ie, stream functions), where boolean streams are given the Cantor metric (two streams have a distance of $2^{-n}$ when the first position at which they differ at time $n$), and programs between streams are interpreted by functions continuous with respect to this metric. While the continuity requirement functions nicely capture causality requirements very well, it unfortunately also permits stream functions to require their whole history to compute a value (that is, functions $f(x)$ may require their whole history $x_0, \ldots, x_n$ to compute $f(x)$ at time $n$).

One idea I have for understanding this phenomenon is that the Cantor space is compact, and that at radius $2^{-n}$ you need $2^n$ balls to cover the space -- that is, there are $2^n$ length-$n$ binary sequences. So I have a vague idea that if somehow there were a way of equipping the Cantor space with an even coarser metric, I could model computations which are permitted to remember less of their input. (Eg, a polynomial bound would permit you to use space logarithmic in the elapsed time.)

• Nit: A subspace of a metric space is compact if it is complete (not closed) and totally bounded. (See e.g. Wikipedia.) – Tsuyoshi Ito Jun 6 '11 at 15:52
• Whatever it is you're doing, it is related to notions of dimension. Study that first. – Andrej Bauer Jun 7 '11 at 8:05
• @Andrej: can you suggest a good textbook? I got into this because I started writing papers using metric space semantics to prove some programs correct, and so I have only a very unsystematic, ad-hoc knowledge of metric topology. – Neel Krishnaswami Jun 7 '11 at 10:51
• It looks like you might be interested in the box dimension of a metric space -- en.wikipedia.org/wiki/Minkowski%E2%80%93Bouligand_dimension – François G. Dorais Jun 9 '11 at 10:03
• As a general introduction to topology which also covers metric spaces I would recommend "Aspects of topology" by Christenson and Voxman. It's a good textbook that covers a lot of material in an accessible and interesting way. There is an old book by Hurewicz on "Dimension theory", which I kind of like. – Andrej Bauer Jun 10 '11 at 15:24

The notion of bounded doubling dimension appears to be related. Specifically, assume your region S is a ball of radius \rho in the metric space. Then the space is said to have bounded doubling dimension $k$ if any such S can be covered by at most $(1/\epsilon)^k$ balls of radius $\epsilon \rho$. The difference between your definition and this one is the limitation of $S$ to be a ball though.
In essence, your parameter $k$ is acting like a kind of dimension of the space. A worthwhile reference is Ken Clarkson's review of different notions of metric space dimension.
Separately, I'm a little confused about your definition, since it appears to require a bound unrelated to the size of $S$. This is odd, because $S$ could grow arbitrarily large.