Geodesic
Vanishing of Schubert coefficients via the effective Hilbert nullstellensatz
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e162

Voir la notice de l'article provenant de la source Cambridge University Press

Schubert Vanishing is a problem of deciding whether Schubert coefficients are zero. Until this work it was open whether this problem is in the polynomial hierarchy ${{\mathsf {PH}}}$. We prove this problem is in ${{\mathsf {AM}}} \cap {{\mathsf {coAM}}}$ assuming the Generalized Riemann Hypothesis ($\mathrm{GRH}$), that is, relatively low in ${{\mathsf {PH}}}$. Our approach uses Purbhoo’s criterion [57] to construct explicit polynomial systems for the problem. The result follows from a reduction to Parametric Hilbert’s Nullstellensatz, recently analyzed in [2]. We extend our results to all classical types. 
Pak, Igor; Robichaux, Colleen. Vanishing of Schubert coefficients via the effective Hilbert nullstellensatz. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e162. doi: 10.1017/fms.2025.10116
@article{10_1017_fms_2025_10116,
     author = {Pak, Igor and Robichaux, Colleen},
     title = {Vanishing of {Schubert} coefficients via the effective {Hilbert} nullstellensatz},
     journal = {Forum of Mathematics, Sigma},
     pages = {e162},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10116},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10116/}
}
TY  - JOUR
AU  - Pak, Igor
AU  - Robichaux, Colleen
TI  - Vanishing of Schubert coefficients via the effective Hilbert nullstellensatz
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e162
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10116/
DO  - 10.1017/fms.2025.10116
ID  - 10_1017_fms_2025_10116
ER  - 
%0 Journal Article
%A Pak, Igor
%A Robichaux, Colleen
%T Vanishing of Schubert coefficients via the effective Hilbert nullstellensatz
%J Forum of Mathematics, Sigma
%D 2025
%P e162
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10116/
%R 10.1017/fms.2025.10116
%F 10_1017_fms_2025_10116

[1] Adve, A., Robichaux, C. and Yong, A., ‘Vanishing of Littlewood–Richardson polynomials’, Comput. Complexity 28 (2019), 241–257.10.1007/s00037-019-00183-6 Google Scholar | DOI

[2] Ait El Manssour, R., Balaji, N., Nosan, K., Shirmohammadi, M. and Worrell, J., ‘A parametric version of the Hilbert Nullstellensatz’, in Proc. 8th SOSA (2025), 444–451. Google Scholar

[3] Anderson, D. and Fulton, W., Equivariant Cohomology in Algebraic Geometry (Cambridge Univ. Press, Cambridge, UK, 2024), 446 pp. Google Scholar

[4] Anderson, D., Richmond, E. and Yong, A., ‘Eigenvalues of Hermitian matrices and equivariant cohomology of Grassmannians’, Compos. Math. 149 (2013), 1569–1582.10.1112/S0010437X13007343 Google Scholar | DOI

[5] Ardila, F. and Billey, S., ‘Flag arrangements and triangulations of products of simplices’, Adv. Math. 214 (2007), 495–524.10.1016/j.aim.2007.02.014 Google Scholar | DOI

[6] Arora, S. and Barak, B., Complexity, Computational. A Modern Approach (Cambridge Univ. Press, Cambridge, UK, 2009), 579 pp. Google Scholar

[7] Berenstein, A. and Sjamaar, R., ‘Coadjoint orbits, moment polytopes, and the Hilbert–Mumford criterion’, J. Amer. Math. Soc. 13 (2000), 433–466.10.1090/S0894-0347-00-00327-1 Google Scholar | DOI

[8] Berline, N., Vergne, M. and Walter, M., ‘The Horn inequalities from a geometric point of view’, Enseign. Math. 63 (2017), 403–470.10.4171/lem/63-3/4-7 Google Scholar | DOI

[9] Billey, S., ‘Kostant polynomials and the cohomology ring for ’, Duke Math. J. 96 (1999), 205–224.10.1215/S0012-7094-99-09606-0 Google Scholar | DOI

[10] Billey, S. and Haiman, M., ‘Schubert polynomials for the classical groups’, J. Amer. Math. Soc. 8 (1995), 443–482.10.1090/S0894-0347-1995-1290232-1 Google Scholar | DOI

[11] Billey, S. and Vakil, R., ‘Intersections of Schubert varieties and other permutation array schemes’, in Algorithms in Algebraic Geometry (Springer, New York, 2008), 21–54.10.1007/978-0-387-75155-9_3 Google Scholar | DOI

[12] Björner, A. and Brenti, F., Combinatorics of Coxeter Groups (Springer, New York, 2005), 363 pp. Google Scholar

[13] Boppana, R. B., Hastad, J. and Zachos, S., ‘Does… have short interactive proofs?’, Inform. Process. Lett. 25 (1987), 127–132.10.1016/0020-0190(87)90232-8 Google Scholar | DOI

[14] Borwein, P., Choi, S., Rooney, B. and Weirathmueller, A. (eds.), The Riemann Hypothesis (Springer, New York, 2008), 533 pp.10.1007/978-0-387-72126-2 Google Scholar | DOI

[15] Brownawell, W. D., ‘Bounds for the degrees in the Nullstellensatz’, Ann. Math. 126 (1987), 577–591.10.2307/1971361 Google Scholar | DOI

[16] Chan, S. H. and Pak, I., ‘Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy’, Forum Math. Pi 12 (2024), Paper No. e21, 38 pp.10.1017/fmp.2024.20 Google Scholar | DOI

[17] Chan, S. H. and Pak, I., ‘Equality cases of the Stanley–Yan log-concave matroid inequality’, preprint (2024), 36 pp.; . Google Scholar | arXiv

[18] De Loera, J. A. and Mcallister, T. B., ‘On the computation of Clebsch–Gordan coefficients and the dilation effect’, Experiment. Math. 15 (2006), 7–19.10.1080/10586458.2006.10128948 Google Scholar | DOI

[19] Feller, W., An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn (Wiley, New York, 1968), 509 pp. Google Scholar

[20] Goldreich, O., Computational Complexity. A Conceptual Perspective (Cambridge Univ. Press, Cambridge, UK, 2008), 606 pp.10.1017/CBO9780511804106 Google Scholar | DOI

[21] Gutfreund, D., Shaltiel, R. and Ta-Shma, A., ‘Uniform hardness versus randomness tradeoffs for Arthur–Merlin games’, Comput. Complexity 12 (2003), 85–130.10.1007/s00037-003-0178-7 Google Scholar | DOI

[22] Hammett, A. and Pittel, B., ‘How often are two permutations comparable?’, Trans. Amer. Math. Soc. 360 (2008), 4541–4568.10.1090/S0002-9947-08-04478-4 Google Scholar | DOI

[23] Hardt, A. and Wallach, D., ‘When do Schubert polynomial products stabilize?’, preprint (2024), 32 pp.; . Google Scholar | arXiv

[24] Hein, N. and Sottile, F., ‘A lifted square formulation for certifiable Schubert calculus’, J. Symbolic Comput. 79 (2017), 594–608.10.1016/j.jsc.2016.07.021 Google Scholar | DOI

[25] Huber, B., Sottile, F. and Sturmfels, B., ‘Numerical Schubert calculus’, J. Symbolic Comput. 26 (1998), 767–788.10.1006/jsco.1998.0239 Google Scholar | DOI

[26] Humphreys, J. E., Linear Algebraic Groups, Graduate Texts in Mathematics, vol. 21 (Springer, New York–Heidelberg, 1975).10.1007/978-1-4684-9443-3 Google Scholar | DOI

[27] Ikenmeyer, C., Mulmuley, K. D. and Walter, M., ‘On vanishing of Kronecker coefficients’, Comput. Complexity 26 (2017), 949–992.10.1007/s00037-017-0158-y Google Scholar | DOI

[28] Ikenmeyer, C., Pak, I. and Panova, G., ‘Positivity of the symmetric group characters is as hard as the polynomial time hierarchy’, Int. Math. Res. Not. (2024), 8442–8458.10.1093/imrn/rnad273 Google Scholar | DOI

[29] Kleiman, S. L., ‘The transversality of a general translate’, Compos. Math. 28 (1974), 287–297. Google Scholar

[30] Kleiman, S. L., ‘Problem 15: Rigorous foundation of Schubert’s enumerative calculus’, in Mathematical Developments Arising from Hilbert Problems (Amer. Math. Soc., Providence, RI, 1976), 445–482.10.1090/pspum/028.2/0429938 Google Scholar | DOI

[31] Kleiman, S. L. and Laksov, D., ‘Schubert calculus’, Amer. Math. Monthly 79 (1972), 1061–1082.10.1080/00029890.1972.11993188 Google Scholar | DOI

[32] Knutson, A., ‘Descent-cycling in Schubert calculus’, Experiment. Math. 10 (2001), 345–353.10.1080/10586458.2001.10504455 Google Scholar | DOI

[33] Knutson, A., ‘Schubert calculus and puzzles’, in Schubert Calculus (MSJ, Tokyo, Japan, 2016), 185–209. Google Scholar

[34] Knutson, A., ‘Schubert calculus and quiver varieties’, in Proc. ICM, vol. VI (EMS Press, 2023), 4582–4605. Google Scholar

[35] Knutson, A. and Zinn-Justin, P., ‘Schubert puzzles and integrability I: invariant trilinear forms’, preprint (2017), 51 pp.; . Google Scholar | arXiv

[36] Knutson, A. and Zinn-Justin, P., ‘Schubert puzzles and integrability III: separated descents’, preprint (2023), 42 pp.; . Google Scholar | arXiv

[37] Koiran, P., ‘Hilbert’s Nullstellensatz is in the polynomial hierarchy’, J. Complexity 12 (1996), 273–286.10.1006/jcom.1996.0019 Google Scholar | DOI

[38] Koiran, P., ‘A weak version of the Blum, Shub and Smale model’, J. Comput. System Sci. 54(1, part 2) (1997), 177–189.10.1006/jcss.1997.1478 Google Scholar | DOI

[39] Kollár, J., ‘Sharp effective Nullstellensatz’, J. Amer. Math. Soc. 1 (1988), 963–975.10.1090/S0894-0347-1988-0944576-7 Google Scholar | DOI

[40] Lagarias, J. C. and Odlyzko, A. M., ‘Effective versions of the Chebotarev density theorem’, in Algebraic Number Fields: -functions and Galois Properties (Academic Press, New York, 1977), 409–464. Google Scholar

[41] Lascoux, A. and Schützenberger, M.-P., ‘Polynômes de Schubert’, C. R. Acad. Sci. Paris Sér. I Math. 294 (1982), 447–450. Google Scholar

[42] Leykin, A., Martín Del Campo, A., Sottile, F., Vakil, R. and Verschelde, J., ‘Numerical Schubert calculus via the Littlewood–Richardson homotopy algorithm’, Math. Comp. 90 (2021), 1407–1433.10.1090/mcom/3579 Google Scholar | DOI

[43] Macdonald, I. G., Notes on Schubert Polynomials (Publ. LaCIM, UQAM, Montreal, 1991), 116 pp. Google Scholar

[44] Manivel, L., Symmetric Functions, Schubert Polynomials and Degeneracy Loci (SMF/AMS, Providence, RI, 2001), 167 pp. Google Scholar

[45] Mayr, E. W. and Meyer, A. R., ‘The complexity of the word problems for commutative semigroups and polynomial ideals’, Adv. Math. 46 (1982), 305–329.10.1016/0001-8708(82)90048-2 Google Scholar | DOI

[46] Mnëv, N. E., ‘The universality theorems on the classification problem of configuration varieties and convex polytopes varieties’, in Lecture Notes in Math. vol. 1346 (Springer, Berlin, 1988), 527–543. Google Scholar

[47] Mulmuley, K. D., Narayanan, H. and Sohoni, M., ‘Geometric complexity theory III. On deciding nonvanishing of a Littlewood–Richardson coefficient’, J. Algebraic Combin. 36 (2012), 103–110.10.1007/s10801-011-0325-1 Google Scholar | DOI

[48] Pak, I., ‘What is a combinatorial interpretation?’, in Open Problems in Algebraic Combinatorics (Amer. Math. Soc., Providence, RI, 2024), 191–260.10.1090/pspum/110/02007 Google Scholar | DOI

[49] Pak, I. and Robichaux, C., ‘Vanishing of Schubert coefficients’, preprint (2024), v1, 24 pp.; v2 (with D. E. Speyer, App. C), 30 pp.; extended abstract in Proc. 57th STOC (2025), 1118–1129. Google Scholar | arXiv

[50] Pak, I. and Robichaux, C., ‘Positivity of Schubert coefficients’, preprint (2024), 7 pp.; . Google Scholar | arXiv

[51] Pak, I. and Robichaux, C., ‘Signed combinatorial interpretations in algebraic combinatorics’, Algebr. Combin. 8 (2025), 495–519.10.5802/alco.413 Google Scholar | DOI

[52] Pak, I. and Robichaux, C., ‘Vanishing of Schubert coefficients is in assuming the…’, preprint (2025), 18 pp.; . Google Scholar | arXiv

[53] Pak, I., Robichaux, C. and Xu, W., ‘On vanishing of Gromov–Witten invariants’, preprint (2025), 11 pp.; . Google Scholar | arXiv

[54] Panova, G., ‘Computational complexity in algebraic combinatorics’, in Current Developments in Mathematics (Int. Press, Boston, MA, 2024), 241–280. Google Scholar

[55] Postnikov, A. and Stanley, R. P., ‘Chains in the Bruhat order’, J. Algebraic Combin. 29 (2009), 133–174.10.1007/s10801-008-0125-4 Google Scholar | DOI

[56] Purbhoo, K., Vanishing and Non-vanishing Criteria for Branching Schubert Calculus, Ph.D. thesis (UC Berkeley, 2004), 96 pp. Google Scholar

[57] Purbhoo, K., ‘Vanishing and nonvanishing criteria in Schubert calculus’, Int. Math. Res. Not. (2006), Art. 24590, 38 pp.10.1155/IMRN/2006/24590 Google Scholar | DOI

[58] Smirnov, E. and Tutubalina, A., ‘Pipe dreams for Schubert polynomials of the classical groups’, European J. Combin. 107 (2023), Paper No. 103613, 46 pp.10.1016/j.ejc.2022.103613 Google Scholar | DOI

[59] St. Dizier, A. and Yong, A., ‘Generalized permutahedra and Schubert calculus’, Arnold Math. J. 8 (2022), 517–533.10.1007/s40598-022-00208-z Google Scholar | DOI

[60] Stanley, R. P., Enumerative Combinatorics, Vol. 2 (Cambridge Univ. Press, 1999), 581 pp.10.1017/CBO9780511609589 Google Scholar | DOI

[61] Stanley, R. P., ‘Positivity problems and conjectures in algebraic combinatorics’, in Mathematics: Frontiers and Perspectives (Amer. Math. Soc., Providence, RI, 2000), 295–319. Google Scholar

[62] The Stacks Project Authors, The Stacks Project, available at https://stacks.math.columbia.edu (2025). Google Scholar

[63] Vakil, R., ‘Murphy’s law in algebraic geometry: badly-behaved deformation spaces’, Invent. Math. 164 (2006), 569–590.10.1007/s00222-005-0481-9 Google Scholar | DOI

Cité par Sources :