  Motivated by problems on random differences in Szemer\'{e}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
$\psi:\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 \omega(N^{-\beta_\ell}\log N)$ for $\beta_\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
$\rho_k(\delta) = \log\Pr[X_k \geq (1+\delta)\mathbb{E}X_k]$. We give quadratic
improvements of the best-known range of $p$ for which a highly precise estimate
of $\rho_k(\delta)$ 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.
