Tao, Terence; Vu, Van H. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. (English) Zbl 1250.60023 Ann. Math. (2) 169, No. 2, 595-632 (2009). Summary: Consider a random sum \(\eta_1v_1 + \dots + \eta_nv_n\), where \(\eta 1,\dots,\eta n\) are independently and identically distributed (i.i.d.) random signs and \(v_1,\dots,v_n\) are integers. The Littlewood-Offord problem asks to maximize concentration probabilities such as \(\mathbf P(\eta_1v_1 + \dots + \eta_nv_n = 0)\) subject to various hypotheses on \(v_1,\dots,v_n\). In this paper we develop an inverse Littlewood-Offord theory (somewhat in the spirit of Freiman’s inverse theory in additive combinatorics), which starts with the hypothesis that a concentration probability is large, and concludes that almost all of the \(v_1,\dots,v_n\) are efficiently contained in a generalized arithmetic progression. As an application we give a new bound on the magnitude of the least singular value of a random Bernoulli matrix, which in turn provides upper tail estimates on the condition number. Cited in 5 ReviewsCited in 111 Documents MSC: 60G50 Sums of independent random variables; random walks 15B52 Random matrices (algebraic aspects) 60E15 Inequalities; stochastic orderings 60F05 Central limit and other weak theorems PDFBibTeX XMLCite \textit{T. Tao} and \textit{V. H. Vu}, Ann. Math. (2) 169, No. 2, 595--632 (2009; Zbl 1250.60023) Full Text: DOI arXiv Link