Fractals/Iterations in the complex plane/Fatou coordinate for f(z)=z+z^2)

Will Jagy

http://math.stackexchange.com/questions/208996/half-iterate-of-x2c?

" This may be helpful.

Let

$f(x)={\frac {-1+{\sqrt {1+4x}}}{2}},\;\;x>0$

We use a technique of Ecalle to solve for the Fatou coordinate $\alpha$ that solves

$\alpha (f(x))=\alpha (x)+1$

For any

$x>0$

let

$x_{0}=x,\;x_{1}=f(x),\;x_{2}=f(f(x)),\;x_{n+1}=f(x_{n})$

Then we get the exact

$\alpha (x)=\lim _{n\rightarrow \infty }{\frac {1}{x_{n}}}-\log x_{n}+{\frac {x_{n}}{2}}-{\frac {x_{n}^{2}}{3}}+{\frac {13x_{n}^{3}}{36}}-{\frac {113x_{n}^{4}}{240}}+{\frac {1187x_{n}^{5}}{1800}}-{\frac {877x_{n}^{6}}{945}}-n$

The point is that this expression converges far more rapidly than one would expect, and we may stop at a fairly small $n$.

It is fast enough that we may reasonably expect to solve numerically for $\alpha ^{-1}(x)$.

We have $f^{-1}(x)=x+x^{2}$

Note

$\alpha (x)=\alpha (f^{-1}(x))+1$
$\alpha (x)-1=\alpha (f^{-1}(x))$
$\alpha ^{-1}\left(\alpha (x)-1\right)=f^{-1}(x)$

It follows that if we define

$g(x)=\alpha ^{-1}\left(\alpha (x)-{\frac {1}{2}}\right)$

we get the miraculous

$g(g(x))=\alpha ^{-1}\left(\alpha (x)-1\right)=f^{-1}(x)=x+x^{2}$

...

Note that $\alpha$ is actually holomorphic in an open sector that does not include the origin, such as real part positive. That is the punchline here, $\alpha$ cannot be extended around the origin as single-valued holomorphic. So, since we are finding a power series around $0$, not only are there a $1/z$ term, which would not be so bad, but there is also a $\log z$ term. So the $\ldots -n$ business is crucial.

I give a complete worked example at my question http://mathoverflow.net/questions/45608/formal-power-series-convergence as my answer http://mathoverflow.net/questions/45608/formal-power-series-convergence/46765#46765

The Ecalle technique is described in English in a book, see

• [K_C_G PDF] http://zakuski.utsa.edu/~jagy/K_C_G_book_excerpts.pdf
• [BAKER] http://zakuski.utsa.edu/~jagy/other.html

The Julia equation is Theorem 8.5.1 on page 346 of KCG.

It would be no problem to produce, say, 50 terms of $\alpha (x)$ with some other computer algebra system that allows longer power series and enough programming that the finding of the correct coefficients, which i did one at a time, can be automated.

No matter what, you always get the

$\alpha ={\mbox{stuff}}-n$

when

$f\leq x$

As I said in comment, the way to improve this is to take a few dozen terms in the expansion of $\alpha (x)$ so as to get the desired decimal precision with a more reasonable number of evaluations of $f(x).<math>SohereisabriefversionoftheGP-PARIsessionthatproduced<math>\alpha (x)$:

=======

        ? taylor( (-1 + sqrt(1 + 4 * x))/2  , x  )
        %1 = x - x^2 + 2*x^3 - 5*x^4 + 14*x^5 - 42*x^6 + 132*x^7 - 429*x^8 + 1430*x^9 - 4862*x^10 + 16796*x^11 - 58786*x^12 + 208012*x^13 - 742900*x^14 + 2674440*x^15 + O(x^16) 
        
        f = x - x^2 + 2*x^3 - 5*x^4 + 14*x^5 - 42*x^6 + 132*x^7 - 429*x^8 + 1430*x^9 - 4862*x^10 + 16796*x^11 - 58786*x^12 + 208012*x^13 - 742900*x^14 + 2674440*x^15  
        
        ? fp = deriv(f) 
        %3 = 40116600*x^14 - 10400600*x^13 + 2704156*x^12 - 705432*x^11 + 184756*x^10 - 48620*x^9 + 12870*x^8 - 3432*x^7 + 924*x^6 - 252*x^5 + 70*x^4 - 20*x^3 + 6*x^2 - 2*x + 1 
        
        L = - f^2 + a * f^3 
        
        R = - x^2 + a * x^3
        
        compare = L - fp * R 
        
        19129277941464384000*a*x^45 - 15941064951220320000*a*x^44 +
     8891571783902889600*a*x^43 - 4151151429711140800*a*x^42 + 
    1752764158206050880*a*x^41 - 694541260905326880*a*x^40 + 
    263750697873178528*a*x^39 - 97281246609064752*a*x^38 + 35183136631942128*a*x^37 
    - 12571609170862072*a*x^36 + 4469001402841488*a*x^35 - 1592851713897816*a*x^34 + 
    575848308018344*a*x^33 - 216669955210116*a*x^32 + 96991182256584*a*x^31 + 
    (-37103739145436*a - 7152629313600)*x^30 + (13153650384828*a + 
    3973682952000)*x^29 + (-4464728141142*a - 1664531636560)*x^28 + (1475471500748*a 
    + 623503489280)*x^27 + (-479514623058*a - 220453019424)*x^26 + (154294360974*a + 
    75418138224)*x^25 + (-49409606805*a - 25316190900)*x^24 + (15816469500*a + 
    8416811520)*x^23 + (-5083280370*a - 2792115360)*x^22 + (1648523850*a + 
    930705120)*x^21 + (-543121425*a - 314317080)*x^20 + (183751830*a + 
    108854400)*x^19 + (-65202585*a - 39539760)*x^18 + (-14453775*a + 15967980)*x^17 
    + (3380195*a + 30421755)*x^16 + (-772616*a - 7726160)*x^15 + (170544*a + 
    1961256)*x^14 + (-35530*a - 497420)*x^13 + (6630*a + 125970)*x^12 + (-936*a - 
    31824)*x^11 + 8008*x^10 + (77*a - 2002)*x^9 + (-45*a + 495)*x^8 + (20*a - 
    120)*x^7 + (-8*a + 28)*x^6 + (3*a - 6)*x^5 + (-a + 1)*x^4 
       
        Therefore a = 1  !!! 
        
        ? 
        L = - f^2 +  f^3 + a * f^4
        
        R = - x^2 +  x^3 + a * x^4 
        
        compare = L - fp * R 
         ....+ (1078*a + 8008)*x^10 + (-320*a - 1925)*x^9 + (95*a + 450)*x^8 + (-28*a - 100)*x^7 + (8*a + 20)*x^6 + (-2*a - 3)*x^5 
        
        This time a = -3/2  !
        
        
        L = - f^2 +  f^3  - 3 * f^4 / 2  + c * f^5 
        
        R = - x^2 +  x^3 - 3 * x^4 / 2  + c * x^5  
        
         compare = L - fp * R
        ...+ (2716*c - 27300)*x^11 + (-749*c + 6391)*x^10 + (205*c - 1445)*x^9 + (-55*c + 615/2)*x^8 + (14*c - 58)*x^7 + (-3*c + 8)*x^6 
        
        
        So c = 8/3 . 
        
        The printouts began to get too long, so I said no using semicolons, and requested coefficients one at a time..
        
        L = - f^2 +  f^3  - 3 * f^4 / 2  + 8 * f^5 / 3 + a * f^6; 
        
        R = - x^2 +  x^3 - 3 * x^4 / 2  + 8 * x^5 / 3  + a * x^6; 
        
           compare = L - fp * R;
         
        ? polcoeff(compare,5)
        %22 = 0
        ? 
        ?  polcoeff(compare,6)
        %23 = 0
        ? 
        ?  polcoeff(compare,7)
        %24 = -4*a - 62/3
        
        So this a = -31/6 
        
        
        I ran out of energy about here:
          L = - f^2 +  f^3  - 3 * f^4 / 2  + 8 * f^5 / 3 - 31 * f^6 / 6 + 157 * f^7 / 15 - 649 * f^8 / 30 + 9427 * f^9 / 210 + b * f^10 ; 
        
          R = - x^2 +  x^3 - 3 * x^4 / 2  + 8 * x^5 / 3  - 31 * x^6 / 6 + 157 * x^7 / 15 - 649 * x^8 / 30 + 9427 * x^9 / 210  + b * x^10;
        
           compare = L - fp * R; 
        ? 
        ?  polcoeff(compare, 10 )
        %56 = 0
        ? 
        ? 
        ?  polcoeff(compare, 11 ) 
        %57 = -8*b - 77692/105
        ? 
        ? 
          L = - f^2 +  f^3  - 3 * f^4 / 2  + 8 * f^5 / 3 - 31 * f^6 / 6 + 157 * f^7 / 15 - 649 * f^8 / 30 + 9427 * f^9 / 210 - 19423 * f^10 / 210 ; 
        
          R = - x^2 +  x^3 - 3 * x^4 / 2  + 8 * x^5 / 3  - 31 * x^6 / 6 + 157 * x^7 / 15 - 649 * x^8 / 30 + 9427 * x^9 / 210 - 19423 * x^10 / 210;
        
           compare = L - fp * R; 
        ?  polcoeff(compare, 10 )
        %61 = 0
        ? 
        ?  polcoeff(compare, 11 ) 
        %62 = 0
        ? 
        ?  polcoeff(compare, 12) 
        %63 = 59184/35
        ? 
        
        So R = 1 / alpha' solves the Julia equation   R(f(x)) = f'(x) R(x).
        
        Reciprocal is alpha'
        
        ? S =   taylor( 1 / R, x)
        %65 = -x^-2 - x^-1 + 1/2 - 2/3*x + 13/12*x^2 - 113/60*x^3 + 1187/360*x^4 - 1754/315*x^5 + 14569/1680*x^6 + 532963/3024*x^7 + 1819157/151200*x^8 - 70379/4725*x^9 + 10093847/129600*x^10 - 222131137/907200*x^11 + 8110731527/12700800*x^12 - 8882574457/5953500*x^13 + 24791394983/7776000*x^14 - 113022877691/18144000*x^15 + O(x^16) 
        
        The bad news is that Pari refuses to integrate 1/x, 
    even when I took out that term it put it all on a common denominator,
     so i integrated one term at a time to get
    
    alpha = integral(S)
    
    and i had to type in the terms myself, especially the log(x)
        
        ? alpha = 1 / x - log(x) + x / 2 - x^2 / 3 + 13 * x^3 / 36 - 113 * x^4 / 240 + 1187 * x^5 / 1800 - 877 * x^6 / 945 + 14569 * x^7 / 11760 + 532963 * x^8 / 24192

======

"

Jonathan Lubin

From http://math.stackexchange.com/questions/911818/how-to-obtain-fx-if-it-is-known-that-ffx-x2x?

"Here’s a technique for finding the first few terms of a formal power series representing the fractional iterate of a given function like

$f(x)=x+x^{2}$.

I repeat that this is a formal solution to the problem, and leaves unaddressed all considerations of convergence of the series answer.

I’m going to find the first six terms of

$f^{\circ 1/2}(x)$

the “half-th” iterate of $f$, out to the $x^{5}$-term.

Let’s write down the iterates of $f$, starting with the zero-th.

${\begin{aligned}f^{\circ 0}(x)&=x\\f^{\circ 1}=f&=x&+x^{2}\\f^{\circ 2}&=x&+2x^{2}&+2x^{3}&+x^{4}\\f^{\circ 3}&\equiv x&+3x^{3}&+6x^{3}&+9x^{4}&+10x^{5}&+8x^{6}\\f^{\circ 4}&\equiv x&+4x^{2}&+12x^{3}&+30x^{4}&+64x^{5}&+118x^{6}\\f^{\circ 5}&\equiv x&+5x^{2}&+20x^{3}&+70x^{4}&+220x^{5}&+630x^{6}\\f^{\circ 6}&\equiv x&+6x^{2}&+30x^{3}&+135x^{4}&+560x^{5}&+2170x^{6}\\f^{\circ 7}&\equiv x&+7x^{2}&+42x^{3}&+231x^{4}&+1190x^{5}&+5810x^{6}\,,\end{aligned}}$

where the congruences are modulo all terms of degree $7$ and more.

Now look at the coefficients

• of the $x$-term: always $1$.
• Of the $x^{2}$-term? In $f^{\circ n}$, it’s $C_{2}(n)=n$.
• The coefficient of $x^{3}$ in $f^{\circ n}$ is $C_{3}(n)=n(n-1)=n^{2}-n$, as one can see by inspection.

Now, a moment’s thought (well, maybe several moments’) tells you that $C_{j}(n)$, the coefficient of $x^{j}$ in $f^{\circ n}$, is a polynomial in $n$ of degree $j-1$.

And a familiar technique of finite differences shows you that

${\begin{aligned}C_{4}(n)&={\frac {2n^{3}-5n^{2}+3n}{2}}\\C_{5}(n)&={\frac {3n^{4}-13n^{3}+18n^{2}-8n}{3}}\,,\end{aligned}}$

I won’t go into the details of that technique. The upshot is that, modulo terms of degree $6$ and higher, you have

$f^{\circ n}(x)\equiv x+nx^{2}+(n^{2}-n)x^{3}+{\frac {1}{2}}(2n^{3}-5n^{2}+3n)x^{4}+{\frac {1}{3}}(3n^{4}-13n^{3}+18n^{2}-8n)x^{5}$.

Now, you just plug in $n={\frac {1}{2}}$ in this formula to get your desired series.

And I’ll leave it to you to go one degree higher, using the iterates I’ve given you."