Paper Info
Title
Gaussian Width Bounds With Applications To Arithmetic Progressions In Random Settings
Abstract
Motivated by a problem on random differences in Szemeredi's theorem and another problem on large deviations for arithmetic progressions in random sets, we prove upper bounds on the Gaussian width of special point sets in R-k. The point sets are formed by the image of the n-dimensional Boolean hypercube under a mapping psi : R-n -> R-k, where each coordinate is a constant-degree multilinear polynomial with 0-1 coefficients. We show the following applications of our bounds. Let [Z/NZ](p) be the random subset of Z/NZ containing each element independently with probability p.1) A set D subset of Z/N Z is l-intersective if any dense subset of Z/N Z contains a proper (l + 1)-term arithmetic progression with common difference in D. Our main result implies that [Z/N Z](p) is l-intersective with probability 1 - o(1) provided p = >= omega(N-beta l logN) for beta(l) = (inverted right perpendiclar(l + 1)/2inverted left perpendiclar)(-1). This gives a polynomial improvement for all l >= 2 of a previous bound due to Frantzikinakis, Lesigne, and Wierdl, and reproves more directly the same improvement shown recently by the authors and Dvir (here we avoid the theories of locally decodable codes and quantum information).2) Let X-k be the number of k-term arithmetic progressions in [Z/N Z](p) and consider the large deviation rate rho k(delta) = log Pr[X-k >= (1 + delta)EXk]. 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 >= 5. In particular, the estimate holds if p >= omega(N-ck logN) for ck = (c(k) = inverted right perpenicular(k - 1)/2inverted left perpenicular)(-1). We also discuss connections with the above-mentioned error correcting codes (locally decodable codes) and the Banach-space notion of type for injective tensor products of l(p)-spaces.
Year
DOI
Venue
2017
10.1093/imrn/rny238
INTERNATIONAL MATHEMATICS RESEARCH NOTICES
Field
DocType
Volume
Tensor product,Discrete mathematics,Combinatorics,Injective function,Gaussian random field,Arithmetic,Multilinear polynomial,Gaussian,Omega,Hypercube,Mathematics,Dense set
Journal
2020
Issue
ISSN
Citations 
22
1073-7928
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
Jop Briet1457.41
Sivakanth Gopi2255.63