Mikołaj Bojańczyk

Define a nontrivial prefix of a word to be a prefix which is neither empty nor full. The following lemma shows that the Factorisation Tree Theorem holds for groups.

Lemma. If is a finite group, then every is the yield of some -factorisation tree of height at most 3 times the size of where is the set of types of nontrivial prefixes of .

Proof. The lemma is proved by induction on the size of .  If this set is empty,  then the word has one letter, and therefore has a -factorisation tree consisting only of a leaf.

Let us therefore focus on the induction step. Consider a word with nonempty, and let  . Cut the word in all places where we find a nontrivial prefix of type . In other words, consider a factorisation

such that the only nontrivial prefixes of with type are

By choice of the factorisation,   is a subset of that does not contain , and therefore the induction assumption can be applied to . For similar reasons, if then   is a subset of that does not contain . Note that multiplying a subset  of a group by on the left does not affect its cardinality, and therefore each has smaller size than , and therefore the induction assumption can be applied as well. Summing up, to every we can apply the induction assumption.

If then the type of goes from to ,  and in a group there is only one such element, namely the identity. Therefore all words have type which is the group identity, and therefore an idempotent node can be used to group all of them into a single tree. To this tree, the words and can be added using a binary rule. This construction creates a tree whose height is 3 plus the maximal height of any tree for , thus completing the proof of the lemma.