10
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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? $\endgroup$ – Olivier Bégassat Sep 27 at 20:41
  • $\begingroup$ 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. $\endgroup$ – Gautam Sep 27 at 20:53
  • 2
    $\begingroup$ This is about factorization in $\mathbb{Q}[i]$, which may be done efficiently. $\endgroup$ – Fedor Petrov Sep 27 at 21:22
  • $\begingroup$ 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? $\endgroup$ – Gautam Sep 27 at 21:54
  • $\begingroup$ 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? $\endgroup$ – user347489 Sep 27 at 22:17
20
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Hi Noam, thanks a lot for this thoughtful reply. My next question is: is there a simple condition we can impose on a SOS polynomial which guarantees that it can be written as a sum of two polynomials with rational coefficients? I'm fine with any simple sufficient condition, not necessarily a full characterization of such polynomials. $\endgroup$ – Gautam Sep 28 at 6:20
  • 7
    $\begingroup$ @Gautam Comments aren't a good place to rise new questions. I guess you should accept Elkies' answer, open a new question, and reference to the present one whose answer inspired it. $\endgroup$ – Peter Mueller Sep 28 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.