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

Abstract

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.

Authors

Terence Tao

Department of Mathematics
University of California
Los Angeles, CA 90095
United States

Van H. Vu

Department of Mathematics
Rutgers University
Piscataway, NJ 08854
United States