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

Terence Tao¹ ; Van H. Vu²

¹ Department of Mathematics <br/>University of California<br/>Los Angeles, CA 90095<br/>United States
² Department of Mathematics<br/>Rutgers University<br/>Piscataway, NJ 08854<br/>United States

Annals of mathematics, Tome 169 (2009) no. 2, pp. 595-632.

Résumé

Consider a random sum $\eta_1 v_1 + …+ \eta_n v_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 $\Bbb{P}( \eta_1 v_1 + …+ \eta_n v_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.

Détail

DOI : 10.4007/annals.2009.169.595