OctoInformBeta

OpenAI preprint, September 2026 · §5. Choice of parameters and failure of duality · §5

§5 (proof of Theorem 1.1): assembly: For a≥1a \ge 1, r≥1r \ge 1 and B>0B > 0, a symmetric convex body KK has log⁡N(L∘,a−1K∘)/log⁡N(K,L)<2h2s/(r+h−1)+2/B\log N(L^\circ, a^{-1}K^\circ)/\log N(K, L) < 2h^2s/(r+h-1) + 2/B, LL the cube

Symmetric convex bodies with arbitrarily small entropy ratio.

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

The duality conjecture for metric entropy asks for absolute constants a,b≥1a, b \ge 1 such that any two symmetric convex bodies KK and LL in ℝn\mathbb{R}^n, in every dimension nn, satisfy log⁡N(K,L)≤blog⁡N(L∘,a−1K∘)\log N(K, L) \le b \log N(L^\circ, a^{-1}K^\circ), with N(K,L)N(K, L) the covering number of KK by translates of LL and K∘K^\circ the polar body of KK. This item fixes a≥1a \ge 1, takes LL to be the cube [−1,1]n[-1,1]^n, and gives bodies KK for which the quotient log⁡N(L∘,a−1K∘)/log⁡N(K,L)\log N(L^\circ, a^{-1}K^\circ)/\log N(K, L) is as small as one likes, so that no constant bb serves for this aa. The library records such a body, with its dimension, as an entropy pair.

Covering Numbers and Polars

The real space ℝι\mathbb{R}^\iota over an index set ι\iota is the set of functions from ι\iota to ℝ\mathbb{R}.✦ For finite ι\iota, the pairing of two of its points is ⟨x,y⟩=∑ixiyi\langle x, y \rangle = \sum_i x_i y_i✦, and the polar K∘K^\circ of a subset KK of ℝι\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 \le 1 \text{ for every } x \in K \}.(1)✦ The cube [−1,1]ι[-1,1]^\iota is the set of points all of whose coordinates have absolute value at most 11.✦ The unit ℓ1\ell^1 ball B1ιB_1^\iota is the set of points xx whose ℓ1\ell^1 norm ∥x∥1=∑i|xi|\|x\|_1 = \sum_i |x_i| is at most 11.✦ A symmetric convex body in ℝι\mathbb{R}^\iota is a compact convex subset KK with nonempty interior and K=−KK = -K.✦

For subsets SS and TT of ℝι\mathbb{R}^\iota, the translates of TT by centers c1,…,cM∈ℝιc_1, \dots, c_M \in \mathbb{R}^\iota cover SS when every x∈Sx \in S has x−cj∈Tx - c_j \in T for some jj✦, and SS is coverable by TT when some finite family of centers does this.✦ The covering number N(S,T)N(S, T) of SS by TT is the least number of centers, placed anywhere in ℝι\mathbb{R}^\iota, whose translates of TT cover SS, and 00 when no finite family does: N(S,T)=min⁡{M:S⊆⋃j=1M(cj+T) for some c1,…,cM∈ℝι}.N(S, T) = \min \Bigl\{ M : S \subseteq \bigcup_{j=1}^{M} (c_j + T) \text{ for some } c_1, \dots, c_M \in \mathbb{R}^\iota \Bigr\}.(2)✦

Matrices and Uniform Approximation

A matrix with rows indexed by a set XX and columns indexed by a finite set YY is given by its columns gy∈ℝXg_y \in \mathbb{R}^X; its row RxR_x is the vector (gy(x))y∈Y(g_y(x))_{y \in Y}, and the column combination with coefficients λ∈ℝY\lambda \in \mathbb{R}^Y is fλ=∑yλygy∈ℝXf_\lambda = \sum_y \lambda_y g_y \in \mathbb{R}^X. Two functions f,f′∈ℝXf, f' \in \mathbb{R}^X are uniformly ε\varepsilon-close when |f(x)−f′(x)|≤ε|f(x) - f'(x)| \le \varepsilon for every x∈Xx \in X.✦ A uniform ε\varepsilon-approximation for gg is a finite set A⊂ℝXA \subset \mathbb{R}^X such that every fλf_\lambda with λ∈B1Y\lambda \in B_1^Y is uniformly ε\varepsilon-close to some point of AA, which need not itself be a combination of the columns.✦

The Parameters

Fix a≥1a \ge 1 and a rank r≥1r \ge 1, the number of variables of the forms considered below. The accuracy parameter θ\theta, the number ss of pivot slots and the compression radius hh depend on aa alone: θ=11000a,s=⌈1/θ⌉,h=⌈exp⁡(log⁡3/θ)⌉+1.\theta = \frac{1}{1000a}, \qquad s = \lceil 1/\theta \rceil, \qquad h = \lceil \exp(\log 3/\theta) \rceil + 1.(3) The form dimension DjD_j, the number uu of directions and the encoding cost CC depend on rr as well: Dj=(r+j−1j),u=⌈2hDhθ⌉,C=log⁡u+hs2ulog⁡(1+s2uθ).D_j = \binom{r+j-1}{j}, \qquad u = \Bigl\lceil \frac{2hD_h}{\theta} \Bigr\rceil, \qquad C = \log u + hs2^u \log\Bigl(1 + \frac{s2^u}{\theta}\Bigr).(4) Here DjD_j counts the multisets of size jj drawn from rr indices, the dimension of the space of forms of degree jj in rr variables over a prime field 𝔽p\mathbb{F}_p.✦

Entropy Pairs

The entropy ratio ρa(K)\rho_a(K) of a subset KK of ℝι\mathbb{R}^\iota, for finite ι\iota, at a real number aa is, with L=[−1,1]ιL = [-1,1]^\iota, ρa(K)=log⁡N(L∘,a−1K∘)log⁡N(K,L).\rho_a(K) = \frac{\log N(L^\circ, a^{-1}K^\circ)}{\log N(K, L)}.(5)✦ The entropy budget β(a,r,B)\beta(a, r, B) of a real number aa, a natural number rr and a real number BB is, with hh and ss as in (3), β(a,r,B)=2h2sr+h−1+2B.\beta(a, r, B) = \frac{2h^2 s}{r + h - 1} + \frac{2}{B}.(6)✦

An entropy pair with parameters aa, rr and BB is a dimension n≥1n \ge 1 with n≥rn \ge r together with a symmetric convex body KK in ℝn\mathbb{R}^n such that, for the cube L=[−1,1]nL = [-1,1]^n, itself a symmetric convex body, KK is coverable by LL, L∘L^\circ is coverable by a−1K∘a^{-1}K^\circ, N(K,L)>1N(K, L) > 1, N(L∘,a−1K∘)≥1N(L^\circ, a^{-1}K^\circ) \ge 1 and 0≤ρa(K)<β(a,r,B)0 \le \rho_a(K) < \beta(a, r, B).✦

From a Matrix to an Entropy Pair

Let a≥1a \ge 1, r≥1r \ge 1 and B>0B > 0, with θ\theta, ss, hh, DjD_j and CC as in (3) and (4), and let pp be a prime with exp⁡(BC/Dh)<p\exp(BC/D_h) < p. Let gg be a matrix with rows indexed by a finite set XX of size pDhp^{D_h} and columns indexed by a finite set YY with |X|≤|Y||X| \le |Y|, whose distinct rows satisfy ∥Rx−Rx′∥∞≥1\|R_x - R_{x'}\|_\infty \ge 1. If a uniform 6θ6\theta-approximation AA for gg and a natural number QQ satisfy |A|≤Q2,log⁡Q≤hslog⁡(pDh−1)+C,|A| \le Q^2, \qquad \log Q \le hs \log\bigl(p^{D_{h-1}}\bigr) + C,(7)✦ then there is an entropy pair with parameters aa, rr and BB.

For natural numbers rr, hh, ss, pp and QQ with r,h≥1r, h \ge 1 and p>1p > 1, and a real number CC with log⁡Q≤hslog⁡(pDh−1)+C\log Q \le hs \log\bigl(p^{D_{h-1}}\bigr) + C, log⁡(Q2)log⁡(pDh)≤2h2sr+h−1+2CDhlog⁡p;\frac{\log(Q^2)}{\log\bigl(p^{D_h}\bigr)} \le \frac{2h^2 s}{r+h-1} + \frac{2C}{D_h \log p};(8)✦ if moreover b≥1b \ge 1, C≥0C \ge 0, 8bh2s<r+h−18bh^2 s < r + h - 1 and exp⁡(8bC/Dh)<p\exp(8bC/D_h) < p, then log⁡(Q2)log⁡(pDh)<12b.\frac{\log(Q^2)}{\log\bigl(p^{D_h}\bigr)} < \frac{1}{2b}.(9)✦

For real numbers ν\nu, mm, μ\mu, QQ and bb with 1<m≤ν1 < m \le \nu, 1≤μ≤Q21 \le \mu \le Q^2, b≥1b \ge 1 and log⁡(Q2)/log⁡m<1/(2b)\log(Q^2)/\log m < 1/(2b), blog⁡μ<log⁡ν,b \log \mu < \log \nu,(10)✦ it applies with ν=N(K,L)\nu = N(K, L) and μ=N(L∘,a−1K∘)\mu = N(L^\circ, a^{-1}K^\circ).

The Claim

Theorem 1. Let a≥1a \ge 1 and B>0B > 0 be real numbers and r≥1r \ge 1 a natural number, and let hh and ss be the compression radius and the number of pivot slots of aa. Then there is an entropy pair with parameters aa, rr and BB; its body KK, in a dimension n≥rn \ge r, satisfies, with L=[−1,1]nL = [-1,1]^n, log⁡N(L∘,a−1K∘)log⁡N(K,L)<2h2sr+h−1+2B.\frac{\log N(L^\circ, a^{-1}K^\circ)}{\log N(K, L)} < \frac{2h^2 s}{r+h-1} + \frac{2}{B}.(11)✦

In the paper, the result reads: the matrix of Proposition 4.3, put into Lemma 2.1 with ε=6θ\varepsilon = 6\theta and t=θt = \theta, gives N(K,L)≥pDhN(K, L) \ge p^{D_h} and N(L∘,a−1K∘)≤Q2N(L^\circ, a^{-1}K^\circ) \le Q^2, and log⁡(Q2)/log⁡m<1/(2b)\log(Q^2)/\log m < 1/(2b) for m=pDhm = p^{D_h}, whence Theorem 1.1.

What Is Checked

The claim (11) is stated over entropy pairs, which rest on symmetric convex bodies, the cube [−1,1]n[-1,1]^n and its polar (1), covering numbers (2) with finite covers, the entropy ratio (5) and the entropy budget (6), with the parameters θ\theta, ss and hh of (3). About these constructions the library also states the passage (7) from a matrix whose distinct rows are at distance at least 11 in the sup norm, together with a uniform approximation, to an entropy pair, the bounds (8) and (9) on log⁡(Q2)/log⁡(pDh)\log(Q^2)/\log\bigl(p^{D_h}\bigr), and the comparison (10).