Permanent anticoncentration for complex Gaussian matrices
- Field
- Topics
Problem
Do complex Gaussian permanents satisfy a polynomial lower-tail bound at their root-mean-square scale? For each integer \(n\geq1\), let \(X\in\mathbb C^{n\times n}\) have independent entries with density \(\pi^{-1}e^{-|z|^2}\). Write \(S_n\) for the permutations of \(\{1,\ldots,n\}\) and define
Does there exist a polynomial \(p\), positive on \([1,\infty)^2\), such that the permanent in Eq. (1) satisfies
The same polynomial must work for every pair \((n,\delta)\) in Eq. (2).
Source
Aaronson and Arkhipov state this as Conjecture 6 in Section 1.2.3 of their arXiv version [AA13].
Progress
Koehler and Leung’s Theorem 1.1 proves that a universal constant \(C>0\) satisfies
\begin{equation} \sup_{z\in\mathbb C}\Pr\!\left[ |\operatorname{Per}X-z|\leq t\sqrt{n!}\right]\leq Cnt^2 \qquad(t>0). \tag{3} \end{equation}Equation (3) implies Eq. (2): take \(p(n,y)=Kny\) with \(K^2>C\). The resolving result is a July 2026 preprint [KL26].
The earlier Theorem 54 of Aaronson and Arkhipov gives only \(\Pr[|\operatorname{Per}X|^2\geq\theta n!]>(1-\theta)^2/(n+1)\) for \(0<\theta<1\). That moment argument guarantees a fraction of large values; it does not alone control the small-value tail [AA13].
Comment
The archived anticoncentration question is resolved by a preprint; no journal publication is asserted. It is distinct from the Permanent-of-Gaussians hardness conjecture. Combining this result with Aaronson–Arkhipov Theorem 7 makes their additive squared-permanent and multiplicative permanent estimation tasks polynomial-time equivalent [AA13]. It does not prove either task hard.