### Little Atoms

13th December, 2010

I was recently interviewed by Neil Denny on Little Atoms. You can hear the result here.

Categories: Richard Elsewhere | Comments (0) | Permalink

### One hell of a relationship

11th December, 2010

Alexandrov said [pdf] of their relationship:

“in 1979 this friendship celebrated its fiftieth anniversary and over the whole of this half century there was not only never any breach in it, there was also never any quarrel, in all this time there was never any misunderstanding between us on any question, no matter how important for our lives and our philosophy; even when our opinions on one of these questions differed, we showed complete understanding and sympathy for the views of each other.”

No quarrels, no misunderstandings, complete understanding and symapthy for 50 years…. that really sets the bar for the rest of us.

Categories: Maths, Politics | Comments (1) | Permalink

### No more news

1st December, 2010

One issue which is often discussed is *sensationalism*. By having racier, more exciting stories than their rivals, a newspaper or TV channel hopes to attract a bigger audience. And of course it is audience size, rather than accuracy or quality of output, which measures success. So dramatic stories are privileged over dull-but-worthy ones, and everything must be dressed up to seem as spicy as possible.

I exaggerate, perhaps, but the process is well known and much analysed. But there is another, deeper phenomenon, at play: Harrabin’s law. It doesn’t depend on the cynicism of the press, but begins with the observation that news, definitionally, has to be *new*. So commonplace or ongoing situations are unlikely to be included. Conversely, the more uncommon an event is, the more newsworthy it is. So rather than providing a summary of the state of the world, the news represents a daily freakshow of uncommon occurrences. It is, by its very definition, utterly unrepresentative of people’s wider experience.

I was impressed by this idea, because it gives a simple causal mechanism whereby many important facts about the world go unreported, for the very reason that they are happening all the time. So newsdesks prioritise rarities such as train and plane crashes over the daily carnage on our roads. Serial killers and terrorists get top billing, while domestic violence chunters along below the radar. The Congalese war, which has been raging for over a decade, claiming millions of victims, makes the news so rarely that many people remain unaware even that it is happening. Meanwhile skirmishes in previously peaceful regions are guaranteed headline status. Deaths due to ecstasy are reported; those due to alcohol are not. How could they be? After all, they are happening constantly. But it is in knowing the things which are happening day in day out which gives us a truer picture of the world we live in.

As you might expect, Harrabin’s law has political consequences. Firstly, it distorts people’s perception of risk. The classic example is the person who is terrified of flying, but thinks nothing of driving to work daily. But it isn’t just at the individual level that problems occur. Terrorism is a rarity in the UK, and therefore by Harrabin’s law, it gets reported and discussed a great deal. Hence, governments are under immense pressure to act using any resources necessary. How domestic violence could benefit from the same media exposure! (Of course, if it hardly ever happened, then it would get it.)

The implication seems clear: we don’t need news. What we need is *importants*. (Of course the two may sometimes coincide.) As for how to bring this revolution about, and how to decide what qualifies as important and what does not… well, I’ll leave that to another day.

Categories: Politics | Comments (0) | Permalink

### In the name of Gauss

1st December, 2010

Dick Lipton has an interesting post about the history of mathematical notation, and how it affects the thinking of those who use it. During the discussion he references a mathematician I had never heard of, one “Johann Gauss”. Well, it turns out that was indeed the great man’s name!

UPDATE: it occurs to me that this post might be incomprehensible to the non-geek community. The point is that Gauss – one of the greatest of all mathematicians – is near universally known as Carl Friedrich Gauss. I am quite surprised that I have managed to get this far through my life without knowing his full name.

Categories: Maths | Comments (0) | Permalink

### Punk Math

19th November, 2010

I just ran into Tom Henderson’s Punk Math Manifesto:

The video’s an appeal for funds taken from Kickstarter, but it looks like the target’s already been reached. (Not that a few more pennies would go unappreciated, I’m sure.)

I definitely dig the philosophy, fleshed out in more detail in this interview. So it’ll be good to see the project develop.

Having said all that, punk’s not really my genre. Maybe I should try experimenting with some Jazz Geometry, or Death Metal Model Theory.

Categories: Maths, Music, Nonsense | Comments (0) | Permalink

### Bad Packer

28th October, 2010

Circle packing is a classical topic in discrete geometry. As Axel Thue and László Fejes Tóth showed, if you want to fit as many identical circular coins on a table as possible (all sitting side by side, no piling up or overlapping), the best you can achieve is for around 90.7% of the table to be covered. This is done by arranging the coins along a hexagonal lattice.

That was an interesting result, and can be lifted into higher dimensions in the even subtler science of sphere and hypersphere-packing.

That’s fine, but we can pose the same problem, using coins which are not circular. Now here is an interesting question: which shape is the worst packer?

The question is only sensible for convex shapes, and we further assume that the shape is centrally symmetric.

Then the answer is conjectured to be the smoothed octagon, with a maximum packing density of around 90.2%.

The smoothing is done by rounding off each corner with a hyperpola which is tangent to the two meeting sides, and which asymptotically approaches the two sides beyond those.

[Image from Wikipedia]

Categories: Geometry, Maths | Comments (0) | Permalink

### Blog and book updates

26th October, 2010

I’ve been doing some updates around this place. If things look rickety it’s because I am now phping and htmling myself. I’m having fun with it, but if I’m honest I don’t really know what I am doing. In fact, I don’t even know the difference between php and html. Luckily I have a tame professional webdesigner who should be able to repair any havoc I wreak.

The most important change is that this blog is finally equipped with an RSS feed. I encourage you to subscribe, because posting is likely to remain erratic, so the old fashioned method of clicking over here every once in a while might prove frustrating. Having said that, I do have a few posts lined up for the days ahead.

In celebration of this great step forward, I have decided to officially baptise this blog. Hereafter it will no longer be known only as “Richard Elwes’ blog”, but as *“Simple City”*.

In other news, my book *Mathematics 1001* is now out… sort of. If you live in the USA, then it is definitely and unambiguously out. I think the same is true in Canada. For residents of the UK, the book is currently in a quantum out/not out state. The wave function seems to depend what sort of outlet you try to buy it from. It is not yet in the shops, but it is, I believe, available online. The official final release date here is 6th November. For citizens of Australia, and other countries, well, I don’t know. But it should be out soon, at least.

Anway, I am collecting book reviews (hooray!) and errata (boo!) here. So far there are barely any of either, but that will certainly change within the next couple of weeks. I’ll confine the updates to those pages rather than blogging them, so if you’re interested then check back there occasionally. (If you have any information for me about such things, then I’d be very grateful if you could drop me a line, or leave a comment here.)

Categories: Bloggery, Bookery | Comments (33) | Permalink

### Concrete Incompleteness 1

21st October, 2010

I’ve just uploaded the slides [pdf] from a talk I gave yesterday at the University of Leeds, about concrete incompleteness. The topic is the same as my recent New Scientist article, but in greater technical detail, though the intention was still that it be reasonably accessible to non-logicians. I’ll tell the central story here as a sort of commentary, and there are equations and other gory details available in the slides.

Since Kurt Gödel proved his celebrated first incompleteness theorem, we have known that arithmetic (that is to say the positive whole numbers with addition and multiplication) will always contain unprovable statements. This means that no matter what fundamental axioms we choose to underlie arithmetic, there will always be some statement T such that neither it nor its negation ‘not T’ can be deduced from our axioms. These are called independent or unprovable statements[1].

But of course, it never makes sense to say “T is an unprovable statement” without reference to some specific axiomatic system: different axioms, different provable & unprovable statements.

The standard axioms for arithmetic were written down by Giuseppe Peano in 19th century Italy. Forty years later, Gödel’s theorem implied that Peano’s axioms must be incomplete. The question for today is: are they incomplete in a way that matters to non-logicians? In the course of studying number theory, or combinatorics, are you liable to run into an unprovable statement? Or are such things really curiosities of no wider importance?

Since then, several concrete instances of incompleteness have been found, examples being the termination of Goodstein sequences, the Paris-Harrington variant of Ramsey’s theorem, and Kruskal’s theorem on finite trees as well as Harvey Friedman’s finite miniaturization of that result.

Now, that last result of 2002 represented a big step forward in unprovability theory, for the following reason: attempts to axiomatise arithmetic did not stop with Peano. In the mean time, a wealth of stronger axiomatic systems have been investigated. In particular, for much modern mathematics, it is not enough to talk just about plain whole numbers. We also need to consider how *sets* of such numbers behave. This is the key, for example, to building a coherent theory of real and complex numbers. Peano’s axioms are *first order*, meaning that they discuss only numbers. To axiomatise the behaviour of sets of numbers, we need what is known as *second order* logic. But which sets of numbers should we axiomatize? The minimum second-order system which extends Peano arithmetic is called ACA_{0}, or “arithmetical comprehension”. Here we can sensibly analyse all the sets of numbers which Peano describes. However there are also many stronger systems, notably ATR_{0}, or “arithmetical transfinite recursion”. This system provides a much richer class of sets, defined via certain infinite processes, unavailable in weaker systems. This is the right level at which to build up a large amount of analysis, calculus, and topology. On the other hand, Friedman’s variant of Kruskal’s theorem is purely finitary in nature, involving only plain whole numbers. It’s natural home would seem to be ACA_{0}, and yet it is unprovable not just at that level, but in ATR_{0} too.

This was certainly a striking result, but recent developments have taken us much further. Way, way beyond second order arithmetic is the the system of Zermelo-Fraenkel set theory, ZFC[2]. This allows not just all possible sets of numbers, but also sets of sets of numbers, sets of sets of sets, and so on ad infinitum (and indeed considerably beyond that). As such, ZFC has become the standard foundation for the whole of mathematics. For most purposes it represents massive overkill.

Of course though, Gödel’s theorem applies here too: there must be questions which even ZFC cannot answer. From a set theorist’s perspective, the primary examples concern the existence of *large cardinals*.

ZFC is the modern setting for the great work that Georg Cantor did in the late 19th century, disassembling the concept of infinity. Cantor showed that there is not just one level of infinity, but an infinite ladder with each rung infinitely higher the last. What’s more, there is no ultimate infinity beyond all the others: this ladder has no top rung. One can ask though, whether or not there are rungs so far up that that they are unapproachable from below. These, if they exist, are called “large cardinals”, and their existence is independent of the axioms of ZFC. Set theorists have been studying multiple varieties of large cardinals, and the logical dependencies between them, for over 100 years.

Returning to the finite realm, and the arithmetic of the plain whole numbers, Gödel assures us that here too, not even ZFC will be enough to resolve all possible queries. There must be statements about numbers which are unprovable in ZFC. So we can repeat the earlier question: are these the sort of things which working mathematicians, who are not logicians or set theorists, need to worry about?

This question has received a brand new answer, in the subject of Boolean Relation Theory developed by Harvey Frieman in a forthcoming book (section 3 on this page has downloadable pdfs). In it, he considers a very simple class of functions of whole numbers, known as the Expansive Linear Growth (ELG) functions, and then identifies a certain configuration of inputs and outputs which such functions may exhibit. (The details are on my slide number 12.) The question is: does every ELG function exhibit such a configuration? And the answer is not deducible within ZFC. Certainly, one cannot construct a counterexample. But we have to pass to a stronger system, which contains certain large cardinals, in order to prove the answer “yes”.

I believe that this is an important result. The situations described by Boolean relation theory are indisputably elementary, and (perhaps somewhat disputably) they seem natural. What is more, they are ripe for generalisation. Replacing the natural numbers with different underlying structures, and considering different classes of sets and functions defined by analytic or geometric conditions, we can ask similar questions about the configurations of inputs and outputs which emerge. This may well represent a door through which questions of provability enter mainstream mathematics, not in ones and twos, but in truly significant quantities.

In syntactic terms, the unprovable statements of Boolean relation theory have complexity at the level of Π^{0}_{2}. Friedman additionally set himself the goal of finding a simpler Π^{0}_{1} sentence, which depends on large cardinals, while at the same time providing “clear and compelling information in the finite mathematical realm”. In a separate development, he claims to have found exactly that, in the form of a statement about directed graphs living among the rational numbers. Unfortunately there are several intermediate definitions needed to present it. None of them are at all difficult, but they do mount up, to the point where I can’t say I have much of a mental picture of what exactly is being asserted. Some details, pared down as much as I can, are in my slides 14-16, and a fuller account is in section 0.14D of the introduction [large pdf] to Harvey’s book.

Ok, that’s it for now, but I do intend to write more on this topic – hence the “1” in the post title. Next time I’ll be musing about the philosophical implications of having syntactically simple statements about natural numbers, which can only be resolved using large cardinals.

[1] They’re sometimes called ‘undecidable’ statements, but – warning! – that word is also used in a different way, to do with algorithms. Generally I prefer ‘uncomputable’ for the algorithmic notion, but maybe that’s just me.

[2] Technically, that’s Zermelo-Fraenkel set theory plus the Axiom of Choice. But I don’t want to think about that here – there’s already enough unprovability on the table. So we’ll just take Choice as given.

Categories: Logic, Maths | Comments (7) | Permalink

### Benoît Mandelbrot

18th October, 2010

Contrary to what is written there, Mandelbrot did not discover fractal geometry, as he acknowledged. Earlier thinkers such as Lewis Fry Richardson, Pierre Fatou and Gaston Julia have a greater claim (and *much* earlier thinkers such as Albrecht Dürer might have something to say about it too).

Mandelbrot did however coin the term ‘fractal’ and he helped bring these earlier ideas together into a coherent theory, recognising the potential for powerful applications in many areas of science. He launched these fantastic shapes into popular consciousness through his books the fractal geometry of nature and the (mis)behaviour of markets. His critics might have dismissed fractals as pretty but useless; today, no-one doubts the central role that chaos theory and dynamical systems have in explaining why the universe looks as it does.

[Update: Tom Leinster at the n-Category Café has a very nice technical post about the Mandelbrot set.]

Well, there is only one picture with which to finish off this post:

Categories: Geometry, Maths | Comments (1) | Permalink

### Benoît Mandelbrot

18th October, 2010

Contrary to what is written there, Mandelbrot did not discover fractal geometry, as he acknowledged. Earlier thinkers such as Lewis Fry Richardson, Pierre Fatou and Gaston Julia have a greater claim (and *much* earlier thinkers such as Albrecht Dürer might have something to say about it too).

Mandelbrot did however coin the term ‘fractal’ and he helped bring these earlier ideas together into a coherent theory, recognising the potential for powerful applications in many areas of science. He launched these fantastic shapes into popular consciousness through his books the fractal geometry of nature and the (mis)behaviour of markets. His critics might have dismissed fractals as pretty but useless; today, no-one doubts the central role that chaos theory and dynamical systems have in explaining why the universe looks as it does.

[Update: Tom Leinster at the n-Category Café has a very nice technical post about the Mandelbrot set.]

Well, there is only one picture with which to finish off this post:

Categories: Geometry, Maths | Comments (1) | Permalink

<< Previous: Well Done Simon!

Next: Concrete Incompleteness 1 >>