Co-author: Dimitri Pasechnik
Title: Algorithmic aspects of Hilbert's 17th problem for ternary forms and related problems
Presentation Slides


A form p on Rⁿ (homogeneous n-variate polynomial) is called positive semidefinite if it is nonnegative on Rⁿ. In other words, the zero vector is a global minimizer of p in this case. The famous 17th conjecture of Hilbert (later proven by Artin) is that a form p is positive semidefinite if and only if it can be decomposed a sum of squares of rational functions. In this paper we give an algorithm to compute such a decomposition for ternary forms (n=3). This algorithm involves the solution of a series of systems of linear matrix inequalities (LMI's). In particular, for a given positive semidefinite ternary form p of degree 2m, we show that the abovementioned decomposition can be computed by solving at most m/4 systems of LMI's of dimensions polynomial in m. The underlying methodology is largely inspired by the original proof of Hilbert, who had been able to prove his conjecture for the case of ternary forms.