Boolean Pythagorean triples problem: Difference between revisions

Revision as of 17:01, 31 May 2016

Revision as of 17:04, 31 May 2016

Line 3:

This problem is part of the [[Infinitary combinatorics|Ramsey theory]] and asks if it is possible to color all 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 up to the number 7824 it is possible to color the numbers such that all Pythagorean triples are admissible. There are more than 10^2,3002300 colorings for numbers up to 7825, but the proof shows that if all the triples up to 7824 are multi-colored, not all those involving 7825 can be multi-colored. The possible colorings were logically narrowed down to aboutjust 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.