Positivity of Schubert coefficients

Igor Pak; Colleen Robichaux

doi:10.5802/crmath.797

Research article - Algebra

Positivity of Schubert coefficients

Igor Pak ¹; Colleen Robichaux ¹

¹Department of Mathematics, UCLA, Los Angeles, CA 90095, USA

Comptes Rendus. Mathématique, Volume 363 (2025), pp. 1507-1515

Abstract (Original language)
Résumé

Schubert coefficients $c^w_{u,v}$ are structure constants describing multiplication of Schubert polynomials. Deciding positivity of Schubert coefficients is a major open problem in Algebraic Combinatorics. We prove a positive rule for this problem based on two well known assumptions: the Generalized Riemann Hypothesis and the strong derandomization assumption by Miltersen–Vinodchandran.

Les coefficients de Schubert $c^w_{u,v}$ sont des constantes de structure décrivant la multiplication des polynômes de Schubert. Décider de la positivité des coefficients de Schubert est un problème ouvert majeur en Combinatoire Algébrique. Nous prouvons une règle de positivité pour ce problème en nous basant sur deux hypothèses standard : l’hypothèse de Riemann généralisée et l’hypothèse de dérandomisation forte de Miltersen–Vinodchandran.

Received: 2025-01-19
Revised: 2025-09-20
Accepted: 2025-09-20
Published online: 2025-12-12

DOI: 10.5802/crmath.797

Classification: 05E14
Keywords: Schubert polynomials, Schubert structure constants, generalized Riemann hypothesis, derandomization, computational complexity, Hilbert Nullstellensatz, combinatorial interpretation
Mots-clés : Polynômes de Schubert, constantes de structure de Schubert, hypothèse de Riemann généralisée, dérandomisation, complexité informatique, Hilbert Nullstellensatz, interprétation combinatoire

Author's affiliations:

Igor Pak ¹ ; Colleen Robichaux ¹

¹ Department of Mathematics, UCLA, Los Angeles, CA 90095, USA

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{CRMATH_2025__363_G13_1507_0,
     author = {Igor Pak and Colleen Robichaux},
     title = {Positivity of {Schubert} coefficients},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1507--1515},
     year = {2025},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {363},
     doi = {10.5802/crmath.797},
     language = {en},
}

TY  - JOUR
AU  - Igor Pak
AU  - Colleen Robichaux
TI  - Positivity of Schubert coefficients
JO  - Comptes Rendus. Mathématique
PY  - 2025
SP  - 1507
EP  - 1515
VL  - 363
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.797
LA  - en
ID  - CRMATH_2025__363_G13_1507_0
ER  -

%0 Journal Article
%A Igor Pak
%A Colleen Robichaux
%T Positivity of Schubert coefficients
%J Comptes Rendus. Mathématique
%D 2025
%P 1507-1515
%V 363
%I Académie des sciences, Paris
%R 10.5802/crmath.797
%G en
%F CRMATH_2025__363_G13_1507_0

Igor Pak; Colleen Robichaux. Positivity of Schubert coefficients. Comptes Rendus. Mathématique, Volume 363 (2025), pp. 1507-1515. doi: 10.5802/crmath.797

References
Cited by

[1] Anshul Adve; Colleen Robichaux; Alexander Yong Vanishing of Littlewood–Richardson polynomials is in $# P$ , Comput. Complexity, Volume 28 (2019) no. 2, pp. 241-257 | Zbl | MR | DOI

[2] Rida Ait El Manssour; Nikhil Balaji; Klara Nosan; Mahsa Shirmohammadi; James Worrell A parametric version of the Hilbert Nullstellensatz, 2025 Symposium on Simplicity in Algorithms (SOSA) (Ioana-Oriana Bercea; Rasmus Pagh, eds.), Society for Industrial and Applied Mathematics (2025), pp. 444-451 | DOI | MR

[3] David Anderson; William Fulton Equivariant cohomology in algebraic geometry, Cambridge Studies in Advanced Mathematics, 210, Cambridge University Press, 2024 | Zbl | MR

[4] Sara Billey; Ravi Vakil Intersections of Schubert varieties and other permutation array schemes, Algorithms in algebraic geometry (Alicia Dickenstein; Frank-Olaf Schreyer; Andrew J. Sommese, eds.) (The IMA Volumes in Mathematics and its Applications), Volume 146, Springer, 2008, pp. 21-54 | DOI | MR | Zbl

[5] Peter Borwein; Stephen Choi; Brendan Rooney; Andrea Weirathmueller The Riemann hypothesis. A resource for the afficionado and virtuoso alike, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, 2008 | DOI | MR

[6] Anders Skovsted Buch; Frank Sottile; Alexander Yong Quiver coefficients are Schubert structure constants, Math. Res. Lett., Volume 12 (2005) no. 4, pp. 567-574 | DOI | Zbl | MR

[7] Swee Hong Chan; Igor Pak Computational complexity of counting coincidences, Theor. Comput. Sci., Volume 1015 (2024), 114776, 19 pages | Zbl

[8] Swee Hong Chan; Igor Pak Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy, Forum Math. Pi, Volume 12 (2024), e21, 38 pages | MR | Zbl

[9] Swee Hong Chan; Igor Pak Equality cases of the Stanley–Yan log-concave matroid inequality (2024) | arXiv | Zbl

[10] David W. Farmer Currently there are no reasons to doubt the Riemann hypothesis (2022) | arXiv

[11] William I. Gasarch The third $P = ? NP$ poll, SIGACT News, Volume 50 (2019) no. 1, pp. 38-59 | DOI | Zbl

[12] Oded Goldreich Computational complexity, Cambridge University Press, 2008 | DOI | MR | Zbl

[13] Nickolas Hein; Frank Sottile A lifted square formulation for certifiable Schubert calculus, J. Symb. Comput., Volume 79 (2017), pp. 594-608 | DOI | Zbl

[14] Christian Ikenmeyer; Igor Pak What is in #P and what is not?, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), IEEE (2022), pp. 860-871 | MR | DOI | Zbl

[15] Christian Ikenmeyer; Igor Pak; Greta Panova Positivity of the symmetric group characters is as hard as the polynomial time hierarchy, Int. Math. Res. Not. (2024) no. 10, pp. 8442-8458 | DOI | Zbl | MR

[16] Allen Knutson Descent-cycling in Schubert calculus, Exp. Math., Volume 10 (2001) no. 3, pp. 345-353 | DOI | Zbl | MR

[17] Allen Knutson Schubert calculus and quiver varieties, ICM—International Congress of Mathematicians. Vol. 6. Sections 12–14 (D. Beliaev; S. Smirnov, eds.), EMS Press, 2023, pp. 4582-4605 | MR | DOI | Zbl

[18] Allen Knutson; Paul Zinn-Justin Schubert puzzles and integrability III: Separated descents (2023) | arXiv | Zbl

[19] Allen Knutson; Paul Zinn-Justin Schubert puzzles and integrability I: Invariant trilinear forms (2024) | arXiv

[20] Pascal Koiran Hilbert’s Nullstellensatz is in the polynomial hierarchy, J. Complexity, Volume 12 (1996) no. 4, pp. 273-286 | DOI

[21] Marc Lackenby Elementary knot theory, Lectures on geometry (N. M. J. Woodhouse, ed.) (Clay Lecture Notes), Oxford University Press, 2017, pp. 29-64 | MR | Zbl

[22] Ian G. Macdonald Notes on Schubert polynomials, Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, 6, Laboratoire de combinatoire et d’informatique mathématique (LaCIM), Université du Québec à Montréal, 1991

[23] Laurent Manivel Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS Texts and Monographs, 6, American Mathematical Society, Société Mathématique de France, 2001 | MR

[24] Peter B. Miltersen; N. Variyam Vinodchandran Derandomizing Arthur–Merlin games using hitting sets, Comput. Complexity, Volume 14 (2005) no. 3, pp. 256-279 | Zbl | MR | DOI

[25] Igor Pak Complexity problems in enumerative combinatorics, Proc. ICM—Rio de Janeiro 2018. Vol. IV. Invited lectures (Boyan Sirakov; Paulo Ney de Souza; Marcelo Viana, eds.), World Scientific (2018), pp. 3153-3180 | MR | Zbl

[26] Igor Pak What is a combinatorial interpretation?, Open problems in algebraic combinatorics (Christine Berkesch; Benjamin Brubaker; Gregg Musiker; Pavlo Pylyavskyy; Victor Reiner, eds.) (Proceedings of Symposia in Pure Mathematics), Volume 110, American Mathematical Society, 2024, pp. 191-260 | MR

[27] Igor Pak; Colleen Robichaux Signed combinatorial interpretations in algebraic combinatorics, Algebr. Comb., Volume 8 (2025) no. 2, pp. 495-519 | MR

[28] Igor Pak; Colleen Robichaux Vanishing of Schubert coefficients, STOC ’25 — Proceedings of the 57th Annual ACM STOC (2025) (Michal Koucký; Nikhil Bansal, eds.), ACM Press (2025), pp. 1118-1129

[29] Igor Pak; Colleen Robichaux Vanishing of Schubert coefficients is in $AM \cap co AM$ assuming the GRH (2025) (To appear in Forum Math. Sigma) | arXiv

[30] Igor Pak; Colleen Robichaux; Weihong Xu On vanishing of Gromov–Witten invariants (2025) | arXiv

[31] Greta Panova Computational complexity in algebraic combinatorics (2023) | arXiv

[32] Henri Poincaré Science and method, Dover Publications, 1914 | MR

[33] Kevin Purbhoo Vanishing and nonvanishing criteria in Schubert calculus, Int. Math. Res. Not. (2006), 24590, 38 pages | DOI | MR

[34] J. Maurice Rojas Dedekind zeta functions and the complexity of Hilbert’s Nullstellensatz (2003) | arXiv

[35] Avery St. Dizier; Alexander Yong Generalized permutahedra and Schubert calculus, Arnold Math. J., Volume 8 (2022) no. 3–4, pp. 517-533 | MR

[36] Richard P. Stanley Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives (V. Arnold; M. Atiyah; P. Lax; B. Mazur, eds.), American Mathematical Society, 2000, pp. 295-319 | MR

[37] Richard P. Stanley Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 2012 | MR

[38] Salil P. Vadhan Pseudorandomness, Found. Trends Theor. Comput. Sci., Volume 7 (2011) no. 1–3, pp. 1-336 | DOI

[39] Avi Wigderson Mathematics and computation, Princeton University Press, 2019 | MR

[40] Herbert S. Wilf What is an answer?, Am. Math. Mon., Volume 89 (1982) no. 5, pp. 289-292 | DOI | MR

Cited by Sources:

Comments - Policy