On Uryson widths

This is a note on parts of Gromov’s paper ‘width and related invariants of Riemannian manifolds’ (1988).

For a compact subset $C$ of $\mathbb{R}^n$ , we define the k-codimensional width (or simply k-width) to be the smallest possible number $w$ where there exists a k-dimensional affine subspace $P_k \subseteq \mathbb{R}^n$ s.t. all points of $C$ is no more than $w$ away from $P_k$ .

i.e.

$\displaystyle{W}_k(C) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p\in C} \mbox{dist}(p, P_k)$
where $\mbox{dist}(p, P_k)$ is the length of the orthogonal segment from $p$ to $P_k$ .

It’s easy to see that, for any $C$ ,

$\mathcal{W}_0(C) \geq \mathcal{W}_1(C) \geq \cdots \geq \mathcal{W}_n(C) = 0$ .

At the first glance it may seems that $\mathcal{W}_0(C) = \frac{\mbox{diam}(C)}{2}$ . However it is not the case since for example the equilateral triangle of side length $1$ in $\mathbb{R}^2$ has diameter $1$ but 0-width $\frac{1}{\sqrt{3}}$ . In fact, by a theorem of Jung, this is indeed the optimum case, i.e. we have:

$\frac{1}{2}\mbox{diam}(C) \leq \mathcal{W}_0(C) \leq \sqrt{\frac{n}{2(n+1)}}\mbox{diam}(C)$

At this point one might wonder (at least I did), if we want to invent a notion that captures the ‘diameter’ after we ‘forget the longest k-dimensions’, a more direct way seem to be taking the smallest possible number $w'$ where there is an orthogonal projection of $C$ onto a $k$ dimensional subspace $P_k$ where any point $p \in P_k$ has pre-image with diameter $\leq w'$ .

i.e.

$\displaystyle \widetilde{\mathcal{W}_k}(X) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p \in P_k} \mbox{diam}(\pi^{-1}_{P_k}(p))$

Now we easily have $\mbox{diam}(C) = \widetilde{\mathcal{W}_0}(C) \geq \widetilde{\mathcal{W}_1}(C) \geq \cdots \geq \widetilde{\mathcal{W}_n}(C) = 0$ .

However, the disadvantage of this notion is, for example, there is no reason for a semicircle arc to have 1-width 0 but a three-quarters circular arc having positive 1-width.

Since we are measuring how far is the set from being linear, taking convex hull should not make the set ‘wider’ $\widetilde{\mathcal{W}_k}$ , unlike $\widetilde{\mathcal{W}_k}$ is not invariant under taking convex hulls. Note that for convex sets we do have

$\frac{1}{2}\widetilde{\mathcal{W}_k}(C) \leq \mathcal{W}_k(C) \leq \sqrt{\frac{n-k}{2(n-k+1)}}\widetilde{\mathcal{W}_k}(C)$

$\mathcal{W}_k(C) = 0$ iff $C$ is contained in a $k$ -plane.

We now generalize this notion to general metric spaces:

Definition: The Uryson k-width of a compact metric space $M$ is the smallest number $w$ where there exists $k$ dimensional topological space $X$ and a continuous map $\pi: M \rightarrow X$ where any point $x \in X$ has pre-image with diameter $\leq w$ .

i.e. $\displaystyle UW_k(M) = \inf \{ \ \sup_{x \in X} \mbox{diam}(\pi^{-1}(x)) \ |$

$\dim{X} = k, \pi:M \rightarrow X \ \mbox{is continuous} \}$

Note: Here dimension is the usual covering dimension for topological spaces: i.e. a topological space $X$ is $n$ dimensional if any finite cover of $X$ has a finite refinement s.t. no point of $X$ is contained in more than $n_1$ sets in the cover and $n$ is the smallest number with this property.

For compact subsets $C$ of $\mathbb{R}^n$ with induced metric, we obviously we have $UW_k(C) \leq \widetilde{\mathcal{W}_k}(C)$ since the pair $(P_k, \pi_{p_k})$ is clearly among the pairs we are minimizing over.

Speaking of topological dimensions, one of the classical results is the following:

Lebesgue’s lemma: Let $M=[0,1]^n$ be the solid n-dimensional cube, then for any topological space $X$ with $\dim(X)<n$ and any continuous map $p: M \rightarrow X$ , we have image of at least one pair of opposite $(n-1)$ -faces intersect.

Since the conclusion is purely topological, this applies equally well to rectangles. i.e. for $M = [0, L_1] \times [0, L_2] \times \cdots \times [0, L_n]$ , $L_1 \geq L_2 \geq \cdots \geq L_n$ , we have $UW_{n-1}(M) \geq L_n$ ; furthermore, $UW_k(M) \geq L_{k+1}$ for all $k$ .

(If the later statement does not hold, we write $M$ as $M_1 \times M_2$ , $M_1$ being the product of the first $(k+1)$ coordinates. Now $UW_k(M) \geq UW_k(M_1) \geq L_{k+1}$ ).

In light of the earlier post about minimax inequality, we should note that if we restrict $X$ to be a homeomorphic copy of $\mathbb{R}^k$ then the notion is the same as the minimax length of fibres. In particular as proved in the post the minimax length of the unit disc to $\mathbb{R}$ is 2.

Exercise: Check that for the unit $2$ -disk, $UW_1(D^2) = \sqrt{3}$ , i.e. the optimum is obtained by contracting the disc onto a triod.

Hence it can indeed be strictly smaller than merely taking $\mathbb{R}^k$ as the targeting space, even for simply connected sets. This gives a better measurement of ‘width’ in the sense that, for example, the $\varepsilon$ neighborhood of a tree will have $1-width$ about $2 \varepsilon$ .

Area777

Chasing dreams from mathematics to the real world

On Uryson widths

Leave a Reply Cancel reply

Share this:

Like this:

Leave a Reply Cancel reply