Gröbner-basis complexity of critical point computation beyond maximal minors: Jacobian corank at least two and the degree of regularity via Grothendieck polynomials

Computing the critical points of a polynomial map restricted to an algebraic set is a bottleneck primitive of polynomial optimization and real algebraic geometry, and is encoded by a structured polynomial system involving minors of a Jacobian matrix. Spaenlehauer (2014) established arithmetic complexity bounds for solving this system by Gröbner bases under genericity assumptions, in the case where the Jacobian has corank at most one: there the determinantal part of the defining ideal is generated by maximal minors, its weighted Hilbert series is obtained through the Eagon–Northcott complex, and the degree of regularity — the quantity governing the cost of the Gröbner computation — follows in closed form. In Section 3.3 the paper explicitly asks whether the degree-of-regularity formula can also be obtained from the evaluation of Grothendieck polynomials, whose evaluations yield the K-polynomials of determinantal ideals also beyond the maximal-minor case; it observes that this approach extends to matrices of corank greater than one while the Eagon–Northcott complex is restricted to maximal minors — the situation arising for non-smooth constraint varieties and generalized critical point problems of higher codimension, where the relevant determinantal ideals are generated by non-maximal minors and no Hilbert-series, degree-of-regularity, or complexity formula of the 2014 type is known. The corank-one case has since been refined (optimized F5 criteria, change-of-order complexity, sharp degree bounds), and significant machinery now exists for Gröbner bases of non-maximal determinantal ideals of generic matrices and for the Castelnuovo–Mumford regularity of matrix Schubert varieties via Grothendieck polynomials; however, no published work derives the weighted degree-of-regularity formula from Grothendieck polynomials or extends the critical-point complexity framework to corank at least two. The problem remains open.

Background

In real algebraic geometry and polynomial optimization, a basic primitive is to compute the critical points of a polynomial $q$ restricted to the variety $V$ cut out by equations $f_1=\dots=f_p=0$ : points of $V$ where the gradient of $q$ is orthogonal to the tangent space of $V$ . When $V$ is smooth of codimension $p$ , these points are exactly the solutions of the system consisting of the $f_i$ together with all maximal minors (subdeterminants of full size) of the Jacobian matrix $\mathrm{jac}(q,f_1,\dots,f_p)$ of partial derivatives — a highly structured overdetermined polynomial system. Solving such systems is the algebraic core of algorithms for global optimization, sampling points in connected components of real sets, and roadmaps, so its complexity matters well beyond computer algebra.

The standard complete-algebra approach computes a Gröbner basis (a canonical generating set of the solution ideal that supports linear-algebra-based solving) with respect to the graded reverse lexicographic order. Matrix-based algorithms such as F4 and F5 — Faugère's linear-algebra algorithms for Gröbner bases — build Macaulay matrices (coefficient matrices gathering all polynomial multiples up to a given degree) degree by degree and reduce them by row-echelon computation; their arithmetic cost is governed by the degree of regularity of the ideal — the degree at which the Hilbert function of a generic homogenization stabilizes, i.e. the largest degree the computation must reach. For structured ideals this degree can be read off from the Hilbert series, weighted here by the input degrees: if $d_0=\deg(q)$ and $d_i=\deg(f_i)$ , the Jacobian entries in row $i$ naturally carry weight $d_i-1$ .

Spaenlehauer (2014) analyzed this weighted setting under genericity assumptions on the coefficients. The key algebraic fact is that the ideal generated by the maximal minors of the generic $(p+1)\times n$ Jacobian matrix is resolved by the Eagon–Northcott complex (the classical minimal free resolution of maximal-minor ideals), from which the weighted Hilbert series of the critical point ideal, its degree of regularity, and finally complexity bounds — $\delta^{O(\log A/\log G)}$ arithmetic operations in $\mathbb{Q}$ in terms of the algebraic degree $\delta$ of the critical locus and the arithmetic and geometric means $A,G$ of a multiset built from $(d_0,\dots,d_p)$ , meeting the best-known $D^{O(n)}$ bound — are derived. The precursor ISSAC 2012 paper by Faugère, Safey El Din and Spaenlehauer handled the equal-degree (unmixed) case by the same route.

The Eagon–Northcott complex, however, only resolves ideals of maximal minors, which corresponds to Jacobian matrices dropping rank by at most one. When the constraint variety is non-smooth, or in generalized critical point problems of higher codimension, the defining system instead involves non-maximal minors (minors of smaller size), cutting out loci where the Jacobian has corank at least two. Such determinantal ideals have more complicated resolutions (for instance via Gulliksen–Negård-type complexes, the classical free resolutions of ideals of submaximal minors of a square matrix), and no Hilbert-series, degree-of-regularity, or complexity formula of the 2014 type is known for them. The paper also observes that the numerator of the weighted Hilbert series — the K-polynomial — of the determinantal part is an evaluation of a Grothendieck polynomial (a combinatorial polynomial from Schubert calculus, the algebraic combinatorics of degeneracy loci in flag manifolds; it is indexed by a permutation, was introduced by Lascoux–Schützenberger and developed geometrically by Knutson and Miller, and its degrees control invariants of determinantal varieties), and that this representation extends to matrices of corank greater than one; whether the degree-of-regularity formula can be recovered or generalized from these polynomials was left as an open direction.

Problem Statement

Address the open question posed in Section 3.3 of Spaenlehauer (2014): determine whether the weighted degree-of-regularity formula for the Gröbner-basis computation of critical points — established in the paper, under its genericity assumptions, in the case where the Jacobian matrix $\mathrm{jac}(q,f_1,\dots,f_p)$ has corank at most one, so that the determinantal part of the defining ideal is generated by maximal minors — can also be obtained from the evaluation of Grothendieck polynomials. Moreover, since evaluations of Grothendieck polynomials yield the K-polynomials of determinantal ideals also beyond the maximal-minor case while the Eagon–Northcott complex is restricted to maximal minors, investigate whether this approach extends to systems in which the Jacobian matrix has corank at least two at the solutions — defining ideals whose determinantal part is generated by non-maximal minors, as arise for non-smooth (singular) constraint varieties and for generalized critical point problems of higher codimension.

For an input system with degree sequence $(d_0,\dots,d_p)$ , in the weighted grading in which the Jacobian entries in row $i$ carry weight $d_i-1$ :

In the corank-one (maximal-minor) case, under the genericity assumptions of Spaenlehauer (2014), determine whether the weighted Hilbert series of the critical point ideal, and the degree of regularity of the graded reverse lexicographic Gröbner basis computation, can be obtained from evaluations of Grothendieck polynomials, and, if so, derive them, recovering the closed-form degree of regularity obtained in the paper via the Eagon–Northcott complex.
Determine whether this Grothendieck-polynomial approach extends to the non-maximal-minor setting (Jacobian corank at least two), where the Eagon–Northcott complex is unavailable, and if so, what weighted Hilbert-series and degree-of-regularity information can be obtained for such critical point systems, potentially yielding complexity estimates for this broader class of structured polynomial systems in the spirit of the corank-one bound $\delta^{O(\log A/\log G)}$ in terms of the algebraic degree $\delta$ of the critical locus.

References

Pierre-Jean Spaenlehauer. On the Complexity of Computing Critical Points with Gröbner Bases. SIAM Journal on Optimization 24(3):1382–1401, 2014. DOI: 10.1137/130936294, https://doi.org/10.1137/130936294 (arXiv:1309.2138, https://arxiv.org/abs/1309.2138)
Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer. Critical points and Gröbner bases (the unmixed case). Proceedings ISSAC 2012, pp. 162–169. DOI: 10.1145/2442829.2442855, https://doi.org/10.1145/2442829.2442855 (arXiv:1202.0179, https://arxiv.org/abs/1202.0179)
Mohab Safey El Din, Pierre-Jean Spaenlehauer. Critical Point Computations on Smooth Varieties: Degree and Complexity Bounds. arXiv:1605.02518, 2016. https://arxiv.org/abs/1605.02518
Jérémy Berthomieu, Alin Bostan, Andrew Ferguson, Mohab Safey El Din. Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems. Journal of Algebra 602:154–180, 2022. DOI: 10.1016/j.jalgebra.2022.03.002, https://doi.org/10.1016/j.jalgebra.2022.03.002 (arXiv:2203.10021, https://arxiv.org/abs/2203.10021)
Sriram Gopalakrishnan, Vincent Neiger, Mohab Safey El Din. Optimized Gröbner basis algorithms for maximal determinantal ideals and critical point computations. arXiv:2402.07353, 2024. https://arxiv.org/abs/2402.07353
Sriram Gopalakrishnan, Vincent Neiger, Mohab Safey El Din. Refined F5 Algorithms for Ideals of Minors of Square Matrices. arXiv:2302.05375, 2023. https://arxiv.org/abs/2302.05375
Sriram Gopalakrishnan. On the arithmetic complexity of computing Gröbner bases of comaximal determinantal ideals. arXiv:2403.02160, 2024. https://arxiv.org/abs/2403.02160
Oliver Pechenik, David E. Speyer, Anna Weigandt. Castelnuovo-Mumford regularity of matrix Schubert varieties. arXiv:2111.10681, 2021. https://arxiv.org/abs/2111.10681
Oliver Pechenik, Matthew St. Denis. Degrees of P-Grothendieck polynomials and regularity of Pfaffian varieties. arXiv:2405.17645, 2024. https://arxiv.org/abs/2405.17645
Bernd Bank, Marc Giusti, Joos Heintz, Mohab Safey El Din. Intrinsic complexity estimates in polynomial optimization. arXiv:1304.5214, 2013. https://arxiv.org/abs/1304.5214
J. A. Eagon, D. G. Northcott. Ideals defined by matrices and a certain complex associated with them. Proceedings of the Royal Society of London. Series A 269(1337):188–204, 1962. DOI: 10.1098/rspa.1962.0170, https://doi.org/10.1098/rspa.1962.0170
Allen Knutson, Ezra Miller. Gröbner geometry of Schubert polynomials. Annals of Mathematics 161(3):1245–1318, 2005. arXiv:math/0110058, https://arxiv.org/abs/math/0110058