Polynomial prime

Suppose that $f(x) = g(x)h(x)$ where $g(x),h(x)$ are nonconstant polynomials with integer coefficients, and suppose that $|f(x|$ is prime for each of ten distinct integer values $n_1,n_2,\ldots,n_{10}$ . Then $|g(n_j)|\times|h(n_j)|$ is prime for $1 \le j \le n$ . Thus, for each $1 \le j \le 10$ , either $g(n_j) = \pm1$ or $h(n_j) = \pm 1$ . Now

• If $p(x)$ is a polynomial with integer coefficients with three distinct integer zeros, then there exists at most one integer value $n$ where $p(n)=2$ .

• If $p(x)$ is a polynomial with integer coefficients with four distinct integer zeros, then there exists no value $n$ for which $p(n) = 2$ .

The proofs of these statements is easy. In the first case, let the zeros be $a<b<c$ . Then $p(x) = (x-a)(x-b)(x-c)q(x)$ for some polynomial $q(x)$ with integer coefficients, and $|(d-a)(d-b)(d-c)| \ge 2$ for any $d \neq a,b,c$ . Moreover $|(d-a)(d-b)(d-c)| = 2$ only when either $a,d,b,c$ or $a,b,d,c$ are consecutive integers. Thus, for any collection of $a,b,c$ , there is at most one possible value of $d$ for which $p(d)=2$ .

In the second case, let the zeros of $p(x)$ be $a<b<c<d$ . Then $p(x) = (x-a)(x-b)(x-c)(x-d)q(x)$ for some polynomial $q(x)$ with integer coefficients. Since $(e-a)(e-b)(e-c)(e-d)$ (with $e$ an integer) is either zero or greater than $2$ in modulus, we see that $p(e)$ cannot be $2$ for any integer $e$ .

Suppose that $|g(n_j)|=1$ a total of $k$ times, and $|h(n_j)|=1$ a total of $10-k$ times. By labelling $g(x)$ and $h(x)$ suitably, we can assume that $0 \le k \le 5$ . Then $|h(x)|$ takes the value $1$ at least five times. Thus we can find $\varepsilon \in\{-1,1\}$ such that $h(x)$ takes the value $\varepsilon$ at least three times. By the above results, it follows that $h(x)$ takes the value $-\varepsilon$ at most once. Thus, in fact, $h(x)$ takes the value $\varepsilon$ at least four times, and hence cannot take the value $-\varepsilon$ at all. Thus $h(x)$ takes the value $\varepsilon$ $10-k$ times, and so $h(x)-\varepsilon$ has $10-k$ zeros, and hence has degree at least $10-k$ . The minimum degree of $h(x)$ is $10-k$ .

1. If $k=5$ then, just as in the above argument about $h(x)$ , $g(x)$ has degree at least $5$ . Thus the smallest degree of $f(x)=g(x)h(x)$ is $5+5=10$ .

2. Suppose that $k=4$ . The polynomial $g(x)=x(x-3)+1=x^2-3x+1$ takes the value $1$ at $x=0,3$ and the value $-1$ at $x=1,2$ . It is not possible for a linear polynomial to hit $1$ or $-1$ a total of four times. Thus the smallest degree of $g(x)$ is two, and so the smallest degree of $f(x)$ is $2+6=8$ .

3. Suppose that $k=3$ . Then there exists $\varepsilon \in \{-1,1\}$ such that $g(x)$ takes the value $\varepsilon$ at least twice, and hence $g(x)-\varepsilon$ has at least two zeros, and hence $g(x)$ has degree at least two. Thus the smallest degree of $f(x)$ is $2+7=9$ .

4. Suppose that $k\le2$ . Then, since $g(x)$ is non constant, $g(x)$ has degree at least one. Thus the smallest degree of $f(x)$ is $1+10-k=11-k \ge 9$ .

Our best bet, therefore, is to choose $g(x) = x^2 - 3x + 1$ and hunt for a suitable degree $6$ polynomial $h(x)$ . It happens that $g(x)$ is helpful, since it achieves a lot of primes. In particular $g(-3)=g(6)=19$ , $g(-2)=g(5)=11$ , $g(-1)=g(4)=5$ are all prime. If we consider $h(x) = 1 + (x+3)(x+2)(x+1)(x-4)(x-5)(x-6)$ then $h(x)$ takes the value $1$ at $-3,-2,-1,4,5,6$ , and moreover $h(0) = h(3) = -719$ , $h(1) = h(2) = -1439$ are all negative primes. Thus we deduce that $|f(x)|$ is prime for $x=-3,-2,-1,0,1,2,3,4,5,6$ , and we are done. Thus the smallest possible degree of $f(x)$ is $8$ .