diff 65affb3..c139821 metric_entropy_duality_counterexamples_v2.txt
diff --git a/metric_entropy_duality_counterexamples_v2.txt b/metric_entropy_duality_counterexamples_v2.txt
index ed51e5b..d03f9e7 100644
--- a/metric_entropy_duality_counterexamples_v2.txt
+++ b/metric_entropy_duality_counterexamples_v2.txt
@@ -1,1573 +1,950 @@
METRIC ENTROPY DUALITY: A COUNTEREXAMPLE
-A clear rewrite for high-school readers
+A self-contained proof for readers comfortable with basic linear algebra
-0. WHAT THIS DOCUMENT IS
-This document explains a research theorem in plain language.
+WHAT THIS DOCUMENT SHOWS
-The theorem says that a famous guess about "covering numbers" is false.
-The guess is called the duality conjecture for metric entropy.
-For every proposed pair of universal constants, we build a counterexample.
+The duality conjecture for metric entropy says that passing to polar
+bodies preserves "covering complexity" up to universal constants. We
+disprove it. For every proposed pair of universal constants a,b >= 1,
+we build one origin-symmetric convex body K in some R^n such that, with
+L = [-1,1]^n,
-You do not need to know the research literature to follow the proof.
-You need:
-- vectors in R^n and dot products,
-- the idea of a convex set,
-- logarithms,
-- finite fields F_p, meaning arithmetic modulo a prime p,
-- patience with long formulas.
+ log N(K,L) > b log N(L^o, a^{-1} K^o).
-On a first reading, read Sections 1, 2, 3, and 7.
-The middle sections prove the three tools used in Section 7.
+Here N(A,B) is the least number of translates of B that cover A. The
+dimension n grows with a and b; we make no claim in fixed dimension.
-1. THE QUESTION
-
-1.1 Covering numbers
-
-Let A and B be bounded sets in a real vector space.
-Assume B has nonempty interior.
-Let N(A,B) be the smallest number of translates of B needed to cover A.
-
-A translate of B is a set x+B = {x+b : b in B}.
-The center x may be anywhere in the ambient space.
-
-Example. In the plane, let B be a square of side 2 centered at the origin.
-How many copies of B does it take to cover a large disk A?
-That number is N(A,B).
+How to read this. Sections 1-3 set up the question and state the plan.
+Sections 4-7 prove the four pieces and assemble them. Section 8 gives
+one consequence. Every step is proved from scratch; no external results
+are assumed.
-Covering numbers measure complexity.
-A set that needs many small copies is complicated.
-A set that needs few copies is simple.
-1.2 Convex bodies and polar
-
-A convex body is a compact convex set with nonempty interior.
-It is origin-symmetric if x in K implies -x in K.
-
-For an origin-symmetric convex body K in R^n, the polar body is
+1. THE QUESTION
- K^o = { y in R^n : <x,y> <= 1 for every x in K }.
+1.1 Covering numbers.
-Here <x,y> is the dot product.
-The polar is another origin-symmetric convex body.
-It records all linear measurements that are at most 1 on K.
+Let A and B be bounded sets in a real vector space; B has nonempty
+interior. Let N(A,B) be the smallest number of translates x + B whose
+union contains A. The centers x are arbitrary: they need not lie in A.
-Example. Let L = [-1,1]^n, the cube.
-Then L^o = { y : |y_1| + ... + |y_n| <= 1 }, the diamond-like body.
+Covering numbers measure complexity. A set that needs many small
+translates is complicated; one that needs few is simple.
-1.3 The duality conjecture
+Example: covering a disk of radius R by translates of a square of side
+2 needs roughly R^2 copies. The exact count is N(disk, square).
-For origin-symmetric convex bodies K and L in R^n, the duality conjecture
-for metric entropy asks whether there are absolute constants a,b >= 1
-such that, for every dimension n and every pair K,L,
+1.2 Convex bodies and polar.
- (1/b) log N(L^o, a K^o)
- <= log N(K,L)
- <= b log N(L^o, a^-1 K^o).
+A convex body is a compact convex set with nonempty interior. It is
+origin-symmetric if x in K implies -x in K.
-The constants a and b must not depend on n, K, or L.
-This is Conjecture 1 in Artstein-Milman-Szarek 2004, building on
-Pietsch's 1972 operator-theoretic question.
+The polar of an origin-symmetric convex body K in R^n is
-The conjecture says that passing to the polar pair preserves covering
-complexity up to a universal change of scale and a universal multiplicative
-constant. In words: covering K by copies of L should be roughly the same
-as covering L^o by copies of K^o.
+ K^o = { y in R^n : <x, y> <= 1 for every x in K }.
-1.4 The main theorem
+It is another origin-symmetric convex body. It lists the linear
+functionals that are at most 1 on K.
-Theorem 1. For every a,b >= 1, there are a positive integer n and an
-origin-symmetric convex body K in R^n such that, with L = [-1,1]^n,
+Example: for the cube L = [-1,1]^n, L^o = { y : sum_i |y_I| <= 1 }, the
+diamond (cross-polytope).
- log N(K,L) > b log N(L^o, a^-1 K^o).
+1.3 The duality conjecture.
-So the upper bound in the conjecture fails for every proposed pair (a,b).
-The dimension n depends on a and b and grows.
-No claim is made about a fixed dimension.
+Fix origin-symmetric convex bodies K, L in R^n. The duality conjecture
+for metric entropy asks whether there are absolute constants a,b >= 1,
+independent of n, K, L, such that for every such pair
-The rest of this document proves Theorem 1 and one consequence.
+ (1/b) log N(L^o, a K^o) <= log N(K,L)
+ <= b log N(L^o, a^{-1} K^o).
-1.5 The shape of the counterexample
+This is Conjecture 1 of Artstein-Milman-Szarek (2004), who attribute
+the operator-theoretic origin to Pietsch (1972).
-We build a real matrix with two opposite properties:
+In words: covering K by copies of L should be roughly the same task as
+covering L^o by copies of K^o, after a universal change of scale a and
+a universal multiplicative loss b.
- (A) It has many rows, and any two rows are far apart in the sup norm.
- (B) The absolutely convex hull of its columns has a small uniform
- approximation list.
+1.4 The main theorem.
-Property (A) makes N(K,L) large.
-Property (B) makes N(L^o, a^-1 K^o) small.
-A simple geometric lemma turns the matrix into the bodies K and L.
-
-The hard part is making (A) and (B) true at the same time.
-We use partitions to compress the columns, and finite fields to separate
-the rows.
+Theorem 1. For every a,b >= 1 there are a positive integer n and an
+origin-symmetric convex body K in R^n such that, with L = [-1,1]^n,
-2. NOTATION AND BASIC OBJECTS
+ log N(K,L) > b log N(L^o, a^{-1} K^o).
-2.1 Finite sets and sup norms
+So the upper bound in the conjecture fails for every proposed (a,b). We
+prove Theorem 1 in Section 7, and one consequence for convexified
+packing in Section 8.
-All logarithms in this document are natural logarithms.
-The binomial coefficient binom(a,b) is a!/(b!(a-b)!).
-For a finite set S, write
+2. NOTATION
- B_infty^S = [-1,1]^S = { f : S -> R : |f(s)| <= 1 for all s in S },
- B_1^S = { lambda in R^S : sum_{s in S} |lambda_s| <= 1 }.
+All logarithms are natural. binom(n,k) = n(n-1)...(n-k+1)/k! is the
+usual binomial coefficient.
-For a function f on S, the sup norm is
+For a finite set S:
+ B_infty^S = [-1,1]^S = { f : S -> R : |f(s)| <= 1 for all s }
+ B_1^S = { lambda in R^S : sum_{s in S} |lambda_s| <= 1 }
||f||_{infty,S} = max_{s in S} |f(s)|.
-If X is a finite set and g_y : X -> R for y in Y, the row R_x in R^Y is
-
- R_x = (g_y(x))_{y in Y}.
-
-The sup norm on R^Y is ||R||_{infty,Y} = max_{y in Y} |R_y|.
-
-2.2 Absolutely convex hull
-
-For a finite set of vectors V, the absolutely convex hull absconv(V)
-is the convex hull of V union -V.
-Equivalently, it is the set of all finite sums
-
- sum_j lambda_j v_j
-
-with v_j in V and sum_j |lambda_j| <= 1.
-
-2.3 Graphs and distance
-
-Let X be a finite set.
-A graph on X has vertices X and some edges between pairs of vertices.
-The graph distance d(x,z) is the smallest number of edges in a path from
-x to z. If there is no path, set d(x,z) = infinity.
-
-A partition of X is a map L : X -> Sigma.
-The set Sigma is the set of labels.
-Two points are in the same class if they have the same label.
-
-2.4 Symmetric multilinear forms
-
-Let p be a prime and let E = F_p^r be the r-dimensional vector space
-over the field with p elements.
-
-A map Z : E^h -> F_p is h-linear if it is linear in each argument
-when the other h-1 arguments are fixed.
-It is symmetric if swapping any two arguments does not change the value.
-
-The space of symmetric h-linear forms on E is written Sym^h(E^*).
-We also use Sym^0(E^*) = F_p.
-
-The number D_j is
-
- D_j = binom(r+j-1,j).
-
-This is the number of multisets of size j chosen from r elements.
-It is also the dimension of Sym^j(E^*) over F_p.
-
-2.5 The main parameters
-
-The proof uses these symbols.
-They are chosen in Section 7.
-
- a,b proposed constants in Theorem 1, a,b >= 1
- theta a small positive number, theta = 1/(1000a)
- s ceil(1/theta)
- h a positive integer with log 3 / log(h+1) <= theta
- r a large positive integer
- D_j binom(r+j-1,j)
- w 2 D_h
- u ceil(h w / theta)
- p a large prime
- X Sym^h(F_p^r), the row index set
- q p^{D_{h-1}}, the number of labels per partition
- Y X times T, the column index set
- T the family of allowed index sets T subset [u]
-
-3. THE PLAN IN DETAIL
-
-3.1 Step 1: matrix to bodies
-
-Lemma 4.1 below is the geometric conversion.
-It says:
-
-Suppose X and Y are finite nonempty sets, and g_y : X -> R for y in Y.
-Let
-
- R_x = (g_y(x))_{y in Y},
- F = { sum_y lambda_y g_y : sum_y |lambda_y| <= 1 }.
-
-Suppose:
-
- (i) ||R_x - R_x'||_{infty,Y} >= 1 for all distinct x,x' in X.
- (ii) For some eps > 0, there is a list of M functions on X such that
- every member of F is within eps in sup norm of a list function.
-
-For t > 0 set
-
- K = 3 absconv{R_x : x in X} + t B_infty^Y,
- L = B_infty^Y.
-
-Then K and L are origin-symmetric convex bodies with nonempty interior,
-and
-
- N(K,L) >= |X|,
- N(L^o, (6 eps + 2t) K^o) <= M.
-
-So we need a matrix with many 1-separated rows and a small eps-net for
-the absolutely convex hull of its columns.
-
-3.2 Step 2: compression from partitions
-
-We build columns from partitions.
-Suppose X carries u partitions L_i : X -> Sigma_i, each with at most q
-labels. For a set T of partition indices, join two points when they share
-a label in some partition indexed by T. Let d_T be the graph distance.
-
-For a center v and a set T, define a column
-
- g_{(v,T)}(x) = phi_h(d_T(x,v)),
-
-where
-
- phi_h(d) = max{0, 1 - log(d+1)/log(h+1)}
- for finite d, and phi_h(infinity) = 0.
-
-This column is 1 at x = v and decreases to 0 as x moves away from v.
-It reaches 0 once the distance is at least h.
-
-Proposition 5.2 says: if the family T is admissible, meaning
-
- |[u] \ T| <= theta u for every T in T,
-
-then the positive column class has a uniform 3 theta approximation list
-of size Q 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).
-
-The key point: Q depends on q and u, not on |X|.
-The number q can be much smaller than |X|.
-
-Corollary 5.3 extends this to signed coefficients.
-The absolutely convex hull of the columns has a uniform 6 theta
-approximation list of size at most Q^2.
-
-3.3 Step 3: finite-field partitions
-
-We need many rows but few labels.
-Take
-
- X = Sym^h(F_p^r).
-
-Then
-
- |X| = p^{D_h},
- D_h = binom(r+h-1,h).
-
-For each direction t_i in F_p^r, define a partition by contraction:
-
- L_i(x) = x(t_i, ., ..., .).
-
-This is a symmetric (h-1)-linear form.
-The number of possible labels is at most
+If X, Y are finite sets and g_y : X -> R for each y in Y, then
+R_x = (g_y(x))_{y in Y} in R^Y is the row at x, and
+f_lambda = sum_{y in Y} lambda_y g_y : X -> R is a column combination.
- q = p^{D_{h-1}},
- D_{h-1} = binom(r+h-2,h-1).
+For a finite set of vectors V, absconv(V) is the convex hull of V
+together with -V. Equivalently, absconv(V) consists of all finite sums
+sum_j lambda_j v_j with v_j in V and sum_j |lambda_j| <= 1.
-The ratio is
+In a graph on a finite set X:
+- graph distance d(x,z) is the fewest edges in a path from x to z;
+- if no such path exists, d(x,z) = infinity.
- D_{h-1} / D_h = h / (r+h-1).
+A partition of X is a map L : X -> Sigma. The set Sigma is the label
+set; two points are in the same class if their labels agree.
-When r is large compared with h, this ratio is small.
-So we get p^{D_h} rows but only p^{D_{h-1}} labels per partition.
+Over a field, the integer
-Proposition 6.3 chooses directions t_1,...,t_u so that every nonzero
-symmetric h-linear form Z has a large set T of indices such that
-Z(t_{i_1},...,t_{i_h}) is nonzero for every tuple from T.
+ D_j = binom(r+j-1, j)
-Proposition 6.4 uses this to show that every two distinct rows x,y in X
-have distance greater than h in the graph for some admissible T.
-Then the column at (x,T) separates x from y by exactly 1.
-So the rows are 1-separated.
+counts multisets of size j drawn from an r-element set.
-3.4 Step 4: choose the numbers
+We write [u] = {1, 2, ..., u}.
-In Section 7 we choose:
- theta = 1/(1000a),
- h with log 3 / log(h+1) <= theta,
- r with r+h-1 > 8 b h^2 s,
- p with p > max{h, h^2 u^{2h}, exp(8bC/D_h)}.
+3. THE STRATEGY
-Then the compression bound gives
+We build a real matrix whose entries lie in [0,1] and whose rows and
+columns have opposite behavior:
- log(Q^2) / log |X| < 1/(2b).
+ (A) many rows, pairwise at sup-norm distance at least 1;
+ (B) a small uniform-approximation list for the absolutely convex
+ hull of the columns.
-The matrix-to-bodies lemma gives
+Section 4 turns such a matrix into a pair of convex bodies with the
+covering bounds we want. Property (A) makes N(K,L) large; property (B)
+makes N(L^o, a^{-1} K^o) small.
- N(K,L) >= |X|,
- N(L^o, a^-1 K^o) <= Q^2.
+Then we produce such a matrix.
-Therefore
+Columns come from partitions. Each partition L_i : X -> Sigma_i
+compresses X to at most q labels. Using a family T of partitions and
+the graph distances d_T, we build profiles phi_h(d_T(x,v)) as columns.
+A uniform approximation argument (Section 5) shows that the
+nonnegative combinations of these columns can be approximated by a
+list whose size Q depends on q and u but not on |X|.
- b log N(L^o, a^-1 K^o)
- <= b log(Q^2)
- < (1/2) log |X|
- < log N(K,L).
+Rows come from finite fields. Take X = Sym^h(F_p^r), the space of
+symmetric h-linear forms. The number of rows is p^{D_h}. Each
+partition is contraction by a fixed direction and has only p^{D_{h-1}}
+labels. Taking r >> h makes D_{h-1}/D_h = h/(r+h-1) small. Choosing
+the directions carefully (Section 6) makes every two distinct rows
+separated by distance > h in some graph, so a single column separates
+them by exactly 1.
-That is Theorem 1.
+Section 7 chooses (theta, h, r, p) in their order of dependence and
+combines the pieces to defeat any proposed (a,b). Section 8 extracts
+the convexified-packing consequence.
-4. STEP 1: FROM A MATRIX TO CONVEX BODIES
+4. FROM A MATRIX TO CONVEX BODIES
-This section proves the geometric conversion.
-It is elementary: rows that are far apart force many translates,
-and a small list for column combinations gives a small cover of the polar.
+This section is purely geometric. Far-apart rows force many translates;
+a small column list gives a small cover of the polar.
-4.1 Lemma (matrix-to-body conversion)
-
-Let X and Y be finite nonempty sets.
-For each y in Y let g_y : X -> R.
-Write
+Lemma 4.1 (matrix-to-body conversion).
+Let X, Y be finite nonempty sets. For each y in Y let g_y : X -> R.
+Set
- R_x = (g_y(x))_{y in Y} in R^Y,
+ R_x = (g_y(x))_{y in Y},
f_lambda = sum_{y in Y} lambda_y g_y,
- F = { f_lambda : lambda in R^Y, sum_y |lambda_y| <= 1 }.
-
-Suppose
-
- ||R_x - R_x'||_{infty,Y} >= 1 for all distinct x,x' in X.
-
-Suppose also that for some eps > 0 there is a list of M functions on X
-such that every f in F is within eps of a list function in sup norm.
-The list functions need not belong to F.
+ F = { f_lambda : sum_{y in Y} |lambda_y| <= 1 }.
-For t > 0 set
+Suppose:
- K = 3 absconv{R_x : x in X} + t B_infty^Y,
- L = B_infty^Y.
+ (i) ||R_x - R_{x'}||_{infty,Y} >= 1 for all distinct x, x' in X;
+ (ii) there is a finite 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 belong to F.)
-Then K and L are origin-symmetric compact convex bodies with nonempty
-interior in R^Y, and
+For t > 0 set K = 3 absconv{R_x : x in X} + t B_infty^Y and
+L = B_infty^Y. Then K, L are origin-symmetric convex bodies with
+nonempty interior in R^Y, and
- N(K,L) >= |X|,
- N(L^o, (6 eps + 2t) K^o) <= M.
+ N(K, L) >= |X|,
+ N(L^o, (6 eps + 2 t) K^o) <= M.
Proof.
-First, K and L.
-The set absconv{R_x : x in X} is compact, convex, symmetric, and contains 0.
-Adding t B_infty^Y gives nonempty interior because t > 0.
-The cube L is also compact, convex, symmetric, and has nonempty interior.
-
-First inequality: N(K,L) >= |X|.
+Bodies. absconv{R_x} is compact, convex, symmetric, and contains 0.
+Adding t B_infty^Y makes K contain a small ball, so K has nonempty
+interior. L is a cube, so it has nonempty interior.
-Each point 3R_x belongs to K.
-If x != x', then
+First inequality. Each point 3 R_x lies in K, and for x != x',
- ||3R_x - 3R_x'||_{infty,Y} >= 3.
+ ||3 R_x - 3 R_{x'}||_{infty,Y} >= 3.
-Any translate of L has diameter at most 2 in sup norm.
-Indeed, if a and b are in z+L, then a-b is in L-L = 2L, so
-||a-b||_{infty,Y} <= 2.
-Therefore one translate of L contains at most one of the points 3R_x.
-To cover all |X| points, we need at least |X| translates.
-Thus N(K,L) >= |X|.
+Any translate of L has sup-diameter at most 2. Indeed, if a, b are in
+z + L then a - b is in L - L = 2 L, so ||a - b||_{infty,Y} <= 2. So
+one translate of L can contain at most one of the points 3 R_x. At
+least |X| translates are required.
-Second inequality: N(L^o, (6 eps + 2t) K^o) <= M.
+Second inequality. The support function
-We use the support function. For delta in R^Y define
+ h_K(delta) = sup_{z in K} <z, delta>
- h_K(delta) = sup_{z in K} <z,delta>.
-
-A direct calculation gives
-
- h_K(delta)
- = 3 max_{x in X} |<R_x,delta>|
- + t sum_{y in Y} |delta_y|.
-
-Why? The maximum of <.,delta> over absconv{R_x} is
-max_x |<R_x,delta>|.
-The maximum over B_infty^Y is sum_y |delta_y|.
-The Minkowski sum allows these two maxima to be added.
-
-Also
-
- <R_x,delta> = sum_y delta_y g_y(x) = f_delta(x).
-
-So
+equals 3 max_x |<R_x, delta>| + t sum_y |delta_y|. Indeed, <.,delta>
+attains its maximum over the finite set {+-R_x} at one of those
+vectors, and over B_infty^Y its maximum is sum_y |delta_y| (attained by
+choosing the sign of each coordinate). The Minkowski sum lets the two
+maxima add. Since <R_x, delta> = f_delta(x),
h_K(delta) = 3 ||f_delta||_{infty,X} + t ||delta||_1.
-The polar of the cube L is the diamond
-
- L^o = B_1^Y = { lambda in R^Y : ||lambda||_1 <= 1 }.
-
-Now use the approximation list.
-Order its M functions.
-For each lambda in B_1^Y, assign lambda to the first list function A with
+The polar of the cube is the diamond: L^o = B_1^Y.
- ||f_lambda - A||_{infty,X} <= eps.
+Now use the list. Order its M entries. For each lambda in B_1^Y
+assign lambda to the first list function A with
+||f_lambda - A||_{infty,X} <= eps. Hypothesis (ii) ensures that at
+least one such function exists. This partitions B_1^Y into at most M
+nonempty clusters; pick one coefficient vector lambda^(k) in B_1^Y
+from each nonempty cluster.
-The hypothesis guarantees that at least one such function exists.
-This partitions B_1^Y into at most M nonempty clusters.
-From each nonempty cluster choose one actual coefficient vector
-lambda^(k) in B_1^Y.
-
-For any lambda in the same cluster,
+For any lambda in the same cluster as lambda^(k),
||f_lambda - f_lambda^(k)||_{infty,X} <= 2 eps,
||lambda - lambda^(k)||_1 <= 2.
-The second inequality holds because both vectors are in B_1^Y:
-
- ||lambda - lambda^(k)||_1
- <= ||lambda||_1 + ||lambda^(k)||_1
- <= 2.
-
-Now apply the support formula to delta = lambda - lambda^(k):
-
- h_K(lambda - lambda^(k))
- = 3 ||f_lambda - f_lambda^(k)||_{infty,X}
- + t ||lambda - lambda^(k)||_1
- <= 3 * 2 eps + t * 2
- = 6 eps + 2t.
-
-Recall the scaling rule for polars:
-
- delta in c K^o <=> h_K(delta) <= c for c > 0.
-
-Therefore every lambda in the cluster lies in
-
- lambda^(k) + (6 eps + 2t) K^o.
-
-There are at most M clusters, so these translates cover B_1^Y = L^o.
-Hence
-
- N(L^o, (6 eps + 2t) K^o) <= M.
-
-This proves the lemma.
-
-4.2 How the lemma is used
-
-For proposed constants a,b >= 1, it is enough to find a matrix and
-positive numbers eps,t such that
-
- log |X| > b log M,
- 6 eps + 2t <= a^-1.
-
-Then the lemma gives
+The second bound holds because both vectors are in B_1^Y:
+||lambda - lambda^(k)||_1 <= ||lambda||_1 + ||lambda^(k)||_1 <= 1 + 1.
- N(K,L) >= |X|,
- N(L^o, a^-1 K^o) <= N(L^o, (6 eps + 2t) K^o) <= M.
+Set delta = lambda - lambda^(k). Then
-The second inequality uses that (6 eps + 2t) K^o is contained in
-a^-1 K^o when 6 eps + 2t <= a^-1.
-Increasing the covering body only makes the cover easier.
-
-Therefore
+ h_K(delta)
+ = 3 ||f_lambda - f_lambda^(k)||_{infty,X}
+ + t ||lambda - lambda^(k)||_1
+ <= 3(2 eps) + t(2)
+ = 6 eps + 2 t.
- b log N(L^o, a^-1 K^o)
- <= b log M
- < log |X|
- <= log N(K,L).
+By definition of the polar and positive homogeneity of h_K,
-This is exactly the failure of the upper bound in the duality conjecture.
+ delta in c K^o iff h_K(delta) <= c (c > 0).
-The rest of the proof constructs such a matrix.
-Section 5 builds the small list for the columns.
-Section 6 separates the rows.
-Section 7 chooses the numbers so that log |X| is much larger than log M.
+So each cluster sits inside lambda^(k) + (6 eps + 2 t) K^o. The at
+most M translates cover B_1^Y = L^o, which is exactly
+N(L^o, (6 eps + 2 t) K^o) <= M.
+Done.
-5. STEP 2: COMPRESSION FROM PARTITIONS
+4.1 How the lemma is used.
-This is the engine of the proof.
-We have u partitions of X, each with at most q labels.
-We build columns from graph distances.
-We show that every nonnegative combination of columns with total mass
-at most 1 can be approximated by a list whose size depends only on
-h, theta, u, q, and not on |X|.
+For proposed a, b >= 1, it suffices to build a matrix and eps, t > 0
+with
-5.1 Setup and the logarithmic profile
+ log |X| > b log M, 6 eps + 2 t <= a^{-1}.
-Let X be a finite nonempty set.
-Let u and q be positive integers.
-For i in [u] = {1,...,u}, let
+Then the lemma gives N(K, L) >= |X| and N(L^o, a^{-1} K^o) <= M. So
- L_i : X -> Sigma_i, |L_i(X)| <= q.
+ b log N(L^o, a^{-1} K^o)
+ <= b log M
+ < log |X|
+ <= log N(K, L),
-Fix 0 < theta < 1 and a nonempty family T of subsets of [u] such that
+which is the failure of the upper bound in the duality conjecture.
- |[u] \ T| <= theta u for every T in T.
-Call such a set T admissible.
+5. COMPRESSION FROM PARTITIONS
-For T in T, form a graph on X.
-Two distinct points x,z are adjacent if
+The engine of the proof: a matrix with many rows but a short column
+list.
- L_i(x) = L_i(z) for some i in T.
+5.1 Setup.
-Let d_T(x,z) be the graph distance.
-If x and z are in different components, set d_T(x,z) = infinity.
+Let X be a finite nonempty set. Let u, q be positive integers and
+L_i : X -> Sigma_i (i = 1, ..., u) be partitions with |L_i(X)| <= q.
-Choose a positive integer h such that
+Fix 0 < theta < 1 and a nonempty family T of subsets of [u] with
- log 3 / log(h+1) <= theta,
- s = ceil(1/theta).
+ |[u] \ T| <= theta u for every T in T.
-Define the logarithmic profile
+Call such T admissible.
- phi_h(d) = max{0, 1 - log(d+1)/log(h+1)}
- for finite d >= 0, and phi_h(infinity) = 0.
+For T in T, put an edge between distinct x, z in X when
+L_i(x) = L_i(z) for some i in T. Let d_T be the graph distance, with
+d_T = infinity between different components.
-The profile is 1 at distance 0 and 0 at distance at least h.
-It decreases as the distance grows.
+Choose a positive integer h with log 3 / log(h+1) <= theta, and put
+s = ceil(1/theta). Define the logarithmic profile
-Set Y = X times T.
-For y = (v,T) in Y, define the column g_y : X -> R by
+ phi_h(d) = max{0, 1 - log(d+1) / log(h+1)} for d in {0,1,2,...},
+ phi_h(infinity) = 0.
- g_y(x) = phi_h(d_T(x,v)).
+So phi_h(0) = 1, phi_h(d) decreases in d, and phi_h(d) = 0 once
+d >= h.
-Then 0 <= g_y(x) <= 1 for all x and y.
+Set Y = X x T. For y = (v, T) in Y define g_y : X -> R by
-For nonnegative coefficients mu_y with total mass at most 1, write
+ g_y(x) = phi_h(d_T(x, v)).
- f_mu = sum_{y in Y} mu_y g_y,
- F_+ = { f_mu : mu_y >= 0, sum_y mu_y <= 1 }.
+All g_y take values in [0,1].
-For a function f on X, let
+For nonnegative coefficients mu_y with sum_y mu_y <= 1 define
- ||f||_{infty,X} = max_{x in X} |f(x)|.
+ f_mu = sum_y mu_y g_y,
+ F_+ = { f_mu : mu_y >= 0, sum_y mu_y <= 1 }.
-We want a uniform approximation list for F_+ whose size is controlled
-by h, theta, u, q, and not by |X|.
+Goal: give a uniform approximation list for F_+ whose size depends only
+on h, theta, u, q -- not on |X|.
-Lemma 5.1 (logarithmic profile).
-For any positive integer h, define
+5.2 The logarithmic profile.
- gamma_j = (log(j+2) - log(j+1)) / log(h+1)
- for 0 <= j < h.
+Lemma 5.1. For any h >= 1, the weights
-The weights gamma_j are positive, sum to 1, and for every
-d in {0,1,2,...} union {infinity},
+ gamma_j = (log(j+2) - log(j+1)) / log(h+1) (j = 0, ..., h-1)
- phi_h(d) = sum_{j=0}^{h-1} gamma_j 1_{d <= j},
+are positive, sum to 1, and for every d in {0, 1, 2, ...} union
+{infinity},
- sum_{j=0}^{h-1} gamma_j 1_{d <= 3j+2}
- <= phi_h(d) + log 3 / log(h+1).
+ (a) phi_h(d) = sum_{j=0}^{h-1} gamma_j 1_{d <= j};
+ (b) sum_{j=0}^{h-1} gamma_j 1_{d <= 3j+2} <= phi_h(d) + log 3 / log(h+1).
-Here 1_{...} is the indicator: it is 1 if the condition is true and
-0 otherwise.
+Here 1_{...} denotes the indicator: 1 if the condition holds, 0
+otherwise.
Proof.
-Positivity is clear because log is increasing.
-The weights telescope:
-
- sum_{j=0}^{h-1} gamma_j
- = (log(h+1) - log 1) / log(h+1)
- = 1.
-For the first identity, suppose 0 <= d < h.
-The sum runs from j = d to j = h-1, so
+Positivity is clear. Telescoping gives sum_{j=0}^{h-1} gamma_j =
+(log(h+1) - log 1) / log(h+1) = 1.
- sum_{j=d}^{h-1} gamma_j
- = (log(h+1) - log(d+1)) / log(h+1)
- = 1 - log(d+1)/log(h+1)
- = phi_h(d).
+Part (a). If d >= h (including d = infinity), both sides are zero. If
+0 <= d < h, the sum runs from j = d to h-1 and equals
+(log(h+1) - log(d+1)) / log(h+1) = phi_h(d).
-If d >= h, including d = infinity, both sides are zero.
+Part (b). Suppose d finite. On the left, index j contributes 1 iff
+d <= 3j+2. For j >= d, we have 3j+2 >= 3d+2 > d, so those j contribute
+to both sides. The extra indices on the left satisfy j < d and
+d <= 3j+2, that is,
-For the second identity, suppose first that d is finite.
-The extra indices counted on the left but not by phi_h(d) satisfy
-
- j < d <= 3j+2.
+ ceil((d-2)/3) <= j <= d-1.
When this set is nonempty, it is the integer interval from
- a_d = max{0, ceil((d+1)/3) - 1}
-
-to
+ a_d = max{0, ceil((d+1)/3) - 1} to b_d = min{h-1, d-1},
- b_d = min{h-1, d-1}.
-
-We have b_d + 2 <= d+1 and a_d + 1 >= (d+1)/3.
-Therefore the extra weight is
+and its total gamma-weight is
sum_{j=a_d}^{b_d} gamma_j
- = (log(b_d+2) - log(a_d+1)) / log(h+1)
- <= log 3 / log(h+1).
-
-An empty interval contributes zero.
-If d = infinity, all indicators on the left vanish.
-This proves the lemma.
+ = (log(b_d + 2) - log(a_d + 1)) / log(h+1).
+Since b_d + 2 <= d+1 and a_d + 1 >= (d+1)/3, this weight is at most
-5.2 The compression proposition
+ (log(d+1) - log((d+1)/3)) / log(h+1) = log 3 / log(h+1).
-Proposition 5.2 (uniform compression).
-Under the setup of Section 5.1, there is a finite list A of real
-functions on X, of cardinality Q, such that every f in F_+ has an
-approximant A_f in A satisfying
+If the interval is empty, the contribution is zero. If d = infinity,
+all indicators on both sides vanish. Done.
- f(x) - 3 theta <= A_f(x) <= f(x) + theta for all x in X.
+5.3 Uniform compression.
-In particular,
+Proposition 5.2 (uniform compression). In the setup of Section 5.1,
+there is a finite list A of real functions on X, of cardinality Q, such
+that every f in F_+ has A_f in A satisfying
- ||f - A_f||_{infty,X} <= 3 theta.
+ f(x) - 3 theta <= A_f(x) <= f(x) + theta (x in X).
-The list can be chosen with
+In particular ||f - A_f||_{infty,X} <= 3 theta. The list can be chosen
+with
log Q <= h s log q + C_{h,theta,u},
-
-where
-
- C_{h,theta,u}
- = log u + h s 2^u log(1 + s 2^u / theta).
+ C_{h,theta,u} = log u + h s 2^u log(1 + s 2^u / theta).
Proof.
-For each i in [u], fix a representative map
+Fix representative maps rho_i : L_i(X) -> X with
+L_i(rho_i(sigma)) = sigma. These are chosen once and for all before any
+coefficient vector mu.
- rho_i : L_i(X) -> X,
- L_i(rho_i(sigma)) = sigma.
+Fix f = f_mu in F_+. For a subset S of Y write mu(S) = sum_{y in S} mu_y.
-These maps are fixed for the whole problem, before any coefficient
-vector mu is chosen.
-
-Step 1: a common index.
-
-Fix f = f_mu in F_+.
-For a subset S of Y, write mu(S) = sum_{y in S} mu_y.
-Average the admissible condition over i:
+(1) A common index. Averaging the admissible inequality over i,
(1/u) sum_{i=1}^u mu{(v,T) : i not in T}
- = sum_{(v,T) in Y} mu_{(v,T)} |[u]\T| / u
- <= theta.
-
-Therefore there is an index i0 in [u] such that
-
- mu{(v,T) : i0 not in T} <= theta.
-
-Retain the columns
-
- Y0 = {(v,T) in Y : i0 in T}.
-
-The omitted mass is at most theta.
-This one index i0 will serve at every distance level j.
-
-Step 2: a bounded number of pivots at each level.
+ = sum_{(v,T) in Y} mu_{(v,T)} |[u] \ T| / u
+ <= theta.
-Fix j in {0,...,h-1}.
-For x in X let
+So some i_0 in [u] satisfies
- I_x = {(v,T) in Y0 : d_T(x,v) <= j}.
+ mu{(v,T) : i_0 not in T} <= theta.
-Start 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 satisfy
-k_j theta < 1, so
+Keep columns in Y_0 = {(v,T) in Y : i_0 in T}; the discarded mass is
+at most theta. This single i_0 will be used at every level.
- k_j <= s = ceil(1/theta).
+(2) Bounded pivots at each level. Fix j in {0, ..., h-1}. For x in X
+set
-The process terminates with pivots z_{j,1},...,z_{j,k_j} and union
+ I_x = {(v,T) in Y_0 : d_T(x, v) <= j}.
- U_j = union_{k=1}^{k_j} I_{z_{j,k}}
+Starting from the empty union, repeatedly add some I_z whose mass
+outside the current union exceeds theta. If k_j sets are added, their
+successive contributions are each > theta, all disjoint from the
+previous union. Hence k_j theta < 1 and k_j <= s. The process stops at
+pivots z_{j,1}, ..., z_{j,k_j} with union
-such that
+ U_j = union_{k=1}^{k_j} I_{z_{j,k}},
- mu(I_x \ U_j) <= theta for every x in X.
+satisfying mu(I_x \ U_j) <= theta for every x in X. (The empty case
+k_j = 0 is allowed.) Assign each column of U_j to the first pivot whose
+set contains it, and let kappa_j(y) in {1, ..., k_j} be its slot.
-The empty choice is allowed.
-Assign every column of U_j to the first pivot whose set contains it.
-Let kappa_j(y) be its assigned slot.
+(3) Label representatives. For a pivot z = z_{j,k}, keep the label
+L_{i_0}(z) and put z' = rho_{i_0}(L_{i_0}(z)). If y = (v,T) is
+assigned to this pivot then i_0 in T, d_T(v, z) <= j, and
+d_T(z, z') <= 1, hence
-Step 3: replace each pivot by a label representative.
+ d_T(v, z') <= j + 1.
-For a pivot z = z_{j,k}, keep only its label L_{i0}(z), and replace it by
+The triangle inequality at every x in X gives
- z' = rho_{i0}(L_{i0}(z)).
-
-If y = (v,T) is assigned to this pivot, then i0 is in T,
-
- d_T(v,z) <= j,
- d_T(z,z') <= 1.
-
-Thus
-
- d_T(v,z') <= j+1.
-
-For every x in X, the triangle inequality gives
-
- d_T(x,v) <= j
- => d_T(x,z') <= 2j+1,
-
- d_T(x,z') <= 2j+1
- => d_T(x,v) <= 3j+2.
-
-All distances used here are finite under the stated hypotheses.
+ d_T(x, v) <= j ==> d_T(x, z') <= 2j + 1,
+ d_T(x, z') <= 2j + 1 ==> d_T(x, v) <= 3j + 2.
Define
- A_j(x)
- = sum_{y=(v,T) in U_j} mu_y
- 1_{d_T(x,z'_{j,kappa_j(y)}) <= 2j+1}.
+ A_j(x) = sum_{y=(v,T) in U_j} mu_y
+ 1_{d_T(x, z'_{j, kappa_j(y)}) <= 2j+1}.
-For comparison, let
+For comparison put
- f_{mu,j}(x)
- = sum_{y=(v,T) in Y} mu_y
- 1_{d_T(x,v) <= j}.
+ f_{mu,j}(x) = sum_{y=(v,T) in Y} mu_y 1_{d_T(x, v) <= j}.
-Every assigned column counted by f_{mu,j}(x) is counted by A_j(x),
-by the forward implication.
-The other columns counted by f_{mu,j}(x) have total mass at most
-2 theta:
-at most theta lies outside Y0, and at most theta lies in I_x \ U_j.
-Conversely, the backward implication bounds every column counted by A_j.
-Hence
+By the first implication, A_j counts every column that f_{mu,j} counts
+and lies in U_j. The remaining columns of f_{mu,j} (either outside Y_0,
+or in I_x \ U_j) have total mass at most 2 theta. By the second
+implication, A_j only counts columns with d_T(x, v) <= 3j+2. Therefore
f_{mu,j}(x) - 2 theta
- <= A_j(x)
- <= sum_{y=(v,T) in Y} mu_y
- 1_{d_T(x,v) <= 3j+2}.
-
-Step 4: combine the levels.
-
-Let
-
- F = sum_{j=0}^{h-1} gamma_j A_j.
+ <= A_j(x)
+ <= sum_{y=(v,T) in Y} mu_y 1_{d_T(x, v) <= 3j + 2}.
-By Lemma 5.1,
-
- f_mu = sum_{j=0}^{h-1} gamma_j f_{mu,j}.
-
-The lower bound gives
+(4) Combine levels. Let F = sum_{j=0}^{h-1} gamma_j A_j. By Lemma 5.1,
+f_mu = sum_j gamma_j f_{mu,j}. The lower bound above gives
F >= f_mu - 2 theta.
-For the upper bound, apply the dilation inequality of Lemma 5.1 to
-each distance d_T(x,v), and sum with weights mu_{(v,T)}.
-Since the total mass is at most 1 and
+For the upper bound, apply part (b) of Lemma 5.1 to each distance
+d_T(x, v), multiply by mu_{(v,T)}, and sum over y. Since the total mass
+of mu is at most 1 and log 3 / log(h+1) <= theta,
- log 3 / log(h+1) <= theta,
+ F <= f_mu + theta.
-we get
+Hence
f_mu - 2 theta <= F <= f_mu + theta.
-Step 5: a finite encoding.
-
-The center v of an assigned column no longer occurs in its indicator
-in A_j.
-Group columns by assigned slot and by T:
+(5) A finite encoding. The column center v disappears from A_j's
+indicators. Group U_j by (kappa, T):
- A_j(x)
- = sum_{k=1}^s sum_{T in T} w_{j,k,T}
- 1_{d_T(x,z'_{j,k}) <= 2j+1},
+ A_j(x) = sum_{k=1}^s sum_{T in T} w_{j,k,T}
+ 1_{d_T(x, z'_{j,k}) <= 2j+1},
-where
+ w_{j,k,T} = sum_{v : (v,T) in U_j, kappa_j(v,T) = k} mu_{(v,T)}.
- w_{j,k,T}
- = sum_{v : (v,T) in U_j, kappa_j(v,T)=k} mu_{(v,T)}.
+Empty slots have zero weight and are padded with a fixed realized
+L_{i_0}-label. (Such a label exists because X is nonempty.) Each
+weight lies in [0,1], and there are at most M_0 = s 2^u weights at each
+level.
-Unused slots have all weights zero and are padded with a fixed realized
-L_{i0}-label.
-Each weight is in [0,1], and there are at most
+Round each weight down to a multiple of delta = theta / M_0:
- M0 = s 2^u
+ tilde w_{j,k,T} = delta floor(w_{j,k,T} / delta).
-weights at each level.
-Round each weight down to a multiple of
+Let tilde A_j be A_j with these rounded weights and put
+A = sum_j gamma_j tilde A_j. For each x in X,
- delta = theta / M0:
+ 0 <= A_j(x) - tilde A_j(x) <= M_0 delta = theta,
- tilde w_{j,k,T}
- = delta floor(w_{j,k,T} / delta).
-
-Let tilde A_j be A_j with these rounded weights, and put
-
- A = sum_{j=0}^{h-1} gamma_j tilde A_j.
-
-Since every indicator is at most one,
-
- 0 <= A_j(x) - tilde A_j(x) <= M0 delta = theta.
-
-The weights gamma_j sum to one, so
+and since sum_j gamma_j = 1,
0 <= F - A <= theta.
-Together with the previous inequalities, this gives
+Combined with (4),
f_mu - 3 theta <= A <= f_mu + theta.
-Step 6: count one list that works for all mu.
+(6) Counting one list. For fixed i_0 the following data determine A:
+the s pivot labels at each of the h levels, and the rounded weights.
+The label L_{i_0}(z_{j,k}) determines z'_{j,k} via rho_{i_0}; no
+original pivot or column center must be stored. There are at most
+q^{h s} choices of labels, and each rounded weight has at most
-For fixed i0, the data determining A are the s pivot labels at each of
-the h levels and the rounded weights.
-The label determines z' through the fixed map rho_{i0}, so no original
-pivot or column center must be specified.
-There are at most q^{h s} choices of labels.
-Each rounded weight has at most
+ floor(M_0 / theta) + 1 <= 1 + M_0 / theta
- floor(M0/theta) + 1 <= 1 + M0/theta
+possible values; there are h M_0 such weights.
-possible values, and there are at most h M0 such weights.
-Enumerate these choices for every i0 in [u], allowing also codes that
-do not arise from a coefficient vector.
-This gives a fixed finite list containing every approximant constructed
-above, with
+Enumerate all such choices for every i_0 in [u], allowing also codes
+that do not come from any coefficient vector. This gives a fixed finite
+list containing every approximant constructed above, of size
- Q <= u q^{h s}
- (1 + s 2^u / theta)^{h s 2^u}.
+ Q <= u q^{h s} (1 + s 2^u / theta)^{h s 2^u}.
-Taking logarithms proves the bound on log Q.
-The graphs and representative maps are shared data defining the list;
-they are not additional choices for each approximant.
-This proves the proposition.
+Taking logarithms proves the bound on log Q. The graphs and the maps
+rho_i are shared data; they are not extra choices per approximant. Done.
+5.4 Signed compression.
-5.3 Signed compression
-
-Corollary 5.3 (signed compression).
-With the notation of Proposition 5.2, put
+Corollary 5.3 (signed compression). With the notation of Proposition
+5.2, put
f_lambda = sum_{y in Y} lambda_y g_y,
- B_1^Y = { lambda in R^Y : sum_{y in Y} |lambda_y| <= 1 },
- F = { f_lambda : lambda in B_1^Y }
- = absconv{g_y : y in Y}.
-
-Then there is a list of at most Q^2 functions which approximates every
-member of F to uniform error 6 theta.
+ F = { f_lambda : lambda in B_1^Y }
+ = absconv{ g_y : y in Y }.
-Moreover, B_1^Y can be partitioned into at most Q^2 nonempty clusters
-such that
+Then a list of at most Q^2 functions approximates every f_lambda in F
+to uniform error 6 theta. Moreover B_1^Y can be partitioned into at
+most Q^2 nonempty clusters so that
||f_lambda - f_lambda'||_{infty,X} <= 12 theta
-whenever lambda and lambda' belong to the same cluster.
-
-Proof.
+whenever lambda, lambda' lie in the same cluster.
-Write
-
- lambda = lambda^+ - lambda^-,
-
-where
-
- lambda_y^+ = max{lambda_y, 0},
- lambda_y^- = max{-lambda_y, 0}.
-
-Each part is nonnegative and has total mass at most one.
-Apply Proposition 5.2 to choose A^+, A^- in A with
+Proof. Write lambda = lambda^+ - lambda^- with lambda_y^+ =
+max{lambda_y, 0} and lambda_y^- = max{-lambda_y, 0}. Each part is
+nonnegative and has total mass at most 1. By Proposition 5.2 there are
+A^+, A^- in A with
||f_{lambda^+} - A^+||_{infty,X} <= 3 theta,
||f_{lambda^-} - A^-||_{infty,X} <= 3 theta.
-Then A^+ - A^- approximates f_lambda to error at most 6 theta.
-There are at most Q^2 differences in A - 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.
-The triangle inequality gives
-
- ||f_lambda - f_lambda'||_{infty,X}
- <= ||f_lambda - A||_{infty,X}
- + ||A - f_lambda'||_{infty,X}
- <= 6 theta + 6 theta
- = 12 theta.
-
-The approximating functions need not belong to F.
-The clusters themselves consist of actual coefficient vectors in B_1^Y.
-This proves the corollary.
-
-
-6. STEP 3: FINITE-FIELD PARTITIONS AND SEPARATED ROWS
-
-We now build the partitions that feed into Section 5.
-We want many rows but few labels per partition.
-The rows will be symmetric multilinear forms over a finite field.
-The partitions will be contractions by chosen directions.
-
-There are two ingredients:
-
- 6.1 a polynomial zero bound over F_p;
- 6.2 a dimension count for symmetric forms;
- 6.3 a choice of directions that makes every nonzero form nonzero on
- many tuples;
- 6.4 the resulting graph separation of rows.
-
-6.1 The polynomial zero bound
-
-Lemma 6.1 (Schwartz-Zippel).
-Let P in F_p[z_1,...,z_k] be a nonzero polynomial of total degree at
-most d, where k and d are nonnegative integers and p is prime.
-If U_1,...,U_k are independent and uniform in F_p, then
-
- Pr(P(U_1,...,U_k) = 0) <= d/p.
-
-Proof.
-
-Induct on k.
-When k = 0, P is a nonzero constant, so its zero probability is 0.
-For k >= 1, write
-
- P(z_1,...,z_k)
- = sum_{j=0}^e P_j(z_1,...,z_{k-1}) z_k^j,
-
-with P_e not the zero polynomial.
-The total degree of P_e is at most d-e.
-By the induction hypothesis,
-
- Pr(P_e(U_1,...,U_{k-1}) = 0) <= (d-e)/p.
-
-Condition on any values of the first k-1 variables for which P_e does
-not vanish.
-The resulting univariate polynomial in z_k has degree e, so it has at
-most e roots.
-Its conditional zero probability is therefore at most e/p.
-
-The sum of these two bounds is
-
- (d-e)/p + e/p = d/p.
+So A^+ - A^- approximates f_lambda to error at most 6 theta, and there
+are at most Q^2 differences in A - A. Order this list and assign each
+lambda in B_1^Y to its first approximant with error <= 6 theta; the
+nonempty fibers form the partition. The triangle inequality gives the
+12 theta diameter bound. Done.
-This also covers e = 0 and all nonzero constant polynomials.
-This proves the lemma.
-6.2 Symmetric forms and their dimension
+6. FINITE-FIELD PARTITIONS AND SEPARATED ROWS
-For positive integers r and h, set
+We now build partitions L_i with few labels and with the extra feature
+that graph distances in a suitable admissible T separate every pair of
+rows.
- D_j = binom(r+j-1, j) for j >= 0.
+6.1 A zero bound.
-Let E = F_p^r.
-Write Sym^j(E^*) for the space of maps E^j -> F_p that are multilinear
-and invariant under permutations of their arguments.
-We also use Sym^0(E^*) = F_p.
+Lemma 6.1 (Schwartz-Zippel). Let P in F_p[z_1, ..., z_k] be a nonzero
+polynomial of total degree <= d; p prime; k, d >= 0. If U_1, ..., U_k
+are independent uniform in F_p, then
-Relative to a basis e_1,...,e_r of E, a symmetric j-linear form is
-specified freely by its values on multisets of j basis vectors.
-Such a multiset is described by counts
+ Pr(P(U_1, ..., U_k) = 0) <= d / p.
- alpha_1,...,alpha_r >= 0,
- alpha_1 + ... + alpha_r = j.
+Proof. Induction on k.
-The number of solutions is
+k = 0: P is a nonzero constant, probability 0.
- binom(r+j-1, j) = D_j.
+k >= 1: write P = sum_{j=0}^e P_j(z_1, ..., z_{k-1}) z_k^j with P_e
+nonzero. The total degree of P_e is at most d - e; induction bounds the
+probability that P_e vanishes by (d-e)/p. Conditioned on values of
+z_1, ..., z_{k-1} making P_e nonzero, the resulting polynomial in z_k
+has degree e and at most e roots (successive division by linear
+factors); the conditional zero probability is at most e/p. Sum: d/p.
+Done.
-Therefore
+6.2 Symmetric forms and their dimension.
- dim_{F_p} Sym^j(E^*) = D_j,
- |Sym^j(E^*)| = p^{D_j}.
+Fix r, h >= 1. Set D_j = binom(r+j-1, j) for j >= 0; this is the
+number of multisets of size j drawn from an r-element set.
-In particular, the row space
+Let E = F_p^r. Write Sym^j(E^*) for the space of maps E^j -> F_p that
+are multilinear and invariant under permuting arguments. Set also
+Sym^0(E^*) = F_p.
- X = Sym^h(E^*)
+Any symmetric j-linear form is determined by its values on multisets of
+j basis vectors, and this determination is a bijection. So
-has size
+ dim Sym^j(E^*) = D_j, |Sym^j(E^*)| = p^{D_j}.
- |X| = p^{D_h}.
+In particular X = Sym^h(E^*) has |X| = p^{D_h}, and every contraction
-Each contraction by a direction t in E,
+ L_i(x) = x(t_i, ., ..., .) (t_i in E fixed)
- x |-> x(t, ., ..., .),
+is a symmetric (h-1)-linear form whose values lie in a space of size
+p^{D_{h-1}}. So L_i has at most q = p^{D_{h-1}} labels.
-is a symmetric (h-1)-linear form.
-So its values lie in a space of size at most
-
- p^{D_{h-1}}.
-
-This is the small label set q in the compression proposition.
-
-
-6.3 Directions with nonvanishing evaluations
-
-Proposition 6.3 (robust directions).
-Let 0 < theta < 1 and let r,h be positive integers.
-Put
+Also
- w = 2 D_h,
- u = ceil(h w / theta),
+ D_{h-1} / D_h = h / (r + h - 1).
-and let p be any prime satisfying
+So with r >> h, q is exponentially smaller than |X| in the log scale we
+care about.
- p > max{h, h^2 u^{2h}}.
+6.3 Directions with nonvanishing evaluations.
-There exist directions t_1,...,t_u in E = F_p^r such that, for every
-nonzero Z in Sym^h(E^*), there is a set T subset [u] with
+Proposition 6.2 (robust directions). Let 0 < theta < 1 and r, h >= 1.
+Put w = 2 D_h and u = ceil(h w / theta). Let p be a prime with
- |[u] \ T| <= theta u
+ p > max{ h, h^2 u^{2h} }.
-for which
+There exist t_1, ..., t_u in E = F_p^r with the following property: for
+every nonzero Z in Sym^h(E^*) there is a set T subset [u] with
+|[u] \ T| <= theta u and
- Z(t_{i_1},...,t_{i_h}) != 0
+ Z(t_{i_1}, ..., t_{i_h}) != 0 for all (i_1, ..., i_h) in T^h.
-for all (i_1,...,i_h) in T^h.
-Tuples in this assertion may have repeated indices.
+Repeated indices are allowed.
Proof.
-Choose t_1,...,t_u independently and uniformly in E.
-Fix a nonzero form Z.
-
-For z = sum_{a=1}^r z_a e_a, define the diagonal polynomial
-
- P_Z(z_1,...,z_r) = Z(z,...,z).
-
-Using multinomial expansion,
+Choose t_1, ..., t_u independently and uniformly in E. Fix a nonzero Z.
- P_Z(z_1,...,z_r)
- = sum_{alpha_1+...+alpha_r=h, alpha_a>=0}
- (h! / (alpha_1! ... alpha_r!))
- Z(e_1^{[alpha_1]},...,e_r^{[alpha_r]})
- z_1^{alpha_1} ... z_r^{alpha_r}.
+Diagonal polynomial. Write z = sum_a z_a e_a. Then
-Here e_a^{[alpha_a]} means that e_a is repeated alpha_a times among
-the arguments.
+ P_Z(z_1, ..., z_r) = Z(z, ..., z)
+ = sum_{alpha_1 + ... + alpha_r = h}
+ (h! / prod_j alpha_j!)
+ Z(e_1^{[alpha_1]}, ..., e_r^{[alpha_r]})
+ z_1^{alpha_1} ... z_r^{alpha_r},
-At least one displayed value of Z is nonzero.
-Since p > h, every multinomial coefficient is nonzero in F_p.
-Distinct multisets give distinct monomials, so P_Z is a nonzero
-polynomial of total degree h.
+where e_a^{[alpha_a]} means e_a repeated alpha_a times among the
+arguments. At least one displayed value of Z is nonzero. Since p > h,
+every multinomial coefficient is nonzero in F_p, and distinct multisets
+give distinct monomials. So P_Z is a nonzero polynomial of total degree
+h.
-For an ordered tuple i = (i_1,...,i_h) in [u]^h, let
+Every tuple zero probability. For an ordered tuple
+i = (i_1, ..., i_h) in [u]^h, let S(i) = {i_1, ..., i_h}. The
+expression Z(t_{i_1}, ..., t_{i_h}) is a polynomial of total degree h in
+the scalars of the vectors with indices in S(i); it is nonzero because
+setting all those vector variables equal to z recovers P_Z. Lemma 6.1
+gives
- supp(i) = {i_1,...,i_h}.
+ Pr(Z(t_{i_1}, ..., t_{i_h}) = 0) <= h / p,
-The expression
+and this applies to any pattern of repeated indices.
- Z(t_{i_1},...,t_{i_h})
+Independence. For this Z, evaluations on tuples with pairwise disjoint
+supports depend on disjoint sets of independent vectors t_i, hence are
+independent.
-considered as a polynomial in the scalar coordinates of the vectors
-with indices in supp(i) has total degree h and is nonzero.
-Indeed, setting all those vector variables equal to z gives the nonzero
-polynomial P_Z.
-
-Lemma 6.1 therefore gives
-
- Pr(Z(t_{i_1},...,t_{i_h}) = 0) <= h/p.
-
-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^{h w} ordered lists of w ordered h-tuples.
-There are 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
+Union bound. There are at most u^{h w} ordered lists of w ordered
+h-tuples, and fewer than p^{D_h} nonzero forms Z. The probability that
+some Z admits w zero tuples with pairwise disjoint supports is at most
p^{D_h} u^{h w} (h/p)^w
- = (h^2 u^{2h} / p)^{D_h}
- < 1.
-
-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 of deleted indices is at most
+ = (h^2 u^{2h} / p)^{D_h} < 1.
- h(w-1) < h w <= theta u.
+So with positive probability no such pair (Z, list) exists. Fix a
+choice of vectors for which it does not.
-If any zero tuple were supported in T, its support would be disjoint
-from all the selected supports, contradicting maximality.
-Thus
+Maximal disjoint family. For every 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
- Z(t_{i_1},...,t_{i_h}) != 0
+ h(w - 1) < h w <= theta u.
-for every tuple from T.
-Since theta < 1, the set T is nonempty.
-The construction imposed no requirement that the sampled vectors be
-distinct or nonzero.
-This proves the proposition.
+If a zero tuple were supported in T, its support would be disjoint from
+all the selected supports, contradicting maximality. Hence
+Z(t_{i_1}, ..., t_{i_h}) != 0 for every tuple from T. Since theta < 1,
+T is nonempty. Done.
+6.4 Separated rows.
-6.4 Partitions with separated rows
-
-Proposition 6.4 (separated rows).
-With the parameters and directions of Proposition 6.3, let
-
- X = Sym^h(E^*),
- L_i(x) = x(t_i, ., ..., .),
- T = { T subset [u] : |[u] \ T| <= 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 5.1, every pair of distinct
-x,y in X has some T in T satisfying
-
- d_T(x,y) > h.
-
-Consequently, for
-
- Y = X times T,
- R_x = (g_{(v,T)}(x))_{(v,T) in Y} in R^Y,
-
-the rows satisfy
-
- ||R_x - R_y||_{infty,Y} = 1 for x != y.
-
-Proof.
-
-The cardinality of X follows from Section 6.2.
-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.
+Proposition 6.3 (separated rows). With the parameters and directions
+of Proposition 6.2, define
-Fix distinct x,y in X, and apply Proposition 6.3 to
+ X = Sym^h(E^*),
+ L_i(x) = x(t_i, ., ..., .),
+ T = { T subset [u] : |[u] \ T| <= theta u }.
- Z = y - x.
+Then |X| = m = 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 T with
-Let T in T be the resulting nonempty set.
+ d_T(x, y) > h.
-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
+Consequently, for Y = X x T and the row vectors
+R_x = (g_{(v,T)}(x))_{(v,T) in Y} in R^Y,
- x = x_0, x_1, ..., x_k = y,
- 1 <= k <= h.
+ ||R_x - R_y||_{infty,Y} = 1 whenever x != y.
-For each edge choose i_j in T such that
+Proof. |X| and q are as in Section 6.2.
- L_{i_j}(x_j) = L_{i_j}(x_{j-1}),
+Fix distinct x, y in X and apply Proposition 6.2 to Z = y - x. Let T
+in T be the resulting set, so Z(t_{i_1}, ..., t_{i_h}) != 0 for every
+tuple from T.
-and put
-
- Delta_j = x_j - x_{j-1}.
-
-Thus
+Suppose a path x = x_0, x_1, ..., x_k = y with 1 <= k <= h. For each
+edge choose i_j in T with L_{i_j}(x_j) = L_{i_j}(x_{j-1}), and put
+Delta_j = x_j - x_{j-1}. Then
Delta_j(t_{i_j}, v_2, ..., v_h) = 0
-for every v_2,...,v_h in E.
-
-Choose any i_* in T, and form the h-tuple consisting of
-
- t_{i_1}, ..., 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 Proposition 6.3.
-This proves
-
- d_T(x,y) > h.
-
-Vertices in different components have infinite distance and already
-satisfy the inequality.
+for all v_2, ..., v_h in E.
-At the column (x,T), the logarithmic profile gives
+Choose any i_* in T. Form the h-tuple
- g_{(x,T)}(x) = 1,
- g_{(x,T)}(y) = 0,
+ (t_{i_1}, ..., t_{i_k}, t_{i_*}, ..., t_{i_*}) (h-k copies of t_{i_*}).
-because d_T(x,y) > h.
-All column values lie in [0,1], so this unit difference also gives the
-exact equality
+Every Delta_j vanishes on this tuple: Delta_j is symmetric and one of
+its arguments is t_{i_j}. So Z = sum_j Delta_j also vanishes there,
+contradicting Proposition 6.2. Hence no such path exists and
+d_T(x, y) > h. (If x, y are in different components, d_T = infinity and
+the same bound holds.)
- ||R_x - R_y||_{infty,Y} = 1.
+Column separation. At the column (x, T): g_{(x,T)}(x) = phi_h(0) = 1
+and g_{(x,T)}(y) = phi_h(d_T(x, y)) = 0 because d_T(x, y) > h. All
+column values lie in [0,1], so ||R_x - R_y||_{infty,Y} = 1. Done.
-This proves the proposition.
-
-The family 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 5.2, whose common index may depend
-on the particular convex combination of columns.
-
-If h also satisfies
-
- log 3 / log(h+1) <= theta,
-
-then the compression bound applies with
-
- q = p^{D_{h-1}},
- s = ceil(1/theta),
+Remark. The family T contains every admissible subset and is fixed
+with the partitions. The separating T above may depend on (x, y); the
+common index i_0 in Proposition 5.2 may depend on the coefficient
+vector. Both behaviors are allowed.
+If h also satisfies log 3 / log(h+1) <= theta, the compression bound of
+Proposition 5.2 applies with q = p^{D_{h-1}} and s = ceil(1/theta),
giving
log Q <= h s D_{h-1} log p + C_{h,theta,u}.
-Once r, h, and theta are fixed, so are u and C_{h,theta,u}.
-The prime p can still be taken arbitrarily large subject to the prime
-threshold in Proposition 6.3.
+Once r, h, theta are fixed, so are u and C_{h,theta,u}. The prime p
+may still be taken arbitrarily large, subject only to the threshold in
+Proposition 6.2.
-7. STEP 4: CHOOSING THE PARAMETERS
+7. PROOF OF THEOREM 1
-We now assemble the three tools.
-Fix a,b >= 1.
+Fix a, b >= 1.
-7.1 The choices
+7.1 Choices.
Set
- theta = 1/(1000a),
- s = ceil(1/theta).
-
-Choose a positive integer h with
-
- log 3 / log(h+1) <= theta.
-
-Such an integer exists because log(h+1) tends to infinity.
+ theta = 1 / (1000 a), s = ceil(1/theta).
-Choose a positive integer r so that
+Choose a positive integer h with log 3 / log(h+1) <= theta (possible
+since log(h+1) -> infinity). Choose a positive integer r with
r + h - 1 > 8 b h^2 s.
-Define
-
- D_j = binom(r+j-1, j) for 0 <= j <= h,
- w = 2 D_h,
- u = ceil(h w / theta).
-
-The number
-
- C = C_{h,theta,u}
- = log u + h s 2^u log(1 + s 2^u / theta)
-
-is now fixed.
-
-Choose a prime p satisfying
-
- p > max{ h, h^2 u^{2h}, exp(8bC/D_h) }.
-
-All quantities on the right have already been determined.
-Primes exceed every finite bound, so such a p exists.
+Define, for 0 <= j <= h,
-Apply Proposition 6.3 with these parameters.
-Form the label maps and graph profiles in Proposition 6.4.
-The row index set is
+ D_j = binom(r+j-1, j), w = 2 D_h, u = ceil(h w / theta),
- X = Sym^h(F_p^r),
+and set C = C_{h,theta,u} = log u + h s 2^u log(1 + s 2^u / theta).
-so
+Finally choose a prime p satisfying
- m = |X| = p^{D_h} > 1.
+ p > max{ h, h^2 u^{2h}, exp(8 b C / D_h) }.
-Each label map takes at most
+Every quantity on the right is already fixed, so such a p exists.
- q = p^{D_{h-1}}
+7.2 Apply the tools.
-values.
-The columns are indexed by
+Use Proposition 6.2 with these parameters, then Proposition 6.3. That
+gives the row space X = Sym^h(F_p^r) with
- Y = X times T,
- T = { T subset [u] : |[u] \ T| <= theta u }.
+ m = |X| = p^{D_h} > 1,
-The real row vectors satisfy
+label sets of size at most q = p^{D_{h-1}}, columns indexed by
+Y = X x T with T = { T subset [u] : |[u] \ T| <= theta u }, and row
+vectors satisfying
||R_x - R_x'||_{infty,Y} = 1 for x != x'.
-In particular, Y is a finite nonempty set.
-The finite field is used only to construct the indices and label maps.
-The matrix entries and the convex bodies below are real.
-
-7.2 Applying compression and the matrix lemma
+Y is finite and nonempty. The finite field is used only to build the
+index and label sets; the matrix entries and the bodies below are real.
-By Proposition 5.2, the positive column class has a uniform 3 theta
-approximation list of cardinality Q with
+By Proposition 5.2 the nonnegative column class has a 3 theta list of
+size Q with
log Q <= h s log q + C
= h s D_{h-1} log p + C.
-Corollary 5.3 gives a uniform 6 theta approximation list of at most Q^2
-functions for the absolutely convex column hull.
-
-Thus the matrix-to-body lemma applies with
-
- eps = 6 theta,
- t = theta.
+By Corollary 5.3 the absolutely convex column hull has a 6 theta
+approximation list of size at most Q^2.
-It gives admissible bodies in dimension n = |Y|,
+Apply Lemma 4.1 with eps = 6 theta and t = theta. It gives 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_infty^Y, L = B_infty^Y,
-such that
+with
- N(K,L) >= m,
+ N(K, L) >= m,
N(L^o, 38 theta K^o) <= Q^2.
-The number 38 comes from
-
- 6 eps + 2t = 6(6 theta) + 2 theta = 38 theta.
-
-Since
-
- 38 theta = 38/(1000a) < a^-1,
+The constant 38 is 6 eps + 2 t = 6(6 theta) + 2 theta. Since
-increasing the covering body preserves the cover, and therefore
+ 38 theta = 38 / (1000 a) < a^{-1},
- N(L^o, a^-1 K^o) <= Q^2.
+replacing the covering body by a smaller one only makes the cover
+strictly easier:
-7.3 Comparing the two entropies
+ N(L^o, a^{-1} K^o) <= Q^2.
-Use the exact identity
+7.3 Compare the entropies.
- D_{h-1} / D_h = h / (r+h-1).
-
-This follows directly from the binomial formula.
-
-Then
+The identity D_{h-1} / D_h = h / (r + h - 1) gives
log(Q^2) / log m
- <= (2 h s D_{h-1} log p + 2C) / (D_h log p)
- = 2 h s (D_{h-1}/D_h) + 2C/(D_h log p)
- = 2 h^2 s/(r+h-1) + 2C/(D_h log p)
- < 1/(4b) + 1/(4b)
- = 1/(2b).
-
-The two strict inequalities come from the choices of r and p:
-
- r+h-1 > 8 b h^2 s
- implies 2 h^2 s/(r+h-1) < 1/(4b),
+ <= (2 h s D_{h-1} log p + 2 C) / (D_h log p)
+ = 2 h s (D_{h-1}/D_h) + 2 C / (D_h log p)
+ = 2 h^2 s / (r + h - 1) + 2 C / (D_h log p)
+ < 1/(4b) + 1/(4b)
+ = 1/(2b).
- p > exp(8 b C / D_h)
- implies 2C/(D_h log p) < 1/(4b).
+The two strict inequalities follow from r + h - 1 > 8 b h^2 s and from
+p > exp(8 b C / D_h).
-Combining this with N(L^o, a^-1 K^o) <= Q^2 and N(K,L) >= m > 1 gives
+Together with N(L^o, a^{-1} K^o) <= Q^2 and N(K, L) >= m > 1,
- b log N(L^o, a^-1 K^o)
- <= b log(Q^2)
- < (1/2) log m
- < log m
- <= log N(K,L).
+ b log N(L^o, a^{-1} K^o)
+ <= b log(Q^2)
+ < (1/2) log m
+ < log m
+ <= log N(K, L).
-The strict inequality (1/2) log m < log m uses m > 1.
-Identifying R^Y with R^n makes L = [-1,1]^n.
-This proves Theorem 1.
+Identifying R^Y with R^n makes L = [-1,1]^n and proves Theorem 1.
-7.4 An asymptotic form
+7.4 An asymptotic form.
-The same estimate gives an asymptotic statement.
+The same estimates give a stronger asymptotic statement. Fix a >= 1,
+and hence theta, h, s. For each positive integer r, define D_h, u, C
+as above and choose a prime
-Fix a >= 1, and hence theta, h, and s.
-For each positive integer r, set D_h, u, C as above and choose a prime
+ p > max{ h, h^2 u^{2h}, exp(r C / D_h) }.
- p > max{ h, h^2 u^{2h}, exp(rC/D_h) }.
+The resulting bodies K_r, L_r satisfy
-The resulting bodies K_r and L_r satisfy
+ 0 <= log N(L_r^o, a^{-1} K_r^o) / log N(K_r, L_r)
+ <= 2 h^2 s / (r + h - 1) + 2 / r
+ -> 0 as r -> infinity.
- 0 <= log N(L_r^o, a^-1 K_r^o) / log N(K_r, L_r)
- <= 2 h^2 s/(r+h-1) + 2/r
- -> 0.
-
-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.
+Both u and C are fixed before p is chosen; no upper bound on the
+resulting dimension is needed.
8. A CONSEQUENCE FOR CONVEXIFIED PACKING
-Ordinary covering entropy is not the only notion of complexity.
-There is also convexified packing.
-The counterexample also separates the two notions.
+There is a stronger notion of "packing" that is also useful.
-8.1 Definition
+8.1 Definition.
For a nonempty bounded set T and an origin-symmetric convex body B,
-let Mhat(T,B) be the largest length of an ordered sequence
-
- x_1, ..., x_m in T
-
-such that
-
- (x_j + int B) intersect conv{x_i : i < j} = empty
+let Mhat(T, B) be the largest length m of an ordered sequence
+x_1, ..., x_m in T with
-for every 1 <= j <= m.
-The first convex hull is the empty set.
+ (x_j + int B) intersect conv{x_i : i < j} = empty, 1 <= j <= m.
-In words: each new point must stay outside the convex hull of all
-previous points, even after adding the interior of B.
-This is a convexified packing condition.
+(The first convex hull is the empty set.) Each new point must lie
+outside the convex hull of its predecessors, even after enlarging them
+by int B.
-8.2 The corollary
+8.2 Separation from convexified packing.
-Corollary 8.1 (separation from convexified packing).
-For every A,C >= 1, there are an integer n >= 1 and an origin-symmetric
-convex body K in R^n such that, with L = [-1,1]^n,
+Corollary 8.1. For every A, C >= 1 there are a positive integer n and
+an origin-symmetric convex body K in R^n such that, with L = [-1,1]^n,
- log N(K,L) > C log Mhat(K, L/A).
+ log N(K, L) > C log Mhat(K, L/A).
Proof.
-First, an ordered B-convexly separated sequence has at most one point
-in each translate of B/4.
+Step 1 (Mhat controls covers by quarter-bodies). Claim: an ordered
+B-convexly separated sequence has at most one point in any translate of
+B/4.
-Indeed, suppose two points x_i and x_j with i < j lie in the same
-translate of B/4.
-Then
+Suppose i < j and both x_i, x_j lie in z + B/4. Then x_j - x_i lies in
+B/4 - B/4 = B/2. Since B is origin-symmetric and convex with 0 in int B,
+every point of B/2 is a convex combination of 0 (interior) and a point
+of B, hence lies in int B. So x_j - x_i lies in int B, equivalently
+x_i lies in x_j + int B. But x_i lies in conv{x_l : l < j}, contradicting
+the separation condition. Hence
- x_j - x_i is in B/4 - B/4 = B/2.
+ Mhat(T, B) <= N(T, B/4).
-Because B is origin-symmetric and has nonempty interior, 0 lies in int B.
-Convexity then gives that B/2 is contained in int B.
-Thus x_i lies in x_j + int B.
-But x_i is in conv{x_l : l < j}, so
-
- (x_j + int B) intersect conv{x_l : l < j}
-
-is nonempty, contradicting the separation condition.
-
-Consequently,
-
- Mhat(T,B) <= N(T,B/4).
-
-There is no boundary ambiguity here because we cover by closed translates.
-
-The universal convexified duality bound of
-Artstein-Milman-Szarek-Tomczak-Jaegermann 2004, Theorem 2,
-applied to K and L/A, gives
+Step 2 (convexified duality). Apply Theorem 2 of Artstein-Milman-
+Szarek-Tomczak-Jaegermann (2004) to the bodies K and L/A:
Mhat(K, L/A)
- <= Mhat((L/A)^o, K^o/2)^2
- = Mhat(A L^o, K^o/2)^2
- = Mhat(L^o, K^o/(2A))^2
- <= N(L^o, K^o/(8A))^2.
-
-The equality uses simultaneous dilation of both arguments:
-
- Mhat(cT, cB) = Mhat(T,B) for c > 0.
+ <= Mhat((L/A)^o, K^o/2)^2
+ = Mhat(A L^o, K^o/2)^2
+ = Mhat(L^o, K^o/(2A))^2
+ <= N(L^o, K^o/(8A))^2.
-Now choose K and L by Theorem 1 with
+The middle equality uses Mhat(c T, c B) = Mhat(T, B) for c > 0. The
+last inequality applies Step 1 with T = L^o and B = K^o/(2A).
- a = 8A,
- b = 2C.
+Step 3 (apply Theorem 1). Choose K, L from Theorem 1 with a = 8A and
+b = 2C. Then
-Theorem 1 gives
+ log N(K, L) > 2 C log N(L^o, K^o/(8A)).
- log N(K,L) > 2C log N(L^o, K^o/(8A)).
+Combining with Step 2,
-Taking logarithms in the displayed bound gives
+ log Mhat(K, L/A) <= 2 log N(L^o, K^o/(8A)),
- log Mhat(K, L/A)
- <= 2 log N(L^o, K^o/(8A)).
-
-Therefore
+so
C log Mhat(K, L/A)
- <= 2C log N(L^o, K^o/(8A))
- < log N(K,L).
-
-This proves the corollary.
-
-
-9. WHAT TO REMEMBER
-
-The whole proof fits into one sentence:
-
- separated rows make covering numbers large,
- a small list for columns makes the polar covering number small,
- and finite fields give both at once.
-
-The details:
+ <= 2 C log N(L^o, K^o/(8A))
+ < log N(K, L).
-1. Covering number N(A,B) is the least number of translates of B that
- cover A.
+Done.
-2. The polar body K^o records linear measurements bounded by 1 on K.
- The duality conjecture asks whether N(K,L) and N(L^o, K^o) are
- comparable up to universal constants.
-3. Theorem 1 says no.
- For every a,b >= 1, there is an origin-symmetric convex body K in
- some R^n such that, with L = [-1,1]^n,
+9. THE WHOLE PROOF AT A GLANCE
- log N(K,L) > b log N(L^o, a^-1 K^o).
+One sentence: separated rows make covering numbers large; a short column
+list makes the polar covering number small; finite fields give both at
+once.
-4. The matrix-to-body lemma turns a matrix into K and L.
- Many 1-separated rows force N(K,L) to be large.
- A small eps-net for the absolutely convex hull of the columns forces
- N(L^o, (6 eps + 2t) K^o) to be small.
+The steps:
-5. Compression builds the small eps-net.
- With u partitions of X, each having at most q labels, the positive
- column class has a 3 theta approximation list of size Q with
+ 1. N(A, B) is the least number of translates of B that cover A. The
+ polar K^o is the body of linear functionals bounded by 1 on K.
- log Q <= h s log q + C_{h,theta,u}.
+ 2. The duality conjecture asks whether N(K, L) and N(L^o, K^o) are
+ comparable up to universal constants. Theorem 1 says no: for every
+ a, b >= 1 there are K, L in some R^n with L a cube and
+ log N(K, L) > b log N(L^o, a^{-1} K^o).
- The signed version has a 6 theta list of size Q^2.
+ 3. Lemma 4.1: many 1-separated rows force N(K, L) large; a small
+ eps-list for the column hull forces N(L^o, (6 eps + 2 t) K^o)
+ small.
-6. Finite fields give many rows and few labels.
- Take X = Sym^h(F_p^r).
- Then
+ 4. Proposition 5.2: with u partitions of X, each having at most q
+ labels, the nonnegative column class has a 3 theta list of size Q
+ with log Q <= h s log q + C_{h,theta,u}. Corollary 5.3 covers
+ signed coefficients: a 6 theta list of size Q^2.
- |X| = p^{D_h},
- q = p^{D_{h-1}},
- D_{h-1}/D_h = h/(r+h-1).
+ 5. Section 6: with X = Sym^h(F_p^r),
+ |X| = p^{D_h}, q = p^{D_{h-1}}, D_{h-1}/D_h = h/(r+h-1).
+ Taking r large makes q small relative to |X| on the log scale, and
+ Section 6.3 separates every pair of rows.
- Taking r large makes the label count small compared with the row
- count on the logarithmic scale.
+ 6. Section 7 chooses parameters so log(Q^2)/log|X| < 1/(2b). Then
+ b log N(L^o, a^{-1} K^o) <= b log(Q^2) < log m <= log N(K, L),
+ which is Theorem 1.
-7. The parameters are chosen so that
+ 7. Section 8 reuses the same K, L to separate ordinary entropy from
+ convexified packing.
- log(Q^2) / log |X| < 1/(2b).
+9.1 Where this fits.
- Then
+The duality problem goes back to Pietsch (1972). Konig and Milman (1987)
+compared the nth roots of the two covering numbers; Bourgain, Pajor,
+Szarek, Tomczak-Jaegermann (1989) proved entropy-number comparisons
+under geometric or sequence-regularity assumptions. Artstein, Milman,
+Szarek (2004) proved dimension-free duality when one body is a
+Euclidean ball; Artstein, Milman, Szarek, Tomczak-Jaegermann (2004)
+proved universal duality for convexified packing and announced ordinary
+entropy duality for spaces with bounded K-convexity constant. Emanuel
+Milman (2007) proved a comparison with logarithmic losses in both the
+scale and the entropy factor; Hu, Peale, Reingold (2022) studied dual
+covering numbers of function classes with explicit scale-dependent
+prefactors.
- b log N(L^o, a^-1 K^o)
- <= b log(Q^2)
- < (1/2) log |X|
- < log N(K,L).
+Theorem 1 says that none of these dimension- or scale-dependent
+estimates can be upgraded to a single universal pair (a, b).
-8. The same construction separates ordinary covering entropy from
- convexified packing entropy; see Corollary 8.1.
-
-9.1 Where this fits
-
-The question goes back to Pietsch in 1972.
-Konig and Milman proved a comparison of nth roots of the two covering
-numbers in 1987.
-Bourgain, Pajor, Szarek, and Tomczak-Jaegermann proved entropy-number
-comparisons under geometric or sequence-regularity assumptions in 1989.
-
-Artstein, Milman, and Szarek proved the dimension-free conjecture when
-one body is a Euclidean ball, and hence when either body is an ellipsoid,
-in 2004.
-Artstein, Milman, Szarek, and Tomczak-Jaegermann proved universal
-duality for convexified packing in 2004.
-They also announced ordinary entropy duality for spaces with bounded
-K-convexity constant, with constants depending on that bound.
-
-Emanuel Milman obtained a comparison with logarithmic losses in both
-the scale and the entropy factor in 2007.
-Hu, Peale, and Reingold studied dual covering numbers of function
-classes in learning theory in 2022, with an explicit prefactor depending
-on the approximation scale and uniform bounds.
-
-Mendelson developed convex-hull estimates for finite sets in 2001.
-The finite-field side of this paper uses the polynomial zero bound of
-Schwartz and Zippel, together with diagonal recovery of symmetric
-multilinear forms in large characteristic.
-
-The point of Theorem 1 is that none of these dimension-dependent or
-scale-dependent estimates can be upgraded to one universal pair of
-constants for all dimensions and all bodies.
10. REFERENCES
@@ -1599,8 +976,7 @@ constants for all dimensions and all bodies.
[7] L. Hu, C. Peale, O. Reingold.
Metric entropy duality and the sample complexity of outcome
indistinguishability.
- Proceedings of Algorithmic Learning Theory 2022,
- PMLR 167, 515-552.
+ Proceedings of Algorithmic Learning Theory 2022, PMLR 167, 515-552.
[8] H. Konig, V. D. Milman.
On the covering numbers of convex bodies.
@@ -1610,17 +986,12 @@ constants for all dimensions and all bodies.
On the duality problem for entropy numbers of operators.
Lecture Notes in Mathematics 1376 (1989), 50-63.
-[10] S. Mendelson.
- On the size of convex hulls of small sets.
- Journal of Machine Learning Research 2 (2001), 1-18.
+[10] M. Ferrero, A. Micali.
+ Sur les n-applications.
+ Memoires de la Societe Mathematique de France 59 (1979), 33-53.
-[11] M. Ferrero, A. Micali.
- Sur les n-applications.
- Memoires de la Societe Mathematique de France 59 (1979), 33-53.
-
-[12] A. Drapal, P. Vojtechovsky.
- Symmetric multilinear forms and polarization of polynomials.
- Linear Algebra and its Applications 431 (2009), 998-1012.
+[11] A. Drapal, P. Vojtechovsky.
+ Symmetric multilinear forms and polarization of polynomials.
+ Linear Algebra and its Applications 431 (2009), 998-1012.
END OF DOCUMENT
-