SOLUTION OF THE PROPELLER CONJECTURE IN ℝ^{3}

STEVEN HEILMAN, AUKOSH JAGANNATH, AND ASSAF NAOR

Abstract. It is shown that every measurable partition {A_{1}, …, A_{k}} of ℝ^{3} satisfies

∑_{i=1}^{k} ∥∫_{A_{i}} xe^{− \frac{1}{2} ∥x∥_{2}^{2}}dx∥_{2}^{2} ⩽ 9π^{2}.  (1)

Let {P_{1}, P_{2}, P_{3}} be the partition of ℝ^{2} into 120^{∘} sectors centered at the origin. The bound (1) is sharp, with equality holding if A_{i} = P_{i} × ℝ for i ∈ {1, 2, 3} and A_{i} = ∅ for i ∈ {4, …, k} (up to measure zero corrections, orthogonal transformations and renumbering of the sets {A_{1}, …, A_{k}}). This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor (FOCS 2008). The proof of (1) reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of (1) is complexity-theoretic: the Unique Games hardness threshold of the Kernel Clustering problem with 4 × 4 centered and spherical hypothesis matrix equals \frac{2π}{3} .

Figure 1. The partition of ℝ^{3} that maximizes the sum of squared lengths of Gaussian moments is a “propeller”: three planar 120^{∘} sectors multiplied by an orthogonal line, with the rest of the partition elements being empty.

S. H. and A. J. were supported by NSF grant CCF-0832795 and NSF Graduate Research Fellowship DGE-0813964. A. N. was supported by NSF grant CCF-0832795, BSF grant 2006009, and the Packard Foundation. Part of this work was carried out when S. H. and A. N. were visiting the Quantitative Geometry program at MSRI.

1. Introduction

For x = (x_{1}, …, x_{m}), y = (y_{1}, …, y_{m}) ∈ ℝ^{m} let ⟨x, y⟩ = ∑_{i=1}^{m} x_{i}y_{i} denote their standard scalar product, and let ∥x∥_{2} = \sqrt{⟨x, x⟩} denote the corresponding Euclidean norm. The cross product of x = (x_{1}, x_{2}, x_{3}), y = (y_{1}, y_{2}, y_{3}) ∈ ℝ^{3} is denoted x×y = (x_{2}y_{3} −x_{3}y_{2}, x_{3}y_{1} −x_{1}y_{3}, x_{1}y_{2} −x_{2}y_{1}). The Gaussian measure on ℝ^{m}, i.e., the measure whose density is x ↦ (2π)^{−m/2}e^{−∥x∥_{2}^{2}/2}, is denoted γ_{m}.

The following theorem is our main result, asserting that among all measurable partitions of ℝ^{3}, the “propeller partition” as depicted in Figure 1 maximizes the sum of the squared lengths of the Gaussian moments associated to the members of the partition.

Theorem 1.1 (Main theorem; geometric formulation). Let {A_{1}, …, A_{k}} be a partition of ℝ^{3} into Lebesgue measurable sets. For i ∈ {1, …, k} let ζ_{i} = ∫_{A_{i}} xdγ_{3}(x) ∈ ℝ^{3} be the Gaussian moment of the set A_{i}. Then

∑_{i=1}^{k} ∥ζ_{i}∥_{2}^{2} ⩽ \frac{9}{8π} .  (2)

Let {P_{1}, P_{2}, P_{3}} be the partition of ℝ^{2} into 120^{∘} sectors centered at the origin. The bound (2) cannot be improved, with equality holding if A_{i} = P_{i}×ℝ for i ∈ {1, 2, 3} and A_{i} = ∅ for i ∈ {4, …, k} (up to measure zero corrections, orthogonal transformations, and renumbering of the sets {A_{1}, …, A_{k}}).

The Propeller Conjecture was posed by Khot and Naor in [23] as part of their investigation of the computational complexity of the Kernel Clustering problem from Machine Learning. Specifically, they conjectured the validity of the bound (2) for measurable partitions of ℝ^{m} for all m > 2. They proved this conjecture for m = 2, and for m = 1 they showed that the right hand side of (2) can be improved to the sharp bound \frac{1}{π}. It is also shown in [23] that proving (2) for k = 4 implies the same conclusion for all k ∈ ℕ. Correspondingly, for partitions of ℝ^{m} it suffices to prove this statement for k = m + 1.

Before explaining the complexity-theoretic consequence of Theorem 1.1, which was the motivation of [23] for posing the Propeller Conjecture, we state two equivalent formulations of it: the first probabilistic (a sharp estimate for the expected maximum of a Gaussian vector) and the second analytic (a sharp Grothendieck inequality). The equivalence of these results to Theorem 1.1 was established in [23]; for Theorem 1.2 below see [23, Lem. 3.7] and for Theorem 1.3 below see [23, Thm. 1.1].

Theorem 1.2 (Main theorem; probabilistic formulation). Let (g_{1}, g_{2}, g_{3}, g_{4}) ∈ ℝ^{4} be a mean zero Gaussian vector (with arbitrary covariance matrix). then

|𝔼 [ max_{i∈\{1,2,3,4\}} g_{i}]| ⩽ \frac{3}{2\sqrt{2π}} \sqrt{∑_{i=1}^{4} 𝔼 [g_{i}^{2}]}.  (3)

The bound (3) cannot be improved, with equality holding when the covariance matrix of (g_{1}, g_{2}, g_{3}, g_{4}) equals

\frac{1}{2} (\begin{matrix}2 & −1 & −1 & 0 \\ −1 & 2 & −1 & 0 \\ −1 & −1 & 2 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}) .

The following analytic formulation of Theorem 1.1 is in terms of a sharp Grothendieck inequality. Grothendieck [13] pioneered in 1953 the use of inequalities of this type in functional analysis, and ever since then such inequalities have permeated many mathematical disciplines. See [23, 24, 25] for an explanation of how the result below relates to a natural extension of the Grothendieck inequality and to approximation algorithms.

Theorem 1.3 (Main theorem; analytic formulation). Let (a_{ij}) be an n × n positive semidefinite matrix with ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} = 0. For every {v_{1}, v_{2}, v_{3}, v_{4}} ⊆ S^{3} with ∑_{i=1}^{4} v_{i} = 0 we have

max_{x_{1},...,x_{n}∈S^{n−1}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨x_{i}, x_{j}⟩ ⩽ \frac{2π}{3} max_{y_{1},...,y_{n}∈\{v_{1},v_{2},v_{3},v_{4}\}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨y_{i}, y_{j}⟩.  (4)

The bound (4) cannot be improved, with asymptotic equality holding when {v_{1}, v_{2}, v_{3}, v_{4}} are the rows of the following matrix.

\frac{1}{2\sqrt{3}} (\begin{matrix}3 & −1 & −1 & −1 \\ −1 & 3 & −1 & −1 \\ −1 & −1 & 3 & −1 \\ −1 & −1 & −1 & 3 \end{matrix}) .

See [24, Sec. 3.1] for a description of a family of n × n matrices (a_{ij}) for which equality in (4) is asymptotically attained (as n → ∞).

Inequality (4) was proved in [23]. Our new contribution is the assertion that (4) cannot be improved, a statement that is equivalent to inequality (2) of Theorem 1.1. This is not the first time that attempts to prove sharpness of a Grothendieck inequality led to an extremal geometric partitioning question. Notably, see König’s conjecture [27] as a step towards Krivine’s conjecture [29] on the sharpness of his version of the classical Grothendieck inequality. Unlike the Propeller Conjecture in ℝ^{3}, these conjectures turned out to be false [8], but they do indicate the interconnection between Grothendieck inequalities and extremal geometric partitioning problems.

The main consequence (and motivation) of Theorem 1.1 is complexity theoretic. To explain it we briefly recall Khot’s Unique Games Conjecture (UGC), which asserts that for every ε ∈ (0, 1) there exists a prime p = p(ε) ∈ ℕ such that no polynomial time algorithm can perform the following task. The input is a system of m linear equations in n variables x_{1}, …, x_{n}, each of which has the form x_{i} − x_{j} ≡ c_{ij} mod p. The algorithm must determine whether there exists an assignment of an integer value to each variable x_{i} such that at least (1 − ε)m of the equations are satisfied, or no assignment of such values can satisfy more than εm of the equations. If neither of these possibilities occurs, then an arbitrary output of the algorithm is allowed. The UGC was introduced by Khot in [20], though the above formulation of it, which is equivalent to the original one, is due to [22]. The use of the UGC as a hardness hypothesis has become popular over the past decade; we refer to Khot’s survey [21] for more information on this topic. Saying that the UGC hardness threshold of an optimization problem 𝒪 equals α ∈ [1, ∞) means that for every ε ∈ (0, 1) there exists a polynomial time algorithm that outputs a number that is guaranteed to be within a multiplicative factor of α + ε from the solution of 𝒪, and that the existence of such an algorithm with approximation guarantee of α − ε would contradict the UGC.

The Kernel Clustering problem is a clustering framework for covariance matrices that originated in the work of Borgwardt, Gretton, Smola and Song [36] in the context of Machine Learning. This problem is generic in the sense that it contains well-studied optimization problems as special cases, and its versatility allows one to design a variety of algorithms tailor-made for particular applications (many of these algorithms are at present shown [36] to be successful empirically, but not rigorously). The input of the Kernel Clustering problem is an n × n symmetric positive semidefinite matrix A = (a_{ij}) and a k × k symmetric positive semidefinite matrix B = (b_{ij}) called the hypothesis matrix. Think of n as very large and k as small, the goal being to cluster the entries of A into a k × k matrix that is most correlated with the hypothesis matrix B. Formally, given a partition {S_{1}, …, S_{k}} of {1, …, n}, form the associated clustered version of A by summing the entries of A over the blocks induced by the partition {S_{1}, …, S_{k}}. One thus obtains a k × k matrix C = (c_{ij}) given by c_{ij} = ∑_{(s,t)∈S_{i}×S_{j}} a_{st}. Let Clust(A|B) denote the maximum of ∑_{i=1}^{k} ∑_{j=1}^{k} c_{ij}b_{ij} over all partitions {S_{1}, …, S_{k}} of {1, …, n}. We refer to [36, 23, 24, 25] for further explanation of this clustering framework, as well as a discussion of important special cases arising from appropriate choices of the hypothesis matrix B.

In what follows, an n × n symmetric positive semidefinite matrix A = (a_{ij}) is called centered if ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} = 0, and it is called spherical if a_{ii} = 1 for all i ∈ {1, …, n}.

Theorem 1.4 (Main theorem; complexity theoretic formulation). Let 𝒪 be the following optimization problem. The input is an n × n symmetric positive semidefinite centered matrix A = (a_{ij}), and also a 4 × 4 symmetric centered and spherical positive semidefinite matrix B = (b_{ij}). The goal is to compute in polynomial time the quantity Clust(A|B). Then the UGC hardness threshold of 𝒪 equals \frac{2π}{3} .

A polynomial time algorithm with approximation ratio \frac{2π}{3} +o(1) for the problem 𝒪 of Theorem 1.4 was designed in [23]. The fact that Theorem 1.1 implies the matching UGC hardness result was also proved in [23]. More generally, it was shown in [23] that the validity of the m-dimensional Propeller Conjecture for some m ⩾ 3 would imply that the UGC hardness threshold of the variant of 𝒪 with B being an m × m matrix equals \frac{8π}{9} (1 − \frac{1}{m}).

This is not the first time that extremal problems in the measure space (ℝ^{m}, γ_{m}) arose from investigations in complexity theory; see for example the Majority is Stablest Conjecture of Khot, Kindler, Mossel and O’Donnell [22], which was solved by Mossel, O’Donnell, and Oleszkiewicz [33] via a reduction to a classical isoperimetric inequality of Borell [7]. A special feature of the Propeller Conjecture is that its conclusion is quite surprising: despite allowing for partitions of ℝ^{m} into m+1 sets, the optimal partition has only three nonempty sets. Note that this degeneracy property occurs for the first time when m = 3, since in the result of [23] for partitions of ℝ^{2} into three sets, all three sets are indeed present in the optimal partition. Thus Theorem 1.1 is a proof of the first nonintuitive case of the Propeller Conjecture: a verification of a prediction about a clean yet unexpected geometric phenomenon that arose from an investigation in computational complexity. To the best of our knowledge this is the first time that such a development occurred in this theory.

Our proof of Theorem 1.1 proceeds as follows. First, using reductions of the Propeller Conjecture that were obtained in [23], we show that it suffices to prove an analogous partitioning problem for the sphere S^{2}. Namely, given a partition of S^{2} into four spherical triangles, the goal is to show that the sum of the squares of lengths of the moments (with respect to the surface area measure on S^{2}) of these spherical triangles cannot exceed 9π^{2}/4. Using additional geometric arguments, we further reduce the question to an optimization problem over a three dimensional search space. We thus obtain a coordinate system with three degrees of freedom, with respect to which one must solve a rather complicated nonlinear optimization problem. After proving several additional estimates that serve to further reduce the search space and give crucial modulus of continuity estimates, we show that it suffices to check that the desired estimate holds true for a finite list of spherical partitions (arising from an appropriate net of the search space). This list of inequalities that must be proved is explicit but very large, so we proceed to check it in a fully rigorous computer-assisted fashion. That is, our computation carefully accounts for all the rounding errors; equivalently the computation can be viewed as an implementation in our setting of interval arithmetic (see [17]).

The role and implications of rigorous computer-assisted proofs has been discussed at length in the literature; many such discussions appear in papers that establish striking results via a proof that has a computer-assisted component (famous examples include [1, 2, 18, 11, 15, 12]). We see no reason to include here a new treatment of this topic. Zwick’s discussion in [39] is an excellent reference for a well thought out explanation of the role of computer-assisted proofs in mathematics and computer science^{1}. The essence of the argument can be best conveyed by quoting Zwick directly [39, Sec. 7]:

“A typical computer assisted proof, like ours, is essentially composed of two steps. The first step says something like: “Here is program P. If program P, when executed by an abstract computer, outputs YES, then the theorem is true, because … ”. The second step says something like: “I ran program P and it said YES!”, or more specifically: “I compiled program P using compiler A, under operating system B, and ran it on processor C, again under operating system B. It said YES!”.”

Zwick then proceeds to explain that

“The first step is a conventional mathematical proof. It simply argues that a certain program has certain properties. Such arguments are common in computer science. Anyone who objects to this step of the proof should find a flaw, or a gap, in the arguments made.”

Nevertheless, Zwick explains that the second step, i.e., the claim that the compilation of the program gave the desired result, is not of the same nature:

“The second step is more problematic. It is certainly not a proof in the conventional mathematical sense of the word. Many things can go wrong here. Program P may not have been compiled correctly by compiler A. Or, due to some bug in operating system B, the program did not run as intended. Or, processor C may suffer from a design flaw that causes an incorrect execution of the program, or perhaps the specific processor used has a short-circuit somewhere, and so on. It is possible to reduce the likelihood of such problems by compiling the program using several different compilers, and running it on different processors. But, while we may eventually be able to produce mathematical correctness proofs for compilers, operating systems, and the hardware design of the processors, it seems that we would never be able to produce a mathematical proof that no hardware fault occurred during a specific computation.

What we can do, is instruct the computer executing program P to print a trace of the execution. This trace is a mathematical proof, though perhaps a not so inspiring one. Like any mathematical proof it should be checked carefully to make sure that it is correct. In many cases, however, this is not humanly possible. The main problem with computer assisted proofs, therefore, is that they are usually too long. They are also, in most cases, less insightful than conventional proofs.”

The bulk of the work presented in this article consists of conventional geometric and analytic proofs, resulting in a reduction of the problem to a region where the desired inequality holds with “room to spare”. This extra room allows us to complete the proof by checking a finite list of concrete inequalities (that we write explicitly) on a certain finite net. Each such inequality can be checked by hand, but the number of such checks is large, and it would be unrealistic (and probably unilluminating) to complete this final check manually. The code that we used is publicly available at the following link, which contains a command-line user interface so that interacting with the code is easy.

         http://cims.nyu.edu/~aukosh/propeller/propeller.html

1Zwick’s paper [39] is another instance of a computer-assisted proof in the context of approximation algorithms.

While the present article deals with an integrality gap lower bound for a semindefinite program (the left hand side of (4)), Zwick proves an integrality gap upper bound, i.e., he uses a rigorous computer-assisted argument to show that a certain algorithm performs well rather than to prove a hardness result.

The code for this proof was run many times on several different computers. The technical requirements are quite modest, with the processor speed only affecting the total run time, and the total memory requirement being less than 200 Mb. One can run the code on anything from a dedicated compute server to a laptop computer (we did both). We ran the code in two different ways. The simplest way was to run it in a serial fashion. That is, we ran the program as a single instance which performed each step of the algorithm described in this paper one after the other. This took 37 hours to complete on a single processor of a compute server with 3.3 GhZ Intel Xenon processors. The second way we ran it was to parallelize the algorithm by breaking up the domain of interest into seven distinct portions and running separate instances on each. This procedure took eight hours when split between seven 3.3 GhZ Intel Xenon processors. (We also ran the program split between seven 2.4 GhZ AMD Opteron processors; this procedure took twelve hours.)

Needless to say, our proof of the Propeller Conjecture in ℝ^{3} leaves something to be desired, since we do not have a short explanation of the validity of the computations in the final step of our proof. It is conceptually important to have a proof of this result, despite the fact that it ends in a lengthy computation, not only because it yields interesting results in mathematics and computational complexity. Importantly, since the Propeller Conjecture is a nonintuitive prediction that arose from investigations in computational complexity, knowing that the first nonintuitive case of this conjecture is indeed true puts the full Propeller Conjecture, and consequently the link between geometry and algorithms that it describes, on a stronger footing. Thus, in addition to yielding a remarkably involved UGC hardness result, our theorem will hopefully invigorate future research on this problem that might lead to a traditional mathematical proof of the Propeller Conjecture in ℝ^{3} that can hopefully be extended to higher dimensions.

A key feature of the Propeller Conjecture is that it asserts that a natural optimization problem exhibits intermediate-dimensional symmetry breaking. There are precedents of results of this type that have been proved in the literature, mostly using Fourier-analytic methods. For this reason we are hopeful that a clean and shorter proof of the Propeller Conjecture will eventually be found. Consider for example the problem of sharp Khinchine inequalities: if ε_{1}, …, ε_{n} are i.i.d. symmetric random variables taking values in {−1, 1} and p ∈ [1, 2), the goal is to compute the minimum of 𝔼 [|∑_{i=1}^{n} a_{i}ε_{i}|^{p}] over all unit vectors a = (a_{1}, …, a_{n}) ∈ ℝ^{n}. For p = 1 it was conjectured by Littlewood (see [16]) that this minimum occurs at a = (1, 1, 0, …, 0)/\sqrt{2}. Littlewood’s conjecture was solved affirmatively by Szarek [37] (see also [38, 30]). Haagerup [14] proved that the same two dimensional symmetry breaking occurs for p ∈ [1, p_{0}], where p_{0} = 1.87... is the solution of the equation 2Γ((p + 1)/2) = \sqrt{π}, i.e., the unit vector that minimizes 𝔼 [|∑_{i=1}^{n} a_{i}ε_{i}|^{p}] equals (1, 1, 0, …, 0)/\sqrt{2} for p ∈ [1, p_{0}] and for p ∈ [p_{0}, 2] this minimum occurs at a = (1, …, 1)/\sqrt{n}. Another famous result of this type is Ball’s cube slicing theorem [3] (resolving a conjecture of Hensley [19]), asserting that the hyperplane section of [−1, 1]^{n} with maximal (n − 1)-dimensional volume is perpendicular to (1, 1, 0, …, 0); see [35] for the corresponding result for complex scalars, as well as [4, 6] for an analogous statement for projections. We refer to [34] for a unified treatment of the results of Szarek, Haagerup, and Ball. There is also a conjecture of Milman predicting a symmetry breaking phenomenon for extremal volumes of slabs in the cube [−1, 1]^{n}; see [5, 28] for partial results along these lines. We mentioned the above statements since we believe that among the literature they are most similar to the Propeller Conjecture, and perhaps (with much more work) related methods could be be used to address the Propeller Conjecture as well.

This article is organized as follows. In Section 2 we present the reduction of the Propeller Conjecture to a certain optimization problem for spherical partitions, and we explain the main ingredients of our proof, including the conventional geometric/analytic arguments, as well as the computer-assisted component. The proofs of the geometric and analytic results leading to the final computational step are contained in Section 3 and Section 4. Section 4.1 contains a detailed explanation of how the numerical step is implemented so as to account for all possible rounding errors. We remark that our arguments extend mutatis mutandis to higher dimensions. For the sake of simplicity we present the entire argument in ℝ^{3}, since while it is conceivable that the scheme presented here can yield a computer-assisted proof of the Propeller Conjecture in higher dimensions, at some fixed dimension the computer-assisted component of the proof will become unfeasible. Now that we know that a nonintuitive case of the Propeller Conjecture is indeed correct, the next natural step is to search for a proof that extends to all dimensions, rather than attempting to prove a few more cases in low dimensions.

2. An overview of the proof of Theorem 1.1

From now on assume for the sake of eventually obtaining a contradiction that {A_{i}}_{i=1}^{4} is a partition of ℝ^{3} into measurable sets that violates the propeller conjecture, i.e.,

∑_{i=1}^{4} ∥∫_{A_{i}} xdγ_{3}(x)∥_{2}^{2} > \frac{9}{8π} .  (5)

Assume moreover that the maximum of ∑_{i=1}^{4} ∥∫_{B_{i}} xdγ_{3}(x)∥_{2}^{2} over all measurable partitions {B_{i}}_{i=1}^{4}

of ℝ^{3} is attained at {A_{i}}_{i=1}^{4}. For a proof that this maximum is indeed attained, see [23, Lem. 3,1]. Using this maximality, it follows from [23, Lem. 3.3] that (up to measure zero corrections) the A_{i} are cones with cusp at the origin, and if we write ζ_{i} = ∫_{A_{i}} xdγ_{3}(x) then ζ_{1} + ζ_{2} + ζ_{3} + ζ_{4} = 0 and for each i ∈ {1, 2, 3, 4} we have

A_{i} = {x ∈ ℝ^{3} : ⟨x, ζ_{i}⟩ = max_{j∈{1,2,3,4}}⟨x, ζ_{j}⟩} .  (6)

By [23, Lem. 3.3 & Cor. 3.4] the vectors {ζ_{i}}_{i=1}^{4} are distinct, nonzero and not coplanar.

Since the sets in question are cones, it is beneficial to study them in terms of their intersection with the sphere S^{2}, i.e., define

T_{i} = A_{i} ∩ S^{2},  (7)

and letting σ denote the surface area measure on S^{2} (thus σ(S^{2}) = 4π), define

z_{i} = ∫_{T_{i}} xdσ(x) = \sqrt{2π^{3}} · ζ_{i},  (8)

where the last equality in (8) follows from integration in polar coordinates. Being a constant multiple of the vectors {ζ_{i}}_{i=1}^{4}, the vectors {z_{i}}_{i=1}^{4} are also distinct, nonzero, not coplanar, and satisfy z_{1} + z_{2} + z_{3} + z_{4} = 0. Moreover,

T_{i} =^{(6)∧(7)∧(8)} {x ∈ S^{2} : ⟨x, z_{i}⟩ = max_{j∈{1,2,3,4}}⟨x, z_{j}⟩} .  (9)

Consequently,

∀i, j ∈ {1, 2, 3, 4}, x ∈ T_{i} ∩ T_{j} ⟹ ⟨z_{i}, x⟩ = ⟨z_{j}, x⟩.  (10)

Fix ℓ ∈ {1, 2, 3, 4}. Since {z_{i}}_{i=1}^{4} are not coplanar there exists a unique v_{ℓ} ∈ S^{2} satisfying

∀i, j ∈ {1, 2, 3, 4} ∖ {ℓ}, ⟨z_{i}, v_{ℓ}⟩ = ⟨z_{j}, v_{ℓ}⟩ > ⟨z_{ℓ}, v_{ℓ}⟩.  (11)

The vectors {v_{ℓ}}_{ℓ=1}^{4} are the vertices of the partition P = {T_{1}, T_{2}, T_{3}, T_{4}} of S^{2}. A simple argument presented in Section 3 shows that v_{i} ∉ {−v_{j}, v_{j}} if i ≠ j and each spherical triangle T_{i} is contained in an open hemisphere of S^{2}. Moreover, for distinct i, j, ℓ ∈ {1, 2, 3, 4} we have det(v_{i}, v_{j}, v_{ℓ}) ≠ 0, and if we define

θ_{ij} = arccos(⟨v_{i}, v_{j}⟩)  and  Θ_{ijℓ} = arccos (⟨\frac{(v_{i} × v_{j})}{||v_{i} × v_{j}||_{2}} , \frac{(v_{j} × v_{ℓ})}{||v_{j} × v_{ℓ}||_{2}} ⟩) ,  (12)

then it is also argued in Section 3 that θ_{ij}, Θ_{ijℓ} ∈ (0, π). Observe θ_{ij} = θ_{ji}, Θ_{ijk} = Θ_{kji}, and Θ_{ijℓ} is the spherical angle, at vertex v_{j}, of the spherical triangle with vertices {v_{i}, v_{j}, v_{ℓ}}; the cosine of this angle is exactly the inner product of unit normals of the two planes containing {v_{i}, v_{j}, 0} and {v_{j}, v_{ℓ}, 0} respectively. See Figure 2 for a schematic description of the notation.

v_{2}  θ_{13} v_{1}  v_{3} θ_{23} θ_{12}_{(a)}  ^{v_{3} v_{2} v_{1} Θ_{213}}_{(b)}

Figure 2. (a) Spherical triangle constructed with three great circles (b) Partition of the sphere into four spherical triangles.

In order to proceed we need to have a formula for the spherical moment z_{4} in terms of the vertices {v_{1}, v_{2}, v_{3}} of the spherical triangle T_{4}. In order to do so, assume that det(v_{1}, v_{2}, v_{3}) > 0. Then

z_{4} = \frac{1}{2} (θ_{12} \frac{v_{1} × v_{2}}{||v_{1} × v_{2}||_{2}} + θ_{23} \frac{v_{2} × v_{3}}{||v_{2} × v_{3}||_{2}} + θ_{31} \frac{v_{3} × v_{1}}{||v_{3} × v_{1}||_{2}} ) .  (13)

Identity (13) was proved by Minchin in 1877; see [32, p. 259]. We also found identity (13) in [9], which is a military publication that is not publicly available (it isn’t classified: we purchased access to it). Since both references for (13) are hard to find, we include a brief derivation of it in Proposition 3.2, using the Cauchy projection formula (see [26, p. 25]).

Using (13) and geometric arguments, we show in Lemma 3.5 that the vertex v_{4} is determined by the vertices {v_{1}, v_{2}, v_{3}} as follows; an analogous formula expresses each vertex of the partition in terms of the other three vertices.

v_{4} = −\frac{1}{\sqrt{λ}} (\frac{sin θ_{23}}{θ_{23}} v_{1} + \frac{sin θ_{13}}{θ_{13}} v_{2} + \frac{sin θ_{12}}{θ_{12}} v_{3}) ,

where

λ = ||\frac{sin θ_{23}}{θ_{23}} v_{1} + \frac{sin θ_{13}}{θ_{13}} v_{2} + \frac{sin θ_{12}}{θ_{12}} v_{3}||_{2}^{2} = \frac{sin^{2} θ_{23}}{θ_{23}^{2}} + \frac{sin^{2} θ_{13}}{θ_{13}^{2}} + \frac{sin^{2} θ_{12}}{θ_{12}^{2}}

+ 2\frac{sin θ_{23} sin θ_{13}}{θ_{23}θ_{13}} cos θ_{12} + 2\frac{sin θ_{23} sin θ_{12}}{θ_{23}θ_{12}} cos θ_{13} + 2\frac{sin θ_{12} sin θ_{13}}{θ_{12}θ_{13}} cos θ_{23}. (14)

In Proposition 3.7 we derive the following restriction on products of opposite edges.

\frac{sin θ_{12} sin θ_{34}}{θ_{12}θ_{34}} = \frac{sin θ_{13} sin θ_{24}}{θ_{13}θ_{24}} = \frac{sin θ_{14} sin θ_{23}}{θ_{14}θ_{23}} .

Also, in Lemma 3.9 we obtain the following expression for the objective function at the partition P = {T_{i}}_{i=1}^{4} as the sum of the squares of the angles between the vertices.

F (P) = ∥z_{1}∥_{2}^{2} + ∥z_{2}∥_{2}^{2} + ∥z_{3}∥_{2}^{2} + ∥z_{4}∥_{2}^{2} = θ_{12}^{2} + θ_{13}^{2} + θ_{14}^{2} + θ_{23}^{2} + θ_{24}^{2} + θ_{34}^{2}.  (15)

Define

γ = \frac{sin θ_{23}}{θ_{23}} cos θ_{12} + \frac{sin θ_{13}}{θ_{13}} + \frac{sin θ_{12}}{θ_{12}} cos θ_{23}.  (16)

In Lemma 3.8 we obtain the following useful restriction on a single spherical triangle appearing in the partition {T_{1}, T_{2}, T_{3}, T_{4}}.

cos (\sqrt{λ − γ^{2}} \frac{θ_{23}θ_{12}}{sin θ_{23} sin θ_{12}} ) = cos (\sqrt{θ_{12}^{2} + θ_{23}^{2} + 2θ_{12}θ_{23} cos Θ_{123}}) = −\frac{γ}{\sqrt{λ}},  (17)

where λ is given in (14).

Observe that (17) is a restriction involving data from only one triangle T_{4}, as we see by the definitions of γ and λ. Moreover, by symmetry, every cyclic permutation of {θ_{12}, θ_{23}, θ_{13}} must also satisfy (17). And, every triangle of P must satisfy (17), with the indices of the θ_{ij} substituted appropriately. To understand the ramifications of (17) assume that θ_{12} = θ_{23} = θ_{13} =: θ. Then (17) simplifies to

cos (\sqrt{2(2 cos θ + 1)(1 − cos θ)}\frac{θ}{sin θ} ) = −\frac{1}{\sqrt{3}}\sqrt{2 cos θ + 1}.  (18)

The only θ ∈ (0, 2π/3) satisfying this equation are θ = arccos(−1/3) ≈ 1.9106332362490187, and θ ≈ 1.5379684120790425. The first solution corresponds to the partition whose vertices are those of a regular simplex inscribed in the sphere, and the second intuitively corresponds to a critical point “between” the regular partition and the propeller partition (note that θ = 2π/3 implies det(v_{1}, v_{2}, v_{3}) = 0, and θ > 2π/3 cannot be achieved by a spherical triangle). The above special values of θ will play an important role in the ensuing computations.

As explained in the discussion following Lemma 3.9, a combination of (15) and (17) can be used to express the value of our objective function at the maximizing partition P in terms of the data from a single spherical triangle in P. Specifically, we have

F (P) = 3 (θ_{12}^{2} + θ_{23}^{2} + θ_{13}^{2}) + 2 cos(Θ_{213})θ_{12}θ_{13} + 2 cos(Θ_{123})θ_{12}θ_{23} + 2 cos(Θ_{231})θ_{23}θ_{13}. (19)

In particular, it follows that the right hand side of (19) must be the same for each set of data for all four triangles of P.

Up to now we only discussed identities that the extremal partition P must satisfy. In order to proceed we need to prove some a priori estimates on the various parameters in question. First, let M = max{θ_{12}, θ_{13}, θ_{23}}. It follows from (19) that F (P) ⩽ 14M^{2} (using the fact that at least one Θ_{ijk} must be greater than \frac{π}{3} ). Our contrapositive assumption (5) combined with (8) implies that F (P) > \frac{9π^{2}}{4} , so we deduce that all the triangles in P must have an edge of length greater than \frac{3π}{2\sqrt{14}} > \frac{5}{4}. Additional arguments (that are significantly more involved technically) imply that for all distinct i, j, ℓ ∈ \{1, 2, 3, 4\} we have θ_{ij} ⩽ π − \frac{1}{2} (Lemma 3.12) and θ_{ij}, sin Θ_{ijℓ} > \frac{1}{10} (Lemma 3.16). In Lemma 4.1 we prove that (θ_{12}, θ_{13}, θ_{23}) must be outside the ℓ_{2} ball of radius \frac{1}{100} centered at (θ, θ, θ) for θ = arccos (−\frac{1}{3}) and θ = 1.53796841207904. This excludes from our search space balls centered at the two solutions of (18) that were discussed above. In Lemma 4.2 we show that, up to a relabeling of the spherical triangles T_{1}, T_{2}, T_{3}, T_{4}, we may assume that \sqrt{λ} > \frac{9}{50}.

It turns out that the above estimates suffice in order to conclude the proof of Theorem 1.1 via a search over a sufficiently fine net. To explain this endgame, note that by the spherical law of cosines we have cos θ_{13} = cos θ_{12} cos θ_{23} +sin θ_{12} sin θ_{23} cos Θ_{123}. It therefore follows from (14), (17),

(16) that if we define h, λ, γ : [0, π]^{3} → ℝ by

λ(x, y, z) = \frac{sin^{2} x}{x} + \frac{sin^{2} y}{y} + \frac{sin^{2} z}{z} + 2\frac{sin x sin y}{xy} cos z + 2\frac{sin x sin z}{xz} cos y + 2\frac{sin y sin z}{yz} cos x,

γ(x, y, z) = \frac{sin z}{z} cos x + \frac{sin y}{y} + \frac{sin x}{x} cos z,

h(x, y, z) = \sqrt{λ(x, y, z)} cos (\sqrt{x^{2} + z^{2} + 2xz \frac{cos y − cos x cos z}{sin x sin z}} ) + γ(x, y, z),

then h(θ_{12}, θ_{13}, θ_{23}) = 0. This identity must hold for all cyclic permutations of the indices {1, 2, 3}, so we also have the two identities h(θ_{13}, θ_{23}, θ_{12}) = h(θ_{23}, θ_{12}, θ_{13}) = 0. It follows that if we define H = (H_{1}, H_{2}, H_{3}) : [0, π]^{3} → ℝ^{3} by H(x, y, z) = (h(y, z, x), h(x, y, z), h(z, x, y)) then at the extremal partition P we have H(θ_{12}, θ_{13}, θ_{23}) = 0.

Our strategy is therefore as follows. At every point q in the search space given by the constraints described above (specifically, see the system of equations (67), excluding also the two balls described in Lemma 4.1), we will show that either H(q) ≠ 0 or F_{0}(q) < 9π^{2}/4, where F_{0} is given by the right hand side of (19) (with the understanding that one expresses cos Θ_{123}, cos Θ_{213}, cos Θ_{231} in terms of θ_{12}, θ_{23}, θ_{13} using the spherical law of cosines, so that F_{0} is a function of θ_{12}, θ_{23}, θ_{13}). Due to the above discussion, such an assertion will complete the proof of Theorem 1.1. Moreover, it turns out that this assertion holds “with room to spare”, making a computer-assisted verification feasible.

To this end, we need to have estimates on the modulus of continuity of H and F_{0}. Such estimates are complicated but can be proved using elementary considerations; see Lemma 4.3 and the discussion immediately following it. Consequently, if we are given a point q in our restricted search space and τ ∈ (0, 1) for which either |H(q)| > τ or F_{0}(q) < 9π^{2}/4 − τ, then it would follow that for some r > 0 that depends on τ via our modulus of continuity estimates, in the entire ball of radius r centered at q either H ≠ 0 or F_{0} < 9π^{2}/4.

From this procedure we achieve a process by which we can iteratively remove from our search space macroscopically large regions of controlled size in which we are guaranteed that a counterexample to the Propeller Conjecture cannot exist. Our program proceeds to remove such balls until it eventually exhausts the entire search space, thus arriving at the conclusion that there is no counterexample to the Propeller Conjecture.

In order to make such a procedure rigorous, we carefully account for all possible rounding errors. We do this quite conservatively, i.e., while significantly overestimating the magnitude of all possible errors, as explained in detail in Section 4.1. Note that our computer-assisted proof does not compute any computationally complicated expressions such as, say, definite integrals or implicitly defined functions: it only checks inequalities between expressions involving elementary combinations of trigonometric functions and square roots.

In summary, the validity of the Propeller Conjecture in ℝ^{3} has mainly conceptual implications, and what remains open seems to be of a more technical nature: to perhaps find a clever transformation, e.g., as in Ball’s cube slicing theorem [3], that allows one to prove the theorem analytically rather than resorting to a transversal of a net in a region where the desired inequality is actually quite weak. At present, we have a clean geometric argument which addresses directly the region where the Propeller Conjecture is most subtle, and in the remainder of the search space we do something rather crude. This has two conceptual consequences: the Propeller Conjecture as a nonintuitive link between complexity theory and geometry is correct, and moreover one has a geometric/analytic proof of this conjecture in a region where it is tightest. Nevertheless, we are lacking a technical idea that allows us to address the remaining region in a way that does not resort to “brute force”. It remains a challenge to find such an idea, with the hope that it will pave the way to a proof of the Propeller Conjecture in all dimensions.

3. Proofs of basic identities and estimates

This section contains proofs the geometric identities and inequalities that were stated in Section 2. Recall that we are assuming that P = {T_{1}, T_{2}, T_{3}, T_{4}} is a partition of S^{2} into four spherical triangles, and that {z_{i}}_{i=1}^{4}, as defined in (8), are the corresponding spherical moments. We are also making the contrapositive assumption that our objective function

F (P) = ∥z_{1}∥_{2}^{2} + ∥z_{2}∥_{2}^{2} + ∥z_{3}∥_{2}^{2} + ∥z_{4}∥_{2}^{2}  (20)

(recall (15)) exceeds 9π^{2}/4, which is the maximal value of F (·) that is predicted by the Propeller Conjecture. We also assume that P maximizes F. The vertices of the partition {v_{i}}_{i=1}^{4} were defined in Section 2, along with the angles θ_{ij} and Θ_{ijℓ} as given in (12).

Proposition 3.1. (a) z_{1} + z_{2} + z_{3} + z_{4} = 0.

(b) Suppose two triangles T_{i}, T_{j} ∈ P share an edge E = T_{i} ∩ T_{j}. Then for all e ∈ E we have ⟨z_{i}, e⟩ = ⟨z_{j}, e⟩. In particular, if ℓ ∉ {i, j} then ⟨z_{i}, v_{ℓ}⟩ = ⟨z_{j}, v_{ℓ}⟩.

(c) For all distinct i, j ∈ {1, 2, 3, 4} we have ⟨z_{i}, v_{i}⟩ = ⟨−3z_{j}, v_{i}⟩.

(d) For all distinct i, j ∈ {1, 2, 3, 4} we have v_{j} ∉ {−v_{i}, v_{i}}.

(e) For all distinct i, j, ℓ ∈ {1, 2, 3, 4} we have det(v_{i}, v_{j}, v_{ℓ}) ≠ 0 , each T_{i} is contained in an open hemisphere, and 0 < θ_{ij}, Θ_{ijℓ} < π.

Proof. Parts (a) and (b) were already proved in Section 2; for part (b) see (10). A combination of (11) and part (a) implies part (c). For ℓ ∈ {1, 2, 3, 4} let Π_{ℓ} be the unique plane containing {z_{i}}_{i∈{1,2,3,4}∖{ℓ}}. A vector is perpendicular to Π_{ℓ} if and only if it has equal inner product on {z_{i}}_{i∈{1,2,3,4}∖{ℓ}}, so ℝv_{ℓ} is also perpendicular to Π_{ℓ}. Since {z_{i}}_{i=1}^{4} are not coplanar the planes {Π_{ℓ}}_{ℓ=1}^{4} have distinct perpendiculars. So v_{1}, v_{2}, v_{3}, v_{4} are distinct with v_{i} ∉ ℝv_{j} for i ≠ j. This establishes (d). For every ℓ ∈ {1, 2, 3, 4} consider the set

U_{ℓ} = \{x ∈ S^{2} : min_{i∈\{1,2,3,4\}∖ℓ}⟨x, z_{i} − z_{ℓ}⟩ > \frac{1}{2}⟨v_{ℓ}, z_{i} − z_{ℓ}⟩\} .

It follows from (11) that U_{ℓ} is an open neighborhood of v_{ℓ}, and in combination with (9) we know that

i ∈ {1, 2, 3, 4} ∖ {ℓ} ⟹ U_{ℓ} ∩ T_{i} = {x ∈ U_{ℓ} ∩ S^{2} : ⟨x, z_{i}⟩ = max_{j∈{1,2,3,4}∖{ℓ}}⟨x, z_{j}⟩} .  (21)

Write I = {1, 2, 3, 4}∖{ℓ}. For every distinct i, k ∈ {1, 2, 3, 4} the set {x ∈ S^{2} : ⟨x, z_{i}⟩ ⩾ ⟨x, z_{j}⟩} is a half sphere, and therefore the set T_{i,ℓ} = {x ∈ S^{2} : ⟨x, z_{i}⟩ = max_{j∈I}⟨x, z_{j}⟩} is strictly contained in a half sphere (since the z_{j} are distinct and nonzero). Note that ∂T_{i,ℓ} is the union of two half circles that meet at antipodal points, and v_{ℓ} is one of these antipodal points. So, the spherical angle of T_{i,ℓ} at the vertex v_{ℓ} is in (0, π). By (9) and (21) this spherical angle is identical for T_{i,ℓ} and T_{i}. This shows that Θ_{iℓj} ∈ (0, π) for all distinct i, j, ℓ ∈ {1, 2, 3, 4}. Also θ_{ij} ∈ (0, π) since v_{j} ∉ {−v_{i}, v_{i}}. Next, assume for the sake of contradiction that det(v_{i}, v_{j}, v_{ℓ}) = 0. Since v_{i} ∉ ℝv_{j} for distinct i, j ∈ {1, 2, 3, 4}, it follows that v_{i} = α_{j}v_{j} + α_{ℓ}v_{ℓ} with α_{j}, α_{ℓ} ∈ ℝ ∖ {0}. Hence v_{i} × v_{j} = α_{ℓ}v_{ℓ} × v_{j} with α_{ℓ} ≠ 0, contradicting Θ_{ijℓ} ∈ (0, π). We have already seen that T_{i,ℓ} is contained a closed hemisphere, and this containment can be chosen such that T_{i,ℓ} intersected with the boundary of the hemisphere is {v_{ℓ}, −v_{ℓ}}. But from (9) we know that T_{i} ⊆ T_{i,ℓ} and T_{i} avoids a neighborhood of {−v_{ℓ}}, so each T_{i} is contained in an open hemisphere. This concludes the proof of (e). □

We now give an explicit formula for the spherical moments {z_{i}}_{i=1}^{4}; as explained in Section 2, this formula can be found in [32, p. 259] and [9, p. 6]. Since these references are hard to find, we provide a proof.

Proposition 3.2. Suppose that the spherical triangle T_{4} ⊆ S^{2} has vertices {v_{1}, v_{2}, v_{3}} satisfying det(v_{1}, v_{2}, v_{3}) > 0. Then the vector z_{4} = ∫_{T_{4}} xdσ ∈ ℝ^{3} satisfies

z_{4} = \frac{1}{2} (θ_{12} \frac{v_{1} × v_{2}}{||v_{1} × v_{2}||_{2}} + θ_{23} \frac{v_{2} × v_{3}}{||v_{2} × v_{3}||_{2}} + θ_{31} \frac{v_{3} × v_{1}}{||v_{3} × v_{1}||_{2}} ) .  (22)

Consequently

⟨z_{4}, v_{1}⟩ = ⟨\frac{θ_{23}}{2} \frac{v_{2} × v_{3}}{||v_{2} × v_{3}||_{2}} , v_{1}⟩ = \frac{θ_{23} det(v_{1}, v_{2}, v_{3})}{2 sin θ_{23}}  (23)

Proof. Fix y ∈ T_{4} ∖ ∂T_{4}. By definition of z_{4},

⟨z_{4}, y⟩ = ∫_{T_{4}}⟨x, y⟩dσ(x).  (24)

Let H ⊆ ℝ^{3} be the convex hull of T_{4} ∪ {0} and let {U_{i}}_{i=1}^{3} ⊆ ℝ^{3} be half spaces through the origin such that {x ∈ ℝ^{3} : ||x||_{2} ⩽ 1} ⋂ (⋂_{i=1}^{3} U_{i}) = H; see Figure 3.

v_{2} v_{1}  0 v_{3}

Figure 3. Spherical triangle together with three disc sectors, each containing {v_{i}, v_{j}, 0}.

Define Π: S^{2} → ℝ^{2} so that Π(x) is the orthogonal projection of x ∈ S^{2} ⊆ ℝ^{3} onto the unique plane that is intersecting the origin and perpendicular to y. Applying the Cauchy projection formula (see for example [26, p. 25]) to T_{4}, we see that

∫_{T_{4}}⟨x, y⟩dσ(x) = Area_{ℝ^{2}}Π(T_{4} ∩ {x ∈ S^{2} : ⟨y, x⟩ > 0}) − Area_{ℝ^{2}}Π(T_{4} ∩ {x ∈ S^{2} : ⟨y, x⟩ ⩽ 0}). (25)

Define A = (T_{4} ∖ ∂T_{4}) ∩ {x ∈ S^{2} : ⟨y, x⟩ > 0} and B = (∂H) ∖ A. Note that ∂H is the union of T_{4} and three sectors of discs {D_{i}}_{i=1}^{3} such that D_{i} ⊆ ∂U_{i}. Since y ∈ ⋂_{i=1}^{3} U_{i}, the exterior normal n(x) of x ∈ D_{i} ⊆ ∂H has nonpositive inner product with y for i = 1, 2, 3. So, ⟨n(x), y⟩ > 0 for x ∈ ∂H if and only if x ∈ A. Since H is convex, Π: A → Π(∂H) and Π: B → Π(∂H) are bijections almost everywhere. Since ∂H = T_{4} ⋃ (⋃_{i=1}^{3} D_{i}), the Cauchy projection formula applied to right side of the identity Area_{ℝ^{2}}(Π(A)) = Area_{ℝ^{2}}(Π(B)) gives

Area_{ℝ^{2}}Π(T_{4} ∩ {x ∈ S^{2} : ⟨y, x⟩ > 0}) = Area_{ℝ^{2}}Π(T_{4} ∩ {x ∈ S^{2} : ⟨y, x⟩ ⩽ 0})

+ \frac{θ_{12}}{2} ⟨y, \frac{v_{1} × v_{2}}{||v_{1} × v_{2}||_{2}} ⟩ + \frac{θ_{23}}{2} ⟨y, \frac{v_{2} × v_{3}}{||v_{2} × v_{3}||_{2}} ⟩ + \frac{θ_{13}}{2} ⟨y, \frac{v_{3} × v_{1}}{||v_{3} × v_{1}||_{2}} ⟩ . (26)

Since (26) holds for any y ∈ S^{2} ∩ T_{4}, (24), (25) and (26) give (22). □

Note that the vectors in the determinant of (23) are assumed to have positive orientation. So, when we apply this equation below we will need to respect orientations.

Corollary 3.3. Under the assumptions of Proposition 3.2, we have

∥z_{4}∥_{2}^{2} = \frac{1}{4} (θ_{12}^{2} + θ_{23}^{2} + θ_{13}^{2} − 2 cos(Θ_{213})θ_{12}θ_{13} − 2 cos(Θ_{123})θ_{12}θ_{23} − 2 cos(Θ_{231})θ_{23}θ_{13}) (27)
= \frac{1}{4} (θ_{12}^{2} + θ_{23}^{2} + θ_{31}^{2} + 2\frac{cos θ_{12} cos θ_{13} − cos θ_{23}}{sin θ_{12} sin θ_{13}} θ_{12}θ_{13}
+2\frac{cos θ_{12} cos θ_{23} − cos θ_{13}}{sin θ_{12} sin θ_{23}} θ_{12}θ_{23} + 2\frac{cos θ_{23} cos θ_{13} − cos θ_{12}}{sin θ_{23} sin θ_{13}} θ_{23}θ_{13}) .  (28)

Proof. Apply (22), and then use either the vector identity ⟨a × b, c × d⟩ = ⟨a, c⟩⟨b, d⟩ − ⟨a, d⟩⟨b, d⟩, or the spherical law of cosines. □

Corollary 3.4. For distinct i, j ∈ {1, 2, 3, 4} we have ⟨z_{i}, v_{j}⟩ > 0.

Proof. Let k, ℓ be such that det(v_{k}, v_{j}, v_{ℓ}) > 0, and apply (23) and Proposition 3.1(e). □

Lemma 3.5. Write ⟨z_{4}, v_{1}⟩ =: a, ⟨z_{4}, v_{2}⟩ =: b, ⟨z_{4}, v_{3}⟩ =: c and ⟨z_{4}, v_{4}⟩ =: −3d. Then the following relation holds

\frac{1}{a}v_{1} + \frac{1}{b}v_{2} + \frac{1}{c}v_{3} + \frac{1}{d}v_{4} = 0  (29)

Proof. By Proposition 3.1(e) we have det(v_{1}, v_{2}, v_{3}) ≠ 0, so we may write v_{4} = ∑_{i=1}^{3} α_{i}v_{i} for some α_{1}, α_{2}, α_{3} ∈ ℝ. By Proposition 3.1(c),

d = ⟨z_{1}, v_{4}⟩ = ⟨z_{2}, v_{4}⟩ = ⟨z_{3}, v_{4}⟩.

Substituting in the expression v_{4} = ∑_{i=1}^{3} α_{i}v_{i} and then applying Proposition 3.1(b) and (c) several times, we get

d = −3aα_{1} + bα_{2} + cα_{3} = aα_{1} − 3bα_{2} + cα_{3} = aα_{1} + bα_{2} − 3cα_{3}.

Solving this system of equations gives

d = −aα_{1} = −bα_{2} = −cα_{3}.

By Corollary 3.4, we may write α_{1} = −d/a, α_{2} = −d/b, α_{3} = −d/c. Substituting these equalities into the expression v_{4} = ∑_{i=1}^{3} α_{i}v_{i} gives (29). Note that at least one α_{i} is nonzero, so d is nonzero as well, that is, we have not made a division by zero. □

Since det(v_{1}, v_{2}, v_{3}) ≠ 0, we have ||\frac{1}{a}v_{1} + \frac{1}{b}v_{2} + \frac{1}{c}v_{3}||_{2} ≠ 0. Since ||v_{4}||_{2} = 1, Lemma 3.5 implies

v_{4} = −\frac{\frac{1}{a}v_{1} + \frac{1}{b}v_{2} + \frac{1}{c}v_{3}}{||\frac{1}{a}v_{1} + \frac{1}{b}v_{2} + \frac{1}{c}v_{3}||_{2}} .  (30)

A priori, we have only determined v_{4} up to multiplication by ±1. However, Proposition 3.1(c) and Corollary 3.4 imply that d = (−1/3)⟨z_{4}, v_{4}⟩ > 0. So, taking the inner product of z_{4} with both sides of (30) shows that (30) has the correct sign.

Applying (23) to (30) gives

v_{4} = −\frac{\frac{sin θ_{23}}{θ_{23}} v_{1} + \frac{sin θ_{13}}{θ_{13}} v_{2} + \frac{sin θ_{12}}{θ_{12}} v_{3}}{||\frac{sin θ_{23}}{θ_{23}} v_{1} + \frac{sin θ_{13}}{θ_{13}} v_{2} + \frac{sin θ_{12}}{θ_{12}} v_{3}||_{2}} .  (31)

Define, as we did in Section 2,

λ = ||\frac{sin θ_{23}}{θ_{23}} v_{1} + \frac{sin θ_{13}}{θ_{13}} v_{2} + \frac{sin θ_{12}}{θ_{12}} v_{3}||_{2}^{2}  (32)

= \frac{sin^{2} θ_{23}}{θ_{23}^{2}} + \frac{sin^{2} θ_{13}}{θ_{13}^{2}} + \frac{sin^{2} θ_{12}}{θ_{12}^{2}} + 2\frac{sin θ_{23} sin θ_{13}}{θ_{23}θ_{13}} cos θ_{12}

+ 2\frac{sin θ_{23} sin θ_{12}}{θ_{23}θ_{12}} cos θ_{13} + 2\frac{sin θ_{12} sin θ_{13}}{θ_{12}θ_{13}} cos θ_{23}.

(33)

Proposition 3.6. (a) All four vertices of P are not contained in any closed half sphere. (b) The function F (P) is well-defined as a function of the vertices {v_{i}}_{i=1}^{4}.

Proof. (a) By Proposition 3.1(e) we have 0 < θ_{ij} < π. (31) says that v_{4} is in the complement of all closed half spheres containing {v_{1}, v_{2}, v_{3}}.

(b) From Proposition 3.1(e), the edges T_{i} ∩ T_{j} of P are geodesics of length less than π, so the vertices uniquely determine the edges. Finally, the edges determine P itself. □

Proposition 3.7 (Restrictions on products of opposite edges).

\frac{sin θ_{12} sin θ_{34}}{θ_{12}θ_{34}} = \frac{sin θ_{13} sin θ_{24}}{θ_{13}θ_{24}} = \frac{sin θ_{14} sin θ_{23}}{θ_{14}θ_{23}} .  (34)

Proof. From Proposition 3.1(c) we have ⟨z_{3}, v_{1}⟩ = ⟨z_{2}, v_{1}⟩. For each side of the equality ⟨z_{3}, v_{1}⟩ = ⟨z_{2}, v_{1}⟩, apply (23) for ⟨z_{i}, v_{1}⟩ and then substitute in (31) to get

−\frac{det(v_{1}, v_{3}, v_{2})}{2\sqrt{λ}} \frac{sin θ_{12}}{θ_{12}} \frac{θ_{24}}{sin θ_{24}} = −\frac{det(v_{1}, v_{3}, v_{2})}{2\sqrt{λ}} \frac{sin θ_{13}}{θ_{13}} \frac{θ_{34}}{sin θ_{34}} .

Canceling terms gives the first equality of (34). The second follows similarly: Proposition 3.1(c) says ⟨z_{3}, v_{2}⟩ = ⟨z_{1}, v_{2}⟩, and so on. □

Lemma 3.8 (Restrictions on a single triangle). Let λ be defined as in (33) and let γ be defined as in (16), i.e.,

γ = \frac{sin θ_{23}}{θ_{23}} cos θ_{12} + \frac{sin θ_{13}}{θ_{13}} + \frac{sin θ_{12}}{θ_{12}} cos θ_{23}.  (35)

Then the following holds

cos (\sqrt{λ − γ^{2}} \frac{θ_{23}θ_{12}}{sin θ_{23} sin θ_{12}} ) = −\frac{γ}{\sqrt{λ}}.  (36)
cos (\sqrt{θ_{12}^{2} + θ_{23}^{2} + 2θ_{12}θ_{23} cos Θ_{123}}) = −\frac{γ}{\sqrt{λ}}.  (37)

Proof. Arguing as in Proposition 3.7, we start with Proposition 3.1(c) and the equality ⟨z_{4}, v_{1}⟩ = ⟨z_{3}, v_{1}⟩. For each side of this equality, apply (23) for ⟨z_{i}, v_{1}⟩ and substitute in (31) to get

\frac{θ_{23}θ_{12}}{sin θ_{23} sin θ_{12}} = \frac{θ_{24}}{sin θ_{24}} \frac{1}{\sqrt{λ}}.  (38)

Substituting θ_{24} = arccos(⟨v_{2}, v_{4}⟩) into (38) and rearranging gives

cos (\sqrt{λ}\sqrt{1 − ⟨v_{2}, v_{4}⟩^{2}} \frac{θ_{23}θ_{12}}{sin θ_{23} sin θ_{12}} ) = ⟨v_{2}, v_{4}⟩.

From (31) and the definitions of λ and γ ((33) and (35)), we have ⟨v_{2}, v_{4}⟩ = −γ/\sqrt{λ}, so

cos (\sqrt{λ}\sqrt{1 − \frac{γ^{2}}{λ}} \frac{θ_{23}θ_{12}}{sin θ_{23} sin θ_{12}} ) = −\frac{γ}{\sqrt{λ}}.

yielding (36). To derive (37), observe that λ − γ^{2} allows some cancelation as follows.

λ − γ^{2} = \frac{sin^{2} θ_{23}}{θ_{23}^{2}} (1 − cos^{2} θ_{12}) + \frac{sin^{2} θ_{12}}{θ_{12}^{2}} (1 − cos^{2} θ_{23}) + 2\frac{sin θ_{23} sin θ_{12}}{θ_{23}θ_{12}} (cos θ_{31} − cos θ_{23} cos θ_{12})

= \frac{sin^{2} θ_{23}}{θ_{23}^{2}} (sin^{2} θ_{12}) + \frac{sin^{2} θ_{12}}{θ_{12}^{2}} (sin^{2} θ_{23}) + 2\frac{sin θ_{23} sin θ_{12}}{θ_{23}θ_{12}} (cos θ_{31} − cos θ_{23} cos θ_{12}).

Thus,

(λ − γ^{2})\frac{θ_{23}^{2}θ_{12}^{2}}{sin^{2} θ_{23} sin^{2} θ_{12}} = θ_{12}^{2} + θ_{23}^{2} + 2θ_{12}θ_{23} \frac{cos θ_{31} − cos θ_{23} cos θ_{12}}{sin θ_{12} sin θ_{23}}
= θ_{12}^{2} + θ_{23}^{2} + 2θ_{12}θ_{23} cos Θ_{123} , by the spherical law of cosines.

Substituting this equation into (36) gives (37). □

Since −\frac{γ}{\sqrt{λ}} = ⟨v_{4}, v_{2}⟩ = cos θ_{24}, (37) says that

θ_{12}^{2} + θ_{23}^{2} + 2θ_{12}θ_{23} cos Θ_{123} = θ_{24}^{2}.  (39)

Substituting (39) back into (27) and (20) gives a simplified form of F (P). Lemma 3.9.

F (P) = ∑_{i<j} θ_{ij}^{2} = ∑_{i<j}(arccos(⟨v_{i}, v_{j}⟩))^{2}  (40)

Proof. Applying (28) to the definition F (P) = ∑_{i=1}^{4} ||z_{i}||_{2}^{2} gives

F (P) = \frac{1}{2} ∑_{i<j} θ_{ij}^{2} − \frac{1}{2} ∑_{i,j,ℓ} cos(Θ_{ijℓ})θ_{ij}θ_{jℓ}.  (41)

Here the first sum in (41) runs over all (i, j) satisfying 1 ⩽ i < j ⩽ 4, and the second sum runs over all equivalence classes of 3-tuples (i, j, ℓ) under the equivalence (i, j, ℓ) ∼ (ℓ, j, i), where i, j, ℓ are distinct elements of {1, 2, 3, 4}. From (39) we have, for r ∉ {i, j, ℓ},

θ_{ij}^{2} + θ_{jℓ}^{2} + 2θ_{ij}θ_{jℓ} cos Θ_{ijℓ} = θ_{jr}^{2}.  (42)

Substituting (42) into (41) gives

F (P) = \frac{1}{2} ∑_{i<j} θ_{ij}^{2} − \frac{1}{4} ∑_{i,j,ℓ} (θ_{jr}^{2} − θ_{ij}^{2} − θ_{jℓ}^{2}) .

In the right summation, for a fixed (i′, j′) with i′ ≠ j′, the term θ_{i′j′}^{2} appears four times with a minus sign and two times with a plus sign. Therefore,

F (P) = \frac{1}{2} ∑_{i<j} θ_{ij}^{2} − \frac{1}{4} ∑_{i,j,ℓ} (θ_{jr}^{2} − θ_{ij}^{2} − θ_{jℓ}^{2}) = \frac{1}{2} ∑_{i<j} θ_{ij}^{2} − \frac{1}{4}(∑_{i<j} −2θ_{ij}^{2}) = ∑_{i<j} θ_{ij}^{2},

proving (40). □ In (40) replace θ_{jr}^{2} with the left side of (42) for (j, r) ∈ {(1, 4), (2, 4), (3, 4)} to get

F (P) = 3 (θ_{12}^{2} + θ_{23}^{2} + θ_{13}^{2}) + 2 cos(Θ_{213})θ_{12}θ_{13} + 2 cos(Θ_{123})θ_{12}θ_{23} + 2 cos(Θ_{231})θ_{23}θ_{13}. (43)

Definition 3.10. By the spherical law of cosines, Θ_{ijℓ} is a function of {θ_{ij}, θ_{jℓ}, θ_{iℓ}}. Let

F_{0}(θ_{12}, θ_{23}, θ_{13}) = 3 (θ_{12}^{2} + θ_{23}^{2} + θ_{13}^{2}) + 2 cos(Θ_{213})θ_{12}θ_{13} + 2 cos(Θ_{123})θ_{12}θ_{23} + 2 cos(Θ_{231})θ_{23}θ_{13}.

By (43), F (P) = F_{0} can be computed by the data from only one triangle of P. That is,

F_{0}(θ_{12}, θ_{23}, θ_{13}) = F_{0}(θ_{12}, θ_{24}, θ_{14}) = F_{0}(θ_{34}, θ_{24}, θ_{23}) = F_{0}(θ_{34}, θ_{14}, θ_{13}).

Since the spherical propeller partition, i.e., the partition of S^{2} corresponding to the intersection of the propeller partition of ℝ^{3} with S^{2}, satisfies F = (9/4)π^{2}, we may bound (43) in terms of M = max{θ_{12}, θ_{13}, θ_{23}}. In particular, we get F (P) ⩽ 14M^{2}, which is less than (9/4)π^{2} if M < π \frac{3}{2\sqrt{14}}. (In our bound on F (P), we use that one Θ_{ijk} must be larger than π/3 by the pigeonhole principle applied to Θ_{123} + Θ_{231} + Θ_{312} − π = Area_{S^{2}}(T_{4}) > 0, so one cosine term satisfies cos Θ_{ijk} ⩽ 1/2.) So, this bound on F gives

Corollary 3.11. Any triangle T_{i} of P must have an edge of length greater than π \frac{3}{2\sqrt{14}} > \frac{5}{4}.

Iteratively applying (34) gives the following improvement to Proposition 3.1(e). This improvement will be important in our numerical calculations in Section 4 and in the proof of Theorem 1.1, since we eventually require a bound on the derivative of θ_{ij}/ sin θ_{ij}.

Lemma 3.12 (Restrictions on edge length). For every distinct i, j ∈ {1, 2, 3, 4},

θ_{ij} < π − \frac{1}{2}.  (44)

Proof. Suppose θ_{12} ⩾ π − 1/2. We are eventually going to derive a contradiction, which will allow us to conclude that θ_{12} < π − 1/2. We will essentially only need (34), the monotonicity of x ↦ (sin x)/x for x ∈ (0, π), the fact that the perimeter θ_{ij} + θ_{jℓ} + θ_{ℓi} of a spherical triangle is bounded by 2π, and that (sin x)/x ⩽ 1 on [0, π]. Relabeling the edges if necessary, we may assume that θ_{13} = max{θ_{13}, θ_{24}}. Using θ_{12} ⩾ π − 1/2, (34) gives

\frac{sin(π − 1/2)}{π − 1/2} ⩾ \frac{sin θ_{12}}{θ_{12}} ⩾ \frac{sin θ_{12} sin θ_{34}}{θ_{12}θ_{34}} = \frac{sin θ_{13} sin θ_{24}}{θ_{13}θ_{24}} ⩾ (\frac{sin θ_{13}}{θ_{13}} )^{2} .  (45)

Therefore, θ_{13} ⩾ X where X ∈ (0, π) satisfies

(\frac{sin X}{X} )^{2} = \frac{sin(π − 1/2)}{π − 1/2}.  (46)

So, θ_{13} ⩾ X > 2.065. Now, since θ_{12} + θ_{13} + θ_{23} ⩽ 2π the bounds on θ_{12} and θ_{13} give

θ_{23} ⩽ 2π − (π − 1/2 + X) =: Y < 1.577.

But then (34) and the bounds on θ_{12} and θ_{23} yield

\frac{sin θ_{14}}{θ_{14}} = \frac{sin θ_{12} sin θ_{34}}{θ_{12}θ_{34}} \frac{θ_{23}}{sin θ_{23}} ⩽ \frac{sin(π − 1/2)}{π − 1/2} \frac{Y}{sin Y} .

So, θ_{14} ⩾ Z where Z ∈ (0, π) is defined by

\frac{sin Z}{Z} = \frac{sin(π − 1/2)}{π − 1/2} \frac{Y}{sin Y} .

Then θ_{14} ⩾ Z > 2.388. But since θ_{14} + θ_{24} + θ_{12} ⩽ 2π the bounds on θ_{14} and θ_{12} give

θ_{24} ⩽ 2π − (π − 1/2 + Z) =: W < 1.254

We now iterate the above argument. Using (45),

\frac{sin θ_{13}}{θ_{13}} = \frac{sin θ_{12} sin θ_{34}}{θ_{12}θ_{34}} \frac{θ_{24}}{sin θ_{24}} ⩽ \frac{sin(π − 1/2)}{π − 1/2} \frac{W}{sin W} .  (47)

So, θ_{13} ⩾ X̃ with (sin X̃)/X̃ = (sin(π − 1/2)/(π − 1/2))(W/ sin W). We now repeat the argument above, starting at (46) and using tildes to designate updated variables. Thus, θ_{13} ⩾ X̃ > 2.499, θ_{23} ⩽ Ỹ < 1.14, θ_{14} ⩾ Z̃ > 2.52, θ_{24} ⩽ W̃ < 1.122. Using W̃ in place of W in (47), we find that θ_{13} > 2.52.

In summary, iterating the above procedure improves our bounds on the θ_{ij}. We find that θ_{13}, θ_{14} > 2.52. We also find that θ_{23}, θ_{24} < 1.14. Since θ_{13} + θ_{14} + θ_{34} ⩽ 2π, θ_{34} ⩽ 2π − (2(2.52)). But then θ_{23}, θ_{24}, θ_{34} < 5/4 < π \frac{3}{2\sqrt{14}}, violating Corollary 3.11 and giving our desired contradiction. We therefore conclude that θ_{ij} < π − 1/2. □

For a partition P = {T_{i}}_{i=1}^{4} as above, the following map G: (S^{2})^{4} → ℝ is also a function of P by Proposition 3.6(b)

G(v_{1}, v_{2}, v_{3}, v_{4}) = ∑_{1⩽i<j⩽4} θ_{ij}^{2}.  (48)

Proposition 3.13. Suppose that the conclusion of Proposition 3.1(e) holds. Then Proposition 3.1(c) holds if and only if P is a critical point of G.

Proof. For a manifold M with v ∈ M, T_{v}M denotes the tangent space of M at v. Since G = ∑_{i<j} θ_{ij}^{2} = ∑_{i<j}(arccos⟨v_{i}, v_{j}⟩)^{2}, we take derivatives of G with respect to v_{i}. For v_{2}, v_{3}, v_{4} ∈ S^{2} fixed and x ∈ ℝ^{3} variable,

∇_{S^{2}}G(·, v_{2}, v_{3}, v_{4}) = (∇_{ℝ^{3}}G (\frac{x}{||x||_{2}} , v_{2}, v_{3}, v_{4}))|_{S^{2}}

Recall that T_{v_{1}}ℝ^{3} is isomorphic to ℝ^{3}. We denote this isomorphism by (d/dy) ↔ y. Let \frac{d}{dy} be a vector in the tangent space T_{v_{1}}ℝ^{3}. Identifying \frac{d}{dy} with y ∈ ℝ^{3} we compute

\frac{d}{dy} G (\frac{x}{||x||_{2}} , v_{2}, v_{3}, v_{4}) = ∑_{j≠1} \frac{−2 arccos(⟨x, v_{j}⟩/ ||x||_{2})}{\sqrt{1 − (⟨x, v_{j}⟩/ ||x||_{2})^{2}}} ⟨\frac{d}{dy} (x/ ||x||_{2}), v_{j}⟩

= ∑_{j≠1} \frac{−2 arccos(⟨x, v_{j}⟩/ ||x||_{2})}{\sqrt{1 − (⟨x, v_{j}⟩/ ||x||_{2})^{2}}} (\frac{||x||_{2} \frac{d}{dy} ⟨x, v_{j}⟩ − \frac{1}{2}⟨x, v_{j}⟩ ||x||_{2}^{−1} \frac{d}{dy} ⟨x, x⟩}{||x||_{2}^{2}})

= ∑_{j≠1} \frac{−2 arccos(⟨x, v_{j}⟩/ ||x||_{2})}{\sqrt{1 − (⟨x, v_{j}⟩/ ||x||_{2})^{2}}} ⟨(\frac{||x||_{2} y − x ||x||_{2}^{−1} ⟨y, x⟩}{||x||_{2}^{2}}) , v_{j}⟩ .

Letting \frac{d}{dy} ∈ T_{v_{1}}S^{2} and x = v_{1} ∈ S^{2} gives ⟨y, x⟩ = 0, so that

\frac{d}{dy} G (\frac{x}{||x||_{2}} , v_{2}, v_{3}, v_{4}) = ∑_{j≠1} \frac{−2 arccos(⟨v_{1}, v_{j}⟩)}{\sqrt{1 − (⟨v_{1}, v_{j}⟩)^{2}}} ⟨y, v_{j}⟩ = ∑_{j≠1} \frac{−2θ_{1j}}{sin θ_{1j}} ⟨y, v_{j}⟩ .

So, if we take \frac{d}{dy} = v_{1} × v_{2} ∈ T_{v_{1}}S^{2} and then use (23), we get

\frac{d}{dy} G = \frac{−2θ_{13}}{sin θ_{13}} det(v_{1}, v_{2}, v_{3}) − \frac{2θ_{14}}{sin θ_{14}} det(v_{1}, v_{2}, v_{4}) = 2(−⟨z_{4}, v_{2}⟩ + ⟨z_{3}, v_{2}⟩).

In general, if we take the derivative at v_{i} in the direction v_{i} × v_{j} and set this derivative to zero, we get ⟨z_{r}, v_{j}⟩ = ⟨z_{ℓ}, v_{j}⟩ where the set {i, j, ℓ, r} is equal to the set {1, 2, 3, 4}. Since the above argument can be reversed, the proposition is proven. □

Setting \frac{d}{dy} = v_{2} − ⟨v_{2}, v_{1}⟩v_{1} and \frac{d}{dy} = v_{3} − ⟨v_{3}, v_{1}⟩v_{3} in the above argument gives

− θ_{12} = θ_{13} cos Θ_{213} + θ_{14} cos Θ_{214}.  (49)

Observe that

\frac{d}{dy} G (\frac{x}{||x||_{2}} , v_{2}, v_{3}, v_{4}) = ∑_{j≠1} \frac{−2θ_{1j}}{sin θ_{1j}} ⟨y, v_{j}⟩ = ∑_{j≠1} \frac{−2θ_{1j}}{sin θ_{1j}} ⟨(v_{2} − ⟨v_{1}, v_{2}⟩v_{1}), v_{j}⟩

= −\frac{2θ_{12}}{sin θ_{12}} (1 − (⟨v_{2}, v_{1}⟩)^{2}) − \frac{2θ_{13}}{sin θ_{13}} (⟨v_{2}, v_{3}⟩ − (⟨v_{2}, v_{1}⟩)(⟨v_{1}, v_{3}⟩))

− \frac{2θ_{14}}{sin θ_{14}} (⟨v_{2}, v_{4}⟩ − (⟨v_{2}, v_{1}⟩)(⟨v_{1}, v_{4}⟩))

= −\frac{2θ_{12}}{sin θ_{12}} (1 − (⟨v_{2}, v_{1}⟩)^{2}) − \frac{2θ_{13}}{sin θ_{13}} ⟨(v_{1} × v_{2}), (v_{1} × v_{3})⟩ − \frac{2θ_{14}}{sin θ_{14}} ⟨(v_{1} × v_{2}), (v_{1} × v_{4})⟩ .

Thus, dividing by sin θ_{12}, setting \frac{d}{dy} G = 0, and simplifying as in Corollary 3.3 gives (49).

We now give a geometric interpretation of (39) and (49) that should clarify their meaning. Define exp_{1}^{−1} : {2, 3, 4} → ℝ^{2} by

exp_{1}^{−1}(j) = θ_{1j} \frac{(v_{j} − ⟨v_{j}, v_{1}⟩v_{1})}{||v_{j} − ⟨v_{j}, v_{1}⟩v_{1}||_{2}} .  (50)

Then exp_{1}^{−1}(j) is perpendicular to v_{1} and parallel to v_{j} − Proj_{v_{1}}v_{j}, with length θ_{1j}.

Lemma 3.14. Suppose that the conclusion of Proposition 3.1(e) holds. If {v_{i}}_{i=1}^{4} is a critical point of G, then

exp_{1}^{−1}(2) + exp_{1}^{−1}(3) + exp_{1}^{−1}(4) = 0.  (51)

Proof. Let Π_{ij} ⊆ ℝ^{3} be the plane containing {0, v_{i}, v_{j}}. For j ∈ {2, 3, 4}, exp_{1}^{−1}(j) ∈ Π_{1j} is perpendicular to v_{1} and in Π_{1j}, so ⟨exp_{1}^{−1}(2), exp_{1}^{−1}(3)⟩ = θ_{12}θ_{13} cos Θ_{213}. We can therefore rewrite (39) as

||exp_{1}^{−1}(2) + exp_{1}^{−1}(3)||_{2}^{2} = ||exp_{1}^{−1}(4)||_{2}^{2} .  (52)

Using the definition of exp_{1}^{−1}(j), we similarly rewrite (49) (with its indices permuted) as

− exp_{1}^{−1}(4) = Proj_{exp_{1}^{−1}(4)}(exp_{1}^{−1}(2)) + Proj_{exp_{1}^{−1}(4)}(exp_{1}^{−1}(3)).  (53)

Since exp_{1}^{−1}(j) is perpendicular to v_{1} for j ∈ {2, 3, 4}, {exp_{1}^{−1}(j)}_{j∈{2,3,4}} lies in a plane containing the origin. Combining (52) and (53) therefore gives (51). □

In particular, orthogonally projecting (51) orthogonal to exp_{1}^{−1}(2) gives

θ_{13} sin Θ_{213} = θ_{14} sin Θ_{214}.  (54)

The similarity of (39),(49) and (54) is no coincidence. For example, note that (49) and (54) express ∑_{j∈{2,3,4}} exp_{1}^{−1}(j) = 0, tangential and perpendicular to exp_{1}^{−1}(2), respectively. So, combining Proposition 3.13, (49), (54) and Lemma 3.14, we deduce the equivalence

Corollary 3.15. Suppose that the conclusion of Proposition 3.1(e) holds. Then

\begin{cases}Prop. 3.1(c) \\ holds \end{cases}\} ⇔ \begin{cases}P is a \\ critical point of G \end{cases}\} ⇔ \begin{cases}(51) holds at each v_{i}. That is, \\ for each i, ∑_{j: j≠i} exp_{i}^{−1}(j) = 0 \end{cases}\}

Lemma 3.16. θ_{ij} > 1/10 and sin Θ_{ijℓ} > 1/10.

Proof. After recording a few identities, we consider a few cases in proving θ_{ij} > 1/10. In all cases, we argue by contradiction and assume 0 < θ_{12} ⩽ 1/10. Also, by relabeling if necessary, we may assume that max{θ_{13}, θ_{23}, θ_{14}, θ_{24}} = max{θ_{13}, θ_{23}}.

cos Θ_{213} = \frac{cos θ_{23} − cos θ_{12} cos θ_{13}}{sin θ_{12} sin θ_{13}} .  (55)

cos Θ_{132} = \frac{cos θ_{12} − cos θ_{13} cos θ_{23}}{sin θ_{13} sin θ_{23}} .  (56)
cos θ_{34} = cos θ_{13} cos θ_{14} + sin θ_{13} sin θ_{14} cos Θ_{314}
= cos θ_{13} cos θ_{14} + sin θ_{13} sin θ_{14} cos(2π − Θ_{213} − Θ_{214}).

(57)

| arccos(x + y) − arccos(x)| ⩽ arccos(1 − y), x, y, x + y ∈ [−1, 1].  (58)

(Case 1) π/2 ⩽ max{θ_{13}, θ_{23}} ⩽ π/2 + 1/10. Without loss of generality, label the edges so that θ_{13} ⩾ θ_{23}, so π/2 ⩽ θ_{13} ⩽ π/2 + 1/10. Then θ_{14} ⩾ θ_{24}, from Proposition 3.1(b). The Proposition shows that Proj_{span{v_{1},v_{2}}}(z_{4}−z_{3}) = 0. Suppose θ_{14} < θ_{24}. Let e be the midpoint of the edge T_{4}∩T_{3} and let n ∈ span{v_{1}, v_{2}} be perpendicular to e such that ⟨n, v_{2}⟩ > 0. Since θ_{13} ⩾ θ_{23}, ⟨z_{4}, n⟩ ⩾ 0. To see this, let Π: S^{2} → ℝ^{2} denote projection onto the unique plane intersecting the origin and perpendicular to n. Without loss of generality, the vertices are oriented so that det(v_{1}, v_{2}, v_{3}) > 0. Let m be the point of intersection of this plane with (∂T_{4}) ∖ (∂T_{3}). The spherical triangle T′_{4} with vertices {v_{1}, v_{2}, m} then has two equal length edges {v_{1}, m} and {v_{2}, m}, and T′_{4} ⊆ T_{4}. Also, θ_{13} ⩾ θ_{23} implies that T_{4} ∩ {x ∈ S^{2} : ⟨x, n⟩ ⩽ 0} = T′_{4} ∩ {x ∈ S^{2} : ⟨x, n⟩ ⩽ 0}. Since T_{4} ⊇ T′_{4} and T′_{4} is isosceles,

Π (T_{4} ∩ {x ∈ S^{2} : ⟨x, n⟩ ⩾ 0}) ⊇ Π (T′_{4} ∩ {x ∈ S^{2} : ⟨x, n⟩ ⩾ 0}) = Π (T_{4} ∩ {x ∈ S^{2} : ⟨x, n⟩ ⩽ 0}) .

So (25) shows ⟨z_{4}, n⟩ ⩾ 0. Similarly, θ_{14} < θ_{24}, implies ⟨z_{3}, n⟩ < 0, a contradiction. Now

cos Θ_{213} = \frac{cos θ_{23} − cos θ_{13} cos θ_{12}}{sin θ_{13} sin θ_{12}} ⩾ \frac{cos θ_{13}(1 − cos θ_{12})}{sin θ_{13} sin θ_{12}} = \frac{tan(θ_{12}/2)}{tan θ_{13}} ⩾ \frac{tan(1/20)}{tan(π/2 + 1/10)}.

So, Θ_{213} ⩽ arccos(\frac{tan(1/20)}{tan(π/2+1/10)}) < π/2 + .01. By (39), (θ_{13} − θ_{12})^{2} ⩽ θ_{14}^{2} ⩽ (θ_{12} + θ_{13})^{2}, so π/2 − 1/10 ⩽ θ_{14} ⩽ θ_{13} + θ_{12} ⩽ π/2 + 1/10 + 1/10. So we similarly conclude that Θ_{214} ⩽ arccos(\frac{tan(1/20)}{tan(π/2+1/5)}) < π/2 + .02. By (57),

cos θ_{34} = cos(θ_{13} + θ_{14}) + sin θ_{13} sin θ_{14}(1 + cos(2π − Θ_{213} − Θ_{214})).  (59)

Since Θ_{314} < π by Proposition 3.1(e),

|1 + cos Θ_{314}| = |1 + cos(2π − Θ_{213} − Θ_{214})| ⩽ |1 + cos(2π − π − .03)| < .0005.

Then (58) applied to (59) gives a dichotomy: (i) if θ_{13} + θ_{14} ⩽ π, then |θ_{34} − (θ_{13} + θ_{14})| < .04. Or (ii) if θ_{13} + θ_{14} > π, then |θ_{34} − (2π − θ_{13} + θ_{14})| < .04. In case (i), θ_{34} ⩾ π/2 + π/2 − 1/10 − .04 > π − 1/2. In case (ii), θ_{34} ⩾ 2π − (π/2 + 1/10 + π/2 + 1/5) − .04 > π − 1/2. So, in either case, Lemma 3.12 is violated. Therefore Case 1 cannot hold. (Case 2) π/2 + 1/10 ⩽ max{θ_{13}, θ_{23}} ⩽ 2.9. Without loss of generality, label the edges so that θ_{13} ⩾ θ_{23}, so π/2 + 1/10 ⩽ θ_{13} ⩽ 2.9. By the triangle inequality on the sphere, θ_{23} ⩾ θ_{13} − θ_{12} ⩾ θ_{13} − 1/10 ⩾ π/2, so

θ_{13} cos Θ_{132} = θ_{13} (\frac{cos θ_{12} − cos θ_{13} cos θ_{23}}{sin θ_{13} sin θ_{23}} ) ⩾ θ_{13} (\frac{cos(1/10) − cos θ_{13} cos θ_{13}}{sin θ_{13} sin(θ_{13} − 1/10)} ) > \frac{π}{2} .

Since θ_{23}, θ_{13} ⩾ π/2, (39) gives

θ_{34} = \sqrt{θ_{13}^{2} + θ_{23}^{2} + 2θ_{13}θ_{23} cos Θ_{132}} > \sqrt{2(π/2)^{2} + 2(π/2)(π/2)} = π,

so (44) is violated. Therefore Case 2 cannot occur. (Case 3) The case max{θ_{13}, θ_{23}} > 2.9 cannot occur, by (44). Also, max{θ_{13}, θ_{23}, θ_{14}, θ_{24}} < π/2 implies that T_{4} and T_{3} are contained in separate but adjacent quarter spheres, so T_{4}∪T_{3} is contained in a half sphere. To see this, consider the edge T_{4} ∩ T_{3}. Let Π_{12} be the plane such that Π_{12} ∩ S^{2} ⊇ T_{4} ∩ T_{3}. Temporarily suppose θ_{13} = θ_{23} = π/2, and let R: ℝ^{3} → ℝ^{3} be the origin fixing rotation that maps the midpoint of T_{4} ∩ T_{3} to v_{3}. Then T_{4} is contained in a quarter sphere whose boundary is contained in Π_{12} ∩ S^{2} and (R(Π_{12})) ∩ S^{2}. If θ_{13}, θ_{23} ⩽ π/2, then T_{4} remains in this quarter sphere, since otherwise v_{3} ∉ {x ∈ S^{2} : d_{S^{2}}(x, v_{1}) ⩽ π/2, d_{S^{2}}(x, v_{2}) ⩽ π/2}. So, Proposition 3.6(a) is violated. All cases therefore produce a contradiction, concluding the proof that θ_{12} > 1/10.

We now prove that sin Θ_{ijk} > 1/10. We argue by contradiction and assume that sin Θ_{132} < 1/10. The procedure is similar to the calculations above. The theme is: if some Θ_{ijk} is very small or very large, this creates additive relations among the edges, up to small errors. Before we begin, we list a few consequences of the spherical law of cosines, for i, j, k distinct elements of {1, 2, 3, 4}.

cos θ_{ij} = cos(θ_{ik} − θ_{kj}) + sin θ_{ik} sin θ_{kj}(cos Θ_{ikj} − 1).  (60)
cos θ_{ij} = cos(θ_{ik} + θ_{kj}) + sin θ_{ik} sin θ_{kj}(cos Θ_{ikj} + 1).  (61)

Now, assume Θ_{132} < π/2. Since Θ_{132} + Θ_{234} + Θ_{134} = 2π and −Θ_{134} > −π from Proposition 3.1(e), Θ_{132} +Θ_{234} ⩾ π. So Θ_{234} > π/2 and sin Θ_{234} ⩽ sin(π −Θ_{132}) = sin(Θ_{132}) < 1/10. So, by relabeling edges if necessary, we may assume that Θ_{132} > π/2. Since Θ_{132} > π/2, cos Θ_{132} ⩽ −.9949. Without loss of generality, label the edges so that θ_{23} = max{θ_{13}, θ_{23}} and θ_{13} = min{θ_{13}, θ_{23}}. (Case 1’) Assume max{θ_{13}, θ_{23}} < π/3. By (39), θ_{34} ⩽ θ_{13} + θ_{23} ⩽ 2π/3. But then Proposition 3.6(a) is violated. (Let v ∈ T_{1} ∩ T_{2} satisfy d_{S^{2}}(v, v_{4}) = min{θ_{34}, π/2}, and note that {v_{i}}_{i=1}^{4} ⊆ {x ∈ S^{2} : d(x, v) ⩽ π/2}.) So Case 1’ cannot occur. (Case 2’) Assume max{θ_{13}, θ_{23}} ⩾ π/3 and 1/10 < min{θ_{13}, θ_{23}} ⩽ 1/2. Then θ_{13} + θ_{23} < π by Lemma 3.12, so (57) and (58) give |θ_{12} − (θ_{13} + θ_{23})| < .11. By the spherical law of sines and Lemma 3.12, sin Θ_{123} = sin Θ_{132} sin θ_{13}/ sin θ_{12} ⩽ sin Θ_{132} sin(1/2)/ sin(1/2) < 1/10. Since θ_{13} ⩽ θ_{23} and θ_{13} ⩽ 1/2, Lemma 3.12 gives cos θ_{13} ⩾ |cos θ_{23}| ⩾ cos θ_{23} cos θ_{12}. So, the formula cos Θ_{123} = (cos θ_{13} − cos θ_{23} cos θ_{12})/(sin θ_{12} sin θ_{23}) shows cos Θ_{123} ⩾ 0, i.e. cos Θ_{123} > .9949.

Since θ_{23} < π − 1/2 from Lemma 3.12, θ_{13} + θ_{23} < π. Combining this with cos Θ_{132} < −.9949,

(61) and (58), we see that θ_{12} ⩾ θ_{13}+θ_{23}−.11. Since cos Θ_{123} > .9949, (39) and θ_{12} > .1 imply θ_{24} ⩾ \sqrt{(π/3)^{2} + (.1)^{2} + 2(.1)(π/3)(.9949)} > π/3. Now, since cos Θ_{123} > .9949, Θ_{123} + Θ_{124} + Θ_{324} = 2π, and −Θ_{123} > −π from Proposition 3.1(e), Θ_{123} + Θ_{324} ⩾ π, so cos Θ_{324} ⩽ cos(π − Θ_{123}) < −.9949. Since θ_{23}, θ_{24} > π/3, by relabeling the edges if necessary we may assume that cos Θ_{123} < −.9949, max{θ_{13}, θ_{23}} ⩾ π/3 and 1/2 < π/3 < min{θ_{13}, θ_{23}}. Thus, we enter into the following case. (Case 3’) Assume max{θ_{13}, θ_{23}} ⩾ π/3 and 1/2 < min{θ_{13}, θ_{23}}. Recall that we may label the edges so that θ_{23} = max{θ_{13}, θ_{23}} and θ_{13} = min{θ_{13}, θ_{23}}. We claim that θ_{23} > 1.3. If not, then (39) says θ_{34}^{2} = θ_{23}^{2} + θ_{13}^{2} + 2θ_{23}θ_{13} cos Θ_{132}, so θ_{34} ⩽ \sqrt{2(1.3)^{2} − 2(.994)(π/3)(1/2)} < 1.53 < π/2 and {v_{i}}_{i=1}^{4} ⊆ {x ∈ S^{2} : d_{S^{2}}(x, v_{3}) ⩽ π/2}. Thus, Proposition 3.6(a) is violated, and our claim is proven.

As in Case 1 in the proof that θ_{ij} > 1/10, (61) gives a dichotomy

(i) |θ_{12} − (θ_{13} + θ_{23})| < .11, or (ii) |θ_{12} + θ_{13} + θ_{23} − 2π| < .11

In case (i), θ_{12} ⩾ θ_{23} + θ_{13} − .11 > 1/2, and in case (ii), Lemma 3.12 says θ_{ij} < π − 1/2, so θ_{12} ⩾ .89 > 1/2. So in either case, 1/2 ⩽ θ_{12} ⩽ π − 1/2, using Lemma 3.12 again. By the spherical law of sines, sin Θ_{123} ⩽ sin Θ_{132}/ sin θ_{12} ⩽ (1/10)(1/ sin(1/2)) < 21/100. Similarly, sin Θ_{312} < 21/100.

Assume (i) holds. If Θ_{123} < π/2, then cos Θ_{123} > .977. By (i), θ_{12} ⩾ 1.3 + 1/2 − .11 = 1.69. By (39), θ_{24}^{2} = θ_{12}^{2} + θ_{23}^{2} + 2θ_{12}θ_{23} cos Θ_{123}, so

θ_{24} ⩾ \sqrt{(1.69)^{2} + (π/3)^{2} + 2(1.69)(π/3)(.977)} > 2.72 > π − \frac{1}{2}.

contradicting Lemma 3.12. If Θ_{123} ⩾ π/2 then cos Θ_{123} < −.977. Then (61) gives a dichotomy: either (i)′ |θ_{13} − (θ_{12} + θ_{23})| < .26 or (ii)′ |θ_{13} + θ_{12} + θ_{23} − 2π| < .26. If (i)′ holds, then θ_{13} ⩾ θ_{12}+θ_{23}−.26, but (i) says θ_{12} ⩾ θ_{13}+θ_{23}−.11. So θ_{13} ⩾ θ_{13}+2θ_{23}−.37, i.e. θ_{23} < .185, contradicting that θ_{23} > π/3. So (ii)′ must hold. But then (i) implies 2θ_{12} ⩾ θ_{12} + θ_{13} + θ_{23} − .11 ⩾ 2π − .37, so θ_{12} ⩾ π − .185, contradicting Lemma 3.12. Therefore (i) does not hold.

Assume (ii) holds. Suppose Θ_{123} < π/2 so cos Θ_{123} > .977. Then (60) and (58) show that |θ_{13} − |θ_{12} − θ_{23}|| < .26. If θ_{12} ⩾ θ_{23}, then |θ_{12} − (θ_{13} + θ_{23})| < .26. So by (ii) 2θ_{12} ⩾ θ_{12} + θ_{13} + θ_{23} − .26 ⩾ 2π − .37, contradicting Lemma 3.12. If θ_{23} ⩾ θ_{12}, then the same argument shows 2θ_{23} ⩾ 2π − .37, contradicting Lemma 3.12. We may therefore assume that cos Θ_{123} < −.977. If cos Θ_{312} > .977, we get the same contradiction, so we may assume cos Θ_{312} < −.977. In summary, cos Θ_{123}, cos Θ_{312}, cos Θ_{132} < −.977.

For i, j distinct, i, j ∈ {1, 2, 3, 4} let E_{ij} = T_{i} ∩ T_{j}. Let i′, j′ so that θ_{i′j′} = max{θ_{13}, θ_{23}, θ_{12}}. Let Π_{i′j′} be the plane containing E_{i′j′} and the origin, and let n be the unit normal to Π_{i′j′} such that ⟨n, z_{4}⟩ < 0. We claim that the edges E_{i′4}, E_{j′4} satisfy

E_{i′4}, E_{j′4} ⊆ {x ∈ S^{2} : 0 ⩽ ⟨x, n⟩ ⩽ .65}.  (62)

Also, the union of E_{i′4}, E_{j′4}, E_{i′j′} forms a noncontractible loop in this topological annulus. To prove E_{i′4} ⊆ {x ∈ S^{2} : ⟨x, n⟩ ⩽ .65}, it suffices to show

Θ_{j′i′4} > π − sin^{−1}(.65), or θ_{i′4} < sin^{−1}(.65).  (63)

To see this consequence, let x ∈ S^{2} be contained in the great circle containing E_{i′4} and let {i′, j′, k} = {1, 2, 3}. Since ⟨n, v_{i′}⟩ = 0 and ⟨n, z_{k}⟩ > 0, ⟨x, n⟩ is maximized when d_{S^{2}}(x, v_{i′}) = π/2 and ⟨x, n⟩ ⩾ 0. For such an x, ⟨x, n⟩ = sin Θ_{j′i′4}. So, in the case that Θ_{j′i′4} > π − sin^{−1}(.65), E_{i′4} ⊆ {x ∈ S^{2} : ⟨x, n⟩ ⩽ .65}. Let now x ∈ {y ∈ S^{2} : d_{S^{2}}(y, v_{i′}) ⩽ θ_{i′4}} ⊇ E_{i′4}. For such an x, ⟨x, n⟩ is maximized for x in the plane containing {v_{i′}, n, 0} with d_{S^{2}}(x, v_{i′}) = θ_{i′4}. So ⟨x, n⟩ = sin θ_{i′4}. So, in the case that θ_{i′4} < sin^{−1}(.65), E_{i′4} ⊆ {x ∈ S^{2} : ⟨x, n⟩ ⩽ .65}, as desired. The containment E_{j′4} ⊆ {x ∈ S^{2} : ⟨x, n⟩ ⩽ .65} follows similarly if one shows: Θ_{i′j′4} > π − sin^{−1}(.65) or θ_{j′4} < sin^{−1}(.65). Specifically, in the above paragraph we switch all indices of the form i′ to j′ and all j′ to i′, and the containment follows.

We now discuss the proof of (63). Let {i′, j′, k} = {1, 2, 3}. Since Θ_{j′i′k}, Θ_{i′j′k} < π by Proposition 3.1(e) and E_{i′j′} ⊆ {x ∈ S^{2} : ⟨x, n⟩ = 0}, we conclude that E_{i′k}, E_{j′k} ⊆ {x ∈ S^{2} : ⟨x, n⟩ ⩽ 0}. By Lemma 3.14, ∑_{j: j≠i′} exp_{i′}^{−1}(j) = 0 and ∑_{j: j≠j′} exp_{j′}^{−1}(j) = 0, so we conclude E_{i′4}, E_{j′4} ⊆ {x ∈ S^{2} : 0 ⩽ ⟨x, n⟩}. By the definition of θ_{i′j′} and Lemma 3.14, Θ_{j′i′4} ⩾ Θ_{ki′4}. In particular, since Θ_{j′i′4} + Θ_{ki′4} ⩾ π, we conclude that Θ_{j′i′4} ⩾ π/2. Similarly, Θ_{i′j′4} ⩾ π/2. If E_{i′4} ∪ E_{i′j′} ∪ E_{j′4} were contractible in {x ∈ S^{2} : 0 ⩽ ⟨x, n⟩ ⩽ .65}, then by (63), the location of v_{4} is such that T_{3} avoids the region {x ∈ S^{2} : ⟨x, n⟩ ⩾ .65 or ⟨x, n⟩ ⩽ 0}. But then either Θ_{i′j′4} or Θ_{j′i′4} is less than π/2, a contradiction. So, the noncontractibility property of E_{i′4} ∪ E_{i′j′} ∪ E_{j′4} follows from (63), which remains to be proven.

Consider θ_{i′k} and E_{i′j′} as fixed with Θ_{j′i′k}, E_{i′4} variable. From Lemma 3.14, recall that exp_{i′}^{−1}(4) and exp_{i′}^{−1}(j′) have angle Θ_{j′i′4}. Also exp_{i′}^{−1}(k) and exp_{i′}^{−1}(j′) have angle Θ_{j′i′k}, and exp_{i′}^{−1}(·) is confined to a plane. By Lemma 3.14, scaling θ_{i′j′} and θ_{i′k} by the same constant (greater than one) leaves Θ_{j′i′4} unchanged and increases θ_{i′4}. So in proving (63), we may assume that θ_{i′j′} = π − 1/2, by Lemma 3.12.

Suppose θ_{i′k} < .815(π − 1/2). In this case, we will show that sin Θ_{j′i′4} < .65, recalling that Θ_{j′i′4} > π/2. Using planar geometry and Lemma 3.14, one can show: decreasing Θ_{j′i′k} decreases Θ_{j′i′4}. So, for the purpose of showing sin Θ_{j′i′4} < .65, we may assume that cos Θ_{j′i′k} = −.977.

Now, suppose θ_{i′k} ⩾ .815(π − 1/2). In this case we show that sin θ_{i′4} < .65, recalling that θ_{i′4} < π/2, since (42) says

θ_{i′4}^{2} = (θ_{i′j′} − θ_{i′k})^{2} + 2θ_{i′j′}θ_{i′k}(1 + cos Θ_{j′i′k}) ⩽ (.185(π − 1/2))^{2} + 2(π − 1/2)^{2}(.815)(.033) < .62.

Consider θ_{i′k}, E_{i′j′} as fixed with Θ_{j′i′k}, E_{i′4} variable. By Lemma 3.14,

θ_{i′4}^{2} = ||exp_{i′}^{−1}(4)||_{2}^{2} = ||exp_{i′}^{−1}(j′) + exp_{i′}^{−1}(k)||_{2}^{2} = θ_{i′j′}^{2} + θ_{i′k}^{2} + 2θ_{i′j′}θ_{i′k} cos Θ_{j′i′k}.

Recall cos Θ_{j′i′k} < −.977, so decreasing Θ_{j′i′k} increases θ_{i′4}. So, for the purpose of maximizing sin θ_{i′4}, we may assume that cos Θ_{j′i′k} = −.977. With these reductions (i.e. that cos Θ_{j′i′k} = −.977 and θ_{i′j′} = π − 1/2) for these two cases, one can then verify (63) directly as a one-dimensional inequality, using Lemma 3.14 and treating θ_{ik} as a variable with all other quantities a function of θ_{ik}. With identical reductions, Θ_{i′j′4} > π − sin^{−1}(.65) θ_{j′4} < sin^{−1}(.65). Therefore, (62) holds.

Given (62), note that the circumference of the geodesic ball {x ∈ S^{2} : ⟨x, n⟩ = .65} is given by 2π\sqrt{1 − (.65)^{2}} > 4.77. By the noncontractible property, θ_{i′j′} + θ_{i′4} + θ_{j′4} ⩾ 4.77. By (39), θ_{i′4} ⩾ \sqrt{(θ_{i′j′} − θ_{i′k})^{2} + 2θ_{i′j′}θ_{i′k}(1 + cos Θ_{j′i′k})} ⩾ θ_{i′j′} − θ_{i′k} and similarly θ_{j′4} ⩾ (θ_{i′j′} − θ_{j′k}). Substituting these inequalities into θ_{i′j′} + θ_{i′4} + θ_{j′4} ⩾ 4.77 gives

θ_{i′j′} + (θ_{i′j′} − θ_{i′k}) + (θ_{i′j′} − θ_{j′k}) ⩾ 4.77.

However, by (ii), θ_{i′j′} +θ_{i′k} +θ_{j′k} ⩾ 2π−.11. So adding the inequalities gives 4θ_{i′j′} ⩾ 4.77+2π−.11, i.e. θ_{i′j′} > 2.73 > π − 1/2, violating Lemma 3.12. So, all cases produce a contradiction, and the result is proven. □

4. Numerical Computations

We now provide a more comprehensive analysis of the system of equations resulting from Lemma 3.8. We begin by writing this system explicitly. For i ∈ {1, 2, 3} choose j, ℓ such that {i, j, ℓ} = {1, 2, 3}. Define

γ_{i} = −\sqrt{λ} ⟨v_{i}, v_{4}⟩ = \frac{sin θ_{iℓ}}{θ_{iℓ}} cos θ_{ij} + \frac{sin θ_{jℓ}}{θ_{jℓ}} + \frac{sin θ_{ij}}{θ_{ij}} cos θ_{iℓ}.  (64)

Then γ = γ_{2} from (35). Our system follows by cyclically permuting the θ_{ij} in (37), i.e.,

\begin{cases}\sqrt{λ} cos (\sqrt{θ_{12}^{2} + θ_{13}^{2} + 2θ_{12}θ_{13} cos Θ_{213}}) + γ_{1} = 0, \\ \sqrt{λ} cos (\sqrt{θ_{12}^{2} + θ_{23}^{2} + 2θ_{12}θ_{23} cos Θ_{123}}) + γ_{2} = 0, \\ \sqrt{λ} cos (\sqrt{θ_{13}^{2} + θ_{23}^{2} + 2θ_{13}θ_{23} cos Θ_{132}}) + γ_{3} = 0, \end{cases}  (65)

where Θ_{ijℓ} and λ are defined in (12) and (32) respectively.

Observe that (65) gives three equations in the three unknowns θ_{12}, θ_{13}, θ_{23}. Define H: [0, π]^{3} → ℝ^{3} so that H(θ_{12}, θ_{13}, θ_{23}) = (H_{1}, H_{2}, H_{3}) is the vector corresponding to the entries of the left side of (65). We now wish to find (θ_{12}, θ_{13}, θ_{23}) such that H = (0, 0, 0).

We first examine neighborhoods of the two points discussed in Section 3.

Lemma 4.1. The global maximum of F does not occur in the ℓ_{2} balls of radius 1/100 around the points {θ_{12}, θ_{13}, θ_{23}} = {θ, θ, θ} ∈ ℝ^{3} with θ = arccos(−1/3) and θ = 1.53796841207904.

Proof. Let δ = 1/100. We claim that |⟨∇_{ℝ^{3}}F_{0}(θ_{12}, θ_{13}, θ_{23}), v⟩| ⩽ 20, for (θ_{12}, θ_{13}, θ_{23}) in an ℓ_{2} ball in ℝ^{3} of radius δ ball around the point (arccos(−1/3), arccos(−1/3), arccos(−1/3)) ∈ ℝ^{3}, where v ∈ S^{2}. Now, F_{0}(arccos(−1/3), arccos(−1/3), arccos(−1/3)) = 6(arccos(−1/3))^{2} ≈ 21.9031 while F at the spherical propeller partition evaluates to (9/4)π^{2} ≈ 22.206. So, given this claim, since δ |⟨∇_{ℝ^{3}}F_{0}⟩| < 22.206−21.903 in B_{2}^{3}({θ}_{i=1}^{3}, δ), no global maximum of F may occur in B_{2}^{3}({θ}_{i=1}^{3}, δ). Similarly, we claim that |⟨∇_{ℝ^{3}}F_{0}(θ_{12}, θ_{13}, θ_{23}), v⟩| ⩽ 15 for (θ_{12}, θ_{13}, θ_{23}) in an ℓ_{2} ball of radius δ around {θ}_{i=1}^{3} ∈ ℝ^{3} with θ ≈ 1.53796841207904. Since F_{0}({θ}_{i=1}^{3}) ≈ 21.7391, once again, no global maximum of F occurs in B_{2}^{3}({θ}_{i=1}^{3}, δ).

Proof of claim: for θ = arccos(−1/3) or θ = 1.537968, we first show that ||Hessian(F_{0})||_{2} < 488 for all points in B_{2}^{3}({θ}_{i=1}^{3}, δ) ⊆ ℝ^{3}. Let F̃(x, y, z) = F_{0}(x, y, z). Then

F̃_{xx} = 6 + 4 \frac{cos (y) y}{sin (y)} − 2 \frac{cos (y) xy cos (x)}{sin (x) sin (y)} + 4 \frac{(cos (z) − cos (x) cos (y)) xy (cos (x))^{2}}{(sin (x))^{3} sin (y)}

− 4 \frac{(cos (z) − cos (x) cos (y)) y cos (x)}{(sin (x))^{2} sin (y)} + 2 \frac{(cos (z) − cos (x) cos (y)) xy}{sin (x) sin (y)} − 2 \frac{cos (x) zy}{sin (z) sin (y)}

+ 4 \frac{cos (z) z}{sin (z)} − 2 \frac{cos (z) xz cos (x)}{sin (x) sin (z)} + 4 \frac{(cos (y) − cos (x) cos (z)) xz (cos (x))^{2}}{(sin (x))^{3} sin (z)}

− 4 \frac{(cos (y) − cos (x) cos (z)) z cos (x)}{(sin (x))^{2} sin (z)} + 2 \frac{(cos (y) − cos (x) cos (z)) xz}{sin (x) sin (z)} .

F̃_{xy} = −2 xy − 2 \frac{(cos (y))^{2} xy}{(sin (y))^{2}} + 2 \frac{cos (y) x}{sin (y)} − 2 \frac{(cos (x))^{2} xy}{(sin (x))^{2}}

+ 2 \frac{(cos (z) − cos (x) cos (y)) xy cos (x) cos (y)}{(sin (x))^{2} (sin (y))^{2}} − 2 \frac{(cos (z) − cos (x) cos (y)) x cos (x)}{(sin (x))^{2} sin (y)}

+ 2 \frac{cos (x) y}{sin (x)} − 2 \frac{(cos (z) − cos (x) cos (y)) y cos (y)}{sin (x) (sin (y))^{2}} + 2 \frac{cos (z) − cos (x) cos (y)}{sin (x) sin (y)}

+ 2 \frac{sin (x) zy cos (y)}{sin (z) (sin (y))^{2}} − 2 \frac{sin (x) z}{sin (z) sin (y)} + 2 \frac{sin (y) xz cos (x)}{(sin (x))^{2} sin (z)} − 2 \frac{sin (y) z}{sin (x) sin (z)}.

With δ < 1/100, θ = arccos(−1/3), and (x, y, z) ∈ B_{2}^{3}({θ}_{i=1}^{3}, δ), we have 1/ |sin(x)| < 1.1, and similarly for y, z. Therefore, in this δ-ball we have |F̃_{xx}| < 228. Here we have bounded the cosine terms by 1, the x, y, z terms by 2 (since arccos(1/3) + δ < 2), and the inverted sine terms by 1.1. Using these same bounds, we find that |F̃_{xy}| < 117 in this same δ-ball. For a 3 × 3 matrix A = a_{ij}, let ||A||_{2} = (∑_{i,j=1}^{3} a_{ij}^{2})^{1/2}. Since F̃ is symmetric in its arguments, we have the following bound in B_{2}^{3}({θ}_{i=1}^{3}, δ)

||Hessian(F̃)||_{2} ⩽ ||(\begin{matrix}228 & 117 & 117 \\ 117 & 228 & 117 \\ 117 & 117 & 228 \end{matrix})||_{2} < 488,

as desired. And the same estimate of the Hessian applies for θ ≈ 1.5379684120790425.

Apply now the Hessian estimate to ||∇_{ℝ^{3}}f(b)||_{2} ⩽ ||∇_{ℝ^{3}}f(a)||_{2} +δ sup_{x⃗∈B_{2}^{3}(a,δ)} ||Hessian(f)(x⃗)||_{2}, which holds for every sufficiently smooth f: ℝ^{3} → ℝ if a, b ∈ ℝ^{3} satisfy ||b − a||_{2} ⩽ δ. We then explicitly calculate ||∇_{ℝ^{3}}F_{0}|_{{arccos(−1/3)}_{i=1}^{3}}||_{2} < 13.6 and ||∇_{ℝ^{3}}F_{0}|_{{1.5379684}_{i=1}^{3}}||_{2} < 9.7. So, in B_{2}^{3}({arccos(−1/3)}_{i=1}^{3}, δ) we have ||∇_{ℝ^{3}}F_{0}||_{2} < 13.6 + 4.88 and in B_{2}^{3}({1.5379684}_{i=1}^{3}, δ) we have ||∇_{ℝ^{3}}F_{0}||_{2} < 9.7 + 4.88, proving the claim. □

Lemma 4.2. We may assume that \sqrt{λ} > .18.

Proof. Substituting in (31), det(v_{2}, v_{1}, v_{4}) = det(v_{1}, v_{2}, v_{3})\frac{sin θ_{12}}{θ_{12}} \frac{1}{\sqrt{λ}}. Using (44),

|det(v_{2}, v_{1}, v_{4})| > |det(v_{1}, v_{2}, v_{3})| \frac{sin(1/2)}{\sqrt{λ} (π − 1/2)}.  (66)

Now, suppose \sqrt{λ} < sin(1/2)/(π − 1/2), and \sqrt{λ′} < sin(1/2)/(π − 1/2), with λ′ defined by

λ′ = ||\frac{sin θ_{12}}{θ_{12}} v_{4} + \frac{sin θ_{24}}{θ_{24}} v_{1} + \frac{sin θ_{14}}{θ_{14}} v_{2}||_{2}^{2}

Applying (66) twice (with indices changed appropriately) shows |det(v_{2}, v_{1}, v_{4})| > |det(v_{1}, v_{2}, v_{3})| and |det(v_{2}, v_{1}, v_{4})| < |det(v_{1}, v_{2}, v_{3})|, a contradiction. We may therefore assume that one triangle of P (which, up to relabeling, is T_{4}) satisfies \sqrt{λ} > (sin(1/2)/(π − 1/2)) > .18. □

We now derive some modulus of continuity and derivative estimates for our system (65). Recall that P = {T_{i}}_{i=1}^{4} satisfies Proposition 3.1(e). Since (65) must hold for the data of each individual triangle T_{i}, we select in (65) the data from the triangle T_{4}. Then θ_{12} + θ_{23} + θ_{13} ⩽ 2π, since the perimeter of T_{4} is bounded by 2π. By relabeling the edges of T_{4} and using the pigeonhole principle, we may assume θ_{12} ⩽ 2π/3. The following summary of (65) holds for any labeling of the form {i, j, ℓ} = {1, 2, 3}.

\begin{cases}θ_{ij} + θ_{jℓ} > θ_{iℓ} & , triangle inequality on the sphere \\ θ_{12} + θ_{23} + θ_{13} ⩽ 2π \\ θ_{12} ⩽ 2π/3 \\ θ_{13}, θ_{23} ⩽ π − 1/2 & , (44) \\ max_{i,j∈\{1,2,3\},i≠j}\{θ_{ij}\} ⩾ π \frac{3}{2\sqrt{14}} & , Corollary 3.11 \\ θ_{ij} ⩾ 1/10 & , Lemma 3.16 \\ sin Θ_{ijℓ} ⩾ 1/10 & , Lemma 3.16 \\ \sqrt{λ} > .18 & , Lemma 4.2 \end{cases}  (67)

For a map f: (X, ||·||_{X}) → (Y, ||·||_{Y}) between two normed linear spaces, a modulus of continuity for f, denoted by ω_{f}, satisfies ||f(x_{1}) − f(x_{2})||_{Y} ⩽ ω_{f}(||x_{1} − x_{2}||_{X} , x_{1}, x_{2}). We allow ω_{f} to depend on x_{1}, with x_{2} in a δ-ball around some given point x_{1} = (θ_{12}, θ_{13}, θ_{23}).

Lemma 4.3. Suppose δ < 1/100, and consider H_{1} : ([0, π]^{3}, ||·||_{∞}) → ℝ, H_{1} = H_{1}(θ_{12}, θ_{13}, θ_{23}). Suppose also that λ = λ(θ_{12}, θ_{13}, θ_{23}) > η. Then, in an ℓ_{∞} ball of radius δ centered at (θ_{12}, θ_{13}, θ_{23}), the following holds

ω_{H_{1}}(δ) ⩽ G(δ, θ⃗, η) = δ [\frac{7}{2} + \frac{15}{2\sqrt{η − 15δ}} + 3(2(θ_{12} + δ) + 2(θ_{13} + δ)
+ (θ_{12} + δ)(θ_{13} + δ) (\frac{2}{sin(θ_{12} + δ)} + \frac{2}{sin(θ_{13} + δ)} + \frac{1}{sin(θ_{12} + δ) sin(θ_{13} + δ)})) ].

(68)

Or, applying Lemma 4.2, for δ sufficiently small,

ω_{H_{1}}(δ) ⩽ δ [\frac{7}{2} + \frac{15}{2\sqrt{.0329 − 15δ}} + 3(2(θ_{12} + δ) + 2(θ_{13} + δ)
+ (θ_{12} + δ)(θ_{13} + δ) (\frac{2}{sin(θ_{12} + δ)} + \frac{2}{sin(θ_{13} + δ)} + \frac{1}{sin(θ_{12} + δ) sin(θ_{13} + δ)})) ].

(69)

Proof. We want to compute the modulus for the following function from (ℝ^{3}, ||·||_{∞}) to ℝ

H_{1}(θ_{12}, θ_{13}, θ_{23}) = \sqrt{λ} cos (\sqrt{θ_{12}^{2} + θ_{13}^{2} + 2θ_{12}θ_{13} cos Θ_{213}}) + γ_{1}

where λ and γ_{1} are defined in (33) and (64) respectively. In what follows, we use the product rule, chain rule, and sum rule for the modulus ω_{(·)}.

ω_{H_{1}}(δ) ⩽ ω\sqrt{λ}(δ) + ||\sqrt{λ}||_{∞} · ω_{cos}(\sqrt{θ_{12}^{2}+θ_{13}^{2}+2θ_{12}θ_{13} cos Θ_{213}})(δ) + ω_{γ_{1}}(δ)

⩽ ω\sqrt{λ}(δ) + 3 · \frac{1}{2} · ω_{(θ_{12}^{2}+θ_{13}^{2}+2θ_{12}θ_{13} cos Θ_{213})}(δ) + \frac{7}{2}δ.

Here we used λ ⩽ 9, \sqrt{λ} ⩽ 3, |\frac{d}{dt}(cos(\sqrt{t}))| ⩽ 1/2, |(sin t)/t| ⩽ 1, and |\frac{d}{dt}((sin t)/t) ⩽ 1/2|. Also, the term (7/2)δ appears since δ^{−1}ω_{γ_{1}}(δ) ⩽ ||∇_{ℝ^{3}}γ_{1}(θ_{12}, θ_{13}, θ_{23})||_{1} ⩽ 7/2. Now, observe that

\frac{∂λ}{∂θ_{12}} = 2\frac{sin θ_{12}}{θ_{12}} ( \frac{d}{dx} \frac{sin x}{x}|_{x=θ_{12}}) + 2\frac{sin θ_{13} sin θ_{23}}{θ_{13}θ_{23}} (− sin θ_{12})

+ 2 ( \frac{d}{dx} \frac{sin x}{x}|_{x=θ_{12}}) \frac{sin θ_{13}}{θ_{13}} cos θ_{23} + 2 ( \frac{d}{dx} \frac{sin x}{x}|_{x=θ_{12}}) \frac{sin θ_{23}}{θ_{23}} cos θ_{13}.

So, taking absolute values, and using that |sin(t)/t| ⩽ 1 and |\frac{d}{dt}(sin(t)/t)| ⩽ 1/2, we see that |∂λ/∂θ_{ij}| ⩽ 5. So, if λ(θ⃗) = λ(θ_{12}, θ_{13}, θ_{23}) > η > 0 for some η, and if x⃗ = (x, y, z) satisfies |x − θ_{12}| < δ, |y − θ_{13}| < δ, |z − θ_{23}| < δ, then at x⃗,

|\frac{∂(\sqrt{λ})}{∂θ_{12}} | ⩽ max_{\{θ⃗∈ℝ^{3} : ||θ⃗−x⃗||_{∞}<δ\}} \frac{1}{2} \frac{1}{\sqrt{λ(θ⃗)}} · \frac{∂λ(θ⃗)}{∂θ_{12}} ⩽ \frac{1}{2} \frac{1}{\sqrt{η − ||∇_{ℝ^{3}}λ||_{1} δ}} · 5 ⩽ \frac{1}{2} \frac{1}{\sqrt{η − 15δ}} · 5.

Therefore, for such x⃗,

||∇_{ℝ^{3}}(\sqrt{λ})||_{1} ⩽ \frac{15}{2\sqrt{η − 15δ}} .

Combining this estimate with our estimate above, we get the following modulus estimate, that applies to x⃗, θ⃗ as just described

ω_{H_{1}}(δ) ⩽ δ [\frac{7}{2} + \frac{15}{2\sqrt{η − 15δ}} + 3(2(θ_{12} + δ) + 2(θ_{13} + δ)
+ (θ_{12} + δ)(θ_{13} + δ) (\frac{2}{sin(θ_{12} + δ)} + \frac{2}{sin(θ_{13} + δ)} + \frac{1}{sin(θ_{12} + δ) sin(θ_{13} + δ)})) ].

We used here the monotonicity of the function x ↦ x/ sin x and the following identities for ψ(θ_{12}, θ_{13}, θ_{23}) = (θ_{12}^{2} + θ_{13}^{2} + 2\frac{θ_{12}θ_{13}}{sin θ_{12} sin θ_{13}} (cos θ_{23} − cos θ_{12} cos θ_{13})),

\frac{1}{2} \frac{∂ψ}{∂θ_{12}} = θ_{12} + \frac{θ_{12}θ_{13}}{sin θ_{12} sin θ_{13}} (sin θ_{12} cos θ_{13})
+ (cos θ_{23} − cos θ_{12} cos θ_{13})(θ_{12}/ sin θ_{12})′ · (θ_{13}/ sin θ_{13})

= θ_{12} + \frac{θ_{12}θ_{13}}{sin θ_{13}} cos θ_{13} + cos Θ_{213} (1 − \frac{θ_{12}}{tan θ_{12}} ) θ_{13},

\frac{1}{2} \frac{∂ψ}{∂θ_{13}} = θ_{13} + \frac{θ_{12}θ_{13}}{sin θ_{12} sin θ_{13}} (sin θ_{13} cos θ_{12})

+ (cos θ_{23} − cos θ_{12} cos θ_{13})(θ_{13}/ sin θ_{13})′ · (θ_{12}/ sin θ_{12})

= θ_{13} + \frac{θ_{12}θ_{13}}{sin θ_{12}} cos θ_{12} + cos Θ_{213} (1 − \frac{θ_{13}}{tan θ_{13}} ) θ_{12},

\frac{1}{2} \frac{∂ψ}{∂θ_{23}} = \frac{θ_{12}θ_{13}}{sin θ_{12} sin θ_{13}} (− sin θ_{23}).
□

Analogous estimates give a gradient bound for F_{0}, as defined in (43). Since F_{0} is symmetric in its arguments, it suffices to take a derivative with respect to one variable. Fix (θ_{12}, θ_{13}, θ_{23}), and let 0 < δ < 1/100. For any (x, y, z) such that |x − θ_{12}| < δ, |y − θ_{13}| < δ, |z − θ_{23}| < δ we have the following derivative bound

|\frac{∂F_{0}}{∂θ_{12}} | ⩽ 6(θ_{12} + δ) + \frac{2(θ_{13} + δ)(θ_{23} + δ)}{sin(θ_{13} + δ) sin(θ_{23} + δ)} + 2\frac{(θ_{12} + δ)(θ_{13} + δ)}{sin(θ_{13} + δ)}

+ 2\frac{(θ_{12} + δ)(θ_{23} + δ)}{sin(θ_{23} + δ)} + 2(θ_{13} + θ_{23} + 2δ) (1 − \frac{θ_{12} + δ}{tan(θ_{12} + δ)})

(70)

The restrictions of (67) and the bounds of (68) and (70) finally yield Theorem 1.1.

Proof of Theorem 1.1. Let P be a partition of the sphere S^{2} that maximizes ∑_{i=1}^{4} ||z_{i}||_{2}^{2}. Arguing by contradiction, we may assume that this partition exceeds the value of the spherical propeller partition, 9π^{2}/4. From Proposition 3.1 we may assume that P is a collection of four nonempty spherical triangles along with four vertices such that det(v_{1}, v_{2}, v_{3}) > 0. Since P is a global maximum of F, it satisfies three equations in the three variables {θ_{12}, θ_{13}, θ_{23}} defined by (65). We may restrict these variables via (67). We may also exclude neighborhoods of the two candidate maxima found in Section 3, using Lemma 4.1. Combining the estimates of (68),(69) and (70) gives sufficient information for an ε-net traversal of the parameter space defined by (67). This numerical computation finds that no zeros of the system (65), within the parameter space defined by (67), exceed the objective value of the propeller partition. This computation contradicts the assumed existence of a maximal P with four nonempty elements. So, recalling (8), ∑_{i=1}^{4} ||z_{i}||_{2}^{2} ⩽ 9π^{2}/4 = 2π^{3}(9/(8π)). □

4.1. Implementation. We describe the ε-net traversal of Theorem 1.1 further below. Before doing so, we describe some issues related to the numerical verification of inequalities. In particular, we discuss how a computer can rigorously verify a mathematical statement. Recall that a normal double precision floating point number in the IEEE-754-2008 standard is a number in base two of the form

±1.a_{1}a_{2}a_{3} ⋯ a_{52} × 2^{b_{1}b_{2}···b_{11}−2^{10}},

where a_{i} ∈ {0, 1} and b_{1}b_{2} ⋯ b_{11} ∈ [2, 2^{11} − 1] ∩ ℤ. All of our computations are done with this discrete set of numbers, with zero included as well. Note that the distance between two consecutive numbers changes according to the values of the two numbers. For example, the distance between 1 and the next largest number is 2^{−52}, whereas the distance between 2 and the next largest number is 2^{−51}. (In general, if the number 2^{k} and the next largest number can be represented in this system, then their distance is 2^{−52+k}.) Due to this spacing between numbers, one must round the result of any arithmetic operation. For example, the addition 1 + 2^{−54} evaluates to 1, if we choose to round to the nearest double precision number. For the sake of flexibility, our analysis below applies regardless of the rounding scheme that is chosen.

For x, y ∈ [0, 2^{500}] where x, y are normal double precision numbers, let fl(x + y) denote the normal double precision number that is evaluated in a computer with the IEEE-754-2008 standard. It suffices for now to note that (x + y) ⩽ (1 + 2 · 2^{−52})fl(x + y). In this case, we say that (x + y) has multiplicative error bounded by (1 + 2 · 2^{−52}). When we speak of numerical error, we mean multiplicative error, unless otherwise stated. Define

ε = 3 · 2^{−52}.

To verify inequalities in our numerical computations, we perform operations for several floating point numbers and keep track of error bounds of the form (x + y) ⩽ (1 + 2 · 2^{−52})fl(x + y). Since (1 + 2 · 2^{−52})^{N} ⩽ (1 + N · 3 · 2^{−52}) = (1 + Nε) for 1 ⩽ N ⩽ 30000, we can bound the multiplicative error of N operations with a multiplicative term of the form (1 + Nε). (Here and below we are overly conservative in our error estimates.)

We now present the formulas that are used in our computations, delaying further discussion of numerical errors. Let x, y > 0 be two normal double precision floating point numbers with x > y. A loss of significance refers to a loss of binary significant digits in the computation of fl(x − y). One can show that fl(x − y) loses at most q and at least p significant binary digits, where 2^{−q} ⩽ 1 − (y/x) ⩽ 2^{−p}. Due to potential loss of significance errors, we evaluate λ as

λ = (\frac{sin^{2} θ_{23}}{θ_{23}^{2}} + \frac{sin^{2} θ_{13}}{θ_{13}^{2}} + \frac{sin^{2} θ_{12}}{θ_{12}^{2}} ) + 2 (\frac{sin θ_{23} sin θ_{13}}{θ_{23}θ_{13}} cos θ_{12}

+ \frac{sin θ_{23} sin θ_{12}}{θ_{23}θ_{12}} cos θ_{13} + \frac{sin θ_{12} sin θ_{13}}{θ_{12}θ_{13}} cos θ_{23}) .

(71)

Our numerical computation of inequalities consists of four steps. (Step (i)) Suppose we want to check (67) for a closed ℓ_{∞} ball (i.e. a cube) of radius δ with center (θ_{12}, θ_{13}, θ_{23}) ∈ [0, π]^{3}. To do so, we must verify the following perturbation of (67).

\begin{cases}(θ_{ij} + θ_{jℓ} + 3δ) ⩾ θ_{iℓ} \\ θ_{12} + θ_{23} + θ_{13} ⩽ (2π + 3δ) \\ θ_{12} ⩽ (2π/3 + δ)(1 + 10ε) \\ θ_{13} + 1/2, θ_{23} + 1/2 ⩽ (π + δ)(1 + 10ε) \\ (δ + max_{i,j∈\{1,2,3\},i≠j}\{θ_{ij}\})(1 + 7ε) ⩾ π \frac{3}{2\sqrt{14}}(1 − 5ε) \\ (θ_{ij} + δ)(1 + 7ε) ⩾ (1/10)(1 − ε) \\ −(3δ + \frac{\sqrt{99}}{10}(sin θ_{ij} sin θ_{jℓ} + 2δ))(1 + 1500ε) ⩽ (cos θ_{iℓ} − cos θ_{ij} cos θ_{jℓ} + 2000ε) \\ (cos θ_{iℓ} − cos θ_{ij} cos θ_{jℓ} − 2000ε) ⩽ (3δ + \frac{\sqrt{99}}{10}(sin θ_{ij} sin θ_{jℓ} + 2δ))(1 + 1500ε) \\ (15δ + 2 · 10^{4}ε + λ) ⩾ .03293 \end{cases}  (72)

If a given inequality of (72) does not hold, then the corresponding inequality of (67) is violated for the entire ℓ_{∞} ball of radius δ. (Step (ii)) If all of the inequalities of (72) are satisfied, we then check if (θ_{12}, θ_{13}, θ_{23}) lies in a neighborhood of two of our known candidate global optima. Let x⃗ = (x_{1}, x_{2}, x_{3}) ∈ [0, π]^{3}. Suppose x_{1} = x_{2} = x_{3} = arccos(−1/3) or x_{1} = x_{2} = x_{3} = 1.5379684120790425. From Lemma 4.1, we know that if θ⃗ = (θ_{12}, θ_{13}, θ_{23}) is close to x⃗, then F is bounded by (9/4)π^{2} in \overline{B_{∞}^{3}}((θ_{12}, θ_{13}, θ_{23}), δ). That is, if the following is not satisfied, then F is bounded as just stated.

[(d_{ℓ_{2}}(θ⃗, x⃗))^{2} + 40000ε + 2δ (d_{ℓ_{1}}(θ⃗, x⃗) + 6000ε + 3δ)] (1 + 20ε) > ((1/100)^{2})(1 − 2ε).  (73)

Here d_{ℓ_{2}} and d_{ℓ_{1}} denote the usual ℓ_{2} and ℓ_{1} metrics on ℝ^{3}. (Step (iii)) If the verification of (73) fails, we use the modulus estimates of Lemma 4.3 to see if H is near zero at θ⃗, with H = (H_{1}, H_{2}, H_{3}) defined after (65). Let α, β, ρ, σ ∈ {±1}. We first check if the following expression has constant sign, over the 2^{4} such choices of α, β, ρ, σ.

[cos (\sqrt{θ_{12}^{2} + θ_{13}^{2} + 2θ_{12}θ_{13} (\frac{cos θ_{23} − cos θ_{12} cos θ_{13} + 2000εα}{sin θ_{12} sin θ_{13}})} ) + 25000εβ]

· \sqrt{λ − 2 · 10^{4}εσ} + (γ_{1} + 3000ερ).

(74)

If (74) is well-defined and its sign is constant, we then consider the following inequalities involving H_{i} for i = 1 and (68).

min_{α,β,ρ,σ∈\{±1\}} |[cos (\sqrt{θ_{12}^{2} + θ_{13}^{2} + 2θ_{12}θ_{13} (\frac{cos θ_{23} − cos θ_{12} cos θ_{13} + 2000εα}{sin θ_{12} sin θ_{13}})} ) + 25000εβ]

· \sqrt{λ − 2 · 10^{4}εσ} + (γ_{1} + 3000ερ)|(1 − 3000ε) > (1 + 3000ε)G(δ, θ⃗, λ − 2 · 10^{4}ε).

(75)

min_{α,β,ρ,σ∈\{±1\}} |[cos (\sqrt{θ_{12}^{2} + θ_{13}^{2} + 2θ_{12}θ_{13} (\frac{cos θ_{23} − cos θ_{12} cos θ_{13} + 2000εα}{sin θ_{12} sin θ_{13}})} ) + 25000εβ]

· \sqrt{λ − 2 · 10^{4}εσ} + (γ_{1} + 3000ερ)|(1 − 3000ε)

> (1 + 5ε)\sqrt{15δ} + δ(1 + 3000ε) [\frac{7}{2} + 3(2(θ_{12} + δ) + 2(θ_{13} + δ)

+ (θ_{12} + δ)(θ_{13} + δ) (\frac{2}{sin(θ_{12} + δ)} + \frac{2}{sin(θ_{13} + δ)} + \frac{1}{sin(θ_{12} + δ) sin(θ_{13} + δ)})) ].

(76)

The inequalities for H_{2} and H_{3} are constructed by permuting cyclically the indices appearing above. If at least one of (75) and (76) is satisfied (for at least one H_{i}), then H_{i} is nonzero on \overline{B_{∞}^{3}}((θ_{12}, θ_{13}, θ_{23}), δ). (Step (iv)) If (75) and (76) are not satisfied for {H_{i}}_{i=1}^{3}, we finally check the value of F_{0} directly, using a modification of (43). Define

cos Θ_{ijk}^{ε} = (\frac{cos θ_{ik} − cos θ_{ij} cos θ_{jk} + 2000ε}{sin θ_{ij} sin θ_{jk}})
F_{0}^{ε} = 3 (θ_{12}^{2} + θ_{23}^{2} + θ_{13}^{2}) + 2 cos(Θ_{213}^{ε})θ_{12}θ_{13} + 2 cos(Θ_{123}^{ε})θ_{12}θ_{23} + 2 cos(Θ_{231}^{ε})θ_{23}θ_{13},
G_{12}^{ε}(θ⃗, δ) = 6(θ_{12} + δ) + \frac{4(θ_{13} + δ)(θ_{23} + δ)}{sin(θ_{13} + δ) sin(θ_{23} + δ)} + 2\frac{(θ_{12} + δ)(θ_{13} + δ)}{sin(θ_{13} + δ)}

+ 2\frac{(θ_{12} + δ)(θ_{23} + δ)}{sin(θ_{23} + δ)} + 2(θ_{13} + θ_{23} + 2δ) [1 − (\frac{θ_{12} + δ}{tan(θ_{12} + δ)}(1 + 1200ε) + ε)] .

If the following is satisfied, then F_{0} is bounded by (9/4)π^{2} in \overline{B_{∞}^{3}}((θ_{12}, θ_{13}, θ_{23}), δ), and therefore F satisfies the same bound for any global maximum of F in this ball.

(9/4)π^{2}(1 − 5ε) − F_{0}^{ε} · (1 + 5000ε) > δ(G_{12}^{ε} + G_{13}^{ε} + G_{23}^{ε})(1 + 10^{4}ε) + 100ε.  (77)

Given these estimates, we can now describe the ε-net traversal of Theorem 1.1. We need a discrete subset N = {x_{i}} ⊆ [0, π]^{3} together with a set of radii δ_{i} > 0 such that

⋃_{x_{i}∈N} \overline{B_{∞}^{3}}(x_{i}, δ_{i}) ⊇ [0, π]^{3},

and such that one of the following cases occurs, for (x_{i}, δ_{i}) with x_{i} ∈ N.

(i) One inequality of (72) does not hold.

(ii) (73) does not hold.

(iii) (75) or (76) holds, and (74) has constant sign over all sign choices α, β, σ, ρ ∈ {±1}.

(iv) (77) holds.

In case (i), \overline{B_{∞}^{3}}(x_{i}, δ_{i}) is either outside of the domain of (65) or (65) cannot be satisfied in \overline{B_{∞}^{3}}(x_{i}, δ_{i}). Case (ii) implies that F = ∑_{i=1}^{4} ||z_{i}||_{2}^{2} is bounded by (9/4)π^{2} on \overline{B_{∞}^{3}}(x_{i}, δ_{i}). Cases (iii) and (iv) imply that no global maximum of F occurs in \overline{B_{∞}^{3}}(x_{i}, δ_{i}). So, the existence of N as defined above completes the proof of Theorem 1.1.

To construct N, we perform the following standard procedure. Begin with the grid

N_{0} = \frac{π}{100}([0, 100]^{3} ∩ ℤ^{3}) ⊆ [0, π]^{3}.

For each point x ∈ N_{0}, check the inequalities discussed above with δ = δ_{0} = π/200. If we discover that x satisfies one of (i) through (iv), then eliminate x from the set N_{0}. Next, include the element (x, δ) in the set N. Let N′_{0} be the set of all points x ∈ N_{0} that have not been included in N. We now “refine” the grid N′_{0} by a factor of 10 and repeat the above procedure. That is, we define

N_{1} = (\frac{π}{1000}([0, 1000]^{3} ∩ ℤ^{3})) ∩ ( ⋃_{x_{i}∈N′_{0}} \overline{B_{∞}^{3}}(x_{i}, π/200)) .

For each point x ∈ N_{1}, we now check (i)-(iv) with δ = δ_{1} = π/2000, and so on. For j ⩾ 1, at the j^{th} iteration of this algorithm, we define

N_{j} = (\frac{π}{10^{j+2}} ([0, 10^{j+2}]^{3} ∩ ℤ^{3})) ∩ ( ⋃_{x_{i}∈N′_{j−1}} \overline{B_{∞}^{3}}(x_{i}, π/(2 · 10^{j+1}))) .

We continue in this manner until the procedure terminates. Upon termination at the j^{th} step, N′_{j} = ∅, so N satisfies our desired properties and proves Theorem 1.1.

We now return to our discussion of numerical error. To keep track of rounding errors resulting from subtractions, we use absolute error where appropriate and add the ε terms that correspond to absolute numerical errors. These additive terms are scaled according to the absolute value of the numbers being subtracted (due to the unequal spacing of floating point numbers described above).

In the description and analysis of (i) through (iv), δ terms come from modulus of continuity estimates, and ε terms account for numerical error. The latter is discussed further below. The first two inequalities of (72) contain no ε terms, since they can be checked in exact arithmetic. Let x ∈ [0, π − 1/2 + 2 × 10^{−2}]. (We make this restriction due to the fourth inequality of (72).) Let us discuss the numerical computation of the sine function. If x > π/2, we replace x with π − x, and we evaluate sin(π − x). Thus, we only need to consider x ∈ [0, π/2]. For such x, we first use a 19^{th} degree (ten term) Taylor expansion around zero, summing terms in ascending degree. In perfect arithmetic, we get a multiplicative error of one plus

|\frac{x^{21}}{(21!) sin(x)}| = |\frac{x}{sin(x)} \frac{x^{20}}{(21!)}| ⩽ \frac{π}{2} \frac{(π/2)^{20}}{21!} < 2.6 × 10^{−16} < \frac{ε}{2}.

Since x ∈ [0, π/2], there are no loss of significance errors in the summation of the series. The addition of each term of the Taylor series involves one operation, and there are ten such terms. Moreover, the n^{th} term contains n + 1 operations. In total, one evaluation therefore has less than 210 operations. So, very conservatively, the multiplicative error of sin(x) is bounded by (1 + 250ε), if x is represented exactly. If the argument x has multiplicative error (1 + kε), then this same analysis shows that the multiplicative error of sin(x) is bounded by (1 + (250 + 100k)ε), since the term x appears 100 times in the formula for sin. For example, since θ_{ij} has multiplicative error (1 + 3ε), we conservatively bound the error of sin θ_{ij} by (1 + 550ε).

To compute cos(x) for x ∈ [0, π − 1/2 + 2 × 10^{−2}], we instead compute sin(π/2 − x) with the procedure outlined above. Due to our representation of the points θ_{ij}, we compute π/2 − x as a rational multiple of π, so no loss of significance errors occurs in this subtraction. Hence, the error estimates for cos θ_{ij} are exactly the ones already used for sin θ_{ij}. However, when evaluating the cosine of more complicated expressions, we need to revert to absolute errors.

We will also need to use the square root function. Here we use the usual Newton’s Method iteration, which is well known to have multiplicative error bounded by (1 + ε).

We now describe the error terms appearing in (72), which are perturbations of (67). The guiding principle is that we want to perturb each inequality so that it is more easily satisfied. To see why this is done, suppose an inequality of (72) is not satisfied. Then, a modulus of continuity estimate and a numerical error estimate, used in the definition of (72), show that the corresponding inequality of (67) is not satisfied in an ℓ_{∞} ball of radius δ. For example, contrast the first inequality of (67) with that of (72). We need only add an additional δ term for each θ_{ij} term, since the modulus of continuity of the function (x, y, z) ↦ x + y + z, viewed as a mapping from (ℝ^{3}, ||·||_{∞}) → ℝ, is exactly 3δ.

So, if the inequality of (72) is violated at a given point θ⃗ = (θ_{12}, θ_{13}, θ_{23}), then the modulus of continuity bound shows that the corresponding inequality of (67) is violated in the ball \overline{B_{∞}^{3}}(θ⃗, δ). The same considerations apply to the second inequality of (72). Note that the first and second inequality are checked in exact arithmetic in our computer implementation, so we do not need to take into account numerical error. As we have mentioned above, our θ_{ij} and δ are represented as numbers of the form π(a/c) where a and c are integers, and it suffices to perform additions of the form π((a + b)/c), and the integer addition a + b can be performed with no error.

The third inequality of (72) only requires a modulus of continuity term of δ. However, we must now take into account numerical errors. We count ten numerical operations on positive numbers (including the error in representing π as a floating point number three times), so in the worst case, the multiplicative error is bounded by (1 + 10ε). Similar considerations apply in the next three inequalities. In the seventh and eighth inequalities, we use our analysis of the sine function, and recall that the multiplicative error for these operations is always bounded by 1 + 550ε. So, in total, the evaluation of the term −(3δ + \frac{\sqrt{99}}{10}(sin θ_{ij} sin θ_{jℓ} + 2δ)) has multiplicative error bounded by 1 + 1500ε. Here we have also included δ terms corresponding to the moduli of continuity, as before.

Unfortunately, we cannot use multiplicative error to deal with the cosine terms, since loss of significance can occur in the evaluation of (cos θ_{iℓ} − cos θ_{ij} cos θ_{jℓ}). However, since the cosine terms are bounded by 1 in absolute value, the absolute error from each cosine evaluation is bounded by 550ε. Therefore the total absolute error from the right hand side of the seventh inequality is bounded by 2000ε. This bound applies similarly to the penultimate inequality of (72). The final inequality of (72) is similar to the previous cases. To get the δ terms, we examine (71) and use that |(sin(x)/x)′| < 1/2 and |sin(x)/x| ⩽ 1 for x ∈ [0, π]. To get the ε terms, note that each term sin^{2} θ_{ij}/θ_{ij}^{2} has absolute error bounded by 1200ε. And each term sin θ_{ij} sin θ_{jk} cos θ_{ik}/θ_{ij}θ_{jk} has absolute error bounded by 1700ε. The total absolute error of λ is therefore bounded by 2 · 10^{4}ε.

We now treat (73). First, recall that (18) yielded our two known zeros of the system (65). The first zero θ_{ij} = θ = arccos(−1/3) is known exactly (up to multiplicative error (1 ± ε)). However, we can only find the second zero computationally. For the purposes of our computations, we therefore show that this second zero is contained in an interval of the form θ_{ij} = θ ∈ [x − 2000ε, x + 2000ε] where x = 1.5379684120790425. To see this, we take (18) and write it as a quotient of the left side over the right side, and we wish to find where the quotient is 1. For θ ∈ [x − 2000ε, x + 2000ε], the multiplicative error involved in calculating this quotient is bounded by 1 + 3000ε. This follows by our analysis of the sine and cosine functions, and since this particular region of parameters avoids loss of significance errors. We can then check numerically that, for θ = x − 2000ε, this quotient, multiplied by (1 + 3000ε) is less than 1, while for θ = x + 2000ε, the quotient, multiplied by (1−3000ε), is greater than 1. So, by our numerical analysis and continuity of the given function, a solution of (18) must lie in the interval θ ∈ [x − 2000ε, x + 2000ε].

We can now confront the errors of (73). Once again, the guiding principle is to add error terms so that the inequality is more easily satisfied. First, the term d_{ℓ_{2}}(θ⃗, x⃗)^{2} is the sum of three squared differences. Due to numerical error in the operations, and the uncertainty of the zero θ_{ij} ≈ 1.5379684120790425, each squared difference has an absolute error bounded by 2π(2000ε) + 100ε. (The factor of 2π comes from the squaring of the difference, and since |x| ⩽ π.) So, in total, the absolute error from the term d_{ℓ_{2}}(θ⃗, x⃗)^{2} is bounded by 40000ε. Since we want to check this inequality in an ℓ_{∞} ball of radius δ, we use the modulus of continuity of d_{ℓ_{2}}^{2}, which is 2δd_{ℓ_{1}}. We therefore add the term 2δd_{ℓ_{1}}(θ⃗, x⃗), and again add terms to this quantity to take into account its own absolute error and its own modulus of continuity. The combined effect of summing the error terms then accumulates a multiplicative error bounded by 1 + 20ε.

We now explain the error terms of (75). From the analysis of the cosine, we know that cos θ_{ij} for θ_{ij} ∈ [0, π − 1/2 + 2 × 10^{−2}] has an absolute error bounded by 550ε. (This follows since the multiplicative error is bounded by (1 + 550ε), and |cos(·)| ⩽ 1.) So, the expression cos θ_{23} − cos θ_{12} cos θ_{13} has absolute error bounded by 2000ε. The remaining operations under the square root of (75) all have multiplicative error bounded by (1 + 1200ε).

When the cosine of the square root term is evaluated, we need to again take into account absolute errors (since, unlike in the cos θ_{ij} terms, we must now account for loss of significance). Since the argument of the cosine term is bounded by π, we can bound the absolute error of the square root term by 4000ε. To take the cosine of the square root term, we need to return to our Taylor series analysis. Note that our Taylor series has Lipschitz constant bounded by 6. (This is a conservative bound that does not account for cancelations in the series summation.) Therefore, the total absolute error of the cosine of the square root in (75) is bounded by 25000ε. From before, the absolute error in the computation of λ in (71) is bounded by 2·10^{4}ε. Similarly, the computation of γ_{1} has absolute error bounded by 3000ε.

Temporarily ignoring any numerical errors, note that we are computing a bound for the absolute value of the derivative of a function. So, in order to conclude anything from (75), the sign of (74) must be constant over all possible numerical errors. (If not, it may be that (74) has an actual value of zero.) Given that this sign is constant, we then take the minimum over all possible numerical errors. It then suffices to take the minimum over the extreme points of a suitable rectangle, due to monotonicity of (75) with respect to the error terms. Note that we take the minimum since we wish to make the inequality more difficult to be satisfied. Finally, the addition of all terms on the left side of the inequality incurs a multiplicative error bounded by 1 + 3000ε, and the addition of the terms on the right side has multiplicative error bounded by 1 + 3000ε. A similar analysis applies to (76).

We now briefly mention the analysis of (77), which is routine at this stage. The principle that we apply here is to make (77) more difficult to be satisfied, so we make its right side larger and its left side smaller. The multiplicative error of the F_{0}^{ε} term is bounded by 1 + 5000ε, since each cos Θ_{ijk}^{ε} term has multiplicative error bounded by 1 + 1200ε. Each G_{ij}^{ε} term has multiplicative error bounded by 1 + 2500ε, so the right side of (77) has multiplicative error bounded by 1 + 10^{4}ε. A 100ε term is added to the right side of (77) to account for the error of the subtraction on the left side. The 1 + 1200ε term and the ε term in the definition of G_{ij}^{ε} account for the errors of the tangent function, and the loss of significance in the subtraction that occurs in the square brackets.

5. Discrete Harmonic Maps into the Sphere

We now summarize and reinterpret the results of Section 3. Recall that we defined G(P) = ∑_{1⩽i<j⩽4} θ_{ij}^{2} as the sum of the squared lengths of the edges of our partition P. We then saw from Propositions 3.13 and 3.1 that all maxima of F are also critical points of G. We also found that critical points of G satisfy (51). Given a partition P, think of its edges as rubber bands. (Recall that a rubber band has energy given by its length squared, and it exerts a force proportional to its length.) The critical points of G are given by configurations of rubber bands (arranged like the edges of Figure 2(b)) that are at equilibrium with respect to the forces exerted by the rubber bands. With this interpretation, (51) becomes intuitively clear. This equation says that, at a fixed vertex, the (tangential) forces of the incident rubber bands are in equilibrium. (For the Euclidean version of this, see e.g. [10] and [31].)

These considerations lead us naturally to the following generalization. Let (V, E) be a (finite) graph. Let u: (V, E) → S^{2} be an embedding of (V, E) into S^{2} (u is sometimes called a map). To be consistent with the above, let u(V) = \{v_{i}\}, and label Length(u(\overline{v_{i}v_{j}})) = θ_{ij} where \overline{v_{i}v_{j}} denotes a spherical geodesic connecting v_{i} to v_{j}. Then a harmonic map u is a critical point of the energy functional ∑_{{i,j}∈E} θ_{ij}^{2}.

References

[1] K. Appel and W. Haken. Every planar map is four colorable. I. Discharging. Illinois J. Math., 21(3):429–490, 1977.

[2] K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. II. Reducibility. Illinois J. Math., 21(3):491–567, 1977.

[3] K. Ball. Cube slicing in R^{n}. Proc. Amer. Math. Soc., 97(3):465–473, 1986.

[4] K. Ball. Mahler’s conjecture and wavelets. Discrete Comput. Geom., 13(3-4):271–277, 1995.

[5] F. Barthe and A. Koldobsky. Extremal slabs in the cube and the Laplace transform. Adv. Math., 174(1):89–114, 2003.

[6] F. Barthe and A. Naor. Hyperplane projections of the unit ball of l_{p}^{n}. Discrete Comput. Geom., 27(2):215–226, 2002.

[7] C. Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete, 70(1):1–13, 1985.

[8] M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The Grothendieck constant is strictly smaller than Krivine’s bound. An extended abstract will appear in 52nd Annual IEEE Symposium on Foundations of Computer Science. Preprint available at http://arxiv.org/abs/1103.6161, 2011.

[9] J. E. Brock. Centroid and inertia tensor of a spherical triangle. National Technical Information Service, Naval Postgraduate School, Monterey, California, 1974.

[10] R. Connelly. Rigidity and energy. Invent. Math., 66(1):11–33, 1982.

[11] D. Gabai, G. R. Meyerhoff, and N. Thurston. Homotopy hyperbolic 3-manifolds are hyperbolic. Ann. of Math. (2), 157(2):335–431, 2003.

[12] D. Gabai, R. Meyerhoff, and P. Milley. Minimum volume cusped hyperbolic three-manifolds. J. Amer. Math. Soc., 22(4):1157–1215, 2009.

[13] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.

[14] U. Haagerup. The best constants in the Khintchine inequality. Studia Math., 70(3):231–283 (1982), 1981.

[15] T. C. Hales. A proof of the Kepler conjecture. Ann. of Math. (2), 162(3):1065–1185, 2005.

[16] R. R. Hall. On a conjecture of Littlewood. Math. Proc. Cambridge Philos. Soc., 78(3):443–445, 1975.

[17] E. Hansen. Global optimization using interval analysis, volume 165 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker Inc., New York, 1992.

[18] J. Hass and R. Schlafly. Double bubbles minimize. Ann. of Math. (2), 151(2):459–515, 2000.

[19] D. Hensley. Slicing the cube in R^{n} and probability (bounds for the measure of a central cube slice in R^{n} by probability methods). Proc. Amer. Math. Soc., 73(1):95–100, 1979.

[20] S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 767–775 (electronic), New York, 2002. ACM.

[21] S. Khot. On the unique games conjecture (invited survey). In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, pages 99–121, 2010.

[22] S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357 (electronic), 2007.

[23] S. Khot and A. Naor. Approximate kernel clustering. In 49th Annual IEEE Symposium on Foundations of Computer Science, pages 561–570, 2008.

[24] S. Khot and A. Naor. Sharp kernel clustering algorithms and their associated grothendieck inequalities. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 664–683, 2010.

[25] S. Khot and A. Naor. Grothendieck-type inequalities in combinatorial optimization. To appear in Comm. Pure Appl. Math., preprint available at http://arxiv.org/abs/1108.2464, 2011.

[26] A. Koldobsky. Fourier analysis in convex geometry, volume 116 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005.

[27] H. König. On an extremal problem originating in questions of unconditional convergence. In Recent progress in multivariate approximation (Witten-Bommerholz, 2000), volume 137 of Internat. Ser. Numer. Math., pages 185–192. Birkhäuser, Basel, 2001.

[28] H. König and A. Koldobsky. Volumes of low-dimensional slabs and sections in the cube. To appear in Advances of Appl. Math., 2011.

[29] J.-L. Krivine. Sur la constante de Grothendieck. C. R. Acad. Sci. Paris Sér. A-B, 284(8):A445–A446, 1977.

[30] R. Latała and K. Oleszkiewicz. On the best constant in the Khinchin-Kahane inequality. Studia Math., 109(1):101–104, 1994.

[31] N. Linial, L. Lovász, and A. Wigderson. Rubber bands, convex embeddings and graph connectivity. Combinatorica, 8(1):91–102, 1988.

[32] G. M. Minchin. A treatise on statics, containing some of the fundamental propositions in electrostatics. London, Longmans, Green & Co. 1877.

[33] E. Mossel, R. O’Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. In 46th Annual Symposium on Foundations of Computer Science, pages 21–30. IEEE Computer Society, 2005.

[34] F. L. Nazarov and A. N. Podkorytov. Ball, Haagerup, and distribution functions. In Complex analysis, operators, and related topics, volume 113 of Oper. Theory Adv. Appl., pages 247–267. Birkhäuser, Basel, 2000.

[35] K. Oleszkiewicz and A. Pełczyński. Polydisc slicing in C^{n}. Studia Math., 142(3):281–294, 2000.

[36] L. Song, A. Smola, A. Gretton, and K. A. Borgwardt. A dependence maximization view of clustering. In Proceedings of the 24th International Conference on Machine Learning, pages 815 – 822, 2007.

[37] S. J. Szarek. On the best constants in the Khinchin inequality. Studia Math., 58(2):197–208, 1976.

[38] B. Tomaszewski. A simple and elementary proof of the Kchintchine inequality with the best constant. Bull. Sci. Math. (2), 111(1):103–109, 1987.

[39] U. Zwick. Computer assisted proof of optimal approximability results. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 496–505, 2002.

Courant Institute, New York University, New York NY 10012

   E-mail address: heilman@cims.nyu.edu

Courant Institute, New York University, New York NY 10012

   E-mail address: asj260@nyu.edu

Courant Institute, New York University, New York NY 10012

   E-mail address: naor@cims.nyu.edu