Splitting Pythagorean triples

Question

Can one partition the set of positive integers into finitely many Pythagorean-triple-free subsets? If so, what is the smallest number of such subsets? Taking a wild guess, I would be least surprised if the answer were 3.

Notice that the 2 subsets of integers such that highest power of 5 that divides them is a) even b) odd manage to split most primitive triples, plus all the multiples of those.

Notice also that Schur proved the positive integers cannot be split into any finite number of sum-free subsets (i.e. no finite partition can split all power-of-1 Fermat triples), while Fermat's theorem proves that all power-of-n (n>2) triples can be split by the trivial partition into 1 set.

Edit: Since this turns out to be a known open problem, we're adding the tag [open-problem] and converting this question to community wiki. The idea is to have a separate answer for each possible approach to solving this problem. If you have some additional insight or a reference to contribute to an answer, you only need 100 rep to do so. We're still figuring out exactly how to handle open problems on MO. The discussion is happening on this tea.mathoverflow.net thread.

Answer 1

This problem appears in Croot and Lev's 2007 "Open Problems in Additive Combinatorics" (http://people.math.gatech.edu/~ecroot/E2S-01-11.pdf ), where it is attributed to Erdos and Graham (the latter of whom offers $250 for its solution).

Other references may include Cooper and Poirel's "Notes on the Pythagorean Triple System" (http://www.math.sc.edu/~cooper/pth.pdf ), which mentions that even the case of whether 2 colors is enough is open. They also exhibit a 2-coloring of the integers from 1 to 1344 without any monochromatic Pythagorean triples.

UPDATE (5/4/16): A new preprint of Heule, Kullmann, and Marek (to appear in the SAT 2016 conference) answers the question for $2$ subsets in the negative: If $\{1,2,\dots,7825\}$ is split into two subsets, one subset must contain a pythagorean triple. The $7825$ here is tight. The proof is heavily computer-assisted, and the key ideas seem to be to cast the problem in the language of satisfiability, and set up a divide-and-conquer method so that the (enormous) resulting instance is handleable by state-of-the-art satisfiability solvers.

Answer 2

One way of rephrasing part of David Eppstein's answer: the stronger ("Szemeredi-type") assertion that a positive-density subset of the integers contains infinitely many Pythagorean triples is NOT true, as your example of the set of integers with odd parts 3 mod 4 (or, I guess, the set of odd integers) shows.

Idle question, vaguely phrased: can you construct a positive-density subsequence of Z which contains no Pythagorean triples, but for no obvious p-adic reason?

Orthogonal idle question: can you partition Z_p - 0 into finitely many pieces such that none contains a solution to x^2 + y^2 = z^2?

Answer 3

One can get part of the way there with a two-part partition into the numbers whose odd parts are 1 mod 4 and 3 mod 4 respectively.

Every Pythagorean triple has the form k^2(m^2-n^2), k^2(2mn), k^2(m^2+n^2), for some k, m, and n, with m and n having different parity from each other and m > n. The two-part partition described above puts k^2(m^2-n^2) and k^2(m^2+n^2) into different partitions whenever m is even and n is odd.

However, this doesn't split the triples with m odd, n even, and the odd parts of m and n both congruent to 1 mod 4: in that case, a, b, and c will all have odd parts congruent to 1 mod 4. E.g. k=1 m=5 n=2: the Pythagorean triple 21,20,29 is not split by this two-way partition.

Answer 4

Consider a greedy strategy: construct sets S1, S2, S3, ... by in turn putting each positive integer c in the smallest-numbered set that doesn't already contain a, b with a^2 + b^2 = c^2.

Then S2 = {5, 10, 15, 20, 30, 35, 40, 45, 55, 60, 70, 80, 90, 95, 105, 110, 115, 120, ...} S3 = {25, 50, 65, 75, 85, 100, ...} S4 = {125, ...}

The pattern appears obvious at first. But 65 is in S3! It can't go in S1 because (52,39,65), (56,33,65), and (63,16,65) are Pythagorean triples; it can't go in S2 because (60,25,65) is as well. Similarly, (68,51,85) and (75,40,85) are both triples.

S4 forms when we hit 125; the triples (117,44,125), (120,35,125), and (100,75,125) block it from S1, S2, and S3 respectively. Since 5^n will be the hypotenuse of n Pythagorean triples, with greatest common divisors 5^0, 5^1, ..., 5^(n-1), I conjecture that the smallest member of Sn is usually 5^(n-1).

In short, if the answer is 3 (or, I suspect, any finite number), a greedy algorithm won't prove it.