All is Arithmetic
Stephen Wolfram asks in A New Kind of Science: Open Problems and Projects(pg. 36).
How can one extend recursive function definitions to continuous numbers? What is the continuous analog of the Ackermann function? The symbolic forms of the Ackermann function with a fixed first argument seem to have obvious interpretations for arbitrary real or complex values of the second argument. But is there a general way to extend these kinds of recursive definitions to continuous cases? Given a way to do this, how does it apply to recursive definitions like those on page 130? What happens to all the irregularities when one is between integer values? Or is it only possible to find simple continuous generalizations to functions that show fundamentally simple behavior? Can this be used as a characterization of when the behavior is simple?
I had two conversations with Wolfram on this topic almost twenty years ago and have spent considerable time contemplating and researching this area of thought since.
The Pythagorean ideal that all is number gave way to founding mathematics on logic in the nineteenth century and then set theory and category theory in the twentieth century. Partial differential equations, cellular automata, computer programs and category theory are examples of disciplines that physicists have used in the attempt to create a foundation for physics. Given the dependency of physics on mathematics and the demise of the Pythagorean ideal in mathematics, it is not surprising that arithmetic is not considered as a foundation of physics. But what if arithmetic is not complete? Addition, multiplication and exponentiation are only the first three arithmetic operators of an infinite series of operators that continue on with tetration, pentation, hexation and so forth. Taken together, these operators define the Ackermann function, but while addition, multiplication and exponentiation are defined for complex numbers, the Ackermann function is only defined for the whole numbers. The use of the Ackermann function is so limited that while the original Ackermann function has three variables, a search of the web shows that most people use a much more limited version with only two variables. The reason that the Ackermann function is so limited is that tetration, pentation and the higher arithmetic operators display chaotic behavior. There is a gigantic discontinuity between our ability to apply the exponential function to Lie algebras to produce Lie groups and the limitation of the higher operators to the natural numbers. Imagine the enormity of the lose if we lost all knowledge of the exponential function! Now imagine the possible difficulties if tetration was involved in fundamental physical processes like quantum mechanics or turbulence. Wouldn’t it be almost impossible to understand something based on arithmetic without understanding the underlying arithmetic itself?
In 1986 Stephen Wolfram pointed out that the problem of extending tetration to the complex numbers was actually part of the much larger and more important problem of unifying the discreet representation of chaotic systems in mathematics with the continuous representation of chaotic systems in physics, of unifying maps from iterated functions and flows from PDEs. He maintained that the duality prevented the derivation of mathematical solutions for continuous chaotic systems as are found in physics. My understanding of Wolfram’s position is that he was interested in the possibility that there might be a principle at play even deeper than the Principle of Equivalence and that it might be possible to formulate a single mathematical approach to dynamics encompassing iterated functions, cellular automata, PDEs, and recurrence equations. Wolfram suggested at if tetration could be defined for complex numbers then those results might be generalized to unify discrete maps and continuous flows. In 1990 I realized that the method I has discovered for defining tetration for complex numbers was not limited to tetration, but applied to iterated functions in the complex domain with a hyperbolic or irrationally neutral fixed point not at infinity.
While my work was never published, two different groups published works on the subject in 1998, at least one of which gives results experimentally consistent with my own research. References to related articles can be found on the dynamics page of my website - http://www.tetration.org/Dynamics/
Locating relevant research can be a challenge since this is not a well-defined area of science with standardized nomenclature; different authors may have a preference for the words recursive, iteration, dynamics, or flows. I will be referring to the extension of recursive function definitions to continuous numbers where chaotic behavior is displayed as continuous iteration; Lie groups are not discussed because they are not chaotic.
One general approach to defining continuous iteration is to use infinite matrices; one group of researchers uses Bell matrices while another uses the Carleman linearization. I have developed a second general approach using the Taylor series that also supports two different techniques; one technique is analytic (purely algebraic), while the other is a combinatorial technique. The infinite matrix approach begins with the recognition that composite functions can be represented by matrix multiplication where the functions are expressed in matrix form. To continuously iterate a function, use either Bell polynomials to form Bell matrices or the Carleman linearization to create an infinite matrix representation of the given function. Next transform the matrix into it’s diagonalized form. In general, only the integerial powers of matrices can found, but diagonalized matrices have the useful property that they can be raised to arbitrary non-integerial powers. Finally, apply the inverse of the transform used to diagonalize the matrix in order to obtain the infinite matrix from which the continuously iterated function can be recovered. Two groups of researchers have written about the Carleman linearization and a third group employee Bell polynomials. The Carleman linearization technique has the advantage of being a widely known and well understood. Also, what on the surface appears to be a limitation of the technique actually is an important validation; the Carleman linearization doesn’t work when the eigenvalues of the matrix are either zero or a root of unity; in dynamical terms this means that the technique only works for hyperbolic or irrationally neutral fixed points. This is vital because any valid quantitative theory of dynamics must be consistent with what is already known about the qualitative theory of dynamics, in this case what is known about topological conjugancy from the classification of fixed points. The classification of fixed points is to complex dynamics what the four classes of cellular automata are to NKS. The Bell matrix technique’s strength is that it provides insight into the combinatorial basis of iterated functions. A big advantage of these techniques is that their reliance on standard matrix operations makes them easy to implement in programming languages like Mathematica.
The other general approach involves finding the Taylor series of an iterated function at a fixed point. The analytic technique is purely algebraic and primarily involves the manipulation of nested summations. Each successive derivative reduces to a simple recurrence equation involving all of the lesser derivatives of the iterated function that have previously been determined. The combinatoric technique is based on the realization that the analytic technique implicitly uses the Bell polynomials. The Bell polynomials are the derivatives of composite functions and embody the combinatoric structure known as Bell numbers or set partitions. In the derivatives of iterated functions the partitioned sets are recursively partitioned into trees thereby generating the combinatoric structure most commonly known as Schroeder’s Fourth Problem - http://oeis.org/A000311.
Other names for this structure are total partitions, phylogenetic trees, or hierarchies. One of the central mysteries of complex systems is the ubiquitousness of hierarchical structures in the universe; could the combinatorial basis of continuous iteration be the explaination? Partitioning creates posets, in fact Comtet uses posets in defining Schroeder’s Fourth Problem and posets are important in discrete formulations of physics, both in quantum loop gravity -http://arxiv.org/abs/hep-th/9809161 - and NKS. Category theory, specifically combinatorial species - http://citeseer.ist.psu.edu/173949.html - can be used to apply analytic functors to the enumerated combinatorial structures. I use this to find the different derivatives of an iterated function at a fixed point allowing higher derivatives to be directly computed without first computing the derivatives of lesser degree. This approach is more general than the first approach; as an example, infinite matrices could be used in defining tetration for real numbers while the Taylor series approach is useful for defining tetration for complex numbers and preliminary work indicates even quaternions.
While the infinite matrix approach is consistent with the classification of fixed points for complex numbers, the Taylor series approach allows the classification of fixed points to be proved in a simpler and more unified manner than the topological approach currently used. Nested summations allow the handling of all Lyapunov characteristic numbers (Carleman linearization eigenvalues) including those that are zero or roots of unity. Of course the roots of unity are generators of finite groups. If the Taylor series coefficients are not matrices, then I suspect that the only additional types of fixed points appearing in higher dimensions will be associated with finite groups and that there is a deep connection between the classification of fixed points and the classification of finite groups. I have no insight as to what other types of fixed points might exist within the realm of non-communitive geometry.
Is the universe ultimately discrete or continuous? For complex functions the general solution in terms of nested summations is discrete, but except for the superattracting case, the specific cases simplify to continuous solutions. The solution of an equation expresses symmetries not found in the original equation; continuous iteration can’t be prohibited without prohibiting discrete iteration. I suggest that Langton’s observation that the most interesting phenomena seem to happen at the boundary of order and chaos has an analog in that interesting things occur at the interface between discrete and continuous phenomena; an example is my work with generating functions in combinatorics. Combinatorics is at the heart of discrete mathematics with generating functions being at the heart of combinatorics, yet if the first two terms of a series associated with either an ordinary or exponential generating function are zero and one, as is often the case, then the generating function can be continuously iterated in a particularly simple manner and the associated series from the continuously iterated generating function can be expressed by a series of polynomials. The clearest case of this is hierarchies of height n where combinatorist have derived the series of n for 2, -1, ½, 2, 3, and 4; the above technique gives a series of polynomials in terms of n consistent with previously known values. Even though articles on continuous iteration have been published since 1997, few researchers in dynamics seem to be aware of the sub-discipline. It maybe that the most important work in continuous iteration at this point is not forging into new areas, but displaying it’s connection to previously developed mathematics, as with combinatorics and the classification of fixed points, in order to establish it’s legitimacy.
Wolfram raises concerns about systems based on numbers that I believe that continuous iteration can mitigate. First, he is concerned that there are no internal constraints prohibiting solutions that are physically impossible when dealing with PDEs. My understanding is that extending continuous iteration to matrix functions would allow the modeling of any physically possible dynamical system. Instead of solving partial differential equations in terms of a general function, partial differential equations would be applied to a general dynamical system and solved perhaps by translating the PDE into a combinatorial problem. In Continuous iteration of dynamical maps - http://arxiv.org/abs/physics/9712026 - a general dynamical system representing a simplified version of the Navier-Stokes equation is studied. A more advanced version of this approach could possibly lend itself to either proving or disproving the Navier-Stokes equation; of course this approach could also be beset with it’s own intractable problems. I have also considered whether the zero values of the J function associated with the Riemann Zeta function couldn’t be expressed by a general dynamical system with the location of successive zeroes given by the dynamical system evaluated at successive increments of time. My focus on these problems has been to create a formulization of continuous iteration capable of attacking a wide variety of problems, not in actually solving those problems.
Is it possible that several of the Millennium Prize Problems -
http://www.claymath.org/millennium/ - are the front-end of a single larger problem? The Navier-Stokes Equations and Yang-Mills Theory are explicitly problems in dynamics, but dynamics are also important to the Riemann Hypothesis and the Poincaré Conjecture. I believe that there is ultimately a single bottleneck in our understanding of dynamics that manifests in numerous areas of mathematics and physics. I wonder what algebraic topology can do that a mature theory of continuous iteration couldn’t do. Wolfram suspects that there are other planets where physics and mathematics have initially been developed in terms of cellular automata instead of PDEs. I wonder whether there are other planets where continuous iteration has been discovered in their equivalent of our nineteenth century and where mathematics and physics evolved in a radically different and simpler manner than here.
Another issue Wolfram has with systems based on numbers is that, unlike cellular automata, they provide no natural way to catalog natural phenomena, but what he refers to as a continuous analog of the Ackermann function would serve that purpose. Using Conway notation, a→b→1 represents a^b, a→b→2 is a^^b or a tetrate b, and so on. Consider the expressions
a→1→2 = a, a→0→2 = 1, a→-1→2 = 0, a→-2→2 = -∞;
it is not even necessary to invoke a continuous analog of the Ackermann function to obtain odd results. Invoking negative numbers in the first parameter quickly leads to counter-intuitive behavior like
-1→0→3 = 1, -1→1→3 = -1, -1→2→3 = -1→-1→2 = 0, -1→3→3 = -1→(-1→2→3)→2 = -1→0→2 = 1. By similar reasoning -1→0→n = 1, -1→1→n = -1, -1→2→n = 0, -1→3→n = 1 for n>2.
Since iterated functions are central to the definition of the Ackermann function, the definition of a continuous Ackermann function is a corollary of defining continuous iteration; regrettably every definition of continuous iteration has some restriction. Tetration is typically represented as iterated exponentiation, but it is just as true that it is iterated logarithms; therefore a comprehensive definition of tetration would need to describe tetration’s Riemann surface. There may be instances when values of the continuous Ackermann function are undecidable when using the Taylor series approach because of its dependence on using fixed points for the center of the disk used for analytic continuation, although in Continuous time evolution from iterated maps and Carleman linearization - http://arxiv.org/abs/math-ph/0002044 - it is claimed that the Carleman linearization isn’t constrained by the use of a fixed point. My concern is that for higher arithmetic operators, there may be areas of the complex plane where no analytically convergent disk centered at a fixed point can be extended to, without first encountering a pole. I suspect that from the perspective of NKS it would be surprising if some values of the continuous Ackerman functions weren’t undecidable; in fact Cantor’s diagonalization method was used to show that the Ackermann function is not primitively recursive only a half decade before Godel used the diagonalization method to show that mathematics must contain undecidable statements.
Let’s consider an even more extreme version of a continuous Ackermann function. It immediately follows from the Taylor series approach to continuous iteration that complex numbers a and b exists such that a→b→c can be defined. I believe that this true not just for complex values of a and b, but for complex values of c as well. The Ackermann function is known for its hierarchy of operators that grow ever faster and faster. But for 1<= a <= 1.444 the opposite happens, the hierarchy of operators grow slower and slower until for a→∞→∞ = a nothing happens at all. I have listed the values of the square root of two tetrated, pentated, hexated, heptated, and octated to infinity - http://www.tetration.org/Ackermann/index.html that I derived in attempt to find experimental evidence that a→∞→x follows a logarithmic spiral into a→∞→∞, as happens in hyperbolic dynamics. Not only would this show a deeper dynamical self-consistency in the Ackermann function, but a→∞→x would provide the one piece of information that the Taylor series approach needs, the locations of the fixed points for a→x→n where n a fixed value representing an arbitrary arithmetic operator.
Consider the equation 2→x→2 = aleph_0, if k is a natural number including zero, then 2→(x+k)→2 = aleph_k. It seems to me that if the General Continuum Hypothesis were true then k would be constrained to the natural numbers and I would have a proof that tetration can’t even be defined for real numbers. On the other hand, it seems to me that a definition of tetration for complex numbers would force the General Continuum Hypothesis to be false.
Getting back to the idea of the Ackermann function as a catalog for systems based on numbers, among at least the first four arithmetic operators, each successive operator brings new phenomena into play. Multiplication adds the rational numbers, exponentiation the complex numbers, and tetration gives rise to chaos. The continuous Ackermann function is iterated continuous iteration; given that my work in continuous iteration is based in combinatorics founded in category theory, I wonder if a category theory approach to the continuous Ackermann function would then involve iterated categories or n-category theory; Baez and Dolan - http://arxiv.org/abs/math.QA/0004133 -conjecture that there is a deeper approach to arithmetic based on combinatorial species. One on my principle interest in computing the continuous Ackermann function is to have an experimental method to systematically explore new mathematical and possibly physical processes. It is not an accident that the two main applications of continuous iteration are general dynamical systems and arithmetic. A model of physics that can’t represent the fact that one object plus a second object of the same type are two objects isn’t very useful. The universe is comprised of a hierarchy of ever more complex systems; quarks, nucleons, atoms, molecules and so on. Could this be because physics is based on the Ackermann function with three continuous parameters with successive levels associated with successive arithmetic operators? Couldn’t evolution be a consequence of a completely continuous Ackermann function? I have hear it said that supersymmetry embodies all possible physical symmetries; it occurs to me that a continuous Ackermann function would embody symmetries, but not the symmetries found in group theory. Initially the idea seemed to be a contradictory, but since then I have learned that quasicrystals do exactly that. I also didn’t think that supersymmetry could be related to chaotic systems, but then found in the final chapter of Supersymmetry in Disorder and Chaos that the book’s author raises the issue of why supersymmetry is useful in the analysis of chaotic and disordered systems, stating that this is likely the result of a deep formal symmetry.
My attempts to identify a physical process based on tetration have focused on the Feynman Path Integral as the most likely candidate. I find the idea that quantum weirdness is a direct result of physics being based on arithmetic to be quite aesthetically pleasing. My experiments with iterated logarithms indicate another possible connection between tetration and quantum mechanics. Since the logarithm function is infinitely multivalued, the exponential map has an infinite number of repelling fixed points, one in each of the infinite periodic strips that map into the entire complex plane. Experimentally, I found that even when I forced the iterated logarithms to a repeated sequence of branches of the logarithm, that they quickly converged. In other words, instead of consistently using the principle branch, branch 2, 3, and 4 could be used to find a period three fixed point on each branch that returns to the same point on every third iteration. Now rotate the complex plane by ninety degrees and pretend that the distance between each strip is Planck’s length and that each strip represents a single point in a one dimensional quantum field theory. The way in which points in one strip are transported to a second strip models the sum of all paths phenomena seen in quantum field theory.
Addressing Wolfram’s final question about the recursive recurrence equations in 130, the only research that I have done with recurrence equations (beyond how to continuously iterated their generating functions) has been to investigate the normalcy of mathematical constants. Unfortunately, I don’t have any positive results to report, but the method of attack I used may be of interest to some people. Currently there is no approach capable of solving recurrence equations in general, much less the recursive recurrence equations that Wolfram is interested in, but I believe that continuous iteration provides a way to solve even these recursive recurrence equations. The central idea is whether a function exists in principle that can be applied to the n th value of a recurrence equation to obtain the n+1 th term. If the recurrence equation not irreversible, in other words, if the recurrence equation does not lose information, then it should be possible to determine how many iterations the process has gone though since it started and to model the system with a continuously iterated function. If the recurrence equation is irreversible, then the time could be tracked by moving from a one-dimensional system to a two dimensional system by applying the recurrence equation to a 2x2 matrix instead of a single number. Unfortunately as I have pointed out, all current approaches to continuous iteration operate under some type of constraint.
One of the most interesting applications of dynamics in recent years has been Bailey and Crandall’s work - http://mathworld.wolfram.com/NormalNumber.html - on one of the most important questions in mathematics, the normalcy of mathematical constants. Experimental results have for years indicated that the digits in mathematical constants like pi are random. Bailey and Crandall have found a way to represent the digits of a large class of mathematical constants in terms of the dynamics of a recurrence equation; for example they have found a way to directly compute the individual hexadecimal digits of pi so that the one-millionth digit of pi could be directly computed without computing any of the other digits. I felt that if the problem could be expressed in terms of continuous iteration then the normalcy of mathematical constants would follow. To deal with the mod 1 applied to the general recurrence equation and the fact that it was likely irreversible, I translated the recurrence equation into the complex domain by mapping the value of the recurrence equation into an angle and using the radial component to track the passage of time. The continuous iteration approach failed because the resulting system’s only fixed point was at infinity.
In wrapping up I would like to thank Stephen Wolfram and the people at Wolfram Science. I regret the necessity of the repeated use of the phrase I believe in this posting, but some important problems are so difficult that it is useful to record not just the sure knowledge of researchers but even their perspectives. I certainly appreciate that Stephen Wolfram has shared his thoughts in conversations and in NKS; I have found his guesses and perspective more useful than most people’s certain knowledge. I hope this posting helps raise the scientific community’s awareness of the interesting work that has been done on continuous iteration and that people give some thought to the limitations that an incomplete theory of arithmetic might have on physics. I believe that continuous iteration, in principle, can provide a single foundation for iterated functions, PDEs, recurrence equations and chaotic arithmetic; it may also be possible to add cellular automata to this list by extending Wolfram’s work with continuous cellular automata.
I suspect that before continuous iteration is embraced by the scientific mainstream it will need to have a big win; it needs to be successful in solving at least one important problem in math or physics. Continuous iteration’s utility in defining a continuous Ackermann function does little to promote continuous iteration because so few people care about the problem. I’ve spent almost no time on applying continuous iteration to the Riemann hypothesis, the Navier-Stokes equation, or the normalcy of mathematical constants; in the incredibly unlikely case that I discovered something useful, there would be no one to communicate my results to, because the methodology employed would not be taken seriously. I would be very interested in hearing Stephen Wolfram’s perspective on the potential significance and applications of continuous iteration. I believe that eventually continuous iteration will be considered extremely important in mathematics and physics, but the lack of papers following up on the initial research into continuous iteration indicate that without the support of a prominent scientist that little additional research will likely be done in the near future.