Super-exponential decay of the zero-permanent probability
For $n \ge 1$ let $A_n$ be an $n \times n$ random matrix with independent entries, each equal to $1$ or $-1$ with probability $1/2$, and let $\operatorname{per}$ denote the permanent. Vu conjectured that $\Pr(\operatorname{per} A_n = 0)$ is super-exponentially small in $n$. Tao and Vu proved $\Pr(\operatorname{per} A_n = 0) \le n^{-c}$ for a constant $c > 0$ and all large $n$, and Hunter, Kwan and Sauermann proved $\Pr(\operatorname{per} A_n = x) \le e^{-cn}$ for an absolute constant $c > 0$ and every $x \in \mathbb{R}$.
Problem. Is it true that for every $c > 0$ there is an $N_c$ such that $$\Pr(\operatorname{per} A_n = 0) \le e^{-cn} \qquad \text{for every } n \ge N_c,$$ that is, $\lim_{n \to \infty} \Pr(\operatorname{per} A_n = 0)^{1/n} = 0$?
Source: Vu (2021; arXiv 2020), Conjecture 6.12, which asks that the probability be super-exponentially small; made quantitative by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- anticoncentration, OpenProblemsInNLA, permanents, random matrices
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{vu2021,
author = {Vu, Van H.},
title = {Recent progress in combinatorial random matrix theory},
journal = {Probab. Surv.},
volume = {18},
year = {2021},
pages = {179--200},
doi = {10.1214/20-PS346},
eprint = {2005.02797},
archivePrefix = {arXiv},
}
@article{tao2009,
author = {Tao, Terence and Vu, Van},
title = {On the permanent of random {B}ernoulli matrices},
journal = {Adv. Math.},
volume = {220},
number = {3},
year = {2009},
pages = {657--669},
doi = {10.1016/j.aim.2008.09.006},
eprint = {0804.2362},
archivePrefix = {arXiv},
}
@misc{hunter2025,
author = {Hunter, Zach and Kwan, Matthew and Sauermann, Lisa},
title = {Exponential anticoncentration of the permanent},
year = {2025},
eprint = {2509.22577},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra16,
author = {Townsend, Alex},
title = {{RA-16}: Super-exponential decay of the zero-permanent probability},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RA-16/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00173, "Super-exponential decay of the zero-permanent probability", clopen.solutions.