Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics

Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics, Discrete Analysis 2018:20, 63 pp.

Szemerédi’s theorem states that for every positive integer $\ell$ and every $\mu>0$ there exists $N$ such that every subset of $\{1,2,\dots,N\}$ of density at least $\mu$ contains an arithmetic progression of length $\ell$. It is not hard to prove that this is equivalent to the statement that if $N$ is sufficiently large, then every function $f:\mathbb Z_N\to[0,1]$ (where $\mathbb Z_N$ is the cyclic group of order $N$) with average value at least $\mu$ satisfies an inequality of the form

$$\mathbb E_{x,d}f(x)f(x+d)\dots f(x+(\ell-1)d)\geq \delta$$

where $\delta$ is a positive constant that depends only on $\mu$ and $\ell$.

We can express this as a statement about a product of random variables, as follows. Let $x$ and $d$ be chosen uniformly at random and for each $1\leq i\leq\ell$ let $X^{(i)}$ be the random variable that takes the value $x+(i-1)d$. Then for every function $f:\mathbb Z_N$ that takes values in $[0,1]$, if $\mathbb E[f(X^{(i)})]\geq\mu$ for each $i$, then we also have that $\mathbb E f(X^{(1)})\dots f(X^{(\ell)})\geq\delta$. A sequence of random variables with this property is called same-set hitting. Note that the random variables $X^{(i)}$ here are not independent, but they are individually uniformly distributed. In particular, they are identically distributed.

The equivalent form of Szemerédi’s theorem given above can be stated and proved for other Abelian groups. A particularly well-known case is when the group is $\mathbb F_p^n$ for some fixed prime $p\geq\ell$. Here we can say more about the corresponding random variables $X^{(i)}$. Now they take values in $\mathbb F_p^n$, and if for each coordinate $j$ we form the vector $\underline{X}_j=(X^{(1)}_j,\dots,X^{(\ell)}_j)$, we find that the vectors $\underline{X}_j$ are independent and identically distributed. Indeed, each one is a random (possibly degenerate) arithmetic progression in the group $\mathbb F_p$.

The purpose of this paper is to consider this situation in general, and in particular to try to understand which systems of random variables $X^{(1)},\dots,X^{(\ell)}$ satisfying the above conditions are same-set hitting.

A related concept, which also comes up in additive combinatorics, is that of being set hitting. This is the natural off-diagonal strengthening of being same-set hitting. That is, the random variables are set hitting if whenever $f_1,\dots,f_\ell$ are functions taking values in $[0,1]$ and $\mathbb Ef_i(X^{(i)})\geq\mu$ for each $i$, we have that $\mathbb Ef_1(X^{(1)})\dots f_\ell(X^{(\ell)})\geq\delta$, where once again $\delta$ depends only on $\mu$ and $\ell$.

To see that this is a considerably stronger property, one need only look at the case of random arithmetic progressions $(X^{(1)},X^{(2)},X^{(3)})$ of length 3 in $\mathbb F_3^n$. If we let $f_1=f_2(x)=1$ if $x_1=0$ and $0$ otherwise, and $f_3(x)=1$ if $x_1=1$ and $0$ otherwise, then each $\mathbb E f_i(X^{(i)})$ is equal to 1/3, but the product $f_1(X^{(1)})f_2(X^{(2)})f_3(X^{(3)})$ is identically zero.

It turns out to be useful in the theory of noise stability to characterize set hitting distributions, and this has been done. But it is harder to characterize same-set hitting distributions. One of the main results of the paper is a characterization in the case $\ell=2$. This is already an interesting case: for example, a consequence of their results is the non-obvious fact that for all $\mu>0$ there exists $\delta>0$ such that if $A$ is a dense subset of $\mathbb F_3^n$ and $(x,y)\in\mathbb F_3^n$ is chosen randomly from all pairs with the property that $y_j-x_j\in\{0,1\}$ for every coordinate $j$, then with probability at least $\delta$ both $x$ and $y$ belong to $A$. For $\ell>2$, sufficient conditions are obtained.

The paper uses techniques from both additive combinatorics and the theory of noise sensitivity, combining the two fields in a new and interesting way. It also contains several interesting open problems.