Let @math be i.i.d. Rademacher random variables taking values @math with probability @math each. Given an integer vector @math , its concentration probability is the quantity @math . The Littlewood-Offord problem asks for bounds on @math under various hypotheses on @math , whereas the inverse Littlewood-Offord problem, posed by Tao and Vu, asks for a characterization of all vectors @math for which @math is large. In this paper, we study the associated counting problem: How many integer vectors @math belonging to a specified set have large @math ? 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., @math for some positive constant @math ) 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 @math due to Cook; and (ii) dense row-regular @math -matrices, for which the previous best known bound is @math for any constant @math due to Nguyen.
The methods we use in this paper can be further developed in various directions. In a recent work @cite_17 , the first two named authors utilized and extended some of the ideas introduced here in order to provide the best known upper bound for the well studied problem of estimating the singularity probability of random @math -valued matrices, and in upcoming work @cite_18 , the second named author uses some of the results in this paper to study the non-asymptotic behavior of the least singular value of different models of discrete random matrices. In another upcoming work of the second named author @cite_8 , it is shown how to extend the techniques introduced here and in @cite_18 to study not-necessarily-discrete models of random matrices. We also anticipate that the techniques presented here (along with some additional combinatorial ideas) should suffice to provide an exponential-type' upper bound on the probability of singularity of the adjacency matrix of a dense random regular digraph, thereby making substantial progress towards a conjecture of Cook [Conjecture 1.7] cook2017singularity .
@cite_8 @cite_18 @cite_17
2941806982 2941595856 2890959015
This paper makes two contributions to the areas of anti-concentration and non-asymptotic random matrix theory. First, we study the counting problem in inverse Littlewood-Offord theory for general random variables: for random variables @math which are i.i.d. copies of a random variable @math (satisfying some mild hypotheses), how many integer vectors @math in a prescribed box have large @math ? Building on recent work of Ferber, Jain, Luh, and Samotij (who treated the case when @math is a Rademacher random variable), we provide significantly better bounds for this problem than those obtained using the inverse Littlewood-Offord theorems of Tao and Vu, and Nguyen and Vu. Next, we study the non-asymptotic behavior of the least singular value @math of a random @math square matrix @math with i.i.d. entries, which are only assumed to be centered with variance @math . As an application of our counting theorem, and utilizing and developing a recent work by the author, we show that for all @math , @math , where @math is an absolute constant, thereby providing a considerably simpler proof of an approximate version of an essentially optimal result due to Rebrova and Tikhomirov. An approximate Spielman-Teng theorem for the least singular value @math of a random @math square matrix @math is a statement of the following form: there exist constants @math such that for all @math , @math . The goal of this paper is to develop a simple and novel framework for proving such results for discrete random matrices. As an application, we prove an approximate Spielman-Teng theorem for @math -valued matrices, each of whose rows is an independent vector with exactly @math zero components. This improves on previous work of Nguyen and Vu, and is the first such result in a truly combinatorial' setting. Let @math denote a random symmetric @math matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values @math and @math with probability @math each). It is widely conjectured that @math is singular with probability at most @math . On the other hand, the best known upper bound on the singularity probability of @math , due to Vershynin (2011), is @math , for some unspecified small constant @math . This improves on a polynomial singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial. In this paper, improving on all previous results, we show that the probability of singularity of @math is at most @math for all sufficiently large @math . The proof utilizes and extends a novel combinatorial approach to discrete random matrix theory, which has been recently introduced by the authors together with Luh and Samotij.