4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ If $p$ has order $n$, there are constants $A$ and $B$ so that $-A+B^{-1}|x|^n\leq|p(x)|\leq A+B|x|^n$. If you can guarantee that the iterates (including the initial value) never reach zero, you can take $A=0$. Would such easy estimates be enough for you? $\endgroup$
    – Joonas Ilmavirta
    Commented Jul 15, 2015 at 20:11
  • 1
    $\begingroup$ @JoonasIlmavirta But one can say so much more. Specifically, there is a real number $H\ge1$ and positive constants $c_1$ and $c_2$, which depend on $p(x)$ and $a$, so that for all $n\ge1$ we have $c_1H^{d^n} \le |p^n(a)| \le c_2H^{d^n}$. $\endgroup$
    – Joe Silverman
    Commented Jul 15, 2015 at 22:42
  • $\begingroup$ @JoeSilverman Thanks a lot. Sorry that I am amateur but where can I find this result? I couldn't find them in the references in your answer. $\endgroup$
    – Spock
    Commented Jul 19, 2015 at 15:40
  • $\begingroup$ The section in my book says that the limit $$\lim d^{-n}\log^+|p^n(a)|$$ converges, and differs from $\log^+|a|$ by a quantity that is bounded solely in terms of $p$. If you exponentiate that relation, you get the statement in my comment. $\endgroup$
    – Joe Silverman
    Commented Jul 19, 2015 at 16:51

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ "The fact that this converges is due to Tate", can you give the year, or a reference? The fact that this converges in the complex domain is due to Hans Brolin (1965) :-) $\endgroup$
    – Alexandre Eremenko
    Commented Jul 16, 2015 at 7:23
  • $\begingroup$ @AlexandreEremenko Tate constructed canonical heights on elliptic curves by using iteration of the doubling map on the $x$-coordinate (so Lattes maps, although I don't think he knew about Lattes work). But actually, his construction is much more general, on abelian varieties. However, comme d'habitude, Tate never actually published this material. It was first described, I believe, by Manin (The Tate height of points on an abelian variety..., Izv Akad Nauk SSR Ser Math 28 (1964)). When Tate worked it out, I don't know. But I don't want to get into a priority argument, so maybe ... $\endgroup$
    – Joe Silverman
    Commented Jul 16, 2015 at 11:54
  • $\begingroup$ ... it would be fair to say that Tate worked out the theory of such limits in the context of number theory/algebraic geometry, while Brolin studied and used such limits in the context of (complex) dynamical systems. And actually, the Brolin functions, which would be defined for all complex points, are what in number theory are called "local height functions", in his case for an archimedean absolute value. There are also $p$-adic local heights, and their sum gives the global height. The construction of local heights for abelian varieties is due to Neron, also circa 1964/1965. $\endgroup$
    – Joe Silverman
    Commented Jul 16, 2015 at 11:57
  • $\begingroup$ Is dynamics (iteration of a polynomial) really mentioned in Manin's paper you refer to? $\endgroup$
    – Alexandre Eremenko
    Commented Jul 16, 2015 at 18:43
  • $\begingroup$ I am a little confused - but may have missed some subtlety. 1) Should $\log$ not be $\log_+$ (i.e., maximum of 0 and the logarithm)? Otherwise, what happens for $p(z)=z^2$ and $a=0$? 2) If this is the case, why isn't the convergence a consequence of [the proof of] Boettcher's theorem? $\endgroup$
    – Lasse Rempe
    Commented Jul 16, 2015 at 20:55
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually, the assumption that $p(x)$ has integer coefficients and that $a$ is an integer has some relevance, namely either $a$ is preperiodic, or it is in the domain of attraction of infinity. So the only way for it to be in $K(p)$ is if it is actually preperiodic. $\endgroup$
    – Joe Silverman
    Commented Jul 15, 2015 at 22:37

You must log in to answer this question.

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