The Reverse Littlewood--Offord problem of Erdős

Abstract

Let ${\epsilon }_1,\dots ,{\epsilon }_n$ be a sequence of independent Rademacher random variables. We prove that there is a constant $c>0$ such that for any unit vectors $v_1,\dots ,v_n\in {\mathbb{R}}^2$, $$\mathrm{Pr}\left[||{\epsilon }_1{v}_1+\dots +{\epsilon }_n{v}_n|{|}_2\le \sqrt{2}\right]\ge \frac{c}{n}.$$ This resolves the only remaining conjecture from the seminal paper of Erdős on the Littlewood--Offord problem, and it is sharp both in the sense that the constant $\sqrt{2}$ cannot be reduced and that the magnitude $n^{-1}$ is best possible. We also prove polynomial bounds for the analogous problem in higher dimensions.

15 pages; updated with reference to earlier work of Beck