Anticoncentration versus the number of subset sums

A major tool in probabilistic combinatorics is the so-called concentration of measure phenomenon, the idea that a sum of a large number of random variables that are sufficiently small and sufficiently independent (where these conditions can be interpreted in a number of ways) is strongly concentrated around its mean. However, for some applications, an inequality in the reverse direction is needed. A major example of this is the problem of finding upper bounds for the probability that a random $n\times n$ matrix $A$ with $\pm 1$ entries is singular: if $v$ is a vector in $\mathbb R^n$, then the probability that it belongs to the kernel of $A$ is $p(v)^n$, where $p(v)$ is the probability that $\sum_i\epsilon_iv_i=0$ for a random $\epsilon\in\{-1,1\}^n$. One would like this probability to be small, and more generally one would like the probability that $\sum_i\epsilon_iv_i$ takes any specific value to be small, which implies a lower bound on how concentrated this random variable can be.

A classic anticoncentration result is the Littlewood-Offord theorem, which states (for $n$ even) that if $|v_i|\geq 1$ for every $i$, then the probability that $|\sum_i\epsilon_iv_i|<1$ is at most $2^{-n}\binom n{n/2}$. More precisely, Littlewood and Offord proved a slightly weaker bound and Erdős obtained the bound just given, using Sperner’s theorem. (Later Kleitman showed that the same was true if the $v_i$ are vectors in a normed space and $|.|$ is the norm.)

In an important contribution to the problem about singularity of random matrices, Terence Tao and Van Vu introduced the notion of inverse Littlewood-Offord theorems. That is, they proved structural results about vectors $v$ for which the probability that $\sum_i\epsilon_iv_i=0$ is large, where “large” typically meant at least $n^{-A}$ for some fixed $A$. It turns out that such vectors must have significant arithmetic structure, such as having almost all their coordinates belonging to a low-dimensional and not too large generalized arithmetic progression. Since then, a significant literature has developed on this general theme.

This paper makes an interesting contribution to this theme, looking at a much weaker definition of “large” and obtaining a correspondingly weaker conclusion. The authors consider vectors $v$ for which the probability that $\sum_i\epsilon_iv_i$ takes a given value is at least $2^{-\epsilon n}$ for some small $\epsilon$. (Actually, they consider 01 sums but this is equivalent.) This condition is too weak for there to be any hope, given current mathematical technology, of relating the coordinates of $v$ to a generalized arithmetic progression, so instead the authors look at a less structural arithmetic property, namely the number of possible sums of the form $\sum_{i\in A}v_i$, which they show can be at most $2^{C\sqrt\epsilon n}$ for some constant $C$. Moreover, there is no assumption that $n$ is sufficiently large: the result holds for all $\epsilon$ in the range $[n^{-2},1]$ (and outside this range it is true for trivial reasons). This greatly improves on an earlier bound of $2^{\delta n}$ due to Nederlof, Pawlewicz, Swennenhuis, and Węgrzycki, where $\delta$ had a logarithmic dependence on $\epsilon$. The authors conjecture that the true dependence is linear.