Post Made Community Wiki by Anton Geraschenko♦♦
2 added 19 characters in body

One way of rephrasing this commentpart 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?

1

One way of rephrasing this comment: 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?