+- Tetration Forum (https://tetrationforum.org)
+-- Forum: Tetration and Related Topics (https://tetrationforum.org/forumdisplay.php?fid=1)
+--- Forum: Mathematical and General Discussion (https://tetrationforum.org/forumdisplay.php?fid=3)
+--- Thread: Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. (/showthread.php?tid=611)
Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. - mike3 - 03/20/2011
Hi.
I just managed to put together the hard proof of the explicit, non-recursive formula for the solution of general recurrences of the form
\( a_1 = r_{1,1} \)
\( a_n = \sum_{m=1}^{n-1} r_{n,m} a_m \)
that I mentioned here:
http://math.eretrandre.org/tetrationforum/showthread.php?tid=576&pid=5542#pid5542
The note with the proof is attached to this post. Comments, critique, etc. would be welcomed.
This proves the existence of the explicit non-recursive expression for the coefficients of the regular Schroder function of \( f(z) = e^{uz} - 1 \), and indeed, of the coefficients of regular Schroder functions in general.
So the question now becomes: is there a more "elegant" expression? I'll give some attempts at trying to take a whack at it here.
1. The regular Schroder function (at the natural fixed point 0) coefficients are given by the above recurrence formula, or the general explicit formula, with
\( r_{1,1} = 1 \)
\( r_{n,m} = \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \).
(where \( \left{{n \atop m}\right} \) is a Stirling number of the 2nd kind.)
Let the resulting coefficients "\( a_n \)" be denoted \( \chi_n \). Then the Schroder function is
\( \chi(z) = \sum_{n=1}^{\infty} \chi_n z^n \).
2. Now, we go and expand these out. The first few coefficients look like:
\( \chi_1 = 1 \)
\( \chi_2 = \frac{u}{-2u + 2} \)
\( \chi_3 = \frac{-2u^3 - u^2}{-6u^3 + 6u^2 + 6u - 6} \)
\( \chi_4 = \frac{6u^6 + 5u^5 + 6u^4 + u^3}{-24u^6 + 24u^5 + 24u^4 - 24u^2 - 24u + 24} \)
\( \chi_5 = \frac{-24u^{10} - 26u^9 - 46u^8 - 45u^7 - 24u^6 - 14u^5 - u^4}{-120u^{10} + 120u^9 + 120u^8 - 240u^5 + 120u^2 + 120u - 120} \).
...
Factoring the denominators and pattern recognition suggests
\( \chi_n = \frac{\sum_{j=n}^{\frac{n(n-1)}{2}} \mathrm{smag}_{n,j} u^j}{(-1)^n n! \prod_{j=1}^{n-1} (1 - u^j), n > 1 \)
where \( \mathrm{smag}_{n,j} \) are the so-called "Schroder function magic numbers".
3. We want to turn this into a recurrence on the numerators. Let \( N_n \) denote the numerator of the nth term \( \chi_n \). Then we have
\( N_n = (-1)^n n! \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \chi_n \).
Now insert the recurrent expression for \( \chi_n \):
\( \begin{align}
N_n &= (-1)^n n! \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \left(\sum_{m=1}^{n-1} \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \chi_m\right)\\
&= (-1)^n n! \sum_{m=1}^{n-1} \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \chi_m\\
&= (-1)^n n! \sum_{m=1}^{n-1} \left(\prod_{j=1}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} \left{{n \atop m}\right} \frac{N_m}{(-1)^m m! \prod_{j=1}^{m-1} (1 - u^j)}\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} \left(\prod_{j=m}^{n-1} (1 - u^j)\right) \frac{u^{n-1}}{1 - u^{n-1}} \left{{n \atop m}\right} N_m\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} \left(\prod_{j=m}^{n-2} (1 - u^j)\right) u^{n-1} \left{{n \atop m}\right} N_m
\end{align} \).
But beyond here we run out of luck. The next step would be to set the sum for \( N_n \) in this and try to solve for a recurrence for the \( \mathrm{smag}_{n,j} \) and then try to come up with an explicit non-recursive formula for that, but it gets hairy and we don't have an expression for the expanded-out product there. So the first order of business here would be to find the explicit, non-recursive formula for the coefficients of
\( \prod_{j=m}^{n-2} (1 - u^j) \).
Any ideas? The degree of the resulting polynomial is \( \sum_{j=m}^{n-2} j = \frac{(n-1)(n-2) - m(m-1)}{2} \).
Also, \( N_1 = -1 \). We don't set it to 1, since if you look at the denominator formula, you'll notice it is equal to -1 there and we have \( \chi_1 = 1 \).
RE: Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. - mike3 - 03/28/2011
(03/20/2011, 03:45 AM)mike3 Wrote: But beyond here we run out of luck. The next step would be to set the sum for \( N_n \) in this and try to solve for a recurrence for the \( \mathrm{smag}_{n,j} \) and then try to come up with an explicit non-recursive formula for that, but it gets hairy and we don't have an expression for the expanded-out product there. So the first order of business here would be to find the explicit, non-recursive formula for the coefficients of
\( \prod_{j=m}^{n-2} (1 - u^j) \).
Any ideas? The degree of the resulting polynomial is \( \sum_{j=m}^{n-2} j = \frac{(n-1)(n-2) - m(m-1)}{2} \).
Also, \( N_1 = -1 \). We don't set it to 1, since if you look at the denominator formula, you'll notice it is equal to -1 there and we have \( \chi_1 = 1 \).
Add:
For this product, we can write
\( \prod_{j=m}^{n-2} (1 - u^j) = \sum_{j=m}^{\frac{(n-1)(n-2) - m(m-1)}{2}} R_{m,n-2,j} u^j \)
where \( R_{m,n,j} \) is another sequence of magic numbers defined for \( n \ge m \). To find the equations for \( R_{m,n,j} \), we use
\( P_{m,n} = \prod_{j=m}^{n} (1 - u^j) \)
then
\( P_{m,n} = (1 - u^n) P_{m,n-1} \).
Now, letting \( P_{m,n} = \sum_{j=0}^{\frac{n(n+1) - m(m-1)}{2}} R_{m,n,j} u^j \), we have
\(
\begin{align}
\sum_{j=0}^{\frac{n(n+1) - m(m-1)}{2}} R_{m,n,j} u^j &= (1 - u^n) \sum_{j=0}^{\frac{n(n-1) - m(m-1)}{2}} R_{m,n-1,j} u^j\\
&= \left(\sum_{j=0}^{\frac{n(n-1) - m(m-1)}{2}} R_{m,n-1,j} u^j\right) - \left(\sum_{j=0}^{\frac{n(n-1) - m(m-1)}{2}} R_{m,n-1,j} u^{j+n}\right)\\
&= \left(\sum_{j=0}^{\frac{n(n-1) - m(m-1)}{2}} R_{m,n-1,j} u^j\right) - \left(\sum_{j=n}^{\frac{n(n+1) - m(m-1)}{2}} R_{m,n-1,j-n} u^j\right)
\end{align}
\)
The last formula allows for equating coefficients, yielding a three-piece recurrence:
\( R_{m,n,j} = R_{m,n-1,j} \), for \( 0 \le j < n \)
\( R_{m,n,j} = R_{m,n-1,j} - R_{m,n-1,j-n} \), for \( n \le j \le \frac{n(n-1) - m(m-1)}{2} \)
\( R_{m,n,j} = -R_{m,n-1,j-n} \), for \( \frac{n(n-1) - m(m-1)}{2} < j \le \frac{n(n+1) - m(m-1)}{2} \)
with the appropriate initial conditions, e.g.
\( R_{m,m,0} = 1 \),
\( R_{m,m,j} = 0 \), for \( 0 < j < m \),
\( R_{m,m,m} = -1 \).
Not sure if this is of any use or helps in getting explicit coefficient formulas, though.
RE: Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. - mike3 - 03/28/2011
Going further, we can get recurrence formulas for \( \mathrm{smag}_{n,j} \). We have
\( N_n = \sum_{j=n-1}^{\frac{n(n-1)}{2}} \mathrm{smag}_{n,j} u^j \).
\( \begin{align}
\sum_{j=n-1}^{\frac{n(n-1)}{2}} \mathrm{smag}_{n,j} u^j &= \sum_{m=1}^{n-1} (-1)^{n-m} \left(\prod_{j=m}^{n-2} (1 - u^j)\right) u^{n-1} \left{{n \atop m}\right} N_m\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} u^{n-1} \left{{n \atop m}\right} \left(\prod_{j=m}^{n-2} (1 - u^j)\right) \left(\sum_{j=m-1}^{\frac{m(m-1)}{2}} \mathrm{smag}_{m,j} u^j\right)\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} u^{n-1} \left{{n \atop m}\right} \left(\sum_{j=0}^{\frac{(n-1)(n-2) - m(m-1)}{2}} R_{m,n-2,j} u^j\right) \left(\sum_{j=m-1}^{\frac{m(m-1)}{2}} \mathrm{smag}_{m,j} u^j\right)\\
&= \sum_{m=1}^{n-1} (-1)^{n-m} \left{{n \atop m}\right} \left(\sum_{j=n-1}^{\frac{n(n-1) - m(m-1)}{2}} R_{m,n-2,j-n+1} u^j\right) \left(\sum_{j=m-1}^{\frac{m(m-1)}{2}} \mathrm{smag}_{m,j} u^j\right)\\
\end{align} \).
Now consider all occurrences of \( u^j \) for a given j. That will be the recurrence for generating the \( \mathrm{smag} \). Let's see where that goes. We multiply the two sums together to get
\( \left(\sum_{j=n-1}^{\frac{n(n-1) - m(m-1)}{2}} R_{m,n-2,j-n+1} u^j\right) \left(\sum_{j=m-1}^{\frac{m(m-1)}{2}} \mathrm{smag}_{m,j} u^j\right) = \sum_{j=n+m-2}^{\frac{n(n-1)}{2}} \left(\sum_{k,l:\ k+l = j \\ n-1 \le k \le \frac{n(n-1) - m(m-1)}{2} \\ m-1 \le l \le \frac{m(m-1)}{2}} R_{m,n-2,k-n+1} \mathrm{smag}_{m,l}\right) u^j \).
Then we have
\( \sum_{j=n-1}^{\frac{n(n-1)}{2}} \mathrm{smag}_{n,j} u^j = \sum_{m=1}^{n-1} (-1)^{n-m} \left{{n \atop m}\right} \sum_{j=n+m-2}^{\frac{n(n-1)}{2}} \left(\sum_{k,l:\ k+l = j \\ n-1 \le k \le \frac{n(n-1) - m(m-1)}{2} \\ m-1 \le l \le \frac{m(m-1)}{2}} R_{m,n-2,k-n+1} \mathrm{smag}_{m,l}\right) u^j
\).
To get the coefficient for a given j, we note that the sum over j will only include that j when \( n + m - 2 \le j \), which means \( m \le j-n+2 \). So we get
\( \mathrm{smag}_{n,j} = \sum_{m=1}^{j-n+2} (-1)^{n-m} \left{{n \atop m}\right} \left(\sum_{k,l:\ k+l = j \\ n-1 \le k \le \frac{n(n-1) - m(m-1)}{2} \\ m-1 \le l \le \frac{m(m-1)}{2}} R_{m,n-2,k-n+1} \mathrm{smag}_{m,l}\right) \)
as the atrocious recurrence for the magic numbers. What to do with that?
(P.S. \( R_{m,n,j} \) when \( n < m \) should be 1)
RE: Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. - mike3 - 04/10/2011
Breaking news:
On this thread on sci.math:
http://groups.google.com/group/sci.math/browse_thread/thread/ef27fed70c64e91f?hl=en
I discussed what amounted to a special case of finding the coefficients \( R \) for the finite product in the formulas. Apparently, this does not have a known solution, and the solution for a related problem (partition numbers) looked to be extremely non trivial, involving sophisticated mathematics.
So it seems that for now, the binary-counting based formula will just have to do...
RE: Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. - tommy1729 - 04/10/2011
(04/10/2011, 08:33 PM)mike3 Wrote: Breaking news:
On this thread on sci.math:
http://groups.google.com/group/sci.math/browse_thread/thread/ef27fed70c64e91f?hl=en
I discussed what amounted to a special case of finding the coefficients \( R \) for the finite product in the formulas. Apparently, this does not have a known solution, and the solution for a related problem (partition numbers) looked to be extremely non trivial, involving sophisticated mathematics.
So it seems that for now, the binary-counting based formula will just have to do...
what about contour integrals ? euler expressed it as an n'th derivative and those can be given as contour integrals.
its not a sum though nor simple.
( btw as for p(n) being a fractal , i said that before. )
tommy1729
RE: Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. - mike3 - 05/09/2011
Meh, it looks like the whole approach of trying to directly find the "magic" numbers is insoluble. So it seems we're left with trying to simplify/"elegantize" the "ugly" binary formula in some other way.
Anyway, I noticed that that "binary" formula can be written simply as a sum over subsets of an interval of naturals (note that binary = indicator functions), giving a neater, more compact form:
\( a_1 = r_{1,1} \)
\( a_n = \sum_{m=1}^{n-1} r_{n,m} a_m \).
Then,
\( a_n = r_{1, 1} \sum_{1 = m_1 < m_2 < \cdots < m_k = n\\2 \le k \le n}\ \prod_{j=2}^k r_{m_j,m_{j-1}}, n > 1 \).
I didn't try a form like this before since I didn't consider it "explicit" enough for my liking
(I'm a fan of sums over straight indices, and I was hoping the straight-index form would help, but alas, no dice.) But this lets us write the Schroder coefficients as\( \chi_n =\ \sum_{1 = m_1 < m_2 < \cdots < m_k = n\\2 \le k \le n}\ \prod_{j=2}^k \frac{u^{m_j-1}}{1 - u_{m_j-1}} \frac{m_{j-1}!}{m_j!} \left{{m_j \atop m_{j-1}}\right}, n > 1 \).
We can eliminate the factorial quotient from the product since the product multiplies it to \( \frac{m_{k-1}! m_{k-2}! ... m_1!}{m_k! m_{k-1}! ... m_2!} = \frac{m_1!}{m_k!} = \frac{1}{n!} \), giving
\( \chi_n = \frac{1}{n!}\ \sum_{1 = m_1 < m_2 < \cdots < m_k = n\\2 \le k \le n}\ \prod_{j=2}^k \frac{u^{m_j-1}}{1 - u^{m_j-1}} \left{{m_j \atop m_{j-1}}\right}, n > 1 \).
A "simpler" formula for this would then mean one that sums over fewer terms and also has straight indices and no binary/subset/etc. stuff. This sums over \( 2^{n-2} \) terms. In theory, it should be possible to get it to \( \frac{n(n-1)}{2} \). How can we do this? The above is very general -- we can express Bernoulli numbers and what not in a similar form. But in that case, and in a lot of other cases, there exists a form with fewer terms, straight indices and no binary/subset/etc. stuff -- just some nested sums and products. Is that possible here as well? Is this formula already known somewhere?