Commutator collecting process

In mathematical group theory, the commutator collecting process is a method for writing an element of a group as a product of generators and their higher commutators arranged in a certain order. The commutator collecting process was introduced by Philip Hall and Wilhelm Magnus. The process is sometimes called a "collection process".

The process can be generalized to define a totally ordered subset of a free magma; this subset is called the Hall set. Members of the Hall set are trees; these can be placed in one-to-one correspondence with words, these being called the Hall words; the Lyndon words are a special case. Hall sets are commonly used to construct a basis for a free Lie algebra.

Statement

The commutator collecting process is usually stated for free groups, as a similar theorem then holds for any group by writing it as a quotient of a free group.

Suppose F₁ is a free group on generators a₁, ..., a_m. Define the descending central series by putting

F_n+1 = [F_n, F₁]

The basic commutators are elements of F₁ defined and ordered as follows.

• The basic commutators of weight 1 are the generators a₁, ..., a_m.
• The basic commutators of weight w > 1 are the elements [x, y] where x and y are basic commutators whose weights sum to w, such that x > y and if x = [u, v] for basic commutators u and v then v ≤ y.

Commutators are ordered so that x > y if x has weight greater than that of y, and for commutators of any fixed weight some total ordering is chosen.

Then F_n/F_n+1 is a finitely generated free abelian group with a basis consisting of basic commutators of weight n.

Then any element of F can be written as

$g=c_{1}^{n_{1}}c_{2}^{n_{2}}\cdots c_{k}^{n_{k}}c$

where the c_i are the basic commutators of weight at most m arranged in order, and c is a product of commutators of weight greater than m, and the n_i are integers.

Hall set

The Hall set is a totally ordered subset of a free magma that employs the same construction as above. Let $A={a_{1},\cdots ,a_{n}}$ be a set of generators, and let $M(A)$ be the free magma over $A$. The free magma is simply the set of non-associative strings in the letters of $A$, with parenthesis retained to show grouping. Equivalently, the free magma is the set of all binary trees whose leaves are elements of $A$.

The Hall set $H\subset M(A)$ can be constructed recursively as follows:

• The Hall set contains the generators: $A\subset H$
• A commutator $[x,y]\in H$ if and only if $x\in H$ and $y\in H$ and $x>y$ and:
  • Either $x\in A$ (and thus $y\in A$),
  • Or $x=[u,v]$ with $u\in H$ and $v\in H$ and $v\leq y$.

This is effectively the same construction as above, without any mention of groups. The ordering is according to the length of the strings; strings of equal length are given arbitrary but fixed order. This is the same ordering as the above-given for groups, with the weights being the string-lengths. These definitions all coincide with that of Viennot. Note that some authors reverse the order of the inequality.

Example

Consider the generating set with two elements $\{a,b\}.$ Define $a>b$ and write $(xy)$ for $[x,y]$ to simplify notation. The initial members of the Hall set are then (in order)

${\begin{aligned}&b,a,\\&ab,\\&(ab)b,\;\;(ab)a,\\&((ab)b)b,\;\;((ab)b)a,\;\;((ab)a)a,\\&(((ab)b)b)b,\;(((ab)b)b)a,\;(((ab)b)a)a,\;(((ab)a)a)a,\;((ab)b)(ab),\;((ab)a)(ab),\\&\cdots \end{aligned}}$

Notice that there are $2,1,2,3,6,\cdots$ elements of each distinct length. This is the beginning sequence of the necklace polynomial in two elements (described next, below).

Combinatorics

A basic result is that the number of elements of length $k$ in the Hall set (over $n$ generators) is given by the necklace polynomial

$M_{n}(k)\ =\ {1 \over k}\sum _{d\,|\,k}\mu \!\left({k \over d}\right)n^{d}={1 \over k}\sum _{d\,|\,k}\mu \!\left({d}\right)n^{k/d}$

where $\mu$ is the classic Möbius function. The sum is a Dirichlet convolution.

Applications

Besides their usefulness for providing a total order for group elements, Hall sets are used to construct a basis for free Lie algebras.

History

Hall sets were introduced by Marshall Hall based on work of Philip Hall on groups. Subsequently, Wilhelm Magnus showed that they arise as the graded Lie algebra associated with the filtration on a free group given by the lower central series. This correspondence was motivated by commutator identities in group theory due to Philip Hall and Witt.

Hall word

Hall words are obtained from the Hall set by "forgetting" the commutator brackets, but otherwise keeping the notion of total order. Hall words can be placed into one-to-one correspondence with the Hall trees; thus, knowing a word is sufficient to deduce the corresponding tree. This follows from the factorization theorem below.

Factorization

The foliage of a magma $M(A)$ is the canonical mapping $f:M(A)\to A^{*}$ from the magma to the free monoid $A^{*}$, given by $f:a\mapsto a$ for $a\in A$ and $f:[x,y]\mapsto f(x)f(y)$ otherwise. The foliage is just the string consisting of the leaves of the tree, that is, taking the tree written with commutator brackets, and erasing the commutator brackets.

Let $[x,y]\in H$ and $w=f([x,y])$ be the corresponding Hall word. Given a factorization of a Hall word $w=uv$ into two non-empty strings $u$ and $v$, then there exists a factorization into Hall trees such that $u=f(x_{1})\cdots f(x_{m})$ and $v=f(y_{1})\cdots f(y_{n})$ with $x_{1},\cdots ,x_{m}>y_{1}$ and $y_{1}\leq y_{2}\leq \cdots \leq y_{n}\leq y.$

From the factorization theorem above, Hall words can be uniquely factorized into ascending order. That is, every Hall word $w$ can be written as a concatenation of other Hall words

$w=c_{1}c_{2}\cdots c_{k}$

with each Hall word $c_{j}$ being totally ordered by the Hall ordering:

$c_{1}\leq c_{2}\leq \cdots \leq c_{k}.$

This is again analogous to the result for groups.

Further combinatorics of Hall trees are given by Guy Melançon.

See also

• Hall–Petresco identity

Reading

• Hall, Marshall (1959), The theory of groups, Macmillan, MR 0103215
• Huppert, B. (1967), Endliche Gruppen (in German), Berlin, New York: Springer-Verlag, pp. 90–93, ISBN 978-3-540-03825-2, MR 0224703, OCLC 527050