OctoInformBeta

OpenAI preprint, September 2026 · §2. Extremal partitions and their centroids

Lemma 2.1: Centroid bounds and an optimizer with the fewest cells of positive Gaussian measure

Gaussian partition and width maxima are attained.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The partition problem is to maximize the sum of squared lengths of the Gaussian centroids of the cells of a partition of Euclidean space. Fix positive integers dd and kk, and equip ℝd\mathbb R^d with its usual Euclidean structure. The standard Gaussian measure γd\gamma_d on ℝd\mathbb R^d has mean zero and identity covariance.

A Gaussian-measurable partition A=(Ai)i=1kA=(A_i)_{i=1}^k of ℝd\mathbb R^d is a family of Borel sets satisfying (1).✦ Empty cells are allowed. Write 𝒫\mathcal P for the collection of these partitions. ∑i=1k𝟏Ai(x)=1for almost every x with respect to γd.\sum_{i=1}^k \mathbf 1_{A_i}(x)=1 \qquad\text{for almost every }x\text{ with respect to }\gamma_d.(1)

The Euclidean tuple space 𝒯=(ℝd)k\mathcal T=(\mathbb R^d)^k is the product of kk copies of ℝd\mathbb R^d, with the norm in (2).✦ ∥v∥2=∑i=1k∥vi∥2,v=(v1,…,vk)∈𝒯.\|v\|^2=\sum_{i=1}^k\|v_i\|^2, \qquad v=(v_1,\ldots,v_k)\in\mathcal T.(2)

The Gaussian centroid z(E)z(E) of a set E⊆ℝdE\subseteq\mathbb R^d is its unnormalized vector integral in (3).✦ For a set family A=(Ai)i=1kA=(A_i)_{i=1}^k, the centroid tuple Z(A)∈𝒯Z(A)\in\mathcal T and the Gaussian centroid energy F(A)F(A) are specified in (4). z(E)=∫Exdγd(x).z(E)=\int_E x\,d\gamma_d(x).(3) Z(A)=(z(A1),…,z(Ak)),F(A)=∑i=1k∥z(Ai)∥2.Z(A)=\bigl(z(A_1),\ldots,z(A_k)\bigr), \qquad F(A)=\sum_{i=1}^k\|z(A_i)\|^2.(4)

For v∈𝒯v\in\mathcal T, the maximum linear score sv(x)s_v(x) at x∈ℝdx\in\mathbb R^d is the maximum of the inner products with its coordinate vectors.✦ The Gaussian width W(v)W(v) of a tuple v∈𝒯v\in\mathcal T is the Gaussian integral of its maximum linear score svs_v, as in (5).✦ sv(x)=max1≤i≤k⟨vi,x⟩,W(v)=∫ℝdsv(x)dγd(x).s_v(x)=\max_{1\le i\le k}\langle v_i,x\rangle, \qquad W(v)=\int_{\mathbb R^d}s_v(x)\,d\gamma_d(x).(5)

The maximizing cell Di(v)⊆ℝdD_i(v)\subseteq\mathbb R^d with ties broken by the least label is the set where ii is the least index attaining the maximum score.✦ Its formula is (6); write D(v)=(Di(v))i=1kD(v)=(D_i(v))_{i=1}^k. Di(v)={x∈ℝd:⟨vj,x⟩≤⟨vi,x⟩for every j,⟨vj,x⟩<⟨vi,x⟩for every j<i}.D_i(v)=\left\{x\in\mathbb R^d: \begin{array}{ll} \langle v_j,x\rangle\le\langle v_i,x\rangle &\text{for every }j,\\ \langle v_j,x\rangle<\langle v_i,x\rangle &\text{for every }j<i \end{array}\right\}.(6)

An active label ii of a set family A=(Ai)i=1kA=(A_i)_{i=1}^k in ℝd\mathbb R^d is an index in {1,…,k}\{1,\ldots,k\} whose cell has positive Gaussian measure. The active label set I(A)I(A) and the number a(A)a(A) of active cells are given in (7). I(A)={i∈{1,…,k}:γd(Ai)>0},a(A)=|I(A)|.I(A)=\{i\in\{1,\ldots,k\}:\gamma_d(A_i)>0\}, \qquad a(A)=|I(A)|.(7)

An optimal partition AA of ℝd\mathbb R^d into kk labeled cells is a member of 𝒫\mathcal P whose centroid energy is at least that of every member of 𝒫\mathcal P.✦ Denote the collection of optimal partitions by 𝒪\mathcal O. A minimal optimal partition AA is a member of 𝒪\mathcal O whose number of active cells is no greater than that of any other member of 𝒪\mathcal O.✦

The Claim

Theorem 1 (Lemma 2.1). There is a tuple v*∈𝒯v_*\in\mathcal T satisfying (8).✦ ∥v*∥=1,W(w)≤W(v*)for every w∈𝒯 with ∥w∥=1.\|v_*\|=1, \qquad W(w)\le W(v_*) \quad\text{for every }w\in\mathcal T\text{ with }\|w\|=1.(8)✦

Let v∈𝒯v\in\mathcal T have width at least that of every unit tuple. Every A∈𝒫A\in\mathcal P then satisfies (9).✦ ∥Z(A)∥≤W(v).\|Z(A)\|\le W(v).(9)✦

For every v∈𝒯v\in\mathcal T, the score cells satisfy (10).✦ ∑i=1k⟨vi,z(Di(v))⟩=W(v).\sum_{i=1}^k\langle v_i,z(D_i(v))\rangle=W(v).(10)✦

There is a partition A*∈𝒫A_*\in\mathcal P satisfying (11).✦ F(B)≤F(A*)for every B∈𝒫.F(B)\le F(A_*)\qquad\text{for every }B\in\mathcal P.(11)✦

There is a partition AminA_{\min} satisfying (12).✦ Amin∈𝒪,a(Amin)≤a(B)for every B∈𝒪.A_{\min}\in\mathcal O, \qquad a(A_{\min})\le a(B)\quad\text{for every }B\in\mathcal O.(12)✦

Let AA be an optimal partition and put C=F(A)C=F(A). Every v∈𝒯v\in\mathcal T satisfies (13).✦ W(v)≤C∥v∥.W(v)\le\sqrt C\,\|v\|.(13)✦

In the paper, the result reads: for n≥4n\ge4, N=n+1N=n+1, and g∼γng\sim\gamma_n, the optimal value CC for NN cells in ℝn\mathbb R^n satisfies C=max⁡∑i=1N∥vi∥2=1𝔼max⁡1≤i≤N⟨vi,g⟩\sqrt C=\max_{\sum_{i=1}^N\|v_i\|^2=1}\mathbb E\max_{1\le i\le N} \langle v_i,g\rangle, with the maximum over vectors vi∈ℝnv_i\in\mathbb R^n, the supremum defining CC is attained, and for every 1≤k≤N1\le k\le N and v1,…,vk∈ℝnv_1,\ldots,v_k\in\mathbb R^n one has 𝔼max⁡1≤i≤k⟨vi,g⟩≤C(∑i=1k∥vi∥2)1/2\mathbb E\max_{1\le i\le k}\langle v_i,g\rangle \le\sqrt C\,(\sum_{i=1}^k\|v_i\|^2)^{1/2}.

What Is Checked

The claims are stated over finite Euclidean vector tuples and Borel Gaussian-measurable partitions, with optimality compared among partitions of the same space with the same kk labels.