OctoInformBeta

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

Proposition 3.2 [Uniform compression]: When log⁡3/log⁡(h+1)≤θ\log 3/\log(h+1)\le\theta and sθ≥1s\theta\ge 1, mixtures of the profiles φh(dT(x,z))\varphi_h(d_T(x,z)) lie within 3θ3\theta of at most uqhs(1+s2u/θ)hs2uuq^{hs}(1+s2^u/\theta)^{hs2^u} functions

A small list approximates every mixture of graph 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

Take a set XX and a matrix whose columns gyg_y, y∈Yy \in Y, are real functions on XX, with YY finite. For λ∈ℝY\lambda \in \mathbb R^Y, a function from YY to ℝ\mathbb R, the combination fλ=∑yλygyf_\lambda = \sum_y \lambda_y g_y is a mixture of the columns when λy≥0\lambda_y \ge 0 for every yy and ∑yλy≤1\sum_y \lambda_y \le 1. The mixtures fill the convex hull KK of 00 and the columns in ℝX\mathbb R^X, and the question is how many translates of the cube 3θB∞3\theta B_\infty, with B∞=[−1,1]XB_\infty = [-1,1]^X and θ>0\theta > 0, it takes to cover KK.

A set 𝒜\mathcal A of real functions on XX is a positive compression of gg at accuracy θ\theta when every mixture fλf_\lambda is uniformly within 3θ3\theta of some A∈𝒜A \in \mathcal A: |fλ(x)−A(x)|≤3θfor every x∈X.|f_\lambda(x) - A(x)| \le 3\theta \quad \text{for every } x \in X.(1)✦ A finite positive compression 𝒜\mathcal A is the set of centers of a covering of KK by |𝒜||\mathcal A| translates of 3θB∞3\theta B_\infty.

In this item the columns are profiles of distances in graphs built from partitions of XX, and the compression is the set of functions decoded from a finite set of codes.

Partition Graphs and Their Profiles

For a natural number nn, [n]={0,…,n−1}[n] = \{0, \dots, n-1\}. Let uu be a positive integer and L0,…,Lu−1L_0, \dots, L_{u-1} labelings of XX, that is, maps from XX to sets of labels, each splitting XX into the classes of points that share a label. The partition graph GTG_T of the labelings, for a set T⊆[u]T \subseteq [u] 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 graph distance dT(x,y)d_T(x, y) is the least number of edges on a path from xx to yy in GTG_T, and ∞\infty when the two points 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 vv of XX is the set of points xx with dT(x,v)≤kd_T(x, v) \le k✦; its indicator function is 𝟏BT(v,k)\mathbf 1_{B_T(v, k)}✦.

The cutoff profile of radius h∈ℕh \in \mathbb N is the real function on distances d∈{0,1,2,…}∪{∞}d \in \{0, 1, 2, \dots\} \cup \{\infty\} given by φh(d)=max⁡{0,1−log⁡(d+1)log⁡(h+1)}for finite d,φh(∞)=0.\varphi_h(d) = \max\Bigl\{0,\ 1 - \frac{\log(d+1)}{\log(h+1)}\Bigr\} \ \text{for finite } d, \qquad \varphi_h(\infty) = 0.(2)✦

For a family 𝒯\mathcal T of subsets of [u][u], the column index set is Y=X×𝒯Y = X \times \mathcal T✦, and the graph distance column at y=(z,T)y = (z, T) in YY is the real function on XX gy(x)=φh(dT(x,z)).g_y(x) = \varphi_h(d_T(x, z)).(3)✦ For a finite set Ω\Omega, centers vω∈Xv_\omega \in X, index sets Tω⊆[u]T_\omega \subseteq [u] and weights μ∈ℝΩ\mu \in \mathbb R^\Omega, the profile mixture is the real function on XX Pμ(x)=∑ω∈Ωμωφh(dTω(x,vω)).P_\mu(x) = \sum_{\omega \in \Omega} \mu_\omega\, \varphi_h(d_{T_\omega}(x, v_\omega)).(4)✦

Codes and the Compression List

Fix θ>0\theta > 0 and positive integers hh and ss. For a positive integer qq, a fixed label encoding EE of the labelings with qq codes is a choice of maps ei:X→[q]e_i \colon X \to [q] and ri:[q]→Xr_i \colon [q] \to X, one pair for each i∈[u]i \in [u], such that for all x,x′∈Xx, x' \in X, ei(x)=ei(x′)e_i(x) = e_i(x') exactly when Li(x)=Li(x′)L_i(x) = L_i(x'), and Li(ri(ei(x)))=Li(x)L_i(r_i(e_i(x))) = L_i(x).✦

The rounding mesh is δ=θ/(s2u)\delta = \theta/(s2^u)✦ and the weight code size is N=⌊1/δ⌋+1N = \lfloor 1/\delta \rfloor + 1✦; a weight code n∈[N]n \in [N] decodes to the weight δn\delta n✦. A compression code is a triple κ=(i,c,w)\kappa = (i, c, w) of an index i∈[u]i \in [u], a label code c(j,k)∈[q]c(j, k) \in [q] for each level j∈[h]j \in [h] and slot k∈[s]k \in [s], and a weight code w(j,k,T)∈[N]w(j, k, T) \in [N] for each level, slot and subset TT of [u][u].✦ With 2[u]2^{[u]} the family of subsets of [u][u], the compression codes form the finite set 𝒞=[u]×[q][h]×[s]×[N][h]×[s]×2[u].\mathcal C = [u] \times [q]^{[h] \times [s]} \times [N]^{[h] \times [s] \times 2^{[u]}}.(5)✦

The decoder of EE sends a compression code κ=(i,c,w)\kappa = (i, c, w), with pivots ri(c(j,k))∈Xr_i(c(j, k)) \in X, to the real function on XX DE(κ)(x)=∑j∈[h]γj∑k∈[s]∑T⊆[u]δw(j,k,T)𝟏BT(ri(c(j,k)),2j+1)(x),D_E(\kappa)(x) = \sum_{j \in [h]} \gamma_j \sum_{k \in [s]} \sum_{T \subseteq [u]} \delta\, w(j, k, T)\, \mathbf 1_{B_T(r_i(c(j, k)),\, 2j+1)}(x),(6)✦ where γj=(log⁡(j+2)−log⁡(j+1))/log⁡(h+1)\gamma_j = (\log(j+2) - \log(j+1))/\log(h+1) is the log increment of radius hh. The compression list 𝒜E\mathcal A_E of EE is the image of the decoder, the finite set of the functions DE(κ)D_E(\kappa) for κ∈𝒞\kappa \in \mathcal C.✦

With the number of pivot slots s=⌈1/θ⌉s = \lceil 1/\theta \rceil, the encoding cost is Ch,θ,u=log⁡u+hs2ulog⁡(1+s2uθ).C_{h,\theta,u} = \log u + hs2^u \log\Bigl(1 + \frac{s2^u}{\theta}\Bigr).(7)✦

The Claim

Theorem 1 (Uniform compression). Let u,q,h,su, q, h, s be positive integers, θ>0\theta > 0, and L0,…,Lu−1L_0, \dots, L_{u-1} labelings of a set XX.

  1. Suppose that XX is finite, that each LiL_i takes at most qq values, that sθ≥1s\theta \ge 1 and log⁡3/log⁡(h+1)≤θ\log 3/\log(h+1) \le \theta, and that 𝒯\mathcal T is a family of subsets TT of [u][u] with |[u]\T|≤θu|[u] \setminus T| \le \theta u. Then some nonempty finite set 𝒜\mathcal A of real functions on XX is a positive compression at accuracy θ\theta of the columns (3), and |𝒜|≤uqhs(1+s2uθ)hs2u.|\mathcal A| \le u\, q^{hs} \Bigl(1 + \frac{s2^u}{\theta}\Bigr)^{hs2^u}.(8)✦

  2. Under the conditions of (a) on XX, ss, θ\theta, hh and 𝒯\mathcal T, let EE be a fixed label encoding with qq codes. Every λ∈ℝY\lambda \in \mathbb R^Y with λy≥0\lambda_y \ge 0 and ∑yλy≤1\sum_y \lambda_y \le 1 has some A∈𝒜EA \in \mathcal A_E with fλ(x)−3θ≤A(x)≤fλ(x)+θfor every x∈X.f_\lambda(x) - 3\theta \le A(x) \le f_\lambda(x) + \theta \quad \text{for every } x \in X.(9)✦

  3. Suppose only that sθ≥1s\theta \ge 1 and log⁡3/log⁡(h+1)≤θ\log 3/\log(h+1) \le \theta, and let EE be a fixed label encoding with qq codes. Let Ω\Omega be a finite set, vω∈Xv_\omega \in X centers, Tω⊆[u]T_\omega \subseteq [u] index sets with |[u]\Tω|≤θu|[u] \setminus T_\omega| \le \theta u, and μω≥0\mu_\omega \ge 0 weights with ∑ωμω≤1\sum_\omega \mu_\omega \le 1. Then some code κ∈𝒞\kappa \in \mathcal C satisfies Pμ(x)−3θ≤DE(κ)(x)≤Pμ(x)+θfor every x∈X.P_\mu(x) - 3\theta \le D_E(\kappa)(x) \le P_\mu(x) + \theta \quad \text{for every } x \in X.(10)✦

  4. Every fixed label encoding EE with qq codes satisfies |𝒜E|≤uqhs(1+s2uθ)hs2u.|\mathcal A_E| \le u\, q^{hs} \Bigl(1 + \frac{s2^u}{\theta}\Bigr)^{hs2^u}.(11)✦

  5. If s=⌈1/θ⌉s = \lceil 1/\theta \rceil, every nonempty finite set 𝒜\mathcal A with |𝒜|≤uqhs(1+s2u/θ)hs2u|\mathcal A| \le u q^{hs}(1 + s2^u/\theta)^{hs2^u} satisfies log⁡|𝒜|≤hslog⁡q+Ch,θ,u.\log |\mathcal A| \le hs \log q + C_{h,\theta,u}.(12)✦

In the paper, the result reads: if XX is finite and nonempty, u,q≥1u, q \ge 1, 0<θ<10 < \theta < 1, 𝒯\mathcal T is nonempty and satisfies the paper’s condition (3.1), h≥1h \ge 1 with log⁡3/log⁡(h+1)≤θ\log 3/\log(h+1) \le \theta, and s=⌈1/θ⌉s = \lceil 1/\theta \rceil, then there is a list 𝒜\mathcal A of QQ real functions on XX such that every nonnegative combination ff of the columns of total mass at most one, the paper’s class ℱ+\mathcal F_+, has some A∈𝒜A \in \mathcal A with f−3θ≤A≤f+θf - 3\theta \le A \le f + \theta pointwise, so that ∥f−A∥∞≤3θ\|f - A\|_\infty \le 3\theta, and log⁡Q≤hslog⁡q+Ch,θ,u\log Q \le hs \log q + C_{h,\theta,u} with Ch,θ,u=log⁡u+hs2ulog⁡(1+s2u/θ)C_{h,\theta,u} = \log u + hs2^u \log(1 + s2^u/\theta).

Parts (b), (d) and (e), with s=⌈1/θ⌉s = \lceil 1/\theta \rceil, give the one-sided bounds and the bound on log⁡Q\log Q for the single list 𝒜E\mathcal A_E of a fixed label encoding.

What Is Checked

The theorem is stated over the partition graphs GTG_T of the labelings with their distances dTd_T and graph balls, the cutoff profile φh\varphi_h and its log increments γj\gamma_j, the columns gyg_y on Y=X×𝒯Y = X \times \mathcal T and the profile mixtures PμP_\mu, positive compression at accuracy θ\theta, fixed label encodings, the compression codes with their rounding mesh and weight codes, the decoder DED_E with its image 𝒜E\mathcal A_E, and the encoding cost Ch,θ,uC_{h,\theta,u}.