OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

§1 (setting): covering numbers, polars and convex bodies: The least number N(A,B)N(A,B) of translates of BB that cover AA, symmetric convex bodies, and the polar of the cube, the ℓ1\ell_1 ball

Covering numbers and polars of sets in real space.

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 KK and LL be symmetric convex bodies in ℝn\mathbb{R}^n. The duality conjecture for metric entropy compares, at every scale t>0t > 0, the number of translates of tLtL needed to cover KK with the number of translates of tK∘tK^\circ needed to cover L∘L^\circ, where K∘K^\circ and L∘L^\circ are the polar bodies.

The library defines these notions in the real space of functions on an index set, together with the cube and the ℓ1\ell_1 ball, and computes one polar, that of the cube.

The Claim

Definition 1. Let ι\iota be an index set. The real space ℝι\mathbb{R}^\iota is the vector space of functions x:ι→ℝx : \iota \to \mathbb{R}, with coordinates xix_i; it is ℝn\mathbb{R}^n when ι\iota has nn elements.✦ The cube in ℝι\mathbb{R}^\iota is the set B∞ι=[−1,1]ι={x∈ℝι:|xi|≤1 for every i∈ι}B_\infty^\iota = [-1,1]^\iota = \{x \in \mathbb{R}^\iota : |x_i| \le 1 \text{ for every } i \in \iota\}.

Let AA and BB be subsets of ℝι\mathbb{R}^\iota. A family of points x1,…,xMx_1, \dots, x_M of ℝι\mathbb{R}^\iota covers AA by BB when A⊆⋃j=1M(xj+B).A \subseteq \bigcup_{j=1}^{M} (x_j + B).(1)✦ The set AA is coverable by BB when some finite family of points covers it by BB: A⊆⋃j=1M(xj+B)for some M≥0 and some x1,…,xM∈ℝι.A \subseteq \bigcup_{j=1}^{M} (x_j + B) \quad \text{for some } M \ge 0 \text{ and some } x_1, \dots, x_M \in \mathbb{R}^\iota.(2)✦ The covering number N(A,B)N(A,B) of AA by BB is the least number MM of points in a finite family of points of ℝι\mathbb{R}^\iota that covers AA by BB, N(A,B)=min⁡{M≥0:A⊆⋃j=1M(xj+B) for some x1,…,xM∈ℝι},N(A,B) = \min \Bigl\{ M \ge 0 : A \subseteq \bigcup_{j=1}^{M} (x_j + B) \text{ for some } x_1, \dots, x_M \in \mathbb{R}^\iota \Bigr\},(3)✦ and N(A,B)=0N(A,B) = 0 when AA is not coverable by BB.

Let now ι\iota be finite. The pairing of two points xx and yy of ℝι\mathbb{R}^\iota is the number ⟨x,y⟩=∑i∈ιxiyi,\langle x, y \rangle = \sum_{i \in \iota} x_i y_i,(4)✦ and the polar 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 \}.(5)✦ A symmetric convex body in ℝι\mathbb{R}^\iota is a compact convex subset KK of ℝι\mathbb{R}^\iota with nonempty interior that is symmetric about the origin: x∈K⇔−x∈Kfor every x∈ℝι.x \in K \iff -x \in K \qquad \text{for every } x \in \mathbb{R}^\iota.(6)✦ The ℓ1\ell_1 norm of a point xx of ℝι\mathbb{R}^\iota is the number ∥x∥1=∑i∈ι|xi|,\|x\|_1 = \sum_{i \in \iota} |x_i|,(7)✦ and the ℓ1\ell_1 ball in ℝι\mathbb{R}^\iota is the set B1ι={x∈ℝι:∥x∥1≤1}B_1^\iota = \{x \in \mathbb{R}^\iota : \|x\|_1 \le 1\}.✦

Theorem 1. For a finite index set ι\iota, the polar of the cube is the ℓ1\ell_1 ball: (B∞ι)∘=B1ι.(B_\infty^\iota)^\circ = B_1^\iota.(8)✦

In the paper, the result reads: for bounded A,B⊆ℝnA, B \subseteq \mathbb{R}^n with BB of nonempty interior, N(A,B)N(A,B) is the least number of translates of BB, with centers anywhere in ℝn\mathbb{R}^n, that cover AA; K∘={y:⟨x,y⟩≤1 for every x∈K}K^\circ = \{y : \langle x, y \rangle \le 1 \text{ for every } x \in K\}; a convex body is compact with nonempty interior; and B∞ι=[−1,1]ιB_\infty^\iota = [-1,1]^\iota while B1ιB_1^\iota is the unit ball of the ℓ1\ell_1 norm.

What Is Checked

These definitions are stated over subsets of the real space ℝι\mathbb{R}^\iota, with ι\iota any index set for the cube and for covers (1), coverability (2) and covering numbers (3), and a finite one from the pairing (4) on, and what the library records about them is the identity (8).