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.