Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Yesterday I came up with a problem: Can we color each point of the plane with finitely many colors such that there doesn't exist any monochromatic regular polygonal?

But I found the problem is too hard for me(maybe someone could solve it for me, or the problem has been studied), so I considered the weaker form: Can we color each point of the plane with finitely many colors such that there doesn't exist any monochromatic equilateral triangle?

After some case discussion, one can prove that only two colors isn't enough, then I have no idea how to work on three colors.

If we use complex number, the problem becomes: Let $\mathbb{Z}[\omega]=\{a+b\omega\mid a,b\in\mathbb{Z},\;\omega=e^{\frac{2i\pi}{3}}\}.$ Can we color each elements of $\mathbb{Z}[\omega]$ such that there doesn't exist any monochromatic solution $(x,y,z)$ to the equation $x^2+y^2+z^2=xy+yz+zx$?

More generally, give a $n$-variable equation $f(x_1,\dots,x_n)$ and a infinite set $S$, can we color each elements of $S$ such that there doesn't exist any monochromatic solution $(x_1,\dots,x_n)$ to the equation $f(x_1,\dots,x_n)=0$?

share|improve this question
    
See mathoverflow.net/questions/33832/… for related information. –  Tony Huynh Jul 11 '13 at 20:26
    
See also this nicely presented expository note by T. Tao (p. 12 in particular): math.ucla.edu/~tao/preprints/Expository/ramsey.dvi –  Daniel m3 Jul 16 '13 at 11:10

2 Answers 2

I think the statement on polygons follows rather directly from the Hales-Jewett theorem. Let $\phi_0,\dots,\phi_{k-1}$ be finitely many linear transformations(=multiplication by a nonzero complex number) of the plane. If the plane (or a sufficienly large finite part of it) is colored by $r$ colors, then there are vectors $a, a+b, a+\phi_0(b),\dots,a+\phi_{k-1}(b)$ with the same color.

The HJ theorem says that given $k$ and $r$, there is some $n$ such that if all functions $f:n\to k$ are colored with $r$ colors, then there is a monocolored line, i.e. some functions $f_0,\dots,f_{k-1}$ such that for some nonempty $J\subseteq n$ the $f_i$'s agree outside $J$ and $f_i(j)=i$ for $j\in J$.

Given $n$ as in the HJ theorem, choose the vectors $a_0,\dots,a_{n-1}$ such that they are independent in the sense that all vectors of the form $v(f)=\sum_{i=0}^{n-1} a^i_{f(i)}$ are distinct, where $a^i_0=0$, $a^i_1=a_i$, $a^i_{j+2}=\phi_j(a_i)$. Let $c$ be a coloring of the plane and set $F(f)=c(v(f))$. BY HJ, there is a monocolored line. Let $J\subseteq n$ as in the theorem. If $b=\sum_{i\in J} a(i)$, then we get that for some $a$, the vectors $a,a+b,a+\phi_0(b),\dots,a+\phi_{k-1}(b)$ are monocolored.

share|improve this answer

Whenever the plane is finitely coloured we can find monochromatic scaled and translated ("homothetic") copies of any finite set of points. This is essentially Gallai's theorem.

Let $S=\{v_1, \ldots, v_k\}$ be a finite set of vectors and $c$ be a colouring of the plane. For large $n$, consider the colouring $(x_1, \ldots, x_n) \mapsto c(x_1 + \cdots + x_n)$ of $S^n$. By the Hales-Jewett theorem there is a monochromatic line. If the active set has size $l$ and the sum of the fixed coordinates is $a$ then this monochromatic line corresponds to the monochromatic set $a+l\cdot S$. This argument also works in higher dimensions, and for sets like $\mathbb N^k$ without a full vector space structure.

A function $f : \mathbb N^k \to \mathbb Z^l$ is called partition regular if, whenever $\mathbb N$ is finitely coloured, there is a monochromatic vector $x$ such that $f(x) = 0$. If we restrict ourselves to polynomials then Gallai's theorem is not as useful as it seems for constructing partition regular functions. For example, it tell us that we can find a monochromatic arithmetic progression of length 3. (Van der Waerden's theorem is a special case of Gallai's theorem.) An arithmetic progression $(a, a+d, a+2d)$ is a root of $f(x, y, z) = x - 2y + z$, but so too is the constant vector $(a, a, a)$. In fact, there is no system of linear equations whose solution sets are precisely the arithmetic progressions of length 3.

Rado gave a beautiful characterisation of the finite partition regular systems of linear equations. For infinite systems of equations very little is known.

If we allow non-linear functions then things get even harder. It is not even know whether, whenever $\mathbb N$ is finitely coloured, there exist $x$ and $y$ such that $xy$ and $x+y$ are the same colour—even if we don't care about the colours of $x$ and $y$!

share|improve this answer

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.