Can we take shortcuts in Hilbert space?

2021-05-22
7 min read

How to add shortcuts in the plane

Imagine you have a network of roads. One way to judge the efficiency of the roads is in terms of how much longer it takes to travel between two points in your network than if you could just drive off-road in a straight line. This measure of efficiency is called quasiconvexity.

Definition: A set $E$ is $C$-quasiconvex meaning that for every $x,y\in \tilde{\Gamma}$, there is a curve $\gamma\subseteq \mathbb{R}^{2}$ connecting $x$ and $y$ so that $\ell(\gamma)\leq C|x-y|$.

Not every connected set of finite length is quasiconvex, and this note is about the problem of adding shortcuts to make it so.

Consider the following two examples.

The first curve is a circle with a small arc missing. If we have two points at either side of the missing arc, they will have to travel a long distance around the rest of the circle to reach each other. It can be shown that this curve is still $C$-quasiconvex although $C$ has to be very large and it will go to infinity as the size of the arc we removed goes to zero.

The second curve we see that any pair of points on either side of the cusp will need to travel a long distance through the curve (to the tip and back again) relative to their Euclidean distance, and this will get worse as the two points approach the tip. In this case, this curve won’t be $C$-quasiconvex for any $C$.

However, it is possible to “fix” a connected set by adding a controlled amount of shortcuts to it to complete it to a quasiconvex set.

Theorem 1: There is $C>1$ so that the following holds. Let $\Gamma\subseteq\mathbb{R}^{2}$ be a connected set of finite length. Then there is a curve $\tilde{\Gamma}\supseteq \Gamma$ so that

  1. $\ell(\tilde{\Gamma})\leq C\ell(\Gamma)$ and
  2. $\tilde{\Gamma}$ is $C$-quasiconvex.

By a curve, I mean a continuous image of an interval; by connected I mean topologically connected, and by length I mean one dimensional Hausdorff measure (so $\ell=\mathscr{H}^{1}$). From topology, you’ll remember that not all sets that are connected are path connected, but one can show that they are path connected if the set is also of finite length [Lemma 3.12, 5].

This result was originally shown in [Corollary 2, 6] by P. Jones. His proof actually requires a lot of complex analysis (see also [4], where the prerequisites for understanding the proof are developed assuming you are comfortable with complex analysis and measure theory). Kenyon and Kenyon later gave a purely geometric and more intuitive proof [7]. Their strategy was to develop an algorithm for adding shortcuts to the curve $\Gamma$ to make it better connected. For example, below on the left you see a connected set in black that consists of the longer sides of two segments forming a thin wedge. If we take two points on opposite sides of this wedge, the path joining them in the set (in green) is much longer than their mutual distance. The simple solution to make this set better connected is to add bridges along the wedge for points at the top of the wedge to access points on the bottom of the wedge, and one can do this by adding bridges that are no more than the length of the original wedge, as seen on the right.

This is a gross simplifcation, of course, but this gives an idea as to some of the steps in their construction.

How to add shortcuts in Euclidean space

The previous proofs rely heavily on the fact that the points lie in the plane. You would think that this should be easier since there is more space to lay the paths between the planets so that they avoid each other, but developing a systematic rule for constructing such a set is not obvious.

Das and Narasimhan showed that one could build a set $\Gamma$ over $E$ so that each pair of points in $E$ was connected by a short path through $\Gamma$, using techniques from graph theory and computational geometry. The drawback is that the set $\Gamma$ might not itself be well-connected (i.e. quasiconvex).

In [1], my advisor Schul and I overcame this last obstacle and showed the following.

Theorem 2: For all integers $d\geq 2$, there is $C>1$ so that the following holds. Let $\Gamma\subseteq\mathbb{R}^{d}$ be a connected set of finite length. Then there is a curve $\tilde{\Gamma}\supseteq \Gamma$ so that

  1. $\ell(\tilde{\Gamma})\leq C\ell(\Gamma)$ and
  2. $\tilde{\Gamma}$ is $C$-quasiconvex.

To prove this, we use the Analyst’s Traveling Salesman Theorem of P. Jones [6] as an accounting tool. Before stating it, we need some notation.

Given a compact set $E\subseteq\mathbb{R}^{2}$ and a square $Q\subseteq \mathbb{R}^{2}$, we define the $\beta$-number of $Q$ to be

$$\beta_{E}(Q) = \ell(Q)^{-1}\inf_{L} \sup_{x\in E\cap Q}{\rm dist}(x,L)$$

where $\ell(Q)$ is the side length of $Q$ and the infimum is over all lines $L\subseteq \mathbb{R}^{2}$. In other words, $\beta_{E}(Q)\ell(Q)$ is the radius (i.e. half the width) of the smallest rectangle containing $E\cap Q$.

The $\beta$-number gives a local and scale invariant way of measuring flatness of a set, local in the sense that we only care about how flat $E$ is inside $Q$, and scale invariant in the sense that, regardless of the true size of $Q$, if $\beta_{E}(Q)$ is small, then we know that if we look inside the square $E\cap Q$ will look very flat relative to $Q$.

Theorem (ATST): Let $\mathscr{D}$ be the set of dyadic squares in $\mathbb{R}^{2}$ and $E\subseteq \mathbb{R}^{2}$ a compact set. If $\Gamma$ is the curve of shortest length containing $E$, then the length of $\Gamma$ satisfies

$$\ell(\Gamma)\sim \beta(E):= {\rm diam} E + \sum_{Q\in \mathscr{D} \atop Q\cap E\neq\emptyset} \beta_{E}(3Q)^2\ell(Q). $$

Discussing the ATST would require a few lectures, but my goal in this article is mostly to motivate an open question related to this theorem and point to a few resources that would help someone get started on solving it.

Very roughly speaking, in our algorithm, if we encounter a cube $Q$ intersecting $\Gamma$ where there is a large gap between two components, then this will mean $\beta(3Q)\geq \epsilon$ where $\epsilon>0$ is some small fixed number.

Thus, we can place a bridge of length no more than some multiple of the size of $Q$, i.e. $\ell(Q)$. Since $\beta(3Q)\geq \epsilon$, this means the length of the bridge is in fact no more than a multiple of $\epsilon^{-2}\beta(3Q)^2\ell(Q)$, and so the ATST says that the sums of the lengths of all bridges we add is no more than $\ell(\Gamma)$.

This a gross simplification of the details (the paper is $\approx 40$ pages). In particular, there exist curves $\Gamma$ that are not $C$-quasiconvex for any $C$ which have $\beta(3Q)<\epsilon$ for all $Q\cap \Gamma\neq\emptyset$, and moreover one must take care that when building bridges they don’t form new cusps like in the first illustration in this post. But the previous illustration gives a basic idea of some of the ideas involved.

Can we add shortcuts in Hilbert space?

One aspect we couldn’t resolve in our paper was whether the constant $C$ in Theorem 2 relies on the dimension $d$ of the ambient space, or whether the theorem could hold in Hilbert space instead of $\mathbb{R}^{d}$. We made every effort to minimize the dependence on $d$; in particular under some assumptions on we make use of a version of the ATST that holds in Hilbert space [9], and in fact under some mild assumptions our result does hold in Hilbert space. However, there is only one step that prevents our proof from being dimension independent (see Remark 11 in [1]).

Bibliography

  1. J. Azzam and R. Schul, How to take shortcuts in Euclidean space: making a given set into a short quasi-convex set, Proc. Lond. Math. Soc. (3) 105 (2012), 367–392. Link.
  2. C. J. Bishop, Tree-like decompositions and conformal maps, Ann. Acad. Sci. Fenn. Math. 35 (2010), 389–404. Link.
  3. G. Das and G. Narasimhan, Short Cuts in Higher Dimensional Space, Proc. of the 7th Canadian Conference on Computational Geometry, 103-108, 1995.
  4. J. B. Garnett and D. E. Marshall, Harmonic measure, Cambridge University Press, 2008.
  5. K. J. Falconer, The geometry of fractal sets, Cambridge University Press, 1986.
  6. P. W. Jones, Rectifiable sets and the traveling salesman problem, Invent. Math. 102 (1990), 1–15. Link.
  7. C. Kenyon and R. Kenyon, How to take short cuts, Discrete Comput. Geom. 8 (1992), 251–264. Link.
  8. K. Okikiolu, Characterization of subsets of rectifiable curves in {${\bf R}^n$}, J. London Math. Soc. (2) 46 (1992), 336–348. Link.
  9. R. Schul, Subsets of rectifiable curves in Hilbert space—the analyst’s {TSP}, J. Anal. Math. 103 (2007), 331–375. Link.