Two commenters suggested the topic for today’s A to Z post. I suspect I’d have been interested in it if only one had. (Although Dina Yagoditch’s suggestion of the Menger Sponge is hard to resist.) But a double domination? The topic got suggested by Mr Wu, author of MathTuition88, and by John Golden, author of Math Hombre. My thanks to all for interesting things to think about.
So you know how in the first car you ever owned the alternator was always going bad? If you’re lucky, you reach a point where you start owning cars good enough that the alternator is not the thing always going bad. Once you’re there, congratulations. Now the thing that’s always going bad in your car will be the manifold. That one’s for my dad.
Manifolds are a way to do normal geometry on weird shapes. What’s normal geometry? It’s … you know, the way shapes work on your table, or in a room. The Euclidean geometry that we’re so used to that it’s hard to imagine it not working. Why worry about weird shapes? They’re interesting, for one. And they don’t have to be that weird to count as weird. A sphere, like the surface of the Earth, can be weird. And these weird shapes can be useful. Mathematical physics, for example, can represent the evolution of some complicated thing as a path drawn on a weird shape. Bringing what we know about geometry from years of study, and moving around rooms, to a problem that abstract makes our lives easier.
We use language that sounds like that of map-makers when discussing manifolds. We have maps. We gather together charts. The collection of charts describing a surface can be an atlas. All these words have common meanings. Mercifully, these common meanings don’t lead us too far from the mathematical meanings. We can even use the problem of mapping the surface of the Earth to understand manifolds.
If you love maps, the geography kind, you learn quickly that there’s no making a perfect two-dimensional map of the Earth’s surface. Some of these imperfections are obvious. You can distort shapes trying to make a flat map of the globe. You can distort sizes. But you can’t represent every point on the globe with a point on the paper. Not without doing something that really breaks continuity. Like, say, turning the North Pole into the whole line at the top of the map. Like in the Equirectangular projection. Or skipping some of the points, like in the Mercator projection. Or adding some cuts into a surface that doesn’t have them, like in the Goode homolosine projection. You may recognize this as the one used in classrooms back when the world had first begun.
But what if we don’t need the whole globedone in a single map? Turns out we can do that easy. We can make charts that cover a part of the surface. No one chart has to cover the whole of the Earth’s surface. It only has to cover some part of it. It covers the globe with a piece that looks like a common ordinary Euclidean space, where ordinary geometry holds. It’s the collection of charts that covers the whole surface. This collection of charts is an atlas. You have a manifold if it’s possible to make a coherent atlas. For this every point on the manifold has to be on at least one chart. It’s okay if a point is on several charts. It’s okay if some point is on all the charts. Like, suppose your original surface is a circle. You can represent this with an atlas of two charts. Each chart maps the circle, except for one point, onto a line segment. The two charts don’t both skip the same point. All but two points on this circle are on all the maps of this chart. That’s cool. What’s not okay is if some point can’t be coherently put onto some chart.
This sad fate can happen. Suppose instead of a circle you want to chart a figure-eight loop. That won’t work. The point where the figure crosses itself doesn’t look, locally, like a Euclidean space. It looks like an ‘x’. There’s no getting around that. There’s no atlas that can cover the whole of that surface. So that surface isn’t a manifold.
But many things are manifolds nevertheless. Toruses, the doughnut shapes, are. Möbius strips and Klein bottles are. Ellipsoids and hyperbolic surfaces are, or at least can be. Mathematical physics finds surfaces that describe all the ways the planets could move and still conserve the energy and momentum and angular momentum of the solar system. That cheesecloth surface stretched through 54 dimensions, is a manifold. There are many possible atlases, with many more charts. But each of those means we can, at least locally, for particular problems, understand them the same way we understand cutouts of triangles and pentagons and circles on construction paper.
So to get back to cars: no one has ever said “my car runs okay, but I regret how I replaced the brake covers the moment I suspected they were wearing out”. Every car problem is easier when it’s done as soon as your budget and schedule allow.
I have been reading Mapping In Michigan and the Great Lakes Region, edited by David I Macleod, because — look, I understand that I have a problem. I just live with it. The book is about exactly what you might imagine from the title. And it features lots of those charming old maps where, you know, there wasn’t so very much hard data available and everyone did the best with what they had. So you get these maps with spot-on perfect Lake Eries and the eastern shore of Lake Huron looking like you pulled it off of Open Street Maps. And then Michigan looks like a kid’s drawing of a Thanksgiving turkey. Also sometimes they drop a mountain range in the middle of the state because I guess it seemed a little empty without.
The first chapter, by Mary Sponberg Pedley, is a biography and work-history of Louis Charles Karpinski, 1878-1956. Karpinski did a lot to bring scholastic attention to maps of the Great Lakes area. He was a professor of mathematics for the University of Michigan. And he commented a good bit about the problems of teaching mathematics. Pedley quoted this bit that I thought was too good not to share. It’s from Arithmetic For The Farm. It’s about the failure of textbooks to provide examples that actually reflected anything anyone might want to know. I quote here Pedley’s endnote:
Karpinski disparaged the typical “story problems” found in contemporary textbooks, such as the following: “How many sacks, holding 2 bushels, 3 pecks and 2 quarts each can be filled from a bin containing 366 bushels, 3 pecks, 4 quarts of what?” Karpinski comments: “How carefully would you have to fill a sack to make it hold 3 pecks 2 quarts of anything? And who filled the bin so marvelously that the capacity is known with an accuracy of one-25th of 1% of the total?” He recommended an easier, more practical means of doing such problems, noting that a bushel is about 1 & 1/4 or 5/4 cubic feet. Therefore the number of bushels in the bin is the length times width times 4/5; the easiest way to get 4/5 of anything is to take away one-fifth of it.
This does read to me like Pedley jumped a track somewhere. It seems to go from the demolition of the plausibility of one problem’s setup to demolishing the plausibility of how to answer a problem. Still, the core complaint is with us yet. It’s hard to frame problems that might actually come up in ways that clearly test specific mathematical skills.
And on another note. This is the 1,000th mathematical piece that I’ve published since I started in September of 2011. If I’m not misunderstanding this authorship statistic on WordPress, which is never a safe bet. I’m surprised that it has taken as long as this to get to a thousand posts. Also I’m surprised that I should be surprised. I know roughly how many days there are in a year. And I know I need special circumstances to post something more often than every other day. Still, I’m glad to reach this milestone, and gratified that there’s anyone interested in what I have to say. In my next thousand posts I hope to say something.
Gaurish, of the For The Love Of Mathematics blog, takes me back into topology today. And it’s a challenging one, because what can I say about a shape this involved when I’m too lazy to draw pictures or include photographs most of the time?
In 1958 Clifton Fadiman, an open public intellectual and panelist on many fine old-time radio and early TV quiz shows, edited the book Fantasia Mathematica. It’s a pleasant read and you likely can find a copy in a library or university library nearby. It’s a collection of mathematically-themed stuff. Mostly short stories, a few poems, some essays, even that bit where Socrates works through a proof. And some of it is science fiction, this from an era when science fiction was really disreputable.
If there’s a theme to the science fiction stories included it is: Möbius Strips, huh? There are so many stories in the book that amount to, “what is this crazy bizarre freaky weird ribbon-like structure that only has the one side? Huh?” As I remember even one of the non-science-fiction stories is a Möbius Strip story.
I don’t want to sound hard on the writers, nor on Fadiman for collecting what he has. A story has to be about people doing something, even if it’s merely exploring some weird phenomenon. You can imagine people dealing with weird shapes. It’s hard to imagine what story you could tell about an odd perfect number. (Well, that isn’t “here’s how we discovered the odd perfect number”, which amounts to a lot of thinking and false starts. Or that doesn’t make the odd perfect number a MacGuffin, the role equally well served by letters of transit or a heap of gold or whatever.) Many of the stories that aren’t about the Möbius Strip are about four- and higher-dimensional shapes that people get caught in or pass through. One of the hyperdimensional stories, A J Deutsch’s “A Subway Named Möbius”, even pulls in the Möbius Strip. The name doesn’t fit, but it is catchy, and is one of the two best tall tales about the Boston subway system.
Besides, it’s easy to see why the Möbius Strip is interesting. It’s a ribbon where both sides are the same side. What’s not neat about that? It forces us to realize that while we know what “sides” are, there’s stuff about them that isn’t obvious. That defies intuition. It’s so easy to make that it holds another mystery. How is this not a figure known to the ancients and used as a symbol of paradox for millennia? I have no idea; it’s hard to guess why something was not noticed when it could easily have been It dates to 1858, when August Ferdinand Möbius and Johann Bendict Listing independently published on it.
The Klein Bottle is newer by a generation. Felix Klein, who used group theory to enlighten geometry and vice-versa, described the surface in 1882. It has much in common with the Möbius Strip. It’s a thing that looks like a solid. But it’s impossible to declare one side to be outside and the other in, at least not in any logically coherent way. Take one and dab a spot with a magic marker. You could trace, with the marker, a continuous curve that gets around to the same spot on the “other” “side” of the thing. You see why I have to put quotes around “other” and “side”. I believe you know what I mean when I say this. But taken literally, it’s nonsense.
The Klein Bottle’s a two-dimensional surface. By that I mean that could cover it with what look like lines of longitude and latitude. Those coordinates would tell you, without confusion, where a point on the surface is. But it’s embedded in a four-dimensional space. (Or a higher-dimensional space, but everything past the fourth dimension is extravagance.) We have never seen a Klein Bottle in its whole. I suppose there are skilled people who can imagine it faithfully, but how would anyone else ever know?
Big deal. We’ve never seen a tesseract either, but we know the shadow it casts in three-dimensional space. So it is with the Klein Bottle. Visit any university mathematics department. If they haven’t got a glass replica of one in the dusty cabinets welcoming guests to the department, never fear. At least one of the professors has one on an office shelf, probably beside some exams from eight years ago. They make nice-looking jars. Klein Bottles don’t have to. There are different shapes their projection into three dimensions can take. But the only really different one is this sort of figure-eight helical shape that looks like a roller coaster gone vicious. (There’s also a mirror image of this, the helix winding the opposite way.) These representations have the surface cross through itself. In four dimensions, it does no such thing, any more than the edges of a cube cross one another. It’s just the lines in a picture on a piece of paper that cross.
The Möbius Strip is good practice for learning about the Klein Bottle. We can imagine creating a Bottle by the correct stitching-together of two strips. Or, if you feel destructive, we can start with a Bottle and slice it, producing a pair of Möbius Strips. Both are non-orientable. We can’t make a division between one side and another that reflects any particular feature of the shape. One of the helix-like representations of the Klein Bottle also looks like a pool toy-ring version of the Möbius Strip.
And strange things happen on these surfaces. You might remember the four-color map theorem. Four colors are enough to color any two-dimensional map without adjacent territories having to share a color. (This isn’t actually so, as the territories have to be contiguous, with no enclaves of one territory inside another. Never mind.) This is so for territories on the sphere. It’s hard to prove (although the five-color theorem is easy.) Not so for the Möbius Strip: territories on it might need as many as six colors. And likewise for the Klein Bottle. That’s a particularly neat result, as the Heawood Conjecture tells us the Klein Bottle might need seven. The Heawood Conjecture is otherwise dead-on in telling us how many colors different kinds of surfaces need for their map-colorings. The Klein Bottle is a strange surface. And yes, it was easier to prove the six-color theorem on the Klein Bottle than it was to prove the four-color theorem on the plane or sphere.
(Though it’s got the tentative-sounding name of conjecture, the Heawood Conjecture is proven. Heawood put it out as a conjecture in 1890. It took to 1968 for the whole thing to be finally proved. I imagine all those decades of being thought but not proven true gave it a reputation. It’s not wrong for Klein Bottles. If six colors are enough for these maps, then so are seven colors. It’s just that Klein Bottles are the lone case where the bound is tighter than Heawood suggests.)
All that said, do we care? Do Klein Bottles represent something of particular mathematical interest? Or are they imagination-capturing things we don’t really use? I confess I’m not enough of a topologist to say how useful they are. They are easily-understood examples of algebraic or geometric constructs. These are things with names like “quotient spaces” and “deck transformations” and “fiber bundles”. The thought of the essay I would need to write to say what a fiber bundle is makes me appreciate having good examples of the thing around. So if nothing else they are educationally useful.
And perhaps they turn up more than I realize. The geometry of Möbius Strips turns up in many surprising places: music theory and organic chemistry, superconductivity and roller coasters. It would seem out of place if the kinds of connections which make a Klein Bottle don’t turn up in our twisty world.
This is, in part, a post for myself. They all are, but this is moreso. My day job includes some Geographic Information Services stuff, which is how we say “maps” when we want to be taken seriously as Information Technology professionals. When we make maps, what we really do is have a computer draw polygons, and then put dots on them. A common need is to put a dot in the middle of a polygon. Yes, this sounds silly, but describe your job this abstractly and see how it comes out.
The trouble is polygons can be complicated stuff. Can be, not are. If the polygon is, like, the border of your building’s property it’s probably not too crazy. It’s probably a rectangle, or at least a trapezoid. Maybe there’s a curved boundary. If you need a dot, such as to place the street address or a description of the property, you can make a good guess about where to put it so it’s inside the property and not too close to an edge.
But you can’t always. The polygons can be complicated. Especially if you’re representing stuff that reflects government or scientific or commercial interest. There’s good reasons to be interested in the boundaries between the low-low tide and the high-high tide lines of a beach, but that’s not going to look like anything simple for any realistic property. Finding a representative spot to fix labels or other business gets tricky.
The approach is, broadly, of a kind with many numerical methods. It tries to find an answer by taking a guess and then seeing if any obvious variations will make it a little better. If you can, then, repeat these variations. Eventually, usually, you’ll get to a pretty good answer. It may not be the exact best possible answer, but that’s all right. We accept that we’ll have a merely approximate answer, but we’ll get it more quickly than we otherwise would have. Often this is fine. Nobody will be upset that the label on a map would be “better” moved one pixel to the right if they get the map ten seconds faster. Optimization is often like that.
I have not tried putting this code into mine yet; I’ve just now read it and I have some higher-priority tasks at work. But I’m hoping to remember that this exists and to see whether I can use it.
Can’t deny that I will sometimes stockpile links of mathematics stuff to talk about. Sometimes I even remember to post it. Sometimes it’s a tweet like this, which apparently I’ve been carrying around since April:
Shepherds in the Lake District once had their own number system for counting sheep…
I admit I do not know whether the claim is true. It’s plausible enough. English has many variants in England alone, and any trade will pick up its own specialized jargon. The words are fun as it is.
From the American Mathematical Society there’s this:
Physicists Surprised To Discover Knots That Can Escape Complex Tangles https://t.co/GtjxndTzTf
I talk a good bit about knot theory. It captures the imagination and it’s good for people who like to doodle. And it has a lot of real-world applications. Tangled wires, protein strands, high-energy plasmas, they all have knots in them. Some work by Paul Sutcliffe and Fabian Maucher, both of Durham University, studies tangled vortices. These are vortices that are, er, tangled together, just like you imagine. Knot theory tells us much about this kind of vortex. And it turns out these tangled vortices can untangle themselves and smooth out again, even without something to break them up and rebuild them. It gives hope for power cords everywhere.
Nerds have a streak which compels them to make blueprints of things. It can be part of the healthier side of nerd culture, the one that celebrates everything. The side that tries to fill in the real-world things that the thing-celebrated would have if it existed. So here’s a bit of news about doing that:
Interpreting clues from 500-year-old book "Utopia" required math developed long after initial publication https://t.co/HjyD4GYwFx
I like the attempt to map Sir Thomas More’s Utopia. It’s a fun exercise in matching stuff to a thin set of data. But as mentioned in the article, nobody should take it too seriously. The exact arrangement of things in Utopia isn’t the point of the book. More probably didn’t have a map for it himself.
(Although maybe. I believe I got this from Simon Garfield’s On The Map: A Mind-Expanding Exploration Of The Way The World Looks and apologize generally if I’ve got it wrong. My understanding is Robert Louis Stevenson drew a map of Treasure Island and used it to make sure references in the book were consistent. Then the map was lost in the mail to his publishers. He had to read his text and re-create it as best he could. Which, if true, makes the map all the better. It makes it so good a lost-map story that I start instinctively to doubt it; it’s so colorfully perfect, after all.)
And finally there’s this gem from the Magic Realism Bot:
A queen discovers that the number zero does not exist, and goes mad.
— Magic Realism Bot (@MagicRealismBot) July 12, 2016
So my attempt at keeping the Reading the Comics posts to Sunday has crashed and burned again. This time for a good reason. As you might have read between the lines on my humor blog, I spent the past week on holiday and just didn’t have time to write stuff. I barely had time to read my comics. I’ll get around to it this week.
In the meanwhile then I’d like to point people to the MathsByAGirl blog. The blog recently had an essay on Nicolas Bourbaki, who’s among the most famous mathematicians of the 20th century. Bourbaki is also someone with a tremendous and controversial legacy, one that I expect to touch on as I catch up on last week’s comics. If you don’t know the secret of Bourbaki then do go over and learn it. If you do, well, go over and read anyway. The author’s wondering whether to write more about Bourbaki’s mathematics and while I’m all in favor of that more people should say.
And as I promised a trifle, let me point to something from my own humor blog. How To Write Out Numbers is an older trifle based on everyone’s love for copy-editing standards. I had forgotten I wrote it before digging it up for a week of self-glorifying posts last week. I hope folks around here like it too.
People think mathematics is mostly counting and arithmetic. It’s what we get at when we say “do the math[s]”. It’s why the mathematician in the group is the one called on to work out what the tip should be. Heck, I attribute part of my love for mathematics to a Berenstain Bears book which implied being a mathematician was mostly about adding up sums in a base on the Moon, which is an irresistible prospect. In fact, usually counting and arithmetic are, at least, minor influences on real mathematics. There are legends of how catastrophically bad at figuring mathematical genius can be. But usually isn’t always, and this week I’d like to show off a case where counting things and adding things up lets us prove something interesting.
The Five-Color Map Theorem.
No, not four. I imagine anyone interested enough to read a mathematics blog knows the four-color map theorem. It says that you only need four colors to color a map. That’s true, given some qualifiers. No discontiguous chunks that need the same color. Two regions with the same color can touch at a point, they just can’t share a line or curve. The map is on a plane or the surface of a sphere. Probably some other requirements. I’m not going to prove that. Nobody has time for that. The best proofs we’ve figured out for it amount to working out how every map fits into one of a huge number of cases, and trying out each case. It’s possible to color each of those cases with only four colors, so, we’re done. Nice but unenlightening and way too long to deal with.
The five-color map theorem is a lot like the four-color map theorem, with this difference: it says that you only need five colors to color a map. Same qualifiers as before. Yes, it’s true because the four-color map theorem is true and because five is more than four. We can do better than that. We can prove five colors are enough even without knowing whether four colors will do. And it’s easy. The ease of the five-color map theorem gave people reason to think four colors would be maybe harder but still manageable.
The proof I want to show uses one of mathematicians’ common tricks. It employs the same principle which Hercules used to slay the Hydra, although it has less cauterizing lake-monster flesh with flaming torches, as that’s considered beneath the dignity of the Academy anymore except when grading finals for general-requirements classes. The part of the idea we do use is to take a problem which we might not be able to do and cut it down to one we can do. Properly speaking this is a kind of induction proof. In those we start from problems we can do and show that if we can do those, we can do all the complicated problems. But we come at it by cutting down complicated problems and making them simple ones.
Please enjoy my little map of the place. It gives all the states a single color because I don’t really know how to use QGIS and it would probably make my day job easier if I did. (Well, QGIS is open-source software, so its interface is a disaster and its tutorials gibberish. The only way to do something with it is to take flaming torches to it.)
States which, in their 17th-century English colonial form, were part of the Dominion of New England (1685-1689). More or less. If I’ve messed up don’t tell me as it doesn’t really matter for this problem.
There’s eight regions here, eight states, so it’s not like we’re at the point we can’t figure how to color this with five different colors. That’s all right. I’m using this for a demonstration. Pretend the Dominion of New England is so complicated we can’t tell whether five colors are enough. Oh, and a spot of lingo: if five colors are enough to color the map we say the map is “colorable”. We say it’s “5-colorable” if we want to emphasize five is enough colors.
So imagine that we erase the border between Maine and New Hampshire. Combine them into a single state over the loud protests of the many proud, scary Mainers. But if this simplified New England is colorable, so is the real thing. There’s at least one color not used for Greater New Hampshire, Vermont, or Massachusetts. We give that color to a restored Maine. If the simplified map can be 5-colored, so can the original.
Maybe we can’t tell. Suppose the simplified map is still too complicated to make it obvious. OK, then. Cut out another border. How about we offend Roger Williams partisans and merge Rhode Island into Massachusetts? Massachusetts started out touching five other states, which makes it a good candidate for a state that needed a sixth color. With Rhode Island reduced to being a couple counties of the Bay State, Greater Massachusetts only touches four other states. It can’t need a sixth color. There’s at least one of our original five that’s free.
OK, but, how does that help us find a color for Rhode Island? Maine it’s easy to see why there’s a free color. But Rhode Island?
Well, it’ll have to be the same color as either Greater New Hampshire or Vermont or New York. At least one of them has to be available. Rhode Island doesn’t touch them. Connecticut’s color is out because Rhode Island shares a border with it. Same with Greater Massachusetts’s color. But we’ve got three colors for the taking.
But is our reduced map 5-colorable? Even with Maine part of New Hampshire and Rhode Island part of Massachusetts it might still be too hard to tell. There’s six territories in it, after all. We can simplify things a little. Let’s reverse the treason of 1777 and put Vermont back into New York, dismissing New Hampshire’s claim on the territory as obvious absurdity. I am never going to be allowed back into New England. This Greater New York needs one color for itself, yes. And it touches four other states. But these neighboring states don’t touch each other. A restored Vermont could use the same color as New Jersey or Connecticut. Greater Massachusetts and Greater New Hampshire are unavailable, but there’s still two choices left.
And now look at the map we have remaining. There’s five states in it: Greater New Hampshire, Greater Massachusetts, Greater New York, Regular Old Connecticut, and Regular old New Jersey. We have five colors. Obviously we can give the five territories different colors.
This is one case, one example map. That’s all we need. A proper proof makes things more abstract, but uses the same pattern. Any map of a bunch of territories is going to have at least one territory that’s got at most five neighbors. Maybe it will have several. Look for one of them. If you find a territory with just one neighbor, such as Maine had, remove that border. You’ve got a simpler map and there must be a color free for the restored territory.
If you find a territory with just two neighbors, such as Rhode Island, take your pick. Merge it with either neighbor. You’ll still have at least one color free for the restored territory. With three neighbors, such as Vermont or Connecticut, again you have your choice. Merge it with any of the three neighbors. You’ll have a simpler map and there’ll be at least one free color.
If you have four neighbors, the way New York has, again pick a border you like and eliminate that. There is a catch. You can imagine one of the neighboring territories reaching out and wrapping around to touch the original state on more than one side. Imagine if Massachusetts ran far out to sea, looped back through Canada, and came back to touch New Jersey, Vermont from the north, and New York from the west. That’s more of a Connecticut stunt to pull, I admit. But that’s still all right. Most of the colonies tried this sort of stunt. And even if Massachusetts did that, we would have colors available. It would be impossible for Vermont and New Jersey to touch. We’ve got a theorem that proves it.
Yes, it’s the Jordan Curve Theorem, here to save us right when we might get stuck. Just like I promised last week. In this case some part of the border of New York and Really Big Massachusetts serves as our curve. Either Vermont or New Jersey is going to be inside that curve, and the other state is outside. They can’t touch. Thank you.
If you have five neighbors, the way Massachusetts has, well, maybe you’re lucky. We are here. None of its neighboring states touches more than two others. We can cut out a border easily and have colors to spare. But we could be in trouble. We could have a map in which all the bordering states touch three or four neighbors and that seems like it would run out of colors. Let me show a picture of that.
A hypothetical map with five regions named by an uninspired committee.
So this map looks dire even when you ignore that line that looks like it isn’t connected where C and D come together. Flood fill didn’t run past it, so it must be connected. It just doesn’t look right. Everybody has four neighbors except the province of B, which has three. The province of A has got five. What can we do?
Call on the Jordan Curve Theorem again. At least one of the provinces has to be landlocked, relative to the others. In this case, the borders of provinces A, D, and C come together to make a curve that keeps B in the inside and E on the outside. So we’re free to give B and E the same color. We treat this in the proof by doing a double merger. Erase the boundary between provinces A and B, and also that between provinces A and E. (Or you might merge B, A, and F together. It doesn’t matter. The Jordan Curve Theorem promises us there’ll be at least one choice and that’s all we need.)
So there we have it. As long as we have a map that has some provinces with up to five neighbors, we can reduce the map. And reduce it again, if need be, and again and again. Eventually we’ll get to a map with only five provinces and that has to be 5-colorable.
Just … now … one little nagging thing. We’re relying on there always being some province with at most five neighbors. Why can’t there be some horrible map where every province has six or more neighbors?
Counting will tell us. Arithmetic will finish the job. But we have to get there by way of polygons.
That is, the easiest way to prove this depends on a map with boundaries that are all polygons. That’s all right. Polygons are almost the polynomials of geometry. You can make a polygon that looks so much like the original shape the eye can’t tell the difference. Look at my Dominion of New England map. That’s computer-rendered, so it’s all polygons, and yet all those shore and river boundaries look natural.
But what makes up a polygon? Well, it’s a bunch of straight lines. We call those ‘edges’. Each edge starts and ends at a corner. We call those ‘vertices’. These edges come around and close together to make a ‘face’, a territory like we’ve been talking about. We’re going to count all the regions that have a certain number of neighboring other regions.
Specifically, F2 will represent however many faces there are that have two sides. F3 will represent however many faces there are that have three sides. F4 will represent however many faces there are that have four sides. F10 … yeah, you got this.
One thing you didn’t get. The outside counts as a face. We need this to make the count come out right, so we can use some solid-geometry results. In my map that’s the vast white space that represents the Atlantic Ocean, the other United States, the other parts of Canada, the Great Lakes, all the rest of the world. So Maine, for example, belongs to F2 because it touches New Hampshire and the great unknown void of the rest of the universe. Rhode Island belongs to F3 similarly. New Hampshire’s in F4.
Any map has to have at least one thing that’s in F2, F3, F4, or F5. They touch at most two, three, four or five neighbors. (If they touched more, they’d represent a face that was a polygon of even more sides.)
How do we know? It comes from Euler’s Formula, which starts out describing the ways corners and edges and faces of a polyhedron fit together. Our map, with its polygon on the surface of the sphere, turns out to be just as good as a polyhedron. It looks a little less blocky, but that doesn’t show.
By Euler’s Formula, there’s this neat relationship between the number of vertices, the number of edges, and the number of faces in a polyhedron. (This is the same Leonhard Euler famous for … well, everything in mathematics, really. But in this case it’s for his work with shapes.) It holds for our map too. Call the number of vertices V. Call the number of edges E. Call the number of faces F. Then:
Always true. Try drawing some maps yourself, using simple straight lines, and see if it works. For that matter, look at my Really Really Simplified map and see if it doesn’t hold true still.
A very simplified blocky diagram of my Dominion of New England, with the vertices and edges highlighted so they’re easy to count if you want to do that.
Here’s one of those insights that’s so obvious it’s hard to believe. Every edge ends in two vertices. Three edges meet at every vertex. (We don’t have more than three territories come together at a point. If that were to happen, we’d change the map a little to find our coloring and then put it back afterwards. Pick one of the territories and give it a disc of area from the four or five or more corners. The troublesome corner is gone. Once we’ve done with our proof, shrink the disc back down to nothing. Coloring done!) And therefore .
A polygon has the same number of edges as vertices, and if you don’t believe that then draw some and count. Every edge touches exactly two regions. Every vertex touches exactly three edges. So we can rework Euler’s formula. Multiply it by six and we get . And from doubling the equation about edges and vertices equation in the last paragraph, . So if we break up that 6E into 4E and 2E we can rewrite that Euler’s formula again. It becomes . 6V – 4E is zero, so, .
Do we know anything about F itself?
Well, yeah. . The number of faces has to equal the sum of the number of faces of two edges, and of three edges, and of four edges, and of five edges, and of six edges, and on and on. Counting!
Do we know anything about how E and F relate?
Well, yeah. A polygon in F2 has two edges. A polygon in F3 has three edges. A polygon in F4 has four edges. And each edge runs up against two faces. So therefore . This goes on forever but that’s all right. We don’t need all these terms.
Because here’s what we do have. We know that . And we know how to write both E and F in terms of F2, F3, F4, and so on. We’re going to show at least one of these low-subscript Fsomethings has to be positive, that is, there has to be at least one of them.
Start by just shoving our long sum expressions into the modified Euler’s Formula we had. That gives us this:
Doesn’t look like we’ve got anywhere, does it? That’s all right. Multiply that -1 and that 6 into their parentheses. And then move the terms around, so that we group all the terms with F2 together, and all the terms with F3 together, and all the terms with F4 together, and so on. This gets us to:
I know, that’s a lot of parentheses. And it adds negative numbers to positive which I guess we’re allowed to do but who wants to do that? Simplify things a little more:
And now look at that. Each Fsubscript has to be zero or a positive number. You can’t have a negative number of shapes. If you can I don’t want to hear about it. Most of those Fsubscript‘s get multiplied by a negative number before they’re added up. But the sum has to be a positive number.
There’s only one way that this sum can be a positive number. At least one of F2, F3, F4, or F5 has to be a positive number. So there must be at least one region with at most five neighbors. And that’s true without knowing anything about our map. So it’s true about the original map, and it’s true about a simplified map, and about a simplified-more map, and on and on.
And that is why this hydra-style attack method always works. We can always simplify a map until it obviously can be colored with five colors. And we can go from that simplified map back to the original map, and color it in just fine. Formally, this is an existence proof: it shows there must be a way to color a map with five colors. But it does so the devious way, by showing a way to color the map. We don’t get enough existence proofs like that. And, at its critical point, we know the proof is true because we can count the number of regions and the number of edges and the number of corners they have. And we can add and subtract those numbers in the right way. Just like people imagine mathematicians do all day.
Properly this works only on the surface of a sphere. Euler’s Formula, which we use for the proof, depends on that. We get away with it on a piece of paper because we can pretend this is just a part of the globe so small we don’t see how flat it is. The vast white edge we suppose wraps around the whole world. And that’s fine since we mostly care about maps on flat surfaces or on globes. If we had a map that needed three dimensions, like one that looked at mining and water and overflight and land-use rights, things wouldn’t be so easy. Nor would they work at all if the map turned out to be on an exotic shape like a torus, a doughnut shape.
But this does have a staggering thought. Suppose we drew boundary lines. And suppose we found an arrangement of them so that we needed more than five colors. This would tell us that we have to be living on a surface such as a torus, the doughnut shape. We could learn something about the way space is curved by way of an experiment that never looks at more than where two regions come together. That we can find information about the whole of space, global information, by looking only at local stuff amazes me. I hope it at least surprises you.
From fiddling with this you probably figure the four-color map theorem should follow right away. Maybe involve a little more arithmetic but nothing too crazy. I agree, it so should. It doesn’t. Sorry.
By way of the UK Ed Chat web site I’ve found something that’s maybe useful in mathematical education and yet just irresistible to my sort of mind. It’s the Metro Map Creator, a tool for creating maps in the style and format of those topographical, circuit-diagram-style maps made famous by the London Underground and many subway or rail systems with complex networks to describe.
UK Ed Chat is of the opinion it can be used to organize concepts by how they lead to one another and how they connect to other concepts. I can’t dispute that, but what tickles me is that it’s just so beautiful to create maps like this. There’s a reason I need to ration the time I spend playing Sid Meier’s Railroads.
It also brings to mind that in the early 90s I attended a talk by someone who was in the business of programming automated mapmaking software. If you accept that it’s simple to draw a map, as in a set of lines describing a location, at whatever scale and over whatever range is necessary, there’s still an important chore that’s less obviously simple: how do you label it? Labels for the things in the map have to be close to — but not directly on — the thing being labelled, but they also have to be positioned so as not to overlap other labels that have to be there, and also to not overlap other important features, although they might be allowed to run over something unimportant. Add some other constraints, such as the label being allowed to rotate a modest bit but not too much (we can’t really have a city name be upside-down), and working out a rule by which to set a label’s location becomes a neat puzzle.
As I remember from that far back, the solution (used then) was to model each label’s position as if it were an object on the end of a spring which had some resting length that wasn’t zero — so that the label naturally moves away from the exact position of the thing being labelled — but with a high amount of friction — as if the labels were being dragged through jelly — with some repulsive force given off by the things labels must not overlap, and simulate shaking the entire map until it pretty well settles down. (In retrospect I suspect the lecturer was trying to talk about Monte Carlo simulations without getting into too much detail about that, when the simulated physics of the labels were the point of the lecture.)
This always struck me as a neat solution as it introduced a bit of physics into a problem which hasn’t got any on the assumption that a stable solution to the imposed physical problem will turn out to be visually appealing. It feels like an almost comic reversal of the normal way that mathematics and physics interact.
Pardon me, now, though, as I have to go design many, many imaginary subway systems.
May 2013 turned out to be an interesting month for number theory, in that there’ve been big breakthroughs on two long-standing conjectures. Number theory is great fun in part because it’s got many conjectures that anybody can understand but which are really hard to prove. The one that’s gotten the most attention, at least from the web sites that I read which dip into popular mathematics, has been the one about twin primes.
It’s long been suspected that there are infinitely many pairs of “twin primes”, such as 5 and 7, or 11 and 13, or 29 and 31, separated by only two. It’s not proven that there are such, not yet. Yitang Zhang of Harvard has announced proof that there are infinitely many pairings of primes that are no more than 70,000,000 apart. This is admittedly not the tightest bound out there, but it’s better than what there was before. But while there are infinitely many primes — anyone can prove that — how many there are in any fixed-width range tends to decrease, and it would be imaginable to think that the distance between primes just keeps increasing, without bounds, the way that (say) each pair of successive powers of two is farther apart than the previous pair were. But it’s not so, and that’s neat to see.
Less publicized is a proof of Goldbach’s Odd Conjecture. Goldbach’s Conjecture is the famous one that every even number bigger than two can be written as the sum of two primes. An equivalent form would be to say that every whole number — even or odd — larger than five can be written as the sum of three primes. Goldbach’s Odd Conjecture cuts the problem by just saying that every odd whole number greater than five can be written as the sum of three primes. And it’s this which Harald Andres Helfgott claims to have a proof for. (He also claims to have a proof that every odd number greater than seven can be written as the sum of three odd primes, that is, that two isn’t needed for more than single-digit odd numbers.)
Word’s come through mathematics circles about the death of Kenneth Ira Appel, who along with Wolgang Haken did one of those things every mathematically-inclined person really wishes to do: solve one of the long-running unsolved problems of mathematics. Even better, he solved one of those accessible problems. There are a lot of great unsolved problems that take a couple paragraphs just to set up for the lay audience (who then will wonder what use the problem is, as if that were the measure of interesting); Appel and Haken’s was the Four Color Theorem, which people can understand once they’ve used crayons and coloring books (even if they wonder whether it’s useful for anyone besides Hammond).
It was, by everything I’ve read, a controversial proof at the time, although by the time I was an undergraduate the controversy had faded the way controversial stuff doesn’t seem that exciting decades on. The proximate controversy was that much of the proof was worked out by computer, which is the sort of thing that naturally alarms people whose jobs are to hand-carve proofs using coffee and scraps of lumber. The worry about that seems to have faded as more people get to use computers and find they’re not putting the proof-carvers out of work to any great extent, and as proof-checking software gets up to the task of doing what we would hope.
Still, the proof, right as it probably is, probably offers philosophers of mathematics a great example for figuring out just what is meant by a “proof”. The word implies that a proof is an argument which convinces a person of some proposition. But the Four Color Theorem proof is … well, according to Appel and Haken, 50 pages of text and diagrams, with 85 pages containing an additional 2,500 diagrams, and 400 microfiche pages with additional diagrams of verifications of claims made in the main text. I’ll never read all that, much less understand all that; it’s probably fair to say very few people ever will.
So I couldn’t, honestly, say it was proved to me. But that’s hardly the standard for saying whether something is proved. If it were, then every calculus class would produce the discovery that just about none of calculus has been proved, and that this whole “infinite series” thing sounds like it’s all doubletalk made up on the spot. And yet, we could imagine — at least, I could imagine — a day when none of the people who wrote the proof, or verified it for publication, or have verified it since then, are still alive. At that point, would the theorem still be proved?
(Well, yes: the original proof has been improved a bit, although it’s still a monstrously large one. And Neil Robertson, Daniel P Sanders, Paul Seymour, and Robin Thomas published a proof, similar in spirit but rather smaller, and have been distributing the tools needed to check their work; I can’t imagine there being nobody alive who hasn’t done, or at least has the ability to do, the checking work.)
I’m treading into the philosophy of mathematics, and I realize my naivete about questions like what constitutes a proof are painful to anyone who really studies the field. I apologize for inflicting that pain.
If you haven’t seen the Aardman Animation movie Arthur Christmas, first, shame on you as it’s quite fun. But also you may wish to think carefully before reading this entry, and a few I project to follow, as it takes one plot point from the film which I think has some interesting mathematical implications, reaching ultimately to the fate of the universe, if I can get a good running start. But I can’t address the question without spoiling a suspense hook, so please do consider that. And watch the film; it’s a grand one about the Santa family.
The premise — without spoiling more than the commercials did — starts with Arthur, son of the current Santa, and Grand-Santa, father of the current fellow, and a linguistic construct which perfectly fills a niche I hadn’t realized was previously vacant, going off on their own to deliver a gift accidentally not delivered to one kid. To do this they take the old sleigh, as pulled by the reindeer, and they’re off over the waters when something happens and there I cut for spoilers.
. 
. And from doubling the equation about edges and vertices equation in the last paragraph, 
. So if we break up that 6E into 4E and 2E we can rewrite that Euler’s formula again. It becomes 
. 6V – 4E is zero, so, 
. 
. The number of faces has to equal the sum of the number of faces of two edges, and of three edges, and of four edges, and of five edges, and of six edges, and on and on. Counting! 
. This goes on forever but that’s all right. We don’t need all these terms. 
nebusresearch 
