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.
Leave a Reply