An Old Galactic Result
A cautionary tale
Karl Sundman was a Finnish mathematician who solved a major open problem in 1906. His solution would have been regarded as paradigm-“shifty” had it been a century or so earlier. It employed power series to represent the solutions of equations, namely the equations of the 3-body problem famously left unsolved by Isaac Newton. The tools of analysis needed to regard a convergent power series as defining a valid real number had been well accepted for a century, and the explicit giving of series and convergence proof even met the demands of mathematical constructivism of his day.
Today Ken and I want to explain why that problem is nevertheless still considered open, even though Sundman solved it over a hundred years ago.
This is a cautionary tale: For some problems there are solutions and there are solutions. There are solutions that make you famous and there are solutions that no one cares about. Unfortunately for Sundman his solution, which is correct mathematically, is the latter type; hence, his lack of fame—did you know about him? He did win honors from the top French and Swedish academies of science for this and other work in mechanics, and he has a Moon crater and an asteroid named for him.
His solution was generalized to any finite number of bodies in 1991 by Qiudong Wang of the University of Arizona, albeit with more restrictions on collisions and singularities than Sundman needed. All of this including Wang’s “beautiful paper” is surveyed in a great 1996 article for the Mathematical Intelligencer by Florin Diacu. We try to add a little more to what Diacu says from the perspective of our paradigms in computational complexity.
Complexity and Uselessness
There is another aspect to this tale: Sometimes impossibility theorems are not ironclad. Sundman solved a problem that had previously been shown to be “impossible.” This is another lesson for us—beware claims that something is impossible. It may not be.
Perhaps his solution failed for two reasons. It went against what was thought to be impossible, and it was useless. That is, the solution, in modern terms, did not yield a practical algorithm.
Ken and I like this tale, even though it is about an old result, a non-theory problem, because it sheds light onto problems that are dear to us in complexity theory. We have talked many times before about galactic algorithms—recall these are algorithms that are useless in practice. We have also talked before about impossibility results—we believe that some of these may not be ironclad. So what happened to Sundman over one hundred years ago is relevant to complexity theory today.
One more word about the following tale: Ken and I are not even amateurs in Sundman’s area of research so be careful to check what we say—another caution.
The Three Body Problem
The problem Sundman solved concerns the motion of three bodies under the sole force of gravity. In more detail, the problem is taking an initial set of data that specifies the positions, masses and velocities of three bodies for some particular point in time, and then determining the motions of the three bodies at a given future time. All of this must be in accord with the laws of Newtonian mechanics; relativity need not enter. It is a important problem: think sun, earth, and moon. The one-body problem is easy, while much of the two-body problem was solved by Johannes Kepler before Newton.
Simulating a system with bodies is not the issue. Subject to limitations of numerical precision and computing power, it is straightforward to apply the attractions and momenta of the bodies at each instant of time to calculate their positions at the next. Animations of particular -body cases are readily available, see here for instance. The issue is representing the positions after steps by a formula of , namely a “closed-form solution.”
Getting a closed-form solution is what we commonly mean by “solving” parameteric equations. At least that’s what Newton meant by solving when he posed the problem, and what others meant by offering prizes for . Newton could not solve it. Nor could anyone else. Let’s look and see why the great Newton failed—what was the roadblock that left the problem open?
An Impossibility Theorem
The obvious way to solve any problem is to look at the number of quantities that one needs to solve for. Then to get enough equations to allow a solution to be found. In linear systems this is easy: if there are unknowns, then in general one needs to have at least linear equations. Of course we may need more if the equations are not independent. The precise theorem is well known: To solve for quantities we need independent linear equations.
This can roughly be generalized to non-linear systems, like the three body problem. A natural approach is to try and find additional equations that can be added to the basic equations of motion. If enough equations can be found, even though the system is nonlinear, then it could be solved. This was tried for years by some of the best mathematicians of the 19th century, and later rigorized in analytic geometry as we know it today.
Finally, in 1887 Ernst Bruns and Henri Poincaré showed that there were not enough extra equations. More precisely, there were not enough extra conserved quantities that would yield enough equations. This leads to the “obvious” conclusion that there could be no analytic solution. For bodies there are quantities and only equations that meet a natural constraint of defining quantities called “integrals”—that is, constants of motion that are algebraic functions of positions and velocities alone, or integrals of such functions. Thus in the three-body case with this yields variables and only equations. The theorem is:
Theorem: There are only ten integrals, algebraic with respect to the time, position, and the velocities only of the bodies.
This is the “impossibility” result for the three-body problem. This barrier seems definitive because it concerns equations, and so trumps any issue of how real numbers are represented.
Yet Sundman was able to solve the three-body problem, by a completely different method. This shows that care must be used when discussing impossibility theorems. Bruns and Poincaré had really shown only that one kind of natural approach must fail. In modern terms this would be like showing that there is no fast algorithm of a special type for a certain problem. They did not rule out all possible algorithms. This why Sundman’s result is not in contradiction with the above impossibility theorem.
We are not the best place too explain what Sundman did. For more details, see Diacu’s article, this 1995 MAA Chauvenet Prize survey by Donald Saari involving complex variables, and also this recent term paper by Peter Senchyna, who is currently a physics undergraduate at the University of Washington.
Roughly speaking, Sundman used an analytic method to get a power series for the three body problem. The key issue then was, does the series converge for all time in the future? The problem is that the series will not converge for initial data that yields singularities. Sundaman used some nontrivial results to show that for generic data he could avoid singularities. The trouble arises from the fact that he uses several transformations that make the series converge slowly. That is, getting the value to any useful precision requires so many terms, that his solution is of little practical use. Or is it?
Is It Really Useless?
So why is Sundman’s result not famous? The answer seems to be that it is a galactic algorithm. He solves the problem by finding a convergent series that correctly predicts where the bodies will be in the future, but the convergence is galactically glacial. Our friends at Wikipedia state that to get a reasonable accuracy one would need to sum terms. That is obviously way too many.
The point we want to make is simple:
Who cares if the series converges slowly, there may be a fast way to get the same result…?
I wish we could show that Sundman series could be sped up tremendously. We cannot. But we can show that there are many examples of a slow series that looks useless, but can be summed quickly. For instance, so consider the sum
To get this to an error of say would require the summation of an astronomical number of terms. So should we give up? Of course not.
Leonhard Euler in 1735 proved the amazing result that
This means that your laptop can almost instantly compute the sum to the required accuracy not by summing the series but by computing . This is easy to do.
Getting the closed form for this series was called the Basel problem. It was first stated in 1644 by Pietro Mengoli, and worked on many top mathematicians. It became a famous open problem of the day. Euler’s solution was a shock that made him immediately famous.
Of course the three-body series may not be able to be sped up in this way. But maybe it can. It might even be possible to transform it analytically into another series for which any decimal place of the answer can be computed locally, in the manner we have covered of “spigot algorithms” for . This leads to two further observations:
- Such a fast series would probably be called the solution, eclipsing Sundman’s.
- Our notorious unsolved problems about complexity classes get involved when we approach the practicality of convergence in this way.
Still, the naive remark that the series itself converges too slowly may be no barrier at all. There are many other examples of slow series that can be computed via various tricks. Perhaps the three-body case is one of these. The slow convergence is not an ironclad impossibility theorem—not even close.
The obvious problem is to look at the series for the three body problem and see if we can apply methods to speed it up. Can we use any theory tricks to make the calculation go exponentially faster?