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
    Commented 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
    Commented Sep 27, 2020 at 20:53
  • 2
    $\begingroup$ This is about factorization in $\mathbb{Q}[i]$, which may be done efficiently. $\endgroup$
    – Fedor Petrov
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Sep 28, 2020 at 9:13
  • $\begingroup$ Mr. @NoamD.Elkies_ math.stackexchange.com/q/4031531/822157, I need to the help. $\endgroup$
    – user164469
    Commented Mar 13, 2021 at 12:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .