Calcolo di una base di Gröbner

Algoritmo di Buchberger Input: g_{1}, …, g_{s} ∈ P^{r}, t.o. σ; Output: G, σ-base di Gröbner di M = ⟨g_{1}, …, g_{s}⟩ ⊆ P^{r}.

Sia LM_{σ}(g_{i}) = c_{i}t_{i}e_{γ_{i}} s′ = s; G = (g_{1}, …, g_{s}) B = {(i, j) | 1 ≤ i < j ≤ s, γ_{i} = γ_{j}}; while B ≠ ∅ do

scegli (i, j) ∈ B;

B = B \ {(i, j)};

S_{ij} = ϕ(σ_{ij}) = \frac{1}{c_{i}} t_{ij}g_{i} − \frac{1}{c_{j}} t_{ji}g_{j};

Calcola NR_{σ,G}(S_{ij}), il ridotto di S_{ij} rispetto a G; if NR_{σ,G}(S_{ij}) ≠ 0 then

s′ = s′ + 1;

g_{s′} = NR_{σ,G}(S_{ij});

G = G, g_{s′};

B = B ∪ {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}}; end if;

end while; return G.

Esempio

Sia P = ℚ[x, y] e sia G = (g_{1}, g_{2}, g_{3}) con g_{1}, g_{2}, g_{3} ∈ P^{2} definiti da:

g_{1} = (x^{2}y − 1, 0), g_{2} = (xy^{2} − 1, x), g_{3} = (0, xy + 1)

Sui termini 𝕋⟨e_{1}, e_{2}⟩ di P^{2} definiamo il term order σ dato da PosLex, quindi t_{1}e_{i} <_{σ} t_{2}e_{j} se i > j o, se i = j, allora se t_{1} <_{Lex} t_{2}. Pertanto vale:

LM_{σ}(g_{1}) = x^{2}ye_{1}, LM_{σ}(g_{2}) = xy^{2}e_{1}, LM_{σ}(g_{3}) = xye_{2}

Calcolo della base di Gröbner con l’algoritmo di Buchberger: s′ = 3; G = (g_{1}, g_{2}, g_{3}) B = {(1, 2)} scegliamo (1, 2) ∈ B; B = ∅ S_{12} = (x − y, −x^{2}). S_{12} è ridotto modulo G. Pertanto: s′ = 4; g_{4} = (x − y, −x^{2}); G = G, g_{4}; B = {(1, 4), (2, 4)}; Scegliamo (1, 4) ∈ B; B = {(2, 4)}; S_{14} = (xy^{2} − 1, x^{3}y); La riduzione con G dà: S_{14} − g_{2} − x^{2}g_{3} = (0, −x^{2} − x); pertanto s′ = 5, g_{5} = (0, −x^{2} − x), G = G, g_{5}; B = {(2, 4), (3, 5)} Scegliamo (2, 4) ∈ B; B = {(3, 5)}; S_{24} = (y^{3} − 1, x^{2}y^{2} + x); La riduzione con G dà: S_{24} − xyg_{3} + g_{3} = (y^{3} − 1, x + 1); pertanto s′ = 6, g_{6} = (y^{3} − 1, x + 1), G = G, g_{6}; B = {(3, 5), (1, 6), (2, 6), (4, 6)} Scegliamo (3, 5) ∈ B; B = {(1, 6), (2, 6), (4, 6)} S_{35} = (0, −xy + x); La riduzione con G dà: S_{35} + g_{3} = (0, x + 1); pertanto s′ = 7, g_{7} = (0, x + 1), G = G, g_{7}; B = {(1, 6), (2, 6), (4, 6), (3, 7), (5, 7)} Scegliamo (5, 7) ∈ B B = {(1, 6), (2, 6), (4, 6), (3, 7)} S_{57} = 0 Scegliamo (3, 7) ∈ B B = {(1, 6), (2, 6), (4, 6)} S_{37} = (0, −y + 1); è ridotto rispetto a G s′ = 8, g_{8} = (0, −y + 1), G = G, g_{8}; B = {(1, 6), (2, 6), (4, 6), (3, 8), (5, 8), (7, 8)} Da qui in poi si vede che la forma ridotta di S_{ij} vale sempre 0 per ogni (i, j) ∈ B. Pertanto una σ-base di Gröbner del modulo M è data da:

\begin{matrix}g_{1} = (x^{2}y − 1, 0), & g_{2} = (xy^{2} − 1, x), & g_{3} = (0, xy + 1), & g_{4} = (x − y, −x^{2}) \\ g_{5} = (0, −x^{2} − x), & g_{6} = (y^{3} − 1, 1 + x), & g_{7} = (0, x + 1), & g_{8} = (0, −y + 1) \end{matrix}

Dal procedimento usato per il calcolo della base di Gröbner {g_{1}, …, g_{8}} con l’algoritmo di Buchberger, si vede anche come otterenere ciascun g_{i} come combinazione lineare dei generatori di partenza (cioè di g_{1}, g_{2}, g_{3}). Ad esempio g_{4} è stato ottenuto da S_{12}, cioè g_{4} = yg_{1} − xg_{2}, mentre g_{5} = S_{14} − g_{2} − x^{2}g_{3}, quindi g_{5} = g_{1}−xy(yg_{1}−xg_{2})−g_{2}−xyg_{3}, cioè g_{5} = (−xy^{2}+1)g_{1}+(x^{2}y−1)g_{2}+(−x^{2})g_{3}. In questo modo si vede che, se chiamiamo H la matrice 1 × 3 la cui riga è costituita dai generatori h_{1} = g_{1}, h_{2} = g_{2}, h_{3} = g_{3} del modulo M e G la matrice 1 × 8 costituita dalla base di Gröbner g_{1}, …, g_{8}, si può costruire una matrice 8 × 3, A, ad entrate polinomiali, tale che

G = H · A

La matrice A vale:

( \begin{matrix}1 & 0 & 0 & y & −xy^{2} + 1 & −y^{3} & −xy^{3} + y & xy^{4} − y^{2} \\ 0 & 1 & 0 & −x & x^{2}y − 1 & xy^{2} + 1 & x^{2}y^{2} − y & −x^{2}y^{3} + y^{2} \\ 0 & 0 & 1 & 0 & −x^{2} & −xy + 1 & −x^{2}y + x + 1 & x^{2}y^{2} − xy − y + 1 \end{matrix} )

Base di Gröbner minimale I leading term della base di Gröbner scritta sopra sono:

LT_{σ}(g_{1}) = x^{2}ye_{1}, LT_{σ}(g_{2}) = xy^{2}e_{1}, LT_{σ}(g_{3}) = xye_{2}, LT_{σ}(g_{4}) = xe_{1},
LT_{σ}(g_{5}) = x^{2}e_{2}, LT_{σ}(g_{6}) = y^{3}e_{1}, LT_{σ}(g_{7}) = xe_{2}, LT_{σ}(g_{8}) = ye_{2}.

Come si vede, alcuni leading term sono multipli di altri (ad esempio LT_{σ}(g_{1}) e LT_{σ}(g_{2}) sono multipli di LT_{σ}(g_{4}), mentre LT_{σ}(g_{3}) è multiplo di LT_{σ}(g_{7})). Se dalla base di Gröbner g_{1}, …, g_{8} togliamo quegli elementi i cui leading term sono multipli di altri, otteniamo ancora una base di Gröbner di M. Quindi gli elementi che rimangono in questo esempio sono: g_{4}, g_{6}, g_{7}, g_{8}. Questa è una base di Gröbner minimale di M, in accordo con la: Definizione: una base di Gröbner g_{1}, …, g_{s} si dice minimale se LT_{σ}(g_{i}) non è multiplo di LT_{σ}(g_{j}) per ogni i ≠ j e se LC_{σ}(g_{i}) = 1 per ogni i. Infine si noti che alcuni elementi della base {g_{4}, g_{6}, g_{7}, g_{8}} possono essere ridotti rispetto agli altri. Ad esempio g_{6} può essere ridotto rispetto a g_{7} (infatti g_{6} →_{{g_{7}}} (y^{3} − 1, 0) = g_{6} − g_{7}) e così pure g_{4} si può ridurre con g_{7} (infatti g_{4} →_{{g_{7}}} (x − y, −1) = g_{4} + xg_{7} − g_{7}). Si ottengono così i seguenti elementi di P^{2}:

\overline{g}_{1} = (0, x + 1), \overline{g}_{2} = (0, y − 1), \overline{g}_{3} = (x − y, −1), \overline{g}_{4} = (y^{3} − 1, 0)

che sono ancora una base di Gröbner di M (perchè i loro LT_{σ} non sono stati alterati) e formano una base di Gröbner ridotta, in accordo con la: Definizione: una base di Gröbner g_{1}, …, g_{s} si dice ridotta se è minimale e se g_{i} è ridotto modulo {g_{1}, …, g_{i−1}, g_{i+1}, …, g_{s}}, per ogni i = 1, …, s.

Si può dimostrare che da ogni base di Gröbner si può estrarre una base di Gröbner ridotta e la base di Gröbner ridotta è unica (per un fissato ordinamento).

Seguendo i calcoli che hanno permesso di ottenere la base di Gröbner ridotta a partire da {g_{1}, …, g_{8}}, si può anche ora trovare una matrice, chiamiamola ancora A, tale che \overline{G} = H · A, dove ora \overline{G} = \overline{g}_{1}, …, \overline{g}_{4}. La matrice A che si trova è:

( \begin{matrix}−xy^{3}+y & −xy^{4}+y^{2} & xy^{3}+xy^{2}−1 & xy^{3}−y^{3}−y \\ x^{2}y^{2}−y & x^{2}y^{3}−y^{2} & −x^{2}y^{2}−x^{2}y−x+y+1 & −x^{2}y^{2}+xy^{2}+y+1 \\ −x^{2}y+x+1 & −x^{2}y^{2}+xy+y−1 & x^{2}y+x^{2}−x−1 & x^{2}y−xy−x \end{matrix} )

Infine, poiché gli elementi di H (che sono i generatori di M) sono ovviamente elementi di M, devono ridursi a 0 con la base di Gröbner \overline{G}, pertanto, applicando l’algoritmo di divisione, si ottiene, ad esempio: h_{1} = y\overline{g}_{1} +y\overline{g}_{2} +(xy +y^{2})\overline{g}_{3} +\overline{g}_{4} e così per tutti gli altri. In questo modo si può costruire una matrice 4 × 3, B, tale che H = \overline{G} · B. La matrice B vale:

( \begin{matrix}y & 1 & y \\ y & y + 1 & −1 \\ xy + y^{2} & y^{2} & 0 \\ 1 & 1 & 0 \end{matrix} )

Consideriamo ora la base di Gröbner \{\overline{g}_{1}, \overline{g}_{2}, \overline{g}_{3}, \overline{g}_{4}\} scritta sopra. Poiché è una base di Gröbner, per il criterio di Buchberger l’S-vettore di \overline{g}_{i} e \overline{g}_{j} (quando è definito) deve ridursi a zero con \{\overline{g}_{1}, \overline{g}_{2}, \overline{g}_{3}, \overline{g}_{4}\}. Infatti si trova, con S_{12}: (y − 1)\overline{g}_{1} − (x + 1)\overline{g}_{2} = 0 da cui si costrisce la sizigia τ_{12} = (y − 1)ε_{1} − (x + 1)ε_{2}, analogamente, con S_{34} si ottiene: (y^{2} +y +1)\overline{g}_{2} +(y^{3} −1)\overline{g}_{3} +(−x+y)\overline{g}_{4} = 0, da cui la sizigia τ_{34} = (y^{2} +y+1)ε_{2} +(y^{3} −1)ε_{3} +(−x+y)ε_{4} e quindi, per il teorema di Schereyer, τ_{12}, τ_{34} è una δ-base di Gröbner del modulo Siz (\overline{g}_{1}, \overline{g}_{2}, \overline{g}_{3}, \overline{g}_{4}) (dove δ è il term-order definito nel teorema di Schreyer).