On algorithms testing positivity of real symmetric polynomials

Abstract

Abstract We show that positivity (≥0) on R + n $\mathbb{R}_{+}^{n}$ and on R n $\mathbb{R}^{n}$ of real symmetric polynomials of degree at most p in n ≥ 2 $n\ge 2$ variables is solvable by algorithms running in polynomial time in the number n of variables. For real symmetric quartics, we find discriminants which lead to the efficient algorithms QE4+ and QE4 running in O ( n ) $O(n)$ time. We describe the Maple implementation of both algorithms, which are then used not only for testing concrete inequalities (with given numerical coefficients and number of variables), but also for proving symbolic inequalities.

Keywords

• Quantifier elimination
• Algorithm
• Symmetric polynomial