# SOS polynomials with rational coefficients

Suppose we are given a univariate polynomial with rational coefficients, $$p \in \Bbb Q [x]$$, and are told that $$p$$ can be expressed as the sum of $$k$$ squares of polynomials with rational coefficients. It is well-known that every univariate sum of squares (SOS) polynomial can be expressed as a sum of two squares.

Can we efficiently find an SOS decomposition $$p = f^2 + g^2$$, where both $$f, g \in \Bbb Q [x]$$?

Just to be clear: I want an efficient algorithm that takes as input a polynomial $$p(x)$$, which is guaranteed to have a representation as the sum of $$k$$ squares of polynomials with rational coefficients, and outputs two polynomials $$f(x), g(x)$$ with rational coefficients such that

$$p(x) = f^2(x) + g^2(x)$$

• Is this always possible? How would you express the constant polynomial 3 as a sum of two squares of rational polynomials? EDIT: I guess your assumption is that $p$ is the SOS of rational polynomials? – Olivier Bégassat Sep 27 at 20:41
• Yes, you may assume that $p(x)$ has a representation as a sum of squares of rational polynomials (though this may involve more than two squares!). The tricky part is finding a representation as a sum of two squares, and also doing it efficiently. I edited the question for clarity. – Gautam Sep 27 at 20:53
• This is about factorization in $\mathbb{Q}[i]$, which may be done efficiently. – Fedor Petrov Sep 27 at 21:22
• Fedor, I didn't quite understand your comment. Are you suggesting we first factor $p(x)$ over the rationals and then use this factorization to obtain the desired decomposition? Can you please elaborate? – Gautam Sep 27 at 21:54
• I guess the idea is that $p(x)=(f(x)-ig(x))(f(x)+ig(x))$? But how is finding this factorization easier than the proposed problem? – user347489 Sep 27 at 22:17

In general you can't write $$p = f^2 + g^2$$ in $${\bf Q}[x]$$ at all, let alone do so efficiently.
For example, $$2 x^2 + 3$$ is positive for all $$x$$ (and is the sum of three squares, $$(x+1)^2 + (x-1)^2 + 1^2$$); but if $$2 x^2 + 3 = f(x)^2 + g(x)^2$$ then $$3 = f(0)^2 + g(0)^2$$, which is impossible because $$3$$ is not a sum of two rational squares. (Cf. the comment of Olivier Bégassat.)
A positive quadratic polynomial can still be written as $$a f(x)^2 + b g(x)^2$$ for rational $$a,b > 0$$; but in degree $$4$$ and beyond even that is not usually true, for Galois-theoretic reasons, using the factorization $$a f^2 + b g^2 = a (f+cg) (f-cg)$$ with $$c^2 = -b/a$$. For example, if $$p$$ has degree $$n$$ and Galois group $$S_n$$ (which is the usual case) then $$p$$ cannot be written as $$a f^2 + b g^2$$. Already $$p = x^4 + x + 1$$ is an example.