Zur Divisorenklassengruppenbere hnungin globalen Funktionenk
orpernvorgelegt von
Diplom-Mathematiker

Florian He
aus Berlin

Vom Fa hberei h 3 Mathematik
der Te hnis hen Universitat Berlin
zur Erlangung des akademis hen Grades eines
Doktors der Naturwissens haften
genehmigte Dissertation

Berlin 1999
D83

II

Promotionsauss hu:Vorsitzender: Prof. Dr. A. Bobenko
Beri hter:
Prof. Dr. M. E. Pohst
Beri hter:
Prof. Dr. F. Grunewald
Tag der wissens haftli hen Ausspra he: 30. August 1999

Zur Divisorenklassengruppenbere hnungin globalen Funktionenk
orpernvorgelegt von
Diplom-Mathematiker

Florian He
aus Berlin

Vom Fa hberei h 3 Mathematik
der Te hnis hen Universitat Berlin
zur Erlangung des akademis hen Grades eines
Doktors der Naturwissens haften
genehmigte Dissertation

Promotionsauss hu:Vorsitzender: Prof. Dr. A. Bobenko
Beri hter:
Prof. Dr. M. E. Pohst
Beri hter:
Prof. Dr. F. Grunewald
Tag der wissens haftli hen Ausspra he: 30. August 1999

Berlin 1999
D83

II

Inhaltsverzei hnis

EinleitungV

1 Grundlagen1

1.1 Notation und Grundlagen . . . . . . . . . . . . . . . . . . . . . .
1.2 Darstellung von Funktionenkorpern und Algorithmen . . . . . . .
1.3 Gitter und Basisreduktion . . . . . . . . . . . . . . . . . . . . . .

1
5
7

2 Konstruktive Riemann-Ro h-Theorie11
2.1 Basen der k-Raume L(D) . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Riemann-Ro h-Raum-Bere hnung I . . . . . . . . . . . . . . . . .
2.3 Der Satz von Riemann-Ro h . . . . . . . . . . . . . . . . . . . . .
2.4 Eigens haften der k[x℄-Invarianten . . . . . . . . . . . . . . . . . .
2.5 Verbindung zur Gittertheorie . . . . . . . . . . . . . . . . . . . .
2.6 Divisorreduktion . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7 Riemann-Ro h-Raum-Bere hnung II . . . . . . . . . . . . . . . .
2.8 Weitere Methoden . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10 Zusatzli he Bewertungsbedingungen . . . . . . . . . . . . . . . . .
2.10.1 Ein weiterer Grundring . . . . . . . . . . . . . . . . . . . .
2.10.2 Der ganze Abs hlu von Rhxi in F . . . . . . . . . . . . .
2.10.3 Zusatzli he Bedingungenan Elemente ausL( D ) . . . . . .

2.10.4 S hnitt von Cl k[x℄; F - mit Cl Rhxi; F -Idealen . . . . .
2.10.5 Der ganze Abs hlu von R[x℄ in F . . . . . . . . . . . . .
2.10.6 Parametris he Basen von L(D) \ a . . . . . . . . . . . . .
2.10.7 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . .

3 Divisorenklassengruppen

15
18
20
21
23
27
27
28
29
30
31
32
33
35
36
38

39

3.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.1 L-Reihen und Satz von Hasse-Weil . . . . . . . . . . . . . 39
3.1.2 Struktur der Klassengruppe . . . . . . . . . . . . . . . . . 43
III

IV

INHALTSVERZEICHNIS

3.2 Bes hrankte Erzeugung . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 Approximation der Klassenzahl . . . . . . . . . . . . . . . . . . . 46
3.4 Cartier-Operator, p-Torsion der Klassengruppe und Hasse-WittInvariante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 Glattheitseigens haften

51

5 Das Klassengruppenverfahren

57

6 Anwendungen

79

7 Beispiele

81

Symbolverzei hnis

95

Zusammenfassung

105

4.1 Glattheitsfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Untere S hranken . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Glattheitsannahme fur reduzierte Divisoren . . . . . . . . . . . . . 56

5.1 Prinzipielle Vorgehensweise . . . . . . . . . . . . . . . . . . . . . .
5.2 Relationensu he . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Deterministis he Methoden . . . . . . . . . . . . . . . . .
5.2.2 Probabilistis he Methode . . . . . . . . . . . . . . . . . . .
5.3 Probabilistis he Methode . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Situation und Strategie . . . . . . . . . . . . . . . . . . . .
5.3.2 Erfolgswahrs heinli hkeit . . . . . . . . . . . . . . . . . . .
5.3.3 Komplexitat . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Praktis he Vorgehensweise . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Erzeugung der Faktorbasis . . . . . . . . . . . . . . . . . .
5.4.2 Relationensu he . . . . . . . . . . . . . . . . . . . . . . . .

58
62
63
64
64
65
67
71
73
73
75

6.1 Eindeutige Klassendarstellung . . . . . . . . . . . . . . . . . . . . 79
6.2 Diskreter Logarithmus . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3 Einheiten und Idealklassengruppe des Dedekindrings oS . . . . . . 80

7.1 Verglei h mit Beispielen aus der Einheitenbere hnung . . . . . . .
7.2 Groes Ges hle ht . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Groer Konstantenkorper . . . . . . . . . . . . . . . . . . . . . .
7.4 Hyperelliptis he Funktionenkorper . . . . . . . . . . . . . . . . . .
7.5 Viele Stellen vom Grad eins . . . . . . . . . . . . . . . . . . . . .
7.6 p-Rang der Klassengruppe und Hasse-Witt-Invariante . . . . . . .

82
87
89
91
91
93

EinleitungEin globaler Funktionenkorper F=k uber dem endli hen Konstantenkorper k ist
eine endli he Erweiterung des rationalen Funktionenkorpers k(x). Neben dem
Ges hle ht zahlt die Divisorenklassengruppe und speziell die von den Divisorenklassen vom Grad null erzeugte, endli he Klassengruppe zu den wi htigsten
Invarianten von F=k.
In der Kryptographie werden endli he, abels he Gruppen G verwendet, in denen
das Gruppengesetz a + b fur a; b 2 G eÆzient, der diskrete Logarithmus x 2
mit ax = b aber nur sehr zeitaufwendig bere hnet werden kann. Geeignete Gruppen G erhalt man unter anderem mit der Punktgruppe elliptis her Kurven [31℄und allgemeiner mit der Gruppe der k-rationalen Punkte der Ja obis hen Varietatgeeigneter hyperelliptis her Kurven uber endli hen Korpern k [26℄. Diese Gruppen
sind isomorph zur Klassengruppe der entspre henden elliptis hen beziehungsweise
hyperelliptis hen globalen Funktionenkorper.
In der Codierungstheorie betra htet man algebrais h-geometris he Codes, wel hebeispielsweise dur h die Funktionswerte gewisser algebrais her Funktionen eines
globalen Funktionenkorpers an Stellen vom Grad eins gegeben werden [55℄. Ein
sol her Code besitzt "gute\ Parameter, wenn die na h oben bes hrankte Anzahl der Stellen vom Grad eins im Verhaltnis zum Ges hle ht gro ist. Funktionenkorpern mit vielen Stellen vom Grad eins erhalt man bei bes hranktem Ges hle ht hau g dur h die Betra htung abels her Erweiterungen [19℄. Gema derKlassenkorpertheorie globaler Funktionenkorper stellt die Klassengruppe einen
wi htigen Teil derjenigen Daten von F=k dar, mit Hilfe derer die abels hen Erweiterungen von F parametrisiert werden konnen. Dieser Ansatz wird in [3℄ verfolgt.
Unter Verwendung von globalen Funktionenkorpern mit vielen Stellen vom Gradeins lassen si h ferner Gitterkugelpa kungen mit zumindest asymptotis h guter
Di hte bei wa hsendem Ges hle ht und wa hsender Dimension konstruieren [44℄.
Fur eine Menge S von Stellen vom Grad eins werden hier S -Einheitengitter verwendet. Diese Gitter korrespondieren zu Untergruppen der Klassengruppe.
Bei der Bere hnung der Klassenzahl, der Klassengruppe oder des L-Polynoms

Z

V

VI

EINLEITUNG

eines globalen Funktionenkorpers lassen si h zwei grundsatzli h vers hiedene Situationen unters heiden: Die Betra htung von Funktionenkorpern F=k des Ges hle hts g uber dem Konstantenkorper k mit q Elementen mit(i) q ! 1 und g fest, oder(ii) q fest und g ! 1.
In der Kryptographie betra htet man meistens die Situation (i). Die Struktur der
Punktgruppe elliptis her Kurven kann in polynomialer Laufzeit in log(q) bere hnet werden [31, 49℄. Dur h die Verallgemeinerung dieser Methode wurde in [24℄ein probabilistis hes Verfahren fur die Bere hnung des L-Polynoms eines globalen Funktionenkorpers F=k mit in log(q) polynomialer, in g aber exponentieller
Laufzeit erhalten.
Fur die Situation (ii) gibt es in g subexponentielle, in log(q) aber exponentielle
probabilistis he Verfahren zur Bestimmung der Struktur der Klassengruppe fur
hyperelliptis he Funktionenkorper [1℄ und fur speziell reell-quadratis he Funktionenkorper [53℄. Wie in [39℄ bemerkt, s heint die Bere hnung des L-Polynoms in
Situation (ii) s hwieriger zu sein.
Wir entwi keln in dieser Arbeit einen probabilistis hen Algorithmus zur Bere hnung der Klassengruppe beziehungsweise Divisorenklassengruppe eines globalen
Funktionenkorpers F=k fur die Situation (ii), dessen Laufzeit unter einer gewissen
Annahme in g subexponentiell und in log(q) exponentiell ist, und verallgemeinern
damit Methoden aus [50℄ und [53℄. Wir gehen hierbei von einer Darstellung desFunktionenkorpers dur h
F = k(x; ) mit f (x; ) = 0
fur ein in y normiertes und separables, irreduzibles Polynom f (x; y) 2 k[x; y℄ aus.
Dieser Algorithmus wurde von uns im Computeralgebrasystem KASH, [25℄, implementiert und auf seine Anwendbarkeit uberpruft. Damit ist es erstmals mogli h,die Klassengruppe beziehungsweise
Divisorenklassengruppe globaler Funktionenkorper mit degy f (x; y)  3 zu bere hnen.
Unser Algorithmus basiert auf der Relationenmethode, die zuvor bereits in Einheiten- und Klassengruppenbere hnungen verwendet wurde [7, 23, 50, 53℄. Jedeendli he, abels he Gruppe kann als Faktorgruppe einer endli h erzeugten, freienabels hen Gruppe na h einer von den sogenannten Relationen erzeugten Untergruppe dargestellt werden. Die Idee fur die Klassengruppenbere hnung ist, alsfreie Erzeuger geeignet gewahlte Divisoren vom Grad null zu verwenden unddann die dur h diese Divisoren darstellbaren Hauptdivisoren, die Relationen, zu
bestimmen.

EINLEITUNGVIIDie Trager der die Klassengruppe erzeugenden Divisoren bilden die aus Stellen
von F=k bestehende Faktorbasis S . Unter Verbesserung einer ahnli hen S hranke aus [53℄ weisen wir na h, da es fur g > 0 beispielsweise genugt, wenn die
Faktorbasis die Stellen von F=k eines Grads kleiner glei hmaxf d2 logq (4g 2)e; d2 logq (2g)e + 1 genthalt. Fur die Relationensu he sind dann alle Hauptdivisoren mit Trager in
S zu nden. Dazu entwi keln und verwenden wir Methoden fur die Reduktion
und fur die Bere hnung der Riemann-Ro h-Raume von Divisoren. Mit Hilfe einer
Approximation der Klassenzahl, die aus den Anzahlen der Stellen eines ahnli h
wie zuvor bes hrankten Grads bere hnet wird, konnen wir s hlieli h testen, ob
die volle Gruppe der Hauptdivisoren gefunden wurde.
Die Arbeit gliedert si h wie folgt:
Im ersten Kapitel stellen wir die theoretis hen und algorithmis hen Grundlagenfur algebrais he und speziell globale Funktionenkorper zusammen.
Im zweiten Kapitel geben wir eine konstruktive Fassung der Riemann-Ro hTheorie und bes hreiben Algorithmen zur Bestimmung des Ges hle hts, zur Reduktion von Divisoren und der Bere hnung ihrer Riemann-Ro h-Raume fur allgemeine algebrais he Funktionenkorper. Wir erweitern diese Methoden, so da au hdiskrete Bewertungen des Konstantenkorpers beru ksi htigt werden konnen.
Im dritten Kapitel stellen wir die Grundlagen fur L-Reihen globaler Funktionenkorper fur Charaktere endli her Ordnung der Divisorenklassengruppe zusammen und beweisen die benotigten S hranken fur die Erzeugung der Klassengruppe
und die Approximation der Klassenzahl mit Hilfe des Satzes von Hasse-Weil. Wir
formulieren weiter eine Version des Satzes von Brauer-Siegel fur globale Funktionenkorper und gehen auf Strukturaussagen uber die Klassengruppe und die
Beziehung der p-Torsion zu einem Di erentialraum ein.
Im vierten Kapitel betra hten wir Glattheitseigens haften, mit denen Ergebnisseuber die Erfolgswahrs heinli hkeit der Relationensu he erhalten werden konnen.
Die eigentli h benotigte, aufgrund der vorangegangenen U berlegungen plausible
und heuristis he unterstutze Aussage formulieren wir als Glattheitsannahme.
Im funften Kapitel kommen wir zur Bes hreibung des Klassengruppenverfahrens.
Na h Erlauterung der allgemeinen Strategie bes hreiben wir deterministis he, in g
exponentielle Te hniken und eine probabilistis he, unter der Glattheitsannahme
in g subexponentielle Te hnik zur Relationensu he. Auf letzterer baut der in derPraxis eingesetzte Algorithmus auf, der ans hlieend formuliert wird.

VIII

EINLEITUNG

Im se hsten Kapitel erwahnen wir Anwendungen des Klassengruppenverfahrens
zur Bestimmung von Einheiten- und Idealklassengruppen und zur Bere hnungdes diskreten Logarithmus.
Im siebten Kapitel fuhren wir einige illustrative Beispiele an, die das Laufzeitverhalten und die Anwendbarkeit des Verfahrens unter Variation der wesentli hen
Parameter q und g demonstrieren.

I h mo hte an dieser Stelle Herrn Prof. Dr. M. E. Pohst ganz herzli h fur seine
Hinweise, Unterstutzung und die gute Zusammenarbeit wahrend der Anfertigung
dieser Arbeit danken.
Ferner danke i h Herrn Prof. Dr. F. Grunewald fur die U bernahme des Koreferats, allen Mitgliedern der Kant-Gruppe, Dr. C. Fieker fur die Dur hsi ht einervorlau gen Fassung der Arbeit und Dr. R. Auer fur einige Hinweise zur Verbesserung von KASH.
Daruber hinaus bedanke i h mi h fur die Forderung dur h ein NaFoG-Stipendium
bei den dafur zustandigen Personen.

Kapitel 1
Grundlagen

In diesem Kapitel werden die dieser Arbeit zugrundeliegenden De nitionen undtheoretis hen sowie algorithmis hen Aussagen fur algebrais he Funktionenkorper
bereitgestellt und Notationen vereinbart. Fur die Theorie der algebrais hen Funktionenkorper verweisen wir auf [11, 12, 13, 55℄, fur algorithmis he Aspekte auf[9, 36, 37, 50, 53℄.

1.1 Notation und Grundlagen
Ein algebrais her Funktionenkorper F=k (in einer Variablen) uber einem Korper k
ist eine Korpererweiterung F von k, so da F eine endli he Erweiterung von k(x)fur ein uber k transzendentes Element x 2 F ist. Der Korper k wird Konstantenkorper genannt. Der algebrais he Abs hlu k0 von k in F hat endli hen Graduber k und wird der exakte Konstantenkorper von F=k genannt. Ein globaler
Funktionenkorper F=k liegt vor, wenn k ein endli her Korper q ist.
Unter einer Stelle P von F=k verstehen wir das eindeutig bestimmte, maximale
Ideal eines (diskreten) Bewertungsrings von F=k. Der zugehorige Bewertungsring
werde mit oP , die zugehorige exponentielle, surjektive Bewertung F ! [f1gmit vP bezei hnet. Fur jedes Element von k0 liefert vP den Wert null. Der Restklassenkorper von P ist der Korper oP =P . Der Grad von P ist der Grad der (stets
endli hen) Korpererweiterung von oP =P uber k0. Wir s hreiben P l(F=k) fur die
Menge aller Stellen von F=k , P ln (F=k) fur die Menge der Stellen vom Grad n
und P ln (F=k) fur die Menge der Stellen vom Grad kleiner glei h n. Mittels desGrads von Stellen erhalten wir eine Abbildung deg : P l(F=k) ! . Gehen wir
in diesen De nitionen vom Korper k zu einem Teilkorper k~ von k0 mit endli hem
Index [k0 : k~℄ uber, so andern si h Stellen, Bewertungen und Restklassenkorper
ni ht. Wir de nieren den Grad uber k~ als degk~ (P ) = [k0 : k~℄ deg(P ).
F

Z

Z

1

2

KAPITEL 1.

GRUNDLAGENDie Gruppe D(F=k) der Divisoren von F=k wird als die von den Elementen aus
P l(F=k) erzeugte, freie abels he Gruppe de niert. Wir s hreiben das Gruppengesetz additiv. Die Elemente von P
D(F=k) sind die Divisoren von F=k. Ein Divisor
D ist also eine formale Summe P 2P l(F=k) nP P , in der fast alle np null sind. Der
Exponent vP (D) einer Stelle P in D ist der Wert np, der Trager supp(D) eines
Divisors D ist die Menge der Stellen P mit vP (D) 6= 0. Einen dur h eine einzige
Stelle mit Exponent eins gegebenen Divisor nennen wir Primdivisor. Fur Divisoren D1; D2 de nieren wir D1  D2, wenn  exponentenweise gilt. Ein Divisor
D  0 heit positiv.
Jeder Divisor lat si h eindeutig als Di erenz D = (D)0 (D)1 positiver Divisoren s hreiben, wobei (D)0 Nullstellendivisor und (D)1 Polstellendivisor von D
genannt wird. Fur eine Menge M von Divisoren oder Stellen von F=k bezei hnen
wir mit hM i die von M erzeugte Untergruppe von D(F=k). Die Gradfunktion deg(degk~ ) wird additiv auf D(F=k) fortgesetzt, analog spre hen wir vom Grad eines
Divisors. Die Menge der Divisoren vom Grad n bezei
hnen wir mit Dn(F=k).
P
S hlieli h de niert die Zuordnung a 7! (a) := P 2P l(F=k) vP (a)P einen Homomorphismus () : F  ! D0(F=k), dessen Bild aus den sogenannten Hauptdivisoren besteht und mit P (F=k) bezei hnet wird. Der Kern von () stimmt mit dem
exakten Konstantenkorper k0 von F=k uberein. Den Nullstellen- beziehungsweise
Polstellendivisor eines Hauptdivisors notieren wir in der Form (a)0 beziehungsweise (a)1.
Es sei D ein Divisor von F=k. Der Riemann-Ro h-Raum L(D) von D wird de niert als
L(D) := fa 2 F  j (a)  Dg [ f0g:
Hierbei handelt es si h um einen endli h-dimensionalen k-Vektorraum, dessen
Dimension mit dim(D) notiert wird. Zur Angabe des Konstantenkorpers, uber
dem die Dimension gemessen wird, s hreiben wir wie beim Grad gelegentli hdimk~ (D). Fur weitergehende Aussagen, insbesondere den Satz von Riemann-Ro h
und die De nition des Ges hle hts g, sei auf [55℄ und Kapitel 2 verwiesen.
Die Menge aller Di erentiale von F=k wird mit (F=k) bezei hnet. Hierbei handelt es si h um einen eindimensionalen F -Vektorraum. Wie ubli h verwenden wir
die Abbildungen d : F ! (F=k) und () : (F=k) ! D(F=k). Es sei D ein
Divisor von F=k. Wir bezei hnen den Di erentialraum von D mit(D) := f! 2 (F=k) j (!)  Dg:
Dies ist nur no h ein k-Vektorraum. Entspre hend der Exponenten vP (!) heien die in (!) vorkommenden Stellen P Null- beziehungsweise Polstellen von !

1.1.

3

NOTATION UND GRUNDLAGEN

mit den Ordnungen vP (!). Fur diese und weitere Aussagen uber Di erentiale
siehe [11, 13, 33, 55℄.
Die Divisorenklassengruppe C l(F=k) wird de niert als D(F=k) = P (F=k), die Faktorgruppe der Gruppe aller Divisoren na h der Gruppe der Hauptdivisoren. Ihre
Elemente heien Divisorenklassen, das Bild eines Divisors D unter dem kanonis hen Homomorphismus [℄ : D(F=k) ! C l(F=k) s hreiben wir als [D℄. Die
Funktionen deg : D(F=k) ! und dim : D(F=k) ! faktorisieren dur h [℄,lassen si h also (vertreterweise) au h auf C l(F=k) de nieren. Wir spre hen analog vom Grad beziehungsweise der Dimension einer Divisorenklasse uber k. Die
Divisorenklassen vom Grad n werden mit C ln(F=k) bezei hnet. Speziell die Divisorenklassen vom Grad null bilden eine Untergruppe C l0 (F=k) = D0(F=k) = P (F=k)
von C l(F=k), die wir als Klassengruppe von F=k bezei hnen. Ihre Ordnung, eventuell unendli h, wird die Klassenzahl h(F=k) von F=k genannt.
Z

1.1. Proposition.

Z(i) Fur die Divisorenklassengruppe gilt:

C l(F=k) = C l0 (F=k)  :Z(ii) Die Klassenzahl eines globalen Funktionenkorpers ist endli h.

Beweis. Der erste Teil folgt aus C l(F=k) = C l0 (F=k) +_ h [D℄ i, wobei D einen
Divisor von F=k kleinsten, positiven Grads bezei hnet. Fur die zweite Aussage

siehe [55, S. 159℄.
Fur einen globalen Funktionenkorper gibt es immer einen Divisor vom Grad eins,[48℄, [55, S. 164℄, der fur diese Isomorphie herangezogen werden kann.
Es sei S eine Menge von Stellen von F=k. Ein Divisor, dessen Trager nur aus
Stellen aus S besteht, wird S -glatt genannt. Die Gruppe der S -glatten Divisoren
wird in Erganzung zur bisherigen Notation mit D(S ) bezei hnet. Analog setzen
wir Dm(S ) := Dm (F=k) \ D(S ) und P (S ) := P (F=k) \ D(S ). Die Elemente vonF  , deren Hauptdivisoren in P (S ) liegen, werden S -Einheiten von F=k genannt.
Die S -Einheiten und die S -glatten Hauptdivisoren bilden jeweils eine Untergruppe
von F  beziehungsweise D0(S ).
Fur eine ni ht-leere Stellenmenge S werde mit oS der Ring der an allen Stellen
aus S ganzen Elemente von F=k bezei hnet, also der Ring derjenigen Elemente
a 2 F , fur die vP (a)  0 fur alle P 2 S gilt. Komplementar wird oS als der Ring
der an allen Stellen auerhalb von S ganzen Elemente de niert. Es folgt aus [11,S. 58 ., S. 64℄, da beide Ringe Dedekindringe sind. Ihre Idealgruppen werden
mit IS beziehungsweise IS bezei hnet. Fur oS gilt weiter, da die Primideale aus
IS eineindeutig und bewertungserhaltend mit den ni ht in S be ndli hen Stellen

4

KAPITEL 1.

GRUNDLAGEN

korrespondieren, da die Einheitengruppe (oS ) genau von den S -Einheiten von
F=k gebildet wird und da der Quotientenkorper von oS mit F ubereinstimmt.
Wir bezei hnen die Idealklassengruppe von oS mit C l(oS ) und ihre Ordnung,eventuell unendli h, mit h(S ). Die Idealklassengruppe ist eine Faktorgruppe derDivisorenklassengruppe: C l(oS ) = D(F=k) = D(S ) + P (F=k) .
Zur Verknupfung aller dieser Strukturen betra hten wir
1.2. Proposition. Es sei  : G ! H ein Homomorphismus abels her Gruppen

und U eine Untergruppe von G. Man hat die kanonis he exakte Sequenz

0 ! ker  \ U ! ker  ! G=U ! (G)=(U ) ! 0:
Beweis. Die dur h  induzierte Abbildung G=U ! (G)=(U ) ist surjektiv, soda die Exaktheit bei (G)=(U ) folgt. Ist a 2 G mit (a) 2 (U ), so gibt es ein
u 2 U , so da a u 2 ker  ist. Der Kern
 von G=U ! (G)=(U ) besteht daher
aus ker  + U =U = ker = ker  \ U , so da si h die Exaktheit an den anderendrei Stellen ergibt.
Hieraus resultieren zwei Folgerungen:1.3. Korollar. Man hat eine kanonis he exakte Sequenz

0 ! D0(S ) = P (S ) ! C l0 (F=k) ! C l(oS ) ! deg D(F=k) = deg D(S ) ! 0:
Beweis. Hierfur wird G := C l(F=k), H := ,  := deg und U := D(S ) +P (F=k)=P (F=k) gesetzt. Dann gilt ker  = C l0 (F=k), ker  \ U =  D0(S ) +P (F=k) =P (F=k) = D0(S ) = P (S ), G=U = D (F=k) = D(S ) + P (F=k) = C l(oS )und (G)=(U ) = deg D(F=k) = deg D(S ) .
Aufgrund dieses Korollars de nieren wir den S -Regulator dur hR(S ) := D0 (S ) : P (S ) :Damit gilt dann die Formel
R(S ) h(S ) = deg D(S ) h(F=k);sofern auer deg D(S ) mindestens zwei der beteiligten Werte endli h sind, vgl.
au h [3, S. 14℄, [43℄.
1.4. Korollar. Es sei A ein S -glatter Divisor mit deg(A) > 0. Dann hat manZ

die kanonis he exakte Sequenz

0 ! D0(S )=P (S ) ! D (S )= hAi + P (S ) ! deg D(S ) = deg(A) ! 0:
Z

1.2.


DARSTELLUNG VON FUNKTIONENKORPERN
UND ALGORITHMEN

5

Beweis.
Hierfur wird G := D(S )=P (S ), H := Z,  := deg und U := hAi +0P (S ) = P (S ) gesetzt.
 Dann gilt ker  = D (S )=P
 (S ), ker  \ U = f0g, G=U =D(S )= hAi + P (S ) und (G)=(U ) = deg D(S ) = deg(A)Z.

Die Gradbewertung v1 zur "unendli hen\ Stelle 1 eines rationalen Funktionenkorpers k(x) ist dur h v1(f=g) := deg(g) deg(f ), f; g 2 k[x℄ de niert. Wir
verwenden deg := v1 dann au h fur Elemente aus k(x). Die Elemente ni ht
positiven Grads von k(x) bilden den diskreten Bewertungsring o1.
Fur eine unitare Ringerweiterung kommutativer Ringe A  B de nieren wir
Cl(A; B ) als den Ring der uber A ganzalgebrais hen Elemente von B .

1.2 Darstellung von Funktionenkorpern und Algorithmen
In diesem Abs hnitt soll kurz auf die Darstellung von Funktionenkorpern und
auf grundlegende Algorithmen Bezug genommen werden, die wir in dieser Arbeitbenotigen werden.
Einen algebrais hen Funktionenkorper F=k realisieren wir als den Quotientenkorper der "endli hen Glei hungsordnung\ k[x; y℄ = f (x; y)k[x; y℄, wobei f (x; y) =y n + a1 y n 1 +    + an 2 k[x℄[y ℄ ein irreduzibles Polynom ist, wel hes normiert undseparabel in y ist. Eine sol he Darstellung existiert fur jeden algebrais hen Funktionenkorper (einer Variablen) uber einem vollkommenen Konstantenkorper k,[50, S. 2℄, [55, S. 128℄. Das Element x wird dann ein separierendes Element von F=kgenannt. Anders ausgedru kt gilt F = k(x; ) mit f (x; ) = 0. Um Komplexitatsaussagen tre en zu konnen, de nieren wir Cf := maxfddeg(ai)=ie j 1  i  ng.
Damit gilt deg dis y f (x; y)  Cf n(n 1) (man sieht dies mit dem Di erenzenprodukt unter Bea htung der Tatsa he, da =xC ganzalgebrais h uber o1 ist).
Fur diese Darstellung
betra hten wir insbesondere die ganzalgebrais hen Ab
s hlusse Cl k[x℄; F und Cl o1; F . Wird S als die Menge der "unendli hen Stelvon F=k uber der unendlen\ von F=k(x) gewahlt, also die Menge der StellenSli hen Stelle 1 von k(x), so gilt
 o = Cl k [x℄; F und oS = Cl o1 ; F . Auerdem hat man
S
=
supp
(
x
)

 1 . Weil k [x℄ und o1 Hauptidealringe sind, besitzen
Cl k[x℄; F und Cl o1; F Ganzheitsbasen bestehend aus [F : k(x)℄ Elementen,
entspre hendes gilt fur ihre Ideale. Sol he Basen sind modulo unimodularer Transformationen uber k[x℄ oder o1 eindeutig
 bestimmt. Die
 Norm NF=k(x) (a) eines(gebro henen) Ideals a von Cl k[x℄; F oder Cl o1; F wird als Determinanteeiner U bergangsmatrix einer Ganzheitsbasis zu einer Idealbasis von a (modulo
Einheiten von k[x℄ oder o1) de niert und ist multiplikativ.
f

6

KAPITEL 1.

GRUNDLAGENIn Algorithmen gehen wir davon aus, da der Korper k bere henbar ist, da also
die Null und die Eins zu Verfugung stehen und da mit vorgegebenen Elementen die Operationen +; ; ; = und die Abfrage auf Glei hheit ausgefuhrt werdenkonnen. Hiermit erhalt man die Mogli hkeit, au h in Polynomringen k[x℄ und rationalen Funktionenkorpern k(x) +; ; ; =; div; = bere hnen zu konnen (div soll
Teilen mit eindeutigem Rest bedeuten). Bei Laufzeitangaben werden die benotigten Operationen und Zuweisungen in k sowie die Bitoperationen fur entspre hende
Re hnungen in gezahlt.
Wir nehmen weiter an, da Algorithmen
zur Bere hnung von Ganzheitsbasen

der Ringe Cl k[x℄; F und Cl o1; F , zur Bere hnung ihrer Primideale zu vorgegebenen Primelementen vono1, eine Element- und Ideal k [x℄ beziehungsweisearithmetik fur Cl k[x℄; F und Cl o1; F inklusive Idealfaktorisierung und Bewertungsbere hnung bezugli h Primidealen zur Verfugung stehen. Dies ist beispielsweise fur k = q oder k = Zahlkorper der Fall, Implementierungen nden
si h in [25℄. Mindestens fur die Bestimmung der Primideale beziehungsweise der
Idealfaktorisierung werden hierbei insbesondere Faktorisierungsalgorithmen fur
Polynome uber k (und uber Erweiterungen von k) benotigt. U ber das prinzipielle
Vorgehen dieser Algorithmen geben [9, 17, 36, 37℄, und speziell fur die Funktionenkorpersituation [50℄, Auskunft.
Im Fall globaler Funktionenkorper (also k = q ) wird in [8℄ gezeigt, da der Aufwand zur Bestimmung der Ganzheitsbasis oS polynomial aquivalent zum Aufwand
der Bestimmung des quadratfreien Anteils der Diskriminante von f (x; y) als Polynom in y ist. Da diese Aufgabe wiederum polynomial im Grad der Diskriminantegelost werden kann, erhalten wir insgesamt einen in Cf und n polynomialen Aufwand. Ohne an dieser Stelle auf die Details eingehen zu konnen, merken wir an,da au h die anderen angefuhrten Algorithmen eine in Cf und n polynomiale
Laufzeit benotigen, in wel he aber no h der maximale Grad der in den Darstellungen der beteiligen Ideale auftretenden Polynome von k[x℄ polynomial eingeht.
Es ist speziell zu bea hten, da die Faktorisierung in k[x℄ einen im Grad polynomialen Aufwand benotigt. Soll beispielsweise ein Potenzprodukt von Primidealen
ausmultipliziert werden, so bringt dies einen Aufwand mit si h, wel her polynomial in Cf ; n, der Anzahl und dem Grad der auftretenden Primpolynome ist. Die
beiden letzten Werte fassen wir spater in einer "Hohe\ zusammen.
Entspre hend Abs
hnitt 1.1 lassen
si h die Stellen von F=k dur h die Primideale
von Cl k[x℄; F und Cl o1; F eineindeutig reprasentieren. Hier gilt die Beziehung deg(P ) = jdeg(NF=k(x)(p))j fur eine Stelle P von F=k und ein Primideal p
von Cl k[x℄; F oder Cl o1; F , wel he dieselbe Bewertung auf F=k de nieren.
Fur einen globalen Funktionenkorper sind wir damit in der Lage, alle Stellen
eines vorgegebenen Grads m zu ermitteln, indem die Primidealfaktorisierungen
Z

F

F

1.3.

7

GITTER UND BASISREDUKTIONder Primpolynome
des
Grads

m
aus
k
[
x
℄
in
Cl
k
[
x
℄
;
F
und die Primideale in
Cl o1; F beru ksi htigt werden.
Ist k der exakte Konstantenkorper von F=k, so kann die Bestimmung der Anzahl
der Stellen vom Grad eins einer endli hen Konstantenkorpererweiterung Fr =kr
von F=k, [kr : k℄ = r und Fr = F kr fast ohne Faktorisierungen erfolgen: Bis auf
wenige Ausnahmen ("Indexteiler\) genugt es aufgrund des Satzes von Kummer[37, S. 390℄, [55, S. 76℄, die Anzahl der Nullstellen von f (x0; y) fur alle x0 2 kr zu
bestimmen, wel he dur h den Grad des ggT von f (x0; y) und yq +1 y gegeben
ist. Man bea htet auerdem, da dieser Grad fur die Konjugierten von x0 uber kglei h bleibt, weil f KoeÆzienten in k hat (ni ht-konjugierte x0 konnen mit einem
zyklis hen Erzeuger von kr lei ht aufgezahlt werden).
Obwohl diese Methode gegenuber dem obigen Faktorisieren sehr eÆzient ist, zahlt
sie do h au h zu den "naiven\ Methoden, weil der Aufwand exponentiell in r ist.
Fur die Eigens haften von Konstantenkorpererweiterungen siehe [55, S. 101 .,S. 163℄.
Spater werden die Landau-Symbole verwendet: Es seien g; h : >0 ! . Wirs hreiben g = O(h), wenn es ; x0 2 gibt, so da jg(x)j  h(x) fur alle x  x0
gilt. Wir s hreiben g = o(h), wenn es fur jedes " > 0 ein x0 2 gibt, so da
jg(x)j  " h(x) fur alle x  x0 gilt.
r

R

R

R

R

1.3 Gitter und Basisreduktion
Fur die Bere hnung von Riemann-Ro h-Raumen benotigen wir einen Reduktionsalgorithmus fur Matrizen in k(x)nn, wel her im Zusammenhang mit Gittern und der Basisreduktion in Funktionenkorpern zu sehen ist. Wir geben diewesentli hen Aussagen fur den vereinfa hten Fall der uber einem Korper formaler
Laurentreihen de nierten Gitter wieder, wobei der Funktionenkorper selbst no h
ni ht auftritt. Dies ges hieht in Abs hnitt 2.5, wo Aussagen uber die dur h Funktionenkorper de nierten Gitter zusammengefat werden. Es sei grundsatzli h auf
die (etwas unters hiedli he) Darstellung in [50℄ verwiesen.
Wir bezei hnen mit k((x 1)) den Korper der formalen Laurentreihen in x 1 . Der
Grad eines Elements sei der Exponent der groten darin auftretenden x-Potenz.
Fur v 2 k((x 1))n bezei hnen wir mit deg(v) den Spaltengrad von v, also das
Maximum der Grade der Eintrage von v, und mit h (v) 2 kn denjenigen Vektor,
der aus den KoeÆzienten der deg(v)-ten Potenzen von x der Eintrage von v
entsteht (also die KoeÆzienten der groten Potenzen, die anderen sind null).
Es seien nun   k((x 1 ))n ein freier k[x℄-Modul des Rangs m und die v1 ; : : : ; vm
eine Basis von . Wir setzen zusatzli h voraus, da die Basiselemente k((x 1 ))-8

KAPITEL 1.

GRUNDLAGEN

linear unabhangig sind (dies ist glei hbedeutend damit, da  bezugli h deg diskret ist, da es also immer nur endli h viele Vektoren mit bes hrankten degWerten gibt).  ist dann ein "ni ht-ar himedis hes\ Gitter. Das Maximum derGrade der Determinanten von m  m-Teilmatrizen von (vj )j ist eine Invariantevon , die wir als Gitterdiskriminante au assen konnen. Unter einem Reduktionss hritt versteht man nun die Addition einer k[x℄-Linearkombination der vj
zu einem vi, i 6= j , so da si h der Spaltengrad von vi verkleinert. Hierbei handelt
es si h um eine unimodulare Transformation. Die bezugli h der Spaltengrade aufsteigend sortierte Basis v1 ; : : : ; vm von  wird reduziert genannt, wenn eine derfolgenden, aquivalenten Bedingungen zutri t:
1.5. Lemma. Die folgenden Bedingungen sind aquivalent:(i) h (v1); : : : ; h (vm ) sind linear unabhangig,(ii) deg(Pmi=1 ivi) = maxmi=1 deg(ivi) fur alle i 2 k[x℄, 1  i  m,(iii) Pmi=1 deg(vi) ist glei h der Gitterdiskriminante,(iv) v1 ; : : : ; vm realisieren die sukzessiven Minima von .
Beweis. Zum Beweis siehe au h [50℄. Die Situation in (i) stellt eine nur auf die
fuhrenden Terme geri htete Si htweise von (ii) und (iii) dar; die lineare Unabhangigkeit bedeutet, da si h keine fuhrenden Terme auslos hen konnen. Mitdiesen Bemerkungen kann man si h die A quivalenz von (i)-(iii) klar ma hen.
Nummer (iv) folgt induktiv aus (ii).
Diese Bedingungen bedeuten, da kein Reduktionss hritt ausgefuhrt werden kann.
Fur eine ni ht reduzierte Basis kann man also einen Reduktionss hritt ausfuhren,der die Summe der Grade der vi verringert. Fur diese Summe stellt die Gitterdiskriminante aber eine untere S hranke dar, so da man na h endli h vielen
Reduktionss hritten zu einer reduzierten Basis kommt. Hieraus ergibt si h der
Reduktionsalgorithmus; man kann also immer eine reduzierte Basis konstruieren.
Eine Matrix, deren Spalten unglei h null eine reduzierte Basis bilden, nennen wir
reduziert.
Die Eigens haft (iii) kann man als Orthogonalitatseigens haft einer reduzierten
Basis au assen. Das Konzept der Orthogonalitat lat si h weiterverfolgen: Wir
betra hten "orthogonale\ oder au h "isometris he\ Abbildungen des k((x 1))n,die dur h unimodulare Matrizen T 2 k[[x 1 ℄℄nn mit Potenzreiheneintragen gegeben werden: v 7! T v. Fur diese gilt deg(v) = deg(T v). Zwei Gitter 1; 2 heiennun isometris h, wenn es ein sol hes T mit 1 = T 2 gibt. Reduzierte Basen
werden unter T in reduzierte Basen uberfuhrt. Zwei isometris he Gitter besitzen

1.3.

9

GITTER UND BASISREDUKTION

dieselben sukzessiven Minima und dieselbe Gitterdiskriminante, wie man anhand
von Lemma 1.5 erkennen kann. Wir de nieren das orthogonale Gitter des Rangs min k((x 1))n mit den Invarianten d1      dm 2 als das eindeutig bestimmte
Gitter, wel hes eine Basis der Form (x d Æi;j )i 2 k((x 1 ))n fur 1  j  m besitzt.
Es gilt nun der folgende "Klassi kationssatz\:
1.6. Lemma. Es sei   k((x 1 ))n ein Gitter vom Rang m. Dann ist  zu genau
einem orthogonalen Gitter in k((x 1 ))n isometris h.
Beweis. Wir bemerken als erstes, da k[[x 1 ℄℄ ein euklidis her Ring fur deg ist undda Elemente kleineren Grads stets von Elementen groeren Grads geteilt werden. Man kann deswegen eine beliebige Basis von  dur h k[[x 1 ℄℄-unimodulare
Zeilenoperationen in eine obere Dreie ksgestalt bringen, wobei die uber der Diagonalen stehenden Eintrage entweder null sind oder einen e ht groeren Grad als
die darunter stehenden Diagonaleintrage haben. Das von dieser Basis erzeugte
Gitter 0 ist ein zu  isometris hes Gitter. Wegen (i) aus Lemma 1.5 mu si hdiese Basis von 0 wegen der Isometrie zu  bereits in Diagonalgestalt be nden,
wenn sie aus einer reduzierten Basis von  entsteht. Eine reduzierte Basis von 
existiert jedo h stets.
Fur die no h zu zeigende Eindeutigkeit kann man si h lei ht uberlegen, da zweivers hiedene orthogonale Gitter ni ht isometris h sein konnen.
Die fur die spatere Anwendung benotigte Version dieses Lemmas liest si h wie
folgt:
1.7. Korollar. In dem k(x)-Vektorraum V seien ein k[x℄-Modul M1 und ein o1ZjModul M2 , beide frei vom Rang n, gegeben. Dann gibt es Basen v1 ; : : : ; vn von M1
und b1 ; : : : ; bn von M2 , so da(b1; : : : ; bn)N = (v1 ; : : : ; vn)
mit einer eindeutigen Matrix N der Gestalt N = (x d Æi;j )i;j 2 k(x)nn und
d1      dn gilt. Die Basis v1 ; : : : ; vn kann dur h Anwendung des Reduktionsalj

gorithmus auf die Spalten einer Transformationsmatrix beliebiger Basen von M1
und M2 erhalten werden.

Beweis. Man betra htet das von den Spalten einer Basistransformationsmatrix
M beliebiger bi und vi aufgespannte Gitter, wendet Lemma 1.6 an und erhalt
unimodulare Matrizen T 2 o1nn und R 2 k[x℄nn mit N = T MR wie gefordert.
Zu bea hten ist, da T 2 o1nn wegen M 2 k(x)nn gilt. Die letzte Aussage ergibt

si h speziell aus dem Beweis von Lemma 1.6.

10

KAPITEL 1.

GRUNDLAGEN

1.8. Beispiel. Wir betra hten die (in Hermite-Normalform be ndli he) Matrix


x3

x x2

2 :

0
x
Diese Matrix ist ni ht reduziert, weil die Summe der Spaltengrade 5 und derDeterminantengrad 4 betragt. Wir subtrahieren das x-fa he der zweiten Spalte
von der ersten Spalte und erhalten die reduzierte Matrix
x x2 2 :x2x

Zur Bere hnung der Normalform negieren wir die letzte Zeile, vertaus hen sie mit
der ersten Zeile und ziehen von der jetzt letzten Zeile das 1=x-fa he der ersten
Zeile ab. Daraus ergibt si h


x2

x



0 x2 1 :Nun wird das x=(x2 1)-fa he der letzten Zeile zur ersten Zeile addiert und die
letzte Zeile mit x2 =(x2 1) skaliert. Daraus erhalt man das Endergebnis

 2
x 0
0 x2 :
1.9. Bemerkung. Bei dem Reduktionsalgorithmus handelt es si h um eine ver-allgemeinerte Polynomdivision, operierend auf Spalten. Entspre hend kann man
ihn au h als eine Grobnerreduktion interpretieren. Fur Funktionenkorper ubernimmt der Reduktionsalgorithmus die Rolle, die der LLL-Algorithmus im Zahlkorperfall spielt.

Kapitel 2
Konstruktive
Riemann-Ro h-Theorie

Das Hauptziel dieses Kapitels ist, einen Algorithmus zur Bestimmung des Riemann-Ro h-Raums L(D) eines Divisors D eines algebrais hen Funktionenkorpers
F=k anzugeben. Wir benutzen dafur eine idealtheoretis he Fassung der RiemannRo h-Theorie, in deren Rahmen der Satz von Riemann-Ro h relativ lei ht bewiesen werden kann. Alle Strukturen sind hierbei einer direkten, algorithmis hen
Behandlung zugangli h. Darauf aufbauend geben wir Methoden zur Divisorreduktion und zur erweiterten Riemann-Ro h-Raum-Bere hnung an, ziehen einen
Verglei h zur Geometrie der Zahlen fur globale Funktionenkorper und betra hten als Anwendungen die Bestimmung von Di erentialraumen und das explizite
Re hnen in der Divisorenklassengruppe.
Zur Vertiefung dieser Methoden verwenden wir im letzten, verglei hsweise umfangrei hen Abs hnitt zusatzli h diskrete Bewertungen des Konstantenkorpers
und beweisen Aussagen uber die Struktur ganzalgebrais her Abs hlusse und uber
Teilraume von Riemann-Ro h-Raumen, deren Elemente zusatzli he Bewertungsbedingungen erfullen. Anwendungen hiervon liegen beispielsweise in der Reduktion algebrais her Funktionenkorper na h diskreten Bewertungen des Konstantenkorpers im Sinne von [13, S. 187 .℄. Auf diese Ergebnisse werden wir jedo him weiteren Verlauf der Arbeit ni ht zuru kgreifen.
Die in den Abs hnitten 2.1 und 2.3 ausgefuhrten Gedanken wurden in ahnli her
Form bereits in [48℄ verwendet, eine neuere Darstellung lat si h in [27℄ nden.
In diesem Kapitel bezei hnet F=k einen algebrais hen Funktionenkorper mit einem separierenden Element x, S := supp (x)1 und n := [F : k(x)℄, vgl. Abs hnitt 1.2.
11

12

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

2.1 Basen der k -Raume L(D)
Das Hauptergebnis dieses Abs hnitts ist der folgende Satz zusammen mit seinem
konstruktiven Beweis:
2.1. Satz. Fur jeden Divisor D von F=k gibt es eindeutig bestimmte, ganzrationale Zahlen d1      dn und Elemente v1 ; : : : ; vn 2 F , so da die Mengef xj vi j 1  i  n; 0  j  di + rgfur alle r 2 Z eine k-Basis von L D + r(x)1 darstellt. Die Elemente v1 ; : : : ; vn
sind k(x)-linear unabhangig.

Wir bemerken, da die obigen di und vi ni ht nur dem Divisor D zugeordnet
sind, sondern au h von dem Konstantenkorper k und dem separierenden Element x abhangen; die Abhangigkeit besteht genauer vom Polynomring k[x℄  F .
Zur spateren Bezugnahme de nieren wir die di als die k[x℄-Invarianten von D,
ges hrieben jDji (wenn die Vorgabe von k[x℄ klar ist).
Um einen konstruktiven Beweis dieses Satzes geben zu konnen, ubersetzen wir
die obige Situation in einen idealtheoretis hen Kontext:
2.2. Proposition. (i) Es besteht eine naturli he, Bewertungen erhaltende Bijektion zwis hen der Menge der Stellen von F=k und der Menge der Primideale von oS und von oS ,(ii) dur h diese Bijektion wird ein Isomorphismus der Gruppe der Divisoren
von F=k auf das direkte Produkt IS  IS der Idealgruppen induziert, D 7!
(DS ; DS ).
(iii) Wenn D einen Divisor bezei hnet und DS , DS die zugehorigen Ideale in IS
und IS sind, dann gilt L(D) = (DS ) 1 \ (DS ) 1 :Beweis. Wir verweisen auf Abs hnitt 1.1, S. 3 unten. Fur (iii) sei p ein Primideal
von oS , P die zugehorige Stelle von F=k und r die genaue Potenz, mit der p in DS
aufgeht. Also ist r = vP (D) erfullt. Weil oS ein Dedekindring ist, gilt a 2 (DS ) 1
genau dann, wenn a 2 F und vP (a)  r ist. Analoges tri t fur (DS ) 1 zu, soda L(D) = (DS ) 1 \ (DS ) 1 folgt.

2.3. Bemerkung. Es sei D ein dur h (DS ; DS ) dargestellter Divisor. Dann wird
D + r(x)0 dur h (xr DS ; DS ) und D + r(x)1 dur h (DS ; x r DS ) dargestellt.

2.1.


BASEN DER K -RAUME

13

L(D)

Wegen Proposition 2.2, (iii) sind wir nun an der Beziehung von (DS ) 1 und(DS ) 1 in F interessiert. Die Ideale in IS und IS sind freie k[x℄- beziehungsweise o1-Moduln vom Rang n, wir konnen daher Basen v1 ; : : : ; vn 2 (DS ) 1 und
b1 ; : : : ; bn 2 (DS ) 1 von (DS ) 1 und (DS ) 1 wahlen. Weil F ein k(x)-Vektorraum
der Dimension n ist, existiert daruber hinaus eine Matrix M 2 k(x)nn, so da(b1 ; : : : ; bn) M = (v1 ; : : : ; vn) gilt. Wir sehen, da M eindeutig bis auf Multiplikation mit einem unimodularen R 2 o1nn von links und einem unimodularen
T 2 k[x℄nn von re hts ist, denn je zwei Basen von (DS ) 1 oder (DS ) 1 unters heiden si h um zwei sol he Transformationen. Korollar 1.7 pat genau auf dieseSituation, wir konnen damit nun einen Beweis fur Satz 2.1 geben:
Beweis von Satz 2.1. Wir xieren ein D und beweisen zuna hst die Existenz.
Dur h Wahl einer Basisubergangsmatrix M fur (DS ) 1 und (DS ) 1 wie oben
und dur h Anwendung von Korollar 1.7 sehen wir, da es Idealbasen (vi )i von(DS ) 1 und (bi)i von (DS ) 1 gibt, wel he zueinander diagonal liegen mit einer
eindeutigen Transformationsmatrix (x d Æi;j )i;j , in anderen Worten x d bi = vi
mit eindeutigen ganzrationalen Zahlen di fur 1  i  n.
Es sei nun r 2 beliebig. Der Divisor D + r(x)1 wird gema Bemerkung 2.3
dur h das Paar (DS ; x r DS ) von Idealen eindeutig dargestellt. Die Idealbasenvon (DS ) 1 und xr (DS ) 1 sind (vi)i wie vorher und (b0i )i mit b0i = xr bi. Diesebe nden si h bereits in diagonaler Lage.PWir
betra hten nun den S hnitt von
n
S
1
r
1
i vi mit beliebigen i 2 k[x℄ liegt(D ) mit x (DS ) : Das Element z = Pi=1nS1in (D ) . Weil auf der anderen Seite z = i=1 ix d r b0i gilt, sieht man, da fur
die Bedingung z 2 xr (DS ) 1 notwendig und hinrei hend ist, da ix d r 2 o1
gilt. Dies bedeutet aber, da deg i  di + r ist. Aufgrund dieser Beoba htung
und der k(x)-linearen Unabhangigkeit der vi ergibt si h die Aussage von Satz 2.1
uber die Basis.
Als na hstes beweisen wir die letzte Aussage: Die k(x)-lineare Unabhangigkeit
von Elementen vi wie im Satz folgtPaus
derBasiseigens
haftder
xj vi fur aller 2 . Denn wenn es eine Relation ni=1 i vi = 0 mit i 2 k[x℄ ni ht alle nullgeben wurde, dann waren die Elemente xj vi k-linear abhangig.
Zu zeigen bleibt die Eindeutigkeit jedweder di, die Satz 2.1 zusammen mit beliebigen vi genugen. Wir behaupten, da erstens v1 ; : : : ; vn eine Idealbasis von(DS ) 1 und zweitens xd1 v1 ; : : : ; xd vn eine Idealbasis von (DS ) 1 darstellen.
Weil

S
1
es fur jedes g 2 (D ) ein r 2 gibt, so da g 2 L D + r(x)1 gilt, konnen
wir g dur h die vi darstellen, und die erste Behauptung ist klar. Fur die zweite Behauptung merken wir
ur jedes g 2 (DS ) 1 ein h 2 k[x℄ gibt, an, da es f
so da g 2 L D + (h)0 ist. Wenn wir r := deg h setzen, gilt r(x)1 = (h)1
1 j
und auerdem D + (h)0 = D + r(x)1 + (h), so da die
 Elemente h x vi mit
1  i  n, 0  j  di + r eine k-Basis von L D + (h)0 darstellen (man bea hte
i

i

Z

i

i

Z

n

Z

14

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

L D + (a) = a 1 L(D) fur a 2 F ). Wir sehen also, da g dur h eine o1-lineare

Kombination der xd vi dargestellt werden kann, was zu beweisen war.
Weil nun die Basen v1 ; : : : ; vn von (DS ) 1 und xd1 v1; : : : ; xd vn von (DS ) 1 indiagonaler Lage zueinander sind, s hlieen wir auf die Eindeutigkeit der di dur hdie Eindeutigkeitsaussage von Korollar 1.7.
Aus dem Beweis ergibt si h speziell die Glei hung
i

n

n
X
i=1

jDji = deg(det M );(2.4)

wobei M wie zuvor die Transformationsmatrix einer Basis von (DS ) 1 zu einer
Basis von (DS ) 1 ist.
Es ist klar, da es eine Verbindung zwis hen den k[x℄-Invarianten eines Divisors
D, dem Ges hle ht und der Dimension des exakten Konstantenkorpers von F=kuber k geben sollte.
2.5. Korollar. Es bezei hne g das Ges hle ht von F=k, und es sei k0 der exakte
Konstantenkorper von F=k. Fur die k[x℄-Invarianten jDji eines Divisors D gilt
dann
n
X
i=1

jDji = degk D + [k0 : k℄(1 g) n:

Beweis. Wir wahlen r 2 gro genug, so da der Divisor D + r(x)1 ni ht
speziell ist, [55, S. 33℄, und da r  jDji fur alle 1  i  n gilt. Aufgrund desSatzes von Riemann-Ro h wissen wir dann, da dimk (D + r(x)1) = degk (D +r(x)1 ) + [k0 : k℄(1 g ) ist. Mittels Satz
2.1 bestatigen wir auf der anderen
Seite
Pn
Pn
die Glei hungen dimk (D + r(x)1) = i=1 (jDji + r + 1) = rn + n + i=1 jDji.
Wegen degk (D + r(x)1) = degk D + rn erhalten wir das gewuns hte Resultat
dur h Glei hsetzen.
Das letzte Ergebnis erlaubt eine ans hauli he Interpretation der Invarianten g
und [k0 : k℄ des Funktionenkorpers F=k und des Grads eines Divisors D (fur ein
festes, separierendes Element x): Dur h diese wird namli h der "Abstand\ derden Divisor darstellenden Ideale DS und DS in F bes hrieben. Bei wa hsendem
Grad entfernen si h DS und DS voneinander, wohingegen si h (DS ) 1 und (DS ) 1
annahern (so da U berlappung entspre hend der Groe des Grads von D eintritt).
Fur den Beweis des Korollars haben wir den Satz von Riemann-Ro h verwendet.
Wir geben spater einen konstruktiven Beweis des Satzes von Riemann-Ro h an,
wel her auf der geeigneten Reformulierung dieses Korollars aufbaut. Dies wird
Z

2.2.

RIEMANN-ROCH-RAUM-BERECHNUNG I

15

Korollar 2.10 sein, fur wel hes wir einen alternativen Beweis verwenden, ohne
den Satz von Riemann-Ro h vorauszusetzen.
Als Anwendung erhalten wir die folgende S hranke fur das Ges hle ht, vgl. [55,S. 132℄, [18, S. 201℄, [33, S. 169℄:
2.6. Korollar. Der algebrais he Funktionenkorper F=k mit dem exakten Konstantenkorper k0 sei dur h eine Glei hung f (x; y ) = 0 mit einem in y normierten
und separablen, irreduziblen Polynom f (x; y ) 2 k[x; y ℄ gegeben. Dann gilt fur das
Ges hle ht von F=k
g

Cf (n

1)n 2(n [k0 : k℄) :2[k0 : k℄

Ist Cf = 1 und k0 = k, so erhalt man daraus(n 1)(n 2) :2
Beweis. Es sei  2 F mit f (x; ) = 0. Wir betra hten Glei hungsordnungenk[x; ℄ von oS und o1 [=xC ℄ von oS (=xC ist ganzalgebrais h uber o1). Fur die
Transformationsmatrix der Basen haben wir dann
(1; x C ; : : : ; x C (n 1) n 1)(xC (i 1) Æi;j )i;j = (1; ; : : : ; n 1):
Die Summe der Grade der hierin auftretenden x-Potenzen bildet wegen (2.4) eineobere S hranke fur die Summe der negierten k[x℄-Invarianten des Nulldivisors.
Mit Korollar 2.5 erhalten wir dann: n + [k0 : k℄(g 1)  Cf n(n 1)=2, woraus
si h dur h Umstellen der Unglei hung die Aussage ergibt.
Man verglei he diese S hranke fur das Ges hle ht mit der S hranke fur den Diskriminantengrad deg dis y f (x; y)  Cf n(n 1) aus Abs hnitt 1.2.
g

f

f

f

f

f

2.2 Riemann-Ro h-Raum-Bere hnung I
In diesem Abs hnitt soll das Basisverfahren zur Bere hnung des Riemann-Ro hRaums eines Divisors bes hrieben werden. Wir setzen die Maximalordnungen oS
und oS als bere hnet voraus (vgl. Abs hnitt 1.2). Die Hohe eines Divisors D wird
als die Summe der Grade des Pol- und Nullstellendivisors von D de niert:
h(D) := degk (D)0 + degk (D)1:
Es gibt nun zwei wesentli he Arten der Darstellung eines Divisors D. Wie bisher verwendet kann D dur h zwei Ideale DS und DS reprasentiert werden, von

16

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

denen wir im Hinbli k auf Proposition 2.2, (iii) aber besser nur die Inversen verwenden. Diese Darstellung soll Idealdarstellung heien. Die andere Darstellung ist
einfa h diejenige als Summe von Stellen beziehungsweise als Potenzprodukt vonPrimidealen. Wir nennen sie die freie Darstellung. Die Divisorarithmetik wird fur
Divisoren in freier Darstellung exponentenweise und fur Divisoren in Idealdarstellung mit Idealarithmetik dur hgefuhrt, wobei in beiden Fallen fur Divisoren
D1 ; D2 wegen Abs hnitt 1.2 ein in Cf , n und maxf h(D1 ); h(D2 ) g polynomialer
Aufwand entsteht (die Groe der Exponenten geht bei der freien Darstellung allerdings nur logarithmis h ein). Dur h Ausmultiplizieren der Primideale in einer
freien Darstellung kann man die Ideale DS und DS der Idealdarstellung bestimmen. Umgekehrt mussen diese beiden Ideale aber faktorisiert werden, um die im
Divisor aufgehenden Stellen und ihre Exponenten zu erhalten. Dieser Darstellungswe hsel erfordert in beiden Ri htungen na h Abs hnitt 1.2 ebenfalls eine
polynomiale Laufzeit in Cf , n und h(D). Dur h die Verwendung von Hauptidealen kann man so au h Hauptdivisoren in freier Darstellung von Elementen aus
F  bestimmen.
Die Bere hnung eines Riemann-Ro h-Raums besteht aus der Bere hnung seiner
Basis. Wir stutzen uns dabei auf Satz 2.1 und unters heiden Basen in kurzer(dur h vi, dj gegebener) und langer (dur h xj vi gegebener) Darstellung.
2.7. Algorithmus. (Riemann-Ro h-Raum-Bere hnung I)
Eingabe: Ein Divisor D des algebrais hen Funktionenkorpers F=k.
Ausgabe: Eine k-Basis von L(D) in kurzer oder langer Darstellung.
1. (Basen) Bestimme k[x℄- beziehungsweise o1-Basen v10 ; : : : ; vn0 und b01 ; : : : ; b0n
der Ideale (DS ) 1 und (DS ) 1 :2. (Trafo) Bestimme M 2 k(x)nn mit (b01 ; : : : ; b0n )M = (v10 ; : : : ; vn0 ).

3. (S hnitt) Bestimme die gesu hte Basis v1 ; : : : ; vn mit den k[x℄-Invarianten
dj dur h Anwendung des Reduktionsalgorithmus auf die Spalten von M
gema Korollar 1.7 und Satz 2.1.

4. (Ende) Ausgabe der Basis von Satz 2.1 in kurzer oder langer Darstellung.
Terminiere.

2.8. Bemerkung. Der Algorithmus benotigt insgesamt eine in Cf ; n und h(D)polynomiale Laufzeit: Die Groe der Eintrage der Matrix M im zweiten S hritt
ist namli h polynomial in Cf ; n und h(D). Folgli h erfordert der Reduktionsalgorithmus ebenfalls polynomiale Zeit in Cf ; n und h(D).

2.2.

17

RIEMANN-ROCH-RAUM-BERECHNUNG I

Wenn man Riemann-Ro h-Raume zu Divisoren kleiner Hohe, also ungefahr in derGroenordnung von n oder Cf , bere hnen mo hte, eignet si h Algorithmus 2.7
gut. Gerade im Zusammenhang mit der Divisorenklassengruppe globaler Funktionenkorper kann es aber vorkommen, da die Exponenten des Divisors in freier
Darstellung bei kleinen Stellengraden in der Groenordnung qg liegen, wobei q die
Elementanzahl von k und g das Ges hle ht von F=k ist. Dies bedeutet dann einen
entspre hend der Bemerkung exponentiellen Zeitaufwand fur Algorithmus 2.7. Die
Diskussion dieser Problematik wird in Abs hnitt 2.6 fortgefuhrt.
2.9. Beispiel. Zur Demonstration der Methode betra hten wir ein mogli hst einfa hes Beispiel: Wir wahlen k = , f (x; y) = y2 x3 1 und F = k(x; )
mit f (x; ) = 0, also einen elliptis hen Funktionenkorper. Man re hnet lei ht
na h, da oF := Cl(k[x℄; F ) = k[x; ℄ gilt. Fur die Bestimmung von oF;1 :=Cl(o1; F ) bea htet man, da =x2 ganzalgebrais h uber o1 ist. Das zugehorige
Minimalpolynom ist f1(y) = y2 (x3 + 1)=x4 2 o1[y℄, und hierfur gilt au hCl(o1; F ) = o1[=x2 ℄. Man sieht damit, da der exakte Konstantenkorper
ist und das Ges hle ht eins betragt. Wir wollen das von x 2 erzeugte Hauptideal in oF faktorisieren. Na h dem Satz von Kummer faktorisieren wir dazu
f (x; y ) mod (x 2)k[x; y ℄ in der Form y 2 9 = (y 3)(y + 3) und erhalten(x 2)oF = p1 p2 mit p1 = (x 2)oF + ( 3)oF und p2 = (x 2)oF + ( + 3)oF .
Daraus s hlieen wir, da es uber der dur h x 2 de nierten Stelle von k(x) vom
Grad 1 zwei unverzweigte Stellen P1 beziehungsweise P2 von F=k vom Grad 1
gibt, an denen x den Wert 2 und  den Wert 3 beziehungsweise 3 annimmt. Wir
untersu hen nun die Zerlegung der unendli hen Stelle 1 von k(x) in F . Dazumu (1=x)oF;1 faktorisiert werden, weil 1=x ein Primelement von 1 ist. Wieder mit dem Satz von Kummer und wegen f1(x; y)  y2 mod (1=x)o1[y℄ gilt
(1=x)o1 = p23 mit p3 = (=x2 )oF;1. Die unendli he Stelle von k(x) besitzt also
genau eine, verzweigte Fortsetzung vom Grad 1 auf F , die ebenfalls mit 1 bezei hnet wird. Man kann daher au h sagen, da x den Grad 2 und  den Grad 3
hat.
Nun soll s hlieli h der Riemann-Ro h-Raum von D = 31 P1 , also der S hnitt
p1 \ p3 3 , bere hnet werden. Eine k[x℄-Basis von p1 wird dur h ( 1 ; 2 ) = (x2;  3) und eine o1-Basis von p3 3 dur h ( 1 ; 2) = (x3 =) (1; =x2) gegeben.
Daraus folgt die Basisbeziehung




x 2 3
0
(
x3 + 1)=x510( 1; 2 ) = ( 1 ; 2) 1=x
0 1
0 x2
0
Q

Q


0
(
x3 + 1)=x3:= ( 1 ; 2) (x 2)=x
3=x
Die Matrix ist bereits reduziert, so da die k[x℄-Invarianten von D beide null

18

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

sind und eine Basis des Riemann-Ro h-Raums dur h x 2; y 3 gegeben wird.
Ans hauli h gespro hen besteht L(D) aus den Elementen von p1 , deren Graddur h 3 bes hrankt ist, so da das Ergebnis mit der obigen Bemerkung uber die
Grade im Einklang steht.

2.3 Der Satz von Riemann-Ro hUnter Benutzung der idealtheoretis hen Spra he aus Abs hnitt 2.1 wollen wir nun
einen kurzen, konstruktiven Beweis des Satzes von Riemann-Ro h 2.13 und eine
De nition des Ges hle hts geben. Wir nehmen an, da wir uns in der Situation
genau na h dem Beweis von Satz 2.1 be nden. Korollar 2.5 wird dann passend
wie folgt reformuliert:
2.10. Korollar. Fur einen algebrais hen Funktionenkorper F=k gibt eine Konstante k;x 2 Z, abhangig vom Konstantenkorper k und vom gewahlten separierenden Element x, so da fur die k[x℄-Invarianten eines Divisors D gilt:nX
i=1

jDji = degk D + k;x n:

Beweis. Fur zwei Ideale a; b von oS oder oS ist der Grad der DeterminanteeinerU bergangsmatrix einer Basis von a zu einer von ab dur h deg NF=k(b) gegeben.
P(nx)Fur einen zusatzli hen Divisor E von F=k stimmt die Summe i=1 jD + E ji wegen (2.4) mit dem Grad der Determinante einer U bergangsmatrix einerPBasis
von
n
1
S
S
1
(DS ES ) zu einer Basis von (D E ) uberein, analoges giltPfnur i=1 jDji.
k
DurPnh Zusammensetzen erhalt man daher den Ausdru
i=1 jD + E ji =Sdeg NF=k(x)(E ) . Weil fur den Divisor E die
i=1 jD ji + deg NF=k(x) (ES )Glei hung degk (E ) = deg NF=k(x)(E S ) deg NF=k(x)(ES ) gilt, ergibt si h daraus
die FormelnnXX
jD + E ji = degk E + jDji:
i=1

i=1

Wegen
dieser Formel kann k;x unter Verwendung des Nulldivisors dur h k;x :=Pn
i=1 j0ji + n de niert werden.
Die Summe der k[x℄-Invarianten eines Divisors ist also glei h seinem Grad plus
einer nur von k, x und dem Funktionenkorper F=k abhangigen Konstante. Wirkonnen nun die Summe der ni ht-negativen jDji gema Satz 2.1 (fur r = 0) ungefahr als Dimension von L(D) au assen. Zum Beweis des Satzes von RiemannRo h 2.13 werden wir zeigen, da es einen zu D dualen Divisor D gibt, dessen

2.3.

19

DER SATZ VON RIEMANN-ROCH

ni ht-negative jDji ungefahr mitPden
negativen jDji ubereinstimmen. Dies bedeun
tet dann dimk D dimk D  i=1 jDji = degk D + Konstante, wel hes bereits
die Riemann-Ro h-Glei hung bis auf die gewissen Ungenauigkeiten darstellt.
Um nun die Existenz eines sol hen D zu zeigen, benutzen wir komplementare
Ideale, komplementare Divisoren und ihre grundlegenden Eigens haften, vgl. [27,S. 88 .℄: Es sei A ein Hauptidealring, K der Quotientenkorper, L=K eine separable
Korpererweiterung vom Grad n und B der ganze Abs hlu von A in L. Wenn aein (gebro henes) Ideal von B ist, so ist a# := f 2 L j TrL=K ( a)  Ag das
komplementare Ideal zu a. Wenn a1 ; : : : ; an 2 a eine A-Basis von a ist, danngibt es a#1; : : : ; a#n 2 a# mit TrL=K (a#i aj ) = Æi;j fur 1  i; j  n, und diesebilden eine A-Basis von a#. Wenn b ein weiteres Ideal von B ist, haben wir(ab)# = a#b 1 . Wieder in unserer Funktionenkorpersituation sei der Divisor D
dur h (a; b) dargestellt. Der k(x)-komplementare Divisor D# zu D wird als derdur h ((a 1)#) 1; ((b 1)#) 1 dargestellte Divisor de niert. Wir merken an, dadiese De nition tatsa hli h nur von dem rationalen Funktionenkorper k(x) und
ni ht von x selbst abhangt. A hnli h wie oben gilt die Identitat (D + E )# =D# E fur Divisoren D und E . Der Di erentendivisor DF=k(x) von F=k(x) ist
glei h dem k(x)-komplementaren Divisor des Nulldivisors. Zuletzt de nieren wir
den zu einem Divisor D (k; x)-dualen Divisor D dur h D# 2(x)1.
Die na hsten Aussagen bilden die Grundlage des Satzes von Riemann-Ro h:
2.11. Lemma. Fur die k[x℄-Invarianten des zu D k(x)-komplementaren Divisors
D# gilt fur alle 1  i  n:
jD#ji = jDji:
Beweis. Wir kurzen a = (DS ) 1 und b = (DS ) 1 ab. D# wird dann dur h (a# ) 1
und (b#) 1 dargestellt. Wie in Abs hnitt 2.1 seien a1; : : : ; an eine k[x℄-Basis vona und b1 ; : : : ; bn eine o1-Basis von b, so da bi = xjDj ai fur 1  i Pn gilt. Es
genugt, b#i = x jDj a#i zu beweisen: Es gibt i;j 2 k(x), so da a#j = ni=1 i;j b#igilt. Damit erhalten wir i;j = TrF=k(x)(a#j bi ) = xjDj TrF=k(x)(a#j ai) = xjDj Æi;j ,wobei die erste und die letzte Glei hheit aufgrund der Dualbasiseigens haft unddie zweite Glei hheit wegen bi = xjDj ai folgen.
2.12. Lemma. Fur jeden Divisor D von F=k und seinen (k; x)-dualen Divii

i

i

i

i

sor D gilt die Glei hungdimk D = degk D + k;x + dimk D:PPP
Beweis. Wir konnen jDj 0 (jDji + 1) + jDj  1 (jDji + 1) = ni=1 jDji + n =degk D + k;x wegen Korollar 2.10 s hreiben. Na h Satz 2.1 ist die Dimension dimk D glei h der obigen, ersten Summe. Wegen Lemma 2.11 und Satz 2.1
i

i

20

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

sehen wir, da die k[x℄-Invarianten von D mit jDji = jDji 2 ubereinstimmen.
AufsummierenPfur die Dimension von D ergibt bereits dimk D =P
jD j 0 (jD ji +1) =jDj  1 (jDji +1), was das Negative der obigen, zweiten
Summe ist.
Der Divisor D kann wegen dem zuvor gesagten als D = Wk;x D ges hrieben
werden, wobei wir Wk;x als DF=k(x) 2(x)1 de nieren. Weiter sei l die Dimension
des exakten Konstantenkorpers k0 von F=k uber k. Mit Lemma 2.12 erkennen wir
nun, da k;x von l geteilt wird und da (Nulldivisor einsetzen) k;x  l gilt. Wir
de nieren s hlieli h das Ges hle ht von F=k dur h g := 1 k;x=l und erhaltenii2.13. Satz (Riemann-Ro h). Die Menge der Divisoren W von F=k, fur die
die Glei hungdimk D = degk D + l(1g ) + dimk (WD)

mit beliebigen Divisoren D gilt, bildet eine ni ht-leere Divisorenklasse von F=k.
Ihre Elemente W; die kanonis hen Divisoren, werden exakt dur h dimk W = lg
und degk W = 2l(g 1) unter allen Divisoren von F=k harakterisiert.
Beweis. Die Divisoren Wk;x sind kanonis he Divisoren, weil sie der geforderten
Glei hung wegen des vorangegangenen Lemmas fur alle Divisoren D genugen.
Auerdem hangt die De nition des Ges hle hts ni ht von k oder x ab, weil fur
Divisoren D groen positiven Grads dimk0 (Wk;x D) = 0, folgli h 1 g =dimk0 D degk0 D gilt, und die re hte Seite ist si herli h von x unabhangig. Wenn
W1 obige Glei hung fur alle Divisoren D erfullt, haben wir dimk W1 = lg unddegk W1 = 2l(g 1), wie man dur h Einsetzen des Nulldivisors und W1 fur D
sehen kann. Wenn fur W2 die Glei hungen dimk W2 = lg und degk W2 = 2l(g 1)gelten, dann ist dimk (W1 W2) = l und degk W1 W2 = 0, so da W1 und W2

derselben Divisorenklasse angehoren. Dies zeigt die letzte Aussage sowie, da die
kanonis hen Divisoren tatsa hli h eine Divisorenklasse bilden.

2.4 Eigens haften der k [x℄-Invarianten
In diesem Abs hnitt soll auf weitere Eigens haften der k[x℄-Invarianten eines Divisors D von F=k eingegangen werden. Gilt dimk (W D) > 0 fur einen kanonis hen
Divisor W , so wird D speziell genannt.
2.14. Lemma. Ein Divisor D von F=k ist ni ht speziell genau dann, wenn furseine k[x℄-Invarianten jDji  1 gilt.

2.5.

21

VERBINDUNG ZUR GITTERTHEORIE

Beweis.
Fur den (k; x)-dualen Divisor D von D gilt dimk (W D) = dimk D =P
jDji 1 (jDji +1) (wie im Beweis von Lemma 2.12). Daraus folgt die Gultigkeit

der Aussage.

2.15. Lemma. Fur die k[x℄-Invarianten eines Divisors D von F=k gilt:

0  jDj1 jDjn  l(1 + g):
Beweis. Die erste Unglei hung ist klar, weil die jDji per De nition in i monoton
fallen. Dur h Addition von Vielfa hen von (x)1 zu D andert si h die Varianz
jDj1 jDjn der k[x℄-Invarianten ni ht (siehe Satz 2.1), so da wir jDj1 = 0,folgli h dimk D > 0 annehmen konnen. Es sei D der (k; x)-duale Divisor zu D.
Aus dimk D = 0 folgt 0  jDji  1 fur alle 1  i  n wegen Lemma 2.14, unddie Aussage ist wahr. Wir nehmen nun an, da dimk D > 0 ist und benutzen
die Tatsa he [55, S. 34℄, da dimk A + dimk B  l + dimk (A + B ) fur Divisoren
A und B mit dimk A > 0 und dimk B > 0 gilt.PEntspre hend dem Vorgehen im
Beweis von Lemma
2.12 haben wir dimk D = jDj 0(jDji + 1)  jDj1 + 1 undPdimk D = jDj  1(jDji + 1)  jDjn 1. Wegen D + D = Wk;x erhalten
wir dur h Aufsummieren und unter Bea htung der zitierten Unglei hung, da
jDj1 +1 jDjn 1  dimk D +dimk D  l + lg gilt, womit der Beweis vollstandig
erbra ht ist.
ii

2.5 Verbindung zur Gittertheorie in globalen
Funktionenkorpern
In diesem Abs hnitt wollen wir die Relevanz der k[x℄-Invarianten eines Divisors
D fur die Geometrie der Zahlen eines globalen Funktionenkorpers F=k mit separierendem Element x erlautern. Zu diesem Zwe k wiederholen wir kurz einige Begri e und Aussagen aus [50℄ (in etwas veranderter Form). Die dur h einen
Funktionenkorper gegebenen Gitter sind im allgemeinen ni ht mehr uber k((x 1))
wie die Gitter von Abs hnitt 1.3 de niert, sondern beispielsweise uber Puiseuxreihenkorpern. Wir gehen hierauf ni ht weiter ein, merken aber an, da die Gittertheorie aus Abs hnitt 1.3 hier analog gilt.
Wir we hseln vom logarithmis hen Langenma deg zu einem Absolutbetrag mittels der Beziehung logq j  j = deg(): Im rationalen Funktionenkorper k(x) de nieren wir den Absolutbetrag eines  2 k(x) dur h jj = q v1() , wobei q die(endli he) Anzahl der Elemente von k ist. Die Menge der Stellen uber 1 wird als
S = fP0 ; P1 ; : : : ; Ps g ges hrieben, und wir bezei hnen mit vi beziehungsweise j  ji
die zu Pi gehorige, surjektive exponentielle Bewertung beziehungsweise den Absolutbetrag, so da j ji = q v ( ) fur beliebiges 2 F  gilt. Es sei nun D eini

22

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIEDivisor von F=k. Wir de nieren i als den Exponenten von Pi in D und ei als den
Verzweigungsindex von Pi uber 1. Auf dem k(x)-Vektorraum F existiert eine1=eultrametris he, j  j-lineare Norm jj  jjD de niert dur h jj jjD = maxsi=0 q =e j ji .
Der freie k[x℄-Modul (DS ) 1 ist diskret bezugli h jj  jjD und wird das zu D (undk, x) gehorige Gitter D genannt. Fur diese Gitter haben wir den ubli hen Begri
der sukzessiven Minima.
Eine Basis !1; : : : ; !n von D , geordnet
naP h aufsteigenden
jj  jjD-Werten, wird
s hwa h reduziert genannt, wenn logq jj ni=1 i !i jjD = maxni=1Plogq jji !i jjD
fur alle i 2 k[x℄, (1  i  n) gilt. Sie heit reduziert, wenn jj ni=1 i!ijjD =maxni=1 jji!ijjD fur alle i 2 k[x℄, (1  i  n) gilt. Es ist klar, da reduzierte
Basen au h s hwa h reduziert sind. Man kann nun beweisen, da reduzierte Basen die sukzessiven Minima von D realisieren und da es (im Fall der zahmen
Verzweigung der Stellen von S uber 1) reduzierte Basen fur alle D gibt [50℄.
Die Bere hnung reduzierter Gitterbasen erfolgt im zahm verzweigten Fall mit dem
Reduktionsalgorithmus aus [50℄. Hierfur werden Approximationen der Gitterelemente in der Form von Puiseuxreihenentwi klungen verwendet.
2.16. Satz. Es sei D ein Divisor von F=k und D das zugehorige Gitter bezugli h k, x. Die s hwa h reduzierten Basen !1 ; : : : ; !n von D entspre hen genau
den Elementen v1 ; : : : ; vn 2 F aus Satz 2.1. Weiterhin stehen die k[x℄-Invarianten
jDji und die Absolutbetrage jj!ijjD (dies sind die sukzessiven Minima von D imiii

Fall einer reduzierten Basis) in der Beziehung

jDji = logq jj!ijjD :Beweis. Es sei D ein Divisor von F=k und r 2 . Wir merken als erstes an, dafur 2 F die Bedingungen 2 L(D + r(x)1) und 2 D ^ logq jj jjD  rZaquivalent sind, wie eine lei hte Re hnung zeigt. 

Es
seien
!
;
:
:
:
;
!
s
hwa
h
reduziert
und
t
:=
log
jj
!
jj
. Fur beliebiges =
1
n
i
i
q
D
Pn
alt man wegen der s hwa hen Reduziertheiti=1 i !i mit i 2 k [x℄ und r 2 erh
der !i die folgenden Aquivalenzen:
2 L(D + r(x)1) , log
q jj jjD  r, logq jji!ijjD  r; fur 1  i  n;
, deg i  ti + r; fur 1  i  n:
Die Eindeutigkeitseigens haft der k[x℄-Invarianten von D aus Satz 2.1 ergibt, da
jDji = ti ist und da die !i die Eigens haft der vi aus Satz 2.1 besitzen.
Es bleibt zu zeigen, da
beliebige Elemente vi des Satzes 2.1 s hwa h reduziertsind. Dafur sei = Pni=1 ivi beliebig und r 2 minimal, so da 2 L(D +r(x)1 ) ist. Wegen Satz 2.1 haben wir i vi 2 L(D + r(x)1 ). Die am Anfang des
Z

Z

2.6.

23

DIVISORREDUKTION

Beweises erwahnte A quivalenz zeigt nun, da logq jj jjD  r und logq jjivijjD  rfur alle 1  i  n gilt.
Wegen der Minimalitat von r erhalten wir daher r =logq jj jjD  maxni=1 logq jjivijjD   r.

2.6 Divisorreduktion
Wir knupfen an die Situation des Abs hnitts 2.2 an. Zur Vereinfa hung der Notation betra hten wir Grade und Dimensionen nun uber dem exakten Konstantenkorper k0 und setzen k = k0 voraus.
2.17. De nition. Es sei A ein Divisor mit deg(A)  1. Der Divisor De heite  0 und dim(De rA) = 0 f
maximalreduziert entlang A, wenn D
ur alle r  1 gilt.
max (F=k; A)
Die Menge der entlang A maximalreduzierten Divisoren wird mit Dredbezei hnet. Es sei m  deg(A). Der Divisor De heit m-minimalreduziert entlangA, wenn De  0, dim(De )  m und dim(De + rA) > m fur alle r  1 gilt.
m (F=k; A)
Die Menge der entlang A m-minimalreduzierten Divisoren wird mit Dredbezei hnet. Die Darstellung eines Divisors D als D = De + rA (a) mit einem
entlang A maximalreduzierten (m-minimalreduzierten) Divisor De , r 2 , a 2 F (und m  deg(A)) nennen wir eine Maximalreduktion (m-Minimalreduktion) von
D entlang A.
Die Eigens haft eines Divisors, reduziert zu sein, ist zwar an si h ni ht besondersinteressant, spielt aber wegen ihrer Verwendung bei Bere hnungen mit der Divisorenklassengruppe eine wi htige Rolle. Wir bemerken die folgenden weiteren
Eigens haften, wobei das Ges hle ht von F=k mit g bezei hnet sei: Fur entlang A
maximalreduzierte Divisoren De gilt dim(De )  deg(A) und deg(De ) < g + deg(A).
Fur entlang A m-minimalreduzierte Divisoren De gilt deg(De ) < g + m.
Fur eine m-Minimalreduktion D = De 1 + rA (a) haben alle weiteren m-Minimalreduktionen den glei hen Grad und werden dur h De 2 := (b) + De 1 fur b 2 L(De 1)
gebildet. Analoges gilt fur die Maximalreduktionen. Man sieht daher, da die mMinimal- und Maximalreduktionen entlang A mittels einer Basis vonL(De 1) ineeine 1-1-Beziehung zu den Punkten des projektiven Raums dim(D1 ) (k) gesetzt
werden konnen (in der algebrais hen Geometrie werden diese au h "vollstandige
lineare Reihen\ genannt). Aus diesen U berlegungen folgt
ZP

2.18. Proposition. Es sei A ein Divisor mit deg(A) = 1. Die Maximalreduktion
eines Divisors D entlang A ist dann eindeutig. Anders ausgedru kt: Fur jedeeDivisorenklasse [D℄ gibt es genau einen entlang A maximalreduzierten Divisor D
e + rA℄.
und ein eindeutig bestimmtes r 2 Z mit [D℄ = [D24

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

Beweis. Wir bere hnen [D rA℄ mit
dem maximal mogli hen, eindeutig bestimm
ten r 2 Z, so da dim [D rA℄ = 1 ist. Die Klasse [D rA℄ enthalt einen
einzigen, positiven Divisor De , wel her entlang A maximalreduziert ist. Damit ist
De + rA ein eindeutiger Reprasentant von [D℄. Die Eindeutigkeit von (a) ergibt
si h wegen (a) = De + rA D.

A hnli h wie im Beweis der Proposition wollen wir nun die S hritte fur eine Reduktion von Divisoren in freier Darstellung erlautern. Dies wird bei der Bere hnung
von Riemann-Ro h-Raumen von Divisoren groer Hohe oder groen Grads einewirksame Hilfe sein.
Vorgegeben sei ein beliebiger Divisor A kleiner Hohe und kleinen Grads; beispielsweise ein Primdivisor vom Grad eins, falls existent. Einen Divisor D mit groenExponenten s hopfen wir mittels A aus. Dies soll heien, da wir ein (mogli hst)
groes Vielfa hes von A von D subtrahieren, so da D rA no h eine Dimension groer null besitzt. Hierbei kann r fur einen Divisor negativen Grads selbst
negativ sein. Mit diesem Vorgehen konnen wir errei hen, da De = (a) + D rAfur a 2 L(D rA) ein entlang A maximalreduzierter, ein m-minimalreduzierteroder nur ein im Grad bes hrankter, positiver Divisor wird. Speziell hat man
dann D = De + rA (a) und L(D) = a  L(De + rA).
Wir ma hen zwei Beoba htungen: Erstens, ist a bekannt, so bestimmt man daraus
De in Idealdarstellung, um Faktorisierung zu vermeiden. Zweitens, die Bere hnung
von a und De ist weiterhin s hwierig, da h(D rA) im allgemeinen ni ht klein
im Verglei h zu h(D) ist. Die hier explizit verwendete Darstellung von D dur h
De nennen wir Elementarreduktion entlang A, uber die Wahl von r verfugen wir
spater. Die Elementarreduktion sollte also nur fur Divisoren kleiner Hohe ausgefuhrt werden.
Es gibt nun eindeutige Divisoren D0; : : : ; Dm, so da D = Pmi=0 2iDi gilt und die
Exponenten in den Di betragli h eins sind. Die Anzahl der in Di auftretenden
Stellen sollte ni ht zu gro sein. Wir evaluieren diese Summe na h dem Horners hema, wobei vor jeder Multiplikation eine Elementarreduktion dur hgefuhrt
wird. Mit De m+1 := 0 nehmen wir fur 1  j < m induktiv an, da
D=2

m jD
em j

+

mX
j 1
i=0

2 +A
iD
i

m
X
i=m j

2 i
ir

m
X
i=m j

2i(ai)

gilt. Dur h eine Elementarreduktion von 2 De m j + Dm j 1 erhalten wir die Darstellung 2 De m j + Dm j 1 = De m j 1 + rm j 1A (am j 1) desselbigen. Dur h
Einsetzen dieses Ausdru ks sieht man, da die Darstellung von D mit j au h fur

2.6.

25

DIVISORREDUKTION

j + 1 gilt. Daraus ergibt si h fur j = m :D = De 0 + A

m
X
i=0

2i ri

m
X
i=0

2i(ai )

(2.19)Die Groe der Exponenten von D geht jetzt nur no h logarithmis h ein. Problematis h bleibt weiterhin die Anzahl der in den einzelnen Di auftretenden
Stellen. Hier summiert man die Stellen aus Di sukzessive auf und erhalt na hjedem S hritt Teildivisoren in Idealdarstellung, auf die man die Elementarreduktion anwendet. Die Anzahl der Stellen geht dann zwar weiterhin linear in die
Laufzeit ein, das Anwa
hsen der Hohen wird jedo h vermieden. Wir s hreibenPt0also Di = Di + liA j=1(bi;j ), wobeiPmt die Anzahl der in D auftretenden Stellen
und Di0 reduziert
ist, setzen dies in i=0 2iDi ein und wenden das Vorgehen fur
Pm i 0(2.19) auf i=0 2 Di an. Zusammenfassend erhalt man:
D = De 0 + A

m
X
i=0

2 ( + li )
i r
i

m
X
i=0



2 (ai) +
i

t
X
j =1

(bi;j )



(2.20)

Wir kommen auf die Wahl von r in der Elementarreduktion zu spre hen. Man
kann zwei Strategien unters heiden, wobei weitere denkbar sind: Gradreduktion
und Maximalreduktion entlang A. Die Gradreduktion liefert einen im Grad bes hrankten, positiven Divisor De , wohingegen die Maximalreduktion einen entlang
A maximalreduzierten Divisor De ergibt. Bei der Gradreduktion bestimmt man
also D rA mit einem maximalen r 2 , so da g  deg(D rA) < g + deg(A)gilt. Dann hat man auf jeden Fall positive, eventuell relativ groe Dimension,
und fur die reduzierten Divisoren De gilt ebenfalls g  deg(De ) < g + deg(A).
Diese Reduktion ist ni ht eindeutig. Bei der Maximalreduktion bestimmt man
wie im Beweis der Proposition 2.18 D rA mit einem maximalen r 2 , so da
0 < dim(D rA)  deg(A) gilt. Dann hat man deg(De ) < g + deg(A), der Gradkann also au h kleiner als g sein. Fur einen Divisor A vom Grad eins ist diese
Reduktion eindeutig. Beide Reduktionsarten stimmen fur vorgelegte Divisorenhau g uberein.
Wir fassen das Vorgehen in einem Algorithmus zusammen:
Z

Z

2.21. Algorithmus. (Divisorreduktion)
Eingabe: Divisoren A; D des algebrais hen Funktionenkorpers F=k, wobei D in
freier Darstellung und deg(A) > 0 ist, und eine Strategie fur die Elementarreduktion.

e mit deg(De ) < g + deg(A), in Idealdarstellung
Ausgabe: Ein positiver Divisor D
gegeben, ein r 2PZ und Elemente
ai ; bi;j 2 F , so da D = De + rAPm iti=0 2 (ai ) + j =1 (bi;j ) mit t := jsupp(D )j gilt.

26

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

1. (Zerlegung von D) Bere hne m 2 Z und Divisoren
D ; : : : ; Dm , deren ExPm i0
ponenten betragli h eins sind und fur die D = i=0 2 Di gilt.

2. (Tragerreduktion) Fur jedes i := 0; : : : ; m wird Di0 sukzessive in Idealdarstellung aufgebaut, wobei na h jeder Addition beziehungsweise Subtraktion eines Primdivisors
von Di eine Elementarreduktion erfolgt. Dies liefert
Pt
0
Di = Di + li A
j =1 (bi;j ).
e m+1 := 0. Bere hne f
3. (Exponentenreduktion) Es sei D
ur j := 1; : : : ; m 1
e m j 1 in Idealdarstellung, ein rm j 1 2 Z und am j 1 2 F
einen Divisor D
e m j + D0
mittels der Elementarreduktion angewendet auf 2 D
m j 1 , so da
0
2 De m j + Dm j 1 = De m j 1 + rm j 1A (am j 1) gilt.
e := D
e 0 und r :=4. (Ende) Setze D
ai ; bi;j . Terminiere.

Pm i
ri
i=0

2 ( + li ). Ausgabe von De , r und

2.22. Bemerkung. Die Groe der Exponenten geht logarithmis h und die Anzahl der Stellen von D linear in die Laufzeit ein. Letzteres gilt, weil die Hoheder Di0 wegen der Reduktion in Abhangigkeit von deg(A) standig bes hranktwird. Insgesamt gibt es also ; 2 R >0 , so da Algorithmus 2.21 eine Laufzeit
 log(h(D)) jsupp(D)j (nCf deg(A)d) benotigt, wobei d der maximale Gradder in D auftretenden Stellen ist. Die Elementarreduktion lat si h in der Praxis
besonders gunstig fur A = (x)1 dur hfuhren.
2.23. Bemerkung. Wird ein Divisor A mit deg(A) = 1 gewahlt und als Strate-

gie fur die Elementarreduktion die Maximalreduktion verwendet, so liefert Algorithmus 2.21 fur jeden Divisor D die eindeutige Maximalreduktion von D entlang
A (weil im letzten S hritt eine Maximalreduktion dur hgefuhrt wird). Man kannso eindeutige Reprasentanten fur Divisorenklassen bere hnen. Wahlt man im Falleines globalen Funktionenkorpers uber dem exakten Konstantenkorper mit q Elementen ein A groeren Grads, so erhalt man maximal (qdeg(A) 1)=(q 1) Mogli hkeiten fur eine Maximalreduktion De , also eine "bes hrankte\ Mehrdeutigkeit.
2.24. Bemerkung. Die Bere hnung aller m-Minimalreduktionen eines Divisors
D entlang A wird ebenfalls auf Algorithmus 2.21 zuru kgefuhrt. Man bestimmt
zuna hst die Maximalreduktion D = De + rA + (a) und su ht dann (binare Suhe mogli h) das maximale j mit dim(De + jA)  m, wobei 0  j  b(g + m
1 deg(De ))= deg(A) gilt. Man erhalt damit einen Vertreter der m-Minimalreduktionen modulo Hauptdivisoren, die anderen ergeben si h entspre hend der Bemerkungen vor Proposition 2.18. Im Fall eines globalen Funktionenkorpers lassen si hdie einzelnen m-Minimalreduktionen sogar direkt aufzahlen, ihre Anzahl betragt
namli h maximal (qm 1)=(q 1), q = jkj.

2.7.

RIEMANN-ROCH-RAUM-BERECHNUNG II

27

2.7 Riemann-Ro h-Raum-Bere hnung II
Mit Hilfe der Divisorreduktion des vorigen Abs hnitts und der Beziehung L(D) =a  L(De + rA) fur D = De + rA (a) konnen wir nun Riemann-Ro h-Raume
au h fur "groe\ Divisoren bere hnen. Dazu bea hten wir zwei Dinge: Enthalt
der Divisor D groe Exponenten, hat dabei aber einen kleinen Grad, so sollte
die Bere hnung von L(De + rA) mit der Divisorreduktion D = De + rA (a) kein
Problem darstellen, weil die Dimension ebenfalls klein ist. Bei groem Grad von D
ist aber au h die Dimension gro, die Angabe einer Basis konnte S hwierigkeiten
bereiten. Do h au h dies stellt na h Satz 2.1 kein Problem dar, wenn A = (x)1
gilt. Die Basiselemente konnen in diesem Fall parametris h angegeben werden.
Daraus ergibt si h
2.25. Algorithmus. (Riemann-Ro h-Raum-Bere hnung II)
Eingabe: Ein Divisor D des algebrais hen Funktionenkorpers F=k.
Ausgabe: Eine k-Basis von L(D) in kurzer Darstellung wie in Satz 2.1, wobei die
Basiselemente vi dur h Potenzprodukte von Elementen aus F  gegebensind.
1. (Reduktion) Fuhre unter Verwendung von A = (x)1 und der Gradreduktion
eine Divisorreduktion von D gema Algorithmus 2.21 dur h, wir erhalten
De , r 2 Z und a 2 F  mit D = De + rA (a), wobei a das Potenzprodukt
der ai und bi;j ist.
e ) in2. (Riemann-Ro h) Bere hne mittels Algorithmus 2.7 eine Basis von L(D0000kurzer Darstellung, gegeben dur h v1 ; : : : ; vn und d1 ; : : : ; dn .

3. (Ende) Setze vj := avj0 , dj := d0j + r fur j := 1; : : : ; n. Ausgabe von v1 ; : : : ; vn
und d1 ; : : : ; dn. Terminiere.

2.26. Bemerkung. Gema Bemerkung 2.22 ist der Aufwand fur diesen Algo-rithmus von derselben Form wie der fur Algorithmus 2.21.

2.8 Weitere Methoden zur Bere hnung
von Riemann-Ro h-Raumen
Wir wollen in diesem Abs hnitt alternative Formen der Bere hnung von RiemannRo h-Raumen diskutieren beziehungsweise erwahnen.

28

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

Aufgrund von Satz 2.16 lat si h der Riemann-Ro h-Raum eines Divisors au h aus
einer reduzierten Basis des Gitters D und seinen sukzessiven Minima bestimmen.
Zu den Vorteilen dieser Methode: Eine reduzierte Basis enthalt mehr Information
als eine s hwa h reduzierte Basis, und zwar die Information uber das Verzweigungsverhalten der Stellen uber 1. Die Folge hiervon ist, da Satz 2.1 nun furverallgemeinerte\ Divisoren D +r(x)1 mit r 2 und rationalen k[x℄-Invarianten"ausgespro
hen werden kann. Wir bemerken, da si h dies gunstig auf die Maximalreduktion von Divisoren entlang (x)1 auswirkt (das gesu hte r ist nun namli hrational, so da au h Teildivisoren von (x)1 spezi ziert werden konnen).
Zu den Na hteilen zahlt, da die Gitterreduktion Approximationen verwendet.
Um korrekte Ergebnisse zu erhalten, ist daher die Verwendung einer ausrei henden Prazision beziehungsweise die Dur hfuhrung einer Fehleranalyse unerlali h.
Abgesehen von Prazisionsfragen ist die Gittermethode von der mathematis hen
und von der programmierte hnis hen Seite her aufwendiger. Wahrend nur im
Fall der zahmen Verzweigung Puiseuxreihenentwi klungen zur Verfugung stehen,werden ansonsten allgemeinere P -adis he beziehungsweise Hamburger-Noether
Reihen benotigt. S hlieli h durfte es Probleme bereiten, bei der Riemann-Ro hRaum-Bere hnung au h diskrete Bewertungen des Konstantenkorpers zu beru ksi htigen. Dies ist bei der hier bes hriebenen, symbolis hen Methode mogli h undwird in Abs hnitt 2.10 behandelt.
Zur Riemann-Ro h-Raum-Bere hnung und zu ihren Anwendungen, siehe na hster
Abs hnitt, gibt es ferner Methoden, die von der Seite der algebrais hen Geometrieinspiriert werden [6, 20, 57, 58℄. Diese basieren auf dem Brill-Noether Algorithmus
und verwenden ebenfalls Reihenentwi klungen.
R

2.9 Anwendungen
Der Satz von Riemann-Ro h dominiert die gesamte Theorie der algebrais hen
Funktionenkorper (einer Variablen). Entspre hend umfangrei h sind die Anwendungsgebiete konstruktiver Verfahren der Riemann-Ro h-Theorie. Wir wollen ein
paar Beispiele erwahnen.
Die Konstruktion algebrais h-geometris her Codes kann mit Hilfe von Basen vonRiemann-Ro h-Raumen und au h von Basen von Divisoren zugeordneten Di erentialraumen erfolgen, vgl. [55℄.
Die Bere hnung von Di erentialraumen (D) selbst kann ebenfalls auf die Bere hnung von Riemann-Ro h-Raumen zuru kgefuhrt werden. Der Funktionenkorper F=k uber dem vollkommenen Korper k werde dur h f (x; y) = 0 de niert,
wobei f (x; y) 2 k[x; y℄ in y normiert, separabel und irreduzibel ist. Wir deu-2.10.


ZUSATZLICHE
BEWERTUNGSBEDINGUNGEN

29

ten das Vorgehen nur grob an. Dur h Anwendung des Di erentialoperators d auf
f (x; y ) = 0 erhalt man na h den Di erentiationsregeln eine F -lineare Relation
zwis hen dy und dx:
fdy = x dx;
fywobei der Nenner unglei h null na h Voraussetzung an f (x; y) ist (fx und fy sinddie partiellen Ableitungen na h x und y). Ein beliebiges Element a von F lat si h
als rationale Funktion in x; y darstellen. Dur h Anwenden von d auf a in dieser
Darstellung und unter Bea htung der Relation zwis hen x und y erhalt man dannein b 2 F mit da = b dx. Man wei, da si h jedes Di erential als b dx fur ein b 2 F
darstellen lat. Der Divisor des Di erentials b dx ist (b dx) = (b) + (dx), wobei(dx) = DF=k(x) 2(x)1 gilt, siehe [55, S. 156 (3.16)℄. Den Di erentendivisor konnen
wir wie ubli h lei ht mit Hilfe der Spurenmatrizen bere hnen [9, S. 203, 4.8.18℄.
Insgesamt sind wir also in der Lage, den Divisor eines beliebigen Di erentials zu
bestimmen. Andererseits sieht man au h, da fur einen Divisor D die Unglei hung(b dx)  D genau dann gilt, wenn (b) + (dx) D  0 ist. Diese A quivalenz liefert
einen k-Vektorraumisomorphismus (D) ! L((dx) D), mit dessen Hilfe wirdann s hlieli h eine k-Basis von (D) bere hnen konnen.
Eine weitere, wi htige Anwendung liegt in der Mogli hkeit, in der Divisorenklassengruppe eines algebrais hen Funktionenkorpers explizit zu re hnen. Sind
zwei Divisorenklassen [D1 ℄ und [D2 ℄ gegeben, so gilt trivialerweise [D1 ℄ + [D2℄ =[D1 + D2℄ und k[D1 ℄ = [kD1℄. Es stellt si h aber die Frage, wann zwei Klassen
glei h beziehungsweise wann eine Klasse die Hauptklasse ist. Glei hheit von [D1℄
und [D2 ℄ gilt genau dann, wenn deg(D1) = deg(D2 ) und dim(D1 D2) > 0 ist,
und dieser "Hauptdivisortest\ kann mit den bes hriebenen Methoden in einfa her
und eÆzienter Weise dur hgefuhrt werden. Wir merken zusatzli h an, da wegen
Bemerkung 2.23 au h eindeutige Reprasentanten selektiert werden konnen.
S hlieli h spielt die Riemann-Ro h-Raum-Bere hnung bei der Erzeugung vonRelationen fur die Klassengruppenbere hnung eines globalen Funktionenkorpers
eine zentrale Rolle. Darauf kommen wir aber in Kapitel 5 no h eingehend zu
spre hen.

2.10 Zusatzli he BewertungsbedingungenIn den vorangegangenen Abs hnitten haben wir diskrete Bewertungen des Konstantenkorpers, falls vorhanden, unberu ksi htigt gelassen. Dies soll nun wiederum in einer idealtheoretis hen Weise na hgeholt werden. Die Ergebnisse dieses
Abs hnitts werden konstruktiv, aber theoretis h dargestellt; wir geben keine ex-

30

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

pliziten Algorithmen an. Es werden Methoden der Theorie der Moduln uber Dedekindringen Verwendung nden, fur die wir beispielsweise auf [10℄ verweisen.
2.10.1 Ein weiterer Grundring

Es sei R ein Dedekindring und k der Quotientenkorper von R. Der Inhalt ont(g)eines Polynoms g 2 k[x℄ wird de niert als der grote gemeinsame Teiler der vonden KoeÆzienten von g erzeugten Hauptideale. Es handelt si h hierbei um ein(gebro henes) Ideal von R. Diese De nition wird auf ganz k(x) dur h die Setzung
ont(g=h) := ont(g)= ont(h) fur g; h 2 k[x℄ ausgedehnt. Die Inhaltsfunktion
besitzt drei Eigens haften:(i) ont(g) = f0g , g = 0,(ii) ont(gh) = ont(g) ont(h),(iii) g d ont(g); ont(h) j ont(g + h) fur alle g; h 2 k(x).
Man sagt, eine rationale Funktion habe ganzen Inhalt, wenn ihr Inhalt ein ganzes
Ideal von R ist.
Unter Verwendung eines festen, separierenden Elements x erweitern wir nun R
na h k(x)  F , indem wir Rhxi als den Ring der rationalen Funktionen mit
ganzem Inhalt de nieren. Dieser Ring wird die Rolle eines weiteren Grundrings
analog wie k[x℄ und o1 spielen.
2.27. Proposition. Der Ring Rhxi ist ein Hauptidealring und die Idealgruppen
von R und Rhxi sind isomorph unter a 7! Rhxia. Die Umkehrabbildung hiervon
ist b 7! b \ k.
Beweis. Es sei a ein Ideal von R mit Erzeugern a0 ; : : : ; an 2 a. Das Ideal Rhxia
stellt ein von a := anxn +   + a0 erzeugtes Hauptideal Rhxia dar, weil ont(a) = a
gilt und die Inhalte aller Elemente von Rhxia dur h a teilbar sind. Im Bildberei hvon a 7! Rhxia liegen also nur Hauptideale.
Es sei b 2 Rhxi. Fur jedes  2 ont(b) haben wir =b 2 Rhxi, folgli h  2Rhxib, so da ont(b)  Rhxib gilt. Weil Rhxi ont(b) ein Hauptideal ist und einen
Erzeuger desselben Inhalts wie b wegen des vorangegangenen Absatzes besitzt,
sind beide Erzeuger assoziiert (unters heiden si h nur um Einheiten) und es gilt
Rhxi ont(b) = Rhxib. Im Bildberei h von a 7! Rhxia liegen also alle Hauptideale
von Rhxi.
Die Abbildung a 7! Rhxia ist si herli h multiplikativ, additiv und inklusionserhaltend. Na h den beiden letzten Absatzen erhalten wir eine Isomorphie der Idealgruppe von R zur Gruppe der Hauptideale von Rhxi. Die Abbildung b 7! b \ k
ist fur Hauptideale b von Rhxi dann tatsa hli h die Umkehrabbildung.

2.10.


ZUSATZLICHE
BEWERTUNGSBEDINGUNGEN

31

Es bleibt zuPzeigen, da jedes ganze Ideal b von Rhxi ein Hauptideal ist. Wirsetzen a := b2b ont(b). Dies ist ein ganzes Ideal von R und es gilt Rhxia = b,weshalb b ein Hauptideal sein mu.
Wir merken an, da jedes Ideal a von R wegen des Chinesis hen Restsatzes als die
Summe zweier Hauptideale dargestellt werden kann. Daher sieht man, da si hjedes Ideal von Rhxi bereits dur h ein einzelnes Element von R oder ein Polynom
in R[x℄ vom Grad eins erzeugen lat.
Eine Gaus he Bewertung auf k(x) ensteht aus einer diskreten Bewertung von k,
wel he wir zuerst auf k[x℄ als das Minimum der Bewertungen der KoeÆzienten
eines gegebenen Polynoms de nieren, und dana h auf k(x) als Di erenz der Bewertung des Zahlers und der Bewertung des Nenners einer rationalen Funktion
fortsetzen.
Die Primideale von R de nieren diskrete Bewertungen von k und wir bemerken,da Rhxi au h als Ring derjenigen rationalen Funktionen von k(x) bes hrieben
werden kann, deren Gaus he Bewertungen fur alle Primideale von R samtli hni ht negativ sind.
2.28. Beispiel. Die Elemente a 2 Zhxi, a 6= 0 lassen si h in der Form a = f=g
normieren, wobei f; g 2 Z[x℄ teilerfremde Polynome des Inhalts eins sind, g einen
positiven LeitkoeÆzienten besitzt und 2 Z1 ist. Bewertungen von a lassen si hdann an ablesen, denn f=g ist eine Einheit in Zhxi. A hnli hes kann man au h
im Fall geeigneter Hauptidealringe R tun.

2.10.2 Der ganze Abs hlu von Rhxi in F

Der ganze Abs hlu von Rhxi im Funktionenkorper F ist ein freier Rhxi-Moduldes Rangs n, weil wir uns gema Proposition 2.27 in der Situation eines endli herzeugten, torsionsfreien Modulsuber einem Hauptidealring be nden. Eine Ganz
heitsbasis von Cl Rhxi; F kann im Prinzip mittels des Round-2-Algorithmus bere hnet werden (wel her beispielsweise in [9℄ und [17℄ bes hrieben wird). Wir
gehen hierauf aber ni ht naher ein.
2.29. Beispiel. Fur R = Z und k = Q betra hten wir den dur h f (x; y ) =y 2 4x3 1 erzeugten Funktionenkorper F = k(x; ) mit f (x; ) = 0. Wir su hen
Cl Zhxi; F . Unter Verwendung der Spur und Norm beliebig angesetzter Elemente sieht man wie im Fall quadratis her Zahlkorper, da wegen der Gestalt von f
Cl Zhxi; F = Zhxi[(1 + )=2℄ gilt.

32

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

2.10.3 Zusatzli he Bedingungen an Elemente aus L(D)Im Abs hnitt 2.1 haben wir L(D) als den S hnitt von Idealen (DS ) 1 und (DS ) 1
von oS beziehungsweise oS betra htet. Dur h S hnittbildung von L(D) mit einem
passend gewahlten Ideal a von Cl Rhxi; F konnen wir zusatzli h errei hen, da
die Fortsetzungen Gaus her Bewertungen von k(x) auf F auf den Elementen desDur hs hnitts vorgegebene Mindestwerte ubers hreiten.
2.30. Lemma. Es sei D ein Divisor von F=k und a ein Ideal von Cl(Rhxi; F ).
Dann ist L(D) \ a ein R-Modul. Es gibt Ideale b1 ; : : : ; bl von R und Elemente
u1 ; : : : ; ul 2 F mit l := dimk D, so da gilt:
L(D) \ a = b1 u1 +_ : : : +_ bl ul:
Beweis. Weil L(D) ein k-Vektorraum, a ein Rhxi-Modul und k \ Rhxi = R ist,sehen wir, da L(D) \ a ein R-Modul ist. Nun sei v1; : : : ; vl eine k-Basis von L(D)und z1 ; : : : ; zn eine Rhxi-Basis von a. Es gibt eine Matrix M 2 R[x℄nl und einen
gemeinsamen Nenner d 2 R[x℄ mit(z1 ; : : : ; zn)d 1M = (v1 ; : : : ; vl ):Zur Bestimmung des S hnitts L(D) \ a verwenden jetzt wir eine Reihe vonaquivalenten Bedingungen. Es sei d das Ideal von R mit dRhxi = dRhxi und
a = (v1 ; : : : ; vl ) mit  = (i )i 2 kl . Dann gilt
a 2 L(D) \ a , d 1 M 2 Rhxin ;, M 2 dRhxin:
Wir ersetzen nun jede Zeile von M dur h mehrere, aber endli
h vieleneue Zeilen,P0iund erhalten eine neue Matrix M : Fixiere eine Zeile i i;j x j 2 k[x℄1l mit
i;j 2 k . Diese wird dur h ( i;j )i;j ersetzt, wobei hierin no h Nullzeilen gestri henwerden. Wir haben dann M 0 2 Rml mit m  l, denn M und M 0 haben l k-linear
unabhangige Spalten. Die letzte, obige Bedingung fur  liest si h nun
a 2 L(D) \ a , M 0  2 dm :Bezei hnen wir den von den Zeilen von M 0 erzeugten R-Modul mit V . Dur hBere hnung der relativen Hermite-Normalform, siehe beispielsweise [10℄, fur die
Zeilen von M 0 erhalten wir Ideale b01 ; : : : ; b0l und unabhangige Zeilen s1; : : : ; sl 2
k1l , so da V = b01 s1 +_ : : : +_ b0l sl gilt. Es seien S die Matrix bestehend aus den
Zeilen s1 ; : : : ; sl , s01 ; : : : ; s0l die Spalten von S 1 und de niere bi := d=b0i fur alle1  i  l. Die A quivalenzenkette lat si h damit wie folgt weiterfuhren:a 2 L(D) \ a , v 2 d; (v 2 V );,  2 b1 s01 +_ : : : +_ bl s0l :2.10.

33


ZUSATZLICHE
BEWERTUNGSBEDINGUNGENDie Basiselemente ui erhalt man also dur h ui = (v1; : : : ; vl )s0i fur 1  i  l.




2.10.4 S hnitt von Cl k[x℄; F - mit Cl Rhxi; F -Idealen

Es sei a ein Ideal von Cl k[x℄; F  und b ein Ideal von Cl Rhxi; F . In diesem Abs hnitt soll die Struktur und eine Mogli hkeit zur Bere hnung von a \ b bes hrieben werden. Wir zitieren eine Proposition, die ubli herweise "Euklidis her S hritt\in Matrix-Normalform-Bere hnungen uber Dedekindringen genannt wird.
2.31. Proposition. Es seien v1 ; v2 linear unabhangige Elemente eines k-Vektorraums V und a1 ; a2 Ideale von R. Dann gibt es  2 a1 =(a1 + a2 )  R und  2
a2 =(a1 + a2 )  R mit  +  = 1, so da gilt:
a1 v1 +_ a2 v2 = (a1 + a2 )(v1 + v2 ) +_ (a1 \ a2 )(v1

v2 ):Beweis. Siehe beispielsweise [10℄.

Das folgende Lemma entspri ht dem Korollar 1.7.
2.32. Lemma. Es sei M 2 k(x)nn regular. Dann gibt es ein U 2 Rhxinn undein V 2 k[x℄nn mit det U 2 Rhxi und det V 2 k , so da UMV 2 k[x℄nndiagonal ist.

Beweis. Wir nehmen an, da M si h in unterer triangularer Gestalt be ndet.
Dies kann beispielsweise dadur h errei ht werden, da M in die untere SpaltenHermite-Normalform gebra ht wird (bezugli h eines gemeinsamen Nenners, k[x℄ist Euklidis h).
Wir beweisen die Diagonalisierbarkeit von M zuerst fur n = 2 und setzen voraus,da si h M 2 k[x℄22 mit gemeinsamen Nenner h 2 k[x℄ tatsa hli h in unterer
Spalten-Hermite-Normalform be ndet. Wir fuhren jetzt eine induktive S hluweise uber endli h viele j 2 1 fur geeignet konstruierte Ideale aj ; j von Rhxi,
Elemente aj ; j ; dj 2 k[x℄ und Rhxi-Moduln Uj := aj (aj ; 0) + j ( j ; dj ) dur h. Fur
j = 1 sei a1 := 1 := Rhxi und


a1 0
:= M:
Z

1

d1

Dur h die na hfolgende Konstruktion weisen wir die Existenz eines r 2 1 na h,fur wel hes r = 0 gilt und ein T 2 k[x℄22 mit det(T ) 2 k und Ur = U1 T
existiert. Wir konnen dann a0 2 k[x℄, und analog 0, als das Produkt von ar undeinem Erzeuger von ar de nieren. Damit gilt dann
Ur = Rhxi(a0 ; 0) + Rhxi(0; 0) = U1 T:Z

34

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

Weil si h zwei Basen von Ur dur h eine Rhxi-unimodulare Transformation unters heiden, sehen wir s hlieli h, da die Diagonalmatrix M 0 2 k[x℄22 mit a0; 0
auf der Diagonalen dur h Rhxi-unimodulare Zeilen- und k[x℄-unimodulare Spaltenoperationen aus M wie gewuns ht hervorgeht. Fur den eingangs de nierten
gemeinsamen Nenner h 2 k[x℄ gibt es ein h0 2 k[x℄, so da hh0 2 Rhxi gilt. Es
genugt daher, M mit h0 zu multiplizieren, anstatt dur h h zu dividieren, womit
der Beweis fur n = 2 abges hlossen ware.
Die angekundigte Konstruktion erfolgt nun derart, da fur geeignete Matrizen
Tj +1 2 k[x℄22 mit det(Tj +1 ) 2 k die Bedingungendeg j < deg dj ;(2.33)
j 6= 0;deg(dj+1) = deg( j );Uj +1 = Uj Tj +1(2.34)
erfullt sind. Ohne Eins hrankung gilt (2.33) fur j = 1, weil si h M voraussetzungsgema in Hermite-Normalform be ndet.
Wenn die obigen Werte fur ein j 2 1 de niert sind und (2.33) gilt, bestimmen
wir die na hsten Werte fur j + 1 wie folgt: Es sei d1;j := aj aj = j \ k und d2;j :=j \ k . Damit haben wir
Uj = d1;j Rhxi( j ; 0) + d2;j Rhxi( j ; dj ):Proposition 2.31 zeigt, da
d1;j ( j ; 0) + d2;j ( j ; dj ) = (d1;j + d2;j )(j j + j j ; j dj ) + (d1;j \ d2;j )(0; dj )fur geeignete j ; j 2 R mit j + j = 1 und daher au h
Uj = (d1;j + d2;j )Rhxi( j ; j dj ) + (d1;j \ d2;j )Rhxi(0; dj )gilt. Mit der Polynomdivision j dj = j j + rj , deg(rj ) < deg( j ) de nieren wir
aj +1 := (d1;j \ d2;j )Rhxi; j +1 := (d1;j + d2;j )Rhxi;
aj +1 := dj ; dj +1 := j ; j +1 := rj ;j 1
Tj +1 :=
1 0 :Z

Im Fall j+1 6= 0 sind die Bedingungen (2.33) und (2.34) damit erfullt. Aufgrund
der Gradbedingung (2.33) gilt jedo h notwendigerweise na h einer endli
hen AnQr
zahl r von S hritten wie gewuns ht r = 0 und Ur = U1 T mit T := j=2 Tj .
Es sei nun s hlieli h n > 2 und M 2 k(x)nn in unterer Dreie ksgestalt. Dur hdie Diagonalisierung von 2  2 Teilmatrizen von M , die dur h die S hnitte der2.10.


ZUSATZLICHE
BEWERTUNGSBEDINGUNGEN

35

Zeilen i; n und Spalten i; n fur i = n 1; : : : ; 1 erhalten werden, konnen wir
alle Elemente bis auf das letzte Element der n-ten Zeile von M zu null ma hen.
Indem dies au h fur die anderen Zeilen dur hgefuhrt wird, lat si h M vollstandig
diagonalisieren.
Wir merken an, da sogar errei ht werden kann, da die Eintrage von M einen
Grad von ho hstens eins besitzen. Im Fall eines Hauptidealrings R konnen sie
sogar selbst als eins gewahlt werden.

2.35. Satz. Es sei a ein Ideal von Cl Rhxi; F , b ein Ideal von Cl k[x℄; F .
Dann ist a \ b ein R[x℄-Modul und es gibt Ideale a1 ; : : : ; an von R und eine Basis
w1 ; : : : ; wn von b, so da gilt:

a \ b = a1 [x℄w1 +_ : : : +_ an [x℄wn :Die Idealklasse des Produkts der aj in R ist eine Invariante von a \ b (verallgemeinerte Steinitz-Klasse).
Beweis. Der S hnitt Rhxi\ k[x℄ ist glei h R[x℄. a ist ein Rhxi-Modul und b ist ein
k[x℄-Modul, beide sind frei vom Rang n. Daher ist a \ b ein R[x℄-Modul und es
gibt eine regulare Matrix M 2 k(x)nn, wel he eine Basis von a (ges hrieben als

Zeile) in eine Basis von b transformiert. Wegen Lemma 2.32 konnen wir die Basisvon a und die Basis von b so wahlen, da M diagonal ist. Die KoeÆzienten einerk[x℄-Linearkombination der Basiselemente von b werden dur h M in eine k(x)Linearkombination der Basiselemente von a transformiert. Multipliziert mit den
Diagonaleintragen mussen diese in Rhxi liegen, was au h dur h Idealzugehorigkeitsbedingungen wie oben mit den aj unterBea htung von Proposition 2.27 ausQn
gedru kt werden kann. S hlieli h gilt j=1 aj = det M 1 Rhxi \ k und det M ist
modulo Multiplikation mit Einheiten aus Rhxi oder aus k[x℄ eindeutig de niert,
weshalb au h die Steinitz-Klasse eindeutig bestimmt ist.
2.10.5 Der ganze Abs hlu von R[x℄ in F

Weil es si h bei R[x℄ ni ht um einen Dedekindring handelt, kann man
 den Round2-Algorithmus ni ht ohne weiteres zur Bestimmung von Cl R[x℄; F heranziehen.
Unter Benutzung
der Einheitsideale
und mit der Beoba htung, da Cl R[x℄; F =Cl k[x℄; F \ Cl Rhxi; F gilt, stellt Satz 2.35 die Struktur von Cl R[x℄; F als
R[x℄-Modul klar und gibt daruber hinaus eine Methode zur Bestimmung einer"Pseudo\-Basis an.

36

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

2.36. Korollar. Es gibt Ideale a1 ; : : : ; an von R und k(x)-linear unabhangige Elemente v1 ; : : : ; vn 2 F , so da der Ring der R[x℄-ganzen Elemente von F die direkte
Summe

Cl R[x℄; F = a1 [x℄v1 +_ : : : +_ an[x℄vnist. Die Idealklasse des Produkts der aj in R ist die (verallgemeinerte) SteinitzKlasse von Cl R[x℄; F .

Das Korollar zeigt auerdem, da Cl R[x℄; F  projektiv ist, weil die Ideale aj
und aj [x℄ invertierbar sind. Fur R[x℄-Moduln ist dies im allgemeinen ni ht derFall, typis he Beispiele stellen gerade die ni ht invertierbaren Ideale von R[x℄dar, beispielsweise p[x℄+ R[x℄x, p ein Primideal von R. Einen anderen Beweis fur
den Fall eines Hauptidealrings R ndet man in [13, S. 192℄.
2.37. Beispiel. Fur den Funktionenk
orper in Beispiel 2.29 ist 1; (1 + )=2 au heine k[x℄-Basis fur Cl k[x℄; F , so da man Cl [x℄; F = [x; (1 + )=2℄ hat.
ZZ

2.10.6 Parametris he Basen von L(D) \ aSatz 2.1 zeigt die Existenz
einer parametris hen Basis von L(D), dur h die Basenfur alle L D +r(x)1, (r 2 ) lei ht angegeben werden konnen. Lemma 2.30 zeigt,
art werden,
wie eine Basis fur L(D) \ a erhalten werden
 kann. Es soll nun gekl
wie parametris he Basen fur L D + r(x)1 \ a angegeben werden konnen. Das
Hauptproblem liegt darin, da der Reduktionsalgorithmus in Korollar 1.7 Spalten
beliebig mit Elementen aus k skalieren mu und dadur h Ganzheitseigens haften
verloren gehen, die in Lemma 2.30 zuru kgewonnen werden. Wir benotigen eine
Proposition uber die Erganzung von Riemann-Ro h-Basen:
2.38. Proposition. Es seien v1 ; : : : ; vn 2 F und d1 ; : : : ; dn 2 fur D wie inSatz 2.1 und es sei w1 ; : : : ; wn eine beliebige Idealbasisvon (DS ) 1 . Wahle ganz
rationale Zahlen sj , so da wj 2 L D sj (x)1 fur 1  j  n gilt. Dann gibt
es eindeutig bestimmte l1 ; : : : ; ln 2 mit der Eigens haft, da die Vereinigungen
Ar [ Br der beiden Familien von Mengen
Ar = f xi wj j 0  i  sj + r; 1  j  n g;
Br = f xi vj j maxf0; lj + rg  i  dj + r; 1  j  n g

disjunkt sind und k-Basen von L D + r(x)1 fur alle r 2 ergeben.
Beweis. Da die lj eindeutig bestimmt sind, sofern sie existieren, folgt aus derBasiseigens haft von Ar [_ Br fur groes r und weil die vi k[x℄-linear unabhangig
sind. Ar [ Br  L(D + r(x)1) ergibt si h aus der Wahl der sj und dj .
Z

Z

Z

Z

2.10.

37


ZUSATZLICHE
BEWERTUNGSBEDINGUNGEN

Weil es si h bei L D + r(x)1 um einen Vektorraum handelt, kann Ar dur hgeeignete WahlPvon
Elementen xi vj zu einer Basis erganzt werden. Es seien ti;j 2nk[x℄ mit vj = i=1 ti;j wi . Wir sehen jetzt, da si h x vj , 0   dj + r, wegen
der KoeÆzientens hranken genau dann im Erzeugnis von Ar be ndet, wenn +deg(ti;j )  si + r fur alle 1  i  n gilt. Erhoht man das maximale dieser
Eigens haft um eins, so liegt x vj ni ht mehr im Erzeugnis von Ar . Daran erkenntman, da lj := minfsi deg(ti;j ) j 1  i  ng + 1 fur 1  j  n das Gewuns hte
leistet.
2.39. Satz. Es sei D ein Divisor von F=k und a ein Ideal von Cl(Rhxi; F ). Es
gibt ganzrationale Zahlen l0 ; r0 ; s , Ideale a ; bj von R und Elemente w ; uj von
F fur 1    n und 1  j  l0 , so da fur alle r  r0


L D + r(x)1 \ a =X1 n0is +ra xi w+X

1j l0

bj xr r0 uj

gilt, wobei alle Summen direkt sind.
Beweis. Wir de nieren die wj und aj wie in Satz 2.35 bezugli h des S hnittsa \ (DS ) 1 und ubernehmen ansonsten die Notation von Proposition 2.38 undihrem Beweis. Es sei weiter r0 2 Z mit sj + r0  0 und lj + r0  0 fur alle
1  j  n. Wir betra hten beliebige r  r0 und setzen r0 := r r0 , s0j := sj + r r0,
lj0 := lj + r r0 und d0j := dj + r r0 , so da s0j ; lj0  0 fur alle 1  j  n gilt. Mitdiesen Bezei hnungen haben wir

Ar = f xi wj j 0  i  s0j + r0 ; 1  j  n g;
Br = f xi vj j lj0 + r0  i  d0j + r0 ; 1  j  n g:

Wir wollen die Elemente von Br "parametris h\ modulo der Elemente von Ar
reduzieren: Dur h geeignetesPSubtrahieren
entfernen wir die Terme der Formniix wj 2 Ar P
ausn den0 x vj = =1 x t;j w 2 Br und erhalten die Aussage: Es
gibt vi;j := =1 xs +10 ;i;j w , ;i;j 2 k[x℄ fur 1  ; j  n und lj0  i  d0j , soda die Di erenzen xr (xi vj vi;j ) im Erzeugnis von Ar liegen und Ar [_ Br0 mit


0

Br0 := f xr vi;j j 1  j  n; lj0  i  d0j geine k-Basis von L D + r(x)1 fur alle r  r0 bildet. Wir bemerken, da die vi;jbeziehungsweise ;i;j von r unabhangig sind.
Fur ein beliebiges Element a 2 L D + r(x)1 gibt es ein hj 2 k[x℄ mit deg(hj ) 38

KAPITEL 2.

KONSTRUKTIVE RIEMANN-ROCH-THEORIE

s0j + r0 und i;j 2 k fur 1  j  n und lj0  i  d0j , so da a dur h
a =

=

n
X
j =1
n
X
 =1

hj wj + xrh w +

0X

n
X
 =1

i;j

i;j vi;j0 0xs +r +1

X
i;j



i;j ;i;j w

eindeutig dargestellt wird. Man bea hte, da die beiden Summen keine Terme derForm x w gemeinsam haben. Na h Satz 2.35 gilt nun
Xa 2 a , h 2 a [x℄ und
i;j ;i;j 2 a [x℄; (1    n):i;j

Die auf der re hten Seite stehende, zweite Bedingung ist unabhangig von r. Die
i;j , die diese Bedingung erfullen, bilden einen endli h erzeugten, torsionsfreien RModul, dessen Basis man ahnli h dem Vorgehen im Beweis von Satz 2.30 und wie
in [17, S. 78 .℄ bestimmen kann. Hieraus ergibt si h die zu beweisende Aussage.
2.10.7 Anwendungen

Anwendungen der Ergebnisse dieses Abs hnitts ergeben si h, wenn bei Spezialisierungen von x im Funktionenkorper Ganzheitsbedingungen bea htet werden sollen,
beispielsweise, wenn die Restklassenkorper Zahlkorper sind und man dur h die
Restbildung ganzalgebrais he Elemente beziehungsweise Minimalpolynome mit
ganzen KoeÆzienten erhalten mo hte.
Ein anderes Einsatzgebiet ergibt si h mit der Reduktion eines Funktionenkorpers
na h einer diskreten Bewertung (einem Primideal) des Konstantenkorpers, es sei
auf [13, S. 187 .℄ verwiesen. Man betra htet fur gewohnli h nur regulare Primideale oder Primideale guter Reduktion. Der obige Ansatz ist jedo h vollig allgemeingultig und kann somit fur beliebige diskrete Bewertungen beziehungsweise
Primideale angewendet werden. Dur h die Betra htung des Dedekindrings R (undni ht nur des Bewertungsrings einer diskreten Bewertung) werden die Bere hnungen simultan fur alle Primideale von R ausgefuhrt.

Abs hlieend sei bemerkt, da die Klassenzahl von Cl Rhxi; F na h dem Irreduzibilitats- und Tragheitssatz aus [13, S. 187 .℄ endli h ist.

Kapitel 3
Divisorenklassengruppen

In diesem Kapitel werden die fur die Klassengruppenbere hnung relevanten theoretis hen Aussagen zusammengestellt. Die wi htigsten Ergebnisse sind die Herleitung einer S hranke an die Grade der fur die Erzeugung der Klassengruppebenotigten Stellen und die Angabe einer Formel fur die Approximation der Klassenzahl.
F=k bezei hnet einen globalen Funktionenkorper uber dem exakten, endli hen
Konstantenkorper k mit dem Ges hle ht g. Die Charakteristik von k sei p, die
Elementanzahl q. In einem fest gewahlten, algebrais hen Abs hlu F von F sei
kr die Erweiterung von k vom Grad r und Fr =kr mit Fr = F kr die Konstantenkorpererweiterung von F=k vom Grad r.

3.1 Grundlagen
3.1.1-Reihen und Satz von Hasse-Weil

L

Unter einem Charakter  endli her Ordnung einer abels hen Gruppe G verstehen wir einen Homomorphismus G !  , dessen Kern endli hen Index in G
besitzt. Der Haupt harakter  = 1 ist der Charakter endli her Ordnung von G
mit ker  = G.
3.1. De nition. Die zu einem Charakter  endli her Ordnung der Divisorenklassengruppe C l(F=k) de nierte formale PotenzreiheX
L(; t) :=([D℄)  tdeg DCD0

heit die L-Reihe von . Die Summe erstre kt si h hierbei uber alle positiven Divisoren. Fur  = 1 spri ht man von der Zeta-Funktion von F=k, die wir mit F=k (t)bezei hnen.
39

40

KAPITEL 3.

DIVISORENKLASSENGRUPPEN

Es sei bemerkt, da si h die Analogie zum Zahlkorperfall mit t = q s ergibt. Wegen der Orthogonalitatsrelationen sind mitunter Fallunters heidungen notwendig.
Hierfur de nieren wir  := 1, wenn  einges hrankt auf C l0 (F=k) der Haupt harakter ist, und  := 0 andernfalls.
3.2. Satz. (i) Eine L-Reihe L(; t) erfullt die Funktionalglei hungL(; t) = ([W ℄) q g 1 t2g 2 L(; 1=(qt));
wobei W einen kanonis hen Divisor bezei hnet.

(ii) Eine L-Reihe L(; t) besitzt die folgenden Darstellungen (als formale Potenzreihen):L(; t) =Y

1

P 2P l(F=k)

([P ℄)  tdeg P= (1 t)(1
= exp

1
X
r=1

qt)

 

tr

Nr () 

r

 1

2(g Y
1+ )
i=1

!

(3.3)

(1

!i ()  t)

(3.5)

;

wobei die !i () 2 C  ganzalgebrais he Zahlen sind undNr () :=X

deg(P )jr

deg(P )  ([P ℄)r= deg(P )= ( + 1)
qr

(3.4)

2(g X
1+ )i=1(3.6)!i ()r

(3.7)

gilt.
Beweis. Teil (i), Teil (ii) (3.3) und (3.4) folgen aus [12, S. 59{67℄ mit t = q s.

Man verglei he au h [33, S. 48 .℄ und [55, S. 158 .℄.
Der Beweis von (3.5) erfolgt dur h Anwendung von log und exp auf die davor
stehenden Darstellungen, wobei mit formalen Potenzreihen gere hnet wird. Aus(3.3) ergibt si h:

 X

deg
P
L(; t) = exp
log 1 ([P ℄)  t
= exp
= exp

P
X X
1

P r=1
X
1
tr =r
r=1

([P ℄)X

deg(P ) j r tdeg P r = rdeg(P )  ([P ℄)r= deg(P )



:

3.1.

41

GRUNDLAGEN

Aus (3.4) ergibt si h:L(; t) = exp 

= exp

1
X
r=1

X
1
r=1

tr

tr =r


qt r =r

+( )



 (

qr

+ 1)

2(g X
1+ ) X
1
i=1

2(g X
1+ )i=1

r=1(!i()  )!i ( )

rt r =r:

Dur h KoeÆzientenverglei h erhalt man (3.5), (3.6) und (3.7).
3.8. Korollar. Es sei  ein Charakter endli her Ordnung von C l(F=k). Dur h :=  Æ NFr =F wird ein Charakter endli her Ordnung auf C l(Fr =kr ) de niert,fur den Nd ( ) = Nrd () fur alle d 2 Z1,  =  und !i ( ) = !i ()r fur alle1  i  2(g 1 + ) mit geeigneter Sortierung gilt.
Beweis. Der zuru kgezogene Charakter  ist von endli her Ordnung, weil sein
Bild endli h ist. Eine Stelle P von F=k mit deg(P ) j r wird in Fr =kr in deg(P )Stellen des Grads eins zerlegt. Hieraus ergibt si h N1 () = Nr (). Indem diesfur  :=  Æ NFdr =Fr angewendet und die Transitivitat der Norm bea htet wird,
sieht man Nd () = N1( ) = Nrd(). In dieser Glei hung steht wegen (3.7) auf
beiden aueren Seiten eine Summe von 2g + 2 d-ten Potenzen fur alle d 2 Z1,

die na h den Newton-Relationen bis auf Vertaus hung ubereinstimmen mussen.
Weil die !i() beziehungsweise !i() unglei h null sind, folgt  =  und!i ( ) = !i ()r na h geeigneter Sortierung.
Fur den Haupt harakter  = 1 s hreiben wir statt Nr () au h Nr (F=k) und statt!i () au h !i(F=k). Man sieht, da Nr (F=k) glei h der Anzahl der Stellen vom
Grad eins in der Konstantenkorpererweiterung Fr =kr ist.
Das Zahlerpolynom der Zeta-Funktion von F=k (Fall  = 1) in (3.4) wird das LPolynom von F=k genannt. Das L-Polynom enthalt einige wi htige Informationenuber den Funktionenkorper F=k. Es erfullt eine Funktionalglei hung, die manlei ht aus der fur L-Reihen ableitet, und kann als harakteristis hes Polynom
eines Frobeniusendomorphismus aufgefat werden (die KoeÆzienten mussen dazu
in ihrer Reihenfolge vertaus ht werden). Wir benotigen fur unsere Zwe ke nur den
folgenden
3.9. Satz. Fur das L-Polynom L(t) von F=k gilt:
L(1) = q g L(1=q ) = h(F=k):
Beweis. Siehe [55, S. 166℄

42

KAPITEL 3.

DIVISORENKLASSENGRUPPEN

Der folgende Satz gehort neben dem Satz von Riemann-Ro h zu den wi htigsten
Satzen uber globale Funktionenkorper:
3.10. Satz (Hasse-Weil). Fur einen Charakter  endli her Ordnung der Divisorenklassengruppe C l(F=k) gilt:

j!i()j = q1=2 ; fur 1  i  2(g 1 + ):
Beweis. In [55, S. 169 .℄ und [33, S. 59 .℄ wird die Aussage fur den Haupt harakter  = 1 na h der Methode von Bombieri und Stepanov bewiesen. Der Ori-

ginalbeweis ndet si h in [59℄.
Fur andere Charaktere  6= 1 endli her Ordnung benotigt man Klassenkorpertheorie: Mit [2, S. 70 .℄ gibt es eine (eindeutige) endli he, abels he und an allen
Stellen unverzweigte Erweiterung E=F , so da C l(F=k) = ker  unter dem Artinsymbol isomorph zur Galoisgruppe Gal(E=F ) ist. Es sei k1 der exakte Konstantenkorper von E . Die benotigte und hieraus folgende Aussage ist, da der
Relativgrad f (P 0jP ), [55, S. 110℄, fur eine Stelle P 0 von E=k1 uber der Stelle
P von F=k mit der Ordnung von [P ℄ in C l(F=k) = ker  ubereinstimmt. Entsprehend der U berlegungen aus [22, S. 217, Thm. 6, i)℄ und [12, S. 148 .℄ (vgl. au h[34, S. 547 .℄) ist die Zeta-Funktion von E=k1 dann das Produkt der L-Reihen
zu Charakteren 0 von C l(F=k) mit ker   ker 0:YE =k1 t[k1 :k℄ =L(0 ; t):ker ker 0Daher ndet man die !i()[k1:k℄ unter den !j (E=k1), fur die die Betragsaussage
mit q[k1:k℄ statt q bereits bewiesen ist.
Wegen Satz 3.2, (3.7) hat dieser Satz eine unmittelbare Auswirkung auf die Zahlen
Nr () und alle si h daraus ergebenden Groen. Wir erhalten beispielsweise eine"e ektive\ Version des Primdivisorsatzes:
3.11. Satz. Fur die Anzahl r (F=k) der Stellen des Grads r von F=k gilt:(i) r (F=k) = (1=r) Pdjr (r=d)Nd(F=k), wobei  die Mobius-Funktion bezei hnet.

(ii) Man hat die folgende, explizite Abs hatzung
r=2rjr (F=k) qr j < (7g + 2)  q r :(iii) Ist g > 0, so gilt r1 (F=k)  1 fur jedes r 2 1 mit r  2 logq (2g) und
mindestens einem r1 jr.
Z

3.1.

43

GRUNDLAGEN

Beweis. Fur (i) und (ii) siehe [55, S. 178{180℄. (iii) beweisen wir wie folgt: Es sei
r 2 Z1 mit Nr (F=k) > 0. Also gibt es eine Stelle vom Grad eins in Fr =kr , unddiese Stelle ruhrt von einer Stelle P von F=k mit r1 := deg(P ) j r her. Aufgrund
von Satz 3.10 und Satz 3.2, (3.7) gilt Nr (F=k) > 0 fur alle r 2 Z1 mit qr + 1 >2gqr=2, wel hes mindestens dann gilt, wenn r  2 logq (2g) ist.

In F=k existiert also immer eine Stelle vom Grad kleiner glei h d2 logq (2g)e. Wir
merken an, da diese S hranke no h verbessert werden kann, beispielsweise mit
dem Tri k von Serre [55, S. 180℄.
Aus dem voranstehenden Satz und [28℄ erhalten wir die asymptotis he Aussage:
3.12. Lemma. Es sei " > 0. F=k dur hlaufe eine Folge von globalen Funktionenkorpern mit festem q und g ! 1. Fur die Anzahl der Stellen P von F=k mit
deg(P )  m und m  (2 + ") logq (g) gilt
m
X
j =1

j (F=k) =q qm=m  1 + o(1) :q 1( ) = PPmj=1 qj =j + O(mgqm=2). Mit
der Methodeaus [28℄ ergibt si h fur den Hauptterm mj=1 qj =j = qm=m q=(q1) + O(1=m) . Na h Ausklammern von qm=m ist der zuerst genannte Fehlerterm
glei h m2g=qm=2 und strebt na h Voraussetzung an m gegen null. Insgesamt folgt
daraus die Aussage.
Eine andere, unmittelbare Folgerung aus Satz 3.9 zusammen mit Satz 3.10 ist das"Brauer-Siegel\-ahnli he Resultat:
Beweis. Mit Satz 3.11 erhalt man

Pm
j =1 j F=k

3.13. Korollar. Fur die Klassenzahl von F=k gelten die Abs hatzungen:(q1=2 1)2g  h(F=k)  (q1=2 + 1)2g :Hierdur h wird jedo h das asymptotis he Verhalten von h(F=k)=qg , an dem manhau g interessiert ist, ni ht besonders genau bes hrieben.
3.1.2 Struktur der KlassengruppeFur eine abels he Gruppe G und d 2 bezei hnen wir die Untergruppe derd-Torsionselemente mit G[d℄ := f g 2 G j dg = 0 g.
Es sei k der algebrais he Abs hlu von k in F . Wir betra hten die Konstantenkorpererweiterung F k=k:
Z

44

KAPITEL 3.

DIVISORENKLASSENGRUPPEN

3.14. Satz. Fur ` 2 Z1 mit p - ` ist C l0 (F k)[`℄ = (Z=`Z)2g; fur r 2 Z1 ist
C l0 (F k)[pr ℄ = (Z=prZ)(F=k), wobei (F=k) die Hasse-Witt-Invariante von F=kbezei hnet. Fur diese gilt 0   (F=k)  g .
Beweis. Fur die erste Aussage mit ` siehe [14℄. Fur die zweite Aussage und mehruber die Hasse-Witt-Invariante siehe [54℄.
Bei diesem Satz handelt es si h ebenso wie bei Satz 3.10 eigentli h um eine fur
abels he Varietaten allgemein gultige Aussage, vgl. [32℄. Fur asymptotis he Aussagen bei wa hsender, aber endli her Konstantenkorpererweiterung siehe [42℄.
Wir s hlieen aus diesem Satz, da die Klassengruppe C l0 (F=k) von F=k (endlihes k !) in Elementarteilergestalt ein Produkt von 2g zyklis hen Gruppen ist undda es ein Erzeugendensystem von maximal 2g Divisorenklassen gibt.

3.2 Bes hrankte Erzeugung
Jede Divisorenklasse [D℄ wird dur h Divisoren D modulo Hauptdivisoren dargestellt, und jeder sol he Divisor setzt si h seinerseits aus Stellen zusammen. Unter
allen Divisoren der Klasse [D℄ gibt es nun naturli h sol he, bei denen das Maximum der Grade der beteiligten
Stellen minimal wird. Diese Zahl nennen wir denMinimalgrad md [D℄ von [D℄. Der Minimalgrad der Klasse des Nulldivisors wird
als null de niert.
3.15. Proposition.
ur g > 0 gibt es einen Divisor D vom Grad eins mit Mi Fnimalgrad md [D℄  d2 logq (2g )e + 1.
Beweis. Setze r := d2 logq (2g )e. Na h Satz 3.11, (iii) gibt es eine Stelle P1 vomGrad r1 j r und eine Stelle P2 vom Grad r2 j (r + 1). Weil r1 und r2 teilerfremd
sind, gibt es l1 ; l2 2 mit l1r1 + l2r2 = 1. Hieraus erhalt man mit A1 := l1P1 + l2 P2einen Divisor der gesu hten Art.
Es sei angemerkt, da es ubli herweise Stellen vom Grad eins gibt, die man fur
A1 verwenden kann. Der Fall g = 0 wird hier und in folgenden Abs hatzungen
nur wegen der log-Ausdru ke ausges hlossen. Wir wollen nun Aussagen uber die
Minimalgrade von Erzeugendensystemen von C l0 (F=k) herleiten.
3.16. Satz. Es sei  ein Charakter endli her Ordnung von C l(F=k), dessen Eins hrankung auf C l0 (F=k) ni ht den Haupt harakter ergibt. Gilt fur die Anzahl derZ

Stellen vom Grad eins von Fr =kr

Nr (F=k) > (g1)2qr=2;

3.2.

45


BESCHRANKTEERZEUGUNG

so existiert eine Stelle P von F=k vom Grad kleiner glei h r mit [P ℄ 6= 1:

Diese Unglei hung gilt immer fur r 2 Z1 mit q r  (2gdere, wenn r  2 logq (4g 2) fur g > 0 ist.

1)2qr=2, also insbeson-

Beweis. Wir ziehen Satz 3.2, (3.6) und (3.7) heran: Weil die Charakterwerte Einheitswurzeln sind, gilt Nr (F=k)  jNr ()j fur alle r 2 Z1, und im Fall der Unglei hheit gibt es einePStelle
P eines Grads kleiner glei h r von F=k mit  [P ℄ 6= 1.
2
g 2
Na h Satz 3.10 gilt j i=1 !i()r j  (g 1)2qr=2. Dur h Umstellen sieht man nun,da die im Satz angegebenen Abs hatzungen Nr (F=k) > jNr ()j erzwingen.

3.17. Satz. Es sei A1 ein Divisor vom Grad eins von F=k und r 2 Z1 wie inSatz 3.16. Es sei weiter S := P lr (F=k) [ supp(A1 ). Dann gilt

D 0 ( S ) =P ( S ) = C l0 (F=k):

Beweis. C l(F=k) ist das (innere) direkte Produkt von C l0 (F=k) und der von[A1 ℄ erzeugten Gruppe. Wir konnen daher jeden Charakter  von C l0 (F=k) auf
C l(F=k) dur h  [A1 ℄ = 1 fortsetzen.
Na h Satz 3.16 gibt es einen Divisor D
mit md [D℄  r und  [D℄ 6= 1, sofern  auf C l0 (F=k) ni ht trivial war.
Wir setzen[D0℄ := [D℄ deg(D)[A1℄ und beoba
hten, da [D0℄ 2 D0(S ) +P (F=k) =P (F=k) = D0(S )=P (S ) und  [D0℄ 6= 1 gilt. Die Charaktergruppevon G := C l0 (F=k)=H , wobei H die von allen sol hen [D0℄ erzeugte Untergruppe bezei hnet, kann demna h nur aus dem Haupt harakter bestehen, so da G(aufgrund der Dualitat) trivial ist, also H = C l0 (F=k) gilt. Weil H wegen derErzeugung isomorph zu einer Untergruppe von D0(S )=P (S ) ist, ergibt si h die zu

beweisende Aussage.

3.18. Korollar. Mit r0 2 Z1 werde das Maximum des Minimalgrads eines Divisors A1 vom Grad eins von F=k und einem r wie in Satz 3.16 bezei hnet. Die
Klassengruppe C l0 (F=k) besitzt dann ein Erzeugendensystem [D1 ℄; : : : ; [Dl ℄, bestehend aus maximal 2g Elementen, mit

md [Di℄  r0 fur 1  i  l:Fur den Minimalgrad jeder Klasse [D℄ von C l(F=k) gilt daher md [D℄  r0 :Beweis. C l0 (F=k) besitzt ein Erzeugendensystem mit wie oben bes hrankten Minimalgraden na h dem vorangegangenen Satz. Diese Bes hrankung des Minimalgrads gilt weiter fur jede Klasse [D℄ von C l(F=k), insbesondere fur jedes maximal 2g-elementige Erzeugendensystem von C l0 (F=k), wel hes na h Satz 3.14
existiert.

46

KAPITEL 3.

DIVISORENKLASSENGRUPPEN

3.19. Bemerkung. Man bea hte, da fur g > 0 allgemeinr0  maxf d2 logq (4g2)e; d2 logq (2g)e + 1 g

errei ht werden kann.
Ein ahnli hes Ergebnis wurde bereits in [53, S. 145 .℄ na h der analogen Methodevon [4℄ fur Zahlkorper bewiesen. Die obige S hranke ist jedo h etwas s harfer,
und der Beweis ist wesentli h kurzer.

3.3 Approximation der Klassenzahl
Die Klassenzahl kann "analytis h\ approximiert werden. Wir wollen die hierfurbenotigte Formel mit explizitem
Fehlerterm angeben und die Verbindung zu einem
Eulerprodukt erklaren.
3.20. Satz. Fur die Klassenzahl h(F=k) und r0 2 0 gilt:Zh F=k = q g

log (

)

+

2g
r0
X
q rX
r=1

r

i=1

!i(F=k)r 

2g  q r0=2 :q 1=2 1 r0 + 1

Beweis. Es sei x ein separierendes Element von F=k. Der Quotient der Zetafunktion von F=k und der Zetafunktion von k(x)=k ergibt gerade
das L-Polynom L(t)P2gr
von F=k. Ferner wissen wir, da Nr (F=k) = q + 1 i=1 !i(F=k)r und daNr (k(x)=k) = q r + P
1 gilt.
Anhandvon Satz3.2, Glei hung (3.5) ergibt si h daP2g
1rr
her L(t) = exp
r=1 t =r i=1 !i (F=k ) . Weil die Reihe im exp-Argumentfur t = q 1 absolut konvergiert und der Wert des L-Polynoms na h Satz 3.9
dort glei h h(F=k)=qg ist, stimmt ihr Grenzwert mit log h(F=k)=qg uberein. Der
Fehlerterm ergibt si h dann dur h folgende Re hnung:
1
X

2g
q rX
!i (F=k)rr
r=r0 +1i=13.21. Bemerkung. Wegen1
r0 + 1 r=2
2
g Xq
 r +1r0
r=r0 +1
+1 1
r0 =2
2
gq 02 X r + 1 (q 1=2)r  q1=22 g 1  rq + 1 :
0
0
r=0
r

P2g
r
i=1 !i F=k
Nr F=k() = qr + 1 Nr (F=k) sind zur Approximation der Klassenzahl die Werte ( ) zu bestimmen, vgl. S. 7.

3.3.

47

APPROXIMATION DER KLASSENZAHL

Unter Verwendung von Satz 3.2, (3.3) konnen wir wie eben im Beweis den Quotienten der Zetafunktionen bilden und erhalten in Analogie zur Zahlkorpersituation,[5℄, [23, S. 26 .℄, na h Sortierung der Faktoren ein Eulerprodukt
1YY

r=1 P0 2P lr (k(x)=k)

(1

tr )

Y
P 2P lr (F=k)(1

tr ) 1 :Man kann zeigen, da dieses Produkt fur t = q 1 gegen h(F=k)=qg konvergiert
und da die Partialprodukte bis r = r0 mit dem exp-Wert obiger Partialsummen
bis r = r0 ubereinstimmen. Wir benotigen diese Aussagen im folgenden aber ni ht
weiter.
Die obige Restgliedabs hatzung ergab si h verglei hsweise lei ht aus der einfa hen
Abs hatzung der !i(F=k) mit Satz 3.10 und ist fur den angestrebten Verwendungszwe k ausrei hend. S harfere Abs hatzungen lassen si h eventuell mit derOesterle-S hranke erzielen, vgl. [3, S. 48℄.
Mit Satz 3.20 ist man au h in der Lage, das Groenverhaltnis der Klassenzahl
zum Wert qg asymptotis h zu untersu hen. Wir erhalten das folgende A quivalentzum Satz von Brauer-Siegel fur Zahlkorper:
3.22. Satz. Es sei " > 0. F=k dur hlaufe eine Folge von globalen Funktionenkorpern mit festem q und g ! 1. Wir nehmen an, da F=k einen rationalen
Teilkorper k(x) mit n = n(g ) := [F : k(x)℄ besitzt. Dann giltlog (h(F=k) = qg )  1 + o(1)  (n 1)  log (2 + ") logq (g) :Beweis. Wir wahlen r0 2 mit 2 logq (g )  r0  (2 + ") logq (g ), was fur hinreihend groes gmogli h ist, und wenden Satz 3.20 an. Der Fehlerterm 2g= (q1=21)qr0=2 (r0 + 1) strebt dabei wegen der Wahl von r0 fur g ! 1 gegen null. Wir
betra hten nun den Approximationswert fur log(h(F=k)=qg ) aus Satz 3.20. Die
Anzahl der Stellen vom Grad eins von Fr =kr lat si h na h oben bes hranken
dur h Nr (F=k)  n(qr + 1),P2weiluber jeder Stelle von kr (x)=kr ho hstens n Stelg
len von Fr =kr liegen. Mit i=1 !i(F=k)r = Nr (F=k) (qr +1)  (n 1) (qr +1)
erhalt man
Z

r0
X
r=1

q r =r

2g
X

!i (

i=1
Pr0
r=1

)  (n 1)

F=k r



r0
X
r=1

q r (q r + 1)=r:

Unter Bea htung von
1=r = 1 + o(1) log(r0) und weil die geometris he
Reihe bes hrankt ist, lat si h diese Summe dur h 1 + o(1) (n 1) log(r0)abs hatzen, wobei mit o(1) von n unabhangige Funktionen bezei hnet werden,

48

KAPITEL 3.

DIVISORENKLASSENGRUPPEN

die fur g ! 1 na h null streben. Weil der Fehlerterm gegen null geht, erhalt man
insgesamt log(h(F=k)=qg )  1 + o(1) (n 1) log(r0 ), woraus die Behauptung
wegen r0  (2 + ") logq (g) folgt.
Dieser Satz besagt also, da der Quotient h(F=k)=qg nur relativ s hwa h wa hsen(oder fallen) kann, sofern die Erweiterungsgrade n genugend s hwa h mit g wa hsen. Auf ahnli he Weise wie eben kann man allgemeiner zeigen, da h(F=k)=qg
nie exponentiell in g fallt, und da h(F=k)=qg exponentiell in g wa hst, wenn beispielsweise die Anzahl der Stellen vom Grad eins asymptotis h gro wird. Dazu
sei auf [40℄ verwiesen.

3.4 Cartier-Operator, p-Torsion der Klassengruppe und Hasse-Witt-Invariante
In diesem Abs hnitt bezei hnet F=k einen algebrais hen Funktionenkorper uber
dem exakten Konstantenkorper k, wobei k entweder der endli he Korper mit q
Elementen oder der algebrais he Abs hlu eines sol hen ist. Die p-Torsion der
Klassengruppe C l0 (F=k) ist isomorph zu einem p -Vektorraum von Di erentialen.
Aufgrund dieser Isomorphie und unter Benutzung des Cartier-Operators lassen
si h sowohl der p-Rang der Klassengruppe als au h die Hasse-Witt-Invariante von
F=k bestimmen. Dies soll im folgenden erlautert werden.
Zusatzli h zu den in Abs hnitt 1.1 gegebenen De nitionen und Aussagen uber
Di erentiale benotigen wir die folgenden: Der Raum der holomorphen Di erentiale, also derjenigen Di erentiale ohne Polstellen, wird mit 1 (F=k) := (D),D der Nulldivisor von F=k, bezei hnet. Anhand
des Satzes von Riemann-Ro h1uberlegt man si h lei ht, da dim (F=k) = g gilt. Ein Di erential ! heit
exakt, wenn ! = da fur ein a 2 F gilt. Ein Di erential ist von der dritten Gattung, wenn seine Polstellen mit der Ordnung eins auftreten. Der Raum dieser
Di erentiale wird mit 3 (F=k) bezei hnet. In Charakteristik p > 0 bestehen die
Di erentiationskonstanten a 2 F mit da = 0 genau aus den p-ten Potenzen F p.
Fur a; x 2 F und x separierend ist die p-te Ableitung dpa=dxp = 0, so da es si hbei der (p 1)-ten Ableitung um eine p-te Potenz handelt.
Ein wi htiger Teilraum von 3 (F=k) ergibt si h mit den logarithmis hen Di erentialen, wel he Di erentiale der Form (1=a) da mit a 2 F  sind. Dieser Raumwird mit log (F=k) bezei hnet. Dur h a 7! (1=a) da erhalt man namli h einen
Homomorphismus F  ! log (F=k), dessen Kern (F)p ist. Man wei, da
vP (a)  0 mod p genau dann gilt, wenn
ur das Resi vP ((1=a) da)  0 ist (fduum gilt zum Beispiel resP (1=a) da  deg(P ) vP (a) mod p). Fur diese undweitere Aussagen uber Di erentiale siehe [11, 13, 33, 55℄.
F

3.4.

49

CARTIER-OPERATORDie Verbindung zur p-Torsion der Klassengruppe wird nun wie folgt hergestellt:
3.23. Satz. Es sei [D℄ 2 C l0 (F=k)[p℄. Dann ist pD = (a) fur ein a 2 F  .
Die Abbildung

C l0 (F=k)[p℄ ! 1 (F=k) \ log (F=k); [D℄ 7! (1=a) da
ist ein Isomorphismus (von F p -Vektorraumen).
Beweis. Wir verweisen auf [51, S. 41℄.

Aufgrund dieses Satzes sind wir an der Bestimmung von 1 (F=k) \ log (F=k)
interessiert. Den Raum 1 (F=k) konnen wir mit Abs hnitt 2.9 bere hnen. Zur
Bestimmung der hierin enthaltenen logarithmis hen Di erentiale wird der CartierOperator eingesetzt.
3.24. De nition. Es sei x ein separierendes Element von F=k. Der CartierOperator C von F=k wird wie folgt de niert:
C : (F=k) ! (F=k); C (! ) := dp 1 (!=dx)=dxp 1 1=p dx;
wobei unter der (1=p)-ten Wurzel die (p 1)-te Ableitung von !=dx 2 F gebildet
wird. Man kann zeigen [29, S. 307 .℄, da diese De nition ni ht von der Wahl desseparierenden Elements x abhangt. Zur Bere hnung der Werte C (!) bea hten
wir Abs hnitt 2.9 und die Tatsa he, da a 7! ap mit a 2 F ein injektiver, p linearer Ringhomomorphismus ist. Fur eine k(x)-Basis a1; : : : ; an von F gibt es
ein M 2 k(x)nn, so da fur beliebiges a = (ai)i mit  2 k(x)n1
ap = (a1 ; : : : ; an )Mp
gilt,
wobei
p aus  dur h p-Potenzierung der KoeÆzienten entsteht. Weil die
ap1 ; : : : ; apn wegen F p \ k(x) = k(x)p linear unabhangig uber k(x) sind, ist M
invertierbar und man kann lei ht na h  au osen.
3.25. Satz. Es sei ! 2 (F=k).
(i) Der Cartier-Operator ist p -linear,(ii) C (zp !) = zC (!) fur jedes z 2 F: C ist also (1=p)-linear und C n ist p FFlinear.

F n(iii) Ist ! an einer Stelle holomorph, so ist C (!) an derselben Stelle ebenfalls
holomorph.

(iv) C (!) = 0 gilt genau dann, wenn ! exakt ist,

50

KAPITEL 3.

DIVISORENKLASSENGRUPPEN(v) C (!) = ! gilt genau dann, wenn ! logarithmis h ist.
Beweis. Wir verweisen auf [29, S. 307 .℄. Die beiden letzten Eigens haften werden
dort nur fur F k=k formuliert, behalten hier aber ihre Gultigkeit (fur ! = adx
bedeutet C (!) = ! per De nition ap = dp 1a=dxp 1, die dortige S hluweise
wird ni ht benotigt). Verglei he au h [2, S. 29 .℄.
Die Kombination der beiden vorangegangenen Satze zusammen mit Aussagenuber p- beziehungsweise (1=p)-lineare Abbildungen (vgl. [21℄, [51℄) ergibt nun den
folgenden Satz, den wir [45℄ entnehmen:
3.26. Satz. Es sei F=k ein globaler Funktionenkorper uber dem exakten Konstantenkorper k der Charakteristik p.
(i) Es gilt
1 (F=k ) \ log (F=k ) = ker (1 C ) j 1 (F=k );wobei 1 (F=k) als F p -Vektorraum aufgefat wird.

(ii) Es sei !1; : : : ; !g eine k-Basis von 1 (F=k) und C g (!i) = Pgj=1 dj;i!j mit
einer Matrix (di;j )i;j 2 kgg . Dann gilt
 (F=k) = rank (di;j )i;j :Mit diesem Satz lat si h die Bere hnung des p-Rangs der Klassengruppe na h (i)und der Hasse-Witt-Invariante na h (ii) auf lineare Algebra zuru kfuhren. Im
Verglei h zum spater vorgestellten, allgemeinen Verfahren der Klassengruppenbere hnung kann man hiermit Funktionenkorper mit wesentli h hoherem Ges hle ht
und groerem Konstantenkorper behandeln. Fur ein Beispiel verweisen wir auf
den Abs hnitt 7.6.
Wir bemerken ferner, da Satz 3.23 zur eÆzienten Bere hnung diskreter Logarithmen in der p-Torsion verwendet werden kann [46℄ und da das harakteristis he
Polynom von C n, jkj = q = pn, unter einer weiteren Voraussetzung mit dem LPolynom von F=k modulo p (na h Umkehrung der Reihenfolge der KoeÆzienten)ubereinstimmt [30, 45℄, vgl. au h [54℄.
Im Hinbli k auf die spatere Bestimmung von S -Einheiten des globalen Funktionenkorpers F=k betra hten wir s hlieli h no h den Homomorphismus (oS ) !
3 ( D ) \ log (F=k ), a 7! (1=a) da f
ur endli hes S  P l(F=k) mit jS j > 1
und D := PP 2S P . Diesen letzteren Raum konnen wir wie oben mit Hilfe desCartier-Operators bere hnen und ahnli h wie in [2, S. 29 .℄ lassen si h dann fur
! 2 3 ( D) \ log (F=k) sogar Elemente b 2 F  mit ! = (1=b) db bestimmen. Ess heint allerdings ni ht mogli h zu sein, hieraus brau hbare Informationen uberdie (unbekannten) S -Einheiten zu gewinnen.

Kapitel 4
Glattheitseigens haften

In diesem Kapitel bezei hnet F=k einen globalen Funktionenkorper vom Ges hle ht g uber dem exakten Konstantenkorper k mit q Elementen.
Wir stellen Untersu hungen uber die Anzahl positiver, glatter Divisoren an, wobei
wir hierfur sowohl eine exakte Formel als au h eine asymptotis he untere S hranke
angeben werden. Im letzten Abs hnitt wird die Glattheitsannahme formuliert, die
wir fur die Komplexitatsuntersu hungen des na hsten Kapitels benotigen.
Glattheitsaussagen fur globale Funktionenkorper s heinen in der Literatur bis
auf den rationalen und reell-quadratis hen Fall bisher ni ht betra htet worden zu
sein, siehe hierfur [35, 53℄.

4.1 Glattheitsfunktion
Die bisherige Glattheitsde nition fur einen Divisor wird wie folgt erweitert:
4.1. De nition. Es seien n; m 2 0. Ein positiver Divisor D von F=k heie(n; m)-glatt, wenn deg D  n und deg P  m fur alle Primdivisoren P  D gilt.
Die Anzahl aller (n; m)-glatten Divisoren wird mit F=k (n; m) bezei hnet.
Man sieht, da F=k (0; m) = F=k (n; 0) = 1 gilt, da der Nulldivisor mitgez
 ahltnnwird. Fur den folgenden Satz bea hte man m := 0 fur 0  n < m und 0 := 1fur n 2 .
Z

Z4.2. Satz. Fur alle n; m 2 Z0 gilt:

(i)

(

)=

F=k n; mX

m Y
i F=k

1j1 ++mjm n i=151() + ji 1:ji

52

KAPITEL 4.

GLATTHEITSEIGENSCHAFTEN(ii) Mit NF=k (n; m) := P0<dm; djn dd (F=k) gilt
n F=k (n; m) =

n 1
X



j =0

1 + NF=k (nj; m)(j; m):

Beweis. Teil (i) ergibt si h wie folgt: Jeder (n; m)-glatte Divisor kann eindeutig
dur h m Summen von ji (ni ht unbedingt vers hiedenen) Stellen des Grads i fur
1  i  m dargestellt werden (leere Summen mitgeda ht). Fur jedes sol he i gibt
es genau i(F=kj)+i ji 1 dieser ji -elementigen Summen (Anzahl der Kombinationen
ji -ter Ordnung von i (F=k) Elementen mit Wiederholung, siehe [41, S. 465℄).
Der Teil (ii) ist komplizierter: Wir setzen

S (n; m) :=X

D (n; m)-glatt
D6=0

deg(D)

und evaluieren diesen Ausdru k auf zwei vers hiedene Weisen. Indem wir S (n; m)als Summe aller mogli hen Grade j multipliziert mit der Anzahl der (n; m)-glatten
Divisoren vom Grad j s hreiben, erhalten wir einerseitsnXS (n; m) =j  F=k (j; m)
F=k (j 1; m)
j =1

n 1
X

= n  F=k (n; m)

j =0

(

)

(4.3)

F=k j; mdur h Zusammenfassung der -Terme. Andererseits konnen wir die Grade deg(D)aber au h in ihre P -Beitrage aufteilen und na h diesen sortiert aufsummieren. Die
folgenden Summationen erstre ken si h uber jeweils alle freien Parameter (l; d 2
und P 2 P l(F=k)):X
X
X
1deg(P ) =deg P S (n; m) =

Z

=
=
=

D (n; m)-glatt
0<lP DX

deg(P )m0<l deg(P )n
n
X
j =1
n 1
X
j =0

deg(P )m0<l deg(P )ndeg(P )  F=k (n
(

j; m)

F=k n

X

0<dm

D (n; m)-glattlP Dl deg(P ); m)dd (F=k)

djj()  NF=k (nF=k j; mj; m):

Dur h Glei hsetzen von (4.3) und (4.4) ergibt si h die Formel in (ii).

(4.4)

4.2.

53

UNTERE SCHRANKEN

4.5. Bemerkung. Die Bere hnung von( ) kann mit Satz 4.2, Teil (ii)ganz praktikabel erfolgen, wohingegen si h Teil (i) dafur ni ht besonders eignet.
Zur Au osung der Rekursion bere hnet man die Werte F=k (j; m) fur 0  j  n
und hat dann einen Aufwand von O(n2) Operationen, die Kenntnis von NF=k (j; m)vorausgesetzt. Fur den Fall, da m  g relativ gro im Verhaltnis zu g ist,stellt letzteres das eigentli he Problem der Bere hnung dar, weil dafur die Werte von j (F=k) beziehungsweise Nj (F=k) bekannt sein mussen. Wir bemerken,da NF=k (n; m) = Nm (F=k) = qm + 1 P2i=1g !i(F=k)m fur n  m gilt. Wennur ein paar
F=k (n; m) nur approximiert werden soll, bere hnet man j (F=k ) fjkleine j und setzt fur die anderen j (F=k)  q =j . Vorteilhaft wirkt si h hier der
Umstand aus, da die Abwei hungen von j (F=k) von qj =j wegen Teil (ii) furgroere j immer weniger vom Gesamtwert von F=k (n; m) ausma hen.
F=k n; m

4.2 Untere S hranken
Es sollen nun asymptotis he Aussagen uber F=k (n; m) bewiesen werden.
4.6. Proposition. Es sei F=k ein globaler Funktionenkorper des Ges hle hts g
und "  1=2. Fur die Anzahl
der (n; m)-glatten Divisoren von F=k mit n; m 2 Z1
und m  2 logq 2(g + ") gilt dann
 j n kn+ 1 log(n) + g=" + 2 log 2(g + ") :F=k (n; m)  q = expm
Beweis. Wir setzen n = rm + b mit 0  b < m. Die Rekursion in Satz 4.2, (ii)wird dur h die auss hlieli he Betra htung der Terme fur j = maxfn m; 0g
aufgelost: F=k (n; m)  n 1(1+ NF=k (m; m)) F=k (n m; m) usw. und im letzten
S hritt F=k (b; m)  n 1 (1 + NF=k (b; b)). Wir erhalten insgesamt( )  (1=n)r+1(1 + NF=k (m; m))r (1 + NF=k (b; b)):(4.7)
m 2gq m=2 und 2gq m=2  g=(g + ")Zu bea hten ist im folgenden
 NF=k (m; m)  q
wegen m  2 logq 2(g + ") na h Voraussetzung. Wenn au h b  2 logq (2(g + "))ist, haben wir mit Ausklammern von q dur h Beru ksi htigung aller Terme desProdukts (4.7):
r+1 n
r+1
(4.8)
F=k (n; m)  (1=n) q (1 g=(g + ")) :Gilt andernfalls b < 2 logq (2(g + ")), so ergibt si h mit qb  2(g + ")2 und (1 +NF=k (b; b)) = q b  2(g +") 2 , indem der letzte Term des Produkts (4.7) fortgelassen
wird:
r+1 n
r
2
(4.9)
F=k (n; m)  (1=n) q (1 g=(g + ")) (2(g + ")) :F=k n; m

54

KAPITEL 4.

GLATTHEITSEIGENSCHAFTEN

Wir erhalten daraus die Behauptung in beiden Fallen fur g = 0 und fur g > 0
wegen log(1 1=x)  1=(x 1) fur x > 1 angewendet auf 1 g=(g + ") =1 1=(1 + "=g) mit x = 1 + "=g.
4.10. Satz. Es seien ; "0 2 >0 mit < 1 und q eine Primpotenz. Dann gibt
es ; Æ 2 , so da fur jeden globalen Funktionenkorper F=k vom Ges hle ht gRRuber dem exakten Konstantenkorper mit q Elementen die Unglei hung)  qn  exp u (log(u) + log(log(u)) + )fur u := n=m und alle n; m 2 Æ mitn  m;
minf m; u g  (2 + "0) logq (3g + 1)(

F=k n; mZ

gilt.

Beweis. Der Beweis basiert auf dem Vorgehen von [38℄ fur den Fall Z, vgl. [52℄.
Na h Voraussetzung gilt u > 1 fur m  1, so da wir b := (1 1= log(u))mde nieren konnen. Die na hfolgenden Abs hatzungen erfordern eine gewisse Mindestgroe der Parameter n; m; u; b, die wir mittels dem nur von ; "0; q abhangigen
Æ si herstellen. Fur den Anfang sei also Æ  1, wir werden es mehrfa h vergroern.
Wir bemerken als erstes, da mit Æ ! 1 au h u ! 1 wegen der Voraussetzungengilt. Wir vergroern Æ, so da b  1 erfullt ist.
Bis zum Beweisende bezei hnen wir nun mit D die Divisoren, die eine Summevon bu ni ht notwendigerweise vers hiedenen Stellen eines Grads > b und  msind und setzen d := deg(D). Damit gilt bbu < d  mbu  n, und man erhalt
die untere Abs hatzung
X
(
n;
m
)

(4.11)
F=k
F=k (n d; bb );Dweil die Trager der D und der dur h F=k (n d; bb ) gezahlten Divisoren disjunktsind. Wir s hatzen nun die F=k (n d; bb ) und dana h die Summe na h unten
ab. Die folgenden Unglei hungen werden dazu benotigt:
m(1 )=  u;
(4.12)
wel he aus den Voraussetzungen folgt, und(n d)=b  (n d)=bb  + 1
 2(n d)=b + 1  2(n=b bu ) + 1(4.13)
 2 (1 1= log(u)) 1u u + 1 + 1
 3u= log(u);

4.2.

55

UNTERE SCHRANKEN

wel he fur alle Divisoren D gilt (fur die zweite Abs hatzung verwenden wir bbu <d wie oben, und fur die letzte Abs hatzung ist eine ausrei hende Vergroerungvon Æ und damit u erforderli h).
Wenn n d = 0 ist, so gilt F=k (n d; bb ) = 1. Andernfalls wenden wir Proposition 4.6 mit " := (g + 1)=2 an. Dies ist zulassig aufgrund der Voraussetzungenan m und n. Unter Verwendung der Unglei hungen2 logq (2(g + ")) = 2 logq (3g + 1)  u
na h Voraussetzung,log(n d) = log((n d)=b) + log(b)  log(u) + log(m)wegen (4.13) fur ausrei hend groes Æ und wegen b  m na h De nition von b,undlog(m)  =(1 ) log(u)wegen (4.12) erhalt man dann mit Proposition 4.6 und (4.13)




n
d
n
d
= exp
F=k (n d; bb )  q
bb + 1 (log(n d) + 2) + 2 log(3g + 1)

 qn d= exp (3u= log(u)) (log(u) + log(m) + 2) + u(4.14)
 qn d= exp ( u);na h ausrei hend groer Wahl von Æ mit einer nur von ; "0; q abhangigen Konstante 2 >0 . Diese Unglei hung gilt fur alle Divisoren D (au h fur n d = 0).
Wir wenden uns jetzt der Abs hatzung der Summe in (4.11) zu. Wegen (4.14)
bekommt (4.11) die GestaltXnq d:(4.15)
F=k (n; m)  q  exp( u) R

Auf die Summe uber alle D greifen wir mittels
X
D

q d

=



X
b<deg(P )mqdeg(P )

Dbu

= bu !

(4.16)

zu, wobei si h die re hte Summe uber alle Stellen P mit b < deg(P )  m erstre kt (die bu -Potenz bildet die Summe aller Werte q d unter Bea htung der
Reihenfolge, weshalb dur h bu ! dividiert wird).
Na h wieder nur von ; "0; q abhangiger Vergroerung von Æ konnen wir aufgrund
der De nition von b annehmen, da wegen Satz 3.11, (ii) q j j (F=k)  1=m(7g +2)q b=2 =b fur b < j  m gilt und da wegen m=b ! 1 fur Æ ! 1 und wegen

56

KAPITEL 4.

GLATTHEITSEIGENSCHAFTEN(2 + "0) logq (3g + 1)  m na h Voraussetzung (7g + 2)mq b=2 =b  1=2 erfullt ist.
Unter Bea htung von m b = m= log(u) erhalten wir:Pdeg(P ) = P
jb<deg(P )m q
b<j m q j (F=k ) (m b) 1=m (7g + 2)q b=2=b (4.17)
 log(u) 1  1 (7g + 2)mq b=2 =b
 (2 log(u)) 1:
Wegen bu !  exp(bu log(bu )) ergibt si h aus (4.17), (4.16) und (4.15):
n
F=k (n; m)  q = exp u (log(u) + log(log(u)) + )fur Æ und , wobei die Summe der Konstanten log(2) aus (4.17) und aus (4.14)
ist.

4.3 Glattheitsannahme fu
 r reduzierte Divisoren
4.18. De nition. Es sei S eine ni ht-leere Teilmenge von P l(F=k). Fur einen S glatten Divisor A mit deg(A)  1 und m  deg(A) werden die S -glatten, entlang
max (S; A) :=A maximal- beziehungsweise m-minimalreduzierten Divisoren mit Dredmax (F=k; A) \D (S ) beziehungsweise D m (S; A) := D m (F=k; A) \D (S ) bezei hDredred
rednet. Ihre Anzahlen erhalten wir mit "Nred ()\ statt "Dred()\.
Fur spatere Komplexitatsanalysen benotigen wir die folgende Annahme uber die
Mindestanzahl glatter, minimalreduzierter Divisoren.
4.19. Glattheitsannahme. Es seien ; 2 (0; 1), < . F=k dur hlaufe eine

Folge von Funktionenkorpern mit festem q und g ! 1. Wir setzen voraus, da
F=k einen rationalen Teilkorper k(x) mit [F : k(x)℄ = O(1) besitzt. Es sei A ein
Divisor von F=k mit deg(A) = O(1) und S die Menge aller Stellen von F=k eines
Grads kleiner glei h m, wobei n  m  n mit n := g + deg(A) 1 gelte. Dannnehmen wir an:deg(A)Nred(S; A)  qn= exp u log(u) (1+o(1)) :Es handelt si h bei dieser Annahme also um Satz 4.10, ausgespro hen fur zusatzli h entlang A deg(A)-minimalreduzierte Divisoren, allerdings unter spezielleren
Bedingungen. Wegen [55, S. 33, I.6.10℄ ers heint es plausibel (man kann au hVerglei hbares beweisen), da ein zufallig gewahlter positiver Divisor "kleinen\
Grads au h eine "kleine\ Dimension besitzt. Mit Annahme 4.19 ubertragen wir
diese Eigens haft auf S -glatte Divisoren. Im Zahlkorperfall wird ubrigens eineahnli he Annahme ausgespro hen, vgl. [7℄.

Kapitel 5
Das Klassengruppenverfahren

In diesem Kapitel wird das Verfahren der Klassengruppenbere hnung eines globalen Funktionenkorpers F=k des Ges hle hts g > 0 uber dem exakten Konstantenkorper k mit q Elementen bes hrieben.
Unter der Bere hnung der Klassengruppe C l0 (F=k) von F=k verstehen wir die
Bere hnung ihrer Struktur als endli he abels he Gruppe
C l0 (F=k) = = 1      = m
mit 1  1 j : : : j m zusammen mit Divisoren D1; : : : ; Dm vom Grad null, deren
Klassen den Erzeugern der zyklis hen Faktoren entspre hen. Die ganze Divisorenklassengruppe C l(F=k) erhalt man unter Hinzunahme eines Divisors A1 vomGrad eins mit Proposition 1.1 in der Form
C l(F=k) =  = 1      = m :Die Komplexitatsbetra htungen konzentrieren si h auf die Situation g ! 1,
wobei alle sonstigen Groen als von g abhangig betra htet und die O- beziehungsweise o-Aussagen glei hmaig fur jeden Funktionenkorper gelten werden,
sofern das Ges hle ht nur gro genug ist. Die erste, grundsatzli he Forderung ist
q = O(1). Wir setzen weiter voraus, da F=k einen rationalen Teilkorper k(x)mit [F : k(x)℄ = O(1) besitzt. Die explizite Darstellung von F=k kann dann mit
einem in y normierten und separablen, irreduziblen Polynom f 2 k~[x; y℄ erfolgen, wobei k~ einen Teilkorper von k bezei hnet und degy (f ) = O(1) gilt. Die
O- beziehungsweise o-Konstanten sind daher stets von g , F=k und Cf = Cf (g )unabhangig.
Das Verfahren stutzt si h im wesentli hen auf Methoden zur Bere hnung desGes hle hts von F=k, der Stellen von F=k eines beliebigen, aber ni ht zu groenGrads, der Riemann-Ro h-Raume von Divisoren und der Hauptdivisoren (in freier
Darstellung) von Elementen von F=k.
Z

Z

Z

Z

Z

57

Z

Z

Z

Z

58

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

5.1 Prinzipielle Vorgehensweise
In diesem Abs hnitt wird das dem Klassengruppenverfahren zugrundeliegende
Prinzip als Bere hnung spezieller S -Einheiten dargestellt und ein Rumpfalgorithmus angegeben. Wir beginnen mit
5.1. Satz (S-Einheiten). Fur eine endli he, ni ht-leere Menge S  P l(F=k)
von Stellen und s := jS j 1 ist(oS ) = =(q 1)  s:
Beweis. D0 (S ) ist frei vom Rang s. Die (ni ht kanonis he) Isomorphie ergibt si h,weil P (S ) aufgrund der Endli hkeit der Klassenzahl endli hen Index in D0(S ) hat
und weil es exakt die Elemente von k sind, deren Hauptdivisoren das Nullelement
reprasentieren. Siehe au h [43℄.
Es genugen bereits endli he Mengen S , um D0(S )=P (S ) = C l0 (F=k) zu erhalten.
In Satz 3.17 beziehungsweise Bemerkung 3.19 werden genauer S hranken fur die
Grade der dafur benotigten Stellen angegeben, so da wir ein geeignetes S explizit bestimmen konnen. Die Klassengruppenbere hnung lat si h deswegen auf die
Bere hnung der entspre henden S -Einheiten beziehungsweise ihrer Hauptdivisoren reduzieren. Allgemein sehen wir eine S -Einheitengruppe fur endli hes, ni ht
leeres S als bere hnet an, wenn eine Basis bestehend aus Elementen von (oS )
fur den freien Teil wie in Satz 5.1 bestimmt worden ist. Analoges gilt fur die freie
Gruppe P (S ). Die Bere hnung der Klassengruppe aus der S -Einheitengruppe beziehungsweise aus P (S ) wird mit dem folgenden Lemma errei ht:
5.2. Lemma. Fur ein endli hes S = fP0 ; : : : ; Psg mit s  1 seien Hauptdivisoren ( 1 ); : : : ; ( l ) von S -Einheiten gegeben. Die von diesen Hauptdivisoren
erzeugte Untergruppe von P (S ) sei U . Dur h Bere hnung der Smith-Normalform
der Matrix M := (vP ( j ))i;j erhalten wir den Rang m und Diagonalelemente
Z

Z

Z

i

1 j : : : j m von M und einen explizit gegebenen Isomorphismus

D(S )=U =

Z

s+1 m

 = 1  = m :
Z

Z

Z

Z

Der maximal mogli he Rang der Matrix M ist s. Genau in diesem Fall hat U
endli hen Index in D0 (S ) und die Eins hrankung der obigen Isomorphie ergibt

D0(S )=U = = 1      = m :
Z

Z

Z

Z

Beweis. Die erste Isomorphieaussage ist an si h klar und folgt aus der Gestalt
der Smith-Normalform von M : Bei ihrer Bere hnung werden die P0; : : : ; Ps unimodular zu Divisoren D1 ; : : : ; Ds+1 transformiert, so da die ersten m Divisoren

5.1.

59

PRINZIPIELLE VORGEHENSWEISE

Di die Ordnung i und die restli hen s + 1 m unendli he Ordnung in D(S )=U
haben. Per De nition entspre hen diese Di unter dem Isomorphismus den Erzeugern der obigen zyklis hen Faktoren. Der maximale Rang von M ist s, weil P (S )und D0(S ) Rang s haben. In diesem Fall hat nur Ds+1 unendli he Ordnung in
D(S )=U . Weil die anderen endli he Ordnung haben, mussen sie den Grad nullhaben, sie bilden daher eine Basis von D0(S ), woraus si h die zweite Isomorphieaussage ergibt. Es sei angemerkt, da der Grad von Ds+1 glei h dem grotengemeinsamen Teiler der Grade der Stellen aus S ist, weil alle Di zusammen eine
Basis von D(S ) bilden.

Wir wenden uns jetzt der Bere hnung der speziell fur die Klassengruppe benotigten S -Einheitengruppe zu. Die folgende Namensgebung hat si h eingeburgert:
5.3. De nition. Eine Faktorbasis S ist eine endli he, ni ht-leere Teilmenge von
P l(F=k). S ist vollstandig, wenn D0(S )=P (S ) = C l0 (F=k) gilt. Zu vorgegebener
Faktorbasis S nennen wir die Hauptdivisoren von S -Einheiten au h Relationen.
Fur den Rest dieses Abs hnitts gehen wir davon aus, da eine Methode zur
Verfugung steht, die unter Eingabe einer no h zu bestimmenden Faktorbasis S
der Reihe na h Relationen ( 1 ); ( 2); : : : produziert, fur die es ein (uns unbekanntes) l 2 1 gibt, so da die ersten l Relationen ( j ) die Gruppe der S -glatten
Hauptdivisoren P (S ) (mit groer Wahrs heinli hkeit) erzeugen. Wir nennen diesen Proze Relationensu he. Wie dies bei spezieller Wahl von S zu bewerkstelligen
ist, wird spater erklart. Die Bestimmung beliebiger S -Einheiten lat si h im ubrigen dann auf diesen speziellen Fall zuru kfuhren.
Wir wahlen jetzt eine vollstandige Faktorbasis S . Die Idee ist dann die folgende:
Die ( j ) werden der Reihe na h abgearbeitet und mit Lemma 5.2 (evtl. blo kweise) ausgewertet, bis der Index der von den ( j ) erzeugten Gruppe U in D0(S )endli h wird. Nun stellt si h die Frage, ob bereits U = P (S ) gilt. Wir wissen
aufgrund der Voraussetzung an S , da der uns bekannte Index (D0(S ) : U ) ein
ganzzahliges Vielfa hes der Klassenzahl h(F=k) = (D0(S ) : P (S )) ist. Mittels
Satz 3.20 konnen wir die Klassenzahl aber au h approximieren und den Fehler
abs hatzen.
5.4. Lemma. Es sei h 2  und I (h ) := fx 2 j 2 1=2 < x=h < 21=2 g. Furjedes h 2 I (h ) gilt dann h \ I (h ) = fhg.
Beweis. Man kann ohne Eins hrankung h > 0 annehmen. Es sei ah 2 I (h ) mit
a 2 >0. Dur h Logarithmieren ergibt si h: j log(a)j = j log(ah) log(h)j 
j log(ah) log(h )j + j log(h ) log(h)j < log(2), also a = 1.
Z

R

Z

Z

R

60

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

Unter Verwendung einer Approximation h der Klassenzahl h(F=k), die so genau
ist, da h(F=k) 2 I (h ) gilt, fahren wir mit der Auswertung weiterer ( j ) fort, bis(D0(S ) : U ) 2 I (h ) erfullt ist. Dann haben wir aufgrund des Lemmas (D0(S ) :U ) = h(F=k), deswegen au h U = P (S ), und sind fertig. Wir fassen das Vorgehen
in einem Algorithmus zusammen:
5.5. Algorithmus. (Klassengruppenverfahren)
Eingabe: Ein globaler Funktionenkorper F=k des Ges hle hts g > 0 uber dem
endli hen Korper k mit q Elementen.
Ausgabe: Struktur und Erzeuger von C l0 (F=k).
1. (Erzeugungss hranke) Bestimme eine fur die Erzeugung der Klassengruppe ausrei hende obere S hranke mE = r 2 Z1 fur die Grade der hierfurbenotigten Stellen und einen Divisor A1 vom Grad eins mittels Satz 3.17
und Proposition 3.15 dur h die Bere hnung der ersten Werte von Nr (F=k)
bis maximal maxf d2 logq (4g 2)e; d2 logq (2g )e + 1 g.

2. (Approximation von h(F=k)) Bere hne eine Approximation h der Klassenzahl h(F=k) mittels Satz 3.20 unter Verwendung der Werte Nr (F=k) bis
mP  2 logq 3g=(q 1=2 1) , so da der Fehlerterm kleiner log(2)=2 wird.
3. (Vollstandige Faktorbasis) Erstelle eine fur die Relationensu he geeignete
Faktorbasis S , die die Stellen von F=k eines Grads kleiner glei h mE und
den Trager von A1 enthalt.
4. (Relationensu he) Unter Verwendung von Lemma 5.2 und Lemma 5.4 wird
die Relationensu he fur S (blo kweise) solange dur hgefuhrt, bis eine Untergruppe U von P (S ) von endli hem Index bekannt ist, fur die (D0 (S ) :U ) 2 I (h ) gilt.

5. (Ende) Es gilt nun U = P (S ). Unter Verwendung von Lemma 5.2 werden die fur die Klassengruppenbere hnung erforderli hen Daten bestimmt.
Terminiere.

5.6. Bemerkung. Die maximale Anzahl der in den S hritten 1 und 2 zu betra htenden Stellen ist O(g2 log(g)), so da der Gesamtaufwand hierfur unter Be-

a htung von Abs hnitt 1.2 und der Voraussetzungen am Anfang dieses Kapitels
polynomial in gCf ist. Die Kosten fur S hritt 3 bis 5 ergeben si h im wesentli hen
aus der Strategie der verwendeten Relationensu he und werden spater untersu ht.
Die Abs hatzung fur mP in S hritt 2 ergibt si h aus dem Fehlerterm in Satz 3.20
mit 2= log(2) < 3.

5.1.

PRINZIPIELLE VORGEHENSWEISE

61

In der Praxis konnen die zu verwendenden, vollstandigen Faktorbasen bei groerem g und q und damit au h M aus Lemma 5.2 relativ gro werden, so da die
Bere hnung der Smith-Normalform zu aufwendig wird. In dieser Situation hilft ingewissem Rahmen eine Variation von Algorithmus 5.5: In S hritt 3 verzi hten wir
auf die Forderung, da S vollstandig sein soll. Das Abbru hkriterium in S hritt 4
wird nur mit der oberen S hranke beibehalten und liefert ni ht notwendigerweisedas gewuns hte Ergebnis. Es ist jetzt namli h mogli h, da nur eine Faktorgruppe
von D0(S )=U zu einer Untergruppe der Klassengruppe isomorph ist. Zur Erkennung beziehungsweise Behebung dieser Situation werden vor S hritt 5 Wurzeltests
dur hgefuhrt.
Bei den Wurzeltests handelt es si h um das folgende Vorgehen: Mit U sei eine
Untergruppe von P (S ) von endli hem Index bezei hnet. Mit Hilfe der letzten Isomorphie in Lemma 5.2 betra hten wir eine Auswahl sol her Divisoren D 2 D0 (S ),deren Klassen in D0(S )=U eine Primzahlordnung l besitzen. Zusammen mit der
Nullklasse bilden letztere einen l -Vektorraum. Genau dann gilt U = P (S ), wennkeiner der Divisoren D fur keines der mogli hen l ein Hauptdivisor ist. Wir testen
dies fur alle D (modulo l ), und falls ein Hauptdivisor D gefunden wurde, konnen
wir U erweitern beziehungsweise den Index von U in P (S ) um l verkleinern, und
beginnen mit den Tests fur l von vorne. Der Aufwand dieser Bere hnungen wird
vom l-Rang der Gruppe D0(S )=P (S ) dominiert. S hlimmstenfalls sind daher wegen Satz 3.14 mindestens (l2g 1)=(l 1) Wurzeltests fur l dur hzufuhren, so dadas Verfahren im allgemeinen exponentiell in g ist. D0 (S )=P (S ) ist aber hau gzyklis h (oder ein Produkt weniger zyklis her Gruppen), so da die Dur hfuhrung
von Wurzeltests in diesem Fall re ht eÆzient ist. Es sei angemerkt, da die auftretenden Exponenten sehr gro werden konnen und daher Algorithmus 2.25 fur
die Hauptidealtests unentbehrli h ist. Vgl. au h [3, S. 16℄, [50, S. 54℄.
In der obigen Situation konnen wir nun mit den Wurzeltests aus D0(S )=U die Untergruppe D0(S )=P (S ) selbst erhalten. Wenn ihre Ordnung in I (h ) liegt, handelt
es si h um die Klassengruppe, ansonsten um eine e hte Untergruppe. Unter Verwendung einer ni ht vollstandigen Faktorbasis konnen wir also die von ihr erzeugte
Untergruppe der Klassengruppe mit Hilfe der Wurzeltests (in unter Umstanden
exponentieller Zeit in g) bere hnen.
Im Zahlkorperfall wird eine Methode fur Wurzeltests basierend auf dem Cebotarevs hen Di htigkeitssatz zur Umgehung der (lRang 1)=(l 1)-vielen Einzels hritte eingesetzt. Wie in [50, S. 55℄ bes hrieben, ist dieses Verfahren im Funktionenkorperfall in der Praxis ni ht eÆzient dur hfuhrbar. Dies liegt daran, da
Stellen eines Grads m mit l j qm 1 betra htet werden mussen, und sol he m sindhau g sehr gro (ni ht selten m = l 1). Es sei s hlieli h auf die Analogie dieser
Methode zur Tate-Li htenbaum Paarung aus [16℄, siehe au h [15℄, hingewiesen.
F

F

62

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

5.2 Relationensu he
In diesem Abs hnitt soll eine U bersi ht uber die Strategien zur Su he von Relationen gegeben werden. Wir xieren dafur eine Faktorbasis S = fP0; : : : ; Psg mits  1 und einen S -glatten Divisor A mit deg(A)  1.
Die allgemeine Form der Relationensu he besteht in der sukzessiven Bere hnung
der S hnitte L(D) \ P (S ) fur S -glatte Divisoren D, wel he na h einer gewissen Strategie zu erzeugen sind. Die spater bere hneten Relationen entstehen im
Prinzip alle auf diese Weise.
Mit den vorausgesetzten Mogli hkeiten ist die Bere hnung dieser S hnitte prinzipiell mogli h. Man bes hrankt si h sinnvollerweise auf Divisoren ni ht-negativen
Grads. Die Bere hnung von L(D) erfolgt mit den Methoden des ersten Kapitels,
dana h kann (und o enbar mu) man fur die Elemente von L(D) multiplikativ modulo Konstanten einzeln uberprufen, ob es si h um S -Einheiten handelt.
Der Aufwand der S hnittbere hnung ist damit a priori exponentiell im Grad derDivisoren D.
Es lassen si h drei allgemeine Situationen beziehungsweise Strategieansatze unters heiden:
1.) Divisoren vom Grad nullFur die S hnittbere hnung werden S -glatte Divisoren D vom Grad nullverwendet. In diesem Fall gilt entweder dim(D) = 0 oder dim(D) = 1, undbei dim(D) = 1 hat man eine S -Einheit gefunden. Die Wahrs heinli hkeitfur dim(D) = 1 bei zufalliger Wahl von D sollte ungefahr bei 1=h(F=k)
liegen. Dieser Ansatz entspri ht einem Re hnen in abels hen Gruppen.

2.) Divisoren eines kleinen Grads

Fur die S hnittbere hnung werden hier S -glatte Divisoren D eines kleinen
Grads und positiver Dimension verwendet, die beispielsweise dur h Divisorreduktion erhalten werden konnen. Ein a 2 L(D) ist genau dann S -glatt,wenn (a) + D S -glatt ist. Weil (a) + D mit D kleinen Grad besitzt, besteht
hierfur eine Glattheitswahrs heinli hkeit. Bei geeigneter Wahl von S fallt
diese hoher als 1=h(F=k) aus.

3.) Divisoren groen Grads
Es werden S -glatte Divisoren D mit groem Grad und groer Dimension

verwendet, beispielsweise so gro, da ein komplettes Erzeugendensystem
der S -Einheiten in L(D) zu nden ist. Man konnte diesen Ansatz als Direktbere hnung von S -Einheiten bezei hnen. Er ist unbrau hbar, weil wir ni ht

5.2.

63

RELATIONENSUCHE

in der Lage sind, die (relativ wenigen) S -Einheiten unter den sehr vielen
Elementen von L(D) zu nden.
In der S hwierigkeit der Bere hnung des S hnitts L(D) \ P (S ) einer additiven mit einer multiplikativen Struktur ist also wegen 3:) ein grundlegendes Problem der Klassengruppenbere hnung zu sehen. Zur S hnittbere hnung bei groem
Divisorgrad erwahnen wir deshalb zwei, leider vergebli he Ansatze, die auf notwendigen Bedingungen fur die Glattheit eines Elements von L(D) beruhen: Es
sei a1; : : : ; am eine Basis von L(PD). Der erste Ansatz besteht darin, die Normen
NF=k(x) (a) von Elementen a = iai 2 L(D) parametris h auszure hnen undauf entspre hende Glattheit zu testen. Hierbei wird stark vereinfa hend die Frage
aufgeworfen, fur wel he Spezialisierungen der i ein Polynom h 2 k[1; : : : ; m; x℄
nur aus Linearfaktoren besteht. Dies ist genau dann der Fall, wenn ein spezialisiertes h eine ausrei hend hohe Potenz von xq x teilt.
Der zweite Ansatz besteht darin, das dur h a de nierte, logarithmis he Di erential (1=a)da parametris h als Linearkombination der logarithmis hen Di erentiale
der S -Einheiten wie am Ende von Abs hnitt 3.4 darzustellen. In beiden Fallen
erhalt man dann jedo h ni ht-lineare Glei hungen und Unglei hungen in groerAnzahl oder mit vielen freien Variablen (m ist gro), deren Losung unter den
gegebenen Umstanden ni ht mehr sinnvoll beziehungsweise mogli h ist.
Es bleiben die Ansatze 1:) und 2:), auf die man si h stutzen kann. Ansatz 1:) fuhrt
zu im Prinzip deterministis hen Algorithmen, wohingegen 2:) einen probabilistis hen Algorithmus liefert. Die folgenden Teilabs hnitte geben einen U berbli kuber diese Methoden, bevor der probabilistis he Ansatz dann eingehend behandelt wird.
5.2.1 Deterministis he Methoden

Zur Bere hnung unabhangiger Relationen beziehungsweise S -Einheiten kann man
zwei Methoden unters heiden.
Fur die erste bes hranken wir uns entspre hend 1:) auf die Betra htung von Divisoren in D0(S ) und wollen heraus nden, wel he davon in P (S ) liegen. Wir konnen
speziell die unabhangigen Divisoren Di := deg(P0)Pi deg(Pi)P0 fur 1  i  sbetra hten. Fur jedes sol he i gibt es ein m 2 mit 1  m  (q1=2 + 1)2g , so da
mDi ein Hauptdivisor ist. Wir bere hnen unabhangige S -Einheiten, indem wir furjedes m und jedes i testen, ob mDi ein Hauptdivisor ist. Die einzelnen Tests sind
mit Algorithmus 2.25 eÆzient zu bewerkstelligen. Zur Reduzierung des Aufwands
in m kann man speziell beispielsweise die Baby-Step-Giant-Step Methode, vgl. [9,S. 235 .℄, verwenden. Der Aufwand bleibt allerdings wegen der S hranke fur m
exponentiell in g.
Z

64

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

Mit der eben bes hriebenen, ersten Methode der Bere hnung unabhangiger Relationen und den Wurzeltests aus Abs hnitt 5.1 kann man also bereits P (S ) unddamit die Klassengruppe fur eine vollstandige Faktorbasis S deterministis h bere hnen. Der Aufwand ist aber exponentiell in g. Allgemeiner konnen unter Verwendung von Divisoren vom Grad null und des Hauptdivisortests Te hniken zum
Bere hnen der Struktur einer abels hen Gruppe von "innen\ heraus eingesetzt
werden.

Die zweite Methode zur Bere hnung unabhangiger Relationen verwendet bereits
Divisorreduktion. Zu einer Folge von speziell oder zufallig gewahlten S -glatten
Divisoren Di, i = 1; 2; : : : bere hnen wir entlang A maximalreduzierte Divisoren
De i mit Di = De i + rA (ai ). Weil diese reduzierten Divisoren positiv und voneinem Grad kleiner g +deg(A) sind, ist ihre Anzahl endli h. Folgli h gibt es j1 ; j2,
so da De j1 = De j2 gilt, und in diesem Fall haben wir mit aj1 =aj2 eine S -Einheit
gefunden. Wahlen wir speziell A = P0 und Di;j = i deg(P0)Pj fur 1  j  s, so
erhalten wir auf diese Weise fur jedes j eine S -Einheit, deren Hauptdivisor vonder Form mj deg(P0 )Pj deg(Pj )P0 analog wie oben ist. Weil es mindestensh(F=k) viele entlang A maximalreduzierte Divisoren gibt, ist der Aufwand dieser
Bere hnungen ebenfalls exponentiell in g.
Es sei an dieser Stelle auf die Verbindung der beiden Methoden zur Bere hnung
von Diri hlet-Einheiten [36, S. 48 .℄, zur Relationenerzwingung [56, S. 46 .℄ und
zur Relationenerzeugung dur h Idealreduktion [47℄ im Zahlkorperfall hingewiesen.
5.2.2 Probabilistis he MethodeDie prinzipielle Verfahrensweise der probabilistis hen Methode ist die folgende:
Zu einem zufallig gegebenen Divisor D bere hnen wir einen positiven Divisor
De mittels Divisorreduktion, so da D = De + rA (a) gilt, ahnli h der zuvor
bes hriebenen Methode der reduzierten Divisoren. Ist De S -glatt, so hat man mit
a eine Relation gefunden. Man stutzt si h also bei dieser Methode ni ht mehr auf
die Glei hheit zweier De , sondern auf ihre Glattheitswahrs heinli hkeit, und erhalt
ein Verfahren, wel hes eine wesentli h bessere Laufzeit als die zuvor bes hriebenen
Methoden hat. Die probabilistis he Methode und ihre Erfolgswahrs heinli hkeit
werden im na hsten Abs hnitt eingehend bes hrieben.

5.3 Probabilistis he MethodeIn diesem Abs hnitt wird die probabilistis he Methode der Relationensu he bes hrieben, auf die wir uns im Klassengruppenverfahren hauptsa hli h stutzen.

5.3.

65

PROBABILISTISCHE METHODE

Die Bes hreibung bleibt theoretis h, so da in dem darau olgenden Abs hnitt die
Vorgehensweise in der Praxis erlautert wird. Insbesondere untersu hen wir jetzt
das asymptotis he Verhalten fur g ! 1, wobei ahnli h wie in [7℄ vorgegangen
wird, vgl. au h [53℄.
5.3.1 Situation und Strategie der Relationensu he

Mit S = fP0; : : : ; Psg, s  1 bezei hnen wir wieder eine Faktorbasis und mit Aeinen positiven, S -glatten Divisor, deg(A)  1.
Die von A erzeugte Untergruppe von D(S ) ist hAi. Wir betra hten die Projektion
prS;A : D(S ) ! D(S )=hAi: Ihre Eins hrankung auf Dm (S ) ist fur alle m 2
injektiv, aber ni ht unbedingt surjektiv. Wir bemerken insbesondere, da P (S )ein isomorphes Bild in D(S )=hAi besitzt.
Wenn A ein Primdivisor ist, sieht man unmittelbar, da D(S )=hAi = s gilt. Im
allgemeinen erhalt man einen Epimorphismus in der folgenden Weise: Wir dividieren A dur h den groten gemeinsamen Teiler der Exponenten von A und erhalten
einen "primitiven\ Divisor D0 . Dur h unimodulare Erganzung erhalten wir weiter Divisoren D1; : : : ; Ds, so da S 0 := fD0; : : : ; Dsg eine Basis von D(S ) ist. Mitdieser Basis ergibt si h die Isomorphie D(S )=hD0i = s und der angekundigte
Epimorphismus D(S )=hAi ! D(S )=hD0i = s.
Dur h diese Abbildungen erhalten wir zusammenfassend ein ebenfalls epimorphes
S;A : D(S ) ! s. Das isomorphe Bild von P (S ) unter S;A in s bezei hnen
wir mit S;A. Die Bere hnung von P (S ) kann damit auf die Bere hnung von S;Azuru kgefuhrt werden. Wegen Korollar 1.4 angewendetdeg(aufA) D0 statt A wissen wir,da ( s : S;A)  deg(A)h(F=k) gilt. Das Bild von Dred (S; A) unter S;A wirds hlieli h mit red
S;A bezei hnet.
Fur die Bere hnung von Bildern und Urbildern unter S;A benotigen wir zusatzli heine Bes hranktheitseigens haft von S;A im Hinbli k auf g ! 1. Wir fordern,da die Grade der Pi aus S polynomial in g und da der Grad von A, die Anzahl
der in A vorkommenden Stellen sowie die betragli he Summe ihrer Exponenten in
A alle O(1) sind. Wenn wir dann die Basis S 0 ni ht "absi htli h s hle ht\ wahlen,konnen wir von folgendem ausgehen: Es sei T 2 (s+1)(s+1) die unimodulare
Transformationsmatrix mit (D0; : : : ; Ds) = (P0 ; : : : ; Ps)T . Es gibt ein positives
ur die Maximumnormen 0 1jjvjj1  jjT vjj1  0 jjvjj1 fur alle
0 = O (1), so da f
v 2 s+1 gilt. Die Basen S und S 0 sollen si h also ni ht zu sehr "unters heiden\.
Diese Forderungen lassen si h beispielsweise dann erfullen, wenn A ein Primdivisor vom Grad eins oder die Di erenz zweier Primdivisoren aus S ist. Weil derGrad der Korpererweiterung F=k(x) na h Voraussetzung O(1) ist, konnen dieseForderungen au h fur A = (x)1 erfullt werden.

Z

Z

Z

Z

Z

Z

Z

Z

Z

66

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

deg(A)
5.7. Bemerkung. Es gilt jred
S;A j  Nred (S; A)= deg(A), weil si h zwei entlang
A deg(A)-minimalreduzierte Divisoren ni ht um ein Vielfa hes von A, eventuellaber um ein Vielfa hes von D0 unters heiden. Weiter ist fur jedes v 2 red
S;A na hder obigen Bes hranktheitsforderung jjvjj1 < 0 g + deg(A) erfullt. Auerdem
bemerken wir no h einmal, da wir (Zs : S;A)  deg(A)h(F=k) haben.

5.8. De nition. Die Relationenabbildung rS;A wird de niert als
rS;A : red
S;A  S;A

! s; (v1 ; v2) 7! v1 + v2
Z

und fur ihre Umkehrung betra hten wir (2 ist die Potenzmenge von S;A)
uS;A : s ! 2 ; uS;A(v ) := f v2 2 S;A j rS;A (v1 ; v2 ) = v fur v1 2 red
S;A g:S;A

Z

S;A

Unter der Relationensu he verstehen wir nun spezieller die sukzessive Bere hnung
von Bildern unter uS;A. Dies kommt der Aufgabe glei h, alle entlang A deg(A)minimalreduzierten und S -glatten Divisoren De mit D = De + rA (a) fur die
Divisoren D 2 S;A1 (v) zu bestimmen. Letztere unters heiden si h voneinander
nur dur h Vielfa he von D0 .
Den Aspekten 1:) und 2:) aus Abs hnitt 5.2 wird dur h die Verwendung der entlang A deg(A)-minimalreduzierten Divisoren Re hnung getragen, denn dadur hbleiben die auftretenden Dimensionen klein.
5.9. Algorithmus. (Bere hnung von uS;A)
Eingabe: Die Divisoren A, D0 ; : : : ; Ds und ein v 2 Zs.
Ausgabe: Die Menge Rv  S;A mit uS;A(v ) = Rv .
P

1. (Divisoren mod A bere hnen) Bere hne den Divisor D := si=1 vi Di , wobei
die vi die KoeÆzienten von v sind. Bere hne die Divisoren Di0 := D + iD0fur i := 0; : : : ; deg(A)= deg(D0 ) 1.
2. (Reduzierte Divisoren) Bere hne mit Algorithmus 2.21 und Bemerkung 2.24
e i;j mit D 0 := De i;j +
alle entlang A deg(A)-minimalreduzierten Divisoren Diri;j A (ai;j ).
e i;j ein S -glatter
3. (Glattheit) Bere hne die Menge J der Indizes (i; j ), fur die D
e i;j ) j (i; j ) 2 J g.
Divisor ist. Setze Rv := f v S;A(D

4. (Ende) Ausgabe von Rv . Terminiere.

5.3.

67

PROBABILISTISCHE METHODE

5.10. Bemerkung. Die Anzahl der entlang A deg(A)-minimalreduzierten Divisoren De i;j im zweiten S hritt betragt maximal deg(A)(qdeg(A) 1)=(q 1) we-

gen Bemerkung 2.24. Die ersten beiden S hritte benotigen damit einen Aufwand
O(1) log jjv jj1 (gCf )O(1) s, na h den Voraussetzungen an S; A; T und wegen Bemerkung 2.22. Fur die Glattheitstests ist zu bea hten, da die De i;j positive Divisoren eines Grads kleiner glei h g +deg(A) in Idealdarstellung sind. Unter Verwendung von Faktorisierungen der De i;j beziehungsweise ihrer Normen und mit Hilfe
einer Ordnung fur die unter Stellen aus S liegenden Stellen von k(x) kann man den
Glattheitstest in einer Laufzeit von O(1)(gCf )O(1) log(s) dur hfuhren, indem diebere hneten Stellen in der Faktorbasis (binar) gesu ht werden, und erhalt dabei
die freie Darstellung
von De i;j . Damit ist die Gesamtlaufzeit von Algorithmus 5.9
O(1) log jjv jj1 (gCf )O(1) s (die ersten beiden S hritte bleiben bestimmend fur dens-Anteil).
Na h Festlegung der Situation fur die Relationensu he und der Bes hreibung, wie
sie fur einzelne v 2 s dur hzufuhren ist, kommen wir nun zur Strategie derErzeugung dieser Vektoren. Mit lS;A := deg(A)2(q1=2 + 1)4g de nieren wir hierfurs dur hzwei Quader QS;A; Qred
S;A 
QS;A := [ 0; lS;A ℄s \ s;


 s
Qred
\ s:
0 g + deg(A) ; lS;A + 0 g + deg(A)S;A :=
Die in Algorithmus 5.5, S hritt 4 dur hzufuhrende Relationensu he besteht nun
einfa h in der zufalligen (und glei hverteilten) Erzeugung von Vektoren v 2 Qred
S;Aals Eingabe fur Algorithmus 5.9, und zwar solange, bis ein Erzeugendensystemvon S;A beziehungsweise P (S ) gefunden wurde (dies kann mit den Methoden
des Abs hnitts 5.1 getestet werden).
Z

Z

Z

Z

5.3.2 Erfolgswahrs heinli hkeit

Dur h die sukzessive Bere hnung von uS;A erhalt man also eine (eventuell leere)
Folge von Vektoren aus S;A beziehungsweise eine Folge von Elementen aus P (S ).
Wir wenden uns jetzt der Frage zu, inwiefern Vektoren aus S;AnU fur ein e htes
Teilgitter U von S;A dur h die Bere hnung von uS;A fur Vektoren des Quaders
Qredonnen.
S;A erhalten werden k
5.11. Lemma. Fur l ! 1 seien s = o(l1=2 ), s  1, und Ql := [0; l℄s ein Quader
im s. Fur jedes Gitter  vom Rang s im s mit d() := ( s : )  l1=2 gilt:o(1)j \ Ql j = 1 +d() jQl j:(5.12)
Z

Z

Z

68

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

Fur jedes e hte Teilgitter U eines sol hen Gitters  gilt:o(1) jQl j:j(nU ) \ Ql j  12+d()Wenn zusatzli h U den Rang s hat und eine Basis in Ql besitzt, so gilt:(5.13)( : U )  (s1=2 l)s=d()  (s1=2 l)s:
(5.14)
Beweis. Wir betra hten eine Basis von  in Hermite-Normalformgestalt und bezei hnen mit di 2 1 die Eintrage auf den Stufen. Dann haben wir di \[0; l℄ = bl=di + 1Qund
unter Bea htung der Stufengestalt der Basis ergibt si h,sda j \ Ql j = i=1 bl=di + 1 ist. Aus dieser Glei hung erhalten wir wegen di  d()  l1=2 :(l + l1=2 )s = d()  j \ Ql j  ls = d():(5.15)
Nun haben wir (l + l1=2 )s = jQlj  (1 + l 1=2 )s = 1 + o(1) und ahnli h ls = jQlj =1 + o(1) wegen s = o(l1=2 ) und weil allgemein (1 + 1=x)x ! e fur x ! 1 gilt.
Aus (5.15) ergibt si h damit (5.12).
Ist r der Rang von U , so gibt es j ; w 2 Q1, rso da die Stufenelementevon U
dur h w d gegeben werden und jU \ Ql j  j=1 bl=(w d ) +1 gilt. Hieraus
erhalten wir fur r < s
jU \ Ql j  (l + 1)s 1(5.16)
und fur r = s wegen jU \ Ql j  d() 1 Qsj=1 l=w + d und weil mindestens
ein w  2 ist:
jU \ Ql j  l + 2l1=2 s = 2d() :(5.17)
Hat U ni ht vollen Rang, so gilt na h (5.15) und (5.16)
j(nU ) \ Ql j  ls=d() (l + 1)s 1= (1 + 1=l) s d()=(l + 1) jQl j = d()= 1 + o(1) jQl j = d():Hat U Rang s, so gilt na h (5.15) und (5.17)
j(nU ) \ Ql j  ls=d() (l + 2l1=2)s = 2d()
= ls 2 (1 +2l 1=2 )s = 2d()= ls 1 + o(1) = 2d() :Mit ls=jQl j = 1 + o(1) ergibt si h die Unglei hung (5.13) in beiden Fallen.
Die letzte Aussage (5.14) uber den Index von U folgt mit der Abs hatzung derDeterminante einer aus s unabhangigen Vektoren von U in Ql gebildeten Matrix
mit Hilfe der Hadamard-S hranke.
Z

Z

j

j

Z

j

j

j

j

j

j

5.3.

69

PROBABILISTISCHE METHODE

1=2
5.18. Lemma. Fur g ! 1 sei s = o lS;A
, s  1. Mit Rv0 := red
S;A  S;A \ QS;A
gilt:
rS;A(Rv0 )  Qred
S;A ;



 deg(A)1+o(1) Nred(S; A)  Qred :rS;A v S;Adeg(A)2 h(F=k)
Beweis. Die Aussage rS;A (Rv0 )  Qred
S;A folgt aus Bemerkung 5.7. Wir bea hten
nun drei Aussagen: Erstens, h(F=k)  (q1=2 + 1)2g na h Korollar
3.13; zweitens,
1=2
rS;A ist in jedem Argument injektiv; drittens, wegen s = o(lS;A) gilt jQS;Aj =(1 + o(1)) jQred
S;Aj. Mit Lemma 5.11, (5.12) angewendet auf S;A und den Quader
QS;A erhalten wir damit, da das Bild rS;A(Rv0 ) fur jede feste Wahl eines v1 2 red
S;A
(1 + o(1)) jQred
j
=
(deg(
A
)
h
(
F=k
))
Elemente
enth
a
lt.
Wegen
Bemerkung
5.7
verS;Adeg(A)
vielfaltigt si h diese Anzahl um mindestens Nred
(S; A)= deg(A), wenn man
v1 2 redvariiert,unddarausergibt
si
h
die
obige
Abs
hatzung.
S;A
5.19. Lemma. Es seien ; 2 (0; 1) und n := g + deg(A) 1. Fur g ! 1
gilt bei Wahl der speziellen Faktorbasis S := P lm (F=k ) mit n  m  n und
u := n=m sowie unter der Glattheitsannahme 4.19:
deg(A)Nred(S; A)  exp u log(u)(1+o(1)) :deg(A)2 h(F=k)
Beweis. Der Faktor deg(A)2 wird von dem (1 + o(1)) aufgenommen, so da mandeg(A)
si h auf die Betra htung des Quotienten Nred
(S; A) = h(F=k) bes hranken kann.
Wegen Satz 3.22 mit den Voraussetzungen an F=k uber die Existenz eines rationalen
Teilkorpers und der Glattheitsannahme 4.19 ergibt si h die Behauptung furdeg(A)
Nred (S; A) = h(F=k), indem man bea htet, da die Fehlerterme ebenfalls in den(1 + o(1))-Ausdru k aufgenommen werden konnen.
5.20. Proposition. Es seien p0 ; p1 2 >0 mit p0 + p1 = 1 und bezei hne V(R 0 )

R

einen Algorithmus, der mit einer Wahrs heinli hkeit von p1 das Ergebnis "wahr\
liefert.

(i) Die erwartete Mindestanzahl von Ausfuhrungen von V , um genau r-mal das
Ergebnis "wahr\ zu erhalten, betragt r=p1 .

(ii) Die Wahrs heinli hkeit, in bp1 1 Ausfuhrungen von V mindestens einmal
das Ergebnis "wahr\ zu erhalten, strebt mit p1 ! 0 gegen 1 1=e.
(iii) Es gibt ein k0 = k0 (p1) 2 2 , so da die Wahrs heinli hkeit, na h k0 r
RAusfuhrungen von V mindestens r-mal das Ergebnis "wahr\ zu erhalten,
mit r ! 1 gegen 1 strebt.

70

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

Beweis. Wir bezei hnen mit Xr die Mindestanzahl von Ausfuhrungen von V ,wel he genau r-mal wahr\ liefern. Es gilt also Xr = w, wenn die letzte unddavor beliebige r 1" von insgesamt w Ausfuhrungen von V den "wahr\-Wert

ergeben. Dies tritt folgli h mit einer Wahrs heinli hkeit von
w 1 r w rp pp(Xr = w) =r 1 1 0ein. Fur den Erwartungswert von Xr ergibt si h damit

1 
1
X
X
w 1 r w r
p 1 p0w
w p(Xr = w) =E (Xr ) =
r
1
w=r
w=0
1
X

pr1

= (r 1)! w(w 1)    (w r + 1) p0w r
w=r
r
r
r
= (r p1 1)!  dxd r (1 x) 1 x=p0 = (r p1 1)!  (1 rp! )r+10
= r=p1;womit Teil (i) bewiesen ware. Fur Teil (ii) bea htet man,1 da die Wahrs heinli hkeit, keinmal den Wert "wahr\ zu erhalten, (1 p1)bp1 betragt, wel hes fur
p1 ! 0 gegen 1=e strebt.
Zum Beweis von Teil (iii) wird ein k0 2 2 mit pk00 1 ek0 < 1 gewahlt und w :=k0 r gesetzt. Wir betra hten die Wahrs heinli hkeit p(Xr  w), in w Ausfuhrungenvon V mindestens r-mal den Wert "wahr\ zu erhalten:w  Xw j w jp p :p(Xr  w) =
j 1 0
R

j =r

Fur die Komplementarwahrs heinli hkeit folgt unter Verwendung der Stirlings hen Formel in der Form log(n!) = n(log(n) 1 + o(1))
p(Xr > w) =


r 1
X
k0 r
j =0

j

p0 )j pk00 r j

k0 r
 r p(0k0 1)r (k0r)r =r!
r
pk00 1 ek0 r eo(r) r p(0k0 1)r




(1

wel hes fur wa hsendes r na h Wahl von k0 gegen null strebt.
5.21. Lemma. Fur g ! 1 bere hnet man mit den Voraussetzungen von Lemma 5.19 ein Erzeugendensystem von S;A, bestehend aus q m+o(1) Elementen,

5.3.

71

PROBABILISTISCHE METHODE

na h erwartungsgema uu(1+o(1)) q m Anwendungen von Algorithmus 5.9 auf zufallig (und glei hverteilt) gewahlte Vektoren aus Qred
S;A mit gegen 1 strebenderWahrs heinli hkeit.
Beweis. Wir stellen die Beoba htung voran, da die Groe s der Faktorbasis S
na h Lemma 3.12 dur h qm+o(1) bes hrankt wird. Wegen Lemma 5.18 und 5.19
kann daher u u(1+o(1)) als untere S hranke fur die Wahrs heinli hkeit aufgefatwerden, ein Element von S;A dur h zufallige Wahl eines Vektors aus Qred
S;A undAnwendung von Algorithmus 5.9 zu erhalten. Mit Proposition 5.20, (ii) erhalten wir daher fur ausrei hend groes g na h uu(1+o(1)) Versu hen eine Relation
mit einer Wahrs heinli hkeit groer 1=2. Bezei hne U ein (von bisher gefundenen Relationen aufgespanntes) e htes Teilgitter von S;A. Wenn eine Relation v

gefunden wird, so konnen wir wegen Lemma 5.11, (5.13) mit einer Wahrs heinli hkeit von beispielsweise mindestens 1=3 davon ausgehen, da v 2 S;AnU ist.
Wenn der Rang von U kleiner als s ist, kann man fur die Wahrs heinli hkeitv 2 S;An  U sogar die glei he untere S hranke annehmen. Wir wenden Proposition 5.20, (i); (iii) mit dem Algorithmus V := " uu(1+o(1)) -malige Anwendung
von Algorithmus 5.9 auf zufallige Vektoren aus Qred
S;A \ an, wobei "wahr\ bedeutensoll, da eine neue, ggf. den Rang vergroernde Relation gefunden wurde. Die
Wahrs heinli hkeit p1 betragt dann entspre hend obigem mindestens 1=6. Na herwartungsgema 6s Anwendungen von V erhalt man ein U mit endli hem Index
in S;A und na h weiteren, erwartungsgema O(sg) Anwendungen wegen Lemma 5.11, (5.14) sogar ein Erzeugendensystem von S;A, denn der Index verringert
si h immer um einen Faktor von mindestens 2. Weil die konstanten Faktoren undselbst g in den o(1)-Ausdru k im Exponenten ubernommen werden konnen, ergibt
si h die Aussage des Lemmas mit Proposition 5.20.
Q

5.3.3 Komplexitat

Zur Minimierung der Anwendungen von Algorithmus 5.9 in Lemma 5.21 gilt es
nun m = m(n) so zu bestimmen, da der Aufwand asymptotis h mogli hst klein
wird. Im Exponenten ndet si h hier bis auf den (1 + o(1))-Faktor ein Ausdru k
der Form (n=m) log(n=m) + mp. Man kann si h uberlegen, da dieser Ausdru k
asymptotis h fur m = + o(1) n log(n) mit einemgeeigneten,
festen 2 >0pminimiert wird und dort den Wert (2 ) 1 + + o(1)p n log(n) besitzt. Hierauspergibt si h unter Minimierung des Vorfaktors = 1= 2 und (2 ) 1 + = 2 .
Wir stoen somit auf die fur komplexitatstheoretis he Aussagen hau g benotigte
FunktionpL(a; x) := exp x log(x) a :R

72

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

5.22. Satz. Mit der Glattheitsannahme 4.19 und unter Verwendung einer geeigneten Faktorbasis bestehend ausp

L 1=

2 log(q) + o(1); gStellen bere hnet man ein Erzeugendensystem des Gitters S;A asymptotis h derselben Groep
L 1= 2 log(q ) + o(1); g
dur h
p

L 2 log(q ) + o(1); g
Anwendungen von Algorithmus 5.9 auf zufallig und glei hverteilt gewahlte Vektoren aus Qred
S;A mit gegen 1 strebender Wahrs heinli hkeit.
Beweis. Folgt mittels der obigen Minimierung des Faktors (2 ) 1 +log(q), Lemma 5.21 und unter Bea htung von deg(A) = O(1).

und =Bei diesem Satz handelt es si h im Prinzip um die komplexitatsbestimmende
Kernaussage uber das Verhalten der probabilistis hen Relationensu he.
Na h der Bere hnung des (wahrs heinli hen) Erzeugendensystems in S hritt 4
von Algorithmus 5.5 mit der bes hriebenen Methode mussen allerdings no h die
Struktur und Erzeugende der Klassengruppe mit Lemma 5.2 in S hritt 5 bestimmt
werden, wobei si h dieser und der von Algorithmus 5.9 gelieferte Anteil an der Gesamtkomplexitat als ni ht unerhebli h erweist. Der Aufwand fur die Bere hnung
der Faktorbasis in S hritt 3 leistet hingegen keinen besonderen Beitrag.
5.23. Satz. Fur festes k = q dur hlaufe F=k eine Folge globaler Funktionenkorper des Ges hle hts g mit g ! 1, die dur h in y normierte und separable, irreduzible Polynome f (x; y ) 2 k[x; y ℄ mit degy (f ) = O(1) gegeben werden. Die
F

Klassengruppe kann dann unter der Glattheitsannahme 4.19 in einer erwarteten
Laufzeit vonp
CfO(1)  L 5 log(q )=6 + o(1); g

mit gegen 1 strebender Wahrs heinli hkeit bere hnet werden.

Beweis. Die Vorbere hnungen der S hritte 1 und 2 in Algorithmus 5.5 sind na h
Bemerkung 5.6 polynomial in Cf und g. Weil die S hranke m verglei hsweisegro gewber ussig. Wir setzen
pahlt wird, ist S hritt 1 in diesem Fall sogar um :=g log(g ) mit einem no h zu bestimmenden 2 >0 . Fur die Groe s derFaktorbasis S = P lm (F=k) gilt damit s = qm+o(1) , und diese Anzahl in Cf polynomialer Operationen wird fur ihre Bere hnung benotigt. Die Verwendung vonLemma 5.21 erfordert dana h uu(1+o(1)) qm Aufrufe von Algorithmus 5.9, was eine
R

5.4.

PRAKTISCHE VORGEHENSWEISE

73

Laufzeit von (Cf )O(1) uu(1+o(1)) q2m entspre hend Bemerkung 5.10 ergibt. S hlieli h gilt es Lemma 5.2 na h Umre hnung der gefundenen Relationen aus S;A in
Divisoren anzuwenden. Hierin dominiert die Bere hnung der Smith-Normalform,
analog wie in [53, S. 202℄ setzen wir einen Aufwand von q5(m+o(1)) fur die qm+o(1)Relationen an (der Wert fur die Faktorbasiserzeugung vers hwindet gegenuberdiesen Groen). Wenn der Rang ni ht s ist oder die Determinante ni ht in dem Intervall I (h ) liegt, endet der Algorithmus ergebnislos, was aber wegen Lemma 5.21
nur mit gegen null gehender Wahrs heinli hkeit eintritt.
Mit der Bere hnung der Smith-Normalform erhalt man au h die die Klassengruppe zyklis h erzeugenden Divisoren. Zur Vermeidung von KoeÆzientenexplosion in
ihren Exponenten bea htet man die folgende Reduktionsmogli hkeit: Ohne Eins hrankung kann deg(A) = 1 und deg(Di ) = 0 fur 1  i  s, Bemerkung 5.6 undS hritt 1 in Algorithmus 5.5, gewahlt werden. A ist dann an den Relationen ni ht
beteiligt, weil diese als Hauptdivisoren den Grad null haben, und die Exponenten
von in den Di dargestellten Divisoren konnen modulo h(F=k) reduziert werden.
Fur den Gesamtaufwand ergibt si h insgesamt(Cf )O(1) L 1=(2 ) + 2 log(q) + o(1); g + L 5 log(q) + o(1); g;wel hes fur
wird.

p

:= 1= 6 log(q) (bei ni ht zu stark wa hsendem Cf ) minimiert

Dieses Laufzeitergebnis stimmt mit dem fur reell-quadratis he Funktionenkorperaus [53℄ uberein.

5.4 Praktis he Vorgehensweise
Na h den vorangegangenen, theoretis hen Ausfuhrungen soll in diesem Abs hnitt
auf die praktis he Dur hfuhrung der Klassengruppenbere hnung eingegangen werden, wobei wir fur die Relationensu he die probabilistis he Methode verwenden. In
den Algorithmen werden nun insbesondere au h praktis he Erfahrungen beru ksi htigt.
5.4.1 Erzeugung der Faktorbasis

Die Wahl der Faktorbasis spielt eine ents heidende Rolle fur die Relationensuhe. Bei den bes hriebenen, deterministis hen Methoden sollte sie vollstandig undmogli hst klein sein, wohingegen fur die probabilistis he Methode ein ausgewogenes Verhaltnis von Groe und Glattheitswahrs heinli hkeit wie in Satz 5.22

74

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

benotigt wird und si h die Vollstandigkeit aufgrund der S hranken bei ausreihend groem Ges hle ht von selbst einstellt.
Bei der probabilistis hen Methode ist man genauer am Minimum des Produkts
der Anzahl der Stellen der Faktorbasis und dem Inversen der Glattheitswahrs heinli hkeit interessiert, um die Anzahl der Versu he der Relationensu he zu
minimieren. Zusatzli h gilt es au h no h die Kosten fur die Smith-NormalformBere hnung in Lemma 5.2 zu beru ksi htigen.
Fur die Divisorreduktion benutzen wir standardmaig A = (x)1, da diese dannbesonders eÆzient ausgefuhrt werden kann. Die Wahl eines anderen Divisor A in
S hritt 3:1 unten mit kleinem Grad bleibt jedo h mogli h und ist beispielsweise
bei relativ groem [F : k(x)℄ im Verhaltnis zu g sinnvoll, weil damit reduzierte
Divisoren zu groer Dimension bei der Relationensu he ausges hlossen werden.
Fur die Praxis hat si h insgesamt das folgende Vorgehen als brau hbar erwiesen (S hritt 3 in Algorithmus 5.5 wird ersetzt)::::
3.1. (Reduktionsdivisor) Wahle A = (x)1 und setze n := g + deg(A)1.

3.2. (Stellenzahl exakt) Es sei r1 das Maximum der S hranken fur die Erzeugung
der Klassengruppe mE und fur die Approximation der Klassenzahl mP aus
S hritt 1 und 2. Bere hne er := r (F=k) fur 1  r  r1 .

3.3. (Stellenzahl approximiert) Setze er := q r =r fur r1 < r  n0:7 .

3.4. (Minimum nden) Finde 1  mH  n0:7 , fur wel hes der Wert

[ : ( )℄

g2 F

kx 5

( )

(

F=k n; n = F=k n; mH

)

 mH
 X
r=1

er



+

X
mH
r=1

er

3

minimal, aber unglei h null wird. Die Bere hnung der F=k -Werte erfolgt
mit Satz 4.2, (ii) und mit den er anstelle der exakten, aber unbekannten r (F=k).

3.5. (S hranke anpassen) Setze mB := maxfmH ; mE g.
3.6. (Faktorbasis erzeugen) Bere hneS := P lmB (F=k) [ supp(A1 ) [ supp (x)1 [ supp(A)::::Wir erwarten eine Glattheitswahrs heinli hkeit von pS;A :=F=k (n; n).

()

F=k n; mB =

5.4.

PRAKTISCHE VORGEHENSWEISE

75

Der Wert in S hritt 3:4 stellt keine exakte Angabe der benotigten Kosten dar,liefert aber in der Praxis im Berei h q < 10 und g < 10 ganz brau hbare S hranken mB . Fur groere q und g mu man meist kleinere mB verwenden, so da unterUmstanden au h Wurzeltests, wie na h Algorithmus 5.5 bes hrieben, notwendig
werden. Fur Beispiele sei auf Kapitel 7 verwiesen.
5.4.2 Relationensu he

Bei der probabilistis hen Relationensu he verzi hten wir gegenuber der Bes hreibung in Abs hnitt 5.3.1 auf die Verwendung der Di, deren Nutzen eher theoretis hwar, und arbeiten direkt mit den Stellen Pi der Faktorbasis (in Algorithmus 5.24
wird die Bezei hnung Di fur andere Divisoren verwendet).
Fur die Praxis hat si h insgesamt das folgende Vorgehen als brau hbar erwiesen,
wobei S hritt 4 in Algorithmus 5.5 ersetzt wird:
5.24. Algorithmus. (Relationensu he)Eingabe: Ein globaler Funktionenkorper F=k des Ges hle hts g > 0 uber dem
endli hen Korper k mit q Elementen, eine Faktorbasis S , ein S -glatter
Divisor A mit deg(A) > 0, eine Approximation h der Klassenzahl
wie in Algorithmus 5.5, sowie die erwartete Glattheitswahrs heinli hkeit pS;A .

Ausgabe: Ein Erzeugendensystem einer Untergruppe U von P (S ) mit dem Index (D0 (S ) : U ) 2 I (h ).
1. (Initialisierung) S hreibe S := fP0 ; : : : ; Ps g und setze W := 1. Wahle furjedes 0  i  s ein zufalliges P 2 S und de niere Di := Pi + P rA
mit einem maximalen r 2 Z, so da dim(Di ) > 0 ist. Setze weiter RV := 0
(Anzahl Relationenversu he), R := 0 (Anzahl der gefundenen Relationen),
RV0 := 0, R0 := 0, RV := maxf10dpS;A1 e; 20g, R := maxfdjS j=10e; 10g,
SR := 1 (Rangzuwa hs pro Relationenzuwa hs), RRV := 1 (Relationen pro
Relationenversu he), i := 0.

2. (S hleife uber i) Na h S hritt 8 wird zu S hritt 2 gesprungen.

3. (Na hstes Element) Wenn L(Di ) multiplikativ modulo k kein bisher ni ht
verwendetes Element enthalt, wird ein neues Di erzeugt: Setze Di := Pi +( Summe von W zufallig gewahlten Stellen aus S mit zufalligen Exponenten
in [1; W ℄ ) rA, mit einem maximalen r 2 Z, so da dim(Di ) > 0 ist.
Wahle fur a ein bisher ni ht verwendetes Element von L(Di ) und setze RV := RV + 1.

76

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN


4. (Relation gefunden?) Uberpr
ufe, ob mit a eine Relation gefunden wurde.
Wenn ja, spei here a fur die spatere Auswertung und setze R := R + 1.

5. (Glattheitstest) Wenn RV RV0  RV ist, so werden die folgenden Teils hritte ausgefuhrt:
5.1. Setze RRV := R=RV .
5.2. (Faktorbasis vergroern?) Wenn RRV  pS;A=100 ist, wird die Faktorbasis um die Stellen des na hsthoheren Grads, als wie bisher verwendet, erweitert, pS;A wird angepat und die neu dazugekommenen
Dj und RV werden wie in der Initialisierung bere hnet. Andernfalls
wird RV := maxf10d1=RRV e; 20g gesetzt.
5.3. Setze RV0 := RV .
6. (Relationen-Test) Wenn R R0  R ist, so werden die folgenden Teils hritte ausgefuhrt:
6.1. (Relationen auswerten) Die Relationen werden wie in Lemma 5.2 ausgewertet und U als das von ihnen erzeugte Teilgitter gesetzt.
6.2. (Endli her Index) Folgendes wird fur endli hen Index (D0 (S ) : U ) getan: Wenn (D0 (S ) : U ) 2 I (h ) ist, so wird die S hleife 2 verlassen.
Wenn der Index und W mit den letzten maxfdjS j=10e; 10g Relationen unverandert geblieben ist, wird W := minfW + 1; jS j; 10g gesetzt
und alle Dj werden wie in S hritt 3 neu bere hnet. S hlieli h wird
R := d2RRV jS j=[F : k(x)℄e gesetzt.
6.3. (Ni ht endli her Index) Wenn der Index no h ni ht endli h war, so
wird das folgende getan: Es sei r der Rangzuwa hs mit den letzten R Relationen. Setze SR := (r=R + SR )=2. Wenn SR < 0:2
ist und der Rang und W mit den letzten maxfjS j=10; 10g Relationen unverandert geblieben ist, dann sei W := minfW + 1; jS j; 10g,
alle Dj werden wie in S hritt 3 neu bere hnet, und es wird R :=maxfdjS j=10e; 10ge gesetzt. Andernfalls sei
R := dminf 3SRR; 2RRV jS j(jS j rank(U ))=(SR [F : k(x)℄) ge:
7. (Na hstes i) Wenn in S hritt 4 eine Relation gefunden wurde, setze i :=i + 1. Wenn i > s ist, dann setze i := 0.
8. (Ende S hleife uber i) Gehe zu S hritt 2.

9. (Ende) Die Relationensu he ist abges hlossen. Ausgabe der gefundenen Relationen und U . Terminiere.

5.4.

77

PRAKTISCHE VORGEHENSWEISE

Bemerkungen:

Wegen der bes hrankten Groe der in S hritt 1 und 3 erzeugten Divisoren Di
tre en die Komplexitatsuberlegungen der vorangegangenen Abs hnitte streng genommen ni ht mehr auf Algorithmus 5.24 zu. In der Praxis erweist si h dieses Vorgehen jedo h als gunstig, weil die Bere hnung der Riemann-Ro h-Raume zugiger
vonstatten geht und die auftretenden Relationen ebenfalls eine bes hrankte Groebesitzen.
Wenn A 6= (x)1 ist, verwendet man statt der Maximalreduktion in S hritt 1
und 3 praktis herweise nur die Gradreduktion aus Abs hnitt 2.6, wel he s hneller
zu bestimmen ist und in der Regel dasselbe Ergebnis liefert.
Fur die Ausfuhrung von S hritt 4 bietet es si h an, die Norm NF=k(x) (a) zu betra hten. Der Nenner ist na h den Voraussetzungen an S und A S -glatt. Eine
gute Vorauswahl S -glatter Elemente a erhalt man daher, falls S = P lm (F=k)
ist, wenn zuerst getestet wird, ob der Zahler der Norm nur aus Primpolynomen
eines Grads  mB besteht. Dies kann eÆzient dur hgefuhrt werden.
Die S hritte 5:1-5:3 beruhen auf der Erfahrung, da die Relationensu he mitunterfur sehr kleine Faktorbasen beziehungsweise sehr kleines q und g ni ht genugend
Relationen nden kann, so da eine Vergroerung notwendig ist. Dies tritt allerdings nur selten ein. Will man die Relationensu he bei groem g mit fester
Faktorbasisgroe dur hfuhren, sollte man diese S hritte ni ht beru ksi htigen.
Das Vorgehen der S hritte 6:1-6:3 realisiert die folgende Strategie: Die Relationen
werden, dur h R gesteuert, zu Beginn der Relationensu he hau g und spater
immer seltener ausgewertet, sofern das Rangwa hstum ausrei hend gut ausfallt.
Hierdur h spart man si h die allzu hau ge Bere hnung der Smith-Normalformin Lemma 5.2, die bei groeren Faktorbasen ziemli h teuer wird. S hlieli h erfolgt die Auswertung der Relationen dann au h, wenn aufgrund des bisherigen
Rangwa hstums ein voller Rang erwartet werden kann. Wenn das Rangwa hstum jedo h s hle ht ist, werden die Relationen immer hau ger ausgewertet undgegebenenfalls dann W erhoht. In die Anzahl R der zu ndenden Relationen
bis zur na hsten Auswertung geht zusatzli h das Verhaltnis des Aufwands, eine Relation zu nden, zum Aufwand der Smith-Normalform-Bere hnung ein: Ist
die Smith-Normalform-Bere hnung verhaltnismaig teuer, so werden relativ viele
Relationen bis zur na hsten Auswertung gesu ht, und umgekehrt.
Fur Beispiele sei auf das Kapitel 7 verwiesen.
B

78

KAPITEL 5.

DAS KLASSENGRUPPENVERFAHREN

Kapitel 6
Anwendungen

In diesem Kapitel wird auf Anwendungen der Klassengruppenbere hnung globaler Funktionenkorper eingegangen: Wir bes hreiben die Bere hnung von Bildern
und Urbildern unter der Isomorphie der Divisorenklassengruppe zur bere hneten,
endli h erzeugten, abels hen Gruppe und die si h daraus ergebende Mogli hkeit
zur Bere hnung diskreter Logarithmen, S -Einheiten und Idealklassengruppen der
Dedekindringe oS , fur beliebige, ni ht-leere endli he Stellenmengen S .
Die Voraussetzungen von Kapitel 5 werden ubernommen.

6.1 Eindeutige Klassendarstellung
Wie bes hrieben liegt die Struktur der Klassengruppe na h der Klassengruppenbere hnung als endli he abels he Gruppe in Elementarteilergestalt C l0 (F=k) == 1      = m vor. Urbilder unter diesem Isomorphismus sind lei ht zu
bere hnen, weil zusatzli h konkrete, den zyklis hen Faktoren entspre hende Divisoren gegeben sind. Es stellt si h nun die Frage, wie das Bild einer beliebigen
Divisorenklasse [D℄ 2 C l0 (F=k) unter diesem Isomorphismus zu bestimmen ist.
Gesu ht ist also eine eindeutige Darstellung von [D℄ in den erzeugenden Divisoren.
Wenn dies geklart ist, erhalt man unter Hinzunahme eines Divisors vom Grad einsmit Proposition 1.1 dann au h die in beiden Ri htungen bere henbare Isomorphie
der ganzen Divisorenklassengruppe C l(F=k) =  = 1      = m .
Wir gehen von einer freien Darstellung (S. 16) von D mit deg(D) = 0 aus. Um
die eindeutige Klassendarstellung zu nden, geht man sehr ahnli h wie bei der
Relationensu he vor. Unter Verwendung der Faktorbasis S aus der Klassengruppenbere hnung bestimmt man zufallig gewahlte S -glatte Divisoren D0 (ni ht zu
groer Hohe) und betra htet die Maximalreduktionen von D + D0 entlang A, alsoe S -glatt ist, hat man eine Darstellung
D + D0 = De + rA (a). Wenn eines dieser D
Z

Z

Z

Z

Z

79

Z

Z

Z

Z

80

KAPITEL 6.

ANWENDUNGEN

von D dur h einen S -glatten Divisor De + rA D0 modulo
einem Hauptdivisor00egefunden. Wegen [D + rA D ℄ 2 D (S ) + P (F=k) = P (F=k) = D0(S )=P (S )bere hnet man dann lei ht die gesu hte Darstellung mit Lemma 5.2. Die Erfolgswahrs heinli hkeit dieses probabilistis hen Vorgehens stimmt mit der Wahrs heinli hkeit uberein, bei der probabilistis hen Relationensu he eine Relation zu
nden, so da ein subexponentieller Aufwand erwartet werden kann.
Mit der Klassendarstellung lassen si h Fragestellungen bezugli h der Divisorenklassengruppe in den Kontext explizit gegebener, endli h erzeugter abels her
Gruppen ubersetzen. Im folgenden nehmen wir an, da die erforderli hen Algorithmen fur endli h erzeugte abels he Gruppen und Homomorphismen zwis hen
ihnen zur Verfugung stehen.

6.2 Diskreter Logarithmus
Fur zwei Divisorenklassen [D1 ℄; [D2℄ vom Grad null ist der diskrete Logarithmus
von [D1 ℄ bezugli h [D2 ℄ eine modulo der Ordnung von [D2 ℄ bestimmte Zahl r 2 ,fur die [D1℄ = r[D2 ℄ gilt. Indem man nun die Klassendarstellung von [D1℄ und [D2℄bestimmt, lat si h das Problem der Bere hnung des diskreten Logarithmus von[D1 ℄ bezugli h [D2℄ in das analoge Problem in = 1      = m ubersetzen,
wo es lei ht wegen der bekannten Groen i gelost werden kann.
Z

Z

Z

Z

Z

6.3 Einheiten und Idealklassengruppe desDedekindrings oS
S sei eine beliebige, ni ht-leere endli he Menge von s + 1 Stellen von F=k. Es
stellt si h die Frage na h der Bere hnung der Einheitengruppe und der Idealklassengruppe des Rings der auerhalb S ganzen Elemente oS . Au h dieses kann mit
Hilfe der Klassendarstellung in die Situation endli h erzeugter abels her Gruppenubertragen werden.
Wir verwenden dazu den Homomorphismus S : D(S ) ! C l(F=k), fur dennamli h ker S = P (S ) und oker S = C l(F=k)=S D(S ) = C l(oS ) gilt (manverglei he mit dem Beweis von Korollar 1.3). Mit Hilfe der Klassendarstellung
erhalten wir fur S einen explizit gegebenen Homomorphismus 0S : s+1 !
 = 1      = m und konnen dessen Kern und Kokern bere hnen. Aus
den Hauptdivisoren P (S ) lassen si h mittels Riemann-Ro h-Raum-Bere hnungs hlieli h fundamentale S -Einheiten von (oS ) in Potenzproduktdarstellung gewinnen.
Z

Z

Z

Z

Z

Z

Kapitel 7
Beispiele

Wir betra hten nun Beispiele fur die Bere hnung von Klassengruppen globaler
Funktionenkorper F=k. Im ersten Abs hnitt bere hnen wir neben der Divisorenklassengruppe au h die Einheiten- und Idealklassengruppe von oS = Cl(k[x℄; F )fur die Beispiele zur Einheitenbere hnung aus [50℄ und fur einige weitere Beispiele. In den darauf folgenden Abs hnitten betra hten wir zufallig gewahlte Funktionenkorper mit entweder groer Elementanzahl q des exakten Konstantenkorpers
oder groem Ges hle ht g, eine Tabelle mit hyperelliptis hen Funktionenkorpern
und speziell konstruierte Funktionenkorper mit vielen Stellen vom Grad eins. Den
Abs hlu bildet ein Beispiel zur Bestimmung des p-Rangs der Klassengruppe sowie der Hasse-Witt-Invariante von F=k.
Alle Bere hnungen wurden mit dem Computeralgebrasystem KASH, [25℄, auf einer
SGI Origin 2000 dur hgefuhrt.
Die Tabelleneintrage gliedern si h in Kasten des folgenden Inhalts:
Der erste Kasten enthalt immer die Werte q und g, die laufende Nummer desBeispiels, die Klassenzahl h(F= q ) und die Struktur der Klassengruppe C l0 (F= q ),sowie die Bere hnungszeit T in Sekunden.
In den Abs hnitten 7.1 und 7.5 folgen zusatzli h der S0 -Regulator R(S0 ), die Idealklassenzahl h(S0) und die Struktur der Idealklassengruppe C l(oS0 ) des Rings oS0
fur S0 := supp (x)1 .
Dana h wird die de nierende Glei hung f (x; ) = 0 des Funktionenkorpers, derGrad n und die Konstante Cf zur KoeÆzientengroe angegeben.
Im letzten Kasten werden die wesentli hen Parameter
des KlassengruppenverPr
fahrens aufgelistet. Fur einen
i=1 i Pi s hreiben wir hier A  Divisor A =
;
deg(
P
);
:
:
:
;
;
deg(
P
)
.
Die
anderenWerte
entspre hen bei glei her Bezei h11rr
nung den Werten aus Algorithmus 5.5 und den Algorithmen in Abs hnitt 5.4: mE
F

F

81

82

KAPITEL 7.

BEISPIELE

ist die S hranke fur die Erzeugung der Faktorbasis, mP ist die S hranke fur die
Approximation der Klassenzahl, mH ist die S hranke, fur die die kurzeste Laufzeit erwartet wird. mB ist die dann tatsa hli h fur die Faktorbasis S verwendete
S hranke. Fur die Anzahl RV der Versu he, eine Relation zu nden, geben wir
den erwarteten (=?) und den tatsa hli hen Wert an. RR bezei hnet die Anzahl
der benotigten Riemann-Ro h-Raum-Bere hnungen, R die Anzahl der gefundenen
Relationen. W ist s hlieli h die Exponentens hranke fur die zufallig gewahlten
Divisoren der Relationensu he.
Fur keines der Beispiele ist eine Vergroerung der Faktorbasis wahrend der Bere hnung erforderli h. Auerdem gilt immer supp(A1 )  S .
Auf die Angabe von Divisoren, Idealen und S -Einheiten verzi hten wir aus Platzgrunden.

7.1 Verglei h mit Beispielen aus der Einheitenbere hnung
Die folgenden Beispiele sind [50, S. 64 .℄ entnommen. Man bea hte, da dort die
Grade der "unendli hen\ Stellen mit in den Regulator aufgenommen werden. Die
Laufzeiten haben si h teilweise erhebli h verbessert.
q = 3;

g=3

h(F=F 3 ) = 76; C l0 (F=F 3 ) = 2  38:
R(S0 ) = 19; h(S0 ) = 4; C l(oS0 ) = 2  2:3
2
F := F 3 (x; ) :
 + (2x + 1) + (2x3 + x2 + x + 1) + x2 + 2 = 0:
A = (x)1

n = 3;

 (1; 1; 2; 1):

1

T = 1:4 s

Cf = 2! mB := 2; jS j = 11; RV =? 16:
RR = 26; RV = 47; R = 36
! R=RV = 0:77; jS j=R = 0:31:
mE = 2;mP = 4;mH = 2

W = 1.
q = 3;

g=2

h(F=F 3 ) = 16; C l0 (F=F 3 ) = 2  8:R(S0 ) = 4; h(S0 ) = 4; C l(oS0 ) 
= 4:
3
2
2
F := F 3 (x; ) :
 + (x + 2) + (2x2 + 2) + 2 = 0:
A = (x)1 (1; 1; 1; 1; 1; 1):

RR = 7;

RV = 14;mE = 1;
W = 1.

mP = 3;mH = 1

R = 102

T = 0:7 sn = 3;! mB := 1; jS j = 5; RV =? 12:! R=RV = 0:71; jS j=R = 0:5:

Cf = 2

7.1.

VERGLEICH MIT BEISPIELEN AUS DER EINHEITENBERECHNUNG

q = 5;

g=1

h(F=F 5 ) = 3;
R(S0 ) = 1;

F := F 5 (x; ) :

 (1; 1; 1; 2):

RR = 5;

RV = 31;

mP = 2;

W = 1.

q = 25;

T = 0:6 s

C l(oS0 ) = 3:

3 + (x2 + 2x + 2)2 + (x + 2) + 2 = 0:

A = (x)1
mE = 1;

3

C l0 (F=F 5 ) = 3:

h(S0 ) = 3;

mH = 1

R = 10 (1; 1; 2; 1):

RR = 39;

RV = 39;mE = 1;mP = 0;W = 1.

g=0

h(F=F 7 ) = 1;
R(S0 ) = 1;

R = 394

T = 1:5 sn = 3;

Cf = 1! mB := 1; jS j = 26; RV =? 124:
! R=RV = 1; jS j=R = 0:67:

5

C l0 (F=F 7 ) = 1:

h(S0 ) = 1;

F := F 7 (x; ) :A = (x)1

mH = 1

Cf = 2! mB := 1; jS j = 4; RV =? 17:! R=RV = 0:32; jS j=R = 0:4:h(F=F 25 ) = 1; C l0 (F=F 25 ) = 1:
R(S0 ) = 1; h(S0 ) = 1; C l(oS0 ) = 1:
32
F := F 25 (x; ) :
 + (3x + 4) + 2 + 1 = 0:q = 7;

n = 3;g=0

A = (x)1

83

T = 0:6 s

C l(oS0 ) = 1:

3 + (2x + 3)2 + 1 = 0:n = 3;

 (1; 1; 2; 1):

Cf = 1! mB := 1; jS j = 8; RV =? 25:
RR = 17; RV = 17; R = 17
! R=RV = 1; jS j=R = 0:47:
mE = 1;mP = 0;mH = 1

W = 1.

q = 49;g=2h(F=F 49 ) = 3600; C l0 (F=F 49 ) = 2  2  30  30:
R(S0 ) = 2; h(S0 ) = 1800; C l(oS0 ) = 2  30  30:
432
F := F 49 (x; ) :
 + 2 + (2x + 3x + 4) + 1 = 0:
A = (x)1 (1; 1; 3; 1):

RR = 71;

RV = 787;

mE = 1;
W = 1.

mP = 1;mH = 1

R = 124!

mB := 1;!

jS j = 70;

R=RV = 0:16;

6

T = 15 s
n = 4;
RV =? 1823:

jS j=R = 0:56:

Cf = 1

84

KAPITEL 7.

q = 11;BEISPIELE

g=2

h(F=F 11 ) = 268; C l0 (F=F 11 ) = 2  134:
R(S0 ) = 268; h(S0 ) = 1; C l(oS0 ) 
= 1:
3
2
2
F := F 11 (x; ) :
 + (8x + x) + (6x2 + 3x + 3) + 8 = 0:
A = (x)1
mE = 1; (1; 1; 1; 1; 1; 1):mP = 1;

RR = 21;

RV = 81;

W = 1.
q = 13;mH = 1

R = 407

T = 2:5 sn = 3;! mB := 1; jS j = 21; RV =? 66:! R=RV = 0:49; jS j=R = 0:53:

g=1h(F=F 13 ) = 16; C l0 (F=F 13 ) = 4  4:
R(S0 ) = 4; h(S0 ) = 4; C l(oS0 ) = 4:
32
F := F 13 (x; ) :
 + (10x + 7x + 1)2 + (2x2 + 8x + 5) + 7 = 0:
A = (x)1 (1; 1; 1; 1; 1; 1):

RR = 16;

RV = 101;mE = 1;mP = 1;

W = 1.
q = 17;mH = 1

R = 21n = 3;!

RR = 19;

RV = 162;mE = 1;mP = 1;

W = 1.
q = 9;

g=0

h(F=F 9 ) = 1;
R(S0 ) = 1;
A = (x)1

R = 40!

W = 1.

mP = 0;C l(oS0 ) = 1:

mH = 1

T = 1:8 s

Cf = 1

10
T = 1:2 sn = 4;! mB := 1; jS j = 10; RV =? 89:
RR = 16; RV = 16; R = 16
! R=RV = 1; jS j=R = 0:63:
mE = 1;

9jS j = 17; RV =? 84:! R=RV = 0:25; jS j=R = 0:43:

4 + 23 + (2x + 1)2 + 2 + 1 = 0:

 (2; 1; 2; 1):

Cf = 2mB := 1;

C l0(F=F 9 ) = 1:

h(S0 ) = 1;

F := F 9 (x; ) :n = 3;

mH = 1

T = 2sjS j = 16; RV =? 52:! R=RV = 0:21; jS j=R = 0:76:h(F=F 17 ) = 16; C l0 (F=F 17 ) = 16:
R(S0 ) = 16; h(S0 ) = 1; C l(oS0 ) 
= 1:
3
2
2
F := F 17 (x; ) :
 + 2 + (6x + 14x + 6) + 10x2 + 10x + 1 = 0:

 (1; 1; 1; 2):8mB := 1;g=1

A = (x)1

Cf = 2

Cf = 1

7.1.

VERGLEICH MIT BEISPIELEN AUS DER EINHEITENBERECHNUNG

q = 5;

g=0

h(F=F 5 ) = 1;
R(S0 ) = 1;

F := F 5 (x; ) :A = (x)1
mE = 1;

RR = 10;
W = 1.

q = 25;C l(oS0 ) = 1:

4 + (2x + 3)3 + 2 + (3x + 2) + 1 = 0:

 (1; 1; 1; 1; 1; 1; 1; 1):mP = 0;

RV = 10;mH = 1

R = 10n = 4;

Cf = 1! mB := 1; jS j = 6; RV =? 32:! R=RV = 1; jS j=R = 0:6:

g=0h(F=F 25 ) = 1; C l0 (F=F 25 ) = 1:
R(S0 ) = 1; h(S0 ) = 1; C l(oS0 ) = 1:
43
F := F 25 (x; ) :
 + 2 + (3x + 2)2 +  + 2 = 0:
A = (x)1

11
T = 1:2 s

C l0 (F=F 5 ) = 1:

h(S0 ) = 1;85

 (2; 1; 2; 1):

12
T = 2:9 s
n = 4;

Cf = 1! mB := 1; jS j = 26; RV =? 411:
RR = 54; RV = 54; R = 54
! R=RV = 1; jS j=R = 0:48:
mE = 1;mP = 0;mH = 1

W = 1.

q = 25;g=0h(F=F 25 ) = 1; C l0 (F=F 25 ) = 1:
R(S0 ) = 1; h(S0 ) = 1; C l(oS0 ) = 1:
43
F := F 25 (x; ) :
 + (2x + 3) + 2 + 1 = 0:
A = (x)1 (1; 1; 3; 1):

13
T = 2:8 sn = 4;

Cf = 1! mB := 1; jS j = 26; RV =? 411:
RR = 40; RV = 40; R = 40
! R=RV = 1; jS j=R = 0:65:
mE = 1;mP = 0;mH = 1

W = 1.

q = 25;g=0h(F=F 25 ) = 1; C l0 (F=F 25 ) = 1:
R(S0 ) = 1; h(S0 ) = 1; C l(oS0 ) = 1:
43
F := F 25 (x; ) :
 + (2x + 3) + (x + 1)2 + (4x + 3) + 1 = 0:
A = (x)1 (1; 1; 1; 1; 1; 1; 1; 1):

14
T = 3:8 sn = 4;! mB := 1; jS j = 26; RV =? 411:
RR = 39; RV = 39; R = 39
! R=RV = 1; jS j=R = 0:67:
mE = 1;
W = 1.

mP = 0;mH = 1

Cf = 1

86

KAPITEL 7.

q = 49;g=0h(F=F 49 ) = 1; C l0 (F=F 49 ) = 1:
R(S0 ) = 1; h(S0 ) = 1; C l(oS0 ) = 1:
43
F := F 49 (x; ) :
 + (2x + 3) + (3x + 2)2 + (4x + 5) + 1 = 0:
A = (x)1
mE = 1; (1; 1; 1; 1; 1; 1; 1; 1):

RR = 129;mP = 0;g=0h(F=F 5 ) = 1;
R(S0 ) = 1;!

R = 12915
T = 11 sn = 4;

Cf = 1jS j = 50; RV =? 960:
! R=RV = 1; jS j=R = 0:39:
mB := 1;

16
T = 1:3 s

C l0(F=F 5 ) = 1:

h(S0 ) = 1;

F := F 5 (x; ) :A = (x)1

mH = 1

RV = 129;

W = 1.
q = 5;BEISPIELE

C l(oS0 ) = 1:

5 + (2x + 3)2 + 3 + 1 = 0:n = 5;

 (2; 1; 3; 1):

Cf = 1! mB := 1; jS j = 6; RV =? 72:
RR = 19; RV = 19; R = 19
! R=RV = 1; jS j=R = 0:32:
mE = 1;mP = 0;mH = 1

W = 1.

Die folgendenen Beispiele haben groeres Ges hle ht und benotigen wie zuvor nur
eine relativ geringe Laufzeit:q = 3;

g = 10h(F=F 3 ) = 52584; C l0 (F=F 3 ) = 2  2  13146:
R(S0 ) = 1; h(S0 ) = 52584; C l(oS0 ) = 2  2  13146:
56
F := F 3 (x; ) :
 + x + x + x + 1 = 0:
A = (x)1
mE = 6; (5; 1):

RR = 265;
W = 1.
q = 11;mP = 5;mH = 4

RV = 495;!

R = 238mB := 6;!

jS j = 192;

R=RV = 0:48;

mE = 2; (4; 1):

RR = 362;
W = 1.

n = 5;

mP = 2;mH = 2

RV = 2701;!

R = 109mB := 2;!

jS j = 71;

R=RV = 0:04;

Cf = 2

RV =? 697:

jS j=R = 0:81:

g=6h(F=F 11 ) = 1847040; C l0 (F=F 11 ) = 2  923520:
R(S0 ) = 1; h(S0 ) = 1847040; C l(oS0 ) = 2  923520:
425F := F 11 (x; ) :
 + x  + x + x + 1 = 0:
A = (x)1

17
T = 44 s

18
T = 25 s
n = 4;
RV =? 5583:

jS j=R = 0:65:

Cf = 2

7.2.

87

GROSSES GESCHLECHT

q = 19;g=7

19
T = 62 sh(F=F 19 ) = 1336199119; C l0 (F=F 19 ) = 1336199119:
R(S0 ) = 1; h(S0 ) = 2672398238; C l(oS0 ) = 2672398238:
4326F := F 19 (x; ) :
 +  + x  + x + x + 1 = 0:
A = (x)1
mE = 2; (2; 2):

RR = 679;

mP = 2;

W = 1.
q = 9;!

mH = 2

RV = 4018;

R = 436mB := 2;!

jS j = 224;

R=RV = 0:11;

n = 4;

RV =? 11112:

jS j=R = 0:51:

g=6

20

C l0 (F=F 9 ) = 2  208978:
R(S0 ) = 417956; h(S0 ) = 1; C l(oS0 ) = 1:h(F=F 9 ) = 417956;
F := F 9 (x; ) :A = (x)1
mE = 3;

RR = 450;mP = 2;!

mH = 3

RV = 8599;

W = 1.

T = 234 s

5 + x3 + x5 + x2 + 1 = 0:

 (1; 1; 1; 2; 1; 2):

R = 700

mB := 3;!

Cf = 2n = 5;jS j = 327;

R=RV = 0:081;

Cf = 1

RV =? 3150:

jS j=R = 0:47:

7.2 Groes Ges hle ht
Es folgen Beispiele, in denen das Ges hle ht fur jeden Konstantenkorper so gro
gewahlt wird, da wir eine ungefahre Vorstellung uber die Grenzen des Verfahrens
beziehungsweise der verwendeten Implementierung erhalten konnen.
Bis auf die ersten beiden und das vierte Beispiel wurde dur hweg A = A1 fur eine gute Glattheitswahrs heinli hkeit verwendet. Als S hranke fur die Faktorbasis
wurde hau g ein kleinerer Wert als mE gewahlt, so da am Ende der Klassengruppenbere hnung Wurzeltests erforderli h waren. Wegen der Strukturen der
Klassengruppen benotigten diese nur einen Bru hteil der gesamten Bere hnungszeit.
q = 2;

g = 5021h(F=F 2 ) = 1743271585380988; C l0 (F=F 2 ) 
T = 8749 s= 1743271585380988:
2101
F := F 2 (x; ) :
 + (x + 1) + x+ x + 1 = 0:n = 2; Cf = 51
A = (x)1
mE = 14; (2; 1):mP = 12;

RR = 79940;
W = 5:

mH = 12

RV = 98342;!

R = 1057

mB := 10;!

jS j = 250;

R=RV = 0:011;

RV =? 83985:

jS j=R = 0:24:

88

KAPITEL 7.

q = 3;BEISPIELE

g = 3022h(F=F 3 ) = 205217259503652; C l0 (F=F 3 ) 
T = 13450 s= 2  102608629751826:2
62
F := F 3 (x; ) :
 + (x + 1) + x + x + 1 = 0:n = 2; Cf = 31
A = (x)1
mE = 8; (1; 2):mP = 7;

RR = 80377;
W = 5.
q = 5;

mH = 7

RV = 130973;!

mB := 6;

R = 1127!

jS j = 230;

RV =? 74270:

R=RV = 0:0086;

g = 1923
T = 6234 s
n = 3; Cf = 7

h(F=F 5 ) = 16563730252090; C l0 (F=F 5 ) = 16563730252090:
321
F := F 5 (x; ) :
 + x + x + x + 1 = 0:A

 (1; 1):mE = 5;mP = 4;

RR = 106132;
W = 4:
q = 7;

mH = 5

RV = 126754;!

mB := 4;

R = 909!

jS j = 219;

RV =? 63731:

R=RV = 0:0072;

g = 14mE = 4; (5; 1):mP = 3;

RR = 14923;
W = 2:
q = 13;mH = 4

RV = 90844;!

mB := 3;

R = 468!

jS j = 148;

RV =? 102364:

R=RV = 0:0052;

g = 10 (1; 1):mE = 3;mP = 2;

RR = 19116;
W = 2:
q = 17;mH = 2

RV = 20802;!

mB := 2;

R = 395!

jS j = 111;

RV =? 10848:

R=RV = 0:019;

g = 10 (1; 1):mE = 2;mP = 2;

RR = 49690;
W = 2:

mH = 2

RV = 52399;!

mB := 2;

R = 666!

jS j = 168;

jS j=R = 0:28:
26
T = 17771 s
n = 5; Cf = 2

h(F=F 17 ) = 2231475497166; C l0 (F=F 17 ) = 2231475497166:
5
6
F := F 17 (x; ) :
 + (x + 1) + x + x + 1 = 0:
AjS j=R = 0:32:

25
T = 1888 s
n = 5; Cf = 2

h(F=F 13 ) = 206665304791; C l0 (F=F 13 ) = 206665304791:
56
F := F 13 (x; ) :
 + (x + 1) + x + x + 1 = 0:
AjS j=R = 0:24:

24
T = 1461 s
n = 5; Cf = 2

h(F=F 7 ) = 1322299613348; C l0 (F=F 7 ) = 2  661149806674:
58
F := F 7 (x; ) :
 + (x + 1) + x + x + 1 = 0:
A = (x)1

jS j=R = 0:2:

RV =? 33990:

R=RV = 0:013;

jS j=R = 0:25:

7.3.

89


GROSSER KONSTANTENKORPER

q = 23;

g = 10h(F=F 23 ) = 37953554676269; C l0 (F=F 23 ) = 37953554676269:
56
F := F 23 (x; ) :
 + (x + 1) + x + x + 1 = 0:A

 (1; 1):mE = 2;mP = 2;

RR = 148690;
W = 2:
q = 25;mH = 2

RV = 154883;!

mB := 2;

R = 1113!

jS j = 322;

27
T = 11602 s
n = 5; Cf = 2
RV =? 81501:

j j

R=RV = 0:0072; S =R = 0:29:

g = 1028h(F=F 25 ) = 147510773172045; C l0 (F=F 25 ) = 3  3  3  5463361969335: T = 69ks
5
6
F := F 25 (x; ) :
 + (x + 1) + x + x + 1 = 0:n = 5; Cf = 2
A (1; 1):mE = 2;mP = 2;

RR = 93274;
W = 5:

mH = 2

RV = 1544153;!

mB := 2;

R = 1053

jS j = 375;

RV =? 47170:! R=RV = 0:00068; jS j=R = 0:36:

7.3 Groer Konstantenkorper
In den folgenden Beispielen betra hten wir einen festen Funktionenkorper undnehmen Konstantenkorpererweiterungen vor. Wir beoba hten, da die Groe derFaktorbasis exponentiell im Grad der Konstantenkorpererweiterung zunimmt, soda dem Verfahren hier s hnell Grenzen gesetzt werden.
q = 2;

g=4h(F=F 2 ) = 10;

F := F 2 (x; ) :A = (x)129
T = 1sn = 2; Cf = 5

C l0 (F=F 2 ) = 10:
2
 + (x + 1) + x9 + x3 + 1 = 0:

 (2; 1):! mB := 5; jS j = 18; RV =? 18:
RR = 37; RV = 40; R = 40
! R=RV = 1; jS j=R = 0:45:
mE = 5;mP = 6;mH = 2

W = 1.
q = 4;g=430
T = 2:6 sn = 2; Cf = 5

h(F=F 4 ) = 280; C l0 (F=F 4 ) = 280:
2
F := F 4 (x; ) :
 + (x + 1) + x9 + x3 + 1 = 0:
A = (x)1
mE = 3;

RR = 98;
W = 1.

 (2; 1):mP = 3;mH = 2

RV = 148;

R = 111!

mB := 3;!

jS j = 38;

R=RV = 0:75;

RV =? 55:

jS j=R = 0:34:

90
q = 8;KAPITEL 7.

g=431
T = 3:5 sn = 2; Cf = 5

h(F=F 8 ) = 4090; C l0 (F=F 8 ) = 4090:2
F := F 8 (x; ) :
 + (x + 1) + x9 + x3 + 1 = 0:
A = (x)1
mE = 2; (2; 1):

RR = 214;mP = 2;mH = 1

RV = 251;

W = 2.
q = 16;g=4

A = (x)1 (2; 1):!

R = 186

jS j = 42;mB := 2;!

R=RV = 0:74;

RV =? 147:

jS j=R = 0:23:
32
T = 19 sn = 2; Cf = 5

h(F=F 16 ) = 114800; C l0 (F=F 16 ) = 5  22960:
2
F := F 16 (x; ) :
 + (x + 1) + x9 + x3 + 1 = 0:mE = 2;

RR = 680;

mP = 1;mH = 1

RV = 703;

W = 2.
q = 64;g=4

A = (x)1 (2; 1):!

R = 575mB := 2;!

jS j = 172;

R=RV = 0:82;

RV =? 436:

jS j=R = 0:3:

33
T = 15 sn = 2; Cf = 5

h(F=F 64 ) = 20041000; C l0 (F=F 64 ) = 5  35  114520:
29F := F 64 (x; ) :
 + (x + 1) + x + x3 + 1 = 0:mE = 1;

RR = 428;mP = 1;mH = 1

RV = 2399;

W = 3.

q = 256;

g=4

A = (x)1 (2; 1):!

R = 302mB := 1;!

jS j = 76;

R=RV = 0:13;

RV =? 3919:

jS j=R = 0:25:h(F=F 256 ) = 5470220000; C l0 (F=F 256 ) = 5  5  5  43761760:
2
9
F := F 256 (x; ) :
 + (x + 1) + x + x3 + 1 = 0:mE = 1;mP = 1;

RR = 1181;
W = 2.

mH = 1

RV = 7868;

q = 512;g=4

A = (x)1 (2; 1):!

R = 1230mB := 1;!

jS j = 320;

R=RV = 0:16;

mP = 1;

RR = 2163;
W = 2.

mH = 1

RV = 25730;!

mB := 1;

R = 2279!

jS j = 566;

34
T = 111 s
n = 2; Cf = 5

RV =? 15520:

jS j=R = 0:26:
35
T = 562 s
n = 2; Cf = 5

h(F=F 512 ) = 76440901630; C l0 (F=F 512 ) = 76440901630:
2
9
F := F 512 (x; ) :
 + (x + 1) + x + x3 + 1 = 0:mE = 1;BEISPIELERV =? 44660:

R=RV = 0:089;

jS j=R = 0:25:

7.4.


HYPERELLIPTISCHE FUNKTIONENKORPER

91

7.4 Hyperelliptis he Funktionenkorper
Wir betra hten eine Familie von hyperelliptis hen Funktionenkorpern F=k fur
k = 3 , wel he dur hy 2 = f (x)
mit einem normierten, irreduziblen
Polynom
f
(
x
)
2
k
[
x
℄,
deg
f
(
x
)
 13 gege
ben werden. Ist deg f (x) gerade, so erhalten wir reell-quadratis he, andernfalls
imaginar-quadratis he Erweiterungen F=k(x) mit "Primdiskriminante\.
Die Tabelle gliedert si h wie folgt: d bezei hnet den Grad von f (x). In der mit
f (x) ubers hriebenen Spalte stehen die Anzahlen der Primpolynome f (x) desGrads d. Dana h folgen das Ges hle ht g, das Minimum hmin, Maximum hmax undarithmetis he Mittel h0 der Klassenzahlen. Die Spalte Cl : f (x) beinhaltet Eintrage
a : b, wobei a die Anzahl der Isomorphietypen der ni ht zyklis hen Klassengruppen
C l0 (F=k) und b die Anzahl der zugehorigen f (x) bedeutet. Bis auf Grad 12 sind die
ni ht zyklis hen Klassengruppen das Produkt zweier zyklis her Faktoren, wobei
der erste Faktor in den meisten Fallen =3 ist. Die Bere hnung der einzelnen
Klassengruppen nahm dur hs hnittli h 4:5s in Anspru h.
F

Z

d

1
2
3
4
5
6
7
8
9
10
11
12

f (x)

3
3
8
18
48
116
312
810
2184
5880
16104
44220

g

0
0
1
1
2
2
3
3
4
4
5
5

13 122640 6

hmin

hmax

1
1
1
1
1
7
2
6
3
29
3
35
9 111
12 13621 38733 51349 1291
86 1714

Z

h0

1:0
1:0
4:0
4:0
14:1
15:0
50:4
58:5
172:2
200:6
607:3
711:8

Cl : f (x)

0: 0
0: 0
0: 0
0: 0
0: 0
0: 0
0: 0
1 : 6 (3  12)
10 : 43
5 : 7841 : 198
41 : 838
1 : 3 (3  3  18)
155 4217 2029:9 186 : 1722

7.5 Viele Stellen vom Grad eins
Wir betra hten nun speziell konstruierte Funkionenkorper, wel he viele Stellen
vom Grad eins besitzen. Die ersten beiden Beispiele wurden uns von R. Auer
und G. Pirsi mitgeteilt und weisen die maximal mogli he Anzahl N1(F=k) auf,

92

KAPITEL 7.

BEISPIELE

das dritte Beispiel haben wir einer Tabelle von [19℄ entnommen. Ein besonders
aufalliges Verhalten des Klassengruppenverfahren lat si h hier ni ht beoba hten.
q = 4;

g = 13;N1 (F=k ) = 33

h(F=F 4 ) = 96486886125;
R(S0 ) = 1;

C l0(F=F 4 ) = 3  3  21  21  21  105  105  105:36

T = 1178 s

h(S0 ) = 96486886125,

C l(oS ) = 3  3  21  21  21  105  105  105:

8 + (x8 + x6 + x5 + x4 + x3 + x2 + 1)4 + (x10 + x9 + x3 + x2 )2 +(x10 + x9 + x8 + x6 + x5 + x4 ) + x22 + wx20 + wx18 + wx16 + x15 +w2 x12 + x11 + wx10 + x9 + wx8 + x6 + x5 + x4 = 0;

F := F 4 (x; ) :A = (x)1
mE = 5;

w2 + w + 1 = 0:

 (8; 1):

RR = 397;

mP = 4;

W = 1.
q = 2;

g = 9;

F := F 2 (x; ) :R = 644mB := 5;!

jS j = 345;

R=RV = 0:61;

N1 (F=k ) = 12h(F=F 2 ) = 135200;
R(S0 ) = 135200;!

mH = 1

RV = 1051;

n = 8;

RV =? 1286:

jS j=R = 0:54:

37
T = 997 s

C l0 (F=F 2 ) = 260  520:

h(S0 ) = 1;

Cf = 3C l(oS ) = 1:

12 +(x2 + x +1)10 +(x2 + x +1)9 +(x4 + x2 +1)8 +(x6 + x5 + x4 +x3 + x2 + x)6 +(x6 + x5 + x3 + x +1)5 +(x6 + x5 + x3 + x2 )4 +(x6 +x5 + x3 + x +1)3 +(x4 + x2 +1)2 +(x4 + x2 +1) + x2 + x +1 = 0:n = 12; Cf = 1

 (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1):mE = 8; mP = 8; mH = 2! mB := 8; jS j = 83; RV =? 112:
RR = 249; RV = 252; R = 196! R=RV = 0:78; jS j=R = 0:42:
A = (x)1

W = 3.
q = 9;

g = 7;

N1 (F=k ) = 36

h(F=F 9 ) = 86704128;
R(S0 ) = 48;

A = (x)1
mE = 3;



RR = 314;
W = 1.

h(S0 ) = 1806336;

4 + ( x5 + x4
n = 4; Cf = 3(2; 1; 2; 1):

F := F 9 (x; ) :mP = 2;38
T = 88 s

C l0 (F=F 9 ) = 16  48  336  336:

mH = 2

RV = 792;

C l(oS ) = 16  336  336:
x3 + x2 )2 + x8!

R = 470mB := 3;!

x6 + x5 + x4 + x3 + x2 = 0:

jS j = 256;

R=RV = 0:59;

RV =? 834:

jS j=R = 0:54:

7.6.

P -RANG DER KLASSENGRUPPE UND HASSE-WITT-INVARIANTE

7.6

93

p-Rang der Klassengruppe und Hasse-Witt-Invariante
Zum Abs hlu betra hten wir ein Beispiel fur die Bere hnung des p-Rangs der
Klassengruppe und der Hasse-Witt-Invariante eines globalen Funktionenkorpers
mit Hilfe des Cartier-Operators, wie in Abs hnitt 3.4 bes hrieben.
Es sei k = q mit q = 512 = 244140625 und F=k der dur hf (x; y ) = y 4 x2 y + 3x18 + 2
de nierte globale Funktionenkorper vom Ges hle ht g = 23.
Die Bere hnung der k-Basis der holomorphen Di erentiale 1 (F=k) benotigt 17s.
Dana h wird die Darstellungsmatrix (di;j )i;j 2 kgg des Cartier-Operators wie inSatz 3.26 in 82s bere hnet.
Fur den p-Rang der Klassengruppe gilt
dimF C l0 (F=k)[p℄ = 4;
die Hasse-Witt-Invariante betragt
 (F=k) = 15:
Hierfur wurde s hlieli h eine Zeit von 1:3s beziehunsgweise 1:8s in Anspru hgenommen.
Wir bemerken, da dieses Beispiel si herli h auerhalb der Rei hweite des allgemeinen Verfahrens der Klassengruppenbere hnung liegt. Auerdem wird klar,da die Bere hung diskreter Logarithmen in C l0(F=k)[p℄ in der Tat sehr eÆzient
dur hgefuhrt werden kann.
F

p

94

KAPITEL 7.

BEISPIELE

Symbolverzei hnis

(a)
(a)0
(a)1
[D℄
(D)0
(D)1

hM i
+_
A
A1


ont(h)CCf

C l(F=k)C ln(F=k)C l(oS )Cl(A; B )
0

deg
degk~
dim(D)

Hauptdivisor von a 2 F 
Nullstellendivisor des Hauptdivisors (a)Polstellendivisor des Hauptdivisors (a)Divisorenklasse von D
Nullstellendivisor des Divisors D
Polstellendivisor des Divisors D
Untergruppe von D(F=k), die von einer Menge M von Divisoren erzeugt wird
Innere direkte Summe
DivisorDivisor vom Grad eins
Charakter endli her Ordnung der Divisorenklassengruppe
Inhalt einer rationalen Funktion h 2 k(x)Cartier-OperatorKoeÆzientengroe des F=k erzeugenden Polynoms f (x; y)Divisorenklassengruppe von F=kMenge der Divisorenklassen vom Grad n von F=k
Idealklassengruppe von oS
Ring der uber A ganzalgebrais hen Elemente von B
1
0 = O (1) mit 0 jjv jj1  jjT v jj1  0 jjv jj1
Grad eines Divisors u ber dem exakten Konstantenkorper k0
Grad eines Divisors u ber dem Konstantenkorper k~Dimension des Riemann-Ro h-Raums L(D) uber dem exakten Konstantenkorper k0

95

2
2
2
3
2
2
2
32
56, 62
44
39
30
49
5
3
3
4
5
65
1
1
2

96
dimk~ (D)D , DiD

jDji
DF=k(x)D(F=k)
Dn(F=k)D(S )Dm(S )DSDS

max (F=k; A)
Dredm (F=k; A)
Dredmax (S; A)
Dredm (S; A)
Dred
ei
F

F=k
Fr =krgh(D )h(F=k )
h(S )

)
I (h
IS
IS
k
k0
kr


k

SYMBOLVERZEICHNIS

Dimension des Riemann-Ro h-Raums L(D) uber dem
Konstantenkorper k~
Divisoren(k; x)-dualer Divisor zu D
k [x℄-Invarianten des Divisors D
Di erentendivisor der Erweiterung F=k(x)Gruppe der Divisoren von F=kMenge der Divisoren vom Grad n von F=k
Gruppe der S -glatten Divisoren
Menge der S -glatten Divisoren vom Grad m
Das dem Divisor D zugeordnete Ideal von IS
Das dem Divisor D zugeordnete Ideal von IS
Menge der entlang A maximalreduzierten Divisoren
von F=kMenge der entlang A m-minimalreduzierten Divisoren
von F=kMenge der entlang A maximalreduzierten S -glatten
Divisoren
Menge der entlang A m-minimalreduzierten S -glatten
Divisoren
Verzweigungsindex einer Stelle Pi u ber 1
Algebrais her Abs hlu von F
Algebrais her Funktionenkorper
Konstantenkorpererweiterung vom Grad r
Ges hle ht eines Funktionenkorpers F=kHohe des Divisors D
Klassenzahl von F=kOrdnung der Idealklassengruppe von oS
Intervall um eine Approximation der Klassenzahl
Idealgruppe von oS
Idealgruppe von oS
Konstantenkorper
Exakter Konstantenkorper
Erweiterung des endli hen Konstantenkorpers k vom
Grad rAlgebrais her Abs hlu von k in F

2
2, 65
18, 20
12
19
2
2
3
3
12
12
23
23
56
56
22
39
1
7, 39
2, 14, 20
15
3
4
59
3
3
1
1
7, 39
43

SYMBOLVERZEICHNIS

S;A

S;A
lS;A

red
S;A
L(; t)L(D) 
md [D℄
mB
mE
mH
mP
n

NF=k(x)NFr =Fmax (S; A)
Nredm (S; A)
Nred
Nr ()Nr (F=k )!i ()!i (F=k )

(F=k)
(D)
O (), o()oSoS(oS )

r (F=k )F=k (n; m)ppS;AP , Pi

Divisorabbildung
Relationengitter
Quaderkantenlangedeg(A) (S; A) unter 
Bild von Dred
S;A
L-Reihe von 
Riemann-Ro h-Raum des Divisors D
Minimalgrad von [D℄Verwendete S hranke fur die Faktorbasis
S hranke fur die Erzeugung der Faktorbasis
Heuristis he S hranke fur die Faktorbasis
S hranke fur die Approximation der Klassenzahl
Erweiterungsgrad [F : k(x)℄ oder S hranke fur Stellen

97

65
65
67
65
39
2
44
74
60
74
60
5, 11, 51,
69, 74
Norm von F na h k(x)5Norm von Fr na h F
41Anzahl der entlang A maximalreduzierten S -glatten Di56
visorenAnzahl der entlang A m-minimalreduzierten S -glatten
56
Divisoren
Charaktersumme r-ten Grads
40
Charaktersumme r-ten Grads fur den Haupt harakter
7, 41
=1
Reziproke Nullstellen von L(; t)40
Reziproke Nullstellen von F=k (t)41Raum aller Di erentiale von F=k
2
Di erentialraum des Divisors D
2Landau-Symbole
7
Ring der an allen Stellen aus S ganzen Elemente
3
Ring der an allen Stellen auerhalb S ganzen Elemente
3S
Einheitengruppe von o , die S -Einheiten
4
Anzahl der Stellen des Grads r von F=k
42
Anzahl aller (n; m)-glatten Divisoren
51
Endli he Charakteristik des Korpers k
39, 48Glattheitswahrs heinli hkeit
74
Stellen von F=k
1, 21

98

SYMBOLVERZEICHNIS

P (F=k)P l(F=k )P ln (F=k)
P ln (F=k)
P (S )
q
QS;A

Qred
S;A
rS;A
R

R(S )

hi

R x

 (F=k )supp(D)SvPvP (D )
x

F=k (t)Gruppe der Hauptdivisoren von F=kMenge aller Stellen von F=kMenge der Stellen vom Grad n von F=kMenge der Stellen vom Grad kleiner glei h n von F=k
Gruppe der Hauptdivisoren von S -Einheiten
Elementanzahl des endli hen Korpers k
Quader in Zs
Quader in Zs
Relationenabbildung
Dedekindring
S -Regulator
Ring der rationalen Funktionen mit ganzem Inhalt
Hasse-Witt-Invariante von F=k
Trager des Divisors D
Ni ht-leere Menge von Stellen von F=k.
Exponentielle, surjektive Bewertung von F ! Z [f1gan der Stelle P
Exponent der Stelle P im Divisor D
Separierendes Element
Zeta-Funktion des Funktionenkorpers F=k

2
1
1
1
3
39, 48
67
67
66
30
4
30
44
2
5, 11, 5912
139

Literaturverzei hnis

[1℄ L. Adleman, J. DeMarrais, M.-D. Huang, A subexponential algorithm fordis rete logarithms over the rational subgroup of the Ja obians of large genus
hyperellipti urves over nite elds, Pro eedings of the First Symposium on

Algorithmi Number Theory, ANTS-I (Itha a, NY) (L. Adleman et. al., ed.),
LNCS 877, Springer-Verlag, Berlin - Heidelberg - New York, 1994, pp. 28{40.
[2℄ E. Artin und J. Tate, Class eld theory, Benjamin, New York, 1968.
[3℄ R. Auer, Ray lass elds of global fun tion elds with many rational pla es,
Dissertation, Carl-von-Ossietzky-Universitat, Oldenburg, 1999.
[4℄ E. Ba h, Expli it bounds for primality testing and related problems, Math.
Comp. 55 (1990), 355{380.
[5℄ E. Ba h, Improved approximations for Euler produ ts, CMS Conf. Pro . 15
(1995), 13{28.
[6℄ D. Le Brigand und J. J. Risler, Algorithme de Brill-Noether et odes deGoppa, Bull. So . Math. Fran e 116 (1988), 231{253.
[7℄ J. Bu hmann, A subexponential algorithm for the determination of lassgroups and regulators of algebrai number elds, Semin. Theor. Nombres,
Prog. Math. 91 (1990), 27{41.
[8℄ A. L. Chistov, The omplexity of onstru ting the ring of integers of a global
eld, Soviet Math. Dokl. 39 (1989), 597{600.
[9℄ H. Cohen, A ourse in algebrai number theory, 3rd orr. printing, GTM 138,
Springer-Verlag, Berlin - Heidelberg - New York, 1996.
[10℄ H. Cohen, Hermite and Smith normal form algorithms over Dedekind domains, Math. Comp. 65 (1996), 1681{1699.
[11℄ P. M. Cohn, Algebrai numbers and algebrai fun tions, Chapman & Hall,
London, 1991.
99

100

LITERATURVERZEICHNIS[12℄ M. Deuring, Le tures on the theory of algebrai fun tions of one variable,
LNM 314, Springer-Verlag, Berlin - Heidelberg - New York, 1973.
[13℄ M. Ei hler, Einfuhrung in die Theorie der algebrais hen Zahlen und Funktionen, Birkhauser Verlag, Basel, 1963.
[14℄ G. Frey, On the stru ture of the lass group of a fun tion eld, Ar h. Math.
33 (1979), 33{40.
[15℄ G. Frey, M. Muller und H.-G. Ru k, The Tate pairing and the dis rete logarithm applied to ellipti urve ryptosystems, Preprint, 1998.
[16℄ G. Frey und H.-G. Ru k, A remark on erning m-divisibility and the dis rete
logarithm in the divisor lass group of urves, Math. Comp. 62 (1994), 865{874.
[17℄ C. Friedri hs, Bere hnung relativer Ganzheitsbasen mit dem Round-2-Algorithmus, Diplomarbeit, Te hnis he Universitat Berlin, 1997.
[18℄ W. Fulton, Algebrai urves, Benjamin, New York, 1969.
[19℄ G. van der Geer, M. van der Vlugt, Tables of urves with many points, regelmaig aktualisierte Tabelle unter http://www.wins.uva.nl/ geer.
[20℄ G. Ha he, Computation in algebrai fun tion elds for e e tive onstru tion of algebrai -geometri odes, Applied algebra, algebrai algorithms anderror- orre ting odes, AAECC-11 (Paris) (G. Cohen et al., ed.), LNCS 948,
Springer-Verlag, Berlin - Heidelberg - New York, 1995, pp. 262{278.
[21℄ H. Hasse und E. Witt, Zyklis he unverzweigte Erweiterungskorper vom Primzahlgrade p uber einem algebrais hen Funktionenkorper der Charakteristik p,
Monatsh. Math. Phys. 43 (1936), 477{492.
[22℄ H. Heilbronn, Zeta-fun tions and L-fun tions, Algebrai Number Theory(J. W. S. Cassels & A. Frohli h, ed.), A ademi Press, London, 1967, pp. 204{230.
[23℄ F. He, Zur Klassengruppenbere hnung in algebrais hen Zahlkorpern, Diplomarbeit, Te hnis he Universitat Berlin, 1996.
[24℄ M.-D. Huang, D. Ierardi, Counting points on urves over nite elds, J.
Symboli Comp. 25 (1998), 1{21.
[25℄ Kant-Gruppe, KASH, http://www.math.tu-berlin.de/ kant, 1999.

LITERATURVERZEICHNIS

101[26℄ N. Koblitz, Hyperellipti ryptosystems, J. Cryptology 1 (1989), 139{150.
[27℄ H. Ko h, Zahlentheorie, Vieweg Verlag, Brauns hweig, 1997.
[28℄ M. Kruse, H. Sti htenoth, Ein Analogon zum Primzahlsatz fur algebrais heFunktionenkorper, manus ripta math. 69 (1990), 219{221.
[29℄ S. Lang, Ellipti fun tions, Addison-Wesley Publishing Company, Reading,
Massa husetts, 1973.
[30℄ J. I. Manin, The Hasse-Witt matrix of an algebrai urve, Trans. Amer.
Math. So . 45 (1965), 245{264.
[31℄ A. Menezes, Ellipti urve publi key ryptosystems, Kluwer A ademi Publishers, Boston, 1993.
[32℄ J. S. Milne, Abelian varieties, Arithmeti Geometry (Storrs, Conne ti ut)(G. Cornell & J. H. Silverman, ed.), Springer-Verlag, Berlin - Heidelberg New York, 1986, pp. 103{150.
[33℄ C. Moreno, Algebrai urves over nite elds, Cambridge University Press,
Cambridge, 1991.
[34℄ J. Neukir h, Algebrais he Zahlentheorie, Springer-Verlag, Berlin - Heidelberg- New York, 1992.
[35℄ D. Panario, X. Gourdon und Ph. Flajolet, An analyti approa h to smoothpolynomials over nite elds, Pro eedings of the Third Symposium on Algorithmi Number Theory, ANTS-III (Portland, Oregon) (J. Buhler, ed.),
LNCS 1423, Springer-Verlag, Berlin - Heidelberg - New York, 1998, pp. 226{
236.
[36℄ M. E. Pohst, Computational algebrai number theory, DMV-Seminar 21,
Birkhauser Verlag, Basel-Boston-Berlin, 1993.
[37℄ M. E. Pohst and H. Zassenhaus, Algorithmi algebrai number theory, 1stpaperba k ed., Cambridge University Press, Cambridge, 1997.
[38℄ C. Pomeran e, Analysis and omparison of some integer fa toring algorithms,
Computational Methods in Number Theory (R. Tijdeman & H. Lenstra, ed.),Mathematis h Centrum, Tra t 154, Amsterdam, 1982, pp. 89{139.

102

LITERATURVERZEICHNIS[39℄ B. Poonen, Computational aspe ts of urves of genus at least 2, Pro eedingsof the Se ond Symposium on Algorithmi Number Theory, ANTS-II (Talen e, Fran e) (H. Cohen, ed.), LNCS 1122, Springer-Verlag, Berlin - Heidelberg - New York, 1996, pp. 283{306.
[40℄ H.-G. Quebbemann, Estimates of regulators and lass numbers in fun tionelds, J. reine angew. Math. 419 (1991), 79{87.
[41℄ F. Reinhard und H. Soeder, dtv-Atlas zur Mathematik Band 2, Deuts her
Tas henbu h Verlag, Mun hen, 1990.
[42℄ M. Rosen, The asymptoti behavior of the lass group of a fun tion eld overa nite eld, Ar h. Math. 24 (1973), 287{296.
[43℄ M. Rosen, S -units and S - lass group in algebrai fun tion elds, J. Algebra
26 (1973), 98{108.
[44℄ M. Rosenbloom, M. Tsfasman, Multipli ative latti es in global elds, Invent.
math. 101 (1990), 687{696.
[45℄ H.-G. Ru k, Class groups and L-series of fun tion elds, J. Number Th. 22(1986), 177{189.
[46℄ H.-G. Ru k, On the dis rete logarithm in the divisor lass group of urves,
Preprint, 1997.
[47℄ E. S heid, Ein neuer Algorithmus zur Bere hnung der Klassenzahl algebrais her Zahlkorper, Diplomarbeit, Universitat des Saarlandes, 1993.
[48℄ F. K. S hmidt, Analytis he Zahlentheorie in Korpern der Charakteristik p,
Math. Zeit. 33 (1931), 1{32.
[49℄ R. S hoof, Ellipti urves over nite elds and the omputation of squareroots, Math. Comp. 44 (1985), 483{494.
[50℄ M. S hornig, Untersu hung konstruktiver Probleme in globalen Funktionenkorpern, Dissertation, Te hnis he Universitat Berlin, 1996.
[51℄ J. P. Serre, Sur la topologie des varietes algebriques en ara teristique p,
Sympos. Internat. Topologia Algebrai a (Mexi o City), 1956, pp. 24{53.
[52℄ M. Seysen, A probabilisti fa torization algorithm with quadrati forms ofnegative dis riminant, Math. Comp. 48 (1987), 757{780.

LITERATURVERZEICHNIS

103[53℄ A. Stein, Algorithmen in reell-quadratis hen Kongruenzfunktionenkorpern,
Dissertation, Universitat des Saarlandes, 1996.
[54℄ H. Sti htenoth, Die Hasse-Witt-Invariante eines Kongruenzfunktionenkorpers, Ar h. Math. 33 (1979), 357{360.
[55℄ H. Sti htenoth, Algebrai fun tion elds and odes, Springer-Verlag, Berlin Heidelberg - New York, 1993.
[56℄ J. Graf v. S hmettow, Beitrage zur Klassengruppenbere hnung, Dissertation,
Heinri h-Heine Universitat Dusseldorf, 1991.
[57℄ E. Vol he k, Computing in the Ja obian of a plane algebrai urve, Proeedings of the First Symposium on Algorithmi Number Theory, ANTS-I(Itha a, NY) (L. Adleman et. al., ed.), LNCS 877, Springer-Verlag, Berlin Heidelberg - New York, 1994, pp. 221{233.
[58℄ E. Vol he k, Addition in the Ja obian of a urve over a nite eld, Computational Number Theory (Oberwolfa h), onferen e manus ript, 1995.
[59℄ A. Weil, Sur les ourbes algebriques et les varietes qui s'en deduisent, Hermann, Paris, 1948.

104

105

Zusammenfassung
Es sei F=k ein algebrais her Funktionenkorper, gegeben dur h
F = k(x; ) mit f (x; ) = 0
fur ein in y normiertes und separables, irreduzibles Polynom f (x; y) 2 k[x; y℄.
Wir bes hreiben eine konstruktive Fassung der Riemann-Ro h-Theorie, die es
uns gestattet, das Ges hle ht g von F=k und Riemann-Ro h-Raume L(D) von
Divisoren D mit Te hniken der algorithmis hen algebrais hen Zahlentheorie zu
bere hnen. Wir geben ferner einen wi htigen Algorithmus zur Divisorreduktion
an und entwi keln Methoden, mit denen zusatzli h diskrete Bewertungen von kberu ksi htigt werden konnen.
Es sei k = q der exakte Konstantenkorper des globalen Funktionenkorpers F=k.
Die Divisorenklassengruppe ist die Gruppe aller Divisorenklassen von F=k. Die
Klassengruppe C l0 (F=k) ist die endli he Gruppe der Divisorenklassen vom Gradnull. Ihre Ordnung ist die Klassenzahl h(F=k).
Fur eine Menge S von Stellen P von F=k mit deg(P )  m beweisen wir mit
Hilfe des Satzes von Hasse-Weil untere S hranken fur m, so da C l0 (F=k) dur hdie Klassen der Divisoren vom Grad null mit Trager in S erzeugt wird. Diese
S hranken sind von der Form O log(g) bei festem q. Weiter geben wir eine
Formel fur die Approximation von h(F=k) bis auf einen festen, multiplikativen
Fehler an, fur wel he die Anzahlen der Stellen eines Grads ebenfalls O log(g)benotigt werden, und formulieren eine Version des Satzes von Brauer-Siegel fur
globale Funktionenkorper.
Wir betra hten Glattheitseigens haften. Ein Divisor D ist (n; m)-glatt, wenndeg(D)  n gilt und sein Trager nur aus Stellen eines Grads  m besteht. Wir beweisen vers hiedene Aussagen uber die Anzahl sol her Divisoren und formulieren
eine Glattheitsannahme.
Das Hauptergebnis ist das Klassengruppenverfahren zur Bere hnung der Klassengruppe beziehungsweise Divisorenklassengruppe von F=k. Dieses stutzt si h auf
die Relationenmethode, fur die wir bei festem q deterministis he, in g aber exponentielle Te hniken und eine probabilistis he, unter der Glattheitsannahme in g
subexponentielle Te hnik entwi keln. Die vorhergehenden Ergebnisse werden hiereingesetzt. Wir bes hreiben Anwendungen dieses Verfahrens zur Einheiten- und
Idealklassengruppenbere hnung und zur Bestimmung diskreter Logarithmen.
Den Abs hlu bilden einige illustrative Beispiele, die das Laufzeitverhalten und
die Anwendbarkeit des Verfahrens unter Variation der wesentli hen Parameter q
und g demonstrieren.
F