In a multiplicative group ${G}$, the commutator of two group elements ${g, h}$ is defined as ${[g,h] := g^{-1}h^{-1}gh}$ (other conventions are also in use, though they are largely equivalent for the purposes of this discussion). A group is said to be nilpotent of step ${s}$ (or more precisely, step ${\leq s}$), if all iterated commutators of order ${s+1}$ or higher necessarily vanish. For instance, a group is nilpotent of order ${1}$ if and only if it is abelian, and it is nilpotent of order ${2}$ if and only if ${[[g_1,g_2],g_3]=id}$ for all ${g_1,g_2,g_3}$ (i.e. all commutator elements ${[g_1,g_2]}$ are central), and so forth. A good example of an ${s}$-step nilpotent group is the group of ${s+1 \times s+1}$ upper-triangular unipotent matrices (i.e. matrices with ${1}$s on the diagonal and zero below the diagonal), and taking values in some ring (e.g. reals, integers, complex numbers, etc.).

Another important example of nilpotent groups arise from operations on polynomials. For instance, if ${V_{\leq s}}$ is the vector space of real polynomials of one variable of degree at most ${s}$, then there are two natural affine actions on ${V_{\leq s}}$. Firstly, every polynomial ${Q}$ in ${V_{\leq s}}$ gives rise to an “vertical” shift ${P \mapsto P+Q}$. Secondly, every ${h \in {\bf R}}$ gives rise to a “horizontal” shift ${P \mapsto P(\cdot+h)}$. The group generated by these two shifts is a nilpotent group of step ${\leq s}$; this reflects the well-known fact that a polynomial of degree ${\leq s}$ vanishes once one differentiates more than ${s}$ times. Because of this link between nilpotentcy and polynomials, one can view nilpotent algebra as a generalisation of polynomial algebra.

Suppose one has a finite number ${g_1,\ldots,g_n}$ of generators. Using abstract algebra, one can then construct the free nilpotent group ${{\mathcal F}_{\leq s}(g_1,\ldots,g_n)}$ of step ${\leq s}$, defined as the group generated by the ${g_1,\ldots,g_n}$ subject to the relations that all commutators of order ${s+1}$ involving the generators are trivial. This is the universal object in the category of nilpotent groups of step ${\leq s}$ with ${n}$ marked elements ${g_1,\ldots,g_n}$. In other words, given any other ${\leq s}$-step nilpotent group ${G'}$ with ${n}$ marked elements ${g'_1,\ldots,g'_n}$, there is a unique homomorphism from the free nilpotent group to ${G'}$ that maps each ${g_j}$ to ${g'_j}$ for ${1 \leq j \leq n}$. In particular, the free nilpotent group is well-defined up to isomorphism in this category.

In many applications, one wants to have a more concrete description of the free nilpotent group, so that one can perform computations more easily (and in particular, be able to tell when two words in the group are equal or not). This is easy for small values of ${s}$. For instance, when ${s=1}$, ${{\mathcal F}_{\leq 1}(g_1,\ldots,g_n)}$ is simply the free abelian group generated by ${g_1,\ldots,g_n}$, and so every element ${g}$ of ${{\mathcal F}_{\leq 1}(g_1,\ldots,g_n)}$ can be described uniquely as

$\displaystyle g = \prod_{j=1}^n g_j^{m_j} := g_1^{m_1} \ldots g_n^{m_n} \ \ \ \ \ (1)$

for some integers ${m_1,\ldots,m_n}$, with the obvious group law. Indeed, to obtain existence of this representation, one starts with any representation of ${g}$ in terms of the generators ${g_1,\ldots,g_n}$, and then uses the abelian property to push the ${g_1}$ factors to the far left, followed by the ${g_2}$ factors, and so forth. To show uniqueness, we observe that the group ${G}$ of formal abelian products ${\{ g_1^{m_1} \ldots g_n^{m_n}: m_1,\ldots,m_n \in {\bf Z} \} \equiv {\bf Z}^k}$ is already a ${\leq 1}$-step nilpotent group with marked elements ${g_1,\ldots,g_n}$, and so there must be a homomorphism from the free group to ${G}$. Since ${G}$ distinguishes all the products ${g_1^{m_1} \ldots g_n^{m_n}}$ from each other, the free group must also.

It is only slightly more tricky to describe the free nilpotent group ${{\mathcal F}_{\leq 2}(g_1,\ldots,g_n)}$ of step ${\leq 2}$. Using the identities

$\displaystyle gh = hg [g,h]; \quad gh^{-1} = ([g,h]^{-1})^{g^{-1}} h^{-1} g; \quad g^{-1} h = h [g,h]^{-1} g^{-1}; \quad g^{-1} h^{-1} := [g,h] g^{-1} h^{-1}$

(where ${g^h := h^{-1} g h}$ is the conjugate of ${g}$ by ${h}$) we see that whenever ${1 \leq i < j \leq n}$, one can push a positive or negative power of ${g_i}$ past a positive or negative power of ${g_j}$, at the cost of creating a positive or negative power of ${[g_i,g_j]}$, or one of its conjugates. Meanwhile, in a ${\leq 2}$-step nilpotent group, all the commutators are central, and one can pull all the commutators out of a word and collect them as in the abelian case. Doing all this, we see that every element ${g}$ of ${{\mathcal F}_{\leq 2}(g_1,\ldots,g_n)}$ has a representation of the form

$\displaystyle g = (\prod_{j=1}^n g_j^{m_j}) (\prod_{1 \leq i < j \leq n} [g_i,g_j]^{m_{[i,j]}}) \ \ \ \ \ (2)$

for some integers ${m_j}$ for ${1 \leq j \leq n}$ and ${m_{[i,j]}}$ for ${1 \leq i < j \leq n}$. Note that we don’t need to consider commutators ${[g_i,g_j]}$ for ${i \geq j}$, since

$\displaystyle [g_i,g_i] = id$

and

$\displaystyle [g_i,g_j] = [g_j,g_i]^{-1}.$

It is possible to show also that this representation is unique, by repeating the previous argument, i.e. by showing that the set of formal products

$\displaystyle G := \{ (\prod_{j=1}^k g_j^{m_j}) (\prod_{1 \leq i < j \leq n} [g_i,g_j]^{m_{[i,j]}}): m_j, m_{[i,j]} \in {\bf Z} \}$

forms a ${\leq 2}$-step nilpotent group, after using the above rules to define the group operations. This can be done, but verifying the group axioms (particularly the associative law) for ${G}$ is unpleasantly tedious.

Once one sees this, one rapidly loses an appetite for trying to obtain a similar explicit description for free nilpotent groups for higher step, especially once one starts seeing that higher commutators obey some non-obvious identities such as the Hall-Witt identity

$\displaystyle [[g, h^{-1}], k]^h\cdot[[h, k^{-1}], g]^k\cdot[[k, g^{-1}], h]^g = 1 \ \ \ \ \ (3)$

(a nonlinear version of the Jacobi identity in the theory of Lie algebras), which make one less certain as to the existence or uniqueness of various proposed generalisations of the representations (1) or (2). For instance, in the free ${\leq 3}$-step nilpotent group, it turns out that for representations of the form

$\displaystyle g = (\prod_{j=1}^n g_j^{m_j}) (\prod_{1 \leq i < j \leq n} [g_i,g_j]^{m_{[i,j]}}) (\prod_{1 \leq i < j < k \leq n} [[g_i,g_j],g_k]^{n_{[[i,j],k]}})$

one has uniqueness but not existence (e.g. even in the simplest case ${n=3}$, there is no place in this representation for, say, ${[[g_1,g_3],g_2]}$ or ${[[g_1,g_2],g_2]}$), but if one tries to insert more triple commutators into the representation to make up for this, one has to be careful not to lose uniqueness due to identities such as (3). One can paste these in by ad hoc means in the ${s=3}$ case, but the ${s=4}$ case looks more fearsome still, especially now that the quadruple commutators split into several distinct-looking species such as ${[[g_i,g_j],[g_k,g_l]]}$ and ${[[[g_i,g_j],g_k],g_l]}$ which are nevertheless still related to each other by identities such as (3). While one can eventually disentangle this mess for any fixed ${n}$ and ${s}$ by a finite amount of combinatorial computation, it is not immediately obvious how to give an explicit description of ${{\mathcal F}_{\leq s}(g_1,\ldots,g_n)}$ uniformly in ${n}$ and ${s}$.

Nevertheless, it turns out that one can give a reasonably tractable description of this group if one takes a polycyclic perspective rather than a nilpotent one – i.e. one views the free nilpotent group as a tower of group extensions of the trivial group by the cyclic group ${{\bf Z}}$. This seems to be a fairly standard observation in group theory – I found it in this book of Magnus, Karrass, and Solitar, via this paper of Leibman – but seems not to be so widely known outside of that field, so I wanted to record it here.

— 1. Generalisation —

The first step is to generalise the concept of a free nilpotent group to one where the generators have different “degrees”. Define a graded sequence to be a finite ordered sequence ${(g_\alpha)_{\alpha \in A}}$ of formal group elements ${g_{\alpha}}$, indexed by a finite, totally ordered set ${A}$, where each ${g_\alpha}$ is assigned a positive integer ${\hbox{deg}(g_\alpha)}$, which we call the degree of ${g_\alpha}$. We then define the degree of any formal iterated commutator of the ${g_\alpha}$ by declaring the degree of ${[g,h]}$ to be the sum of the degrees of ${g}$ and ${h}$. Thus for instance ${[[g_{\alpha_1},g_{\alpha_2}],g_{\alpha_3}]}$ has degree ${\hbox{deg}(g_{\alpha_1}) + \hbox{deg}(g_{\alpha_2}) + \hbox{deg}(g_{\alpha_3})}$. (The ordering on ${A}$ is not presently important, but will become useful for the polycyclic representation; note that such ordering has already appeared implicitly in (1) and (2).)

Define the free ${\leq s}$-step nilpotent group ${{\mathcal F}_{\leq s}( (g_\alpha)_{\alpha \in A} )}$ generated by a graded sequence ${(g_\alpha)_{\alpha \in A}}$ to be the group generated by the ${g_\alpha}$, subject to the constraint that any iterated commutator of the ${g_\alpha}$ of degree greater than ${s}$ is trivial. Thus the free group ${{\mathcal F}_{\leq s}(g_1,\ldots,g_k)}$ corresponds to the case when all the ${g_i}$ are assigned a degree of ${1}$.

Note that any element of a graded sequence of degree greater than ${s}$ is automatically trivial (we view it as a ${0}$-fold commutator of itself) and so can be automatically discarded from that sequence.

We will recursively define the free ${\leq s}$-step nilpotent group of some graded sequence ${(g_\alpha)_{\alpha \in A}}$ in terms of simpler sequences, which have fewer low-degree terms at the expense of introducing higher-degree terms, though as mentioned earlier there is no need to introduce terms of degree larger than ${s}$. Eventually this process exhausts the sequence, and at that point the free nilpotent group will be completely described.

— 2. Shift —

It is convenient to introduce the iterated commutators ${[g,mh]}$ for ${m=0,1,2,\ldots}$ by declaring ${[g,0h] := g}$ and ${[g,(m+1)h] := [[g,mh],h]}$, thus for instance ${[g,3h] = [[[g,h],h],h]}$.

Definition 1 (Shift) Let ${s \geq 1}$ be an integer, let ${(g_\alpha)_{\alpha \in A}}$ be a non-empty graded sequence, and let ${\alpha_0}$ be the minimal element of ${A}$. We define the (degree ${\leq s}$) shift ${(g_\alpha)_{\alpha \in A'}}$ of ${(g_\alpha)_{\alpha \in A}}$ by defining ${A'}$ to be formed from ${A}$ by removing ${\alpha_0}$, and then adding at the end of ${A}$ all commutators ${[\beta,m\alpha_0]}$ of degree at most ${s}$, where ${\beta \in A \backslash \{\alpha_0\}}$ and ${m \geq 1}$. For sake of concreteness we order these commutators lexicographically, so that ${[\beta,m\alpha_0] \geq [\beta',m'\alpha_0]}$ if ${\beta >\beta'}$, or if ${\beta=\beta'}$ and ${m > m'}$. (These commutators are also considered to be larger than any element of ${A \backslash \{ \alpha_0\}}$). We give each ${[\beta,m\alpha_0]}$ a degree of ${\hbox{deg}(\beta) + m \hbox{deg}(\alpha_0)}$, and define the group element ${g_{[\beta,m\alpha_0]}}$ to be ${[g_\beta,m g_{\alpha_0}]}$.

Example 1 If ${s \leq 3}$, and the graded sequence ${g_a,g_b,g_c}$ consists entirely of elements of degree ${1}$, then the shift of this sequence is given by

$\displaystyle g_b, g_c, g_{[b,a]}, g_{[b,2a]}, g_{[c,a]}, g_{[c,2a]}$

where ${[b,a], [c,a]}$ have degree ${2}$, and ${[b,2a]}$, ${[c,2a]}$ have degree ${3}$, and ${g_{[b,a]} = [g_b,g_a]}$, ${g_{[b,2a]} = [g_b,2g_a]}$, etc.

The key lemma is then

Lemma 2 (Recursive description of free group) Let ${s \geq 1}$ be an integer, let ${(g_\alpha)_{\alpha \in A}}$ be a non-empty graded sequence, and let ${\alpha_0}$ be the minimal element of ${A}$. Let ${(g_\alpha)_{\alpha \in A'}}$ be the shift of of ${(g_\alpha)_{\alpha \in A}}$. Then ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} )}$ is generated by ${g_{\alpha_0}}$ and ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A'} )}$, and furthermore the latter group is a normal subgroup of ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} )}$ that does not contain ${g_{\alpha_0}}$. In other words, we have a semi-direct product representation

$\displaystyle {\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} ) = {\bf Z} \ltimes {\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A'} )$

with ${g_{\alpha_0}}$ being identified with ${(1,id)}$ and the action of ${{\bf Z}}$ being given by the conjugation action of ${g_{\alpha_0}}$. In particular, every element ${g}$ in ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} )}$ can be uniquely expressed as ${g = g_\alpha^{n_\alpha} g'}$, where ${g' \in {\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A'} )}$.

Proof: The argument will be motivated by the identities

$\displaystyle g_{\alpha_0}^{-1} [g_\beta,mg_{\alpha_0}] g_{\alpha_0} = [g_\beta,mg_{\alpha_0}] [g_\beta,(m+1)g_{\alpha_0}] \ \ \ \ \ (4)$

and its inverse

$\displaystyle g_{\alpha_0} [g_\beta,mg_{\alpha_0}] g_{\alpha_0}^{-1} = [g_\beta,mg_{\alpha_0}] [g_\beta,(m+2)g_{\alpha_0}] \ldots ([g_\beta,(m+1)g_{\alpha_0}] [g_\beta,(m+3)g_{\alpha_0}] \ldots)^{-1} \ \ \ \ \ (5)$

(note that the products terminate in finite time due to nilpotency). In particular, we of course have

$\displaystyle [[g_\beta,mg_{\alpha_0}], g_{\alpha_0}] = [g_\beta,(m+1)g_{\alpha_0}]. \ \ \ \ \ (6)$

We now form a semi-direct product

$\displaystyle G := {\bf Z} \ltimes {\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A'} ).$

To do this, we need a conjugation action of ${(1,id)}$ on ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A'} )}$. Inspired by the identities (4), (5), we define this action on generators by mapping

$\displaystyle g_{[\beta,m\alpha_0]} \mapsto g_{[\beta,m\alpha_0]} g_{[\beta,(m+1)\alpha_0]} \ \ \ \ \ (7)$

and inverted via the mapping

$\displaystyle g_{[\beta,m\alpha_0]} \mapsto (g_{[\beta,m\alpha_0]} g_{[\beta,(m+2)\alpha_0]} \ldots) (g_{[\beta,(m+1)\alpha_0]} g_{[\beta,(m+3)\alpha_0]} \ldots)^{-1}. \ \ \ \ \ (8)$

Note that this map and its inverse preserve the degree of the generators, and so by the definition of the weighted free group this defines an automorphism on ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A'} )}$. By construction, we have the counterpart of (6):

$\displaystyle [ g_{\beta,m\alpha_0}, (1,id) ] = g_{\beta,(m+1)\alpha_0}. \ \ \ \ \ (9)$

The group ${G}$ is generated by ${(1,id)}$ together with the ${g_\alpha}$ for ${\alpha \in A'}$. Giving ${(1,id)}$ the degree of ${\hbox{deg}(\alpha_0)}$, one checks by hand (using plenty of commutator identities, as well as (9)) that any iterated commutator of generators with total degree greater than ${s}$ in ${G}$ is trivial. Thus there is a homomorphism from ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} )}$ to ${G}$ which maps ${g_{\alpha_0}}$ to ${(1,id)}$ and ${g_\alpha}$ to ${g_\alpha}$ for all ${\alpha \in A \backslash \{\alpha_0\}}$. Comparing (6) with (9) with, we see that this homomorphism also maps ${[g_\beta,mg_{\alpha_0}]}$ to ${g_{[\beta,m\alpha_0}]}$.

On the other hand, there is an obvious homomorphism from ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A'} )}$ to ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} )}$ that maps ${g_{[\beta,m\alpha_0]}}$ to ${[g_\beta,mg_{\alpha_0}]}$, and from the compatibility of (4), (5) with (7), (8) we may extend this homomorphism to a homomorphism from ${G}$ to ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} )}$ which also maps ${(1,id)}$ to ${g_{\alpha_0}}$. By checking this homomorphism on generators, we see that this map inverts the previous homomorphism from ${{\mathcal F}_{\leq s}( ( g_\alpha)_{\alpha \in A} )}$ to ${G}$, and so the two groups are isomorphic, as required. $\Box$

We can now iterate this. Observe that every time one shifts a non-empty graded sequence, one removes one element (the minimal element ${g_{\alpha_0}}$) but replaces it with zero or more elements of higher degree. Iterating this process, we eventually run out of elements of degree one, then degree two, and so forth, until the sequence becomes completely empty. We glue together all the elements encountered this way and refer to the full sequence as the completion ${(g_\alpha)_{\alpha \in \overline{A}}}$ of the original sequence ${(g_\alpha)_{\alpha \in A}}$. As a corollary of the above lemma we thus have

Corollary 3 (Explicit description of free nilpotent group) Let ${s \geq 1}$ be an integer, and let ${(g_\alpha)_{\alpha \in A}}$ be a graded sequence. Then every element ${g}$ of ${{\mathcal F}_{\leq s}( (g_\alpha)_{\alpha \in A})}$ can be represented uniquely as

$\displaystyle \prod_{\alpha \in \overline{A}} g_\alpha^{n_\alpha}$

where ${n_\alpha}$ is an integer, and ${\overline{A}}$ is the completion of ${A}$.

Example 2 We continue with the sequence ${g_a,g_b,g_c}$ from Example 1, with ${s = 3}$. We already saw that shifting once yielded the sequence

$\displaystyle g_b, g_c, g_{[b,a]}, g_{[b,2a]}, g_{[c,a]}, g_{[c,2a]}.$

Another shift gives

$\displaystyle g_c, g_{[b,a]}, g_{[b,2a]}, g_{[c,a]}, g_{[c,2a]}, g_{[c,b]}, g_{[c,2b]}, g_{[[b,a],b]}, g_{[[c,a],b]},$

and shifting again gives

$\displaystyle g_{[b,a]}, g_{[b,2a]}, g_{[c,a]}, g_{[c,2a]}, g_{[c,b]}, g_{[c,2b]}, g_{[[b,a],b]}, g_{[[c,a],b]}, g_{[[b,a],c]},$

$\displaystyle g_{[[c,a],c]}, g_{[[c,b],c]}.$

At this point, all remaining terms in the sequence have degree at least two, and further shifting simply removes the first element without adding any new elements. Thus the completion is

$\displaystyle g_a, g_b, g_c, g_{[b,a]}, g_{[b,2a]}, g_{[c,a]}, g_{[c,2a]},$

$\displaystyle g_{[c,b]}, g_{[c,2b]},g_{[[b,a],b]}, g_{[[c,a],b]}, g_{[[b,a],c]}, g_{[[c,a],c]}, g_{[[c,b],c]}$

and every element of ${{\mathcal F}_{\leq 3}(g_a,g_b,g_c)}$ can be uniquely expressed as

$\displaystyle g_a^{n_a} g_b^{n_b} g_c^{b_c} [g_b,g_a]^{n_{[b,a]}} [g_b,2g_a]^{n_{[b,2a]}}$

$\displaystyle [g_c,g_a]^{n_{[c,a]}} [g_c,2g_a]^{n_{[c,2a]}} [g_c,g_b]^{n_{[c,b]}} [g_c,2g_b]^{n_{[c,2b]}}$

$\displaystyle [[g_b,g_a],g_b]^{n_{[[b,a],b]}} [[g_c,g_a],g_b]^{n_{[[c,a],b]}} [[g_b,g_a],g_c]^{n_{[[b,a],c]}}$

$\displaystyle [[g_c,g_a],g_c]^{n_{[[c,a],c]}} [[g_c,g_b],g_c]^{n_{[[c,b],c]}} .$

In a recent paper of Leibman, a related argument was used to expand bracket polynomials (a generalisation of ordinary polynomials in which the integer part operation ${x \mapsto \lfloor x \rfloor}$ is introduced) of degree ${\leq s}$ in several variables ${(x_\alpha)_{\alpha \in A}}$ into a canonical basis ${(x_\alpha)_{\alpha \in \overline{A}}}$, where ${\overline{A}}$ is the same completion of ${A}$ that was encountered here. This was used to show a close connection between such bracket polynomials and nilpotent groups (or more precisely, nilsequences).