A sharp inverse Littlewood-Offord theorem

Terence Tao, Van H. VuRandom Struct. Algorithms 2010 · DOI

TL;DR

This paper introduces a "strong inverse Littlewood-Offord theorem" that precisely characterizes when a random walk's sum is likely to fall within a small set. It establishes a tight relationship between the concentration probability of a random walk and the additive structure of its steps, showing that high concentration implies the steps must lie within a generalized arithmetic progression (GAP) of a specific rank and volume.

What Problem Does This Paper Address?

The Littlewood-Offord problem, and its inverse, are fundamental questions in combinatorics and probability concerning the distribution of sums of random variables. Specifically, the Littlewood-Offord problem asks how concentrated the sum $S(v) = \sum_{i=1}^n \epsilon_i v_i$ can be, where $v_i$ are numbers and $\epsilon_i$ are random signs or coin flips. The "inverse" problem asks: if the sum is highly concentrated (i.e., has a high probability of landing on a specific value), what can we say about the structure of the $v_i$?

Previous work established that if the $v_i$ are non-zero, the concentration probability is at most $O(n^{-1/2})$. Later results improved this bound under stronger assumptions, like the $v_i$ being distinct. However, a precise characterization of when the concentration probability is large, and what that implies about the $v_i$'s additive structure, remained an open question. This paper tackles this by providing a sharp, "asymptotically optimal" characterization for multisets $v$ with large concentration probabilities, focusing on the structure of generalized arithmetic progressions (GAPs).

Methods

The paper introduces a novel algorithmic approach to prove its main results. The core idea is to iteratively construct a sequence of symmetric generalized arithmetic progressions (GAPs), $Q_i$, and associated "bad" elements from the input multiset $v$.

  1. Algorithm: The algorithm starts with an initial GAP $Q_0 = \{0\}$ and the input multiset $v$. In each step $i+1$, it identifies elements in the current multiset $v^i$ that are "bad" with respect to $Q_i$ (meaning they significantly expand the set $Q_i$ when added).
  2. GAP Construction: If a sufficient number of bad elements are found, a new GAP $Q_{i+1}$ is constructed by extending $Q_i$ using these bad elements. This process continues until a stopping condition is met.
  3. Analysis: The algorithm's analysis relies on defining a "potential" function $F_i$ related to the concentration probability and the size of the GAPs. Key lemmas establish how these potentials and GAP sizes evolve with each step, particularly distinguishing between "proper" and "improper" GAP constructions.
  4. Key Tools: The proof heavily utilizes concepts from additive combinatorics, including:
  5. Generalized Arithmetic Progressions (GAPs): Sets of the form $\{ \sum_{i=1}^d n_i v_i : |n_i| \le N_i \}$.
  6. Ruzsa Triangle Inequality: A fundamental tool for bounding the size of sumsets and difference sets.
  7. Cauchy-Schwarz Inequality: Used to count solutions to additive equations.
  8. Freiman Isomorphisms: Used to reduce problems in general groups to the integers.

The "strong inverse theorem" (Theorem 1.9) is derived as a special case of a more general theorem (Theorem 1.10), which is proven using this algorithmic framework.

Datasets

Not discussed in the paper. The paper deals with theoretical mathematical objects (multisets of elements in additive groups) rather than empirical datasets.

Key Insights and Ideas

  • Tight Characterization of Concentration: The paper provides a sharp characterization of when a random walk's sum is highly concentrated. It's not just about the $v_i$ being "structured" in a general sense, but specifically about them lying within a generalized arithmetic progression (GAP) of a controlled rank and volume.
  • Algorithmic Proof Technique: The introduction of an algorithm that iteratively constructs GAPs and analyzes their properties is a novel and powerful approach to proving inverse theorems in additive combinatorics. This method allows for precise control over the parameters involved.
  • Rank vs. Volume Trade-off: The results highlight a crucial trade-off between the rank of the GAP and its volume. A high concentration probability implies the existence of a GAP with a low rank (relative to the concentration bound) and a correspondingly controlled volume.
  • "Asymptotically Optimal" Bounds: The paper claims its bounds are "asymptotically optimal," meaning that the exponents and dependencies on parameters like rank and volume cannot be significantly improved.

Key Results

  • Theorem 1.9 (Strong Inverse Theorem): If $P_\mu(v) \ge n^{-A}$ for some $A > 0$, then there exists a proper symmetric GAP $Q$ of rank at most $O(A)$ and volume $O(n^{A - 1/2 + O(\epsilon)})$, which contains all but $O(n^{1-\epsilon})$ elements of $v$. This is a significant improvement over previous "weak" inverse theorems.
  • Theorem 1.10 (General Strong Inverse Theorem): This is a more general version of Theorem 1.9, providing a bound on the volume of the GAP in terms of the concentration probability and a parameter $k$. It states that if $P_\mu(v) \ge C_0 k^{-d}$, then there exists a GAP $Q$ of rank at most $d-1$ and volume $O(P_\mu(v)^{-1} k^\epsilon)$ such that $Q_{1/k}$ contains almost all elements of $v$.
  • Proposition 1.7 (Forward Theorem): If the steps $v_i$ lie in a symmetric GAP $Q$ of rank $d$, then the concentration probability $P_\mu(v)$ is bounded by $O_d(Q \mu n^{-1}) \gg_d (1 + \mu n)^{-d/2} |Q|^{-1}$. This provides the "forward" direction, showing that structure implies concentration.
  • Proposition 1.12: Recovers classical bounds for the concentration probability when all $v_i$ are non-zero ($P_\mu(v) \ll_{\mu,\epsilon} n^{-1/2+\epsilon}$) or distinct ($P_\mu(v) \ll_{\mu,\epsilon} n^{-3/2+\epsilon}$), up to small epsilon losses.

Limitations and Future Work

  • Epsilon Losses: While the results are described as "sharp" and "asymptotically optimal," they often come with small additive or multiplicative "epsilon losses" in exponents. The paper acknowledges that these are often artifacts of the proof techniques and might be removable with further work.
  • Constant Dependencies: The implied constants in the asymptotic notation can depend on various parameters (like $d, \epsilon, \mu, K$). Making these constants explicit or understanding their behavior is a common challenge in such problems.
  • Generalization to Other Groups: The paper focuses on torsion-free additive groups and mentions that results can be reduced to the integer case via Freiman isomorphisms. Extending these results to groups with torsion might require different techniques.
  • Applications: The paper mentions applications of its theorems in recovering classical bounds and hints at further applications in related areas of combinatorics and probability. The full scope of these applications could be a direction for future research.

Summary updated

BibTeX
@article{tao2010sharp,
  author = {Terence Tao and Van H. Vu},
  title = {{A sharp inverse Littlewood-Offord theorem}},
  journal = {Random Struct. Algorithms},
  year = {2010},
  doi = {10.1002/rsa.20327},
}
Figure