Growth of the size of iterated polynomials I have been working independently on a project but now I am stuck and need to seek an expert's wisdom for a part of it. I am basically looking for theorems related to growth of the size of polynomials. My Google search has led me to papers on root-finding algorithms which is not what I intend to do. 
I am dealing with polynomials $p(x)$ of degree at least $2$ in $\mathbb{Z}[x]$ with a non-zero constant term and the size of the $n$-th iteration, i.e. $|p^{\circ n}(a)|$, where $a$ is any integer. 
My example was very specific but I am looking for anything remotely similar. Is there any results that you know of related to the size and the growth rate of polynomials? Any comparison or upper/lower bound theorems?
 A: The quantity you're looking for, I think, is the canonical height of $a$ with respect to the polynomial $p(x)$. In your situation, since you're just dealing with integers, if we let $d=\deg(p)\ge 2$, then the canonical height is defined by
$$ \hat h_p(a) = \lim_{n\to\infty} \frac{1}{d^n}\log\bigl|p^n(a)\bigr|. $$
The fact that the limit converges is due to Tate, and a very general version was proven by Call and me. The canonical height has many nice properties, including the following:


*

*There is a constant $C=C(p)$ so $\bigl|\hat h_p(b) - \log|b|\bigr|<C$ for all integers $b$.

*$\hat h_p\bigl(p(b)\bigr) = d \hat h_p(b)$ for all integers $b$.

*The integer $b$ is preperiodic for $p$ if and only if $\hat h_p(b)=0$. (Being preperiodic means that there are $m>n\ge0$ so that $p^m(b)=p^n(b)$. Note that in any case we have $\hat h_p(b)\ge0$.)


In particular, if your $a$ is not preperiodic, then using these facts you get a pretty good estimate for $\log\bigl|p^n(a)\bigr|$, namely
$$
  \log\bigl|p^n(a)\bigr| = \hat h_p\bigl(p^n(a)\bigr) + O(1)
  = d^n \hat h_p(a) + O(1),
$$
where the $O(1)$ depends on $p$, but not on $a$ or $n$. Further, with more work, one can even show that if $B$ is a bound for the largest coefficient of $p(x)$, then the $O(1)$ can be replaced by $O(\log|B|)$, where now the big-$O$ constant depends only on the degree of $p(x)$. Here are a couple references for all of this:
Section 3.4 of The Arithmetic of Dynamical Systems, J.H. Silverman, Springer, GTM 241.
G. Call, J.H. Silverman, Canonical heights on varieties with
morphisms, Compositio Math. 89 (1993), 163-205.
A: The size of $|p^n(a)|$ can be very different depending on $a$.
If $a$ is periodic point of 
$p$, then
this sequence will
be bounded. If $a$ is in the domain of attraction of infinity then
$\log|p^n(a)|$ is like $d^n$ where $d$ is the degree.
More precisely, for each polynomial there is a compact set $K(p)$ in the complex plane,
called the filled in Julia set, such that for $a\in K(f)$ your sequence is bounded, while
for $a\not\in K(p)$ it grows like $d^n$. When searching on Google look on "Holomorphic dynamics".
Remark. It is irrelevant for what I wrote above, whether $a$ is an integer or not and whether the coefficients are integer or complex. However, as Joe Silverman suggested in his comment, if the coefficients and $a$ are integers, then $p^n(a)$ are
also integers, and as $K(f)$ may contain only finitely many integers,
the sequence can be bounded only if it is pre-periodic, that is becomes periodic after
the removal of finitely many terms.
EDIT. So for polynomials over integers and integer $a$, the question whether the sequence is bounded can be solved by finitely many arithmetic operations. But this is not completely trivial: one needs an explicit estimate, how many integer points can $K(f)$ contain, or something equivalent to this.
And from the discussion of the history I conclude that the result essentially follows from a theorem of L. E. Bottcher (early 1900-s) who proved the existence of an analytic function
$\phi(z)\sim z$ near $\infty$ which conjugates the polynomial with $z^d$, that is
$$\phi\circ p(z)=\phi(z)^d.$$
But Bottcher did not investigate the full domain of existence of this function, 
and $\phi$ may not exist
in the whole domain of attraction of $\infty$. The idea to consider $\log|\phi|$ which is well-defined in the whole domain of attraction and can be extended to a subharmonic function in the whole plane
was for the first time published by Brolin in 1965. Tate apparently had the same idea simultaneously or earlier but did not publish it.
