Group case

Mikołaj Bojańczyk

zajęcia / courses

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$

zajęcia / courses

Group case

Leave a Reply