# Integer dynamics hitting infinitely many primes

I am wondering if there are any rigorous results telling that some dynamical system hits infinitely many primes (except for the case when orbits are just arithmetic progressions). To make it specific, is there a polynomial $f(x)$ such that its iterations $f^n(x)$ are prime for infinitely many $n$ given that the integer $x$ is fixed. A simple observation here is that if $f(x) = 2x + 1$ then asking if iterations of $f(1)$ contain infinitely many primes is equivalent to the Mersenne primes conjecture.

P. S. This question seems to be related to the Bunyakovsky conjecture, so maybe somebody knows about any partial results in this direction?

• Pedantic comment alert: Presumably this is not exactly what you meant: $f(x)=2x-7$ satisfies $f^n(7)$ is prime for all $n$. Apr 26, 2013 at 1:18
• @Anthony - Actually, in arithmetic dynamics your sequence 7,7,7,... is considered an arithmetic progression, with initial term 7 and common difference 0. This is a convenient convention, for example, for stating the dynamical Mordell-Lang conjecture, which says that $\{n : f^n(x)\in Y\}$ is a finite union of arithmetic progressions. Here $f:X\to X$ is a morphism of a (smooth) projective variety, and $Y\subset X$ is a (smooth) subvariety. Apr 26, 2013 at 2:40
• (I) $f(x):=(x−1)\cdot x+1$, for $f(1):=3$, gives what can be called Euclid numbers $f(1)\ f(2)\ \ldots$. (One can throw in $f(0):=2$, so that $f(n)=f(0)\cdot \ldots\cdot f(n−1)+1$ for every $n=1 2 \ldots$). -o-#-o- (II) $f(x):=(x−2)\cdot x+2$ gives Fermat numbers $f(1)\ f(2)\ \ldots$ for $f(1):=3$ (so that $f(n)=f(1)\cdot \ldots\cdot f(n−1)+2$ for every $n=2 3 \ldots$). -o-#-o- (III) Etc May 2, 2013 at 18:15

I'm fairly certain that nothing along these lines is known.

Until the late 1990's there were no known `elementary' polynomial sparse sequences that contained infinitely many primes(*). In 1998 Friedlander and Iwaniec proved that the sequence of integers of the form $x^2 +y^4$ contains infinity many primes. The number of elements of this sequence less than $N$ is $N^{3/4}$. In 2001, Heath-Brown proved that the sequence of integers of the form $x^3+2y^3$ contain infinitely many primes. The number of elements of this sequence less than $N$ is $N^{2/3}$. This seems the best result in this direction to date. Nothing seems to be known (other than upper bounds from sieve theory) about polynomials in a single variable (other than linear equations / arithmetic progressions, of course).

If there was a polynomial whose iterates contained infinity many primes this would give an exponentially sparse sequence with infinitely many primes. This seems far from anything anyone can prove at present. In particular, there appears to be no polynomial time (in the bit length) constructable sequence of integers which is proven to be prime infinitely often and whose intersection with the first $N$ integers is less than $N^{1/2}$. Indeed such a result would yield new results on the problem of deterministically constructing large primes (see the Polymath 4 project).

On the other hand, there is some remarkable work in which nontrivial estimates have been obtained for the number of prime divisors of sequences obtained by iterates of various quadratic polynomials. See: R. Jones, The density of prime divisors in the arithmetic dynamics of quadratic polynomials. J. Lond. Math. Soc. (2) 78 (2008), no. 2, 523–544

Update: (*) Indeed, I had forgotten about the Piatetski-Shapiro prime number theorem when I wrote this. However, the best exponent on this result is gives a set of density around $N^{.861}$ which is inferior to Heath-Brown's result for the purposes discussed here.

As Mark says, nothing is known about infinitely many primes in dynamical sequences, other than ones that contain an arithmetic progression. An easier, but still useful, question, is that of primitive prime divisors. A prime $p$ is a primitive prime divisor of $f^n(x)$ if $p\mid f^n(x)$ and $p\nmid f^m(x)$ for all $m\lt n$. There's a vast literature on primitive prime divisors in various sorts of sequences. In general, if $\mathcal{A}=(a_n)$ is a sequence of integers, or more generally, rational numbers, the Zsigmondy set of $\mathcal{A}$ is $$\mathcal Z(\mathcal A) = \{ n : \hbox{the numerator of a_n has no primitive prime divisors} \}.$$ Patrick Ingram and I  showed that under suitable hypotheses on $f\in\mathbb{Q}(T)$ and $x,y\in\mathbb{Q}$, the Zsigmondy set $\mathcal{Z}(f^n(x)-y)$ is finite. In addition to some obvious conditions needed to avoid trivial counterexamples, we needed to assume that $y$ is preperiodic for $f$. Recently, Gratton, Nguyen, and Tucker  removed this restriction on $y$, conditional on the $abc$ conjecture.

 Ingram, Patrick; Silverman, Joseph H.; Primitive divisors in arithmetic dynamics. Math. Proc. Cambridge Philos. Soc. 146 (2009), no. 2, 289–302 (MR2475968)

 Chad Gratton, Khoa Nguyen, Thomas J. Tucker, ABC implies primitive prime divisors in arithmetic dynamic, preprint, http://arxiv.org/abs/1208.2989

In 1947, American William . H. Mills proved that there is a real number $A$, greater than 1 but not an integer, such that integer part of

$$A^{3^n}$$

is prime for all $n =1, 2, 3, \ldots$. The numnber $A$ is known as the Mill's constant. Its value is unknown, but if the Riemann hypothesis is true then,

$$A \approx 1.3063778838630806904686144926\ldots$$

 Mills, W. H. (1947) A prime representing function. Bull. Amer. Math. Soc., 53: 604: MR 8, 567.

 [Mill's constant]1

• thanks, Nilothal, but it looks like it difficult to prove anything useful about this number, so it hardly helps for integer dynamics Apr 28, 2013 at 9:38