<p>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 <span class="math-container">$k$</span> if any such S can be covered by at most <span class="math-container">$(1/\epsilon)^k$</span> balls of radius <span class="math-container">$\epsilon \rho$</span>. The difference between your definition and this one is the limitation of <span class="math-container">$S$</span> to be a ball though.</p>
<p>In essence, your parameter <span class="math-container">$k$</span> is acting like a kind of dimension of the space. A worthwhile reference is <a href="https://kenclarkson.org/nn_survey/p.pdf" rel="nofollow noreferrer">Ken Clarkson's review of different notions of metric space dimension</a>.</p>
<p>Separately, I'm a little confused about your definition, since it appears to require a bound unrelated to the size of <span class="math-container">$S$</span>. This is odd, because <span class="math-container">$S$</span> could grow arbitrarily large.</p>

CC BY-SA 3.0
2011-06-06T16:27:29.807Z
I'm not wedded to my definition -- it was just an attempt to make a vague intuition precise enough for people to criticize!
Neel Krishnaswami
CC BY-SA 3.0
2011-06-06T17:11:18.140Z
Do you think bounded doubling dimension gets at what you're looking for ?
Suresh Venkat
CC BY-SA 3.0
2011-06-06T18:06:48.390Z
I'm not sure yet -- I need to think about it a little more carefully. I've downloaded the review and am looking at it now.
Neel Krishnaswami
CC BY-SA 4.0
2011-06-06T16:02:01.130Z
2022-07-20T10:22:38.893Z
2022-07-20T10:22:38.893Z
Suresh Venkat
<p>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$. </p>

<p>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$. </p>

<p>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$). </p>

<p>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.) </p>

CC BY-SA 3.0
2011-06-06T15:52:44.390Z
Nit: A subspace of a metric space is compact if it is _complete_ (not closed) and totally bounded.  (See e.g. [Wikipedia](http://en.wikipedia.org/wiki/Compact_space).)
Tsuyoshi Ito
CC BY-SA 3.0
2011-06-07T08:05:28.443Z
Whatever it is you're doing, it is related to notions of dimension. Study that first.
Andrej Bauer
CC BY-SA 3.0
2011-06-07T10:51:45.983Z
@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
CC BY-SA 3.0
2011-06-09T10:03:58.517Z
It looks like you might be interested in the *box dimension* of a metric space -- http://en.wikipedia.org/wiki/Minkowski%E2%80%93Bouligand_dimension
François G. Dorais
CC BY-SA 3.0
2011-06-10T15:24:43.437Z
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
<pl.programming-languages><denotational-semantics><metric-spaces>
Has anyone studied "polynomially compact" metric spaces?
Neel Krishnaswami
# Has anyone studied "polynomially compact" metric spaces?

(Asked by: username_0 on 2011-06-06)

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

**Tags:** pl.programming-languages, denotational-semantics, metric-spaces

> **Comments:**
> **username_1**: Nit: A subspace of a metric space is compact if it is _complete_ (not closed) and totally bounded.  (See e.g. [Wikipedia](http://en.wikipedia.org/wiki/Compact_space).)  
> **username_2**: Whatever it is you're doing, it is related to notions of dimension. Study that first.  
> **username_0**: @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.  
> **username_3**: It looks like you might be interested in the *box dimension* of a metric space -- http://en.wikipedia.org/wiki/Minkowski%E2%80%93Bouligand_dimension  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_4 on 2011-06-06. Score: 4

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](https://kenclarkson.org/nn_survey/p.pdf).

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.

> **Comments:**
> **username_0**: I'm not wedded to my definition -- it was just an attempt to make a vague intuition precise enough for people to criticize!  
> **username_4**: Do you think bounded doubling dimension gets at what you're looking for ?  
> **username_0**: I'm not sure yet -- I need to think about it a little more carefully. I've downloaded the review and am looking at it now.  

---

