# The Affine Weyl group

The visualisation below is a work-in-progress to show features of affine Weyl groups corresponding to the irreducible rank-2 root systems. Click and draw to move around, or hold shift and scroll to zoom in and out. An overview of what each option means and the particular conventions used are below.

## Definition of the affine Weyl group

Let (R \subseteq V, R^\vee \subseteq V^*) be a reduced, irreducible root system.
Each root \alpha \in R and integer k \in \bbZ defines an *affine Hyperplane* H_{\alpha, k}^\vee = \set{\mu \in V^* \mid \innprod{\mu, \alpha} = k} in the dual space V^*, and together with its corresponding coroot \alpha^\vee an *affine reflection* r_{\alpha, k}(\mu) = \mu - (\innprod{\mu, \alpha} - k)\alpha^\vee fixing H_{\alpha, k}^\vee pointwise.
Let \Aff(V^*) denote the group of invertible affine transformations of V^*; the subgroup generated by all the affine reflections r_{\alpha, k} is called the *affine Weyl group* associated to (R, R^\vee), denoted by W.
The finite Weyl group W_f is naturally a subgroup, generated by those reflections with k = 0. Hence in our setup we have W_f \subseteq W \subseteq \Aff(V^*), and the visualisation above is a picture of V^*.

*Note:* Entirely analagously there is an affine Weyl group which is a subgroup of \Aff(V), which is often also called the affine Weyl group.
If the root system (R, R^\vee) is simply-laced then these groups are isomorphic, but otherwise they differ.
The convention we have adopted is standard in the literature on Coxeter groups, for example in Bourbaki.
We warn that when looking at the literature on algebraic groups, the affine Weyl group appearing in the linkage principle is the subgroup of \Aff(V), not of \Aff(V^*).

The affine hyperplanes cut the space V^* up into disjoint simplices upon which W acts freely and transitively, hence after choosing a reference simplex \Delta we can identify an element w \in W with the simplex w \Delta. If a base has already been chosen for the underlying finite root system, then the standard choice of \Delta is the unique simplex in the dominant chamber which touches the zero vector. The walls of \Delta then are the walls H_{\alpha, 0}^\vee corresponding to the simple roots \alpha for the finite Weyl group W_f, along with the wall H_{\theta, 1}^\vee where \theta is the highest root of the finite root system. The finite simple reflections S_f together with the affine reflection r_{\theta, 1} generate the affine Weyl group W as a Coxeter group.

## Options

The *labelling* option puts a number or polynomial on top of each alcove.

*Length*labels each group element by its length l(w).*# Reduced expressions*labels each group element by the number of reduced expressions for l(w). The reduced expressions themselves are not enumerated (there can be exponentially many in the length), but rather they are only counted by noting that c(\id) = 1, and c(w) = \sum_{s \in L(w)} c(sw) where L(w) denotes the left descent set of w.*KL polynomials*labels each group element w with the Kazhdan-Lusztig polynomial h_{w, x}, where x is the selected (purple) element under the cursor. We are using the Soergel normalisation of the Hecke algebra - more details are below in the Hecke algebras section.*KL polynomials (v = 1)*labels each group element w with the Kazhdan-Lusztig polynomial h_{w, x} evaluated at v = 1.*\mu-coefficients*labels each group element w with the v^1-coefficient appearing in the Kazhdan-Lusztig polynomial h_{w, x}. These coefficients determine the structure of the cells.*AS KL polynomials*labels each dominant alcove with the antispherical Kazhdan-Lusztig polynomial n_{w, x}, where x is the element under the cursor. More details are in the antispherical modules section.

The *shading* option displays a set of elements by shading them a darker colour. For the *Bruhat*, *right weak*, and *left weak* options, the set \set{w \in W \mid w \leq x} is shaded, where x is the element under the cursor and \leq is the given partial ordering. When the *covering* option is also set, the elements that x covers are shaded in green. For the *cone type* option, the cone type T(x) = \set{w \in W \mid l(xw) = l(x) + l(w)} is shaded (or at least the part that can be computed with whatever partial internal enumeration of the Coxeter group is currently being used).

- The
*right weak*ordering is the order generated by w \leq ws whenever l(w) < l(ws). Reduced expressions for w are in bijection with maximal chains \id < \cdots < w in the right weak ordering (the same can be said about the left weak ordering). - The
*left weak*ordering is the order generated by w \leq sw whenever l(sw) < l(w). - The
*Bruhat ordering*is the order generated by w \leq wt whenever t is a reflection. A*reflection*in a general Coxeter group is a conjugate of a Coxeter generator. In the case of finite and affine Weyl groups, these “abstract” reflections are in bijection with the affine reflections generating the group.

Cells: upon choosing left, right, or two-sided cells, the cells for a limited subset of the Kazhdan-Lusztig basis are computed and shown. The cell ordering is also computed, and shown on the left.

The *NF Tree* option shows the tree associated to the chosen normal form.

The *p-canonical* option shows p-canonical basis elements for the antispherical module for select types.
After selecting a dataset from the p-canonical list, two more labelling options become available: one showing the expansion of a p-canonical basis element into the canonical basis, and another for those coefficients evaluated at v = 1.
The *# p-can in can* shows the number of nonzero terms in the expansion of each p-canonical basis element in terms of the canonical basis elements.
Unlike everything else on this page (which is calculated on-the-fly in your browser), the p-canonical datasets were calculated offline - each requiring several hours of CPU time.
The algorithm used is due to Thorge Jensen and Geordie Williamson.

## Hecke algebras

We use the “Soergel normalisation” of the Hecke algebra, which are the same as the conventions used in the book *Introduction to Soergel bimodules*.
We give a few details here so that the reader can check what conventions we are using; see Chapter 3 of *Introduction to Soergel bimodules* for a proper introduction to the Hecke algebra.

The *Hecke algebra* H = H(W, S) is a free \bbZ[v^{\pm}]-module, with a *standard basis* \set{\delta_x \mid x \in W}. The quadratic relation used is \delta_s^2 = (v^{-1} - v)\delta_s + 1, hence the right-multiplication-by-\delta_s formula for s \in S is

The *bar involution* is the \bbZ-linear map sending p(v) \delta_x to \overline{p(v) \delta_x} = p(v^{-1}) \delta_{x^{-1}}^{-1}. On generators, we have \delta_s^{-1} = \delta_s + (v - v^{-1}). The *Kazhdan-Lusztig basis* or *canonical basis* is the unique set \set{b_x \mid x \in W} \subseteq H of elements which are self-dual (fixed points of the bar involution), and furthermore satisfy the *degree bound* condition

We have b_{\id} = \delta_{\id} = 1 \in H and b_s = \delta_s + v.
The Laurent polynomials h_{y, x} are called *Kazhdan-Lusztig polynomials*.
Canonical basis elements can be calculated in a relatively straightforward fashion by using the right-multiplication formulas

where \mu(y, x) denotes the coefficient of v in h_{y, x}.

## Antispherical modules

Let I \subseteq S be a subset of the Coxeter generators, then the subgroup W_I \subseteq W generated by I is called a *parabolic subgroup* of W. The length function on (W_I, I) is equal to the restriction of the length function on (W, S) to W_I. Each right coset W_I x contains a unique *minimal-length coset representative* x_0 = \argmin_{w \in W_I x} l(w). Let {^I W} \subseteq W denote the set of minimal-length coset representatives of elements of W: they can be characterised as the elements which cannot be made shorter by left-multiplication by I:

We get a bijection of sets W_I \times {^I W} \to W by multiplying group elements, which satisfies l(uv) = l(u) + l(v) for u \in W_I and v \in {^I W}. The example we will be most interested in is when I is the subset of simple reflections of the underlying finite root system, so W_I is the usual finite Weyl group. In this case, {^I W} is the set of alcoves that lie in the dominant chamber of the finite system.

The Hecke algebra H_I = H(W_I, I) is naturally a subalgebra of the Hecke algebra H.
Let \cL = \bbZ[v^{\pm 1}] denote the ring of Laurent polynomials.
The quadratic relation implies that \set{v^{-1}, -v} are the eigenvalues for the action of right multiplication by any \delta_s upon H, hence we may define an algebra homomorphism H_I \to \cL by sending \delta_s to (-v) for s \in I.
This makes \cL into a H_I-bimodule called \cL(-v), which can be induced to a right H-module N = \cL(-v) \otimes_{H_I} H, called the *antispherical module*. The elements \set{1 \otimes \delta_x \mid x \in {^I W}} form a *standard basis* for N.

The bar involution on H induces an \bbZ-linear involution on N, by setting \overline{p \otimes h} = \overline{p} \otimes \overline{h}. We can again define a *canonical basis* of N by looking for a set \set{d_x \mid x \in {^I W}} of self-dual elements which satsify the degree bound condition

We have a right multiplication formula

which can be used to calculate the canonical basis of N, using a similar idea to the calculation of the canonical basis of H: when x < xs then d_x b_s = d_{xs} + (\text{junk}), and the junk can be identified as the elements violating the degree bound, and removed by subtracting an appropriate multiple of d_y for various y < x.

## Cells

Suppose that H is an algebra, equipped with a choice of basis \set{h_x \mid x \in W} for some indexing set W. (We will always be considering H to be the Hecke algebra, and the indexing set to be the affine Weyl group W). When multiplying a particular basis element h_w on the left by an arbitrary element of H, the product can be re-expanded in the chosen basis, yielding some terms on the right: n h_w = \sum_{z} \lambda_z h_z. Whenever h_z appears in the expansion with a nonzero coefficient, we write z \xleftarrow{L} w, which can be read informally as ”h_w produces an h_z under left multiplication”. More formally, we define the binary relation z \xleftarrow{L} w if and only if there exists some n \in H such that n h_w = \sum_{y} \lambda_y h_y with \lambda_z \neq 0.

The relation \xleftarrow{L} is reflexive (z \xleftarrow{L} z for all z), but unless the basis h_x is extremely special it will not be transitive.
We take its transitive closure by declaring that z \leq_L w if there exists some path z \xleftarrow{L} \cdots \xleftarrow{L} w.
By construction \leq_L is reflexive and transitive and so is a *preorder* (a preorder is like a partial order, but missing the axiom that x \leq y and y \leq x implies x = y).
By taking its strongly connected components (or the strong components generated by \xleftarrow{L}), we introduce equivalence classes called *left cells*, and a partial order \leq_L on those left cells.

Analagously, we can define the binary relation z \xleftarrow{R} w for when h_z appears in a product like h_w m, and z \xleftarrow{LR} w for when h_z appears in a product like n h_w m. (The \xleftarrow{LR} relation is the union of the \xleftarrow{L} and \xleftarrow{R} relations). And analagously we get right cells, and two-sided cells.

In the Hecke algebra, the standard basis does not produce interesting cells. Every standard basis element \delta_x is invertible, and hence produces the relation x \xleftarrow{L} y for all x, y \in W, and hence a single cell containing every element. On the other hand, the cells defined by the KL basis is very interesting. We give a short account of how the cells are computed, after all the KL basis elements have been computed.

For y, x \in W let \mu(y, x) be the coefficient of v in the polynomial h_{y, x}. Then we have the following formulae for right and left multiplication by the canonical basis element b_s corresponding to a simple generator:

In order to generate the preorder \leq_L, it is enough to consider left multiplication by some generating set of the algebra. The generating set we choose are the KL basis elements \set{b_s \mid s \in S} corresponding to the simple reflections, since we have those nice formulae above showing how such products expand back into the KL basis. Then it is simply a matter of running through, for all elements y \in W, and for all s \in S such that ys > y, the nonzero \mu(z, y) coefficients, checking the additional condition that zs < z. If zs < z and \mu(z, y) \neq 0, then we add an edge z \leftarrow y to a directed graph. After collecting all edges, we run a beautiful algorithm due to Robert Tarjan to generate the strong components of the graph: these are the cells. This algorithm outputs the cells in a topological ordering, so the “condensed graph” (the directed acyclic graph where vertices are cells, and edges are induced by the edges on the original graph) can be easily generated. The transitive closure of this condensed graph is the cell ordering. To display the cell ordering however, we take the transitive reduction of the graph: this deletes edges until all we are left with are covering relations.

## Normal forms

After fixing an order on the generating set S, there are two commonly used *normal forms* for elements of a Coxeter group W. Clearly a normal form should be a reduced expression, but which one?

- The
`ShortLex`

normal form for w \in W is the lexicographically least reduced word in the generators representing w. If \mathtt{ShortLex}(w) = (s_1, \ldots, s_n), then s_1 is the “smallest possible starting letter” for w, in that s_1 is the least generator s such that l(s w) < l(w). Furthermore, (s_2, \ldots, s_n) is the normal form for s_1 w. Every suffix of a normal form is again a normal form. - The
`InvShortLex`

normal form for w \in W is (s_1, \ldots, s_n), where s_n is the “smallest possible ending letter” for w. The`InvShortLex`

language (as a formal language contained in S^*) is the reverse of the`ShortLex`

language. We have the equality \mathtt{Reverse}(\mathtt{InvShortLex}(w)) = \mathtt{ShortLex}(w). Every prefix of a normal form is again a normal form.

Since any prefix of a normal form is again a normal form, the normal forms define a tree structure on the group, with an edge x \xrightarrow{s} y iff NF(x) \cdot s = NF(y) as words.

## The p-dialated affine Weyl group

Recall that the affine Weyl group W \subseteq \Aff(V^*) is generated by the reflections r_{\alpha, k} where \alpha is a finite root, and k is an integer.
For p > 0, the subgroup generated by the r_{\alpha, k} with k \in p \bbZ is called the *p-dialated affine Weyl group* W_p \subseteq W.
In a fractal-like way, it is both a subgroup of W (when both W and W_p are viewed as sitting inside \Aff(V^*)), and it is abstractly *isomorphic* to W.

W is generated by the simple reflections s_1, \ldots, s_n (which are all linear reflections), and the affine reflection s_0 = r_{\theta, 1} where \theta is the highest root of the underlying finite root system. W_p is generated by the same linear reflections s_1, \ldots, s_n, and the affine reflection s_0^{(1)} = r_{\theta, p}. These generators give the same Coxeter presentation, and so the isomorphism W \to W_p may be defined by sending s_1 \mapsto s_1, \ldots, s_n \mapsto s_n, and s_0 \mapsto s_0^{(1)}.

Now the fractal part: we want to define a homomorphism W \mapsto W_p \injto W which embeds W inside of itself. (This is because to compute using W and W_p we really treat them as finitely presented groups, in which they look exactly the same). In order to compute this map, we need to know how to express the affine reflection s_0^{(1)} in terms of (s_1, \ldots, s_n, s_0). Purely by the definition of r_{\theta, k} we can see that s_0 = t_{\theta^\vee} s_\theta where t_\mu \colon V^* \to V^* is translation by \mu \in V^*. Similarly we have s_0^{(1)} = t_{p \theta^\vee} s_\theta. So if we know how to express s_\theta in terms of the finite simple reflections s_1, \ldots, s_n, then we can get t_{\theta^\vee} in terms of the affine simple generators and we will then have s_0^{(1)} = (t_{\theta^\vee})^p s_\theta.

In order to find s_\theta we use the general fact that w r_\alpha w^{-1} = r_{w \alpha} (which holds in any reflection-faithful root system).
When constructing the root system we indexed roots by increasing *depth* (how far, in terms of reflections, they are away from being simple), and recorded this data in a reflection table.
This leads to a simple process for finding a sequence of simple reflections such that x_n \cdots x_2 x_1 \theta = \alpha_s for some simple root \alpha_s, then \theta = x_1 x_2 \cdots x_n \alpha_s and hence letting w = x_1 \cdots x_n we have r_\theta = r_{w \alpha_s} = w s w^{-1}, and so t_{\theta^\vee} = s_0 w s w^{-1}.
Finally we have s_0^{(1)} = t_{p \theta^\vee} s_\theta = (s_0 s_\theta)^p s_\theta = (s_0 s_\theta)^{p - 1} s_0

What would also be handy to be able to calculate is the *factorisation map* W \to W_p \times {^p W}, where {^p W} is the set of minimal coset representatives (which behaves well by general reflection subgroup theory).
Here we can use a similar idea to parabolic subgroups, based on the fact (still true for general reflection subgroups) that each coset W_p x has a unique element of minimal length (with length as measured in W).
Therefore to factorise an element w, try to multiply on the left by any of the subgroup generators (s_1, \ldots, s_n, s_0^{(1)}) and see if the length goes down.
Eventually we get to some product x_k \cdots x_1 w of minimal length in the coset W_p w, and we have w = (x_1 \cdots x_k)(x_k \cdots x_1 w), a product of elements of W_p with a minimal coset rep.
(In fact, during this algorithm we can treat any x_i = s_0^{(1)} as a simple generator for the left factor, and a product of simple generators for the right factor, which means we can treat the left generator as either being inside W or inside W_p, implicitly using the isomorphism W \to W_p).

(In fact one thing is not obvious from the description above: why can we necessarily move to a minimal-length element only by multiplication on the left by the simple generators of W_p? Clearly we cannot choose any generating set of W_p. The reason this is working is because the set of generators for W_p is canonical with respect to the reflection subgroup W_p \subseteq W …)

It is not hard to see that the cardinality of {^p W} is p^{|S|}: the fundamental alcove and the p-dialated fundamental alcove are similar simplicies in an |S|-dimensional space, therefore the ratio of their volumes is p^{|S|}.

## How alcoves are drawn

The affine fundamental chamber is the open simplex generated by \Delta = (\Lambda_1^\vee, \Lambda_2^\vee, \Lambda_3^\vee). Using the usual formula for the simple reflections on the coweight basis, this chamber gets moved around generating other chambers w \Delta for w \in W. In order to draw triangles in the plane, we need to take each generating vector v \in \Delta of the simplex, treat it as a projective line \bbR v, and intersect with the hyperplane \innprod{-, \delta} = 1. This is done by converting from the (\Lambda_1^\vee, \Lambda_2^\vee, \Lambda_3^\vee) basis into the (\varpi_1^\vee, \varpi_2^\vee, \delta^*) basis, then doing the usual projectivisation thing where the vector is normalised so that the last coordinate is 1. (This works because \innprod{\varpi_1^\vee, \delta} = \innprod{\varpi_2^\vee, \delta} = 0). The basis conversion map is

Note that in this approach the coordinates of the simplex start as basis vectors (1, 0, 0), (0, 1, 0), and (0, 0, 1). It’s only after basis conversion and scaling that we end up with (1/a_1, 0, 1), (0, 1/a_2, 1), (0, 0, 1).

## Geometry

We will model the 2D Euclidean space for the affine Weyl group inside the 3D coweight space of the affine root system, living inside the plane \innprod{-, \delta} = 1. We use the adjoint realisation of the affine root datum, so the coweight space is the space V^* with basis (\Lambda_1^\vee, \Lambda_2^\vee, \Lambda_3^\vee) of affine fundamental weights, and the weight space V has basis (\alpha_1, \alpha_2, \alpha_3) of simple roots. These are in perfect pairing: \innprod{\Lambda_i^\vee, \alpha_j} = \delta_{ij}.

An alternative basis of V is the basis (\alpha_1, \alpha_2, \delta), with \alpha_3 = \delta - \widetilde{\alpha}, where \widetilde{\alpha} = a_1 \alpha_1 + a_2 \alpha_2 is the highest root of the finite root system generated by the two finite roots. The corresponding alternative basis of V^* is (\varpi_1^\vee, \varpi_2^\vee, \delta^*) which is a dual basis to (\alpha_1, \alpha_2, \delta), and the relation to the old basis is

### Detecting cursor position

Given a point (x_1, x_2) inside a triangle on the screen, which open simplex w\Delta does it correspond to? We embed this point into the affine space by adding \delta^*, then rewrite in fundamental coweight coordinates

which gives us a point on the interior of an affine chamber. This chamber is the dominant chamber if all coordinates are nonnegative, otherwise some coordinate (say i) is negative, and the simple reflection s_i can be applied to move the point to a smaller length chamber. Eventually we reach the dominant chamber, and the sequence of reflections applied gives us a reduced word in the Weyl group generators for w. .

### Drawing

We only actually need to draw the coloured walls in order to generate “the look” of the affine Weyl group. This is easy enough: if w\Delta = (v_1, v_2, v_3), then the right-multiplication-by-s_1-wall is the segement [v_2, v_3], etc. We may also need to shade various simplices.

There are three different coordinate systems in play:

where the last coordinate system is “screen coordinates” in pixels. The coordinates of a simplex never change in the first two bases, but they will change in the last basis as we zoom and pan around.