Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 155 (Metric Embeddings)

A coarse embedding $f:X\to Y$ has nondecreasing control functions ${\rho }_{-},{\rho }_{+}$ such thatA family is a uniform coarse embedding of a family of metric spaces when all its maps use the same controls.

For $H_n=\{0,1{\}}^n$ with the Hamming distance, the coordinate map into ${\ell }_1^n$ satisfiesso the cubes embed isometrically and uniformly into $L^1$. The same coordinate map into ${\ell }_2^n$ satisfiesThus they also uniformly coarsely embed into $L^2$, with ${\rho }_{-}(t)={\rho }_{+}(t)=\sqrt{t}$. This is the Hamming cube as an L1 and L2 metric.

For a finite graph $G=(V,E)$, defineAn expander family is a sequence of graphs with orders tending to infinity, uniformly bounded degrees, and $h(G)$ uniformly bounded below.

Now let $|V|=n$ and let $M$ be a median of $f:V\to \mathbb{R}$. PutBoth supports have at most $n/2$ vertices. The layer-cake representation and the definition of $h$ giveand the same holds for $k$. Since their supports are disjoint,Adding givesThe triangle inequality also givesand henceRepresent an $L^1$-valued map as scalar functions on the underlying measure space and integrate this inequality. The result is the L1 Poincare inequality for an expander graph.

Suppose next that $G$ is $d$-regular and $F:V\to L^1$ is noncontracting with Lipschitz constant $D$. The Poincare inequality givesA ball of radius $r$ in a graph of maximum degree $d$ has at mostvertices. Therefore, forat least $n/2$ vertices lie outside the radius-$r$ ball about each vertex. Integrating the tail count of the distance givesConsequently every such $F$ haswhich proves the L1 distortion lower bound for an expander graph.

Finally, suppose an expander family admitted uniform coarse embeddings $F_n$ into $L^1$. Embedded edges have length at most ${\rho }_{+}(1)$, whereas the preceding Poincare argument and the fact that at least half the ordered pairs have distance comparable to $\log |V_n|$ implyThis contradicts ${\rho }_{-}(t)\to \infty$. Thus expanders do not uniformly coarsely embed into $L^1$. They do not uniformly coarsely embed into $L^2$ either: a Hilbert space embeds isometrically into an $L^1$ space byso an $L^2$ coarse embedding would produce an $L^1$ one. This is the expander graph obstruction to uniform coarse embedding.

The relation that $X$ is finitely representable in $Y$ means that every finite-dimensional subspace $E\subseteq X$ has, for every $\epsilon >0$, a linear copy in $Y$ of distortion below $1+\epsilon$. A superreflexive Banach space is one for which every Banach space finitely representable in it is a reflexive Banach space.

Suppose first that $X$ is reflexive and $(x_i)\subseteq B_X$. By weak compactness, the sequence has a weak cluster point $x\in B_X$. The point $x$ belongs to the weak closure of every tail convex hull, and the weak and norm closures of a convex set agree by the Hahn-Banach separation theorem. Choose a convex combinationwithin $\theta /2$ of $x$, enlarging $n$ beyond all indices used. Then choosewithin $\theta /2$ of $x$. It follows that $\Vert y-z\Vert <\theta$.

Conversely, the James reflexivity criterion in convex-block form says that a nonreflexive Banach space has a number $\theta >0$ and a sequence $(x_i)\subseteq B_X$ such thatfor every $n$. One obtains this form from the usual bidual separation proof by applying the principle of local reflexivity to each finite-dimensional stage. Such a sequence contradicts the asserted property. This proves the convex-block separation criterion for reflexivity.

Consider now the uniform finite version. If it fails for some $\theta >0$, choose for every $N$ a sequence $(x_i^{(N)}{)}_{i=1}^N\subseteq B_X$ for which every cut has convex-hull distance at least $\theta$. In a free ultrapower $X_{\mathcal{U}}$, letfilling the finitely many missing coordinates arbitrarily. Every initial-tail pair of convex hulls of $({\xi }_i)$ remains at distance at least $\theta$, so the first criterion makes $X_{\mathcal{U}}$ nonreflexive. Since an ultrapower is finitely representable in $X$, this contradicts superreflexivity.

Conversely, if $X$ is not superreflexive, choose a nonreflexive space $Y$ finitely representable in $X$. The first criterion supplies a sequence in $B_Y$ whose convex blocks are separated by some $\theta >0$. For each $N$, transfer the span of its first $N$ vectors to $X$ with distortion arbitrarily close to one and normalize. The resulting $N$-term sequence violates the uniform condition, with separation at least, say, $\theta /2$. This proves the uniform finite convex-block criterion for superreflexivity.

A purely metric equivalent is the diamond-graph characterization of superreflexivity:For sufficiency, argue contrapositively. If $X$ is not superreflexive, the preceding uniform criterion supplies arbitrarily long unit-ball sequences whose convex hulls stay a fixed distance apart across every cut. At each replacement step in the diamond graph, map the two new branches to convex combinations on opposite sides of the corresponding cut. The upper bound follows from convexity and the lower bound from the fixed separation. The standard recursive diamond construction therefore embeds every $D_m$ into $X$ with one distortion constant independent of $m$. Thus divergence of the diamond distortions forces superreflexivity.

The Bourgain embedding theorem states that every $n$-point metric space embeds into a Hilbert space with distortion at most $C\log n$; the random-subset construction may be taken to have dimension $O((\log n{)}^2)$.

We use the following finite Frechet embedding lemma. For every integer $q\ge 2$, an $n$-point metric space $X$ has subsets $A_1,\dots ,A_k$ such thatand, for every $x,y\in X$, some $A_i$ satisfiesHere is the probabilistic proof. Put $\vartheta =n^{-1/q}$. For every level $i=1,\dots ,q$, independently formrandom subsets $A_{i,j}$ by including each point with probability $p_i=\min \{1/2,n^{-i/q}\}$.

Fix $x,y$ and put $\Delta =d(x,y)/(2q-1)$. Form $q+1$ open balls $B_0,\dots ,B_q$ by taking $B_t$ to have radius $t\Delta$ and center $x$ for even $t$ and $y$ for odd $t$. Consecutive balls are disjoint because their radii sum to at most $(2q-1)\Delta =d(x,y)$. Partition the cardinality interval $[1,n]$ intoAmong the $q+1$ cardinalities $|B_t|$, either two consecutive ones lie in one interval, or some consecutive pair decreases. In either case there are $i,t$ such that, after orienting the pair appropriately,At level $i$, a random set hits $B_t$ with probability at least $\vartheta /3$ and misses the disjoint $B_{t+1}$ with probability at least $1/4$. These events are independent, and when both occur the two distance-to-set values differ by at least $\Delta$. Thus one sample succeeds with probability at least $\vartheta /12$. All $m$ samples at that level fail with probability at mostA union bound over the fewer than $n^2/2$ unordered pairs leaves a simultaneous successful choice. There are $qm\le Cq{n}^{1/q}\log n$ coordinates, proving the lemma.

DefineEvery distance-to-set coordinate is one-Lipschitz, while the lemma supplies the lower bound. Henceproving the Low-dimensional Frechet embedding into linfinity.

Take $q=\lceil \log n\rceil$. Then $n^{1/q}\le e$, $k=O((\log n{)}^2)$, and the distortion into ${\ell }_{\infty }^k$ is $O(\log n)$. Sincethe identity ${\ell }_{\infty }^k\to {\ell }_2^k$ has distortion $O(\log n)$. Composition gives

Finally let a $d$-regular expander $G$ embed into ${\ell }_{\infty }^k$ with distortion at most $\alpha$. For $1<p<\infty$, the identityhas distortion at most $k^{1/p}$. Therefore the assumed lower bound givesFor $k\ge e^2$, choose $p=\log k$, so $k^{1/p}=e$ andAdjusting the constant handles bounded $k$, and exponentiation proves the Dimension lower bound for an expander embedded in linfinitywhere $c>0$ depends only on $d$ and $h$.

The Johnson–Lindenstrauss lemma says that for $0<\epsilon <1$, every set of $N$ points in a Hilbert space admits a linear map into ${\ell }_2^m$, where $m\le C{\epsilon }^{-2}\log N$, such that every pairwise distance is multiplied by a factor in $[1-\epsilon ,1+\epsilon ]$.

Let $S$ be a maximal $\delta$-separated subset of the unit sphere $S_E$. Maximality makes it a $\delta$-net. The translates $s+(\delta /2)B_E$, $s\in S$, have disjoint interiors and lie in $(1+\delta /2)B_E$. Comparing $n$-dimensional volumes givesso

Put $M=\Vert T\Vert$. For every $x\in S_E$, choose $s\in S$ with $\Vert x-s\Vert \le \delta$. Thenand taking the supremum givesThe reverse triangle inequality givesThus $T$ is injective and the net estimate for a linear operator yields

For a standard normal $Y$, completing the square givesWith $\beta =\sqrt{2/\pi }$, setNow $H(0)=H^{\prime }(0)=0$. Its second derivative is bounded above on $[0,1]$, so Taylor's theorem gives $H(u)\le C{u}^2$ there. For $u\ge 1$, the elementary bound $\Phi (u)\le 1$ givesThis proves the first subgaussian concentration of the absolute Gaussian average estimate. The second estimate is supplied in the question.

For fixed $x\ne 0$, rotational invariance of a Gaussian vector giveswhere the $Y_i$ are independent standard normals. HenceFor the upper tail, the Chernoff bound and the preceding moment estimate giveChoosing $u=\beta \delta /(2C)$ gives $e^{-c{\delta }^{2}k}$; the supplied negative-moment bound gives the same lower-tail estimate. Therefore

Fix $\epsilon >0$ and choose $0<\delta <1/3$ so thatTake a $\delta$-net of $S^{n-1}$ with at most $(3/\delta {)}^n$ points. If $k\ge C_{\epsilon }n$, the union bound and the concentration estimate show that with positive probability the random map satisfies the required inequalities simultaneously on the net. The net estimate then proves the Almost-isometric Gaussian embedding from l2 into l1 with distortion below $1+\epsilon$.

For the final claim, first apply the Bourgain embedding theorem to the given $n$-point metric space, obtaining distortion $O(\log n)$ in Euclidean dimension $O((\log n{)}^2)$. Apply the Johnson–Lindenstrauss lemma to its $n$ image points, reducing the dimension to $m=O(\log n)$ at constant additional distortion. Finally apply the preceding Gaussian construction with $k=O(m)=O(\log n)$. The composition proves the Low-dimensional L1 embedding of a finite metric space: