Gröbnerbas

Gröbnerbaser är ett verktyg för att lösa icke linjära ekvationssystem bestående av polynom. Det kan ses som en generalisering av en polynomring över en kropp K[x₁, ..,x_n].

Att räkna med gröbnerbaser kan ses som att göra gausselimination eller att hitta minsta gemensamma delaren på hos två polynom som inte är linjära

Begreppet Gröbnerbas introducerades 1965 av matematikern Bruno Buchberger i hans doktoravhandling där han använde dem för att bevisa sin tes. Buchberger döpte baserna efter sin rådgivare Wolfgang Gröbner.

Bakgrund

Gröbnerbaser är först och främst definierat för en ideella (icke tomma) polynomringar R=K[x₁, ..,x_n] över en kropp K. För alla former av kroppen K gäller teorin bakom gröbnerbaser men oftast så kroppar bestående av antingen rationella nummer eller integraler.

En polynom ring i en variabel kan ses som en summa av polynom $p=c_{n}x^{n}+c_{n-1}x^{n-1}+...+c_{2}x^{2}+c_{1}x+c_{0}=\sum _{k=0}^{n}c_{k}x^{k}$ där $c$ är ett element skilt från noll och n är ett heltal. Polynomringar är även definierade i flera variabler men eftersom notationen är omständlig så tänker jag lämna att förklara det.

Vid användning av gröbnerbaser så bör den bas för de polynom man använder vara i skrivna i linjär ordning (dvs en mängd där elementen är ordnade i stigande ordning) . Den bas som det är skrivna i brukar betecknas som monom, där en monom är den enklaste formen av ett polynom. Det kan innefatta en variabel eller fler variabler med både exponenter och konstanter framför sig.

Ett till viktigt begrepp kopplat till gröbnerbaser är division med flera variabler också kallat reduktion. När man pratar om division med flera variabler så använder du termen ledande monom, det vill säga det monomet i polynmet som har högst gradtal. Till exempel så lm(x^3+y)=x^3.

Om man har två polynom f och g så säger man att reducerbart om något monom m i f är en multipel av det ledande monomet i g, m=lm(g).

Definition

Låt gröbnerbasen G tillhör den ideal (ideal betyder att de additativa lagarna multiativa lagarna gäller, dvs om x,y tillhör I och a,b är reella tal så tillhör ax+by också I) delmängd I tillpo lynom ringen R i en kropp. G är då en gröbner bas om kroppen R har dessa egenskaper.

• De ideala som ges av polynomen som är bas för I kan beskrivas som bas för G • Polynomen i I är delbar med något av de polynom som är bas för G • Division av flera variabler av något polynom i polynom ringen R med G ger en unik rest • Division av flera variabler med något polynom i I med G ger resten 0

Sedan tänkte jag också beskriva definitionen på ett mer matematiskt sätt vilket beskriv i boken ”An Intuduction to Gröbner Bases” av Ralf Fröberg.

Sats

Låt f[g₁, ..,g_s]] tillhöra K [x₁, ..,x_n]] sen låter du resten du får om du dividerar f med G då, G=[g₁, ..,g_s] om resten då blir noll kommer f tillhöra G.

Vi vill sedan hitta ett G'=[g₁, ..,g_s] för a= [g₁, ..,g_s] så att divisionen mellan f₁ och f₂ med G' är lika så länge f₁ och f₂ tillhör a.

Definition

Låt a vara en ideal i mängden K[x₁, ..,x_n]]. Då kallas ett visst [g₁, ..,g_s] element i a med egenskapen att oavsett vilket element ut kroppen k dividerat med dessa uppsättningar med g är identiska för en gröbner bas till a.

Sats

Om [g₁, ..,g_s] är en gröbnerbas till a spänner [g₁, ..,g_s] upp hela a.

Bevis

Man kan se att [g₁, ..,g_s] tillhör a eftersom g_i tillhör a för alla i. Låt oss säga att f tillhör a. Man kan då säga att lm(f) tillhör (lm(g₁),..,lm(g_s)), för något g_k och något n kommer lm(f-ng_k)= lm(f). Eftersom f - f-ng_k tillhör a får vi att f kommer att tillhöra [g₁, ..,g_s].

Källor

• Fröberg, Ralf; Passare Mikael (1997) (på engelska). An introduction to Gröbner bases. Pure and applied mathematics (New York, N.Y. : 1948), 0079-8185. Chichester: Wiley. Libris 4985489. ISBN 0-471-97442-0