（计算数学专业论文）关于sturm序列的因子结构.pdf

摘要 本文主要是研究s t u r m 序列因子的结构任取s t u r m 序列u 及其任意 一个因子”，从u 中依次删去这个因子w ，我们就会得到一个新的序列，称为 剩余序列然后，根据因子的不同，对剩余序列进行分类最后讨论剩余序列 在双射作用下的变化情况：其中大多数剩余序列可以通过双射变成s t u r m 序 列；另外的少数不能通过双射变成s t u r m 序列论文的主要内容如下； 第一章简要地介绍了s t u r m 序列和字上的组合的发展进程，以及现在关 于s t u r m 序列的一些研究课题 第二章详细介绍了s t u r m 序列的基础知识及其等价定义 第三章包含下述内容t 首先，因为s t u r m 序列是一个非周期的并且其语 言复杂度是最小的符号序列所以我们对于所研究的对象进行一些合理的限 制，将所研究的s t u r m 序列限制在标准s t u r m 序列及其斜率小于等于1 的序 列下面其次，利用标准字的长度严格单调递增的性质，将选定的因子的长度 限定在两个相邻的标准字的长度之间再次，根据选定的因子与一些特殊因子 之间的关系，分类研究其对应的剩余序列，从而得出剩余序列的因子的分类 最后，用原来的序列为s t u r m 序列的特点，得出如下结论：大多数类型的剩余 序列可以通过双射变成s t u r m 序列，有一小部分的剩余序列不能通过双射变 成s t u r m 序列 关键词：s t u r m 序罗j 标准字；字上的组合 a b s t r a c t i nt h i st h e s i sw em a i n l ys t u d yt h es t r u c t u r eo ft h ef a c t o r so fs t u r m i a ns e - q u e n c e s g i v e nb eas t u r m i a ns e q u e n c eu a n daf a c t o r o fu 1 e tu sd e l e t ei nt u r n a l l si nu w et h e ng e tan e ws e q u e n c e w h i c hi sc a l l e dar e m a i n i n gs e q u e n c e a c c o r d i n gt od i f f e r e n tf a c t o r s ，w eg i v eac l a s s i f i c a t i o nf o rt h er e m a i n i n gs e q u e n c e s f i n a l l y , w ed i s c u s st h er e m a i n i n gs e q u e n c e su n d e rb i j e c t i o n ：m o s to ft h e mc a nb e c h a n g e di n t oas t u r m i a ns e q u e n c eb yb i j e c t i o n w h i l eaf e wo ft h e m c a n tt u r ni n t oa s t u r m i a ns e q u e n c eb yb i j e c t i o n t h em a i nc o n t e n to ft h i si ss u m m a r i z e da sf o l l o w s ： i nt h ef i r s tc h a p t e r ，w eb r i e f l yi n t r o d u c et h ee v o l u t i o no nt h es t u r m i a ns e - q u e n c e sa n dc o m b i n a t o r i c so nw o r d s a sw e l l a ss o m et o p i c sa b o u ts t u r m i a ns e - q u e n c e si nr e c e n ty e a r s i nt h es e c o n dc h a p t e r ，w ei n t r o d u c et h ep r e l i m i n a r i e so fs t u r m i a ns e q u e n c e sa n d i t so t h e rd e f i n i t i o n s ，s u c ha sb a l a n c e ds e q u e n 亡e s ：c u t t i n gs e q u e n c e sa n dr o t a t i o n s e q u e n c e s ，e t c i nt h el a s tc h a p t e r ，t h em a i nr e s e 3 血i sa sf o l l o w s ：f i r s t l y , s i n c eas t u r m i a n s e q u e n c ei sa na p e r i o d i cs e q u e n c e sw i t h j i 出l a n g u a g ec o m p l e x i t y , w ec a l lm a k e s o m er e a s o n a b l ec o n s t r i c t i o nf o rt h e m ，t h a ti s ，l e tt h es t u r m i a ns e q u e n c e sb es t a a l - d a r da n dw i t hi t ss l o p el e s st h a n1 s e c o n d l y , b yt h ee x a c ti n c r e a s eo fl e n g t h so ft h e s t a n d a r dw o r d sw ec a nr e s t r i c tt h el e n g t ho ft h es e l e c t e df a c t o rb e t w e e nt h el e n g t h s o ft w oc o n s e c u t i v es t a n d a r dw o r d s t h i r d l y ，a c c o r d i n gt or e l a t i o n sb e t w e e nt h es e - l e c t e df a c t o ra n ds o m es p e c i a lf a c t o r s ，w es t u d yt h er e m a i n i n gs e q u e n c e s ，a n d 百v e ac l a s s i f i c a t i o no ft h ef a c t o r so fr e m a i n i n gs e q u e n c e s f i n a l l y , f r o mt h ep r o p e r t i e so f t h eo r i g i n a ls e q u e n c e s ，w eo b t a i nt h ec o n c l u s i o n ：m o s to ft h e mc a nb ec h a n g e di n t o as t u r m i a ns e q u e n c eb yb i j e c t i o n ，w h i l eaf e wo ft h e mc a tt u r ni n t oas t u r m i a n b yb i j e c t i o n k e y w o r d s ：s t u r n i a ns e q u e n c e s ；c o m b i n a t o r i c so nw o r d s ；s t a n d a r dw o r d s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或 其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所做 的贡献均已在论文中做了明确的说明并表示了谢意 作者签名： 关于s t u r m 序列的因子结构 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文 版权使用规是少，同意大连理工大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅本人授权大连理工大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、 缩印或扫描等复制手段保存和汇编学位论文 作者签名，逖叠 一名；至耄 塑年月! 日 一3 4 对于符号序列，我们可以将其看作是有限字母表上的形式语言 s t u r m 序列是两个字母表上的一个无限符号序列，并且对每个正整数1 2 ，它的长为n 的因子恰好有n + 1 个，因此我们简单的说s t u x m 序列是语言复杂度为n + l 的 无穷序列因为s t u r m 序列是具有最低语言复杂度的非周期序列，因此它是 形式语言中研究最为广泛的一类符号序列，在计算机图形学、博弈论、信号分 析、丢番图逼近、自动机和准晶图形学等方面都有广泛的应用 最早对s t u r m 序列进行研究的是m o r s e 和h e d l u n df 1 ，2 1 ，他们证明了在某 种意义上s t u r m 序列是一种最简单的非平凡序列并且给出了这些序列的两个 简单的组合解释“s t u r m ”这个术语，更精确的说，应该是s t u r m 轨道，是 他们在1 9 4 3 年提出来的，是以数学家c h s r l e sf r a n c o i ss t u r m ( 1 8 0 3 - 1 8 5 5 ) 的名 字所命名的，他因为在计算代数方程的根方面的成就而闻名于世的考虑微分 方程 ”+ f ( x ) v = 0 这里f ( x ) 是一个关于z 的周期为1 的连续函数设该方程的解为y = “( z ) ，则 正如m o r s e 和h e d l u n d 所描述的那样，一个s t u r m 序列可以用来刻画u 扛) = 0 的解的分布情况如果。表示“( z ) = 0 在区间h n + 1 】上的解的个数，则无 限序列 0 1 k 0 0 1 k 1 0 1 k 2 o l k - 是一个s t t t r m 序列 c o v e n 和h e d l u n d 的文章 3 】和c o v e n 的文章 4 】讨论了s t u r m 序列中的 许多组合性质而s t o l a r s k y 在他的文章 5 】中主要研究了连分式、不动点和 b e a t t y 序列之间的关系最近二十多年，对于s t u r m 序列的研究有了很大的 发展，主要是从算法、动力系统和字上的组合的角度进行研究 s t u r m 序列具有许多等价定义，每一个定义都反应了s t u r m 序列的一个 特定性质这些等价定义包括t w o - d i s t a n c e 序列( l u n n o na n dp l e a s a n t s 6 ) 、 关于s t u r m 序列的因子结构 b e a t t y 序列( d eb r u i j i n 7 ，8 ) 、b 越a n c e d 序列、c u t t i n g 序列和r o t a t i o n 序列 以及通过某些算法所作的定义通过构造一个算法来描述s t u r m 序列，给组 合数学和数论之间搭起了一座桥梁而利用因子所定义的s t u r m 序列恰好描 述了一个符号动力系统最先详细研究该序列的也是从这个角度出发的【2 】它 给出了平滑圆盘上的测地学的一个描述 对于s t u r m 序列组合结构的研究主要集中在利用其各种等价定义来得到 该序列的组合性质以及一些有关算法和几何上的性质【9 ，1 0 ，1 1 ，1 2 ，1 3 ，14 最近 研究最为广泛的是与s t u r m 序列相关的可逆替换的一些内容，特别是f i b o n a c d 替换关于可逆替换的文章请参考 1 5 1 6 ，1 7 1 下面简要介绍用组合的方法来研究s t u r m 序列的一些结果 c a o 和w e n 1 1 1 介绍了s t u r m 序列的一些组合性质，讨论了标准字、回 文、单字等一系列的组合性质，着重介绍了现阶段s t u r m 序列组合性质的几个 研究方面j u s t i n 和p k i l l of 1 3 1 主要研究s t t t r m 字的幂，在利用了连分式这个 主要工具和数学归纳法，计算了具有周期为m 的最长因子的长度函数l ( m ) d a m a n m 和l e n z 1 8 1 主要来解决s t u r m 序列索引的问题，在这篇文章中，也 是应用了数学归纳法得出了求索引的公式l 讧和w a n g 1 9 1 利用了s t u r m 序 列构造了一系列具有较高复杂度的序列，然后在这些序列的基础上，构造了新 的s t u r m 序列，并确定了新旧s t u r m 序列之间的关系 另外，文献【5 ，2 0 ，2 1 ，2 2 ，2 3 ，2 4 和 2 5 等，从组合的角度研究s t u r m 序 列，比如因子的幂、因子的交迭和回文等 也有不少文章是关于s u r m 序列或者s t u r m 字的序的研究，例如d a m a n i k 和l e n z 1 8 在求s t u r m 序列索引的同时，恰恰也给出了s t u r m 序列一个排序； 而关于s t u r m 字的排序文章则有更多，序的定义也有几种，例如字典序、半径 序、左因子序等关于序方面的文章请参考 2 6 ，2 7 ，2 8 作为有限字母表上的序列，有时也称作字，它们又是组合数学研究的对 象字上的组合研究最早要追溯到2 0 世纪初1 9 0 6 年t h u e 发表了它在重复 自由字方面的第一篇文章，这被认为是关于字上的数学的研究的起点，但是从 那以后的几十年，他的研究成果一直不被人们所知道后来在这方面陆续有了 一些比较分散的研究性文章，但在很多情况下，都是对t h u e 一开始所作的结 果的一些重复性的工作系统地进行字上的研究开始于2 0 世纪5 0 年代，分别 2 大连理工大学硕士学位论文 在巴黎和俄罗斯独立进行在法国这方面的研究开始于m p s c h t z e n b e r g e r ， 是为了对编码理论的研究在俄罗斯，关于字的理论主要是p s n o v i k o v 和 s a d i a n 为了解决群上b u r n s i d e 问题所利用的一种工具真正推动字上的组 合理论研究的是m l o t h a i r e 于1 9 8 3 年所写的一本书，书名正是叫做字上的 组合学( c o m b i n a t o r i c so nw o r d s ) 这本书覆盖了在那以前几乎所有这方面 的研究成果l o t h a i r e 于2 0 0 2 年出版了该书的第二卷字上的代数组合学 ( a l g e b r a i cc o m b i n a t o r i c so i lw o r d s ) 现在一个关于字的国际会议从1 9 9 7 年开 始每两年举行一次，最近的一次在2 0 0 5 年9 月1 3 1 7 号在加拿大的蒙特利尔 举行字上的组合不仅在数学，而且与其他许多学科都有紧密地联系，如计 算机科学、物理学和生物学等方面都有广泛的应用l o t h a i r e 还于2 0 0 5 年写 了一本名为字上的应用组合学( a p p l i e dc o m b i n a t o r i c so nw o r d s ) 的书，其 中主要介绍了在生物学以及在语言学方面的应用s t u r m 字在遍历性理论， 计算机图形学，和准晶等方面有许多应用关于字的组合的相关文章，请参看 2 9 ，2 8 ，3 0 ，3 1 ，3 2 ，3 3 ，3 4 ，3 5 ，3 6 ，3 7 ，3 8 ，3 9 ，如，4 1 关于准晶方面的相关文章参 看 4 2 ，4 3 ，4 4 ，4 5 ，4 6 ，4 7 ，4 8 本文中关于s t u r m 序列研究的出发点是基于下面的考虑：既然一个s t u r m 序列中的每个因子在其中出现无限多次，那么我们令该序列依照顺序删去该 因子，剩下的每一部分都是该序列的因子，由于s t u r m 序列自身的特殊性，那 么剩余的部分就有什么样的特征? 剩余的序列与原来的s t u r m 序列有什么关 系? 答案是这样的，由于被删除的因子选择的不同，剩余因子要么全是一样 的，或者有2 个( 3 个，4 个) 不同的情况并且剩余的序列大部分可以通过双 射变成s t u r m 序列，另外一小部分不能通过双射变成s t u r m 序列 一3 一 2s t u r m 序列及其等价定义 2 1s t u r m 序列的基础知识 设s = f 1 ，z 2 ，为具有k 个字母2 1 ，f 2 ，k 的字母表一个有限长 的字符串“= u l u 2 u 3 u 。，其中u i s ，称为s 上的字；然而一个无限长的字 符串u = “1 u 2 u 3 u 。，其中u t s ，称为s 上的序列记s 4 ( s “) 为s 上所 有字( 序列) 的集合 两个字u = u l u 2 u r 和 = 1 2 的连接定义为字“l “2 u r 1 2 并且记作u ”特别，u n 表示”个u 的连接个字和一个序列的连接可以类似 地定义在连接这种操作下，s 形成了一个含幺半群，其中单位元为空字s 一 个字w 的长度为这个字中包含字母的个数，记作川，空字e 的长度定义为0 ” 中包含字母z ( z s ) 的个数记作叫f 记七维向量l ( w ) 垒( f 1 】川f ：，卜 显然，l w i = | w l l ，+ p i l ：+ - - + l ”k 对于两个字u ，w ，如果存在两个字”1 ，”2 s + 满足w = ”1 u ”2 ，则称u 是w 的因子，记作u w 在这种情况下，记( 川；“) 为u 在7 1 ) 中的出现字或序 列在序列中的出现可以类似的定义如果w = 一，则称“( 或v ) 是”的左( 右) 因子，记为“qw ( 或u ) 对于一个字u 和一个序列f s “，如果存在一 个字”和一个序列f l 满足f = ”“e 1 ，则称u 是f 的一个因子，记作u f ； 如果u = 毛则称u 是f 的左因子，记作u 司f 设叫= z 1 茹n 和让= ( 2 ：r x r + 1 x n ) w ，字z 1 。2 z r - 1 记作 u 记 面= 。$ ，1 x 2 x 1 为 的逆如果 = 面，则称 为一个回文所有回文的 集合记作p 对于字”s ，如果w = u p j p = 1 ，则称”为本原的 对于w ，设w = 。1 $ 2 x i 。l 和0 k 川，那么定义 的第k 次 共轭为： 瓯扣) ：= z k + l 。i 。i x l x 2 k 的共轭的集合定义为： g ( ”) ：= ( g ) ；0 k 一5 关于s t u r m 序列的因子结构 考虑a 上的有限或无限字”，对于任意的n ，复杂性函数p ( n ，w ) 表示的是 w 的长为n 的因子的个数，即 p m ，w ) = c a r d ( f ( n ： ) ) 这里用f ( n ，”) 表示w 的所有长为n 的因子所构成的集合很显然，p ( o ，”) = 1 ， 而p ( 1 ，”) 恰好等于w 中所出现字母的个数如果w 是一个无限字，则w 的 每一个因子都可以向右扩展，因此就有 p ( 礼，训) p ( n + 1 叫) 又因为f ( n + m ，7 1 ) ) cf ( n ，) f ( m ，w ) ，所以有 p ( n + m ， ) p ：w 加( m ， ) 由复杂度函数可以这样定义s t u r m 序列：序列f 是s t u r m 序列当且仅当 对所有的n21 ，有p ( n ，f ) = n + 1 因为p ( 1 ，f ) = 2 ，所以任意s t u r m 序列都是两个字母表上的符号序列假 设f 是字母表 。，b ) 的序列若“是f 的一个因子，并且u 。和u b 也是f 的 因子，就称n 为f 的特殊因子由此有下面的命题 命题2 1 ( 2 8 ) f 是一个s t u r m 序列当且仅当对任意n ：f 长为n 的特殊因子恰 好只有一个 下面的命题给出s t u r m 序列因子的一个重要性质 命题2 2 ，( 4 9 ) 一个s t u r m 序列是循环发生的，也就是说，s t u r m 序列的任何 一个因子在它里面发生无穷多次 由s t u r m 序列的定义，很容易得到下面的结论 在s t u r m 序列u 中，a a ，b b 不可能同时存在，也就是说，a h 阢b 6 一 u 不同时成立 不妨设b 6 二：u ，则称b 在u 中独立存在 在用组合的方法来研究s t u r m 序列和s t u r m 字中，连分式起了非常重要 的作用，下面简单介绍一下连分式的相关知识 首先，对任意正整数序列( n 。) 。，o ，可以定义一个序列( z 。) 。，o 如下 一6 一 大连理工大学硕士学位论文 111 观2 石现。码一萨再i e 易知序列( 。) 。，o 收敛于实数z 相反的，任给无理数z 0 ，1 】，有且仅有一个唯一的正整数序列( a n ) 。，o 满 足。是它的极限记为 1 。2 i # 二车1 钆+ 再毒 习惯上记 将a o = m 替代初始值0 ，可以将z 扩展到所有的正的无理数上去即 。= c o = a l ，n 2 ，a - 在本节最后，我们给出几种序以及l y n d o n 字的定义 任给两个字x ，y n ，6 n 如果zqy ，则定义, 7 y ，这种序称之为左因子 序很显然，左因子序是一个偏序 另外两种序都是定义在有序字母表a = n _ 6 ) 上的它们都是全序 首先设a b 通过下面来定义半径序：任给两个字。，y ，则定义 fz y ，当h j yj ； l $ y ，当f z i = i g i 且。= u ，y = “时 下面给出字典序的定义： 任给两个字z ，y ，如果。qy ，则定义。 1 ) ，可以得到一条数值轨道 x o ，。i ，。n ，一 ( 2 1 ) 考虑丁上的两个区间如= 【0 ，o ) 和j 1 = b 1 ) ，定义编码函数“。为 州扣 毒嚣誊 数值序列( 2 ，1 ) 可以通过下面的符号序列来实现 卢o ( 。o ) ，b ( 。1 ) ，一，p n ( z 。) ，一( 2 2 ) 一9 一 关于s t u r m 序列的因子结构 这条序列也被称为由a 和卢所确定的r o t a t i o n 序列，记为r 伊由 2 j 我们知 道r o t a t i o n 序列和s t u r m 序列是等价的 定理2 2 ( 2 】) 每一个r o t a t i o n 序列是一个s t u r m 序列相反，对每一个s t u r m 序列f ，存在实数n 和寥使得咒，口= f 下面我们给出s t u r r a 序列的另一个等价定义 2 4 c u t t i n g 序列 任给无理数o 0 和口f 一1 1 ，这就确定了直线y = o ：x + 卢考虑这条 直线和下面的网格： ( x ，y ) r 2 ：z 0 ，y 0 ，z 或y 是正整数) 、那么沿着 这条直线我们就得到一系列的交点，我们给于这些点赋值如下：如果交点是 直线y = 。z + 卢和垂直线的交点，也就是说，这个交点的x 坐标为整数，我 们给它赋予n ；如果交点是直线y = a z + 卢和水平线的交点，也就是说，这个 交点的坐标为整数，我们给它赋予b 如果交点是格子的顶点，我们可以认 为它是两个点，一个是y = a 。+ 卢与水平线的交点，另一个是与垂直线的交 点，我们可以给它赋予n b 或地因为a 是无理数，所以这种情况最多会出现 一次最后我们就得到字母表s = f 。，讣上的一个序列，记为r 8 ，这个序列 称之为c u t t i n g 序列在这种情况下，c u t t i n g 序列r ，口也可以称为是由直线 y = a z + p 生成的序列 对于c u t t i n g 序列我们有下面的命题 命题2 5 ( 5 0 】) 令f 弘，则下面结论是等价的 ( 1 ) f 是s t u r m 序列； ( 2 ) f 是c u t t i n g 序列 就像 1 5 所叙述的那样，由平行直线所生成的c u t t i n g 序列具有相同的因 子下面给出标准字的定义 定义2 1 设o z 0 ，1 为无理数考虑由直线y = a z 生成的序列兄，其中 z 0 ，如果在从点( 口，p ) 到直线y = o z 的水平( 垂直或直交) 距离比横坐标小 于q 的点到直线的水平( 垂直或直交) 距离都小，则点( 吼p ) 称作收敛点这 些点可以由第一个和最后一个坐标来排序很方便的我们可令a o ：= ( 1 ：o ) 设 l o 大连理工大学硕士学位论文 a 。：= ( q n , p 。) 是第n 个收敛点，设0 。为包含着从a 。到直线y = q z 的垂足 的正方形易知直线交q 。两次从原点的下一个交点到0 。的第二个交点开 始数，这样我们就得到一个字它称作n 阶标准字记作a 。为了方便，令 a o = a a 一1 = b 对于c u t t i n g 序列，我们有如下命题 命题2 6 ( 1 1 】) 任给n n ，有a 。一1 司a 。司r ，a b a 2 n 一1 ，b a a 2 。 对于无理数o le 【0 ，1 ，设其连分式为o t = o ；a l ，a 2 ，n - 命题2 7 ( 1 1 】) 设如是f 0 的n 阶标准字，那么任给n n ，有a 。+ 1 以n “+ 1 a n 一1 命题2 8 ( f 1 1 ) 令f ，则下面结论是等价的 ( 1 ) f 是s t u r m 序列； ( 2 ) f 是c u t t i n g 序列 3s t u 工m 序列的构造 3 1 研究对象的简化 任意给定一个s t u r m 序列u ，根据其等价定义( c u t t i n g 序列) ，我们知道， 一定存在一个无理数a 0 和实数卢，使得该s t u r m 序列为该直线y = 一+ p 生成由 1 5 ，我们知道由平行直线生成的s t u r m 序列具有相同的因子不失 一般性，我们仅仅讨论由直线y = 生成的s t u r m 序列的情况 在本文中，如果不特殊声明，下面的s t u r m 序列均是由直线y = a 。生成+ 由于直线y = ( ，- 1 x 和直线y = a z 关于直线y = 茹对称，所以，通过交换字母 n 和b ，直线y = o _ 1 z 生成的s t u r m 序列就会变成线y = z 生成的s t u r m 序 列因此我们可以将无理数n 限制在( 0 ，1 ) 上 设。的连分式为。= 【0 ；a l ，a 2 ，a ，其中( n 。) 。，0 为正整数由命题 2 7 我们可以容易得到 a n 司a n + l 什a1 睁a n + 1 当n 0 从 1 1 知，u 为序列 a 。) 的极限 下面我们给出两个重要的引理 引理3 1 ( 1 2 】) 任给n 0 ，那么s t u r m 序列可以唯一写成a 。和a 。1 地连接 在这种连接下，a 。一1 都是独立出现，而且。的幂为a 。+ l 或a n + 1 + 1 从现在开始，我们总是假设n ，卢s 并且n 卢 引理3 2 ( 1 1 1 ，命题3 ) 任给n 0 ，卢p a 。，那么有 a n a ；一1 = a n - - 1 a 。卢一1 口一1 卢o ， 如一1 如= a a n i o 一1 卢一1 q p 一1 3 关于s t u r m 序列的因子结构 3 2 剩余序列的分类 令u a 6 尸为任意一个s t u r m 序列和w 为其任意一个因子由命题2 2 、 令u 依次删去”则会产生一个新的序列这个序列我们记为u ”，称作剩余 序列很显然，当1 w l = 1 时，剩余序列是平凡的因此，我们假设1 w l 1 任给w 一 u ，那么一定存在一个n n ，从而满足 i a 。jsj “j f 4 1 f 对于给定的整数n ，设。和臼分别为且。一1 和a 。的最后一个字母由 1 1 中 的命题5 ( 5 ) ， d a 。卢一1 二：a ： 引理3 3 如果a a 。口一1 i w ，那么w a 挈+ z + 2 证明由引理3 2 ，a 1 a 。一1 a 。= a + l + a a 。一1 一1 口一1 d 卢因为q a 。口一1 i ，所 以w a + 1 + 1 a 。1 a 。口一1 q 一1 a + + 2 a 。一l _ a t + ，+ 3 因为陋f i a 。+ 1 f ，所 以 _ 且挈+ 1 + 2 口 我们首先考虑两个简单的情况 命题3 1 如果n a 。口_ 1 _ w ，那么存在u 的两个非空的因子，记作u l ，u 2 ，满足 w w “1 ，“2 卜 证明由引理3 1 ，存在矿的两个非空的因子， 1 = f l a a ，“- r 1 1 a n , - 1 q 1 ， 2 = 卢a 挈+ 1 a n - n l ， 从而满足 u ( a a 。口1 ) p 1 ，”2 一 设w = 。1 q 厶卢一1 y l 为u 的因子，这里z 1 ，y 1 ( n ，b 卜很显然， z 1 劬1 ，1 2 ，可1 司 1 ，y l 司v 2 因为 w z a 2 ，l a 。isl 刮 i a 。+ l l ， 一1 4 大连理工大学硕士学位论文 所以一定存在u 的两个非空因子 乱1 = 可f 1 1 。f 1 ，让2 = 掣f 1 ”2 z 了1 从而满足叫”缸l ，u 2 。 口 命题3 2 如果 满足条件= l a 。i 和w a a 。口，那么u w 是一个周期序 列，也就是说，一定存在u 的一个非空的因子u ，满足w ”如卜 证明很显然，a 芦_ 1 ；：叫因为= i a 。i ，所以我们可以设w = x - 1 a 。z ，其 中oq a 。由引理3 上那么u 可以唯一写成z a 。z 和x - 1 a n - 1 a 。z 地连接 在这种连接下，x - - 1 a n 一。a n x 都是独立出现当z i a 。1 n _ 1 卢_ 1 时，存在u 的 一个因子，= x - 1 a n - - 1 a 。，从而满足w w u ) “；当。qa 。一1 f ：x _ 1 卢- 1 时， 因为。a n - 1 a 。z = 。a 。z 。_ 1 a n - 1 0 t - 1 卢- 1 d 卢，所以，存在u 的一个因子， u = x - 1 a n - l c l “卢- 1 a 触，从而满足u 加 u 。 因此，存在矿的一个因子， f 。一1 a n - - 1 口一1 卢一1 n 卢。，当z 司a 铲1 0 t 一1 口一1 让= 1 。一1 a n 一1 a 乱z ，当x z a a n - 1 a 一1 卢一1 从而满足w ” u p 口 下面总是假设l a 。l i a 。+ 1 l 和a a 。卢- 1 i 由引理3 3 ，我们可设 w = x a n y ，其中x 非空，i y | l a 。i ，z p a 。，y 日a 。，并且05i n 。+ 1 显然， w 司。：1 a n + i a n 定理3 1 如果w z w - 1 厶+ 1 a 。) ，那么存在u 的两个非空的因子u 1 ，“2 ，满足 u w u 1 ，“2 ) “ 证明由引理3 1 ，u 可以唯一写成z a ：1 a n + l a 。一1 和x a 。十1 a 。一1 地连接 在这种连接下，x a n + l a 。z - 1 都是独立出现 显然，t ，司。a 二1 a + 1 a 。一1 和w 司x a n + 1 a 。z 设 t 1 = 1 1 ) 1 ( z a ：1 a n + l a n z 一1 ) “2 = w 一1 ( 茁a n + 1 a n z 一1 ) 因为o a n 卢一1 i 叫和w z w 一1 ( z a 乱+ 1 a 。) ，j 听以u 叫 u 1 ，u 2 ) u 口 1 5 关于s t u r m 序列的因子结构 引理3 4 令a a 。卢一1 二：和x 2 w ，其中x 2 扣，b ) 如果存在一个字u 1 _ u 满 足 u l t j a 。a 。+ 1 a 。和叫i ( 钍1 ) z i l ，那么u 1 是唯一的 证明如果z 焉= x l a ；y 1 ，那么z = x l ，y = y 1 因为u 1 w _ 2 i 厶j ，那么存在u 四个非空的因子，u 1 ，u 2 = 2 。一1 ，u 3 = v 3 a 。z 一1 ，u 4 = v 4 x ，满足u # o 让1 ，钍2 ，u 3 ，牡4 p ( 3 ) 因为 2 a 。| ，所以，z p 3 和x l 蛳由引理31 ，引理3 2 ，u 可以唯一写成。a 二1 a n + l a 。a 。- 。，x a n + l a n z 一1 和z a ：2 a n + l a 。z 一1 地连接因 为1 w i 2 1 a 。l ，所以存在矿四个非空的因子，u 1 ，“2 = v 2 a 。，“3 = , v 3 x 一，u 4 = 蛳$ ，满足u w 如1 ，u 2 ， a 3 ，u 4 ) “ ( 5 ) 因为西”2 和 2 1 a 。i ，那么一定存在u 三个非空的因子，记作 札2 ，“3 ，u 4 ，满足u t 上2 ，u 3 ，u 4 ) u ( 5 ) 如果x s v 2 和川= 2 1 a 。l ，那么一定存在u 两个非空的因子，记作u 3 满足u w u 2 ，u 3 ) 。 由命题31 ，命题3 2 ，定理3 1 ，定理3 2 和定理3 3 我们有下面的定理 定理3 4 任给一个s t o r m 序列u a ，b ) 。，及一个双射：一o 巩一b ， 其中u 口：巩_ u ，并且使得u 可以通过双射砂变成一个新的序列如果这个 新序列是s t u r m 序列，那么一定存在一个正整数n o n 满足i i = i a n 。i 或 | y b i = l a 。| _ 下面的命题是我们在下面证明中要用到的重要工具 命题3 3 任给一个s t u r m 序列u o ，b ) 。和一个双射妒1 ：w l a ：w 2 一b ， 其中u 1 ”2 u ，使得妒1 渺) 为一个新的序列如果存在一个n n ，满足 u 1 = v - - 1 a n + l 和w 2 = v - l a 。a n l 口，其中 qa 。+ 1 ，那么t i l ( u ) 是一个s t u r m 序列，并且它的连分式为 f。0。；a+n。+；。2。-+。1，。a。n+。3 证明首先定义两个双射 妒2 ：w l a n + 1 ，w 2 a n a n + 1 妒3 ：a n + 】a aa + 1 b ，当a n + 2 1 时 当o 。+ 2 = 1 时 通过双射，1 ，妒2 和妒3 得妒1 ( 矿) = ，3 ( u ) 记妒3 ( a 0 1 厶+ 件1 a 。+ 1 ) 为b ；，令b 一1 = ，3 ( a 。a 。+ 1 ) = b 那么 b o = 砂3 ( a n + 1 ) = 。： b 1 = 妒3 ( a 。- - + 11 a 。+ 2 a n + 1 ) = b ；”+ 2 1 b 一1 ， b 2 = 妒3 ( a 善l a n + 3 a 。+ 1 ) = b 1 a ”+ 3 b o ， b = 妒3 ( 4 0 l a 。+ i + 1 a 。+ 1 ) = b 川a - + 1 + 且一2 ， 1 8 大连理工大学硬士学位论文 下面需要分两种情况来讨论这个问题 ( i ) 当+ 2 1 令b 1 = a 。+ 2 1 ，b 2 = a n + 3 ，b i = + l “，那么妒1 渺) ( = v 3 哆) ) 是一 个s t u r m 序列，鼠为其 阶标准字其中 2 1 ，另外【b o = 0 ；b l = 口。+ 2 1 ，b 2 = a n + 3 ，b = a n + l + j ，】是它的连分式 ( i i ) 当a n + 2 = 1 双射怕就变为，母3 ：a 。+ 1 一a ，a 。+ 2 一b 由【1 1 1 可得，妒1 ( u ) ( = 妒3 ( u ) ) 是一个s t t t r m 序列，并且它的连分式为k + 3 ；。州，+ 5 ，】 因此饥( 矿) 是一个s t u r m 序列，并且它的连分式为 fl o ；口n + 2 1 ，+ 3 【k + 3 ；o m + 4 ，a n + 5 ， ，当。卅2