In a beautiful thought experiment by the Hungarian mathematician Paul Erdös (1913-1996), a couple of aliens land on our earth and ask us about the value of the fifth Ramsey number. If we can’t give the answer in a reasonable time, they will destroy our planet. According to Erdös, we should call together all our mathematicians, who should do everything possible to calculate this value. But if the aliens want to hear not the fifth but the sixth Ramsey number, we should do everything we can to destroy the aliens.
Ramsey numbers, named after Frank Ramsey (1903-1930), quantify how big something must be so that certain patterns inevitably emerge. A common description of the fifth Ramsey number, abbreviated as R5, is the smallest number of people that must come together so that there is certainly a group of five people who all know each other, or all of them don’t know each other. Similarly, the sixth Ramsey number is R6 the smallest group size with the property that there are either six who all know each other or six who are all strangers to each other.
Eliminate the aliens
Determining R3 – how many people should be present at a party, so that there are definitely three who all or not all know each other? – was in 1953 a statement from an American mathematics competition for undergraduate students. It is a fun puzzle to check for yourself that the answer is six.
Larger Ramsey numbers are extremely difficult to compute. That the students at the competition do not go to R4 was asked, will have to do with the fact that the problem creators themselves had no idea how to approach this – it was an open problem at the time. Spurred on by the competition, mathematicians threw themselves into this. In 1955 came the redeeming answer: R4 = 18. This means that there must be at least 18 people present, so that there is always a group of four who all know each other or all do not.
When thinking of mathematics, many people think of exact answers, whether or not expressed in a concise formula
The problem with this type of problem is that the number of cases you have to look at quickly becomes very large. At present, no one knows the exact value of the fifth Ramsey number, let alone the sixth or seventh. Maybe one day it will work for R5 to calculate exactly, but R6 will almost certainly never be known. The calculation is simply unfeasible because of the enormous number of possibilities that have to be checked. That is why this should not be attempted in Erdös’ thought experiment – the only way to survive is to eliminate the aliens.
When thinking of mathematics, many people think of exact answers, whether or not expressed in a concise formula. That is true at secondary school level, but for problems at a higher level it is the exception rather than the rule if someone came up with a precise formula for the solution. When it’s too hard to get exact answers, mathematicians try to find lower and upper bounds. For example, someone wanting to calculate the fifth Ramsey number might say, “I don’t know how large R5 is exact, but I can prove that it is at least 43 and at most 48.”
Two trillion cases
For difficult problems such a statement is already quite an achievement, especially if it is not clear in advance that such a limit exists. Take the prime numbers, which are only divisible by 1 and themselves. What is the smallest value of k with the property that there exist infinitely many pairs of prime numbers that differ by at most k? It has been suspected for centuries that this value is 2 – this is the so-called twin prime conjecture. In 2013 an upper bound for k was proved for the first time: 70 million. Admittedly a large number, still far from 2, but before that it was not even certain whether such an upper limit existed for this issue at all. That 70 million is considered one of the greatest breakthroughs in mathematics of this century. The limit has now been lowered to 246.
Back to the Ramsey numbers. The fifth Ramsey number is – indeed – between 43 and 48. The lower bound 43 was proven in 1989, the upper bound 48 in 2017. For the proof of this upper limit approximately two trillion cases had to be checked using computer calculations. Mathematicians think that 43 is the exact value of R5because many attempts have already been made to improve that lower limit – without success.
Apart from these concrete cases, mathematicians are also interested in general questions
Obviously, the closer the lower and upper limits are to each other, the better. For R6 the best known lower bound is 102, the best upper bound is 161. So the sixth Ramsey number is somewhere between those two numbers. For larger Ramsey numbers, the distance between the two limits increases rapidly. The tenth Ramsey number is between 798 and 23,556.
Apart from these specific cases mathematicians are also interested in general questions. For example: how does Rn with increasing size of n? Is there a linear increase (even)? Or exponential (very fast)? Or logarithmic (slow)?
Smaller upper limits
Lower and upper limits play a crucial role in this research. As early as 1935, Erdös, together with his friend and colleague George Szekeres, proved that the nth Ramsey number is in any case not greater than 4 raised to the power of n. Twelve years later, he showed that the square root of 2 raised to the power of n is an underestimation. Erdös’ lower bound for Rn is therefore (2)nits upper bound is 4n. That upper limit is far from sharp: if you fill in the value 5 for n, you get 1024, while we know that R5 is no greater than 48. Still, the formula gives an upper bound that is true for any value of n. Smaller upper limits were found several times in the decades after 1935, but the improvements were relatively small. Until March of this year: then four mathematicians an article on the preprint server arXiv in which they give an ‘exponential improvement’ of that upper limit.
Such knowledge is important not only in mathematics, but also in computer science
Marcelo Campos, Simon Griffiths, Robert Morris and Julian Sahasrabudhe have shown that Rn does not exceed 3,993n. That doesn’t sound like a spectacular result, because 3.993 is barely less than 4. If you use R10,000 want to know, the upper limit of Erdös gives a number of 6,021 digits. The upper limit of Campos and his colleagues is eight digits less.
To see how substantial this improvement is, mathematicians look at the ratio between the two upper bounds as n gets bigger and bigger. The quotient is 3.993n divided by 4n equals 0.99825n, which is close to zero for large values of n. The quotients between the upper limits that have been known for some time and 4n Although they also have limit zero, those quotients go to zero quite slowly. The new upper limit is ‘exponentially better’ in the sense that the said ratio is 0.99825n ‘exponentially fast’ converges to zero. This means that the upper limit of Campos, Griffiths, Morris and Sahasrabudhe is really much better quality – although this is only visible for very large values of n.
Efficient computer programs
Finding good lower and upper limits is essential to be able to provide quality guarantees. Statements such as ‘the calculated solution deviates from the best by no more than 10 percent’ are impossible without limits.
Such knowledge is important not only in mathematics, but also in computer science. A programmer who is working on a computer program that has to perform a certain task will want to write a program that is as efficient as possible. He can knock on the door of the mathematician to ask how fast a computer can be ready at its fastest. The mathematician can rarely answer such a question exactly, but he can indicate the minimum or maximum number of steps the program must perform. If the programmer has made a program whose number of steps is close to that minimum, he knows that his program can hardly gain efficiency by programming even smarter.