A counterexample to metric-entropy duality

Source and verification

This article explains family 329 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

Polarity exchanges a convex body with a body of linear tests. Metric-entropy duality asks whether this exchange preserves covering complexity up to universal constants and a fixed change of scale. Family 329 claims a counterexample for every proposed pair of constants, already when one body is a cube. The argument converts a matrix with many separated rows and compressible columns into the required convex bodies. (OpenAI, 2026)

🏷️ Preliminaries: covering numbers and polar bodies

For bounded $A$ and a body $B$ with nonempty interior, $N(A,B)$ is the least number of translates of $B$ covering $A$. Centers may be anywhere in the ambient space. Its logarithm is called covering entropy.

An origin-symmetric convex body $K\subset {\mathbb{R}}^n$ is compact, convex, has nonempty interior, and satisfies $K=-K$. Its polar is

$$\begin{array}{c}{K}^{\circ }\\ =\{y:⟨x,y⟩\le 1\text{for every }x\in K\}.\end{array}$$

For the cube $B_{\infty }=[-1,1{]}^n$, maximization coordinate by coordinate gives

$$\underset{x\in B_{\infty }}{\sup }⟨x,y⟩=\Vert y{\Vert }_1,B_{\infty }^{\circ }=B_1.$$

The universal duality conjecture asks for absolute $a,b\ge 1$ such that

$$\begin{array}{c}{b}^{-1}\log N(L^{\circ },a{K}^{\circ })\le \log N(K,L),\\ \log N(K,L)\le b\log N(L^{\circ },a^{-1}{K}^{\circ })\end{array}$$

in every dimension for every symmetric pair.

Manuscript claim

For every $a,b\ge 1$, there is a positive dimension and a full-dimensional symmetric convex body $K$ such that, with $L=B_{\infty }$,

$$\begin{array}{c}\log N(K,L)\\ >b\log N(L^{\circ },a^{-1}{K}^{\circ }).\end{array}$$

Thus no proposed universal pair works. The dimension and body depend on the proposed constants. (OpenAI, 2026)

This does not contradict dimension-free comparisons for ellipsoids or for classes with a uniformly controlled $K$-convexity constant. Nor is ordinary covering entropy the same quantity as convexified packing, which imposes an ordered convex-hull avoidance condition.

🏷️ An elementary matrix-to-body lemma

Let $R_x=(g_y(x){)}_{y\in Y}$ be the rows of a finite real matrix, indexed by $x\in X$. Assume distinct rows are separated by at least one in the supremum norm.

Consider the absolutely convex hull of its columns as functions on $X$:

$$\mathcal{F}=\left\{f_{\lambda }=\sum _{y\in Y}{\lambda }_y{g}_y:\Vert \lambda {\Vert }_1\le 1\right\}.$$

Suppose $\mathcal{F}$ has a uniform $\epsilon$-approximation list of size $M$. The list’s functions need not themselves belong to $\mathcal{F}$.

For $t>0$, set

$$\begin{array}{c}K=3\mathrm{conv}\{\pm R_x:x\in X\}+t{B}_{\infty }^Y,\\ L=B_{\infty }^Y.\end{array}$$

The small cube makes $K$ full-dimensional. Its points $3R_x$ are at mutual sup distance at least three, while every translated unit cube has diameter two. Therefore $N(K,L)\ge |X|$.

For the polar side, the support function is

$$h_K(\delta )=3\Vert f_{\delta }{\Vert }_{\infty ,X}+t\Vert \delta {\Vert }_1.$$

Group coefficient vectors in $B_1^Y$ by their assigned approximating function and choose one actual representative ${\lambda }^{(k)}$ from each nonempty group. Within a group,

$$\begin{array}{c}\Vert f_{\lambda }-f_{{\lambda }^{(k)}}{\Vert }_{\infty }\le 2\epsilon ,\\ \Vert \lambda -{\lambda }^{(k)}{\Vert }_1\le 2.\end{array}$$

Hence $h_K(\lambda -{\lambda }^{(k)})\le 6\epsilon +2t$. Since $\delta \in c{K}^{\circ }$ exactly when $h_K(\delta )\le c$,

$$N(L^{\circ },(6\epsilon +2t)K^{\circ })\le M.$$

This proves the geometric conversion. Actual coefficient representatives are important: they control the added cube term even if the original approximation centers were arbitrary functions.

🏷️ Compressing columns through partition labels

The difficult task is now a finite construction with

$$\begin{array}{c}\log |X|>b\log M,\\ 6\epsilon +2t\le a^{-1}.\end{array}$$

The source equips a finite set with many partitions. A selected family of partitions defines a graph: points are joined when they belong to a common class in one selected partition. Let $d_T(x,v)$ be its graph distance, possibly infinite.

Columns are truncated logarithmic distance profiles

$$\begin{array}{c}{g}_{T,v}(x)\\ ={\left(1-\frac{\log (1+d_T(x,v))}{\log (1+h)}\right)}_{+},\end{array}$$

with value zero for infinite distance. Every chosen partition family omits only a small fraction of all partitions.

For a convex combination of columns, averaging finds a partition present in nearly all its coefficient mass. At each radius, a bounded list of pivots captures most of the mass. Replacing a pivot by a representative of its partition class stores a short label rather than a potentially expensive center.

The replacement enlarges radii from $j$ to at most $3j+2$. The resulting profile error is bounded by

$$\frac{\log 3}{\log (1+h)},$$

because $1+(3j+2)=3(1+j)$. This simple logarithmic identity is why the profiles tolerate the geometric replacement. Signed combinations are handled by separating positive and negative coefficient mass.

🏷️ Row separation and the order of parameters

A finite combinatorial construction supplies many rows relative to the number of partition labels. The manuscript realizes it using symmetric multilinear forms over a finite field. The relevant output for this post is the count: there are $p^{D_h}$ rows and at most $p^{D_{h-1}}$ labels per partition, where

$$\begin{array}{c}{D}_j=\left(\genfrac{}{}{0ex}{}{r+j-1}{j}\right),\\ \frac{D_{h-1}}{D_h}=\frac{h}{r+h-1}.\end{array}$$

A nonvanishing selection ensures that distinct rows are separated by one; otherwise a short graph path would contradict the selected evaluations.

First choose the cutoff and approximation accuracy for the proposed scale $a$. Then increase $r$ to make the displayed ratio small enough for $b$. Finally choose the prime $p$ large enough that the remaining encoding costs are negligible. This ordered choice defeats fixed universal constants while allowing the dimension to grow.

The partition compression and separation construction are the manuscript’s research inputs. The matrix-to-body deduction above explains exactly what they must deliver without developing the underlying finite-field machinery.

🏷️ Key steps and proof outlines

A finite matrix separates the two covering problems

Let $r_x$ be rows of a finite matrix and write $g_y(x)$ for its columns. The construction makes distinct rows at least one apart in the sup norm. Consequently their dilates form a packing in a body such as $K=3\mathrm{absconv}\{r_x\}+t{B}_{\infty }$. A cover by sufficiently small translates of the cube must use at least the number of packed rows.

The polar covering problem is controlled by a different statistic. For a vector of coefficients $\delta$, define $f_{\delta }(x)={\sum }_y{\delta }_y{g}_y(x)$. The support function is

$$h_K(\delta )=3\Vert f_{\delta }{\Vert }_{\infty }+t\Vert \delta {\Vert }_1.$$

Thus a finite list approximating all such coefficient combinations in the appropriate sup norm yields a small polar cover. The small added cube makes $K$ full dimensional; its contribution $t\Vert \delta {\Vert }_1$ must be kept in the covering-radius calculation. The manuscript’s matrix contract gives radius $6\epsilon +2t$ from list error $\epsilon$. (OpenAI, 2026)

Logarithmic profiles tolerate a multiplicative change of radius

The columns come from graph-distance profiles of the form

$$g_y(x)={\left(1-\frac{\log (1+d(x,y))}{\log (1+h)}\right)}_{+}.$$

These profiles distinguish certain rows sharply, but they are compressible after averaging. Their useful feature is an exact expansion as a positive combination of ball indicators. The coefficients are successive logarithmic differences, so they telescope to the profile value. Replacing radius $j$ by a controlled larger radius such as $3j+2$ changes the profile by at most $\log 3/\log (1+h)$. A large parameter $h$ therefore makes coarse radius descriptions accurate.

For a positive coefficient combination, choose a finite partition that contains almost all of the relevant coefficient mass. At each radius, retain a bounded collection of pivots and record their partition labels. Centers assigned to the same record have comparable ball membership after enlarging radii. The logarithmic estimate turns this geometric comparison into uniform approximation of the entire weighted profile. Signed combinations are handled by separating positive and negative coefficients before compression; cancellation is not assumed to preserve a positive argument.

Partition counting supplies many rows but few descriptions

The source builds partitions with two competing properties: they separate the needed pairs of rows, while most weighted centers are compatible with one partition. A finite-field construction supplies the combinatorial counts. For this proof’s analytic use, the relevant input is simply a finite separation certificate together with the number of labels; the covering argument does not require learning the algebraic construction itself.

Its elementary counting ingredient bounds the probability that a nonzero polynomial vanishes on a uniformly sampled point by its degree divided by the field size. One proves this inductively by separating the leading coefficient in one variable: outside the exceptional set where that coefficient vanishes, a nonzero one-variable polynomial has at most its degree many roots. The construction uses this estimate to show that forbidden coincidences occupy only a small fraction of the available partitions.

If $D_j=\left(\genfrac{}{}{0ex}{}{r+j-1}{j}\right)$, the row count and record count involve successive values of $D_j$. The ratio

$$\frac{D_{h-1}}{D_h}=\frac{h}{r+h-1}$$

can be made small by increasing $r$. This is the counting advantage that ultimately separates the two entropies.

The parameters must be chosen in the right order

First choose the desired approximation tolerance from the proposed duality constants. Then choose $h$ so that the logarithmic radius loss is below that tolerance. Next choose $r$ so that the ratio of record exponents to row exponents is sufficiently small. Finally choose the finite-field size large enough that exceptional probabilities and fixed combinatorial overheads are negligible at those already fixed parameters.

This order is part of the proof. Increasing all parameters simultaneously without tracking their dependencies could destroy either accuracy or the entropy gap. The resulting row packing lower bound and compressed-list upper bound contradict the proposed uniform duality estimate at the same scales. The asserted counterexample rests on the source’s partition and compression lemmas, not merely on comparing formal dimension counts.

See Also

• Cotype and approximation gives a restricted entropy-duality consequence with constants controlled by geometric hypotheses.
• Nonlinear metric equivalence concerns a different way that metric information can fail to determine linear structure.

🏷️ Manuscripts and verification scope

• Counterexamples to the duality conjecture for metric entropy — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the universal-constant counterexample with arbitrary finite-cover centers and a sequence with vanishing dual-to-primal logarithmic entropy ratio. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Counterexamples to the duality conjecture for metric entropy.