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

- African Institute for Mathematical Sciences
- More about Jan Hązła

- Mathematics, MIT
- More about Elchanan Mossel

### Editorial introduction

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 ℓ and every μ>0 there exists N such that every subset of {1,2,…,N} of density at least μ contains an arithmetic progression of length ℓ. It is not hard to prove that this is equivalent to the statement that if N is sufficiently large, then every function f:ZN→[0,1] (where ZN is the cyclic group of order N) with average value at least μ satisfies an inequality of the form

Ex,df(x)f(x+d)…f(x+(ℓ−1)d)≥δ

where δ is a positive constant that depends only on μ and ℓ.

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≤i≤ℓ let X(i) be the random variable that takes the value x+(i−1)d. Then for every function f:ZN that takes values in [0,1], if E[f(X(i))]≥μ for each i, then we also have that Ef(X(1))…f(X(ℓ))≥δ. 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 Fnp for some fixed prime p≥ℓ. Here we can say more about the corresponding random variables X(i). Now they take values in Fnp, and if for each coordinate j we form the vector X_j=(X(1)j,…,X(ℓ)j), we find that the vectors X_j are independent and identically distributed. Indeed, each one is a random (possibly degenerate) arithmetic progression in the group Fp.

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),…,X(ℓ) 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 f1,…,fℓ are functions taking values in [0,1] and Efi(X(i))≥μ for each i, we have that Ef1(X(1))…fℓ(X(ℓ))≥δ, where once again δ depends only on μ and ℓ.

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 Fn3. If we let f1=f2(x)=1 if x1=0 and 0 otherwise, and f3(x)=1 if x1=1 and 0 otherwise, then each Efi(X(i)) is equal to 1/3, but the product f1(X(1))f2(X(2))f3(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 ℓ=2. This is already an interesting case: for example, a consequence of their results is the non-obvious fact that for all μ>0 there exists δ>0 such that if A is a dense subset of Fn3 and (x,y)∈Fn3 is chosen randomly from all pairs with the property that yj−xj∈{0,1} for every coordinate j, then with probability at least δ both x and y belong to A. For ℓ>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.