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.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

(3.1) $$ \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

(3.2) $$ \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

(3.3) $$ \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:

(3.4) $$ \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:

(3.5) $$ \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. 1. $\mathcal {T}(u_1,\ldots ,u_k)$ has a solution over $\mathbb {C}({\boldsymbol {\alpha }})$ ,

2. 2. $X\times _{\mathrm {Spec}(\mathbb {C}[{\boldsymbol {\alpha }}])} \mathrm {Spec}\,(\overline {\mathbb {C}({\boldsymbol {\alpha }})})\neq \emptyset $ ,

3. 3. $X\times _{\mathrm {Spec}(\mathbb {C}[{\boldsymbol {\alpha }}])} \mathrm {Spec}(\,{\mathbb {C}({\boldsymbol {\alpha }}))}\neq \emptyset $ ,

4. 4. the general fiber of X →Spec(ℂ[α ]) is nonempty, and

5. 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:

(3.6) $$ \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.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)$