More On Coloring The Plane
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 ”
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 ” 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 apart have the same color? The value is known to be either
,
,
, or
; 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 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
Note that means that the “distance” between the pair
and
is
. 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
the value need not even be a real number.
Say a field is
-colorable provided for any set
of cardinality
, there is a coloring
of
with
colors so that for all
,
On the Axiom of Choice, Erdős proved with Nicolaas de Bruijn that every infinite graph is colorable with
colors provided every finite subgraph of
is colorable with
colors. This applies whether vertices in
are points
and
in the real plane
or the complex plane
, and whether the edge relation is Euclidean distance
or
. The advantage of the latter is that it can be written over the language of all fields. Whereas, the definition of Euclidean distance in
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 enables us to exploit a consequence of
being algebraically closed, whereas
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
over the language of fields:
- The sentence
is true over the complex field.
- The sentence
is true over all algebraically closed fields.
- The sentence
is true over some algebraically closed field.
- The sentence
is true over all finite fields
with sufficiently large characteristic
.
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 when
is the statement
, where
This expresses that the field is -colorable, and below we call it
. Note that
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
:
- The complex numbers are
-colorable for all natural numbers
.
- The complex plane is
-colorable with
as the edge relation.
- For each
, there is a
so that for all finite fields of characteristic
are
-colorable.
Proof: Let’s prove that . This follows from the Erdős-de Bruijn theorem applied to the infinite graph with vertex set
and edges connecting
and
if
.
Let’s next prove that . This is trivial, since by definition if the complex plane is
-colorable under
, then the complex field is
colorable for all
.
Let’s next prove that . The key insight is our having a first-order sentence
over the language of fields that encodes that the field is
-colorable. By
it follows that
is true by the Transfer theorem.
Let’s finally prove that . Assume that
is true, but
is not. Then there is a proof in the theory of
that
is false. But this proof transfers to all finite fields with large enough characteristic, which is a contradiction with
.
Thus by working over finite fields, we can address exactly the problem of coloring the complex plane under . 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
, if
is
-colorable for all
, then the real plane is
-colorable.
Proof: is a sub-field of
, so the hypothesis implies that
is
-colorable for all
. When the
function above is restricted to values in
,
is equivalent to the points
and
having Euclidean distance
in the plane. The conclusion thus follows from the Erdős-de Bruijn theorem applied to the graph in the real plane.
Thus if we can -color the
graphs of all finite fields (of sufficiently large characteristic, if that helps), then we can
-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 ; of course we are interested only in the values
through
. Working by contraposiiton and viewling the last proof, this is what we want to show: if there is some
for which
is not
-colorable, then there is some
for which
is not
-colorable. Let a witnessing
of size
be given, and look at the graph on
defined by
. Each edge of the graph involves complex numbers
such that
. Using the original Roman letters for real parts and Greek for imaginary parts, this means
Since the imaginary part must vanish, this gives . If this entailed that one (and a-fortiori both) of
and
had to vanish, the real parts would automatically become a finite subset of the Euclidean plane that is not
-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
of points in the plane that is not
-colorable. Note that
is a subset of
where
collects all co-ordinates of points in
, so we would in fact have
such that
is not
-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.”]
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
and
, where
is the finite field with
elements, then
, where
.
From this it follows immediately that if
, then
. This implies that the chromatic number of the distance graph is
. This can be also done in higher dimensions.
So this means that over complex plane the number is large?
“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?
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?
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).