A New Approach to the Inverse Littlewood-Offord Problem

Let η1, . . . , ηn be iid Bernoulli random variables, taking values 1, −1 with probability 1/2. Given a multiset V of n integers v1, . . . , vn, we define the concentration probability as ρ(V ) := supx P(v1η1 + · · · + vnηn = x).
A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the vi are non-zero, then ρ(V ) is O(n−1/2). Since then, many researchers obtained improved bounds by assuming various extra restrictions on V .
About five 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 give a characterization of the set V , given that ρ(V ) is relatively large. In this talk I will present a new, general method to attack the inverse problem. As an application, we strengthen a previous result of Tao and Vu, obtaining an optimal characterization for V . This immediately implies several classical theorems, such as those of Sarkozy-Szemeredi and Halasz. As another application, we obtain an asymptotic, stable version of a famous theorem of Stanley that shows that under the assumption that the vi are different, ρ(V ) attains its maximum value when V is a symmetric arithmetic progression.
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. Inverse results in continuous setting will also be included.

Date

Affiliation

Rutgers, The State University of New Jersey

Speakers

Hoi H. Nguyen