# Lie Algebras Generated by Extremal Elements

A non-zero element $x$ of a Lie algebra $L$ over the field $K$ is extremal if $[x,[x,y]] \in K x$ for all $y \in L$. If $x$ is extremal, the existence of a linear map $f_x : L \rightarrow K$ such that $[x,[x,y]] = f_x(y) x$ for all $y \in L$ immediately follows from linearity of $[\cdot,\cdot]$.

In this section we describe functions for computing with Lie algebras generated by such extremal elements. For a simple connected undirected finite graph $\Gamma$ we consider an algebraic variety $X$ over $K$ whose $K$-points parametrize Lie algebras generated by extremal elements. Here the generators of the Lie algebras correspond to the vertices of the graph, and we prescribe commutation relations corresponding to the nonedges of $\Gamma$.

Details of the setup may be found in [[Roozemond, 2011](../../references.md#cite-roozemond11)]; we describe the essential ingredients here.

Assume that $\Gamma$ is a connected undirected finite graph with $n$ vertices, without loops or multiple bonds, and that $K$ is a field of characteristic distinct from 2. We let $\Pi$ be the vertex set of $\Gamma$ and denote adjacency of two vertices $x,y \in \Pi$ by $i \sim j$.

We denote by $F(K, \Gamma)$ the quotient of the free Lie algebra over K generated by $\Pi$ modulo the relations $[x,y]=0$ for all $x,y \in \Pi$ with $x \not\sim y$. We write $F^*$ for the space of all $K$-linear functions on $F$. For every $f \in (F^*)^\Pi$ we denote by $L(K,\Gamma, f)$ (often abbreviated to $L(f)$) the quotient of $F(K,\Gamma)$ by the ideal $I( f )$ generated by the infinitely many elements $[x,[x,y]] - f_x(y) x$ for $x \in \Pi$, $y \in F$.

By construction $L( f )$ is a Lie algebra generated by $|\Pi| = n$ extremal elements, the extremal generators corresponding to the vertices of $\Gamma$ and commuting whenever they are not adjacent. The element $f_x \in F^*$ is a parameter expressing the extremality of $x \in \Pi$.

In the Lie algebra $L(0)$ the elements of $\Pi$ map to sandwich elements. This algebra is finite-dimensional, by [[Zel$'$manov and Kostrikin, 1990](../../references.md#cite-zk90)] this Lie algebra is finite-dimensional; for general $f \in (F^*)^\Pi$ we have $\dim(L(f)) \leq \dim(L(0))$ by [[Cohen *et al.*, 2001](../../references.md#cite-csuw01), Lemma 4.3]. It is therefore natural to focus on the Lie algebras $L( f )$ of maximal possible dimension, i.e., those of dimension $\dim(L(0))$. We define the set $X := \{ f \in (F^*)^\Pi \mid \dim(L(f)) = \dim(L(0)) \}$, the parameter space for all maximal-dimensional Lie algebras of the form $L( f )$.

The functions currently implemented in Magma allow computation of $X$ and $L(f)$, for any $f$, for the cases where $X$ is an affine space (which is unproven, but true in all currently known cases).

Lie algebras generated by extremal elements are of type `AlgLieExtr`. The verbose flag `"AlgLieExtr"` may be set between 1 and 5 to show details and progress of the various computations.

## Constructing Lie Algebras Generated by Extremal Elements

### `ExtremalLieAlgebra(K, n): Rng, RngIntElt -> AlgLieExtr`

```magma
CommGens       : SeqEnum                    Default: []
HeisenbergPairs: SeqEnum                    Default: []
```

Construct the Lie algebra over the field $K$ generated by $n$ extremal elements. The characteristic of $K$ must be distinct from 2.

The optional argument `CommGens` contains pairs of integers $(i,j)$, with $1 \leq i,j \leq n$, describing that generators $x_i$ and $x_j$ commute, i.e., $[x_i, x_j] = 0$.

The optional argument `HeisenbergPairs` contains pairs of integers $(i,j)$, with $1 \leq i \leq n$ and $1 \leq j \leq \dim(L(0))$, describing that $f_{x_i}(b_j)$ should be taken equal to $0$. (Note that if it is required to have $j > n$ it would be necessary to have prior knowledge about the basis of $L(0)$).

### `ExtremalLieAlgebra(K, G): Rng, GrphUnd -> AlgLieExtr`

```magma
HeisenbergPairs: SeqEnum                    Default: []
```

Construct the Lie algebra over the field $K$ whose extremal generators are described by the graph $G$, i.e., with $|V(G)|$ generators, and $x_i$ and $x_j$ commute whenever vertices $x_i$ and $x_j$ of $G$ are not adjacent.

See [`ExtremalLieAlgebra`](#function-extremalliealgebrakn) above for a description of the optional argument `HeisenbergPairs`.

## Properties of Lie Algebras Generated by Extremal Elements

### `NumberOfGenerators(L): AlgLieExtr -> RngIntElt`

### `Ngens(L): AlgLieExtr -> RngIntElt`

The number of generators of $L$.

### `CoefficientRing(L): AlgLieExtr -> Rng`

### `BaseRing(L): AlgLieExtr -> Rng`

The coefficient ring of $L$. Immediately after construction, this is equal to the field $K$ provided as argument to [`ExtremalLieAlgebra`](#function-extremalliealgebrakn). However, after the multiplication table has been computed (see below), the coefficient ring would in general be a multivariate polynomial ring over $K$ describing the parameter space.

### `CommutatorGraph(L): AlgLieExtr -> GrphUnd`

The graph describing the extremal generators of $L$ and their commutator relations.

### `Example: Alg Lie Extr Constr (ex-3fa178)`

We construct a Lie algebra generated by $4$ extremal elements in two different manners.

```magma
> QQ := Rationals();
> L := ExtremalLieAlgebra(QQ, BipartiteGraph(2,2));
> Ngens(L), CoefficientRing(L);
4 Rational Field
> G := CommutatorGraph(L); G;
Graph
Vertex  Neighbours

1       3 4 ;
2       3 4 ;
3       1 2 ;
4       1 2 ;

> L := ExtremalLieAlgebra(QQ, 4 : CommGens := [<1,2>,<3,4>]);
> Ngens(L), CoefficientRing(L);
4 Rational Field
> G := CommutatorGraph(L); G;
Graph
Vertex  Neighbours

1       3 4 ;
2       3 4 ;
3       1 2 ;
4       1 2 ;

```

### `Basis(L): AlgLieExtr -> SeqEnum[AlgFPLieElt], SeqEnum[UserProgram]`

Compute a monomial basis for $L(0)$ (this is also a monomial basis for $L(f)$ for any $f \in X$; see the introduction of Section [Lie Algebras Generated by Extremal Elements](#sectalglieextr)).

The first return value is a sequence consisting of monomials of the free Lie algebra over $K$ with $n$ generators, where $K$ is the coefficient ring of $L$ and $n$ is the number of generators. The second return value is a sequence consisting of functions $c$. Each of these functions may be applied to a sequence of generators and a composition function. These may be used to construct the basis elements in other environments.

The algorithm used in this function is due to W. de Graaf.

### `ZBasis(L): AlgLieExtr -> SeqEnum[AlgFPLieElt], SeqEnum[RngIntElt], SeqEnum[AlgFPLieElt]`

For $L$ a Lie algebra generated by extremal elements over the field of rational numbers, compute a basis of the corresponding Lie ring over the integers.

This function returns three sequences $B$, $T$, $C$, respectively, describing bases for $L(0)$ over **any** field $K$. $B$ is a not necessarily monomial basis, with torsion described by $T$. It is such that if $T[i]$ is nonzero, $m$ say, then $B[i]$ is zero unless the characteristic of $K$ divides $m$.

The third sequence, $C$, is a sequence of monomials that linearly span $L(0)$ over any field $K$. Note, however, that if $T$ contains nonzero elements, then $C$ would in general contain superfluous elements and therefore not be a basis.

The algorithm used in this function is due to W. de Graaf. The only currently known case with nontrivial torsion is for $\Gamma(L) = K_5$.

### `Dimension(L): AlgLieExtr -> RngIntElt`

The dimension of $L(0)$. This value is computed via a basis computation, so potentially quite time-consuming.

### `Example: Alg Lie Extr Basis (ex-0b6eca)`

We continue the previous example [Example: Alg Lie Extr Constr](#example-ex-3fa178) and demonstrate the computation of a basis of $L(0)$.

```magma
> B, C := Basis(L);
> B;
[
    $.1,
    $.2,
    $.3,
    $.4,
    ($.4, $.2),
    ($.4, $.1),
    ($.3, $.2),
    ($.3, $.1),
    ($.4, ($.3, $.2)),
    ($.4, ($.3, $.1)),
    ($.2, ($.4, $.1)),
    ($.2, ($.3, $.1)),
    ($.4, ($.2, ($.3, $.1))),
    ($.3, ($.2, ($.4, $.1))),
    ($.2, ($.4, ($.3, $.1)))
]
> [ c(["x","y","z","u"], func<i,j|i cat j>) : c in C ];
[ x, y, z, u, uy, ux, zy, zx, uzy, uzx, yux, yzx, uyzx, zyux, yuzx ]
> A := FreeAlgebra(Rationals(), 4);
> [ c([A.1,A.2,A.3,A.4], func<x,y|x*y>) : c in C ];
[
    $.1,
    $.2,
    $.3,
    $.4,
    $.4*$.2,
    $.4*$.1,
    $.3*$.2,
    $.3*$.1,
    $.4*$.3*$.2,
    $.4*$.3*$.1,
    $.2*$.4*$.1,
    $.2*$.3*$.1,
    $.4*$.2*$.3*$.1,
    $.3*$.2*$.4*$.1,
    $.2*$.4*$.3*$.1
]
> #B, #C, Dimension(L);
15 15 15

```

### `MultiplicationTable(~L): AlgLieExtr`

```magma
HowMuch   : MonStgElt                    Default: "Auto"
MemLimit  : RngIntElt                    Default: Infinity()
FullJacobi: BoolElt                      Default: false
```

Force computation of a general multiplication table for $L$, i.e., one that may be used for constructing $L(f)$ for any $f \in X$ (see the introduction to this section [Lie Algebras Generated by Extremal Elements](#sectalglieextr)). This computation is necessary for constructing instances as described in Section [Instances of Lie Algebras Generated by Extremal Elements](#subsectalglieextrinstances), but it will be done automatically if needed. Data about the variety $X$ is computed concurrently and stored internally; see Section [Studying the Parameter Space](#subsectalglieextrvariety) for the relevant functions in accessing that information.

The optional parameters may be used to influence the computation, although the defaults should generally work well. `HowMuch` may be set to “Auto” (the default), “Top” or “Full” and prescribes whether only the first `Ngens(L)` rows of the multiplication table are computed (“Top”), or all entries (“Full”). If set to “Auto” some fraction of the multiplication table is computed depending on the dimension of $L$ and the other parameters.

`MemLimit` may be set to a positive integer $m$, and if given Magma will attempt to limit its memory usage to $m$ MB, by limiting the portion of the multiplication table that is being computed.

`FullJacobi` may be set to `true` in order to force checking the Jacobi identity for all basis elements, thus providing more certainty with regards to the information about the parameter space $X$. Note that even if this parameter is set to `true` a heuristic (Monte-Carlo) method is used, as considering all $\dim(L(0))^3$ triples quickly becomes infeasible as the dimension grows.

The verbose flag `"AlgLieExtr"` may be set to 3 or more to obtain some information about the default choices Magma makes with regards to these parameters.

### `MultiplicationTable(L): AlgLieExtr -> SeqEnum`

```magma
Rep  : MonStgElt                    Default: "Auto"
Check: BoolElt                      Default: true
```

A general multiplication table for $L$.

If `Rep` is set to “Dense” it will be returned as a sequence of sequences of vectors over `CoefficientRing(L)`. If `Rep` is set to “Sparse” it will be returned as a sequence of 4-tuples. If `Rep` is set to “Auto” a choice between these representations is made depending on $\dim(L)$. Both these representations may be used on the right hand side of the [`LieAlgebra<R, n | Q : parameters >`](construct.md#constructor-liealgebrarnq) constructor.

The optional parameter `Check` controls whether the Jacobi identity is verified for all triples (if `true` it will actually be checked for all $\dim(L(0))^3$ triples, as opposed to the behaviour of the procedural version, [`MultiplicationTable`](#function-multiplicationtablelproc)`(~L)`, described above).

Note that this function is impractical in terms of CPU time and memory usage once $\dim(L)$ exceeds approximately $50$. In such cases, the Lie algebra is more easily studied using the functions described in Section [Instances of Lie Algebras Generated by Extremal Elements](#subsectalglieextrinstances).

### `Example: Alg Lie Extr Mult Table (ex-7dacec)`

We construct the generic Lie algebra generated by $3$ extremal elements and construct a structure constant Lie algebra using the multiplication table.

```magma
> L := ExtremalLieAlgebra(Rationals(), 3);
> L:Maximal;
Lie algebra generated by 3 extremal elements, defined over Rational
Field
> MultiplicationTable(~L);
> L:Maximal;
Lie algebra generated by 3 extremal elements, originally defined over
Rational Field
  Now living over Polynomial ring of rank 4 over Rational Field
  Dimension: 8
  Picked 4 f-values:
    f(2, [1]) = f21
    f(3, [1]) = f31
    f(3, [2]) = f32
    f(1, [32]) = f132

> Dimension(L);
8
> MT := MultiplicationTable(L);
> MT[4][8];
(0   -1/2*f31*f32   0   -1/2*f132   0   0   0   1/2*f32)
> M := LieAlgebra<CoefficientRing(L), 8 | MT>;
> M;
Lie Algebra of dimension 8 with base ring Polynomial ring of rank 4
over Rational Field
> M.4*M.8;
(0   -1/2*f31*f32   0   -1/2*f132   0   0   0   1/2*f32)
> M.1*(M.1*M.2);
(f21   0   0   0   0   0   0   0)

```

## Instances of Lie Algebras Generated by Extremal Elements

### `Instance(L): AlgLieExtr -> AlgLie`

```magma
Rep  : MonStgElt                    Default: "Auto"
Check: BoolElt                      Default: true
```

The Lie algebra $L(f)$ for general $f$. The Lie algebra returned will in general be defined over a multivariate polynomial ring.

This function is identical to [`MultiplicationTable`](#function-multiplicationtablel), except that it returns a Lie algebra rather than a multiplication table. Please refer to that function for information on the optional arguments `Rep` and `Check`. Note that this function also is impractical in terms of CPU time and memory usage once $\dim(L)$ exceeds approximately $50$. In such cases, the Lie algebra is more easily studied by constructing particular instances of $L(f)$ individually, as described below.

### `Instance(L, Q): AlgLieExtr, SeqEnum -> AlgLie, Map`

```magma
Rep  : MonStgElt                    Default: "Auto"
Check: BoolElt                      Default: true
```

Construct $L(f)$ where the $i$-th free parameter of $X$ is set to Q[i]. Consult `L:Maximal` or [`FreefValues`](#function-freefvalues) to obtain information about the free parameters. The coefficient ring of the Lie algebra $M$ returned will be equal to `Universe(Q)`. As a second return value, an invertible map from $M$ to the free Lie algebra of rank `Ngens(L)` is returned.

The optional argument `Rep` may be “Auto”, “Dense” or “Sparse” (refer to the documentation at [`MultiplicationTable`](#function-multiplicationtablel) for more information). `Check` may be set to `true` or `false` and determines whether the Jacobi identity is checked on the Lie algebra returned.

### `Example: Alg Lie Extr Mult Instance (ex-658a16)`

We construct the generic Lie algebra generated by $3$ extremal elements and study one of its instances.

```magma
> L := ExtremalLieAlgebra(Rationals(), 3);
> MultiplicationTable(~L);
> L:Maximal;
Lie algebra generated by 3 extremal elements, originally defined over
Rational Field
  Now living over Polynomial ring of rank 4 over Rational Field
  Dimension: 8
  Picked 4 f-values:
    f(2, [1]) = f21
    f(3, [1]) = f31
    f(3, [2]) = f32
    f(1, [32]) = f132

> M := Instance(L); M;
Lie Algebra of dimension 8 with base ring Polynomial ring of rank 4
over Rational Field
> M.1*(M.1*M.2);
(f21   0   0   0   0   0   0   0)

```

So in the most general case, $[x_1, [x_1, x_2]] = f_{x_2}(x_1) x_1$. Next, we consider an instance where we set $f_{x_2}(x_1) = 1/7$, $f_{x_3}(x_1) = 1/5$, $f_{x_3}(x_2) = 1/3$ and $f_{x_1}([x_3,x_2]) = 1$.

```magma
> N, phi := Instance(L, [Rationals()|1/7,1/5,1/3,1]);
> N;
Lie Algebra of dimension 8 with base ring Rational Field
> SemisimpleType(N);
A2
> N.1*(N.1*N.2);
(1/7   0   0   0   0   0   0   0)
> y := phi(N.2); z := phi(N.3);
> Parent(y):Minimal;
Free Lie algebra of rank 3 over Rational Field
> (y,(y,z));
-($.2, ($.3, $.2))
> (y,(y,z)) @@ phi;
(  0 1/3   0   0   0   0   0   0)
> (y,(y,z)) @@ phi @ phi;
1/3*$.2

```

## Studying the Parameter Space

### `FreefValues(L): AlgLieExtr -> SeqEnum, SeqEnum`

The values $f_x(b)$ generating the parameter space $X$ (see the introduction to this section [Lie Algebras Generated by Extremal Elements](#sectalglieextr) for details). This function returns two sequences: the first of the $f_x(b)$ as elements of `CoefficientRing(L)` and the second of the pairs $(x,b)$ as two-tuples of integers.

### `fValue(L, x, b): AlgLieExtr, RngIntElt, RngIntElt -> RngElt`

The value $f_x(b)$ as an element of `CoefficientRing(L)`.

### `fValueProof(L, x, b): AlgLieExtr, RngIntElt, RngIntElt`

Print a proof of correctness for the value $f_x(b)$.

### `Example: Alg Lie Extrf Val (ex-dc2192)`

We consider the generic Lie algebra generated by $4$ extremal elements.

```magma
> L := ExtremalLieAlgebra(Rationals(), 4);
> vals, pairs := FreefValues(L);
> vals;
[
    f21,
    f31,
    f41,
    f32,
    f42,
    f43,
    f143,
    f243,
    f142,
    f132,
    f1432,
    f2431
]
> #vals;
12
> pairs;
[ <2, 1>, <3, 1>, <4, 1>, <3, 2>, <4, 2>, <4, 3>, <1, 5>, <2, 5>, <1,
6>, <1, 8>, <1, 11>, <2, 12> ]

```

This shows that $\dim(X) = 12$. We compute some values $f_x(b)$.

```magma
> fValue(L, 1, 5);
f143
> fValue(L, 4, 17);
-f41*f42
> fValueProof(L, 4, 17);
f(4, [241]) -> -f(4,[2])*f(4,[1]) {f(x,[y,[x,N]]) = -f(x,y)f(x,N) by
  assoc. of f and anti-comm. of L}
    f(4, [2]) = f42 {Free}
    f(4, [1]) = f41 {Free}
= -f41*f42

```

### `DimensionsEstimate(L, g): AlgLieExtr, UserProgram -> SeqEnum, SetMulti`

```magma
NumSamples: RngIntElt                     Default: Infinity()
Check     : BoolElt                       Default: true
Rep       : MonStgElt                     Default: "Auto"
verbose   : AlgLieExtr                    Default: Verbose : 10
```

Estimate the dimensions of the subvarieties of the parameter space $X$ of $L$ giving rise to irreducible Lie algebra modules of different dimensions.

This procedure repeatedly (exactly `NumSamples` times) invokes `Instance(L, g())` to produce a Lie algebra $M$. The composition series of $M$ are computed, and the dimension $e$ of its simple factor is stored. Then, for each of these $e$ encountered, the dimension of the subvariety (inside the algebraic variety $X$) that contains Lie algebras whose top factor has dimension $e$ is estimated using the dimension $d$ of the full f-variety. (Here $d$ is taken to be the number of free f-values computed; see [`FreefValues`](#function-freefvalues)).

If the verbose flag `"AlgLieExtr"` is set 3 or more, then after each step the estimate is printed as a sequence of triples $(e, n, s)$: $n$ is the number of times dimension $e$ was encountered, and $s$ the estimate for the dimension of the subvariety.

Upon finishing (which will only happen if `NumSamples` is set to some finite number) that sequence of triples is returned. The second return value is a multiset containing the dimensions encountered in the search.

Note that this procedure assumes that $X$ itself is an affine variety (which has been proved if `CommutatorGraph(L)` is a connected simply laced Dynkin diagram of finite or affine type) and that `g` produces uniformly random elements of $X$. If either of these two is not the case, the estimates produced are likely wrong. Moreover, `g` must produce sequences of elements of a finite field.

The optional argument `Rep` may be “Auto”, “Dense” or “Sparse” (refer to the documentation at [`MultiplicationTable`](#function-multiplicationtablel) for more information). `Check` may be set to `true` or `false` and determines whether the Jacobi identity is checked on the Lie algebras constructed.

### `InstancesForDimensions(L, g, D): AlgLieExtr, UserProgram, SetEnum[RngIntElt] -> Assoc`

```magma
Check: BoolElt                    Default: true
```

For each $d \in D$ attempt to find an instance of $L$ whose simple factor has dimension $d$, by repeatedly invoking `Instance(L, g())`. The result is returned in the form of an associative array $A$ such that, for all $d \in D$, $A[d]$ is a triple $(v, M, \phi)$ where $v$ is such that `Instance(L, v)` is $M$, and $\phi$ is an invertible map from $M$ to the free Lie algebra.

See [`DimensionsEstimate`](#function-dimensionsestimate) for the required properties of `g`. The optional parameter `Check` may be set to `true` or `false` and determines whether the Jacobi identity is checked on the Lie algebras constructed.

### `Example: Alg Lie Extr Variety Dims (ex-44228f)`

We consider the generic Lie algebra generated by $3$ extremal elements.

```magma
> L := ExtremalLieAlgebra(Rationals(), 3);
> FreefValues(L);
[
    f21,
    f31,
    f32,
    f132
]
[ <2, 1>, <3, 1>, <3, 2>, <1, 4> ]

```

So $\dim(X) = 4$. We create a function `g` used to construct random instances of $L$ over GF(5).

```magma
> g := func< | [ Random(GF(5)) : i in [1..4] ]>;
> repeat M := Instance(L, g()); until Rank(KillingForm(M)) eq 8;
> M;
Lie Algebra of dimension 8 with base ring GF(5)
> SemisimpleType(M);
A2

```

So in this case `g()` yielded a Lie algebra of type A$_2$. We use `g` to obtain information about $X$, using 500 random instances.

```magma
> DimensionsEstimate(L, g : NumSamples := 500);
[ <3, 121, "3.12">, <8, 379, "3.83"> ]
{* 3^^121, 8^^379 *}

```

This shows that 379 instances were found where $M$ was simple of dimension 8, and 121 cases where $M$ had a simple factor of dimension 3. Using this result one might conjecture that there is a codimension $1$ subspace of $X$ with Lie algebras whose simple factor has dimension $3$.

```magma
> A := InstancesForDimensions(L, g, {3,8} : Check := false);
> A[3];
<[ 2, 1, 4, 4 ], Lie Algebra of dimension 8 with base ring GF(5),
Mapping from: Lie Algebra of dimension 8 with base ring GF(5) to Free
Lie algebra of rank 3 over GF(5) given by a rule>
> M := A[3][2]; MM := M/SolvableRadical(M); MM;
Lie Algebra of dimension 3 with base ring GF(5)
> SemisimpleType(MM);
A1
> M := A[8][2]; IsSimple(M);
true
> SemisimpleType(M);
A2

```