# Compression by partitions

*Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).*

The matrix of [Covering numbers and polar bodies](covering-numbers-and-polar-bodies.md) needs columns all of whose signed combinations of \(\ell^1\)-norm at most \(1\) can be approximated, in the maximum norm over the rows, by a short list of functions. This lesson constructs such columns from finitely many partitions of the row set [OpenAI-E, Section 3]. Each column is a function of a graph distance to a centre, decreasing logarithmically with the distance. The point is that the length of the approximation list depends on the number of classes of the partitions, not on the number of rows: in an approximant, every centre is replaced by a *label*, the class of a pivot point in one of the partitions. Replacing a point by its label moves it by at most one step in the graph, which enlarges distances from \(j\) to at most \(3j+2\), and the logarithmic profile makes the cost of this enlargement small.

The lesson is self-contained apart from elementary counting.

## 1. Partitions, graphs and profiles

Let \(X\) be a finite nonempty set, \(u,q\) positive integers and \([u]=\{1,\dots,u\}\). For each \(i\in[u]\) let \(L_i:X\to\Sigma_i\) be a map taking at most \(q\) values (the *labels*); its fibres form a partition of \(X\) into at most \(q\) classes. Fix \(0<\theta<1\) and a nonempty family \(\mathcal T\) of subsets of \([u]\) with
\[
\begin{gathered}
|[u]\setminus T|\le\theta u\\
(T\in\mathcal T).
\end{gathered}\tag{1.1}
\]
For \(T\in\mathcal T\), join distinct \(x,z\in X\) by an edge if \(L_i(x)=L_i(z)\) for some \(i\in T\), and let \(d_T(x,z)\in\{0,1,2,\dots\}\cup\{\infty\}\) be the graph distance (\(\infty\) between different components). It satisfies the triangle inequality.

Fix a positive integer \(h\) with
\[
\begin{gathered}
\frac{\log3}{\log(h+1)}\le\theta,\\
\text{and put}\quad s=\lceil1/\theta\rceil.
\end{gathered}\tag{1.2}
\]
The *logarithmic profile* is \(\phi_h(d)=\max\{0,1-\frac{\log(d+1)}{\log(h+1)}\}\) for \(d=0,1,2,\dots\) and \(\phi_h(\infty)=0\). Let \(Y=X\times\mathcal T\), and for \(y=(v,T)\in Y\) define the column
\[
\begin{gathered}
g_y(x)=\phi_h\bigl(d_T(x,v)\bigr)\in[0,1]\\
(x\in X).
\end{gathered}
\]

**Lemma 1.1** (the profile as a sum of balls). The numbers \(\gamma_j=\frac{\log(j+2)-\log(j+1)}{\log(h+1)}\), \(0\le j<h\), are positive and sum to \(1\), and for every \(d\in\{0,1,2,\dots\}\cup\{\infty\}\)
the relations (1.3) hold:
\[
\begin{aligned}
\phi_h(d)&=\sum_{j=0}^{h-1}\gamma_j\mathbf1_{\{d\le j\}},\\
\sum_{j=0}^{h-1}\gamma_j\mathbf1_{\{d\le3j+2\}}&\le\phi_h(d)\\
&\quad+\frac{\log3}{\log(h+1)}.
\end{aligned}
\]

**Proof.** The sum of the \(\gamma_j\) telescopes to \(\frac{\log(h+1)}{\log(h+1)}=1\). For \(0\le d<h\), the first sum runs over \(j=d,\dots,h-1\) and telescopes to \(\frac{\log(h+1)-\log(d+1)}{\log(h+1)}=\phi_h(d)\); for \(d\ge h\) both sides vanish. In the second sum, the indices not counted by \(\phi_h(d)\) are those with \(j<d\le3j+2\). For finite \(d\) they form the integers from \(a=\lceil\frac{d+1}3\rceil-1\ge0\) to \(b=\min\{h-1,d-1\}\), with total weight \(\frac1{\log(h+1)}\log\frac{b+2}{a+1}\), and \(b+2\le d+1\le3(a+1)\). For \(d=\infty\) all indicators vanish. \(\square\)

## 2. Uniform compression

For nonnegative \(\mu\in\mathbb R^Y\) with \(\sum_y\mu_y\le1\) put \(f_\mu=\sum_y\mu_yg_y\), and let \(\mathcal F_+\) be the set of these functions. For \(S\subseteq Y\) write \(\mu(S)=\sum_{y\in S}\mu_y\).

**Proposition 2.1** (uniform compression). There is a list \(\mathcal A\) of \(Q\) real functions on \(X\) such that every \(f\in\mathcal F_+\) has some \(A\in\mathcal A\) satisfying, for all \(x\in X\), the inequalities (2.1):
\[
f(x)-3\theta\le A(x)\le f(x)+\theta,
\]
and such that the bound (2.2) holds:
\[
\begin{aligned}
\log Q&\le hs\log q+C_{h,\theta,u},\\
C_{h,\theta,u}&=\log u\\
&\quad+hs2^u\log\Bigl(1+\frac{s2^u}\theta\Bigr).
\end{aligned}
\]

**Proof.** Fix once and for all, for each \(i\), a map \(\rho_i\) from the labels of \(L_i\) to \(X\) with \(L_i(\rho_i(\sigma))=\sigma\): a representative of each class.

*One partition for most of the mass.* Let \(f=f_\mu\). By (1.1),
\[
\begin{aligned}
&\frac1u\sum_{i=1}^u\mu\{(v,T):i\notin T\}\\
&\quad =\sum_{(v,T)\in Y}\mu_{(v,T)}\frac{|[u]\setminus T|}u\le\theta,
\end{aligned}
\]
so some \(i_0\in[u]\) has \(\mu\{(v,T):i_0\notin T\}\le\theta\). Put \(Y_0=\{(v,T)\in Y:i_0\in T\}\).

*Few pivots at each level.* Fix \(j\in\{0,\dots,h-1\}\) and let \(I_x=\{(v,T)\in Y_0:d_T(x,v)\le j\}\) for \(x\in X\). Starting from \(U=\varnothing\), as long as some \(I_z\) has \(\mu(I_z\setminus U)>\theta\), choose such a \(z\) and replace \(U\) by \(U\cup I_z\). Each step adds mass more than \(\theta\), and the total mass is at most \(1\), so there are \(k_j<1/\theta\) steps, hence \(k_j\le s\). The result is a set of pivots \(z_{j,1},\dots,z_{j,k_j}\) and \(U_j=\bigcup_kI_{z_{j,k}}\) with
\[
\begin{gathered}
\mu(I_x\setminus U_j)\le\theta\\
(x\in X).
\end{gathered}\tag{2.3}
\]
Assign each \(y\in U_j\) to the first pivot \(z_{j,k}\) with \(y\in I_{z_{j,k}}\), and write \(k=\kappa_j(y)\).

*Replacing pivots by labels.* For a pivot \(z\), let \(z'=\rho_{i_0}(L_{i_0}(z))\). Then \(L_{i_0}(z')=L_{i_0}(z)\), so \(d_T(z,z')\le1\) for every \(T\) containing \(i_0\). If \(y=(v,T)\) is assigned to \(z\), then \(i_0\in T\) and \(d_T(v,z)\le j\), so \(d_T(v,z')\le j+1\), and for every \(x\in X\) the implications (2.4) hold: if \(d_T(x,v)\le j\), then \(d_T(x,z')\le2j+1\); if \(d_T(x,z')\le2j+1\), then \(d_T(x,v)\le3j+2\).
Writing \(z'_{j,k}\) for the replacement of \(z_{j,k}\), define
\[
\begin{gathered}
A_j(x)=\sum_{y=(v,T)\in U_j}\mu_y\mathbf1_{\{d_T(x,z'_{j,\kappa_j(y)})\le2j+1\}},\\
f_{\mu,j}(x)=\sum_{y=(v,T)\in Y}\mu_y\mathbf1_{\{d_T(x,v)\le j\}}.
\end{gathered}
\]
A column counted in \(f_{\mu,j}(x)\) is either in \(U_j\), and then counted in \(A_j(x)\) by (2.4), or outside \(Y_0\) (mass at most \(\theta\)), or in \(I_x\setminus U_j\) (mass at most \(\theta\) by (2.3)). A column counted in \(A_j(x)\) has \(d_T(x,v)\le3j+2\) by (2.4). Hence the inequalities (2.5) hold:
\[
\begin{aligned}
f_{\mu,j}(x)-2\theta&\le A_j(x)\\
&\le\sum_{y=(v,T)}\mu_y\mathbf1_{\{d_T(x,v)\le3j+2\}}.
\end{aligned}
\]

*Combining the levels.* Let \(F=\sum_j\gamma_jA_j\). By (1.3), \(f_\mu=\sum_j\gamma_jf_{\mu,j}\), so (2.5) gives \(F\ge f_\mu-2\theta\); and summing the second part of (1.3) over the columns with weights \(\mu_y\), with \(\frac{\log3}{\log(h+1)}\le\theta\) and \(\sum_y\mu_y\le1\), gives \(F\le f_\mu+\theta\).

*Encoding.* The centre \(v\) of a column does not appear in \(A_j\). Grouping the columns by their slot \(k\) and their set \(T\),
\[
\begin{gathered}
A_j(x)=\sum_{k=1}^s\sum_{T\in\mathcal T}w_{j,k,T}\mathbf1_{\{d_T(x,z'_{j,k})\le2j+1\}},\\
w_{j,k,T}=\sum_{v:\ (v,T)\in U_j,\ \kappa_j(v,T)=k}\mu_{(v,T)}\in[0,1],
\end{gathered}
\]
where unused slots get weight \(0\) and an arbitrary fixed label. There are at most \(M_0=s2^u\) weights per level. Round each weight down to a multiple of \(\delta=\theta/M_0\), call the resulting functions \(\widetilde A_j\), and put \(A=\sum_j\gamma_j\widetilde A_j\). Since the indicators are at most \(1\), \(0\le A_j-\widetilde A_j\le M_0\delta=\theta\), so \(0\le F-A\le\theta\), and (2.1) follows.

*Counting.* \(A\) is determined by \(i_0\), the \(hs\) labels \(L_{i_0}(z_{j,k})\) (the points \(z'_{j,k}\) are recovered through \(\rho_{i_0}\)), and the at most \(hM_0\) rounded weights, each taking at most \(1+M_0/\theta\) values. Listing all such data, whether or not they arise from some \(\mu\), gives a list of length at most \(u\,q^{hs}(1+\frac{s2^u}\theta)^{hs2^u}\), which is (2.2). \(\square\)

The partitions, the graphs, the family \(\mathcal T\) and the representatives \(\rho_i\) are fixed before the list is formed; only \(i_0\), the labels and the weights depend on \(\mu\). Nothing is assumed about the separation of the rows.

**Corollary 2.2** (signed compression). There is a list of at most \(Q^2\) functions on \(X\) such that every \(f_\lambda=\sum_y\lambda_yg_y\) with \(\sum_y|\lambda_y|\le1\) lies within \(6\theta\) of one of them in the maximum norm.

**Proof.** Write \(\lambda=\lambda^+-\lambda^-\) with \(\lambda^\pm_y=\max\{\pm\lambda_y,0\}\). Both parts are nonnegative with mass at most \(1\), so Proposition 2.1 gives \(A^\pm\in\mathcal A\) with \(\max_X|f_{\lambda^\pm}-A^\pm|\le3\theta\). Then \(A^+-A^-\) is within \(6\theta\) of \(f_\lambda\), and there are at most \(Q^2\) differences. \(\square\)

## 3. Exercises

**Exercise 3.1** (easy). Show that \(\phi_h\) is nonincreasing, \(\phi_h(0)=1\) and \(\phi_h(d)=0\) for \(d\ge h\).

**Exercise 3.2** (medium). Replace the logarithmic profile by the linear profile \(\psi_h(d)=\max\{0,1-d/h\}\). Show that the analogue of the second inequality in (1.3) then holds only with an error close to \(\frac23\) for some \(d\), and explain why the argument needs the logarithm.

**Exercise 3.3** (easy). Check that the number of steps in the greedy choice of pivots satisfies \(k_j\le s\), even when \(1/\theta\) is an integer.

## 4. Solutions

**3.1.** \(\log(d+1)\) is increasing, \(\log1=0\), and \(\log(d+1)\ge\log(h+1)\) for \(d\ge h\).

**3.2.** For \(\psi_h=\sum_{j<h}\frac1h\mathbf1_{\{d\le j\}}\) the extra indices \(j<d\le3j+2\) have weight about \(\frac1h\cdot\frac{2d}3\) for \(d\le h\), which is close to \(\frac23\) when \(d\) is close to \(h\). The dilation \(j\mapsto3j+2\) multiplies scales by about \(3\), and only a weight that is uniform in \(\log j\) charges each dyadic-type range \([j,3j+2]\) by the same small amount \(\frac{\log3}{\log(h+1)}\).

**3.3.** After \(k\) steps the union has mass greater than \(k\theta\) and at most \(1\), so \(k<1/\theta\le s\).

## References

- [OpenAI-E] OpenAI, *Counterexamples to the duality conjecture for metric entropy*, OpenAI Math Release preprint, 24 September 2026, Section 3. https://github.com/openai/math/blob/main/preprints/Counterexamples-to-the-duality-conjecture-for-metric-entropy-September-24-2026