A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 1 · The Gaussian propeller conjecture
The Gaussian propeller bound in every dimension
expertly designed by an internal OpenAI model · released 2026-09-24
· original PDF
IntroductionLet \(\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 \[\mathcal F(\mathcal A)=\sum_{i=1}^k\|z(A_i)\|^2.\] 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]. Heilman, Jagannath, and Naor proved the bound for every finite partition of \(\mathbb R^3\) [4]. 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. Theorem 1. For all positive integers \(d\) and \(k\), every measurable partition \((A_1,\ldots,A_k)\) of \(\mathbb R^d\) satisfies \[\sum_{i=1}^k\left\|\int_{A_i}x\,d\gamma_d(x)\right\|^2 \le\frac9{8\pi}.\] Empty cells are allowed. The constant is sharp whenever \(d\ge2\) and \(k\ge3\): three planar sectors of angle \(2\pi/3\), multiplied by the orthogonal complement of their plane, attain equality, with any further cells empty. The attaining propellerThe 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 \[\int_P x\,d\gamma_2(x) =\frac1{2\pi}\left(\int_0^\infty r^2e^{-r^2/2}\,dr\right) \left(\int_{-\alpha}^{\alpha}(\cos\theta,\sin\theta)\,d\theta\right) =\frac{\sin\alpha}{\sqrt{2\pi}}(1,0).\] 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. Figure 1 shows the planar partition and its centroid directions. The kernel-clustering consequenceThe 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\mathbf 1=0\), this problem asks for an assignment \(\sigma:[N]\to[k]\) maximizing \[\sum_{p,q=1}^N a_{pq}\mathbf 1_{\{\sigma(p)=\sigma(q)\}}.\] Here \([N]=\{1,\ldots,N\}\), \(\mathbf 1\) 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] has loss factor \[\alpha_k=\frac{8\pi}{9}\left(1-\frac1k\right).\] Theorem 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], 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. Proof strategyThe 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 7 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]. Extremal partitions and their centroidsOur 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] 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 \[C=\sup_{(A_1,\ldots,A_N)} \sum_{i=1}^N\left\|\int_{A_i}x\,d\gamma_n(x)\right\|^2, \qquad B=\frac{3}{2\sqrt{2\pi}}.\] 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]. Its proof also gives attainment directly. Lemma 2. If \(g\) is a standard Gaussian vector in \(\mathbb R^n\), then \[ \sqrt C= \max_{\sum_{i=1}^N\|v_i\|^2=1} \mathbb E\max_{1\le i\le N}\langle v_i,g\rangle. \tag{1}\] The supremum defining \(C\) is attained. Moreover, for every \(1\le k\le N\) and every list \(v_1,\ldots,v_k\in\mathbb R^n\), \[ \mathbb E\max_{1\le i\le k}\langle v_i,g\rangle \le \sqrt C\left(\sum_{i=1}^k\|v_i\|^2\right)^{1/2}. \tag{2}\] Proof. For a partition with moments \(z_i=\int_{A_i}x\,d\gamma_n(x)\), Euclidean norm duality gives \[\left(\sum_i\|z_i\|^2\right)^{1/2} =\max_{\sum_i\|v_i\|^2=1} \sum_i\int_{A_i}\langle v_i,x\rangle\,d\gamma_n(x).\] Taking the supremum jointly over partitions and lists, and then first over partitions, yields the right side of (1). Indeed, for each fixed list the pointwise maximum is attained by assigning \(x\) to a largest score \(\langle v_i,x\rangle\), with ties resolved by the smallest index. This gives a measurable partition. The expected maximum is continuous in the list: the absolute difference of two maxima is at most \(\|g\|\max_i\|v_i-w_i\|\). Compactness of the sphere of lists therefore gives a maximizing list. Its score partition has moment norm at least its pairing with that list, namely \(\sqrt C\), so it attains \(C\). For (2), let \(Q_1,\ldots,Q_k\) be a score partition for the specified list, and put \(b_i=\int_{Q_i}x\,d\gamma_n(x)\). Appending \(N-k\) empty cells shows that \(\sum_i\|b_i\|^2\le C\). Consequently \[\mathbb E\max_i\langle v_i,g\rangle =\sum_i\langle v_i,b_i\rangle \le\left(\sum_i\|v_i\|^2\right)^{1/2} \left(\sum_i\|b_i\|^2\right)^{1/2},\] which proves the assertion. ◻ We argue by contradiction and henceforth assume \[ C>B^2=\frac{9}{8\pi}. \tag{3}\] 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 \[ \sum_{i=1}^m z_i=0, \qquad \sum_{i=1}^m\|z_i\|^2=C. \tag{4}\] The following structure statement develops the minimal-cell reduction of [5]; the rank assertions are proved directly from the Gram matrix. Lemma 3. The centroids satisfy \(\langle z_i,z_j\rangle<0\) for \(i\ne j\). Their span \(V\) has dimension \(m-1\), every proper subset of the centroids is linearly independent, and, for each fixed \(i\), the \(m-1\) vectors \(z_i-z_j\), \(j\ne i\), form a basis of \(V\). The optimal cells have the closed conical representatives \[ K_i=\{x\in\mathbb R^n: \langle z_i-z_j,x\rangle\ge0\text{ for every }j\ne i\}. \tag{5}\] Furthermore, \(m\ge5\). Proof. Since \(C>0\), we have \(m\ge2\). Merging two cells changes the objective by \(2\langle z_i,z_j\rangle\). A positive product would contradict optimality; a zero product would contradict minimality of \(m\). Thus every such product is negative, and in particular every \(z_i\) is nonzero. For the original optimal partition, pairing each cell with its own centroid gives \[C\le\mathbb E\max_i\langle z_i,g\rangle\le C,\] where the second inequality is (2). The difference between the maximum score and the assigned score is nonnegative and has zero integral, so it vanishes almost everywhere. The centroids are distinct, and their score ties lie on finitely many Gaussian-null hyperplanes. This proves (5); overlaps between these closed representatives are immaterial. Let \(Q=(\langle z_i,z_j\rangle)_{i,j=1}^m\) be the Gram matrix. Its row sums vanish by (4). Hence, for every \(a=(a_1,\ldots,a_m)\in\mathbb R^m\), \[ a^{\mathsf T}Qa =\sum_{i<j}(-\langle z_i,z_j\rangle)(a_i-a_j)^2. \tag{6}\] All weights are positive, so the kernel of \(Q\) consists exactly of constant vectors. Its rank is \(m-1\), and the only linear relations among the centroids are multiples of their sum. A dependence on a proper subset would have a zero coefficient and therefore must be trivial. A relation among \(z_i-z_j\), \(j\ne i\), gives a relation among all centroids whose coefficients sum to zero; it too must be trivial. This proves the linear-algebra assertions. Each \(K_i\) depends only on the orthogonal projection onto \(V\). If \(d=\dim V\), then orthogonal Gaussian product decomposition identifies \(K_i\) with \((K_i\cap V)\times V^\perp\), and its moment is the moment of \(K_i\cap V\) in \(V\), extended by zero on \(V^\perp\). If \(m\le4\), then \(d\le3\). Taking the product of this partition of \(V\cong\mathbb R^d\) with \(\mathbb R^{3-d}\) preserves its moment norms. The three-dimensional propeller theorem of Heilman, Jagannath, and Naor [4], which permits any finite number of cells, would then give \(C\le9/(8\pi)\), contradicting (3). Thus \(m\ge5\). ◻ 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) remains valid for lists in \(V\), by embedding them in \(\mathbb R^n\). Set \[ X_i=\langle z_i,g\rangle, \qquad P_i=\gamma_{m-1}(K_i), \qquad r_i=\frac{\|z_i\|}{\sqrt C}. \tag{7}\] 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 \[ P_i\le\frac12\qquad(1\le i\le m). \tag{8}\] Probability bounds for the cellsThroughout 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 \[\phi(x)=\frac{e^{-x^2/2}}{\sqrt{2\pi}},\qquad \Phi(x)=\int_{-\infty}^x\phi(u)\,du,\qquad r_i=\frac{|z_i|}{\sqrt C},\qquad P_i=\gamma_{m-1}(K_i).\] 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\). Lemma 4. Set \[A=\begin{cases}0.929,&m=5,\\0.884,&m\ge6.\end{cases}\] For every \(i\), \[ r_i\le\frac23,\qquad P_i\ge Ar_i^2,\qquad P_i\ge0.415r_i+0.15r_i^2. \tag{9}\] Rearrangement boundsFix 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\), \[|z|-\int_H\langle e,g\rangle\,d\gamma_{m-1}(g) =\int(\langle e,g\rangle-x)(1_K-1_H)\,d\gamma_{m-1}(g)\le0.\] Consequently \(|z|\le\phi(x)\). As \(\sqrt C>B=(3/2)\phi(0)\), this proves \(r<2/3\) and \[ \frac P{r^2}\ge \frac94 e^{x^2}\Phi(-x). \tag{10}\] 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 \[M'(x)=1-\operatorname{Var}(Z\mid Z>x)<1\] 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 7 give \[ \min_{x\in\mathbb R}f(x)>0.8843837>0.884. \tag{11}\] 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 \[p(x)=\frac12-\frac{\arcsin x+x\sqrt{1-x^2}}\pi.\] Using \(\mathbb ER=3\sqrt{2\pi}/4\), its Gaussian first moment is \[\mathbb ER\,\frac2\pi\int_x^1 u\sqrt{1-u^2}\,du =\phi(0)(1-x^2)^{3/2}.\] It follows that \[ \frac P{r^2}\ge R(x):=\frac94\frac{p(x)}{(1-x^2)^3}. \tag{12}\] To identify the global minimum, define \[F(x)=6xp(x)-\frac2\pi(1-x^2)^{3/2},\qquad H(x)=p(x)-\frac x\pi\sqrt{1-x^2}.\] Direct differentiation gives \[R'(x)=\frac94\frac{F(x)}{(1-x^2)^4},\qquad F'(x)=6H(x),\qquad H'(x)=\frac{4x^2-3}{\pi\sqrt{1-x^2}}.\] 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 7 gives \(R(0.29)>0.9312526\) and \(|R'|<0.03\) on this interval, whence \[ \min_{0\le x<1}R(x)>0.9311326>0.929. \tag{13}\] The first two assertions of Lemma 4 follow. The loss on removing one scoreRearrangement has supplied the radius bound and the quadratic probability bound. To obtain the remaining linear–quadratic estimate in Lemma 4, 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 \[\mathbb E\max_{j\ne i}X_j\le \sqrt C\sqrt{C-\alpha|z_i|^2}.\] Since \(\mathbb E\max_jX_j=C\), the loss satisfies \[ \mathbb E\bigl(X_i-\max_{j\ne i}X_j\bigr)_+ \ge C\bigl(1-\sqrt{1-\alpha r_i^2}\bigr). \tag{14}\] 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 \[p_i(u):=\Pr\{X_i\ge X_j+u\text{ for all }j\ne i\} =\gamma_{m-1}(K_i+uh).\] 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 \[ p_i'(0)=-\int_{K_i}\langle h,x\rangle\,d\gamma_{m-1}(x) =-\langle h,z_i\rangle=-\frac1\alpha. \tag{15}\] 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], 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 (15). With \(q=\Phi^{-1}(P_i)\), the supporting tangent gives \[p_i(u)\le\Phi\!\left(q-\frac{u}{\alpha\phi(q)}\right) \qquad(u\ge0).\] Integration, using \((q\Phi(q)+\phi(q))'=\Phi(q)\), gives \[ \mathbb E\bigl(X_i-\max_{j\ne i}X_j\bigr)_+ =\int_0^\infty p_i(u)\,du \le\alpha\phi(q)\bigl(q\Phi(q)+\phi(q)\bigr). \tag{16}\] Define \[G(q)=\frac{\phi(q)\bigl(q\Phi(q)+\phi(q)\bigr)}{\Phi(q)^2}.\] Combining (14) and (16), rationalizing, and canceling \(\alpha\), we obtain \[ P_i^2G\bigl(\Phi^{-1}(P_i)\bigr) \ge\frac{Cr_i^2}{1+\sqrt{1-\alpha r_i^2}} \ge\frac{B^2r_i^2}{1+\sqrt{1-r_i^2}}. \tag{17}\] A linear–quadratic probability boundThe loss constraint is implicit in the cell probability. To extract an explicit lower bound, we first prove two monotonicity properties of \(G\). Lemma 5. The function \(G\) is nonincreasing and satisfies \(0<G(q)<1\). Moreover, \[P\longmapsto P^2G\bigl(\Phi^{-1}(P)\bigr)\] is increasing on \((0,1/2]\). Proof. Put \(\lambda=\phi(q)/\Phi(q)\). Integration of the normal density gives \[\mathbb E(Z\mid Z\le q)=-\lambda,\qquad V(q):=\operatorname{Var}(Z\mid Z\le q)=1-q\lambda-\lambda^2.\] Thus \(G=1-V=\lambda(q+\lambda)\). The distance \(U=q-Z\), under this conditioning, has positive mean \(q+\lambda\) and positive variance, proving \(0<G<1\). Its survival function is \(S(u)=\Phi(q-u)/\Phi(q)\), \(u\ge0\). The identity \((\log\Phi)''(q)=-\lambda(q+\lambda)<0\) shows that \(\log S\) is concave. Its increments therefore satisfy \[\log S(u+v)-\log S(u)\le\log S(v)-\log S(0).\] Since \(S(0)=1\), this gives \(S(u+v)\le S(u)S(v)\). Integrating over \(u,v\ge0\) gives \[\frac12\mathbb EU^2 =\int_0^\infty\!\int_0^\infty S(u+v)\,du\,dv \le(\mathbb EU)^2.\] Hence \(V\le(q+\lambda)^2\). Direct differentiation now gives \[V'(q)=\lambda\bigl((q+\lambda)^2-V(q)\bigr)\ge0,\] so \(G\) is nonincreasing. Finally, for \(q\le0\), both positive factors of \(\phi(q)(q\Phi(q)+\phi(q))\) are increasing in \(q\), proving the last assertion. ◻ We finish the proof of Lemma 4. 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 \[ (0.415+0.15r)^2G\bigl(\Phi^{-1}(P_0(r))\bigr) <\frac{B^2}{1+\sqrt{1-r^2}}. \tag{18}\] By Lemma 5 and (17), this implies \(P_i>P_0(r_i)\), which is stronger than the last assertion of Lemma 4. Here is a finite interval verification of (18). 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 7. The last column is a strict lower bound for \[\Delta(a,b,U):= \frac{B^2}{1+\sqrt{1-a^2}}-U(0.415+0.15b)^2.\] It is positive in every row. The coefficient \((0.415+0.15r)^2\) and the right side of (18) are increasing in \(r\), so these endpoint inequalities cover every point of the intervals, not only their endpoints.
Competition with two other cellsContinue with the minimal-active-cell optimal partition from Lemma 3, 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 \[r_1\ge r_2\ge\cdots\ge r_m=t>0, \qquad L=r_1^2+r_2^2, \qquad c=r_3^2.\] 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 \[e=\frac{z_m}{|z_m|},\qquad T=\langle e,g\rangle, \qquad a_j=-\frac{\langle z_m,z_j\rangle}{|z_m|^2} \quad(1\le j<m).\] Strict negativity of the off-diagonal products and \(\sum_jz_j=0\) imply \[ a_j>0,\qquad \sum_{j<m}a_j=1. \tag{19}\] Define the residual vectors and scores by \[w_j=\frac{z_j}{\sqrt C}+a_jte, \qquad Y_j=\langle w_j,g\rangle.\] 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 \[ \frac{\langle z_j,g\rangle}{\sqrt C}=-a_jtT+Y_j. \tag{20}\] Its covariance matrix \(H\) has entries \[ H_{jk}=\frac{\langle z_j,z_k\rangle}{C}-a_ja_kt^2, \qquad h_j:=H_{jj}=r_j^2-a_j^2t^2. \tag{21}\] 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 \[D_{jk}=\sqrt{h_jh_k-H_{jk}^2}.\] 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. Lemma 6 (Two competing scores). For every pair of distinct indices \(j,k<m\), \[ D_{jk}\le \frac3\pi\,t(1+a_j)(1+a_k). \tag{22}\] Proof. Let \(K\) be the winning cone for the score \(\langle z_m,g\rangle\). The partition agrees with its score cones almost everywhere, so \(\mathbb E[\mathbf 1_Kg]=z_m\). The definitions of \(T\) and \(Y_j\) give \[ \mathbb E[\mathbf 1_KT]=|z_m|=\sqrt C\,t>Bt, \qquad \mathbb E[\mathbf 1_KY_j]=\langle w_j,z_m\rangle=0. \tag{23}\] The scores sum to zero. Their maximum is therefore nonnegative, and on \(K\) we have, by (20), \[T\ge0,\qquad Y_j\le(1+a_j)tT\quad(j<m).\] Fix distinct \(j,k<m\) and write \[U=\frac{Y_j}{(1+a_j)t},\qquad V=\frac{Y_k}{(1+a_k)t}.\] The pair \((U,V)\) is independent of \(T\), and its Gaussian density is bounded above everywhere by \[ M=\frac{t^2(1+a_j)(1+a_k)}{2\pi D_{jk}}. \tag{24}\] Here the denominator follows by taking the square root of the covariance determinant after the two rescalings. For a real number \(x\), write \(x_+=\max\{x,0\}\). Adding the two zero expectations from (23), taking a positive part, and then enlarging the integration region yields \[\begin{align*} \mathbb E[\mathbf 1_KT] &=\mathbb E[\mathbf 1_K(T+U+V)]\\ &\le\mathbb E\big[ \mathbf 1_{\{T\ge0,\ U\le T,\ V\le T\}}(T+U+V)_+\big]. \end{align*}\] For a fixed \(s\ge0\), within \(u\le s\), \(v\le s\) the positive integrand is supported on the triangle with vertices \((s,s)\), \((s,-2s)\), and \((-2s,s)\). The corresponding unweighted planar integral is \[\begin{align*} \int_{u\le s}\int_{v\le s}(s+u+v)_+\,dv\,du &=\int_0^\infty\int_0^\infty(3s-a-b)_+\,db\,da\\ &=\int_0^{3s}\int_0^{3s-a}(3s-a-b)\,db\,da =\frac{(3s)^3}{6}, \end{align*}\] where \(a=s-u\) and \(b=s-v\). Figure 2 shows this integration region and its affine integrand. \[\int_{\Delta_s}h_s(u,v)\,du\,dv =\underbrace{\frac{(3s)^2}{2}}_{\text{area}} \underbrace{\frac{3s+0+0}{3}}_{\text{mean affine height}} =\frac{27s^3}{6}.\] Using (24), independence, and \(\mathbb E[T_+^3]=2/\sqrt{2\pi}\), we obtain \[Bt<\mathbb E[\mathbf 1_KT] \le \frac{27M}{6}\,\mathbb E[T_+^3] =\frac{9t^2(1+a_j)(1+a_k)}{2\pi\sqrt{2\pi}\,D_{jk}}.\] Since \(B=3/(2\sqrt{2\pi})\), this gives (22), in fact with a strict inequality. ◻ 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. Corollary 7 (Constraints on the three largest radii). The quantities \(L,c,t\) satisfy \[\begin{align*} (c-t^2)(L-c-2t^2) &\le8\left(\frac3\pi\right)^2t^2, \tag{25}\\ \frac32(c-t^2)^2 &\le10\left(\frac3\pi\right)^2t^2. \tag{26}\end{align*}\] Proof. For the first inequality, the signs and row sums of \(H\) give \[H_{31}^2+H_{32}^2 \le (|H_{31}|+|H_{32}|)^2\le h_3^2.\] It follows that \[ D_{31}^2+D_{32}^2\ge h_3(h_1+h_2-h_3). \tag{27}\] By (21) and \(0<a_j\le1\), \[h_3\ge c-t^2\ge0, \qquad h_1+h_2-h_3\ge L-c-2t^2.\] If \(L-c-2t^2\ge0\), these inequalities and (27) show that \[D_{31}^2+D_{32}^2\ge(c-t^2)(L-c-2t^2).\] If \(L-c-2t^2<0\), the same conclusion follows from the nonnegativity of the determinant squares. On the other hand, Lemma 6 gives \[D_{31}^2+D_{32}^2 \le\left(\frac3\pi\right)^2t^2 (1+a_3)^2\big((1+a_1)^2+(1+a_2)^2\big).\] Because \(a_1+a_2\le1-a_3\), \[(1+a_1)^2+(1+a_2)^2 \le (2-a_3)^2+1.\] For \(0\le x\le1\), the identity \[8-(1+x)^2\big((2-x)^2+1\big)=(1-x)^2(3-x^2)\ge0\] therefore proves (25). For the second inequality, let \(\rho_{jk}=H_{jk}/\sqrt{h_jh_k}\) for \(1\le j<k\le3\). These correlations belong to \([-1,0]\). Since \[0\le\operatorname{Var}\left(\sum_{j=1}^3\frac{Y_j}{\sqrt{h_j}}\right) =3+2\sum_{1\le j<k\le3}\rho_{jk},\] we have \[\sum_{j<k\le3}\rho_{jk}^2 \le\sum_{j<k\le3}|\rho_{jk}|\le\frac32.\] Each \(h_j\ge c-t^2\ge0\) for \(j\le3\). Thus \[ \sum_{j<k\le3}D_{jk}^2 =\sum_{j<k\le3}h_jh_k(1-\rho_{jk}^2) \ge\frac32(c-t^2)^2. \tag{28}\] To bound the sum furnished by Lemma 6, put \[s_1=a_1+a_2+a_3,\qquad s_2=a_1a_2+a_1a_3+a_2a_3,\qquad s_3=a_1a_2a_3.\] Equation (19) implies \(0\le s_1\le1\), \(0\le s_2\le s_1^2/3\le1/3\), and \(s_3\ge0\). Expanding in these elementary symmetric functions gives \[\begin{align*} \sum_{j<k\le3}(1+a_j)^2(1+a_k)^2 &=3+4s_1+2s_1^2+2s_1s_2+s_2^2-(6+2s_1)s_3\\ &\le3+4+2+\frac23+\frac19=\frac{88}{9}<10. \end{align*}\] Squaring (22), summing over the three pairs, and combining with (28) proves (26). ◻ Excluding five or more active cellsWe show that the scalar bounds of Lemma 4 and the geometric constraints of Corollary 7 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 \[r_1\ge\cdots\ge r_m=t>0,\qquad \sum_{j=1}^m r_j^2=1,\qquad L=r_1^2+r_2^2,\qquad c=r_3^2.\] Set \[ A=\begin{cases}.929,&m=5,\\.884,&m\ge6,\end{cases} \qquad d=A-.15,\qquad s=\frac{.415}{d}, \qquad e(u)=.415u-du^2. \tag{29}\] The probability excesses \(\delta_j=P_j-Ar_j^2\) satisfy, by (9), \[ \delta_j\ge\max\{0,e(r_j)\},\qquad \sum_{j=1}^m\delta_j=1-A. \tag{30}\] 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 7. The third radius and the small-minimum caseFirst we obtain a bound that holds for every value of \(t\). For \(j\ge3\), the inequality \(r_j\le\sqrt c\) gives \[e(r_j)=r_j^2\left(\frac{.415}{r_j}-d\right) \ge r_j^2\left(\frac{.415}{\sqrt c}-d\right).\] Summing these charges in (30) yields \[(1-L)\left(\frac{.415}{\sqrt c}-d\right)\le1-A.\] 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 \[ (1-L)\left(\frac{.415}{\sqrt c}-.734\right)\le.116. \tag{31}\] Since \(r_j\le2/3\), we have \(L\le8/9\). If \(\sqrt c\le.23\), the left side of (31) exceeds its right side by at least \[\frac19\left(\frac{.415}{.23}-.734\right)-.116 =\frac{101}{34500}>0.\] Consequently \[ \sqrt c>.23. \tag{32}\] Suppose now that \(t\le q_0:=.066\). We contradict (25), which reads \[ (c-t^2)(L-c-2t^2)\le8(3/\pi)^2t^2. \tag{33}\] If \(\sqrt c\ge.44\), then \(L\ge2c\), so the left side is at least \[(c-t^2)(c-2t^2) \ge(.44^2-q_0^2)(.44^2-2q_0^2).\] Both factors here are positive, and \[ (.44^2-q_0^2)(.44^2-2q_0^2) -8(3/\pi)^2q_0^2>.00321132. \tag{34}\] This contradicts (33). 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 (31) gives \[L-c-2t^2 \ge 1-\frac{.116}{.415/b-.734}-b^2-2q_0^2 =:M(b).\] Also \(c-t^2\ge a^2-q_0^2>0\). Every \(M(b)\) is positive, and the last column of the table contradicts (33). Thus \[ t>.066. \tag{35}\]
Bounding the remaining radiiWe next prove that \[ r_j\le.42\qquad(j\ge4). \tag{36}\] Suppose instead that \(r_4>.42\), and put \[K=\frac{d\cdot.42}{s+.42}.\] For every \(u\ge.42\) we have \[ \max\{0,e(u)\}\ge K(s^2-u^2). \tag{37}\] Indeed, when \(u\le s\), use \[e(u)=\frac{du}{s+u}(s^2-u^2) \quad\hbox{and}\quad \frac{u}{s+u}\ge\frac{.42}{s+.42}.\] When \(u>s\), the right side of (37) is negative, so nonnegativity proves the inequality. Applying this to the first four radii and using the minimum radius on the others gives \[\sum_{j=1}^4\delta_j \ge K\left(4s^2-\sum_{j=1}^4r_j^2\right) \ge K\bigl(4s^2-1+(m-4)t^2\bigr).\] For \(j\ge5\), ordering and normalization give \(r_j\le1/\sqrt5\). By (35), these radii lie in \([.066,1/\sqrt5]\). Concavity of \(e\) therefore gives \[\delta_j\ge\min\{e(.066),e(1/\sqrt5)\}=e(.066).\] 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 \[ 1-A\ge K\bigl(4s^2-1+(m-4)(.066)^2\bigr)+(m-4)e(.066). \tag{38}\] 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 (36).
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, \[ ke(.42)-(1-A)= \begin{cases}.0027688,&A=.929,\\.0184672,&A=.884. \end{cases} \tag{39}\] Hence (30) forces \(ke(t)\le1-A\). Let \(t_0\) be the smaller root of \(ke(u)=1-A\): \[ t_0=\frac{.415-\sqrt{.415^2-4d(1-A)/k}}{2d}. \tag{40}\] Equation (39) 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 \[ \begin{aligned} .1070554<t_0<.1070555&\qquad(A=.929),\\ .1176565<t_0<.1176566&\qquad(A=.884) \end{aligned} \tag{41}\] 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)\). The final contradictionWe claim that \[ c>2.6t. \tag{42}\] Otherwise, (32) places the third radius in \([.23,\sqrt{2.6t}]\). It is distinct from the \(k\) indices just charged, so concavity of \(e\) and (30) imply \[ 1-A\ge\min\{e(.23),e(\sqrt{2.6t})\}+ke(t). \tag{43}\] 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 (40). Thus \[e(.23)+ke(t)-(1-A) \ge e(.23)+ke(.066)-(1-A)>0,\] by Table 4. Second, the function \[F(t)=e(\sqrt{2.6t})+ke(t) =.415\sqrt{2.6t}-2.6dt+k(.415t-dt^2)\] is strictly concave for \(t>0\), since \[F''(t)=-\frac{.415\sqrt{2.6}}{4t^{3/2}}-2kd<0.\] 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 (43) and prove (42).
Finally, (26), (42), and \(0<t<.12\) give \[10(3/\pi)^2t^2 \ge1.5(c-t^2)^2 >1.5(2.6-.12)^2t^2.\] But \[1.5(2.6-.12)^2-10(3/\pi)^2>.10667806>0.\] This contradiction rules out \(C>B^2\) and completes the upper bound. Completion of the proof of Theorem 1. Section 5 rules out \(C>9/(8\pi)\) for the supremum defined in Section 2. The product-and-empty-cell reduction at the start of that section transfers this bound to every dimension and finite cell count. The construction in Section 1.1 attains the bound whenever \(d\ge2\) and \(k\ge3\). ◻ Gaussian maximaThe partition bound also gives a sharp inequality for Gaussian maxima. The four-score version appears in Heilman, Jagannath, and Naor [4]; Gaussian partition duality is due to Khot and Naor [5]. Subtracting the common average score gives the following centered form in every dimension. Corollary 8 (Gaussian maxima). Let \(d,k\) be positive integers, let \(g\) be standard Gaussian in \(\mathbb R^d\), and let \(v_1,\ldots,v_k\in\mathbb R^d\), with \(\bar v=k^{-1}\sum_{i=1}^k v_i\). Then \[\mathbb E\max_{1\le i\le k}\langle v_i,g\rangle \le\frac{3}{2\sqrt{2\pi}} \left(\sum_{i=1}^k\|v_i-\bar v\|^2\right)^{1/2}.\] The constant is sharp already for three vectors in the plane. Proof. Put \(u_i=v_i-\bar v\). Subtracting the common score \(\langle\bar v,g\rangle\) leaves the expected maximum unchanged. Partition \(\mathbb R^d\) according to the largest score \(\langle u_i,x\rangle\), resolving ties by the smallest index, and let \(z_i\) be the Gaussian first moments of these cells. Then Theorem 1 and Cauchy–Schwarz give \[\mathbb E\max_i\langle v_i,g\rangle =\sum_i\langle u_i,z_i\rangle \le\left(\sum_i\|u_i\|^2\right)^{1/2} \left(\sum_i\|z_i\|^2\right)^{1/2} \le\frac{3}{2\sqrt{2\pi}} \left(\sum_i\|u_i\|^2\right)^{1/2}.\] For sharpness, take the three centroid vectors of the planar propeller in Section 1.1. Their sum is zero, their score cells are the propeller sectors, and both inequalities are equalities. ◻ 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\). A kernel-clustering applicationThe objective and the approximation thresholdThis application uses Theorem 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\mathbf 1=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 \[ \operatorname{val}_A(\sigma)=\sum_{p,q=1}^N a_{pq}\mathbf 1_{\{\sigma(p)=\sigma(q)\}}, \qquad \operatorname{Clust}(A\mid I_k)=\max_{\sigma:[N]\to[k]}\operatorname{val}_A(\sigma). \tag{44}\] 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 \(\mathbf 1_{S_i}^{\mathsf T}A\mathbf 1_{S_i}\). A deterministic approximation with loss factor \(\alpha\ge1\) returns an assignment of value at least \(\operatorname{Clust}(A\mid I_k)/\alpha\). An expected approximation has the same inequality with the returned value replaced by its expectation. Put \[c_*=\frac9{8\pi}, \qquad \alpha_k=\frac{1-1/k}{c_*} =\frac{8\pi}{9}\left(1-\frac1k\right).\] The matching rounding constant.Khot and Naor’s approximation theorem [5] gives the expected rounding bound \[\mathbb E\operatorname{val}_A(\sigma)\ge\frac{\operatorname{Clust}(A\mid I_k)}{\alpha_k}\] on the inputs in (44). 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. Theorem 9 (Kernel-clustering hardness). For each fixed \(k\ge3\) and every fixed \(1\le\alpha<\alpha_k\), it is NP-hard, given a rational symmetric matrix \(A\succeq0\) with \(A\mathbf 1=0\) and the identity-target objective (44), to find \(\sigma:[N]\to[k]\) such that \[\operatorname{val}_A(\sigma)\ge\operatorname{Clust}(A\mid I_k)/\alpha.\] In particular, such a deterministic polynomial-time approximation would imply \(\mathrm P=\mathrm{NP}\). 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]. Here the target is \(I_k\), and the Gaussian constant is supplied by Theorem 1. The two external hardness inputsThe Gaussian parameter in Khot and Naor’s theorem is \[C_k:=\sup_{(B_1,\ldots,B_k)} \sum_{i=1}^k \left\|\int_{B_i}x\,d\gamma_{k-1}(x)\right\|^2.\] The supremum ranges over measurable partitions of \(\mathbb R^{k-1}\), with empty cells allowed. Since \(k\ge3\), Theorem 1 and the attaining example in Section 1.1 give \[ C_k=c_*. \tag{45}\] 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\mathbb N\) and \(\nu\in\{0,\ldots,k-1\}^r\), write \[b_\nu(x)=\prod_{j=1}^r b_{\nu_j}(x_j), \qquad |\nu|=\bigl|\{j:\nu_j\ne0\}\bigr|.\] Every \(h:\Omega^r\to\mathbb R\) has expansion \(h=\sum_\nu\widehat h(\nu)b_\nu\), with coefficients computed using uniform probability measure. For real \(D\ge0\), set \[ \operatorname{Inf}_j^{\le D}(h)= \sum_{\substack{|\nu|\le D\\\nu_j\ne0}}\widehat h(\nu)^2. \tag{46}\] 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 \[\operatorname{OBJ}(f)=\sum_{i=1}^k\|P_1f_i\|_2^2.\] All \(L_2\) norms in this section use uniform probability measure. Define the closed simplex with slack by \[\Delta_k=\{u\in\mathbb R^k:u_i\ge0,\ \sum_{i=1}^k u_i\le1\}.\] Theorem 10 (Khot–Naor low-influence bound). For fixed \(k\) and every \(\eta>0\), there exists \(0<\tau_0<1/2\), independent of \(r\), such that every \(r\in\mathbb N\) and every \(f:\Omega^r\to\Delta_k\) satisfying \[\operatorname{Inf}_j^{\le\log(1/\tau_0)}(f_i)\le\tau_0 \quad(i\in[k],\ j\in[r])\] obey \(\operatorname{OBJ}(f)\le C_k+\eta\). This is [5], 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 \[ D=\max\{1,\lceil\log(1/\tau)\rceil\}. \tag{47}\] Monotonicity of (46) in the cutoff gives the useful contrapositive \[ \operatorname{OBJ}(f)>C_k+\eta \quad\Longrightarrow\quad \operatorname{Inf}_j^{\le D}(f_i)>\tau \text{ for some }i\in[k],\ j\in[r]. \tag{48}\] 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 11 (Unique Games input). For every fixed \(\varepsilon,\delta\in(0,1/2)\), there are an integer \(s\ge1\) and a deterministic polynomial-time reduction from \(\mathrm{3SAT}\) to explicit unweighted simple bipartite Unique Games instances over \(\mathbb F_2^s\). If the formula is satisfiable the game has a labeling satisfying at least \(1-\varepsilon\) of its edges; if it is unsatisfiable every labeling satisfies at most \(\delta\) of its edges. The edge set is nonempty and each constraint is a translation of the alphabet. The alphabet size and the polynomial’s degree and constants depend only on \(\varepsilon,\delta\). 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. A rational centered positive semidefinite matrixLet \(G=(V,W,E)\) be a game supplied by Theorem 11, 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 \[\ell(v)=\pi_{vw}(\ell(w)).\] Translations are permutations, so this changes no game value. Delete isolated vertices, put \(M=|E|\), and write \[d_v=|N(v)|,\qquad \mu(v)=\frac{d_v}{M}\quad(v\in V).\] 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 \[(R_\pi x)_a=x_{\pi(a)}\quad(a\in[r]).\] For a scalar table \(h:W\times\Omega^r\to\mathbb R\), define \[ (T_vh)(x)=\frac1{d_v} \sum_{w\in N(v)}h(w,R_{\pi_{vw}}x), \qquad Q(h)=\sum_{v\in V}\mu(v)\|P_1T_vh\|_2^2 . \tag{49}\] The output matrix will represent \(Q\) in the ordinary, unnormalized Euclidean coordinates of the table \(h\). Lemma 12. For fixed \(k,r\), one can construct in deterministic polynomial time a rational symmetric matrix \(A\), indexed by \(W\times\Omega^r\), such that \[h^{\mathsf T}Ah=Q(h),\qquad A\succeq0,\qquad A\mathbf 1=0 .\] For every \(\sigma:W\times\Omega^r\to[k]\), if \(F_i(w,x)=\mathbf 1_{\{\sigma(w,x)=i\}}\), then \[ \operatorname{val}_A(\sigma)= \sum_{v\in V}\mu(v)\operatorname{OBJ}(F_v),\qquad F_v=(T_vF_1,\ldots,T_vF_k):\Omega^r\to\Delta_k. \tag{50}\] All output assignment values lie in \([0,1]\). Proof. Put \(q=k^r\). The projection \(P_1\), written as a matrix acting on the counting-coordinate vector \((h(x))_{x\in\Omega^r}\), is \[ (P_1)_{x,y}=\frac1q \sum_{j=1}^r\bigl(k\mathbf 1_{\{x_j=y_j\}}-1\bigr). \tag{51}\] To see this, the centered subspaces of functions of distinct individual coordinates are mutually orthogonal. Hence \[(P_1h)(x)= \sum_{j=1}^r\bigl(\mathbb E[h(X)\mid X_j=x_j]-\mathbb Eh(X)\bigr),\] which is (51). This matrix is rational, symmetric and idempotent. The counting-coordinate matrix of \(T_v\) has entries \[(T_v)_{x,(w,y)} =\frac1{d_v}\mathbf 1_{\{w\in N(v)\}} \mathbf 1_{\{y=R_{\pi_{vw}}x\}} .\] Define \[ A=\frac1q\sum_{v\in V}\mu(v)T_v^{\mathsf T}P_1T_v. \tag{52}\] There are two factors \(q^{-1}\): one in (51), and one outside the sum in (52) because \(L_2\) uses probability measure. Symmetry and \(P_1^2=P_1\) give \[h^{\mathsf T}Ah =\sum_v\mu(v)\frac1q\|P_1T_vh\|_{\ell_2}^2=Q(h)\ge0.\] Also \(T_v\mathbf 1=\mathbf 1\) and \(P_1\mathbf 1=0\), so (52) gives \(A\mathbf 1=0\). There are \(N=|W|k^r\) output indices. For fixed \(k,r\) this is polynomial in the explicit game size, and the dense matrix can be computed by rational arithmetic in polynomial time. Its entries are sums of terms with denominators dividing \(M d_v q^2\). A common denominator divides \(M q^2\prod_{v\in V}d_v\), whose bit length is \(O(\log M+\sum_v\log d_v+\log q)\), and the numerators also have polynomial bit length. No irrational Fourier basis needs to be constructed. By definition of the ordered sum, \(\operatorname{val}_A(\sigma)=\sum_iF_i^{\mathsf T}AF_i\); inserting (49) proves (50). Every \(F_v(x)\) is an average of coordinate unit vectors, so its entries are nonnegative and sum to one. Parseval and orthogonal projection give \[ 0\le\operatorname{OBJ}(F_v) \le\sum_{i=1}^k\|F_{v,i}\|_2^2 \le\mathbb E\sum_{i=1}^k F_{v,i}=1. \tag{53}\] Since \(\sum_v\mu(v)=1\), the last claim follows. ◻ Completeness and weighted decodingThe next two lemmas compare ordinary edge-value completeness and soundness with the kernel objective. They adapt the Khot–Naor reduction [5] to the precise input of Theorem 11. Lemma 13 (Completeness). If a labeling of \(G\) satisfies at least \(1-\varepsilon\) of its edges, then the matrix of Lemma 12 satisfies \[\operatorname{Clust}(A\mid I_k)\ge \left(1-\frac1k\right)(1-\varepsilon)^2.\] Proof. Use a witnessing labeling \(\ell\) to set \(\sigma(w,x)=x_{\ell(w)}\). For \(j\in[r]\), let \(D_j(x)=e_{x_j}\), where \(e_1,\ldots,e_k\) are the coordinate unit vectors in \(\mathbb R^k\). With \[p_{v,j}= \Pr_{w\in N(v)}\{\pi_{vw}(\ell(w))=j\},\] the chosen permutation convention gives \(F_v=\sum_{j=1}^r p_{v,j}D_j\). For each \(i\), the level-one part of the \(i\)-th component of \(D_j\) is \(\mathbf 1_{\{x_j=i\}}-1/k\). These parts for different \(j\)’s are orthogonal. Moreover, \[\sum_{i=1}^k \mathbb E\bigl(\mathbf 1_{\{X_j=i\}}-1/k\bigr)^2=1-\frac1k.\] It follows that \[\operatorname{OBJ}(F_v)= \left(1-\frac1k\right)\sum_{j=1}^r p_{v,j}^2 \ge \left(1-\frac1k\right)p_{v,\ell(v)}^2.\] The weighted mean \(\mathbb E_{v\sim\mu}p_{v,\ell(v)}\) is exactly the satisfied-edge fraction of \(\ell\), and is therefore at least \(1-\varepsilon\). Jensen’s inequality and (50) prove the claim. ◻ Lemma 14 (Soundness). Fix \(\eta>0\) with \(C_k+2\eta<1\), and choose \(\tau,D\) as in (47) for this \(\eta\). If every labeling of \(G\) satisfies at most \(\delta\) of its edges, where \[ 0<\delta<\frac{\eta\tau^2}{4kD}, \tag{54}\] then \(\operatorname{Clust}(A\mid I_k)\le C_k+2\eta\). Proof. Suppose an assignment \(\sigma\) gives a larger value, and use the functions in Lemma 12. Let \[V_{\mathrm{good}}= \{v:\operatorname{OBJ}(F_v)>C_k+\eta\}.\] If its \(\mu\)-mass is \(\beta\), then (53) gives \[\sum_v\mu(v)\operatorname{OBJ}(F_v) \le\beta+(1-\beta)(C_k+\eta) \le C_k+\eta+\beta.\] The assumed objective therefore forces \(\beta>\eta\). For every \(v\in V_{\mathrm{good}}\), (48) supplies \(i_v\in[k]\) and \(j_v\in[r]\) with \(\operatorname{Inf}_{j_v}^{\le D}(F_{v,i_v})>\tau\). Taking the squared norm of the relevant Fourier coefficients in the neighbor average, and using convexity, gives \[ \operatorname{Inf}_{j_v}^{\le D}(F_{v,i_v}) \le \frac1{d_v}\sum_{w\in N(v)} \operatorname{Inf}_{\pi_{vw}^{-1}(j_v)}^{\le D}(F_{i_v}(w,\cdot)). \tag{55}\] The inverse permutation in this formula follows directly from \((R_\pi x)_a=x_{\pi(a)}\): the Fourier indices involving left coordinate \(j_v\) come from right coordinate \(\pi^{-1}(j_v)\). Every influence on the right belongs to \([0,1]\), by Parseval and \(0\le F_i(w,\cdot)\le1\). An average exceeding \(\tau\) has more than a \(\tau/2\) fraction of its entries at least \(\tau/2\): otherwise its average is at most \(\tau/2+(\tau/2)\cdot1\le\tau\). For each \(w\in W\), form the finite label list \[L(w)= \{a\in[r]:\operatorname{Inf}_a^{\le D}(F_i(w,\cdot))\ge\tau/2 \text{ for some }i\in[k]\}.\] For every scalar \(h\), counting how often a Fourier coefficient contributes gives \[\sum_{a=1}^r\operatorname{Inf}_a^{\le D}(h) =\sum_{|\nu|\le D}|\nu|\,\widehat h(\nu)^2 \le D\|h\|_2^2.\] Consequently \[ |L(w)|\frac{\tau}{2} \le\sum_{i=1}^k\sum_{a=1}^r \operatorname{Inf}_a^{\le D}(F_i(w,\cdot)) \le kD, \qquad |L(w)|\le\frac{2kD}{\tau}. \tag{56}\] Label a good \(v\) by \(j_v\), and other left vertices arbitrarily. Independently label each right vertex uniformly from \(L(w)\) when this list is nonempty, and arbitrarily otherwise. For a good \(v\), more than a \(\tau/2\) fraction of its neighbors have \(\pi_{vw}^{-1}(j_v)\in L(w)\), by (55). On each such edge the random label at \(w\) satisfies the constraint with probability at least \(\tau/(2kD)\), by (56). The expected fraction of satisfied edges is therefore greater than \[\eta\cdot\frac{\tau}{2}\cdot\frac{\tau}{2kD} =\frac{\eta\tau^2}{4kD}.\] Here the weights \(\mu(v)=d_v/M\) ensure that this is the uniform-edge fraction. Some deterministic labeling attains at least its expectation, contradicting (54). ◻ Completing the reductionProof of the hardness assertion in Theorem 9. Fix \(k\ge3\) and \(1\le\alpha<\alpha_k\). First choose rational \(\varepsilon,\eta>0\) sufficiently small that \(\varepsilon<1/2\), \(c_*+2\eta<1\), and \[ \alpha< \frac{(1-1/k)(1-\varepsilon)^2}{c_*+2\eta}. \tag{57}\] Next choose \(\tau,D\) from Theorem 10 and (47); these depend on \(k,\eta\), not the game size. Choose a rational \[0<\delta< \min\left\{\frac12,\frac{\eta\tau^2}{4kD}\right\}.\] Apply Theorem 11 with these fixed errors. Only at this stage is the fixed alphabet size \(r=2^s\) determined. In particular \(k^r\) is a constant with respect to the input formula size, although no uniform bound polynomial in the error reciprocals is asserted. Compose that deterministic reduction with Lemma 12. Lemmas 13 and 14, together with (45), give the gap \[\begin{aligned} \varphi\text{ satisfiable} &\ \Longrightarrow\ \operatorname{Clust}(A_\varphi\mid I_k)\ge H:=(1-1/k)(1-\varepsilon)^2,\\ \varphi\text{ unsatisfiable} &\ \Longrightarrow\ \operatorname{Clust}(A_\varphi\mid I_k)\le S:=c_*+2\eta . \end{aligned}\] The output is a rational symmetric centered PSD matrix with polynomial dimension and bit length. By (57), \(S<H/\alpha\). Choose a fixed rational \(\theta\) strictly between these numbers. A deterministic loss-factor-\(\alpha\) algorithm produces value greater than \(\theta\) on satisfiable formulas; every assignment has value less than \(\theta\) on unsatisfiable formulas. The returned value is an exactly computable rational number. This would decide \(\mathrm{3SAT}\) in polynomial time. Thus achieving the stated factor is NP-hard. ◻ Remark 15 (Randomized guarantees). The quoted Khot–Naor rounding guarantee is in expectation. The deterministic hardness conclusion of Theorem 9 does not use \(\mathrm P\ne\mathrm{NP}\) to exclude randomized algorithms. More precisely, a polynomial-time randomized algorithm whose expected value is at least \(\operatorname{Clust}(A\mid I_k)/\alpha\) for some fixed \(\alpha<\alpha_k\) would place \(\mathrm{3SAT}\) in \(\mathrm{RP}\). Indeed, on the reduction instances its returned value \(X\) lies in \([0,1]\). In the satisfiable case \(\mathbb EX\ge H/\alpha>\theta\); therefore \[\Pr\{X>\theta\}\ge \frac{H/\alpha-\theta}{1-\theta}>0.\] This is a fixed positive constant. In the unsatisfiable case \(X\le S<\theta\) always. A fixed number of repetitions gives one-sided success probability at least \(1/2\). Remark 16 (Inputs to the application). The Gaussian proof supplies only (45). Khot and Naor supply the expected rounding guarantee [5] and the analytic low-influence bound [5]. Their reduction in Section 3.3 is the model for Lemmas 12–14; the degree weights and the squared completeness loss explicitly accommodate the ordinary edge-value, possibly nonregular instances from [9]. No stronger Unique Games promise is assumed. The separate Unique Games theorem is a formal dependency only of this hardness application. The algorithmic endpoint is quoted in its ideal rounding formulation; this section supplies no finite-precision endpoint implementation. Elementary certificates for the numerical inequalitiesThis 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. Enclosure formulasWe use \[ 3.14159<\pi<3.14160. \tag{58}\] 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 \[\frac{\lfloor\sqrt{\lfloor xD^2\rfloor}\rfloor}{D} \le\sqrt{x}\le \frac{\lfloor\sqrt{\lfloor xD^2\rfloor}\rfloor+1}{D}.\] 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 \[E_N(y)=\sum_{j=0}^N\frac{(-y)^j}{j!}.\] Taylor’s integral remainder gives \[ E_{15}(y)\le e^{-y}\le E_{14}(y). \tag{59}\] This conclusion does not require the initial terms of the series to be decreasing. Integrating the same bounds, set \[J_N(x)=\sum_{j=0}^N \frac{(-1)^j x^{2j+1}}{2^j j!(2j+1)},\qquad x\ge0.\] Then \[ \frac12+\frac{J_{15}(x)}{\sqrt{2\pi}} \le\Phi(x)\le \frac12+\frac{J_{14}(x)}{\sqrt{2\pi}},\qquad \Phi(-x)=1-\Phi(x). \tag{60}\] Together with (58) 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 \[Q(x)=\sum_{j=0}^4\frac{\binom{2j}{j}}{4^j(2j+1)}x^{2j+1}.\] 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\), \[ Q(x)\le\arcsin x\le Q(x)+\frac{x^{11}}{11(1-x^2)}. \tag{61}\] The two rearrangement minimaWrite \(f(x)=(9/4)e^{x^2}\Phi(-x)\) and \(D_f(x)=2x-\phi(x)/\Phi(-x)\), as in (10). Substitution into (59)–(60) gives the following strict enclosures: \[\begin{array}{rcl} -0.000131&<&D_f(0.6119)<-0.000126,\\ 0.000120&<&D_f(0.6121)< 0.000124,\\ -0.000430&<&D_f(x)<0.000424 \quad(0.6119\le x\le0.6121),\\ 0.884383832&<&f(0.612). \end{array}\] 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 \[\min f\ge f(0.612)e^{-10^{-7}} >0.884383832(1-10^{-7})>0.8843837.\] For \(p,F,H,R\) from (12) and its following calculation, (61) gives \[\begin{array}{rcl} -0.0047010&<&F(0.29)<-0.0046981,\\ 0.0007683&<&F(0.294)<0.0007712,\\ 0.9312526&<&R(0.29),\\ 0.22198&<&p(0.294)-0.294/\pi. \end{array}\] For \(0.29\le x\le0.294\), the last row implies \[H(x)=p(x)-\frac{x\sqrt{1-x^2}}\pi \ge p(0.294)-\frac{0.294}\pi>0.\] Therefore \(F\) is increasing throughout the interval, and the first two rows imply \(|F(x)|<0.004702\) there. Consequently \[|R'(x)|<\frac{(9/4)0.004702}{(1-0.294^2)^4} <0.015189<0.03.\] This proves the derivative bound on the entire interval. The minimum therefore exceeds \(0.9312526-0.03(0.004)=0.9311326\). Quantiles and the interval probability boundsFor \(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 (59)–(60) and the definition of \(G\). Since \(G\) is nonincreasing, \[G\bigl(\Phi^{-1}(P_0(r))\bigr)\le G(q_a) \qquad(r\ge a).\] 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.
|
| ||||||||
|