Gaussian width bounds with applications to arithmetic progressions in random settings

Jop Briët, Sivakanth GopiarXiv 2017 · arXiv

In the world of probabilistic combinatorics, understanding the "width" of a set of points can reveal deep truths about how random structures behave. In their paper, "Gaussian width bounds with applications to arithmetic progressions in random settings," Jop Briët and Sivakanth Gopi provide powerful new upper bounds for the Gaussian width of specific point sets. These bounds lead to significant improvements in our understanding of arithmetic progressions (APs) within random subsets of integers.

TL;DR

The authors prove new upper bounds on the Gaussian width of point sets generated by multilinear polynomials over the Boolean hypercube. These geometric bounds provide "polynomial improvements" to the density thresholds required for random sets to contain arithmetic progressions and sharpen the estimates for how often these progressions occur in rare "large deviation" events.

What Problem Does This Paper Address?

The core challenge lies in estimating the Gaussian width of a set $T \subseteq \mathbb{R}^k$, defined as the expected maximum correlation between points in $T$ and a standard Gaussian vector. While Gaussian width is a fundamental concept in high-dimensional probability and convex geometry, it is notoriously difficult to calculate for complex sets.

The authors focus on sets formed by the image of a Boolean hypercube $\{0, 1\}^n$ under a multilinear polynomial mapping. This isn't just a theoretical exercise; these specific sets appear naturally when studying arithmetic progressions in random environments. Specifically, the paper addresses two long-standing problems:

  1. $\ell$-intersective sets: At what density does a random subset of integers almost certainly contain an $(\ell+1)$-term arithmetic progression with a common difference from a specified set?
  2. Large Deviations: How accurately can we predict the probability that a random set contains significantly more $k$-term arithmetic progressions than expected (the "upper tail" problem)?

Methods

The authors bridge the gap between geometry and combinatorics using several sophisticated tools:

  • Random Matrix Theory: A cornerstone of the proof is the Tomczak-Jaegermann inequality (1974), a non-commutative version of the Khintchine inequality. This allows the authors to bound the spectral norm of random matrices, which they use to handle the quadratic case of their mapping.
  • Hypergraph Reductions: To handle higher-degree polynomials (degree $d > 2$), the authors reduce the problem to the quadratic case. They represent the polynomial's support as a hypergraph and decompose it into a small number of "matchings" (sets of edges that don't overlap).
  • Generalized Birthday Paradox: They employ a variant of the birthday paradox to show that a random mapping into a high-dimensional space will, with high probability, "cover" the edges of their hypergraph in a way that preserves the properties needed for their matrix bounds.
  • Banach Space Theory: The paper links Gaussian width to the concept of "type" constants in Banach spaces, specifically for injective tensor products of $\ell_p$-spaces. This provides a structural geometric framework for their combinatorial results.

Datasets

As a theoretical mathematics paper, this work does not use empirical datasets. Instead, it operates on mathematical structures:

  • The Boolean Hypercube: $\{0, 1\}^n$.
  • Random Subsets: $[Z/NZ]_p$, where each element is chosen independently with probability $p$.
  • Arithmetic Progressions: $k$-term sequences of the form $a, a+b, \dots, a+(k-1)b$.

Key Insights and Ideas

  • The "Ceiling" Effect: The main theorem (Theorem 1.1) features an exponent involving $\lceil d/2 \rceil$. This arises because the authors reduce higher-degree problems to the quadratic case. They suggest that removing this ceiling (improving the exponent from $1 - 1/\lceil d/2 \rceil$ to $1 - 2/d$) is a major open question that could unlock even stronger results.
  • Geometric-Combinatorial Duality: The paper demonstrates that hard problems in additive number theory (like finding APs) can be translated into geometric problems (bounding the width of a point set). If the set is "narrow" enough, the random structure behaves predictably.
  • LDC Connection: The authors highlight a deep link between Gaussian width and Locally Decodable Codes (LDCs). Techniques used to prove lower bounds on the length of LDCs (often using quantum information theory) are shown here to be reachable through purely classical geometric means.

Key Results

The paper delivers concrete improvements over previous best-known results:

  • Intersective Sets: For $\ell \geq 3$, they provide a polynomial improvement on the density $p$ required for a random set to be $\ell$-intersective. For example, they show it holds for $p \geq \omega(N^{-\beta_\ell} \log N)$ where $\beta_\ell = 1/\lceil (\ell+1)/2 \rceil$.
  • Large Deviation Rates: They provide "quadratic improvements" for the range of $p$ where the large deviation rate for $k$-term APs can be precisely estimated for all odd $k \geq 5$.
  • Theorem 1.1: The main technical result provides a bound of $GW \lesssim nt \sqrt{kn^{1 - \frac{1}{\lceil d/2 \rceil}} \log n}$, which serves as the engine for the combinatorial applications.

Limitations and Future Work

The most prominent limitation is the $\lceil d/2 \rceil$ factor in the exponent. The authors acknowledge that their reduction to the quadratic case might not be optimal. If the exponent could be improved to $1 - 2/d$, it would resolve several conjectures in coding theory and Szemerédi-type theorems.

Additionally, the results for large deviations currently require the modulus $N$ to be a prime number to utilize certain transitive properties of arithmetic progressions. Extending these high-precision estimates to composite $N$ remains a direction for future research.

Summary updated

BibTeX
@misc{briet2017gaussian,
  author = {Jop Briët and Sivakanth Gopi},
  title = {{Gaussian width bounds with applications to arithmetic progressions in random settings}},
  year = {2017},
  eprint = {1711.05624},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.05624},
}
Figure