The three-squares lemma for partial words with one hole (Q418740)

Partial words are words containing unknown symbols at some positions. Such positions are called holes. A lot of effort is being devoted to answering the natural question, which of the known properties of (full) words can be observed in partial words as well. One such property is expressed by the three-squares lemma, an important tool in attempts to prove the conjecture that the number of distinct squares in a word of length \(n\) is always less than \(n\). The lemma states that in any word, if \(w^{2}\), \(v^{2}\), and \(u^{2}\) are three squares starting at the same position, \(|w|<|v|<|u|\), \(v\notin w^{\ast}\), and \(w\) is primitive, then \(|u|+|v|\leq|u|\).NEWLINENEWLINEIn partial words, a square has the form \(uu^{\prime}\), where \(u^{\prime}\) is compatible with \(u\). Two partial words are compatible if they are of the same length and they differ only at some of the positions where one of them contains a hole. The paper provides a generalization of the three-squares lemma for partial words with one hole. The generalization is a corollary of a theorem with more detailed results about the relative size of the squares. The quite painstaking proof of the theorem is divided into several steps, provided in six sections of the paper.