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)$$



SOS polynomials with rational coefficients
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](https://mathoverflow.net/questions/372753/sos-polynomials-with-rational-coefficients#comment943118_372753) 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.


