# 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

1
– yoyo Jan 7 '12 at 18:45
– 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
– Pavel Jan 8 '12 at 9:37
show 2 more comments

## 1 Answer

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.

I can provide some more details if this interests you. The proof of Meshulam's is not long, but is lengthened considerably if Fourier transforms need to be defined and introduced.

-

I'll try, yet, searching for an easier answer. Thanks for the insight, though. – Pavel Jan 14 '12 at 10:13
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9176238179206848, "perplexity_flag": "head"}