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.

martes, 18 de abril de 2017

Nunca hubo milagro

NUNCA HUBO MILAGRO

Banach y Tarski se encontraban gesticulando y argumentando, en el mismo cubículo, frente a un inmenso pizarrón verde, cuando demostraban el teorema que sería conocido a la postre como la Paradoja de Banach-Tarski: dada una bola sólida en $\mathbb{R}^{3}$, existe una descomposición de esta en un número finito de subconjuntos disjuntos que se pueden juntar otramente para producir dos copias idénticas a la bola original. Justo cuando terminaron la prueba, ambos callaron y se miraron muy contentos. Tarski hizo una pequeña aspiración y retuvo el aire un instante hasta que finalmente, abstraído, le dijo a Banach: "Ahora sabemos cómo fue que Cristo multiplicó los peces y el pan".

Autor: Enrique Ruiz.

Postdata. Leí este cuento por vez primera en 2016: no obstante, debo de confesar que estuve aguardando su aparición desde aproximadamente el primer semestre de 2004 pues fue más o menos por aquel tiempo que el Prof. Vulfrano T. me comentó que la multiplicación de los panes y los peces se podía conectar con el Axioma de Elección.