# Graph coloring problem on Z3

I'm trying to solve the next problem:

Trying to prove that for every $k$ there is an integer $n=n(k)$ so that for any coloring of the set $\mathbb Z_3^n$ of all $n$-dimensional vectors with coordinates in $\mathbb Z_3$ by $k$ colors, there are three distinct vectors $X$, $Y$, $Z$ having the same color so that $X_i+Y_i+Z_i\equiv 0 \pmod 3$ for all $1 \le i \le n$.

I guess I need to use SCHUR proof in a different way but I don’t know exactly how to determine the coloring function. Any help will be appreciated. Thank you very much!

-
Groovy guy: I've tried to edit your post (by adding LaTeX) for better readability. Please, check, whether I did not unintentionally change meaning of your question. – Martin Sleziak Jan 7 '12 at 18:35
is this a case of hales-jewett? en.wikipedia.org/wiki/Hales–Jewett_theorem – yoyo Jan 7 '12 at 18:45
@yoyo: I think so -- I was wondering why you removed your earlier comment about that. The components add to $0$ iff they're either all different or all the same, so the condition is equivalent to the three vectors being on a line. (Here's a working link for convenience.) – joriki Jan 7 '12 at 18:46
More precisely, not all $\{X,Y,Z\}$ as described in the question are "combinatorial lines" as used in the Wikipedia article (a counterexample is $\{12,21,00\}$) but every "combinatorial line" is a valid $\{X,Y,Z\)$, and that is the direction that matters. – Henning Makholm Jan 7 '12 at 18:54
The Hales-Jewett theorem seems a bit of an overkill for a graph theory (so it seems) question. Schur's theorem proof, looks, indeed, like an easier way, as long as the coloring condition stated right. – Pavel Jan 8 '12 at 9:37

Since we are working modulo $3$, the condition $x+y+z=0$ is the same as $x+y=2z$, which happens if and only if we have an arithmetic progression of length $3$. (Specifically, $x,z,y$ form a progression since $z-x=y-z$, and all progressions of length three give rise to such an equation.)
Meshulam's theorem tells us that if $A\subset \mathbb{F}_3^n$ contains no three term arithmetic progressions, then $|A|\ll \frac{N}{\log N}$ where $N=3^n$ is the size of the set $\mathbb{F}_3^n$. This statement above can be proven using some Fourier analysis, and it implies van der Waerden's Theorem, the statement in your question.