The Setting
Let be a set carrying a family of labelings indexed by a set , each of which partitions into the classes of points with a common label. For a finite set of indices, two points of are adjacent when some labeling in the set gives them the same label; the distance to a fixed point in this graph, passed through a logarithmic cutoff, is a real function on , and these functions are the columns of a matrix. A combination of the columns with nonnegative weights of total mass at most one is a point of , the space of real functions on , lying in the convex hull of the columns and the origin.
The item is the proof of Proposition 3.2, in Section 3 of the OpenAI preprint Counterexamples to the duality conjecture for metric entropy, on uniform compression from partitions. The library states six claims about it and gives the grouping of weights and the rounding down to a finite mesh as two definitions.
Partition Graphs
The partition graph of the labelings, for a finite set of indices, is the simple graph on in which two distinct points and are adjacent when for some .✦ The partition graph distance between points is the least number of edges on a path from to in , a value in that is when and lie in different components.✦
The closed graph ball of radius about a point in the partition graph is the set (1)✦ The indicator of a set is the function on equal to on and off it.✦
Profiles, Columns and Mixtures
The cutoff profile of radius is the real function on with and, for finite , (2)✦ where is the natural logarithm. The log increment , for natural numbers and , is the real number (3)✦
For a finite family of finite subsets of , the column index set is the product , whose elements are the pairs of a point and a member .✦ The graph distance column at is the function given by (4)✦ For a matrix with columns indexed by a finite set and a vector , the combination of columns is the point of .✦
The profile mixture of points and finite sets , indexed by a finite set and weighted by real numbers , is the function on given by (5)✦
Levels and Assignments
For points , finite sets and weights indexed by a finite set , and a level , the level value at a point is the real number (6)✦
An assignment of to a set of slots is a partial map from to together with, for each slot , a center and a replacement pivot . The assigned value of the assignment at level and a point is the real number (7)✦
The Claim
Theorem 1. Let , , be labelings of a set .
(i) Common index. Let be a finite set, an integer and a real number, let be weights with , and let be sets with . Then there is an index with (8)✦
(ii) Pivot replacement. Let be finite, and , and let be points with and . Then (9)✦
For (iii) to (v), let be a finite set and, for each , let , let be finite and let ; the level values (6), the assigned values (7) and the profile mixture (5) are those of these data.
(iii) Lower level bound. Let and , and let be an assignment of to slots, with centers and representatives , such that for every slot and every with has and . Let be a real number such that the with have total weight at most and, for every point , so do the unassigned with and . Then for every (10)✦
(iv) Upper level bound. Under the hypotheses of (iii) on , and alone, for every (11)✦
(v) Combination of levels. Let , let be an integer and a real number with , let , and let and , for , be real numbers with and . Then (12)✦
(vi) Mixtures as combinations of columns. Let be finite, a finite family of finite subsets of , and . Then the profile mixture of the points and the sets , indexed by the column index set, is the combination of the graph distance columns (4): for every (13)✦
Definition 1. Let be a partial map from a finite set to a set of slots, a map to a set of tags, and . The grouped weight of a slot and a tag is the real number (14)✦ For real numbers and , the rounding of down to the mesh is the real number (15)✦
What Is Checked
The claim is stated over the partition graphs of a family of labelings of a set , their distances and closed balls , the cutoff profile and the log increments , the level values and the assigned values of an assignment with centers and representatives, the profile mixture , and the graph distance columns on with their combinations in .