1 Introduction
For bounded sets A,B in a finite-dimensional real vector space, with B having nonempty interior, let N(A,B) denote the least number of translates of B that cover A. The translation vectors may lie anywhere in the ambient space. For an origin-symmetric convex body K\subset\R^n, its polar is
Here a convex body is compact and has nonempty interior. All logarithms are natural.
The duality conjecture for metric entropy, originating in Pietsch’s operator-theoretic work in 1972, asks whether there are absolute constants a,b\ge1 such that
for every dimension and every pair of origin-symmetric convex bodies K,L; see [AMST04, Conjecture 1]. It asks whether passing to the polar pair preserves covering complexity up to universal changes of scale and multiplicative constants.
We disprove the full conjecture.
Theorem 1.1. For every a,b\ge1, there are a positive integer n and an origin-symmetric convex body K\subset\R^n such that, with L=[-1,1]^n,
Thus the upper bound in (1.1) fails for every proposed pair of absolute constants. In particular, the two-sided duality conjecture has a negative answer. The bodies in Theorem 1.1 have nonempty interior in the full ambient dimension. Their dimensions grow with the parameters; no assertion about a fixed dimension is intended.
1.1 Related work
The question developed from the duality problem for entropy numbers of operators; Artstein, Milman and Szarek give the geometric and operator formulations in [AMS04, pp. 1314–1315] and attribute the original problem to Pietsch’s 1972 work. Early progress already showed that polarity controls covering numbers in several regimes. König and Milman proved a comparison of the nth roots of the two covering numbers [KM87, Theorem 1]; on the logarithmic scale this allows an additive error proportional to n. Bourgain, Pajor, Szarek and Tomczak-Jaegermann established entropy-number comparisons under geometric and sequence-regularity assumptions, as well as estimates with losses depending on the rank [BPST89].
Artstein, Milman and Szarek proved the dimension-free conjecture when one body is a Euclidean ball, and hence when either body is an ellipsoid [AMS04, Theorem 1]. Artstein, Milman, Szarek and Tomczak-Jaegermann proved universal duality for convexified packing [AMST04, Theorem 2]. This quantity uses an ordered sequence of points: the interior of the translate centered at each new point must avoid the convex hull of its predecessors. That requirement is stronger than pairwise separation and differs from the ordinary covering number in (1.1). They also announced ordinary entropy duality for spaces whose K-convexity constant is bounded, with the comparison constants depending on that bound [AMST04, Theorem 5]; see also the later derivation in [Mil07, Section 2]. A bound for each individual finite-dimensional space does not provide one pair of constants for all spaces and dimensions.
For arbitrary symmetric convex bodies, Emanuel Milman obtained a comparison with logarithmic losses in both the scale and the entropy factor [Mil07, Corollary 1.2]. Connections with learning theory provide another perspective: Hu, Peale and Reingold study dual covering numbers of function classes, obtaining a comparison with an explicit prefactor depending on the approximation scale and the uniform bounds of the function classes [HPR22, Theorem 11]. These dimension- or scale-dependent estimates are compatible with the failure of a universal pair a,b.
The column approximation in this paper also belongs to the broader study of entropy of convex hulls. For example, Mendelson develops finite-set convex-hull estimates in L_2(\mu) using Maurey’s approximation method [Men01, Section 2.1]. Here the approximation is uniform over all row coordinates and uses the special partition structure: labels replace the original centers in the finite encoding. The finite-field side uses the polynomial zero estimate associated with Schwartz and Zippel [Sch80, Zip79], together with diagonal recovery of symmetric multilinear forms in sufficiently large characteristic [FM79, DV09]. We prove the precise elementary forms of these tools and the additional compression and separation arguments below.
Theorem 1.1 also separates ordinary covering entropy from convexified-packing entropy, even after a fixed change of scale; Corollary 5.1 states and proves this consequence after the construction.
1.2 The construction and its main mechanism
The proof starts with a finite real matrix whose entries lie in [0,1]. Its rows are pairwise separated by one in the sup norm, while the absolutely convex hull of its columns admits a small uniform approximation list. A direct support-function calculation converts these two properties into large primal entropy and small polar entropy.
The approximation statement is the reusable part of the argument. Suppose a finite set carries u partitions, each with at most q classes. For a subset T of the partition indices, join two points whenever they belong to the same class in one partition indexed by T. We consider the resulting graph distances d_T, allowing infinite distance between components. For a positive integer cutoff h, define the profiles
with value zero at infinite distance. The columns consist of these profiles over all centers v and over a family of sets T, each omitting only a small fraction of the partitions.
Proposition 3.2 gives a uniform approximation of every nonnegative combination of these columns whose coefficients sum to at most one. For a given combination, averaging finds one partition present in all but a small amount of coefficient mass. At each distance level, a greedy selection of a bounded number of pivots captures all but a small residual mass at every point. Each pivot can then be replaced by a fixed representative of its class in the common partition. This replacement requires storing a label, rather than a point of the original set.
The replacement enlarges the relevant distance radii from j to at most 3j+2. The logarithmic profile bounds the error caused by this enlargement by \log3/\log(1+h), uniformly over all columns and all graph components. After grouping weights by pivot slot and by T, the approximation count depends on q through a fixed power. It does not depend on the number of possible column centers through an additional factor. Both the choice of the common partition and all grouped weights are included in the count. Splitting a signed coefficient vector into its positive and negative parts then gives an approximation list for the absolutely convex column hull, with twice the full error of the nonnegative approximation and the square of the list size.
To obtain separated rows, we use symmetric h-linear forms on \F_p^r, where p is a sufficiently large prime and r is a positive integer. A probabilistic choice of directions ensures that, for every nonzero form, one can delete a small fraction of the directions so that no evaluation on a remaining h-tuple vanishes, including tuples with repetitions. Contraction with one direction supplies a partition. A short path in the associated graph would express a nonzero form as a sum of forms killed by the directions along the path, contradicting the nonvanishing property.
There are p^{D_h} rows but at most p^{D_{h-1}} labels in each partition, where D_j=\binom{r+j-1}{j} for j\ge0. The ratio
tends to zero as r grows with h fixed. All remaining encoding costs are fixed before the prime p is chosen. Taking p sufficiently large therefore makes those costs negligible. This order of choices is what allows the compression result and the separation construction to produce a failure of dimension-free entropy duality.
Section 2 first proves the matrix-to-body conversion, which serves as the construction target. Section 3 then establishes uniform compression for an arbitrary admissible family of partitions. Section 4 constructs the finite-field partitions and proves row separation. Finally, Section 5 chooses the parameters and applies the conversion to defeat any proposed universal constants, then derives the convexified-packing consequence. All arguments needed for the construction are included.
1.3 Notation
For a finite set S, write
The sup norm on functions on S is denoted by \|\cdot\|_{\infty,S}. For a finite collection of vectors, \absconv denotes the convex hull of the vectors and their negatives. A uniform \varepsilon-approximation list may have centers outside the class being approximated; actual centers in the coefficient ball will be chosen in Lemma 2.1. We write [u]=\{1,\ldots,u\}.
2 The matrix construction target
The geometric part of the argument is an elementary conversion of a real matrix into a pair of convex bodies. It specifies exactly what the two combinatorial constructions must achieve: many separated rows and a small uniform approximation list for the absolutely convex hull of the columns. The small cube added to the row hull ensures nonempty interior without losing the polar covering estimate.
Lemma 2.1 (Matrix-to-body conversion). Let X and Y be finite nonempty sets, and let g_y\colon X\to\R, y\in Y, be real functions. Write
Suppose that
and that, for some \varepsilon>0, there is a list of M functions on X such that every member of \mathcal F is within \varepsilon of a function on the list in the uniform norm. The functions on the list need not belong to \mathcal F. For t>0, set
Then K,L are origin-symmetric compact convex bodies with nonempty interior in \R^Y, and
Both covering numbers use arbitrary ambient translation centers.
Proof. The hull \absconv\{R_x:x\in X\} is the convex hull of the finitely many vectors \pm R_x. It is compact, convex, and symmetric, and contains zero. Thus K has the same three properties and contains tB_\infty^Y, which gives it nonempty interior in the full ambient space. The corresponding properties of L are immediate.
Each point 3R_x belongs to K, and two distinct such points have uniform distance at least 3. Every translate of L has uniform diameter 2, whatever its center. Hence it contains at most one of these |X| points. This proves the first inequality in (2.1).
For the polar estimate, the support function h_K(\delta)=\sup_{z\in K}\langle z,\delta\rangle is exactly
Indeed, a linear functional attains its maximum over the finite convex hull at one of the vectors \pm R_x. Its maximum over B_\infty^Y is \sum_y|\delta_y|, attained by choosing the sign of each coordinate. The two choices in the Minkowski sum are independent, so their maxima add. The same cube calculation gives
Order the approximating list. Assign each \lambda\in B_1^Y to the first list function within \varepsilon of f_\lambda, thereby partitioning B_1^Y into at most M nonempty clusters. From each nonempty cluster choose one actual vector \lambda^{(k)}\in B_1^Y. For any \lambda in that cluster, the triangle inequality gives
Consequently (2.2) implies
For every c>0, the definition of the polar and positive homogeneity give the equivalence
Each cluster is therefore contained in \lambda^{(k)}+(6\varepsilon+2t)K^\circ. These at most M translates cover B_1^Y=L^\circ, proving the second inequality. Selecting representatives inside the coefficient ball is what controls the contribution of the added cube, even when the original list functions lie outside \mathcal F.
For proposed constants a,b\ge1, the lemma reduces the problem to finding a matrix and positive numbers \varepsilon,t for which
Indeed, increasing the polar covering body preserves the cover supplied by the lemma. The next two sections construct the matrix. The compression argument controls M through the number of labels in a partition; the finite-field construction makes that number small relative to the row count on the logarithmic scale.
3 Uniform compression from partitions
We first prove an approximation result for an arbitrary family of partitions of a finite set. Its cost depends on the number of labels of a partition, whereas the underlying set can be much larger.
Let X be a finite nonempty set, let u,q be positive integers, and let
Fix 0<\theta<1 and a nonempty family \mathcal T of subsets of [u] such that
In particular, every T\in\mathcal T is nonempty. For each such T, form the undirected graph on X in which distinct vertices x,z are adjacent when L_i(x)=L_i(z) for some i\in T. Write d_T(x,z) for its graph distance, with distance \infty between different components.
Choose a positive integer h such that
Define the logarithmic profile
Set Y=X\times\mathcal T. For y=(v,T)\in Y, define the column function
Thus 0\le g_y\le1. For nonnegative coefficients of total mass at most one, write
For a function f:X\to\R, let \|f\|_{\infty,X}=\max_{x\in X}|f(x)|.
We seek a uniform approximation list for \mathcal F_+ whose size is controlled by h,\theta,u,q, rather than |X|. The next lemma expresses each profile as a weighted sum of graph-ball indicators and bounds the error caused by enlarging their radii from j to 3j+2.
Lemma 3.1 (Logarithmic profile). For any positive integer h, the weights
are positive, sum to one, and satisfy, for every d\in\{0,1,2,\ldots\}\cup\{\infty\},
Proof. Positivity and the identity \sum_j\gamma_j=1 follow by telescoping. If 0\le d<h, the sum in (3.4) runs from j=d to j=h-1 and equals
If d\ge h, including d=\infty, both sides are zero.
For finite d, the extra indices counted on the left of (3.5) satisfy j<d\le3j+2. When this index set is nonempty, it is the integer interval from
Since b_d+2\le d+1 and a_d+1\ge(d+1)/3, its weight is
An empty interval contributes zero. If d=\infty, all the indicators vanish. This also covers all distances at and beyond the cutoff h.
Proposition 3.2 (Uniform compression). Under the hypotheses above, there is a finite list \mathcal A of real-valued functions on X, of cardinality Q, such that every f\in\mathcal F_+ has an approximant A\in\mathcal A satisfying
In particular, \|f-A\|_{\infty,X}\le3\theta. The list can be chosen with
Proof. For each i\in[u], fix a representative map
These maps are fixed for the entire approximation problem, before any coefficient vector is chosen.
A common index. Fix f=f_\mu\in\mathcal F_+, and use \mu(S)=\sum_{y\in S}\mu_y for subsets S\subseteq Y. Averaging (3.1) gives
Choose i_0\in[u] for which the omitted mass is at most \theta, and retain the columns in
This one index will serve at every level j.
A bounded number of pivots at each level. Fix j\in\{0,\ldots,h-1\} and, for x\in X, let
Starting 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 give k_j\theta<1; in particular k_j\le s. The process therefore terminates with pivots z_{j,1},\ldots,z_{j,k_j} and union
The empty choice is allowed. Assign every column of U_j to the first pivot whose set contains it, and denote its assigned slot by \kappa_j(y).
For a pivot z=z_{j,k}, retain only its label L_{i_0}(z), and replace it 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)\le j, and d_T(z,z')\le1. Consequently,
For every x\in X, the triangle inequality now gives the two implications
All distances used in these triangle inequalities are finite under their respective hypotheses, even if the graph is disconnected. Figure 1 illustrates the two bounds.
(a) Keeping an assigned match
(b) Controlling the extra matches
Figure 1: The two triangle inequalities in the compression step. The pivot z is replaced by its fixed label representative z'. The diagrams show schematic graph paths; the labels are upper bounds on their lengths. The logarithmic profile controls the enlargement to radius 3j+2.
Write z'_{j,k}=\rho_{i_0}(L_{i_0}(z_{j,k})) and define
For comparison, let
Every assigned column counted by f_{\mu,j}(x) is counted by A_j(x), by (3.9). The other columns counted by f_{\mu,j}(x) have total mass at most 2\theta: at most \theta lies outside Y_0, and at most \theta lies in I_x\setminus U_j. Conversely, (3.10) bounds every column counted by A_j(x). Hence
Combining the levels. Let F=\sum_{j=0}^{h-1}\gamma_jA_j. By (3.4), f_\mu=\sum_j\gamma_jf_{\mu,j}. Thus the lower bound in (3.11) gives F\ge f_\mu-2\theta. For the upper bound, apply (3.5) separately to each distance d_T(x,v) and sum with weights \mu_{(v,T)}. Since the total mass is at most one and \log3/\log(h+1)\le\theta, this yields the pointwise interval
A finite encoding. The center v of an assigned column no longer occurs in its indicator in A_j. Grouping columns by assigned slot and by T gives exactly
where
Unused slots have all weights zero and are padded with a fixed realized L_{i_0}-label. Such a label exists because X is nonempty. Each weight belongs to [0,1], and there are at most M_0=s2^u weights at each level. Round each weight down to a multiple of \delta=\theta/M_0, writing
Let \widetilde A_j be (3.13) with these rounded weights, and put A=\sum_j\gamma_j\widetilde A_j. Since every indicator is at most one,
The weights \gamma_j sum to one, so 0\le F-A\le\theta. Together with (3.12), this proves (3.6).
It remains to count one list that works for all \mu. For fixed i_0, the data determining A are the s pivot labels at each of the h levels and the rounded weights in (3.13). The label determines z'_{j,k} through the fixed map \rho_{i_0}, so no original pivot or column center must also be specified. There are at most q^{hs} choices of labels. Each rounded weight has at most
possible values, and there are at most hM_0 such weights. Enumerate these choices for every i_0\in[u], allowing also codes that do not arise from a coefficient vector. This gives a fixed finite list of functions containing every approximant constructed above, with
Taking logarithms proves (3.7). The graphs and the representative maps are shared data defining this list; they are not additional choices for each approximant.
The family \mathcal T and all the graphs are fixed before applying Proposition 3.2. The common index i_0 may depend on the coefficient vector. No separation assumption on X, and no choice of a single distinguished member of \mathcal T, enters the argument.
Corollary 3.3 (Signed compression). With the notation of Proposition 3.2, put
and
There is a list of at most Q^2 functions which approximates every member of \mathcal F to uniform error 6\theta. Moreover, B_1^Y can be partitioned into at most Q^2 nonempty clusters such that
whenever \lambda,\lambda' belong to the same cluster.
Proof. Write \lambda=\lambda^+-\lambda^-, where \lambda_y^+=\max\{\lambda_y,0\} and \lambda_y^-=\max\{-\lambda_y,0\}. Each part is nonnegative and has total mass at most one. Apply Proposition 3.2 to choose A^+,A^-\in\mathcal A with
Then A^+-A^- approximates f_\lambda to error at most 6\theta. There are at most Q^2 differences in \mathcal A-\mathcal 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, and the triangle inequality proves (3.14). The approximating functions need not belong to \mathcal F; the clusters themselves consist of actual coefficient vectors in B_1^Y.
4 Finite-field partitions and separated rows
We now construct partitions with few labels for which the functions of Section 3 separate every pair of rows. The construction has two steps. First, we choose directions so that, for each nonzero symmetric multilinear form, one can make a form-dependent deletion of a small fraction of the directions and obtain nonzero evaluations on every tuple of remaining directions. Second, these remaining directions obstruct short paths in the corresponding partition graph.
We use the standard total-degree polynomial zero estimate [Sch80, Corollary 1]; related early work on randomized polynomial evaluation is due to Zippel [Zip79]. We include the precise finite-field statement and its elementary proof.
Lemma 4.1 (Polynomial zero bound). Let P\in\F_p[z_1,\ldots,z_k] be a nonzero polynomial of total degree at most d, where k,d are nonnegative integers and p is prime. If U_1,\ldots,U_k are independent and uniform in \F_p, then
Proof. We induct on k. When k=0, the polynomial is a nonzero constant, and its zero probability is zero. For k\ge1, write
The total degree of P_e is at most d-e, so the induction hypothesis bounds the probability that this leading coefficient vanishes by (d-e)/p. Conditional on any values of the first k-1 variables for which it does not vanish, the resulting univariate polynomial has degree e and at most e roots, by successive division by linear factors. Its conditional zero probability is therefore at most e/p. The sum of these two bounds is d/p. This argument also covers e=0 and, in particular, all nonzero constant polynomials.
For positive integers r,h, set
If E=\F_p^r, write \operatorname{Sym}^j(E^*) for the space of maps E^j\to\F_p that are multilinear and invariant under permutations of their arguments. We interpret \operatorname{Sym}^0(E^*) as \F_p. Relative to a basis e_1,\ldots,e_r, a symmetric j-linear form is specified freely by its values on multisets of j basis vectors. The number of such multisets is D_j. Thus
Proposition 4.2 (Directions with nonvanishing evaluations). Let 0<\theta<1 and let r,h be positive integers. Put
and let p be any prime satisfying
There exist t_1,\ldots,t_u\in E=\F_p^r such that, for every nonzero Z\in\operatorname{Sym}^h(E^*), there is a set T\subseteq[u] with |[u]\setminus T|\le\theta u for which
Tuples in this assertion may have repeated indices.
Proof. Choose t_1,\ldots,t_u independently and uniformly in E. Fix a nonzero form Z. For z=\sum_{a=1}^r z_a e_a, its diagonal polynomial is
where 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 displayed multinomial coefficient is nonzero in \F_p. Distinct multisets give distinct monomials, so P_Z is a nonzero polynomial of total degree h. This is the diagonal recovery of a symmetric multilinear form when h! is invertible; see [FM79, Corollary 1.2] and [DV09, Proposition 3.3]. The coordinate argument above gives the precise fact needed here.
For an ordered tuple \mathbf i=(i_1,\ldots,i_h)\in[u]^h, let \supp(\mathbf i)=\{i_1,\ldots,i_h\}. The expression Z(t_{i_1},\ldots,t_{i_h}), considered as a polynomial in the scalar coordinates of the vectors with indices in \supp(\mathbf i), has total degree h and is nonzero: setting all those vector variables equal to z gives the nonzero polynomial (4.5). Lemma 4.1 therefore gives
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^{hw} ordered lists of w ordered h-tuples, and 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
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 deleted is at most
If any zero tuple were supported in T, its support would be disjoint from all the selected supports, contradicting maximality. Thus (4.4) holds. Since \theta<1, the set T is nonempty. The construction imposed no requirement that the sampled vectors be distinct or nonzero.
Proposition 4.3 (Partitions with separated rows). With the parameters and directions of Proposition 4.2, let
and let \mathcal T=\{T\subseteq[u]:|[u]\setminus T|\le\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 3, every pair of distinct x,y\in X has some T\in\mathcal T satisfying
Consequently, for Y=X\times\mathcal T and R_x=(g_{(v,T)}(x))_{(v,T)\in Y}\in\R^Y, the rows satisfy
Proof. The cardinality of X follows from (4.1). 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 4.2 to Z=y-x. Let T\in\mathcal 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
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
Choose any i_*\in T, and form the h-tuple consisting of t_{i_1},\ldots,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 (4.4). This proves (4.8); vertices in different components have infinite distance and already satisfy it.
At the column (x,T), the logarithmic profile gives g_{(x,T)}(x)=1 and 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 (4.9).
The family \mathcal 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 3.2, whose common index may depend on the particular convex combination of columns. If h also satisfies \log3/\log(h+1)\le\theta, the compression bound applies with q=p^{D_{h-1}} and s=\lceil1/\theta\rceil, giving
Once r,h,\theta are fixed, so are u and C_{h,\theta,u}; the prime p can still be taken arbitrarily large subject to (4.3).
5 Choice of parameters and failure of duality
We now choose the parameters in their order of dependence. The field size is chosen last, so it can absorb the encoding term from Proposition 3.2.
Proof of Theorem 1.1. Fix a,b\ge1. Put
and choose a positive integer h with \log3/\log(h+1)\le\theta. Such an integer exists because \log(h+1) tends to infinity. Choose a positive integer r so that
As in Section 4, define
The number
is now fixed. Choose a prime p satisfying
All quantities on the right have already been determined, and primes exceed every finite bound.
Apply Proposition 4.2 with these parameters, and form the label maps and graph profiles in Proposition 4.3. The row index set X consists of the symmetric h-linear forms on \F_p^r, so
Each label map takes at most q=p^{D_{h-1}} values. The columns are indexed by Y=X\times\mathcal T, where
and the real row vectors satisfy
In particular, Y is a finite nonempty set. The finite field serves only to construct the indices and label maps; the matrix entries and the convex bodies below are real.
By Proposition 3.2, the positive column class has a uniform 3\theta approximation list of cardinality Q satisfying
Corollary 3.3 gives a uniform 6\theta approximation list of at most Q^2 functions for the absolutely convex column hull. Thus Lemma 2.1 applies with \varepsilon=6\theta and t=\theta. It gives admissible bodies in dimension n=|Y|,
such that
Since 38\theta=38/(1000a)<a^{-1}, increasing the covering body preserves this cover, and therefore
It remains to compare the two entropies. The exact identity
yields
where the strict inequalities follow respectively from (5.1) and (5.3). Combining (5.6) with N(K,L)\ge m>1 gives
Identifying \R^Y with \R^n makes L=[-1,1]^n and proves the claimed counterexample for the arbitrary proposed constants a,b.
The same estimate gives an asymptotic form of the conclusion. Fix a\ge1, and hence \theta,h,s. For each positive integer r, set D_h,u,C as above and choose a prime
The resulting bodies K_r,L_r satisfy
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.
5.1 A consequence for convexified packing
Theorem 1.1 also separates ordinary covering entropy from convexified-packing entropy. For a nonempty bounded set T and an origin-symmetric convex body B, let \widehat M(T,B) be the largest length of an ordered sequence x_1,\ldots,x_m\in T such that
with the first convex hull taken to be empty [AMST04, Section 2].
Corollary 5.1 (Separation from convexified packing). For every A,C\ge1, there are an integer n\ge1 and an origin-symmetric convex body K\subset\R^n such that, with L=[-1,1]^n,
Proof. An ordered B-convexly separated sequence has at most one point in each translate of B/4: two such points have difference in B/2\subset\operatorname{int}B, contradicting the separation condition. Consequently \widehat M(T,B)\le N(T,B/4), with no boundary ambiguity for covers by closed translates. The universal convexified duality bound [AMST04, Theorem 2], applied to K,L/A, gives
Here the equality uses simultaneous dilation of both arguments. Choose K,L by Theorem 1.1 with a=8A and b=2C. Taking logarithms in the displayed bound proves the corollary.
References
- [AMS04]S. Artstein, V. Milman, and S. J. Szarek. Duality of metric entropy. Annals of Mathematics, 159(3):1313–1328, 2004. doi:10.4007/annals.2004.159.1313, arXiv:math/0407236.
- [AMST04]S. Artstein, V. Milman, S. Szarek, and N. Tomczak-Jaegermann. On convexified packing and entropy duality. Geometric and Functional Analysis, 14(5):1134–1141, 2004. Numbered locators refer to arXiv:math/0407238v1. doi:10.1007/s00039-004-0486-3, arXiv:math/0407238v1.
- [BPST89]J. Bourgain, A. Pajor, S. J. Szarek, and N. Tomczak-Jaegermann. On the duality problem for entropy numbers of operators. In Geometric Aspects of Functional Analysis (1987–1988), pages 50–63, Springer, 1989. doi:10.1007/BFb0090048.
- [DV09]Aleš Drápal and Petr Vojtěchovský. Symmetric multilinear forms and polarization of polynomials. Linear Algebra and its Applications, 431(5–7):998–1012, 2009. arXiv:1509.05707, https://arxiv.org/abs/1509.05707.
- [FM79]Miguel Ferrero and Artibano Micali. Sur les n-applications. Mémoires de la Société Mathématique de France, 59:33–53, 1979. doi:10.24033/msmf.247.
- [HPR22]Lunjia Hu, Charlotte Peale, and Omer Reingold. Metric entropy duality and the sample complexity of outcome indistinguishability. In Sanjoy Dasgupta and Nika Haghtalab, editors, Proceedings of the 33rd International Conference on Algorithmic Learning Theory, pages 515–552, PMLR, 2022. https://proceedings.mlr.press/v167/hu22a.html.
- [KM87]H. König and V. D. Milman. On the covering numbers of convex bodies. In Geometrical Aspects of Functional Analysis, pages 82–95, Springer, 1987. doi:10.1007/BFb0078138.
- [Men01]Shahar Mendelson. On the size of convex hulls of small sets. Journal of Machine Learning Research, 2:1–18, 2001. https://www.jmlr.org/papers/v2/mendelson01a.html.
- [Mil07]Emanuel Milman. A remark on two duality relations. Integral Equations and Operator Theory, 57(2):217–228, 2007. doi:10.1007/s00020-006-1479-4, arXiv:math/0603461.
- [Sch80]J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980. doi:10.1145/322217.322225.
- [Zip79]Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, Symbolic and Algebraic Computation, pages 216–226, Springer, 1979. doi:10.1007/3-540-09519-5_73.