HOMOTOPY HYPERBOLIC 3-MANIFOLDS ARE HYPERBOLIC

HOMOTOPY HYPERBOLIC 3-MANIFOLDS ARE HYPERBOLIC David Gabai, G. Robert Meyerhoff, and Nathaniel Thurston

Section 0: Introduction

This paper introduces a rigorous computer-assisted procedure for analyzing hyperbolic 3-manifolds. This technique is used to complete the proof of several long-standing rigidity conjectures in 3-manifold theory as well as to provide a new lower bound for the volume of a closed orientable hyperbolic 3-manifold.

Theorem 0.1: Let N be a closed hyperbolic 3-manifold. Then

1) If f: M → N is a homotopy equivalence where M is a closed irreducible 3-manifold, then f is homotopic to a homeomorphism.

2) If f, g: M → N are homotopic homeomorphisms, then f is isotopic to g.

3) The space of hyperbolic metrics on N is path connected.

Remarks: Under the hypothesis that M is hyperbolic, conclusion i) follows from Mostow’s rigidity theorem [Mo]. Under the hypothesis that N is Haken, conclusions i)-ii) follow from Waldhausen [W]. If N is both Haken and hyperbolic, then iii) follows by combining [Mo] and [W]. Since non-Haken manifolds are necessarily orientable we will from now on assume that all manifolds under discussion are orientable.

Theorem 0.1 with the added hypothesis that a closed geodesic δ ⊂ N has a non coalescable insulator family was proven by Gabai (see [G]). Thus Theorem 0.1 follows from [G] and the main technical result of this paper which is,

Theorem 0.2: If δ is a shortest geodesic in a closed orientable hyperbolic 3-manifold, then δ has a non-coalescable insulator family.

Remarks: If δ is the core of an embedded hyperbolic tube of radius (ln 3)/2 = 0.549306... then δ has a non-coalescable insulator family by Lemma 5.9 of [G]. In this paper we establish a second condidition, sufficient to guarantee the existence of a non-coalescable insulator family for δ. That is if Corona (δ) < 2π/3. (Corona(δ) < 2π/3 if tube radius(δ) > (ln 3)/2). We use the expression “N satisfies the insulator condition” when there is a geodesic δ which has a non-coalescable insulator family.

We prove Theorem 0.2 by first showing that all closed hyperbolic 3-manifolds, with seven families of exceptional cases, have embedded hyperbolic tubes of radius (ln 3)/2 about their shortest geodesics. Conjecturally, up to isometry, there are exactly six exceptional manifolds (see Conjecture 4.2). Second, we show that any shortest geodesic δ in six of the seven families has Corona(δ) < 2π/3. Finally, we show that the seventh family corresponds to Vol3, the third smallest known hyperbolic 3-manifold, and that the insulator condition holds for Vol3. Each of the three parts of the proof is carried out with the assistance of a rigorous computer program.

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

Here is a hint why Theorem 0.2 might be amenable to computer proof. If a shortest geodesic δ in a hyperbolic 3-manifold N does not have a (ln 3)/2 tube then there is a 2-generator subgroup G of π_{1}(N) = Γ which also does not have that property. That is, after identifying N = H^{3}/Γ and letting Z = H^{3}/G, then a shortest geodesic in Z does not have a (ln 3)/2 tube. G is a group of 2 generators, generated by f and w, where f ∈ Γ is a primitive hyperbolic isometry whose fixed axis δ_{0} ⊂ H^{3} projects to δ, and w is an isometry of H^{3} which takes δ_{0} to a nearest translate. Here δ_{0} is a lift of δ to H^{3}.

The space of relevant 2-generator groups in Isom(H^{3}) naturally lives in C^{3}. We show that except for seven small regions in C^{3} the shortest geodesic in any discrete, torsion free, parabolic free 2-generator group must have a (ln 3)/2 tube. Further, if Corona(δ) ≥ 2π/3, then there is a 2-generator subgroup with that property. That is, there is a 2-generator subgroup G of π_{1}(N) such that if N_{1} = H^{3}/G, then Corona(δ_{1}) = Corona(δ) ≥ 2π/3 for some shortest geodesic δ_{1} in N_{1}. We show that away from a single small open set in C^{3}, every discrete, torsion free, parabolic free 2-generator group G satisfies Corona(δ) < 2π/3, where δ is a shortest geodesic in H^{3}/G. We finally show that the exceptional open set contains a unique manifold which is Vol3. In fact we show that if a shortest geodesic δ in N satisfies Corona(δ) > 2π/3, then N = Vol3. A variant of the above arguments shows that Vol3 satisfies the insulator condition.

This paper is organized as follows. In Chapter 1 we describe a space P′ ⊂ C^{3} which naturally parametrizes all relevant 2-generator groups. We explain how a theorem of Meyerhoff as well as elementary hyperbolic geometry considerations imply that we need only consider a compact portion P of C^{3}. We explain in detail the plan for proving Theorem 0.2. We will actually be working in the parameter space W = exp(P). The technical reasons for working in W is described at the end of this section. In Chapter 2 we describe and prove the necessary results about the Corona function. In Chapter 3 we prove that the exceptional open set in C^{3} contains only Vol3. Also if δ is a shortest geodesic in a closed orientable hyperbolic 3-manifold N and Corona(δ) ≥ 2π/3, then N =Vol3. Nonetheless, we are able to show that Vol3 satisfies the insulator condition. In Chapter 4, we prove some applications, one of which is discussed briefly below.

In Chapters 5 through 8 we address the computer-related aspects of the proof. Here, the method for describing the decomposition of the parameter space W into sub-regions is given, and the conditions used to eliminate all but seven of the sub-regions are discussed. At the end of this chapter, the first part of a detailed example is given. Eliminating a sub-region requires that a certain function is shown to be bounded appropriately over the entire sub-region. This is carried out by using a first-order Taylor series approximation of the function together with a remainder bound. Our computer version of such Taylor series with remainder bounds is called an AffApprox and in Chapter 6, the relevant theory is developed. At this point, the detailed example of Chapter 5 can be completed.

Finally, in Chapters 7 and 8, round-off error analysis appropriate to our set-up is introduced. Specifically, in Chapter 8, round-off error is incorporated into the AffApprox formulas introduced in Chapter 6. The proofs here require an analysis of round-off error for complex numbers, which is carried out in Chapter 7.

We used two rigorous computer programs in our proofs—verify and fudging. These programs are provided in Appendices 1 and 2. Actually, fudging is a variation of verify and as such we only provide the sections of fudging that are changed. The proofs amount to having verify and fudging analyze several computer files. These computer files are available from the Geometry Center. Details about how to get them and the programs can be found at

http://www.geom.umn.edu:/locate/HomotopyHyperbolic

A consequence of this work is that either the shortest geodesic in a closed orientable 3-manifold N has a 1.059191579962 … /2 tube or N = Vol3. The volume of Vol3 is 1.01... and by [GM2] if N has a log(3)/2 = 0.549306 … tube about a geodesic, then the volume of N is greater than 0.16668 …. This leaves some exceptional cases that can be analyzed using data provided by verify. In any case, we obtain

Theorem 4.5: If N is a closed hyperbolic 3-manifold, then vol(N) > 0.16668 ….

Remark: The best published lower bound for volume is 0.001 by [GM1], which improved the lower bound of 0.0008 of [M2].

Acknowledgements: We thank The Geometry Center and especially Al Marden and David Epstein for the vital and multifaceted roles they played in this work. Jeff Weeks and SNAPPEA provided valuable data and ideas. In fact it was the data from an undistributed version of SNAPPEA that encouraged us to pursue a computer-assisted proof of Theorem 0.2.

Bob Riley specially tailored his program POINCARÉ to directly address the needs of our project. His work provided many leads in our search for killerwords. Further, he provided the first proofs that the six exceptional regions (other than the Vol3 region) correspond to closed orientable 3-manifolds. The authors are deeply grateful for his help.

The first-named author thanks the NSF for partial support. Some of the first author’s preliminary ideas were formulated while visiting David Epstein at the University of Warwick Mathematics Institute. The second-named author thanks the NSF for partial support; the USC and Caltech Mathematics Departments for supporting him as a visitor while much of this work was done; and Jeff Weeks, Alan Meyerhoff, and especially Rob Gross for computer assistance. The third-named author thanks the NSF for partial support; and the Geometry Center and the Berkeley Mathematics Department for their support.

Chapter 1: Killer Words and the Parameter Space

Definition 1.1: We will work in the upper-half-space model for hyperbolic 3-space. All isometries will be orientation preserving. If f is an isometry, then we define Relength(f) = inf{ρ(x, f(x)) | x ∈ H^{3}}. Thus Relength(f) = 0 if and only if f is either a parabolic or elliptic isometry. If Relength(f) ≠ 0, then f is hyperbolic and fixes a unique geodesic σ in H^{3}. In that case σ is oriented (the negative end being the repelling fixed point on S_{∞}^{2}) and the isometry f is the composition of a rotation of t (mod 2π) radians along σ (the sign of the angle of rotation is determined by the right-hand rule) followed by a pure translation of H^{3} along σ of l = Relength(f). We define length(f) = l +it. If σ is an oriented geodesic in H^{3}, then it makes sense to talk about an l + it translation of H^{3} along σ, even when l ≤ 0.

If f is elliptic, then f is a rotation of t radians about some oriented geodesic. If f is elliptic, we define length(f) = |t|i, the absolute value accounting for the arbitrariness of the orientation of the fixed geodesic. If f is parabolic or the identity, we define length(f) = 0 + i0. So, for all isometries we have that Relength = Re(length).

Definition 1.2: If G is a subgroup of Isom(H^{3}), then we say that f is an element of smallest length in G if Relength(f) ≤ Relength(g) for all g ∈ G, g ≠ id.

Convention 1.3: Let B denote the oriented geodesic t(0, 0, 1), with negative end (0, 0, 0). Let C denote the oriented geodesic with negative endpoint (−1, 0, 0) and positive endpoint (1, 0, 0).

Lemma 1.4: If the isometry f is represented by the matrix A ∈ PSL(2, C), then

length(f) = 2Arccosh(trace(A)/2),

where the branch of Arccosh with positive real values is taken, unless the real part is zero in which case the non-negative imaginary part is taken.

Proof: Because trace is a conjugacy invariant, we can normalize our set-up via conjugation and assume that the axis of f is B. As such, A is a diagonal matrix, with diagonal entries p and p^{−1}.

The action of A on the bounding complex plane is simply multiplication by p^{2}. Extending this action to upper-half-space in the natural way rotates the z− axis by angle arg(p^{2}) and sends (0, 0, 1) to (0, 0, |p|^{2}). Thus, Im(length(f)) = arg(p^{2}) = Im(ln(p^{2})) and, using the hyperbolic metric, Re(length(f)) = ln(|p|^{2}) = Re(ln(p^{2})). That is, length(f) = ln(p^{2}). Thus, we need only show that 2 ln(p) = 2Arccosh(trace(A)/2). But this follows because cosh(ln(p)) = (p + p^{−1})/2 = trace(A)/2.

Definition 1.5: If σ, τ are disjoint oriented geodesics in H^{3} which do not meet at infinity, then define distance(σ, τ) = length(w) where w ∈ Isom(H^{3}) is the hyperbolic element which translates H^{3} along the unique common perpendicular between σ and τ and which takes the oriented geodesic σ to the oriented geodesic τ. The oriented common perpendicular from σ to τ is called the orthocurve between σ and τ. The ortholine between σ and τ is the complete oriented geodesic in H^{3} which contains the orthocurve between σ and τ.

If σ, τ intersect at one point in H^{3} then slight changes must be made in the above definition. The ortholine has no natural orientation, the orthocurve is a point, and w is an elliptic isometry.

If σ, τ intersect at infinity, then there is no unique common perpendicular, hence no ortholine, and distance(σ, τ) = 0+i0, or 0+iπ depending on whether or not σ and τ point in the same direction at their intersection point(s) at infinity.

Lemma 1.6: distance(σ, τ) = distance(τ, σ)

Lemma 1.7: If the isometry f is represented by the matrix

A = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ PSL(2, C),

then 2distance(f(B), B) = 2Arccosh(ad + bc). Again, the branch of Arccosh with positive real values is taken, unless the real part is zero in which case the non-negative imaginary part is taken.

Proof: In the case where B and f(B) do not intersect at infinity, we will compute the length of h, the square of the transformation taking B to f(B) along their ortholine. h = (f ∘ ρ ∘ f^{−1}) ∘ ρ where ρ is 180-degree rotation about B and hence (f ∘ ρ ∘ f^{−1}) is 180-degree rotation about f(B). ρ and f are represented by the matrices

± ( \begin{matrix}i & 0 \\ 0 & −i \end{matrix} ) and ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ PSL(2, C).

Hence, h = (f ∘ ρ ∘ f^{−1}) ∘ ρ can be computed to have representation

( \begin{matrix}ad + bc & 2ab \\ 2cd & ad + bc \end{matrix} ) .

Using Lemma 1.3, we have that

2distance(f(B), B) = length(h) = 2Arccosh(trace(h)/2) = 2Arccosh(ad + bc).

If f fixes the point (0, 0, 0) at infinity, then c = 0, ad = 1 and the formula holds. Similarly for the other cases in which B and f(B) intersect at infinity. Note that this formula only defines distance(f(B), B) modulo iπ, but this is sufficient for our purposes.

Definition 1.8: Let δ be a geodesic in the hyperbolic 3-manifold N. Then tuberadius(δ) = sup{r | there exists in N an embedded D^{2} × S^{1} of radius r centered about the geodesic δ}.

Lemma 1.9: Let δ be a geodesic in the hyperbolic 3-manifold N and {δ_{i}}_{i≥0} be the set of its distinct lifts to H^{3}, then tuberadius(δ) = min{Redistance(δ_{0}, δ_{i}) | i ≠ 0}.

Definition 1.10: We define an open subset P′ of C^{3} which naturally parametrizes the collection of conjugacy classes of 2-generator subgroups G ⊂ Isom(H^{3}) with specified generators f, w where f is hyperbolic and w is not parabolic. By conjugating G we can assume that f is a positive translation of H^{3} along the geodesic B, and that the orthocurve from w^{−1}(B) to B lies on C on the negative side of C ∩ B. Associated to {G, f, w}, the group G with specified generators f, w, is the parameter (L, D, R) = (l + it, d + ib, r + ia) where l + it = length(f) and d + ib = distance(w(B), B). The complex number r + ia is defined as follows. The isometry w is the composition of two isometries, first a d + ib translation of H^{3} along C, which takes w^{−1}(B) to B, as oriented geodesics, followed by an r + ia translation along B.

We are primarily interested in the set T′ ⊂ C^{3} which parametrizes all conjugacy classes of triples {G, f, w} where G is a group generated by a shortest element f which (positively) translates B and w ∈ G takes B to a nearest translate w(B) such that −Relength(f)/2 < Redistance( (ortholine from w^{−1}(B) to B), (ortholine from B to w(B))) ≤ Relength(f)/2. By conjugating G we can assume both that f is a positive translation along the geodesic B and that the orthocurve from w^{−1}(B) to B lies in C on the negative side of B ∩ C. See Figure 1.1.

Remark 1.11: Said another way, T′ corresponds to those parameters such that l is the real length of a shortest element of G, d is the real distance between B and a nearest translate, and −l/2 < r ≤ l/2. In what follows, it is essential to remember that an element α of P′ corresponds not only to a group G, but a group with two special generators. When α ∈ T′, then two (i.e. l and d) of α′s six real parameters correspond to invariants of {G, f, w}.

We are only interested in the subset of T′ corresponding to parameters α with d ≤ ln(3). The following two propositions imply this subset of T′ lives in a compact subset of P′.

Proposition 1.12: All closed geodesics of length less than 0.0979 in all hyperbolic 3manifolds have embedded solid tube neighborhoods of radius ln 3/2.

Proof: In [M1] it is proven that a geodesic of length x + iy has an embedded solid-tube neighborhood of radius r(x + iy) satisfying

sinh^{2}(r(x + iy)) = max_{n∈Z_{+}} \frac{1}{2}(\frac{\sqrt{1 − 2k(x, y, n)}}{k(x, y, n)} − 1) where k(x, y, n) = cosh(nx) − cos(ny).

Of course, we restrict to x + iy values which produce positive radii r(x + iy) by means of this formula. It is easy to compute that for a given x + iy we need to have n for which 0 < k(x, y, n) < −1 + \sqrt{2} to produce a positive radius tube by this method.

The function \frac{1}{2}(\frac{\sqrt{1−2k}}{k} − 1) is decreasing on the interval (0, −1 + \sqrt{2}). It is therefore easy to solve for the range of k values that produce radii r greater than ln 3/2. In fact, positive k less than 0.3397 work.

Thus, to complete the proof of this proposition, we need to show that when a geodesic has real length x less than 0.0979, that for all angles y there exists a positive integer n for which k(x, y, n) is less than 0.3397. Because cosh is an increasing function, we can restrict our analysis to x = 0.0979. Thus, we need only show that given any angle y, we can find a positive integer n such that cosh(n0.0979) − cos(ny) < 0.3397. When n > 8 we can compute that cosh(n0.0979) − cos(ny) > 0.3397, and we therefore restrict to positive integers n ≤ 8.

We now consider angles y. Because cos is an even function, we need only consider y ∈ [0, π]. We will cover [0, π] by 11 overlapping closed sub-intervals σ_{i} each of which has an associated positive integer n_{i} for which cosh(n_{i}0.0979) − cos(n_{i}y) < 0.3397 is true for all y ∈ σ_{i}.

σ_{0} = [0.000, 0.843] n_{0} = 1
σ_{1} = [0.835, 0.960] n_{1} = 7
σ_{2} = [0.951, 1.143] n_{2} = 6
σ_{3} = [1.123, 1.391] n_{3} = 5
σ_{4} = [1.386, 1.755] n_{4} = 4
σ_{5} = [1.733, 1.858] n_{5} = 7
σ_{6} = [1.832, 2.357] n_{6} = 3
σ_{7} = [2.334, 2.3792] n_{7} = 8
σ_{8} = [2.3789, 2.647] n_{8} = 5
σ_{9} = [2.630, 2.755] n_{9} = 7
σ_{10} = [2.730, π] n_{10} = 2

Proposition 1.13: If the shortest geodesic in a closed hyperbolic 3-manifold has length greater than or equal to 1.29, then it has an embedded solid tube neighborhood of radius ln 3/2.

Proof: Consider the following folklore result: The shortest geodesic in a closed hyperbolic 3-manifold has an embedded solid tube neighborhood of radius l/4 where l is the real length of the shortest geodesic. The proof is simple: Expand a solid tube around the shortest geodesic, if it hits itself before a radius of l/4 then we will construct a loop of length less than l, a contradiction to “shortestness.” Drop the two obvious perpendiculars from the hitting point down to the core geodesic. Consider the following loop— down one perpendicular, follow the shorter direction on the core geodesic, up the other perpendicular. This non-trivial loop has length less than l/4 + l/2 + l/4 < l.

We now improve on this loop. Replace the first half of the journey by the hypotenuse of the right triangle formed by the first perpendicular and the first half of the shorter arc along the core geodesic. Replace the second half of the journey by the hypotenuse of the right triangle formed by the second perpendicular and the second half of the shorter arc along the core geodesic. Using the hyperbolic Pythagorean Theorem (see [F]) cosh c = (cosh a)(cosh b) with a = ln 3/2 and b = l/4 we get that the length of the constructed loop is 2 cosh^{−1}(cosh(ln 3/2)(cosh(l/4))) and this is less than l when l > 1.29, by a calculation and the fact that 2 cosh^{−1}(cosh(ln 3/2)(cosh(l/4)) − l is a decreasing function of l.

In fact, we can solve explicitly for the value of l at which

2 cosh^{−1}(cosh(ln 3/2)(cosh(l/4)) − l = 0.

Noting that cosh(ln 3/2) = \frac{2}{\sqrt{3}} we get \frac{2}{\sqrt{3}}(cosh(l/4))) = cosh(l/2). Using a half-angle formula for cosh(l/2) we get \frac{2}{\sqrt{3}}(cosh(l/4))) = 2 cosh^{2}(l/4) − 1. Setting x = cosh^{2}(l/4) we get the quadratic \frac{2}{\sqrt{3}}x = 2x^{2} − 1. Solving and substituting, we get l = 1.289784...

Definition 1.14: Let P ⊂ P′ be those parameters α = (l + it, d + ib, r + ia) such that a) −π ≤ t ≤ 0

b) 0 ≤ r ≤ l/2
c) 0.0978 ≤ l ≤ 1.29
d) l/2 ≤ d ≤ ln(3)

Define T = T′ ∩ P.

Lemma 1.15: If α = (l + it, d + ib, r + ia) ∈ T′ has d ≤ ln(3) and corresponds to a 2generator group {G_{α}, f_{α}, w_{α}}, then there exists a parameter β ∈ T with associated group {G_{β}, f_{β}, w_{β}} such that G_{β} is conjugate to G_{α}.

Proof: d < l/2 is eliminated from consideration by the first paragraph of the proof of Proposition 1.13, and the definition of T′. If d ≤ ln(3), then 0.0978 ≤ l ≤ 1.29 by Proposition 1.12. If for the triple {G, f, w} we have −l/2 < r < 0, then the triple {G, f, w^{−1}} is conjugate to an element of T whose new r-parameter is −r. Thus we can assume that b), c), and d) hold for the relevant {G, f, w}.

This leaves property a). Conjugating G by a reflection in the geodesic plane spanned by B and C changes the t-parameter to −t (mod 2π). The effect on b and a is irrelevant.

By [G; Lemma 5.9] a closed orientable hyperbolic 3-manifold N satisfies the insulator condition provided that tuberadius(δ) > ln(3)/2 for some geodesic δ ⊂ N. Thus we are led to ask

Question 1.16: List all closed orientable hyperbolic 3-manifolds N possessing a shortest geodesic δ such that tuberadius(δ) ≤ ln(3)/2.

Remarks 1.17: i) Using a J. Weeks-modified version of Snappea it was known experimentally that any shortest geodesic in Vol3 has a .415... tube (see [G]). Conjecturally, up to isometry, there are a total of six manifolds in the list answering Question 1.16 (see Theorem 1.30 and Remark 1.31 iii, and Theorem 4.xx).

ii) If a shortest geodesic δ in N satisfies tuberadius(δ) ≤ ln(3)/2, then N can be expressed as H^{3}/Γ where a lift of δ is the geodesic B, and C is an ortholine between B and a nearest Γ−translate. Thus N gives rise to an element α ∈ T . In fact N may give rise to finitely many different elements of T . Thus we need to investigate.

Question 1.18: Name all parameters α = (l + it, d + ib, r + ia) ∈ T .

We now describe our method of (partially) answering Question 1.18. There is a technical point to mention: starting with Definition 1.22, we will work in the space W ⊃ exp(P), but for now we will describe the results in terms of the unexponentiated space P.

We will partition P into about one billion regions {P_{i}} and show that T is disjoint from all but seven small such regions. Suppose that P_{i} is a region of this partition and α ∈ P_{i}. Let h be a word in the letters f, w and their inverses. Associated to the parameter α = (l_{α}+it_{α}, d_{α}+ib_{α}, r_{α}+ia_{α}) there are the group elements f_{α}, w_{α} and hence h_{α}. Suppose that h_{α} ≠ f_{α}^{m}. We ask

a) Is Relength(h_{α}) < Relength(f_{α}) = l_{α}?
b) Is Redistance(h_{α}(B), B) <Redistance(w_{α}(B), B) = d_{α}?

If either a) or b) is true, then α ∉ T .

Now let β ∈ P_{i}, with f_{β}, w_{β}, and h_{β} the associated hyperbolic isometries. If say a) is true for α then so is the statement Relength(h_{β}) < Relength(f_{β}) = l_{β} for β sufficiently close to α. Thus we can show that T ∩ P_{i} = ∅ if we can find an α for which say statement a) is true, and then use first-order Taylor approximation (with error/remainder term) to show that the corresponding statement holds for all β ∈ P_{i}.

Definition 1.19: A word h in w, f, w^{−1}, f^{−1} for which statement a) (resp. b)) holds (non-trivially) for each β ∈ P_{i} is called a killer word for P_{i} with respect to contradiction a) (resp. b)).

Summary 1.20: With seven exceptions, to each of the approximately one billion regions partitioning P, we will associate a killerword and a contradiction.

Remark 1.21: Computers are well suited for partitioning a region such as P into many sub-regions {P_{i}}, and finding a killerword h_{i} which eliminates α_{i} ∈ P_{i} due to contradiction C_{i}. Depending on the contradiction, we find computable expressions for approximations of the values of Relength(h_{β}) or Redistance(h_{β}(B), B) and thus use the computer to eliminate all of P_{i}.

There are a number of difficulties in executing this procedure. First, a uniform mesh of the partition would yield far too many sub-regions to be handled by computer. In fact with 6 real parameters, refining a given mesh by a factor of 10 would change the partition size by a factor of 10^{6}. Our method for refining the parameter space and the way the computer keeps track of the refinements are discussed briefly in Remark 1.27 and in more detail in Chapter 5.

A second difficulty is finding the killerwords. In practice, most of the parameter space is eliminated by killerwords of length less than 7, but a number of spots need killerwords of length 10 and a few regions need killerwords of length 35. A brute force enumeration and testing of the various words would take far too long. Note that there are more than 70,000 words of length 10 and 4×3^{29} words of length 30. Techniques for finding killer words can be found in [Txxx].

Finally, there is the issue of rigor. The main difficulty in making the plan work rigorously is that we need to bound the difference between what the computer thinks a value is and what the value actually is. In particular we need to control roundoff error, which becomes quite significant when one does a large number of multiplications, e.g. in the computation of length(h_{α}) when h is a 35 letter word. Another issue is to make sure that h_{β} is bounded away from f_{β}^{m}, and in particular bounded away from id, when computing say Relength(h_{β}). A large portion of this paper is devoted to addressing these issues. See Remark 1.30 for a more detailed discussion.

Definition 1.22: Let

W = {(x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) : |x_{i}| ≤ 4 × 2^{(5−i)/6} for i = 0, 1, 2, 3, 4, 5}

⊃ exp(P) = {(x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) | x_{0} + ix_{3} = exp(e), x_{1} + ix_{4} = exp(f), x_{2} + ix_{5} = exp(g)where(e, f, g) ∈ P}

and let

S = exp(T ).

Also, let

L′ = exp(L) = exp(l + it), D′ = exp(D) = exp(d + ib), R′ = exp(R) = exp(r + ia).

Remarks 1.23: i) We work with W instead of exp(P) because we want our initial region to be a (6-dimensional) box that is easily sub-divided. This has the side-effect that certain sub-boxes W_{i} of W will be eliminated because they are outside of exp(P) rather than by the analogues of conditions a) and b) above. The entire collection of conditions is given in Section 5.

ii) All the ideas expressed in 1.18-1.21 will be carried out in the parameter space W rather than the space P. That is mainly because of Lemmas 1.24 - 1.26 which demonstrate that while working in W one need only understand the basic arithmetic operations +, −, ×, /, √.

iii) The reason for choosing the co-ordinates of W so that L′ = x_{0} + ix_{3}, D′ = x_{1} + ix_{4}, R′ = x_{2} + ix_{5} was to gain a mild computer advantage.

Lemma 1.24: If (L′, D′, R′) ∈ W and f, w are the generators of the associated group G then a)

Matrix[f] = ( \begin{matrix}\sqrt{L′} & 0 \\ 0 & 1/\sqrt{L′} \end{matrix} )

b)

Matrix[w] = ( \begin{matrix}\sqrt{R′} ∗ ch & sh ∗ \sqrt{R′} \\ sh/\sqrt{R′} & ch/\sqrt{R′} \end{matrix} )

where ch = (\sqrt{D′} + 1/\sqrt{D′})/2 and sh = (\sqrt{D′} − 1/\sqrt{D′})/2

Proof: a) By our set-up we have that the (oriented) axis of f is B. Following the proof of Lemma 1.3,

Matrix[f] = ( \begin{matrix}p & 0 \\ 0 & 1/p \end{matrix} )

where p = exp(length(f)/2) = \sqrt{exp(length(f))} = \sqrt{exp(L)} = \sqrt{L′}

b) w = β ∘ α where β is translation of distance R along B and α is translation of distance D along C. Thus,

Matrix[β] = ( \begin{matrix}\sqrt{R′} & 0 \\ 0 & 1/\sqrt{R′} \end{matrix} )

and Matrix[α] can be computed to be

( \begin{matrix}cosh(D/2) & sinh(D/2) \\ sinh(D/2) & cosh(D/2) \end{matrix} ) .

But cosh(D/2) = (exp(D/2) + exp(−D/2))/2 = (\sqrt{D′} + 1/\sqrt{D′})/2 = ch and similarly for sh. Thus,

Matrix[α] = ( \begin{matrix}ch & sh \\ sh & ch \end{matrix} )

and b) follows by matrix multiplication.

Lemma 1.25: If h ∈ Isom(H^{3}) is represented by the matrix

A = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ PSL(2, C),

then

a) exp(Relength(h)) = |trace(A) ± \sqrt{(trace(A)/2)^{2} − 1}|^{2}

b) exp(Redistance(h(B), B)) = |orthotrace(A) ± \sqrt{(orthotrace(A)/2)^{2} − 1}| where orthotrace(A) = ad + bc.

Here the +, − produce reciprocal values for exp(Relength(h)), and we take the one producing the larger value, unless the value is 1, in which case there is no choice.

Proof: Because cosh(x) = (exp(x) + exp(−x))/2 it is easy to compute that cosh^{−1}(x) = log(x ± \sqrt{x^{2} − 1}). Of course, x − \sqrt{x^{2} − 1} and x + \sqrt{x^{2} − 1} are inverses, which corresponds to the fact that cosh^{−1}(x) for x ≠ 1 consists of values differing by a factor of −1.

a) exp(Relength(h)) = | exp(length(h))| = | exp(2Arccosh(trace(A)/2))| = |(trace(A)/2) ± \sqrt{(trace(A)/2)^{2} − 1}|^{2} where the second equality follows from Lemma 1.2.

b) exp(Redistance(h(B), B)) = | exp(distance(h(B), B))| = | exp(Arccosh(ad + bc))| = |(ad + bc) ± \sqrt{(ad + bc)^{2} − 1}| where the second equality follows from Lemma 1.7.

Remarks 1.26: i) It follows from Lemma 1.25 that if h is a word in f, w and their inverses, then for any parameter value α ∈ W, exp(Relength(h_{α})), and exp(Redistance(h_{α}(B), B)) can be computed using only the operations +, −, ×, /, √.

ii) During the course of the computer work needed to prove the main theorems, the parameter space W was decomposed into sub-boxes by computer via a recursive subdivision process: Given a sub-box that is being analyzed, either it can be handled, or it cannot. If it cannot be handled, it is sub-divided in half by a hyper-plane {x_{i} = c} (where i runs through the various co-ordinate dimensions cyclically) and the two pieces are analyzed separately. And so on.

As such, a sub-box of W can be described by a sequence of 0’s and 1’s where 0 means “take the lesser x_{i} values” and 1 means “take the greater x_{i} values.” Remarkably, for the decomposition of W into sub-boxes, all the sub- box descriptions could be neatly encoded into one tree (although in practice we found it preferable to use several trees to describe the entire decomposition). This is described in Chapter 5.

iii) In the following proposition, seven exceptional boxes are described as sequences of 0’s and 1’s. Four of the boxes—X_{0}, X_{4}, X_{5}, X_{6}— are each the union of two abutting sub-boxes, X_{0} = X_{0a} ∪ X_{0b} and so on. It is a pleasant exercise to work through the fact that they abut.

It is also a pleasant exercise to calculate by hand the co-ordinate ranges of the various sub-boxes. For example, the range of the last co-ordinate (i.e., x_{5}) of the sub-box

X_{6a} = 111000000001000111 111111110101001111 011111010111111111 110001001011000111 0

is found by taking the 6th entry, the 12th, entry, the 18th entry and so on. These entries are 011111111111. The first entry (0) means take the lesser x_{5} values, and produces the interval [−4, 0]. The second entry (1) means take the greater x_{5} values, and produces the interval [−2, 0]. The third entry (1) produces [−1, 0]. Continuing, we see that X_{6a} has −2^{−9} ≤ x_{5} = Im(R′) ≤ 0. The other co-ordinates can be computed in the same fashion, although they must at the end be multiplied by the facter 2^{(5−i)/6} (see the definition of the initial box W). The range of co-ordinate values is given for each of the seven boxes. Finally, two quasi-relators are given for each sub-box X_{0}, X_{1}, …, X_{6}.

Definition 1.27: A quasi-relator in a sub-box X of W is a word in f, w, f^{−1}, w^{−1} that is close to the identity throughout X and experimentally appears to be converging to the identity at some point in X. In particular, a quasi-relator rigorously has Relength less than that of f at all points in X.

Proposition 1.28: S∩(W−⋃_{n=1,...,7} X_{n}) = ∅ where the X_{n} are the exceptional sub-boxes

X_{0a} = 001000110111110001 101001010101011001 011011010111101101 100001101101000111 010001110101100101 1101110111110100

X_{0b} = 001001110110110000 101000010100011000 011010010110101100 100000101100000110 010000110100100100 1101100111100100

X_{0} = ( \begin{matrix}−0.840655162503 … ≤ Re(L′) ≤ −0.840600786360 … \\ −0.840642408899 … ≤ Re(D′) ≤ −0.840593965263 … \\ 0.999979499517 … ≤ Re(R′) ≤ 1.000022657890 … \\ −2.137267196028 … ≤ Im(L′) ≤ −2.137228746289 … \\ −2.137295441962 … ≤ Im(D′) ≤ −2.137226932315 … \\ −0.000061035156 … ≤ Im(R′) ≤ 0.000061035156 … \end{matrix} )

X_{0} quasi-relators:

r_{1} = fwF wwF wfww

r_{2} = F wfwfW fwfw

X_{1} = 001000110001110110 011101000110111110 100010110000100011 101101001101001000 110101011000000100 000

X_{1} = ( \begin{matrix}−1.348528333122 … ≤ Re(L′) ≤ −1.348310828552 … \\ −0.543343817104 … ≤ Re(D′) ≤ −0.543150042561 … \\ 0.903908961497 … ≤ Re(R′) ≤ 0.904081594988 … \\ −2.661029541660 … ≤ Im(L′) ≤ −2.660721943747 … \\ −2.858770529287 … ≤ Im(D′) ≤ −2.858496490701 … \\ −1.471679687500 … ≤ Im(R′) ≤ −1.471435546875 … \end{matrix} )

X_{1} quasi-relators:

r_{1} = F F wF W F W fW F W F wF F ww

r_{2} = F F wwF wfwfW fwfwF ww

X_{2} = 001000110101010010 101010110001100101 110111100001101010 111100100000010001 111100

X_{2} = ( \begin{matrix}−1.787017545957 … ≤ Re(L′) ≤ −1.785277509398 … \\ −1.074286063490 … ≤ Re(D′) ≤ −1.072735867150 … \\ 0.741633479486 … ≤ Re(R′) ≤ 0.743014547418 … \\ −2.272533378081 … ≤ Im(L′) ≤ −2.271302986431 … \\ −2.718462773249 … ≤ Im(D′) ≤ −2.717366618905 … \\ −1.529296875000 … ≤ Im(R′) ≤ −1.528320312500 … \end{matrix} )

X_{2} quasi-relators:

r_{1} = F wfwfW ffW fwfwF ww

r_{2} = F F wF F wwF wfwfwF ww

X_{3} = 111000000001000110 011011101101011000 111101011110001100 111111100110110000 0000100010100010

X_{3} = ( \begin{matrix}0.581172210661 … ≤ Re(L′) ≤ 0.581607219801 … \\ 1.156446469500 … ≤ Re(D′) ≤ 1.156834018585 … \\ 1.404200819866 … ≤ Re(R′) ≤ 1.404546086849 … \\ −3.312214322575 … ≤ Im(L′) ≤ −3.311906724662 … \\ −2.756280098119 … ≤ Im(D′) ≤ −2.755732020947 … \\ −1.179687500000 … ≤ Im(R′) ≤ −1.179199218750 … \end{matrix} )

X_{3} quasi-relators:

r_{1} = F F wfwF F wwF W F wF W fW F W ffW F W fW F wF W F ww r_{2} = F F wfwF wfW fwfW W fwfW fwF wfwF F wwF W F ww

X_{4a} = 111000000001000110 011001001111101010 011110110110111101 100011111110110110 10000111101

X_{4b} = 111000000001000110 011001001111101010 111110010110011101 000011011110010110 00000101101

X_{4} = ( \begin{matrix}0.333217001023 … ≤ Re(L′) ≤ 0.334957037582 … \\ 0.977398792251 … ≤ Re(D′) ≤ 0.978173890421 … \\ 1.354137107330 … ≤ Re(R′) ≤ 1.354827641296 … \\ −3.319596672476 … ≤ Im(L′) ≤ −3.318981476651 … \\ −2.825337821794 … ≤ Im(D′) ≤ −2.824789744622 … \\ −1.225585937500 … ≤ Im(R′) ≤ −1.224609375000 … \end{matrix} )

X_{4} quasi-relators:

r_{1} = F F wfwF wfW fwfW fwF wfwF F wwF W F wF W F ww r_{2} = F F wfwF wfwF F wwF W F wF W fW F W fW F wF W F ww

X_{5a} = 001000110001110111 001111000101111111 101111100111001111 000001111011110111 1

X_{5b} = 001001110000110110 001110000100111110 101110100110001110 000000111010110110 1

X_{5} = ( \begin{matrix}−1.379848991182 … ≤ Re(L′) ≤ −1.378108954623 … \\ −1.379674742433 … ≤ Re(D′) ≤ −1.376574349753 … \\ 0.999893182771 … ≤ Re(R′) ≤ 1.002655318635 … \\ −2.537067582893 … ≤ Im(L′) ≤ −2.534606799593 … \\ −2.536501152136 … ≤ Im(D′) ≤ −2.534308843448 … \\ −0.001953125000 … ≤ Im(R′) ≤ 0.001953125000 … \end{matrix} )

X_{5} quasi-relators:

r_{1} = F wF W F wF wfwfW fwfw

r_{2} = F wfwfW fW F W fW fwfw

X_{6a} = 111000000001000111 111111110101001111 011111010111111111 110001001011000111 0

X_{6b} = 111001000000000110 111110110100001110 011110010110111110 110000001010000110 0

X_{6} = ( \begin{matrix}1.378108954623 … ≤ Re(L′) ≤ 1.379848991182 … \\ 1.376574349753 … ≤ Re(D′) ≤ 1.379674742433 … \\ 0.999893182771 … ≤ Re(R′) ≤ 1.002655318635 … \\ −2.537067582893 … ≤ Im(L′) ≤ −2.534606799593 … \\ −2.536501152136 … ≤ Im(D′) ≤ −2.534308843448 … \\ −0.001953125000 … ≤ Im(R′) ≤ 0.001953125000 … \end{matrix} )

X_{6} quasi-relators:

r_{1} = F W F wF W fW F wF W F wfw

r_{2} = F W F wfwF wfW fwF wfw

Proof: Two computer files contain the data needed for the proof. The first computer file describes the partition of W into sub-boxes, and the second describes the killerwords and contradictions associated with each sub-box (other than the X_{i}). We have a computer program verify which shows that the killerwords in question actually do kill off their associated sub- boxes. This computer program addresses the issues of Remark 1.21. The code for verify is given in Appendix 1, although we encourage readers to produce their own verification programs.

In addition, verify showed that the listed words were quasi-relators for the given subboxes.

Corollary 1.29: If δ is a shortest geodesic in N, a closed orientable hyperbolic 3-manifold, then

i) either tuberadius(δ) > ln(3)/2 or exp(length(δ)) ∈ L(X_{k}) for some k ∈ 0, …, 6 where L(X_{k}) denotes the range of L′ values in the sub-box X_{k}.

ii) either tuberadius(δ) > ln(3)/2 or tuberadius(δ) = Re(D)/2 where exp(D) ∈ D(X_{k}) for some k ∈ 0, …, 6 where D(X_{k}) denotes the range of D′ values in the sub-box X_{k}.

Experimental Theorem 1.30: Associated to each of the sub-boxes X_{0}, X_{1}, …, X_{6} of W is a closed orientable 3-manifold of Heegaard genus 2 with fundamental group generated by f, w with 2 relators r_{1}, r_{2} as given in Proposition 1.28.

Experimental Proof: Experimentally, at some point in the sub-box X_{i} under consideration the quasi-relators are actually relators. Applying Berge [Be], it follows that the 2-generator 2-relator presentation < f, w; r_{1}, r_{2} > is the group presentation of a Heegaard genus 2 closed orientable 3-manifold.

Remarks 1.31: i) In Chapter 3 it is proven rigorously that Vol3, the hyperbolic 3-manifold with the third smallest volume known, is the unique manifold associated with sub-box X_{0}. As of this writing its not known if the other boxes have unique manifolds.

ii) Except for Vol3, Riley’s program POINCARÉ was the first to show (experimentally) that there is a closed orientable (hyperbolic) 3-manifold associated to each box. It provided a group presentation, which presumably could have been shown to be those of the above.

iii) Experimental evidence suggests that the manifolds associated to X_{5} and X_{6} are isometric hyperbolic 3-manifolds, isometric to the Weeks census manifold s479(−3, 1). Also experimentally, the manifold associated with X_{2} is s778(−3, 1) and the manifold associated with X_{1} is v2678(2, 1).

iv) Berge [Be] provides the explicit Heegaard genus 2 diagrams for each of the manifolds in Experimental Theorem 1.30, so that the dilligent reader can recover Dehn surgery descriptions of these manifolds.

Remark 1.32: It might be best to say that the list of killerwords and contradictions used to prove Proposition 1.28 was generated in an artistic rather than systematic mathematical way. Nevertheless, to have a rigorous mathematical proof one need only prove that these words work.

Remark 1.33: Recall that we use first-order Taylor approximations (with Remainder term) which we denote AffApprox’s to show that a killer word which eliminates a point x ∈ W_{i} eliminates all of W_{i}. In setting up a Taylor approximation system we avoided a considerable amount of calculation by using the parameter space W instead of working with P.

In the parameter space W, all functions analyzed via Taylor approximations are built up from the operations +, −, ×, /, √ . We prove combination formulas for these functions, which show how the Taylor approximations (including the Remainder term) change when one of these operations is applied to two AffApprox’s. This is carried out in Chapter 6.

To ensure that all of our computer calculations are rigorous, we use a round-off error analysis. Typically, this is done by using interval arithmetic on floating-point numbers. This is too slow for our purposes, and so we introduce round-off error at the level of AffApprox’s and incorporate the round-off error into the Remainder term. This also requires developing round-off error for complex numbers. This is all done in Chapters 7 and 8.

Chapter 2: The Corona Insulator Family

The upshot of Proposition 1.28 is that if a closed orientable hyperbolic 3-manifold has a shortest geodesic which does not have an embedded ln 3/2 tube then the parameters for its associated 2-generator subgroup(s) (G, f, w) must be in one of the sub-boxes X_{0}, X_{1}, …, X_{6} listed in that proposition. Nonetheless—as we shall see in this Chapter and the next— such manifolds have non-coalescable insulator families about their shortest geodesics. However, they might not be Dirichlet insulator families.

In this Chapter, we describe a new insulator family {κ_{ij}} called the Corona insulator, and we describe a condition sufficient for this family to be non-coalescable—a condition which is weaker than the tuberadius(δ) > ln(3)/2 sufficient condition for the Dirichlet insulator family.

The reason Dirichlet insulator families for geodesics with solid tubes of radius greater than ln 3/2 are non-coalescable is that the amount of visual angle taken up by the various insulators is less than 120 degrees, and thus there is no chance for tri-linking to occur. The visual angle (measured at one axis) for a member of the Dirichlet insulator family associated to two axes depends only on the real distance between the two axes.

In contrast, the visual angle for a member of the Corona insulator family associated to two axes depends on the (complex) distance between the two axes. We now give this function, C, and name it the Corona function. After that we give a precise definition of the visual angle function, and prove that the Corona function is the proper visual angle function for the Corona insulator family.

Definition 2.1: Let C : (0, ∞) × S^{1} → R be defined by

C(u, v) = |Im(Arccosh(1 − \frac{4}{1 ± cosh(u + iv)}))|

where ± is positive for −π/2 ≤ v ≤ π/2 and negative otherwise.

In the following definition, it is helpful to imagine the geodesic σ as being the z−axis in the upper-half-space model of H^{3}.

Definition 2.2: If σ ⊂ H^{3} is a geodesic, then S_{∞}^{2}−∂σ is parametrized by S^{1}×R (these are sometimes called Steiner circles) where each x×R lies in the ideal boundary of a hyperbolic halfplane bounded by σ, two such lines x × R, y × R are at distance θ in the S^{1} factor if they meet at ∂σ at angle θ. If R ⊂ S^{2} − ∂σ, then define visualangle_{σ}(R) = θ ∈ [0, 2π], where θ = inf{θ_{2} − θ_{1} mod 2π | R ⊂ [θ_{1}, θ_{2}] × R}. The possible choice of 0 or 2π is made in the obvious manner.

Proposition 2.3: Let δ_{i}, δ_{j} be disjoint oriented geodesics in H^{3}. Then there exists a smooth simple closed curve κ_{ij} in S_{∞}^{2} separating ∂δ_{i} from ∂δ_{j} such that for k ∈ {i, j}, visualangle_{δ_{k}}(κ_{ij}) = C(distance(δ_{i}, δ_{j})).

Proof: Let P be the orthocurve from δ_{i} to δ_{j}. Consider the half-plane with boundary δ_{i} determined by δ_{i} and P, and the half-plane with boundary δ_{j} determined by δ_{j} and P. Allow these half-planes to expand into solid angles at the same rate. (A solid angle is a closed set in B^{3} = H^{3} ∪ S_{∞}^{2} bounded by two hyperboic halfplanes which meet along a common geodesic.) At first, the four half-planes that bound these solid angles intersect in H^{3}, but at some angle θ these half-planes intersect only at infinity (that is, in S_{∞}^{2}). By reasons of symmetry they intersect in two or four points (four points of intersection occur when Im(distance(δ_{i}, δ_{j})) is π/2 or 3π/2).

Let S_{i}, S_{j} be the solid angles which exist at angle θ. Let T_{k} = S_{k} ∩ S_{∞}^{2} for k ∈ {i, j}. Let κ_{ij} be a simple closed curve in T_{i} ∩ T_{j} which separates ∂δ_{i} from ∂δ_{j}. By construction, for k ∈ {i, j} visualangle_{δ_{k}}(κ_{ij}) = θ. See Figure 2.2.

To complete the proof of the Proposition, we now show that θ = C(distance(δ_{i}, δ_{j})). To do this, we use hyperbolic trigonometry on a degenerate right-angled hexagon in H^{3}. Following [F], a degenerate right-angled hexagon is a 5-tuple of oriented geodesics S_{1}, ⋯, S_{5} in H^{3} such that S_{i} is orthogonal to S_{i+1} and S_{1} and S_{5} limit at a common point S_{0} at infinity. These oriented geodesics give rise to complex numbers σ_{0}, σ_{2}, σ_{3}, σ_{4}. σ_{0} = 0 if the axes S_{1} and S_{5} either both point into S_{0} or both point out of S_{0}. Otherwise σ_{0} = πi. For k ∈ {2, 3, 4} σ_{k} = e if an e-translation of the oriented geodesic S_{k} takes the oriented geodesic S_{k−1} to the oriented geodesic S_{k+1}. By [F; pg. 83] we have the following Hyperbolic Law of Cosines.

cosh(σ_{0}) = cosh(σ_{2}) cosh(σ_{4}) + sinh(σ_{2}) sinh(σ_{4}) cosh(σ_{3}).

We work in the upper-half-space model of hyperbolic 3-space, and normalize so that the ortholine from δ_{j} to δ_{i} is B (thus δ_{i} intersects B above δ_{j}), while the oriented axis δ_{i} is C. B will be S_{3}, while the oriented geodesics δ_{i} and δ_{j} will be S_{2} and S_{4}, respectively.

Of course, u + iv = distance(δ_{i}, δ_{j}). If −π/2 ≤ v ≤ 0 then the intersection points at infinity occur in the second quadrant and the fourth quadrant (see Figure 2.3a). For convenience, we work with the point in the second quadrant and send (unique) perpendiculars from it to the geodesics δ_{i} and δ_{j}. The perpendicular to δ_{i} will be oriented towards δ_{i} and then denoted S_{1}, while the perpendicular to δ_{j} will be oriented away from δ_{j} and then denoted S_{5}. The intersection point at infinity (in the second quadrant) is S_{0}.

This is the proper set-up for applying the (degenerate) Hyperbolic Law of Cosines (see Figure 2.3b). Note that σ_{3} = −(u + iv), and σ_{0} = iπ. By symmetry σ_{2} = σ_{4} = (α + iβ)/2 where (α + iβ)/2 is distance(S_{1}, S_{3}). Plugging into the Law of Cosines, using a half-angle formula (cosh(2z) = 2 cosh^{2}(z) − 1 = 2 sinh^{2}(z) + 1), solving for cosh(α + iβ), and taking the Arccosh, we get the desired result. Note that the visual angle in this set-up is −β, thus necessitating taking the absolute value.

When 0 ≤ v ≤ π/2 our 2 intersection points occur in the first and third quadrants, and we carry out the same procedure. This time S_{2} and S_{4} are traversed in the direction opposite to their orientations (the attendant changes in sign drop out though). In this case, the visual angle is β.

The cases −π ≤ v ≤ −π/2 and π/2 ≤ v ≤ π reduce to the previous cases after adding or subtracting π. The formula in Definition 2.1 is then obtained after noting that cosh(z ± iπ) = − cosh(z).

Definition 2.4: Let δ be a simple closed geodesic in the closed orientable hyperbolic 3-manifold N. Let {δ_{i}}_{i≥0} be the lifts of δ to H^{3}. For each π_{1}(N)-orbit of unordered pairs (δ_{i}, δ_{j}) choose a representative where i = 0. If Redistance(δ_{0}, δ_{i}) ≤ ln(3)/2, then let κ_{0j} be a smooth simple closed curve in S^{2} separating ∂δ_{0} from ∂δ_{j} such that for k ∈ {0, j}, visualangle_{δ_{k}}(κ_{0j}) = C(distance(δ_{0}, δ_{j})). If Redistance(δ_{0}, δ_{i}) > ln(3)/2, then let κ_{0j} be the Dirichlet insulater, i.e. the boundary of the geodesic plane orthogonally bisecting the orthocurve between δ_{0}, δ_{j}.

In either case, extend the collection π_{1}(N)-equivariantly to a family {κ_{ij}} defined for all i, j. This is the Corona family for δ.

Lemma 2.5: The Corona family {κ_{ij}} is i) an insulator family for δ ii) noncoalescable if max{C(δ_{0}, δ_{j}) | j > 0} < 2π/3.

Proof: We check that {κ_{ij}} satisfies the various conditions of Definitions 0.4-0.5 of [G].

i) By construction, κ_{ij} separates ∂δ_{i} from ∂δ_{j} and {κ_{ij}} is π_{1}(N)-equivariant. Because for k ∈ {i, j}, δ_{k} − visualangle(κ_{ij}) < π, {κ_{ij}} satisfies the convexity condition.

Modulo the natural action of π_{1}(N) on κ_{ij}, there are only finitely many insulators κ_{ij} which are not Dirichlet insulators. Therefore, for fixed i, there exist only finitely many κ_{ij} such that diam(κ_{ij}) > ϵ. This establishes local finiteness.

ii) No trilinking follows immediately from ii).

Definition 2.6: If δ is a simple closed geodesic in the hyperbolic 3-manifold N, define maxcorona(δ) = max{C(δ_{0}, δ_{j}) | j > 0}

Remark 2.7: a) It seems possible that the Dirichlet insulator family associated to the geodesic δ ∈ N may be non-coalescable, while the Corona insulator family is coalescable and conversely.

b) If tuberadius(δ) > ln(3)/2, then both the Dirichlet insulator and Corona insulator families coincide and by Lemma 5.9 of [G] they are non-coalescable.

Proposition 2.8: Let δ be a shortest geodesic in the closed orientable hyperbolic 3manifold N. Then either the Corona insulator family is noncoalescable or there exists a 2-generator subgroup G of π_{1}(N) with generators f, w such that the parameter associated to {G, f, w} lies in the sub-box X_{0} = X_{0a} ∪ X_{0b} ⊂ W.

Proof: Let δ be a shortest geodesic in N, a closed orientable hyperbolic 3-manifold. By Corollary 1.29 and Lemma 2.5 either δ has a non-coalescable insulator family or length(δ) lies in L(X_{k}) for some k ∈ {0, 1, …, 6} and maxcorona(δ) ≥ 2π/3. Let G be a 2-parameter subgroup of π_{1}(N) generated by f and g, where f corresponds to δ and has axis B and g maximizes C(g(B), B). We will show that if C(g(B), B) ≥ 2π/3, then the parameter associated to {G, f, g} lies in the sub-box X_{0}.

In fact we will show that if {G, f, g} is any torsion-free subgroup of Isom(H^{3}) where f is a length-minimizing loxodromic element with axis B and g maximizes C(g(B), B) where C(g(B), B) ≥ 2π/3, then the parameter β = (L_{β}, D_{β}, R_{β}) ∈ exp^{−1}(X_{0}).

It follows as in the first paragraph that L_{β} ∈ L(X_{k}) for some k ∈ {0, 1, 2, 3, 4, 5, 6}. Also D_{β} is subject to nontrivial constraint. For example if L_{β} ∈ L(X_{1}), then D_{β} must lie in the decorated region of Figure 2.4, because Redistance(g(B), B) ≥ min_{d}(X_{k}) > 1.059 where min_{d}(X_{k}) is the minimal d value in X_{k}. In fact the disjointness of the L(X_{k})’s implies that if β ∈ S ∩ X_{k}, then tuberadius(δ) ≥ min_{d}(X_{k})/2, where δ corresponds to the element f. Finally C(g(B), B) ≥ 2π/3 implies that D_{β} cannot lie in the decorated region of Figure 2.4.

Our proof is now similar to the proof of Proposition 1.28. We partition the initial box W into sub-boxes W_{i} and eliminate W_{i} if any of the following conditions hold (for clarity, the conditions have been translated into “pre-exponentiated” form).

a) There exists no β ∈ W_{i} such that length(f_{β}) ∈ L(X_{k}).

b) W_{i} has some L values in L(X_{k}) but there exists no β ∈ W_{i} such that distance (w_{β}(B), B) ∈ decorated region for that k.

c) There exists a killerword h in f, w, f^{−1}, w^{−1}, such that Relength(h_{β}) < Relength(f_{β}) and h_{β} ≠ id for all β ∈ W_{i}.

d) There exists a killer word h in f, w, f^{−1}, w^{−1} such that

C(distance(h_{β}(B), B)) > C(distance(w_{β}(B), B))

and h_{β}(B) ≠ B for all β ∈ W_{i}.

We have two files that contain the decomposition of W into sub-boxes and associated conditions/(killer words). The program fudging checks that these files do indeed eliminate all of W − X_{0}. Fudging analyzes the cases k = 1, …, 6 all at once.

Remarks 2.9: i) Note that in practice the proof of Proposition 2.8 requires working in a considerably smaller parameter space than that of Proposition 1.28. Condition a) implies that the parameter space is “(2 + ϵ)-complex dimensional” and condition b) implies that one of these parameters is greatly constrained. This suggests why it took so much longer to come up with the partition and the associated killer words for Proposition 1.28. In fact, it took roughly 1500 CPU days to find the partition and the associated killer words for Proposition 1.28, versus roughly 2 CPU days for Proposition 2.8. Here, the term “CPU day” refers to 24 hours of running an SGI Indigo 2 workstation with an R4400 chip, and the estimate of 1500 CPU days refers to 15 to 20 such machines running 80 to 90 percent of the time for 3 to 4 months.

ii) We took pains to make fudging as similar to verify as we could, thereby lessening the amount of analysis needed to show the veracity of fudging. Appendix 2 contains those sections of fudging that differ from corresponding sections of verify.

iii) When working with exponentiated co-ordinates (that is, in W rather than P) the Corona function changes as follows. Let X = exp(α + iβ) and U = exp(u + iv), then the Corona function formula

cosh(α + iβ) = 1 − \frac{4}{1 + cosh(u + iv)}

becomes

\frac{X + X^{−1}}{2} = 1 − \frac{4}{1 + (U + U^{−1})/2}

It is a pleasant exercise to solve this, and we find that

X = \frac{(U^{2} − 6U + 1) ± 4(U − 1)\sqrt{−U}}{(U + 1)^{2}}

the two answers so gotten are reciprocals, which means their associated arguments are opposites. In fudging, the exponentiated version of the Corona function is the function horizon(ortho), which takes in U =ortho and computes the associated X value. β, the argument of X, is implicitly gotten in the function larger-angle.

iv) It is possible that by working purely in the context of the Corona function, rather than first working with Redistance and attempting to prove Proposition 1.28, the computer proof can be simplified. We started this project with the naive idea that perhaps Vol3 was the only manifold whose shortest geodesic did not have a ln(3)/2 tube. The remarkable fact that this naive idea is almost correct accounts for the fact that a proof of Theorem 0.2 can be obtained with only the mild extra effort detailed in this chapter and the next.

For 0 ≤ v ≤ π/2 C(u, v) = β where β satisfies

cosh(α + iβ) = 1 − \frac{4}{1 + cosh(u + iv)}.

For −π/2 ≤ v ≤ 0 C(u, v) = −β where β satisfies

cosh(α + iβ) = 1 − \frac{4}{1 + cosh(u + iv)}.

For π/2 ≤ v ≤ π C(u, v) = −β where β satisfies

cosh(α + iβ) = 1 − \frac{4}{1 + cosh(u + i(v − π))}.

For −π ≤ v ≤ −π/2 C(u, v) = β where β satisfies

cosh(α + iβ) = 1 − \frac{4}{1 + cosh(u + i(v + π))}.

In all of these cases, we normalize the sign of β by requiring that α be positive.

Lemma 2.10: i) if h = wF wfwfW fwf then Relength(h_{α}) < Relength(f_{α}) for all parameters α in exp^{−1}(X_{0})

ii) if h_{2} = wF wfwwfwF w then Relength(h_{α}) < Relength(f_{α}) for all parameters α in exp^{−1}(X_{0})

iii) |R| < |L/2| throughout exp^{−1}(X_{0}).

Proof: This easy calculation was carried out by verify.

Chapter 3: Vol3

The two main results of this chapter are

Proposition 3.1: If N is a closed orientable hyperbolic 3-manifold, then either N is Vol3, the third smallest known closed orientable hyperbolic 3-manifold, or maxcorona(δ) < 2π/3 for δ a shortest geodesic in N.

Proposition 3.2: Any shortest geodesic in Vol3 satisfies the insulator condition.

Remark 3.3: Vol3 is the third smallest known closed orientable hyperbolic 3-manifold. Topologically Vol3 is (3,1) surgery on manifold m007 in the census of cusped hyperbolic 3-manifolds (see [W]). It is also (-3,2) (-6,1) surgery on the “left-handed Whitehead link”, link 5_{2}^{2} in the standard knot tables. Snappea gives an experimental proof that Vol3 is hyperbolic and that its volume is that of the regular ideal 3-simplex. A rigorous proof can be found in [JR]. Previously, Hodgson-Weeks [HW1] had found an exact Dirichlet domain for Vol3, that is, the face pairings were expressible as explicit matrices with coefficients in a finite extension F of Q and they obtained equations in F for the various faces. See Remark 3.14.

Remarks 3.4: i) Idea of Proof of Proposition 3.1: If N has maxcorona(δ) ≥ 2π/3, then it must have an (L, D, R) parameter in the region R = exp^{−1}(X_{0}), (X_{0} is defined in Proposition 1.28). A geometric argument (Lemma 3.7) which utilizes Lemmas 3.5 and 3.6 shows that R = 0 and an algebraic argument (Lemmas 3.8, 3.9, 3.11, 3.12) shows that L = D = ω, where exp(ω) is a root of the polynomial 1 + 2d + 6d^{2} + 2d^{3} + d^{4}. This implies ([HW1] or [JR]) that g = π_{1}(Vol3) and hence N is covered by Vol3. By [JR], N = Vol3.

ii) The proof of Proposition 3.2 will be somewhat similar to the proofs of Propositions 1.28, 2.8.

Lemma 3.5: Let R = exp^{−1}(X_{0}) If α = (L, D, R) = (l + it, d + ib, r + ia) ∈ R ∩ T , then f_{α}, w_{α} satisfy the relations

i) wF wfwfW fwf

ii) wF wfwwfwF w

Proof: In i), ii) above and what follows below we supress the subscripts α. Also W (resp. F) denotes w^{−1} (resp. f^{−1}). because i), ii) are cyclic permutations of the quasirelators r_{2}, r_{1} corresponding to the X_{0} sub-box of Proposition 1.28, it follows that if h = wF wfwfW fwf or wF wfwwfwF w, then Relength(h) < Relength(f) throughout R. Since α ∈ T , f is a shortest element and so h = id.

Lemma 3.6: The following substitutions give rise to three sets of new relators. a) In i), ii) replace f by w and replace w by f.

b) In i), ii) replace f by F.

c) In i), ii) replace w by W.

Proof: Note that replacing f by w necessitates replacing F by W, and so on.

a) First, a cyclic permutation of relator i) gives relator i) with f replaced by w and w replaced by f. Second, one readily obtains the relator fW fwffwfW f from i), ii), because fW fwf = (wF wfw)^{−1} = wfwF w = (fwfW f)^{−1} where the first and third equalities follow from i) and the second from ii).

b) Again it is routine to obtain b) from i), ii).

c) Conclusion c) follows from a) and b).

Lemma 3.7: If (L, D, R) ∈ R ∩ T , then R = 0.

Proof: With respect to the parameter (L, D, R) let G be the group generated by f, w. Figure 3.1 shows a schematic picture of geodesics B, W (B), w(B), f(w(B)), f(W (B)). Also, it shows the images of the orthocurve O from W (B) to B after translation by w, f and fw. Finally, it shows the orthocurves O_{1} from fW (B) to W (B) and O_{2} from w(B) to fw(B). Note that Figure 3.1 displays the situation where Re(R) > 0. It is also apriori possible that O_{2} might intersect w(B) on the positive side of w(O). There are other similar possible inaccuracies.

σ_{1} = fwffw ∈ G sends geodesic W (B) to fw(B) and σ_{2} = wF F wF ∈ G sends the geodesic fW (B) to w(B). Now σ_{2}^{−1}σ_{1} = fW ffW fwffw is a relator of G, since it is a cyclic permutation of relator ii) with f replaced by w and w replaced by f. Thus σ_{1} = σ_{2} and hence σ_{1}(O_{1}) = O_{2}.

As in Fenchel [F] a right angled hexagon consists of a cyclically ordered 6-tuple of oriented geodesics λ_{1}, ⋯, λ_{6} in H^{3} such that λ_{i} intersects λ_{i+1} (mod 6) orthogonally.

Each “edge” of the hexagon is labelled by the complex number e_{i} where one obtains λ_{i+1} from λ_{i−1} by e_{i} translation of H^{3} along the oriented geodesic λ_{i}.

(3.1) The effect of reversing the orientation of λ_{i} is to change e_{i} to −e_{i}, e_{i+1} to e_{i+1}+πi, and e_{i−1} to e_{i−1} + πi.

Figure 3.1 gives rise to the two right-angled hexagons drawn in Figure 3.2. (Figure 3.2a may be inaccurate for the following reason. It is not clear whether the head of O_{1} should be placed in front of the tail of O or behind the tail of O. A similar statement holds for the tail of O_{1} and for Figure 3.2b.) Assume that in Figure 3.2a, λ_{1} corresponds to B and the edges are cyclically ordered counterclockwise. Then e_{6} = D, e_{1} = L, e_{2} = −D. We now show that if e_{5} has value c, then e_{3} has value c + πi. Observe that there is an order-2 rotation τ of H^{3} about an axis orthogonal to B which reverses the orientation on B and takes the oriented orthocurve O to the oriented orthocurve f(O). Since distance(W (B), B) = distance(fW (B), B) it follows that τ(fW (B)) = −W (B) and τ(W (B)) = −fW (B) where the - sign indicates that the orientation has been reversed. This in turn imples that τ(O_{1}) = −O_{1} and therefore using (3.1) that e_{3} = e_{5} + πi.

Let ϕ be the isometry of H^{3} which is an r + i(π + a) translation of B. Thus ϕ(B) = B, ϕ(O) = −w(O), ϕ(f(O)) = −fw(O). This implies that ϕ(W (B)) = w(B) and ϕ(fW (B)) = fw(B) which in turn implies that ϕ(O_{1}) = −O_{2}. If the hexagon of Figure 3.2b with edges λ′_{1}, ⋯, λ′_{6} is counterclockwise cyclically oriented so that λ′_{1} denotes the oriented geodesic B, then again using (3.1) it follows that e′_{5} = c and e′_{3} = c + πi.

Via elements of G, we translate each of W (B), fW (B), w(B), fw(B) to B and after translation we obtain from Figure 3.2 the various distance relations schematically indicated on Figure 3.3. Here O_{i}^{∗} is G translation of O_{i} with an endpoint on B. Two such translates appear in Figure 3.3, one where O_{i}^{∗} points into B and one where O_{i}^{∗} points out. Call the former (resp. latter) the pointing in (resp. out) O_{i}^{∗}. Actually Figure 3.3 includes 3 more relations. Because the oriented O_{1} is a G−translate of the oriented O_{2} and f is a primitive element of G which fixes B, it follows that

distance((pointing in O_{1}^{∗}), (pointing in O_{2}^{∗})) = 0 (mod L)

and

distance((pointing out O_{1}^{∗}), (pointing out O_{2}^{∗})) = 0 (mod L).

Finally distance(w(O), O) = R.

We therefore obtain the following two equations

(3.2) c − R + L + c + πi = 0 (mod L) c − L + R + c + πi = 0 (mod L)

and hence

(3.3) 2R = 0 (mod L) 4c = 0 (mod L).

Using the L′ and R′ ranges for X_{0} provided in Proposition 1.28, it is easy to compute that for each element of R = exp^{−1}(X_{0}), |Re(R)| < |Re(L)/2|. It then follows that R = 0 for (L, D, R) ∈ R ∩ T .

Lemma 3.8: If (L, D, R) ∈ R ∩ T , then L = D.

Proof: We will now use the exponential coordinates l = exp(L), d = exp(D). These l, d should not be confused with the l + it, d + ib used above. In the following calculations Mathematica [Math] was used to perform matrix multiplication of 2×2 matrices with coeficients rational functions in the variables \sqrt{l}, \sqrt{d}. We will follow Mathematica’s notation (for example, in Mathematica’s notation the 2 × 2 matrix (a_{ij}) is {{a_{11}, a_{12}}, {a_{21}, a_{22}}}). In particular, plugging in R = 0 in Lemma 1.24 we get the following matrix representations of f, F, w, W. Because the R term drops out, we can express the matrices of w and W as functions of d alone.

f[l ] = {{Sqrt[l], 0}, {0, 1/Sqrt[l]}}

F [l ] = {{1/Sqrt[l], 0}, {0, Sqrt[l]}}
w[d ] = {{1/2(Sqrt[d] + 1/Sqrt[d]), 1/2(Sqrt[d] − 1/Sqrt[d])},
{1/2(Sqrt[d] − 1/Sqrt[d]), 1/2(Sqrt[d] + 1/Sqrt[d])}}

W [d ] = {{1/2(Sqrt[d] + 1/Sqrt[d]), 1/2(−Sqrt[d] + 1/Sqrt[d])},

{1/2(−Sqrt[d] + 1/Sqrt[d]), 1/2(Sqrt[d] + 1/Sqrt[d])}}

Let Y be the relator F.w.f.w.f.W.f.w.f.w, which is a cyclic permutation of relator i) of Lemma 3.4. Multiplying this product of 10 matrices we obtain the following matrix for Y which we know is I.

Y [l , d ] = {{((1 + d) ∗ (1 − 2 ∗ d^{2} + d^{4} + 8 ∗ d ∗ l − 16 ∗ d^{2} ∗ l
+8 ∗ d^{3} ∗ l − 2 ∗ l^{2} + 4 ∗ d ∗ l^{2} − 4 ∗ d^{2} ∗ l^{2} + 4 ∗ d^{3} ∗ l^{2}−
2 ∗ d^{4} ∗ l^{2} + l^{4} + 4 ∗ d ∗ l^{4} + 6 ∗ d^{2} ∗ l^{4} + 4 ∗ d^{3} ∗ l^{4}
+d^{4} ∗ l^{4}))/(32 ∗ d^{(5/2)} ∗ l^{(3/2)}),

((−1 + d) ∗ (1 + 4 ∗ d + 6 ∗ d^{2} + 4 ∗ d^{3} + d^{4} + 4 ∗ d ∗ l+
8 ∗ d^{2} ∗ l + 4 ∗ d^{3} ∗ l − 2 ∗ l^{2} − 12 ∗ d^{2} ∗ l^{2} − 2 ∗ d^{4} ∗ l^{2}+
4 ∗ d ∗ l^{3} + 8 ∗ d^{2} ∗ l^{3} + 4 ∗ d^{3} ∗ l^{3} + l^{4} + 4 ∗ d ∗ l^{4}+
6 ∗ d^{2} ∗ l^{4} + 4 ∗ d^{3} ∗ l^{4} + d^{4} ∗ l^{4}))/(32 ∗ d^{(5/2)} ∗ l^{(3/2)})},

{((−1 + d) ∗ (1 + 4 ∗ d + 6 ∗ d^{2} + 4 ∗ d^{3} + d^{4} + 4 ∗ d ∗ l+
8 ∗ d^{2} ∗ l + 4 ∗ d^{3} ∗ l − 2 ∗ l^{2} − 12 ∗ d^{2} ∗ l^{2} − 2 ∗ d^{4} ∗ l^{2}+
4 ∗ d ∗ l^{3} + 8 ∗ d^{2} ∗ l^{3} + 4 ∗ d^{3} ∗ l^{3} + l^{4} + 4 ∗ d ∗ l^{4}+
6 ∗ d^{2} ∗ l^{4} + 4 ∗ d^{3} ∗ l^{4} + d^{4} ∗ l^{4}))/(32 ∗ d^{(5/2)} ∗ l^{(3/2)}),

((1 + d) ∗ (1 + 4 ∗ d + 6 ∗ d^{2} + 4 ∗ d^{3} + d^{4} − 2 ∗ l^{2} + 4 ∗ d ∗ l^{2}−
4 ∗ d^{2} ∗ l^{2} + 4 ∗ d^{3} ∗ l^{2} − 2 ∗ d^{4} ∗ l^{2} + 8 ∗ d ∗ l^{3}−
16 ∗ d^{2} ∗ l^{3} + 8 ∗ d^{3} ∗ l^{3} + l^{4} − 2 ∗ d^{2} ∗ l^{4} + d^{4} ∗ l^{4}))
/(32 ∗ d^{(5/2)} ∗ l^{(3/2)})}}

Since G is generated by f, an L translation along B, and w, a D translation along C, it follows from Lemma 3.6 that the relation Y = I holds with l and d switched. Thus 0 = Y_{12}, and 0 = Y_{12} (with l, d switched) which implies that 0 = (1 + 4 ∗ d + 6 ∗ d^{2} + 4 ∗ d^{3} + d^{4} + 4 ∗ d ∗ l + 8 ∗ d^{2} ∗ l+

4 ∗ d^{3} ∗ l − 2 ∗ l^{2} − 12 ∗ d^{2} ∗ l^{2} − 2 ∗ d^{4} ∗ l^{2}+
4 ∗ d ∗ l^{3} + 8 ∗ d^{2} ∗ l^{3} + 4 ∗ d^{3} ∗ l^{3} + l^{4} + 4 ∗ d ∗ l^{4}+
6 ∗ d^{2} ∗ l^{4} + 4 ∗ d^{3} ∗ l^{4} + d^{4} ∗ l^{4})−

(1 + 4 ∗ l + 6 ∗ l^{2} + 4 ∗ l^{3} + l^{4} + 4 ∗ l ∗ d + 8 ∗ l^{2} ∗ d+

4 ∗ l^{3} ∗ d − 2 ∗ d^{2} − 12 ∗ l^{2} ∗ d^{2} − 2 ∗ l^{4} ∗ d^{2}+
4 ∗ l ∗ d^{3} + 8 ∗ l^{2} ∗ d^{3} + 4 ∗ l^{3} ∗ d^{3} + d^{4} + 4 ∗ l ∗ d^{4}+
6 ∗ l^{2} ∗ d^{4} + 4 ∗ l^{3} ∗ d^{4} + l^{4} ∗ d^{4}) =

4 ∗ (1 + d)^{2} ∗ (1 + l)^{2} ∗ (−d + l) ∗ (−1 + d ∗ l).

This implies that d = l and hence D = L or we obtain one of the following solutions which contradicts the condition Re(D) > 0. The solution d = −1 implies D = ln(d) = ln(−1) = πi. The solution d = 1 implies D = 0. The solution d ∗ l = 1 implies that d = 1/l and hence D = ln(d) = ln(1/l) = − ln(l) = −L and hence Re(D) < 0.

Lemma 3.9: If (L, D, R) ∈ R ∩ T , then d = exp(D) is a root of the polynomial

1 + 2 ∗ d + 6 ∗ d^{2} + 2 ∗ d^{3} + d^{4}.

Proof: The equation Y_{12} = 0 yields

0 = 1 + 4 ∗ d + 6 ∗ d^{2} + 4 ∗ d^{3} + d^{4} + 4 ∗ d ∗ l + 8 ∗ d^{2} ∗ l + 4 ∗ d^{3} ∗ l − 2 ∗ l^{2}− 12 ∗ d^{2} ∗ l^{2} − 2 ∗ d^{4} ∗ l^{2} + 4 ∗ d ∗ l^{3} + 8 ∗ d^{2} ∗ l^{3} + 4 ∗ d^{3} ∗ l^{3} + l^{4} + 4 ∗ d ∗ l^{4}+

6 ∗ d^{2} ∗ l^{4} + 4 ∗ d^{3} ∗ l^{4} + d^{4} ∗ l^{4}.

Setting l = d we obtain

0 = 1 + 4 ∗ d + 8 ∗ d^{2} + 12 ∗ d^{3} − 2 ∗ d^{4} + 12 ∗ d^{5} + 8 ∗ d^{6} + 4 ∗ d^{7} + d^{8} =

(1 + 2 ∗ d − 2 ∗ d^{2} + 2 ∗ d^{3} + d^{4}) ∗ (1 + 2 ∗ d + 6 ∗ d^{2} + 2 ∗ d^{3} + d^{4}).

On the other hand setting l = d in the equation Y_{11} = 1 we obtain

32d^{5} = (1 + d)(1 + 4 ∗ d^{2} − 12 ∗ d^{3} + 6 ∗ d^{4} + 8 ∗ d^{5} + 4 ∗ d^{6} + 4 ∗ d^{7} + d^{8})]

and so

0 = (−1 + d) ∗ (1 + 2 ∗ d + 6 ∗ d^{2} + 2 ∗ d^{3} + d^{4}) ∗ (−1 + 4 ∗ d^{3} + d^{4})

The only common solutions to these equations are the roots of the equation

(3.4) (1 + 2 ∗ d + 6 ∗ d^{2} + 2 ∗ d^{3} + d^{4})

Remark 3.10: The two facts Y = I, and l, d can be switched in Y follow from relator i) of Lemma 3.4 and R = 0. Relator ii) was used in the proof that R = 0.

Lemma 3.11: The roots of 1 + 2 ∗ d + 6 ∗ d^{2} + 2 ∗ d^{3} + d^{4} are

(−1 + i ∗ \sqrt{3})/2 − (−6 − 2 ∗ i ∗ \sqrt{3})^{(1/2)}/2
(−1 + i ∗ \sqrt{3})/2 + (−6 − 2 ∗ i ∗ \sqrt{3})^{(1/2)}/2
(−1 − i ∗ \sqrt{3})/2 − (−6 + 2 ∗ i ∗ \sqrt{3})^{(1/2)}/2
(−1 − i ∗ \sqrt{3})/2 + (−6 + 2 ∗ i ∗ \sqrt{3})^{(1/2)}/2

Remark 3.12: Note that if x is a root of 1 + 2 ∗ d + 6 ∗ d^{2} + 2 ∗ d^{3} + d^{4}, then so are x̄, 1/x and 1/x̄.

Lemma 3.13: If (L, D, R) ∈ R ∩ T , then

D = L = ln((−1 + i ∗ \sqrt{3})/2 − (−6 − 2 ∗ i ∗ \sqrt{3})^{(1/2)}/2)
= ω ≈ 0.83144294552931 − 1.945530759503636 ∗ i.

Proof: The other 3 solutions are −L, Re(L) − Im(L), −Re(L) + Im(L) and lie outside R. The above solution lies in R.

Remark 3.14: In our language, Hodgson and Weeks [HW1] knew that π_{1}(Vol3) was generated by f, w with D = L = ω and R = 0. Also that the various solutions of (3.4) corresponded to symmetries of Vol3.

Corollary 3.15: Vol3 is the unique hyperbolic 3-manifold with ¿associated parameter values in S ∩ X_{0}.

Proof of Proposition 3.1: By Proposition 2.8 if maxcorona(δ) ≥ ln(3)/2, then the parameter for a 2-generator subgroup G of π_{1}(N) lies in S ∩ X_{0}. Since G = π_{1}(Vol3), N is covered by Vol3. By Reid (see [JR]) Vol3 only covers Vol3. Therefore N =Vol3.

Proof Proposition 3.2: We show that the Dirichlet insulator associated to a shortest geodesic δ in N satisfies the insulator condition if C(O(2)) < 113.16 degrees. Here O(2) = distance(B, second closest lift of δ) and O(1) = ω corresponds to the closest lift. This actually requires that we be a bit more precise, so we insert the following definition.

Definition 3.16: Let δ be a geodesic in the hyperbolic 3-manifold N and {δ_{i}}_{i≥0} be the preimages of δ in H^{3}. Define an equivalence relation on {δ_{i}}_{i≥1} by saying that δ_{i} = δ_{j} if either

i) there exists a g ∈ π_{1}(N) such that g(δ_{0}) = δ_{0} and g(δ_{i}) = δ_{j}

or ii) there exists g ∈ π_{1}(N) such that g(δ_{i}) = δ_{0} and g(δ_{0}) = δ_{j}. Call an equivalence class an orthoequivalence class. Consider the collection O of com-

plex numbers {distance(δ_{0}, δ_{i}) | i > 0 and only one δ_{i} is represented in each equivalence class } Now order O to obtain the ortholength spectrum of δ, {O(1), O(2), ⋯} where i ≤ j implies Re(O(i)) ≤ Re(O(j)).

The based ortholength spectrum consists of all distinct pairs of complex numbers of the form {(distance(C, ortholine from B to g(B)), distance(B, g(B)) | g ∈ π_{1}(N)}.

The geodesic plane midway between B and w^{−1}(B) intersects the B − C plane in a geodesic E at distance Re(ω)/2 = Re(lengthf)/2 from B. Conjugate π_{1}(N) so that f is still an ω translation of B and so that one endpoint of E is at (1,0) and the other endpoint is at (x, 0), where x > 1. By [Beardon; p. 166 ] x < 23.815. Thus the Dirichlet insulator λ (resp. w(λ) between B, w^{−1}(B) (resp. B, w(B)) is symmetric about the x−axis and lies within the circle passing through (1,0), (23.815,0) (resp. (-1,0), (-23.815, 0)). By [G; Lemma 4.7] this circle takes up a visual angle of less than 133.68 degrees. Now f is the composition of an exp(Re(ω)) homothety centered about the origin and an Im(ω) radian ≈ −111.4707 degree rotation. Because exp(4 ∗ Re(ω)) > 27.82 > 23.815 it follows that the geodesic E is taken “beyond” E by w^{4}. In fact, we see that λ ∩ (f^{n}(λ) ∪ f^{n}w(λ)) = ∅ if |n| ≥ 4. Therefore if there was a trilinking among three insulators associated to the orthoclass of w(B), there would be a tri-linking involoving 3 circles from the collection {f^{n}w(λ), f^{n}(λ) | −3 ≤ n ≤ 0}.

Since S_{∞}^{2} is rotated by at most 111.48 degrees under f^{±1}, and λ takes up less than 133.68 degrees B-visual angle it follows that f^{−1}(λ)∪λ take up less than 133.68+111.48 = 245.06 degrees B−visual angle. Similar arguments show that if λ and one of f^{n}(λ) or f^{m}w(λ) nontrivially intersect, then the union cannot take up more B-visual angle, in fact except for f^{±}(λ), it takes up less. See Figure 3.4 which shows the union of {f^{n}w(λ), f^{n}(λ) | −3 ≤ n ≤ 0}. Therefore, if the union of three such circles was connected, they would take up at most 133.68 + 2(111.48) = 356.64 degrees of B-visual angle and hence would not create a trilinking.

Now suppose that C(O(2)) < 113.16. Thus any insulator associated to a translate of B not in the O(1) class would take less than 113.16 degrees visual angle. There are three cases to consider: trilinking involving no O(1) insulators; trilinking involving exactly one O(1) insulator; trilinking involving exactly two O(1) insulators. The case of no O(1) insulators cannot occur because 3(113.16) < 360. The case of exactly one O(1) insulator cannot occur because B-visual angle(O(1)) + 2(C(O(2)) < 133.68 + 2(113.16) = 360. Finally, the case of exactly two O(1) insulators cannot occur, because the two O(1) insulators would take up at most 245.06 degrees of visual angle (see the above paragraph) and adding to this the fact that C(O(2)) < 113.16 produces less than 360 degrees.

The proof of Proposition 3.2 is now completed by the following

Lemma 3.17: If δ is a shortest geodesic in Vol 3, then C(O(2)) < 113.16.

Proof: Step 1: Re(O(2)) > Re(O(1))

Proof of Step 1. If Re(O(2)) =Re(O(1)), then it follows by Proposition 3.1 that O(2) = O(1) = ω. Furthermore the collection of orthocurves must appear symmetrically on the geodesic B, i.e. if distance(O(2)−ortholine, C) = x+yi, with 0 ≤ x, x minimal, then there is an ortholine at distance n(x+yi) with n ∈ Z along B from C whose corresponding ortholength is ω. Use the fact that if v ∈ π_{1}(Vol3) is the element with distance(v(B), B) = O(2) as above, then the group generated by v, f is conjugate to the group generated by w, f.

If x = 0, and y > 0 is minimal, then y = π/m. Using Fenchel’s law of cosines [F; p. 83 ], it follows that if m = 2, then there exists an ω̄ ortholength thereby contradicting Proposition 3.1. See Figure 3.5. If m > 2, then a similar argument shows that there exists a real ortholength less than Re(ω).

If x > 0 choose m minimal so that mx =Re(ω). By replacing y by y + πi, if necessary, we can assume that m(x + yi) = ω. Therefore an x + iy translation τ along B descends to a Z/m action ϕ on Vol3. Any lift of ϕ^{n} is a conjugate of τ^{n} which is fixed-point free or the identity. This contradicts the fact that Vol3 only covers Vol3.

Step 2: C(O(2)) < 113.16

Proof of Step 2. We obtain this result with computer assistance in a manner similar to the proofs of Propositions 1.28 and 2.8. Our parameter space W is the usual initial box. As before, a parameter gives rise to a group G with generators f, v. (Here we reserve the letter w to denote one of the generators of π_{1}(Vol3).) We consider the parameters U ⊂ W such that f, v generate a group G where f is of minimal length, and maxcorona(δ_{f}) = C(v) ≥ 113.16. If Step 2 was false then U ≠ ∅ for it contains the 2-generator subgroup of π_{1}(Vol3) generated by f, v where distance(v(B), B) = O(2). We now show that U = ∅ as follows.

We partition W into regions W_{i} such that each W_{i} can be eliminated for one of the following reasons.

z) W_{i} = X_{0}.

a) There exists no β ∈ W_{i} such that length(f_{β}) ∈ L(X_{0}). In particular, length(f_{β}) ≠ ω throughout W_{i}.

b) W_{i} has some L values in L(X_{0}) but there exists no β ∈ W_{i} such that the real part of distance(v_{β}(B), B) is greater than the minimum d value for X_{0}. In particular, Re(distance(v_{β}(B), B)) ≤ Re(ω) throughout W_{i}.

c) There exists a killerword h in f, w, f^{−1}, w^{−1}, such that h_{β} ≠ id and Relength(h_{β}) < Relength(f_{β}) for all β ∈ W_{i}.

It turns out that a Corona condition is not needed—c) is sufficient to generate all the killer words we need!

There are files containing the partition of W and the associated conditions/killerwords, and fudging verifies that they indeed work. Fudging actually takes care of the sub-boxes X_{0}, …, X_{6} all at once, and the associated files reflect that fact.

As noted earlier, fudging works with the exponentiated versions of the above conditions.

Here is an experimental “proof” of Lemma 3.17. In [HW2] an algorithm is given to compute, with multiplicities, the length spectrum of a hyperbolic 3-manifold M, given a Dirichlet domain for M. Weeks has observed [Weeks, personal communication] that a very similar argument gives an algorithm to compute the based ortholength spectrum. In fact an analogue to Proposition 1.6.2 [HW2], (with an analogous proof) is the following

Lemma 3.18 (Weeks): Let M be a closed orientable 3-manifold having a Dirichlet domain D with basepoint x and with spine radius r. Let δ be a geodesic of length l + it. To compute all the based ortholengths of real length less than or equal to λ with basing less than or equal to l/2 from some point on δ_{0} (a preimage of δ) it suffices to find all translates gD satisfying ρ(x, gx) ≤ 2r + 2Arccosh(cosh(l/2) cosh(λ/2)).

Proof: As in [HW2] we can assume that ρ(δ_{0}, x) ≤ r. The 0-basing on δ_{0} will be given by the oriented perpendicular P from δ_{0} to x. Figure 3.6 shows that if there is a translate δ_{i} = g(δ_{0}) based at distance ≤ l/2, at real distance ≤ λ from δ_{0}, then ρ(g(x), x) ≤ λ+l+2r. As in [HW2] an application of the hyperbolic cosine law yields the better estimate of the Lemma.

Provided one is given a Dirichlet domain, [HW2] gives an efficient algorithm to find these g’s. Finally to each such g one computes the basing and distance from g(δ_{0}) to δ_{0}.

The collection of ortholengths with basings ≤ l/2 contains at least 2 representatives for each ortholength class, thus the Weeks algorithm can be used to give lower bounds on the various O(i)’s. Snappea computes a Dirichlet domain for Vol3 with spine radius ≤ 0.68. Because l < 0.83145, taking λ = 1.24 we obtain 2r + 2arccosh(cosh(l/2) cosh(λ/2)) < 2.89. This algorithm has been implemented on an undistributed version of Snappea, and provided the following estimates. Note that Re(O(2)) ≥ 1.24 is sufficient to guarantee that C(O(2)) < 113.16 degrees.

O(1) ≈ .83144 − 1.94553I,
O(2) ≈ 1.3170 − πI,
O(3) = O(4) ≈ 1.4197 + 1.0963I,
O(5) ≈ 1.9769 − 1.2995.

These estimates were found using a “tiling” of radius 3.00 > 2.89, which is sufficient for “proving” that for Vol3, Re(O(2)) > 1.24.

Remark 3.19: This experimental proof should be easily rigorizable by implementing Weeks’s algorithm using exact arithmetic.

Chapter 4: Applications

We provide some applications. First, we give a partial answer to Question 1.16. Second a lower bound for the volume of hyperbolic 3-manifolds is produced. Finally, we give a relationship between isotopic closed curves in a hyperbolic 3-manifold and essential links in B^{3}.

Theorem 4.1: If δ is a shortest geodesic in a closed orientable hyperbolic 3-manifold N, then either tuberadius(δ) ≥ 1.059191579962 … /2 or N =Vol3.

Proof: If tuberadius(δ) = d/2 < ln(3)/2, then by Corollary 1.29 ii, d ∈

[0.831426508686 …, 0.831461989726 …] ∪ [1.068029907104 …, 1.068134862048 …]∪

[1.072078514724 …, 1.072622271888 …] ∪ [1.094788113123 …, 1.095007375882 …]∪ [1.094973832380 …, 1.095231885426 …] ∪ [1.059191579962 …, 1.060372139694 …].

If d < 1.059191579962 …, then by Proposition 1.28 the parameter (L, D, R) ∈ P′ associated to N must be in R ∩ T = exp^{−1}(X_{0} ∩ S). It then follows by Corollary 3.15 that N = Vol3.

Conjecture 4.2: If δ is a shortest geodesic in a closed orientable hyperbolic 3-manifold N, then either tuberadius(δ) > ln(3)/2 or N is one of six exceptional manifolds.

Remark 4.3: Vol3 is one of these manifolds. As in Remark 1.32, three others are conjecturally, s479(−3, 1), s778(−3, 1), v2678(2, 1). These correspond to sub-boxes X_{5}, X_{2}, X_{1} respectively.

The conjectured fundamental groups of the six manifolds are < f, w; r_{1}(X_{k}), r_{2}(X_{k}) > for k ∈ 0, …, 6. (The groups for k = 5, 6 are isomorphic). Using [Be] one can get explicit Heegaard genus 2 descriptions of all the conjectured manifolds.

One could prove Conjecture 4.2 by first showing that for each k, T ∩ X_{k} is a point T_{k}. Let M_{k} be the hyperbolic 3-manifold which corresponds to T_{k}. Second show that M_{k} nontrivially covers no 3-manifold. This procedure was carried out in Chapter 3 for the subbox X_{0}.

Remarks 4.4: The previous best lower bound for the volume of hyperbolic 3-manifolds was on the order of 0.001 (see [GM1] and [M2]). Using the results of this paper and the method of [M1] it is easy to improve this to 0.1. However, Gehring and Martin provide an improved tube-volume formula in [GM2] and we use their formula to get a lower bound of 0.16668 …. The Gehring-Martin tube-volume formula for manifolds (as opposed to orbifolds) is

V(t) = \sqrt{3} tanh(t) cosh(2t)Arcsinh^{2}(sinh(t)/ cosh(2t))

where t is the radius of the embedded solid tube. Note that the length of the core geodesic is irrelevant.

Theorem 4.5: \frac{5}{2\sqrt{3}}Arcsinh^{2}(\frac{\sqrt{3}}{5}) = 0.16668 … is a lower bound for the volume of closed hyperbolic 3-manifolds.

Proof: [GM2; Corollary 1.7] applies the tube-volume formula V(t) to tubes of radius at least ln(3)/2 and produces

Vol(N) ≥ V(ln(3)/2) = \frac{5}{2\sqrt{3}}Arcsinh^{2}(\frac{\sqrt{3}}{5}) = 0.16668 …

Corollaries 1.29 and 3.15 imply that if the tube radius of a shortest geodesic in N is less than ln(3)/2, then either N = Vol3 or N contains an embedded open tube of radius d/2, where d ∈ Re(ln(D(X_{k}))), about a geodesic of length l ∈ Re(ln(L(X_{k}))) for some k ∈ 1, …, 6. As in the Theorem 4.1 we compute that l ≥ 1.059536368901 …

In the first case, Vol(N) = Vol(Vol3) = 1.01 …, while in the second case l and d are bounded as follows: l ≥ 1.059536368901 … and d ≥ 1.059191579962 …. Plugging these into the tube-volume formula πl sinh^{2}(d/2) we get Vol(N) ≥ 1.02419 ….

Theorem 4.6: Let k_{1}, k_{2} be simple closed curves in N such that k_{1} is a geodesic. Then k_{1} is isotopic to k_{2} if and only if as B^{3}-links q^{−1}(k_{1}) is equivalent to q^{−1}(k_{2}) where q : H^{3} → N is the universal covering projection.

Proof: Apply Corollary 5.6 of [G]. Recall that an equivalence between B^{3}-links Γ, Δ is a homeomorphism of B^{3} which takes Γ to Δ and fixes S^{2} pointwise.

Remark 4.7: A similar argument extends Theorem 4.6 to homotopy essential links which lift to trivial B^{3}-links. The general case of Conjecture 5.5A of [G] is still open.

Chapter 5: Conditions and Sub-Boxes

As described in Section 1, our goal is to kill off all points in S ⊂ C^{3}, but for computational reasons we will actually work with the box B ⊃ S. We will decompose B into a collection of sub-boxes such that each sub-box has an associated “condition” that will describe how to kill off that entire sub-box. The set-up for describing these sub-boxes will be given in Section 3.

We now list the conditions used to kill off the sub-boxes. There are two types of conditions: the trivial and the interesting. The trivial conditions kill off sub-boxes in W by noting that the sub-box in question misses S. The interesting conditions are where the real work is done, and they require a killer word in f, w, f^{−1}, w^{−1} to work their magic.

To be consistent with the computer program verify we use the following notation. L′ = z_{0} + iz_{3}, D′ = z_{1} + iz_{4}, and R′ = z_{2} + iz_{5}. Here (L′, D′, R′) ∈ W and L′ = exp(L) = exp(l + it), D′ = exp(D) = exp(d + ib), R′ = exp(R) = exp(r + ia).

The Trivial Conditions 5.1:

Condition ‘s’ (short): Tests that all points in the sub-box have |z_{0} +iz_{3}| < 1.10274. This ensures that exp(l) = | exp(L)| = |L′| = |z_{0} + iz_{3}| < 1.10274 < exp(0.0978), and Definition 1.14 tells us that we are outside of S = exp(T)

Condition ‘l’ (long): Tests that all points in the sub-box have |z_{0} + iz_{3}| > 3.63201. This ensures that exp(l) = | exp(L)| = |L′| = |z_{0} + iz_{3}| > 3.63201 > exp(1.2897845) and we are outside of S. Here we have improved S to allow for the value computed in the proof of Proposition 1.13, rather than the cruder value 1.29.

Condition ‘n’ (near): Tests that all points in the sub-box have |z_{1} + iz_{4}| < 1. This ensures that exp(d) = | exp(D)| = |D′| = |z_{1} + iz_{4}| < 1 = exp(0) and we are outside of S. Actually, we used a stronger condition in Definition 1.14 (l/2 ≤ d).

Condition ‘f’ (far): Tests that all points in the sub-box have |z_{1} + iz_{4}| > 3. This ensures that exp(d) = | exp(D)| = |D′| = |z_{1} + iz_{4}| > 3 = exp(ln 3) and we are outside of S.

Condition ‘w’ (whirle big): Tests that all points in the sub-box have |z_{2} + iz_{5}|^{2} > |z_{0} + iz_{3}| This ensures that exp(r) = | exp(R)| = |R′| = |z_{2} + iz_{5}| > \sqrt{|z_{0} + iz_{3}|} = \sqrt{exp(l)} = exp(l/2) and we are outside of S. In the computer program, this test requires a round-off error analysis. As such, the formula in the program is more complicated than expected. See Chapters 7 and 8 for a discussion of round-off error.

Condition ‘W’ (whirle small): Tests that all points in the sub-box have |z_{2}+iz_{5}| < 1. This ensures that exp(r) = | exp(R)| = |R′| = |z_{2} +iz_{5}| < 1 = exp(0) and we are outside of S.

The Interesting Conditions 5.2:

Condition ‘L’: This condition comes equipped with a killer word k in f and w, and tests that all points in the sub-box have | exp(length(k))| < |L′| = | exp(L)|, where length(k) means the length of the isometry determined by k. This, of course, contradicts the fact that L is the length of the shortest geodesic.

It is easy to carry out the test | exp(length(k))| < |L′| because Lemma 1.25a) can be used. Note that in verify the function which computes exp(length) is called length.

Of course, Condition ‘L’ also checks that the isometry corresponding to the word k is not the identity.

Condition ‘O’: This condition comes equipped with a killerword k in f and w, and tests that all points in the sub-box have | exp(distance(k(B), B))| < |D′| = | exp(D)|. This, of course, contradicts the “nearest” condition.

It is easy to carry out the test | exp(distance(k(B), B))| < |D′| because Lemma 1.25b) can be used. Note that in verify the function which computes exp(distance(k(B), B))is called orthodist.

Also, Condition ‘O’ checks that the isometry corresponding to the word k does not take the axis of f to itself. bigskip Condition ‘2’: This is just the ‘L’ condition without the “not-the-identity” check, but with the additional proviso that k is of the form f^{p}w^{q}. This ensures that k is not the identity, because for k to be the identity f and w would have to have the same axis, which contradicts the fact that d can be taken to be greater than or equal to l/4.

Condition ‘conjugate’: There is one other condition that is used to eliminate points in W. Following Definition 1.14 (and Lemma 1.15) we eliminate all boxes with 0 < t ≤ π. Of course, after exponentiating L = l + it, this corresponds to eliminating all boxes with z_{3} > 0. Specifically, we toss all sub-boxes of W whose fourth entry is a 1. This condition does not appear in verify and fudging because it is applied “outside” of these programs, as described at the end of this Chapter.

Construction 5.3: We now give the method for describing the roughly 930 million subboxes that the initial box W is sub-divided into.

All sub-boxes are gotten by sub-division of a previous sub-box along a real hyper-plane mid-way between parallel faces of the sub-box before sub-division. Of course, these midway planes are of the form x_{i} = a constant. We use 0’s and 1’s to describe which half of a subdivided sub-box to take (0 corresponds to lesser x_{i} values). For example, 0 describes the box W ∩{(x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) : x_{0} ≤ 0}, 010 describes the box W ∩{(x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) : x_{0} ≤ 0, x_{1} ≥ 0, x_{2} ≤ 0}, and so on.

In this way, we get a 1-to-1 correspondence between strings and sub-boxes. If s is a string of 0’s and 1’s, then let Z(s) denote the box corresponding to s. The range of values for the i-th coordinate in the sub-box Z(s) is related to the binary fraction 0.s_{i}s_{i+6} … s_{i+6k}. The two sub-boxes gotten from subdividing Z(s) are Z(s0) and Z(s1).

The directions of sub-division cycle among the various coordinate axes: the n-th subdivision is across the (n mod 6)-th axis. The dimensions of the top-level box W were chosen so that sub-division is always done across the longest dimension of the box, and so that all of the sub-boxes are similar. This explains the factor of 2^{(5−i)/6} in Definition 1.22.

To kill a sub-box Z(s), the checker program has two (recursive) options: use a condition (and, if necessary, an associated killer word) to kill Z(s) directly, or first kill Z(s0) and then kill Z(s1).

There is also a third option: don’t kill Z(s), and instead mark s as omitted. Any omitted sub-boxes are checked with another instance of the checker program, unless the sub-box is one of the 7 exceptional sub-boxes (11 before joining abutters).

Thus, a typical output from verify would be

verified000000111101111111 − {0000001111011111110000000111101111111110}

Which means that the sub-box Z(000000111101111111) was killed except for its sub-boxes Z(0000001111011111110) and Z(000000111101111111110). The ouput

verified0000001111011111110 − { }.

and verified000000111101111111110 − { }.

shows that these boxes were subsequently killed as well, and thus the entire sub-box Z(000000111101111111) has been killed.

Instead of immediately working on killing the top-level box, we subdivide in the six co-ordinate directions to get the 64 sub-boxes

Z(000000), Z(000001), Z(000010), Z(000011), …, Z(111111).

We then throw out the ones with fourth co-ordinate equal to 1 (thanks to Definition 1.14 and Lemma 1.15), leaving us with the 32 sub-boxes

Z(000000), Z(000001), Z(000010), Z(000011), …, Z(111011).

We then use verify to kill these, with the exception of the 7 exceptional boxes (11 before joining abutters together) listed in Proposition 1.28.

The choices in verify are made for it by a sequence of integers given as input. The sequence of integers containing the directions for killing Z(000000) is contained in the file data6/000000. In such a sequence, 0 tells verify to sub-divide the present box (by x_{i} = c), to position itself on the ”left-hand” box (x_{i} ≤ c) created by that sub-division, and to read in the next integer in the sequence. A positive integer n tells verify to kill the sub-box it is positioned at directly, using the condition (and killer word, if necessary) on line n in the ’conditionlist’ file, and to then position itself at the “next” natural sub-box. −1 tells verify to omit the sub-box, and mark it as skipped (the sequence of integers used in killing the skipped box Z(s) is contained in a file data6/s)..

The checker program verify, its inputs, and the list of conditions will be available from the Geometry Center. Details about how to get them can be found at

http://www.geom.umn.edu:/locate/HomotopyHyperbolic

Similarly for the program fudging which is used on the 7 exceptional boxes.

Example 5.4: To illustrate the checking in action, this is a (non-representative) example, which shows how the sub-box Z(s) (minus a hole) is killed, where

s = 001000110001110111001111000101111111101111100111001111000001111011110111.

The input associated with this sub-box is

(0, 0, 0, 1929, 12304, 0, 0, 7, 0, 1965, 0, 1929, 1929, 1996, −1),

which causes the program to kill Z(s) in the following fashion:

kill Z(s): kill Z(s0): kill Z(s00): kill Z(s000) with condition 1929 = “L(FwFWFWfWFWFwFwfww)” kill Z(s001) with condition 12304 = “L(FwfWFFWFwFwfwfWfwfw)” kill Z(s01): kill Z(s010): kill Z(s0100) with condition 7 = “L(w)” kill Z(s0101): kill Z(s01010) with condition 1965 = “L(fwFwFWFFWFwFwfwww)” kill Z(s01011): kill Z(s010110) with condition 1929 kill Z(s010110) with condition 1929

kill Z(s011) with condition 1996 = “L(FwFwFWFWfWFWFwFwfww)” omit Z(s1) as shown in figure 5.1. Z(s1) is ignored, so the checker would indicate this omission in its report. In fact,

Z(s1) is omitted entirely, since it is one of the 11 exceptional boxes.

The use of condition “L(w)” so deep in the tree is unusual. In this case, it’s because the manifold in the exceptional sub-box has length(f) = length(w), so that the program will frequently come to places where it can bound length(f) > length(w) nearby.

One might wonder why the checker subdivides Z(s01011), since it’s going to use the same condition to kill both halves. The reason is the error bound for Z(s01011) wasn’t good enough to prove that the sub-box is killed directly.

The binary numbers used by the computer require too much space to print. In the example calculation which follows, we instead use a decimal representation. Also, only 10 decimals are printed, less accurate than the 53 binary digits used for the actual calculations.

The sub-box Z(s01011) is the region where

( \begin{matrix}−1.381589027741 … ≤ Re(L′) ≤ −1.379848991182 … \\ −1.378124546093 … ≤ Re(D′) ≤ −1.376574349753 … \\ 0.999893182771 … ≤ Re(R′) ≤ 1.001274250703 … \\ −2.535837191243 … ≤ Im(L′) ≤ −2.534606799593 … \\ 2.535404997792 … ≤ Im(D′) ≤ −2.534308843448 … \\ −0.001953125000 … ≤ Im(R′) ≤ 0.000000000000 … \end{matrix} )

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

Figure 5.1: six levels of subdivision, in two projections, with all the trimmings At this point, we would like to compute

f, w, g = f^{−1}wf^{−1}w^{−1}f^{−1}w^{−1}fw^{−1}f^{−1}w^{−1}f^{−1}wf^{−1}wfww, length(g),

and so on. However, these items take on values over an entire sub-box and thus are computed via AffApprox’s (first-order Taylor Approximations with remainder bounds), which are not formally defined until the next Chapter. As such, we complete Example 5.4 at the end of Chapter 6.

Chapter 6: Affine Approximations

Remark 6.1: To show that a sub-box of the parameter box W is killed by one of the interesting conditions (plus associated killerword) we need to show that at each point in the sub-box, the killerword evaluated at that point satisfies the given condition. That is, we are simply analyzing a certain function from the sub-box to C.

As described in Remark 6.5, this analysis can be pulled back from the sub-box in question to the unit complex 3-disc A, where A = {(z_{0}, z_{1}, z_{2}) ∈ C^{3} : |z_{k}| ≤ 1 for k = 1, 2, 3}. Loosely, we will analyze such a function on A by using Taylor series approximations consisting of an affine approximating function together with a bound on the “error” in the approximation (this could also be described as a “remainder bound”).

Problems 6.2: There are two immediate problems likely to arise from this Taylor approximation approach. The first problem is the appearance of unpleasant functions such as cosh^{−1}. We have already taken care of this problem by “exponentiating” our preliminary parameter space P. This resulted in all functions under consideration being built up from the co-ordinate functions L′, D′, and R′ on P by means of the elementary operations +, −, ×, /, \sqrt{.}

Second, for a given “built-up function” the computer needs to be able to compute the Taylor approximation, and the error term. This will be handled in this section by developing combination formulas for elementary operations (see the Propositions below). Specifically, given two Taylor approximations with error terms representing functions g and h and an elementary operation on g and h, we will show how to get the Taylor approximation with error term for the resultant function from the two original Taylor approximations.

Remark 6.3: We set up the Taylor approximation approach rigorously as follows. The notation will be a bit unusual, but we are motivated by a desire to stay close to the notation used in the checker computer programs, verify and fudging. However, it should be pointed out that the formulas in this Chapter will be superceded by the ones in Chapter 8, which incorporate a round-off error analysis. It is the Chapter 8 formulas that are used in verify and fudging.

Definition 6.4: An AffApprox x is a five-tuple (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e), consisting of four complex numbers x.f, x.f_{0}, x.f_{1}, x.f_{2} and one real number x.e, which represents all functions g : A → C such that

|g(z_{0}, z_{1}, z_{2}) − (x.f + x.f_{0}z_{0} + x.f_{1}z_{1} + x.f_{2}z_{2})| < x.e

for all (z_{0}, z_{1}, z_{2}) ∈ A. That is, x represents all functions from A to C that are x.e−wellapproximated by the affine function x.f + x.f_{0}z_{0} + x.f_{1}z_{1} + x.f_{2}z_{2}. We will denote this set of functions associated with x by r(x).

Remark 6.5: As mentioned in Remark 6.1, given a sub-box to analyze, instead of working with functions defined on the sub-box, we will work with corresponding functions defined on A. Specifically, rather than build up a function by elementary operations performed on the co-ordinate functions L′, D′, R′ restricted to the given sub-box, we will perform the elementary operations on the following functions defined on A,

(p_{0} + ip_{3}; s_{0} + is_{3}, 0, 0; 0) (p_{1} + ip_{4}; 0, s_{1} + is_{4}, 0; 0) (p_{2} + ip_{5}; 0, 0, s_{2} + is_{5}; 0)

where (p_{0} + ip_{3}, p_{1} + ip_{4}, p_{2} + ip_{5}) is the center of the sub-box in question, and the s_{i} describe the six dimensions of the box. In the computer programs, these three functions are called along, ortho, and whirle, respectively, and p_{i} and s_{i} are denoted pos[i] and size[i], respectively.

After the following Remarks, we state and prove the combination formulas.

Remarks 6.6: i) We will break with the convention used previously in this paper and start the numbering of the Propositions with 6.1. However, we will end this Chapter with Example 6.7.

ii) The negation of a set of functions is the set consisting of the negatives of the original functions, and similarly for other operations.

Proposition 6.1 (unary minus): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) then −(r(x)) = r(−x) where

−x = (−x.f; −x.f_{0}, −x.f_{1}, −x.f_{2}; x.e).

Proof:

|g(z_{0}, z_{1}, z_{2}) − (x.f + x.f_{0}z_{0} + x.f_{1}z_{1} + x.f_{2}z_{2})| < e

if and only if

| − g(z_{0}, z_{1}, z_{2}) − (−x.f − x.f_{0}z_{0} − x.f_{1}z_{1} − x.f_{2}z_{2})| < e

Proposition 6.2 (addition): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is the AffApprox (y.f; y.f_{0}, yf_{1}, y.f_{2}; y.e), then r(x + y) ⊇ r(x) + r(y), where

x + y = (x.f + y.f; x.f_{0} + y.f_{0}, x.f_{1} + y.f_{1}, x.f_{2} + y.f_{2}; x.e + y.e)

Proof: If g ∈ r(x) and h ∈ r(y) then we must show that g + h ∈ r(x + y).

|(g + h)(z_{0}, z_{1}, z_{2}) − ((x.f + y.f) + (x.f_{0} + y.f_{0})z_{0} + (x.f_{1} + y.f_{1})z_{1} + (x.f_{2} + y.f_{2})z_{2})| ≤ |g(z_{0}, z_{1}, z_{2}) − (x.f + (x.f_{0})z_{0} + (x.f_{1})z_{1} + (x.f_{2})z_{2})+

h(z_{0}, z_{1}, z_{2}) − (y.f + (y.f_{0})z_{0} + (y.f_{1})z_{1} + (y.f_{2})z_{2})|

≤ |g(z_{0}, z_{1}, z_{2}) − (x.f + (x.f_{0})z_{0} + (x.f_{1})z_{1} + (x.f_{2})z_{2})|+ |h(z_{0}, z_{1}, z_{2}) − (y.f + (y.f_{0})z_{0} + (y.f_{1})z_{1} + (y.f_{2})z_{2})|

≤ x.e + y.e

We now do subtraction. The statement and proof are essentially the same as for addition. The only thing to note is that the errors add.

Proposition 6.3 (subtraction): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is the AffApprox (y.f; y.f_{0}, yf_{1}, y.f_{2}; y.e), then r(x − y) ⊇ r(x) − r(y), where

x − y = (x.f − y.f; x.f_{0} − y.f_{0}, x.f_{1} − y.f_{1}, x.f_{2} − y.f_{2}; x.e + y.e)

We now state variations on Propositions 6.2 and 6.3 whose usefulness will not be apparent until Chapter 8, when we incorporate round-off error into these formulas. In what follows, a “double” corresponds to a real number, and has an associated AffApprox, with last four entries zero.

Proposition 6.4 (addition of an AffApprox and a double): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is a double, then r(x + y) ⊇ r(x) + r(y), where

x + y = (x.f + y; x.f_{0}, x.f_{1}, x.f_{2}; x.e).

Proposition 6.5 (subtraction of a double from an AffApprox): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is a double, then r(x − y) ⊇ r(x) − r(y), where

x − y = (x.f − y; x.f_{0}, x.f_{1}, x.f_{2}; x.e).

Proposition 6.6 (multiplication): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is the AffApprox (y.f; y.f_{0}, yf_{1}, y.f_{2}; y.e), then r(x × y) ⊇ r(x) × r(y), where

x × y = (x.f × y.f; x.f × y.f_{0} + x.f_{0} × y.f, x.f × y.f_{1} + x.f_{1} × y.f, x.f × y.f_{2} + x.f_{2} × y.f; (size(x) + x.e) × (size(y) + y.e) + (|x.f| × y.e + x.e × |y.f|))

with size(x) = |x.f_{0}| + |x.f_{1}| + |x.f_{2}| and size(y) = |y.f_{0}| + |y.f_{1}| + |y.f_{2}| Proof: If g ∈ r(x) and h ∈ r(y) then we must show that g × h ∈ r(x × y). That is, we need to show

|(g × h)(z_{0}, z_{1}, z_{2}) − ((x.f × y.f)+ (x.f × y.f_{0} + x.f_{0} × y.f)z_{0} + (x.f × y.f_{1} + x.f_{1} × y.f)z_{1} + (x.f × y.f_{2} + x.f_{2} × y.f)z_{2})|

≤ (size(x) + x.e) × (size(y) + y.e) + (|x.f| × y.e + x.e × |y.f|)

Note that for any point (z_{0}, z_{1}, z_{2}) ∈ A and any functions g ∈ r(x) and h ∈ r(y) we can find complex numbers u, v with |u| ≤ 1 and |v| ≤ 1, such that

g(z_{0}, z_{1}, z_{2}) = x.f + (x.f_{0}z_{0} + x.f_{1}z_{1} + x.f_{2}z_{2}) + (x.e)u

and

h(z_{0}, z_{1}, z_{2}) = y.f + (y.f_{0}z_{0} + y.f_{1}z_{1} + y.f_{2}z_{2}) + (y.e)v.

Multiplying out, we see that

(g × h)(z_{0}, z_{1}, z_{2}) = (x.f × y.f)+ (x.f × y.f_{0} + x.f_{0} × y.f)z_{0} + (x.f × y.f_{1} + x.f_{1} × y.f)z_{1} + (x.f × y.f_{2} + x.f_{2} × y.f)z_{2}+

(x.f × y.e)v + (x.e × y.f)u+

((x.f_{0}z_{0} + x.f_{1}z_{1} + x.f_{2}z_{2}) + (x.e)u) × ((y.f_{0}z_{0} + y.f_{1}z_{1} + y.f_{2}z_{2}) + (y.e)v)

Hence,

|(g × h)(z_{0}, z_{1}, z_{2}) − ((x.f × y.f)+ ((x.f × y.f_{0} + x.f_{0} × y.f)z_{0} + (x.f × y.f_{1} + x.f_{1} × y.f)z_{1} + (x.f × y.f_{2} + x.f_{2} × y.f)z_{2}))|

≤ (|x.f|y.e + x.e|y.f|) + (size(x) + x.e) × (size(y) + y.e).

Proposition 6.7 (an AffApprox multiplied by a double): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is a double, then r(x × y) ⊇ r(x) × r(y), where

x × y = (x.f × y; x.f_{0} × y, x.f_{1} × y, x.f_{2} × y; x.e × |y|)

Proposition 6.8 (division): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is the AffApprox (y.f; y.f_{0}, yf_{1}, y.f_{2}; y.e), then r(x/y) ⊇ r(x)/r(y), where

x/y = (x.f/y.f; (−x.f × y.f_{0} + x.f_{0} × y.f)/(y.f^{2}), (−x.f × y.f_{1} + x.f_{1} × y.f)/(y.f^{2}),

(−x.f × y.f_{2} + x.f_{2} × y.f)/(y.f^{2});

(|x.f| + size(x) + x.e)/(|y.f| − (size(y) + y.e))−

((|x.f|/|y.f| + size(x)/|y.f|) + |x.f|size(y)/(|y.f||y.f|)))

Of course, we have to avoid division by zero. That is, we demand that |y.f| > size(y)+y.e.

Proof: For notational convenience, denote (x.f_{0}z_{0} + x.f_{1}z_{1} + x.f_{2}z_{2}) by x.f_{k}z_{k} and similarly for y.f_{k}z_{k} and so on. As above, note that for any point (z_{0}, z_{1}, z_{2}) ∈ A and any functions g ∈ r(x) and h ∈ r(y) we can find complex numbers u, v with |u| ≤ 1 and |v| ≤ 1, such that

g(z_{0}, z_{1}, z_{2}) = x.f + (x.f_{k}z_{k}) + (x.e)u

and

h(z_{0}, z_{1}, z_{2}) = y.f + (y.f_{k}z_{k}) + (y.e)v.

We compare (g/h)(z_{0}, z_{1}, z_{2}) with its putative affine approximation. That is, we analyze

|(x.f + (x.f_{k}z_{k}) + (x.e)u)/(y.f + (y.f_{k}z_{k}) + (y.e)v)−

((x.f/y.f) + \frac{(x.f_{k})y.f − x.f(y.f_{k})}{y.f^{2}}z_{k})|

Putting this over a common denominator of |(y.f^{2})(y.f +(y.f_{k}z_{k})+(y.e)v)| and cancelling equal terms (in the numerator) we are left with a quotient whose numerator is

|x.e(y.f^{2})u − (x.f_{k})y.f(y.f_{k})z_{k} − x.f(y.f_{k}^{2})z_{k}+ (x.f)y.f(y.e)v + x.f_{k}(y.f)y.e(v)z_{k} − x.f(y.f_{k})y.e(v)z_{k}|.

We must show this (first) quotient is bounded by

(|x.f| + size(x) + x.e)/(|y.f| − (size(y) + y.e))− ((|x.f|/|y.f| + size(x)/|y.f|) + |x.f|size(y)/(|y.f||y.f|)).

Putting this over a common denominator of |y.f|^{2}(|y.f| − (size(y) + y.e)) and cancelling equal terms (in the numerator) we are left with a second quotient, whose numerator is

x.e|y.f|^{2} − (−|x.f||y.f|y.e − size(x)|y.f|(size(y) + y.e) − |x.f|size(y)(size(y) + y.e))

and we see that all terms in this numerator are positive. Further, the terms in the numerators of the first and second quotients correspond in a natural way, and each term in the numerator of the second quotient is greater than or equal to the absolute value of its corresponding term in the numerator of the first quotient.

Finally, because the denominator in the second quotient is less than or equal to the absolute value of the denominator in the first quotient, we see that the absolute value of the first quotient is less than or equal to the second quotient, as desired.

We present a couple of variations on Proposition 6.8 which will be useful when we do round-off error.

Proposition 6.9 (division of a double by an AffApprox): If x is a double and y is the AffApprox (y.f; y.f_{0}, yf_{1}, y.f_{2}; y.e), then r(x/y) ⊇ r(x)/r(y), where

x/y = (x/y.f; −x × y.f_{0}/(y.f^{2}), −x.f × y.f_{1}/(y.f^{2}), −x.f × y.f_{2}/(y.f^{2});

(|x|/(|y.f| − (size(y) + y.e))− (|x|/|y.f| + |x|size(y)/(|y.f||y.f|)))

Of course, we have to avoid division by zero. That is, we demand that |y.f| > size(y)+y.e.

Proposition 6.10 (division of an AffApprox by a double): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) and y is a double, then r(x/y) ⊇ r(x)/r(y), where

x/y = (x.f/y; x.f_{0}/y, x.f_{1}/y, x.f_{2}/y; x.e/|y|)

Of course, we have to avoid division by zero. That is, we demand that |y| > 0.

Finally, we do the square root.

Proposition 6.11 (square root): If x is the AffApprox (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.e) then r(\sqrt{x}) ⊇ \sqrt{r(x)}, where

\sqrt{x} = (\sqrt{x.f}; \frac{x.f_{0}}{2\sqrt{x.f}} , \frac{x.f_{1}}{2\sqrt{x.f}} , \frac{x.f_{2}}{2\sqrt{x.f}};

\sqrt{|x.f|} − (\frac{size(x)}{2\sqrt{|x.f|}} + \sqrt{|x.f| − (size(x) + x.e)}))

Of course, we have to avoid division by zero, and taking the real square root of a negative number. In particular, when |x.f| > size(x) + x.e we get the formula above, but if this does not hold, then we use the crude estimate (0; 0, 0, 0; \sqrt{|x.f| + size(x) + x.e}).

Proof: As above, note that for any point (z_{0}, z_{1}, z_{2}) ∈ A and any function g ∈ r(x) we can find a complex number u with |u| ≤ 1, such that

g(z_{0}, z_{1}, z_{2}) = x.f + (x.f_{k}z_{k}) + (x.e)u.

Also, because |x.f| > size(x) + x.e. we see that the argument of x.f + (x.f_{k}z_{k}) + (x.e)u is within π/2 of the argument of x.f, and therefore, we can require that \sqrt{g(z_{0}, z_{1}, z_{2})} has argument within π/4 of the argument of \sqrt{x.f}.

We need to show that

|\sqrt{x.f + x.f_{k}z_{k} + (x.e)u} − (\sqrt{x.f} + \frac{x.f_{k}}{2\sqrt{x.f}})z_{k}|

≤ \sqrt{|x.f|} − (\frac{size(x)}{2\sqrt{|x.f|}} + \sqrt{|x.f| − (size(x) + x.e)} )

Or, after multiplying both sides by \sqrt{|x.f|},

\sqrt{x.f(x.f + x.f_{k}z_{k} + (x.e)u)} − (x.f + (x.f_{k})z_{k}/2)
≤ (|x.f| − size(x)/2) − \sqrt{|x.f|(|x.f| − (size(x) + x.e))}

The two sides of the inequality are of the form A − B and C − D, and we “simplify” by multiplying by \frac{A+B}{A+B} and \frac{C+D}{C+D}. We now show that the (absolute value of the) left-hand numerator is less than or equal to the right-hand numerator. Later, we will show that the (absolute value of the) left-hand denominator is larger than or equal to the right-hand denominator. The left-hand numerator is

|x.f(x.f + x.f_{k}z_{k} + (x.e)u) − (x.f + (x.f_{k})z_{k}/2)^{2}|
= |x.f^{2} + x.f(x.f_{k})z_{k} + x.f(x.e)u − x.f^{2} − x.f(x.f_{k})z_{k} − (x.f_{k}^{2})z_{k}^{2}/4|
= |x.f(x.e)u − (x.f_{k}^{2})z_{k}^{2}/4|

The right-hand numerator is

(|x.f| − size(x)/2)^{2} − |x.f|(|x.f| − (size(x) + x.e))
= |x.f|^{2} − |x.f|size(x) + size(x)^{2}/4 − |x.f|^{2} + |x.f|size(x) + |x.f|x.e
= |x.f|x.e + size(x)^{2}/4

So the left-hand numerator is indeed less than or equal to the right-hand numerator.

We now compare the denominators, but only after dividing each by \sqrt{|x.f|}. The left-hand denominator is

|\sqrt{x.f + x.f_{k}z_{k} + (x.e)u} + (\sqrt{x.f} + \frac{x.f_{k}z_{k}}{2\sqrt{x.f}})|

while the right-hand denominator is

\sqrt{|x.f|} − \frac{size(x)}{2\sqrt{|x.f|}} + \sqrt{|x.f| − (size(x) + x.e)}

The claim that the left-hand denominator is greater than or equal to the right-hand denominator is a bit complicated. First, compare the \sqrt{x.f} term and the \sqrt{|x.f|} terms. They are the same distance from the origin. Next, note that as z_{k} and u take on all values, x.f + x.f_{k}z_{k} + (x.e)u describes a disk centered at x.f and whose radius is less than |\sqrt{x.f}|. Hence, \sqrt{x.f + x.f_{k}z_{k} + (x.e)u} describes a convex symmetric (about the line formed by the origin and x.f) set centered at \sqrt{x.f}. Further, \sqrt{x.f} + \sqrt{x.f + x.f_{k}z_{k} + (x.e)u} describes a convex symmetric (about the line formed by the origin and x.f) set centered at 2\sqrt{x.f}. In any case, it is easy enough to see that no points on this convex symmetric set get closer to the origin than \sqrt{|x.f|} + \sqrt{|x.f| − (size(x) + x.e)}.

Finally, because |\frac{x.f_{k}z_{k}}{2\sqrt{x.f}} | ≤ \frac{size(x)}{2\sqrt{|x.f|}}, no points of

\sqrt{x.f} + \sqrt{x.f + x.f_{k}z_{k} + (x.e)u} + \frac{x.f_{k}z_{k}}{2\sqrt{x.f}}

can get closer to the origin than

\sqrt{|x.f|} + \sqrt{|x.f| − (size(x) + x.e)} − \frac{size(x)}{2\sqrt{|x.f|}}

Example 6.7 (Continuation of Example 5.4): We repeat the description of the subbox under investigation.

The sub-box Z(s01011) with

s = 001000110001110111001111000101111111101111100111001111000001111011110111

HOMOTOPY HYPERBOLIC 3-MANIFOLDS ARE HYPERBOLIC

is the region where

( \begin{matrix}−1.381589027741 … ≤ Re(L′) ≤ −1.379848991182 … \\ −1.378124546093 … ≤ Re(D′) ≤ −1.376574349753 … \\ 0.999893182771 … ≤ Re(R′) ≤ 1.001274250703 … \\ −2.535837191243 … ≤ Im(L′) ≤ −2.534606799593 … \\ 2.535404997792 … ≤ Im(D′) ≤ −2.534308843448 … \\ −0.001953125000 … ≤ Im(R′) ≤ 0.000000000000 … \end{matrix} )

For this sub-box, we get

f = [ \begin{matrix}( \begin{matrix}−0.8677851121 + i1.4607429651; \\ 0.0000248810 − i0.0003125810, \\ 0.0000000000 + i0.0000000000, \\ 0.0000000000 + i0.0000000000; \\ 0.0000000289 \end{matrix} ) & ( \begin{matrix}0.0000000000 + i0.0000000000; \\ 0.0000000000 + i0.0000000000, \\ 0.0000000000 + i0.0000000000, \\ 0.0000000000 + i0.0000000000; \\ 0.0000000000 \end{matrix} ) \\ ( \begin{matrix}0.0000000000 + i0.0000000000; \\ 0.0000000000 + i0.0000000000, \\ 0.0000000000 + i0.0000000000, \\ 0.0000000000 + i0.0000000000; \\ 0.0000000000 \end{matrix} ) & ( \begin{matrix}−0.3006023265 − i0.5060039953; \\ −0.0000909686 − i0.0000593570, \\ 0.0000000000 + i0.0000000000, \\ 0.0000000000 + i0.0000000000; \\ 0.0000000301 \end{matrix} ) \end{matrix} ]

and

w = [ \begin{matrix}( \begin{matrix}−0.5845111829 + i0.4773282853; \\ 0.0000000000 + i0.0000000000, \\ −0.0000296707 − i0.0001657332, \\ −0.0004345111 − i0.0001209539; \\ 0.0000002590 \end{matrix} ) & ( \begin{matrix}−0.2840228472 + i0.9825063583; \\ 0.0000000000 + i0.0000000000, \\ 0.0000516606 − i0.0001128245, \\ 0.0005776611 − i0.0001998632; \\ 0.0000006462 \end{matrix} ) \\ ( \begin{matrix}−0.2832291572 + i0.9833572297; \\ 0.0000000000 + i0.0000000000, \\ 0.0000515806 − i0.0001129408, \\ −0.0005778031 + i0.0002005440; \\ 0.0000002806 \end{matrix} ) & ( \begin{matrix}−0.5846352333 + i0.4764792236; \\ 0.0000000000 + i0.0000000000, \\ −0.0000294917 − i0.0001656653, \\ 0.0004341392 + i0.0001213070; \\ 0.0000005286 \end{matrix} ) \end{matrix} ] .

calculating g = f^{−1}wf^{−1}w^{−1}f^{−1}w^{−1}fw^{−1}f^{−1}w^{−1}f^{−1}wf^{−1}wfww gives

g = [ \begin{matrix}( \begin{matrix}−0.5764337542 + i0.4752708071; \\ −0.0031657223 − i0.0001436786, \\ −0.0017723577 + i0.0000352928, \\ −0.0011623491 + i0.0017516088; \\ 0.0008229225 \end{matrix} ) & ( \begin{matrix}−0.2704033973 + i0.9822741250; \\ −0.0045902952 − i0.0019135041, \\ −0.0026219461 − i0.0007506230, \\ −0.0002823450 + i0.0033805602; \\ 0.0008037640 \end{matrix} ) \\ ( \begin{matrix}−0.2861207992 + i0.9766064999; \\ −0.0002777968 + i0.0020330488, \\ 0.0000837571 + i0.0010241875, \\ 0.0028322367 − i0.0005972336; \\ 0.0018172437 \end{matrix} ) & ( \begin{matrix}−0.5861133046 + i0.4624368851; \\ −0.0021932627 + i0.0040523411, \\ −0.0008612361 + i0.0022394639, \\ 0.0061581377 − i0.0005862070; \\ 0.0017738513 \end{matrix} ) \end{matrix} ] .

We then get

length(g) = ( \begin{matrix}−1.3588762105 − i2.4897230182; \\ 0.0030210500 − i0.0182284729, \\ 0.0007938572 − i0.0096614614, \\ −0.0122034521 + i0.0074353043; \\ 0.0080071969 \end{matrix} )

and

\frac{length(g)}{L′} = ( \begin{matrix}0.9825397896 − i0.0008933519; \\ 0.0053701602 + i0.0037789019, \\ 0.0028076072 + i0.0018421952, \\ −0.0002400615 − i0.0049443045; \\ 0.0027802966 \end{matrix} ) .

This isn’t quite good enough to kill the sub-box, since |length(g)/L′| can be high as 1.0001951323.

When we subdivide Z(s01011), we have to analyze two sub-boxes, Z(s010110) and Z(s010111). For Z(s010110), the same calculation on the region

−1.381589027741073400 ≤ Re(L′) ≤ −1.379848991182205200 −1.378124546093485700 ≤ Re(D′) ≤ −1.376574349753672900 0.999893182771602220 ≤ Re(R′) ≤ 1.001274250703607400 −2.535837191243490300 ≤ Im(L′) ≤ −2.534606799593201600 −2.535404997792558600 ≤ Im(D′) ≤ −2.534308843448505900 −0.001953125000000000 ≤ Im(R′) ≤ −0.000976562500000000 gives

\frac{length(g)}{L′} = ( \begin{matrix}0.9814518667 + i0.0008103446; \\ 0.0053616729 + i0.0037834001, \\ 0.0028027236 + i0.0018435245, \\ −0.0013175066 − i0.0032448794; \\ 0.0019033926 \end{matrix} ) ,

and we can then bound |\frac{length(g)}{L′}| ≤ 0.9967745579, which kills Z(s010110). On Z(s010111), the calculation gives

\frac{length(g)}{L′} = ( \begin{matrix}0.9836225919 − i0.0025990177; \\ 0.0053786346 + i0.0037743930, \\ 0.0028124892 + i0.0018408583, \\ −0.0013333182 − i0.0032343347; \\ 0.0019044429 \end{matrix} )

and |\frac{length(g)}{L′}| ≤ 0.9989610507, which kills Z(s010111).

Chapter 7: Complex Numbers with Round-Off Error

Remark 7.1: The theoretical method for proving Theorem 0.2 has been implemented on the computer programs verify and fudging given in the Appendices. To make this computer-aided proof rigorous, we need to deal with round-off error in calculations.

One approach to round-off error would be to use interval arithmetic packages to carry out all calculations with floating-point numbers (also called “doubles”), or to generate our own version of these packages. However, it appears that this would be much too slow given the size of our collection of sub-boxes and conditions and killer words.

To solve this problem of speed, we implement round-off error at a higher level of programing. That is, we incorporate round-off error directly into AffApprox’s. This necessitates that we incorporate it into complex numbers as well.

Definition 7.2: In the next Chapter we work with AffApprox’s. In this section we show how to do standard operations on complex numbers while keeping track of round-off error. There are two types of complex numbers to consider:

1.) An XComplex corresponds to a complex number that is represented exactly. Thus, it simply consists of a real part and an imaginary part.

2.) An AComplex corresponds to an “interval” that contains the complex number in question. Thus, it consists of an XComplex and a floating-point number representing the error. In particular, (x; e) represents the set of complex numbers {w : |w − x| ≤ e }. Following the notation of Chapter 6, we could now denote this set of complex numbers by r(x, e), but instead we suppress mention of the r functions throughout the rest of this section. It seems preferable to abuse notation in this fashion in the interests of simplicity.

Remark 7.3: In general, our operations act on XComplexes and produce AComplexes, or they act on AComplexes and produce AComplexes . In one case, the unary minus, an XComplex goes to an XComplex. In the calculations that follow the effect on the error is the whole point.

Conventions 7.4: We begin, by writing down our basic rules, which follow easily from the IEEE-754 double-precision standard for machine arithmetic. (Actually, the “hypot” function h(a, b), which computes by elaborate chicanery \sqrt{a^{2} + b^{2}}, is not part of the IEEE standard, but satisfies the appropriate standard according to the documentation provided (see [Kahan]).) The operations here are on double-precision floating-point real numbers (doubles) and we denote a true operation by the usual symbol and the associated machine operation by the same symbol in a circle, with two exceptions: a machine square root \sqrt{a} is denoted ^{o} \sqrt{a} and the machine version of the hypot function is denoted h_{∘}. Perhaps a third exception is our occasional notation of true multiplication by the absence of a symbol. The standard number used in error analysis is an “EPS.” It depends on the number of bits used to store floating-point numbers, and this can vary from machine to machine. Finally, it should be noted that our analysis breaks down when there is “underflow,” so in the computer programs we ask the computer to inform us if underflow has occurred.

As in Chapter 6, we now break with the usual numbering convention.

Basic Properties 7.0 (assuming no underflow):

1 + k × EP S = 1 ⊕ (k ⊗ EP S) when k is an integer which is not huge in absolute value.

2^{k} × A = 2^{k} ⊗ A when k is an integer, 2^{k} ⊗ A is not infinity.

|(a + b) − (a ⊕ b)| ≤ (EP S/2)|a + b|

|(a + b) − (a ⊕ b)| ≤ (EP S/2)|a ⊕ b|

|(a − b) − (a ⊖ b)| ≤ (EP S/2)|a − b|

|(a − b) − (a ⊖ b)| ≤ (EP S/2)|a ⊖ b|

|(a × b) − (a ⊗ b)| ≤ (EP S/2)|a × b|

|(a × b) − (a ⊗ b)| ≤ (EP S/2)|a ⊗ b|

|(a/b) − (a ⊘ b)| ≤ (EP S/2)|a/b|

|(a/b) − (a ⊘ b)| ≤ (EP S/2)|a ⊘ b|

|\sqrt{a} − ^{o} \sqrt{a}| ≤ (EP S/2)|\sqrt{a}|

|\sqrt{a} − ^{o} \sqrt{a}| ≤ (EP S/2)| ^{o} \sqrt{a}|

|h(a, b) − h_{∘}(a, b)| ≤ (EP S)|h(a, b)|

|h(a, b) − h_{∘}(a, b)| ≤ (EP S)|h_{∘}(a, b)|

From these formulas, we immediately compute the following.

(1 − EP S/2)|a + b| ≤ |a ⊕ b| ≤ (1 + EP S/2)|a + b|

(1 − EP S/2)|a ⊕ b| ≤ |a + b| ≤ (1 + EP S/2)|a ⊕ b|

(1 − EP S/2)|a − b| ≤ |a ⊖ b| ≤ (1 + EP S/2)|a − b|

(1 − EP S/2)|a ⊖ b| ≤ |a − b| ≤ (1 + EP S/2)|a ⊖ b|

(1 − EP S/2)|a × b| ≤ |a ⊗ b| ≤ (1 + EP S/2)|a × b|

(1 − EP S/2)|a ⊗ b| ≤ |a × b| ≤ (1 + EP S/2)|a ⊗ b|

(1 − EP S/2)|a/b| ≤ |a ⊘ b| ≤ (1 + EP S/2)|a/b|

(1 − EP S/2)|a ⊘ b| ≤ |a/b| ≤ (1 + EP S/2)|a ⊘ b|

(1 − EP S/2)|\sqrt{a}| ≤ | ^{o} \sqrt{a}| ≤ (1 + EP S/2)|\sqrt{a}|

(1 − EP S/2)| ^{o} \sqrt{a}| ≤ |\sqrt{a}| ≤ (1 + EP S/2)| ^{o} \sqrt{a}|

(1 − EP S)|h(a, b)| ≤ |h_{∘}(a, b)| ≤ (1 + EP S)|h(a, b)|

(1 − EP S)|h_{∘}(a, b)| ≤ |h(a, b)| ≤ (1 + EP S)|h_{∘}(a, b)|

Of course, we can also get the following type of formula, which is sometimes convenient, for example, in the proof of Lemma 7.2.

(\frac{1}{1 + \frac{EP S}{2}} )|a ⊕ b| ≤ |a + b| ≤ (\frac{1}{1 − \frac{EP S}{2}} )|a ⊕ b|

Proof: There is a finite set of numbers which are representable on the computer, and the IEEE standard states that the result of an operation is always the closest representable number to the true solution. Ignoring technicalities, a non-zero floating-point number is represented by a fixed number of bits of which the first determines the sign of the number, the next m represent the exponent, and the remaining n represent the mantissa of the number. Because our non-zero numbers start with a 1, that means the n mantissa bits actually represent the next n binary digits after the 1. That is, the mantissa is actually 1.b_{1}b_{2}b_{3}...b_{n}. With this divyying up of the m + n + 1 bits among exponent and mantissa, EP S would be 2^{−n} and EP S/2 would be 2^{−(n+1)}.

Given this set-up, properties of the form

|(a + b) − (a ⊕ b)| ≤ (EP S/2)|a + b|

follow immediately. Then,

|(a + b) − (a ⊕ b)| ≤ (EP S/2)|a ⊕ b|

follows because the true answer has “exponent” which is less than or equal to the exponent of the machine answer.

Before starting in with our Propositions, we prove a couple of lemmas.

Lemma 7.0:

(1 − EP S) ⊗ |a ⊕ b| ≤ |a + b| ≤ (1 + EP S) ⊗ |a ⊕ b|
Analagous formulas hold for −, ∗, /, \sqrt{.}

Proof: Assume a + b > 0. If (1 + EP S) ⊗ (a ⊕ b) < (a + b) then the machine number (1 + EP S) ⊗ (a ⊕ b) is a better approximation to a + b than a ⊕ b, because (a ⊕ b) < (1 + EP S) ⊗ (a ⊕ b). This contradicts the IEEE standard. The case a + b < 0 can be handled similarly, and the case a + b = 0 is trivial. Similarly for the left-hand inequality.

Lemma 7.1:

(1 + EP S/2)^{a}A ≤ (1 + kEP S) ⊗ A

where A ≥ 0, and a and k are (not huge) integers, such that for a even, k = \frac{a}{2} + 1 and for a odd, k = \frac{a+1}{2} + 1.

Proof:

(1 + EP S/2)^{a}A ≤ (1 − EP S/2)(1 + kEP S)A ≤ (1 + kEP S) ⊗ A

The first inequality holds if a and k are as in the Lemma, and the second inequality is a consequence of one of the formulas preceding Lemma 7.0 (A ≥ 0).

We start the operations. We will give proofs for most, the others should be straightforward to derive. Note that for an XComplex, x = (x.re, x.im), and for an AComplex, x = (x.re, x.im, x.e).

Proposition 7.1 (-X):

−x = (−x.re, −x.im).

Proposition 7.2 (X + D) (an XComplex and a double added together, which yields an AComplex):

x + d = (x.re ⊕ d, x.im; (EP S/2) ⊗ |x.re ⊕ d|)

Proof: The error is bounded by

|(x.re + d) − (x.re ⊕ d)|
≤ (EP S/2)|x.re ⊕ d|
= (EP S/2) ⊗ |x.re ⊕ d|

Proposition 7.3 (X - D) (a double subtracted from an XComplex, which yields an AComplex):

x − d = (x.re ⊖ d, x.im; (EP S/2) ⊗ |x.re ⊖ d|)

Proposition 7.4 (X + X) (an XComplex and an XComplex added together, which yields an AComplex):

x+y = (x.re⊕y.re, x.im⊕y.im; (EP S/2)⊗((1+EP S)⊗(|x.re⊕y.re|⊕|x.im⊕y.im|)))

Proof: The error is bounded by

|(x.re + y.re) − (x.re ⊕ y.re)| + |(x.im + y.im) − (x.im ⊕ y.im)|
≤ (EP S/2)(|x.re ⊕ y.re| + |x.im ⊕ y.im|)
≤ (EP S/2)((1 + EP S) ⊗ (|x.re ⊕ y.re| ⊕ |x.im ⊕ y.im|))
= (EP S/2) ⊗ ((1 + EP S) ⊗ (|x.re ⊕ y.re| ⊕ |x.im ⊕ y.im|))

To go from line 2 to line 3 we used Lemma 7.0.

Proposition 7.5 (X - X):

x+y = (x.re⊖y.re, x.im⊖y.im; (EP S/2)⊗((1+EP S)⊗(|x.re⊖y.re|⊕|x.im⊖y.im|)))

Proposition 7.6 (A + A) (an AComplex and an AComplex added together, which yields an AComplex):

x + y = (re, im; e) where re = x.re ⊕ y.re im = x.im ⊕ y.im e = (1 + 2EP S) ⊗ (((EP S/2) ⊗ (|re| ⊕ |im|)) ⊕ (x.e ⊕ y.e))

Proof: The error is bounded by the sum of the contributions from the real part, the imaginary part, and the two individual errors:

|(x.re ⊕ y.re) − (x.re + y.re)| + |(x.im ⊕ y.im) − (x.im + y.im)| + (x.e + y.e).

≤ (EP S/2)|x.re ⊕ y.re| + (EP S/2)|x.im ⊕ y.im| + (1 + EP S/2)(x.e ⊕ y.e)

≤ (1 + EP S/2)(EP S/2)(|x.re ⊕ y.re| ⊕ |x.im ⊕ y.im|) + (1 + EP S/2)(x.e ⊕ y.e)

= (1 + EP S/2)((EP S/2)(|x.re ⊕ y.re| ⊕ |x.im ⊕ y.im|) + (x.e ⊕ y.e))

≤ (1 + EP S/2)^{2}(((EP S/2)(|x.re ⊕ y.re| ⊕ |x.im ⊕ y.im|)) ⊕ (x.e ⊕ y.e))

≤ (1 + 2EP S) ⊗ (((EP S/2) ⊗ (|x.re ⊕ y.re| ⊕ |x.im ⊕ y.im|)) ⊕ (x.e ⊕ y.e))

The hierarchy for machine operations is the same as that for true operations, so one pair of parentheses is unnecessary and will often be omitted in what follows.

Proposition 7.7 (A - A):

x + y = (re, im; e) where re = x.re ⊖ y.re im = x.im ⊖ y.im e = (1 + 2EP S) ⊗ (((EP S/2) ⊗ (|re| ⊕ |im|)) ⊕ (x.e ⊕ y.e))

Proposition 7.8 (X × D):

x × d = (re, im; e) where re = x.re ⊗ y im = x.im ⊗ y e = (EP S/2) ⊗ ((1 + EP S) ⊗ (|re| ⊕ |im|))

Proof: The error is bounded by

|(x.re × y) − (x.re ⊗ y)| + |(x.im × y) − (x.im ⊗ y)|
≤ (EP S/2)|x.re ⊗ y| + (EP S/2)|x.im ⊗ y|

= (EP S/2)(|x.re ⊗ y| + |x.im ⊗ y|)
≤ (EP S/2) ⊗ ((1 + EP S) ⊗ (|x.re ⊗ y| ⊕ |x.im ⊗ y|))

Proposition 7.9 (X / D):

x/d = (re, im; e)where re = x.re ⊘ y im = x.im ⊘ y e = (EP S/2) ⊗ ((1 + EP S) ⊗ (|re| ⊕ |im|))

Proposition 7.10 (X × X):

x × y = (re, im; e) where re = re1 ⊖ re2, with re1 = x.re ⊗ y.re and re2 = x.im ⊗ y.im im = im1 ⊕ im2, with im1 = x.re ⊗ y.im and im2 = x.im ⊗ y.re e = EP S ⊗ ((1 + 2EP S) ⊗ ((|re1| ⊕ |re2|) ⊕ (|im1| ⊕ |im2|)))

Proof: The error is bounded by the sum of the contributions from the real part and the imaginary part:

|(x.re × y.re − x.im × y.im) − ((x.re ⊗ y.re) ⊖ (x.im ⊗ y.im))| + |(x.re × y.im + x.im × y.re) − ((x.re ⊗ y.re) ⊕ (x.im ⊗ y.im))|

We want to bound this by a machine formula. Let’s begin by bounding

|(x.re × y.re − x.im × y.im) − ((x.re ⊗ y.re) ⊖ (x.im ⊗ y.im))|

by a machine formula.

|(x.re × y.re − x.im × y.im) − ((x.re ⊗ y.re) ⊖ (x.im ⊗ y.im))|

≤ |((x.re × y.re) − (x.im × y.im)) − ((x.re ⊗ y.re) − (x.im ⊗ y.im))| + |((x.re ⊗ y.re) − (x.im ⊗ y.im)) − ((x.re ⊗ y.re) ⊖ (x.im ⊗ y.im))|

≤ |(x.re × y.re) − (x.re ⊗ y.re)| + |(x.im × y.im) − (x.im ⊗ y.im)| + (EP S/2)|(x.re ⊗ y.re) − (x.im ⊗ y.im)|

≤ (EP S/2)|(x.re ⊗ y.re)| + (EP S/2)|(x.im ⊗ y.im)| + (EP S/2)(|x.re ⊗ y.re| + |x.im ⊗ y.im|)

= (EP S/2)(2)(|x.re ⊗ y.re| + |x.im ⊗ y.im|)

≤ EP S(1 + EP S/2)(|x.re ⊗ y.re| ⊕ |(x.im ⊗ y.im|)

Almost the exact same calculation produces the analagous formula for the imaginary contribution, and we now combine the two to get a bound on the total error.

≤ EP S(1 + EP S/2)(|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) + EP S(1 + EP S/2)(|x.re ⊗ y.im| ⊕ |x.im ⊗ y.re|)

= EP S(1 + EP S/2)((x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) + (|x.re ⊗ y.im| ⊕ |x.im ⊗ y.re|))

≤ EP S(1 + EP S/2)^{2}((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) ⊕ (|x.re ⊗ y.im| ⊕ |x.im ⊗ y.re|))

≤ EP S ⊗ ((1 + 2EP S) ⊗ ((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) ⊕ (|x.re ⊗ y.im| ⊕ |x.im ⊗ y.re|)))

Proposition 7.11 (D / X):

x/y = (re, im; e) where

re = (x ⊗ y.re) ⊘ nrm where nrm = y.re ⊗ y.re ⊕ y.im ⊗ y.im
im = −(x ⊗ y.im) ⊘ nrm
e = (2EP S) ⊗ ((1 + 2EP S) ⊗ (|re| ⊕ |im|))

Proof: The true version of x/y is equal to (x × y.re + i(−x × y.im))/(y.re^{2} + y.im^{2}) and we need to compare this with the machine version to find the error. Further, this error is less than or equal to the sum of the real error and the imaginary error. Thus, we start with the real calculation (as above, we use nrm to represent the machine version of y.re^{2} + y.im^{2}).

|\frac{x × y.re}{y.re^{2} + y.im^{2}} − ((x ⊗ y.re) ⊘ nrm)|

≤ |(x ⊗ y.re) ⊘ nrm − \frac{x ⊗ y.re}{nrm}| + |\frac{x ⊗ y.re}{nrm} − \frac{x × y.re}{nrm}| + |\frac{x × y.re}{nrm} − \frac{x × y.re}{y.re^{2} + y.im^{2}} |

Before continuing, let’s compare \frac{1}{nrm} and \frac{1}{y.re^{2}+y.im^{2}} by developing a formula for comparing \frac{1}{a^{2}+b^{2}} and its associated \frac{1}{nrm}:

Lemma 7.2:

|\frac{1}{nrm} − \frac{1}{a^{2} + b^{2}} | ≤ (EP S + (EP S/2)^{2})\frac{1}{nrm}

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

where nrm = a ⊗ a ⊕ b ⊗ b.

Proof: We compute that

(\frac{1}{1 + EP S/2})^{2} × nrm ≤ a^{2} + b^{2} ≤ (\frac{1}{1 − EP S/2})^{2} × nrm,

hence

\frac{1}{nrm}(1 − EP S/2)^{2} ≤ \frac{1}{a^{2} + b^{2}} ≤ \frac{1}{nrm}(1 + EP S/2)^{2}.

It then follows that

|\frac{1}{nrm} − \frac{1}{a^{2} + b^{2}} | ≤ \frac{1}{nrm}(1 + EP S/2)^{2} − \frac{1}{nrm}

= \frac{1}{nrm}((1 + EP S/2)^{2} − 1) = (EP S + (EP S/2)^{2})\frac{1}{nrm}

Getting back to our main calculation (with nrm = y.re ⊗ y.re ⊕ y.im ⊗ y.im),

|(x ⊗ y.re) ⊘ nrm − \frac{x ⊗ y.re}{nrm}| + |\frac{x ⊗ y.re}{nrm} − \frac{x × y.re}{nrm}| + |\frac{x × y.re}{nrm} − \frac{x × y.re}{y.re^{2} + y.im^{2}} |

≤ (EP S/2)\frac{|x ⊗ y.re|}{nrm} + (EP S/2)\frac{|x ⊗ y.re|}{nrm} + (EP S + (EP S/2)^{2})\frac{|x × y.re|}{nrm}

= (EP S/2)(\frac{1}{nrm})(2|x ⊗ y.re| + (2 + EP S/2) × |x × y.re|)

≤ (EP S/2)(\frac{1}{nrm})(2|x ⊗ y.re| + (2 + EP S/2)(1 + EP S/2) × |x ⊗ y.re|)

= (EP S/2)(\frac{1}{nrm})(|x ⊗ y.re|)(2 + (2 + EP S/2)(1 + EP S/2))

≤ (EP S/2)(4 + 3EP S/2 + (EP S/2)^{2})(|x ⊗ y.re|)(\frac{1}{nrm})

≤ (EP S/2)(4 + 3EP S/2 + (EP S/2)^{2})(1 + EP S/2)(|x ⊗ y.re| ⊘ nrm)

≤ (2EP S)(1 + 3EP S/8 + (EP S/4)^{2})(1 + EP S/2)(|(x ⊗ y.re ⊘ nrm)|)

We also get the analagous formula for the imaginary contribution for the error, so our total error is bounded by (2EP S)(1+3EP S/8+(EP S/4)^{2})(1+EP S/2)((|(x⊗y.re)⊘nrm|)+(|(x⊗y.im)⊘nrm|)) ≤ (2EP S)(1+3EP S/8+(EP S/4)^{2})(1+EP S/2)^{2}((|(x⊗y.re)⊘nrm|)⊕(|(x⊗y.im)⊘nrm|))

≤ (2EP S)(1 − EP S/2)(1 + 2EP S)((|(x ⊗ y.re) ⊘ nrm|) ⊕ (|(x ⊗ y.im) ⊘ nrm|))

≤ (2EP S) ⊗ ((1 + 2EP S) ⊗ ((|(x ⊗ y.re) ⊘ nrm|) ⊕ (|(x ⊗ y.im) ⊘ nrm|)))

Here we used the fact that

(1 + 3EP S/8 + (EP S/4)^{2})(1 + EP S/2)^{2} ≤ (1 − EP S/2)(1 + 2EP S)

Proposition 7.12 (X / X):

x/y = (re, im; e) where re = (x.re ⊗ y.re ⊕ x.im ⊗ y.im) ⊘ nrm where nrm = y.re ⊗ y.re ⊕ y.im ⊗ y.im im = (x.im ⊗ y.re ⊖ x.re ⊗ y.im) ⊘ nrm e = (5EP S/2) ⊗ ((1 + 3EP S) ⊗ A) where

A = ((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) ⊕ (|x.im ⊗ y.re| ⊕ |x.re ⊗ y.im|)) ⊘ nrm

Proof: It will be useful to begin by comparing (a × b + c × d)/(e × e + f × f) with (a ⊗ b ⊕

c ⊗ d) ⊘ nrm.

Lemma 7.3:

|(a ⊗ b ⊕ c ⊗ d) ⊘ nrm − (a × b + c × d)/e × e + f × f)|

≤ (EP S/2)(1 + EP S/2)(5 + 3EP S/2 + (EP S/2)^{2})(|a ⊗ b| ⊕ |c ⊗ d|)/nrm

Proof: At one point in the proof, we will use the fact that |A ⊕ B| ≤ |A| ⊕ |B|. This fact is easily seen by considering the various possibilities for the sign of A versus the sign of B. At a different point in the proof, Lemma 7.2 with a, b replaced by e, f will be used.

|(a ⊗ b ⊕ c ⊗ d) ⊘ nrm − (a × b + c × d)/e × e + f × f)|

≤ |(a ⊗ b ⊕ c ⊗ d) ⊘ nrm − (a ⊗ b ⊕ c ⊗ d)/nrm| + |(a ⊗ b ⊕ c ⊗ d)/nrm − (a × b + c × d)/(e × e + f × f)|

≤ (EP S/2)|(a ⊗ b ⊕ c ⊗ d)/nrm| + |(a ⊗ b ⊕ c ⊗ d)/nrm − (a ⊗ b + c ⊗ d)/nrm| + |(a ⊗ b + c ⊗ d)/nrm − (a × b + c × d)/(e × e + f × f)|

≤ (EP S/2)|a ⊗ b ⊕ c ⊗ d|/nrm + |(a ⊗ b ⊕ c ⊗ d) − (a ⊗ b + c ⊗ d)|/nrm

+ |(a ⊗ b + c ⊗ d)/nrm − (a × b + c × d)/nrm| + |(a × b + c × d)/nrm − (a × b + c × d)/(e × e + f × f)|

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

≤ (EP S/2)|a ⊗ b ⊕ c ⊗ d|/nrm + (EP S/2)|a ⊗ b ⊕ c ⊗ d|/nrm

+ |(a ⊗ b + c ⊗ d)/nrm − (a × b + c × d)/nrm| + |(a × b + c × d)/nrm − (a × b + c × d)/(e × e + f × f)|

≤ (EP S/2)|a ⊗ b ⊕ c ⊗ d|/nrm + (EP S/2)|a ⊗ b ⊕ c ⊗ d|/nrm

+ |(a ⊗ b − a × b)/nrm − (c ⊗ d − c × d)/nrm| + (EP S + (EP S/2)^{2})|(a × b + c × d)|/nrm

≤ (EP S)|a ⊗ b ⊕ c ⊗ d|/nrm + (EP S/2)|a ⊗ b|/nrm + (EP S/2)|c ⊗ d|/nrm + (EP S + (EP S/2)^{2})(1 + EP S/2)|(a ⊗ b + c ⊗ d)|/nrm

≤ (EP S)|a ⊗ b ⊕ c ⊗ d|/nrm + (EP S/2)|a ⊗ b|/nrm + (EP S/2)|c ⊗ d|/nrm + (EP S + (EP S/2)^{2})(1 + EP S/2)(|a ⊗ b| + |c ⊗ d|)/nrm

≤ (EP S)|a ⊗ b ⊕ c ⊗ d|/nrm + (EP S/2 + (EP S + (EP S/2)^{2})(1 + EP S/2))(|a ⊗ b| + |c ⊗ d|)/nrm

≤ (EP S)|a ⊗ b ⊕ c ⊗ d|/nrm + (EP S/2)(1 + (2 + EP S/2)(1 + EP S/2))(|a ⊗ b| + |c ⊗ d|)/nrm

≤ (EP S)(|a ⊗ b| ⊕ |c ⊗ d|)/nrm + (EP S/2)(3 + 3EP S/2 + (EP S/2)^{2})(|a ⊗ b| + |c ⊗ d|)/nrm

≤ (EP S)(1 + EP S/2)(|a ⊗ b| ⊕ |c ⊗ d|)/nrm

+ (EP S/2)(3 + 3EP S/2 + (EP S/2)^{2})(1 + EP S/2)(|a ⊗ b| ⊕ |c ⊗ d|)/nrm ≤ (EP S/2)(1 + EP S/2)(2 + (3 + 3EP S/2 + (EP S/2)^{2}))(|a ⊗ b| ⊕ |c ⊗ d|)/nrm

≤ (EP S/2)(1 + EP S/2)(5 + 3EP S/2 + (EP S/2)^{2})(|a ⊗ b| ⊕ |c ⊗ d|)/nrm

We now use this lemma to get the error term for X/X. Of course, this error is less than the sum of the real and imaginary errors. Also, we let

A = ((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) ⊕ (|x.im ⊗ y.re| ⊕ |(−x.re) ⊗ y.im|)) ⊘ nrm

|(x.re⊗y.re⊕x.im⊗y.im)⊘nrm−(x.re×y.re+x.im×y.im)/(y.re×y.re+y.im×y.im)|+ |(x.im⊗y.re⊕(−x.re)⊗y.im)⊘nrm−(x.im×y.re+(−x.re)×y.im)/(y.re×y.re+y.im×y.im)|

≤ (EP S/2)(1 + EP S/2)(5 + 3EP S/2 + (EP S/2)^{2})((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) + (|x.im ⊗ y.re| ⊕ |x.re ⊗ y.im|))/nrm

≤ (EP S/2)(1 + EP S/2)^{3}(5 + 3EP S/2 + (EP S/2)^{2})(((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) ⊕ (|x.im ⊗ y.re| ⊕ |(−x.re) ⊗ y.im|)) ⊘ nrm)

= (EP S/2)(1 + EP S/2)^{3}(5 + 3EP S/2 + (EP S/2)^{2})(A)
≤ (1 − (EP S/2))^{2}(5EP S/2)(1 + 3EP S)(A)
≤ (1 − (EP S/2))(5EP S/2)((1 + 3EP S) ⊗ A)
≤ (5EP S/2) ⊗ ((1 + 3EP S) ⊗ A)

Here we used the fact that

(1 + EP S/2)^{3}(5 + 3EP S/2 + (EP S/2)^{2}) ≤ (1 − EP S/2)^{2}(5)(1 + 3EP S)

Proposition 7.13 (A / A):

x/y = (re, im; e) where re = (x.re ⊗ y.re ⊕ x.im ⊗ y.im) ⊘ nrm where nrm = y.re ⊗ y.re ⊕ y.im ⊗ y.im im = (x.im ⊗ y.re ⊖ x.re ⊗ y.im) ⊘ nrm e = (1 + 4EP S) ⊗ (((5EP S/2) ⊗ A ⊕ (1 + 103EP S) ⊗ B) ⊘ nrm) where

A = (|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) ⊕ (|x.im ⊗ y.re| ⊕ |x.re ⊗ y.im|)
B = x.e ⊗ (|y.re| ⊕ |y.im|) ⊕ (|x.re| ⊕ |x.im|) ⊗ y.e

We are assuming (the computer will complain if this is not true) y.e < 100EP S ⊗ |y|, or, more accurately,

y.e^{2} < ((10000EP S) ⊗ EP S) ⊗ nrm.

Proof: The error is bounded by |x/y − x ⊘ y| + (\frac{x}{y}).e where

(\frac{x}{y}).e = \frac{|x| + x.e}{|y| − y.e} − \frac{|x|}{|y|}

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

= \frac{|x||y| + |y|x.e − |x||y| + |x|y.e}{|y|(|y| − y.e)}

= \frac{|y|x.e + |x|y.e}{|y|(|y| − y.e)}

≤ (1 + 101EP S)\frac{|y|x.e + |x|y.e}{|y|^{2}}

We have used the fact that our assertion y.e^{2} < (10000EP S ⊗ EP S) ⊗ nrm implies that

\frac{1}{|y|(|y| − y.e)} ≤ (1 + 101EP S)\frac{1}{|y|^{2}} ,

which we derive in the next seven lines.

y.e^{2} < (10000EP S ⊗ EP S) ⊗ nrm ≤ (1 + (EP S/2))(10000EP S ⊗ EP S) × nrm

≤ (1 + (EP S/2))^{3}(10000EP S ⊗ EP S) × (y.re^{2} + y.im^{2})
≤ (1 + (EP S/2))^{4}(10000EP S × EP S) × (y.re^{2} + y.im^{2})
= (1 + (EP S/2))^{4}(100EP S)^{2} × |y|^{2}

This implies that y.e < A × |y|, where A = (1 + (EP S/2))^{2}(100EP S). Now, noting that \frac{1}{1−A} ≤ 1 + 101EP S), we see that

\frac{1}{|y|(|y| − y.e)} ≤ \frac{1}{|y|(|y| − A|y|)} = \frac{1}{|y|^{2}(1 − A)} ≤ (1 + 101EP S)\frac{1}{|y|^{2}}

Resuming with our main proof, and setting

A = (|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|) ⊕ (|x.im ⊗ y.re| ⊕ |x.re ⊗ y.im|)

B = x.e ⊗ (|y.re| ⊕ |y.im|) ⊕ (|x.re| ⊕ |x.im|) ⊗ y.e

we have that

|x/y − x ⊘ y| + (\frac{x}{y}).e

≤ |x/y − x ⊘ y| + (1 + 101EP S)\frac{|y|x.e + |x|y.e}{|y|^{2}}

≤ (EP S/2)(1 + EP S/2)(5 + 3EP S/2 + (EP S/2)^{2})((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|)

+ (|x.im ⊗ y.re| ⊕ |x.re ⊗ y.im|))/nrm + (1 + 101EP S)(x.e × (|y.re| + |y.im|) + (|x.re| + |x.im|) × y.e)/(|y|^{2})

≤ (5EP S/2)(1 + EP S/2)^{2}(1 + (3EP S/10) + (EP S^{2}/20))((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|)

⊕ (|x.im ⊗ y.re| ⊕ |x.re ⊗ y.im|))/nrm

+ (1 + 101EP S)(1 + EP S/2)(x.e × (|y.re| ⊕ |y.im|)

+ (|x.re| ⊕ |x.im|) × y.e)/((\frac{1}{(1 + EP S/2)})^{2}nrm)

≤ (5EP S/2)(1 + EP S/2)^{3}((|x.re ⊗ y.re| ⊕ |x.im ⊗ y.im|)

⊕ (|x.im ⊗ y.re| ⊕ |x.re ⊗ y.im|))/nrm

+ (1 + 101EP S)(1 + EP S/2)^{3}(1 + EP S/2)^{2}(x.e ⊗ (|y.re| ⊕ |y.im|)
⊕ (|x.re| ⊕ |x.im|) ⊗ y.e)/nrm
= (1 + EP S/2)^{3}((5EP S/2)(A) + (1 + 101EP S)(1 + EP S/2)^{2}(B))/nrm
(1 + EP S/2)^{3}((5EP S/2)A + (1 + 103EP S)B)/nrm
(1 + EP S/2)^{6}(((5EP S/2) ⊗ A ⊕ (1 + 103EP S) ⊗ B) ⊘ nrm)
(1 + 4EP S) ⊗ (((5EP S/2) ⊗ A ⊕ (1 + 103EP S) ⊗ B) ⊘ nrm)

Here we have used the fact that

(1 + EP S/2)^{2}(1 + (3EP S/10) + (EP S^{2}/20)) ≤ (1 + (EP S/2)^{3})

Proposition 7.14 (\sqrt{X}):

Let s_{o} = ^{o} \sqrt{(|x.re| ⊕ h_{o}(x.re, x.im)) ⊗ 0.5} and d_{o} = (x.im ⊘ s) ⊗ 0.5, then \sqrt{x} = (re, im; e) where

re = s_{o} if x.re > 0.0 and re = d_{o} otherwise, im = d_{o} if x.re > 0.0 and im = s_{o} otherwise, e = EP S ⊗ ((1 + 4EP S) ⊗ (1.25 ⊗ s_{o} ⊕ 1.75 ⊗ |d_{o}|))

Proof: This will be a little nasty. Let’s begin by analyzing e_{s}, which is the difference between

the true calculation of s and the machine calculation of s, that is e_{s} = |s − s_{o}|. First, we bound s.

s = \sqrt{(|x.re| + h(x.re, x.im)) ∗ 0.5}
≤ (1 + EP S)^{1/2}\sqrt{(|x.re| + h_{o}(x.re, x.im)) ∗ 0.5}
≤ (1 + EP S)^{1/2}(1 + EP S/2)^{1/2}\sqrt{(|x.re| ⊕ h_{o}(x.re, x.im)) ∗ 0.5}

≤ (1 + EP S)^{1/2}(1 + EP S/2)^{1/2}(1 + EP S/2) ^{o} \sqrt{(|x.re| ⊕ h_{o}(x.re, x.im)) ∗ 0.5}

= (1 + EP S)^{1/2}(1 + EP S/2)^{3/2}s_{o}

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

By a power series expansion, we see that

(1 + EP S)^{1/2}(1 + EP S/2)^{3/2}

= (1 + \frac{1}{2}EP S − \frac{1}{8}EP S^{2} + ...) + (1 + \frac{3}{2}EP S/2 + \frac{3}{8}(EP S/2)^{2} + ...)

= (1 + \frac{1}{2}EP S − \frac{1}{8}EP S^{2} + ...) + (1 + \frac{3}{4}EP S + \frac{3}{32}(EP S)^{2} + ...)

= (1 + \frac{5}{4}EP S + \frac{11}{32}EP S^{2} + ...)

So that,

s ≤ (1 + \frac{5}{4}EP S + \frac{11}{32}EP S^{2} + ...)s_{o}

Similarly,

s ≥ (1 − \frac{5}{4}EP S)s_{o}

Thus, we can bound the s error,

e_{s} = |s − s_{o}|

≤ ((1 + \frac{5}{4}EP S + \frac{11}{32}EP S^{2} + ...) − 1)s_{o}

= (\frac{5}{4}EP S + \frac{11}{32}EP S^{2} + ...)s_{o}

Next, we analyze e_{d}, which is the absolute value of the difference between the true calculation of d and the machine calculation of d. That is, e_{d} = |d − d_{o}|.

e_{d} = |x.im/(2s) − x.im ⊘ (2s_{o})|

≤ |x.im ⊘ (2s_{o}) − x.im/(2s_{o})| + |x.im/(2s_{o}) − x.im/(2s)|

≤ (EP S/2)|x.im/(2s_{o})| + |\frac{x.im}{2} \frac{s − s_{o}}{ss_{o}} |

≤ (EP S/2)|x.im/(2s_{o})| + |\frac{x.im}{2} \frac{1}{ss_{o}} ((5/4)EP S + (11/32)EP S^{2} + ...)s_{o}|

≤ (EP S/2)|x.im/(2s_{o})| + |\frac{x.im}{2} \frac{1}{s}((5/4)EP S + (11/32)EP S^{2} + ...)|

≤ (EP S/2)|x.im/(2s_{o})| + |\frac{x.im}{2} \frac{1}{s_{o}(1 − (5/4)EP S)}((5/4)EP S + (11/32)EP S^{2} + ...)|

= (EP S/2)|x.im/(2s_{o})|(1 + \frac{(5/2) + (11/16)EP S + ...)}{(1 − (5/4)EP S)})

HOMOTOPY HYPERBOLIC 3-MANIFOLDS ARE HYPERBOLIC

= (EP S/2)\frac{(7/2) + (−9/16)EP S + ...}{(1 − (5/4)EP S)}|x.im/(2s_{o})|

≤ (EP S/2)(1 + EP S/2)\frac{7/2}{(1 − (5/4)EP S)}|x.im ⊘ (2s_{o})|

= (EP S/2)(1 + EP S/2)\frac{7/2}{(1 − (5/4)EP S)}|d_{o}|

Finally, we can bound the overall error e = e_{s} + e_{d}.

e_{s} + e_{d}

≤ (\frac{5}{4}EP S + \frac{11}{32}EP S^{2} + ...)s_{o} + (EP S/2)(1 + EP S/2)\frac{7/2}{(1 − (5/4)EP S)}|d_{o}|

≤ (EP S + \frac{11}{40}EP S^{2} + ...)(\frac{5}{4}s_{o}) + EP S(1 + EP S/2)\frac{1}{(1 − (5/4)EP S)}|\frac{7}{4}d_{o}|

≤ EP S(1 + EP S/2)\frac{1}{(1 − (5/4)EP S)}(\frac{5}{4}s_{o}) + EP S(1 + EP S/2)\frac{1}{(1 − (5/4)EP S)}|\frac{7}{4}d_{o}|

≤ EP S(1 + EP S/2)\frac{1}{(1 − (5/4)EP S)}(\frac{5}{4}s_{o} + |\frac{7}{4}d_{o}|)

≤ EP S(1 + EP S/2)^{3} \frac{1}{(1 − (5/4)EP S)}(\frac{5}{4} ⊗ s_{o} ⊕ |\frac{7}{4} ⊗ d_{o}|)

≤ EP S(1 − (EP S/2))(1 + 4EP S)(\frac{5}{4} ⊗ s_{o} ⊕ |\frac{7}{4} ⊗ d_{o}|)

≤ EP S ⊗ ((1 + 4EP S) ⊗ (\frac{5}{4} ⊗ s_{o} ⊕ |\frac{7}{4} ⊗ d_{o}|))

Finally, we develop a couple of formulas for the absolute value of an XComplex. Formula 7.0 (absUB(X)):

If x is an XComplex, then we get an upper bound on the absolute value of x as follows.

|x| = h(x.re, x.im) ≤ (1 + EP S)h_{∘}(x.re, x.im)

≤ (1 − EP S/2)(1 + 2EP S)h_{∘}(x.re, x.im)
≤ (1 + 2EP S) ⊗ h_{∘}(x.re, x.im)

Thus, we define

absUB(x) = (1 + 2EP S) ⊗ h_{∘}(x.re, x.im)

Formula 7.1 (absLB(X)):

If x is an XComplex, then we get a lower bound on the absolute value of x as follows.

|x| = h(x.re, x.im) ≥ (1 − EP S)h_{∘}(x.re, x.im)
≥ (1 + EP S/2)(1 − 2EP S)h_{∘}(x.re, x.im)
≥ (1 − 2EP S) ⊗ h_{∘}(x.re, x.im)

Thus, we define

absLB(x) = (1 − 2EP S) ⊗ h_{∘}(x.re, x.im)

Finally, in several places in the programs verify and fudging we perform a standard operation on a pair of doubles and must take into account round-off error. This is easy if we use Lemma 7.0.

For example, in inequalityHolds we want to show that wh×wh > absUB(along), where wh = absLB(whirle). By Lemma 7.0, we know that (1 − EP S) ⊗ (wh ⊗ wh) ≤ wh × wh and we simply test that (1 − EP S) ⊗ (wh ⊗ wh) ≥ absUB(along).

Similar situations occur in the functions horizon and larger-angle in fudging.

A slightly more complicated version of this occurs in the computer calculation of pos[i] and size[i], that is, the center and size of a sub-box. Prior to multiplication by scale[i] = 2^{(5−i)/6}, the calculations of pos and size are exact. However, multiplication by scale introduces round-off error. For the center of the box we will have the computer use pos[i] ⊗ scale[i] with the realization that this is not necessarily pos[i] × scale[i]. Thus, we have to choose appropriate sizes to ensure that the machine sub-box contains the true sub-box.

Notationally, this is annoying, because we typically use a computer command like pos[i] = pos[i] ⊗ scale[i], while in an exposition, we need to avoid that. We will denote the true center of the box by p[i] and the machine center of the box by p_{0}[i], and the true and machine sizes will be denoted s[i] and s_{0}[i]. We will let pos[i] and size[i] be the position and size (true and machine are the same) before multiplication by scale[i].

Let p[i] = pos[i] × scale[i], p_{0}[i] = pos[i] ⊗ scale[i], and s[i] = size[i] × scale[i]. We must select s_{0}[i] so that p_{0}[i] + s_{0}[i] ≥ p[i] + s[i]. (Here, taking + on the left-hand side is correct, because the need for machine calculation there is incorporated at other points in the programs.) So, we must find s_{0}[i] such that s_{0}[i] ≥ (p[i] − p_{0}[i]) + s[i].

(p[i] − p_{0}[i]) + s[i]. ≤ (EP S/2)|p_{0}[i]| + size[i] × scale[i]
≤ (EP S/2)|p_{0}[i]| + (1 + EP S/2)(size[i] ⊗ scale[i])
≤ (1 + EP S/2)((EP S/2)|p_{0}[i]| + (size[i] ⊗ scale[i]))
≤ (1 + EP S/2)^{2}((EP S/2)|p_{0}[i]| ⊕ (size[i] ⊗ scale[i]))
≤ (1 + 2EP S) ⊗ ((EP S/2)|p_{0}[i]| ⊕ (size[i] ⊗ scale[i]))

Thus we take

s_{0}[i] = (1 + 2EP S) ⊗ ((EP S/2)|p_{0}[i]| ⊕ (size[i] ⊗ scale[i]))

This also works to give p_{0}[i] − s_{0}[i] ≤ p[i] − s[i].

Chapter 8: AffApprox’s with Round-Off Error

In Chapter 6, we saw how to do calculations with AffApprox’s. In this chapter, we incorporate round-off error into these calculations.

Convention 8.1: Recall that an AffApprox x is a five-tuple (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) consisting of four complex numbers (x.f, x.f_{0}, x.f_{1}, x.f_{2}) and one real number x.err. In Chapter 6, the real number was denoted x.e, but it seems preferable to use x.err in this Chapter. Also, we will suppress mention of the r functions used in Chapter 6 (see Definition 6.4). As such, statements in this section will have to be translated (implicitly) to account for this suppression.

Remark 8.2: One approach to round-off error for AffApprox’s would be to replace the four complex numbers by four AComplex numbers complete with their round-off errors, and similarly for the one real number. We will not do this because it would necessitate keeping track of five separate round-off-error terms when we do AffApprox calculations.

Instead, we will replace the four complex numbers by four XComplex numbers (“exact” complex numbers) and push all the round-off error into the .err term. In particular, in doing an AffApprox calculation, our subsidiary calculations will generally be on XComplex numbers and produce an AComplex number whose .e term will be plucked off and forced into the .err term of the final AffApprox.

Convention 8.3: In what follows, we will use Basic Properties 7.0 and Lemmas 7.0 and 7.1. Also, the Propositions in Chapter 6 will be utilized; as such, the numbering of the Propositions is the same in both Chapters (for example, Propositon 6.7 corresponds to Proposition 8.7).

-X:

Proposition 8.1: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err), then

−x = (−x.f; −x.f_{0}, −x.f_{1}, −x.f_{2}; x.err)

X + Y:

We analyze the addition of the AffApproxs x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y = (y.f; y.f_{0}, y.f_{1}, y.f_{2}; y.err). To get the first term in x + y we add the XComplex numbers x.f and y.f; which produces the AComplex number r f = x.f + y.f, and then we pluck off the XComplex part, r f.z. The round-off error part r f.e will be foisted into the overall error term r error for x + y. Similarly for the next three terms in x + y.

Abstractly, the overall error term r error comes from adding the round-off error contributions r f.e, r f_{0}.e, r f_{1}.e, r f_{2}.e and the AffApprox error contributions x.err, y.err. Of course, we have to produce a machine version.

Proposition 8.2: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y = (y.f; y.f_{0}, y.f_{1}, y.f_{2}; y.err), then

x + y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

where

r error = (1 + 3EP S) ⊗ ((x.e ⊕ y.e) ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))

Proof: The error is given by

(x.e + y.e) + ((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))

≤ (1 + EP S/2)(x.e ⊕ y.e) + (1 + EP S/2)((r f.e ⊕ r f_{0}.e) + (r f_{1}.e ⊕ r f_{2}.e))
≤ (1 + EP S/2)^{2}(x.e ⊕ y.e) + (1 + EP S/2)^{2}((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e))
≤ (1 + EP S/2)^{3}((x.e ⊕ y.e) ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))
≤ (1 + 3EP S) ⊗ ((x.e ⊕ y.e) ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))

To get the last line we used Lemma 1 in Section 5. X - Y: Proposition 8.3: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y = (y.f; y.f_{0}, y.f_{1}, y.f_{2}; y.err), then

x − y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x.f − y.f
r f_{k} = x.f_{k} − y.f_{k}
r error = (1 + 3EP S) ⊗ ((x.e ⊕ y.e) ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))

X + D

Here, we add the AffApprox x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) to the double y. The only terms that change are the first and the last. Proposition 8.4: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y is a double, then

x + y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x.f + y
r f_{k} = x.f_{k}
r error = (1 + EP S) ⊗ (x.err ⊕ r f.e)

Proof: The error is given by

x.err + r f.e

HOMOTOPY HYPERBOLIC 3-MANIFOLDS ARE HYPERBOLIC

≤ (1 + EP S) ⊗ (x.err ⊕ r f.e)

by Lemma 0 in Section 5. X - D Proposition 8.5: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y is a double, then

x − y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x.f − y
r f_{k} = x.f_{k}
r f.z = x.f − y
r error = (1 + EP S) ⊗ (x.err ⊕ r f.e)

X * Y We multiply the AffApproxs x, y while pushing all error into the .err term. We will use the functions (see Formulas 7.0 and 7.1, at the end of Chapter 7) absUB =

(1 + 2EP S) ⊗ hypot_{o}(x.re, x.im) and absLB(x) = (1 − 2EP S) ⊗ hypot_{o}(x.re, x.im). When x is an AffApprox, we define dist(x) to be

(1 + 2EP S) ⊗ (absUB(x.f_{0}) ⊕ (absUB(x.f_{1}) ⊕ absUB(x.f_{2}))).

This is the machine representation of the sum of the absolute values of the linear terms in the AffApprox x (the proof is straightforward). Proposition 8.6: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y = (y.f; y.f_{0}, y.f_{1}, y.f_{2}; y.err), then

x ∗ y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x.f × y.f
r f_{k} = x.f × y.f_{k} + x.f_{k} × y.f
Then, x × y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error), where
r error = (1 + 3EP S) ⊗ (A ⊕ (B ⊕ C))

with

A = (dist(x) ⊕ x.e) ⊗ (dist(y) ⊕ y.e)
B = absUB(x.f) ⊗ y.e ⊕ absUB(y.f) ⊗ x.e

C = (r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)

Proof: We add the non-round-off error term for x × y to the various round-off error terms that accumulated.

((dist(x) + x.e) × (dist(y) + y.e)) + ((absUB(x.f) × y.e + absUB(y.f) × x.e) + (r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))

≤ (1 + EP S/2)^{2}[(dist(x) ⊕ x.e) × (dist(y) ⊕ y.e)] + (1 + EP S/2)(absUB(x.f) ⊗ y.e + absUB(y.f) ⊗ x.e) + (1 + EP S/2)((r f.e ⊕ r f_{0}.e) + (r f_{1}.e ⊕ r f_{2}.e))

≤ (1 + EP S/2)^{3}[(dist(x) ⊕ x.e) ⊗ (dist(y) ⊕ y.e)] + (1 + EP S/2)^{2}{(absUB(x.f) ⊗ y.e ⊕ absUB(y.f) ⊗ x.e) + ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e))}

≤ (1 + EP S/2)^{3}A + (1 + EP S/2)^{2}(B + C)
≤ (1 + EP S/2)^{3}A + (1 + EP S/2)^{3}(B + C)
≤ (1 + EP S/2)^{4}(A ⊕ (B + C))
≤ (1 + 3EP S) ⊗ (A ⊕ (B + C))

X * D:

Proposition 8.7: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y is a double, then

x × y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x.f × y
r f_{k} = x.f_{k} × y
r error = (1 + 3EP S) ⊗ ((x.e ⊗ |y|) ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))

Proof:

(x.e × |y|) + ((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))
≤ (1 + EP S/2)(x.e ⊗ |y|) + (1 + EP S/2)((r f.e ⊕ r f_{0}.e) + (r f_{1}.e ⊕ r f_{2}.e))
≤ (1 + EP S/2)^{2}(x.e ⊗ |y|) + (1 + EP S/2)^{2}((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e))
≤ (1 + EP S/2)^{3}((x.e ⊗ |y|) ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))
≤ (1 + 3EP S) ⊗ ((x.e ⊗ |y|) ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))

X/Y:

For convenience, let ax = absUB(x.f), ay = absLB(y.f).

Proposition 8.8: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y = (y.f; y.f_{0}, y.f_{1}, y.f_{2}; y.err), then

x/y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x.f/y.f
r f_{k} = (x.f_{k} × y.f − x.f × y.f_{k})/(y.f × y.f)
r.error = (1 + 3EP S) ⊗ (((1 + 3EP S) ⊗ A ⊖ (1 − 3EP S) ⊗ B) ⊕ C)

with

A = (ax ⊕ (dist(x) ⊕ x.e)) ⊘ D
B = (ax ⊘ ay ⊕ dist(x) ⊘ ay) ⊕ ((dist(y) ⊗ ax) ⊘ (ay ⊗ ay))
C = (r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)
D = ay ⊖ (1 + EP S) ⊗ (dist(y) ⊕ y.e)

Of course, we do have to be concerned about division by zero, so the program will complain if ay is not greater than (1 + EP S) ⊗ (dist(y) ⊕ y.e), that is, if D is not greater than zero.

Proof:

As usual, we add the round-off errors to the old AffApprox error, taking into account round-off error. Let’s work on it bit by bit.

(ax + dist(x) + x.e)/(ay − (dist(y) + y.e))
≤ (ax + (1 + EP S/2)(dist(x) ⊕ x.e))/(ay − (1 + EP S) ⊗ (dist(y) ⊕ y.e))
≤ (1 + EP S/2)^{2}(ax ⊕ (dist(x) ⊕ x.e))/(ay − (1 + EP S) ⊗ (dist(y) ⊕ y.e))

≤ (1 + EP S/2)^{2}(ax ⊕ (dist(x) ⊕ x.e))/(\frac{1}{1 + EP S/2})(ay ⊖ (1 + EP S) ⊗ (dist(y) ⊕ y.e))

≤ (1 + EP S/2)4(ax ⊕ (dist(x) ⊕ x.e)) ⊘ (ay ⊖ (1 + EP S) ⊗ (dist(y) ⊕ y.e))

= (1 + EP S/2)^{4}A
≤ (1 + 3EP S) ⊗ A

The next term, being subtracted, requires opposite inequalities.

(ax/ay + dist(x)/ay) + dist(y) × ax/(ay × ay)

≥ (1−EP S/2)(ax⊘ay +dist(x)⊘ay)+(1−EP S/2)(dist(y)⊗ax)/(\frac{1}{1 − EP S/2})(ay ⊗ay)

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

≥ ((1 − EP S/2)^{2}(ax ⊘ ay ⊕ dist(x) ⊘ ay) + (1 − EP S/2)^{3}(dist(y) ⊗ ax) ⊘ (ay ⊗ ay) ≥ (1 − EP S/2)^{3}[(ax ⊘ ay ⊕ dist(x) ⊘ ay) + (dist(y) ⊗ ax) ⊘ (ay ⊗ ay)) ≥ ((1 − EP S/2)^{4}((ax ⊘ ay ⊕ dist(x) ⊘ ay) ⊕ ((dist(y) ⊗ ax) ⊘ (ay ⊗ ay)))

≥ (1 + EP S/2)(1 + 3EP S)(B)
≥ (1 − 3EP S) ⊗ B

Finally, we do the round-off terms.

((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))

≤ (1 + EP S/2)((r f.e ⊕ r f_{0}.e) + (r f_{1}.e ⊕ r f_{2}.e))
≤ (1 + EP S/2)^{2}((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e))
= (1 + EP S/2)^{2}C

Now, we put these three pieces together.

(ax + dist(x) + x.e)/(ay − (dist(y) + y.e)) − ((ax/ay + dist(x)/ay) + dist(y) × ax/(ay × ay)) + ((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))

≤ (1 + 3EP S) ⊗ A − (1 − 3EP S) ⊗ B + (1 + EP S/2)^{2}C

≤ (1 + EP S/2)((1 + 3EP S) ⊗ A ⊖ (1 − 3EP S) ⊗ B) + (1 + EP S/2)^{2}C
≤ (1 + EP S/2)^{2}(((1 + 3EP S) ⊗ A ⊖ (1 − 3EP S) ⊗ B) + C)
≤ (1 + EP S/2)^{3}(((1 + 3EP S) ⊗ A ⊖ (1 − 3EP S) ⊗ B) ⊕ C)
≤ (1 + 3EP S) ⊗ (((1 + 3EP S) ⊗ A ⊖ (1 − 3EP S) ⊗ B) ⊕ C)

D/X:

We are dividing a double x by an AffApprox y. For convenience, let ax = |x|, ay = absLB(y.f). Proposition 8.9: If x is a double, and y = (y.f; y.f_{0}, y.f_{1}, y.f_{2}; y.err), then

x/y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x/y.f
r f_{k} = −(x × y.f_{k})/(y.f × y.f)
r error = (1 + 3EP S) ⊗ (((1 + 2EP S) ⊗ (ax ⊘ D) ⊖ (1 − 3EP S) ⊗ B) ⊕ C)

B = ax ⊘ ay ⊕ (dist(y) ⊗ ax ⊘ (ay ⊗ ay))
C = (r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)
D = ay ⊖ (1 + EP S) ⊗ (dist(y) ⊕ y.e)

Again, we have to be concerned about division by zero, so the program will complain if ay is not greater than (1 + EP S) ⊗ (dist(y) ⊕ y.e), that is if D is not greater than zero.

Proof:

Let’s start with the pieces.

ax/(ay − (dist(y) + y.e))
≤ ax/(ay − (1 + EP S) ⊗ (dist(y) ⊕ y.e))

≤ ax/(\frac{1}{1 + EP S/2})(ay ⊖ (1 + EP S) ⊗ (dist(y) ⊕ y.e))

≤ (1 + EP S/2)^{2}ax ⊘ D
≤ (1 + 2EP S) ⊗ (ax ⊘ D)

The next term, being subtracted, requires opposite inequalities.

ax/ay + dist(y) × ax/(ay × ay)

≥ (1 − EP S/2)ax ⊘ ay + (1 − EP S/2)dist(y) ⊗ ax/(\frac{1}{1 − EP S/2})(ay ⊗ ay)

≥ (1 − EP S/2)ax ⊘ ay + (1 − EP S/2)^{3}dist(y) ⊗ ax ⊘ (ay ⊗ ay)
≥ (1 − EP S/2)^{3}(ax ⊘ ay + dist(y) ⊗ ax ⊘ (ay ⊗ ay))
≥ (1 − EP S/2)^{4}[ax ⊘ ay ⊕ (dist(y) ⊗ ax ⊘ (ay ⊗ ay))]
≥ (1 + EP S/2)(1 − 3EP S)B
≥ (1 − 3EP S) ⊗ B

Finally, we do the round-off terms as before.

((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))
≤ (1 + EP S/2)^{2}C

Putting the pieces together, we have:

≤ ax/(ay − (dist(y) + y.e)) − (ax/ay + dist(y) × ax/(ay × ay)) + ((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))

≤ (1 + 2EP S) ⊗ (ax ⊘ D) − (1 − 3EP S) ⊗ B + (1 + EP S/2)^{2}C

DAVID GABAI, G. ROBERT MEYERHOFF, AND NATHANIEL THURSTON

≤ (1 + EP S/2)((1 + 2EP S) ⊗ (ax ⊘ D) ⊖ (1 − 3EP S) ⊗ B) + (1 + EP S/2)^{2}C

≤ (1 + EP S/2)^{2}(((1 + 2EP S) ⊗ (ax ⊘ D) ⊖ (1 − 3EP S) ⊗ B) + C) ≤ (1 + EP S/2)^{3}(((1 + 2EP S) ⊗ (ax ⊘ D) ⊖ (1 − 3EP S) ⊗ B) ⊕ C) ≤ (1 + 3EP S) ⊗ (((1 + 2EP S) ⊗ (ax ⊘ D) ⊖ (1 − 3EP S) ⊗ B) ⊕ C)

X/D:

We are dividing an AffApprox x by a double y and the computer will object if y = 0. Proposition 8.10: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and y is a double, then

x/y = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = x.f/y
r f_{k} = x.f_{k}/y
r error = (1 + 3EP S) ⊗ ((x.e ⊘ |y|) ⊕ [(r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)])

Proof:

This is easy.

x.e/|y| + ((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))

≤ (1 + EP S/2)x.e ⊘ |y| + (1 + EP S/2)^{2}[(r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)]

≤ (1 + EP S/2)^{2}(x.e ⊘ |y| + [(r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)])
≤ (1 + EP S/2)^{3}(x.e ⊘ |y| ⊕ [(r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)])
≤ (1 + 3EP S) ⊗ (x.e ⊘ |y| ⊕ [(r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)])

\sqrt{X} :

Here, x is an AffApprox and we let ax = absUB(x.f). There are two cases to consider depending on whether or not D = ax ⊖ (1 + EP S) ⊗ (dist(x) ⊕ x.e) is or is not greater than zero. Proposition 8.11a: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and D is not greater than zero, then we use the crude over-estimate \sqrt{x} = (0; 0, 0, 0; (1+2EP S)⊗ ^{o} \sqrt{(ax ⊕ (xdist ⊕ x.e))} ) Proof:

\sqrt{ax + xdist + x.e}
≤ \sqrt{ax + (1 + EP S/2)(xdist ⊕ x.e)}

≤ \sqrt{(1 + EP S/2)^{2}(ax ⊕ (xdist ⊕ x.e))}
= (1 + EP S/2)\sqrt{(ax ⊕ (xdist ⊕ x.e))}
≤ (1 + EP S/2)^{2} ^{o} \sqrt{(ax ⊕ (xdist ⊕ x.e))}
≤ (1 + 2EP S) ⊗ ^{o} \sqrt{(ax ⊕ (xdist ⊕ x.e))}

Proposition 8.11b: If x = (x.f; x.f_{0}, x.f_{1}, x.f_{2}; x.err) and D is greater than zero, then,

\sqrt{x} = (r f.z; r f_{0}.z, r f_{1}.z, r f_{2}.z; r error)

where

r f = \sqrt{x.f}
t = r f + r f
r f_{k} = AComplex(x.f_{k}.re, x.f_{k}.im, 0)/t

(Simply put, r f_{k} = x.f_{k}/(2\sqrt{x.f}). The reason we have to fuss to define r f_{k} is because \sqrt{x.f} is an AComplex.)

r error = (1 + 3EP S) ⊗ (

\{(1 + EP S) ⊗ ^{o} \sqrt{ax}
⊖ (1 − 3EP S) ⊗ [dist(x) ⊘ (2 × ^{o} \sqrt{ax}) ⊕ ^{o} \sqrt{D} ]\}
⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e))

)

Proof:

Let’s work on the pieces.

\sqrt{ax} ≤ (1 + EP S) ⊗ ^{o} \sqrt{ax}

Next,

dist(x)/(2\sqrt{ax}) + \sqrt{ax − (dist(x) + x.e)}
≥ (1 − EP S/2)^{2}dist(x) ⊘ (2 ^{o} \sqrt{ax}) + \sqrt{ax − (1 + EP S) ⊗ (dist(x) ⊕ x.e)}

≥ (1 − EP S/2)^{2}dist(x) ⊘ (2 ^{o} \sqrt{ax})

+ (1 − EP S/2)^{1/2}\sqrt{ax ⊖ (1 + EP S) ⊗ (dist(x) ⊕ x.e)}

≥ (1 − EP S/2)^{2}dist(x) ⊘ (2 ^{o} \sqrt{ax}) + (1 − EP S/2)^{3/2} ^{o} \sqrt{D}
≥ (1 − EP S/2)^{2}[dist(x) ⊘ (2 ^{o} \sqrt{ax}) + ^{o} \sqrt{D} ]
≥ (1 − EP S/2)^{3}[dist(x) ⊘ (2 ^{o} \sqrt{ax}) ⊕ ^{o} \sqrt{D} ]

≥ (1 + EP S/2)(1 − 3EP S)[dist(x) ⊘ (2 ^{o} \sqrt{ax}) ⊕ ^{o} \sqrt{D} ]
≥ (1 − 3EP S) ⊗ [dist(x) ⊘ (2 ^{o} \sqrt{ax}) ⊕ ^{o} \sqrt{D} ]

Adding in the usual term, we get as our error bound

\sqrt{ax} − (dist(x)/(2\sqrt{ax}) + \sqrt{ax − (dist(x) + x.e)} ) + ((r f.e + r f_{0}.e) + (r f_{1}.e + r f_{2}.e))

≤ (1 + EP S) ⊗ ^{o} \sqrt{ax}

− (1 − 3EP S) ⊗ [dist(x) ⊘ (2 ^{o} \sqrt{ax}) ⊕ ^{o} \sqrt{D} ]
+ (1 + EP S/2)^{2}((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e))

≤ (1 + EP S/2)\{(1 + EP S) ⊗ ^{o} \sqrt{ax}

⊖ (1 − 3EP S) ⊗ [dist(x) ⊘ (2 ^{o} \sqrt{ax}) ⊕ ^{o} \sqrt{D} ]\}

+ (1 + EP S/2)^{2}((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e))

≤ (1 + EP S/2)^{3}(\{(1 + EP S) ⊗ ^{o} \sqrt{ax}

⊖ (1 − 3EP S) ⊗ [dist(x) ⊘ (2 ^{o} \sqrt{ax}) ⊕ ^{o} \sqrt{D} ]\}
⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))

≤ (1 + 3EP S) ⊗ (\{(1 + EP S) ⊗ ^{o} \sqrt{ax} ⊖ (1 − 3EP S) ⊗ [dist(x) ⊘ (2 ^{o} \sqrt{ax})

⊕ ^{o} \sqrt{D} ]\} ⊕ ((r f.e ⊕ r f_{0}.e) ⊕ (r f_{1}.e ⊕ r f_{2}.e)))

References

[B] A. Beardon, The Geometry of Discrete Groups, Graduate Texts in mathematics 91, Springer-Verlag, New York, 1983.

[Be] J. Berge, Heegaard, a program to understand Heegaard splittings of 3-manifolds, available free from the author.

[F] W. Fenchel, Elementary Geometry in Hyperbolic Space, de Gruyter Studies Math., 11, de Gruyter, Berlin (1989).

[G] D. Gabai, On the Geometric and Topological Rigidity of Hyperbolic 3-Manifolds, to appear, J. Amer. Math. Soc.

[GM1] F. Gehring and G. Martin, Inequalities of Möbius Transformations and Discrete Groups, j. Reine Agnew. math. 418 (1991) 31 - 76.

HOMOTOPY HYPERBOLIC 3-MANIFOLDS ARE HYPERBOLIC

[GM2] F. Gehring and G. Martin, Precisely invariant collars and the volume of hyperbolic 3-folds, preprint.

[HW1] C. Hodgson and J. Weeks, personal communication.

[HW2] C. Hodgson and J. Weeks, Symmetries, Isometries and Length Spectra of Closed Hyperbolic 3-Manifolds, Exp. Math. 3 (1994), 261-274.

[JR] K. Jones and A. Reid,

[K] W. Kahane, Interval Arithmetic Options in the Proposed IEEE Floating Point Arithmetic Standard; Interval Mathematics 1980, Ed. Karl L. E. Nickel, 99-128.

[Math] Mathematica 2.0, A system for doing mathematics by computer, Wolfram Research Inc., Champaign Il.

[M1] G. R. Meyerhoff, A Lower Bound for the Volume of Hyperbolic 3-Manifolds, Canadian J. Math. 39 (1987) 1038-1056.

[M2] G. R. Meyerhoff, Sphere-Packing and Volume in Hyperbolic 3-Space, Comment. Math. Helvetici 61 (1986) 271-278.

[Mo] G. D. Mostow, Quasi-Conformal Mappings in n-Space and the Rigidity of Hyperbolic Space Forms, IHES Publ. Math. 34 (1968) 53-104.

[T] N. Thurston, Finding Killer Words, in preparation.

[Wa] F. Waldhausen, On Irreducible 3-Manifolds which Are Sufficiently Large, Annals of Math. 87 (1968) 56-88.

[W] J. Weeks, SNAPPEA, available from the Geometry Center, geom.umn.edu.