The ADE affair, 3

Clusters, and the associated cluster algebras and cluster categories, form a hot topic in mathematics at the moment. Clusters are connected with topics such as Poisson geometry, integrable systems, representation theory and total positivity as well as combinatorial enumeration.

I learned a bit about clusters in two excellent talks at the Algebra, Combinatorics and Dynamics meeting in Belfast in August 2010, by David Jordan and Peter Jørgensen.

This is an exposition of the introductory part of the theory, not including most of the applications hinted at above, but describing a question to which the people I spoke to didn’t know the answer.

I should stress that I am not at all an expert on clusters. The fact that I don’t know something doesn’t mean that it isn’t known! Readers who want to know more are referred to the papers of Fomin and Zelevinsky, especially “Cluster algebras II” in Inventiones Math. 154 (2003), 53-121.

A recurrence

Consider the recurrence relation

x_n+3 = (x_n+1x_n+2+1)/x_n.

Because of the denominators, it might seem that we can’t expect this recurrence to produce integer sequences. Nevertheless, starting with 1,1,1, we obtain 1,1,1,2,3,7,11,26,41,97,153,362,571,…, which is sequence number A005246 in Neil Sloane’s On-Line Encyclopedia of Integer Sequences, where a number of occurrences of it are logged, in particular the fact that it gives the denominators of the continued fraction convergents to √3. Alternatively it gives integer solutions to

⌊√3x²⌋=x⌊√3x⌋

The terms satisfy the linear recurrence a(n) = 4a(n−2)−a(n−4).

We are going to see why this and similar recurrences produce integer sequences.

Quiver mutation

The next definition is not quite standard, but I will stick to it here. A quiver is a finite directed graph (with multiple edges allowed) with the properties

• there are no loops;
• there are no 2-cycles (i.e. all edges between two vertices point in the same direction).

About the last condition: we regard an edge (v,u) as the negative of an edge (u,v), so that two oppositely directed edges between u and v would cancel out. We will often have to add n edges (u,v) to a quiver. If u and v are unconnected, or there are already m edges from u to v, this is unproblematic; if there are m edges from v to u, the result is n−m edges from u to v if n>m, or m−n edges from v to u if m>n (or no edges at all if m=n).

The operation μ_u of mutation of a quiver Q at a vertex u consists of doing the following:

• reverse the directions of all edges incident with u;
• for any two vertices v and w, if there were k edges from v to u and l edges from u to w before mutation, then we add kl edges from v to w (with the convention outlined in the preceding paragraph).

Exercise: μ_u is an involution (that is, doing it a twice returns us to the starting quiver).

We will work with three running examples.

Example 1: Consider the quiver with two vertices 1 and 2, with a single edge from 1 to 2. Both the mutations μ₁ and μ₂ have the effect of reversing this edge.

Example 2: Consider the quiver consisting of a directed path from 1 to 3 on the vertex set {1,2,3}. Mutations at 1 and 3 each reverse a single edge, so that any orientation of the path can be obtained by a sequence of mutations.

Mutation at 2 is a bit more complicated. We reverse the edges (1,2) and (2,3); and, according to the second clause of the definition, we add the edge (1,3). Thus we have produced an oriented triangle (1,3,2).

If we now mutate this triangle at vertex 1, we reverse the edges (1,3) and (2,1); the added edge (2,3) cancels the existing edge (3,2), and we have the directed path (3,1,2).

So we can contain all three paths on the three vertices, each with all possible orientations of edges, together with the two orientations of the triangle.

It is not difficult to check that these 14 quivers are closed under mutation. It happens that 14 is the fifth Catalan number, and counts the number of dissections of a hexagon into triangles. This is no coincidence. It can be shown that the number of quivers obtained from an orientation of a path of length n is the (n+3)rd Catalan number.

Example 3: Take the transitive tournament on {1,2,3} with edges (1,2), (2,3) and (1,3): that is, the total order (1,2,3) on this set.

Mutation at 1 gives the total order (2,3,1), and mutation at 3 gives the total order (3,1,2). Mutation at 2, however, gives the oriented triangle (1,3,2) with the edge (1,3) doubled. If we now mutate this graph at 1 or 3, we reverse all the edges; then mutating at 2, we get the other three transitive tournaments.

The set of 12 quivers consisting of six transitive tournaments and six oriented triangles each with an edge doubled is closed under mutation.

Exercise: Show that any orientation of the edges of a tree can
be obtained from any other by a sequence of mutations.

Remark: Given a quiver Q, is the set of quivers which can be obtained from Q by mutation finite or infinite? I don’t know the answer to this question. In all the examples above, the set is finite. But starting from an oriented triangle where all edges have multiplicity at least 2 and one has multiplicity greater than 2, it is possible to obtain infinitely many quivers by mutation.

Clusters and cluster variables

A seed is an ordered pair (Q,(x₁,…,x_n)), where Q is a
quiver (with vertices numbered 1,…,n) and x₁,…,x_n are
variables which are algebraically independent over C (so that
the field C(x₁,…,x_n) of rational functions of these
variables is a pure transcendental extension of C with transcendence
degree n).

We extend the operation of mutation to act on seeds in the following odd-looking way:

μ_u(Q,(x₁,…,x_n))=(μ_uQ,(y₁,…,y_n)),

where y_i = x_i for i≠u, and

y_u = (∏x_v+∏x_w)/x_u.

The two products are over edges (u,v) originating at u and edges (w,u) terminating at u respectively (multiple edges require the variables to be repeated as often as necessary), and empty products are taken to be 1.

We note two easy things and one non-trivial fact about this operation.

• μ_u acting on seeds is an involution.
• y₁,…,y_n are algebraically independent generators for C(x₁,…,x_n). For we have expressed y_u as a rational function of the xs, and the fact that the transformation is invertible shows that we can go back.
• After any sequence of mutations, if the final cluster variables are
  expressed in terms of the original ones, the denominators are all
  monomials in the original variables.

The variables that arise in this process are called cluster variables. The second component of any seed is a cluster.

Example 1: Let Q and Q* be the quivers with edge (1,2) and (2,1) respectively. Applying μ₁ and μ₂ in turn, the cluster variables are (writing (x,y) for (x₁,x₂)):

• (x,y)
• ((y+1)/x,y)
• ((y+1)/x,(x+y+1)/xy)
• ((x+1)/y,(x+y+1)/xy)
• ((x+1)/y,x)
• (y,x)

and then the sequence continues with the pairs reversed, returning to its starting point after ten steps.

So there are ten clusters, consisting of five pairs (involving reversing the terms in an ordered pair), of the five cluster variables.

It is not entirely clear whether the cluster variables should form a set or a sequence. There are five sets of cluster variables in this case.

If we successively mutate at the vertices alternately, we generate a recurrence relation

x_n+2 = (1+x_n+1)/x_n,

which returns to its starting point after five steps. With x₁=x₂=1, we get the sequence (1,1,2,3,2,1,1,2,…).

We see that the same quiver can be associated with different clusters in a mutation-closed set. However, the following theorem holds:

Theorem:
In the mutation-closure of a single seed, two seeds with the same cluster are equal.

However, the proof of this theorem requires a good deal of theory. I feel that it calls for a more direct proof!

Example 2:
In this case, calculation shows that there are just nine cluster variables, and fourteen (unordered) clusters.

Example 3:
In this example, we saw that mutating the transitive tournament (1,2,3) at 1 produces the transitive tournament (2,3,1). Mutating this at 2 produces (3,1,2), and mutating this at 3 gets us back to (1,2,3).

But the cluster variables do not return to their original values. If we take the original variables to be (x₁,x₂,x₃), and the first mutation to change x₁ to x₄, then x₄=(x₂x₃+1)/x₁. Then we can let the next new cluster variable be x₅, and so on; we have the recurrence relation

x_n+3 = (x_n+1x_n+2+1)/x_n

with which we began this account.

Specialising the starting variables to 1, the theorem about denominators shows that all cluster variables obtained will have denominator 1, that is, will be integers, as claimed. But the sequence with which we began clearly grows for ever, so the set of cluster variables in this case must be infinite.

The main result of the paper of Fomin and Zelevinsky mentioned earlier (and the reason for discussing clusters in this series) is
the following:

Theorem:
The set of cluster variables arising from a given seed is finite if and only if the quiver is an orientation of one of the ADE diagrams.

This result is particularly intriguing since in most cases, the symmetry exhibited by the root system associated with the diagram is not apparent at all from its geometric realization.

In the next section we look at this a bit further.

Actually their result is a bit more general; I have simplified the presentation. They have a formulation which also allows orientations of the diagrams with multiple bonds, which I will discuss later in the series.

Groups

Once we have found the smallest mutation-closed set of quivers containing a given n-vertex quiver, we have a set with n involutions on it, and it is natural to ask what group they generate. In the finite case described by the preceding theorem, it might be natural to expect that this group would be the Coxeter group associated with the diagram; but this turns out not to be the case!

In each of our three examples, the set of quivers is closed under reversing all its edges. The equivalence relation whose classes consist of a quiver and its reverse is preserved by mutation. So in each case the group is imprimitive, with a system of blocks of imprimitivity of size 2.

In Example 1, there are only two quivers, and the group is C₂. It is not too hard to show that in Example 2, the group is the semidirect product of the elementary abelian group of order 2⁶ by S₇, while in Example 3, it is PSL(2,5) (the rotation group of an icosahedron acting on its twelve faces).

Needless to say, I know no general theory which would have predicted these
facts.

The seed-mutations are again involutions on the set of all seeds in a mutation-closed class. The group they generate has the group acting on quivers as a homomorphic image.

In Example 1, the seed-mutation group is dihedral of order 10. The rotations map to the identity and the reflections to the non-trivial permutation of the quivers. I am not sure what happens in the other cases.

So I end with the general problem:

What are the cluster groups associated with clusters for the ADE diagrams? Is there any connection with either the Coxeter groups, or the 3-dimensional rotation groups, of these types?

Previous | Next