Non-existence of degree bounds for weighted sums of squares representations (Q2577530): Difference between revisions

The purpose of this article, as it is very clearly indicated in its title, is to prove the non-existence of degree bounds for weighted sums of squares representations. More precisely, given a family of polynomials \(h_1,\dots,h_r\in{\mathbb R}[x_1,\dots,x_n]\), the author studies the problem of representing polynomials in the form \(f=s_0+s_1h_1+\cdots+s_rh_r\) with sums of squares \(s_i\). Let \(M\) be the quadratic cone of all \(f\) which admit such a representation. As the author indicates, there are two computational issues associated with \(M\), called the recognition problem and the realization problem. The first one is to decide whether a given polynomial \(f\) lies in \(M\), that is, has a representation \(f=s_0+s_1h_1+\cdots+s_rh_r\) with sums of squares \(s_i\). The second one is to find such a representation explicitly. The case \(r=0\) deals with the representation of polynomials as sums of squares and the recognition problem and the realization problem have been studied by \textit{V. Powers} and \textit{T. Wörmann} through a ``Gram matrices algorithm'' [J. Pure Appl. Algebra 127, 99--104 (1998; Zbl 0936.11023)]. As the author says, similar results could be obtained provided one has a function \(\varphi:{\mathbb N}\to{\mathbb N}\) with the property that every \(f\in M\) admits a representation \(f=s_0+s_1h_1+\cdots+s_rh_r\) with sums of squares \(s_i\) such that \(\deg(s_i)\leq \varphi(\deg(f))\). In the case \(r=0\), such function is \(\varphi:{\mathbb N}\to{\mathbb N}:\;d\mapsto \frac{1}{2}d\). If such function \(\varphi\) does not exists, this means for the recognition and realization problems of \(M\) that there cannot be any rule for when to stop the adapted ``Gram matrices algorithm'' in terms only of \(\deg(f)\) [see \textit{Y. E. Nesterov, A. S. Nemerovski}, ``A general approach to polynomial-time algorithms design for convex programming'', Technical Report, Centre for Economics \& Mathematics Institute, USSR Academy of Science, Moscow, (1988)]. From the discussion above it becomes clear that the existence or non-existence of such a bound function \(\varphi\) is a key issue for the complexity of both problems. In this way, the quadratic module \(M\) is called stable if admits such a function \(\varphi\), for one, or equivalently, any finite system of generators. The main result of this article says that if the subset \(K=\{h_1\geq 0,\dots, h_r\geq 0\}\) of \({\mathbb R}^n\) has dimension \(\geq 2\) and the sequence has the moment property (MP), then the problem is not stable. In particular, this includes the case where \(M\) is compact, \(\dim(K)\geq 2\) and the cone \(M\) is multiplicatively closed, which, as the author remarks, was the initial aim of the article. For dimension \(1\), as the author points out, it is easy to see that \(M\) may be stable. As it is usual with this author, this manuscript is very well written and all the results are very clearly exposed. All this makes very pleasant the reading of this article.