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]; 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] 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, 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#

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#

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 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. 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.

> 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 ;

Run in calculator

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).

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 and demonstrate the computation of a basis of $L(0)$.

> 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

Run in calculator

MultiplicationTable(~L): AlgLieExtr#

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). This computation is necessary for constructing instances as described in Section Instances of Lie Algebras Generated by Extremal Elements, 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 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#

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 > 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(~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.

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.

> 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)

Run in calculator

Instances of Lie Algebras Generated by Extremal Elements#

Instance(L): AlgLieExtr -> AlgLie#

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, 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#

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 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 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.

> 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)

Run in calculator

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$.

> 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

Run in calculator

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 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.

> 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> ]

Run in calculator

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

> 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

Run in calculator

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

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).

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 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#

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 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.

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

Run in calculator

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

> 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

Run in calculator

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.

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

Run in calculator

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$.

> 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

Run in calculator