A sharp inverse Littlewood-Offord theorem

Original · EN

Let ηᵢ, i=1,..., n be iid Bernoulli random variables. Given a multiset of n numbers v₁,..., vₙ, the concentration probability ¶₁() of is defined as ¶₁():= ₓ ¶(v₁ η₁+... vₙ ηₙ=x). A classical result of Littlewood-Offord and Erd os from the 1940s asserts that if the vᵢ are non-zero, then this probability is at most O(n⁻¹/²). Since then, many researchers obtained better bounds by assuming various restrictions on. In this paper, we give an asymptotically optimal characterization for all multisets having large concentration probability. This allow us to strengthen or recover several previous results in a straightforward manner.