# SOS polynomials with integer coefficients

A well known theorem of Polya and Szego says that every non-negative univariate polynomial $$p(x)$$ can be expressed as the sum of exactly two squares: $$p(x) = (f(x))^2 + (g(x))^2$$ for some $$f, g$$. Suppose $$p$$ has integer coefficients. In general, its is too much to hope that $$f, g$$ also have integer coefficients; consider, for example, $$p(x) = x^2 + 5x + 10$$. Are there simple conditions we can impose on $$p$$ that guarantee that $$f, g$$ have integer coefficients?

• Clearly a necessary condition is that $p(n)$ is a sum of two squares for every integer $n$. Could this condition be sufficient? Is there a nice characterization of polynomials with this property? May 29, 2020 at 3:03
• Not an answer, just a comment: The result that a nonnegative univariate polynomial is a sum of two squares is a direct consequence of the fundamental theorem of algebra. The result by Polya and Szegö is more subtle, it deals with polynomials on $[0,\infty[$. May 29, 2020 at 4:47
• @KasperAndersen Thanks for the correction. The result I found states that if $p(x) \geq 0$ for all $x \geq 0$ then there exist $f, g, h, k$ so that $p(x) = f(x)^2 + g(x)^2 + x(h(x)^2 + k(x)^2)$. Is that the result you were referring to? If so, I'd be interested in understanding when $f, g, h, k$ have integer coefficients as well. May 29, 2020 at 18:12

There is the following result of Davenport, Lewis, and Schinzel [DLS64, Cor to Thm 2]:

Theorem. Let $$p \in \mathbf Z[x]$$. Then the following are equivalent:

1. $$p$$ is a sum of two squares in $$\mathbf Z[x]$$;
2. $$p(n)$$ is a sum of two squares in $$\mathbf Z$$ for all $$n \in \mathbf Z$$;
3. Every arithmetic progression contains an $$n$$ such that $$p(n)$$ is a sum of two squares in $$\mathbf Z$$.

Criterion 3 is really weak! For example, it shows that in 2, we may replace $$\mathbf Z$$ by $$\mathbf N$$. Because it's short but takes some time to extract from [DLS64], here is their proof, simplified to this special case.

Proof. Implications 1 $$\Rightarrow$$ 2 $$\Rightarrow$$ 3 are obvious. For 3 $$\Rightarrow$$ 1, factor $$p$$ as $$p = c \cdot p_1^{e_1} \cdots p_r^{e_r}$$ with $$p_j \in \mathbf Z[x]$$ pairwise coprime primitive irreducible and $$c \in \mathbf Q$$. We only need to treat the odd $$e_j$$ (and the constant $$c$$). Let $$P = p_1 \cdots p_r$$ be the radical of $$p/c$$, and choose $$d \in \mathbf N$$ such that $$P$$ is separable modulo every prime $$q \not\mid d$$. Suppose $$P$$ has a root modulo $$q > 2d\operatorname{height}(c)$$; say $$P(n) \equiv 0 \pmod q$$ for some $$n$$. Then $$P'(n) \not\equiv 0 \pmod q$$, hence $$P(n+q) \not\equiv P(n) \pmod{q^2}$$. Replacing $$n$$ by $$n+q$$ if necessary, we see that $$v_q(P(n)) = 1$$; i.e. there is a $$j$$ such that $$v_q\big(p_i(n)\big) = \begin{cases}1, & i = j, \\ 0, & i \neq j.\end{cases}.$$ If $$e_j$$ is odd, then so is $$v_q(p(n))$$, which equals $$v_q(p(n'))$$ for all $$n' \equiv n \pmod{q^2}$$. By assumption 3 we can choose $$n' \equiv n \pmod{q^2}$$ such that $$p(n')$$ is a sum of squares, so we conclude that $$q \equiv 1 \pmod 4$$. If $$L = \mathbf Q[x]/(p_j)$$, then we conclude that all primes $$q > 2d\operatorname{height}(c)$$ that have a factor $$\mathfrak q \subseteq \mathcal O_L$$ with $$e(\mathfrak q) = f(\mathfrak q) = 1$$ (i.e. $$p_j$$ has a root modulo $$q$$) are $$1$$ mod $$4$$. By Bauer's theorem (see e.g. [Neu99, Prop. VII.13.9]), this forces $$\mathbf Q(i) \subseteq L$$.

Thus we can write $$i = f(\theta_j)$$ for some $$f \in \mathbf Q[x]$$, where $$\theta_j$$ is a root of $$p_j$$. Then $$p_j$$ divides $$N_{\mathbf Q(i)[x]/\mathbf Q[x]}\big(f(x)-i\big) = \big(f(x)-i\big)\big(f(x)+i\big),$$ since $$p_j$$ is irreducible and $$\theta_j$$ is a zero of both. Since $$f(x)-i$$ and $$f(x)+i$$ are coprime and $$p_j$$ is irreducible, there is a factor $$g \in \mathbf Q(i)[x]$$ of $$f(x)+i$$ such that $$p_j = u \cdot N_{\mathbf Q(i)[x]/\mathbf Q[x]}(g) = u \cdot g \cdot \bar g$$ for some $$u \in \mathbf Q[x]^\times = \mathbf Q^\times$$. Applying this to all $$p_j$$ for which $$e_j$$ is odd, we get $$p = a \cdot N_{\mathbf Q(i)[x]/\mathbf Q[x]}(h)$$ for some $$h \in \mathbf Q(i)[x]$$ and some $$a \in \mathbf Q^\times$$. By assumption 3, this forces $$a$$ to be a norm as well, so we may assume $$a = 1$$. Write $$h = \alpha H$$ for $$\alpha \in \mathbf Q(i)$$ and $$H \in \mathbf Z[i][x]$$ primitive. Then $$p(x) = |\alpha|^2 H \bar H,$$ so Gauss's lemma gives $$|\alpha|^2 \in \mathbf Z$$. Since $$|\alpha|^2$$ is a sum of rational squares, it is a sum of integer squares; say $$|\alpha|^2 = |\beta|^2$$ for somce $$\beta \in \mathbf Z[i]$$. Finally, setting $$F + iG = \beta H,$$ we get $$p = F^2 + G^2$$ with $$F, G \in \mathbf Z[x]$$. $$\square$$

Footnote: I am certainly surprised by this, given that the version for four squares is clearly false. Indeed, the condition just reads $$p(n) \geq 0$$ for all $$n \in \mathbf Z$$. But the OP's example cannot be written as any finite sum of squares in $$\mathbf Z[x]$$, because exactly one of the terms can have positive degree. (However, it might be different in $$\mathbf Q[x]$$.)

References.

[DLS64] H. Davenport, D. J. Lewis, and A. Schinzel, Polynomials of certain special types. Acta Arith. 9 (1964). ZBL0126.27801.

[Neu99] J. Neukirch, Algebraic number theory. Grundlehren der Mathematischen Wissenschaften 322 (1999). ZBL0956.11021.

• Thanks for this thoughtful answer. Do you have any thoughts about the situation in Q[x]? Jul 9, 2020 at 0:59
• Can't you just clear denominators? Like, multiply with a large square to assume $p \in \mathbf Z[x]$, and apply the criterion of DLS? Jul 9, 2020 at 15:17