Simple City

Schelling Segregation (Part 1)

Posted by richardelwes on June 14, 2013

Posted in: Complex systems, Elwes Elsewhere, Maths. 2 Comments

Here’s a question:

When a city contains people of different races, segregation often occurs: sizeable parts of town largely inhabited by people of one race. But when asked what sort of neighbourhood they would like to live in, people often report a preference for mixed neighbourhoods. So why does the reality often fail to reflect this desire?

Of course, there are various conceivable explanations. One comes from what economists call revealed preferences, meaning that, when push comes to shove, people may not be quite so keen on mixed neighbourhoods as they thought they were. But there are other, more interesting possibilities. With some friends I’ve recently being doing some mathematical work which is relevant to this question, and which allows us to take people at their word. The interesting thing is: high levels of segregation can emerge even in a city where everyone would be completely happy in a mixed neighbourhood.

It also produces some rather lovely pictures:

In the next post I’ll explain what this picture means and discuss our work in more detail. (Impatient? The preprint is here.) This post is background, and the starting point is a theoretical model of racial segregation devised by Thomas Schelling in 1969. It’s a simple model of a city, in which people may move houses depending on whether or not they are satisfied with the make-up of their current neighbourhoods.

Schelling is best known for his infamous work on game theory at the RAND Corporation during the Cold War. His book on that subject, Strategies of Conflict, is a very readable introduction to these ideas (so long as you don’t mind a little maths), and is accurately summarised by Cousin It as follows:

”Forget rationalist Judo: this is rationalist eye-gouging, rationalist gang warfare, rationalist nuclear deterrence. Techniques that let you win, but you don’t want to look in the mirror afterward.”

Schelling also played an interesting role in the genesis of Stanley Kubrick’s film on this very subject: Dr Strangelove (Or: How I Learned To Stop Worrying And Love The Bomb).

In 2005, Schelling was awarded the Nobel Memorial prize in Economics in 2005 (though not without some controversy). The Academy commented on both his work on strategy and – my focus here – his insights into questions related to racial segregation.

I’ll describe his model in the next post, but as you will see it is very simple indeed. Now, you can view this either as a good or a bad thing. For a mathematician – that’s me – it’s good, since it provides the possibility of a thorough analysis of the mechanisms at work. On the other hand, for a social scientist, it does carry the undeniable disadvantage that the model is a pretty feeble reflection of reality.

So let’s admit from the outset that Schelling’s model town is by no means realistic: it ignores obviously relevant factors such as geography, local amenities, transport, and, well, pretty much anything else you can think of that real people actually care about when choosing where to live. On top of this, it pretends that people live in a beautifully convenient geometrical arrangement, which in reality happens only occasionally.

There have been numerous subsequent modifications of the model to make it more realistic, and therefore presumably more useful to social scientists, for instance by incorporating factors such as house prices. Even so, I hold that Schelling’s original simple model carries a rather profound lesson for us all, not about racial segregation particularly, but more generally about the relationship between the actions of individuals and the larger scale social structures to which they can give rise.

This relationship can be extremely counterintuitive, as discussed in Schelling’s – again very readable and less technical – book on this theme: Micromotives and Macrobehaviour. As he says

“…sometimes the results are surprising. Sometimes they are not easily guessed. Sometimes the analysis is difficult. Sometimes it is inconclusive. But even inconclusive analysis can warn against jumping to conclusions about individual intentions from observations of aggregates, or jumping to conclusions about the behavior of aggregates from what one knows or can guess about individual intentions.”

In particular, in the next post I’ll discuss the surprising finding that when people are more tolerant of neighbours of different races, this may actually lead to greater segregation.

Twin Prime Day! (Or why theorems in analytic number theory are like buses)

Posted by richardelwes on May 14, 2013

Posted in: Maths, Number theory. 9 Comments

Waiting For Goldbach

Yesterday, two – yes two! – dramatic developments in the theory of prime numbers were announced. Both are – if correct – major theorems in their own right. Both can also be seen as steps towards the very biggest questions in the subject.

(For those who came in late: remember that a prime is a whole number like 7, which can’t be divided by anything except itself and 1. So 6 is non-prime as it is divisible by 2.)

Twin Primes

It has long been observed that prime numbers sometimes come in pairs: 3 & 5, 17 & 19, 29 & 31, 821 & 823,…

The Twin Prime Conjecture asserts, very simply, that this list goes on forever: there are infinitely many pairs of twin primes, meaning pairs (a) and (b) where (b=a+2). This is an old open problem which has left numerous clever people scratching their heads down the centuries. Although the list of known twin primes has grown ever longer (as of 2013, the record holders are 200700 digits long!), no-one has managed to prove it for certain.

Yesterday at Harvard Yitang Zhang announced a proof, not of the full twin prime conjecture, but of a weaker result: that there are infinitely many pairs of primes (a) and (b) where (a < b leq a+70,000,000). Although this bound of 70 million is admittedly slightly bigger than 2, this is still a huge breakthrough, as it is the first time any result of this type has been proven. It establishes for the first time a very deep fact indeed: that even when you look at truly gigantic primes, you are guaranteed still to find some which are close together in an absolute and unwavering sense.

Goldbach’s Conjecture

In a letter to Leonhard Euler in 1742, Christian Goldbach remarked that every even number bigger than 2 can be written as two primes added together: e.g. 4=2+2, 10=7+3, 100=61+59, etc..

Again, a great many people have tried and failed to prove that this simple observation should always hold, although (again) computational work has verified it for all even numbers up to a large value, in this case 4,000,000,000,000,000,000.

Now, another way to state Goldbach’s conjecture is to say that every whole number from 7 onwards (not necessarily even) can be written as the sum of three primes. (It’s worth spending a minute or two thinking about why this is equivalent.)

A weaker statement, then, is that every odd number from 7 onwards is the sum of three primes. This statement, known as Goldbach’s Odd Conjecture, would certainly follow from his main conjecture. But it looks as if we won’t have to wait that long, because yesterday Harald Helfgott claimed a proof!

In fact, Helfgott has shown that it is true for all odd numbers above 10,000,000,000,000,000,000,000,000,000,000, and separately with David Platt has checked numbers up to that limit by computer.

In fact, we’ve known since 1937 that Goldbach’s Odd Conjecture must hold for all large enough numbers, but previously the threshold was over 1300 digits long: way, way too big to be checked computationally. Yesterday, Helfgott finally slammed that window shut.

[Post edited 15th May, see comments]

UPDATE, 19th May. In fact, Peter Rowlett points out that Helfgott is claiming the proof of two weak Goldbach conjectures:

1) Every odd number from 7 onwards is the sum of three primes

and the stronger statement:

2) Every odd number from 9 onwards is the sum of three odd primes (i.e. you can do it without using 2).

Chaotic Fishponds and Mirror Universes

Posted by richardelwes on May 3, 2013

Posted in: Bookery. 4 Comments

I have a new book out! Chaotic Fishponds and Mirror Universes is published by Quercus and is available now as a paperback or e-book.

My intention is to show how mathematics is essential to many aspects of today’s world. So each of its 35 chapters discusses a genuine application of maths to some other part of life. The title comes from the sections on symmetry in physics and chaos in population biology. There are other chapters focusing on traditional sciences, including chemistry, astronomy, and optics.

However, much of the book is concerned with modern technology. Just about everyone knows, at some level, that maths plays a central role in our interconnected, computerized, hi-tech world. But far fewer people have a good sense for what that role actually is. So I have included chapters discussing how maths enables the rendering of CGI graphics, allows us to search the internet quickly and email our friends securely, how it guides the limbs of robots, and the trajectories of spacecraft, and much else besides.

Also covered are various overlooked techniques which nevertheless contribute enormously to the smooth running of modern civilization, including industrial optimization, weather forecasting, queuing theory, and the mathematical modelling of disease epidemics.

What else? Add a dash of economics, a sprinkling of psychology, a spoonful of game theory, a little something on the theory of elections, the sociology of Facebook, the relationship between computer programming and logical paradox, and garnish with handful of statistical illusions.

I hope that the reader will come away not only convinced of the fact that maths is indeed essential to the modern world, but will also have a better insight into how.

Euler’s Totient Theorem

Posted by richardelwes on April 14, 2013

Posted in: Maths, Number theory. 4 Comments

In honour of Leonhard Euler’s 306th birthday (and also to celebrate my finally having figured out how to use Mathjax on my blog^[1]) I thought I’d have a quick look at one of his great accomplishments. This result is sometimes known simply as Euler’s theorem… but that really is a hopelessly ambiguous name.

The result revolves around a single, simple idea: that of the totient. This starts with the observation that any two whole numbers either have a factor in common, or they don’t. For instance 12 and 33 share a a factor of 3, while 8 and 9 have only 1 in common (which we don’t count, since it’s a factor of everything). That is to say, 8 and 9 are coprime.

The totient of some number $n$ , written $\phi(n)$ , is the the number of numbers between 1 and $n$ which are coprime to it. For instance, the totient of 8 is 4, since 1, 3, 5, 7 are coprime to it (while 2, 4, 6, 8 aren’t). So we can say that $\phi(8)=4$ .

Calculating the totient function seems to require a lot of counting. What is $\phi(100)$ , for instance? It looks nastily as if we will have to traipse through the numbers 1 to 99 in turn, laboriously determining which is coprime to 100 and which isn’t.

Euler’s first theorem about the totient theorem is that there is a much quicker way, a formula. It works like this: say $p_1, p_2, \ldots$ are the prime numbers dividing $n$ . Then $\phi(n)= n \times \left(1 - \frac{1}{p_1} \right) \times \left(1 - \frac{1}{p_2} \right) \times \ldots$ .
In the case of 100, the relevant prime numbers are 2 and 5, so we can calculate the answer very quickly: $\phi(100)=100 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5})=40$ .

Now, if we start with a prime number $p$ , then $\phi(p)=p-1$ ). How so? Well, no number between 1 and $p-1$ can share a factor with $p$ , since the only possible factors are 1 (which doesn’t count for present purposes) and $p$ itself, which is too big. For instance, all of 1,2,3,4,5,6 are coprime to 7, and so $\phi(7)=6$ .

Euler’s insight, then, was that the totient function might allow certain facts about prime numbers $p$ to be extended to any numbers $n$ , by judiciously replacing occurrences of $p-1$ with $\phi(n)$ . The context where he applied this idea was…

Fermat’s Little Theorem

In 1640, Pierre de Fermat had made the following observation about prime numbers: if $p$ is prime (e.g. $p=3$ ), and $a$ is any whole number not divisible by $p$ (e.g. $7$ ), then $a^{p-1}$ always leaves a remainder of 1, when divided by $p$ (in this case $7^{3-1} = 49 = 3 \times 16+1$ . We write this as $a^{p-1} \equiv 1 \textrm{ mod } p$ .

Fermat’s Little Theorem is a delightful result. It has also turned out to be amazingly useful and important, serving as the lynchpin of the public key cryptography on which we modern day internet users all rely. But Fermat – somewhat characteristically – never provided a proof. That had to wait for the later thinkers Gottfried Leibniz and Leonhard Euler. Euler not only proved Fermat’s little theorem, he extended it. Euler’s theorem says this: if $n$ is any number and $a$ is any number coprime to $n$ , then $a^{\phi(n)} \equiv 1 \textrm{ mod } n$ .

For instance, taking $n=8$ and $a=3$ (and remembering that $\phi(8)=4)$ it is true that $3^4=81=8 times 10+1$ .

This elegant, unexpected theorem has perhaps been rather eclipsed by Euler’s other magnificent achievements. I’ll end with a couple of open problems about the totient function:

Robert Carmichael asked: is there some number $m$ , where there is exactly one number (n) with $\phi(n)=m$ ? (If we replace ‘exactly one’ with ‘exactly two’ or ‘exactly three’, etc., the answer is yes!)

We know that $\phi(p)=p-1$ for any prime number $p$ , and it is fairly easy to see that this can only hold if $p$ is prime. A weaker condition is that $\phi(n)$ should divide $n-1$ . Derrick Lehmer asked whether there is any non-prime number which satisfies this. None is known so far!

[1] Update: since my last blog reboot, I am no longer using MathJax,but the WordPress.com Latex support.

A rhopalic sentence

Posted by richardelwes on April 4, 2013

Posted in: Nonsense, puzzles. 2 Comments

A rhopalic sentence is one in which each word is longer (usually by exactly one letter) than the last. Here’s my effort:

I am not very happy around strange abstract paintings, preferring portraiture; contemporary postmodernism underestimates picturesqueness, antagonistically mischaracterizing bourgeoisification, exhibitionistically, overenthusiastically overintellectualizing nonrepresentationalism.

The Power of Spin

Posted by richardelwes on March 27, 2013

Posted in: Crankishness, Nonsense, Stats. Leave a comment

A dialogue:

A. Imagine that you could lift up into the air, and soar through the sky, just by gently fluttering your arms.

B. Yes, I’ve dreams like that. Lovely.

A. Where would you go?

B. Hmmm… I’m not sure. Maybe a cruise over the ocean to Rio?

A. What?? You seriously think you can flap your way to Brazil? What sort of lunatic are you?

As verbal entrapment goes, it’s hardly very clever or subtle. But A-san’s logic is identical to that from a recent Church of England press release.

The Church commissioned a survey which asked

“Irrespective of whether you currently pray or not, if you were to pray for something at the moment, what would it be for?”

19% of their interviewees were unwilling or unable to address this hypothetical scenario, either saying that they never prayed or that they didn’t know.

On the strength of this data, the Church announced that “Four out of five British adults believe in the power of prayer”, a statistic which is now making its way through the UK press.

I have just written to the CoE press office, reminding them of the Ninth Commandment: “You shall not bear false witness against your neighbour”.

The Maths that Makes the Modern World

Posted by richardelwes on March 22, 2013

Posted in: Elwes Elsewhere, Technology. Leave a comment

I was invited to give this year’s WP Milne lecture at Leeds Festival of Science. Professor Milne was a maths teacher at Clifton College, before going on to become the head of Leeds University’s maths department. In honour of this slightly unusual career path, the annual Milne lecture is delivered to an audience of sixth form students (aged 16-18), as well as to the members of the Yorkshire Branch of the Mathematical Association.

I was delighted to be asked, both as a general honour, and in particular because I have also spent a (very) little time teaching in schools, before migrating to the university sector.

I spoke about The Maths that Makes the Modern World, and divided my talk into two halves: on the simplex algorithm for linear programming, and on Google’s Pagerank algorithm, topics also covered in my book.

The Will Rogers Phenomenon

Posted by richardelwes on December 1, 2012

Posted in: puzzles, Stats. 3 Comments

“When the Okies left Oklahoma and moved to California, they raised the average intelligence level in both states.”

– Will Rogers

In statistics, the Will Rogers Phenomenon, named after the 1920s comedian who made that jibe, occurs when moving some element from set A to set B increases the average (mean or median) of both A and B.

It sounds impossible, but can actually happen quite easily. For example, A={4,5,6} & B={1,2,3}. If 4 migrates from A to B it’s pretty clear that both averages increase.

This has caused a certain amount of confusion over the years, for example in medicine. In this paper, doctors were trying to understand what had happened to cause the average life-span of certain groups of cancer patients to rise. The answer appears to be that a change in diagnostic technology led to a Will Rogers situation.

Oversimplifying considerably, patients were classified as “slightly ill” or “very ill”. Improvements in diagnoses then meant that some people who would previously have been classified as “slightly ill” were instead picked up as being “very ill”. This increased the average lifespan of the “slightly ill” group, as it were, by removing its illest members. But it also increased that of the “very ill” group because the new members were not as ill as those diagnosed “very ill” under the old system.

The confusing thing, of course, is that both groups see their average lifespan rise – which sounds wonderful. But it’s something of a mirage, because this could all happen without any individual seeing a longer life expectancy.

In praise of Pick’s theorem

Posted by richardelwes on September 8, 2012

Posted in: Education, Elwes Elsewhere, Geometry. Leave a comment

Should Pick’s theorem be on the A-level maths syllabus? In a blogpost at the De Morgan Journal, I argue that it should.

As easy as 123…

Posted by richardelwes on September 4, 2012

Posted in: Maths, Number theory. 1 Comment

In a paper with the unassuming title of Inter-universal Teichmuller theory IV: log-volume computations and set-theoretic foundations [pdf], Shinichi Mochizuki has released a purported proof of the ABC conjecture. This would be huge news if correct, as this single conjecture is known to imply all sorts of exciting facts about the world of numbers. Proposed by Joseph Oesterlé and David Masser in 1985, its most famous consequence is Fermat’s Last Theorem… but of course that has already succumbed to other methods. So, to give a flavour of its power, I’ll discuss another: Pillai’s conjecture.

This starts with the observation that the numbers 8 & 9 are rather unusual. They are neighbours which are both powers of other positive whole numbers: 8=2³ and 9=3². In 1844, Eugène Catalan conjectured that this is the only instance of two powers sitting next to each other, a delightful and surprising fact which was eventually proved by Preda Mihăilescu in 2002.

However, a host of related questions remain unanswered. What about powers which are two apart, as 25 (=5²) and 27 (=3³) are? Or three apart, as happens for 125 (=5³) and 128 (=2⁷)?

In 1936 Subbayya Pillai conjectured that for every whole number k there are only ever finitely many pairs of powers exactly k apart. But so far the only case this is known is for k=1, i.e. Catalan’s original 8 & 9.

A proof of the ABC conjecture would confirm Pillai’s conjecture for all the remaining values of k at a stroke… and a great deal else besides. So watch closely as the world’s number theorists now descend on Mochizuki’s paper!