Splitting Pythagorean triples

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.

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?

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.