Proof that I am a *pure* mathematician

I have always been drawn towards pure, rather than applied, mathematics.  As a student I had no feel for mechanics: I could solve the equations but I had no physical intuition. I always felt out of my depth in any kind of applied mathematics, whereas I felt at home with abstract pure mathematics.

Now when I teach mathematics I have sometimes regretted my preference.  I see the value of physical applications; I enjoy reading about relativity and quantum theory, and feel that I have gained some understandings of these topics to which, thirty years ago, I couldn't relate at all.

Now I have been looking at Mark Levi's two marvellous books, The Mathematical Mechanic and Why Cats Land on Their Feet.  These are books about mechanics.  The former uses physics to "prove" pure mathematical propositions, for example using an argument about a rotating fishtank to "prove" Pythagoras's Theorem.  (The inverted commas reflect my pure mathematical reluctance to accept that physics can be used in this way!) The latter presents physical paradoxes and their resolution - for example, if, sitting in a seat attached rigidly to the frame of a spacecraft which is stationary in outer space, I push a balloon away from me, what happens to the spaceship?

These books are wonderful.  Despite my comment about physics and proof above, I find the contents beautiful and astonishing.  But they are also over my head.  I have to read carefully and think deeply to get the point, and I need to be told why the paradoxes in the second volume are paradoxical because my physical understanding is so limited I don't "get" it easily. 

So what these books confirm is that I have very little intuition about the physics of the world around us.  Had I had a different upbringing that might not have been the case, but I have to accept that my mathematical talents do not extend at all to mechanics.  I don't particularly regret that - the pleasure of pure mathematics compensates - except when I realise that my appreciation of Levi's books is so limited. I feel as I imagine someone would respond to Matisse who knew the paintings only from monochrome reproduction - there is much to enjoy but I will never be able fully to appreciate them.

This helps me understand why I enjoy quantum theory.  I can't do mechanics because I have no physical intuition - but quantum theory makes a nonsense of our intuitions so my weakness isn't a problem!

Can I finish by encouraging any reader to seek out Levi's books, if you don't already know them.  If you're an applied mathematician you'll love them; pure mathematicians will also find things to wonder at.  Even if I can't fully appreciate them, I can still admire and enjoy.

Maths and technology - from the HE Maths Ideas Exchange

This post is late because I spent an exciting but exhausting weekend in Sheffield, first at the CETL-MSOR conference on mathematics teaching in HE and then at the Ideas Exchange weekend organised by Peter Rowlett of the MSOR Network.  Both were extremely productive, not just for the inspiring presentations but also for the informal discussions with colleagues from across the sector.  I'm very grateful for the valuable and productive conversations I've had over the last few days, and especially to Dagmar Waller and Peter Rowlett for organising these events.

The Ideas Exchange provides an opportunity for each participant to put forward, in five minutes, an idea for subsequent discussion with sympathetic colleagues.  It was suggested that this might be something which one had tried and wished to share, an idea that one was planning to implement and wanted advice on, or a mad suggestion that, with refinement and suggestions from others, might just turn into something workable.  This was the second such Ideas Exchange weekend - my report on the first was published in MSOR Connections (and one of the best pieces of news from the CETL-MSOR Conference is that Connections will continue).  That they work so well is due to the openness and friendliness of the participants: it's a delight to spend time with people so committed to teaching mathematics effectively.

There is a lot I could write about from both events (and much that I have still to digest).  But this post will focus one of my "ideas" - not actually mine at all, in fact.

At my University's teaching and learning conference one speaker mentioned a proposal that every degree course should have a compulsory final year module on "how new technology will change this subject" or something similar.  (I didn't catch the name of the person to whom this proposal was attributed.)  Should maths degrees contain such a module?

My first reaction was that it would be hard to make a case to colleagues for dropping their favourite courses in Complex Analysis or the Analytical Algebraic Topology of Locally Euclidean Parametrization of Infinitely Differentiable Riemannian Manifolds or whatever.  These courses obviously give students skills and techniques which are immediately valuable to a wide range of employers in a way which thinking about possibly applications of technology and mathematics could not possibly match.  

But should our maths graduates be thinking more about how technology will change mathematics?  I think there is a case.  For one thing, new technology such as apps on mobile devices are making like better in many small (and some big) ways.  I'd like our maths graduates to be among the leaders in this field, but I'm not sure that our teaching particularly promotes this kind of creative thinking.  I'm also struck that, despite many university mathematicians' preference for chalk and blackboards, IT is changing maths in ways which we don't articulate to our students. At BMC last year Sir Timothy Gowers noted that Wikipedia is an invaluable tool for mathematicians, greatly facilitating the practice of our subject.  In his recent LMS Popular Lecture Sir Timothy talked about the emergence of computers as research assistants.  He, Terence Tao and many others use blogs as a tool for mathematical collaboration, and Gowers's Polymath project is perhaps shows how mathematics will be done by humans in the years before the field is taken over by creative computer research mathematicians.

It certainly seems to me that my childhood view of mathematics as an individual activity, which was perhaps only rarely a reality (Andrew Wiles?), is no longer tenable: technology is making mathematics an increasingly collaborative venture.  And we should perhaps be making more of this in our undergraduate teaching.

Mathematics and Tennis

Now that a fascinating fortnight at Wimbledon has finished, it's perhaps appropriate to consider the contributions that the mathematics of tennis made to our enjoyment.  I've read long ago (I forget where) an analysis that shows that the scoring system at tennis - dividing the match into games and sets - is remarkably effective at maximising the interest for spectators, creating points of excitement throughout the match: simply counting up the total points won wouldn't be nearly so exciting.  As I recall, the argument is that this is why tennis attracts a bigger audience than other racket sports.

The opening chapter of Julian Havil's wonderful book Nonplussed presents three tennis paradoxes.  The best (most surprising) of these is that if you are playing a strong server (the probability that the server wins a point on their serve is just over 90%) then you are more likely to break serve from 40-30 or 30-15 down than you are at love all.  (There is an assumption that the probability of winning the point is independent of the score.)

Of course in any knock-out tournament, even if the better player wins every match it is by no means certain that the top two players will meet in the final.  If they are in the same half of the draw, they meet earlier and, in a random draw with 2^n players, the probability of that is (2^(n-1)-1)/((2^n)-1) which is only just under 1/2.  Seeding addresses this problem.  But seeding can create its own issues.  Suppose we have three top players, equally good, all some way better than any of their other competitors.  Then two will be in the same half of the draw, and the third will have double the chances of winning of each of the other two.  If this victory is then used to determine the seeding for the next tournament, that player will carry this advantage forward, and will win more tournaments than their equally-good adversaries.

The system for challenging line-calls brings in a new dimension.  In each set each player can make at least  three challenges when they believe a ball was wrongly called out (or in).  Successful challenges don't count, but unsuccessful ones are deducted from the allowance of three.  If the call is shown to be wrong, then depending on the circumstance the point is replayed or the point is won by the player challenging.  The challenge must be played immediately - if you think the ball was out and you return it, you've lost your right to challenge.

How sure do you have to be that the call was wrong before you should challenge?  There are obviously a lot of factors that influence the decision.  How many challenges one has left - presumably one wants one in reserve for the dubious call in the decisive game still to come.  The stage of the set - if the set is almost finished and you haven't used any challenges, there is little to be gained by saving them.  The importance of the point - if the disputed call is resulting in a crucial service break you might challenge even if you are sure the call is correct!  The gain from a successful challenge - if you are going to win, rather than lose, a point, the challenge is more worthwhile than if you are going to replay it.  Yesterday Andy Murray challenged a call that his first serve was out - would that be a better challenge than a second serve called out?  I would guess that the threshold estimate of probability of success before you challenge is strongly affected by all these circumstances.

There are other factors too.  Sometimes you might just want a moment to regroup, and it might be worth using a challenge just to get a short break. And how do you decide whether to challenge or to play the ball?  If you think your opponent's shot is just out, but you can return it, do you stop and challenge or do you play on?  The decision must be made instantly!

It would be fascinating to now how much professional tennis players think about these things when using their challenges.  I doubt if they do probability calculations in their heads, so do they have heuristics and if so, how good are they?  Are some players better tacticians in using challenges than others?

The LMS Popular Lectures - Gowers and Penrose

Last week was exceptionally busy, but one highlight was the opportunity to hear two of today's greatest mathematicians, Sir Timothy Gowers and Sir Roger Penrose, deliver the London Mathematical Society's Popular Lectures in central London.  (There is another opportunity to hear them in Birmingham on 26 September, and the lectures are normally made available on DVD).

This was a wonderful opportunity to hear two top mathematicians talking about their views of mathematics. Both talks took their theme from the Turing centenary, a reminder of just how important a contribution Turing made to the culture and practice of contemporary mathematics.

Gowers was talking about the possibility of computers becoming mathematicians, in the sense of creating and proving theorems.  He was particularly interesting in his analysis of two fairly well-known mathematics puzzles which can be solved by the right insight.  What Gowers did here was to show how these insights can be understood, not as a sudden creative spark from nowhere, but as the consequence of an understandable line of mathematical thinking.  This was fascinating, and empowering: these kind of insights don't need incomprehensible strokes of brilliant genius but could be accessible if you think hard enough about the problem.

Gowers predicted that in 50 years time computers will be able to do mathematical research better than humans.  He didn't discuss how mathematicians will react to this.  If pure mathematics can be created by humans, will people still want to do it?  This kind of mathematics is already an esoteric pursuit: if one is doing world-leading pure mathematics it is unlikely that more than a small number of people are actively engaging with your work.  If computers are doing it better, will human mathematicians still see it as a worthwhile activity to devote their life to?

Penrose talked about consciousness.  His argument, as I understand it, is that human consciousness is not subject to the limitations that Godel's Theorems show apply to formal systems, and that we need a new theory that goes beyond quantum theory in order to understand consciousness.  He presented a toy model universe to show that the universe need not be computable - the toy model certainly proved that it is possible to have uncomputable universes - but I am unconvinced by his arguments.

Although I am not qualified to disagree with Penrose, who knows much more and has thought much more deeply about these subjects than I do, I don't think his arguments are valid.  I do not understand why he thinks Godel's Theorems do not apply to human thought.  His assertion seems to be based on a claim that humans can always jump "outside the system" to see implications that are not formally consequences of a logical system, so there can be no "Godel sentence" that is true but which human consciousness cannot prove to be true.  I don't understand why he can be confident of this, so I don't see that consciousness presents a problem for quantum theory.  Nor do I share the worries he expressed that the Measurement Problem in quantum theory.  Everett's interpretation, that we view only one branch of the universal wavefunction, seems to me to be a perfectly logical solution to the Measurement Problem - we don't have to accept it, but it does show that a solution is possible, in the same way that Penrose's toy model uncomputable universe makes its point.

Regardless of whether .I was persuaded by the speakers, this was an exciting and stimulating evening which kept a huge audience engaged for the whole of a long evening.  Well done the LMS!

In praise of Knuth - the joy of algorithms

Since I am taking part in a Turing-related Lates evening at the Science Museum on Wednesday 27 June, in which my contribution will look at a curious mathematical algorithm and its applications in computing, I have been thinking about some of the algorithms I have used in programming, and this post will describe one particular favourite (not the algorithm I will be demonstrating on Wednesday).

I used to be a keen bridge player.  Sometimes in competitions hands were "computer-dealt" and people noticed that the card distributions seemed to be less regular than in hands shuffled and dealt physically.  Good players even adjusted their play according to whether the hand was dealt by a human or a computer.  The moral is that human shuffling isn't perfectly random.

Anyway, I wanted to programme the shuffle of a pack of cards so that I could use computers to explore strategies for playing various forms of patience ("solitaire" to Americans).  In particular a student project verified that the probability of clock patience coming out is indeed 1/13, as I had proved as a schoolboy.  How do you get a computer to shuffle a pack of cards (or equivalently to generate a random permutation of the numbers 1 to 52, or more generally 1 to n)?  (In this post I am using "random" to mean that all possibilities are equally likely, which is what one hopes for in shuffling cards.)

I thought the obvious approach was to generate successive random (equally likely) integers between 1 and n, simply rejecting those that had already been drawn.  As we go through the shuffle, we are more and more likely to generate random numbers corresponding to cards already dealt, so towards the end it can take a long time to find an undealt card - when there is only one number left to be drawn, the probability of hitting it is only 1/n and the expected number of draws required to get it is n.  In practice this algorithm seemed to work OK for a pack of 52 cards - the probability that it takes an absurdly long time to get the last few cards is in fact quite small, and some clumsy ad hoc adjustments could improve it.  The result was a messy piece of code which might take some time to complete the shuffle for a large pack.

Then a colleague (thanks, Don) told me about Knuth's shuffling algorithm (which it turns out is a variation of one devised by Fisher and Yates before the computer era).  It's beautiful.  To shuffle n cards, you simply do the following: for i between 1 and n, we successively swap card i with a random card in the pack.  It's easy to see that the result is a random permutation of the pack and that all possible permutations are equally likely.  We have a simple algorithm, very easy to programme, that generates a random shuffle in a fixed number of steps. 


One of the joys of mathematics can be finding that there is a beautiful, simple solution to a problem on which one has spent a lot of time working with messy, unsatisfactory methods.  This was such an example.  I remember how happy I felt when I learned about this algorithm! 


Of course, the downside is that I am reminded that people like Knuth always seem to produce beautiful, simple algorithms in contrast to my clumsy efforts.  It's a bit like watching Messi play football - how many can aspire to play like that? - except that I am left with the frustrating feeling that I should have been able to come up with the algorithm myself.  Luckily perhaps I have now reached an age where I can appreciate beautiful mathematics without beating myself up over my failure to do it for myself.

When conceding a goal doesn't matter

As a follow-up to yesterday's post, here's more on the maths of football tournament mini-groups.

In last night's UEFA Euro 2012 matches, Croatia played Spain and Italy played Ireland.  Because Ireland had lost both previous matches and the others had been drawn, it was likely that the tie-breaking rules would come into effect and the score in the Croatia-Spain match would be crucial.  Assuming Italy beat Ireland, the winners of Croatia-Spain would go through and the losers would be out.  Croatia and Spain would both qualify if they drew 2-2, Spain and Italy if the result was 0-0, while if Spain and Croatia drew 1-1 then Italy would have to beat Ireland by two goals and score three times to deny Croatia.

So we're in the last couple of minutes of both matches, Spain and Croatia is goalless and Italy lead Ireland 1-0.  At this point Spain and Italy are on course to qualify. Croatia need a goal, but the interesting thing is that conceding a goal doesn't damage Croatia.  In fact Spain score just before the end, but Croatia need to score just one goal to go through, and the Spanish goal makes no difference to them.   At this point there is no likely situation in which a 1-0 win for Croatia is better for them than a 1-1 draw, unless Italy were to score two more goals in injury time.   (In fact Italy scored one more to win 2-0 so perhaps that wasn't an impossible scenario.)

Indeed, perhaps Croatia are more likely to score if Spain have scored, since Spain are likely to be less worried about conceding an equaliser which won't put them out.

Spain's goal did change the order of the top two in the group, but, coming when it did, it made no difference at all to Croatia's chances.

I am reminded of the Scottish Premier Division 1990/91.  Rangers and Aberdeen are fighting it out with two matches left.  In these days it is two points for a win (not three) and one for a draw, and if two teams finish level then the deciding factor is goal difference, with goals scored then being decisive if both teams have the same goal difference.  The last match of the season is Rangers against Aberdeen.  With two matches left, Rangers are two points above Aberdeen.  Aberdeen are winning their penultimate match but, in injury time, Rangers are trailing Motherwell 1-0.  If it finishes like that, the teams will go into their last match level on points.  Rangers will have scored 60 and conceded 21, Aberdeen have scored 62 and conceded 25.   Rangers' goal difference is better and they need only draw the last match against Aberdeen to win the league.

So what do Rangers do?  They throw caution to the wind in seeking an equaliser.  Had they got an equaliser they would have gone into the last match a point above Aberdeen, and needed a draw to win the league.  So  scoring an equaliser would not have benefited them in the slightest: they need exactly the same from the last match as if they lose 1-0 to Motherwell.  But in fact the reckless attack allowed Motherwell to score twice more in injury time.  Rangers lost 3-0, their goal difference is now the same as Aberdeen's, they have scored fewer goals, and now they need to win the final match if they are to win the championship.  The reckless pursuit of an equaliser which could make no difference has actually made the league title much harder to win.

(Rangers beat Aberdeen 2-0 so this mathematical madness didn't actually cost them the championship.)

The maths of "The Group of Death"

Tonight Spain play Croatia in the UEFA Euro 2012 football tournament.  At this stage teams are playing in groups of four - each team plays each of the other three (six matches) - with the top two in each group progressing to the next round.  The results of the first four matches mean that if Spain and Croatia draw tonight and both teams score at least twice, then Italy are knocked out whether or not they win their match against Ireland.

While sporting integrity (a strange concept currently being invoked in discussion about the future of Rangers in the Scottish Premier League) will ensure that Spain and Croatia both play to win, history suggests that if the score is 2-2 with five minutes remaining it would be irrational either side were to take risks in attempting to score a late winner.   A similar situation arose in 1982 when West Germany played Austria in the World Cup. A one-goal victory for the Germans would ensure that both sides progressed.  West Germany scored an early goal and thereafter, according to Wikipedia, "Onlookers noted that both teams played as though they were content with the result", the 1-0 outcome seeing both teams through at the expense of Algeria.  There have been other examples in international and club matches.  Robert Axelrod writes about an English league match in his book about the Prisoners' Dilemma and the mathematics of altruism, "The Evolution of Co-operation".


In fact there is a lot of (relatively simple) mathematics in sporting league tables.  Quite possibly my interest in mathematics began around my eighth birthday in 1965 when Kilmarnock had to beat Hearts 2-0 in the final match to win the league on goal average (the ratio of goals for to goals against), a much more complicated tie-break mechanism than the goal difference used now.


The current rules for deciding ties in mini-leagues in tournaments like Euro 2012 is that, rather than look at goal difference over all matches, instead we look at results over the matches involving the teams who have tied.  So if A and B finish with the same number of points (3 for each win and one for each draw), and A won the match between A and B, then A finish above B.  This avoids the situation which eliminated Scotland in the 1974 World Cup, when all three of Scotland, Yugoslavia and Brazil beat Zaire while the matches between these three were drawn.  Scotland played the weak Zaire side first which meant that Brazil knew exactly how many goals they had to score against Zaire to finish above Scotland.


While the newer rules work well in some circumstances, they still give rise to situations like tonight's Spain-Croatia match.  


As a boy I loved mathematical puzzles based around sporting league tables - typically one was given an incomplete table and had to work out the results of every match.  These appealed to my twin loves of sport and logic.  I noticed however that on the final edition of Dara O'Briain's School of Hard Sums, when such a problem was presented, it didn't enthuse the students on the programme: perhaps these problems no longer have wide appeal.  Nevertheless I still enjoy the mathematics of league tables.


For example, (1) in mini-leaguers of four teams as in Euro 2012, can a team win two matches out of three and still not qualify for the next round?  (2) Can a team win one and lose two, and still not qualify?  (3)What is the smallest number of points with which a team can qualify?


Answers: (1) Yes if three teams win two matches and the fourth loses all three - this would have happened if Denmark had beaten Germany in the "Group of Death" last night, since Germany would have been out despite winning their first two matchers.  (2) Yes, if one team wins three matches and the other three each beat one of the others - this would have happened if Netherlands had beaten Portugal last night. (3) A team can go through with one defeat and two draws, if one team win all three matches and the other three matches are all drawn.


One point which was obvious when league tables were displayed during the TV coverage of last night's matches is that, under today;s tie-breaking rules, traditional league tables (recording numbers of matches, wins, draws,losses, goals for and against, and points) do not contain enough information to show which teams will qualify.  If both last night's matches had been drawn, Denmark and Portugal would each have had four points. Portugal would have finished second, and qualified, because they beat Denmark in the match between these two teams.  But one couldn't have deduced that from thr group table.  Exactly the same numbers could have arisen in the group table with Denmark beating Portugal and drawing with Netherlands, and Portugal beating Netherlands.  


So whereas once a group table gave all the information you needed to decide the order of the teams, this is no longer the case.  How could we create an improved group table which actually included all the information we need?