The Boolean Pythagorean triples problem asks whether the positive integers admit a coloring with two colors in which no Pythagorean triple has all three entries the same color. The restriction applies to all Pythagorean triples, including nonprimitive ones.
Heule et al. (2016) proved that the integers from 1 through 7824 admit such a coloring, but those from 1 through 7825 do not. Thus 7825 is the least finite cutoff that forces a same-color Pythagorean triple, and the infinite problem has a negative answer. Their proof is computer-assisted. The problem is an example of Ramsey theory.
For a positive integer 
, let 
be the set of Pythagorean
triples 
with 
. Introduce Boolean
variables 
, with True and False
representing the two colors. The conjunctive
normal form
![F_N= ^ _((a,b,c) in T_N)[(x_a v x_b v x_c) ^ (¬x_a v ¬x_b v ¬x_c)]](/images/equations/BooleanPythagoreanTriplesProblem/NumberedEquation1.svg) |
is satisfiable iff an admissible coloring exists. Here 
, 
, and 
denote OR, AND,
and NOT. Each pair of clauses
excludes the two assignments in which its three Boolean
variables agree (Heule et al. 2016).
For a positive integer 
, let 
count the admissible colorings
of 
,
with the two colors labeled. The values 
begin 2, 4, 8, 16, 24, 48, 96, 192, ... (OEIS
A272709), and 
for 
. A finite partial coloring
for 
is encoded by OEIS A383181: codes 1 and 2 denote
fixed colors, while each code 0 may independently receive either color. Its 2899
free positions therefore give the lower bound 
.
