The diamond lemma

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 R be the set of regions in the complement of these circles, and suppose that every region is a triangle. Put a partial order on R by x \leq y if x is south of every circle that y is south of. Show that, for x and y \in R, there is some z \in R such that w \leq z if and only if w \leq x and w \leq y.

2 (Mozes, see also IMO 1986.3) Let G be a finite graph, and let r be a real valued function on the vertices of G. Consider the following (solitaire) game: find a vertex i for which r_i is negative. Replace r_i by - r_i and, for every vertex j that neighbors i, decrease r_j by -r_i. The game ends if all of the r_i are nonnegative. You and I start playing with the same graph and the same r. Show that, if my game ends in N moves at position z, then your game will end in the same position, in the same number of moves.

3 (Poincare, Birkhoff and Witt) Define U to be the ring generated by E, F and G, subject to the relations FE=EF+G, GE=EG+F and GF=FG+E. Show that any element of R can be expressed uniquely as a sum of elements of the form E^i F^j G^k. (Uniqueness is up to rearranging the sum and combining like terms.)

4 (Jordan and Holder) Let G be a finite group. Let G = G_0 \supsetneq G_1 \supsetneq G_2 \supsetneq \cdots \supsetneq G_r = \{ e \}
G = H_0 \supsetneq H_1 \supsetneq H_2 \supsetneq \cdots \supsetneq H_s = \{ e \}
by two sequences of subgroups such that G_{i+1} is normal in G_i, with G_{i+1}/G_i simple, and the same is true for the H‘s. Then r=s and the quotients H_{i+1}/H_i are a permutation of the quotients G_{i+1}/G_i.

What do all of these have in common? You can remember all of their solutions by drawing the same figure — the diamond!

Solution 1

We say that z is a meet of x and y if z has the required properties.

For any region r, let \ell(r) be the number of circles below r. We will prove the following statement by induction on \ell(r):

Inductive Claim Suppose that r \geq x and r \geq y. Then x and y have a meet.

This establishes the result, as we can take r to be the region containing the north pole and the hypotheses on r become trivial. In the other hand, the base case is trivial because, when \ell(r)=0, then r must be the region containing the north pole, we have r=x=y, and r is a meet of x and y.

Now for the inductive part. Let r \to \cdots \to x and r \to \cdots \to y be southward traveling paths from r to x and y. Let the first steps on these paths be r \to s and r \to t, crossing lines i and j. If s=t, or equivalently i=j, then we can take s as a new r and we are done by induction. Otherwise, let u be the region due south of the crossing of i and j. It is easy to see that u is a meet of s and t.

Applying the inductive hypothesis to (s, x, u), let z' be a meet of x and u. Applying the inductive hypothesis to (t, u, y), let z'' be a meet of u and y. Applying the inductive hypothesis to (u, z', z''), let z be a meet of z' and z''. We leave it to the reader to check that z is a meet of x and y.

Solution 2

The proof is by induction on N. Say my game begins r \to s \to \cdots \to z and your game begins r \to t \to \cdots. (We don’t know yet that your game ends.) Let my first move be at vertex i and yours at vertex j. The case i=j is an immediate induction, so let’s assume i \neq j. We know that r_i and r_j <0.

My brother and your sister come to join us. Here is how they play. If i and j are not adjacent, my brother starts off playing at i, then at j and your sister starts of at j and then at i. So, after two moves, both he and she reach the same configuration u. If, on the other hand, i is adjacent to j, then my brother starts with iji and your sister starts jij. 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 u.

After this, my brother plays in any manner he wishes. By induction, after he moves to s, he will make N-1 more moves and end at z. Your sister also plays in any manner she wishes. By induction between her and my brother, after she gets to u, she will make either N-2 or N-3 more moves and end at z, having made N moves in total. Finally, we apply the induction hypothesis to you and your sister. After you both move to t, you will make N-1 more moves, ending at z. So we all get to z in N moves.

Generalizing

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, r \to s \to \cdots \to x and r \to t \to \cdots \to y 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 1, and prove your result in this case.

Now, using your analysis from the first step, build paths r \to s \to \cdots \to u and r \to t \to \cdots \to u which come together in the required way. Inductively, bring the paths s \to x and s \to u together at some z'; bring the paths t \to u and t \to y together at some z''; finally, bring u \to z' and u \to z'' together at some z.

Often, as in Solution 1, the starting point r 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 E^i F^j G^k a standard monomial, and a sum of standard monomials a standard polynomial. Let the states of our system be formal noncommutative polynomials in E, F and G. Let our operations be finding a term of the form FE, GE or GF, and replacing it by EF+G, EG-F or FG+E respectively. So the states where we can perform no operations are precisely the standard polynomials. We want to show that, starting with any polynomial r, this process will terminate and, if we perform the process in two different ways, r \to \cdots \to x and r \to \cdots \to y, then x=y. 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 r \to \cdots \to x and r \to \cdots \to y, which may not end at standard polynomials, then we can join them together into two paths r \to \cdots x \to \cdots \to z and
r \to \cdots y \to \cdots \to z 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 r \to s and r \to t. 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, GFE \to (FG+E)E and GFE \to G(EF+G). 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 GFE + FGE and our first move was to E^2 on one path, and to GEF + G^2 + FGE on the other. According to the rubric above, we should move E^2 \to FEG - F^2 + E^2 - FGE. But, as we’ve defined things, this isn’t a legal move, because there is no GE to replace in E^2. This possibility of terms cancelling is a major nuisance; I leave it to Bergmann to explain how to fix it.

Solution 4

You do it!

10 thoughts on “The diamond lemma”

  1. The diamond lemma comes up under other names as well, e.g., “confluence” of normalization/reduction algorithms, the “Church-Rosser property”. Mac Lane’s proof of the coherence theorem for monoidal categories (as given in Categories for the Working Mathematician) is a classic illustration of the technique.

  3. 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.

    There is at least one paper trying to unify the story (http://arxiv.org/abs/0712.1142); it is not written as thorough as it could be though.

    Also (in a pitiful attempt of self-advertising) let me mention this paper as an instance of a yet another Diamond Lemma – it is essentially a paper telling its reader about one good definition, and about what consequences a good definition can have :-)

  4. Is the Vect extension of the diamond lemma still the diamond lemma? I would hope so, and David endorses this usage, but I don’t know if it is entirely standard.

    I first encountered the diamond lemma in Milnor’s proof of unique factorization of 3-manifolds. I have used similar arguments in 3-manifold topology on a few occasions. Of course, the linear version of course also shows up a lot in skein theories for quantum topological invariants.

  5. The Jordan-Holder theorem looks a lot easier to me. You don’t need induction, but can write down the whole diamond at once, by intersecting the two filtrations, to get a diamond-shaped poset.

  6. @Ben Wieland: I think you are right, although even then I think that the diamond proof will be a little shorter than dealing with the whole poset at once. But I also don’t mind having some examples in an expository post which don’t need the full strength of the technique I’m explaining.

    @Greg Kuperberg: I’m not sure exactly what you mean by the Vect extension of the diamond lemma, but it seems to me Bergmann’s paper would be an example of it, and his title is “The Diamond Lemma for Ring Theory.”

  7. @Greg Kuperberg: I’m not sure exactly what you mean by the Vect extension of the diamond lemma, but it seems to me Bergmann’s paper would be an example of it, and his title is “The Diamond Lemma for Ring Theory.”

    Hi David. I should just have said, a linear extension of the diamond lemma. You’re right that George Bergman’s paper (one n, by the way) gives an example of such an extended diamond lemma. It is logically more general than the original diamond lemma, because each case can be completed to a linear combination of different diamonds. The PBW theorem is a classic example of this, of course.

    Maybe it would be interesting to formulate a category-theoretic diamond lemma that captures both the unique-completion and the linear-combination-of-completions cases.

    Now that I think of it, here is yet another interpretation that I noticed recently of the linearly extended diamond lemma, as it arises in the PBW theorem and other cases. The PBW theorem says that a certain filtered vector space, U(g), is the same size as its associated graded. The filtered vector space comes from another filtered vector space, T(g), quotiented by a filtered set of relations. The diamond lemma is equivalent to the statement that spectral sequence of the resolution converges at E_1. It is always equivalent to that statement. So it could be fair to say that the theory of spectral sequences co-opts the diamond lemma. Maybe that is a good way to say it in category theory terms.

  8. Pingback: Irreducible Root Systems « The Unapologetic Mathematician ~

  9. I’m bothered by the first example: it seems non-trivial to construct families of more than three great circles so that every complementary region is a triangle.

  10. Pingback: Operations, pro-objects, and Grothendieck’s Galois theory | Annoying Precision ~

Comments are closed.