（基础数学专业论文）sturmian序列和字典序.pdf

华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 i 摘摘 要要 sturmian 序列在符号动力系统中起着很重要的作用，以及在组合学、遍历理论 中，甚至在计算机科学理论、生物学和物理学等领域中也是如此。 由定义知：sturmian 序列是复杂度函数为 + 1 的序列，即是非周期序列中复 杂度最小的序列。序列还有许多等价定义，比如旋转序列、平衡序列、 christoffel词。 本文主要研究的是 sturmian 序列的性质与字典序，其结构如下：第一章是绪论 部分；第二章介绍 sturmian 序列的性质和等价定义；第三章介绍了字典序，进一步 又研究了 sturmian序列的比较（对应于字典序）并讨论了 sturmian序列的动力学性 质；第四章主要研究字典序词对，特别地，通过特征 sturmian 序列，我们得到关于 映射的像集的一个新刻画。 关键词关键词：sturmian序列，旋转序列，平衡序列，字典序。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 ii abstract sturmian sequences play a very important role in symbolical dynamical systems, as well as in many other fileds such as combinatorics on words, ergodic theory, and even in theoretical computer science, biology, physics, etc. by definition, sturmian sequences are those with complexity +1; in other words, they are the sequences with minimal complexity among all aperiodic ones. there are many equivalent definitions of sturmian sequences under different names such as rotation sequences, balanced sequences and christoffel words. in this thesis, we study sturmian sequences and the lexicographic order. and the thesis is organized as follows: after an introductory chapter (chap.1), several equivalent definitions and some properties of sturmian sequences are presented in chapter 2; in chapter 3, the lexicographic order is introduced and then the comparison (with respect to the lexicographic order) of sturmian sequences is studied, also the dynamical properties of sturmian sequences are discussed. in the last chapter, the lexicographic world is studied and, in particular, a new characterization of the image of the mapping phi in terms of characteristic sturmian sequences is obtained. keywords: sturmian sequence, rotation sequence, balanced sequence, lexicographic order. 独创性声明 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的 研究成果。近我所知，除文中已标明引用的内容外，本论文不包含任何其他人或集 体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文 中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权数。 本论文属于 不保密。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 1 绪绪 论论 1.1 1.1 问题研究的背景及意义问题研究的背景及意义 人类对自然界的研究和观测都是在一定的精度下进行的，其目的就是对客观事 物或者过程的基本不变的性质得到精确的结论。精度的测量很自然的就会带来很多 的数据，而且真正用以刻画事物根本性质的特征量不是很多。为了得到这些可以描 述事物性质的特征量，不一定非要从大量的原始数据出发，符号序列就是在有限的 精度下考查复杂系统的一个有效的工具。 符号动力学，作为动力系统理论中的抽象章节已经有很悠久的历史了。从 20 世 纪 20 年代开始作为数学家证明的有力手段。而符号动力系统是形式上最简单的动力 系统，是一种高度的概括。 符号动力学的状态空间或相空间就是符号序列空间，动力学是由位移操作来实 现的。对一个特定的符号序列，从初始点出发，不断地转换位置，就可以得到一串 新的序列，即是相空间的一串点，这些点就组成一条轨道，这个过程就是一个动力 学过程。正如1所说的那样，一方面基于传统的无穷小分析的微分理论难以施展时， 基于粗粒化的符号动力学仍能发挥作用；另一方面，一般的数值方法解决不了的地 方它仍能提供定性分析的工具。 根据文献2所说的，符号序列的应用可追溯到 1851 年，1921 年 morse 第一次发 现符号动力学方法对研究动力学系统的重要性3。1938 年 morse 和 hedlund 研究动 力系统拓扑理论的一篇文章，标题为符号动力学 4。接着 bowen、ruelle 和 sinai 等人在微分动力系统方面又发展了符号动力学，文献1中对这个有详细的介绍。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 2 现在对符号序列的研究已深入到物理学、生物学、化学以及计算机科学等领域。 对符号动力系统的研究主要有以下两个方面：一是从符号动力学的应用角度出发， 给出其在物理学、微分方程和混沌等方面的应用，二是从组合数学的角度出发，对 符号序列的组合结构以及性质进行了探讨性的研究。 对符号序列来说，我们可以把它看作是有限字母表上的形式语言，而对形式语 言语法复杂性的研究是符号序列中一个非常重要的研究方向。 sturmian序列是一个 2元字母表上的无穷符号序列，且对每一正整数，它的长为 + 1 的因子恰好有 + 1 个，所以也就是说 sturmian序列是语言复杂度为 +1 的无穷序列。 sturmian 序列是具有最小语言复杂度的非最终周期的序列，所以是形式语言中 应用的最为广泛的一种序列，它在计算机图形学、博弈论、丢番图逼近论和准晶体 图形学等方面都有广泛的研究。 最早对 sturmian 序列深入研究的是 morse 和 hedlund5,6，他们说明了，从某种 意义上，sturmian 序列是一种最简单的非平凡序列，并且给出了 sturmian 序列的两 个简单的组合解释，“sturmian”这个术语，更精确的说是 sturmian序列轨道，是他们 在 1943 年提出来的， 是以数学家 charles francois sturm(1803-1855)的名字命名的 （见 7） 。 sturmian序列动力系统可以应用在代数学、数论、物理学和计算机科学等领域 中4。我们知道，一个动力系统的粗粒化描述可以用一条无限的符号序列来表示。因 此 sturmian序列引起了包括数学家、物理学家和生物学家在内的许多科学工作者的 广泛注意和高度重视。特别是准晶体结构的发现，更加引起了数学物理工作者对 sturmian序列的关注，那是由于它可被看作是一个简单的以为准晶体模型1,2。 sturmian序列有许多的等价定义，每一个等价定义都可以说明 sturmian序列的 一个特殊性质，这些等价定义包括 beatty序列3,8、平衡序列、切割序列和旋转序列 等等。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 3 1.2 1.2 文献综述文献综述 sturmian序列最早出现在18世纪天文学家 bernoulli9的初期著作中， 在19世纪， christoffel10和 markov11的著作中也出现了 sturmian序列。 最早开始深入研究 sturmian序列的数学家 morse 和 hedlund5,6，也是他首先提 出了 sturmian 序列这个概念。他们主要表明了，从某种意义上，sturmian 序列是一 种最简单的非平凡序列，而且还给出了 sturmian 序列的两个简单的组合解释， “sturmian”这个术语，更精确的说是 sturmian 轨道，是他们在 1943 年提出来的，是 以数学家 charles francois sturm(1803-1855)的名字命名的（见7） 。 sturmian 序列动力系统可以应用在代数学、数论、物理学和计算机科学等领域 中4。我们知道，一个动力系统的粗粒化描述可以用一条无限的符号序列来表示。因 此 sturmian 序列引起了包括数学家、物理学家和生物学家在内的许多科学工作者的 广泛注意和高度重视。特别是准晶体结构的发现，更加引起了数学物理工作者对 sturmian序列的关注，那是由于它可被看作是一个简单的以为准晶体模型1,2。 sturmian 序列有许多不同的定义方式，有些是从几何角度定义的，另外有些是 组合学的方法定义的。 coven和 hedlund 的文章12和 coven的文章13讨论了sturmian 序列的组合性质。而 stolarsky 在他的文章14中主要研究了连分数、不动点和 beatty 序列之间的关系。 从 20 世纪末以来，越来越多的数学家对这个序列产生了兴趣，sturmian序列有 很多特殊性质，特别的是，sturmian 序列是建立在 2 元字母表上并具有最小复杂度 的序列，同时也是平衡的序列。 本文主要是研究 sturmian序列和字典序词对， 在 sturmian序列的性质的基础上， 通过特征 sturmian序列，我们得到关于映射的像集的一个新刻画。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 4 1.3 1.3 本文的结构及安排本文的结构及安排 本文总共分为四章，其主要内容如下： 第一章是绪论部分，主要内容包括问题研究的背景及意义；回顾前人所研究的 成果。 第二章介绍了相关的基础知识，包括词和序列，sturmian 序列的性质及其等价 定义平衡序列和旋转序列的一些性质。 第三章介绍了字典序，进一步又研究 sturmian 序列的比较（对应于字典序）并 讨论了 sturmian序列的动力学性质。 第四章主要研究字典序词对，特别地，通过特征 sturmian 序列，我们得到关于 映射的像集的一个新刻画。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 5 2 预备知识预备知识 在本节中，我们将给出一些相关的定义、记号、基础知识和相关结果，具体可 以参见文献15的第二章。 2.1 2.1 词和序列词和序列 设 = 1,2 , 是一个包含个元素的集合，我们称是一个有限字母表， 其中的元素为字母表中的字母。如果 = 012 = 012 ， 其中 , 1 ，那么称有限字符串（无穷字符串）为有限词（无限词或 序列） 。如果词是有限词，则用符号 表示有限词的长度，此时 = 。长度 为零的词称为空词， 用符号表示。 字母出现在词中的次数就用符号 来表示。 表示定义在字母表上的所有有限词的集合， a表示定义在字母表上的所有无限 词（或序列）的集合，表示定义在字母表上的所有有限词和无限词的集合，即 = 。 在中定义一个词上的运算，称为拼接，即： = 01, = 01 ， = , 则 = 0101 。根据长度定义可知 = + 。 例如： = , ，若 = ，则 = 10， = 4， = 6。 如果存在词 , ，使得 = ，则称是的一个因子。如果 = ，则 称是词的前缀，记 = 。如果 = ，则称是词 的后缀，记 = 。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 6 如果 = 012， 那么称词 10 为词的镜像词， 用符号 表 示。如果 = ，那么称词为回文词。 + 称为词的回文右闭词，即 + 是以词 为前缀的最短回文词。 对于无限词 （或序列） ， 如果 = ， 则称序列是纯周期的； 如果 = ， 则称是最终周期的。对于有限词 = 012，如果存在 ，使得 = +，对任意的 1 都成立，则称为词的周期。显然，对任意大 于等于 的整数都是词的周期。由此可见，如果是词的周期，则 = ，其中 = / ，符号“ ”表示小于等于的最大整数，也就是数的整 数部分，符号“ ”表示大于等于的最小整数，符号“ ”表示数的小数部分。此时， 我们不妨记 = ，其中 = 。例如： = 容易看出5是词 的周期，记 = ，则 = 2 = 2 2 5 = 12 5 。 如果序列的每个因子都在中出现无数次，那么称为常返的；如果对任意， 存在相应的，使得每个长度为的因子中出现所有长度为的因子，那么称为一致 常返的。 把有限词 （无限词或序列） 的所有因子构成的集合称为的语言， 用符号 表 示。 而 表示的长度为的语言， 即的长度为的因子集， 用符号 , 或 表示。 对于给定的一个序列，一个重要的工作是计算它的复杂度函数 , (或 )。现在我们给出复杂度函数的概念：定义在字母表上的有限词或序列，对 于任意的，复杂度函数 , 表示中长度为的因子的个数，即： , = , 。 很显然， ,0 = 1，即长度为零的词只有空词一个。而 ,1 恰好等于中所出 现的字母的个数。 如果是序列，则中的每个因子都可以向右延拓，因此有 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 7 , , +1 ， 又因为 , + , , ， 所以有 , + , , 。 这个函数已经在各类文献中都有广泛的研究，具体可以参考文献16。 命题命题 2.115 设是一个序列，以下四个结论相互等价： （1）序列是最终周期的； （2） , 有界； （3）存在一个正整数，使得 , ； （4）存在一个正整数，使得 , = , + 1 。 证明： （1）（2）因为是最终周期的，所以有 = 。 所以 , + ，从而有界。 （2）（3） 显然。 （3）（4） 因为存在 使得 , ，而 ,0 ,1 , 1 , 则其中必有 一个取等号，否则 , ， , 1 1, ,0 0。矛盾。 所以（4）成立。 （4）（1） 对于的长度为的任意因子，其延拓也是的因子，又因为 , = , + 1 ， 所以长度为的的延拓唯一。所以若 +1 +1= +1 +1， 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 8 则 += +，以此类推 += +，对任意成立，所以 += +。 所以是最终周期的。得证。 2.2 sturmian2.2 sturmian 序列及其等价定义序列及其等价定义 定义定义 2.2 如果对于所有的 ， 序列的复杂度函数 , = + 1， 则称序列为 sturmian序列。 注： （1）sturmian序列是非最终周期的且 sturmian序列是复杂度函数最小的。 （2）由定义知 ,1 = 2，所以 sturmian序列都是定义在2元字母表上的序列。 因此，我们讨论 sturmian 序列时，总是假定它是定义在2元字母表 = 0,1 上的 符号序列。 是序列的因子，如果 , 也是序列的因子，则称是序列的右特殊因子； 如果 , 是序列的因子，则称是序列的左特殊因子，其中 。 我们有如下命题： 命题命题 2.3 是 sturmian序列当且仅当对任意的 ，的长为的特殊因子只有一 个。 定理定理 2.415 sturmian序列是一个常返的序列，或者说，sturmian序列中的任何一个因 子都会在序列中出现无数次。 证明：假设sturmian序列中长度为的因子在序列中只出现有限次，那么存在正 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 9 整数， 使得因子在序列的第个位置以后不再出现。 定义序列， 使得 = +。 因为因子不是序列的因子。故序列的复杂度函数有 ，根据命题 2.1 知 序列是最终周期的，故序列也是最终周期的，得出矛盾。得证。 注：特别地，sturmian序列也是一致常返的序列。 命题命题 2.5 如果序列是sturmian序列，那么因子00和11有且只有一个是序列的因 子。 我们再来给出sturmian序列的一种等价定义平衡序列： 设是定义在字母表 = 0,1 上的有限词。词的高度为包含1的个数，用符号 表示。任意给定义在字母表上的长度相等的词 ,，他们的平衡度用符号 , 表示，即： , = 。 定义定义 2.6 设是定义在字母表 = 0,1 上的有限词的集合，对于中任意两个长度 相等的词，如果 , 1，那么称是平衡的。 定义定义 2.7 设序列是定义在字母表 = 0,1 上的序列，任意取中长度相等的因子 ,，如果 , 1，那么称序列是平衡的。 对于一个有限词或序列来说，如果它的语言 是平衡的，那么也是平衡的；反 之，如果是平衡的，那么它的语言 也是平衡的。 我们有如下几个定理： 命题命题 2.8 设是一个有限词或序列的因子集，如果是平衡的，那么对于任意的 0，我们有 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 10 +1。 定义定义 2.9 非空词 w 的斜率 = 。 例如： = 010010101000,则 = 4, = 12, = 4 12。 很容易验证以下等式： = + 。 命题命题 2.10 集合是平衡的当且仅当对于任意给定的中词 , 有以下式子成立： 1 + 1 。 推论推论 2.11 s 是一个平衡序列，对于任意的 ，令表示为序列的 s 长度为 n 的 前缀，当 时，序列 1收敛。 证明：由命题 2.10 中满足的不等式可以推出序列 1 为 cauchy列，因此收 敛。 事实上，极限 = 就是序列 s 的斜率。 命题命题 2.12 假设 s 是斜率为的平衡序列，对于 s 的每个非空因子 u，都有不等式 1 。 成立。 确切的说，以下两个不等式只有一个成立： 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 11 1 +1， 或者 1 +1。 如果 是无理数，则以上不等式不可能取到等号。 命题命题 2.13 假设 s 是平衡序列，s 的斜率 是有理数当且仅当 s 是最终周期的。 在介绍了平衡序列及其性质以后， 我们接着引进一类与 sturmian序列等价的序列 （或 无限词）旋转词。 定义定义 2.14 给定两个实数 0,1 和 ，定义两个无限词： ,: ，, : ， 其中对任意的 ，有 , = +1 + + ， s, n = n+ 1 + n + ， 称无限词,为下旋转词，, 为上旋转词。 它们的斜率均为 ， 截距均为 。 容易验证， 对任意的 ， 旋转词 , 和 , 均取值于二元字母表 0,1 。当 时，旋转词 ,= ,; , = , ，所以我们不妨假设 0,1)。 由定义 2.14 可知， 0,= 0, = 0， 1,= 1, = 1。余下可设 0,1 ， 当 + 时， + = 1 + + ， 所以 , = , ； 而当 + 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 12 时， + = + ，此时 , = 0, = 1； , 1 = 1, , 1 = 0。 综上可知， 假如 是无理数时， ,与, 最多只有一个长度为2的因子不同。 假如一个词的斜率是有理数（无理数） ，则称该旋转词是有理的（无理的） 。 现在考虑一种特殊情况，即当 0 1, = 0 时，此时 ,0 0 = = 0， ,0 0 = = 1。又假设 是无理数，则对任意的，当 + 时，所以有 , = , ，所以 ,0= 0, ,0 = 1 。 其中是它们的共同后缀，而且 = ,，我们称为 的特征词。 定理定理 2.15 假设是一个序列，以下结论是等价的： 1) 是 sturmian序列； 2) 是非最终周期的平衡序列； 3) 是无理旋转词。 引理引理 2.16 （1） l s, = l s, 。 （2） l s, = l s, 。 命题命题 2.1715 （1）设是一个序列的语言 ，是不平衡的当且仅当存在一个回 文词，使得 00 和 11 在集合中。 （2） 设是一个序列的语言 ， 是不平衡的当且仅当存在一个词， 使得 00 和 11 在集合中。 （1）证明：充分性：显然成立。 必要性：假设是不平衡的，考虑两个相同的长度为 的 , 使得 , 2，且取它们为最短长度。 和 的第一个字母是不同的，对最后一个字 母也是如此，如果第一个是0，第一个是1，则有因式分解 = 0 和 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 13 = 1，但 。 事实上， = 0 和 = 1 否则 , = ， ，这与的极小性矛盾。因而， 再由极小性， = 00， = 11。 再假设不是回文词，则可以找到的一个后缀和字母，使得是的后缀，还有 的另一个后缀 ，但 不是的后缀，那么显然， 是的后缀，其中是其他字母。 这就给出一个的恰当的前缀 0 和的前缀 1。如果 = 0 和 = 1，那么， 00,1 1 = 2，这与的极小性矛盾。 但如果 = 01， = 1 0 ,且 , = , ，这又与极小性矛盾。 从而是回文词。 注：由（1）可以推出（2） ，所以直接证明（1）即可。结论（2）即是阻滞条件（block condition） 。 2.3 christoffel2.3 christoffel 词的定义（相对词的定义（相对斜率是有理数）斜率是有理数） 定义定义 2.18 设 p 和是两个互素的正整数，令 = +，如下定义两个有限词： ,= 011， ,= 011， 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 14 其中 = + 1 ， = +1 ，0 1。 则称 , 为下 christoffel词，, 为上 christoffel词。 引理引理 2.1917 序列是最终周期且是常返的，则是纯周期的序列。 引理引理 2.2015 假设是斜率为的旋转词，则是斜率为的平衡序列；假如是有理 数，则是纯周期的；假如是无理数，则是非最终周期的。 证明：不妨设 = , 是下旋转词（上旋转词的证明类似） 。 设 序 列 = + 1 + 1 的 高 度 为 = + + + 。 那么 1 1+。 与 1 矛盾。 令 = | + , + ， 由命题 2.12 知， 1； 当是无理数时， 1。因此当 0 时， + +1 （*） 否则存在整数，使得 + 1 + ，令 = + 1 ， 则 ，这与的定义矛盾。当是非周期序列时，是一无理数， 并且至多有一个整数，使得 + 是一整数，由（*）知，对于所有的，或者 = + ，这时 = ,；或者除了0之外的所有整数， = + ，即 = + 1 。这时 = ,。 如果 = 是一个周期为 = 的周期序列，那么的斜率 = ，其中 = = 。若 + 全不为整数， = + ；如果存在，使得 = +，我们可以得出 = + 。 否则，存在不妨设 + ， 由（*）式可知 1+ = +。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 16 考虑长为 的序列 = +1 + 2 和长为 的序列 = + 1 + 2 。 这时 = = 1 ， = + + = + 1 。 因此 = 1 + 1 。这与命题 2.10 矛盾。 类似地，如果存在，使得 1 += +， 那么 = + 。得证。 定理定理 2.22 假设是一个序列，则序列是常返且平衡的充要条件是是旋转词。 证明：充分性：常返性是显然成立的，再由引理 2.20 得知序列是平衡的。得证。 必要性： 由引理 2.13 知序列是最终周期的， 再由引理 2.19 知道是序列是纯周期的。 根据引理 2.21 得到是有理旋转词，得证。 注：“常返”条件是不能去掉的。可以考虑平衡序列01。由引理 2.20 知，旋转词不 可能是最终周期的，但非纯周期的。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 17 3 sturmian3 sturmian 序列的比较和动力学性质序列的比较和动力学性质 3.1 sturmiansturmian 序列的比较序列的比较 我们回忆定义 , = +1 + + ， , = +1 + + 。 注：(1)当是无理数时，即为 sturmian序列。 (2)当是有理数时， , 可以表示成是的后缀，是斜率表示成 = 的词。 下面设 0，1 （不要求是无理数） ，我们有 ,0= 0， ,0= 1， ,1= 10，,1= 01。 定义定义 3.1 集合 = 0，1 上字典序定义如下：对任意的 , ，我们称 小于 ，记作 ，如果存在 ，当 ,。 得证。 定理定理3.315 设 0 1 且 是无理数， , 满足 0 。 证明：因为是无理数，故存在 , 使得 + = + , = 0,。 + 1 + = + 1 + + 1 成立。也就是说 , 与 , 前 个位置都 是一样的，但有 , = 1， , + 1 = 0， , = 0， , + 1 = 1。 即 ,= 10， ,= 01。得证。 定理定理 3.4 如果 , 满足 0 1，那么有 , , 。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 19 证明： （1）前半部分是平凡的，由定理 3.2 即可以得到。 （2）下证后半部分： 0 = 2 ， 1 = 3 2 ， 0 = 2 ， 1 = 3 2 ， 当且仅当存在使得 = ， ， + 1 = +1 ， 但是有 +2 + 2 + 1 = +2 。 也就是说，, 有如下表示 = 1 , = 0。 从而我们可以得到 。得证。 3.2 3.2 动力系统性质动力系统性质 我们先来介绍动力系统的一些相关定义： 设是一个紧的度量的拓扑空间，: 为连续映射，我们一般将偶对 , 称为拓扑动力系统。 注：如果是双射并且1为连续的，就说为同胚，此时也 ，1 为动力系统。 对自然数，我们定义的次迭代为 = ， 并约定 0= （其 中表示恒同映射） 。 对 , 称 = , 为的轨道。如果是同胚映射，则可定义负 向轨道及双向轨道为 , = ,1, 及 + , = : 。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 20 （在为同胚时， 我们也经常把称 : 为轨道， 而 , 为正向轨道。 ） 定义定义 3.6 是紧的度量空间，其上的同胚映射 : 称为可迁的，如果对每个 ，都有它的轨道 : = ,1, 在中稠密。 定义定义 3.7 是紧的度量空间，其上的同胚映射 : 称为极小的，如果对每个 ，都有它的轨道 : = ,1, 在中稠密。 命题命题 3.8 设序列 0,1 ，则有 , 是一个动力系统，从而有如下结论： 序列是一致常返的当且仅当 , 是极小的。 定理定理 3.9 设序列 0,1 ，我们有 充分必要条件是 ， 如果序列是一致常返的，则有 充分必要条件是 = 。 引理引理 3.1015 如果序列和是 sturmian序列，且序列和有相同的斜率，那么 = 。 定理定理 3.11 如果 = ,，那么有 = ,: 0,1 ,: 0,1 。 证明：对任意的 0，1 ，由引理 3.9 知 , = , ， 那么有 ,: 0,1 ,: 0,1 。 另一方面由于是一致常返的，且若有 ，则有 = ，从而和 复杂度也是相同的，故也是 sturmian序列，即 = , 或者 = ,。再由 引理 3.9 知 = 。得证。 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 21 4 sturmian4 sturmian 序列与字典序序列与字典序词对词对 本章中，我们将研究字典序词对和 sturmian序列，通过特征 sturmian序列，我 们得到关于映射的像集的一个新刻画。 令 = 0,1 ，用 表示