I ran into this obstacle in a harmonic analysis problem; I know epsilon about coloring problems.


Is it possible to finitely color Z^2 so that the points (x,a) and (a,y) are differently colored for every x, y and a in the integers (excepting, of course, the trivial cases x=y=a)?



Can I finitely color Z^2 such that (x,a) and (a,y) are different for every x,y,a?
No, this isn't possible. First note that the question is the same if we replace Z with any infinite subset of Z. Now, suppose it were possible to color Z2 with k colors, where k is minimum. Pick any row r. We can find an infinite set S of integers not containing r such that for x in S, all the (x, r) have the same color c. No point in SxS can have color c, so SxS is colored with k-1 colors. But this contradicts the minimality of k.


