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)$.
SOS polynomials with rational coefficients
Gautam
- 1.7k
- 10
- 24