Repetitions in Words: Branching Out from Dejean's theorem

这项拟议中的研究是在一个相对较新的数学领域，称为单词组合学。一个单词是从某个有限的字母表中取出来的字母序列。相关的例子是计算机读取的长二进制字符串，或生物学家分析的长DNA/RNA序列。从广义上讲，词的组合学是对词的模式和结构的研究。近年来，计算机在该领域发挥着越来越重要的作用，无论是生成实验证据，还是作为证明结果的工具。与此同时，随着大数据的兴起，理解长词结构的需求已经成为一个关键挑战。这导致了组合数学在不同领域的一些实际应用，包括生物信息学，文本和自然语言处理，通信技术和晶体学。在组合数学中研究的模式的典型例子是正方形。一个正方形是一个xx形式的单词，其中x是一个非空单词。例如，英语单词murmur是一个正方形。如果一个词不包含任何平方因子，那么这个词就是无平方因子的。例如，英语单词apple和banana不是无平方数的，因为它们分别包含平方数pp和anan作为因子，而单词cantalume是无平方数的。在世纪早期，阿克塞尔·图（Axel Thue）得出了一个令人惊讶的结果：在只有三个字母的字母表上，存在任意长的无平方词。正方形适合于更普遍的单词重复主题。正方形的指数为2，因为它们是由一个较短的词组成的，这个词重复了两次。英文单词alfalfa的指数为7/3，因为它可以通过将较短的单词alf重复7/3次来形成。虽然图厄表明，有任意长的平方超过三个字母的话，一个更强的结果实际上是真的-有任意长的话超过三个字母，不包含指数大于7/4的因素。事实上，这是最好的可能性，因为每一个足够长的三个字母的单词都包含一个至少为7/4的指数因子。三个字母的重复阈值是7/4。德让定理，这是通过许多作者的工作证明了大约40年，给出了每一个可能的字母表大小的重复阈值的值。换句话说，在任何固定的字母表上，德让定理精确地描述了可以避免的重复，以及在足够长的单词中不可避免地出现的重复。 本文的研究将从理论和计算两个方面对德让定理的几种强化和变形进行改进。这项工作将扩大我们的知识重复的话，并将导致新的方法和技术的发展组合的话。这项工作预期在博弈论和图论的理论应用，并在实际应用中的潜力。

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.