Apocalypse, Retreat or Revolution?

I’ve been enjoying this book:

• Tim Lenton and Andrew Watson, Revolutions That Made the Earth, Oxford U. Press, Oxford, 2011.

It’s mainly about the history of life on Earth, and how life has affected the climate and atmosphere. For example: when photosynthesis first started pumping a deadly toxic gas into the atmosphere—oxygen—how did life evolve to avoid disaster?

Or: why did most of the Earth freeze, about 650 million years ago, and what did life do then?

Or: what made 96% of all marine species and 70% of vertebrates on land die out, around 250 million years ago?

This is the book’s strength: a detailed but readable version of the greatest story we know, complete with mysteries yet to be solved. But at the end they briefly ponder the future. They consider various scenarios, lumped into three categories: apocalypse, retreat or revolution.

Apocalypse

They begin by reviewing the familiar story: how soaring population and fossil fuel usage is making our climate ever hotter, making our oceans ever more acidic, and sucking phosphorus and other nutrients out of ground and into the sea.

They consider different ways these trends could push the Earth into a new, inhospitable state. They use the term ‘apocalypse’. I think ‘disaster’ is better, but anyway, they write:

Even the normally cheerful and creative Jim Lovelock argues that we are already doomed, and nothing we can do now will stop the Earth system being carried by its own internal dynamics into a different and inhospitable state for us. If so, all we can do is try to adapt. We disagree—in our view the game is not yet up. As far as we can see no one has yet made a convincing scientific case that we are close to a global tipping point for ‘runaway’ climate change.

[…]

Yet even without truly ‘runaway’ change, the combination of unmitigated fossil fuel burning and positive feedbacks from within the Earth system could still produce an apocalyptic climate for humanity. We could raise global temperature by up to 6 °C this century, with more to come next century. On the way there, many parts of the Earth system could pas their own thresholds and undergo profound changes in state. These are what Tim [Lenton] and colleagues have called ‘tipping elements’ in the climate system.

They warrant a book by themselves, so we will just touch on them briefly here. The tipping elements include the great ice sheets covering Greenland and West Antarctica that are already losing mass and adding to sea level rise. In the tropics, there are already changes in atmospheric circulation, and in the pattern of El Niño events. The Amazon rainforest suffered severe drought in 2005 and might in the future face a climate drying-triggered dieback, destroying biodiversity and adding carbon to the atmosphere. Over India, an atmospheric brown cloud of pollution is already disrupting the summer monsoon, threatening food security. The monsoon in West Africa could be seriously disrupted as the neighboring ocean warms up. The boreal forests that cloak the northern high latitudes are threatened by warming, forest fires and insect infestation. The list goes on. The key point is that the Earth’s climate, being a complex feedback system, is unlikely to respond in an entirely smooth and proportional way to significant changes in energy balance caused by human activities.

Here is a map of some tipping elements. Click for more details:

Retreat

They write:

A popular answer to apocalyptic visions of the future is retreat, into a lower energy, lower material consumption, and ultimately lower population world. In this future world the objective is to minimize human effects on the Earth system and allow Gaia to reassert herself, with more room for natural ecosystems and minimal intervention in global cycles. The noble aim is long-term sustainability for for people as well as the planet.

There are some good and useful things we can take from such visions of the future, especially in helping to wean ourselves off fossil fuels, achieve greater energy efficiency, promote recycling and redefine what we mean by quality of life. However, we think that visions of retreat are hopelessly at odds with current trends, and with the very nature of what drives revolutionary changes of the Earth. They lack pragmatism and ultimately they lack ambition. Moreover, a retreat sufficient to forestall the problems outlined above might be just as bad as the problems it sought to avoid.

Revolution

They write:

Our alternative vision of the future is of revolution, into a high energy, high recycling world that can support billions of people as part of a thriving and sustainable biosphere. The key to reaching this vision of the future is to learn from past revolutions: future civilizations must be fuelled from sustainable energy sources, and they must undertake a greatly enhanced recycling of resources.

And here is where the lessons of previous ‘revolutions’ are especially useful. As I said last time, they list four:

1. The origin of life, before 3.8 billion years ago.

2. The Great Oxidation, when photosynthesis put oxygen into the atmosphere between 3.4 and 2.5 billion years ago.

3. The rise of complex life (eukaryotes), roughly 2 billion years ago.

4. The rise of humanity, roughly 0 billion years ago.

Their book argues that all three of the earlier revolutions disrupted the Earth’s climate, pushing it out of stability. It only restabilized after reaching a fundamentally new state. This new stable state could only be born after some new feedback mechanisms had developed.

For example, in every revolution, it has been important to find ways to recycle ‘wastes’ and make them into useful ‘resources’. This was true with oxygen during the Great Oxidation… and it must be true with our waste products now!

In any sort of approximate equilibrium state, there can’t be much ‘waste’: almost everything needs to be recycled. Serious amounts of ‘waste’ can only occur for fairly short periods of time, in the grand scheme of things. For example, we are now burning fossil fuels and creating a lot of waste CO₂, but this can’t go on forever: it’s only a transitional phase.

Apocalypse and Revolution?

I should talk about all this in more detail someday. But not today.

For now, I would just like to suggest that ‘apocalypse’ and ‘revolution’ are not really diametrically opposed alternatives. All three previous revolutions destroyed the world as it had been!

For example, when the Great Oxidation occurred, this was an ‘apocalypse’ for anaerobic life forms, who now struggle to survive in specialized niches here and there. It only seems like a triumphant ‘revolution’ in retrospect, to the new life forms that comfortably survive in the new world.

So, I think we’re headed for a combination of apocalypse and revolution: the death of many old things, and the birth of new ones. At best we have a bit of influence in nudging things in a direction we like. I don’t think ‘retreat’ is a real option: nostalgic though I am about many old things, time always pushes us relentlessly into new and strange worlds.

Major Transitions in Evolution

The changes we’re starting to go through now are so big that we need to step back and take a very long view to get any sort of handle on them. I’m struggling to do this now. This book has been very helpful:

• Tim Lenton and Andrew Watson, Revolutions That Made the Earth, Oxford U. Press, Oxford, 2011.

There’s a lot in it, and I’d love to tell you about all of it… but for now, let me just list 8 major transitions life on Earth may have gone through:

1. Compartments. This transition takes us from self-replicating molecules to self-replicating molecules in ‘compartments’—membranes of some sort. A compartment separates ‘self’ from ‘other’, and it’s crucial to life as we know it. When did this transition happen? Certainly after 4.4 billion years ago, when the Earth first got a solid crust. Probably after 3.85 billion years ago, when the Late Heavy Bombardment ended. Certainly before 3.3 billion years ago, when the earliest well-established microfossils are found. Probably before 3.8 billion years ago, which is the age of the Isua greenstone belt—a formation that contains graphite specks with less carbon-13 than average, a hint of life.

2. Groups of genes. This transition takes us from independent self-replicating molecules to self-replicating molecules linked into long chains, probably RNA. When did this happen? I have no idea; I’m not sure anyone does. Probably sometime between 4.4 and 3.3 billion years ago!

3. Genetic code. This transition takes us from a world where RNA both stored information and catalyzed reactions to a world where DNA stores the information used to build for proteins, which catalyze reactions. When did this happen? Again, probably sometime between 4.4 and 3.3 billion years ago!

4. Eukaryotes. This transition takes us from prokaryotes to eukaryotes. Prokaryotes, like bacteria and archaea, have relatively simple cells, like this:

Eukaryotes—like animals, plants, fungi and protists—have cells with lots of internal parts called organelles. Here are some things you might see in a eukaryotic cell:

It’s now believed some organelles were originally independent prokaryotes that got swallowed up but survived as symbiotic partners: so-called endosymbionts. The evidence is especially good for mitochondria and chloroplasts, which have their own DNA. When did this transition occur? Some experts say around 1.85 billion years ago. Nick Butterfield has seen fossils of red algae dating back to 1.2 billion years ago, so eukaryotes were definitely around by then. The authors of this book date eukaryotes to “roughly 2 billion years ago, give or take 0.5 billion years.”

5. Sex. This transition takes us from populations of asexually reproducing clones to populations that reproduce sexually. When did this happen? Roughly around the time eukaryotes arose. The authors write:

We would like to know if the evolution of sex is really separate from the evolution of eukaryotes, or whether the two are so closely related that sex co-evolved with the eukaryotic cell. It would help if we knew precisely why organisms bother with sex, but we don’t.

6. Cell differentiation. This transition takes us from single-celled protists to multi-celled animals, plants and fungi where different cells specialize to play different roles. When did this happen? The oldest known animal fossils are some early sponges in the Trezona Formation in South Australia… they go back 665 million years. Plants may go back 1.2 billion years, and fungi perhaps around 1.4 billion years. Just for fun, here’s a typical plant cell:

but of course the point is that thanks to differentiation, different cells in the organism look different!

7. Social colonies. This transition takes us from solitary individuals to social organizations such as colonies of ants, bees and termites, or the somewhat different societies of birds and mammals. Sociality has arisen independently many times, but it’s hard to say when because it’s hard to find fossil evidence! In the early Triassic, about 250 million years ago, we find fossilized burrows containing up to twenty cynodonts of a type known as Trirachodon:

Cynodonts are classified as synapsids, a group of animals that includes mammals but also ‘proto-mammals’ like these. By the late Triassic, there’s also evidence for social behavior among termites. It would be funny if proto-mammals beat the insects to sociality. I bet the insects got there first: the fossil record is not always complete!

8. Language. This is the transition from societies without language (for example, earlier primates) to societies with (for example, us). When did this happen? Alas, it’s even harder to read off the beginning of language from the fossil record than the arrival of social behavior! I’ll just quote Wikipedia:

Some scholars assume the development of primitive language-like systems (proto-language) as early as Homo habilis, while others place the development of primitive symbolic communication only with Homo erectus (1.8 million years ago) or Homo heidelbergensis (0.6 million years ago) and the development of language proper with Homo sapiens sapiens less than 100,000 years ago.

So that’s a list of 8 ‘major transitions’! With each one we get a higher level of organization, while preserving the structures that came before. At least that’s true of the first 7: the last is a work in progress.

In fact, this list was first propounded here:

• Eörs Szathmáry and John Maynard Smith, The major evolutionary transitions, Nature 374 (1995), 227-232.

and these authors expanded on their ideas here:

• Eörs Szathmáry and John Maynard Smith, The Major Transitions in Evolution, Oxford U. Press, Oxford, 1995.

I haven’t read that book yet, alas. Lenton and Watson actually argue for a different, shorter list:

1. The origin of life, before 3.8 billion years ago.

2. The Great Oxidation, when photosynthesis put oxygen into the atmosphere between 3.4 and 2.5 billion years ago.

3. The rise of complex life (eukaryotes), roughly 2 billion years ago.

4. The rise of humanity, roughly 0 billion years ago.

They consider these to be the “truly difficult events that may have determined the pace of evolution”.

Of course the latest revolution, humanity, is not complete. There is no guarantee that it will have a happy ending. Lenton and Watson sketch several alternative futures:

1. Apocalypse.

2. Retreat.

3. Revolution.

I’ll say more about these later. This is what Azimuth is ultimately all about.

The Complexity Barrier

Could we grow the whole universe with all its seeming complexity starting from a little seed? How much can you do with just a little information?

People have contests about this. My programmer friend Bruce Smith points out this animation, produced using a program less than 4 kilobytes long:

As he notes:

…to be fair, the complexity of some of the OS, graphics drivers, and hardware should be included, but this is a lot less than you might think if you imagine rewriting it purely for compactness rather than for speed, and only including what this sort of program needs to produce output.

Sampo Syreeni pointed me to this video, all generated from under 64 kilobytes of x86 code:

As he points out, one trick is to use symmetry.

These fancy images produced from tiny amounts of information are examples of the ‘demoscene’. a computer art subculture where people produce demos: non-interactive audio-visual computer presentations that run in real time.

According to the Wikipedia article on the demoscene:

Recent computer hardware advancements include faster processors, more memory, faster video graphics processors, and hardware 3D acceleration. With many of the past’s challenges removed, the focus in making demos has moved from squeezing as much out of the computer as possible to making stylish, beautiful, well-designed real time artwork […]

The old tradition still lives on, though. Demo parties have competitions with varying limitations in program size or platform (different series are called compos). On a modern computer the executable size may be limited to 64 kB or 4 kB. Programs of limited size are usually called intros. In other compos the choice of platform is restricted; only old computers, like the 8-bit Commodore 64, or the 16-bit Amiga, or Atari ST, or mobile devices like handheld phones or PDAs are allowed. Such restrictions provide a challenge for coders, musicians and graphics artists and bring back the old motive of making a device do more than was intended in its original design.

What else can you do with just a little information? Bruce listed a couple more things:

• Bill Gates’ first commercial success was an implementation of a useful version of BASIC in about 4000 bytes;

• the complete genetic code of an organism can be as short as a few hundred thousand bytes, and that has to be encoded in a way that doesn’t allow for highly clever compression schemes.

So if quite complex things can be compressed into fairly little information, you can’t help but wonder: how complex can something be?

The answer: arbitrarily complex! At least that’s true if we’re talking about the Kolmogorov complexity of a string of bits: namely, the length of the shortest computer program that prints it out. Lots of long strings of bits can’t be compressed. You can’t print most of them out using short programs, since there aren’t enough short programs to go around.

Of course, we need to fix a computer language ahead of time, so this is well-defined. And we need to make sure the programs are written in binary, so the comparison is fair.

So, things can be arbitrarily complex. But here’s a more interesting question: how complex can we prove something to be?

The answer is one of the most astounding facts I know. It’s called Chaitin’s incompleteness theorem. It says, very roughly:

There’s a number L such that we can’t prove the Kolmogorov complexity of any specific string of bits is bigger than L.

Make sure you understand this. For any number,
we can prove there are infinitely many bit strings with Kolmogorov complexity bigger than that. But we can’t point to any particular bit string and prove its Kolmogorov complexity is bigger than !

Over on Google+, Allen Knutson wrote:

That’s an incredibly disturbing theorem, like driving to the edge of the universe and finding a wall.

I call the complexity barrier. So one question is, how big is ? It’s hard, or perhaps even impossible, to find the smallest that does the job. But we can certainly find numbers that work. And they’re surprisingly small!

My friend Bruce estimates that the complexity barrier is a few kilobytes.

I’d like to see a program a few kilobytes long that produces a video showing a big bang, the formation of stars and galaxies, then planets, including one where life evolves, then intelligent life, then the development of computers… and finally someone writing the very same program.

I can’t prove it’s possible… but you can’t prove it isn’t!

Let’s see why.

For starters, we need to choose some axioms for our system of math, so we know what ‘provable’ means. We need a system that’s powerful enough to prove a bunch of basic facts about arithmetic, but simple enough that a computer program can check if a proof in this system is valid.

There are lots of systems like this. Three famous ones are Peano arithmetic, Robinson arithmetic (which is less powerful) and Zermelo-Fraenkel set theory (which is more powerful).

When you have a system of math like this, Gödel’s first incompleteness theorem kicks in: if the system is consistent, it can’t be complete. In other words, there are some questions it leaves unsettled. This is why we shouldn’t be utterly shocked that while a bunch of bit strings have complexity more than , we can’t prove this.

Gödel’s second incompleteness theorem also kicks in: if the system can prove that it’s consistent, it’s not! (If it’s not consistent, it can prove anything, so you shouldn’t trust it.) So, there’s a sense in which we can never be completely sure that our system of math is consistent. But let’s assume it is.

Given this, Chaitin’s theorem says:

There exists a constant such that no string of bits has Kolmogorov complexity that provably exceeds .

How can we get a number that does the job? Any number with

will do. Here:

• is the length of a program where if you input a natural number , it will search through all proofs in Peano arithmetic until it finds one that proves some bit string has Kolmogorov complexity . If it finds one, then it outputs this bit string. If it never finds one, it grinds on endlessly. (Of course, if , it will never find one!)

• is a small overhead cost: the length of the extra 'glue' to create a bigger program that takes the number , written out in binary, and feeds it into the program described above.

The length of written out in binary is about . This bigger program thus has length

and for the proof of Chaitin’s incompleteness theorem to work, we need this to be smaller than Obviously we can accomplish this by making big enough, since grows slower than

Given all the stuff I’ve told you, the proof of Chaitin’s theorem almost writes itself! You run this bigger program I just described. If there were a bit string whose Kolmogorov complexity is provably greater than , this program would print one out. But that’s a contradiction, because this program has length less than .

So, we just need to pick a computer language and a suitable system of math, and estimate and, less importantly because it’s so much smaller, . Then will be just a bit bigger than .

I picked the language C and Peano arithmetic and asked Bruce if he could guess, roughly, what answer we get for . He replied:

I don’t think it can be done in C, since C semantics are not well-defined unless you specify a particular finite machine size. (Since C programs can do things like convert pointers to integers and back, tell you the size of any datatype, and convert data of any specified datatype to bytes and back.) On a finite machine of bits, all programs either finish in time less than about or take forever.

But if you take “C without size-specific operations”, or a higher level language like Python, or for that matter a different sort of low-level language like a Turing machine, then that’s not an issue — you can define a precise semantics that allows it to run a program for an arbitrarily long time and allocate an arbitrary number of objects in memory which contain pointers to each other. (To stick with the spirit of the question, for whatever language you choose, you’d want to disallow use of any large external batch of information like a “standard library”, except for whatever is so basic that you think of it as part of the native language. This is not a serious handicap for this problem.)

The main things that the program ‘‘ (I’d rather call the program itself ‘U’ than call its length ‘‘) needs to do are:

• recognize a syntactically correct statement or proof;

• check the validity of a purported proof;

• recognize certain statements as saying or implying “The Kolmogorov complexity of is more than ” for some and . (It’s not necessary to recognize all such statements, just at least one for each and ; so it can just recognize a statement that consists of some template with specific values of and inserted into it at certain places.)

Assuming that expresses the proofs it wants to check in a practical proof language (which will be more like what a practical theorem-prover like Coq uses than like what a traditional logician would recognize as “straight Peano arithmetic”, but which will not be excessively powerful in the spirit of this question), I’d estimate that the most complex part is checking proof validity, but that that can still be expressed in at most a few dozen syntactic rules, each expressible in a few lines of code. (The authors of a system like Coq, which includes code to actually do that, would know better, as long as they remember that the vast majority of their system’s actual code is not needed for this problem.)

This makes me think that even without trying to compact it much, in a reasonable language we could write in a few hundred lines of code, or (after a bit of simple compression) a few thousand bytes. (And perhaps much less if we tried hard to compact the whole program in clever ways.)

So will also be “a few thousand” (bytes or digits), or perhaps less, rather than some number you can never possibly count to.

Does anyone know if Chaitin or someone actually went ahead a wrote a program that showed a specific value of would work?

Network Theory (Part 15)

Last time we saw how to get a graph whose vertices are states of a molecule and whose edges are transitions between states. We focused on two beautiful but not completely realistic examples that both give rise to the same highly symmetrical graph: the ‘Desargues graph’.

Today I’ll start with a few remarks about the Desargues graph. Then I’ll get to work showing how any graph gives:

• A Markov process, namely a random walk on the graph.

• A quantum process, where instead of having a probability to hop from vertex to vertex as time passes, we have an amplitude.

The trick is to use an operator called the ‘graph Laplacian’, a discretized version of the Laplacian which happens to be both infinitesimal stochastic and self-adjoint. As we saw in Part 12, such an operator will give rise both to a Markov process and a quantum process (that is, a one-parameter unitary group).

The most famous operator that’s both infinitesimal stochastic and self-adjoint is the Laplacian, Because it’s both, the Laplacian shows up in two important equations: one in stochastic mechanics, the other in quantum mechanics.

• The heat equation:

describes how the probability of a particle being at the point smears out as the particle randomly walks around:

The corresponding Markov process is called ‘Brownian motion’.

• The Schrödinger equation:

describes how the amplitude of a particle being at the point wiggles about as the particle ‘quantumly’ walks around.

Both these equations have analogues where we replace space by a graph, and today I’ll describe them.

Drawing the Desargues graph

First I want to show you a nice way to draw the Desargues graph. For this it’s probably easiest to go back to our naive model of an ethyl cation:

Even though ethyl cations don’t really look like this, and we should be talking about some trigonal bipyramidal molecule instead, it won’t affect the math to come. Mathematically, the two problems are isomorphic! So let’s stick with this nice simple picture.

We can be a bit more abstract, though. A state of the ethyl cation is like having 5 balls, with 3 in one pile and 2 in the other. And we can focus on the first pile and forget the second, because whatever isn’t in the first pile must be in the second.

Of course a mathematician calls a pile of things a ‘set’, and calls those things ‘elements’. So let’s say we’ve got a set with 5 elements. Draw a red dot for each 2-element subset, and a blue dot for each 3-element subset. Draw an edge between a red dot and a blue dot whenever the 2-element subset is contained in the 3-element subset. We get the Desargues graph.

That’s true by definition. But I never proved that any of the pictures I showed you are correct! For example, this picture shows the Desargues graph:

but I never really proved this fact—and I won’t now, either.

To draw a picture we know is correct, it’s actually easier to start with a big graph that has vertices for all the subsets of our 5-element set. If we draw an edge whenever an -element subset is contained in an -element subset, the Desargues graph will be sitting inside this big graph.

Here’s what the big graph looks like:

This graph has vertices. It’s actually a picture of a 5-dimensional hypercube! The vertices are arranged in columns. There’s

• one 0-element subset,

• five 1-element subsets,

• ten 2-element subsets,

• ten 3-element subsets,

• five 4-element subsets,

• one 5-element subset.

So, the numbers of vertices in each column go like this:

which is a row in Pascal’s triangle. We get the Desargues graph if we keep only the vertices corresponding to 2- and 3-element subsets, like this:

It’s less pretty than our earlier picture, but at least there’s no mystery to it. Also, it shows that the Desargues graph can be generalized in various ways. For example, there’s a theory of bipartite Kneser graphs The Desargues graph is .

Desargues’ theorem

I can’t resist answering this question: why is it called the ‘Desargues graph’? This name comes from Desargues’ theorem, a famous result in projective geometry. Suppose you have two triangles ABC and abc, like this:

Suppose the lines Aa, Bb, and Cc all meet at a single point, the ‘center of perspectivity’. Then the point of intersection of ab and AB, the point of intersection of ac and AC, and the point of intersection of bc and BC all lie on a single line, the ‘axis of perspectivity’. The converse is true too. Quite amazing!

The Desargues configuration consists of all the actors in this drama:

• 10 points: A, B, C, a, b, c, the center of perspectivity, and the three points on the axis of perspectivity

and

• 10 lines: Aa, Bb, Cc, AB, AC, BC, ab, ac, bc and the axis of perspectivity

Given any configuration of points and lines, we can form a graph called its Levi graph by drawing a vertex for each point or line, and drawing edges to indicate which points lie on which lines. And now for the punchline: Levi graph of the Desargues configuration is the ‘Desargues-Levi graph’!—or Desargues graph, for short.

Alas, I don’t know how this is relevant to anything I’ve discussed. For now it’s just a tantalizing curiosity.

A random walk on the Desargues graph

Back to business! I’ve been telling you about the analogy between quantum mechanics and stochastic mechanics. This analogy becomes especially interesting in chemistry, which lies on the uneasy borderline between quantum and stochastic mechanics.

Fundamentally, of course, atoms and molecules are described by quantum mechanics. But sometimes chemists describe chemical reactions using stochastic mechanics instead. When can they get away with this? Apparently whenever the molecules involved are big enough and interacting with their environment enough for ‘decoherence’ to kick in. I won’t attempt to explain this now.

Let’s imagine we have a molecule of iron pentacarbonyl with—here’s the unrealistic part, but it’s not really too bad—distinguishable carbonyl groups:

Iron pentacarbonyl is liquid at room temperatures, so as time passes, each molecule will bounce around and occasionally do a maneuver called a ‘pseudorotation’:

We can approximately describe this process as a random walk on a graph whose vertices are states of our molecule, and whose edges are transitions between states—namely, pseudorotations. And as we saw last time, this graph is the Desargues graph:

Note: all the transitions are reversible here. And thanks to the enormous amount of symmetry, the rates of all these transitions must be equal.

Let’s write for the set of vertices of the Desargues graph. A probability distribution of states of our molecule is a function

with

We can think of these probability distributions as living in this vector space:

I’m calling this space because of the general abstract nonsense explained in Part 12: probability distributions on any measure space live in a vector space called Today that notation is overkill, since every function on lies in But please humor me.

The point is that we’ve got a general setup that applies here. There’s a Hamiltonian:

describing the rate at which the molecule randomly hops from one state to another… and the probability distribution evolves in time according to the equation:

But what’s the Hamiltonian ? It’s very simple, because it’s equally likely for the state to hop from any vertex to any other vertex that’s connected to that one by an edge. Why? Because the problem has so much symmetry that nothing else makes sense.

So, let’s write for the set of edges of the Desargues graph. We can think of this as a subset of by saying when is connected to by an edge. Then

We’re subtracting because there are 3 edges coming out of each vertex so this is the rate at which the probability of staying at decreases. We could multiply this Hamiltonian by a constant if we wanted the random walk to happen faster or slower… but let’s not.

The next step is to solve this discretized version of the heat equation:

Abstractly, the solution is easy:

But to actually compute we might want to diagonalize the operator In this particular example, we could take advantage of the enormous symmetry of the Desargues graph. Its symmetry group includes the permutation group so we could take the vector space and break it up into irreducible representations of . Each of these will give an eigenspace of so by this method we can diagonalize I’d sort of like to try this… but it’s a big digression, so I won’t. At least, not today!

Graph Laplacians

The Hamiltonian we just saw is an example of a ‘graph Laplacian’. We can write down such a Hamiltonian for any graph, but it gets a tiny bit more complicated when different vertices have different numbers of edges coming out of them.

The word ‘graph’ means lots of things, but right now I’m talking about simple graphs. Such a graph has a set of vertices and a set of edges such that

which says the edges are undirected, and

which says there are no loops. Let be the degree of the vertex meaning the number of edges coming out of it.

Then the graph Laplacian is this operator on :

There is a huge amount to say about graph Laplacians! If you want, you can get started here:

• Michael William Newman, The Laplacian Spectrum of Graphs, Masters Thesis, Department of Mathematics, University of Manitoba, 2000.

But for now, let’s just say that is a Markov process describing a random walk on the graph, where hopping from one vertex to any neighboring vertex has unit probability per unit time. We can make the hopping faster or slower by multiplying by a constant. And here is a good time to admit that most people use a graph Laplacian that’s the negative of ours, and write time evolution as . The advantage is that then the eigenvalues of the Laplacian are

But what matters most is this. We can write the operator as a matrix whose entry is 1 when there’s an edge from to and 0 otherwise, except when , in which case the entry is And then:

Puzzle 1. Show that for any finite graph, the graph Laplacian is infinitesimal stochastic, meaning that:

and

This fact implies that for any the operator is stochastic—just what we need for a Markov process.

But we could also use as a Hamiltonian for a quantum system, if we wanted. Now we think of as the amplitude for being in the state . But now is a function

with

We can think of this function as living in the Hilbert space

where the inner product is

Puzzle 2. Show that for any finite graph, the graph Laplacian is self-adjoint, meaning that:

This implies that for any , the operator is unitary—just what we need for one-parameter unitary group. So, we can take this version of Schrödinger’s equation:

and solve it:

and we’ll know that time evolution is unitary!

So, we’re in a dream world where we can do stochastic mechanics and quantum mechanics with the same Hamiltonian. I’d like to exploit this somehow, but I’m not quite sure how. Of course physicists like to use a trick called Wick rotation where they turn quantum mechanics into stochastic mechanics by replacing time by imaginary time. We can do that here. But I’d like to do something new, special to this context.

Maybe I should learn more about chemistry and graph theory. Of course, graphs show up in at least two ways: first for drawing molecules, and second for drawing states and transitions, as I’ve been doing. These books are supposed to be good:

• Danail Bonchev and D.H. Rouvray, eds., Chemical Graph Theory: Introduction and Fundamentals, Taylor and Francis, 1991.

• Nenad Trinajstic, Chemical Graph Theory, CRC Press, 1992.

• R. Bruce King, Applications of Graph Theory and Topology in Inorganic Cluster Coordination Chemistry, CRC Press, 1993.

The second is apparently the magisterial tome of the subject. The prices of these books are absurd: for example, Amazon sells the first for $300, and the second for $222. Luckily the university here should have them…

Buycotts

I always thought the opposite of a boycott was a girlcott. Turns out it’s a ‘buycott’.

In a boycott, a bunch of people punish a company they dislike by not buying their stuff. In a buycott, they reward one they like.

Here on Azimuth, Allan Erskine pointed out one organization pushing this idea: Carrotmob, founded by Brent Schulkin. Why ‘Carrotmob’? Well, while a boycott threatens a company with the ‘stick’ of economic punishment, a mob of customers serves as a ‘carrot’ to reward good behavior.

Carrotmob’s first buycott was local: they went to 23 convenience stores in San Francisco with a plan to transform one into the most environmentally-friendly store in the neighborhood, and promised to bring in a bunch of consumers to the winner to spend a bunch of money on one day. In order to receive the increased sales from this event, store owners were invited to place bids on what percentage of that revenue they’d spend on making their store more energy-efficient. The winning bid was 22%, by K & D Market. On the day of the campaign, hundreds of people arrived and spent over $9200. In exchange, the store took 22% of that revenue, and used it to do a full retrofit of their lighting system.

Can it be scaled up? Can these deals be enforced? Time will tell, but it seems like a good thing to try. For one thing, unlike a boycott, it spreads good vibes, because it’s a positive-sum game. On the other hand, over on Google+, Matt McIrvin wrote:

I’m a little skeptical that this kind of approach works over the long term, because it would have the effect of increasing the market price of “good” products through increased demand, which in turn means that anyone who doesn’t care about the attribute in question will be motivated to buy the lower-priced “bad” products instead. What you end up with is just a market sector of politically endorsed products that may do a good niche business but that most people ignore.

This is also the big problem with just telling people to go green instead of taxing or otherwise regulating environmental externalities.

Here are some good stories:

• Ready? Set. Shop! One genius environmentalist puts the flash-mob phenomenon to high-minded use, San Francisco Magazine, June 2008.

• Change we can profit from, The Economist, 29 January 2009.

For more, try the references here:

• Carrotmob, Wikipedia.

What other innovative strategies could environmentalists use, that we should know about?

By the way, boycotts are named after Captain Charles Boycott. The story is sort of interesting…

A Math Puzzle Coming From Chemistry

I posed this puzzle a while back, and nobody solved it. That’s okay—now that I think about it, I’m not sure how to solve it either!

It seems to involve group theory. But instead of working on it, solving it and telling you the answer, I’d rather dump all the clues in your lap, so we can figure it out together.

Suppose we have an ethyl cation. We’ll pretend it looks like this:

As I explained before, it actually doesn’t—not in real life. But never mind! Realism should never stand in the way of a good puzzle.

Continuing on in this unrealistic vein, we’ll pretend that the two black carbon atoms are distinguishable, and so are the five white hydrogen atoms. As you can see, 2 of the hydrogens are bonded to one carbon, and 3 to the other. We don’t care how the hydrogens are arranged, apart from which carbon each hydrogen is attached to. Given this, there are

ways to arrange the hydrogens. Let’s call these arrangements states.

Now draw a dot for each of these 20 states. Draw an edge connecting two dots whenever you can get from one state to another by having a hydrogen hop from the carbon with 2 hydrogens to the carbon with 3. You’ll get this picture, called the Desargues graph:

The red dots are states where the first carbon has 2 hydrogens attached to it; the blue ones are states where the second carbon has 2 hydrogens attached to it. So, each edge goes between a red and a blue dot. And there are 3 edges coming out of each dot, since there are 3 hydrogens that can make the jump!

Now, the puzzle is to show that you can also get the Desargues graph from a different kind of molecule. Any molecule shaped like this will do:

The 2 balls on top and bottom are called axial, while the 3 around the middle are called equatorial.

There are various molecules like this. For example, phosphorus pentachloride. Let’s use that.

Like the ethyl cation, phosphorus pentachloride also has 20 states… but only if count them a certain way! We have to treat all 5 chlorines as distinguishable, but think of two arrangements of them as the same if we can rotate one to get the other. Again, I’m not claiming this is physically realistic: it’s just for the sake of the puzzle.

Phosphorus pentachloride has 6 rotational symmetries, since you can turn it around its axis 3 ways, but also flip it over. So, it has

states.

That’s good: exactly the number of dots in the Desargues graph! But how about the edges? We get these from certain transitions between states. These transitions are called pseudorotations, and they look like this:

Phosphorus pentachloride really does this! First the 2 axial guys move towards each other to become equatorial. Beware: now the equatorial ones are no longer in the horizontal plane: they’re in the plane facing us. Then 2 of the 3 equatorial guys swing out to become axial.

To get from one state to another this way, we have to pick 2 of the 3 equatorial guys to swing out and become axial. There are 3 choices here. So, we again get a graph with 20 vertices and 3 edges coming out of each vertex.

Puzzle. Is this graph the Desargues graph? If so, show it is.

I read in some chemistry papers that it is. But is it really? And if so, why? David Corfield suggested a promising strategy. He pointed out that we just need to get a 1-1 correspondence between

• states of the ethyl cation and states of phosphorus pentachloride,

together with a compatible 1-1 correspondence between

• transitions of the ethyl cation and transitions of phosphorus pentachloride.

And he suggested that to do this, we should think of the split of hydrogens into a bunch of 2 and a bunch of 3 as analogous to the split of chlorines into a bunch of 2 (the ‘axial’ ones) and a bunch of 3 (the ‘equatorial’ ones).

It’s a promising idea. There’s a problem, though! In the ethyl cation, a single hydrogen hops from the bunch of 3 to the bunch of 2. But in a pseudorotation, two chlorines go from the bunch of 2 to the bunch of 3… and meanwhile, two go back from the bunch of 3 to bunch of 2.

And if you think about it, there’s another problem too. In the ethyl cation, there are 2 distinguishable carbons. One of them has 3 hydrogens attached, and one doesn’t. But in phosphorus pentachloride it’s not like that. The 3 equatorial chlorines are just that: equatorial. They don’t have 2 choices about how to be that way. Or do they?

Well, there’s more to say, but this should already make it clear that getting ‘natural’ one-to-one correspondences is a bit tricky… if it’s even possible at all!

If you know some group theory, we could try solving the problem using the ideas behind Felix Klein’s ‘Erlangen program’. The group of permutations of 5 things, say acts as symmetries of either molecule. For the ethyl cation the set of states will be for some subgroup You can think of as a set of structures of some sort on a 5-element set. The group acts on and the transitions will give an invariant binary relation on For phosphorus pentachloride we’ll have some set of states for some other subgroup , and the transitions will give an invariant relation on .

We could start by trying to see if is the same as —or more precisely, conjugate. If they are, that’s a good sign. If not, it’s bad: it probably means there’s no ‘natural’ way to show the graph for phosphorus pentachloride is the Desargues graph.

I could say more, but I’ll stop here. In case you’re wondering, all this is just a trick to get more mathematicians interested in chemistry. A few may then go on to do useful things.

Bioremediation and Ecological Restoration Job

The University of Texas – Pan American (UTPA) Department of Biology is trying to fill an Assistant Professor Faculty position in Bioremediation and Ecological Restoration, which will start in Fall 2012 pending budget approval. They’re looking for someone whose area of research is bioremediation and/or ecological restoration, and they’re especially interested in candidates whose research focuses on environmental issues relevant to the Lower Rio Grande Valley.

For more details, go here.