The Polychromatic Number of the Plane

Assume that there is a 3-colouring of the plane

\begin{equation*} c:\mathbb{E}^2\to\{\color{red}{\bullet},\color{blue}{\bullet},\color{green}{\bullet}\} \end{equation*}

such that
- There are no two points coloured \(\color{red}{\mbox{red}}\) at the distance \(r\text{;}\)
- There are no two points coloured \(\color{blue}{\mbox{blue}}\) at the distance \(b\text{;}\)
- There are no two points coloured \(\color{green}{\mbox{green}}\) at the distance \(g\text{.}\)
Let a Cartesian coordinate system in \(\mathbb{E}^2\) be given.
We construct three Moser spindles like on Figure 6.4.5:

Figure 6.4.5. Three Moser spindles share the origin \(O\) as a common point and with the edges of lengths \(r\text{,}\) \(b\text{,}\) and \(g\text{.}\)
Consider 18 vectors, each of them with its initial point at the origin and the terminal point being a vertex in one of the three Moser spindles.

Call those vectors

\begin{equation*} \vec{v}_1, \vec{v}_2, \ldots, \vec{v}_6, \vec{v}_7, \vec{v}_8, \ldots, \vec{v}_{12},\vec{v}_{13},\vec{v}_{14},\ldots, \vec{v}_{18}\text{.} \end{equation*}

Here the terminal points of the vectors \(\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_6\) belong to the Moser spindle with all edges of length \(r\text{,}\) the terminal points of the vectors \(\vec{v}_7, \vec{v}_8, \ldots, \vec{v}_{12}\) belong to the Mosers spindle with all edges of length \(b\text{,}\) and the terminal points of the vectors \(\vec{v}_{13}, \vec{v}_{14}, \ldots, \vec{v}_{18}\) belong to the Moser spindle with all edges of length \(g\text{.}\) See Figure 6.4.6.

Figure 6.4.6. Eighteen vectors with the same initial point.
Next we define a 3-colouring \(c'\) of the vector space

\begin{equation*} \mathbb{E}^{18}=\{ (a_1,a_2,\ldots, a_{18}): a_1,a_2,\ldots, a_{18}\in\mathbb{R}\} \end{equation*}

by

\begin{equation*} c'(a_1,a_2,\ldots, a_{18})=c(P) \end{equation*}

where \(P\) is the terminal point of the vector

\begin{equation*} a_1\cdot \color{red}{\vec{v}_1}+\cdots + a_6\cdot \color{red}{\vec{v}_6}+a_7\cdot \color{blue}{\vec{v}_7}+\cdots + a_{12}\cdot \color{blue}{\vec{v}_{12}}+a_{13}\cdot \color{green}{\vec{v}_{13}}+\cdots + a_{18}\cdot \color{green}{\vec{v}_{18}}\text{.} \end{equation*}
Let \(M\subset \mathbb{E}^{18}\) be the set of all 18-tuples such that \((a_1,a_2,\ldots,a_{18})\in M\) if and only if all of the following conditions are satisfied:
1. \(a_i\in \{0,1\}\) for all \(i\in \{1,2,\ldots,18\}\text{;}\)
2. \(\displaystyle a_1+a_2+a_3+a_4+a_5+a_6\in \{0,1\}\)
3. \(\displaystyle a_7+a_8+a_9+a_{10}+a_{11}+a_{12}\in \{0,1\}\)
4. \(\displaystyle a_{13}+a_{14}+a_{15}+a_{16}+a_{17}+a_{18}\in \{0,1\}\)
For example

\begin{equation*} (\underbrace{1,0,0,0,0,0}_{1\leq i\leq 6},\underbrace{0,0,0,0,0,1}_{7\leq i\leq 12},\underbrace{1,0,0,0,0,0}_{13\leq i\leq 18})\in M \end{equation*}

but

\begin{equation*} (\underbrace{1,0,0,0,0,0}_{1\leq i\leq 6},\underbrace{0,0,0,0,0,0}_{7\leq i\leq 12},\underbrace{1,1,0,0,0,0}_{13\leq i\leq 18})\not\in M\text{.} \end{equation*}
Note that

\begin{equation*} |M|=7^3\text{.} \end{equation*}
Consider the set

\begin{equation*} M_{r}=\{(a_1,a_2,a_3,a_4,a_5,a_6,\underbrace{0,0,\cdots,0}_{\text{ All 0's } })\in M: a_1,\ldots, a_6\in\{0,1\}\} \end{equation*}

and note that \(|M_{r}|=7\text{.}\)
Two observations and a conclusion:
1. If \((a_1,a_2,a_3,a_4,a_5,a_6,\underbrace{0,0,\cdots,0}_{\text{ All 0's } })\in M_{\color{red}{r}}\) and \(a_i\not= 0\) for some \(i\in \{1,\ldots,6\}\text{,}\) then
  
  \begin{equation*} \vec{OP}=a_1\cdot \color{red}{\vec{v}_1}+\cdots + a_6\cdot \color{red}{\vec{v}_6}+0\cdot \color{blue}{\vec{v}_7}+\cdots + 0\cdot \color{blue}{\vec{v}_{12}}+0\cdot \color{green}{\vec{v}_{13}}+\cdots + 0\cdot \color{green}{\vec{v}_{18}} =\color{red}{\vec{v}_i} \end{equation*}
  
  and \(P\) is one of the points in the Moser spindle that has all edges of length \(\color{red}{r}\text{.}\)
2. The Moser spindle that has all edges of length \(\color{red}{r}\) cannot have three red vertices:
  
  Figure 6.4.7. If there are three \(\color{red}{r}\) vertices then two of them are \(\color{red}{r}\) units apart.
3. The set \(M_{\color{red}{r}}\) can have at most two elements coloured \(\color{red}{r}\) by the colouring \(c'\text{.}\)
Another observation:

Figure 6.4.8. A translate of the Moser spindle is the Moser spindle.

For each of the 49 elements of the set

\begin{equation*} M_{\color{blue}{b}\color{green}{g}}=\{(0,0,0,0,0,0,a_7,a_8,\ldots,a_{18})\in M: a_7,\ldots, a_{18}\in\{0,1\}\} \end{equation*}

we make a translate of \(M_{\color{red}{r}}\) in \(\mathbb{E}^{18}\text{:}\)

\begin{equation*} M_{\color{red}{r}}^a=a+M_{\color{red}{r}}, \ a\in M_{\color{blue}{b}\color{green}{g}}\text{.} \end{equation*}

Clearly

\begin{equation*} M=\cup_{a\in M_{\color{blue}{b}\color{green}{g}}}M_{r}^a \end{equation*}

and, for all \(a,b\in M_{\color{blue}{b}\color{green}{g}}\text{,}\)

\begin{equation*} a\not=b \Rightarrow M_{\color{red}{r}}^a\cap M_{\color{red}{r}}^b=\emptyset\text{.} \end{equation*}

In other words we have divided the set \(M\) into \(7^2=49\) mutually disjunct copies of \(M_{\color{red}{r}}\text{.}\)

How many elements in \(M_{\color{red}{r}}^a\text{,}\) \(a\in M_{\color{blue}{b}\color{green}{g}}\text{,}\) are coloured \(\color{red}{\mbox{red}}\) by \(c'\text{?}\)
Let \((0,0,0,0,0,0,a_7,a_8,\ldots,a_{18})\in M_{\color{blue}{b}\color{green}{g}}\) and let

\begin{equation*} \vec{a}=0\cdot \color{red}{\vec{v}_1}+\cdots + 0\cdot \color{red}{\vec{v}_6}+a_7\cdot \color{blue}{\vec{v}_7}+\cdots + a_{12}\cdot \color{blue}{\vec{v}_{12}}+a_{13}\cdot \color{green}{\vec{v}_{13}}+\cdots + a_{18}\cdot \color{green}{\vec{v}_{18}}\text{.} \end{equation*}

Then the elements of \(M_{\color{red}{r}}^a\) are coloured by \(c'\) in the same way that \(c\) colours the vertices of the Moser spindle that is obtained as the translate of the original Moser spindle by \(\vec{a}\text{!}\)

Therefore, for each \(a\in M_{\color{blue}{b}\color{green}{g}}\text{,}\) the set \(M_{\color{red}{r}}^a\) can have at most TWO \(\color{red}{\mbox{ red }}\) elements.
\begin{align*} \#\text{ of } \color{red}{\mbox{ red }} \text{ elements of } M\amp =\amp \sum _{a\in M_{\color{blue}{b}\color{green}{g}}}\#\text{ of } \color{red}{\mbox{ red }} \text{ elements of } M_{\color{red}{r}}^a\\ \amp \leq\amp \sum _{a\in M_{\color{blue}{b}\color{green}{g}}}2=2\cdot 49=98\text{.} \end{align*}
Similarly

\begin{equation*} \#\text{ of } \color{blue}{\mbox{ blue }} \text{ elements of } M\leq 98 \end{equation*}

and

\begin{equation*} \#\text{ of } \color{green}{\mbox{ green }} \text{ elements of } M\leq 98\text{.} \end{equation*}

Therefore

\begin{align*} 7^3\amp =\amp (\#\text{ of }\color{red}{\mbox{ red }} \text{ elements of } M)+(\#\text{ of } \color{blue}{\mbox{ blue }} \text{ elements of } M)\\ \amp +\amp (\#\text{ of } \color{green}{\mbox{ green }} \text{ elements of } M) \leq 3\cdot 98=3\cdot (2\cdot 7^2)=6\cdot7^2\text{.} \end{align*}

Contradiction!
Therefore, our assumption that there is a 3-colouring of the plane

\begin{equation*} c:\mathbb{E}^2\to\{\color{red}{\bullet},\color{blue}{\bullet},\color{green}{\bullet}\} \end{equation*}

such that
- There are no two points coloured \(\color{red}{\mbox{red}}\) at the distance \(\color{red}{r}\text{;}\)
- There are no two points coloured \(\color{blue}{\mbox{blue}}\) at the distance \(\color{blue}{b}\text{;}\)
- There are no two points coloured \(\color{green}{\mbox{green}}\) at the distance \(\color{green}{g}\text{;}\)
led to a contradiction!
Each colour of every 3-colouring of the plane realizes all distances. This implies

\begin{equation*} 4\leq \chi_p\text{.} \end{equation*}

Introduction to Ramsey Theory: Lecture notes for undergraduate course

Section 6.4 The Polychromatic Number of the Plane

Example 6.4.1.

Definition 6.4.3.

Observation 6.4.4.

Proof.

Theorem 6.4.12.