Mathematics of Planet Earth

While struggling to prepare my talk on “what mathematicians can do”, I remembered this website pointed out by Tom Leinster:

• Mathematics of Planet Earth 2013.

The idea is to get lots of mathematicians involved in programs on these topics:

• Weather, climate, and environment
• Health, human and social services
• Planetary resources
• Population dynamics, ecology and genomics of species
• Energy utilization and efficiency
• Connecting the planet together
• Geophysical processes
• Global economics, safety and stability

There are already a lot of partner societies (including the American Mathematical Society) and partner institutes. I would love to see more details, but this website seems directed mainly at getting more organizations involved, rather than saying what any of them are going to do.

There is a call for proposals, but it’s a bit sketchy. It says:

A call to join is sent to the planet.

which makes me want to ask “From where?”

(That must be why I’m sitting here blogging instead of heading an institute somewhere. I never fully grew up.)

I guess the details will eventually become clearer. Does anyone know some activities that have been planned?

Energy, the Environment, and What Mathematicians Can Do (Part 1)

I’m preparing a talk to give at Hong Kong University next week. It’s only half done, but I could use your feedback on this part while I work on the rest:

• Energy, The Environment, and What Mathematicians Can Do.

So far it makes a case for why mathematicians should get involved in these issues… but doesn’t say what they can to help! That’ll be the second part. So, you’ll just have to bear with the suspense for now.

By the way, all the facts and graphs should have clickable links that lead you to online references. The links aren’t easy to see, but if you hover the cursor over a fact or graph, and click, it should work.

Network Theory (Part 1)

As a mathematician who has gotten interested in the problems facing our planet, I’ve been trying to cook up some new projects to work on. Over the decades I’ve spent a lot of time studying quantum field theory, quantum gravity, n-categories, and numerous pretty topics in pure math. My accumulated knowledge doesn’t seem terribly relevant to my new goals. But I don’t feel like doing a complete ‘brain dump’ and starting from scratch. And my day job still requires that I prove theorems.

Green Mathematics

I wish there were a branch of mathematics—in my dreams I call it green mathematics—that would interact with biology and ecology just as fruitfully as traditional mathematics interacts with physics. If the 20th century was the century of physics, while the 21st is the century of biology, shouldn’t mathematics change too? As we struggle to understand and improve humanity’s interaction with the biosphere, shouldn’t mathematicians have some role to play?

Of course, it’s possible that when you study truly complex systems—from a living cell to the Earth as a whole—mathematics loses the unreasonable effectiveness it so famously has when it comes to simple things like elementary particles. So, maybe there is no ‘green mathematics’.

Or maybe ‘green mathematics’ can only be born after we realize it needs to be fundamentally different than traditional mathematics. For starters, it may require massive use of computers, instead of the paper-and-pencil methods that work so well in traditional math. Simulations might become more important than proofs. That’s okay with me. Mathematicians like things to be elegant—but one can still have elegant definitions and elegant models, even if one needs computer simulations to see how the models behave.

Perhaps ‘green mathematics’ will require a radical shift of viewpoint that we can barely begin to imagine.

It’s also possible that ‘green mathematics’ already exists in preliminary form, scattered throughout many different fields: mathematical biology, quantitative ecology, bioinformatics, artificial life studies, and so on. Maybe we just need more mathematicians to learn these fields and seek to synthesize them.

I’m not sure what I think about this ‘green mathematics’ idea. But I think I’m getting a vague feel for it. This may sound corny, but I feel it should be about structures that are more like this:

than this:

I’ve spent a long time exploring the crystalline beauty of traditional mathematics, but now I’m feeling an urge to study something slightly more earthy.

Network Theory

When dreaming of grand syntheses, it’s easy to get bogged down in vague generalities. Let’s start with something smaller and more manageable.

Network theory, and the use of diagrams, have emerged independently in many fields of science. In particle physics we have Feynman diagrams:

In the humbler but more practical field of electronics we have circuit diagrams:

Throughout engineering we also have various other styles of diagram, such as bond graphs:

I’ve already told you about Petri nets, which are popular in computer science… but also nice for describing chemical reactions:

‘Chemical reaction networks’ do a similar job, in a more primitive way:

Chemistry shades imperceptibly into biology, and biology uses so many styles of diagram that an organization has tried to standardize them:

• Systems Biology Graphical Notation (SBGN) homepage.

SBGN is made up of 3 different languages, representing different visions of biological systems. Each language involves a comprehensive set of symbols with precise semantics, together with detailed syntactic rules how maps are to be interpreted:

1) The Process Description language shows the temporal course of biochemical interactions in a network.

2) The Entity Relationship language lets you to see all the relationships in which a given entity participates, regardless of the temporal aspects.

3) The Activity Flow language depicts the flow of information between biochemical entities in a network.

Biology shades into ecology, and in the 1950s, Howard T. Odum developed the ‘Energy Systems Language’ while studying tropical forests. Odum is now considered to be the founder of ‘systems ecology’. If you can get ahold of this big fat book, you’ll see it’s packed with interesting diagrams describing the flow of energy through ecosystems:

• Howard T. Odum, Systems Ecology: an Introduction, Wiley-Interscience, New York, 1983.

His language is sometimes called ‘Energese’, for short:

The list goes on and on, and I won’t try for completeness… but we shouldn’t skip probability theory, statistics and machine learning! A Bayesian network, also known as a “belief network”, is a way to represent knowledge about some domain: it consists of a graph where the nodes are labelled by random variables and the edges represent probabilistic dependencies between these random variables. Various styles of diagrams have been used for these:

And don’t forget neural networks!

What Mathematicians Can Do

It’s clear that people from different subjects are reinventing the same kinds of diagrams. It’s also clear that diagrams are being used in a number of fundamentally different ways. So, there’s a lot to sort out.

I already mentioned one attempt to straighten things out: Systems Biology Graphical Notation. But that’s not the only one. For example, in 2001 the International Council on Systems Engineering set up a committee to customize their existing Unified Modeling Language and create something called Systems Modeling Language. This features nine types of diagrams!

So, people are already trying to systematize the use of diagrams. But mathematicians should join the fray.

Why? Because mathematicians are especially good at soaring above the particulars and seeing general patterns. Also, they know ways to think of diagrams, not just as handy tools, but as rigorously defined structures that you can prove theorems about… with the help of category theory.

I’ve written a bit about diagrams already, but not their ‘green’ applications. Instead, I focused on their applications to traditional subjects like topology, physics, logic and computation:

• John Baez and Aaron Lauda, A prehistory of n-categorical physics, to appear in Deep Beauty: Mathematical Innovation and the Search for an Underlying Intelligibility of the Quantum World, ed. Hans Halvorson, Cambridge U. Press.

• John Baez and Mike Stay, A Rosetta stone: topology, physics, logic and computation, in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-174.

It would be good to expand this circle of ideas to include chemistry, biology, ecology, statistics, and so on. There should be a mathematical theory underlying the use of networks in all these disciplines.

I’ve started a project on this with Jacob Biamonte, who works on two other applications of diagrams, namely to quantum computation and condensed matter physics:

• Jacob D. Biamonte, Stephen R. Clark and Dieter Jaksch, Categorical tensor networks.

So far we’ve focused on one aspect: stochastic Petri nets, which are used to describe chemical reactions and also certain predator-prey models in quantitative ecology. In the posts to come, I want to show how ideas from quantum field theory be used in studying stochastic Petri nets, and how this relates to the ‘categorification’ of Feynman diagram theory.

This Week’s Finds (Week 309)

In the next issues of This Week’s Finds, I’ll return to interviewing people who are trying to help humanity deal with some of the risks we face.

First I’ll talk to the science fiction author and astrophysicist Gregory Benford. I’ll ask him about his ideas on “geoengineering” — proposed ways of deliberately manipulating the Earth’s climate to counteract the effects of global warming.

After that, I’ll spend a few weeks asking Eliezer Yudkowsky about his ideas on rationality and “friendly artificial intelligence”. Yudkowsky believes that the possibility of dramatic increases in intelligence, perhaps leading to a technological singularity, should command more of our attention than it does.

Needless to say, all these ideas are controversial. They’re exciting to some people — and infuriating, terrifying or laughable to others. But I want to study lots of scenarios and lots of options in a calm, level-headed way without rushing to judgement. I hope you enjoy it.

This week, I want to say a bit more about the Hopf bifurcation!

Last week I talked about applications of this mathematical concept to climate cycles like the El Niño – Southern Oscillation. But over on the Azimuth Project, Graham Jones has explained an application of the same math to a very different subject:

• Quantitative ecology, Azimuth Project.

That’s one thing that’s cool about math: the same patterns show up in different places. So, I’d like to take advantage of his hard work and show you how a Hopf bifurcation shows up in a simple model of predator-prey interactions.

Suppose we have some rabbits that reproduce endlessly, with their numbers growing at a rate proportional to their population. Let be the number of animals at time . Then we have:

where is the growth rate. This gives exponential growth: it has solutions like

To get a slightly more realistic model, we can add ‘limits to growth’. Instead of a constant growth rate, let’s try a growth rate that decreases as the population increases. Let’s say it decreases in a linear way, and drops to zero when the population hits some value . Then we have

This is called the “logistic equation”. is known as the “carrying capacity”. The idea is that the environment has enough resources to support this population. If the population is less, it’ll grow; if it’s more, it’ll shrink.

If you know some calculus you can solve the logistic equation by hand by separating the variables and integrating both sides; it’s a textbook exercise. The solutions are called “logistic functions”, and they look sort of like this:

The above graph shows the simplest solution:

of the simplest logistic equation in the world:

Here the carrying capacity is 1. Populations less than 1 sound a bit silly, so think of it as 1 million rabbits. You can see how the solution starts out growing almost exponentially and then levels off. There’s a very different-looking solution where the population starts off above the carrying capacity and decreases. There’s also a silly solution involving negative populations. But whenever the population starts out positive, it approaches the carrying capacity.

The solution where the population just stays at the carrying capacity:

is called a “stable equilibrium”, because it’s constant in time and nearby solutions approach it.

But now let’s introduce another species: some wolves, which eat the rabbits! So, let be the number of rabbits, and the number of wolves. Before the rabbits meet the wolves, let’s assume they obey the logistic equation:

And before the wolves meet the rabbits, let’s assume they obey this equation:

so that their numbers would decay exponentially to zero if there were nothing to eat.

So far, not very interesting. But now let’s include a term that describes how predators eat prey. Let’s say that on top of the above effect, the predators grow in numbers, and the prey decrease, at a rate proportional to:

For small numbers of prey and predators, this means that predation increases nearly linearly with both and . But if you have one wolf surrounded by a million rabbits in a small area, the rate at which it eats rabbits won’t double if you double the number of rabbits! So, this formula includes a limit on predation as the number of prey increases.

Okay, so let’s try these equations:

and

The constants 4 and 2 here have been chosen for simplicity rather than realism.

Before we plunge ahead and get a computer to solve these equations, let’s see what we can do by hand. Setting gives the interesting parabola

together with the boring line . (If you start with no prey, that’s how it will stay. It takes bunny to make bunny.)

Setting gives the interesting line

together with the boring line .

The interesting parabola and the interesting line separate the plane into four parts, so these curves are called separatrices. They meet at the point

which of course is an equilibrium, since there. But when this equilibrium occurs at a negative value of , and negative populations make no sense.

So, if there is no equilibrium population, and with a bit more work one can see the problem: the wolves die out. For larger values of there is an equilibrium population. But the nature of this equilibrium depends on : that’s the interesting part.

We could figure this out analytically, but let’s look at two of Graham’s plots. Here’s a solution when :

The gray curves are the separatrices. The red curve shows a solution of the equations, with the numbers showing the passage of time. So, you can see that the solution spirals in towards the equilibrium. That’s what you expect of a stable equilibrium.

Here’s a picture when :

The red and blue curves are two solutions, again numbered to show how time passes. The red curve spirals in towards the dotted gray curve. The blue one spirals out towards it. The gray curve is also a solution. It’s called a “stable limit cycle” because it’s periodic, and nearby solutions move closer and closer to it.

With a bit more work, we could show analytically that whenever there is a stable equilibrium. As we increase , when passes 3 this stable equilibrium suddenly becomes a tiny stable limit cycle. This is a Hopf bifurcation!

Now, what if we add noise? We saw the answer last week: where we before had a stable equilibrium, we now can get irregular cycles — because the noise keeps pushing the solution away from the equilibrium!

Here’s how it looks for with white noise added:

The following graph shows a longer run in the noisy case, with rabbits () in black and wolves () in gray. Click on the picture to make it bigger:

There is irregular periodicity — and as you’d expect, the predators tends to lag behind the prey. A burst in the rabbit population causes a rise in the wolf population; a lot of wolves eat a lot of rabbits; a crash in rabbits causes a crash in wolves.

This sort of phenomenon is actually seen in nature sometimes. The most famous case involves the snowshoe hare and the lynx in Canada. It was first noted by MacLulich:

• D. A. MacLulich, Fluctuations in the Numbers of the Varying Hare (Lepus americanus), University of Toronto Studies Biological Series 43, University of Toronto Press, Toronto, 1937.

The snowshoe hare is also known as the “varying hare”, because its coat varies in color quite dramatically. In the summer it looks like this:

In the winter it looks like this:

The Canada lynx is an impressive creature:

But don’t be too scared: it only weighs 8-11 kilograms, nothing like a tiger or lion.

Down in the United States, the same species lynx went extinct in Colorado around 1973 — but now it’s back!

• Colorado Division of Wildlife, Success of the Lynx Reintroduction Program, 27 September, 2010.

In Canada, at least, the lynx rely for the snowshoe hare for 60% to 97% of their diet. I suppose this is one reason the hare has evolved such magnificent protective coloration. This is also why the hare and lynx populations are tightly coupled. They rise and crash in irregular cycles that look a bit like what we saw in our simplified model:

This cycle looks a bit more strongly periodic than Graham’s graph, so to fit this data, we might want to choose parameters that give a limit cycle rather than a stable equilibrium.

But I should warn you, in case it’s not obvious: everything about population biology is infinitely more complicated than the models I’ve showed you so far! Some obvious complications: snowshoe hare breed in the spring, their diet varies dramatically over the course of year, and the lynx also eat rodents and birds, carrion when it’s available, and sometimes even deer. Some less obvious ones: the hare will eat dead mice and even dead hare when they’re available, and the lynx can control the size of their litter depending on the abundance of food. And I’m sure all these facts are just the tip of the iceberg. So, it’s best to think of models here as crude caricatures designed to illustrate a few features of a very complex system.

I hope someday to say a bit more and go a bit deeper. Do any of you know good books or papers to read, or fascinating tidbits of information? Graham Jones recommends this book for some mathematical aspects of ecology:

• Michael R. Rose, Quantitative Ecological Theory, Johns Hopkins University Press, Maryland, 1987.

Alas, I haven’t read it yet.

Also: you can get Graham’s R code for predator-prey simulations at the Azimuth Project.

---

Under carefully controlled experimental circumstances, the organism will behave as it damned well pleases. – the Harvard Law of Animal Behavior

Petri Nets

I’m trying to build bridges between mathematics and practical subjects like ecology and engineering — subjects that might help us save the planet.

As part of this, I have a project to explain how some ideas from electrical engineering, control theory, systems ecology, systems biology and the like can be formalized — and to some extent unified — using “symmetric monoidal categories”. Whenever you have a setup with:

• abstract gadgets that have ‘input wires’ and ‘output wires’,

and you can

• hook up these gadgets by connecting outputs to inputs,

and

• the wires can cross over each other, and

• it doesn’t matter whether one wire crosses over or under another

then you’ve probably got a symmetric monoidal category! For a precise definition, and lots of examples, try:

• John Baez and Mike Stay, Physics, topology, logic and computation: a Rosetta Stone, in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-174.

Back then I was excited about examples from ‘topological quantum field theory’, and ‘linear logic’, and ‘programming semantics’, and ‘quantum circuit theory’. But now I’m trying to come down to earth and think about examples of a more everyday nature. And they turn out to be everywhere!

For example, when you see these diagrams:

you may see a 10-watt amplifier with bass boost, and 16-volt power supply with power-on indicator light. But I see morphisms in symmetric monoidal categories!

Back in week296 I explained a symmetric monoidal category where the morphisms are electrical circuits made only from linear resistors. It’s easy to generalize this to ‘passive linear circuits’ where we include linear inductors and capacitors… and we can keep going further in this direction. I’m writing a paper on this stuff now.

But today I want to head in another direction, and tell you about something I’m beginning to work on with Jacob Biamonte: something called ‘Petri nets’.

Before I do, I have to answer a question that I can see forming in your forehead: what’s the use of this stuff?

I don’t actually think electrical engineers are going to embrace category theory — at least not until it’s routinely taught as part of college math. And I don’t even think they should! I don’t claim that category theory is going to help them do anything they want to do.

What it will do is help organize our understanding of systems made of parts.

In mathematics, whenever you see a pattern that keeps showing up in different places, you should try to precisely define it and study it — and whenever you see it showing up somewhere, you should note that fact. Eventually, over time, your store of patterns grows, and you start seeing connections that weren’t obvious before. And eventually, really cool things will happen!

It’s hard to say what these things will be before they happen. It’s almost not worth trying. For example, the first people who started trying to compute the perimeter of an ellipse could never have guessed that the resulting math would, a century or so later, be great for cryptography. The necessary chain of ideas was too long and twisty to possibly envision ahead of time.

But in the long run, having mathematicians develop and investigate a deep repertoire of patterns tends to pay off.

Petri nets – the definition

So: what’s a Petri net? Here’s my quick explanation, using graphics that David Tweed kindly provided for this article:

• Petri net, Azimuth Project.

A Petri net is a kind of diagram for the describing processes that arise in systems with many components. They were invented in 1939 by Carl Adam Petri — when he was 13 years old — in order to describe chemical reactions. They are a widely used model of concurrent processes in theoretical computer science. They are also used to describe interactions between organisms (e.g. predation, death, and birth), manufacturing processes, supply chains, and so on.

Here is an example from chemistry:

The circles in a Petri net denote so-called states, which in this example are chemical compounds. The rectangular boxes denote transitions, which in this example are chemical reactions. Every transition has a finite set of input states, with wires coming in from those, and a finite set of output states, with wires going out. All this information can equally well be captured by the usual notation for chemical reactions, as follows:

C + O₂ → CO₂

CO₂ + NaOH → NaHCO₃

NaHCO₃ + HCl → H₂O + NaCl + CO₂

One advantage of Petri nets is that we can also label each state by some number (0,1,2,3,…) of black dots, called tokens. In our example, each black dot represents a molecule of a given kind. Thus

describes a situation where one atom of carbon, one molecule of oxygen, one molecule of sodium hydroxide, and one molecule of hydrochloric acid are present. No molecules of any other kind are present at this time.

We can then describe processes that occur with the passage of time by moving the tokens around. If the carbon reacts with oxygen we obtain:

If the carbon dioxide combines with the sodium hydroxide to form sodium bicarbonate, we then obtain:

Finally, if the sodium bicarbonate and hydrochloric acid react, we get:

Note that in each case the following rule holds: for any given transition, we can delete one token for each of its input states and simultaneously add one token for each of its output states.

Here is a simpler example, taken from this article:

• Petri net, Wikipedia.

Here the transitions are denoted by black rectangles. This example is somewhat degenerate, because there no transitions with more than one input or more than one output. However, it illustrates the possibility of having more than one token in a given state. It also illustrates the possibility of a transition with no inputs, or no outputs. In chemistry this is useful for modelling a process where molecules of a given sort are added to or removed from the environment.

Symmetric monoidal categories

Now, what about symmetric monoidal categories? If you really want the definition, either read theRosetta Stone paper or the nLab article. For now, you can probably fake it.

A symmetric monoidal category is, very roughly, a category with a tensor product. If we ignore the tokens, a Petri net is a way of specifying a symmetric monoidal category by giving a set of objects and a set of morphisms between tensor products of these objects, for example

where denotes the tensor product of no objects. For example, the objects might be molecules and the morphisms might be chemical reactions; in this case the tensor product symbol is written ‘‘ rather than ‘‘.

The kind of symmetric monoidal category we get this way is a ‘free strict symmetric monoidal category’. It’s ‘free’ in the sense that it’s ‘freely generated’ from some objects and morphisms, without any relations. It’s ‘strict’ because we’re assuming the tensor product is precisely associative, not just associative ‘up to isomorphism’.

For more on how Petri nets describe free symmetric monoidal categories, see:

• Vladimiro Sassone, On the category of Petri net computations, 6th International Conference on Theory and Practice of Software Development, Proceedings of TAPSOFT ’95, Lecture Notes in Computer Science 915, Springer, Berlin, pp. 334-348.

Here Sassone describes a category of Petri nets and sketches the description of a functor from that category to the category of strict symmetric monoidal categories. Sassone also has some other papers on Petri nets and category theory.

As I mentioned, Petri nets have been put to work in many ways. I won’t even start trying to explain that today — for that, try the references on the Azimuth Project page. My only goal today was to convince you that Petri nets are a pathetically simple idea, nothing to be scared of. And if you happen to be a category theorist, it should also be pathetically simple to see how they describe free strict symmetric monoidal categories. If you’re not… well, never mind!

Quantum Information Processing 2011 (Day 2)

Here are some very fragmentary notes on the second day of QIP 2011. You can see arXiv references, slides, and videos of the talks here. I’ll just give links to the slides, and again I’ll only mention 3 talks.

Stephanie Werner gave a talk on the relation between the uncertainty principle and nonlocality in quantum theory. There’s a general framework for physical theories, called “generalized probabilistic theories”, which includes classical and quantum mechanics as special cases. In this framework we can see that while quantum theory is “nonlocal” in the sense made famous by John Bell, even more nonlocal theories are logically possible!

For example, while quantum theory violates the Clauser–Horn–Shimony–Holt inequality, which is obeyed by any local hidden variables theory, it doesn’t violate it to the maximum possible extent. There is a logically conceivable gadget, the Popescu–Rohrlich box, which violates the CHSH inequalities to the maximum extent allowed by a theory that prohibits faster-than-light signalling. However, such a gadget would give us implausibly godlike computational powers.

In Werner’s talk, she explained another reason not to hope for more nonlocality than quantum theory provides. Namely, given the “steering” ability we have in quantum theory — that is, our ability to prepare a state at one location by doing a measurement at another — the theory cannot be more nonlocal than it is while still obeying the uncertainty principle.

Jérémie Roland gave a talk on generalizations of Grover’s search algorithm. Grover’s algorithm is one of the implausibly godlike powers that quantum computers might give us, if only we could build the bloody things: it’s a way to search a list of N items for a given item in a time that’s only on the order of N^1/2. This algorithm assumes we can freely jump from place to place on the list, so instead of a linearly ordered “list” it’s probably better to visualize this data structure as a complete graph with N vertices. Roland’s talk explained a way to generalize this idea to arbitrary graphs.

He began by considering a Markov chain on the graph — that is, a way to blunder randomly from vertex to vertex along the graph, where you can only go from one vertex to another in one step if there’s an edge connecting them. He assumed that it’s reversible and ergodic. Then, starting from this, he described how to fashion a quantum process that finds the desired vertex (or vertices) in about the square root of the time that the Markov chain would take.

Robin Kothari gave a talk on using quantum computation to efficiently detect certain properties of graphs. He considered “minor-closed properties” of graphs. Let me just tell you what those properties are, and tell you about a fascinating older result about them.

The word graph means many slightly different things, but in this blog entry I mean a finite set whose elements are called vertices, together with a set of unordered pairs of distinct vertices, which we call edges. So, these are undirected finite graphs without self-loops or multiple edges connecting vertices.

A minor of a graph is another graph that can be obtained from the first one by repeatedly:

1) removing edges,

2) removing vertices that have no edges connected to them, and

3) contracting edges, that is, shrinking them to nothing and then identifying the vertices at both ends, like this:

For example, this graph:

is a minor of this one:

A property of graphs is minor-closed if whenever one graph has it, all its minors also have it.

What are some minor-closed properties? An obvious one is lacking cycles, that is, being a forest. You can get rid of cycles by getting rid of edges and vertices, or contracting edges, but you can’t create them!

A more interesting minor-closed property is planarity. If you can draw a graph on the plane, you can clearly also draw the graph you get by removing an edge, or removing a lone vertex, or contracting an edge.

Now, Kuratowski showed that planar graphs as precisely those that don’t have this graph:

or this one:

as minors.

Similarly, graphs that lack cycles are precisely those that don’t have a triangle as a minor!

So, we could ask if this pattern generalizes. Given a minor-closed property of graphs, is it equivalent to a property saying that there’s some finite set of graphs that don’t show up as minors?

This is called Wagner’s conjecture, after Klaus Wagner. He published it in 1970.

Wagner’s conjecture is true! It was proved by Neil Robertson and Paul Seymour in 2004. But the really interesting thing, to me, is that their proof takes about 400 or 500 pages!

I find this quite surprising… but then, I wouldn’t have guessed the four-color theorem was so hard to prove, either.

To make sure you understand Wagner’s conjecture, check that if we dropped the word “finite”, it would have a one-sentence proof.

This Week’s Finds (Week 308)

Last week we met the El Niño-Southern Oscillation, or ENSO. I like to explain things as I learn about them. So, often I look back and find my explanations naive. But this time it took less than a week!

What did it was reading this:

• J. D. Neelin, D. S. Battisti, A. C. Hirst et al., ENSO theory, J. Geophys. Res. 103 (1998), 14261-14290.

I wouldn’t recommend this to the faint of heart. It’s a bit terrifying. It’s well-written, but it tells the long and tangled tale of how theories of the ENSO phenomenon evolved from 1969 to 1998 — a period that saw much progress, but did not end with a neat, clean understanding of this phenomenon. It’s packed with hundreds of references, and sprinkled with somewhat intimidating remarks like:

The Fourier-decomposed longitude and time dependence of these eigensolutions obey dispersion relations familiar to every physical oceanographer…

Nonetheless I found it fascinating — so, I’ll pick off one small idea and explain it now.

As I’m sure you’ve heard, climate science involves some extremely complicated models: some of the most complex known to science. But it also involves models of lesser complexity, like the "box model" explained by Nathan Urban in "week304". And it also involves some extremely simple models that are designed to isolate some interesting phenomena and display them in their Platonic ideal form, stripped of all distractions.

Because of their simplicity, these models are great for mathematicians to think about: we can even prove theorems about them! And simplicity goes along with generality, so the simplest models of all tend to be applicable — in a rough way — not just to the Earth’s climate, but to a vast number of systems. They are, one might say, general possibilities of behavior.

Of course, we can’t expect simple models to describe complicated real-world situations very accurately. That’s not what they’re good for. So, even calling them "models" could be a bit misleading. It might be better to call them "patterns": patterns that can help organize our thinking about complex systems.

There’s a nice mathematical theory of these patterns… indeed, several such theories. But instead of taking a top-down approach, which gets a bit abstract, I’d rather tell you about some examples, which I can illustrate using pictures. But I didn’t make these pictures. They were created by Tim van Beek as part of the Azimuth Code Project. The Azimuth Code Project is a way for programmers to help save the planet. More about that later, at the end of this article.

As we saw last time, the ENSO cycle relies crucially on interactions between the ocean and atmosphere. In some models, we can artificially adjust the strength of these interactions, and we find something interesting. If we set the interaction strength to less than a certain amount, the Pacific Ocean will settle down to a stable equilibrium state. But when we turn it up past that point, we instead see periodic oscillations! Instead of a stable equilibrium state where nothing happens, we have a stable cycle.

This pattern, or at least one pattern of this sort, is called the "Hopf bifurcation". There are various differential equations that exhibit a Hopf bifurcation, but here’s my favorite:

Here and are functions of time, , so these equations describe a point moving around on the plane. It’s easier to see what’s going on in polar coordinates:

The angle goes around at a constant rate while the radius does something more interesting. When , you can see that any solution spirals in towards the origin! Or, if it starts at the origin, it stays there. So, we call the origin a "stable equilibrium".

Here’s a typical solution for , drawn as a curve in the plane. As time passes, the solution spirals in towards the origin:

The equations are more interesting for . Then whenever

This has two solutions, and . Since is a solution, the origin is still an equilibrium. But now it’s not stable: if is between and , we’ll have , so our solution will spiral out, away from the origin and towards the circle . So, we say the origin is an "unstable equilibrium". On the other hand, if starts out bigger than , our solution will spiral in towards that circle.

Here’s a picture of two solutions for :

The red solution starts near the origin and spirals out towards the circle . The green solution starts outside this circle and spirals in towards it, soon becoming indistinguishable from the circle itself. So, this equation describes a system where and quickly settle down to a periodic oscillating behavior.

Since solutions that start anywhere near the circle will keep going round and round getting closer to this circle, it’s called a "stable limit cycle".

This is what the Hopf bifurcation is all about! We’ve got a dynamical system that depends on a parameter, and as we change this parameter, a stable fixed point become unstable, and a stable limit cycle forms around it.

This isn’t quite a mathematical definition yet, but it’s close enough for now. If you want something a bit more precise, try:

• Yuri A. Kuznetsov, Andronov-Hopf bifurcation, Scholarpedia, 2006.

Now, clearly the Hopf bifurcation idea is too simple for describing real-world weather cycles like the ENSO. In the Hopf bifurcation, our system settles down into an orbit very close to the limit cycle, which is perfectly periodic. The ENSO cycle is only roughly periodic:

The time between El Niños varies between 3 and 7 years, averaging around 4 years. There can also be two El Niños without an intervening La Niña, or vice versa. One can try to explain this in various ways.

One very simple, general idea to add random noise to whatever differential equation we were using to model the ENSO cycle, obtaining a so-called stochastic differential equation: a differential equation describing a random process. Richard Kleeman discusses this idea in Tim Palmer’s book:

• Richard Kleeman, Stochastic theories for the irregularity of ENSO, in Stochastic Physics and Climate Modelling, eds. Tim Palmer and Paul Williams, Cambridge U. Press, Cambridge, 2010, pp. 248-265.

Kleeman mentions three general theories for the irregularity of the ENSO. They all involve the idea of separating the weather into "modes" — roughly speaking, different ways that things can oscillate. Some modes are slow and some are fast. The ENSO cycle is defined by the behavior of certain slow modes, but of course these interact with the fast modes. So, there are various options:

1. Perhaps the relevant slow modes interact with each other in a chaotic way.
2. Perhaps the relevant slow modes interact with each other in a non-chaotic way, but also interact with chaotic fast modes, which inject noise into what would otherwise be simple periodic behavior.
3. Perhaps the relevant slow modes interact with each other in a chaotic way, and also interact in a significant way with chaotic fast modes.

Kleeman reviews work on the first option but focuses on the second. The third option is the most complicated, so the pessimist in me suspects that’s what’s really going on. Still, it’s good to start by studying simple models!

How can we get a simple model that illustrates the second option? Simple: take the model we just saw, and add some noise! This idea is discussed in detail here:

• H. A. Dijkstra, L. M. Frankcombe and A.S von der Heydt, The Atlantic Multidecadal Oscillation: a stochastic dynamical systems view, in Stochastic Physics and Climate Modelling, eds. Tim Palmer and Paul Williams, Cambridge U. Press, Cambridge, 2010, pp. 287-306.

This paper is not about the ENSO cycle, but another one, which is often nicknamed the AMO. I would love to talk about it — but not now. Let me just show you the equations for a Hopf bifurcation with noise:

They’re the same as before, but with some new extra terms at the end: that’s the noise.

This could easily get a bit technical, but I don’t want it to. So, I’ll just say some buzzwords and let you click on the links if you want more detail. and are two independent Wiener processes, so they describe Brownian motion in the and coordinates. When we differentiate a Wiener process we get white noise. So, we’re adding some amount of white noise to the equations we had before, and the number says precisely how much. That means that and are no longer specific functions of time: they’re random functions, also known as stochastic processes.

If this were a math course, I’d feel obliged to precisely define all the terms I just dropped on you. But it’s not, so I’ll just show you some pictures!

If and , here are some typical solutions:

They look similar to the solutions we saw before for , but now they have some random wiggles added on.

(You may be wondering what this picture really shows. After all, I said the solutions were random functions of time, not specific functions. But it’s tough to draw a "random function". So, to get one of the curves shown above, what Tim did is randomly choose a function according to some rule for computing probabilities, and draw that.)

If we turn up the noise, our solutions get more wiggly. If and , they look like this:

In these examples, , so we would have a limit cycle if there weren’t any noise — and you can see that even with noise, the solutions approximately tend towards the limit cycle. So, we can use an equation of this sort to describe systems that oscillate, but in a somewhat random way.

But now comes the really interesting part! Suppose . Then we’ve seen that without noise, there’s no limit cycle: any solution quickly spirals in towards the origin. But with noise, something a bit different happens. If and we get a picture like this:

We get irregular oscillations even though there’s no limit cycle! Roughly speaking, the noise keeps knocking the solution away from the stable fixed point at , so it keeps going round and round, but in an irregular way. It may seem to be spiralling in, but if we waited a bit longer it would get kicked out again.

This is a lot easier to see if we plot just as a function of . Then we can run our solution for a longer time without the picture becoming a horrible mess:

If you compare this with the ENSO cycle, you’ll see they look roughly similar:

That’s nice. Of course it doesn’t prove that a model based on a Hopf bifurcation plus noise is "right" — indeed, we don’t really have a model until we’ve chosen variables for both and . But it suggests that a model of this sort could be worth studying.

If you want to see how the Hopf bifurcation plus noise is applied to climate cycles, I suggest starting with the paper by Dijkstra, Frankcombe and von der Heydt. If you want to see it applied to the El Niño-Southern Oscillation, start with Section 6.3 of the ENSO theory paper, and then dig into the many references. Here it seems a model with may work best. If so, noise is not required to keep the ENSO cycle going, but it makes the cycle irregular.

To a mathematician like me, what’s really interesting is how the addition of noise "smooths out" the Hopf bifurcation. When there’s no noise, the qualitative behavior of solutions jumps drastically at . For we have a stable equilibrium, while for we have a stable limit cycle. But in the presence of noise, we get irregular cycles not only for but also . This is not really surprising, but it suggests a bunch of questions. Such as: what are some quantities we can use to describe the behavior of "irregular cycles", and how do these quantities change as a function of and ?

You’ll see some answers to this question in Dijkstra, Frankcombe and von der Heydt’s paper. However, if you’re a mathematician, you’ll instantly think of dozens more questions — like, how can I prove what these guys are saying?

If you make any progress, let me know. If you don’t know where to start, you might try the Dijkstra et al. paper, and then learn a bit about the Hopf bifurcation, stochastic processes, and stochastic differential equations:

• John Guckenheimer and Philip Holmes, Nonlinear Oscillations, Dynamical Systems and Bifurcations of Vector Fields, Springer, Berlin, 1983.

• Zdzisław Brzeźniak and Tomasz Zastawniak, Basic Stochastic Processes: A Course Through Exercises, Springer, Berlin, 1999.

• Bernt Øksendal, Stochastic Differential Equations: An Introduction with Applications, 6th edition, Springer, Berlin, 2003.

Now, about the Azimuth Code Project. Tim van Beek started it just recently, but the Azimuth Project seems to be attracting people who can program, so I have high hopes for it. Tim wrote:

My main objectives to start the Azimuth Code Project were:

• to have a central repository for the code used for simulations or data analysis on the Azimuth Project,

• to have an online free access repository and make all software open source, to enable anyone to use the software, for example to reproduce the results on the Azimuth Project. Also to show by example that this can and should be done for every scientific publication.

Of less importance is:

• to implement the software with an eye to software engineering principles.

This less important because the world of numerical high performance computing differs significantly from the rest of the software industry: it has special requirements and it is not clear at all which paradigms that are useful for the rest will turn out to be useful here. Nevertheless I’m confident that parts of the scientific community will profit from a closer interaction with software engineering.

So, if you like programming, I hope you’ll chat with us and consider joining in! Our next projects involve limit cycles in predator-prey models, stochastic resonance in some theories of the ice ages, and delay differential equations in ENSO models.

And in case you’re wondering, the code used for the pictures above is a simple implementation in Java of the Euler scheme, using random number generating algorithms from Numerical Recipes. Pictures were generated with gnuplot.

---

There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies. – C.A.R. Hoare