Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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  
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
show 2 more comments

1 Answer 1

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.

share|improve this answer
    
I'll try, yet, searching for an easier answer. Thanks for the insight, though. –  Pavel Jan 14 '12 at 10:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.