Boolean Pythagorean triples problem: Difference between revisions

Revision as of 03:28, 28 May 2016

Revision as of 19:46, 28 May 2016

Line 1:

The '''Boolean Pythagorean triples problem''' was a conjecture relating to [[Pythagorean triple]]s which was shown to be false 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>

The problem asks if it is possible to color all the integers either red or blue so that no pythagoreanPythagorean triple of integers ''a'', ''b'', ''c'', satisfying <math>a^2+b^2=c^2</math> are all the same color. The proof tested all possible colouring of numbers up to 7,825 and found no such colouring was possible. There are 10^2,300 such colourings and the proof took two days of time on the Stampede supercomputer at the [[Texas Advanced Computing Center]]. The proof 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.