Videos

A New Approach to the Inverse Littlewood-Offord Problem

Presenter
February 1, 2010
Keywords:
  • Computer Science and Discrete Mathematics (CSDM)
Abstract
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.