Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, January 26, 2010 - 4:30pm

Hoi H. Nguyen

Rutgers

Location

University of Pennsylvania

DRL 2N36

Let \eta_1,..,\eta_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 ho(V) := \sup_x P(v_1\eta_1+...+ v_n \eta_n=x). A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v_i are non-zero, then ho(V) is O(n^{-1/2}). Since then, many researchers 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 give a characterization of the set V, given that ho(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 v_i are different, ho(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 \eta_i are independent variables satisfying some weak conditions. Inverse results in continuous setting will also be included. Joint work with Van Vu, Rutgers University