Boolean Pythagorean triples problem: Difference between revisions

Revision as of 02:26, 20 May 2020

Latest revision as of 06:30, 6 July 2025

(35 intermediate revisions by 25 users not shown)

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 relatingfrom to[[Ramsey theory]] about whether the [[natural number|positive integers]] can be colored red and blue so that no [[Pythagorean triple]]s whichconsist of all red or all blue members. The Boolean Pythagorean triples problem was solved usingby [[Marijn Heule]], Oliver Kullmann and [[Victor W. Marek]] in May 2016 through a [[computer-assisted proof]], inwhich Mayshowed 2016that such a coloring is only possible up to the number 7824.<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|issue=7605 |pages=17–18|pmid=27251254|bibcode=2016Natur.534...17L|doi-access=free}}</ref>

==Statement==

ThisThe problem is from [[Ramsey theory]] and 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.

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.

Marijn Heule, Oliver Kullmann and [[Victor W. Marek]] investigated the problem, and 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"/>}}

==Solution==

There are {{nowrap|2⁷⁸²⁵ ≈ 3.63×10²³⁵⁵}} possible coloring combinations for the numbers up to [[7825 (number)|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]] 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.

[[Marijn Heule]], Oliver Kullmann and [[Victor W. Marek]] investigated the problem, and 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"/>}}

}}

There are {{nowrap|2⁷⁸²⁵ ≈ 3.63×10²³⁵⁵}} possible coloring combinations for the numbers up to [[7825 (number)|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 [[BooleanSAT satisfiabilitysolver]] 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,<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>

The paper describing the proof was published in the SAT 2016 conference,<ref name="arXiv">{{Cite conference|lastlast1=Heule|firstfirst1=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> 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.

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"/>

[[File:Ptn-7824-zoom-2.png|alt=|center|400x400px]]

==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"/>

== 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.<ref>{{Cite journal|last1=Eliahou|first1=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|s2cid=19035265 }}</ref>

== See also ==