Exponential anticoncentration of the permanent
Preprint
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 $\varepsilon>0$ such that each entry $a_{ij}$ satisfies $\sup_{z}\Pr[a_{ij}=z]\le1-\varepsilon$ (for example, $A$ could be a uniformly random $n\times n$ matrix with $\pm1$ entries). Significantly improving previous bounds of Tao and Vu, we prove that the permanent of $A$ is exponentially anticoncentrated: there is $c_{\varepsilon}>0$ such that $\sup_{z}\Pr[\operatorname{per}(A)=z]\le\exp(-c_{\varepsilon}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 $\pm1$ entries, resolving a problem of Ingram and Razborov.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- The singularity probability of a random symmetric matrix is exponentially smallJournal of the American Mathematical Society, 2024
- On the permanent of a random symmetric matrixSelecta Mathematica, 2021
- On the values of the permanent of (0,1)-matricesLinear Algebra and its Applications, 2018
- On the singularity probability of discrete random matricesJournal of Functional Analysis, 2010
- On the permanent of random Bernoulli matricesAdvances in Mathematics, 2009
- On the singularity probability of random Bernoulli matricesJournal of the American Mathematical Society, 2007
- On random ±1 matrices: Singularity and determinantRandom Structures & Algorithms, 2005
- A Course in Combinatorics2001
- Estimates for the concentration function of combinatorial number theory and probabilityPeriodica Mathematica Hungarica, 1977
- On a lemma of Littlewood and OffordBulletin of the American Mathematical Society, 1945