Gröbner bases and critical values: the asymptotic combinatorics of determinantal systems (Q2132458)

Determinantal polynomial systems arise in several problems in Mathematics, for instance in the computation of the critical values of a polynomial map restricted to an algebraic set. Given an infinite field \(K\), in this paper the authors consider a \textit{generic} determinantal ideal \(I\subseteq K[x_1,\dots,x_n]\) 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\). They give new complexity bounds on computing a Lex-Gröbner basis of I, assuming that a DRL-Gröbner basis of \(I\) is known. This result is obtained by assuming a variant of Fröberg's conjecture, and extending the results of [\textit{J.-C. Faugère} and \textit{C. Mou}, J. Symb. Comput. 80, Part 3, 538--569 (2017; Zbl 1404.13031)] and [\textit{G. Moreno-Socías}, J. Pure Appl. Algebra 180, No. 3, 263--283 (2003; Zbl 1062.13007)]. More precisely, the authors prove a result on the structure of the DRL staircase of \(I\), and obtain as a consequence that the multiplication matrix \(M_n\) (the one associated to the linear map of multiplication by \(x_n\)) can be constructed without performing any arithmetic operations. Then the authors prove asymptotic formulae for the number \(m\) of non-trivial columns of \(M_n\). Finally, they obtain a new complexity result for the Sparse-FGLM algorithm for generic determinantal systems.