Let be i.i.d.\ Rademacher random variables taking values with probability each. Given an integer vector $\boldsymbol{a} = (a_1, \dotsc, a_n)$, its concentration probability is the quantity $\rho(\boldsymbol{a}):=\sup_{x\in \Z}\Pr(\epsilon_1 a_1+\dotsb+\epsilon_n a_n = x)$. The Littlewood--Offord problem asks for bounds on under various hypotheses on , whereas the \emph{inverse} Littlewood--Offord problem, posed by Tao and Vu, asks for a characterization of all vectors for which is large. In this paper, we study the associated counting problem: How many integer vectors belonging to a specified set have large ? The motivation for our study is that in typical applications, the inverse Littlewood--Offord theorems are only used to obtain such counting estimates. Using a more direct approach, we obtain significantly better bounds for this problem than those obtained using the inverse Littlewood--Offord theorems of Tao and Vu and of Nguyen and Vu. Moreover, we develop a framework for deriving upper bounds on the probability of singularity of random discrete matrices that utilizes our counting result. To illustrate the methods, we present the first `exponential-type' (i.e., for some positive constant ) upper bounds on the singularity probability for the following two models: (i) adjacency matrices of dense signed random regular digraphs, for which the previous best known bound is due to Cook; and (ii) dense row-regular -matrices, for which the previous best known bound is for any constant due to Nguyen. This is joint work with Asaf Ferber, Vishesh Jain and Wojciech Samotij.
The counting problem in inverse Littlewood-Offord theory