The Boolean Pythagorean triples problem was a problem relating to Pythagorean triples which was solved using a computer-assisted proof in May 2016.[1]
This problem is part of the 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 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 102300 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 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.[2] and has been accepted for the SAT 2016 conference.
References
- ^ Lamb, Evelyn (26 May 2016). "Two-hundred-terabyte maths proof is largest ever". Nature. doi:10.1038/nature.2016.19990.
- ^ Heule, Marijn J. H.; Kullmann, Oliver; Marek, Victor W. (2016-05-03). "Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer". arXiv:1605.00723 [cs].