14
$\begingroup$

It is well known that no nonconstant polynomial $f\in \mathbb{Z}[x]$ can assume only prime values at integer arguments. Indeed, if $a\in \mathbb{Z}$ is so large that $|f(a)|>1$, and if $p$ is a prime factor of $f(a)$, then all values of $f(a+pf(x))$ are divisible by $p$.

Question: Can a sequence of the form $f(a),f(f(a)),\ldots$ (for some fixed $a\in \mathbb{Z}$) take on only prime values and tend to infinity?

If $f$ is linear, then the answer to the question is no. To prove this, assume on the contrary that $f^n(a)$ tends to infinity and takes only prime values. Choose $n$ so large that $p:=|f^n(a)|$ is a prime greater than any coefficient of $f$. Then $f$ is a permutation polynomial mod $p$, therefore $f^m(p)$ is divisible by $p$ for infinitely many $m$, a contradiction.

If $f$ is not linear, and if the sequence in question consists only of primes, then (as Dietrich Burde pointed out) $f$ would be a non-linear polynomial taking infinitely many prime values, something that is not known to exist.

On the other hand, if the sequence $f(a),f(f(a)),\ldots$ can never take only prime values (which is my guess) then maybe the problem has a simple solution. Does anyone have any ideas or references?

This is an expanded form of a question posted on Math SE here.

Improve this question
$\endgroup$
3
  • 13
    $\begingroup$ Note that the Fermat numbers $2^{2^n}+1$ are of this form (with $f(a) = (a-1)^2 + 1$), and it is still not proven (though almost certainly true) that there are infinitely many composite Fermat numbers. So this problem is likely beyond the reach of current technology. $\endgroup$
    – Terry Tao
    Commented Dec 23, 2013 at 18:20
  • $\begingroup$ On the other hand, with results of Zhang and improvements, it is possible that there is a (likely nonperiodic) sequence of polynomials p_i such that p_1(a), p_2(p_1(a)), ... are all prime, with p_i coming from {g(x), x+c} for c a small even number. (Posted before seeing Terry Tao's comment.) $\endgroup$
    – The Masked Avenger
    Commented Dec 23, 2013 at 18:27
  • $\begingroup$ @Terry Tao: Thanks for pointing out this connection. I wonder if there are any footholds in the study of orbits of polynomials mod $p$ as $p$ varies? $\endgroup$
    – Sidney Raffer
    Commented Dec 24, 2013 at 2:53

2 Answers 2

Reset to default
4
$\begingroup$

Let $d=\deg(f)\ge2$. Since the height of $f^n(\alpha)$ grows like $C^{d^n}$ with $C>1$ (unless the orbit is finite), one would expect the sequence $f^n(\alpha)$ to contain only finitely many primes on probabilistic grounds. So people study other questions. For example, how large is the set of primes that divides at least one term in the sequence? See [1]. Or as joro indicates, one might look at the orbit behavior modulo $p$ for varying $p$; see for example [2] or [3]. Or one might ask how many terms in the sequence have a primitive prime divisor, that is, a prime dividing $f^n(\alpha)$ that does not divide $f^m(\alpha)$ for all $m<n$; see for example [4] and [5].

[1] Hamblenm Spencer and Jones, Rafe and Madhu, Kalyani, The density of primes in orbits of $z^d + c$, 2013, arXiv:1303.6513.

[2] Akbary, Amir and Ghioca, Dragos, Periods of orbits modulo primes, J. Number Theory 129 (2009), 2831-2842.

[3] Silverman, Joseph H., Variation of periods modulo $p$ in arithmetic dynamics, New York J. Math. 14 (2008), 601--616.

[4] Ingram, Patrick and Silverman, Joseph H., Primitive divisors in arithmetic dynamics, Math. Proc. Cambridge Philos. Soc. 146 (2009), 289-302.

[5] Gratton, Chad and Nguyen, Khoa and Tucker, Thomas J., ABC implies primitive prime divisors in arithmetic dynamics, 2012, arXiv:1208.2989.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Joe, Thank you for explaining the lay of the land. $\endgroup$
    – Sidney Raffer
    Commented Dec 24, 2013 at 19:53
  • $\begingroup$ Interesting. Probabilistic grounds might be misleading in my opinion. Assuming Schinzel's hypothesis H is applicable for this (it might be), it implies arbitrary large $n$ with all iterates being prime. Another argument: there is a constant A such that floor(A^3^n) is prime for all $n \ge 1$. $\endgroup$
    – joro
    Commented Dec 25, 2013 at 9:07
  • $\begingroup$ @joro I don't see the applicability of Schinzel. Probabilisitically, if $F(x)\in\mathbb{Z}[x]$ and if there is no a priori reason why $F(n)$ should always be composite, one would expect infinitely many prime values of $|F(n)|$, since $\sum 1/\log|F(n)|$ diverges. On the other hand, $\sum 1/\log|f^n(\alpha)|$ converges. As for your second point, the constant $A$ is "weird", in the sense it has to be carefully constructed. The values of $f^n(\alpha)$ feel much more random (at least to me). $\endgroup$
    – Joe Silverman
    Commented Dec 25, 2013 at 13:18
  • $\begingroup$ I agree that your arguments are plausible. They apply to all doubly exponential sequences and in some sense the "weird" constant A is a counterexample. As for Schinzel H. Take $f=(x-1)^2+1$. Fermat numbers are f^n(3). Take the set {f(x),f(f(x)) ... f^n(x)} for $n$ arbitrary large. Schinzel H is applicable if all polynomials are irreducible (otherwise we get infinitely many Fermat composites). So Schinzel H implies iterates prime infinitely often up to $n$ for arbitrary large $n$. $\endgroup$
    – joro
    Commented Dec 26, 2013 at 7:37
  • $\begingroup$ @joro We seem to be talking about different problems (and mine is the one that the OP posed). You're saying that for a fixed (but arbitrarily large) $n$, Schinzel (might) imply that there exist infinitely many $x$ such that all of $f(x),\ldots,f^n(x)$ are prime. That is correct. I'm saying that there is unlikely to be a single $x$ value such that $f^n(x)$ is prime for infinitely many $n$. Both questions are certainly interesting, but I don't see that they are that closely related. (I believe that the general feeling is that there are only finitely many Fermat primes.) $\endgroup$
    – Joe Silverman
    Commented Dec 26, 2013 at 12:44
3
$\begingroup$

Some comments.

Assuming a plausible, conjecture, one can make $f(a),f(f(a)),\ldots f^n(a)$ prime for arbitrary large $n$.

Take $f(x)=2 x + 1$.

This is Cunningham chain

From the above link:

It follows from Dickson's conjecture and the broader Schinzel's hypothesis H, both widely believed to be true, that for every $k$ there are infinitely many Cunningham chains of length $k$. There are, however, no known direct methods of generating such chains.

For certain $f$ one can prove this is impossible.

If some $f^n(x)$ is reducible over $\mathbb{Z}[x]$, the rest of the iterates will be reducible too.

This happens for $g(x) = x^2 - x - 1$.

$$g(g(g(x))) = (x^{4} - 3 x^{3} + 4 x - 1) \cdot (x^{4} - x^{3} - 3 x^{2} + x + 1)$$

By the boxing principle $f^k(x)$ becomes periodic $\mod p$ and if the periodic part contains zero it is impossible too -- this doesn't work for interesting coprime sequences.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .