Skip to content

An Old Galactic Result

July 25, 2014


A cautionary tale

KarlSundmanS

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 {N} 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 {N \geq 3} 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 {N}-body cases are readily available, see here for instance. The issue is representing the positions after {t} steps by a formula of {t}, 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 {N \geq 3}. 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 {n} unknowns, then in general one needs to have at least {n} linear equations. Of course we may need more if the equations are not independent. The precise theorem is well known: To solve for {n} quantities we need {n} 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 {N} bodies there are {6N} quantities and only {10} 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 {N=3} this yields {18} variables and only {10} 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.

Sundman’s Result

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 {10^{8000}} 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

\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^{2}}.

To get this to an error of {2^{-1000}} 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

\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^{2}} = \frac{\pi^{2}}{6}.

This means that your laptop can almost instantly compute the sum to the required accuracy not by summing the series but by computing {\pi^{2}/6}. 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 {d} of the answer can be computed locally, in the manner we have covered of “spigot algorithms” for {\pi}. 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.

Open Problems

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?

About these ads
7 Comments leave one →
  1. July 25, 2014 12:31 pm

    Saari and Xia’s “Off to infinity in finite time” (1995) is another terrific survey on this topic.

    @article{Saari:1995aa, Author = {Saari, Donald G. and Xia, Zhihong}, Journal = {Notices Amer. Math. Soc.}, Number = {5}, Pages = {538--546}, Title = {Off to infinity in finite time}, Volume = {42}, Year = {1995}}

  2. July 25, 2014 3:25 pm

    my understanding is that there is some major link of this problem (3 body problem) to the new field of chaotic dynamics with findings of instability & which also relate to the solar system stability. there the lorentz equation is the prototypical case study. re galactic algorithms, an expanding subj esp in the modern age with mass TCS research scale. it seems one could write an entire book on the subj.

    but lets face it the concept of “closed form solution” is both expansive and a bit primitive. even simply finding roots of polynomials barely adhere to that right? also there is no “formula” for primes, except there are many, many algorithms. whats the difference? the distinction blurs an awful lot in the 21st century & probably will continue to blur.

  3. July 26, 2014 2:28 am

    I don’t think it is quite true to say that Kepler solved the 2-body problem before Newton. Kepler’s “solution” was observational, that is, obeyed by the sun and a planet to a relatively high degree of accuracy (based on Tycho Brahe’s data). Newton’s job was to find the equation which led to this solution, as he famously did.

  4. Clément Canonne permalink
    July 26, 2014 1:00 pm

    I must be missing something about the first “impossibity result”. Stated as it is, wouldn’t it suggest that even $2$-body problem is hopeless, as for $N=2$ you get 12 variables but only 10 integral equations?

    • Clément Canonne permalink
      July 26, 2014 5:44 pm

      My apologies for the two typos (“impossibility”, and “even the 2-body”)…

      • SamG permalink
        July 28, 2014 6:24 pm

        Yes I understand — with WordPress, it’s so annoying.

        To Dick and Ken: Would you please be able to install a “preview” button so that a poster can preview, before clicking on “Post Comment”? This would be ideal.

Trackbacks

  1. Laplace’s Demon | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,141 other followers