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

Abstract

Consider a random sum r)\V + • • • + r]nvn, where 771, . . . , rin are independently and identically distributed (i.i.d.) random signs and vi, . . . , vn are integers. The Littlewood-Offord problem asks to maximize concentration probabilities such as P(r?i^iH 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 , . . . , vn are efficiently contained in a generalized arithmetic progression. As an application we give a new bound on the magnitude of the

Locations

• Annals of Mathematics - View - PDF
• arXiv (Cornell University) - View - PDF
• Annals of Mathematics - View - PDF
• arXiv (Cornell University) - View - PDF