# September 10, 2002 {#week186}

Okay, now let's pull together all the strands of our story about Dynkin
diagrams and $q$-mathematics. The story can be summarized in a rather
elaborate diagram, of which this is the first part:
$$
  \begin{tikzpicture}[scale=2]
    \node[align=center] (dyn) at (0,0) {Dynkin diagram};
    \node[align=center] (sag) at (-1,-1) {simple algebraic\\group};
    \node[align=center] (cog) at (1,-1) {Coxeter group};
    \node[align=center] (flv) at (-1,-2) {flag variety};
    \node[align=center] (coc) at (1,-2) {Coxeter complex};
    \node[align=center] (qpl) at (0,-3) {$q$-polynomial};
    \draw[->] (dyn) to node[label=left:{\scriptsize pick a field}]{} (sag);
    \draw[->] (dyn) to (cog);
    \draw[->] (sag) to node[label=below:{\scriptsize Weyl group}]{} (cog);
    \draw[->] (sag) to (flv);
    \draw[->] (cog) to (coc);
    \draw[->] (flv) to (qpl);
    \draw[->] (coc) to (qpl);
  \end{tikzpicture}
$$
We start with a Dynkin diagram and see what we can do with it; we'll
find that two separate routes lead to the same polynomial, which for
lack of a better name I'll call the "$q$-polynomial". In recent weeks
I've hinted that starting with the Dynkin diagrams in the $\mathrm{A}_n$ series,
like this:
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) to (4,0);
    \foreach \x in {0,1,2,3,4}
      \node at (\x,0) {$\bullet$};
  \end{tikzpicture}
$$
we get the polynomials called "$q$-factorials". Now I'll sketch the
story for arbitrary Dynkin diagrams!

Way back in ["Week 62"](#week62) I showed how a Dynkin diagram
gives a finite reflection group: that is, a finite group of symmetries
of $n$-dimensional Euclidean space, generated by reflections, one for each
of the $n$ dots in the diagram, satisfying relations described by the
edges in the diagram. In fact, I noted that this trick works for a
slightly more general class of diagrams called "Coxeter diagrams". The
resulting groups are called "Coxeter groups".

But let's not go for maximal generality: any Dynkin diagram gives us a
Coxeter group, and that's enough for now. Some of these Coxeter groups
are symmetry groups of Platonic solids and their analogues in other
dimensions: the regular polytopes. For example, starting with this
Dynkin diagram:
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) to (1,0);
    \node at (0,0) {$\bullet$};
    \node at (1,0) {$\bullet$};
    \node at (2,0) {$\mathrm{A}_2$};
  \end{tikzpicture}
$$
we get the symmetry group of the equilateral triangle, while starting
with this one:
$$
  \begin{tikzpicture}
    \draw[double,double equal sign distance] (0.5,0) to (1,0);
    \draw[double,double equal sign distance,-implies] (0,0) to (0.55,0);
    \node at (0,0) {$\bullet$};
    \node at (1,0) {$\bullet$};
    \node at (2,0) {$\mathrm{B}_2$};
  \end{tikzpicture}
$$
we get the symmetry group of the square, and starting with this one:
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) to (2,0);
    \node at (0,0) {$\bullet$};
    \node at (1,0) {$\bullet$};
    \node at (2,0) {$\bullet$};
    \node at (3,0) {$\mathrm{A}_3$};
  \end{tikzpicture}
$$
we get the symmetry group of the regular tetrahedron. Other Coxeter
groups are symmetry groups of polytopes that aren't regular. This, for
example:
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) to (6,0);
    \draw[thick] (4,0) to (4,1);
    \foreach \x in {0,1,2,3,4,5,6}
      \node at (\x,0) {$\bullet$};
    \node at (4,1) {$\bullet$};
    \node at (7,0.5) {$E_8$};
  \end{tikzpicture}
$$
is the symmetry group of a non-regular polytope in 8 dimensions with 240
vertices!

However, some Coxeter groups are not naturally regarded as the symmetry
groups of polytopes. So, to deal with all Coxeter groups in a systematic
way, it's better to think of them as symmetries of certain simplicial
complexes called "Coxeter complexes". Roughly speaking, a simplicial
complex is a gadget made of points, line segments, triangles,
tetrahedra, $4$-simplices, and so on --- all stuck together in a nice way.

If you have a Coxeter diagram with $n$ dots, the highest dimension of the
simplices in its Coxeter complex will be $n-1$, and it will have one of
these top-dimensional simplices for each element of the Coxeter group.
For example, I've already said this Dynkin diagram:
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) to (1,0);
    \node at (0,0) {$\bullet$};
    \node at (1,0) {$\bullet$};
    \node at (2,0) {$\mathrm{A}_2$};
  \end{tikzpicture}
$$
gives the Coxeter group consisting of symmetries of the equilateral
triangle --- by which I mean all reflections and rotations. This group has
6 elements, so the Coxeter complex is built from 6 line segments
together with lower-dimensional simplices (points) --- and in fact, it's
just a hexagon.

A hexagon is also what you get by dividing each edge of the equilateral
triangle into two parts. That's no coincidence: whenever our Coxeter
group is naturally the symmetries of a polytope, we can get the Coxeter
complex by "barycentrically subdividing" the surface of this polytope
- which basically means sticking an extra vertex in the middle of every
face of the polytope and using these to chop its surface into simplices.

For example, this diagram
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) to (2,0);
    \node at (0,0) {$\bullet$};
    \node at (1,0) {$\bullet$};
    \node at (2,0) {$\bullet$};
    \node at (3,0) {$\mathrm{A}_2$};
  \end{tikzpicture}
$$
gives the symmetry group of the tetrahedron, so we can get its Coxeter
complex by barycentrically subdividing the surface of the tetrahedron,
obtaining a shape with 24 triangles. Surprise: this is just the size of
the symmetry group of the tetrahedron!

But that's how it always works: the number of top-dimensional simplices
in the Coxeter complex is the number of elements in the Coxeter group.
Even better, if you pick any top-dimensional simplex in the Coxeter
complex, there always exists a *unique* element of the Coxeter group
that maps it to any other top-dimensional simplex. So the Coxeter
complex is the best possible thing made out of simplices on which the
Coxeter group acts as symmetries.

Now, all of this has been done starting with a Dynkin diagram and
nothing else. But we can do other stuff if we pick a field, like the
real numbers $\mathbb{R}$ or the complex numbers $\mathbb{C}$ --- or if you're feeling daring,
the field $\mathbb{F}_q$ with $q$ elements, where $q$ is some power of a prime number.

First and most importantly, a field lets us define a "simple algebraic
group". If we use $\mathbb{R}$ or $\mathbb{C}$ as our field these are just the usual real or
complex simple Lie groups associated with Dynkin diagrams, which I
explained in ["Week 63"](#week63) and ["Week 64"](#week64).
These are tremendously important in physics, and that's what got me
going on this business in the first place! But we can also mimic this
procedure using other fields, and if we use the finite field $\mathbb{F}_q$, we
get fascinating connections to $q$-mathematics... which I've begun
explaining in recent Weeks.

No matter what field we use, the group we get will be the symmetries of
a kind of "incidence geometry": a setup with stuff like points, lines,
and planes, but perhaps also other geometrical figures that they never
told you about in school. There will be one type of geometrical figure
for each dot in our Dynkin diagram!

In the case where our field is the complex numbers, I explained these
incidence geometries rather carefully in ["Week 178"](#week178),
["Week 179"](#week179) and ["Week 180"](#week180). But
they're pretty similar for other fields, so to a zeroth approximation
you can sort of fake it and pretend they work just the same. Eventually
that attitude will get you in trouble, but hopefully you'll notice when
it happens.

For example, the Dynkin diagram $\mathrm{A}_n$ has $n$ dots in a row like this:
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) to (4,0);
    \foreach \x in {0,1,2,3,4}
      \node at (\x,0) {$\bullet$};
  \end{tikzpicture}
$$
and this gives the symmetry groups of *projective* geometry: the
geometry of points, lines, planes, and so on up to dimension $n$.

More precisely, if we pick any field $\mathbb{F}$, we can use this diagram to
concoct the group $\mathrm{SL}(n+1,\mathbb{F})$ consisting of $(n+1)\times(n+1)$ matrices with
entries in $\mathbb{F}$ and determinant equal to $1$. This group acts on the
projective $n$-space $\mathbb{FP}^n$ --- the space of all $1$-dimensional subspaces of
the vector space $\mathbb{F}^{n+1}$. Just as in the complex case, we can talk about
points, lines, planes and the like in $\mathbb{FP}^n$, and also incidence
relations like "this point lies on that line". These relations satisfy
the axioms of projective geometry, as explained in
["Week 162"](#week162). The group $\mathrm{SL}(n+1,\mathbb{F})$ acts on all these
geometrical figures in a way that preserves the incidence relations...
so we say it's a symmetry group for this particular projective
geometry!

(If you prefer the group $\mathrm{PSL}(n+1,\mathbb{F})$, that's fine too; maybe even
better. They have the same Lie algebra so it's not all that big a
deal.)

The same general sort of thing works for all other Dynkin diagrams, too.
The $\mathrm{B}_n$ and $\mathrm{D}_n$ series give the symmetry groups of conformal
geometries, while the $\mathrm{C}_n$ series give the symmetry groups of symplectic
geometries, and the exceptional Dynkin diagrams give symmetry groups of
"exceptional geometries" associated to the octonions and their
analogues for other fields.

In general, whenever we pick a Dynkin diagram and a field we get a
geometry. We define a "maximal flag" in this geometry to consist of
one geometrical figure of each type, all incident. The set of maximal
flags turns out to be the key to understanding all the different kinds
of incidence geometry in a unified way. When our field is the real or
complex numbers this set is a manifold, often called the "flag
manifold" --- it's a special case of the flag manifolds described in
["Week 180"](#week180). But over other fields, the set of maximal
flags is not a manifold but an "algebraic variety". If you don't know
what that means, don't worry: I'm only mentioning this because then we
get to call it the "flag variety" and sound intelligent. The real
point here is that there's a wonderful analogy:

| simple algebraic groups | Coxeter groups |
| :---------------------- | :------------- |
| flag varieties | Coxeter complexes |

Just as a Coxeter group acts as symmetries of its Coxeter complex, a
simple algebraic group acts as symmetries of its flag variety. But the
analogy goes far deeper than that! In a certain strange way, you really
can think of the Coxeter group as a simple algebraic group over the
field $\mathbb{F}_q$ where $q = 1$, and you can think of the Coxeter complex as the
corresponding flag variety.

Of course, there *is no* field $\mathbb{F}_q$ with $q = 1$. Nonetheless, all sorts
of formulas that work for other values of $q$ for simple algebraic groups
over $\mathbb{F}_q$ and their flag varieties, apply when $q = 1$ to Coxeter groups
and their Coxeter complexes! I gave the primordial example in
["Week 184"](#week184), which comes from the Dynkin diagram $\mathrm{A}_n$.
The number of points in the flag variety of the group $\mathrm{SL}(n+1,\mathbb{F}_q)$ is
the $q$-factorial
$$[n+1]! = [1] [2] \ldots [n+1]$$
where
$$[i] = 1 + q + q^2 + \ldots + q^{i-1}$$
When we set $q = 1$ in this formula, we get the ordinary factorial $(n+1)!$,
and this is the number of total orderings of an $n$-element set. It's
also the number of top-dimensional simplices in the Coxeter complex for
$\mathrm{A}_n$ --- and that's the way to think about it that works for other Dynkin
diagrams.

In general, the trick is to set up a kind of incidence geometry starting
from the Coxeter complex, in which the top-dimensional simplices serve
as maximal flags, and the $0$-simplices serve as geometrical figures of
the various types... where two figures are "incident" if the
$0$-simplices are both vertices of some top-dimensional simplex!

To get a tiny taste of how this stuff works, consider the Dynkin diagram
$\mathrm{A}_2$. We've seen that the Coxeter complex is a barycentrically
subdivided triangle:
$$
  \begin{tikzpicture}
    \draw[thick] (0,0) node{$\bullet$} to node{$\times$}
      (2,0) node{$\bullet$} to node{$\times$}
      (1,1.73) node{$\bullet$} to node{$\times$}
      (0,0);
  \end{tikzpicture}
$$
or viewed a bit differently, a hexagon:
$$
  \begin{tikzpicture}
    \draw[thick] (0:1) node{$\bullet$} to
      (60:1) node{$\times$} to
      (120:1) node{$\bullet$} to
      (180:1) node{$\times$} to
      (-120:1) node{$\bullet$} to
      (-60:1) node{$\times$} to
      (0:1);
  \end{tikzpicture}
$$
Here the vertices marked $\times$ are the vertices of the original triangle,
while the vertices marked $\bullet$ correspond to its edges. We make up a puny
little geometry where the $\times$'s are called "points" and the $\bullet$'s are
called "lines". And we say a point and a line are "incident" if the
$\times$ and $\bullet$ are the two ends of a line segment.

Note that any two distinct points are incident to a unique line, and any
two distinct lines are incident to a unique point! This is
characteristic of projective plane geometry. And that's just right,
because $\mathrm{A}_2$ is the Dynkin diagram corresponding to projective plane
geometry. If we do projective plane geometry over a field $\mathbb{F}$, the group
$\mathrm{SL}(3,\mathbb{F})$ acts as symmetries. But for this puny little geometry, the
*Coxeter group* acts as symmetries. This is the symmetry group of the
triangle, which is the group of permutations of its three vertices.

More generally, suppose we start with the diagram $\mathrm{A}_n$. Then we'd see
that its Coxeter group consists of permutations of $n+1$ things: the
vertices of an $n$-simplex. The Coxeter complex would be gotten by
barycentrically subdividing the surface of this $n$-simplex. And the
Coxeter group would act on a puny little geometry built from the Coxeter
complex, very much as $\mathrm{SL}(n+1,\mathbb{F})$ acts on the projective space $\mathbb{FP}^n$.

As I explained in ["Week 184"](#week184) and
["Week 185"](#week185), this relation between permutation groups
and the groups $\mathrm{SL}(n+1,\mathbb{F})$ is just the tip of a very big iceberg. What
I'm saying now is that a similar story works for all the other Dynkin
diagrams, too!

To explain how this works, I'd need to tell you about the "Bruhat
decomposition" of a flag variety. And to explain it *really* well, I'd
need to tell you about Jacques Tits' theory of "buildings". Jim Dolan
and I have been studying this over the last year, and it's really
cool... but alas, it's too big a subject to explain here! So think of
this Week as a mere *advertisement* for the theory of buildings, if you
like. I'll give you some references at the end.

Okay. So far I've talked about two kinds of things we can get from
Dynkin diagrams: "flag varieties", if we pick a field, and "Coxeter
complexes", where we don't need to pick a field. Now let's bring in
the $q$-mathematics! It turns out that that we can decategorify either the
flag variety or the Coxeter complex and get something I call the
"$q$-polynomial".

We can define this polynomial in four equivalent ways:

a) the coefficient of $q^i$ in this polynomial is the number of Coxeter
group elements of length $i$. Here we "length" of any element in the
Coxeter group is its length as a word when we write it as product of the
generating reflections.

b) the coefficient of $q^i$ in this polynomial is the number of
top-dimensional simplices of distance $i$ from a chosen top-dimensional
simplex in the Coxeter complex. Here we measure "distance" between
top-dimensional simplices in the hopefully obvious way, based on how
many walls you need to cross to get from one to the other.

c) the coefficient of $q^i$ in this polynomial is the number of $i$-cells
in the Bruhat decomposition of the flag variety. Here the "Bruhat
decomposition" is a standard way of writing the flag variety as a
disjoint union of "$i$-cells", that is, copies of $\mathbb{F}^i$ where $\mathbb{F}$ is our
field and $i$ is a natural number. These $i$-cells are called either
"Bruhat" or "Schubert" cells, depending on who you talk to.

d) the coefficient of $q^i$ is the rank of the $(2i)$th homology group of
the flag variety defined over the complex numbers. More precisely: this
homology group is isomorphic to $\mathbb{Z}^k$ for some natural number $k$, called
the "rank" of the homology group.

It's easy to see that a) and b) are equivalent; ditto for c) and d).
The equivalence between b) and c) is deeper; it comes from the wonderful
analogy between Coxeter complexes and flag varieties.

Let's calculate the $q$-polynomial of $\mathrm{A}_2$ using method b):
$$
  \begin{tikzpicture}
    \draw[thick] (0:1) node{$\bullet$} to node[label={[label distance=-1mm]above right:{$1$}}]{}
      (60:1) node{$\times$} to node[label={[label distance=-1mm]above:{$0$}}]{}
      (120:1) node{$\bullet$} to node[label={[label distance=-1mm]above left:{$1$}}]{}
      (180:1) node{$\times$} to node[label={[label distance=-1mm]below left:{$2$}}]{}
      (-120:1) node{$\bullet$} to node[label={[label distance=-1mm]below:{$3$}}]{}
      (-60:1) node{$\times$} to node[label={[label distance=-1mm]below right:{$2$}}]{}
      (0:1);
  \end{tikzpicture}
$$
I've written down the distance of each top-dimensional simplex from a
given one. There's one of distance $0$, two of distance $1$, two of
distance $2$, and 1 of distance $3$. This gives
$$q^3 + 2q^2 + 2^q + 1 =  [3]!$$
just as it should.

We can distill all sorts of nice information from the $q$-polynomial. For
example, starting from facts a) -- d) we immediately get:

e) the degree of this polynomial is the maximum length of an element of
the Coxeter group. There is in fact a unique element with maximum
length, called the "long word".

f) the degree of this polynomial is the dimension of the flag variety
over any field.

and also:

g) the value of this polynomial at $q$ a prime power is the cardinality
of the flag variety over the field $\mathbb{F}_q$.

h) the value of this polynomial at $q = 1$ is the number of elements in
the Coxeter group.

i) the value of this polynomial at $q = 1$ is the Euler characteristic of
the flag variety over the complex numbers.

j) the value of this polynomial at $q = -1$ is the Euler characteristic
of the flag variety defined over the real numbers.

We can summarize this network of relations in the following diagram:
$$
  \begin{tikzpicture}[scale=2]
    \small
    \node[align=center] (dyn) at (0,0) {Dynkin diagram};
    \node[align=center] (sag) at (-1,-1) {simple algebraic\\group};
    \node[align=center] (cog) at (1,-1) {Coxeter group};
    \node[align=center] (flv) at (-1,-2) {flag variety};
    \node[align=center] (coc) at (1,-2) {Coxeter complex};
    \node[align=center] (qpl) at (0,-3) {$q$-polynomial};
    \draw[->] (dyn) to node[label=left:{\scriptsize pick a field}]{} (sag);
    \draw[->] (dyn) to (cog);
    \draw[->] (sag) to node[label=below:{\scriptsize Weyl group}]{} (cog);
    \draw[->] (sag) to (flv);
    \draw[->] (cog) to (coc);
    \draw[->] (flv) to (qpl);
    \draw[->] (coc) to (qpl);
    \node[align=center] (ml) at (-1.5,-4) {number of points\\in flag variety\\over $\mathbb{F}_q$ group};
    \node[align=center] (mr) at (1.5,-4) {dimension of\\flag variety\\= length of\\longest word\\in Coxeter};
    \draw[->] (qpl) to node[label=left:{\scriptsize value at a prime power $q$}]{} (ml);
    \draw[->] (qpl) to node[label=right:{\scriptsize degree}]{} (mr);
    \node[align=center] (bl) at (-1.75,-5.75) {number of Coxeter\\group elements\\= number of cells\\in flag variety\\= Euler characteristic\\of flag variety\\over $\mathbb{C}$};
    \node[align=center] (br) at (1.75,-5.75) {number of Coexter\\group elements\\of length $i$\\= number of $i$-cells\\in flag variety\\= rank of $(2i)$th\\homology group of\\flag variety\\over $\mathbb{C}$};
    \draw[->] (qpl) to (bl);
    \node[fill=white] at (-0.9,-4.65) {\scriptsize value at $q=1$};
    \draw[->] (qpl) to (br);
    \node[fill=white] at (0.9,-4.65) {\scriptsize $i$th coefficient};
    \node[align=center] (b) at (0,-6) {Euler characteristic\\of flag variety\\over $\mathbb{R}$};
    \draw[->] (qpl) to (b);
    \node[fill=white] at (0,-5.3) {\scriptsize value at $q=-1$};
  \end{tikzpicture}
$$
Besides things I've already explained, I stuck in an extra arrow
showing that you can get the Coxeter group from a simple algebraic group
by forming something called its "Weyl group". I explained this
connection way back in ["Week 62"](#week62). If we work over the
real numbers and use the compact real form of our simple Lie group, the
Weyl group acts on the Lie algebra of the maximal torus of this group ---
the so-called "Cartan algebra". In this context it's good to think of
the Coxeter complex as sitting inside the Cartan algebra!

Next week I'll go through a bunch of examples. Right now, let me just
give you some references for further reading.

To understand most of what I'm saying you mainly just need to
understand the "Bruhat decomposition" of the flag variety. For a quick
sketch of how this works over the complex numbers, try this book:

1) William Fulton and Joe Harris, _Representation Theory --- a First Course_, Springer Verlag, Berlin, 1991.

For a treatment of it over arbitrary fields, try:

2) Francois Digne and Jean Michel, _Representations of Finite Groups of Lie Type_, London Mathematical Society Student Texts **21**, Cambridge U. Press, Cambridge, 1991.

But to understand the relation to incidence geometry, it will help a lot
if you eventually study "buildings". This subject has a certain
reputation for obscurity. One good place to start is this book written
by someone who was himself trying to understand the subject:

3) Kenneth S. Brown, _Buildings_, Springer, Berlin, 1989.

Another is this:

4) Paul Garrett, _Buildings and Classical Groups_, Chapman & Hall, London, 1997.

For a lot more information about how finite simple groups show up as
symmetries of buildings, try:

5) Antonio Pasini, _Diagram Geometries_, Oxford U. Press, Oxford, 1994.

and for the original source, go to:

6) Jacques Tits, _Buildings of Spherical Type and Finite BN-pairs_, Springer Lecture Notes in Mathematics **386**, Berlin, New York, 1974.

Even better, come and sit in on Jim Dolan's seminar on the subject,
here at UCR!