Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908300052791296 |
|---|---|
| author | Pak, Igor Robichaux, Colleen |
| author_facet | Pak, Igor Robichaux, Colleen |
| contents | The Schubert vanishing problem is a central decision problem in algebraic combinatorics and Schubert calculus, with applications to representation theory and enumerative algebraic geometry. The problem has been studied for over 50 years in different settings, with much progress given in the last two decades.
We prove that the Schubert vanishing problem is in ${\sf AM}$ assuming the Generalized Riemann Hypothesis (GRH). This complements our earlier result in arXiv:2412.02064, that the problem is in ${\sf coAM}$ assuming the GRH. In particular, this implies that the Schubert vanishing problem is unlikely to be ${\sf coNP}$-hard, as we previously conjectured in arXiv:2412.02064.
The proof is of independent interest as we formalize and expand the notion of a lifted formulation partly inspired by algebraic computations of Schubert problems, and extended formulations of linear programs. We use a result by Mahajan--Vinay to show that the determinant has a lifted formulation of polynomial size. We combine this with Purbhoo's algebraic criterion to derive the result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03004 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH Pak, Igor Robichaux, Colleen Combinatorics Computational Complexity Discrete Mathematics Algebraic Geometry Primary: 05E14, Secondary: 14M15, 14N15, 68Q17, 68Q25, 90C27 The Schubert vanishing problem is a central decision problem in algebraic combinatorics and Schubert calculus, with applications to representation theory and enumerative algebraic geometry. The problem has been studied for over 50 years in different settings, with much progress given in the last two decades. We prove that the Schubert vanishing problem is in ${\sf AM}$ assuming the Generalized Riemann Hypothesis (GRH). This complements our earlier result in arXiv:2412.02064, that the problem is in ${\sf coAM}$ assuming the GRH. In particular, this implies that the Schubert vanishing problem is unlikely to be ${\sf coNP}$-hard, as we previously conjectured in arXiv:2412.02064. The proof is of independent interest as we formalize and expand the notion of a lifted formulation partly inspired by algebraic computations of Schubert problems, and extended formulations of linear programs. We use a result by Mahajan--Vinay to show that the determinant has a lifted formulation of polynomial size. We combine this with Purbhoo's algebraic criterion to derive the result. |
| title | Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH |
| topic | Combinatorics Computational Complexity Discrete Mathematics Algebraic Geometry Primary: 05E14, Secondary: 14M15, 14N15, 68Q17, 68Q25, 90C27 |
| url | https://arxiv.org/abs/2504.03004 |