On the singularity of random symmetric matrices

Abstract

A well-known conjecture states that a random symmetric $n\times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta \left(n^2{2}^{-n}\right)$. In this paper we prove that the probability of this event is at most $\exp (-\Omega (\sqrt{n}))$, improving the best known bound of $\exp (-\Omega (n^{1/4}\sqrt{\log n}))$, which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood-Offord theorem in ${\mathbb{Z}}_p^n$ that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.

16 pages, plus a 10-page appendix