（基础数学专业论文）自由逆半群的groebnershirshov基.pdf

a b s t r a c t i nt h i st h e s i s ，w ef i n dg r s b n e r - s h i r s h o vb a s e sf o rf r e ei n v e r s es e m i g r o u p sw i t hr e s p e c t t ot h ed e g - l e xo r d e r i n go fw o r d s ，a n dg i v et h e ( u n i q u ea n ds h o r t e s t ) n o r m a lf o r m si nt h e c l a s s e so fe q u i v a l e n tw o r d so faf r e ei n v e r s es e m i g r o u p t h i st h e s i sc o n s i s t so ff o u rp a r t s t h ep r e f a c eg i v e sab r i e fh i s t o r yo fg r s b n e r - s h i r s h o vb a s i st h e o r ya n df r e ei n v e r s es e m i g r o u p ，a n ds u m m a r i z e ss o m er e c e n tr e s u l t so n g r s b n e r - s h i r s h o vb a s e sf o rg r o u p sa n ds e m i g r o u p s i nc h a p t e r1 ，w ei n t r o d u c eg r s b n e r - s h i r s h o vb a s i st h e o r yf o ra s s o c i a t i v ea l g e b r a sa n ds e m i g r o u p sr e s p e c t i v e l y i nc h a p t e r2 ， w ed e f i n ea n ds t u d yo r d e r e dc a n o n i c a li d e m p o t e n t si nf r e ei n v e r s es e m i g r o u p s i nt h el a s t c h a p t e r ，w ep r o v eo u r m a i nt h e o r e ml e txb eas e t ，x 一1 = z 一1 i z x ) w i t hx nx 一1 = 刀， aw e l l o r d e r i n go ny = x ux 一1a n da l s ot h ed e g - l e xo r d e r i n go ny 。，珂) t h ef r e ei n v e r s e s e m i g r o u pg e n e r a t e db yx l e ts cy + y + b et h es e to ft h ef o l l o w i n gd e f i n i n gr e l a t i o n s ( a ) a n d ( b ) ： ( a ) ( e ，e ) ，w h e r eb o t hea n df a x eo r d e r e dp r i m ec a n o n i c a li d e m p o t e n t s ，e i sa c a n o n i c a li d e m p o t e n ta n d e e f ； ( b ) ( x - l e 7 z f 7 z 一1 ，f r x 一1 e 7 ) ，w h e r ex y ，b o t hx - l e xa n dx 7 z 一1a r eo r d e r e dp r i m e c a n o n i c a li d e m p o t e n t s t h e nsi sag r s b n e r - s h i r s h o vb a s i sf o rt h ef r e ei n v e r s es e m i g r o u p 尼( x ) w i t hr e s p e c t t ot h ed e g - l e xo r d e r i n go fy 。 a sas t r a i g h t f o r w a r da p p l i c a t i o no ft h ea b o v et h e o r e m ，w eg i v ean o r m a lf o r mo ft h ef r e e i n v e r s es e m i g r o u p 口( x ) k e y w o r d s ：g r s b n e r - s h i r s h o vb a s i s ，n o r m a lf o r m ，f r e ei n v e r s es e m i g r o u p 摘要( a b s t r a c t ) a b s t r a c t p r e f a c e c h a p t e r1 p r e l i m i n a r i e s c o n t e n t s c h a p t e r2 o r d e r e dc a n o n i c a li d e m p o t e n t s c h a p t e r3 m a i nt h e o r e m r e f e r e n c e a c k n o w l e d g e m e n t p u b l i c a t i o n s l l l 1 3 6 1 3 1 6 2 0 2 1 p r e f a c e g r s b n e r - s h i r s h o vb a s i st h e o r y , w h i c hh a sb e c o m eam a j o rr e s e a r c ha r e ai nc o m p u - t a t i o n a la l g e b r aa n dc o m p u t e rs c i e n c e ，w a si n v e n t e di n d e p e n d e n t l yb ya i s h i r s h o v 【4 s ， s e ea l s o 1 8 ，f o rn o n - c o m m u t a t i v ea n dn o n - a s s o c i a t i v ea l g e b r a s ，a n db yh h i r o n a k a 【3 2 】 a n db b u c h b e r g e r 【2 0 f o rc o m m u t a t i v ea l g e b r a s ( i nt h ec o m m u t a t i v ec a s e ，t h eg r s b n e r - s h i r s h o vb a s i si sw e l l - k n o w na st h eg r s b n e rb a s i s ) t h et h e o r yo fg r s b n e r - s h i r s h o vb a s e s i sg e n e r a t i n gi n c r e a s i n gi n t e r e s tb e c a u s eo fi t su s e f u l n e s si np r o v i d i n gc o m p u t a t i o n a lt o o l s a n di ng i v i n ga l g e b r a i c a ls t r u c t u r e sw h i c ha r ea p p l i c a b l et oaw i d er a n g eo fp r o b l e m si n m a t h e m a t i c s ，s c i e n c e ，e n g i n e e r i n g ，a n dc o m p u t e rs c i e n c e i np a r t i c u l a r ，t h et e c h n i q u e o fg r s b n e r - s h i r s h o vb a s e si sp r o v e dt ob ev e r yu s e f u li nt h es t u d yo fp r e s e n t a t i o n so f a s s o c i a t i v ea l g e b r a s ，l i ea l g e b r a s ，s e m i g r o u p s ，g r o u p s ，q a l g e b r a s ，e t c b yg e n e r a t o r sa n d d e f i n i n gr e l a t i o n s ，s e e ，f o re x a m p l e ，t h eb o o k 【1 7 】b yl a b o k u ta n dg k u k i n ，s u r v e y p a p e r s 【1 5 ，1 6 b yl a b o k u ta n dp k o l e s n i k o v ，a n d 【1 2 b yl a b o k u ta n dy u q u n c h e n t h e r ea r es e v e r a lr e c e n tr e s u l t so ng r s b n e r - s h i r s h o vb a s e sf o rg r o u p sa n ds e m i - g r o u p s g r s b n e r - s h i r s h o vb a s e sf o rb r a i dg r o u p si nd i f f e r e n ts e t s o fg e n e r a t o r sw e r e f o u n db yl a b o k u te t c i n 【8 ，9 ，1 1 ，1 4 i np a r t i c u l a r ，a r t i n - m a r k o v ( 【2 ，3 6 】) ，g a r s i d e ( 【3 1 】) ，a n db i r m a n - k o - l e e ( 4 】) n o r m a lf o r m s o fab r a i dg r o u pw e r eg i v e ni nt h e s ep a p e r s ag r s b n e r - s h i r s h o vb a s i sf o rac h i n e s em o n o i d ( 3 0 】) w a sf o u n da n dt h es t a i r c a s en o r m a l f o r m ( 3 0 】) o fac h i n e s em o n o i dw a sg i v e nb yy u q u nc h e na n dj i a n j u nq i ui n 【2 4 a g r s b n e r - s h i r s h o vb a s i sf o rt h ea d j a _ ne x t e n s i o no ft h en o v i k o vg r o u pw a sf o u n db yl a b o k u ta n dv v c h a i n i k o vi n 【1 0 ，w h i c ha l s og a v et h ea d j a np r o o fo ft h ea d j a n - r a b i n t h e o r e m ( 1 ，4 3 】) k a k a l o r k o t i ( 3 4 ，3 5 ) h a sa c t u a u yf o u n dg r s b n e r - s h i r s h o vb a s e s f o rs o m eg r o u p so fn o v i k o v - b o o n et y p e ( 3 9 ，1 9 ) a n dg i v e nan e wp r o o fo fb o k u t ( 【5 】) a n d d c o l l i n s ( 2 8 ，2 9 ) r e s u l t s y u q u nc h e n a n dc h a n y a nz h o n g 【2 5 ，2 6 ，2 7 f o u n dg r s b n e r - s h i r s h o vb a s e sf o rh n n e x t e n s i o n so fg r o u p s ，s o m eo n e - r e l a t o rg r o u p sa n db r a i dg r o u p s i na d y a n - t h u r s t o ng e n e r a t o r s b yu s i n gg r s b n e r - s h i r s h o vb a s e s ，y u q u nc h e n 【2 2 ，2 3 】 g a v et h ee x t e n s i o n so fg r o u p sa n da l g e b r a s ，a n dl a b o k u t ，y u q u nc h e na n dq i u h u i m o 【1 3 】g a v ee m b e d d i n g so fa l g e b r a si n t os i m p l ea l g e b r a sa n dt w o - g e n e r a t e da l g e b r a s i n v e r s es e m i g r o u p sf o r mo n eo ft h ei m p o r t a n tc l a s s e so fs e m i g r o u p s i fo n et r e a t s t h e ma su n a r ys e m i g r o u p sw i t ht h ea d d i t i o n a lu n a r yo p e r a t i o n ，t a k i n gt h ei n v e r s ee l e m e n t ， t h e n ，a si sk n o w n ，t h ec l a s so fi n v e r s es e m i g r o u p si sav a r i e t y f r e ei n v e r s es e m i g r o u p sa r e t h ef r e ea l g e b r a so ft h i sv a r i e t y t h e r ea r es e v e r a lw o r k sd e v o t e dt od i f f e r e n tc o n s t r u c t i o n s d e s c r i b i n gf r e ei n v e r s es e m i g r o u p s ，s e eh e s c h e i b l i c h 4 5 ，4 6 ，w d m u n n 3 7 ，3 8 ，g b p r e s t o n 4 2 ja n db m s c h e i n 【4 7 ，s e ea l s oas u r v e y 4 4 】b yn r r e i l l ya n dab o o k 【4 0 】b ym p e t r i c h an e w c o n s t r u c t i o nf o rf r e ei n v e r s es e m i g r o u p sw a sf o u n dr e c e n t l yi n af u n d a m e n t a lp a p e rb yo p o l i a k o v aa n db m s c h e i n 【4 1 a sw a sn o t e di n 4 1 】，e a c h o ft h ec o n s t r u c t i o n sm e n t i o n e da b o v ec a nb ee a s i l yo b t m n e db yu s i n gt h ec o n s t r u c t i o no f p o h a k o v aa n ds c h e i n i nt h i st h e s i sw ef i n dg r s b n e 卜s h i r s h o vb a s e sf o rf r e ei n v e r s es e m i g r o u p su s i n gt h e c o n c e p to ft h ec a n o n i c a li d e m p o t e n t sf r o mt h ep a p e r 【4 1 a sar e s u l t ，w eo b t a i nt h e ( u n i q u ea n ds h o r t e s t ) n o r m a lf o r m so fe l e m e n t so ft h ef r e ei n v e r s es e m i g r o u pt o g e t h e r w i t ht h eg r s b n e r s h i r s h o va l g o r i t h mt ot r a n s f o r ma n yw o r dt oi t sn o r m a lf o r m t h e n o r m a lf o r m sc o n s i s t so fas e to fc a n o n i c a lw o r d si nt h es e n s eo f 【4 l 】，b u tc o n t r a r yt o c a n o n i c a lw o r d ，t h en o r m a lf o r mi su n i q u ef o rag i v e ne l e m e n to faf r e ei n v e r s es e m i g r o u p t h em a i np a r to ft h i st h e s i sw a sp u b l i s h e di ni n t e r n a t i o n a lj o u r n a lo fa l g e b r aa n d c o m p u t a t i o n ( v 0 1 1 9 ，n o 2 ( 2 0 0 9 ) 1 2 9 - 1 4 3 ) t i t l e db yg r s b n e r - s h i r s h o vb a s e s | o 甲扣e e i n v e r s es e m i 5 y r o u p s 2 c h a p t e r1 p r e l i m i n a r i e s i nt h i sc h a p t e r ，w ec i t es o m ec o n c e p t sa n dr e s u l t sf r o mt h el i t e r a t u r e 【4 8 ，6 ，7 】w h i c h a r er e l a t e dt ot h eg r s b n e r s h i r s h o vb a s e sf o ra s s o c i a t i v ea l g e b r a s l e tkb eaf i e l d ，k ( x ) t h ef r e ea s s o c i a t i v ea l g e b r ao v e r 尼g e n e r a t e db yxa n dx t h e f r e em o n o i dg e n e r a t e db yx ，w h e r et h ee m p t yw o r di st h ei d e n t i t yw h i c hi sd e n o t e db y1 f o raw o r dw x + ，w ed e n o t et h el e n g t h ( d e g r e e ) o fwb yi 叫1 l e tx b eaw e u - o r d e r e d s e ta n df 七( x ) t h e nb yfw ed e n o t et h em a x i m u mm o n o m i a li nf ，w h i c hi sa l s o c a l l e dt h el e a d i n gw o r do f f w ec a l lfm o n i ci ffh a sc o e f f i c i e n t1 aw e l lo r d e r i n g o i lx 4i sc a l l e dm o n o m i a li fi ti sc o m p a t i b l ew i t ht h em u l t i p l i c a t i o n o fw o r d s ，t h a ti s ，f o ru ， x ，w eh a v e 钍 v 兮w l u w 2 w l v w 2 ，f o ra l lw l ，w 2 x + as t a n d a r de x a m p l eo fm o n o m i a lo r d e r i n go nx 4i st h ed e g l e xo r d e r i n gt oc o m p a r et w o w o r d sf i r s tb yd e g r e ea n dt h e nl e x i c o g r a p h i c a l l y , w h e r exi saw e u - o r d e r e ds e t l e tfa n dgb et w om o n i cp o l y n o m i a l si nk ( x ) a n d i 加l ， t h e nt h ep o l y n o m i a l ( ，9 ) 锄= b a gi sc a u e dt h ei n t e r s e c t i o nc o m p o s i t i o no ffa n dg w i t hr e s p e c tt ow ( i i ) i fw = f = 口雪6f o rs o m ea ，b x + ，t h e nt h ep o l y n o m i a l ( ，9 ) 叫= f a g bi s c a l l e dt h ei n c l u s i o nc o m p o s i t i o no ffa n dgw i t hr e s p e c tt ow t h ew o r dwi sc a l l e dt h ea m b i g u i t yo ft h ec o m p o s i t i o n ( ，夕) 。 l e tscki x ) s u c ht h a te v e r ys si sm o n i c t h e nt h ec o m p o s i t i o n ( f ，夕) 伽i sc a l l e d t r i v i a lm o d u l o ( s ，w ) i f ( f ，9 ) 。= a i a i s i b i ，w h e r ee a c hq k ，a i ，玩x 。，8 i sa n d a i 百i b i w i ft h i si st h ec a s e t h e nw ew r i t e ( ，9 ) 伽三0m o d ( s ，叫) i ng e n e r a l ，f o rp ，q 七( x ) ，w ew r i t ep 兰q m o d ( s ，w ) w h i c hm e a n st h a tp q = e o q a i s i b i ，w h e r ee a c ho q k ，a i ，b i x 。，8 i sa n da i g i i b i w si sc a u e dag r 6 b n e 卜s h i r s h o vb a s i si nk ( x ) w i t hr e s p e c tt ot h em o n o m i a lo r d e r i n g i fa n yc o m p o s i t i o n ( f ，夕) 加o fp o l y n o m i a l si nsi st r i v i a lm o d u l o ( s ，叫) f o ras e ts 庇( x ) ，t h ei d e a lo fk ( x ) g e n e r a t e db ysi sd e n o t e db yi d ( s ) i fsi sa g r s b n e r - s h i r s h o vb a s i si nk ( x ) t h e ni ti sa l s oc a l l e dag r s b n e r s h i r s h o vb a s i sf o ri d ( s ) a n df o rt h ea l g e b r ak ( x ) l d ( s ) = k ( xs ) g e n e r a t e db yxw i t hd e f i n i n gr e l a t i o n ss 3 t h ef o l l o w i n gl e m m aw a sf i r s tp r o v e db ys h i r s h o v 4 s f o rf r e el i ea l g e b r a s ( w i t h d e g - l e xo r d e r i n g ) ( s e ea l s ob o k u t 【6 】) b o k u t 【7 s p e c i a l i z e dt h ea p p r o a c ho fs h i r s h o vt o a s s o c i a t i v ea l g e b r a s ( s e ea l s ob e r g m a n 3 】) f o rt h ec a s eo fc o m m u t a t i v ep o l y n o m i a l s ， t h i sl e m m ai sk n o w na st h eb u c h b e r g e r st h e o r e m 【2 1 l e m m a1 1 ( c o m p o s i t i o n - d i a m o n dl e m m a ) l e tsb eas u b s e to la 加ea l g e b r a k x ) o v e raf i e l dk ，a n d am o n o m i a lo r d e r i n go nx + t h e nt h ef o l l o w i n gs t a t e m e n t s a r ee q u i v a l e n t 俐si sag r s b n e r - s h i r s h o vb a s i s o ri d ( s ) w i t hr e s p e c tt o 陋) l i d ( s 、)兮，= o 动f o rs o m e8 sa n da ，b x + ( i i i ) i r r ( s ) = u x + l 钆o 吾6 ，s s ，a ，b x + ) i sak - b a s i so t h ea l g e b r ak 口 i fas u b s e tso fk ( x ) i sn o tag r s b n e r - s h i r s h o vb a s i sf o ri d ( s ) t h e no n e c a na d dt os an o n t r i v i a lc o m p o s i t i o n ( f ，夕) 伽o ff ，g sa n dc o n t i n u et h i sp r o c e s sr e p e a t e d l y ( a c t u a l l y u s i n gt h et r a n s f i n i t ei n d u c t i o n ) i no r d e rt oo b t a i na s e tro fg e n e r a t o r so fi d ( s ) s u c ht h a t a n yc o m p o s i t i o no fe l e m e n t so fr i st r i v i a lm o d u l ora n dt h ec o r r e s p o n d i n ga m b i g u i t y t h e nri sag r 6 b n e r - s h i r s h o vb a s i sf o rk x l s ) t h i sk i n do fp r o c e s si sc a l l e ds h i r s h o v a l g o r i t h m l e tg = s g p xs 、b eas e m i g r o u pp r e s e n t e db yg e n e r a t o r sxa n dd e f i n i n gr e l a t i o n s s = u i = v ii i ，) f o rs o m ei n d e xs e ti w ew i l li d e n t i f yas e m i g r o u pr e l a t i o nu = v ( 让，u x 4 ) w i t ht h ea l g e b r ar e l a t i o nu v = 0a n dw i t ht h ep o l y n o m i a l ( b i n o m i a l ) u 一口忍) t h e nt h es e m i g r o u pa l g e b r ak gh a st h ep r e s e n t a t i o n 克g = k b e c a u s ea n yc o m p o s i t i o no fb i n o m i a l si sa g a i nab i n o m i a l ，f r o mt h es h i r s h o va l g o r i t h m ， i tf o l l o w st h a tt h e r ee x i s t sag r s b n e r - s h i r s h o vb a s i srf o rk gc o n s i s t i n go fb i n o m i a l s s u c ht h a tg = s g p a l s o rd o e sn o td e p e n do nt h ef i e l d 七ri sa l s oc a l l e da g r s b n e r - s h i r s h o vb a s i sf o rt h es e m i g r o u pg a c t u a l l y ，w ed on o tn e e dt ou s es e m i g r o u pa l g e b r ak gt od e f i n eag r s b n e r - s h i r s h o v b a s i sf o ras e m i g r o u pg l e tu sr e f o r m u l a t ed e f i n i t i o no fag r s b n e r - s h i r s h o vb a s i sf o ra s e m i g r o u pa n dc o m p o s i t i o n d i a m o n dl e m m af o raf r e es e m i g r o u p l e t b eam o n o m i a lo r d e r i n go nx + ，s = ( u ，v ) l v u ) x x as e to f s e m i g r o u pr e l a t i o n s ，三m o d ( s ) t h ec o n g r u e n c er e l a t i o no nx + g e n e r a t e db ys ，a u bh a v b a n da v bh a u b ( ( u ，v ) s ，a ，b x + ) t h es e l e m e n t a r yt r a n s f o r m a t i o n so fx w o r d s t h e nu 三vm o d ( s ) i fa n do n l yi ft h e r ee x i s t sas e q u e n c eu = u 0h u 1h hu k 。v o fs - e l e m e n t a r yt r a n s f o r m a t i o n so fut o d e n o t esk m o d ( s ) = s g p t h es e m i g r o u p g e n e r a t e db yx w i t hd e f i n i n gr e l a t i o n ss 4 w ew i l lw r i t ei t 兰vr o o d ( s 叫) ，w x 。，i fu = u oh u 1 hu 南= vf o rs o m e s - e l e m e n t a r yt r a n s f o r m a t i o n sa n du t w ( 0 i 七) l e t ( u ，u ) ，( ? 2 t ，v 7 ) x 。x x 。w i t h 口 “， l w if o rs o m e a ，b ，w x + ，t h e n ( ( u ， ) ，( u ，t ，7 ) ) 叫= ( v b ，a v 7 ) i sc a u e dt h ei n t e r s e c t i o nc o m p o s i t i o no f ( u ，v ) a n d ( u 7 ，u 7 ) w i t hr e s p e c tt ow ( i i ) i fw = 让= a u 7 b f o rs o m ea ，b ，w x + ，t h e n ( ( 孔，口) ，( “7 ，秽7 ) ) t t ，= ( v ，a v 7 6 ) i sc a l l e d t h ei n c l u s i o nc o m p o s i t i o no f ( 让，v ) a n d ( u 7 ，口7 ) w i t hr e s p e c tt o a c o m p o s i t i o n0 ，q ) = ( u ，秒) ，( u p ，u 7 ) ) 。i sc a l l e dt r i v i a lm o d ( s ，硼) ，i f p 兰qm o d ( s ，叫) i ta g r e e sw i t ht h ea b o v ed e f i n i t i o no ft r i v i a l i t yo fac o m p o s i t i o nf o rp o l y n o m i a l s s x 4 x + i sc a l l e dag r s b n e r - s h i r s h o vb a s 拈i nx + r e l a t i v et om o n o m i a lo r d e r i n g i fa n y c o m p o s i t i o no fr e l a t i o n sf r o msi st r i v i a lm o d ( s ，加) i nt h i sc a s e ，w ea l s oc a l ls t ob eag r 5 b n e r - s h i r s h o vb a s i sf o rs e m i g r o u ps g p t h e nb yl e m m a1 1 w eh a v e l e m m a1 2 ( c o m p o s i t i o n - d i a m o n dl e m m af o rs e m i g r o u p s ) l e tx b eaf r e e m o n o i do ns e txw i t ham o n o m i a lo r d e r i n g ，s = ( u ，v ) l v u ) sx x + t h e nt h e f o l l o w i n gc o n d i t i o n sa r ee q u i v a l e n t 丘，si sag r 5 b n e r - s h i r s h o vb a s i s 如r 冼es e m i g r o u ps g p ( x l s ) r e l a t i v et o 5 i ) 巧p ，q x ，q pa n dp 兰qr o o d ( s ) ，t h e np = a u b ，w h e r ea ，b x ，( 乱，v ) s a n du uy o rs o m ew o r dv ( i i i ) i r r ( s ) = 妇x + i p a u b ，( u ，v ) s 扣r8 0 m ew o r d sv ，a ，b x ) i sas e to f n o r m a l1 0 1 m s1 0 i rs g p x l s 、 5 c h a p t e r2 o r d e r e dc a n o n i c a li d e m p o t e n t s i nt h i sc h a p t e r ，w ed e f i n ea n ds t u d yo r d e r e dc a n o n i c a li d e m p o t e n t si nf r e ei n v e r s e s e m i g r o u p s w er e c a l lt h a ta j li n v e r s es e m i g r o u pi sas e m i g r o u pi nw h i c he v e r ye l e m e n tah a s au n i q u e l yd e t e r m i n e da 一1s u c ht h a ta a - l a = aa n da - 1 a a 一1 = a 一1 t h ec a t e g o r yo f a l li n v e r s es e m i g r o u p s ( a c t u a l l y , i ti sav a r i e t yr e l a t i v et ot w oo p e r a t i o n so ba n da - 1 1 p o s s e s s e sf r e eo b j e c t s ，f r e ei n v e r s es e m i g r o u p s l e ty 2 ( x ) b eaf r e ei n v e r s es e m i g r o u p g e n e r a t e db yas e tx ，x 一1 = z 一1 l z x w i t hxnx 一1 = 乃d e n o t exux 一1b yy t h e n 珂( x ) h a st h ef o l l o w i n gs e m i g r o u pp r e s e n t a t i o n 刀( x ) = s g p ( y ia a a = 口，a a 一1 b b 一1 = b b 一1 a a ，口，b y + ) w h e r e1 1 = 1 ，( x - 1 ) 一1 = x ( z x ) a n d ( y l y 2 ) 一1 = 蛎1 盯