Pith. sign in

REVIEW 3 major objections 5 minor 38 references

Positivity of Schubert Coefficients

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Assuming two standard conjectures, the Schubert positivity problem has a positive rule: positive coefficients are certified by polynomial-time checkable witnesses.

desk verdict Conditional on the companion paper's reduction, the theorem follows, but the note is a translation with a heavy external dependency. read the letter →

arxiv 2412.18984 v1 pith:BIEPTZLH submitted 2024-12-25 math.CO cs.CCcs.DMmath.HO

Igor Pak , Colleen Robichaux This is my paper · ORCID
classification math.COcs.CCcs.DMmath.HO MSC 05E0514M1568Q17
keywords SchubertcoefficientspositivityproblempositiverulecombinatorialinterpretationParametricHilbertNullstellensatzAMandNPcomplexityclassesderandomizationGeneralizedRiemannHypothesis
topics The Riemann Hypothesis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that, under two standard conjectures, deciding whether a Schubert coefficient is positive admits a positive rule: whenever the answer is yes, there exists a combinatorial object of polynomial size that certifies the positivity. This is the first general positive rule for the Schubert positivity problem, a long-standing open question in algebraic combinatorics. The proof reduces the problem to a parametric version of Hilbert's Nullstellensatz, shows that problem lies in the complexity class AM under GRH, and then uses a derandomization assumption to collapse AM to NP. If correct, the result is the first general evidence that Schubert coefficients may have a combinatorial interpretation, though the paper does not construct one.

What carries the argument

The load-bearing mechanism is the Parametric Hilbert's Nullstellensatz problem (HNP), which asks whether a polynomial system with coefficients in $\mathbb{Z}(y_1,\ldots,y_k)$ has a solution over $\mathbb{C}(y_1,\ldots,y_k)$. A lifted square formulation converts the condition that a Schubert coefficient is positive (or vanishes) into such a system; under GRH, a known method places HNP in AM; under MVA, AM collapses to NP. The witness for positivity is thus a solution of the lifted system over a finite field, verified by randomized polynomial identities that MVA derandomizes.

What would settle it

Run the paper's reduction on explicit permutation triples: for a known positive Schubert coefficient and a known zero coefficient, build the lifted square system and test whether the parametric polynomial system is solvable over $\mathbb{C}(y)$; if the two cases do not separate, the reduction in the companion paper is false and Theorem 2.1 falls.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is Theorem 2.1: assuming the Generalized Riemann Hypothesis and the MVA derandomization assumption, the Schubert positivity problem (deciding whether a Schubert coefficient $c_{u,v}^w$ is positive) has a positive rule. Equivalently, the problem lies in NP: for every positive coefficient there is a certificate verifiable in polynomial time, and no such certificate exists for a zero coefficient. The argument chains three known results: a reduction from Schubert positivity to the Parametric Hilbert Nullstellensatz (HNP) obtained in the authors' companion paper; the theorem that HNP is in AM assuming GRH; and the collapse AM = NP following from MVA. The paper notes the reduction extends verbatim to Schubert calculus for root systems B and C but not D.

Load-bearing premise

The paper quotes, without proof, the reduction from the Schubert positivity problem to a parametric polynomial-system problem proved in its companion paper; if that reduction is wrong or does not apply to all permutation triples, the theorem collapses.

Editorial extensions

If this is right

  • Under GRH and MVA, the Schubert positivity problem is in NP, so every positive Schubert coefficient has a certificate verifiable in polynomial time.
  • This yields the first positive rule for Schubert positivity in full generality.
  • If Schubert positivity is NP-hard (the authors conjecture it is), then under the same assumptions the problem is NP-complete.
  • The argument extends without change to Schubert calculus for root systems B and C, but not D.
  • The theorem does not by itself decide positivity in polynomial time; it provides witnesses for positive instances only.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A concrete check of the reduction chain on small permutation triples—comparing certificate existence from the lifted polynomial system with known positive and zero Schubert coefficients—would test the claimed bridge without needing to resolve GRH or MVA.
  • If the parametric Nullstellensatz reduction can be made unconditional, for instance by replacing GRH with effective bounds on primes in arithmetic progressions, the same proof would give an unconditional positive rule.
  • The paper's conditional NP membership removes one structural obstacle to a #P-style combinatorial interpretation: no counting interpretation can exist unless positivity is in NP, so the absence of a known interpretation is now less informative than it was before.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper claims a conditional positive rule for Schubert positivity: assuming the Generalized Riemann Hypothesis (GRH) and the Miltersen–Vinodchandran Assumption (MVA), the decision problem (2.1) of whether a Schubert coefficient c_{u,v}^w is positive is in NP, and therefore has a positive rule in the sense defined in (2.5). The proof chains three results: a reduction from Schubert positivity to the Parametric Hilbert's Nullstellensatz (HNP) cited from the authors' companion paper [PR24b, Lemma 1.10], a result of [A+24] placing HNP in AM under GRH, and the MVA-based collapse AM = NP of [MV05]. The paper also contains a substantial discussion of the meaning of 'combinatorial interpretation' and 'positive rule', and it addresses anticipated critiques about the interest and certainty of the result.

Significance. If the cited reduction holds, the theorem is a notable conditional contribution: it would give the first general positive rule for Schubert positivity under standard hypotheses, and it connects an open problem in algebraic combinatorics to derandomization assumptions in a way that is both novel and thought-provoking. The paper's careful formalization of 'positive rule' as membership in NP (equations (2.2)-(2.5)) is a useful clarification independent of the main theorem, and the discussion in Section 4 shows a commendable awareness of the limits of the result. However, the central reduction is not proved or even stated in this note, so the paper's main claim is currently unverifiable from the manuscript alone; the significance is therefore contingent on the correctness and availability of [PR24b].

major comments (3)
  1. [§2.3, Proof of Theorem 2.1] The proof rests entirely on [PR24b, Lemma 1.10], which is neither stated nor proved in this manuscript. The note only says that 'a modification of the lifted formulation given in [HS17]' yields a reduction from the Schubert positivity problem (2.1) to HNP. For the theorem to be sound, the authors must state the lemma and verify that it (i) produces a polynomial system of size polynomial in the input (the permutations u, v, w in their natural presentation), (ii) has solvability over C(y_1,...,y_k) exactly equivalent to c_{u,v}^w > 0, not merely a one-sided implication, and (iii) fits exactly the parametric Nullstellensatz format assumed by [A+24, Thm 1], including the coefficient field, the number of parameters, and any degree bounds. Without this information, the claimed reduction—and hence the entire theorem—cannot be checked.
  2. [§2.3, definition of HNP] The description of HNP is incomplete: it does not specify how the polynomial system f_1 = ... = f_m = 0 is encoded as input, what degree bounds are allowed, or whether the parameters y_1,...,y_k are existential variables or part of the input data. These details matter because [A+24, Thm 1] is a complexity-theoretic result with specific hypotheses. The reduction from Schubert positivity must be shown to produce instances in exactly the class for which the AM upper bound holds; otherwise the chain from (2.1) to HNP to AM to NP is broken.
  3. [§3.1, meaning of Theorem 2.1] The description of the resulting positive rule is too vague to serve as a certificate. The authors state that the rule 'consists of solutions of the lifted formulation system over multiple primes whose existence is guaranteed by GRH' and that random bits come from a pseudorandom generator constructed in [MV05], but they do not explain how a solution over finite fields is converted into a polynomial-time verifiable witness for c_{u,v}^w > 0, nor how the verifier for the NP membership works. A precise description of the NP witness and its verification algorithm is needed to substantiate the claim that this is a positive rule in the sense of (2.5).
minor comments (5)
  1. [Title and abstract] The title reads 'POSITIVITY OF SCHUBERT T COEFFICIENTS' and the abstract contains 'Schubert T coefficients'; the stray 'T' should be removed.
  2. [After the abstract] The Hebrew phrase 'דרךאמונהבחרתי' appears without translation or attribution; either remove it or provide a translation and explanation, as the current presentation is opaque to most readers.
  3. [Footnote 1 (p. 3)] The footnote about permutations being given in their natural presentation is relevant to the complexity claim and should be moved into the main text, preferably near the statement of the Schubert positivity problem (2.1).
  4. [§3.1] The statement that Theorem 2.1 'would contradict Conjecture 10.1 in [Pak24]' is not explained; the conjecture itself is not stated, so readers cannot evaluate this claimed implication.
  5. [References] The description of [A+24] as 'a recent breakthrough' is a subjective evaluation; a more neutral phrasing, such as 'a recent result', would be more appropriate in a formal setting.

Circularity Check

1 steps flagged · score 4.0 of 10

Theorem 2.1 rests on the authors' own companion result [PR24b, Lemma 1.10] as the sole Schubert-specific reduction; the independent results [A+24] and [MV05] are not at issue.

  1. self citation load bearing [Section 2.3, Proof of Theorem 2.1; see also Section 3.1]
    "We showed in [PR24b, Lemma 1.10], that a modification of the lifted formulation given in [HS17] can be used to show that the Schubert positivity problem reduces to Parametric Hilbert’s Nullstellensatz (HNP)."

    This is the only step in the proof that connects Schubert coefficients to the complexity-theoretic machinery. The note neither states nor proves Lemma 1.10 of [PR24b]; it cites the authors' own companion preprint. All remaining steps are independent: [A+24] places HNP in AM under GRH, and [MV05] collapses AM to NP under MVA. Since Theorem 2.1's conclusion for Schubert positivity depends entirely on the asserted reduction being a correct polynomial-time equivalence that fits the HNP format of [A+24], the central claim is load-bearing on an unverified self-citation. This is not an equation-level circularity, but it is a self-citation chain on which the paper's main result rests.

full rationale

The paper is explicit that it is an expository companion to [PR24b], and the definition of a positive rule as NP membership is a deliberate translation rather than a logical circle. The proof chain of Theorem 2.1 is [PR24b, Lemma 1.10] (Schubert positivity reduces to HNP), [A+24, Thm 1] (HNP is in AM under GRH), and [MV05, Thm 1.5] (AM = NP under MVA). The latter two are independent external results and are not called into question here. The former is the sole Schubert-specific reduction and is imported from the authors' own companion paper without statement or proof; the present note even says 'We deduce Theorem 2.1 from a known complexity theoretic result [MV05], a recent breakthrough [A+24], and one of our results in [PR24b].' Under the rubric this is the self_citation_load_bearing pattern. Because the external complexity components are independent and the reduction may be correct, the score is moderate (4) rather than the 8-10 range reserved for results forced entirely by self-citation or definition. No fitted-input-as-prediction, imported uniqueness theorem, or ansatz-by-citation pattern was found.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theorem rests on two unproven domain assumptions and on three cited theorems that are not reproduced. The key reduction [PR24b] is from the authors' own prior work, which adds a self-citation component. No free parameters are fitted, and no new entities are introduced.

assumptions (5)
  • domain assumption Generalized Riemann Hypothesis (GRH): all nontrivial zeros of L-functions L(s, χ_k) have real part 1/2.
    External unproven hypothesis. Used to place Parametric Hilbert's Nullstellensatz in AM via [A+24]. Stated in Section 2.3.
  • domain assumption Miltersen-Vinodchandran Assumption (MVA): some language in NE ∩ coNE requires nondeterministic circuits of size 2^Ω(n).
    External unproven complexity assumption. Implies AM = NP via [MV05, Thm 1.5]. Stated in Section 2.3.
  • standard math Reduction from Schubert positivity to Parametric Hilbert's Nullstellensatz, as stated in [PR24b, Lemma 1.10].
    A theorem from the authors' own companion paper. The proof is not reproduced in this note; the central claim depends on it.
  • standard math HNP is in AM assuming GRH, per [A+24, Thm 1] extending Koiran [Koi96].
    A recent result cited without proof in this note.
  • standard math AM = NP under MVA, per [MV05, Thm 1.5].
    A published result in complexity theory, cited but not proved here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Positivity of Schubert Coefficients." pith.science (2026). https://pith.science/paper/BIEPTZLH

@misc{pith2026241218984,
  author       = {Pith},
  title        = {Pith review of: Positivity of Schubert Coefficients},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BIEPTZLH}},
  note         = {Machine review of arXiv:2412.18984}
}
abstract

Schubert coefficients $c_{u,v}^w$ are structure constants describing multiplication of Schubert polynomials. Deciding positivity of Schubert coefficients is a major open problem in Algebraic Combinatorics. We prove a positive rule for this problem based on two standard assumptions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 24 canonical work pages

  1. [1]

    Anshul Adve, Colleen Robichaux and Alexander Yong, Vanishing of Littlewood--Richardson polynomials is in , Comput.\ Complexity 28 (2019), 241--257

    work page 2019

  2. [2]

    Rida Ait El Manssour, Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi and James Worrell, A parametric version of the Hilbert Nullstellensatz, preprint (2024), 13 pp.; arXiv:2408.13027

    work page Pith review arXiv 2024

  3. [3]

    David Anderson and William Fulton, Equivariant cohomology in algebraic geometry, Cambridge Univ.\ Press, Cambridge, UK, 2024, 446 pp

    2024

  4. [4]

    Sara Billey and Ravi Vakil, Intersections of S chubert varieties and other permutation array schemes, in Algorithms in algebraic geometry, Springer, New York, 2008, 21--54

    2008

  5. [5]

    Peter Borwein et al.\ (Eds.), The Riemann hypothesis, Springer, New York, 2008, 533 pp

    work page 2008

  6. [6]

    Buch, Frank Sottile and Alexander Yong, Quiver coefficients are Schubert structure constants, Math.\ Res.\ Lett

    Anders S. Buch, Frank Sottile and Alexander Yong, Quiver coefficients are Schubert structure constants, Math.\ Res.\ Lett. 12 (2005), 567--574

    work page 2005

  7. [7]

    Pi 12 (2024), Paper No

    Swee Hong Chan and Igor Pak, Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy, Forum Math. Pi 12 (2024), Paper No. e21, 38 pp

    2024

  8. [8]

    1015 (2024), Paper No

    Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, Theoret.\ Comput.\ Sci. 1015 (2024), Paper No. 114776, 19 pp

    2024

Show all 38 references
  1. [9]

    Swee Hong Chan and Igor Pak, Equality cases of the Stanley--Yan log-concave matroid inequality, preprint (2024), 36 pp.; arXiv:2407.19608

    2024 arXiv

  2. [10]

    Farmer, Currently there are no reasons to doubt the Riemann Hypothesis, preprint (2022), 58 pp.; arXiv:2211.11671

    David W. Farmer, Currently there are no reasons to doubt the Riemann Hypothesis, preprint (2022), 58 pp.; arXiv:2211.11671

    2022

  3. [11]

    Gasarch, The third =?\

    William I. Gasarch, The third =?\. poll, ACM SIGACT News 50 (2019), no. 1, 38–59

    2019

  4. [12]

    A conceptual perspective, Cambridge Univ.\ Press, Cambridge, UK, 2008, 606 pp

    Oded Goldreich, Computational complexity. A conceptual perspective, Cambridge Univ.\ Press, Cambridge, UK, 2008, 606 pp

    2008

  5. [13]

    Symbolic Comput

    Nickolas Hein and Frank Sottile, A lifted square formulation for certifiable S chubert calculus, J. Symbolic Comput. 79 (2017), 594--608

    2017

  6. [14]

    Christian Ikenmeyer and Igor Pak, What is in and what is not?, preprint (2022), 82 pp.; extended abstract in Proc.\ 63rd FOCS (2022), 860--871; arXiv:2204.13149

    2022 arXiv

  7. [15]

    (2024), no

    Christian Ikenmeyer, Igor Pak and Greta Panova, Positivity of the symmetric group characters is as hard as the polynomial time hierarchy, Int.\ Math.\ Res.\ Not. (2024), no. 10, 8442--8458

    2024

  8. [16]

    10 (2001), 345--353

    Allen Knutson, Descent-cycling in S chubert calculus, Experiment.\ Math. 10 (2001), 345--353

    2001

  9. [17]

    VI, EMS Press, 4582--4605

    Allen Knutson, Schubert calculus and quiver varieties, in Proc.\ ICM (2022, virtual), Vol. VI, EMS Press, 4582--4605

    2022

  10. [18]

    Allen Knutson and Paul Zinn-Justin, Schubert puzzles and integrability I: invariant trilinear forms, preprint (2017), 51 pp.; arXiv:1706.10019

    2017 arXiv

  11. [19]

    Allen Knutson and Paul Zinn-Justin, Schubert puzzles and integrability III: separated descents, preprint (2023), 42 pp.; arXiv:2306.13855

    2023 arXiv

  12. [20]

    Pascal Koiran, Hilbert's Nullstellensatz is in the polynomial hierarchy, J.\ Complexity 12 (1996), 273--286; see also DIMACS Tech.\ Report 96-27 (1996), 18 pp

    1996

  13. [21]

    Marc Lackenby, Elementary knot theory, in Lectures on geometry, Oxford Univ.\ Press, Oxford, UK, 2017, 29--64

    2017

  14. [22]

    Macdonald, Notes on Schubert polynomials, Publ.\ LaCIM, UQAM, Montreal, 1991, 116 pp

    Ian G. Macdonald, Notes on Schubert polynomials, Publ.\ LaCIM, UQAM, Montreal, 1991, 116 pp

    1991

  15. [23]

    Laurent Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS, Providence, RI, 2001, 167 pp

    2001

  16. [24]

    Miltersen and N

    Peter B. Miltersen and N. Variyam Vinodchandran, Derandomizing Arthur--Merlin games using hitting sets, Comput.\ Complexity 14 (2005), 256--279

    2005

  17. [25]

    IV, World Sci., Hackensack, NJ, 2018, 3153--3180

    Igor Pak, Complexity problems in enumerative combinatorics, in Proc.\ ICM Rio de Janeiro, Vol. IV, World Sci., Hackensack, NJ, 2018, 3153--3180

    2018

  18. [26]

    Igor Pak, What is a combinatorial interpretation?, in Open Problems in Algebraic Combinatorics, AMS, Providence, RI, 2024, 191--260

    2024

  19. [27]

    Igor Pak and Colleen Robichaux, Signed combinatorial interpretations in algebraic combinatorics, preprint (2024), 23 pp.; to appear in Algebraic Combinatorics; arXiv:2406.13902

    2024 arXiv

  20. [28]

    Igor Pak and Colleen Robichaux, Vanishing of Schubert coefficients, preprint (2024), 24 pp.; arXiv:2412. 02064

    2024

  21. [29]

    Greta Panova, Computational complexity in algebraic combinatorics, to appear in Current Developments in Mathematics, International Press, Boston, MA, 30 pp.; arXiv:2306.17511

    arXiv

  22. [30]

    Henri Poincar\' e , Science and method (translated from French), Nelson, London, 1914, 288 pp

    1914

  23. [31]

    24590, 38 pp

    Kevin Purbhoo, Vanishing and nonvanishing criteria in Schubert calculus, Int.\ Math.\ Res.\ Notices 2006 (2006), Art. 24590, 38 pp

    2006

  24. [32]

    Maurice Rojas, Dedekind zeta functions and the complexity of Hilbert's Nullstellensatz, preprint (2003), 16 pp.; arXiv:math/0301111

    J. Maurice Rojas, Dedekind zeta functions and the complexity of Hilbert's Nullstellensatz, preprint (2003), 16 pp.; arXiv:math/0301111

    2003 arXiv

  25. [33]

    Dizier and Alexander Yong, Generalized permutahedra and S chubert calculus, Arnold Math

    Avery St. Dizier and Alexander Yong, Generalized permutahedra and S chubert calculus, Arnold Math. J. 8 (2022), 517--533

    2022

  26. [34]

    Stanley, Positivity problems and conjectures in algebraic combinatorics, in Mathematics: frontiers and perspectives, AMS, Providence, RI, 2000, 295--319

    Richard P. Stanley, Positivity problems and conjectures in algebraic combinatorics, in Mathematics: frontiers and perspectives, AMS, Providence, RI, 2000, 295--319

    2000

  27. [35]

    Stanley, Enumerative Combinatorics , vol

    Richard P. Stanley, Enumerative Combinatorics , vol. 1 (Second ed.), Cambridge Univ. Press, 2012, 626 pp

    2012

  28. [36]

    Vadhan, Pseudorandomness, Found.\ Trends Theor.\ Comput.\ Sci

    Salil P. Vadhan, Pseudorandomness, Found.\ Trends Theor.\ Comput.\ Sci. 7 (2011), 1--336

    2011

  29. [37]

    Avi Wigderson, Mathematics and computation, Princeton Univ.\ Press, Princeton, NJ, 2019, 418 pp

    2019

  30. [38]

    Wilf, What is an answer?, Amer.\ Math.\ Monthly 89 (1982), no

    Herbert S. Wilf, What is an answer?, Amer.\ Math.\ Monthly 89 (1982), no. 5, 289--292

    1982

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.