diff b34550f..f6bf760 metric_entropy_duality_counterexamples_v2.txt
diff --git a/metric_entropy_duality_counterexamples_v2.txt b/metric_entropy_duality_counterexamples_v2.txt
index a8b7c09..198467f 100644
--- a/metric_entropy_duality_counterexamples_v2.txt
+++ b/metric_entropy_duality_counterexamples_v2.txt
@@ -28,7 +28,7 @@ the sharp form is the following.
Artstein, Milman, Szarek and Tomczak-Jaegermann record this as Conjecture 1,
noting the operator-theoretic origin in Pietsch's 1972 work.
-Available at ./artstein-milman-szarek-tomczak-2004-entropy-duality-math0407238.pdf
+Available at ./pdf/artstein-milman-szarek-tomczak-2004-entropy-duality-math0407238.pdf
The right-hand inequality is the substantive half. The result below shows
that it fails for every proposed pair of constants, already when L is a cube.
@@ -49,14 +49,14 @@ geometric or sequence-regularity hypotheses, and estimates whose loss depends
on the rank. Thus a single universal pair for all bodies and dimensions was
open.
-Available at ./bourgain-pajor-szarek-tomczak-1989-duality-entropy-numbers-ihes-m89-01.pdf
+Available at ./pdf/bourgain-pajor-szarek-tomczak-1989-duality-entropy-numbers-ihes-m89-01.pdf
Artstein, Milman and Szarek settle the dimension-free conjecture when one of
the two bodies is a Euclidean ball, and hence when either body is an
ellipsoid. The comparison holds uniformly over symmetric convex bodies and
over n whenever one side is Hilbertian.
-Available at ./artstein-milman-szarek-2004-duality-metric-entropy-math0407236.pdf
+Available at ./pdf/artstein-milman-szarek-2004-duality-metric-entropy-math0407236.pdf
"... this verifies the duality conjecture for entropy numbers of linear
operators, posed by Pietsch in 1972, in the central case when either the
@@ -68,7 +68,7 @@ logarithmic factors in the dimension, proving
N(K, T) <= N(T^o, (C log n)^{-1} K^o)^{C log n log log n} with universal C.
A loss that depends on n is compatible with the failure of a universal pair.
-Available at ./milman-2007-two-duality-relations-math0603461.pdf
+Available at ./pdf/milman-2007-two-duality-relations-math0603461.pdf
A parallel line concerns convexified packing. Artstein, Milman, Szarek and
Tomczak-Jaegermann prove universal duality for a packing number whose new
@@ -78,7 +78,7 @@ constants depending on that bound. Hu, Peale and Reingold study the dual
covering numbers of function classes and obtain a comparison with an explicit
prefactor depending on the approximation scale and the sup norms of the class.
-Available at ./hu-peale-reingold-2022-metric-entropy-duality-outcome-indistinguishability.pdf
+Available at ./pdf/hu-peale-reingold-2022-metric-entropy-duality-outcome-indistinguishability.pdf
The construction also borrows two standard tools, each proved from scratch
so that nothing is assumed. The finite-field argument uses the
@@ -89,8 +89,8 @@ modern formulation, to Drapal and Vojtechovsky. Convex-hull approximation in
the style of Maurey, as developed for small finite sets by Mendelson, is a
third source of technique.
-Available at ./drapal-vojtechovsky-2009-symmetric-multilinear-forms-1509.05707.pdf
-Available at ./mendelson-2001-size-of-convex-hulls-small-sets.pdf
+Available at ./pdf/drapal-vojtechovsky-2009-symmetric-multilinear-forms-1509.05707.pdf
+Available at ./pdf/mendelson-2001-size-of-convex-hulls-small-sets.pdf
The strategy is a real matrix whose rows and columns behave oppositely. The
rows are pairwise at sup-norm distance at least one, so covering by a cube
@@ -101,9 +101,9 @@ with large N(K, L) and small N(L^o, a^{-1} K^o). The rows and the list are
then built together, rows from symmetric multilinear forms over a finite
field, columns from the graph distances attached to a family of partitions.
-Notation used throughout. For a finite set S write B_infty^S = [-1,1]^S =
+Notation used throughout. For a finite set S write B_infinity^S = [-1,1]^S =
{f : S -> R : |f(s)| <= 1 for all s in S} and B_1^S = {lambda in R^S :
-sum_s |lambda_s| <= 1}; write ||f||_{infty,S} = max_s |f(s)|. For a finite
+sum_s |lambda_s| <= 1}; write ||f||_{infinity,S} = max_s |f(s)|. For a finite
set of vectors V, absconv(V) is the convex hull of V together with -V, that
is, the set of sums sum_j lambda_j v_j with v_j in V and sum_j |lambda_j| <= 1.
In a graph on a finite set, d(x, z) is the fewest edges in a path and equals
@@ -120,34 +120,34 @@ convex hull of the columns.
Matrix-to-body lemma. Let X and Y be finite nonempty sets, and for each
y in Y let g_y : X -> R. Put R_x = (g_y(x))_{y in Y} in R^Y,
f_lambda = sum_{y in Y} lambda_y g_y, and F = { f_lambda :
- sum_y |lambda_y| <= 1 }. Suppose (i) ||R_x - R_{x'}||_{infty,Y} >= 1 for
+ sum_y |lambda_y| <= 1 }. Suppose (i) ||R_x - R_{x'}||_{infinity,Y} >= 1 for
distinct x, x' in X, and (ii) for some eps > 0 there is a list of M
functions on X such that every f in F is within eps, in the sup norm on X,
of a list function; the list functions need not lie in F. For t > 0 set
- K = 3 absconv{R_x : x in X} + t B_infty^Y and L = B_infty^Y. Then K and L
+ K = 3 absconv{R_x : x in X} + t B_infinity^Y and L = B_infinity^Y. Then K and L
are origin-symmetric compact convex bodies with nonempty interior in R^Y,
the covering numbers may use arbitrary centers, and
N(K, L) >= |X|, N(L^o, (6 eps + 2 t) K^o) <= M.
Proof. The set absconv{R_x} is the convex hull of the finitely many vectors
+R_x and -R_x, hence compact, convex, symmetric, and it contains zero. Adding
-t B_infty^Y keeps these properties and gives K nonempty interior in the full
+t B_infinity^Y keeps these properties and gives K nonempty interior in the full
space. The cube L has the same properties.
For the first inequality, each point 3 R_x lies in K, and distinct such
-points are at sup-distance at least 3. A translate of L = B_infty^Y has
+points are at sup-distance at least 3. A translate of L = B_infinity^Y has
sup-diameter at most 2: if a and b lie in z + L then a - b lies in L - L = 2L
-and ||a - b||_{infty,Y} <= 2. So one translate of L meets the set
+and ||a - b||_{infinity,Y} <= 2. So one translate of L meets the set
{3 R_x : x in X} in at most one point, and N(K, L) >= |X|.
For the second, the support function h_K(delta) = sup_{z in K} <z, delta>
equals 3 max_x |<R_x, delta>| + t sum_y |delta_y|. A linear functional
attains its maximum over the finite convex hull of {+R_x, -R_x} at one of
-those vectors, giving 3 max_x |<R_x, delta>|; over t B_infty^Y the maximum is
+those vectors, giving 3 max_x |<R_x, delta>|; over t B_infinity^Y the maximum is
t sum_y |delta_y|, attained by matching each sign; the two terms of the
Minkowski sum are chosen independently, so the maxima add. Since
<R_x, delta> = f_delta(x),
- h_K(delta) = 3 ||f_delta||_{infty,X} + t ||delta||_1.
+ h_K(delta) = 3 ||f_delta||_{infinity,X} + t ||delta||_1.
The same cube computation gives L^o = B_1^Y = {lambda in R^Y :
||lambda||_1 <= 1}.
@@ -156,10 +156,10 @@ list function within eps of f_lambda; hypothesis (ii) guarantees one exists.
This splits B_1^Y into at most M nonempty clusters, and from each nonempty
cluster one coefficient vector lambda^(k) in B_1^Y is selected. For lambda and
lambda^(k) in the same cluster the triangle inequality gives
-||f_lambda - f_lambda^(k)||_{infty,X} <= 2 eps, while both vectors lie in
+||f_lambda - f_lambda^(k)||_{infinity,X} <= 2 eps, while both vectors lie in
B_1^Y, so ||lambda - lambda^(k)||_1 <= 1 + 1 = 2. With delta = lambda -
lambda^(k),
- h_K(delta) = 3 ||f_lambda - f_lambda^(k)||_{infty,X}
+ h_K(delta) = 3 ||f_lambda - f_lambda^(k)||_{infinity,X}
+ t ||lambda - lambda^(k)||_1
<= 3 (2 eps) + t (2) = 6 eps + 2 t.
For c > 0 positivity and positive homogeneity of h_K give the equivalence
@@ -227,7 +227,7 @@ contributes zero, and d = infinity makes every indicator vanish.
Compression proposition. Under the setup above there is a finite list Acal
of real functions on X, of cardinality Q, such that every f in F_+ has
A in Acal with f(x) - 3 theta <= A(x) <= f(x) + theta for every x in X.
- In particular ||f - A||_{infty,X} <= 3 theta, and the list can be chosen
+ In particular ||f - A||_{infinity,X} <= 3 theta, and the list can be chosen
with
log Q <= h s log q + C_{h,theta,u},
C_{h,theta,u} = log u + h s 2^u log(1 + s 2^u / theta).
@@ -309,14 +309,14 @@ shared data, not extra choices per approximant.
and F = {f_lambda : lambda in B_1^Y} = absconv{g_y : y in Y}. Then a list
of at most Q^2 functions approximates every f_lambda in F to uniform error
6 theta, and B_1^Y splits into at most Q^2 nonempty clusters with
- ||f_lambda - f_lambda'||_{infty,X} <= 12 theta for lambda, lambda' in the
+ ||f_lambda - f_lambda'||_{infinity,X} <= 12 theta for lambda, lambda' in the
same cluster.
Proof. Write lambda = lambda^+ - lambda^- with lambda_y^+ = max{lambda_y, 0}
and lambda_y^- = max{-lambda_y, 0}; each part is nonnegative of total mass at
most one. The compression proposition supplies A^+, A^- in Acal with
-||f_{lambda^+} - A^+||_{infty,X} <= 3 theta and
-||f_{lambda^-} - A^-||_{infty,X} <= 3 theta, so A^+ - A^- approximates
+||f_{lambda^+} - A^+||_{infinity,X} <= 3 theta and
+||f_{lambda^-} - A^-||_{infinity,X} <= 3 theta, so A^+ - A^- approximates
f_lambda to within 6 theta. The differences A^+ - A^- range over at most Q^2
functions; ordering the list and assigning each lambda in B_1^Y to the first
approximant within 6 theta yields at most Q^2 nonempty fibers, and the
@@ -375,7 +375,7 @@ polarization, recovery of a symmetric multilinear form in characteristic
exceeding the degree; the coordinate statement above is the precise form
needed, and matches Ferrero and Micali and Drapal and Vojtechovsky.
-Available at ./drapal-vojtechovsky-2009-symmetric-multilinear-forms-1509.05707.pdf
+Available at ./pdf/drapal-vojtechovsky-2009-symmetric-multilinear-forms-1509.05707.pdf
For an ordered tuple i = (i_1, ..., i_h) in [u]^h let S(i) = {i_1, ..., i_h}.
The value Z(t_{i_1}, ..., t_{i_h}) is a polynomial of total degree h in the
@@ -408,7 +408,7 @@ nonzero.
Then |X| = p^{D_h}, each L_i has at most q = p^{D_{h-1}} labels, and for
every distinct x, y in X there is T in Tcal with d_T(x, y) > h.
Consequently, with Y = X x Tcal and R_x = (g_{(v,T)}(x))_{(v,T) in Y} in
- R^Y, the rows satisfy ||R_x - R_y||_{infty,Y} = 1 whenever x != y.
+ R^Y, the rows satisfy ||R_x - R_y||_{infinity,Y} = 1 whenever x != y.
Proof. The cardinality and label bound are as computed. Fix distinct x, y and
apply the robust-directions proposition to Z = y - x, getting T in Tcal with Z
@@ -452,7 +452,7 @@ order of dependence so the field size can absorb the encoding term.
m = |X| = p^{D_h} > 1, each label map has at most q = p^{D_{h-1}} labels,
the columns are indexed by Y = X x Tcal with Tcal = {T subset [u] :
|[u]∖T| <= theta u}, and the real row vectors obey
- ||R_x - R_{x'}||_{infty,Y} = 1 for distinct x, x'. The set Y is finite and
+ ||R_x - R_{x'}||_{infinity,Y} = 1 for distinct x, x'. The set Y is finite and
nonempty, and the finite field serves only to build the index and label sets;
the matrix entries and the bodies below are real.
@@ -462,7 +462,7 @@ order of dependence so the field size can absorb the encoding term.
6 theta list of at most Q^2 functions. Apply the matrix-to-body lemma with
eps = 6 theta and t = theta. It produces origin-symmetric bodies in
dimension n = |Y|,
- K = 3 absconv{R_x : x in X} + theta B_infty^Y, L = B_infty^Y,
+ K = 3 absconv{R_x : x in X} + theta B_infinity^Y, L = B_infinity^Y,
with
N(K, L) >= m, N(L^o, 38 theta K^o) <= Q^2,
since 6 eps + 2 t = 6(6 theta) + 2 theta = 38 theta. Because
@@ -519,7 +519,7 @@ Since (L/A)^o = A L^o and simultaneous dilation preserves Mhat,
<= N(L^o, K^o/(8A))^2,
the last step being Step 1 with T = L^o and B = K^o/(2A).
-Available at ./artstein-milman-szarek-tomczak-2004-entropy-duality-math0407238.pdf
+Available at ./pdf/artstein-milman-szarek-tomczak-2004-entropy-duality-math0407238.pdf
Step 3: choose K, L from the main theorem with a = 8A and b = 2g. Then
log N(K, L) > 2g log N(L^o, K^o/(8A)). Together with Step 2,