computers

An Interesting Ramsey Theory Riddle

[Total: 3    Average: 5/5]

This insight will be about Ramsey theory. Ramsey theory has its origins in a very nice riddle:

Consider a party of 6 people. Any two of these 6 will either be meeting each other for the first time (in which case they are strangers), or they will know each other (in which case they are friends). Show that in this party of 6 people, there are either 3 who are mutual strangers or mutual friends. Show that the same does not hold in a party of 5 people.

Try to prove this riddle yourself, it shouldn’t be too difficult.

Then we can do what mathematicians do best: generalize this. This generalization has been done by Ramsey. We say that ##R(m,n) = v## if in a party of v people, there are at least m people who are mutual friends or n people who are mutual strangers, while the same does not hold true in a party with v-1 people. Our riddle at the start states that ##R(3,3)=6##.

But wait! Why should there be a number v such that ##R(m,n) = v##? Why should this have a solution at all? Why should there exist a party size where 100 people either are mutual friends or 1000 people are mutual strangers? Well, this is proved in what is called Ramsey’s theorem. Ramsey also gives an upper bound on v.

So let’s prove Ramsey’s theorem. The clue lies in the following result: ##R(m,n)\leq R(m-1,n) + R(m,n-1)##. Using this result and a simple induction gives us the final result. To prove the result, take a party with ##R(m-1,n) + R(m,n-1)## guests. Take an arbitrary guest, which we call Mister T. Now for anybody in the room, we have that Mister T either knows this person or not. So we can split the party in two: the people who know mister T, the people who don’t know mister T and mister T himself. So we have
[tex]R(m-1,n) + R(m,n-1) = \text{number of people knowing mister T} + \text{number of people not knowing mister T} + 1[/tex]
We can deduce that either the number of people knowing mister T is bigger than ##R(m-1,n)## or the number of people not knowing mister T is bigger than ##R(m,n-1)##. In the first case, since the number of people knowing mister T is bigger than ##R(m-1,n)##, we see that there is either a set of ##m-1## friends among those who know mister T, or there are ##n## strangers among those who know mister T. If there are ##n## strangers who know mister T, then there are ##n## strangers in the entire party. Done. If there are ##m-1## friends who know mister T, then together with mister T, there are ##m## friends in the party. Done.
Analogously, since the number of people not knowing mister T is bigger than ##R(m,n-1)##, we see that among those, there are either ##m## friends or ##n-1## strangers. In the first case, there are ##m## friends in the party. Done. In the second case, there are ##n-1## strangers and if we add Mister T to that list, there are ##n## strangers. Done.

Ramsey actually proved a more general result, where you can be more than just a friend or a stranger. For example, you can be a friend, a stranger or an enemy. If in a party with ##v## people there are at least ##m## friends, or ##n## strangers or ##k## enemies, and this does not hold in a party with ##v-1## people, then we say that ##R(m,n,k) = v##. So why should this ##v## exist? The crucial result here is
[tex]R(m,n,k) \leq R(m,R(n,k))[/tex]
Indeed, in a party with ##R(m,R(n,k))## people there are either ##m## friends or ##R(n,k)## non-friends. In the first case, we are done. In the second case, we get that the non-friends either know eachother or are enemies. Since there are ##R(n,k)## non-friends, there are either ##n## strangers or ##k## enemies. Done.

Of course, we can go even more general. To consider even more general cases, we rephrase our results a bit. We are again in a party with ##v## people. Now every two of these people are holding a rope of a certain color. For example, in a party of ##4## people, every person is holding ##3## ropes, and there are ##6## ropes in total. Now every rope has a certain color. This color can be red, green, blue, etc. There are ##c## colors in general. Now we say that ##v = R(n_1,…,n_c)## if there are at least ##n_1## people who are all mutually holding a rope with color 1, or there are at least ##n_2## people who are all mutually holding a rope with color 2, etc., while a party of ##v-1## does not have this property. Try to show that for any ##c## numbers, there is always a party size ##v## such that ##v = R(n_1,…,n_c)##.

Let’s go back to just the case with friends and strangers. Not many exact values are known. We know that ##R(1,n) = R(n,1) = 1## for every ##n##, and that ##R(2,n) = R(n,2) = n## for every ##n##. Try to show this. Aside from this, only very few values are know. For example, we know that ##R(3,3)= 6##, by the riddle. We also know that ##R(4,4) = 18##. But ##R(5,5)## is not known, although we do know it is between ##43## and ##49##. In fact, the great mathematician Spender has said that:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of ##R(5, 5)## or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for ##R(6, 6)##. In that case, he believes, we should attempt to destroy the aliens.

For three or more colors, the situation is even more difficult. Aside from trivial cases, we only know that ##R(3,3,3) = 17##.

But research on Ramsey theory has exploded ever since. For example, there is also infinite Ramsey theory, where they consider parties with infinite numbers. The basic result is this: consider a party with countably infinite people present, and all are holding ropes with ##c## colors in total. Then there is an infinite subset of the party such that all people in the subset are mutually holding the same rope. This is pretty easy to prove, but we can go on and assume that instead of every two people sharing a rope, we can say that every 3 people are holding a rope, or every 4 people are holding a rope. The infinite Ramsey theorem says that: consider a party with countably infinite people, and all ##n## people are sharing a rope of a certain color. Then there is some infinite subset of the party such that all ##n## people in the subset are holding the same rope. Of course, we can go even further and consider uncountably infinite parties and so on.

In general, Ramsey theory deals with problems of this kind: we have some structure that is cut into various disjoint pieces. How big must the original structure be so that at least one of the pieces has an interesting property.

And this leads us to the Boolean Pythagorean triples problem, a problem that was “solved” only last month in May 2016 (I’ll explain at the end why I put solved between quotations). First, three numbers are said to be a Pythagorean triple if there exists a rectangular triangle with those numbers as sides. Now consider the party where all natural numbers are invited. It’s election season and every number votes either for Trump or Clinton. Is it possible that among all Pythagorean triples ##(a,b,c)##, we have that not all are voting for the same person? Heule, Kullman and Marek have shown that it is not possible. Even more: if we invite all numbers up to ##7824##, then this is possible, but as soon as we invite ##7825##, it has become impossible: at least one Pythagorean triple must all vote for the same candidate!

How was it solved? Well, they reduced the problem to a small number of cases of about one trillion. Then they let a supercomputer run for 2 entire days and the answer popped out. If you would write out the proof, then it would be the largest proof currently known.

But is this a proof? Computer assisted proofs have been controversial ever since the proof of the four colour theorem. The problem is this: assume that we have an oracle which answers every well-formed question truthfully with either yes and no. We can then ask this oracle a lot of different math problems. Like “Is the Fermat’s last theorem true?”, or “Is Goldbach’s conjecture true?”, and we would the answer immediately! Isn’t that fun? Hmmm. The problem is that we then know the truth or falsity of the statements, but we have come no closer to seeing why the result is true. And this is the entire purpose of a proof isn’t it? We don’t do proofs in math just to see whether something is true or false, but we do proofs because we want to see why. And this is exactly the problem with computer assisted proofs. We know now 100% that the Boolean Pythagorean triples problem is false (and we even know exactly when it fails!), but we don’t know why. We don’t know what’s special about ##7825## that would ruin everything. So I would say that the problem is solved, but not proven.

 

 

5 replies
  1. fresh_42
    fresh_42 says:

    To start with: It's been a great pleasure to read your Insight. I wonder if Ramsey's theory will share a similar fortune as many other problems that could be formulated so easily.

    I'm always surprised again how some numbers or their properties fascinates us. When I think of Pythagoras I usually think of him as an ancient esoteric, a charlatan. On the other hand when it comes to Ramanujan I think of him as one of the greatest, possibly the greatest virtuoso who ever played on the gamut of numbers. Does this discrepancy exist because Ramanujan contributed so much more to number theory than taxicab numbers or am I simply unfair to Pythagoras.

    It's also worth reading Simon Singh's book on Fermat's Last Theorem. It brought literally thousands of hobby mathematicians to try a solution because it could be stated so easily. Today it's believed that Fermat never had a real proof of it, or at best only for the case ##n=3.## One must know that at the time, some scholars made fun of it to write their colleagues letters, in which they stated to have proven something without actually given a proof, just to see whether the other one can find out. Nevertheless it was a real booster for number theory. The proof itself, however, is only understood by a handful of mathematicians (meanwhile maybe some more) and requires deep insights into the theory of elliptic curves and (as far as I know) the theory of modular forms. It is agreed to be proven, although only a few could verify this. What makes such a situation different from a computer based handling of cases? I remember I once had a computer proven some cases as well to verify a theorem. Long after it has been accepted, I found some loopholes in the program. It didn't change the result, for I could close them but nobody (except me) ever really noticed. Another prominent example is the Four-Color-Theorem.

    As in chess, I think we will have to develop a common ground on which we will judge computer based proofs. Personally I think it will require to say goodbye to some selfish human attitudes.

    Back to ##7825 = 5^2 cdot P_{5cdot P_{5+1}}##. What fascinates us on numbers? One can probably take any number and construct obscure relations around it. I like the hypothesis that it comes from our evolutionary based need to recognize patterns. It is kind of fascinating by itself that this pattern-recognition led to so many theorems and knowledge in number theory. And that it has such an enormous history from Pythagoras, over Ramanujan to Wiles.

  2. mfb
    mfb says:

    Great article!

    R(5,5) is between 43 and 49. So we have an example of a group of 42 where no subgroup of 5 exists, and we have a proof that groups of 50 people have to have such a subgroup?

    Constructing it with the given recursive rule leads to a higher upper bound:

    R(4,3) <= R(3,3) + R(4,2) = 6+4 = 10

    R(5,3) <= R(4,3) + R(3,3) = 16

    R(4,4) <= R(4,3) + R(3,4) = 20

    R(5,4) <= R(4,4) + R(5,3) = 36

    R(5,5) <= R(5,4) + R(4,5) = 72

  3. Collin237
    Collin237 says:

    We don’t know what’s special about 7825 that would ruin everything.

    Reference https://www.physicsforums.com/insights/friends-strangers-7825-computers/

    This isn't like the four-color theorem. This is a computation that doesn't require any second-order logic. Beyond 7825, the induction is trivial for us humans, and we can let the computer halt. With only a finite amount of exact bead-pushing, what would such a question even mean? What could an answer to "why" be, except "I just showed you"?

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply