MathDB

Boolean Pythagorean triples problem

About 10 years old · traced to

Call a triple (a,b,c)(a,b,c) of positive integers a Pythagorean triple if a2+b2=c2a^{2}+b^{2}=c^{2}; such triples are not required to be primitive, i.e. gcd⁡(a,b,c)\gcd(a,b,c) may exceed 11. For a map χ:Z>0→{red,blue}\chi:\mathbb{Z}_{>0}\to\{\text{red},\text{blue}\}, a Pythagorean triple (a,b,c)(a,b,c) is monochromatic under χ\chi if χ(a)=χ(b)=χ(c)\chi(a)=\chi(b)=\chi(c).

There exists a map

χ:Z>0→{red,blue}\chi:\mathbb{Z}_{>0}\to\{\text{red},\text{blue}\}

such that no Pythagorean triple is monochromatic under χ\chi; equivalently, there is a partition Z>0=R⊔B\mathbb{Z}_{>0}=R\sqcup B such that neither RR nor BB contains positive integers a,b,ca,b,c with a2+b2=c2a^{2}+b^{2}=c^{2}.

References

Primary source

Wikipedia

Additional references

  1. Wikipedia, Boolean Pythagorean triples problem, the article this problem comes from.
unsolved-problem
Posted

Progress summary

Refreshed
Claimed solved

A computer-checked proof settled the problem in 2016, showing that avoiding a single-color right triangle works only up to 7,824.

The problem asks whether all positive integers can be colored red and blue without a single-color triple satisfying a2+b2=c2a^2+b^2=c^2. It is associated with Ronald Graham and Paul Erdős, and was settled by Marijn Heule, Oliver Kullmann, and Victor W. Marek in 2016.

Known results

  • Cooper and Poirel, 2008: a valid coloring exists through 13441344.
  • Heule, Kullmann, and Marek, 2016: a valid coloring exists through 78247824, but every coloring through 78257825 contains a monochromatic Pythagorean triple.
  • The original result used SAT solving and a checkable compressed certificate for the unsatisfiable 78257825 case.

Certified verification, 2016

Independent work verified the SAT proof with an LRAT checker extracted from a Coq formalization, including the relevant proof transformations. This corroborates the computer-assisted resolution; no later gap, withdrawal, or competing claim was found.

Current status (as of August 2026): The finite threshold is settled exactly at 78257825: avoidance is possible through 78247824 and impossible at 78257825, with the computer-assisted proof independently certified; the broader arbitrary-color partition-regularity question remains separate.

Sources

Solutions 0

No solutions have been posted yet.