On the arithmetic complexity of computing Gröbner bases of comaximal determinantal ideals
This paper improves the complexity analysis given in ‘Refined F5 algorithms for ideals of minors of square matrices’ . A theorem about the structure of grevlex staircases of reverse lexicographic ideals is established, then applied to give an upper bound on the arithmetic complexity of computing Gröbner bases of comaximal minors of square matrices in the zero-dimensional case and under genericity assumptions. A lower bound on the size of a reduced grevlex Gröbner basis of such determinantal systems is also given. Both results depend on the conjectural nonemptiness of an explicit Zariski open subset.