What Makes A Theorem Important?

The Car Crash Theorem and why theorems are important

Anton Klyachko is a mathematician who is an expert on group theory. He has worked extensively on equations over groups and related problems, and is on the faculty of the famous Mathematics and Mechanics Department at Moscow State University.

Today I will talk about why some theorems are considered more important than others, here jointly with Ken Regan.

What I will use to make this concrete is a result proved by Klyachko in 1992. The result is called the Car Crash Theorem. Now that is a neat name, but does not sound like a theorem that most would work on, or even think about. But I will argue it is really a quite important theorem.

His paper starts in a way that might suggest that the result is just a fun result. Indeed the title of his paper is: “Funny property of sphere and equations over groups.” I love funny properties, but not all funny properties are important. His is.

The paper has the following unique beginning:

In this paper we present and prove a simple but non-obvious topological fact. This is so simple and funny that can be included in a collection of puzzles or suggested as a problem for a school tournament.

This paper seems quite neat, but it has some issues as pointed out by Roger Fenn and Colin Rourke in their paper. They graciously attribute the problems to language—Russian to English—and to the journal’s editors. Certainly Klyachko’s main idea is quite powerful—if you are interested in the full details see their paper.

I was unable to get an on-line pointer to Klyachko’s paper. Thanks to our library, yes the library, Farbod Shokrieh was able to get the actual paper. Here is the title part:

Note the curve on the left, that is from the book’s shadow as it was being xeroxed. Remember when that was the only way to get journal articles?

Car Crash Theorem

Let be a finite connected graph on the 2-sphere—that is fancy terminology for a ball, as in a basketball or a soccer ball. Around the boundary of each region a car will drive according to these rules:

1. Each car stays on the same boundary forever, it never moves to another region.
2. The motion is continuous, cars cannot jump.
3. Each point of the graph is visited infinitely often, and there is a lower bound on the speed of the cars—they never stop nor slow to a `crawl.”
4. Each car moves with the same orientation.

The rules are really natural: cars move around their region over and over, they never get too slow, nor can they jump, and finally they all have the orientation.

Let’s look, actually look, at the simplest case possible: when has two regions. It would look like this:

Note the inner car and the outer car are really moving with the same orientation. Think of each car driver’s side against the region, and then the car moves forward.

Klyachko’s theorem is:

Theorem: Let be such a connected graph. If cars travel as described above there must be at least two distinct points where there are collisions.

As a check it is easy to see that the cars will “crash” twice as they go around the cycle. Note, we assume that the crash is really not a “crash,” since they keep on moving. Perhaps it should be called a meeting, but I think the Car Meeting Theorem would not be as fun to state.

After I started to write this I discovered that the problem was previously posted to MathOverflow by Anton Geraschenko. He used ants instead of cars. I decided to stay with “cars,” since that is what is used in Klyachko’s paper. I also decided to continue with this discussion too. Please look at MathOverflow for additional comments.

A Proof Sketch

Ken Regan worked out a proof that reads differently from Fenn and Rourke, but uses the same basic ideas. Here it goes:

The idea of the proof is to reduce the general case to trivial cases like the one shown in the diagram above.

First, we can choose one region and flatten the sphere so that region forms a boundary in the plane. Then the car on that boundary is seen from the opposite direction, so it travels counterclockwise. One source calls this the “drunken car” (or ant). The strategy is to contract the drive path of this guy until he causes a crash. (Uh-oh, first a post on using science to serve distortion and now we’re glorifying drunk-driving\dots sometimes one has a bad-hair week.)

Next, we can help the proof by adding more traffic. Add a center point to every region and triangulate its interior. Now consider a car running clockwise around the boundary. Just before it comes to an intersection, imagine a car that just beats it to the corner and turns in front of it. We can now make the original car turn right and head to the center in the opposite direction that just traveled. Thus, with a gap that can be made arbitrarily small, car takes over the function of car , while itself disappears to the outside world. This pattern can be continued all the way around the boundary avoiding all crashes, even at the center. Thus the new triangulated graph has a crash-free itinerary if and only if the new graph has.

Now consider any edge being traversed by the drunken car. Either it is the outer edge of a triangle with two edges toward the middle, or part of two boundary edges of a triangle with one interior edge.

In the latter case, picture the interior edge being the base of a triangle with the two boundary edges pointing up. As the drunken car approaches the first boundary edge from the right, the normal car must be on the interior edge. It cannot be on either boundary edge, else the drunken car will crash into it before it finishes the triangle. Moreover, in a crash-free itinerary, the drunken car must complete the two edges before the normal car finishes that edge. Once the drunken car has moved off that triangle, we don’t care what the normal car does. Hence if the original itinerary is crash-free, then we can get a crash-free itinerary in the graph obtained by deleting the two boundary edges, and making the drunken car take over the no-longer-needed normal car on the interior edge. We have thus made progress in contracting the graph.

In the former case we have similar reasoning, but with an extra twist. As the drunken car approaches the boundary edge of the triangle, the normal car can be on either of the two interior edges. If it is on the interior edge away from the drunken car’s entry, then it is still the case that it must stay on that edge until the drunken car is off the triangle. Hence in the graph obtained by removing the boundary edge, we may suppose the drunken car speeds up quickly to overtake and then take over the normal car. If it is on the interior edge incident to the drunken car’s entry, it might not even reach the second edge before the drunken car has moved on. But this is the case where we don’t care what the normal car does thereafter—so we again can just speed up the drunken car after it has overtaken the normal car. Again the transformation of removing exterior edge(s) from the triangle does not increase the number of crashes.

The process can continue until we get a single triangle (or the degenerate two-edge case above). Then the drunken car is driving counterclockwise along the outside of the triangle, while the last normal car is driving clockwise on the inside. Clearly they will crash, but we can even say more. If both cars do one full circuit, then they must crash twice. Although we spoke in terms of having a crash-free itinerary in proving our single-triangle reductions, the logic applies to say that the reduction does not increase the number of crashes. Hence the original graph must have at least 2 crashes, which completes the proof.

Another View

We can translate spherical or planar map instances into a constraint-satisfaction problem of building certain interval graphs. Let there be “tracks” for the regions in the map, including the outer region for the drunken car. Give each edge two labels for its two directions. Then we divide each track into intervals corresponding to the labels of the edges in region . The constraints are:

As the intervals are formed going left-to-right, the label of the next interval must be the successor to the previous one.

For each edge, its two labels form a forbidden pair.

A crash-free itinerary then yields an interval graph that meets these constraints. This graph has nodes for each interval on each track. Two nodes are adjacent if their intervals overlap vertically. The graph meets the second set of constraints if no adjacent nodes form a forbidden pair. If we extend the adjacency relation to successive nodes within each track, then we forbid all pairs other than the successor in the region’s cycle.

Finally we require that track~1, for the drunken car, must be a full cycle. Then the theorem is equivalent to saying there is no way to complete intervals on the other tracks without violating one (or two) of the constraints.

Why Is It Important?

Why is this theorem important? Why are any theorems important? There are at least several reasons that come to mind:

Some theorems are important because of their intrinsic nature. They may not have applications, but they just are beautiful. Or they have a interesting proof.

Some theorems solve open problems. Of course any such theorem is automatically important, since the field has already decided that the question is interesting.

Some theorems create whole new directions for mathematics and theory. These are sometimes—not always—relatively easy theorems to prove. But they may be very hard theorems to realize they should be proved. Their importance is that they show us that something new is possible.

Some theorems are important because they introduce new proof techniques. Or contain a new lemma that is more useful than the theorem proved.

Some theorems are important because of their “promise.” This is a subjective reason—a theorem may be important because people feel it could be even more important. Here, both the relation to group equations and the constraints-on-interval-graphs view make us feel Klyachko Car Crash Theorem has some hidden possibilities.

The Application

Klyachko’s Car Crash Theorem is important because it partially solved a long standing open problem. The problem concerns when equations over certain groups can be solved. An equation over a group is:

where is the unknown and are elements of the group and the exponents are integers. Say it has a solution provided there is a group that contains as a subgroup and an element in so that the equation is true. The nature of the equation is sensitive to the sum of the exponents. I have discussed this before here. Consider,

which is the equation

It has no solution if and have different finite orders. This follows since , which implies that and must have the same order. Note the sum of the exponents in this example equation is .

In particular Klyachko uses his theorem to prove:

Theorem: An equation over a group without torsion is solvable if the exponent sum is .

Recall torsion means that there are elements in the group of finite order.

It might seem strange that his basic topological fact about graphs has anything to do with group equations, but it does. Very roughly: words over a group can be used to build a graph that naturally lies on the 2-sphere. See the paper for the details. Then, the Car Crash Theorem is invoked.

Open Problems

Did you know Klyachko’s Car Crash Theorem? I ran across in my continuing attempt to understand solvable groups: I am still trying to prove or disprove whether or not a solvable group can be universal. Recall that would imply that is in . More on the status of my search in the near future.