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