You are currently browsing the tag archive for the ‘Littlewood-Offord theorems’ tag.

Van Vu and I have just uploaded to the arXiv our preprint “A sharp inverse Littlewood-Offord theorem“, which we have submitted to Random Structures and Algorithms.  This paper gives a solution to the (inverse) Littlewood-Offord problem of understanding when random walks are concentrated in the case when the concentration is of polynomial size in the length $n$ of the walk; our description is sharp up to epsilon powers of $n$.  The theory of inverse Littlewood-Offord problems and related topics has been of importance in recent developments in the spectral theory of discrete random matrices (e.g. a “robust” variant of these theorems was crucial in our work on the circular law).

For simplicity I will restrict attention to the Bernoulli random walk.  Given $n$ real numbers $v_1,\ldots,v_n$, one can form the random variable

$S := \epsilon_1 v_1 + \ldots + \epsilon_n v_n$

where $\epsilon_1,\ldots,\epsilon_n \in \{-1,+1\}$ are iid random signs (with either sign +1, -1 chosen with probability 1/2).  This is a discrete random variable which typically takes $2^n$ values.  However, if there are various arithmetic relations between the step sizes $v_1,\ldots,v_n$, then many of the $2^n$ possible sums collide, and certain values may then arise with much higher probability.  To measure this, define the concentration probability $p(v_1,\ldots,v_n)$ by the formula

$p(v_1,\ldots,v_n) = \sup_x {\Bbb P}(S=x)$.

Intuitively, this probability measures the amount of additive structure present between the $v_1,\ldots,v_n$.  There are two (opposing) problems in the subject:

• (Forward Littlewood-Offord problem) Given some structural assumptions on $v_1,\ldots,v_n$, what bounds can one place on $p(v_1,\ldots,v_n)$?
• (Inverse Littlewood-Offord problem) Given some bounds on $p(v_1,\ldots,v_n)$, what structural assumptions can one then conclude about $v_1,\ldots,v_n$?

Ideally one would like answers to both of these problems which come close to inverting each other, and this is the guiding motivation for our paper.

This week I am in San Diego for the 39th ACM Symposium for the Theory of Computing (STOC). Today I presented my work with Van Vu on the condition number of randomly perturbed matrices, which was the subject of an earlier post on this blog. For this short talk (20 minutes), Van and I prepared some slides; of course, in such a short time frame one cannot hope to discuss many of the details of the result, but one can at least convey the statement of the result and a brief sketch of the main ideas in the proof.

One late update (which didn’t make it onto the slides): last week, an alternate proof of some cases of our main result (together with some further generalisations and other results, in particular a circular law for the eigenvalues of discrete random matrices) was obtained by Pan and Zhou, using earlier arguments by Rudelson and Vershynin.

[Update, June 16: It was pointed out to me that the Pan-Zhou result only recovers our result in the case when the unperturbed matrix has a spectral norm of $O(n^{1/2})$ (our result assumes that the unperturbed matrix has polynomial size). Slides also updated.]