Boolean Pythagorean triples problem: Difference between revisions

Revision as of 17:04, 31 May 2016

Revision as of 19:45, 31 May 2016

Line 1:

The '''Boolean Pythagorean triples problem''' was a problem relating to [[Pythagorean triple]]s which was solved using a [[computer-assisted proof]] in May 2016.<ref>{{Cite journal|last=Lamb|first=Evelyn|date=26 May 2016|title=Two-hundred-terabyte maths proof is largest ever|url=http://www.nature.com/news/two-hundred-terabyte-maths-proof-is-largest-ever-1.19990|journal=Nature|doi=10.1038/nature.2016.19990}}</ref>

This problem is part of the [[Infinitary combinatorics|Ramsey theory]] and asks if it is possible to color alleach of the integers either red or blue so that no Pythagorean triple of integers ''a'', ''b'', ''c'', satisfying <math>a^2+b^2=c^2</math> are all the same color. For example, a coloring with ''a'' and ''b'' red and ''c'' blue is an admissible coloring, but all three blue would not be. The proof shows that it is impossible.

The proof shows that upsuch a coloring is impossible. Up to the number 7824 it is possible to color the numbers such that all Pythagorean triples are admissible. There are more than 10²³⁰⁰ colorings for numbers up to 7825, but the proof shows that iffor any coloring for which all the triples up to 7824 are multi-colored, not all those involving 7825 can beare multi-colored. The

There are 2⁷⁸²⁵ colorings for numbers up to 7825. These possible colorings were logically narrowed down to just under a trillion cases, and those were examined using the [[brute force method]]. The proof took two days of computer execution time on the Stampede supercomputer at the [[Texas Advanced Computing Center]] and generated 200 terabytes of data.

In the 1980s [[Ronald Graham]] offered a $100 prize for the solution of the problem, which has now been awarded to Marijn Heule. The paper describing the proof was published on arXiv on 3 May 2016.<ref>{{Cite journal|last=Heule|first=Marijn J. H.|last2=Kullmann|first2=Oliver|last3=Marek|first3=Victor W.|date=2016-05-03|title=Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer|url=http://arxiv.org/abs/1605.00723|journal=arXiv:1605.00723 [cs]}}</ref> and has been accepted for the SAT 2016 conference.