Repetitions in Words: Branching Out from Dejean's theorem

这项拟议的研究是在一个相对较新的数学领域，称为词的组合学。单词是取自某个有限字母表的一系列字母。相关的例子有计算机读取的长二进制字符串，或生物学家分析的DNA/RNA长序列。广义地说，词的组合学是研究词中的模式和结构。近年来，计算机在这一领域扮演着越来越重要的角色，无论是在产生实验证据方面，还是作为证明结果的工具。与此同时，随着大数据的兴起，需要了解长词的结构已成为一个关键挑战。这导致了组合学对单词的结果在不同领域的几个实际应用，包括生物信息学、文本和自然语言处理、通信技术和结晶学。在组合学中研究关于词的模式的典型例子是正方形。正方形是xx形式的词，其中x是一个非空词。例如，英语单词MURMUR是一个正方形。如果一个词不包含方块作为因子，则它是无方块的。例如，英语单词Apple和banana不是无正方形的，因为它们分别包含作为因数的正方形pp和anan，而单词哈密瓜则是无正方形的。在二十世纪初，阿克塞尔·图建立了一个令人惊讶的结果：在字母表上有任意长的不含正方形的单词，只有三个字母。方块符合单词重复这一更普遍的主题。方块的指数是2，因为它们是由一个较短的单词组成的，这个单词恰好重复两次。英语单词紫花苜蓿的指数为7/3，因为它可以通过将较短的单词alf恰好重复7/3次而形成。虽然Thue证明了三个字母上存在任意长度的无正方形的单词，但一个更强的结果实际上是正确的--三个字母上的任意长单词的指数因子不超过7/4。事实上，这是最有可能的，因为三个字母上的每个足够长的单词都包含至少7/4的指数因子。这意味着三个字母的重复阈值是7/4。Dejean定理通过许多作者在大约40年的工作中得到证明，给出了每种可能的字母表大小的重复阈值的值。换句话说，在任何固定的字母表上，德简定理准确地描述了可以避免的重复，以及不可避免地在足够长的单词中出现的重复。所提出的研究将通过理论和计算方法对Dejean定理的几个加强和变形取得进展。这项工作将扩大我们对单词重复的知识，并将导致关于单词的组合数学的新方法和新技术的发展。这项工作预期了在博弈论和图论中的理论应用以及实际应用的潜力。

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.