Suppose we are given a univariate polynomial $p(x)$ with rational coefficients, and are told that $p(x)$ can be expressed as the sum of $k$ squares of polynomials with rational coefficients. It is well-known that every univariate SOS polynomial can be expressed as a sum of two squares. Can we efficiently find a representation of $p(x)$ as $f^2(x) + g^2(x)$, where both f and g have rational coefficients? Just to be clear: I want an efficient algorithm which 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)$.

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

Suppose we are given a univariate polynomial $p(x)$ with rational coefficients, and are told that $p(x)$ is SOS. It is well-known that every univariate SOS polynomial can be expressed as a sum of two squares. Can we efficiently find a representation of $p(x)$ as $f^2(x) + g^2(x)$, where both f and g have rational coefficients? Just to be clear: I want an efficient algorithm which takes as input an SOS polynomial $p(x)$ with rational coefficients and outputs two polynomials $f(x), g(x)$ with rational coefficients such that $p(x) = f^2(x) + g^2(x)$.

Suppose we are given a univariate polynomial $p(x)$ with rational coefficients, and are told that $p(x)$ can be expressed as the sum of $k$ squares of polynomials with rational coefficients. It is well-known that every univariate SOS polynomial can be expressed as a sum of two squares. Can we efficiently find a representation of $p(x)$ as $f^2(x) + g^2(x)$, where both f and g have rational coefficients? Just to be clear: I want an efficient algorithm which 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)$.