Computer Cracks 200 Terabyte Math Proof

Here’s a cute problem, called the Boolean Pythagorean Theorem problem. Here are the first few Pythagorean triples:

3^2 + 4^2 = 5^2

6^2 + 8^2 = 10^2

5^2 + 12^2 = 13^2

9^2 + 12^2 = 15^2

8^2 + 15^2 = 17^2

12^2 + 16^2 = 20^2

7^2 + 24^2 = 25^2

15^2 + 20^2 = 25^2

10^2 + 24^2 = 26^2

20^2 + 21^2 = 29^2

18^2 + 24^2 = 30^2

16^2 + 30^2 = 34^2

21^2 + 28^2 = 35^2

12^2 + 35^2 = 37^2

15^2 + 36^2 = 39^2

27^2 + 36^2 = 45^2

9^2 + 40^2 = 41^2

27^2 + 36^2 = 45^2

OK, let’s have some fun with this. Let’s write every multiple of 5 (5, 10, 15, 20, 25, 30, 35, 40, 45) in boldface:

3^2 + 4^2 = {\bf 5}^2

6^2 + 8^2 = {\bf 10}^2

{\bf 5}^2 + 12^2 = 13^2

9^2 + 12^2 = {\bf 15}^2

8^2 + {\bf 15}^2 = 17^2

12^2 + 16^2 = {\bf 20}^2

7^2 + 24^2 = {\bf 25}^2

{\bf 15}^2 + {\bf 20}^2 = {\bf 25}^2

{\bf 10}^2 + 24^2 = 26^2

{\bf 20}^2 + 21^2 = 29^2

18^2 + 24^2 = {\bf 30}^2

16^2 + {\bf 30}^2 = 34^2

21^2 + 28^2 = {\bf 35}^2

12^2 + {\bf 35}^2 = 37^2

{\bf 15}^2 + 36^2 = 39^2

27^2 + 36^2 = {\bf 45}^2

9^2 + {\bf 40}^2 = 41^2

27^2 + 36^2 = {\bf 45}^2

For nearly all of these equations, there is one number that’s in boldface and one that’s not. However, there’s one that is all in one typeface: {\bf 15}^2 + {\bf 20}^2 = {\bf 25}^2.

So here’s a question: is it possible to divide the integers so that every Pythagorean triple (not just the small ones listed above) has at least one number in boldface and another that’s not?

This May, it was proved that it’s impossible. The proof is very brute-force (from https://cosmosmagazine.com/mathematics/computer-cracks-200-terabyte-maths-proof):

The team found all triples could be multi-coloured in integers up to 7,824. As soon as they hit 7,825, it became impossible.

But to prove a solution doesn’t exist, you need to try all possibilities. There are more than 10^{2300} ways to colour all those integers, so the scientists used a few mathematical tricks to reduce the number of combinations to trial to just under one trillion.

Two days later, with 800 processors at the University of Texas Stampede supercomputer crunching all possibilities in parallel, the team had their answer – no.

There is no way to colour the integers 1 to 7,825 in a way that leaves all Pythagorean triples multi-coloured, the team reported in arXiv.

I had to read this news article a couple of times to appreciate this: a supercomputer ran for two days on a supercomputer (without parallelization, computation time was 51,000 hours), producing an output file of 200 terabytes, comparable “to the size of the entire digitized text held by the US Library of Congress.” Wow.

Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: