## Sunday, May 5, 2013

### Chaos Theory

I wrote this overview of chaos theory for a class, and figured I'd post it here.  It's written for the audience of my professor, but you can gloss over the more technical parts.  The first half is mostly a historical overview.

Chaos is a condition where a deterministic system, governed by a set of simple rules, can lead to erratic, seemingly random results.  This is because tiny variations in the starting conditions are amplified many times and become significant.  While this may seem like a logical thing, it was only recently discovered and accepted.  The history of science is about discovering the laws that govern the natural world, and it was long accepted that simple laws lead to simple consequences.  The idea of chaos as an innate property of natural systems was so revolutionary that even its discoverer avoided the idea.

Chaos theory was discovered largely by accident.  The story begins with the ancient Greek philosophers who came up with the term chaos as a contrast to cosmos, their name for order in the universe.  The word chaos meant an empty abyss that existed before creation.  The term was used at the start of the Bible which is translated to "without form and void" to describe the state of the universe before God created the world, and with it order.

In the late 16th century, Galileo developed his laws of motion.  These laws seemed to govern all the motion in the world.  This set off a series of discoveries of simple laws that explained a wide range of phenomena.  Galileo was followed by Kepler who came up with laws that very accurately described orbital mechanics.  Kepler described orbits as ellipses that had the planets speed up as they moved in closer to the Sun.  After Kepler, Newton arrived and drew the connection between earthly phenomenon and the heavenly movements of planets.  His insight was that the same set of laws described all motion.  The same force that pulled an object to the ground on Earth kept the Moon in orbit in space.

Newton also cast the die for all modern science.  He invented calculus as a tool to help explain the constant change that governs nature.  He came up with a differential equation that described all motion:
F = ma = m cdot {dv}/{dt} = m cdot {d^2s}/{dt^2}
where: F is force, m is mass, a is acceleration, v is velocity, s is displacement, and t is time.

Newton's few simple laws described the vast array of motion observed.  His technique of finding a differential equation to describe a system, and then integrating it was the prototype for science for hundreds of years.  With this technique scientists could predict future states based on known initial conditions.  Following Newton's lead gave rise to whole new fields: Fluid mechanics, elasticity theory, kinetic theory, thermodynamics, and electricity & magnetism are all examples of fields that resulted from Newton's way of doing science.

Newton published his blueprint for science, the Principia Mathematica, in 1687.  For the next 200 years it described all motion observed in the universe.  However, in the late 19th century flaws with Newtonian physics began to emerge.  One flaw was the fact that light could only exist as a propagation of a wave.  Yet, Newtonian physics said that on observer riding at the speed of light should see light standing still, but still oscillating as a wave.  Einstein explained this paradox by developing special relativity.  Special relativity said that time and length are relative, and not unchanging as dictated by Newton.  This was the first of three major challenges to Newton's world view of absolute laws.

The second challenge came from the study of electrons in the atom.  It was shown that electrons could only exist in discrete orbits.  When the electron changed from one orbit to another it made a quantum leap, never existing in the space between.  While these two revolutions took place early on in the 20th century, the third took longer to be accepted.

The story of the third revolution begins with the same orbital mechanics that were so instrumental in creating Newtonian physics to begin with.  Describing the orbit of one body around another is known as the two body problem.  The differential equation describing it was solved by Newton by converting it from a nonlinear to a linear problem.

The similar problem involving three bodies was, however, unsolved for many years.  Mathematicians eventually simplified the three body problem into a problem with two large bodies in a circular orbit, and a small particle-like third body.  This was known as the restricted circular three body problem.  Unfortunately, even the simplified problem proved intractable.

In the late 19th century a mathematician and physicist named Henri Poincaré attempted a novel, and largely geometric, solution to the three body problem.  He invented a concept called state space.  A state was all the information one needed to calculate the future of a system.  State space was the collection of all possible states.  Using state space, Poincaré could map a system and study its behavior from a fresh perspective.  Additionally, Newton's differential equation, F=ma, gives a vector field in state space.  This vector fields shows what an object at any given location will do from there.  By following the vector arrows one can start an object in state space and follow its path to learn how it will behave.

Poincaré attempted to plot the three body problem through state space but discovered a shocking revelation.  He found that the paths of the bodies crossed each other infinitely many times.  This meant that a given starting location had two possible paths that would lead to very different behaviors.  Which path a body would take depended on tiny variations in the exact starting location.  Here was a deterministic system where tiny changes to the initial conditions would lead to wildly different behaviors, the first glimpse of chaos.

Chaos theory is inherently interdisciplinary, and has seen application to a wide array of different problems in unrelated fields.  Fractals are a well known visualization of chaos.  The Mandelbrot set is the most well known fractal.  The rules for generating it are simple.  Begin with the complex number plane.  For any given complex number c in the plane, follow the iteration:
zn+1 = zn2 + c, with z0 = 0.  If this sequence remains bounded then c is a member of the Mandelbrot set.  By coloring the Mandelbrot set black against a white background one can see a border of infinite complexity.  Zooming in on any portion of the border only shows more complexity.  The difference between a number falling inside or outside the Mandelbrot set is infinitely small.

Fractals also show another sign of chaos.  When zooming in on the border, the same patterns appear at every level.  The same distinctive Mandelbrot shape is visible no matter how far one zooms in.  The same is true of other areas where chaos governs systems.  Graphs of heart rate variations and Internet traffic flow show the same overall pattern when one zooms in, a result of chaos.

The double pendulum is another simple example of chaos in action.  A pendulum is described exactly by Newton's F=ma.  Given the position and velocity of a pendulum one can predict exactly how it will behave in time.  Adding a second pendulum to the end of the first, however, brings chaos into the problem and makes it intractable.  When started from a high position, the double pendulum behaves erratically, with the second pendulum swinging around the first seemingly at random.  However, the double pendulum is governed by the same F=ma as the single variety.  It is simply a result of chaos that tiny imperceptible differences in the starting conditions lead to wildly different behaviors.

Another example of the practical benefits of chaos are cryptographic hashes which are used in storing passwords, and just about every other use of cryptography in computers.  Cryptographic hashes take a piece of data as an input and then output a small, random, but deterministic, key.  In effect, they give a fingerprint to data.  To be useful, they must have something called the avalanche effect, which says that any tiny change to the input should result in a large change to the output.  Changing a single bit in the input data will result in a totally different hash.  This allows hashes to serve as proof that data hasn't been tampered with.

Chaos theory had a long journey from a mythical concept, to something that was deemed to only represent the unknown aspects of nature, to an accepted innate quality of the universe.  The man considered to be the discoverer of chaos in its modern form, Poincaré, found the idea so shocking that he largely ignored it.  It was decades before his discovery would begin to turn up useful results.  However, it is now indisputable that chaos is a fact of nature.  Further, it is indisputable that chaos theory has been invaluable, having applications from weather prediction to computer security.  It deserves its title of the third revolution of the 20th century.