# Polynomial mapping primes to primes

Consider a non constant polynomial $P\in\mathbb{Z}[X]$ sending prime numbers to prime numbers. I encountered on the web two different proofs that $P$ is the identity polynomial, one on mathoverflow here and another one (somehow stated in more elementary words) there. The point is : both proof use the Dirichlet progression Theorem and I am wondering if there is any way to prove this fact without the use of such a deep result. As a matter a fact, it seems that the second proof only uses that

There exists only a finite number of pair of distinct primes $(p,q)$ such that $p +\mathbb{N} q$ contains a finite number of primes.

Using the Dirichlet progression Theorem, the finite number of the previous statement is zero, of course. But is there any (if possible elementary) argument to prove the above result ?

Thanks for any help.

Edit : I did not manage to find any more elementary proof to characterize those integers polynomials sending primes to primes. However (for what it worth) I give below an elementary proof of a different (related) result. It is possible that a simpler proof exists, would be happy to read it. Denote by $\mathscr{P}$ the set of all prime numbers.

If $P\in\mathbb{Z}[X]$ satisfies $P(\mathscr{P}) = \mathscr{P}$, then $P(X)=\pm X$.

The case $\deg(P)=1$ is easily handled, so that we just have to prove that $\deg(P)>1$ is impossible. Note that if $P(\mathscr{P}) = \mathscr{P}$, then for all $n\in\mathbb{N}^*$ we have also $P_n(\mathscr{P}) = \mathscr{P}$, where $P_n = P\circ \cdots \circ P$ is the $n$-th iterate of $P$. In particular, for al $(p,n)\in\mathscr{P}\times\mathbb{N}$ there exists $q_n\in\mathscr{P}$ such that $P_n(q_n) = p$. Since $\deg(P_n)>\deg(P)>1$ the (discrete) sequence $(q_n)_n$ is bounded, thus taking a certain value $q_p\in\mathscr{P}$ infinitely many times, i.e. the equation $P_n(q_p)=p$ holds for an infinity of natural integers. If $(p_k)_k$ is an enumeration of $\mathscr{P}$, one can thus produce a diagonal extraction $\varphi:\mathbb{N}\rightarrow \mathbb{N}$ such that $P_{\varphi(n)}(q_p)=p$ holds for all $(p,n)\in\mathscr{P}\times\mathbb{N}$. But this means that $P_{\varphi(n)}$ and $P_{\varphi(n+1)}$ take the same value on an infinite set (since $p\mapsto q_p$ is obviously injective) : the sequence $P_{\varphi(n)}$ is constant. This contradicts $\deg(P)>1\Rightarrow\deg(P_{n+1})>\deg(P_n)$.

As for the general result, this means that we "just" need to prove that such polynomials are onto ... I also tried to used the iterated polynomials but did not succeed.

• Why do you think there should be a more elementary proof? The problem of prime values of polynomials is very hard; for instance, we don't even know if $x^2 + 1$ takes on infinitely many primes... – Stanley Yao Xiao Apr 19 '17 at 18:26
• Because the poster is asking about a polynomial map which is stable on the set of primes. One can show that such a map is eventually order preserving, must either be the identity or have a nonzero constant coefficient as a polynomial, must have iterates which have the same property, and which for sufficiently large primes p have iterates which mod p look like constant maps. This is a lot to ask of most polynomials. I think some distance can be covered by elementary arguments substituting for analytic number theory. Gerhard "Thinking Of Combinatorial Methods Presently" Paseman, 2017.04.19. – Gerhard Paseman Apr 19 '17 at 18:49
• this is rather funny, but assuming such a polynomial exists, one can deduce some simple cases of Dirichlet's theorem. It goes roughly like this: first show that $P(0)=\pm1$, and then observe that this means that $P^{(k)}(0)=\pm1$ as well for the $k$-th iteration of $P$ (with the same sign for each $k$). Then $P^{(k)}(p) - P^{(k)}(0)$ is divisible by $p$, and unpacking this we get Dirichlet for progressions with offset $\pm1$ and difference a large enough prime. – amakelov Apr 24 '17 at 4:30
• @amakelov The cases of Dirichlet's theorem on APs you mention in your comment do have an elementary proof: Given $n \in \mathbf N^+$, the infinitude of the primes of the form $nk+1$ is a rather straightforward consequence of Zsigmondy's theorem on primitive divisors (en.wikipedia.org/wiki/Zsigmondy%27s_theorem), while the infinitude of the primes of the form $nk-1$ is a (more complicate) consequence of certain properties of Chebyshev polynomials, though I couldn't trace back a reference for this result (can anyone?). – Salvo Tringali Apr 27 '17 at 9:03
• @amakelov As far as I can say, the (elementary) proof of the case $nk-1$ I'm alluding to in my previous comment has nothing to do with cyclotomic polynomials: For one thing, that case is never mentioned in S. Gueron & R. Tessler's Infinitely Many Primes in Arithmetic Progressions: The Cyclotomic Polynomial Method [Math. Gaz. 86 (Mar., 2002), No. 505, 110-114], which is entirely devoted, as the title suggests, to the cyclotomic method. – Salvo Tringali Apr 27 '17 at 9:12