Boolean Pythagorean triples problem
The Boolean Pythagorean triples problem is a problem from Ramsey theory about whether the positive integers can be colored red and blue so that no Pythagorean triples consist of all red or all blue members. The Boolean Pythagorean triples problem was solved by Marijn Heule, Oliver Kullmann and Victor W. Marek in May 2016 through a computer-assisted proof.[1]
Statement
The problem asks if it is possible to color each of the positive integers either red or blue, so that no Pythagorean triple of integers a, b, c, satisfying [math]\displaystyle{ a^2+b^2=c^2 }[/math] are all the same color.
For example, in the Pythagorean triple 3, 4 and 5 ([math]\displaystyle{ 3^2+4^2=5^2 }[/math]), if 3 and 4 are colored red, then 5 must be colored blue.
Solution
Marijn Heule, Oliver Kullmann and Victor W. Marek showed that such a coloring is only possible up to the number 7824. The actual statement of the theorem proved is
Theorem — The set {1, . . . , 7824} can be partitioned into two parts, such that no part contains a Pythagorean triple, while this is impossible for {1, . . . , 7825}.[2]
There are 27825 ≈ 3.63×102355 possible coloring combinations for the numbers up to 7825. These possible colorings were logically and algorithmically narrowed down to around a trillion (still highly complex) cases, and those, expressed as Boolean satisfiability problems, were examined using a SAT solver. Creating the proof took about 4 CPU-years of computation over a period of two days on the Stampede supercomputer at the Texas Advanced Computing Center and generated a 200 terabyte propositional proof, which was compressed to 68 gigabytes.
The paper describing the proof was published in the SAT 2016 conference,[2] where it won the best paper award.[3] The figure below shows a possible family of colorings for the set {1,...,7824} with no monochromatic Pythagorean triple, and the white squares can be colored either red or blue while still satisfying this condition.
Prize
In the 1980s Ronald Graham offered a $100 prize for the solution of the problem, which has now been awarded to Marijn Heule.[1]
Generalizations
As of 2018, the problem is still open for more than 2 colors, that is, if there exists a k-coloring (k ≥ 3) of the positive integers such that no Pythagorean triples are the same color.[4]
See also
References
- ↑ 1.0 1.1 Lamb, Evelyn (26 May 2016). "Two-hundred-terabyte maths proof is largest ever". Nature 534 (7605): 17–18. doi:10.1038/nature.2016.19990. PMID 27251254. Bibcode: 2016Natur.534...17L.
- ↑ 2.0 2.1 Heule, Marijn J. H.; Kullmann, Oliver; Marek, Victor W. (2016). "Theory and Applications of Satisfiability Testing – SAT 2016: 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings". in Creignou, Nadia; Le Berre, Daniel. 9710. pp. 228–245. doi:10.1007/978-3-319-40970-2_15.
- ↑ SAT 2016
- ↑ Eliahou, Shalom; Fromentin, Jean; Marion-Poty, Virginie; Robilliard, Denis (2018-10-02). "Are Monochromatic Pythagorean Triples Unavoidable under Morphic Colorings?" (in en). Experimental Mathematics 27 (4): 419–425. doi:10.1080/10586458.2017.1306465. ISSN 1058-6458. https://www.tandfonline.com/doi/full/10.1080/10586458.2017.1306465.
 |  |
