Hallord

Inom matematiken , inom områdena gruppteori och kombinatorik , ger Hall-ord en unik monoidfaktorisering av den fria monoiden . De är också helt ordnade och ger därmed en total beställning på monoiden. Detta är analogt med det mer kända fallet med Lyndon-ord ; i själva verket är Lyndon-orden ett specialfall, och nästan alla egenskaper som Lyndon-ord besitter överförs till Hall-ord. Hall-ord står i en-till-en-korrespondens med Hall-träd . Dessa är binära träd ; tillsammans bildar de Hall-setet . Denna uppsättning är en speciell helt ordnad delmängd av en fri icke-associativ algebra, det vill säga en fri magma . I denna form ger Hall-träden en grund för fria Lie-algebror och kan användas för att utföra de kommutationer som krävs av Poincaré-Birkhoff-Witt-satsen som används i konstruktionen av en universell omslutande algebra . Som sådan generaliserar detta samma process när den görs med Lyndon-orden. Hallträd kan också användas för att ge en total ordning till elementen i en grupp, via kommutatorinsamlingsprocessen , vilket är ett specialfall av den allmänna konstruktionen som anges nedan. Det kan visas att Lazard-uppsättningar sammanfaller med Hall-uppsättningar.

Den historiska utvecklingen går i omvänd ordning från ovanstående beskrivning. Kommutatorinsamlingsprocessen beskrevs först, 1934, av Philip Hall och utforskades 1937 av Wilhelm Magnus . Halluppsättningar introducerades av Marshall Hall baserat på arbete av Philip Hall på grupper. Därefter Wilhelm Magnus att de uppstår som den graderade Lie-algebra associerad med filtreringen på en fri grupp som ges av den lägre centrala serien . Denna korrespondens motiverades av kommutatoridentiteter i gruppteorin på grund av Philip Hall och Ernst Witt .

Hall set

Hall -uppsättningen är en helt ordnad delmängd av en fri icke-associativ algebra, det vill säga en fri magma . Låt $A={a_{1},\ldots ,a_{n}}$ vara en uppsättning generatorer, och låt $M(A)$ vara den fria magman över $A$ . Den fria magman är helt enkelt uppsättningen av icke-associativa strängar i bokstäverna i $A$ , med bibehållen parentes för att visa gruppering. Parentes kan skrivas med hakparenteser, så att delar av den fria magman kan ses som formella kommutatorer. På motsvarande sätt är den fria magman mängden av alla binära träd med löv markerade av element av $A$ .

Halluppsättningen $H\subseteq M(A)$ kan konstrueras rekursivt (i stigande ordning) enligt följande:

• Elementen i $A$ ges en godtycklig total ordning.
• Hall-setet innehåller generatorerna: $A\subseteq H.$
• En formell kommutator $[x,y]\in H$ om och endast om $x\in H$ och $y\in H$ och $x>y$ och:
  • Antingen $x\in A$ (och därmed $y\in A$ ),
  • Eller $x=[u,v]$ med $u\in H$ och $v\in H$ och $v\leq y$ .
• Kommutatorerna kan beställas godtyckligt, förutsatt att $y<[x,y]$ alltid gäller.

Konstruktionen och notationen som används nedan är nästan identiska med den som används i kommutatorinsamlingsprocessen och kan därför jämföras direkt; vikterna är stränglängderna. Skillnaden är att det inte krävs något omnämnande av grupper. Dessa definitioner sammanfaller alla med X. Viennots. Observera att vissa författare vänder om ordningen på ojämlikheten. Observera också att ett av tillstånden, $v\leq y$ , kan kännas "bakåt"; denna "efterblivenhet" är det som ger den fallande ordningen som krävs för faktorisering. Att vända ojämlikheten inte på denna "efterblivenhet".

Exempel

Betrakta generatorset med två element $\{a,b\}.$ Definiera $a>b$ och skriv $xy$ för $[x,y]$ för att förenkla notation , med endast parentes vid behov. De första medlemmarna i Hall-setet är sedan (i ordning)

${\begin{aligned}&b,a,\\&ab,\\&(ab)b,\;\;(ab )a,\\&((ab)b)b,\;\;((ab)b)a,\;\;((ab)a)a,\\&(((ab)b)b) b,\;(((ab)b)b)a,\;(((ab)b)a)a,\;(((ab)a)a)a,\;((ab)b)( ab),\;((ab)a)(ab),\\&\cdots \end{aligned}}$

Lägg märke till att det finns $2,1,2,3,6,\ldots$ element av varje distinkt längd. Detta är startsekvensen för halsbandspolynomet i två element (beskrivs härnäst nedan).

Kombinatorik

Ett grundläggande resultat är att antalet element med längden $k$ i Hall-uppsättningen (över $n$ generatorer) ges av halsbandspolynomet

$M_{n}(k)\ =\ {1 \över k}\summa _{d\,|\,k}\mu \!\left({k \ över d}\right)n^{d}={1 \over k}\summa _{d\,|\,k}\mu \!\left({d}\right)n^{k/d}$

där $\mu$ är den klassiska Möbius-funktionen . Summan är en Dirichlet-falsning .

Definitioner och lemman

Vissa grundläggande definitioner är användbara. Givet ett träd $t=[x,y]$ kallas elementet ${\displaystyle x} det$ omedelbara vänstra underträdet , och på samma sätt är ${\displaystyle y} det$ omedelbara högra underträd . Ett höger underträd är antingen $y$ själv, eller ett höger underträd av antingen $x$ eller $y$ . Detta är i motsats till det extrema högra underträdet , som antingen är $y$ själv, eller ett extremt högerunderträd av $y$ .

Ett grundläggande lemma är att om $v$ är ett höger underträd av ett Hall-träd $t=[x,y]$ , då $v\leq y.$

Hallord

Hall-ord erhålls från Hall-uppsättningen genom att "glömma" kommutatorparenteserna, men i övrigt behålla begreppet total ordning. Det visar sig att denna "glömma" är ofarlig, eftersom motsvarande Hall-träd kan härledas från ordet, och det är unikt. Det vill säga, Hall-orden står i en-till-en-korrespondens med Hall-träden. Den totala ordningen på Hall-träden går över till en total ordning på Hall-orden.

Denna överensstämmelse tillåter en monoid faktorisering : givet den fria monoiden $A^{*}$ , kan alla element i $A^{*}$ unikt faktoriseras till en stigande sekvens av Hall-ord. Detta är analogt med och generaliserar det mer kända fallet av faktorisering med Lyndon-ord som tillhandahålls av Chen-Fox-Lyndon-satsen .

Mer exakt kan varje ord $w\in A^{*}$ skrivas som en sammanlänkning av Hall-ord

$w=h_{1}h_{2}\cdots h_{k}$

med varje Hall-ord $h_{j}$ helt ordnat efter Hall-ordningen:

$h_{1}\leq h_{2}\leq \cdots \leq h_{k}.$

På detta sätt sträcker sig Hall-ordordningen till en total ordning på monoiden. De lemman och satser som krävs för att tillhandahålla korrespondensen från ord till träd, och den unika ordningen, skissas nedan.

Lövverk

Bladverket av en magma $M(A)$ är den kanoniska avbildningen $to A^{*}}$ \ från magman till den fria monoiden $A^{*}$ , given av $f:a\mapsto a$ för $a\in A$ och $f:[x,y]\mapsto f(x)f(y)$ annars. Bladverket är bara strängen som består av trädets löv, det vill säga tar trädet skrivet med kommutatorparenteser och raderar kommutatorparenteserna.

Faktorisering av Hall-ord

Låt $t=[x,y]\in H$ vara ett Hallträd, och $w=f([x, y])$ vara motsvarande Hall-ord. Givet all faktorisering av ett Hall-ord $w=uv$ till två icke-tomma strängar $u$ och $v$ , så finns det en faktorisering till Hall-träd så att $u=f(x_{1})\cdots f(x_{m})$ och $v=f(y_{1})\cdots f(y_{n})$ med

$x_{1},\ldots ,x_{m}>y_{1}$

och

$y_{1}\leq y_{2}\leq \cdots \leq y_{n}\leq y.$

Detta och den efterföljande utvecklingen nedan ges av Guy Melançon.

Korrespondens

Motsatsen till ovanstående faktorisering etablerar överensstämmelsen mellan Hall-ord och Hall-träd. Detta kan anges i följande intressanta form: om $t$ är ett Hall-träd, och motsvarande Hall-ord $f(t)$ faktoriseras som

$f(t)=f(t_{1})\cdots f(t_{n})$

med

$f(t_{1})\leq \cdots \leq f(t_{n})$

då $n=1$ . Med andra ord kan Hall-ord inte inkluderas i en fallande sekvens av andra Hall-ord. Detta innebär att, givet ett Hall-ord, kan motsvarande träd identifieras unikt.

Standardfaktorisering

Den totala ordern på Hallträd går över till Hallord. Sålunda, givet ett Hallord $w=f([x,y])$ , kan det faktoriseras som $w =f(x)f(y)$ med $f(x)>f(y)$ . Detta kallas standardfaktorisering .

Standardsekvens

En sekvens av hallord $(w_{1},w_{2},\ldots ,w_{n})$ sägs vara en standardsekvens om varje $w_{i}$ är antingen en bokstav eller en standardfaktorisering $w_{i}=u_{i}v_{i}$ med $v_{i}\leq w_{i+1},\cdots ,w_{n}.$ Observera att ökande sekvenser av Hall-ord är standard.

Termomskrivning

Den unika faktoriseringen av alla ord $w\in A^{*}$ till en sammanlänkning av en stigande sekvens av Hall-ord $w=h_{1} h_{2}\cdots h_{k}$ med $h_{1}\leq h_{2}\leq \cdots \leq h_{k}$ kan uppnås genom definiera och rekursivt tillämpa ett enkelt termomskrivningssystem . Det unika med faktoriseringen följer av systemets konfluensegenskaper . Omskrivningen utförs genom utbyte av vissa par av på varandra följande Hall-ord i en sekvens; den ges efter dessa definitioner.

En droppe i en sekvens $(h_{1},h_{2},\ldots ,h_{n})$ av Hall-ord är ett par $(h_{i},h_{i+1})$ så att $h_{i}>h_{i+1}.$ Om sekvensen är en standardsekvens, så kallas släppet som ett legalt släpp om man också har att $h_{i+1}\leq h_{i+2},\ldots ,h_{n}.$

Givet en standardsekvens med ett legalt fall, finns det två distinkta omskrivningsregler som skapar nya standardsekvenser. Man sammanfogar de två orden i droppen:

$(h_{1},h_{2},\ldots ,h_{n})\to (h_{1},h_{2},\ldots ,h_{i}h_{i+1},\ldots ,h_{n})$

medan den andra permuterar de två elementen i droppen:

$(h_ {1},h_{2},\ldots ,h_{n})\to (h_{1},h_{2},\ldots ,h_{i-1},h_{i+1},h_{i },h_{i+2},\ldots ,h_{n})$

Det är inte svårt att visa att båda omskrivningarna resulterar i en ny standardsekvens. I allmänhet är det mest bekvämt att applicera omskrivningen på den lagliga droppen längst till höger; det kan dock visas att omskrivningen är sammanflytande, och så får man samma resultat oavsett ordningsföljd.

Total beställning

En total ordning kan anges på orden $w\in A^{*}.$ Detta liknar den vanliga lexikografiska ordningen , men på nivån för Hall-ord. Med tanke på två ord $u,v$ räknas in i stigande Hallordordning , dvs.

$u=u_{1}u_{2}\cdots u_{m}\quad$ och $\quad v=v_{ 1}v_{2}\cdots v_{n}$

med varje $u_{i},v_{j}$ ett hallord, har man en ordning att $u<v$ om antingen

$m<n\quad$ och $\quad u_{1}=v_{1},\,u_ {2}=v_{2},\,\cdots ,u_{m}=v_{m}$

eller om

$u_{1}=v_{1},\,u_{2}=v_{2},\,\ldots ,u_ {k}=v_{k}\quad$ och $\quad u_{k+1}<v_{k+1}.$

Egenskaper

Hallord har ett antal märkliga egenskaper, många av dem nästan identiska med dem för Lyndon-ord . Den första och viktigaste egenskapen är att Lyndon-ord är ett specialfall av Hall-ord. Det vill säga, definitionen av ett Lyndon-ord uppfyller definitionen av Hall-ordet. Detta kan lätt verifieras genom direkt jämförelse; Observera att riktningen för ojämlikheten som används i definitionerna ovan är exakt den omvända till den som används i den vanliga definitionen för Lyndon-ord. Uppsättningen av Lyndon-träd (som följer av standardfaktoriseringen) är en Hall-uppsättning.

Andra fastigheter inkluderar:

• Hallord är acykliska , även kända som primitiva . Det vill säga de kan inte skrivas i formen $w=x^{n}$ för något ord $x\in A^{*}$ och ${\ displaystil n>1}$ .
• Ett ord $w\in A^{*}$ är ett hallord om och endast om för någon faktorisering av $w=uv$ till icke-tomma ord lyder $w>vu$ . I synnerhet innebär detta att inget Hall-ord är en konjugat av ett annat Hall-ord. Observera igen, detta är precis som det är för ett Lyndon-ord: Lyndon-ord är de minsta av sin konjugationsklass; Hallord är de största.
• Ett ord $w\in A^{*}$ är ett Hallord om och bara om det är större än någon av dess rätta faktorer. Detta följer av de två föregående punkterna.
• Varje primitivt ord $w\in A^{*}$ är konjugerat till ett Hall-ord. Det vill säga, det finns en cirkulär förskjutning av $w$ som är ett Hall-ord. På motsvarande sätt finns det en faktorisering $w=uv$ så att $vu$ är ett Hall-ord. Detta konjugat är unikt, eftersom inget Hall-ord är ett konjugat av ett annat Hall-ord.
• Varje ord $w\in A^{*}$ är konjugaten av en potens av ett unikt Hall-ord.

Implikationer

Det finns ett liknande termomskrivningssystem för Lyndon-ord , detta är hur faktoriseringen av en monoid uppnås med Lyndon-ord.

Eftersom Hall-orden kan placeras i Hall-träd, och varje Hall-träd kan tolkas som en kommutator, kan termen omskrivning användas för att utföra kommutatorinsamlingsprocessen på en grupp.

En annan mycket viktig tillämpning av omskrivningsregeln är att utföra de kommutationer som förekommer i Poincaré–Birkhoff–Witt-satsen . En detaljerad diskussion om kommuteringen ges i artikeln om universella enveloping algebror . Observera att termomskrivning med Lyndon-ord också kan användas för att erhålla den nödvändiga kommuteringen för PBW-satsen.

Historia

Halluppsättningar introducerades av Marshall Hall baserat på arbete av Philip Hall på grupper. Därefter Wilhelm Magnus att de uppstår som den graderade Lie-algebra associerad med filtrering på en fri grupp som ges av den lägre centrala serien . Denna korrespondens motiverades av kommutatoridentiteter i gruppteorin på grund av Philip Hall och Ernst Witt .

Se även

• Hall–Petresco identitet
• Markov vägmätare