OctoInformBeta

OpenAI preprint, September 2026 · §2. The matrix construction target · §2

Lemma 2.1 [Matrix-to-body conversion]: For t>0t>0, 11-separated rows and a uniform ε\varepsilon-approximation list of MM functions give N(Kt,B∞Y)≥|X|N(K_t,B_\infty^Y)\ge|X| and N(B1Y,(6ε+2t)Kt∘)≤MN(B_1^Y,(6\varepsilon+2t)K_t^\circ)\le M

Converting a matrix into a convex body with covering bounds.

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 finite sets XX and YY and a real matrix gg with rows indexed by XX and columns indexed by YY, given by its columns gy:X→ℝg_y\colon X\to\mathbb{R}. Two properties of gg matter: its rows, as points of ℝY\mathbb{R}^Y, lie far apart in the sup norm, while the combinations ∑yλygy\sum_y\lambda_y g_y with ∑y|λy|≤1\sum_y|\lambda_y|\le1, as functions on XX, all lie uniformly close to members of a short list of functions.

The question is how to read both properties off one symmetric convex body K⊆ℝYK\subseteq\mathbb{R}^Y: the first as a lower bound on the number of translates of the cube needed to cover KK, the second as an upper bound on the number of translates of a multiple of the polar K∘K^\circ of KK needed to cover the polar of the cube. These are the two covering numbers compared by the duality conjecture for metric entropy, with the cube as the second body.

Bodies, Polars and Covering Numbers

For a finite set ι\iota, the space ℝι\mathbb{R}^\iota is the vector space of real functions on ι\iota✦, with the pairing ⟨x,y⟩=∑i∈ιxiyi\langle x,y\rangle=\sum_{i\in\iota}x_iy_i✦, the ℓ1\ell_1 norm ∥x∥1=∑i∈ι|xi|\|x\|_1=\sum_{i\in\iota}|x_i| and the sup norm ∥x∥∞=max⁡i∈ι|xi|\|x\|_\infty=\max_{i\in\iota}|x_i|. The ℓ1\ell_1 unit ball B1ιB_1^\iota is the set of points x∈ℝιx\in\mathbb{R}^\iota with ∥x∥1≤1\|x\|_1\le1✦, and the cube B∞ι=[−1,1]ιB_\infty^\iota=[-1,1]^\iota is the set of points xx with |xi|≤1|x_i|\le1 for every ii.✦

The polar of a set K⊆ℝιK\subseteq\mathbb{R}^\iota is the set K∘={y∈ℝι:⟨x,y⟩≤1 for every x∈K},K^\circ=\{y\in\mathbb{R}^\iota:\langle x,y\rangle\le1\text{ for every }x\in K\},(1)✦ and the polar of the cube B∞ιB_\infty^\iota is B1ιB_1^\iota. The support function of KK is the function hKh_K on ℝι\mathbb{R}^\iota given by hK(δ)=sup⁡z∈K⟨z,δ⟩h_K(\delta)=\sup_{z\in K}\langle z,\delta\rangle.✦ A symmetric convex body in ℝι\mathbb{R}^\iota is a compact convex subset KK of ℝι\mathbb{R}^\iota with nonempty interior such that x∈Kx\in K exactly when −x∈K-x\in K.✦

Translates z1+B,…,zM+Bz_1+B,\dots,z_M+B of a set B⊆ℝιB\subseteq\mathbb{R}^\iota cover a set A⊆ℝιA\subseteq\mathbb{R}^\iota when every x∈Ax\in A has x−zj∈Bx-z_j\in B for some jj, the centers zjz_j being arbitrary points of ℝι\mathbb{R}^\iota.✦ The set AA is finitely coverable by BB when some finite family of translates of BB covers it✦, and the covering number of AA by BB is N(A,B)=min⁡{M≥0:some M translates of B cover A},N(A,B)=\min\{M\ge0:\text{some }M\text{ translates of }B\text{ cover }A\},(2)✦ with N(A,B)=0N(A,B)=0 when AA is not finitely coverable by BB.

Rows, Combinations and the Body

The row of gg at x∈Xx\in X is the point Rx=(gy(x))y∈Y∈ℝY,R_x=\big(g_y(x)\big)_{y\in Y}\in\mathbb{R}^Y,(3)✦ and the combination of the columns of gg with coefficients λ∈ℝY\lambda\in\mathbb{R}^Y is the function fλ=∑y∈Yλygyf_\lambda=\sum_{y\in Y}\lambda_y g_y on XX.✦ For a real number ε\varepsilon, two functions ff and hh on XX are uniformly ε\varepsilon-close when |f(x)−h(x)|≤ε|f(x)-h(x)|\le\varepsilon for every x∈Xx\in X.✦ A uniform ε\varepsilon-approximation list for gg is a finite set AA of real functions on XX such that every combination fλf_\lambda with λ∈B1Y\lambda\in B_1^Y is uniformly ε\varepsilon-close to some member of AA.✦

The absolute convex hull absconv⁡{Rx}\operatorname{absconv}\{R_x\} of the rows of gg is the convex hull in ℝY\mathbb{R}^Y of the rows and their negatives: absconv⁡{Rx}=conv⁡({Rx:x∈X}∪{−Rx:x∈X}).\operatorname{absconv}\{R_x\}=\operatorname{conv}\big(\{R_x:x\in X\}\cup\{-R_x:x\in X\}\big).(4)✦ The matrix body KtK_t of gg at a real parameter tt is the Minkowski sum Kt=3absconv⁡{Rx}+tB∞Y⊆ℝY.K_t=3\operatorname{absconv}\{R_x\}+t\,B_\infty^Y\subseteq\mathbb{R}^Y.(5)✦

The Claim

Theorem 1. Let XX and YY be finite sets with XX nonempty, and let gg be a real matrix with columns gy:X→ℝg_y\colon X\to\mathbb{R}, y∈Yy\in Y, whose rows are 11-separated: ∥Rx−Rx′∥∞≥1\|R_x-R_{x'}\|_\infty\ge1 for all distinct x,x′∈Xx,x'\in X. Let ε≥0\varepsilon\ge0 and t>0t>0, and let AA be a uniform ε\varepsilon-approximation list for gg with MM members. Then KtK_t and B∞YB_\infty^Y are symmetric convex bodies, KtK_t is finitely coverable by B∞YB_\infty^Y, B1YB_1^Y is finitely coverable by (6ε+2t)Kt∘(6\varepsilon+2t)K_t^\circ, and N(Kt,B∞Y)≥|X|,N(B1Y,(6ε+2t)Kt∘)≤M.N(K_t,B_\infty^Y)\ge|X|,\qquad N\big(B_1^Y,(6\varepsilon+2t)K_t^\circ\big)\le M.(6)✦ If YY is nonempty as well, then n=|Y|≥1n=|Y|\ge1, and there is a symmetric convex body K⊆ℝnK\subseteq\mathbb{R}^n, finitely coverable by the cube B∞nB_\infty^n (itself a symmetric convex body), with B1nB_1^n finitely coverable by (6ε+2t)K∘(6\varepsilon+2t)K^\circ and N(K,B∞n)≥|X|,N(B1n,(6ε+2t)K∘)≤M.N(K,B_\infty^n)\ge|X|,\qquad N\big(B_1^n,(6\varepsilon+2t)K^\circ\big)\le M.(7)✦

In the paper, the result reads: for finite nonempty sets XX and YY and functions gyg_y on XX with rows RxR_x and combinations fλf_\lambda, if ∥Rx−Rx′∥∞≥1\|R_x-R_{x'}\|_\infty\ge1 for distinct x,x′x,x' and, for some ε>0\varepsilon>0, a list of MM functions on XX, not necessarily of the form fλf_\lambda, approximates every fλf_\lambda with ∥λ∥1≤1\|\lambda\|_1\le1 within ε\varepsilon uniformly, then for every t>0t>0 the bodies K=KtK=K_t and L=B∞YL=B_\infty^Y are origin-symmetric compact convex bodies with nonempty interior, N(K,L)≥|X|N(K,L)\ge|X| and N(L∘,(6ε+2t)K∘)≤MN(L^\circ,(6\varepsilon+2t)K^\circ)\le M, with translates centered anywhere in ℝY\mathbb{R}^Y.

What Is Checked

The claim is stated over the rows (3) of a real matrix on finite sets, their absolute convex hull (4), the matrix body (5), the cube, the polar (1), the covering number (2) with finite coverability, and uniform ε\varepsilon-approximation lists for the combinations fλf_\lambda.

For XX nonempty and t>0t>0 this holds whatever the matrix: Kt is a symmetric convex body in ℝY.K_t\text{ is a symmetric convex body in }\mathbb{R}^Y.(8)✦ For XX nonempty and t≥0t\ge0 it computes the support function of KtK_t through the row support max⁡x∈X|⟨Rx,δ⟩|\max_{x\in X}|\langle R_x,\delta\rangle| of a point δ∈ℝY\delta\in\mathbb{R}^Y, hKt(δ)=3maxx∈X|⟨Rx,δ⟩|+t∥δ∥1,h_{K_t}(\delta)=3\max_{x\in X}|\langle R_x,\delta\rangle|+t\|\delta\|_1,(9)✦ and describes the multiples of its polar: for every c>0c>0, δ∈cKt∘⇔3maxx∈X|⟨Rx,δ⟩|+t∥δ∥1≤c.\delta\in c\,K_t^\circ\iff3\max_{x\in X}|\langle R_x,\delta\rangle|+t\|\delta\|_1\le c.(10)✦

The lower bound of (6) needs only the separation of the rows, and holds for every real tt: |X|≤N(Kt,B∞Y).|X|\le N(K_t,B_\infty^Y).(11)✦ For ε≥0\varepsilon\ge0 and t>0t>0 the upper bound needs no separation, and it uses only the list AA: N(B1Y,(6ε+2t)Kt∘)≤M.N\big(B_1^Y,(6\varepsilon+2t)K_t^\circ\big)\le M.(12)✦ Such a list also yields coefficient representatives, points c1,…,cMc_1,\dots,c_M of B1YB_1^Y such that every λ∈B1Y\lambda\in B_1^Y has an index jj with |fλ(x)−fcj(x)|≤2ε for every x∈X,∥λ−cj∥1≤2.|f_\lambda(x)-f_{c_j}(x)|\le2\varepsilon\text{ for every }x\in X,\qquad\|\lambda-c_j\|_1\le2.(13)✦