This is an announcement for the paper "The Littlewood-Offord Problem and invertibility of random matrices" by Mark Rudelson and Roman Vershynin.

Abstract: We prove two basic conjectures on the distribution of the smallest singular value of random n times 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 of 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.

Archive classification: Probability; Functional Analysis

Mathematics Subject Classification: 15A52; 11P70

Remarks: 35 pages, no figures

Submitted from: vershynin@math.ucdavis.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/math.PR/0703503

or

http://arXiv.org/abs/math.PR/0703503

or by email in unzipped form by transmitting an empty message with subject line

uget 0703503

or in gzipped form by using subject line

get 0703503

to: math@arXiv.org.