präsentiert von
Inhaltsverzeichnis
1
Einleitung
1
2
Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
3
2.1
Monomordnungen
. . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2
Polynomreduktionen . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Gr¨
obnerbasen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4
S-Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5
Transformations- und Syzygiematrizen . . . . . . . . . . . . . . .
10
2.6
Reduzierte Gr¨
obnerbasen
. . . . . . . . . . . . . . . . . . . . . .
13
3
Gl¨
uckbringende Primzahlen
14
4
Lifting von Gr¨
obnerbasen
18
5
Der Liftingalgorithmus
29
5.1
Gleichungssystem zur Bestimmung der Liftingfolge . . . . . . . .
29
5.2
Gr¨
obnerbasen von Moduln . . . . . . . . . . . . . . . . . . . . . .
30
5.3
Bestimmung der gew¨
unschten L¨
osung des Gleichungssystems . .
31
5.4
R¨
uckschluss auf die reduzierte Gr¨
obnerbasis . . . . . . . . . . . .
33
5.5
Liftingalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Literaturverzeichnis
39
1. Einleitung
1
Einleitung
Bruno Buchberger entwickelte im Jahre 1965 das Konzept der Gr¨
obnerbasen.
Mit Gr¨
obnerbasen, die Buchberger nach seinem Doktorvater Wolfgang Gr¨
obner
benannte, lassen sich eine Vielzahl von Problemen l¨
osen, wie z.B. dem Idealzu-
geh¨
origkeitsproblem oder das L¨
osen nichtlinearer polynomieller Gleichungssys-
teme.
Ein großes Problem bei der Berechnung von Gr¨
obnerbasen in
Q[x
1
, . . . , x
]
ist das riesige Wachstum der Koeffizienten, die die praktische Berechnung aus
Laufzeit- und Speicherplatzgr¨
unden erschweren oder sogar unm¨
oglich machen.
Es seien beispielsweise
F =
x
2
y
2
-
14
3
x
3
y
xy
3
-
12
7
x
2
y
2
+ 8x
y
4
+ 8y
- 24x
3
und I das von F erzeugte Ideal. Wir k¨
onnen zeigen, dass
G =
y
4
+ 8y
xy
3
+ 8x
x
2
die reduzierte Gr¨
obnerbasis von I bzgl. der lexikografischen Monomordnung mit
x < y ist.
Obwohl die Koeffizienten von F und G relativ klein sind, so kommen bei der Be-
rechnung von zwischenzeitlich auftretenden Polynomen sehr große Koeffizienten
wie 1098247/1190896 zustande (siehe [7, Seite 300 f., Beispiel 2]).
Franz Winkler entwarf in seiner Arbeit [7] einen Algorithmus, um f¨
ur ein gege-
benes System von Polynomen in
Q[x
1
, . . . , x
] eine Gr¨
obnerbasis zu berechnen,
ohne mit dem Problem des enormen Zuwachses der Koeffizienten konfrontiert
zu werden.
Das Prinzip dieses Algorithmus beruht darauf, dass man sich per Zufall eine
Primzahl p ausw¨
ahlt und zun¨
achst die reduzierte Gr¨
obnerbasis G
(0)
von F in
F
p
[x
1
, . . . , x
] berechnet. Wenn man Gl¨
uck hat, dann verliert man keine bedeu-
tenden Informationen ¨
uber die gesuchte reduzierte Gr¨
obnerbasis G. Anschlie-
ßend kann man G
(0)
zu einem System G
(i-1)
in
Z/p
i
Z f¨ur beliebige nat¨urliche
Zahlen i hochheben. Wissen wir eine obere Schranke f¨
ur die Koeffizienten von G,
so kann man i groß genug w¨
ahlen, sodass wir nach der Transformation der Ko-
effizienten von
Z/p
i
Z nach Q tats¨achlich die gesuchte reduzierte Gr¨obnerbasis
G in
Q[x
1
, . . . , x
] erhalten.
In dieser Arbeit soll diese Methode von Winkler vorgestellt und erkl¨
art werden.
Dazu werden wir in den Kapiteln 2 bis 4 das ben¨
otigte Wissen aneignen, um
den Algorihmus verstehen zu k¨
onnen.
In Kapitel 2 werden wir eine Einf¨
uhrung in die Theorie der Gr¨
obnerbasen geben
und die wichtigsten Begriffe und Resultate pr¨
asentieren. Eine Besonderheit in
1
1. Einleitung
diesem Kapitel stellt die Beschreibung von Gr¨
obnerbasen mithilfe von Matrizen
dar, den sogenannten Transformations- und Syzygiematrizen.
In Kapitel 3 definieren wir den Begriff der gl¨
uckbringenden Primzahlen p und
werden zeigen, dass diese Primzahlen f¨
ur den informationserhaltenden ¨
Ubergang
der reduzierten Gr¨
obnerbasis von
Q[x
1
, . . . , x
] nach
F
p
[x
1
, . . . , x
] verantwort-
lich sind. Außerdem wird sich herausstellen, dass f¨
ur ein gegebenes System von
Polynomen in
Q[x
1
, . . . , x
] fast alle Primzahlen gl¨
uckbringend sind.
In Kapitel 4 besch¨
aftigen wir uns mit Liftingfolgen und werden herausfinden,
dass die Folgenglieder in
Z/p
i
Z die reduzierte Gr¨obnerbasis in Q[x
1
, . . . , x
]
richtig approximieren.
Im abschließenden Kapitel 5 werden wir die Funktionsweise des Algorithmus
erkl¨
aren und ein Beispiel pr¨
asentieren.
2
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
2
Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
In diesem Kapitel befassen wir uns mit den grundlegenden Begriffen zur Theorie
der Gr¨
obnerbasen, die f¨
ur das weitere Verst¨
andnis dieser Arbeit von fundamen-
taler Bedeutung sind. Wir nehmen im Folgenden stets an, dass R ein Ring und
K ein K¨
orper sei.
2.1
Monomordnungen
Definition 1
(a) Sei = (
1
, . . . ,
)
N
0
. Dann heißt x
··= x
1
1
x
2
2
· · · x
ein Monom
in x
1
, . . . , x
.
(b) R[x
1
, . . . , x
]
··=
A
c
x
c
R, A N
n
0
,
|A| < heißt der Po-
lynomring
mit Variablen und Koeffizienten aus R.
(c) Sei f =
A
c
x
R[x
1
, . . . , x
]. Dann heißt c
der Koeffizient des
Monoms x
in f . Ist c
= 0, so heißt c
x
ein Term in f .
Definition 2
Eine Relation > auf
N
0
heißt Monomordnung, falls f¨
ur beliebige , ,
N
0
folgende Bedingungen gelten:
(a) Es gilt genau eine der folgenden Aussagen: > , > , = .
(b) Aus > folgt + > + .
(c) > ist eine Wohlordnung, d.h. jede nichtleere Teilmenge von
N
0
besitzt
ein kleinstes Element bzgl. >.
Bemerkung 3
(a) Die Vorschrift
- x
beschreibt eine Bijektion zwischen
N
0
und der
Menge aller Monome in x
1
, . . . , x
. Es l¨
asst sich also jedes
N
0
einein-
deutig mit einem Monom x
assoziieren.
(b) Ist > eine Monomordnung, so sagen wir auch x
> x
, falls > gilt.
Beispiel 4
Seien = (
1
, . . . ,
), = (
1
, . . . ,
)
N
0
und :
N
0
N
0
, (w
1
, . . . , w
)
i=1
w
i
.
(a) Dann heißt > bzgl. der lexikografischen Monomordnung mit
x
1
>
· · · > x
, falls
i
-
i
> 0 gilt, wobei i der kleinste Index mit
i
-
i
= 0 ist.
F¨
ur die lexikografische Monomordnung mit x > y > z gelten damit bei-
spielsweise xy
2
> y
3
z
4
und x
3
y
3
z
2
> x
3
y
2
z
4
.
3
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
(b) Wir nennen > bzgl. der standardgewichteten lexikografischen
Monomordnung
, falls entweder () > () oder () = () mit
> bzgl. der lexikografischen Monomordnung gilt.
F¨
ur die standardgewichtete lexikografische Monomordnung mit x > y > z
gelten damit zum Beispiel y
3
z
4
> xy
2
und x
3
y
3
z
2
> x
3
y
2
z
4
.
Im Folgenden sei > eine fest gew¨
ahlte Monomordnung.
Definition 5
Seien f, f
1
, . . . , f
s
nichttriviale Polynom in R[x
1
, . . . , x
], wobei f =
A
c
x
und F
R[x
1
, . . . , x
].
(a) M(f )
··= {x
| c
= 0
}.
(b) multideg(f )
··= max
A
heißt der Multigrad von f . In diesem Fall ist das
Maximum bzgl. der Monomordnung > gemeint.
(c) LC(f )
··= a
multideg(f )
heißt der Leitkoeffizient von f .
(d) LM(f )
··= x
multideg(f )
heißt das Leitmonom von f .
(e) LT(f )
··= LC(f) LM(f) = a
multideg(f )
x
multideg(f )
heißt der Leitterm von f .
(f) LM(F )
··= {LM(g) | g F, g = 0}.
(g) LT(F )
··= {LT(g) | g F, g = 0}.
Beispiel 6
Es sei > die lexikografische Monomordnung mit x > y > z und F = (f
1
, f
2
)
mit f
1
= 2xy
2
+ 3yz und f
2
= y
3
z
2
+ 4z
5
+ 1
Q[x, y]. Dann gelten folgende
Aussagen:
· M(f
1
) =
{xy
2
, yz
}, M(f
2
) =
{y
3
z
2
, z
5
, 1
}.
· multideg(f
1
) = (1, 2, 0).
· LC(f
1
) = 2, LM(f
1
) = xy
2
.
· LM(F ) = {LM(f
1
), LM(f
2
)
} = {xy
2
, y
3
z
2
}.
F¨
ur den Multigrad kann man leicht die folgenden Rechenregeln zeigen:
Proposition 7
Es seien f, g
R[x
1
, . . . , x
] mit f, g = 0. Dann gelten folgende Aussagen:
(a) multideg(f g) = multideg(f ) + multideg(g).
(b) Es gelte f +g = 0. Dann gilt multideg(f +g)
max{multideg(f), multideg(g)}.
4
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
2.2
Polynomreduktionen
Definition 8
Seien g, h, f
1
, . . . , f
s
R[x
1
, . . . , x
] und F = (f
1
, . . . , f
s
).
(a) g heißt reduzibel zu h bzgl. F , wenn ein k
{1, . . . , s}, c R mit c = 0
und ein Monom u existieren, sodass folgende Bedingungen gelten:
(i) c ist der Koeffizient des Monoms u
· LM(f
k
) in g.
(ii) LC(f
k
)
R
×
, d.h. LC(f
k
) ist eine Einheit in R.
(iii) h l¨
asst sich schreiben als
h = g
-
c
LC(f
k
)
· u · f
k
.
In diesem Fall schreiben wir g
-
-
F
h.
(b) g heißt nach endlich vielen Schritten reduzibel zu h bzgl. F , wenn
g = h gilt oder wenn es ein m
N und q
0
, . . . , q
m
R[x
1
, . . . , x
] gibt,
sodass
g = q
0
-
-
F
q
1
-
-
F
q
2
-
-
F
. . .
-
-
F
q
m
= h.
In diesem Fall schreiben wir g
-
-
F
h.
Bemerkung 9
Seien g, h, f
1
, . . . , f
s
R[x
1
, . . . , x
] und F = (f
1
, . . . , f
s
).
(a) Es gelte g
-
-
F
h. Dann gilt multideg(g)
multideg(u·f
k
), da LM(u
·f
k
) =
u
· LM(f
k
) ein Monom in g mit Koeffizient c = 0 ist. Mit Proposition 7 (b)
folgt damit außerdem multideg(g)
multideg(h).
(b) Die Relation
-
-
F
ist noethersch, d.h. jede Folge r
1
, r
2
, r
3
, . . . von Ele-
menten in R[x
1
, . . . , x
], sodass f¨
ur jedes i die Bedingung r
i
-
-
F
r
i+1
gilt,
ist endlich. Dies liegt daran, dass der Multigrad bei der Reduktion nicht
gr¨
oßer wird (siehe (a)) und dass die Monomordnung eine Wohlordnung
ist.
(c) Es gelte g
-
-
F
h. Dann liefert die Definitionsvorschrift ein m
N
0
und
:
{1, . . . , m} {1, . . . , s}, sodass
h = g
-
m
=1
c
LC(f
( )
)
· u · f
( )
,
wobei c
k
der Koeffizient des Monoms u
k
· LM f
(k)
in
F
k
··= g -
k-1
=1
c
LC(f
( )
)
· u · f
( )
5
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
ist. Wir definieren
a
k
··=
m
=1
( )=k
c
LC(f
( )
)
· u
und bezeichnen mit A
F
(g, h) die Menge aller Tupel (a
1
, . . . , a
s
), die wir
durch diese Vorschrift erhalten. Aufgrund dieser Konstruktion gilt f¨
ur je-
des a
A
F
(g, h) die Gleichung a
· F = g - h.
Da c
k
der Koeffizient des Monoms u
k
· LM f
(k)
in F
k
ist, folgt mit
Proposition 7 (b) außerdem, dass a
k
f
k
= 0 die Aussage multideg(a
k
f
k
)
multideg(g) impliziert.
Beispiel 10
Es seien F = (f
1
, f
2
) mit f
1
= y
2
- 1, f
2
= xy
- 1 R[x, y] und g = x
2
y +
xy
2
+ y
2
R[x, y]. Außerdem sei die lexikografische Monomordnung mit x > y
gew¨
ahlt.
Dann ist x
· LM(f
1
) = xy
2
ein Monom in g mit Koeffizient 1. Also gilt
g
-
-
F
q
1
··= g -
1
LC(f
1
)
· x · f
1
= x
2
y + x + y
2
.
Nun ist x
· LM(f
2
) = x
2
y ein Monom in q
1
mit Koeffizient 1. Also folgt
q
1
-
-
F
q
2
··= q
1
-
1
LC(f
2
)
· x · f
2
= 2x + y
2
.
Es ist außerdem LM(f
1
) = y
2
ein Monom in q
2
mit Koeffizient 1. Somit gilt
q
2
-
-
F
h
··= q
2
-
1
LC(f
1
)
· f
1
= 2x + 1.
Wir erhalten also g
-
-
F
h mit
h = g
-
1
LC(f
1
)
· x · f
1
-
1
LC(f
2
)
· x · f
2
-
1
LC(f
1
)
· f
1
= g
- (x + 1) · f
1
- x · f
2
,
also erhalten wir die Zerlegung g = (x + 1)
· f
1
+ x
· f
2
+ h und damit ist
(x + 1, x)
A
F
(g, h).
Man kann aber auch bei der Reduktion von g mit Polynomen aus F in einer
anderen Reihenfolge stattdessen g
-
-
F
~
h
··= x + y + 1 mit der Zerlegung g =
f
1
+ (x + y)
· f
2
+ ~
h erhalten, d.h. also (1, x + y)
A
F
(g, ~
h).
Definition 11
Sei g
R[x
1
, . . . , x
] und F ein endliches Tupel mit Eintr¨
agen aus R[x
1
, . . . , x
].
6
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
(a) Gibt es kein h
R[x
1
, . . . , x
], sodass g
-
-
F
h gilt, so heißt g irreduzibel
bzgl. F .
(b) Gilt g
-
-
F
h und h sei irreduzibel bzgl. F , so heißt h eine Normalform
von g bzgl. F .
Bemerkung 12
Jedes Polynom besitzt eine Normalform, da
-
-
F
eine noethersche Relation ist
(siehe Bemerkung 9 (b)). Jedoch gibt es im Allgemeinen keine eindeutige Nor-
malform (siehe Beispiel 14).
Der n¨
achste Satz gibt eine Charakterisierung f¨
ur die Irreduzibilit¨
at eines Poly-
noms an.
Satz 13
Sei g
R[x
1
, . . . , x
], F = (f
1
, . . . , f
s
) mit f
i
R[x
1
, . . . , x
] und LC(f
i
)
R
×
f¨
ur i = 1, . . . , s. Dann sind folgende Aussagen ¨
aquivalent:
(a) g ist irreduzibel bzgl. F.
(b) Kein Term von g liegt im von LT(F ) erzeugten Ideal.
Beweis
Beweis von
"¬
(b)
¬(a)"
Es sei ax
ein Term von g, der im von LT(F ) erzeugten Ideal liegt. Dann gibt
es ein f
k
F , c R mit c = 0 und ein Monom x
, sodass ax
= cx
· LT(f
k
)
gilt. Also ist a = c
· LC(f
k
) = 0 der Koeffizient des Monoms x
= x
· LM(f
k
)
in g. Setzt man h
··= g -
a
LC(f
k
)
· x
· f
k
, so gilt g
-
-
F
h, d.h. g ist reduzibel zu
h bzgl. F .
Beweis von
"¬
(a)
¬(b)"
Es sei g reduzibel zu h bzgl. F f¨
ur ein h
R[x
1
, . . . , x
]. Dann gibt es ein
f
k
F, c R mit c = 0 und ein Monom x
, sodass x
· LT(f
k
) einem Monom
in g mit Koeffizient c entspricht, d.h. cx
·LT(f
k
) ist ein Term in g. Dieser Term
in g liegt im von LT(F ) erzeugten Ideal.
Beispiel 14
Seien g = x
2
y + xy
2
+ y
2
und F = (y
2
-1, xy -1) wie im Beispiel 10. Wir haben
gezeigt, dass g
-
-
F
h und g
-
-
F
~
h gelten, wobei h = 2x + 1 und ~
h = x + y + 1.
Mit Satz 13 folgt, dass h und ~
h zwei verschiedene Normalformen von g bzgl. F
sind.
7
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
2.3
Gr¨
obnerbasen
Definition 15
Seien F, G endliche Tupel mit Eintr¨
agen aus K[x
1
, . . . , x
] und I ein Ideal mit
I = (G). Dann heißt G eine Gr¨
obnerbasis
von I, wenn g
-
-
G
0 f¨
ur alle
g
I gilt. Gilt zus¨atzlich I = (F ), so heißt G auch eine Gr¨obnerbasis von F .
Bemerkung 16
G ist also genau dann eine Gr¨
obnerbasis von F ist, wenn 0 das einzige bzgl. F
irreduzible Polynom in I ist.
Eine weitere Charakterisierung f¨
ur Gr¨
obnerbasen liefert der folgende Satz:
Satz 17
Seien F = (f
1
, . . . , f
s
) mit f
1
, . . . , f
s
K[x
1
, . . . , x
] und I
K[x
1
, . . . , x
] ein
Ideal mit I = (F ). Dann sind folgende Aussagen ¨
aquivalent:
(a) F ist eine Gr¨
obnerbasis von I.
(b) Es gilt (LT(I)) = (LT(F )).
Beweis
Beweis von
"¬
(b)
¬(a)"
Es sei (LT(I)) = (LT(F )). Dann existiert ein g
I, sodass LT(g) nicht in
(LT(F )) liegt. Damit ist jede Normalform von g bzgl. F nicht Null. Also ist F
keine Gr¨
obnerbasis von I.
Beweis von
"¬
(a)
¬(b)"
Es sei g
I, sodass jede Normalform von g bzgl. F ungleich Null ist. Sei r eine
solche Normalform. Da r ein bzgl. F irreduzibles Polynom in I ist, folgt mit
Satz 13, dass LT(r)
(LT(F )).
Beispiel 18
F¨
ur das folgende Beispiel sei die lexikografische Monomordnung mit x > y > z
gew¨
ahlt. Es sei F = (f
1
, f
2
, f
3
) mit f
1
, f
2
, f
3
K[x, y, z], wobei
f
1
= xz
2
- yz + y + z
2
,
f
2
=
-xz
2
+ y
2
,
f
3
=
-xy + xz - x - y.
Sei außerdem I
K[x, y, z] das von F erzeugte Ideal. Dann gilt. LT(f
1
) = xz
2
,
LT(f
2
) =
-xz
2
und LT(f
3
) =
-xy.
Wir betrachten f
1
+ f
2
= y
2
- yz + y + z
2
I und sehen, dass kein Term von
f
1
+ f
2
durch ein LT(f
k
) teilbar ist. Nach Satz 17 ist F also keine Gr¨
obnerbasis
von I.
8
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
Bemerkung 19
In [1] werden Gr¨
obnerbasen durch Aussage (b) aus Satz 17 definiert. Deshalb
werden wir im Laufe dieser Arbeit auch auf Aussagen aus [1] zur¨
uckgreifen.
2.4
S-Polynome
Nun werden wir uns mit den S-Polynomen befassen, die so so konstruiert sind,
dass diese f¨
ur das Ausl¨
oschen von Leittermen verantwortlich sind.
Definition 20
Seien f, g, g
1
, . . . , g
t
Polynome in R[x
1
, . . . , x
], deren Leitkoeffizienten Einheiten
in R sind.
(a) Seien multideg(f ) = , multideg(g) = und = (
1
, . . . ,
n
), wobei
i
= max
{
i
,
i
}. Dann heißt x
das kleinste gemeinsame Vielfache
von LM(f ) und LM(g) (Schreibweise: LCM(LM(f ), LM(g))
··= x
).
(b) Das Polynom
S(f, g)
··=
x
LT(f )
· f -
x
LT(g)
· g
heißt S-Polynom von f und g.
(c) Seien G = (g
1
, . . . , g
t
) und i, j
{1, . . . , t} Indizes mit i < j und es gelte
S(g
i
, g
j
)
-
-
G
0. Dann definieren wir
B
G
i,j
··= {a - m
i
e
i
+ m
j
e
j
| a A
G
(S(g
i
, g
j
), 0)
} , wobei
m
i
=
LCM(LM(g
i
), LM(g
j
))
LT(g
i
)
und
m
j
=
LCM(LM(g
i
), LM(g
j
))
LT(g
j
)
gelten und wir mit e
k
den k-ten Einheitsvektor bezeichnen.
Bemerkung 21
Seien g
1
, . . . , g
t
Polynome in R[x
1
, . . . , x
], deren Leitkoeffizienten Einheiten in
R sind, und G = (g
1
, . . . , g
t
).
(a) Aufgrund der Konstruktion von B
G
i,j
gilt f¨
ur jedes Element b
B
G
i,j
die
Bedingung b
· G = 0.
(b) Ist R = K ein K¨
orper, so besagt das Buchberger-Kriterium (siehe [1,
Seite 85, Theorem 6]), dass G genau dann eine Gr¨
obnerbasis ist, wenn
S(g
i
, g
j
)
-
-
G
0 f¨
ur alle Indizes i, j
{1, . . . , t} mit i < j gilt.
(c) Mit dem Buchberger-Algorithmus (siehe [1, Seite 90, Theorem 2]) kann
man f¨
ur ein endliches Tupel von Polynomen aus K[x
1
, . . . , x
] eine Gr¨
obner-
basis konstruieren.
9
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
Beispiel 22
F¨
ur das folgende Beispiel sei die lexikografische Monomordnung mit x > y > z
gew¨
ahlt. Sei G = (g
1
, g
2
, g
3
) mit g
1
, g
2
, g
3
K[x, y, z], wobei
g
1
= xy
- xz + x + y, g
2
= xz
2
- yz + y + z
2
,
g
3
= y
2
- yz + y + z
2
.
Dann gilt
S(g
1
, g
2
) = z
2
· g
1
- y · g
2
=
-xz
3
+ xz
2
+ y
2
z
- y
2
,
S(g
1
, g
3
) = y
· g
1
- x · g
3
=
-xz
2
+ y
2
,
S(g
2
, g
3
) = y
2
· g
2
- xz
2
· g
3
= xyz
3
- xyz
2
- xz
4
- y
3
z + y
3
+ y
2
z
2
.
Wir k¨
onnen zeigen, dass S(g
1
, g
2
), S(g
1
, g
3
), S(g
2
, g
3
)
-
-
G
0 gilt und die Reduk-
tionsvorschrift folgende Zerlegungen liefert:
S(g
1
, g
2
) = (
-z + 1) · g
2
+ (z
- 1) · g
3
,
S(g
1
, g
3
) =
-g
2
+ g
3
,
S(g
2
, g
3
) = (z
3
- z
2
)
· g
1
+ (
-2z - 1) · g
2
+ (
-yz + y + 2z - 1) · g
3
.
Also ist G nach dem Buchberger-Kriterium eine Gr¨
obnerbasis und es gilt a
i,j
A
G
(S(g
i
, g
j
), 0), wobei
a
1,2
··= (0, -z + 1, z - 1),
a
1,3
··= (0, -1, 1),
a
2,3
··= (z
3
- z
2
,
-2z + 1, -yz + y + 2z - 1)
sind. Dies liefert uns folgende Elemente s
i,j
B
G
i,j
, wobei
s
1,2
··= a
1,2
- z
2
e
1
+ y
· e
2
= (
-z
2
, y
- z + 1, z - 1),
s
1,3
··= a
1,3
- y · e
1
+ x
· e
3
= (
-y, -1, x + 1),
s
2,3
··= a
2,3
- y
2
e
2
+ xz
2
e
3
= (z
3
- z
2
,
-y
2
- 2z + 1, xz
2
- yz + y + 2z - 1).
Man kann leicht nachrechnen, dass s
i,j
· G = 0 gilt.
2.5
Transformations- und Syzygiematrizen
Im Folgenden werden wir eine Beschreibung von Gr¨
obnerbasen mithilfe von
Matrizen angeben.
Proposition 23
Seien F ein endliches Tupel mit Eintr¨
agen aus K[x
1
, . . . , x
] und G eine Gr¨
obner-
basis von F mit t Eintr¨
agen. Dann existieren Matrizen X, Y und R mit Eintr¨
agen
aus K[x
1
, . . . , x
], sodass G = X
·F , F = Y ·G, R·G = 0 und f¨ur je zwei Indizes
i, j
{1, . . . , t} mit i < j ein Zeilenvektor in R existiert, dass einem Element in
B
G
i,j
entspricht.
10
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
Beweis
Seien F = (f
1
, . . . , f
s
) und G = (g
1
, . . . , g
t
). Da F und G das gleiche Ideal
erzeugen, existieren q
i,j
, r
k,l
K[x
1
, . . . , x
], sodass f
i
= q
i,1
g
1
+
· · · + q
i,t
g
t
und g
k
= r
k,1
f
1
+
· · · + r
k,s
f
s
gelten. Seien X
··= (r
i,j
) und Y
··= (q
k,l
). Dann
gilt G = X
· F und F = Y · G. Die Existenz einer solchen Matrix R folgt aus
Bemerkung 21.
Definition 24
Seien F ein endliches Tupel mit Eintr¨
agen aus K[x
1
, . . . , x
] und G eine Gr¨
obner-
basis von F . Sind X, Y und R Matrizen mit Eintr¨
agen aus K[x
1
, . . . , x
], die
die Eigenschaften aus der Proposition 23 erf¨
ullen, dann heißen X, Y Transfor-
mationsmatrizen
und R Syzygiematrix von (F, G).
Die folgende Charakterisierung von Gr¨
obnerbasen unterscheidet sich minimal
vom Buchberger-Kriterium und wird an dieser Stelle lediglich zitiert:
Satz 25
Sei G = (g
1
, . . . , g
t
)
T
mit g
k
K[x
1
, . . . , x
]. Dann ist G genau dann ei-
ne Gr¨
obnerbasis, wenn f¨
ur alle Indizes i, j mit 1
i < j t Polynome
a
i,j
1
, . . . , a
i,j
t
K[x
1
, . . . , x
] existieren, sodass folgende Bedingungen gelten:
(a) S(g
i
, g
j
) = a
i,j
1
g
1
+
· · · + a
i,j
t
g
t
.
(b) a
i,j
k
g
k
= 0 impliziert multideg(a
i,j
k
g
k
)
multideg(S(g
i
, g
j
)).
Beweis
Siehe [1, Seite 104, Theorem 3].
Mit dem vorherigen Satz k¨
onnen wir nun Gr¨
obnerbasen anhand von Matrizen
charakterisieren, was der folgende Satz zeigt:
Satz 26
Sei G = (g
1
, . . . , g
t
)
T
mit g
k
K[x
1
, . . . , x
]. Dann sind folgende Aussagen
¨
aquivalent:
(a) G ist eine Gr¨
obnerbasis.
(b) Es existiert eine Matrix R mit Eintr¨
agen aus K[x
1
, . . . , x
] und Zeilen s
i,j
,
1
i < j t, mit folgenden Eigenschaften:
(i) R
· G = 0.
(ii) s
i,j
= a
i,j
- m
i
e
i
+ m
j
e
j
,
wobei a
i,j
= (a
i,j
1
, . . . , a
i,j
t
) mit a
i,j
k
K[x
1
, . . . , x
],
m
i
=
LCM(LM(g
i
), LM(g
j
))
LT(g
i
)
und
m
j
=
LCM(LM(g
i
), LM(g
j
))
LT(g
j
)
.
11
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
(iii) a
i,j
k
g
k
= 0 impliziert multideg(a
i,j
k
g
k
)
multideg(S(g
i
, g
j
)).
Beweis
Beweis von
"
(a)
(b)"
Sei G eine Gr¨
obnerbasis. Nach Satz 25 existieren f¨
ur alle Indizes i, j mit 1
i < j
t Polynome a
i,j
1
, . . . , a
i,j
t
K[x
1
, . . . , x
] existieren, sodass
· S(g
i
, g
j
) = a
i,j
1
g
1
+
· · · + a
i,j
t
g
t
,
· a
i,j
k
g
k
= 0 impliziert multideg(a
i,j
k
g
k
)
multideg(S(g
i
, g
j
)).
Definiere a
i,j
··= (a
i,j
1
, . . . , a
i,j
t
) und s
i,j
··= a - m
i
e
i
+ m
j
e
j
. Dann erf¨
ullt eine
Matrix R, die f¨
ur alle Indizes i, j mit 1
i < j t die Vektoren s
i,j
als Zeilen
enth¨
alt, offenbar die Bedingungen (i), (ii) und (iii).
Beweis von
"
(b)
(a)"
Sei R eine Matrix mit Eintr¨
agen aus K[x
1
, . . . , x
] und Zeilen s
i,j
, 1
i < j t,
die die Bedingungen (i), (ii) und (iii) erf¨
ullen. Die Bedingungen (i) und (ii)
implizieren
0 = a
i,j
1
g
1
+
· · · + a
i,j
t
g
t
- m
i
g
i
+ m
j
g
j
= a
i,j
1
g
1
+
· · · + a
i,j
t
g
t
- S(g
i
, g
j
)
und damit S(g
i
, g
j
) = a
i,j
1
g
1
+
· · · + a
i,j
t
g
t
. Zusammen mit Bedingung (iii) folgt
also, dass G gem¨
aß Satz 25 eine Gr¨
obnerbasis ist.
Bemerkung 27
(a) Eine Syzygiematrix erf¨
ullt die Bedingungen aus Satz 26.
(b) Definition 24 kann mit (a) wie folgt interpretiert werden:
· Die Transformationsmatrizen sind daf¨ur verantwortlich, dass F und
G das gleiche Ideal erzeugen.
· Die Syzygiematrix stellt sicher, dass G eine Gr¨obnerbasis darstellt.
Beispiel 28
Seien F, G wie in den Beispielen 18 und 22 gew¨
ahlt. Es sei > außerdem die
lexikografische Monomordnung mit x > y > z. Dann gelten G = X
·F , F = Y ·G
und R
· G = 0, wobei
X =
0
0
-1
1
0
0
1
1
0
, Y =
0
1
0
0
-1 1
-1
0
0
und
R =
-z
2
y
- z + 1
z
- 1
-y
-1
x + 1
z
3
- z
2
-y
2
- 2z + 1 xz
2
- yz + y + 2z - 1
.
12
2. Einf¨
uhrung in die Theorie der Gr¨
obnerbasen
sind. Wir sehen, dass die Zeilen der Matrix R genau die Elemente s
i,j
B
G
i,j
aus
Beispiel 22 sind. Mit Satz 26 folgt, dass G eine Gr¨
obnerbasis von F ist, X, Y
Tranformationsmatrizen und R eine Syzygiematrix von (F, G) sind.
2.6
Reduzierte Gr¨
obnerbasen
Aus Effizienzgr¨
unden ist es g¨
unstig, die Anzahl der Polynome einer Gr¨
obnerbasis
m¨
oglichst klein zu halten. Reduzierte Gr¨
obnerbasen sind in diesem Sinne die
idealen Gr¨
obnerbasen.
Definition 29
Eine Gr¨
obnerbasis G = (g
1
, . . . , g
n
) heißt reduziert, wenn f¨
ur alle k = 1, . . . , n
folgende Eigenschaften gelten:
(a) Es ist g
k
G irreduzibel bzgl. G \ {g
k
}.
(b) Es gilt LC(g
k
) = 1.
Aus dem folgenden Satz folgt die Existenz und Eindeutigkeit der reduzierten
Gr¨
obnerbasis.
Satz 30
Sei I
K[x
1
, . . . , x
] ein nichttriviales Ideal. Dann besitzt I genau eine redu-
zierte Gr¨
obnerbasis.
Beweis
Siehe [1, Seite 92, Proposition 6].
Beispiel 31
Wir w¨
ahlen die lexikografische Monomordnung mit x > y > z und betrachten
die Gr¨
obnerbasis G = (g
1
, g
2
, g
3
) aus Beispiel 22. Man kann leicht sehen, dass
kein Term von g
i
im von LT(G
\ {g
i
}) erzeugten Ideal liegt. Mit Satz 13 folgt
also, dass G eine reduzierte Gr¨
obnerbasis ist.
13
3. Gl¨
uckbringende Primzahlen
3
Gl¨
uckbringende Primzahlen
In diesem Kapitel werden wir uns mit gl¨
uckbringenden Primzahlen p besch¨
afti-
gen, die f¨
ur den Informationserhalt beim ¨
Ubergang der reduzierten Gr¨
obnerbasis
G in
Q[x
1
, . . . , x
] nach
F
p
[x
1
, . . . , x
] verantwortlich sind.
Definition 32
Seien m
N und p eine Primzahl.
(a)
Z
(p)
··=
q
r
q, r
Z, p r .
(b)
Z
m
··= Z/mZ.
F¨
ur
Z
(p)
kann man leicht die folgenden Eigenschaften zeigen:
Proposition 33
Sei p eine Primzahl. Dann ist
Z
(p)
Q ist ein Ring und die Menge der Einheiten
von
Z
(p)
ist
Z
×
(p)
=
q
r
q, r
Z, p q, r .
Definition 34
Seien F ein endliches Tupel mit Eintr¨
agen aus
Q[x
1
, . . . , x
], G die reduzierte
Gr¨
obnerbasis von F und p eine Primzahl. Dann heißt p gl¨
uckbringend
f¨
ur
F , falls es Transformationsmatrizen X, Y und eine Syzygiematrix R von (F, G)
gibt, sodass F, G, X, Y, R jeweils Matrizen mit Eintr¨
agen aus
Z
×
(p)
[x
1
, . . . , x
]
sind.
Der folgende Satz beschreibt, wie sich im Falle einer gl¨
uckbringenden Primzahl
die reduzierten Gr¨
obnerbasen in
Q[x
1
, . . . , x
] und
F
p
[x
1
, . . . , x
] zueinander
verhalten.
Satz 35
Sei F = (f
1
, . . . , f
s
) mit f
i
Q[x
1
, . . . , x
], G = (g
1
, . . . , g
t
) die reduzierte
Gr¨
obnerbasis von F in
Q[x
1
, . . . , x
]. Außerdem sei p eine f¨
ur F gl¨
uckbringende
Primzahl. Dann ist G (mod p) die reduzierte Gr¨
obnerbasis von F (mod p) in
F
p
[x
1
, . . . , x
].
Beweis
Da p eine f¨
ur F gl¨
uckbringende Primzahl ist, existieren Transformationsatrizen
X, Y und eine Syzygiematrix R von (F, G) mit Eintr¨
agen aus
Z
×
(p)
[x
1
, . . . , x
].
Dann existieren die Matrizen ¯
F
··= F (mod p), ¯G ··= G (mod p), ¯
X
··= X
(mod p), ¯
Y
··= Y (mod p) und ¯R ··= R (mod p) in F
p
[x
1
, . . . , x
].
Da X und Y Transformationsatrizen von (F, G) sind, gelten G = X
· F und
F = Y
· G. Damit gelten in F
p
[x
1
, . . . , x
] die entsprechenden Gleichungen ¯
G =
¯
X
· ¯
F und ¯
F = ¯
Y
· ¯
G, d.h. ¯
F und ¯
G erzeugen das gleiche Ideal in
F
p
[x
1
, . . . , x
].
14
3. Gl¨
uckbringende Primzahlen
Da R eine Syzygiematrix ist, gilt R
· G = 0, somit auch ¯
R
· ¯
G = 0 und die
Zeilen von R entsprechen den Elementen aus B
G
i,j
, d.h. sie haben die Form
s
i,j
··= a
i,j
- m
i
g
i
+ m
j
g
j
mit a
i,j
= (a
i,j
1
, . . . , a
i,j
t
)
A
G
(S(g
i
, g
j
), 0) und
m
i
, m
j
wie in Bemerkung 21. Wegen a
i,j
A
G
(S(g
i
, g
j
), 0) l¨
asst sich S(g
i
, g
j
)
schreiben als
S(g
i
, g
j
) =
m
=1
c
LC(g
( )
)
· u · g
( )
,
sodass folgende Aussagen gelten (vgl. Bemerkung 9 (c)):
· c
k
ist der Koeffizient des Monoms u
k
· LM g
(k)
in
F
k
··= S(g
i
, g
j
)
-
k-1
=1
c
LC(g
( )
)
· u · g
( )
.
· Es ist
a
i,j
k
=
m
=1
( )=k
c
LC(g
( )
)
· u .
Wir wollen nun zeigen, dass c
Z
(p)
f¨
ur alle
= 1, . . . , m gilt. Dies wollen wir
per Indunktion nach m beweisen.
Induktionsanfang (m = 1)
Weil p f¨
ur F gl¨
uckbringend ist, gilt g
i
, g
j
Z
(p)
[x
1
, . . . , x
]. Daraus folgt F
1
=
S(g
i
, g
j
)
Z
(p)
[x
1
, . . . , x
]. Da außerdem c
1
einem Koeffizienten in S(g
i
, g
j
)
entspricht, folgt also c
1
Z
(p)
.
Induktionsschritt (m
m + 1)
Nach der Induktionshypothese gilt c
1
, . . . , c
m
Z
(p)
. Wir haben auch festge-
stellt, dass S(g
i
, g
j
)
Z
(p)
[x
1
, . . . , x
] gilt. Damit folgt also F
m+1
Z
(p)
[x
1
, . . . , x
].
Da c
m+1
ein Koeffizient in F
m+1
ist, folgt schließlich c
m+1
Z
(p)
.
Mit dieser Behauptung erhalten wir in
F
p
[x
1
, . . . , x
] die entsprechende Glei-
chung
S(¯
g
i
, ¯
g
j
) =
m
=1
¯
c
LC(¯
g
( )
)
· u · ¯g
( )
,
sodass folgende Aussagen gelten:
· ¯c
k
ist der Koeffizient des Monoms u
k
· LM ¯g
(k)
in
¯
F
k
··= S(¯g
i
, ¯
g
j
)
-
k-1
=1
¯
c
LC(¯
g
( )
)
· u · ¯g
( )
.
15
3. Gl¨
uckbringende Primzahlen
· Es ist
¯
a
i,j
k
=
m
=1
( )=k
¯
c
LC(¯
g
( )
)
· u .
Da ¯
c
k
der Koeffizient des Monoms u
k
· LM ¯g
(k)
in ¯
F
k
ist, folgt mit Propo-
sition 7 (b), dass ¯
a
i,j
k
¯
g
k
= 0 die Aussage multideg(¯
a
i,j
k
¯
g
k
)
multideg(S(¯g
i
, ¯
g
j
))
impliziert.
Es sind zudem ¯
s
i,j
= ¯
a
i,j
- ¯
m
i
¯
g
i
+ ¯
m
j
¯
g
j
die Zeilen der Matrix ¯
R in
F
p
[x
1
, . . . , x
],
wobei
¯
m
i
=
LCM(LM(¯
g
i
), LM(¯
g
j
))
LT(¯
g
i
)
und
¯
m
j
=
LCM(LM(¯
g
i
), LM(¯
g
j
))
LT(¯
g
j
)
gilt.
1
Mit Satz 26 folgt schließlich, dass ¯
G = (¯
g
1
, . . . , ¯
g
t
) die reduzierte Gr¨
obner-
basis von ¯
F ist.
Bemerkung 36
Sei F ein endliches Tupel mit Eintr¨
agen aus
Q[x
1
, . . . , x
] und G die reduzier-
te Gr¨
obnerbasis von F . Seien außerdem X, Y Transformationsmatrizen und R
eine Syzygiematrix von (F, G). Dann gibt es nur endlich viele Primzahlen p,
sodass mindestens eine der Matrizen F, G, X, Y, R keine Matrix mit Eintr¨
agen
aus
Z
×
(p)
[x
1
, . . . , x
] ist. Das liegt daran, dass es insgesamt nur endlich viele
Matrixeintr¨
age, damit nur endlich viele Koeffizienten in den Polynomen und
aufgrund der Primfaktorzerlegung auch nur endlich viele Primfaktoren in den
Koeffizienten gibt. Also sind fast alle Primzahlen f¨
ur F gl¨
uckbringend.
Beispiel 37
F¨
ur dieses Beispiel sei die standardgewichtete lexikografische Monomordnung
mit x < y gew¨
ahlt und F = (x
2
+ 9x
2
- y, xy + 4x
2
+ 3x)
Q[x, y]
2
. Dann ist
G =
x
3
-
3
2
x
2
+
1
4
y
y
2
- 16x
2
+ 3y
- 12x
xy + 4x
2
+ 3x
die reduzierte Gr¨
obnerbasis von F mit Transformationsmatrizen
X =
-
1
4
1
4
x
-y - 4x - 3 xy + 9x - 4
,
Y =
-4 0 x
0
0
1
und Syzygiematrix
R =
-y
2
+ 16x
2
+ 24x + 9
x
3
+
1
4
y
-
3
4
-
3
2
xy + 3x
2
+
9
2
x
- 3
-y - 4x - 3
1
4
x
2
-
3
2
x + 1
0
-x
y
- 4x
.
1
Wir haben sogar gezeigt, dass ¯
R eine Syzygiematrix ist.
16
3. Gl¨
uckbringende Primzahlen
Wir bemerken, dass F, G, X, Y, R jeweils Matrizen mit Eintr¨
agen aus
Z
×
(5)
[x, y]
sind. Also ist 5 eine f¨
ur F gl¨
uckbringende Primzahl und die reduzierte Gr¨
obner-
basis von
¯
F = F
(mod 5) =
x
2
y + 4x
2
+ 4y
xy + 4x
2
+ 3x
F
5
[x, y]
2
ist nach dem Satz 35 gegeben durch
¯
G = G
(mod 5) =
x
3
+ x
2
+ 4y
y
2
+ 4x
2
+ 3y + 3x
xy + 4x
2
+ 3x
.
Anhand des Beweises von Satz 35 sieht man auch, dass
¯
X = X
(mod 5) =
1
4x
4y + x + 2
xy + 4x + 1
,
¯
Y = Y
(mod 5) =
1
0
x
0
0
1
Transformationsmatrizen und
¯
R = R
(mod 5) =
4y
2
+ x
2
+ 4x + 4
x
3
+ 4y + 3
xy + 3x
2
+ 2x + 2
4y + x + 2
4
x
2
+ x + 1
0
4x
y + x
eine Syzygiematrix von ( ¯
F , ¯
G) sind.
17
4. Lifting von Gr¨
obnerbasen
4
Lifting von Gr¨
obnerbasen
In diesem Abschnitt werden wir uns mit Liftingfolgen und ihren Eigenschaften
besch¨
aftigen. Die Hauptresultate in diesem Kapitel sind die Existenz (Satz 41)
und Eindeutigkeit (Satz 44) geeigneter Liftingfolgen, die eine richtige L¨
osung
des Gleichungssystems in Kapitel 5 garantiert.
Definition 38
Sei A eine Matrix mit Eintr¨
agen aus
Z
p
i
[x
1
, . . . , x
]. Dann heißt eine Matrix
~
A mit Eintr¨
agen aus
Z
p
i+1
[x
1
, . . . , x
] ein Lift von A nach
Z
p
i+1
, falls A
~
A
(mod p
i
).
Definition 39
Sei F
Q[x
1
, . . . , x
]
m
, p eine f¨
ur F gl¨
uckbringende Primzahl. Außerdem seien
G
(0)
F
p
[x
1
, . . . , x
]
n
die reduzierte Gr¨
obnerbasis von ¯
F
··= F (mod p), Y
(0)
eine Transformationsmatrix mit Y
(0)
· G
(0)
F (mod p) und R
(0)
eine Syzy-
giematrix von ( ¯
F , G
(0)
). Seien weiter t
N und G
(i)
, Y
(i)
, R
(i)
Matrizen mit
Eintr¨
agen in
Z
p
i+1
[x
1
, . . . , x
].
(a) Dann heißt heißt L = (G
(i)
, Y
(i)
, R
(i)
)
0
i<t
eine Liftingfolge von F
modulo p, falls f¨
ur alle i = 1, . . . , t folgende Bedingungen erf¨
ullt sind:
(i) Es ist
Y
(i-1)
· G
(i-1)
F, R
(i-1)
· G
(i-1)
0 (mod p
i
).
(ii) F¨
ur i > 1 gilt
G
(i-1)
G
(i-2)
,
Y
(i-1)
Y
(i-2)
,
R
(i-1)
R
(i-2)
(mod p
i-1
).
(iii) Die Eintr¨
age von G
(i-1)
= g
(i-1)
1
, . . . , g
(i-1)
n
sind normiert, d.h.
LC(g
(i-1)
k
) = 1 f¨
ur k = 1, . . . , n.
(iv) F¨
ur i > 1 und k = 1, . . . , n gilt LM(g
(i-1)
k
) = LM(g
(i-2)
k
).
(b) F¨
ur 0
j < t heißt eine Liftingfolge L = (G
(i)
, Y
(i)
, R
(i)
)
0
i<t
zu j
hochreduzierend
, wenn f¨
ur alle i = 0, . . . , j und r, s mit 1
r < s n
eine Zeile von R
(i)
existiert, die einem Element aus B
G
(i)
r,s
entspricht.
Das folgende Lemma werden wir sp¨
ater in einigen S¨
atzen verwenden:
Lemma 40
Es sei G = (g
1
, . . . , g
n
) eine reduzierte Gr¨
obnerbasis in
Q[x
1
, . . . , x
], p eine f¨
ur
G gl¨
uckbringende Primzahl und G
(0)
= (g
(0)
1
, . . . , g
(0)
n
) die reduzierte Gr¨
obner-
basis von G in
F
p
[x
1
, . . . , x
]. Außerdem sei h
(G) Z
(p)
[x
1
, . . . , x
] und
i
N, sodass jeder Koeffizient von h ein Vielfaches von p
i-1
ist. Dann ist
h
p
i-1
G
(0)
.
18
4. Lifting von Gr¨
obnerbasen
Beweis
Da jeder Koeffizient von h ein Vielfaches von p
i-1
ist, existiert ein Polynom
q
Z
(p)
[x
1
, . . . , x
] mit h = p
i-1
·q und damit
h
p
i-1
q (mod p). Es ist q (G),
weil h
(G) gilt. Nun folgt somit außerdem q
-
-
G
0, da G eine Gr¨
obnerbasis
ist. Die Reduktionsvorschrift liefert uns Polynome a
1
, . . . , a
n
Z
(p)
[x
1
, . . . , x
],
sodass q = a
1
g
1
+ . . . , a
n
g
n
(vgl. Induktionsbeweis von Satz 35). Damit folgt
in
F
p
[x
1
, . . . , x
] die Gleichung ¯
q = ¯
a
1
g
(0)
1
+ . . . , ¯
a
n
g
(0)
n
, wobei ¯
q
··= q (mod p)
und ¯
a
k
··= a
k
(mod p). Also folgt ¯
q
(G
(0)
) und wegen
h
p
i-1
q (mod p) auch
h
p
i-1
(G
(0)
).
Der folgende Satz besagt, dass es eine Liftingfolge gibt, die die reduzierte Gr¨
obner-
basis G in
Q[x
1
, . . . , x
] richtig approximiert und in den Folgengliedern G
(i)
keine neuen Monome auftreten oder verloren gehen.
Satz 41
Seien F
Q[x
1
, . . . , x
]
m
, p eine f¨
ur F gl¨
uckbringende Primzahl und G
Q[x
1
, . . . , x
]
n
die reduzierte Gr¨
obnerbasis von F . Es seien außerdem G
(0)
F
p
[x
1
, . . . , x
]
n
die reduzierte Gr¨
obnerbasis von ¯
F
··= F (mod p), Y
(0)
eine
Transformationsmatrix mit Y
(0)
· G
(0)
F (mod p) und R
(0)
eine Syzygie-
matrix von ( ¯
F , G
(0)
). Dann existiert f¨
ur jedes i
N und j = 1, . . . , i Matrizen
G
(j-1)
, Y
(j-1)
, R
(j-1)
mit Eintr¨
agen aus
Z
p
j
[x
1
, . . . , x
], sodass folgende Aus-
sagen gelten:
(a) L = (G
(j)
, Y
(j)
, R
(j)
)
0
j<i
ist eine Liftingfolge von F modulo p.
(b) Es ist G
(j-1)
= G (mod p
j
) f¨
ur alle j = 1, . . . , i.
(c) F¨
ur alle j = 2, . . . , i und k = 1, . . . , n gilt M(g
(j-1)
k
) = M(g
(j-2)
k
).
Beweis
Da die Teilaussagen (b) und (c) bereits ein paar Bedingungen f¨
ur die Definition
von Liftingfolgen erf¨
ullen, m¨
ussen wir f¨
ur (a) nur noch folgende Aussagen zeigen:
(a-i) Es gilt
Y
(j-1)
· G
(j-1)
F, R
(j-1)
· G
(j-1)
0 (mod p
j
).
(a-ii) F¨
ur alle j = 2, . . . , i gilt
Y
(j-1)
Y
(j-2)
, R
(j-1)
R
(j-2)
(mod p
j-1
).
Wir beweisen die Aussagen per Induktion nach i.
19
4. Lifting von Gr¨
obnerbasen
Induktionsanfang (i = 1)
Die Aussagen (a-ii) und (c) muss man f¨
ur den Fall i = 1 nicht ber¨
ucksichtigen.
Die Aussage (a-i) gilt bereits nach Voraussetzung , d.h. es folgt (a). Mit Satz 35
folgt außerdem Aussage (b).
Induktionsschritt (i
- 1 i)
F¨
ur i
-1 und j = 1, . . . , i-1 existieren gem¨aß der Induktionshypothese Matrizen
G
(j-1)
, Y
(j-1)
, R
(j-1)
mit Eintr¨
agen aus
Z
p
j
[x
1
, . . . , x
], sodass die Aussagen
(a) bis (c) gelten.
Wir definieren zun¨
achst G
(i)
··= G (mod p
i+1
). Damit folgt bereits Aussage (b)
und mit der Induktionshypothese auch (c).
Als N¨
achstes wollen wir Matrizen Y
(i-1)
, R
(i-1)
finden, die die Bedingungen
(a-i) und (a-ii) erf¨
ullen. Seien dazu ~
Y
(i-2)
und ~
R
(i-2)
Lifts von Y
(i-2)
und
R
(i-2)
nach
Z
p
i
. Die Aussage (a-ii) verlangt also, dass wir Matrizen Y , R mit
Eintr¨
agen aus
F
p
[x
1
, . . . , x
] finden m¨
ussen, sodass
Y
(i-1)
= ~
Y
(i-2)
+ p
i-1
· Y
und
R
(i-1)
= ~
R
(i-2)
+ p
i-1
· R
gelten. Die erste Gleichung in der Bedingung (a-i) verlangt, dass Y die Glei-
chung
F
Y
(i-1)
· G
(i-1)
~
Y
(i-2)
· G
(i-1)
+ p
i-1
· Y · G
(i-1)
(mod p
i
)
erf¨
ullen muss. Diese Gleichung ist ¨
aquivalent zu
F
- ~
Y
(i-2)
· G
(i-1)
p
i-1
· Y · G
(i-1)
(mod p
i
).
(1)
Mit Bedingung (c) f¨
ur i
- 1 kann man den Term auf der rechten Seite der
Gleichung (1) umschreiben zu
p
i-1
· Y · G
(i-2)
p
i-1
· Y · G
(0)
(mod p
i
)
Die linke Seite der Gleichung (1) entspricht aufgrund der Bedingung (c) f¨
ur i
-1
hingegen einem Tupel h
(i-1)
1
, . . . , h
(i-1)
m
T
, wobei
h
(i-1)
k
= h
k
(mod p
i
) und h
k
(G) Z
(p)
[x
1
, . . . , x
].
Mit Bedingung (a) f¨
ur i
- 1 folgt, dass die linke Seite der Gleichung (1) und
damit auch die Koeffizienten der Polynome h
k
Vielfache von p
i-1
sind. Somit
folgt einerseits mit Lemma 40, dass h
(i-1)
k
/p
i-1
(G
(0)
) gilt. Andererseits l¨
asst
sich die Gleichung (1) mit diesem Argument vereinfachen zu
1
p
i-1
·
h
(i-1)
1
..
.
h
(i-1)
m
Y · G
(0)
(mod p).
20
4. Lifting von Gr¨
obnerbasen
Da h
(i-1)
k
/p
i-1
(G
(0)
) gilt, ist h
(i-1)
k
/p
i-1
nach endlich vielen Schritten re-
duzibel zu 0 bzgl. G
(0)
. Dann erf¨
ullt Y unsere gesuchten Anforderungen, wenn
man die Elemente aus A
G
(0)
h
(i-1)
k
/p
i-1
, 0 als Zeilen f¨
ur Y w¨
ahlt.
Nun wollen wir unsere Matrix R berechnen. Wegen der zweiten Gleichung in
Bedingung (a) muss R die Gleichung
0
R
(i-1)
· G
(i-1)
~
R
(i-2)
· G
(i-1)
+ p
i-1
· R · G
(i-1)
(mod p
i
)
erf¨
ullen. Stellen wir diese Gleichung um, erhalten wir
~
R
(i-2)
· G
(i-1)
-p
i-1
· R · G
(i-1)
(mod p
i
).
(2)
Mit den gleichen Argumenten wie bei der Bestimmung von Y
l¨
asst sich die
Gleichung (2) umschreiben zu
1
p
i-1
·
r
(i-1)
1
..
.
r
(i-1)
l
-R · G
(0)
(mod p),
wobei r
(i-1)
k
/p
i-1
(G
(0)
) ist. Damit k¨
onnen wir f¨
ur R die Matrix w¨
ahlen, die
die Elemente aus A
G
(0)
- r
(i-1)
k
/p
i-1
, 0 als Zeilen enth¨
alt.
Bemerkung 42
Sei ~
G
(i-2)
ein Lift von G
(i-2)
nach
Z
p
i
und G eine Matrix mit Eintr¨
agen aus
F
p
[x
1
, . . . , x
], sodass G
(i-1)
= ~
G
(i-2)
+ p
i-1
· G = G (mod p
i
). Aus dem
Beweis beobachten wir, dass G , Y , R , die die Matrizen G
(i-1)
, Y
(i-1)
, R
(i-1)
bestimmen, die Gleichungen
G
(0)
· Y + Y
(0)
· G
1
p
i-1
· (F - ~
Y
(i-2)
· ~
G
(i-2)
)
(mod p)
G
(0)
· R + R
(0)
· G
1
p
i-1
· (- ~
R
(i-2)
· ~
G
(i-2)
)
(mod p)
erf¨
ullen.
Beispiel 43
Wir setzen das Beispiel 37 fort und setzen G
(0)
··= ¯G, Y
(0)
··= ¯Y und R
(0)
··= ¯R.
Nun wollen wir Matrizen G
(1)
, Y
(1)
und R
(1)
finden, sodass die Bedingungen
aus Satz 41 gelten.
Wir definieren
G
(1)
··= G (mod 5
2
) =
x
3
+ 11x
2
+ 19y
y
2
+ 9x
2
+ 3y + 13x
xy + 4x
2
+ 3x
.
21
4. Lifting von Gr¨
obnerbasen
W¨
ahlen wir
~
Y
(0)
=
1
0
x
0
0
1
als Lift von Y
(0)
nach
Z
25
und werten den Ausdruck auf der linken Seite der
Gleichung (1) aus, so erhalten wir
F
- ~
Y
(0)
· G
(1)
5 · -
x
3
- x
2
- 4y
0
= 5
·
h
1
h
2
(mod 25).
Die Polynome h
1
, h
2
F
5
[x, y] sind nach dem Beweis reduzibel bzgl. G
(0)
. Nun
berechnen wir (
-1, 0, 0) A
G
(0)
(h
1
, 0) und (0, 0, 0)
A
G
(0)
(h
2
, 0). Setzen wir
Y
··= -
1
0
0
0
0
0
,
so erhalten wir schließlich
Y
(1)
··= Y
(0)
+ 5
· Y = -
4
0
x
0
0
1
.
W¨
ahlen wir
~
R
(0)
=
4y
2
+ x
2
+ 4x + 4
x
3
+ 4y + 3
xy + 3x
2
+ 2x + 2
4y + x + 2
4
x
2
+ x + 1
0
4x
y + x
als Lift von R
(0)
nach
Z
25
, so kann man auf analoge Weise mit Gleichung (2)
R =
2x
2
+ 2
-y
-x
2
y
- x
3
+ xy + 2x
2
+ x + 2
-2x + 2 -1
-x
2
+ x
- 1
0
0
-y - 2x
bestimmen und erh¨
alt schließlich
R
(1)
··= R
(0)
+ 5
· R
=
4y
2
+ 11x
2
+ 4x + 14
x
3
- y + 3 -5x
2
y
- 5x
3
+ 6xy + 13x
2
+ 7x + 12
4y
- 9x + 12
-1
-4x
2
+ 6x
- 4
0
4x
-4y - 9x
.
Man kann leicht nachpr¨
ufen, dass (G
(0)
, Y
(0)
, R
(0)
), (G
(1)
, Y
(1)
, R
(1)
) eine Lif-
tingfolge von F modulo 5 darstellt.
Nun werden wir beweisen, dass die Folgenglieder G
(i)
einer Liftingfolge die ge-
suchte reduzierte Gr¨
obnerbasis G tats¨
achlich korrekt ann¨
ahern. Die folgenden
Beweise sind aufgrund der Tatsache, dass wir uns nur mit Gr¨
obnerbasen in Poly-
nomringen ¨
uber K¨
orpern (und nicht ¨
uber Ringe) befasst haben, sehr technisch.
22
4. Lifting von Gr¨
obnerbasen
Satz 44
Seien F
Q[x
1
, . . . , x
]
m
, G
Q[x
1
, . . . , x
]
n
die reduzierte Gr¨
obnerbasis
von F , p eine f¨
ur F gl¨
uckbringende Primzahl und i
0. Es seien außerdem
L = (G
(j)
, Y
(j)
, R
(j)
)
0
j<i+1
eine Liftingfolge von F modulo p und G
(j)
=
g
(j)
1
, . . . , g
(j)
n
. Dann gelten folgende Aussagen:
(a) Es gilt S g
(i)
r
, g
(i)
s
---
G
(i)
0 f¨
ur alle Indizes r, s mit 1
r < s n.
(b) Jedes Polynom h
G
(i)
Z
p
i+1
[x
1
, . . . , x
] ist reduzibel bzgl. G
(i)
.
(c) F (mod p
i+1
) und G
(i)
erzeugen das gleiche Ideal in
Z
p
i+1
[x
1
, . . . , x
].
(d) G
(i)
= G (mod p
i+1
).
Beweis
(a) Ist L eine zu i hochreduzierende Liftingfolge, so folgt f¨
ur alle Indizes r, s
mit 1
r < s n insbesondere B
G
(i)
r,s
=
, also auch S g
(i)
r
, g
(i)
s
---
G
(i)
0.
Falls L nicht zu i hochreduzierend ist, so sei j der kleinste Index mit
1
j i, sodass keine Zeile von R
(j)
einem Element von B
G
(j)
r,s
entspricht,
wobei r, s zwei Indizes mit 1
r < s n sind.
Seien r, s mit 1
r < s n. Dann gibt es ein N, sodass die -te Zeile
in R
(j-1)
einem Element B
G
(j-1)
r,s
entspricht, also einem Element der Form
a
(j-1)
r,s
- m
r
e
r
+ m
s
e
s
, wobei a
(j-1)
r,s
= (a
(j-1)
r,s,1
, . . . , a
(j-1)
r,s,n
) ein Element in
A
G
(j-1)
S(g
(j-1)
r
, g
(j-1)
s
), 0 ist,
m
r
=
LCM LM(g
(j-1)
r
), LM(g
(j-1)
s
)
LT(g
(j-1)
r
)
,
m
s
=
LCM(LM(g
(j-1)
r
), LM(g
(j-1)
s
))
LT(g
(j-1)
s
)
.
Weiter sind die Eintr¨
age von a
(j-1)
r,s
von der Form
a
(j-1)
r,s,k
=
d
=1
( )=k
c
(j-1)
LC g
(j-1)
( )
· u ,
sodass
S g
(j-1)
r
, g
(j-1)
s
=
d
=1
c
(j-1)
LC g
(j-1)
( )
· u · g
(j-1)
( )
und c
(j-1)
k
der Koeffizient des Monoms u
k
· LM(g
(j-1)
(k)
) in
Q
(j-1)
k
··= S g
(j-1)
r
, g
(j-1)
s
-
k-1
=1
c
(j-1)
LC g
(j-1)
( )
· u · g
(j-1)
( )
23
4. Lifting von Gr¨
obnerbasen
ist. Da L eine Liftingfolge ist, gilt LT(g
(j-1)
k
) = LT(g
(j)
k
) und damit folgen
insbesondere
m
r
=
LCM LM(g
(j)
r
), LM(g
(j)
s
)
LT(g
(j)
r
)
,
m
s
=
LCM(LM(g
(j)
r
), LM(g
(j)
s
))
LT(g
(j)
s
)
,
Es gelten außerdem
· S(g
(j)
r
, g
(j)
s
)
S(g
(j-1)
r
, g
(j-1)
s
) (mod p
j
),
· M S(g
(j-1)
r
, g
(j-1)
s
)
M S(g
(j)
r
, g
(j)
s
) ,
d.h. jedes Monom in S(g
(j-1)
r
, g
(j-1)
s
) tritt auch in S(g
(j)
r
, g
(j)
s
) auf.
Also ist auch u
1
· LM(g
(j)
(1)
) ein Monom in S(g
(j)
r
, g
(j)
s
) mit einem Koeffizi-
enten kongruent zu c
(j-1)
1
modulo p
j
, den wir mit c
(j)
1
bezeichnen. Weiter
ist auch u
2
· LM(g
(j)
(2)
) ein Monom in
S(g
(j)
r
, g
(j)
s
)
-
c
(j)
1
LC(g
(j)
(1)
)
· u
1
· g
(j)
(1)
,
mit einem Koeffizienten kongruent zu c
(j-1)
2
modulo p
j
, den wir c
(j)
2
nen-
nen. Diesen Vorgang k¨
onnen wir induktiv fortsetzen und erhalten damit
Koeffizienten c
(j)
k
, sodass c
(j)
k
c
(j-1)
k
(mod p
j
) und c
(j)
k
der Koeffizient
des Monoms u
k
· LM(g
(j)
(k)
) in
Q
(j)
k
··= S g
(j)
r
, g
(j)
s
-
k-1
=1
c
(j)
LC g
(j)
( )
· u · g
(j)
( )
ist. Es ist insbesondere Q
(j)
d+1
Q
(j-1)
d+1
= 0 (mod p
j
), d.h. Q
(j)
d+1
=
-p
j
·h
f¨
ur ein h
F
p
[x
1
, . . . , x
].
Definieren wir nun
a
(j)
r,s,k
··=
d
=1
( )=k
c
(j)
LC g
(j)
( )
· u ,
und a
(j)
r,s
··= (a
(j)
r,s,1
, . . . , a
(j)
r,s,n
), so folgt auch a
(j)
r,s
a
(j-1)
r,s
(mod p
j
).
Sei nun ^
R die Matrix, dessen -te Zeilen gleich a
(j)
r,s
- m
r
e
r
+ m
s
e
s
f¨
ur
1
r < s n sind. Da ^
R
(j)
R
(j-1)
R
(j)
(mod p
j
) gilt, existiert eine
Matrix R mit Eintr¨
agen aus
F
p
[x
1
, . . . , x
], sodass
^
R
(j)
= R
(j)
- p
j
· R
(3)
24
4. Lifting von Gr¨
obnerbasen
Multiplizieren wir Gleichung (3) mit G
(j)
von rechts, so folgt wegen R
(j)
·
G
(j)
0 (mod p
j+1
) die Gleichung
p
j
· h -p
j
· R · G
(j)
-p
j
· R · G
(0)
(mod p
j+1
),
die ¨
aquivalent ist zur Gleichung
h
-R · G
(0)
(mod p).
Daraus folgt, dass h
k
G
(0)
gilt f¨
ur k = 1, . . . , l, d.h. die Polynome h
k
sind nach endlich vielen Schritten reduzibel zu 0 bzgl. G
(0)
. Sei nun ¯
R
eine Matrix, sodass zu jedem 1
k l eine Zeile von ¯
R existiert, sodass
diese einem Element aus A
G
(0)
(
-h
k
, 0) entspricht. Dann gilt h
- ¯
R
·G
(0)
(mod p). Es sei S
(j)
··= R - ¯R . Dann folgt
S
(j)
· G
(0)
R · G
(0)
- ¯
R
· G
(0)
-h + h 0 (mod p).
(4)
Definieren wir ¯
R
(j)
··= R
(j)
- p
j
· S
(j)
, dann entsprechen die Zeilen von
¯
R
(j)
Elementen aus B
G
(j)
r,s
.
Als N¨
achstes wollen wir Matrizen ¯
R
(j+1)
, ¯
R
(j+2)
, . . . , ¯
R
(i)
konstruieren,
sodass
¯
L = (G
(0)
, Y
(0)
, R
(0)
), . . . , (G
(j-1)
, Y
(j-1)
, R
(j-1)
),
(G
(j)
, Y
(j)
, ¯
R
(j)
), . . . , (G
(i)
, Y
(i)
, ¯
R
(i)
)
eine Liftingfolge von F modulo p darstellt. Dazu behaupten wir, dass
f¨
ur alle Indizes k
{j, j + 1, . . . , i} Matrizen S
(k)
mit Eintr¨
agen aus
F
p
[x
1
, . . . , x
] existieren, sodass f¨
ur
¯
R
(k)
··= R
(k)
-
k
=j
p
· S
()
,
¯
R
(j-1)
··= R
(j-1)
die folgenden Aussagen gelten:
(i) ¯
R
(k)
· G
(k)
0 (mod p
k+1
).
(ii) ¯
R
(k)
¯
R
(k-1)
(mod p
k
).
(iii)
k
=j
p
· S
()
· G
(k-j)
0 (mod p
k+1
).
Diese Behauptung zeigen wir per Induktion nach k.
Induktionsanfang (k = j)
Es sei S
(j)
wie vorhin definiert. Dann gelten
(i) ¯
R
(j)
· G
(j)
= R
(j)
· G
(j)
- p
j
· S
(j)
· G
(j)
0 (mod p
j+1
),
25
4. Lifting von Gr¨
obnerbasen
(ii) ¯
R
(j)
= R
(j)
- p
j
· S
(j)
R
(j)
R
(j-1)
= ¯
R
(j-1)
(mod p
j
),
(iii) p
j
· S
(j)
· G
(0)
0 (mod p
j+1
).
Induktionsschritt (j < k
i)
Aufgrund der Induktionshypothese und R
(k-1)
·G
(k-1)
0 (mod p
k
) folgt
-
k-1
=j
p
·S
()
·G
(k-1)
= ¯
R
(k-1)
·G
(k-1)
-R
(k-1)
·G
(k-1)
0 (mod p
k
).
Wegen G
(d)
G
(d-1)
(mod p
d
) f¨
ur 1
d k - 1 gilt damit außerdem
-
k-1
=j
p
·S
()
·G
(k-j)
-
k-1
=j
p
·S
()
·G
(k-1)
p
k
·q (mod p
k+1
),
wobei q = (q
1
, . . . , q
l
) mit q
1
, . . . , q
l
F
p
[x
1
, . . . , x
] ist. Mit Lemma 40
folgt daraus q
1
, . . . , q
l
(G
(0)
), also sind die Polynome q
1
, . . . , q
l
jeweils
reduzibel zu 0 bzgl. G
(0)
.
Sei nun S
(k)
die Matrix, sodass es f¨
ur jedes d
{1, . . . , l} eine Zeile von
S
(k)
gibt, die einem Element aus A
G
(0)
(q
d
, 0) entspricht. Dann gilt
S
(k)
· G
(0)
q (mod p).
Wir zeigen im Folgenden, dass mit dieser Matrix die Bedingungen (i), (ii)
und (iii) gelten.
Die Bedingung (i) ist erf¨
ullt, denn es gilt
¯
R
(k)
· G
(k)
=
R
(k)
-
k
=j
p
· S
()
· G
(k)
= R
(k)
· G
(k)
-
k
=j
p
· S
()
· G
(k)
- p
k
· S
(k)
· G
(k)
R
(k)
· G
(k)
+ p
k
· q - p
k
· q 0 (mod p
k+1
).
Aufgrund von
¯
R
(k)
= R
(k)
-
k
=j
p
· S
()
R
(k-1)
-
k-1
=j
p
· S
()
= ¯
R
(k-1)
(mod p
k
)
gilt auch die Bedingung (ii). Es gilt außerdem
k
=j
p
· S
()
· G
(k-j)
=
k-1
=j
p
· S
()
· G
(k-j)
+ p
k
· S
(k)
· G
(k-j)
-p
k
· g + p
k
· g = 0 (mod p
k+1
),
26
4. Lifting von Gr¨
obnerbasen
woraus auch schließlich die Bedingung (iii) folgt.
Wir haben nun eine neue Liftingfolge ¯
L gefunden, die zu j hochreduzierend
ist. Wiederholt man diesen Vorgang, so erhalten wir eine zu i hochredu-
zierende Liftingfolge. Insbesondere bedeutet das, dass S g
(i)
r
, g
(i)
s
---
G
(i)
0
f¨
ur alle Indizes r, s mit 1
r < s n ist.
(b) Sei nun h
G
(i)
Z
p
i+1
[x
1
, . . . , x
]. Dann l¨
asst sich h darstellen als
h =
n
k=1
h
k
g
(i)
k
, wobei h
k
Z
p
i+1
[x
1
, . . . , x
] ist. Man kann mithilfe von
Teilaussage (a) eine Darstellung von h finden, sodass f¨
ur alle Summanden
h
k
g
(i)
k
= 0 die Bedingung
multideg(h
k
g
(i)
k
)
multideg(h)
gilt (vgl. Beweis von [1, Seite 85, Theorem 6]). Damit gibt es also ein
k
{1, . . . , n}, sodass LM(h
k
g
(i)
k
) = LM(h) ist, d.h. h ist reduzibel bzgl.
G
(i)
.
(c) Sei ¯
F
··= F (mod p
i+1
). Da p eine gl¨
uckbringende Primzahl ist, exis-
tiert ¯
G
(i)
= ¯
g
(i)
1
, . . . , ¯
g
(i)
n
··= G (mod p
i+1
) und es gilt ( ¯
F ) = ( ¯
G
(i)
)
Z
p
i+1
[x
1
, . . . , x
]. Weil L eine Liftingfolge ist, gilt insbesondere Y
(i)
·G
(i)
F (mod p
i+1
) und damit ( ¯
F )
G
(i)
.
Als N¨
achstes wollen wir zeigen, dass ( ¯
F ) =
G
(i)
gilt. Wir nehmen
zun¨
achst an, dass ( ¯
F )
G
(i)
gelten w¨
urde. Dann existiert ein Poly-
nom h
G
(i)
\( ¯
F ). Mit Teilaussage (b) folgt, dass h reduzibel bzgl. G
(i)
ist. Dann ist h auch reduzibel bzgl. ¯
G
(i)
, da LM(g
(i)
k
) = LM(¯
g
(i)
k
) f¨
ur alle
k = 1, . . . , n gilt.
Sei nun q
Z
p
i+1
[x
1
, . . . , x
], sodass h
---
¯
G
(i)
q gilt. Dann ist q
G
(i)
,
weil h
G
(i)
und
¯
G
(i)
= ( ¯
F )
G
(i)
. Es ist aber q
( ¯
F ), da sonst
h
( ¯
F ) w¨
are, was wir nach unserer Annahme ausgeschlossen haben. Mit
den gleichen Argumenten wie f¨
ur h ist q reduzibel bzgl. ¯
G
(i)
. Dieser Re-
duktionsschritt l¨
asst sich also beliebig oft durchf¨
uhren. Das liefert jedoch
einen Widerspruch, da
-
- eine noethersche Relation ist.
Die Annahme ist demnach falsch, d.h. es gilt ( ¯
F ) = G
(i)
.
(d) Sei ¯
G
(i)
= ¯
g
(i)
1
, . . . , ¯
g
(i)
n
··= G (mod p
i+1
). Wir nehmen an, dass es ein
k
{1, . . . , n} g¨abe, sodass g
(i)
k
= ¯
g
(i)
k
.
Es ist g
(0)
k
irreduzibel bzgl. G
(0)
\ {g
(0)
k
}, da G
(0)
eine reduzierte Gr¨
obner-
basis ist. Da M(g
(i)
k
) = M(g
(0)
k
) gilt, so ist auch g
(i)
k
irreduzibel bzgl. G
(i)
\
{g
(i)
k
}. Zudem gilt LT(g
(i)
k
) = LT(¯
g
(i)
k
), d.h. ¯
g
(i)
k
---
G
(i)
h
··= ¯g
(i)
k
- g
(i)
k
= 0,
insbesondere ist LM(g
(i)
k
)
M(h). Weiter gilt wegen M(g
(i)
k
) = M(¯
g
(i)
)
27
4. Lifting von Gr¨
obnerbasen
auch M(h)
M(g
(i)
k
). Daraus folgt insgesamt, dass h irreduzibel bzgl.
G
(i)
ist.
Mit Teilaussage (b) folgt h
(G
(i)
) und damit (G
(i)
) = ( ¯
G
(i)
) = (F ).
Dies widerspricht jedoch Teilaussage (c), d.h. es muss g
(i)
k
= ¯
g
(i)
k
f¨
ur alle
k = 1, . . . , n gelten.
28
5. Der Liftingalgorithmus
5
Der Liftingalgorithmus
5.1
Gleichungssystem zur Bestimmung der Liftingfolge
Ist p eine f¨
ur F
Q[x
1
, . . . , x
]
m
gl¨
uckbringende Primzahl, so existieren insbe-
sondere Matrizen G
(0)
, Y
(0)
, R
(0)
mit Eintr¨
agen aus
F
p
[x
1
, . . . , x
], sodass
Y
(0)
· G
(0)
F (mod p),
R
(0)
· G
(0)
0 (mod p),
wobei G
(0)
= (g
(0)
1
, . . . , g
(0)
n
) die reduzierte Gr¨
obnerbasis von ¯
F
··= F (mod p)
und R
(0)
eine Syzygiematrix von ( ¯
F , G
(0)
) in
F
p
[x
1
, . . . , x
] darstelllen. Unser
Ziel ist es nun, die reduzierte Gr¨
obnerbasis G von F in
Q[x
1
, . . . , x
] zu bestim-
men.
Nach Satz 41 l¨
asst sich (G
(0)
, Y
(0)
, R
(0)
) zu einer Liftingfolge (G
(i)
, Y
(i)
, R
(i)
)
i
beliebiger L¨
ange erweitern. Satz 44 besagt hingegen, dass die Eintr¨
age G
(i)
dieser
Folgenglieder die reduzierte Gr¨
obnerbasis G richtig approximieren.
Nun wollen wir (G
(i)
, Y
(i)
, R
(i)
) aus dem vorherigen Folgenglied
(G
(i-1)
, Y
(i-1)
, R
(i-1)
) berechnen. Seien dazu ~
G
(i-1)
, ~
Y
(i-1)
, ~
R
(i-1)
willk¨
urlich
gew¨
ahlte Lifts von G
(i-1)
, Y
(i-1)
, R
(i-1)
nach
Z
p
i+1
mit M(~
g
(i-1)
k
) = M(g
(0)
k
)
und LC(~
g
(i-1)
k
) = 1 f¨
ur k = 1, . . . , n, wobei ~
G
(i-1)
= (~
g
(i-1)
1
, . . . , ~
g
(i-1)
n
).
Wir bestimmen ein c
F
p
[x
1
, . . . , x
]
n(m+l+1)
, welches das Gleichungssystem
U
· c = v
(i)
(5)
l¨
ost, wobei,
v
(i)
=
1
p
i
·
F
- ~
Y
(i-1)
· ~
G
(i-1)
- ~
R
(i-1)
· ~
G
(i-1)
,
U =
H
m
0
Y
(0)
0
H
l
R
(0)
,
(6)
l =
n
2
die Anzahl der Zeilen in R
(0)
beschreibt und
H
k
=
g
(0)
1
· · · g
(0)
n
0
. ..
0
g
(0)
1
· · · g
(0)
n
eine Matrix mit k Zeilen und kn Spalten ist.
Seien ¯
c = (¯
y, ¯
r, ¯
g)
F
p
[x
1
, . . . , x
]
n(m+l+1)
mit
¯
y = (y
1,1
, . . . , y
1,n
, . . . , y
m,1
, . . . , y
m,n
),
¯
r = (r
1,1
, . . . , r
1,n
, . . . , r
l,1
, . . . , r
l,n
),
¯
g = (g
1
, . . . , g
n
)
29
5. Der Liftingalgorithmus
und
G =
g
1
..
.
g
n
, Y =
y
1,1
· · · y
1,n
..
.
..
.
y
m,1
· · · y
m,n
, R =
r
1,1
· · · r
1,n
..
.
..
.
r
l,1
· · · y
l,n
.
Ist ¯
c eine L¨
osung von (5), so erf¨
ullen G , Y , R die Gleichungen
G
(0)
· Y + Y
(0)
· G
1
p
i
· (F - ~
Y
(i-1)
· ~
G
(i-1)
)
(mod p)
G
(0)
· R + R
(0)
· G
1
p
i
· (- ~
R
(i-1)
· ~
G
(i-1)
)
(mod p)
und wir sehen, dass das die gleichen Gleichungen sind wie in Bemerkung 42.
Erf¨
ullt ¯
c zus¨
atzlich die Eigenschaft
M(g
j
)
M g
(0)
j
- LT(g
(0)
j
)
(7)
f¨
ur alle j = 1, . . . , n, so setzen wir
G
(i)
= ~
G
(i-1)
+ p
i
· G ,
Y
(i)
= ~
Y
(i-1)
+ p
i
· Y ,
R
(i)
= ~
R
(i-1)
+ p
i
· R .
Satz 41 impliziert die Existenz einer L¨
osung des Gleichungssystems (5) und Satz
44 besagt weiter, dass die letzten n Eintr¨
age einer L¨
osung ¯
c mit der Eigenschaft
(7) eindeutig bestimmt sind.
5.2
Gr¨
obnerbasen von Moduln
Wir wollen sp¨
ater eine L¨
osung ¯
c mit dieser gew¨
unschten Eigenschaft (7) kon-
kret berechnen. Bevor wir eine Beschreibung f¨
ur ein L¨
osungsverfahren ange-
ben, werden wir uns kurz mit dem Begriff der Gr¨
obnerbasis von Moduln ¨
uber
K[x
1
, . . . , x
] auseinandersetzen, welche die Theorie aus Kapitel 2 verallgemei-
nert. Mehr zu diesem Thema findet man in [4].
Definition 45
Seien g, h, f
1
, . . . , f
s
K[x
1
, . . . , x
]
r
mit g = (g
1
, . . . , g
r
) und f
k
= (f
k,1
, . . . , f
k,r
)
f¨
ur k = 1, . . . , s. Es sei außerdem F = (f
1
, . . . , f
s
).
(a) Dann heißt g reduzibel zu h bzgl. F , falls es k
{1, . . . , s}, l {1, . . . , r},
c
K mit c = 0 und ein Monom u in x
1
, . . . , x
gibt, sodass die folgenden
Eigenschaften gelten:
(i) c ist der Koeffizient des Monoms u
· LM(f
k,l
) in g
l
30
5. Der Liftingalgorithmus
(ii) h l¨
asst sich schreiben als
h = g
-
c
LC(f
k,l
)
· u · f
k
In diesem Fall schreiben wir g
-
-
F
h.
(b) g heißt nach endlich vielen Schritten reduzibel zu h bzgl. F , wenn
g = h gilt oder wenn es ein m
N und q
0
, . . . , q
m
K[x
1
, . . . , x
]
r
gibt,
sodass
g = q
0
-
-
F
q
1
-
-
F
q
2
-
-
F
. . .
-
-
F
q
m
= h.
In diesem Fall schreiben wir g
-
-
F
h.
Definition 46
Seien U
K[x
1
, . . . , x
]
r
ein Untermodul, g
1
, . . . , g
t
K[x
1
, . . . , x
]
r
Erzeuger
von U und G = (g
1
, . . . , g
t
). Dann heißt G eine Gr¨
obnerbasis
von U , falls
g
-
-
G
0 f¨
ur alle g
U gilt.
5.3
Bestimmung der gew¨
unschten L¨
osung des Gleichungs-
systems
Nun m¨
ochten wir uns wieder mit der Bestimmung eines ¯
c mit der Eigenschaft
(7) befassen. Wir werden zun¨
achst von solch einer L¨
osung ¯
c ausgehen und im
Folgenden zeigen, wie man diese explizit ausrechnet.
Als Erstes berechnen wir eine spezielle L¨
osung c
0
f¨
ur das Gleichungssystem
(5) und ein Erzeugendensystem E f¨
ur die L¨
osungsmenge des homogenen Glei-
chungssystems
U
· c = 0.
(8)
Eine ausf¨
uhrliche Beschreibung zur Berechnung von L¨
osungen linearer Glei-
chungssysteme ¨
uber Polynomringen findet man in [6] (alternativ: [2]).
Danach formen wir E in ein neues Erzeugendensystem
C =
..
.
h
(1)
1
..
.
h
(1)
n
,
..
.
h
(2)
1
..
.
h
(2)
n
,
. . .
,
..
.
h
(d)
1
..
.
h
(d)
n
f¨
ur die L¨
osungsmenge von (8) um, sodass
C = (h
(1)
, . . . , h
(d)
)
mit
h
(l)
=
h
(l)
1
..
.
h
(l)
n
31
5. Der Liftingalgorithmus
eine Gr¨
obnerbasis des von C erzeugten Moduls bildet. Ein Verfahren zur Be-
rechnung von Gr¨
obnerbasen von Moduln wird in [4, Seite 149f.] erkl¨
art.
Wir bezeichnen nun mit g = (g
1
, . . . , g
n
) und g = (g
1
, . . . , g
n
) die Vektoren, die
die letzten n Eintr¨
age von c
0
und ¯
c beschreiben. Dann bilden g
-g die letzten n
Eintr¨
age von c
0
-¯c. Da c
0
-¯c nun eine L¨osung des homogenen Gleichungssystems
(8) und C eine Gr¨
obnerbasis darstellen, ist g
- g reduzibel zu 0 bzgl. C .
Da g die Eigenschaft (7) erf¨
ullen soll, schreiben wir g
k
=
x
M
k
c
(k)
x
, wobei
M
k
= M(g
(0)
k
-LT(g
(0)
k
)) und wir c
(k)
als Variablen in
F
p
auffassen. Dann liefert
uns die Reduktionsvorschrift g
- g
-
-
C
0 eine Darstellung
g = g +
M
=1
c
LC h
(())
()
· u
· h
(())
,
(9)
wobei c
k
der Koeffizient des Monoms u
k
· LM h
(())
(k)
in
g
(k)
- g
(k)
-
k-1
=1
c
LC h
(())
()
· u
· h
(())
()
ist (vgl. Bemerkung 9 (c)).
Da die Polynome g
k
die Variablen c
(k)
enthalten, m¨
ussen die Koeffizienten c
so-
mit auch von c
(k)
abh¨
angen. Multiplizieren wir die Polynome auf beiden Seiten
von (9) aus und wenden einen Koeffizientenvergleich auf die Monome an, so er-
halten wir ein lineares Gleichungssystem nach c
(k)
, das eine eindeutig bestimmte
L¨
osung besitzt, da die Eintr¨
age von g eindeutig bestimmt sind.
Definieren wir weiter
a
l
··=
M
=1
()=l
c
LC h
(())
()
· u
,
dann erhalten wir die Gleichung
g = g +
d
l=1
a
l
· h
(l)
.
Haben wir dieses lineare Gleichungssystem gel¨
ost, so k¨
onnen wir schließlich ¯
c
durch
¯
c = c
0
-
d
l=1
a
l
·
..
.
h
(l)
1
..
.
h
(l)
n
berechnen.
32
5. Der Liftingalgorithmus
5.4
R¨
uckschluss auf die reduzierte Gr¨
obnerbasis
Im folgenden Abschnitt besch¨
aftigen wir uns mit dem Problem, wie wir von
einem Tupel G
(i)
Z
p
i+1
[x
1
, . . . , x
] auf die reduzierte Gr¨
obnerbasis G in
Q[x
1
, . . . , x
] schließen k¨
onnen.
Definition 47
Seien p eine Primzahl und N
N. Dann definieren wir
F
p,N
··=
a
b
a, b
Z, -N a N, 1 b N, ggT(a, b) = 1, ggT(b, p) = 1 .
Kennen wir eine Schranke N
N an die Koeffizienten der reduzierten Gr¨obner-
basis, so garantiert der folgende Satz, dass wir die reduzierte Gr¨
obnerbasis zum
Schluss richtig identifizieren.
Satz 48
Seien p eine Primzahl, k, N
N mit N
p
k
-1
2
. Dann gibt es f¨
ur jedes n
Z
p
k
h¨
ochstens ein Element
a
b
F
p,N
, sodass a
bn (mod p
k
).
Beweis
Siehe [5, Seite 9f.].
Bemerkung 49
Es gelten die Bedingungen aus Satz 48. Die Definition von
F
p,N
induziert eine
kanonische Abbildung :
F
p,N
Z
p
k
. Ist
~
Z ··= ab
-1
Z
p
k
a
b
F
p,N
,
so bildet die Abbildung :
F
p,N
~
Z, x (x) wegen Satz 48 eine Bijektion.
Ein Algorithmus zur Rekonstruktion eines Elementes
-1
(n) aus einem n
~
Z
ist in [3] zu finden.
5.5
Liftingalgorithmus
Wir nehmen nun an, dass wir einen Weg kennen w¨
urden, um eine Primzahl
p und ein N
N zu bestimmen, sodass p f¨ur F gl¨uckbringend ist und die
Polynome der reduzierten Gr¨
obnerbasis G von F Polynome mit Koeffizienten
aus
F
p,N
sind, d.h. wir kennen eine Schranke f¨
ur die Koeffizienten der Polynome
in G. Kennen wir keine solche Schranke, so kann der folgende Algorithmus als
p-adische Approximation an G angesehen werden:
Eingabe:
· ein endliches Tupel F mit Eintr¨agen aus Q[x
1
, . . . , x
]
33
5. Der Liftingalgorithmus
· eine f¨ur F gl¨uckbringende Primzahl p
· eine Schranke N N, sodass die Polynome der reduzierten Gr¨obnerbasis
Elemente aus
F
p,N
[x
1
, . . . , x
] sind
Ausgabe:
· die reduzierte Gr¨obnerbasis G von F
Schritt 1:
Setze K
··=
log(2N
2
+1)
log(p)
(d.h. also N
p
K
-1
2
).
Schritt 2:
Setze i
··= 1. Berechne die reduzierte Gr¨obnerbasis G
(0)
= g
(0)
1
, . . . , g
(0)
n
von ¯
F
··= F (mod p) und Matrizen Y
(0)
, R
(0)
, sodass
Y
(0)
· G
(0)
F (mod p),
R
(0)
· G
(0)
0 (mod p),
wobei R
(0)
eine Syzygiematrix von ( ¯
F , G
(0)
) ist.
Schritt 3:
Sei U die Matrix aus (6). Berechne ein Erzeugendensystem
C =
..
.
g
(1)
1
..
.
g
(1)
n
,
..
.
g
(2)
1
..
.
g
(2)
n
,
. . .
,
..
.
g
(d)
1
..
.
g
(d)
n
,
der L¨
osungsmenge des homogenen Gleichungssystems U
· c = 0, sodass
C =
g
(1)
1
..
.
g
(1)
n
,
g
(2)
1
..
.
g
(2)
n
, . . . ,
g
(d)
1
..
.
g
(d)
n
eine Gr¨
obnerbasis des von C erzeugten Moduls bildet.
Schritt 4:
Ist i = K, dann gehe zu Schritt 6.
Schritt 5:
W¨
ahle Lifts ~
G
(i-1)
, ~
Y
(i-1)
, ~
R
(i-1)
von G
(i-1)
, Y
(i-1)
, R
(i-1)
nach
Z
p
i+1
mit M (~
g
(i-1)
k
) = M (g
(0)
k
) und LC(~
g
(i-1)
k
) = 1 f¨
ur k = 1, . . . , n.
Bestimme eine L¨
osung ¯
c = (¯
y, ¯
r, ¯
g) des Gleichungssystems
U
· c =
1
p
i
·
F
- ~
Y
(i-1)
· ~
G
(i-1)
- ~
R
(i-1)
· ~
G
(i-1)
in
F
p
[x
1
, . . . , x
], wobei
¯
y = (y
1,1
, . . . , y
1,n
, . . . , y
m,1
, . . . , y
m,n
)
¯
r = (r
1,1
, . . . , r
1,n
, . . . , r
l,1
, . . . , r
l,n
)
¯
g = (g
1
, . . . , g
n
)
34
5. Der Liftingalgorithmus
und M(g
j
)
M g
(0)
j
- LT(g
(0)
j
) f¨
ur j = 1, . . . , n erf¨
ullt ist.
Setze
G
(i)
··= G
(i-1)
+ p
i
·
g
1
..
.
g
n
,
Y
(i)
··= Y
(i-1)
+ p
i
·
y
1,1
· · · y
1,n
..
.
..
.
y
m,1
· · · y
m,n
,
R
(i)
··= R
(i-1)
+ p
i
·
r
1,1
· · · r
1,n
..
.
..
.
r
l,1
· · · y
l,n
und i
··= i + 1. Wiederhole Schritt 4.
Schritt 6:
Sei G
(k)
= (g
(k)
1
, . . . , g
(k)
n
) mit g
(k)
=
c
x
f¨
ur = 1, . . . , n.
Berechne
-1
(c
)
F
p,N
und setze g
··=
-1
(c
)
·x
f¨
ur = 1, . . . , n.
Dann ist G = (g
1
, . . . , g
) die reduzierte Gr¨
obnerbasis von F .
Beispiel 50
Es sei die lexikografische Monomordnung mit x < y gew¨
ahlt. In diesem Beispiel
wollen wir mithilfe des Liftingalgorithmus eine reduzierte Gr¨
obnerbasis G von
F =
x
2
y
2
-
14
3
x
3
y
xy
3
-
12
7
x
2
y
2
+ 8x
y
4
+ 8y
- 24x
3
aus dem Einf¨
uhrungsbeispiel von Kapitel 1 bestimmen.
Zun¨
achst einmal w¨
ahlen wir zuf¨
allig p = 5 aus und werden gleich feststellen,
dass 5 tats¨
achlich eine f¨
ur F gl¨
uckbringende Primzahl ist. Wir rechnen nun f¨
ur
F
(mod 5) =
x
2
y
2
+ 2x
3
y
xy
3
- x
2
y
2
- 2x
y
4
- 2y + x
3
die reduzierte Gr¨
obnerbasis
G
(0)
=
y
4
- 2y
xy
3
- 2x
x
2
aus mit der Transformationsmatrix
Y
(0)
=
0
0
y
2
+ 2xy
0
1
-y
2
1
0
x
35
5. Der Liftingalgorithmus
und der Syzygiematrix
R
(0)
=
-x
y
0
-x
2
0
y
4
- 2y
0
-x y
3
- 2
.
Dann berechnen wir die Matrix U aus Gleichung (5) aus, deren transponierte
Matrix wie folgt aussieht:
y
4
- 2y
0
0
0
0
0
xy
3
- 2x
0
0
0
0
0
x
2
0
0
0
0
0
0
y
4
- 2y
0
0
0
0
0
xy
3
- 2x
0
0
0
0
0
x
2
0
0
0
0
0
0
y
4
- 2y
0
0
0
0
0
xy
3
- 2x
0
0
0
0
0
x
2
0
0
0
0
0
0
y
4
- 2y
0
0
0
0
0
xy
3
- 2x
0
0
0
0
0
x
2
0
0
0
0
0
0
y
4
- 2y
0
0
0
0
0
xy
3
- 2x
0
0
0
0
0
x
2
0
0
0
0
0
0
y
4
- 2y
0
0
0
0
0
xy
3
- 2x
0
0
0
0
0
x
2
0
0
1
-x
-x
2
0
0
1
0
y
0
-x
y
2
+ 2xy
-y
2
x
0
y
4
- 2y
x
3
- 2
.
Jetzt w¨
ahlen wir
~
G
(0)
=
y
4
+ 3y
xy
3
+ 3x
x
2
, ~Y
(0)
=
0
0
y
2
+ 2xy
0
1
4y
2
1
0
x
,
~
R
(0)
=
4x
y
0
4x
2
0
y
4
+ 3y
0
4x
y
3
+ 3
als Lifts von G
(0)
, Y
(0)
, R
(0)
und wollen als N¨
achstes eine L¨
osung ¯
c f¨
ur das
Gleichungssystem
U
· c =
1
5
·
F
- ~
Y
(0)
· ~
G
(0)
- ~
R
(0)
· ~
G
(0)
36
5. Der Liftingalgorithmus
berechnen, sodass die letzten drei Eintr¨
age (g
1
, g
2
, g
3
) von ¯
c die Bedingung
M(g
k
)
M g
(0)
k
- LT(g
(0)
k
)
erf¨
ullen. Als L¨
osung finden wir schließlich den
Vektor
¯
c =
0
0
2xy
0
0
y
2
0
0
0
0
-y
0
0
0
-y
4
- 2y
0
0
-y
3
- 2
y
x
0
und berechnen aus den Eintr¨
agen von ¯
c die neuen Matrizen
G
(1)
=
y
4
+ 8y
xy
3
+ 8x
x
2
, Y
(1)
=
0
0
y
2
+ 12xy
0
1
9y
2
1
0
x
R
(1)
=
4x
-4y
0
4x
2
0
-4y
4
- 7y
0
4x
-4y
3
- 7
.
Fassen wir an dieser Stelle die Polynome von G
(1)
als Polynome in
Q[x
1
, . . . , x
]
auf und definieren entsprechend
G
··=
y
4
+ 8y
xy
3
+ 8x
x
2
,
so ist G tats¨
achlich die reduzierte Gr¨
obnerbasis von F in
Q[x
1
, . . . , x
]. Wir
haben also bereits nach dem ersten Durchlauf des Algorithmus erahnen k¨
onnen,
wie die reduzierte Gr¨
obnerbasis von G aussieht. Um in diesem Beispiel die redu-
zierte Gr¨
obnerbasis von G garantieren zu k¨
onnen, h¨
atte man mindestens viermal
37
5. Der Liftingalgorithmus
den Algorithmus durchlaufen m¨
ussen, da N = 8 der h¨
ochste Koeffizient in G
ist und K =
log(2N
2
+1)
log(5)
= 4. Nach dem ersten Durchlauf h¨
atte man n¨
amlich
f¨
alschlicherweise
y
4
-
1
3
y
xy
3
-
1
3
x
x
2
raten k¨
onnen, da auch
-1 3 · 8 (mod 25).
Die Bestimmung einer geeigneten Schranke N und einer gl¨
uckbringenden Prim-
zahl p ohne Kenntnis der reduzierten Gr¨
obnerbasis G bleiben damit ein offenes
Problem.
38
Literaturverzeichnis
Literaturverzeichnis
[1] David A. Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algo-
rithms: An Introduction to Computational Algebraic Geometry and Commu-
tative Algebra, 3/e (Undergraduate Texts in Mathematics). Springer-Verlag
New York, Inc., Secaucus, NJ, USA, 2007.
[2] A. Furukawa, T. Sasaki, and H. Kobayashi. The grobner basis of a module
over k[x
1
, ..., x
n
] and polynomial solutions of a system of linear equations. In
Proceedings of the Fifth ACM Symposium on Symbolic and Algebraic Com-
putation, SYMSAC '86, pages 222224, New York, NY, USA, 1986. ACM.
[3] Peter Kornerup and R. T. Gregory. Mapping integers and hensel codes onto
farey fractions. BIT Numerical Mathematics, 23(1):920.
[4] H.Michael M¨
oller and Ferdinando Mora. New constructive methods in clas-
sical ideal theory. Journal of Algebra, 100(1):138 178, 1986.
[5] W. Trinks. On improving approximate results of buchberger's algorithm by
newton's method. SIGSAM Bull., 18(3):711, August 1984.
[6] F. Winkler. Solution of Equations I: Polynomial Ideals and Groebner Bases.
In R.D. Jenks and D. Chudnovsky, editors, Computers and Mathematics,
volume 125, pages 383407. Marcel Dekker, 1990.
[7] Franz Winkler. A p-adic approach to the computation of gr¨
obner bases.
Journal of Symbolic Computation, 6(23):287 304, 1988.
39
Häufig gestellte Fragen
Worum geht es in diesem Dokument?
Dieses Dokument ist eine umfassende Sprachvorschau, die den Titel, das Inhaltsverzeichnis, die Ziele und Hauptthemen, Kapitelzusammenfassungen und Schlüsselwörter enthält.
Was ist der Inhalt dieses Dokuments?
Das Dokument gibt einen Überblick über die Theorie der Gröbnerbasen und einen Liftingalgorithmus. Es enthält Inhaltsverzeichnis, Einleitungen, Einführungen, Definitionen, Beispiele, Bemerkungen, Propositionen und Beweise zu den relevanten Themen.
Welche Themen werden im Detail behandelt?
Die behandelten Themen umfassen Monomordnungen, Polynomreduktionen, Gröbnerbasen, S-Polynome, Transformations- und Syzygiematrizen, reduzierte Gröbnerbasen, glückbringende Primzahlen und Lifting von Gröbnerbasen.
Was sind die Hauptziele des Dokuments?
Das Ziel des Dokuments ist die Vorstellung und Erklärung der Methode von Winkler zur Berechnung von Gröbnerbasen, ohne mit dem Problem des enormen Zuwachses der Koeffizienten konfrontiert zu werden.
Welche Algorithmen werden betrachtet?
Das Dokument konzentriert sich auf den Liftingalgorithmus und die damit verbundenen Schritte zur Bestimmung der Liftingfolge und des Rückschlusses auf die reduzierte Gröbnerbasis.
Wo finde ich das Literaturverzeichnis?
Das Literaturverzeichnis befindet sich am Ende des Dokuments und listet die referenzierten Werke auf.
Was ist eine Monomordnung?
Eine Monomordnung ist eine Relation auf N0^n, die bestimmte Bedingungen erfüllt, wie Totale Ordnung, Kompatibilität mit der Addition und Wohlordnung.
Was ist eine Polynomreduktion?
Eine Polynomreduktion ist ein Prozess, bei dem ein Polynom durch ein anderes bzgl. einer gegebenen Menge von Polynomen reduziert wird, wodurch ein einfachereres Polynom entsteht.
Was ist eine Glückbringende Primzahl?
Eine Glückbringende Primzahl ist ein Primzahl, die den informationserhaltenden Übergang der reduzierten Gröbnerbasis von Q[x1, . . . , xn] nach Fp[x1, . . . , xn] verantwortlich ist.
Ende der Leseprobe aus 41 Seiten
- nach oben
- Arbeit zitieren
- Duc Khoi Do (Autor:in), 2016, Eine p-adische Methode zur Berechnung von Gröbnerbasen, München, Page::Imprint:: GRINVerlagOHG, https://www.diplomarbeiten24.de/document/428273
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.
neugierig - aktuell - relevant
Entdecken Sie hilfreiche Tipps und Tricks rund ums Studium!
Entdecken Sie hilfreiche Tipps und Tricks rund ums Studium!
Ihre Hausarbeit / Abschlussarbeit:
- - Publikation als E-Book und Buch
- - Hohes Honorar auf die Verkäufe
- - Für Sie komplett kostenlos - mit ISBN
- - Es dauert nur 5 Minuten
- - Jede Arbeit findet Leser
- © GRIN Publishing GmbH.
- Alle Inhalte urheberrechtlich geschützt. Kopieren und verbreiten untersagt.
- info@grin.com
- AGB
- Open Publishing
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Folgen Sie GRIN auf
- GRIN Verlag GmbH
-
- Nymphenburger Str. 86
- 80636
- Munich, Deutschland
- +49 89-550559-0
- +49 89-550559-10
- info@grin.com
-
Kommentare