Anticoncentration of independent complex Gaussian hafnians
- Field
- Topics
Problem
Do independent complex Gaussian hafnians satisfy a polynomial lower-tail bound at their root-mean-square scale? For each integer \(n\geq1\), let \(X=X^T\in\mathbb C^{2n\times2n}\) have zero diagonal. The entries above the diagonal are independent with density \(\pi^{-1}e^{-|z|^2}\). Define
where \(\mathcal M_{2n}\) is the set of perfect matchings of \(\{1,\ldots,2n\}\). Does there exist a polynomial \(p\), positive on \([1,\infty)^2\), such that
The definitions in Eq. (1) fix the ensemble and normalization. One polynomial must satisfy Eq. (2) for every \(n\) and \(\delta\).
Source
This is a precise lower-tail formulation motivated by the hafnian anticoncentration discussion following Eq. (11) of Hamilton et al. [HKS+17]. Its explicitly normalized independent-entry ensemble is an editorial refinement, rather than a verbatim numbered conjecture.
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
The matching expansion gives \(\mathbb E|\operatorname{Haf}X|^2=h_n\) because only equal matchings survive the expectation. It fixes the scale in Eq. (2), but supplies no lower-tail estimate.
For a different ensemble, Zhao’s September 2026 preprint proves a polynomial small-ball bound. If \(S\) is real symmetric with independent standard real Gaussian entries above the diagonal, Theorem 2.3 gives
\begin{equation} \sup_{z\in\mathbb R}\Pr\!\left[ |\operatorname{Haf}S-z|\leq t\sqrt{h_n}\right] \leq\min\!\left\{1,\frac{2}{\sqrt\pi}n^{3/8}t\right\}. \tag{3} \end{equation}Equation (3) settles the real symmetric analogue. It does not state a theorem for the circular complex ensemble in Eq. (1) [Zha26].
Hongru Zhao resolves the independent circular complex Gaussian lower-tail question in Theorem 2.3 and Corollary 2.5 of arXiv:2610.00112v1; the corresponding locators in the September 20 Zenodo manuscript v1.0.0 are Theorem 2.2 and Corollary 2.4 [Zhao26]. For the ensemble in Eq. (1), every \(n\geq1\), \(z\in\mathbb C\), and \(\varepsilon\geq0\) satisfy
\begin{equation} \Pr\!\left[\lvert\operatorname{Haf}X-z\rvert\leq\varepsilon\sqrt{h_n}\right] \leq\min\{1,b_n\varepsilon^2\}, \qquad b_n=\frac{(2n-1)!!}{(2n-2)!!}\leq2\sqrt{n/\pi}, \tag{4} \end{equation}with \(0!!=1\). Taking \(z=0\) and \(\varepsilon=\delta/(2n)\) in Eq. (4) gives
\begin{equation} \Pr\!\left[\lvert\operatorname{Haf}X\rvert<\frac{\delta\sqrt{h_n}}{2n}\right] \leq\frac{b_n\delta^2}{4n^2}\leq\frac{\delta^2}{2n}<\delta \qquad(n\geq1,\ 0<\delta<1). \tag{5} \end{equation}Thus the single polynomial \(p(n,u)=2nu\), positive on \([1,\infty)^2\), satisfies the exact strict inequality in Eq. (2) by Eq. (5). The prose proof obtains the independent ensemble as a fixed-dimension limit of finite transpose-Gram hafnians; diagonal entries do not affect the hafnian. GitHub #123.
Yuxuan Zhang subsequently gives a direct proof of the same bound in Eq. (4), with the same coefficient \(b_n\) and polynomial \(p(n,u)=2nu\); see Theorem 1 of his September 20 preprint, preserved in the September 26 Zenodo archive [Zhang26]. The proof bounds the expected reciprocal of the conditional variance obtained by conditioning on all edges not incident to one vertex, using Gaussian kernels and coordinate compression without assuming independence of overlapping hafnian minors. His revised research note acknowledges Zhao’s earlier resolution. Both derivations build on the Gaussian interpolation and compression method of Koehler and Leung for Ginibre permanents [KL26].
- Reported progress: Issue #92.
Comment
The archived independent complex Gaussian lower-tail question is solved by Eq. (4); the resolving manuscripts are preprints, and peer review is not established by the cited sources. Earlier-resolution credit belongs to Hongru Zhao: the bound was already stated in Eq. (3.4) of his September 11 arXiv revision [Zhao26H], and his work is accompanied by archived Lean formalization and recorded verification, with a public archive dating to September 1 [Zhao26L]. Yuxuan Zhang’s later direct proof supplies a concise derivation for the exact independent-entry ensemble. Finite transpose-Gram matrices have a different law and their theorem has additional hypotheses; the independent-ensemble resolution does not assert a bound for every Gaussian boson-sampling ensemble. Average-case computational hardness remains a separate question.
References
- [HKS+17]
- C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, "Gaussian Boson Sampling," Physical Review Letters 119, 170501 (2017).DOIarXiv
- [Zha26]
- H. Zhao, "Shifted Anticoncentration for Real Gram Hafnians and Symmetric Gaussian Hafnians," arXiv preprint (September 2026).arXiv
- [Zhao26]
- H. Zhao, "Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry," preprint (2026). Zenodo manuscript v1.0.0 with proof supplement (September 20, 2026),arXivDOI
- [Zhang26]
- Y. Zhang, "Anticoncentration of Independent Complex Gaussian Hafnians," research preprint (September 20, 2026), Theorem 1. Archived in Agentic Proofs for QIQC: Collected Manuscripts, version 1.0 (September 26, 2026), archived manuscript.DOIlink
- [KL26]
- F. Koehler and P. K. Leung, "Anticoncentration of the Permanent in Ginibre Ensembles," arXiv preprint (2026).arXiv