How Do I Prove that $\mathbb{E}^d\nrightarrow (l_4)_3$?

80 Views Asked by At

Question

Prove that for all $d\geq 1, \mathbb{E}^d\nrightarrow (l_4)_3$.

That is, we need to prove that there is no way to colour the points in $\mathbb{E}^d$ with 3 colours such that there will always exist 4 collinear points, evenly spaced 1 unit apart, that are all the same colour.

Note: Here, $\mathbb{E}^d$ is $\mathbb{R}^d$ with Euclidean norm-2, $l_k$ is a configuration of $k$ points in a line, separated by unit distances, and r is the number of colours. So, $(l_k)_r$ would mean colouring $\mathbb{E}^d$ using $r$ number of colours to get monochromatic $k$-points.

Note: We may consider $c(v)=\lfloor 2\lVert v \rVert^2\rfloor mod 3$ (I used $c(v)=\lfloor \lVert v \rVert^2\rfloor mod 4$ for $\mathbb{E}^d\nrightarrow (l_3)_4$, and the solution worked out well). Here, $c$ is the colouring function, $v$ is vertex (or points).

Attempt We use prove by contradiction. Suppose:

$c(x-u)=c(x)=c(x+u)=c(x+2u)=r$, where $r\in \{0,1,2\}$.

Then, we have the following equations:

$2\lVert x-u \rVert^2 = 3a+r+\alpha$

$2\lVert x \rVert^2 = 3b+r+\beta$

$2\lVert x+u \rVert^2 = 3c+r+\gamma$

$2\lVert x+2u \rVert^2 = 3a+r+\theta$

where $\alpha,\beta,\gamma,\theta \in [0,1)$.

Expanding the norms and simplifying the resulting equations by taking one equation form another, we have:

$4=3(a-b-c+d)+\alpha -\beta -\gamma +\theta$.

Although this looks like a contradiction since $-2<\alpha -\beta -\gamma +\theta<2$. However, since we are dealing with $mod 3$ here, I am thinking of re-writing this equation as:

$1=3(a-b-c+d-1)+\alpha -\beta -\gamma +\theta$.

The problem is, this is not a contradiction anymore. I am not sure if there is something I am mixing up here. Your help would be greatly appreciated.