HEXAGONbeta

A sharp Brégman–Minc bound for permanents

A mix of human-written and AI-generated textHuman understanding: all partsmath.CA — Classical Analysis and ODEsmath.CO — Combinatoricsmath.FA — Functional Analysismath.IT — Information Theory

Contributed by Suvrit Sra ↗

Version 1 / Nov 02, 2026 / CC BY 4.0

Abstract

We prove a sharp Brégman–Minc bound for permanents of nonnegative matrices that was conjectured by Samorodnitsky and Gurvits. Specifically, for ϕ(x)=Γ(1+1/x)−x\phi(x)=\Gamma(1+1/x)^{-x}, with ϕ(0)=0\phi(0)=0, applied entrywise, we show that every nonnegative row-stochastic square matrix AA satisfies per⁡ϕ[A]≤1\operatorname{per}\phi[A]\le1, which is the Brégman–Minc inequality when each row of AA is uniform on its support. The crux of our proof is a scalar inequality on the simplex, which we prove using a carefully chosen yet elementary integral representation. We note brief applications to the entropy of a random permutation and to sharp bounds for rectangular permanents and matchings.

Provenance statement

The results were developed with GPT-6 (Pro) after extensive back and forth; none were obtained zero-shot. The author chose the problem, directed its Orlicz formulation, and suggested seeking positive integral representations as in subentropy (Sra, 2019), which was decisive to unlocking the proof—Section 3. GPT Pro supplied derivations, literature searches, and repeated checks; GPT and Claude helped polish the writing.

Tools used

OpenAI
GPT-6 Pro
Anthropic
Claude

References

  1. L. M. Br é gman. Some properties of nonnegative matrices and their permanents. Soviet Math. Dokl. , 14: 0 945--949, 1973. Translated from Dokl. Akad. Nauk SSSR 211 (1973), no. 1, 27--30.
  2. Alexandre Bristiel and Pietro Caputo. Entropy inequalities for random walks and permutations. Ann. Inst. Henri Poincar é Probab. Stat. , 60 0 (1): 0 54--81, 2024. 10.1214/22-AIHP1267. Preprint: arXiv:2109.06009 (https://arxiv.org/abs/2109.06009).arXivDOI
  3. Leonid Gurvits and Alex Samorodnitsky. Bounds on the permanent and some applications. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages 90--99. IEEE Computer Society, 2014. 10.1109/FOCS.2014.18. Extended version: arXiv:1408.0976 (https://arxiv.org/abs/1408.0976); conjecture numbering refers to that version.arXivDOI
  4. Richard Jozsa and Graeme Mitchison. Symmetric polynomials in information theory: entropy and subentropy. J. Math. Phys. , 56 0 (6): 0 062201, 2015. 10.1063/1.4922317. Preprint: arXiv:1404.7694 (https://arxiv.org/abs/1404.7694).arXivDOI
  5. National Institute of Standards and Technology . NIST digital library of mathematical functions. https://dlmf.nist.gov/5.8, 2026. Chapter 5, especially §5.8. Accessed 30 October 2026.link
  6. Jaikumar Radhakrishnan. An entropy proof of B r é gman's theorem. J. Combin. Theory Ser. A , 77 0 (1): 0 161--164, 1997. 10.1006/jcta.1996.2727.DOI
  7. Alex Samorodnitsky. An upper bound for permanents of nonnegative matrices. J. Combin. Theory Ser. A , 115 0 (2): 0 279--292, 2008. 10.1016/j.jcta.2007.05.010. Preprint: arXiv:math/0605147 (https://arxiv.org/abs/math/0605147).arXivDOI
  8. George W. Soules. Permanental bounds for nonnegative matrices via decomposition. Linear Algebra Appl. , 394: 0 73--89, 2005. 10.1016/j.laa.2004.06.022.DOI
  9. Suvrit Sra. Logarithmic inequalities under a symmetric polynomial dominance order. Proc. Amer. Math. Soc. , 147 0 (2): 0 481--486, 2019. 10.1090/proc/14023. Preprint, with a slightly different title: arXiv:1509.05902 (https://arxiv.org/abs/1509.05902).arXivDOI

Version history

  1. v1Submitted by Suvrit SraInitial depositCurrentOct 31, 2026