Gaussian width bounds with applications to arithmetic progressions in random settings

Motivated by problems on random differences in Szemerédi’s theorem and on
large deviations for arithmetic progressions in random sets, we prove upper
bounds on the Gaussian width of point sets that are formed by the image of the
$n$-dimensional Boolean hypercube under a mapping
$ψ:\mathbb{R}^n\to\mathbb{R}^k$, where each coordinate is a constant-degree
multilinear polynomial with 0-1 coefficients. We show the following
applications of our bounds. Let $[\mathbb{Z}/N\mathbb{Z}]_p$ be the random
subset of $\mathbb{Z}/N\mathbb{Z}$ containing each element independently with
probability $p$.

$\bullet$ A set $D\subseteq \mathbb{Z}/N\mathbb{Z}$ is $\ell$-intersective if
any dense subset of $\mathbb{Z}/N\mathbb{Z}$ contains a proper $(\ell+1)$-term
arithmetic progression with common difference in $D$. Our main result implies
that $[\mathbb{Z}/N\mathbb{Z}]_p$ is $\ell$-intersective with probability $1 –
o(1)$ provided $p \geq ω(N^{-β_\ell}\log N)$ for $β_\ell =
(\lceil(\ell+1)/2\rceil)^{-1}$. This gives a polynomial improvement for all
$\ell \ge 3$ of a previous bound due to Frantzikinakis, Lesigne and Wierdl, and
reproves more directly the same improvement shown recently by the authors and
Dvir.

$\bullet$ Let $X_k$ be the number of $k$-term arithmetic progressions in
$[\mathbb{Z}/N\mathbb{Z}]_p$ and consider the large deviation rate
$ρ_k(δ) = \log\Pr[X_k \geq (1+δ)\mathbb{E}X_k]$. We give quadratic
improvements of the best-known range of $p$ for which a highly precise estimate
of $ρ_k(δ)$ due to Bhattacharya, Ganguly, Shao and Zhao is valid for
all odd $k \geq 5$.

We also discuss connections with error correcting codes (locally decodable
codes) and the Banach-space notion of type for injective tensor products of
$\ell_p$-spaces.