algebra-precalculuspolynomials
Through definitions, theorems and my professor the following is true:
When expression of the form $(x-r)(x-s)$ are multiplied out a quadratic polynomial is obtained.
For example $(x-2)(x+7)$ = $x^2 + 5x -14$
But I cannot explain how $x^2 – 1253x + 255$ can’t be written as a product of two polynomials with integer coefficients.
(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.
It's true in general. It suffices to show that $PQ$ has odd degree. Suppose to the contrary that there exist some $P,Q\in\mathbb F_2[x]$ subject to the constraints outlined in the OP for which $PQ=1+x+\cdots+x^{2n}=\frac{x^{2n+1}-1}{x-1}$. Observe by Frobenius that $\sum a_kx^{2k}=\left(\sum a_kx^k\right)^2$ in $\mathbb F_2[x]$. We shall prove that $1+x+\cdots+x^{2n}$ is squarefree; this clearly implies the result. Indeed, \begin{align*}\gcd\left(1+x+\cdots+x^{2n},\left(1+x+\cdots+x^{2n}\right)'\right)&=\gcd\left(1+x+\cdots+x^{2n},1+x^2+\cdots+x^{2n-2}\right)\\&=\gcd\left(1+x+\cdots+x^{2n},\left(1+x+\cdots+x^{n-1}\right)^2\right)\\&=\gcd\left(\tfrac{x^{2n+1}-1}{x-1},\left(\tfrac{x^{n}-1}{x-1}\right)^2\right)=1\end{align*} Where the last equality follows from the identity $\gcd(x^m-1,x^n-1)=x^{\gcd(m,n)}-1$ $\blacksquare$
Best Answer
Suppose there are integers $r,s$ such that $rs=255, \ r+s=1253$.
From $rs=255$ we get that both $r$ and $s$ are odd and from $r+s=1253$ a contradiction.