Inverse Littlewood-Offord theorems and the condition number of random discrete matrices

• 成果类型: Article
• 署名作者: Tao, Terence; Vu, Van H.
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2009.169.595
• 发表日期: 2009
• 页码: 595-632
• 关键词: DISTRIBUTIONS; singularity; probability; eigenvalues

摘要

Consider a random sum eta(1)nu(1) + ... + eta(n)nu(n), where eta(1), ... , eta(n) are independently and identically distributed (i.i.d.) random signs and nu(1), ... , nu(n) are integers. The Littlewood-Offord problem asks to maximize concentration probabilities such as P(eta(1)nu(1) + ... + eta(n)nu(n) = 0) subject to various hypotheses on nu(1), ... , nu(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 nu(1), ... , nu(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.