Repetitions in Words: Branching Out from Dejean's theorem

点击翻译按钮获取中文摘要

The proposed research is in a relatively new field of mathematics called combinatorics on words. A word is a sequence of letters taken from some finite alphabet. Relevant examples are the long binary strings read by computers, or the long sequences of DNA/RNA that are analysed by biologists. Broadly speaking, combinatorics on words is the study of patterns and structures in words. In recent years, computers have played an increasingly important role in the field, both for generating experimental evidence, and as tools for proving results. At the same time, the need to understand the structure of long words has become a key challenge with the rise of big data. This has led to several practical applications of results from combinatorics on words in diverse areas including bioinformatics, text and natural language processing, communication technology, and crystallography. The prototypical example of a pattern studied in combinatorics on words is the square. A square is a word of the form xx, where x is a nonempty word. For example, the English word murmur is a square. A word is square-free if it contains no squares as factors. For example, the English words apple and banana are not square-free, since they contain the squares pp and anan as factors, respectively, while the word cantaloupe is square-free. In the early twentieth century, Axel Thue established the surprising result that there are arbitrarily long square-free words over alphabets with just three letters. Squares fit into the more general theme of repetitions in words. Squares have exponent 2, since they are made up of a shorter word that is repeated exactly twice. The English word alfalfa has exponent 7/3, as it can be formed by repeating the shorter word alf exactly 7/3 times. While Thue showed that there are arbitrarily long square-free words over three letters, a stronger result is actually true - there are arbitrarily long words over three letters that contain no factor of exponent greater than 7/4. In fact, this is best possible, since every long enough word on three letters contains a factor of exponent at least 7/4. This says that the repetition threshold for three letters is 7/4. Dejean's theorem, which was proven through the work of many authors over approximately 40 years, gives the value of the repetition threshold for every possible alphabet size. In other words, over any fixed alphabet, Dejean's theorem describes exactly the repeitions that can be avoided, and the repetitions that must inevitably occur in long enough words. The proposed research will make progress on several strengthenings and variations of Dejean's theorem through both theoretical and computational methods. This work will expand our knowledge of repetitions in words, and will lead to the development of new methods and techniques in combinatorics on words. This work has anticipated theoretical applications in game theory and graph theory, and the potential for practical applications.