COMPRESSION BOUNDS FOR LIPSCHITZ MAPS FROM THE HEISENBERG GROUP TO L_{1}

JEFF CHEEGER, BRUCE KLEINER, AND ASSAF NAOR

Abstract. We prove a quantitative bi-Lipschitz nonembedding theorem for the Heisenberg group with its Carnot-Carathéodory metric and apply it to give a lower bound on the integrality gap of the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem.

Contents

1. Introduction and statement of main results  2
2. The proof of Theorem 1.1; overview and background  8
3. Preliminaries  16
4. Reduction to the stability of individual monotone sets  18
5. Cuts with small perimeter  25
6. The kinematic formula and δ-monotone sets  26
7. The quantitative interior and boundary  28
8. Classification of monotone sets  34
9. Proof of the stability of monotone sets  38
10. Nondegeneracy of the initial configuration.  42
11. Proof of Lemma 7.8  48
12. Proof of Proposition 7.10  54
13. Appendix 1: The Sparsest Cut problem  63
14. Appendix 2: Quantitative bounds, coercivity and monotonicity  65
References  66

J.C. was supported in part by NSF grant DMS-0704404.

B.K. was supported in part by NSF grant DMS-0805939.

A. N. was supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

1. Introduction and statement of main results

Theorem 1.1, the main result of this paper, is a quantitative bi-Lipschitz nonembedding theorem, in which the domain is a metric ball in the Heisenberg group, ℍ, with its Carnot-Carthéodory metric, d^{ℍ}, and the target is the space L_{1}; for the definition of d^{ℍ} see the subsection of Section 2 entitled: “The Heisenberg group as a PI space”. This result has consequences of a purely mathematical nature, as well as for theoretical computer science.

Define c_{p}(X, d^{X}), the L_{p} distortion of the metric space (X, d^{X}), to be the infimum of those D > 0 for which there exists a mapping f : X → L_{p} satisfying \frac{∥f(x)−f(y)∥_{Lp}}{d^{X}(x,y)} ∈ [1, D] for all distinct x, y ∈ X. The quantitative study of bi-Lipschitz embeddings of finite metric spaces in L_{p} spaces goes back to [50, 28]. The modern period begins with a result of Bourgain, [12], who answered a question of [39] by showing that for every fixed p, any n-point metric space can be embedded in L_{p} with distortion ≲ log n.^{1} By [53], Bourgain’s theorem is sharp for any fixed p < ∞.

Since L_{1}, equipped with the square root of its usual distance, is well known to be isometric to a subset of L_{2} (see for example [63]) it follows that if (X, d^{X}) isometrically embeds in L_{1}, then (X, \sqrt{d^{X}}) isometrically embeds in L_{2}. Metrics for which (X, \sqrt{d^{X}}) isometrically embeds in L_{2} are said to be of negative type. Such metrics will play a fundamental role in our discussion. On the other hand, it is also well known that L_{2} embeds isometrically in L_{1} (see for example [64]) which implies that c_{1}(X, d^{X}) ⩽ c_{2}(X, d^{X}), for all (X, d^{X}). Recently, it was shown that for n-point metric spaces of negative type, c_{2}(X, d^{X}) ≲ (log n)^{1/2+o(1)}, and in particular c_{1}(X, d^{X}) ≲ (log n)^{1/2+o(1)}; see [5], which improves on a corresponding result in [15]. For embeddings in L_{2}, the result of [5] is sharp up to the term o(1); see [28].

As shown in [48], the Carnot-Carathéodory metric d^{ℍ} is bi-Lipschitz to a metric of negative type. From this and Corollary 1.5 of Theorem 1.1 below, it follows immediately that for all n, there exist n-point metric spaces of negative type with c_{1}(X, d^{X}) ≳ (log n)^{δ}, for some explicit δ > 0. From the standpoint of such nonembedding theorems, the target L_{1} presents certain challenges. Lipschitz functions f : ℝ → L_{1} need not be differentiable anywhere. Therefore, a tool which is useful for L_{p} targets with 1 < p < ∞ is not available. Moreover, the fact that L_{2} embeds isometrically in L_{1} implies that bi-Lipschitz embedding in L_{1} is no harder than in L_{2} and might be strictly easier in cases of interest.

The Sparsest Cut problem is a fundamental NP hard problem in theoretical computer science. This problem will formally stated in Section 13 (an appendix) where some additional details of the discussion which follows will be given; see also our paper [24] (and the references therein) which focuses on the computer science aspect of our work. A landmark development took place in the 1990’s, when it was realized that this optimization problem for a certain functional defined on all subsets of an n-vertex weighted graph, is equivalent to an optimization problem for a corresponding functional over all functions from an n-vertex weighted graph to the space L_{1}; see [10, 53, 9]. This is a consequence of the cut cone representation for metrics induced by maps to L_{1}, which also plays a fundamental role in this paper; see Section 1. Once this reformulation has been observed, one can relax the problem to an optimization problem for the corresponding functional over functions with values in any n-point metric space. The relaxed problem turns out to be a linear program, and hence, is solvable in polynomial time. Define the integrality gap of this relaxation to be the supremum over all n point weighted graphs of the ratio of the solution of the original problem to the relaxed one. The integrality gap measures the performance of the relaxation in the worst case. It is essentially immediate that the integrality gap is ⩽ the supremum of c_{1}(X, d^{X}) over all n point metric spaces, (X, d^{X}), and hence, by Bourgain’s theorem is ≲ log n; see [53, 9]. This upper bound relies only on the form of the functional and not on any special properties of L_{1}. A duality argument based on the cut cone representation shows that the integrality gap is actually equal to the supremum of c_{1}(X, d^{X}) over all n point metric spaces.

1In this paper, the symbols ≲, ≳, denote the corresponding inequalities, up to a universal multiplicative constant, which in all cases can be explicitly estimated from the corresponding proof. Similarly, ≍ denotes equivalence up to such a factor.

Subsequently, Goemans [31] and Linial [51] observed that if in relaxing the Sparsest Cut problem as above, one restricts to n point metric spaces of negative type, one obtains a semidefinite programming problem, which, by the Ellipsoid Algorithm, can still be solved in polynomial time with arbitrarily good precision; see [34]. As above, by the duality argument, the integrality gap for the Goemans-Linial semidefinite relaxation is actually equal to the supremum of c_{1}(X, d^{X}) over all n point metric spaces of negative type. Based on certain known embedding results for particular metric spaces of negative type, the hope was that this integrality gap might actually be bounded (the “Goemans-Linial conjecture”) or in any case, bounded a very slowly growing function of n. At present, one knows the upper bound ≲ (log n)^{1/2+o(1)}, which follows from from [5]. This result makes the Goemans-Linial semidefinite relaxation the most successful algorithm to date for solving the Sparsest Cut problem to within a definite factor. In the opposite direction, it was shown in [43] that the integrality gap for the Goemans-Linial semidefinite relaxation is ≳ log log n. The analysis of [43], improved upon that of the breakthrough result of [41], which was the first to show that the Goemans-Linial semidefinite relaxation cannot yield a constant factor approximation algorithm for the Sparsest Cut problem, thus resolving the Goemans-Linial conjecture [31, 51, 52]. These lower bounds on the integrality gap depend on its characterization as the supremum of c_{1}(X, d^{X}) over all n point metric spaces of negative type.

Motivated by the potential relevance to the Sparsest Cut problem, the question of whether (ℍ, d^{ℍ}) bi-Lipschitz embeds in L_{1} was raised in [48]. In response, it was shown in [18] that if U ⊂ ℍ is open and f : U → L_{1} is Lipschitz (or more generally of bounded variation), then for almost all x ∈ U (with respect to Haar measure) and y varying in the coset of the center of ℍ containing x, one has lim_{y→x} \frac{∥f(y)−f(x)∥_{L_{1}}}{d^{ℍ}(x,y)} = 0. Thus, (ℍ, d^{ℍ}) does not admit a bi-Lipschitz embedding into L_{1}.

For further applications as discussed above, a quantitative version of this theorem of [18] was required; see Theorem 1.1 below.^{2} It follows from Corollary 1.5 of Theorem 1.1 that there exists a sequence of n-point metric spaces, (X_{n}, d^{X_{n}}), of negative type, such that c_{1}(X_{n}, d^{X_{n}}) ≳ (log n)^{δ} and hence, that the integrality gap for the Goemans Linial relaxation of Sparsest Cut is ≳ (log n)^{δ} for some explicit δ > 0; compare Remark 1.7. This represents an exponential improvement on the above mentioned lower bound ≳ log log n; compare also the upper bound ⩽ (log n)^{1/2+o(1)}.

2For purposes of exposition, in Theorem 1.1, we restrict attention to the case of Lipschitz maps, although everything we say has an analogous statement which apply to BV maps as well, sometimes with minor variations.

We also give a purely mathematical application of Theorem 1.1 to the behavior of the L_{1} compression rate of the the discrete Heisenberg group. The L_{1} compression rate is a well studied invariant of the asymptotic geometry of a finitely generated group, which was defined by Gromov in [32]; see below for the definition.

In what follows, given p ∈ ℍ and r > 0, we denote the d^{ℍ}-open ball of radius r centered at p by B_{r}(p) = {x ∈ ℍ : d^{ℍ}(x, p) < r}. On cosets of the center of H (viewed as the z-axis in ℝ^{3}) let L denote 1-dimensional Lebesgue measure associated to the standard Euclidean metric on ℝ^{3}. Thus, L × L denotes the corresponding measure on pairs of points, (x_{1}, x_{2}) which lie the center.

Note that cosets of the center are parameterized by ℝ^{2}. Below, L_{2} denotes Lebesgue measure on ℝ^{2}. Let F denote a subset of pairs (x_{1}, x_{2}), such that x_{1}, x_{2} lie on some coset of the center \underline{L}. Define a measure on such subsets by stipulating that the measure of F is given by

∫_{ℝ^{2}}(L × L)(F ∩ (\underline{L} × \underline{L})) dL_{2}(\underline{L}) .

Theorem 1.1 (Quantitative central collapse). There exists a universal constant δ ∈ (0, 1) such that for every p ∈ ℍ, every f : B_{1}(p) → L_{1} with Lip(f) ⩽ 1, and every ϵ ∈ (0, \frac{1}{4}), there exists r ⩾ ϵ/2 such that with respect to Haar measure, for at least half ^{3} of the points x ∈ B_{\frac{1}{2}} (p), at least half of the points (x_{1}, x_{2}) ∈ B_{r}(x) × B_{r}(x) which lie on the same coset of the center with d^{ℍ}(x_{1}, x_{2}) ∈ [ϵr/2, 3ϵr/2] satisfy:

(1.2)  \frac{∥f(x_{1}) − f(x_{2})∥_{L_{1}}}{d^{ℍ}(x_{1}, x_{2})} ⩽ \frac{1}{(log(1/ϵ))^{δ}} .

In particular, compression by a factor of η ∈ (0, \frac{1}{2}) is guaranteed to occur for a pair of points whose distance is ≳ e^{−2η^{−c}}, where c = δ^{−1} (δ as in (1.2)).

The constant δ in Theorem 1.1 can be explicitly estimated from our proof; a crude estimate is δ = 2^{−60} in Theorem 1.1. At various points in the proof, we have sacrificed sharpness in order to simplify the exposition; this is most prominent in Proposition 7.10 below, which must be iterated several times, thus magnifying the non-sharpness. Obtaining the best possible δ in Theorem 1.1 remains an interesting open question, the solution of which probably requires additional ideas beyond those contained in this paper.

Before discussing the consequences of Theorem 1.1, we briefly indicate the reason for the form of the estimate (1.2); see also the discussion of Section 2. We will associate to f a nonnegative quantity, the total nonmonotonicty, which can be written as a sum over scales, and on each scale as an integral over locations. The assumption Lip(f) ⩽ 1 turns out to imply an a priori bound on the total nonmonotonicity. Since for ϵ ∈ (0, 1), the total number of scales between 1 and ϵ is ≍ log(1/ϵ), by the pigeonhole principle, there exists a scale as in (1.2), such that at most locations, the total nonmonoticity is ≲ 1/(log(1/ϵ)). We show using a stability theorem, Theorem 4.13, that for suitable δ, this gives (1.2). This discussion fits very well with a quantitative result (and phenomenon) due in a rather different context to Jones; see [40] and compare the discussion in Section 2. As explained in Section 14, the argument indicated above can be viewed as a particular instance of one which is applicable in considerable generality.

3In Theorem 1.1, by suitably changing the constant δ, “at least half” can be replaced by any definite fraction.

The discrete case. As we have indicated, Theorem 1.1 has implications in the context of finite metric spaces. These are based on properties of the discrete version of Heisenberg group, ℍ(ℤ) (defined below) and its metric balls, which follow from Theorem 1.1.

We emphasize at the outset that our results in the discrete case are obtained (without difficulty) directly from the corresponding statements in the continuous case, and not by a “discretization” of their proofs. As in [18] and in [23], where a different proof of the nonquantitative result of [18] is given, the proof of Theorem 1.1 is carried out in the continuous case because in that case, the methods of real analysis are available. Nonetheless, in the present instance, the quantitative issues remain highly nontrivial and the proof requires new ideas beyond those of [18], [23]; see the discussion at the beginning of Section 2 and in particular Remark 2.1.

We will view ℍ as ℝ^{3} equipped with the noncommutative product (a, b, c) · (a′, b′, c′) = (a + a′, b + b′, c + c′ + ab′ − ba′); for further discussion of ℍ, see Section 2. From the multiplication formula, it follows directly that for R > 0, the map, A_{R} : ℝ^{3} → ℝ^{3}, defined by A_{R}((a, b, c)) = (Ra, Rb, R^{2}c) is an automorphism of ℍ. It is also a homothety of the metric d^{ℍ}. The discrete Heisenberg group, ℍ(ℤ), is the integer lattice, ℤ^{3} = {(a, b, c) | a, b, c ∈ ℤ}, equipped with the above product. It is a discrete cocompact subgroup of ℍ. For further discussion of the Heisenberg group see Section 2.

Fix a finite set of generators T of a finitely generated group, Γ. The word metric d_{T} on Γ is the left invariant metric defined by stipulating that d_{T} (g_{1}, g_{2}) is the length of the shortest word in the elements of T and their inverses which expresses g_{1}^{−1}g_{2}. Up to bi-Lipschitz equivalence, the metric d_{T} is independent of the choice of generating set. For the case of ℍ(ℤ), we can take T = {(±1, 0, 0), (0, ±1, 0), (0, 0, ±1)}. For definiteness, from now on this choice will be understood. By an easy general lemma, given a free co-compact action of a finitely generated group Γ acting freely and cocompactly on a length space (X, d^{X}), the metric on Γ induced by the restriction to any orbit of the metric d^{X} is bi-Lipschitz equivalent to d_{T}; see [14]. For the case of ℍ(ℤ), we can take (X, d^{X}) = (ℍ, d^{ℍ}).

Define ρ : ℝ^{3} × ℝ^{3} → [0, ∞) by

(1.3) \begin{matrix}ρ( & (x, y, z), (t, u, v)) \\ := ([(\frac{(t − x)^{2} + (u − y)^{2}}{2} )^{2} + (v − z + xu − yt)^{2}]^{\frac{1}{2}} + \frac{(t − x)^{2} + (u − y)^{2}}{2} )^{\frac{1}{2}} . \end{matrix}

It was shown in [48] that (ℍ, ρ) is a metric of negative type bi-Lipschitz to (ℍ, d^{ℍ}).

It follows from [18] that

(1.4)  lim_{n→∞} c_{1} ({0, …, n}^{3}, ρ) = ∞ ,

but no information can be deduced on the rate of blow up as n → ∞. From Theorem 1.1 we get the following corollary, whose proof will be explained at the end of this subsection.

Corollary 1.5. For the constant δ > 0 in Theorem 1.1, we have for all n ∈ ℕ, metric spaces ({0, …, n}^{3}, ρ) of negative type, satisfying

(1.6)  c_{1} ({0, …, n}^{3}, ρ) ≳ (log n)^{δ} .

Remark 1.7. Since the metric spaces c_{1} ({0, …, n}^{3}, ρ) are of negative type, relation (1.6) implies that the integrality gap of the Goemans Linial relaxation of Sparsest Cut is ≳ (log n)^{δ} for δ > 0 as Theorem 1.1.

Remark 1.8. A metric space is said to be doubling if a metric ball B_{2r}(x), can be covered by at most N < ∞ metric balls of radius r, where N is independent of x, r. For n-point metric spaces, (X, d), which are doubling, the bound in Bourgain’s theorem can be sharpened to c_{1}(X, d) ⩽ c_{2}(X, d) ≲ \sqrt{log n}, which follows from the results of [8, 58]; see the explanation in [35]. The metric spaces, (ℍ, d^{ℍ}) and (ℍ(ℤ), d_{T}) are doubling. (To see this, use for example, the left invariance of d^{ℍ} and the homotheties A_{R}.) Before the bi-Lipschitz non-embeddability of ℍ into L_{1} was established in [18], there was no known example of a doubling metric space which does not admit a bi-Lipschitz embedding into L_{1}. Corollary 1.5 shows that there is a sequence of n-point doubling metric spaces for which c_{1}(X, d) ≳ (log n)^{δ}.

Remark 1.9. The behavior of the L_{2} distortion for n-point doubling metric spaces is much easier to understand than the L_{1} distortion. Namely, for fixed doubling constant, the above mentioned bound, c_{2}(X, d) ≲ \sqrt{log n} cannot be improved; see [46], and for dependence on the doubling constant, [42].

Given a finitely generated group Γ and a 1-Lipschitz function f : (Γ, d_{T}) → L_{1}, Gromov [32] defined the compression rate ω_{f} : [1, ∞) → [0, ∞) by:

ω_{f}(t) := inf {∥f(x) − f(y)∥_{L_{1}} | d_{T} (x, y) ⩾ t} .

Stated differently, ω_{f} is the largest non-decreasing function for which ∥f(x) − f(y)∥_{L_{1}} ⩾ ω_{f} (d_{T} (x, y)) for all x, y ∈ Γ.

It follows from [18] that for any 1-Lipschitz map f : ℍ(ℤ) → L_{1} we have lim inf \frac{ω_{f} (t)}{t} = 0, but [18] does not give any information on the rate at which \frac{ω_{f} (t)}{t} tends to zero. From Theorem 1.1 we can obtain the bound:

Corollary 1.10. For every f : ℍ(ℤ) → L_{1} which is 1-Lipschitz with respect to the word metric d_{W}, we have for arbitrarily large t:

(1.11)  ω_{f}(t) ≲ \frac{t}{(1 + log t)^{δ}} ,

where δ > 0 is the constant in Theorem 1.1.

Remark 1.12. A general result from [62] (see Corollary 5 there) implies that if an increasing function ω : [1, ∞) → [0, ∞) satisfies ∫_{1}^{∞} \frac{ω(t)^{2}}{t^{3}} dt < ∞ then there exists a mapping f : ℍ(ℤ) → L_{1} which is Lipschitz in the metric d_{T} and ω_{f} ≳ ω. In fact, f can be chosen to take values in the smaller space L_{2}. By choosing ω(t) = \frac{t}{\sqrt{1+log t}·log log(2+t)}, and bringing in Corollary 1.10, it follows that in the terminology of [7], the discrete Heisenberg group (ℍ(ℤ), d_{T}) has L_{1} compression gap

(\frac{t}{\sqrt{1 + log t} · log log(2 + t)}, \frac{t}{(1 + log t)^{δ}} ) .

It would be of interest to evaluate the supremum of those δ > 0 for which every Lipschitz function f : ℍ(ℤ) → L_{1} satisfies (1.11).

We close this subsection by explaining how Corollaries 1.10 and 1.5 are deduced from Theorem 1.1. A key point is to pass from the discrete settings of these corollaries to the continuous setting of Theorem 1.1 via a Lipschitz extension theorem. The basic idea is simple and general (see Remark 1.6 in [48]). Additionally, the homotheties A_{R}(a, b, c) = (Ra, Rb, R^{2}c) are used to convert information from Theorem 1.1 concerning small scales, into information concerning large scales. The existence of these homotheties is, of course, a special property of (ℍ, d^{ℍ}).

We will give the details for Corollary 1.10; the case of Corollary 1.5 is entirely similar.

Proof of Corollary 1.10. Fix a map f : ℍ(ℤ) → L_{1}, which is 1-Lipschitz with respect to the word metric d_{T}. The map f can be extended to a map f̃: ℍ → L_{1} whose Lipschitz constant with respect to d^{ℍ} satisfies Lip \binom{}{f} ≲ 1. This fact follows from the general result of [47], which states that such an extension is possible for any Banach space valued mapping from any doubling subset of a metric space to the entire metric space, but in the present simpler setting it also follows from a straightforward partition of unity argument.

Fix R > 1 and define g_{R} : B_{1}((0, 0, 0)) → L_{1} by g_{R}(x) = \frac{1}{R} f̃(δ_{R}(x)). Since d^{ℍ}(A_{R}(x), A_{R}(y)) = Rd^{ℍ}(x, y), Lip(g_{R}) ≲ 1. For ϵ ∈ (0, \frac{1}{4}), an application of Theorem 1.1 shows that there exist x, y ∈ ℍ such that R ≳ d^{ℍ}(x, y) ≳ ϵR, and

(1.13)  ∥f̃(x) − f̃(y)∥_{L_{1}} ≲ \frac{1}{(log(1/ϵ))^{δ}} · d^{ℍ}(x, y) .

Choose ϵ = \frac{1}{\sqrt{R}}. Since there exist a, b ∈ ℤ^{3} such that d^{ℍ}(a, x) ≲ 1 and d^{ℍ}(b, y) ≲ 1, and

since Lip \binom{}{f} ≲ 1, it follows from (1.13) that provided R is large enough,

ω_{f} (d_{W} (a, b)) ⩽ ∥f(a) − f(b)∥_{L_{1}} ≲ \frac{d^{ℍ}(a, b)}{(log R)^{δ}} ≲ \frac{d^{ℍ}(a, b)}{(log (d^{ℍ}(a, b)))^{δ}} ,

implying (1.11). □

2. The proof of Theorem 1.1; overview and background

We begin with an informal overview of the proof of Theorem 1.1. We then proceed to a more detailed discussion, including relevant background material.

Many known bi-Lipschitz non-embedding results are based in essence on a differentiation argument. Roughly, one shows that at almost all points, in the infinitesimal limit, a Lipschitz map converges to a map with a special structure. One then shows (which typically is not difficult) that maps with this special structure cannot be bi-Lipschitz. The term “special structure” means different things in different settings. When the domain and range are Carnot groups as in Pansu’s differentiation theorem [57], special structure means a group homomorphism. As observed in [48, 19], Pansu’s theorem extends to the case in which the domain is (ℍ, d^{ℍ}) and the target is an infinite dimensional Banach space with the Radon-Nikodym property, in particular, the target can be L_{p} for 1 < p < ∞.

The above approach fails for embeddings into L_{1}, since even when the domain is ℝ, Lipschitz maps need not be differentiable anywhere. A simple example is provided by the map t → χ_{[0,t]}, where χ_{[0,t]} denotes the characteristic function of [0, t]; see [4]. Nevertheless, the result on central collapse proved in [18] can be viewed as following from a differentiation theorem, provided one interprets this statement via a novel notion of “infinitesimal regularity” of mappings introduced in [18].

The approach of [18] starts out with the cut-cone representation of L_{1} metrics (see [27, 18]), which asserts that for every f : ℍ → L_{1} we can write

∥f(x) − f(y)∥_{L_{1}} = ∫_{2^{ℍ}} |χ_{E}(x) − χ_{E}(y)|dΣ_{f}(E) ,

for all x, y, where Σ_{f} is a canonically defined measure on 2^{ℍ} (see the discussion following (2.7) for precise formulations). The differentiation result of [18] can be viewed as a description of the infinitesimal structure of the measure Σ_{f}. It asserts that at most locations, in the infinitesimal limit, Σ_{f} is supported on vertical half spaces. This is achieved by first showing that the Lipschitz condition on f implies that Σ_{f} is supported on special subsets, those with finite perimeter. One then uses results on the local structure of sets of finite perimeter in the Heisenberg group to complete the proof; the argument is described in greater detail later in this section.

An alternative approach to this result on the infinitesimal behavior of Σ_{f}, which does not require the introduction of sets of finite perimeter, was obtained in [23]. This approach is based on the classification of monotone sets. A subset E ⊂ ℍ is called monotone if for every horizontal line L, up to a set of measure zero, E ∩ L is a sub-ray of the line. If we view ℍ = ℝ^{3}, the horizontal lines are a certain codimension 1 subset of all the lines; for details, see the subsection entitled “The Heisenberg group as a PI space”. The proof of [23] proceeds by showing that infinitesimally the measure Σ_{f} is supported on monotone subsets, and a non-trivial classification theorem which asserts that monotone subsets are half spaces. (The proof is recalled in Section 8.)

Our proof of Theorem 1.1 combines the methods of [18] and [23], with several significant new ingredients. Inspired by the proof in [23], our argument is based on an appropriately defined notion of almost monotonicity of subsets. But, unlike [23], we require the use of perimeter bounds as well. In our situation, perimeter bounds are used in finding a controlled scale such that at most locations, apart from a certain collection of cuts, the mass of Σ_{f} is supported on subsets which are sufficiently close to being monotone. In actuality, the excluded cuts may have infinite measure with respect to Σ_{f}. Nonetheless, using perimeter bounds and the isoperimetric inequality in ℍ, we show that their contribution to the metric is negligibly small.

A crucial, and by far the most complicated, new ingredient in this paper is a stability version of the classification of monotone sets of [23], which asserts that sets which are almost monotone are quantitatively close to half spaces. One of the inherent reasons for the difficulty of proving such a stability result arises from the need to work locally, i.e., to consider almost monotone subsets inside a metric ball in ℍ of finite radius. Here the situation is fundamentally different from the corresponding classification result in [23]: There are even precisely monotone subsets in such a ball which are not half spaces^{4}; see Example 9.1. Inevitably, our classification result must take this complication into account. We can only assert that on a (controllably) smaller ball, the given almost monotone subset is close to a half space.

In order to make the above informal description precise, we will require some additional preliminaries, which are explained in the remainder of this introduction. For a discussion, in a wider context, of estimates whose form is equivalent to that of (1.2), and which arise from our general mechanism, see Appendix 2, Section 14. Remark 2.1. As we explained above, the present paper belongs to the general topic of controlling the scale at which the infinitesimal “special structure” of a mapping (arising from a differentiation theorem) appears in approximate form. However, it is important to realize that it is impossible in general to obtain a quantitative estimate for the rate at which the limiting situation is approached. To see this point, consider a model problem associated to the sequence of functions f_{n}(x) = \frac{sin(nx)}{n}. Although |f′_{n}(x)| ⩽ 1, for all n ∈ ℕ and x ∈ ℝ, it is not possible control independently of n the difference between f_{n} and its first order Taylor polynomial; note that f′′_{n}, which controls the remainder term, is not bounded independently of n. Nonetheless, there is an explicit uniform estimate for the scale above which any f_{n} is approximated by some linear function, which might not be equal to its first order Taylor series. As far as we are aware, the first instance of a result of this type is in [40]; see also for example [11], and for additional information, the appendix by Semmes in [33].

PI spaces. A natural setting for a large part of our work is that of PI spaces: a certain class of metric measure spaces, of which the Heisenberg group is a member. Together with the key concept of “upper gradient” on which their definition is based, these spaces were introduced in [38].

Let (X, d^{X}) denote a metric space. If f : X → ℝ, then g : X → [0, ∞] is called an upper gradient of f, if for all rectifiable curves c : [0, ℓ] → X, parameterized by arc length,

(2.2)  |f(c(ℓ)) − f(c(0))| ⩽ ∫_{0}^{ℓ} g(c(s)) ds .

4 In ℝ^{n}, monotone subsets of a ball are necessarily the intersection of the ball with a half space.

A complete metric measure space (X, d^{x}, μ) is called a PI space if a doubling condition and Poincaré inequality hold. Thus, there exists p ⩾ 1 and for all R > 0 there exist β = β(R), τ = τ(R), Λ = Λ(R), such that for all x ∈ X and r ⩽ R we have:

(2.3)  μ(B_{2r}(x)) ⩽ β · μ(B_{r}(x)) ,

(2.4)  − ∫_{B_{r}(x)×B_{r}(x)} |f(x_{1}) − f(x_{2})| d(μ × μ)(x_{1}, x_{2}) ⩽ τ · r · (− ∫_{B_{Λr}(x)} g^{p} dμ)^{\frac{1}{p}} ,

where we use the notation:

− ∫_{U} h dμ = \frac{1}{μ(U)} ∫_{U} h dμ .

As shown in [36], (2.3) and (2.4) imply a strengthening of (2.4), which we will need. Namely, for some χ = χ(β, τ) > 1, τ′ = τ′(β, τ), one has the Poincaré-Sobolev inequality,

(2.5)  (− ∫_{B_{r}(x)×B_{r}(x)} |f(x_{1}) − f(x_{2})|^{χp}d(μ × μ)(x_{1}, x_{2}))^{\frac{1}{χp}} ⩽ τ′ · r · (− ∫_{B_{Λr}(x)} g^{p} dμ)^{\frac{1}{p}} .

It is important that for the case of the Heisenberg group of dimension 2n + 1, relation (2.5) holds with p = 1, χ = \frac{2n+2}{2n+1}; thus if 2n + 1 = 3, then χ = \frac{4}{3}.

Observe that (2.4), for fixed p, implies (2.4) for any p′ > p. In this paper, without further explicit mention, we will always assume that p = 1, which is necessary for the ensuing results on finite perimeter. Solely in order to have one fewer constant to list, we will also make the innocuous assumption that Λ = 1. For the cases of primary interest here, X = ℝ^{n} or X = ℍ, relation (2.5) does hold with Λ = 1 and as noted above, with p = 1.

Maps to L_{1}: cut metrics and cut measures. Let X denote a set and let E ⊂ X denote a subset. In place of “subset”, we will also use the term “cut”. If E ⊂ X, then associated to E is a so-called elementary cut metric, denoted d_{E}, on X, where by definition, d_{E}(x_{1}, x_{2}) = 0 if either x_{1}, x_{2} both lie in E, or if x_{1}, x_{2} both lie in E′ (here, and in what follows, we denote E′ = X \ E). Otherwise, d_{E}(x_{1}, x_{2}) = 1.

Remark 2.6. Clearly, d_{E} = d_{E′}. For this reason, it is common to define the space of cuts of X as the quotient of the power set 2^{X} by the involution, E ↦ E′, although we don’t do this here.

By definition, a cut metric d_{Σ} is an integral of elementary cut metrics with respect to some measure Σ on 2^{X}. Thus,

(2.7)  d_{Σ}(x_{1}, x_{2}) = ∫_{2^{X}} d_{E}(x_{1}, x_{2}) dΣ(E) .

For f : U → L_{1}, the pull-back metric induced by f is defined as d_{f}(x_{1}, x_{2}) = ∥f(x_{1}) − f(x_{2})∥_{1}. It follows from the “cut-cone characterization” of L_{1} metrics (see [27, 18]) that there is a canonically defined measure Σ_{f} on 2^{X} (on an associated sigma algebra) such that (2.7) holds with Σ = Σ_{f}.

Now let (X, μ) denote a σ-finite measure space. Let U ⊂ X denote a measurable subset and f : U → L_{1}(Y, ν) be a map which satisfies:

∫_{U} ∥f(x)∥_{1} dμ < ∞ .

There is a variant of the description of d_{f} in terms of Σ_{f} in the L_{1} framework; see [18]. In this context, 2^{U} is replaced by a measure theoretic version of the space of cuts. One should regard a cut as an equivalence class of measurable sets E ⊂ U of finite μ-measure, where two sets are considered equivalent if their symmetric difference has measure zero. The collection of such cuts may be identified with the subset of L_{1}(U) consisting of characteristic functions. Hence it inherits a topology and a Borel structure from L_{1}(U). For our purposes, there is no harm in blurring the distinction between measurable sets and their equivalence classes, which for purposes of exposition, is done below.

Let Cut(U) denote the space of cuts. As above, we have:

(2.8)  d_{f}(x_{1}, x_{2}) = ∫_{Cut(U)} d_{E}(x_{1}, x_{2}) dΣ_{f}(E) ,

where Σ_{f} is a suitable σ-finite Borel measure on Cut(U). Here we view d_{f} as an element of L_{1}^{loc}(U × U), whose restriction to any subset V ⊂ U, with finite measure, lies in L_{1}(V × V). Given two such L_{1}-metrics d_{1}, d_{2} ∈ L_{1}(V × V) there is a well-defined L_{1}-distance, denoted ∥d_{1} − d_{2}∥_{L_{1}(V ×V)}, given by:

(2.9)  ∥d_{1} − d_{2}∥_{L_{1}(V ×V)} = ∫_{V ×V} |d_{1}(x_{1}, x_{2}) − d_{2}(x_{1}, x_{2})| d(μ × μ)(x_{1}, x_{2}).

It is shown in [18], that if X is a PI space, U ⊂ B_{1}(p) ⊂ X is an open set, and f is 1-Lipschitz, or more generally, 1-BV, then the cut measure Σ_{f} has finite total perimeter:

(2.10)  ∫_{Cut(U)} Per(E)(U) dΣ_{f}(E) = ∫_{Cut(U)} PER(E, U) dΣ_{f}(E) < c(β, τ).

Intuitively, for U open, the perimeter, PER(E, U), is the codimension 1 measure of the (measure theoretic) boundary of E inside U. In actuality, U → PER(E, U) defines a Borel measure Per(E). The restriction of this measure to Borel subsets of U is denoted Per(E, U). The mass of Per(E, U) is denoted PER(E, U) and is equal to Per(E)(U); for the definition, see (3.5). Moreover, there is a total perimeter measure, λ_{f}, which is a Radon measure on U, such that

(2.11)  λ_{f} = ∫_{Cut(U)} Per(E, U) dΣ_{f}(E) ,

(2.12)  Mass(λ_{f}) = λ_{f}(U) = ∫_{Cut(U)} PER(E, U) dΣ_{f}(E) .

In particular, if f has bounded variation (f ∈ BV) then Σ_{f} is supported on cuts with finite perimeter. For the precise definitions and relevant properties of cut measures, BV maps and perimeter measures, see [18].

The Heisenberg group as a Lie group. Recall that the 3-dimensional Heisenberg group ℍ, can be viewed as ℝ^{3} equipped with the group structure

(2.13)  (a, b, c) · (a′, b′, c′) = (a + a′, b + b′, c + c′ + ab′ − ba′) .

Note that the inverse of (a, b, c) is (−a, −b, −c). The center Center(ℍ) consists of the 1dimensional subgroup {0} × {0} × ℝ. There is a natural projection π : ℍ → ℍ/Center(ℍ) = ℝ^{2} and the cosets of the center are just vertical lines in ℝ^{3}, i.e., lines parallel to the z-axis.

Since the correction term, ab′ − a′b, in (2.13), which measures the failure of the multiplication to be commutative, can be viewed as a determinant, we get the following very useful geometric interpretation:

(∗) The correction term, ab′ − a′b, is the signed area of the parallelagram spanned by the vectors π((a, b, c)), π((a′, b′, c′)).

(∗∗) Equivalently, if we regard ℝ^{3} as ℝ^{2} × ℝ, then ab′ − a′b is the standard symplectic form, ω, on ℝ^{2}.

Let K : ℝ^{2} → ℝ^{2} be an invertible linear transformation and set

(2.14)  A_{K}(a, b, c) := (K(a, b), (det K) · c) .

It is easily checked that A_{K} is an automorphism of ℍ.

Let H_{g} denote affine plane passing through g ∈ ℍ, which is the image under left multiplication by g ∈ ℍ, of the subspace ℝ^{2} × {0} ⊂ ℍ. We call H_{g} the horizontal 2-plane at g ∈ ℍ. Since the automorphism A_{K} preserves the subspace ℝ^{2} × {0} ⊂ ℍ_{e}, where ℍ_{e} denotes the tangent space at the identity e = (0, 0, 0), it follows that A_{K} maps horizontal subspaces to horizontal subspaces. The collection {H_{g}}_{g∈ℍ} defines a left-invariant connection on the principle bundle, ℝ → ℍ → ℝ^{2}, which in coordinates, has the following explicit description.

The plane H_{(0,0,0)} is given by (u, v, 0) where u, v take arbitrary real values. In general,

H_{(a,b,c)} = (a, b, c)(u′, v′, 0) = (a + u′, b + v′, c − bu′ + av′),

so putting a + u′ = u, b + v′ = v, we get

(2.15)  H_{(a,b,c)} = (u, v, c + av − bu) .

The affine 2-planes in ℝ^{3} whose projections to ℝ^{2} are surjective are just those which admit a parameterization (u, v, c+av −bu). It follows that every such 2-plane arises as the horizontal 2-plane associated to a unique point (a, b, c), and conversely, that every horizontal 2-plane associated to some point in ℝ^{3} projects surjectively onto ℝ^{2}.

A line in ℝ^{3}, which passes through the point (a, b, c), and lies in the plane H_{(a,b,c)}, can be written

(2.16)  L = (a, b, c) + t(u, v, −bu + av) t ∈ ℝ ,

where u, v are fixed and t varies. In discussing the Heisenberg case, unless otherwise indicated, the term line will refer exclusively to such a horizontal line. The collection of all such lines is denoted lines(ℍ).

Definition 2.17. A half-space P ⊂ ℍ = ℝ^{3} is the set of points lying on one side of some 2-plane P, including those points of the plane itself.

The half-space H is called horizontal if its associated 2-plane H is horizontal. Otherwise it is called vertical. Thus, a vertical half-space is the inverse image under π of an ordinary half plane in ℝ^{2}.

The Heisenberg group as a PI space. Consider the left-invariant Riemannian metric ⟨ · , · ⟩ on ℍ which corresponds to the standard Euclidean metric at the tangent space to the identity. The Carnot-Carathéodory distance d^{ℍ}(x_{1}, x_{2}) is defined to be the infimum of lengths of curves c : [0, ℓ] → ℍ, from x_{1} to x_{2}, such that for all s, the tangent vector c′(s) is horizontal i.e. c′(s) lies in the 2-dimensional subspace of the tangent space corresponding to the affine plane H_{c(s)}. The length of c′(s) is calculated with respect to ⟨ · , · ⟩. In particular, one sees that for all g_{1}, g_{2} ∈ ℍ,

(2.18)  d^{ℍ}(g_{1}, g_{2}) = d^{ℍ} (g_{1}^{−1}, g_{2}^{−1}) .

A well known consequence (see [56]) of the definition of d^{ℍ}, in combination with (∗), (∗∗) above, is that if p, q ∈ ℍ, whith π(p) = π(q), and c : [0, ℓ] → ℝ^{2} is a curve parametrized by arc length such that its horizontal lift c̃ starts at p and ends at q, then the vertical separation of p and q (in coordinates) is the signed area enclosed by the curve c.

Geodesics of d^{H} can be characterized as those smooth horizontal curves which project (locally) either to a circular arc or to a line segment in ℝ^{2}. Thus, the lines L ∈ lines(ℍ) are precisely those geodesics of d^{ℍ} which are affine lines in ℍ = ℝ^{3}. Any two points of ℍ can be joined by a minimal geodesic of d^{ℍ}, although typically, not by a horizonal line L ∈ lines(ℍ). Note that when viewed as a curve in (ℍ, d^{ℍ}), any affine line which is not a member of lines(ℍ) has the property that any of its finite sub-segments has infinite length.

The distance d^{ℍ} ((a, b, c), (a′, b′, c′)), is bounded above and below by a constant multiple of

(2.19)  ((a − a′)^{2} + (b − b′)^{2})^{\frac{1}{2}} + |c − c′ + ab′ − ba′|^{2} .

When restricted to any vertical line is just the square root of the coordinate distance. Thus, there is a constant C > 0 such that for the metric d^{ℍ}, the metric ball about e = (0, 0, 0) satisfies the box-ball principle:

(2.20)  B_{C^{−1}r}(e) ⊂ \{(a, b, c) | |a| < r, |b| < r, |c| < r^{\frac{1}{2}} \} ⊂ B_{Cr}(e) .

Thus, in coordinates, B_{r}(e) looks roughly like a cylinder whose base has radius r and whose height is 2r^{2}.

In this paper we will consider the PI space (ℍ, d^{ℍ}, L_{3}), where L_{3} denotes Haar measure on ℍ, which coincides with the Lebesgue measure on ℝ^{3}.

Let r_{θ} denote rotation in ℝ^{2} through an angle θ and let I denote the identity on ℝ^{2}. From now on we write O_{θ} for A_{r_{θ}}. Since O_{θ} preserves horizontal subspaces and induces an isometry on H_{e} = ℝ^{2} × {0}, it follows that O_{θ} is an isometry of (ℍ, d^{ℍ}). Clearly, O_{θ} preserves the measure L_{3} as well. Similarly, for ψ ∈ ℝ, the automorphism A_{ψI} scales the metric by a factor ψ and the measure L_{3} by a factor ψ^{4}; see (2.14).

Behavior under blow up of finite perimeter cuts of ℍ. Let E ⊂ B_{1}(e) ⊂ ℍ denote a finite perimeter (FP) cut. Then at Per(E)-a.e. p ∈ E, asymptotically under blow up, the measure of the symmetric difference of E and some vertical half-space V, goes to zero; see [29], [30]. Equivalently, the indicator χ_{E} converges to χ_{V} in the L_{1}^{loc} sense. The corresponding theorem for ℝ^{n} is due to De Giorgi [25], [26]. The results of [29], [30] depend essentially on those of [1], [2], in which an asymptotic doubling property for the perimeter measure is proved for arbitrary PI spaces.

If d_{V} is an elementary cut metric associated to a vertical half-space then the restriction of d_{V} to a coset of the center is trivial. Thus, the results of [29], [30], together with (2.7), suggest that under blow up, at almost all points, a Lipschitz map f : ℍ → L_{1} becomes degenerate in the direction of (cosets of) the center. In particular, there exists no bi-Lipschitz embedding of ℍ in L_{1}. This is the heuristic argument behind the main result of [18].

In order to prove Theorem 1.1, we will take a different approach, leading to a quantitative version of a somewhat crude form of the blow up results of [29], [30] (and the corresponding earlier results of [25], [26]). Here, “crude” means that our argument does not give uniqueness of the blow up, nor in the Heisenberg case, does it show that only vertical half-spaces arise. [30]. For our purposes, neither of these properties is needed. Our approach is based on the notion of monotone sets as introduced [23]; the discussion there, while not quantitative, does recover the results on verticality and uniqueness of blow ups.

Monotone sets and half-spaces. In the definition that follows and elsewhere in this paper, E′ denotes the complement of E.

Definition 2.21. Fix an open set U ⊆ ℍ. Let lines(U) denote the space of unparametrized oriented horizontal lines whose intersection with U is nonempty. Let N_{U} denote the unique left invariant measure on lines(ℍ), normalized so that N_{U}(lines(U)) = 1. A subset E ⊆ U is monotone with respect to U if for N_{U}-almost every line L, both E ∩ L and (U \ E) ∩ L are essentially connected, in the sense that there exist connected subsets F_{L} = F_{L}(E), F′_{L} = F′_{L}(E) ⊆ L (i.e., each of F_{L}, F′_{L} is either empty, equals L, or is an interval, or a ray in L) such that the symmetric differences (E ∩ L)△F_{L} and ((U \ E) ∩ L)△F′_{L} have 1-dimensional Hausdorff measure 0.

Monotone subsets of ℍ were introduced in [23] where they were used to give a relatively short proof of the non-embedding theorem of [18], which does not require the introduction of FP sets and hence, does not depend on [29], [30]. Instead, a blow up argument is used to directly reduce the nonembedding theorem to the special case in which the cut measure Σ_{f} is supported on monotone cuts; compare the discussion in the next subsection. For the case U = ℍ, a nontrivial classification result asserts that if E is monotone, then L_{3}(E△P) = 0 for some half-space P; see [23].

Remark 2.22. If we regard ℍ as ℝ^{3}, then horizontal lines in ℍ are a particular codimension 1 subset of the set of all affine lines in ℝ^{3}. A typical pair of points lies on no horizontal line. However, the classification of monotone subsets of ℍ is precisely the same as for ℝ^{3} with its standard metric. In the latter case, the proof is trivial while in the former case it is not.

Degeneracy of cut metrics which are supported on half-spaces. Once monotone subsets are known to be half-spaces it follows (after the fact) that the connectedness condition in Definition 2.21 holds for almost every affine line \underline{L}, i.e., not just for horizontal ones. Thus, if a cut measure Σ is supported on monotone cuts, d_{Σ} has the property that if x_{1}, x_{2}, x_{3} ∈ \underline{L} and x_{2} lies between x_{1} and x_{3}, then d_{Σ}(x_{1}, x_{3}) = d_{Σ}(x_{1}, x_{2}) + d_{Σ}(x_{2}, x_{3}). But if \underline{L} is not horizontal, i.e., a coset of the center, then d^{ℍ}|\underline{L} is comparable to the square root of the coordinate distance, and it is trivial to verify that this metric is not bi-Lipschitz to one with the property mentioned above; see (4.1).

In proving Theorem 1.1, we will show that on a definite scale, using Theorem 4.13, we can reduce modulo a controlled error, to the case in which the cut measure is supported on cuts which are close to half-spaces. The error term, though controlled, is larger than the term which corresponds to the model case of monotone cuts.

δ-monotone sets. Theorem 4.13, which asserts that an approximately monotone set is close to some half-space (in the sense that the symmetric difference has small measure) plays a key role in the proof of Theorem 1.1. But unlike in [23], we cannot dispense with consideration of FP sets. We use (2.10), the bound on the total perimeter, to obtain a bound on the total nonmonotonicity, and hence, to get the estimate for a scale on which the total nonmonontonicity is so small that Theorem 4.13 applies; see the discussion after Theorem 1.1 and compare Remark 2.23 below.

Remark 2.23. If one restricts attention to 1-Lipschitz maps f : B → L_{1}, rather than more general BV maps, then using the fact that the 1-Lipschitz condition is preserved under restriction to horizontal lines, it is possible to derive the above mentioned bound on the total nonmonotonicity without reference to FP sets. However, even for Lipschitz maps, the introduction of FP sets cannot be avoided; see Lemma 4.2 which concerns an issue arising from the fact that the mass of the cut measure can be infinite; see also Proposition 5.2.

We will need to consider subsets, E ⊂ B_{R}(p) ⊂ ℍ, which are δ-monotone on B_{R}(p); see Definition 4.11. Here, small δ means approximately monotone, and δ = 0 corresponds to the case of monotone sets as in Definition 2.21. After rescaling, Theorem 4.13 states that there exists a constant a < ∞, such that if E ⊂ B_{R}(p) ⊂ ℍ is ϵ^{a}-monotone, and R ⩾ ϵ^{−3}, then L_{3}((E ∩ B_{1}(p))△(P ∩ B_{1}(p))) ≲ ϵ, for some half-space P.

Remark 2.24. Absent the assumption R ⩾ ϵ^{−3}, the conclusion of Theorem 4.13 can fail, even if “ϵ^{a}-monotone” is replaced by “monotone”; see Example 9.2. For the analogous result in ℝ^{n}, ϵ^{−3} can indeed be replaced by 1.

Remark 2.25. The discussion of monotone sets can be formulated for arbitrary PI spaces; see [22]. But in general, monotone subsets need not be rigid. In [21], the flexibility of monotone subsets of Laakso spaces [45] is used to construct bi-Lipschitz embeddings of Laakso spaces into L_{1}. This is of interest since these spaces do not admit a bi-Lipschitz embedding into any Banach space with the Radon-Nikodym Property, e.g., separable dual spaces, such as L_{p}, 1 < p < ∞ or ℓ_{1}; see [20].

The kinematic formula; perimeter and nonmonotonicity. To bound the total nonmonotoncity in terms of the total perimeter, we use a kinematic formula for the perimeter of an FP set. From now on, we will just refer to the kinematic formula. In ℝ^{n}, the kinematic formula expresses the perimeter of an FP set E, as an integral with respect to the natural measure on the space of lines L, of the 1-dimensional perimeter function PER(E∩L). In [55], a suitable kinematic formula is been proved for Carnot groups; see (6.1). In that context, a line means a horizontal line L ∈ lines(ℍ).

Up to a set of measure zero, an FP subset of ℝ is a finite union of disjoint closed intervals for any open interval, I, the perimeter, PER(E, I), is the number of end points of these intervals which are contained in I; see [3]. On the other hand, the condition that E is monotone can be reformulated as the requirement that for almost every line L, the 1-dimensional perimeter PER(E ∩ L) is either 0 or 1. Since our initial quantitative data provides an integral bound on the mass of the total perimeter measure (see (2.10), (3.14)) it is not surprising that the kinematic formula plays a key role in our discussion.

3. Preliminaries

In this section, X denotes a PI space. In particular, it could by ℝ^{n} or ℍ. Fix p ∈ X and let f : B_{r}(p) → L_{1} denote a Lipschitz map. In this paper we will often rescale this ball to unit size and correspondingly rescale the map f, and hence, the induced metric, d_{Σ_{f}}, or equivalently, the cut measure. Finally, we rescale the measure, μ, so that the rescaled ball has unit measure.

We set

(3.1)  f̆ = r^{−1}f ,
(3.2)  Σf̆ = r^{−1} · Σ_{f} ,
(3.3)  d̆^{X} = r^{−1} · d^{X} ,

(3.4)  μ̆( ·) = \frac{μ( ·)}{μ(B_{r}(p))} .

For the case Lipschitz maps, we always use the full set of rescalings (3.1)–(3.4).

Note that for U open, Per(E)(U) is defined by:

(3.5)  Per(E)(U) = inf_{{h_{i}}} lim inf_{i} ∫_{U} Lip(h_{i})dμ ,

where the infimum is taken over all sequences of Lipschitz functions {h_{i}}_{i=1}^{∞}, with h_{i} ⟶^{L_{1}^{loc}} χ_{E}. Since rescaling as in (3.3), has the effect,

(3.6)  Lip(h_{i}) → r · Lip(h_{i}) ,

it follows that (3.3), (3.4), imply

(3.7)  Per(E) → r · \frac{1}{μ(B_{r}(p))} · Per(E) .

Remark 3.8. When generalizing our considerations to BV functions, or in particular, sets of finite perimeter, it is of interest to consider as well, the effect of rescaling as in (3.3), (3.4), with (3.1), (3.2) omitted. If (3.1), (3.2), are omitted, then (3.7) is a relevant rescaling. For the case of FP sets in particular, it is the relevant rescaling. It can be used to give a quantitative analog of Theorem 1.1 for a single FP set, E, in which the set of points at which on a controlled scale, E is not close to a half-space, has small codimension 1 Hausdorff content, as measured with respect to coverings by balls of small radius.

If (3.1), (3.2), are not omitted then by (3.2), (3.7), the corresponding rescaling factor for the total perimeter measure, λ_{f}, is r · \frac{1}{μ(B_{r}(p))} · r^{−1}, i.e.,

(3.9)  λ_{f} → \frac{1}{μ(B_{r}(p))} · λ_{f} .

Normalization. After rescaling f, Σ_{f}, d^{X}, μ, as in (3.1)–(3.4), we will often denote the rescaling of the ball, B_{r}(x) as B̆_{r}(x). Thus,

(3.10)  B̆_{r}(x) ⊂ X ,
(3.11)  μ̆ (B̆_{r}(x)) = 1 ,

(3.12)  f̆: B̆_{r}(x) → L_{1} ,
(3.13)  Lip \binom{}{f̆} = 1 ,

or more generally,

(3.14)  ∫_{Cut(B̆_{r}(x))} Per(E) (B̆_{r}(x)) dΣf̆(E) ⩽ 1 .

Standard inequalities. We will make repeated use of the trivial inequality (often called Markov’s inequality), which states that for a measure space (Y, ν) and f ∈ L_{1}(Y, ν), one has

(3.15)  ν({x | f(x) ⩾ t}) ⩽ t^{−1} ∫_{Y} |f| dν .

We also use the weak-type (1,1) inequality for the maximal function, which is a consequence of the doubling property of the measure; see e.g. Chapter 1 of [61]. We now recall this basic estimate.

Let β denote the doubling constant of μ. Let ζ denote a Radon measure. Fix an open subset U and let C denote the collection of closed balls \overline{B_{r}(y)} such that \overline{B_{5r}(y)} ⊂ U. Given k, j ∈ ℕ, define B_{j,k} = B_{j,k}(ζ) ⊂ C, by

(3.16)  B_{j,k} := \{\overline{B_{r}(y)} ∈ C | ζ (\overline{B_{r}(y)}) ⩾ kr^{−j} · μ (\overline{B_{r}(y)})\} .

and set

(3.17)  B_{j,k} = ⋃_{\overline{B_{r}(q)}∈B_{j,k}} \overline{B_{r}(q)} .

By the standard covering argument (see [61, 37]), there is a dsijoint sub-collection {B_{r_{i}}(q_{i})}_{i=1}^{∞} ⊂ B_{j,k}, such that

(3.18)  B_{j,k} ⊂ ⋃_{i=1}^{∞} \overline{B_{5r_{i}}}(q_{i}) ,

(3.19)  ∑_{i=1}^{∞}(5r_{i})^{−j} · μ(\overline{B_{5r_{i}}(q_{i})}) ⩽ 5^{−j}k^{−1} · β^{3} · ζ(U) .

Relations (3.18), (3.19), imply that the codimension j Hausdorff content of B_{j,k} (as defined with respect to the measure μ) is bounded by 5^{−j}k^{−1}·β^{3}·ζ(U). The codimension 0 Hausdorff content (j = 0) is just the measure μ itself.

4. Reduction to the stability of individual monotone sets

In this section we reduce the proof of the main degeneration theorem, Theorem 1.1, to Theorem 4.13, a stability theorem for individual monotone sets, which states roughly, that a set which is almost monotone is almost a half space. The complete proof of Theorem 4.13 will occupy Sections 7–11.

The next few paragraphs contain an overview of this section. For definiteness, we will restrict attention to the Heisenberg group. Everything we say applies, mutadis mutandis, to the simpler case of ℝ^{n} as well.

We begin by considering an ideal case, the proof of which is given prior to the more general Proposition 4.14. Then we explain how to reduce to ideal case up to an error which is controlled.

Let d_{P} denote a cut metric for which the cut measure is supported on cuts P which are half-spaces. Let ϵ > 0. We will see by an easy argument that for every line \underline{L} line through the identity, e ∈ ℍ, which makes an angle ⩾ θ > 0 with the horizontal plane, for half^{5} of the pairs of points x_{1}, x_{2} ∈ \underline{L}, with \frac{1}{2}ϵ ⩽ d^{ℍ}(x_{1}, x_{2}) ⩽ \frac{3}{2}ϵ, we have

(4.1)  d_{P}(x_{1}, x_{2}) ≲_{θ} ϵ · d^{ℍ}(x_{1}, x_{2}) ,

where the implied constant in (4.1) depends only on θ.

In proving Theorem 1.1, we first find a scale such that at a typical location, the support of the cut measure consists almost entirely of cuts which are almost half-spaces, i.e., cuts which differ from half-spaces by sets of small measure. As explained below, for this, it suffices to find a scale on which the total nonmonotonicity is small. By the pigeon hole principle, it is easy to find a scale on which the total perimeter is small. On such a scale we apply Proposition 4.28, which asserts that total nonmonotonicity of a cut metric can be bounded in terms of the the total perimeter. Proposition 4.28 is proved in Section 6.

5The measure on pairs x_{1}, x_{2}, with \frac{1}{2}ϵ ⩽ d^{ℍ}(x_{1}, x_{2}) ⩽ \frac{3}{2}ϵ, is L × L where L denotes Lebesgue measure associated to the Euclidean metric on \underline{L}. Of course, in the statement, “half” can be replaced by any definite fraction < 1, provided ≲_{θ} in (4.1) is allowed to depend on that fraction.

On a scale on which the total nonmonotonicity is small, the effect of cuts which are not almost half-spaces can be absorbed into the error term, after which they can be ignored. However, to get to a situation in which our conclusion can be obtained by appying Theorem 4.13, we must further reduce to one in which there is a suitable bound on the mass of the cut measure. Otherwise, the total effect of the small deviations of the remaining individual cuts from being half-spaces could carry us uncontrollably far from the ideal case considered in (4.1). This point is addressed in Lemma 4.2, which states that the cuts can be decomposed into a subset which makes a contribution which can be absorbed into the error term for the cut metric, and one for which the mass has a definite bound. Lemma 4.2 is proved in Section 5.

Controlling the cut measure. The following lemma will be applied to rescaled balls, on a scale on which the total nonmonoticity is sufficiently small. For f Lipschitz, relation (4.3) in the hypothesis of Lemma 4.2 holds for all such balls. If more generally f is BV, then for most such balls, it holds after suitably controlled rescaling.

Given metrics, d, d′, define ∥d − d′∥_{L^{1}} as in (2.9).

Lemma 4.2. Let f : B_{1}(p) → L_{1} satisfy

(4.3)  λ_{f}(B_{1}(p)) ⩽ 1 .

Given η > 0, the support of Σ_{f} can be written as a disjoint union D_{1} ∪ D_{2}, such that if d_{f} = d_{1} + d_{2} denotes the corresponding decomposition of the cut metric d_{f}, then

(4.4)  Σ_{f}(D_{1}) ⩽ η^{−3} ,
(4.5)  ∥d_{f} − d_{1}∥_{L_{1}} ≲ η .

If f is 1-Lipschitz, then so are d_{1}, d_{2}.

Lemma 4.2 is a consequence of the more general Proposition 5.2 which is proved in Section 5.

Stability of monotone sets. Let lines(ℍ) denote the space of unparameterized oriented horizontal lines, and let lines(U) denote the collection of horizontal lines whose intersection with U is nonempty. Let N denote the unique left-invariant measure on lines(ℍ), normalized so that

(4.6)  N (lines(B_{1}(e)) = 1 .

Let H_{L}^{1} denote 1-dimensional Hausdorff measure on L ∈ lines(ℍ) with respect to the metric induced from d^{ℍ}. We note that if E ⊂ ℍ is measurable, then L ∩ E is measurable for N -a.e. L ∈ lines(ℍ).

Given a ball B_{r}(x) ⊂ ℍ and L ∈ lines(B_{r}(x)), we define the nonconvexity of (E, L) on B_{r}(x), denoted NC_{B_{r}(x)}(E, L), by

(4.7) NC_{B_{r}(x)}(E, L) := inf {∫_{L∩B_{r}(x)} |χ_{I} − χ_{E∩L∩B_{r}(x)}| dH_{L}^{1} | I ⊂ L ∩ B_{r}(x) subinterval} ,

where we allow in the infimum above the subinterval I to be empty. Similarly, we define the nonmonotonicity of (E, L) on B_{r}(x) by

(4.8)  NM_{B_{r}(x)}(E, L) := NC_{B_{r}(x)}(E, L) + NC_{B_{r}(x)}(E′, L) .

The total nonconvexity and total nonmonotonicity of E on B_{r}(X) are defined to be the following (scale invariant) quantities:

(4.9)  NC_{B_{r}(x)}(E) := \frac{1}{r^{4}} ∫_{lines(B_{r}(x))} NC_{B_{r}(x)}(E, L) dN (L) ,

(4.10)  NM_{B_{r}(x)}(E) := \frac{1}{r^{4}} ∫_{lines(B_{r}(x))} NM_{B_{r}(x)}(E, L) dN (L) ,

Note that NM_{B_{r}(x)}(E) = 0 if E is monotone, or more generally if the the symmetric difference of E and some monotone subset has measure zero.

Definition 4.11. A cut E ⊂ B_{r}(p) ⊂ ℍ is said to be δ-monotone on B_{r}(x) if

(4.12)  NM_{B_{r}(x)}(E) < δ .

We have the following stability theorem.

Theorem 4.13. There exists a > 0 (e.g., a = 2^{52} works here), such that if the cut E ⊂ B_{1}(x) is ϵ^{a}-monotone on B_{1}(x), then there exists a half-space P ⊆ ℍ such that

\frac{L_{3} ((E ∩ B_{ϵ^{3}}(x))△P)}{L_{3} (B_{ϵ^{3}}(x))} ≲ ϵ .

Cut measures supported on cuts which are almost half-spaces. In this subsection, we begin by verifying (4.1), which concerns the case of a cut measure which is supported on halfspaces. Then we consider in Proposition 4.14, the more general case of a cut measure which is supported on cuts which are almost half-spaces, i.e., cuts that satisfy the the conclusion of Theorem 4.13. Of course, there is an error term in the general case, which leads to a weaker estimate than in the ideal case.

Proof of (4.1). For simplicity, we just consider pairs of points, x_{1}, x_{2}, with d^{ℍ}(x_{1}, x_{2}) = ϵ. For d^{ℍ}(x_{1}, x_{2}) = t, with t ∈ [\frac{1}{2}ϵ, \frac{3}{2}ϵ], the proof is the same.

Consider first an elementary cut metric d_{E} on the real line, associated to a subset E such that E and E′ are connected. Clearly, if x_{3} lies between x_{1} and x_{2}, then

d_{E}(x_{1}, x_{3}) + d_{E}(x_{3}, x_{2}) = d_{E}(x_{1}, x_{2}) .

By linearity, this holds more generally for cut metrics on the line whose cut measures are supported on such cuts.

Let Σ_{P} denote a cut measure on B_{1}(p) ⊂ ℍ such that every cut in the support of Σ_{P} is of the form P ∩ B_{1}(p), for some half-space P. Then for almost every affine (not necessarily horizontal) line \underline{L}, the restriction d_{P}|\underline{L} is a cut metric as in the previous paragraph.

Consider a subinterval I ⊂ \underline{L} ∩ B_{1}(p) with end points y, z such that say d^{ℍ}(y, z) = \frac{1}{2} and hence, L(I) ⩾ \frac{1}{4}.. Let ϵ be as in (4.1) and let ψ > 0 be arbitrary. Let α index those intervals J_{α} ⊂ I whose end points x_{1,α}, x_{2,α} satisfy d^{ℍ}(x_{1,α}, x_{2,α}) = ϵ, and such that d_{P}(x_{1,α}, x_{2,α}) ⩾ ψ · d^{ℍ}(x_{1,α}, x_{2,α}). Note that if \underline{L} is as in (4.1) (i.e., it makes a definite angle θ with the horizontal plane) then L(J_{α}) ≍_{θ} ϵ · d^{ℍ}(x_{1,α}, x_{2,α}) ≍_{θ} ϵ^{2}.

By the standard covering argument, there is a disjoint sub-collection {J_{α_{1}}, …, J_{α_{N}} } of {J_{α}}, such that ⋃_{α} J_{α} ⊂ (5J_{α_{1}}) ∪ ⋯ ∪ (5J_{α_{N}}), and by the length space property of d_{P}, we have

N · ψϵ ⩽ d_{P}(x_{1,1}, x_{2,1}) + ⋯ + d_{P}(x_{1,N}, x_{2,N}) ⩽ d_{P}(y, z) = \frac{1}{2} .

Thus, N ⩽ \frac{1}{2}(ψ · ϵ)^{−1} and since L(J_{α}) ≍_{θ} ϵ^{2},

L (⋃_{α} J_{α}) ≲_{θ} \frac{5}{2}ψ^{−1} · ϵ^{−1} · ϵ^{2} = \frac{5}{2}ψ^{−1} · ϵ .

By taking ψ to be a suitably large multiple (depending on θ) of ϵ, and incorporating this multiple into the symbol ≲_{θ} in (4.1), we get L (⋃_{α} J_{α}) ⩽ \frac{1}{2}L(I), which suffices to prove (4.1). □

To simplify the statement of Proposition 4.14, we state it for unit balls. In the application (to Lipschitz maps) we will set ϵ_{1} = ϵ^{40} and consider the rescaling as in (3.1)–(3.4) of B_{ϵ_{1}^{3}}(x) to unit size. Prior to stating the proposition, we give a few preliminaries.

Below, without loss of generality we can (and will) assume p is the indentity element of ℍ. We consider only affine lines \underline{L} such that \underline{L} ∩ B_{\frac{1}{2}} (p) ≠ ∅. Let \underline{x} ∈ \underline{L} be such that d^{ℍ}(\underline{x}, p) is minimal. Using left translation by \underline{x}^{−1} we identify \underline{L} with a line through the identify and define the angle θ with the horizontal as in (4.1). If θ_{0} is sufficiently small and \underline{L} makes Euclidean angle ⩽ θ_{0} with the vertical, then the angle θ with the horizontal will be ⩾ \frac{π}{3}.^{6}

Put

S = \{\underline{L} | \underline{L} makes a Euclidean angle ⩽ θ_{0} with the vertical ∧ \underline{L} ∩ B_{\frac{1}{2}} (p) ≠ ∅\} .

Let L will denote Euclidean 1-dimensional Lebesgue measure on \underline{L}. Note that it differs by a bounded factor from the 1-dimensional Lebesgue measure on \underline{L} induced by the above identification via \underline{x}^{−1}, so the distinction between these measures plays no essential role and will be supressed below.

Recall that the space of all affine lines in ℍ = ℝ^{3} is a 4-dimensional homogeneous manifold which carries a natural measure A. (The precise normalization plays no role below.)

6For the purposes of Proposition 4.14, \frac{π}{3} can actually be replaced by any number < \frac{π}{2} .

Proposition 4.14. Fix ψ ∈ (0, 1). Assume that h : B_{1}(p) → L_{1} is such that Σ_{h} satisfies the total perimeter bound (4.3), and assume that Σ_{h} is supported on cuts E ⊂ B_{1}(p), such that for some half-space P_{E},

(4.15)  L_{3}((P_{E} ∩ B_{1}(p))△E) ≲ (ψ · ϵ^{4})^{4} .

Let S_{0} ⊂ S denote the subset of affine lines \underline{L} such that at least two thirds of the (x_{1}, x_{2}) ∈ (\underline{L} ∩ B_{1}(p)) × (\underline{L} ∩ B_{1}(p)), satisfying

(4.16)  \frac{2}{3}ϵ ⩽ d^{ℍ}(x_{1}, x_{2}) ⩽ \frac{5}{4}ϵ ,
(4.17)  d_{h}(x_{1}, x_{2}) ⩽ ϵ · d^{ℍ}(x_{1}, x_{2}) .

Then

(4.18)  A(S_{0}) ⩾ (1 − ψ)A(S) .

If h is 1-Lipschitz and for all E in the support of Σ_{h},

(4.19)  L_{3}((P_{E} ∩ B_{1}(p))△E) ≲ ϵ^{80} ,

for some small enough constant c > 0, then for all \underline{L} ∈ S and at least half the points (x_{1}, x_{2}) ∈ \underline{L} × \underline{L} satisfying

(4.20)  \frac{2}{3}ϵ ⩽ d^{ℍ}(x_{1}, x_{2}) ⩽ \frac{3}{2}ϵ ,

there holds

(4.21)  d_{h}(x_{1}, x_{2}) ≲ ϵ · d^{ℍ}(x_{1}, x_{2}) .

Proof. Assume first that (4.15) holds. Let D_{1}, D_{2} and d_{h} = d_{1} + d_{2} be as in Lemma 4.2 with η = ψ · ϵ^{4}. Hence, Σ_{h}(D_{1}) ⩽ (ψ · ϵ^{4})^{−3} and ∥d_{h} − d_{1}∥_{L_{1}} ≲ ψ · ϵ^{4}.

Using (4.15), it is straightforward to construct a half space P_{E}, which varies measurably with respect to Σ_{h} (alternatively one can use a measurable selection theorem as in [44]), such that L_{3}((P_{E} ∩ B_{1}(p))△E) ≲ (ψ · ϵ^{4})^{4}. Put

(4.22)  d_{P,1}(x_{1}, x_{2}) = ∫_{D_{1}} d_{P_{E}}(x_{1}, x_{2}) dΣ_{1}(E) .

From Σ_{h}(D_{1}) ⩽ (ψ · ϵ^{4})^{−3}, L_{3}((P_{E} ∩ B_{1}(p))△E) ≲ (ψ · ϵ^{4})^{4}, we obtain

(4.23)  ∥d_{1} − d_{P,1}∥_{L_{1}} ≲ ψ · ϵ^{4} .

This, together with ∥d_{h} − d_{1}∥_{L_{1}} ≲ ψ · ϵ^{4}, implies

(4.24)  ∥d_{h} − d_{P,1}∥_{L^{1}} ≲ ψ · ϵ^{4} .

Write the integral in the definition of the L_{1}-norm in (4.24) as iterated integral, integrating first over pairs of points lying on a given affine line \underline{L} ∈ S, and then over the set of lines, \underline{L} ∈ S with respect to the measure A. It follows from Markov’s inequality (3.15) that for a fraction ⩾ 1 − ψ of affine lines \underline{L} in S,

(4.25)  ∥d_{h} − d_{P,1}∥_{L_{1}(\underline{L}×\underline{L},L×L)} ≲ ϵ^{4} .

On such a line \underline{L}, consider the set of pairs satisfying (4.16), for which (4.1) holds for the metric d_{P,1}. By noting that the measure of the space of pairs of points on \underline{L} satisfying (4.16) is ≳ ϵ^{2}, and applying Markov’s inequality once more, on \underline{L} × \underline{L} to (4.25), we find that for at least half of the pairs points at which (4.1) holds for d_{P,1}, the error term arising from (4.25) is ≲ ϵ^{2}. This gives (4.17).

Finally, assume h is Lipschitz. Let Haus^{ℝ^{3}} denote Hausdorff distance associated to the Euclidean distance d^{ℝ^{3}}. We define a metric ρ^{ℝ^{3}} on S, where, for \underline{L}_{1}, \underline{L}_{2} ∈ S,

ρ^{ℝ^{3}}(\underline{L}_{1}, \underline{L}_{2}) = Haus^{ℝ^{3}}(\underline{L}_{1} ∩ B_{1}(p), \underline{L}_{2} ∩ B_{1}(p)) .

Clearly, with respect to the distance ρ^{ℝ^{3}}, the restriction of the measure A to S is Ahlfors 4-regular. Thus, it follows from (4.18) that if we take ψ = ηϵ^{16} = η(ϵ^{4})^{4}, for a η a sufficiently small universal constant, then S_{0} is (ϵ/100)^{4}-dense in S with respect to ρ^{ℝ^{3}}. So given \underline{L} ∈ S, we can choose \underline{L}_{1} ∈ S_{0} such that ρ^{ℝ^{3}}(\underline{L}, \underline{L}_{1}) ⩽ (ϵ/100)^{4}.

Let P : \underline{L}_{1} ∩ B_{1}(p) → \underline{L} assign to each each x ∈ \underline{L}_{1} ∩ B_{1}(p) the closest point on \underline{L}. Thus, d^{ℝ^{3}}(x, P (x)) ⩽ (ϵ/100)^{4}. Also, at all points, the difference between the differential dP and

a Euclidean isometry is bounded by ϵ^{4}. Finally, since on B_{1}(p) we have d^{ℍ} ⩽ (10d^{ℝ^{3}})^{\frac{1}{2}} , if x ∈ \underline{L} ∩ B_{1}(p), then

(4.26)  d^{ℍ}(x, P (x)) ⩽ ϵ^{2} .

We can assume without loss of genenerality that ϵ is so small that for at least half the pairs, (x_{1}, x_{2}) ∈ \underline{L} × \underline{L} satisfying (4.16), (4.17), we will have (P (x_{1}), P (x_{2})) ∈ B_{1}(p) × B_{1}(p) and (4.20) will hold. From (4.26) and the assumption that h is 1-Lipschitz, it follows (using the triangle inequality) that for say ϵ < \frac{1}{4}, such a pair satisfies (4.21). □

Scale estimate; total perimeter and total nonmonotonicity. Next, we show how to estimate from below a scale on which, apart from a collection of cuts which contributes negligibly to the cut metric d_{f}, the hypothesis of Proposition 4.14 will be satisfied at most locations; see Proposition 4.31. It is from this estimate that the logarithmic behavior in (1.2) of Theorem 1.1 arises.

Recall that the cut measure Σ_{f} is supported on cuts E with finite perimeter. Fix δ > 0. Using the structure of finite perimeter subsets of ℍ and the kinematic formula, in Section 6 we will decompose the total perimeter measure λ_{f} as a sum,

(4.27)  λ_{f} = ∑_{j=0}^{∞} ŵ_{j} ,

in such a way that the measure ŵ_{j} controls the total non-monotonicity on the scale δ^{j} in the following sense.

Fix j > 0 and as usual, let B̆_{\frac{1}{4} δ^{j}}(x) denote the standard rescaling of the ball B_{\frac{1}{4} δ^{j}}(x) ⊂ B_{1}(p) as in (3.10)–(3.14).

Proposition 4.28. If for all r > 0,

(4.29)  λ_{f}(B_{r}(x)) ≲ L_{3}(B_{r}(x)) ,

then

(4.30)  ∫_{Cut}_{(B̆_{\frac{1}{4} δ^{j}} (x))} NM_{B̆_{\frac{1}{4} δ^{j}} (x)}(E) dΣ_{f}(E) ≲ \frac{ŵ_{j} (B_{\frac{1}{4} δ^{j}}(x))}{L_{3} (B_{\frac{1}{4} δ^{j}}(x))} + δ .

In order to apply Proposition 4.28, we need to find j such that ŵ_{j}(B_{1}(p)) ⩽ δ, and hence,

at most locations, x, the term \frac{ŵ_{j}(B_{\frac{1}{4} δ^{j}} (x))}{L_{3}(B_{\frac{1}{4} δ^{j}} (x))} is ≲ δ.

Proposition 4.31. There exists j ⩽ δ^{−1} for which

(4.32)  Mass \binom{}{w_{j}} ≲ δ .

For such j and at least half the points x in B_{1}(p),

(4.33)  ∫_{Cut}_{(B̆_{\frac{1}{4} δ^{j}} (x))} NM_{B̆_{\frac{1}{4} δ^{j}} (x)}(E) dΣ_{f}(E) ≲ δ .

Proof. We have

(4.34)  1 ≳ Mass(λ_{f}) = ∑_{j=0}^{∞} Mass(ŵ_{j}) .

Thus the number of terms in the sum above for which Mass \binom{}{w_{j}} ⩾ δ is bounded by ≲ δ^{−1}, and the claim follows. The conclusion follows from the weak-type (1,1) inequality for the maximal function applied to the measure ŵ_{j}, i.e., (3.19), together with Proposition 4.28. □

Proof of Theorem 1.1. Let a be as in Theorem 4.13. Fix ϵ > 0 and let

(4.35)  δ = cϵ^{40(6+a)+2}

for an appropriately small enough constant c > 0. By Proposition 4.31, can choose j ≲ δ^{−1}, such that (4.33) holds for at least half the points x in B_{1}(p). Below we restrict attention to such a point x and rescale B_{\frac{1}{4} δ^{j}}(x) to standard size, denoting this ball as usual by B̆_{\frac{1}{4} δ^{j}}(x).

By (4.30), (4.33) and Markov’s inequality (3.15), we can write Cut (B̆_{\frac{1}{4} δ^{j}}(x)) as a disjoint

union Cut (B̆_{\frac{1}{4} δ^{j}}(x)) = D_{3} ∪ D_{4}, with corresponding metric decomposition d_{f} = d_{3} + d_{4}, where

(4.36)  Σ_{f}(D_{3}) ⩽ cϵ^{40·6+2} ,
(4.37)  NM_{B̆_{\frac{1}{4} δ^{j}} (x)}(E) ⩽ ϵ^{40a} ∀ E ∈ D_{4} .

By (4.36), we have d_{3}(x_{1}, x_{2}) < cϵ^{40·6+2}, for all x_{1}, x_{2}. Therefore, if d_{f} is restricted to B_{ϵ^{40·6}}(x) = B_{(ϵ^{80})}^{3}(x) and this ball is rescaled to unit size, we get

(4.38)  |d_{f} − d_{4}| ⩽ ϵ^{2} ,

while by (4.37) and Theorem 4.13, d_{4} is supported on cuts which satisfy the hyposthesis of Proposition 4.14. From Proposition 4.14, together with (4.38), Theorem 1.1 follows. □

Preview of the proof of Theorem 4.13. After two preliminary technical results on δmonotone subsets of ℍ have been stated in Section 7, and the classification of monontone subsets of ℍ has been reviewed in Section 8, Theorem 4.13 is proved in Section 9. However, there is a technical step in the argument (the nondegeneracy of the initial configuration) the proof of which, for reasons of exposition, is deferred until Section 10. The proofs of the technical results, Lemma 7.8 and Proposition 7.10, are deferred to Sections 11, 12. The proof of Proposition 7.10 is (by far) the most involved part of this paper.

5. Cuts with small perimeter

In this section we prove Lemma 4.2, which shows that cuts with very small perimeter make a negligible contribution to the cut metric d_{f}. It is most natural to argue here in the context of general PI spaces. Thus, let X denote a PI space, for example, ℝ^{n} or ℍ. Fix p ∈ X and let f : B_{1}(p) → L_{1} satisfy, Lip(f) ⩽ 1.

Put

(5.1)  \begin{aligned}D_{1} & = \{E | Per(E)(B_{1}(p)) ⩽ θ\} , \\ D_{2} & = \{E | Per(E)(B_{1}(p)) > θ\} , \end{aligned}

and let d_{f} = d_{1} + d_{2} denote the corresponding decomposition of the metric d_{f}. Let β denote the doubling constant of X, and τ′, χ > 1, the constants in the Poincaré-Sobolev inequality (2.5).

Proposition 5.2. If f : B_{1}(p) → L_{1} satisfies

(5.3)  λ_{f}(B_{1}(p)) ⩽ K ,

then for all θ > 0,

(5.4)  Σ_{f}(D_{2}) ⩽ Kθ^{−1} ,
(5.5)  ∥d_{f} − d_{2}∥_{L_{1}} ⩽ \frac{2τ′K}{1 − 2^{χ−1}} · θ^{χ−1} .

Proof. From (5.3) and Markov’s inequality (3.15), we get (5.4).

For n ∈ ℕ put

D_{1,n} = {E | θ · 2^{−(n+1)} ⩽ Per(E)(B_{1}(p)) ⩽ θ · 2^{−n}} .

Then D_{1} = ⋃_{n∈ℕ} D_{1,n}. By (5.3) and Markov’s inequality once more, we have

Σ_{f}(D_{1,n}) ⩽ K2^{n+1}θ^{−1} .

Moreover, if E ∈ D_{1,n} then by (2.5)^{7}

(5.6)  − ∫_{B_{1}(p)×B_{1}(p)} |χ_{E}(x_{1}) − χ_{E}(x_{2})| dμ × dμ ⩽ τ′ · (θ · 2^{−n})^{χ} .

By summing over n we get (5.5). □

7It follows immediately from (3.5), the definition of perimeter, that if (2.5) holds for Lipschitz functions, then it holds for FP sets (in which case it becomes an isoperimetric inequality). A corresponding statement is valid for more general BV functions.

Note that when Lip(f) ⩽ 1, by virtue of (2.10), (5.3) holds with K = c(β, τ′). To get (4.4), (4.5) from (5.4), (5.5), we take θ to be a suitable multiple of η^{3} (noting that for X = ℍ, we have β = 16, χ = \frac{4}{3}).

6. The kinematic formula and δ-monotone sets

In this section, using the kinematic formula, we decompose the total perimeter measure as a sum of measures λ_{f} = w_{1} + w_{2} · · ·. Then we prove Proposition 4.28, which states that w_{j} controls the total nonmonotonicity on the scale δ^{j}.

We rely on the simple structure of sets of finite perimeter in dimension 1 and on the kinematic formula, which expresses the perimeter of an FP subset E of ℝ^{n} or a Carnot group, as an integral over the space of lines L, of the perimeters of the 1-dimensional FP sets E ∩ L.

FP sets in dimension 1. Let V denote an open subset of ℝ and let F ⊂ V have finite perimeter, i.e., Per(F)(V) < ∞. Then there exists a unique collection of finitely many disjoint intervals, I_{1}(F), …, I_{N}(F), which are relatively closed in V, such that the symmetric difference of F and I(F) = ⋃_{i=1}^{N} I_{i}(F) has measure zero. Moreover, the perimeter measure per(F), is a sum of delta functions concentrated at the endpoints of these intervals, and the perimeter Per(F)(V) is equal to the number of endpoints; see Proposition 3.52 of [3]. In what follows, we will often assume without explicit mention that the set F ⊂ ℝ, has been replaced by its precise representative I(F) = ⋃_{i=1}^{N} I_{i}(F). Note that I(F′ ∩ V) = I(F)′, per(F′) = per(F).

The kinematic formula. A kinematic formula exists for the PI space (ℍ, d^{X}, L), and more generally, for any Carnot group, an in particular also for ℝ^{n}; see Proposition 3.13, of [55]. Below, the notation is as introduced prior to (4.6).

Let U ⊂ ℍ denote an open subset such that Per(E)(U) < ∞. The kinematic formula states that the function L ↦ Per(E ∩ L)(U ∩ L) lies in L_{1}(lines(U), N), and in addition (for some constant c = c(ℍ) > 0)

(6.1)  Per(E)(U) = c · ∫_{lines(U)} Per(E ∩ L)(U ∩ L) dN (L) .

Perimeter bounds nonmonotonicity. Fix 0 < δ < 1. For all E, L as above, and j ⩾ 0, let C_{j}(E, L) denote the collection of intervals, I(E, L), occuring in I(E ∩ L ∩ B_{1}(x)) such that

(6.2)  δ^{j+1} ⩽ length(I(E, L)) < δ^{j} .

Let E_{j}(E, L) denote the collection of all end points of intervals in C_{j}(E, L). Let card(S) denote the cardinality of the set S. For c(ℍ) as in (6.1) and A ⊂ B_{1}(x), put

(6.3)  w_{j}(E, L)(A) = c(ℍ) · card({e ∈ E_{i}(E, L) | e ∈ A}) ,

(6.4)  w_{j}(E)(A) = ∫_{lines(B_{1}(x))} w_{j}(E, L)(A) dN (L) ,

(6.5)  ŵ_{j}(E)(A) = ŵ_{j}(E′)(A) = \frac{1}{2} (w_{j}(E)(A) + w_{j}(E′)(A)) .

Finally, set

(6.6)  ŵ_{j}(A) = ∫_{Cut(B_{1}(x))} ŵ_{j}(E)(A) dΣ_{f}(E) .

By the the kinematic formula (6.1), we get the decomposition of the perimeter measure and total perimeter measure,

(6.7)  Per(E) = ∑_{j} ŵ_{j}(E) ,

(6.8)  λ_{f} = ∑_{j=0}^{∞} ŵ_{j} .

which is a restatement of (4.27).

Proof of Proposition 4.28. Fix E with finite perimeter. For N -a.e. L ∈ lines (B_{\frac{1}{4} δ^{j}}(x)), we can assume that L ∩ E ∩ B_{\frac{1}{4} δ^{j}}(x) and L ∩ E′ ∩ B_{\frac{1}{4} δ^{j}}(x) consist of finitely many intervals, I_{1}, …, I_{N}, in the natural consecutive ordering. Note that all the intervals I_{2}, …, I_{N−1}, (including both end points), are contained in B_{\frac{1}{4} δ^{j}}(x). In particular, these intervals lie in C_{k}(E, L), for various k ⩾ j.

Since the nonmonotonicity NM_{B_{\frac{1}{4} δ^{j}} (x)}(E, L) is defined as an infimum over intervals (see (4.8)), it can be bounded from above by employing any specific interval I. For definiteness, assume say I_{1} ⊂ E. where I_{N} = ∅ if N = 1. If I_{N} ⊂ E, put I = L ∩ B_{\frac{1}{4} δ^{j}}(x). If I_{N} ⊂ E′, put I = I′_{1} ∩ B_{\frac{1}{4} δ^{j}}(x).

Rescale the ball B_{\frac{1}{4} δ^{j}}(x) to unit size as in (3.10)–(3.14). Then by employing the above chosen interval I, we get

(6.9)  NM_{B_{\frac{1}{4} δ^{j}} (x)}(E, L) ≲ ∑_{k⩾j} ∑_{I∈C_{k}(E,L)} length(I) .

Since an interval is determined by its endpoints, (6.9) implies

(6.10)  NM_{B_{\frac{1}{4} δ^{j}} (x)}(E, L) ≲ ∑_{k⩾j} δ^{k−j} Mass (ŵ_{k}(E, L)) ,

and by integrating over the space of lines, we get

(6.11)  NM_{B_{\frac{1}{4} δ^{j}} (x)}(E) ≲ Mass(ŵ_{j}) + δ Mass(Per(E)) ,

which completes the proof of Proposition 4.28. □

7. The quantitative interior and boundary

The proof (though not the statement) of Theorem 4.13 utilizes quantitative notions of the interior and boundary of a measurable set E. In the present section, after defining these notions, we state two key properties for δ-convex and δ-monotone subsets of ℍ; see Proposition 7.10, Lemma 7.8. We also deduce two particular consequences of Proposition 7.10 for the structure of the quantitative boundary of δ-monotone sets. These are used in the proof of Theorem 4.13. Assuming Proposition 7.10 and Lemma 7.8, the proof of Theorem 4.13 is given in Section 9. The proofs of Proposition 7.10 and Lemma 7.8, which are the most technical parts of our discussion, are postponed until Sections 12 and 11, respectively.

Definition 7.1. Let (X, d^{X}, μ) be a metric measure space and E ⊂ X a measurable subset. For α ∈ (0, 1) and u > 0 define:

(7.2)  int_{α,u}(E) := \{x | \frac{μ(E ∩ B_{u}(x))}{μ(B_{u}(x))} ⩾ 1 − α\} ,

(7.3)  ∂_{α,u}(E) := \{x | α < \frac{μ(E ∩ B_{u}(x))}{μ(B_{u}(x))} < 1 − α\} .

Observe that ∂_{α,u}(E) = ∅ for α ⩾ \frac{1}{2}. We note the following properties which are trivial consequences of the definitions.

If β ⩽ α, then,

(7.4)  \begin{aligned}int_{β,u}(E) & ⊂ int_{α,u}(E) \\ ∂_{α,u}(E) & ⊂ ∂_{β,u}(E). \end{aligned}

For u_{2} ⩽ u_{1} and x ∈ X set

c(u_{1}, u_{2}, x) = \frac{μ(B_{u_{1}}(x))}{μ(B_{u_{2}}(x))} .

Then

(7.5)  \begin{aligned}x ∈ int_{α,u_{1}}(E) & ⟹ x ∈ int_{c(u_{1},u_{2},x)·α,u_{2}}(E) \\ x ∈ ∂_{c(u_{1},u_{2},x)·α,u_{2}}(E) & ⟹ x ∈ ∂_{α,u_{1}}(E). \end{aligned}

If x ∈ ∂_{α,u}(E) then

(7.6)  x ∈ int_{1−α,u}(E) ∩ int_{1−α,u}(E′).

Finally,

(7.7)  (∂_{α,u} (E))′ = int_{α,u}(E) ∪ int_{α,u}(E′).

Quantitative interior of δ-monotone subsets. If a subset E of a ball, B_{1}(p), is close to a half-space, then it follows that there exists a sub-ball of a definite size which is almost entirely contained in either E or E′. Conversely, proving that δ-monotone subsets have this property constitutes an important step in the proof that such a set is close to a half-space. (It is the remainder of argument, based on Proposition 7.10 below, which requires that we shrink the size of the ball on which the conclusion is obtained. This is the content of Lemma 7.8, which constitutes both Step A) of the proof in the precisely monotone case, treated in Section 8 and more generally, Step A′) of the case, δ > 0, treated in Section 9.

Lemma 7.8. There exists 0 < c < \frac{1}{2} such that if E ⊂ B_{r}(p) is ϵ^{2}-monotone on B_{r}(p) then there exists q ∈ B_{\frac{1}{2} r}(p) such that q ∉ ∂_{ϵ,cr}(E), i.e., q ∈ int_{ϵ,cr}(E) ∪ int_{ϵ,cr}(E′).

Quantitative convexity of δ-convex sets. If E ⊂ ℝ^{n} is convex and L is a line passing through points p ∈ E and q ∈ int(E), then the segment of L lying between p and q also consists of interior points of E. Below, for subsets of ℍ which are almost convex, we given a quantitative version of this statement.

We say that E ⊂ B_{r}(p) is δ-convex on B_{r}(p) if for NC_{B_{r}(p)}(E, L) as in (4.7),

(7.9)  NC_{B_{r}(p)}(E) = ∫_{lines(B̆_{r}(x))} NC(E, L) dN (L) < δ .

Proposition 7.10. There exists universal constants c ∈ (0, 1) and C ∈ (1, ∞) with the following properties. Fix κ, η, ξ, r, ρ ∈ (0, 1) such that

(7.11)  ρ ⩽ min \{\frac{1}{2}κr^{2}, c\} .

Set

(7.12)  δ_{1} = \frac{cκ^{3}η^{2}ξρ^{3}}{r} ,
(7.13)  δ_{2} = cκ^{6}η^{3}ξ^{2}ρ^{3}r^{6} .

Let L ∈ lines(ℍ) be parameterized by arc length and assume that

(7.14)  L(0) ∈ int_{1−η,ρ}(E) ,
(7.15)  L(1) ∈ int_{δ_{1},Cr}(E) ,

and E ⊂ ℍ is δ_{2}-convex on B_{2C}(L(0)), then for all s ∈ [κ, 1],

(7.16)  L(s) ∈ int_{ξ,crs}(E) .

Remark 7.17. The import of the proposition is the following: Even if L(0) is only in the very weak quantitative interior of E (η small) we can ensure that L(s) is in the very strong quantitative interior of E (i.e. ξ small), provided that L(1) is in the sufficiently strong quantitative interior of E (δ_{1} sufficiently small) and E is sufficiently convex (δ_{2} sufficiently small).

Remark 7.18. The application to the proof of Theorem 4.13 requires some properties of the quantitative boundary for δ-monotone sets which are derived in the next subsection using Proposition 7.10. The assumption, L(0) ∈ int_{1−η,ρ} E, is guaranteed by assuming L(0) ∈ ∂_{η,ρ} E; see (7.6).

Remark 7.19. Note that the constants, 1 ⩾ κ, η, ξ, ρ > 0 can be chosen arbitrarily small, provided r is then chosen to satisfy (7.11). The particular form of (7.11) reflects the multiplicative structure of ℍ; compare Remark 12.19. In view of (7.5), by taking ξ a definite amount smaller if necessary, we can replace csr in (7.16) by any smaller positive radius.

Lines in quantitative boundaries of δ-monotone sets. Given that any proper monotone subset, E, is a half-space, and hence, that ∂ E is a 2-plane, it follows that if for L ∈ lines(ℍ), y_{1}, y_{2} ∈ L ∩ ∂ E, y_{1} ≠ y_{2}, then L ⊂ ∂ E. Moreover, ∂ E is a union of such lines L ∈ lines(ℍ). Conversely, these statements form two key substeps in the proof that monotone subsets ℍ are half-spaces; see substeps 1) and 2) of part B) of Section 8.

Essentially, Corollaries 7.27, 7.41, of Proposition 7.10, constitute the corresponding substeps in the proof that δ-monotone subsets are close to half-spaces. Specifically, if we quantify the hypotheses of the above two statements, then the conclusions hold in a weaker quantitative sense. Prior to tackling these corollaries, whose statements are somewhat complicated, the reader may wish to look at the proofs of above mentioned substeps given in Section 8. Here and in Section 8, the skeleton of the argument is precisely the same, but in Section 8, the technical complications are absent.

Below, we have sacrificed some sharpness to avoid further complication in the relevant expressions.

Corollary 7.20. Let C, c be the constants from Proposition 7.10. For every κ, α_{1}, α_{2} ∈ (0, 1), u_{1} ∈ (0, \frac{κ^{3}}{2} ), u_{2} ∈ (0, cκ^{2}) define

(7.21)  γ = C · max \{\sqrt{\frac{2u_{1}}{κ}} , \frac{u_{2}}{cκ}\} ,

and

(7.22)  β = \frac{C^{5}α_{1}^{2}α_{2}u_{1}^{3}u_{2}^{4}κ}{c^{3}γ^{5}} ,

(7.23)  δ = \frac{C^{2}α_{1}^{3}α_{2}^{2}u_{1}^{3}u_{2}^{8}κ}{c^{7}γ^{2}} .

Fix L ∈ lines(ℍ) which is parameterized by arc length and E ⊂ B_{2C}(L(0)) which is δmonotone on B_{2C}(L(0)). Assume that

x_{1} = L(0) ∈ ∂_{α_{1},u_{1}}(E) , x_{2} = L(κ) ∈ ∂_{α_{2},u_{2}}(E) ,

so that in particular d^{ℍ}(x, y) = κ. Then for all t ∈ [κ, 1] we have

L(t) ∈ ∂_{β,γ}(E) .

Proof. Assume for the sake of contradiction that L(t) ∉ ∂_{β,γ}(E). Thus without loss of generality we can assume that, say, x_{1} ∈ int_{1−α_{1},u_{1}}(E) and L(t) ∈ int_{β,γ}(E). In order to apply Proposition 7.10 rescale the metric d^{ℍ} → \frac{1}{t}d^{ℍ}, so that the rescaled distance between x_{1} and L(t) is equal to 1. Let L′(s) = L(ts), so that L′ is parameterized according to arc length in the rescaled metric. We will apply Proposition 7.10 with the following parameters:

(7.24)  η = α_{1}, ρ = \frac{u_{1}}{t} , r = \frac{γ}{Ct}, s = \frac{κ}{t}, ξ = α_{2} (\frac{Ctu_{2}}{cγκ} )^{4} .

Note that, with this notation, the parameter β, as defined in (7.22), is at most δ_{1}, as given in (7.12) (where we used the assumption t ⩾ κ). Hence in the rescaled metric, and using the notation in (7.24), we have x_{1} = L′(0) ∈ int_{1−η,ρ}(E), L(t) = L′(1) ∈ int_{δ_{1},Cr}(E). Moreover, after rescaling, E is δ-monotone on B_{2C/t}(x_{1}), and hence E is \frac{δ}{t^{4}} -monotone on B_{2C}(x_{1}). Observe that \frac{δ}{t^{4}} , with δ given in (7.23), is at most δ_{2} as defined in (7.13) (using the assumption t ⩾ κ). We are therefore in position to apply Proposition 7.10, provided that we check that with our definitions κ, η, ξ, r, ρ ∈ (0, 1), s ∈ [κ, 1], and (7.11) is satisfied. These facts are ensured by the assumptions u_{1} < \frac{κ^{3}}{2} , u_{2} < Cκ^{2}, t ∈ [κ, 1], and (7.21). So, the conclusion of Proposition 7.10 says that in the rescaled metric we have x_{2} = L′(s) ∈ int_{ξ,crs}(E).

Rescaling back to the original metric d^{ℍ}, we see that x_{2} ∈ int_{ξ,crst}(E) = int_{ξ, \frac{cγκ}{Ct}} (E). In other words: (7.25)

L_{3}(E′ ∩ B_{\frac{cγκ}{Ct}} (x_{2})) ⩽ ξ · L_{3}(B_{\frac{cγκ}{Ct}} (x_{2})) = ξ · (\frac{cγκ}{Ctu_{2}} )^{4} · L_{3} (B_{u_{2}}(x_{2})) =^{(7.24)} α_{2} · L_{3} (B_{u_{2}}(x_{2})) .

Note that \frac{cγκ}{Ct} ⩾ u_{2}, and hence B_{\frac{cγκ}{Ct}} (x_{2}) ⊃ B_{u_{2}}(x_{2}), as ensured by (7.21) (since t ⩽ 1). Moreover, the assumption x_{2} ∈ ∂_{α_{2},u_{2}}(E) implies that

(7.26)  L_{3}(E′ ∩ B_{\frac{cγκ}{Ct}} (x_{2})) ⩾ L_{3}(E′ ∩ B_{u_{2}}(x_{2})) > α_{2} · L_{3}(B_{u_{2}}(x_{2})) .

Inequalities (7.25), (7.26) yield the desired contradiction. □

Corollary 7.27. Let C, c be the constants from Proposition 7.10. For every κ ∈ (0, \frac{1}{2}],

α_{1}, α_{2} ∈ (0, 1), u_{1} ∈ (0, \frac{κ^{7}}{8C^{2}} ), u_{2} ∈ (0, \frac{cκ^{4}}{2C} ) define

(7.28)  γ_{∗} = C^{3/2} (\frac{2}{κ})^{1/2} · max \{(\frac{2u_{1}}{κ} )^{1/4} , (\frac{u_{2}}{cκ})^{1/2}\} ,

and

(7.29)  β_{∗} = \frac{128C^{29}α_{1}^{4}α_{2}^{3}u_{1}^{6}u_{2}^{12}}{κ^{5}γ_{∗}^{19}} ,

(7.30)  δ_{∗} = \frac{2^{16}C^{41}α_{1}^{6}α_{2}^{5}u_{1}^{9}u_{2}^{20}}{81c^{16}κ^{8}γ_{∗}^{26}} .

Fix L ∈ lines(ℍ) parameterized by arc length and E ⊂ B_{3C}(L(0)), which is δ_{∗}-monotone on B_{3C}(L(0)). Assume that

x_{1} = L(0) ∈ ∂_{α_{1},u_{1}}(E) , x_{2} = L(κ) ∈ ∂_{α_{2},u_{2}}(E) ,

so that in particular d^{ℍ}(x, y) = κ. Then for all t ∈ [0, 1] we have

(7.31)  L(t) ∈ ∂_{β_{∗},γ_{∗}}(E) .

Proof. The case t ∈ [κ, 1] is a simple consequence of Corollary 7.20. Indeed, since E is δ_{∗}- monotone on B_{3C}(L(0)), it is also (\frac{3}{2})^{4} · δ_{∗}-monotone on B_{2C}(L(0)). Note that (\frac{3}{2})^{4} · δ_{∗} ⩽ δ, where δ is given in (7.23) (this follows immediately from the definitions and our assumed upper bounds on u_{1}, u_{2}). We can therefore apply Corollary 7.20 to deduce that L(t) ∈ ∂_{β,γ}(E), where β, γ are given in (7.22), (7.21). Note that γ_{∗} ⩾ γ, and hence by (7.5) we have

(7.32)  L(t) ∈ ∂_{(_{\frac{γ}{γ∗}})^{4}·β,γ_{∗}}(E) .

Since β_{∗} ⩽ (\frac{γ}{γ_{∗}} )^{4} · β we can use (7.4) to deduce that L(t) ∈ ∂_{β_{∗},γ_{∗}}(E), as required.

To deal with the case t ∈ [0, κ], note that since, as explained above, E is δ-monotone on B_{2C}(L(0)), by Corollary 7.20 we have L(2κ) ∈ ∂_{β,γ}(E). We wish to apply Corollary 7.20 to the points L(2κ), x_{2} = L(κ), L(t), and to the geodesic L′(s) = L(−s + 2κ) (so that L′(0) = L(2κ), L′(κ) = L(κ), L′(2κ − t) = L(t), where 2κ − t ∈ [κ, 1]), with (α_{1}, u_{1}) replaced by (β, γ) and (α_{2}, u_{2}) unchanged. Note that it follows from (7.21),(7.28) that:

(7.33)  γ_{∗} = C\sqrt{\frac{2γ}{κ}} = C · max \{\sqrt{\frac{2γ}{κ}} , \frac{u_{2}}{cκ}\} ,

where in the last step above we used the fact that γ ⩾ \frac{Cu_{2}}{cκ}, which implies that \sqrt{\frac{2γ}{κ}} ⩾ \frac{u_{2}}{cκ} by our assumption on u_{2}. We can restate (7.33) as saying that γ_{∗} corresponds to the quantity γ of Corollary 7.20, where we substitute our new choice of parameters. Moreover, by substituting these values into (7.23) and (7.22), we see that for these new parameters (\frac{3}{2})^{4} · δ_{∗} is equal to the value of δ from (7.23), and β_{∗} is equal to the value of β from (7.29) (we chose the values of β_{∗}, δ_{∗} precisely for this purpose). Note that since E is δ_{∗}-monotone on B_{3C}(L(0)) ⊃ B_{2C}(L(2κ)), it is also (\frac{3}{2})^{4} · δ_{∗}-monotone on B_{2C}(L(2κ)). In order to apply Corollary 7.20

we also need to ensure that γ = C · max \{\sqrt{\frac{2u_{1}}{κ}} , \frac{u_{2}}{cκ}\} ⩽ \frac{κ^{3}}{2} and β = \frac{C^{5}α_{1}^{2}α_{2}u_{1}^{3}u_{2}^{4}κ}{c^{3}γ^{5}} ⩽ 1, which is indeed the case, as follows from the assumed upper bounds on u_{1}, u_{2}. The conclusion of Corollary 7.20 is precisely (7.31). □

Corollary 7.34. Let C, c be the constants from Proposition 7.10. Fix α, u ∈ (0, 1), t ∈ (0, \frac{1}{3}] and d > 0, such that:

(7.35)  \frac{2C}{c} u ⩽ d ⩽ min \{2C, \frac{C^{2}}{2} \} · t ,

(7.36)  αu^{4} ⩽ min \{\frac{c^{3}}{2C^{7}} d^{3}t, \frac{8c^{4}}{C^{5}} dt^{3}\} .

Denote:

(7.37)  ϕ = \frac{C^{20}}{2^{9}c^{12}} · \frac{α^{4}u^{16}}{d^{8}t^{8}} ,

(7.38)  ζ = \frac{C^{17}}{2^{12}c^{16}} · \frac{α^{5}u^{20}}{t^{11}d^{5}} .

Assume that x ∈ ℍ and E ⊂ B_{2C}(x) are such that x ∈ ∂_{α,u}(E). Assume also that E is ζ-monotone on B_{2C}(x). Then there exists L ∈ lines(ℍ) with L(0) = x such that either L(t) or L(−t) is in ∂_{ϕ,d}(E).

Proof. Take any L ∈ lines(ℍ) with L(0) = x. Note that (7.35), (7.36), (7.37) imply that ϕ ⩽ \frac{1}{2}. Hence, we are done if one of \{L(−t), L(t)\} is in int_{ϕ,d}(E) and the other is in int_{ϕ,d}(E′). Indeed, in this case since the collection of all oriented lines through x is connected (it can be identified with the unit circle) the required result follows from the Intermediate Value Theorem.

Assume for the sake of contradiction that the assertion of Corollary 7.34 is false. Then by the above discussion {L(−t), L(t)} ⊂ int_{ϕ,d}(E) or {L(−t), L(t)} ⊂ int_{ϕ,d}(E′). So, assume without loss of generality that {L(−t), L(t)} ⊂ int_{ϕ,d}(E). In order to apply Proposition 7.10 we rescale the metric: d^{ℍ} → \frac{1}{2t}d^{ℍ}. Denote y_{1} = L(−t), y_{2} = L(t), so that in the rescaled metric the distance between y_{1} and y_{2} is 1, and their distance from x is \frac{1}{2}. The geodesic L′(s) = L(2ts − t) is parameterized by arc length in the rescaled metric with L′(0) = y_{1}, L′ (\frac{1}{2}) = x, L′(1) = y_{2}. We will apply Proposition 7.10 to the geodesic L′ with the following parameters:

(7.39)  κ = η = s = \frac{1}{2}, ξ = α (\frac{2Cu}{cd})^{4} , r = \frac{d}{2Ct}, ρ = \frac{C^{5}}{8c^{3}} · \frac{αu^{4}}{dt^{3}} .

Note that (7.35), (7.36) ensure that ρ ⩽ min \{\frac{1}{2}κr^{2}, c\} and r, ξ ⩽ 1. In the rescaled metric y_{1}, y_{2} ∈ int_{ϕ,d/(2t)}(E) = int_{ϕ,Cr}(E). Since ρ ⩽ \frac{d}{2t} we may conclude from (7.5) that

y_{2} ∈ int_{(_{\frac{d}{2tρ}})^{4}·ϕ,ρ}(E) =^{(7.37)∧(7.39)} int_{η,ρ}(E) .

In the rescaled metric E is ζ-monotone on B_{C/t}(x). Since t ⩽ \frac{1}{3} we have B_{2C}(y_{1}) ⊂ B_{C/t}(x), and therefore E is \frac{ζ}{(2t)^{4}} -monotone on B_{2C}(y_{1}). Observe that with the parameters set as in (7.39), we have δ_{1} = ϕ and δ_{2} = \frac{ζ}{(2t)^{4}} , where δ_{1}, δ_{2} are as in (7.12), (7.13). Therfore, we can apply Proposition 7.10, which implies that (in the rescaled metric)

(7.40)  x ∈ int_{ξ,crs}(E) =^{(7.39)} int_{α·(\frac{2Cu}{cd})^{4}, \frac{cd}{4Ct}} (E) .

But, in the rescaled metric we know that x ∈ ∂_{α, \frac{u}{2t}} (E). Note that it follows from (7.35) that \frac{u}{2t} ⩽ \frac{cd}{4Ct}. Hence, by (7.5) and (7.7) we deduce from (7.40) that x ∈ int_{α, \frac{u}{2t}} (E) ⊂ (∂_{α, \frac{u}{2t}} (E))′, which yields the desired contradiction. □

Corollary 7.41. There exist universal constants \overline{c}, \overline{C} > 0 with the following properties. Fix α ∈ (0, 1) and u ∈ (0, \overline{c}). Let x ∈ ℍ and E ⊂ B\overline{C}(x) be δ-monotone on B\overline{C}(x), where

(7.42)  δ = \overline{c} · α^{29}u^{71} .

Assume also that x ∈ ∂_{α,u}(E). Then there exists L ∈ lines(ℍ), parameterized by arc length, such that x = L(0) and for all s ∈ [−\frac{1}{3}, \frac{1}{3}] we have:

(7.43)  L(s) ∈ ∂_{\overline{c}·α^{19}u^{46},\overline{C}·u^{1/4}}(E) .

Proof. Below we will have \overline{C} ⩾ 4C, where C is the constant from Proposition 7.10. We will first apply Corollary 7.34 with t = \frac{1}{3} and d ≍ u, while noting that if d is a large enough multiple of u, and \overline{c} is small enough (i.e., u is small enough), then the conditions (7.35), (7.36) are satisfied. For ϕ as in (7.37) we have ϕ ≍ α^{4}u^{8}, and for ζ as in (7.38) we have ζ ≍ α^{5}u^{15}. Note that since E is δ-monotone on B\overline{C}(x) it is also ζ-monotone on B_{2C}(x), provided \overline{c} is small enough. Hence, it follows from Corollary 7.34 that there exists L ∈ lines(ℍ) with L(0) = x and L (−\frac{1}{3}) ∈ ∂_{ϕ,d}(E).

Next, we will apply Corollary 7.27 with x_{1} = L (−\frac{1}{3}), x_{2} = x, κ = \frac{1}{3}, α_{1} = ϕ, u_{1} = d, α_{2} = α, u_{2} = u. Provided \overline{c} is small enough, u_{1}, u_{2} satisfy the conditions of Corollary 7.27.

For γ_{∗} as in (7.28) we have γ_{∗} ≍ u^{1/4}, for β_{∗} as in (7.29) we have β_{∗} ≍ α^{19}u^{181/4}, and for δ_{∗} as in (7.30) we have δ_{∗} ≍ α^{29}u^{141/2}. Moreover, since E is δ-monotone on B\overline{C}(x) it is also δ_{∗}-monotone on B_{3C}(x_{1}), provided \overline{c} is small enough. Corollary 7.27 now implies that L(s) ∈ ∂_{β_{∗},γ_{∗}}(E) for all s ∈ [−\frac{1}{3}, \frac{1}{3}], as required. □

8. Classification of monotone sets

It was shown in [23] that a proper nonempty monotone set E ⊂ ℍ is, up to a set of measure zero, a half-space P. In this section we recall the proof of this result, which is an essential preliminary for proof of Theorem 4.13, the stability version for δ-monotone sets, given in Section 9. To give the key ideas, it suffices to consider the case of precisely monotone sets. We call a set E precisely monotone if E ∩ L and E′ ∩ L are connected for all L (rather than connected modulo subsets of measure zero).

There are two main steps:

A) E ∩ B_{r}(p) or E′ ∩ B_{r}(p) has nonempty interior for every r > 0 and p ∈ ℍ.

B) Either ∂E is contained in a 2-plane, in which case (by a trivial connectedness argument) the theorem holds, or ∂E has nonempty interior.

Step A) follows from the special case of Lemma 7.8 in which ϵ = 0; the general case of Lemma 7.8 is A′), the quantitative version of A), which is used in the proof of Theorem 4.13. Below, we prove Step B).

Proof of Step B). It will suffice assume that ∂E is nonempty.

Proof. The proof of B) has the following substeps.

1) If L ∈ lines(ℍ) and L ∩ ∂E contains at least two points, then L ⊂ ∂E.

2) ∂E is a union of lines.

3) Steps 1) and 2) imply B).

Steps 1), 2), are special cases of Corollaries 7.27, 7.41, respectively. But for clarity, we will repeat the proofs in the present simpler (nonquantitative) situation. The proof of step 3) requires some additional properties of pairs of lines, which are established in the next subsection.

Properties of pairs of lines. L_{1}, L_{2} ∈ lines(ℍ) are called parallel if L_{2} = g · L_{1}, or equivalently, L_{1} = g^{−1} · L_{2}, for some g ∈ ℍ. This holds if and only if the projections π(L_{1}), π(L_{2}) are either parallel or coincide. Unless π(L_{1}) = π(L_{2}), the lines L_{1}, L_{2} are not parallel as lines in ℝ^{3}.

If L_{1}, L_{2} are not parallel, then their projections intersect in a unique point. If in addition, L_{1} ∩ L_{2} = ∅, then the pair L_{1}, L_{2} is called skew. We put

(8.1)  F (L_{1}, L_{2}) = π^{−1}(π(L_{1}) ∩ π(L_{2})) .

Define the vertical distance between L_{1}, L_{2} by

(8.2)  d^{V} (L_{1}, L_{2}) = d^{ℍ}(L_{1} ∩ F (L_{1}, L_{2}), L_{2} ∩ F (L_{1}, L_{2})) .

The following lemmas describe the family of lines L which intersect both L_{1} and L_{2}, where L_{1}, L_{2}, are either parallel lines with distinct projections, or skew. At this point, the roles of L_{1}, L_{2} are symmetric and assertions about L_{1} should be understood as applying to L_{2} as well.

Lemma 8.3. If L_{1}, L_{2} ∈ lines(ℍ) are parallel, and π(L_{1}) ≠ π(L_{2}), then:

1) For x ∈ L_{1}, there is a unique x^{∗} ∈ L_{2}, such that x, x^{∗} lie on a line L(x) ∈ lines(ℍ). Moreover, there is a unique shortest line segment b(L_{1}, L_{2}) from L_{1} to L_{2} which is orthogonal to both L_{1} and L_{2}.

2) There exists a unique point m = m(L_{1}, L_{2}) ∈ ℝ^{2} lying halfway between π(L_{1}) and π(L_{2}), such that for all x ∈ L_{1}, the line L(x) intersects the fibre π^{−1}(m). Moreover, every point on π^{−1}(m) intersects some line L(x).

3) The union of the lines {L(x)}_{x∈L_{1}} is a smooth ruled surface X = X(L_{1}, L_{2}) defined over ℝ^{2} \ T, where T = T (L_{1}, L_{2}) denotes the line parallel to π(L_{1}), π(L_{2}), which passes through m(L_{1}, L_{2}). At no point x ∈ X is X tangent to the horizontal subspace H_{x}.

Proof. Let O_{θ} be as in the subsection of Section 1 entitled “the Heisenberg group as a Lie group”. By applying O_{θ} for suitable θ, and then applying a suitable left translation we can assume that L_{1} = (0, 0, 0) · (t, 0, 0). Next, after a suitable translation (a′′, 0, 0) (which leaves L_{1} invariant) we can assume that assume that L_{2} intersects the plane (u, v, 0) along the v-axis, and hence can be written as (0, b′′, 0) · (s, 0, 0) (we are using here the fact that π(L_{1}) ≠ π(L_{2})). Finally, after a translation of the form (0, −b′′/2, 0) we can assume that

(8.4)  L_{1} = (t, e, −et) L_{2} = (s, −e, es)

for some e ∈ ℝ.

For this pair, if x = (t, e, −et), then

(8.5)  x^{∗} = (−t, −e, −et) .

To see this, observe that the line L(x) in ℝ^{3} which joins these points, is parallel to the plane (u, v, 0) and passes through the point (0, 0, −et). So L(x) ∈ lines(ℍ); see (2.15). The fiber π^{−1}((0, 0)) is the unique fiber through which all of these lines pass as t varies in (−∞, ∞), and every point on π^{−1}((0, 0)) arises in this way. Thus, for this pair,

(8.6)  m(L_{1}, L_{2}) = (0, 0) .

The unique shortest line segment joining L_{1}, L_{2} has length 2e and is contained in the line

(8.7)  b(L_{1}, L_{2}) := (0, s, 0) .

The surface, X, is given by

(8.8)  (u, v, −e^{2}u/v) .

From these facts, all remaining statements are straightforward to verify. □

Lemma 8.9. If L_{1}, L_{2} ∈ lines(ℍ) are skew, then there is a hyperbola Y = Y (L_{1}, L_{2}) ⊂ ℝ^{2} with asymptotes π(L_{1}), π(L_{2}), such that every tangent line of Y has a unique lift, L ∈ lines(ℍ), which intersects both L_{1} and L_{2}. Conversely, if L ∈ lines(ℍ) and L ∩ L_{i} ≠ ∅, for i = 1, 2, then π(L) is tangent to Y. Except for the unique point L_{1} ∩ F (L_{1}, L_{2}) (respectively L_{2} ∩ F (L_{1}, L_{2})) every point x of L_{1} lies on a unique line, \underline{L}(x), intersecting L_{2} (respectively every point x of L_{2} lies on a unique line, \underline{L}(x), intersecting L_{1}).

Proof. By applying a suitable left translation and then an isometry O_{θ} and after possibly interchanging the subscripts of L_{1}, L_{2}, we can assume the canonical normalization:

(8.10)  L_{1} = (t, wt, c),  L_{2} = (s, −ws, −c), w, c > 0, π(L_{1}) ∩ π(L_{2}) = (0, 0).

From the geometric interpretation of the correction term given after (2.13), it follows that the points p = (t, wt, c) ∈ L_{1}, and q = (s, −ws, −c) ∈ L_{2} lie on some L ∈ lines(ℍ), precisely when there is parallelogram in ℝ^{2} spanned (s, −ws), (t, wt), with oriented area 2c. Define θ(L_{1}, L_{2}) ∈ (0, π) by

(8.11)  tan(\frac{1}{2}θ(L_{1}, L_{2})) = w ,

or equivalently,

(8.12)  tan(\frac{1}{2}θ(L_{1}, L_{2})) · ts = w · ts = c .

Then (1 + w^{2}) · (sin θ(L_{1}, L_{2})) · ts = 2c. The envelope of the resulting family of lines is the hyperbola, Y, with equation:

(8.13)  w^{2}u^{2} − v^{2} = cw.
□

Corollary 8.14. Let L_{1}, L_{2} be skew lines as in the proof of Lemma 8.9. Put x = (t, wt, c), x̂ = (−t, −wt, c) (where x, x̂ ∈ L_{1}). Then as elements of lines(ℍ), the lines \underline{L}(x), \underline{L}(x̂), are parallel, and

m(\underline{L}(x), \underline{L}(x̂)) = (0, 0) .

There are precisely two shortest horizontal segments joining L_{1} and L_{2}. In the notation of the proof of Lemma 8.9, these are the segments which project to the segments that touch π(L_{1}), π(L_{2}) and are tangent to the hyperbola Y at its focal point ±\sqrt{c/w}. Thus these segments are contained in the lines:

(8.15)  \begin{aligned}b_{+}(L_{1}, L_{2}) & := (\sqrt{\frac{c}{w}}, s, \sqrt{\frac{c}{w}} · s ) \\ b_{−}(L_{1}, L_{2}) & := (−\sqrt{\frac{c}{w}}, s, −\sqrt{\frac{c}{w}} · s) . \end{aligned}

Remark 8.16. A pair of parallel lines, L_{1}, L_{2}, with distinct projections, can be viewed as a limiting case of a pair of skew lines L_{1,t}, L_{2,t} in which lim_{t→∞} θ(L_{1,t}, L_{2,t}) = 0 (where θ(L_{1,t}, L_{2,t}) is the angle between π(L_{1,t}) and π(L_{2,t})), and as t → ∞, one of b_{±}(L_{1,t}, L_{2,t}) moves off to infinity while the other converges to b(L_{1}, L_{2}), of the pair of parallel lines L_{1}, L_{2}; compare (8.7).

Proof of 1). Let p ∈ ∂E. Then the exists p_{i} ∈ E, with p_{i} → p. Let q ∈ int(E), the interior of E, and assume that there is a line, L ∈ lines(ℍ), with L(0) = p to L(ℓ) = q. If L_{i} denotes the line parallel to L passing through p_{i} then L_{i}(ℓ) → L(ℓ) and hence L_{i}(ℓ) ∈ int(E) for i sufficiently large. Since E is convex, by (the non-quantitative version of) Corollary 7.27, we get L_{i}(s) ∈ int(E), for 0 < s ⩽ ℓ and i sufficiently large and by passing to the limit L(s) ∈ int(E), for 0 < s ⩽ ℓ. Since, E′ is also convex, the corresponding statement holds for E′ as well. This completes the proof of sub-step 1).

Proof of 2). Let p ∈ ∂E, L ∈ lines(ℍ) with p = L(0) and fix q = L(ℓ) ≠ p. We need to show that q ∈ ∂E. By 1), we can assume say L(ℓ) ∈ int(E). Similarly, L(−ℓ) ∈ int(E) or L(−ℓ) ∈ int(E′). By the same argument as in in the proof of 1), if L(ℓ) ∈ int(E) and L(−ℓ) ∈ int(E), then p = L(0) ∈ int(E). Therefore, we may assume that L(−ℓ) ∈ int(E′). Since the collection of unit tangent vectors to the collection of horizontal geodesics at p is a circle, and in particular, connected, it follows by continuity that there exists a horizontal geodesic, \underline{L}, with \underline{L}(0) = p and \underline{L}(ℓ) ∈ ∂E. The conclusion of 2) now follows from sub-step 1).

Proof of 3). By 2), ∂E is a union of lines. If ∂E contains only parallel lines with the same projection, then it is contained in a vertical plane. Likewise, if ∂E contains only lines passing through some fixed point, then it is contained in the horizontal 2-plane through that point. Thus, we can assume that ∂E contains either a pair of parallel lines with distinct projections or a pair of skew lines. By Lemma 8.3, if ∂E contains a pair of parallel lines L_{1}, L_{2} with distinct projections, then distinct members of the family of lines {L(x)}_{x∈L_{1}} are skew lines which intersect π^{−1}(m(L_{1}, L_{2})). So we can assume that ∂E contains a pair of skew lines L_{1}, L_{2}.

Claim: If L_{1}, L_{2} are pair of skew lines, with L_{1} ∪ L_{2} ⊂ ∂E, then π^{−1}(π(L_{1}) ∩ π(L_{2})) ⊂ ∂E.

To see this, note that by Corollary 8.14, for every line L_{3} intersecting L_{1} and L_{2}, there is a parallel line, L_{4}, intersecting L_{1} and L_{2}, such that m(L_{3}, L_{4}) = π(L_{1}) ∩ π(L_{2}). Since by step 1), L_{3} ∪ L_{4} ⊂ ∂E, it follows from Lemma 8.3, that π^{−1}(m(L_{3}, L_{4})) ∈ ∂E.

For Y = Y (L_{1}, L_{2}) as in Lemma 8.9. Let U denote the component of ℝ^{2} \ Y, which intersects both branches of Y. Every point of V = U \(π(L_{1})∪π(L_{2})) is the intersection of a pair of distinct tangent lines of Y. Each such pair of lines lifts to a pair of skew lines L_{5}, L_{6} in ∂E. By the Claim, π^{−1}(π(L_{5}) ∩ π(L_{6})) ∈ ∂E, so π^{−1}(V) ⊂ ∂E. Thus ∂E has non-empty interior, as required. □

9. Proof of the stability of monotone sets

The proof of Theorem 4.13, i.e., the stability of monotone sets, has two main steps, A′), B′), which are quantitative versions of steps A), B), in the classification of monotone subsets of ℍ given in Section 8. In fact, A′) is just Lemma 7.8, which is proved in Section 11. In this section, assuming assuming some technical geometric preliminaries which are proved in Section 10,we carry out step B′), thereby completing the proof of Theorem 4.13.

The proof of B′) has substeps 1′)–3′), which correspond to substeps 1)–3) of B). Substeps 1′), 2′), are just Corollaries 7.27, 7.41, specialized to our specific context. Substep 3′) requires a substantial preliminary discussion; see Section 10, and in particular, Lemma 10.3 and Corollaries 10.27, 10.51. The point of the discussion in Section 10 is to quantify the following statement which occurs at the end of the first paragraph of the proof of substep 3): “Thus, we can assume that ∂E contains either a pair of parallel lines with distinct projections or a pair of skew lines”. Once this statement has been quantified, the proof of substep 3′) is completed by repeating, mutadis mutandis, the proof of substep 3).

The preliminaries to substep 3′), i.e., Section 10, constitute the part of the argument which necessitates assuming that E is ϵ^{a}-monotone on B_{ϵ^{−3}}(x), rather than on B_{1}(x). The following example shows that such an assumption cannot be entirely avoided even if ϵ^{a}-monotonicity is strengthened to monotonicity.

Example 9.1. Consider the set

(9.2)  E = {(x, y, z) | z ⩽ xy, y > 0} .

We claim that if B_{r}(p) ⊂ {(x, y, z) | y > 0}, then E ∩B_{r}(p) is monotone. This is equivalent to the statement that if a line L ∈ lines(ℍ) passes through two points in ∂(E) = {(x, y, z) | z = xy, y > 0}, then L is contained in ∂E. Note that the horizontal line L = (a, t, at) passes through (a, b, ab). If b > 0, then L is contained in ∂E. Conversely, if (a, b, ab), (a′, b′, a′b′) ∈ ∂E, then b, b′ > 0. If these points lie on a horizontal line, since H_{(a,b,ab)} = (x, y, ab−bx+ay), we get

(9.3)  a′b′ = ab − ba′ + ab′;

see (2.15). The solutions of (9.3) are: a′ = a , b′ arbitrary, which gives the above line L, or: a′ arbitrary, b′ = −b, which contradicts the assumption b′ > 0.

Proof of Theorem 4.13. Recall that in Theorem 4.13, we are given E ⊂ B_{1}(x) which is ϵ^{a}-monotone on B_{1}(x). Our goal is to find a half-space P ⊆ ℍ such that

\frac{L_{3} ((E ∩ B_{ϵ^{3}}(x))△P)}{L_{3} (B_{ϵ^{3}}(x))} ≲ ϵ .

For convenience of notation in the ensuing argument we will rescale the ball B_{1}(x) above by ϵ^{−3}. Thus our assumption is that E ⊂ B_{ϵ^{−3}}(x) is ϵ^{a}-monotone on B_{ϵ^{−3}}(x), and, for the sake of contradiction, that for no half-space P we have:

L_{3} ((E ∩ B_{1}(x))△P) ≲ ϵ .

This contrapositive assumption will be used via the following simple lemma. In what follows, for A ⊂ ℍ and ϵ > 0, the closed ϵ-tubular neighborhood of A is denoted by:

(9.4)  \overline{T_{ϵ}(A)} = \{x ∈ ℍ : d^{ℍ}(x, A) ⩽ ϵ\} .

Lemma 9.5. Let Q ⊂ ℍ be a 2-plane. Assume that for some ϵ, r ∈ (0, \frac{1}{2}) a subset E ⊂ ℍ satisfies:

∂_{ϵ,r}(E) ∩ B_{1}(x) ⊂ \overline{T_{ϵ}(Q)} .

Then there exists a half-space P ⊂ ℍ such that:

L_{3} ((E ∩ B_{1}(x))△P) ≲ ϵ .

Proof. The set B_{1}(x) \ \overline{T_{ϵ}(Q)} has at most two connected components, say C_{1}, C_{2} (one of which might be empty). Since ϵ < \frac{1}{2}, by continuity, for j ∈ \{1, 2\} we have C_{j} ⊂ int_{ϵ,r}(E) or C_{j} ⊂ int_{ϵ,r}(E′). For definiteness assume that C_{1} ⊂ int_{ϵ,r}(E). Let 𝔑 ⊂ C_{1} be an r-net in C_{1}. Thus the balls {B_{r/2}(y)}_{y∈𝔑} are disjoint, and the balls {B_{r}(y)}_{y∈𝔑} cover C_{1}. Moreover, since for each y ∈ 𝔑 we have y ∈ int_{ϵ,r}(E), we know that L_{3}(B_{r}(y) ∩ E′) ⩽ ϵL_{3}(B_{r}(y)). Hence

L_{3}(C_{1} ∩ E′) ⩽ ∑_{y∈N} L_{3}(B_{r}(y) ∩ E′) ⩽ ∑_{y∈N} ϵ · L_{3}(B_{r}(y)) = 16ϵ · ∑_{y∈𝔑} L_{3}(B_{r/2}(y))

= 16ϵ · L_{3} ( ⋃_{y∈𝔑} B_{r/2}(y)) ⩽ 16ϵ · L_{3} (B_{1+ \frac{r}{2}} (x)) ≲ ϵ .

This argument shows that for j ∈ {1, 2} either L_{3}(C_{j} ∩ E′) ≲ ϵ or L_{3}(C_{j} ∩ E) ≲ ϵ. Thus we can take P to be either one of the half-spaces bounded by Q, or a half space that contains B_{1}(x). □

By virtue of Lemma 9.5, we can assume from now on that for every 2-plane P ⊂ ℍ we have:

(9.6)  ∂_{c_{1}ϵ,ϵ^{k_{1}}}(E) ∩ B_{1}(x) ⊄ \overline{T_{c_{1}ϵ}(P)} ,

where k_{1} > 1, c_{1} > 0 are constants which will be determined presently.

By rescaling the metric d^{ℍ} by a suitable multiple of ϵ^{−3} we can apply Corollary 7.41 with α ≍ ϵ and u ≍ ϵ^{k_{1}+3}, and (after rescaling back to our present setting) deduce that provided

(9.7)  \begin{aligned}a & > 29 + 71(k_{1} + 3) = 242 + 71k_{1} , \\ k_{2} & < \frac{k_{1} + 3}{4} , \\ h_{2} & > 19 + 46(k_{1} + 3) = 157 + 46k_{1} , \end{aligned}

and ϵ is smaller than a small enough universal constant, we can associate to every point y ∈ ∂_{ϵ,ϵ^{k_{1}}}(E) ∩ B_{1}(x) an open set O_{y} of lines through the origin of H_{y}, such that for all L ∈ O_{y} we have:

(9.8)  L ([−c_{2}ϵ^{−3}, c_{2}ϵ^{−3}]) ⊂ ∂_{ϵ^{h_{2}},ϵ^{k_{2}}}(E) ,

for some small enough constant c_{2} > 0. We have used here the fact that the definition of the quantitative boundary in (7.3) is an open condition.

As we shall see in Section 10 (see Lemma 10.1 and Corollaries 10.27, 10.44, 10.51) the above discussion implies the following: If c_{1} in assumption (9.6) is a small enough universal constant, then there exists a pair of skew lines L, L′ ∈ lines(ℍ), with the following properties:

• The distance of L and L′ from x is at most \frac{c_{2}}{10}ϵ^{−3}.

• Both L and L′ intersect ∂_{ϵ^{h_{2}},ϵ^{k_{2}}}(E) ∩ B_{c_{2}ϵ^{−3}/10}(x).

• θ(L, L′), the angle between L and L′, is bounded away from 0 and π, say, tan θ(L, L′) ∈ [\frac{2}{5}, \frac{5}{2}]; for the definition of θ(L, L′) see (8.11).

• L, L′ have separation ≳ ϵ^{3}, i.e. d^{V} (L, L′) ≳ ϵ^{3}, where the vertical distance d^{V} ( · , ·) is as in (8.2).

We now use the lines L, L′ to perform substep 3′), that is, to produce a quantitative version of the argument in substep 3) of the classification of precisely monotone sets.

First of all, we will apply again Corollary 7.41 (rescaled, as before, by ≍ ϵ^{−3}) to deduce from the fact that L and L′ intersect ∂_{ϵ^{h_{2}},ϵ^{k_{2}}}(E) ∩ B_{c_{2}ϵ^{−3}/10}(x) that:

(9.9)  (L ∪ L′) ∩ B_{c_{3}ϵ^{−3}}(x) ⊂ ∂_{ϵ^{h_{3}},ϵ^{k_{3}}}(E) ,

where c_{3} > 0 is a universal constant, provided that:

(9.10)  \begin{aligned}a & > 29h_{2} + 71(k_{2} + 3) = 29h_{2} + 71k_{2} + 213 , \\ k_{3} & < \frac{k_{2} + 3}{4} , \\ h_{3} & > 19h_{2} + 46(k_{2} + 3) = 19h_{2} + 46k_{2} + 138 . \end{aligned}

Now, as in the non-quantitative proof, let Y = Y (L, L′) ⊂ ℝ^{2} be the hyperbola from Lemma 8.9, and let U be the component of ℝ^{2} \ Y which intersects both branches of Y. Let c_{4} be a small enough constant, and take a point q ∈ U such that B_{c_{4}ϵ^{3}}(q) ∩ ℝ^{2} ⊂ U and d^{ℍ}(q, π(L) ∩ π(L′)) ⩽ 10ϵ^{3}. As in the proof of substep 3) of the classification of monotone sets, using Lemma 8.9, any point z ∈ B_{c_{4}ϵ^{3}}(q) ∩ ℝ^{2} is of the form z = π(L^{∗}) ∩ π(L^{∗∗}), where, provided c_{4} is small enough, L^{∗}, L^{∗∗} are skew lines which intersect L ∩ B_{c_{3}ϵ^{−3}}(x) and L′ ∩ B_{c_{3}ϵ^{−3}}(x), both of which are contained in ∂_{ϵ^{h_{3}},ϵ^{k_{3}}}(E). Another application of Corollary 7.41 implies that:

(9.11)  (L^{∗} ∪ L^{∗∗}) ∩ B_{c_{5}ϵ^{−3}}(x) ⊂ ∂_{ϵ^{h_{4}},ϵ^{k_{4}}}(E) ,

provided that:

(9.12)  \begin{aligned}a & > 29h_{3} + 71(k_{3} + 3) = 29h_{3} + 71k_{3} + 213 , \\ k_{4} & < \frac{k_{3} + 3}{4} , \\ h_{4} & > 19h_{3} + 46(k_{3} + 3) = 19h_{3} + 46k_{3} + 138 . \end{aligned}

We continue to argue as is substep 3). We use Corollary 8.14 to deduce that z = m (\underline{L}^{∗}, \underline{L}^{∗∗}), where (once more, provided c_{4} is small enough), \underline{L}^{∗}, \underline{L}^{∗∗} are parallel lines which intersect the line segments L^{∗} ∩ B_{c_{5}ϵ^{−3}}(x) and L^{∗∗} ∩ B_{c_{5}ϵ^{−3}}(x), both of which are contained in ∂_{ϵ^{h_{4}},ϵ^{k_{4}}}(E). So, another application of Corollary 7.41 gives:

(9.13)  (\underline{L}^{∗} ∪ \underline{L}^{∗∗}) ∩ B_{c_{6}ϵ^{−3}}(x) ⊂ ∂_{ϵ^{h_{5}},ϵ^{k_{5}}}(E) ,

provided that:

(9.14)  \begin{aligned}a & > 29h_{4} + 71(k_{4} + 3) = 29h_{4} + 71k_{4} + 213 , \\ k_{5} & < \frac{k_{4} + 3}{4} , \\ h_{5} & > 19h_{4} + 46(k_{4} + 3) = 19h_{4} + 46k_{4} + 138 . \end{aligned}

By Lemma 8.3, any point on the fiber π^{−1}(z) lies on a line which touches both of \underline{L}^{∗}, \underline{L}^{∗∗}. Moreover (using the explicit formula for this line, which is contained in the proof of Lemma 8.3), since the vertical separation between L and L′ is ≳ ϵ^{3}, and z is an arbitrary point in B_{c_{4}ϵ^{3}}(q) ∩ ℝ^{2}, a (final) application of Corollary 7.41, together with the ball-box principle, shows that there exists p ∈ ℍ such that:

(9.15)  B_{r}(p) ⊂ ∂_{ϵ^{h_{6}},ϵ^{k_{6}}}(E) ∩ B_{ϵ^{−3}}(x),

where r ≍ ϵ^{3}, provided that:

(9.16)  \begin{aligned}a & > 29h_{5} + 71(k_{5} + 3) = 29h_{5} + 71k_{5} + 213 , \\ k_{6} & < \frac{k_{5} + 3}{4} , \\ h_{6} & > 19h_{5} + 46(k_{5} + 3) = 19h_{5} + 46k_{5} + 138 . \end{aligned}

Now, by choosing k_{1} sufficiently large, we will use (9.15) to contradict Lemma 7.8. provided k_{1} is large enough. Modulo the proofs of technical lemmas which were postponed to the following sections, this will conclude the proof of Theorem 4.13 Before doing so, note that for the conditions (9.7), (9.10), (9.12), (9.14), (9.16) to be satisfied we can ensure that (9.15) is satisfied for, say, a = 2^{40}k_{1}, k_{6} = 2^{−10}k_{1}, h_{6} = 2^{30}k_{1}. (In actuality, these are big overestimates.)

It remains to show how to choose k_{1} so that (9.15) will contradict Lemma 7.8. Since E is ϵ^{a}-monotone on B_{ϵ^{−3}}(x), it is also ≍ ϵ^{a−24}-monotone on B_{r}(p) (recall that r ≍ ϵ^{3}). By Lemma 7.8 we can find p′ ∈ B_{r/2}(p) such that p′ ∉ ∂_{α,r′}(E), where α ≍ ϵ^{(a−24)/2} and r′ ≍ r ≍ ϵ^{3}. Without loss of generality assume that p′ ∈ int_{α,r′}(E), so that

(9.17)  L_{3} (E′ ∩ B_{r′}(p′)) ⩽ αL_{3} (B_{r′}(p′)) ≍ ϵ^{\frac{a}{2} −12}ϵ^{12} = ϵ^{a/2} .

But, at the same time, p′ ∈ ∂_{ϵ^{h_{6}},ϵ^{k_{6}}}(E), which means that

(9.18)  L_{3} (E′ ∩ B_{ϵ^{k_{6}}}(p′)) > ϵ^{h_{6}}L_{3} (B_{ϵ^{k_{6}}}(p′)) ≍ ϵ^{h_{6}+4k_{6}} .

In order for (9.18) to contradict (9.17) assume that ϵ^{k_{6}} > r′, which would hold for small enough ϵ if k_{6} = \frac{k_{1}}{2^{10}} > 3. In this case B_{ϵ^{k_{6}}}(p′) ⊂ B_{r′}(p′), and the desired contradiction would follow (for small enough ϵ) if \frac{a}{2} > h_{6} +4k_{6}. Choosing k_{1} = 2^{12}, and thus a = 2^{52} and h_{6} = 2^{42} yields the required contradiction, and completes the proof of Theorem 4.13. □

10. Nondegeneracy of the initial configuration.

In this section, we prove the assertion on nondegeneracy of the initial configuration, which was used in the proof of substep 3′) given in Section 9; see the four items marked with bullets in paragraph following (9.8). Specifically under the assumptions of Lemma 10.3 below, we show that at distance ≲ ϵ^{−3} from x we can find a pair of skew lines in the controlled quantitative boundary which make standard angle as in (10.52), and have separation ≳ ϵ^{3}; see (10.5), (10.53).

Given a pair of (unordered) skew lines L, L̃, define 0 < θ(L, L̃) < π to be the angle between π(L) and π(L̃) which faces the sector which contains the hyperbola Y (L, L̃) from Lemma 8.9. The vertical distance d^{V} (L, L̃) is defined as in (8.2). As in (8.15), denote by b(L, L̃) the union of the (two) shortest horizontal segments joining L and L̃, and denote the length of each of these segments by 𝔡(L, L̃). Then with the geometric interpretation of the multiplication in ℍ, we get

(10.1)  \frac{1}{2} cot(\frac{1}{2}θ(L, L̃)) · (𝔡(L, L̃))^{2} = (d^{V} (L, L̃))^{2} .

Since tan (\frac{θ}{2}) ⩾ \frac{sin θ}{2} for all θ ∈ [0, π], it follows from (10.1) that

(10.2)  (𝔡(L, L̃))^{2} ≳ sin θ(L, L̃) · (d^{V} (L, L̃))^{2}.

In what follows, for A ⊂ ℍ and ϵ > 0, the closed ϵ-tubular neighborhood of A is denoted \overline{T_{ϵ}(A)} = \{x ∈ ℍ : d^{ℍ}(x, A) ⩽ ϵ\}. The required nondegeneracy of the initial configuration, namely the existence of the “quantitatively skew” lines L, L′ that are described in the paragraph preceding (9.9), is a consequence of the following Lemma 10.3. The hypothesis (10.4) below corresponds to the assumption concerning 2-planes that we arrived at in (9.6), and the discussion preceding (9.8). Recall that \overline{T_{ϵ}(·)} denotes the closed ϵ-tubular neighborhood, as defined in (9.4).

Lemma 10.3. Fix x ∈ ℍ, U ⊂ B_{1}(x) and ϵ ∈ (0, 1). For all y ∈ U, fix an open set O_{y} of lines through the origin of H_{y}. Assume that for all 2-planes P we have:

(10.4)  U ⊄ \overline{T_{ϵ}(P)} .

Then there exist y, z ∈ U and L_{y} ∈ O_{y}, L_{z} ∈ O_{z}, such that L_{y}, L_{z} are skew and:

(10.5)  (𝔡(L_{y}, L_{z}))^{2} ≳ sin (θ(L_{y}, L_{z})) · (d^{V} (L_{y}, L_{z}))^{2} ≳ ϵ^{6} .

yes

Proof. Denote the Euclidean distance in ℝ^{2} by d( · , ·). Fix y_{1} ∈ U. Let V denote the unique vertical 2-plane containing L_{y_{1}}. It follows from (10.4), with P = V, that there exists y_{2} ∈ U such that

(10.6)  d(π(L_{y_{1}}), π(y_{2})) ⩾ ϵ .

Let H = H_{q} denote the unique horizontal 2-plane containing the line, L_{y_{1}}, and the point y_{2} ∉ L_{y_{1}}. Note that q ∈ L_{y_{1}}. By (10.4), there exists y_{3}, such that

(10.7)  d^{ℍ}(y_{3}, H_{q}) ⩾ ϵ .

For arbitrary q, y_{3} ∈ ℍ, we have

(10.8)  d^{ℍ}(q, H_{y_{3}}) = d^{ℍ}(y_{3}, H_{q}) .

To see (10.8), note that by left-invariance of d^{ℍ}, the left-hand side equals d^{ℍ}(y_{3}^{−1} · q, H_{(0,0,0)}), and the right-hand side equals d^{ℍ}(q^{−1} · y_{3}, H_{(0,0,0)}). If z ∈ H_{(0,0,0)} is closest to y_{3}^{−1} · q, then z^{−1} ∈ H_{(0,0,0)}, and by (2.18), d^{ℍ}((y_{3})^{−1} · q, z) = d^{ℍ}(q^{−1} · y_{3}, z^{−1}). By symmetry, this gives (10.7).

Since d^{ℍ}(q, L_{y_{3}}) ⩾ d^{ℍ}(q, H_{y_{3}}), from (10.7), (10.8), we get

(10.9)  d^{ℍ}(q, L_{y_{3}}) ⩾ ϵ .

Since O_{y_{1}}, O_{y_{2}}, O_{y_{3}} are open, we can assume that no two of L_{y_{1}}, L_{y_{2}}, L_{y_{3}} are parallel. By applying a translation we may also assume that q = (0, 0, 0). Thus, after applying a suitable rotation we may assume that L_{y_{1}} is the x-axis and y_{1} = (a, 0, 0), y_{2} = (b, c, 0) for some a, b, c ∈ ℝ. Set L_{y_{1}} ∩ π(L_{y_{2}}) = n_{3} = (s, 0, 0) and let α ∈ (0, π) denote the angle between L_{y_{1}} and π(L_{y_{2}}).

It follows from (10.6) that |c| ⩾ ϵ. Since |a − b| + |c| + \sqrt{|ac|} ≍ d^{ℍ}(y_{1}, y_{2}) ⩽ 2, we have:

(10.10)  |a| ≲ \frac{1}{ϵ} and |a − b| ≲ 1.

Note that

(10.11)  sin α = \frac{c}{d(π(y_{2}), n_{3})} ≍ \frac{c}{c + |b − s|} ⩾ \frac{ϵ}{ϵ + |b| + |s|},

and by the geometric interpretation of the multiplication,

(10.12)  (d^{V} (L_{y_{1}}, L_{y_{2}}))^{2} = |c| · |s| ⩾ ϵ|s|.

It follows by multiplying together (10.11) and (10.12) that we may assume that ϵ + |b| ⩾ |s|, since otherwise (10.5) holds with ϵ^{6} replaced by ϵ^{2}. Using (10.10) we deduce that |b|, |s| ≲ \frac{1}{ϵ}, and therefore it follows from (10.11) that

(10.13)  sin α ≳ ϵ^{2} .

Using (10.12) and (10.13) that we may assume that

(10.14)  d(n_{3}, q) = |s| ≲ ϵ^{3} ,

since otherwise (10.5) holds.

Let S denote the triangle with vertices π(L_{y_{2}})∩π(L_{y_{3}}) = n_{1}, L_{y_{1}} ∩π(L_{y_{3}}) = n_{2} and n_{3}. Let α_{j} denote the angle at the vertex n_{j} (thus α_{3} is either α or π − α). Put ℓ_{j} = d(n_{j+1}, n_{j+2}). (Here and in the rest of the proof of Lemma 10.3, indices are taken mod 3.) It follows from (10.13) that there exists j ∈ {1, 2}, such that

(10.15)  sin α_{j} ⩾ \frac{c}{2}ϵ^{2} .

Write {k} = {1, 2} \ {j}. From (10.13), (10.15), we may assume that

(10.16)  (d^{V} (L_{y_{1}}, L_{y_{2}}))^{2} ≲ ϵ^{4} ,
(10.17)  (d^{V} (L_{y_{k}}, L_{y_{3}}))^{2} ≲ ϵ^{4} ,

since otherwise (10.5) holds.

From the geometric interpretation of the multiplication, it follows that there exists r ∈ {1, 2, 3} such that

(10.18)  (d^{V} (L_{r+1}, L_{r+2}))^{2} ≳ area(S) = \frac{1}{2}ℓ_{1}ℓ_{2} sin α_{3} .

By multiplying both sides of (10.18) by sin α_{r} and using the law of sines to express sin α_{r} in terms of sin α_{3}, we obtain with (10.13) and the triangle inequality,

(10.19)  (d^{V} (L_{r+1}, L_{r+2}))^{2} sin α_{r} ≳ (sin α_{3})^{2} · min {ℓ_{1}^{2}, ℓ_{2}^{2}} ≳ ϵ^{4} · min {ℓ_{1}^{2}, ℓ_{2}^{2}} .

Arguing similarly with (10.15), we have:

(10.20)  (d^{V} (L_{r+1}, L_{r+2}))^{2} sin α_{r} ≳ ϵ^{4} · min {ℓ_{k}^{2}, ℓ_{3}^{2}} .

We may therefore assume that min \{ℓ_{1}^{2}, ℓ_{2}^{2}\} ⩽ \frac{ϵ^{2}}{16} and min \{ℓ_{k}^{2}, ℓ_{3}^{2}\} ⩽ \frac{ϵ^{2}}{16}, since otherwise (10.5) holds. By the triangle inequality ℓ_{k} ⩽ ℓ_{j} + ℓ_{3}, and therefore

(10.21)  ℓ_{k} ⩽ \frac{1}{2}ϵ .

By adding (10.14), (10.16), (10.17), (10.21), we get d^{ℍ}(L_{y_{3}}, q) ⩽ \frac{1}{2}ϵ + O(ϵ^{2}), which contradicts (10.9) for ϵ small enough. This contradiction completes the proof. □

In deriving the consequences of Lemma 10.3, we will work in coordinates. Thus, we write L_{1}, L_{2} for L_{y}, L_{z}. As in (8.10), we can canonically assume that:

L_{1} = (t, wt, c), L_{2} = (s, −ws, −c) .

As in (8.11), the angle 0 < θ(L_{1}, L_{2}) < π is determined by tan (\frac{1}{2}θ(L_{1}, L_{2})) = w. Let b_{+}(L, L̃), b_{−}(L, L̃) contain the shortest line joining L_{1}, L_{2}; see (8.15). Thus,

b_{±}(L_{1}, L_{2}) = (±\sqrt{\frac{c}{w}}, u, ±\sqrt{\frac{c}{w}}u) ,

and so,

(10.22)  d^{ℍ}(b_{+}(L_{1}, L_{2}), b_{−}(L_{1}, L_{2})) = 2\sqrt{\frac{c}{w}} .

Put:

(10.23)  e_{i,±}(L_{1}, L_{2}) = L_{i} ∩ b_{±}(L_{1}, L_{2}) ,

or equivalently,

(10.24)  \begin{aligned}e_{1,+}(L_{1}, L_{2}) & = (\sqrt{\frac{c}{w}}, \sqrt{cw}, c) , \\ e_{2,+}(L_{1}, L_{2}) & = (\sqrt{\frac{c}{w}}, −\sqrt{cw}, −c) . \end{aligned}

Then with the geometric interpretation of the multiplication in ℍ, (d^{V} (L_{1}, L_{2}))^{2} is twice the area of the triangle with vertices π(L_{1}) ∩ π(L_{2}), π(e_{1,+}(L_{1}, L_{2})), π(e_{2,+}(L_{1}, L_{2})). It follows that (d^{V} (L_{1}, L_{2}))^{2} = 2c. Note that

𝔡(L_{1}, L_{2}) = d^{ℍ}((e_{1,±}(L_{1}, L_{2}), e_{2,±}(L_{1}, L_{2})) .

Therefore,

(10.25)  𝔡(L_{1}, L_{2}) = 2\sqrt{cw} .

Equation (10.1) now becomes:

(10.26)  (𝔡(L_{1}, L_{2}))^{2} = 2w · (d^{V} (L_{1}, L_{2}))^{2} .

Corollary 10.27 below will be derived directly from Lemma 10.3 without further reference to the assumption on 2-planes. The proof will rely on the following additional information. Write o_{1} = y and o_{2} = z. Since o_{1}, o_{2} ∈ B_{1}(x), we have d^{ℍ}(o_{1}, o_{2}) < 2, which implies d^{V} (o_{1}, o_{2}) < 2, d(π(o_{1}), π(o_{2})) < 2.

We put

\begin{aligned}o_{1} & = (t_{1}, wt_{1}, c) , \\ o_{2} & = (s_{2}, −ws_{2}, −c) , \end{aligned}

where without loss of generality, we can assume either case i), t_{1} ⩾ 0, s_{2} ⩽ 0, or case ii), t_{1} ⩾ 0, s_{2} ⩾ 0.

Below, to avoid confusion, we will write Ω for the constant c, in (10.5). We also assume ϵ ⩽ 1.

Corollary 10.27. The following bound holds true:

(10.28)  c · \frac{w}{1 + w^{2}} ≳ ϵ^{6} .

Moreover,

i) If t_{1} ⩾ 0, s_{1} ⩽ 0,

(10.29)  ϵ^{6} ≲ w ≲ ϵ^{−6} .
(10.30)  ϵ^{3}\sqrt{1 + w^{2}} ≲ 𝔡(L_{1}, L_{2}) ≲ \sqrt{w} .
(10.31)  d^{ℍ}(o_{1}, e_{1,+}(L_{1}, L_{2})) ≲ \sqrt{w} + \frac{1}{\sqrt{w}} .

(10.32)  ϵ^{6} ≲ c ≲ 1 .
(10.33)  |t_{1}| + |s_{2}| ≲ 1 .
(10.34)  |t_{1} + s_{2}| ≲ \frac{1}{w} .
(10.35)  w · |t_{1}| · |s_{2}| ≲ 1 .

ii) If t_{1} ⩾ 0, s_{2} ⩾ 0,

(10.36)  w ≲ ϵ^{−6} .
(10.37)  ϵ^{3}\sqrt{1 + w^{2}} ≲ 𝔡(L_{1}, L_{2}) ≲ \sqrt{1 + w} .
(10.38)  d^{ℍ}(o_{1}, e_{1,+}(L_{1}, L_{2})) ≲ ϵ^{−3} .
(10.39)  ϵ^{6} ≲ c ≲ 1 + \frac{1}{w} .
(10.40)  |t_{1} − s_{2}| ≲ 1 .
(10.41)  t_{1} + s_{2} ≲ \frac{1}{w} .
(10.42)  |c − wt_{1}s_{2}| ≲ 1 .

Proof. Since sin θ(L_{1}, L_{2}) = 2 · \frac{w}{1+w^{2}} , (d^{V} (L_{1}, L_{2}))^{2} = 2c, (10.28) is just a rewriting of (10.5). The lower bounds in (10.30), (10.37), follow from (10.28) and (10.25).

Next note that since d^{ℍ}(o_{1}, o_{2}) ⩽ 2, from the box-ball principle we have

(10.43)  |t_{1} − s_{2}| + w|t_{1} + s_{2}| + \sqrt{|2c − 2wt_{1}s_{2}|} ≲ 1 .

Case i). Since t_{1} ⩾ 0, s_{2} ⩽ 0 implies that in the third term on the right-hand side of (10.43) we have −wt_{1}s_{2} > 0, we get c ≲ 1, which gives the upper bound in (10.32) and since 𝔡(L_{1}, L_{2}) = 2\sqrt{cw}, the upper bound in (10.29) as well. Using c ≲ 1 and multiplying both sides of (10.28) by \frac{1+w^{2}}{w}, gives (10.29). Relations (10.33)–(10.35) follow immediately from (10.43) and t_{1} ⩾ 0, s_{2} ⩽ 0.

To prove (10.31), by considering the cases, w ⩽ 1, w ⩾ 1, and using the box ball principle, (10.43), it suffices to show that

t_{1} + \sqrt{\frac{c}{w}} ≲ \frac{1}{\sqrt{w}} .

Since c ≲ 1 we get \sqrt{\frac{c}{w}} ≲ \frac{1}{\sqrt{w}}. From (10.33) we get t_{1} ≲ 1, which gives the case w ⩽ 1. For w ⩾ 1, relations (10.34), (10.35) imply t_{1} ≲ \frac{1}{\sqrt{w}}, which completes the proof.

Case ii). Relation (10.39) was already shown in the proof of case i). By using t_{1} ⩾ 0, s_{2} ⩾ 0, relations (10.40)–(10.42) follow directly from (10.43). From (10.41),

c ≲ 1 + wt_{1}s_{2} ≲ 1 + w · (t_{1} + s_{2})^{2} ,

which, by (10.41), gives the upper bound for c in (10.39). From this, the upper bound in (10.37) follows immediately, as does the implication c ⩽ 5 if w ⩾ 1. This, together with (10.28), gives the upper bound for w in (10.36).

To prove (10.38), note that from (10.42), by dividing through by w and factoring, we get,

|\sqrt{\frac{c}{w}} − \sqrt{t_{1}s_{2}}| · |\sqrt{\frac{c}{w}} + \sqrt{t_{1}s_{2}}| ≲ \frac{1}{w} ,

which, together with (10.41), gives

(1 + w) |\sqrt{\frac{c}{w}} − t_{1}| ≲ (1 + w)\frac{1}{\sqrt{wc}} + (1 + w) |\sqrt{t_{1}s_{2}} − t_{1}| .

From (10.40), in case w ⩽ 1, and (10.41), in case w ⩾ 1, it follows that the second term on the right-hand side is ≲ 1. By using the lower bound in (10.30) to bound the first term on the right-hand side, the proof is complete. □

In the next corollary, by considering separately the cases 0 < w ⩽ 1, 1 ⩽ w < ∞, we obtain estimates which depend only on ϵ.

Corollary 10.44.

1) If 0 < w ⩽ 1, then

(10.45)  ϵ^{3} ≲ 𝔡(L_{1}, L_{2}) ≲ 1 ,

(10.46)  d^{ℍ}(o_{1}, e_{1,+}(L_{1}, L_{2})) ≲ ϵ^{−3} .

2) If 1 ⩽ w < ∞,

(10.47)  ϵ^{3} ≲ d^{ℍ}(b_{+}(L_{1}, L_{2}), b_{−}(L_{1}, L_{2})) ≲ 1

(10.48)  ϵ^{3} ≲ 𝔡(L_{1}, L_{2}) ≲ ϵ^{−3} .

(10.49)  d^{ℍ}(o_{1}, e_{1,+}(L_{1}, L_{2})) ≲ ϵ^{−3} .

Proof. Relation (10.47), i.e., the bound on 2\sqrt{\frac{c}{w}}, for w ⩾ 1, is a direct consequence of (10.29), (10.32), (10.36), (10.39). The remaining relations can be read off from Corollary 10.51. □

If w ⩾ 1, as a consequence of (10.47) we obtain a pair of parallel lines b_{±}(L_{1}, L_{2}) whose separation, 2\sqrt{\frac{c}{w}}, is bounded below by ≳ ϵ^{3} and above by a universal constant, and with a transversal L_{1}, such that (10.48), (10.49) hold. This will suffice for our application.

If w ⩽ 1, although 2\sqrt{\frac{c}{w}} is not bounded above, 𝔡(L_{1}, L_{2}) is bounded above by a universal constant, and below by ≳ ϵ^{3}, and d^{ℍ}(o_{1}, e_{1,+}(L_{1}, L_{2})) is bounded by a definite multiple of ϵ^{−3}. In this case we obtain a pair of skew lines making standard angle and controlled separation as follows.

Let

r = \sqrt{1 + w^{2}} · \sqrt{\frac{c}{w}}

denote the distance from the origin in ℝ^{2} to (\sqrt{\frac{c}{w}}, ±\sqrt{cw})) = π(e_{1,±}(L_{1}, L_{2})). The points

\begin{matrix}\frac{𝔡(L_{1}, L_{2}) + r}{r} · (\sqrt{\frac{c}{w}}, \sqrt{cw}) , \\ \frac{r}{𝔡(L_{1}, L_{2}) + r} · (\sqrt{\frac{c}{w}}, \sqrt{cw}) , \end{matrix}

lie on the projection of a line, L ∈ lines(H), with z_{i} = L ∩ L_{i}, where

\begin{aligned}d^{ℍ}(z_{1}, e_{1,+}(L_{1}, L_{2})) & = 𝔡(L_{1}, L_{2}) , \\ d^{ℍ}(z_{2}, e_{2,+}(L_{1}, L_{2})) & = \frac{r}{r + 𝔡(L_{1}, L_{2})} · 𝔡(L_{1}, L_{2}) . \end{aligned}

By direct computation, the slope m(L) of π(L) satisfies

(10.50)  \frac{2}{3} ⩽ m(L) ⩽ \frac{5}{2} .

From this we get:

Corollary 10.51. The lines L, b_{+}(L_{1}, L_{2}) are skew. The point π(L) ∩ π(b_{+}(L_{1}, L_{2})) lies on the line segment from π(e_{1,+}(L_{1}, L_{2})) to π(e_{2,+}(L_{1}, L_{2})). Moreover,

(10.52)  \frac{2}{5} ⩽ tan θ(L, b_{+}(L_{1}, L_{2})) ⩽ \frac{3}{2} ,

and

(10.53)  \sqrt{\frac{2}{3}} · 𝔡(L_{1}, L_{2}) ⩽ d^{V} (L, b_{+}(L_{1}, L_{2})) ⩽ 𝔡(L_{1}, L_{2}) .

Proof. Relation (10.52) follows directly from (10.50). By the discussion above, the triangle with vertices, (0, 0), π(e_{1,+}(L_{1}, L_{2})), π(e_{2,+}(L_{1}, L_{2})), and the triangle with vertices (0, 0), π(z_{1}), π(z_{2}), have equal areas. It follows that the triangles with vertices, π(e_{1,+}(L_{1}, L_{2})), π(z_{1}), π(L) ∩ π(b_{+}(L_{1}, L_{2}), π(e_{2,+}(L_{1}, L_{2})), π(z_{2}), π(L) ∩ π(b_{+}(L_{1}, L_{2}), (whose union is the symmetric difference of the previous ones) have equal areas as well. From this and the geometric interpretation of multiplication, we get (10.53). □

11. Proof of Lemma 7.8

In this section we prove Lemma 7.8. We begin with some measure theoretic preliminaries which play a role here and in Section 12. Then we give the proof for case of precisely monotone sets (for which the preliminaries are not required); compare also the proof in [23]. Finally, show how to modify the argument to obtain the general case of Lemma 7.8.

Measure theoretic preliminaries. Recall that L_{3} denotes Lebesgue measure on ℍ = ℝ^{3} which is a Haar measure of ℍ. Given L ∈ lines(ℍ) we denote by H_{L}^{1} the Hausdorff measure induced by the metric d^{ℍ} on L. Recall that N denotes the unique left invariant invariant measure on lines(ℍ) which is normalized so that N (lines(B_{1}(p))) = 1. Given L ∈ lines(ℍ) we denote by [L] its Heisenberg parallelism class, i.e., [L] = {gL : g ∈ ℍ}. ℍ acts transitively on [L]. Therefore there exists a left invariant measure μ_{[L]} on [L], normalized so that for every measurable A ⊂ ℍ we have

(11.1)  ∫_{[L]} H_{L′}^{1}(L′ ∩ A) dμ_{[L]}(L′) = L_{3}(A) .

The space of all parallelism classes will be denoted 𝔓 = {[L] : L ∈ lines(ℍ)}. Each such parallelism class [L] is uniquely determined by an angle θ ∈ [0, 2π), corresponding to the angle of π(L) ⊂ ℝ^{2} (recall that the lines L ∈ lines(ℍ) are oriented). We thus there is an induced measure dθ on 𝔓 which corresponds to the standard measure on the circle S^{1}. By uniqueness there exists a constant c > 0 such that for all integrable f : lines(ℍ) → ℝ we have:

(11.2)  ∫_{lines(ℍ)} f dN = c ∫_{𝔓} (∫_{L′∈[L]} f(L′)dμ_{[L]}(L′)) dθ([L]) .

Let ℙ ⊂ lines(ℍ)×ℍ denote the space of oriented pointed lines, i.e., ℙ = {(L, x) : x ∈ L}. We shall use below the measure ν on ℙ which is defined by setting for every compactly supported continuous f : ℙ → ℝ:

(11.3)  ∫_{ℙ} f dν = ∫_{lines(ℍ)} (∫_{L} f(L, x)dH_{L}^{1}(x)) dN (L) .

In the proof of Lemma 7.8 we shall use the space of configurations C, where a configuration is a quadruple (L, x_{1}, x_{2}, [L′]), where L ∈ lines(ℍ), x_{1}, x_{2} ∈ L, and [L′] ∈ 𝔓 (i.e., a doubly pointed line and a parallelism class). C carries two measures σ_{1}, σ_{2}, which are defined as follows. Given f : C → ℝ which is continuous and compactly supported let: (11.4)

∫_{C} f dσ_{1} = ∫_{lines(ℍ)} ∫_{𝔓} (∫_{L×L} f(L, x_{1}, x_{2}, [L′]) d (H_{L}^{1} × H_{L}^{1}) (x_{1}, x_{2})) dθ([L′]) dN (L) ,

(11.5) ∫_{C} f dσ_{2}

= ∫_{𝔓} (∫_{[L′]×[L′]} (∫_{L_{1}} f(L(x), x, L(x) ∩ L_{2}, [L′])dH_{L_{1}}^{1}(x)) d (μ_{[L′]} × μ_{[L′]}) (L_{1}, L_{2})) dθ([L′]),

where in (11.5), as in Section 8, given two parallel lines L_{1}, L_{2} ∈ [L′] with distinct projections and x ∈ L_{1}, L(x) denotes the unique element of lines(ℍ) which passes through x and intersects L_{2}. (In Section 8, L(x) ∩ L_{2} was denoted x^{∗}).

Each of σ_{1}, σ_{2} is absolutely continuous with respect to the other. Moreover, given a compact subset of the Heisenberg group K ⊂ ℍ and a > 0, let C(K, a) denote the set of configurations (L, x_{1}, x_{2}, [L′]) ∈ C with x_{1}, x_{2} ∈ K and d (π(x_{1}L′(0)^{−1}L′), π(x_{2}L′(0)^{−1}L′)) ⩾ a, i.e., the unique lines in [L′] which pass through x_{1}, x_{2} have projections of distance at least a, and x_{1}, x_{2} are in the compact set K. One checks from the definitions that on the compact set C(K, a), the Radon–Nikodym derivatives \frac{dσ_{1}}{dσ_{2}} , \frac{dσ_{2}}{dσ_{1}} are continuous. Hence for every measurable A ⊂ C(K, a), we have

(11.6)  σ_{1}(A) ≍ σ_{2}(A),

where the implied constants depend only on K and a. This observation will be used in the proof of Lemma 7.8 below.

A consequence of small nonconvexity. Recall that the nonconvexity NC_{B_{r}(x)}(E, L) was defined in (4.7). The following consequence of small nonconvexity will be used in the present section and repeatedly in Section 12 (where the main result concerns δ-convex sets, which are more general than δ-montone sets).

Lemma 11.7. Fix p ∈ ℍ and E ⊂ ℍ. Let L ∈ lines(ℍ) satisfy NC_{B_{1}(p)}(E, L) < δ. Assume that [c, d] ⊂ [a, b] ⊂ L ∩ B_{1}(p) and

(11.8)  H_{L}^{1}([a, c] ∩ E) > δ ,  H_{L}^{1}([d, b] ∩ E) > δ ,

then

H_{L}^{1}([c, d] ∩ E′) ⩽ δ .

Proof. For all sufficiently small η > 0, we have H_{L}^{1}([a, c] ∩ E) ⩾ δ + η, H_{L}^{1}([d, b] ∩ E) ⩾ δ + η. If I ⊂ L ∩ B_{1}(p) is an interval which exceeds the infimum on the right-hand side of (4.7) by at most η/2, then the intersection of I with both [a, c] and [d, b] must have positive H_{L}^{1} measure. Thus, I = [e, f] ⊃ [c, d]. By the choice of I, we also have H_{L}^{1}([e, f] ∩ E′) < δ + η/2, which implies H_{L}^{1}([c, d] ∩ E′) < δ + η/2. Letting η tend to 0 completes the proof. □

The case of precisely monotone sets. We call a set E ⊂ B_{1}(p) precisely monotone if E ∩ L and E′ ∩ L are connected for all L ∈ lines(ℍ). Therefore, given such a pair (E, L), either L ∩ B_{1}(p) ⊂ E, L ∩ B_{1}(p) ⊂ E′, or there exists a unique q_{L,E} ∈ L such that (L \ {q_{L,E}}) ∩ B_{1}(p) consists of two open intervals, one of which is contained in E and the other of which is contained in E′.

Choose a pair of parallel lines, L_{1}, L_{2} with distinct projections and recall that X = X(L_{1}, L_{2}) denotes the ruled surface which is the union of lines, L(x), passing through L_{1} and L_{2}. Here, {x} = L(x) ∩ L_{1}. Note that ℍ acts on L_{1}, L_{2}, X(L_{1}, L_{2}) by left translation.

Lemma 11.9. Fix p ∈ ℍ. There is a left-invariant function defined on pairs L_{1}, L_{2} of parallel lines with distinct projections and taking values in 6-tuples of relatively open subsets of the surface X(L_{1}, L_{2}) ∩ B_{1}(p), {W_{j}(L_{1}, L_{2})}_{j=1}^{6}, such that if E is a precisely monotone subset of B_{1}(p), then for some j(L_{1}, L_{2}, E) ∈ {1, 2, 3, 4, 5, 6}, W (L_{1}, L_{2}, E) := W_{j(L_{1},L_{2},E)}(L_{1}, L_{2}) consists entirely of points of E, or entirely of points of E′.

Proof. We can assume that say L_{1} = (t, b, −bt), L_{2} = (s, −b, −bs), with \frac{1}{2} ⩽ b ⩽ 1. Then, in the notation of Lemma 8.3, for x = (t, b, −bt) ∈ L_{1}, we have x^{∗} = (−t, −b, bt), L(x) = (r, r/b, −bt).

Let I_{1}, I_{2}, I_{3}, denote the intervals, (0, \frac{1}{6}), (\frac{1}{6}, \frac{1}{3}), (\frac{1}{3}, \frac{1}{2}), respectively, and let −I_{j} be defined by t ∈ −I_{j} if and only −t ∈ I_{j}. Define W_{1}(L_{1}, L_{2}) to be B_{1}(p) intersected with the union of those segments of the lines L(x) which join x ∈ L_{1}(I_{1}) to x^{∗} ∈ L_{2}(−I_{1}). Also, define W_{2}(L_{1}, L_{2}) to be B_{1}(p) intersected with the union of those subrays of the lines L(x) for which x ∈ L_{1}(I_{1}), x^{∗} ∈ L_{2}(−I_{1}), whose endpoint is x and which are disjoint to the segment [x, x^{∗}]. Define W_{3}(L_{1}, L_{2}), W_{4}(L_{1}, L_{2}) and W_{5}(L_{1}, L_{2}), W_{6}(L_{1}, L_{2}) analogously, corresponding to j = 2, 3, respectively.

There exists some i(L_{1}, L_{2}, E) ∈ {1, 2, 3}, such that q_{E,L_{1}} ∉ L_{1}(I_{i}) and q_{E,L_{2}} ∉ L_{2}(−I_{i}) (where possibly, one or both of q_{E,L_{1}}, q_{E,L_{1}} do not exist altogether).

Fix i = i(L_{1}, L_{2}, E) as above. There are four possibilities:

1a) L_{1}(I_{i}) ⊂ E, L_{1}(−I_{i}) ⊂ E,

1b) L_{1}(I_{i}) ⊂ E′, L_{1}(−I_{i}) ⊂ E′,

2a) L_{1}(I_{i}) ⊂ E, L_{2}(−I_{i}) ⊂ E′,

2b) L_{1}(I_{i}) ⊂ E′, L_{2}(−I_{i}) ⊂ E.

In cases 1a), 1b), we can take j(L_{1}, L_{2}, E) = 2i − 1, while in cases 2a), 2b), we can take j(L_{1}, L_{2}, E) = 2i. □

Take a small interval [0, d] in the center of ℍ and consider all left translates g(X(L_{1}, L_{2})) = X(g(L_{1}), g(L_{2})), where g ∈ [0, d]. Clearly, for some subset S = S(L_{1}, L_{2}, E) ⊂ [0, d], of measure ⩾ \frac{d}{12}, if g ∈ S, then the integers j(g(L_{1}), g(L_{2}), E) will all coincide and in addition, either for all g ∈ S, W (g(L_{1}), g(L_{2}), E) ⊂ E, or for all g ∈ S, W (g(L_{1}), g(L_{2}), E) ⊂ E′. Without essential loss of generality, we can assume 0 ∈ S and say W (L_{1}, L_{2}, E) ⊂ E. Hence, W (g(L_{1}), g(L_{2}), E) = g(W (L_{1}, L_{2}, E)) ⊂ E, for all g ∈ S.

Choose an interior point y ∈ W (L_{1}, L_{2}, E) ∩ B_{1}(p), lying at a definite distance from the boundary, choose a line L(x) such that y ∈ L(x), and choose L ∈ lines(ℍ) making a definite angle with L(x). Let [L] denote the collection of lines parallel to L. By Lemma 8.3 (and continuity) we can assume that d has been chosen so small that if g ∈ [0, d], L′ ∈ [L] and L′ ∩ g(X(L_{1}, L_{2})) ∩ B_{10d}(y) ≠ ∅, then L′ intersects g(X(L_{1}, L_{2})) transversely. Parameterize each such L′ such that L′(0) = L′ ∩ W (L_{1}, L_{2}, E). Let J denote the smallest interval containing S. Then the length of J is ⩾ \frac{d}{12} and by monotonicity of E, we have L′(J) ⊂ E. This completes the proof in the precisely monotone case.

Proof of Lemma 7.8. Suppose now that E ⊂ B_{1}(p) is ϵ^{2}-monotone on B_{1}(p). Choose a measurable mapping L ↦ I_{L,E} ⊂ L (e.g., via an application of the measurable selection theorem in [44]) such that I_{L,E} ∩ B_{1}(p), (I_{L,E})′ ∩ B_{1}(p) are intervals and for almost all L,

(11.10)  H_{L}^{1}(I_{L,E} △ (E ∩ L ∩ B_{1}(p)) ⩽ 2 · NM_{B_{1}(p)}(L, E) .

Let \overline{q}_{L,E} denote the common boundary point of I_{L,E}, (I_{L,E})′.

Define I_{1}, I_{2}, I_{3} as above. Given a pair L_{1}, L_{2} of parallel lines with distinct projections, define i(L_{1}, L_{2}, E) as above, but replacing q_{L,E} by \overline{q}_{L,E}. Then, mutatis mutandis, define cases 1a)–2b) and {W_{j}(L_{1}, L_{2})}_{j=1}^{6} , j(L_{1}, L_{2}, E), W (L_{1}, L_{2}, E) as above.

In the Claim below, Center(ℍ) is equipped with its natural measure L and W (L_{1}, L_{2}, E) ⊂ X(L_{1}, L_{2}) is equipped with the natural surface measure M on X(L_{1}, L_{2}).

Claim. There exists a universal constant c > 0 with the following properties. Assume that E ⊂ B_{1}(p) is ϵ^{2}-monotone on B_{1}(p). Then there exists a pair of parallel lines L_{1}, L_{2} whose projections lie at distance ⩾ c, such that for a fraction ⩾ c of g ∈ Center(ℍ) ∩ B_{1}(p), the surface W (g(L_{1}), g(L_{2}), E) has measure ⩾ c and, apart from a subset of measure ⩽ ϵ/c, it consists either entirely of points of E or entirely of points in E′.

Assume provisionally, that the Claim holds. Since E ⊂ B_{1}(p) is ϵ^{2}-monotone, by (11.2) with f(L) = NM_{B_{1}(p)}(E, L) and Markov’s inequality (3.15), we can choose a parallelism class [L] of lines which are all a definite amount transverse to X(L_{1}, L_{2}) (i.e., the angle between these lines and the surface X(L_{1}, L_{2}) is larger than a universal constant) such that apart from a subset of measure ≲ ϵ of lines in [L], the remaining lines are all ≲ ϵ-monotone. From this, together the Claim and Lemma 11.7, we directly obtain Lemma 7.8.

Proof of the Claim. Rather than studying the space of surfaces X(L_{1}, L_{2}) directly, it is advantageous to decompose each such X(L_{1}, L_{2}) into its collection of ruling lines, L, and then to lift considerations to space of all triples (L_{1}, L_{2}, L), where a triple (L_{1}, L_{2}, L) is a set of lines L_{1}, L_{2}, L ∈ lines(B_{1}(p)), such that L_{1}, L_{2} are parallel in the Heisenberg sense, and L_{1} ∩ L = x_{1}, L_{2} ∩ L = x_{2} are nonempty and lie in B_{1}(p). Recall the set of configurations C that was defined in the paragraph following (11.3). Each configuration (L, x_{1}, x_{2}, [L′]) ∈ C with x_{1}, x_{2} ∈ B_{1}(p) determines, and is determined by, the triple (L_{1}, L_{2}, L), where L_{1} = x_{1}L′(0)^{−1}L′ and L_{2} = x_{2}L′(0)^{−1}L′ (thus using previous notation, L = L(x_{1}) and x_{2} = x_{1}^{∗}). Let C_{1} denote the set of configurations (L, x_{1}, x_{2}, [L′]) ∈ C with x_{1}, x_{2} ∈ B_{1}(p).

Definition 11.11. A pointed line (L, x) is called consistent if one of the following two options holds true: either x ∈ I_{L,E} and x ∈ E, or x ∈ (I_{L,E})′ ∩ B_{1}(p) and x ∈ E′. A configuration (L, x_{1}, x_{2}, [L′]) is called consistent if (L_{1}, x_{1}), (L_{2}, x_{2}), (L, x_{1}), (L, x_{2}) are all consistent, where L_{1} = x_{1}L′(0)^{−1}L′ and L_{2} = x_{2}L′(0)^{−1}L′. Such a configuration is called ϵ-monotone on B_{1}(p) with respect to E if L_{1}, L_{2}, L are all ϵ-monotone on B_{1}(p) with respect to E.

Let G_{ϵ} denote the set of configurations which are consistent and ϵ-monotone on B_{1}(p) and let (G_{ϵ})′ = C_{1} \ G_{ϵ}. By using Lemma 11.7, it is immediate to verify from the definitions that if for some parallel lines L_{1}, L_{2} ∈ lines(B_{1}(p)) we have:

(11.12)  H_{L_{1}}^{1} (x ∈ L_{1} (I_{j(L_{1},L_{2},E)}) : (L(x), x, x^{∗}, [L_{1}]) ∈ (G_{ϵ})′) ≲ ϵ,

then apart from a set of measure ≲ ϵ, the set W (L_{1}, L_{2}, E) consists either entirely of points of E or entirely of points in E′.

Lemma 11.13. If E is ϵ^{2}-monotone on B_{1}(p) then:

(11.14)  σ_{1}((G_{ϵ})′) ≲ ϵ,

where σ_{1} is defined as in (11.4).

Proof. We use the notation introduced in our discussion of measure theoretical preliminaries at the beginning of this section. Fix L ∈ lines(B_{1}(p)) and let G′(L, E) denote the set of x ∈ L ∩ B_{1}(p) such that (L, x) is not consistent. By definition, we have

(11.15)  H_{L}^{1}(G′(L, E)) ⩽ 2 · NM_{B_{1}(p)}(L, E) ,

so

(11.16)  ∫_{lines(B_{1}(p))} H_{L}^{1}(G′(L, E)) dN (L) ⩽ 2 · NM_{B_{1}(p)}(E) ⩽ ϵ^{2} .

For x ∈ B_{1}(p), denote by m(x) measure (with respect to dθ) of the set of those [L] ∈ P such that for the unique L′ ∈ [L] such that x ∈ L′, the pointed line (L′, x) is not consistent. Then by (11.1) and (11.2) we deduce from (11.16) that

(11.17)  ∫_{B_{1}(p)} m(x) dL_{3}(x) ≲ ϵ^{2} .

For x_{1}, x_{2} ∈ L, define F (x_{1}, x_{2}) by

(11.18)  F (x_{1}, x_{2}) = m(x_{1}) + m(x_{2}) + χ_{I_{L,E}△(E∩L∩B_{1}(p))}(x_{1}) + χ_{I_{L,E}△(E∩L∩B_{1}(p))}(x_{2}) .

Then,

(11.19) ∫_{lines(B_{1}(p))} (∫_{x_{1},x_{2}∈L∩B_{1}(p)} F (x_{1}, x_{2})d (H_{L}^{1} × H_{L}^{1}) (x_{1}, x_{2})) dN (L)

≲^{(11.17)} ϵ^{2} + ∫_{lines(B_{1}(p))} H_{L}^{1}(I_{L,E} △ (E ∩ L ∩ B_{1}(p))dN (L) ≲^{(11.10)} ϵ^{2} + NM_{B_{1}(p)}(E) ≲ ϵ^{2} .

It follows from (11.19) and (11.4) that if we denote by A ⊆ C the set of configurations (L, x_{1}, x_{2}, [L′]) which are not consistent then σ_{1}(A) ≲ ϵ^{2}.

Let B ⊂ C denote the set of configurations (L, x_{1}, x_{2}, [L′]) which are not ϵ-monotone on B_{1}(p) with respect to E. This implies that for (L, x_{1}, x_{2}, [L′]) ∈ B we have:

NM_{B_{1}(p)}(L, E) + NM_{B_{1}(p)}(x_{1}L′(0)^{−1}L′, E) + NM_{B_{1}(p)}(x_{2}L′(0)^{−1}L′, E) ⩾ ϵ.

Hence, using Markov’s inequality (3.15), combined with the identities (11.4), (11.2), we deduce that

σ_{1}(B) ≲ \frac{NM_{B_{1}(p)}(E)}{ϵ} ⩽ ϵ.

Since, by definition, σ_{1}((G_{ϵ})′) ⩽ σ_{1}(A) + σ_{1}(B), the proof of (11.14) is complete. □

Set a = \frac{1}{100} and recall that, as defined before (11.6), that C̃ = C(B_{1}(p), a) is the set of all configurations (L, x_{1}, x_{2}, [L′]) ∈ C such that x_{1}, x_{2} ∈ B_{1}(p) and the projections of the parallel lines x_{1}L′(0)^{−1}L′, x_{2}L′(0)^{−1}L′ have distance at least a. It follows from (11.6) and (11.14) that σ_{2} ((G_{ϵ})′ ∩ C̃) ≲ ϵ, where the measure σ_{2} is as in (11.5). It follows from (11.5) that there exists a parallelism class [L′] ∈ 𝔓 such that if we define

F = {L_{1}, L_{2} ∈ [L′] : d(π(L_{1}), π(L_{2})) ⩾ a} ,

(11.20) ∫_{F} H_{L_{1}}^{1} (x ∈ L_{1} ∩ B_{1}(p) : (L(x), x, x^{∗}, [L′]) ∈ (G_{ϵ})′) d (μ_{[L′]} × μ_{[L′]}) (L_{1}, L_{2}) ≲ ϵ.

Partition the set of all (L_{1}, L_{2}) ∈ F ×F into equivalence classes, where (L_{1}, L_{2}) is equivalent to (L′_{1}, L′_{2}) if there exists g ∈ Center(ℍ) such that L′_{1} = g(L_{1}), L′_{2} = g(L_{2}) We deduce from (11.20) that there exist L_{1}, L_{2} ∈ F, an index j ∈ {1, 2, 3, 4, 5, 6}, and a subset D ⊂ Center(ℍ) ∩ B_{1}(p) of measure ≳ 1, such that for all g ∈ D we have j(g(L_{1}), g(L_{2}), E) = j, the surface W (g(L_{1}), g(L_{2}), E) has measure ≳ 1, and, by another application of Markov’s inequality (3.15),

H_{L_{1}}^{1} (x ∈ L_{1}(I_{j}) : (L(x), x, x^{∗}, [L_{1}]) ∈ (G_{ϵ})′) ≲ ϵ .

The claim now follows from the discussion following (11.12), and hence the proof of Lemma 7.8 is complete. □

12. Proof of Proposition 7.10

In this section we will consider both lines in ℝ^{2} and their horizontal lifts to ℍ. It will be convenient to use notation, which differs somewhat from that employed elsewhere in the paper. This change will also prevent an undesirable proliforation of subscripts, which would result if we continued to write L (exclusively) for horizontal lines in ℍ.

Let π : ℍ → ℝ^{2} denote the canonical map . Given a line segment τ_{1} ⊂ ℝ^{2} with τ_{1}(0) = (0, 0), denote by τ̃_{1} its unique lift to a segment of a horizontal line in ℍ emanating from the origin. Similarly, consider a once broken line segment τ_{1} ∪ τ_{2}, i.e., a pair of line segments such that the initial point of the line segment τ_{2} is the final point of τ_{1}. Again, we assume τ_{1}(0) = (0, 0). Denote by { \atop τ_{1} ∪ τ_{2}} the lift of τ_{1} ∪ τ_{2} to a continuous broken horizontal line in ℍ = ℝ^{3}, emanating from the origin.

In place of the line L in Proposition 7.10, we will write γ̃. Since both the statement and proof are somewhat technical, for purposes of exposition, we first consider the model case in which γ̃(0) ∈ E, B_{Cr}(γ̃(1)) ⊂ E and E is precisely convex. In this case, we will show that for a large enough universal constant C, there exists c > 0 such that B_{csr}(γ̃(s)) ⊂ E, for all 0 ⩽ s ⩽ 1.

Recall that in Proposition 7.10 we are given parameters κ, η, ξ, r, ρ ∈ (0, 1) such that ρ ⩽ \frac{1}{2}κr^{2} and ρ ⩽ c, where c ∈ (0, 1) will be a small enough universal constant to be determined below. For the reader’s convenience we recall here the values of δ_{1}, δ_{2} in Proposition 7.10, namely (7.12) and (7.13):

(12.1)  δ_{1} = \frac{cκ^{3}η^{2}ξρ^{3}}{r} ,
(12.2)  δ_{2} = cκ^{6}η^{3}ξ^{2}ρ^{3}r^{6} .

In the proof we will also use an auxiliary parameter ω > 0, which will be given by:

(12.3)  ω = \overline{c}κ^{3}ηξr^{2} ,

where \overline{c} ⩾ \sqrt{c} will be an appropriately chosen universal constant.

namely (7.12) and (7.13), we have:

Values of constants. For the reader’s convenience we include here a summary of the steps of the proof of Proposition 7.10, in which the particular values of the constants enter explicitly. For the constraint ρ ⩽ \frac{1}{2}κr^{2}, (12.18), (12.51), (12.67); for ω, (12.30), (12.38), (12.59); for δ_{1}, (12.30), (12.65); for δ_{2}, (12.38), (12.61).

Proof of model case. For reasons of exposition, we begin with the proof of the model case described above.

Remark 12.4. Even though the statement of Proposition 7.10 pertains to balls, the multiplicative structure of ℍ and its relation to the geometry will necessitate the introduction of certain product cylinders, where the product structure corresponds to ℍ = ℝ^{2} × ℝ. In fact, our argument will show that if a cylinder centered at γ̃(1) wtih base radius r^{2} and height r, is contained in E, then a cylinder with base radius ≳ sr^{2} and height sr centered at γ̃(s), will be contained in E. Here, both heights are measured with respect to the metric d^{ℍ}.

Remark 12.5. Let O_{θ} be as in Section 1; see the subsection titled: “The Heisenberg group as a PI space”. By applying a suitable left translation and action by O_{θ}, we can assume γ̃ is the line (s, 0, 0). In the present subsection and in the proof of Proposition 7.10, we consider only points (\overline{a}, \overline{b}, \overline{c}) ∈ B_{csr}(γ̃(s)) with \overline{c} ⩾ 0. Points with \overline{c} ⩽ 0 are handled by the symmetric argument i.e. by interchanging the roles of ϕ and ψ below.

Let Θ ⊂ ℝ^{2} denote angular sector which is the union of rays τ such that τ(0) = γ(0) = (0, 0) and τ(1) ∈ B_{r/2}(γ(1)), where here B_{r/2}(γ(1)) denotes the Euclidean disk in ℝ^{2}. Let Θ̃ denote the union of the lifts of rays τ ⊂ Θ. By the convexity of E, it follows that τ ⊂ Θ implies τ̃(s) ∈ E, for 0 ⩽ s ⩽ 1, where s denotes arc length. To prove the non-quantititative version of (7.16), it suffices to show show that for any τ ⊂ Θ,

(12.6)  π^{−1}(τ(s)) ∩ B_{csr}(τ̃(s)) ⊂ E .

Set

(12.7)  λ = arctan(r^{2}) ,

and let ϕ, ψ denote the rays in Θ which make an angle λ with τ. For the sake of proving (12.6), by applying a suitable rotation, assume that τ is the x-axis, so that we have τ̃(s) = (s, 0, 0). Choose the parameterization u such that ϕ̃(u) = (u, −ur^{2}, 0), ψ̃(u) = (u, ur^{2}, 0).

Fix s_{0} ∈ [0, 1] and let u_{0} be the unique value of u such that the line segment χ, from ϕ(u_{0}) to ψ(1), intersects τ at τ(s_{0}), where χ(0) = ϕ(u_{0}). Thus

(12.8)  u_{0} = \frac{s_{0}}{2 − s_{0}} .

Let ϕ_{1} denote the segment of ϕ from τ(0) = ϕ(0) to ϕ(u_{0}). Let χ̃ denote the segment of { \atop ϕ_{1} ∪ χ} which lifts χ. Choose the parameterization t such that

(12.9)  χ̃(t) = u_{0}(1, −r^{2}, 0) · t ((1, r^{2}, 0) − u_{0}(1, −r^{2}, 0)) ,

where above, as usual, “·” denotes multiplication in ℍ. If we define d_{0} by χ(d_{0}) = τ(s_{0}), then from (12.9), it follows that

(12.10)  d_{0} = \frac{s_{0}}{2} ,

(12.11)  χ̃(d_{0}) = (s_{0}, 0, \frac{2s_{0}^{2} · r^{2}}{2 − s_{0}} ) .

By the assumed convexity of E we have ϕ̃(u) ⊂ E, for all 0 ⩽ u ⩽ 1. From (12.9), for t = 1, and the box-ball principle, (2.20), we can assume that C has been chosen such that χ̃(1) ∈ B_{Cr}(γ̃(1)) ⊂ E. Since E is convex, this gives χ̃(d_{0}) ∈ E. Similarly, by (2.20), for

0 ⩽ v ⩽ \frac{2s_{0}^{2} · r^{2}}{2 − s_{0}} ,

the line (0, 0, −v) · χ̃, intersects Θ̃ ∩ E and satisfies, (0, 0, −v) · χ̃(1) ∈ B_{Cr}(γ̃(1)) ⊂ E. Again by convexity of E, we get (0, 0, −v) · χ̃(d_{0}) ∈ E. It is straightforward to check that this implies that B_{crs_{0}}(τ̃(s_{0})) ⊂ E for some universal constant c > 0, as required.

Remark 12.12. In our proof of Proposition 7.10, it is necessary to replace χ̃ by a 1-parameter a family of lines χ̃_{θ}, to be defined below. To this end, we observe that there is some flexibility in the definition of χ̃. First note that from (12.7), (12.8), (12.10) and the law of sines, it follows that for some universal c_{1} > 0 we have

(12.13)  c_{1} · r^{2} ⩽ ∠(τ̃′(s_{0}), χ̃′(d_{0})) .

For all

(12.14)  0 ⩽ θ ⩽ c_{2} · r^{2} ,

with c_{2} > 0 a small constant, let χ̃_{θ} denote the horizontal line through χ̃(d_{0}) = τ̃(s_{0}) obtained by rotating χ̃ by an angle θ about the point χ̃(d_{0}), in the clockwise direction. The constant C can be chosen such that χ̃_{θ} intersects B_{Cr}(γ̃(1)). It will also intersect Θ̃ ∩ E. In fact, if q = g(τ̃(s_{0})) ∈ B_{cs_{0}r^{2}}(τ̃(s_{0})), then g(χ̃_{θ}) intersects both Θ ∩ E and B_{Cr}(γ̃(1)). It follows that for any q ∈ B_{cs_{0}r^{2}}(τ̃(s_{0})), and any χ̃_{θ} with θ as in (12.14), in verifying that π^{−1}(π(q)) ∩ B_{crs_{0}}(τ̃(s_{0})) ⊂ E, we can use only the lines which are parallel to some χ̃_{θ}.

Intermediate case and proof. Before going to the proof of Proposition 7.10, we consider a slight generalization of the model case. As before, assume that B_{Cr}(γ̃(0)) ∈ E and E is convex. Assume in addition that g(γ̃(0)) ∈ E for some g, with

(12.15)  d^{ℍ}(g(γ̃(0)), γ̃(0)) ⩽ ρ ,

where recall that we are assuming that ρ ⩽ κr^{2}. The box-ball principle (2.20), together with (12.15), implies that for all s > 0 we have

(12.16)  d^{ℍ}(γ̃(s), g(γ̃(s)) ≲ max \{ρ, \sqrt{sρ}\} .

Since ρ ⩽ r^{2} it follows from (12.16) that provided C is large enough, the assumption B_{Cr}(γ̃(1)) ⊆ E implies that B_{\frac{1}{2} Cr}(gγ̃(1)) ⊆ E. Now, a computation like those above shows that for all 0 ⩽ s ⩽ 1 we have

(12.17)  B_{csr}(gγ̃(s)) ⊂ E for all s ∈ [0, 1] ,

where c > 0 is a universal constant. It follows from (12.15), the bound ρ ⩽ κr^{2}, and (12.17), that there exists a constant c′ > 0 such that

(12.18)  B_{\frac{1}{2} csr}(γ̃(s)) ⊂ E , for all s ∈ [c′κ, 1] .

Remark 12.19. It is worthwhile to emphasize here that in order to obtain (12.18), we must take ρ proportional to r^{2} (rather than to r); compare also the use cylinders, B_{csr^{2}}(τ(0)) × [−(sr)^{2}, (sr)^{2}] in the model case above and below.

Proof of Proposition 7.10. The arguments in the model and intermediate cases use Θ̃ ⊂ E, respectively, g(Θ̃) ∩ B_{1}(γ̃(0)) ⊂ E. Since in the general case, our hypotheses are measure theoretic, we will employ integral geometry and in particular, the measure theoretical preliminaries given in Section 11.

The first (and most involved) step is to show the existence of a thickened version 𝕊 of the angular sector, g(Θ̃) ⊂ E, of the intermediate case:

(12.20)  𝕊 = ⋃_{ζ∈A} gζ(Θ̃) ,

for some g ∈ ℍ, where A is a suitably chosen subset of the center of ℍ such that gζ(γ̃(0)) ∈ B_{ρ}(γ̃(0)) ∩ E for all ζ ∈ A. We think of 𝕊 as a “thin slab”.

The slices gζ(Θ̃) of 𝕊 will be shown to consist almost entirely of points of E. Hence, the vertical structure exhibited in (12.20) implies that the mass of E ∩ 𝕊 is very evenly distributed. In the presence of sufficiently small nonconvexity of E, this compensates for the fact that the mass of E ∩ 𝕊, while subject to a definite lower bound depending on η (see (12.24)) might be still be very small, which might otherwise prevent 𝕊 from serving as an adequate substitute for Θ̃.

The following lemma, summarizes the essential properties of 𝕊. Eventually, we will be interested in the behavior of the intersection of 𝕊 with the cylinder (with coordinate description)

B_{csr^{2}}(τ(s)) × [−c · (s · r)^{2}, c · (s · r)^{2}],

whose intrinsic height is 2(rs) and whose measure is ≍ (s · r^{2})^{2} · (s · r)^{2}. This may help to explain the right-hand sides of (12.22)–(12.25).

Lemma 12.21. There exists g ∈ ℍ satisfying (12.15) and A ⊂ Center(ℍ) such that for 𝕊 as in (12.20):

a)

(12.22)  𝕊 ⊂ g (ℝ^{2} × I) ,

for some I ⊂ [−ρ^{2}, ρ^{2}] ⊂ Center(ℍ), with

(12.23)  L(I) ≍ ξρ^{2} ,

where L denotes the Hausdorff measure on the center of ℍ, with its induced \frac{1}{2}-snowflake metric. b) 𝕊 has a definite thickness:

(12.24)  L(A) ≳ ηξρ^{2} .

c) 𝕊 consists almost entirely of points of E, i.e., for all ζ ∈ A:

(12.25)  L_{2} ((gζ \binom{}{Θ} \ (B_{ρ}(γ̃(0)) ∪ B_{r}(γ̃(1)))) ∩ E′) ≲ ωr^{2} .

Granted Lemma 12.21, the proof of Proposition 7.10 is not difficult to complete. We will now give a brief overview of the argument to come. Since E is δ_{2}-convex, we can chose χ̃_{θ}, as in Remark 12.12 such that for a fraction very close to 1 of lines L ∈ [χ̃_{θ}], the nonconvexity, NC_{B_{Cr}(γ̃(0))}(E, L) is very small. By a quantitative version of the proofs of previously considered model and intermediate cases, it follows that such lines consist almost entirely of points of E. The argument uses (12.24), (12.25), and Lemma 11.7 below. In fact, Lemma 11.7 enters, in similar fashion, in the proof of Lemma 12.21.

Proof of Lemma 12.21. In the next few subsections we will show that for most points, g(γ̃(0)) ∈ E ∩ B_{ρ}(γ̃(0)), the sector g(Θ̃) consists almost entirely of points of E. The remainder of the construction will be a simple consequence of this fact.

Implication of almost full measure of E in B_{Cr} (γ̃(1)). By the assumption (7.14) we have:

(12.26)  L_{3}(E ∩ B_{ρ}(γ̃(0))) ⩾ η · L_{3}(B_{ρ}(γ̃(0))) ≳ ηρ^{4} .

Let C > 0 be the (large enough, but fixed) constant that was chosen in the intermediate case of the proof. Assume as in (7.15) that L(1) ∈ int_{δ_{1},Cr}(E). chosen to be a large enough universal Recall that the parameter ω is defined in (12.3). At the end of the proof, it will become clear why it is necessary to choose this value of ω; see (12.30), (12.38), (12.59).

For τ ⊂ Θ, set

(12.27)  S_{[τ̃]} = {τ̂ ∈ [τ̃] | 0 < H1 ; τ̂(τ̂ ∩ E ∩ B_{ρ}(γ̃(0))) ⩽ ω · η · ρ} ,

(12.28)

T_{[τ̃]} = \{τ̂ ∈ [τ̃] | 0 < H1 ; τ̂(τ̂ ∩ E ∩ B_{ρ}(γ̃(0)) and H1 ; τ̂ (τ̂ ∩ E ∩ B_{\frac{1}{2} r}(γ̃(1))) ⩽ \frac{1}{2} · r\} .

Without loss of generality, we can assume that κ is small enough that if τ̂ ∈ S_{[τ̃]} then τ̂(1) ∈ B_{\frac{1}{2} r}(γ̃(1)); see (12.16). From (7.15), (7.12), (11.1), we get:

(12.29)  μ_{[τ̃]} (T_{[τ̃]}) ≲ δ_{1}r^{3} ⩽ ωηρ^{3} ,

provided that the following lower bound on ω holds:

(12.30)  ω ⩾ \frac{δ_{1}}{η} · (\frac{r}{ρ})^{3} .

An inspection of our choice of parameters (12.1), (12.3) shows that (12.30) does indeed hold in our setting. (Note that here, we used the requirement \overline{c} ⩾ \sqrt{c} ⩾ c.)

Estimates in the space of pointed lines. Recall that ν denotes the measure on ℙ, the space of pointed lines, as in (11.3). Let

(12.31)

U^{#} = \{(τ̂, τ̂(0)) | τ̂(0) ∈ E ∩ B_{ρ}(γ̃(0)) and τ̂ ⊂ τ̂(0)γ̃(0)^{−1} \binom{}{Θ}\} ,

S^{#} = {(τ̂, τ̂(0)) | τ̂ ∈ S ∩ g(Θ̃), τ̂(0) = g(γ̃(0)) ∈ E ∩ B_{ρ}(γ̃(0))} ,

T^{#} = {(τ̂, τ̂(0)) | τ̂(0) ∈ E ∩ B_{ρ}(γ̃(0)) and τ̂ ∈ T_{[τ̂]} and τ̂ ⊂ τ̂(0)γ̃(0)^{−1} (Θ̃)} .

Then

(12.32)  ν (U^{#}) ≍ r^{2}L_{3}(E ∩ B_{ρ}(γ̃(0))) ≳ ηr^{2}ρ^{4},
(12.33)  ν (S^{#}) ≲ ωηr^{2}ρ^{4} ,
(12.34)  ν (T^{#}) ≲ ωηr^{2}ρ^{4} .

Relation (12.32) follows from (11.1), (11.2), (11.3), (12.7) and (12.26). Relations (12.33), (12.34) follow similarly, using (12.27) and (12.29), respectively.

Recall that E is δ_{2}-convex on B_{2C}(γ̃(0)), for δ_{2} as in (7.13). Define:

(12.35)  V = \{L ∈ lines (B_{2C}(γ̃(0))) | NC_{B_{2C}(γ̃(0))}(E, L) ⩾ \frac{ω}{2} \} ,
(12.36)  V^{#} = {(L, x) ∈ ℙ | L ∈ V and x ∈ E ∩ B_{ρ}(γ̃(0))} .

By (4.7), Markov’s inequality (3.15) and (11.3), we have

(12.37)  ν (V^{#}) ≲ \frac{δ_{2}}{ω} · ρ ⩽ ωηr^{2}ρ^{4} ,

provided that in addition to (12.30) we also assume that

(12.38)  ω ⩾ \sqrt{\frac{δ_{2}}{ηr^{2}ρ^{3}}} .

An inspection of our choice of parameters (12.2), (12.3) shows that (12.38) holds in our setting (note that we used here the requirement \overline{c} ⩾ \sqrt{c}).

It follows from (12.32)–(12.34) and (12.37) that

(12.39)  ν (S^{#} ∪ T^{#} ∪ V^{#}) ≲ ω · ν (U^{#}) .

Define

(12.40)  W^{#} = U^{#} \ (S^{#} ∪ T^{#} ∪ V^{#}) .

Then, for (τ̂, τ̂(0)) ∈ W^{#}, the definitions (12.31), (12.36), together with Lemma 11.7, imply that if we set

J = [ρ + \frac{ω}{2} , 1 − \frac{r}{2} − \frac{ω}{2} ] ,

then

(12.41)  H1 ; τ̂(E′ ∩ τ̂(J)) ⩽ \frac{ω}{2} .

For x ∈ E ∩ B_{ρ}(γ̃(0)), x = g(γ̃(0)), put

(12.42)  𝔊(x) = {τ̂ ⊂ g(Θ̃) | (τ̂, x) ∈ W^{#} } .

Note that, using the above notation, the set of all τ̂ ⊂ g(Θ̃) with τ̂(0) = x is parameterized by the corresponding angle ϕ in the sector given by (12.7). It follows from (12.39), (12.32), (12.26), that there exists a large enough universal constant c > 0 such that if we put

(12.43)  E_{1} = {x ∈ E ∩ B_{ρ}(γ̃(0)) | dϕ(𝔊(x)) ⩽ cωr^{2} } .

then

(12.44)  L_{3}(E_{1}) ⩾ \frac{1}{2}L_{3}(E ∩ B_{ρ}(γ̃(0))) ≳ ηρ^{4} .

In the following corollary and below, we consider the splitting of the measure

(12.45)  L_{3} = L × L_{2} = H^{2} × L_{2} ,

relative to the product structure on ℍ = ℝ^{3}, where L = H^{2} corresponds to the center of ℍ (with its induced \frac{1}{2}-snowflake metric) and L_{2} to the plane (x, y, 0) ⊂ ℝ^{3}. In connection with (12.47) below, recall that L_{3}(B_{ρ}(γ̃(0))) ≍ ρ^{4} = ρ^{2} × ρ^{2}, where the product corresponds to the decomposition in (12.45).

Corollary 12.46. There exists q ∈ π(E_{1}) such that

(12.47)  ηρ^{2} ≲ L(π^{−1}(q) ∩ E_{1}) ≲ ρ^{2} .

If g(γ̃(0)) ∈ π^{−1}(q) ∩ E_{1} then

(12.48)  L_{2} (E′ ∩ (g(Θ̃) \ (B_{ρ} (γ̃(0)) ∪ B_{r} (γ̃(1))))) ≲ ωr^{2} .

Proof. Relation (12.47) follows from the splitting of the measure in (12.45) and (12.44). Relation (12.48) follows from the definitions of U^{#}, S^{#}, T^{#}, V^{#}, W^{#}, together with (12.41), (12.42), (12.43). □

Construction of 𝕊; completion of the proof of Lemma 12.21. By virtue of (12.47) we can choose an interval I ⊂ [−ρ^{2}, ρ^{2}] such that

(12.49)  L(I) ≍ ξρ^{2} ,
(12.50)  L (π^{−1}(q) ∩ E_{1} ∩ q(I)) ≳ ηξρ^{2} .

Define a subset A of the center of ℍ by

A = π^{−1}((0, 0)) ∩ q^{−1}(π(E_{1})) ∩ I .

Choose g = qγ̃(0)^{−1}. Then g satisfies (12.15), and by (12.49), (12.50), a), b) of Lemma 12.21 hold. Since by the definition of q , for all ζ ∈ A, we have gζγ̃(0) ∈ π^{−1}(q) ∩ E_{1}, Corollary 12.46 implies that part c) holds as well. □

Completion of the proof of Proposition 7.10. By choosing c in Proposition 7.10 sufficiently small, we can assume without essential loss of generality that g of Lemma 12.21 is the point (0, 0, 0) and that I is symmetric about the origin. Fix s ∈ [κ, 1] and let τ, χ̃_{θ} with 0 ⩽ θ ⩽ \frac{r^{2}}{100} be as in Remark 12.12, with θ to be determined below.

Let S denote the square with center τ(s) and side length csr^{2}, with one side parallel to χ_{θ}. Of the two sides of S which are orthogonal to χ_{θ}, let α denote the one which is furthest from the origin (0, 0) ∈ ℝ^{2}. Let R denote the rectangle with one side parallel to χ_{θ} and of length, 2sr^{2} + (s/2), and such the two side which are orthogonal to χ_{θ}, the one furthest from (0, 0) ∈ ℝ^{2} is α. In particular, S ⊂ R. By a standard covering argument, it will suffice to show that at most a fraction ξ of points of S × [0, (csr)^{2}] lie in E′; see (7.16). Since by our assumptions ρ ⩽ \frac{1}{2}κr^{2} and s ⩾ κ,

(12.51)  ξρ^{2} ⩽ \frac{1}{2}ξ(sr)^{2} ,

it suffices to show that at most a fraction ξ of the points of S × ([0, (csr)^{2}] \ I) lie in E′.

Let

𝔉_{θ} = \{L ∈ \left[{ \atop χ_{θ}}\right] | L ∩ (α × ([0, (csr)^{2}] \ I)) ≠ ∅\} .

Note that 𝔉 can (essentially) be described alternatively as consisting of those lines in \left[{ \atop χ_{θ}}\right] which intersect R. If follows from (11.1) that

(12.52)  μ_{\left[{ \atop χ_{θ}}\right]} (𝔉_{θ}) ≳ (sr^{2})(sr)^{2} = s^{3}r^{4} .

Moreover, since E is δ_{2}-convex on B_{2C} (γ̃(0)), there exists θ ∈ (0, \frac{r^{2}}{100}) such that

(12.53)  ∫_{L∈𝔉_{θ}} NC_{B_{2C}(γ̃(0))}(E, L)dμ_{\left[{ \atop χ_{θ}}\right]}(L) ⩽ \frac{100δ_{2}}{r^{2}} .

We shall fix θ as in (12.53) from now on. It follows from (12.52), (12.53) that there exists a universal constant c′′ > 0 such that if we define

(12.54)  𝔉_{θ}^{∗} = \{L ∈ 𝔉_{θ} |NC_{B_{2C}(γ̃(0))}(E, L) ⩽ \frac{c′′δ_{2}}{ξs^{3}r^{6}} \}

then

(12.55)  μ_{\left[{ \atop χ_{θ}}\right]} (𝔉_{θ}^{∗}) ⩾ (1 − \frac{ξ}{8}) μ_{\left[{ \atop χ_{θ}}\right]} (𝔉_{θ}) .

Lemma 12.21 implies that

L_{3} ((𝕊 \ (B_{ρ}(γ̃(0)) ∪ B_{r}(γ̃(1)))) ∩ E′) ≲ ωr^{2}ξρ^{2} ,

and hence, using (11.1) and Markov’s inequality (3.15), we see that there exists a universal constant c′′′ > 0 such that if we define

(12.56)  𝔉_{θ}^{∗∗} = \{L ∈ 𝔉_{θ}^{∗} |H_{L}^{1} ((𝕊 \ (B_{ρ}(γ̃(0)) ∪ B_{r}(γ̃(1)))) ∩ E′ ∩ L) ⩽ \frac{c′′′ωρ^{2}}{s^{3}r^{2}} \} ,

then

(12.57)  μ_{\left[{ \atop χ_{θ}}\right]} (𝔉_{θ}^{∗∗}) ⩾ (1 − \frac{ξ}{4}) μ_{\left[{ \atop χ_{θ}}\right]} (𝔉_{θ}) .

Note that the definitions of 𝔉_{θ} and 𝕊, together with (12.23), (12.24), imply that for all L ∈ 𝔉_{θ} we have

(12.58)  H_{L}^{1} ((𝕊 \ (B_{ρ}(γ̃(0)) ∪ B_{r}(γ̃(1)))) ∩ B_{s(1− \frac{r}{8} )} (γ̃(0)) ∩ L) ≳ ηξρ^{2}.

Thus, by the definition of 𝔉_{θ}^{∗∗}, and recalling that s ⩾ κ, we see that provided that

(12.59)  ω ⩽ c^{∗}ηξκ^{3}r^{2},

where c^{∗} > 0 is a small enough absolute constant, we have for all L ∈ 𝔉_{θ}^{∗∗},

(12.60)  H_{L}^{1} (E ∩ B_{s(1− \frac{r}{8} )} (γ̃(0)) ∩ L) ≳ ηξρ^{2}.

We shall choose \overline{c} = c^{∗} in (12.3), thus completing our choice of ω.

Assuming also that for a small enough constant, c^{∗∗} > 0, we have

(12.61)  δ_{2} ⩽ c^{∗∗}ηξ^{2}κ^{3}r^{6}ρ^{2},

which follows from our choice of δ_{2} in (12.2), provided c is small enough, we conclude from the definition of 𝔉_{θ}^{∗}, together with (12.58), that for all L ∈ 𝔉_{θ}^{∗∗},

(12.62)  NC_{B_{2C}(γ̃(0))}(E, L) ⩽ \frac{1}{4}ηξρ^{2},

and

(12.63)  H_{L}^{1} (E ∩ B_{s(1− \frac{r}{8} )} (γ̃(0)) ∩ L) ⩾ NC_{B_{2C}(γ̃(0))}(E, L) .

Recall also, assumption (7.15), which implies that L_{3}(E′ ∩ B_{r}(γ̃(1))) ≲ δ_{1}r^{4}. Moreover, by the definition of 𝔉_{θ} we have H_{L}^{1} (L ∩ B_{r}(γ̃(1))) ≳ r for all L ∈ 𝔉_{θ}.

For a sufficiently small universal constant c′′′′ > 0 (see below) define

(12.64)  𝔉_{θ}^{∗∗∗} = {L ∈ 𝔉_{θ}^{∗∗} |H_{L}^{1} (L ∩ B_{r}(γ̃(1)) ∩ E) ⩾ c′′′′r} .

By Markov’s inequality

μ_{\left[{ \atop χ_{θ}}\right]}(𝔉_{θ}^{∗∗} \ 𝔉_{θ}^{∗∗∗}) ≲ \frac{δ_{1}r^{4}}{r} .

Therefore, if for a sufficently small universal constant, c^{∗∗∗} > 0, we have,

(12.65)  δ_{1} ⩽ c^{∗∗∗}κ^{3}ξr,

it follows that

(12.66)  μ_{\left[{ \atop χ_{θ}}\right]} (𝔉_{θ}^{∗∗∗}) ⩾ (1 − \frac{ξ}{2}) · μ_{\left[{ \atop χ_{θ}}\right]} (𝔉_{θ}) ,

Note that our assumption (12.1), together with ρ ⩽ \frac{1}{2}κr^{2}, implies that (12.65) holds provided c is small enough.

For every L ∈ 𝔉_{θ}^{∗∗∗} we know that

H_{L}^{1} (L ∩ B_{r}(γ̃(1)) ∩ E) ⩾ c′′′r ⩾^{(12.62)} NC_{B_{2C}(γ̃(0))}(E, L),

provided that

(12.67)  ηξρ^{2} ⩽ 4c′′′r ,

which holds if c is small enough. In combination with (12.60), (12.62), (12.63), (12.66) and Lemma 11.7, we obtain the required result. □

13. Appendix 1: The Sparsest Cut problem

As mentioned in Section 1, Theorem 1.1, and in particular, Corollary 1.5, leads to an exponential improvement of the previously best known [43] lower bound on the integrality gap of the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands. We now add some additional details to the discussion of Section 1; for further details, we refer to see also our paper [24], and the references therein.

The Sparsest Cut problem with general demands (and capacities) asks for an efficient proceedure to partition a weighted graph into two parts, so as to minimize the interface between them. Formally, we are given an n-vertex graph G = (V, E), with a positive weight (called a capacity) c(e) associated to each edge e ∈ E, and a nonnegative weight (called a demand) D(u, v) associated to each pair of vertices u, v ∈ V. The goal is to evaluate in polynomial time (and in particular, while examining only a negligible fraction of the subsets of V) the quantity:

(13.1)  Φ^{∗}(c, D) = min_{∅≠S⊊V} \frac{∑_{uv∈E} c(uv) |χ_{S}(u) − χ_{S}(v)|}{∑_{u,v∈V} D(u, v) |χ_{S}(u) − χ_{S}(v)|} .

To get a feeling for the meaning of Φ^{∗}, consider the case c(e) = D(u, v) = 1 for all e ∈ E and u, v ∈ V. This is an important instance of the Sparsest Cut problem which is called “Sparsest Cut with Uniform Demands”. In this case Φ^{∗} becomes:

(13.2)  Φ^{∗} = min_{∅≠S⊊V} \frac{#\{edges joining S and V \ S\}}{|S| · |V \ S|} .

Thus, in the case of uniform demands, the Sparsest Cut problem essentially amounts to solving efficiently the combinatorial isoperimetric problem on G: determining the subset of the graph whose ratio of edge boundary to its size is as small as possible.

¿From now on, the Sparsest Cut problem will be understood to be with general capacities and demands. These allow one to tune the notion of “interface” between S and V \S to a wide variety of combinatorial optimization problems, which is one of the reasons why the Sparsest Cut problem is one of the most important problems in the field of approximation algorithms. It is used as a subroutine in many approximation algorithms for NP-hard problems; see the survey article [60], as well as the references in [49, 6, 5, 24], for some of the (vast) literature on this topic.

The problem of computing Φ^{∗}(c, D) in polynomial time is known to be NP hard [59]. The most fruitful approach to finding an approximate solution has been to consider relaxations of the problem. Observe that the term d_{S} := |χ_{S}(u) − χ_{S}(v)|, occuring in (13.1) is just the distance from u to v in the elementary cut metric associated to S; see Section 2. One is therefore led consider the minimization of the functional

(13.3)  Φ(c, D, d) = \frac{∑_{uv∈E} c(uv)d(u, v)}{∑_{u,v∈V} D(u, v)d(u, v)} ,

where d varies over an enlarged class of metrics. The following successively larger classes of metrics have played a key role: elementary cut metrics (as in (13.1)), L_{1} metrics (equivalently, cut metrics), metrics of negative type, arbitrary metrics. Denote the later two collections of metrics by NEG, MET, and denote the corresponding minima by Φ^{∗}(c, D) ⩾ Φ_{L_{1}}^{∗}(c, D) ⩾ Φ_{NEG}^{∗}(c, D) ⩾ Φ_{MET}^{∗}(c, D). From the standpoint of theoretical computer science, a key point is that Φ_{MET}^{∗}(c, D) is a linear program (since the triangle inequality is a linear condition) and Φ_{NEG}^{∗}(c, D) can be computed by the Ellipsoid Algorithm. Thus, both are computable in polynomial time with arbitrarily good precision.

Let d denote an L_{1} metric and let Σ_{d} denote the cut measure occuring in the cut metric representation d = ∑_{S⊂V} Σ_{d}(S)d_{S} of d; see (2.7). By substituting the cut metric representation into (13.3), it follows directly that in fact, Φ^{∗}(c, D) = Φ_{L_{1}}^{∗}(c, D), for all c, D; [10, 53, 9]. The key point is that L_{1} metrics are the convex cone generated by elementary cut metrics (and a corresponding statement would hold for any such convex cone and its generators).

If d_{1}, d_{2} are any two metrics on V, define their distortion by

dist(d_{1}, d_{2}) = (max_{u,v∈V} \frac{d_{1}(u, v)}{d_{2}(u, v)}) · (max_{u,v∈V} \frac{d_{2}(u, v)}{d_{1}(u, v)}) .

It follows immediately that for all c, D,

(13.4)  max \{\frac{Φ(c, D, d_{1})}{Φ(c, D, d_{2})}, \frac{Φ(c, D, d_{2})}{Φ(c, D, d_{1})}\} ⩽ dist(d_{1}, d_{2}) .

Thus,

(13.5)  sup_{c,D} \frac{Φ_{L_{1}}^{∗}(c, D)}{Φ_{NEG}^{∗}(c, D)} ⩽ sup_{d∈NEG} c_{1}(V, d) ,

(13.6)  sup_{c,D} \frac{Φ_{L_{1}}^{∗}(c, D)}{Φ_{MET}^{∗}(c, D)} ⩽ sup_{d∈MET} c_{1}(V, d) .

Recall that by definition, the left-hand sides in (13.5), (13.6) are the integrality gaps for the corresponding relaxations. Since Φ^{∗}(c, D) = Φ_{L_{1}}^{∗}(c, D), Bourgain’s embedding theorem implies that the first of these integrality gaps is ≲ log n; [53, 9]. Similarly, for the Goemans-Linial semidefinite relaxation, the embedding theorem for metrics of negative type given in [5] implies the the integrality gap is ≲ (log n)^{1/2+o(1)}. (Of course, the upper bound in terms of distortion also applies if L_{1} metrics are replaced by the original elementary cut metrics, but since these metrics are so highly degenerate, it does it not provide useful information. This illustrates the power of the observation of [53, 9].)

From now on we restrict attention to the Goemans-Linial semidefinite relaxation. (What we say also applies mutadis mutandis to the relaxation to MET.) As in (13.5), for all c, D, and all d_{2} ∈ NEG,

(13.7)  \frac{Φ_{L_{1}}^{∗}(c, D)}{Φ_{NEG}^{∗}(c, D)} ⩽ c_{1}(V, d_{2}) .

A duality argument (sketched below) shows that for all d_{2}, their exist c, D for which (13.7) becomes an equality. Therefore, the integrality gap is actually equal to sup_{d∈NEG} c_{1}(V, d).

Thus, by Corollary 1.5 (see also Remark 1.7) the integrality gap is ≳ (log n)^{δ} for some explicit δ > 0. Recall that the previous best bound was ≳ log log n; see [43], [41].

Here is a sketch of the duality argument; for further discussion, see Proposition 15.5.2 of [54]. Consider a set V of cardinality n, the vertices of our graph (whose edge structure will be determined below). Define an embedding F of the metrics on V into ℝ^{n(n−1)/2} as follows: The coordinates x_{u,v} correspond to unordered pairs u, v of distinct vertices in V, and x_{u,v}(F (d)) = d(u, v). The image of the L_{1} metrics on V is a convex cone L ⊂ ℝ^{n(n−1)/2} generated by the images of the elementary cut metrics d_{S}. Let d_{2} satisfy F (d_{2}) ∉ L. By an easy compactness argument, the distortion dist(d, d_{2}), for d with F (d) ∈ L, is minimized by some d_{1}, with F (d_{1}) ∈ L. Minimality implies that in fact, F (d_{1}) ∈ ∂L. Take a supporting hyperplane, P, for L which passes through F (d_{1}). Let ℓ denote a linear functional satisfying ℓ |_{P} ≡ 0, ℓ |_{L} ⩽ 0 and ℓ(F (d_{2})) > 0. Let ∑_{(u,v)} ℓ_{u,v}·x_{(u,v)}^{∗} denote the coordinate representation of ℓ. Define capacities by: c(uv) = ℓ_{u,v} if ℓ_{u,v} > 0 and otherwise c(uv) = 0. Define demands by: D(u, v) = −ℓ_{u,v} if ℓ_{u,v} < 0 and otherwise D(u, v) = 0. Define a graph structure with vertices, V, by stipulating that uv ∈ E if and only if c(uv) > 0. It is trivial to check that for the above c, D, we have Φ(c, D, d) ⩾ 1, for all d with F (d) ∈ L. Also Φ(d_{1}) = 1, Φ(c, D, d_{2}) ⩽ \frac{1}{dist(d_{1},d_{2})} = \frac{1}{c_{1}(V,d_{2})}. These relations imply that for these c, D, (13.7) is an equality. By choosing d_{2} ∈ NEG such that c_{1}(V, d_{2}) is maximal, it follows that (13.5) is also an equality. (If F (d_{2}) ∈ L, this is trivial.)

14. Appendix 2: Quantitative bounds, coercivity and monotonicity

In this Appendix, we briefly discuss from a more general standpoint, the structure of our argument, as outlined after the statement of Theorem 1.1 and in Section 4. We point out that in essence, what we have done follows the general scheme of other arguments in geometric analysis and nonlinear partial differential equations; compare Example 14.1 below. Typically, the results are not stated explicitly in quantitative form. Here, we wish to emphasize that the possibility of an estimate of the form of (1.2) is actually implicit in the arguments. The crucial ingredient is a quantity which is coercive, monotone and bounded.

Coercivity and almost rigidity. The term, rigid, connotes special (i.e. highly constrained) structure. A standard feature of (the statment and proof of) rigidity theorems is the existence of a numerical measurement Q ⩾ 0 which is coercive in the sense that if Q = 0, then the desired rigidity holds, and more generally (and often much harder to prove) if Q < ϵ^{a}, for some a < ∞, then in a suitable sense, the structure is ϵ-close the one which is obtained in the rigid case. Statments of this type are known as stability theorems, ϵ-regularity theorems or almost rigidity theorems. A classical example from Riemannian geometry is the sphere theorem, in which the coercive quantity is minus the logarithm of the pinching; see [13] and the references therein.

In our case, we are given E ⊂ ℍ, and the coercive quantity is Q(E) = NM_{B_{r}(x)}(E), the nonmonotonicity of E on B_{r}(x). Coercivitity is the statement that monotone subsets are half-spaces, or more generally, that almost monontone subsets are close to half-spaces; see Theorem 4.13.

Bounded monotone quantities and existence of a good scale. As in Sections 1, 2, we point out the general character of the estimate in Proposition 4.31 for the scale on which Theorem 4.13 can be applied. Namely, by Markov’s inequality (3.15) (which in this case amounts to the pigeonhole principle), such an estimate for the scale will appear whenever we are dealing with an a priori bounded nonnegative quantity, which can be written as a sum of nonnegative terms, which correspond to the various scales, such that each term is coercive on its own scale (in the suitably scaled sense). Such a quantity is monotone in the sense that the sum is nondecreasing as we include more and more scales; compare (4.34), (6.11).

Quantities which are coercive and monotone are well-known to play a key role in geometric analysis and in partial differential equations. In the latter case, for evolution equations, monotonicity is defined with respect to the time parameter, rather than the scale.

We include below the following illustrative example, which requires familiarity with Riemannian geometry. Numerous other choices from diverse areas would serve equally well; compare Remark 2.1.

Example 14.1. A theorem from Riemannian geometry states that for noncollapsed Gromov-Hausdorff limit spaces, M_{i}^{n} ⟶^{d_{GH}} Y^{n}, such that Ric_{M_{i}^{n}} ⩾ −(n − 1) for all i, every tangent cone Y_{y} is a metric cone; see Remark 4.99 of [17] and [16]. In this case, the rigid objects are metric cones and the relevant coercive quantity, Q, is derived from the volume ratio,

(14.2)  \frac{Vol(B_{r}(p))}{Vol(B_{r}(\underline{p}))} ,

where \underline{p} ∈ \underline{M}^{n} and \underline{M}^{n} denotes the hyperbolic n-space with curvature ≡ −1. The coercivity of Q is guaranteed by the “volume cone implies metric cone theorem” and its corresponding almost rigidity theorem, which states that almost volume cones are close in the Gromov-Hausdorff sense to be almost metric cones; see [16], [17]. The monotonicity of Q is a consequence of the Bishop-Gromov inequality, which asserts that the volume ratio in (14.2) is a monotone nonincreasing function of r.

References

[1] L. Ambrosio. Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces. Adv. Math., 159(1):51–67, 2001.

[2] L. Ambrosio. Fine properties of sets of finite perimeter in doubling metric measure spaces. Set-Valued Anal., 10(2-3):111–128, 2002. Calculus of variations, nonsmooth analysis and related topics.

[3] L. Ambrosio, N. Fusco, and D. Pallara. Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, 2000.

[4] N. Aronszajn. Differentiability of Lipschitzian mappings between Banach spaces. Studia Math., 57(2):147–190, 1976.

[5] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1–21 (electronic), 2008.

[6] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 222–231 (electronic), New York, 2004. ACM.

[7] G. Arzhantseva, C. Drutu, and M. Sapir. Compression functions of uniform embeddings of groups into Hilbert and Banach spaces. J. Reine Angew. Math., 633:213–235, 2009.

[8] P. Assouad. Plongements Lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429–448, 1983.

[9] Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291–301 (electronic), 1998.

[10] D. Avis and M. Deza. The cut cone, L^{1} embeddability, complexity, and multicommodity flows. Networks, 21(6):595–617, 1991.

[11] S. Bates, W. B. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal., 9(6):1092–1127, 1999.

[12] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[13] S. Brendle and R. Schoen. Manifolds with 1/4-pinched curvature are space forms. J. Amer. Math. Soc., 22(1):287–307, 2009.

[14] D. Burago, Y. Burago, and S. Ivanov. A course in metric geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001.

[15] S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2):Art. 22, 18, 2008.

[16] J. Cheeger and T. Colding. Lower bounds on Ricci curvature and the almost rigidity of warped products. Ann. of Math. (2), 144(1):189–237, 1996.

[17] J. Cheeger and T. Colding. On the structure of spaces with Ricci curvature bounded below. J. Diff. Geom., 46:406–480, 1997.

[18] J. Cheeger and B. Kleiner. Differentiating maps into L^{1} and the geometry of BV functions. To appear in Ann. Math., preprint available at http://arxiv.org/abs/math/0611954, 2006.

[19] J. Cheeger and B. Kleiner. On the differentiability of Lipschitz maps from metric measure spaces to Banach spaces. In Inspired by S. S. Chern, volume 11 of Nankai Tracts Math., pages 129–152. World Sci. Publ., Hackensack, NJ, 2006.

[20] J. Cheeger and B. Kleiner. Differentiation of Lipschitz maps from metric measure spaces to Banach spaces with the Radon Nikodym Property. to appear in GAFA, Geom. Funct. Anal, preprint available at http://arxiv.org/pdf/0808.3249, 2008.

[21] J. Cheeger and B. Kleiner. Embedding Laakso spaces in L^{1}. In preparation, 2008.

[22] J. Cheeger and B. Kleiner. Metric differentiation for PI spaces. In preparation, 2008.

[23] J. Cheeger and B. Kleiner. Metric differentiation and monotonicity and maps to L^{1}. Preprint available

at http://arxiv.org/abs/0907.3295, 2009.

[24] J. Cheeger, B. Kleiner, and A. Naor. A (log n)^{Ω(1)} integrality gap for the Sparsest Cut SDP. To appear in Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 2009.

[25] E. De Giorgi. Su una teoria generale della misura (r − 1)-dimensionale in uno spazio ad r dimensioni. Ann. Mat. Pura Appl. (4), 36:191–213, 1954.

[26] E. De Giorgi. Nuovi teoremi relativi alle misure (r − 1)-dimensionali in uno spazio ad r dimensioni. Ricerche Mat., 4:95–113, 1955.

[27] M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.

[28] P. Enflo. On the nonexistence of uniform homeomorphisms between L_{p}-spaces. Ark. Mat., 8:103–105 (1969), 1969.

[29] B. Franchi, R. Serapioni, and F. Serra Cassano. Rectifiability and perimeter in the Heisenberg group. Math. Ann., 321(3):479–531, 2001.

[30] B. Franchi, R. Serapioni, and F. Serra Cassano. On the structure of finite perimeter sets in step 2 Carnot groups. J. Geom. Anal., 13(3):421–466, 2003.

[31] M. X. Goemans. Semidefinite programming in combinatorial optimization. Math. Programming, 79(1-3, Ser. B):143–161, 1997. Lectures on mathematical programming (ismp97) (Lausanne, 1997).

[32] M. Gromov. Asymptotic invariants of infinite groups. In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.

[33] M. Gromov. Metric structures for Riemannian and non-Riemannian spaces. Modern Birkhäuser Classics. Birkhäuser Boston Inc., Boston, MA, english edition, 2007. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates.

[34] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.

[35] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In FOCS, pages 534–543. IEEE Computer Society, 2003.

[36] P. Hajłasz and P. Koskela. Sobolev met Poincaré. Mem. Amer. Math. Soc., 145(688):x+101, 2000.

[37] J. Heinonen. Lectures on Analysis on Metric Spaces. Springer, New York, N.Y., 2001. Universitext.

[38] J. Heinonen and P. Koskela. From local to global in quasiconformal structures. Proc. Nat. Acad. Sci. USA, 93:554–556, 1996.

[39] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

[40] P. W. Jones. Lipschitz and bi-Lipschitz functions. Rev. Mat. Iberoamericana, 4(1):115–121, 1988.

[41] S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ_{1}. In Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science (FOCS 2005), pages 53–62, 2005.

[42] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839–858, 2005.

[43] R. Krauthgamer and Y. Rabani. Improved lower bounds for embeddings into L_{1}. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1010–1017, New York, 2006. ACM.

[44] K. Kuratowski and C. Ryll-Nardzewski. A general theorem on selectors. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 13:397–403, 1965.

[45] T. Laakso. Ahlfors Q-regular spaces with arbitrary Q > 1 admitting weak Poincaré inequality. Geom. Funct. Anal., 10(1):111–123, 2000.

[46] U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285–307, 2001.

[47] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

[48] J. R. Lee and A. Naor. L_{p} metrics on the Heisenberg group and the Goemans-Linial conjecture. In Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 99–108. IEEE Computer Society, 2006.

[49] T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999.

[50] J. Lindenstrauss. On nonlinear projections in Banach spaces. Michigan Math. J., 11:263–287, 1964.

[51] N. Linial. Finite metric-spaces—combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pages 573–586, Beijing, 2002. Higher Ed. Press.

[52] N. Linial. Squared ℓ_{2} metrics into ℓ_{1}. In Open problems on embeddings of finite metric spaces, edited by

J. Matoušek, page 5. 2002. Available at http://kam.mff.cuni.cz/~matousek/metrop.ps.

[53] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

[54] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[55] F. Montefalcone. Some relations among volume, intrinsic perimeter and one-dimensional restrictions of BV functions in Carnot groups. Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 4(1):79–128, 2005.

[56] R. Montgomery. A tour of subriemannian geometries, their geodesics and applications, volume 91 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2002.

[57] P. Pansu. Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. of Math. (2), 129(1):1–60, 1989.

[58] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), pages 300–306 (electronic), New York, 1999. ACM.

[59] F. Shahrokhi and D. W. Matula. The maximum concurrent flow problem. J. Assoc. Comput. Mach., 37(2):318–334, 1990.

[60] D. B. Shmoys. Cut problems and their application to divide-and-conquer. In Approximation Algorithms for NP-hard Problems, (D.S. Hochbaum, ed.), pages 192–235. PWS, 1997.

[61] E. 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.

[62] R. Tessera. Quantitative property A, Poincaré inequalities, L^{p}-compression and L^{p}-distortion for metric measure spaces. Geom. Dedicata, 136:203–220, 2008.

[63] J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, New York, 1975. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.

[64] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991.

Courant Institute, New York University, 251 Mercer Street, New York NY 10012, USA.