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.

One of the first forward Littlewood-Offord theorems was by Erdős, who showed

Theorem 1. If at least k of the v_1,\ldots,v_n are non-zero, then p(v_1,\ldots,v_n) \leq O(k^{-1/2}).

In fact the sharp bound was computed by Erdős as $\binom{k}{\lfloor k/2\rfloor}/2^k$; the proof relies, incidentally, on Sperner’s theorem, which is of relevance to the ongoing polymath1 project.  (An earlier result of Littlewood and Offord gave a weaker bound of O( k^{-1/2} \log k ).)  Taking contrapositives, we obtain an inverse Littlewood-Offord theorem:

Corollary 1. If p(v_1,\ldots,v_n) \geq p, then at most O(1/p^2) of the v_1,\ldots,v_n are non-zero.

The bound is sharp in the sense that it is attained in the case when all the v_i are equal.  However, the theorem is far from sharp in other cases; if k of the v_1,\ldots,v_n are non-zero, then p(v_1,\ldots,v_n) can be as small as 2^{-k}.

Another forward Littlewood-Offord theorem in a similar spirit is by Särkőzy and Szemerédi, who showed

Theorem 2. If at least k of the v_1,\ldots,v_n are distinct, then p(v_1,\ldots,v_n) \leq O(k^{-3/2}).

(The slightly weaker bound of O( k^{-3/2} \log k ) was obtained by Erdős and Moser.)  Again, it has a contrapositive:

Corollary 2. If p(v_1,\ldots,v_n) \geq p, then the v_1,\ldots,v_n take on at most O( p^{-2/3} ) distinct values.

Again, Theorem 2 is optimal in the sense that the bound is attained when v_1,\ldots,v_n lie in an arithmetic progression (e.g. v_i = i), but is not always sharp otherwise.  There are many further forward and inverse Littlewood-Offord results; see our paper for a discussion of some of these.

In recent years it has become clearer that the concentration probability is connected to the extent to which the v_1,\ldots,v_n lie in a generalised arithmetic progression (GAP)

P = \{ n_1 w_1 + \ldots + n_d w_d: -N_i \leq n_i \leq N_i \hbox{ for } i=1,\ldots,d \};

the quantity d is known as the rank of the GAP.  For instance, an easy computation gives

Theorem 3. (Forward Littlewood-Offord)  If v_1,\ldots,v_n lie in a GAP P of rank d, then

p(n_1,\ldots,n_d) \ll_d n^{-d/2} |P|^{-1}.

Intuitively, a random sum of n vectors in P should lie in a dilate O(\sqrt{n}) P of P, which has size about n^{d/2} |P|, which leads to the stated concentration result.

One of our main results is a sort of converse to the above claim, in the regime where the concentration probability is of polynomial size:

Theorem 4. (Inverse Littlewood-Offord)  If p(v_1,\ldots,v_n) \geq n^{-A}, and \varepsilon > 0, then there exists a GAP P of rank d at most 2A that contains all but O_{A,\varepsilon}(n^{1-\varepsilon}) of the v_1,\ldots,v_n, and such that

p(n_1,\ldots,n_d) \ll_{A,\varepsilon} n^{-d/2+\varepsilon} |P|^{-1}.

Thus, Theorem 3 is sharp up to epsilon losses, and up to throwing away a small number of vectors.  One can use this theorem to deduce several earlier theorems, such as Theorem 1 and Theorem 2, except for some epsilon losses.  (It is certainly of interest to try to see how one can remove these epsilon losses; I know this problem is currently being looked at.)

In an earlier paper we had proven a weaker version of Theorem 4, in which the rank d was only bounded by O_A(1) instead of the optimal value of 2A, and the nearly-sharp n^{-d/2+\varepsilon} factor was replaced by n^{-O_A(1)}.

Our methods are purely combinatorial, based on “growing” the GAP P by a greedy algorithm.  Roughly speaking, the idea is as follows:

  1. Start with the trivial progression Q = \{0\}.  Also, pick an integer k a little bit smaller than \sqrt{n}.
  2. Call an element x of Q “bad” if adding the progression \{ -kx, \ldots, -x,0,x,\ldots, kx\} to Q significantly increases the size of Q, and “good” otherwise.
  3. If only a few of the v_1,\ldots,v_n are bad, STOP.
  4. Otherwise, if there are a lot of bad v_i, there is a way to use Hölder’s inequality to find a bad x with the property that S is much more likely to fall into a translate of Q + \{-kx,\ldots,kx\} than it is to Q.    Replace Q with this larger GAP and return to step 2.

This algorithm turns out to terminate in a bounded number of steps if the concentration probability of S was initially of polynomial size, and will trap most of the v_1,\ldots,v_n in the set of good points relating to Q, which turns out to essentially be a GAP P of size about n^{d/2} times bigger than that of Q, where d is the rank of Q.

About these ads