n-body problem

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/N-body_problem

In physics, the n-body problem is the problem of predicting the individual motions of a group of celestial objects interacting with each other gravitationally. Solving this problem has been motivated by the desire to understand the motions of the Sun, Moon, planets, and visible stars. In the 20th century, understanding the dynamics of globular cluster star systems became an important n-body problem. The n-body problem in general relativity is considerably more difficult to solve due to additional factors like time and space distortions.

The classical physical problem can be informally stated as the following:

Given the quasi-steady orbital properties (instantaneous position, velocity and time) of a group of celestial bodies, predict their interactive forces; and consequently, predict their true orbital motions for all future times.

The two-body problem has been completely solved and is discussed below, as well as the famous restricted three-body problem.

History

Knowing three orbital positions of a planet's orbit – positions obtained by Sir Isaac Newton from astronomer John Flamsteed – Newton was able to produce an equation by straightforward analytical geometry, to predict a planet's motion; i.e., to give its orbital properties: position, orbital diameter, period and orbital velocity. Having done so, he and others soon discovered over the course of a few years, those equations of motion did not predict some orbits correctly or even very well. Newton realized that this was because gravitational interactive forces amongst all the planets were affecting all their orbits.

The aforementioned revelation strikes directly at the core of what the n-body issue physically is: as Newton understood, it is not enough to just provide the beginning location and velocity, or even three orbital positions, in order to establish a planet's actual orbit; one must also be aware of the gravitational interaction forces. Thus came the awareness and rise of the n-body "problem" in the early 17th century. These gravitational attractive forces do conform to Newton's laws of motion and to his law of universal gravitation, but the many multiple (n-body) interactions have historically made any exact solution intractable. Ironically, this conformity led to the wrong approach.

After Newton's time the n-body problem historically was not stated correctly because it did not include a reference to those gravitational interactive forces. Newton does not say it directly but implies in his Principia the n-body problem is unsolvable because of those gravitational interactive forces. Newton said in his Principia, paragraph 21:

And hence it is that the attractive force is found in both bodies. The Sun attracts Jupiter and the other planets, Jupiter attracts its satellites and similarly the satellites act on one another. And although the actions of each of a pair of planets on the other can be distinguished from each other and can be considered as two actions by which each attracts the other, yet inasmuch as they are between the same, two bodies they are not two but a simple operation between two termini. Two bodies can be drawn to each other by the contraction of rope between them. The cause of the action is twofold, namely the disposition of each of the two bodies; the action is likewise twofold, insofar as it is upon two bodies; but insofar as it is between two bodies it is single and one ...

Newton concluded via his third law of motion that "according to this Law all bodies must attract each other." This last statement, which implies the existence of gravitational interactive forces, is key.

As shown below, the problem also conforms to Jean Le Rond D'Alembert's non-Newtonian first and second Principles and to the nonlinear n-body problem algorithm, the latter allowing for a closed form solution for calculating those interactive forces.

The problem of finding the general solution of the n-body problem was considered very important and challenging. Indeed, in the late 19th century King Oscar II of Sweden, advised by Gösta Mittag-Leffler, established a prize for anyone who could find the solution to the problem. The announcement was quite specific:

Given a system of arbitrarily many mass points that attract each according to Newton's law, under the assumption that no two points ever collide, try to find a representation of the coordinates of each point as a series in a variable that is some known function of time and for all of whose values the series converges uniformly.

In case the problem could not be solved, any other important contribution to classical mechanics would then be considered to be prizeworthy. The prize was awarded to Poincaré, even though he did not solve the original problem. (The first version of his contribution even contained a serious error.) The version finally printed contained many important ideas which led to the development of chaos theory. The problem as stated originally was finally solved by Karl Fritiof Sundman for n = 3 and generalized to n > 3 by L. K. Babadzanjanz and Qiudong Wang.

General formulation

The n-body problem considers n point masses m_i, i = 1, 2, …, n in an inertial reference frame in three dimensional space ℝ³ moving under the influence of mutual gravitational attraction. Each mass m_i has a position vector q_i. Newton's second law says that mass times acceleration m_i d²q_i/dt² is equal to the sum of the forces on the mass. Newton's law of gravity says that the gravitational force felt on mass m_i by a single mass m_j is given by

$${\displaystyle {\mathbf{F}}_{ij}=\frac{G{m}_i{m}_j}{{\Vert {\mathbf{q}}_j-{\mathbf{q}}_i\Vert }^2}\cdot \frac{\left({\mathbf{q}}_j-{\mathbf{q}}_i\right)}{\Vert {\mathbf{q}}_j-{\mathbf{q}}_i\Vert }=\frac{G{m}_i{m}_j\left({\mathbf{q}}_j-{\mathbf{q}}_i\right)}{{\Vert {\mathbf{q}}_j-{\mathbf{q}}_i\Vert }^3},}$$

where G is the gravitational constant and ‖q_j − q_i‖ is the magnitude of the distance between q_i and q_j (metric induced by the l₂ norm).

Summing over all masses yields the n-body equations of motion:

${\displaystyle m_i\frac{d^2{\mathbf{q}}_i}{d{t}^2}=\sum _{\genfrac{}{}{0ex}{}{j=1}{j\ne i}}^n\frac{G{m}_i{m}_j\left({\mathbf{q}}_j-{\mathbf{q}}_i\right)}{{\Vert {\mathbf{q}}_j-{\mathbf{q}}_i\Vert }^3}=-\frac{\mathrm{\partial }U}{\mathrm{\partial }{\mathbf{q}}_i}}$

where U is the self-potential energy

$${\displaystyle U=-\sum _{1\le i<j\le n}\frac{G{m}_i{m}_j}{\Vert {\mathbf{q}}_j-{\mathbf{q}}_i\Vert }.}$$

Defining the momentum to be p_i = m_i dq_i/dt, Hamilton's equations of motion for the n-body problem become

$${\displaystyle \frac{d{\mathbf{q}}_i}{dt}=\frac{\mathrm{\partial }H}{\mathrm{\partial }{\mathbf{p}}_i}\frac{d{\mathbf{p}}_i}{dt}=-\frac{\mathrm{\partial }H}{\mathrm{\partial }{\mathbf{q}}_i},}$$

where the Hamiltonian function is

$${\displaystyle H=T+U}$$

and T is the kinetic energy

$${\displaystyle T=\sum _{i=1}^n\frac{{\Vert {\mathbf{p}}_i\Vert }^2}{2m_i}.}$$

Hamilton's equations show that the n-body problem is a system of 6n first-order differential equations, with 6n initial conditions as 3n initial position coordinates and 3n initial momentum values.

Symmetries in the n-body problem yield global integrals of motion that simplify the problem. Translational symmetry of the problem results in the center of mass

$${\displaystyle \mathbf{C}=\frac{{\displaystyle \sum _{i=1}^n{m}_i{\mathbf{q}}_i}}{{\displaystyle \sum _{i=1}^n{m}_i}}}$$

moving with constant velocity, so that C = L₀t + C₀, where L₀ is the linear velocity and C₀ is the initial position. The constants of motion L₀ and C₀ represent six integrals of the motion. Rotational symmetry results in the total angular momentum being constant

$${\displaystyle \mathbf{A}=\sum _{i=1}^n{\mathbf{q}}_i\times {\mathbf{p}}_i,}$$

where × is the cross product. The three components of the total angular momentum A yield three more constants of the motion. The last general constant of the motion is given by the conservation of energy H. Hence, every n-body problem has ten integrals of motion.

Because T and U are homogeneous functions of degree 2 and −1, respectively, the equations of motion have a scaling invariance: if q_i(t) is a solution, then so is λ^−2/3q_i(λt) for any λ > 0.

The moment of inertia of an n-body system is given by

$${\displaystyle I=\sum _{i=1}^n{m}_i{\mathbf{q}}_i\cdot {\mathbf{q}}_i=\sum _{i=1}^n{m}_i{\Vert {\mathbf{q}}_i\Vert }^2}$$

and the virial is given by Q = 1/2 dI/dt. Then the Lagrange–Jacobi formula states that

$${\displaystyle \frac{d^{2}I}{d{t}^2}=2T-U.}$$

For systems in dynamic equilibrium, the longterm time average of ⟨d²I/dt²⟩ is zero. Then on average the total kinetic energy is half the total potential energy, ⟨T⟩ = 1/2⟨U⟩, which is an example of the virial theorem for gravitational systems. If M is the total mass and R a characteristic size of the system (for example, the radius containing half the mass of the system), then the critical time for a system to settle down to a dynamic equilibrium is

$${\displaystyle t_{\mathrm{c}\mathrm{r}}=\sqrt{\frac{GM}{R^3}}.}$$

Special cases

Two-body problem

Main article: Two-body problem

Any discussion of planetary interactive forces has always started historically with the two-body problem. The purpose of this section is to relate the real complexity in calculating any planetary forces. Note in this Section also, several subjects, such as gravity, barycenter, Kepler's Laws, etc.; and in the following Section too (Three-body problem) are discussed on other Wikipedia pages. Here though, these subjects are discussed from the perspective of the n-body problem.

The two-body problem (n = 2) was completely solved by Johann Bernoulli (1667–1748) by classical theory (and not by Newton) by assuming the main point-mass was fixed; this is outlined here. Consider then the motion of two bodies, say the Sun and the Earth, with the Sun fixed, then:

$${\displaystyle \begin{array}{rlrl}{m}_1{\mathbf{a}}_1& =\frac{G{m}_1{m}_2}{r_{12}^3}({\mathbf{r}}_2-{\mathbf{r}}_1)& & \text{Sun–Earth}\\ m_2{\mathbf{a}}_2& =\frac{G{m}_1{m}_2}{r_{21}^3}({\mathbf{r}}_1-{\mathbf{r}}_2)& & \text{Earth–Sun}\end{array}}$$

The equation describing the motion of mass m₂ relative to mass m₁ is readily obtained from the differences between these two equations and after canceling common terms gives:

$${\displaystyle \alpha +\frac{\eta }{r^3}\mathbf{r}=\mathbf{0}}$$

Where

• r = r₂ − r₁ is the vector position of m₂ relative to m₁;
• α is the Eulerian acceleration d²r/dt²;
• η = G(m₁ + m₂).

The equation α + η/r³r = 0 is the fundamental differential equation for the two-body problem Bernoulli solved in 1734. Notice for this approach forces have to be determined first, then the equation of motion resolved. This differential equation has elliptic, or parabolic or hyperbolic solutions.

It is incorrect to think of m₁ (the Sun) as fixed in space when applying Newton's law of universal gravitation, and to do so leads to erroneous results. The fixed point for two isolated gravitationally interacting bodies is their mutual barycenter, and this two-body problem can be solved exactly, such as using Jacobi coordinates relative to the barycenter.

Dr. Clarence Cleminshaw calculated the approximate position of the Solar System's barycenter, a result achieved mainly by combining only the masses of Jupiter and the Sun. Science Program stated in reference to his work:

The Sun contains 98 per cent of the mass in the solar system, with the superior planets beyond Mars accounting for most of the rest. On the average, the center of the mass of the Sun–Jupiter system, when the two most massive objects are considered alone, lies 462,000 miles from the Sun's center, or some 30,000 miles above the solar surface! Other large planets also influence the center of mass of the solar system, however. In 1951, for example, the systems' center of mass was not far from the Sun's center because Jupiter was on the opposite side from Saturn, Uranus and Neptune. In the late 1950s, when all four of these planets were on the same side of the Sun, the system's center of mass was more than 330,000 miles from the solar surface, Dr. C. H. Cleminshaw of Griffith Observatory in Los Angeles has calculated.

Real motion versus Kepler's apparent motion

The Sun wobbles as it rotates around the Galactic Center, dragging the Solar System and Earth along with it. What mathematician Kepler did in arriving at his three famous equations was curve-fit the apparent motions of the planets using Tycho Brahe's data, and not curve-fitting their true circular motions about the Sun (see Figure). Both Robert Hooke and Newton were well aware that Newton's Law of Universal Gravitation did not hold for the forces associated with elliptical orbits. In fact, Newton's Universal Law does not account for the orbit of Mercury, the asteroid belt's gravitational behavior, or Saturn's rings. Newton stated (in section 11 of the Principia) that the main reason, however, for failing to predict the forces for elliptical orbits was that his math model was for a body confined to a situation that hardly existed in the real world, namely, the motions of bodies attracted toward an unmoving center. Some present physics and astronomy textbooks do not emphasize the negative significance of Newton's assumption and end up teaching that his mathematical model is in effect reality. It is to be understood that the classical two-body problem solution above is a mathematical idealization. See also Kepler's first law of planetary motion.

Three-body problem

Main article: Three-body problem

This section relates a historically important n-body problem solution after simplifying assumptions were made.

In the past not much was known about the n-body problem for n ≥ 3. The case n = 3 has been the most studied. Many earlier attempts to understand the three-body problem were quantitative, aiming at finding explicit solutions for special situations.

• In 1687, Isaac Newton published in the Principia the first steps in the study of the problem of the movements of three bodies subject to their mutual gravitational attractions, but his efforts resulted in verbal descriptions and geometrical sketches; see especially Book 1, Proposition 66 and its corollaries (Newton, 1687 and 1999 (transl.), see also Tisserand, 1894).
• In 1767, Euler found collinear motions, in which three bodies of any masses move proportionately along a fixed straight line. The Euler's three-body problem is the special case in which two of the bodies are fixed in space (this should not be confused with the circular restricted three-body problem, in which the two massive bodies describe a circular orbit and are only fixed in a synodic reference frame).
• In 1772, Lagrange discovered two classes of periodic solution, each for three bodies of any masses. In one class, the bodies lie on a rotating straight line. In the other class, the bodies lie at the vertices of a rotating equilateral triangle. In either case, the paths of the bodies will be conic sections. Those solutions led to the study of central configurations, for which q̈ = kq for some constant k > 0.
• A major study of the Earth–Moon–Sun system was undertaken by Charles-Eugène Delaunay, who published two volumes on the topic, each of 900 pages in length, in 1860 and 1867. Among many other accomplishments, the work already hints at chaos, and clearly demonstrates the problem of so-called "small denominators" in perturbation theory.
• In 1917, Forest Ray Moulton published his now classic, An Introduction to Celestial Mechanics (see references) with its plot of the restricted three-body problem solution (see figure below). An aside, see Meirovitch's book, pages 413–414 for his restricted three-body problem solution.

Motion of three particles under gravity, demonstrating chaotic behaviour

Moulton's solution may be easier to visualize (and definitely easier to solve) if one considers the more massive body (such as the Sun) to be stationary in space, and the less massive body (such as Jupiter) to orbit around it, with the equilibrium points (Lagrangian points) maintaining the 60° spacing ahead of, and behind, the less massive body almost in its orbit (although in reality neither of the bodies are truly stationary, as they both orbit the center of mass of the whole system—about the barycenter). For sufficiently small mass ratio of the primaries, these triangular equilibrium points are stable, such that (nearly) massless particles will orbit about these points as they orbit around the larger primary (Sun). The five equilibrium points of the circular problem are known as the Lagrangian points. See figure below:

Restricted three-body problem

In the restricted three-body problem math model figure above (after Moulton), the Lagrangian points L₄ and L₅ are where the Trojan planetoids resided (see Lagrangian point); m₁ is the Sun and m₂ is Jupiter. L₂ is a point within the asteroid belt. It has to be realized for this model, this whole Sun-Jupiter diagram is rotating about its barycenter. The restricted three-body problem solution predicted the Trojan planetoids before they were first seen. The h-circles and closed loops echo the electromagnetic fluxes issued from the Sun and Jupiter. It is conjectured, contrary to Richard H. Batin's conjecture (see References), the two h₁ are gravity sinks, in and where gravitational forces are zero, and the reason the Trojan planetoids are trapped there. The total amount of mass of the planetoids is unknown.

The restricted three-body problem that assumes the mass of one of the bodies is negligible. For a discussion of the case where the negligible body is a satellite of the body of lesser mass, see Hill sphere; for binary systems, see Roche lobe. Specific solutions to the three-body problem result in chaotic motion with no obvious sign of a repetitious path.

The restricted problem (both circular and elliptical) was worked on extensively by many famous mathematicians and physicists, most notably by Poincaré at the end of the 19th century. Poincaré's work on the restricted three-body problem was the foundation of deterministic chaos theory. In the restricted problem, there exist five equilibrium points. Three are collinear with the masses (in the rotating frame) and are unstable. The remaining two are located on the third vertex of both equilateral triangles of which the two bodies are the first and second vertices.

Four-body problem

Inspired by the circular restricted three-body problem, the four-body problem can be greatly simplified by considering a smaller body to have a small mass compared to the other three massive bodies, which in turn are approximated to describe circular orbits. This is known as the bicircular restricted four-body problem (also known as bicircular model) and it can be traced back to 1960 in a NASA report written by Su-Shu Huang. This formulation has been highly relevant in the astrodynamics, mainly to model spacecraft trajectories in the Earth-Moon system with the addition of the gravitational attraction of the Sun. The former formulation of the bicircular restricted four-body problem can be problematic when modelling other systems than the Earth-Moon-Sun, so the formulation was generalized by Negri and Prado to expand the application range and improve the accuracy without loss of simplicity.

Planetary problem

The planetary problem is the n-body problem in the case that one of the masses is much larger than all the others. A prototypical example of a planetary problem is the Sun–Jupiter–Saturn system, where the mass of the Sun is about 1000 times larger than the masses of Jupiter or Saturn. An approximate solution to the problem is to decompose it into n − 1 pairs of star–planet Kepler problems, treating interactions among the planets as perturbations. Perturbative approximation works well as long as there are no orbital resonances in the system, that is none of the ratios of unperturbed Kepler frequencies is a rational number. Resonances appear as small denominators in the expansion.

The existence of resonances and small denominators led to the important question of stability in the planetary problem: do planets, in nearly circular orbits around a star, remain in stable or bounded orbits over time? In 1963, Vladimir Arnold proved using KAM theory a kind of stability of the planetary problem: there exists a set of positive measure of quasiperiodic orbits in the case of the planetary problem restricted to the plane. In the KAM theory, chaotic planetary orbits would be bounded by quasiperiodic KAM tori. Arnold's result was extended to a more general theorem by Féjoz and Herman in 2004.

Central configurations

Main article: Central configuration

A central configuration q₁(0), …, q_N(0) is an initial configuration such that if the particles were all released with zero velocity, they would all collapse toward the center of mass C. Such a motion is called homothetic. Central configurations may also give rise to homographic motions in which all masses moves along Keplerian trajectories (elliptical, circular, parabolic, or hyperbolic), with all trajectories having the same eccentricity e. For elliptical trajectories, e = 1 corresponds to homothetic motion and e = 0 gives a relative equilibrium motion in which the configuration remains an isometry of the initial configuration, as if the configuration was a rigid body. Central configurations have played an important role in understanding the topology of invariant manifolds created by fixing the first integrals of a system.

n-body choreography

Main article: n-body choreography

Solutions in which all masses move on the same curve without collisions are called choreographies. A choreography for n = 3 was discovered by Lagrange in 1772 in which three bodies are situated at the vertices of an equilateral triangle in the rotating frame. A figure eight choreography for n = 3 was found numerically by C. Moore in 1993 and generalized and proven by A. Chenciner and R. Montgomery in 2000. Since then, many other choreographies have been found for n ≥ 3.

Analytic approaches

For every solution of the problem, not only applying an isometry or a time shift but also a reversal of time (unlike in the case of friction) gives a solution as well.

In the physical literature about the n-body problem (n ≥ 3), sometimes reference is made to "the impossibility of solving the n-body problem" (via employing the above approach). However, care must be taken when discussing the 'impossibility' of a solution, as this refers only to the method of first integrals (compare the theorems by Abel and Galois about the impossibility of solving algebraic equations of degree five or higher by means of formulas only involving roots).

Power series solution

One way of solving the classical n-body problem is "the n-body problem by Taylor series".

We start by defining the system of differential equations:

$${\displaystyle \frac{d^2{\mathbf{x}}_i(t)}{d{t}^2}=G\sum _{\genfrac{}{}{0ex}{}{k=1}{k\ne i}}^n\frac{m_k\left({\mathbf{x}}_k(t)-{\mathbf{x}}_i(t)\right)}{{\left|{\mathbf{x}}_k(t)-{\mathbf{x}}_i(t)\right|}^3},}$$

As x_i(t₀) and dx_i(t₀)/dt are given as initial conditions, every d²x_i(t)/dt² is known. Differentiating d²x_i(t)/dt² results in d³x_i(t)/dt³ which at t₀ which is also known, and the Taylor series is constructed iteratively.

A generalized Sundman global solution

In order to generalize Sundman's result for the case n > 3 (or n = 3 and c = 0) one has to face two obstacles:

1. As has been shown by Siegel, collisions which involve more than two bodies cannot be regularized analytically, hence Sundman's regularization cannot be generalized.
2. The structure of singularities is more complicated in this case: other types of singularities may occur (see below).

Lastly, Sundman's result was generalized to the case of n > 3 bodies by Qiudong Wang in the 1990s. Since the structure of singularities is more complicated, Wang had to leave out completely the questions of singularities. The central point of his approach is to transform, in an appropriate manner, the equations to a new system, such that the interval of existence for the solutions of this new system is [0,∞).

Singularities of the n-body problem

There can be two types of singularities of the n-body problem:

• collisions of two or more bodies, but for which q(t) (the bodies' positions) remains finite. (In this mathematical sense, a "collision" means that two pointlike bodies have identical positions in space.)
• singularities in which a collision does not occur, but q(t) does not remain finite. In this scenario, bodies diverge to infinity in a finite time, while at the same time tending towards zero separation (an imaginary collision occurs "at infinity").

The latter ones are called Painlevé's conjecture (no-collisions singularities). Their existence has been conjectured for n > 3 by Painlevé (see Painlevé conjecture). Examples of this behavior for n = 5 have been constructed by Xia and a heuristic model for n = 4 by Gerver. Donald G. Saari has shown that for 4 or fewer bodies, the set of initial data giving rise to singularities has measure zero.

Simulation

Main article: n-body simulation

While there are analytic solutions available for the classical (i.e. nonrelativistic) two-body problem and for selected configurations with n > 2, in general n-body problems must be solved or simulated using numerical methods.

Few bodies

For a small number of bodies, an n-body problem can be solved using direct methods, also called particle–particle methods. These methods numerically integrate the differential equations of motion. Numerical integration for this problem can be a challenge for several reasons. First, the gravitational potential is singular; it goes to infinity as the distance between two particles goes to zero. The gravitational potential may be "softened" to remove the singularity at small distances:

$${\displaystyle U_{\epsilon }=\sum _{1\le i<j\le n}\frac{G{m}_i{m}_j}{\sqrt{{\Vert {\mathbf{q}}_j-{\mathbf{q}}_i\Vert }^2+{\epsilon }^2}}}$$

Second, in general for n > 2, the n-body problem is chaotic, which means that even small errors in integration may grow exponentially in time. Third, a simulation may be over large stretches of model time (e.g. millions of years) and numerical errors accumulate as integration time increases.

There are a number of techniques to reduce errors in numerical integration. Local coordinate systems are used to deal with widely differing scales in some problems, for example an Earth–Moon coordinate system in the context of a solar system simulation. Variational methods and perturbation theory can yield approximate analytic trajectories upon which the numerical integration can be a correction. The use of a symplectic integrator ensures that the simulation obeys Hamilton's equations to a high degree of accuracy and in particular that energy is conserved.

Many bodies

Direct methods using numerical integration require on the order of 1/2n² computations to evaluate the potential energy over all pairs of particles, and thus have a time complexity of O(n²). For simulations with many particles, the O(n²) factor makes large-scale calculations especially time-consuming.

A number of approximate methods have been developed that reduce the time complexity relative to direct methods:

• Tree code methods, such as a Barnes–Hut simulation, are spatially-hierarchical methods used when distant particle contributions do not need to be computed to high accuracy. The potential of a distant group of particles is computed using a multipole expansion or other approximation of the potential. This allows for a reduction in complexity to O(n log n).
• Fast multipole methods take advantage of the fact that the multipole-expanded forces from distant particles are similar for particles close to each other, and uses local expansions of far-field forces to reduce computational effort. It is claimed that this further approximation reduces the complexity to O(n).
• Particle mesh methods divide up simulation space into a three dimensional grid onto which the mass density of the particles is interpolated. Then calculating the potential becomes a matter of solving a Poisson equation on the grid, which can be computed in O(n log n) time using fast Fourier transform or O(n) time using multigrid techniques. This can provide fast solutions at the cost of higher error for short-range forces. Adaptive mesh refinement can be used to increase accuracy in regions with large numbers of particles.
• P³M and PM-tree methods are hybrid methods that use the particle mesh approximation for distant particles, but use more accurate methods for close particles (within a few grid intervals). P³M stands for particle–particle, particle–mesh and uses direct methods with softened potentials at close range. PM-tree methods instead use tree codes at close range. As with particle mesh methods, adaptive meshes can increase computational efficiency.
• Mean field methods approximate the system of particles with a time-dependent Boltzmann equation representing the mass density that is coupled to a self-consistent Poisson equation representing the potential. It is a type of smoothed-particle hydrodynamics approximation suitable for large systems.

Strong gravitation

In astrophysical systems with strong gravitational fields, such as those near the event horizon of a black hole, n-body simulations must take into account general relativity; such simulations are the domain of numerical relativity. Numerically simulating the Einstein field equations is extremely challenging and a parameterized post-Newtonian formalism (PPN), such as the Einstein–Infeld–Hoffmann equations, is used if possible. The two-body problem in general relativity is analytically solvable only for the Kepler problem, in which one mass is assumed to be much larger than the other.

Other n-body problems

Most work done on the n-body problem has been on the gravitational problem. But there exist other systems for which n-body mathematics and simulation techniques have proven useful.

In large scale electrostatics problems, such as the simulation of proteins and cellular assemblies in structural biology, the Coulomb potential has the same form as the gravitational potential, except that charges may be positive or negative, leading to repulsive as well as attractive forces. Fast Coulomb solvers are the electrostatic counterpart to fast multipole method simulators. These are often used with periodic boundary conditions on the region simulated and Ewald summation techniques are used to speed up computations.

In statistics and machine learning, some models have loss functions of a form similar to that of the gravitational potential: a sum of kernel functions over all pairs of objects, where the kernel function depends on the distance between the objects in parameter space. Example problems that fit into this form include all-nearest-neighbors in manifold learning, kernel density estimation, and kernel machines. Alternative optimizations to reduce the O(n²) time complexity to O(n) have been developed, such as dual tree algorithms, that have applicability to the gravitational n-body problem as well.

A technique in Computational fluid dynamics called Vortex Methods sees the vorticity in a fluid domain discretized onto particles which are then advected with the velocity at their centers. Because the fluid velocity and vorticity are related via a Poisson's equation, the velocity can be solved in the same manner as gravitation and electrostatics: as an n-body summation over all vorticity-containing particles. The summation uses the Biot-Savart law, with vorticity taking the place of electrical current. In the context of particle-laden turbulent multiphase flows, determining an overall disturbance field generated by all particles is an n-body problem. If the particles translating within the flow are much smaller than the flow's Kolmogorov scale, their linear Stokes disturbance fields can be superposed, yielding a system of 3n equations for 3 components of disturbance velocities at the location of n particles.

Pleistocene human diet

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Pleistocene_human_diet

The diet of known human ancestors varies dramatically over time. Strictly speaking, according to evolutionary anthropologists and archaeologists, there is not a single hominin Paleolithic diet. The Paleolithic covers roughly 2.8 million years, concurrent with the Pleistocene, and includes multiple human ancestors with their own evolutionary and technological adaptations living in a wide variety of environments. This fact with the difficulty of finding conclusive of evidence often makes broad generalizations of the earlier human diets very difficult. Our pre-hominin primate ancestors were broadly herbivorous, relying on either foliage or fruits and nuts and the shift in dietary breadth during the Paleolithic is often considered a critical point in hominin evolution. A generalization between Paleolithic diets of the various human ancestors that many anthropologists do make is that they are all to one degree or another omnivorous and are inextricably linked with tool use and new technologies. Nonetheless, according to the California Academy of Sciences, "Prior to about 3.5 million years ago, early humans dined almost exclusively on leaves and fruits from trees, shrubs, and herbs—similar to modern-day gorillas and chimpanzees."

Background

Hominin timeline
−10 — – −9 — – −8 — – −7 — – −6 — – −5 — – −4 — – −3 — – −2 — – −1 — – 0 —	Miocene Pliocene Pleistocene Hominini Nakalipithecus Ouranopithecus Oreopithecus Sahelanthropus Orrorin Ardipithecus Australopithecus H. habilis H. erectus H. heidelbergensis Homo sapiens Neanderthals Denisovans	← Earlier apes ← Gorilla split ← Chimpanzee split ← Earliest bipedal ← Earliest stone tools ← Dispersal beyond Africa ← Earliest fire / cooking ← Earliest rock art ← Earliest clothes ← Modern humans H o m i n i d s
(million years ago)

Due to the variety of environments inhabited, physiologies of the humans and human ancestors alive during the Paleolithic over 2.8 million years, we can’t ascribe a single set diet to any species, regional or cultural group. Larger brain sizes required a greater caloric intake. In colder climates meat might be necessary due to the decreased availability of plant based foods, and in hotter tropical climates a wider range of plants would be available.

Evolution of hominins

Main article: Human evolution

Recents estimates of the last common ancestors of humans and chimpanzees are around 12 million years ago. After this split the first bipedal hominins appeared around 4 million years ago in the genus Australopithecus.The first appearance of genus Homo takes place around 2.8 million years ago with Homo habilis, followed by Homo erectus at around 1.8 million years ago, Homo neanderthalensis by 400,000 years ago and finally the first appearance of Homo sapiens by 200,000 years ago. In each new species of hominin, particularly genus Homo there is a general trend of increasing brain size and decreasing dentition, these patterns are inextricably linked with an evolving diet.

Lines of evidence to uncover the diet of human ancestors

There are numerous difficulties in detecting and understanding the ancient diet of human ancestors. The Paleolithic begins around 2.6 million years ago and ends only around 12,000 years ago with the onset of the Holocene and Neolithic. The enormous time scale, variable environments inhabited by human ancestors and issues with preservation ensure that direct evidence is often very difficult to come by.

Evolutionary anthropologists who study the evolution of human origins and diet use a variety of methods to determine what human ancestors ate. As a starting point comparative analysis of the diets of humans closest living relatives, great apes such as chimpanzees, bonobos and other great apes, though these comparison are limited. Through environmental reconstruction of the areas ancient humans lived, inferences of available resources can be made. A common method of analysis is through the study of dentition and toothwear, as different foods will leave different markers that can be studied. There is also direct archaeological evidence, different types of tools would be used to process and consume different types of food and often be associated with faunal remains and evidence of fire. Human coprolites can also reflect direct evidence of diet.

More recent techniques have been introduced such as carbon isotopic analysis of recovered bones, which can be used as direct evidence of diet, and life history traits. An example would be the expensive tissue hypothesis, linking a decrease in gut size with an increase in brain size. Recently genetic studies of differences between Homo sapiens and other related hominins to determine adaptations related to diet.

Hominin diet before the Paleolithic

Generally speaking, inferring feeding adaptations in fossil hominins is not a simple task, and hence diet reconstructions have relied on diverse techniques (e.g. microwear, stable isotopes, functional morphology, etc.) that have provided different or even contradictory results. The direct predecessors to genus Homo, Australopithecus are thought to have broadly been frugivores or herbivores. The dental and jaw morphology of Australopithecus afarensis have often been assumed to indicate a diet of harder brittle foods, however tooth wear analysis from some specimen reflect a diet of tough grasses and leaves. This is corroborated by stable carbon isotopic evidence indicating the consumption of plants found along riversides and under tree cover. A recent study that analysed several hominin taxa has shown that they were probably no hard-food specialists, most likely relying on a softer diet.

Homo naledi, Homo habilis, Homo floresiensis and Homo erectus

Homo naledi

Almost half of H. naledi teeth have one or more chips on the enamel surface, caused by teeth coming into contact with hard foods or environmental grit during life. These antemortem enamel fractures are predominantly small and on the surfaces between molars, suggesting either a small hard dietary item was commonly consumed, or, more likely, environmental grit was incorporated into their diet when eating foods such as tubers. Two other studies support the suggestion that H. naledi consumed large quantities of small hard objects, most likely in the form of dust or grit. Crown shape supports this finding, with taller crowned and more wear resistant molars, potentially evolving to protect against abrasive particles. Microwear on the molars of H. naledi also suggests they regularly consumed hard and abrasive items. Overall, it is likely H. naledi differed substantial from other African fossil hominins in terms of diet, behaviour, or masticatory processing.

Homo habilis

By 3 million years ago the broad pattern of human dentition was in place with reduced canines and a jaw morphology implying heavier chewing. Stone tools and butchered animal remains dating to 2.6 million years ago have been found together in Ethiopia. This finding provides both the clearest evidence of meat eating by early human ancestors and the association of earliest stone tools with the butchering of animals for meat and marrow. This co-occurrence of stone tools is clearly linked with the butchering of animals and earliest identifiable appearances of Homo habilis. Tooth wear from Homo habilis indicates a relative lack of hard foods such as nuts, tubers or other hard brittle plant material being consumed. This is not to say that no tougher foods were eaten by H. habilis, only that it was likely not a regular part of the diet. By contrast, Homo erectus teeth generally reflect a much higher degree of wear, indicating tougher plant foods being eaten. While likely able to consume a variety of plant and animal resources, it seems that H. habilis was not able to exploit the wide array of resources and ecological niches its descendants would be able to.

Homo erectus

In contrast to Homo habilis, H. erectus left its ancestral environment of Africa and spread through much of the old world. Homo erectus appears to have avoided other large predators. Several interpretations of Homo erectus diet have been made, usually contrasting between primarily plant based foragers and scavengers or opportunistic hunters. However, as H. erectus dispersed across Eurasia some behaviors in some areas appear to have changed. The trajectory of diets between Homo habilis and Homo erectus can be described as a diversification of diet as Homo erectus spread within Africa and beyond into Asia. Meat played a critical role in the evolution of H. habilis, but as Homo erectus evolved the diet broadened to include tougher foods that H. habilis did not consume regularly. A broad diet alone however is not Homo erectus' sole contribution to evolution of the human lineage. Genetic evidence of reduced jaw muscles implies the adoption of cooking by humans prior to the branching of H. sapiens and H. neanderthalensis, placing the first use of fire for cooking firmly during the time of Homo erectus. Fire presents clear advantages to a species diet, in that cooking allows a greater range of foods to be eaten and improves the caloric content of both animal protein and plants. Another hypothesis is that H. erectus used tools to slice up their food even before they started to cook it, making it easier to chew.

Homo floresiensis

Homo floresiensis is thought to have diverged from humanity's ancestral branch prior to the evolution of Homo erectus. The direct ancestor of Homo floresiensis is currently thought to be Homo habilis, but this is subject to change with new information. Tooth wear from Homo floresiensis implies a tough, fibrous diet requiring powerful mastication. There is some evidence of meat eating associated with Homo floresiensis, but current evidence indicated that a plant based diet dominated. The specific plant species available to H. floresiensis is currently unknown. This complicates H. floresiensis relationship to H habilis, due to the latter’s association with intensive meat eating diet. That being the case, more than enough time passed for H. floresiensis diet to specialize to its given environment.

Homo heidelbergensis and Homo neanderthalensis

Homo heidelbergensis

Homo heidelbergensis, the likely predecessor of Homo neanderthalensis has few direct clues to its diet. Two adult incisors, likely from H. heidelbergensis have been found in England in an environment that at death would have been a spring fed wetland. The teeth themselves are heavily worn, implying heavy wear in the individual’s diet. Wooden spears dating to between 380,000 and 400,000 years BP were found in Germany, indicating that H. heidelbergensis was a big game hunter with sophisticated technology.

Homo neanderthalensis

Neanderthals were almost certainly effective hunters. Multiple sites associated with H. neanderthalensis also have the remains of butchered animals. More direct stable isotope evidence from Neanderthal bodies also indicates a heavy, though by no means exclusive reliance on animal protein. The degree to which Neanderthals rely on meat in their diet is extensively debated with contradictory evidence found often at very similar sites. Worn teeth from Neanderthal remains at a variety of sites imply use of plant and other abrasive foods, while other researchers find that Neanderthal tooth wear in general indicates a varied diet of both plants and meat. There is clear evidence of the consumption and processing of ancestors of wheat and barley by Neanderthals from starch analysis of dental calculus, while in Belgium, a species related to Sorghum was consumed along with other unknown plants. At the site of Shanidar in Iraq, in addition to the ancestors of wheat and barley, Homo neanderthalensis is known to have consumed dates, legumes and a variety other unknown plant species. In addition, evidence exists from the same teeth of Neanderthals to support the increased use of fire in their diet in addition to the wide variety of plant and animals in their diet. Evidence from Neanderthal coprolites from a Middle Paleolithic site in Spain support a diet of animal protein and plants at that site, though there is a lack of indicators for the consumption of starchy tubers. Neanderthals at El Sidron cave in Spain appear to have a more limited diet of meat when compared to other Neanderthal groups. In February 2019, scientists reported evidence, based on isotope studies, that at least some Neanderthals may have eaten meat. Nonetheless, instead of diet dominated by meat eating, the genetic and microbiological evidence from dental calculus implies reliance on mushrooms, pine nuts and a species of moss. The implications of this array of evidence is important due to the evidence that the “broad spectrum” of plant use is not unique to Homo sapiens. Homo neanderthalensis had, for all intents and purposes, a complex diet similar to many hunter-gather groups of Homo sapiens. The critical factor in this diet was that it varies significantly based on the local environment.

Homo sapiens

The evidence of early Homo sapiens diet stems from multiple lines of evidence, and there is a relative abundance of information due to both a larger relative population footprint and more recent evidence. A key contribution to early human diet likely was the introduction of fire to hominins toolkit. Some studies indicate a correlation with the introduction of fire and the reduction of tooth and gut size, going so far as to indicate their reduction as clear evolutionary indicators of the widespread introduction of fire.

A key difference between the diets of Homo sapiens and our closest extinct relatives H. neanderthalensis is the ability to effectively digest cooked starches, with some evidence found linking cooked starch and a further increase in H. sapiens brain size. Roots and tubers were introduced into the broader human diet, and can likely be assumed to be associated with fire as cooking would likely be necessary for many tubers to be digested. The use of root and tuber species in some Hunter Gatherer cultures makes up a critical component of diet. This is not only for the nutritional value of the species, but the relative annual stability of the species. This buffer effect would be important for many groups that relied on tubers. The ability to process starch is linked genetically to modern humans, with the genes necessary to its consumption not found in H. neanderthalensis. The timing of this mutation on modern humans is important as it means the ability to digest heavily starchy foods has only developed in the last 200ky years. In addition to the exploitation of tubers, another dietary innovation (this far) of Homo sapiens is the introduction of coastal and other marine resources. Some researchers have argued that the introduction of shellfish and other marine species play a significant role in the evolution of modern Homo sapiens.

By the upper Paleolithic, more complex tools and a higher proportion of meat in the human diet are assumed to correlate with an expansion of population in Europe. Though the diet of modern humans is not consistent through the Upper Paleolithic, from the Middle to Late Pleistocene there is a general shift in many areas towards a less abrasive diet. This is accompanied by changing technologies that would aid in the processing of abrasive plant species. Ethnographic comparisons with contemporary groups of Hunter Gatherers broadly imply a high reliance on animal protein supplemented with a wide range of available plant foods. While a reliance on animal protein is often seen as typical, it is by no means universal.

By the time of the Upper Paleolithic and modern Homo sapiens, not only was a wide variety of plants consumed, but a wide variety of animals, snails and fish. In order to exploit the many different species consumed, there was a wider variety of tools made than ever before available to humans. The shift to a higher quality diet and the technology to process a wide array of foods is reflected in modern humans by both the relatively larger brain size and reduction in gut size. The trend of larger brain size, the eating of animal protein, fire use and diversification of exploited foods is key to understanding the changing diets of human ancestors.

Cannibalism

Debates over the frequency of cannibalism in ancient humanity have been sporadic, usually erupting on the discovery of human with cut and break marks reflective of being processed as food. Evidence of cannibalism has been tied to both Homo sapiens and Homo neanderthalensis. Many theories of cannibalism amongst humans rely on a lack of available prey, crowding and fears of potential starvation. There are clear biological drawbacks of cannibalism including disease, and in addition instances of ritual cannibalism that have nothing to do with nutrition drawn from the ethnographic record. Evidence from Neanderthal remains in Belgium features cracked bones, cut marks and other indicators of processing for food. Notably, reindeer remains from the same site have the same types of butcher marks. The degree to which these remains reflect a ritual behavior, regular diet or isolated instances of dietary distress is not known.

Neolithic adaptations

The evolution of the human diet has not stopped since the end of the Paleolithic. Major functional adaptations have arisen in the last few thousand years as human technology has altered the environment. The most prevalent dietary adaptation since the Neolithic is lactase persistence, an adaptation that allows humans to digest milk. This adaptation appears roughly 4000 years ago in Europe. For populations more dependent on agriculture and domesticated animals, the importance of being able to add another edible resource should be noted.

General trends

Many specifics of the evolution of the human diet change regularly as new research and lines of evidence become available. Through the Paleolithic across the last 2.8 million years there has been a pattern of human and human ancestor’s biology adapting to an additionally available food source with resulting greater brain size, with the subsequent broadening and diversification of human diet. Homo habilis incorporated larger amounts of animal protein and fat into its diet, then as Homo erectus evolved it increased the breadth of its diet through fire and more advanced tool use. Homo sapiens in turn evolved the ability to consume cooked starch and marine life, which led to a further increase in brain size then greater technological diversification that ultimately allowed modern humans to adapt to a wide variety of ecological niches. The initial technological and biological adaptations each have knock on effects that allow a greater range of species to be used as food. This culminates in the Neolithic when suites of plants and animals are ultimately domesticated. In short, if there is a clear universal human Paleolithic diet, it is the use of fire to cook food.