Article: Minkowski Weak Embedding Theorem

My article Minkowski weak embedding theorem¹ with Stathis Chrontsios-Garitsis just got accepted at HJM, so it’s high time that I write a short summary.

The two sentence version: The Assouad embedding theorem loosely states that any metric space with finite Assouad dimension can be embedded into $\mathbb{R}^n$ without too much distortion. The Minkowski (or box-counting) dimension is smaller than the Assouad dimension and we show that an analogue of the Assouad embedding theorem still holds if one replaces the assumption of finite Assouad dimension with the weaker assumption of finite Minkowski dimension.

The somewhat longer version:

1 Introduction

Let us first recall/introduce some basic notions: doubling and the related Assouad dimension.

We say that a metric space $(X,d)$ is doubling if every closed ball $B=B(x,r)\subseteq X$ can be covered by at most $K$ balls $B_i=B(y_i,r/2), i\in\{1,\dots,K\}$ of half the diameter of $B$. The Assouad dimension can be considered a quantification of the doubling property:

Let $N_r(F)$ denote the minimal number of closed balls of radius $r>0$ required to cover $F$. The Assouad dimension captures the exponent of the maximal relationship between balls of radius $R$ and its covering by $r$-balls. Formally, $$ \dim_{\mathrm{A}} X = \inf\left\{ \alpha> 0 \mid (\exists C>0)(\forall 0 < r < R)\quad \sup_{x\in X} N_r(B(x,R)) \leq C \left(\frac{R}{r}\right)^\alpha\right\}. $$

It is fairly easy to see that the Assouad dimension and doubling must be connected. So let’s prove the following equivalence:

Proposition 1. A metric space $(X,d)$ is doubling if and only if it has finite Assouad dimension.

Proof. First assume that $s = \dim_{\mathrm{A}} X <\infty$. Then, $$\sup_{x\in X} N_r(B(x,R)) \leq C\left(\frac{R}{r}\right)^{s+1}$$ for some $C>0$. Now fix $r = R/2$ and let $B=B(x,R)$ be an arbitrary ball. Then, $$N_{R/2}(B(x,R)) \leq C 2^{s+1}.$$ That is, $B(x,R)$ can be covered by at most $C 2^{s+1}$ many balls and $(X,d)$ is doubling.

Now assume $(X,d)$ is doubling. Then there exists $K$ such that $N_{R/2}(B(x,R)) \leq K$ for all $x\in X$ and $R > 0$. Now let $0 < r < R$ be given and set $k,m \in \mathbb{Z}$ to be the least integers such that $R < 2 ^k$ and $r < 2^m$. We get $m \leq k$ and $$ 2^{m-1} \leq r < 2^m \quad \text{and}\quad 2^{k-1} \leq R <2^k. $$ Since $N_r(B(x,R))$ is non-decreasing in $R$ and non-increasing in $r$, we get $$\begin{aligned} N_r(B(x,R)) &\leq N_{2^{m-1}}(B(x,2^k)) \leq K^{k-m+1}\\ &= K^2 \frac{K^{k-1}}{K^m} =K^2 \frac{2^{(k-1)\log_2 K}}{2^{m \log_2 K}}\\ &\leq K^2 \left(\frac{R}{r}\right)^{\log_2 K}.\end{aligned}$$ Now $x,r,R$ were arbitrary and so $\dim_{\mathrm{A}} X \leq \log_2 K$. □

For totally bounded spaces, the (upper) Minkowski dimension $\dim_{\mathrm{M}}$, also known as the upper box-counting dimension, is given by the limit $\limsup_{r\to 0} \frac{\log N_r(X)}{-\log r}$. It can also be expressed analogously to the Assouad dimension by $$\dim_{\mathrm{M}} X = \inf \left\{ \alpha > 0 \mid (\exists C>0) (\forall r>0)\quad N_r(X) \leq C r^{-\alpha}\right\}.$$ Writing it like this also shows that $\dim_{\mathrm{M}} X \leq \dim_{\mathrm{A}}X$ by taking $R=\mathrm{diam}(X)$.

2 The Assouad Embedding Theorem

The Assouad and Minkowski dimensions agree with our intuitive notion for “nice” regular sets. For instance, for instance, $\mathbb{R}^N$ has dimension $N$. Further, both notions are bi-Lipschitz invariant. In particular, this means that any mapping $\phi:X\to \mathbb{R}^N$ for $N < \dim_{\mathrm{A}}X$ cannot possibly be bi-Lipschitz.

A natural question therefore is, whether the converse holds and there exists such a bi-Lipschitz map if $N$ is sufficiently large. This is false, but a partial converse is given by Assouad embedding theorem. This embedding result was first proven by Assouad², while Naor and Neiman³ made a quantitative improvement some time later. The embedding theorem states that there exists an “almost” bi-Lipschitz map whenever the space is doubling, i.e. has finite Assouad dimension.

Theorem (Assouad Embedding Theorem). Let $(X,d)$ be a doubling metric space. There exists $N\in\mathbb{N}$ such that for all $\tfrac12 < \alpha < 1$, there exists a constant $K$ and a mapping $\phi:X\to \mathbb{R}^N$ such that $$ K^{-1} d(x,y)^\alpha \leq |\phi(x) - \phi(y)| \leq K d(x,y)^\alpha$$ for all $x,y \in X$.

Recently, David and Snipes⁴ produced a streamlined proof of the above, that formed the basis of our article ¹. If you want to learn more about the Assouad dimension (and its variants) I recommend this book⁵ by Jonathan Fraser.

3 Weaker Assumptions

In addition to the notions of dimensions above (Minkowski & Assouad), it will be helpful to motivate our result by introducing yet another dimension. The (upper) Assouad spectrum $\dim_{\mathrm{A}}^\theta X$ was introduced by Fraser and Yu⁶ to interpolate between the Minkowski and Assouad dimensions. It achieves this by restricting the relative sizes of $r$ and $R$ in the Assouad dimension by means of a parameter $\theta\in(0,1)$: $$ \dim_{\mathrm{A}}^\theta X = \inf\left\{ \alpha> 0 \mid (\exists C>0)(\forall 0 < r \;{ \color{red}\leq R^{1/\theta}} < R < 1)\quad \sup_{x\in X} N_r(B(x,R)) \leq C \left(\frac{R}{r}\right)^\alpha\right\}. $$ The function $\theta\mapsto \dim_{\mathrm{A}}^\theta X$ is continuous and non-decreasing in $\theta$ and tends to the Minkowski dimension as $\theta\to 0$. It does not tend to the Assouad dimension when $\theta\to 1$ but instead approaches a value known as the quasi-Assouad spectrum, see e.g. this article⁷.

It is worth pointing out here that by continuity we must have that the spectrum is finite for small enough $\theta$ if the Minkowski dimension is finite and this is exactly what we use to prove the following:

Theorem 1. Let $(X,d)$ be a compact metric space with $\dim_M X <\infty$ and let $\tfrac12 < \alpha <1$. There exist $\tau \in (0,1)$ and $n_0\in\mathbb{N}$ such that for every $n > n_0$ there is an $L$-Lipschitz map $F: X^\alpha \to \mathbb{R}^M$, where $L = L(\alpha, n)$ and $M=M(n)$ such that $$|F(x) - F(y)| \geq L^{-1} d(x,y)^\alpha$$ for all $x,y\in X$ such that $d(x,y)\geq 4 \tau^{2n}$.

That is, finite (upper) Minkowski dimension is enough to find a “coarse” embedding into $\mathbb{R}^M$ that is Lipschitz (“from above”) for all $x,y$ in the snowflaked space $X^\alpha = (X,d^\alpha)$. However, it is not bi-Lipschitz everywhere and one can only get a Lipschitz property “from below” for sufficiently separated points.

4 Applications?

Clearly, our theorem has a weaker conclusion than the Assouad embedding theorem. However, it may provide useful bounds when considering spaces that are non-doubling, yet have finite Minkowski dimension. One such class of examples comes from Random Geometry. The Brownian continuum random tree (CRT) and the Brownian map (BM) are particular examples of metric spaces that have finite Minkowski dimension ($2$ and $4$, respectively) but are not doubling and have infinite Assouad dimension, see e.g. here⁸. The same also holds for spaces with a Liouville quantum gravity metric⁹.

Another example of a space that has finite Minkowski dimension but infinite Assouad dimension are the boundaries of tree graphs which expand exponentially from the root, say at rate $r\in (0,\infty)$ but have vertices with unbounded number of descendants.

5 Proof curiosities: The Assouad spectrum

You may wonder why I went to great length explaining the Assouad spectrum, when the theorem clearly only involves the Minkowski dimension. As it stands, we prove Theorem 1 under the assumption that the Assouad spectrum is finite for some $\theta>0$. This allows us to quantify directly the “relative doubling” one obtains by iterating the bound. From scale $r\in(0,1)$ with covering number $N_r$, we can bound the covering number of scale $r^{1/\theta}, r^{1/\theta^2}, r^{1/\theta^3},\dots$ geometrically. The existence of $\theta>0$ is equivalent to finite Minkowski dimension, though we did not find a proof that uses the Minkowski dimension directly.

References.