• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. mike3 Long Time Fellow Posts: 368 Threads: 44 Joined: Sep 2009 03/20/2011, 03:45 AM (This post was last modified: 03/20/2011, 03:47 AM by mike3.) 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   ExplicitFormulaProofq.pdf (Size: 68.76 KB / Downloads: 288) mike3 Long Time Fellow Posts: 368 Threads: 44 Joined: Sep 2009 03/28/2011, 11:51 AM (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. mike3 Long Time Fellow Posts: 368 Threads: 44 Joined: Sep 2009 03/28/2011, 11:04 PM (This post was last modified: 03/29/2011, 03:37 AM by mike3.) 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) mike3 Long Time Fellow Posts: 368 Threads: 44 Joined: Sep 2009 04/10/2011, 08:33 PM 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... tommy1729 Ultimate Fellow Posts: 1,358 Threads: 330 Joined: Feb 2009 04/10/2011, 09:46 PM (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 mike3 Long Time Fellow Posts: 368 Threads: 44 Joined: Sep 2009 05/09/2011, 05:08 AM (This post was last modified: 05/10/2011, 01:06 AM by mike3.) 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? « Next Oldest | Next Newest »

 Possibly Related Threads... Thread Author Replies Views Last Post Recursive formula generating bounded hyper-operators JmsNxn 0 1,298 01/17/2017, 05:10 AM Last Post: JmsNxn Extrapolated Faá Di Bruno's Formula Xorter 1 1,825 11/19/2016, 02:37 PM Last Post: Xorter Explicit formula for the tetration to base $$e^{1/e}$$? mike3 1 2,659 02/13/2015, 02:26 PM Last Post: Gottfried Number theoretic formula for hyper operators (-oo, 2] at prime numbers JmsNxn 2 3,670 07/17/2012, 02:12 AM Last Post: JmsNxn fractional iteration by schröder and by binomial-formula Gottfried 0 2,432 11/23/2011, 04:45 PM Last Post: Gottfried simple base conversion formula for tetration JmsNxn 0 3,109 09/22/2011, 07:41 PM Last Post: JmsNxn Change of base formula using logarithmic semi operators JmsNxn 4 7,545 07/08/2011, 08:28 PM Last Post: JmsNxn Constructing the "analytical" formula for tetration. mike3 13 16,458 02/10/2011, 07:35 AM Last Post: mike3 One very important formula Ansus 7 9,733 11/03/2010, 04:21 AM Last Post: Ansus Alternate continuum sum formula? mike3 9 9,106 12/21/2009, 08:57 PM Last Post: mike3

Users browsing this thread: 1 Guest(s)