Repetitions in Words: Branching Out from Dejean's theorem

文字中的重复：德让定理的分支

• 批准号: RGPIN-2021-04084
• 负责人: Mol, Lucas
• 金额: $ 0.53万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742861
• 关键词: Repetitions; Words; Branching; Out; 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.

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