More On Coloring The Plane

May 22, 2011

tags: color plane, open, Problems, Proof, transfer

by rjlipton

An approach to the plane coloring problem

John Isbell was a mathematician who has made many contributions to topology, category theory, and diverse aspects of algebra. He is considered to have been one of the top experts on uniform spaces, which are topological spaces with extra structure.

Today I want to return to the problem of coloring the points of the Euclidean plane.

Recently I mentioned this problem, which is due to Ed Nelson, and has been open over fifty years. Isbell still has the best upper bound on the problem: an almost sixty years result. I have no idea how to solve the problem, but have some small observations that I thought might be interesting to share.

First I have two stories that I must relate on Isbell, before getting to the math. I just recently discovered—thanks to our friends at Wikipedia—that Isbell published several papers under pseudonyms. One was under the name “John Rainwater” and some under the names “M. G. Stanley” and “H. C. Enos.” I have no idea why he did this, but it seems to be an interesting tidbit. Do any of you use secret pseudonyms? I guess you would not tell me, but I had to ask. There is an old story about pseudonyms involving Edmund Landau, Godfrey Hardy, and John Littlewood:

Landau thought that “Littlewood” was a pseudonym for Hardy (so it would not seem that Hardy was writing all the papers).

True? Who knows.

As I wrote before, I took a projective geometry course from Isbell when I was a senior at Case Western Reserve University. The course was nominally for sophomores, but I had taken most other math courses and it seemed like a good idea to learn some geometry. I almost failed the course. The textbook we used was very vague and informal; even the definition of a projective plane was never given. There were examples and informal discussions but nothing direct like, “A projective plane is a structure ${\dots}$ ”

I spent hours and hours trying to understand what was going on—what is a projective plane? I looked at other books, but they did not synch with Isbell’s lectures at all. I finally remember getting it—I figured out what a projective plane is. I went to his office. I recall he was seated behind his desk with his feet up. I said, “Professor Isbell, I think I finally get what a projective plane is. It is ${\dots}$ ” He listen politely and I still recall his exact answer:

“You could view it that way.”

This was not too helpful. On homework and exams I continued to get terrible grades. I think the problem was that by the time I was a senior I was used to a certain level of rigor. And I could not “prove” any of the theorems I was asked to because I had no rigorous definitions to work with, no firm basis to argue from. The rest of the class were more junior students who had no problems. They would get A’s on the exams, and when they showed me their returned exams their answers made no sense to me. I felt like they and Isbell were talking in some foreign language, a language which I not only did not know, but even lacked a dictionary for.

I should have dropped the course. But instead I worked even harder, putting more hours in, and I decided that I was going to pass the course—somehow. It all came down to the final exam, which I needed not only to pass but to do very well on, if I were to pass the whole class.

Then a miracle happened. The day of the final exam came and Isbell handed it out. I looked at it and was shocked. It had nothing to do with projective geometry. Nothing. It was a general algebra exam: the questions were all on groups, rings, fields, and so on. I thought he handed us the wrong exam. Indeed someone asked, and he said no, it was the final exam. I aced it, while the all the rest of the class did not do so well. I got a B.

Coloring The Plane

The plane-coloring problem first stated by Ed Nelson in 1950 is: How many colors are needed to assign each point of the plane a color so that no two points exactly distance ${1}$ apart have the same color? The value is known to be either ${4}$ , ${5}$ , ${6}$ , or ${7}$ ; the lower bound is due to Leo Moser and the upper bound is due to Isbell.

The following graphic shows Isbell’s insight:

The hexagons are somewhat less than unit-distance across, but with more than unit distance to the nearest of the same color, so seven colors suffice. The seven color sets are translations of each other, and Hugo Hadwiger in 1945 had used the same pattern to give an upper bound of 7 on the related problem of tessellating the plane by congruent sets, whose best-known lower bound is 5.

There is a vast literature on this problem, although the main question has not been dented in decades. The results are on generalizations and restrictions of the simple sounding problem: how many colors are needed to color the plane?

Coloring Fields

In order to study the coloring problem on the plane I plan to look at a related question of coloring fields. The plane can be viewed as the product ${\mathbb{R}^{2}}$ of the set of the reals. Obviously we can study the coloring problem for other “planes,” where we replace the reals by another field.

Define

$\displaystyle d(x,y,r,s) = (x-r)^{2} + (y-s)^{2}.$

Note that ${d(x,y,r,s)=1}$ means that the “distance” between the pair ${(x,y)}$ and ${(r,s)}$ is ${1}$ . We have put “distance” in quotes because over fields other than the reals this need not be the square of a true metric—indeed over ${\mathbb{C}}$ the value need not even be a real number.

Say a field ${\mathcal F}$ is ${(m,\ell)}$ -colorable provided for any set ${A \subseteq \mathcal{F}}$ of cardinality ${m}$ , there is a coloring ${\chi}$ of ${A^{2}}$ with ${\ell}$ colors so that for all ${x,y,r,s \in A}$ ,

$\displaystyle d(x,y,r,s)=1 \implies \chi(x,y) \neq \chi(r,s).$

On the Axiom of Choice, Erdős proved with Nicolaas de Bruijn that every infinite graph ${G}$ is colorable with ${\ell}$ colors provided every finite subgraph of ${G}$ is colorable with ${\ell}$ colors. This applies whether vertices in ${G}$ are points ${(x,y)}$ and ${(r,s)}$ in the real plane ${\mathbb{R}^2}$ or the complex plane ${\mathbb{C}^2}$ , and whether the edge relation is Euclidean distance ${1}$ or ${d(x,y,r,s) = 1}$ . The advantage of the latter is that it can be written over the language of all fields. Whereas, the definition of Euclidean distance in ${\mathbb{C}}$ involves the notion of real and imaginary part which does not apply to all fields, and Euclidean distance itself does not even make sense over finite fields.

Using ${d}$ enables us to exploit a consequence of ${\mathbb{C}}$ being algebraically closed, whereas ${\mathbb{R}}$ is not.

Finite Fields

A powerful meta-principle that I have discussed before is the close connection between questions about complex numbers and finite fields. For a much better explanation than I could give, please see the discussion a while ago by Terence Tao here.

The mathematical statement allows us to transfer statements between certain fields:

Theorem: The following are all equivalent for any first order sentence ${S}$ over the language of fields:

The sentence ${S}$ is true over the complex field.
The sentence ${S}$ is true over all algebraically closed fields.
The sentence ${S}$ is true over some algebraically closed field.
The sentence ${S}$ is true over all finite fields ${F_{p}}$ with sufficiently large characteristic ${p}$ .

This is a beautiful result that can be used to reduce a question about the complex numbers to finite fields. We apply it for particluar ${\ell,m > 0}$ when ${S}$ is the statement ${(\forall a_1,\dots,a_m)M}$ , where

$\displaystyle M = \vee_{c_1,\dots,c_{m^2} \in \{1,\dots,\ell\}} \wedge_{h,i,j,k}[d(a_h,a_i,a_j,a_k) = 1 \rightarrow c_{h,i} \neq c_{j,k}].$

This expresses that the field is ${(m,\ell)}$ -colorable, and below we call it ${\Delta(m,\ell)}$ . Note that ${\Delta(m,\ell)}$ is a simple universal sentence.

Coloring Connection

The following new theorem connects the complex plane coloring problem with finite fields. (Ken fixed my original version and wrote the second part of this section.)

Theorem: The following statements are equivalent for any ${\ell}$ :

The complex numbers are ${(m,\ell)}$ -colorable for all natural numbers ${m}$ .
The complex plane is ${\ell}$ -colorable with ${d(x,y,r,s) = 1}$ as the edge relation.
For each ${m}$ , there is a ${m_{0}}$ so that for all finite fields of characteristic ${p>m_{0}}$ are ${(m,\ell)}$ -colorable.

Proof: Let’s prove that ${(1) \implies (2)}$ . This follows from the Erdős-de Bruijn theorem applied to the infinite graph with vertex set ${\mathbb{C^2}}$ and edges connecting ${(x,y)}$ and ${(r,s)}$ if ${d(x,y,r,s) = 1}$ .

Let’s next prove that ${(2) \implies (1)}$ . This is trivial, since by definition if the complex plane is ${\ell}$ -colorable under ${d}$ , then the complex field is ${(m,\ell)}$ colorable for all ${m}$ .

Let’s next prove that ${(1) \implies (3)}$ . The key insight is our having a first-order sentence ${\Delta(m,\ell)}$ over the language of fields that encodes that the field is ${(m,\ell)}$ -colorable. By ${(1)}$ it follows that ${(3)}$ is true by the Transfer theorem.

Let’s finally prove that ${(3) \implies (1)}$ . Assume that ${(3)}$ is true, but ${(1)}$ is not. Then there is a proof in the theory of ${\mathbb{C}}$ that ${\Delta(m,\ell)}$ is false. But this proof transfers to all finite fields with large enough characteristic, which is a contradiction with ${(3)}$ . $\Box$

Thus by working over finite fields, we can address exactly the problem of coloring the complex plane under ${d}$ . But our original problem is for the real plane under Euclidean distance, for which we have a better intuition. The following theorem gives a one-sided relation.

Theorem: For all ${\ell > 0}$ , if ${\mathbb{C}}$ is ${(m,\ell)}$ -colorable for all ${m > 0}$ , then the real plane is ${\ell}$ -colorable.

Proof: ${\mathbb{R}}$ is a sub-field of ${\mathbb{C}}$ , so the hypothesis implies that ${\mathbb{R}}$ is ${(m,\ell)}$ -colorable for all ${m}$ . When the ${d}$ function above is restricted to values in ${\mathbb{R}}$ , ${d(x,y,r,s) = 1}$ is equivalent to the points ${(x,y)}$ and ${(r,s)}$ having Euclidean distance ${1}$ in the plane. The conclusion thus follows from the Erdős-de Bruijn theorem applied to the graph in the real plane. $\Box$

Thus if we can ${\ell}$ -color the ${d(\cdot) =1}$ graphs of all finite fields (of sufficiently large characteristic, if that helps), then we can ${\ell}$ -color the plane.

We would like this to be an if-and-only-if, so that lower bounds on finite fields would apply to the plane. Here is a possible strategy for doing so. Fix any ${\ell}$ ; of course we are interested only in the values ${\ell = 4}$ through ${\ell = 7}$ . Working by contraposiiton and viewling the last proof, this is what we want to show: if there is some ${m > 0}$ for which ${\mathbb{C}}$ is not ${(m,\ell)}$ -colorable, then there is some ${m' > 0}$ for which ${\mathbb{R}}$ is not ${(m',\ell)}$ -colorable. Let a witnessing ${A \subset \mathbb{C}}$ of size ${m}$ be given, and look at the graph on ${A^2}$ defined by ${d(\cdot) = 1}$ . Each edge of the graph involves complex numbers ${x,y,r,s}$ such that ${d(x,y,r,s) = 1}$ . Using the original Roman letters for real parts and Greek for imaginary parts, this means

$\displaystyle \begin{array}{rcl} 1 &=& (x + i\xi - (r + i\rho))^2 + (y + i\upsilon - (s + i\sigma))^2\\ &=& ((x - r) + i(\xi - \rho))^2 + ((y - s) + i(\upsilon - \sigma))\\ &=& (x - r)^2 + (y - s)^2 - (\xi - \rho)^2 - (\upsilon - \sigma)^2 \\ & & + 2i(x-r)(\xi-\rho) + 2i(y-s)(\upsilon-\sigma). \end{array}$

Since the imaginary part must vanish, this gives ${(x-r)(\xi-\rho) = -(y-s)(\upsilon-\sigma)}$ . If this entailed that one (and a-fortiori both) of ${(\xi - \rho)}$ and ${(\upsilon-\sigma)}$ had to vanish, the real parts would automatically become a finite subset of the Euclidean plane that is not ${\ell}$ -colorable. Unfortunately it does not. However, it might be strong enough to allow these points to be copied and translated in a way that creates a larger finite set ${B}$ of points in the plane that is not ${\ell}$ -colorable. Note that ${B}$ is a subset of ${A'^2}$ where ${A'}$ collects all co-ordinates of points in ${B}$ , so we would in fact have ${m' > 0}$ such that ${\mathbb{R}}$ is not ${(m',\ell)}$ -colorable.

Open Problems

Can we use the power of finite fields to solve the coloring problem? At least for complex fields, or at least possibly to improve Isbell’s upper bound in the real plane case? I have tried some natural ways to “color” pairs of numbers from a finite field and have not been able to discover one that works. Perhaps you can.

Can equivalence be proved in the relation between the real and complex cases? Does the suggested strategy work?

Update

See the first comment for the gist of this paper by Alex Iosevich and Misha Rudnev. It does not cite Erdős-de Bruijn so maybe this post helps draw some further consequences. Kudos, noticed within two hours of posting! Others are welcome to pitch in.

[Other updates: changed featured picture, fixed last formula and occurrences of “Erdős.”]

8 Comments leave one →

iosevich permalink

May 22, 2011 3:36 pm

Over finite fields, the chromatic number of the distance graph can be easily computer using my result with Misha Rudnev: Erdős distance problem in vector spaces over finite fields. Trans. Amer. Math. Soc. 359 (2007), no. 12, 6127–6142

We prove that if $t \not=0$ and $E \subset {\Bbb F}_q^2$ , where ${\Bbb F}_q$ is the finite field with $q$ elements, then
$\nu(t)=\# \{(x,y) \in E \times E: {(x_1-y_1)}^2+{(x_2-y_2)}^2=t \}={(\# E)}^2 q^{-1}+R(t)$ , where $|R(t)| \leq 2 \cdot \# E \cdot \sqrt{q})$ .

From this it follows immediately that if $\# E>2q^{\frac{3}{2}}$ , then $\nu(t)>0$ . This implies that the chromatic number of the distance graph is $\ge \frac{\sqrt{q}}{2}$ . This can be also done in higher dimensions.

Reply
- rjlipton permalink*
  
  May 22, 2011 4:11 pm
  
  So this means that over complex plane the number is large?
  
  Reply
delta permalink

May 23, 2011 1:43 am

“Ick” on the story of Isbell’s class.

On the graphic of the seven-colored plane, I’m a bit mystified why there’s no clever pattern to how the 1-7’s are laid out? Like, if you exchanged the “4”‘s for the “6”‘s, then every “1” would be surrounded by 2-7 in order. But as is, the numbers are laid out in a weird irregular upward crawl. Am I missing some elegance to the layout?

Reply
Stefan permalink

May 23, 2011 3:54 am

I’m no logician, and the sentence “Then there is a proof in the theory of C that Delta(m,l) is false” in the proof of 3 => 1 worries me. Why is Gödel’s Incompleteness Theorem not relevant here?

Reply
- Phil permalink
  
  May 23, 2011 4:22 am
  
  The incompleteness theorem only applied to theories that are capable of interpreting arithmetic. There is no first order definition of the naturals numbers in C, and so this theorem does not apply. The sentence that worries you is not problematic, as the theory of algebraically closed fields of characteristic 0 (i.e. the theory of C) is complete (http://en.wikipedia.org/wiki/Complete_theory).
  
  Reply

	Amazing: Zhengfeng J… on Halting Is Poly-Time Quantum…
	Amazing: Zhengfeng J… on Halting Is Poly-Time Quantum…
	. on Halting Is Poly-Time Quantum…
	. on Halting Is Poly-Time Quantum…
	Shtetl-Optimized… on Halting Is Poly-Time Quantum…
	. on Halting Is Poly-Time Quantum…
	KWRegan on Halting Is Poly-Time Quantum…
	. on Halting Is Poly-Time Quantum…
	Halting Is Poly-Time… on Hobgoblins in Our Equatio…
	Halting Is Poly-Time… on Our Thoughts on P=NP
	Halting Is Poly-Time… on Surprises in Mathematics and…
	Cristóbal Camarero on A Math Gift For All
	KWRegan on Our Thoughts on P=NP
	KWRegan on Our Thoughts on P=NP
	Yu LI on Our Thoughts on P=NP

a personal view of the theory of computation

More On Coloring The Plane

Update

Trackbacks

Leave a Reply Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

More On Coloring The Plane

Update

Share this:

Like this:

Related

Trackbacks

Leave a Reply Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter