Gröbner bázisok elemi elmélete
(Vajda Róbert)

Vázlat

a
Motiváció
aa
Term rendezés
 
Redukció
a
Gröbner bázisok 
a
Buchberger algoritmus
 
Alkalmazások, implementációka

Szeged, november 15.															        Algebra szeminárium

Motiváció

1.Probléma:
(Subscript[f, 1]) = 0
(Subscript[f, 2]) = 0
…
(Subscript[f, s]) = 
        0            (Subscript[f, i]) ∈ K[X]

Van-e megoldás? Mikor van véges sok megoldás? Hány megoldás van? Hogyan oldjuk meg (szimbolikusan)?

2.Probléma:

?\(TraditionalForm\`\(\(\ \)\(f ∈ ⟨f\_1, …, f\_s⟩\)\)\)  (ideál tartalmazási probléma)

Lineáris Algebra

Legyen  az egyenletrendszer 

x + 2y + 3z = 4
5x + 6y + 7z = 8
9x + 10y + 11z = 12  

Megoldás a (K^3) affin tér részhalmaza (varietás)
 
 K[x, y, z] -ben a rendszerhez tartozó ideált, a ⟨(Subscript[f, 1]), (Subscript[f, 2]), 
          (Subscript[f, 3])⟩ = ⟨x + 2  y + 3  z - 
            4,  5  x + 6  y + 7  z - 8,  
          9  x + 10  y + 11  z - 12⟩ ideált is vizsgálhatjuk. Végtelen sok egyenletrendszert reprezentál. Válasszunk olyan generátorrendszerét, amelyikbõl egyszerű leolvasni a megoldást ⟶ GB egy ilyen speciális generátorrendszer lesz.

Adjuk meg az ideál egy másik generátorát!

Lineáris Algebra

x + 2y + 3z = 4
5x + 6y + 7z = 8
9x + 10y + 11z = 12 

Kapcsolat a Gauss-elimináció és a polinomhalmazzal történõ redukció között
(({{1, 2, 3}, {5, 6, 7}, {9, 10, 11}})({{4}, {8}, {12}}))~(({{1, 2, 3}, {0, -4, -8}, {9, 10, 11}})({{4}, {-12}, {12}}))~…~(({{1, 0, -1, -2}, {0, 1, 2, 3}})) 
⟨x + 2  y + 3  z - 4,  
            5  x + 6  y + 7  z - 8,  
            9  x + 10  y + 11  z - 12⟩=⟨x - z + 2,y + 2  z - 3⟩
elemi átalakítások ≡ redukciós lépések (a redukció előfeltételez egy rendezést a változókon, itt pl. x > y > z)

(Subscript[f, 2]) (Subscript[-> , (Subscript[f, 1])])h = (Subscript[f, 2]) - 
            5  (Subscript[f, 1]) = -4 y - 8  z + 
              12 ⟹ ⟨(Subscript[f, 1]), (Subscript[f, 2]), 
                  (Subscript[f, 3])⟩ = ⟨(Subscript[f, 1]), 
                (Subscript[f, 2]) - 5  (Subscript[f, 1]), 
                (Subscript[f, 3])⟩   ((Subscript[f, 2]) = 5  (Subscript[f, 1]) + h) 
Redukciós lépéseknek vége, ha nincs tovább redukálható elem ((Subscript[f, 1]) főmonomja nem oszt egyetlen monomot sem).

Egyhatározatlanos polinomgyűrű

Itt is ismert a redukció, ami nem más, mint a maradékos osztás és a polinom fokszáma redukálódik.
Tf, f, g ≠ 0 ∈ K[x] Ekkor ∃ q, r :  f = q g + r , ahol r = 0 vagy deg[r] < deg[g]

Ezt úgy is megfogalmazhatjuk, hogy f-et redukáltuk g  ({g}) szerint r-re   ⟨f, 
          g⟩ = ⟨g, 
          r⟩
A redukció a fokszám szerint történt.

Redukciók sorozata (Euklideszi alg.) ⟨f, 
          g⟩ = ⟨g, 
            r⟩ = … = ⟨ 
              (Subscript[r, k])⟩=⟨lnko[f, 
            g]⟩

Alapfogalmak

Legyen K[X] = K[(Subscript[x, 1]), (Subscript[x, 2]), …, (Subscript[x, n])] valamely test feletti polinomgyűrű. 

Két fontos összetevő: 

Term rendezés

Redukció

Term rendezés

Def. Legyen ([X], ·,1) a termek (power products – hatványszorzatok) monoidja, ahol \(TraditionalForm\`\([X]\) = {X\^α = \(x\_1\^α\_1\) …\ x\_n\^α\_n | \ α\_i ∈ ℕ\_0}\) és a szorzás a kitevők összegzését jelenti.
Ekkor ezen ' < ' egy megengedett (az oszthatósággal kompatibilis) rendezés, ha

	  (A)  1 < 
        (X^α) (α ≠ 0) 
	\(\((B)\)\ \ X\^α < \(\(X\^β\)\(⟹\)\)\)(X^α)(X^γ)<(X^β) (X^γ) 
aDe

Lemma.
Ha < megengedett rendezés és s | t ⟹s ≤ t
\(TraditionalForm\`\( < \^\(-1\)\)\)Noether-féle és így [X] minden részhalmazának van legkisebb eleme.

Lexikografikus term rendezés

Rögzítsük a határozatlanok egy sorrendjét, pl. \(x\_1\( > \_lex\)x\_2\( > \_lex\)…\( > \_lex\)x\_n\).
Legyenek  s = (Subscript[((Subscript[x, 1])^i), 1]) (Subscript[((Subscript[x, n])^i), n]),  
          t = (Subscript[((Subscript[x, 1])^j), 1]) (Subscript[((Subscript[x, n])^j), n]) tetszőleges termek.

Ekkor  s\( < \_lex\)t ⟺ ∃ k ∈ {1, …, 
                        n} ∀ l (l < k) (Subscript[i, l])=(Subscript[j, l]) ∧ (Subscript[i, k])<(Subscript[j, k]) 

Példa. \(\(x\_1\^2\) \(x\_2\) x\_3\^2\( < \_lex\)\(x\_1\^2\) 
              x\_2\^2\) 

(1 < (Subscript[x, 3]) < ((Subscript[x, 3])^2) < ((Subscript[x, 3])^3) < 
              (Subscript[x, 2]) < (Subscript[x, 2]) (Subscript[x, 3]) < (Subscript[x, 2]) ((Subscript[x, 3])^2) < 
              ((Subscript[x, 2])^2) < ((Subscript[x, 2])^2) (Subscript[x, 3]) < ((Subscript[x, 2])^3) < 
              (Subscript[x, 1]) < (Subscript[x, 1]) (Subscript[x, 3]) < (Subscript[x, 1]) ((Subscript[x, 3])^2) < (Subscript[x, 1]) 
                (Subscript[x, 2]) < (Subscript[x, 1]) (Subscript[x, 2]) (Subscript[x, 3]) < (Subscript[x, 1]) ((Subscript[x, 2])^2) < 
              ((Subscript[x, 1])^2) < ((Subscript[x, 1])^2) (Subscript[x, 3]) < ((Subscript[x, 1])^2) (Subscript[x, 2]) < ((Subscript[x, 1])^3))

Deglex term rendezés

Legyen \(TraditionalForm\`\( < \_lex\)\) az előző (a határozatlanok egy rögz. sorrendje szerinti ) lexikografikus rendezés. 
Legyenek  s = (Subscript[((Subscript[x, 1])^i), 1]) (Subscript[((Subscript[x, n])^i), n]),  
          t = (Subscript[((Subscript[x, 1])^j), 1]) (Subscript[((Subscript[x, n])^j), n]) tetszőleges termek.

Ekkor  s\( < \_deglex\)t ⟺∑(Subscript[i, l])<∑(Subscript[j, l])∨ \((∑i\_l = ∑j\_l ∧ \ s\( < \_lex\)t)\)  

Példák. \(\(x\_1\^2\) x\_2\^2\( < \_deglex\)\(x\_1\^2\) \(x\_2\) 
              x\_3\^2\)
                  ((Subscript[x, 1])^2)(Subscript[x, 2])(Subscript[x, 3])\( < \_deglex\)((Subscript[x, 1])^2) 
              ((Subscript[x, 2])^2)
                 

(1<(Subscript[x, 3])<(Subscript[x, 2])<(Subscript[x, 1])<((Subscript[x, 3])^2)<(Subscript[x, 2]) (Subscript[x, 3])<((Subscript[x, 2])^2)<(Subscript[x, 1]) (Subscript[x, 3])<(Subscript[x, 1]) (Subscript[x, 2])<((Subscript[x, 1])^2)<((Subscript[x, 3])^3)<(Subscript[x, 2]) ((Subscript[x, 3])^2)<((Subscript[x, 2])^2) (Subscript[x, 3])<((Subscript[x, 2])^3)<(Subscript[x, 1]) ((Subscript[x, 3])^2)<(Subscript[x, 1]) (Subscript[x, 2]) (Subscript[x, 3])<(Subscript[x, 1]) ((Subscript[x, 2])^2)<((Subscript[x, 1])^2) (Subscript[x, 3])<((Subscript[x, 1])^2) (Subscript[x, 2])<((Subscript[x, 1])^3))

lcf, lpp, lmon, red  (főegyüttható, főterm, főmonom, redukt)

Legyen egy term rendezés rögzítve (<),  \(TraditionalForm\`f ∈ K[X]\{0}\).

\(TraditionalForm\`lpp(
          f) = \(max\_ < \){X\^α | \ 
              coeff(f, X\^α) ≠ 0}\) 
lc(f) = coeff(f, lpp(f))
lmon(f) = in(f) = lc(f) lpp(f)
red(f) = f - in(f)

Példa.
Ha <  a lex. term rendezés  x > y > z-vel és f=2  (x^2) y z+3  x (y^3)-2  (x^3) , akkor
lpp(f) = (x^3),  lc(f) = -2,  
      lmon(f) = -2 (x^3)
Ha <  a deglex. term rendezés  x > y > z-vel és f=2  (x^2) y z+3  x (y^3)-2  (x^3) , akkor
lpp(f) = (x^2) y z,  lc(f) = 2,  
          lmon(f) = 2  (x^2) y z

Indukált részbenrendezés

Indukált részbenrendezés K[X]-en (<< )

Tf, hogy \(TraditionalForm\`f, g ∈ K[X]\{0}\). f << g⟺ lpp(f) < 
          lpp(g)∨(lpp(f) = 
            lpp(g) ∧  red (f) << red (g))

Redukció

f h szerint redukálható (1 lépésben) g-re (f (Subscript[-> , h])g) , ha vannak olyan s, 
      t  ∈ [X] :  
          coeff(f, s) ≠ 0 ∧  lpp(h) t = s ∧ g = 
          f - coeff(f, s)/lc(h) t h.

Példa.  Legyen < a gradlex. term rendezés ((Subscript[x, 1]) < (Subscript[x, 2]) < (Subscript[x, 3]))
h = (Subscript[x, 1]) (Subscript[x, 3]) + (Subscript[x, 1]) (Subscript[x, 2]) - 2  (Subscript[x, 3]),  
      f = ((Subscript[x, 3])^3) + 2  (Subscript[x, 1]) (Subscript[x, 2]) (Subscript[x, 3]) + 2  (Subscript[x, 2]) - 1
f (Subscript[-> , h])(((Subscript[x, 3])^3) + 2  (Subscript[x, 2]) - 1 - 
            2  (Subscript[x, 1]) ((Subscript[x, 2])^2) + 4  (Subscript[x, 2]) (Subscript[x, 3])), mert

lpp(h) = (Subscript[x, 1]) (Subscript[x, 3]),  lpp(h) | 
        2  (Subscript[x, 1]) (Subscript[x, 2]) 
          (Subscript[x, 3]), (s = (Subscript[x, 1]) (Subscript[x, 2]) (Subscript[x, 3]),  
        t = (Subscript[x, 2])) 
 g = f - 2  (Subscript[x, 2]) h = 
                ((Subscript[x, 3])^3) + 2  (Subscript[x, 2]) - 1 - 2  (Subscript[x, 1]) ((Subscript[x, 2])^2) + 4(Subscript[x, 2])(Subscript[x, 3]) (g < f)  

A definíció kiterjesztése: Legyen H = {(Subscript[h, 1]), …, (Subscript[h, s])} (polinomok véges halmaza).
                                        f (Subscript[-> , H])g⟺(Underscript[∃ , i]) f(Subscript[⟶, (Subscript[h, i])])g

Gröbner Bázis, motiváló példák

Sokféle bevezetési lehetőség, egyik legtermészetesebb, ami a bevezetett redukcióval hozza kapcsolatba. Problematikus példák.
ℚ[x] :  f = x,  (Subscript[f, 1]) = (x^2),  
          (Subscript[f, 2]) = (x^2) - x,  fnem redukálható F = {(Subscript[f, 1]), (Subscript[f, 2])} szerint, pedig f ∈ 
              (Subscript[I, 1]) = ⟨(Subscript[f, 1]), 
                (Subscript[f, 2])⟩.
ℚ[x, y],  deglex,  y > x,  
          f = (y^2) x - x,  (Subscript[f, 1]) = y x - y,  (Subscript[f, 2]) = (y^2) - x
\(f\( -> \_\(f\_1\)\)\(y\^2 - 
                  x\( -> \_\(f\_2\)\)0\ \ \((\(\(⟹\)\(f\)\) ∈ I\_2 = ⟨f\_1, 
                        f\_2⟩)\)\)\), míg f (Subscript[-> , (Subscript[f, 2])])(x^2) - x és ez tovább már nem redukálható. 
Cseréljük ki a generátorrendszert, pl. \(I\_1 = \(⟨lnko[f\_1, 
                    f\_2]⟩ = ⟨x⟩\)\), (Subscript[I, 2])=⟨(Subscript[f, 1]), (Subscript[f, 2]), 
                (x^2) - x⟩ 
Ekkor f (Subscript[-> , lnko[(Subscript[f, 1]), (Subscript[f, 2])]])0 ill.

Gröbner Bázis, DEF.

Legyen I = {(Subscript[g, 1]),  (Subscript[g, 2]), …, 
            (Subscript[g, s])} = ⟨G⟩ ⊂ K[
                X]. G Gröbner bázisa I-nek, ha minden \(TraditionalForm\`f ∈ I\(\(⟶\_G\)\^*\)0\).

Sokféle alternatív definíció létezik (olyan generátorrendszer, ahol minden ideálbeli elem redukálható, redukció reláció Church-Rosser, ... ), ezekről megmutatható, hogy ekvivalensek és minden ideálnak van GB-a. A felépítés szempontjából érdekesek azok, amelyek nem hivatkoznak explicite a redukció relációra, pl.

DEF2. G Gröbner bázisa I-nek, ha ⟨In(G)⟩=⟨In(⟨G⟩)⟩

Gröbner Bázis, unicitás, (normált) redukált GB

Gröbner bázis nem egyértelmű, pl. ha I = ⟨(Subscript[f, 1]), (Subscript[f, 2]), 
            (Subscript[f, 3])⟩ = ⟨(y^2) + y x + (x^2), 
            y + x,  y⟩ akkor GB = {(Subscript[f, 1]), (Subscript[f, 2]), (Subscript[f, 3]), (Subscript[f, 4]) = (x^2), (Subscript[f, 5]) = y} Gröbner bázisa I-nek (lex, y > x), de pl. a
GB2 = {(Subscript[f, 3]), (Subscript[f, 5])} is. A második, "kisebb" bázist redukáltnak nevezzük. G redukált GB,  ha

(1) (Underscript[∀ , i]) lc(i) = 1  
(2)(Underscript[∀ , i]) (Subscript[g, i]) redukált modulo G - {(Subscript[g, i])}

Tétel (Buchberger). Tetsz. (de rögz.) term rendezés esetén minden (nemzéró) ideálnak pontosan egy redukált Gröbner bázisa van.

Buchberger Algoritmus

Hogyan határozzunk meg egy Gröbner bázist, hogyan határozzuk meg a redukált Gröbner bázist? 

Def. (S-polinom) Legyen f,\(g ∈ K[X]\{0}\), t=lkkt(lpp(f), lpp(g)). spol(f, g)=(t/(In(f))) f - (t/(In(g))) g.
ℚ[x, y],  deglex,  
      y > x,   (Subscript[f, 1]) = y x - y,  
      (Subscript[f, 2]) = (y^2) - x .  lkkt(lpp((Subscript[f, 1])), lpp((Subscript[f, 2]))) = (y^2) x 
spol((Subscript[f, 1]), (Subscript[f, 2])) = (y) (Subscript[f, 1]) - (x) (Subscript[f, 2]) = 
          (x^2) - (y^2)

PolynomialReduce[(x^2) - (y^2), {y x - y, y^2 - x}, {y, x}, 
        MonomialOrder -> 
          DegreeLexicographic][[2]]

Buchberger Algoritmus

Alapmódszer: Input: termrendezés, az I ideál egy véges F={(Subscript[f, 1]), …, (Subscript[f, s])} bázisa. Output: I Gröbner bázisa. 
Válasszunk egyet az \(TraditionalForm\`{f\_i, 
            f\_j}\ párokhoz\ tartozó\ \ S - \(\(polinomokból\)\(.\)\)\) Redukáljuk ezt modulo F, ha nemzéró a redukt (r), akkor vegyük hozzá F-hez, azaz legyen (Subscript[F, 1]) = F ⋃ {r}. Ismételjük ezt minaddig, amíg az összes képezhető S-polinom már nullára redukálódik.
Példa.
\(TraditionalForm\`ℚ[x, y], \ deglex, \ 
      y > x, \ \ f\_1 = y\ x - y, \ 
      f\_2 = \(y\^2 - 
            x . \ \(spol(f\_1, f\_2)\) = \(x\^2 - 
              y\^2\(\(⟶\_{f\_1, f\_2}\)\^+\)f\_3 = 
            x\^2 - x ≠ 0\)\)\)

\(TraditionalForm\`{f\_1, 
            f\_2} ⋃ {f\_3} = {f\_1, f\_2, 
              f\_3} . \ \(spoly(f\_1, 
                f\_3)\)\(⟶\^+\)0\  ∧ \(spoly(f\_2, 
              f\_3)\)\(⟶\^+\)0\ ⟹\ {f\_1, f\_2, f\_3}\) GB!

Buchberger Algoritmus

Tétel. Buchberger algoritmusa véges sok lépés után terminál és az utolsó véges polinomhalmaz az I ideál Gröbner bázisa. 

Tétel. G Gröbner bázis ⟺ \(TraditionalForm\`\(∀ \+\(i, j\)\)\+\(i ≠ j\)\(spol(
            g\_i, g\_j)\)\(⟶\_+\)0. \) 
Megjegyzés. Redukált GB konstruálásához 'interredukáljuk' a kapott GB-t.

Alkalmazások 1

Egyenletrendszer megoldása (P8)
 3 a1 + 3  d = 21
 a1 + d + 13 =  (a1 + 6) q
 a1 + 2  d + 30 = (a1 + 6) (q^2)

ps = {3  a1 + 3  d - 21, 
        a1 + d + 13 - (a1 + 6) q, 
        a1 + 2  d + 30 - (a1 + 6) (q^2)}

GroebnerBasis[ps, {q, d, a1}]

Solve[-(a1^2) + 38  a1 - 136 == 0, a1]

Megjegyzés. A GB a lex termrendezés szerint számoltuk. Pusztán a redukált GB 'alakjából' sok mindent leolvashatunk, pl. 1 ∉  I, ezért van megoldás (alg. zárt test felett), ha minden (Subscript[x, i]) változóhoz létezik egy (Subscript[g, i]) ∈ GB, úgy, hogy lpp((Subscript[g, i])) tiszta (Subscript[x, i])-hatvány, akkor véges sok megoldás van, továbbá a megoldások száma (multiplicitással) a különböző redukálhatatlan termek száma (1, a1). Továbbá, a lexikografikus termrendezés esetén  a r. GB-ban a változók szeparáltak (triang. rendszer)  
(Mego.: 4 7 10,  10 20 40 ill. 34 7 -20, 40 20 10)

Alkalmazások 2

? f ∈  I
- Számítsuk ki az ideál egy GB-át, és vizsgáljuk, hogy \(TraditionalForm\`f\(\(⟶\_GB\)\^+\)0\).
Példa.
? 4 x (y^4) + 16  (x^2) (y^2) + (y^2) + 8  x + 
          2 ∈ ⟨4  z - 4  x (y^2) - 16  (x^2) - 1, 
          2  (y^2) z + 4  x + 1, 
          2  (x^2) z + 2  (y^2) + x⟩

f = 
        4  x (y^4) + 16  (x^2) (y^2) + (y^2) + 8  x + 
          2; 

    (Subscript[f, 1]) = 4  z  - 4  x (y^2) - 16  (x^2) - 1;

    (Subscript[f, 2]) = 2  (y^2) z + 4  x + 1; 
    (Subscript[f, 3]) = 2  (x^2) z + 2  (y^2) + x;

PolynomialReduce[f, 
        GroebnerBasis[{(Subscript[f, 1]), (Subscript[f, 2]), (Subscript[f, 3])}, {z, y, x}], {z, y, 
          x}][[2]]

⟹ f ∈ 
      I

Implementáció 1 (Mathematica)

Mathematica-ban pl. a PolynomialReduce[] GroebnerBasis[] utasítások hassználhatók:

f = (y^2) x - x; (Subscript[f, 1]) = y x - y; 
    (Subscript[f, 2]) = (y^2) - x;

PolynomialReduce[f, {(Subscript[f, 1]), (Subscript[f, 2])}, 
      MonomialOrder -> DegreeLexicographic]
PolynomialReduce[f, {(Subscript[f, 2]), (Subscript[f, 1])}, 
      MonomialOrder -> DegreeLexicographic]

{(Subscript[f, 1]), (Subscript[f, 2])} nem GB!

GroebnerBasis[{(Subscript[f, 1]), (Subscript[f, 2])}, 
      MonomialOrder -> DegreeLexicographic]

Implementáció 2 (Mathematica, Maple)

Mathematica-hoz is készült (extern) Gröbner-programcsomag (Groebner.m, G. Helzer, Univ. of Maryland, B. Buchberger ,RISC, etc.)
Maple-ben külön (intern) Groebner-csomag áll rendelkezésre. 'heavy' Gröbner számítások ⟶ Singular (Kaiserslautern, Németo.)

Külső csomag nem része a az alaprendszernek!

<< Groebner.m

vars = {x, y, z}; f = 2  (x^2) y z + 3  x (y^3) - 2  (x^3);

\(TableForm[{{\(LeadingCoefficient[vars, lex]\)[
            f], \(LeadingPowerProduct[vars, lex]\)[
            f], \(LeadingTerm[vars, lex]\)[
            f]}, {\(LeadingCoefficient[vars, deglex]\)[
            f], \(LeadingPowerProduct[vars, deglex]\)[
            f], \(LeadingTerm[vars, deglex]\)[f]}}, 
      TableHeadings -> {{"lex", "deglex"}, {"lc", "lpp", "in"}}]\)

Irodalom

B. Buchberger: Ein Algorithmus zum Auffinden des Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. (Mathematical Institute, University of Innsbruck, Austria, PhD Thesis. 1965)
 
W. W. Adams – Ph. Loustaunau: An Introduction to Gröbner Bases. GSM 3, 1996.

Th. Becker – V. Weispfenning: Gröbner Bases: A Computational Approach to Commutative Algebra. Springer, New York, 1993.
 
F. Winkler: Polynomial Algorithms in Computer Algebra. 8. The method of Gröbner Bases. Springer, Wien-New York, 1996.
 
Iványi Antal et al.: Informatikai Algoritmusok 1. 2.3 Gröbner-bázisok. pp. 63-71.  ELTE Kiadó, Budapest, 2004.

A zsonglőr diák és mestere :)