An optimal version of the inverse Littlewood-Offord theorem

Hoi Nguyen
Rutgers University

Let V={v_1,..,v_n} be a multiset of n real numbers. Let eta_i be i.i.d.
Bernoulli random variables. The concentration probability P(V) of V is defined as P(V):=sup_v P(eta_1 v_1 +...+ eta_n v_n = v). A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v_i are non-zero, then the concentration probability of V is O(n^{-1/2}).
In the reverse direction, Tao and Vu proved that any set of large concentration probability must have structure. In this talk, we will provide a general approach that gives an almost best possible characterization for all such V. This allows us to recover several previous forward Littlewood-Offord results, including a significant result of Stanley from the 1980s on the optimal value of P(V) when v_i are distinct. (Joint with Van Vu, Rutgers University)

Back to Workshop IV: Analytical Methods in Combinatorics, Additive Number Theory and Computer Science