Let η_{1}, . . . , η_{n} be iid Bernoulli random variables, taking values 1, −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 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.

# A New Approach to the Inverse Littlewood-Offord Problem

Hoi H. Nguyen

Rutgers, The State University of New Jersey

February 1, 2010