The Setting
Take finite sets and and a real matrix with rows indexed by and columns indexed by , given by its columns . Two properties of matter: its rows, as points of , lie far apart in the sup norm, while the combinations with , as functions on , all lie uniformly close to members of a short list of functions.
The question is how to read both properties off one symmetric convex body : the first as a lower bound on the number of translates of the cube needed to cover , the second as an upper bound on the number of translates of a multiple of the polar of needed to cover the polar of the cube. These are the two covering numbers compared by the duality conjecture for metric entropy, with the cube as the second body.
Bodies, Polars and Covering Numbers
For a finite set , the space is the vector space of real functions on ✦, with the pairing ✦, the norm and the sup norm . The unit ball is the set of points with ✦, and the cube is the set of points with for every .✦
The polar of a set is the set (1)✦ and the polar of the cube is . The support function of is the function on given by .✦ A symmetric convex body in is a compact convex subset of with nonempty interior such that exactly when .✦
Translates of a set cover a set when every has for some , the centers being arbitrary points of .✦ The set is finitely coverable by when some finite family of translates of covers it✦, and the covering number of by is (2)✦ with when is not finitely coverable by .
Rows, Combinations and the Body
The row of at is the point (3)✦ and the combination of the columns of with coefficients is the function on .✦ For a real number , two functions and on are uniformly -close when for every .✦ A uniform -approximation list for is a finite set of real functions on such that every combination with is uniformly -close to some member of .✦
The absolute convex hull of the rows of is the convex hull in of the rows and their negatives: (4)✦ The matrix body of at a real parameter is the Minkowski sum (5)✦
The Claim
Theorem 1. Let and be finite sets with nonempty, and let be a real matrix with columns , , whose rows are -separated: for all distinct . Let and , and let be a uniform -approximation list for with members. Then and are symmetric convex bodies, is finitely coverable by , is finitely coverable by , and (6)✦ If is nonempty as well, then , and there is a symmetric convex body , finitely coverable by the cube (itself a symmetric convex body), with finitely coverable by and (7)✦
In the paper, the result reads: for finite nonempty sets and and functions on with rows and combinations , if for distinct and, for some , a list of functions on , not necessarily of the form , approximates every with within uniformly, then for every the bodies and are origin-symmetric compact convex bodies with nonempty interior, and , with translates centered anywhere in .
What Is Checked
The claim is stated over the rows (3) of a real matrix on finite sets, their absolute convex hull (4), the matrix body (5), the cube, the polar (1), the covering number (2) with finite coverability, and uniform -approximation lists for the combinations .
For nonempty and this holds whatever the matrix: (8)✦ For nonempty and it computes the support function of through the row support of a point , (9)✦ and describes the multiples of its polar: for every , (10)✦
The lower bound of (6) needs only the separation of the rows, and holds for every real : (11)✦ For and the upper bound needs no separation, and it uses only the list : (12)✦ Such a list also yields coefficient representatives, points of such that every has an index with (13)✦