The counting problem in inverse Littlewood-Offord theory, and its applications to discrete random matrix theory

The counting problem in inverse Littlewood-Offord theory, and its applications to discrete random matrix theory

-
Vishesh Jain, MIT
Fine Hall 401

Let $\epsilon_1,\dots,\epsilon_n$ be i.i.d. Rademacher random variables taking on the values $\pm 1$ with probability $1/2$ each. Given an integer vector $\boldsymbol{a} = (a_1,\dots,a_n)$, we define the concentration probability as $\rho(\boldsymbol{a}):=\sup_{x\in \Z}\Pr[\epsilon_1 a_1+\dots+\epsilon_n a_n = x]$. The Littlewood-Offord problem asks for bounds on $\rho(\boldsymbol{a})$ in terms of various hypothesis on $\boldsymbol{a}$, whereas the \emph{inverse} Littlewood-Offord problem of Tao and Vu asks for a characterization of $\boldsymbol{a}$ given that $\rho(\boldsymbol{a})$ is large. In this talk, I will isolate the counting problem in inverse Littlewood-Offord theory, which asks \emph{how many} vectors $\boldsymbol{a}$ belonging to a specified set of integer vectors have large $\rho(\boldsymbol{a})$. -- in typical applications, especially to discrete random matrix theory, the inverse Littlewood-Offord theorems are only used via such counting corollaries. I will discuss how to obtain significantly better bounds for this problem than can be obtained using the inverse Littlewood-Offord theorems of Tao and Vu, and Nguyen and Vu using a novel combinatorial approach. As an application of this general framework, I will also discuss how to obtain new bounds for the singularity problem for several well-studied models of discrete random matrices in a unified manner, thereby improving previous bounds of Cook, Nguyen, and Vershynin.

Based on joint work with Asaf Ferber (MIT), Kyle Luh (Harvard), and Wojciech Samotij (Tel Aviv University).