OctoInformBeta

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

§3 (setting): partition graphs, the logarithmic profile and the columns: Label maps LiL_i on XX give graphs GTG_T with distances dTd_T, and the columns are g(v,T)(x)=ϕh(dT(x,v))g_{(v,T)}(x)=\phi_h(d_T(x,v)) for (v,T)∈X×𝒯(v,T)\in X\times\mathcal T

Matrix columns from logarithmic bumps on partition graphs.

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

Start from a set XX of points and uu label maps LiL_i on it, i∈[u]={1,…,u}i \in [u] = \{1, \dots, u\}, each taking at most qq values. A label map cuts XX into classes, the points that share a label. A set TT of indices turns XX into a graph, two points being joined when some LiL_i with i∈Ti \in T gives them the same label, and the graph distance dTd_T counts the steps between two points, infinite across components.

Fix a radius h≥1h \ge 1. Around a base point vv, the column g(v,T)g_{(v,T)} is a bump on XX of height 11 at vv that decays with the logarithm of dT(x,v)d_T(x,v) and vanishes at distance hh and beyond, and off the component of vv. The columns over all base points vv and all TT in a family 𝒯\mathcal T make a matrix, and its rows RxR_x, one for each point xx of XX, are points of ℝX×𝒯\mathbb R^{X \times \mathcal T}.

Label Maps and Their Encodings

Let XX be a set and ι\iota an index set. A family of label maps on XX indexed by ι\iota is a family of maps Li:X→ΣiL_i : X \to \Sigma_i, i∈ιi \in \iota, each into a set Σi\Sigma_i of labels.

Take ι=[u]\iota = [u], a natural number qq, and [q]={1,…,q}[q] = \{1, \dots, q\}. A fixed label encoding of (Li)i∈[u](L_i)_{i \in [u]} with qq codes is a family of maps ei:X→[q]e_i : X \to [q] together with maps ρi:[q]→X\rho_i : [q] \to X, i∈[u]i \in [u], such that for every ii and all points x,zx, z of XX ei(x)=ei(z)⇔Li(x)=Li(z),Li(ρi(ei(x)))=Li(x).e_i(x) = e_i(z) \iff L_i(x) = L_i(z), \qquad L_i\bigl(\rho_i(e_i(x))\bigr) = L_i(x).(1)✦

If XX is finite and nonempty and |Li(X)|≤qfor every i∈[u],|L_i(X)| \le q \quad \text{for every } i \in [u],(2)✦ then (Li)i∈[u](L_i)_{i \in [u]} has a fixed label encoding with qq codes.

Partition Graphs

For a subset TT of ι\iota, the partition graph GTG_T is the simple graph on XX in which two points xx and zz are adjacent when x≠zandLi(x)=Li(z) for some i∈T.x \ne z \quad \text{and} \quad L_i(x) = L_i(z) \text{ for some } i \in T.(3)✦

The distance dT(x,z)d_T(x,z) between points xx and zz of XX is their graph distance in GTG_T: dT(x,z)=min⁡{ℓ:GT has a path of length ℓ from x to z},min⁡∅=∞,d_T(x,z) = \min\{\ell : G_T \text{ has a path of length } \ell \text{ from } x \text{ to } z\}, \qquad \min \emptyset = \infty,(4)✦ so that dTd_T takes values in {0,1,2,…}∪{∞}\{0, 1, 2, \dots\} \cup \{\infty\}.

For a natural number kk, the ball of radius kk about a point zz in GTG_T is the set of points xx of XX with dT(x,z)≤k.d_T(x,z) \le k.(5)✦

The Logarithmic Profile

The logarithmic profile ϕh\phi_h with cutoff hh, for a natural number hh, is the real function on {0,1,2,…}∪{∞}\{0, 1, 2, \dots\} \cup \{\infty\} given by ϕh(d)=max⁡{0,1−log⁡(d+1)log⁡(h+1)}(d≠∞),ϕh(∞)=0.\phi_h(d) = \max\Bigl\{0,\; 1 - \frac{\log(d+1)}{\log(h+1)}\Bigr\} \quad (d \ne \infty), \qquad \phi_h(\infty) = 0.(6)✦

The Definition

Definition 1. Let (Li)i∈ι(L_i)_{i \in \iota} be a family of label maps on a set XX, let 𝒯\mathcal T be a finite family of finite subsets of ι\iota, and let hh be a natural number. The column index set is Y=X×𝒯,Y = X \times \mathcal T,(7)✦ the column of (v,T)∈Y(v,T) \in Y is the real function on XX given by g(v,T)(x)=ϕh(dT(x,v)),g_{(v,T)}(x) = \phi_h\bigl(d_T(x,v)\bigr),(8)✦ and the row of a point xx of XX is the vector Rx=(gy(x))y∈Y∈ℝY.R_x = \bigl(g_y(x)\bigr)_{y \in Y} \in \mathbb R^Y.(9)✦

In the paper, the result reads: label maps Li:X→ΣiL_i : X \to \Sigma_i, i∈[u]i \in [u], with at most qq realized labels each; a family 𝒯\mathcal T of subsets TT of [u][u] with |[u]\T|≤θu|[u] \setminus T| \le \theta u for a parameter θ\theta; for T∈𝒯T \in \mathcal T the graph joining distinct xx and zz when Li(x)=Li(z)L_i(x) = L_i(z) for some i∈Ti \in T, with graph distance dTd_T, equal to ∞\infty between components; ϕh(d)=max⁡{0,1−log⁡(d+1)/log⁡(h+1)}\phi_h(d) = \max\{0, 1 - \log(d+1)/\log(h+1)\} with ϕh(∞)=0\phi_h(\infty) = 0; Y=X×𝒯Y = X \times \mathcal T and g(v,T)(x)=ϕh(dT(x,v))g_{(v,T)}(x) = \phi_h(d_T(x,v)); and fλ=∑yλygyf_\lambda = \sum_{y} \lambda_y g_y for λ∈ℝY\lambda \in \mathbb R^Y.

What Is Checked

The definition is stated over a set XX with label maps LiL_i indexed by ι\iota, a finite family 𝒯\mathcal T of finite subsets of ι\iota and a natural number hh, through the partition graphs GTG_T of (3), their distances dTd_T of (4) and the logarithmic profile ϕh\phi_h of (6).

About these constructions the library proves one further fact: a map ff from a finite set XX to any set, taking at most qq values, has an injection of its value set f(X)f(X) into [q][q].✦