Threaded Mode | Linear Mode

andydude · (This post was last modified: 05/01/2008 03:55 AM by andydude.)

In a recent post I gave a forumla for the second diagonal of iterated-dxp (e^x-1) and this line of research has led to some interesting discoveries. I have since generalized the approach to "interpolating" the diagonals of these series, and I found generating functions for the first three diagonals of parabolic iteration. I would like to present my findings and see if there is anything like this already out there...

It all started with noticing that the first diagonal is:

$f^{\circ t}(x) = \sum_{k=0}^{\infty} t^k x^{k+1} f_2^k + \cdots$

where the function being iterated is of the form $f(x) = x + \sum_{k=2}^{\infty} f_k x^k$ . This naturally lead to investigating the second diagonal, which I found is not too different than that of iterated-dxp:

$- \sum_{k=0}^{\infty} t^k x^{k+2} f_2^k H_k^{(2)} \left(f_2 - \frac{f_3}{f_2}\right)$

but it involves a little more than just harmonic numbers. So I began looking at the third diagonal, and found some patterns, but I was only able to interpolate the coefficients up to a point, then I was stuck with a sequence of rational numbers I had no idea what to do with, then I eventually found A130894/A130895 which solved the problem I was having. Before I went to OEIS, I had found the coefficients of the third diagonal to be:

$\sum_{k=0}^{\infty} t^k x^{k+3} f_2^k \left({k+1 \atop 2}\right) \left(A^2 C_k + D\right)$

where A and D are constants (described later), and $C_k$ was the rational sequence [0, 1, 3/2, 71/36, 29/12, 638/225, 349/108, ...], which according to OEIS is equivalent to
$C_n = \frac{1}{n} \sum_{k=1}^{n} \frac{H^{(2)}_k}{n+1-k}$
where H is Conway and Guy's harmonic numbers (not the usual generalized harmonic numbers). Once I had the generating functions from OEIS, then I could being playing the game of generatingfunctionology. So I took this huge expression (D is "large" when written out) for the third diagonal, and played with derivatives and integrals until it was a recognizable function that generated the right coefficients. Maybe I'll post a more in-depth discussion of the techniques I used later on, but for now, I just want to show the results.

Going back to the first diagonal:
$\sum_{k=0}^{\infty} t^k x^{k+1} f_2^k = \frac{x}{1- f_2 t x}$
and according to OEIS the generating function of the 2nd degree harmonic numbers is $-\frac{\log(1-x)}{(1-x)^2}$ , which means the second diagonal is:
$- \sum_{k=0}^{\infty} t^k x^{k+2} f_2^k H_k^{(2)} A = x^2 \frac{\log(1 - f_2 t x)}{(1 - f_2 t x)^2} A$
where $A = \left(f_2 - \frac{f_3}{f_2}\right)$ and using the new generating functions for $C_k$ , we find the generating function for the third diagonal is:

$\sum_{k=0}^{\infty} t^k x^{k+3} f_2^k \left({k+1 \atop 2}\right) \left(A^2 C_k + D\right) = x^3 \frac{A^2(\log(1 - f_2 t x)^2 - \log(1 - f_2 t x)) + (f_2 t x) D}{(1 - f_2 t x)^3}$

and finally, written out in full:
$ \begin{tabular}{rl} f^{\circ t}(x) & = \frac{x}{z} \\ & + \left(\frac{x}{z}\right)^2 \left(f_2 - \frac{f_3}{f_2}\right) \log(z) \\ & + \left(\frac{x}{z}\right)^3 \left[ \left(f_2 - \frac{f_3}{f_2}\right)^2 (\log(z)^2 - \log(z)) + (1-z)\left(\frac{f_2}{2} \left(f_2 - \frac{f_3}{f_2}\right) - \left(\frac{f_3}{f_2}\right)^2 + \frac{f_4}{f_2} \right) \right] \\ & + \cdots \end{tabular} $
where $z = 1 - f_2 t x$ .

The most fascinating part, though, is that t only appears in z.

Andrew Robbins

Ivars · 04/30/2008, 10:19 AM

Hi Andrew,

For basic readers like me, what exactly is ${f_2}$ in $z = 1 - f_2 t x$ ? and is $z = 1 - f_2 t x = 1- f_2 *t* x$ ?

Thank You in advance,

Ivars

andydude · (This post was last modified: 05/05/2008 10:41 PM by andydude.)

Ivars Wrote:For basic readers like me, what exactly is ${f_2}$ in $z = 1 - f_2 t x$ ? and is $z = 1 - f_2 t x = 1- f_2 *t* x$ ?

Well, $f_2 = \frac{f''(0)}{2}$ and in general, $f_k = \frac{1}{k!}\frac{d^k}{dx^k}f(0) = \frac{1}{k!} \left[ \frac{d^k}{dx^k}f(x)\right]_{x=0}$ . These are the coefficients of a Taylor series.

And yes, that's normal multiplication.

Any other questions? Smile

Andrew Robbins

Ivars · 04/30/2008, 07:02 PM

Is not

$(\log(z)^2 - \log(z))$ just $\log(z)$ ?

Ivars

andydude · 04/30/2008, 07:34 PM

Ivars Wrote:Is not $(\log(z)^2 - \log(z))$ just $\log(z)$ ?

No, $(\log(z)^2 - \log(z)) = \log(z)(\log(z)-1)$
but $(\log(z^2) - \log(z)) = \log(z)$ .

Do not confuse $\log(z)^2$ and $\log(z^2)$ , they are two completely different functions.

Andrew Robbins

andydude · (This post was last modified: 05/03/2008 08:13 PM by andydude.)

From these generating functions is it easy to see that parabolic iteration does not work for $f_2 = 0$ , which I believe has already been proven by someone, somewhere. What is interesting is that there are actually 2 reasons for this. The first reason is that there are many $f_2$ in the denominator, which cannot be zero, and the second reason is that if $f_2 = 0$ , then $z=1$ which means t plays no part in the equations at all.

Also, I wonder if studying the special case $f^{\circ 1/x}(x)$ would yield more insights, as this would imply that $z = 1 - f_2$ , so there wouldn't be an x in the denominator. This would make finding more diagonals easier.

Andrew Robbins

PS. I think it was either Bennet or Jabotinsky that showed $f_2 = 0$ doesn't work.

***bo198214*** · 05/04/2008, 07:14 AM

I admit I didnt dive completely into your derivations.
First question what is the parabolic flow matrix?
Is it the Carleman/Bell-Matrix of parabolic iteration $f^{\circ t}(x)$ ?
Why is it then important to know the diagonals? Because the first entry is the coefficient of the series of $f^{\circ t}(x)$ ?

andydude Wrote:From these generating functions is it easy to see that parabolic iteration does not work for $f_2 = 0$ ,
which I believe has already been proven by someone, somewhere. What is interesting is that there are actually 2 reasons for this. The first reason is that there are many $f_2$ in the denominator, which cannot be zero, and the second reason is that if $f_2 = 0$ , then $z=1$ which means t plays no part in the equations at all.

I dont get this, lets look at the double binomial formula, which should give the same coefficients if I understood that right. There are no denominators depending on the value of any $f_k$ . I only know that in hyperbolic iteration there occurs $f_1^n-f_1$ in the denominator.

So lets clarify the basics first Smile

andydude · 05/05/2008, 05:26 AM

What is the flow matrix?
The flow matrix (although it could also be called iterational matrix ... see here) is the matrix of coefficients $A_{jk}$ where $f^{\circ t}(x) = \sum_{j=0}^{\infty}\sum_{k=0}^{\infty} A_{jk} t^j x^k$ which are obtained from any method (usually a special case of regular iteration), for parabolic iteration there will only be a finite number of t's, but for hyperbolic iteration (yes, the flow matrix would apply to that as well) this matrix is not triangular (as it is with parabolic iteration). For parabolic iteration the "flow series" is:

$ \begin{tabular}{rl} f^{\circ t}(x) & = x \\ & + x^2 \left( tf_2 \right) \\ & + x^3 \left( t(f_3-f_2^2) + t^2f_2^2 \right) \\ & + x^4 \left( t\left(\frac{f_2}{2}(3f_2^2 - 5f_3) + f_4\right) + t^2\left(\frac{5f_2}{2}(f_3-f_2^2) \right) + t^3f_2^3 \right) \\ & + \cdots \end{tabular} $

this corresponds to the "flow matrix":

$ \left[\begin{tabular}{cccccc} 0 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 0 & 0 & \cdots \\ 0 & f_2 & 0 & 0 & 0 & \cdots \\ 0 & (f_3-f_2^2) & f_2^2 & 0 & 0 & \cdots \\ 0 & \left(\frac{f_2}{2}(3f_2^2 - 5f_3) + f_4\right) & \left(\frac{5f_2}{2}(f_3-f_2^2) \right) & f_2^3 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{tabular}\right] $

However, the flow matrix is not limited to parabolic iteration, but applies to hyperbolic iteration as well. Since the coefficients of hyperbolic iteration are not polynomials, there is a big difference between the series and the matrix, which may serve to illustrate the need for an flow matrix. For hyperbolic iteration the "flow series" is:

$ \begin{tabular}{rl} f^{\circ t}(x) & = x f_1^t \\ & + x^2 \frac{f_1^{t-1}(f_1^{t} - 1)f_2}{(f_1 - 1)} \\ & + x^3 \frac{f_1^{t-2}(f_1^t-1)(f_1((f_1-1)f_3-2f_2^2) + f_1^t(2f_2^2 + (f_1-1)f_1f_3))}{(f_1-1)^2(f_1+1)} \\ & + \cdots \end{tabular} $

which corresponds to the "flow matrix":

$ \left[\begin{tabular}{cccc} 0 & 0 & 0 & \cdots \\ 1 & \log(f_1) & \log(f_1)^2/2 & \cdots \\ 0 & \frac{f_2\log(f_1)}{(f_1-1)f_1} & \frac{3f_2\log(f_1)^2}{2(f_1-1)f_1} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{tabular}\right] $

Is it the Carleman matrix of parabolic iteration?
No, it is the first row of the Carleman matrix^t, or the first column of the Bell matrix^t, meaning both have been raised to the t. The flow matrix is simply a different expression for the flow series.

Why is it important to know the diagonals?
Well, it seems important to know the asymptotic behavior of the coefficients, and it is very difficult to know the asymptotic behavior of a sequence you only have the first few members of, so my goal with these diagonals is to provide a formula that we can use for root-tests and other convergence tests, so the world will stop calling them "formal power series" and start calling them functions. That is my ultimate goal.

But then again, how am I helping when I only have 3 diagonals, and we don't need to find asymptotic behavior of $t^k x^k$ but of $t^k$ ? Well, it is obvious that the diagonals follow more of a pattern than the columns, so it seems easier to interpolate the diagonals than the columns of the flow matrix. My hope is that after enough diagonals are found, then a pattern will be found in the columns, as well.

Are these the same as Jabotinsky's double-binomial formula?
Yes. However, that formula is expressed in terms of the coefficients of the n-th iterate of a function. The only way I've seen Daniel Geisler write the flow series has been in terms of the coefficients of the 1-st iterate only, which is a major distinction between Jabotinsky's, and the flow series.

Andrew Robbins

andydude · 05/05/2008, 08:30 AM

bo198214 Wrote:I admit I didnt dive completely into your derivations.

I'm sorry for the terseness, it was very complicated, and the way I found them was to look at lots of finite differences and finite quotients until I saw a pattern. I will describe my derivation techniques as soon as I finish the "HyperSage" library.

Also, for comparison, Gottfried gives the same "parabolic flow matrix" as table (1.6.1.4.) in ContinuousfunctionalIteration.pdf

Andrew Robbins

***bo198214*** · 05/05/2008, 05:33 PM

andydude Wrote:I'm sorry for the terseness,

No, no, its ok. I just lacked the basics, thats all. Thank you for your very nice explanation. I just have digest it and then look at the case $f_2$ . Because I dont believe that it should not be possible, the question would be what goes wrong in the case $f_2=0$ , can only be a convergence thing. Perhaps Walker excluded that case in his construction of an entire superexponential.

Possibly Related Threads...
Thread:		Author	Replies:	Views:	Last Post
	Iteration series: Half-iterate using the infinite iteration-series?	Gottfried	31	2,450	01/04/2013 05:21 PM Last Post: sheldonison
	Iteration series: Different fixpoints and iteration series (of an example polynomial)	Gottfried	0	466	09/04/2011 05:59 AM Last Post: Gottfried
	Fractional iteration of x^2+1 at infinity and fractional iteration of exp	bo198214	10	2,824	06/09/2011 05:56 AM Last Post: bo198214
	Parabolic Iteration	andydude	3	2,676	08/16/2007 07:51 PM Last Post: bo198214