In praise of Roger Penrose

Roger Penrose has been awarded a share in the Nobel Prize for physics and I could not be more pleased.

It is not that I have met him or even attended a lecture by him and nor do we even see him much on TV – but I owe him a debt for his insight and also for his ability to educate and inform.

A few years ago I bought his “Fashion, Faith and Fantasy” – his stern critique of what he sees as the fashion of string theory and assorted similar ideas. I’m not going to pretend it’s an easy book, and much of it was well over my head – but it is still choc-full of insight. From it I went back to an older copy of “Cycles of Time”. This is a shorter book and was much more heavily marketed as for the “lay reader” but, actually, I found much of it much harder to get to grips with – if you don’t really understand conformal geometry (and I didn’t) it’s pretty hard to follow. But, and this is a big but, it has an absolutely brilliant explanation of entropy in its opening chapters and if, like me, you never really got to grips with this subject (because, I maintain, it was so poorly explained) as an undergraduate, this really cuts through the fog.

It mattered to me because its discussion of phase spaces gave me an insight into the stochastic nature of memory management systems and the way in which entropy can help us explain latency in computer systems. I wrote quite a bit about that in my PhD thesis and I am convinced it’s a subject that would repay a lot more investigation. Sir Roger collected an additional citation for that (not that he needed it of course).

Only last night I again made an attempt on the massive “The Road to Reality” – previously I’ve never managed to get past the introductory discussion of non-Euclidean geometry in chapter two, but I feel a bit more confident about that now, so giving it another go.

How secure is your encryption?

Papal Encryption
Papal Encryption (Photo credit: Samuraijohnny)

The answer is, “probably quite secure, but not as secure as you might think.”

This is not a story about the NSA but about the fundamental maths of encryption – and about the ability to “guess” what an encrypted message might mean through a sophisticated version of “frequency analysis” – in other words guessing what the unencoded symbols would be on the basis of how likely they are to occur.

Up to now the assumption has been that for long enough messages encryption would essentially erase the underlying pattern of a message – in other words the encoded message would have the maximum possible degree of randomness or “entropy“.

A parallel can be made with compression – in a perfect compression algorithm entropy would be maximised: there would be no underlying pattern of 1s and 0s in the binary – as if there was a pattern then this too could be compressed (replaced by a shorter symbol) and so on. In fact most compression algorithms are pretty good – which is why you cannot repeatedly zip files and hope they will keep getting smaller.

But if you are using encryption you might not regard “pretty good” and really good enough – you would want a more or less nailed-on guarantee that your encryption would have maximum entropy, as a pattern in the coded message might point to the patterns in the underlying message.

To get that guarantee we need to show that coding the same word in “clear text” would result in a truly random selection of “code words”. Now, no mathematical process can ever truly guarantee this but it was assumed, based on what seemed to be sound reasoning, that for a sufficiently long message of “clear text” the entropy of the coded message would rapidly approach the maximum.

But report Mark Christiansen and Ken Duffy from the National University of Ireland (Maynooth) and Flavio du Pin Calmon and Muriel Medard from MIT – that assumption is flawed. In fact, in the real world, the approach to maximum entropy is a good deal slower than previously believed: in fact “conditioned” (i.e. real world) sources never get there

There is a paper discussing this – here – with some heavy duty maths. Another article – which probably does a better job than me in explaining it, (but also seems to play down the Irish connection!) is here.

The bottom line seems to be that sophisticated “brute force” attacks (also known as guessing!) might just work after all – because once you guess one word well, the rest of the code might fall into place. If the decoder has some clues about what the message might contain (think of the cryptanalysts at Bletchley Park knowing that many German messages contained weather reports) then it is possible that guesses might – just might – work.

Does this mean that your encryption is broken? Probably not. But it does mean that someone might be able to break your messages well inside the known age of the universe after all.

Time’s arrow

English: Lee Smolin at Harvard University
English: Lee Smolin at Harvard University (Photo credit: Wikipedia)

The forward march of time is possibly the most basic and shared human experience. Whatever else may happen in our lives none of us can make time run backwards  (the title of this post recalls Martin Amis‘s brilliant novel premised on this idea – time running backwards – if you’ve read it you will understand why we are never likely to see it filmed, as 90 minutes of backwards time would be just too much to take.)

Yet, as Lee Smolin points out in this week’s New Scientist, our most fundamental theories of physicsquantum mechanics and general relativity – are time free: they work just as well if time runs the other way round. Physicists square this circle by insisting on only time-forward solutions and by imposing special conditions on our universe. We have even invented a physical category – which has no material existence per se – called entropy and demanded that it always increase.

The accepted physics leaves us in the difficult position of believing that “the future” is not the future at all – it exists and has always existed but we are barred from getting there “ahead of time”. It’s a deep contradiction, though whether this is a flaw in the theories or in human comprehension is what the debate (such as it exists, those who challenge QM and GR are very much in the minority) is all about.

In Smolin’s view (or perhaps my interpretation of it) all of this violates the “Copernican principle” – that we observers are nothing special – that has guided much of physics’s advances of the last five centuries. So what if it is actually telling us that our theories are wrong and like Newtonian gravity is to general relativity, they are merely approximations?

Smolin’s argument is just this. He says we should base our theories on the fundamental observation that time flows in only one direction and so find deeper, truer theories based on unidirectional time.

Representing one terabit of information

I picked up my copy of Roger Penrose‘s Cycles of Time: An Extraordinary New View of the Universeand reread his opening chapter on the nature of entropy (if you struggle with this concept as a student then I recommend the book for this part alone – his exposition is brilliant).

My next thought was to think if I could model his comments about a layer of red paint sitting on top of blue paint – namely could I just write a program that showed how random molecular movements would eventually turn the whole thing purple. Seemed like a nice little programming project to while a way a few hours with – and the colours would be lovely too.

Following Penrose’s outline we would look at a ‘box’ (as modelled below) containing 1000 molecules. The box would only be purple if 499, 500 or 501 molecules were red (or blue), otherwise it would be shaded blue or red.

three dimensional grid

And we would have 1000 of these boxes along each axis – in other words 10^9 boxes and 10^{12} molecules – with 5 \times 10^8 boxes starting as blue (or red).

Then on each iteration we could move, say 10^6 molecules and see what happens.

But while the maths of this is simple, the storage problem is not – even if we just had a bit per molecule it is one terabit of data to store and page in and out on every iteration.

I cannot see how compression would help – initially the representation would be highly compressible as all data would be a long series of 1s followed by a long series of 0s. But as we drove through the iterations and the entropy increased that would break down – that is the whole point, after all.

I could go for a much smaller simulation but that misses demonstrating Penrose’s point – that even with the highly constrained categorisation of what constitutes purple, the mixture turns purple and stays that way.

So, algorithm gurus – tell me how to solve this one?

Update: Redrew the box to reflect the rules of geometry!

Entropy and randomness in communications, a quick introduction

Last year I remarked on how Roger Penrose‘s discussion of entropy in Cycles of Time did more to explain the physical nature of the concept (to me, at least) than many years of formal education.

And now, another book, Information and Coding Theory has given me some real insight into how computers deliver pseudo-randomness and why they look for sources of entropy.

The maths of all this are deceptively simple, but are of fundamental importance in information theory.

First of all, we can think of what sort of information events convey. There is a famous aphorism about the habits of bears, the direction from which the Sun rises and the title of the head of the Catholic Church. No newspaper or TV bulletin would ever bother to tell us, on a daily basis, that the Sun has indeed risen from the East. In effect that event conveys no information because it is completely expected. Toss a coin, though, and we do not know the outcome in advance – the result is of interest because the outcome is not known in advance.

Hence we can posit an information function I(e) which tells us how much information we can derive from event e , or, if we think of symbols in a data stream we can call this I(s_i) – the amount of information we can derive if the next symbol we see is s_i .

From our earlier discussion we can see that the result of this function is dependent on the probability of the event occurring or the symbol being received – i.e. if we knew the Sun was always going to rise in the East we can derive no information from that very thing happening. Hence:

I(s_i) is a function of  p_i where p_i is the probability that the next symbol to be seen is i . As we will only consider ‘memoryless’ events we will also insist that p_i is independent of time or any previously seen symbol. Hence:

I(s_is_j) (i.e. the information we can gain from seeing the symbol s_i followed by the symbol s_j is I(s_i) + I(s_j)

Taking these points together we can define I(s_i) = log\frac{1}{p_i} = -log(p_i)

We can see that I tends to infinity if the probability of an event tends to zero (think of the Sun rising in the West!) and tends to 0 if nothing unexpected happens.

The entropy of a system (communication) H(S) then becomes:

H(S) = \sum\limits_i^q p_iI(s_i) = \sum\limits_i^q p_ilog\frac{1}{p_i} = -\sum\limits_i^q p_i log(p_i)

Evolution and the second law of thermodynamics

"The Blue Marble" is a famous photog...
Image via Wikipedia

When I wrote my first piece about Roger Penrose‘s Cycles of Time – one of the links offered to me was to a Christian fundamentalist blogger who claimed that the second law of thermodynamics showed evolution could not have taken place:

E. Evolution contradicts the Second law of Thermodynamics

In the Theory of Evolution it is proposed that “simple life” evolved into more complex life forms by Spontaneous Generation. Both Darwin’s Theory of Evolution and the Spontaneous Generation model both directly contravene the Law of Biogenesis.

The Second Law Of Thermodynamics

The Second Law of Thermodynamics states that the disorder in a system increases, rather than decreases. 

The problem for this argument’s advocates is that Penrose demolishes it in brilliant style. I won’t quote from him directly, but I will try to summarise his argument.

Penrose begins by actually restating the fundamentalist argument in a much wider sense – it is life itself that on a naive view would appear to violate the second law – after all our bodies do not melt away (so long as we live), but remain highly ordered and as we grow (eg our hair or nails) appear to create order out of disorder.

The key to this is the Sun. The first thing a secondary school science student is taught is that the Sun supplies the Earth with energy but, in fact, this is not true in the sense that the Sun does not provide a net increase in energy on Earth – if it did then our planet would continually heat up until it reached an equilibrium. The Earth re-radiates the Sun’s energy back into space at a equal rate to which it is recieved.

What the Sun is, though, is much hotter than surrounding space and so it sends the Earth a number of high energy (yellow light) photons. When the Earth re-radiates the Sun’s energy it does so at a lower temperature than the Sun – essentially at infra-red frequencies – so many more photons are radiated back into space than are received. More photons means a greater phase space and hence it means a higher entropy. So the Sun continually supplies the Earth with low entropy energy which processes on the Earth – including life – convert into high entropy energy.

For instance when we eat food we convert that low entropy food source (eg an egg) into high entropy heat energy. The food source itself ultimately derived its energy from the low entropy energy source that is the Sun, and so on.

Of course, all the time, the Sun’s own entropy is increasing, but we don’t need to worry about the consequences of that for a few billion more years.

It’s a brilliant, beautiful, argument though it is also one that is seldom, if ever, taught in schools.

The second law of thermodynamics and the history of the universe

Oxford Physicist Roger Penrose to Speak at Bro...
Image via Wikipedia

I had to go on quite a long plane journey yesterday and I bought a book to read – Roger Penrose‘s work on cosmology: Cycles of Time: An Extraordinary New View of the Universe

I bought it on spec – it was on the popular science shelves: somewhere I usually avoid at least for the physical sciences, as I know enough about them to make hand waving more annoying than illuminating, but it seemed to have some maths in it so I thought it might be worthwhile.

I have only managed the first 100 pages of it so far, so have not actually reached his new cosmology, but already feel it was worth every penny.

Sometimes you are aware of a concept for many years but never really understand it, until some book smashes down the door for you. “Cycles of Time” is just such a book when it comes to the second law of thermodynamics. At ‘A’ level and as an undergraduate we were just presented with Boltzmann’s constant and told it was about randomness. If anybody talked about configuration space or phase space in any meaningful sense it passed me by.

Penrose gives both a brilliant exposition of what entropy is all about in both intuitive and mathematical form but also squares the circle by saying that, at heart, there is an imprecision in the law. And his explanation of why the universe moves from low entropy to high entropy is also brilliantly simple but also (to me at least) mathematically sound: as the universe started with such a low entropy in the big bang a random walk process would see it move to higher entropy states (volumes of phase space).

There are some frustrating things about the book – but overall it seems great. I am sure I will be writing more about it here, if only to help clarify my own thoughts.

In the meantime I would seriously recommend it to any undergraduate left wondering what on earth entropy really is. In doing so I am also filled with regret at how I wasted so much time as an undergrad: university really is wasted on the young!

(On breakthrough books: A few years ago I had this experience with Diarmaid MacCulluch’s Reformation and protestantism. People may think that the conflict in the North of Ireland is about religion – but in reality neither ‘side’ really knows much about the religious views of ‘themuns’. That book ought to be compulsory reading in all Ireland’s schools – North and South. Though perhaps the Catholic hierarchy would have some issues with that!)