Real root finding for equivariant semi-algebraic systems
share
Let R be a real closed field. We consider basic semi-algebraic sets defined by n-variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2d < n. 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 2d-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 s polynomials of degree d in time (sn)^O(d). This improves the state-of-the-art which is exponential in n. When the variables x_1, ..., x_n are quantified and the coefficients of the input system depend on parameters y_1, ..., y_t, one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time (sn)^O(dt).
READ FULL TEXT