Also available at http://math.ucr.edu/home/baez/week186.html

September 10, 2002
This Week's Finds in Mathematical Physics (Week 186)
John Baez

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:


                          DYNKIN DIAGRAM
                          /             \
                         /               \
           pick a field /                 \ 
                       /                   \
                      /                     \
                     /        Weyl group     \
           SIMPLE ALGEBRAIC ----------> COXETER GROUP 
                 GROUP                        | 
                    |                         | 
              FLAG VARIETY             COXETER COMPLEX 
                     \                       /
                      \                     /
                       \                   /
                        \                 /
                         \               /
                          \             /
                           \           /
                           q-POLYNOMIAL


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 
of the A_n series, like this:

                  o-------o-------o-------o-------o

we get the polynomials called "q-factorials".  Now I'll sketch the 
story for arbitrary Dynkin diagrams!  

Way back in "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:

                           o-------o                  A_2

 
we get the symmetry group of the equilateral triangle, while starting
with this one:

                           o===>===o                  B_2


we get the symmetry group of the square, and starting with this one:


                       o-------o--------o             A_3


we get the symmetry group of the regular tetrahedron.  Other Coxeter
groups are symmetry groups of polytopes that aren't regular.   This, 
for example:

                                     o
                                     | 
                                     |                E_8
                 o----o----o----o----o----o-----o


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:  

                           o-------o                   A_2

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

                       o-------o--------o              A_3

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 R or the complex numbers C - or if you're feeling daring,
the field 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 R or C as our field these are just the usual real
or complex simple Lie groups associated with Dynkin diagrams, which 
I explained in "week63" and "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 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 "week178", "week179" and
"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 A_n has n dots in a row like this:


                  o-------o-------o-------o-------o


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 F, we can use this diagram to
concoct the group SL(n+1,F) consisting of (n+1) x (n+1) matrices with
entries in F and determinant equal to 1.  This group acts on the
projective n-space FP^n - the space of all 1-dimensional subspaces of
the vector space F^{n+1}.  Just as in the complex case, we can talk about
points, lines, planes and the like in FP^n, and also incidence relations
like "this point lies on that line".  These relations satisfy the axioms
of projective geometry, as explained in "week162".  The group SL(n+1,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 PSL(n+1,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 B_n and D_n series give the symmetry groups of conformal geometries,
while the 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 "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 F_q where q = 1, and you can think of the Coxeter
complex as the corresponding flag variety.

Of course, there *is no* field F_q with q = 1.  Nonetheless, all sorts
of formulas that work for other values of q for simple algebraic groups 
over F_q and their flag varieties, apply when q = 1 to Coxeter
groups and their Coxeter complexes!  I gave the primordial example in
"week184", which comes from the Dynkin diagram A_n.  The number of 
points in the flag variety of the group SL(n+1,F_q) is the q-factorial 

[n+1]! = [1] [2] ... [n+1]

where

[i] = 1 + q + q^2 + ... + 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 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 A_2.  We've seen that the Coxeter complex is a barycentrically
subdivided triangle:       

                               x
                              / \
                             /   \
                            /     \
                           /       \
                          o         o
                         /           \
                        /             \
                       /               \
                      /                 \
                     x---------o---------x


or viewed a bit differently, a hexagon:


                            x-----o
                           /       \
                          /         \
                         o           x
                          \         /
                           \       /
                            x-----o

Here the vertices marked x are the vertices of the original triangle,
while the vertices marked o correspond to its edges.  We make up a puny
little geometry where the x's are called "points" and the o's are called
"lines".  And we say a point and a line are "incident" if the x and o
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 A_2 is the Dynkin diagram corresponding to projective plane
geometry.  If we do projective plane geometry over a field F, the group
SL(3,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 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 SL(n+1,F) acts on the projective space
FP^n.

As I explained in "week184" and "week185", this relation between 
permutation groups and the groups SL(n+1,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 F^i where 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 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 A_2 using method b):
                
                              0
                           x-----o
                        1 /       \ 1
                         /         \
                        o           x
                         \         /
                        2 \       / 2
                           x-----o
                              3

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 + 2q + 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 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:


                          DYNKIN DIAGRAM
                          /             \
                         /               \
           pick a field /                 \ 
                       /                   \
                      /                     \
                     /       Weyl group      \
           SIMPLE ALGEBRAIC ----------> COXETER GROUP 
                 GROUP                        | 
                    |                         | 
              FLAG VARIETY             COXETER COMPLEX 
                     \                       /
                      \                     /
                       \                   /
                        \                 /
                         \               /
                          \             /
                           \           /
                           q-POLYNOMIAL
 value at a prime power q /   |  |  |  \degree
                         /    |  |  |   \
    number of points in /     |  |  |  dimension of flag variety =
  flag variety over F_q       |  |  |  length of longest word in Coxeter group
                              |  |  |
                              |  |  |
                value at q = 1|  |  |ith coefficient
                              |  |  |
         number of Coxeter group | number of Coxeter group 
                        elements | elements of length i =
               = number of cells | number of i-cells
                 in flag variety | in flag variety =
       = Euler characteristic of | rank of (2i)th homology group of
             flag variety over C | flag variety over C
                                 |
                                 |
                                 |value at q = -1
                                 |
              Euler characteristic of flag variety over R 


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 "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!

-----------------------------------------------------------------------
Previous issues of "This Week's Finds" and other expository articles  on
mathematics and physics, as well as some of my research papers,  can be
obtained at

http://math.ucr.edu/home/baez/

For a table of contents of all the issues of This Week's Finds, try

http://math.ucr.edu/home/baez/twf.html

A simple jumping-off point to the old issues is available at

http://math.ucr.edu/home/baez/twfshort.html

If you just want the latest issue, go to

http://math.ucr.edu/home/baez/this.week.html