Gaussian width bounds with applications to arithmetic progressions in random settings

Abstract

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 $\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\ge \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 \mathrm{Pr}[X_k\ge (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\ge 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.

18 pages, some typos fixed

References in corpus (4)

• Upper tails and independence polynomials in random graphs
• Upper tails for arithmetic progressions in random subsets
• Upper tails for arithmetic progressions in a random set
• On Embeddings of ${\ell }_1^k$ from Locally Decodable Codes

Cited by in corpus (4)

• Multiple correlation sequences not approximable by nilsequences
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Deviation probabilities for arithmetic progressions and irregular discrete structures
• High-entropy dual functions over finite fields and locally decodable codes