Boolean Pythagorean triples problem: Difference between revisions

Revision as of 16:19, 18 July 2016

Latest revision as of 06:30, 6 July 2025

(63 intermediate revisions by 44 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 relating to [[Pythagorean triple]]s which was solved using a [[computer-assisted proof]] in May 2016.<ref>{{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}}</ref>

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]], which showed that 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|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, a coloring with ''a'' and ''b'' red and ''c'' blue is an admissible coloring, but all three blue would not be.

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 Marek investigated the probelm and showed that such a coloring is impossible. Up to the number 7824 it is possible to color the numbers such that all Pythagorean triples are admissible, but the proof shows that no such coloring can be extended to also color the number 7825. 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 2⁷⁸²⁵ colorings for the numbers up to 7825. These possible colorings were logically narrowed down to just under a trillion cases, and those were examined using a [[Boolean satisfiability]] solver. Creating the proof took two days of computer execution time on the Stampede supercomputer at the [[Texas Advanced Computing Center]] and generated 200 terabytes of data which were compressed to 68 gigabytes.

[[Marijn Heule]], Oliver Kullmann and Victor W. Marek investigated the probelm and showed that such a coloring is impossible. Up to the number 7824 it isonly possible to color the numbers such that all Pythagorean triples are admissible, but the proof shows that no such coloring can be extendedup to also color the number 78257824. 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⁷⁸²⁵ colorings≈ 3.63×10²³⁵⁵}} possible coloring combinations for the numbers up to [[7825 (number)|7825]]. These possible colorings were logically and algorithmically narrowed down to just underaround a trillion (still highly complex) cases, and those, expressed as [[Boolean satisfiability]] problems, were examined using a [[BooleanSAT satisfiabilitysolver]] solver. Creating the proof took twoabout days4 CPU-years of computercomputation executionover timea period of two days on the Stampede supercomputer at the [[Texas Advanced Computing Center]] and generated a 200 terabytesterabyte ofpropositional dataproof, which werewas compressed to 68 gigabytes.

The paper describing the proof was published on arXiv on 3 May 2016<ref name="arXiv">{{Cite arxiv|last=Heule|first=Marijn J. H.|last2=Kullmann|first2=Oliver|last3=Marek|first3=Victor W.|date=2016-05-03|title=Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer |arxiv=1605.00723 }}</ref> and has been accepted for the SAT 2016 conference an won the best paper award in that conference<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|last1=Heule|first1=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]]

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

* [[List of long mathematical proofs]]

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

== References ==

<references />

Line 16 ⟶ 31:

[[Category:Computer-assisted proofs]]

[[Category:Mathematical problems]]

[[Category:Pythagorean theorem]]

[[Category:Ramsey theory]]