Decomposing polynomials with integer coefficients

Solution 1:

(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.

Solution 2:

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