Skip to main content
3 of 4
edited title
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

SOS polynomials with rational coefficients

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

Gautam
  • 1.7k
  • 10
  • 24