Asymptotics of iterated polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T17:56:22Z http://mathoverflow.net/feeds/question/11691 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11691/asymptotics-of-iterated-polynomials Asymptotics of iterated polynomials Michael Lugo 2010-01-13T19:59:10Z 2011-06-10T18:32:38Z <p>Let the sequence $u_1, u_2, \ldots$ satisfy $u_{n+1} = u_n - u_n^2 + O(u_n^3)$. Then it can be shown that if $u_n \to 0$ as $n \to \infty$, then $u_n = n^{-1} + O(n^{-2} \log n)$. (See N. G. de Bruijn, <i>Asymptotic methods in analysis</i>, Section 8.5.)</p> <p>This can be used to obtain asymptotics for $v_{n+1} = Av_n - Bv_n^2 + O(v_n^3)$, where $A$ and $B$ are constants. Let $w_n = A^{-n} v_n$; this gives $$A^{n+1} w_{n+1} = A^{n+1} w_n - B A^n w_n^2 + O(A^n w_n^3)$$ and so $$w_{n+1} = w_n - BA^{-1} w_n^2 + O(w_n^3).$$ Then let $w_n = Ax_n/B$ to get $$Ax_{n+1}/B = Ax_n/B - B/A \cdot (Ax_n/B)^2 + O(x_n^3)$$ and after simplifying $x_{n+1} = x_n - x_n^2 + O(x_n^3)$. This satisfies the initial requirements for $u_n$ (with some checking of the side condition); then substitute back.</p> <p>But say I actually know that $u_{n+1} = P(u_n)$ for some polynomial $P$, with $P(z) = z - z^2 + a_3 z^3 + \cdots + a_d z^d.$ In this case it seems like it should be possible to get more explicit information about $u_n$. Is there a known algorithm for computing an asymptotic series for $u_n$ as $n \to \infty$?</p> http://mathoverflow.net/questions/11691/asymptotics-of-iterated-polynomials/11707#11707 Answer by 002 for Asymptotics of iterated polynomials 002 2010-01-13T23:04:21Z 2010-01-13T23:04:21Z <p>Have you tried the method of section 8.7, i.e., solving Abel's equation $\phi(P(x))-\phi(x)=1$? Here we expect <code>$\phi(t)=t^{-1}+\sum_{n=1}^{\infty}c_n t^n$</code>, and you can find the coefficients of $\phi$ one by one. For example, I took $P(x)=x-x^2+x^3+x^4$ and immediately found <code>$c_1=-2$</code>, <code>$c_2=-5/2$</code>, <code>$c_3=-7/2$</code>, <code>$c_4=-17/4$</code>... Not a general formula, but you can get as many terms as you want for a given $P$.</p> http://mathoverflow.net/questions/11691/asymptotics-of-iterated-polynomials/67462#67462 Answer by Sylvain Bonnot for Asymptotics of iterated polynomials Sylvain Bonnot 2011-06-10T18:32:38Z 2011-06-10T18:32:38Z <p>As explained above by 002, solving Abel equation is indeed the key. Using the language of holomorphic dynamics, people would say that you are studying the dynamics of a polynomial near the parabolic fixed point $z=0$. By a simple linear change of variables, the study of any such parabolic fixed point can be reduced to the study of $z \mapsto z+z^{2}+O(z^3)$. Then you can apply another change $w=-\frac{1}{z}$. Thus you are reduced to the study of $f(w)=w+1+O(1/w)$. If the real part $Re(w)$ is large enough you will obtain $f^{n}(w)=w+n+O(\log n)$. This will give you what you want (when going back to the z-variable).</p> <p>The domain $Re(w)>R$ (for large $R$) looks like some kind of cardioid (in your particular case) when you visualize it in the z-variable (it's poetically called an attracting petal). All this material is explained in details in several books. One great example is the book by John Milnor on Complex dynamics. Here is a free (earlier) version: <a href="http://www.math.sunysb.edu/cgi-bin/preprint.pl?ims90-5" rel="nofollow">http://www.math.sunysb.edu/cgi-bin/preprint.pl?ims90-5</a></p> <p>So in summary the key words you should look for are: parabolic fixed point, Fatou coordinates, Leau-Fatou flower theorem (the last one describing those "petals")...</p>