Vanishing of Schubert Coefficients

Schubert coefficients are nonnegative integers that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. Computing them is both difficult and mysterious. It is known that they are in GapP, but little else is known except in special cases. Notably, it is a major open problem to show that they are in # P in full generality. We study the hardness of vanishing of Schubert coefficients, i.e. whether they are equal to zero. Until this work it was open whether the vanishing is in PH. In fact, it was believed to be not in PH. We prove that the vanishing problem is in coAM assuming the GRH (the Generalized Riemann Hypothesis). Our approach is based on a reduction to HNP (Parametric Hilbert’s Nullstellensatz) recently introduced by Ait El Manssour et al. We then use a completely different approach to show that the non-vanishing of Schubert coefficients is in NP ℂ ∩ P ℝ in the Blum–Shub–Smale (BSS) model of computation. This result is incomparable to the inclusion in AM and underscores the algebraic nature of Schubert coefficients. We apply our approach to show that computing Schubert coefficients is in # P ℂ. This is the first nontrivial upper bound for the problem. We present our results in the generality of all series of classical reductive groups: general linear, special orthogonal, and symplectic groups of complex matrices, corresponding to root systems A,B,C, and D, respectively. With one notable exception, the above results extend to all series.