Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems

Abstract

We consider ideals involving the maximal minors of a polynomial matrix. For example, those arising in the computation of the critical values of a polynomial restricted to a variety for polynomial optimisation. Gröbner bases are a classical tool for solving polynomial systems. For practical computations, this consists of two stages. First, a Gröbner basis is computed with respect to a DRL (degree reverse lexicographic) ordering. Then, a change of ordering algorithm, such as \textsf{Sparse-FGLM}, designed by Faugère and Mou, is used to find a Gröbner basis of the same ideal but with respect to a lexicographic ordering. The complexity of this latter step, in terms of arithmetic operations, is $O(m{D}^2)$, where $D$ is the degree of the ideal and $m$ is the number of non-trivial columns of a certain $D\times D$ matrix. While asymptotic estimates are known for $m$ for generic polynomial systems, thus far, the complexity of \textsf{Sparse-FGLM} was unknown for determinantal systems. By assuming Fröberg's conjecture we expand the work of Moreno-Socías by detailing the structure of the DRL staircase in the determinantal setting. Then we study the asymptotics of the quantity $m$ by relating it to the coefficients of these Hilbert series. Consequently, we arrive at a new bound on the complexity of the \textsf{Sparse-FGLM} algorithm for generic determinantal systems and for generic critical point systems. We consider the ideal in the polynomial ring $\mathbb{K}[x_1,\dots ,x_n]$, where $\mathbb{K}$ is some infinite field, generated by $p$ generic polynomials of degree $d$ and the maximal minors of a $p\times (n-1)$ polynomial matrix with generic entries of degree $d-1$. Then for the case $d=2$ and for $n\gg p$ we give an exact formula for $m$ in terms of $n$ and $p$. Moreover, for $d\ge 3$, we give an asymptotic formula, as $n\to \infty$, for $m$ in terms of $n,p$ and $d$.