HEXAGONbeta

Linear Trace-Deficit Decay for Permanents of Positive Semidefinite Contractions

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.PR — Probability

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Oct 15, 2026 / CC BY 4.0

Abstract

Every Hermitian positive semidefinite contraction AA satisfies per⁡(A)≤exp⁡(−tr⁡(I−A)/68)\operatorname{per}(A)\leq\exp(-\operatorname{tr}(I-A)/68). This proves the linear trace-deficit bound conjectured by Ebrahimnejad, Nagda, and Oveis Gharan, whose estimate had quadratic dependence on the normalized deficit. The proof combines a size-biased complex Gaussian representation, a block version of Hanson–Wright decoupling, and a rational Loewner majorant. The constant is uniform in the dimension and is not optimized.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.

Tools used

Bolzano team
Bolzano

References

  1. F. Ebrahimnejad, A. Nagda, and S. Oveis Gharan, On approximability of the permanent of PSD matrices , STOC 2025, 625--630. Numbered references use the full version, arXiv:2404.10959v1, 2024. https://arxiv.org/abs/2404.10959.arXiv
  2. N. Anari and F. Ebrahimnejad, Optimal e(γ+o(1))ne^{(\gamma+o(1))n}-Approximation of the Permanent of Positive Semidefinite Matrices , arXiv:2605.21946, 2026. https://arxiv.org/abs/2605.21946.arXiv
  3. N. Anari, L. Gurvits, S. Oveis Gharan, and A. Saberi, Simply exponential approximation of the permanent of positive semidefinite matrices , FOCS 2017, 914--925. https://arxiv.org/abs/1704.03486.link
  4. C. Yuan and P. A. Parrilo, Maximizing products of linear forms, and the permanent of positive semidefinite matrices , Mathematical Programming 193 (2022), 499--510. https://doi.org/10.1007/s10107-021-01616-3.DOI
  5. A. Barvinok, A remark on approximating permanents of positive definite matrices , arXiv:2005.06344, 2020. https://arxiv.org/abs/2005.06344.arXiv
  6. M. Rudelson and R. Vershynin, Hanson--Wright inequality and sub-Gaussian concentration , Electronic Communications in Probability 18 (2013), no. 82, 1--9. https://arxiv.org/abs/1306.2872.link
  7. D. Hsu, S. M. Kakade, and T. Zhang, A tail inequality for quadratic forms of subgaussian random vectors , Electronic Communications in Probability 17 (2012), no. 52, 1--6. https://arxiv.org/abs/1110.2842.link
  8. A. Laddha and M. R. Pittu, An algorithmic upper bound for permanents via a permanental Schur inequality , arXiv:2509.08121, 2025. https://arxiv.org/abs/2509.08121.arXiv
  9. Z. Yi, Diffuse Gaussian truncation for deterministic approximate counting , arXiv:2609.04079, 2026. https://arxiv.org/abs/2609.04079.arXiv

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 15, 2026