Repetitions in Words: Branching Out from Dejean's theorem

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

• 批准号: RGPIN-2021-04084
• 负责人: Mol, Lucas
• 金额: $ 0.78万
• 依托单位: Thompson Rivers University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742860
• 关键词: 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是一个非空单词。例如，英语单词“杂音”是一个正方形。如果一个单词不包含作为因数的平方，那么它就是无平方的。例如，英语单词apple和banana不是无方形的，因为它们分别包含正方形pp和anan作为因子，而单词cantaloupe是无方形的。在20世纪早期，阿克塞尔·图伊（Axel Thue）建立了一个令人惊讶的结果，即在只有三个字母的字母表上存在任意长的无方形单词。方形符合单词重复的更普遍的主题。正方形的指数是2，因为它们是由一个恰好重复两次的较短单词组成的。英语单词alfalfa的指数是7/3，因为它可以通过重复较短的单词half正好7/3次而形成。虽然Thue证明了存在超过三个字母的任意长无平方词，但一个更强大的结果实际上是正确的——存在超过三个字母的任意长词，其指数因子不大于7/4。事实上，这是最好的选择，因为每个足够长的单词都包含至少7/4的指数因子。这说明三个字母的重复阈值是7/4。德让定理（Dejean’s theorem）是经过许多作者近40年的努力证明的，它给出了每种可能字母表大小的重复阈值。换句话说，在任何固定的字母表中，德让定理精确地描述了可以避免的重复，以及在足够长的单词中不可避免地出现的重复。本研究将从理论和计算两方面对德让定理进行若干强化和改进。这项工作将扩大我们对单词重复的认识，并将导致单词组合学新方法和新技术的发展。这项工作预期了博弈论和图论的理论应用，以及实际应用的潜力。