The Littlewood-Offord problem and invertibility of random matrices

We prove two basic conjectures on the distribution of the smallest singular value of random n x n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n(-1/2), which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables X-k and real numbers a(k), determine the probability p that the Sum Sigma(k)a(k)X(k) lies near some number v. For arbitrary coefficients a(k) of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p. Published by Elsevier Inc.