MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Pedantic comment alert: Presumably this is not exactly what you meant: $f(x)=2x-7$ satisfies $f^n(7)$ is prime for all $n$. – Anthony Quas Apr 26 '13 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. – Joe Silverman Apr 26 '13 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 – Włodzimierz Holsztyński May 2 '13 at 18:15
up vote 12 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
thanks, Nilothal, but it looks like it difficult to prove anything useful about this number, so it hardly helps for integer dynamics – DmitryZ Apr 28 '13 at 9:38

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,

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.