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 G is a finite group, then every w \in G^+ is the yield of some G-factorisation tree of height at most 3 times the size of [w] where [w] \subseteq G is the set of types of nontrivial prefixes of w.

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

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

    \[w = w_1 w_2 \cdots w_n\]

such that the only nontrivial prefixes of w with type g are

    \[w_1, \quad w_1w_2, \quad \ldots, \quad  w_1 \cdots w_{n-1}\]

By choice of the factorisation,  [w_1] is a subset of [w] that does not contain g, and therefore the induction assumption can be applied to [w_1]. For similar reasons, if i \ge 2 then  g \cdot [w_i] is a subset of [w] that does not contain g. Note that multiplying a subset  of a group by g on the left does not affect its cardinality, and therefore each [w_i] has smaller size than [w], and therefore the induction assumption can be applied as well. Summing up, to every w_1,\ldots,w_n we can apply the induction assumption.

If i \in \{2,\ldots,n-1\} then the type of w_i goes from g to g,  and in a group there is only one such element, namely the identity. Therefore all words w_2,\ldots,w_{n-1} 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 w_1 and w_n can be added using a binary rule. This construction creates a tree whose height is 3 plus the maximal height of any tree for w_1,\ldots,w_n, thus completing the proof of the lemma. \Box



Leave a Reply

Your email address will not be published.