Constructing the "analytical" formula for tetration.  Printable Version + Tetration Forum (https://math.eretrandre.org/tetrationforum) + Forum: Tetration and Related Topics (https://math.eretrandre.org/tetrationforum/forumdisplay.php?fid=1) + Forum: Mathematical and General Discussion (https://math.eretrandre.org/tetrationforum/forumdisplay.php?fid=3) + Thread: Constructing the "analytical" formula for tetration. (/showthread.php?tid=576) Pages:
1
2

Constructing the "analytical" formula for tetration.  mike3  01/17/2011 Hi. I was wondering about the problem of finding "analytical" formulas for tetration, that is, formulas that are more like "formulas" than "procedures" to compute tetration. This includes, e.g. infinite sums and other things like that. A "closed form" formula, that is, one in terms of a finite number of "conventional" functions, is most likely not possible. Now, it seems the Riemann mappings so far are hugely resistant to attempts to describe them, so I was curious on concentrating on the simpler problem of describing the regular iteration, which is what the Riemann mappings would deform. The regular tetrational, or "unipolar superfunction" of , can be given by with recursivelygenerated coefficients . with the "complete" Bell polynomials. The above series is a Fourier series, but can be rearranged into a Taylor series if we so please: The problem, then, is the description of the coefficients . The first few are: ... By pattern recognition, it appears that . The denominator can be given in true closed form via the "qPochhammer symbol" as . (The appearance of qanalogs is curious. I'm wondering about the connections between qanalogs, tetration, iteration, fractals, chaos, and continuum sums...) The problem, however, is the sequence of "magic" numbers for the numerators. For j starting at 0, we get n = 1: 1 n = 2: 1 n = 3: 2, 1 n = 4: 6, 6, 5, 1 n = 5: 24, 36, 46, 40, 24, 9, 1 n = 6: 120, 240, 390, 480, 514, 416, 301, 160, 64, 14, 1 n = 7: 720, 1800, 3480, 5250, 7028, 8056, 8252, 7426, 5979, 4208, 2542, 1295, 504, 139, 20, 1 n = 8: 5040, 15120, 33600, 58800, 91014, 124250, 155994, 177220, 186810, 181076, 163149, 134665, 102745, 71070, 44605, 24550, 11712, 4543, 1344, 265, 27, 1 n = 9: 40320, 141120, 352800, 695520, 1204056, 1855728, 2640832, 3473156, 4277156, 4942428, 5395818, 5561296, 5433412, 5021790, 4391304, 3625896, 2820686, 2056845, 1398299, 879339, 504762, 260613, 117748, 45178, 13845, 3156, 461, 35, 1 n = 10: 362880, 1451520, 4021920, 8769600, 16664760, 28264320, 44216040, 64324680, 88189476, 114342744, 141184014, 166279080, 187614312, 202901634, 210825718, 210403826, 201934358, 186191430, 164980407, 140216446, 114231817, 88934355, 66047166, 46576620, 31071602, 19460271, 11365652, 6112650, 2987358, 1298181, 488878, 153094, 37692, 6705, 749, 44, 1 ... The first column appears to be factorials, i.e. , the last is of course , and the secondtolast looks to be but beyond that I'm not sure. Is there some way to actually prove or disprove these results from the recurrence formula, and even better, to get a "real" (perhaps a sum/product) formula for the coefficients ? What I'm really after here is some way to analyze that recurrence formula. How would one go about approaching such a problem? Also, for all its worth (I just plugged 1, 3, 18, 180, 2700 into the oeis.org dictionary.). For all that's worth. I don't know how you could decompose that in a "useful" manner. But again, no proofs, just guesses. RE: Constructing the "analytical" formula for tetration.  Gottfried  01/17/2011 Hi Mike  welcome in the club of patternmatcher... :) I've seen these coefficients in the inverse Schröderfunction for the dxp(x)iterates. I don't have it at hand and hope I recall it correct, but we had a thread in which I think Sheldon discussed that somehow complementary coefficients (which occur also in the noninverse Schröderfunction). which were to compare to that of yours again: I've had the same coefficients in my discussion of the Bellmatrix for dxp(x) (in my then notation Ut(x)) and its symbolic powers. Here we find that coefficients in the second column (the coefficents of Sheldon) and in the last column (your coefficients) of the Acoefficientsmatrix as shown in http://go.helmsnet.de/math/tetdocs/APT.htm . That they are from that columns corresponds to the fact, that the Schröderfunction is a scaling of the iterate of (positive) infinite height, so that only that of the second column remain significant, and that of the inverse Schröderfunction are that of the negative infinite height (this is just a guess, but accidentally seems to fit) which keep only that of the last column significant, because heights shift the columns down/upwards by construction. For a sketch see the following. I use the coefficientsmatrix A_4 at x^4 according to my mentioned paper. A_4 is and contains your coefficients of n=4 in the last column and the "complementary" in the second column. This is for height h=1. If we have height h=2 we get With increasing height that columns get accordingly shifted. From height h=5 on the columns are strictly"separated", the rowsums consist only on the entries of one column only. In the limit of height infinity only the last column is significant (if the log of the base is u>1) or the second (if the log of the base is u<1), so in the Schröderfunction we rediscover only the coefficients of that column. Sorry I've no time to go into more detail here at the moment, but I hope it is understandable so far. I didn't find any simpler construction for that coefficents than just this  a construction of R. Mathar, which I described elsewhere in the forum used only the Stirlingnumbers but was also iterative and thus had the same complexity for the computation. The coefficients can also be found by solving linear equationsystems using that columnshifting depending on the heightparameter and the hypothesis of even divisibility by the denominator at integer hights. (I did some sketches for that solution but got tired so didn't make it a full explicite procedure) The relation to the qanalogues is very striking; however precisely this relation makes me skeptical, whether we are on the right track with the powerseries so far since exactly that qanalogues occured in an exercise of L.Euler, where he discussed another series for the logfunction and used that qanalogues in the denominator. However: that "log" was correct only on the integer exponents, but was a false log at fractional exponents... a striking analogy to our tetrational problems with fractional heights while integer heights are easy to handle. I discussed this in short with Henryk here in the forum (but without conclusive results); search for the terms "false logarithm" and I think also in sci.math or sci.research. (I'm currently much occupied with my two statistical courses so please excuse the short style of this msg and the missing references into the msgs of our forum here. Perhaps I can come back to this later in the week. Please ask any specific question anyway) Gottfried RE: Constructing the "analytical" formula for tetration.  mike3  01/22/2011 @Gottfried: That's interesting, your matrix seems to be related to the iteration of the decremented exponential. I'm thinking that perhaps that would be a better line of attack here. The regular Schroder function for the fixed point at 0 of a function with such a fixed point, i.e. is given by where the coefficients satisfy the recurrence where is the nth coefficient of the mth exponentiation (NOT iteration!) of (for iteration, it would be , and is too ambiguous here to be used), i.e. . For , i.e. the decremented exponential, we get, using the binomial theorem (here, is a Stirling number of the 2nd kind), . So, the recurrence is , which looks to be much more "linear" than the weird Bellpolynomials recurrence. Could it be possible to come up with an explicit formula for the ? Then the Lagrange inversion formula can be applied to obtain the inverse Schroder function , which then yields the coefficients of a Fourier series for the superfunction of the decremented exponential, which can be topoconjugated to the desired function (although it may be offset from the original, but at least we would have a formula with explicit, nonrecursive coefficients). ADD: I tried some expansions of those coefficients. I noticed that the numerators seemed to contain coefficients that look like the second column of your matrices (the 1, 5, 6, 5 thing). Could there be some simpler way to transform that second column into the last column? If so, then we might be able to extract a simpler formula from the explicit formula for once it is developed. RE: Constructing the "analytical" formula for tetration.  tommy1729  01/23/2011 well i was about to tell you your problem had a combinatorial interpretation similar to stirling numbers of the 2nd kind. seems you found that yourself. how about the Lyapunov exponent and schroeder summations in the classic page : http://tetration.org/Tetration/index.html maybe they help , or reduce ... on the other hand perhaps you know that page by heart and considered this before. RE: Constructing the "analytical" formula for tetration.  mike3  01/24/2011 (01/23/2011, 10:59 PM)tommy1729 Wrote: well i was about to tell you your problem had a combinatorial interpretation similar to stirling numbers of the 2nd kind. You mean the original problem? I'd be curious to hear more. Do you have a way to get a nonrecursive formula? And I've seen the site you linked to. It does not give nonrecursive coefficient formulas. RE: Constructing the "analytical" formula for tetration.  Gottfried  01/24/2011 Mike  without having it definite, I think that your recursive description should be the same as that in the eingenvalue/eigensystemcomputation in the APTarticle: it is just a simple procedure and works fast. I was as well looking for a simpler, nonrecursive description But I didn't find anything convincing. The only thing I found was that method which solves linear equation systems using the (u1)(u^21)...()  denominators and assumes that at integer heights the numerator must be evenly divisible by that denominator plus the assumption, that the first and last row of the coefficientsmatrices are the Stirlingnumbers first and second kind, respectively (or opposite). With this each coefficientmatrix can be determined separately, nonrecursive at least in the sense that the coefficientsmatrices (and thus the computation of their second and their last columns) are independent of each other. (Don't know whether the description of this in the mentioned APTarticle was too short/imprecise?) I didn't proceed there  it seemed to be too complicated and does not give an optimization over the efficient recursive procedure ; maybe you could find an improvement once the system of conditions is formally stated in terms of linear equations/matrixformula and thus possibly get a more explicite expression in terms of the "curlybraces" ;) only. Well, I'll give it another try myself today, but my emphasis on this has a bit cooled down, to be frank... Gottfried RE: Constructing the "analytical" formula for tetration.  mike3  01/28/2011 News: I may have just found a really complicated but "explicit" or "nonrecursive" formula for the solutions of a general recurrence sequence of the form , which these Schroder function coefficient equations belong to. It's not "nice", though, but it looks to work (no proof yet as it was found by pattern examination). If you want details, just ask. But at least it seems to show that an explicit formula exists, so that there may perhaps be a simpler, more "elegant" one. RE: Constructing the "analytical" formula for tetration.  Gottfried  01/28/2011 (01/28/2011, 03:12 AM)mike3 Wrote: News: I may have just found a really complicated but "explicit" or "nonrecursive" formula for the solutions of a general recurrence sequence of the formWow. If this is not uncomfortably much work then show this please. Perhaps it gives a bit more insight into the whole problem as well as into that of my special "hobby", the iterationseries... or at least some fresh idea. Gottfried RE: Constructing the "analytical" formula for tetration.  mike3  01/28/2011 Well, here goes... this is LONG! I'm going to also give an explanation of the derivation, since you were asking for more "insight" into the problem. OK, so you have the recurrence I gave. . If we expand a few terms, we get ... Looking at this, we see that the number of products in each is 1, 1, 2, 4, 8, ... , or for . It is possible to prove this by considering how the above process works: each sum adds together the previous terms, which are themselves sums, thus the number of products in that sum should equal the sum of the numbers of products in the previous terms. That is, Taking the forward difference of that last equation gives . This kind of difference equation has as solutions . We see that for the given initial conditions, i.e. and , for . Now, we move on to consider the number of factors in each product. Counting them, we see that n = 1: 1 n = 2: 2 n = 3: 2, 3 n = 4: 2, 3, 3, 4 n = 5: 2, 3, 3, 4, 3, 4, 4, 5 ... Looking at the formula, we see the nth term should be the concatenation (due to the sum) of the previous terms with their elements each incremented by 1 (due to the multiplication of a new factor.). That is, . (where the "+" are actually string concatenations. Formally, .) We can "refactor" this process by noting that the "increment" "distributes" over the concatenation, so . Now, we know that the previous term is also an "incremented concatenation" of the terms before it, thus if we decremented that term and then concatenated itself to that, we would have the concatenation of all terms before , and thus i.e. the sequence can be formed by taking the previous term, incrementing all its elements, and then concatenating it to the unincremented version, which is also easily observable from the pattern, but this gives a kind of "proof". Anyway, by looking at the dictionary of integer sequences at oeis.org, I found that these strings appear within the sequence of "binary weights of n", the number of 1 bits in an integer. Looking at it, it appears element j (first is j = 1) of is given by the number of 1 bits in . This can be written explicitly. Note that is a "lossy right shift" of (i.e. shift right k bits, knock off everything past the binary point, like the ">>" operation in the C programming language.). Then, we can get the kth bit (0th is the LSB) of as . The second term is a lossy right shift by k+1 bits followed by a left shift by 1 bit, which is like the right shift by k bits but with its LSB cleared. So we can add up all the bits in (thus giving the number of 1 bits) by . Taking and noting that the first and last bit are always 1 (by virtue of and note also that this is always odd as is even and is odd, and even + odd = odd), we get . These connections to binary made me wonder about whether or not this whole thing could be interpreted in terms of binary. I noticed that the are present at most only once in a product, i.e. there are no higherdegree factors. And the indices, for the nth term of our original sequence, range from 1 to n. So I thought that each product could be represented as a binary nxn matrix with 1bit elements, and we could look for patterns there. This led me to see part of, but not all of, the pattern. However, the most fruitful way of viewing it, I found, was to arrange the terms and factors like this: Code: r11 where the value of each term can be found by multiplying the columns' elements together and then adding up the results. We can now see an interesting alternating pattern... which looks like binary counting! We see that the factors appear and disappear as the bits of , which also explains the "number of 1 bits of " observation. The left indices of the in a product, then, are generated by acquiring the position of each one bit in , with the LSB counted as position 1, and putting them in numerical order for convenience. That is, . Now for the right indices. If we look at them, they look like (here, for the 5th term) Code: 11 The same "bit index" interpretation works here as well. Ignoring the last "1", these terms give the positions of 1 bits in . So, we have . Then, the notquitesymbolic but still "explicit" and "nonrecursive" formula is . RE: Constructing the "analytical" formula for tetration.  Gottfried  01/28/2011 (01/28/2011, 09:12 PM)mike3 Wrote: Well, here goes... this is LONG! I'm going to also give an explanation of the derivation, since you were asking for more "insight" into the problem. Very interesting! and not soo long at all. I cannot chew it instantly but I'll take my time tomorrow and on sunday to interprete and relate it to the matrixnotation. Now since I see that 2,3,3,4,3,4,4,5,... pattern and the stringconcatenation I get the impression that this might be one of the cases where the recursive description is replaced by an expansion back to the initial parameter(s), but where no obvious simplification is found  which would reflect my experience that I couldn't find a shorter description for the schrödercoefficients than by the explicite matrixeigendecomposition (for the triangular case). But well  this is just an impression by the first reading, perhaps it is completely false. Anyway  thanks so far. I'll try to understand everything next two days. Gottfried Upps: one question: the r's in this posts are the chi's of the earlier one? 