Boolean Pythagorean triples problem: Difference between revisions

Revision as of 06:25, 17 October 2022

Revision as of 00:12, 4 January 2023

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 whether the [[natural number|positive integers]] can be colored red and blue so that no [[Pythagorean triple]]s 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]].<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==

Line 14:

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.

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.

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

Line 21:

== 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|lastlast1=Eliahou|firstfirst1=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 ==