## Section 3 Constructions

### Subsection 3.1 Stratifications

###### Definition 3.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:

###### Lemma 3.2.

A nilpotent Lie algebra \(\mathfrak{g}\) is stratifiable if and only if there exists a derivation \(\delta\colon\mathfrak{g}\to\mathfrak{g}\) such that the induced map \(\mathfrak{g}/[\mathfrak{g},\mathfrak{g}]\to \mathfrak{g}/[\mathfrak{g},\mathfrak{g}]\) is the identity map. Moreover, a stratification is given by the layers \(V_i=\ker (\delta-i)\text{.}\)

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

###### Definition 3.3.

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

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{.}\)

###### Proposition 3.4.

Let \(X_1,\ldots,X_n\) be a basis adapted to the lower central series of a nilpotent Lie algebra \(\mathfrak{g}\) defined over a field \(F\text{.}\) Let \(w_1,\ldots,w_n\) be the degrees of the basis elements and let \(c_{ij}^k\in F\) be the structure coefficients in the basis. A linear map \(\delta\colon\mathfrak{g}\to\mathfrak{g}\) is a derivation that restricts to the identity on \(\mathfrak{g}/[\mathfrak{g},\mathfrak{g}]\) if and only if

such that, for each triple of indices \(i,j,k\) such that \(w_k\gt w_i+w_j\text{,}\) the coefficients \(a_{ij}\in F\) satisfy the linear equation

###### Proof.

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

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

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

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

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

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

###### Algorithm 3.5. Stratification.

Input: A nilpotent Lie algebra \(\mathfrak{g}\text{.}\) Output: A stratification of \(\mathfrak{g}\) or the non-existence of one.

- Construct a basis \(X_1,\ldots,X_n\) adapted to the lower central series.
- Find a derivation \(\delta\) as in (3.1) solving the linear system (3.2). If the system has no solutions, then \(\mathfrak{g}\) is not stratifiable.
- Return the stratification with the layers \(V_i=\ker (\delta-i)\text{.}\)

### Subsection 3.2 Positive gradings

###### Definition 3.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.

###### Lemma 3.7.

Let \(m \ge 1\) and let \(\mathcal{V} \) be a \(\mathbb{Z}^m\)-grading of a Lie algebra \(\mathfrak{g}\text{.}\) Suppose the convex hull of the set of weights of \(\mathcal{V} \) does not contain the origin. Then there exists a homomorphism \(f \colon \mathbb{Z}^m \to \mathbb{Z}\) whose restriction on the weights is injective and positive.

###### Proof.

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

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.

###### Proposition 3.8.

Let \(\mathcal{W}\) be a torsion-free grading. Then \(\mathcal{W}\) admits a positive realization if and only if the convex hull of the set of weights of the universal realization of \(\mathcal{W}\) does not contain the origin.

###### Proof.

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.

###### Algorithm 3.9. Positive realization.

Input: A torsion-free grading \(\mathcal{V}\) for a Lie algebra \(\mathfrak{g}\text{.}\) Output: A positive realization of \(\mathcal{V}\) or the non-existence of one.

- Compute the universal realization \(\widetilde{\mathcal{V}}\) of \(\mathcal{V}\) using Algorithm 2.13. Let \(\mathbb{Z}^k\) be the grading group of \(\widetilde{\mathcal{V}}\text{.}\)
- If the convex hull of the weights of \(\widetilde{\mathcal{V}}\) contains the origin, then no positive realization exists.
- Otherwise, find a vector \(v \in \mathbb{Z}^k\) so that the homomorphism \(f\colon \mathbb{Z}^k\to\mathbb{Z}\text{,}\) \(f(\cdot)=\langle v,\cdot\rangle\) maps all weights of \(\widetilde{\mathcal{V}}\) to distinct positive integers.
- Return the push-forward grading \(f_*\widetilde{\mathcal{V}}\text{.}\)

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.

###### Remark 3.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.

###### Remark 3.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.

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

### Subsection 3.3 Maximal gradings

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.

###### Algorithm 3.12. Maximal grading.

Input: A Lie algebra \(\mathfrak{g}\) over an algebraically closed field \(F\text{.}\) Output: A maximal grading of \(\mathfrak{g}\text{.}\)

- Compute a basis for the derivation algebra \(\der(\mathfrak{g})\text{.}\) Set \(B= \emptyset\text{.}\)
- Determine the \(\mathfrak{t}^*\)-grading \(\mathcal{V}:\mathfrak{g}=\bigoplus_\lambda V_\lambda\) induced by the torus \(\mathfrak{t}=\langle B\rangle\text{.}\)
- Compute a basis \(A_1,\ldots,A_n\) for the centralizer \(C(\mathfrak{t})\subset \der(\mathfrak{g})\text{.}\)
- Compute the adjoint representation \(\ad\colon C(\mathfrak{t})\to \bigoplus_{\lambda}\mathfrak{gl}(\mathfrak{gl}(V_\lambda))\text{.}\)
- Compute a basis \(K_1,\ldots,K_m\) for \(\ker(\ad)\subset C(\mathfrak{t})\text{.}\) If \(K_{i}\notin \mathfrak{t}\) for some \(i=1,\ldots,m\text{,}\) extend \(\mathfrak{t}\) by \(K_{i}\) and go back to step 2.
- Repeat for each \(A=A_i\) and \(A=A_i+A_j\text{,}\) \(i,j=1,\ldots,n\text{:}\) compute the Jordan decomposition \(A=A_s+A_n\text{.}\) If \(A_s\notin \mathfrak{t}\text{,}\) extend \(\mathfrak{t}\) by \(A_s\) and go back to step 2.
- Compute and return the universal realization of the grading \(\mathcal{V}\text{.}\)

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

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.

###### Example 3.13.

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

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

###### Lemma 3.14.

Let \(\mathfrak{c}\) be a Lie algebra and let \(X_1,\ldots,X_n\) be a basis of \(\mathfrak{c}\text{.}\) If \(\ad(X_i)\) is nilpotent for \(1\leq i\leq n\) and \(\ad(X_i+X_j)\) is nilpotent for all \(1\leq i\lt j\leq n\text{,}\) then \(\ad(X)\) is nilpotent for all \(X\in\mathfrak{c}\text{.}\)

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

###### Lemma 3.15.

Let \(F\) be a field of characteristic zero. Let \(A\in\mathfrak{gl}(n,F)\) be any linear map and \(A=A_s+A_n\) its Jordan decomposition. Then \(\ad(A)=\ad(A_s)+\ad(A_n)\) is the Jordan decomposition of the map \(\ad(A)\colon \mathfrak{gl}(n,F)\to\mathfrak{gl}(n,F)\text{.}\)

###### Proof.

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{.}\)

###### Remark 3.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].