Mikołaj Bojańczyk

## 4. Factorisation trees

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 equipped with a product operation which is associative.

Let be a semigroup. Define an -factorisation tree to be a tree where nodes are labelled by elements of , subject to the following restrictions:
a) if a node has children with labels , read from left to right, then its label is the product ;
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 ).  Define the height of a tree to be the biggest number of edges on a root-to-leaf path. We are interested in creating -factorisation trees of small height. Clearly every word of length is the yield of some -factorisation tree of height at most , 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 ‘s modulo two.

Example. Consider the semigroup  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.

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

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

For a semigroup , define to be the smallest number such that every word in is the yield of some -factorisation tree of height at most . The theorem says that is finite for every finite .

Consider a surjective semigroup morphism . If is an idempotent in , then its inverse image under is easily seen to be closed under multiplication, and therefore is a subsemigroup of .

Lemma 1. If  is a surjective semigroup morphism, then

where ranges over idempotents in .

Proof.  Let be a word. First create a factorisation tree for the word in obtained from by applying to every letter. Let us look at this tree as a candidate for an -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 , corresponding to some idempotent . Let be the infixes of that correspond to the children of this idempotent node; their products in belong to the subsemigroup . Therefore we can combine them into an -factorisation tree, which is also an -factorisation tree.

Let us now prove the Factorisation Tree Theorem. The proof is by induction on the size of the semigroup. Let be a semigroup. In order to use the induction assumption, we will try to use Lemma 1. Consider a morphism like in Lemma 1, and the inequality in the conclusion of the lemma. If is not a bijection, then the semigroup is strictly smaller than . If has an image of size at least two, then every semigroup of the form is also smaller than . Therefore, if  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 be a -class which is as simple as possible (unlike for monoids, a semigroup need not have a unique -class that is simplest). Let be the set of -classes in and consider the function

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

Lemma 2. The function is compositional.

Proof. We need to show that and uniquely determine . First observe that if either or is zero, which means that either or is outside ,  then also , by choice of as lightest possible -class, and therefore is zero.  Consider now the case when . From Green’s relations it follows that membership is uniquely determined by the -classes of and , and so is the -class of if .

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

The remaining case is when is a bijection. This means that every -class in is a singleton, and there is at most one element outside , call this element zero. The element zero , if it exists, satisfies .

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

where and have nonzero type, and each is chosen so that has zero type. Therefore, a tree for can be obtained by combining the zeros of using an idempotent node, and then adding using a binary node (if it is nonempty).

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

Note that these infixes cannot use the zero, so they are actually in .

The base case is when 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 . Let

be a decomposition of which identifies all appearances of the infix . By induction assumption, trees of small height can be found for each  used in the above decomposition. If , then these trees can be combined using the binary rule. Suppose that , and consider the words

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