Optimal Inverse Littlewood-Offord theorems

By Hoi H. Nguyen, Van H. Vu. 2010

110 citations recorded by the source corpus.

Abstract Let η i , i = 1 , … , n , be iid Bernoulli random variables, taking values ±1 with probability 1 2 . Given a multiset V of n integers v 1 , … , v n , we define the concentration probability as ρ ( V ) : = sup x P ( v 1 η 1 + ⋯ + v n η n = x ) . A classical result of Littlewood–Offord and Erdős from the 1940s asserts that, if the v i are non-zero, then ρ ( V ) is O ( n − 1 / 2 ) . Since then, many researchers have obtained improved bounds by assuming various extra restrictions on V. About 5 years ago, motivated by problems concerning random matrices, Tao and Vu introduced the inverse Littlewood–Offord problem. In the inverse problem, one would like to characterize the set V, given that ρ ( V ) is relatively large. In this paper, we introduce a new method to attack the inverse problem. As an application, we strengthen the previous result of Tao and Vu, obtaining an optimal characterization for V. This immediately implies several classical theorems, such as those of Sarkozy and Szemeredi and Halasz. The method also applies to the continuous setting and leads to a simple proof for the β-net theorem of Tao and Vu, which plays a key role in their recent studies of random matrices. All results extend to the general case when V is a subset of an abelian torsion-free group, and η i are independent variables satisfying some weak conditions.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0641eab2bd6e326c871c2175672577083ff72469

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

Local Universality of Zeroes of Random Polynomials (2013, methodology): “There are many such theorems in the literature; we will use [Nguyen & Vu, 2011, Theorem 2.9].”