OctoInformBeta

OpenAI preprint, September 2026 · §3. Uniform compression from partitions · §3

§3 (proof of Proposition 3.2): common index, pivots, levels, rounding: An index omitted by small weight, pivots replaced at one graph step, and rounded level sums within three times that weight of the mixture

The steps that compress a mixture of graph distance profiles.

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

Let XX be a set carrying a family of labelings Li:X→ΛiL_i \colon X \to \Lambda_i indexed by a set ι\iota, each of which partitions XX into the classes of points with a common label. For a finite set of indices, two points of XX are adjacent when some labeling in the set gives them the same label; the distance to a fixed point in this graph, passed through a logarithmic cutoff, is a real function on XX, and these functions are the columns of a matrix. A combination of the columns with nonnegative weights of total mass at most one is a point of ℝX\mathbb R^X, the space of real functions on XX, lying in the convex hull of the columns and the origin.

The item is the proof of Proposition 3.2, in Section 3 of the OpenAI preprint Counterexamples to the duality conjecture for metric entropy, on uniform compression from partitions. The library states six claims about it and gives the grouping of weights and the rounding down to a finite mesh as two definitions.

Partition Graphs

The partition graph GTG_T of the labelings, for a finite set T⊆ιT \subseteq \iota of indices, is the simple graph on XX in which two distinct points xx and yy are adjacent when Li(x)=Li(y)L_i(x) = L_i(y) for some i∈Ti \in T.✦ The partition graph distance dT(x,y)d_T(x,y) between points x,y∈Xx, y \in X is the least number of edges on a path from xx to yy in GTG_T, a value in {0,1,2,…}∪{∞}\{0, 1, 2, \dots\} \cup \{\infty\} that is ∞\infty when xx and yy lie in different components.✦

The closed graph ball BT(v,k)B_T(v,k) of radius k∈ℕk \in \mathbb N about a point v∈Xv \in X in the partition graph GTG_T is the set BT(v,k)={x∈X:dT(x,v)≤k}.B_T(v,k) = \{x \in X : d_T(x,v) \le k\}.(1)✦ The indicator 𝟏B\mathbf 1_B of a set B⊆XB \subseteq X is the function on XX equal to 11 on BB and 00 off it.✦

Profiles, Columns and Mixtures

The cutoff profile of radius h∈ℕh \in \mathbb N is the real function φh\varphi_h on {0,1,2,…}∪{∞}\{0, 1, 2, \dots\} \cup \{\infty\} with φh(∞)=0\varphi_h(\infty) = 0 and, for finite dd, φh(d)=max⁡(0,1−log⁡(d+1)log⁡(h+1)),\varphi_h(d) = \max\Bigl(0,\; 1 - \frac{\log(d+1)}{\log(h+1)}\Bigr),(2)✦ where log\log is the natural logarithm. The log increment γh(j)\gamma_h(j), for natural numbers hh and jj, is the real number γh(j)=log⁡(j+2)−log⁡(j+1)log⁡(h+1).\gamma_h(j) = \frac{\log(j+2) - \log(j+1)}{\log(h+1)}.(3)✦

For a finite family 𝒯\mathcal T of finite subsets of ι\iota, the column index set is the product X×𝒯X \times \mathcal T, whose elements are the pairs (z,T)(z,T) of a point z∈Xz \in X and a member T∈𝒯T \in \mathcal T.✦ The graph distance column at (z,T)(z,T) is the function g(z,T)∈ℝXg_{(z,T)} \in \mathbb R^X given by g(z,T)(x)=φh(dT(x,z)).g_{(z,T)}(x) = \varphi_h\bigl(d_T(x,z)\bigr).(4)✦ For a matrix with columns gy∈ℝXg_y \in \mathbb R^X indexed by a finite set YY and a vector λ∈ℝY\lambda \in \mathbb R^Y, the combination of columns is the point fλ=∑y∈Yλygyf_\lambda = \sum_{y \in Y} \lambda_y g_y of ℝX\mathbb R^X.✦

The profile mixture of points vy∈Xv_y \in X and finite sets Ty⊆ιT_y \subseteq \iota, indexed by a finite set YY and weighted by real numbers μy\mu_y, is the function FμF_\mu on XX given by Fμ(x)=∑y∈Yμyφh(dTy(x,vy)).F_\mu(x) = \sum_{y \in Y} \mu_y\, \varphi_h\bigl(d_{T_y}(x, v_y)\bigr).(5)✦

Levels and Assignments

For points vy∈Xv_y \in X, finite sets Ty⊆ιT_y \subseteq \iota and weights μy\mu_y indexed by a finite set YY, and a level j∈ℕj \in \mathbb N, the level value Vj(x)V_j(x) at a point x∈Xx \in X is the real number Vj(x)=∑y∈Yμy𝟏BTy(vy,j)(x).V_j(x) = \sum_{y \in Y} \mu_y\, \mathbf 1_{B_{T_y}(v_y,\,j)}(x).(6)✦

An assignment σ\sigma of YY to a set KK of slots is a partial map from YY to KK together with, for each slot k∈Kk \in K, a center ck∈Xc_k \in X and a replacement pivot qk∈Xq_k \in X. The assigned value Aj(x)A_j(x) of the assignment at level jj and a point x∈Xx \in X is the real number Aj(x)=∑y∈Yσ(y) definedμy𝟏BTy(qσ(y),2j+1)(x).A_j(x) = \sum_{\substack{y \in Y \\ \sigma(y) \text{ defined}}} \mu_y\, \mathbf 1_{B_{T_y}(q_{\sigma(y)},\,2j+1)}(x).(7)✦

The Claim

Theorem 1. Let LiL_i, i∈ιi \in \iota, be labelings of a set XX.

(i) Common index. Let YY be a finite set, u≥1u \ge 1 an integer and θ≥0\theta \ge 0 a real number, let μy≥0\mu_y \ge 0 be weights with ∑y∈Yμy≤1\sum_{y \in Y} \mu_y \le 1, and let Ty⊆[u]={1,…,u}T_y \subseteq [u] = \{1, \dots, u\} be sets with |[u]\Ty|≤θu|[u] \setminus T_y| \le \theta u. Then there is an index i0∈[u]i_0 \in [u] with ∑y∈Yi0∉Tyμy≤θ.\sum_{\substack{y \in Y \\ i_0 \notin T_y}} \mu_y \le \theta.(8)✦

(ii) Pivot replacement. Let T⊆ιT \subseteq \iota be finite, i∈Ti \in T and j∈ℕj \in \mathbb N, and let v,z,z′∈Xv, z, z' \in X be points with dT(v,z)≤jd_T(v,z) \le j and Li(z′)=Li(z)L_i(z') = L_i(z). Then dT(v,z′)≤j+1andBT(v,j)⊆BT(z′,2j+1)⊆BT(v,3j+2).d_T(v,z') \le j+1 \quad\text{and}\quad B_T(v,j) \subseteq B_T(z',2j+1) \subseteq B_T(v,3j+2).(9)✦

For (iii) to (v), let YY be a finite set and, for each y∈Yy \in Y, let vy∈Xv_y \in X, let Ty⊆ιT_y \subseteq \iota be finite and let μy≥0\mu_y \ge 0; the level values (6), the assigned values (7) and the profile mixture (5) are those of these data.

(iii) Lower level bound. Let i∈ιi \in \iota and j∈ℕj \in \mathbb N, and let σ\sigma be an assignment of YY to slots, with centers ckc_k and representatives qkq_k, such that Li(qk)=Li(ck)L_i(q_k) = L_i(c_k) for every slot kk and every yy with σ(y)=k\sigma(y) = k has i∈Tyi \in T_y and dTy(ck,vy)≤jd_{T_y}(c_k, v_y) \le j. Let θ\theta be a real number such that the yy with i∉Tyi \notin T_y have total weight at most θ\theta and, for every point x′∈Xx' \in X, so do the unassigned yy with i∈Tyi \in T_y and x′∈BTy(vy,j)x' \in B_{T_y}(v_y, j). Then for every x∈Xx \in X Vj(x)−2θ≤Aj(x).V_j(x) - 2\theta \le A_j(x).(10)✦

(iv) Upper level bound. Under the hypotheses of (iii) on ii, jj and σ\sigma alone, for every x∈Xx \in X Aj(x)≤V3j+2(x).A_j(x) \le V_{3j+2}(x).(11)✦

(v) Combination of levels. Let ∑y∈Yμy≤1\sum_{y \in Y} \mu_y \le 1, let h≥1h \ge 1 be an integer and θ≥0\theta \ge 0 a real number with log⁡3/log⁡(h+1)≤θ\log 3 / \log(h+1) \le \theta, let x∈Xx \in X, and let αj\alpha_j and ρj\rho_j, for 0≤j<h0 \le j < h, be real numbers with Vj(x)−2θ≤αj≤V3j+2(x)V_j(x) - 2\theta \le \alpha_j \le V_{3j+2}(x) and 0≤αj−ρj≤θ0 \le \alpha_j - \rho_j \le \theta. Then Fμ(x)−3θ≤∑j=0h−1γh(j)ρj≤Fμ(x)+θ.F_\mu(x) - 3\theta \le \sum_{j=0}^{h-1} \gamma_h(j)\, \rho_j \le F_\mu(x) + \theta.(12)✦

(vi) Mixtures as combinations of columns. Let XX be finite, 𝒯\mathcal T a finite family of finite subsets of ι\iota, h∈ℕh \in \mathbb N and μ∈ℝX×𝒯\mu \in \mathbb R^{X \times \mathcal T}. Then the profile mixture of the points v(z,T)=zv_{(z,T)} = z and the sets T(z,T)=TT_{(z,T)} = T, indexed by the column index set, is the combination of the graph distance columns (4): for every x∈Xx \in X Fμ(x)=fμ(x).F_\mu(x) = f_\mu(x).(13)✦

Definition 1. Let σ\sigma be a partial map from a finite set YY to a set KK of slots, τ:Y→S\tau \colon Y \to S a map to a set SS of tags, and μ∈ℝY\mu \in \mathbb R^Y. The grouped weight ωk,t\omega_{k,t} of a slot k∈Kk \in K and a tag t∈St \in S is the real number ωk,t=∑y∈Yσ(y)=k,τ(y)=tμy.\omega_{k,t} = \sum_{\substack{y \in Y \\ \sigma(y) = k,\ \tau(y) = t}} \mu_y.(14)✦ For real numbers δ\delta and ww, the rounding rd⁡δ(w)\operatorname{rd}_\delta(w) of ww down to the mesh δ\delta is the real number rd⁡δ(w)=δmax⁡(0,⌊w/δ⌋).\operatorname{rd}_\delta(w) = \delta \max\bigl(0, \lfloor w/\delta \rfloor\bigr).(15)✦

What Is Checked

The claim is stated over the partition graphs GTG_T of a family of labelings of a set XX, their distances dTd_T and closed balls BT(v,k)B_T(v,k), the cutoff profile φh\varphi_h and the log increments γh(j)\gamma_h(j), the level values VjV_j and the assigned values AjA_j of an assignment with centers and representatives, the profile mixture FμF_\mu, and the graph distance columns g(z,T)g_{(z,T)} on X×𝒯X \times \mathcal T with their combinations fμf_\mu in ℝX\mathbb R^X.