What’s new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

# A sharp inverse Littlewood-Offord theorem

16 February, 2009 in math.CO, math.PR, paper | Tags: generalised arithmetic progressions, Littlewood-Offord theorems, random walks, Van Vu

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.

### Recent Comments

Sandeep Murthy on An elementary non-commutative…
Luqing Ye on 245A, Notes 2: The Lebesgue…
Frank on Soft analysis, hard analysis,…
andrescaicedo on Soft analysis, hard analysis,…
Richard Palais on Pythagoras’ theorem
The Coffee Stains in… on Does one have to be a genius t…
Benoît Régent-Kloeck… on (Ingrid Daubechies) Planning f…
Luqing Ye on 245B, Notes 7: Well-ordered se…
Luqing Ye on 245B, Notes 7: Well-ordered se…
Arjun Jain on 245B, Notes 7: Well-ordered se…
%anchor_text% on Books
Luqing Ye on 245B, Notes 7: Well-ordered se…
Arjun Jain on 245B, Notes 7: Well-ordered se…
Luqing Ye on 245A, Notes 2: The Lebesgue…
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 56, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9144031405448914, "perplexity_flag": "middle"}