Bilipschitz embeddings of metric spaces into Euclidean spaces
Abstract
When does a metric space admit a bilipschitz embedding into some finite-dimensional Euclidean space? There does not seem to be a simple answer to this question. Results of Assouad [A1], [A2], [A3] do provide a simple answer if one permits some small («snowflake») deformations of the metric, but unfortunately these deformations immediately disrupt some basic aspects of geometry and analysis, like rectifiability, differentiability, and curves of finite length. Here we discuss a (somewhat technical) criterion which permits more modest deformations, based on small powers of an A1 weight. For many purposes this type of deformation is quite innocuous, as in standard results in harmonic analysis about Ap weights [J], [Ga], [St2]. In particular, it cooperates well with «uniform rectifiability» [DS2], [DS4].
Full text
Publicacions Matem`atiques, Vol 43 (1999), 571–653. BILIPSCHITZ EMBEDDINGS OF METRIC SPACES INTO EUCLIDEAN SPACES S. Semmes∗ Abstract When does a metric space admit a bilipschitz embedding into some finite-dimensional Euclidean space? There does not seem to be a simple answer to this question. Results of Assouad [A1], [A2], [A3] do provide a simple answer if one permits some small (“snowflake”) deformations of the metric, but unfortunately these deformations immediately disrupt some basic aspects of geometry and analysis, like rectifiability, differentiability, and curves of finite length. Here we discuss a (somewhat technical) criterion which permits more modest deformations, based on small powers of an A1weight. For many purposes this type of deformation is quite innocuous, as in standard results in harmonic analysis about Ap weights [J], [Ga], [St2]. In particular, it cooperates well with “uniform rectifiability” [DS2], [DS4]. 1. Preliminaries Let (M,d(x, y)) be a metric space. Thus Mis a nonempty set, and d(x, y) is a symmetric nonnegative function on M×Mwhich vanishes exactly on the diagonal and satisfies the triangle inequality. Question 1.1. Under what conditions does (M,d(x, y)) admit a bilipschitz embedding into some Rm? ∗Partially supported by the U.S. National Science Foundation. The author would also like to thank Kevin Rogovin for pointing out some oversights in a previous version of this paper. The author is grateful too to the referee for his or her comments and suggestions.
572 S. Semmes In other words, under what conditions does there exist a mapping f:M→Rm(for some finite m) such that (1.2) C−1d(x, y)≤|f(x)−f(y)|≤Cd(x, y) for some constant Cand all x, y ∈M? When this type of embedding exists, it roughly means that one might as well think of Mas living in a finite-dimensional Euclidean space to begin with, which can be very useful. There is a simple necessary condition for this to occur, which is that M be doubling. This means that there is a constant kso that every ball in M can be covered by kballs of half the radius. It is not hard to show that Euclidean spaces satisfy the doubling property, and that the doubling property is inherited by spaces which admit bilipschitz embeddings into other spaces that are doubling. A partial converse to this was given by Assouad [A1], [A2], [A3]. Theorem 1.3 (Assouad). Let (M,d(x, y)) be a metric space which is doubling. Then for each s∈(0,1), the metric space (M,d(x, y)s) admits a bilipschitz embedding into some Rm(with mand the bilipschitz constant depending on sand the doubling constant for M). It is well-known (and not difficult to prove) that (M,d(x, y)s) is automatically a metric space when (M,d(x, y)) is, assuming that 0<s<1. One can also check that (M,d(x, y)s) is doubling if and only if (M,d(x, y)). The doubling condition seems to capture all of the “size” requirements is needed in order to admit a bilipschitz embedding into some Rm, and Assouad’s theorem helps to make that precise. (One could formulate Assouad’s theorem slightly differently, and say that (M,d(x, y)) is doubling if and only if (M,d(x, y)s) admits a bilipschitz embedding into some Rm, where 0 <s<1.) However, the doubling condition is not sufficient for the existence of a bilipschitz embedding. A basic family of examples, which was known to Assouad, is given by the Heisenberg groups with their natural (invariant) Carnot metrics. Like Euclidean spaces, the Heisenberg groups with their Carnot metrics admit transitive groups of isometries (given by left translations) and also one-parameter families of “dilations”, which have the effect of rescaling the metric. It turns out that Lipschitz mappings from Heisenberg groups into Euclidean spaces (or other Carnot groups) are “differentiable almost everywhere” in a suitable sense.
Bilipschitz embeddings of metric spaces 573 See [Pa]. This is analogous to more classical results for Lipschitz mappings on Euclidean spaces [Fe], [St1], and it permits one to show that bilipschitz mappings from the Heisenberg groups into Euclidean spaces do not exist. More precisely, if one did have a bilipschitz mapping from a Heisenberg group into a Euclidean space, then the differentials of the mapping (which exist almost everywhere) would be bilipschitz as well. However, the differentials are given almost everywhere by group homomorphisms, and this leads to a contradiction, because homomorphisms from Heisenberg groups into Euclidean spaces have to have nontrivial kernel, since the latter are commutative (as additive groups) while the former are not. The Heisenberg groups are also doubling, as one can see most easily by using the translation and dilation symmetries (to reduce the doubling property to the case of a single ball). See [Se2] for further discussion of this family of examples. These examples seem to indicate that the existence of a bilipschitz embedding into some Rmis a rather delicate issue, and indeed no clear way exists at present to decide when a metric space which is doubling admits such an embedding. The result of Assouad provides a pretty good substitute, but the “snowflake transform” which replaces (M,d(x, y)) with (M,d(x, y)s), 0 <s<1, distorts the geometry of Mtoo severely for some purposes. It changes the Hausdorff dimension, for instance, and one can check that (M,d(x, y)s) can never contain nonconstant rectifiable curves when s<1 and (M,d(x, y)) is a metric space. In analysis it is often natural to have not just a metric but also a measure. Given a metric space (M,d(x, y)), a nonnegative Borel measure µon Mis said to be doubling if there is a constant Csuch that (1.4) µ(2B)≤Cµ(B) for all balls Bin M, where 2Bdenotes the ball with the same center as Band twice the radius. (For the record, when we refer to a “ball” in M, we shall mean an open ball by default, although closed balls would work just as well in practice.) The existence of a (nonzero) doubling measure on Mimplies that (M,d(x, y)) is doubling as a metric space, as is well-known and not hard to show. If µis doubling with respect to d(x, y), then it is also doubling with respect to d(x, y)sfor any s, and this is easy to verify too. Let us make the convention that “doubling measures” are always not identically zero. The doubling condition then implies that a doubling measure has a positive value on any nonempty open ball in the metric space.
574 S. Semmes Much of standard “order 0” harmonic analysis makes sense as soon as one has a metric space (or quasi-metric space) and a doubling measure. Of course Lpspaces make sense as soon as one has a measure, but with the extra structure of a metric and the doubling condition for µone can make sense of Calder´on-Zygmund operators, maximal operators, H1, BMO, Apweights, etc., and with much the same results as usual. See [CW1], [CW2], [CM], [J], for instance. For this type of analysis the passage from d(x, y)tod(x, y)smakes no real difference, and Assouad’s theorem implies that one might as well think of working with subsets of Euclidean spaces rather than abstract metric spaces. For analysis roughly like that of H¨older continuous functions on Rn of some order αstrictly between 0 and 1, the “snowflake transform” d(x, y)→ d(x, y)sis not so important either, except that the H¨older exponent αchanges with s. However, for analysis which sees integer orders of smoothness, like Lipschitz functions or Sobolev spaces W1,p, something like the snowflake transform is much more serious. Integer orders of smoothness on Euclidean spaces behave very differently from non-integer orders, and this reflects something quite substantial about the geometry of Euclidean spaces. Roughly speaking, H¨older conditions like (1.5) |g(x)−g(y)|≤C|x−y|α for real-valued functions gon Rnare much “flabbier” when 0 <α<1 than for the α= 1 case of Lipschitz functions. This is reflected in the differentiability almost everywhere of Lipschitz functions on Euclidean spaces, for instance. (See also [Se3] for more discussion of this theme.) In this paper, our sympathies lie largely with contexts in which integer orders of smoothness, rectifiability of curves and surfaces, differentiability of functions, and so forth, are of concern. We would like to be able to put a metric space into some Rm, and with only relatively modest distortions in geometry that do not cause too much trouble for considerations like these. We shall not really be able to do this outright, but we shall give a way to combine pieces of information at different scales and locations into a single and more coherent picture. 2. Definitions and the main result Fix a metric space (M,d(x, y)), and a doubling (Borel) measure µon M. This data will be used throughout this section. Note that the combination of (M,d(x, y)) and µis sometimes called a “space of homogeneous type”, as in [CW2].
Bilipschitz embeddings of metric spaces 575 Definition 2.1 (The BPE condition). We say that (M,d(x, y),µ) satisfies the BPE condition (BPE for “big pieces of Euclidean spaces”) if there exist positive constants m,k, and θ, with man integer, so that for each ball Bin Mthere is measurable set E⊆Band a mapping h: E→Rmwith the properties (2.2) µ(E)≥θµ(B) and (2.3) k−1d(x, y)≤|h(x)−h(y)|≤kd(x, y) for all x, y ∈E (i.e., his k-bilipschitz on E). With the BPE condition we bring aspects of measure into the problem of bilipschitz embeddings. Note that there are examples of spaces which satisfy the BPE condition but do not admit bilipschitz embeddings into any finite-dimensional Euclidean space. We shall say more about this in Section 4. The following is a basic concept from harmonic analysis. (General references include [Ga], [J], [St2].) Definition 2.4 (A1weights). Let w(x) be a measurable real-valued function on Mwhich is positive µ-almost everywhere. Then w(x)isan A1weight if there is a constant Cso that (2.5) 1 µ(B)B w(x)dµ(x)≤Cessinf Bw for all balls Bin M. Here “essinf” means the essential infimum, which is defined (as usual) by taking the largest possible value of the infimum that occurs when a set of measure 0 is removed from the set over which the essential infimum is being taken. (In other words, the essential infimum is not effected by small values of the function which are attained only on sets of measure 0.) Of course (2.6) essinf Bw≤1 µ(B)B w(x)dµ(x) automatically, and one can reformulate the A1condition as saying that the essential infimum of wover any ball is always comparable in size to the average of wover the same ball.
576 S. Semmes Observe that (2.7) w(x)dµ(x) is a doubling measure on Mwhen w(x)isanA1weight. This is not hard to see, and there is a stronger “approximate monotonicity” property that holds too. Namely, if B1and B2are balls which satisfy B1⊇B2, then (2.8) essinf B2 w≥essinf B1 w automatically, and the A1condition yields (2.9) 1 µ(B2)B2 w(x)dµ(x)≥C−11 µ(B1)B1 w(x)dµ(x), using also (2.6). This is much stronger than the doubling condition, because (2.9) applies no matter how small B2is compared to B1(i.e., with a uniform constant). To illustrate the notion of an A1weight, let us consider functions of the form |x|αon the real line. For this we use the standard metric and Lebesgue measure on R, as our choice of background metric and measure. These functions are A1weights when −1<α≤0, as one can check through straightforward computation. The A1property fails when α>0, because of the vanishing at the origin, and also when α≤−1, since |x|αis not even locally integrable at the origin in that case. Similarly, on Rn,|x|αis an A1weight exactly when −n<α≤0. If x1denotes the first coordinate of a point x∈Rn, then |x1|αis an A1 weight on Rnif and only if −1<α≤0, and for practically the same reasons as when n=1. Notice that if w(x) is just a positive constant, then wis an A1weight with constant equal to 1 in (2.5). More generally, if w(x)isanyA1 weight, and cis a positive constant, then cw(x)isanA1weight, and with the same A1-constant as w(x). Thus, one should never take individual values of an A1weight too seriously, since constant multiplicative factors behave like free parameters. Conversely, if w(x)isanA1weight with constant equal to 1 in (2.5), then w(x) must be equal to a fixed constant µ-almost everywhere on M. This is not hard to check, since one would have equality in (2.6).
Bilipschitz embeddings of metric spaces 577 If w(x)isanA1weight, then w(x) is locally bounded away from 0, by (2.5). However, it is possible for A1weights to tend to zero (at modest rates) at infinity, as in the preceding examples. The sets (of measure 0) on which an A1weight blows up can be practically arbitrary (as shown by a construction in [CR] —see also [J], [St2]), but the nature of the blowing up is regulated rather strongly by (2.5). In particular, one has approximate monotonicity as one shrinks down to specific locations, as in (2.9). We shall use A1weights to make suitable deformations of metrics for bilipschitz embeddings into Euclidean spaces, as in the next assertion (which is the main result of this paper). Proposition 2.10. Let (M,d(x, y)) be a metric space, and let µbe a doubling measure on M.If(M,d(x, y),µ)satisfies the BPE condition, then there is an A1weight w(v)on Mwith the following property. Given δ∈(0,1], define Dδ(x, y)for x, y ∈Mby (2.11) Dδ(x, y)=d(x, y)·inf 1 µ(B)B w(v)δdµ(v):Bis a ball in Mwhich contains xand yand satisfies diam B<3d(x, y). (If x=y, set Dδ(x, y)=0.) Then for each δ∈(0,1] there is an integer and a mapping f:M→Rsuch that (2.12) C−1Dδ(x, y)≤|f(x)−f(y)|≤CD δ(x, y) for some constant Cand all x, y ∈M. In other words, the deformation (M,Dδ(x, y)) of (M,d(x, y)) admits a bilipschitz embedding into R. These constants Cand may be chosen so that they depend only on δ, the doubling constant for µ, and the constants associated to the BPE condition for (M,d(x, y),µ)from Definition 2.1. One can think of (2.11) as saying that Dδ(x, y) is obtained by changing d(x, y) at a given location and scale by an amount which is the average of w(v)δat the same approximate location and scale. (See also Remark 2.13 below.) This type of deformation is pretty mild, at least when δis small, or the weight w(v) is sufficiently moderate. We shall discuss this further in Section 3. When δis not small, pathologies can occur for general weights. This will also be discussed in Section 3. This is not really a problem in the context of Proposition 2.10, though.
578 S. Semmes As we mentioned towards the end of Section 1, Proposition 2.10 is not really about producing bilipschitz embeddings directly, without any such knowledge in advance. Instead it provides a method for converting many separate pieces of partial information into something global. This can be quite convenient, e.g., for aspects of Mwhich involve topology. A particular context in which Proposition 2.10 applies is that of “uniformly rectifiable” metric spaces (to which we shall return in Section 4). For these Proposition 2.10 shows that the setting of abstract metric spaces is not too different from that of subsets of Euclidean spaces. In particular, most of the existing literature about uniform rectifiability is formulated for subsets of Euclidean spaces, and Proposition 2.10 provides a way to reduce to that case. Similarly, if one is interested in working with differential forms, currents, and exterior differentiation on a uniformly rectifiable metric space, then one avenue would be to use Proposition 2.10 to reduce to the existing theory for subsets of Euclidean spaces (as in [Fe]). Note that the BPE condition for (M,d(x, y),µ) can be recovered from the embedding of (M,Dδ(x, y)) provided by Proposition 2.10 (and for any choice of δ>0), as we shall see in Section 3 (just after Lemma 3.40). In harmonic analysis, one is accustomed to the idea of a weight as giving a deformation of the background measure, and to weighted-norm inequalities as saying that such deformations do not change basic properties of interest too much. See [Ga], [J], [St2], for instance. The present use of weights is similar in spirit. (See also [DS1], [Se3], and Section 3 below.) The proof of Proposition 2.10 will be given in Section 6. In Sections 4 and 5 we shall discuss the embeddings in Proposition 2.10 in a couple of slightly more specialized situations. Remark 2.13 (The infimum in (2.11)). Notice that there always exist balls Bwhich satisfy the conditions in (2.11), i.e., which contain x and yand have diameter <3d(x, y). One can take B(x, 4 3d(x, y)) and B(y, 4 3d(x, y)), for instance. (The factors 4 3are included because “balls” are open, by default. If closed balls are used, this extra factor can be dropped, but this is not a serious matter in any event.) If B1and B2 are any two balls which contain xand yand have diameter <3d(x, y), then the averages (2.14) 1 µ(Bi)Bi w(v)δdµ(v),i=1,2 are approximately the same, in the sense that the average over B1 is bounded by a constant multiple of the average over B2, and viceversa. This is an easy consequence of the doubling properties for µand
Bilipschitz embeddings of metric spaces 579 w(v)δdµ(v). The same would be true for any roughly similar class of balls B(living near x,yand having size around d(x, y)), for the same reason of the doubling conditions. 3. On the behavior of Dδ(x, y) Throughout this section, we assume that M,d(x, y), µ,δ, and Dδ(x, y) are as in Proposition 2.10 (except for the BPE hypothesis). We want to look at the behavior of Dδ(x, y) in comparison with d(x, y) in some detail. This will not be used in the proof of Proposition 2.10, but it helps to make clear what the proposition really means. More precisely, in this section we shall look at the behavior of Dδ(x, y) when w(v)isany A1weight, or is more general than that, rather than the special case of weights produced as in Proposition 2.10. In particular, we shall be interested in the behavior of Dδ(x, y) when δis small. For applying Proposition 2.10, note that one is free to take δ to be as small as one wants. The material in this section is fairly standard in some circles (and not in others), and we include it largely for the sake of clarity and completeness. We begin with the following observation. Lemma 3.1. Suppose that w(v)is an A1weight on M, with constant Cwin (2.5), and let δ∈(0,1] be given. Then w(v)δis an A1 weight with constant Cδ w, and (3.2) C−δ w1 µ(B)B w(v)dµ(v)δ ≤1 µ(B)B w(v)δdµ(v) ≤1 µ(B)B w(v)dµ(v)δ for all balls Bin M. Thus, if we set (3.3) D δ(x, y)=d(x, y)·inf 1 µ(B)B w(v)dµ(v)δ :Bis a ball in Mwhich contains xand yand satisfies diam B<3d(x, y)
586 S. Semmes Indeed, if f:M→Ris as in Proposition 2.10, then one can take (3.23) ρδ(x, y)=|f(x)−f(y)|, and this will have the required features. (Note that fdepends on δ.) Specifically, (3.22) is the same as (2.12) in this case, while the triangle inequality for ρδ(x, y) follows easily from its particular form (and from the triangle inequality for the Euclidean metric on R). The existence of a metric ρδ(x, y) satisfying (3.22) is actually much easier than the existence of an embedding f:M→Ras in Proposition 2.10, and it happens more generally. To analyze this further, let us define a candidate for ρδ(x, y)by (3.24) ρδ(x, y) = inf k i=1 Dδ(zi,z i−1), where the infimum is taken over all finite chains z0,z 1,... ,z kof points in Mwhich begin at xand end at y(z0=x,zk=y). This is a kind of universal construction, which makes sense independently of the particular form for Dδ(x, y) that we have here. It is easy to see that ρδ(x, y), defined in this manner, is nonnegative and symmetric, using the corresponding properties for Dδ(x, y). The triangle inequality also holds automatically for ρδ(x, y), as one can check using the fact that any chain from xto ycan be combined with any chain from yto wto give a chain from xto w. Furthermore, (3.25) ρδ(x, y)≤Dδ(x, y) for all x, y ∈M, as one can see by using the one-step chain z0=x,z1=yin (3.24). The first inequality in (3.22) does not follow automatically, even if one knows that Dδ(x, y) is a quasimetric. The particular form of Dδ(x, y) does not especially help here either, nor is a doubling condition for w(v)δdµ(v) (or for w(v)dµ(v)) sufficient. As a basic counterexample, imagine that Mis R2, with the Euclidean metric, and that w(v)=|v1|β, where v1denotes the first component of v∈R2, and βis any positive number. Then w(v)δdv is a doubling measure on R2for any δ>0 (and indeed w(v)δis always an “A∞weight”), but one can check that ρδ(x, y) as defined in (3.24) actually vanishes for all pairs of points x, y ∈R2 whose first coordinates are 0. (A variant of this will be discussed in Section 5.)
Bilipschitz embeddings of metric spaces 587 For that matter, there is no metric ρδ(x, y)onR2which will satisfy (3.22) in this case, and not just the candidate in (3.24). It is not hard to verify that if there is ever a metric ρδ(x, y) that satisfies (3.22), then the construction in (3.24) will work as well. This works in general, without regard to the specific form of Dδ(x, y) that we have here. However, if w(v) is actually an A1weight on M, then we are in much better shape. The A1condition prevents any kind of local vanishing of w(v), as occurs in the examples on R2mentioned above. More precisely, if w(v)isanA1weight on M, and if δ>0 is small enough (as in Lemma 3.8), then the first inequality in (3.22) will hold (for some constant C), and with ρδ(x, y) defined as in (3.24). This is very similar to an observation in [Se1] (Example (a) in Section 4 in [Se1]). In more concrete terms, one wants to show that there is a constant Cso that (3.26) Dδ(x, y)≤C k i=1 Dδ(zi,z i−1) for any pair of points x, y ∈Mand any chain z0,z 1,... ,z kof points in Mwhich begins at xand ends at y. To see this, it is helpful to consider the following two cases separately. First, if each point ziin the chain z0,z 1,... ,z klies in the ball B(x, 10 d(x, y)), say, then (3.26) is not hard to derive from the definition of Dδ(x, y), using the triangle inequality for d(·,·) and the A1property for w(v). For this it is helpful to employ Lemma 3.29 below, which puts the A1condition for w(v)in a more convenient form (at the level of Dδ(·,·), from which the triangle inequality for d(·,·) is easier to apply). Second, if the zi’s do not all lie in B(x, 10 d(x, y)), then one can reduce to this case by looking at the first of the zi’s which does not lie in B(x, 10 d(x, y)). This is similar to Lemma 3.3 in [Se1], and is not difficult to manage anyway. It is for this case that we need the assumption that δbe small, in order to apply Lemma 3.8. Specifically, we need to know that Dδ(x, z)≥C−1Dδ(x, y) when z/∈B(x, 10 d(x, y)). In applying Lemma 3.8 here, we are switching the roles of yand z, and also replacing D δ(x, y) with Dδ(x, y). The latter is allowed because of (3.4), and since we are assuming that w(v)isan A1weight. Now let us look more at comparisons between Dδ(x, y) and d(x, y). We begin with a “quasisymmetry” condition. If w(v)isanA1weight on M, and δ>0 is small enough, then there is a function η:[0,∞)→[0,∞) such that limt→0η(t) = 0 and (3.27) Dδ(x, z)≤η(t)Dδ(x, y) whenever d(x, z)≤td(x, y),
588 S. Semmes for all x, y, z ∈Mand t>0. In other words, this says that the identity mapping on Mis quasisymmetric as a map from (M,d(x, y)) to (M,Dδ(x, y)) (in the sense of [TV]). This property implies that relative distances are approximately the same for d(x, y) and Dδ(x, y). This is true uniformly in δ, i.e., with a single choice of η, but one can make “better” choices of ηas δgets smaller. We shall say more about this in a moment. One can also describe (3.27) as saying that d(x, y) and Dδ(x, y) determine roughly the same class of “balls” in M, even if they might assign very different diameters to sets in M. To establish the quasisymmetry property (3.27), it is helpful to first use Lemma 3.1 to reduce to the analogous assertion for D δ(x, y) instead of Dδ(x, y). Once this reduction is made, the A1property for w(v)is not needed, but only the doubling conditions for µand w(v)dµ(v). The quasisymmetry condition then holds for all small δwith a single choice of η(t) of the form Cmax(t1/2,t 2), for instance. For t≤1, this is essentially the same as Lemma 3.19. When t≥1, one may as well restrict one’s attention to x, y, z ∈Mwhich satisfy (3.28) d(x, y)≤d(x, z)≤td(x, y) (rather than just the second inequality). This is because of the t= 1 case already established. Under the condition (3.28), it is not hard to show that D δ(x, z)≤CtaD δ(x, y) for suitable constants Cand a, and with C and aclose to 1 when δis small. This is analogous to the computations made in the proof of Lemma 3.8, but with some minor changes. (In particular, the roles of expressions like Bw(v)dµ(v) and µ(B) are now the opposite of what they were before.) As δtends to 0, the quasisymmetry conditions for D δ(·,·) and Dδ(·,·) improve, and one can choose η:[0,∞)→[0,∞) so that it becomes uniformly close to the identity on bounded subsets of [0,∞). This is not hard to show, using the same kinds of computations as above. One can also choose η(t) so that its growth at infinity and decay near 0 are only slightly worse than linear (in terms of powers of t). These quasisymmetry properties provide fairly good senses in which the Dδ(x, y)’s represent only mild deformations of the geometry of d(x, y), especially as δ→0. One can do better than this, however. We begin with the following lower bounds.
Bilipschitz embeddings of metric spaces 589 Lemma 3.29. Fix points x, y ∈Mand δ∈(0,1], and put (3.30) τδ(x, y)=Dδ(x, y) d(x, y). Let z,u ∈Mbe points such that z,u ∈B(x, 10 d(x, y)) (where the ball B(x, 10 d(x, y)) is defined in terms of d(·,·), as usual). If w(v)is an A1weight on M, then (3.31) Dδ(z,u)≥(1 + Cδ)−1τδ(x, y)d(z,u), where Cdepends only on the A1constant for wand the doubling constant for µ(and not on the specific choices of x,y,z,oruin particular). This is a kind of “A1property” at the level of distance functions, rather than measures. Roughly speaking, it says that Dδ(z,u) is always approximately “larger” than d(z,u), except that we allow for a scale factor τ(x, y) (which does not depend on zor u). Of course the choice of the constant 10 in B(x, 10 d(x, y)) does not matter, and could be replaced by any other number, with larger choices leading to larger values of C in (3.31). To prove Lemma 3.29, it is enough to show (3.32) D δ(z,u)≥(1 + Cδ)−1τ δ(x, y)d(z,u) in place of (3.31), where Cis a constant, and τ δ(x, y) is defined in the same way as (3.30), but with Dδ(·,·) replaced by D δ(·,·). This follows from (3.4), which ensures that the substitution of D δ(·,·) for Dδ(·,·) leads at worst to additional factors of the form Cδ w. Note that Cδ wis bounded by the sum of 1 and a constant multiple of δwhen δlies in (0,1]. Next, we only need to worry about δ= 1 in order to prove the lemma. This is because (3.33) D δ(ξ,η) d(ξ,η)=D 1(ξ,η) d(ξ,η)δ for all ξ,η ∈M, by the definition of D δ(·,·) in (3.3). In other words, the fact that we can get (1 + Cδ)−1on the right side of (3.31), instead of a constant without such good control on the dependence on δ, follows directly from a bound for δ= 1 with any reasonable constant and the presence of the exponent δon the right side of (3.33).
590 S. Semmes Thus it suffices to show that (3.34) D1(z,u)≥C−1τ1(x, y)d(z,u) under the conditions of the lemma. We have gone back to D1and τ1here, instead of D 1and τ 1, because D 1(z,u)=D1(z,u) and τ 1(x, y)=τ1(x, y), by definitions. (See (2.11) and (3.3).) Fix x,y,z, and uas in the statement of Lemma 3.29. Set (3.35) I(x, y) = inf 1 µ(B)B w(q)dµ(q):Bx, y and diam B<3d(x, y). More precisely, the infimum is taken over B’s which are balls in M(with respect to d(·,·)). Define I(z,u) in the same manner, but with zand u instead of xand y. The desired estimate (3.34) is then the same as (3.36) I(z,u)≥C−1I(x, y), as one can see by unwinding the definitions (of D1(·,·) and τ1(x, y)). To prove (3.36), let Bbe a ball in Mwhich contains zand uand has diameter <3d(z,u). By assumption, z,u ∈B(x, 10 d(x, y)), and so d(z,u)≤20 d(x, y) and diam B<60 d(x, y). This implies in turn that (3.37) B⊆B(x, 70 d(x, y)), since zand ulie in both Band B(x, 10 d(x, y)). Using (3.37) and the A1property for w(v) we obtain that (3.38) 1 µ(B)B w(v)dµ(v) ≥C−11 µ(B(x, 70 d(x, y))) B(x,70 d(x,y)) w(v)dµ(v), as in (2.9). By taking the infimum over Bwe get that (3.39) I(z,u)≥C−11 µ(B(x, 70 d(x, y))) B(x,70 d(x,y)) w(v)dµ(v), by the definition of I(z,u). From here it is easy to derive (3.36) (with a modestly different constant C), using the doubling condition for µ. This completes the proof of Lemma 3.29. The next lemma records estimates in the direction opposite to that of Lemma 3.29, i.e., with upper bounds for Dδ(z,u) instead of lower bounds. We no longer have uniform control, but only for “most” points, in the sense of µ-measure.
Bilipschitz embeddings of metric spaces 591 Lemma 3.40. Assume that w(v)is an A1weight on M. Fix x, y ∈ Mand δ∈(0,1], and define τδ(x, y)as before, in (3.30). For each λ>0, there is a (relatively closed and hence measurable) subset Fλ of B(x, 10 d(x, y)) with the properties described below. (Here the ball B(x, 10 d(x, y)) is defined in terms of d(·,·), as usual. Also, Fλdoes not depend on δ.) Let z,u ∈Mbe points such that z,u ∈B(x, 10 d(x, y)) and at least one of zand ulies in Fλ. Then (3.41) Dδ(z,u)≤(Cλ)δτδ(x, y)d(z,u). Also, Fλis a subset of B(x, 10 d(x, y)) of substantial size, in the sense that (3.42) µ(B(x, 10 d(x, y))\Fλ)≤Cλ −1µ(B(x, 10 d(x, y))). Here Cdepends only on the A1constant for wand the doubling constant for µ(and not on the specific choices of x,y,z,oruin particular). Before we explain why this is true, let us say a few things about what it means. If we take λ=2C, with Cas in Lemma 3.40, then (3.42) implies that Fλcontains at least half of the elements of B(x, 10 d(x, y)), as measured by µ, and then (3.41) reduces to (3.43) Dδ(z,u)≤(2C2)δτδ(x, y)d(z,u). This together with Lemma 3.29 shows that Dδ(z,u) is bounded from above and below by (bounded) constant multiples of τδ(x, y)d(z,u) when zand urange among at least half of the points in B(x, 10 d(x, y)). In particular, this shows that the existence of the embedding f:M→Ras in the conclusions of Proposition 2.10 implies that (M,d(·,·),µ) satisfies the BPE condition (Definition 2.1). In other words, the passage from the BPE condition to the conclusions of Proposition 2.10 does not lead to loss of information (modulo worse constants and embedding dimensions). Notice also that Lemma 3.40 very much does not work (in general) if instead of Dδ(·,·) we used deformations of d(·,·) of the form d(·,·)1−δ,as in Theorem 1.3. Everything else in this section so far —like Lemma 3.29 and the quasisymmetry properties of the deformations of d(·,·)— would work just as well for these “snowflake” deformations d(·,·)1−δ. With Lemma 3.40 we make use of the measure theory in a significant way.
592 S. Semmes Remark 3.44. Lemma 3.40 would work just as well if w(v) were an “A∞weight” (see [Ga], [J], [St2]) instead of an A1weight. Lemma 3.29 does not work for A∞weights in general, but one can repair this by taking measure theory into account in the same manner as for Lemma 3.40, i.e., only asking for lower bounds when one of zor ulies in a set Fλ⊆ B(x, 10 d(x, y)) of large size (in the sense of (3.42)). In this case, the lower bounds would depend on λind the same manner as for the upper bounds in (3.41). Note that for A∞weights, one does not in general have the approximation of Dδ(x, y) by actual metrics, as in (3.22). We shall return to this point in Section 5. Let us now prove Lemma 3.40. We begin by using exactly the same reductions as in the proof of Lemma 3.29. That is, one can replace Dδ(·,·) with D δ(·,·) throughout, because of (3.4), and then we may reduce to the case where δ= 1, because the powers of δcan be washed out, as in (3.33). In the end, it suffices to find Fλ⊆B(x, 10 d(x, y)) so that (3.42) holds, and so that (3.45) D1(z,u)≤Cλτ1(x, y)d(z,u) when z,u ∈B(x, 10 d(x, y)) and at least one of zor ulies in Fλ.Asin (3.36), we can reformulate (3.45) as (3.46) I(z,u)≤CλI(x, y), where I(·,·) is defined in (3.35). This follows from the definitions of D1(·,·) and τ1(x, y). Before we choose Fλ, let us record the following fact. Let zand wbe arbitrary points in B(x, 10 d(x, y)), and let Bbe a ball which contains zand wand has diameter which is <3d(z,u). For instance, Bmight simply be B(z, 4 3d(z,u)). Just as in (3.37), we have that (3.47) B⊆B(x, 70 d(x, y)). Let fbe the function which is equal to won B(x, 70 d(x, y)) and which vanishes on the complement of B(x, 70 d(x, y)). Thus (3.48) M f(p)dµ(p)=B(x,70 d(x,y)) w(p)dµ(p) ≤CI(x, y)µ(B(x, 10 d(x, y))).
Bilipschitz embeddings of metric spaces 593 The second step follows from the definition of I(x, y) in (3.35) and the doubling conditions for µand wdµ. In particular, this constant Cdepends only on the doubling constants for µand wdµ. Let f∗denote the (uncentered) Hardy-Littlewood maximal function of f, given by (3.49) f∗(p) = sup Bp 1 µ(B)B f(q)dµ(q), where the supremum is taken over all balls Bin Mthat contain p. Put (3.50) Eλ={p∈M:f∗(p)>λI(x, y)}. It is not hard to check that Eλis an open subset of M, since the balls B in (3.49) are open (by our standing convention that “ball” means “open ball”, by default). We also have that (3.51) µ(Eλ)≤C(λI(x, y))−1M f(p)dµ(p), where Cdepends only on the doubling constant for µ. This is the usual “weak-type (1,1) inequality” for the maximal function, extended to the case of general doubling measures as in [CW1], [CW2], and proved through a Vitali-type covering lemma. Combining this with (3.48), we obtain that (3.52) µ(Eλ)≤Cλ −1µ(B(x, 10 d(x, y))), but with a modestly larger choice of C. Now set Fλ=B(x, 10 d(x, y))\Eλ.ThusFλis a relatively closed subset of B(x, 10 d(x, y)), since Eλis an open set, and (3.42) follows immediately from (3.52). Let z,u ∈B(x, 10 d(x, y)) be given, with one of z,ulying in Fλ.It remains to verify (3.46). For the sake of definiteness, let us assume that z∈Fλ, the other case being equivalent to this one. Fix any ball Bin M such that Bcontains zand uand diam B<3d(z,u). Thus (3.53) I(z,u)≤1 µ(B)B w(q)dµ(q) by the definition (3.35) of I(·,·). We can rewrite this as (3.54) I(z,u)≤1 µ(B)B f(q)dµ(q),
594 S. Semmes because of (3.47) and the definition of f. On the other hand, (3.55) 1 µ(B)B f(q)dµ(q)≤f∗(z) by the definition (3.49) of f∗and the fact that Bcontains z. Our assumption that z∈Fλyields (3.56) f∗(z)≤λI(x, y), and thus we conclude that (3.57) I(z,u)≤λI(x, y). This shows that (3.46) holds (with C= 1), and the proof of Lemma 3.40 is now complete. To recapitulate once more, from Lemmas 3.29 and 3.40 we have that Dδ(·,·) and d(·,·) are practically the same in any given ball in M, modulo bounded distortions, “bad” sets of small measure (as in (3.42)), and a positive scale factor. 4. Variations on the theme In this section, we shall restrict our attention to metric spaces that are “Ahlfors regular”, in the sense of the next definition. For the record, B(x, t) denotes the closed ball with center xand radius t, in a given metric space. Definition 4.1. A metric space (M,d(x, y)) is said to be Ahlfors regular of dimension s(where sis some positive number) if it is complete, and if there is a Borel measure µon Msuch that (4.2) C−1ts≤µ(B(x, t)) ≤Ct s for some constant C>0 and all x∈M,0<t≤diam M. One sometimes also refers to the measure µas being Ahlfors-regular of dimension s. Note that µis automatically doubling in this case, with a constant that depends only on the dimension sand the constant Cin (4.2).
Bilipschitz embeddings of metric spaces 595 If (M,d(x, y)) is Ahlfors-regular of dimension s, then (4.2) necessarily holds with µreplaced by s-dimensional Hausdorff measure Hs, and in fact µand Hsare each bounded by a constant multiple of the other. This is not too hard to prove, but we shall not really need it here anyway. Let us make the standing assumption for the time being that (M,d(x, y)) is Ahlfors-regular of dimension s, and that µis as in Definition 4.1. In this case we have that (4.3) d(x, y)≈(µ(B(x, d(x, y))))1 s≈(µ(B(y,d(x, y))))1 s, where we write A1≈A2to mean that A1and A2are bounded from above and below by constant multiples of each other. This is an immediate consequence of (4.2). If µwere merely doubling (i.e., without Ahlfors regularity), then expressions like (µ(B(x, d(x, y))))1 sprovide quasisymmetrically-equivalent ways to measure distance in Mcompared to the original distance d(x, y). (This assertion uses the assumption that (M,d(x, y)) be Ahlfors regular in a mild way, to know that Mis “uniformly perfect”. This last means that for any point x∈Mand any radius r≤diam Mthere is a point y∈Mwith d(x, y)≈r.) With Ahlforsregularity the two measurements of distance are almost the same, as in (4.3). Let w(v)beanA1weight on M(with respect to d(·,·) and µ), and let Dδ(x, y) be as defined in (2.11). The assumption of Ahlfors-regularity gives us another way to look at Dδ(x, y), as follows. Lemma 4.4. Let w(v)be an A1weight on M, as above, and suppose that δ,s>0satisfy δ,δ·s≤1. Define Dδ(x, y)by (4.5) Dδ(x, y) = inf B w(v)δsdµ(v)1 s :Bis a ball in Mwhich contains xand yand satisfies diam B<3d(x, y). Then (4.6) C−1Dδ(x, y)≤ Dδ(x, y)≤CD δ(x, y) for some constant Cand all x, y ∈M.
602 S. Semmes Let us fix constants m,k, and θas in Definition 2.1. Thus, inside of each ball Bin Mthere is a measurable subset E⊆Band a mapping g: E→Rmsuch that µ(E)≥θµ(B) and gis bilipschitz with constant k. These assertions will be in force throughout the present section, and the various constants which come up below will (mostly) depend only on these parameters and the doubling constant for µ. Remember that the existence of the doubling measure µon Mimplies that Mis doubling as a metric space (i.e., every ball in Mcan be covered by a bounded number of balls of half the radius). This was mentioned in Section 1. Also, the doubling constant for Mas a metric space is controlled by the doubling constant for µas a measure, as an easy consequence of the argument. To prove Proposition 2.10, we want to combine local mappings from the BPE condition into larger ones. Let us recall the following simple fact, concerning extensions of Lipschitz functions. Proposition 6.2. Let Abe a (nonempty) subset of M, and suppose that f:A→Ris Lipschitz with constant L. Then there exists an extension of fto a real-valued function F:M→Rwhich is also Lipschitz with constant L. This is well-known, and one of the standard proofs is to take (6.3) F(x) = inf{f(y)+Ld(x, y):y∈A}. It is not hard to check that this is Lipschitz with constant L(since x→ d(x, u) is Lipschitz with constant 1 for any u∈M) and that it is equal to fon A. (Note that here, for the Lipschitz condition for x→ d(x, u), it is important that d(x, y) be an actual metric —satisfying the ordinary triangle inequality— rather than the weaker quasimetric condition (3.18).) The next proposition gives a substitute for Whitney decompositions for our metric space M. (See [St1] for the usual Whitney decomposition. This type of extension is well known in some quarters, as in [CW1].) Proposition 6.4 (Generalized Whitney decompositions). Let Ωbe a open subset of M, with M\Ω=∅. Then there is a subset Aof Ω with the following properties: (i) if we set Ba=B(a, 10−1dist(a, M\Ω)), then (6.5) Ω = a∈A Ba;
Bilipschitz embeddings of metric spaces 603 (ii) there is a constant C0(depending only on the doubling constant for M) so that for each a∈Athere are at most C0choices of b∈Asuch that 5Bbintersects 5Ba; (iii) if a1,a2are distinct elements of A, then (6.6) 1 3Ba1∩1 3Ba2=∅. Let us indicate how Proposition 6.4 can be proved, both for the sake of completeness, and for the details of its formulation. We begin with the following observation. Suppose that a, b ∈Ω satisfy (6.7) 5Ba∩5Bb=∅. Then (6.8) d(a, b)≤1 2dist(a, M\Ω) + 1 2dist(b, M\Ω), by the definition of Ba,Bb. For any y,z ∈Mwe have that (6.9) dist(y,M\Ω) ≤dist(z,M\Ω) + d(y,z), because of the triangle inequality, and therefore (6.10) dist(b, M\Ω) ≤dist(a, M\Ω) + d(a, b) ≤3 2dist(a, M\Ω) + 1 2dist(b, M\Ω), using (6.8). This reduces to (6.11) dist(b, M\Ω) ≤3 dist(a, M\Ω) (by moving the dist(b, M\Ω) term from the right side of (6.10) to the left, and then simplifying the constant factors). Switching the roles of a and bwe also have that (6.12) dist(a, M\Ω) ≤3 dist(b, M\Ω). In short, dist(a, M\Ω) and dist(b, M\Ω) are nearly the same, by (6.11) and (6.12). Going back to (6.8), we have that (6.13) d(a, b)≤1 2(1 + 3) dist(a, M\Ω) ≤2 dist(a, M\Ω), and similarly with binstead of aon the right-hand side.
604 S. Semmes Imagine now that we have chosen A⊆Ω so that (6.14) d(a1,a 2)≥min i=1,2 1 10 dist(ai,M\Ω) when a1,a 2∈A, a1=a2. Let us verify that part (ii) of Proposition 6.4 holds automatically if (6.14) is true. Fix a∈A, and let Aadenote the set of b∈Asuch that (6.7) holds. Thus we have (6.13) when b∈Aa, by the discussion above. Also, (6.15) d(b1,b 2)≥1 30 dist(a, M\Ω) when b1,b 2∈Aaand b1=b2, because of (6.14) and (6.12). These two conditions imply that the number of elements in Abis bounded by a constant that depends only on the doubling constant for M, as required in (ii) of Proposition 6.4. Specifically, the doubling condition guarantees that (6.16) B(a, 2 dist(a, M\Ω)) can be covered by a bounded number of open balls of radius (6.17) 1 60 dist(a, M\Ω). Each b∈Aalies in (6.16), since it satisfies (6.13), but no two distinct b’s in Aacan lie in the smaller (open) balls of radius (6.17), because of the lower bound in (6.15). This shows that the number of b’s in Aais bounded by the number of balls in our covering of (6.16), which does the job. Now let us check that part (iii) of Proposition 6.4 holds automatically if Asatisfies (6.14). Suppose to the contrary that we have distinct points a1,a 2∈Asuch that (6.18) 1 3Ba1∩1 3Ba2=∅. This implies that (6.19) d(a1,a 2)≤1 30 dist(a1,M\Ω) + 1 30 dist(a2,M\Ω), by the definition of Ba1,Ba2. We may as well assume that (6.20) dist(a1,M\Ω) ≤dist(a2,M\Ω),
Bilipschitz embeddings of metric spaces 605 since we can always reverse the indices to ensure that this is true. Thus (6.21) d(a1,a 2)≥1 10 dist(a1,M\Ω), by (6.14). As in (6.9) we have that (6.22) dist(a2,M\Ω) ≤dist(a1,M\Ω) + d(a1,a 2), and we can put this back into (6.19) to obtain that (6.23) d(a1,a 2)≤2 30 dist(a1,M\Ω) + 1 30d(a1,a 2). This yields (6.24) d(a1,a 2)≤2 29 dist(a1,M\Ω), by moving the d(a1,a 2) term on the right side of (6.23) to the left side, and then simplifying the fractions. However, (6.24) is incompatible with (6.21). This shows that the intersection of balls in (6.18) was impossible, which is exactly what we wanted (to derive part (iii) of Proposition 6.4 from (6.14)). To obtain part (i) of Proposition 6.4, it suffices to choose A⊆Ω so that (6.14) holds and Ais maximal with respect to these properties. More precisely, to say that Ais maximal means that if z∈Ω\A, then A∪{z} does not satisfy (6.14). This says exactly that there is a point a∈Aso that (6.25) d(z,a)≤min 10−1dist(z,M\Ω),10−1dist(a, M\Ω) ≤10−1dist(a, M\Ω) holds. Thus z∈Bafor this choice of a∈A, and we conclude that part (i) of Proposition 6.4 holds when Ais maximal. In order to have an A⊆Ω which satisfies (6.14) and is maximal, one does not need anything too abstract like Zorn’s lemma. Let {Uj}∞ j=1 be a sequence of subsets of Ω such that Ujis bounded, dist(Uj,M\Ω) >0, and Uj⊆Uj+1 for all j, and so that (6.26) Ω = ∞ j=1 Uj.
606 S. Semmes For instance, one can fix p∈Mand take (6.27) Uj={x∈B(p, j) : dist(x, M\Ω) ≥j−1}. If Ais any subset of Ω that satisfies (6.14), then the number of elements of A∩Ujis bounded by a constant that depends on Ujbut not on A, because of the doubling property of M. This is like the argument above, for deriving part (ii) of Proposition 6.4 from (6.14). (That is, no two elements of Uj∩Acan lie in a single ball of sufficiently small radius (depending on dist(Uj,M\Ω)), because of (6.14), amd hence the number of elements in Uj∩Ais controlled by the (finite) number of balls of this radius needed to cover Uj.) Thus one can first choose A1⊆U1so that it satisfies (6.14) and is maximal with respect to these properties (by choosing A1so that it contains as many elements as possible), then add points to get a subset A2of U2which satisfies (6.14) and is maximal, and so on. In the end, the set Awhich is the union of the Aj’s, 1 ≤j<∞, will satisfy (6.14) and be maximal in Ω. Indeed, if Awere not maximal in Ω, so that there is some point w∈Ω\Asuch that A∪{w}satisfies (6.14), then Aj∪{w}also satisfies (6.14) for all j, and this contradicts the maximality of Ajin Ujwhen jis large enough so that w∈Uj(which happens eventually, by (6.26)). This completes the proof of Proposition 6.4 (i.e., a maximal set A⊆Ω which satisfies (6.14) exists, and parts (i), (ii), and (iii) of Proposition 6.4 are true for any Awith these features, as explained above). To prove Proposition 2.10, we shall construct a sequence {Ωj}∞ j=0 of open sets in Msuch that the Ωj’s are decreasing in j, and so that we understand fairly well how to make bilipschitz embeddings into Euclidean spaces on M\Ωj. In other words, we shall operate by “layers”, but where the scales involved in level jvary from place to place in M. (Specifically, the relevant “scales” at level jwill be given essentially by the distance to M\Ωj.) In the end, we shall have to combine all these layers in a slightly careful way, both for constructing an embedding of Minto some Rand for the choice of the A1weight w(x)onM(as in Proposition 2.10). The latter will be chosen so that it increases geometrically on the Ωj’s. We define {Ωj}∞ j=0 recursively as follows. Fix a basepoint p0∈M, and set Ω0=M\{p0}. We assume now that Ωjhas already been chosen for some j≥0, and we want to define Ωj+1. We also assume that Ωj is open, and that M\Ωjis nonempty. We shall choose Ωj+1 so that it is an open subset of Ωj, which will permit the recursion to continue afterwards.
Bilipschitz embeddings of metric spaces 607 Let Aj=A(Ωj) be the subset of Ωjwhich is provided by Proposition 6.4. Given a∈M, put (6.28) Ba,j =B(a, 10−1dist(a, M\Ωj)), as in Proposition 6.4. For each a∈Aj, let Ea,j be a subset of Ba,j such that (6.29) µ(Ea,j)≥θ1µ(Ba,j) and (6.30) there is a k-bilipschitz mapping ga,j :Ea,j →Rm. It will be convenient to require also that (6.31) Ea,j is closed, and Ea,j ⊆1 4Ba,j. The existence of such a set Ea,j follows from the BPE condition, as reviewed at the beginning of the section, except for a couple of minor changes. Namely, the constant θ1in (6.29) should be taken a bit smaller than the original parameter θ(with θ1≥C−1θfor a suitable constant C), to accommodate (6.31) and the fact that Ba,j is a closed ball (while the BPE condition was stated for open balls). Also, to get Ea,j to be closed (as in (6.31)), one can simply take the closure of the (possibly non-closed) set provided by the BPE condition. The bilipschitz embedding ga,j into Rmautomatically extends to the closure, by standard reasoning, and the bilipschitz constant is not changed by this extension. Set (6.32) Ej= a∈Aj Ea,j and (6.33) Ωj+1 =Ω j\Ej. Thus Ωj+1 ⊆Ωjautomatically. Note that the complement of Ωj+1 in Mis given by Ej∪(M\Ωj). If Ωjhappens to be empty, then Aj,Ej, and Ωj+1 are empty too. This is not very interesting, but we do not mind it.
608 S. Semmes Lemma 6.34. Ej∪(M\Ωj)is a closed subset of M(and hence Ωj+1 is open in M). To see this, let {zs}sbe any sequence of points in Ej∪(M\Ωj) which converges to some point z∈M. We want to show that zis contained in Ej∪(M\Ωj). If z∈M\Ωj, then there is nothing to do, and so we assume that z∈Ωj. This means that zlies in Ba,j for some a∈Aj, by part (i) of Proposition 6.4. Because lims→∞ zs=z, we have that zs∈2Ba,j for all but finitely many s’s. In particular, zs∈Ωjfor all but finitely many s’s. Since the zs’s lie in Ej∪(M\Ωj), we have that for all but finitely many s’s there is an b(s)∈Ajsuch that zs∈Eb(s),j. On the other hand, part (ii) of Proposition 6.4 implies that there are only finitely many b’s in Ajsuch that Bb,j intersects 2Ba,j. Because Eb(s),j ⊆Bb(s),j, we conclude that the b(s)’s represent only finitely many distinct elements of Aj.In particular, there is a single b0∈Ajsuch that b(s)=b0for infinitely many s’s. Thus zs∈Eb0,j for infinitely many values of s. This implies that z∈Eb0,j, since each individual Eb,j is closed, by construction, and since lims→∞ zs=z.Thuszlies in Ej, and Lemma 6.34 follows. Remember that the openness of Ωjand nonemptiness of M\Ωjwere the “induction hypotheses” from which we started. Lemma 6.34 shows that Ωj+1 satisfies the same conditions, so that the process may be repeated indefinitely. In the end we get a decreasing sequence {Ωj}∞ j=0 of open subsets of M, together with the auxiliary sets Aj,Ba,j,Ea,j, and Ej. Eventually we shall want to combine the ga,j’s associated to the Ea,j’s to obtain our embedding fof Minto some R(as in Proposition 2.10), but first we want to give some quantitative estimates about the way that the Ωj’s decrease with j. We begin with the following simple observation. Lemma 6.35. If x∈Ba,j, then (6.36) dist(x, M\Ωj)≤11 10 dist(a, M\Ωj) and (6.37) dist(a, M\Ωj)≤10 9dist(x, M\Ωj). Indeed, (6.38) dist(x, M\Ωj)≤dist(a, M\Ωj)+d(x, a), as in (6.9), and so (6.39) dist(x, M\Ωj)≤(1+10 −1) dist(a, M\Ωj),
Bilipschitz embeddings of metric spaces 609 since x∈Ba,j (and Ba,j is as in (6.28)). This proves (6.36). Similarly, (6.40) dist(a, M\Ωj)≤dist(x, M\Ωj)+d(a, x) ≤dist(x, M\Ωj)+10 −1dist(a, M\Ωj), again because x∈Ba,j. It is easy to derive (6.37) from (6.40), by subtracting the last term on the right and simplifying the constant factors. This proves Lemma 6.35. Lemma 6.41. For each j≥0and x∈Mwe have that (6.42) dist(x, M\Ωj+1)≤1 7dist(x, M\Ωj). Thus Ωj+1 is fairly dense in Ωj, at the scale of the largest balls in Ωj. To prove Lemma 6.41, let x∈Ωjbe given, and choose a∈Ajso that x∈Ba,j (as in part (i) of Proposition 6.4). From (6.28), (6.29), and (6.31) we have that (6.43) Ea,j ∩1 4Ba,j =Ea,j ∩Ba, 1 40 dist(a, M\Ωj)=∅ (i.e., the left-hand side has positive µ-measure, and hence is nonempty). Thus there is a point z∈Ea,j such that (6.44) d(x, z)≤d(x, a)+d(a, z) ≤1 10 dist(a, M\Ωj)+ 1 40 dist(a, M\Ωj) =1 8dist(a, M\Ωj). Combining this with (6.37) yields (6.45) d(x, z)≤10 9·8dist(x, M\Ωj)<1 7dist(x, M\Ωj). On the other hand, z∈M\Ωj+1 automatically, by the definition (6.33), (6.32) of Ωj+1. This gives (6.42) when x∈Ωj, and Lemma 6.41 follows (since the case where x∈M\Ωjis trivial). The next observation controls the rate at which the Ωj’s decrease in terms of measure.
610 S. Semmes Lemma 6.46. There is a constant θ2>0such that for every x∈M, r>0, and j≥0we have that (6.47) µ(B(x, r)∩Ωj+1)≤(1 −θ2)µ(B(x, ρ)∩Ωj), where (6.48) ρ=r+2 9sup y∈B(x,r) dist(y,M\Ωj). The estimate (6.47) would be a bit simpler and more standard if ρwere equal to r—so that exponential decay of µ(B(x, r)∩Ωj)injwould follow immediately by iteration— but the small correction to ρin (6.48) will not cause much trouble. Also, the constant θ2in Lemma 6.46 can be taken to be a geometric constant times θ1, where θ1is as in (6.29). To prove Lemma 6.46, let x,r, and jbe given as above. Let Adenote the set of a∈Ajsuch that Ba,j intersects B(x, r). Thus (6.49) B(x, r)∩Ωj⊆ a∈A Ba,j, by part (i) of Proposition 6.4 (with Ω = Ωj). Notice that (6.50) µ a∈A Ba,j∩Ej≥C−1 a∈A µ(Ba,j ∩Ej), because of the bounded overlap property of the Ba,j’s provided by part (ii) of Proposition 6.4. On the other hand, (6.51) Ba,j ∩Ej⊇Ea,j, since Ea,j ⊆Ba,j by construction (as mentioned just after (6.28)), and since Ejis the union of the Ea,j’s, a∈Aj, by definition. (See (6.32).) This permits us to rewrite (6.50) as (6.52) µ a∈A Ba,j∩Ej≥C−1 a∈A µ(Ej,a). Combining this with (6.29) we obtain that (6.53) µ a∈A Ba,j∩Ej≥C−1 a∈A θ1µ(Ba,j) ≥C−1θ1µ a∈A Ba,j.
Bilipschitz embeddings of metric spaces 611 Next we observe that (6.54) a∈A Ba,j∩Ej= a∈A Ba,j\Ωj+1. This follows from the definition (6.33) of Ωj+1 and the fact that the Ba,j’s, a∈Aj, are contained in Ωj, by construction. (Remember also that A⊆Aj.) Thus (6.53) becomes (6.55) µ a∈A Ba,j\Ωj+1≥C−1θ1µ a∈A Ba,j, and this yields (6.56) µ a∈A Ba,j∩Ωj+1≤1−C−1θ1µ a∈A Ba,j. From (6.49) and (6.56) we obtain that (6.57) µ(B(x, r)∩Ωj+1)≤1−C−1θ1µ a∈A Ba,j. To finish the proof of Lemma 6.46, it remains to show that (6.58) a∈A Ba,j ⊆B(x, ρ)∩Ωj, where ρis as in (6.48). In other words, (6.47) will follow from (6.57) once we have (6.58). The Ba,j’s are all contained in Ωjby construction (when a∈A⊆Aj), and so it suffices to show that (6.59) Ba,j ⊆B(x, ρ) when a∈A in order to establish (6.58). Let a∈Abe given, and arbitrary. Thus a∈Ajand Ba,j intersects B(x, r), by the definition of A. Also, the radius of Ba,j is 10−1dist(a, M\Ωj), as in (6.28). Let ybe any element of Ba,j ∩B(x, r). From Lemma 6.35 we have that (6.60) dist(a, M\Ωj)≤10 9dist(y,M\Ωj),
618 S. Semmes When δ= 1 this is practically the same as what we got in Lemma 6.66. Specifically, we write Bas B(x, r), as in the notation above, and then (6.101) follows easily from (6.87), (6.88), (6.89), and (6.97). One can also think in terms of going directly to the conclusions of the earlier argument, and applying the A1condition (6.68) together with (6.71). When δ<1, one can derive (6.101) from its counterpart for δ= 1, using Lemma 3.1. Alternatively, one can also think of (6.101) when δ<1as being a special case of the argument for Lemma 6.66, since (6.102) w(y)δ≈1+ ∞ j=1 λδj 1Ωj(y). That is, each side of (6.102) is bounded by a constant multiple of the other, so that we can think of w(y)δas being like replacing λwith λδin the preceding arguments. This change is compatible with the requirement (6.67), since λ>1 implies that 1 <λ δ≤λ. Thus we have Lemma 6.99. Next, we want to derive some estimates which will be useful for checking Lipschitz and bilipschitz conditions with respect to Dδ(u.v)onM, where Dδ(u, v) is as in (2.11) in the statement of Proposition 2.10. We begin with the following auxiliary definition. Definition 6.103 (Admissible families of mappings). Let pbe a nonnegative integer, and let {ψa,j}a,j, be a family of mappings from Minto Rd, where jruns through all nonnegative integers and aruns through the set Ajfor each individual j. (Remember that Aj=A(Ωj) is the set associated to Ωjin Proposition 6.4, as mentioned just above (6.28).) This family is said to be admissible if the following two conditions hold: (6.104) supp ψa,j ⊆5Ba,j, where Ba,j is as in (6.28), and supp ψa,j denotes the closure of the set of x’s such that ψa,j(x)= 0; and (6.105) the ψa,j’s are Lipschitz (with respect to d(·,·)) on M, and with uniformly bounded constant. In general, when we refer to a function as being “Lipschitz on M”, we mean Lipschitz with respect to our original distance d(·,·) (rather than something like Dδ(·,·)).
Bilipschitz embeddings of metric spaces 619 As a concrete example of an admissible family of mappings, consider {ha,j}a,j , with each ha,j :M→Rdefined by (6.106) ha,j(x) = max(2 radius Ba,j −d(x, a),0). Here “radius Ba,j” means 10−1dist(a, M\Ωj), as in (6.28). (One should consider this as an assignment of a number to radius Ba,j, rather than a general definition. This is because Ba,j might be representable as a ball in Mwith center aand a different radius, i.e., Mmight have some kind of gaps. Notice also that M\Ωjis nonempty for all j, because Ωj⊆Ω0=M\{p0}, by construction.) These mappings ha,j are all Lipschitz with constant 1 (since functions of the form x→ dist(x, p) for any p∈Mare Lipschitz with constant 1, by the triangle inequality (as in (6.9)), and because this Lipschitz condition is not disturbed by the other operations in (6.106)). The localization condition (6.104) also holds automatically for each ha,j, with the 5 in (6.104) replaced with a 2. Thus {ha,j}a,j is indeed an admissible family. This type of family will be useful later on, for making some localizations. In Lemma 6.142, we shall consider another admissible family of mappings, based on the ga,j’s from (6.30). Before we get to that, we shall give some general estimates for admissible families of mappings. Lemma 6.107. Let {ψa,j}a,j be an admissible family of mappings into some Rp. For each δ∈(0,1] there is a constant C(δ)such that (6.108) ∞ j=0 a∈Aj λδj|ψa,j(x)−ψa,j(y)|≤C(δ)Dδ(x, y) for all x, y ∈M. This constant C(δ)also depends on the Lipschitz bound for the ψa,j’s, as in (6.105), and the other usual constants, like λand geometric constants for (M,d(u, v),µ)(but not on xor y). Let {ψa,j}a,j and δbe given as in the statement of the lemma. We shall first derive some preliminary bounds, and then deal with Lemma 6.107 afterwards. Sublemma 6.109. For each nonnegative integer j1and each x∈M we have that (6.110) ∞ j=j1 a∈Aj λδj|ψa,j(x)|≤Cλδj1dist(x, M\Ωj1). Here Cdepends on the Lipschitz bound for the ψa,j’s and the other usual parameters, but not on xor j1. (Actually, Cdoes not depend on δin this case.)
620 S. Semmes To see this, notice that the property of bounded overlap in part (ii) of Proposition 6.4 and the condition (6.104) on the supports of the ψa,j’s ensure that (6.111) ψa,j(x)= 0 for at most a bounded number of a’s in Aj for each fixed xand j. Thus there are only a bounded number of terms in the inner sum on the left side of (6.110) that really matter. Let us check that (6.112) |ψa,j(x)|≤Cdist(x, M\Ωj) for a suitable constant Cand all x∈M,j≥0, and a∈Aj. The support condition (6.104) and the Lipschitz bound (6.105) imply that |ψa,j(x)|is bounded by a constant multiple of the radius of Ba,j. The latter is equal to 10−1dist(a, M\Ωj), by (6.28). If ψa,j(x)= 0 (and these are the only x’s which we need to consider for (6.112)), then x∈5Ba,j, by (6.104). This implies that (6.113) dist(a, M\Ωj)≤2 dist(x, M\Ωj), by the same kind of argument as used to derive (6.37) in Lemma 6.35. Combining these pieces of information gives (6.112), as desired. From (6.111) and (6.112) we obtain that (6.114) ∞ j=j1 a∈Aj λδj|ψa,j(x)|≤ ∞ j=j1 Cλδj dist(x, M\Ωj) for a suitable constant C. Because of Lemma 6.41, this reduces further to (6.115) ∞ j=j1 a∈Aj λδj|ψa,j(x)|≤ ∞ j=j1 Cλδj 7j1−jdist(x, M\Ωj1). We can rewrite this as (6.116) ∞ j=j1 a∈Aj λδj|ψa,j(x)|≤Cλδj1∞ i=0 λδi 7−idist(x, M\Ωj1). The infinite series on the right-hand side converges, because λ≤2 (as in Standing Assumptions 6.98) and δ≤1. Thus the sum is really just a finite constant, and Sublemma 6.109 is an immediate consequence of (6.116).
Bilipschitz embeddings of metric spaces 621 Sublemma 6.117. For each nonnegative integer j1and every pair of points x, y ∈Mwe have that (6.118) j1 j=0 a∈Aj λδj|ψa,j(x)−ψa,j(y)|≤C(δ)λδj1d(x, y). This constant C(δ)depends on the usual parameters (in addition to δ), but it does not depend on j1,x,ory. For each fixed jwe have that (6.119) a∈Aj |ψa,j(x)−ψa,j(y)|≤Cd(x, y) for some constant Cand all x, y ∈M. This uses (6.111) to say that only boundedly many terms in the sum are nonzero, and then the Lipschitz condition (6.105) to bound the individual terms by a constant multiple of d(x, y). Thus (6.120) j1 j=0 a∈Aj λδj|ψa,j(x)−ψa,j(y)|≤C j1 j=0 λδj d(x, y), and Sublemma 6.117 follows by summing the geometric series. This uses the assumption that λ>1, as in Standing Assumptions 6.98, and in particular the constant gets large when λapproaches 1. Let us now use Sublemmas 6.109 and 6.117 to prove Lemma 6.107. Fix x, y ∈Mand δ∈(0,1], and set (6.121) B=B(x, 4 3d(x, y)), say. (We may as well assume that x=y, so that d(x, y)>0, since otherwise Lemma 6.107 is trivial.) We have that (6.122) Dδ(x, y)≈d(x, y)1 µ(B)B w(z)δdµ(z), i.e., each side of (6.122) is bounded by a constant multiple of the other. This follows from (2.11) and the doubling properties of µand w(z)δdµ(z), as in Remark 2.13. Let kbe as in Lemma 6.99, for this choice of B. From (6.101) in Lemma 6.99 we get that (6.123) C(δ)−1λδk d(x, y)≤Dδ(x, y)≤C(δ)λδk d(x, y)
622 S. Semmes for some constant C(δ) (which is not quite the same as the one in (6.101), in that it incorporates the one from (6.122) too). To prove Lemma 6.107, it is enough to show that (6.124) ∞ j=0 a∈Aj λδj|ψa,j(x)−ψa,j(y)|≤C(δ)λδk d(x, y) for some constant C(δ), i.e., (6.124) in place of (6.108), because of (6.123). Let Sdenote the left side of (6.124), and let S1and S2denote the pieces of Sthat correspond to the sums over j≤kand j>k, respectively. Thus (6.125) S=S1+S2, by definitions. For S1we have that (6.126) S1≤C(δ)λδk d(x, y) for some constant C(δ), because of Sublemma 6.117. For S2we get (6.127) S2≤Cλδ(k+1)(dist(x, M\Ωk+1) + dist(y,M\Ωk+1)) using Sublemma 6.109. We also have that (6.128) B⊆ Ωk+1, because of the choice of k(as in Lemma 6.99). Thus Bintersects M\Ωk+1, from which we may conclude that (6.129) dist(x, M\Ωk+1) + dist(y,M\Ωk+1)≤4d(x, y), using also the definition of Bin (6.121). Combining (6.127) with (6.129) we obtain (6.130) S2≤Cλδ(k+1) d(x, y). This together with (6.126) and (6.125) yields (6.124), which is what we needed to finish the proof of Lemma 6.107. The following is a mild strengthening of Lemma 6.107 which will also be useful.
Bilipschitz embeddings of metric spaces 623 Lemma 6.131. Let {ψa,j}a,j be an admissible family of mappings into some Rq. Fix a positive integer pand points x, y ∈M,x=y.Let Bbe the ball given in (6.121) (and depending on x,y), and let kbe the integer associated to Bas in Lemma 6.99. For each δ∈(0,1] there is a constant C(δ)such that (6.132) j:|j−k|≥p a∈Aj λδj|ψa,j(x)−ψa,j(y)|≤C(δ)λ−δp Dδ(x, y). Here the sum on the left is implicitly restricted to j’s which are nonnegative integers. The constant C(δ)does not depend on p,x,y,ork(but does depend on the Lipschitz bound for the ψa,j’s, and the other usual constants, like λand geometric constants for (M,d(u, v),µ)). In other words, the sum in (6.108) becomes small (compared to Dδ(x, y)) if we restrict ourselves to j’s which are far from k. To prove this, we proceed in exactly the same manner as for Lemma 6.107. Specifically, let Hdenote the double-sum on the left side of (6.132), and let H1,H2denote the portions of the sum which correspond to j≤k−pand to j≥k+p, respectively, so that (6.133) H=H1+H2 by definitions. Thus (6.134) H1≤C(δ)λδ(k−p)d(x, y), by Sublemma 6.117. (More precisely, we may apply Sublemma 6.117 when k−p≥0; if k<p, then H1is 0, and there is nothing to do.) From Sublemma 6.109 we have that (6.135) H2≤Cλδ(k+p)(dist(x, M\Ωk+p) + dist(y,M\Ωk+p)). Using Lemma 6.41 we can reduce this to (6.136) H2≤Cλδ(k+p)71−p(dist(x, M\Ωk+1) + dist(y,M\Ωk+1)). On the other hand, (6.129) holds for the same reason as before (i.e., (6.128)), and so we may replace (6.136) with (6.137) H2≤4Cλδ(k+p)71−pd(x, y). Combining (6.134) and (6.137) we have that (6.138) H=H1+H2≤C(λ−δp +λδp 71−p)λδk d(x, y).
624 S. Semmes We now apply (6.123) (which we may do, because the ball Band the integer khave been chosen here in exactly the same manner as before) to convert (6.138) into (6.139) H≤C(δ)(λ−δp +λδp 71−p)Dδ(x, y). From here we get (6.140) H≤C(δ)λ−δpDδ(x, y), (with a slightly larger choice of C(δ)). This uses the assumptions λ≤2 (as in Standing Assumptions 6.98) and δ≤1 (from the statement of the lemma) to ensure that (6.141) λδp 7−p≤λ−δp, which is exactly what we need to go from (6.139) to (6.140). The proof of Lemma 6.131 is now complete, because (6.140) is the same as (6.132) (by definition of H). Now that we have these basic estimates, we want to adjust the mappings ga,j from (6.30) to get an admissible family. Recall that the ga,j’s map into Rm, as in (6.30). Lemma 6.142. For each integer j≥0and element aof Ajthere is a mapping Ga,j :M→Rmsuch that supp Ga,j ⊆1 3Ba,j;(6.143) Ga,j is Lipschitz on Mwith constant ≤C0;(6.144) Ga,j is bilipschitz on Ea,j with constant ≤C0.(6.145) Here C0≥1depends on the doubling and BPE constants for (M,d(x, y),µ), but not on aor j. To prove Lemma 6.142, we start with the ga,j’s from (6.30). Fix j≥0 and a∈Aj. Without loss of generality, we may assume that ga,j takes the value 0 somewhere on Ea,j ; otherwise, we could make this be true by composing ga,j with a translation on Rm, which would not affect the bilipschitz condition (6.30) (nor the Ea,j’s). Using this normalization, we get that (6.146) |ga,j(z)|≤kdiam Ea,j
Bilipschitz embeddings of metric spaces 625 for all z∈Ea,j, since ga,j is Lipschitz on Ea,j with constant kby (6.30). Let us write radius Ba,j once again for the radius of the ball Ba,j, whose value is 10−1dist(a, M\Ωj), as in (6.28). (The actual value of the radius will not matter for the computation that we are about to perform, i.e., it will wash out in the end.) Because Ea,j ⊆1 4Ba,j, by (6.31), we have that (6.147) diam Ea,j ≤2 radius 1 4Ba,j =1 2radius Ba,j. Thus (6.148) |ga,j(z)|≤k 2radius Ba,j for all z∈Ea,j, by (6.146). Let us extend ga,j to M\1 3Ba,j by setting it to be 0 there. This does not affect the original choice of ga,j on Ea,j, since the latter is contained in 1 4Ba,j. Let us check that (6.149) ga,j is Lipschitz with constant 6kon Ea,j ∪M\1 3Ba,j, i.e., (6.150) |ga,j(x)−ga,j(y)|≤6kd(x, y) whenever x, y ∈Ea,j ∪M\1 3Ba,j. If xand yboth lie in M\1 3Ba,j, then (6.150) is trivial, since ga,j vanishes on M\1 3Ba,j.Ifx, y ∈Ea,j, then (6.150) follows from (6.30). The remaining possibility is that one of x,ylies in M\1 3Ba,j and the other in Ea,j ⊆1 4Ba,j. In this case we have that (6.151) d(x, y)≥1 12 radius Ba,j, and (6.150) follows from this and the fact that one of xand ysatisfies (6.148), while ga,j vanishes at the other one. This proves (6.149). Now choose Ga,j to be a Lipschitz extension of ga,j from Ea,j∪ M\1 3Ba,jto all of M(with values still in Rm). We can do this while maintaining a bound for the Lipschitz constant, because of Proposition 6.2. Thus Ga,j satisfies (6.144). We already set ga,j to be 0 on M\1 3Ba,j, so that (6.143) holds, and (6.145) follows from the bilipschitz condition (6.30) for ga,j and the fact that Ga,j is the same as ga,j on Ea,j, by construction. This completes the proof of Lemma 6.142. Instead of the ha,j’s from (6.106), it will be helpful to make localizations in a slightly more precise manner, as in the next lemma.
626 S. Semmes Lemma 6.152. Let an integer j≥0and an element aof Ajbe given. Define Ha,j :M→Rby (6.153) Ha,j(x) = max(1.5 radius Ba,j −dist(x, Ea,j),0). (As usual, radius Ba,j =10 −1dist(a, M\Ωj), as in (6.28).) Then Ha,j satisfies the following properties: Ha,j is Lipschitz with constant ≤1;(6.154) supp Ha,j ⊆2Ba,j;(6.155) Ha,j(x)≥1 4radius Ba,j when x∈Ba,j.(6.156) In particular, {Ha,j}a,j is an admissible family (in the sense of Definition 6.103). This is quite straightforward from the definitions, but let us be a bit careful. Notice first that each Ea,j is nonempty, because of (6.29), so that the distance function on the right side of (6.153) makes sense. Any function of the form x→ dist(x, Z), where Zis a nonempty subset of M, is a 1-Lipschitz function of x, by a standard application of the triangle inequality. (This is practically the same as (6.9), for instance.) From this it follows that Ha,j is 1-Lipschitz too, because the Lipschitz condition is not disturbed by the addition of a constant, or by taking the maximum (or minimum) with a constant (or any other 1-Lipschitz function). This gives (6.154). In order to check (6.155) and (6.156), let us observe that (6.157) d(x, a)−1 4radius Ba,j ≤dist(x, Ea,j) ≤d(x, a)+1 4radius Ba,j. These inequalities come from the fact that Ea,j ⊆1 4Ba,j, as in (6.31). (More precisely, we are also using the nonemptiness of Ea,j, as mentioned above, and the knowledge that Ba,j is centered at a, by its definition (6.28).) Once we have (6.157), the desired properties (6.155) and (6.156) follow from the definition (6.153) of Ha,j and easy calculation. This proves Lemma 6.152. The embedding fin Proposition 2.10 will be obtained by combining the Ga,j’s from Lemma 6.142 and the Ha,j ’s from Lemma 6.152. To do this, we shall need a bit of coding, and this is our next task.
Bilipschitz embeddings of metric spaces 627 Let L0and L1be large positive constants, to be chosen later. The only penalty for making L0,L1large will be in the size of the dimension of the target space Rfor the embedding fin Proposition 2.10. Put (6.158) C={(a, j):jis a nonnegative integer, and a∈Aj}. Given j, let us say that a, b ∈Ajare L1-neighbors if (6.159) L−1 1dist(b, M\Ωj)≤dist(a, M\Ωj)≤L1dist(b, M\Ωj) and (6.160) d(a, b)≤L1min(dist(a, M\Ωj),dist(b, M\Ωj)). Lemma 6.161 (Coding lemma). If L2is a positive integer which is sufficiently large (depending only on L0,L1, and the doubling constant for (M,d(x, y))), then there is a mapping Γ:C→{1,2,... ,L 2}(which is the “coding”) which satisfies the following property. Suppose that (a, j),(a,j)are elements of Csuch that Γ(a, j)= Γ(a,j). Then (6.162) j=jmod L0 and (6.163) a=aif also j=jand a, aare L1-neighbors. To prove this we shall use the following. Sublemma 6.164. For each j≥0and a∈Ajthere are at most C(L1)choices of b∈Ajsuch that aand bare L1-neighbors (where C(L1)depends on L1and the doubling constant for (M,d(x, y)), but not on jor a). We can derive this from the doubling condition for (M,d(x, y)). Let Nj(a) denote the set of b∈Ajwhich are L1-neighbors of a. Then (6.165) d(a, b)≤L2 1dist(a, M\Ωj) for all b∈Nj(b), by (6.159) and (6.160). Also, (6.166) B(b, (30L1)−1dist(a, M\Ωj)) ⊆1 3Bb,j
634 S. Semmes and the error term >1is given by (6.200) >1= (a,j)∈C:j=k Γ(a,k)=i λδj |Ha,j(x)−Ha,j (y)|. More precisely, (6.198) is derived from (6.172) by separating the terms in the definition of Hiaccording to whether j=kor not, and then applying the triangle inequality to get (6.201) β1≤|Hi(x)−Hi(y)|+>1 (which is the same as (6.198)). We want to analyze β1and >1. Sublemma 6.202. Notations and assumptions as above. If L1≥40, then (6.203) β1≥1 88λδk dist(x, M\Ωk)≥1 176λδk d(x, y). The second inequality in (6.203) follows automatically from (6.191), and so we only need to consider the first one. We should first check which terms in the sum in (6.199) are nonzero. Suppose that a∈Aksatisfies Γ(a, k)=iand Ha,k(x)= 0. The latter implies that x∈2Ba,k, by (6.155). We also have that x∈Bb,j,asin (6.194), so that 2Ba,k and Bb,j have nonempty intersection. This means that aand bare L1-neighbors in Ak, by Sublemma 6.181. Therefore a=b, because of Lemma 6.161 and the fact that Γ(a, k)=i=Γ(b, k). Conversely, Hb,k(x) is indeed nonzero, and (6.204) Hb,k(x)≥1 44λδk dist(x, M\Ωk). To see this, notice first that (6.205) Hb,k(x)≥1 4radius Bb,k =1 40 dist(b, M\Ωk). The first step in (6.205) is the same as (6.156), while the second step is just the definition of radius Bb,k. To go from (6.205) to (6.204), we apply (6.36) in Lemma 6.35 (with binstead of a), again using the fact that x∈Bb,k.
Bilipschitz embeddings of metric spaces 635 Now suppose that Ha,k(y)= 0 for some a∈Akwith Γ(a, k)=i. Then y∈2Ba,k, by (6.155). If ais another element of Akwith Γ(a,k)=i and Ha,k(y)= 0, then we also have that y∈2Ba,k, so that 2Ba,k and 2Ba,k intersect. As before, this means that aand aare L1-neighbors in Ak, by Sublemma 6.181, and hence that a=a, because of the properties of the coding in Lemma 6.161. In short, there is at most one possible choice for a∈Akwith Ha,k(y)= 0 and Γ(a, k)=i, and there may simply be none. To summarize, either (6.206) β1=λδk Hb,k(x) or (6.207) β1=λδk |Hb,k(x)−Ha,k(y)|, where a∈Ak,Ha,k(y)= 0, and Γ(a, k)=i. All of the other terms in (6.199) must vanish, by the arguments above. If (6.206) holds, then the first inequality in (6.203) follows from (6.204), and we are finished. Thus we suppose that (6.207) is true instead. If (6.208) Ha,k(y)≤1 80 dist(b, M\Ωk), then (6.209) Hb,k(x)−Ha,k(y)≥1 40 dist(b, M\Ωk)−1 80 dist(b, M\Ωk) ≥1 80 dist(b, M\Ωk) ≥1 88 dist(x, M\Ωk), where the first step comes from (6.205), and the last step uses Lemma 6.35 again, just as in the transition from (6.205) to (6.204). This and (6.207) imply (6.203). Finally, we consider the possibility that (6.207) holds, with a∈Ak, Ha,k(y)= 0, and Γ(a, k)=i, and that (6.210) Ha,k(y)>1 80 dist(b, M\Ωk) too (i.e., the opposite of (6.208)). By the definition (6.153) of Ha,k, the maximal value of Ha,k is (6.211) 1.5·radius Ba,k =1.5·10−1dist(a, M\Ωk) ≤1 5dist(a, M\Ωk),
636 S. Semmes and so (6.210) yields (6.212) dist(a, M\Ωk)>5 80 dist(b, M\Ωk)= 1 16 dist(b, M\Ωk). We want to use this to show that (6.213) aand bare L1-neighbors in Ak, at least if L1is large enough. Let us first check that (6.214) dist(a, M\Ωk)≤2 dist(b, M\Ωk). Since Ha,k(y)= 0, we have that (6.215) d(y,a)≤2 radius Ba,k =1 5dist(a, M\Ωk), by (6.155) and the fact that radius Ba,k =10 −1dist(a, M\Ωk). On the other hand, (6.216) dist(a, M\Ωk)≤d(y,a) + dist(y,M\Ωk), as in (6.9), so that (6.217) 4 5dist(a, M\Ωk)≤dist(y,M\Ωk), using (6.215). Combining this with (6.188) yields (6.218) 4 5dist(a, M\Ωk)≤dist(x, M\Ωk). We also have that (6.219) dist(x, M\Ωk)≤11 10 dist(b, M\Ωk), by (6.36) in Lemma 6.35 (with binstead of a) and the fact that x∈Bb,k, and (6.214) follows immediately from this and (6.218). From (6.212) and (6.214) we have that aand bsatisfy the first requirement (6.159) for being L1-neighbors in Akas soon as L1≥16. We want to verify that the second requirement (6.160) also holds when L1is large enough. From the triangle inequality we have that (6.220) d(a, b)≤d(a, y)+d(y,x)+d(x, b).
Bilipschitz embeddings of metric spaces 637 This leads to (6.221) d(a, b)≤1 5dist(a, M\Ωk)+2 dist(x, M\Ωk)+ 1 10 dist(b, M\Ωk), because of (6.215), (6.191), and the fact that x∈Bb,k. Combining this with (6.219) we obtain that (6.222) d(a, b)≤1 5dist(a, M\Ωk)+23 10 dist(b, M\Ωk). If we use (6.212), then we can convert (6.222) into (6.223) d(a, b)≤2 + 368 10 dist(a, M\Ωk), while (6.214) gives (6.224) d(a, b)≤4+23 10 dist(b, M\Ωk). Thus (6.225) d(a, b)≤40 min(dist(a, M\Ωk),dist(b, M\Ωk)). This shows that (6.160) holds when L1≥40. To recapitulate, for this last part of the proof of Sublemma 6.202, we have assumed that (6.210) and (6.207) hold, with a∈Ak,Ha,k(y)=0, and Γ(a, k)=i, and we have shown that (6.213) is true (i.e., and bare L1-neighbors), at least when L1≥40. From this we may conclude that a=b, because of (6.163) in Lemma 6.161 (and the fact that Γ(a, k)=i= Γ(b, k)). On the other hand, the information that Ha,k(y)= 0 implies that y∈2Ba,k, by (6.155). This is the same as saying that y∈2Bb,k, since a=b, which is exactly what is ruled out by the hypothesis of Case I, under which we are currently working. Thus the last situation for Sublemma 6.202 (described in (6.210) and the lines immediately before it) simply does not occur in Case I. We have already seen that the conclusion (6.203) of Sublemma 6.202 holds in the other possible circumstances (i.e., when (6.206) is true, or (6.207) and (6.208) are satisfied), and so Sublemma 6.202 is completely proved. Now that we have a good lower bound for β1, we want to bound >1 from above, and show that it is small compared to β1. Let us begin with the observation that (6.226) >1≤ (a,j)∈C |j−k|≥L0 λδj |Ha,j(x)−Ha,k(y)|.
638 S. Semmes The right-hand side here in (6.226) differs from the definition (6.200) of >1only in the collection of pairs (a, j) over which the sum extends. The collection of pairs (a, j) in (6.226) contains the corresponding collection for (6.200) (and hence the sum in (6.226) is larger). This follows from the properties of our coding, as formulated in Lemma 6.161. Namely, if (a, j)∈Csatisfies Γ(a, j)=iand j=k, as in (6.200), then we must have |j−k|≥L0, because of (6.162) in Lemma 6.161 and the fact that Γ(b, k)=iby construction (as in (6.196)). This gives (6.226) from (6.200). We may now apply Lemma 6.131 (with ψa,j =Ha,j and p=L0)to obtain that (6.227) >1≤Cλ−δL0Dδ(x, y), as a consequence of (6.226). This constant Cdoes not depend on L0, x,ory, but only on the usual parameters. Let us rewrite (6.203) in Sublemma 6.202 as (6.228) β1≥C−1Dδ(x, y), using (6.187). From (6.227) and (6.228) we conclude that (6.229) β1−>1≥C−1Dδ(x, y) when L0is large enough, depending on the usual parameters (and not on xor yin particular). The constant Cin (6.229) also depends only on the usual parameters. Combining (6.229) with (6.197) and (6.198), we obtain that (6.230) |f(x)−f(y)|≥C−1Dδ(x, y) when L0is large enough, with the same conditions on L0and the same constant Cas in (6.229). This gives (6.178) in Lemma 6.177 under the circumstances of Case I, which is what we wanted. Case II: y∈2Bb,k, and (6.231) |Hb,k(x)−Hb,k(y)|≥ 1 40C−2 0d(x, y), where C0≥1 is the constant from Lemma 6.142.
Bilipschitz embeddings of metric spaces 639 This case can be handled in practically the same manner as Case I. We use the same two initial steps (6.197), (6.198) as before, with the same definitions of β1and >1. The analogue of Sublemma 6.202 is much simpler now, because we have (6.232) β1=λδk |Hb,k(x)−Hb,k(y)| in place of (6.206), (6.207). This can be checked through the same kind of arguments as in the first part of the proof of Sublemma 6.202. The main point is that the a∈Akwhich occurs in (6.207) has to be equal to bunder the circumstances of the present case, since y∈2Bb,k, and because of the coding property (6.163) in Lemma 6.161. Combining (6.232) and (6.231) we get that (6.233) β1≥1 40C−2 0λδk d(x, y). This is exactly analogous to the conclusion (6.203) of Sublemma 6.202. From here one can proceed as in Case I, to conclude that (6.178) holds in Case II as well. Case III: y∈2Bb,k, and we also have that (6.234) |Hb,k(x)−Hb,k(y)|<1 40C−2 0d(x, y), and (6.235) dist(x, Ek)<1 40C−2 0d(x, y), where C0≥1 is again the constant from Lemma 6.142. Let us begin with some preliminary observations pertaining to the hypotheses (6.234) and (6.235) above. Sublemma 6.236. dist(x, Ek) = dist(x, Eb,k). Indeed, suppose to the contrary that there is a point z∈Ek\Eb,k such that (6.237) d(x, z)<dist(x, Eb,k). Because of (6.235), such a point zsatisfies (6.238) d(x, z)<1 40C−2 0d(x, y).
640 S. Semmes This gives (6.239) d(x, z)<1 20C−2 0dist(x, M\Ωk), by (6.191). By definition (see (6.32)), Ekis the union of the sets Ea,k,a∈Ak. Thus there is an a∈Aksuch that z∈Ea,k. Since we are assuming that z/∈Eb,k, we should have that a=b. We would like to show that x∈Ba,k. If we can do that, then (6.237) would contradict the minimality condition (6.195) in the choice of b(since dist(x, Ea,k)≤d(x, z) automatically), and we would be finished with the proof of Sublemma 6.236. Remember from (6.31) that Ea,k ⊆1 4Ba,k. To show that x∈Ba,k,it therefore suffices to show that (6.240) d(x, z)≤3 4radius Ba,k =3 410−1dist(a, M\Ωk), by the definition (6.28) of Ba,k. Because of (6.36) in Lemma 6.35 (applied to z∈Ba,k instead of x), it is enough to show that (6.241) d(x, z)≤3 411−1dist(z,M\Ωk) (i.e., this would imply (6.240)). As a general fact, we have that (6.242) dist(x, M\Ωk)≤d(x, z) + dist(z,M\Ωk), as in (6.9). Combining this with (6.239) (and the inequality C0≥1) yields (6.243) dist(x, M\Ωk)≤1 20 dist(x, M\Ωk) + dist(z,M\Ωk). Hence (6.244) dist(x, M\Ωk)≤20 19 dist(z,M\Ωk). Putting this back into (6.239) we get that (6.245) d(x, z)≤1 19 dist(z,M\Ωk). This implies (6.241). Sublemma 6.236 follows from here, as mentioned before.
Bilipschitz embeddings of metric spaces 641 Sublemma 6.246. Hb,k(x)=1.5 radius Bb,k −dist(x, Eb,k). Indeed, Hb,k(x) = max(1.5 radius Bb,k −dist(x, Eb,k),0), by definition. (See (6.153).) Because x∈Bb,k, as in (6.194), we have that (6.247) dist(x, Eb,k)≤1.5 radius Bb,k, by the second inequality in (6.157). This proves Sublemma 6.246. Sublemma 6.248. dist(y,Eb,k)<1 20 C−2 0d(x, y). To see this, we begin with the observation that (6.249) Hb,k(y)≥Hb,k(x)−|Hb,k(x)−Hb,k(y)|, by the triangle inequality. Using Sublemma 6.246 we can convert this into (6.250) Hb,k(y)≥1.5 radius Bb,k −dist(x, Eb,k)−|Hb,k(x)−Hb,k(y)|. Substituting (6.234) and (6.235) into (6.250), we obtain (6.251) Hb,k(y)>1.5 radius Bb,k −1 40C−2 0d(x, y)−1 40C−2 0d(x, y) =1.5 radius Bb,k −1 20C−2 0d(x, y). If we can show that (6.252) Hb,k(y)>0, then Sublemma 6.248 will follow, because (6.253) Hb,k(y)=1.5 radius Bb,k −dist(y,Eb,k) when Hb,k(y)>0, by the definition (6.153) of Hb,k(y). It is enough to show that (6.254) 1 20 d(x, y)<1.5 radius Bb,k instead of (6.252), because of (6.251) and the fact that C0≥1. By definition, (6.255) radius Bb,k =1 10 dist(b, M\Ωk),
642 S. Semmes while (6.256) dist(x, M\Ωk)≤11 10 dist(b, M\Ωk), as in (6.36) in Lemma 6.35 (with bin place of a). (Remember that x∈Bb,k, by our choice of b. See (6.194).) We also have that (6.257) d(x, y)≤2 dist(x, M\Ωk), by (6.191). Thus (6.258) 1 20 d(x, y)≤1 10 dist(x, M\Ωk)≤11 100 dist(b, M\Ωk), using (6.256) for the second step. The last expression is strictly less than 1.5 radius Bb,k, by (6.255). This gives (6.254), and Sublemma 6.248 follows. Sublemmas 6.236 and 6.248 and the assumption (6.235) tell us that x and ylie close to Eb,k. We want to use this to bound |f(x)−f(y)|from below, by reducing to the bilipschitz condition on Gb,k from Lemma 6.142. We start with the inequality (6.259) |f(x)−f(y)|≥|Gi(x)−Gi(y)|, which follows automatically from (6.174). This time we write (6.260) |Gi(x)−Gi(y)|≥β2−>2, where the main term β2is given by (6.261) β2= a∈Ak Γ(a,k)=i λδk (Ga,k(x)−Ga,k(y)) , and the error term is (6.262) >2= (a,j)∈C:j=k Γ(a,k)=i λδj |Ga,j(x)−Ga,j (y)|.
Bilipschitz embeddings of metric spaces 643 The derivation of (6.260) from the definition (6.172) of Giis completely analogous to the derivation of (6.198) from the definition of Hibefore, in (6.172); that is, we separate terms in the sum in (6.172) that defines Gi according to whether j=kor not, and then use the triangle inequality to get (6.260). Under the present conditions, the formula for β2reduces to (6.263) β2=λδk |Gb,k(x)−Gb,k(y)|. In other words, (6.264) Ga,k(x)=Ga,k(y) = 0 when a∈Ak,Γ(a, k)=i,a=b. This follows from considerations of coding and L1-neighbors in Aksimilar to ones in the treatment of the previous two cases. Specifically, we have that x∈Bb,k by the choice of b, as in (6.194), while y∈2Bb,k by the hypothesis of this case. If Ga,k(x)orGa,k(y) is not zero, it means that xor ylies in 1 3Ba,k, by (6.143) in Lemma 6.142. This leads to (6.265) 2Bb,k ∩Ba,k =∅, and hence that aand bare L1-neighbors, as in Sublemma 6.181. Thus a=bwhen Γ(a, k)=i(= Γ(b, k)), because of the property (6.163) in Lemma 6.161. This gives (6.264), and (6.263) then follows from (6.261). We want to use the bilipschitz condition (6.145) for Gb,k in Lemma 6.142 to obtain a lower bound for β2. This bilipschitz condition applies only to elements of Eb,k, and so we cannot apply it directly to x and y. Thus we first choose x,y∈Eb,k such that (6.266) d(x, x)<1 40C−2 0d(x, y) and d(y,y)<1 20C−2 0d(x, y). We can do this, because (6.235) and Sublemmas 6.236 and 6.248 ensure that dist(x, Eb,k)<1 40 C−2 0d(x, y) and dist(y,Eb,k)<1 20 C−2 0d(x, y). The bilipschitz condition (6.145) for Gb,k yields (6.267) |Gb,k(x)−Gb,k(y)|≥C−1 0d(x,y). We want to convert this into information about xand y. The Lipschitz condition (6.144) for Gb,k and (6.266) imply that (6.268) |Gb,k(x)−Gb,k(x)|+|Gb,k(y)−Gb,k(y)| ≤C0(d(x, x)+d(y,y)) <3 40C−1 0d(x, y).
650 S. Semmes while d(a, y)≤1 5dist(a, M\Ωk+1) by (6.309), d(x, y) is bounded in terms of dist(q,M\Ωk+1) by (6.285) and (6.289), and d(x, q)≤ 10−1dist(q,M\Ωk+1) by (6.286). Using this and the previous estimates one can get the second requirement (6.160) for aand qto be L1-neighbors in Ak+1 when L1is large enough, i.e., d(a, q) is bounded by the minimum of L1dist(a, M\Ωk+1) and L1dist(q,M\Ωk+1). The size requirement for L1can be given explicitly in terms of the constant C0(from Lemma 6.142) and ordinary numbers (like the 58 above). Thus we have shown that if (6.301) and (6.306) hold, and if L1is large enough, then aand qare L1-neighbors in Ak+1. Since we also have that Γ(a, k +1)=t=Γ(q,k + 1) (as mentioned just after (6.301)), the property (6.163) in Lemma 6.161 implies that a=q. This is incompatible with (6.309) and Sublemma 6.287, and so we conclude that this last scenario (in which (6.301) and (6.306) hold) is not possible (at least if L1is large enough). The proof of Sublemma 6.298 is now complete, since we have shown that (6.299) is true under either of the conditions (6.300) or (6.301) together with (6.304), and that the remaining possibility of (6.301) and (6.306) simply does not occur (when L1is large enough). From now on let us assume that L1is large enough for the purposes of Sublemma 6.298. Let us reformulate the conclusion (6.299) of Sublemma 6.298 as saying that (6.314) β3≥1 3520C−2 0λδ(k+1) d(x, y). This we can do because of (6.285). We conclude that (6.315) β3≥C−1Dδ(x, y), by (6.187). (As usual, this constant Cdepends only on suitable parameters, and not on x,y,orkin particular.) It remains to estimate >3, and this we can do in practically the same manner as in the earlier cases. Specifically, we first use the property (6.162) of our coding to convert (6.297) into (6.316) >3≤ (a,j)∈C:|j−(k+1)|≥L0 λδj |Ha,j(x)−Ha,j(y)|. We then apply Lemma 6.131 to obtain (6.317) >3≤Cλ −δL0Dδ(x, y).
Bilipschitz embeddings of metric spaces 651 This uses also the admissibility of the family {Ha,j}a,j provided by Lemma 6.152 for the applicability of Lemma 6.131. If L0is large enough, depending on the usual parameters, then we have that (6.318) β3−>3≥C−1Dδ(x, y), where this constant Cis 2 times the one in (6.315). This follows immediately from (6.315) and (6.317). From here we conclude that (6.319) |f(x)−f(y)|≥C−1Dδ(x, y) (with the same constant Cas in (6.318)), because of (6.294) and (6.295). This gives (6.178) again in this case, which is what we wanted. To summarize, we have shown that (6.178) holds in each of Cases I, II, III, and IV. These four cases cover all situations, as one can easily verify. Thus Lemma 6.177 is now completely proved, and Proposition 2.10 follows as well. References [A1] P. Assouad, Espaces M´etriques, Plongements, Facteurs, Th`ese de Doctorat (January, 1977), Universit´e de Paris XI, 91405 Orsay, France. [A2] P. Assouad,´ Etude d’une dimension m´etrique li´ee `a la possibilit´e de plongement dans Rn,C. R. Acad. Sci. Paris 288 (1979), 731–734. [A3] P. Assouad, Plongements Lipschitziens dans Rn,Bull. Soc. Math. France 111 (1983), 429–448. [CM] R. Coifman and Y. Meyer, Au-del`a des op´erateurs pseudodiff´erentiels, Ast´erisque 57,Soci´et´e Math´ematique de France (1978). [CR] R. Coifman and R. Rochberg, Another characterization of BMO, Proc. Amer. Math. Soc. 79 (1980), 249–254. [CW1] R. Coifman and G. Weiss,“Analyse Harmonique Non-commutative sur Certains Espaces Homog`enes,” Lecture Notes in Math. 242, Springer-Verlag, 1971. [CW2] R. Coifman and G. Weiss, Extensions of Hardy spaces and their use in analysis, Bull. Amer. Math. Soc. 83 (1977), 569–645.
652 S. Semmes [DS1] G. David and S. Semmes, Strong A∞-weights, Sobolev inequalities, and quasiconformal mappings, in “Analysis and Partial Differential Equations,” edited by C. Sadosky, Lecture Notes in Pure and Applied Mathematics 122, Marcel Dekker, 1990, pp. 101–111. [DS2] G. David and S. Semmes, Singular Integrals and Rectifiable Sets in Rn: au-del`a des graphes lipschitziens, Ast´erisque 193, Soci´et´e Math´ematique de France (1991). [DS3] G. David and S. Semmes, Quantitative rectifiability and Lipschitz mappings, Trans. Amer. Math. Soc. 337 (1993), 855–889. [DS4] G. David and S. Semmes,“Analysis of and on Uniformly Rectifiable Sets,” Mathematical Surveys and Monographs 38, 1993, American Mathematical Society. [DS5] G. David and S. Semmes,“Fractured Fractals and Broken Dreams: Self-Similar Geometry through Metric and Measure,” Oxford Lecture Series in Mathematics and its Applications 7, Oxford University Press, 1997. [Fe] H. Federer,“Geometric Measure Theory,” Springer-Verlag, 1969. [Ga] J. Garnett,“Bounded Analytic Functions,” Academic Press, 1981. [Ge] F. Gehring, The Lpintegrability of the partial derivatives of a quasiconformal mapping, Acta Math. 130 (1973), 265–277. [J] J. L. Journ´ e,“Calder´on-Zygmund Operators, Pseudodifferential Operators, and the Cauchy Integral of Calder´on,” Lecture Notes in Math. 994, Springer-Verlag, 1983. [Pa] P. Pansu,M´etriques de Carnot-Carath´eodory et quasiisom´etries des espaces sym´etriques de rang un, Ann. of Math. 129 (1989), 1–60. [Se1] S. Semmes, Bilipschitz mappings and strong A∞weights, Ann. Acad. Sci. Fenn. Ser. A I Math. 18 (1993), 211–248. [Se2] S. Semmes, On the nonexistence of bilipschitz parameterizations and geometric problems about A∞weights, Rev. Mat. Iberoamericana 12 (1996), 337–410. [Se3] S. Semmes, Metric Spaces and Mappings Seen at Many Scales, appendix, in “Metric Structures in Riemannian and non-Riemannian Spaces,” by M. Gromov et al, Birkh¨auser. [St1] E. M. Stein,“Singular Integrals and Differentiability Properties of Functions,” Princeton University Press, 1970. [St2] E. M. Stein,“Harmonic Analysis : Real-Variable Methods, Orthogonality, and Oscillatory Integrals,” Princeton University Press, 1993.
Bilipschitz embeddings of metric spaces 653 [TV] P. Tukia and J. V¨ ais¨ al¨ a, Quasisymmetric embeddings of metric spaces, Ann. Acad. Sci. Fenn. Ser. A I Math. 5(1980), 97–114. Department of Mathematics Rice University Box 1892 Houston TX 77251-1892 U.S.A. e-mail: [email protected] Primera versi´o rebuda el 2 de setembre de 1998, darrera versi´o rebuda el 15 de mar¸c de 1999