A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{ -1,1\}$ is singular with probability $\Theta\big( n^2 2^{ -n} \big)$. In this paper we prove that the probability of this event is at most $\exp\big( - \Omega( \sqrt{ n} ) \big)$, improving the best known bound of $\exp\big( - \Omega( n^{ 1/4} \sqrt{ \log n} ) \big)$, 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.
Categories: math.CO math.PR