The Gaussian propeller bound in every dimension

1 Introduction

Let \gamma_n denote the standard Gaussian probability measure on \mathbb R^n, with density (2\pi)^{-n/2}\exp(-\|x\|^2/2). For a measurable set A\subseteq\mathbb R^n, its Gaussian first moment is z(A)=\int_A x\,d\gamma_n(x). We call this unnormalized vector its centroid. Thus a centroid is not divided by the measure of its cell. For positive integers d,k and a measurable partition \mathcal A=(A_1,\ldots,A_k) of \mathbb R^d, define

Partitions are understood up to Gaussian null sets, and empty cells are allowed. The cell probabilities are unrestricted. All norms and inner products below are Euclidean.

The propeller conjecture asks whether three planar sectors meeting at angles 2\pi/3, extended by an orthogonal Euclidean factor, maximize this functional whenever d\ge2 and k\ge3. It arose in Khot and Naor’s study of approximate kernel clustering [5], where Gaussian first moments govern approximation and Unique Games hardness. Their formulation uses k cells in \mathbb R^{k-1}, with unused cells permitted. They proved that a maximizer can be chosen to be a conical partition in the span of its centroids and determined the three-cell value [5, Theorem 1.2 and Corollary 3.4].

Heilman, Jagannath, and Naor proved the bound for every finite partition of \mathbb R^3 [4, Theorem 1.1]. Their computer-assisted argument treats the remaining four-cell conical configurations through spherical geometry and a finite verification. We use that theorem as an established input. The new estimates below show that an extremizer with five or more active cells cannot have value greater than 9/(8\pi). Here an active cell has positive Gaussian measure. This proves the conjecture in all remaining dimensions.

1.1 The attaining propeller

The attaining partition illustrates an important feature of the problem: in every dimension at least two, only three cells are needed once at least three labels are available.

Consider a sector P in \mathbb R^2 of opening 2\alpha, symmetric about the first coordinate axis. Polar integration gives

For \alpha=\pi/3, three such sectors partition the plane and their squared centroid lengths sum to 3\sin^2(\pi/3)/(2\pi)=9/(8\pi). An orthogonal Gaussian factor contributes zero to every centroid, so the construction has the same value in every dimension at least two. The construction proves the attainment assertion in Theorem 1.1. Figure 1 shows the planar partition and its centroid directions.

1.2 Analytic background and related partition problems

The geometric reduction in Khot and Naor’s work is also the starting point here. We reprove its needed form, including attainment, the maximal-score description of the cells, and the effective dimension. The Gaussian-maximum duality used in this reduction is the normalized vector form of their Lemma 3.7. Our estimates then combine the loss on deleting one score with bounds for competition against two residual scores.

The one-score estimate uses the Gaussian Minkowski inequality introduced by Ehrhard for convex sets [2]. Latała extended the inequality when one of the sets is convex [7]; Borell proved the Borel-set version [1, Theorem 1.1]. Van Handel later gave a stochastic-game proof [10]. We need only the convex case: applied to translates of a cell, the inequality makes its inverse-normal Gaussian measure a concave function of the translation parameter. The translation direction, derivative, and resulting deletion estimate are derived in Section 3.

A related question asks which partition maximizes the probability that two correlated Gaussian vectors belong to the same cell, often with equal cell probabilities prescribed. This noise-stability objective is distinct from the unrestricted first-moment functional studied here. Heilman [3, Theorem 1.7] obtained a conditional route to the propeller bound for three or four cells in arbitrary dimension, assuming an additional stability property of equal-volume noise-stability maximizers. That result retains both the stability hypothesis and the restriction to at most four cells. The present argument addresses all finite cell counts and imposes no cell-mass constraint.

1.3 The kernel-clustering consequence

The Gaussian constant also determines the identity-target kernel-clustering threshold. For a rational symmetric positive semidefinite matrix A=(a_{pq})_{p,q=1}^N with A\one=0, this problem asks for an assignment \sigma:[N]\to[k] maximizing

Here [N]=\{1,\ldots,N\}, \one is the all-ones vector, and the indicator is one when its subscripts have the same label. Empty clusters are allowed. A loss factor \alpha means returning an assignment worth at least 1/\alpha times the maximum value. For fixed k\ge3, Khot and Naor’s expected Gaussian rounding guarantee [5, Theorem 2.1] has loss factor

Theorem 1.1 evaluates the Gaussian partition parameter in their hardness analysis. Together with their low-influence theorem and the companion paper The Unique Games Theorem [9, Theorem 1.1], it gives NP-hardness of every deterministic approximation with a fixed loss factor below \alpha_k. Section 6 proves this application on rational inputs and specifies the ideal rounding convention at the endpoint. The separate Unique Games input is needed only for the hardness statement.

1.4 Proof strategy

The difficulty is to control all measurable partitions while allowing both their shapes and their probabilities to vary. We first replace this infinite-dimensional optimization by a finite list of Gaussian linear scores. Two different consequences of optimality then constrain that list: deleting one score costs a definite amount of expected maximum, and competing against two scores constrains a covariance determinant.

Section 2 proves the reduction in full. Norm duality identifies the square root of the largest possible partition value with the largest possible expectation of the maximum score over lists of vectors with total squared norm one. Compactness gives an extremizer. Among extremizers, choose one with the fewest cells of positive measure. Merging two cells shows that its nonzero centroids z_1,\ldots,z_m have strictly negative pairwise inner products. Its cells agree almost everywhere with the cones where the corresponding score \langle z_i,x\rangle is largest. The centroids span a space of dimension m-1. The theorem of Heilman, Jagannath, and Naor therefore excludes m\le4 from any counterexample to the desired bound.

For the remaining case m\ge5, let C be the optimal value, let r_i=\|z_i\|/\sqrt C be the normalized centroid lengths, and let P_i be the cell probabilities. Then \sum_i r_i^2=\sum_iP_i=1. Section 3 bounds each P_i below in terms of r_i. Halfspace rearrangement gives one such estimate; when m=5, spherical rearrangement in the four-dimensional centroid span improves it. A further bound comes from removing one score and recentering the remaining vectors. The extremal score inequality gives a lower bound for the loss. Translations of the deleted score’s winning cone, together with Ehrhard’s inequality, give an upper bound. Comparing the two produces a scalar constraint on P_i and r_i.

Section 4 uses the cell with the smallest normalized centroid length. Projecting the other scores orthogonally to its centroid gives residual Gaussian scores independent of the score in that direction. Their integrals over the chosen cell vanish. For two residual scores, these identities allow us to estimate a positive-part integral by replacing the joint density with its maximum. The denominator of this two-dimensional Gaussian density bound is the square root of the residual covariance determinant. The resulting pairwise bound yields two inequalities involving the three largest normalized centroid lengths and the smallest one.

Finally, Section 5 combines the scalar probability bounds with the identity \sum_iP_i=1. The available probability mass forces the third-largest squared length to be too large relative to the smallest length, contradicting the determinant bound. This excludes an optimal value above 9/(8\pi). Appendix A gives exact rational enclosures for every finite numerical comparison, including the complete interval cover needed for the scalar constraint. The geometric proof uses the three-dimensional propeller bound and Ehrhard’s inequality as its external theorem inputs; the remaining geometric estimates are proved here. Section 6 gives a separate kernel-clustering application. Its reduction adapts Khot and Naor’s construction and uses two additional theorem inputs: their discrete Fourier estimate and the separate Unique Games theorem in [9].

2 Extremal partitions and their centroids

Our goal is to replace an arbitrary measurable partition by an optimal partition described by finitely many Gaussian linear scores. We include the extremal reduction of Khot and Naor [5, Theorem 1.2 and Lemma 3.3] in the form needed below.

It suffices to prove the upper bound for n+1 cells in \mathbb R^n with n\ge4. Indeed, given k cells in \mathbb R^d, put n=\max\{d,k-1,4\}, take their products with \mathbb R^{n-d}, and append n+1-k empty cells. Gaussian product decomposition appends zero coordinates to each first moment and preserves the objective.

Fix such an n and put N=n+1. All partitions below are measurable partitions up to Gaussian null sets, and empty cells are permitted. Write

The moments exist, and Cauchy–Schwarz on each cell gives C\le n. We first record the normalized vector form of the Gaussian-maximum description in [5, Lemma 3.7]. Its proof also gives attainment directly.

We argue by contradiction and henceforth assume

Choose an optimal partition with the fewest cells of positive measure, discard its null cells, and call the remaining cells active. Denote their moments by z_1,\ldots,z_m. Thus

The following structure statement develops the minimal-cell reduction of [5, Lemma 3.3]; the rank assertions are proved directly from the Gram matrix.

We have reduced a hypothetical counterexample to at least five active cells whose centroid span has dimension one less than their number. From now on we work in V\cong\mathbb R^{m-1}, use K_i for the reduced cones, and let g be standard Gaussian in this space. Their moments remain exactly z_i. Inequality (2.2) remains valid for lists in V, by embedding them in \mathbb R^n. Set

Then P_i>0, r_i>0, \sum_iP_i=\sum_i r_i^2=1, and \mathbb E\max_iX_i=C. Since \sum_iX_i=0, a winning score is nonnegative. Thus K_i\subseteq\{X_i\ge0\} and

3 Probability bounds for the cells

Throughout this section, we work with the putative extremizer above: C>B^2, m\ge5, and B=3/(2\sqrt{2\pi}). We will obtain lower bounds for each cell probability in terms of its normalized centroid length. Since the probabilities sum to one, these bounds constrain how the normalized centroid lengths can be distributed among the cells. Every terminating decimal in the proof denotes an exact rational number. Write

The winning cone K_i lies in \{x:\langle z_i,x\rangle\ge0\}, because the scores sum to zero. Thus 0<P_i\le1/2.

3.1 Rearrangement bounds

Fix a cell, and temporarily suppress its index. Let e=z/|z|, x=\Phi^{-1}(1-P), and H=\{g:\langle e,g\rangle\ge x\}. Since \gamma_{m-1}(H)=P,

Consequently |z|\le\phi(x). As \sqrt C>B=(3/2)\phi(0), this proves r<2/3 and

For completeness, the minimum on the right can be localized by a one-dimensional argument. Put M(x)=\phi(x)/\Phi(-x). The logarithmic derivative of f(x)=(9/4)e^{x^2}\Phi(-x) is 2x-M(x), and

for a standard normal variable Z. Hence (\log f)' is strictly increasing. Its signs at 0.6119 and 0.6121 are opposite, so f has a unique global minimum in that interval. The elementary bounds in Appendix A give

This proves the required quadratic estimate when m\ge6.

When m=5, conicality improves the estimate. Work in the four-dimensional span of the centroids and write the standard Gaussian as RU, where U is uniform on S^3 and independent of R. The coordinate \langle e,U\rangle has density (2/\pi)\sqrt{1-u^2} on [-1,1]. The same threshold comparison as above shows that, among spherical sets of measure P, an upper cap maximizes the first moment in direction e. Since P\le1/2, write its threshold as x\in[0,1). Its probability is

Using \mathbb ER=3\sqrt{2\pi}/4, its Gaussian first moment is

It follows that

To identify the global minimum, define

Direct differentiation gives

Thus H first decreases and then increases. Since H(0)=1/2 and H(1)=0, it has exactly one zero in (0,1); it is negative after that zero. Accordingly F first increases and then decreases to F(1)=0. The certified signs F(0.29)<0<F(0.294) show that F has exactly one interior zero and that this zero lies in (0.29,0.294). It is the unique minimizer of R. Appendix A gives R(0.29)>0.9312526 and |R'|<0.03 on this interval, whence

The first two assertions of Lemma 3.1 follow.

3.2 The loss on removing one score

Rearrangement has supplied the radius bound and the quadratic probability bound. To obtain the remaining linear–quadratic estimate in Lemma 3.1, we use the behavior of the winning probability under translation. Fix i, put X_j=\langle z_j,g\rangle, and set \alpha=m/(m-1). Removing z_i and recentering the remaining vectors produces z_j+z_i/(m-1), j\ne i, whose squared norms sum to C-\alpha|z_i|^2. A common translation of the scores has zero expectation. The extremal dual bound therefore gives

Since \mathbb E\max_jX_j=C, the loss satisfies

Here u_+=\max(u,0).

The vectors z_i-z_j, j\ne i, form a basis of the centroid span. There is therefore a vector h in that span satisfying \langle h,z_i-z_j\rangle=1 for every j\ne i. For u\ge0, the gap probability is

Summing the equations defining h gives \langle h,z_i\rangle=(m-1)/m=1/\alpha. Differentiation of the translated Gaussian density, justified by Gaussian integrability, yields

Ehrhard’s inequality states that \Phi^{-1}\circ\gamma_{m-1} is concave under Minkowski interpolation of convex sets [2]; we use the formulation in [1, Theorem 1.1], which also allows general Borel sets. The cone K_i is closed and convex. Its score-difference normals form a basis, so it has nonempty interior and is a proper subset of the centroid span. Minkowski interpolation of two translates of K_i is the translate with the interpolated displacement. Hence u\mapsto\Phi^{-1}(p_i(u)) is concave. All finite translates have measure strictly between zero and one, and the derivative at zero exists by (3.7). With q=\Phi^{-1}(P_i), the supporting tangent gives

Integration, using (q\Phi(q)+\phi(q))'=\Phi(q), gives

Define

Combining (3.6) and (3.8), rationalizing, and canceling \alpha, we obtain

3.3 A linear–quadratic probability bound

The loss constraint is implicit in the cell probability. To extract an explicit lower bound, we first prove two monotonicity properties of G.

We finish the proof of Lemma 3.1. Set P_0(r)=(0.415+0.15r)r for 0<r\le2/3. Then P_0(r)\le P_0(2/3)=103/300<1/2. We will prove

By Lemma 3.2 and (3.9), this implies P_i>P_0(r_i), which is stronger than the last assertion of Lemma 3.1.

Here is a finite interval verification of (3.10). In each row of Table 1, U bounds G(\Phi^{-1}(P_0(r))) above throughout [a,b]\cap(0,2/3]. The first row uses G<1; the other rows follow from monotonicity and the certified quantile bounds in Appendix A. The last column is a strict lower bound for

It is positive in every row. The coefficient (0.415+0.15r)^2 and the right side of (3.10) are increasing in r, so these endpoint inequalities cover every point of the intervals, not only their endpoints.

4 Competition with two other cells

Continue with the minimal-active-cell optimal partition from Lemma 2.2, satisfying C>B^2 and m\ge5. The scalar estimates constrain one cell at a time. We now use the first-moment identity for the cell with smallest centroid norm to obtain constraints on pairs of the other centroids. Relabel the nonzero centroids so that

Thus the three largest radii and the chosen smallest radius have distinct indices, including when some radii are equal. We will use the centroid identity for this cell to control the joint distribution of any two competing scores.

Let g be a standard Gaussian vector in the ambient Euclidean space, and put

Strict negativity of the off-diagonal products and \sum_jz_j=0 imply

Define the residual vectors and scores by

Each w_j is orthogonal to e. Consequently Y=(Y_j)_{j<m} is a centered Gaussian vector independent of the standard normal variable T, and

Its covariance matrix H has entries

Since \sum_{j<m}w_j=0, every row of H sums to zero; also H_{jk}<0 for j\ne k. For distinct j,k<m, set

These quantities are positive. Indeed, a linear dependence between w_j and w_k would give a dependence between z_j,z_k,z_m, whereas every proper subset of the centroids is linearly independent and m\ge5. In particular, all h_j are positive.

The pairwise inequality becomes useful for the partition problem when we sum it over competitors with the largest centroid lengths. The negative off-diagonal covariances prevent all of these pairwise determinants from being small simultaneously.

5 Excluding five or more active cells

We show that the scalar bounds of Lemma 3.1 and the geometric constraints of Corollary 4.2 are incompatible. We first confine the smallest radius to .066<t<.12, and then prove c>2.6t, contradicting the second determinant constraint. Throughout this section, the radii are ordered as

Set

The probability excesses \delta_j=P_j-Ar_j^2 satisfy, by (3.1),

All terminating decimals below denote exact rational numbers. The finite comparisons are recorded with strict lower bounds; the rational arithmetic and square-root enclosures that verify them are described in Appendix A.

5.1 The third radius and the small-minimum case

First we obtain a bound that holds for every value of t. For j\ge3, the inequality r_j\le\sqrt c gives

Summing these charges in (5.2) yields

If A=.929, add .045(1-L) to both sides and bound the added right-hand term by .045; if A=.884, no adjustment is needed. Thus in both cases

Since r_j\le2/3, we have L\le8/9. If \sqrt c\le.23, the left side of (5.3) exceeds its right side by at least

Consequently

Suppose now that t\le q_0:=.066. We contradict (4.7), which reads

If \sqrt c\ge.44, then L\ge2c, so the left side is at least

Both factors here are positive, and

This contradicts (5.5).

For the remaining range .23<\sqrt c<.44, use the four intervals in Table 2. On an interval [a,b], the denominator .415/\sqrt c-.734 is positive, and (5.3) gives

Also c-t^2\ge a^2-q_0^2>0. Every M(b) is positive, and the last column of the table contradicts (5.5). Thus

5.2 Bounding the remaining radii

We next prove that

Suppose instead that r_4>.42, and put

For every u\ge.42 we have

Indeed, when u\le s, use

When u>s, the right side of (5.9) is negative, so nonnegativity proves the inequality. Applying this to the first four radii and using the minimum radius on the others gives

For j\ge5, ordering and normalization give r_j\le1/\sqrt5. By (5.7), these radii lie in [.066,1/\sqrt5]. Concavity of e therefore gives

The last equality follows from Table 3, where e(.066)=.023996676 for A=.929 and e(.066)=.024192696 for A=.884. Combining the charges and replacing t by .066 proves

The right side increases with m, with increment K(.066)^2+e(.066)>0. At the smallest permitted m, its excess over 1-A is already positive by Table 3. This contradiction proves (5.8).

Put k=2 when m=5 and k=3 when m\ge6. There are at least k indices after the first three, and their radii belong to [t,.42]. Their charges are each at least \min\{e(t),e(.42)\}. Moreover,

Hence (5.2) forces ke(t)\le1-A. Let t_0 be the smaller root of ke(u)=1-A:

Equation (5.11) places .42 strictly between the two roots of this concave quadratic. Since t\le.42, the larger-root alternative is excluded, and t\le t_0. The enclosures

imply t_0<.109 in the first case and t_0<.12 in both cases. Furthermore, e(.42)>(1-A)/k\ge e(t), so each of the k selected indices contributes at least e(t).

5.3 The final contradiction

We claim that

Otherwise, (5.4) places the third radius in [.23,\sqrt{2.6t}]. It is distinct from the k indices just charged, so concavity of e and (5.2) imply

We check both possible endpoint charges on the entire interval [.066,t_0].

First, e is increasing up to t_0, the smaller root in (5.12). Thus

by Table 4. Second, the function

is strictly concave for t>0, since

Its minimum on [.066,t_0] is therefore attained at an endpoint. Table 4 gives F(.066)>1-A and 2.6t_0<s^2. The latter implies e(\sqrt{2.6t_0})>0; since ke(t_0)=1-A, it also gives F(t_0)>1-A. These inequalities contradict (5.15) and prove (5.14).

Finally, (4.8), (5.14), and 0<t<.12 give

But

This contradiction rules out C>B^2 and completes the upper bound.

5.4 Gaussian maxima

The partition bound also gives a sharp inequality for Gaussian maxima. The four-score version appears in Heilman, Jagannath, and Naor [4, Theorem 1.2]; Gaussian partition duality is due to Khot and Naor [5, Lemma 3.7]. Subtracting the common average score gives the following centered form in every dimension.

Every finite centered jointly Gaussian vector (X_1,\ldots,X_k) can be written as (\langle v_i,g\rangle)_{i=1}^k, including when its covariance is singular. Thus the corollary also bounds its expected maximum by 3/(2\sqrt{2\pi}) times \bigl(\sum_i\operatorname{Var}(X_i-\bar X)\bigr)^{1/2}, where \bar X=k^{-1}\sum_iX_i.

6 A kernel-clustering application

6.1 The objective and the approximation threshold

This application uses Theorem 1.1, the kernel-clustering results of Khot and Naor, and the companion paper The Unique Games Theorem. None of these complexity arguments is used in the proof of the Gaussian inequality.

Fix an integer k\ge3. An input is an explicitly represented rational symmetric matrix A=(a_{pq})_{p,q=1}^N satisfying A\succeq0 and A\one=0. The latter is the centering condition; for a positive semidefinite matrix it is equivalent to \sum_{p,q}a_{pq}=0. For a map \sigma:[N]\to[k], define

Here [m]=\{1,\ldots,m\}, and I_k is the k-by-k identity target matrix. The sum is over ordered pairs and includes the diagonal. Equivalently, it is \sum_{i=1}^k\sum_{p,q\in S_i}a_{pq} for the cells S_i=\sigma^{-1}(i); empty cells are allowed. There is no normalization by cell cardinalities. Each objective value is nonnegative, since it is a sum of quadratic forms \one_{S_i}^{\mathsf T}A\one_{S_i}.

A deterministic approximation with loss factor \alpha\ge1 returns an assignment of value at least \Clust(A\mid I_k)/\alpha. An expected approximation has the same inequality with the returned value replaced by its expectation. Put

The matching rounding constant. Khot and Naor’s approximation theorem [5, Theorem 2.1] gives the expected rounding bound

on the inputs in (6.1). This is their endpoint analytic guarantee using an optimal semidefinite relaxation and ideal Gaussian sampling. We quote this rounding guarantee separately from the rational-input hardness statement below; an exact finite-bit implementation at the endpoint is not asserted here.

We prove the hardness statement below. It concerns strict improvement over \alpha_k, not hardness at the endpoint.

For the more general objective \sum_{p,q}a_{pq}b_{\sigma(p)\sigma(q)} with a fixed positive semidefinite target matrix B=(b_{ij})_{i,j=1}^k, Khot and Naor later characterized the Unique Games hardness threshold for approximating the optimal clustering value through geometric and Gaussian partition parameters [6, Theorem 1.1]. Here the target is I_k, and the Gaussian constant is supplied by Theorem 1.1.

6.2 The two external hardness inputs

The Gaussian parameter in Khot and Naor’s theorem is

The supremum ranges over measurable partitions of \R^{k-1}, with empty cells allowed. Since k\ge3, Theorem 1.1 and the attaining example in Section 1.1 give

We first specify the discrete analytic input. Let \Omega=[k] have uniform probability measure. Choose a real orthonormal basis b_0,b_1,\ldots,b_{k-1} of functions on \Omega, with b_0=1. For r\in\N and \nu\in\{0,\ldots,k-1\}^r, write

Every h:\Omega^r\to\R has expansion h=\sum_\nu\widehat h(\nu)b_\nu, with coefficients computed using uniform probability measure. For real D\ge0, set

Thus a nonintegral cutoff is interpreted by the displayed inequality on the integer |\nu|. Let P_1 be orthogonal projection onto the span of b_\nu with |\nu|=1, and, for f=(f_1,\ldots,f_k), put

All L_2 norms in this section use uniform probability measure. Define the closed simplex with slack by

This is [5, Theorem 3.8], with the same uniform product measure, Fourier degree, simplex, and Gaussian normalization. Its proof uses the invariance principle of Mossel, O’Donnell, and Oleszkiewicz [8] to compare low-influence functions on product spaces with their Gaussian counterparts. The restriction \tau_0<1/2 is harmless: decreasing the threshold and increasing the degree cutoff strengthen the hypotheses. Choose a rational 0<\tau<\min\{\tau_0,1/2\} and set

Monotonicity of (6.3) in the cutoff gives the useful contrapositive

Indeed, if every influence at cutoff D were at most \tau, every influence at the original cutoff would be at most \tau_0.

The second input is the following exact interface of [9, Theorem 1.1].

Only ordinary satisfied-edge fractions are asserted here. We will use neither regularity nor the stronger condition that almost every left vertex has all its incident constraints satisfied.

6.3 A rational centered positive semidefinite matrix

Let G=(V,W,E) be a game supplied by Theorem 6.3, and enumerate its alphabet as [r], where r=2^s. Reorient constraints if necessary so that the permutation \pi_{vw}:[r]\to[r] attached to vw\in E is satisfied precisely when

Translations are permutations, so this changes no game value. Delete isolated vertices, put M=|E|, and write

Choosing v with probability \mu(v), then a uniform w\in N(v), chooses an edge uniformly.

To fix the permutation convention, for a permutation \pi define

For a scalar table h:W\times\Omega^r\to\R, define

The output matrix will represent Q in the ordinary, unnormalized Euclidean coordinates of the table h.

6.4 Completeness and weighted decoding

The next two lemmas compare ordinary edge-value completeness and soundness with the kernel objective. They adapt the Khot–Naor reduction [5, Section 3.3] to the precise input of Theorem 6.3.

6.5 Completing the reduction

A Elementary certificates for the numerical inequalities

This appendix gives rational enclosures for the numerical comparisons used in the proof. All finite decimals denote exact rationals. The formulas below and the tables suffice to reproduce the comparisons; no numerical optimization or numerical quadrature is needed.

A.1 Enclosure formulas

We use

For example, these bounds follow from \pi=16\arctan(1/5)-4\arctan(1/239) by bounding each arctangent between its alternating-series partial sums through indices 7 and 6. All square-root enclosures may be obtained using rational numbers l,u\ge0 with l^2\le x\le u^2. An explicit rule, if desired, is to set D=10^{35} and use

For an interval of possible x, apply the lower rule to its lower endpoint and the upper rule to its upper endpoint. Thus only rational operations and integer square roots are required.

For y\ge0, let

Taylor’s integral remainder gives

This conclusion does not require the initial terms of the series to be decreasing. Integrating the same bounds, set

Then

Together with (A.1) and the square-root rule, these are rational enclosures for both \phi and \Phi at every argument used below. Interval addition, subtraction, multiplication, and division by intervals avoiding zero preserve the enclosures.

For the cap calculation, put

The binomial series has positive coefficients at most one. Its tail starting in degree 10 is bounded by x^{10}/(1-x^2); after integration this gives, for 0\le x<1,

A.2 The two rearrangement minima

Write f(x)=(9/4)e^{x^2}\Phi(-x) and D_f(x)=2x-\phi(x)/\Phi(-x), as in (3.2). Substitution into (A.2)–(A.3) gives the following strict enclosures:

For the third row, use the whole rational interval [0.6119,0.6121] in the elementary interval operations; \phi(x) decreases and \Phi(-x) decreases there, so endpoint enclosures give both factors. Thus |D_f|<0.001 throughout that interval. The minimizer lies within 0.0001 of 0.612, and so

For p,F,H,R from (3.4) and its following calculation, (A.4) gives

For 0.29\le x\le0.294, the last row implies

Therefore F is increasing throughout the interval, and the first two rows imply |F(x)|<0.004702 there. Consequently

This proves the derivative bound on the entire interval. The minimum therefore exceeds 0.9312526-0.03(0.004)=0.9311326.

A.3 Quantiles and the interval probability bounds

For P_0(a)=(0.415+0.15a)a, Table 5 gives a rational q_a satisfying \Phi(q_a)<P_0(a), and a strict upper bound on G(q_a). Each entry follows by substituting the displayed rational argument into (A.2)–(A.3) and the definition of G. Since G is nonincreasing,

In each row the listed upper bound is strictly below the value of U in Table 1.

Finally, for each row (a,b,U) of Table 1, replace \pi by its upper bound in B^2=9/(8\pi), enclose \sqrt{1-a^2} from above, and subtract the exact rational U(0.415+0.15b)^2. This gives the lower bounds in that table’s last column. The same rational and square-root rules apply to the finite comparisons in the numerical elimination section.