The Setting
The duality conjecture for metric entropy asks for absolute constants such that any two symmetric convex bodies and in , in every dimension , satisfy , with the covering number of by translates of and the polar body of . This item fixes , takes to be the cube , and gives bodies for which the quotient is as small as one likes, so that no constant serves for this . The library records such a body, with its dimension, as an entropy pair.
Covering Numbers and Polars
The real space over an index set is the set of functions from to .✦ For finite , the pairing of two of its points is ✦, and the polar of a subset of is the set (1)✦ The cube is the set of points all of whose coordinates have absolute value at most .✦ The unit ball is the set of points whose norm is at most .✦ A symmetric convex body in is a compact convex subset with nonempty interior and .✦
For subsets and of , the translates of by centers cover when every has for some ✦, and is coverable by when some finite family of centers does this.✦ The covering number of by is the least number of centers, placed anywhere in , whose translates of cover , and when no finite family does: (2)✦
Matrices and Uniform Approximation
A matrix with rows indexed by a set and columns indexed by a finite set is given by its columns ; its row is the vector , and the column combination with coefficients is . Two functions are uniformly -close when for every .✦ A uniform -approximation for is a finite set such that every with is uniformly -close to some point of , which need not itself be a combination of the columns.✦
The Parameters
Fix and a rank , the number of variables of the forms considered below. The accuracy parameter , the number of pivot slots and the compression radius depend on alone: (3) The form dimension , the number of directions and the encoding cost depend on as well: (4) Here counts the multisets of size drawn from indices, the dimension of the space of forms of degree in variables over a prime field .✦
Entropy Pairs
The entropy ratio of a subset of , for finite , at a real number is, with , (5)✦ The entropy budget of a real number , a natural number and a real number is, with and as in (3), (6)✦
An entropy pair with parameters , and is a dimension with together with a symmetric convex body in such that, for the cube , itself a symmetric convex body, is coverable by , is coverable by , , and .✦
From a Matrix to an Entropy Pair
Let , and , with , , , and as in (3) and (4), and let be a prime with . Let be a matrix with rows indexed by a finite set of size and columns indexed by a finite set with , whose distinct rows satisfy . If a uniform -approximation for and a natural number satisfy (7)✦ then there is an entropy pair with parameters , and .
For natural numbers , , , and with and , and a real number with , (8)✦ if moreover , , and , then (9)✦
For real numbers , , , and with , , and , (10)✦ it applies with and .
The Claim
Theorem 1. Let and be real numbers and a natural number, and let and be the compression radius and the number of pivot slots of . Then there is an entropy pair with parameters , and ; its body , in a dimension , satisfies, with , (11)✦
In the paper, the result reads: the matrix of Proposition 4.3, put into Lemma 2.1 with and , gives and , and for , whence Theorem 1.1.
What Is Checked
The claim (11) is stated over entropy pairs, which rest on symmetric convex bodies, the cube and its polar (1), covering numbers (2) with finite covers, the entropy ratio (5) and the entropy budget (6), with the parameters , and of (3). About these constructions the library also states the passage (7) from a matrix whose distinct rows are at distance at least in the sup norm, together with a uniform approximation, to an entropy pair, the bounds (8) and (9) on , and the comparison (10).