Are many small sets explicitly small ?
Philosophy: In a high dimensional space, given a large subset, most points of the space are close to the subset. The point is to get dimension independant bounds. I will give evidence that positive results may exist.
1. -small sets
Vocabulary: Our ambient space will be the hypercube , . Each point in is a subset of . To avoid confusion, subsets of are called classes. We shall always use the measure which is the th power of the Bernoulli distribution on .
An up-class is a class such that , .
Definition 1 For , let
Given a class , let
is an up-class. We view points of as very far
Main conjecture: When and are large, is very small.
This does not mean that has small measure.
Definition 2 A class is -small if there exists a family of subsets of such that
and the sum of measures of is .
So smallness of is attested by a small number of witnesses.
Proposition 3 If and , then is -small.
Proof: is the set of of size . It is covered by with .
Main conjecture: When is a down class, and , is -small.
2. Connections to geometry and probability
2.1. Connection to convexity
Carathéodory: For a convex set in , every point is the barycenter So additions are needed to construct the convex hull of a balanced set . (We consider multiplication by a real number as costless, since ).
How many operations are needed to construct an approximation of the convex hull ? In terms of Gaussian measure .
Convexity conjecture: The exists such that for every banaced , there exists a convex set which is contained in the sum of copies of .
The Main conjecture is a kind of discretized version of the Convexity conjecture (down-class refelcts convexity).
2.2. Stochastic processes
Given stochastic process , , estimate .
Example 2 for in Gaussian , in a subset of .
Theorem 4 , a purely metric quantity, which is hard to evaluate.
Corollary 5 The set where the Gaussian process is large is covered by a collection of half-spaces, the sum of the measures of which is .
Corollary 6 Given a convex balanced set , is covered by a collection of half-spaces, the sum of the measures of which is .
Reformulated convexity conjecture: Replace has large Gaussian measure with its complement is covered by half spaces, the sum of the measures of which is .
I view as a discrete analogue of the complement of .
2.3. Selector processes on sets
Independantly select at random points of , producing random subsets . Given a class , estimate the quantity
Remark 1 Suppose there exists such that
Proof: Union bound.
Let us merge these two remarks.
Definition 7 Given classes, , ,
Say that dominates if each set is contained in a set .
This gives a method to estimate .
Question: Are the above two remarks the only way to estimate ? I.e., is every class a small perturbation of a class for which the union bound is sharp ?
2.4. General selector processes
Let be a random set. Given a vector , let . Estimate
as a function of the geometry of . Seems related to
Bernoulli problem: estimate , random. Specifically, show that there are no better ways to estimate it than the obvious ones (by the absolute values).
Problem: Show that the set (of ‘s) where the selector process is large (compared to its expectation) is -small.
This would follow from the Main conjecture. Indeed,
is a down class.
3. Approaches to the Main conjecture
3.1. Relaxing smallness: measures
-small sets are hard to manipulate, so I introduce easier notions.
Definition 8 Say a probability measure on is -spread if for all , .
For instance, is -spread.
Example 3 The measure which is uniform on sets of cardinality is -spread.
Definition 9 A class is weakly -small if it does not carry a -spread probability measure.
Proposition 10 -small implies weakly -small.
Question: Is the converse true, up to a multiplicative constant ?
Weak form of Main conjecture: When is a down class, and , is weakly -small.
Measures give the impression to be easier to manipulate than classes. It might be easier to find a counter example in that manner. Naively,
3.2. Relaxing :
Definition 11 If is a down class, and , let
Given view as a kind of distance of to .
Which down classes satisfy the conjecture for all -spread measures ? For this, one must control the measure of for each product measure. Product measures are indexed by vectors (). One is interested in as a function of . For instance, if , . In general, it is complicated. So we compare it with multilinear polynomials.
Definition 12 Say a set satisfies if compares, up to a factor, with a multilinear polynomial.
Hopefully, every set satisfies . This would be our boldest conjecture.
Theorem 13 If is a down class and satisfies , conjecture 3 holds for .
Property survives various operations, which makes production of a counter example a hard task.