The diamond lemma November 20, 2009Posted by David Speyer in Uncategorized.
A few results
1 (Bjorner, Eidelman and Ziegler) Suppose we have a finite collection of great circles on a sphere, none of them through the north or nouth pole. Let be the set of regions in the complement of these circles, and suppose that every region is a triangle. Put a partial order on by if is south of every circle that is south of. Show that, for and , there is some such that if and only if and .
2 (Mozes, see also IMO 1986.3) Let be a finite graph, and let be a real valued function on the vertices of . Consider the following (solitaire) game: find a vertex for which is negative. Replace by and, for every vertex that neighbors , decrease by . The game ends if all of the are nonnegative. You and I start playing with the same graph and the same . Show that, if my game ends in moves at position , then your game will end in the same position, in the same number of moves.
3 (Poincare, Birkhoff and Witt) Define to be the ring generated by , and , subject to the relations , and . Show that any element of can be expressed uniquely as a sum of elements of the form . (Uniqueness is up to rearranging the sum and combining like terms.)
4 (Jordan and Holder) Let be a finite group. Let
by two sequences of subgroups such that is normal in , with simple, and the same is true for the ‘s. Then and the quotients are a permutation of the quotients .
We say that is a meet of and if has the required properties.
For any region , let be the number of circles below . We will prove the following statement by induction on :
Inductive Claim Suppose that and . Then and have a meet.
This establishes the result, as we can take to be the region containing the north pole and the hypotheses on become trivial. In the other hand, the base case is trivial because, when , then must be the region containing the north pole, we have , and is a meet of and .
Now for the inductive part. Let and be southward traveling paths from to and . Let the first steps on these paths be and , crossing lines and . If , or equivalently , then we can take as a new and we are done by induction. Otherwise, let be the region due south of the crossing of and . It is easy to see that is a meet of and .
Applying the inductive hypothesis to , let be a meet of and . Applying the inductive hypothesis to , let be a meet of and . Applying the inductive hypothesis to , let be a meet of and . We leave it to the reader to check that is a meet of and .
The proof is by induction on . Say my game begins and your game begins . (We don’t know yet that your game ends.) Let my first move be at vertex and yours at vertex . The case is an immediate induction, so let’s assume . We know that and .
My brother and your sister come to join us. Here is how they play. If and are not adjacent, my brother starts off playing at , then at and your sister starts of at and then at . So, after two moves, both he and she reach the same configuration . If, on the other hand, is adjacent to , then my brother starts with and your sister starts . In three moves, they have again reached the same configuration. (Exercise! Remember to check that all vertices which are played are in fact negative at the time.) Call this configuration .
After this, my brother plays in any manner he wishes. By induction, after he moves to , he will make more moves and end at . Your sister also plays in any manner she wishes. By induction between her and my brother, after she gets to , she will make either or more moves and end at , having made moves in total. Finally, we apply the induction hypothesis to you and your sister. After you both move to , you will make more moves, ending at . So we all get to in moves.
I hope it is clear that Solutions 1 and 2 have the same inductive structure, although the details differ. The general strategy goes as follows: suppose we have some process which goes from one state to another. We have two different paths, and that start at the same state, and we want to show that, in some sense, they come together again. In the figure above, we are presented with the black structure, and we need to show that the paths rejoin. We will do this by adding the blue structure.
First, make a careful analysis of the case where the two paths have length , and prove your result in this case.
Now, using your analysis from the first step, build paths and which come together in the required way. Inductively, bring the paths and together at some ; bring the paths and together at some ; finally, bring and together at some .
Often, as in Solution 1, the starting point is trivial in the most important application. But bringing it into the problem allows us to apply this inductive structure.
One of the main difficulties is figuring out what to induct on. Roughly, one wants to use the length of the paths, but this may not be precisely right.
There are many good papers on the diamond lemma, but they tend to focus on applications to one particular field, and call it by different names. Here are some examples of the Diamond Lemma in Grobner bases, noncommutative rings, braid groups (chapter 14, see figure 12!), lattices (lemma 2.1), anti-matroids (lemma 2.6).
Solution 3 (a sketch)
Let’s talk about Puzzle 3. This is typical of applications to ring theory, and there are many subtleties which are particular to this context. I would like to refer to Bergmann’s superb paper for the details but, sadly, it is not publicly available online. For those without academic access, the best reference I can find online is Wenfeng Ge’s masters thesis.
Let’s call a standard monomial, and a sum of standard monomials a standard polynomial. Let the states of our system be formal noncommutative polynomials in , and . Let our operations be finding a term of the form , or , and replacing it by , or respectively. So the states where we can perform no operations are precisely the standard polynomials. We want to show that, starting with any polynomial , this process will terminate and, if we perform the process in two different ways, and , then . I’ll ignore termination, which is the easier question, to focus on the latter issue.
A better way to phrase our claim is that if we have any two paths and , which may not end at standard polynomials, then we can join them together into two paths and
which have a common endpoint. This trick is frequently useful: by phrasing our claim to apply to more paths, we make induction easier.
We start with a careful analysis of the case of paths of length 1. Say we have and . If the two changes happen in different monomials, or if they happen in nonoverlapping parts of the same monomial, then we can just make both changes in the two possible orders to get to the same destination in two steps.
So the only interesting case is two overlapping changes. For example, and . In this case, we make the following moves
The reader familiar with Lie algebras might like to see how this computation works in a general universal enveloping algebra; it’s a bit more complicated because the quadratic terms may not be standard.
The structure of the proof is now the same. Of course, we have to figure out what to induct on, and that’s a little subtle. But the worse issue is the following: Suppose our starting state is and our first move was to on one path, and to on the other. According to the rubric above, we should move . But, as we’ve defined things, this isn’t a legal move, because there is no to replace in . This possibility of terms cancelling is a major nuisance; I leave it to Bergmann to explain how to fix it.
You do it!