Deciding positivity of multisymmetric polynomials (Q898286)

A simple form of the half degree principle, discovered by \textit{V. Timofte} [J. Math. Anal. Appl. 284, No. 1, 174--190 (2003; Zbl 1031.05130)], says that nonnegativity on \(\mathbb{R}^n\) of a polynomial \(f\) of degree\(\geq 4\) in the ring \(\mathbb{R}[X_1,\dots,X_n]^{S_n}\) of symmetric polynomials, is guaranteed if it is nonnegative on all real \(n\)-tuples with not more than \( \deg f/2\) distinct components. A particularly nice proof of this was found by \textit{C. Riener} [J. Pure Appl. Algebra 216, No. 4, 850--856 (2012; Zbl 1242.05272)]. In the present paper, results of this type are found for multisymmetric polynomials. They are applied to give favorable upper bounds for the computational complexity of testing nonnegativity and convexity in the class of multisymmetric polynomials polynomials. In the general nonsymmetric case, these problems are NP-hard; see [\textit{A. A. Ahmadi} et al., Math. Program. 137, No. 1--2 (A), 453--476 (2013; Zbl 1274.90516)]. Let \(V=\mathbb{R}^n\) and denote by \(\mathbb{R}[V^k]\) the family of all real polynomials in \(nk\) variables named \(X_{11}, \dots, X_{nk}.\) Think of these as arranged of in an \(n\times k\) matrix. Then, a polynomial \(f\in \mathbb{R}[V^k] \) is \(k\)-symmetric if (after suitable renaming of its variables) it is invariant under permutations of the rows. These we denote by \(X_{i\cdot},\) while the columns are abbreviated \(X_{\cdot j},\) \(i=1,\dots,n; j=1,\dots,k.\) A monomial in \(\mathbb{R}[V^k]\) has the form \(X_{1\cdot }^{\alpha(1)} X_{2\cdot}^{\alpha(1)} \cdots X_{n\cdot}^{\alpha(n)},\) where \(\alpha(i)=(\alpha_1(i),\dots, \alpha_k(i))\in \mathbb{Z}_{\geq 0}^k\) and \(X_{i\cdot}^{\alpha(i)}=X_{i1}^{\alpha_1(i)} \cdots X_{ik}^{\alpha_k(i)}.\) Let \(w\in \mathbb{Z}_{\geq 1}^k.\) Then, the \(w\)-degree of the monomial is defined as \(\sum_{i=1}^n\sum_{j=1}^k w_j \alpha_j(i)\) and for \(f\in \mathbb{R}[V^k]\), \(\deg_w f\) is simply the maximum \(w\)-degree of its monomials. A special role among the \(k\)-symmetric polynomials is played by the polynomials \(p_{\alpha}=\text{sym}(X_{1.}^\alpha),\) where `sym' denotes the evident symmetrization operator. The \(p_\alpha\) are the natural generalization of the classical powersums to multiples of which they revert for \(k=1.\) Let \(N_d:=\{\alpha\in \mathbb{Z}_{\geq 0}: \alpha \cdot w \leq d\}.\) It can be shown, see [\textit{J. Dalbec}, Beitr. Algebra Geom. 40, No. 1, 27--51 (1999; Zbl 0953.05077)], that for a \(k\)-symmetric \(f\) of \(w\)-degree \(\leq d\) there exists a polynomial \(F\) such that \(f=F(\{p_{\alpha}\}_{\alpha \in N^d} ).\) Denote by \(A_m\) the set of matrices in \(\mathbb{R}^{n\times k}\) with at most \(m\) distinct rows. \(A_m\) is the union of less than \(n^m\) \(mk\)-dimensional subspaces of \(\mathbb{R}^{n\times k}.\) For \(r>0\), let \(B_r\) be the euclidean 0-centered ball of radius \(r\) in \(\mathbb{R}^{n\times k}\) and for \(f\in \mathbb{R}[V^k]\) let \(\kappa(f)\) be the smallest \(m\) such that for all \(r>0\), \(\min_{x\in A_m} f(x)=\min_{x\in B_r\cap A_m} f(x).\) The main theorem is Theorem 14: If \(f\in\mathbb{R}[V^k]^{S_n},\) and \(\deg_w f \leq d \geq \max\{2w_j:j=1,\dots,k\},\) then \(\kappa(f) \leq \prod_{j=1}^k \lfloor d/w_j \rfloor.\) The proof of this theorem uses above polynomial representation of \(f\) via the \(p_\alpha\) and gives in dependence of \(F\) often much better information. Furthermore, using the characterization of the \(A_{\kappa(f)}\) above, it follows that for the class of polynomials in \(\mathbb{R}[V^k]^{S_n},\) the complexity of testing positivity grows only polynomially in the number of variables. Subjecting a polynomial \(f\in \mathbb{R}[V^k]\) to the morphism defined by \(\varphi(X_{ij})=Y_j,\) one gets a polynomial in \(\mathbb{R}[Y_1,\dots,Y_k]\) whose monomials define \(k\)-tuples exponents. Letting \(E_f\) be the set of these k-tuples, one can deduce that if \(E_f\subset \text{conv}(0,a_1e_1,\dots,a_ke_k),\) (with rationals \(a_i\) and \(e_i\) the standard vectors) then \(\kappa(f)\leq \prod_{j=1}^k \lfloor a_j \rfloor,\) which is the number of lattice points in \([0,a_1-1]\times \cdots \times [0,a_k-1].\) The authors use this to give as their second main result a bound for \(\kappa(g_f)\) where \(g_f\) means the `quadratic' form associated to the Hessian matrix of \(f.\) (As the Hessian is a matrix whose entries are of degree up to \(d-2\), \(g_f\) is in fact a polynomial of degree up to \(d.\)) For example, a simple corollary is that if \(f\in\mathbb{R}[V^k]^{S_n},\) has (usual) degree \(d\), then \(\kappa(g_f) \leq 6^k (d-2)^k.\) Such bounds imply that the complexity of deciding convexity in the class of \(k\)-symmetric polynomial of degree \(\leq d\) grows polynomially in the number of variables.