HEXAGONbeta

A new proof of van der Waerden's inequality, and beyond

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.MG — Metric Geometrymath.IT — Information Theorymath.PR — Probability

Contributed by Suvrit Sra ↗

Version 1 / Nov 05, 2026 / CC BY 4.0

Abstract

We give a new, self-contained proof of van der Waerden's permanent inequality via a monotone-averaging argument. Specifically, we show that the minimum total correlation of a random permutation with prescribed doubly stochastic marginals never decreases when two rows or two columns of the marginal matrix are averaged. This quantity is largest at the uniform matrix, which yields van der Waerden's bound. The monotone-averaging rests on the quadratic Alexandrov–Fenchel inequality, which lets us extend the argument to many other problems. In this way we also prove the Friedland–Tverberg inequalities and Gurvits's coefficient bound for Lorentzian polynomials.

Provenance statement

The results in this paper were developed through extensive use of an AI assistant (OpenAI's GPT Pro, in a session that identified itself as GPT-6 Astra Pro). None of the claims were obtained zero-shot. The author's proposal of a Schur-type averaging statement for permanents led to Theorem 2.1; at the author's request the argument was compared with the proofs of Falikman, Egorychev, and Gurvits, and tested on mixed volumes and Lorentzian polynomials, leading to Sections 4–5. The AI assistant carried out the derivations, the literature search, and checks of the arguments. The partial-matching and binary-averaging results (Sections 3 and 6) were developed later in the same way, at the author's request, with AI assistants carrying out the derivations and independent checks. The author also used AI assistants (GPT and Claude) to polish the writing.

Tools used

OpenAI
GPT-6 Astra Pro
Anthropic
Claude

References

  1. Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. Parimutuel betting on permutations. In Internet and Network Economics (WINE 2008) , volume 5385 of Lecture Notes in Computer Science , pages 126--137. Springer, 2008. 10.1007/978-3-540-92185-1_21.DOI
  2. Nima Anari. Beyond the Bethe approximation of the permanent. Preprint, arXiv:2608.28031v2 (https://arxiv.org/abs/2608.28031v2), 2026.arXiv
  3. Nima Anari and Shayan Oveis Gharan. A generalization of permanent inequalities and applications in counting and optimization. Preprint, arXiv:1702.02937 (https://arxiv.org/abs/1702.02937), 2017.arXiv
  4. Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash social welfare, matrix permanent, and stable polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , volume 67 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 36:1--36:12, 2017. 10.4230/LIPIcs.ITCS.2017.36. Theorem numbering refers to arXiv:1609.07056v2 (https://arxiv.org/abs/1609.07056v2).arXivDOI
  5. Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials I : entropy and a deterministic approximation algorithm for counting bases of matroids. Duke Math. J. , 170: 0 3459--3504, 2021. 10.1215/00127094-2020-0091. Theorem numbering refers to arXiv:1807.00929 (https://arxiv.org/abs/1807.00929).arXivDOI
  6. D. N. Bernshtein. The number of roots of a system of equations. Funct. Anal. Appl. , 9: 0 183--185, 1975. 10.1007/BF01075595.DOI
  7. Joseph E. Bonin, Carolyn Chun, and Tara Fife. The natural matroid of an integer polymatroid. SIAM J. Discrete Math. , 37: 0 1751--1770, 2023. 10.1137/22M1521122. Preprint: arXiv:2209.03786 (https://arxiv.org/abs/2209.03786).arXivDOI
  8. Julius Borcea, Petter Br ä nd é n, and Thomas M. Liggett. Negative dependence and the geometry of polynomials. J. Amer. Math. Soc. , 22: 0 521--567, 2009. 10.1090/S0894-0347-08-00618-8.DOI
  9. Petter Br ä nd é n and June Huh. Lorentzian polynomials. Ann. of Math. (2) , 192: 0 821--891, 2020. 10.4007/annals.2020.192.3.4.DOI
  10. L. M. Br é gman. Some properties of nonnegative matrices and their permanents. Dokl. Akad. Nauk SSSR , 211 0 (1): 0 27--30, 1973. URL https://www.mathnet.ru/eng/dan37755. In Russian; English translation in Soviet Math. Dokl. 14 (1973), 945--949.link
Show all 38 referencesShow fewer references
  1. Gi-Sang Cheon and Ian M. Wanless. An update on M inc's survey of open problems involving permanents. Linear Algebra Appl. , 403: 0 314--342, 2005. 10.1016/j.laa.2005.02.030.DOI
  2. Mary Cryan, Heng Guo, and Giorgos Mousa. Modified log- S obolev inequalities for strongly log-concave distributions. Ann. Probab. , 49 0 (1): 0 506--525, 2021. 10.1214/20-AOP1453. Preprint: arXiv:1903.06081 (https://arxiv.org/abs/1903.06081).arXivDOI
  3. Dingding Dong and Vishesh Jain. A deterministic (1+ε)n(1+\varepsilon)^n approximation for the permanent of a nonnegative matrix. Preprint, arXiv:2609.11049v1 (https://arxiv.org/abs/2609.11049v1), 2026.arXiv
  4. Jack Edmonds. Matroid intersection. Ann. Discrete Math. , 4: 0 39--49, 1979. 10.1016/S0167-5060(08)70817-3.DOI
  5. G. P. Egorychev. Proof of the van der W aerden conjecture for permanents. Siberian Math. J. , 22 0 (6): 0 854--859, 1981. 10.1007/BF00968054. Translated from Sibirsk. Mat. Zh. 22 (1981), no. 6, 65--71.DOI
  6. D. I. Falikman. Proof of the van der W aerden conjecture regarding the permanent of a doubly stochastic matrix. Math. Notes , 29 0 (6): 0 475--479, 1981. 10.1007/BF01163285. Translated from Mat. Zametki 29 (1981), no. 6, 931--938.DOI
  7. Shmuel Friedland. A proof of a generalized van der Waerden conjecture on permanents. Linear and Multilinear Algebra , 11 0 (2): 0 107--120, 1982. 10.1080/03081088208817436.DOI
  8. Shmuel Friedland and Leonid Gurvits. Generalized Friedland--Tverberg inequality: applications and extensions, 2006. URL https://arxiv.org/abs/math/0603410. arXiv:math/0603410, version 2; published in revised form as ``Lower bounds for partial matchings in regular bipartite graphs and applications to the monomer--dimer entropy'', Combin. Probab. Comput. 17 (2008) 347--361.arXiv
  9. Leonid Gurvits. The van der Waerden conjecture for mixed discriminants. Advances in Mathematics , 200 0 (2): 0 435--454, 2006. 10.1016/j.aim.2004.12.002. Preprint: arXiv:math/0406420.arXivDOI
  10. Leonid Gurvits. Van der W aerden/ S chrijver-- V aliant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all. Electron. J. Combin. , 15 0 (1): 0 Research Paper 66, 2008. 10.37236/790. Preprint: arXiv:0711.3496 (https://arxiv.org/abs/0711.3496).arXivDOI
  11. Leonid Gurvits. On multivariate N ewton-like inequalities. In Advances in Combinatorial Mathematics , pages 61--78. Springer, 2009 a . 10.1007/978-3-642-03562-3_4. Theorem numbering refers to arXiv:0812.3687 (https://arxiv.org/abs/0812.3687).arXivDOI
  12. Leonid Gurvits. A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor. Discrete Comput. Geom. , 41: 0 533--555, 2009 b . 10.1007/s00454-009-9147-5. Theorem numbering refers to arXiv:cs/0702013v4 (https://arxiv.org/abs/cs/0702013v4).arXivDOI
  13. Leonid Gurvits. Unleashing the power of Schrijver 's permanental inequality with the help of the Bethe approximation. Preprint, arXiv:1106.2844v11 (https://arxiv.org/abs/1106.2844v11), 2012.arXiv
  14. Leonid Gurvits and Jonathan Leake. Counting matchings via capacity-preserving operators. Combin. Probab. Comput. , 30: 0 956--981, 2021. 10.1017/S0963548321000122.DOI
  15. Leonid Gurvits and Jonathan Leake. Unique minimizers for permanents, mixed discriminants, and log-concave polynomials. Preprint, arXiv:2609.21083 (https://arxiv.org/abs/2609.21083), 2026. Revision 2, 15 October 2026.arXiv
  16. Ole J. Heilmann and Elliott H. Lieb. Theory of monomer-dimer systems. Communications in Mathematical Physics , 25 0 (3): 0 190--232, 1972. 10.1007/BF01877590.DOI
  17. Thorkell Helgason. Aspects of the theory of hypermatroids. In Hypergraph Seminar , volume 411 of Lecture Notes in Math. , pages 191--213. Springer, Berlin, 1974.
  18. Yair Lavi. The Marcus--Minc transform inequality, 2026. URL https://arxiv.org/abs/2609.29262. Preprint, arXiv:2609.29262, version 1.arXiv
  19. Joonkyung Lee and Jaehyeon Seo. Antiferromagnetic models are clique-minimizing. Preprint, arXiv:2608.17920 (https://arxiv.org/abs/2608.17920), 2026.arXiv
  20. C. J. H. McDiarmid. Independence structures and submodular functions. Bull. London Math. Soc. , 5: 0 18--20, 1973.
  21. O. S. Rothaus. Study of the permanent conjecture and some generalizations. Bull. Amer. Math. Soc. , 78 0 (5): 0 749--752, 1972. 10.1090/S0002-9904-1972-13017-9.DOI
  22. Alexander Schrijver. Counting 1-factors in regular bipartite graphs. Journal of Combinatorial Theory, Series B , 72 0 (1): 0 122--135, 1998. 10.1006/jctb.1997.1798.DOI
  23. Paul B. Slater. Maximum entropy convex decompositions of doubly stochastic and nonnegative matrices. Environment and Planning A , 19 0 (3): 0 403--407, 1987. 10.1068/a190403.DOI
  24. Suvrit Sra. A sharp B r é gman-- M inc bound for permanents. Companion preprint, 2026 a .
  25. Suvrit Sra. Supplement: G amma-- O rlicz upper bounds for mixed derivatives. Supplement to the companion preprints, 2026 b .
  26. Damian Straszak and Nisheeth K. Vishnoi. Real stable polynomials and matroids: optimization and counting. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017) , pages 370--383, 2017 a . 10.1145/3055399.3055457. Appendix numbering refers to arXiv:1611.04548 (https://arxiv.org/abs/1611.04548).arXivDOI
  27. Damian Straszak and Nisheeth K. Vishnoi. On convex programming relaxations for the permanent. Preprint, arXiv:1701.01419 (https://arxiv.org/abs/1701.01419), 2017 b .arXiv
  28. Joseph S. Verducci. Minimum majorization decomposition. In Contributions to Probability and Statistics , pages 160--173. Springer, New York, 1989. 10.1007/978-1-4612-3678-8_12.DOI

Version history

  1. v1 · 31 pagesSubmitted by Suvrit SraInitial depositCurrentNov 05, 2026