by Jonathan Kujawa
A few months ago I wrote about one of my favorite results in math: Ramsey's Theorem. It tells us that when we look at things at a large enough scale complete chaos is impossible. That is, if we look hard enough we inevitably find patterns. Call it the Conspiracy Theory Theorem.
Ramsey's theorem launched an entire field of mathematics which answers questions of the form “In such-and-such a setting, what kind of structure do we find if we look on a large enough scale?”. Or you might instead ask: “In such-and-such a setting, if I want to avoid a certain structure on large scales, what do I have to do?”. Of course, it's usually easier to ask the question than to find the answer [1].
A famous recent example is the Green-Tao Theorem. In 2004 Ben Green and Terence Tao proved that within the prime numbers you can find arbitrarily long arithmetic progressions. The prime numbers are the ones which can only be evenly divided by one and themselves (and so have to do with multiplication/division). They are rather randomly distributed amongst all the numbers, but the Green-Tao theorem says that if you look for the right kind of structure (sequences of numbers given by addition) and at a large enough scale, then you can't avoid finding it. It is a striking result which was among the reasons Dr. Tao earned the Fields medal in 2006 and has put Dr. Green in the running for a Fields medal this year [2].
When reading up on Ramsey's Theorem I discovered a delightful book edited by Alexander Soifer entitled “Ramsey Theory: Yesterday, Today, and Tomorrow“. It mixes the history and mathematics of Ramsey theory and covers everything from pre-Ramsey Ramsey theory up to the current state of the art.
From this book I learned of an irresistible 60+ year old question called the Hadwiger-Nelson problem. It's easy to state:
If you want to color the points of the Euclidean plane in such a way as to guarantee that there are never two points of the same color which are exactly one unit apart, how many colors do you need?
By the Euclidean plane we just mean the usual xy-plane you use in geometry when you draw circles, parabolas, etc. Since the plane goes off to infinity in every direction there are infinitely many points on the plane. A reasonable first guess is that you'll need infinitely many colors [3]. If it is possible to color the plane with finitely many colors, then surely it's something crazy like one of those Magic Eye posters which were all the rage in US shopping malls in the 80's:
With a little sideways thinking, it might occur to you to tile the plane with squares sized so that the distance from corner to corner is a little less than one unit. All of the points within that square are then less than one unit apart so can be colored a single color without causing us any trouble. We then can color the points on the plane by instead coloring each square a single color. This (in retrospect) easy observation quickly gives a striking breakthrough to what seemed previously to be an unsolvable problem.
For example here is a coloring of the squares using nine colors:
Here I've colored the plane using nine colors in a three by three grid with the pattern repeating over and over in all directions. Let's think about the points of the plane which are colored, say, red. Those within one square are all less than one unit apart. If you do the geometry, you'll find that those in two different red squares are always more than one unit apart. So there are never two red points exactly one unit apart. The same goes for each of the other eight colors.
So we don't need infinitely many colors! In fact, we can do a little bit better than nine. If we tile the squares so that each row is offset as you would when laying bricks, then you only need seven colors:
I'll leave it to you to figure out how to color this with seven colors. Now that we know we only need finitely many colors, how low can we go?
Obviously one color isn't enough since any line segment of length one would have two points of the same color at its ends. What about two colors? Well, if you draw an equilateral triangle in the plane where all three sides have length one, then you see that if you only use two colors you are forced to have two corners of the triangle which have the same color and are exactly one unit apart.
What about three colors? The Moser brothers introduced what is now called the Moser Spindle:
The Moser Spindle is a configuration of seven points in the plane so that each of the dashed lines is exactly one unit long. With some trial and error you will find that it is impossible to color these seven points with only three colors while avoiding having two of the same color on a dashed line. Alternatively, if you'd like a fun puzzle, a colleague of mine showed me a clever argument using multiple equilateral triangles and a circle which shows that any coloring with three colors fails the challenge.
From this we see we need at least four colors. So the number of colors we need is either 4, 5, 6, or 7.
What's the final answer? Nobody knows! We are at the frontier of human knowledge. If you press experts they may be willing to bet on which of these four numbers is the smallest number of colors you need; but nobody knows the final answer. My best guess based on gut instinct alone is that it is 5 or 6, but your guess is definitely as good as mine!
Like any good problem in math, it opens a Pandora's box of other questions: What if we tile the plane with other shapes? What if we wanted to color points in 3-dimensional space? What if we wanted to color the points on another shape — say the surface of the Earth? Whatever you ask, the answer is surely that nobody knows. Whatever you can say, it's quite likely to be new.
[1] A good working definition of a “good” question is one which is neither too easy nor too hard. It's boring to answer easy questions and infuriating when you can't make any progress at all.
[2] The Fields medal is awarded every four years to mathematicians under the age of 40. It is a closely held secret who will win this year, but of course that doesn't stop wild speculation. There is even a poll for those who'd like to weigh in!
[3] What happens if we replace “exactly one unit apart” with “closer than one unit apart”? If you think about a line segment which is one unit long, then you realize that there are infinitely many points along that line segment and so you'll need infinitely many colors. Similarly, if we replace “exactly one unit apart” with “farther than one unit apart”, then if you look at an infinitely long line you can again find infinitely many points which are all, say, two or more units apart. So again you'll need infinitely many colors. Somehow “exactly one unit apart” is the sweet spot where suddenly something very interesting happens. See [1].
[4] Thanks to stereogrammes.org for the image.
[5] Thanks to wikipedia for the image.