CharLiePy¶

CharLiePy (Characters of Lie type groups in Python) is a python package which implements algorithms to carry out symbolic computations with Coxeter groups and related mathematical structures. The ultimate goal of CharLiePy is to develop a custom platform for carrying out computations with finite reductive groups and their characters. It may be considered as a Python version of the original CHEVIE package which was written in GAP3 and MAPLE. This was inspired by the Python package PyCox [Gec12] developed by Meinolf Geck. The development version of CHEVIE is currently maintained by Jean Michel.

CharLiePy is a mix of high level Python code and handwritten C extensions. For instance, following GAP, permutations are implemented as arrays in C to permit faster caluclations than are possible in direct Python. By building from the ground up it is possible to make design choices that are specifically tailored to working with finite reductive groups. For instance, unlike GAP, permutations on less than 255 points are stored as 8-bit integers. This saves memory when working with the Weyl group of \(\mathsf{E}_8\), which has a natural permutation representation on 240 points.

The focus of CharLiePy is narrower than that of CHEVIE, in that we do not anticipate working with the more general class of complex reflection groups.

Why Python?¶

One of the original reasons for choosing Python as the language for CharLiePy is the success of the Sage project. In particular, CharLiePy may be used in Sage by simply importing CharLiePy in an interactive session. Here are some additional reasons:

Python is very popular with the wider scientific community (see for instance the SciPy project).
It is easy to encorporate C extensions into Python, thus allowing one to obtain speed advantages when needed.
As Python is a widely used modern programming language, anyone learning to use CharLiePy for research will simultaneously gain a useful transferable skill.
The Python language is syntactically similar to the GAP3 language, on which the original CHEVIE package was based. Thus it should not be difficult for people to switch between the two languages.

References¶

G¶

[Gec12]

M. Geck, PyCox: computing with (finite) Coxeter groups and Iwahori-Hecke algebras, LMS J. Comput. Math. 15 (2012), 231-256.

[GKP00]

M. Geck, S. Kim and G. Pfeiffer, Minimal length elements in twisted conjugacy classes of finite Coxeter groups, J. Algebra 229 (2000), no.2, 570-600.

[GM97]

M. Geck and J. Michel, “Good” elements in finite Coxeter groups and representations of Iwahori–Hecke algebras, Proc. London Math. Soc. (3) 74 (1997), no. 2, 275-305.

[GP00]

M. Geck and G. Pfeiffer, Characters of finite Coxeter groups and Iwahori-Hecke algebras, vol. 21, London Mathematical Society Monographs. New Series, New York: The Clarendon Press Oxford University Press, 2000.

J¶

[JK81]

G. James and A. Kerber, The representation theory of the symmetric group, vol. 16, Encyclopedia of Mathematics and its Applications, Addison-Wesley Publishing Co., Reading, Mass., 1981.

L¶

[Lus85]

G. Lusztig, Character Sheaves I, Adv. in Math. 56 (1985), no. 3, 193-237; Character Sheaves II, Adv. in Math. 57 (1985), no. 3, 226-265; Character Sheaves III, Adv. in Math. 57 (1985), no. 3, 226-315; Character Sheaves IV, Adv. in Math. 59 (1986), no. 1, 1-63; Character Sheaves V, Adv. in Math. 61 (1986), no. 2, 103-155.

Glossary¶

Coxeter Groups¶

Cartan matrix

A matrix \(C = (c_{ij})\), with \(1 \leqslant i,j \leqslant n\) and \(c_{ij} \in \mathbb{R}\), such that:

for \(i\neq j\) we have \(c_{ij} \leqslant 0\)

\(c_{ij} \neq 0\) if and only if \(c_{ji} \neq 0\)

\(c_{ii} = 2\)

for \(i \neq j\) we have \(c_{ij}c_{ji} = 4\cos^2(\pi/m_{ij})\) where \(m_{ij} \geqslant 2\) or \(m_{ij} = \infty\).

Coxeter group

A group \(W\) containing a generating set \(\mathbb{S}\) such that \((W,\mathbb{S})\) is a Coxeter system.

Coxeter matrix

A symmetric matrix \(M = (m_{ij})\), with \(1 \leqslant i,j \leqslant n\) and \(m_{ij} \in \mathbb{N} \cup \{\infty\}\), such that

\(m_{ii} = 1\) for all \(i\),

\(m_{ij} > 1\) for all \(i \neq j\).

Coxeter system

A pair \((W,\mathbb{S})\) such that \(W\) is a group and \(\mathbb{S} \subset W\) is a finite generating set such that the defining relations for \(W\) are just relations of the form \(s^2 = 1\) and \((st)^{m_{st}} = 1\), where \(s \neq t \in \mathbb{S}\) and \(m_{st} = m_{ts} > 1\). If, for two generators \(s,t \in \mathbb{S}\) there exists no \(i \in \mathbb{N}\) such that \((st)^i = 1\) then as a convention we set \(m_{st} = \infty\).

length function

For a Coxeter system \((W,\mathbb{S})\) this is the function \(\ell : W \to \mathbb{N}\) defined by setting \(\ell(1) = 0\) and \(\ell(w) = r\) if \(s_1\cdots s_r\) is a reduced expression for \(w \neq 1\).

reduced expression

Given a Coxeter system \((W,\mathbb{S})\) and an element \(w \in W\) this is a word \(w = s_1\cdots s_r\) in the generators \(\mathbb{S}\) such that any other word \(w = s_1\cdots s_{r'}\) satisfies \(r' \geqslant r\).

Representation Theory¶

generic degree polynomial

Assume \(W\) is a finite Coxeter group and \(V\) is the natural module for \(W\).

j-induction

For any coxeter group \(W\) and subgroup \(H\) this is the following map \(j_H^W : \mathrm{Cent}(H) \to \mathrm{Cent}(W)\) taking class functions on \(H\) to class functions on \(W\). Denote by \(n_{\chi,\rho}\) the multiplicity of \(\rho \in \mathrm{Irr}(W)\) in the usual induced character \(\mathrm{Ind}_H^W(\chi)\). Then

\[j_H^W(\chi) = \sum_{\rho} n_{\chi,\rho} \rho\]

where the sum is taken over all \(\rho \in \mathrm{Irr}(W)\) such that \(b_{\rho} = b_{\chi}\), where \(b_{\chi}\) denotes the b-invariant of \(\chi\). See 5.2 of [GP00] for a generalisation of this to all finite groups.

preferred extension

Assume \((W,\mathbb{S})\) is a Coxeter system such that \(W\) is a Weyl group and \(\phi : W \to W\) is an automorphism stabilising \(\mathbb{S}\). Every \(\phi\)-invariant irreducible character of \(W\) may be extended to an irreducible character of the semidirect product \(W \rtimes \langle \phi \rangle\). This term refers to the extension defined by Lusztig in 17.2 of [Lus85].

Schur element

If \(\chi\) is an irreducible character of an Iwahori-Hecke algebra \(H_{\mathcal{A}}(W,\mathbb{S},\{a_s,b_s \mid s \in \mathbb{S}\})\) then the associated Schur element \(c_{\chi}\) is the unique element for which the following relation holds

\[\begin{split}\sum_{\chi} \chi(T_w)c_{\chi}^{-1} = \begin{cases} 1 &\text{if }w=1,\\ 0 &\text{if }w\neq 1, \end{cases}\end{split}\]

where the sum runs over all the irreducible characters of the algebra.

sign character

Given a Coxeter system \((W,\mathbb{S})\) this is the homomorphism \(\mathrm{sgn} : W \to \mathbb{C}^{\times}\) obtained by setting \(\mathrm{sgn}(w) = (-1)^{\ell(w)}\) where \(\ell : W \to \mathbb{N}\) is the length function.

Hecke Algebras¶

Iwahori-Hecke algebra

Fix a Coxeter system \((W,\mathbb{S})\) and a commutative ring \(\mathcal{A}\) with 1. Furthermore let us assume that \(\{a_s,b_s \mid s \in \mathbb{S}\} \subset \mathcal{A}\) are such that \(a_s = a_t\) and \(b_s = b_t\) whenever \(s,t \in \mathbb{S}\) are conjugate in \(W\). The Iwahori-Hecke algebra \(H_{\mathcal{A}}(W,\mathbb{S},\{a_s,b_s \mid s \in \mathbb{S}\})\) is the \(\mathcal{A}\)-algebra generated by \(\{T_s \mid s \in \mathbb{S}\}\) and satisfying the relations

\[\begin{split}\begin{cases} T_s^2 = a_sT_1 + b_sT_s &\text{for }s\in \mathbb{S}\\ T_sT_tT_s \cdots = T_tT_sT_t \cdots &\text{for }s\neq t\text{ and with }m_{st}\text{ factors on each side}. \end{cases}\end{split}\]

Here \(m_{st}\) is as in the definition of Coxeter system. This algebra is in fact free as an \(\mathcal{A}\)-module with basis given by \(\{T_w \mid w \in W\}\). It also satisfies the multiplication relation

\[\begin{split}T_sT_w = \begin{cases} T_{sw} &\text{if }\ell(sw) > \ell(w)\\ a_sT_{sw} + b_sT_w &\text{if }\ell(sw) < \ell(w) \end{cases}\end{split}\]

for all \(s \in \mathbb{S}\) and \(w \in W\), where \(\ell\) is the length function of \((W,\mathbb{S})\).

generic Iwahori-Hecke algebra

Fix a Coxeter system \((W,\mathbb{S})\) and indeterminates \(\{u_s \mid s \in \mathbb{S}\}\) over \(\mathbb{C}\) such that \(u_s = u_t\) whenever \(s,t \in \mathbb{S}\) are conjugate in \(W\). Let \(\mathcal{A} = \mathbb{Z}[u_s^{\pm} \mid s \in \mathbb{S}]\) and assume that there exists a ring homomorphism \(\mathcal{A} \to \mathbb{Z}\) which sends \(u_s \to 1\) for all \(s \in \mathbb{S}\). Then the generic Iwahori-Hecke algebra is defined to be the Iwahori-Hecke algebra \(H_{\mathcal{A}}(W,\mathbb{S},\{u_s,u_s-1 \mid s \in \mathbb{S}\})\).

Combinatorics¶

bipartition

A pair of ordered partitions.

partition

A finite weakly decreasing sequence of non-zero natural numbers.

dual partition

If \(\lambda = (\lambda_1,\dots,\lambda_r)\) is a partition of \(n\) then the dual partition is the partition of \(n\) obtained in the following way. First let \(\lambda' = (\lambda_1',\dots,\lambda_n')\) be the sequence obtained by setting

\[\lambda_i' = |\{\lambda_j \mid 1 \leqslant j \leqslant n \text{ and }\lambda_j \geqslant i\}|.\]

Then \(\lambda^*\) is obtained from \(\lambda'\) by removing all entries equal to zero.

Coxeter Cosets¶

Let us assume that \((W,\mathbb{S})\) is a Coxeter system.

Definition

We say \(\phi : W \to W\) is a Coxeter automorphism of \(W\) if \(\phi(\mathbb{S}) = \mathbb{S}\).

Note that such an automorphism implicitly depends upon our choice of generating set \(\mathbb{S}\). If \(W\) is finite then all such sets \(\mathbb{S}\) are conjugate, hence in this case any automorphism is a Coxeter automorphism for some choice of \(\mathbb{S}\).

Given such a Coxeter automorphism we may consider the semidirect product \(\widetilde{W} = W \rtimes \langle \phi \rangle \cong \langle W, \phi \rangle\), where \(\langle\phi\rangle\) is the cyclic subgroup of the automorphism group \(\mathrm{Aut}(W)\) generated by \(\phi\). Of particular importance to representation theory is the coset

\[W\phi = \{(w,\phi) \mid w \in W\} \subset \widetilde{W},\]

which we call a Coxeter coset. Below we will identify \(W\) with its natural image \(\{(w,1) \mid w \in W\}\) in \(\widetilde{W}\).

In CharLiePy we have implemented general algorithms for working with Coxeter cosets, which we describe in this section. Mainly these algorithms deal with conjugacy classes and irreducible characters.

Warning

For the moment these functions only support the case where \(W\) is a finite Coxeter group.

The following class implements Coxeter cosets in CharLiePy.

Conjugacy Classes¶

Let us recall that the automorphism \(\phi\) induces a natural equivalence relation on the group \(W\), which we call \(\phi\)-conjugacy. In particular, we say two elements \(x,y \in W\) are \(\phi\)-conjugate if there exists an element \(z \in W\) such that

\[x = z^{-1}y\phi(z).\]

The equivalence classes under this relation are known as the \(\phi\)-conjugacy classes of \(W\), which we denote by \(H^1(\phi,W)\).

Definition

We say \(C \subset W\phi\) is a \(\phi\)-conjugacy class if any one of the following equivalent conditions is satisfied:

\(C\) is a \(W\)-orbit under the natural conjugation action of \(W\) on \(W\phi\).
\(C\) is a conjugacy class of \(\widetilde{W}\) contained in the coset \(W\phi\).
the set \(\{w \in W \mid (w, \phi) \in C\}\) is a \(\phi\)-conjugacy class of \(W\).

We now consider how we may reduce the problem of determining \(\phi\)-conjugacy classes to the case where \(W\) is irreducible. First let us write \(W\) as a direct product \(W^{(1)} \times \cdots \times W^{(r)}\) such that each \(W^{(i)}\) is an orbit of \(\phi\) acting on the irreducible factors of \(W\). We will denote by \(\phi^{(i)}\) the restriction of \(\phi\) to the orbit \(W^{(i)}\) then the following is obvious

Lemma

The natural product map

\begin{align*} W^{(1)} \times \cdots \times W^{(r)} &\to W\\ (w_1,\dots,w_r) &\mapsto w_1\cdots w_r \end{align*}

induces a bijection

\[H^1(\phi^{(1)},W^{(1)}) \times \cdots H^1(\phi^{(r)},W^{(r)}) \to H^1(\phi, W)\]

In other words \(W^{(i)} = W^{(i)}_1 \times \cdots \times W^{(i)}_{m_i}\) and \(\phi\) cyclically permutes the factors \(W^{(i)}_j\).

The following function will produce the \(\phi\)-conjugacy classes of any Coxeter coset.

Data Book¶

Many algorithms in CharLiePy reduce a problem to the case of irreducible root systems and then run specialised algorithms for that particular case. Thus much of the data in CharLiePy depends upon the irreducible root systems.

In this section of the documentation we keep track of our assumptions and conventions for each irreducible type. For example, here it is described our conventions for the labellings of irreducible characters and conjugacy classes of these groups.

The sections are listed using the familiar classification of irreducible root systems. A number preceeding a type denotes that we consider an automorphism of the root system of that order.

Type \(\mathrm{A}_n\)¶

Throughtout \((W,\mathbb{S})\) will denote an irreducible Coxeter system of type \(\mathrm{A}_n\). We will also denote by \(\Phi\) a root system whose associated reflection group is \(W\) and by \(\Delta \subset \Phi^+ \subset \Phi\) a set of simple and positive roots respectively.

Root System¶

One may realise the indecomposabe root system of type \(\mathrm{A}_n\) in the real vector space

\[V = \{(x_1,\dots,x_n) \mid x_1+\cdots+x_n = 0\} \subset \mathbb{R}^n.\]

In the following table we assume that \(\{e_1,\dots,e_n\}\) denotes the standard basis of \(\mathbb{R}^n\) (i.e. \(e_i = (0,\dots,0,1,\dots,0)\) with 1 occurring in the ith position).

\(\Phi\)	\(\{e_i - e_j \mid i \neq j, 1 \leqslant i,j \leqslant n+1\}\)
\(\Phi^+\)	\(\{e_i - e_j \mid 1 \leqslant i < j \leqslant n+1\}\)
\(\Delta\)	\(\{\alpha_1 = e_1 - e_2,\dots, \alpha_n = e_n - e_{n+1}\}\)

The Cartan matrix of the root system is

\[\begin{split}C = \begin{bmatrix} 2 & -1 & 0 & 0 & \cdots & 0\\ -1 & 2 & -1 & 0 & \cdots & 0\\ 0 & -1 & 2 & -1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ 0 & \cdots & 0 & -1 & 2 & -1\\ 0 & \cdots & 0 & 0 & -1 & 2 \end{bmatrix}.\end{split}\]

Coxeter Group¶

In the following table we denote by \(s_i\) the reflection of the corresponding simple root \(\alpha_i\) for \(i \in \{1,\dots,n+1\}\).

\(W\)	\(\mathfrak{S}_{n+1}\)
\(s_i\)	\((i, i+1)\)
\(\|W\|\)	\((n+1)!\)

Here \(\mathfrak{S}_{n+1}\) denotes the symmetric group on \(\{1,\dots,n+1\}\) and \((i,i+1) \in \mathfrak{S}_{n+1}\) is a basic transposition. The Coxeter matrix of the Coxeter system is

\[\begin{split}M = \begin{bmatrix} 1 & 3 & 2 & 2 & \cdots & 2\\ 3 & 1 & 3 & 2 & \cdots & 2\\ 2 & 3 & 1 & 3 & \cdots & 2\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ 2 & \cdots & 2 & 3 & 1 & 3\\ 2 & \cdots & 2 & 2 & 3 & 1 \end{bmatrix}.\end{split}\]

Conjugacy Classes¶

The cycle type of any element of the symmetric group \(\mathfrak{S}_{n+1}\) gives a partition of \(n+1\) which uniquely determines the conjugacy class containing the element (see 1.2 of [JK81]). To each partition \(\lambda \vdash n+1\) we denote by \(w_{\lambda}\) a very good representative of the corresponding conjugacy class. This may be constructed in the following way (see 2.1 of [GM97]).

If \(\lambda = (\lambda_1,\dots,\lambda_r)\) then there is a corresponding standard parabolic subgroup \(W_{\lambda}\) of \(W\) isomorphic to \(\mathfrak{S}_{\lambda_1} \times \cdots \times \mathfrak{S}_{\lambda_r}\). The element \(w_{\lambda}\) may then simply be taken as a Coxeter element of \(W_{\lambda}\). In particular we have \(w_{\lambda} = w_1\cdots w_r\) where

\[w_i = s_{\lambda_1+\cdots+\lambda_{i-1}+1}\cdots s_{\lambda_1+\cdots+\lambda_i}\]

Let us now write the partition \(\lambda\) as \((1^{a_1},\dots,n^{a_n})\) for some non-negative integers \(a_i\), then we have the centraliser order is given by

\[|C_W(w_{\lambda})| = \prod_{i=1}^n i^{a_i}a_i.\]

(see 1.2.15 of [JK81]).

Irreducible Characters¶

There is a bijection between the set of partitions of \(n+1\) and the irreducible characters of \(W\) which may be constructed as follows. For each partition \(\lambda\) we consider the standard parabolic subgroup \(W_{\lambda^*}\) of \(W\) isomorphic to \(\mathfrak{S}_{\lambda_1^*} \times \cdots \times \mathfrak{S}_{\lambda_r^*}\), where \(\lambda^* = (\lambda_1^*, \dots, \lambda_r^*)\) is the dual partition of \(\lambda\). The j-induction of the sign character of \(W_{\lambda^*}\)

\[\chi_{\lambda} = j_{W_{\lambda^*}}^W(\mathrm{sgn})\]

is then an irreducible character of \(W\) (see 5.4.5 of [GP00]). The map \(\lambda \mapsto \chi_{\lambda}\) then gives the required bijection.

Type \({}^2\mathrm{A}_n\)¶

Coxeter Coset¶

There is a unique non-trivial automorphism \(\phi : W \to W\) stabilising the set of Coxeter generators \(\mathbb{S}\). It may be realised as conjugation by the longest element \(w_0 \in W\).

\(\phi\)-Conjugacy Classes¶

As \(\phi\) can be realised as an inner automorphism the \(\phi\)-conjugacy classes of \(W\) are simply the conjugacy classes of \(W\). In particular, the map \(w \mapsto ww_0\) defines a bijection between the conjugacy classes and \(\phi\)-conjugacy classes of \(W\) (see 2.9 of [GKP00]). The map

\[\lambda \mapsto w_{\lambda} \mapsto w_{\lambda}w_0\]

gives a bijection between the partitions of \(n+1\) and the \(\phi\)-conjugacy classes of \(W\). Here \(w_{\lambda}\) is as in Conjugacy Classes.

To construct minimal length representatives of the \(\phi\)-conjugacy classes we will need to work in the symmetric group \(\mathfrak{S}_{n+1}\). Let \(\lambda\) be a partition of \(n+1\). We will denote by \(\mu = (\mu_1,\dots,\mu_r)\) a maximal composition obtained from \(\lambda\) by rearranging the entries. In other words, there exists \(k\) \((0 \leqslant k \leqslant r)\) such that \(\mu_1,\dots,\mu_k\) are even numbers (in any order) and \(\mu_{k+1},\dots,\mu_r\) are odd numbers such that \(\mu_{k+1} \geqslant \cdots \geqslant \mu_r\).

Now, to \(\mu\) we define an element \(\sigma_{\mu} \in \mathfrak{S}_{n+1}\) as follows. Consider the list \((a_1,\dots,a_{n+1})\) with \(a_{2i-1} = i\) and \(a_{2i} = n+1 - (i-1)\) for all \(1 \leqslant i \leqslant n+1\) then we set

\[\sigma_{\mu} = \sigma_{\mu_1}\sigma_{\mu_2}\cdots\sigma_{\mu_r}\]

where \(\sigma_{\mu_i}\) is the \(\mu_i\)-cycle given by

\[\sigma_{\mu_i} = (a_{\mu_1+\cdots+\mu_{i-1}+1}, a_{\mu_1+\cdots+\mu_{i-1}+2},\dots, a_{\mu_1+\cdots+\mu_{i-1}+\mu_i}).\]

By Theorem 3.3 of [GKP00] we have \(\sigma_{\mu}w_0\) is an element of minimal length in its \(\phi\)-conjugacy class. From this we obtain a reduced expression for this element by applying Algorithm A from pg. 9 of [GP00].

Warning

It is an open problem to determine whether these minimal length representatives are good in the sense of Definition 5.3 of [GKP00].

Irreducible Characters¶

As \(\phi\) can be realised as an inner automorphism we have all irreducible characters of \(W\) are \(\phi\)-stable. Thus the irreducible characters of the coset \(W\phi\) are labelled by the partitions of \(n+1\). Each such irreducible character is obtained by restricting an extension \(\tilde{\chi}_{\lambda}\) of \(\widetilde{W} = W \rtimes \langle \phi \rangle\) to the coset \(W\phi\). Here we choose Lusztig’s preferred extension. In particular, if \(E\) is the simple module affording \(\chi_{\lambda}\) then \(\phi\) acts on \(E\) as \((-1)^{a_{\lambda}}w_0\) where \(a_{\lambda}\) is the a-invariant of \(\chi_{\lambda}\).