Real Root Finding for Equivariant Semi-algebraic Systems

Abstract

Let <i><b>R</b></i> be a real closed field. We consider basic semi-algebraic sets defined by <i>n</i>-variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2<i>d</i> &#60; <i>n</i>. Such a semi-algebraic set is invariant by the action of the symmetric group. We show that such a set is either empty or it contains a point with at most 2<i>d</i>−1 distinct coordinates. Combining this geometric result with efficient algorithms for real root finding (based on the critical point method), one can decide the emptiness of basic semi-algebraic sets defined by <i>s</i> polynomials of degree <i>d</i> in time <i>(sn)^O(d)</i>. This improves the state-of-the-art which is exponential in <i>n</i>. When the variables <i>x₁, ..., x_n</i> are quantified and the coefficients of the input system depend on parameters <i>y₁, ..., y_t</i>, one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time <i>(sn)^O(d)</i>.