Singularity of sparse Bernoulli matrices (Q2130504): Difference between revisions

The main purpose of this paper is to develop methods capable of capturing the singularity probability with a sufficient precision. The invertibility of discrete random matrices has received significant attention from many mathematicians. The classical problem in this direction -- estimating the singularity probability of a square random matrix \(B_n\) with independent and identically distributed (i.i.d.) \(\pm1\) entries -- was first considered by \textit{J. Komlos} [Stud. Sci. Math. Hung. 2, 7--21 (1967; Zbl 0153.05002)]. He showed that \(\mathbb{P}\{M_n \text{ is singular}\} = o_n(1)\), where \(o_n(1)\) is a quantity which tends to zero as \(n\to\infty\). Later, the bound \(\mathbb{P}\{M_n \text{ is singular}\} \le 0.999^n\) was obtained by \textit{J. Kahn} et al. [J. Am. Math. Soc. 8, No. 1, 223--240 (1995; Zbl 0829.15018)]. The upper bound was sequentially improved to \(0.939^n\) in [\textit{T. Tao} and \textit{V. Vu}, Random Struct. Algorithms 28, No. 1, 1--23 (2006; Zbl 1086.60008)] and \((3/4+o_n(1))^n\) by \textit{T. Tao} and \textit{V. Vu} [J. Am. Math. Soc. 20, No. 3, 603--628 (2007; Zbl 1116.15021)], and to \((1/{\sqrt 2}+o_n(1))^n\) by \textit{J. Bourgain} et al. [J. Funct. Anal. 258, No. 2, 559--603 (2010; Zbl 1186.60003)]. An old conjecture stating that \(\mathbb{P}\{M_n {\text{ is singular}}\} = (1/2+o_n(1))^n\) was resolved in [\textit{K. Tikhomirov}, Ann. Math. (2) 191, No. 2, 593--634 (2020; Zbl 1458.15023)]. The main result of the paper can be formulated as follows. Theorem. There is a universal constant \(C\ge 1\) with the following property. Let \(n\ge 1\), and let \(M_n\) be an \(n\times n\) random matrix such that the entries of \(M_n\) are i.i.d. Bernoulli \(p\), with \(p=(p_n)\) satisfying \[ C \ln n \le np \le C^{-1}n. \] Then, \[ \mathbb{P}\{M_n\text{ is singular}\}=\left(2+o_n(1)\right)n(1-p)^n. \] The authors provide the corresponding upper and lower bounds for the smallest singular value \(M_n\) too.