Anticoncentration of the Permanent in Ginibre Ensembles

Frederic Koehler; Pui Kuen Leung

Anticoncentration of the Permanent in Ginibre Ensembles

T0 review · 0 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the normalized Gaussian permanent has a radial density bounded by O(n^{(β+2)/4}) over the reals, complexes, and quaternions, and in the complex case obtains sup_z P(|per G_n − z| ≤ ε√n!) ≤ nε², resolving the Permanent

desk verdict A convincing resolution of the Aaronson–Arkhipov permanent anticoncentration conjecture, built on a genuinely new Laplace-transform comparison that holds up under scrutiny. read the letter →

arxiv 2607.20329 v1 pith:VPMWYXFB submitted 2026-07-22 math.PR cs.CCmath-phmath.MPquant-ph

Frederic Koehler , Pui Kuen Leung This is my paper · ORCID

classification math.PRcs.CCmath-phmath.MPquant-ph MSC 60B2060E1515A15

keywords permanentanticoncentrationGinibreensembleLaplace-transformordersmall-ballprobabilityquaternionicStudydeterminantrandommatrix

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the normalized Gaussian permanent—with row-ordered multiplication for real, complex, and quaternionic entries—has a density whose maximum grows only polynomially in n, as n^{(β+2)/4} where β is the real dimension of the field. In the complex case this gives sup_z P(|per G_n − z| ≤ ε√n!) ≤ min{1, nε²}, which resolves the Permanent Anticoncentration Conjecture for BosonSampling. The core is a comparison of the squared permanent with the squared determinant (or Study determinant for quaternions) in Laplace-transform order, showing the permanent is at least as spread out as the determinant at all scales. A separate stability result extends the same polynomial bound to arbitrary independent Gaussian perturbations of the matrix, proving a stronger form of a previously conjectured gentle-perturbation bound.

What carries the argument

The load-bearing object is the Laplace-transform order of nonnegative random variables (U ⪯_Lt V when E e^{-sU} ≥ E e^{-sV} for all s ≥ 0) and its matrix-variate extension for outer products of random vectors. The main technical tool is the Fourier coordinate-compression inequality (Proposition 3.5): for the permanental cofactor vector C determined by an (n−1)×n Gaussian matrix, the characteristic function φ_n(z) = E e^{i(z,C)_R} is always nonnegative and is no larger than its value at the one-coordinate vector ||z||₂ e₁. This one-sided replacement for the determinant's exact spherical invariance lets the permanent's cofactor vector inherit the determinant's factorial-scale spreading, transf

What would settle it

A direct numerical check of Proposition 3.5 for K = H at n = 3: generate many standard quaternionic Gaussian (2×3) matrices B, compute the permanental cofactor entries C_j = per_H(B_{−j}), and estimate E e^{i(z,C)_R} versus E e^{i(||z||₂ e₁,C)_R} for a test vector z with two nonzero equal-weight coefficients; if the former exceeds the latter by more than sampling error, the compression inequality fails and the density bound loses its support.

Watch

Extended reading notes

Core claim

The central discovery is that permanent anticoncentration can be reduced to a one-sided comparison between the permanent and determinant cofactor vectors in Laplace-transform order. For an (n−1)×n Gaussian matrix B, the signed determinant cofactor vector is spherically invariant and obeys an exact recursion governed by a product of independent gamma variables; the paper shows, through a new Fourier coordinate-compression inequality, that the permanental cofactor vector is at least as well spread out in Laplace order. From this, the squared permanent Laplace-dominates the squared determinant, and the density of the normalized permanent at zero is bounded by that of a known gamma benchmark, yi

Load-bearing premise

The entire argument rests on the Fourier coordinate-compression inequality—that for the random cofactor vector of a Gaussian matrix, every linear test statistic has characteristic function bounded between zero and the value for a single coordinate of equal Euclidean norm—and this must hold without obstruction in the noncommutative quaternionic case.

Editorial extensions

If this is right

For K = C the small-ball probability satisfies sup_z P(|per G_n − z| ≤ ε√n!) ≤ min{1, nε²}, settling the Permanent Anticoncentration Conjecture.
For every K ∈ {R,C,H}, the density of the normalized permanent at zero is bounded by κ_{n,β} ≍ n^{(β+2)/4}, giving polynomial small-ball bounds with exponent (β+2)/4 in all three fields.
For every deterministic A ∈ R^{n×n}, the perturbed permanent per(G_n^R + A)/√n! has density bounded by n^{3/4}; hence sup_w P(|per(G_n^R + A) − w| ≤ ε√n!) ≲ n^{3/4}ε, proving a stronger version of the gentle-perturbation conjecture.
The logarithmic asymptotics log|per_K G_n^K| = 1/2 log(n!) + O_P(log n) follow, refining the known typical-scale result to logarithmic error.
The comparison also gives Sdet(G_H^n)^2 ⪯_Lt |per_H G_H^n|² for the quaternionic Study determinant, extending anticoncentration to the symplectic Ginibre ensemble.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: The Fourier compression inequality is a one-sided analog of spherical invariance; if it holds for other row distributions satisfying the projection condition of Appendix C, the same Laplace-order method would transfer anticoncentration to non-Gaussian row models at the exact second-moment scale.
Editorial inference: The explicit nε² constant in the complex case is likely not optimal at small ε: the proof bounds the permanent's density by a gamma benchmark from the determinant, and comparing with the permanent's own moments might improve the linear n factor.
Editorial inference: Uniformity over centers z means the result controls not just |per G_n| but the full small-ball behavior over the plane, which is the property needed for zero-counting and continuity estimates in average-case complexity arguments.
Editorial inference: The method suggests a general recipe for anticoncentrating any symmetric multilinear polynomial of Gaussian entries: find a spherically invariant benchmark and prove Fourier compression for its cofactor vector.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is real: this paper proves the permanent anticoncentration conjecture for complex Ginibre matrices, with the sharp nε² small-ball bound, and also covers the real and quaternionic cases plus a perturbed-permanent conjecture. That is a major result, and the proof is more than just a clever trick. The central mechanism—Fourier coordinate compression for permanental cofactor vectors, feeding a Laplace-transform comparison against a gamma benchmark—is genuinely new as far as I can tell. The chain from Proposition 3.5 through the cofactor induction to the density bound is explicit and internally consistent. The reader's strongest claim is correct, and the stress-test note's verification of the quaternionic two-column expansion makes sense: the real-bilinear structure rescues the argument where noncommutativity might have broken it.

What the paper does especially well is that it gives a usable, non-asymptotic bound with no fitted parameters. The benchmark is an explicit gamma product, the comparison is proved from Gaussian structure rather than assumed, and the final small-ball estimate follows from a monotone limit. The appendix showing that the Laplace comparison cannot be strengthened to stochastic or convex order is also a good sign: it demonstrates genuine understanding of the order's limits instead of overselling it.

Soft spots are minor relative to the main result. I did not machine-check the quaternionic algebra, and the paper leaves a few degeneracies implicit (e.g., C=0 in the two-coordinate step). But these are technical gaps, not conceptual ones; the stress-test note addresses the main worry about Proposition 3.5, and the argument holds together on reading. The notation calling (·,·)_R the Euclidean inner product is harmless, as the note says. The self-citations to [KL26] are for applications and definitions, not load-bearing, so they don't bother me.

The only real limitation I see is that the paper is about Gaussian permanents, not Bernoulli or other discrete models. That is the hard case for BosonSampling, so it is a substantive gap relative to the full AA program, but it is not a flaw in this paper—the authors are explicit about what they prove. The typical-scale results of Tao–Vu and the exponential anticoncentration of Hunter–Kwan–Sauermann remain separate, and this paper complements rather than replaces them.

Who should read it: anyone working on anticoncentration, random matrix theory, or quantum complexity lower bounds. It deserves a serious referee. I would send it out and expect acceptance after a check of the quaternionic computations and some cleanup of the edge cases.

Referee Report

0 major / 5 minor

Summary. The paper proves a Gaussian permanent anticoncentration theorem for the three Ginibre ensembles over R, C, and H. For a standard K-Ginibre matrix G_n^K with β=dim_R K, the normalized row-ordered permanent W_n^K=per_K G_n^K/√(n!) is shown to have a radial density p_n^K with sup norm O(n^{(β+2)/4}), yielding the uniform small-ball estimate sup_z P(|W_n^K-z|≤ε) = O(n^{(β+2)/4} ε^β). In the complex case this gives sup_z P(|per G_n-z|≤ε√(n!)) ≤ min{1, nε²}, resolving the Aaronson–Arkhipov Permanent Anticoncentration Conjecture and, via the perturbation result in Section 4, a conjecture of Bouland et al. The proof is built on a Laplace-transform comparison between the squared permanent and a gamma benchmark arising from the determinant (or Study determinant for H). The main technical innovation is a Fourier coordinate compression for permanental cofactor vectors (Proposition 3.5), which is fed into an induction (Theorem 3.6) that yields the matrix and scalar Laplace comparisons. The density bound follows from an approximate-identity argument using the explicit Laplace transform of the gamma benchmark.

Significance. If correct, this is a substantial resolution of a well-known open problem. The proof is explicit and structurally informative: it identifies the exact gamma benchmark, proves the comparison in Laplace-transform order, and then extracts a uniform density bound rather than only a centered lower-tail estimate. It also extends the result to real and quaternionic Ginibre ensembles and to arbitrary deterministic additive perturbations, giving a stronger form of the Bouland–Datta–Fefferman–Hernández conjecture. The paper ships no fitted parameters, and the main computations are checkable by hand. The appendices honestly delineate the limits of the method, showing that stronger stochastic/convex orders fail.

minor comments (5)

[§1.2] The sentence that (·,·)_R is the ordinary Euclidean inner product on R^{βm} is false for K=C and K=H. For example, with K=C, Re(zw)=Re(z\bar{w}) fails when w is not real. The subsequent Fourier and Laplace identities are still valid because the map z↦Re(z w) is a nondegenerate real bilinear form; after an orthogonal change of coordinates it becomes the standard real inner product. Please correct this statement and add a remark where Lemma 3.4 is applied in Theorem 3.6, so that the translation to the standard Fourier inversion formula is explicit.
[§3.2, proof of Prop. 3.5] In the lower-bound paragraph, the expansion along the last Gaussian row is written as ∑_j D_j h_j. Since the last row is the final factor in the row-ordered permanent, the correct expression is ∑_j h_j D_j; the real parts coincide because Re(qr)=Re(rq), so the argument is unaffected. A one-sentence clarification would avoid confusion.
[§4.1] The quaternionic case of Theorem 4.1 is deferred to Subsection C.2, but the proof of (29) for K∈{R,C} is written before the reader is told that the H case is handled later. Add a forward pointer at the start of the proof, as is done for Theorem C.1.
[Appendix A] The table of Wick-averaged values A,B,C is terse. A short sentence indicating how the quaternionic entries are computed (e.g., by writing each quaternionic entry as a 4-vector and using the real Gaussian Wick formula) would improve reproducibility, especially because the Q_Δ entry C=336 differs from the permanent's C=366.
[§C.1, Eq. (35)] The projection condition γ_{1,β} ≤_{Lt} |R_i c|²/(σ_i²∥c∥²) should explicitly exclude c=0. This is harmless but should be stated.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the permanent benchmark and Laplace comparison are independently derived.

full rationale

The central claim is not circular. Theorem 1.1 follows from the Laplace comparison Δ_n^K ≤_{Lt} X_n^K, where Δ_n^K is the determinant/Study-determinant benchmark whose exact gamma-product law is derived independently in Propositions 2.1 and 2.3. The comparison is proved by an induction in Theorem 3.6 whose load-bearing inputs are Proposition 3.5 (Fourier coordinate compression, established directly from conditioning on a Gaussian row and a two-column bilinear expansion) and Lemma 3.4 (Fourier domination implies Laplace domination). No parameter is fitted to the target bound, and no normalization from the claimed small-ball estimate is fed back into the derivation. The only self-citations, e.g. [KL26], appear in applications and context rather than as load-bearing premises. Any technical concerns about individual lemmas would be correctness questions, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central derivation has no fitted constants; the only inputs are the Gaussian law and cited quaternionic determinant background. The gamma benchmark is explicit, so the result is not tuned to match PACC.

assumptions (4)

domain assumption Standard K-Gaussian entries have independent real N(0,1/β) coordinates for β=dim_R K; this fixes the law of the matrix and is the domain assumption for all results.
Definition in Section 1; all subsequent Gaussian integrals use this.
standard math Study determinant facts from [CDL00, Asl96]: multiplicativity, triangular formula Sdet(QR)=∏ r_jj, and relation to singular values.
Used in Proposition 2.3 and Appendix B; not re-derived in the paper.
standard math Gaussian integration standard identities: centered Gaussian characteristic function, orthogonal change of variables, Cramér–Wold theorem.
Invoked in Lemmas 3.1–3.4 and Proposition 3.5.
standard math Laplace-transform order is a known partial order; preservation under multiplication by a common independent nonnegative factor is taken as standard. References [AKP91, SS07].
Used in Theorem 1.5 and Section 3.4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Anticoncentration of the Permanent in Ginibre Ensembles." pith.science (2026). https://pith.science/paper/VPMWYXFB

@misc{pith2026260720329,
  author       = {Pith},
  title        = {Pith review of: Anticoncentration of the Permanent in Ginibre Ensembles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VPMWYXFB}},
  note         = {Machine review of arXiv:2607.20329}
}

abstract

Let $\mathbb{K}\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$, put $\beta=\dim_{\mathbb{R}}\mathbb{K}$, and let $G_n^{\mathbb{K}}$ be an $n\times n$ matrix with i.i.d. standard $\mathbb{K}$-Gaussian entries, namely a standard $\mathbb{K}$-Ginibre matrix. We prove that the normalized row-ordered permanent $W_n^{\mathbb{K}}=\operatorname{per}_{\mathbb{K}}G_n^{\mathbb{K}}/\sqrt{n!}$ has a radial density $p_n^{\mathbb{K}}$ satisfying $\|p_n^{\mathbb{K}}\|_\infty=p_n^{\mathbb{K}}(0)\lesssim_\beta n^{(\beta+2)/4}$ and $\sup_{z\in\mathbb{K}}\mathbb{P}(|W_n^{\mathbb{K}}-z|\leq\varepsilon)\lesssim_\beta n^{(\beta+2)/4}\varepsilon^\beta$. In particular, for $\mathbb{K}=\mathbb{C}$, this resolves the Permanent Anticoncentration Conjecture of Aaronson and Arkhipov. The proof compares the squared Gaussian permanent with the squared (Study) determinant in Laplace-transform order.

Figures

Figures reproduced from arXiv: 2607.20329 by the authors.

**Figure 1.** displays the same qualitative separation over R, C, and H: the distribution functions cross, while the Laplace-transform differences retain the same sign. Indeed, for nonnegative U, V , Ee −sU − Ee −sV = s Z ∞ 0 e −st FU (t) − FV (t) dt, so the exponential kernel averages over the crossing rather than comparing the CDFs pointwise. 10 −2 10 −1 10 0 10 1 t -0.001 0.000 0.001 0.002 0.003 0.004 0.005 0.006 FΔ3 (t) − F… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references

[1]

Theory of Computing , volume =

Aaronson, Scott and Arkhipov, Alex , title =. Theory of Computing , volume =. 2013 , doi =

2013
[2]

Physical Review A , volume =

Chabaud, Ulysse and Douce, Tom and Markham, Damian and van Loock, Peter and Kashefi, Elham and Ferrini, Giulia , title =. Physical Review A , volume =. 2017 , doi =

2017
[3]

2010 , note =

Tao, Terence , title =. 2010 , note =

2010
[4]

2026 , eprint =

Koehler, Frederic and Leung, Pui Kuen , title =. 2026 , eprint =

2026
[5]

2021 , eprint =

Nezami, Sepehr , title =. 2021 , eprint =

2021
[6]

Lundow, P. H. and Markstr. Efficient Computation of Permanents, with Applications to. Journal of Computational Physics , volume =. 2022 , doi =

2022
[7]

Mathematical Research Letters , volume =

Carbery, Anthony and Wright, James , title =. Mathematical Research Letters , volume =. 2001 , doi =

2001
[8]

Exponential Improvements to the Average-Case Hardness of

Bouland, Adam and Datta, Ishaun and Fefferman, Bill and Hern. Exponential Improvements to the Average-Case Hardness of. 66th Annual Symposium on Foundations of Computer Science (. 2025 , eprint =

2025

Show all 32 references

[9]

2025 , eprint =

Hunter, Zach and Kwan, Matthew and Sauermann, Lisa , title =. 2025 , eprint =

2025
[10]

Linear Algebra and its Applications , volume =

Ingram, DeVon and Razborov, Alexander , title =. Linear Algebra and its Applications , volume =. 2026 , doi =

2026
[11]

Advances in Mathematics , volume =

Tao, Terence and Vu, Van , title =. Advances in Mathematics , volume =
[12]

2021 , eprint =

Kwan, Matthew and Sauermann, Lisa , title =. 2021 , eprint =

2021
[13]

, title =

Juskevicius, Tomas and Lee, James D. , title =. 2015 , eprint =

2015
[14]

, title =

Brascamp, Herm Jan and Lieb, Elliott H. , title =. Advances in Mathematics , volume =. 1976 , doi =

1976
[15]

and Thomas, Joy A

Dembo, Amir and Cover, Thomas M. and Thomas, Joy A. , title =. IEEE Transactions on Information Theory , volume =. 1991 , doi =

1991
[16]

, title =

Forrester, Peter J. , title =. 2010 , isbn =

2010
[17]

The Mathematical Intelligencer , volume =

Aslaksen, Helmer , title =. The Mathematical Intelligencer , volume =. 1996 , doi =

1996
[18]

Electronic Journal of Linear Algebra , volume =

Cohen, Nir and De Leo, Stefano , title =. Electronic Journal of Linear Algebra , volume =. 2000 , doi =

2000
[19]

Journal of Computer and System Sciences , volume =

Chien, Steve and Rasmussen, Lars Eilstrup and Sinclair, Alistair , title =. Journal of Computer and System Sciences , volume =. 2003 , doi =

2003
[20]

Journal of Mathematical Physics , volume =

Ginibre, Jean , title =. Journal of Mathematical Physics , volume =. 1965 , doi =

1965
[21]

Engels, Christian and Rao, B. V. Raghavendra , title =. Discrete Applied Mathematics , volume =. 2020 , doi =

2020
[22]

Proceedings of the 42nd ACM Symposium on Theory of Computing , pages =

Arvind, Vikraman and Srinivasan, Srikanth , title =. Proceedings of the 42nd ACM Symposium on Theory of Computing , pages =. 2010 , doi =

2010
[23]

On Wishart Distribution: Some Extensions , journal =

D. On Wishart Distribution: Some Extensions , journal =. 2011 , doi =

2011
[24]

Journal of Applied Probability , volume =

Alzaid, Abdulhamid and Kim, Jee Soo and Proschan, Frank , title =. Journal of Applied Probability , volume =. 1991 , doi =

1991
[25]

George , title =

Shaked, Moshe and Shanthikumar, J. George , title =. 2007 , doi =

2007
[26]

A Useful Ageing Property Based on the Laplace Transform , journal =

Klefsj. A Useful Ageing Property Based on the Laplace Transform , journal =. 1983 , doi =

1983
[27]

Lin, Gwo Dong , title =. Sankhy
[28]

Journal of Applied Probability , volume =

Klar, Bernhard , title =. Journal of Applied Probability , volume =. 2002 , doi =

2002
[29]

Applications of Stochastic Ordering to Wireless Communications , journal =

Tepedelenlio. Applications of Stochastic Ordering to Wireless Communications , journal =. 2011 , doi =

2011
[30]

Miscellaneous Results Related to the

Genest, Christian and Ouimet, Fr. Miscellaneous Results Related to the. Journal of Mathematical Analysis and Applications , volume =. 2023 , doi =

2023
[31]

Genest, Christian and Ouimet, Fr. On the. Electronic Journal of Probability , volume =. 2024 , doi =

2024
[32]

and Sokal, Alan D

Scott, Alexander D. and Sokal, Alan D. , title =. Acta Mathematica , volume =. 2014 , doi =

2014

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

Theory of Computing , volume =

Aaronson, Scott and Arkhipov, Alex , title =. Theory of Computing , volume =. 2013 , doi =

2013

[2] [2]

Physical Review A , volume =

Chabaud, Ulysse and Douce, Tom and Markham, Damian and van Loock, Peter and Kashefi, Elham and Ferrini, Giulia , title =. Physical Review A , volume =. 2017 , doi =

2017

[3] [3]

2010 , note =

Tao, Terence , title =. 2010 , note =

2010

[4] [4]

2026 , eprint =

Koehler, Frederic and Leung, Pui Kuen , title =. 2026 , eprint =

2026

[5] [5]

2021 , eprint =

Nezami, Sepehr , title =. 2021 , eprint =

2021

[6] [6]

Lundow, P. H. and Markstr. Efficient Computation of Permanents, with Applications to. Journal of Computational Physics , volume =. 2022 , doi =

2022

[7] [7]

Mathematical Research Letters , volume =

Carbery, Anthony and Wright, James , title =. Mathematical Research Letters , volume =. 2001 , doi =

2001

[8] [8]

Exponential Improvements to the Average-Case Hardness of

Bouland, Adam and Datta, Ishaun and Fefferman, Bill and Hern. Exponential Improvements to the Average-Case Hardness of. 66th Annual Symposium on Foundations of Computer Science (. 2025 , eprint =

2025