OctoInformBeta

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

Corollary 3.3 [Signed compression]: From a list AA within 3θ3\theta of the nonnegative combinations, the differences A−AA-A, at most |A|2|A|^2 functions, cover the hull at uniform scale 6θ6\theta

Differences of a positive list cover the absolutely convex hull.

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 and YY a finite set. The real space ℝX\mathbb{R}^X is the vector space of all functions from XX to ℝ\mathbb{R}, and a real matrix gg with rows indexed by XX and columns indexed by YY is given by its columns gy∈ℝXg_y \in \mathbb{R}^X, y∈Yy \in Y. The ℓ1\ell^1 norm of a point λ\lambda of ℝY\mathbb{R}^Y is ∥λ∥1=∑y|λy|\|\lambda\|_1 = \sum_{y} |\lambda_y|✦, and the unit ℓ1\ell^1 ball B1YB_1^Y is the set of points of ℝY\mathbb{R}^Y of ℓ1\ell^1 norm at most 11✦. The combination of the columns with coefficients λ∈ℝY\lambda \in \mathbb{R}^Y is the point fλf_\lambda of ℝX\mathbb{R}^X given by fλ(x)=∑y∈Yλygy(x)(x∈X).f_\lambda(x) = \sum_{y \in Y} \lambda_y \, g_y(x) \qquad (x \in X).(1)✦

As λ\lambda runs over B1YB_1^Y, the combination fλf_\lambda runs over the absolutely convex hull ℱ=absconv⁡{gy}\mathcal F = \operatorname{absconv}\{g_y\} of the columns; with nonnegative coefficients of sum at most 11 it runs over the convex hull ℱ+\mathcal F_+ of the columns and the origin. The item is about covering ℱ\mathcal F in the uniform norm, by translates of the cube εB∞X=[−ε,ε]X\varepsilon B_\infty^X = [-\varepsilon, \varepsilon]^X with centers anywhere in ℝX\mathbb{R}^X, once such a cover of ℱ+\mathcal F_+ is at hand: what the signs of the coefficients cost in the number of centers and in the accuracy.

The library states the result for every matrix and, again, for one family of matrices whose entries are graph distances on a finite set, cut off at a radius.

Approximation Lists and Codes

For a real number ε\varepsilon, two points ff and kk of ℝX\mathbb{R}^X are uniformly ε\varepsilon-close, ∥f−k∥∞≤ε\|f - k\|_\infty \le \varepsilon, when |f(x)−k(x)|≤ε|f(x) - k(x)| \le \varepsilon at every point xx of XX.✦ A uniform ε\varepsilon-approximation list for gg is a finite set BB of points of ℝX\mathbb{R}^X that comes within ε\varepsilon of every member of ℱ\mathcal F: every λ∈B1Y has some b∈B with ∥fλ−b∥∞≤ε.\text{every } \lambda \in B_1^Y \text{ has some } b \in B \text{ with } \|f_\lambda - b\|_\infty \le \varepsilon.(2)✦ Its members need not lie in ℱ\mathcal F.

A positive list for gg at scale θ∈ℝ\theta \in \mathbb{R} is a finite set AA of points of ℝX\mathbb{R}^X that comes within 3θ3\theta of every member of ℱ+\mathcal F_+: every μ∈ℝY with all μy≥0 and ∑yμy≤1 has some a∈A with ∥fμ−a∥∞≤3θ.\text{every } \mu \in \mathbb{R}^Y \text{ with all } \mu_y \ge 0 \text{ and } \textstyle\sum_y \mu_y \le 1 \text{ has some } a \in A \text{ with } \|f_\mu - a\|_\infty \le 3\theta.(3)✦

The difference list of a finite set AA of points of ℝX\mathbb{R}^X is the finite set A−A={a−b:a,b∈A}A - A = \{a - b : a, b \in A\}.✦ A pair code for AA is an ordered pair (a,b)(a, b) of members of AA, a point of A×AA \times A✦, and its decoding is the difference a−ba - b✦.

Graph Distance Columns

Let XX be a finite set and, for each index ii in a set ι\iota, let LiL_i be a labeling of XX, a map from XX to a set of labels. The partition graph GTG_T of the labelings, for a finite set TT of indices, is the simple graph on XX in which two distinct points xx and yy are adjacent when some index i∈Ti \in T gives them the same label, Li(x)=Li(y)L_i(x) = L_i(y).✦ The graph distance dT(x,y)d_T(x, y) between points xx and yy of XX 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 cutoff profile of radius h∈ℕh \in \mathbb{N} is the function φh\varphi_h on {0,1,2,…}∪{∞}\{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.(4)✦

Let 𝒯\mathcal T be a finite family of finite sets of indices. The column index set is X×𝒯X \times \mathcal T: a column index is a pair (z,T)(z, T) of a point z∈Xz \in X and a member TT of 𝒯\mathcal T, which selects the partition graph.✦ The graph distance column g(z,T)g_{(z,T)} at the column index (z,T)(z, T) is the function on XX given by g(z,T)(x)=φh(dT(x,z)).g_{(z,T)}(x) = \varphi_h\bigl(d_T(x, z)\bigr).(5)✦

The Claim

Theorem 1 (Signed compression). (a) Let XX be a set, YY a finite set, gg a real matrix with columns gy∈ℝXg_y \in \mathbb{R}^X, θ\theta a real number, and AA a positive list for gg at scale θ\theta. Then the difference list has at most |A|2|A|^2 members, |A−A|≤|A|2,|A - A| \le |A|^2,(6)✦ and is a uniform 6θ6\theta-approximation list for gg: every λ∈B1Y has some b∈A−A with ∥fλ−b∥∞≤6θ.\text{every } \lambda \in B_1^Y \text{ has some } b \in A - A \text{ with } \|f_\lambda - b\|_\infty \le 6\theta.(7)✦ The set of pair codes for AA has exactly |A|2|A|^2 members, |A×A|=|A|2,|A \times A| = |A|^2,(8)✦ and there is a map c:B1Y→A×Ac \colon B_1^Y \to A \times A such that, for all λ,λ′∈B1Y\lambda, \lambda' \in B_1^Y, ∥fλ−(a−b)∥∞≤6θwhere c(λ)=(a,b),∥fλ−fλ′∥∞≤12θwhenever c(λ)=c(λ′).\begin{gathered} \|f_\lambda - (a - b)\|_\infty \le 6\theta \quad \text{where } c(\lambda) = (a, b), \\ \|f_\lambda - f_{\lambda'}\|_\infty \le 12\theta \quad \text{whenever } c(\lambda) = c(\lambda'). \end{gathered}(9)✦

(b) Let u,q,h,su, q, h, s be positive integers and θ>0\theta > 0 a real number with sθ≥1s\theta \ge 1 and log⁡3/log⁡(h+1)≤θ\log 3 / \log(h+1) \le \theta. Let L0,…,Lu−1L_0, \dots, L_{u-1} be labelings of a finite set XX, each taking at most qq values, and let 𝒯\mathcal T be a finite family of subsets of {0,…,u−1}\{0, \dots, u-1\}, each missing at most θu\theta u indices. Then, for the graph distance columns (5) indexed by X×𝒯X \times \mathcal T, there are finite sets AA and BB of functions on XX such that A≠∅,|A|≤uqhs(1+s2uθ)hs2u,|B|≤|A|2,every λ∈B1X×𝒯 has some b∈B with ∥fλ−b∥∞≤6θ.\begin{gathered} A \ne \emptyset, \qquad |A| \le u \, q^{hs} \Bigl(1 + \frac{s \, 2^u}{\theta}\Bigr)^{hs \, 2^u}, \qquad |B| \le |A|^2, \\ \text{every } \lambda \in B_1^{X \times \mathcal T} \text{ has some } b \in B \text{ with } \|f_\lambda - b\|_\infty \le 6\theta. \end{gathered}(10)✦

In the paper, the result reads: with fλ=∑yλygyf_\lambda = \sum_y \lambda_y g_y and ℱ={fλ:λ∈B1Y}=absconv⁡{gy}\mathcal F = \{f_\lambda : \lambda \in B_1^Y\} = \operatorname{absconv}\{g_y\}, there is a list of at most Q2Q^2 functions approximating every member of ℱ\mathcal F to uniform error 6θ6\theta, and B1YB_1^Y can be partitioned into at most Q2Q^2 nonempty clusters on each of which ∥fλ−fλ′∥∞≤12θ\|f_\lambda - f_{\lambda'}\|_\infty \le 12\theta, where QQ bounds the size of the positive list AA.

The paper’s clusters are the nonempty fibers of the map cc in (9), a map into the |A|2|A|^2 pair codes of (8).

What Is Checked

The claim is stated over the combinations fλf_\lambda of the columns of a matrix with coefficients in the unit ℓ1\ell^1 ball, uniform closeness, approximation lists, positive lists, the difference list and the pair codes with their decoding, and, in part (b), over the graph distance columns (5) on the column index set X×𝒯X \times \mathcal T, built from the partition graphs GTG_T, their distances dTd_T and the cutoff profile φh\varphi_h.