Monomiell ordning

Inom matematiken är en monomordning (ibland kallad termordning eller en tillåten ordning ) en total ordning på mängden av alla ( moniska ) monomer i en given polynomring , som uppfyller egenskapen att respektera multiplikation, dvs.

Om $u\leq v$ och $w$ är någon annan monomial, då $uw\leq vw$ .

Monomialordningar används oftast med Gröbnerbaser och multivariat division . I synnerhet är egenskapen att vara en Gröbner-bas alltid relativ till en specifik monomordning.

Definition, detaljer och variationer

Förutom att respektera multiplikation krävs ofta att monomiala ordrar är välordnar , eftersom detta säkerställer att den multivariata divisionsproceduren kommer att avslutas. Det finns emellertid praktiska tillämpningar även för multiplikationsrespekterande ordningsrelationer på uppsättningen av monomialer som inte är välordningar.

I fallet med ändligt många variabler är välordning av en monomiell ordning ekvivalent med konjunktionen av följande två villkor:

Ordern är en total order .
Om u är någon monomial så är $1\leq u$ .

Eftersom dessa villkor kan vara lättare att verifiera för en monomordning definierad genom en explicit regel, än att direkt bevisa att det är en välordning, föredras de ibland i definitioner av monomordning.

Ledande monomialer, termer och koefficienter

Valet av en total ordning på monomialerna tillåter sortering av termerna för ett polynom. Den ledande termen för ett polynom är alltså termen för den största monomialen (för den valda monomialordningen).

Konkret, låt $R$ vara vilken ring som helst av polynom. Då är mängden $M$ för de (moniska) monomierna i $R$ en bas för $R$ , betraktad som ett vektorrum över koefficienternas fält . Således har vilket polynom som helst som inte är noll $i$ R $ett$ unikt uttryck $p=\textstyle \sum _{u\in S}c_{u}u$ som en linjär kombination av monomer, där $S$ är en finit delmängd av $M$ och $c u$ är alla icke-noll. När en monomordning har valts är den ledande monomialen den största $u$ i $S$ , den ledande koefficienten är motsvarande $c u$ , och den ledande termen är motsvarande $c u u$ . Huvudmonomial /koefficient/term används ibland som en synonym för "ledande". Vissa författare använder "monomial" istället för "term" och "power product" istället för "monomial". I denna artikel antas ett monomial inte innehålla en koefficient.

Den definierande egenskapen för monomordningar innebär att termernas ordning bibehålls när ett polynom multipliceras med ett monom. Dessutom är den ledande termen för en produkt av polynom produkten av de ledande termerna av faktorerna.

Exempel

På uppsättningen ${\displaystyle \left\{x^{n}\mid n\in \mathbb {N} \right\}} potenser$ av en variabel x , de enda monomiala ordningsföljderna är den naturliga ordningen 1 < x < x ² < x ³ < ... och dess motsats, varav den senare inte är en välordning. Därför blir begreppet monomiell ordning intressant endast i fallet med flera variabler.

Den monomiala ordningen innebär en ordning på de obestämda individerna. Man kan förenkla klassificeringen av monomordningar genom att anta att de obestämda benämns x ₁ , x ₂ , x ₃ , ... i fallande ordning för den monomiala ordningen som betraktas, så att alltid x ₁ > x ₂ > x ₃ > ... . (Om det skulle finnas oändligt många obestämda, är denna konvention oförenlig med villkoret att vara en brunnsordning, och man skulle tvingas använda den motsatta ordningen, men fallet med polynom i oändligt många variabler beaktas sällan.) I exemplet nedan använder vi x , y och z istället för x ₁ , x ₂ och x ₃ . Med denna konvention finns det fortfarande många exempel på olika monomiala ordningar.

Lexikografisk ordning

Lexikografisk ordning (lex) jämför först exponenter för x ₁ i monomialerna, och i fall av likhet jämför exponenter för x ₂ och så vidare. Namnet härrör från likheten med den vanliga alfabetiska ordningen som används i lexikografi för ordböcker, om monomialer representeras av sekvensen av exponenterna för de obestämda. Om antalet obestämda är fast (som det vanligtvis är fallet), är den lexikografiska ordningen en välordning , även om detta inte är fallet för den lexikografiska ordningen tillämpad på sekvenser av olika längd (se Lexikografisk ordning § Ordning av sekvenser av olika längder ). För Gröbners basisberäkningar tenderar denna beställning att vara den mest kostsamma; sålunda bör det undvikas, så långt det är möjligt, förutom för mycket enkla beräkningar.

Graderad lexikografisk ordning

Graderad lexikografisk ordning (grlex, eller delex för grad lexikografisk ordning ) jämför först den totala graden (summan av alla exponenter), och i händelse av oavgjort tillämpas lexikografisk ordning. Denna ordning är inte bara en brunnsordning, den har också egenskapen att varje monomial endast föregås av ett ändligt antal andra monomer; detta är inte fallet för lexikografisk ordning, där alla (oändligt många) potenser av x är mindre än y (den lexikografiska ordningen är ändå en brunnsordning är relaterad till omöjligheten att konstruera en oändligt minskande kedja av monomialer). Även om det är mycket naturligt, används denna ordning sällan: Gröbner-basen för den graderade omvända lexikografiska ordningen, som följer, är lättare att beräkna och ger samma information om den ingående uppsättningen av polynom.

Graderad omvänd lexikografisk ordning

Graderad omvänd lexikografisk ordning (grevlex, eller degrevlex för grad omvänd lexikografisk ordning ) jämför den totala graden först och använder sedan en omvänd lexikografisk ordning som tie-breaker, men den omvänder resultatet av den lexikografiska jämförelsen så att lexikografiskt större monomialer av samma grad anses vara degrevlex mindre. För att den slutliga ordningen ska visa den konventionella ordningen x ₁ > x ₂ > … > x _n av de obestämda, är det dessutom nödvändigt att den tie-breaker lexikografiska ordningen före omkastning anser att den sista obestämda x _n är den största, vilket betyder att den måste börja med det obestämda. Ett konkret recept för den graderade omvända lexikografiska ordningen är alltså att jämföra med totalgraden först, sedan jämföra exponenter för det sista obestämda x _n men vända utfallet (så monomialen med mindre exponent är större i ordningen), följt (som alltid) endast vid oavgjort) genom en liknande jämförelse av x _{n −1} , och så vidare som slutar med x ₁ .

Skillnaderna mellan graderade lexikografiska och graderade omvända lexikografiska ordningar är subtila, eftersom de faktiskt sammanfaller för 1 och 2 obestämda. Den första skillnaden kommer för grad 2 monomial i 3 obestämda, som är graderade lexikografiska ordnade som $x_{1 }^{2}>x_{1}x_{2}>x_{1}x_{3}>x_{2}^{2}>x_{2}x_{3}>x_{3}^{2}$ men graderad omvänd lexikografi ordnad som $x_{1}^{2}>x_{1}x_ {2}>x_{2}^{2}>x_{1}x_{3}>x_{2}x_{3}>x_{3}^{2}$ . Den allmänna trenden är att den omvända ordningen uppvisar alla variabler bland de små monomierna av någon given grad, medan med den icke-omvända ordningen kommer intervallen för de minsta monomierna av någon given grad endast att bildas från de minsta variablerna.

Elimineringsorder

Blockordning eller elimineringsordning (lexdeg) kan definieras för vilket antal block som helst, men för enkelhetens skull betraktar vi endast fallet med två block (om antalet block är lika med antalet variabler, är denna ordning helt enkelt lexikografisk ordning). För denna ordning är variablerna uppdelade i två block x ₁ ,..., x _h och y ₁ ,..., y _k och en monomordning väljs för varje block, vanligtvis den graderade omvända lexikografiska ordningen. Två monomialer jämförs genom att jämföra deras x -del, och i händelse av oavgjort, genom att jämföra deras y- del. Denna ordning är viktig eftersom den tillåter eliminering , en operation som motsvarar projektion i algebraisk geometri.

Viktordning

Viktordningen beror på en vektor $(a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^ {n}$ kallas viktvektorn. Den jämför först prickprodukten av exponentsekvenserna för monomialerna med denna viktvektor, och i händelse av oavgjort använder den någon annan fast monomial ordning. Till exempel är de graderade orderna ovan viktordrar för viktvektorn "totalgrad" (1,1,...,1). Om a i _är rationellt oberoende tal (så i synnerhet inget av dem är noll och alla bråk ${\tfrac {a_{i}}{a_{j}}}$ är irrationella) så är oavgjort kan aldrig inträffa, och viktvektorn själv specificerar en monomiell ordning. I det motsatta fallet skulle man kunna använda en annan viktvektor för att bryta band, och så vidare; efter att ha använt n linjärt oberoende viktvektorer kan det inte finnas några kvarvarande kopplingar. Man kan faktiskt definiera vilken monomiell ordning som helst genom en sekvens av viktvektorer ( Cox et al. s. 72–73), till exempel (1,0,0,...,0), (0,1,0,). ..,0), ... (0,0,...,1) för lex, eller (1,1,1,...,1), (1,1,..., 1,0 ), ... (1,0,...,0) för grevlex.

Betrakta till exempel monomialerna $xy^{2}z$ , $z^{2}$ , $x^{3}$ och $x^{2}z^{2}$ ; Monomialordningarna ovan skulle beställa dessa fyra monomialer enligt följande:

Lex: $x^{3}>x^{2}z^{2}>xy^{2}z>z^{2}$ (kraften av $x$ dominerar).
Grlex: $x^{2}z^{2}>xy^{2}z>x^{3}>z^{2}$ (total grad dominerar; högre effekt av $x$ bröt oavgjort bland de två första).
Grevlex: $xy^{2}z>x^{2}z^{2}>x^{3}>z^{2}$ (total grad dominerar; lägre kraft av $z$ bröt oavgjort bland de två första).
En viktordning med viktvektor (1,2,4): $x^{2}z^{2}>xy^{2}z> z^{2}>x^{3}$ (prickprodukterna 10>9>8>3 lämnar inga band att bryta här).

Besläktade föreställningar

En elimineringsorder garanterar att en monomial som involverar någon av en uppsättning obestämda ämnen alltid kommer att vara större än en monomial som inte involverar någon av dem.
En produktorder är det enklare exemplet på en elimineringsorder. Den består i att kombinera monomiala ordningar på osammanhängande uppsättningar av obestämda till en monomordning på deras förening. Den jämför helt enkelt exponenterna för de obestämda i den första uppsättningen med den första monomiska ordningen, och bryter sedan banden med den andra monomala ordningen på de obestämda i den andra uppsättningen. Denna metod generaliserar uppenbarligen till varje osammanhängande förening av uppsättningar av obestämda; den lexikografiska ordningen kan erhållas på så sätt från singletonmängderna { x ₁ }, { x ₂ }, { x ₃ }, ... (med den unika monomiala ordningen för varje singelton).

När man använder monomiala beställningar för att beräkna Gröbner-baser kan olika ordningsföljder leda till olika resultat, och beräkningens svårighetsgrad kan variera dramatiskt. Till exempel har graderad omvänd lexikografisk ordning ett rykte om sig att producera, nästan alltid, de Gröbnerbaser som är lättast att beräkna (detta upprätthålls av det faktum att, under ganska vanliga förhållanden på idealet, har polynomen i Gröbnerbasen en grad som är högst exponentiell i antalet variabler; inget sådant komplexitetsresultat finns för någon annan ordning). Å andra sidan krävs elimineringsorder för eliminering och relativa problem.

David Cox; John Little; Donal O'Shea (2007). Idealer, varianter och algoritmer: en introduktion till beräknings-algebraisk geometri och kommutativ algebra . Springer. ISBN 978-0-387-35650-1 .