Let $n$ be a natural number and $f_1$, $f_2$, ..., $f_n$ be polynomials with integers coeffcients. Show that there exists a polynomial $g(x)$ which can be factored (with at least two terms of degree at least $1$) over the integers such that $f_i(x)+g(x)$ cannot be factored (with at least two terms of degree at least $1$) over the integers for every $i$.
Problem
Source: MOP 2005 Homework - Black Group #22
Tags: algebra, polynomial, parameterization, modular arithmetic, function, number theory unsolved, number theory
27.05.2014 05:41
The basic idea here will be to apply Eisenstein; for each $f_i$ we can choose a prime $p_i$ and determine the coefficients of $g$ modulo $p_i^2$ required for Eisenstein w.r.t. $p_i$ to take effect. Afterwards, we'll doctor our answer somewhat to ensure $g$ is not itself irreducible and that there are no technical issues in the proof (for the most part, it will be enough to require that all parameters are sufficiently large). We'll attempt to pick a $g$ of the form \[g(x) = Cx^N + g_dx^d + \dots g_0\] where $d$ is the maximum degree occurring among the $f_i$ and $C, N$ are parameters to be chosen later. The only condition on $C$ will be that $p_i \nmid C$ for any $i$. Now for each $i$, we pick a (new) prime $p_i$ and choose $\{g_i\}$ modulo $p_i^2$ so that Eisenstein applies to $f_i(x) + g(x)$ for the prime $p_i$. Explicitly, we choose $g_j \equiv -{f_i}_{j} \pmod{p_i^2}$ for $1 \le j \le d$ and $g_0 \equiv -{f_{i}}_{j} + p_i \pmod{p_i^2}$. (In fact, this is more than what is required for Eisenstein, but it's more convenient to work modulo $p_i^2$ uniformly). Doing this for primes $p_1, p_2, \dots, p_n$ gives us a family of candidate functions $g$ with coefficients determined only modulo $p_1^2p_2^2\dots p_n^2$. For now let $g_i$ stand for a fixed, arbitrary member of its congruence class. We must now ensure $g$ is not itself irreducible. The simplest way to do this would be to find a $g$ with an integer root. Since we're free to adjust $g_0$ by any multiple of $p_1^2p_2^2 \dots p_n^2$ it's enough to find $g$ with an integer root modulo $p_1^2, p_2^2, \dots, p_n^2$. Fix $i$. If there exists an integer input $z$ such that \[g_dz^d + \dots + g_0 \not \equiv 0 \pmod{p_i}\] and $p_i \nmid z$, then by suitable choice of $C$ modulo $p_i^2$, $g$ has $z$ as a root modulo $p_i^2$. If the polynomial $g_dx^d + \dots + g_0$ is identically zero modulo $p_i$ either the $g_j$ are all zero modulo $p_i$, or else $d \ge p_i - 1$. Both these problems can be solved by requiring that $p_i$ be sufficiently large - first larger in magnitude than any of the coefficients of the $f_i$, next larger than $d + 1$. We can do this for every $1 \le i \le n$, at which point Chinese Remainder Theorem furnishes an integer root modulo $p_1^2p_2^2 \dots p_n^2$, and $g$ has an integer root, as desired.
24.11.2014 14:33
Let $a_{i,k}$ be the coefficient of $x^k$ in $f_i$.Suppose that $d_i$ be the degree of the polynomial $f_i$ and $d=\text{max}\{d_i\}$.Take $d$ variables $b_1,b_2,\cdots,b_d$ and let $p_1,p_2,\cdots,p_n$ be $n$ distinct primes.Then for each $i$ solve the congruences $a_{i,k} \equiv -b_{k}\pmod{p_i} \forall k \in [d_{i}-1,2]$ and $b_{0} \equiv -a_{i,0} \pmod{p_i}$ but $b_{0} \not\equiv -a_{i,0} \pmod{{p_i}^2}$.Also consider $b_{d_i}$ such that ${p_i} \nmid a_{i,d_i}+b_{d_i}$.Then for each $k$ we obtain a solution of $b_k$ modulo $p_1p_2 \cdots p_n$.We claim that $g(x)=\sum_{i=0}^{d}{{b_i}x^i}$ satisfies our conditions. But this is due to our construction.Consider $f_i+g(x)$ for any $i$.The coefficient of $x^{d_i}$ is $a_{i,d_i}+b_{d_i}$ which is not divisible by $p_i$.The rest all coefficients are divisible by $p_i$ and the constant term $a_{i,0}+b_{0}$ is not divisible by ${p_i}^2$.So by Eisenstein's irreducibility criterion $g(x)$ satisfies the problem conditions.Note that once we have found such a $g(x)$,we can find infinitely many of them.