燈塔群及其性質(zhì)

1、蘇州大學(xué)本科生畢業(yè)設(shè)計（論文）學(xué)院(部)數(shù)學(xué)科學(xué)學(xué)院題 目燈塔群及其性質(zhì)目錄第一章 燈塔群的生成元(2)第1.1節(jié) 群的乘法(2)第1.2節(jié) 群的生成元(2)第二章 燈塔群的表出(3)第三章 L2同構(gòu)于一個矩陣群(3)第四章 字長的計算(5)第4.1節(jié) 群元素的有效描述(5)第4.2節(jié) 有效路徑(6)第4.3節(jié) 字長的計算(6)第五章 燈塔群和凱萊圖(8)第5.1節(jié) DiestelLeader圖(8)第5.2節(jié) 作為L2中元素的DL2(2)中的頂點(diǎn)(10)第5.3節(jié) DL2(2)是L2的一個凱萊圖(11)第5.4節(jié) 在凱萊圖上移動(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，是循環(huán)群2的一個無限直和，式子中0對應(yīng)此處燈是滅的，1對應(yīng)燈是亮著的，而這直和是用來確保只有有限多個燈是亮著的而一個整數(shù)集的元素給出了燈夫的位置，同時B確定哪些燈是亮著的這個群有兩個生成元：t增加了k，那么燈夫就向正數(shù)的街燈那側(cè)移動(t-1指的是減少k，自然是向負(fù)數(shù)側(cè)移動)，而生成元a指的就是某個位置上的街燈lk的狀態(tài)改變了(關(guān)閉了或者開啟了)關(guān)鍵詞：生成元、表出、同構(gòu)、字長、凱萊圖前言 燈塔群是一個非常有趣的群，可以形象的和一條無限長的街道聯(lián)系起來，街道兩旁排列著均勻的路燈柱，一個燈夫在街道上行走，點(diǎn)亮或者熄滅某些燈泡我們將這以數(shù)學(xué)的形式表現(xiàn)出來，就是燈塔群L2它作為一個群還可以和凱

6、萊圖聯(lián)系起來，將圖上的點(diǎn)與它的元素對應(yīng)，有很多國內(nèi)外專家學(xué)者從不同的角度入手研究過燈塔群，本文對國外相關(guān)文獻(xiàn)進(jìn)行總結(jié)歸納后，描述它的部分重要性質(zhì)我們先看一個它的元素的例子：例1 設(shè)gL2，g=(-6,-1,4,5,6,-2),它的對應(yīng)燈塔圖如圖1：圖1(來自文獻(xiàn)4)把它轉(zhuǎn)化成由生成集a,t表示的形式，則為g=t4atatat7at5at4，上圖類似數(shù)軸的這個部分我們稱為燈臺，以后討論某些性質(zhì)的時候我們需要在燈臺上進(jìn)行操作第一章 燈塔群的生成元1.1 群的乘法對于燈塔群L2，它的單位元是燈夫位置在0且沒有燈泡被點(diǎn)亮的那個元素，即，0，同時要研究一個群，我們還要給出這個群上的乘法定義1.1：假設(shè)S

7、是一個集合，我們先約定a+S=a+bbS那么對于一個元素g1=S1,aL2和g2=S2,bL2,在群L2上做乘法，那么就有：g1g2=S1a+S2S1a+S2,a+b這就是一般形式下燈塔群中元素做乘法的形式，當(dāng)然這比較抽象，在有了生成元之后我們可以更好的去理解這個乘法1.2 群的生成元為了得到一個群L2，我們需要兩個基礎(chǔ)的元素也就是說，我們需要讓燈夫能夠在兩個方向均可以移動一個單位，同時他也可以改變他所在位置的燈泡的狀態(tài)，即點(diǎn)亮或者熄滅它定義1.2：L2有兩個生成元其中一個生成元tL2，它代表燈夫向自己所在位置的右側(cè)移動一個單位，反過來t1L2表示的就是燈夫往左走了一個單位L2的另一個生成元a

8、L2，代表燈夫在當(dāng)前的位置改變了燈的狀態(tài)（點(diǎn)亮或熄滅）注：以上移動均在數(shù)軸上進(jìn)行，右即代表數(shù)軸的正方向我們來看看這兩個生成元是如何通過作用于燈臺來構(gòu)建L2中的元素的我們給出一個=t2at4a，燈夫從整數(shù)0的位置開始考慮h中的每一個生成元對應(yīng)的指令，有如下變化： t2表示燈夫向右移動兩步，來到整數(shù)2 a表示燈夫在整數(shù)2位置，點(diǎn)亮了此處的燈泡 t4表示燈夫又向右移動了四步，來到整數(shù)6，a表示點(diǎn)亮了此處的燈泡現(xiàn)在，我們通過生成元的指令，構(gòu)建出了一個L2中的元素(2,6,6)對于之前提到的群的乘法，我們用生成元來描述可以更好的加以理解假設(shè)元素g=(-6,-1,4,5,6,-2)，再加上之前舉例的元素=

9、t2at4a，我們來看gh的結(jié)果從g中燈夫最終的位置-2開始，按照h的指令一步步進(jìn)行，t2a代表燈夫從-2開始向右移動2步，到達(dá)0，將0位置上的燈點(diǎn)亮，t4a則是燈夫繼續(xù)從0位置向右移動四步，來到4并把4位置上原本亮著的燈熄滅，并停在4這樣，我們就得到了gh的結(jié)果，顯然，gh=(-6,-1,0,5,6,4)第二章 燈塔群的表出顯然上面給出的生成元a和t已經(jīng)可以構(gòu)造任何特定的點(diǎn)亮的燈泡和燈夫的組合然而，為了給出群L2的一個表出，我們也必須給出一些關(guān)系馬上能夠給出的一個就是a2相當(dāng)于/2中的單位元，同樣a也是/2的生成元這在燈塔圖中代表我們在同樣的位置將一個燈泡的狀態(tài)改變了兩次，這會把它變回初始的

10、狀態(tài)，無論是開還是關(guān)群的表出包含關(guān)系的無限集，可以看作如下情況：燈夫從初始位置(0)，向右移動k(k)個單位，點(diǎn)亮位置k的燈泡然后回到初始點(diǎn)；再向右移動j(j)個單位，點(diǎn)亮j位置的燈泡再回到初始點(diǎn)我們不難發(fā)現(xiàn)，j和k處的燈泡都是亮著的，燈夫則還在初始位置顯然這樣的話燈夫一開始是先向j還是k移動都無關(guān)緊要，因?yàn)樽罱K結(jié)果都是一樣的這也就意味著tkatk和tjatj這兩者是可交換的，我們將此關(guān)系寫作tkatk,tjatj=1 (a,b表示aba1b1，稱為a和b交換)這對任意的kj成立，當(dāng)然對于平凡情況k=j同樣成立我們對群L2描述了一個關(guān)系的無限集 結(jié)合這兩種類型的關(guān)系，我們得到了L2的表出：L2

11、=a,ta2=1,tkatk,tjatj=1,j,k符號L2中的2，表明燈泡狀態(tài)是由群/2模型化的，也就是說，他們不是開啟就是關(guān)閉的，不會有其他的狀態(tài)第三章 L2同構(gòu)于一個矩陣群我們現(xiàn)在從另外一個角度給出燈塔群L2，將其描述為一組矩陣我們已經(jīng)知道L2中的元素可以唯一的由數(shù)對hi=/2i以及 k來表示我們可以將h中給出的信息重新表示為一個關(guān)于t和t-1的多項(xiàng)式P，其系數(shù)在/2上，其中多項(xiàng)式的非零系數(shù)則唯一的對應(yīng)于h中的非零項(xiàng)也就是說，我們使用h中的項(xiàng)作為多項(xiàng)式的系數(shù)，因此元素(···，0,0,1,0,1,1,1,0,0,···),元組中

12、第一個1是由-2引導(dǎo)的，省略號則表示無窮多個0，得到多項(xiàng)式t2+1+t+t2現(xiàn)在我們考慮將L2中的元素表示成數(shù)對(P,k)，其中P形如iciti是包含了有限多個非零項(xiàng)關(guān)于變量t和t-1的多項(xiàng)式，其中k是整數(shù)，ci/2我們將這些信息寫在矩陣中，其中t作為形式變量,注意由于ci/2，因此t的系數(shù)做的是模2加法而非普通加法：gL2對應(yīng)于數(shù)對(P,k),其一對一的聯(lián)系到如下矩陣：tkP01定理3.1 燈塔群L2同構(gòu)于一個形式如tkP01的矩陣群G，k而P代表包含有限多個非零項(xiàng)的關(guān)于變量t和t-1的多項(xiàng)式，系數(shù)ci/2其中L2的生成元t唯一的對應(yīng)到矩陣t001，a唯一對應(yīng)到矩陣1101證明：構(gòu)建一個映射

13、f:L2G,G中的元素都形如tkP01，f就如同上述將每一個燈塔群L2的元素都聯(lián)系到對應(yīng)形式的矩陣上去，我們需要證明這是一個同構(gòu)映射首先對于任意的g1=S1,k1L2, g2=S2,k2L2它們對應(yīng)的矩陣假設(shè)為tk1P101和tk2P201，假如k1k2，那么顯然矩陣不相等，而如果k1=k2，那么由于g1和g2本身不相等，那么它們各自包含的有限數(shù)集一定不相等，那么P1P2，這兩個矩陣也是不相等的，也就是說f是一個單射對于G中的每一個矩陣，我們都可以之前規(guī)定的形式對應(yīng)的寫出一個L2的元素，所以f也是一個滿射，即f是一個一一映射接下來我們來看f是否保持運(yùn)算：即是否有fg1g2=fg1fg2先看左側(cè)

14、，根據(jù)燈塔群中的乘法定義，g1g2=S1k1+S2S1k1+S2,k1+k2,按照映射f把它寫成矩陣，就是tk1+k2P1+tk1P201，解釋一下多項(xiàng)式部分，我們將亮著的燈泡轉(zhuǎn)化成對應(yīng)t的次冪的系數(shù)，因此k1+S2轉(zhuǎn)化成多項(xiàng)式是tk1P2，集合和S1做并，正好就是對應(yīng)多項(xiàng)式相加，而由于多項(xiàng)式P中t的系數(shù)是做模2加法的，因此就已經(jīng)代表著減去了重疊的部分，即P1+tk1P2這個式子本身就代表著集合做并之后減去了交集的部分fg1fg2=tk1P101tk2P201=tk1+k2P1+tk1P201左右兩端相等，因此f正是一個同構(gòu)映射，那么L2和G是同構(gòu)的證畢我們來看一下如何通過矩陣t001（對應(yīng)生

15、成元t）和1101（對應(yīng)生成元a）相乘得到任意的元素gL2假設(shè)g=tkP01代表L2中的某個元素，其中k代表燈夫位置，多項(xiàng)式P的系數(shù)代表一系列亮起的燈泡我們知道在乘法中我們?nèi)コ藅得到的結(jié)果是燈夫向右移動一步，但是不會改變附近的燈泡狀態(tài)，那么我們來看反映到矩陣上是什么樣的結(jié)果：tkP01t001=tk+1P01根據(jù)我們之前的定義，這個結(jié)果矩陣的意義可以很輕松的看出，P沒有變化代表燈泡狀態(tài)未變，t的指數(shù)由k變?yōu)閗+1代表燈夫右移了一個單位，這正符合我們的預(yù)期我們知道如果對一個元素gL2乘以生成元a，那么我們得到的就是在燈夫位置的燈泡狀態(tài)改變一次，其他不變因此假如我們操作的元素是tkP01，我們希望

16、它右乘矩陣1101（就是a）之后，只有位置k上的燈泡狀態(tài)發(fā)生了變化，即多項(xiàng)式P中只有tk這一項(xiàng)系數(shù)產(chǎn)生變化下面我們來驗(yàn)證一下結(jié)果是否如我們期望那般：tkP011101=tkP+tk01顯然，燈夫位置無變化，而多項(xiàng)式P中tk這一項(xiàng)系數(shù)需要加上1，如果它原本是1，那么這一項(xiàng)就消去（即燈滅），若是0，那么添上這一項(xiàng)，顯然結(jié)果是符合預(yù)期的第四章 字長的計算下面一個需要研究的問題就是L2的元素關(guān)于生成集a,t的字長的計算一個元素的字長指的是我們?yōu)榱说玫揭粋€元素所需要乘以的生成元的最小數(shù)量為了以一種有效的方式描述燈夫創(chuàng)建一個特定的組合之后停在指定位置的情況，我們需要考慮這樣一個L2上最小長度的字Sean

17、Cleary和Jennifer Taback討論過燈塔群中的閉塞字以及其他卷積，探索幾何形狀下燈塔群的凱萊圖和廣泛卷積如果在凱萊圖G,X中從的恒等出發(fā)沒有能延伸過的測地線的話，有著有限生成集的群G中的元素就稱為閉塞的另外還描述了凱萊圖中的元素和一些擺動字間的非凸性1 4.1 群元素的有效描述假設(shè)gL2，亮著的燈泡位置在-3,4,5，燈夫停在整數(shù)2的位置如果要依據(jù)L2的生成集a,t構(gòu)建這個元素g，我們需要在燈臺上進(jìn)行以下步驟 燈夫從整數(shù)0的位置開始，此刻燈臺上沒有燈亮著 燈夫移動到整數(shù)4然后開啟此處的燈 燈夫從4右移一個單位來到5，然后開啟此處的燈 燈夫再從整數(shù)5向左移動，來到整數(shù)-3，開啟此處

18、的燈泡 最后，燈夫從-3向右移動到整數(shù)2的位置，停下當(dāng)然，我們可以很直觀的感受到，如果我們先讓燈夫移動到5開啟此處的燈，然后讓他去-3，再去4，最后回到2，這必然是一種效率非常低下的方式，盡管最終得到的結(jié)果沒有變化定義4.1 如果我們依據(jù)以下標(biāo)準(zhǔn)，為L2的某個元素g構(gòu)建一條路徑： 讓燈夫向右移動到最小的需要點(diǎn)亮的正數(shù)位置，點(diǎn)亮這里的燈泡 繼續(xù)向右移動，過程中遇到需要點(diǎn)亮的就立刻點(diǎn)亮哪個 當(dāng)正數(shù)的燈泡點(diǎn)亮完畢后，讓燈夫回到初始點(diǎn)0 讓燈夫向左移動，按順序點(diǎn)亮過程中遇到的需要點(diǎn)亮的燈泡 左側(cè)需要點(diǎn)亮的燈泡全部點(diǎn)亮之后，讓燈夫移動到最終位置上我們把根據(jù)以上標(biāo)準(zhǔn)-來構(gòu)建出元素g的一條路徑記為g，它就稱

19、為g的有效路徑下面我們會介紹一些符號來描述它先讓燈夫移動向負(fù)數(shù)那邊也會得到一條類似的有效路徑雖然它們不一定是最小長度，但是依舊可以按照下面的描述用來計算g的字長4.2 有效路徑我們用ak=tkatk來表示a關(guān)于tk的共軛，ak表示初始情況下燈夫在0處，兩邊是無限個均未點(diǎn)亮的燈泡，然后燈夫移動到位置k點(diǎn)亮了此處的燈泡，然后回到了起始點(diǎn)0顯然如之前討論過的那樣，所有的ak都是可交換的出現(xiàn)在一個字=i=1mai中成對的ak全部消掉，那表示的是同一位置上的燈開啟一次關(guān)閉一次，沒有變化（反之亦然）注意到如果兩個這樣的共軛乘在一起，比如說a2a7，t相鄰冪之間的消去是有具體意義的，指的是燈夫移動到整數(shù)2點(diǎn)

20、亮此處的燈之后，繼續(xù)向右移動五個單位到整數(shù)7，點(diǎn)亮了此處的燈泡，然后回到了起始點(diǎn)：a2a7=t2at2t7at7=t2at5at7定義4.2 假如L2的一個元素g有著正側(cè)點(diǎn)亮的燈泡：i1<i2<···<ikik>0，和負(fù)數(shù)側(cè)點(diǎn)亮的燈泡：j1>j2>···>jljl>0，以及最終燈夫停下的位置m，我們就把路徑g表示成如下形式：g=ai1ai2···aikaj1aj2···ajltm如果是為了給Ln中的元素n3找到類似于上面的有效路

21、徑，我們僅僅只是在g的表達(dá)式中給生成元a添上冪4.3 計算字長有一種簡單直接的算法，來計算關(guān)于生成集a,t的元素gL2從上面提到的任意一種有效路徑的字長定理4.3 給出一個gL2，先根據(jù)定義4.1來寫出有效路徑g以及記號ak=tkatk然后我們從這條路徑上來計算數(shù)值量，記為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所需要乘以的生成元個數(shù)，從上式可以看出有k+l個a，而t的個數(shù)我們看指數(shù)和就可以,負(fù)指數(shù)部分去掉負(fù)號來計算，是2ik+jl+m+jl個t那么我們把g中的正負(fù)下標(biāo)部分換位，再次將共軛部分展開g=tj1atj2j1atjljl1ati1+jlati2i1atikik1atmik同樣是看生成元個數(shù)，a還是k+l個，而t按照指數(shù)和來看是2jl+ik+mik個，那么顯然g的字長，被這兩個長度限制住了，即最多也只能是k+l+min2jl+ik+mik,2ik+jl+m+jl，也就是Dg第二步，我們來證明g

23、的字長至少應(yīng)該是Dg：我們想得到g字長的下界，就需要從幾何角度來分析g，它是一個代表亮著的燈的集合和一個整數(shù)，要把它的燈塔圖和構(gòu)成g的a和t聯(lián)系起來假設(shè)g包含n個亮著的燈泡，那么顯然我們知道它至少要包含n個a才能完成將這n個燈點(diǎn)亮的操作，那么易知，表示成g形式的g包含至少k+l個a再來看t，為了計算出t的總數(shù)，需要分別來看正和負(fù)兩方面t的指數(shù)和同時也是包含了燈夫的最終位置的，先來考慮部分指數(shù)和： 正數(shù)側(cè)最右端被點(diǎn)亮的燈為ik，那么顯然t的指數(shù)和至少為ik(這很好理解，燈夫從起始點(diǎn)0往右側(cè)移動時，先點(diǎn)亮第一個遇到的需要點(diǎn)亮的燈，然后一路下去到ik) 同理負(fù)數(shù)側(cè)最左邊被點(diǎn)亮的是jl,那么t的指數(shù)和

24、至少是-jl 然后，單看燈夫的最終位置，t的指數(shù)和一定是m那么，我們分兩種情況來看的話： 假如燈夫先點(diǎn)亮右側(cè)，那么t用到的指數(shù)和就是0,ik,-jl,m,全部加起來就得到t的總指數(shù)和，是2ik+jl+m+jl 假如燈夫先點(diǎn)亮左側(cè)，那么t用到的指數(shù)和就是0,-jl,ik,m,全部加起來就得到t的總指數(shù)和，是2jl+ik+mik這樣我們就得到了g的字長的下界，顯然它就是Dg，再結(jié)合第一部分的證明，定理證畢如果仔細(xì)查看Dg的公式，就很容易發(fā)現(xiàn)Dg是g的燈塔圖中幾個有關(guān)量的總和： 被點(diǎn)亮燈泡的數(shù)量 方向A上最遠(yuǎn)處被點(diǎn)亮的燈泡和原點(diǎn)距離的兩倍 方向B上最遠(yuǎn)處被點(diǎn)亮的燈泡和原點(diǎn)的距離 燈夫和方向B上最遠(yuǎn)燈

25、泡之間的距離例2 我們舉出一個根據(jù)定理給出的Dg表達(dá)式直接計算字長的例子，我們寫出例1中的g的路徑g=a4a5a6a1a6t2，然后，計算出字長：Dg=3+2+min18+26,18+2+6=27第五章 燈塔群和凱萊圖為了給群L2得到一個凱萊圖，我們必須得稍微變換一下生成集我們考慮L2的這樣一個生成集t,at(以及Ln的生成集t,at,a2t,······,an-1t,n3)這有時也被稱為通電自由生成集，即移動和開啟燈泡可以用單一的一個生成元完成，也就是說通電（即點(diǎn)亮燈泡）這一行為不再需要自己的生成元不難看出元素的有效路徑和字度量的有

26、效計算也是適用于這種生成集的Murray Elder研究過燈塔群的測地線表達(dá)燈塔群Ln是無窮多錐型的，沒有正則測地線表達(dá)，關(guān)于某些生成集有反測地線表達(dá)而燈塔群關(guān)于一個生成集的測地線全表達(dá)不是相反的而是無關(guān)的，同時關(guān)于另外一個生成集它的測地線全表達(dá)卻是相反且無關(guān)的25.1 DiestelLeader圖：L2關(guān)于生成集t,at的凱萊圖將在下面展現(xiàn)，是一種非常特殊的圖形，叫做DiestelLeader圖這些圖是為了回答以下的問題而引進(jìn)的：每一個“好”的無限圖都擬等距于一些有限生成群的凱萊圖嗎？這里的“好”包含了一些專門的條件，例如：在其他條件下，圖必須是連通的且在每一個頂點(diǎn)都具有相同的度為了定義一個

27、DiestelLeader圖，我們考慮兩個度為d+1的無限樹，將其表示為T1和T2我們給樹標(biāo)定方向使每個頂點(diǎn)都有一條輸入邊和d個傳出邊請看，圖2和3的樹（每棵樹只顯示了一部分）在每個樹上固定一個高度函數(shù)i:Ti,i=1,2這個高度函數(shù)固定了高度0;有一條輸出邊是從高度0的一個頂點(diǎn)出發(fā)止于高度1的一個頂點(diǎn)，還有一條邊是從高度-1的一個頂點(diǎn)出發(fā)止于高度0的一個頂點(diǎn)以這種方式繼續(xù)下去，我們已經(jīng)將Ti中的每一級頂點(diǎn)都用一個整數(shù)來確定看下面的圖2，已經(jīng)在一個樹上舉了一個高度函數(shù)的例子如果在樹上選擇了不同的高度函數(shù)，那么得到的就是同構(gòu)的DiestelLeader圖圖2(來自文獻(xiàn)4)每一邊固定了高度函數(shù)的樹

28、做乘積T1×T2DiestelLeader圖DL2(2)的頂點(diǎn)集是T1×T2的子集(圖中的兩個坐標(biāo)位于水平線上)舉個例子，數(shù)對(s,t)是DL2(2)的頂點(diǎn)，注意這張圖只表現(xiàn)出了無限樹的一小部分用T1×T2來表示這兩個樹T1和T2的乘積而T1×T2中的點(diǎn)是形如(t1,t2)的有序?qū)?，其中t1T1,t2T2DiestelLeader圖DL2(d)是這些樹乘積的一個特別的子集為了識別這種圖（如其它任何圖形一樣）我們來描述它的頂點(diǎn)和邊(1) DiestelLeader圖DL2(d)中的頂點(diǎn)：定義5.1 DiestelLeader圖DL2(d)的頂點(diǎn)集是樹的乘積

29、T1×T2的一個子集且這兩個坐標(biāo)的高度之和是0：(t1,t2)tiTi,1t1+2t2=0一個讓DL2(d)的頂點(diǎn)變得可視的方法是向相反的方向定向T1和T2，也就是把它們畫在同一頁上，向頁面頂部移動時T1的高度函數(shù)增加，而同時這個方向上T2的高度函數(shù)會減少這樣畫樹就會使得T1高度k的位置在紙上同一水平是T2的高度-k現(xiàn)在DiestelLeader圖DL2(d)的頂點(diǎn)只是簡單的多對頂點(diǎn)，每個樹取一點(diǎn)，且二者在同一水平線上關(guān)于這對樹的表示，請參見圖2，其中每一棵樹的高度都標(biāo)注在圖的兩側(cè)使用圖2的標(biāo)注，可以看到DL2(d)上的點(diǎn)(s,t)請注意圖2中依舊只有無限樹的一部分(2) Diest

30、elLeader圖DL2(d)中的邊：定義5.2 使用圖3中的標(biāo)注，如果頂點(diǎn)s0和s1是由T1中的邊連接且頂點(diǎn)t0和t1是由T2中的邊連接的，就稱頂點(diǎn)(s0,t0)和(s1,t1)是由邊連接的由于兩個坐標(biāo)的高度之和必須保持在0，去找到DL2(d)中通過一條單獨(dú)的邊連接到(s0,t0)的頂點(diǎn)，我們只能做以下兩件事中的一件： 在T1高度增加1的同時T2的高度降低1 在T1高度降低1的同時T2的高度增加1圖3(來自文獻(xiàn)4)使用每個樹標(biāo)記的頂點(diǎn)，我們可以看到圖DL2(2)的頂點(diǎn)(s0, t0), (s0, t0), (s2, t2), and (s2, t2)都是通過一條單獨(dú)的邊連接到頂點(diǎn)(s1,t1

31、)的T1(或T2)中有著d條輸出邊連接s1(或t1)到一個高度增加1的頂點(diǎn)以及一條單獨(dú)的邊連接s1(或t1)到T1(或T2)中高度減少1的一個頂點(diǎn)，我們可以看到DL2(d)中有著2d個頂點(diǎn)通過一條單獨(dú)的邊連接到(s1,t1)在圖3中通過DL2(2)中的一條邊連接了點(diǎn)(s0,t0)和(s1,t1)通過一條單邊連接到(s1,t1)的三個剩余的頂點(diǎn)是(s0, t0), (s2, t2), and (s2, t2)(圖3)重要提醒：當(dāng)看圖2和3的時候，我們必須注意畫在每個樹上的邊不代表它是存在于圖DL2(2)中的邊在圖2和3中繪制樹的乘積給我們提供了簡單的方法來看到DL2(2)中的頂點(diǎn)，或相等地來看如

32、我們將在下面展示的，凱萊圖(L2,t,at)的頂點(diǎn)以上我們所描述的邊我們知道一定會出現(xiàn)在DiestelLeader圖中，但是實(shí)際上沒有繪制在圖2或3中對于DL2(2)中頂點(diǎn)之間的邊的例子，見圖65.2 作為L2中元素的DL2(2)中的頂點(diǎn)：我們現(xiàn)在展示凱萊圖(L2,t,at)就是DiestelLeader圖DL2(2)我們必須展示如何以獨(dú)特的捕獲群結(jié)構(gòu)的方式來將DL2(2)中的一個頂點(diǎn)和L2中的一個元素聯(lián)系起來這涉及到了在樹中確認(rèn)頂點(diǎn)的另一種方法 在一個樹上標(biāo)記邊我們考慮一個固定高度函數(shù)的價3無限樹TT的每個頂點(diǎn)都有兩個輸出邊，然后我們標(biāo)記左邊為0，右邊為1. 在樹1上確認(rèn)一個頂點(diǎn)在樹T上選擇

33、高度k的一個頂點(diǎn)v，T的邊全都用0和1標(biāo)記從v出發(fā)有一條獨(dú)一無二的向下經(jīng)由T的路徑，每一步高度下降了1通過這條路我們記下邊的標(biāo)簽會得到一連串的0和1但是最終得到的總是0我們將這一串記作i=a1,a2,a3,a4,···，而ai0,1，aj=0對大于某個常數(shù)的j成立 在樹2上確認(rèn)一個頂點(diǎn)反過來，我們給一串i=a1,a2,a3,a4,···，而ai0,1，aj=0對大于某個常數(shù)的j成立，以及一個整數(shù)k可以在T的高度k找到一個獨(dú)一無二的點(diǎn)，從出發(fā)一條獨(dú)一無二的向下路徑可以被標(biāo)記為圖4(來自文獻(xiàn)4)這一串1,0,1,0,0,0,·

34、· ·以及高度k=2描述了樹T上獨(dú)一無二的一個點(diǎn)圖5(來自文獻(xiàn)4)DL2(2)的元素由1,2,2唯一表示，其中1=1,0,1,0,0,···而2=1,0,0,0,0,···給定條件下，假設(shè)這樣的序列已經(jīng)包含了全部的05.3 DL2(2)作為L2的一個凱萊圖：我們現(xiàn)在準(zhǔn)備好呈現(xiàn)出一個關(guān)于DiestelLeader圖DL2(2)和L2中的元素之間的雙射我們上面已經(jīng)描述過如何將DL2(2)中的元素以元組1,2,2的形式展現(xiàn)考慮L2中的一個元素，通過g=(P,k)給出，P是一個變量多項(xiàng)式(關(guān)于t)而且t和t-1的系數(shù)屬于/

35、2，有有限多個非0系數(shù)，k讓數(shù)列ai表示P的系數(shù)，其中ai是ti的系數(shù)將ai分成兩個子列：1=aii<k和2=aiik，其中前一個是按照相反的順序排列的，即ak-1,ak-2,···注意這兩個數(shù)列最終必須包括全部的0因此，我們將g看做三元組1,2,2，然后對應(yīng)DL2(2)中的頂點(diǎn)就是非常清楚的了例如，在圖5中描述DL2(2)的頂點(diǎn)對應(yīng)于矩陣 證明DL2(2)就是關(guān)于生成群t,at的凱萊圖L2完全由延伸到兩個圖之間的圖同構(gòu)給出Jennifer Taback把部分結(jié)論推廣到了高維燈塔群中，介紹了高維燈塔群或者說DiestelLeader群dq在d3的情況下是圖自

36、動的，實(shí)際上是找到了一族新的圖自動的群且它們自己并非自動群35.4 在凱萊圖上移動我們現(xiàn)在要理解如何在凱萊圖上移動，以同樣的方式我們也就知道了如何在凱萊圖×上移動我們知道從×,1,0,0,1中任意的一個頂點(diǎn)g(我們提到g的時候指頂點(diǎn)的同時也指這個點(diǎn)對應(yīng)的群中的元素g)，有一個標(biāo)為(1,0)的從g發(fā)出沿x方向終止于一個單位長度之后頂點(diǎn)的邊，同樣的有標(biāo)為(0,1)的從g出發(fā)沿y方向終止與一個單位長度之后頂點(diǎn)的邊，當(dāng)然類似的也有由生成元的逆來表示的邊從g出發(fā)沿標(biāo)為s的邊走下去得到的就是對應(yīng)于gs的那個頂點(diǎn)對DL2(2)=(L2,t,at)，我們希望直觀地看到如何通過一條單獨(dú)的邊連

37、接到不同于坐標(biāo)1,2,k的一個頂點(diǎn)比如說我們在一個頂點(diǎn)g=1,2,kL2，然后通過一條等同于生成元t作用的邊(也就是說，我們把g看做L2的一個元素，然后跟生成元t做乘法來看結(jié)果gt)，我們來看它連接到的那個頂點(diǎn)gt的坐標(biāo)究竟是什么為了研究這個問題我們需要借助矩陣，把t寫成t001，然后1,2,k對應(yīng)的元素g寫成相應(yīng)的tkP01的形式，注意如果我們有多項(xiàng)式的系數(shù)無窮序列ai，那么就有1=aii<k和2=aiik如上所示，gt=tk+1P01圖6(來自文獻(xiàn)4)這一對實(shí)線畫出的邊代表圖DL2(2)中生成元t作用于DL2(2)中的兩個頂點(diǎn)(分別用實(shí)心圓和實(shí)心方塊表示的)其他虛線代表的是單個樹中的

38、邊，但是不是DL2(2)中的邊然后這把對應(yīng)的DL2(2)中的頂點(diǎn)的三元組改變成了什么樣呢？首先可以明確的是整數(shù)坐標(biāo)(即元組中的第三個部分)從k變到了k+1，而多項(xiàng)式P既然沒有變化，那么在gt和t中P的系數(shù)是完全一樣的從g到gt改變的部分是我們把a(bǔ)i劃分成兩個子列的那個分割點(diǎn)：從gt中我們得到的是1=aii<k+1和2=aiik+1，前者是以ak為起始的注意到我們?yōu)榱说玫?實(shí)際上將2的第一個數(shù)挪走了，然后把它放在了1的最前端，就得到了1當(dāng)然2就是原本的2去掉它最前端的那個數(shù)，剩下的部分現(xiàn)在我們就看到了DL2(2)中頂點(diǎn)g和gt的坐標(biāo)之間的精確差異，同樣的我們也可以把gt在DL2(2)上通過

39、如下操作變換到g在樹T1上，沿著標(biāo)記為ak的邊到達(dá)高度k+1的另一個新頂點(diǎn)，在樹T2上，只需去除掉路徑的初始邊緣，這樣，截斷的路徑就起始于-(k+1)這樣對應(yīng)于B1,B2,k+1的新頂點(diǎn)是通過一條單獨(dú)的邊連接到1,2,k的要理解從頂點(diǎn)g出發(fā)通過一條等于at作用的邊得到了什么，我們需要連續(xù)乘以a和t兩個生成元的矩陣：gat=tk+1tk+P01gat的多項(xiàng)式項(xiàng)和P只有一個系數(shù)不同：tk這一項(xiàng)的系數(shù)增加了1，而由于系數(shù)是取自集合/2，因此系數(shù)做的是模2加法，簡單地說就是0會變成1反之1變成0整數(shù)的坐標(biāo)現(xiàn)在是k+1，我們把tk+P的系數(shù)分成兩個子列，我們得到1，第一個數(shù)是ak+1(模2加法)，其后的數(shù)就是1，而2=aiik+1頂