Tuesday, December 23, 2008

Th Seven Bridges of Q'w'nis

The most recent US presidential election has left Rotary High Command in something of a quandary. The window on many of our most of our important higher governmental connections is now closing. No longer will we be able to send captured Kiwanians to secret sites in Eastern Europe to be enlightened on new, aggressive interrogation techniques. But Noon Rotary is not so easily discouraged, and it has occurred to some in High Command that the current political situation might give that pitiful minority of the club who are democrats added value added value, if only as hostages.

It was in this spirit that I, a mere Replacement Cog in the group’s organizational structure, was approached with the request of a favor requiring something of my mathematical training. The following story was related to me in regard to some black operations that are being carried out deep in enemy territory on behalf of Noon Rotary High Command by a group known simply as “the Agency.”

This region is known as Q’w’nis. It is occupied by a simple, though sinister, people who are famed for creating a special wheat cake covered with a sugary tree derivative in the month of December. There is a huge gorge that divides the region of Q’w’nis and in the middle of that gorge are two tall rock formations, much like what you see in monument valley. One of the formations is called B’tar and the other S’ryp.

The gorge itself is too wide to be spanned directly by a bridge of any type; nevertheless, the pieces of the region are bound together for purposes of transportation by great swinging bridges that make use of B’tar and S’ryp. On the south side of the gorge there are a total of three bridges. Two of these connect to B’tar and one to S’ryp. On the north side, there are also three which connect to B’tar and S’ryp in the same way. There is also a single bridge between B’tar and S’ryp. This means there are five bridges connecting to B’tar, three to S’ryp, and a total of seven bridges all together.

The Agency plans to destroy these bridges in order to disrupt trade in the region and have concocted the following plan. Land a helicopter secretly on B’tar and begin tracing a path across the bridges, destroying each one as they go. Then, having closed the path, get back into the helicopter and return home.They discovered a problem, however. Normally the Agency just comes up with these plans and does them, but this time one of the agents drew a map of the region and began tracing out the route ahead of time. He discovered that, no matter how he traversed the bridges, when all the bridges were destroyed, he was somewhere besides on B’tar with the helicopter.

This was a pretty green agent or he never would’ve planned it out ahead. He would’ve done his job and dealt with the consequences as they happened. However, it occurred to the Agency that they might be able to save the helicopter if they called in a consultant. That’s where I came in.

As is so often the case, they did not get the answer they wanted. It turns out that, regardless of the path their agent might take, he will wind up stranded away from the helicopter. Each of the bodies of land has an odd number of bridges attaching it to the rest. If you use up the bridges as you cross them, you will always wind up away from where you started.

“This is actually exactly like the old Seven Bridges of Konigsberg problem,” I said. “It was solved by Leonhard Euler centuries ago.”

“Konigsberg?” the contact said. “I’ve never heard of Konigsberg.”

“It’s called Kalingrad now,” I said. “It’s in Russia.”He said nothing but eyed me suspiciously. Getting no further feedback, I still proceeded.

“You know,” I said, “it occurs to me that if your purpose is just to disrupt travel you could leave the single bridge between B’tar and S’ryp intact, and take out the remaining six bridges from the B’tar-S’ryp end of it.”

On hearing that, he answered.“The Agency does not require you to tell us how to do our business.” And with that, he left.I wonder if this will get me any points with High Command.

Friday, December 12, 2008

Hyperbolic History

An Introductory Fable
The McCoys were a family who lived in the hills and had a passel of kids. Passel is one of those imprecise words, but when I say it here, I mean more than one, but beyond that the actual number is not important. The hills that the family lived in and the hollows that they farmed were, in spite of their verdant fecundity, relatively bereft of people.

The McCoys were full of life and laughter and stories. These stories were about people the parents had known in old country during the days before they came to the hills. The children, though they'd heard the stories many times, loved to listen to them again and again.

When each of the McCoy children came of age, a trip was made to the city, which was many miles away, and a suitable spouse was found and brought back.

Each time the new couple lived with the original family until they were on their feet and had a desire for independence and at such a time they--quite tearfully because the family was close--removed themselves from the original family in order to take up occupation in one of the adjacent valleys.

As travel was difficult and by foot, there weren't many opportunities to travel back and forth, and eventually they fell out of touch, busy with their own lives.

As the years progressed, the McCoy grandchildren came of age and were married to suitable spouses, had families, and moved them into adjacent hills and hollows , but, and, for similar reasons, fell out of touch with their parents.

In the fullness of time, the family filled up the land, and, it came to pass, that distant cousins were residing in adjacent valleys far from the original McCoy home. They met and feasted because of coming upon kinfolks, however distant, in such a way. They passed the tradition moonshine jug and shared stories. In doing this they made the discovery they could understand the stories from those original McCoys so much better than each other's more recent stories.

Though they were neighbors in the sense of geography, they were much closer to those first McCoy's culturally than they were to each other.

Hyperbolic Geometry

Tenth grade geometry was the first course in mathematics I actually liked. My teacher, Hoyt Sloan, was of the old-fashioned sort who insisted that we learn how to do proofs. (With a name like Hoyt, you are going to be old-fashioned.) As I read more about mathematics and learned more about geometry, I kept running into something called hyperbolic geometry. It was rather a mysterious area of knowledge. None of my sources described what it was other than an alternative to Euclidean geometry. Euclidean geometry is what is taught in a typical high school geometry class.

It is named for Euclid, the ancient Greek mathematician, because he wrote a book about it in which he had a set of rules (axioms and postulates) that described the ways points, lines, and planes behave. The postulates were "obvious" statements from which other less obvious statements were deduced.

One of these postulates stated that given a line and a point not on the that line there is exactly one line through the point that is parallel to the original line. This is called the parallel postulate. Whereas postulates are meant to stand without proof, it seemed to a lot of folks that they should be able to prove the parallel postulate, so over the years a lot of ink was spent in the process of trying to do just that, but no one ever succeeded.

That's because you can't. It turned out there are other geometries besides Euclidean and the geometry in which there is more than one line through a point that is parallel to the original line is called hyperbolic geometry.

It's presented this way because that is how it was stumbled upon historically, but I find this regrettable because it leaves the impression that there is something wrong with hyperbolic geometry.

A Better Approach

A better way to understand the hyperbolic plane is through the concept of curvature. First, think about a sphere, which is the idealized version of a ball. (That is to say a basketball or a billiard ball, not a costume ball.) If you put a spherical object on a table, you can see that points on the ball curve away from the table. This is called positive curvature.

The table upon which the ball is sitting it perfectly flat and doesn't curve. This is called zero curvature.

Now consider another familiar object: the saddle. (If you are not from a rural culture, think of a Pringle's Potato Chip.) If you put a saddle on a table, you will note that some of the saddle curves away from the table and some curves toward it.

It's impossible to actually do this, but you can imagine the saddle to sink into the table so the the point of the saddle that normally meets your posterior is flush with the table top itself. Doing this, you can see in your head that part of the saddle is below the table and part is above. This is called negative curvature.

Now imagine yourself taking a walk. When you are walking on the plains around Wichita, you are most likely standing at a point of zero curvature. When you are at the peak of a mountain in Colorado, you are at a point of positive curvature.

But when you are standing at the top of a mountain pass in Utah with canyon walls curving up away from you on either side and the road curving down and away in front and behind you, you are at a point of negative curvature.

Geometrically speaking, in Euclidean Geometry, every point is a point of zero curvature and in Hyperbolic Geometry every point is a point of negative curvature.

How Big is your Circle?

One of the first formulas that anyone learns is C=2πr, that is the circumference of a circle is 2 times pi times the radius of the circle. This formula only works in Euclidean geometry, however. On the surface of a sphere, the circumference of a circle is somewhat less than it would be for a circle of the same radius on a plane.

You can see this by imagining a basketball cut in half along its equator. The equator is a circle because every point on it is the same distance from the north pole. (Not that a Santa Claus lives on a basketball, but I think you know what I mean.) Making the half basketball flat requires stretching out the equator, which makes it larger. In other words, it was originally smaller.

In hyperbolic geometry, the case is the opposite. The circumferences of circles are much larger with respect to their radii that is the case in Euclidean geometry. To be technical--and you knew I'd get here eventually--there is an exponential relationship between the radius and the circumference of the circle in hyperbolic geometry.

What does this have to do with a bunch of danged ol' hillbillies?

This is the connection, at least in a metaphorical way, to my original example. Your usual intuition for distances does not work in hyperbolic geometry. If you were taken by a spaceship to a hyperbolic world (a world inhabited a race of shapely warrior princesses...er forget that), it would be dangerous to go walking around.

As you got farther from your spaceship, the circumference of a circle around your spaceship would become increasingly large, and before you had gotten very far, it would be too far for you to walk around in a reasonable amount of time. Indeed if you walked to any place on the planet, but then decided you wanted to go to all most any other place, you would be well-advised to walk back to your spaceship first.

There are mathematicians who've noted this sort of behavior in the geometry of graphs. I don't mean the sort of graphs that you run into in College Algebra or Calculus. You might know them better by the name networks. These are geometrical/combinatorial objects constructed with vertices and edges, as you may have seen in the Seven Bridges of Konigsburg Problem.

It has occurred to me that if you have a growing system in which there is memory of the beginning state and the gaining of memories in subsequent states, after several generations there will be a great informational distance been the product states. That is to say, the McCoy cousins are not going to have much in common to talk about beyond stories about their great-great-etc grandparents--if they have managed to keep that tradition alive.

A practical application

This is the section in which the usually mild-mannered mathematician rants. Seeing a culture come unravelled is not pleasant. (I am convinced he end of civilization will be viewed on YouTube.) There are so many venues in which we take in culture, so many channels on the television, so many blogs on the 'Net, our common core of information is becoming very small relative to the mass of data that we are buried under. In order to understand someone who is outside of our own circle, we have to refer back to that common core of culture.

In my opinion, this makes it much more important to actually HAVE a common core of culture, a set of stories that everyone knows. As religious-nut/Bible-thumper being one of my avocations, I would tout holy scripture to an important part of our common cultural core. (I'd also put the old Warner Brothers cartoons there, but I am widely considered strange.)