Semidefinite programming and sums of Hermitian squares of noncommutative polynomials (Q847674)

In this short and well-written paper, the authors present an algorithm for finding sums of Hermitian squares decompositions for polynomials in noncommuting variables. The algorithm is based on the author's ''Newton chip method'', a noncommutative analog of the classical Newton polytope method, and semidefinite programming. Let \(\mathbb{R}\left<\overline{X}\right> = \mathbb{R}\left<X_1,\dots, X_n\right>\) denote the algebra of polynomials in noncommuting variables \(X_1,\dots, X_n\) with real coefficients. The elements in this algebra are called NC polynomials. The algebra \(\mathbb{R}\left<\overline{X}\right> \) becomes a \(*\)-algebra with the involution \(*\) that fixes \(\mathbb{R}\cup \{\overline{X}\}\). Let \[ \mathrm{Sym} \mathbb{R}\left<\overline{X}\right> = \{f \in \mathbb{R}\left<\overline{X}\right> : f = f^{*} \}. \] An NC polynomial of the form \(g*g\) is called a \textit{Hermitian square} and the set of all sums of Hermitian squares is denoted by \(\Sigma^2\). Clearly, \(\Sigma^2 \subsetneq \mathrm{Sym} \mathbb{R}\left<\overline{X}\right> \). This article presents an effective \textit{tight} algorithm to compute a Hermitian squares decomposition of a particular symmetric NC polynomial in case this decomposition exists. The algorithm developed in this paper fills an important gap in the new and highly active area of free semialgebraic geometry.