Integer dynamics hitting infinitely many primes

Question

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?

Answer 1

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.

Answer 2

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 [1] 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 [2] removed this restriction on $y$, conditional on the $abc$ conjecture.

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

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

Answer 3

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 $$

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

[2] [Mill's constant]1