1 Introduction
1.1 Foreword
The Schubert vanishing problem asks whether Schubert structure constants (Schubert coefficients) are zero. This is one of the oldest problems in enumerative geometry, going back to Schubert’s original work in the 1870s. Fundamentally, it is about the existence of certain configurations of complex lines, planes, etc., with given dimensions of intersections; see, for example, [Reference Kleiman and Laksov31]. Motivated in part by Hilbert’s 15th Problem aiming to make Schubert’s work rigorous (see [Reference Kleiman30]), the area of Schubert calculus has exploded and developed rich connections with representation theory and algebraic combinatorics (see [Reference Anderson and Fulton3, Reference Knutson34]).
Despite a large body of numerical work, see, for example, [Reference Huber, Sottile and Sturmfels25, Reference Hein and Sottile24, Reference Leykin, Martín del Campo, Sottile, Vakil and Verschelde42], the complexity analysis of the problem has been entirely missing, see [Reference Billey and Vakil11, p. 41]. In this paper we give the first such analysis, placing the Schubert vanishing problem in the complexity class
${{\mathsf {AM}}} \cap {{\mathsf {coAM}}}$
assuming the
$\mathrm{GRH}$
(Main Theorem 1.1), that is, relatively low in the polynomial hierarchy
${{\mathsf {PH}}}$
. Until now, it was not known whether the problem is in
${{\mathsf {PH}}}$
. This result has a number of combinatorial and complexity implications, notably that Schubert vanishing is unlikely to be
${{\mathsf {NP}}}$
-hard (Corollary 1.5).
The proof is entirely algebraic and uses concise reductions of the Schubert vanishing problem and its negation to instances of Hilbert’s Nullstellensatz 
over function fields. From this point, the complexity theoretic heavy lifting was done by Koiran [Reference Koiran37, Reference Koiran38] and Ait El Manssour et al. [Reference Ait El Manssour, Balaji, Nosan, Shirmohammadi and Worrell2], who showed that 
is in
${{\mathsf {AM}}}$
assuming the
$\mathrm{GRH}$
. The surprising part is that we have two reductions rather than just one, suggesting that there is no Murphy’s law (universality theorem) for the Schubert vanishing, cf. [Reference Mnëv46, Reference Vakil63].
Our own motivation comes from the problem of finding a combinatorial interpretation for the Schubert coefficients, one of the most celebrated open problems in algebraic combinatorics [Reference Stanley61, Problem 11]. In the complexity language, having a combinatorial interpretation implies that Schubert positivity (nonvanishing) is in the complexity class
${{\mathsf {NP}}}$
, see [Reference Pak48,
$\S$
10]. Our results imply this conclusion, modulo
$\mathrm{GRH}$
and standard derandomization assumptions (see also
$\S $
4.4).
Finally, we note that Schubert vanishing is of interest in its own right, independent of geometric considerations, in part because Schubert positivity (nonvanishing) is asymptotically rare (see
$\S $
4.3). Additionally, positivity of Schubert coefficients is the main assumption in the generalized Horn inequalities, see, for example, [Reference Anderson, Richmond and Yong4, Reference Berenstein and Sjamaar7, Reference Berline, Vergne and Walter8]. In his 2022 ICM paper, Knutson emphasized the importance of the Schubert vanishing problem as follows: “For applications (including real-world engineering applications) it is more important to know that [Schubert] structure constant is positive, than it is to know its actual value” [Reference Knutson34,
$\S$
1.4].
1.2 Schubert coefficients
We start with a general setup, see, for example, [Reference Anderson and Fulton3] for the background and
$\S $
2.1 for standard notation. Let
$\mathsf {G}$
be a complex reductive Lie group. Take
$\mathsf {B}\subset \mathsf {G}$
and
$\mathsf {B}_{-}\subset \mathsf {G}$
to be the Borel subgroup and opposite Borel subgroup, respectively. The torus subgroup is defined as
$\mathsf {T}=\mathsf {B}\cap \mathsf {B}_{-}\hskip .03cm$
. The Weyl group is defined as the normalizer
$\mathcal {W}\cong N_{\mathsf {G}}(\mathsf {T})/\mathsf {T}$
. The Bruhat decomposition states that
$$ \begin{align*}\mathsf{G} \ = \ \bigsqcup_{w\in \mathcal{W}} {\hskip.06cm} \mathsf{B}_{-} {\hskip.06cm} \dot{w} {\hskip.06cm} \mathsf{ B}, \end{align*} $$
where
$\dot {w}$
is the preimage of w in the normalizer
$N_{\mathsf {G}}(\mathsf T)$
.
The generalized flag variety is defined as
$\mathsf {G}/\mathsf {B}$
. Recall that
$\mathsf {G}/\mathsf {B}$
has finitely many orbits under the left action of
$\mathsf {B}_{-}\hskip .03cm$
. These are called Schubert cells and denoted
$\Omega _w\hskip .03cm$
. Schubert cells are indexed by the Weyl group elements
$w\in \mathcal {W}$
.
The Schubert varieties
$X_w$
are the Zariski closures of Schubert cells
$\Omega _w$
. The Schubert classes
$\{\sigma _w\}_{w\in \mathcal {W}}$
are the Poincaré duals of Schubert varieties. These form a
${\mathbb Z}$
-linear basis of the cohomology ring
$H^{*}(\mathsf {G}/\mathsf {B})$
. The Schubert coefficients
$c_{u,v}^w$
are defined as structure constants:
$$ \begin{align} \sigma_u \smallsmile \sigma_v \, = \, \sum_{w\in {\mathcal{W}}} {\hskip.06cm} c_{u,v}^{w} {\hskip.06cm} \sigma_{w}. \end{align} $$
Thus
$c_{u,v}^{w}=[\sigma _{\mathrm {{id}}}] \hskip .03cm \sigma _u \smallsmile \sigma _v\smallsmile \sigma _{w_{\circ }w}$
, where
$w_\circ $
is the long word in
$\hskip .03cm\mathcal {W}$
, see
$\S $
2.3. Generalizing, we take
$$ \begin{align} c(u_1,u_2,\ldots,u_k) \, := \, [\sigma_{\mathrm{{id}}}] {\hskip.06cm} \sigma_{u_1} \smallsmile\sigma_{u_2}\smallsmile\cdots \smallsmile \sigma_{u_k}, \end{align} $$
where
$k\geq 3$
. In particular, we have
$c_{u,v}^w = c(u,v,w_\circ w)$
. By commutativity of
$H^{*}(\mathsf {G}/\mathsf {B})$
, Schubert coefficients
$c(u_1,\ldots ,u_k)$
exhibit
$S_k$
-symmetry.
By Kleiman transversality [Reference Kleiman29], the coefficients
$c(u_1,\ldots ,u_k)$
count the number of points in the intersection of generically translated Schubert varieties:
$$ \begin{align} c(u_1,\ldots,u_k) \, = \,\#\big\{{\hskip.06cm} X_{u_1}\big(F_{\bullet}^{(1)}\big) \cap \cdots \cap X_{u_k}\big(F^{(k)}_{\bullet}\big){\hskip.06cm}\big\}, \end{align} $$
where
$X_{u_i}\big (F_{\bullet }^{(i)}\big )$
is the Schubert variety
$X_{u_i}$
translated by a generic flag
$F_{\bullet }^{(i)}$
. In particular, we have
$c(u_1,\ldots ,u_k)\in \mathbb N$
. The Schubert vanishing problem is a decision problem
where
$u_1,\ldots ,u_k\in \mathcal W$
. We consider the problem only for classical types
$Y \in \{A,B,C,D\}$
, and use the notation 
to denote the Schubert vanishing problem in type Y.Footnote 1 These correspond to considering
$\mathsf {G}\in \{\mathsf {SL}_n({\mathbb {C}}), \mathsf {SO}_{2n+1}({\mathbb {C}}), \mathsf {Sp}_{2n}({\mathbb {C}}), \mathsf {SO}_{2n}({\mathbb {C}})\}$
, respectively.
1.3 Main results
Recall the complexity class
${{\mathsf {AM}}}$
of decision problems whose “yes” answers can be decided in polynomial time by an Arthur–Merlin protocol with two messages, see, for example, [Reference Arora, Barak and Complexity6, Reference Goldreich20]. Heuristically, one should think of the class
${{\mathsf {AM}}}$
as a (nonobvious) probabilistic extension of the class
${{\mathsf {NP}}}$
. The complexity class
${{\mathsf {coAM}}}$
is the complement of languages in
${{\mathsf {AM}}}$
, that is, the decision problems whose “no” answers can be decided in polynomial time by an Arthur–Merlin protocol with two messages. See
$\S $
2.4 for connections to other complexity classes.
Theorem 1.1 (Main theorem).
SchubertVanishing
$(Y)$
is in
${{\mathsf {AM}}} \cap {{\mathsf {coAM}}}$
assuming the
$\mathrm{GRH}$
, for all
$Y \in \{A,B,C,D\}$
.
Here the
$\mathrm{GRH}$
stands for the Generalized Riemann Hypothesis, that all nontrivial zeros of L-functions
$L(s,\chi _k)$
have real part
$\frac 12$
. In fact, tracing back the references shows that a weaker assumption, the Extended Riemann Hypothesis (
) suffices. We stick with the
$\mathrm{GRH}$
as it is better known, and refer to [Reference Borwein, Choi, Rooney and Weirathmueller14,
$\S$
6] for definitions and relationships between these hypotheses.
To get some idea of the result, recall the graph isomorphism problem which is naturally in
${{\mathsf {NP}}}\subseteq {{\mathsf {AM}}}$
. One of the first and most celebrated examples of the interactive proof is the
${{\mathsf {AM}}}$
protocol for graph nonisomorphism, see, for example, [Reference Goldreich20,
$\S$
9.1.3]. Heuristically, this means that a prover can convince a verifier that two given graphs are not isomorphic using a probabilistic argument, if the prover has unlimited power, but the verifier can perform only poly-time computations verifying prover’s claims. In particular, this shows that GraphIsomorphism in
${{\mathsf {AM}}} \cap {{\mathsf {coAM}}}$
. Famously, this was used in [Reference Boppana, Hastad and Zachos13] to conclude that the problem is unlikely to be
${{\mathsf {NP}}}$
-complete, cf. Corollary 1.5.
There is extensive literature in algebraic combinatorics with necessary and sufficient conditions for the vanishing of Schubert coefficients. We postpone discussion of the prior work, as well as the implications of the main theorem, until later in this section.
1.4 Hilbert’s Nullstellensatz
Let
$R={\mathbb {C}}{}[x_1,\dots ,x_s]$
for some
$s>0$
. Hilbert’s weak Nullstellensatz states that a polynomial system
$$ \begin{align} f_1 {\hskip.06cm} = {\hskip.06cm} \ldots {\hskip.06cm} = {\hskip.06cm} f_m {\hskip.06cm} = {\hskip.06cm} 0 \quad \text{where} \quad f_i\in R \end{align} $$
has no solutions over
${\mathbb {C}}$
if and only if there exist
$(g_1,\ldots ,g_m)\in R^m$
, such that
$$ \begin{align*}\sum_{i=1}^m {\hskip.06cm} f_i {\hskip.06cm} g_i \, = \, 1. \end{align*} $$
Now let
$f_1,\ldots ,f_m\in \mathbb Z[x_1,\dots ,x_s]$
. The decision problem 
(Hilbert’s Nullstellensatz) asks if the polynomial system (1.4) has a solution over
$\mathbb {C}$
.Footnote 2 Here, the size of the polynomial system is the sum of the degrees of the polynomials
$f_i$
added to the sum of bit-lengths of the coefficients in the
$f_i$
.
The original proof of Hilbert’s Nullstellensatz does not imply that 
is decidable. This follows from [Reference Mayr and Meyer45] by Mayr and Meyer, who showed that 
is in
${{\mathsf {EXPSPACE}}}$
and is also
${{\mathsf {NP}}}$
-hard. Major improvements by Brownawell [Reference Brownawell15] and Kollár [Reference Kollár39] showed that one can take
$g_i$
of single exponential size (effective Nullstellensatz), which can be used to show that 
is in
${{\mathsf {PSPACE}}}$
. In a surprising breakthrough, Koiran showed that 
is in the polynomial hierarchy:
Theorem 1.2 [Reference Koiran37, Thm 2].
HN
is in
${{\mathsf {AM}}}$
assuming the
$\mathrm{GRH}$
.
For the proof, Koiran needs existence of primes in certain intervals and with modular conditions, thus the
$\mathrm{GRH}$
assumption. For the proof of Theorem 1.1, we need the following strengthening of Theorem 1.2 to finite algebraic extensions. Let
$$ \begin{align*}f_1,\ldots,f_m{\hskip.06cm}\in{\hskip.06cm} \mathbb{Z}(y_1,\ldots,y_k) \hskip.03cm [x_1,\dots,x_s]. \end{align*} $$
The decision problem 
(Parametric Hilbert’s Nullstellensatz) asks if the polynomial system (1.4) has a solution over
$\overline {\mathbb {C}(y_1,\ldots ,y_k)}$
. Most recently, Ait El Manssour, Balaji, Nosan, Shirmohammadi, and Worrell extended Theorem 1.2 to 
Theorem 1.3 [Reference Ait El Manssour, Balaji, Nosan, Shirmohammadi and Worrell2, theorem 1].
HNP
is in
${{\mathsf {AM}}}$
assuming the
$\mathrm{GRH}$
.
In the proof, the authors substantially simplified Koiran’s original approach in [Reference Koiran37, Reference Koiran38], avoiding the use of semi-algebraic geometry. We refer the reader to a [Reference Ait El Manssour, Balaji, Nosan, Shirmohammadi and Worrell2] for an extensive background of 
and other related work.
1.5 Proof outline
We prove Theorem 1.1 by showing that Schubert vanishing can be viewed as an instance of the Parametric Hilbert’s Nullstellensatz. We then show that the same holds for Schubert nonvanishing. More precisely, we prove the following:
Lemma 1.4 (Main lemma).
Both
SchubertVanishing
$(Y)$
and
$\neg $
SchubertVanishing
$(Y)$
reduce to
HNP
, for all
$Y \in \{A,B,C,D\}$
.
Here 
where
$u_1,\ldots ,u_k\in \mathcal W$
. The lemma, combined with Theorem 1.3 immediately implies Theorem 1.1. For the proof of the Lemma 1.4, we give an explicit construction of two polynomial systems (1.4) with polynomially many parameters, one system for each part of the lemma. For both systems, we start with Purbhoo’s criterion (Lemma 3.1), and restate it as a lifted formulation, giving reductions to 
.
Purbhoo’s criterion directly connects 
to a particular sum of vector spaces being full-dimensional. We construct generators for this vector space and formulate a pair of polynomial systems to determine if these generators form a basis or not. We note that Purbhoo’s criterion is stated in terms of generic group elements. However, such generic elements need not necessarily have succinct (polynomial size) representations. To bypass this issue, we describe explicit constructions of generic elements in terms of formal parameters. The resulting equations have polynomial coefficients in these parameters.
1.6 Prior work
The literature on the vanishing of Schubert coefficients and its various extensions is too extensive to be fully reviewed. Below are some highlights that we believe are most relevant. Although many of these conditions extend to larger k and all types, we restrict our presentation to the case
$k=3$
and type A, which is the best studied.
$(1)$
First, recall a large number of sufficient conditions for the vanishing of Schubert coefficients
$c_{u,v}^w\hskip .03cm$
. These conditions are scattered across the literature and include:Footnote 3
-
○ the number of inversion condition
${\mathrm {inv}}(u)+{\mathrm {inv}}(v)\neq {\mathrm {inv}}(w)$
[Reference Lascoux and Schützenberger41], -
○ the number of descents condition
${\mathrm {des}}(w)> {\mathrm { des}}(u)+{\mathrm {des}}(v)$
[Reference Lascoux and Schützenberger41], -
○ strong Bruhat order condition
$u \not \leqslant w$
, see, for example, [Reference St. Dizier and Yong59,
$\S$
5.1], -
○ Knutson’s descent cycling condition
${\mathrm {Des}}(u) \cap {\mathrm {Des}}(v) \cap {\mathrm {Des}}(w w_\circ )\ne \varnothing $
[Reference Knutson32], -
○ Billey–Vakil’s permutation array condition [Reference Billey and Vakil11, Thm 5.1] (see also [Reference Ardila and Billey5, Prop. 9.7]),
-
○ St. Dizier–Yong’s condition on certain fillings of Rothe diagrams [Reference St. Dizier and Yong59, Thm A], and
-
○ Hardt–Wallach’s condition on empty rows in Rothe diagrams [Reference Hardt and Wallach23, Cor. 5.12].
The first three of these follow directly from the Lascoux–Schützenberger definition of Schubert polynomials, see
$\S $
4.2, while the other conditions are more technical. All of these can be verified in poly-time; this is immediate in all cases except for the strong Bruhat order condition which needs the Ehresmann criterion [Reference Manivel44, Prop. 2.1.11], and the St. Dizier–Yong condition where this is a part of their main theorem.
For Grassmannian permutations (permutations with one descent), Schubert coefficients are the Littlewood–Richardson (LR) coefficients, see, for example, [Reference Macdonald43, Reference Manivel44], which are extensively studied in algebraic combinatorics, see, for example, [Reference Stanley60, Ch. 7]. In this case, the vanishing problem is in
${{{\mathsf {P}}}}$
as a corollary of the Knutson–Tao saturation theorem [Reference De Loera and McAllister18, Reference Mulmuley, Narayanan and Sohoni47].
There are several other classes of permutations, where the Schubert coefficients have a known combinatorial interpretation. In such cases, the combinatorial interpretation can be interpreted as sufficient conditions for nonvanishing. Notable examples include:
-
○ Purbhoo’s root game conditions [Reference Purbhoo56, Reference Purbhoo57], and
-
○ Knutson and Zinn-Justin’s tiling conditions [Reference Knutson and Zinn-Justin35, Reference Knutson and Zinn-Justin36].
We refer to [Reference St. Dizier and Yong59,
$\S$
5] and [Reference Pak and Robichaux49,
$\S$
1.6] for technical details, comparisons, and further background on all these conditions.
$(2)$
Partly motivated by numerical applications, there have also been efforts to give a description of an algebraic system for various Schubert problems. Notably, in [Reference Billey and Vakil11, Thm 5.4], Billey and Vakil give an algebraic system with exactly
$c^w_{u,v}$
solutions for generic values of certain variables. They also describe the system of conditions for these variables being generic under the assumption that the set of solutions is
$0$
-dimensional [Reference Billey and Vakil11, Cor. 5.5]. The authors do not give a complexity analysis for this system; see [Reference Pak and Robichaux49,
$\S$
8.1] for further details and a complexity discussion.
In [Reference Hein and Sottile24], Hein and Sottile introduced an algebraic system giving a practical algorithm for computing Schubert coefficients. Their system had additional variables compared to the Billey–Vakil system and allowed polynomial equations to have smaller (polynomial) size. In the first draft [Reference Pak and Robichaux49] of this paper, we used the Hein–Sottile system (in type A), which we modified and extended to other types. We eventually shifted our approach in favor of an algebraic system given by Purbhoo’s criterion. This characterization is amenable to a more uniform approach and is a better fit with Hilbert’s Nullstellensatz, as this criterion characterizes the vanishing problem in particular. We refer to
$\S $
4.1 for an overview of our earlier preprints in the evolution of this paper.
$(3)$
Finally, there is very little known about the computational complexity of Schubert vanishing. It follows from existing literature that 
, but even that bound was never explicitly written. In type A and for
$k=3$
, this was observed by Morales as a consequence of the Postnikov–Stanley formula [Reference Postnikov and Stanley55, Cor. 17.13], see [Reference Pak48,
$\S$
10] for details.Footnote 4 In combinatorial terminology, this formula shows
$c^w_{u,v}$
has a signed combinatorial interpretation derived from the (usual) combinatorial interpretation for the Schubert–Kostka numbers (see
$\S $
4.2) in terms of pipe dreams.
For general
$k\ge 4$
, the result follows by taking convolutions. For other classical types, one can follow the approach above and combine the pipe dream construction in [Reference Smirnov and Tutubalina58] with the effective Möbius inversion in [Reference Pak and Robichaux51,
$\S$
2.2]. We omit the details which are straightforward, but require a separate explanation in each type. Another way to see that Schubert vanishing is in
${{\mathsf {PSPACE}}}$
it to use the recursive, but type-independent Billey’s formula [Reference Billey9, Eq. (5.5)].
1.7 Implications
From the computational complexity point of view, Main Theorem 1.1 shows that 
is in
$\Sigma ^{{\text {p}}}_2\cap \Pi ^{{\text {p}}}_2$
assuming the
$\mathrm{GRH}$
, that is, relatively low in the polynomial hierarchy
${{\mathsf {PH}}}$
. Inclusion in
${{\mathsf {PH}}}$
was out of reach prior to this paper.
Similarly, it has been conjectured for a while that computing Schubert coefficients is computationally hard, see, for example, an extensive discussion in [Reference Billey and Vakil11,
$\S$
5.2] and [Reference Pak and Robichaux49,
$\S$
1.4]. Notably, Adve, Robichaux, and Yong asked whether 
is
${{\mathsf {NP}}}$
-hard [Reference Adve, Robichaux and Yong1, Question 4.3]. In the opposite direction, the authors conjectured that 
is
${{\mathsf {NP}}}$
-hard [Reference Pak and Robichaux49, Conj. 1.6]. The following result resolves in the negative both the question and the conjecture under standard assumptions:
Corollary 1.5.
SchubertVanishing
is not
${{\mathsf {NP}}}$
-hard, assuming the
$\mathrm{GRH}$
and
${{\mathsf {PH}}}\ne \Sigma ^{{\text {p}}}_2$
, that is, the polynomial hierarchy does not collapse to its second level. Similarly, 
is not
${{\mathsf {NP}}}$
-hard, under the same assumptions.
The corollary follows immediately from the Main Theorem 1.1 and a result of Boppana, Håstad and Zachos [Reference Boppana, Hastad and Zachos13, Thm 2.3]. In particular, the corollary implies that the vanishing of Schubert coefficients is quite different from the vanishing of Kronecker coefficients which is known to be
${{\mathsf {coNP}}}$
-hard [Reference Ikenmeyer, Mulmuley and Walter27]. See also [Reference Panova54,
$\S$
5.2] for further details and references.
In algebraic combinatorics, a major open problem is whether Schubert coefficients have a combinatorial interpretation [Reference Stanley61, Problem 11]. In the language of computational complexity this is asking whether this counting problem is in
${{\mathsf {\#P}}}$
, the counting analogue of
${{\mathsf {NP}}}$
. See a detailed discussion in [Reference Pak48,
$\S$
10]. This would imply that 
is in
${{\mathsf {coNP}}}$
. In the combinatorial language, this is saying that positivity of Schubert coefficients problem
$\big \{c^w_{u,v}>^?0\big \}$
has a positive rule [Reference Pak and Robichaux50].
The special cases mentioned above suggest that both Schubert vanishing and Schubert nonvanishing might have a positive rule, that is, that 
. Until recently this conclusion would seem fantastical and out of reach. Now, it was shown by Gutfreund, Shaltiel, and Ta-Shma [Reference Gutfreund, Shaltiel and Ta-Shma21], that if
${{\mathsf {EXP}}}$
requires exponential time even for
${{\mathsf {AM}}}$
protocols (we call this assumption GST), then
${{\mathsf {AM}}}\cap {{\mathsf {coAM}}} ={{\mathsf {NP}}}\cap {{\mathsf {coNP}}}$
. In a combinatorial language, this says:
Corollary 1.6. Both Schubert vanishing and Schubert nonvanishing have a positive rule, assuming GST and GRH.
It is worth comparing this result with other problems where a combinatorial interpretation (
${{\mathsf {\#P}}}$
formula) was recently refuted. These include squared
$S_n$
-characters [Reference Ikenmeyer, Pak and Panova28], Stanley’s inequality for linear extensions [Reference Chan and Pak16], and the Stanley–Yan matroid inequality [Reference Chan and Pak17]. In all these cases, the vanishing problem is not in
${{\mathsf {PH}}}$
(unless
${{\mathsf {PH}}}$
collapses), implying nonexistence of a combinatorial interpretation. Theorem 1.1 shows that a different approach is needed for Schubert coefficients.
2 Definitions and notation
2.1 Standard notation
We use
$\mathbb N=\{0,1,2,\ldots \} $
and
$[n]=\{1,\ldots ,n\}$
. Unless stated otherwise, the underlying field is always
${\mathbb {C}}$
. We use
$e_1,\ldots ,e_n$
to denote the standard basis in
${\mathbb {C}}^n$
, and
${\mathbf {0}}$
to denote the zero vector. We use bold symbols such as
${\boldsymbol{x}}$
and
${\boldsymbol {\alpha }}$
to denote sets and vectors of variables, and bars such as
$\overrightarrow x$
and
$\overrightarrow \alpha $
to denote complex vectors.
Recall the following standard notation for almost simple Lie groups, see [Reference Humphreys26]. We have the special linear group
$\mathsf {SL}_n({\mathbb {C}})$
, the odd special orthogonal group
$\mathsf {SO}_{2n+1}({\mathbb {C}})$
, the symplectic group
$\mathsf {Sp}_{2n}({\mathbb {C}})$
, and the even special orthogonal group
$\mathsf {SO}_{2n}({\mathbb {C}})$
. These groups correspond to root systems
$A_n$
,
$B_n$
,
$C_n$
, and
$D_n$
, and are called groups of type A, B, C, and D, respectively.
To distinguish the types, we use subscripts in Schubert coefficients, for example,
$c_{{\langle }A{\rangle }}(u,v,w)$
. We omit the dependence on the type when it is clear from the context. We use bullets to denote flags:
$F_\bullet = \{F_0 \subset F_1 \subset \ldots \subset F_n = V\}$
is a complete flag in V if
$\dim F_i = i$
.
2.2 Computational notation
For a polynomial
$g\in \mathbb Z[x_1,\ldots ,x_n]$
, let
$\deg (g)$
denote the degree of g, and let
$s(g)$
denote the sum of bit-lengths of coefficients in g. The size of the polynomial g is defined as
$$ \begin{align*}\phi(g) {\hskip.06cm} := {\hskip.06cm} \deg(g) {\hskip.06cm} + {\hskip.06cm} s(g). \end{align*} $$
For a collection of polynomials
$\overrightarrow f = (f_1,\ldots , f_m)$
as in (1.4), the size is defined as
$$ \begin{align*}\phi\big(\overrightarrow f\big) {\hskip.06cm} := {\hskip.06cm} \sum_{i=1}^{m} {\hskip.06cm} \deg(f_i) {\hskip.06cm} + {\hskip.06cm} \sum_{i=1}^{m} {\hskip.06cm} s(f_i). \end{align*} $$
For a matrix M with polynomial entries, the size
$\phi (M)$
is the sum of sizes of these polynomials.
2.3 Algebraic combinatorics background
In type A, the Weyl group is
$\mathcal W\simeq S_n$
and the length function is given by the number of inversions
${\mathrm {inv}}(w) :=\#\{(i,j) {\hskip .06cm} : {\hskip .06cm} w(i)>i, {\hskip .06cm} 1\le i<j\le n\}$
. The longest element is
$w_\circ =(n,n-1,\ldots ,1)$
. A permutation
$w\in S_n$
is said to have a descent at i, if
$w(i)> w(i+1)$
. Denote by
${\mathrm {Des}}(w)$
the set of descents of w, and by
${\mathrm {des}}(\sigma ):=|{\mathrm {Des}}(\sigma )|$
the number of descents. The Rothe diagram is defined as
and note that 
.
In types
$B/C$
, we have
$\mathcal W\simeq S_n\ltimes \mathbb Z_2^n$
, and the elements are represented as signed permutations, for example,
$(4,-{3},5, -{1},2)\in \mathcal W_{C_5}$
. In type D, we have
$\mathcal W\simeq S_n\ltimes \mathbb Z_2^{n-1}$
, and the elements are represented as signed permutations with an even number of negative signs, as in the example above. See [Reference Björner and Brenti12] for analogues of inversions and descents in other types, and note that the first four conditions in
$\S $
1.6 extend verbatim.
2.4 Complexity background
As we mentioned in the introduction, the paper can be completely understood without the use of complexity theory, since Main Theorem 1.1 easily follows from the (algebraic) Main Lemma 1.4. Still, for the purposes of motivation, we assume the reader is familiar with basic complexity theory and relationships between standard complexity classes:
${{\mathsf {P}}}$
,
${{\mathsf {BPP}}}$
,
${{\mathsf {NP}}}$
,
$\Sigma ^{{\text {p}}}_m$
,
$\Pi ^{{\text {p}}}_m$
,
${{\mathsf {PH}}}$
,
${{\mathsf {PSPACE}}}$
and
${{\mathsf {EXPSPACE}}}$
. We refer to [Reference Arora, Barak and Complexity6, Reference Goldreich20] for the background.
Let us elaborate on the class
${{\mathsf {AM}}}$
and its complement
${{\mathsf {coAM}}}$
, due to their prominence in the paper. One can view complexity problems as interactive proofs, with quantifiers describing communications between a prover and verifier. When we have a
${{\mathsf {BPP}}}$
verifier, that is, when the verifier (Arthur) has powers to flip coins and the prover (Merlin) has unlimited computational powers. Such communication is called the Arthur–Merlin protocol. The number of quantifiers becomes the number of messages between the prover and the verifier.
The complexity class
${{\mathsf {AM}}}$
is a class of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol with two messages, see, for example, [Reference Arora, Barak and Complexity6,
$\S$
8.2]. Recall the inclusions
$$ \begin{align*}{\mathsf{NP}} \ \subseteq \ {\mathsf{\exists{\cdot}BPP}} \ \subseteq \ {{\mathsf{AM}}} \ \subseteq \ \Pi^{{\text{p}}}_2 \ \subseteq \ {{\mathsf{PH}}}. \end{align*} $$
Famously, graph isomorphism is in
${{\mathsf {coAM}}}$
, since graph nonisomorphism can be established by a simple interactive protocol (see, e.g., [Reference Arora, Barak and Complexity6, Thm 8.13]). Other problems in
${{\mathsf {AM}}} \cap {{\mathsf {coAM}}}$
include code equivalence, ring isomorphism, permutation group isomorphism and tensor isomorphism; see the references in [Reference Pak and Robichaux52,
$\S$
1.5.1].
3 Proof of Main Lemma 1.4
3.1 Purbhoo’s criterion
Fix
$Y\in \{A,B,C,D\}$
and let
$\mathsf {G}= \mathsf {G}_Y$
be a semisimple algebraic group of type Y. In each case,
$\mathsf {G}$
is a matrix group lying in an ambient vector space V. Let
$\mathsf {N}$
denote the subgroup of unipotent matrices, so we have
$$ \begin{align*}\mathsf{N}\subset \mathsf{B}\subset\mathsf{G} \subset V. \end{align*} $$
Let
${\mathfrak n}$
denote the Lie algebra of
$\mathsf {N}$
. We think of
${\mathfrak n}$
as a subspace of V. Finally, for
$w\in \mathcal {W}$
, let
$Z_w:={\mathfrak n}\cap (w\mathsf {B}_{-}w^{-1})$
.
It is well-known and follows from [Reference Billey and Haiman10], that
$$ \begin{align} c_{{\langle}B{\rangle}}({u_1,\dots,u_k}) \, = \, 2^{a} {\hskip.06cm} c_{{\langle}C{\rangle}}({u_1,\dots,u_k}), \end{align} $$
where
$$ \begin{align*}a {\hskip.06cm} = {\hskip.06cm} {\zeta}(w_{\circ}u_k) {\hskip.06cm} - {\hskip.06cm} {\zeta}(u_1) {\hskip.06cm} - {\hskip.06cm} \ldots {\hskip.06cm} - {\hskip.06cm} {\zeta}(u_{k-1}) \end{align*} $$
and
${\zeta }(\pi )$
denotes the number of sign changes in the signed permutation
$\pi \in \mathcal {W}$
. This shows the vanishing problems in types B and C are equivalent. Thus for simplicity, we consider only types A, B, and D.
Lemma 3.1 (Purbhoo’s criterion [Reference Purbhoo57, Cor. 2.6]).
For generic
$\rho _1,\ldots ,\rho _k\in \mathsf {N}\subset \mathsf {G}$
, we have:
$$\begin{align*}c(u_1,\ldots,u_k){\hskip.06cm}> {\hskip.06cm} 0 \quad \Longleftrightarrow \quad \rho_1 R_{u_1}\rho_1^{-1}{\hskip.06cm} + {\hskip.06cm} \ldots {\hskip.06cm} + {\hskip.06cm} \rho_k R_{u_k}\rho_k^{-1} \, = \, \rho_1 R_{u_1}\rho_1^{-1}{\hskip.06cm} \oplus {\hskip.06cm} \ldots {\hskip.06cm} \oplus {\hskip.06cm} \rho_k R_{u_k}\rho_k^{-1}. \end{align*}$$
Generalizing the number of inversions condition in
$\S $
1.6(1), the dimension condition says that
$$ \begin{align} c(u_1,\ldots,u_k) {\hskip.06cm} = {\hskip.06cm} 0 \quad \text{ if } \quad {\mathrm{inv}}(u_1)+\dots+{\mathrm{ inv}}(u_k) {\hskip.06cm} \ne {\hskip.06cm} \dim({\mathfrak n}). \end{align} $$
Thus it suffices to restrict to the case
${\mathrm {inv}}(u_1)+\ldots +{\mathrm { inv}}(u_k)=\dim ({\mathfrak n})$
. In that setting,
$$\begin{align*}c(u_1,\ldots,u_k){\hskip.06cm}> {\hskip.06cm} 0 \quad \Longleftrightarrow \quad \rho_1 R_{u_1}\rho_1^{-1}{\hskip.06cm} + {\hskip.06cm} \ldots {\hskip.06cm} + {\hskip.06cm} \rho_k R_{u_k}\rho_k^{-1} \, = \, {\mathfrak n}. \end{align*}$$
Using Lemma 3.1, it suffices to determine the dimension of the vector space
$H:=\rho _1 R_{u_1}\rho _1^{-1}{\hskip .06cm} + {\hskip .06cm} \ldots {\hskip .06cm} + {\hskip .06cm} \rho _k R_{u_k}\rho _k^{-1}$
for generic
$\rho _i\hskip .03cm$
. In
$\S $
3.3, we describe how to construct these
$\rho _i\hskip .03cm$
. In
$\S $
3.2, we describe how to construct bases for these
$R_{u_i}\hskip .03cm$
. In
$\S $
3.4, we combine these constructions to obtain bases for each summand
$\rho _i R_{u_i}\rho _i^{-1}$
. From these we obtain vectors
$\pi _j$
which generate H.
In
$\S $
3.5, we prove Lemma 1.4 in two parts. We construct a system of equations to test whether these
$\pi _j$
are linearly dependent. By Lemma 1.4 and the dimension condition, if
$\pi _j$
are linearly dependent, the corresponding coefficient vanishes. Next we form a square matrix M with columns
$\pi _j$
and test if M is invertible. By Lemma 1.4 and the dimension condition (3.2), if M is nonsingular, the corresponding coefficient is positive.
Our equations are stated in terms of formal parameters to ensure generic choices are made. Thus in each case we test satisfiability of the systems over the appropriate function field.
3.2 Root systems
In each type, the Weyl group
$\mathcal {W}$
is generated by reflections
$r_\gamma $
, where
$\gamma $
are roots in a root system
$\Phi $
. The root system
$\Phi $
is partitioned in terms of its positive and negative roots:
$\Phi =\Phi _+\sqcup \Phi _-$
. In Table 1, we recall
$\Phi _+$
, where
$e_i$
denotes the i-th elementary basis vector in
$\mathbb {C}^n$
.
Table 1 Positive roots and corresponding matrix entries.
For ease of notation, define the integer
$N({\mathsf {G}})$
, where
$$\begin{align*}N({\mathsf{G}}) \, = \, \begin{cases} {\hskip.06cm} n & \text{ if } \ \mathsf{G}=\mathsf{SL}_n({\mathbb{C}}),\\ {\hskip.06cm} 2n+1 & \text{ if } \ \mathsf{G}=\mathsf{SO}_{2n+1}({\mathbb{C}}),\\ {\hskip.06cm} 2n & \text{ if } \ \mathsf{G}=\mathsf{SO}_{2n}({\mathbb{C}}). \end{cases} \end{align*}$$
To each
$\gamma \in \Phi _+\hskip .03cm$
, we wish to associate a particular
$m\times m$
matrix, where
$m=N({\mathsf {G}})$
. Define the subset
$U({\mathsf {G}})\subset [m]\times [m]$
as in Table 1. We construct a bijection
$\phi :U(\mathsf {G})\rightarrow \Phi _+$
as follows.
(A) For
$\mathsf {SL}_n$
take
$\phi (i,j):=e_i-e_j\hskip .03cm$
.
(B) For
$\mathsf {SO}_{2n+1}$
take
$$\begin{align*}\phi(i,j) \, := \, \begin{cases} \ \hskip.03cm e_i+e_j & \ \text{ if } \ j\leq n\\\ {\hskip.06cm} e_i-e_{2n+2-j} & \ \text{ if } \ n+1<j\\\ {\hskip.06cm} e_i & \ \text{ if } \ j=n+1 \\ \end{cases} \end{align*}$$
(D) For
$\mathsf {SO}_{2n}$
take
$$\begin{align*}\phi(i,j) \, := \, \begin{cases} e_i+e_j & \ \text{ if } \ j\leq n\\ e_i-e_{2n+1-j} & \ \text{ if } \ n<j \end{cases} \end{align*}$$
Thus for every positive root
$\gamma \in \Phi _+$
we define
$\mathrm {E}_{\gamma }'$
to be the
$m\times m$
matrix with a
$1$
in position
$\phi ^{-1}(\gamma )$
and
$0$
elsewhere. For
$\mathsf {SL}_n$
let
$\mathrm {E}_{\gamma }:=\mathrm {E}_{\gamma }'\hskip .03cm$
. For
$\mathsf {SO}_{2n+1}$
and
$\mathsf {SO}_{2n}\hskip .03cm$
, let
$\mathrm {E}_{\gamma }:=\mathrm {E}_{\gamma }'-\mathrm {D}_{m}(\mathrm {E}_{\gamma }')^{T}\mathrm {D}_{m}\hskip .03cm$
, where
$\mathrm {D}_{m}$
is the antidiagonal matrix.
3.3 Generic unipotent subgroup elements
Let
$m:=N({\mathsf {G}})$
. We now describe how to construct an upper unitriangular
$m\times m$
matrix
${\mathrm{K}}=(\kappa _{ij})$
which lies in
$\mathsf {N}\subset \mathsf {B}\subset \mathsf {G}$
. Define:
$$\begin{align*}\kappa_{ij}= \begin{cases} \, \alpha_{ij} & \text{ if } \ i<j \ \text{ and } \ (i,j)\in U(\mathsf{G}) \hskip.03cm,\\ \, z_{ij} & \text{ if } \ i<j \ \text{ and } \ (i,j)\not\in U(\mathsf{G}) \hskip.03cm,\\ \, 1 & \text{ if } \ i=j\hskip.03cm,\\ \, 0 & \text{ if } \ i>j. \end{cases} \end{align*}$$
Here we treat
$\alpha _{ij}$
as parameters and
$z_{ij}$
as variables.
Note we have no additional dependencies placed on
$\kappa _{ij}$
to ensure that
$\kappa \in \mathsf {G}$
for
$\mathsf {G}=\mathsf {SL}_n({\mathbb {C}})$
. For
$\mathsf {G}=\mathsf {SO}_{2n+1}({\mathbb {C}})$
and
$\mathsf {G}=\mathsf {SO}_{2n}({\mathbb {C}})$
, let
$\mathrm {D}_{m}$
be the antidiagonal matrix. To ensure
$\kappa \in \mathsf {G}$
, we need
$$\begin{align*}{{\mathrm{K}}}^T \cdot {\mathrm{D}_{m}}\cdot {{\mathrm{K}}} \, = \, {\mathrm{D}_{m}} \quad \text{ and } \quad \det({{\mathrm{K}}}) {\hskip.06cm} = {\hskip.06cm} 1. \end{align*}$$
Clearly,
$\det ({\mathrm{K}}) = 1$
is already satisfied. Then we need only to impose
${\mathrm{K}}^T \cdot {\mathrm {D}_{m}}\cdot {\mathrm{K}} \, = \, {\mathrm { D}_{m}}\hskip .03cm$
.
3.4 Main construction
Let
$m=N({\mathsf {G}})$
. In light of Lemma 3.1, we consider the vector space
$$\begin{align*}H \, = \, \rho_1 R_{u_1}\rho_1^{-1} {\hskip.06cm} + {\hskip.06cm} \dots {\hskip.06cm} + {\hskip.06cm}\rho_k R_{u_k}\rho_k^{-1}. \end{align*}$$
Let
$d:=\dim {\mathsf {G}/\mathsf {B}}$
and note that
$\dim \mathfrak {n}=|U({\mathsf {G}})|=d\leq \binom {m}{2}=O(m^2)$
. By the dimension condition, we can assume
$$ \begin{align} {\mathrm{inv}}(u_1) {\hskip.06cm} + {\hskip.06cm} \ldots {\hskip.06cm} + {\hskip.06cm} {\mathrm{inv}}(u_k) \, = \, d. \end{align} $$
Further, we can assume that
${\mathrm {inv}}(u_i)\geq 1$
for all
$i\in [k]$
, so we have
$k\leq d$
.
Recall that for
$w\in \mathcal {W}$
, we have
$Z_w={\mathfrak n}\cap (w\mathsf {B}_{-}w^{-1})$
. Equivalently,
$Z_w$
is the subspace of
${\mathfrak n}$
generated by basis elements
$\mathrm {E}_\gamma $
for
$\gamma \in \Phi _+(w)$
, where
$$\begin{align*}\Phi_+(w)\, := \big\{\beta\in \Phi_+ \, : \, w^{-1}\beta\not\in \Phi_+ \big\}. \end{align*}$$
Thus for
$i\in [k]$
, we construct bases for the
$R_{u_i}$
as follows:
$$ \begin{align*} S_{u_i} \, & := \, \big\{x_{{\gamma},i} {\hskip.06cm} \mathrm{E}_{\gamma} \, : \, \gamma\in \Phi_+(u_i)\big\}. \end{align*} $$
Since
${\mathrm {inv}}(u_i)=|\Phi _+(u_i)|$
for
$i\in [k]$
and we assumed (3.3), the collection
$\cup _{i\in [k]} S_{u_i}$
has
$d= O(m^2)$
elements. Let
${\boldsymbol{x}}:= \big \{x_{\gamma ,i}\big \}$
be the set of those variables appearing in the collection. We have:
$$ \begin{align} \sum_{i=1}^k{\hskip.06cm} {\mathrm{inv}}(u_i) \, = \, \sum_{i=1}^k {\hskip.06cm} \dim(R_{u_i}) \, = \, \sum_{i=1}^k \big|S_{u_i}\big| {\hskip.06cm} = {\hskip.06cm} d. \end{align} $$
We now construct generic matrices
$\rho _1,\ldots ,\rho _k \in \mathsf {N}$
according to
$\S $
3.3 above, in terms of formal parameters
$\alpha _{j\ell }^{(i)}$
and variables
$z_{j\ell }^{(i)}$
. Define
${\boldsymbol {\alpha }}:=\big \{\alpha _{j\ell }^{(i)}\big \}$
and
${\boldsymbol{x}}:=\big \{z_{j\ell }^{(i)}\big \}$
to be the sets of parameters and variables, respectively, appearing in some
$\rho _i$
, where
$i\in [k]$
. Then
$$\begin{align*}|{\boldsymbol{\alpha}}|=|{\boldsymbol{z}}|\le k\cdot m^2 \leq d\cdot m^2= O(m^4).\end{align*}$$
By the construction in
$\S $
3.3, each matrix
$\rho _i$
is an upper triangular
$m\times m$
matrix with linear entries. Thus it has size
$O(m^2)$
, where the size is defined in
$\S $
2.2.
Now for each
$i\in [k]$
, form the upper unitriangular matrix
$\widetilde {\rho _i}$
whose
$(j,\ell )$
entry for
$j<\ell $
is the variable
$y_{j\ell }^{(i)}$
. Define the set of variables
${\boldsymbol{y}}:=\big \{\hskip .03cm y_{j\ell }^{(i)} {\hskip .06cm} : {\hskip .06cm} i\in [k], {\hskip .06cm} 1\leq j<\ell \leq m \big \}$
. For all
$i\in [k]$
, construct bases for
$\rho _i R_{u_i}\widetilde {\rho _i}$
as follows:
$$ \begin{align*} T_{u_i} \, &:= \, \rho_i \hskip.03cm S_{u_i} \hskip.03cm \widetilde{\rho_i} \, = \, \big\{ \rho_i \cdot g \cdot \widetilde{\rho_i} {\hskip.06cm} : {\hskip.06cm} g \in S_{u_i}\big\}. \end{align*} $$
By (3.4), we have
$|T_{u_1}|+\ldots + |T_{u_k}|=d$
.
Consider the map
$\tau $
on
$m\times m$
matrices defined by restricting to entries in positions
$U({\mathsf {G}})$
. Recall that for
$\mathsf {G}=\mathsf {SL}_n$
, we have
${\mathfrak n}$
is the set of strictly upper triangular matrices. For
$\mathsf {G}=\mathsf {SO}_{2n+1}$
or
$\mathsf {G}=\mathsf {SO}_{2n}$
, we have
${\mathfrak n}$
is the set of strictly upper triangular matrices which are skew symmetric with respect to reflection about the main antidiagonal. By the definition of
${\mathfrak n}$
, every
$m\times m$
matrix in
${\mathfrak n}$
is determined by its entries in positions
$U({\mathsf {G}})$
. Thus,
$\dim (T_{u_i})=\dim \big (\tau (T_{u_i})\big )$
for each
$i\in [k]$
. Let
$$ \begin{align*}T \, := \, \bigcup_{i\in[k]} {\hskip.06cm} \tau(T_{u_i})\hskip.03cm, \end{align*} $$
and write
$T=\{\pi _i {\hskip .06cm}:{\hskip .06cm} i\in [d]\}$
. Since
$|U({\mathsf {G}})|=d$
, we may view each
$\pi _i\in T$
as a d-vector.
3.5 Proof of Main Lemma 1.4
As mentioned above, by the dimension condition (3.2), we can assume that (3.3) holds, and that
${\mathrm {inv}}(u_i)\geq 1$
for all
$i\in [k]$
. Define
$\widetilde {\rho _i}$
for all
$i\in [k]$
, and let
$T=\big \{\pi _i{\hskip .06cm}: {\hskip .06cm} i\in [d]\big \}$
as in
$\S $
3.4 above. We prove the two parts of the lemma separately.
First part of the lemma.
For the vanishing result, we analyze the negation of the condition in Lemma 3.1:
$$ \begin{align} \rho_1 R_{u_1}\rho_1^{-1} {\hskip.06cm} + {\hskip.06cm} \dots {\hskip.06cm} + {\hskip.06cm} \rho_k R_{u_k}\rho_k^{-1} \, \subsetneq \, {\mathfrak n}. \end{align} $$
Note that (3.5) holds if and only if T is linearly dependent for
$\widetilde {\rho _i}=\rho _i^{-1}$
, with
$\rho _i\in \mathsf {N}$
for each
$i\in [k]$
.
We introduce two new sets of variables:
${{\boldsymbol{q}}}=\{q_{i}{\hskip .06cm}:{\hskip .06cm} i\in [d]\}$
and
${{\boldsymbol{s}}}=\{s_{i}{\hskip .06cm}:{\hskip .06cm}i\in [d]\}$
. Consider a polynomial system
$\mathcal {T}(u_1,\ldots ,u_k)$
defined as follows:
$$ \begin{align*}\left\{ \ \begin{aligned} & \rho_i\cdot \widetilde{\rho_i}{\hskip.06cm} = {\hskip.06cm} \mathsf{Id}_{m} \ \text{ for } \ i\in[k], \\ & \rho_i^T \cdot {\mathrm{D}_{m}}\cdot \rho_i \, = \, {\mathrm{D}_{m}} \ \text{ for } \ i\in[k], \, \text{ if } \ \mathsf{ G}=\mathsf{SO}_{m}\hskip.03cm,\\ &\sum_{i=1}^d {\hskip.06cm} q_i\cdot\pi_i {\hskip.06cm} = {\hskip.06cm} 0\hskip.03cm, \\ & \sum_{i=1}^d {\hskip.06cm} q_i\cdot s_i{\hskip.06cm} = {\hskip.06cm} 1. \end{aligned} \right. \end{align*} $$
Here
$\mathcal {T}(u_1,\ldots ,u_k)$
uses variables
${\boldsymbol{x}}\cup {\boldsymbol{y}}\cup {\boldsymbol{x}}\cup {\boldsymbol{q}}\cup {{\boldsymbol{s}}}$
and parameters
${\boldsymbol {\alpha }}$
. Note that entries in
$\pi _i\in T$
are cubic monomials. Thus the whole system
$\mathcal {T}(u_1,\ldots ,u_k)$
has size
$O(m^{5})$
. See Table 4 for details regarding the size computations.
Now, the proper containment in (3.5) holds if and only if
$\mathcal {T}(u_1,\ldots ,u_k)$
is satisfiable over
$\mathbb {C}({\boldsymbol {\alpha }})$
. We note the following statements are equivalent since the parameters
$\alpha $
are algebraically independent:
-
1.
$\mathcal {T}(u_1,\ldots ,u_k)$
has a solution over
$\mathbb {C}({\boldsymbol {\alpha }})$
, -
2.
$X\times _{\mathrm {Spec}(\mathbb {C}[{\boldsymbol {\alpha }}])} \mathrm {Spec}\,(\overline {\mathbb {C}({\boldsymbol {\alpha }})})\neq \emptyset $
, -
3.
$X\times _{\mathrm {Spec}(\mathbb {C}[{\boldsymbol {\alpha }}])} \mathrm {Spec}(\,{\mathbb {C}({\boldsymbol {\alpha }}))}\neq \emptyset $
, -
4. the general fiber of X →Spec(ℂ[α ]) is nonempty, and
-
5.
$\mathcal {T}(u_1,\ldots ,u_k)$
has a solution over
$\mathbb {C}$
for a generic choice of evaluations
$\overrightarrow \alpha $
of
${\boldsymbol {\alpha }}$
.
The equivalence of (i) and (ii), (ii) and (iii), and (iv) and (v) are straightforward. The equivalence of (iii) and (iv) follows from [62, Lemma 37.24.1] and [62, Lemma 37.24.2]).
Therefore, by Lemma 3.1 and (3.1), the problem
SchubertVanishing
$(Y)$
reduces to
HNP
for every type
$Y\in \{A,B,C,D\}$
.
Second part of the lemma.
To prove the nonvanishing result, we analyze the condition in Lemma 3.1:
$$ \begin{align} \rho_1 R_{u_1}\rho_1^{-1} {\hskip.06cm} + {\hskip.06cm} \dots {\hskip.06cm} + {\hskip.06cm} \rho_k R_{u_k}\rho_k^{-1} \, = \, {\mathfrak n}. \end{align} $$
Let M be the
$d\times d$
matrix formed by the vectors in T. Then (3.6) holds if and only if M is invertible for
$\widetilde {\rho _i}=\rho _i^{-1}$
with
$\rho _i\in \mathsf {N}$
for each
$i\in [k]$
.
Let
$\widetilde {M}=(t_{ij})$
be a
$d\times d$
matrix of variables. Define the set of variables
${{\boldsymbol{t}}}=\{t_{ij}{\hskip .06cm} : i,j\in [d]\}$
. Let
$\mathcal {S}(u_1,\ldots ,u_k)$
be the system defined as follows:
$$ \begin{align*}\left\{ \ \begin{aligned} & \rho_i\cdot \widetilde{\rho_i}{\hskip.06cm} = {\hskip.06cm} \mathsf{Id}_{m}{\hskip.06cm} \text{ for } i\in[k],\\ & \rho_i^T \cdot {\mathrm{D}_{m}}\cdot \rho_i \, = \, {\mathrm{D}_{m}}{\hskip.06cm} \text{ for } i\in[k], \text{ if } \mathsf{ G}=\mathsf{SO}_{N},\\ & M \cdot \widetilde{M} {\hskip.06cm} = {\hskip.06cm} \mathsf{Id}_{d}{\hskip.06cm}. \end{aligned} \right. \end{align*} $$
Here the system
$\mathcal {S}(u_1,\ldots ,u_k)$
uses variables
${\boldsymbol{x}}\cup {\boldsymbol{y}}\cup {\boldsymbol{x}}\cup {\boldsymbol{t}}$
and parameters
${\boldsymbol {\alpha }}$
. Note that entries in M are cubic monomials. Thus the whole system
$\mathcal {S}(u_1,\ldots ,u_k)$
has size
$O(m^{6})$
. See Table 4 for details regarding the size computations.
Now, the equality in (3.6) holds if and only if the system
$\mathcal {S}(u_1,\ldots ,u_k)$
is satisfiable over
$\mathbb {C}({\boldsymbol {\alpha }})$
. As in the previous part, since the parameters in
${\boldsymbol {\alpha }}$
are algebraically independent, the system
$\mathcal {S}(u_1,\ldots ,u_k)$
has a solution over
$\mathbb {C}({\boldsymbol {\alpha }})$
if and only if
$\mathcal {S}(u_1,\ldots ,u_k)$
has a solution over
$\mathbb {C}$
for a generic choice of evaluations
$\overrightarrow \alpha $
of
${\boldsymbol {\alpha }}$
. Therefore, just as in the first part, by Lemma 3.1 and (3.1), the problem 
reduces to 
, for every type
$Y \in \{A,B,C,D\}$
.
4 Final remarks
4.1 Evolution of this paper
This paper grew out of a series of unpublished preprints and research announcements of the authors (aimed at somewhat different audiences), where we successively strengthened the results while we simultaneously streamlined and simplified the proofs. Below is a brief description of these preprints. This paper is the definitive version that we do not plan to modify.
The original preprint [Reference Pak and Robichaux49], v1, proved only the
${{\mathsf {coAM}}}$
inclusion in the Main Theorem 1.1 and only for types
$A,B,C$
. The proof was technical, employed the Hein–Sottile algebraic system, and did not cover type D. The presentation was aimed at complexity theorists and included results in the Blum–Shub–Smale (nonstandard) models of computing that were established using Purbhoo’s criterion: SchubertPositivity is in
${\mathsf {NP}}_{\mathbb {C}} \cap {\mathsf {P}}_{\mathbb {R}}\hskip .03cm$
. The latter results are included in the STOC’25 extended abstract based on [Reference Pak and Robichaux49], but are omitted in the current version of the paper.
In v2 of the same preprint [Reference Pak and Robichaux49], we added an extensive description of the prior combinatorial work on the subject. We also added a new Appendix C (joint with David Speyer) with a different algebraic system based on the Cayley transform. This proved the
${\mathsf {coAM}}$
inclusion for all types, in particular for type D.
In a companion paper [Reference Pak and Robichaux50] aimed at algebraic combinatorialists, we gave an extensive epistemological and theological discussion on the delicate subject of proving combinatorial results under standard assumptions from other areas. This paper is a short announcement with no new proofs.
Finally, the most recent preprint [Reference Pak and Robichaux52] gives a proof of Main Theorem 1.1 based on a technical new tool (Determinant Lemma 2.2). Here we are using Purbhoo’s criterion to prove that Schubert vanishing is in
${\mathsf {AM}}$
for all types. We also use this Determinant Lemma to resolve the type D case that was omitted in [Reference Pak and Robichaux49]. These tools proved crucial in our forthcoming paper [Reference Pak, Robichaux and Xu53], where we extend parts of Main Theorem 1.1 to enriched cohomology theories.
In this paper we are able to obtain a simple proof of both parts of Main Theorem 1.1, avoiding technicalities of the earlier preprints. Let us emphasize that this paper is the first version where we are able to take the intersection of k Schubert varieties, for all
$k\ge 3$
. While for many applications it is useful to have larger k, until now we were unable to give an algebraic system simple enough to prove the reduction to 
for nonconstant k.
4.2 Schubert polynomials
A combinatorial approach to Schubert coefficients is given by Schubert polynomials
$\mathfrak {S}_w\in \mathbb N[x_1,x_2,\ldots ]$
indexed by permutations
$w\in S_n\hskip .03cm$
. They were introduced by Lascoux and Schützenberger [Reference Lascoux and Schützenberger41], building on the earlier works by Demazure (1974) and Bernstein–Gelfand–Gelfand (1973). In type A, the translation is given by Borel’s ring isomorphism:
$$ \begin{align*}\Phi {\hskip.06cm} : \, H^{*}(\mathsf{G}/\mathsf{B}) {\hskip.06cm} \longrightarrow {\hskip.06cm} \mathbb Z[x_1,\ldots,x_n]/\langle e_i(x_1,\ldots,x_n) \, : \, i\in[n]\rangle\,, \end{align*} $$
where
$e_i$
are elementary symmetric polynomials. Schubert polynomials are polynomial representatives of Schubert classes:
$\mathfrak {S}_w:=\Phi (\sigma _w)$
. Then Schubert coefficients can be defined as multiplication constants:
$$ \begin{align*}\mathfrak{S}_u \cdot \mathfrak{S}_v \, = \, \sum_{w \hskip.03cm \in \hskip.03cm S_\infty} {\hskip.06cm} c^w_{u,v} {\hskip.06cm} \mathfrak{S}_w. \end{align*} $$
In this notation, the Schubert–Kostka numbers mentioned in
$\S $
1.6 are the coefficients
$[{\boldsymbol{x}}^\alpha ] \hskip .03cm \mathfrak {S}_u\hskip .03cm$
. We refer to [Reference Macdonald43, Reference Manivel44] for introductory surveys, [Reference Knutson33, Reference Knutson34] for overviews of recent results, and to [Reference Pak48,
$\S$
10] for computational complexity aspects. Let us mention that Schubert polynomials play a central role in algebraic combinatorics, but do not appear in the proof of Main Theorem 1.1.
4.3 Vanishing is exponentially likely
It is easy to see that asymptotically, Schubert coefficients are almost always zero. Indeed, for
$k=3$
in type A, we have
$\mathbb P[c^w_{u,v}>0]<c^{-n}$
for some
$c>1$
, where the probability is over uniform permutations
$u,v,w\in S_n\hskip .03cm$
. Recall the sufficient conditions for vanishing given in
$\S $
1.6, and take their complements. The result follows from the number of inversions necessary condition
${\mathrm {inv}}(u)+{\mathrm {inv}}(v) = {\mathrm {inv}}(w)$
and the asymptotic normality of the
${\mathrm {inv}}$
statistics on
$S_n\hskip .03cm$
, see, for example, [Reference Feller19,
$\S$
X.6].
Alternatively, Knutson’s descent cycling necessary condition states that we must have
${\mathrm {Des}}(u) \cap {\mathrm {Des}}(v) \cap {\mathrm {Des}}(w\hskip .03cm w_\circ )=\varnothing $
. Since distant descents are given by mutually independent fair coin flips, this condition also gives an exponential decay for the probability
$\mathbb P[c^w_{u,v}>0]$
, even if we condition on the number of inversions equality. Finally, the strong Bruhat order necessary condition
$u \leqslant w$
was studied asymptotically in [Reference Hammett and Pittel22]. Although only polynomial upper bounds are known, exponential decay is likely again.
4.4 Combinatorial interpretations
When it comes to finding combinatorial interpretations for Schubert coefficients, there are two ways to think of our results. On the one hand, as we mentioned in
$\S $
1.7, these are the first positive results obtained in full generality, suggesting that both Schubert vanishing and Schubert positivity have a positive rule, under standard assumptions. On the other hand, the AM protocols of this paper are far removed from the type of positive rule that people are interested in, see quotes in [Reference Pak and Robichaux52, Appendix B] and an extensive discussion in [Reference Pak and Robichaux50].
We should emphasize that the complexity of counting solutions of algebraic systems (1.4) remains a major open problem, so our approach cannot be extended to the problem of computing Schubert coefficients. Furthermore, in contrast with the Billey–Vakil and Hein–Sottile algebraic systems (see
$\S $
1.6), Purbhoo’s criterion applies only to the vanishing of Schubert coefficients.
4.5 Unconditional approaches
It is an interesting question whether the
$\mathrm{GRH}$
assumption in Theorem 1.1 can be weakened or completely removed. In fact, Koiran’s proof of Theorem 1.2 uses only an effective version of the Chebotarev density theorem given in [Reference Lagarias and Odlyzko40]. The latter assumes the
$\mathrm{GRH}$
or a slightly weaker assumption 
mentioned in the introduction. Despite recent advances in the area, it seems unlikely that the
$\mathrm{GRH}$
assumption can be removed from Theorem 1.3 which we crucially employ.
Table 2 Indices and Number of Positive Roots
Table 3 Parameter and Variable Size Analysis for
$\mathcal T(u_1,\ldots ,u_k)$
and
$\mathcal S(u_1,\ldots ,u_k)$
Table 4 Equation Size Analysis for
$\mathcal T(u_1,\ldots ,u_k)$
and
$\mathcal S(u_1,\ldots ,u_k)$
A Size Charts
We recall the values of
$N({\mathsf {G}})$
and
$U({\mathsf {G}})$
, as defined in
$\S $
3.2, for each
$\mathsf {G}$
.
Now we describe the size computations for the systems
$\mathcal T(u_1,\ldots ,u_k)$
and
$\mathcal S(u_1,\ldots ,u_k)$
in Main Lemma 1.4 for each group
$\mathsf {G}$
. In these systems, we assumed
$k\leq |U({\mathsf {G}})|$
, so
$k=O(n^2)$
in each case. Additionally, note that
$m=O(n)$
.
First we give the sizes of the variables and parameters used in the systems. In Table 3, the size measures the cardinality of the set.
Then we describe the sizes of the equations in the systems. In Table 4, the size is defined as in
$\S $
2.2. Below
$m=N({\mathsf {G}})$
and
$d=U({\mathsf {G}})$
.
Note that for
$\mathsf {G}=\mathsf {SL}_n$
, the equations in the second line in Table 4 are not used.
Acknowledgments
We are grateful to Kevin Purbhoo for sharing his insights which partially motivated this paper. We thank Sara Billey, Nickolas Hein, Minyoung Jeon, Allen Knutson, Leonardo Mihalcea, Greta Panova, Oliver Pechenik, Maurice Rojas, Mahsa Shirmohammadi, Alex Smith, Frank Sottile, Avi Wigderson, James Worrell, Weihong Xu, Alex Yong, and Paul Zinn-Justin for interesting discussions and helpful comments. We are especially grateful to David Speyer for suggesting we use the Cayley transform in types
$C/D$
, and for his insights leading to Appendix C in [Reference Pak and Robichaux49].
This paper was partially written when the first author was a member at the Institute of Advanced Study in Princeton, NJ. We are grateful for the hospitality.
Competing interest
The authors have no competing interests to declare.
Financial support
The first author was partially supported by the NSF grant CCF-2302173. The second author was partially supported by the NSF MSPRF grant DMS-2302279.
. On the other hand, Tarui’s theorem gives that 
Open access
