Bergmans diamantlemma

Inom matematiken , specifikt fältet abstrakt algebra, är Bergmans diamantlemma (efter George Bergman ) en metod för att bekräfta huruvida en given uppsättning monomialer av en algebra bildar en $k$ -bas. Det är en förlängning av Gröbner-baser till icke-kommutativa ringar . Beviset för lemma ger upphov till en algoritm för att erhålla en icke-kommutativ Gröbner-bas för algebra från dess definierande relationer. Men i motsats till Buchbergers algoritm , i det icke-kommutativa fallet, kan denna algoritm inte avslutas.

Förberedelser

Låt $k$ vara en kommutativ associativ ring med identitetselement 1, vanligtvis ett fält . Ta en godtycklig uppsättning $X$ av variabler. I det finita fallet har man vanligtvis $X=\{x_{1},x_{2},x_{3},\dots ,x_ {n}\}$ . Då $\langle X\rangle$ den fria semigruppen med identitet 1 på $X$ . Slutligen, $k\langle X\rangle$ är den fria associativa $k$ - algebra över $X$ . Element av $\langle X\rangle$ kommer att kallas ord , eftersom element i $X$ kan ses som bokstäver.

Monomial ordning

Reduktionerna nedan kräver ett val av ordning $<$ på orden dvs monomialer av $\langle X\rangle$ . Detta måste vara en total beställning och uppfylla följande:

För alla ord $u,u',v$ och $w$ , har vi att om $w<v$ då $uwu'<uvu'$ .
För varje ord ${\displaystyle w} är$ samlingen $\{v\in \langle X\rangle :v<w\}$ ändlig.

Vi kallar en sådan order tillåtlig . Ett viktigt exempel är gradens lexikografiska ordning , där $w<v$ om $w$ har mindre grad än $v$ ; eller i det fall de har samma grad, säger vi $w<v$ om $w$ kommer tidigare i den lexikografiska ordningen än $v$ . Till exempel ges graden lexikografisk ordning på monomialer av $k\langle x,y\rangle$ genom att först anta $x<y$ . Då innebär ovanstående regel att monomialerna är ordnade på följande sätt:

$1<x<y<x^{2}<xy<yx<y^{2} <x^{3}<x^{2}y<\dots$

Varje element $h\in k\langle X\rangle$ har ett inledande ord som är det största ordet under ordningen $<$ som visas i $h$ med icke -nollkoefficient. I $k\langle x,y\rangle$ om $h=x^{2}+2x^{2}yy ^{2}x$ , då är det inledande ordet i $h$ i lexikografisk ordning $y^{2}x$ .

Minskning

Antag att vi har en mängd $\{g_{\sigma }\}_{\sigma \in S}\subseteq k\langle X\rangle$ som genererar en 2 -sided ideal $I$ av $k\langle X\rangle$ . Sedan kan vi skala varje $g_{\sigma }$ så att dess inledande ord $w_{\sigma }$ har koefficient 1. Således kan vi skriva ${\ displaystyle g_{\sigma }=w_{\sigma }-f_{\sigma }} ,$ där $f_{\sigma }$ är en linjär kombination av ord $v$ så att $v<w_{\sigma }$ . Ett ord $w$ kallas reducerat med avseende på relationerna $\{g_{\sigma }\}_{\sigma \in S}$ om det inte innehåller någon av de inledande orden $w_{\sigma }$ . Annars, $w=uw_{\sigma }v$ för vissa $u,v\in \langle X\rangle$ och vissa ${\ displaystyle \sigma \in S}$ . Sedan finns det en reduktion ${\displaystyle r_{u\sigma v}:k\langle X\rangle \to k\langle X\rangle } ,$ vilket är en endomorfism av $k\langle X\rangle$ som fixar alla element i $\langle X\rangle$ förutom $w=uw_{\sigma } v$ och skickar detta till $uf_{\sigma }v$ . Genom valet av ordning finns det bara ändligt många ord mindre än ett givet ord, därför kommer en finit sammansättning av reduktioner att skicka alla $h\in k\langle X\rangle$ till en linjär kombination av reducerade ord.

Alla element delar en ekvivalensklass modulo $I$ med sin reducerade form. Således bildar de kanoniska bilderna av de reducerade orden i $k\langle X\rangle /I$ en $k$ -spannmängd. Idén med icke-kommutativa Gröbnerbaser är att hitta en uppsättning generatorer $g_{\sigma }$ av den ideala $I$ så att bilderna av de motsvarande reducerade orden i $k\langle X\rangle /I$ är en $k$ -bas. Bergmans diamantlemma låter oss verifiera om en uppsättning generatorer $g_{\sigma }$ har denna egenskap. Dessutom, i fallet där den inte har denna egenskap, leder beviset för Bergmans Diamond Lemma till en algoritm för att utöka uppsättningen generatorer till en som har det.

Ett element $h\in k\langle X\rangle$ kallas reduktionsunik om de ges två finita sammansättningar av reduktioner $s_{1}$ och $s_ {2}$ så att bilderna $s_{1}(h)$ och $s_{2}(h)$ är linjära kombinationer av reducerade ord, sedan $s_{1}(h)=s_{2}(h)$ . Med andra ord, om vi tillämpar reduktioner för att omvandla ett element till en linjär kombination av reducerade ord på två olika sätt, får vi samma resultat.

Reduktionsserien leder till ett gemensamt uttryck. Diamantformen ger upphov till namnet.

Otydligheter

När man utför reduktioner kanske det inte alltid finns ett självklart val för vilken minskning man ska göra. Detta kallas en tvetydighet och det finns två typer som kan uppstå. Anta först att vi har ett ord $w=tvu$ för vissa icke-tomma ord $t,v,u$ och antag att $w_{\sigma }=tv$ och $w_{\tau }=vu$ är inledande ord för vissa $\sigma ,\tau \in S$ . Detta kallas en överlappningsambiguity , eftersom det finns två möjliga reduktioner, nämligen $r_{1\sigma u}$ och $r_{t\tau 1}$ . Denna tvetydighet går att lösa om $tr_{1\sigma u}$ och $r_{t\tau 1}u$ kan reduceras till ett vanligt uttryck med hjälp av sammansättningar av reduktioner .

För det andra kan ett inledande ord finnas i ett annat, dvs. $w_{\sigma }=t\omega _{\tau }u$ för vissa ord $t,u$ och några index $\sigma ,\tau \in S$ . Då har vi en inklusionstvetydighet . Återigen är denna tvetydighet lösbar om $s_{1}\circ r_{1\sigma 1}(w)=s_{ 2}\circ r_{t\tau u}(w)$ , för vissa kompositioner av reduktioner $s_{1}$ och $s_{2}$ .

Uttalande av Lemma

Uttalandet av lemma är enkelt men involverar den terminologi som definierats ovan. Detta lemma är tillämpligt så länge som den underliggande ringen är associativ .

Låt ${\displaystyle \{g_{\sigma }\}_{\sigma \in S}\subseteq k\langle X\rangle } generera$ en ideal $I$ av $k\langle X\rangle$ , där $g_{\sigma }=w_{\sigma }-f_{\sigma }$ med $w_{\sigma }$ de inledande orden under någon fast tillåten ordning av $\langle X\rangle$ . Då är följande likvärdiga:

Alla överlappande och inkluderande tvetydigheter bland $g_{\sigma }$ är lösbara.
Alla element i $k\langle X\rangle$ är reduktionsunika.
Bilderna av de reducerade orden i $k\langle X\rangle /I$ bildar en $k$ -bas.

Här görs reduktionerna med avseende på den fasta uppsättningen generatorer $\{g_{\sigma }\}_{\sigma \in S}$ av $I$ . När något av ovanstående gäller säger vi att $\{g_{\sigma }\}_{\sigma \in S}$ är en Gröbner-bas för $I$ . Givet en uppsättning generatorer, kontrollerar man vanligtvis det första eller andra villkoret för att bekräfta att uppsättningen är en $k$ -basis.

Exempel

Att lösa oklarheter

Ta ${\displaystyle A=k\langle x,y,z\rangle / (yx-pxy,zx-qxz,zy-ryz)} ,$ som är kvantpolynomringen i 3 variabler, och antag $x<y<z$ . Ta $<$ för att vara gradens lexikografisk ordning, då är de inledande orden i de definierande relationerna ${\displaystyle yx} ,$ z $\displaystyle zx}$ och $zy$ . Det finns exakt en överlappande tvetydighet som är $zyx$ och inga inkluderande tvetydigheter. Man kan lösa via $yx=pxy$ eller via $zy=ryz$ först. Det första alternativet ger oss följande kedja av reduktioner,

$zyx=pzxy=pqxzy=pqrxyz,$

medan den andra möjligheten ger,

$zyx=ryzx=rqyxz=rqpxyz.$

Eftersom $p,q,r$ är kommutativa är ovanstående lika. Således försvinner tvetydigheten och Lemma antyder att $\{yx-pxy,zx-qxz,zy-ryz\$ är en Gröbner-bas av $I$ .

Icke-lösande oklarheter

Låt $A=k\langle x,y,z\rangle / (z^{2}-xy-yx,zx-xz,zy-yz)$ . Under samma ordning som i det föregående exemplet är de inledande orden för generatorerna av idealet ${\displaystyle z^{2}} ,$ z $\displaystyle zx}$ och $zy$ . Det finns två överlappande tvetydigheter, nämligen $z^{2}x$ och $z^{2}y$ . Låt oss betrakta $z^{2}x$ . Om vi löser $z^{2}$ först får vi,

$z^{2}x=(xy+yx)x=xyx+yx^{2},$

som inte innehåller några inledande ord och därför reduceras. Att lösa $zx$ först får vi,

$z^{2}x=zxz=xz^{2}=x(xy+yx)=x^{2}y+xyx.$

Eftersom båda ovanstående är reducerade men inte lika, ser vi att tvetydigheten inte löser sig. Därför $\{z^{2}-xy-yx,zx-xz,zy-yz\$ inte en Gröbner grund för det ideal den genererar.

Algoritm

Följande korta algoritm följer av beviset på Bergmans Diamantlemma. Den bygger på att lägga till nya relationer som löser tidigare olösliga oklarheter. Antag att $w=w_{\sigma }u=tw_{\tau }$ är en överlappande tvetydighet som inte löser sig. Sedan, för vissa sammansättningar av reduktioner $s_{1}$ och $s_{2}$ , har vi att $h_{ 1}=s_{1}\circ r_{1\sigma u}(w)$ och $h_{2}=s_{2}\circ r_{ t\tau 1}(w)$ är distinkta linjära kombinationer av reducerade ord. Därför får vi en ny relation som inte är noll $h_{1}-h_{2}\in I$ . Ledordet i denna relation är nödvändigtvis annorlunda än de ledande orden i existerande relationer. Skala nu denna relation med en konstant som inte är noll så att dess inledande ord har koefficienten 1 och lägg till den till genereringsmängden $I$ . Processen är analog för inklusionstvetydigheter.

Nu löses den tidigare olösliga överlappningstvetydigheten genom konstruktion av den nya relationen. Nya oklarheter kan dock uppstå. Denna process kan avslutas efter ett ändligt antal iterationer som producerar en Gröbner-bas för idealet eller aldrig avslutas. Den oändliga uppsättningen av relationer som produceras i fallet där algoritmen aldrig avslutas är fortfarande en Gröbner-bas, men den kanske inte är användbar om inte ett mönster i de nya relationerna kan hittas.

Exempel

Låt oss fortsätta med exemplet från ovan där $A=k\langle x,y,z\rangle /(z^{2}-xy-yx,zx-xz,zy-yz)$ . Vi fann att överlappningsambiguiteten $z^{2}x$ inte löser sig. Detta ger oss $h_{1}=xyx+yx^{2}$ och $h_{2}=x^ {2}y+xyx$ . Den nya relationen är därför $h_{1}-h_{2}=yx^{2}-x^{2}y\in I$ vars inledande ord är $yx^{2}$ med koefficient 1. Därför behöver vi inte skala det och kan lägga till det till vår uppsättning relationer som nu är $\{z^{2}-xy-yx,zx-xz,zy-yz,yx^{2}-x^ {2}y\}$ . Den tidigare tvetydigheten löser sig nu till antingen $h_{1}$ eller $h_{2}$ . Att lägga till den nya relationen lade inte till några tvetydigheter så vi har kvar den överlappande tvetydigheten ${\displaystyle z^{2}y} som$ vi identifierade ovan. Låt oss försöka lösa det med de relationer vi har för närvarande. Återigen, genom att lösa $z^{2}$ först får vi,

$z^{2}y=(xy+yx)y=xy^{2}+yxy.$

Å andra sidan löser vi $zy$ två gånger först och sedan $z^{2}$ finner vi,

$z^{2}y=zyz=yz^{2}=y(xy+yx)=yxy+y^{2}x.$

Vi har alltså $h_{3}=xy^{2}+yxy$ och $h_{4}=yxy+ y^{2}x$ och den nya relationen är $h_{3}-h_{4}=xy^{2}-y^{2}x$ med inledande ord $y^{2}x$ . Eftersom koefficienten för det inledande ordet är -1 skalar vi relationen och adderar sedan $y^{2}x-xy^{2}$ till uppsättningen av definierande relationer. Nu löser sig alla oklarheter och Bergmans Diamantlemma antyder det

$\{z^{2}-xy -yx,zx-xz,zy-yz,yx^{2}-x^{2}y,y^{2}x-xy^{2}\}$ är en Gröbner-bas för det ideal som den definierar.

Ytterligare generaliseringar

Vikten av diamantlemma kan ses av hur många andra matematiska strukturer det har anpassats för:

Lemmat har använts för att bevisa Poincaré-Birkhoff-Witt-satsen .

^ ^a ^b ^c ^d ^e ^f ^g ^h Rogalski, D. (2014-03-12). "En introduktion till icke-kommutativ projektiv geometri". arXiv :1403.3065 [math.RA].
^ ^a ^b ^c ^d Bergman, George (1978-02-01). "Diamantlemma för ringteori" . Framsteg i matematik . 29 (2): 178–218. doi : 10.1016/0001-8708(78)90010-5 . ISSN 0001-8708 .
^ Dotsenko, Vladimir; Tamaroff, Pedro (2020-10-28). "Tangentkomplex och diamantlemma". arXiv : 2010.14792 [ math.RA ].
^ ^a ^b Lopatkin, Viktor (2021-10-12). "Garside Theory: a Composition--Diamond Lemma Point of View". arXiv : 2109.07595 [ math.RA ].
^ Reyes, A., Suárez, H. (2016-12-01) "Baser för kvantalgebras och skeva Poincare-Birkhoff-Witt-förlängningar". MOMENTO No 54. ISSN 0121-4470
^ ^a ^b Hellström, L (2002-10-22) " The Diamond Lemma for Power Series Algebras" . Print & Media, Umeå universitet, Umeå. ISBN 91-7305-327-9
^ Li, Huishi (2009-06-23). "Algebras definierade av Monic Gr\"obner Baser över ringar". arXiv : 0906.4396 [ math.RA ].
^ Elias, Ben (2019-07-24). "Ett diamantlemma för algebror av Hecke-typ". arXiv : 1907.10571 [ math.RT ].
^ Bokut, LA; Chen, Yuqun; Li, Yu (2011-01-07). "Gr\"obner-Shirshov baser för kategorier". arXiv : 1101.1563 [ math.RA ].
^ Dotsenko, Vladimir; Khoroshkin, Anton (2010-06-01). "Gröbnerbaser för operader" . Duke Mathematical Journal . 153 (2): 363–396. arXiv : 0812.4069 . doi : 10.1215/00127094-2010-026 . ISSN 0012-7094 . S2CID 12243016 .

[:0-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h Rogalski, D. (2014-03-12). "En introduktion till icke-kommutativ projektiv geometri". arXiv :1403.3065 [math.RA].

[:1-2] Bergman, George (1978-02-01). "Diamantlemma för ringteori" . Framsteg i matematik . 29 (2): 178–218. doi : 10.1016/0001-8708(78)90010-5 . ISSN 0001-8708 .

[3] Dotsenko, Vladimir; Tamaroff, Pedro (2020-10-28). "Tangentkomplex och diamantlemma". arXiv : 2010.14792 [ math.RA ].

[:3-4] Lopatkin, Viktor (2021-10-12). "Garside Theory: a Composition--Diamond Lemma Point of View". arXiv : 2109.07595 [ math.RA ].

[5] Reyes, A., Suárez, H. (2016-12-01) "Baser för kvantalgebras och skeva Poincare-Birkhoff-Witt-förlängningar". MOMENTO No 54. ISSN 0121-4470

[:2-6] Hellström, L (2002-10-22) " The Diamond Lemma for Power Series Algebras" . Print & Media, Umeå universitet, Umeå. ISBN 91-7305-327-9

[7] Li, Huishi (2009-06-23). "Algebras definierade av Monic Gr\"obner Baser över ringar". arXiv : 0906.4396 [ math.RA ].

[8] Elias, Ben (2019-07-24). "Ett diamantlemma för algebror av Hecke-typ". arXiv : 1907.10571 [ math.RT ].

[9] Bokut, LA; Chen, Yuqun; Li, Yu (2011-01-07). "Gr\"obner-Shirshov baser för kategorier". arXiv : 1101.1563 [ math.RA ].

[10] Dotsenko, Vladimir; Khoroshkin, Anton (2010-06-01). "Gröbnerbaser för operader" . Duke Mathematical Journal . 153 (2): 363–396. arXiv : 0812.4069 . doi : 10.1215/00127094-2010-026 . ISSN 0012-7094 . S2CID 12243016 .