# Will Jagy

Let

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


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

${\displaystyle \alpha (f(x))=\alpha (x)+1}$


For any

${\displaystyle x>0}$


let

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


Then we get the exact

${\displaystyle \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 ${\displaystyle n}$.

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

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

Note

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


It follows that if we define

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


we get the miraculous

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


...

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

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

It would be no problem to produce, say, 50 terms of ${\displaystyle \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

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


when

${\displaystyle f\leq x}$


As I said in comment, the way to improve this is to take a few dozen terms in the expansion of ${\displaystyle \alpha (x)}$ so as to get the desired decimal precision with a more reasonable number of evaluations of ${\displaystyle f(x).[itex]SohereisabriefversionoftheGP-PARIsessionthatproduced[itex]\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

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

${\displaystyle 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

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

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

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

{\displaystyle {\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 ${\displaystyle 7}$ and more.

Now look at the coefficients

• of the ${\displaystyle x}$-term: always ${\displaystyle 1}$.
• Of the ${\displaystyle x^{2}}$-term? In ${\displaystyle f^{\circ n}}$, it’s ${\displaystyle C_{2}(n)=n}$.
• The coefficient of ${\displaystyle x^{3}}$ in ${\displaystyle f^{\circ n}}$ is ${\displaystyle 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 ${\displaystyle C_{j}(n)}$, the coefficient of ${\displaystyle x^{j}}$ in ${\displaystyle f^{\circ n}}$, is a polynomial in ${\displaystyle n}$ of degree ${\displaystyle j-1}$.

And a familiar technique of finite differences shows you that

{\displaystyle {\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 ${\displaystyle 6}$ and higher, you have

${\displaystyle 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 ${\displaystyle 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."