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

Improve this question
$\endgroup$
5
  • 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, 2020 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, 2020 at 20:53
  • 2
    $\begingroup$ This is about factorization in $\mathbb{Q}[i]$, which may be done efficiently. $\endgroup$
    – Fedor Petrov
    Sep 27, 2020 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, 2020 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, 2020 at 22:17

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 2
    $\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, 2020 at 6:20
  • 9
    $\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, 2020 at 9:13
  • $\begingroup$ Mr. @NoamD.Elkies_ math.stackexchange.com/q/4031531/822157, I need to the help. $\endgroup$
    – user164469
    Mar 13, 2021 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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