diff 15c9324..65affb3 metric_entropy_duality_counterexamples_v2.txt
diff --git a/metric_entropy_duality_counterexamples_v2.txt b/metric_entropy_duality_counterexamples_v2.txt
index e69de29..ed51e5b 100644
--- a/metric_entropy_duality_counterexamples_v2.txt
+++ b/metric_entropy_duality_counterexamples_v2.txt
@@ -0,0 +1,1626 @@
+METRIC ENTROPY DUALITY: A COUNTEREXAMPLE
+A clear rewrite for high-school readers
+
+0. WHAT THIS DOCUMENT IS
+
+This document explains a research theorem in plain language.
+
+The theorem says that a famous guess about "covering numbers" is false.
+The guess is called the duality conjecture for metric entropy.
+For every proposed pair of universal constants, we build a counterexample.
+
+You do not need to know the research literature to follow the proof.
+You need:
+- vectors in R^n and dot products,
+- the idea of a convex set,
+- logarithms,
+- finite fields F_p, meaning arithmetic modulo a prime p,
+- patience with long formulas.
+
+On a first reading, read Sections 1, 2, 3, and 7.
+The middle sections prove the three tools used in Section 7.
+
+1. THE QUESTION
+
+1.1 Covering numbers
+
+Let A and B be bounded sets in a real vector space.
+Assume B has nonempty interior.
+Let N(A,B) be the smallest number of translates of B needed to cover A.
+
+A translate of B is a set x+B = {x+b : b in B}.
+The center x may be anywhere in the ambient space.
+
+Example. In the plane, let B be a square of side 2 centered at the origin.
+How many copies of B does it take to cover a large disk A?
+That number is N(A,B).
+
+Covering numbers measure complexity.
+A set that needs many small copies is complicated.
+A set that needs few copies is simple.
+
+1.2 Convex bodies and polar
+
+A convex body is a compact convex set with nonempty interior.
+It is origin-symmetric if x in K implies -x in K.
+
+For an origin-symmetric convex body K in R^n, the polar body is
+
+ K^o = { y in R^n : <x,y> <= 1 for every x in K }.
+
+Here <x,y> is the dot product.
+The polar is another origin-symmetric convex body.
+It records all linear measurements that are at most 1 on K.
+
+Example. Let L = [-1,1]^n, the cube.
+Then L^o = { y : |y_1| + ... + |y_n| <= 1 }, the diamond-like body.
+
+1.3 The duality conjecture
+
+For origin-symmetric convex bodies K and L in R^n, the duality conjecture
+for metric entropy asks whether there are absolute constants a,b >= 1
+such that, for every dimension n and every pair K,L,
+
+ (1/b) log N(L^o, a K^o)
+ <= log N(K,L)
+ <= b log N(L^o, a^-1 K^o).
+
+The constants a and b must not depend on n, K, or L.
+This is Conjecture 1 in Artstein-Milman-Szarek 2004, building on
+Pietsch's 1972 operator-theoretic question.
+
+The conjecture says that passing to the polar pair preserves covering
+complexity up to a universal change of scale and a universal multiplicative
+constant. In words: covering K by copies of L should be roughly the same
+as covering L^o by copies of K^o.
+
+1.4 The main theorem
+
+Theorem 1. For every a,b >= 1, there are a positive integer n and an
+origin-symmetric convex body K in R^n such that, with L = [-1,1]^n,
+
+ log N(K,L) > b log N(L^o, a^-1 K^o).
+
+So the upper bound in the conjecture fails for every proposed pair (a,b).
+The dimension n depends on a and b and grows.
+No claim is made about a fixed dimension.
+
+The rest of this document proves Theorem 1 and one consequence.
+
+1.5 The shape of the counterexample
+
+We build a real matrix with two opposite properties:
+
+ (A) It has many rows, and any two rows are far apart in the sup norm.
+ (B) The absolutely convex hull of its columns has a small uniform
+ approximation list.
+
+Property (A) makes N(K,L) large.
+Property (B) makes N(L^o, a^-1 K^o) small.
+A simple geometric lemma turns the matrix into the bodies K and L.
+
+The hard part is making (A) and (B) true at the same time.
+We use partitions to compress the columns, and finite fields to separate
+the rows.
+
+2. NOTATION AND BASIC OBJECTS
+
+2.1 Finite sets and sup norms
+
+All logarithms in this document are natural logarithms.
+The binomial coefficient binom(a,b) is a!/(b!(a-b)!).
+
+For a finite set S, write
+
+ B_infty^S = [-1,1]^S = { f : S -> R : |f(s)| <= 1 for all s in S },
+ B_1^S = { lambda in R^S : sum_{s in S} |lambda_s| <= 1 }.
+
+For a function f on S, the sup norm is
+
+ ||f||_{infty,S} = max_{s in S} |f(s)|.
+
+If X is a finite set and g_y : X -> R for y in Y, the row R_x in R^Y is
+
+ R_x = (g_y(x))_{y in Y}.
+
+The sup norm on R^Y is ||R||_{infty,Y} = max_{y in Y} |R_y|.
+
+2.2 Absolutely convex hull
+
+For a finite set of vectors V, the absolutely convex hull absconv(V)
+is the convex hull of V union -V.
+Equivalently, it is the set of all finite sums
+
+ sum_j lambda_j v_j
+
+with v_j in V and sum_j |lambda_j| <= 1.
+
+2.3 Graphs and distance
+
+Let X be a finite set.
+A graph on X has vertices X and some edges between pairs of vertices.
+The graph distance d(x,z) is the smallest number of edges in a path from
+x to z. If there is no path, set d(x,z) = infinity.
+
+A partition of X is a map L : X -> Sigma.
+The set Sigma is the set of labels.
+Two points are in the same class if they have the same label.
+
+2.4 Symmetric multilinear forms
+
+Let p be a prime and let E = F_p^r be the r-dimensional vector space
+over the field with p elements.
+
+A map Z : E^h -> F_p is h-linear if it is linear in each argument
+when the other h-1 arguments are fixed.
+It is symmetric if swapping any two arguments does not change the value.
+
+The space of symmetric h-linear forms on E is written Sym^h(E^*).
+We also use Sym^0(E^*) = F_p.
+
+The number D_j is
+
+ D_j = binom(r+j-1,j).
+
+This is the number of multisets of size j chosen from r elements.
+It is also the dimension of Sym^j(E^*) over F_p.
+
+2.5 The main parameters
+
+The proof uses these symbols.
+They are chosen in Section 7.
+
+ a,b proposed constants in Theorem 1, a,b >= 1
+ theta a small positive number, theta = 1/(1000a)
+ s ceil(1/theta)
+ h a positive integer with log 3 / log(h+1) <= theta
+ r a large positive integer
+ D_j binom(r+j-1,j)
+ w 2 D_h
+ u ceil(h w / theta)
+ p a large prime
+ X Sym^h(F_p^r), the row index set
+ q p^{D_{h-1}}, the number of labels per partition
+ Y X times T, the column index set
+ T the family of allowed index sets T subset [u]
+
+3. THE PLAN IN DETAIL
+
+3.1 Step 1: matrix to bodies
+
+Lemma 4.1 below is the geometric conversion.
+It says:
+
+Suppose X and Y are finite nonempty sets, and g_y : X -> R for y in Y.
+Let
+
+ R_x = (g_y(x))_{y in Y},
+ F = { sum_y lambda_y g_y : sum_y |lambda_y| <= 1 }.
+
+Suppose:
+
+ (i) ||R_x - R_x'||_{infty,Y} >= 1 for all distinct x,x' in X.
+ (ii) For some eps > 0, there is a list of M functions on X such that
+ every member of F is within eps in sup norm of a list function.
+
+For t > 0 set
+
+ K = 3 absconv{R_x : x in X} + t B_infty^Y,
+ L = B_infty^Y.
+
+Then K and L are origin-symmetric convex bodies with nonempty interior,
+and
+
+ N(K,L) >= |X|,
+ N(L^o, (6 eps + 2t) K^o) <= M.
+
+So we need a matrix with many 1-separated rows and a small eps-net for
+the absolutely convex hull of its columns.
+
+3.2 Step 2: compression from partitions
+
+We build columns from partitions.
+Suppose X carries u partitions L_i : X -> Sigma_i, each with at most q
+labels. For a set T of partition indices, join two points when they share
+a label in some partition indexed by T. Let d_T be the graph distance.
+
+For a center v and a set T, define a column
+
+ g_{(v,T)}(x) = phi_h(d_T(x,v)),
+
+where
+
+ phi_h(d) = max{0, 1 - log(d+1)/log(h+1)}
+ for finite d, and phi_h(infinity) = 0.
+
+This column is 1 at x = v and decreases to 0 as x moves away from v.
+It reaches 0 once the distance is at least h.
+
+Proposition 5.2 says: if the family T is admissible, meaning
+
+ |[u] \ T| <= theta u for every T in T,
+
+then the positive column class has a uniform 3 theta approximation list
+of size Q with
+
+ log Q <= h s log q + C_{h,theta,u},
+ C_{h,theta,u} = log u
+ + h s 2^u log(1 + s 2^u / theta).
+
+The key point: Q depends on q and u, not on |X|.
+The number q can be much smaller than |X|.
+
+Corollary 5.3 extends this to signed coefficients.
+The absolutely convex hull of the columns has a uniform 6 theta
+approximation list of size at most Q^2.
+
+3.3 Step 3: finite-field partitions
+
+We need many rows but few labels.
+Take
+
+ X = Sym^h(F_p^r).
+
+Then
+
+ |X| = p^{D_h},
+ D_h = binom(r+h-1,h).
+
+For each direction t_i in F_p^r, define a partition by contraction:
+
+ L_i(x) = x(t_i, ., ..., .).
+
+This is a symmetric (h-1)-linear form.
+The number of possible labels is at most
+
+ q = p^{D_{h-1}},
+ D_{h-1} = binom(r+h-2,h-1).
+
+The ratio is
+
+ D_{h-1} / D_h = h / (r+h-1).
+
+When r is large compared with h, this ratio is small.
+So we get p^{D_h} rows but only p^{D_{h-1}} labels per partition.
+
+Proposition 6.3 chooses directions t_1,...,t_u so that every nonzero
+symmetric h-linear form Z has a large set T of indices such that
+Z(t_{i_1},...,t_{i_h}) is nonzero for every tuple from T.
+
+Proposition 6.4 uses this to show that every two distinct rows x,y in X
+have distance greater than h in the graph for some admissible T.
+Then the column at (x,T) separates x from y by exactly 1.
+So the rows are 1-separated.
+
+3.4 Step 4: choose the numbers
+
+In Section 7 we choose:
+
+ theta = 1/(1000a),
+ h with log 3 / log(h+1) <= theta,
+ r with r+h-1 > 8 b h^2 s,
+ p with p > max{h, h^2 u^{2h}, exp(8bC/D_h)}.
+
+Then the compression bound gives
+
+ log(Q^2) / log |X| < 1/(2b).
+
+The matrix-to-bodies lemma gives
+
+ N(K,L) >= |X|,
+ N(L^o, a^-1 K^o) <= Q^2.
+
+Therefore
+
+ b log N(L^o, a^-1 K^o)
+ <= b log(Q^2)
+ < (1/2) log |X|
+ < log N(K,L).
+
+That is Theorem 1.
+
+
+4. STEP 1: FROM A MATRIX TO CONVEX BODIES
+
+This section proves the geometric conversion.
+It is elementary: rows that are far apart force many translates,
+and a small list for column combinations gives a small cover of the polar.
+
+4.1 Lemma (matrix-to-body conversion)
+
+Let X and Y be finite nonempty sets.
+For each y in Y let g_y : X -> R.
+Write
+
+ R_x = (g_y(x))_{y in Y} in R^Y,
+ f_lambda = sum_{y in Y} lambda_y g_y,
+ F = { f_lambda : lambda in R^Y, sum_y |lambda_y| <= 1 }.
+
+Suppose
+
+ ||R_x - R_x'||_{infty,Y} >= 1 for all distinct x,x' in X.
+
+Suppose also that for some eps > 0 there is a list of M functions on X
+such that every f in F is within eps of a list function in sup norm.
+The list functions need not belong to F.
+
+For t > 0 set
+
+ K = 3 absconv{R_x : x in X} + t B_infty^Y,
+ L = B_infty^Y.
+
+Then K and L are origin-symmetric compact convex bodies with nonempty
+interior in R^Y, and
+
+ N(K,L) >= |X|,
+ N(L^o, (6 eps + 2t) K^o) <= M.
+
+Proof.
+
+First, K and L.
+The set absconv{R_x : x in X} is compact, convex, symmetric, and contains 0.
+Adding t B_infty^Y gives nonempty interior because t > 0.
+The cube L is also compact, convex, symmetric, and has nonempty interior.
+
+First inequality: N(K,L) >= |X|.
+
+Each point 3R_x belongs to K.
+If x != x', then
+
+ ||3R_x - 3R_x'||_{infty,Y} >= 3.
+
+Any translate of L has diameter at most 2 in sup norm.
+Indeed, if a and b are in z+L, then a-b is in L-L = 2L, so
+||a-b||_{infty,Y} <= 2.
+Therefore one translate of L contains at most one of the points 3R_x.
+To cover all |X| points, we need at least |X| translates.
+Thus N(K,L) >= |X|.
+
+Second inequality: N(L^o, (6 eps + 2t) K^o) <= M.
+
+We use the support function. For delta in R^Y define
+
+ h_K(delta) = sup_{z in K} <z,delta>.
+
+A direct calculation gives
+
+ h_K(delta)
+ = 3 max_{x in X} |<R_x,delta>|
+ + t sum_{y in Y} |delta_y|.
+
+Why? The maximum of <.,delta> over absconv{R_x} is
+max_x |<R_x,delta>|.
+The maximum over B_infty^Y is sum_y |delta_y|.
+The Minkowski sum allows these two maxima to be added.
+
+Also
+
+ <R_x,delta> = sum_y delta_y g_y(x) = f_delta(x).
+
+So
+
+ h_K(delta) = 3 ||f_delta||_{infty,X} + t ||delta||_1.
+
+The polar of the cube L is the diamond
+
+ L^o = B_1^Y = { lambda in R^Y : ||lambda||_1 <= 1 }.
+
+Now use the approximation list.
+Order its M functions.
+For each lambda in B_1^Y, assign lambda to the first list function A with
+
+ ||f_lambda - A||_{infty,X} <= eps.
+
+The hypothesis guarantees that at least one such function exists.
+This partitions B_1^Y into at most M nonempty clusters.
+From each nonempty cluster choose one actual coefficient vector
+lambda^(k) in B_1^Y.
+
+For any lambda in the same cluster,
+
+ ||f_lambda - f_lambda^(k)||_{infty,X} <= 2 eps,
+ ||lambda - lambda^(k)||_1 <= 2.
+
+The second inequality holds because both vectors are in B_1^Y:
+
+ ||lambda - lambda^(k)||_1
+ <= ||lambda||_1 + ||lambda^(k)||_1
+ <= 2.
+
+Now apply the support formula to delta = lambda - lambda^(k):
+
+ h_K(lambda - lambda^(k))
+ = 3 ||f_lambda - f_lambda^(k)||_{infty,X}
+ + t ||lambda - lambda^(k)||_1
+ <= 3 * 2 eps + t * 2
+ = 6 eps + 2t.
+
+Recall the scaling rule for polars:
+
+ delta in c K^o <=> h_K(delta) <= c for c > 0.
+
+Therefore every lambda in the cluster lies in
+
+ lambda^(k) + (6 eps + 2t) K^o.
+
+There are at most M clusters, so these translates cover B_1^Y = L^o.
+Hence
+
+ N(L^o, (6 eps + 2t) K^o) <= M.
+
+This proves the lemma.
+
+4.2 How the lemma is used
+
+For proposed constants a,b >= 1, it is enough to find a matrix and
+positive numbers eps,t such that
+
+ log |X| > b log M,
+ 6 eps + 2t <= a^-1.
+
+Then the lemma gives
+
+ N(K,L) >= |X|,
+ N(L^o, a^-1 K^o) <= N(L^o, (6 eps + 2t) K^o) <= M.
+
+The second inequality uses that (6 eps + 2t) K^o is contained in
+a^-1 K^o when 6 eps + 2t <= a^-1.
+Increasing the covering body only makes the cover easier.
+
+Therefore
+
+ b log N(L^o, a^-1 K^o)
+ <= b log M
+ < log |X|
+ <= log N(K,L).
+
+This is exactly the failure of the upper bound in the duality conjecture.
+
+The rest of the proof constructs such a matrix.
+Section 5 builds the small list for the columns.
+Section 6 separates the rows.
+Section 7 chooses the numbers so that log |X| is much larger than log M.
+
+
+5. STEP 2: COMPRESSION FROM PARTITIONS
+
+This is the engine of the proof.
+We have u partitions of X, each with at most q labels.
+We build columns from graph distances.
+We show that every nonnegative combination of columns with total mass
+at most 1 can be approximated by a list whose size depends only on
+h, theta, u, q, and not on |X|.
+
+5.1 Setup and the logarithmic profile
+
+Let X be a finite nonempty set.
+Let u and q be positive integers.
+For i in [u] = {1,...,u}, let
+
+ L_i : X -> Sigma_i, |L_i(X)| <= q.
+
+Fix 0 < theta < 1 and a nonempty family T of subsets of [u] such that
+
+ |[u] \ T| <= theta u for every T in T.
+
+Call such a set T admissible.
+
+For T in T, form a graph on X.
+Two distinct points x,z are adjacent if
+
+ L_i(x) = L_i(z) for some i in T.
+
+Let d_T(x,z) be the graph distance.
+If x and z are in different components, set d_T(x,z) = infinity.
+
+Choose a positive integer h such that
+
+ log 3 / log(h+1) <= theta,
+ s = ceil(1/theta).
+
+Define the logarithmic profile
+
+ phi_h(d) = max{0, 1 - log(d+1)/log(h+1)}
+ for finite d >= 0, and phi_h(infinity) = 0.
+
+The profile is 1 at distance 0 and 0 at distance at least h.
+It decreases as the distance grows.
+
+Set Y = X times T.
+For y = (v,T) in Y, define the column g_y : X -> R by
+
+ g_y(x) = phi_h(d_T(x,v)).
+
+Then 0 <= g_y(x) <= 1 for all x and y.
+
+For nonnegative coefficients mu_y with total mass at most 1, write
+
+ f_mu = sum_{y in Y} mu_y g_y,
+ F_+ = { f_mu : mu_y >= 0, sum_y mu_y <= 1 }.
+
+For a function f on X, let
+
+ ||f||_{infty,X} = max_{x in X} |f(x)|.
+
+We want a uniform approximation list for F_+ whose size is controlled
+by h, theta, u, q, and not by |X|.
+
+Lemma 5.1 (logarithmic profile).
+For any positive integer h, define
+
+ gamma_j = (log(j+2) - log(j+1)) / log(h+1)
+ for 0 <= j < h.
+
+The weights gamma_j are positive, sum to 1, and for every
+d in {0,1,2,...} union {infinity},
+
+ phi_h(d) = sum_{j=0}^{h-1} gamma_j 1_{d <= j},
+
+ sum_{j=0}^{h-1} gamma_j 1_{d <= 3j+2}
+ <= phi_h(d) + log 3 / log(h+1).
+
+Here 1_{...} is the indicator: it is 1 if the condition is true and
+0 otherwise.
+
+Proof.
+Positivity is clear because log is increasing.
+The weights telescope:
+
+ sum_{j=0}^{h-1} gamma_j
+ = (log(h+1) - log 1) / log(h+1)
+ = 1.
+
+For the first identity, suppose 0 <= d < h.
+The sum runs from j = d to j = h-1, so
+
+ sum_{j=d}^{h-1} gamma_j
+ = (log(h+1) - log(d+1)) / log(h+1)
+ = 1 - log(d+1)/log(h+1)
+ = phi_h(d).
+
+If d >= h, including d = infinity, both sides are zero.
+
+For the second identity, suppose first that d is finite.
+The extra indices counted on the left but not by phi_h(d) satisfy
+
+ j < d <= 3j+2.
+
+When this set is nonempty, it is the integer interval from
+
+ a_d = max{0, ceil((d+1)/3) - 1}
+
+to
+
+ b_d = min{h-1, d-1}.
+
+We have b_d + 2 <= d+1 and a_d + 1 >= (d+1)/3.
+Therefore the extra weight is
+
+ sum_{j=a_d}^{b_d} gamma_j
+ = (log(b_d+2) - log(a_d+1)) / log(h+1)
+ <= log 3 / log(h+1).
+
+An empty interval contributes zero.
+If d = infinity, all indicators on the left vanish.
+This proves the lemma.
+
+
+5.2 The compression proposition
+
+Proposition 5.2 (uniform compression).
+Under the setup of Section 5.1, there is a finite list A of real
+functions on X, of cardinality Q, such that every f in F_+ has an
+approximant A_f in A satisfying
+
+ f(x) - 3 theta <= A_f(x) <= f(x) + theta for all x in X.
+
+In particular,
+
+ ||f - A_f||_{infty,X} <= 3 theta.
+
+The list can be chosen with
+
+ log Q <= h s log q + C_{h,theta,u},
+
+where
+
+ C_{h,theta,u}
+ = log u + h s 2^u log(1 + s 2^u / theta).
+
+Proof.
+
+For each i in [u], fix a representative map
+
+ rho_i : L_i(X) -> X,
+ L_i(rho_i(sigma)) = sigma.
+
+These maps are fixed for the whole problem, before any coefficient
+vector mu is chosen.
+
+Step 1: a common index.
+
+Fix f = f_mu in F_+.
+For a subset S of Y, write mu(S) = sum_{y in S} mu_y.
+Average the admissible condition over i:
+
+ (1/u) sum_{i=1}^u mu{(v,T) : i not in T}
+ = sum_{(v,T) in Y} mu_{(v,T)} |[u]\T| / u
+ <= theta.
+
+Therefore there is an index i0 in [u] such that
+
+ mu{(v,T) : i0 not in T} <= theta.
+
+Retain the columns
+
+ Y0 = {(v,T) in Y : i0 in T}.
+
+The omitted mass is at most theta.
+This one index i0 will serve at every distance level j.
+
+Step 2: a bounded number of pivots at each level.
+
+Fix j in {0,...,h-1}.
+For x in X let
+
+ I_x = {(v,T) in Y0 : d_T(x,v) <= j}.
+
+Start with an empty union.
+Add a set I_z whenever its mass outside the current union is greater
+than theta.
+If k_j sets are added, their successive contributions satisfy
+k_j theta < 1, so
+
+ k_j <= s = ceil(1/theta).
+
+The process terminates with pivots z_{j,1},...,z_{j,k_j} and union
+
+ U_j = union_{k=1}^{k_j} I_{z_{j,k}}
+
+such that
+
+ mu(I_x \ U_j) <= theta for every x in X.
+
+The empty choice is allowed.
+Assign every column of U_j to the first pivot whose set contains it.
+Let kappa_j(y) be its assigned slot.
+
+Step 3: replace each pivot by a label representative.
+
+For a pivot z = z_{j,k}, keep only its label L_{i0}(z), and replace it by
+
+ z' = rho_{i0}(L_{i0}(z)).
+
+If y = (v,T) is assigned to this pivot, then i0 is in T,
+
+ d_T(v,z) <= j,
+ d_T(z,z') <= 1.
+
+Thus
+
+ d_T(v,z') <= j+1.
+
+For every x in X, the triangle inequality gives
+
+ d_T(x,v) <= j
+ => d_T(x,z') <= 2j+1,
+
+ d_T(x,z') <= 2j+1
+ => d_T(x,v) <= 3j+2.
+
+All distances used here are finite under the stated hypotheses.
+
+Define
+
+ A_j(x)
+ = sum_{y=(v,T) in U_j} mu_y
+ 1_{d_T(x,z'_{j,kappa_j(y)}) <= 2j+1}.
+
+For comparison, let
+
+ f_{mu,j}(x)
+ = sum_{y=(v,T) in Y} mu_y
+ 1_{d_T(x,v) <= j}.
+
+Every assigned column counted by f_{mu,j}(x) is counted by A_j(x),
+by the forward implication.
+The other columns counted by f_{mu,j}(x) have total mass at most
+2 theta:
+at most theta lies outside Y0, and at most theta lies in I_x \ U_j.
+Conversely, the backward implication bounds every column counted by A_j.
+Hence
+
+ f_{mu,j}(x) - 2 theta
+ <= A_j(x)
+ <= sum_{y=(v,T) in Y} mu_y
+ 1_{d_T(x,v) <= 3j+2}.
+
+Step 4: combine the levels.
+
+Let
+
+ F = sum_{j=0}^{h-1} gamma_j A_j.
+
+By Lemma 5.1,
+
+ f_mu = sum_{j=0}^{h-1} gamma_j f_{mu,j}.
+
+The lower bound gives
+
+ F >= f_mu - 2 theta.
+
+For the upper bound, apply the dilation inequality of Lemma 5.1 to
+each distance d_T(x,v), and sum with weights mu_{(v,T)}.
+Since the total mass is at most 1 and
+
+ log 3 / log(h+1) <= theta,
+
+we get
+
+ f_mu - 2 theta <= F <= f_mu + theta.
+
+Step 5: a finite encoding.
+
+The center v of an assigned column no longer occurs in its indicator
+in A_j.
+Group columns by assigned slot and by T:
+
+ A_j(x)
+ = sum_{k=1}^s sum_{T in T} w_{j,k,T}
+ 1_{d_T(x,z'_{j,k}) <= 2j+1},
+
+where
+
+ w_{j,k,T}
+ = sum_{v : (v,T) in U_j, kappa_j(v,T)=k} mu_{(v,T)}.
+
+Unused slots have all weights zero and are padded with a fixed realized
+L_{i0}-label.
+Each weight is in [0,1], and there are at most
+
+ M0 = s 2^u
+
+weights at each level.
+Round each weight down to a multiple of
+
+ delta = theta / M0:
+
+ tilde w_{j,k,T}
+ = delta floor(w_{j,k,T} / delta).
+
+Let tilde A_j be A_j with these rounded weights, and put
+
+ A = sum_{j=0}^{h-1} gamma_j tilde A_j.
+
+Since every indicator is at most one,
+
+ 0 <= A_j(x) - tilde A_j(x) <= M0 delta = theta.
+
+The weights gamma_j sum to one, so
+
+ 0 <= F - A <= theta.
+
+Together with the previous inequalities, this gives
+
+ f_mu - 3 theta <= A <= f_mu + theta.
+
+Step 6: count one list that works for all mu.
+
+For fixed i0, the data determining A are the s pivot labels at each of
+the h levels and the rounded weights.
+The label determines z' through the fixed map rho_{i0}, so no original
+pivot or column center must be specified.
+There are at most q^{h s} choices of labels.
+Each rounded weight has at most
+
+ floor(M0/theta) + 1 <= 1 + M0/theta
+
+possible values, and there are at most h M0 such weights.
+Enumerate these choices for every i0 in [u], allowing also codes that
+do not arise from a coefficient vector.
+This gives a fixed finite list containing every approximant constructed
+above, with
+
+ Q <= u q^{h s}
+ (1 + s 2^u / theta)^{h s 2^u}.
+
+Taking logarithms proves the bound on log Q.
+The graphs and representative maps are shared data defining the list;
+they are not additional choices for each approximant.
+This proves the proposition.
+
+
+5.3 Signed compression
+
+Corollary 5.3 (signed compression).
+With the notation of Proposition 5.2, put
+
+ f_lambda = sum_{y in Y} lambda_y g_y,
+ B_1^Y = { lambda in R^Y : sum_{y in Y} |lambda_y| <= 1 },
+ F = { f_lambda : lambda in B_1^Y }
+ = absconv{g_y : y in Y}.
+
+Then there is a list of at most Q^2 functions which approximates every
+member of F to uniform error 6 theta.
+
+Moreover, B_1^Y can be partitioned into at most Q^2 nonempty clusters
+such that
+
+ ||f_lambda - f_lambda'||_{infty,X} <= 12 theta
+
+whenever lambda and lambda' belong to the same cluster.
+
+Proof.
+
+Write
+
+ lambda = lambda^+ - lambda^-,
+
+where
+
+ lambda_y^+ = max{lambda_y, 0},
+ lambda_y^- = max{-lambda_y, 0}.
+
+Each part is nonnegative and has total mass at most one.
+Apply Proposition 5.2 to choose A^+, A^- in A with
+
+ ||f_{lambda^+} - A^+||_{infty,X} <= 3 theta,
+ ||f_{lambda^-} - A^-||_{infty,X} <= 3 theta.
+
+Then A^+ - A^- approximates f_lambda to error at most 6 theta.
+There are at most Q^2 differences in A - A.
+
+Order this finite list and assign each lambda in B_1^Y to its first
+approximant with error at most 6 theta.
+The nonempty fibers form the claimed partition.
+The triangle inequality gives
+
+ ||f_lambda - f_lambda'||_{infty,X}
+ <= ||f_lambda - A||_{infty,X}
+ + ||A - f_lambda'||_{infty,X}
+ <= 6 theta + 6 theta
+ = 12 theta.
+
+The approximating functions need not belong to F.
+The clusters themselves consist of actual coefficient vectors in B_1^Y.
+This proves the corollary.
+
+
+6. STEP 3: FINITE-FIELD PARTITIONS AND SEPARATED ROWS
+
+We now build the partitions that feed into Section 5.
+We want many rows but few labels per partition.
+The rows will be symmetric multilinear forms over a finite field.
+The partitions will be contractions by chosen directions.
+
+There are two ingredients:
+
+ 6.1 a polynomial zero bound over F_p;
+ 6.2 a dimension count for symmetric forms;
+ 6.3 a choice of directions that makes every nonzero form nonzero on
+ many tuples;
+ 6.4 the resulting graph separation of rows.
+
+6.1 The polynomial zero bound
+
+Lemma 6.1 (Schwartz-Zippel).
+Let P in F_p[z_1,...,z_k] be a nonzero polynomial of total degree at
+most d, where k and d are nonnegative integers and p is prime.
+If U_1,...,U_k are independent and uniform in F_p, then
+
+ Pr(P(U_1,...,U_k) = 0) <= d/p.
+
+Proof.
+
+Induct on k.
+When k = 0, P is a nonzero constant, so its zero probability is 0.
+For k >= 1, write
+
+ P(z_1,...,z_k)
+ = sum_{j=0}^e P_j(z_1,...,z_{k-1}) z_k^j,
+
+with P_e not the zero polynomial.
+The total degree of P_e is at most d-e.
+By the induction hypothesis,
+
+ Pr(P_e(U_1,...,U_{k-1}) = 0) <= (d-e)/p.
+
+Condition on any values of the first k-1 variables for which P_e does
+not vanish.
+The resulting univariate polynomial in z_k has degree e, so it has at
+most e roots.
+Its conditional zero probability is therefore at most e/p.
+
+The sum of these two bounds is
+
+ (d-e)/p + e/p = d/p.
+
+This also covers e = 0 and all nonzero constant polynomials.
+This proves the lemma.
+
+6.2 Symmetric forms and their dimension
+
+For positive integers r and h, set
+
+ D_j = binom(r+j-1, j) for j >= 0.
+
+Let E = F_p^r.
+Write Sym^j(E^*) for the space of maps E^j -> F_p that are multilinear
+and invariant under permutations of their arguments.
+We also use Sym^0(E^*) = F_p.
+
+Relative to a basis e_1,...,e_r of E, a symmetric j-linear form is
+specified freely by its values on multisets of j basis vectors.
+Such a multiset is described by counts
+
+ alpha_1,...,alpha_r >= 0,
+ alpha_1 + ... + alpha_r = j.
+
+The number of solutions is
+
+ binom(r+j-1, j) = D_j.
+
+Therefore
+
+ dim_{F_p} Sym^j(E^*) = D_j,
+ |Sym^j(E^*)| = p^{D_j}.
+
+In particular, the row space
+
+ X = Sym^h(E^*)
+
+has size
+
+ |X| = p^{D_h}.
+
+Each contraction by a direction t in E,
+
+ x |-> x(t, ., ..., .),
+
+is a symmetric (h-1)-linear form.
+So its values lie in a space of size at most
+
+ p^{D_{h-1}}.
+
+This is the small label set q in the compression proposition.
+
+
+6.3 Directions with nonvanishing evaluations
+
+Proposition 6.3 (robust directions).
+Let 0 < theta < 1 and let r,h be positive integers.
+Put
+
+ w = 2 D_h,
+ u = ceil(h w / theta),
+
+and let p be any prime satisfying
+
+ p > max{h, h^2 u^{2h}}.
+
+There exist directions t_1,...,t_u in E = F_p^r such that, for every
+nonzero Z in Sym^h(E^*), there is a set T subset [u] with
+
+ |[u] \ T| <= theta u
+
+for which
+
+ Z(t_{i_1},...,t_{i_h}) != 0
+
+for all (i_1,...,i_h) in T^h.
+Tuples in this assertion may have repeated indices.
+
+Proof.
+
+Choose t_1,...,t_u independently and uniformly in E.
+Fix a nonzero form Z.
+
+For z = sum_{a=1}^r z_a e_a, define the diagonal polynomial
+
+ P_Z(z_1,...,z_r) = Z(z,...,z).
+
+Using multinomial expansion,
+
+ P_Z(z_1,...,z_r)
+ = sum_{alpha_1+...+alpha_r=h, alpha_a>=0}
+ (h! / (alpha_1! ... alpha_r!))
+ Z(e_1^{[alpha_1]},...,e_r^{[alpha_r]})
+ z_1^{alpha_1} ... z_r^{alpha_r}.
+
+Here e_a^{[alpha_a]} means that e_a is repeated alpha_a times among
+the arguments.
+
+At least one displayed value of Z is nonzero.
+Since p > h, every multinomial coefficient is nonzero in F_p.
+Distinct multisets give distinct monomials, so P_Z is a nonzero
+polynomial of total degree h.
+
+For an ordered tuple i = (i_1,...,i_h) in [u]^h, let
+
+ supp(i) = {i_1,...,i_h}.
+
+The expression
+
+ Z(t_{i_1},...,t_{i_h})
+
+considered as a polynomial in the scalar coordinates of the vectors
+with indices in supp(i) has total degree h and is nonzero.
+Indeed, setting all those vector variables equal to z gives the nonzero
+polynomial P_Z.
+
+Lemma 6.1 therefore gives
+
+ Pr(Z(t_{i_1},...,t_{i_h}) = 0) <= h/p.
+
+This applies to every pattern of repeated indices.
+
+For this fixed Z, evaluations on tuples with pairwise disjoint index
+supports depend on disjoint subsets of the independent vectors t_i.
+Their zero events are consequently independent.
+
+There are at most u^{h w} ordered lists of w ordered h-tuples.
+There are fewer than p^{D_h} choices of nonzero Z.
+A union bound shows that the probability that some nonzero Z has w zero
+tuples with pairwise disjoint supports is at most
+
+ p^{D_h} u^{h w} (h/p)^w
+ = (h^2 u^{2h} / p)^{D_h}
+ < 1.
+
+The count includes all forms over the chosen field.
+No independence between different forms is needed.
+
+Fix vectors for which this event does not occur.
+
+For each nonzero Z, take a family of zero tuples with pairwise disjoint
+supports that is maximal under inclusion.
+It contains at most w-1 tuples.
+Delete the union of their supports, and let T be the remaining indices.
+The number of deleted indices is at most
+
+ h(w-1) < h w <= theta u.
+
+If any zero tuple were supported in T, its support would be disjoint
+from all the selected supports, contradicting maximality.
+Thus
+
+ Z(t_{i_1},...,t_{i_h}) != 0
+
+for every tuple from T.
+Since theta < 1, the set T is nonempty.
+The construction imposed no requirement that the sampled vectors be
+distinct or nonzero.
+This proves the proposition.
+
+
+6.4 Partitions with separated rows
+
+Proposition 6.4 (separated rows).
+With the parameters and directions of Proposition 6.3, let
+
+ X = Sym^h(E^*),
+ L_i(x) = x(t_i, ., ..., .),
+ T = { T subset [u] : |[u] \ T| <= theta u }.
+
+Then
+
+ |X| = m = p^{D_h},
+
+and each label map L_i has at most
+
+ q = p^{D_{h-1}}
+
+realized labels.
+
+For the partition graphs of Section 5.1, every pair of distinct
+x,y in X has some T in T satisfying
+
+ d_T(x,y) > h.
+
+Consequently, for
+
+ Y = X times T,
+ R_x = (g_{(v,T)}(x))_{(v,T) in Y} in R^Y,
+
+the rows satisfy
+
+ ||R_x - R_y||_{infty,Y} = 1 for x != y.
+
+Proof.
+
+The cardinality of X follows from Section 6.2.
+The contraction L_i(x) is a symmetric (h-1)-linear form, so its possible
+values belong to a space of cardinality p^{D_{h-1}}.
+This bounds the realized labels even if a contraction is not surjective.
+
+Fix distinct x,y in X, and apply Proposition 6.3 to
+
+ Z = y - x.
+
+Let T in T be the resulting nonempty set.
+
+Recall that distinct vertices are adjacent in the graph for T if their
+labels agree at some i in T.
+Suppose there were a path
+
+ x = x_0, x_1, ..., x_k = y,
+ 1 <= k <= h.
+
+For each edge choose i_j in T such that
+
+ L_{i_j}(x_j) = L_{i_j}(x_{j-1}),
+
+and put
+
+ Delta_j = x_j - x_{j-1}.
+
+Thus
+
+ Delta_j(t_{i_j}, v_2, ..., v_h) = 0
+
+for every v_2,...,v_h in E.
+
+Choose any i_* in T, and form the h-tuple consisting of
+
+ t_{i_1}, ..., t_{i_k}
+
+followed by h-k copies of t_{i_*}.
+Every Delta_j vanishes on this tuple, since it is symmetric and one of
+its arguments is t_{i_j}.
+The identity
+
+ Z = sum_{j=1}^k Delta_j
+
+implies that Z also vanishes on the tuple, contrary to Proposition 6.3.
+This proves
+
+ d_T(x,y) > h.
+
+Vertices in different components have infinite distance and already
+satisfy the inequality.
+
+At the column (x,T), the logarithmic profile gives
+
+ g_{(x,T)}(x) = 1,
+ g_{(x,T)}(y) = 0,
+
+because d_T(x,y) > h.
+All column values lie in [0,1], so this unit difference also gives the
+exact equality
+
+ ||R_x - R_y||_{infty,Y} = 1.
+
+This proves the proposition.
+
+The family T here contains every admissible subset and is fixed with
+the partitions.
+The separating set T may depend on the pair of rows.
+This is compatible with Proposition 5.2, whose common index may depend
+on the particular convex combination of columns.
+
+If h also satisfies
+
+ log 3 / log(h+1) <= theta,
+
+then the compression bound applies with
+
+ q = p^{D_{h-1}},
+ s = ceil(1/theta),
+
+giving
+
+ log Q <= h s D_{h-1} log p + C_{h,theta,u}.
+
+Once r, h, and theta are fixed, so are u and C_{h,theta,u}.
+The prime p can still be taken arbitrarily large subject to the prime
+threshold in Proposition 6.3.
+
+
+7. STEP 4: CHOOSING THE PARAMETERS
+
+We now assemble the three tools.
+Fix a,b >= 1.
+
+7.1 The choices
+
+Set
+
+ theta = 1/(1000a),
+ s = ceil(1/theta).
+
+Choose a positive integer h with
+
+ log 3 / log(h+1) <= theta.
+
+Such an integer exists because log(h+1) tends to infinity.
+
+Choose a positive integer r so that
+
+ r + h - 1 > 8 b h^2 s.
+
+Define
+
+ D_j = binom(r+j-1, j) for 0 <= j <= h,
+ w = 2 D_h,
+ u = ceil(h w / theta).
+
+The number
+
+ C = C_{h,theta,u}
+ = log u + h s 2^u log(1 + s 2^u / theta)
+
+is now fixed.
+
+Choose a prime p satisfying
+
+ p > max{ h, h^2 u^{2h}, exp(8bC/D_h) }.
+
+All quantities on the right have already been determined.
+Primes exceed every finite bound, so such a p exists.
+
+Apply Proposition 6.3 with these parameters.
+Form the label maps and graph profiles in Proposition 6.4.
+The row index set is
+
+ X = Sym^h(F_p^r),
+
+so
+
+ m = |X| = p^{D_h} > 1.
+
+Each label map takes at most
+
+ q = p^{D_{h-1}}
+
+values.
+The columns are indexed by
+
+ Y = X times T,
+ T = { T subset [u] : |[u] \ T| <= theta u }.
+
+The real row vectors satisfy
+
+ ||R_x - R_x'||_{infty,Y} = 1 for x != x'.
+
+In particular, Y is a finite nonempty set.
+The finite field is used only to construct the indices and label maps.
+The matrix entries and the convex bodies below are real.
+
+7.2 Applying compression and the matrix lemma
+
+By Proposition 5.2, the positive column class has a uniform 3 theta
+approximation list of cardinality Q with
+
+ log Q <= h s log q + C
+ = h s D_{h-1} log p + C.
+
+Corollary 5.3 gives a uniform 6 theta approximation list of at most Q^2
+functions for the absolutely convex column hull.
+
+Thus the matrix-to-body lemma applies with
+
+ eps = 6 theta,
+ t = theta.
+
+It gives admissible bodies in dimension n = |Y|,
+
+ K = 3 absconv{R_x : x in X} + theta B_infty^Y,
+ L = B_infty^Y,
+
+such that
+
+ N(K,L) >= m,
+ N(L^o, 38 theta K^o) <= Q^2.
+
+The number 38 comes from
+
+ 6 eps + 2t = 6(6 theta) + 2 theta = 38 theta.
+
+Since
+
+ 38 theta = 38/(1000a) < a^-1,
+
+increasing the covering body preserves the cover, and therefore
+
+ N(L^o, a^-1 K^o) <= Q^2.
+
+7.3 Comparing the two entropies
+
+Use the exact identity
+
+ D_{h-1} / D_h = h / (r+h-1).
+
+This follows directly from the binomial formula.
+
+Then
+
+ log(Q^2) / log m
+ <= (2 h s D_{h-1} log p + 2C) / (D_h log p)
+ = 2 h s (D_{h-1}/D_h) + 2C/(D_h log p)
+ = 2 h^2 s/(r+h-1) + 2C/(D_h log p)
+ < 1/(4b) + 1/(4b)
+ = 1/(2b).
+
+The two strict inequalities come from the choices of r and p:
+
+ r+h-1 > 8 b h^2 s
+ implies 2 h^2 s/(r+h-1) < 1/(4b),
+
+ p > exp(8 b C / D_h)
+ implies 2C/(D_h log p) < 1/(4b).
+
+Combining this with N(L^o, a^-1 K^o) <= Q^2 and N(K,L) >= m > 1 gives
+
+ b log N(L^o, a^-1 K^o)
+ <= b log(Q^2)
+ < (1/2) log m
+ < log m
+ <= log N(K,L).
+
+The strict inequality (1/2) log m < log m uses m > 1.
+Identifying R^Y with R^n makes L = [-1,1]^n.
+This proves Theorem 1.
+
+7.4 An asymptotic form
+
+The same estimate gives an asymptotic statement.
+
+Fix a >= 1, and hence theta, h, and s.
+For each positive integer r, set D_h, u, C as above and choose a prime
+
+ p > max{ h, h^2 u^{2h}, exp(rC/D_h) }.
+
+The resulting bodies K_r and L_r satisfy
+
+ 0 <= log N(L_r^o, a^-1 K_r^o) / log N(K_r, L_r)
+ <= 2 h^2 s/(r+h-1) + 2/r
+ -> 0.
+
+Although u and C may grow rapidly with r, both are fixed before p is
+chosen.
+No upper bound on the resulting ambient dimension is required for this
+conclusion.
+
+
+8. A CONSEQUENCE FOR CONVEXIFIED PACKING
+
+Ordinary covering entropy is not the only notion of complexity.
+There is also convexified packing.
+The counterexample also separates the two notions.
+
+8.1 Definition
+
+For a nonempty bounded set T and an origin-symmetric convex body B,
+let Mhat(T,B) be the largest length of an ordered sequence
+
+ x_1, ..., x_m in T
+
+such that
+
+ (x_j + int B) intersect conv{x_i : i < j} = empty
+
+for every 1 <= j <= m.
+The first convex hull is the empty set.
+
+In words: each new point must stay outside the convex hull of all
+previous points, even after adding the interior of B.
+This is a convexified packing condition.
+
+8.2 The corollary
+
+Corollary 8.1 (separation from convexified packing).
+For every A,C >= 1, there are an integer n >= 1 and an origin-symmetric
+convex body K in R^n such that, with L = [-1,1]^n,
+
+ log N(K,L) > C log Mhat(K, L/A).
+
+Proof.
+
+First, an ordered B-convexly separated sequence has at most one point
+in each translate of B/4.
+
+Indeed, suppose two points x_i and x_j with i < j lie in the same
+translate of B/4.
+Then
+
+ x_j - x_i is in B/4 - B/4 = B/2.
+
+Because B is origin-symmetric and has nonempty interior, 0 lies in int B.
+Convexity then gives that B/2 is contained in int B.
+Thus x_i lies in x_j + int B.
+But x_i is in conv{x_l : l < j}, so
+
+ (x_j + int B) intersect conv{x_l : l < j}
+
+is nonempty, contradicting the separation condition.
+
+Consequently,
+
+ Mhat(T,B) <= N(T,B/4).
+
+There is no boundary ambiguity here because we cover by closed translates.
+
+The universal convexified duality bound of
+Artstein-Milman-Szarek-Tomczak-Jaegermann 2004, Theorem 2,
+applied to K and L/A, gives
+
+ Mhat(K, L/A)
+ <= Mhat((L/A)^o, K^o/2)^2
+ = Mhat(A L^o, K^o/2)^2
+ = Mhat(L^o, K^o/(2A))^2
+ <= N(L^o, K^o/(8A))^2.
+
+The equality uses simultaneous dilation of both arguments:
+
+ Mhat(cT, cB) = Mhat(T,B) for c > 0.
+
+Now choose K and L by Theorem 1 with
+
+ a = 8A,
+ b = 2C.
+
+Theorem 1 gives
+
+ log N(K,L) > 2C log N(L^o, K^o/(8A)).
+
+Taking logarithms in the displayed bound gives
+
+ log Mhat(K, L/A)
+ <= 2 log N(L^o, K^o/(8A)).
+
+Therefore
+
+ C log Mhat(K, L/A)
+ <= 2C log N(L^o, K^o/(8A))
+ < log N(K,L).
+
+This proves the corollary.
+
+
+9. WHAT TO REMEMBER
+
+The whole proof fits into one sentence:
+
+ separated rows make covering numbers large,
+ a small list for columns makes the polar covering number small,
+ and finite fields give both at once.
+
+The details:
+
+1. Covering number N(A,B) is the least number of translates of B that
+ cover A.
+
+2. The polar body K^o records linear measurements bounded by 1 on K.
+ The duality conjecture asks whether N(K,L) and N(L^o, K^o) are
+ comparable up to universal constants.
+
+3. Theorem 1 says no.
+ For every a,b >= 1, there is an origin-symmetric convex body K in
+ some R^n such that, with L = [-1,1]^n,
+
+ log N(K,L) > b log N(L^o, a^-1 K^o).
+
+4. The matrix-to-body lemma turns a matrix into K and L.
+ Many 1-separated rows force N(K,L) to be large.
+ A small eps-net for the absolutely convex hull of the columns forces
+ N(L^o, (6 eps + 2t) K^o) to be small.
+
+5. Compression builds the small eps-net.
+ With u partitions of X, each having at most q labels, the positive
+ column class has a 3 theta approximation list of size Q with
+
+ log Q <= h s log q + C_{h,theta,u}.
+
+ The signed version has a 6 theta list of size Q^2.
+
+6. Finite fields give many rows and few labels.
+ Take X = Sym^h(F_p^r).
+ Then
+
+ |X| = p^{D_h},
+ q = p^{D_{h-1}},
+ D_{h-1}/D_h = h/(r+h-1).
+
+ Taking r large makes the label count small compared with the row
+ count on the logarithmic scale.
+
+7. The parameters are chosen so that
+
+ log(Q^2) / log |X| < 1/(2b).
+
+ Then
+
+ b log N(L^o, a^-1 K^o)
+ <= b log(Q^2)
+ < (1/2) log |X|
+ < log N(K,L).
+
+8. The same construction separates ordinary covering entropy from
+ convexified packing entropy; see Corollary 8.1.
+
+9.1 Where this fits
+
+The question goes back to Pietsch in 1972.
+Konig and Milman proved a comparison of nth roots of the two covering
+numbers in 1987.
+Bourgain, Pajor, Szarek, and Tomczak-Jaegermann proved entropy-number
+comparisons under geometric or sequence-regularity assumptions in 1989.
+
+Artstein, Milman, and Szarek proved the dimension-free conjecture when
+one body is a Euclidean ball, and hence when either body is an ellipsoid,
+in 2004.
+Artstein, Milman, Szarek, and Tomczak-Jaegermann proved universal
+duality for convexified packing in 2004.
+They also announced ordinary entropy duality for spaces with bounded
+K-convexity constant, with constants depending on that bound.
+
+Emanuel Milman obtained a comparison with logarithmic losses in both
+the scale and the entropy factor in 2007.
+Hu, Peale, and Reingold studied dual covering numbers of function
+classes in learning theory in 2022, with an explicit prefactor depending
+on the approximation scale and uniform bounds.
+
+Mendelson developed convex-hull estimates for finite sets in 2001.
+The finite-field side of this paper uses the polynomial zero bound of
+Schwartz and Zippel, together with diagonal recovery of symmetric
+multilinear forms in large characteristic.
+
+The point of Theorem 1 is that none of these dimension-dependent or
+scale-dependent estimates can be upgraded to one universal pair of
+constants for all dimensions and all bodies.
+
+10. REFERENCES
+
+[1] S. Artstein, V. Milman, S. J. Szarek.
+ Duality of metric entropy.
+ Annals of Mathematics 159 (2004), 1313-1328.
+
+[2] S. Artstein, V. Milman, S. Szarek, N. Tomczak-Jaegermann.
+ On convexified packing and entropy duality.
+ Geometric and Functional Analysis 14 (2004), 1134-1141.
+
+[3] E. Milman.
+ A remark on two duality relations.
+ Integral Equations and Operator Theory 57 (2007), 217-228.
+
+[4] A. Pietsch.
+ Theorie der Operatorenideale (Zusammenfassung).
+ Friedrich-Schiller-Universitat Jena, 1972.
+
+[5] J. T. Schwartz.
+ Fast probabilistic algorithms for verification of polynomial
+ identities.
+ Journal of the ACM 27 (1980), 701-717.
+
+[6] R. Zippel.
+ Probabilistic algorithms for sparse polynomials.
+ Lecture Notes in Computer Science 72 (1979), 216-226.
+
+[7] L. Hu, C. Peale, O. Reingold.
+ Metric entropy duality and the sample complexity of outcome
+ indistinguishability.
+ Proceedings of Algorithmic Learning Theory 2022,
+ PMLR 167, 515-552.
+
+[8] H. Konig, V. D. Milman.
+ On the covering numbers of convex bodies.
+ Lecture Notes in Mathematics 1267 (1987), 82-95.
+
+[9] J. Bourgain, A. Pajor, S. J. Szarek, N. Tomczak-Jaegermann.
+ On the duality problem for entropy numbers of operators.
+ Lecture Notes in Mathematics 1376 (1989), 50-63.
+
+[10] S. Mendelson.
+ On the size of convex hulls of small sets.
+ Journal of Machine Learning Research 2 (2001), 1-18.
+
+[11] M. Ferrero, A. Micali.
+ Sur les n-applications.
+ Memoires de la Societe Mathematique de France 59 (1979), 33-53.
+
+[12] A. Drapal, P. Vojtechovsky.
+ Symmetric multilinear forms and polarization of polynomials.
+ Linear Algebra and its Applications 431 (2009), 998-1012.
+
+END OF DOCUMENT
+