TRM intern and University of Oxford student Kai Laddiman speaks to St John’s College Computer Scientist Stefan Kiefer about the infamous million-dollar millennium problem: P versus NP.
You can read more about P vs NP here.
Perfect Numbers and Mersenne Primes
Perfect numbers and Mersenne primes might seem like unrelated branches of math, but work by Euclid and Euler over 2000 years apart showed they are so deeply connected that a one-to-one correspondence exists between the two sets of numbers.
Produced by Tom Rocks Maths intern Kai Laddiman, with assistance from Tom Crawford. Thanks to St John’s College, Oxford for funding the placement.
From aliens to bees via tattoos…
A short review of intern Joe Double’s work with Tom Rocks Maths over the summer of 2018. Written for the OUS East Kent branch who provided funding for the project.
‘First of all, I must thank you again for the grant, and for the warmth and friendliness at your event; it was an absolute delight to give my presentation and talk to your members, as it has been interacting with you in general.
I had the opportunity to work with one of my tutors over the summer to produce pieces for a general audience about complex mathematical topics. Without the help of the OUS East Kent group, I couldn’t have taken up this opportunity – with their grant’s help, I was able to afford to live in Oxford through a large part of the summer, allowing me to work in close contact with my tutor and use his studio for creating the videos and audio pieces I worked on. The OUSEK grant can be put to use far more flexibly than those from bigger schemes (which always have preconditions to meet about how the project will apply to industry, say), so I couldn’t recommend applying more if you have an idea for a project for your time at Oxford which is on the unusual side!’
Pieces I produced during the project:
Why do Bees Build Hexagons? Honeycomb Conjecture explained by Thomas Hales
A video I edited of Tom (my tutor) interviewing Thomas Hales about the mathematics behind beehives.
Would Alien (Non-Euclidean) Geometry Break Our Brains?
My main video, written, filmed and edited by me, about demystifying non-Euclidean geometry.
My main audio piece, where I interview Professor Adrian Moore (also of St Hugh’s) about what philosophy can tell us about how aliens might do maths.
Maths proves that maths isn’t boring
An article about Gödel’s incompleteness theorems, and how they show maths is always risky.
An audio piece I edited about a tattoo Tom got of the Platonic solids.
Alien maths – we’re counting on it
An article about how we use the mathematics of prime numbers to send messages to the stars.
An article about a game theory paper which could amongst other things help stop deforestation.
The original article was published on the OUS East Kent website here.
What are the chances that two England teammates share a Birthday?
Cast your mind back to the summer of 2018… we saw the warmest ever weather in the UK, Brexit was not yet a complete and utter disaster, and seemingly against all the odds the England football team reached the semi-finals of the World Cup for the first time since 1990. No doubt the team had a huge celebration together afterwards – but it wouldn’t be the first time that two of them have celebrated an occasion at the same time. As well as playing together at the heart of England’s defence, Manchester City duo Kyle Walker and John Stones also share the same birthday! Stones was born on 28th May 1994, making him 24 years old; Walker was born on the same day in 1990, meaning that he is exactly four years older than his teammate. How strange! Or is it…?
On the face of it, it seems quite surprising that in an England squad of just 23 players, two of them happen to share a birthday. However, as we’re about to see, this isn’t a freakish coincidence – maths says that it’s quite likely! What we’re talking about here is commonly known as the birthday problem: if there are a group of people of a certain size, what is the likelihood that at least two of them have the same birthday?
Let’s start by saying that we have a group of N people, and assume that birthdays are equally likely on every day of the year. (There is some evidence to suggest that this isn’t the case for top athletes; some say that they tend to be born early in the school year, such as around September in England. This is because they are slightly older than the other children in the year, and so they have a slight head-start in their physical development. However, we don’t want to make things too complicated, so we’ll ignore that for now.)
The easiest way to think about the problem is to first try to work out what the probability is that none of the N people share a birthday. Suppose our N people walk into a room, that is empty at first, one at a time. When the first person walks in, it’s obvious that they don’t share a birthday with anyone else in the room, because there isn’t anyone else. Therefore, they have the maximum probability of not sharing a birthday with anyone else in the room, which is 1.
Now think of the second person who walks in. The only way that they could share a birthday with someone in the room is if it happens to be exactly the same day as the first person. That means there is a 1 in 365 chance that they do share a birthday, so there is a 364 in 365 chance that they don’t.
Suppose that the first two birthdays don’t match, and then the third person walks in. They now have 2 days that they can’t share a birthday with, so there are 363 possible choices out of 365. Because we assumed that the first two didn’t match, we multiply the probabilities, so now the chance that none of them share a birthday is (364/365) * (363/365).
We can repeat this process until we get to our final person, number N. For example, the fourth person has 3 birthdays that they cannot share, so we multiply by a chance of 362/365; the fifth person has 4 days to avoid, so we include a probability of 361/365… By the time the Nth person walks in, there are N-1 people already in the room, so there are N-1 days that their birthday cannot fall on. This leaves them with 365-(N-1) possibilities out of 365.
To work out the total probability, we multiply all of these terms together which gives the likelihood that none of the N people share a birthday as
1 * (364/365) * (363/365) * (362/365) * … * ((365-(N-1))/365).
You might be thinking that this still looks like quite a big probability that none of them share a birthday, because all of the terms are very close to 1. But, if we try some values of N in a calculator, then it tells a very different story. (The percentages are calculated by finding the probability from the equation above and multiplying by 100.)
When N = 10, we get an 88% chance that none of them share a birthday. However, this drops down to 59% when there are N = 20 people. When we get to N = 23, the number of players in the England squad, the probability reaches just under 50%. That means that, incredibly, the likelihood that at least two of the 23 people share a birthday is just bigger than 50%!
So, in a random group of 23 people, it’s more likely than not that two of them share a birthday! This seems very strange at first; surely you’d need more than 23 people for a shared birthday to be more likely than not?! This is why the problem is commonly known as the birthday paradox – it might be very hard to get your head around, but the maths doesn’t lie!
Perhaps, in order to convince ourselves, we should look at some real-life examples. This is where the World Cup squads come into play: each team is restricted to bringing 23 players to the tournament. (We’ve seen that number before…) If our calculations above are correct, then if we picked any one of the World Cup squads, there would be roughly a 50:50 chance that at least two of the squad members share a birthday, which means that out of all of the squads that went to Russia, we would expect about half of them to have a birthday match. Well, let’s take a look…
Of the 32 teams, which were divided into 8 groups of 4, the following teams have at least one pair of players who share a birthday:
| Group A | Russia |
| Group B | Iran, Morocco, Portugal, Spain |
| Group C | Australia, France, Peru |
| Group D | Croatia, Nigeria |
| Group E | Brazil, Costa Rica |
| Group F | Germany, South Korea |
| Group G | England |
| Group H | Poland |
So, not only is there at least one team in every group with a birthday match, but if we count the total, there are 16 squads with a shared birthday pair – exactly half of the teams! The experimental results have matched up with the mathematical theory to perfection. Hopefully that’s enough to convince you that our calculations were indeed sound!
A slightly different question that you might ask is as follows: if I am in a group with a certain number of people, what are the chances that at least one of them shares my birthday? Is it the same idea? What we have worked out above is the probability that any two people in the room share a birthday (or rather, we worked out the opposite, but we can find the right answer from our working). Note that the pair doesn’t necessarily include you; it’s a lot more likely that it’s some other pair in the group.
In order to work out the answer to this similar sounding question, we work the other way around again, by calculating the probability that none of the N people share my birthday. For each of the N people, there is only one birthday that they cannot have, and that is mine (14th November, in case you were wondering), which means there are 364 out of 365 possibilities for each person. We no longer care whether their birthdays match up; we only care if they match with mine. So each person has a 364/365 chance of not sharing my birthday; and the overall probability is just 364/365 * 364/365 * … * 364/365, N times, which we write as (364/365)N.
Once again, we can plug some values of N into a calculator: N = 10 gives a 97% chance that no-one else has my birthday. For N = 50 the probability is still very high: there is an 87% chance that none of these 50 people have the same birthday as me. N = 100 gives 76%; N = 200 gives 58%; you have to go all the way to N = 253 before the probability dips below 50%, and it becomes more likely than not that at least one person will celebrate their birthday with me.
Applying this idea to all 736 players (32 squads of 23 players) involved in the World Cup, we should expect around 3 of them to have been born on the same day as me – 14th November. And I am very happy to confirm that France’s Samuel Umtiti, Switzerland’s Roman Burki, and Belgium’s Thomas Vermaelen all have what is undoubtedly the best birthday of the year… Two similar problems with two very different solutions!
You can check which footballers share a birthday with you at www.famousbirthdays.com/date/monthDD-soccerplayer.html, where you enter the month in words and the day in numbers (no preceding zero required).
Kai Laddiman
Why do Bees Build Hexagons? Honeycomb Conjecture explained by Thomas Hales
Mathematician Thomas Hales explains the Honeycomb Conjecture in the context of bees. Hales proved that the hexagon tiling (hexagonal honeycomb) is the most efficient way to maximise area whilst minimising perimeter.
Produced by Tom Rocks Maths intern Joe Double, with assistance from Tom Crawford. Thanks to the Oxford University Society East Kent Branch for funding the placement and to the Isaac Newton Institute for arranging the interview.
Would Alien (Non-Euclidean) Geometry Break Our Brains?
The author H. P. Lovecraft often described his fictional alien worlds as having ‘Non-Euclidean Geometry’, but what exactly is this? And would it really break our brains?
Produced by Tom Rocks Maths intern Joe Double, with assistance from Tom Crawford. Thanks to the Oxford University Society East Kent Branch for funding the placement.
Not so smooth criminals: how to use maths to catch a serial killer
The year is 1888, and the infamous serial killer Jack the Ripper is haunting the streets of Whitechapel. As a detective in Victorian London, your mission is to track down this notorious criminal – but you have a problem. The only information that you have to go on is the map below, which shows the locations of crimes attributed to Jack. Based on this information alone, where on earth should you start looking?
The fact that Jack the Ripper was never caught suggests that the real Victorian detectives didn’t know the answer to this question any more than you do, and modern detectives are faced with the same problem when they are trying to track down serial offenders. Fortunately for us, there is a fascinating way in which we can apply maths to help us to catch these criminals – a technique known as geospatial profiling.
Geospatial profiling is the use of statistics to find patterns in the geographical locations of certain events. If we know the locations of the crimes committed by a serial offender, we can use geospatial profiling to work out their likely base location, or anchor point. This may be their home, place of work, or any other location of importance to them – meaning it’s a good place to start looking for clues!
Perhaps the simplest approach is to find the centre of minimum distance to the crime locations. That is, find the place which gives the overall shortest distance for the criminal to travel to commit their crimes. However, there are a couple of problems with this approach. Firstly, it doesn’t tend to consider criminal psychology and other important factors. For example, it might not be very sensible to assume that a criminal will commit crimes as close to home as they can! In fact, it is often the case that an offender will only commit crimes outside of a buffer zone around their base location. Secondly, this technique will provide us with a single point location, which is highly unlikely to exactly match the true anchor point. We would prefer to end up with a distribution of possible locations which we can use to identify the areas that have the highest probability of containing the anchor point, and are therefore the best places to search.
With this in mind, let’s call the anchor point of the criminal z. Our aim is then to find a probability distribution for z, which takes into account the locations of the crime scenes, so that we can work out where our criminal is most likely to be. In order to do this, we will need two things.
- A prior distribution for z. This is just a function which defines our best guess at what z might be, before we have used any of our information about the crime locations. The prior distribution is usually based off data from previous offenders whose location was successfully determined, but it’s usually not hugely important if we’re a bit wrong – this just gives us a place to start.
- A probability density function (PDF) for the locations of the crime sites. This is a function which describes how the criminal chooses the crime site, and therefore how the criminal is influenced by z. If we have a number of crimes committed at known locations, then the PDF describes the probability that a criminal with anchor point z commits crimes at these locations. Working out what we should choose for this is a little trickier…
We’ll see why we need these in a minute, but first, how do we choose our PDF? The answer is that it depends on the type of criminal, because different criminals behave in different ways. There are two main categories of offenders – resident offenders and non-resident offenders.
Resident offenders are those who commit crimes near to their anchor point, so their criminal region (the zone in which they commit crimes) and anchor region (a zone around their anchor point where they are often likely to be) largely overlap, as shown in the diagram:
If we think that we may have this type of criminal, then we can use the famous normal distribution for our density function. Because we’re working in two dimensions, it looks like a little hill, with the peak at the anchor point:
Alternatively, if we think the criminal has a buffer zone, meaning that they only commit crimes at least a certain distance from home, then we can adjust our distribution slightly to reflect this. In this case, we use something that looks like a hollowed-out hill, where the most likely region is in a ring around the centre as shown below:
The second type of offenders are non-resident offenders. They commit crimes relatively far from their anchor point, so that their criminal region and anchor region do not overlap, as shown in the diagram:
If we think that we have this type of criminal, then for our PDF we can pick something that looks a little like the normal distribution used above, but shifted away from the centre:
Now, the million-dollar question is which model should we pick? Determining between resident and non-resident offenders in advance is often difficult. Some information can be made deduced from the geography of the region, but often assumptions are made based on the crime itself – for example more complex/clever crimes have a higher likelihood of being committed by non-residents.
Once we’ve decided on our type of offender, selected the prior distribution (1) and the PDF (2), how do we actually use the model to help us to find our criminal? This is where the mathematical magic happens in the form of Bayesian statistics (named after statistician and philosopher Thomas Bayes).
Bayes’ theorem tells us that if we multiply together our prior distribution and our PDF, then we’ll end up with a new probability distribution for the anchor point z, which now takes into account the locations of the crime scenes! We call this the posterior distribution, and it tells us the most likely locations for the criminal’s anchor point given the locations of the crime scenes, and therefore the best places to begin our search.
This fascinating technique is actually used today by police detectives when trying to locate serial offenders. They implement the same steps described above using an extremely sophisticated computer algorithm called Rigel, which has a very high accuracy of correctly locating criminals.
So, what about Jack?
If we apply this geospatial profiling technique to the locations of the crimes attributed to Jack the Ripper, then we can predict that it is most likely that his base location was in a road called Flower and Deane Street. This is marked on the map below, along with the five crime locations used to work it out.
Unfortunately, we’re a little too late to know whether this prediction is accurate, because Flower and Deane street no longer exists, so any evidence is certainly long gone! However, if the detectives in Victorian London had known about geospatial profiling and the mathematics behind catching criminals, then it’s possible that the most infamous serial killer in British history might never have become quite so famous…
Francesca Lovell-Read
Goldbach’s Conjecture: easy but hard
Often in Mathematics problems that are easy to state turn out to be extremely difficult to solve. Two hundred and seventy-five years ago, Goldbach wrote a letter to the famous Swiss mathematician Leonhard Euler in which he wrote the simple statement:
“Every even integer greater than 2 can be expressed as the sum of two primes.”
Just in case you are not up to speed with your maths (and let’s face it why would you be if you’re not a mathematician), let’s break this statement down. The even integers are the numbers divisible by two: 2, 4, 6, 8, …, 256, … and so on. The prime numbers are the ones that can only be obtained by multiplying one by themselves. For example, 3 and 5 are prime numbers because 3=1×3 and 5=1×5 and they have no other representations as a product of two numbers. However, 6 for instance is not prime because 6=1×6=2×3. In fact, all even integers, greater than 2 that were mentioned above, are not primes because they are all divisible by 2 and therefore can be represented as a product of two numbers in at least two ways: 4=1×4=2×2, 6=1×6=2×3, 8=1×8=2×4 etc.
And so, to Goldbach’s conjecture. It says that all even numbers: 4, 6, 8, 10, … can be written as a sum of two primes. Let’s see a couple of examples:
4=2+2
6=3+3
8=3+5
10=3+7
12=5+7
….
A nice way to represent the conjecture visually is through a “pyramid” and because we all love pretty pictures let’s see how this magic happens.
First, we write all of the prime numbers on two of the sides of a triangle as below: 2, 3, 5, 7 etc. We then draw a line leaving each prime number which is parallel to the opposite side of the triangle (stick with me), and finally at the points of intersection of these lines, we write the sum of the numbers. It sounds more complicated than it is as you’ll see with the following example. In the picture below, take the blue line coming out of the number 7 on the left and the red line coming out from the number 11 on the right. They intersect at 18 because 11+7=18. This means that the even integer 18 can be represented as a sum of the two prime numbers 11 and 7. If you look at the intersections of all of the red and blue lines in the pyramid, you’ll see that we actually get all of the even numbers. In other words, any even integer can be written as the sum of two prime numbers, and we can see what those two numbers are by finding the corresponding intersection on our diagram. This is Goldbach’s Conjecture.
It is not very difficult to show that a small even number greater than 2 is the sum of two prime numbers – either by finding the corresponding point on the picture or by trying all of the possibilities. Let’s take 96. We start by checking the smallest prime number 3. 96=3+93, but 93 is not a prime, because 93=1×93=3×31. We continue with the next prime – 5. 96=5+91, which again doesn’t work because 91=1×91=7×13. Next, we try with 7: 96=7+89. Since 89 is a prime, we have obtained a representation of the number 96 as a sum of two primes.
We were able to quickly check whether 96 satisfies Goldbach’s conjecture because the number is relatively small. It becomes much harder to make these checks for larger numbers. It’s been verified with the use of a computer that the conjecture is true for numbers as big as 4×1018 and this is why the conjecture is believed to be true, but we do not yet have a formal mathematical proof. And being mathematicians, we cannot say something is true until we can prove it.
There have of course been many efforts over the last 275 years to try to prove the conjecture, most of which followed one of two routes. Either by proving that all even integers can be represented as a sum of some number of primes – as a sum of 6 primes (1995, Ramare) and as a sum of 4 primes (Herald Helfgott) – or by proving that almost all even integers can be written as a sum of 2 primes. But, as of yet, the secret formula required to unlock the proof of Goldbach’s Conjecture remains elusive.
You may be wondering why on earth mathematicians are spending their time and effort to prove this seemingly random result about prime numbers? Is it really that important? Whilst you may have a valid point about the applications of this particular conjecture, the value in proving such a result is not in the statement itself, but rather in the new methods, theories and techniques that will need to be developed to solve the problem. So, in 20, 10 or even 2 years from now when you hear that Goldbach’s conjecture has been proved, you should be happy not because we now know for sure that it’s true, but rather because some incredible new area of mathematics has been developed in the process. And who knows, this new area of maths may even pose a new, even more complicated conjecture that will occupy mathematicians for the next 275 years…
Mariya Delyakova
Take me to your chalkboard
Is alien maths different from ours? And if it is, will they be able to understand the messages that we are sending into space? My summer intern Joe Double speaks to philosopher Professor Adrian Moore from BBC Radio 4’s ‘a history of the infinite’ to find out…
