On the Billaud Conjecture and related problems

The Billaud Conjecture, which has been open since 1993, is a fundamental problem on finite words $w$ and their heirs, i.e., the words obtained by deleting every occurrence of a given letter from some word $w$. The Conjecture posits that every morphically primitive word, i.e., a word which is only a fixed point of the identity on the set of symbols of the word, has at least one morphically primitive heir.

In this thesis we introduce the Conjecture, and give a comprehensive overview of the current state of knowledge about it. In particular, we recall the known special cases in which the Conjecture holds. Based on the previous special case results we develop a `blueprint' for solving the Conjecture for an arbitrary alphabet size, i.e., we identify an enumeration of the cases which need to be solved in order to prove the Billaud Conjecture for a fixed alphabet size. We apply the blueprint to the proof of the next major case of the Conjecture, i.e., the case for quaternary alphabets, and discuss the potential for generalising our reasoning to larger alphabets.

Subsequently, we introduce and investigate the related class of so-called Billaud words, i.e., words whose all heirs are morphically imprimitive. We provide a characterisation of morphically imprimitive Billaud words, using a new concept. We show that there are two phenomena through which words can have morphically imprimitive heirs, and we highlight that only one of those occurs in morphically primitive words. We examine our concept further, and we use it to rephrase and study the Billaud Conjecture in more detail.

Finally, we relate the notions associated with the Billaud Conjecture to other concepts available in the literature. In particular, we show that the Conjecture can be expressed as a problem of characterising the outcome of the application of a synchronised shuffle operation to certain classes of languages. We assert that these classes of languages are expressible using the so-called pattern expressions, which we show are not closed under the synchronised shuffle. Finally, we show equivalence of a relevant class of pattern expression languages to a certain kind of languages of regular expressions extended with backreferences.