# Uniqueness of sum of squares representation

Given a polynomial $$f(x) \in \mathbb{R}[x] = \mathbb{R}[x_{1},\dots,x_{n}]$$. We say $$f(x)$$ is sum of squares(SOS) if there are polynomials, $$p_{1},\dots,p_{k}$$ such that $$f = p_{1}^{2} + \dots+p_{k}^{2}$$. Can we impose conditions on the representation so that $$f$$ is represented uniquely? Or in particular, given that the representation is composed of n-squared terms, can we characterize all such representations and obtain a unique up-to-something conclusion?

I'm working on a paper that is on the convergence of a semidefinite programming algorithm, but my professor thought it would be interesting to include a case about applications to sum of squares. I have no previous exposure to algebraic geometry, so the above problem has been my concern.

Since the algorithm requires (roughly) strong convexity, which implies the uniqueness of minimizer, to converge linearly. I wonder if we can impose any condition so that $$f$$ is represented uniquely.

Of course, we can do stupid things such as $$p(x)^{2} = \left( \sqrt{ \frac{1}{4}}p(x) \right)^{2} + \left(\sqrt{ \frac{3}{4} }(p(x)\right)^{2}$$. From my algebra course, I learned unique factorization domain, but I don't have any experience with algebraic geometry to come up with anything meaningful in this case.

• Please don't call this representation a "factorization", because it isn't one. Commented Dec 22, 2023 at 0:44
• @RobertIsrael Thank you. I just edited the post. Commented Dec 22, 2023 at 1:20
• If $c,s$ are any numbers such that $c^2+s^2=1$, then $f^2+g^2=(cf+sg)^2+(sf-cg)^2$. More generally, if $A$ is any orthogonal matrix and $(f_1,\dotsc,f_n)A=(g_1,\dotsc,g_n)$, then $f_1^2+\dotsb+f_n^2 = g_1^2+\dotsb+g_n^2$. I don't know if there's any reason to expect that this is the full extent of nonuniqueness. Commented Dec 22, 2023 at 1:47
• @ZachTeitler Thank you for the insight. I don't think the other way is true though, even if both representations consist of n-terms, A might not be orthogonal. Is there anything more can say when we restrict to n-terms, such as assuming $f_1 ,\dots, f_n$ are linearly independent? Commented Dec 22, 2023 at 18:14

For one source of nonuniqueness, note that $$a^2 + b^2 = c^2 + d^2$$ is equivalent to $$(a+c)(a-c) = (d+b)(d-b)$$. For any polynomials $$s,t,u,v$$ we can take $$a+c = st$$, $$a-c = uv$$, $$d+b=su$$ and $$d-b = tv$$ with \eqalign{ a &= (uv+st)/2 \cr b &= (su - tv)/2\cr c &= (uv - st)/2\cr d &= (su + tv)/2\cr}

This is not a full answer, rather a possible direction. I guess it would be interesting for you to look at the Gram representation of a polynomial which is given by

$$p(x)=z(x)^TMz(x)$$

where $$M$$ is a symmetric matrix and $$z(x)$$ is a vector of monomials. We have that $$p(x)$$ is SOS if and only if $$M$$ is positive definite.

In many cases, there are relationships between the monomials within $$z(x)$$ and this is reflected by the fact that the kernel

$$\mathcal{K}=\{N\ \mathrm{symetric}:z(x)^TNz(x)=0\ \mathrm{for\ all\ }x\}$$ is non-empty. The fact that the kernel is non-empty means that your representation is non-unique since

$$p(x)=z(x)^T(M+N)z(x)$$ for all $$N\in \mathcal{K}$$.