Jorge Luis Borges is one of the most mathematical of great writers. In an essay entitled “Kafka and his Precursors”, he pointed out that there is a strange collection of pieces and fragments, including Zeno’s paradox and stories by Han Yu, Kierkegaard, Léon Bloy, and Lord Dunsany, which have something in common, but that if Kafka had never written, we would not have perceived the similarity; these pieces have the property of being “Kafkaesque”.

It has twice happened to me that something I wrote later turned out to be important in the study of a subject that didn’t exist at the time. Each time, it was a collaboration with Jaap Seidel, to whom I owe a very great deal; the second time, Sergei Tsaranov was involved too.

The first of these events was my first joint paper. Jaap had invited us to visit him in the north of Holland where he was having a sailing holiday (except that the weather was far too bad to allow any sailing). We drove with him back to Eindhoven; I remember walking in a nature reserve in Arnhem, looking at the moufflons while discussing the material which would go into this paper. This paper turned out to anticipate the concept of “mutually unbiased bases” in quantum information theory. However, I won’t discuss this further here.

The case I want to talk about is a paper entitled “Signed graphs, root lattices and Coxeter groups”, which Jaap, Sergei and I published in 1994. Reading this paper reminds me what a universal mathematician (I almost said “magpie”) Jaap was. Some of the background to this can be found in my posts on the ADE affair, starting here.

A root system of type ADE consists of a spanning set of vectors in Euclidean space, each of squared length 2, any two making an angle 60°, 90°, 120° or 180°, and (crucially) closed under reflection in the hyperplane perpendicular to any vector in the set. We assume that the root system is indecomposable, that is, not contained in the union of non-zero orthogonal subspaces. The integer span of a root system is a root lattice, a discrete subgroup of the additive group of the vector space. The reflections referred to in the definition generate the Weyl group of the lattice.

A root system contains a fundamental basis, a basis such that all inner products are non-positive; any root can be expressed in terms of the basis, with all coefficients having the same sign. The reflections corresponding to a fundamental basis generate the Weyl group. Each has order 2, and the product of two of them has order 2 or 3 according as the corresponding roots make angle 90° or 120°. The group defined by these generators and relations is the Coxeter group associated with the root system. It is known that the natural map from the Coxeter group to the Weyl group is an isomorphism.

The fundamental basis can be represented by a graph whose vertices are the vectors, two vertices joined by an edge (which implicitly has label −1) if they are not perpendicular (so their inner product is −1). This graph is the Coxeter–Dynkin diagram of the root system. Thus, these diagrams implicitly contain complete information about the root system, its root lattice, and its Coxeter group.

What if we choose a different basis?

Any basis can be represented by a signed graph, whose vertices are the vectors, and two vertices are joined by an edge if they are not perpendicular, the sign of the edge being the inner product of the vectors. We can associate a signed adjacency matrix A with such a graph; the graph represents a basis for a root system if and only if 2I+A is positive definite. We can tentatively associate a Coxeter group with the signed graph, ignoring the signs on the edges; the Weyl group will again be a homomorphic image of this group.

In the paper, one of the tasks we performed was to find what additional relations are necessary to give a presentation of the Weyl group. For each chordless cycle in the graph whose edges carry an odd number of + signs, we add a relation


where x1, …, xn are the vertices in the cycle. It is easy to see that an equivalent relation is obtained if we start the cycle in a different point, or traverse it in the opposite direction.

Thus we defined the Coxeter group of the signed graph to be the quotient of the usual Coxeter graph by these relations. In our case, it is isomorphic to the Weyl group.

There is far more in the paper than this; I will summarise briefly.

  • We introduced a notion of local switching which corresponds to natural operations on bases for a given root system. We reported briefly on the “clusters” into which signed graphs are partitioned by repeated local switching, based on computations by Franz Bussemaker.
  • More significantly, we investigated what happens if the adjacency matrix of the signed graph is not positive definite. It then corresponds to a root system in a real vector space with indefinite inner product. In the positive semidefinite case, we used the theory of vanishing lattices from singularity theory to explain the positive semi-definite case (where the Weyl group is a semi-direct product of the additive group of a lattice with a finite Weyl group). We showed that things go badly wrong in general.

Last week Robert Marsh talked about cluster algebras in the Pure Mathematics seminar. I have briefly discussed this in the series on ADE, and will be even more brief here. The remarkable theorem of Fomin and Zelevinsky asserts that a mutation class of seeds is finite if and only if one of them has a graph which is a Coxeter–Dynkin diagram. This is remarkable partly because cluster algebras are associated with directed graphs, whereas Coxeter–Dynkin diagrams are undirected. In order to make the correspondence work, it is necessary to symmetrise the digraphs.

Marsh and his co-author Michael Barot, after proving their results, had noticed our paper, and discovered that there is an overlap in the simply-laced (ADE) case: our local switching corresponds to cluster mutation, and the presentations they had obtained for the Weyl groups in that case corresponded precisely to ours. Their work was more general in that they deal with the other Coxeter–Dynkin diagrams (of types BFG) as well, and ours is more general in that we say something about the non-positive-definite case.

Their paper is here on the arXiv.

I don’t think we need feel bad for not inventing cluster algebras six years before Fomin and Zelevinsky. They had Coxeter–Dynkin diagrams with directions on the edges, and found it convenient to undirect them. Ours were all undirected by definition, since they arise from inner products; it would not have been clear to us that we should give them directions.

Jaap would have been absolutely delighted by this link, and would certainly have made suggestions about further directions that we could take.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , . Bookmark the permalink.

1 Response to Precursors

  1. Bill Fahle says:

    Another famous writer/mathematician is Lewis Carroll, aka Charles Dodgson. He wrote about as much math under real name Charles Dodgson as he did literary work under his pen name.

    I like to believe in impossible things, until they become possible.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.