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

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

2005-11-08

arxiv.org/abs/math/0511215v2

Mathematics

Probability

37 pages, no figures, to appear, Annals of Math. Referee comments incorporated

Scientific paper

Consider a random sum $\eta_1 v_1 + ... + \eta_n v_n$, where $\eta_1,...,\eta_n$ are i.i.d. random signs and $v_1,...,v_n$ are integers. The Littlewood-Offord problem asks to maximize concentration probabilities such as $\P(\eta_1 v_1 + ... + \eta_n v_n = 0)$ subject to various hypotheses on the $v_1,...,v_n$. In this paper we develop an \emph{inverse} Littlewood-Offord theorem (somewhat in the spirit of Freiman's inverse sumset theorem), which starts with the hypothesis that a concentration probability is large, and concludes that almost all of the $v_1,...,v_n$ are efficiently contained in an arithmetic progression. As an application we give some new bounds on the distribution of the least singular value of a random Bernoulli matrix, which in turn gives upper tail estimates on the condition number.

Affiliated with

Also associated with

No associations

Rating

Inverse Littlewood-Offord theorems and the condition number of random discrete matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inverse Littlewood-Offord theorems and the condition number of random discrete matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104220