Starke Gröbnerbasen

über Euklidischen Ringen

gemeinsames Projekt mit

Gerhard Pfister undAdrian Popescu

#0Ausgangssituation

R bezeichnet einen Euklidischen Ring,hier meistens R = Z, R nullteilerfrei

Polynomring P über R in n Variablen:

P = R[x1, . . . , xn] = R[x]

Wir haben eine Monomordnung < auf P gegeben.Hier ist < global, also xi > 1 für alle i.

Für Terme eventuell Auflösung in R, z.B.

4x < −15x in Z[x] da |4| < |− 15| in Z.

Wir können dann für f ∈ P

den Leitterm lt(f),den Leitkoeffizienten lc(f)und das Leitmonom lm(f)

eindeutig angeben.

Beispiel:f = 12x2 − 17xy2 + 4 ∈ Z[x, y] mit < DRL

lt(f) = −17xy2

lc(f) = −17

lm(f) = xy2

Es gilt lt(f) = lc(f) lm(f).

Sei I ◁ P ein Ideal. Wir definierendas Leitideal von I als das Ideal L(I) erzeugtvon allen Leittermen von allen Elementen in I.

Sei F ⊂ P eine Menge. Wir definierendas Leitideal von F durch L(F) = ⟨lt(f) | f ∈ F⟩.

Gegeben I ◁ P, G ⊂ P, so heißtG Gröbnerbasis für I falls gilt:

G ⊂ I und L(G) = L(I).

Gröbnerbasen können wir berechnenmit Buchbergers Algorithmus

Grundlegende Struktur:

Für f, g ∈ P \ {0} definieren wir das S-Polynom

spoly(f, g) = λf− σg

mit λ lt(f) = σ lt(g) wobei λ, σ minimaleTerme mit dieser Eigenschaft sind.

Spezialfall: Reduktion

Falls λ = 1 festgelegt brauchen wir g mit

lt(f) = σ lt(g), so dass lt(f− σg) < lt(f).

Schreibweise fG meint

(1) Solange f ̸= 0, suche passendes g ∈ G.(2) Falls erfolgreich, setze f← f− σg.

Zurück zu Schritt 1.(3) Gib f zurück.

Buchbergers Kriterium:

Falls G ⊂ P und für alle f, g ∈ G gilt

spoly(f, g)G = 0,

dann ist G eine Gröbnerbasis für ⟨G⟩.

I = ⟨f1, . . . , fr⟩ ⊂ PG← {f1, . . . , fr}

P ← {(fi, fj) | 1 ≤ i < j ≤ r}

While (P ̸= ∅) doWähle (p, q), P ← P \ {(p, q)}

h← spoly(p, q) = λp− σq

h← hG

If h ̸= 0?

P ← P ∪ {(h, g) | g ∈ G}

G← G ∪ {h}

Return G

Ist R ein Körper, G ⊂ I, so gilt:

L(I) = L(G)

⇐⇒Für alle f ∈ I \ {0} existiert g ∈ G mit lt(g) | lt(f).

Leider gilt diese Äquivalenz nichtüber beliebigen Euklidischen Ringen:

⇐= ,=⇒ /

Beispiel:Betrachte I = ⟨x⟩ ◁ Z[x].

G = {2x, 3x} ist eine Gröbnerbasis für I:

G ⊂ I, L(I) = ⟨x⟩ und x = 3x− 2x ∈ L(G).

aber 2x ∤ x und 3x ∤ x.

Gegeben I ◁ P, G ⊂ P nennen wirG starke Gröbnerbasis für I falls gilt:

Für alle f ∈ I \ {0} existiert g ∈ G

mit lt(g) | lt(f).

Problem in unserem Beispiel?

spoly(2x, 3x) = 0

Müssen gcd(2, 3) = 1 erreichenohne das Monom zu kürzen.

Idee:

G-Polynom von 2x und 3x bilden:gpoly(2x, 3x) = (−1) · (2x) + 1 · (3x) = x.

Neue Struktur:

Für f, g ∈ P \ {0} definieren wir das G-Polynom

gpoly(f, g) = auf+ bvg

mit u lm(f) = v lm(g), u, v minimale Monome unda lc(f) + b lc(g) = gcd(lc(f) , lc(g)), a, b ∈ R.

S-Polynom =⇒ Leitmonom wird gekürzt

G-Polynom =⇒ Leitkoeffizient wird gcd,Leitmonom bleibt erhalten

Verallgemeinertes Buchberger Kriterium:

Falls G ⊂ P und für alle f, g ∈ G gilt

spoly(f, g)G = 0 und gpoly(f, g)G = 0,

dann ist G eine starke Gröbnerbasis für ⟨G⟩.

#1Unnötige Paare

Für f, g ∈ G mit lc(f) | lc(g) gilt:

gpoly(f, g) {f,g} = 0.

Buchbergers Produktkriterium

Für f, g ∈ G mit lc(f) , lc(g) teilerfremdund lm(f) , lm(g) teilerfremd gilt:

spoly(f, g) {f,g} = 0.

Gilt nicht für G-Polynome:gpoly(3x, 2y) = y · 3x− x · 2y = xy ̸= 0.

Buchbergers Kettenkriterium (spoly)

Für f, g, h ∈ G mit

lm(f) | lcm (lm(g) , lm(h)) undlc(f) | lcm (lc(g) , lc(h))

können wir spoly(g, h) löschen, solange wirspoly(f, g) und spoly(f, h) betrachten.

Buchbergers Kettenkriterium (gpoly)

Für f, g, h ∈ G mit

lm(f) | lcm (lm(g) , lm(h)) undlc(f) | gcd (lc(g) , lc(h))

können wir gpoly(g, h) löschen, solange wirgpoly(f, g) und gpoly(f, h) betrachten.

Ergebnis von Lichtblau

Für f, g ∈ G betrachte nur

▶ spoly(f, g) falls lc(f) | lc(g) oder lc(g) | lc(f),▶ gpoly(f, g) falls lc(f) ∤ lc(g) und lc(g) ∤ lc(f).

#2Koeffizientenwachstum vermeiden

Modulare Techniken funktionieren meist nicht:

I = ⟨6x, 8x⟩ ◁ Z[x], dann ist G = {2x, 6x, 8x}

eine starke Gröbnerbasis.

Gröbnerbasen bzgl. Primzahlen p > 3 würdenimmer Gp = {x} sein.

Idee: Versuche Konstante oder Monomzu finden, die / das in I ◁ P liegt.

Kürze damit bei Reduktionen die Koeffizienten.

Sei I = ⟨f1, . . . , fr⟩ ◁ Z[x].

▶ Betrachte I über Q.▶ Berechne Gröbnerbasis G von I über Q.

▶ Gilt G = 1 so existiert Konstante c in I über Z.

▶ Berechne S = syz(1, f1, . . . , fr) ⊂∑r

i=0Q[x]ei.Dann ∃ σ ∈ S der Form se0 + . . . mit s ∈ Q.Finde k ∈ Z so dass kσ ∈

∑ri=0 Z[x]ei.

▶ Setze I = ⟨ks, f1, . . . , fr⟩.

#3Reduktionen verallgemeinern

Bislang kürzen wir f mit g fallslt(g) | lt(f), d.h. λlt(g) = lt(f).

Dann gilt lt(f− λg) < lt(f).

Wollen aber auch Leitkoeffizienten klein halten.

Verallgemeinerte Reduktion von f bzgl. G:

Suche g ∈ G mit lm(g) | lm(f).

1.Falls lc(g) | lc(f) kürze Leitterm:

lt(f− λg) < lt(f) und lm(f− λg) < lm(f)

2.Falls lc(g) ∤ lc(f) und lm(g) < lm(f)

so kürze den Leitkoeffizienten fallsa ∈ R existiert mit lc(f) − a lc(g) < lc(f):

lt(f− λg) < lt(f) aber lm(f− λg) = lm(f)

3.Und falls lc(g) ∤ lc(f) und lm(g)= lm(f)?

Tausche f, g mit spoly(f, g), gpoly(f, g) aus.

Lemma

⟨f, g⟩ = ⟨spoly(f, g), gpoly(f, g)⟩

falls lm(f) = lm(g).

Beweis:Zeige, dass beide Paare das gleiche Gitter aufspannen.

Betrachte hierzu M =

(u v

lc(g)d

− lc(f)d

)wobei

gpoly(f, g) = u f + v g

spoly(f, g) = lc(g)d

f − lc(f)d

g

gcd(lc(f) , lc(g)) = d

det(M) = −ulc(f)d

− vlc(g)d

= − 1d(u lc(f) + v lc(g)) = −1.

Also ist M invertierbar.

#4Implementierung

Verfügbar in Singular 4− 1− 2.

Beispiele Singular (Lichtblau) Singular Macaulay2 Magma

Cyclic-6 0, 330 0, 320 4, 708 2, 799

Cyclic-7 18.731, 820 5.636, 210 out of memory 366, 060

Katsura-7 2, 200 2, 250 204, 928 251, 630

Katsura-8 133, 390 135, 360 64.555, 420 (> 24h)Katsura-9 13.366, 590 12.951, 160 (> 24h) (> 24h)

Eco-9 3, 920 4, 050 870, 409 22, 520

Eco-10 38, 760 40, 670 (> 24h) 289, 540

F-633 0, 140 0, 120 14, 982 12, 880

F-744 118, 610 117, 890 (> 24h) (> 24h)Noon-7 34, 930 32, 700 (> 24h) (> 24h)Noon-8 3.1390, 060 3.079, 370 (> 24h) (> 24h)

Reimer-5 3, 620 3, 590 out of memory 1.932, 400

Reimer-6 1.216, 960 1.232, 530 out of memory (> 24h)Lichtblau 1, 910 1, 830 69, 536 2.242, 900

Bayes-148 9, 970 9, 900 117, 635 46, 240

Mayr-42 212, 320 212, 770 218, 635 40, 270

Yang-1 149, 120 147, 250 181, 210 50, 330

Jason-210 47, 010 46, 780 (> 24h) (> 24h)

#5Nähere Zukunft

Neue Ideen für ZN falls N keine Primzahlmit Tommy Hofmann

F4 Algorithmus über Euklidischen Ringenin gb / GB.jl für OSCAR.

Danke für Ihre Aufmerksamkeit

Fragen? Anmerkungen?