## Section3Constructions

### Subsection3.1Stratifications

###### Definition3.1.

A stratification (a.k.a. Carnot grading) is a $\mathbb{Z}$-grading $\mathfrak{g}=\bigoplus_{n\in\mathbb{Z}}V_n$ such that $V_1$ generates $\mathfrak{g}$ as a Lie algebra. A Lie algebra $\mathfrak{g}$ is stratifiable if it admits a stratification.

In this section we show that constructing a stratification for a Lie algebra (or determining that one does not exist) is a linear problem and, consequently, prove Theorem 1.2. Our method is based on Lemma 3.10 of [6], which gives the following characterization of stratifiable Lie algebras:

The condition of Lemma 3.2 is straightforward to check in a basis adapted to the lower central series.

###### Definition3.3.

The lower central series of a Lie algebra $\mathfrak{g}$ is the decreasing sequence of subspaces

\begin{equation*} \mathfrak{g}=\mathfrak{g}^{(1)}\supset \mathfrak{g}^{(2)}\supset \mathfrak{g}^{(3)}\supset\cdots\text{,} \end{equation*}

where $\mathfrak{g}^{(i+1)} = [\mathfrak{g},\mathfrak{g}^{(i)}]\text{.}$ A basis $X_1,\dots,X_n$ of a Lie algebra $\mathfrak{g}$ is adapted to the lower central series if for every non-zero $\mathfrak{g}^{(i)}$ there exists an index $n_i\in\mathbb{N}$ such that $X_{n_i},\dots,X_n$ is a basis of $\mathfrak{g}^{(i)}\text{.}$ The degree of the basis element $X_i$ is the integer $w_i=\max\{j\in\mathbb{N}: X_i\in\mathfrak{g}^{(j)}\}\text{.}$

If $\delta\colon\mathfrak{g}\to\mathfrak{g}$ is a derivation that restricts to the identity on $\mathfrak{g}/[\mathfrak{g},\mathfrak{g}]\text{,}$ then by Lemma 3.2 $\mathfrak{g}$ admits a stratification

\begin{equation*} \mathfrak{g}=V_1\oplus\dots\oplus V_s \end{equation*}

such that $\restr{\delta}{V_i} = i\cdot \operatorname{id}\text{.}$ Since the terms of the lower central series are given in terms of the stratification as $\mathfrak{g}^{(i)}=V_i\oplus\dots\oplus V_s \text{,}$ it follows that $\delta(Y)\in i\cdot Y+\mathfrak{g}^{(i+1)}$ for any $Y\in\mathfrak{g}^{(i)}\text{.}$ That is, a derivation $\delta$ restricting to the identity on $\mathfrak{g}/[\mathfrak{g},\mathfrak{g}]$ is of the form (3.1) for some coefficients $a_{ij}\in F\text{.}$

It is then enough to show that (3.2) is equivalent to the Leibniz rule

\begin{equation*} \delta([X_i,X_j]) = [\delta(X_i),X_j]+[X_i,\delta(X_j)],\quad \forall i,j\in\{1,\ldots,n\}\text{.} \end{equation*}

Indeed, this would prove that a linear map defined by (3.1) is a derivation if and only if the coefficients $a_{ij}$ satisfy the linear system (3.2).

Since the basis $X_i$ is adapted to the lower central series, only the structure coefficients with large enough degrees are non-zero, i.e., we have

$$[X_i,X_j] = \sum_{w_k\geq w_i+w_j}c_{ij}^kX_k\text{.}\label{eq-lcs-basis-structure-coefficients}\tag{3.3}$$

By direct computation using (3.1) and (3.3) we get the expressions

\begin{align*} [\delta(X_i),X_j] \amp = \sum_{w_k\geq w_i+w_j}c_{ij}^kw_iX_k + \sum_{w_h\gt w_i}\sum_{w_k\geq w_h+w_j}a_{ih}c_{hj}^kX_k\\ [X_i,\delta(X_j)] \amp = \sum_{w_k\geq w_i+w_j}c_{ij}^kw_jX_k + \sum_{w_h\gt w_j}\sum_{w_k\geq w_i+w_h}a_{jh}c_{ih}^kX_k\\ \delta([X_i,X_j]) \amp = \sum_{w_k\geq w_i+w_j}c_{ij}^kw_kX_k + \sum_{w_h\geq w_i+w_j}\sum_{w_k\gt w_h}c_{ij}^ha_{hk}X_k \end{align*}

Denoting $\sum_k B_{ij}^kX_k = \delta([X_i,X_j])-[\delta(X_i),X_j]-[X_i,\delta(X_j)]\text{,}$ we find that the equation $B_{ij}^k=0$ is up to reorganizing terms equivalent to (3.2).

Finally, we observe that when $w_k\leq w_i+w_j\text{,}$ the condition $B_{ij}^k=0$ is automatically satisfied: for $w_k\lt w_i+w_j$ all of the sums are empty, and for $w_k=w_i+w_j\text{,}$ the only remaining terms from the sums cancel out as

\begin{equation*} B_{ij}^k = c_{ij}^kw_k-c_{ij}^kw_i-c_{ij}^kw_j=0\text{.} \end{equation*}

The concrete criterion of Proposition 3.4 provides the algorithm of Theorem 1.2.

###### Definition3.6.

An $\mathbb{R}$-grading $\mathcal{V} \colon \mathfrak{g} = \bigoplus_{\alpha \in \mathbb{R}} V_\alpha$ is positive if $\alpha\gt 0$ for all the weights of $\mathcal{V}\text{.}$ If such a grading exists for $\mathfrak{g}\text{,}$ then $\mathfrak{g}$ is said to be positively gradable.

One of our main goals is to determine when a grading admits a positive realization, i.e., can be realized as a positive grading. A characterization is given in Proposition 3.22 of [6]. In the lemma and proposition below, we provide constructive proofs for this characterization.

Let us consider the natural embedding of $\mathbb{Z}^m$ into $\mathbb{Q}^m\text{.}$ Using the canonical inner product $\langle\cdot,\cdot\rangle$ on $\mathbb{Q}^m\text{,}$ we define for each vector $v \in \mathbb{Q}^m\text{,}$ the corresponding open half-space

\begin{equation*} M_v = \{x\in \mathbb{Q}^m : \langle v, x \rangle > 0 \}\text{.} \end{equation*}

Denote by $\Omega= \{\alpha_1,\ldots,\alpha_N\}$ the set of weights of $\mathcal{V}\text{.}$ Recall that the convex hull of a set is the intersection of all the affine half-spaces containing the set. Hence, because the convex hull of $\Omega$ does not contain the origin, it is contained in an open half-space $M_{v_0} \subset \mathbb{Q}^m\text{.}$ Moreover, there exists a neighborhood $B$ of $v_0$ such that the convex hull of $\Omega$ is contained in every half-space $M_v$ with $v\in B\text{.}$

By construction all the inner products $\langle v, \alpha_i \rangle$ with $\alpha_i \in \Omega$ and $v\in B$ are strictly positive. Since $B$ has non-empty interior, we may choose some $v\in B$ such that all the numbers $\langle v, \alpha_1 \rangle , \ldots, \langle v, \alpha_N \rangle$ are strictly positive and distinct. Rescaling $v$ to eliminate denominators, we obtain a vector $\tilde{v} \in \mathbb{Z}^m\text{,}$ and the map $f(\cdot)=\langle \tilde{v}, \cdot \rangle$ is the required homomorphism $\mathbb{Z}^m \to \mathbb{Z}\text{.}$ Concretely, a valid vector $\tilde{v}$ can be found directly by just enumerating the points of $\mathbb{Z}^k$ with increasing distance from the origin and testing one by one if all the inner products with the weights are positive and distinct.

We only need to prove the forward implication due to Lemma 3.7. Let $\mathcal{V}$ be a positive realization of $\mathcal{W}$ and let $\widetilde{\mathcal{W}}$ be the universal realization of $\mathcal{W}\text{,}$ which by Lemma 2.14 is a $\mathbb{Z}^k$-grading. Then by the definition of a universal realization there is a homomorphism $f \colon \mathbb{Z}^k \to \mathbb{R}$ such that $\mathcal{V}= f_* \widetilde{\mathcal{W}}$. Consider the vector $v = (f(e_1),\ldots,f(e_k)) \in \mathbb{R}^k\text{,}$ where $e_1,\ldots, e_k$ are the standard basis vectors of $\mathbb{Z}^k\text{,}$ and express $f$ as $f(\cdot)= \langle v, \cdot \rangle\text{.}$ Since $\mathcal{V}$ is a positive grading, then for all weights $\alpha$ of $\widetilde{\mathcal{W}}$ we have $f(\alpha) \gt 0 \text{,}$ that is, $\langle v, \alpha \rangle \gt 0\text{.}$ Hence all the weights belong to the open half-space determined by the vector $v\text{,}$ and so the origin is not contained in their convex hull.

The above results give the following algorithm for Theorem 1.5.i. We stress that we do not need to assume that the base field of $\mathfrak{g}$ is algebraically closed.

The algorithm for Theorem 1.5.ii is somewhat similar to Algorithm 3.9. Suppose we have an $S$-grading $\mathcal{V}$ for a finitely generated abelian group $S\text{,}$ and we want to find a homomorphism $S\to\mathbb{R}$ turning it into a positive grading. If some element of $S$ has torsion, then no such homomorphism can exist. Otherwise, $S$ is isomorphic to $\mathbb{Z}^k$ for some $k \ge 1$ and we may follow steps 2-Item 3 of the above algorithm to obtain a homomorphism $S\to\mathbb{R}$ giving a positive realization if one exists.

###### Remark3.10.

The argument of Lemma 3.7 can also be used to find a realization over $\mathbb{Z}$ for any torsion-free grading $\mathcal{V}\text{.}$ Indeed, first consider the universal realization of $\mathcal V$ over some $\mathbb{Z}^k\text{.}$ Then disregarding the discussion about half-spaces and positivity, find a push-forward to $\mathbb{Z}$ by constructing a vector $v$ for which the projection is injective on the weights.

###### Remark3.11.

The results we have established can also be used to explicitly enumerate the positive gradings of a given Lie algebra $\mathfrak{g}$ over an algebraically closed field, in two different senses.

1. Consider the maximal grading $\mathcal{V}$ of $\mathfrak{g}$ over $\mathbb{Z}^k\text{.}$ Up to automorphism, positive gradings of $\mathfrak{g}$ are given by the projections from $\mathbb{Z}^k$ to $\mathbb{R}$ mapping the weights of $\mathcal{V}$ to strictly positive numbers. A parametrisation of these projections gives a parametrisation of positive gradings.
2. Construct all the gradings of $\mathfrak{g}$ as in Proposition 2.25 (using a maximal grading constructed in Algorithm 3.12). Then check one by one which of them admit positive realizations. This produces a finite list of positive gradings so that every positive grading of $\mathfrak{g}$ is equivalent in the sense of Definition 2.9 to one of the elements on the list.

The algorithm of Theorem 1.3 is given by applying Algorithm 3.9 to the maximal grading of a Lie algebra. Indeed, if some grading admits a positive realization, then by Proposition 2.23 the maximal grading admits a positive realization as well. For the maximal grading, a positive realization if one exists is given by Algorithm 3.9.

The existence of a positive realization of a grading can also be phrased as the existence of a solution to a linear system. This viewpoint gives rise to an alternate elementary algorithm to determine whether a positive realization exists, as we explain in Appendix A.

In this section we prove Theorem 1.1 by providing an algorithm to construct a maximal grading for a Lie algebra $\mathfrak{g}$ defined over an algebraically closed field of characteristic zero. In this setting, every torus is split. The method we use to compute maximal gradings is the following.

The rest of the section is devoted to proving the correctness of Algorithm 3.12 and to explaining the steps in more detail. Step 6 is the most involved part.

Step 1 is straightforward linear algebra. In step 2, the grading induced by the torus $\mathfrak{t}$ has a concrete description in terms of a fixed basis of $\mathfrak{t}\text{.}$ Namely, a basis $\delta_1,\ldots,\delta_k$ defines an isomorphism $\mathfrak{t}^*\to F^k$ and hence an equivalent push-forward grading over $F^k\text{.}$ Expanding out the construction of Lemma 2.17 shows that the push-forward grading has the layers

\begin{equation*} V_\lambda = V_{(\lambda_1,\ldots,\lambda_k)} = \bigcap_{i=1}^k E^{\lambda_i}_{\delta_i}\text{,} \end{equation*}

where $E^{\lambda_i}_{\delta_i}$ is the (possibly zero) eigenspace for the eigenvalue $\lambda_i$ of the derivation $\delta_i\text{.}$

Step 3 is another straightforward linear algebra computation. In step 4, the key observation is that any linear map $A\in C(\mathfrak{t})$ preserves the eigenspaces of all the derivations $\delta\in\mathfrak{t}\text{.}$ Hence such a linear map $A$ also preserves the layers $V_\lambda$ of the $F^k$-grading. It follows that each map $\ad(A)$ restricts to a linear map $\ad(A)\colon \mathfrak{gl}(V_\lambda)\to \mathfrak{gl}(V_\lambda)$ for each weight $\lambda\text{.}$ The direct sum of these representations gives the representation $\ad\colon C(\mathfrak{t})\to \bigoplus_{\lambda}\mathfrak{gl}(\mathfrak{gl}(V_\lambda))\text{.}$

Step 5 captures the situation when the torus $\mathfrak{t}$ can be extended without refining the grading. Indeed, the elements of the kernel of $\ad$ are the elements $A\in C(\mathfrak{t})$ whose restrictions commute with all other maps in $\mathfrak{gl}(V_\lambda)$ for each weight $\lambda\text{.}$ That is, they are the maps $A\in C(\mathfrak{t})$ such that each $\restr{A}{V_\lambda}$ is a multiple of the identity. The eigenspaces of such maps are sums of the layers $V_\lambda\text{,}$ so they do not further refine the grading induced by $\mathfrak{t}\text{,}$ as seen in the following example.

Let $\mathfrak{h}$ be the Heisenberg Lie algebra with the only bracket $[X,Y]=Z\text{.}$ Consider the derivation

The grading induced by $\delta$ is $\mathfrak{h}=V_1\oplus V_2\oplus V_3=\langle X\rangle\oplus\langle Y\rangle \oplus \langle Z\rangle\text{.}$

The centralizer of $\delta$ in $\der(\mathfrak{h})$ is the two-dimensional space $C(\delta)=\langle \delta_1,\delta_2\rangle\text{,}$ where the two basis derivations are defined by

\begin{align*} \delta_1(X)\amp = X,\amp \delta_1(Y)\amp = 0,\amp \delta_1(Z)\amp = Z,\\ \delta_2(X)\amp = 0,\amp \delta_2(Y)\amp = Y,\amp \delta_1(Z)\amp = Z\text{.} \end{align*}

The one-dimensional Lie algebras $\mathfrak{gl}(V_i)$ are all abelian, so the adjoint representation $\ad\colon C(\delta)\to \mathfrak{gl}(\mathfrak{gl}(V_1))\oplus \mathfrak{gl}(\mathfrak{gl}(V_2))\oplus \mathfrak{gl}(\mathfrak{gl}(V_3))$ is just the zero map. Both $\{\delta,\delta_1\}$ and $\{\delta,\delta_2\}$ span strictly bigger tori than $\{\delta\}\text{,}$ but neither torus further refines the original grading $\mathfrak{h}=V_1\oplus V_2\oplus V_3\text{:}$ for instance, the grading induced by $\langle\delta,\delta_1\rangle$ is $V_{(1,1)}\oplus V_{(2,0)}\oplus V_{(3, 1)} =\langle X\rangle\oplus\langle Y\rangle \oplus \langle Z\rangle \text{.}$

Step 6 is the most intricate part of Algorithm 3.12. To prove its correctness, we need to show that if $A_s\in\mathfrak{t}$ for all basis elements $A=A_i$ and all their sums $A=A_i+A_j\text{,}$ then the torus $\mathfrak{t}$ is maximal. The proof is based on the efficient criterion of Proposition 2.6.11 of [12]:

To make use of the criterion Lemma 3.14, we also need the fact the Jordan decomposition is preserved by the adjoint representation.

By Proposition 2.2.5 of [12], since the field $F$ is perfect (as a field of characteristic zero), the adjoint map preserves both semisimplicity and nilpotency, so the map $\ad(A_s)$ is semisimple and the map $\ad(A_n)$ is nilpotent. Moreover, since the maps $A_s$ and $A_n$ commute, the Jacobi identity implies that the maps $\ad(A_s)$ and $\ad(A_n)$ also commute. The claim follows from the uniqueness of the Jordan decomposition.

With the above results, we are able to conclude that if the semisimple parts of $A_i$ and $A_i+A_j$ are contained in $\mathfrak{t}$ for all basis elements $A_i\text{,}$ then the torus $\mathfrak{t}$ in step 6 of Algorithm 3.12 is maximal. First, by step 5 we have $\mathfrak{t}=\ker(\ad)$ for the restricted adjoint representation $\ad\colon C(\mathfrak{t})\to \bigoplus_{\lambda}\mathfrak{gl}(\mathfrak{gl}(V_\lambda))$ defined in step 4. Then for any $A\in C(\mathfrak{t})$ by Lemma 3.15 we find that $A_s\in\mathfrak{t}$ if and only if $\ad(A)=\ad(A_n)\text{,}$ that is, if and only if $\ad(A)$ is nilpotent. By Lemma 3.14, if all $\ad(A_i)$ and $\ad(A_i+A_j)$ are nilpotent, then $\ad(A)$ is nilpotent for all $A\in C(\mathfrak{t})\text{.}$ Hence $A_s\in\mathfrak{t}$ for all $A\in C(\mathfrak{t})\text{.}$ In other words, no semisimple element $A_s\in C(\mathfrak{t})\setminus\mathfrak{t}$ exists, so $\mathfrak{t}$ is maximal.

The final part of Algorithm 3.12 is step 7, where we replace the indexing by eigenvalues of the derivations of $\mathfrak{t}$ with indexing over some $\mathbb{Z}^k$ given by the universal realization. The precise method was described earlier in Algorithm 2.13. Since the construction of the first six steps of Algorithm 3.12 leads to a maximal torus of $\der(\mathfrak{g})\text{,}$ by Definition 2.21 the output is a maximal grading of $\mathfrak{g}\text{.}$

###### Remark3.16.

The only part where we use the assumption that the base field is algebraically closed is in step 6. The significance of the assumption is that the Jordan decomposition and Proposition 2.6.11 of [12] give us an efficient method to construct semisimple elements in $C(\mathfrak{t})\setminus\mathfrak{t}\text{.}$

If the base field is not algebraically closed, we need to explicitly require that the constructed elements of $C(\mathfrak{t})\setminus\mathfrak{t}$ are diagonalizable. The subset of diagonalizable elements of $C(\mathfrak{t})\setminus\mathfrak{t}$ is a semialgebraic set, and constructions to extract points from such sets exist, see for instance Section 13 of [1] on the existential theory of the reals. The problem is that these methods are practical only in low dimensions, and the construction would be needed in dimension $\dim\mathfrak{gl}(\mathfrak{g})=\dim(\mathfrak{g})^2\text{.}$ For Lie algebras defined over finite fields, more efficient randomized algorithms to find split tori exist, see [5] and [27].