Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
| dc.creator | Tao, Terence | |
| dc.creator | Vu, Van | |
| dc.date | 2005-11-08 | |
| dc.date | 2007-01-28 | |
| dc.date.accessioned | 2026-07-07T07:43:08Z | |
| dc.date.available | 2026-07-07T07:43:08Z | |
| dc.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. | |
| dc.description | 37 pages, no figures, to appear, Annals of Math. Referee comments incorporated | |
| dc.identifier | https://arxiv.org/abs/math/0511215 | |
| dc.identifier | http://arxiv.org/abs/math/0511215 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/122705 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 15A52; 11P70 | |
| dc.title | Inverse Littlewood-Offord theorems and the condition number of random discrete matrices | |
| dc.type | text |