{"id":"dfce3ae9-4d7a-4c51-be3b-2ce43275fc78","arxiv_id":"2412.02064","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Schubert coefficient vanishing is shown to be decidable by an Arthur-Merlin protocol (in coAM) under GRH for all classical Lie types, placing it in the polynomial hierarchy for the first time.","lead":"This paper proves that deciding whether a Schubert coefficient is zero is an Arthur-Merlin problem (in coAM) assuming the generalized Riemann hypothesis, for all classical Lie types. That puts the long-open vanishing problem inside the polynomial hierarchy for the first time.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 2's Eq(B) rows for SO/Sp list only diagonal equations, not B^T J B = J; if EY omits them, Appendix C's type-D reduction over-approximates Borel membership and Lemma C.1 is unproven.","rationale":"The central theorem depends on the reduction from nonvanishing of Schubert coefficients to HNP. For type D, Appendix C is the only source: the main-body lifted formulations explicitly exclude type D (Remark A.2). I checked the algebraic encoding in Appendix C and found that Table 2's Borel equations, as printed, are weaker than the defining relation B^T J B=J for the orthogonal and symplectic Borel subgroups. This is an internal inconsistency: the prose says B^T J B=J should be imposed, but the table used in E_Y omits it. One concrete separator is the upper-triangular matrix I+E_{12} in SO_4, which satisfies the printed diagonal equations but is not in SO_4. This is exactly the type-specific risk the reader identified. The external components (the HNP theorem, Kleiman transversality, and the type A/B/C constructions) are independent and not in question. Because the gap is localized and likely repairable by adding O(n^2) polynomial equations, I do not move the verdict; it remains CONDITIONAL pending verification or correction of Appendix C's Table 2.","tokens_in":32554,"tokens_out":22177,"duration_ms":210966,"concrete_test":"Re-derive Table 2 for SO_4 by expanding B^T J B = J with J=D_4 and B upper triangular, and check whether the printed Eq(B) row is equivalent to it. Specifically, verify whether B=I+E_{12} satisfies Table 2's equations but violates B^T J B=J; if so, the full matrix equation B^T J B=J must be added to E_Y, and for SO_{2n+1} the determinant condition must be corrected to b_{n+1,n+1}=1. A confirmatory run on a small type-D instance where c^w_{u,v}=0 but the over-approximated printed system has a solution would settle the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Appendix C's claim (Lemma C.1) that the HNP system E_Y(u,v,w) is satisfiable over C(y,z) iff c^w_{u,v}>0. For this to hold, the equations in Table 2 must exactly encode membership in the Borel subgroup B of G. As printed, the Eq(B) rows for SO_{2n+1}, Sp_{2n}, and SO_{2n} consist only of the diagonal conditions b_{ii} b_{(N+1-i)(N+1-i)}=1, plus in the SO_{2n+1} row an apparent determinant-index error (b_{nn}=1 instead of b_{n+1,n+1}=1). These diagonal conditions are necessary but not sufficient. For example, for SO_4 with J=D_4, the upper-triangular matrix B=I+E_{12} satisfies all printed diagonal equations but violates B^T J B=J, so B is not in SO_4. Since C.4 constructs E_Y from Eq(P_i) and Eq(Q_i) 'in Table 2', the system as written permits Borel factors outside G. The prose says B^T J B=J is imposed, but that matrix equation is not included in the table; if it is also absent from E_Y, the reduction tests a larger variety and the 'iff' in the proof of Lemma C.1 fails for type D. The determinant condition for SO_{2n+1} should read b_{n+1,n+1}=1, which further indicates the Borel encodings are not yet reliable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the decision problem SchubertVanishing: given permutations u,v,w in the Weyl group of one of the classical types A,B,C,D, is the Schubert structure constant c^w_{u,v} equal to 0? The main theorem (Theorem 1.4) states that, assuming GRH, SchubertVanishing is in coAM, and hence in Sigma_2^p, for types A,B,C,D. The proof reduces the negation of SchubertVanishing to the Parametric Hilbert Nullstellensatz (HNP), which was recently shown to be in AM by Ait El Manssour et al. For types A,B,C the reduction is via explicit lifted formulations whose number of solutions over C(y,z) equals the corresponding Schubert coefficient (Propositions 5.2, 6.2, 6.3). For type D the paper relies on a new appendix (joint with Speyer) that constructs a uniform HN system for all classical types from the double-coset description of Schubert intersections. The paper also contains BSS-model results and a discussion of conjectures around #P-hardness of Schubert coefficients.","tokens_in":32773,"tokens_out":12310,"duration_ms":114820,"significance":"The main result, if correct, would be the first nontrivial upper bound in the polynomial hierarchy for the Schubert vanishing problem, a problem for which only PSPACE and C=P bounds were previously known. The construction is explicit and polynomial-sized, and it builds on the recent HNP result without circularity: the reduction uses Kleiman transversality, the Billey-Haiman relation, and external theorems, and does not assume the vanishing problem. The paper also makes the case that the vanishing problem is unlikely to be coNP-hard under standard derandomization assumptions. The main caveat is that the type D case depends on the Appendix C encoding of Borel subgroups; as printed, that encoding is incomplete, so the central claim as stated is not yet fully supported.","major_comments":[{"comment":"In the rows for SO_{2n+1}, Sp_{2n}, and SO_{2n}, the set Eq(B) is printed as only the diagonal conditions b_{ii} b_{(2n+2-i)(2n+2-i)}=1 (plus a determinant condition in the odd orthogonal case). These conditions are necessary but not sufficient for B to lie in G: for example, for SO_4 with J=D_4, the upper-triangular matrix B=I+E_{12} satisfies all printed diagonal equations but violates B^T J B=J. Since the system E_Y(u,v,w) in C.4 is explicitly assembled from Eq(P_i) and Eq(Q_i) 'in Table 2', the satisfiability of E_Y as written is not equivalent to the non-emptiness of the double-coset intersection Xi in Equation (C.2). Therefore the 'if and only if' in the proof of Lemma C.1 is not established for types B, C, and D. The prose in C.3 says that B^T J B=J is imposed, but this matrix equation never appears in Table 2 or in C.4. The authors should either include the full matrix equation in E_Y (this adds O(n^2) equations, preserving the HNP reduction) or prove that the enlarged system has the same satisfiability over C(y,z). As printed, this is a load-bearing gap in the proof of Theorem 1.4 for type D.","section":"Appendix C, Table 2 and C.4"}],"minor_comments":[{"comment":"The determinant condition is printed as 'bnn=1'; in the stated conventions this should be b_{n+1,n+1}=1, and the surrounding text 'det(B)=bnn' in C.3 has the same indexing issue. This typo, together with the missing matrix equations, suggests the table needs a careful rewrite.","section":"Appendix C, Table 2, SO_{2n+1} row"},{"comment":"The parameter set for M is listed as {m_{ij}}_{i+j <= 2n+1} and the text says t=2n^2+n, but equation (A.2) forces the antidiagonal entries m_{i,2n+1-i} to vanish, so the dimension of so(2n) is n(2n-1)=2n^2-n. Please correct the parameter count or the index bound.","section":"Appendix A and Table 1, SO_{2n}"},{"comment":"The phrase 'whether c^w_{u,v} in #P' should be phrased as whether the function (u,v,w) |-> c^w_{u,v} is in #P, since a coefficient is an integer rather than a counting function.","section":"Abstract"},{"comment":"The statement that Theorem 1.4 implies 'there are currently no other tools' to attack Conjecture 1.3 is too strong; the theorem rules out a particular route, not the existence of all possible tools.","section":"Section 2.2(2)"}],"recommendation":"major_revision","confidential_remarks":"The Appendix C issue is serious but fixable. If the authors include the full orthogonal/symplectic Borel equations, the system remains polynomial-sized and the main theorem would go through. I therefore do not recommend rejection, but the current version should not be accepted with the table as written. The type D appendix reads as if the table is a compressed summary of the equations, but C.4 refers to it as the definition of the system; this ambiguity needs to be resolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first proof that Schubert vanishing sits in the polynomial hierarchy, and the main reduction is clean. The type D appendix is the piece to scrutinize; the published Table 2 under-specifies the Borel equations, and the stress-test concern is real.\n\nThe genuinely new content is the reduction of nonvanishing of Schubert coefficients to the Parametric Hilbert Nullstellensatz of Ait El Manssour et al. The lifted systems for types A, B, C are explicit, polynomial-sized, and counted correctly. The trick of using Cayley transforms for generic group elements is nice. No circularity: the HNP-in-AM result is external, and the Schubert-side facts are standard (Kleiman transversality, Billey-Haiman in type B). The paper also does real service in explaining what the new upper bound rules out: under GRH, Schubert vanishing is not NP-complete and a C=P-completeness route is blocked.\n\nThe soft spots are concentrated in Appendix C. The table for Borel elements in types B/C/D lists only the diagonal equations b_ii b_{(N+1-i)(N+1-i)}=1, not the matrix equation B^T J B = J. The prose in C.3 clearly says that matrix equation is imposed, and the counterexample in the stress-test (B=I+E_{12} in SO_4) shows the diagonal conditions alone do not force B to lie in G. So the table, which is what the proof of Lemma C.1 references as Eq(B), does not exactly encode Borel membership. There is also a typo: in the SO_{2n+1} row, the determinant condition should be b_{(n+1)(n+1)}=1, not b_nn=1. These are fixable, but they sit precisely at the load-bearing point of the type D construction, and a referee should ask for the full equations to be written out.\n\nThe type B and C lifted formulations are presented more tersely; they look right, but the count in Proposition 6.3 depends on the Billey-Haiman relation, and I did not verify every matrix identity. That is a moderate, not fatal, concern.\n\nNet: the main theorem is a substantive advance and the argument is honest. The A/B/C part should hold up; the type D appendix needs a corrected and complete Table 2 before the paper is accepted as written. This deserves serious peer review, not a desk reject, and I would cite it if I worked on Schubert positivity or GCT.","headline":"First PH upper bound for Schubert vanishing via a clean reduction to parametric Nullstellensatz; the type D appendix is the soft spot and Table 2 needs fixing.","tokens_in":33424,"tokens_out":3568,"would_cite":true,"duration_ms":34516,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["14M15","05E99","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The vanishing of Schubert coefficients is in coAM under GRH, placing it in the second level of the polynomial hierarchy, for the first time.","keywords":["Schubert coefficients","vanishing problem","complexity classes","polynomial hierarchy","coAM","Hilbert Nullstellensatz","lifted formulations","classical Lie types"],"falsifier":"Find a concrete triple of permutations $u,v,w$ in type D for which the system $E^D(u,v,w)$ of Appendix C has a solution over $\\mathbb{C}(y,z)$ but the Schubert coefficient $c^w_{u,v}(D)$ is zero, or vice versa. Because the system size is $O(n^2)$, this can be checked by explicit computation for small $n$, for instance $n=4$ or $n=5$, using exact arithmetic over function fields, and any mismatch would refute the main reduction for type D.","tokens_in":32229,"feed_emoji":"🧩","tokens_out":3561,"duration_ms":24435,"temperature":0.7,"pith_summary":"This paper proves that the problem of deciding whether a Schubert coefficient $c^w_{u,v}$ is zero belongs to the complexity class coAM, assuming the Generalized Riemann Hypothesis. Since coAM is contained in the second level of the polynomial hierarchy $\\Sigma_2^p$, this gives the first upper bound placing the Schubert vanishing problem inside ${\\sf PH}$. The result holds for the classical types A, B, C, and D. Previously only the ${\\sf PSPACE}$ upper bound was known, and the paper explains why a natural ${\\sf C_{=}P}$ upper bound does not by itself imply a ${\\sf PH}$ upper bound.","feed_headline":"Schubert vanishing lands in the polynomial hierarchy","feed_subtitle":"Under GRH, deciding whether a Schubert coefficient is zero is in coAM, giving the first PH upper bound for the problem.","key_machinery":"The central mechanism is the lifted formulation: a polynomial system with $O(n^2)$ equations and variables, with coefficients depending polynomially on parameters $y,z$, such that for generic parameter values the number of solutions over $\\mathbb{C}$ equals the Schubert coefficient. For nonvanishing, the system has a solution over the function field $\\mathbb{C}(y,z)$ exactly when the coefficient is positive. In type D the new machinery is the double-coset intersection criterion: $c^w_{u,v}(Y)>0$ iff $B^- \\dot{u} B \\cap \\pi B^- \\dot{v} B \\cap \\rho B^- \\dot{w_0 w} B$ is nonempty for generic $\\pi,\\rho$, together with polynomial-size descriptions of generic group elements via Cayley transforms and of Borel subgroups via triangular matrix equations.","core_discovery":"The paper's central claim is that the vanishing problem $\\{c^w_{u,v}=^? 0\\}$ is in ${\\sf coAM}$ under GRH. The proof works by reducing the nonvanishing problem to an instance of the Parametric Hilbert Nullstellensatz (HNP), a decision problem that was recently shown to be in ${\\sf AM}$ under GRH. The reduction uses 'lifted formulations': polynomial systems whose number of solutions over the function field $\\mathbb{C}(y,z)$ counts the Schubert coefficient, and whose existence of a solution characterizes nonvanishing. For types A, B, and C the lifted formulations come from Stiefel coordinates and bilinear incidence equations; for type D the paper supplies a new construction (jointly with David Speyer) based on double-coset intersections and Borel subgroup equations, which avoids the exponentially large determinant equation that blocked the earlier approach.","pith_inferences":["If the HNP-in-AM theorem were ever derandomized, the GRH assumption could likely be removed and the vanishing problem would probably land in NP or coNP, which would contradict the paper's Conjecture 1.5 but would strengthen the case that combinatorial witnesses exist.","The double-coset construction in Appendix C suggests that other cohomological structure constants definable by generic intersections of Schubert varieties—not only the classical types—might admit polynomial-size lifted formulations, as long as the group and flag conditions can be encoded with polynomial-size equations.","A natural testable extension is to apply the same lifted-formulation method to the vanishing of equivariant Schubert coefficients or to quiver coefficients, where the geometric counting interpretation is similar but the defining systems are not yet known to be polynomial-size.","The paper's framework indicates that the difficulty in type D was not geometric but computational: the determinant $\\det(\\omega)=1$ condition is of exponential size, so any improvement must avoid explicitly encoding that equation; the new construction does so by working directly with double cosets and Borel subgroups."],"forward_implications":["Assuming GRH, SchubertVanishing is in coAM, hence inside $\\Sigma_2^p$: the first polynomial-hierarchy upper bound for this problem. As a consequence, the vanishing problem cannot be NP-complete unless PH collapses to the second level.","Since positive Schubert coefficients would be witnessed by an HNP solution when GRH holds, the paper identifies a structural obstacle to proving Conjecture 1.3 (Schubert not in $\\#{\\sf P}$) by showing the vanishing problem is not in PH.","The result extends to the vanishing problem for generic $k$-fold intersections of Schubert varieties for every fixed $k$, as noted in the final remarks.","In the BSS model over the complex numbers, the same lifted formulations place nonvanishing in ${\\sf NP}_{\\mathbb{C}}$ and Schubert coefficient computation in $\\#{\\sf P}_{\\mathbb{C}}$ in all classical types.","The type D construction (Appendix C) also gives a new uniform proof of the reduction for types A, B and C, replacing the earlier Stiefel-coordinate systems with double-coset equations."],"supporting_citations":[{"why":"Provides the Parametric Hilbert Nullstellensatz (HNP) in AM under GRH, which is the target of the reduction and the source of the coAM upper bound.","marker":"[A+24]"},{"why":"Supplies the original lifted square formulation for Schubert calculus in type A that the paper translates and extends.","marker":"[HS17]"},{"why":"Gives Kleiman's transversality theorem, used to express Schubert coefficients as counts of points in generic intersections of Schubert varieties.","marker":"[Kle74]"},{"why":"Provides the relation between type B and type C Schubert coefficients (factor $2^{s(w)-s(u)-s(v)}$), used to lift the type C result to type B.","marker":"[BH95]"},{"why":"Gives the algebraic nonvanishing criterion via root spaces and double cosets (Lemma B.7) used in the BSS-model proof, and informs the double-coset perspective of Appendix C.","marker":"[Pur06]"},{"why":"Supplies the Cayley transform parameterization of generic orthogonal and symplectic group elements, which is the backbone of the variable-parameter systems in types B, C and D.","marker":"[Weyl39]"},{"why":"The original Hilbert Nullstellensatz in AM under GRH; the paper notes that HNP extends Koiran's approach and that HN is unlikely to be in NP.","marker":"[Koi96]"}],"fun_headline_variants":["Schubert vanishing in coAM under GRH","First PH bound for Schubert vanishing","Lifted formulations crack Schubert vanishing","Type D resolved: Schubert vanishing in coAM"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire argument rests on the availability of polynomial-size lifted polynomial systems whose satisfiability exactly matches nonvanishing of the Schubert coefficient, and for type D this depends on the Appendix C claim (Equation C.1) that the double-coset intersection is nonempty for generic $\\pi,\\rho$ exactly when $c^w_{u,v}>0$, together with the Borel parametrization tables correctly encoding membership in the Borel subgroups of $SO_{2n}$.","fun_headline_variants_meta":{"raw":{"variants":["Schubert vanishing in coAM under GRH","First PH bound for Schubert vanishing","Lifted formulations crack Schubert vanishing","Type D resolved: Schubert vanishing in coAM"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000769,"raw_usage":{"total_tokens":3399,"prompt_tokens":927,"completion_tokens":2472,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":2415}},"tokens_in":543,"tokens_out":2472,"duration_ms":226711,"temperature":1.0,"reasoning_tokens":2415,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:53:08.354106+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a concrete triple of permutations $u,v,w$ in type D for which the system $E^D(u,v,w)$ of Appendix C has a solution over $\\mathbb{C}(y,z)$ but the Schubert coefficient $c^w_{u,v}(D)$ is zero, or vice versa. Because the system size is $O(n^2)$, this can be checked by explicit computation for small $n$, for instance $n=4$ or $n=5$, using exact arithmetic over function fields, and any mismatch would refute the main reduction for type D.","supporting_citations":[],"review_version":1}