==== TABLE OF CONTENTS ====
Counterexamples-to-the-duality-conjecture-for-metric-entropy//01-introduction.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//02-matrix-contract.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//03-compression.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//04-partitions.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//05-counterexample.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//paper.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//pivot-comparison.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//preamble.tex
Counterexamples-to-the-duality-conjecture-for-metric-entropy//references.bib
===========================

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//01-introduction.tex ====
\section{Introduction}\label{sec: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
\[
 K^\circ=\{y\in\R^n:\langle x,y\rangle\le1
                    \text{ for every }x\in K\}.
\]
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
\begin{equation}\label{eq:duality-conjecture}
 \frac1b\log N(L^\circ,aK^\circ)
 \le \log N(K,L)
 \le b\log N(L^\circ,a^{-1}K^\circ)
\end{equation}
for every dimension and every pair of origin-symmetric convex bodies
$K,L$; see \cite[Conjecture~1]{AMSTJ2004}.
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.

\begin{theorem}\label{thm:main}
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$,
\[
 \log N(K,L)>b\log N(L^\circ,a^{-1}K^\circ).
\]
\end{theorem}

Thus the upper bound in \eqref{eq:duality-conjecture} fails for every
proposed pair of absolute constants. In particular, the two-sided
duality conjecture has a negative answer. The bodies in
Theorem~\ref{thm:main} have nonempty interior in the full ambient
dimension. Their dimensions grow with the parameters; no assertion
about a fixed dimension is intended.

\subsection{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 \cite[pp.~1314--1315]{AMS2004} and attribute the original
problem to Pietsch's 1972 work. Early progress already showed that
polarity controls covering numbers in several regimes. K\"onig and Milman
proved a comparison of the $n$th roots of the two covering numbers
\cite[Theorem~1]{KonigMilman1987}; 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 \cite{BPSTJ1989}.

Artstein, Milman and Szarek proved the dimension-free conjecture when
one body is a Euclidean ball, and hence when either body is an ellipsoid
\cite[Theorem~1]{AMS2004}. Artstein, Milman, Szarek and
Tomczak-Jaegermann proved universal duality for \emph{convexified packing}
\cite[Theorem~2]{AMSTJ2004}. 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 \eqref{eq:duality-conjecture}. They also announced ordinary entropy
duality for spaces whose K-convexity constant is bounded, with the
comparison constants depending on that bound
\cite[Theorem~5]{AMSTJ2004}; see also the later derivation in
\cite[Section~2]{Milman2007}. 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 \cite[Corollary~1.2]{Milman2007}. 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 \cite[Theorem~11]{HuPealeReingold2022}.
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
\cite[Section~2.1]{Mendelson2001}. 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 \cite{Schwartz1980,Zippel1979}, together with diagonal recovery
of symmetric multilinear forms in sufficiently large characteristic
\cite{FerreroMicali1979,DrapalVojtechovsky2009}. We prove the precise
elementary forms of these tools and the additional compression and
separation arguments below.

Theorem~\ref{thm:main} also separates ordinary covering entropy from
convexified-packing entropy, even after a fixed change of scale;
Corollary~\ref{cor:convexified-separation} states and proves this
consequence after the construction.

\subsection{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
\[
 x\longmapsto
 \max\left\{0,1-\frac{\log(1+d_T(x,v))}{\log(1+h)}\right\},
\]
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~\ref{prop:compression} 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
\[
 \frac{D_{h-1}}{D_h}=\frac{h}{r+h-1}
\]
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~\ref{sec:convex-bodies} first proves the matrix-to-body conversion,
which serves as the construction target. Section~\ref{sec:compression}
then establishes uniform compression for an arbitrary admissible family
of partitions. Section~\ref{sec:partitions} constructs the finite-field
partitions and proves row separation. Finally, Section~\ref{sec:parameters}
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.

\subsection{Notation}

For a finite set $S$, write
\[
 B_\infty^S=[-1,1]^S,\qquad
 B_1^S=\left\{\lambda\in\R^S:
                   \sum_{s\in S}|\lambda_s|\le1\right\}.
\]
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~\ref{lem:matrix-to-bodies}. We write $[u]=\{1,\ldots,u\}$.
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//01-introduction.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//02-matrix-contract.tex ====
\section{The matrix construction target}
\label{sec:convex-bodies}

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.

\begin{lemma}[Matrix-to-body conversion]
\label{lem:matrix-to-bodies}
Let $X$ and $Y$ be finite nonempty sets, and let
$g_y\colon X\to\R$, $y\in Y$, be real functions.  Write
\[
 R_x=(g_y(x))_{y\in Y}\in\R^Y,
 \qquad
 f_\lambda=\sum_{y\in Y}\lambda_y g_y,
 \qquad
 \mathcal F=\{f_\lambda:\|\lambda\|_1\le1\}.
\]
Suppose that
\[
 \|R_x-R_{x'}\|_\infty\ge1
 \quad\text{for all distinct }x,x'\in X,
\]
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
\[
 K=3\absconv\{R_x:x\in X\}+tB_\infty^Y,
 \qquad L=B_\infty^Y.
\]
Then $K,L$ are origin-symmetric compact convex bodies with nonempty
interior in $\R^Y$, and
\begin{equation}
\label{eq:matrix-body-bounds}
 N(K,L)\ge |X|,
 \qquad
 N\bigl(L^\circ,(6\varepsilon+2t)K^\circ\bigr)\le M.
\end{equation}
Both covering numbers use arbitrary ambient translation centers.
\end{lemma}

\begin{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
\eqref{eq:matrix-body-bounds}.

For the polar estimate, the support function
$h_K(\delta)=\sup_{z\in K}\langle z,\delta\rangle$ is exactly
\begin{equation}
\label{eq:row-support-function}
 h_K(\delta)
 =3\max_{x\in X}|\langle R_x,\delta\rangle|
     +t\sum_{y\in Y}|\delta_y|
 =3\|f_\delta\|_{\infty,X}+t\|\delta\|_1.
\end{equation}
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
\[
 L^\circ=B_1^Y=\{\lambda\in\R^Y:\|\lambda\|_1\le1\}.
\]

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
\[
 \|f_\lambda-f_{\lambda^{(k)}}\|_{\infty,X}
 \le2\varepsilon,
 \qquad
 \|\lambda-\lambda^{(k)}\|_1\le2.
\]
Consequently \eqref{eq:row-support-function} implies
\[
 h_K(\lambda-\lambda^{(k)})\le6\varepsilon+2t.
\]
For every $c>0$, the definition of the polar and positive homogeneity
give the equivalence
\[
 \delta\in cK^\circ
 \quad\Longleftrightarrow\quad h_K(\delta)\le c.
\]
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$.
\end{proof}

For proposed constants $a,b\ge1$, the lemma reduces the problem to finding
a matrix and positive numbers $\varepsilon,t$ for which
\[
 \log|X|>b\log M,
 \qquad 6\varepsilon+2t\le a^{-1}.
\]
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.
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//02-matrix-contract.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//03-compression.tex ====
\section{Uniform compression from partitions}
\label{sec:compression}

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
\[
  L_i:X\longrightarrow\Sigma_i,\qquad i\in[u]=\{1,\ldots,u\},
  \qquad |L_i(X)|\le q.
\]
Fix $0<\theta<1$ and a nonempty family $\mathcal T$ of subsets of $[u]$
such that
\begin{equation}
  |[u]\setminus T|\le\theta u\qquad(T\in\mathcal T).
  \label{eq:admissible-sets}
\end{equation}
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
\begin{equation}
  \frac{\log3}{\log(h+1)}\le\theta,
  \qquad s=\lceil1/\theta\rceil.
  \label{eq:compression-parameters}
\end{equation}
Define the logarithmic profile
\[
  \phi_h(d)=\max\left\{0,1-\frac{\log(d+1)}{\log(h+1)}\right\}
  \quad(d=0,1,2,\ldots),\qquad \phi_h(\infty)=0.
\]
Set $Y=X\times\mathcal T$.  For $y=(v,T)\in Y$, define the column function
\begin{equation}
  g_y(x)=\phi_h(d_T(x,v))\qquad(x\in X).
  \label{eq:column-functions}
\end{equation}
Thus $0\le g_y\le1$.  For nonnegative coefficients of total mass at most
one, write
\[
  f_\mu=\sum_{y\in Y}\mu_y g_y,
  \qquad
  \mathcal F_+=\left\{f_\mu:\mu_y\ge0,\ \sum_{y\in Y}\mu_y\le1\right\}.
\]
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$.

\begin{lemma}[Logarithmic profile]
\label{lem:log-profile}
For any positive integer $h$, the weights
\[
  \gamma_j=\frac{\log(j+2)-\log(j+1)}{\log(h+1)}
  \quad(0\le j<h)
\]
are positive, sum to one, and satisfy, for every
$d\in\{0,1,2,\ldots\}\cup\{\infty\}$,
\begin{align}
  \phi_h(d)
    &=\sum_{j=0}^{h-1}\gamma_j\mathbf1_{\{d\le j\}},
    \label{eq:profile-expansion}\\
  \sum_{j=0}^{h-1}\gamma_j\mathbf1_{\{d\le3j+2\}}
    &\le\phi_h(d)+\frac{\log3}{\log(h+1)}.
    \label{eq:profile-dilation}
\end{align}
\end{lemma}

\begin{proof}
Positivity and the identity $\sum_j\gamma_j=1$ follow by telescoping.
If $0\le d<h$, the sum in \eqref{eq:profile-expansion} runs from $j=d$
to $j=h-1$ and equals
\[
  \frac{\log(h+1)-\log(d+1)}{\log(h+1)}.
\]
If $d\ge h$, including $d=\infty$, both sides are zero.

For finite $d$, the extra indices counted on the left of
\eqref{eq:profile-dilation} satisfy $j<d\le3j+2$.  When this index set is
nonempty, it is the integer interval from
\[
  a_d=\max\left\{0,\left\lceil\frac{d+1}{3}\right\rceil-1\right\}
  \quad\text{to}\quad
  b_d=\min\{h-1,d-1\}.
\]
Since $b_d+2\le d+1$ and $a_d+1\ge(d+1)/3$, its weight is
\[
  \sum_{j=a_d}^{b_d}\gamma_j
  =\frac{\log((b_d+2)/(a_d+1))}{\log(h+1)}
  \le\frac{\log3}{\log(h+1)}.
\]
An empty interval contributes zero.  If $d=\infty$, all the indicators
vanish.  This also covers all distances at and beyond the cutoff $h$.
\end{proof}

\begin{proposition}[Uniform compression]
\label{prop: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
\begin{equation}
  f(x)-3\theta\le A(x)\le f(x)+\theta\qquad(x\in X).
  \label{eq:positive-approximation}
\end{equation}
In particular, $\|f-A\|_{\infty,X}\le3\theta$.  The list can be chosen with
\begin{equation}
  \log Q\le hs\log q+C_{h,\theta,u},
  \qquad
  C_{h,\theta,u}
   =\log u+hs2^u\log\left(1+\frac{s2^u}{\theta}\right).
  \label{eq:compression-count}
\end{equation}
\end{proposition}

\begin{proof}
For each $i\in[u]$, fix a representative map
\[
  \rho_i:L_i(X)\longrightarrow X,
  \qquad L_i(\rho_i(\sigma))=\sigma.
\]
These maps are fixed for the entire approximation problem, before any
coefficient vector is chosen.

\emph{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
\eqref{eq:admissible-sets} gives
\[
  \frac1u\sum_{i=1}^u\mu\{(v,T):i\notin T\}
   =\sum_{(v,T)\in Y}\mu_{(v,T)}\frac{|[u]\setminus T|}{u}
   \le\theta.
\]
Choose $i_0\in[u]$ for which the omitted mass is at most $\theta$, and
retain the columns in
\[
  Y_0=\{(v,T)\in Y:i_0\in T\}.
\]
This one index will serve at every level $j$.

\emph{A bounded number of pivots at each level.}
Fix $j\in\{0,\ldots,h-1\}$ and, for $x\in X$, let
\[
  I_x=\{(v,T)\in Y_0:d_T(x,v)\le j\}.
\]
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
\[
  U_j=\bigcup_{k=1}^{k_j}I_{z_{j,k}}
  \quad\text{such that}\quad
  \mu(I_x\setminus U_j)\le\theta\qquad(x\in X).
\]
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,
\begin{equation}
  d_T(v,z')\le j+1.
  \label{eq:pivot-replacement}
\end{equation}
For every $x\in X$, the triangle inequality now gives the two implications
\begin{align}
  d_T(x,v)\le j
   &\ \Longrightarrow\ d_T(x,z')\le2j+1,
   \label{eq:pivot-forward}\\
  d_T(x,z')\le2j+1
   &\ \Longrightarrow\ d_T(x,v)\le3j+2.
   \label{eq:pivot-backward}
\end{align}
All distances used in these triangle inequalities are finite under their
respective hypotheses, even if the graph is disconnected.
Figure~\ref{fig:pivot-comparison} illustrates the two bounds.

\input{figures/pivot-comparison}

Write $z'_{j,k}=\rho_{i_0}(L_{i_0}(z_{j,k}))$ and define
\[
  A_j(x)=\sum_{y=(v,T)\in U_j}\mu_y
       \mathbf1_{\{d_T(x,z'_{j,\kappa_j(y)})\le2j+1\}}.
\]
For comparison, let
\[
  f_{\mu,j}(x)=\sum_{y=(v,T)\in Y}\mu_y
                       \mathbf1_{\{d_T(x,v)\le j\}}.
\]
Every assigned column counted by $f_{\mu,j}(x)$ is counted by $A_j(x)$,
by \eqref{eq:pivot-forward}.  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, \eqref{eq:pivot-backward} bounds every column counted by
$A_j(x)$.  Hence
\begin{equation}
  f_{\mu,j}(x)-2\theta
  \le A_j(x)
  \le\sum_{y=(v,T)\in Y}\mu_y\mathbf1_{\{d_T(x,v)\le3j+2\}}.
  \label{eq:level-comparison}
\end{equation}

\emph{Combining the levels.}
Let $F=\sum_{j=0}^{h-1}\gamma_jA_j$.  By
\eqref{eq:profile-expansion}, $f_\mu=\sum_j\gamma_jf_{\mu,j}$.
Thus the lower bound in \eqref{eq:level-comparison} gives
$F\ge f_\mu-2\theta$.  For the upper bound, apply
\eqref{eq:profile-dilation} 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
\begin{equation}
  f_\mu-2\theta\le F\le f_\mu+\theta.
  \label{eq:unrounded-approximation}
\end{equation}

\emph{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
\begin{equation}
  A_j(x)=\sum_{k=1}^{s}\sum_{T\in\mathcal T}
       w_{j,k,T}\mathbf1_{\{d_T(x,z'_{j,k})\le2j+1\}},
  \label{eq:grouped-approximation}
\end{equation}
where
\[
  w_{j,k,T}=
  \sum_{\substack{v\in X:\ (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_{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
\[
  \widetilde w_{j,k,T}
   =\delta\left\lfloor\frac{w_{j,k,T}}{\delta}\right\rfloor.
\]
Let $\widetilde A_j$ be \eqref{eq:grouped-approximation} with these
rounded weights, and put $A=\sum_j\gamma_j\widetilde A_j$.  Since every
indicator is at most one,
\[
  0\le A_j(x)-\widetilde A_j(x)\le M_0\delta=\theta.
\]
The weights $\gamma_j$ sum to one, so $0\le F-A\le\theta$.
Together with \eqref{eq:unrounded-approximation}, this proves
\eqref{eq:positive-approximation}.

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 \eqref{eq:grouped-approximation}.
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
\[
  \left\lfloor\frac{M_0}{\theta}\right\rfloor+1
  \le1+\frac{M_0}{\theta}
\]
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
\[
  Q\le u\,q^{hs}
        \left(1+\frac{s2^u}{\theta}\right)^{hs2^u}.
\]
Taking logarithms proves \eqref{eq:compression-count}.  The graphs and
the representative maps are shared data defining this list; they are
not additional choices for each approximant.
\end{proof}

The family $\mathcal T$ and all the graphs are fixed before applying
Proposition~\ref{prop:compression}.  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.

\begin{corollary}[Signed compression]
\label{cor:signed-compression}
With the notation of Proposition~\ref{prop:compression}, put
\[
  f_\lambda=\sum_{y\in Y}\lambda_y g_y,
  \qquad
  B_1^Y=\left\{\lambda\in\R^Y:\sum_{y\in Y}|\lambda_y|\le1\right\},
\]
and
\[
  \mathcal F=\{f_\lambda:\lambda\in B_1^Y\}
            =\absconv\{g_y:y\in Y\}.
\]
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
\begin{equation}
  \|f_\lambda-f_{\lambda'}\|_{\infty,X}\le12\theta
  \label{eq:signed-cluster-diameter}
\end{equation}
whenever $\lambda,\lambda'$ belong to the same cluster.
\end{corollary}

\begin{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~\ref{prop:compression} to
choose $A^+,A^-\in\mathcal A$ with
\[
  \|f_{\lambda^+}-A^+\|_{\infty,X}\le3\theta,
  \qquad
  \|f_{\lambda^-}-A^-\|_{\infty,X}\le3\theta.
\]
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
\eqref{eq:signed-cluster-diameter}.  The approximating functions need
not belong to $\mathcal F$; the clusters themselves consist of actual
coefficient vectors in $B_1^Y$.
\end{proof}
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//03-compression.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//04-partitions.tex ====
\section{Finite-field partitions and separated rows}
\label{sec:partitions}

We now construct partitions with few labels for which the functions of
Section~\ref{sec:compression} 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
\cite[Corollary~1]{Schwartz1980}; related early work on randomized
polynomial evaluation is due to Zippel~\cite{Zippel1979}. We include
the precise finite-field statement and its elementary proof.

\begin{lemma}[Polynomial zero bound]
\label{lem:polynomial-zero}
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
\[
  \Pr\bigl(P(U_1,\ldots,U_k)=0\bigr)\le \frac{d}{p}.
\]
\end{lemma}

\begin{proof}
We induct on $k$.  When $k=0$, the polynomial is a nonzero constant,
and its zero probability is zero.  For $k\ge1$, write
\[
  P(z_1,\ldots,z_k)
  =\sum_{j=0}^{e}P_j(z_1,\ldots,z_{k-1})z_k^j,
  \qquad P_e\ne0.
\]
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.
\end{proof}

For positive integers $r,h$, set
\[
  D_j=\binom{r+j-1}{j}\quad(j\ge0).
\]
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
\begin{equation}
  \dim_{\F_p}\operatorname{Sym}^j(E^*)=D_j,
  \qquad
  \bigl|\operatorname{Sym}^j(E^*)\bigr|=p^{D_j}.
  \label{eq:symmetric-form-dimension}
\end{equation}

\begin{proposition}[Directions with nonvanishing evaluations]
\label{prop:robust-directions}
Let $0<\theta<1$ and let $r,h$ be positive integers.  Put
\begin{equation}
  w=2D_h,\qquad
  u=\left\lceil\frac{hw}{\theta}\right\rceil,
  \label{eq:field-parameters}
\end{equation}
and let $p$ be any prime satisfying
\begin{equation}
  p>\max\{h,h^2u^{2h}\}.
  \label{eq:field-prime-threshold}
\end{equation}
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
\begin{equation}
  Z(t_{i_1},\ldots,t_{i_h})\ne0
  \qquad\text{for all }(i_1,\ldots,i_h)\in T^h.
  \label{eq:robust-nonvanishing}
\end{equation}
Tuples in this assertion may have repeated indices.
\end{proposition}

\begin{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
\begin{equation}
  \begin{aligned}
  P_Z(z_1,\ldots,z_r)&=Z(z,\ldots,z)\\
  &=\sum_{\substack{\alpha_1+\cdots+\alpha_r=h\\\alpha_a\ge0}}
    \frac{h!}{\alpha_1!\cdots\alpha_r!}
    Z(e_1^{[\alpha_1]},\ldots,e_r^{[\alpha_r]})
    z_1^{\alpha_1}\cdots z_r^{\alpha_r},
  \end{aligned}
  \label{eq:diagonal-polynomial}
\end{equation}
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 \cite[Corollary~1.2]{FerreroMicali1979} and
\cite[Proposition~3.3]{DrapalVojtechovsky2009}. 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 \eqref{eq:diagonal-polynomial}.
Lemma~\ref{lem:polynomial-zero} therefore gives
\begin{equation}
  \Pr\bigl(Z(t_{i_1},\ldots,t_{i_h})=0\bigr)\le\frac hp.
  \label{eq:tuple-zero-probability}
\end{equation}
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
\begin{equation}
  p^{D_h}u^{hw}\left(\frac hp\right)^w
  =\left(\frac{h^2u^{2h}}p\right)^{D_h}<1.
  \label{eq:field-union-bound}
\end{equation}
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
\[
  h(w-1)<hw\le\theta u.
\]
If any zero tuple were supported in $T$, its support would be disjoint
from all the selected supports, contradicting maximality.  Thus
\eqref{eq:robust-nonvanishing} holds.  Since $\theta<1$, the set $T$ is
nonempty.  The construction imposed no requirement that the sampled
vectors be distinct or nonzero.
\end{proof}

\begin{proposition}[Partitions with separated rows]
\label{prop:separated-rows}
With the parameters and directions of
Proposition~\ref{prop:robust-directions}, let
\[
  X=\operatorname{Sym}^h(E^*),\qquad
  L_i(x)=x(t_i,\cdot,\ldots,\cdot),
\]
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~\ref{sec:compression}, every pair of distinct $x,y\in X$ has
some $T\in\mathcal T$ satisfying
\begin{equation}
  d_T(x,y)>h.
  \label{eq:graph-separation}
\end{equation}
Consequently, for $Y=X\times\mathcal T$ and
$R_x=(g_{(v,T)}(x))_{(v,T)\in Y}\in\R^Y$, the rows satisfy
\begin{equation}
  \|R_x-R_y\|_\infty=1\qquad(x\ne y).
  \label{eq:row-separation}
\end{equation}
\end{proposition}

\begin{proof}
The cardinality of $X$ follows from
\eqref{eq:symmetric-form-dimension}.  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~\ref{prop:robust-directions} 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
\[
  x=x_0,x_1,\ldots,x_k=y,\qquad 1\le k\le 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,\ldots,v_h)=0
  \qquad\text{for every }v_2,\ldots,v_h\in E.
\]
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 \eqref{eq:robust-nonvanishing}.  This proves
\eqref{eq:graph-separation}; 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 \eqref{eq:row-separation}.
\end{proof}

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~\ref{prop:compression},
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
\begin{equation}
  \log Q\le hsD_{h-1}\log p+C_{h,\theta,u}.
  \label{eq:field-compression-bound}
\end{equation}
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 \eqref{eq:field-prime-threshold}.
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//04-partitions.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//05-counterexample.tex ====
\section{Choice of parameters and failure of duality}
\label{sec:parameters}

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~\ref{prop:compression}.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Fix $a,b\ge1$.  Put
\[
 \theta=\frac1{1000a},
 \qquad s=\lceil1/\theta\rceil,
\]
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
\begin{equation}
\label{eq:rank-choice}
 r+h-1>8bh^2s.
\end{equation}
As in Section~\ref{sec:partitions}, define
\[
 D_j=\binom{r+j-1}{j}\quad(0\le j\le h),
 \qquad w=2D_h,
 \qquad u=\left\lceil\frac{hw}{\theta}\right\rceil.
\]
The number
\begin{equation}
\label{eq:fixed-encoding-term}
 C=C_{h,\theta,u}
   =\log u+hs2^u\log\left(1+\frac{s2^u}{\theta}\right)
\end{equation}
is now fixed.  Choose a prime $p$ satisfying
\begin{equation}
\label{eq:prime-choice}
 p>\max\left\{
       h,\ h^2u^{2h},\ \exp\left(\frac{8bC}{D_h}\right)
      \right\}.
\end{equation}
All quantities on the right have already been determined, and primes
exceed every finite bound.

Apply Proposition~\ref{prop:robust-directions} with these parameters,
and form the label maps and graph profiles in
Proposition~\ref{prop:separated-rows}.  The row index set $X$ consists
of the symmetric $h$-linear forms on $\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\mathcal T$, where
\[
 \mathcal T=\{T\subseteq[u]:|[u]\setminus T|\le\theta u\},
\]
and the real row vectors satisfy
\begin{equation}
\label{eq:final-row-separation}
 \|R_x-R_{x'}\|_\infty=1\qquad(x\ne x').
\end{equation}
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~\ref{prop:compression}, the positive column class has
a uniform $3\theta$ approximation list of cardinality $Q$ satisfying
\[
 \log Q\le hs\log q+C
         =hsD_{h-1}\log p+C.
\]
Corollary~\ref{cor:signed-compression} gives a uniform $6\theta$
approximation list of at most $Q^2$ functions for the absolutely
convex column hull.  Thus Lemma~\ref{lem:matrix-to-bodies} applies
with $\varepsilon=6\theta$ and $t=\theta$.  It gives admissible
bodies in dimension $n=|Y|$,
\begin{equation}
\label{eq:final-bodies}
 K=3\absconv\{R_x:x\in X\}+\theta B_\infty^Y,
 \qquad L=B_\infty^Y,
\end{equation}
such that
\[
 N(K,L)\ge m,
 \qquad N(L^\circ,38\theta K^\circ)\le Q^2.
\]
Since $38\theta=38/(1000a)<a^{-1}$, increasing the covering body
preserves this cover, and therefore
\begin{equation}
\label{eq:final-dual-bound}
 N(L^\circ,a^{-1}K^\circ)\le Q^2.
\end{equation}

It remains to compare the two entropies.  The exact identity
\[
 \frac{D_{h-1}}{D_h}=\frac{h}{r+h-1}
\]
yields
\begin{equation}
\label{eq:entropy-ratio}
 \frac{\log(Q^2)}{\log m}
 \le \frac{2h^2s}{r+h-1}
      +\frac{2C}{D_h\log p}
 <\frac1{4b}+\frac1{4b}
 =\frac1{2b},
\end{equation}
where the strict inequalities follow respectively from
\eqref{eq:rank-choice} and \eqref{eq:prime-choice}.
Combining \eqref{eq:final-dual-bound} with $N(K,L)\ge m>1$ gives
\[
 b\log N(L^\circ,a^{-1}K^\circ)
 \le b\log(Q^2)
 <\frac12\log m
 <\log N(K,L).
\]
Identifying $\R^Y$ with $\R^n$ makes $L=[-1,1]^n$ and proves the
claimed counterexample for the arbitrary proposed constants $a,b$.
\end{proof}

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
\[
 p>\max\left\{h,\ h^2u^{2h},\ \exp\left(\frac{rC}{D_h}\right)
        \right\}.
\]
The resulting bodies $K_r,L_r$ satisfy
\[
 0\le
 \frac{\log N(L_r^\circ,a^{-1}K_r^\circ)}
      {\log N(K_r,L_r)}
 \le \frac{2h^2s}{r+h-1}+\frac2r
 \longrightarrow0.
\]
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.

\subsection{A consequence for convexified packing}

Theorem~\ref{thm:main} 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
\[
 (x_j+\operatorname{int}B)\cap\conv\{x_i:i<j\}=\varnothing
 \qquad(1\le j\le m),
\]
with the first convex hull taken to be empty
\cite[Section~2]{AMSTJ2004}.

\begin{corollary}[Separation from convexified packing]
\label{cor:convexified-separation}
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$,
\[
 \log N(K,L)>C\log\widehat M(K,L/A).
\]
\end{corollary}

\begin{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 \cite[Theorem~2]{AMSTJ2004}, applied to $K,L/A$, gives
\[
\begin{split}
 \widehat M(K,L/A)
 &\le\widehat M(A L^\circ,K^\circ/2)^2\\
 &=\widehat M(L^\circ,K^\circ/(2A))^2\\
 &\le N(L^\circ,K^\circ/(8A))^2.
\end{split}
\]
Here the equality uses simultaneous dilation of both arguments.
Choose $K,L$ by Theorem~\ref{thm:main} with $a=8A$ and $b=2C$.
Taking logarithms in the displayed bound proves the corollary.
\end{proof}
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//05-counterexample.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//paper.tex ====
\documentclass[11pt]{article}
\usepackage{cmap}
\input{preamble}
\title{Counterexamples to the duality conjecture\\for metric entropy}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We disprove Pietsch's dimension-free duality conjecture for metric entropy.
For every proposed pair of universal constants, we construct
origin-symmetric convex bodies that violate the corresponding covering-entropy
inequality, already when the covering body is a cube.
\end{abstract}
\input{sections/01-introduction}
\input{sections/02-matrix-contract}
\input{sections/03-compression}
\input{sections/04-partitions}
\input{sections/05-counterexample}
\bibliographystyle{alpha}
\begingroup
\raggedright
\bibliography{references}
\endgroup
\end{document}
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//paper.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//pivot-comparison.tex ====
\begin{figure}[hbp]
\centering
\begin{minipage}[t]{.48\linewidth}
\centering
{\small\textup{(a)} Keeping an assigned match\par}
\medskip
\begin{tikzpicture}[font=\small,
 point/.style={circle,fill=black,inner sep=1.6pt},
 path/.style={draw=black!75,line width=.6pt},
 bound/.style={draw=linkblue,dashed,line width=.7pt}]
\node[point,label=above:$x$] (x) at (0,0) {};
\node[point,label=above:$v$] (v) at (1.5,0) {};
\node[point,label=above:$z$] (z) at (3,0) {};
\node[point,label=above:$z'$] (zp) at (4.5,0) {};
\draw[path] (x) -- node[below] {$\le j$} (v);
\draw[path] (v) -- node[below] {$\le j$} (z);
\draw[path] (z) -- node[below] {$\le1$} (zp);
\draw[bound] (x) to[bend right=40]
 node[below=3pt,text=linkblue] {$d_T(x,z')\le2j+1$} (zp);
\path (0,-1.55) -- (4.5,-1.55);
\end{tikzpicture}
\end{minipage}\hfill
\begin{minipage}[t]{.48\linewidth}
\centering
{\small\textup{(b)} Controlling the extra matches\par}
\medskip
\begin{tikzpicture}[font=\small,
 point/.style={circle,fill=black,inner sep=1.6pt},
 path/.style={draw=black!75,line width=.6pt},
 bound/.style={draw=linkblue,dashed,line width=.7pt}]
\node[point,label=above:$x$] (x) at (0,0) {};
\node[point,label=above:$z'$] (zp) at (3.8,0) {};
\node[point,label=below:$v$] (v) at (3.8,-1.2) {};
\draw[path] (x) -- node[above] {$\le2j+1$} (zp);
\draw[path] (zp) -- node[right] {$\le j+1$} (v);
\draw[bound] (x) -- node[below left,text=linkblue] {$\le3j+2$} (v);
\path (0,-1.55) -- (4.5,-1.55);
\end{tikzpicture}
\end{minipage}
\caption{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$.}
\label{fig:pivot-comparison}
\end{figure}
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//pivot-comparison.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//preamble.tex ====
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,calc}
\definecolor{linkblue}{RGB}{24,62,110}
\usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue,bookmarksnumbered=true]{hyperref}
\hypersetup{pdftitle={Counterexamples to the duality conjecture for metric entropy},pdfauthor={OpenAI}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\F}{\mathbb F}
\DeclareMathOperator{\absconv}{absconv}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\rank}{rank}
\setlist[enumerate]{label=\textup{(\roman*)},leftmargin=*,itemsep=.25em}
\setlist[itemize]{leftmargin=*,itemsep=.25em}
\setlength{\emergencystretch}{1.5em}
\numberwithin{equation}{section}
\ifdefined\pdfinfoomitdate\pdfinfoomitdate=1\fi
\ifdefined\pdftrailerid\pdftrailerid{}\fi
\ifdefined\pdfsuppressptexinfo\pdfsuppressptexinfo=15\fi
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//preamble.tex ====

==== BEGIN Counterexamples-to-the-duality-conjecture-for-metric-entropy//references.bib ====

@article{AMS2004,
  author       = {Artstein, S. and Milman, V. and Szarek, S. J.},
  title        = {Duality of metric entropy},
  journal      = {Annals of Mathematics},
  volume       = {159},
  number       = {3},
  pages        = {1313--1328},
  year         = {2004},
  doi          = {10.4007/annals.2004.159.1313},
  url          = {https://annals.math.princeton.edu/2004/159-3/p07},
  eprint       = {math/0407236},
  archivePrefix = {arXiv}
}

@article{AMSTJ2004,
  author       = {Artstein, S. and Milman, V. and Szarek, S. and Tomczak-Jaegermann, N.},
  title        = {On convexified packing and entropy duality},
  journal      = {Geometric and Functional Analysis},
  volume       = {14},
  number       = {5},
  pages        = {1134--1141},
  year         = {2004},
  doi          = {10.1007/s00039-004-0486-3},
  url          = {https://link.springer.com/article/10.1007/s00039-004-0486-3},
  eprint       = {math/0407238v1},
  archivePrefix = {arXiv},
  note         = {Numbered locators refer to \href{https://arxiv.org/abs/math/0407238v1}{arXiv:math/0407238v1}}
}

@article{Milman2007,
  author       = {Milman, Emanuel},
  title        = {A remark on two duality relations},
  journal      = {Integral Equations and Operator Theory},
  volume       = {57},
  number       = {2},
  pages        = {217--228},
  year         = {2007},
  doi          = {10.1007/s00020-006-1479-4},
  url          = {https://link.springer.com/article/10.1007/s00020-006-1479-4},
  eprint       = {math/0603461},
  archivePrefix = {arXiv}
}

@book{Pietsch1972,
  author       = {Pietsch, Albrecht},
  title        = {Theorie der Operatorenideale ({Zusammenfassung})},
  series       = {Wissenschaftliche Beitr{\"a}ge der Friedrich-Schiller-Universit{\"a}t Jena},
  publisher    = {Friedrich-Schiller-Universit{\"a}t},
  address      = {Jena},
  year         = {1972},
  language     = {German}
}

@article{Schwartz1980,
  author       = {Schwartz, J. T.},
  title        = {Fast probabilistic algorithms for verification of polynomial identities},
  journal      = {Journal of the ACM},
  volume       = {27},
  number       = {4},
  pages        = {701--717},
  year         = {1980},
  doi          = {10.1145/322217.322225},
  url          = {https://doi.org/10.1145/322217.322225}
}

@incollection{Zippel1979,
  author       = {Zippel, Richard},
  title        = {Probabilistic algorithms for sparse polynomials},
  editor       = {Ng, Edward W.},
  booktitle    = {Symbolic and Algebraic Computation},
  series       = {Lecture Notes in Computer Science},
  volume       = {72},
  pages        = {216--226},
  publisher    = {Springer},
  address      = {Berlin, Heidelberg},
  year         = {1979},
  doi          = {10.1007/3-540-09519-5_73},
  url          = {https://link.springer.com/chapter/10.1007/3-540-09519-5_73}
}

@inproceedings{HuPealeReingold2022,
  author       = {Hu, Lunjia and Peale, Charlotte and Reingold, Omer},
  title        = {Metric entropy duality and the sample complexity of outcome indistinguishability},
  editor       = {Dasgupta, Sanjoy and Haghtalab, Nika},
  booktitle    = {Proceedings of the 33rd International Conference on Algorithmic Learning Theory},
  series       = {Proceedings of Machine Learning Research},
  volume       = {167},
  pages        = {515--552},
  publisher    = {PMLR},
  year         = {2022},
  url          = {https://proceedings.mlr.press/v167/hu22a.html}
}

@incollection{KonigMilman1987,
  author = {K{\"o}nig, H. and Milman, V. D.},
  title = {On the covering numbers of convex bodies},
  booktitle = {Geometrical Aspects of Functional Analysis},
  series = {Lecture Notes in Mathematics},
  volume = {1267},
  pages = {82--95},
  publisher = {Springer},
  year = {1987},
  doi = {10.1007/BFb0078138},
  url = {https://doi.org/10.1007/BFb0078138}
}

@incollection{BPSTJ1989,
  author = {Bourgain, J. and Pajor, A. and Szarek, S. J. and Tomczak-Jaegermann, N.},
  title = {On the duality problem for entropy numbers of operators},
  booktitle = {Geometric Aspects of Functional Analysis (1987--1988)},
  series = {Lecture Notes in Mathematics},
  volume = {1376},
  pages = {50--63},
  publisher = {Springer},
  year = {1989},
  doi = {10.1007/BFb0090048},
  url = {https://doi.org/10.1007/BFb0090048}
}

@article{Mendelson2001,
  author = {Mendelson, Shahar},
  title = {On the size of convex hulls of small sets},
  journal = {Journal of Machine Learning Research},
  volume = {2},
  pages = {1--18},
  year = {2001},
  url = {https://www.jmlr.org/papers/v2/mendelson01a.html}
}

@article{FerreroMicali1979,
  author = {Ferrero, Miguel and Micali, Artibano},
  title = {Sur les $n$-applications},
  journal = {M{\'e}moires de la Soci{\'e}t{\'e} Math{\'e}matique de France},
  volume = {59},
  pages = {33--53},
  year = {1979},
  doi = {10.24033/msmf.247},
  url = {https://www.numdam.org/articles/10.24033/msmf.247/}
}

@article{DrapalVojtechovsky2009,
  author = {Dr{\'a}pal, Ale{\v s} and Vojt{\v e}chovsk{\'y}, Petr},
  title = {Symmetric multilinear forms and polarization of polynomials},
  journal = {Linear Algebra and its Applications},
  volume = {431},
  number = {5--7},
  pages = {998--1012},
  year = {2009},
  eprint = {1509.05707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1509.05707}
}
==== END Counterexamples-to-the-duality-conjecture-for-metric-entropy//references.bib ====