Boolean Pythagorean triples problem: Difference between revisions

Revision as of 00:05, 27 August 2020

Revision as of 00:07, 27 August 2020

Line 1:

{{short description|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 [[Pythagorean triple]]s,. whichThe 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>a^2+b^2=c^2</math> are all the same color. For example, in the Pythagorean triple 3, 4 and 5 (<math>3^2+4^2=5^2</math>), if 3 and 4 are colored red, then 5 must be colored blue.

The Boolean Pythagorean triples problem was solved by Marijn Heule, Oliver Kullmann and [[Victor W. Marek]] in May 2016 through a [[computer-assisted proof]].<ref name="nature">{{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|volume=534|pages=17–18|pmid=27251254|bibcode=2016Natur.534...17L|doi-access=free}}</ref>

==Solution==
Marijn TheyHeule, 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

{{math 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}.<ref name="arXiv"/>}}

Line 9 ⟶ 12:

The paper describing the proof was published in the SAT 2016 conference,<ref name="arXiv">{{Cite conference|last=Heule|first=Marijn J. H.|last2=Kullmann|first2=Oliver|last3=Marek|first3=Victor W.|author3-link=Victor W. Marek|year=2016|contribution=Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer |arxiv=1605.00723|doi=10.1007/978-3-319-40970-2_15|series=Lecture Notes in Computer Science|volume=9710|pages=228–245|title=Theory and Applications of Satisfiability Testing – SAT 2016: 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings|editor1-first=Nadia|editor1-last=Creignou|editor2-first=Daniel|editor2-last=Le Berre}}</ref> where it won the best paper award.<ref>[http://sat2016.labri.fr/ SAT 2016]</ref>

==Prize==

In the 1980s [[Ronald Graham]] offered a $100 prize for the solution of the problem, which has now been awarded to Marijn Heule.<ref name="nature"/>