4. Factorisation trees

Mikołaj Bojańczyk

zajęcia / courses

In this part, it will be technically more convenient to talk about semigroups. A semigroup is like a monoid, except that it does not need to have an identity element. In other words, a semigroup is a set $S$ equipped with a product operation $S^+ \to S$ which is associative.

Let $S$ be a semigroup. Define an $S$ -factorisation tree to be a tree where nodes are labelled by elements of $S$ , subject to the following restrictions:
a) if a node has children with labels $s_1,\ldots,s_n$ , read from left to right, then its label is the product $s_1 \cdots s_n$ ;
b) if a node has more than two children, all of these children have the same label, and this label is an idempotent.
Nodes with more than two children are called idempotent nodes. We also assume that every non-leaf node has at least two children, and therefore children that have exactly two children are called binary rules.

Define the yield of a tree to be the sequence of leaf labels read from left to right (this is a word in $S^+$ ). Define the height of a tree to be the biggest number of edges on a root-to-leaf path. We are interested in creating $S$ -factorisation trees of small height. Clearly every word of length $n$ is the yield of some $S$ -factorisation tree of height at most $\log n$ , which does not use idempotent nodes, and is constructed by recursively splitting the word in two parts. As the following example shows, using idempotent nodes can decrease the height of a tree to a constant, e.g. at most 6 for the morphism which counts $a$ ‘s modulo two.

Example. Consider the semigroup $\{0,1\}$ with addition modulo 2.

Every word with only zeros has a factorisation tree of height at most 1, by combining all the zero leaves using an idempotent root.
Every word with exactly two ones has a factorisation tree of height at most 4, by using binary nodes to combine the trees for the blocks of zeros with the two ones.
Every word with an even number of ones has a factorisation tree of height at most 5, by combining the trees from the previous item using an idempotent root.
Every word with an odd number of ones has a factorisation tree of height at most 6, by using the previous item and using a binary root to append the extra one with its trailing zeros.

Therefore, every word has a factorisation tree of height at most 6. $\Box$

As shown by Imre Simon, the above example generalises to all semigroups.

Theorem (Factorisation Tree Theorem). For every finite semigroup $S$ , there is a constant $k$ such that every word in $S^+$ is the yield of an $S$ -factorisation tree of height at most $k$ .

For a semigroup $S$ , define $height(S) \in \mathbb N \cup \{\infty\}$ to be the smallest number $k$ such that every word in $S^+$ is the yield of some $S$ -factorisation tree of height at most $k$ . The theorem says that $height(S)$ is finite for every finite $S$ .

Consider a surjective semigroup morphism $h : S \to T$ . If $e$ is an idempotent in $T$ , then its inverse image under $h$ is easily seen to be closed under multiplication, and therefore is a subsemigroup of $S$ .

Lemma 1. If $h : S \to T$ is a surjective semigroup morphism, then

$height(S) \le height(T) \cdot \max_{e } height (h^{-1}(e))$

where $e$ ranges over idempotents in $T$ .

Proof. Let $w \in S^+$ be a word. First create a factorisation tree $t$ for the word in $T^+$ obtained from $w$ by applying $h$ to every letter. Let us look at this tree as a candidate for an $S$ -factorisation tree. The leaf nodes are correct, and the binary nodes are correct, because they do not depend on the structure of the semigroup. The only issue is with the idempotent nodes. Consider an idempotent node in the tree $t$ , corresponding to some idempotent $e \in T$ . Let $w_1,\ldots,w_n$ be the infixes of $w$ that correspond to the children of this idempotent node; their products in $S$ belong to the subsemigroup $h^{-1}(e)$ . Therefore we can combine them into an $h^{-1}(e)$ -factorisation tree, which is also an $S$ -factorisation tree. $\Box$

Let us now prove the Factorisation Tree Theorem. The proof is by induction on the size of the semigroup. Let $S$ be a semigroup. In order to use the induction assumption, we will try to use Lemma 1. Consider a morphism $h$ like in Lemma 1, and the inequality in the conclusion of the lemma. If $h$ is not a bijection, then the semigroup $T$ is strictly smaller than $S$ . If $h$ has an image of size at least two, then every semigroup of the form $h^{-1}(e)$ is also smaller than $S$ . Therefore, if $h$ is nontrivial, i.e. it is not a bijection and has image of size at least two, then we can apply the induction assumption to all semigroups that appear on the right side of the inequality in Lemma 1.

Let $J$ be a $\Jj$ -class which is as simple as possible (unlike for monoids, a semigroup need not have a unique $\Jj$ -class that is simplest). Let $J/\Hh$ be the set of $\Hh$ -classes in $J$ and consider the function

$h : S \to J{/\Hh} \sqcup \{0\}$

which maps each element of $J$ to its $\Hh$ -class, and which maps other elements to a designated zero element.

Lemma 2. The function $h$ is compositional.

Proof. We need to show that $h(s)$ and $h(t)$ uniquely determine $h(st)$ . First observe that if either $h(s)$ or $h(t)$ is zero, which means that either $s$ or $t$ is outside $J$ , then also $st \not \in J$ , by choice of $\Jj$ as lightest possible $\Jj$ -class, and therefore $h(st)$ is zero. Consider now the case when $s,t\in J$ . From Green’s relations it follows that membership $st \in J$ is uniquely determined by the $\Hh$ -classes of $s$ and $t$ , and so is the $\Hh$ -class of $st$ if $st \in J$ . $\Box$

From the above lemma it follows that $h$ is a semigroup morphism, with an appropriate semigroup structure on its image. Therefore, if $h$ is nontrivial then we can use the induction assumption and Lemma 1. The remaining case is when $h$ is a trivial, i.e. $h$ maps all elements to a single one, or $h$ is a bijection. When $h$ maps all elements to a single one, this means that all of the semigroup is in a single $\Hh$ -class, which means that the semigroup is a group, by the $\Hh$ -dichotomy lemma proved here. The group case is considered here.

The remaining case is when $h$ is a bijection. This means that every $\Hh$ -class in $J$ is a singleton, and there is at most one element outside $J$ , call this element zero. The element zero $0$ , if it exists, satisfies $s0=0s=0$ .

First observe, that the interesting case is words which have type other than zero. If a word has zero type, then it admits a decomposition

$w = w_1 s_1 w_2 s_2 \cdots w_n s_n w_{n+1}$

where $w_1,\ldots,w_{n} \in S^+$ and $w_{n+1} \in S^*$ have nonzero type, and each $s_i$ is chosen so that $w_i s_i$ has zero type. Therefore, a tree for $w$ can be obtained by combining the zeros of $w_is_i$ using an idempotent node, and then adding $w_{n+1}$ using a binary node (if it is nonempty).

We are therefore left with finding trees of small height for words $w \in S^+$ that have nonzero type. We prove this by induction on the number of two-letter infixes, i.e. the following parameter:

$[w] = \{ st \in S^2 : \text{$w$ has an infix $st$ }\}$

Note that these infixes cannot use the zero, so they are actually in $J^2$ .

The base case is when $w$ has no two-letter infixes, i.e. it has length one, and therefore a factorisation tree of height zero. For the induction step, choose some two letter infix $st \in J^2$ . Let

$w = w_0 st w_1 st w_2 \cdots w_{n} st w_{n+1}$

be a decomposition of $w$ which identifies all appearances of the infix $st$ . By induction assumption, trees of small height can be found for each $w_i$ used in the above decomposition. If $n \in \{0,1\}$ , then these trees can be combined using the binary rule. Suppose that $n \ge 2$ , and consider the words

$tw_1s, \quad \ldots \quad tw_ns.$

They all have the same $\Rr$ -class, namely that of $t$ , and they all have the same $\Ll$ -class, namely that of $s$ , and therefore they all have the same type by assumption on all $\Hh$ -classes being singletons. Furthermore, this type is idempotent, because also $tw_1stw_2s$ has this type. Therefore, the idempotent rule can be used to combine all of the above words into a single tree.

zajęcia / courses

4. Factorisation trees

Leave a Reply