Chapter 4 - Sesquipowers

Summary

Introduction

In this chapter we shall be concerned with sesquipowers. Any nonempty word is a sesquipower of order 1. A word w is a sesquipower of order n if w = uvu, where u is a sesquipower of order n — 1. Sesquipowers have many interesting combinatorial properties which have applications in various domains. They can be defined by using bi-ideal sequences.

A finite or infinite sequence of words f₁,…,f_n,… is called a bi-ideal sequence if for all i > 0, f_i is both a prefix and a suffix of f_i+1 and, moreover, 2|f_i| ≤ |f_i+1|. A sesquipower of order n is then the nth term of a bi-ideal sequence. Bi-ideal sequences have been considered, with different names, by several authors in algebra and combinatorics (see Notes).

In Sections 4.2 and 4.3 we analyze some interesting combinatorial properties of bi-ideal sequences and the links existing between bi-ideal sequences, recurrence and n-divisions. From these results we will obtain in Section 4.4 an improvement (Theorem 4.4.5) of an important combinatorial theorem of Shirshov. We recall (see Lothaire 1983) that Shirshov's theorem states that for all positive integers p and n any sufficiently large word over a finite totally ordered alphabet will have a factor f which is a pth power or is n-divided, i.e., f can be factorized into nonempty blocks as f = x₁ … x_n with the property that all the words that one obtains by a nontrivial rearrangement of the blocks are lexicographically less than f.