# Decomposing polynomials with integer coefficients

Can every quadratic with integer coefficients be written as a sum of two polynomials with integer roots? (Any constant $k \in \mathbb{Z}$, including $0$, is also allowed as a term for simplicity's sake.)

(In other words, is any given $P(x) = A + Bx + Cx^2$ expressible as

$$P(x) = \color{red}{k(x-r_1)(x-r_2)\cdots(x-r_n)} + \color{blue}{\ell(x-s_1)(x-s_2)\cdots(x-s_m)}$$

where all variables other than $x$ are integers?) As an example of such a decomposition, if $C = 1$ then $P(x) = (A - Ax) + (Ax + Bx + x^2) = \color{red}{-A(x-1)} + \color{blue}{(x)(x+A+B)}$. The "two polynomials" restriction is essential; expressions like $P(x) = \color{red}{(A)} + \color{green}{(Bx)} + \color{blue}{(Cx^2)}$ don't count.

I've been contemplating this statement for a while and could use some help. I'm having trouble whether trying to prove it or find a (verifiable) counterexample. (Note that the components can have arbitrarily high degrees $n,m$ but cancel out to give $P(x)$.) Variations on completing the square didn't help.

If the answer is affirmative, I would also be interested in the following generalizations:

• In addition to quadratics, can higher-order polynomials be decomposed into two polynomials?

• (Refinement of the above if it is true) If two polynomials do not suffice for $P(x)$ of arbitrary degree, is there a finite number $N$ that does?

Thanks in advance for any ideas or help.

Note: I have used the colors I can most easily distinguish in the question, but if they cause other people difficulty please feel free to change them or remove them.

-
This is resisting everything I've thrown at it. I believe it's possible to decompose any quadratic into two quadratics in this way, and Mathematica has verified that this can be done up to $\bmod \gcd(C,n)$ for $n\leq 30$, but I am far from a proof. –  Alex Becker Jul 6 '12 at 21:23
Not sure if it matters, but the decomposition isn't unique. For example, $P(x) = x^2 + 6 x + 7$ can be written as $\color{red}{(x+2)(x+3)} + \color{blue}{(x+1)}$ or $\color{red}{(x+1)(x+4)} + \color{blue}{(x+3)}$. –  csd Jul 16 '12 at 21:02
@csd: Yes, I am aware of this. The existence is what I'd like to know about. –  Vandermonde Jul 21 '12 at 0:40

(EDIT: Gerry Myerson pointed out a serious oversight in my previous answer. In the following answer, I consider polynomials with integer roots to have degree at least one, meaning nonzero constants are considered as a separate case. I believe this will address the gap found by Gerry.)

$1 + 9x + 27x^2$ cannot be expressed as either the sum of a constant and a polynomial with integer roots, or the sum of two polynomials with integer roots.

First, we'll show that $1 + 9x + 27x^2$ cannot be decomposed as a constant plus a polynomial with integer roots. Suppose to the contrary that $1 + 9x + 27x^2 = a + c(x+r_1)(x+r_2)$ for some integers $a, c, r_1, r_2$. Then $1 + 9x + 27x^2 = (a + cr_1r_2) + c(r_1 + r_2)x + cx^2$, and so $c = 27$. However, no integer values of $r_1, r_2$ will make $c(r_1 + r_2) = 27(r_1 + r_2) = 9$, meaning $1 + 9x + 27x^2$ has no such decomposition.

To prove the second assertion, we'll establish that there are families of quadratics which, if written as the sum of two polynomials with integer roots, can only be decomposed as the difference of two cubics. We can then demonstrate the impossibility of decomposing $1 + 9x + 27x^2$ in this way using modular arithmetic and brute force. First it will be useful to prove some intermediate results.

Lemma 1.1. A polynomial $f$ where the leading coefficient does not divide $f(n)$ for any $n$ cannot be expressed as the sum of two polynomials with integer roots of differing degrees.

Proof. Note that $f$ cannot have integer roots, otherwise the leading coefficient would divide $f(n) = 0$ for some $n$. Now suppose $f$ has a decomposition as: $$f(x) = k(x + r_1)(x + r_2)\cdots(x + r_i) + l(x + s_1)(x + s_2)\cdots(x + s_j)$$ with $i \ne j$. WLOG, let $i > j$. Since $f$ has no integer roots, both $k$ and $l$ are not zero. Consequently, $i$ must equal the degree of $f$ and $k$ must equal the leading coefficient of $f$. However, by evaluating the polynomial at $x = -s_1$, we see that $k$ divides $f(-s_1)$, a contradiction. So there is no such decomposition. $\square$

Lemma 1.2. A polynomial $f$ which is odd for all $f(n)$, when decomposed into the sum of two polynomials with integer roots, must be the sum of one polynomial with all even roots and the other with odd roots.

Proof. Note that $f$ has no integer roots, and so $k$ and $l$ are not zero. Now we examine the decomposition of $f$ as $$f(x) = k(x + r_1)(x + r_2)\cdots(x + r_i) + l(x + s_1)(x + s_2)\cdots(x + s_j)$$ Given that $f(0)$ is odd, exactly one of the terms on the RHS is odd for the substitution $x = 0$. WLOG, suppose the first term is odd; all factors are also odd, and so $k, r_1, r_2, \ldots, r_i$ are odd. Given that $f(1)$ is odd, the first term is even for the substitution $x = 1$, and by repeating our previous analysis we discover that $l, s_1 + 1, s_2 + 1, \ldots, s_j + 1$ are odd. This implies that $s_1, s_2, \ldots, s_j$ are even. So one polynomial in the decomposition of $f$ must have all even roots, and the other odd. $\square$

Lemma 1.3. If a quadratic polynomial $f(x) = a + bx + cx^2$ with odd coefficients such that $\gcd(b, c) \not\mid a$ can be decomposed into two polynomials with integer roots, each polynomial in the decomposition must be cubic.

Proof. For quadratic polynomials, $\gcd(b, c) \not\mid a$ is equivalent to the condition that $c$ never divides $f(n)$ for any $n$, so we can apply lemma (1.1). Since $f(n)$ is also odd for all $n$ we may also use lemma (1.2). Then consider the decomposition of $f$ as $$f(x) = a + bx + cx^2 = k(x + r_1)(x + r_2)\cdots(x + r_i) + l(x + s_1)(x + s_2)\cdots(x + s_j)$$ From lemma (1.1), we know that $i = j$. From lemma (1.2), we can suppose WLOG that the first polynomial on the RHS has all odd roots. Reinterpreting the decomposition modulo 2, we have \begin{align} f(x) \equiv 1 + x + x^2 & \equiv (x+1)^i + x^j \pmod 2 \\ & \equiv (x+1)^j + x^j \pmod 2 \\ & \equiv (x+1)^j - x^j \pmod 2 \end{align}

The coefficients of $(x+1)^j$ are the binomial coefficients; so the coefficient of the linear term is ${j \choose j-1} = {j \choose 1} = j$, which for even $j$ does not match the parity of the linear term of $f$. For odd $j$, the coefficient of the $x^{j-1}$ term is also ${j \choose 1}$, but since all terms with degree greater than two have coefficients equal to zero, $j$ must equal three. So if quadratics with odd coefficients which satisfy lemma (1.1) can decomposed into two polynomials with integer roots, they can only be expressed as the sum (difference) of two cubics with integer roots. $\square$

Remark. With some trial and error, we can demonstrate polynomials which are not decomposable as the sum of two polynomials with integer roots on the strength of lemma (1.2) alone. For example, no values of $i$, $j$ will make $(x+1)^i + x^j \equiv 1 + x^3 + x^5 \pmod 2$.

Now, specifically, we aim to show that $1 + 9x + 27x^2$ cannot be decomposed into two cubics, and therefore into two polynomials with integer roots.

The easiest approach is bruteforce calculation: since $f(x) = 1 + 9x + 27x^2$ satisfies all criteria of lemma (1.3), we consider a decomposition for $f$ as the difference of two cubics \begin{align} f(x) & = & 1 + 9x + 27x^2 & = (x + r_1)(x + r_2)(x + r_3) - (x + s_1)(x + s_2)(x + s_3) \\ & \equiv & 1 & \equiv (x + r_1)(x + r_2)(x + r_3) - (x + s_1)(x + s_2)(x + s_3) \pmod 9 \end{align} and attempt to find suitable values of $r_1, r_2, r_3, s_1, s_2, s_3$ such that the RHS remains equivalent to one (modulo 9) for all values of $x$.

The following Javascript function will generate an array of all the unique triples $r_1, r_2, r_3$ for a given modulus, which can be taken to be the roots of a cubic under the same modulus, and the order of elements doesn't matter. Then it tries all pairs of triples hoping to find a pair whose difference remains equivalent to the target (with respect to the modulus) for all substitutions of $x$.

function pairsOfCubicsDifferenceEquivalentToXmoduloY(target, modulus) {
target = mod(target, modulus);

/* Generate all unique triples. */
for (var i = 0, triplets = []; i < modulus; ++i) {
for (var j = i; j < modulus; ++j) {
for (var k = j; k < modulus; ++k) {
triplets.push([i,j,k]);
}
}
}

/* Brute force. Try all pairs of triples. */
for (var i = 0, result = []; i < triplets.length; ++i) {
for (var j = 0; j < triplets.length; ++j) {
for (var x = 0; x <= modulus; ++x) {
if (
mod(    (x+triplets[i][0])*(x+triplets[i][1])*(x+triplets[i][2])
- (x+triplets[j][0])*(x+triplets[j][1])*(x+triplets[j][2])
, modulus) != target) {
break;
}
/* Full circle! A solution. */
if (x == modulus) {
result.push( [triplets[i], triplets[j]] );
}
}
}
}

return result;

/* Auxiliary: make remainder a nonnegative value. */
function mod(x, modulus) {
return ((x % modulus) + modulus) % modulus;
}
}


Anticlimactically, evaluating pairsOfCubicsDifferenceEquivalentToXmoduloY(1, 9) will return no results, and so $1 + 9x + 27x^2$ cannot be expressed as the difference of two cubics, or therefore as the sum of two polynomials with integer roots. $\square$

(One!) further thought: the following observations let us give another exposition of a result by RicardoCruz, where he shows that quadratics $f(x) = a + bx + cx^2$ where $\gcd(b, c) \mid a$ can be decomposed systematically.

Observation 2.1 (Shifting.) If a quadratic $f(x)$ has a decomposition $$f(x) = a + bx + cx^2 = k(x + r_1)(x + r_2)\cdots(x + r_i) + l(x + s_1)(x + s_2)\cdots(x + s_j)$$ then it has a decomposition $f(x+n)$ for any integer $n$. $$f(x+n) = f(n) + (2cn+b)x + cx^2 = k(x + n+r_1)(x + n+r_2)\cdots(x + n+r_i) + l(x + n+s_1)(x + n+s_2)\cdots(x + n+s_j)$$

Observation 2.2 (Linear terms are absorbent.) For a quadratic $f(x) = a + bx + cx^2$, if the leading coefficient divides the constant term, we can decompose $f$ into polynomials with integer roots. Let $a = cpq$ and rewrite $f$ as \begin{align} f(x) & = a + bx + cx^2 \\ & = cpq + bx + cx^2 \\ & = c(x^2 + pq) + bx \\ & = c(x + p)(x + q) - c(p+q)x + bx \\ f(x) & = c(x + p)(x + q) + (b - c[p+q])x \end{align}

Returning now to our initial motivation. If $f(x) = a + bx + cx^2$ and $\gcd(b, c) \mid a$, we can factor out $\gcd(b, c)$ from each term, so after pulling out a constant we may assume that $\gcd(b, c) = 1$. Now we can find an $n$ such that $c \mid f(n)$, by considering the quadratic modulo $c$. \begin{align} f(n) & \equiv 0 \pmod c \\ a + bn + cn^2 & \equiv 0 \pmod c \\ bn & \equiv -a \pmod c \\ \end{align} where $b$ is invertible since $\gcd(b, c) = 1$. If we "shift" $f(x)$ by $n$ using observation (2.1), then the constant term $f(n)$ will be divisible by $c$, and we can apply observation (2.2) to find a decomposition for $f(x+n)$, then shift back by $-n$ to get a decomposition for $f(x)$.

Let's take an example from RicardoCruz's answer, where $f(x) = 2 + 57x + 31x^2$. \begin{align} f(n) & \equiv 0 \pmod {31} \\ 2 + 57n + 31n^2 & \equiv 0 \pmod {31} \\ -5n & \equiv -2 \pmod {31} \\ n & \equiv -12 \pmod {31} \end{align}

and then \begin{align} f(x) & = 2 + 57x + 31x^2 \\ f(x-12) & = 2 + 57(x-12) + 31(x-12)^2 \\ & = 3782 - 687x + 31x^2 \\ & = 31(x^2 + 122) - 687x \\ \end{align}

We can pick any divisors of $122$, so why not $-2$ and $-61$? \begin{align} f(x-12) & = 31(x^2 + [-2][-61]) - 687x \\ & = 31(x - 2)(x - 61) + (31 \cdot 63)x - 687x \\ & = 31(x - 2)(x - 61) + 1266x \\ f([x+12] - 12) & = 31([x+12] - 2)([x+12] - 61) + 1266[x+12] \\ f(x) & = 31(x + 10)(x - 49) + 1266(x+12) \end{align} which agrees with RicardoCruz's analysis.

-
This is an exciting development! I got to see whether this argument goes through when I have time –  Vandermonde Apr 6 at 23:37
Thanks! It is a large chunk of information; I hope the exposition is clear. –  kate Apr 7 at 0:29
But $1+9x+9x^2=(1)+(9x+9x^2)$, and all the solutions of $1=0$ are integers, and all the solutions of $9x+9x^2=0$ are integers. –  Gerry Myerson Jul 25 at 0:32
@Gerry, I hope I haven't misread you, but I can't see how a nonzero constant polynomial has integer roots? I'm worried I'm missing something important, but while your example $f(x) = 1$ does have integer coefficients, I understood that to be a separate term in a decomposition it also needs to have integer roots. –  kate Jul 25 at 5:49
I didn't say $1=0$ has integer roots; I said, all of its roots are integers. You can't find a root that's not an integer, can you? And if you look at the statement of the question, it's quite clear that constants are counted as polynomials with only integer roots. I'll think about $27x^2+9x+1$. –  Gerry Myerson Jul 25 at 6:17

If $a$ is a multiple of $b$, so that $a =mb$, you can decompose in this way:
$$a+bx+cx^2=c(x-b)(x+b)+b(x+cb+m)$$
or, if you prefer:
$$a+bx+cx^2=cx^2+b(x+m)$$
But if $a$ can be expressed as $a=mb-n^2c$, where $m$ and $n$ are integers, then we can decompose the polynomial in this way: $$a+bx+cx^2=c(x-n)(x+n)+b(x+m)$$
Let's see an example that cannot be included in the previous cases ($a=mb$ and $a=mb-n^2c$).

Let $P(x)=2+57x+31x^2$, and let's decompose $P(x)$ in this way: $$2+57x+31x^2=k(x-r_1)(x-r_2)+\ell x+D \quad (1)$$ where $D=\ell s_1$, i.e. $D$ is a multiple of $\ell$.
From equation $(1)$ we can conclude: $$k=31$$ $$\ell = 57+31(r_1+r_2) \quad(2)$$ $$D=2-3(r_1 r_2)\quad(3)$$
But $D$ is a multiple of $\ell$ ($D=\ell s_1$), therefore we can conclude from that fact and from equations $(2)$ and $(3)$ the following: $$2-57s_1=31[r_1r_2+s_1(r_1+r_2)] \quad(4)$$ From equation $(4)$ we conclude that $2-57s_1$ is a multiple of $31$. Thus if $n=r_1 r_2+s_1(r_1+r_2)$ we reached the following equation: $$2=31n+57s_1 \quad(5)$$ A solution of equation $(5)$ is $n=-22$ and $s_1=12$ (Using Euclidean Algorithm).

Now we can solve equation $(4)$.
A solution is $r_1=-10$ and $r_2=49$ (Using factoring).
And replacing the values of $r_1$ and $r_2$ in $(2)$ we get: $$\ell = 1266$$ Therefore $P(x)=2+57x+31x^2$ can be decomposed in this way: $$2+57x+31x^2=31(x+10)(x-49)+1266(x+12)$$ A conclusion that we can draw from that example is:

If $a$ is not a multiple of $gcd(b,c)$, then the polynomial cannot be decomposed in this way: $$a+bx+cx^2=k(x-r_1)(x-r_2)+\ell(x-s_1)$$ since there won't be a solution to the Diophantine equation $(5)$.

-
$2+57x+31x^2=(2-3x+x^2)+(60x+30x^2)$. –  Gerry Myerson Jul 25 '12 at 12:40
It always seems possible to do any particular example, but a proof that it's always possible.... –  Gerry Myerson Jul 25 '12 at 12:59
@Gerry. See my conclusion from the example I gave and try to decompose $4x^2+6x+1$ in that way. –  RicardoCruz Jul 25 '12 at 13:14
$4x^2+6x+1=(5x^2+10x+5)+(-x^2-4x-4)=5(x+1)^2-(x+2)^2$. –  Gerry Myerson Jul 26 '12 at 2:03
@Gerry. As you may have seen it was impossible to decompose $4x^2+6x+1$ in a second degree polynomial and a first degree polynomial, you needed two second degree polynomials. –  RicardoCruz Jul 26 '12 at 17:55