Exponential anticoncentration of the permanent

Abstract

Let $A\in {\mathbb{R}}^{n\times n}$ be a random matrix with independent entries, and suppose that the entries are "uniformly anticoncentrated" in the sense that there is a constant $\epsilon >0$ such that each entry $a_{ij}$ satisfies ${\sup }_z\mathrm{Pr}[a_{ij}=z]\le 1-\epsilon$ (for example, $A$ could be a uniformly random $n\times n$ matrix with $\pm 1$ entries). Significantly improving previous bounds of Tao and Vu, we prove that the permanent of $A$ is exponentially anticoncentrated: there is $c_{\epsilon }>0$ such that ${\sup }_z\mathrm{Pr}[\mathrm{per}(A)=z]\le \exp (-c_{\epsilon }n)$. Our proof also works for the determinant, giving an alternative proof of a classical theorem of Kahn, Komlós and Szemerédi. As a consequence, we see that there are at least exponentially many different permanents of $n\times n$ matrices with $\pm 1$ entries, resolving a problem of Ingram and Razborov.

12 pages. Comments welcome!