Boolean Pythagorean triples problem: Difference between revisions

Revision as of 12:07, 1 June 2016

Latest revision as of 06:30, 6 July 2025

(72 intermediate revisions by 51 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''' was 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 part of the [[Infinitary combinatorics|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.

The proof shows 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 for any coloring for which all the triples up to 7824 are multi-colored, not all those involving 7825 are multi-colored. 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==

[[Marijn Heule]], 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"/>}}

}}

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 thea [[bruteSAT force methodsolver]]. TheCreating 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 proof, which was compressed to 68 datagigabytes.

In the 1980s [[Ronald Graham]] offered a $100 prize for the solution of the problem, which has now been awarded to Marijn Heule. The paper describing the proof was published onin arXivthe on 3 MaySAT 2016 conference,<ref name="arXiv">{{Cite journalconference|lastlast1=Heule|firstfirst1=Marijn J. H.|last2=Kullmann|first2=Oliver|last3=Marek|first3=Victor W.|dateauthor3-link=Victor W. Marek|year=2016-05-03|titlecontribution=Solving and Verifying the booleanBoolean Pythagorean Triples problem via Cube-and-Conquer |urlarxiv=http://arxiv.org/abs/1605.00723|journaldoi=arXiv:160510.007231007/978-3-319-40970-2_15|series=Lecture [cs]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> andwhere hasit beenwon acceptedthe forbest thepaper award.<ref>[http://sat2016.labri.fr/ SAT 2016]</ref> conferenceThe 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]]

== References ==

Line 16 ⟶ 31:

[[Category:Computer-assisted proofs]]

[[Category:Mathematical problems]]

[[Category:Pythagorean theorem]]

[[Category:Ramsey theory]]