Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems
share
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 , 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(mD^2), where D is the degree of the ideal and m is the number of non-trivial columns of a certain D × D matrix. While asymptotic estimates are known for m for generic polynomial systems, thus far, the complexity of 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 algorithm for generic determinantal systems and for generic critical point systems. We consider the ideal in the polynomial ring 𝕂[x_1, …, x_n], where 𝕂 is some infinite field, generated by p generic polynomials of degree d and the maximal minors of a p × (n-1) polynomial matrix with generic entries of degree d-1. Then for the case d=2 and for n ≫ p we give an exact formula for m in terms of n and p. Moreover, for d ≥ 3, we give an asymptotic formula, as n →∞, for m in terms of n,p and d.
READ FULL TEXT
