diff c139821..9e3f2ca metric_entropy_duality_counterexamples_v2.txt
diff --git a/metric_entropy_duality_counterexamples_v2.txt b/metric_entropy_duality_counterexamples_v2.txt
index d03f9e7..7ccaae2 100644
--- a/metric_entropy_duality_counterexamples_v2.txt
+++ b/metric_entropy_duality_counterexamples_v2.txt
@@ -1,997 +1,521 @@
-METRIC ENTROPY DUALITY: A COUNTEREXAMPLE
-A self-contained proof for readers comfortable with basic linear algebra
-
-
-WHAT THIS DOCUMENT SHOWS
-
-The duality conjecture for metric entropy says that passing to polar
-bodies preserves "covering complexity" up to universal constants. We
-disprove it. For every proposed pair of universal constants a,b >= 1,
-we build one 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).
-
-Here N(A,B) is the least number of translates of B that cover A. The
-dimension n grows with a and b; we make no claim in fixed dimension.
-
-How to read this. Sections 1-3 set up the question and state the plan.
-Sections 4-7 prove the four pieces and assemble them. Section 8 gives
-one consequence. Every step is proved from scratch; no external results
-are assumed.
-
-
-1. THE QUESTION
-
-1.1 Covering numbers.
-
-Let A and B be bounded sets in a real vector space; B has nonempty
-interior. Let N(A,B) be the smallest number of translates x + B whose
-union contains A. The centers x are arbitrary: they need not lie in A.
-
-Covering numbers measure complexity. A set that needs many small
-translates is complicated; one that needs few is simple.
-
-Example: covering a disk of radius R by translates of a square of side
-2 needs roughly R^2 copies. The exact count is N(disk, square).
-
-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.
-
-The polar of an origin-symmetric convex body K in R^n is
-
- K^o = { y in R^n : <x, y> <= 1 for every x in K }.
-
-It is another origin-symmetric convex body. It lists the linear
-functionals that are at most 1 on K.
-
-Example: for the cube L = [-1,1]^n, L^o = { y : sum_i |y_I| <= 1 }, the
-diamond (cross-polytope).
-
-1.3 The duality conjecture.
-
-Fix origin-symmetric convex bodies K, L in R^n. The duality conjecture
-for metric entropy asks whether there are absolute constants a,b >= 1,
-independent of n, K, L, such that for every such pair
-
- (1/b) log N(L^o, a K^o) <= log N(K,L)
- <= b log N(L^o, a^{-1} K^o).
-
-This is Conjecture 1 of Artstein-Milman-Szarek (2004), who attribute
-the operator-theoretic origin to Pietsch (1972).
-
-In words: covering K by copies of L should be roughly the same task as
-covering L^o by copies of K^o, after a universal change of scale a and
-a universal multiplicative loss b.
-
-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 (a,b). We
-prove Theorem 1 in Section 7, and one consequence for convexified
-packing in Section 8.
-
-
-2. NOTATION
-
-All logarithms are natural. binom(n,k) = n(n-1)...(n-k+1)/k! is the
-usual binomial coefficient.
-
-For a finite set S:
-
- B_infty^S = [-1,1]^S = { f : S -> R : |f(s)| <= 1 for all s }
- B_1^S = { lambda in R^S : sum_{s in S} |lambda_s| <= 1 }
- ||f||_{infty,S} = max_{s in S} |f(s)|.
-
-If X, Y are finite sets and g_y : X -> R for each y in Y, then
-R_x = (g_y(x))_{y in Y} in R^Y is the row at x, and
-f_lambda = sum_{y in Y} lambda_y g_y : X -> R is a column combination.
-
-For a finite set of vectors V, absconv(V) is the convex hull of V
-together with -V. Equivalently, absconv(V) consists of all finite sums
-sum_j lambda_j v_j with v_j in V and sum_j |lambda_j| <= 1.
-
-In a graph on a finite set X:
-- graph distance d(x,z) is the fewest edges in a path from x to z;
-- if no such path exists, d(x,z) = infinity.
-
-A partition of X is a map L : X -> Sigma. The set Sigma is the label
-set; two points are in the same class if their labels agree.
-
-Over a field, the integer
-
- D_j = binom(r+j-1, j)
-
-counts multisets of size j drawn from an r-element set.
-
-We write [u] = {1, 2, ..., u}.
-
-
-3. THE STRATEGY
-
-We build a real matrix whose entries lie in [0,1] and whose rows and
-columns have opposite behavior:
-
- (A) many rows, pairwise at sup-norm distance at least 1;
- (B) a small uniform-approximation list for the absolutely convex
- hull of the columns.
-
-Section 4 turns such a matrix into a pair of convex bodies with the
-covering bounds we want. Property (A) makes N(K,L) large; property (B)
-makes N(L^o, a^{-1} K^o) small.
-
-Then we produce such a matrix.
-
-Columns come from partitions. Each partition L_i : X -> Sigma_i
-compresses X to at most q labels. Using a family T of partitions and
-the graph distances d_T, we build profiles phi_h(d_T(x,v)) as columns.
-A uniform approximation argument (Section 5) shows that the
-nonnegative combinations of these columns can be approximated by a
-list whose size Q depends on q and u but not on |X|.
-
-Rows come from finite fields. Take X = Sym^h(F_p^r), the space of
-symmetric h-linear forms. The number of rows is p^{D_h}. Each
-partition is contraction by a fixed direction and has only p^{D_{h-1}}
-labels. Taking r >> h makes D_{h-1}/D_h = h/(r+h-1) small. Choosing
-the directions carefully (Section 6) makes every two distinct rows
-separated by distance > h in some graph, so a single column separates
-them by exactly 1.
-
-Section 7 chooses (theta, h, r, p) in their order of dependence and
-combines the pieces to defeat any proposed (a,b). Section 8 extracts
-the convexified-packing consequence.
-
-
-4. FROM A MATRIX TO CONVEX BODIES
-
-This section is purely geometric. Far-apart rows force many translates;
-a small column list gives a small cover of the polar.
-
-Lemma 4.1 (matrix-to-body conversion).
-Let X, Y be finite nonempty sets. For each y in Y let g_y : X -> R.
-Set
-
- R_x = (g_y(x))_{y in Y},
- f_lambda = sum_{y in Y} lambda_y g_y,
- F = { f_lambda : sum_{y in Y} |lambda_y| <= 1 }.
-
-Suppose:
-
- (i) ||R_x - R_{x'}||_{infty,Y} >= 1 for all distinct x, x' in X;
- (ii) there is a finite list of M functions on X such that every f in
- F is within eps (in the sup norm on X) of a list function.
- (The list functions need not belong to F.)
-
-For t > 0 set K = 3 absconv{R_x : x in X} + t B_infty^Y and
-L = B_infty^Y. Then K, L are origin-symmetric convex bodies with
-nonempty interior in R^Y, and
-
- N(K, L) >= |X|,
- N(L^o, (6 eps + 2 t) K^o) <= M.
-
-Proof.
-
-Bodies. absconv{R_x} is compact, convex, symmetric, and contains 0.
-Adding t B_infty^Y makes K contain a small ball, so K has nonempty
-interior. L is a cube, so it has nonempty interior.
-
-First inequality. Each point 3 R_x lies in K, and for x != x',
-
- ||3 R_x - 3 R_{x'}||_{infty,Y} >= 3.
-
-Any translate of L has sup-diameter at most 2. Indeed, if a, b are in
-z + L then a - b is in L - L = 2 L, so ||a - b||_{infty,Y} <= 2. So
-one translate of L can contain at most one of the points 3 R_x. At
-least |X| translates are required.
-
-Second inequality. The support function
-
- h_K(delta) = sup_{z in K} <z, delta>
-
-equals 3 max_x |<R_x, delta>| + t sum_y |delta_y|. Indeed, <.,delta>
-attains its maximum over the finite set {+-R_x} at one of those
-vectors, and over B_infty^Y its maximum is sum_y |delta_y| (attained by
-choosing the sign of each coordinate). The Minkowski sum lets the two
-maxima add. Since <R_x, delta> = f_delta(x),
-
- h_K(delta) = 3 ||f_delta||_{infty,X} + t ||delta||_1.
-
-The polar of the cube is the diamond: L^o = B_1^Y.
-
-Now use the list. Order its M entries. For each lambda in B_1^Y
-assign lambda to the first list function A with
-||f_lambda - A||_{infty,X} <= eps. Hypothesis (ii) ensures that at
-least one such function exists. This partitions B_1^Y into at most M
-nonempty clusters; pick one coefficient vector lambda^(k) in B_1^Y
-from each nonempty cluster.
-
-For any lambda in the same cluster as lambda^(k),
-
- ||f_lambda - f_lambda^(k)||_{infty,X} <= 2 eps,
- ||lambda - lambda^(k)||_1 <= 2.
-
-The second bound holds because both vectors are in B_1^Y:
-||lambda - lambda^(k)||_1 <= ||lambda||_1 + ||lambda^(k)||_1 <= 1 + 1.
-
-Set delta = lambda - lambda^(k). Then
-
- h_K(delta)
- = 3 ||f_lambda - f_lambda^(k)||_{infty,X}
- + t ||lambda - lambda^(k)||_1
- <= 3(2 eps) + t(2)
- = 6 eps + 2 t.
-
-By definition of the polar and positive homogeneity of h_K,
-
- delta in c K^o iff h_K(delta) <= c (c > 0).
-
-So each cluster sits inside lambda^(k) + (6 eps + 2 t) K^o. The at
-most M translates cover B_1^Y = L^o, which is exactly
-N(L^o, (6 eps + 2 t) K^o) <= M.
-
-Done.
-
-4.1 How the lemma is used.
-
-For proposed a, b >= 1, it suffices to build a matrix and eps, t > 0
-with
-
- log |X| > b log M, 6 eps + 2 t <= a^{-1}.
-
-Then the lemma gives N(K, L) >= |X| and N(L^o, a^{-1} K^o) <= M. So
-
- b log N(L^o, a^{-1} K^o)
- <= b log M
- < log |X|
- <= log N(K, L),
-
-which is the failure of the upper bound in the duality conjecture.
-
-
-5. COMPRESSION FROM PARTITIONS
-
-The engine of the proof: a matrix with many rows but a short column
-list.
-
-5.1 Setup.
-
-Let X be a finite nonempty set. Let u, q be positive integers and
-L_i : X -> Sigma_i (i = 1, ..., u) be partitions with |L_i(X)| <= q.
-
-Fix 0 < theta < 1 and a nonempty family T of subsets of [u] with
-
- |[u] \ T| <= theta u for every T in T.
-
-Call such T admissible.
-
-For T in T, put an edge between distinct x, z in X when
-L_i(x) = L_i(z) for some i in T. Let d_T be the graph distance, with
-d_T = infinity between different components.
-
-Choose a positive integer h with log 3 / log(h+1) <= theta, and put
-s = ceil(1/theta). Define the logarithmic profile
-
- phi_h(d) = max{0, 1 - log(d+1) / log(h+1)} for d in {0,1,2,...},
- phi_h(infinity) = 0.
-
-So phi_h(0) = 1, phi_h(d) decreases in d, and phi_h(d) = 0 once
-d >= h.
-
-Set Y = X x T. For y = (v, T) in Y define g_y : X -> R by
-
- g_y(x) = phi_h(d_T(x, v)).
-
-All g_y take values in [0,1].
-
-For nonnegative coefficients mu_y with sum_y mu_y <= 1 define
-
- f_mu = sum_y mu_y g_y,
- F_+ = { f_mu : mu_y >= 0, sum_y mu_y <= 1 }.
-
-Goal: give a uniform approximation list for F_+ whose size depends only
-on h, theta, u, q -- not on |X|.
-
-5.2 The logarithmic profile.
-
-Lemma 5.1. For any h >= 1, the weights
-
- gamma_j = (log(j+2) - log(j+1)) / log(h+1) (j = 0, ..., h-1)
-
-are positive, sum to 1, and for every d in {0, 1, 2, ...} union
-{infinity},
-
- (a) phi_h(d) = sum_{j=0}^{h-1} gamma_j 1_{d <= j};
- (b) sum_{j=0}^{h-1} gamma_j 1_{d <= 3j+2} <= phi_h(d) + log 3 / log(h+1).
-
-Here 1_{...} denotes the indicator: 1 if the condition holds, 0
-otherwise.
-
-Proof.
-
-Positivity is clear. Telescoping gives sum_{j=0}^{h-1} gamma_j =
-(log(h+1) - log 1) / log(h+1) = 1.
-
-Part (a). If d >= h (including d = infinity), both sides are zero. If
-0 <= d < h, the sum runs from j = d to h-1 and equals
-(log(h+1) - log(d+1)) / log(h+1) = phi_h(d).
-
-Part (b). Suppose d finite. On the left, index j contributes 1 iff
-d <= 3j+2. For j >= d, we have 3j+2 >= 3d+2 > d, so those j contribute
-to both sides. The extra indices on the left satisfy j < d and
-d <= 3j+2, that is,
-
- ceil((d-2)/3) <= j <= d-1.
-
-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},
-
-and its total gamma-weight is
-
- sum_{j=a_d}^{b_d} gamma_j
- = (log(b_d + 2) - log(a_d + 1)) / log(h+1).
-
-Since b_d + 2 <= d+1 and a_d + 1 >= (d+1)/3, this weight is at most
-
- (log(d+1) - log((d+1)/3)) / log(h+1) = log 3 / log(h+1).
-
-If the interval is empty, the contribution is zero. If d = infinity,
-all indicators on both sides vanish. Done.
-
-5.3 Uniform compression.
-
-Proposition 5.2 (uniform compression). In 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 A_f in A satisfying
-
- f(x) - 3 theta <= A_f(x) <= f(x) + theta (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},
- C_{h,theta,u} = log u + h s 2^u log(1 + s 2^u / theta).
-
-Proof.
-
-Fix representative maps rho_i : L_i(X) -> X with
-L_i(rho_i(sigma)) = sigma. These are chosen once and for all before any
-coefficient vector mu.
-
-Fix f = f_mu in F_+. For a subset S of Y write mu(S) = sum_{y in S} mu_y.
-
-(1) A common index. Averaging the admissible inequality 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.
-
-So some i_0 in [u] satisfies
-
- mu{(v,T) : i_0 not in T} <= theta.
-
-Keep columns in Y_0 = {(v,T) in Y : i_0 in T}; the discarded mass is
-at most theta. This single i_0 will be used at every level.
-
-(2) Bounded pivots at each level. Fix j in {0, ..., h-1}. For x in X
-set
-
- I_x = {(v,T) in Y_0 : d_T(x, v) <= j}.
-
-Starting from the empty union, repeatedly add some I_z whose mass
-outside the current union exceeds theta. If k_j sets are added, their
-successive contributions are each > theta, all disjoint from the
-previous union. Hence k_j theta < 1 and k_j <= s. The process stops at
-pivots z_{j,1}, ..., z_{j,k_j} with union
-
- U_j = union_{k=1}^{k_j} I_{z_{j,k}},
-
-satisfying mu(I_x \ U_j) <= theta for every x in X. (The empty case
-k_j = 0 is allowed.) Assign each column of U_j to the first pivot whose
-set contains it, and let kappa_j(y) in {1, ..., k_j} be its slot.
-
-(3) Label representatives. For a pivot z = z_{j,k}, keep the label
-L_{i_0}(z) and put z' = rho_{i_0}(L_{i_0}(z)). If y = (v,T) is
-assigned to this pivot then i_0 in T, d_T(v, z) <= j, and
-d_T(z, z') <= 1, hence
-
- d_T(v, z') <= j + 1.
-
-The triangle inequality at every x in X gives
-
- d_T(x, v) <= j ==> d_T(x, z') <= 2j + 1,
- d_T(x, z') <= 2j + 1 ==> d_T(x, v) <= 3j + 2.
-
-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 put
-
- f_{mu,j}(x) = sum_{y=(v,T) in Y} mu_y 1_{d_T(x, v) <= j}.
-
-By the first implication, A_j counts every column that f_{mu,j} counts
-and lies in U_j. The remaining columns of f_{mu,j} (either outside Y_0,
-or in I_x \ U_j) have total mass at most 2 theta. By the second
-implication, A_j only counts columns with d_T(x, v) <= 3j+2. Therefore
-
- f_{mu,j}(x) - 2 theta
- <= A_j(x)
- <= sum_{y=(v,T) in Y} mu_y 1_{d_T(x, v) <= 3j + 2}.
-
-(4) Combine levels. Let F = sum_{j=0}^{h-1} gamma_j A_j. By Lemma 5.1,
-f_mu = sum_j gamma_j f_{mu,j}. The lower bound above gives
-
- F >= f_mu - 2 theta.
-
-For the upper bound, apply part (b) of Lemma 5.1 to each distance
-d_T(x, v), multiply by mu_{(v,T)}, and sum over y. Since the total mass
-of mu is at most 1 and log 3 / log(h+1) <= theta,
-
- F <= f_mu + theta.
-
-Hence
-
- f_mu - 2 theta <= F <= f_mu + theta.
-
-(5) A finite encoding. The column center v disappears from A_j's
-indicators. Group U_j by (kappa, 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},
-
- w_{j,k,T} = sum_{v : (v,T) in U_j, kappa_j(v,T) = k} mu_{(v,T)}.
-
-Empty slots have zero weight and are padded with a fixed realized
-L_{i_0}-label. (Such a label exists because X is nonempty.) Each
-weight lies in [0,1], and there are at most M_0 = s 2^u weights at each
-level.
-
-Round each weight down to a multiple of delta = theta / M_0:
-
- 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 gamma_j tilde A_j. For each x in X,
-
- 0 <= A_j(x) - tilde A_j(x) <= M_0 delta = theta,
-
-and since sum_j gamma_j = 1,
-
- 0 <= F - A <= theta.
-
-Combined with (4),
-
- f_mu - 3 theta <= A <= f_mu + theta.
-
-(6) Counting one list. For fixed i_0 the following data determine A:
-the s pivot labels at each of the h levels, and the rounded weights.
-The label L_{i_0}(z_{j,k}) determines z'_{j,k} via rho_{i_0}; no
-original pivot or column center must be stored. There are at most
-q^{h s} choices of labels, and each rounded weight has at most
-
- floor(M_0 / theta) + 1 <= 1 + M_0 / theta
-
-possible values; there are h M_0 such weights.
-
-Enumerate all such choices for every i_0 in [u], allowing also codes
-that do not come from any coefficient vector. This gives a fixed finite
-list containing every approximant constructed above, of size
-
- 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 the maps
-rho_i are shared data; they are not extra choices per approximant. Done.
-
-5.4 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,
- F = { f_lambda : lambda in B_1^Y }
- = absconv{ g_y : y in Y }.
-
-Then a list of at most Q^2 functions approximates every f_lambda in F
-to uniform error 6 theta. Moreover B_1^Y can be partitioned into at
-most Q^2 nonempty clusters so that
-
- ||f_lambda - f_lambda'||_{infty,X} <= 12 theta
-
-whenever lambda, lambda' lie in the same cluster.
-
-Proof. Write lambda = lambda^+ - lambda^- with lambda_y^+ =
-max{lambda_y, 0} and lambda_y^- = max{-lambda_y, 0}. Each part is
-nonnegative and has total mass at most 1. By Proposition 5.2 there are
-A^+, A^- in A with
-
- ||f_{lambda^+} - A^+||_{infty,X} <= 3 theta,
- ||f_{lambda^-} - A^-||_{infty,X} <= 3 theta.
-
-So A^+ - A^- approximates f_lambda to error at most 6 theta, and there
-are at most Q^2 differences in A - A. Order this list and assign each
-lambda in B_1^Y to its first approximant with error <= 6 theta; the
-nonempty fibers form the partition. The triangle inequality gives the
-12 theta diameter bound. Done.
-
-
-6. FINITE-FIELD PARTITIONS AND SEPARATED ROWS
-
-We now build partitions L_i with few labels and with the extra feature
-that graph distances in a suitable admissible T separate every pair of
-rows.
-
-6.1 A zero bound.
-
-Lemma 6.1 (Schwartz-Zippel). Let P in F_p[z_1, ..., z_k] be a nonzero
-polynomial of total degree <= d; p prime; k, d >= 0. If U_1, ..., U_k
-are independent uniform in F_p, then
-
- Pr(P(U_1, ..., U_k) = 0) <= d / p.
-
-Proof. Induction on k.
-
-k = 0: P is a nonzero constant, probability 0.
-
-k >= 1: write P = sum_{j=0}^e P_j(z_1, ..., z_{k-1}) z_k^j with P_e
-nonzero. The total degree of P_e is at most d - e; induction bounds the
-probability that P_e vanishes by (d-e)/p. Conditioned on values of
-z_1, ..., z_{k-1} making P_e nonzero, the resulting polynomial in z_k
-has degree e and at most e roots (successive division by linear
-factors); the conditional zero probability is at most e/p. Sum: d/p.
-Done.
-
-6.2 Symmetric forms and their dimension.
-
-Fix r, h >= 1. Set D_j = binom(r+j-1, j) for j >= 0; this is the
-number of multisets of size j drawn from an r-element set.
-
-Let E = F_p^r. Write Sym^j(E^*) for the space of maps E^j -> F_p that
-are multilinear and invariant under permuting arguments. Set also
-Sym^0(E^*) = F_p.
-
-Any symmetric j-linear form is determined by its values on multisets of
-j basis vectors, and this determination is a bijection. So
-
- dim Sym^j(E^*) = D_j, |Sym^j(E^*)| = p^{D_j}.
-
-In particular X = Sym^h(E^*) has |X| = p^{D_h}, and every contraction
-
- L_i(x) = x(t_i, ., ..., .) (t_i in E fixed)
-
-is a symmetric (h-1)-linear form whose values lie in a space of size
-p^{D_{h-1}}. So L_i has at most q = p^{D_{h-1}} labels.
-
-Also
-
- D_{h-1} / D_h = h / (r + h - 1).
-
-So with r >> h, q is exponentially smaller than |X| in the log scale we
-care about.
-
-6.3 Directions with nonvanishing evaluations.
-
-Proposition 6.2 (robust directions). Let 0 < theta < 1 and r, h >= 1.
-Put w = 2 D_h and u = ceil(h w / theta). Let p be a prime with
-
- p > max{ h, h^2 u^{2h} }.
-
-There exist t_1, ..., t_u in E = F_p^r with the following property: for
-every nonzero Z in Sym^h(E^*) there is a set T subset [u] with
-|[u] \ T| <= theta u and
-
- Z(t_{i_1}, ..., t_{i_h}) != 0 for all (i_1, ..., i_h) in T^h.
-
-Repeated indices are allowed.
-
-Proof.
-
-Choose t_1, ..., t_u independently and uniformly in E. Fix a nonzero Z.
-
-Diagonal polynomial. Write z = sum_a z_a e_a. Then
-
- P_Z(z_1, ..., z_r) = Z(z, ..., z)
- = sum_{alpha_1 + ... + alpha_r = h}
- (h! / prod_j alpha_j!)
- Z(e_1^{[alpha_1]}, ..., e_r^{[alpha_r]})
- z_1^{alpha_1} ... z_r^{alpha_r},
-
-where e_a^{[alpha_a]} means e_a 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, and distinct multisets
-give distinct monomials. So P_Z is a nonzero polynomial of total degree
-h.
-
-Every tuple zero probability. For an ordered tuple
-i = (i_1, ..., i_h) in [u]^h, let S(i) = {i_1, ..., i_h}. The
-expression Z(t_{i_1}, ..., t_{i_h}) is a polynomial of total degree h in
-the scalars of the vectors with indices in S(i); it is nonzero because
-setting all those vector variables equal to z recovers P_Z. Lemma 6.1
-gives
-
- Pr(Z(t_{i_1}, ..., t_{i_h}) = 0) <= h / p,
-
-and this applies to any pattern of repeated indices.
-
-Independence. For this Z, evaluations on tuples with pairwise disjoint
-supports depend on disjoint sets of independent vectors t_i, hence are
-independent.
-
-Union bound. There are at most u^{h w} ordered lists of w ordered
-h-tuples, and fewer than p^{D_h} nonzero forms Z. The probability that
-some Z admits 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.
-
-So with positive probability no such pair (Z, list) exists. Fix a
-choice of vectors for which it does not.
-
-Maximal disjoint family. For every 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 deleted is at most
-
- h(w - 1) < h w <= theta u.
-
-If a zero tuple were supported in T, its support would be disjoint from
-all the selected supports, contradicting maximality. Hence
-Z(t_{i_1}, ..., t_{i_h}) != 0 for every tuple from T. Since theta < 1,
-T is nonempty. Done.
-
-6.4 Separated rows.
-
-Proposition 6.3 (separated rows). With the parameters and directions
-of Proposition 6.2, define
-
- X = Sym^h(E^*),
- L_i(x) = x(t_i, ., ..., .),
- T = { T subset [u] : |[u] \ T| <= theta u }.
-
-Then |X| = m = p^{D_h}, each L_i has at most q = p^{D_{h-1}} labels,
-and for every distinct x, y in X there is T in T with
-
- d_T(x, y) > h.
-
-Consequently, for Y = X x T and the row vectors
-R_x = (g_{(v,T)}(x))_{(v,T) in Y} in R^Y,
-
- ||R_x - R_y||_{infty,Y} = 1 whenever x != y.
-
-Proof. |X| and q are as in Section 6.2.
-
-Fix distinct x, y in X and apply Proposition 6.2 to Z = y - x. Let T
-in T be the resulting set, so Z(t_{i_1}, ..., t_{i_h}) != 0 for every
-tuple from T.
-
-Suppose a path x = x_0, x_1, ..., x_k = y with 1 <= k <= h. For each
-edge choose i_j in T with L_{i_j}(x_j) = L_{i_j}(x_{j-1}), and put
-Delta_j = x_j - x_{j-1}. Then
-
- Delta_j(t_{i_j}, v_2, ..., v_h) = 0
-
-for all v_2, ..., v_h in E.
-
-Choose any i_* in T. Form the h-tuple
-
- (t_{i_1}, ..., t_{i_k}, t_{i_*}, ..., t_{i_*}) (h-k copies of t_{i_*}).
-
-Every Delta_j vanishes on this tuple: Delta_j is symmetric and one of
-its arguments is t_{i_j}. So Z = sum_j Delta_j also vanishes there,
-contradicting Proposition 6.2. Hence no such path exists and
-d_T(x, y) > h. (If x, y are in different components, d_T = infinity and
-the same bound holds.)
-
-Column separation. At the column (x, T): g_{(x,T)}(x) = phi_h(0) = 1
-and g_{(x,T)}(y) = phi_h(d_T(x, y)) = 0 because d_T(x, y) > h. All
-column values lie in [0,1], so ||R_x - R_y||_{infty,Y} = 1. Done.
-
-Remark. The family T contains every admissible subset and is fixed
-with the partitions. The separating T above may depend on (x, y); the
-common index i_0 in Proposition 5.2 may depend on the coefficient
-vector. Both behaviors are allowed.
-
-If h also satisfies log 3 / log(h+1) <= theta, the compression bound of
-Proposition 5.2 applies with q = p^{D_{h-1}} and s = ceil(1/theta),
-giving
-
- log Q <= h s D_{h-1} log p + C_{h,theta,u}.
-
-Once r, h, theta are fixed, so are u and C_{h,theta,u}. The prime p
-may still be taken arbitrarily large, subject only to the threshold in
-Proposition 6.2.
-
-
-7. PROOF OF THEOREM 1
-
-Fix a, b >= 1.
-
-7.1 Choices.
-
-Set
-
- theta = 1 / (1000 a), s = ceil(1/theta).
-
-Choose a positive integer h with log 3 / log(h+1) <= theta (possible
-since log(h+1) -> infinity). Choose a positive integer r with
-
- r + h - 1 > 8 b h^2 s.
-
-Define, for 0 <= j <= h,
-
- D_j = binom(r+j-1, j), w = 2 D_h, u = ceil(h w / theta),
-
-and set C = C_{h,theta,u} = log u + h s 2^u log(1 + s 2^u / theta).
-
-Finally choose a prime p satisfying
-
- p > max{ h, h^2 u^{2h}, exp(8 b C / D_h) }.
-
-Every quantity on the right is already fixed, so such a p exists.
-
-7.2 Apply the tools.
-
-Use Proposition 6.2 with these parameters, then Proposition 6.3. That
-gives the row space X = Sym^h(F_p^r) with
-
- m = |X| = p^{D_h} > 1,
-
-label sets of size at most q = p^{D_{h-1}}, columns indexed by
-Y = X x T with T = { T subset [u] : |[u] \ T| <= theta u }, and row
-vectors satisfying
-
- ||R_x - R_x'||_{infty,Y} = 1 for x != x'.
-
-Y is finite and nonempty. The finite field is used only to build the
-index and label sets; the matrix entries and the bodies below are real.
-
-By Proposition 5.2 the nonnegative column class has a 3 theta list of
-size Q with
-
- log Q <= h s log q + C
- = h s D_{h-1} log p + C.
-
-By Corollary 5.3 the absolutely convex column hull has a 6 theta
-approximation list of size at most Q^2.
-
-Apply Lemma 4.1 with eps = 6 theta and t = theta. It gives bodies in
-dimension n = |Y|:
-
- K = 3 absconv{R_x : x in X} + theta B_infty^Y, L = B_infty^Y,
-
-with
-
- N(K, L) >= m,
- N(L^o, 38 theta K^o) <= Q^2.
-
-The constant 38 is 6 eps + 2 t = 6(6 theta) + 2 theta. Since
-
- 38 theta = 38 / (1000 a) < a^{-1},
-
-replacing the covering body by a smaller one only makes the cover
-strictly easier:
-
- N(L^o, a^{-1} K^o) <= Q^2.
-
-7.3 Compare the entropies.
-
-The identity D_{h-1} / D_h = h / (r + h - 1) gives
-
- log(Q^2) / log m
- <= (2 h s D_{h-1} log p + 2 C) / (D_h log p)
- = 2 h s (D_{h-1}/D_h) + 2 C / (D_h log p)
- = 2 h^2 s / (r + h - 1) + 2 C / (D_h log p)
- < 1/(4b) + 1/(4b)
- = 1/(2b).
-
-The two strict inequalities follow from r + h - 1 > 8 b h^2 s and from
-p > exp(8 b C / D_h).
-
-Together with N(L^o, a^{-1} K^o) <= Q^2 and N(K, L) >= m > 1,
-
- b log N(L^o, a^{-1} K^o)
- <= b log(Q^2)
- < (1/2) log m
- < log m
- <= log N(K, L).
-
-Identifying R^Y with R^n makes L = [-1,1]^n and proves Theorem 1.
-
-7.4 An asymptotic form.
-
-The same estimates give a stronger asymptotic statement. Fix a >= 1,
-and hence theta, h, s. For each positive integer r, define D_h, u, C
-as above and choose a prime
-
- p > max{ h, h^2 u^{2h}, exp(r C / D_h) }.
-
+For bounded sets A and B in a real finite-dimensional space, with B having
+nonempty interior, let N(A, B) be the least number of translates of B whose
+union covers A; the translation centers may lie anywhere. This number is the
+resolution cost of describing A by copies of B. For an origin-symmetric convex
+body K the polar is K^o = { y : <x,y> <= 1 for every x in K }, again an
+origin-symmetric convex body. All logarithms are natural; the base affects
+only constants and is immaterial.
+
+Passing to the polar exchanges a body with the collection of linear
+functionals bounded by one on it. The duality conjecture for covering numbers
+asks whether this exchange preserves covering complexity up to a universal
+change of scale and a universal multiplicative factor. Pietsch posed the
+question in 1972 in operator-theoretic form. In the covering-number language
+the sharp form is the following.
+
+ Duality conjecture (Pietsch 1972; stated as Conjecture 1 by Artstein,
+ Milman, Szarek and Tomczak-Jaegermann). Do there exist constants a, b >= 1
+ such that, for every n and every pair of origin-symmetric convex bodies
+ K, L in R^n,
+ (1/b) log N(L^o, a K^o) <= log N(K, L) <= b log N(L^o, a^{-1} K^o)?
+
+Artstein, Milman, Szarek and Tomczak-Jaegermann record this as Conjecture 1,
+noting the operator-theoretic origin in Pietsch's 1972 work.
+
+Available at ./artstein-milman-szarek-tomczak-2004-entropy-duality-math0407238.pdf
+
+The right-hand inequality is the substantive half. The result below shows
+that it fails for every proposed pair of constants, already when L is a cube.
+
+ Main theorem. 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).
+
+The dimension n grows with a and b; no statement concerns a fixed dimension.
+Because the polar inequality can be forced to fail with L a cube, no universal
+(a, b) survives.
+
+The surrounding landscape fixes what is and is not already known. Konig and
+Milman proved that the n-th roots of the two covering numbers are comparable, which on the logarithmic scale leaves an additive error of
+order n. Bourgain, Pajor, Szarek and
+Tomczak-Jaegermann obtained entropy-number comparisons under geometric or
+sequence-regularity hypotheses, and estimates whose loss depends on the rank.
+Thus a single universal pair for all bodies and dimensions was open.
+
+Available at ./bourgain-pajor-szarek-tomczak-1989-duality-entropy-numbers-ihes-m89-01.pdf
+
+Artstein, Milman and Szarek settle the dimension-free conjecture when one of
+the two bodies is a Euclidean ball, and hence when either body is an
+ellipsoid. The comparison holds uniformly over symmetric convex bodies and
+over n whenever one side is Hilbertian.
+
+Available at ./artstein-milman-szarek-2004-duality-metric-entropy-math0407236.pdf
+
+ "... this verifies the duality conjecture for entropy numbers of linear
+ operators, posed by Pietsch in 1972, in the central case when either the
+ domain or the range of the operator is a Hilbert space."
+ (Artstein, Milman, Szarek)
+
+For arbitrary origin-symmetric bodies Emanuel Milman reduces the gap to
+logarithmic factors in the dimension, proving
+N(K, T) <= N(T^o, (C log n)^{-1} K^o)^{C log n log log n} with universal C.
+A loss that depends on n is compatible with the failure of a universal pair.
+
+Available at ./milman-2007-two-duality-relations-math0603461.pdf
+
+A parallel line concerns convexified packing. Artstein, Milman, Szarek and
+Tomczak-Jaegermann prove universal duality for a packing number whose new
+point must avoid the convex hull of earlier ones, and announce ordinary
+entropy duality for spaces whose K-convexity constant is bounded, with
+constants depending on that bound. Hu, Peale and Reingold study the dual
+covering numbers of function classes and obtain a comparison with an explicit
+prefactor depending on the approximation scale and the sup norms of the class.
+
+Available at ./hu-peale-reingold-2022-metric-entropy-duality-outcome-indistinguishability.pdf
+
+The construction also borrows two standard tools, each proved from scratch
+so that nothing is assumed. The finite-field argument uses the
+polynomial zero estimate of Schwartz and of Zippel, together with the
+diagonal (polarization) recovery of symmetric multilinear forms in
+characteristic exceeding the degree, due to Ferrero and Micali and, in a
+modern formulation, to Drapal and Vojtechovsky. Convex-hull approximation in
+the style of Maurey, as developed for small finite sets by Mendelson, is a
+third source of technique.
+
+Available at ./drapal-vojtechovsky-2009-symmetric-multilinear-forms-1509.05707.pdf
+Available at ./mendelson-2001-size-of-convex-hulls-small-sets.pdf
+
+The strategy is a real matrix whose rows and columns behave oppositely. The
+rows are pairwise at sup-norm distance at least one, so covering by a cube
+needs many translates. The absolutely convex hull of the columns admits a
+short uniform approximation list, so the dual cover is cheap. A matrix with
+these two features converts, by a support-function computation, into a body K
+with large N(K, L) and small N(L^o, a^{-1} K^o). The rows and the list are
+then built together, rows from symmetric multilinear forms over a finite
+field, columns from the graph distances attached to a family of partitions.
+
+Notation used throughout. For a finite set S write B_infty^S = [-1,1]^S =
+{f : S -> R : |f(s)| <= 1 for all s in S} and B_1^S = {lambda in R^S :
+sum_s |lambda_s| <= 1}; write ||f||_{infty,S} = max_s |f(s)|. For a finite
+set of vectors V, absconv(V) is the convex hull of V together with -V, that
+is, the set of sums sum_j lambda_j v_j with v_j in V and sum_j |lambda_j| <= 1.
+In a graph on a finite set, d(x, z) is the fewest edges in a path and equals
+infinity between distinct components. A partition of X is a map L : X -> Sigma;
+two points share a class when the labels agree. For integers r >= 1 and
+j >= 0, D_j = binom(r+j-1, j) counts multisets of size j drawn from an
+r-element set. Write [u] = {1, ..., u}.
+
+The geometric half is a conversion of a real matrix into a pair of bodies. It
+records exactly what the combinatorial constructions must achieve: many
+separated rows, and a short uniform approximation list for the absolutely
+convex hull of the columns.
+
+ Matrix-to-body lemma. Let X and Y be finite nonempty sets, and for each
+ y in Y let g_y : X -> R. Put R_x = (g_y(x))_{y in Y} in R^Y,
+ f_lambda = sum_{y in Y} lambda_y g_y, and F = { f_lambda :
+ sum_y |lambda_y| <= 1 }. Suppose (i) ||R_x - R_{x'}||_{infty,Y} >= 1 for
+ distinct x, x' in X, and (ii) for some eps > 0 there is a list of M
+ functions on X such that every f in F is within eps, in the sup norm on X,
+ of a list function; the list functions need not lie in F. For t > 0 set
+ K = 3 absconv{R_x : x in X} + t B_infty^Y and L = B_infty^Y. Then K and L
+ are origin-symmetric compact convex bodies with nonempty interior in R^Y,
+ the covering numbers may use arbitrary centers, and
+ N(K, L) >= |X|, N(L^o, (6 eps + 2 t) K^o) <= M.
+
+Proof. The set absconv{R_x} is the convex hull of the finitely many vectors
++R_x and -R_x, hence compact, convex, symmetric, and it contains zero. Adding
+t B_infty^Y keeps these properties and gives K nonempty interior in the full
+space. The cube L has the same properties.
+
+For the first inequality, each point 3 R_x lies in K, and distinct such
+points are at sup-distance at least 3. A translate of L = B_infty^Y has
+sup-diameter at most 2: if a and b lie in z + L then a - b lies in L - L = 2L
+and ||a - b||_{infty,Y} <= 2. So one translate of L meets the set
+{3 R_x : x in X} in at most one point, and N(K, L) >= |X|.
+
+For the second, the support function h_K(delta) = sup_{z in K} <z, delta>
+equals 3 max_x |<R_x, delta>| + t sum_y |delta_y|. A linear functional
+attains its maximum over the finite convex hull of {+R_x, -R_x} at one of
+those vectors, giving 3 max_x |<R_x, delta>|; over t B_infty^Y the maximum is
+t sum_y |delta_y|, attained by matching each sign; the two terms of the
+Minkowski sum are chosen independently, so the maxima add. Since
+<R_x, delta> = f_delta(x),
+ h_K(delta) = 3 ||f_delta||_{infty,X} + t ||delta||_1.
+The same cube computation gives L^o = B_1^Y = {lambda in R^Y :
+||lambda||_1 <= 1}.
+
+Order the M functions of the list. Assign each lambda in B_1^Y to the first
+list function within eps of f_lambda; hypothesis (ii) guarantees one exists.
+This splits B_1^Y into at most M nonempty clusters, and from each nonempty
+cluster one coefficient vector lambda^(k) in B_1^Y is selected. For lambda and
+lambda^(k) in the same cluster the triangle inequality gives
+||f_lambda - f_lambda^(k)||_{infty,X} <= 2 eps, while both vectors lie in
+B_1^Y, so ||lambda - lambda^(k)||_1 <= 1 + 1 = 2. With delta = lambda -
+lambda^(k),
+ h_K(delta) = 3 ||f_lambda - f_lambda^(k)||_{infty,X}
+ + t ||lambda - lambda^(k)||_1
+ <= 3 (2 eps) + t (2) = 6 eps + 2 t.
+For c > 0 positivity and positive homogeneity of h_K give the equivalence
+delta in c K^o if and only if h_K(delta) <= c. Hence each cluster lies in
+lambda^(k) + (6 eps + 2 t) K^o, and the at most M translates cover
+B_1^Y = L^o. This is the second inequality. Choosing the representatives
+inside the coefficient ball is what keeps the added cube under control even
+when the list functions themselves lie outside F.
+
+To defeat proposed constants a, b >= 1 it therefore suffices to build a
+matrix and numbers eps, t > 0 with
+ log |X| > b log M, 6 eps + 2 t <= a^{-1}.
+The lemma then gives N(K, L) >= |X| and, since a smaller covering body only
+makes a cover easier, N(L^o, a^{-1} K^o) <= M. Hence
+ b log N(L^o, a^{-1} K^o) <= b log M < log |X| <= log N(K, L),
+which is the failure of the upper bound. The rest of the argument produces the
+matrix and controls M.
+
+The compression engine takes a finite set carrying few-class partitions and
+returns a short uniform list for the nonnegative combinations of the column
+profiles built from the partition graphs. Its cost depends on the number of
+labels of a partition, never on the size of the underlying set.
+
+Setup for compression. Let X be a finite nonempty set, let u and q be positive
+integers, and let L_i : X -> Sigma_i, i in [u], be partitions with
+|L_i(X)| <= q. Fix 0 < theta < 1 and a nonempty family Tcal of subsets of [u]
+with |[u] \ T| <= theta u for every T in Tcal; call such T admissible. For
+T in Tcal form the undirected graph on X in which distinct x, z are adjacent
+when L_i(x) = L_i(z) for some i in T, and let d_T be its graph distance, with
+d_T = infinity between distinct components. Fix a positive integer h with
+log 3 / log(h+1) <= theta and put s = ceil(1/theta). Define the logarithmic
+profile
+ phi_h(d) = max{0, 1 - log(d+1)/log(h+1)} for d in {0,1,2,...},
+ phi_h(infinity) = 0,
+so phi_h(0) = 1, phi_h decreases, and phi_h(d) = 0 once d >= h. With
+Y = X x Tcal, for y = (v, T) define g_y : X -> R by g_y(x) = phi_h(d_T(x, v));
+all values lie in [0,1]. For nonnegative coefficients mu_y with
+sum_y mu_y <= 1 put f_mu = sum_y mu_y g_y and F_+ = { f_mu : mu_y >= 0,
+sum_y mu_y <= 1 }. The aim is a uniform approximation list for F_+ whose size
+depends only on h, theta, u, q.
+
+ Logarithmic-profile lemma. For h >= 1 the weights
+ gamma_j = (log(j+2) - log(j+1)) / log(h+1), for j = 0, ..., h-1, are
+ positive and sum to 1, and for every d in {0,1,2,...} together with
+ 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),
+ where 1{...} is the indicator of the bracketed condition.
+
+Proof. Positivity is clear and the weights telescope to
+(log(h+1) - log 1)/log(h+1) = 1. For the first identity, if d >= h, including
+d = infinity, both sides vanish; if 0 <= d < h the sum runs from j = d to
+h-1 and equals (log(h+1) - log(d+1))/log(h+1) = phi_h(d). For the second,
+take d finite. An index j satisfies d <= 3j + 2 exactly when
+j >= (d-2)/3; for j >= d one has 3j + 2 >= 3d + 2 > d, so those indices lie
+on both sides. The extra indices counted on the left are those with j < d and
+d <= 3j + 2, that is ceil((d-2)/3) <= j <= d - 1. 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}, whose gamma-weight is
+ sum_{j=a_d}^{b_d} gamma_j = (log(b_d+2) - log(a_d+1))/log(h+1).
+Because b_d + 2 <= d + 1 and a_d + 1 >= (d+1)/3, this is at most
+(log(d+1) - log((d+1)/3))/log(h+1) = log 3/log(h+1). An empty interval
+contributes zero, and d = infinity makes every indicator vanish.
+
+ Compression proposition. Under the setup above there is a finite list Acal
+ of real functions on X, of cardinality Q, such that every f in F_+ has
+ A in Acal with f(x) - 3 theta <= A(x) <= f(x) + theta for every x in X.
+ In particular ||f - A||_{infty,X} <= 3 theta, and the list can be chosen
+ 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).
+
+Proof. For each i fix a representative map rho_i : L_i(X) -> X with
+L_i(rho_i(sigma)) = sigma; these are fixed before any coefficient vector is
+chosen. Fix f = f_mu in F_+ and write mu(S) = sum_{y in S} mu_y for subsets S
+of Y.
+
+A common index. Averaging the admissibility 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.
+So some i_0 in [u] has mu{(v,T) : i_0 not in T} <= theta. Keep the columns in
+Y_0 = {(v,T) in Y : i_0 in T}; the discarded mass is at most theta. This i_0
+serves at every level.
+
+Bounded pivots. Fix j in {0, ..., h-1} and set
+I_x = {(v,T) in Y_0 : d_T(x,v) <= j} for x in X. Starting from the empty
+union, repeatedly add some I_z whose mass outside the current union exceeds
+theta. If k_j sets are added, the successive contributions each exceed
+theta and are disjoint from the previous union, so k_j theta < 1 and
+k_j <= s. The process stops at pivots z_{j,1}, ..., z_{j,k_j} with union
+U_j = union_{k=1}^{k_j} I_{z_{j,k}} such that mu(I_x \ U_j) <= theta for
+every x; the empty case k_j = 0 is allowed. Assign each column of U_j to the
+first pivot whose set contains it, with slot kappa_j(y) in {1, ..., k_j}.
+
+Label representatives. For a pivot z = z_{j,k} keep the single label
+L_{i_0}(z) and replace z by z' = rho_{i_0}(L_{i_0}(z)). If y = (v,T) is
+assigned to this pivot then i_0 in T, d_T(v,z) <= j, and d_T(z,z') <= 1, hence
+d_T(v,z') <= j + 1. The triangle inequality at any x gives the two
+implications d_T(x,v) <= j implies d_T(x,z') <= 2j + 1, and d_T(x,z') <= 2j+1
+implies d_T(x,v) <= 3j + 2. All distances involved are finite under the
+respective hypotheses, even when the graph is disconnected. Define
+ A_j(x) = sum_{y=(v,T) in U_j} mu_y * 1{d_T(x, z'_{j,kappa_j(y)}) <= 2j+1},
+and for comparison f_{mu,j}(x) = sum_{y=(v,T) in Y} mu_y * 1{d_T(x,v) <= j}.
+By the forward implication A_j counts every column that f_{mu,j} counts and
+lies in U_j; the remaining columns of f_{mu,j}, either outside Y_0 or in
+I_x \ U_j, carry total mass at most 2 theta. By the backward implication A_j
+counts only columns with d_T(x,v) <= 3j + 2. Therefore
+ f_{mu,j}(x) - 2 theta <= A_j(x)
+ <= sum_{y=(v,T) in Y} mu_y * 1{d_T(x,v) <= 3j + 2}.
+
+Combine the levels. Put Fp = sum_{j=0}^{h-1} gamma_j A_j. The first identity
+of the profile lemma gives f_mu = sum_j gamma_j f_{mu,j}, so the lower bound
+above yields Fp >= f_mu - 2 theta. For the upper bound apply the second
+identity to each distance d_T(x,v), multiply by mu_{(v,T)}, and sum: since the
+total mass is at most one and log 3/log(h+1) <= theta,
+ f_mu - 2 theta <= Fp <= f_mu + theta.
+
+A finite encoding. The center v no longer appears in A_j's indicators.
+Grouping U_j by (kappa, T),
+ A_j(x) = sum_{k=1}^s sum_{T in Tcal} w_{j,k,T}
+ * 1{d_T(x, z'_{j,k}) <= 2j+1},
+ w_{j,k,T} = sum_{v : (v,T) in U_j, kappa_j(v,T)=k} mu_{(v,T)}.
+Empty slots carry weight zero and are padded with a fixed realized
+L_{i_0}-label, which exists because X is nonempty. Each weight lies in [0,1]
+and there are at most M_0 = s 2^u weights at each level. Round each weight
+down to a multiple of delta = theta/M_0, writing
+tilde w_{j,k,T} = delta floor(w_{j,k,T}/delta). Let tilde A_j be A_j with the
+rounded weights and A = sum_j gamma_j tilde A_j. Every indicator is at most
+one, so 0 <= A_j(x) - tilde A_j(x) <= M_0 delta = theta for every x, and since
+the gamma_j sum to one, 0 <= Fp - A <= theta. With the previous interval,
+ f_mu - 3 theta <= A <= f_mu + theta.
+
+Counting one list. For fixed i_0 the data determining A are the s pivot labels
+at each of the h levels and the rounded weights. The label L_{i_0}(z_{j,k})
+determines z'_{j,k} through rho_{i_0}, so no original pivot or column center
+is stored. There are at most q^{h s} choices of labels, each rounded weight
+takes at most floor(M_0/theta) + 1 <= 1 + M_0/theta values, and there are at
+most h M_0 weights. Enumerating these choices for every i_0 in [u], allowing
+also codes not arising from any coefficient vector, gives a fixed finite list
+containing every approximant, of size
+ Q <= u q^{h s} (1 + s 2^u / theta)^{h s 2^u}.
+Taking logarithms yields the stated bound. The graphs and the maps rho_i are
+shared data, not extra choices per approximant.
+
+ Signed-compression corollary. In the same setup put f_lambda =
+ sum_{y in Y} lambda_y g_y, B_1^Y = {lambda in R^Y : sum_y |lambda_y| <= 1},
+ and F = {f_lambda : lambda in B_1^Y} = absconv{g_y : y in Y}. Then a list
+ of at most Q^2 functions approximates every f_lambda in F to uniform error
+ 6 theta, and B_1^Y splits into at most Q^2 nonempty clusters with
+ ||f_lambda - f_lambda'||_{infty,X} <= 12 theta for lambda, lambda' in the
+ same cluster.
+
+Proof. Write lambda = lambda^+ - lambda^- with lambda_y^+ = max{lambda_y, 0}
+and lambda_y^- = max{-lambda_y, 0}; each part is nonnegative of total mass at
+most one. The compression proposition supplies A^+, A^- in Acal with
+||f_{lambda^+} - A^+||_{infty,X} <= 3 theta and
+||f_{lambda^-} - A^-||_{infty,X} <= 3 theta, so A^+ - A^- approximates
+f_lambda to within 6 theta. The differences A^+ - A^- range over at most Q^2
+functions; ordering the list and assigning each lambda in B_1^Y to the first
+approximant within 6 theta yields at most Q^2 nonempty fibers, and the
+triangle inequality gives the 12 theta diameter. The approximants need not
+lie in F, while the clusters are genuine coefficient vectors in B_1^Y.
+
+The rows come from symmetric multilinear forms over a finite field. Two
+ingredients are needed: a zero estimate for polynomials, and directions on
+which every nonzero form stays nonzero across a large product set.
+
+ Zero-counting lemma. Let p be prime and let P in F_p[z_1, ..., z_k] be a
+ nonzero polynomial of total degree at most d, with k, d >= 0. 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. For k = 0 the polynomial is a nonzero constant and the
+probability is zero. For k >= 1 write P = sum_{j=0}^{e} P_j(z_1, ..., z_{k-1})
+z_k^j with P_e nonzero. The total degree of P_e is at most d - e, so by
+induction P_e vanishes with probability at most (d - e)/p. Conditioned on
+values of z_1, ..., z_{k-1} that keep P_e nonzero, the resulting polynomial in
+z_k has degree e and at most e roots, found by pulling out linear factors one at
+a time, so its conditional zero probability is at most e/p. The two bounds add
+to d/p. The case e = 0, including a nonzero constant, is covered.
+
+Symmetric forms. Fix r, h >= 1, a prime p, and E = F_p^r. Write Sym^j(E^*) for
+the maps E^j -> F_p that are multilinear and invariant under permuting
+arguments, with Sym^0(E^*) = F_p. Relative to a basis a symmetric j-linear form
+is determined by its values on multisets of j basis vectors, and this
+determination is a bijection, so
+ dim Sym^j(E^*) = D_j = binom(r+j-1, j), |Sym^j(E^*)| = p^{D_j}.
+In particular X = Sym^h(E^*) has |X| = p^{D_h}. A fixed direction t in E gives
+the contraction L_t(x) = x(t, ., ..., .), a symmetric (h-1)-linear form, so its
+values lie in a set of size p^{D_{h-1}} and a label map built from one direction
+has at most q = p^{D_{h-1}} labels. The exact ratio is
+ D_{h-1}/D_h = h/(r + h - 1),
+so with r large against h the label set is exponentially smaller than the row
+set on the logarithmic scale.
+
+ Robust-directions proposition. Let 0 < theta < 1 and r, h >= 1. Put
+ w = 2 D_h and u = ceil(h w/theta), and let p be a prime with
+ p > max{h, h^2 u^{2h}}. There exist t_1, ..., t_u in E = F_p^r such that,
+ for every nonzero Z in Sym^h(E^*), some T subset [u] with |[u] \ T| <=
+ theta u satisfies Z(t_{i_1}, ..., t_{i_h}) != 0 for every (i_1, ..., i_h) in
+ T^h; tuples may repeat indices.
+
+Proof. Choose t_1, ..., t_u independently and uniformly in E and fix a nonzero
+Z. For z = sum_a z_a e_a the diagonal value is
+ P_Z(z_1, ..., z_r) = Z(z, ..., z)
+ = sum_{alpha_1 + ... + alpha_r = h} (h! / prod_j alpha_j!)
+ Z(e_1^{[alpha_1]}, ..., e_r^{[alpha_r]}) z_1^{alpha_1} ... z_r^{alpha_r},
+where e_a^{[alpha_a]} means e_a repeated alpha_a times among the arguments. At
+least one displayed value of Z is nonzero, every multinomial coefficient is
+nonzero in F_p because p > h, and distinct multisets give distinct monomials;
+so P_Z is a nonzero polynomial of total degree h. This is the diagonal, or
+polarization, recovery of a symmetric multilinear form in characteristic
+exceeding the degree; the coordinate statement above is the precise form
+needed, and matches Ferrero and Micali and Drapal and Vojtechovsky.
+
+Available at ./drapal-vojtechovsky-2009-symmetric-multilinear-forms-1509.05707.pdf
+
+For an ordered tuple i = (i_1, ..., i_h) in [u]^h let S(i) = {i_1, ..., i_h}.
+The value Z(t_{i_1}, ..., t_{i_h}) is a polynomial of total degree h in the
+scalar coordinates of the vectors with indices in S(i), nonzero because setting
+all those vectors equal to z gives the nonzero P_Z. The zero-counting lemma
+gives Pr(Z(t_{i_1}, ..., t_{i_h}) = 0) <= h/p for any pattern of repeated
+indices. For this fixed Z, evaluations on tuples whose supports are pairwise
+disjoint depend on disjoint subsets of the independent vectors t_i, so those
+zero events are independent. There are at most u^{h w} ordered lists of w
+ordered h-tuples and fewer than p^{D_h} nonzero forms Z, so 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,
+using w = 2 D_h and p > h^2 u^{2h}. The count covers all forms over the field
+with no independence needed between different forms. Fix a choice of directions
+for which this event fails.
+
+For each nonzero Z take a family of zero tuples with pairwise disjoint supports
+that is maximal under inclusion; it has at most w - 1 tuples. Delete the union
+of the supports and let T be the remaining indices. The number deleted is at
+most h(w-1) < h w <= theta u, so |[u] \ T| <= theta u. If a zero tuple were
+supported in T, its support would be disjoint from all the chosen ones,
+contradicting maximality. Hence Z is nonzero on every tuple from T^h, and T is
+nonempty because theta < 1. No sampled vector was required to be distinct or
+nonzero.
+
+ Separated-rows proposition. With the parameters and directions of the
+ robust-directions proposition, set X = Sym^h(E^*), the label map
+ L_i(x) = x(t_i, ., ..., .), and Tcal = {T subset [u] : |[u] \ T| <= theta u}.
+ Then |X| = p^{D_h}, each L_i has at most q = p^{D_{h-1}} labels, and for
+ every distinct x, y in X there is T in Tcal with d_T(x, y) > h.
+ Consequently, with Y = X x Tcal and R_x = (g_{(v,T)}(x))_{(v,T) in Y} in
+ R^Y, the rows satisfy ||R_x - R_y||_{infty,Y} = 1 whenever x != y.
+
+Proof. The cardinality and label bound are as computed. Fix distinct x, y and
+apply the robust-directions proposition to Z = y - x, getting T in Tcal with Z
+nonzero on every tuple from T^h. Suppose a path x = x_0, x_1, ..., x_k = y with
+1 <= k <= h. For each edge pick i_j in T with L_{i_j}(x_j) = L_{i_j}(x_{j-1}),
+and put Delta_j = x_j - x_{j-1}. Then Delta_j(t_{i_j}, v_2, ..., v_h) = 0 for
+all v_2, ..., v_h in E. Pick any i_* in T and form the h-tuple made of
+t_{i_1}, ..., t_{i_k} followed by h - k copies of t_{i_*}. Each Delta_j
+vanishes on this tuple, being symmetric with argument t_{i_j}, so
+Z = sum_j Delta_j vanishes there too; all entries lie in T, contradicting the
+nonvanishing. Hence no such path exists and d_T(x, y) > h; vertices in
+different components have infinite distance and already obey the bound. For the
+column (x, T) the profile gives g_{(x,T)}(x) = phi_h(0) = 1 and
+g_{(x,T)}(y) = phi_h(d_T(x, y)) = 0, while every value lies in [0,1], so the sup
+distance between R_x and R_y is exactly one.
+
+With q = p^{D_{h-1}} and s = ceil(1/theta), valid once log 3/log(h+1) <= theta,
+the compression bound reads
+ log Q <= h s D_{h-1} log p + C_{h,theta,u}.
+The family Tcal holds every admissible subset and is fixed with the partitions;
+the separating T may depend on the pair (x, y), and the common index i_0 in the
+compression proof may depend on the coefficient vector. Both dependencies are
+allowed.
+
+Everything is now assembled. Fix a, b >= 1 and choose the parameters in
+order of dependence so the field size can absorb the encoding term.
+
+ Proof of the main theorem. Set theta = 1/(1000 a) and s = ceil(1/theta).
+ Choose a positive integer h with log 3/log(h+1) <= theta, possible since
+ log(h+1) grows without bound. Choose a positive integer r with
+ r + h - 1 > 8 b h^2 s. Put D_j = binom(r+j-1, j) for 0 <= j <= h,
+ w = 2 D_h, and 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 then fixed. Choose a prime p with
+ p > max{ h, h^2 u^{2h}, exp(8 b C/D_h) }.
+ Every quantity on the right is already determined, and primes exceed any
+ finite bound.
+
+ Apply the robust-directions proposition with these parameters and then the
+ separated-rows proposition. The row set is X = Sym^h(F_p^r) with
+ m = |X| = p^{D_h} > 1, each label map has at most q = p^{D_{h-1}} labels,
+ the columns are indexed by Y = X x Tcal with Tcal = {T subset [u] :
+ |[u]\T| <= theta u}, and the real row vectors obey
+ ||R_x - R_{x'}||_{infty,Y} = 1 for distinct x, x'. The set Y is finite and
+ nonempty, and the finite field serves only to build the index and label sets;
+ the matrix entries and the bodies below are real.
+
+ By the compression proposition the nonnegative column class has a 3 theta
+ list of size Q with log Q <= h s log q + C = h s D_{h-1} log p + C, and by
+ the signed-compression corollary the absolutely convex column hull has a
+ 6 theta list of at most Q^2 functions. Apply the matrix-to-body lemma with
+ eps = 6 theta and t = theta. It produces origin-symmetric bodies in
+ dimension n = |Y|,
+ K = 3 absconv{R_x : x in X} + theta B_infty^Y, L = B_infty^Y,
+ with
+ N(K, L) >= m, N(L^o, 38 theta K^o) <= Q^2,
+ since 6 eps + 2 t = 6(6 theta) + 2 theta = 38 theta. Because
+ 38 theta = 38/(1000 a) < a^{-1}, and a smaller covering body only makes the
+ cover easier,
+ N(L^o, a^{-1} K^o) <= Q^2.
+
+ It remains to compare the two entropies. The identity D_{h-1}/D_h =
+ h/(r + h - 1) gives
+ log(Q^2)/log m
+ <= (2 h s D_{h-1} log p + 2 C)/(D_h log p)
+ = 2 h s (D_{h-1}/D_h) + 2 C/(D_h log p)
+ = 2 h^2 s/(r + h - 1) + 2 C/(D_h log p)
+ < 1/(4b) + 1/(4b) = 1/(2b),
+ the two strict inequalities following from r + h - 1 > 8 b h^2 s and from
+ p > exp(8 b C/D_h). With N(L^o, a^{-1} K^o) <= Q^2 and N(K, L) >= m > 1,
+ b log N(L^o, a^{-1} K^o) <= b log(Q^2) < (1/2) log m < log m
+ <= log N(K, L).
+ Identifying R^Y with R^n makes L = [-1,1]^n and gives the failure of the
+ claimed bound for the arbitrary proposed constants a, b.
+
+The same estimates give an asymptotic form. Fix a >= 1, and hence theta, h, 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(r C/D_h) }.
The resulting bodies K_r, 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 as r -> infinity.
-
-Both u and C are fixed before p is chosen; no upper bound on the
-resulting dimension is needed.
-
-
-8. A CONSEQUENCE FOR CONVEXIFIED PACKING
-
-There is a stronger notion of "packing" that is also useful.
-
-8.1 Definition.
-
-For a nonempty bounded set T and an origin-symmetric convex body B,
-let Mhat(T, B) be the largest length m of an ordered sequence
-x_1, ..., x_m in T with
-
- (x_j + int B) intersect conv{x_i : i < j} = empty, 1 <= j <= m.
-
-(The first convex hull is the empty set.) Each new point must lie
-outside the convex hull of its predecessors, even after enlarging them
-by int B.
-
-8.2 Separation from convexified packing.
-
-Corollary 8.1. For every A, C >= 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) > C log Mhat(K, L/A).
-
-Proof.
-
-Step 1 (Mhat controls covers by quarter-bodies). Claim: an ordered
-B-convexly separated sequence has at most one point in any translate of
-B/4.
-
-Suppose i < j and both x_i, x_j lie in z + B/4. Then x_j - x_i lies in
-B/4 - B/4 = B/2. Since B is origin-symmetric and convex with 0 in int B,
-every point of B/2 is a convex combination of 0 (interior) and a point
-of B, hence lies in int B. So x_j - x_i lies in int B, equivalently
-x_i lies in x_j + int B. But x_i lies in conv{x_l : l < j}, contradicting
-the separation condition. Hence
-
- Mhat(T, B) <= N(T, B/4).
-
-Step 2 (convexified duality). Apply Theorem 2 of Artstein-Milman-
-Szarek-Tomczak-Jaegermann (2004) to the bodies K and L/A:
-
- 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 middle equality uses Mhat(c T, c B) = Mhat(T, B) for c > 0. The
-last inequality applies Step 1 with T = L^o and B = K^o/(2A).
-
-Step 3 (apply Theorem 1). Choose K, L from Theorem 1 with a = 8A and
-b = 2C. Then
-
- log N(K, L) > 2 C log N(L^o, K^o/(8A)).
-
-Combining with Step 2,
-
- log Mhat(K, L/A) <= 2 log N(L^o, K^o/(8A)),
-
-so
-
- C log Mhat(K, L/A)
- <= 2 C log N(L^o, K^o/(8A))
- < log N(K, L).
-
-Done.
-
-
-9. THE WHOLE PROOF AT A GLANCE
-
-One sentence: separated rows make covering numbers large; a short column
-list makes the polar covering number small; finite fields give both at
-once.
-
-The steps:
-
- 1. N(A, B) is the least number of translates of B that cover A. The
- polar K^o is the body of linear functionals bounded by 1 on K.
-
- 2. The duality conjecture asks whether N(K, L) and N(L^o, K^o) are
- comparable up to universal constants. Theorem 1 says no: for every
- a, b >= 1 there are K, L in some R^n with L a cube and
- log N(K, L) > b log N(L^o, a^{-1} K^o).
-
- 3. Lemma 4.1: many 1-separated rows force N(K, L) large; a small
- eps-list for the column hull forces N(L^o, (6 eps + 2 t) K^o)
- small.
-
- 4. Proposition 5.2: with u partitions of X, each having at most q
- labels, the nonnegative column class has a 3 theta list of size Q
- with log Q <= h s log q + C_{h,theta,u}. Corollary 5.3 covers
- signed coefficients: a 6 theta list of size Q^2.
-
- 5. Section 6: with X = Sym^h(F_p^r),
- |X| = p^{D_h}, q = p^{D_{h-1}}, D_{h-1}/D_h = h/(r+h-1).
- Taking r large makes q small relative to |X| on the log scale, and
- Section 6.3 separates every pair of rows.
-
- 6. Section 7 chooses parameters so log(Q^2)/log|X| < 1/(2b). Then
- b log N(L^o, a^{-1} K^o) <= b log(Q^2) < log m <= log N(K, L),
- which is Theorem 1.
-
- 7. Section 8 reuses the same K, L to separate ordinary entropy from
- convexified packing.
-
-9.1 Where this fits.
-
-The duality problem goes back to Pietsch (1972). Konig and Milman (1987)
-compared the nth roots of the two covering numbers; Bourgain, Pajor,
-Szarek, Tomczak-Jaegermann (1989) proved entropy-number comparisons
-under geometric or sequence-regularity assumptions. Artstein, Milman,
-Szarek (2004) proved dimension-free duality when one body is a
-Euclidean ball; Artstein, Milman, Szarek, Tomczak-Jaegermann (2004)
-proved universal duality for convexified packing and announced ordinary
-entropy duality for spaces with bounded K-convexity constant. Emanuel
-Milman (2007) proved a comparison with logarithmic losses in both the
-scale and the entropy factor; Hu, Peale, Reingold (2022) studied dual
-covering numbers of function classes with explicit scale-dependent
-prefactors.
-
-Theorem 1 says that none of these dimension- or scale-dependent
-estimates can be upgraded to a single universal pair (a, b).
-
-
-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] M. Ferrero, A. Micali.
- Sur les n-applications.
- Memoires de la Societe Mathematique de France 59 (1979), 33-53.
-
-[11] A. Drapal, P. Vojtechovsky.
- Symmetric multilinear forms and polarization of polynomials.
- Linear Algebra and its Applications 431 (2009), 998-1012.
-
-END OF DOCUMENT
+ 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.
+Both u and C are fixed before p is chosen, and no upper bound on the resulting
+dimension is required.
+
+Convexified packing. For a nonempty bounded set T and an origin-symmetric
+convex body B, let Mhat(T, B) be the largest m for which there is an ordered
+sequence x_1, ..., x_m in T with
+ (x_j + int B) intersect conv{x_i : i < j} = empty for 1 <= j <= m,
+the first convex hull being empty. This count is at least an ordinary packing
+count, since each new point must avoid the convex hull of its predecessors.
+
+ Convexified-packing corollary. For every A >= 1 and every g >= 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) > g log Mhat(K, L/A).
+
+Proof. Step 1: a B-convexly separated sequence has at most one point in each
+translate of B/4. If i < j and both x_i, x_j lie in z + B/4, then x_j - x_i
+lies in B/4 - B/4 = B/2, and because B is origin-symmetric and convex with 0
+in its interior every point of B/2 lies in int B; then x_i lies in
+x_j + int B while also x_i lies in conv{x_l : l < j}, contradicting the
+separation. Hence Mhat(T, B) <= N(T, B/4).
+
+Step 2: the universal convexified-packing duality of Artstein, Milman, Szarek
+and Tomczak-Jaegermann, applied to the bodies K and L/A, states
+ Mhat(K, L/A) <= Mhat((L/A)^o, K^o/2)^2.
+Since (L/A)^o = A L^o and simultaneous dilation preserves Mhat,
+ Mhat(K, L/A) <= Mhat(A L^o, K^o/2)^2 = Mhat(L^o, K^o/(2A))^2
+ <= N(L^o, K^o/(8A))^2,
+the last step being Step 1 with T = L^o and B = K^o/(2A).
+
+Available at ./artstein-milman-szarek-tomczak-2004-entropy-duality-math0407238.pdf
+
+Step 3: choose K, L from the main theorem with a = 8A and b = 2g. Then
+log N(K, L) > 2g log N(L^o, K^o/(8A)). Together with Step 2,
+ log Mhat(K, L/A) <= 2 log N(L^o, K^o/(8A)),
+ g log Mhat(K, L/A) <= 2g log N(L^o, K^o/(8A)) < log N(K, L),
+which is the corollary.