Today’s post looks at the following problem. Color a plane (an infinite flat surface) so that any two points that are one unit apart are also different colors. The picture above is an example of such a coloring, with two caveats. The black borders are there to help you see what is going on (remove them to get the actual solution) and you have to continue the pattern indefinitely. The goal is to use as few colors as possible. This smallest number of colors that meet the goal is called the chromatic number of the plane. The formal name of this problem is the Hadwiger-Nelson problem. This problem is famous, in part, because much of the progress on it has been made by amateur mathematicians. The professors ended up needing a lot of help on this one. We also still don’t know the final answer to this problem. Occupy Math will go over what we do know.
The first step is to establish that it is possible to color the plane at all so that points one unit apart must be different colors. The coloring at the top of the post works to show that seven colors are enough. First look at the basic pattern that is repeated to generate the coloring at the top of the post:
The individual hexagons need to be sized so that opposite vertices are just under one unit apart. That means that no two points a distance of one from one another are in the same hexagon. That leaves the problem of two points one unit apart being the same color but being in different hexagons. The hexagons of any one color are all in the same relative position with respect to one another, so we can look at just one color:
Remember that we sized the hexagons so that the longest distance inside the hexagon is just less than one? The distances between hexagons are clearly substantially more than the distance across a hexagon — so hexagons that are the same color are a good deal more than one apart even at their point of closest approach. Occupy Math concludes that the coloring at the top of the post does show that the minimum number of colors we need to solve the problem are no more than seven. This is the smallest number we know will work. Unfortunately we can’t prove we actually need all 7 colors.
What’s the smallest number of colors we know are needed?
A rather deep and confusing theorem, the compactness theorem of mathematical logic, implies that if you can prove something, you can prove it in a finite number of steps. This has a consequence in the search for the chromatic number of the plane: if some number of colors are absolutely required to color the plane, then we can find a finite set of points that require that number of colors. These finite diagrams that demonstrate that some number of colors are required are called gadgets.
Occupy Math’s editor objected to this terminology — because the diagrams later in the post don’t look much like “gadgets”; they’re not mechanical. All a gadget is is a set of points, connected by lines of length one. This means that every gadget actually appears in the plane. Here’s the reason they’re useful — if a gadget cannot be colored so that the points at either end of each line are different colors, using k colors, then the whole plane also needs more than k colors. A gadget that uses k colors is called a k-gadget. Let’s look at an example. The vertices of an equilateral triangle with side length one form a 3-gadget. Since each point is at the end of a line from each other point, they must all be different colors.
Since we are using an equilateral triangle, all three points (which we inflated to make them easy to see) are at distance one from one another. This means they all have to be different colors; this is a 3-gadget. Since there is a 3-gadget, at least three colors are needed to color the plane. This follows from the fact the points in the gadget can be thought of as being points in the plane.
Let’s find a 4-gadget!
Start with two equilateral triangles that share a side. Make a second copy of the triangles and keep the top points of the objects on top of one another. Rotate the second copy until the bottom points are one unit apart. Stop there! Since that is potentially very confusing, here is a looped animation of the construction; the final gadget is shown to the right.
Occupy Math claims this collection of points is a 4-gadget. We have already seen that a triangle needs three colors. Consult with the picture below as we make the following argument. Suppose we try to color the points of the thing we just constructed with only three colors. If the top point is orange then the two points in the middle of each double triangle need to be blue and purple. This means that the last point in each group of four cannot be blue or purple — which leaves orange. Our careful rotation put these two tentatively orange points at a distance of one from one another. This means that one of them cannot be orange either, so a fourth color, pink, is required. Try coloring this yourself: there are lots of ways to color it with four colors and none to color it with three.
The fact we have a 4-gadget means coloring the plane needs at least 4 colors!
That’s all we know. The plane can be colored with seven colors and any coloring must use at least four colors. The actual minimum number of colors is still a mystery. Weird, huh?
The shortest path to progress would be to find a 5-gadget. The problem is that current work suggests that a 5-gadget probably has hundreds of points in it. A computer search is hard because “the points are at distance one from one another” is not something you can do by crunching numbers. Round-off errors will kill you! A computer working to construct a 5-gadget would need an AI of some sort using logic — like the arguments that Occupy Math has used in this post. Only they would be bigger. Much, much bigger.
Occupy Math hopes you have found this trip into unsolved math problems instructional and interesting. If you are a teacher, or interested in playing with math, you can always look for more 4-gadgets. Occupy Math has constructed several 4-gadgets during faculty meetings that failed to engage his full attention. One of the biggest math results in this post is the thing based on the compactness theorem. The idea “a statement that has a proof has a finite proof” is a bit startling — and pretty convenient.
This post treats the reader to a number of instructive pictures. Occupy Math thinks it worth mentioning that about twenty sheets of paper covered with drawings of triangles, hexagonal tilings, and calculations were needed before the computer code that was used to make the pictures worked properly. This post rests on a foundation of piles and piles of basic geometry and trig. To make progress on hard, interesting math, you kind of need to know basic math. Here ends the micro-sermon.
Alert readers will have noticed that gadgets are, in fact, graphs which have come up in Occupy Math before. The problem of coloring the plane sounds a little like the four-color (map coloring) problem, but it is actually quite different. Want to see more graph theory? Have another topic you are interested in? Let Occupy Math know by commenting or tweeting!
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics