A surprise in the world of prime numbers

The world of mathematics is buzzing with the news of a breakthrough in the theory of prime numbers by a virtually unknown mathematician named Yitang Zhang.  Prime numbers are numbers like 3, 5, 23, 97 which cannot be expressed as a product of two smaller numbers.  Prime numbers have been studied since the time of the Ancient Greeks and about 23 centuries ago the famous geometer Euclid discovered that there are an infinite number of them.  Since that time the study of prime numbers has produced some of the deepest results in the whole of mathematics yet these results are often very easy to understand (but the reasons the results are true are another matter).  

It is easy to see that 2 and 3 are the only consecutive prime numbers (because if you have two consecutive numbers one of them must be even but 2 is the only even prime number).  What about prime numbers differing by 2?  Here there are more: (3, 5), (5, 7), (11, 13) for example and there are many other so-called twin primes.  But are there are an infinite supply of twin primes?  Despite hundreds of years of research we don't know the answer to this innocuous question.

What about pairs of prime numbers that differ by 4 (like (3,7) or (19, 23))?  We don't know if there are infinitely many such pairs either.  And if you replace 4 by any other even number at all we still don't know.  For example, we don't know whether there are infinitely many prime pairs that differ by 30 say (like 31 and 61).

Enter Yitang Zhang.  In his 50's he is definitely beyond the age where most mathematicians make their mark and until now he has been practically unknown.  After he got his PhD in 1992 he had found it difficult to get an academic job, working for several years as an accountant and even in a Subway sandwich shop.  But he never gave up doing mathematics and eventually was appointed at the University of New Hampshire.  There he pursued an unremarkable research career with no publication since 2001 but he was loved by his students apparently because he set easy exams.  Now he has burst onto the world's mathematical stage with a result that has surprised all the experts.  He has proved that there is some number k that "works" for prime pairs.  We don't know that k=2 or k=4; all we know is that k is less than 70 million.  And for this k, whatever it is, Zhang has proved that there are infinitely many pairs of prime numbers that differ by k.

The reason that this has excited mathematicians is that no result like this has ever been proved before and it gives some hope that the original prime twin problem might eventually be solved.  It is also a surprise result in that it hardly ever happens that a giant step like this is taken by such an obscure mathematician.  When it has happened before (such as for the Indian genius Ramanajuan) the newcomer is usually much younger since mathematics at its most creative is usually a young person's metier.

Zhang's theorem probably won't have much practical use.  If you like problems about ages and birthdays here's a consequence that might be appealing.  Somewhere, sometime, there were two mammals of different ages and there will be an infinite number of years when both their ages are prime numbers.  Might there be two human beings with this property?  We don't know because humans haven't been around for 70 million years whereas mammals have.

Freedom of information: a window?

You may not agree that the glory days of newspaper journalism are long gone.  Perhaps you think that the Washington Post's Watergate investigation which led to the eventual resignation of US President Nixon was less than stellar reporting.  Maybe you think that the meek way almost the entire mainstream media accepted the US and UK lies about Iraqi weapons of mass destruction as an excuse to go to war was an isolated collective error of judgement.  If so, you and I have quite different opinions on the way that newspaper reporting has changed over the years.

But perhaps we agree on something else: that the Wikileaks revelations told us things about how the US conducted its wars in Afghanistan and Iraq, and how its emissaries around the world conducted business with foreign powers gave us an unprecedented grandstand view of events that most of us never hear about.  Perhaps you think, along with Senator Joe Lieberman, that the leaks were "outrageous, reckless and despicable" but I hope you would fall short of Sarah Palin's call to pursue Julian Assange with the same urgency that Al-Qaida leaders were pursued, or Congressman Mike Rogers' threat to have foreign national Assange executed for treason against the US.  Nevertheless the scale of what we learnt via Bradley Manning and Julian Assange cannot be denied.

The point of this post is not to persuade you to my view (that Manning and Assange are among the great heros of our time).  It is more to alert you to the fact that, if you care about knowing what is going on in the world, you have just lived through a short period where we the people had information about how great powers operate of a magnitude that we might not see again for a very long time.

The intense efforts that the US and UK governments went to in order to suppress events in the Afghan and Iraqi wars, and the publication of US diplomatic cables tell us how much they were embarrassed by the Wikileaks collaboration with the Guardian and other newspapers.  I have no doubt that they have ramped up their security to prevent a repeat.  In any case the US retaliation against Manning has been so severe that other potential leakers of his persuasion might well think again (certainly Julian Assange himself is in no hurry to be extradited to Sweden in case he is handed over to US authorities).  Furthermore the US authorities are now pursuing the Associated Press organisation by subpoena-ing phone records that might bear on the CIA successfully thwarting a plot by al-Qaeda in Yemen to blow up a U.S. jetliner (this is not the first such aggressive subpoena act).

So don't expect anything as informative as the Wikileak bonanza to strike again for a very long time.
Therefore my take home message is this.  Have a good luck at what we already have.  You can go to the Wikileaks web site itself.  However you might find this is more than you can handle!  It is vast.  Instead you might try the Guardian site which is very well-organised and will tell you also a lot about the politics associated with the reaction of the US and the UK.

A serious case of poor economic analysis

In this post I want to give some more publicity to a story that has, so far, only been run in specialised economic news columns.  It is a dramatic one that suggests much of the world has taken a wrong financial turn partly because of one influential academic paper, around which there are now some serious questions.

Two economists,  Carmen Reinhart and Kenneth Rogoff at Harvard University, released a paper in 2008, “Growth in a Time of Debt.” whose main conclusion was that countries whose public debt was over 90% of their Gross Domestic Product have below average growth rates, slightly negative in fact.  Their paper has been widely cited (454 Google Scholar citations as of 21 April, 2013).  In addition it has been used by government exchequers to justify severe austerity measures.  The most significant such example is when Paul Ryan, the Republican chair of the US House of Representatives budget committee, a notable economic hawk who has pushed for rapid fiscal tightening, cited the Reinhart-Rogoff paper as “conclusive empirical evidence that total debt exceeding 90 per cent of the economy has a significant negative effect on economic growth”.  In addition, as reported in the Guardian, British Chancellor George Osborne has repeatedly said that his monetary policy was highly influenced by the paper.

Last week there was a bombshell.  Three researchers from the University of Massachusetts, Thomas Herndon, Michael Ash, and Robert Pollin, published a paper "Does high public debt consistently stifle economic growth" which seriously undermined (some have said "tore to shreds") the Reinhart-Rogoff conclusions.  The new paper challenges the Reinhart-Rogoff methodology in two ways: by criticising the ways in R&R excluded some data that did not accord with their conclusion, and by criticising how they weighted their summations.  You can read the actual details in the source articles.  More sensationally, Herndon et al found an error in the spreadsheet that R&R had used to construct their main summative table.

In their response R&R who were obviously deeply embarrassed by the spreadsheet error nevertheless argued that their main conclusions were still sound and a debate is now beginning between the two sides.  So far Herndon et al robustly maintain that the R&R study is not only flawed in the way that they originally claimed but that the results are almost the opposite of those claimed by R&R.

I hope that the debate does not simply recede into exchanges between academics guarding their reputations.  This issue is of fundamental importance to the way in which we regulate our economies.  I am so far dismayed by the entrenched attitudes of those who originally espoused the R&R conclusions.  In particular the response from George Osborne's office has been abysmal - just a claim that their economic policy does not rest on one academic paper and that "the majority of economists" back Osborne's strategy.

It seems to me that economists, and the entire discipline of Economics, faces a challenge.  They need to sort out for policy-makers just what the situation is vis a vis debt versus growth.  I know this might be a big ask but they must do their level best.  If we see two camps emerging divided by political affiliations we would be tempted to kiss goodbye to any pretence that Economics is a science.

Prime conjunctions

I have 4 children and around 10 years ago their ages were 17, 23, 29 and 31.  This period lasted only for a few weeks until one of them had a birthday but I made much of it at the time for these ages are all prime numbers.  One day they will be 47, 53, 59 and 61 - another prime conjunction and I hope I shall still be around to celebrate it.  I will definitely miss the next (and so will they): 167, 173, 179, 181.

Of course I am extraordinarily fortunate in having so wonderful a quartet of children.  Am I fortunate in another way:- that their ages allow such prime conjunctions?  We shall soon see.

Let's consider a set of n children (think of n as being 2, 3 or 4 if you like).  How likely is it that one day they will all have prime ages?  I'm going to simplify matters in three ways.  The first simplification is really unnecessary in practice: it is that we'll assume no two children were born at exactly the same time of day on the same day of the year.  The second simplification is that we'll only worry about odd primes.  Ignoring the prime 2 is not such a big deal.  This special case is actually quite significant if you are just interested in whether the children have a prime conjunction at all but not if you are more concerned with whether they have lots of them.  The third simplification is apparently quite bizarre but at the end of the post I will explain that it is not as bizarre as all that - so bear with me.  This simplification is that rather than thinking about prime conjunctions we think about occasions (odd conjunctions) when all the children's ages are odd.

We want to think about their ages and we have to write down these ages in some order.  Rather than that order being highest to lowest or lowest to highest I shall write them down in order of birthday throughout the year.  For example three children born on 2 March 1991, 6 November 1994, 4 May 1997 will be ordered  with the March birthday coming first, then the May birthday, then the November birthday.  So, at the beginning of this year, their ages were 22, 15, 18.  These remain their ages until 2 March when the 22 becomes 23.  Another change (from 15 to 16 occurs on 4 May) and another change occurs on 6 November.

In terms of evenness and oddness it was Even, Odd, Even at the beginning of the year and then it went
Odd, Odd, Even
Odd, Even, Even
Odd, Even, Odd
and, continuing to track the changes in 2014,
Even, Even, Odd
Even, Even, Odd
Even, Odd, Odd
and then we come back to
Even, Odd, Even

Put more concisely we begin with a list of E's and O's.  We change the first one, then we change the second, then we change the third, and then we go back to the start of the list and change the first (then the second, then the third).
EOE, OOE, OEE, OEO, EEO, EOO, EOE
and now the cycle repeats.

For this particular set of birthdays we never find OOO so these children are never all of an odd age (and therefore never all odd prime ages (as it happens, it doesn't matter in this case whether we allow the prime 2)).

OK.  Let's jump to the general case.  Now we have n children.  As before we list their evenness or oddness of age by order of their birthday.  Suppose at the beginning of the year that gives us a bunch of evens followed by a bunch of odds.  At some stage in the year those initial evens will all have changed to odds and all of them will be an odd age.  Instead suppose at the beginning of the year we have a bunch of odds followed by a bunch of evens.  Part way through the year everyone will now be even and so, a year later, everyone will be odd.

But what if we don't have one of these types of initial odd/even lists.  If that happens then either we begin with an even, later in the list we have some odd, and still later we have another even (or we might have a similar case with the roles of evens and odds exchanged):
E ... O ... E ...
We start our process of changing the evens and odds one by one from the beginning.  It is easy to see that, no matter where we are in the process, the three symbols at these places cannot all be equal; so we can never get all odds.

It is not too difficult to work out that 2n even/odd lists have the property that they consist of a bunch of one type (even or odd) followed by a bunch of the other type (odd or even).  But there are 2ⁿ sequences in all.  So what that means is that, with n children, the chance of their having an odd conjunction is n/2^n-1.  And notice that if they do have an odd conjunction then they will have others at two-yearly intervals - so many of them.

Therefore, given that I have 4 children, the chance of them having an odd conjunction is exactly 50%.

But, wait a minute, I began by asking about prime conjunctions!  All I have done is analyse the chance of getting an odd conjunction.  The passage from odd to prime leads us to some deep unsolved questions in number theory.

Suppose I have two children with the younger born between 1 and 3 years after the older.  Then some of the time their ages will differ by 2 and every two years there will be a period when their ages are both odd.  These children will have many prime conjunctions, the first few being (3, 5), (5, 7), (11, 13), (17, 19).  The Twin Prime Conjecture states that there are infinitely prime conjunctions in this case (prime numbers differing by 2).  It is a very long-standing unsolved problem and most mathematicians believe it is true.

What if I have two children born more than a year apart?  Then every two years their ages will differ by an even number k.  Now we are in the realm of Polignac's Conjecture: whether there are infinitely many primes that differ by some specific even integer k.  With more than two children we come to an even more general conjecture by Dickson.

What all this means is that if your children do not have an odd conjunction (and we have seen above how this may be tested, and how likely it is) then you will never see a prime conjunction. But, more usefully, if you are looking for a prime conjunction, you should first find an odd conjunction (if any) and then starting adding two to it repeatedly hoping to find a set of odd numbers that are indeed all prime. This is not guaranteed (e.g. 7, 9, 11 - all increments include a multiple of 3). However Dickson's theorem (which I will write about in a future blog) provides some refined help if needed. Finally, unless a large number of mathematicians are going to be very surprised indeed, if your children have "several" prime conjunctions, they will have infinitely many prime conjunctions.

Update 22 May 2013

The mathematical world is buzzing with the news that a virtually unknown mathematician Yitang Zhang at the University of New Hampshire has proved that there is a number k<70,000,000 for which Polignac's conjecture is true.  So we know now that somewhere sometime there must have been two mammals (because mammals go back more than 70 million years) who enjoy an infinite number of prime conjunctions.

From Daniel Ellsberg to Bradley Manning

When I post a blog entry I like to have something more to say than just a rehash of known facts.  But today I don't.  I write out of rage for the treatment of Private Bradley Manning, a hero who has put his freedom in jeopardy for principles that all of us who value honesty and decency should share.  Manning is currently on trial for sending to Wikileaks material about the war in Iraq and Afghanistan.  The most infamous disclosure was footage of a US helicopter firing on civilians in Baghdad with a voice-over from the operators whose vicious delight in killing their victims is evil and sickening.  The material he released seems not to be compromising to US military strategy, nor to endanger the lives of serving personnel; but it gives a perspective on US thinking that must be deeply embarrassing for the High Command.

In my opinion Manning's actions should be applauded.  But, not only has he been put on trial, he has been treated with cruelty out of all proportion to the nature of the offences - including over a year of solitary confinement under brutal conditions.

Plus ça change, plus c'est la même chose.  Over forty years ago another whistle-blower, Daniel Ellsberg, was arraigned by the US courts.  His crime was to have leaked the so-called Pentagon Papers that contained the damning revelation that the US government had known years earlier that the Vietnam war almost certainly could not be won, had lied to the public and had continued to wage the war causing tens of thousands of US deaths.  At Ellsberg's trial it came to light that, in an attempt to discredit him, the US administration had broken into the office of his psychiatrist and had installed illegal wiretaps.  As a result of this incredible persecution the judge threw out all charges.

Both Ellsberg and Manning broke the law.  Yet with the perspective of history the vast majority of us on all points of the political spectrum applaud Ellsberg.  Without his courage we would not have known about the crimes of the Johnson and Nixon administrations, and there would have been no Watergate.  But at the time Ellsberg was excoriated in the same terms that Manning is now suffering.  I am absolutely sure that history will judge Manning just as favourably as we now judge Ellsberg.

Finally, an interesting and uplifting postscript.  Daniel Ellsberg has had a distinguished career as a proponent of open government and in March 2011, two weeks before he turned 80, he showed that his passion for social justice burned just as brightly: he was arrested in a protest demonstration against Manning's incarceration.

The Swerve

I've just finished reading "The Swerve" by Stephen Greenblatt.  It's a fascinating account of how in the early 15th century a copy of "On the Nature of Things" by the Roman author Lucretius was discovered in a remote monastery.  The book is a powerful and passionate poem inspired by the Greek philosopher Epicurus and had long been thought to be lost forever.

Greenblatt brilliantly conjures up the atmosphere of late medieval Europe by writing about the life and times of the man, Poggio Bracciolini, who made the discovery.  He goes on to describe how the prevailing theology of the day was challenged by exposure to the ideas of Epicurus and makes a good case that "On the Nature of Things" was one of the drivers towards the more enlightened ideas we have today.  I encourage you to read "The Swerve" as Lucretius' original "De Rerum Natura" is possibly a little inaccessible unless you happen to be a Latin scholar.

For me the deepest impression was about the contrast between the philosophy of Epicurus and the teachings of the Christian churches.

We tend to think that "Epicurean" means unthinking abandonment to licentiousness.  But that completely distorts the Epicurean message.  Indeed that message does advocate that one should pursue pleasure.  However, the point of the pursuit is to live life to the full because this life is all there is.  So not only the bodily passions are important but also the passions of the mind and the satisfactions of creating and living out one's own thoughtful purposes.  Everything is made of atoms and when our body dies the atoms are reformed.  The soul is also made of atoms and it too does not survive our deaths.  Isn't that incredibly modern?

Contrast that with the central message of Christianity: bear your privations in this life so that you may enjoy the eternal one that follows (because if you don't you'll be enduring an infinite torment afterwards).  I literally shudder to think of how many lives have been blighted by this message.  How much effort has gone into refining the Christian dogma and imposing it on its adherents.  We could have begun the enlightenment 1700 years earlier if the Christian religion had not had the supreme good luck to be adopted as Ancient Rome's official religion.

But don't read my ranting: go out and buy Stephen Greenblatt's masterpiece.

Deductive and inductive inferences 2

In my last post I extolled the virtues of inductive inference and I verged on claiming that it was a more useful tool than deductive inference.  In this post I want to say something about deductive inference, where its strengths lie, and comment on why its use is sometimes more difficult than we expect.

In its purest form deductive inference starts with various statement known to be true, carries out a logical sequence of steps using these statements, and arrives at one or more further statements.  If the initial statements really are true and the reasoning steps are logically valid then the new statements will also be true.  Further deductive inferences can then be made starting from these new statements and, repeating this many times, very long chains of deductive inference can be created.

Mathematics is just a collection of these inferential chains.  Deep Mathematics is when the chains are long and 'good' Mathematics is when the resulting statements are deemed to be interesting (which is often a subjective judgement).  This pure form of deductive inference does occur outside Mathematics but usually the inferential chains are very short; however, when it can be used, it has the edge over inductive inference in that the statements it arrives at will be believable beyond doubt.

However, in my previous post I promoted both deductive and inductive inferences as ways of making good judgements, or making good decisions as often as possible.  The pure form of deductive inference described above seems to be an 'all or nothing' process (and, in that case, will usually be a 'nothing' process because if even a single one of the links in the inferential chain cannot be made then the final result will be worthless).

What rescues deductive inference from being largely useless outside Mathematics is the notion of probability which gives us a way of ascribing a likelihood of truth to the conclusion we have reached.  This is not the place in which to write about probability but the sort of thing I mean can be appreciated by a simple example.  If I know it is 90% likely (probability 0.9) that my roses have black spot fungus and my fungicide has a 60% success rate (probability 0.6) at treating black spot then, by applying the fungicide I have a 0.9 * 0.4 = 0.36 chance of  my roses continuing to have black spot after applying the fungicide; therefore no black spot is a 1 - 0.36 = 0.64 chance.

If you didn't follow that, don't worry.  The main message of this post is that such reasoning is not easy because our brains don't seem to have a good intuitive grasp of probability.  Formal training in probabilistic assessment is almost essential in order to reliably calculate the odds that any particular event will occur.  It alerts you to the common logical fallacies but is definitely not a guarantee you will not fall into one.  The remainder of this post is a description of some of the counter-intuitive conclusions that you might come to in assessing the likelihood of an event.

The Birthday paradox.  

At a party or 24 or more people it is more likely than not that there will be two people with the same birthday.  Most people find this surprising.  The justification is no more than a few lines of probabilistic calculation but you have to know what you are doing.

The Monty Hall problem.  

A game show contestant is asked to pick one of three doors.  One of the doors conceals a valuable prize and there is nothing behind the other two doors.  The contestant makes their choice and then the game show host (who knows which door conceals the prize) opens a door that was not picked to reveal no prize behind that door.  The contestant is asked whether they wish to change their mind and go for the other unopened door.  Should they change their mind or not?

It is very tempting to believe that the contestant neither increases or decreases their chance of winning by changing and that the prize is behind either remaining door with a 50-50 chance.  In fact they double their chance of winning by changing their choice.  This so counter-intuitive that (see this Wikipedia article) almost 1000 PhD graduates, including the famous Paul Erdös, were fooled.

Boy girl combinations

If someone says to you "I have two children and (at least) one is a boy" what is the probability that they have two boys?  The logical trap is to reason that the remaining child is as likely to be a boy as a girl and therefore the answer is 50%.  In fact the actual probability of two boys is 33% (probability 1/3).  The reason that this problem fools people is that the 'sample space' (the set of equally likely different possibilities from which one has to choose) is not what, at first, you think it might be (indeed, this is often the pitfall that probability presents).  The sample space is BB, BG, GB (these combinations being the order by age of the children).  Only one out of three represents two boys.

See how subtle this is?  Had you been told "I have two children and the elder is a boy" then the 50% answer would have been correct.

But if you thought that was bad enough enough consider being told this.  "I have two children.  One is a boy born on a Tuesday".  Now what is the probability of there being two boys?  The answer is 13/27.  This astonishing answer is discussed in a  Science News article along with various caveats and is worth reading for reinforcing my warnings about the danger of trusting your probabilistic intuition.

If you are still with me but are beginning to feel that these apparent paradoxes are not important in the real world please think again.  We have to make decisions every day and most of the time we act with imperfect knowledge.  But that doesn't mean that we cannot improve the choices we make.  We have to realise that some choices are more likely to be successful than others, and that there are ways to find these successful choices more often than not.  The science of Probability is the key to such informed decision-making.  Should we eat organic foods?  Should we get a 'flu shot?  How much Life Insurance should we buy?  The list is long.  And we should remember that our gut feel about probability is very likely to be unreliable.