By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

The Gaussian propeller bound in every dimension

For all positive integers dd and kk, every measurable partition (A1,…,Ak)(A_1, \dots, A_k) of Rd\mathbb{R}^d (with empty cells allowed) satisfies ∑i=1k∥∫Aix dγd(x)∥2≤98π\sum_{i=1}^k \left\| \int_{A_i} x \, d\gamma_d(x) \right\|^2 \le \frac{9}{8\pi}, and the constant is sharp whenever d≥2d \ge 2 and k≥3k \ge 3, attained by three planar sectors of angle 2π/32\pi/3 multiplied by the orthogonal complement of their plane, with any further cells empty.

For a putative optimal partition with C>9/(8π)C > 9/(8\pi) and the fewest active cells z1,…,zmz_1, \dots, z_m, the centroids satisfy ⟨zi,zj⟩<0\langle z_i, z_j \rangle < 0 for i≠ji \neq j, their span VV has dimension m−1m-1, every proper subset of the centroids is linearly independent, the optimal cells have closed conical representatives Ki={x∈Rn:⟨zi−zj,x⟩≥0 for every j≠i}K_i = \{x \in \mathbb{R}^n : \langle z_i - z_j, x \rangle \ge 0 \text{ for every } j \neq i\}, and m≥5m \ge 5.

Under the putative extremizer with C>B2C > B^2 and m≥5m \ge 5, setting A=0.929A = 0.929 for m=5m = 5 and A=0.884A = 0.884 for m≥6m \ge 6, every cell satisfies ri≤2/3r_i \le 2/3, Pi≥Ari2P_i \ge A r_i^2, and Pi≥0.415ri+0.15ri2P_i \ge 0.415 r_i + 0.15 r_i^2.

For the putative extremizer with r1≥⋯≥rm=t>0r_1 \ge \dots \ge r_m = t > 0, L=r12+r22L = r_1^2 + r_2^2, and c=r32c = r_3^2, the quantities L,c,tL, c, t satisfy (c−t2)(L−c−2t2)≤8(3/π)2t2(c - t^2)(L - c - 2t^2) \le 8(3/\pi)^2 t^2 and 32(c−t2)2≤10(3/π)2t2\frac{3}{2}(c - t^2)^2 \le 10(3/\pi)^2 t^2.

The scalar bounds of Lemma 3.1 and the geometric constraints of Corollary 4.2 are incompatible, excluding m≥5m \ge 5 active cells and ruling out C>9/(8π)C > 9/(8\pi).

For positive integers d,kd, k, a standard Gaussian vector gg in Rd\mathbb{R}^d, and v1,…,vk∈Rdv_1, \dots, v_k \in \mathbb{R}^d with vˉ=k−1∑i=1kvi\bar{v} = k^{-1} \sum_{i=1}^k v_i, Emax⁡1≤i≤k⟨vi,g⟩≤322π(∑i=1k∥vi−vˉ∥2)1/2\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}, and the constant is sharp already for three vectors in the plane.

For each fixed k≥3k \ge 3 and every fixed 1≤α<αk=8π9(1−1k)1 \le \alpha < \alpha_k = \frac{8\pi}{9}\left(1 - \frac{1}{k}\right), it is NP-hard, given a rational symmetric matrix A⪰0A \succeq 0 with A1=0A\mathbf{1} = 0 and the identity-target objective (6.1), to find σ:[N]→[k]\sigma : [N] \to [k] such that valA(σ)≥Clust(A∣Ik)/α\mathrm{val}_A(\sigma) \ge \mathrm{Clust}(A \mid I_k)/\alpha.

Methods

Gaussian-maximum duality and minimal-cell reduction: replacing the infinite-dimensional partition optimization by a finite list of Gaussian linear scores via Euclidean norm duality (Lemma 2.1) and reducing a hypothetical counterexample to a minimal-active-cell optimal partition with m >= 5 (Lemma 2.2).

Source excerpts

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

Halfspace and spherical rearrangement bounds: bounding cell probabilities below in terms of normalized centroid lengths via halfspace rearrangement (for m >= 6) and spherical cap rearrangement in R^4 (for m = 5).

Source excerpts

“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.” · Show in paper

Score-deletion and Ehrhard's inequality: bounding the loss on removing one score from below via the extremal dual bound and from above via translations of the winning cone and Ehrhard's inequality.

Source excerpts

“Ehrhard's inequality states that Phi^-1 o gamma_{m-1} is concave under Minkowski interpolation of convex sets [2]; we use the formulation in [1, Theorem 1.1], which also allows general Borel sets.” · Show in paper

Orthogonal projection and residual covariance determinant bound: projecting other scores orthogonally to the smallest-norm centroid to obtain independent residual Gaussian scores and bounding a positive-part integral via the two-dimensional Gaussian density maximum.

Source excerpts

“We will use the centroid identity for this cell to control the joint distribution of any two competing scores.” · Show in paper

Rational interval enclosures: using exact rational arithmetic, Taylor's integral remainder for e^-y and Phi(x), and binomial series bounds for arcsin x to certify all finite numerical comparisons without numerical optimization or quadrature.

Source excerpts

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

Kernel-clustering reduction from Unique Games: constructing a rational centered positive semidefinite matrix A in deterministic polynomial time from a bipartite Unique Games instance (Lemma 6.4) and proving completeness (Lemma 6.5) and soundness (Lemma 6.6) via Khot-Naor's low-influence bound.

Source excerpts

“Lemma 6.4. For fixed k, 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 >= 0, A1 = 0.” · Show in paper