On Uryson widths

ConanLeave a comment

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.

Leave a comment