Gaussian width bounds with applications to arithmetic progressions in random settings

DOI10.1093/IMRN/RNY238zbMATH Open1470.11014arXiv1711.05624OpenAlexW2770274520WikidataQ129085254 ScholiaQ129085254MaRDI QIDQ5854232FDOQ5854232

Authors: Jop Briët, Sivakanth Gopi 

Publication date: 16 March 2021

Published in: IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Abstract: 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}omathbb{R}^k$, where each coordinate is a constant-degree multilinear polynomial with 0-1 coefficients. We show the following applications of our bounds. Let $[mathbbZ/NmathbbZ{]}_p$ be the random subset of $mathbbZ/NmathbbZ$ containing each element independently with probability $p$. $$ A set $DsubseteqmathbbZ/NmathbbZ$ is $ell$-intersective if any dense subset of $mathbbZ/NmathbbZ$ contains a proper $(ell+1)$-term arithmetic progression with common difference in $D$. Our main result implies that $[mathbbZ/NmathbbZ{]}_p$ is $ell$-intersective with probability $1-o(1)$ provided $$ for $$. This gives a polynomial improvement for all $ellge3$ of a previous bound due to Frantzikinakis, Lesigne and Wierdl, and reproves more directly the same improvement shown recently by the authors and Dvir. $$ Let $X_k$ be the number of $k$-term arithmetic progressions in $[mathbbZ/NmathbbZ{]}_p$ and consider the large deviation rate $h{o}_k(delta)=logPr[X_{k}geq(1+delta)mathbbE{X}_k]$. We give quadratic improvements of the best-known range of $p$ for which a highly precise estimate of $h{o}_k(delta)$ due to Bhattacharya, Ganguly, Shao and Zhao is valid for all odd $kgeq5$. We also discuss connections with error correcting codes (locally decodable codes) and the Banach-space notion of type for injective tensor products of $el{l}_p$-spaces.

Full work available at URL: https://arxiv.org/abs/1711.05624

Recommendations

• Upper tail large deviations for arithmetic progressions in a random set
• Arithmetic structures in random sets
• Upper tails for arithmetic progressions in random subsets
• Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\)
• An improved construction of progression-free sets

zbMATH Keywords

Gaussian widthSzemerédi's theoremrandom differences

Mathematics Subject Classification ID

Large deviations (60F10) Arithmetic progressions (11B25)

Cited In (10)

• Upper tails via high moments and entropic stability
• Multiple correlation sequences not approximable by nilsequences
• High-entropy dual functions over finite fields and locally decodable codes
• On the upper tail problem for random hypergraphs
• Deviation probabilities for arithmetic progressions and other regular discrete structures
• On the threshold for Szemerédi's theorem with random differences
• Replica symmetry in upper tails of mean-field hypergraphs
• Subspaces of tensors with high analytic rank
• Upper tail large deviations for arithmetic progressions in a random set
• Bivariate fluctuations for the number of arithmetic progressions in random sets

This page was built for publication: Gaussian width bounds with applications to arithmetic progressions in random settings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854232)