Results on Gaussian partitions, rearrangement, Ehrhard concavity, residual scores and kernel clustering, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• The propeller — Corollary 2.2. Three planar sectors of angle 2 pi/3 have sum of squared Gaussian first moments 9/(8 pi); so C(d,k) >= 9/(8 pi) for d >= 2 and k >= 3.
• Duality with expected maxima (Khot-Naor) — Lemma 3.2. sqrt C(n,N) is the maximum of E max_i <v_i,g> over lists with sum |v_i|^2 = 1; optimal partitions exist; for k <= N vectors, E max is at most sqrt C times their Euclidean norm.
• Structure of optimal partitions (Khot-Naor) — Proposition 4.1. An optimal partition with the fewest active cells has moments with negative pairwise inner products, cells equal to the score cones, and a moment span of dimension m - 1.
• At most four active cells (under HJN) — Theorem 4.3. Under the three-dimensional theorem (HJN), an optimal partition with at most four active cells has value at most 9/(8 pi).
• Polar decomposition in R^4 — Lemma 2.1. For g standard Gaussian in R^4, |g| and g/|g| are independent, E|g| = 3 sqrt(2 pi)/4, and a coordinate of g/|g| has density (2/pi) sqrt(1 - u^2).
• Rearrangement bounds — Proposition 2.4. In a hypothetical optimal partition with value above 9/(8 pi) and m >= 5 active cells, r_i < 2/3 and P_i > A r_i^2, with A = 0.929 for m = 5 and A = 0.884 for m >= 6.
• Ehrhard concavity of translates — Lemma 3.1. For a closed convex cone with nonempty interior, not the whole space, u -> Phi^{-1}(gamma(K + uh)) is concave.
• A truncated normal variance — Lemma 4.1. G(q) = phi(q)(q Phi(q) + phi(q))/Phi(q)^2 equals 1 - Var(Z | Z <= q), lies in (0,1) and is nonincreasing; P -> P^2 G(Phi^{-1}(P)) increases on (0, 1/2].
• Linear-quadratic bound — Proposition 5.2. In the hypothetical optimal partition every cell satisfies P_i > 0.415 r_i + 0.15 r_i^2.
• Two competing scores — Lemma 2.1. The residual covariance determinants relative to the shortest moment satisfy D_jk < (3/pi) t (1 + a_j)(1 + a_k).
• Constraints on the three largest lengths — Corollary 3.1. (c - t^2)(L - c - 2t^2) <= 8 (3/pi)^2 t^2 and (3/2)(c - t^2)^2 <= 10 (3/pi)^2 t^2.
• The Gaussian propeller bound (OpenAI; under HJN) — Theorem 7.1. Every finite measurable partition of R^d has sum of squared Gaussian first moments at most 9/(8 pi), with equality for the propeller when d >= 2 and k >= 3.
• Gaussian maxima — Corollary 8.1. E max_i <v_i, g> <= (3/(2 sqrt(2 pi))) (sum_i |v_i - vbar|^2)^(1/2), sharp for three vectors in the plane.
• Degree-one projection and influences — Lemma 2.1. The degree-one projection on a product of uniform finite spaces as a rational matrix; influences under relabelling of coordinates; the sum of influences up to degree D is at most D ||h||^2.
• From a Unique Games instance to a clustering input — Lemma 3.1. A rational centered positive semidefinite matrix whose clustering values are mu-averages of OBJ over the left vertices.
• Kernel clustering threshold (OpenAI; under KN-INF and UGT) — Theorem 4.1. For fixed k >= 3, finding a clustering within a fixed loss factor below (8 pi/9)(1 - 1/k) of the optimum is NP-hard.

Reading order

Read the lessons in order. The second to fourth lessons work in the setting fixed at the end of the first; the fifth combines their bounds; the sixth is an application that needs only the first and the fifth.