**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 1For , letGiven 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 2A 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.

Example 1

Proposition 3If 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 2for in Gaussian , in a subset of .

Theorem 4, a purely metric quantity, which is hard to evaluate.

Corollary 5The set where the Gaussian process is large is covered by a collection of half-spaces, the sum of the measures of which is .

Corollary 6Given 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

Trivial bound:

Remark 1Suppose there exists such that

Then .

Proof: Union bound.

Let us merge these two remarks.

Definition 7Given classes, , ,

Say that dominates if each set is contained in a set .

Then

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).

Less ambitious

**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 8Say a probability measure on is -spread if for all , .

For instance, is -spread.

Example 3The measure which is uniform on sets of cardinality is -spread.

Definition 9A 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 11If is a down class, and , let

Given view as a kind of distance of to .

**Conjecture**: There exists such that if is a down class,

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 12Say a set satisfies if compares, up to a factor, with a multilinear polynomial.

Hopefully, every set satisfies . This would be our boldest conjecture.

Theorem 13If is a down class and satisfies , conjecture 3 holds for .

Property survives various operations, which makes production of a counter example a hard task.