Split ordinary d-dimensional space R^d into finitely many regions
A_1, ..., A_k. Weight every point by the standard bell-curve
(Gaussian) density. For each region A_i, integrate the position vector
x against this density over A_i, without dividing by the mass of A_i.
Call the resulting vector z(A_i) the "Gaussian centroid" of A_i. The
Gaussian propeller theorem states:
sum over i of ||z(A_i)||^2 is at most 9/(8 pi) = 0.3581...
The bound holds for every number of regions, with any shapes and any
sizes. It is attained, exactly, by three 120-degree pie slices of the
plane, extended by extra orthogonal coordinates in higher dimensions.
No partition exceeds this value.
The Gaussian propeller theorem. For every finite measurable partition
of a Euclidean space, the sum of the squared lengths of the Gaussian
first moments of its cells is at most 9/(8 pi). The bound is attained,
in every dimension d >= 2, by three planar sectors of angle 2 pi/3
extended by an orthogonal Euclidean factor, with any further cells
empty.
Definitions. Let gamma_d be the standard Gaussian probability measure
on R^d, with density
phi_d(x) = (2 pi)^(-d/2) exp( -||x||^2 / 2 ).
For a measurable set A in R^d, define its Gaussian first moment
z(A) = integral_A x d gamma_d(x).
z(A) is the Gaussian centroid of A, but note carefully: z(A) is
NOT divided by the Gaussian measure of A. So z(A) is not an average
position -- it is the vector "balance point" of A's probability mass.
Equivalently, if X is a gamma_d-random point, z(A) is the probability
of landing in A times the average position given landing in A.
For a measurable partition A_1, ..., A_k of R^d (cells may be empty;
partitions are understood up to gamma_d-null sets), define
F(A_1, ..., A_k) = sum_{i=1}^k ||z(A_i)||^2.
The Gaussian propeller conjecture asks: what is the largest possible
value of F? The conjecture is that the maximum is 9/(8 pi), attained
by the "propeller" configuration below whenever d >= 2 and k >= 3.
Historical context. The conjecture arose in Khot and Naor's study of
approximate kernel clustering, where Gaussian first moments govern
the performance of certain approximation algorithms. Khot and Naor
proved that an optimal partition may be chosen conical in the span of
its centroids, and computed the three-cell value. Heilman,
Jagannath, and Naor later proved the bound for every finite partition
of R^3. Heilman later gave a conditional route through hyperstable
sets for three or four cells, and a 2026 preprint recasts the
three-dimensional proof without computer assistance. All remaining
dimensions and all cell counts are treated below.
Approximate kernel clustering Khot+Naor 2009: ./khot-naor-2009.pdf
> In the kernel clustering problem one is given a large n x n
> positive semi-definite matrix A with sum of entries zero and a
> small k x k positive semi-definite matrix B; the goal is to
> partition the indices into k cells maximizing the quadratic form.
Solution of the propeller conjecture in R^3 Heilman+Jagannath+Naor 2013: ./heilman-jagannath-naor-2013.pdf
> Every measurable partition {A_1, ..., A_k} of R^3 satisfies
> sum_i || integral_{A_i} x e^{-||x||^2 / 2} dx ||^2 <= 9 pi^2.
> The bound is sharp, with equality for A_i = P_i x R on three
> 120-degree planar sectors.
Hyperstable sets with voting and algorithmic hardness applications Heilman 2022: ./heilman-2022.pdf
> Under the assumption that a maximizing partition is hyperstable:
> a (conditional) version of the Propeller Conjecture of Khot and
> Naor for 4 sets.
On the Propeller Conjecture Heilman 2026: ./on-propeller-conjecture-2026.pdf
> the sum of the squared lengths of the Gaussian moments of any
> partition of Euclidean space is at most 9/(8 pi).
THEOREM 1.1 (Gaussian propeller bound). For all positive integers d
and k, every measurable partition (A_1, ..., A_k) of R^d satisfies
sum_{i=1}^k || integral_{A_i} x d gamma_d(x) ||^2 <= 9/(8 pi).
Empty cells are allowed. The constant is sharp whenever d >= 2 and
k >= 3: three planar sectors of angle 2 pi/3, multiplied by the
orthogonal complement of their plane, attain equality, with any
further cells empty.
Consider a sector P in R^2 with opening 2 alpha, symmetric about the
first coordinate axis. In polar coordinates (r, theta), the Gaussian
measure on R^2 is (1/(2 pi)) exp(-r^2/2) r dr dtheta. So
integral_P x d gamma_2(x)
= (1/(2 pi)) (integral_0^infty r^2 e^{-r^2/2} dr)
(integral_{-alpha}^{alpha} (cos theta, sin theta) d theta)
= (sin alpha / sqrt(2 pi)) (1, 0).
The radial integral equals sqrt(2 pi)/2, and the angular integral
equals (2 sin alpha, 0); their product divided by 2 pi is the
displayed result.
For alpha = pi/3, three sectors of opening 2 alpha tile the plane.
Their squared centroid lengths sum to
3 sin^2(pi/3) / (2 pi) = 3 (3/4) / (2 pi) = 9 / (8 pi).
An orthogonal Gaussian factor contributes zero to every centroid: the
joint density factors, and the extra coordinates integrate against x
to zero. So the same construction has the same value in every
dimension d >= 2. This proves the attainment half of Theorem 1.1.
The name "propeller": three blades of opening 120 degrees radiate from
the origin, symmetric under rotations by 2 pi/3. In dimension d >= 3,
extend every blade to the product with R^{d-2}. The extra coordinates
contribute nothing to the centroids.
The proof has three moves.
(a) Reduce to finitely many Gaussian scores. By norm duality, the
square root of the largest possible F-value equals the largest possible
expected maximum of k Gaussian linear scores, over k vectors whose
squared norms sum to one. Compactness then gives an extremizer.
(b) Constrain the extremizer's centroids. At an optimal partition with
the fewest active cells, the centroids have strictly negative pairwise
inner products, span a space of dimension m-1, and each cell is a
conical region where one score is largest. If m <= 4, the
three-dimensional propeller theorem of Heilman, Jagannath, and Naor
applies directly. So the only case left is m >= 5.
(c) Bound the m >= 5 case via two constraints.
- Scalar: removing one score costs a definite amount of expected
maximum. Ehrhard's inequality turns this loss into a lower bound on
each cell's probability P_i in terms of its normalized radius r_i.
- Geometric: use the cell with the smallest centroid. Project other
centroids onto its orthogonal direction; the residual scores are
Gaussian, independent of the small-direction score, and integrate
to zero over the chosen cell. This forces a determinant bound on
pairs of residuals, which translates into inequalities among the
three largest radii and the smallest.
(d) Eliminate. Combine the scalar bounds with sum P_i = 1. This rules
out an optimal configuration with m >= 5 active cells whose value
exceeds 9/(8 pi).
External inputs used below: the HJN 3-D propeller theorem, and
Ehrhard's inequality for convex sets, extended by Latala to one convex
set and re-proved by van Handel via a stochastic game. Everything else
is proved below. The kernel-clustering application also uses Khot-Naor's
discrete Fourier estimate and the Unique Games Conjecture of Khot.
Symetrisation dans l'espace de Gauss Ehrhard 1983: ./ehrhard-1983.pdf
A note on the Ehrhard inequality Latala 1996: ./latala-1996.pdf
The Borell-Ehrhard game van Handel 2018: ./van-handel-2018.pdf
On the Unique Games Conjecture Khot: ./khot-ugc-survey.pdf
> This article surveys recently discovered connections between the
> Unique Games Conjecture and computational complexity, algorithms,
> discrete Fourier analysis, and geometry.
It suffices to prove the bound for N = n+1 cells in R^n with n >= 4.
Given k cells in R^d:
- put n = max(d, k-1, 4);
- replace each cell A_i by A_i x R^{n-d};
- append n+1-k empty cells.
The centroid of A_i x R^{n-d} equals (z(A_i), 0, ..., 0), so its
squared length is unchanged.
Fix n >= 4 and N = n+1. Define
C = sup over measurable partitions (A_1, ..., A_N) of R^n of
sum_{i=1}^N || integral_{A_i} x d gamma_n(x) ||^2,
B = 3 / (2 sqrt(2 pi)).
Cauchy-Schwarz on each cell gives C <= n < infinity.
LEMMA 3.1 (Norm duality; after Khot and Naor). Let g be standard
Gaussian in R^n. Then
sqrt(C) = max over lists v_1, ..., v_N with
sum_{i=1}^N ||v_i||^2 = 1, of
E max_{1 <= i <= N} <v_i, g>.
The maximum is attained. Moreover, for every 1 <= k <= N and any list
v_1, ..., v_k in R^n,
E max_{1 <= i <= k} <v_i, g>
<= sqrt(C) * ( sum_{i=1}^k ||v_i||^2 )^{1/2}.
Proof of Lemma 3.1. For any partition with centroids z_i, norm duality
gives
(sum_i ||z_i||^2)^{1/2}
= max over lists with sum_i ||v_i||^2 = 1 of sum_i <v_i, z_i>.
For a fixed list, sum_i <v_i, z_i> = E[<v_{sigma(X)}, X>] where X is
gamma_n-distributed and sigma(X) is the label of the cell containing X.
This is at most E max_i <v_i, X> = E max_i <v_i, g>. Taking suprema
over partitions and lists gives (sum-side) <= (max-side).
Conversely, for any list v, let K_i = {x : <v_i, x> >= <v_j, x> for
all j}, with the smallest index winning ties. The K_i are a partition,
and sum_i <v_i, z(K_i)> = E max_i <v_i, g>. By Cauchy-Schwarz and the
definition of C,
sum_i <v_i, z(K_i)>
<= (sum_i ||v_i||^2)^{1/2} (sum_i ||z(K_i)||^2)^{1/2}
<= (sum_i ||v_i||^2)^{1/2} * sqrt(C).
So (max-side) <= (sum-side). Equality follows.
Attainment: the map v -> E max_i <v_i, g> is continuous (it is
1-Lipschitz in max_i ||v_i||, with ||g|| as Lipschitz constant), and
the constraint set {sum ||v_i||^2 = 1} is compact.
Shorter-list inequality. Given v_1, ..., v_k and score cells Q_i,
appending N-k empty cells gives sum_i ||z(Q_i)||^2 <= C. Then
E max_{1<=i<=k} <v_i, g>
= sum_i <v_i, z(Q_i)>
<= (sum_i ||v_i||^2)^{1/2} (sum_i ||z(Q_i)||^2)^{1/2}
<= sqrt(C) (sum_i ||v_i||^2)^{1/2}.
From now on assume, for contradiction,
C > B^2 = 9 / (8 pi).
Among all optimal partitions, choose one with the fewest active
(positive-measure) cells. Discard its null cells; call the remaining
ones active, and denote their centroids by z_1, ..., z_m. Then
sum_{i=1}^m z_i = 0,
sum_{i=1}^m ||z_i||^2 = C.
The first identity holds because summing integral_{A_i} x dgamma(x)
over a partition recovers integral x dgamma_n(x) = 0 (gamma_n is
centered).
LEMMA 3.2 (Structure of the centroids; after Khot and Naor). The
centroids satisfy <z_i, z_j> < 0 whenever i != j. Their span V has
dimension m-1. Every proper subset of the centroids is linearly
independent. For each fixed i, the m-1 vectors z_i - z_j (j != i) form
a basis of V. The optimal cells have the closed conical representatives
K_i = {x : <z_i - z_j, x> >= 0 for every j != i}.
Moreover, m >= 5.
Proof of Lemma 3.2.
Step 1: pairwise negativity. Merging two cells i, j into one changes
the value of F by exactly 2 <z_i, z_j>. If <z_i, z_j> > 0, the merged
partition would be better, contradicting optimality. If <z_i, z_j> = 0,
merging keeps the value and reduces the number of active cells,
contradicting minimality of m. Hence every <z_i, z_j> < 0 with i != j;
in particular every z_i is nonzero.
Step 2: optimal cells are the score cones. Pairing each cell with its
own centroid,
sum_i ||z_i||^2 = sum_i <z_i, z_i>
= sum_i integral_{A_i} <z_i, x> dgamma_n(x)
= integral <z_{sigma(x)}, x> dgamma_n(x)
<= E max_i <z_i, g>
<= sqrt(C) (sum_i ||z_i||^2)^{1/2}
= C.
Both ends are C, so both inequalities are equalities. The nonnegative
difference max_j <z_j, x> - <z_{sigma(x)}, x> has zero integral, so
vanishes a.e. Score ties lie in finite hyperplanes <z_i - z_j, x> = 0,
all gamma_n-null. Hence cells agree a.e. with the closed cones K_i.
Step 3: Gram-matrix linear algebra. Let Q = (<z_i, z_j>). Its row sums
vanish. For any a in R^m,
a^T Q a = sum_{i<j} ( -<z_i, z_j> ) (a_i - a_j)^2.
Each weight -<z_i, z_j> is positive, so a^T Q a = 0 iff a is a
multiple of (1, ..., 1). Thus ker Q = span{(1, ..., 1)} and rank
Q = m-1. The only linear relation among the centroids is sum_i z_i = 0.
A dependence among a proper subset would have a zero coefficient
somewhere, but no multiple of (1, ..., 1) does. So every proper subset
is linearly independent. A relation sum_i c_i (z_i - z_{i_0}) = 0
gives a relation among all centroids whose coefficients sum to zero;
only the zero multiple satisfies that, so the z_i - z_{i_0} form a
basis of V.
Step 4: m >= 5. The cones K_i depend only on the projection to V. If
d = dim V, then by orthogonal Gaussian decomposition, K_i is the
product of (K_i cap V) with V^perp, and its centroid has norm equal
to that of K_i cap V. If m <= 4, then d <= 3. Identifying V with R^d
and extending by R^{3-d}, the 3-dimensional propeller theorem of
Heilman, Jagannath, and Naor gives C <= 9/(8 pi), contradicting the
assumption C > 9/(8 pi). Hence m >= 5.
Consequences. Work in V = R^{m-1}, with g standard Gaussian there.
Set
X_i = <z_i, g>,
P_i = gamma_{m-1}(K_i),
r_i = ||z_i|| / sqrt(C).
Then P_i > 0, r_i > 0, sum_i P_i = sum_i r_i^2 = 1, and E max_i X_i
= C. Because sum_i X_i = 0, the winning score is always nonnegative,
so K_i is contained in {X_i >= 0}. Therefore
P_i <= 1/2 for every i.
Keep the extremizer and notation of the extremizer above: C > B^2, m >= 5.
Write phi(x) = (1/sqrt(2 pi)) e^{-x^2/2} and
Phi(x) = integral_{-infinity}^x phi(u) du. Recall P_i > 0, 0 < r_i
<= 1, sum_i P_i = sum_i r_i^2 = 1, and P_i <= 1/2.
LEMMA 4.1 (Cell probability bounds). Let A = .929 if m = 5 and
A = .884 if m >= 6. For every active cell i,
r_i <= 2/3,
P_i >= A r_i^2,
P_i >= .415 r_i + .15 r_i^2.
Every terminating decimal below denotes an exact rational. The
required numerical comparisons are certified in the appendix.
The proof has three parts. First, halfspace rearrangement gives the
first two inequalities with A = .884. When m = 5, spherical
rearrangement improves the constant to A = .929. Second, removing one
score from the maximum and applying Ehrhard's inequality produces a
nonlinear constraint connecting each P_i to r_i. Third, a finite
interval check with explicit rational bounds extracts the linear-
plus-quadratic lower bound on P_i.
Fix a cell and temporarily suppress its index. Let e = z/|z| be the
unit direction of its centroid, let x = Phi^{-1}(1 - P), and let
H = {g : <e, g> >= x} be the upper halfspace in direction e with the
same Gaussian measure P.
Halfspace rearrangement. Among all measurable subsets of R^{m-1} of
Gaussian measure P, an upper halfspace maximizes the first moment in
direction e:
<e, integral_A g dgamma_{m-1}(g)>
<= <e, integral_H g dgamma_{m-1}(g)> = phi(x).
(The final evaluation is a one-dimensional Gaussian computation:
<e, g> is standard normal and E[(<e, g>)_+ ; <e, g> >= x] = phi(x).)
Applying this to A = K, and using z = integral_K g dgamma_{m-1}(g),
gives
|z| - int_H <e, g> dgamma_{m-1}(g)
= int (<e, g> - x) (1_K - 1_H) dgamma_{m-1}(g) <= 0.
Small radius. Because phi attains its maximum at 0,
phi(x) <= phi(0) = 1/sqrt(2 pi). Recall B = (3/2) phi(0). Since
sqrt(C) > B,
r = |z|/sqrt(C) <= phi(x)/sqrt(C) <= phi(0)/B = 2/3.
Halfspace ratio. Combining |z| <= phi(x) and sqrt(C) > B,
P/r^2 = P C / |z|^2
> P B^2 / phi(x)^2
= (9/(8 pi)) P / phi(x)^2
= (9/4) e^{x^2} Phi(-x).
The right side is a function of x alone. The function
f(x) = (9/4) e^{x^2} Phi(-x)
has a single global minimum. Indeed, d/dx log f(x) = 2x - phi(x)/Phi(-x),
and phi(x)/Phi(-x) has derivative 1 - Var(Z | Z > -x) < 1 for standard
normal Z, so the derivative of log f is strictly increasing. Its signs
at x = .6119 and x = .6121 are opposite, and the certified enclosures
in the appendix give
min_{x in R} f(x) > .8843837 > .884.
Consequently, P/r^2 > .884 for every active cell. The first two
inequalities of Lemma 4.1 follow with A = .884.
When m = 5, V has dimension 4 and a spherical rearrangement improves
the constant to .929.
Write g = R U with R >= 0 in S^3 uniform and independent of R. Then
E R = 3 sqrt(2 pi)/4, and for a fixed unit vector e, the coordinate
<e, U> has density (2/pi) sqrt(1 - u^2) on [-1, 1].
Spherical rearrangement. Among all subsets of S^3 of fixed spherical
measure, an upper cap {U : <e, U> >= x} maximizes <e, integral_A U>.
Write the cap threshold as x in [0, 1). Its cap probability is
p(x) = 1/2 - ( arcsin x + x sqrt(1 - x^2) ) / pi,
and its Gaussian first moment in direction e is
E R * (2/pi) integral_x^1 u sqrt(1 - u^2) du
= phi(0) (1 - x^2)^{3/2}.
So P/r^2 > R(x), where
R(x) = (9/4) p(x) / (1 - x^2)^3.
The function R has a unique global minimizer. Define
F(x) = 6 x p(x) - (2/pi) (1 - x^2)^{3/2},
H(x) = p(x) - (x/pi) sqrt(1 - x^2).
Direct differentiation yields
R'(x) = (9/4) F(x) / (1 - x^2)^4,
F'(x) = 6 H(x),
H'(x) = (4 x^2 - 3) / (pi sqrt(1 - x^2)).
So H decreases on [0, sqrt(3)/2), increases on (sqrt(3)/2, 1], and has
H(0) = 1/2, H(1) = 0. Hence H has exactly one zero in (0, 1). F
increases then decreases to F(1) = 0. The certified values
F(.29) < 0 < F(.294) show that F has one interior zero, in
(.29, .294), and this zero is the unique minimizer of R. The certified
bounds
R(.29) > .9312526,
|R'(x)| < .03 on (.29, .294),
give min R > .9312526 - .03(.004) = .9311326 > .929. Consequently,
when m = 5, P/r^2 > .929. This completes the quadratic bound of
Lemma 4.1 in both cases.
The rearrangement bounds above used the shape of a single winning
cone. The linear-plus-quadratic bound in Lemma 4.1 comes instead from
the behaviour of the expected maximum when one score is removed.
Fix a cell i and put alpha = m/(m-1) and X_j = <z_j, g>.
Recentering. Remove z_i and recenter the remaining scores on the
mean of z_j for j != i. The new score vectors are
z_j + z_i/(m-1), j != i. Using sum_j z_j = 0 and sum_j ||z_j||^2 = C,
sum_{j != i} || z_j + z_i/(m-1) ||^2 = C - alpha |z_i|^2.
The left side is a sum of squared norms, so alpha r_i^2 <= 1. In
particular the square root below is real. The shorter-list inequality
(Lemma 3.1) and E max_j X_j = C give
E ( X_i - max_{j != i} X_j )_+
>= C ( 1 - (1 - alpha r_i^2)^{1/2} ). (4.1)
The translated cone. By Lemma 3.2 the m-1 vectors z_i - z_j, j != i,
form a basis of V. There is therefore a vector h in V satisfying
<h, z_i - z_j> = 1 for every j != i.
Summing over the m-1 values of j gives <h, z_i> = 1/alpha. For u >= 0
define
p_i(u) = Pr{ X_i >= X_j + u for all j != i }
= gamma_{m-1}(K_i + u h).
Differentiation in u at zero and Gaussian integration by parts yield
p_i'(0) = - integral_{K_i} <h, x> dgamma_{m-1}(x)
= -<h, z_i> = -1/alpha.
Ehrhard concavity. Ehrhard's inequality states that for the standard
Gaussian measure in any dimension, Phi^{-1} o gamma is concave on
Minkowski interpolation of convex sets. The winning cone K_i is closed
and convex, has nonempty interior, and is a proper subset of V.
Minkowski interpolation of its translates is the translate with
interpolated displacement. Therefore u -> Phi^{-1}(p_i(u)) is concave
on [0, infinity).
Write q = Phi^{-1}(P_i). The derivative at u = 0 is -1/(alpha phi(q)).
Concavity gives the tangent-line bound
p_i(u) <= Phi( q - u / (alpha phi(q)) ) for u >= 0.
Integrating. Since E loss = integral_0^infty p_i(u) du and
(q Phi(q) + phi(q))' = Phi(q),
E ( X_i - max_{j != i} X_j )_+
= integral_0^infty p_i(u) du
<= alpha phi(q) ( q Phi(q) + phi(q) ).
Ratio constraint. Combine with (4.1), multiply by
1 + (1 - alpha r_i^2)^{1/2}, and use (1-x)(1+x) = 1-x^2:
C r_i^2
<= phi(q)( q Phi(q) + phi(q) )( 1 + (1 - alpha r_i^2)^{1/2} ).
Dividing by Phi(q)^2 = P_i^2 and using C > B^2, alpha > 1,
P_i^2 G(Phi^{-1}(P_i)) >= B^2 r_i^2 / ( 1 + (1 - r_i^2)^{1/2} ),
where
G(q) = phi(q)( q Phi(q) + phi(q) ) / Phi(q)^2.
LEMMA 4.2. The function G is nonincreasing in q, satisfies
0 < G(q) < 1, and P -> P^2 G(Phi^{-1}(P)) is increasing on (0, 1/2].
Proof. Put lambda = phi(q)/Phi(q). Conditioning Z <= q,
E(Z | Z <= q) = -lambda,
V(q) := Var(Z | Z <= q) = 1 - q lambda - lambda^2,
so G = 1 - V = lambda(q + lambda). The distance U = q - Z given
Z <= q has positive mean q + lambda and positive variance, so
0 < G < 1.
The survival function S(u) = Phi(q - u)/Phi(q) satisfies
(log S)''(u) = (log Phi)''(q - u), which is strictly negative for every
u, so log S is
concave. Concavity of log S gives the submultiplicative inequality
S(u+v) <= S(u) S(v). Integrating over u, v >= 0,
(1/2) E U^2 <= (E U)^2.
Hence V <= (q + lambda)^2, so V'(q) = lambda((q + lambda)^2 - V(q)) >= 0.
Therefore G is nonincreasing. For q <= 0 both positive factors of
phi(q)(q Phi(q) + phi(q)) are increasing, so P^2 G(Phi^{-1}(P)) is
increasing in P on (0, 1/2].
Now set P_0(r) = (.415 + .15 r) r for r in (0, 2/3], so P_0(2/3) =
103/300 < 1/2. The goal is to prove
(.415 + .15 r)^2 G(Phi^{-1}(P_0(r))) < B^2 / (1 + (1 - r^2)^{1/2}).
By Lemma 4.2, this implies P_i > P_0(r_i), stronger than the
linear-plus-quadratic bound. The finite verification is in the table
below. Each row (a, b, U) gives U > G(Phi^{-1}(P_0(r))) on [a, b] and a
positive lower bound for
Delta(a, b, U) = B^2 / (1 + (1 - a^2)^{1/2}) - U(.415 + .15 b)^2.
The factor (0.415 + 0.15 r)^2 and the right side of (4.2) are both
increasing in r, so endpoint inequalities cover the whole interval.
a b U Delta * 10^6 >
0 .05 1.0 542
.05 .14 .91 6173
.14 .24 .87 2976
.24 .33 .836 1328
.33 .41 .809 523
.41 .48 .788 392
.48 .54 .771 1076
.54 .59 .756 2787
.59 .64 .743 4115
.64 2/3 .73 8886
All values are positive. This proves the linear-plus-quadratic bound
and completes Lemma 4.1.
The scalar estimates give one probability bound per cell. To get
constraints among the radii, use the cell with the smallest centroid.
Label the cells so that
r_1 >= r_2 >= ... >= r_m = t > 0,
L = r_1^2 + r_2^2,
c = r_3^2.
(The three largest radii have distinct indices, even when equal as
numbers.) The first-moment identity for cell m controls the joint
distribution of any two competing scores.
Setup. Let g be standard Gaussian in V = R^{m-1}. Put
e = z_m / |z_m|, T = <e, g>,
a_j = - <z_m, z_j> / |z_m|^2 (1 <= j < m).
Pairwise negativity and sum_j z_j = 0 give
a_j > 0 and sum_{j < m} a_j = 1. (5.1)
Define residual vectors and scores
w_j = z_j / sqrt(C) + a_j t e, Y_j = <w_j, g>.
Each w_j is orthogonal to e, so Y = (Y_j)_{j < m} is a centered
Gaussian vector independent of T. The decomposition
<z_j, g> / sqrt(C) = -a_j t T + Y_j (5.2)
follows from <a_j t e, g> = a_j t T. The covariance matrix H of Y has
entries
H_{jk} = <z_j, z_k>/C - a_j a_k t^2,
h_j := H_{jj} = r_j^2 - a_j^2 t^2. (5.3)
Since sum_{j<m} w_j = 0, every row of H sums to zero. Also H_{jk} < 0
for j != k, which forces h_j > 0.
For distinct j, k < m, put D_{jk} = (h_j h_k - H_{jk}^2)^{1/2}. These
are strictly positive: a linear dependence between w_j and w_k would
give a dependence among z_j, z_k, z_m, contradicting Lemma 3.2.
LEMMA 5.1 (Two competing scores). For every pair of distinct indices
j, k < m,
D_{jk} <= (3/pi) t (1 + a_j) (1 + a_k). (5.4)
Proof. Let K = K_m be the winning cone for the score <z_m, g>. By
Lemma 3.2 it agrees a.e. with the optimal cell, so
integral_K g dgamma_{m-1}(g) = z_m.
Two centroid identities. Since T = <e, g>,
E[ 1_K T ] = <e, z_m> = |z_m| = sqrt(C) t > B t.
And since w_j is orthogonal to e and chosen with <w_j, z_m> = 0,
E[ 1_K Y_j ] = <w_j, z_m> = 0.
Pointwise constraints on K. On K the score <z_m, g> = sqrt(C) t T is
largest. The maximum of all scores is always nonnegative (their sum is
zero), so T >= 0 on K. And for j != m, <z_j, g> <= <z_m, g>; by (5.2)
this reads Y_j <= (1 + a_j) t T.
Fix distinct j, k < m. Define U = Y_j / ((1 + a_j) t) and
V = Y_k / ((1 + a_k) t). The pair (U, V) is a centered Gaussian
independent of T. Its covariance determinant is
D_{jk}^2 / ((1 + a_j)^2 (1 + a_k)^2 t^4),
so the joint density is bounded everywhere by
M = (1 + a_j)(1 + a_k) t^2 / (2 pi D_{jk}).
Positive part. Adding the two zero expectations
E[1_K Y_j] = E[1_K Y_k] = 0 gives E[1_K (T + U + V)] = E[1_K T]. On K
the bounds T >= 0, U <= T, V <= T hold, and (T + U + V) <=
(T + U + V)_+. Therefore
E[ 1_K T ]
<= E[ 1_{T >= 0, U <= T, V <= T} (T + U + V)_+ ].
Inner triangle integral. Condition on T = s >= 0. The inner integral
over (U, V) is at most M times the unweighted integral
integral_{u <= s, v <= s} (s + u + v)_+ du dv.
Substitute a = s - u, b = s - v. Then s + u + v = 3s - a - b on a, b
>= 0, so the integral becomes
integral_{a, b >= 0} (3s - a - b)_+ da db
= integral_0^{3s} r (3s - r) dr
= (3s)^3 / 6.
Averaging over T and using E[T_+^3] = 2 / sqrt(2 pi),
E[ 1_K T ]
<= M * (27/6) * E[T_+^3]
= 9 t^2 (1 + a_j)(1 + a_k) / (2 pi sqrt(2 pi) D_{jk}).
Combine with B t < E[1_K T] and divide:
D_{jk} < 9 t (1 + a_j)(1 + a_k) / (2 pi sqrt(2 pi) B)
= (3/pi) t (1 + a_j)(1 + a_k),
using 2 pi sqrt(2 pi) B = 3 pi. This proves (5.4).
COROLLARY 5.2 (Constraints on the three largest radii). The quantities
L, c, t satisfy
(c - t^2)(L - c - 2 t^2) <= 8 (3/pi)^2 t^2, (5.5)
(3/2)(c - t^2)^2 <= 10 (3/pi)^2 t^2. (5.6)
Proof of (5.5). The matrix H has strictly negative off-diagonal
entries and vanishing row sums. For the first three indices,
|H_{31}| + |H_{32}| = -H_{31} - H_{32} = H_{33} = h_3,
so H_{31}^2 + H_{32}^2 <= h_3^2. Hence
D_{31}^2 + D_{32}^2
= h_3(h_1 + h_2) - (H_{31}^2 + H_{32}^2)
>= h_3 ( h_1 + h_2 - h_3 ). (5.7)
From (5.3) and 0 < a_j <= 1,
h_3 = r_3^2 - a_3^2 t^2 >= c - t^2,
h_1 + h_2 - h_3
= (L - c) - (a_1^2 + a_2^2 - a_3^2) t^2
>= L - c - 2 t^2.
If L - c - 2 t^2 >= 0, then (5.7) gives
D_{31}^2 + D_{32}^2 >= (c - t^2)(L - c - 2 t^2); if L - c - 2 t^2 < 0,
then the right side of (5.5) is positive but the left side is
nonpositive, so (5.5) is trivial.
For the upper bound, apply Lemma 5.1 to (3,1) and (3,2):
D_{31}^2 + D_{32}^2
<= (3/pi)^2 t^2 (1 + a_3)^2 ( (1+a_1)^2 + (1+a_2)^2 ).
Using a_1 + a_2 <= 1 - a_3 and convexity,
(1+a_1)^2 + (1+a_2)^2 <= (2 - a_3)^2 + 1.
For 0 <= x <= 1, 8 - (1+x)^2((2-x)^2+1) = (1-x)^2(3-x^2) >= 0, so
D_{31}^2 + D_{32}^2 <= 8 (3/pi)^2 t^2. Combining with the lower bound
gives (5.5).
Proof of (5.6). Put rho_{jk} = H_{jk}/sqrt(h_j h_k), so each rho_{jk}
lies in [-1, 0]. The variance identity
Var(Y_1/sqrt(h_1) + Y_2/sqrt(h_2) + Y_3/sqrt(h_3))
= 3 + 2 sum rho_{jk} >= 0 gives sum_{j<k} |rho_{jk}| <= 3/2, so
sum_{j<k} rho_{jk}^2 <= 3/2.
Since h_j >= c - t^2 for j <= 3, and D_{jk}^2 = h_j h_k (1 - rho_{jk}^2),
sum_{j<k<=3} D_{jk}^2
>= (c - t^2)^2 ( 3 - sum_{j<k} rho_{jk}^2 )
>= (3/2)(c - t^2)^2. (5.8)
For the upper bound, square Lemma 5.1 and sum over the three pairs.
Write s_1 = a_1 + a_2 + a_3, s_2 = a_1 a_2 + a_1 a_3 + a_2 a_3, and
s_3 = a_1 a_2 a_3. Expanding,
sum_{j<k<=3} (1+a_j)^2 (1+a_k)^2
= 3 + 4 s_1 + 2 s_1^2 + 2 s_1 s_2 + s_2^2 - (6 + 2 s_1) s_3.
Because a_j > 0 and a_1 + a_2 + a_3 <= 1, 0 <= s_1 <= 1,
0 <= s_2 <= 1/3, s_3 >= 0. So the sum is at most
3 + 4 + 2 + 2/3 + 1/9 = 88/9 < 10, giving
sum_{j<k<=3} D_{jk}^2 <= 10 (3/pi)^2 t^2. Combined with (5.8), this
proves (5.6).
Now combine the scalar constraints (probability vs radius) with the
geometric constraint (5.6) to rule out C > 9/(8 pi). Strategy:
(a) confine the smallest radius t; (b) bound the third-largest radius
from below proportionally to t; (c) contradict (5.6).
Throughout, radii are ordered as r_1 >= ... >= r_m = t > 0,
sum r_j^2 = 1, L = r_1^2 + r_2^2, c = r_3^2. Set
A = .929 if m = 5, A = .884 if m >= 6,
d = A - .15,
s = .415 / d,
e(u) = .415 u - d u^2.
The probability excesses
delta_j = P_j - A r_j^2
satisfy, by Lemma 4.1,
delta_j >= max{ 0, e(r_j) }, sum_j delta_j = 1 - A. (6.1)
All decimals below are exact rationals; every finite comparison is
certified in the appendix.
A universal charge bound. For j >= 3, ordering gives r_j^2 <= c, so
e(r_j) = r_j^2 (.415/r_j - d) >= r_j^2 (.415/sqrt(c) - d).
Summing over j >= 3 in (6.1),
(1 - L)(.415/sqrt(c) - d) <= 1 - A.
When A = .929, add .045(1-L) to both sides and bound .045(1-L) by
.045; when A = .884, no adjustment is needed. In both cases,
(1 - L)(.415/sqrt(c) - .734) <= .116. (6.2)
Since r_j <= 2/3 (Lemma 4.1), L <= 8/9, hence 1 - L >= 1/9. If
sqrt(c) <= .23, the left side of (6.2) is at least
(1/9)(.415/.23 - .734) = .116 + 101/34500 > .116,
contradicting (6.2). So
sqrt(c) > .23. (6.3)
The small minimum. Suppose t <= q_0 := .066.
Case 1: sqrt(c) >= .44. Then r_1, r_2 >= r_3 = sqrt(c), so
L = r_1^2 + r_2^2 >= 2c, hence L - c - 2 t^2 >= c - 2 t^2. Both
factors of (5.5) are bounded below:
c - t^2 >= .44^2 - q_0^2,
c - 2 t^2 >= .44^2 - 2 q_0^2.
Therefore the left side of (5.5) exceeds 8(3/pi)^2 q_0^2 by at least
.00321132, contradicting (5.5) at t = q_0.
Case 2: .23 < sqrt(c) < .44. Split into four subintervals; on each
[a, b], the factor .415/sqrt(c) - .734 is positive and at least
.415/b - .734, so (6.2) gives
L - c - 2 t^2 >= 1 - .116/(.415/b - .734) - b^2 - 2 q_0^2 =: M(b).
The last column of the small-minimum table below gives
(a^2 - q_0^2) M(b) > 8 (3/pi)^2 q_0^2, so (5.5) fails on [a, b].
the small-minimum table (small minimum, sqrt(c) < .44):
[a, b] M(b) (a^2 - q_0^2) M(b) - 8(3/pi)^2 q_0^2 >
[.23, .30] .72264 .00330237
[.30, .35] .61198 .02063552
[.35, .41] .40621 .01621418
[.41, .44] .24314 .00803616
Both cases are impossible. Therefore
t > .066. (6.4)
The bound r_j <= .42 for every j >= 4 follows by contradiction. Suppose r_4 > .42, put
K = d .42/(s + .42). For every u >= .42,
max{0, e(u)} >= K(s^2 - u^2). (6.5)
Indeed, if .42 <= u <= s, then e(u) = (d u/(s+u))(s^2 - u^2) and
u/(s+u) >= .42/(s+.42). If u > s, the right side is negative and the
left side is nonnegative.
Apply (6.5) to j = 1, 2, 3, 4:
sum_{j=1}^4 delta_j >= K (4 s^2 - sum_{j=1}^4 r_j^2)
>= K (4 s^2 - 1 + (m-4) t^2).
For j >= 5, ordering and normalization give r_j <= 1/sqrt(5). By
(6.4) the radii r_j for j >= 5 lie in [.066, 1/sqrt(5)]. Concavity of
e therefore gives delta_j >= min{e(.066), e(1/sqrt(5))} = e(.066), where
the four-radii table (below) shows e(.066) is the smaller value. So
1 - A >= K(4 s^2 - 1 + (m-4)(.066)^2) + (m-4) e(.066). (6.6)
The right side increases with m (increment K(.066)^2 + e(.066) > 0);
evaluation at the smallest permitted m already pushes the right side above
1 - A. This contradicts (6.6), proving
r_4 <= .42.
the four-radii table (four radii > .42):
A smallest m e(1/sqrt(5)) lower RHS of (6.6) minus (1-A) >
.929 5 .02979364 .00092980
.884 6 .03879364 .02229774
Put k = 2 when m = 5 and k = 3 when m >= 6. There are at least k
indices j >= 4, and their radii lie in [t, .42] by ordering and r_4 <= .42,
so each contributes at least min{e(t), e(.42)}. Moreover,
k e(.42) - (1 - A) = .0027688 if A = .929, .0184672 if A = .884.
Thus k e(.42) > 1 - A, so (6.1) forces k e(t) <= 1 - A. Let t_0 be the
smaller root of k e(u) = 1 - A:
t_0 = (.415 - sqrt(.415^2 - 4 d (1 - A)/k)) / (2d).
Because .42 lies strictly between the two roots of this concave
quadratic and t <= .42, t <= t_0. The enclosures
.1070554 < t_0 < .1070555 (A = .929),
.1176565 < t_0 < .1176566 (A = .884),
give t_0 < .12 in both cases.
Claim: c > 2.6 t. Suppose not. By (6.3), the third radius is in
[.23, sqrt(2.6t)]. The third index is distinct from the k selected
indices, so concavity of e and (6.1) give
1 - A >= min{ e(.23), e(sqrt(2.6 t)) } + k e(t). (6.8)
First endpoint. Because e increases up to t_0 (t_0 < s), for
t >= .066, e(.23) + k e(t) - (1-A) >= e(.23) + k e(.066) - (1-A),
which is positive by the endpoint-margin table.
Second endpoint. Define F(t) = e(sqrt(2.6 t)) + k e(t)
= .415 sqrt(2.6 t) - 2.6 d t + k(.415 t - d t^2). Its second derivative
F''(t) = -.415 sqrt(2.6)/(4 t^{3/2}) - 2 k d is negative for t > 0, so
F is strictly concave, and its minimum on [.066, t_0] is at an
endpoint. The endpoint-margin values give F(.066) > 1 - A and 2.6 t_0 < s^2. The
latter gives e(sqrt(2.6 t_0)) > 0 (since sqrt(2.6 t_0) < s and e > 0 on
(0, s)), while k e(t_0) = 1 - A, so F(t_0) > 1 - A. Hence
F > 1 - A on [.066, t_0], contradicting (6.8) and proving c > 2.6 t.
the endpoint-margin table (endpoint margins):
A e(.23)+k e(.066)-(1-A) F(.066)-(1-A) s^2 - 2.6 t_0 >
.929 .031234252 .01522916 .00546157
.884 .013199488 .00253590 .01376450
Final contradiction. From c > 2.6 t, t < .12, and (5.6),
10 (3/pi)^2 t^2 >= (3/2)(c - t^2)^2 > (3/2)(2.6 - .12)^2 t^2.
But (3/2)(2.6-.12)^2 - 10(3/pi)^2 > .10667806 > 0, which is false.
This contradiction rules out C > 9/(8 pi) and completes the proof of
the upper bound in Theorem 1.1.
The partition bound also gives a sharp inequality for Gaussian maxima.
The four-score version appears in Heilman, Jagannath, and Naor; the
general Gaussian partition duality is due to Khot and Naor.
COROLLARY 7.1 (Gaussian maxima). Let d and k be positive integers, let
g be standard Gaussian in R^d, and let v_1, ..., v_k be vectors in R^d
with mean bar v = (1/k) sum_{i=1}^k v_i. Then
E max_{1 <= i <= k} <v_i, g>
<= (3/(2 sqrt(2 pi))) ( sum_{i=1}^k ||v_i - bar v||^2 )^{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 <bar v, g>
leaves the maximum unchanged. Partition R^d by the largest score
<u_i, x>, with ties resolved by the smallest index. Let z_i be the
Gaussian first moments of the resulting cells. Then by Theorem 1.1 and
Cauchy-Schwarz,
E max_i <v_i, g>
= E max_i <u_i, g>
= sum_i <u_i, z_i>
<= (sum_i ||u_i||^2)^{1/2} (sum_i ||z_i||^2)^{1/2}
<= (3/(2 sqrt(2 pi))) (sum_i ||u_i||^2)^{1/2}.
Sharpness. Take the three centroid vectors of the planar propeller from
the construction above as v_1, v_2, v_3. Their sum is zero, their winning score
cells are the propeller sectors, and both Cauchy-Schwarz inequalities
become equalities.
Jointly Gaussian vectors. Any finite centered jointly Gaussian vector
(X_1, ..., X_k) can be written as (<v_i, g>) for suitable vectors in
some Euclidean space, even when the covariance matrix is singular. So
the corollary also bounds
E max_i X_i
<= (3/(2 sqrt(2 pi))) ( sum_i Var(X_i - bar X) )^{1/2},
where bar X = (1/k) sum_i X_i.
The Gaussian bound also has a consequence in approximation algorithms.
It is included for completeness, adapting Khot and Naor's reduction. No
complexity argument enters the proof of Theorem 1.1. The kernel-clustering
consequence stands apart as a downstream application.
Fix an integer k >= 3. An input is an explicitly represented rational
symmetric matrix A = (a_pq)_{p,q=1}^N satisfying A positive semidefinite
and A 1 = 0 (every row sum is zero).
For a map sigma: [N] -> [k], define
val_A(sigma) = sum_{p,q=1}^N a_pq 1_{sigma(p) = sigma(q)},
Clust(A | I_k) = max_sigma val_A(sigma).
Equivalently, Clust(A | I_k) is the largest possible
sum_{i=1}^k 1_{S_i}^T A 1_{S_i} over cells S_1, ..., S_k, where 1_{S_i}
is the indicator of S_i. Empty cells are allowed and every value is
nonnegative.
A DETERMINISTIC APPROXIMATION with loss factor alpha >= 1 returns an
assignment sigma with val_A(sigma) >= Clust(A | I_k)/alpha. An
expected approximation has the same inequality in expectation.
Constants:
c_* = 9/(8 pi),
alpha_k = (1 - 1/k)/c_* = (8 pi/9)(1 - 1/k).
The matching rounding guarantee. Khot and Naor's approximation theorem
gives the expected rounding bound
E val_A(sigma) >= Clust(A | I_k)/alpha_k
on the inputs above, using an optimal semidefinite relaxation and ideal
Gaussian sampling. This is quoted separately from the hardness statement.
THEOREM 8.1 (Kernel-clustering hardness under the Unique Games
Conjecture). Assume the Unique Games Conjecture of Khot. For each fixed
k >= 3 and every fixed 1 <= alpha < alpha_k, it is NP-hard, given a
rational symmetric matrix A positive semidefinite with A 1 = 0 and the
identity-target objective above, to find sigma: [N] -> [k] with
val_A(sigma) >= Clust(A | I_k)/alpha.
In particular, such a deterministic polynomial-time approximation would
refute the Unique Games Conjecture.
The proof below concerns strict improvement over alpha_k; hardness at
the exact endpoint alpha = alpha_k is not asserted.
Gaussian parameter. Khot and Naor's reduction routes the Gaussian
partition parameter into the threshold:
C_k = sup over partitions B_1, ..., B_k of R^{k-1} of
sum_{i=1}^k || integral_{B_i} x dgamma_{k-1}(x) ||^2.
Because k >= 3, Theorem 1.1 and the attaining example give
C_k = c_*. (8.1)
The first external theorem. Let Omega = [k] with uniform probability,
and choose a real orthonormal basis b_0, ..., b_{k-1} of functions on
Omega, with b_0 = 1. For r in N and nu in {0, ..., k-1}^r, write
b_nu(x) = prod_{j=1}^r b_{nu_j}(x_j),
|nu| = |{ j : nu_j != 0 }|,
so every h: Omega^r -> R has expansion h = sum_nu h_hat(nu) b_nu. For
real D >= 0 define the truncated influence
Inf_j^{<= D}(h) = sum over |nu| <= D with nu_j != 0 of h_hat(nu)^2.
Let P_1 be the orthogonal projection onto the span of b_nu with
|nu| = 1, and put OBJ(f) = sum_{i=1}^k || P_1 f_i ||_2^2 for
f = (f_1, ..., f_k). All norms are over the uniform measure. Define
Delta_k = { u in R^k : u_i >= 0, sum_{i=1}^k u_i <= 1 }.
THEOREM 8.2 (Khot-Naor low influence). For fixed k and every eta > 0,
there exists 0 < tau_0 < 1/2, independent of r, such that every
f: Omega^r -> Delta_k satisfying
Inf_j^{<= log(1/tau_0)}(f_i) <= tau_0 (all i in [k], j in [r])
obeys OBJ(f) <= C_k + eta.
This is Khot and Naor's low-influence bound. Its proof uses the
invariance principle of Mossel, O'Donnell, and Oleszkiewicz. Choose a
rational 0 < tau < min{tau_0, 1/2} and set
D = max{ 1, ceil( log(1/tau) ) }. (8.2)
Monotonicity of Inf_j^{<= D} in the cutoff gives the contrapositive: if
OBJ(f) > C_k + eta, then Inf_j^{<= D}(f_i) > tau for some i in [k],
j in [r].
Noise stability of functions with low influences Mossel+O'Donnell+Oleszkiewicz 2010: ./mossel-odonnell-oleszkiewicz-2010.pdf
> Functions f: Omega_1 x ... Omega_n -> R with low influences
> (averaged variances E[Var_{Omega_i}[f]] small compared to Var[f]
> for each coordinate i) have noise stability matching their Gaussian
> counterparts, by an invariance principle.
The second external input is the Unique Games Conjecture of Khot, in
the following standard form.
The Unique Games Conjecture. For every fixed eps, delta in
(0, 1/2), there are an integer s >= 1 and a deterministic
polynomial-time reduction from 3SAT to explicit unweighted simple
bipartite Unique Games instances over F_2^s. If the formula is
satisfiable the game has a labeling satisfying at least 1 - eps of its
edges; if 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 eps, delta.
Only ordinary satisfied-edge fractions are asserted.
Let G = (V, W, E) be a game as furnished by the Unique Games Conjecture,
with alphabet
enumerated as [r] for r = 2^s. Reorient each constraint so that the
permutation pi_vw satisfies the constraint when l(v) = pi_vw(l(w)).
Delete isolated vertices, put M = |E|, d_v = |N(v)|, and
mu(v) = d_v/M. Choosing v by mu(v) then a uniform w in N(v) draws a
uniform edge.
Permutation convention. For a permutation pi of [r],
(R_pi x)_a = x_{pi(a)} for a in [r]. For a scalar table
h: W x Omega^r -> R, define
(T_v h)(x) = (1/d_v) sum_{w in N(v)} h(w, R_{pi_vw} x),
Q(h) = sum_{v in V} mu(v) ||P_1 T_v h||_2^2.
LEMMA 8.4 (Rational centered PSD matrix). For fixed k and r, one can
construct in deterministic polynomial time a rational symmetric matrix
A, indexed by W x Omega^r, such that
h^T A h = Q(h), A positive semidefinite, A 1 = 0.
Moreover, for every sigma: W x Omega^r -> [k], if
F_i(w, x) = 1_{sigma(w,x) = i}, then
val_A(sigma) = sum_{v in V} mu(v) OBJ(F_v),
F_v = (T_v F_1, ..., T_v F_k): Omega^r -> Delta_k,
and every output assignment value lies in [0, 1].
Proof. Put q = k^r. In counting coordinates (h(x))_{x in Omega^r},
(P_1)_{x,y} = (1/q) sum_{j=1}^r ( k 1_{x_j = y_j} - 1 ).
Indeed, the centered subspaces for distinct coordinates are mutually
orthogonal, so (P_1 h)(x) = sum_{j=1}^r ( E[h(X)|X_j = x_j] - E h(X) ).
The matrix is rational, symmetric, and idempotent, (P_1)^2 = P_1.
The matrix of T_v in counting coordinates is
(T_v)_{x, (w,y)} = (1/d_v) 1_{w in N(v)} 1_{y = R_{pi_vw} x}.
Define
A = (1/q) sum_{v in V} mu(v) T_v^T P_1 T_v. (8.3)
There are two q-factors because P_1 has a 1/q prefactor and the L_2
norm uses probability measure. Symmetry and P_1^2 = P_1 give
h^T A h = sum_v mu(v)(1/q)||P_1 T_v h||_{l_2}^2 = Q(h) >= 0. Also
T_v 1 = 1 and P_1 1 = 0, so A 1 = 0.
The matrix has N = |W| k^r indices, polynomial in the explicit game
size for fixed k and r, and its entries have denominators dividing
M d_v q^2 in rational arithmetic.
Objective identity. By definition val_A(sigma) = sum_i F_i^T A F_i.
Inserting (8.3),
val_A(sigma) = sum_v mu(v) OBJ(F_v).
Finally, every F_v(x) is an average of coordinate unit vectors, so
entries are nonnegative and sum to one, and
0 <= OBJ(F_v) <= sum_i ||F_{v,i}||_2^2
<= E sum_i F_{v,i} = 1.
Since sum_v mu(v) = 1, every output assignment value lies in [0, 1].
LEMMA 8.5 (Completeness). If a labeling of G satisfies at least
1 - eps of its edges, then the matrix of Lemma 8.4 satisfies
Clust(A | I_k) >= (1 - 1/k)(1 - eps)^2.
Proof. Use the witnessing labeling l to set sigma(w, x) = x_{l(w)}. For
j in [r], let D_j(x) = e_{x_j}, where e_1, ..., e_k are the coordinate
unit vectors in R^k. With p_{v,j} = Pr_{w in N(v)}{pi_vw(l(w)) = j},
the permutation convention gives F_v = sum_j p_{v,j} D_j.
For each i, the level-one part of the i-th component of D_j equals
1_{x_j = i} - 1/k. These parts for distinct j are orthogonal, and
sum_{i=1}^k E (1_{x_j=i} - 1/k)^2 = 1 - 1/k.
So
OBJ(F_v) = (1 - 1/k) sum_j p_{v,j}^2
>= (1 - 1/k) p_{v, l(v)}^2.
The weighted mean E_{v ~ mu} p_{v, l(v)} is the satisfied-edge fraction
of l, hence at least 1 - eps. By Jensen's inequality,
sum_v mu(v) OBJ(F_v)
>= (1 - 1/k) E_{v ~ mu} p_{v, l(v)}^2
>= (1 - 1/k)(1 - eps)^2.
Combined with the objective identity of Lemma 8.4, this proves the
lemma.
LEMMA 8.6 (Soundness). Fix eta > 0 with C_k + 2 eta < 1, and choose
tau, D as in (8.2). If every labeling of G satisfies at most delta of
its edges, where
0 < delta < eta tau^2 / (4 k D), (8.4)
then Clust(A | I_k) <= C_k + 2 eta.
Proof. Suppose an assignment sigma gives a larger value. Use the
functions F_1, ..., F_k from Lemma 8.4 and let
V_good = { v in V : OBJ(F_v) > C_k + eta }.
Let the mu-measure of V_good be beta. Every other v contributes at most
C_k + eta to the objective, and every v contributes at most 1, so
sum_v mu(v) OBJ(F_v) <= beta + (1 - beta)(C_k + eta)
<= C_k + eta + beta.
The assumed objective therefore forces beta > eta.
For every v in V_good, the contrapositive of Theorem 8.2 gives i_v in
[k] and j_v in [r] with Inf_{j_v}^{<= D}(F_{v, i_v}) > tau. Taking the
squared norm of the relevant Fourier coefficients inside the neighbor
average and applying convexity,
Inf_{j_v}^{<= D}(F_{v, i_v})
<= (1/d_v) sum_{w in N(v)} Inf_{pi_vw^{-1}(j_v)}^{<= D}(F_{i_v}(w, .)).
The inverse permutation arises from (R_pi x)_a = x_{pi(a)}. Every
influence on the right is in [0, 1] by Parseval and 0 <= F_i <= 1. An
average exceeding tau has more than a tau/2 fraction of its entries at
least tau/2.
Label-list size. For each w in W, let
L(w) = { a in [r] : Inf_a^{<= D}(F_i(w, .)) >= tau/2 for some i }.
For every scalar h, sum_{a=1}^r Inf_a^{<= D}(h) equals
sum_{|nu| <= D} |nu| h_hat(nu)^2, which is at most D ||h||_2^2.
Therefore
|L(w)| tau/2
<= sum_{i=1}^k sum_{a=1}^r Inf_a^{<= D}(F_i(w, .))
<= k D,
so |L(w)| <= 2 k D / tau.
Random decoding. Label a good left vertex v by j_v, and other left
vertices arbitrarily. Label each right vertex independently and uniformly
from L(w), or arbitrarily if L(w) is empty.
For a good v, more than a tau/2 fraction of its neighbors have
pi_vw^{-1}(j_v) in L(w). On each such edge the random label at w
satisfies the constraint with probability at least tau/(2kD). The
expected fraction of satisfied edges exceeds
eta * (tau/2) * (tau/(2 k D)) = eta tau^2 / (4 k D).
The weights mu(v) = d_v/M make this the uniform-edge fraction; some
deterministic labeling attains at least its expectation, contradicting
(8.4).
Proof of Theorem 8.1. Assume the Unique Games Conjecture. Fix k >= 3
and 1 <= alpha < alpha_k. Choose
rational eps, eta > 0 with eps < 1/2, c_* + 2 eta < 1, and
alpha < (1 - 1/k)(1 - eps)^2 / (c_* + 2 eta). (8.5)
Choose tau, D from Theorem 8.2 and (8.2), and a rational
0 < delta < min{1/2, eta tau^2 / (4kD)}. Invoke the Unique Games
Conjecture with these fixed errors; only then is r = 2^s determined, so
k^r is a constant in the input formula size.
Composing the reduction with Lemma 8.4 and using Lemmas 8.5-8.6,
phi satisfiable => Clust(A_phi | I_k) >= H := (1-1/k)(1-eps)^2,
phi unsatisfiable => Clust(A_phi | I_k) <= S := c_* + 2 eta.
The output is a rational symmetric centered PSD matrix of polynomial
dimension and bit length. By (8.5), S < H/alpha. Choose rational theta
with S < theta < H/alpha. A deterministic loss-factor-alpha algorithm
produces value > theta on satisfiable formulas and < theta on
unsatisfiable ones, deciding 3SAT in polynomial time. Hence the
approximation problem at loss factor alpha is NP-hard.
Remark on randomized guarantees. A polynomial-time randomized
algorithm with expected value at least Clust(A|I_k)/alpha for some
alpha < alpha_k would place 3SAT in RP: on the reduction instances its
returned value X lies in [0,1], and Pr{X > theta} >=
(H/alpha - theta)/(1 - theta) > 0 is a fixed positive constant while
X <= S < theta on unsatisfiable instances.
This appendix provides rational enclosures for every finite numerical
comparison. Every decimal is an exact rational.
Throughout,
3.14159 < pi < 3.14160. (A.1)
For example, these bounds follow from
pi = 16 arctan(1/5) - 4 arctan(1/239) by bounding the alternating
series of each arctangent through partial sums to indices 7 and 6.
Square roots. For any rational x >= 0 with rational l, u >= 0 and
l^2 <= x <= u^2, l <= sqrt(x) <= u. An explicit rule: set
D = 10^35, and use
floor(sqrt(floor(x D^2))) / D <= sqrt(x)
<= ( floor(sqrt(floor(x D^2))) + 1 ) / D.
For an interval of possible x, apply the lower rule to its lower
endpoint and the upper rule to its upper endpoint. Only rational
operations and integer square roots are required.
Exponential. For y >= 0 let E_N(y) = sum_{j=0}^N (-y)^j / j!. Taylor's
integral remainder gives
E_15(y) <= e^{-y} <= E_14(y). (A.2)
This does not require the initial terms to be decreasing.
Normal CDF. Integrating the same bounds and setting
J_N(x) = sum_{j=0}^N (-1)^j x^{2j+1} / ( 2^j j! (2j+1) ) for x >= 0,
(1/2) + J_15(x)/sqrt(2 pi)
<= Phi(x)
<= (1/2) + J_14(x)/sqrt(2 pi), (A.3)
Phi(-x) = 1 - Phi(x).
Together with (A.1) and the square-root rule, these give rational
enclosures for both phi and Phi everywhere below. Interval addition,
subtraction, multiplication, and division by intervals avoiding zero
preserve the enclosures.
Arcsine. Put Q(x) = sum_{j=0}^4 binom(2j,j)/(4^j (2j+1)) x^{2j+1}. The
binomial series has positive coefficients of size at most 1; its tail
from degree 10 is bounded by x^{10}/(1 - x^2), and integrating gives,
for 0 <= x < 1,
Q(x) <= arcsin x <= Q(x) + x^{11} / (11 (1 - x^2)). (A.4)
Halfspace case. With f(x) = (9/4) e^{x^2} Phi(-x) and
D_f(x) = 2x - phi(x)/Phi(-x) = (log f)'(x), substituting (A.2)-(A.3)
gives the strict enclosures
-.000131 < D_f(.6119) < -.000126,
.000120 < D_f(.6121) < .000124,
-.000430 < D_f(x) < .000424 for .6119 <= x <= .6121,
.884383832 < f(.612).
Interval arithmetic on the whole rational interval [.6119, .6121]
gives |D_f| < .001 there. Since D_f is strictly increasing, f has a
unique minimizer within .0001 of .612. Therefore
min f >= f(.612) e^{-10^{-7}} > .884383832 (1 - 10^{-7})
> .8843837 > .884.
Cone case. For p, F, H, R as in the spherical rearrangement,
-.0047010 < F(.29) < -.0046981,
.0007683 < F(.294) < .0007712,
.9312526 < R(.29),
.22198 < p(.294) - .294/pi.
For .29 <= x <= .294, H(x) = p(x) - x sqrt(1-x^2)/pi is at least
p(.294) - .294/pi, which is positive, so H > 0 throughout. Hence F is
increasing, and the first two lines give |F(x)| < .004702 on the whole
interval. Since R'(x) = (9/4) F(x)/(1-x^2)^4,
|R'(x)| < (9/4)(.004702) / (1 - .294^2)^4 < .015189 < .03.
The minimizer of R lies in [.29, .294], so
min R > .9312526 - .03(.004) = .9311326 > .929.
For P_0(a) = (.415 + .15 a) a, Table A.1 gives a rational q_a with
Phi(q_a) < P_0(a) and a strict upper bound on G(q_a). Each entry
follows by substituting the displayed rational into (A.2)-(A.3) and
the definition of G. Since G is nonincreasing (Lemma 4.2),
G(Phi^{-1}(P_0(r))) <= G(q_a) for r >= a. In each row the upper bound
is strictly below the value of U used in the interval verification.
Table A.1 (quantile enclosures).
a q_a 10^6 (P_0(a) - Phi(q_a)) > G(q_a) <
.05 -2.033 98 .887728
.14 -1.548 228 .854397
.24 -1.238 381 .826606
.33 -1.024 366 .803691
.41 -0.860 470 .783737
.48 -0.728 452 .766006
.54 -0.621 539 .750456
.59 -0.535 739 .737150
.64 -0.450 684 .723262
The verification table is justified as follows. For
each row (a, b, U), replace pi by its upper bound (A.1) in
B^2 = 9/(8 pi), enclose sqrt(1 - a^2) from above, and subtract the exact
rational U(.415 + .15 b)^2. The result is the value in the last column.
All entries are positive.
The same rational and square-root rules also justify the finite
comparisons in the small-minimum table, the four-radii table, the endpoint-margin table and the t_0
enclosures in the elimination argument. Every inequality is strict and rational;
no floating-point evaluation is needed.