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 ${\Gamma}$ 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 ${\Gamma}$ 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 ${\Gamma}$ 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 ${A}$ running clockwise around the boundary. Just before it comes to an intersection, imagine a car ${A'}$ that just beats it to the corner and turns in front of it. We can now make the original car ${A}$ turn right and head to the center in the opposite direction that ${A'}$ just traveled. Thus, with a gap that can be made arbitrarily small, car ${A'}$ takes over the function of car ${A}$, while ${A}$ 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 ${r}$ “tracks” for the ${r}$ 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 ${r}$ into intervals corresponding to the labels of the edges in region ${r}$. The constraints are:

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

${\bullet}$ 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:

${\bullet }$ 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.

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

${\bullet }$ 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.

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

${\bullet }$ 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 ${G}$ is:

$\displaystyle a_1x^{e_1} a_2x^{e_2} \dots a_mx^{e_m} = 1,$

where ${x}$ is the unknown and ${a_1,a_2\dots}$ are elements of the group ${G}$ and the exponents ${e_i}$ are integers. Say it has a solution provided there is a group ${\hat G}$ that contains ${G}$ as a subgroup and an element ${x}$ in ${\hat G}$ 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,

$\displaystyle ax = xb,$

which is the equation

$\displaystyle b^{-1}x^{-1}ax = 1.$

It has no solution if ${a}$ and ${b}$ have different finite orders. This follows since ${b = x^{-1}ax}$, which implies that ${a}$ and ${b}$ must have the same order. Note the sum of the exponents in this example equation is ${0}$.

In particular Klyachko uses his theorem to prove:

Theorem: An equation over a group ${G}$ without torsion is solvable if the exponent sum is ${1}$.

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 ${\mathsf{NC^1}}$ is in ${\mathsf{TC^0}}$. More on the status of my search in the near future.

1. December 4, 2010 12:32 pm

Regarding the title question, Terence Tao wrote a really nice article, “What is good mathematics?”, on the subject.

• December 5, 2010 6:33 pm

Qiaochu Yuan, that was a terrific article by Terry Tao that you suggested. It provides a near-perfect complement to Dick and Ken’s essay … I enjoyed both of these essays immensely.

If I may offer an engineering perspective, one aspect of good theorems and good mathematics, that is not mentioned (except implicitly) in either of the above essays, is simply tbis: Good math in general, and good theorems in particular, rest upon necessary foundations of good postulates.

As a case in point, I recently had occasion to (recreationally) compute instances of the so-called “half-exponential functions”. These functions were fun to instantiate as algorithms solely because I was *not* aware of the (several) mathematical analyses of this topic on the MathOverflow forum. Via correct mathematical reasoning, the MathOverflow analyses drew computationally discouraging conclusions regarding the feasibility of computing these functions … but fortunately, these theorems depended upon postulates that (in retrospect) are not binding upon applied mathematicians and engineers.

It is for this reason that engineers believe (as I put it on Scott’s weblog): Postulates—no matter how convenient—must not become articles of faith.

The point is that for a good theorem to be recognized as a great theorem, it must rest upon postulates that are so strong, and so natural, that even the hyper-elastic consciences of applied mathematicians and practicing engineers cannot find loopholes in them. 🙂

December 6, 2010 6:08 pm

Following your link about half-exponential functions, it at least SEEMS as if you mistake the statement that half-exponential functions aren’t elementary functions to mean they can’t be described finitely or approximated arbitrarily well – for example by their taylor expansions, Newton’s method or as solutions of an initial value problem.

Being ELEMENTARY is a rather specific property for a function, it means it can be described by FINITE algebraic combinations of the identity, log,exp and n-th roots. Hypergeometric functions for example are generally not elementary functions. I’d even say MOST functions mathematicians care about are not elementary.

I certainly agree that many mathematicians are too stubborn about precise terms. They often seem to first search for loopholes in the formulation of a question so they can answer it negatively (for example by citing some fact about Galois groups, that really only matters in the most rigorous interpretation of the question).

Quite regularly an obvious generalization of weakening of the statement (usually this is what the questioner is interested in) can be answered positively.

Like in this case, the statement that half-exponential functions aren’t elementary is useless, almost irrelevant in the computer age.

• December 6, 2010 6:54 pm

Jac, I agree entirely with your arguments. To paraphrase Mark Twain:

Uniformity is precious; let us economize it.

🙂

2. December 4, 2010 3:11 pm

This problem also appears in one of Winkler’s puzzle books.

December 5, 2010 3:41 am

In the former case of edge deletion (the one with a twist), it is true that the “normal car” which is about to be deleted can be overtaken, but how can it be shown that there is an itinerary for the drunken car which will avoid OTHER normal cars, ie. ones which aren’t about to be deleted, which may be passing through one of the edges of the triangle under consideration?

For instance, how can you rule out the case where the about-to-be-deleted car is on the edge incident to where the drunken car enters, while another normal car is on the further edge?

December 5, 2010 4:05 am

Hm, I guess the solution is to speed up the normal car so that it gets out of the way in time, which means temporarily speeding up ALL the normal cars passing through the intersection it needs to get out of the way.

• December 5, 2010 2:22 pm

Ah thanks, you raise a good point. The answer I had in my mind while writing my version of the proof is that since the “drunken car” is tracing the same route that the normal car has just followed, it would inherit the crash-avoidance property. Your issue is that the movement of the normal car thru the first of the 2 edges might free a second normal car in the triangle to its right to go up that edge, which would then oppose the drunken car.

This seems to be “the rub” against the proof really being as easy as my writeup, in particular my writeup not needing a notion of “flow”. I did express my disconcertment about that to Dick before we posted, but figured this was either the “language issue” or because the theorem in the Fenn-Rourke version was more extensive. My argument may be fixable in any of 3 ways: (1) saying we are inducting always on the first triangle in the drunken car’s cycle; (2) your solution, which could be tantamount to implementing a notion of flow; or (3) arguing that either the middle triangle or the one to its right can be shortcutted out.

Indeed, now I see (3) seems to == the “Crucial Lemma” in the MathOverflow item, since those two triangles share one edge. (I should clarify also that this is the source of this proof strategy as well as the “drunk” car/ant nomenclature.) Not sure I can say more on it now, as Dick and I have 2 other non-blog things going on and we both have XYZ besides. This takes me back to my days of homework in advanced university courses, except where your homework will be published on the Internet even before the professor has a chance to grade it :-).

4. December 5, 2010 7:43 am

Unfortunatly i have not yet solved it.

December 6, 2010 10:48 am

I think there is a need for a more rigorous definition, since you can make the cars virtually jump by adding single edges – the car will disappear at a point to come back later while traversing the extra edge, thus allowing graphs that can be traversed without crashes. I think you mean something more like that the graph is 2-connected, or perhaps that the dual is without loops?

December 6, 2010 1:49 pm

Peter

If you add edges, then you add cars? No. See the paper for the details.