Communications of the ACM
A Mathematical Proof Takes 200 Terabytes To State
The latest example of proof by computer enters a new realm, with a proof 200 terabytes in size.
Credit: I Programmer
The idea that computers play a key role in mathematical proof is well accepted today by all but the purist of mathematicians, but the latest example of proof by computer enters a new realm - a proof 200 terabytes in size.
The Pythagorean Triples problem is, or was, an open problem in Ramsey theory:
Can the set of natural numbers, 1,2,3 ... be divided into two parts such that neither part contains a Pythagorean Triple, i.e. three numbers which form the sides of a right angle triangle and where:
a2+b2=c2.
You can also pose the problem as trying to paint the Pythagorean triples with two colors so that no triple is all the same color.
There is also a related problem that asks if the triples can be divided into k sets or painted using n colors. The problem with just two sets is the most basic and the one to solve first.
This is one of those wonderful math problems that is easy to state but very, very difficult to solve. You can start easily enough and when you hit the first triple - the well known 3,4,5 triangle triple you can simply put the 3 into one set and the 4 and 5 in the other. You can carry on like this but 5 is also in another triple 5,12,13 so now you can't put both 12 and 13 in the same set as 5, but 12 and 13 are part of another two triples 12,35,37 and 13,84,85. You can see that as you progress the constraints on how numbers are allocated become more and more difficult.
The question is can it be done?
From I Programmer
View Full Article
No entries found