Analyst’s Traveling Salesman Theorems. A Survey.

Raanan Schul

1 Introduction

The purpose of this essay is to present a partial survey of a family of theorems that are usually referred to as analyst’s traveling salesman theorems (also referred to as geometric traveling salesman theorems). There have been several new theorems recently added to this family of theorems which we feel should be collected together to give some bigger picture. Authors whose theorems we quote are David, Hahlomaa, Jones, Léger, Lerman, Okikiolu, Pajot, Semmes and the author of this essay. We will try and present things in a chronological order when it makes sense to do so. There are several excellent introductory sources we would like to refer the reader to. One is a survey by Guy David [Dav], another is a book by Hervé Pajot [Paj02], and yet another is the introduction of [DS93]. Finally, we mention that at the time of writing this, the result at the end of section 3.3 has not yet been submitted for publication.

The classical Traveling Salesman Problem is the problem of finding an optimal tour (of some restricted class) through a collection of cities, when given a set of roads connecting them. This is a famous problem in the computer science community. The Analyst’s version is similar, except one is allowed to talk about an arbitrary set of cities, meaning that one discusses questions like ‘what is the length of a shortest curve containing a given set K’. It turns out however, that one really discusses more. What one ends up discussing in the theorems we will present is a multi-scale geometric description of the set K. This in turn leads to a quantitative discussion of rectifiability. Because of the multi-scale nature of this theory, all the major difficulties present themselves when considering finite sets K. In the setting of ℂ (and ℝ^{d}), this relates to boundedness properties of singular integrals, and in particular to boundedness properties of the Cauchy integral, which was the original motivation for considering this multi-scale description. See [DS] or the surveys previously mentioned.

2 Some Definitions

≲ and ∼

Given two functions a and b into ℝ we say

a ≲ b

with constant C, when there exists a constant C = C_{a,b} such that

a ≤ Cb.

We say that a ∼ b if we have a ≲ b and b ≲ a.

K, M, Balls and Nets. Multiresolution Families

Let M be a metric space with metric dist(·, ·). We will fix a set K ⊂ M. We will always assume that diam(K) < ∞. This assumption may be removed for some of the results, however if we are to use D^{K} as defined below then we have a ‘largest’ scale. No constants will depend on diam(K) unless explicitly stated.

A ball Q is a set

Q = Ball(x, r) := {y : dist(x, y) ≤ r}

for some x ∈ M and some r > 0.

We say that X ⊂ K is an ϵ − net for K if

(i) for all x_{1}, x_{2} ∈ X we have dist(x_{1}, x_{2}) > ϵ (ii) for all y ∈ K there exits x ∈ X such that dist(x, y) ≤ ϵ Hence K ⊂ ⋃_{x∈X} Ball(x, ϵ) for an ϵ − net X for K. Note that if X′ ⊂ K satisfies (i) then

X′ can be extended to an ϵ − net X for K since a maximal subset of K satisfying (i), will satisfy (ii).

Fix a set K. Denote by X_{n}^{K} a sequence of 2^{−n} − nets for K, such that X_{n}^{K} ⊂ X_{n+1}^{K}. Set

D^{K} = {Ball(x, A2^{−n}) : x ∈ X_{n}^{K}, n an integer, n > n_{0}}

for a constants A > A_{0} > 1 and integer n_{0}. The constant A_{0} is fixed large enough (independently of K) so that a collection of theorems we discuss later will hold. We require n_{0} < − log(diam(K)).

Remark 2.1. The constant n_{0} is only needed to assure that we indeed have such a sequence of nets. The constants in the theorems we state will be independent of the particular choice of n_{0}, and so it is suppressed in the notation. One may choose X_{n_{0}}, and then for n > n_{0} build X_{n}^{K} from X_{n−1}^{K} by extending to a 2^{−n} − net.

Remark 2.2. For some of the theorems the requirement of X_{n}^{K} ⊂ X_{n+1}^{K} is not needed.

We call D^{K} a multiresolution family. Note that D^{K} depends on K.

Lipschitz Functions, Rectifiable Sets, Rectifiable curves

A function f : ℝ^{k} → M is said to be Lipschitz if

\frac{dist(f(x), f(y))}{∥x − y∥} ≤ C_{f}, ∀x, y ∈ ℝ^{k}.

A set is called k-rectifiable if it is contained in a countable union of images of Lipschitz functions f_{j} : ℝ^{k} → M, except for a set of k-dimensional Hausdorff measure zero. For more details see [Mat95], where one can also find an excellent discussion of rectifiability in the setting of ℝ^{d}, part of which carries over to the setting of other metric spaces.

A set is called a rectifiable curve if it is the image a Lipschitz function defined on ℝ. A standard result is that if Γ is a connected set of finite (Hausdorff) length then it is a rectifiable curve.

Ahlfors-Regularity

Given a set K we say that K is k-Ahlfors-Regular if there is a C > 0 so that for all x ∈ K and 0 < r < diam(K) we have

\frac{r^{k}}{C} ≤ H^{k}|_{K}(Ball(x, r)) < Cr^{k}.

Some of the theorems below will deal with 1-Ahlfors-Regular sets. One can view those theorem and proofs as a discussion about a Carleson measure with support on K × ℝ_{+}.

The Jones β Numbers

Assume we have a set K lying in ℝ^{d}. Consider Q a cube or ball. We define the Jones β_{∞} number as

β_{∞,K}(Q) = \frac{1}{diam(Q)} inf_{L line} sup_{x∈K∩Q} dist(x, L)
= \frac{radius of thinnest cylinder containing K ∩ Q}{diam(Q)}.

Hence if K̂ ⊃ K then β_{∞,K̂}(Q) ≥ β_{∞,K}(Q). Note that we have defined a quantity which is scale independent. This quantity has L^{p} variants. Given a locally finite measure μ and 1 ≤ p < ∞, one defines

β_{p,μ}(Q) = \frac{1}{diam(Q)} inf_{L line}\{∫_{Q} dist(y, L)^{p} \frac{dμ(y)}{μ(Q)}\}^{1/p}.

L  ^{h}  ^{K ∩ Q} Figure 1: h = β^{∞,K}(Q)diam(Q)

Clearly

β_{p,μ} ≤ β_{∞,supp(μ)}.  (2.1)

We define β_{∞,μ} = β_{∞,supp(μ)}.

Various other definitions of β(Ball(x, r)) will appear below, with various sub-indices. The common thread is that they in some sense measure how far a set K ∩ Ball(x, r) is from being along a geodesic (when this has a meaning), and that they are scale invariant.

Menger Curvature and other quantities

Let x_{1}, x_{2}, x_{3} ∈ M be three distinct points. Take x′_{1}, x′_{2}, x′_{3} ∈ ℂ such that dist(x_{i}, x_{j}) = |x′_{i} − x′_{j}| for 1 ≤ i, j ≤ 3. If x′_{1}, x′_{2}, x′_{3} are collinear then define

c(x_{1}, x_{2}, x_{3}) := 0.

Otherwise, let R be the radius of the circle going through x′_{1}, x′_{2}, x′_{3}. In this case define

c(x_{1}, x_{2}, x_{3}) := \frac{1}{R}.

This quantity is referred to as the Menger curvature of the triple x_{1}, x_{2}, x_{3}.

For an ordered triple (x_{1}, x_{2}, x_{3}) ∈ M^{3} we define

∂_{1}(x_{1}, x_{2}, x_{3}) := dist(x_{1}, x_{2}) + dist(x_{2}, x_{3}) − dist(x_{1}, x_{3}).

Let {x_{1}, x_{2}, x_{3}} ⊂ M be an unordered triple. Assume without loss of generality dist(x_{1}, x_{2}) ≤ dist(x_{2}, x_{3}) ≤ dist(x_{1}, x_{3}). Define

∂({x_{1}, x_{2}, x_{3}}) := ∂_{1}(x_{1}, x_{2}, x_{3}),

or equivalently

∂({x_{1}, x_{2}, x_{3}}) = min_{σ∈S_{3}} ∂_{1}(x_{σ(1)}, x_{σ(2)}, x_{σ(3)}).

Hence we have for all {x, y, z} ⊂ M

0 ≤ ∂({x, y, z}) ≤ ∂_{1}(x, y, z)

where non-negativity follows from the triangle inequality.

Remark 2.3. If

dist(x, y) ≤ dist(y, z) ≤ dist(x, z) ≤ A · dist(x, y)  (2.2)

then

c^{2}(x, y, z)diam{x, y, z}^{3} ∼ ∂({x, y, z})

with constant depending only on A. See [Hah05].

Moreover, in a Euclidean space, by the Pythagorean theorem,

β_{∞,{x,y,z}}^{2}(Ball(x, diam{x, y, z})diam{x, y, z} ∼ ∂({x, y, z})  (2.3)

with constant depending only on A.

3 Traveling Salesman Theorems

3.1 ℝ^{d}

We start by stating two theorems. We will give a different formulations than the original statements. The reason for this is that these formulation will generalize nicely later in the survey. In the context of ℝ^{d} the formulations we give are equivalent to the original ones. The first theorem is a quantitative way of saying ‘a connected set is flat at most scales in most locations’.

Theorem 3.1. [Jon90, Oki92] For any connected set Γ ⊂ ℝ^{d} such that Γ ⊃ K we have

∑_{D^{K}} β_{∞,Γ}^{2}(Q)diam(Q) ≲ H^{1}(Γ).  (3.1)

This was first proven for d = 2 by Jones using complex analysis, and then extended to all d by Okikiolu, who used geometric methods. The constant that comes out of Okikiolu’s proof depends exponentially on the dimension d, however in remark 3.6 we will state a stronger result. The following theorem gives a very good reason to care about the left hand side of inequality (3.1).

Theorem 3.2. [Jon90] Suppose A_{0} is large enough. Given a set K ⊂ ℝ^{d}, there exists a connected set Γ_{0} ⊃ K such that the length of Γ_{0} satisfies

H^{1}(Γ_{0}) ≲ diam(K) + ∑_{D^{K}} β_{∞,K}^{2}(Q)diam(Q).  (3.2)

Again, the constant which comes out of the original proof is exponential in the dimension d, but more general versions of this theorem exist where the dimension d becomes irrelevant. See remark 3.6 and theorem 3.8.

One can actually get a little more from the proofs that were given in [Jon90, Oki92] to these theorems. If Γ is 1-Ahlfors regular then for all z ∈ Γ and R > 0

∑_{{Q∈D^{K} \atop Q⊂B(z,R)}} β_{∞,Γ}^{2}(Q)diam(Q) ≲ R.  (3.3)

Conversely, if one has the condition that for all z ∈ K and R > 0

∑_{{Q∈D^{K} \atop Q⊂B(z,R)}} β_{∞,K}^{2}(Q)diam(Q) ≲ R  (3.4)

then the construction yields a 1-Ahlfors-Regular Γ_{0} (recall that we had assumed diam(K) < ∞).

In any case, combining theorems 3.1 and 3.2 one gets

diam(K) + ∑_{D^{K}} β_{∞,K}^{2}(Q)diam(Q) ∼ H^{1}(Γ_{MST})

where Γ_{MST} is the shortest curve containing K.

We will give some idea of the arguments that are used for the proofs theorems 3.1 and 3.2 after we discuss their generalizations and variations in various categories. We will try and discuss them in a roughly chronological order. Note that some theorems will contain only a variation or generalization of theorem 3.2, whereas others will do so for both theorem 3.1 and theorem 3.2.

3.2 Variations in ℝ^{d}

We start with a theorem by David and Semmes, who showed the following, which contains both a variation of theorem 3.1 and a variation of theorem 3.2.

Theorem 3.3. [DS] Let K ⊂ ℝ^{d} be a 1-Ahlfors-Regular set and 1 ≤ q ≤ ∞. Then K is contained in a connected 1-Ahlfors-Regular set if and only if for all z ∈ K and 0 < R < diam(K)

∫_{0}^{R} ∫_{Ball(z,R)} β_{q,H^{1}|_{K}}(Ball(x, t))^{2}dH^{1}|_{K}(x)\frac{dt}{t} ≲ R.  (3.5)

Remark 3.4. Note that the left hand side of inequality (3.5) can be discretized as a multiresolution sum as in the left hand side of inequality (3.3).

Remark 3.5. The theorem we stated is a special case of much more general theorem which was proved in [DS]. The general theorem deals with sets in ℝ^{d}, which are k-Ahlfors-Regular for k ≥ 1. It gives an equivalence between several conditions that vary from the above conditions, which are of geometric type, to conditions which have to do with the boundedness of a family of singular integral operators. Since they show much more, the route they take to show theorem 3.3 is different (and in particular, less direct) than the route used in the proofs of the other results we discuss.

Later, in [Paj96], Pajot gave a construction which was based on [Jon90], and gives another variation on theorem 3.2. For a compact 1-Ahlfors-Regular set K satisfying (3.5) and 1 ≤ q, he constructed a 1-Ahlfors-Regular connected set Γ_{0} ⊃ K. This set satisfied

H^{1}(Γ_{0}) ≲ diam(K) + ∫_{0}^{diam(K)} ∫ β_{q,H^{1}|_{K}}(Ball(x, t))^{2}dH^{1}|_{K}(x)\frac{dt}{t}.  (3.6)

This gives a more direct proof of theorem 3.3 as we stated it, but does not prove the full result of [DS]. Note that since β_{q,H^{1}|_{K}} ≤ β_{∞,K}, there is no need to show anything along the lines of theorem 3.1.

3.3 Beyond ℝ^{d}

The next evolution of these theorems came recently. The topic of interest was varying the ambient space. Several results deal with substituting ℝ^{d} by other metric spaces. We start with a remark about the dependence on the ambient dimension d.

Remark 3.6. It turns out that both theorem 3.1 and theorem 3.2 hold with constants independent of the dimension d. In fact, they hold in the setting of an infinite dimensional Hilbert space. Both of these were shown in [Schb]. For theorem 3.2, this statement can also be deduced from [Hah05].

The original formulation of theorems 3.1 and 3.2 had the sums on the left hand side of inequality (3.1) and the right hand side of inequality (3.2) being over cubes which are triples of cubes in a dyadic grid on ℝ^{d}. With that formulation, the dependence of the constant of theorem 3.1 on the dimension d is indeed exponential!

We continue with a result by Ferrari, Franchi and Pajot. This is a Heisenberg group analogue of theorem 3.2. Their first task was to define the analogue of β. Let ℍ be the first Heisenberg group with the Carnot-Caratheodory metric d_{ℍ}. As in [FFP], we follow the notation of [Ste93], denoting P_{k} ∈ ℍ by P_{k} = [z_{k}, t_{k}] = [x_{k} + iy_{k}, t_{k}] and P_{1} · P_{2} = [z_{1} + z_{2}, t_{1} + t_{2} + 2ℑ(z_{1}z̄_{2})]. Denote by G(ℍ, 1) the set of elements of the form a · r, where a ∈ ℍ is any element, and r is a Euclidean straight line in the set {[z, 0] : z ∈ ℂ} going through the origin. Define

β_{ℍ}_{,K}(Ball(P, t)) = inf_{L∈G(ℍ,1)} sup_{P′∈Ball(P,t)∩K} \frac{d_{ℍ}(P′, L)}{t},

where a ball is of course a ball with respect to d_{ℍ}. This definition of β_{ℍ} is of interest since in [FFP] they prove the following theorem.

Theorem 3.7. [FFP] Suppose A_{0} is large enough. Let K ∈ ℍ be a compact set. Then there exists a connected set Γ_{0} ⊃ K. The length of Γ_{0} satisfies

H^{1}(Γ_{0}) ≲ diam(K) + ∑_{D^{K}} β_{ℍ}_{,K}^{2}(Q)diam(Q).

(They actually give an equivalent integral formulation.) One would like some variation of theorem 3.1 in this setting as well. In [FFP] this is shown for some class of sets Γ, namely images of C^{1,α} regular simple horizontal curves (defined in [FFP]). We refer the reader to the original for more details and definitions.

In [Hah05] Hahlomaa proves the following.

Theorem 3.8. [Hah05] Suppose A_{0} is large enough. Let M be a metric space. Let K ⊂ M. Let Q ∈ D^{K}. Define

β_{M,∞,K}^{2}(Q)diam(Q) = diam(Q)^{3} sup_{x_{1},x_{2},x_{3}∈Q dist(x_{i},x_{j})≥A^{−1}diam(Q)} c^{2}(x_{1}, x_{2}, x_{3}).  (3.7)

Then there exists K′ ⊂ [0, 1] and a function f : K′ → K such that

∥f∥_{Lip} ≲ diam(K) + ∑_{D^{K}} β_{M,∞,K}^{2}(Q)diam(Q)

and Image(f) = K.

Notice that remark 2.3 relates this theorem to theorem 3.2. Also note that if M is a complete geodesic space than one may extend f to a function with the same Lipschitz constant and the domain [0, 1]. In fact this theorem generalizes theorem 3.2 further than [Schb] (and may have even been done prior to it!). Unfortunately, the analogue of theorem 3.1 is false in this metric space setting. We give an example which illustrates this.

3.3.1 An example

Consider the plane (ℝ^{2}) with the taxi-cab metric (i.e. dist((x_{1}, y_{1}), (x_{2}, y_{2})) = |x_{1} − x_{2}| + |y_{1} − y_{2}|). This is an isometric subset of L^{1}. Let N ∈ ℕ and ϵ > 0 be constants. Set

Γ = ([0, 1] × \{0\}) ∪ ⋃_{{d= \frac{k}{2^{N}} \atop 0<k<2^{N}}} (\{d\} × [0, ϵ2^{−i(d)}]),

where d = \frac{j}{2^{i(d)}} in reduced form.

Figure 2: Γ for ϵ = \frac{1}{8} and N = 4

Consider X_{n} = \{(x, 0) : x = \frac{k}{2^{n}} , 0 ≤ k ≤ 2^{n}\} dyadic numbers of scale 2^{−n} and the family of balls around it of radius \frac{A}{2^{n}}, giving D^{Γ}.

We have

H^{1}(Γ) = 1 + ϵ(1 + 2\frac{1}{2} + 4\frac{1}{4} + ... + 2^{N} \frac{1}{2^{N}}) = 1 + ϵN.

Consider

Q_{m,d} = Ball(d, \frac{A}{2^{m}}),

where d = \frac{k}{2^{n}} , 1 ≤ n ≤ N, 0 < k < 2^{n}, m ≥ n. We have

β_{M,∞,Γ}^{2}(Q_{m,d})diam(Q_{m,d}) ≳ min{diam(Q_{m,d}), ϵ2^{−n}}

for all such Q (with constant independent of m, d). Summing over m, this gives a total of

≳ log(\frac{1}{ϵ})ϵ2^{−n}

for each d = \frac{k}{2^{n}}.

We now sum over d to get

∑_{D^{Γ}} β_{M,∞,Γ}^{2}(Q)diam(Q) ≳ log(\frac{1}{ϵ})ϵN.

Choosing ϵ and N properly we get that there is no universal constant C such that

∑_{D^{Γ}} β_{M,∞,Γ}^{2}(Q)diam(Q) ≤ CH^{1}(Γ).

Remark 3.9. As pointed out by Hahlomaa, this example is not entirely satisfactory in the following sense. One may strengthen the constraints on the set over which the supremum is taken in equation (3.7) and still get theorem 3.8. One may also choose to look at a smaller set of balls then the one in D^{K} and again, still get theorem 3.8. Finally, one may look at the infimum over all ‘suitable’ collections of balls D^{K} rather than just any choice. If one does that, then the example given is not satisfactory to be convinced that a variation of theorem 3.1 is false in this setting.

Fortunately, we are able to say more in the category of 1-Ahlfors-regular sets, as is seen from the following sequence of theorems.

Theorem 3.10. [Hahb] Let K be a 1-Ahlfors-Regular set in a metric space M with metric dist(·, ·). Then

inf ∥f∥_{Lip} ≲ diam(K) + ∫ ∫ ∫ c^{2}(x_{1}, x_{2}, x_{3})dH^{1}|_{K}(x_{3})dH^{1}|_{K}(x_{2})dH^{1}|_{K}(x_{1})

where the infimum on the left hand side is over functions f : K′ → K with K′ ⊂ [0, 1], the norm ∥ · ∥_{Lip} is the Lipschitz norm, and the integral on the right hand side is over all triples x_{1}, x_{2}, x_{3} ∈ K such that

A · dist(x_{i}, x_{j}) ≥ diam{x_{1}, x_{2}, x_{3}}.

This is a reformulation of the main theorem in [Hahb] according to a remark at the end of the paper. Note that this is very close to the inequality (3.6). To see this one must decompose the integral into triples of comparable diameters, and then discretize the integral. Let us give another version of this theorem, which comes out of the proof of [Hahb], and is reminiscent of the if half of theorem 3.3 (i.e. the analogue of theorem 3.2).

Theorem 3.11. [Haha] Let K be a 1-Ahlfors-Regular set in a complete geodesic metric space M with metric dist(·, ·), so that diam(K) < ∞. Assume further, that for all z ∈ K and R > 0

∫ ∫ ∫ c^{2}(x_{1}, x_{2}, x_{3})dH^{1}|_{K}(x_{3})dH^{1}|_{K}(x_{2})dH^{1}|_{K}(x_{1}) ≤ C_{0}R

where the integral on the left hand side is over all triples x_{1}, x_{2}, x_{3} ∈ K ∩Ball(z, R) such that

A · dist(x_{i}, x_{j}) ≥ diam{x_{1}, x_{2}, x_{3}}.

Then there is a 1-Ahlfors-Regular connected set Γ_{0} ⊃ K, whose constant depends only on C_{0} and on the 1-Ahlfors-Regularity constant of K.

A nice feature of the above theorem is that the analogue to theorem 3.1 holds for it. We show in [Scha]

Theorem 3.12. [Scha] Let Γ be a connected 1-Ahlfors-Regular set in a metric space M with metric dist(·, ·). Then for all z ∈ Γ and R > 0

∫ ∫ ∫ c^{2}(x_{1}, x_{2}, x_{3})dH^{1}|_{Γ}(x_{3})dH^{1}|_{Γ}(x_{2})dH^{1}|_{Γ}(x_{1}) ≲ R  (3.8)

with constant depending only on the 1-Ahlfors-Regularity constant of Γ, where the integral on the left hand side is over all triples x_{1}, x_{2}, x_{3} ∈ Γ ∩ Ball(z, R) such that

A · dist(x_{i}, x_{j}) ≥ diam{x_{1}, x_{2}, x_{3}}.

In fact, a little more is true. One may replace inequality (3.8) by

∫ ∫ ∫_{(Γ∩Ball(z,R))^{3}} \frac{∂(\{x_{1}, x_{2}, x_{3}\})}{diam\{x_{1}, x_{2}, x_{3}\}^{3}} dH^{1}|_{Γ}(x_{3})dH^{1}|_{Γ}(x_{2})dH^{1}|_{Γ}(x_{1}) ≲ R.  (3.9)

Note that in inequality (3.9) we are integrating over all triples in (Γ ∩ Ball(z, R))^{3}.

3.4 Argument Outlines

We try in this section to give some idea of what arguments for most of the above theorems look like (the proof in [DS] is the exception). These are not easy theorems, and what we say below ignores many precise details, technicalities and hard work that had to be done by the authors attributed to these theorems. Needless to say, technicalities in different settings are of different nature! An important observation is that in the Euclidean cases, a main ingredient is inequality (2.3) which is essentially the Pythagorean theorem, whereas in the Metric cases, one simply defines β in a way which gives the information on the right hand side of inequality (2.3).

3.4.1 Theorem 3.1, Generalizations and Variations

Let Γ by given. Using a standard result for abstract graphs and a compactness property, one may obtain a Lipschitz parameterization of Γ, γ : [0, 1] → Γ, with Lipschitz norm bounded by a constant times the length (one dimensional Hausdorff measure) of Γ. If Γ is 1-Ahlfors-Regular to begin with, then γ can be taken to satisfy |γ^{−1}(Ball(x, r))| ≲ r. In either case, one fixes γ and uses it throughout the proof.

Assume first that for all x ∈ Γ and r ≥ 0 we have that γ^{−1}(Ball(x, r)) has only one connected component. Then one can translate the question of bounding ∑ β^{2}(Q)diam(Q), to a question about the geometry of the image under γ of a multiresolution on the domain of γ. It is sometimes non-trivial to obtain a useful multiresolution of the domain. Using the idea of successive approximations, either inequality (2.3) (in the Euclidean case) or the definition of β (the metric case), and some standard summation techniques one gets the desired estimate. This idea was used in [Jon90, Oki92, Schb, Scha]. An important point is that one may also use this idea to deal with balls where there is an arc which, up to a constant, is far enough from being along a geodesic.

Balls where this idea cannot be used are harder to deal with. For such a ball Q, one can philosophically consider the case where Γ ∩ Q is a collection of straight line segments with endpoints outside the ball. In [Jon90] complex analysis comes into play. In [Oki92] geometric ideas are used, and in [Schb, Scha] they are carried further. We give these geometric ideas in the language of [Schb, Scha]. For such a ball Q, one assigns a weight w_{Q} to the set Γ ∩ Q. This is done in such a way, that for every Q, ∫ w_{Q}dH^{1}|_{Γ} ≥ β^{2}(Q)diam(Q) and for every x, ∑_{Q} w_{Q}(x) ≤ 1. In fact, a little more is obtained, namely control by ∫ w_{Q}dH^{1}|_{Γ} of

β(Q)diam(Q) rather then just β^{2}(Q)diam(Q). Either way, since one may exchange the sum and the integral, one gets the desired estimate.

3.4.2 Theorem 3.2, Generalizations and Variations

We briefly discuss the construction of Γ_{0}. Most variations of theorem 3.2 use a similar theme to the one we give below.

The construction of Γ_{0} is a multi-scale construction, starting from the ‘roughest’ scale and then refining.

x  y x  z  y

Figure 3: Stage n (left) and stage n + 1 (right).

Let us first consider a naive approach to doing so. Suppose we have at stage n a connected graph Γ^{n}, with vertices X_{n}. Suppose further, that Γ^{n+1} is obtained from Γ^{n} by modifying the edges of Γ^{n}. We would like to use either inequality (2.3) (Euclidean case) or the definition of β (metric case) to estimate the difference in length between Γ^{n+1} and Γ^{n} by the sum of β^{2}(Q)diam(Q) for Q of radius A2^{−n}. At a first glance it is tempting to think that at least for the category of β_{∞} this is trivial. Unfortunately, even in that category difficulties arise.

Generally speaking, there are three cases. The first case is that β_{∞}(Q) ≥ ϵ_{0}, some universal constant. This case can usually be handled by crude estimates. (In [Schb, Hah05] one needs to be a little careful in this case since there are potentially unboundedly many points in (X_{n+1} ∖ X_{n}) ∩ Q.) The second case, is the case where one may indeed apply inequality (2.3). This is when the picture looks locally like figure 3, with comparable mutual distances between x, y and z, i.e. x, y ∈ X_{n}, z ∈ X_{n+1}, and β_{∞}(Q) ≤ ϵ_{0}. Finally, there is the case where β_{∞}(Q) ≤ ϵ_{0} but either the distances between x, y and z are not comparable, or the picture is not as in figure 3. One example is x = (0, 0), y = (1, 0), z = (1 − ϵ, ϵ) where ϵ is small. This is in practice broken up into several cases, but the general philosophy is that one uses coarser scales to account for the difference in length between Γ^{n+1} and Γ^{n} in Q, which is not so easy to do.

Remark 3.13. A consequence of these ideas is that as in inequality (3.4) , local control on β numbers gives local control on length.

These ideas first appeared in [Jon90] and were later used in [Hah05, Paj96, FFP, Schb], where more difficulties had to be dealt with. For instance the main difficulty in [FFP] is to relate β_{ℍ} to the right hand side of inequality (2.3). In addition, the cases where one uses an average rather than a supremum for the Jones-β number (i.e. [Paj96, Hahb]) require some more work.

3.5 Other traveling salesman type theorems

We conclude with mentioning some results that use similar quantities, but are of a little different nature. (One should note that these results appeared before several results we have already mentioned)

We say that Γ is a 1-Lipschitz graph if it is an isometric image of the graph of a Lipschitz function from ℝ to ℝ^{d−1}. A result by Léger gives the following.

Theorem 3.14. [Lég99] Let K ⊂ ℝ^{d} be a set with 0 < H^{1}(K) < ∞. Suppose further that

∫ ∫ ∫_{K^{3}} c^{2}(x_{1}, x_{2}, x_{3})dH^{1}|_{K}(x_{3})dH^{1}|_{K}(x_{2})dH^{1}|_{K}(x_{1}) < ∞.

Then K is 1-rectifiable.

Let us also state a key lemma from the proof of the above theorem, which quite clearly fits in with the results we discussed in previous sections.

Lemma 3.15. [Lég99] For any fixed C_{0} ≥ 10 there exists a number η > 0 such that if μ is a compactly supported Borel measure on ℝ^{d} satisfying

(i) μ(Ball(0, 2)) ≥ 1, μ(ℝ^{d} ∖ Ball(0, 2)) = 0

(ii) for any ball B, μ(B) ≤ C_{0}diam(B)

(iii) ∫ ∫ ∫_{(ℝ^{d})^{3}} c^{2}(x_{1}, x_{2}, x_{3})dμ(x_{3})dμ(x_{2})dμ(x_{1}) ≤ η then there is a 1-Lipschitz graph Γ such that

μ(Γ) ≥ \frac{99}{100}μ(ℝ^{d})

Note that there is no assumption on the 1-Ahlfors-Regularity of μ.

For the next result we need a few more definitions. Let μ be a locally finite Borel measure on ℝ^{d}. Set

J_{2}(x) = ∑_{Q∈dyadic grid Q∋x} β_{2,μ}^{2}(Q).  (3.10)

Denote by J_{Q_{0}}(x), where Q_{0} is a given cube (with sides parallel to the axes) the analogue of J_{2}(x), but where we only consider cubes Q ⊂ Q_{0} in the sum (3.10).

We can now give a result by Lerman, which is of nature similar to the previous lemma.

Theorem 3.16. [Ler03]. There exist a constants C_{1}, C_{2}, C_{3} > 1, that depends only on d, such that if μ is a locally finite Borel measure on ℝ^{d}, Q_{0} is a cube, and if

∫_{C_{1}Q_{0}} e^{C_{2}J_{Q_{0}}(x)}dμ(x) ≤ Aμ(Q_{0})  (3.11)

(for some A > 0), then there is a curve Γ ⊂ C_{1}Q_{0} such that

μ(Γ) ≥ C_{3}^{−1}A^{−1}μ(Q_{0})  (3.12)

and

H^{1}(Γ) ≤ C_{3}Adiam(Q_{0}).  (3.13)

Here, C_{1}Q_{0} is a cube with sides parallel to those of Q, which is a dilate of Q by C_{1} (with the same center). This result is a (difficult) variant of a result by Bishop and Jones about the β_{∞} case (see [BJ94]).

References

[BJ94] Christopher J. Bishop and Peter W. Jones. Harmonic measure, L^{2} estimates and the Schwarzian derivative. J. Anal. Math., 62:77–113, 1994.

[Dav] Guy David. http://www.math.u-psud.fr/∼gdavid/Notes-Parkcity.dvi.

[DS] G. David and S. Semmes. Singular integrals and rectifiable sets in R^{n}: Au-delá des graphes lipschitziens.

[DS93] Guy David and Stephen Semmes. Analysis of and on uniformly rectifiable sets, volume 38 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 1993.

[FFP] Fausto Ferrari, Bruno Franchi, and Hervé Pajot. The geometric traveling salesman problem in the Heisenberg group. Preprint.

[Haha] Immo Hahlomaa. Personal communication.

[Hahb] Immo Hahlomaa. Curvature and Lipschitz parametrizations in 1-regular metric spaces. Annales Academiae Scientiarum Fennicae.

[Hah05] Immo Hahlomaa. Menger curvature and Lipschitz parametrizations in metric spaces. Fund. Math., pages 143–169, 2005.

[Jon90] Peter W. Jones. Rectifiable sets and the traveling salesman problem. Invent. Math., 102(1):1–15, 1990.

[Lég99] J. C. Léger. Menger curvature and rectifiability. Ann. of Math. (2), 149(3):831–869, 1999.

[Ler03] Gilad Lerman. Quantifying curvelike structures of measures by using L_{2} Jones quantities. Comm. Pure Appl. Math., 56(9):1294–1365, 2003.

[Mat95] Pertti Mattila. Geometry of sets and measures in Euclidean spaces. Fractals and rectifiability, volume 44 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995.

[Oki92] Kate Okikiolu. Characterization of subsets of rectifiable curves in R^{n}. J. London Math. Soc. (2), 46(2):336–348, 1992.

[Paj96] Hervé Pajot. Sous-ensembles de courbes Ahlfors-régulières et nombres de Jones. Publ. Mat., 40(2):497–526, 1996.

[Paj02] Hervé Pajot. Analytic capacity, rectifiability, Menger curvature and the Cauchy integral, volume 1799 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2002.

[Scha] Raanan Schul. Ahlfors-regular curves in metric spaces. In preperation.

[Schb] Raanan Schul. Subsets of rectifiable curves in Hilbert space. Submitted.

[Ste93] Elias M. Stein. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, volume 43 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1993. With the assistance of Timothy S. Murphy, Monographs in Harmonic Analysis, III.