Computing critical points for invariant algebraic systems. (May 2023) - Faugère, Jean-Charles; Labahn, George; Safey El Din, Mohab; Schost, Éric; Vu, Thi Xuan
Abstract: Let K be a field and ( f 1, …, f s, ϕ ) be multivariate polynomials in K [ x 1, …, x n ] (with s < n ) each invariant under the action of S n, the group of permutations of 1, …, n . We consider the problem of computing the critical points of ϕ restricted to the algebraic set V ( f ), where f = ( f 1, …, f s ) . This is the same as computing the points at which f vanishes and the Jacobian matrix associated to ( f 1, …, f s, ϕ ) is rank deficient, provided that this set is finite. We exploit the invariance properties of the input to split the solution space according to the orbits of S n . This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in d s, ( n + d d ) and ( n s + 1 ) where d is the maximum degree of the input polynomials. When d, s are fixed, this is polynomial in n while when s is fixed and d ≃ n this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.