# Polynomial with integer coefficient evaluates to -1,1 in degree + 1 values

Does there exist a polynomial $P \in \mathbb{Z}[X]$ and pairwise distinct $a_1, \dots ,a_{d+1} \in \mathbb{Z}$, with $d > \deg(P)$, such that $|P(a_i)| = 1$ for all $i \in \{1, \dots, d+1\}$?

I am pretty sure that such a polynomial cannot exist. But this is just an intuition. Any ideas how to prove that this is a contradiction?

-
Couldn't you take $P(X)=X$, $a_1=1$ and $a_2=-1$? – Cam McLeman Jun 5 '12 at 14:59
Yes of course ... – joachim Jun 5 '12 at 15:05
Maybe you want to insist on degree greater than 1? And maybe irreducible. – Cam McLeman Jun 5 '12 at 15:08
$d$ is strictly bigger than the degree. I think this is stronger. – joachim Jun 5 '12 at 15:11
Well, it's definitely stronger. Robert Israel's answer addresses this situation as well. – Cam McLeman Jun 5 '12 at 15:12

If $B = \{i: P(a_i) = -1\}$, then $P(z)+1$ is divisible by $Q(z) = \prod_{i \in B} (z - a_i)$. We may assume $\text{card}(B) \ge (d+1)/2$ (otherwise replace $P$ by $-P$. Now if $i \in \{1,\ldots,d+1\} \backslash B$, $P(a_i) = 1$ so $Q(a_i)$ divides $2$, so $Q(a_i) \in \{-2,-1,1,2\}$. So each $a_i - a_j$ for $j \in B$ is in $\{-2,-1,1,2\}$, and at most one can be $\pm 2$. In particular, $\text{card}(B) \le 3$. Moreover, if $\text{card}(B) = 3$ there is at most one possible value for $a_i$, namely $0$. This reduces us to a small number of possible cases, which can be checked individually.
EDIT: One such case is $P(x) = 1 + (x+1)(x-2)$, where $P(x) = 1,-1,-1,1$ for $x=-1,0,1,2$, do $d = 3$ and $\deg P = 2$.