Two combinatorial properties of partitions of the free semigroup into finitely many parts (Q760429): Difference between revisions

Let \(A^+\) be the free semigroup over an alphabet A. Given a map \(\phi: A^+\to E\) into a set E and a positive integer k, we say that a word \(w\in A^+\) is a k-th power mod \(\phi\) if there is a factorisation \(w=w_ 1w_ 2...w_ k\) with \(w_ i\in A^+\) and, for all i, j, \(\phi (w_ i)=\phi (w_ j).\) A k-th power mod \(\phi\) has its gaps bounded by p if each of its components \(w_ i\) satisfies \(| w_ i| \leq p\). A k-th power mod \(\phi\) is uniform if, for all i, j, \(| w_ i| =| w_ j|.\) A map \(\phi: A^+\to E\) is strongly repetitive if, for any \(w\in A^+\), there is a positive integer p such that, for every positive integer k, w contains a factor which is a k-th power mod \(\phi\) with gaps bounded by p. A map \(\phi: A^+\to E\) is uniformly repetitive if, for every positive integer k, there is a positive integer m such that any word over A of length at least m contains a factor which is uniform k-th power mod \(\phi\). A semigroup S is strongly repetitive (uniformly repetitive, respectively) if, for any finite alphabet A, any morphism \(\phi: A^+\to S\) is strongly repetitive (uniformly repetitive, respectively). The authors prove following theorems. Theorem 1. For any alphabet A, containing at least two letters, there is a partition of \(A^+\) into two parts which is not uniformly repetitive. Theorem 2. For any alphabet A,\(| A| \geq 2\), there is a partition of \(A^+\) into 3 classes which is not strongly repetitive.