5
$\begingroup$

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!

  • 0
    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.2012-01-07
  • 1
    is this a case of hales-jewett? http://en.wikipedia.org/wiki/Hales–Jewett_theorem2012-01-07
  • 0
    @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](http://en.wikipedia.org/wiki/Hales-Jewett_theorem).)2012-01-07
  • 0
    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.2012-01-07
  • 0
    The Hales-Jewett theorem seems a bit of an overkill for a graph theory (so it seems) question. [Schur's theorem proof](http://www.proofwiki.org/wiki/Schur's_Theorem_(Ramsey_Theory)), looks, indeed, like an easier way, as long as the coloring condition stated right.2012-01-08
  • 0
    Thank's for the editing + comments + references I’ll read it all, and try again.2012-01-08
  • 0
    @Henning: Thanks for that -- I was suffering from a misconception of what a combinatorial line is.2012-01-10

1 Answers 1

2

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.

  • 0
    I'll try, yet, searching for an easier answer. Thanks for the insight, though.2012-01-14