What is the Assouad dimension of a complete unit ball?

Question

I have been recently exposed to the following definition of the Assouad dimension

For any point $x\in\mathbb{R}^D$ and any $r>0$, let $B(x, r) =\{z:\|x−z\| \le r\}$ denote the closed ball of radius $r$ centered at $x$. The Assouad dimension of $S\subset\mathbb{R}^D$ is the smallest integer $d$ such that for any ball $B(x, r)\subset\mathbb{R}^D$, the $set\ B(x, r)\cap S$ can be covered by $2^d$ balls of radius $r/2$.

This value $d$ is supposed to be a measure of the 'intrinsic dimensionality' of a data $S \subset \mathbb{R}^D$. Intuition dictates that it should be $D$ for truly $D$-dimensional $S$.

Let $S$ be the ball $B(x,r)$. I can't see how it can be covered by $2^d$ balls.

Answer 1

Definitions

It might help if you start with a somewhat expanded (and rather complicated looking) definition.

Definition 1: Let $(X,d)$ be a metric space and $S \subseteq X$. For any real numbers $r$ and $R$ with $0 < r < R$, let $\mathcal{N}_S(r,R)$ denote the number of balls of radius $r$ required to cover a ball of radius $R$ which is centered in $S$. Define $$ \Delta_{\varepsilon,t}(S) := \sup\left\{ \frac{\log \mathcal{N}_S(r,R)}{\log(R/r)} \ \middle|\ 0 < r < R < \varepsilon\ \text{and}\ R > tr \right\}. $$ The Assouad dimension of $S$ is given by $$ \dim_{\text{As}}(S) := \lim_{\varepsilon\to 0} \lim_{t\to\infty} \Delta_{\varepsilon,t}(S).$$

This particular formulation is very general—it makes sense in any metric space. The essential idea is that you count the number of little balls which are required to cover a large ball, and ask how bad that can get as (1) the radii of the balls goes to zero but (2) the ratio between the radii of a large ball and a small ball goes to infinity. This definition is taken from a paper by H. Movahedi-Lankarani.

It is worth noting that, contrary to what is asserted in the question, the Assouad dimension of a set $S$ is not necessarily an integer. Indeed, it "typically" won't be an integer.

This characterization of the Assouad dimension is a little unwieldy, but it can be simplified a bit. The simplification has the advantage of making the Assouad dimension "look" a bit more like the box-counting dimension, which may be written $$\dim_{\text{box}}(S) = \inf\left\{ a \ \middle|\ \exists K>1 \text{ s.t. }\mathcal{N}_S(r) \le K\left( \frac{1}{r} \right)^a \text{ for all } 0 < r < 1 \right\}, $$ where $\mathcal{N}_S(r)$ is the number of balls of radius $r$ required to cover $S$.

Definition 2: Let $S \subseteq \mathbb{R}^D$ be compact (closed and bounded). The Assouad dimension of $S$ is given by $$ \dim_{\text{As}}(S) = \inf\left\{ a \ \middle|\ \exists K>1 \text{ s.t. }\mathcal{N}_S(r,R) \le K\left( \frac{R}{r} \right)^a \text{ for all } 0 < r < R < 1 \right\}, $$ where $\mathcal{N}_S(r,R)$ is as above.

This definition is (essentially) that given by Jouni Luukkainen, Eric Olson, James Robinson, and others. This characterization is nice, as it makes obvious the scaling relation—basically, we are looking for the "best" exponent such that the number of little balls needed to cover a big ball scales like the ratio of the two radii, rasied to that power.

Dimension of a Ball

There are a few results which I am going to state without proof:

1. For any integer $D$, we have $\dim_{\text{As}}(\mathbb{R}^D) = D$.
2. If $S\subseteq T$, then $\dim_{\text{As}}(S) \le \dim_{\text{As}}(T)$.

The first result follows, essentially, from a slightly more general theory, which I don't want to present here (this answer is already too long). The second result should be "obvious"—if $S\subseteq T$, then any ball in $S$ is also a ball in $T$. Thus $$ \mathcal{N}_S(r,R) \le \mathcal{N}_T(r,R),$$ from which the result follows.

Now, suppose that $B = B(x,R)$ is a ball is a ball (either open or closed, it doesn't matter) in $\mathbb{R}^D$, and suppose for contradiction that $\dim_{\text{As}}(B) = a < D$. This would imply that $B$ can be covered by $K(R/r)^a$ balls of radius $r$, and so $$ \operatorname{vol}(B) \le K\left(\frac{R}{r} \right)^a \operatorname{vol}(B(0,r)), \tag{$\ast$}$$ where $\operatorname{vol}(B(x,r))$ denotes the $D$-dimensional volume (really, the Lebesgue measure) of a ball of radius $r$. Note that this inequality does, actually, make sense: the union of the $r$-balls contains $B$, so the volume of $B$ is bounded by the volume of the union. But the union contains $M(R/r)^a$ $r$-balls, each of which has the same volume.

It follows from elementary calculus techniques that $$ \operatorname{vol}(B(0,r)) = \Omega_D r^D, $$ where $\Omega_D$ is a constant which depends on $D$. For example: $$ \Omega_1 = 2, \qquad \Omega_2 = \pi, \qquad \Omega_3 = \frac{4}{3}\pi, \qquad \text{etc.} $$ Substituting this into ($\ast$) gives $$ K\left(\frac{R}{r} \right)^a \operatorname{vol}(B(0,r)) \le K\Omega_N \left(\frac{R}{r} \right)^a r^D = K\Omega_N R^a r^{D-a}. $$ But $D-a > 0$ by hypothesis, and this inequality must hold for all $r > 0$, from which it follows that $r^{D-a}$ can be made arbitrarily close to zero by a choice of $r$. But then $$ \operatorname{vol}(B) \le K\Omega_N R^a r^{D-a} $$ for all $r < R$, which implies that $\operatorname{vol}(B) = 0$. This is a contradiction, therefore we cannot have $\dim_{\text{As}}(B) < D$. In other words, $\dim_{\text{As}}(B) \ge D$.

On the other hand, since $B \subseteq \mathbb{R}^D$, it must be the case that $$\dim_{\text{As}}(B) \le \dim_{\text{As}}(\mathbb{R}^D) = D, $$ and so $$ D \le \dim_{\text{As}}(B) \le D \implies \dim_{\text{As}}(B) = D. $$

Futher Reading

I gave a talk on this topic a few years ago. Some slightly more detailed definitions (and a more terse version of the above argument) can be found in the notes for that talk. For further reading, I would once again suggest Robinson's book:

Robinson, James C., Dimensions, embeddings, and attractors, Cambridge Tracts in Mathematics 186. Cambridge: Cambridge University Press (ISBN 978-0-521-89805-8/hbk). xii, 205 p. (2011). ZBL1222.37004.