Gaussian width bounds with applications to arithmetic progressions in random settings

DOI10.1093/IMRN/RNY238MaRDI QIDQ5854232zbMATH OpenOpenAlexWikidataFDO

Authors Jop Briët, Sivakanth Gopi

Publication date 16 March 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Gaussian widthSzemerédi's theoremrandom differences

Mathematics Subject Classification ID

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

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.

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}\)

Cited in

(10)

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

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)