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) }.
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