Buildings and BN-Pairs
Todd Trimble
March 19, 2007
The purpose of these notes is to study the notions of buildings
and BN-pairs, and ultimately define them in a short crisp form which
we hope will be congenial to category theorists. A building is
sometimes described as a kind of "metric space" in which the distance
function takes values in a Coxeter group instead of the real
numbers. Here we will take that description seriously, from Lawvere's
point of view that the appropriate generalization of metric space is
that of a category enriched in a monoidal category.
An ulterior motive is that the idea of building as standardly defined
seems rather closely tied to the combinatorics of Coxeter groups, and
hence does not seem obviously exportable to other enriched category
(or other logical) contexts. We correct this impression by
reformulating the notion in terms of a natural quantalic logic, in a
way which invites much wider generalization within enriched category
theory.
1. The Rough Idea
From one point of view, buildings are axiomatizations of incidence
geometries (such as projective planes). The basic objects of study are
"flags" in the geometry (chains of incidence relations); for example,
in the case of projective plane geometry, a flag would be an ordered
pair (point, flag) where the point is incident to the flag.
To specify the geometry, we specify certain types of geometric
relations on the set of flags, and a Coxeter group is used to keep
track of these relations. For example, in the case of projective
planes, two flags f, f' stand in one of the following six types of
relation:
-- f and f' are identical
-- f and f' have the same point
-- f and f' have the same line
-- the point of f lies on the line of f'
-- the point of f' lies on the line of f
-- f' is in generic position with respect to f.
The six relations here are tracked by the six elements of the Coxeter
group S_3. To make this precise, consider a very degenerate example
of a "projective plane", where the "points" are the vertices (0), (1),
(2) of a triangle. and the "lines" are the edges (01), (02), (12). Let
us choose a flag f as our "favorite", say <(0), (01)>. With respect
to f, any other flag f' will be best (i.e., most sharply) described by
exactly one of the six relations above, and the unique permutation on
0, 1, 2 which sends f to f' is the element of S_3 used to track that
relation. Hence:
Relation: Element:
-- f and f are identical e
-- f and f' have the same point (1 2)
-- f and f' have the same line (0 1)
-- point of f lies on line of f' (0 2 1)
-- point of f' lies on line of f (0 1 2)
-- f in general position wrt f (0 2)
In general, a Coxeter group W is used to define a certain type of
incidence geometry, and in fact is considered a simple "degenerate"
model for that geometry, with exactly one flag f' to bear witness to
each type of geometric relation with respect to a chosen favorite
flag. Then, a general model for that geometry, called a W-building,
is then given by a set of "flags" F together with a function
d: F x F --> W
where d(f, f') is the relation which "most sharply" describes
how f' stands in relation to f. This "distance" function d
must satisfy certain building axioms which it is our purpose to describe.
2. Coxeter groups and "Murphy monoids".
The "distance" d should be thought of as measuring "how close two
flags are to being identical". When we say "d(f, f') is the relation
which *most sharply* describes how f' stands in relation to f", we
seem to be suggesting that the relations are ordered in terms of
"sharpness", where the sharpest possible relation is the identity
relation. In other words, we seem to be suggesting a sharpness poset
structure on W, with the identity playing the role of maximal element.
However, W is a group. Unless W is trivial, the group
operations on W (multiplication, inversion) do not respect a partial
order structure on W. Thus the group structure on W is at odds with
this (to-be-defined) sharpness order, and in fact thinking of W as a
group, while traditional, may not be the best way to express the sense
in which buildings are "metric spaces with W-valued distances".
Interestingly, there is another way to think of the underlying set of
W, as carrying a monoid structure which James Dolan has taken to
calling the "Murphy monoid", which does respect the sharpness order.
This monoid is denoted W_{oo}, and buildings will be certain types of
metric spaces valued in W_{oo}, or more precisely certain categories
enriched in the monoidal poset W_{oo}.
But before we carry this out, it is a good idea to recall some basic
facts about Coxeter groups, as some of these facts do play a role in
Murphy monoids. First, recall that a Coxeter group is really a group
presentation, described by an n x n Coxeter matrix M. The generators
s_1, ..., s_n correspond to rows of M, and the relations are given by
equations
(s_i s_j)^{m_{ij}} = 1
where m_{ij} is the entry of M in row i and column j. The axioms on M
are that each diagonal entry m_{ii} is 1) (the generators s_i are
involutions), and each m_{ij} = m_{ji} is a positive integer greater
than 1, possibly infinite. Quite extraordinarily, these simple
conditons are enough to ensure that the Coxeter group defined by these
relations can be realized as a group of reflections (on a sphere, or
on an affine space, or on a hyperbolic space). Some of the finite
Coxeter groups fall within well-known infinite series (such as those
of types A, B, and D); others are more special (e.g., E_6, E_7, and
E_8). All these reflection groups are also equivalently described by
well-known Coxeter diagrams.
Let us rewrite the defining relations of the group presentation in the
equivalent form
(si)^2 = 1 [quadratic relations]
(si)(sj)(si)... = (sj)(si)(sj)... [generalized braid relations]
where each side of the second equation is an alternating word of
length m_{ij}. It turns out that the word problem for this
presentation of Coxeter groups is decidable: there is an algorithm for
deciding whether two words in the alphabet s1, ..., sn are related by
applying a sequence of braid relations and quadratic relations. In
rough outline, this is a terminating and confluent algorithm for
finding a word in "normal form" which represents a given group
element. This word will be in particular a "reduced" word, meaning a
word of shortest length among all words which represent that group
element. This means no sequence of applications of braid relations
will deform the word into another in which two si's appear
consecutively (which would permit a shortening by replacing (si)^2 by
1). Any reduced word can be brought to normal form by applying a
certain set of braid relations; we won't go into the details
here. Suffice it to say that the normal form gives a section
Normal form: W --> Free monoid on {s1, ..., sn}
of the canonical projection
Free monoid on {s1, ..., sn} --> W
which sends a word to its value in W.
Now we turn to the definition of "Murphy monoid" based on a Coxeter
matrix M. This is presented as a monoid with generators s1, ..., sn as
before, but subject to the defining relations
(si)^2 = si [quadratic relations]
(si)(sj)(si)... = (sj)(si)(sj)... [generalized braid relations]
Thus, the only difference between this and the previous
presentation is that the si are idempotents, not involutions.
The word problem for the Murphy monoid is also decidable; in fact, one
just uses the same normalizing algorithm used for the Coxeter group!
The point is that a reduced word for the Coxeter group is the same as
a reduced word for the Murphy monoid (or, in other words, if a word is
not reduced because it can be shortened by applying (si)^2 = 1 on the
Coxeter side, it is not reduced because it can be shortened by
applying (si)^2 = si on the Murphy side). Thus, the set of words in
normal form is the same in each case: the image of the section
Normal form: W_{oo} --> Free monoid on {s1, ..., sn}
is the same as the image of the normalizing section of the Coxeter
group, and hence there is a definite way of identifying W with W_{oo}
as sets of normal words (or of braid-equivalence classes of reduced
words). In this way, we can view W_{oo} as a monoid deformation of W
in a meaningful way.
There is one more piece of algebraic structure we need for the Murphy
monoid: a *-operator, whose counterpart for the Coxeter group is
inversion. Recall that a *-operator on a monoid is a map x |--> x*
such that 1* = 1, (xy)* = y*x*, and x** = x. On the Murphy monoid,
there is a unique *-operator such that s* = s for each generator s
(observe that if a *-operator is defined in this way on the free
monoid, where it writes a word backwards, then this operator clearly
respects the quadratic and braid relations, and hence induces a
well-defined operator on the Murphy monoid).
3. The Murphy monoid as monoidal poset. Murphy actions.
We define a "sharpness" order on W_{oo} by stipulating that the
identity e is the sharpest element of all (i.e., is the top element in
the sharpness order), and then defining sharpness to be the smallest
reflexive transitive antisymmetric relation which is respected by the
Murphy monoid operations. We will write w => w' or w' <= w to say that
w' is sharper than w. (Note: the order <= opposite to the sharpness
order is usually called the *Bruhat order*.
Thus W_{oo} becomes a monoidal poset. Moreover, it is obvious that the
*-operator preserves the order, so we can say that W_{oo} is a
*-monoidal poset.
Let us illustrate this structure in the case of projective planes,
where W = S_3. We take as one generator of W the transposition l = (0
<--> 1), which changes the flag <(0), (01)> in the degenerate model W
to <(1), (01)>, thus changing the point but keeping the line. We may
call l "the point-changer". For the other generator, we take the
transposition p = <1 <--> 2>, which changes the flag <(0), (01)> to
<(0), (02)>, thus changing the line but keeping the point. We call p
"the line-changer".
Now we regard l and p as generators of the W_{oo}, and write out the
elements (as reduced words) together with the poset structure. One
element a is sharper than another element b if there is a path running
up from a to b.
e
/ \
l p
|\ /|
|/ \|
lp pl
\ /
lpl=plp
We now describe the geometric meaning of W_{oo}, using again the
example of projective planes to illustrate. There are several (closely
related) pictures for how we might think of an element w in W_{oo}. We
discuss the case w = p for concreteness, but the general definitions
are clear:
(a) Bruhat cell picture: d(f, f') = p. This says f and f' have the
same point, but that is the most we can say (i.e. f and f' are not
identical). The set of f' bearing this relationship to a fixed flag f
forms a Bruhat cell B_p of the space of flags. There are six Bruhat
cells B_w, one for each element w of W_{oo}; they partition the flag
space.
(b) Schubert cell picture: d(f, f') <= p. This says f and f' have the
same point. They may be equal. The set of f' bearing this relationship
to a fixed f forms a Schubert cell S_p of the space of flags. There
are six Schubert cells S_w, with an inclusion S_w <= S_w' if w <= w'.
(c) Bruhat operator picture: consider p as an operator assigning to
each flag f the set of flags f' satisfying d(f, f') = p [i.e., f and
f' have different lines, but nothing worse than that]. In other words,
we think of the line-changer p as a relation [p]: F -|-> F (a function
F --> PF). Each w defines an operator [w]: F -|-> F.
(d) Schubert operator picture: consider w as an operator assigning to
each flag f the set of flags f' such that d(f, f') => w, i.e., as a
relation [w]: F -|-> F.
Here are some crucial facts, which may be checked by hand for
projective planes, and which form vital ingredients for the general
notion of building.
(1) The Schubert operators define a homomorphism
(W_{oo}, <=) --> P(F x F)
of *-monoidal posets (where the multiplication on P(F x F) is
relational composition, the *-operator is the taking of relational
opposites, and the ordering is by inclusion). We will call this the
Schubert condition.
(2) If s is a generator of the Murphy monoid, then the Bruhat operator
[s] satisfies [s] = [s]*. Moreover, if w is a reduced word
(x1)(x2)...(xk) [where the xi are drawn from the set of generators],
then in the Bruhat operator picture, we have
[(x1)(x2)...(xk)] = [x1].[x2]...[xk].
where the left side refers to the value of the word w in the Murphy
monoid (or Coxeter group). We will call (2) the Bruhat-Tits condition.
Notice that (2) is manifestly untrue if w is unreduced. Take for
example the word w = pp (whose value is p in the Murphy monoid). We
have that f'' belongs to ([p].[p])(f) iff f'' can be obtained by
changing the line of f twice (once to an intermediate flag f', and
then again to get f''). But then it is possible for f'' to be
identical to f! Hence we have for the Bruhat operators the equation
[p][p] = [p] + 1.
hence [pp] = [p] is not equal to [p][p]. But in the case of reduced
words, the Bruhat-Tits condition gives a nice way of picturing the
Bruhat cell classification based on Murphy words. Take for example the
Bruhat cell B_{pl} (with respect to a favored flag f). According to
the Bruhat-Tits condition, this is the set of flags obtainable from f
by first applying the operator p (change a line of f to get some new
flag f') followed by the operator l (change a point of f' to get a new
flag f''). [Note: we are composing left to right in the Murphy
monoid.] This means precisely that the line of f'' passes through a
point of f, and the Bruhat cell B_{pl} consists precisely of all such
f''.
It is clear that the Bruhat-Tits condition (2) sharpens the Schubert
condition (1) in the case where the products occurring in (1) are
reduced, and in fact (2) is the standard definition of building!
However, by making reference to reduced words, it seems somewhat
specific to Coxeter groups: it is not immediately clear how the idea
of building might generalize to other contexts. We repair this defect
in the next section.
Now a word about the terminology "Murphy monoid": who is Murphy? This
is actually something of a joke. Looking at the equation (1), it
claims that the Murphy product x1...xk gives a kind of worst-case
scenario for which Bruhat cell a flag f', obtained as an element or
possible outcome of applying the operators [x1], [x2], ..., [xk] to f,
can belong to: "worst" in the sense of being as far from identical to
f as possible. Thus, if we side with the pessimist Murphy who said,
"whatever can go wrong, will go wrong", the prediction is that the
Murphy product x1...xk does give the Bruhat cell that f' winds up
living in. In fact, the pessimist is generally (I mean generically)
right. For example, when we consider the case of an infinite
projective plane, and change the line of a flag twice, the chances are
nil that, by some miracle, we wind up back at the original flag!
This observation also helps explain the notation W_{oo}. If for
example we consider the projective plane over a finite field with q
elements, and apply the Bruhat line-changer twice, the probability is
1/q that we wind back at the original flag. Thus, interpreting the
Bruhat line-changer in a statistical way as a random variable which
changes the line of a flag at random, we arrive at the equation
[p]^2 = (1 - 1/q)[p] + (1/q)[1]
where the coefficients are probability weights. This is the quadratic
relation for the Hecke algebra attached to the symmetric group S_n
(our case was S_3, but the relation holds for general n; the group S_n
is the Coxeter group for projective space in n-1 dimensions). In the
q --> oo limit, we arrive at the Murphy relation
[p]^2 = [p],
hence the notation W_{oo} for this limiting case.
4. The enriched category picture
Under the Schubert condition (1) which we posit for buildings of type
W, a building F with distance function
d: F x F --> W_{oo}
becomes an honest-to-goodness W_{oo}-valued metric space, meaning
(following Lawvere) that it is a category enriched in the monoidal
poset W_{oo}. The composition law gives the triangle inequality
d(x, z) <= d(x, y)d(y, z)
Roughly speaking, this says that for any y, the Murphy monoid element
d(x,y)d(y,z) is a "worst-case scenario" for where z may live with
respect to x.
In fact, the Schubert condition is stronger than mere enrichment. In
general, if V is a monoidal category, then a category enriched in V
consists of a set X and a function
d: X x X --> V
together with a lax monoidal functor
V^{op} --> Set^{X x X}
v |-----> (x, y) |-> V(v, d(x, y))
into the monoidal category of endospans on X. If V is a monoidal
poset, the lax monoidal functor is valued in the monoidal poset of
binary relations:
V^{op} --> 2^{X x X}
and the lax monoidality is not an extra structure, but a property.
Now, the Schubert condition is a stronger property on a pair (F, d: F
x F --> W_{oo}), with the lax monoidality above replaced with strong
(*-)monoidality.
Equivalently, the Schubert condition says that the map
2^d: 2^{W_{oo}} --> 2^{F x F}
is a (strong) homomorphism of *-quantales. Here the domain is the
quantale of upward-closed sets of W_{oo} with respect to the sharpness
order =>, i.e., subsets S of W_{oo} such that (s in S and w <= s)
implies (w in S). The quantale multiplication is the convolution
product, defined by
ST = {x: x <= st for some s in S and t in T},
and the *-operator is defined by
S* = {s*: s in S}.
In fact, 2^{W_{oo}} is the free *-quantale generated by the *-monoid
W_{oo}^{op}.
The Schubert condition is still not as strong as the Bruhat-Tits
condition. But, we will show that the Bruhat-Tits condition is
equivalent to the property that
2^d: 2^{W_{oo}} --> 2^{F x F}
is a morphism of *-quantales which preserves the biclosed
structure. It is *this* condition which is our desired reformulation
of the notion of building: one which is clearly generalizable or
exportable to other enriched category contexts.
Let us step back and abstract a little from what we have done. Let M
be any *-monoidal poset (we could even drop the *-operator, but
let's keep it for now), and let X be any set equipped with an
"M-classification map" d: X x X --> M, generalizing the Bruhat
classification. This induces a map
2^d: 2^M --> 2^{X x X}
which interprets each upward-closed set of M as a binary relation on X.
There is a natural *-quantale structure on 2^M, and, as with any
quantale, 2^M is biclosed (in the same way that every locale is a
Heyting algebra in a unique way). We can think of the biclosed
*-quantale structure as specifying a theory, and we define a pair (X,
d) as above to be a *model* of the theory if 2^d: 2^M --> 2^{X x X} of
biclosed *-quantales.
Thus, our claim is that a W-building is precisely the same as a model
of the theory of the Murphy monoid (in this quantalized sense).
In the rest of this section, we analyze more concretely what
preservation of the biclosed structure means. This analysis works
generally for any *-monoidal poset M. Then it becomes a simple matter
to show that the Bruhat-Tits condition implies this preservation
property in the case of buildings.
Lemma: Let X be a set and let d: X x X --> M be a function into a
*-monoidal poset M (with partial order denoted =>) such that
2^d: 2^M --> 2^{X x X}
is a map of *-quantales. Then 2^d preserves the biclosed structure
iff it satisfies the extension property
(forall x, y in X) (forall w in M) (exists z in X)
d(x, y)w = d(x, z) and d(y, z) <= w.
Proof: Define the biclosure operators / and \ in a *-quantale by the
adjunction formulas
ST --> U TS --> U
-------- --------
S --> U/T S --> T\U
Then (T\U)* = U*/T*. Consequently it suffices to consider
preservation of just one biclosure operator.
Because 2^d is a *-quantale map, there is an automatic inclusion arrow
2^d(U/T) --> 2^d(U) / 2^d(T)
corresponding to
[2^d(U/T)][2^d(T)] = 2^d((U/T)T) --> 2^d(U)
and hence it suffices to analyze the case that there is an arrow in
the other direction:
2^d(U) / 2^d(T) --> 2^d(U/T).
Now, each of the functors 2^d, -/T, and --/2^d(T) has a left adjoint.
Thus, letting E_d denote the adjoint to 2^d, this class of arrows is
mated to a class of arrows
[E_d(S)]T --> E_d[S 2^d(T)] (S in 2^{X x X}, T in 2^M).
Since both sides of this arrow are cocontinuous in the separate
arguments S and T, it is necessary and sufficient to analyze the case
where S is a singleton (x, y) in X x X, and T is the upward-closed
subset U_w generated by a single element w of M (i.e., U_w = {v in M:
w => v}, which we also write as {v in M: v <= w}).
We calculate E_d((x, y)) = {u in M: d(x, y) => u}, and further that
the left-hand side [E_d(S)]T becomes simply
[E_d((x, y))]U_w = {v in M: d(x, y)w => v}
which is just the upwards-closed set generated by d(x, y)w. Since the
right-hand side of the previous display is also upwards-closed, it
becomes necessary and sufficient to analyze the condition that d(x,
y)w belongs to it.
As for the right-hand side E_d[S 2^d(T)], the relational composite
inside the brackets becomes
(x, y).2^d(U_w) = {(x, z): w => d(y, z)}
Thus the right-hand side becomes
{v in M: d(x, z) => v for some z such that w => d(y, z)}
and the condition that this contains d(x, y)w is just
exists_z d(x, z) => wd(x, y) and w => d(y, z)
which by the triangle inequality is equivalent to
exists_z d(x, z) = wd(x, y) and w => d(y, z)
as was to be shown. QED
5. Thick Buildings
7. Proofs of the theorems
Lemma 2: Let F be a set and let d: F x F --> W_{oo} be a function. The
Bruhat-Tits condition on (F, d) implies the Schubert condition.
Proof: The Schubert condition says that
d(x, x') <= s_{i(1)}...s_{i(k)}
iff there exists a chain x = x_0, x_1, ..., x_k = x' such that
d(x_{j-1}, x_j) <= s_{i(j)}
for j = 1, ..., k.
Lemma 3: The Bruhat-Tits condition on (F, d) implies that 2^d
preserves biclosed structure.
Proof: By Lemma 1 in section 4... [unfinished]
© 2007 Todd H. Trimble