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
    @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