10
$\begingroup$

Motivated by this question.

Let $f \in \mathbb{Q}[x]$ or$f \in \mathbb{Z}[x]$ .

Consider the sequence $f(x),f(f(x)), \ldots f^n(x)$.

If some $f^k(x)$ is reducible, the rest 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)$$

Fermat numbers are related to similar quadratic map and if it happens to be reducible for some $k$, this will mean there are infinitely many Fermat composites.

Given $f$, is it possible to decide if some $f^k(x)$ is reducible?

$\endgroup$
6
  • $\begingroup$ Joro, I added a logic tag. $\endgroup$ Commented Dec 24, 2013 at 11:36
  • 1
    $\begingroup$ Do we actually know a non-linear polynomial $f(x)$ such that $f^n(x)$ is irreducible for all $n$? $\endgroup$ Commented Dec 24, 2013 at 13:22
  • $\begingroup$ You guys should ask Michael Zieve. He has answered similar questions. $\endgroup$ Commented Dec 24, 2013 at 13:30
  • $\begingroup$ Related: arxiv.org/abs/1210.4127 Newly reducible iterates in families of quadratic polynomials $\endgroup$
    – joro
    Commented Dec 24, 2013 at 13:54
  • $\begingroup$ @SJR the answer to your question appears to be yes, check the arxiv reference from my comment. $\endgroup$
    – joro
    Commented Dec 24, 2013 at 13:56

1 Answer 1

13
$\begingroup$

I believe that the first person with significant results along these lines was Odoni [1]. There are also papers of Rafe Jones that consider questions of this sort, see for example [2] and [3]. A polynomial is called stable if all of its iterates are irreducible, and more generally, a polynomial is called eventually stable if for all sufficiently large $n$, the factorization of $f^n(x)$ in $\mathbb{Q}[x]$ is completely explained by factorizations of $f^m(x)$ for a fixed finite collection of $m$ values. There is a conjecture that says that all (maybe with a few obvious exceptions) polynomials are eventually stable.

This problem has also been studied over finite fields,. Note that if $f\in\mathbb{Z}[x]$ is monic and if $f^n(x) \bmod{p}$ is irreducible for some prime $p$ and all $n$, then $f$ is also stable over $\mathbb{Q}$. For a recent paper and a recent preprint with finite field stability results, see [4] and [5].

This reference list isn't meant to be exhaustive, but if you look at these papers and forward and backward reference them, you should be able to find pretty much everything that's known and conjectured regarding (eventual) stability.

[1] Odoni, R. W. K., The Galois theory of iterates and composites of polynomials, Proc. London Math. Soc. (3), 51 (1985), 385-414.

[2] Jones, Rafe, An iterative construction of irreducible polynomials reducible modulo every prime, J. Algebra 369 (2012), 114-128.

[3] Jones, Rafe and Rouse, Jeremy, Galois theory of iterated endomorphisms, Proc. Lond. Math. Soc. (3) 100 (2010),763-794.

[4] Ahmadi, Omran and Luca, Florian and Ostafe, Alina and Shparlinski, Igor E., On stable quadratic polynomials, Glasg. Math. J. 54 (2102), 359-369.

[5] Gomez-Perez, Domingo and Nicolas, Alejandro and Ostafe, Alina and Sadornil, Daniel, Stable Polynomials over Finite Fields, 2012, arXiv:1206.4979.

$\endgroup$

You must log in to answer this question.

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