miércoles, 26 de abril de 2017

A play on the interplay 'twixt primes and polynomials

In what follows, we shall denote the set of positive prime numbers by $\mathbf{P}$.

Act I. It is more or less well-known that there does not exist a non-constant polynomial $f \in \mathbb{Z}[x]$ such that $f(n) \in \mathbf{P}$ for every $n \in \mathbb{N}$. This can be proven by reductio ad absurdum: if $f(n) \in \mathbf{P}$ for every $n \in \mathbb{N}$ and $f(1) =: p$, then $p \mid f(1+kp)$ for every $k \in \mathbb{N}$; it follows that at least one of the equations $f(x)=p$ or $f(x)=-p$ has more solutions than $\deg(f)$, Q. E. A. This result is typically attributed to Christian Goldbach: W. Narkiewicz, on page 25 of his "The Development of Prime Number Theory", even mentions that it can be found in a letter from Goldbach to Euler written on September 28th, 1743. Luckily for us, Springer-Verlag published two years ago a translation into English of the correspondence of L. Euler with C. Goldbach edited and commented by F. Lemmermeyer and M. Mattmüller.

Act II. Several years ago, while perusing a very interesting article on primes in arithmetic progressions by M. R. Murty, I learned the notion of prime divisor of a polynomial: if $p \in \mathbf{P}$ and $f \in \mathbb{Z}[x]$, we say that $p$ is a prime divisor of $f$ if $p \mid f(n)$ for some $n \in \mathbb{Z}$. According to Murty, the basic theorem on the set of prime divisors of a non-constant $f \in \mathbb{Z}[x]$ can be traced back (at least) to a 1912 paper of I. Schur. The theorem can be proven emulating the celebrated proof of Eucl. IX-20.

Theorem. If $f$ is a non-constant polynomial of integer coefficients, then its set of prime divisors is infinite.

Proof. If $f(0)=0$, then every $p \in \mathbf{P}$ is a prime divisor of $f$. If $f(0) = c \neq 0$, then $f$ has at least one prime divisor as it can take on the values $\pm 1$ only finitely many times. Given any finite set $\mathcal{P}_{k}:=\{p_{1}, \ldots, p_{k}\}$ of prime divisors of $f$, we are to show that we can always find another prime divisor of $f$ which does not belong to $\mathcal{P}_{k}$. Let $A := p_{1} \cdots p_{k}$ and consider the equality $f(Acx)=cg(x)$ where $g \in \mathbb{Z}[x]$ is a polynomial of the form $1+c_{1}x+c_{2}x^{2}+\cdots$ where every $c_{i}$ is a multiple of $A$. Since $g$ is a non-constant polynomial whose constant term is different from $0$, $g$ has at least one prime divisor $p$. Clearly enough, this prime number $p$ is also prime divisor of $f$ which does not belong to $\mathcal{P}_{k}$. Q.E.D.

Act III. Resorting to the ideas in the previous paragraphs plus Dirichlet's glorious theorem on primes in arithmetic progressions, we are going to determine all the non-constant polynomials $f \in \mathbb{Z}[x]$ such that $f(\mathbf{P}) \subseteq \mathbf{P}$.

- If $f$ is one such polynomial and $f(0)=0$, then $f(x)=xg(x)$ for some some $g \in \mathbb{Z}[x]$. Given that $p \cdot g(p) =f(p) \in \mathbf{P}$ for every $p \in \mathbf{P}$, it follows that $g(p) = \pm 1$ for every $p \in \mathbf{P}$; therefore, in this case we obtain that either $g(x)=1$ and $f(x) =x$ or $g(x)=-1$ and $f(x)=-x$.
- Let us assume now that $f$ is one such polynomial and $f(0)=c \neq 0$. By the above theorem, we may fix a prime divisor $q$ of $f$ which is greater than $|c|$. If $n \in \mathbb{Z}$ is a witness of the fact that $q$ is a prime divisor of $f$, then $q \nmid n$. Thus, if $p_{1} < p_{2} < p_{3} < \ldots$ are all the positive primes in the arithmetic progression whose first term is $n$ and whose common difference is $q$, we have that $f(p_{i}) \equiv f(n) \equiv 0 \pmod{q}$ for every $i \in \mathbb{N}$, which is decidedly absurd because $f$ can assume the values $\pm q$ only finitely many times.

Hence, $f(x)=x$ is the only non-constant polynomial with integer coefficients which sends $\mathbf{P}$ to one of its subsets.

THE END.

2 comentarios:

Octavio dijo...

Wow, bro! I liked this one very much.

José Hdz. Stgo. dijo...

I am very glad you liked it! By the way, I recently left a comment for you in the entry on the Aristippus anecdote.

With warm regards,

J.H.S.