Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
Abstract
Description
Consider a random sum $η_1 v_1 + ... + η_n v_n$, where $η_1,...,η_n$ are i.i.d. random signs and $v_1,...,v_n$ are integers. The Littlewood-Offord problem asks to maximize concentration probabilities such as $¶(η_1 v_1 + ... + η_n v_n = 0)$ subject to various hypotheses on the $v_1,...,v_n$. In this paper we develop an \emph{inverse} Littlewood-Offord theorem (somewhat in the spirit of Freiman's inverse sumset theorem), which starts with the hypothesis that a concentration probability is large, and concludes that almost all of the $v_1,...,v_n$ are efficiently contained in an arithmetic progression. As an application we give some new bounds on the distribution of the least singular value of a random Bernoulli matrix, which in turn gives upper tail estimates on the condition number.
37 pages, no figures, to appear, Annals of Math. Referee comments incorporated
37 pages, no figures, to appear, Annals of Math. Referee comments incorporated