## Notes of Michel Talagrand’s talk

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. ${p}$-small sets

Vocabulary: Our ambient space will be the hypercube ${\{ 0,1 \}^S}$, ${|S|=n}$. Each point in ${\{ 0,1 \}^S}$ is a subset of ${S}$. To avoid confusion, subsets of ${\{ 0,1 \}^S}$ are called classes. We shall always use the measure ${\mu_p}$ which is the ${n}$th power of the Bernoulli distribution ${\mathcal{B}_p}$ on ${\{ 0,1 \}}$.

An up-class is a class such that ${I\in A}$, ${I\subset J \Rightarrow J\in A}$.

Definition 1 For ${I\in S}$, let $\displaystyle \begin{array}{rcl} H_I =\{J\in S\,;\, I\subset J\}. \end{array}$

Given a class ${A}$, let $\displaystyle \begin{array}{rcl} A^{(q)} =\{J\subset S\,;\, J \textrm{ cannot be covered by }k\textrm{ elements of }A\} \end{array}$

${A^{(q)}}$ is an up-class. We view points of ${A^{(q)}}$ as very far

Main conjecture: When ${A}$ and ${q}$ are large, ${A^{(q)}}$ is very small.

This does not mean that ${A^{(q)}}$ has small measure.

Definition 2 A class ${C}$ is ${p}$-small if there exists a family ${I}$ of subsets of ${S}$ such that$\displaystyle \begin{array}{rcl} C\subset \bigcup H_I \end{array}$

and the sum of ${\mu_p}$ measures of ${H_I}$ is ${\leq \frac{1}{2}}$.

So smallness of ${C}$ is attested by a small number of witnesses.

Example 1 $\displaystyle \begin{array}{rcl} B=\{I\subset S\,;\,|I|\leq k\}. \end{array}$

Proposition 3 If ${\mu_p (B)\geq 9/10}$ and ${q=100}$, then ${B^{(q)}}$ is ${p}$-small.

Proof: ${B^{(q)}}$ is the set of ${J}$ of size ${\geq s=qk+1}$. It is covered by ${H_I}$ with ${|I|=s}$. $\Box$

Main conjecture: When ${A}$ is a down class, ${\mu_p (A)\geq 1-\frac{1}{q}}$ and ${q=10^{10^{10}}}$, ${A^{(q)}}$ is ${p}$-small.

2. Connections to geometry and probability

2.1. Connection to convexity

Carathéodory: For a convex set in ${{\mathbb R}^n}$, every point is the barycenter So ${n}$ additions are needed to construct the convex hull of a balanced set ${A}$. (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 ${G}$.

Convexity conjecture: The exists ${q}$ such that for every banaced ${D}$, there exists a convex set ${C}$ which is contained in the sum of ${q}$ copies of ${D}$.

The Main conjecture is a kind of discretized version of the Convexity conjecture (down-class refelcts convexity).

2.2. Stochastic processes

Given stochastic process ${X_t}$, ${t\in T}$, estimate ${\sup_{t\in T}X_t}$.

Example 2 ${X_t (\omega)=t\cdot\omega}$ for ${\omega}$ in Gaussian ${{\mathbb R}^n}$, ${t}$ in a subset ${T}$ of ${{\mathbb R}^n}$.

Theorem 4 ${\mathop{\mathbb E}(\sup_{t\in T}X_t)\sim\gamma_2 (T)}$, 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 ${\leq\frac{1}{2}}$.

Corollary 6 Given a convex balanced set ${C}$, is covered by a collection of half-spaces, the sum of the measures of which is ${\leq\frac{1}{2}}$.

Reformulated convexity conjecture: Replace ${C}$ has large Gaussian measure with its complement is covered by half spaces, the sum of the measures of which is ${\leq\frac{1}{2}}$.

I view ${A^{(q)}}$ as a discrete analogue of the complement of ${A+A+\cdots +A}$.

2.3. Selector processes on sets

Independantly select at ${\mathcal{B}_p}$ random points of ${S}$, producing random subsets ${Y}$. Given a class ${F}$, estimate the quantity

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_p (F):=\mathop{\mathbb E}_{Y} (\sup_{I\in F}|I\cap Y) \end{array}$

Trivial bound: ${\mathop{\mathbb E}_p (F)\leq\max\{|I|\,;\,I\in F\}}$

Remark 1 Suppose there exists ${M\geq 1}$ such that$\displaystyle \begin{array}{rcl} \sum_{J\in F}(\frac{p|J|}{M})^M \leq 1. \end{array}$

Then ${\mathop{\mathbb E}_p (F)\leq LN}$.

Proof: Union bound.

Let us merge these two remarks.

Definition 7 Given classes, ${F}$, ${G}$,$\displaystyle \begin{array}{rcl} F+G=\{I\cup J\,;\, I\in F\, J\in G\}. \end{array}$

Say that ${G}$ dominates ${F}$ if each set ${I\in F}$ is contained in a set ${I\in G}$.

Then

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_p (F)\leq \mathop{\mathbb E}_p (G). \end{array}$

This gives a method to estimate ${\mathop{\mathbb E}_p}$.

Question: Are the above two remarks the only way to estimate ${\mathop{\mathbb E}_p}$ ? I.e., is every class ${F}$ a small perturbation of a class ${G}$ for which the union bound is sharp ?

2.4. General selector processes

Let ${Y}$ be a random set. Given a vector ${t\in{\mathbb R}^S}$, let ${X_t =\sum_{i\in Y}t_i}$. Estimate

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_p (\sup_{t\in T}X_t) \end{array}$

as a function of the geometry of ${T}$. Seems related to

Bernoulli problem: estimate ${\mathop{\mathbb E}_p (\sup_{t\in T}\sum_{i}\epsilon_i t_i)}$, ${\epsilon_i \in\pm 1}$ 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 ${Y}$‘s) where the selector process is large (compared to its expectation) is ${p}$-small.

This would follow from the Main conjecture. Indeed,

$\displaystyle \begin{array}{rcl} \{Y\subset S\,;\, \sup_{t\in T}X_t \geq LM\} \end{array}$

is a down class.

3. Approaches to the Main conjecture

3.1. Relaxing smallness: measures

${p}$-small sets are hard to manipulate, so I introduce easier notions.

Definition 8 Say a probability measure ${\nu}$ on ${B^S}$ is ${\delta}$-spread if for all ${I\in S}$, ${\nu(H_I)\subset \delta^{|I|}}$.

For instance, ${\mu_p}$ is ${p}$-spread.

Example 3 The measure which is uniform on sets of cardinality ${1}$ is ${\frac{1}{n}}$-spread.

Definition 9 A class is weakly ${\delta}$-small if it does not carry a ${\delta}$-spread probability measure.

Proposition 10 ${p}$-small implies weakly ${p}$-small.

Question: Is the converse true, up to a multiplicative constant ?

Weak form of Main conjecture: When ${A}$ is a down class, ${\mu_p (A)\geq 1-\frac{1}{q}}$ and ${q=10^{10^{10}}}$, ${A^{(q)}}$ is weakly ${p}$-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 ${A^{(q)}}$ :

Definition 11 If ${A}$ is a down class, and ${I\subset S}$, let$\displaystyle \begin{array}{rcl} A_I =\{J\subset I\,;\,J\in A\}. \end{array}$

Given ${\alpha\in (0,1)}$ view ${\mu_{\alpha}(A_I)}$ as a kind of distance of ${I}$ to ${A}$.

Conjecture: There exists ${\alpha>0}$ such that if ${A}$ is a down class,

$\displaystyle \begin{array}{rcl} \mu_p (A)\leq \prod \mu_p (A_I)^{\nu(\{I\})}. \end{array}$

Which down classes satisfy the conjecture for all ${p}$-spread measures ${\nu}$ ? For this, one must control the measure of ${A}$ for each product measure. Product measures are indexed by vectors ${t\in {\mathbb R}_+^S}$ (${\lambda_t =\bigotimes_{i}\mathcal{B}_{e^{-t_i}}}$). One is interested in ${-\log\lambda_t (A)}$ as a function of ${t}$. For instance, if ${A=\{\emptyset\}}$, ${-\log\lambda_t (A)=\sum_i t_i}$. In general, it is complicated. So we compare it with multilinear polynomials.

Definition 12 Say a set ${A}$ satisfies ${C_{\gamma}}$ if ${t\mapsto -\log\lambda_t (A)}$ compares, up to a ${\gamma}$ factor, with a multilinear polynomial.

Hopefully, every set satisfies ${C_{\gamma}}$. This would be our boldest conjecture.

Theorem 13 If ${A}$ is a down class and satisfies ${C_{\gamma}}$, conjecture 3 holds for ${\alpha\leq 1-(1-p)^{\gamma/\delta}}$.

Property ${C_{\gamma}}$ survives various operations, which makes production of a counter example a hard task.

﻿