2020/11/03 by Jain, Vishesh, Sah, Ashwin, Sawhney, Mehtaab · 1 citation
#FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2011.02344
We show that for an n× n random symmetric matrix An, whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable ξ with mean 0 and variance 1, ℙ[sn(An) ≤ ε/√(n)] ≤ Oξ(ε1/8 + exp(-Ωξ(n1/2))) for all ε≥ 0. This improves a result of Vershynin, who obtained such a bound with n1/2 replaced by nc for a small constant c, and 1/8 replaced by (1/8) + η (with implicit constants also depending on η> 0). Furthermore, when ξ is a Rademacher random variable, we prove that ℙ[sn(An) ≤ ε/√(n)] ≤ O(ε1/8 + exp(-Ω((logn)1/4n1/2))) for all ε≥ 0. The special case ε= 0 improves a recent result of Campos, Mattos, Morris, and Morrison, which showed that ℙ[sn(An) = 0] ≤ O(exp(-Ω(n1/2))). The main innovation in our work are new notions of arithmetic structure -- the Median Regularized Least Common Denominator and the Median Threshold, which we believe should be more generally useful in contexts where one needs to combine anticoncentration information of different parts of a vector.