Misplaced Pages

Boolean Pythagorean triples problem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Can one split the integers into two sets such that every Pythagorean triple spans both?

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.

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 a 2 + b 2 = c 2 {\displaystyle a^{2}+b^{2}=c^{2}} are all the same color.

For example, in the Pythagorean triple 3, 4 and 5 ( 3 2 + 4 2 = 5 2 {\displaystyle 3^{2}+4^{2}=5^{2}} ), if 3 and 4 are colored red, then 5 must be colored blue.

Solution

Marijn Heule, Oliver Kullmann, and Victor W. Marek demonstrated that it is possible to partition the set { 1 , … , 7824 } {\displaystyle \{1,\ldots ,7824\}} into two subsets such that neither subset contains a Pythagorean triple. However, such a partition is not possible for the set { 1 , … , 7825 } {\displaystyle \{1,\ldots ,7825\}} . This result was achieved by analyzing a vast number of possible colorings, which initially amounted to about 2 7825 {\displaystyle 2^{7825}} combinations.The researchers reduced this to around a trillion cases, which were then tested using a SAT solver. The computational process required approximately 4 CPU-years over two days on the Stampede supercomputer at the Texas Advanced Computing Center. The resulting proof, initially 200 terabytes in size, was compressed to 68 gigabytes.The findings were published in the SAT 2016 conference paper "Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer," which received the best paper award.

Prize

In the 1980s Ronald Graham offered a $100 prize for the solution of the problem, which has now been awarded to Marijn Heule.

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.

See also

References

  1. ^ Lamb, Evelyn (26 May 2016). "Two-hundred-terabyte maths proof is largest ever". Nature. 534 (7605): 17–18. Bibcode:2016Natur.534...17L. doi:10.1038/nature.2016.19990. PMID 27251254.
  2. Eliahou, Shalom; Fromentin, Jean; Marion-Poty, Virginie; Robilliard, Denis (2018-10-02). "Are Monochromatic Pythagorean Triples Unavoidable under Morphic Colorings?". Experimental Mathematics. 27 (4): 419–425. arXiv:1605.00859. doi:10.1080/10586458.2017.1306465. ISSN 1058-6458. S2CID 19035265.
Categories: