7
$\begingroup$

Certifying the non-negativity of a symmetric polynomial is much easier than certifying the non-negativity of an arbitrary polynomial function: for instance, in (1) is proved that the complexity of deciding if a symmetric polynomial $f \in \mathbb{R}[X_1,\ldots,X_n]$ of fixed degree is non-negative grows only polynomially with $n$. This is in contrast to the general case which complexity is NP-hard already in the case of quartic forms (2).

Say that a polynomial is $G$-invariant if it is invariant under all actions of a linear group $G$. Are there any other results that reduces the complexity of deciding if a fixed degree $G$-invariant polynomial is non-negative for $G \ne S_{n}$?

(1): Riener, Cordian. "Symmetric semi-algebraic sets and non-negativity of symmetric polynomials." arXiv preprint [arXiv:1409.0699] (2014).

(2): Murty, Katta G., and Santosh N. Kabadi. "Some NP-complete problems in quadratic and nonlinear programming." Mathematical programming 39.2 (1987): 117-129.

$\endgroup$

1 Answer 1

1
$\begingroup$

In a recent paper (as of 1st February 2015) it is proved that the non-negativity of homogeneous forms invariant under the reflection group defined by a root system $\Phi \subseteq \mathbb{R}^n$ can be reduced to verifying the non-negativity of these forms in the union of the hyperplanes perpendicular to the elements of $\Phi$ [link].

Two examples of applications of this theorem are given in the paper:

  • A symmetric form $F$ of degree $2d < 2n$ is nonnegative if and only if it is so on the hyperplanes $x_i - x_j = 0$;

  • An even symmetric form of degree $2d < 4n$ is nonnegative if and only if it is so on the hyperplanes defined by $x_i = 0$ and by $\pm x_i \pm x_j=0$ for $1 \le i \ne j \le n$.

The paper is:

Jose Acevedo and Mauricio Velasco, Test Sets for Nonnegativity of Polynomials Invariant under a Finite Reflection Group. arXiv preprint arXiv:1502.00252 (2015).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.