灯塔群及其性质

1、苏州大学本科生毕业设计（论文）学院(部)数学科学学院题 目灯塔群及其性质目录第一章 灯塔群的生成元(2)第1.1节 群的乘法(2)第1.2节 群的生成元(2)第二章 灯塔群的表出(3)第三章 L2同构于一个矩阵群(3)第四章 字长的计算(5)第4.1节 群元素的有效描述(5)第4.2节 有效路径(6)第4.3节 字长的计算(6)第五章 灯塔群和凯莱图(8)第5.1节 DiestelLeader图(8)第5.2节 作为L2中元素的DL2(2)中的顶点(10)第5.3节 DL2(2)是L2的一个凯莱图(11)第5.4节 在凯莱图上移动(12)摘要The name of the group come

2、s from viewing the group as acting on a doubly infinite sequence of street lamps ,-l2,-l1,l1,l2,l3,each of which may be on or off, and a lamplighter standing at some lamp lk. An equivalent description for this, called the base group B of L is B=2, an infinite direct sum of copies of the cyclic group

3、 2 where 0 corresponds to a light that is off, and 1 corresponds to a light that is on, and the direct sum is used to ensure that only finitely many lights are on at once. An element of gives the position of the lamplighter, and B to encode which bulbs are illuminated. There are two generators for t

4、he group: the generator t increments k, so that the lamplighter moves to the next lamp (t-1 decrements k), while the generator a means that the state of lamp lk is changed(from off to on or from on to off).灯塔群的名字取自这个群的元素是作用于无限多个街灯,-l2,-l1,l1,l2,l3,，他们中的一些是亮着或者灭的，然后一个灯夫站在某个街灯lk旁边有一个等价描述，就是L的基群B写成这种形式

5、B=2，是循环群2的一个无限直和，式子中0对应此处灯是灭的，1对应灯是亮着的，而这直和是用来确保只有有限多个灯是亮着的而一个整数集的元素给出了灯夫的位置，同时B确定哪些灯是亮着的这个群有两个生成元：t增加了k，那么灯夫就向正数的街灯那侧移动(t-1指的是减少k，自然是向负数侧移动)，而生成元a指的就是某个位置上的街灯lk的状态改变了(关闭了或者开启了)关键词：生成元、表出、同构、字长、凯莱图前言 灯塔群是一个非常有趣的群，可以形象的和一条无限长的街道联系起来，街道两旁排列着均匀的路灯柱，一个灯夫在街道上行走，点亮或者熄灭某些灯泡我们将这以数学的形式表现出来，就是灯塔群L2它作为一个群还可以和凯

6、莱图联系起来，将图上的点与它的元素对应，有很多国内外专家学者从不同的角度入手研究过灯塔群，本文对国外相关文献进行总结归纳后，描述它的部分重要性质我们先看一个它的元素的例子：例1 设gL2，g=(-6,-1,4,5,6,-2),它的对应灯塔图如图1：图1(来自文献4)把它转化成由生成集a,t表示的形式，则为g=t4atatat7at5at4，上图类似数轴的这个部分我们称为灯台，以后讨论某些性质的时候我们需要在灯台上进行操作第一章 灯塔群的生成元1.1 群的乘法对于灯塔群L2，它的单位元是灯夫位置在0且没有灯泡被点亮的那个元素，即，0，同时要研究一个群，我们还要给出这个群上的乘法定义1.1：假设S

7、是一个集合，我们先约定a+S=a+bbS那么对于一个元素g1=S1,aL2和g2=S2,bL2,在群L2上做乘法，那么就有：g1g2=S1a+S2S1a+S2,a+b这就是一般形式下灯塔群中元素做乘法的形式，当然这比较抽象，在有了生成元之后我们可以更好的去理解这个乘法1.2 群的生成元为了得到一个群L2，我们需要两个基础的元素也就是说，我们需要让灯夫能够在两个方向均可以移动一个单位，同时他也可以改变他所在位置的灯泡的状态，即点亮或者熄灭它定义1.2：L2有两个生成元其中一个生成元tL2，它代表灯夫向自己所在位置的右侧移动一个单位，反过来t1L2表示的就是灯夫往左走了一个单位L2的另一个生成元a

8、L2，代表灯夫在当前的位置改变了灯的状态（点亮或熄灭）注：以上移动均在数轴上进行，右即代表数轴的正方向我们来看看这两个生成元是如何通过作用于灯台来构建L2中的元素的我们给出一个=t2at4a，灯夫从整数0的位置开始考虑h中的每一个生成元对应的指令，有如下变化： t2表示灯夫向右移动两步，来到整数2 a表示灯夫在整数2位置，点亮了此处的灯泡 t4表示灯夫又向右移动了四步，来到整数6，a表示点亮了此处的灯泡现在，我们通过生成元的指令，构建出了一个L2中的元素(2,6,6)对于之前提到的群的乘法，我们用生成元来描述可以更好的加以理解假设元素g=(-6,-1,4,5,6,-2)，再加上之前举例的元素=

9、t2at4a，我们来看gh的结果从g中灯夫最终的位置-2开始，按照h的指令一步步进行，t2a代表灯夫从-2开始向右移动2步，到达0，将0位置上的灯点亮，t4a则是灯夫继续从0位置向右移动四步，来到4并把4位置上原本亮着的灯熄灭，并停在4这样，我们就得到了gh的结果，显然，gh=(-6,-1,0,5,6,4)第二章 灯塔群的表出显然上面给出的生成元a和t已经可以构造任何特定的点亮的灯泡和灯夫的组合然而，为了给出群L2的一个表出，我们也必须给出一些关系马上能够给出的一个就是a2相当于/2中的单位元，同样a也是/2的生成元这在灯塔图中代表我们在同样的位置将一个灯泡的状态改变了两次，这会把它变回初始的

10、状态，无论是开还是关群的表出包含关系的无限集，可以看作如下情况：灯夫从初始位置(0)，向右移动k(k)个单位，点亮位置k的灯泡然后回到初始点；再向右移动j(j)个单位，点亮j位置的灯泡再回到初始点我们不难发现，j和k处的灯泡都是亮着的，灯夫则还在初始位置显然这样的话灯夫一开始是先向j还是k移动都无关紧要，因为最终结果都是一样的这也就意味着tkatk和tjatj这两者是可交换的，我们将此关系写作tkatk,tjatj=1 (a,b表示aba1b1，称为a和b交换)这对任意的kj成立，当然对于平凡情况k=j同样成立我们对群L2描述了一个关系的无限集 结合这两种类型的关系，我们得到了L2的表出：L2

11、=a,ta2=1,tkatk,tjatj=1,j,k符号L2中的2，表明灯泡状态是由群/2模型化的，也就是说，他们不是开启就是关闭的，不会有其他的状态第三章 L2同构于一个矩阵群我们现在从另外一个角度给出灯塔群L2，将其描述为一组矩阵我们已经知道L2中的元素可以唯一的由数对hi=/2i以及 k来表示我们可以将h中给出的信息重新表示为一个关于t和t-1的多项式P，其系数在/2上，其中多项式的非零系数则唯一的对应于h中的非零项也就是说，我们使用h中的项作为多项式的系数，因此元素(···，0,0,1,0,1,1,1,0,0,···),元组中

12、第一个1是由-2引导的，省略号则表示无穷多个0，得到多项式t2+1+t+t2现在我们考虑将L2中的元素表示成数对(P,k)，其中P形如iciti是包含了有限多个非零项关于变量t和t-1的多项式，其中k是整数，ci/2我们将这些信息写在矩阵中，其中t作为形式变量,注意由于ci/2，因此t的系数做的是模2加法而非普通加法：gL2对应于数对(P,k),其一对一的联系到如下矩阵：tkP01定理3.1 灯塔群L2同构于一个形式如tkP01的矩阵群G，k而P代表包含有限多个非零项的关于变量t和t-1的多项式，系数ci/2其中L2的生成元t唯一的对应到矩阵t001，a唯一对应到矩阵1101证明：构建一个映射

13、f:L2G,G中的元素都形如tkP01，f就如同上述将每一个灯塔群L2的元素都联系到对应形式的矩阵上去，我们需要证明这是一个同构映射首先对于任意的g1=S1,k1L2, g2=S2,k2L2它们对应的矩阵假设为tk1P101和tk2P201，假如k1k2，那么显然矩阵不相等，而如果k1=k2，那么由于g1和g2本身不相等，那么它们各自包含的有限数集一定不相等，那么P1P2，这两个矩阵也是不相等的，也就是说f是一个单射对于G中的每一个矩阵，我们都可以之前规定的形式对应的写出一个L2的元素，所以f也是一个满射，即f是一个一一映射接下来我们来看f是否保持运算：即是否有fg1g2=fg1fg2先看左侧

14、，根据灯塔群中的乘法定义，g1g2=S1k1+S2S1k1+S2,k1+k2,按照映射f把它写成矩阵，就是tk1+k2P1+tk1P201，解释一下多项式部分，我们将亮着的灯泡转化成对应t的次幂的系数，因此k1+S2转化成多项式是tk1P2，集合和S1做并，正好就是对应多项式相加，而由于多项式P中t的系数是做模2加法的，因此就已经代表着减去了重叠的部分，即P1+tk1P2这个式子本身就代表着集合做并之后减去了交集的部分fg1fg2=tk1P101tk2P201=tk1+k2P1+tk1P201左右两端相等，因此f正是一个同构映射，那么L2和G是同构的证毕我们来看一下如何通过矩阵t001（对应生

15、成元t）和1101（对应生成元a）相乘得到任意的元素gL2假设g=tkP01代表L2中的某个元素，其中k代表灯夫位置，多项式P的系数代表一系列亮起的灯泡我们知道在乘法中我们去乘t得到的结果是灯夫向右移动一步，但是不会改变附近的灯泡状态，那么我们来看反映到矩阵上是什么样的结果：tkP01t001=tk+1P01根据我们之前的定义，这个结果矩阵的意义可以很轻松的看出，P没有变化代表灯泡状态未变，t的指数由k变为k+1代表灯夫右移了一个单位，这正符合我们的预期我们知道如果对一个元素gL2乘以生成元a，那么我们得到的就是在灯夫位置的灯泡状态改变一次，其他不变因此假如我们操作的元素是tkP01，我们希望

16、它右乘矩阵1101（就是a）之后，只有位置k上的灯泡状态发生了变化，即多项式P中只有tk这一项系数产生变化下面我们来验证一下结果是否如我们期望那般：tkP011101=tkP+tk01显然，灯夫位置无变化，而多项式P中tk这一项系数需要加上1，如果它原本是1，那么这一项就消去（即灯灭），若是0，那么添上这一项，显然结果是符合预期的第四章 字长的计算下面一个需要研究的问题就是L2的元素关于生成集a,t的字长的计算一个元素的字长指的是我们为了得到一个元素所需要乘以的生成元的最小数量为了以一种有效的方式描述灯夫创建一个特定的组合之后停在指定位置的情况，我们需要考虑这样一个L2上最小长度的字Sean

17、Cleary和Jennifer Taback讨论过灯塔群中的闭塞字以及其他卷积，探索几何形状下灯塔群的凯莱图和广泛卷积如果在凯莱图G,X中从的恒等出发没有能延伸过的测地线的话，有着有限生成集的群G中的元素就称为闭塞的另外还描述了凯莱图中的元素和一些摆动字间的非凸性1 4.1 群元素的有效描述假设gL2，亮着的灯泡位置在-3,4,5，灯夫停在整数2的位置如果要依据L2的生成集a,t构建这个元素g，我们需要在灯台上进行以下步骤 灯夫从整数0的位置开始，此刻灯台上没有灯亮着 灯夫移动到整数4然后开启此处的灯 灯夫从4右移一个单位来到5，然后开启此处的灯 灯夫再从整数5向左移动，来到整数-3，开启此处

18、的灯泡 最后，灯夫从-3向右移动到整数2的位置，停下当然，我们可以很直观的感受到，如果我们先让灯夫移动到5开启此处的灯，然后让他去-3，再去4，最后回到2，这必然是一种效率非常低下的方式，尽管最终得到的结果没有变化定义4.1 如果我们依据以下标准，为L2的某个元素g构建一条路径： 让灯夫向右移动到最小的需要点亮的正数位置，点亮这里的灯泡 继续向右移动，过程中遇到需要点亮的就立刻点亮哪个 当正数的灯泡点亮完毕后，让灯夫回到初始点0 让灯夫向左移动，按顺序点亮过程中遇到的需要点亮的灯泡 左侧需要点亮的灯泡全部点亮之后，让灯夫移动到最终位置上我们把根据以上标准-来构建出元素g的一条路径记为g，它就称

19、为g的有效路径下面我们会介绍一些符号来描述它先让灯夫移动向负数那边也会得到一条类似的有效路径虽然它们不一定是最小长度，但是依旧可以按照下面的描述用来计算g的字长4.2 有效路径我们用ak=tkatk来表示a关于tk的共轭，ak表示初始情况下灯夫在0处，两边是无限个均未点亮的灯泡，然后灯夫移动到位置k点亮了此处的灯泡，然后回到了起始点0显然如之前讨论过的那样，所有的ak都是可交换的出现在一个字=i=1mai中成对的ak全部消掉，那表示的是同一位置上的灯开启一次关闭一次，没有变化（反之亦然）注意到如果两个这样的共轭乘在一起，比如说a2a7，t相邻幂之间的消去是有具体意义的，指的是灯夫移动到整数2点

20、亮此处的灯之后，继续向右移动五个单位到整数7，点亮了此处的灯泡，然后回到了起始点：a2a7=t2at2t7at7=t2at5at7定义4.2 假如L2的一个元素g有着正侧点亮的灯泡：i1<i2<···<ikik>0，和负数侧点亮的灯泡：j1>j2>···>jljl>0，以及最终灯夫停下的位置m，我们就把路径g表示成如下形式：g=ai1ai2···aikaj1aj2···ajltm如果是为了给Ln中的元素n3找到类似于上面的有效路

21、径，我们仅仅只是在g的表达式中给生成元a添上幂4.3 计算字长有一种简单直接的算法，来计算关于生成集a,t的元素gL2从上面提到的任意一种有效路径的字长定理4.3 给出一个gL2，先根据定义4.1来写出有效路径g以及记号ak=tkatk然后我们从这条路径上来计算数值量，记为Dg如果g=ai1ai2···aikaj1aj2···ajltm那么我们有：Dg=k+l+min2jl+ik+mik,2ik+jl+m+jl证明：我们需要分两步，先来证明g的字长最多是Dg：对于任意的gL2，我们按照有效路径g的写法，并把所有的共轭展开g=ti1at

22、i2i1atikik1atik+j1atj2j1atjljl1atm+jl我们主要就是要确定一个元素g所需要乘以的生成元个数，从上式可以看出有k+l个a，而t的个数我们看指数和就可以,负指数部分去掉负号来计算，是2ik+jl+m+jl个t那么我们把g中的正负下标部分换位，再次将共轭部分展开g=tj1atj2j1atjljl1ati1+jlati2i1atikik1atmik同样是看生成元个数，a还是k+l个，而t按照指数和来看是2jl+ik+mik个，那么显然g的字长，被这两个长度限制住了，即最多也只能是k+l+min2jl+ik+mik,2ik+jl+m+jl，也就是Dg第二步，我们来证明g

23、的字长至少应该是Dg：我们想得到g字长的下界，就需要从几何角度来分析g，它是一个代表亮着的灯的集合和一个整数，要把它的灯塔图和构成g的a和t联系起来假设g包含n个亮着的灯泡，那么显然我们知道它至少要包含n个a才能完成将这n个灯点亮的操作，那么易知，表示成g形式的g包含至少k+l个a再来看t，为了计算出t的总数，需要分别来看正和负两方面t的指数和同时也是包含了灯夫的最终位置的，先来考虑部分指数和： 正数侧最右端被点亮的灯为ik，那么显然t的指数和至少为ik(这很好理解，灯夫从起始点0往右侧移动时，先点亮第一个遇到的需要点亮的灯，然后一路下去到ik) 同理负数侧最左边被点亮的是jl,那么t的指数和

24、至少是-jl 然后，单看灯夫的最终位置，t的指数和一定是m那么，我们分两种情况来看的话： 假如灯夫先点亮右侧，那么t用到的指数和就是0,ik,-jl,m,全部加起来就得到t的总指数和，是2ik+jl+m+jl 假如灯夫先点亮左侧，那么t用到的指数和就是0,-jl,ik,m,全部加起来就得到t的总指数和，是2jl+ik+mik这样我们就得到了g的字长的下界，显然它就是Dg，再结合第一部分的证明，定理证毕如果仔细查看Dg的公式，就很容易发现Dg是g的灯塔图中几个有关量的总和： 被点亮灯泡的数量 方向A上最远处被点亮的灯泡和原点距离的两倍 方向B上最远处被点亮的灯泡和原点的距离 灯夫和方向B上最远灯

25、泡之间的距离例2 我们举出一个根据定理给出的Dg表达式直接计算字长的例子，我们写出例1中的g的路径g=a4a5a6a1a6t2，然后，计算出字长：Dg=3+2+min18+26,18+2+6=27第五章 灯塔群和凯莱图为了给群L2得到一个凯莱图，我们必须得稍微变换一下生成集我们考虑L2的这样一个生成集t,at(以及Ln的生成集t,at,a2t,······,an-1t,n3)这有时也被称为通电自由生成集，即移动和开启灯泡可以用单一的一个生成元完成，也就是说通电（即点亮灯泡）这一行为不再需要自己的生成元不难看出元素的有效路径和字度量的有

26、效计算也是适用于这种生成集的Murray Elder研究过灯塔群的测地线表达灯塔群Ln是无穷多锥型的，没有正则测地线表达，关于某些生成集有反测地线表达而灯塔群关于一个生成集的测地线全表达不是相反的而是无关的，同时关于另外一个生成集它的测地线全表达却是相反且无关的25.1 DiestelLeader图：L2关于生成集t,at的凯莱图将在下面展现，是一种非常特殊的图形，叫做DiestelLeader图这些图是为了回答以下的问题而引进的：每一个“好”的无限图都拟等距于一些有限生成群的凯莱图吗？这里的“好”包含了一些专门的条件，例如：在其他条件下，图必须是连通的且在每一个顶点都具有相同的度为了定义一个

27、DiestelLeader图，我们考虑两个度为d+1的无限树，将其表示为T1和T2我们给树标定方向使每个顶点都有一条输入边和d个传出边请看，图2和3的树（每棵树只显示了一部分）在每个树上固定一个高度函数i:Ti,i=1,2这个高度函数固定了高度0;有一条输出边是从高度0的一个顶点出发止于高度1的一个顶点，还有一条边是从高度-1的一个顶点出发止于高度0的一个顶点以这种方式继续下去，我们已经将Ti中的每一级顶点都用一个整数来确定看下面的图2，已经在一个树上举了一个高度函数的例子如果在树上选择了不同的高度函数，那么得到的就是同构的DiestelLeader图图2(来自文献4)每一边固定了高度函数的树

28、做乘积T1×T2DiestelLeader图DL2(2)的顶点集是T1×T2的子集(图中的两个坐标位于水平线上)举个例子，数对(s,t)是DL2(2)的顶点，注意这张图只表现出了无限树的一小部分用T1×T2来表示这两个树T1和T2的乘积而T1×T2中的点是形如(t1,t2)的有序对，其中t1T1,t2T2DiestelLeader图DL2(d)是这些树乘积的一个特别的子集为了识别这种图（如其它任何图形一样）我们来描述它的顶点和边(1) DiestelLeader图DL2(d)中的顶点：定义5.1 DiestelLeader图DL2(d)的顶点集是树的乘积

29、T1×T2的一个子集且这两个坐标的高度之和是0：(t1,t2)tiTi,1t1+2t2=0一个让DL2(d)的顶点变得可视的方法是向相反的方向定向T1和T2，也就是把它们画在同一页上，向页面顶部移动时T1的高度函数增加，而同时这个方向上T2的高度函数会减少这样画树就会使得T1高度k的位置在纸上同一水平是T2的高度-k现在DiestelLeader图DL2(d)的顶点只是简单的多对顶点，每个树取一点，且二者在同一水平线上关于这对树的表示，请参见图2，其中每一棵树的高度都标注在图的两侧使用图2的标注，可以看到DL2(d)上的点(s,t)请注意图2中依旧只有无限树的一部分(2) Diest

30、elLeader图DL2(d)中的边：定义5.2 使用图3中的标注，如果顶点s0和s1是由T1中的边连接且顶点t0和t1是由T2中的边连接的，就称顶点(s0,t0)和(s1,t1)是由边连接的由于两个坐标的高度之和必须保持在0，去找到DL2(d)中通过一条单独的边连接到(s0,t0)的顶点，我们只能做以下两件事中的一件： 在T1高度增加1的同时T2的高度降低1 在T1高度降低1的同时T2的高度增加1图3(来自文献4)使用每个树标记的顶点，我们可以看到图DL2(2)的顶点(s0, t0), (s0, t0), (s2, t2), and (s2, t2)都是通过一条单独的边连接到顶点(s1,t1

31、)的T1(或T2)中有着d条输出边连接s1(或t1)到一个高度增加1的顶点以及一条单独的边连接s1(或t1)到T1(或T2)中高度减少1的一个顶点，我们可以看到DL2(d)中有着2d个顶点通过一条单独的边连接到(s1,t1)在图3中通过DL2(2)中的一条边连接了点(s0,t0)和(s1,t1)通过一条单边连接到(s1,t1)的三个剩余的顶点是(s0, t0), (s2, t2), and (s2, t2)(图3)重要提醒：当看图2和3的时候，我们必须注意画在每个树上的边不代表它是存在于图DL2(2)中的边在图2和3中绘制树的乘积给我们提供了简单的方法来看到DL2(2)中的顶点，或相等地来看如

32、我们将在下面展示的，凯莱图(L2,t,at)的顶点以上我们所描述的边我们知道一定会出现在DiestelLeader图中，但是实际上没有绘制在图2或3中对于DL2(2)中顶点之间的边的例子，见图65.2 作为L2中元素的DL2(2)中的顶点：我们现在展示凯莱图(L2,t,at)就是DiestelLeader图DL2(2)我们必须展示如何以独特的捕获群结构的方式来将DL2(2)中的一个顶点和L2中的一个元素联系起来这涉及到了在树中确认顶点的另一种方法 在一个树上标记边我们考虑一个固定高度函数的价3无限树TT的每个顶点都有两个输出边，然后我们标记左边为0，右边为1. 在树1上确认一个顶点在树T上选择

33、高度k的一个顶点v，T的边全都用0和1标记从v出发有一条独一无二的向下经由T的路径，每一步高度下降了1通过这条路我们记下边的标签会得到一连串的0和1但是最终得到的总是0我们将这一串记作i=a1,a2,a3,a4,···，而ai0,1，aj=0对大于某个常数的j成立 在树2上确认一个顶点反过来，我们给一串i=a1,a2,a3,a4,···，而ai0,1，aj=0对大于某个常数的j成立，以及一个整数k可以在T的高度k找到一个独一无二的点，从出发一条独一无二的向下路径可以被标记为图4(来自文献4)这一串1,0,1,0,0,0,·

34、· ·以及高度k=2描述了树T上独一无二的一个点图5(来自文献4)DL2(2)的元素由1,2,2唯一表示，其中1=1,0,1,0,0,···而2=1,0,0,0,0,···给定条件下，假设这样的序列已经包含了全部的05.3 DL2(2)作为L2的一个凯莱图：我们现在准备好呈现出一个关于DiestelLeader图DL2(2)和L2中的元素之间的双射我们上面已经描述过如何将DL2(2)中的元素以元组1,2,2的形式展现考虑L2中的一个元素，通过g=(P,k)给出，P是一个变量多项式(关于t)而且t和t-1的系数属于/

35、2，有有限多个非0系数，k让数列ai表示P的系数，其中ai是ti的系数将ai分成两个子列：1=aii<k和2=aiik，其中前一个是按照相反的顺序排列的，即ak-1,ak-2,···注意这两个数列最终必须包括全部的0因此，我们将g看做三元组1,2,2，然后对应DL2(2)中的顶点就是非常清楚的了例如，在图5中描述DL2(2)的顶点对应于矩阵 证明DL2(2)就是关于生成群t,at的凯莱图L2完全由延伸到两个图之间的图同构给出Jennifer Taback把部分结论推广到了高维灯塔群中，介绍了高维灯塔群或者说DiestelLeader群dq在d3的情况下是图自

36、动的，实际上是找到了一族新的图自动的群且它们自己并非自动群35.4 在凯莱图上移动我们现在要理解如何在凯莱图上移动，以同样的方式我们也就知道了如何在凯莱图×上移动我们知道从×,1,0,0,1中任意的一个顶点g(我们提到g的时候指顶点的同时也指这个点对应的群中的元素g)，有一个标为(1,0)的从g发出沿x方向终止于一个单位长度之后顶点的边，同样的有标为(0,1)的从g出发沿y方向终止与一个单位长度之后顶点的边，当然类似的也有由生成元的逆来表示的边从g出发沿标为s的边走下去得到的就是对应于gs的那个顶点对DL2(2)=(L2,t,at)，我们希望直观地看到如何通过一条单独的边连

37、接到不同于坐标1,2,k的一个顶点比如说我们在一个顶点g=1,2,kL2，然后通过一条等同于生成元t作用的边(也就是说，我们把g看做L2的一个元素，然后跟生成元t做乘法来看结果gt)，我们来看它连接到的那个顶点gt的坐标究竟是什么为了研究这个问题我们需要借助矩阵，把t写成t001，然后1,2,k对应的元素g写成相应的tkP01的形式，注意如果我们有多项式的系数无穷序列ai，那么就有1=aii<k和2=aiik如上所示，gt=tk+1P01图6(来自文献4)这一对实线画出的边代表图DL2(2)中生成元t作用于DL2(2)中的两个顶点(分别用实心圆和实心方块表示的)其他虚线代表的是单个树中的

38、边，但是不是DL2(2)中的边然后这把对应的DL2(2)中的顶点的三元组改变成了什么样呢？首先可以明确的是整数坐标(即元组中的第三个部分)从k变到了k+1，而多项式P既然没有变化，那么在gt和t中P的系数是完全一样的从g到gt改变的部分是我们把ai划分成两个子列的那个分割点：从gt中我们得到的是1=aii<k+1和2=aiik+1，前者是以ak为起始的注意到我们为了得到1实际上将2的第一个数挪走了，然后把它放在了1的最前端，就得到了1当然2就是原本的2去掉它最前端的那个数，剩下的部分现在我们就看到了DL2(2)中顶点g和gt的坐标之间的精确差异，同样的我们也可以把gt在DL2(2)上通过

39、如下操作变换到g在树T1上，沿着标记为ak的边到达高度k+1的另一个新顶点，在树T2上，只需去除掉路径的初始边缘，这样，截断的路径就起始于-(k+1)这样对应于B1,B2,k+1的新顶点是通过一条单独的边连接到1,2,k的要理解从顶点g出发通过一条等于at作用的边得到了什么，我们需要连续乘以a和t两个生成元的矩阵：gat=tk+1tk+P01gat的多项式项和P只有一个系数不同：tk这一项的系数增加了1，而由于系数是取自集合/2，因此系数做的是模2加法，简单地说就是0会变成1反之1变成0整数的坐标现在是k+1，我们把tk+P的系数分成两个子列，我们得到1，第一个数是ak+1(模2加法)，其后的数就是1，而2=aiik+1顶