Breaking New Ground In The Quest For The "Analytical" Formula For Tetration.
#1
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/tetrationforu...42#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 \).


Attached Files
.pdf   ExplicitFormulaProofq.pdf (Size: 68.76 KB / Downloads: 849)
#2
(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.
#3
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)
#4
Breaking news:

On this thread on sci.math:
http://groups.google.com/group/sci.math/...e91f?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...
#5
(04/10/2011, 08:33 PM)mike3 Wrote: Breaking news:

On this thread on sci.math:
http://groups.google.com/group/sci.math/...e91f?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
#6
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 Smile (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?



Possibly Related Threads…
Thread Author Replies Views Last Post
  Divergent Series and Analytical Continuation (LONG post) Caleb 54 13,284 03/18/2023, 04:05 AM
Last Post: JmsNxn
  Pictures of some generalized analytical continuations Caleb 18 4,383 03/17/2023, 12:56 AM
Last Post: tommy1729
  f(x+y) g(f(x)f(y)) = f(x) + f(y) addition formula ? tommy1729 1 691 01/13/2023, 08:45 PM
Last Post: tommy1729
Question Formula for the Taylor Series for Tetration Catullus 8 4,463 06/12/2022, 07:32 AM
Last Post: JmsNxn
  There is a non recursive formula for T(x,k)? marraco 5 5,948 12/26/2020, 11:05 AM
Last Post: Gottfried
  Extrapolated Faá Di Bruno's Formula Xorter 1 5,841 11/19/2016, 02:37 PM
Last Post: Xorter
  Explicit formula for the tetration to base [tex]e^{1/e}[/tex]? mike3 1 6,951 02/13/2015, 02:26 PM
Last Post: Gottfried
  fractional iteration by schröder and by binomial-formula Gottfried 0 4,859 11/23/2011, 04:45 PM
Last Post: Gottfried
  simple base conversion formula for tetration JmsNxn 0 5,582 09/22/2011, 07:41 PM
Last Post: JmsNxn
  Change of base formula using logarithmic semi operators JmsNxn 4 14,782 07/08/2011, 08:28 PM
Last Post: JmsNxn



Users browsing this thread: 1 Guest(s)