OctoInformBeta

A counterexample to metric-entropy duality

For bounded sets A,BA,B in a finite-dimensional real vector space, with BB of nonempty interior, the covering number N(A,B)N(A,B) is the least number of translates of BB, centered anywhere in the space, that cover AA. A convex body is a compact convex set with nonempty interior. The polar of an origin-symmetric convex body K⊂ℝnK\subset\mathbb{R}^n is K∘={y∈ℝn:⟨x,y⟩≤1 for every x∈K}K^\circ=\{y\in\mathbb{R}^n:\langle x,y\rangle\le1\text{ for every }x\in K\}. The duality conjecture for metric entropy asks whether there are absolute constants a,b≥1a,b\ge1 such that 1blog⁡N(L∘,aK∘)≤log⁡N(K,L)≤blog⁡N(L∘,a−1K∘)\frac1b\log N(L^\circ,aK^\circ)\le\log N(K,L)\le b\log N(L^\circ,a^{-1}K^\circ) for every nn and every pair of origin-symmetric convex bodies K,L⊂ℝnK,L\subset\mathbb{R}^n.

The conjecture developed from the duality problem for entropy numbers of operators, which Artstein, Milman and Szarek attribute to Pietsch’s work of 1972. In the form above it is Conjecture 1 of Artstein, Milman, Szarek and Tomczak-Jaegermann. König and Milman proved a comparison of the nnth roots of N(K,L)N(K,L) and N(L∘,K∘)N(L^\circ,K^\circ). On the logarithmic scale it allows an additive error proportional to nn. Artstein, Milman and Szarek proved the conjecture when one of the two bodies is a Euclidean ball. The convexified packing number M̂(T,B)\widehat M(T,B) of a bounded set TT with respect to an origin-symmetric convex body BB is the largest length of a sequence x1,…,xm∈Tx_1,\ldots,x_m\in T in which each translate xj+int⁡Bx_j+\operatorname{int}B avoids the convex hull of x1,…,xj−1x_1,\ldots,x_{j-1}. Artstein, Milman, Szarek and Tomczak-Jaegermann proved the duality with universal constants for convexified packing numbers in place of covering numbers.

The main theorem of the preprint refutes the right-hand inequality for every choice of the constants, already when LL is a cube: for every a,b≥1a,b\ge1 there are a positive integer nn and an origin-symmetric convex body K⊂ℝnK\subset\mathbb{R}^n such that, with L=[−1,1]nL=[-1,1]^n, log⁡N(K,L)>blog⁡N(L∘,a−1K∘)\log N(K,L)>b\log N(L^\circ,a^{-1}K^\circ). The preprint also proves an asymptotic form for fixed a≥1a\ge1: there is a sequence of origin-symmetric convex bodies Kr⊂ℝnrK_r\subset\mathbb{R}^{n_r} with nr→∞n_r\to\infty such that, with Lr=[−1,1]nrL_r=[-1,1]^{n_r}, the ratio log⁡N(Lr∘,a−1Kr∘)/log⁡N(Kr,Lr)\log N(L_r^\circ,a^{-1}K_r^\circ)/\log N(K_r,L_r) tends to 00 as r→∞r\to\infty. From the main theorem the preprint derives that for every A,C≥1A,C\ge1 there are a positive integer nn and an origin-symmetric convex body K⊂ℝnK\subset\mathbb{R}^n with log⁡N(K,L)>Clog⁡M̂(K,L/A)\log N(K,L)>C\log\widehat M(K,L/A) for L=[−1,1]nL=[-1,1]^n, a consequence the Lean library does not contain.

The Lean library MetricEntropy proves the main theorem with no hypothesis beyond a,b≥1a,b\ge1. It proves the asymptotic form with no hypothesis beyond a≥1a\ge1. The results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference: where the preprint states a result differently, the statement on a page is the Lean library’s, with the preprint’s beside it. The preprint is a guide only, which gives the results their order and their names.

The Lean library: MetricEntropy

MetricEntropy is a Lean library: 17 items, in five groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): covering numbers, polars and convex bodies Covering numbers and polars of sets in real space. §1
  2. Theorem 1.1 [main theorem] The duality conjecture for metric entropy fails. §1
§2. The matrix construction target 2 items
  1. Lemma 2.1 [Matrix-to-body conversion] Converting a matrix into a convex body with covering bounds. §2
  2. §2 (displayed): enlarging the polar scale Larger dilates of a polar body need no more translates. §2
§3. Uniform compression from partitions 5 items
  1. §3 (setting): partition graphs, the logarithmic profile and the columns Matrix columns from logarithmic bumps on partition graphs. §3
  2. Lemma 3.1 [Logarithmic profile] The logarithmic profile is an average of ball indicators. §3
  3. Proposition 3.2 [Uniform compression] A small list approximates every mixture of graph profiles. §3
  4. §3 (proof of Proposition 3.2): common index, pivots, levels, rounding The steps that compress a mixture of graph distance profiles. §3
  5. Corollary 3.3 [Signed compression] Differences of a positive list cover the absolutely convex hull. §3
§4. Finite-field partitions and separated rows 5 items
  1. Lemma 4.1 [Polynomial zero bound] A nonzero polynomial of low degree over 𝔽p\mathbb{F}_p has few zeros. §4
  2. §4 (setting): symmetric forms and their dimension Symmetric forms correspond to functions on multisets. §4
  3. Proposition 4.2 [Directions with nonvanishing evaluations] Directions on which no nonzero form vanishes after few deletions. §4
  4. Proposition 4.3 [Partitions with separated rows] Rows of distinct symmetric forms lie at sup distance one. §4
  5. §4 (displayed): the dimension ratio The dimension ratio Dh−1/DhD_{h-1}/D_h of symmetric forms is h/(r+h−1)h/(r+h-1). §4
§5. Choice of parameters and failure of duality 3 items
  1. §5 (setting): the parameters The counterexample’s parameters can be chosen, the prime last. §5
  2. §5 (proof of Theorem 1.1): assembly Symmetric convex bodies with arbitrarily small entropy ratio. §5
  3. §5 (displayed): the asymptotic form Symmetric convex bodies with entropy ratio tending to zero. §5

No item matches.