Reductio Ad Absurdum

As $f(x)$ is reducible, let $f(x)=g(x)h(x)$ where $g(x),h(x)$ are non-constant polynomials with integer coefficients and $d_g,d_h$ are the degrees of $g,h$ respectively. Note that $d_g+d_h=4$ as their product is a quartic polynomial.

Clearly, $f(x),g(x),h(x) \in \mathbb{Z}$ for all integers $x$ . Note that the only way to express a prime number $p$ as a product of 2 positive integers is $1 \times p$ since these are it's only factors. Therefore, if $|f(x)|=|g(x)||h(x)|$ is prime, either $|g(x)|=1,|h(x)|=p$ or $|g(x)|=p,|h(x)|=1$ .

Therefore, if $|f(x)|$ is prime then either $g(x)=1, g(x)=-1, h(x)=1$ or $h(x)=-1$ . Note that $g(x)=1$ has at most $d_g$ roots since $g(x)-1$ is a polynomial of degree $d_g$ so $g(x)-1=0$ has at most $d_g$ roots. Similarly, $g(x)=-1,h(x)=1,h(x)=-1$ have at most $d_g,d_h,d_h$ roots each respectively.

Therefore, the largest possible number of values is attained when all the roots above are distinct and all integral, giving us a total of $d_g+d_g+d_h+d_h = 2 \times 4 = 8$ possible values.

To show that this is possible, consider the quartic polynomial $f(x) = x^4 - 15x^2 + 25$ . Substituting the 8 values $x = \pm 1, \pm 2, \pm 3, \pm 4$ gives us $|f(x)| = 11,19, 29,41$ respectively which are all primes thus showing that 8 is the maximum.

Let $f(x)=g(x)h(x)$ . $|f(x)|$ is prime iif $|g(x)|=1$ and $|h(x)|$ is prime or vice versa. If degree of g is three, $|g(x)|=1$ for max 6 distinct integers $n_i$ , $|h(x)|=1$ for max 2 distinct integer $m_j$ . If $|g(m_j)|$ is ever prime, $g(n_i)|$ is ever prime, $n_i$ and $m_j$ are distinct, then f is prime for all 6+2 points. If degree of f and g is 2, there are max 4 integer such that $|g(x)|=1$ and $|h(x)|$ is prime and 4 such that $|h(x)|=1$ and $|g(x)|$ is prime. Again, max 4+4 solutions. For $x=\{-1,0,1,2,3,4,5,6\}$ , $g(x)=x^2-x-1=\{1,-1,-1,1,5,11,19,29\}$ . Look at the same parabola, translated 4 units to the right: $h(x)=(x-4)^2-(x-4)-1=\{29,19,11,5,1,-1,-1,1\}$ for the same values of x. Therefore, (f(x)=g(x)h(x)) is ever prime in $\{-1,\ldots,6\}$ .

first, let's say f(x) = p(x)q(x), where f and g are non-constant polynomials of degree less than 4. consider the case in which p has degree 3 and q has degree 1. for |f(x)| to be prime, then either p or q must be +/- 1, while the other must be +/- of a prime number. if we look at p(x), which has degree 3, the maximum number of solution for |p(x)| = 1 is 6, because a third degree polynomial can only meet the line y = 1 (or y = -1) at most 3 times. it is actually possible for this to happen, by interpolating the points: (0,1),(1,-1),(2,1),(3,-1),(4,1),(5,-1). similarly, |q(x)| = 1 has at most 2 solutions, using similar arguments. therefore the case in which p has degree 3 and q has degree 1 can yield at most 8 solutions. the only other possible case would be p and q has degree 2, and by similar arguments, we can say that this would yield at most 8 solutions too. then we can easily construct such polynomials p and q, and show that 8 is the answer.

The upper bound is simple: if $f(x)$ is reducible, then by Gauss's lemma there are non-constant integer polynomials $g$ and $h$ such that $f(x) = g(x) h(x)$ . Since $| f(x_i) | = |g(x_i)|\cdot |h(x_i)|$ is prime and $g(x_i), h(x_i)$ are integers, exactly one of $|g(x_i)|, |h(x_i)|$ is $1$ for each $x_i$ . But there are at most $\deg g$ values of $x$ for which $g(x) = 1$ , and at most $\deg g$ values of $x$ for which $g(x) = -1$ , so only $2 \deg g$ distinct $x$ satisfying $|g(x)| = 1$ . Applying the same argument to $h$ we see there are at most $2 (\deg g + \deg h) = 8$ distinct $x$ where $| f(x) |$ is prime.

To show this is feasible, note that the polynomial $p(x) = x^2 + x - 1$ takes the values $1, -1, -1, 1$ at $x = -2, -1, 0, 1$ , respectively. Our hope is to find four consecutive prime values of $p(x)$ , and indeed $p(2) = 3, p(3) = 11, p(4) = 19, p(5) = 29$ are all prime. Therefore we may take $f(x) = p(x) p(3-x)$ . By the previous calculations, $|f(x)|$ is prime for $x = -2, -1, 0, 1$ , and since $f(x) = f(3-x)$ the same is true for $x = 2, 3, 4, 5$ .

So, how lucky were we? Schinzel's Hypothesis H conjectures that an finite set of polynomials will be simultaneously prime infinitely often, provided there are no obvious obstructions (such as one is reducible, or their product is always divisible by a certain prime). In our case $p(x), p(x+1), p(x+2), p(x+3)$ are irreducible, and the value of their product at $x=-2$ is $1$ , so there is no local obstruction. Therefore we'd expect to eventually find four consecutive prime values, even though such instances get rarer and rarer (conjecturally, spaced apart by $O(\log^4 x)$ on average).

Since $f(x)$ is reducible, let $f(x)=P(x)Q(x)$ where $P$ and $Q$ are non-constant polynomials with integer coefficients satisfy $deg P+deg Q=deg f=4$ . Wlog, ${deg P}\leq{deg Q}$ . $P(x)$ and $Q(x)$ are integers for all integer $x$ . If both $P(x)$ and $Q(x)$ are not equal to $\pm1$ , then $|f(x)|$ is not a prime. When $|f(x)|$ is a prime, exactly one of $P(x)$ or $Q(x)$ equals to $\pm1$ (and the other is a prime). Divide into two cases: Case 1 : $deg P=1$ and $deg Q=3$ . When $P(x)=1$ , $P(x)-1=0$ , let $R(x)=P(x)-1$ . Since $deg R=1$ , there exist at most one (integer) value of $x$ satisfy $R(x)=0$ and $P(x)=1$ . Similarly, there exist at most one (integer) value of $x$ satisfy $P(x)=-1$ , at most three (integer) values of $x$ satisfy $Q(x)=1$ and at most three (integer) values of $x$ satisfy $Q(x)=-1$ . Therefore, there exist at most 8 (integer) values of $x$ satisfy $P(x)$ or $Q(x)$ equals to $\pm1$ . In other words, there exist at most 8 (integer) values of $x$ satisfy $|f(x)|$ is prime for $deg P=1$ and $deg Q=3$ . Case 2 : $deg P=deg Q=2$ . Using the same method in Case 1, there exist at most two (integer) values of $x$ satisfy each $P(x)=1, P(x)=-1, Q(x)=1, Q(x)=-1$ . Therefore, there exist at most 8 (integer) values of $x$ satisfy $|f(x)|$ is prime for $deg P=deg Q=2$ . For both cases, there exist at most 8 (distinct integer) values of $x$ that satisfy $|f(x)|$ is a prime. Take $f(x)=(x^2-3x+1)(x^2-11x+29)$ and $(x_{1}, x_{2}, x_{3}, x_{4}, x_{5},x_{6},x_{7},x_{8})=(0,1,2,3,4,5,6,7)$ . This shows that the largest possible number (8) is achievable. QED

We know that $f(x)$ is reducible, so $f(x)=g(x)h(x)$ for some $g,h \in \mathbb{Z}[x]$ , where without loss of generality, $\deg g \le \deg h$ . Since $\deg f = 4 = \deg g + \deg h$ then $\deg g \in \{ 1, 2\}$ . We work on both cases one by one.

Case 1. $f(x)=(ax^2+bx+c)(px^2+qx+r)$ . If $|f(s)|=|as^2+bs+c||ps^2+qs+s|$ is a prime number, then it can't be the case that $|as^2+bs+c|>1,|ps^2+qs+r|>1$ and none of them can be $0$ and therefore, for each $i$ , it's either $|ax_i^2+bx_i+c|=1$ or $|px_i^2+qx_i+r|=1$ $. But, the equation $|ax^2+bx+c|=1$ may only have at most $4$ solutions. Indeed, one can write $(ax^2+bx+c)^2-1=0$ which is equivalent in finding the roots of degree-four polynomials. Similarly, $|px^2+qx+r|=1$ also may only have $4$ solutions. Thus, we must have $n \le 8$ .

Case 2. $f(x)=(ax+b)(px^3+qx^2+rx+s)$ . Similar with above arguments, we must have either $|ax_i+b|=1$ or $|px_i^3+qx_i^3+rx_i+s|=1$ for each $i$ . But $|ax_i+b|=1$ can only have at most $2$ solutions and $|px^3+qx^2+rx+s|=1$ can only have $6$ solutions, similarly we have $n \le 8$ .

Now, we only need to show that there are such integers and polynomials for $n=8$ . Consider polynomial $f(x)=(x^2-3x+1)(x^2+5x+5)$ , we can verify that for $x=-4,-3,-2,-1,0,1,2,3$ , $|f(x)|$ is a prime number.

Let the polynomial be $P(x)$ , and we have $P(x)=Q(x)\cdot R(x)$ , where $Q, R$ are polynomials with integer coefficients. For $P(x_i)=p,$ a prime we have $(Q(x), R(x))=(1,p), (p,1), (-1,-p), (-p, -1)$ only. Alternatively, we want to maximize the solutions for $|Q(x)|=1$ and $|R(x)|=1$ . We know that the maximum solutions for $Q(x)=1$ is the degree of $Q$ . Similar for $Q(x)=-1$ . Also similar for $R$ . Add these up we have twice the sum of degrees of $Q$ and $R$ , which is $4\times 2=8$ . It is clear such a polynomial $P$ is constructable. Therefore the answer is $8$ .

Solution 1: We will prove that the answer is $8.$ To show that this is possible, consider the polynomial $g(x)=x^2-x-1.$ Note that for $x=-1,0,1,2$ $|g(x)=1$ and for $x=3,4,5,6$ $|g(x)|$ is a prime. Therefore, $f(x)=g(x)g(5-x)$ satisfies the condition of the problem with $n=-1,0,...,6.$

We will now prove that $8$ is the largest possible number of $n.$ Because $f$ is reducible of degree four, either it is a product of two quadratic polynomials, or a linear and a cubic polynomial.

Case 1. Suppose $f(x)=g(x)h(x),$ $deg(g)=deg(h)=2.$ For each $n$ when $|f(n)|$ is prime, either $g(n)=\pm 1$ or $h(n)=\pm 1$ . Note that $g(x)-1,$ $h(x)-1,$ $g(x)+1,$ $h(x)+1$ are not constants, and each has no more than $2$ roots. This means that the total number of possible values of $n$ is at most $8.$

Case 2. Suppose $f(x)=g(x)h(x),$ where $deg(g)=1,$ $deg(h)=3.$ Similar to the previous case, every $n$ for which $|f(x)|$ is a prime is a root of one of the polynomials $g(x)-1,$ $h(x)-1,$ $g(x)+1,$ $h(x)+1.$ They have degrees $1,3,1,3,$ so the total number of roots is at most $8.$

Solution 2: First of all, if $g(x)=x^2-x-1$ and $h(x)=g(x-4)$ , then for $f(x)=g(x)h(x)$ the number $|f(n)|$ is prime for $n=-1,0,1,2,3,4,5,6$ .

Suppose for some $f(x)=g(x)h(x)$ the number $|f(n)|$ is prime for at least 9 different $n$ . Then either $g$ or $h$ takes values $1$ and $-1$ at least five times. Without loss of generality, assume that this is $g$ . If at least four of these values of $g$ are the same, then $g$ , having degree at most three, is a constant, which is impossible by assumption. If three of the values are $1$ , and two are $-1$ , or the other way around, then note that for all integer $n$ and $m$ the number $n-m$ divides $g(n)-g(m)$ . Therefore, all inputs where $g$ is $1$ are within $2$ from the inputs where $g$ is $-1.$ A simple case-by-case analysis shows that this is impossible.

Therefore, the answer is $8.$