同步鏈與純正非同步半群

李旺威, 黎先華

(1. 嶺南師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院, 廣東 湛江 524048; 2. 蘇州大學(xué)數(shù)學(xué)科學(xué)學(xué)院, 江蘇 蘇州 215006)

Cerny猜想是同步自動機(jī)研究的重要問題之一,許多科學(xué)技術(shù)問題可以用同步自動機(jī)模型來解決[2-5]．近年來, 國際上一些著名的群論及半群的專家投入到該問題的研究, 獲得了許多創(chuàng)新的成果．2014年, Araújo等[6]證明了本原群同步于每一秩為n-2的變換, 本原群同步于每一秩為2的變換和本原群同步于每一秩為3或4的非一致變換．2019年, Ryzhikov[7]給出無非平凡圈自動機(jī)同步字長度的上下界．近年來, Li等[8-9]解決了幾乎同步群的兩個公開問題, 并證明了非本原群同步于一類非一致變換．本文擬討論置換群和一個非可逆變換是否可以生成一個常量映射．

1 判斷同步半群的方法

若半群〈G,α〉包含一個常量映射, 則稱G同步于變換α．若半群的每一個元素都落在一個子群中, 則稱該半群是完全正則的．設(shè)α∈TnSn和ker(α)={A1,A2,…,Ar}, 則定義α的核類型為[|A1|,|A2|,…,|Ar|]．若半群〈G,α〉是非同步半群, 則存在β∈〈G,α〉G使得半群〈G,β〉完全正則．因此, 完全正則半群在非同步半群中扮演著“堤壩”的角色, 即完全正則半群能阻止生成集生成常量映射, 自然希望能找到一些特殊的元素“打破”這個“堤壩”,首先給出同步鏈的定義．

設(shè)S是Tn的子半群和e∈S．若e2=e,則稱e是S的冪等元, 且記E(S)={x∈S:x2=x}．設(shè)Y={a1,a2,…,at}是集合Xn的子集,e是Tn的冪等元, 且滿足aie=a(ai,a=at∈Y)和xe=x(x∈XnY), 記為e=[a1,a2,…,at], 其中at=a．

設(shè)ei=[ai1,ai2,…,ait](i=1,2,…,r)．對于冪等元ei, 若非單點(diǎn)核類是一個同步鏈,則稱集合E={e1,e2,…,er}具有性質(zhì)SYN．由于e1e2…er是一個常量映射, 則半群S是同步的．因此, 若E(S)包含一個具有性質(zhì)SYN的子集E,則該半群S是同步的．根據(jù)上面的方法,可給出一些滿足Cerny猜想的變換半群．

例2根據(jù)上面的符號,有

1) 設(shè)Tn=〈Sn,[1,2]〉．由于α=[1,2][2,3]…[n-1,n]是常量映射,且

(1,3)[1,2](1,3)=[3,2],(3,2)[3,2](3,2)=[2,3],

(2,4)[2,3](2,4)=[4,3],(4,3)[4,3](4,3)=[4,3],

…

(n-2,n)[n-1,n-2](n-2,2)=[n,n-1],(n,n-1)[n,n-1](n,n-1)=[n-1,n],

其中(i,j)∈Sn, 則α*=[1,2]g1[1,2]g2…gn-2[1,2]gn-1是一個常量映射．換言之, 在集合E(Tn)中存在具有性質(zhì)SYN的子集E={[1,2],[2,3],…,[n-1,n]},故Tn是同步半群,且α*的長度為2(n-1); 因此,全變換半群Tn=〈Sn,[1,2]〉滿足Cerny猜想．

2) 對于α∈Tn, 定義Z(α)=XnXnα, 且記|Z(α)|為α的虧數(shù)．設(shè)Singn=TnSn．由于Singn的任一元素是虧值1的冪等元的乘積,有Singn=〈e∈E(Singn):Z(e)=1〉．又由于[i,i+1]∈{E(Singn):Z(e)=1}, 其中1≤i≤n-1, 則在集合E(Singn)中存在具有性質(zhì)SYN的子集E={[1,2],[2,3],…,[n-1,n]}, 故α*=[1,2]g1[1,2]g2…gn-2[1,2]gn-1是一個常量映射且α*的長度為(n-1); 因此,半群Singn=〈e∈E(Singn):Z(e)=1〉滿足Cerny猜想．

3) 設(shè)K(n,r)={α∈Singn: rank(α)≤r}．Evseev等[10]已證明K(n,r)由秩為r的冪等元生成, 即K(n,r)=〈e∈E(K(n,r)): rank(e)=r〉．由于[i,i+1,…,i+t]∈{E(K(n,r)): rank(e)=r}, 其中i=1,1+t,1+2t,…; 1≤t≤n-1, 則在集合E(K(n,r))中存在具有性質(zhì)SYN的子集E, 故α*=[1,2,…,1+t][1+t,3+t,…,1+2t]…[1+rt,2+rt,…,n]是一個常量映射且α*的長度為(n-1); 因此, 半群〈e∈E(K(n,r)): rank(e)=r〉滿足Cerny猜想．

4) 設(shè)On是Singn的子半群, 且由Xn上的保序變換組成．Howie[11]證明了On由虧值1的冪等元生成, 即On=〈e∈E(On):Z(e)=1〉．由于[i,i+1]∈{e∈E(On):Z(e)=1}, 其中1≤i≤n-1, 則在集合E(On)中存在具有性質(zhì)SYN的子集E, 故α*=[1,2][2,3]…[n-1,n]是常量映射且α*的長度為(n-1); 因此, 半群〈e∈E(On):Z(e)=1〉滿足Cerny猜想．

6) 設(shè)G是Xn上的循環(huán)群, 其中n是素數(shù),設(shè)冪等元e=[1,2]．由于

…

對于本原群G,應(yīng)用同步鏈的概念可以證明下面兩個類型變換半群是同步的．

引理3設(shè)G是集合Xn上的本原群,A?Xn,則存在Xn的一個同步鏈,即存在gi∈G(i=1,2,…,r)使得[A,Ag1,…,Agr]是Xn的一個同步鏈．

定理4設(shè)G是集合Xn上的本原群,e是核類型為(t,1,…,1)(t≥2)的冪等元, 則S=〈G,e〉是同步半群和常量映射的長度至多為2(n-1)．

注: 對于一般的變換α,較難確定半群〈G,α〉是否同步．然而,基于定理4,可以通過判斷群G和α是否可以生成核類型為(t,1,…,1)(t≥2)的變換,從而確定半群〈G,α〉是否同步．利用代數(shù)軟件GAP可以發(fā)現(xiàn)本原群G與很多類型的變換α能生成核類型為(t,1,…,1)(t≥2)的變換．

定理5設(shè)G是集合Xn上的本原群,e是核類型為(2,2,1,…,1)的冪等元, 則S=〈G,e〉是同步半群．

證明 設(shè)e是核類型為(2,2,1,…,1)的冪等元,A1和A2是e的非單點(diǎn)核類．由G的本原性知,存在g1,g2,g3∈G使得A1e1={a1},A2e1={a2}與{a1,a2}?B, 其中e1=(eg1)r1和e2=(g2eg3)r2是冪等元,B是ker(e2)的核塊; 因此,A1∪A2是ker(e1e2)的塊,從而f=e1e2是核類型(4,1,…,1)的冪等元．由定理4, 得〈G,f〉是同步半群,故S=〈G,e〉是同步半群．

2 純正非同步半群

對于半群S和S中元素a, 若存在x∈S使得axa=a,則稱a是S的正則元．若半群S的每個元素都是正則的,則稱S是正則半群．若半群S是正則的且其冪等元集合是一個子半群,則稱為純正半群．半群S的Green關(guān)系L,R,H,D,J分別定義為: 對于a,b∈S,aLb?S1a=S1b,aRb?aS1=bS1,H=L∩R,D=L°R=R°L,aJb?S1aS1=S1bS1．McAlister[13]證明了半群S=〈G,e〉是純正半群．

定理6[13]設(shè)G是Xn上的置換群和e=[1,2]是冪等元．若2屬于1所在的軌道上, 則半群S=〈G,e〉是純正的當(dāng)且僅當(dāng)存在g∈G使得1g=2,g2∈F和g-1Fg=F,其中F是G上關(guān)于1的穩(wěn)定子群．

對于上面的結(jié)論,可以發(fā)現(xiàn)半群S=〈G,e〉是非同步的．證明該結(jié)論, 須先證明〈G,α〉是完全正則的,即下面的引理．設(shè)G是Xn上的傳遞非本原群,Δ是G的非平凡塊,Σ={Δg:g∈G}是G的完全非本原系．

引理7設(shè)G是Sn的子群和α∈TnSn且滿足rank(α2)=rank(α), 則S=〈G,α〉是完全正則半群當(dāng)且僅當(dāng)對任意的g∈G有rank(αgα)=rank(α)．

證明 設(shè)S=〈G,α〉是完全正則半群．由于〈G,α〉G是完全單的,即僅有一個J-類, 則對于任意的g∈G,α和αg都屬于這個J-類, 故對任意的g∈G有rank(αgα)=rank(α)．

反之, 設(shè)對任意的g∈G有rank(αgα)=rank(α)．由于α且滿足rank(α2)=rank(α), 則存在冪等元e使得(α,e)∈H, 即e和α滿足im(e)=im(α), ker(e)=ker(α)．注意到, 對任意的g∈G有rank(αgα)=rank(α)等價于對于任意的g∈G有g(shù)映射im(α)成ker(α)的一個橫截, 故對于任意的g∈G有g(shù)映射im(e)成ker(e)的一個橫截,則對任意的g∈G有rank(ege)=rank(e), 從而〈G,e〉是完全正則半群．

設(shè)x=αg1αg2…αgth∈〈G,α〉, 其中g(shù)1,g2,…,gt,h∈G．由(α,e)∈H,有(αgi,egi)∈H．又因〈G,e〉是完全正則半群,〈G,e〉G和〈G,α〉G有相同的冪等元集合,故存在冪等元f∈〈G,e〉使得(αg1αg2…αgt,f)∈H,則對于任意的g∈G有g(shù)映射im(f)成ker(f)的一個橫截．因?yàn)閤與αg1αg2…αgt相差一個群元素h,所以存在冪等元f′∈〈G,e〉使得(x,f′)∈H．由于有限群的子半群是一個子群, 則〈G,α〉∩Hf′是一個以f′為單位元的群．由此可知,〈G,α〉的任一元素都屬于某個子群,故〈G,α〉是完全正則半群．

定理8對定理6中的群G和冪等元e, 半群S=〈G,e〉是非同步半群．

證明 對于定理6中的G和冪等元e,G一定是非傳遞的或傳遞非本原的．設(shè)G是非傳遞群．由于G有k(k>1)條軌道且集合{1,2}包含在1條軌道中,則半群S=〈G,e〉中元素的最小秩為k,即S中沒有常量映射,故S是非同步半群．

設(shè)G是傳遞群．由于G滿足定理6的條件,則{1,2}?Δ, 其中Δ是G的非平凡塊．若{1,2}=Δ, 則對任意的g∈G,{1,2}都不能吸收其他單點(diǎn)成為一個新的核類．但對于g∈G, 變換ege的非單點(diǎn)核類由單點(diǎn)構(gòu)成,且該非單點(diǎn)核類是一個非平凡塊, 故存在hi∈G,i=1,2,…,s, 使得ker(eh1eh2…h(huán)se)={Δg:∈G}．若{1,2}?Δ, 存在h∈G使得Bj∈ker(ehe)和Ai?Bj?Δg, 故存在hi∈G,i=1,2,…,s,使得{1,2}吸收單點(diǎn)變成一個非平凡塊, 且e的單點(diǎn)也合并成G的非平凡塊, 有ker(eh1eh2…h(huán)se)={Δg:g∈G}．令β=eh1eh2…h(huán)se,則對所有g(shù)∈G, 有rank(βgβ)=rank(β)．根據(jù)引理7, 〈G,β〉是完全正則半群, 得rank(β)是半群S中元素最小的秩, 故半群S是非同步半群．

利用代數(shù)軟件GAP[14]嘗試確定滿足定理8中的群類, 稱該類群為純正非同步群,結(jié)果如表1所示．圖1為GAP程序．通過GAP軟件可以確定其生成集, 但在GAP軟件中至多能計算級數(shù)為30的傳遞置換群,而級數(shù)為16的傳遞置換群有1 954個, 且絕大部分級數(shù)為16的傳遞群都滿足定理8的條件,故表1中僅給出級數(shù)為16傳遞群的一些代表元．同樣地,級數(shù)為18,20,24,28,30的傳遞置換群的個數(shù)分別是983,1 117,25 000,1 854,5 712,表1也僅列出部分代表元．表1中符號的含義為:E(4)表示級數(shù)為4的第2個傳遞置換群;D6(6)表示級數(shù)為6的第2個傳遞置換群;E(8),E(8):2,E(8):E4分別表示級數(shù)為8的第3,9,18個傳遞置換群;D(10) 表示級數(shù)為10的第2個傳遞置換群;D6(6)[×]2表示級數(shù)為12的第3個傳遞置換群;D14(14)表示級數(shù)為14的第2個傳遞置換群; TnNi表示級數(shù)為n的第i個傳遞置換群．

圖1 GAP程序

表1 純正非同步群