The Boolean Pythagorean triples problem is a problem from

Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...

about whether the

positive integers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

can be colored red and blue so that no

Pythagorean triple A Pythagorean triple consists of three positive integers , , and , such that . Such a triple is commonly written , and a well-known example is . If is a Pythagorean triple, then so is for any positive integer . A primitive Pythagorean triple is ...

s consist of all red or all blue members. The Boolean Pythagorean triples problem was solved by

Marijn Heule Marienus Johannes Hendrikus Heule (born March 12, 1979 at Rijnsburg, The Netherlands) is a Dutch computer scientist at Carnegie Mellon University who studies SAT solvers. Heule has used these solvers to resolve mathematical conjectures such as t ...

, Oliver Kullmann and Victor W. Marek in May 2016 through a

computer-assisted proof A computer-assisted proof is a mathematical proof that has been at least partially generated by computer. Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a ...

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

are all the same color. For example, in the Pythagorean triple 3, 4 and 5 (

3^2+4^2=5^2

), if 3 and 4 are colored red, then 5 must be colored blue.

Solution

, 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 There are 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 were examined using a

Boolean satisfiability In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

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 The Texas Advanced Computing Center (TACC) at the University of Texas at Austin, United States, is an advanced computing research center that provides comprehensive advanced computing resources and support services to researchers in Texas and acr ...

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, where it won the best paper award. The figure below shows a possible family of colorings for the set with no monochromatic Pythagorean triple, and the white squares can be colored either red or blue while still satisfying this condition. Ptn-7824-zoom-2

Prize

In the 1980s

Ronald Graham Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...

offered a $100 prize for the solution of the problem, which has now been awarded to

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.{{Cite journal, last=Eliahou, first=Shalom, last2=Fromentin, first2=Jean, last3=Marion-Poty, first3=Virginie, last4=Robilliard, first4=Denis, date=2018-10-02, title=Are Monochromatic Pythagorean Triples Unavoidable under Morphic Colorings?, url=https://www.tandfonline.com/doi/full/10.1080/10586458.2017.1306465, journal=Experimental Mathematics, language=en, volume=27, issue=4, pages=419–425, doi=10.1080/10586458.2017.1306465, issn=1058-6458, arxiv=1605.00859

References

Computer-assisted proofs Mathematical problems Pythagorean theorem Ramsey theory

Statement

Solution

Prize

Generalizations

See also

References