## Standard Lyndon bases of Lie algebras and enveloping algebras

Arun Ram

Department of Mathematics and Statistics

University of Melbourne

Parkville, VIC 3010 Australia

aram@unimelb.edu.au

Last updated: 19 May 2015

This is an excerpt of the paper *Standard Lyndon bases of Lie algebras and enveloping algebras* by Pierre Lalonde Arun Ram.

The first author's research was supported by FCAR and NSERC grants. The second author's research was partially supported by a National
Science Foundation Postdoctoral Fellowship.

## Finite-dimensional simple Lie algebras

In this section we shall compute the standard Lyndon words corresponding to the finite dimensional simple Lie algebras over $\u2102\text{.}$
Each such algebra is determined by a Cartan matrix $C$ with integer entries $\u27e8{\alpha}_{i},{\alpha}_{j}\u27e9,$
$1\le i,j\le n\text{.}$ A list of these Cartan matrices
can be found in [Bou1981] pp. 250-275. We shall use the Bourbaki conventions for numbering.

Fix a Cartan matrix $C$ corresponding to a finite dimensional simple Lie algebra. Let
$$A=\{{x}_{1},{x}_{2},\dots ,{x}_{n},{h}_{1},{h}_{2},\dots ,{h}_{n},{y}_{1},{y}_{2},\dots ,{y}_{n}\},$$
and let $J$ be the ideal of Serre relations in $\text{Lie}\left(A\right),$
i.e., the ideal generated by the elements
$$\begin{array}{cc}[{h}_{i},{h}_{j}]\phantom{\rule{2em}{0ex}}(1\le i,j\le n),& \text{(S1)}\\ [{x}_{i},{y}_{i}]-{h}_{i},\phantom{\rule{2em}{0ex}}[{x}_{i},{y}_{i}]\phantom{\rule{1em}{0ex}}\text{if}\phantom{\rule{1em}{0ex}}i\ne j,& \text{(S2)}\\ [{h}_{i},{x}_{j}]-\u27e8{\alpha}_{j},{\alpha}_{i}\u27e9{x}_{j},\phantom{\rule{2em}{0ex}}[{h}_{i},{y}_{j}]+\u27e8{\alpha}_{j},{\alpha}_{i}\u27e9{y}_{j},& \text{(S3)}\\ {\left(\text{ad}\hspace{0.17em}{x}_{i}\right)}^{-\u27e8{\alpha}_{j},{\alpha}_{i}\u27e9+1}\left({x}_{j}\right)\phantom{\rule{2em}{0ex}}(i\ne j),& \left({S}_{ij}^{+}\right)\\ {\left(\text{ad}\hspace{0.17em}{y}_{i}\right)}^{-\u27e8{\alpha}_{j},{\alpha}_{i}\u27e9+1}\left({y}_{j}\right)\phantom{\rule{2em}{0ex}}(i\ne j)\text{.}& \left({S}_{ij}^{-}\right)\end{array}$$
Here ${\left(\text{ad}\hspace{0.17em}a\right)}^{k}\left(b\right)=[a,[a,[a,\dots ,[a,b]]]]\text{.}$
Let $X=\{{x}_{1},{x}_{2},\dots ,{x}_{n}\}$
be ordered by ${x}_{1}<{x}_{2}<\cdots <{x}_{n},$
and let ${J}^{+}$ be the Lie ideal in $\text{Lie}\left(X\right)$
generated by the relations $\left({S}_{ij}^{+}\right)\text{.}$
Let $Y=\{{y}_{1},{y}_{2},\dots ,{y}_{n}\},$
${y}_{1}<\cdots <{y}_{n},$ and let ${J}^{-}$
be the Lie ideal in $\text{Lie}\left(Y\right)$ generated by the relations
$\left({S}_{ij}^{-}\right)\text{.}$ Define
$$\U0001d524=\text{Lie}\left(A\right)/J,\phantom{\rule{2em}{0ex}}{\U0001d52b}^{+}=\text{Lie}\left(X\right)/{J}^{+},\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}{\U0001d52b}^{-}=\text{Lie}\left(Y\right)/{J}^{-}\text{.}$$

Let ${\alpha}_{i}$ be independent vectors. The ${\alpha}_{i}$ are called the *simple roots*.
The *root lattice* is the lattice $Q=\sum _{i=1}^{n}\mathbb{Z}{\alpha}_{i}\text{.}$
Let ${Q}^{+}=\{\alpha =\sum _{i=1}^{n}{a}_{j}{\alpha}_{i}\in Q\hspace{0.17em}|\hspace{0.17em}{a}_{i}\ge 0\}\text{.}$
The *height* of a root $\alpha =\sum _{i=1}^{n}{a}_{i}{\alpha}_{i}\in {Q}^{+}$
is $\text{ht}\left(\alpha \right)=\sum _{i=1}^{n}{a}_{i}\text{.}$
The *weights* of words $w={x}_{{i}_{1}}\cdots {x}_{{i}_{k}}\in {X}^{*}$
and $\stackrel{\u203e}{w}={y}_{{i}_{1}}\cdots {y}_{{i}_{k}}\in {Y}^{*}$
are defined by
$$\text{wt}\left(\ell \right)={\alpha}_{{i}_{1}}+\cdots +{\alpha}_{{i}_{k}}\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}\text{wt}\left(\stackrel{\u203e}{\ell}\right)=-{\alpha}_{{i}_{1}}-\cdots -{\alpha}_{{i}_{k}},$$
respectively. Note that the length of a word $w$ such that $\text{wt}\left(w\right)=\alpha $
is equal to $\text{ht}\left(\alpha \right)\text{.}$

With notations for standard bracketings as in (1.1) we define
$${\U0001d524}_{\alpha}=\u2102\text{-span}\left\{b\left[\ell \right]\hspace{0.17em}\right|\hspace{0.17em}\ell \in {X}^{*},\text{wt}\left(\ell \right)=\alpha \}$$
and
$${\U0001d524}_{-\alpha}=\u2102\text{-span}\left\{b\left[\stackrel{\u203e}{\ell}\right]\hspace{0.17em}\right|\hspace{0.17em}\stackrel{\u203e}{\ell}\in {Y}^{*},\text{wt}\left(\stackrel{\u203e}{\ell}\right)=-\alpha \},$$
for each $\alpha \in {Q}^{+}\text{.}$ The set
$${\mathrm{\Phi}}^{+}=\{\alpha \in {Q}^{+}\hspace{0.17em}|\hspace{0.17em}\alpha \ne 0,\text{dim}\left({\U0001d524}_{\alpha}\right)\ne 0\}$$
is the set of *positive roots*. Let $\U0001d525$ be the linear span of the generators ${h}_{i}\text{.}$
The following facts about finite dimensional simple Lie algebras $\U0001d524$ are standard ([Hum1972] Thms. 18.3, 14.2, 8.4)
(3.1a)
$\U0001d524\cong {\U0001d52b}^{-}\oplus \U0001d525\oplus {\U0001d52b}^{+}\text{.}$
(3.1b)
${\U0001d52b}^{+}\cong \underset{\alpha \in {\mathrm{\Phi}}^{+}}{\u2a01}{\U0001d524}_{\alpha}$
and ${\U0001d52b}^{-}\cong \underset{\alpha \in {\mathrm{\Phi}}^{+}}{\u2a01}{\U0001d524}_{-\alpha}\text{.}$
(3.1c)
${\mathrm{\Phi}}^{+}$ is finite.
(3.1d)
$\text{dim}\left({\U0001d524}_{\alpha}\right)=1$
for all $\alpha \in {\mathrm{\Phi}}^{+}\text{.}$
The following result follows easily from the above facts.

(a)
For each $\alpha \in {\mathrm{\Phi}}^{+}$ there is a unique standard Lyndon word
${\ell}_{\alpha}\in {X}^{*}$ with respect to the ideal ${J}^{+}$
such that $\text{wt}\left({\ell}_{\alpha}\right)=\alpha \text{.}$
(b)
The words ${\ell}_{\alpha},{\stackrel{\u203e}{\ell}}_{\alpha}$
and the letters ${h}_{i}$ are the standard Lyndon words in ${A}^{*}$
with respect to the ideal $J\text{.}$ These words form a basis of the finite dimensional simple Lie algebra
$\U0001d524\text{.}$

*Proof. *
(a) Since the standard Lyndon words in ${X}^{*}$ with respect to the ideal ${J}^{+}$
form a basis of ${\U0001d52b}^{+},$ it follows that ${\U0001d524}_{\alpha}$
is the subset of ${\U0001d52b}^{+}$ spanned by the bracketings of standard Lyndon words of weight $\alpha $
with letters in $X\text{.}$ Similarly, ${\U0001d524}_{-\alpha}$
is the subspace of ${\U0001d52b}^{-}$ spanned by all $b\left[w\right]$
such that $w$ is a standard Lyndon word with letters in $Y$ and such that $\text{wt}\left(t\right)=-\alpha \text{.}$
The statement in (a) now follows from (3.1a) and (3.1b).

(b) It follows from (3.1d) that for each $\alpha \in {\mathrm{\Phi}}^{+}$
there is a *unique* standard Lyndon word ${\ell}_{\alpha}$ of weight $\alpha $ and that
${\U0001d524}_{\alpha}=\u2102b\left[{\ell}_{\alpha}\right]\text{.}$
Furthermore, it is clear from the form of the relations in ${J}^{+}$ and ${J}^{-}$
that ${\U0001d524}_{-\alpha}=\u2102b\left[{\stackrel{\u203e}{\ell}}_{\alpha}\right],$
where if ${\ell}_{\alpha}={x}_{{i}_{1}}\cdots {x}_{{i}_{k}},$
then ${\stackrel{\u203e}{\ell}}_{\alpha}$ is the word in ${Y}^{*}$
given by ${\stackrel{\u203e}{\ell}}_{\alpha}={y}_{{i}_{1}}\cdots {y}_{{i}_{k}}\text{.}$

$\square $

Our goal is to determine the standard Lyndon words ${\ell}_{\alpha},$ for all
$\alpha \in {\mathrm{\Phi}}^{+}\text{.}$ This is done by induction on the
lengths of the words (heights of the roots). The main tools are Propositions (2.4) and (2.9) from section 2 and the tables of the positive roots for the finite
dimensional simple Lie algebras, [Bou1981] pp. 250-275.

Let $\alpha =\sum _{i=1}^{n}{a}_{i}{\alpha}_{i}\in {\mathrm{\Phi}}^{+}\text{.}$
By Proposition (2.9) we know that ${\ell}_{\alpha}$ is of the form
$$\begin{array}{cc}{\ell}_{\alpha}={\ell}_{{\beta}_{1}}{\ell}_{{\beta}_{2}}\cdots {\ell}_{{\beta}_{k}}{x}_{e},& \text{(3.3)}\end{array}$$
where
(1)
${\ell}_{{\beta}_{j}}$ are standard Lyndon words for all
$1\le j\le k,$
(2)
${\ell}_{{\beta}_{j}}$ is a left factor of
${\ell}_{{\beta}_{j-1}}$ for all
$j>1,$
(3)
${x}_{e}\in X\text{.}$
In the following discussion we shall exclude the trivial case $\mid {\ell}_{\alpha}\mid =1$
so that $k>0\text{.}$ Because of (2), each of the factors
${\ell}_{{\beta}_{j}}$ begins with the same letter, say ${x}_{b}\in X,$
$1\le b\le n,$ and ${x}_{b}\ne {x}_{e}$
since ${\ell}_{\alpha}$ is Lyndon; in fact, the letter ${x}_{b}$ is the smallest letter in
the word ${\ell}_{\alpha}\text{.}$ Thus, since $\text{wt}\left({x}_{b}\right)={\alpha}_{b},$
$b$ is the smallest integer in $\{1,\dots ,n\}$ such that
${a}_{b}\ne 0\text{.}$ Since ${x}_{b}$ appears exactly
${a}_{b}$ times in ${\ell}_{\alpha}$ and it appears as the first letter of each of the
factors ${\ell}_{{\beta}_{j}},$ $1\le j\le k,$
it follows that $k\le {a}_{b}\text{.}$ A scan of the root tables for the finite dimensional
simple Lie algebras shows that ${a}_{b}\le 3$ and that ${a}_{b}=3$
for only one positive root (this root is in type ${G}_{2}\text{).}$

For each $1\le j\le k,$ let ${\beta}_{j}=\text{wt}\left({\ell}_{{\beta}_{j}}\right)\text{.}$
Then the factorization in (3.3) must satisfy the following:
(1)
${\beta}_{j}=\text{wt}\left({\ell}_{{\beta}_{j}}\right)\in {\mathrm{\Phi}}^{+}$
for all $1\le j\le k,$ since the factors ${\ell}_{{\beta}_{j}}$
are standard Lyndon words.
(2)
$\sum _{j=1}^{k}{\beta}_{j}+{\alpha}_{e}=a$
where ${\alpha}_{e}=\text{wt}\left({x}_{e}\right)\text{.}$
(3)
Since ${\ell}_{\alpha}$ is Lyndon, ${x}_{e}>{x}_{b},$
where ${x}_{b}$ is the first letter of the words ${\ell}_{{\beta}_{j}}$
and ${x}_{e}$ is the last letter of ${\ell}_{\alpha}\text{.}$
(4)
$k\le 2,$ except for a single root in type ${G}_{2}\text{.}$
(5)
If $k=2,$ then ${\beta}_{1}-{\beta}_{2}\in {Q}^{+},$
since ${\ell}_{{\beta}_{2}}$ is a left factor of ${\ell}_{{\beta}_{1}}\text{.}$
(6)
${\ell}_{\alpha}$ is a Lyndon word.
(7)
All the Lyndon factors of ${\ell}_{\alpha}$ are standard Lyndon words of smaller length and thus correspond to roots
$\gamma \in {\mathrm{\Phi}}^{+}$ such that
$\text{ht}\left(\gamma \right)<\text{ht}\left(\alpha \right)\text{.}$
Given these rules it is easy to construct the standard Lyndon words by induction. Let $\alpha \in {\mathrm{\Phi}}^{+},$
and assume that the standard Lyndon words ${\ell}_{\beta}$ are known for all
$\beta \in {\mathrm{\Phi}}^{+}$ such that
$\text{ht}\left(\beta \right)<\text{ht}\left(\alpha \right)\text{.}$
There are very few choices of roots ${\beta}_{j}\in {\mathrm{\Phi}}^{+},$
$1\le j\le k,$ $k\le 2,$
such that ${\beta}_{1}-{\beta}_{2}\in {Q}^{+}$ if
$k=2$ and $\alpha -\sum _{j}{\beta}_{j}={\alpha}_{e},$
where ${\alpha}_{e}\text{,}$ $1\le e\le n\text{.}$
The words ${\ell}_{{\beta}_{j}}$ are all known since
$\text{ht}\left({\beta}_{j}\right)<\text{ht}\left(\alpha \right)\text{.}$
Restricting to the cases where ${x}_{e}$ is greater than the first letter of the words ${\ell}_{{\beta}_{j}}$
leaves very few possibilities. In fact, one finds that for each root $\alpha \in {\mathrm{\Phi}}^{+}$
(except the root $\alpha ={\alpha}_{1}+2{\alpha}_{2}+4{\alpha}_{3}+2{\alpha}_{4}$
in type ${F}_{4}\text{)}$ there is a unique word ${\ell}_{\alpha}$ which
satisfies conditions (1)-(7) above. Since there is a unique standard Lyndon word corresponding to the root $\alpha $ this word must be
${\ell}_{\alpha}\text{.}$

Consider the root $\alpha ={\alpha}_{1}+2{\alpha}_{2}+4{\alpha}_{3}+2{\alpha}_{4}$
in ${F}_{4}\text{.}$ Applying (1)-(7) above, leaves two possibilities for the word
${\ell}_{\alpha}\text{:}$ ${w}_{1}={x}_{1}{x}_{2}{x}_{3}{x}_{4}{x}_{3}{x}_{2}{x}_{3}{x}_{4}{x}_{3}$
and ${w}_{2}={x}_{1}{x}_{2}{x}_{3}{x}_{4}{x}_{3}{x}_{4}{x}_{2}{x}_{3}{x}_{3}\text{.}$
Modulo the ideal ${J}^{+}$ we can write ${w}_{1}$ as a linear combination of standard Lyndon words which are smaller
in the order $\prec $ (greater in lexicographic order). This computation is as follows (we have suppressed the $x\text{'s}$
in writing the words and at each step we have underlined the letters which are being changed modulo the defining relations for the ideal ${J}^{+}\text{):}$
$$\begin{array}{rcl}{w}_{1}& =& 123432\underset{\_}{343}\\ & =& \frac{1}{2}\left(123432433\right)+\frac{1}{2}\left(1234\underset{\_}{3233}4\right)\\ & =& \frac{1}{2}[\left(123432433\right)+\frac{1}{3}\left(123\underset{\_}{42}3334\right)+\left(123433234\right)-\frac{1}{3}\left(123433324\right)]\\ & =& \frac{1}{2}[\left(123432433\right)+\frac{1}{3}\left(1\underset{\_}{232}43334\right)+\left(123433234\right)-\frac{1}{3}\left(123433324\right)]\\ & =& \frac{1}{2}[\left(123432433\right)+\frac{1}{6}[\left(132243334\right)+\left(\underset{\_}{122}343334\right)]+\left(123433234\right)-\frac{1}{3}\left(123433324\right)]\\ & =& \frac{1}{2}[\left(123432433\right)+\frac{1}{6}[\left(132243334\right)+[2\xb7\left(212343334\right)-\left(221343334\right)]]+\left(123433234\right)-\frac{1}{3}\left(123433324\right)]\text{.}\end{array}$$
Thus ${w}_{1}={x}_{1}{x}_{2}{x}_{3}{x}_{4}{x}_{3}{x}_{2}{x}_{3}{x}_{4}{x}_{3}$
is not a standard Lyndon word and ${\ell}_{\alpha}={x}_{1}{x}_{2}{x}_{3}{x}_{4}{x}_{3}{x}_{4}{x}_{2}{x}_{3}{x}_{3}\text{.}$

Figure 1 gives the standard Lyndon words corresponding for each of the finite dimensional simple Lie algebras. Let us explain how to read these diagrams. Each
tree is rooted. A path
$${p}_{w}=({i}_{1}\to {i}_{2}\to \cdots \to {i}_{k})$$
in the tree consisting of a chain of successive vertices and edges moving away from the root determines a word
$w={x}_{{i}_{1}}\cdots {x}_{{i}_{k}}\in {X}^{*}\text{.}$
The trees are constructed (by applying the procedure described above) so that this word is always a standard word with respect to the ideal of Serre relations
determined by the corresponding Cartan matrix. If the word is Lyndon then we say that the path is Lyndon. In the discussion following Proposition (3.2)
we have described how one proves (case by case) the following theorem.

For each of the trees in Figure 1 the set of words determined by the Lyndon paths in the tree is the complete
set of standard Lyndon words for the corresponding finite dimensional simple Lie algebra.

$$\begin{array}{c}\n\n\n\n\nAn\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\ni\ni+1\nn-1\nn\n\n\n\n\n\n\n\nBn\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\ni\ni+1\nn-1\nn\nn\nn-1\ni+2\ni+1\n\n\n\n\n\n\n\nCn\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\ni\ni+1\nn-1\nn\nn-1\ni+2\ni+1\n\n\ni\ni+1\nn-2\nn-1\nn\n\n\n\n\n\n\n\nDn\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\ni\ni+1\nn-2\nn\nn-1\ni+2\ni+1\n\n\nn-1\n\n\n\n\n\n\n\nF4\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n1\n2\n3\n4\n3\n2\n\n\n1\n2\n3\n4\n3\n4\n2\n3\n3\n2\n\n\n3\n2\n2\n3\n\n\n2\n3\n4\n3\n4\n\n\n3\n4\n3\n\n\n4\n\n\n\n\n\n\n\nG2\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n2\n2\n1\n2\n\n\n1\n1\n1\n2\n\n\n2\n\n\n\n\n\end{array}$$
$$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n1\n\n\n3\n\n\n4\n\n\n5\n2\n\n\n6\n2\n\n\n7\n2\n4\n\n\n8\n2\n4\n3\n\n\n7\n4\n5\n3\n\n\n4\n5\n3\n3\n\n\n5\n3\n6\n3\n4\n\n\n6\n3\n3\n4\n2\n\n\n7\n3\n4\n4\n2\n\n\n3\n4\n2\n5\n2\n\n\n4\n5\n2\n2\n\n\n6\n2\n4\n4\n\n\n6\n2\n4\n3\n\n\n2\n4\n3\n\n\n4\n3\n\n\n5\n3\n\n\n3\n\n\n4\n\n\n3\n\n\n\n1\n\n\n\n3\n\n\n\n4\n\n\n\n5\n\n\n\n6\n\n\n\n7\n\n\n\n8\n\n\n\n\n2\n\n\n\n4\n\n\n\n5\n\n\n\n6\n\n\n\n7\n\n\n\n\n\n\n\n\n\n\n8\n\n\n7\n3\n\n\n6\n3\n4\n\n\n2\n5\n3\n4\n5\n\n\n4\n3\n4\n5\n6\n\n\n3\n4\n5\n6\n7\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n3\n4\n5\n6\n7\n8\n\n\n4\n5\n6\n7\n8\n\n\n5\n6\n7\n8\n\n\n6\n7\n8\n\n\n7\n8\n\n\n8\n\n\n\n\end{array}$$
Figure 1. The trees giving the standard Lyndon paths. The root of each tree is the left most vertex. For ${A}_{n},{B}_{n},{C}_{n},{D}_{n},$
we give a generic tree with root $i,$ where $i=1,2,\dots ,n$
$\text{(}i=1,2,\dots ,n-1$
for ${D}_{n}\text{).}$ The standard paths for ${E}_{7}$ (respectively
${E}_{6}\text{)}$ are the paths from the trees for ${E}_{8}$ not containing
$8$ (respectively $7$ and $8\text{).}$ The white vertices end Lyndon paths, while black
vertices end non-Lyndon paths. The trees are designed so that for each root system all the ends of Lyndon paths corresponding to roots of the same height lie on a
common vertical line.

*Remark.* We have made some effort to compute the bracketing rule for the finite dimensional simple Lie algebras in terms of the basis of standard Lyndon words.
We have not yet succeeded in learning much from this exercise. We make only the following remarks, with a bit of reservation as the computations are complicated and
difficult to check precisely. It seems that the standard Lyndon bases for Types ${A}_{n},{B}_{n},{C}_{n},{D}_{n}$
are Chevalley bases. However, the standard Lyndon basis for type ${G}_{2}$ is definitely not a Chevalley basis. In fact, in type
${F}_{4}$ there are even some structure coefficients that are not integral.

*Remark.* It is clear that all of the results in section 2 are valid for any Lie algebra given by generators and relations. Preliminary computations seem
to indicate that it will be very instructive to study root multiplicities for Kac-Moody Lie algebras by way of standard Lyndon words.

page history