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.
Concrete pictures ground the definitions. Covering a disk of radius R by
translations of one square of side two takes on the order of R^2 copies, so N
grows like the square of the radius. For the cube L = [-1,1]^n the polar is
L^o = { y in R^n : sum_i |y_i| <= 1 }, the cross-polytope and the unit ball of
the l1 norm, so polarity exchanges the sup norm and the l1 norm.
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.
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.