DIPLOMARBEIT

Algebraisch-geometrische Codes

ausgeführt am Institut für Geometrie der Technischen Universität Wien

unter der Anleitung von Ao.Univ.Prof. Dr. Michael Drmota

durch

Clemens Fuchs

Novaragasse 24/15 1020 Wien

10. August 2000 .............................

Vorwort

Durch den Eintritt der Industriestaaten in das Informationszeitalter und die revolutionären Erneuerungen im Bereich der Unterhaltungselektronik, haben in den letzten Jahrzehnten Methoden zur Fehlerbehandlung bei der Datenübertragung eine bedeutendere Rolle denn je erlangt. Diese sind das Forschungsgebiet der Codierungstheorie, dessen Ergebnisse jetzt von jedermann, ob beim Internetsurfen, Telefonieren oder beim Abspielen einer CD, bewusst oder unbewusst genutzt werden. Codes mit guten Fehlererkennungsund -korrektureigenschaften werden benötigt, um die notwendigen Datenübertragungen möglich zu machen.

Es ist ein wohlbekanntes Problem der Codierungstheorie, dass lange Codes mit günstigen Eigenschaften schwierig zu konstruieren sind. Die Gilbert-Varshamov-Schranke besagt, dass eine Folge von Codes mit wachsender Blocklänge, hohen Informationsraten und entsprechend guten Fehlerkorrektureigenschaften existiert. Man nennt solche Familien von Codes ”gut“. Der Beweis dieses Satzes ist allerdings nicht konstruktiv, er enthält also keinen Hinweis wie man derartige Codes konstruieren kann.

Einer der wichtigsten Fortschritte in der Theorie der fehlerkorrigierenden Codes war die Verwendung von Methoden aus der algebraischen Geometrie. Diese Entdeckung geht auf V. D. Goppa zurück der 1981 die Klasse der geometrischen Goppa-Codes (auch algebraisch-geometrische Codes genannt) eingeführt hat (siehe [7]). Geometrische Goppa-Codes haben hervorragende asymptotische Eigenschaften und Goppa konnte zeigen, dass diese Codes die Gilbert-Varshamov-Schranke erreichen. Das war der erste Fortschritt innerhalb von 30 Jahren. Tsfasman, Vlǎdut und Zink zeigten 1982, dass mit Hilfe von geometrischen Goppa-Codes, die Gilbert-Varshamov-Schranke sogar noch verbessert werden kann. Alle diese Ergebnisse waren aber nach wie vor nicht konstruktiv. Mittlerweile gibt es allerdings sogar schon die ersten expliziten Beschreibungen solcher Codes (siehe z.B. [18]).

In den letzten Jahren entdeckten Xing, Niederreiter und Lam neue Methoden um Codes mit Hilfe der algebraischen Geometrie zu konstruieren (siehe [15], [25] und [26]), indem sie ihre Konstruktionen im Zusammenhang mit low-discrepancy sequences (siehe [13] und [24]) betrachteten. Dabei verwendeten sie Ansätze, die sich wesentlich von denen Goppas unterschieden. Özbudak und Stichtenoth fanden durch Verallgemeinerung dieser Konstruktionen eine äquivalente Beschreibung der geometrischen Goppa-Codes (siehe [16]). Neue Einblicke in die Natur dieser Codes ergeben sich durch die Betrachtung von Spezialklassen, die man durch die Konstruktionen von Xing, Niederreiter und Lam erhält (siehe [25]).

Insbesondere die letzten Konstruktionen von Xing, Niederreiter und Lam (siehe [15] und [26]), die eine echte Verallgemeinerung der geometrischen Goppa-Codes darstellen und daher den Namen verallgemeinerte algebraischgeometrische Codes bekommen haben, scheinen sehr vielversprechend zu sein. Es handelt sich dabei zweifellos um eine weitreichende und sehr interessante Verallgemeinerung der geometrischen Goppa-Codes. Man kann mit ihrer Hilfe sehr gute - ja sogar bestmögliche - Beispiele für Codes über kleinen Alphabeten angeben, was mit Hilfe von geometrischen Goppa-Codes nicht möglich zu sein scheint.

Diese Arbeit soll die oben erwähnten Themen aufarbeiten und ist folgendermaßen gegliedert:

Im ersten Kapitel werden die Grundlagen der Codierungstheorie dargestellt. Die dazu notwendigen Begriffe, wie Codes, Gewicht und Distanz, Fehlererkennung und Fehlerkorrektur, etc., werden exakt eingeführt und die wichtigsten Eigenschaften bewiesen. Im Abschnitt 1.5 wird die Gilbert-Varshamov-Schranke formuliert und bewiesen und die Probleme, die sich daraus ergeben, aufgezeigt. In Abschnitt 1.6 behandeln wir die in den Anwendungen (bisher) am häufigsten verwendeten Codes, die BCH-Codes und geben dadurch weitere Motivation zur Suche nach guten Codes. Dieser Teil der Arbeit richtet sich vor allem nach dem Buch von Pretzel (siehe [17]).

Im zweiten Kapitel wird die Sprache entwickelt, um algebraisch-geome-trische Codes betrachten zu können, nämlich die Theorie der algebraischen Funktionenkörper. Solche algebraische Objekte treten in natürlicher Weise in vielen Bereichen der Mathematik auf, wie etwa in der algebraischen Geometrie, der algebraischen Zahlentheorie oder in der komplexen Analysis. Tatsächlich ist die Theorie der algebraischen Funktionenkörper äquivalent zur Theorie der algebraischen Kurven. Wir wählen aber den rein algebraischen Zugang, da man dadurch relativ schnell zum Hauptergebnis, dem Satz von Riemann-Roch kommt, der in Abschnitt 2.6 behandelt wird. Durch diese Vorgangsweise erspart man sich viel Topologie, die beim Studium der algebraischen Kurven notwendig ist und die man zusätzlich zur Algebra benötigt. Dieses Kapitel stammt zum größten Teil aus dem Buch von Stichtenoth (siehe [19]) und zu einem kleineren Teil aus dem Buch von Pretzel (siehe [18]).

Im dritten Kapitel können wir die geometrischen Goppa-Codes einführen und mit Hilfe des Satzes von Riemann-Roch deren Parameter abschätzen. Dabei werden wir zwei Beschreibungen von Goppa und eine Beschreibung nach Xing - Niederreiter - Lam und Özbudak - Stichtenoth kennenlernen. In Abschnitt 3.3 untersuchen wir spezielle Klassen von geometrischen Goppa-Codes: die rationalen Goppa-Codes, welche die BCH-Codes als Spezialfall enthalten, und die sogenannten XNL-Codes, welche auf den Konstruktionen von Xing, Niederreiter und Lam beruhen. Im Abschnitt 3.4 schließlich, werden wir die Beziehung zwischen den geometrischen Goppa-Codes und der asymptotischen Gilbert-Varshamov-Schranke kennenlernen und sehen, dass sie durch diese verbessert werden kann. Dieses Kapitel beruht hauptsächlich auf dem Buch von Stichtenoth (siehe [19]) und weiters auf den Arbeiten von Xing, Niederreiter, Lam und Özbudak, Stichtenoth (siehe [15],[25],[26] und [16]).

Das vierte und letzte Kapitel beschäftigt sich schlußendlich mit den verallgemeinerten algebraisch-geometrischen Codes, ihrer Konstruktion und es wird eine interessante Teilklasse vorgestellt, die eine offensichtliche Verallgemeinerung der geometrischen Goppa-Codes ist. Im Abschnitt 4.2 wird sich zeigen, dass wir dadurch Codes gewinnen können, die in einem gewissen Sinne Weltrekorde sind.

Abschließend möchte ich mich noch herzlich bei Herrn Prof. Niederreiter bedanken, der das Thema vorgeschlagen hat und bei der Literaturauswahl federführend war. Weiterer Dank gebührt meinem Betreuer Herrn Prof. Drmota und nicht zuletzt meinem Bruder Michael, für das sorgfältige Korrekturlesen.

Wien, August 2000 Clemens Fuchs

Inhaltsverzeichnis

1 Grundlagen der Codierungstheorie 5 1.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Blockcodes, Gewicht und Distanz . . . . . . . . . . . . . . . . 6 1.3 Linearcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Äquivalente Codes . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Die Gilbert-Varshamov-Schranke . . . . . . . . . . . . . . . . 16 1.6 BCH-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Algebraische Funktionenkörper 24 2.1 Funktionenkörper und Stellen . . . . . . . . . . . . . . . . . . 24 2.2 Bewertungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Der rationale Funktionenkörper . . . . . . . . . . . . . . . . . 37 2.4 Divisoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.5 Adèle und Weil-Differentiale . . . . . . . . . . . . . . . . . . . 50 2.6 Der Satz von Riemann-Roch und Anwendungen . . . . . . . . 58 2.7 Die P -adische Vervollständigung . . . . . . . . . . . . . . . . 66 2.8 Die Hasse-Weil-Schranke . . . . . . . . . . . . . . . . . . . . . 70

3 Geometrische Goppa-Codes 75 3.1 Konstruktion nach Goppa . . . . . . . . . . . . . . . . . . . . 75 3.2 Konstruktion nach Xing - Niederreiter - Lam und Özbudak -

Stichtenoth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.3 Einige spezielle Klassen von Goppa-Codes . . . . . . . . . . . 86 3.4 Geometrische Goppa-Codes und die asymptotische Gilbert-

Varshamov-Schranke . . . . . . . . . . . . . . . . . . . . . . . 96

4 Verallgemeinerte AG-Codes 100 4.1 Konstruktion nach Xing - Niederreiter - Lam . . . . . . . . . 100 4.2 Gewinn gegenüber Goppas Konstruktion . . . . . . . . . . . . 108

Kapitel 1

Grundlagen der Codierungstheorie

1.1 Einführung

Die Anwendungsgebiete der Codierungstheorie sind sehr vielfältig, jedoch haben alle folgendes gemeinsam: Informationen sollen von einer Quelle über einen Informationskanal zu einem Empfänger geschickt werden. Dabei treten in der Regel Fehler auf. Ziel der Codierungstheorie ist es, Strategien zu entwickeln, die bei der Übertragung aufgetretenen Fehler zu erkennen und zu korrigieren. Beispiele für solche Übertragungen sind: gesprochene Nachrichten, Funk, Audiosysteme, Fernsehen, Computernetze, Satellitenkommunikation, Datenspeicherung, usw.

Um Fehler zu erkennen bzw. zu korrigieren, werden die folgenden beiden Prinzipien angewandt:

• Redundanz,

• Grammatik.

Diese Prinzipien sind uns von der natürlichen Sprache her wohlbekannt. Die Wörter in unserer Sprache bilden nur einen sehr kleinen Teil der möglichen Zeichenketten. Außerdem ergeben nur wenige Folgen von Wörtern einen Satz. Wir können sagen, dass mit sehr großer Wahrscheinlichkeit ein Fehler nur wenige Buchstaben betreffen wird. Da in der natürlichen Sprache die Anzahl der Worte, die man durch Änderung von nur wenigen Buchstaben ineinander überführen kann, gering ist, wird ein falsch geschriebenes Wort mit großer Wahrscheinlichkeit als solches erkannt, und da nur wenige mögliche Kandidaten als korrekte Version in Frage kommen, kann man es vielleicht sogar korrigieren. Insbesondere kann dazu die Grammatik nutzbringend eingesetzt werden.

Im folgenden wollen wir stets annehmen, dass eine Nachricht aus den Symbolen einer festen, endlichen Menge A aufgebaut ist, die wir das Alphabet nennen. Das Alphabet soll ein Nullsymbol besitzen, welches wir mit 0 bezeichnen.

Als erstes wollen wir den Kanal modellieren über den wir die Informationen senden. Dieses Modell wird natürlich umso komplizierter, je besser wir versuchen die Wirklichkeit nachzubilden. Das einfachste Modell erhält man unter der Annahme, dass es zu jedem Paar verschiedener Symbole a,b ∈ A eine feste Wahrscheinlichkeit p_{a,b} gibt, die angibt mit welcher Wahrscheinlichkeit b empfangen wird, wenn a gesendet wurde. Man spricht von einem Zufallsfehler-Kanal. Außerdem wollen wir noch annehmen, dass die Wahrscheinlichkeiten p_{a,b} dieselben sind für alle Paare a, b mit a ≠ b. Einen solchen Kanal nennt man symmetrisch. Im folgenden wollen wir stets annehmen, dass wir einen symmetrischen Zufallsfehler-Kanal haben.

Die nächste Stufe in unserem Modell ist der Encoder. Dieser wandelt die Eingangsnachricht um, sodass Fehler erkannt und korrigiert werden können. Zum Schluß benötigen wir noch einen Decoder, der die ursprüngliche Nachricht wieder herstellt, nachdem der Fehler- Prozessor die Nachricht auf eventuelle Fehler untersucht, diese korrigiert, oder mit einem Fehlersignal abgebrochen hat.

1.2 Blockcodes, Gewicht und Distanz

Wir wollen stets annehmen, dass unser Encoder (den wir gleich definieren werden) die Nachricht in Wörter bzw. Blöcke zerlegt, das heißt in Folgen von Symbolen fester Länge k. Der Encoder übersetzt jedes Wort in ein Codewort mit fester Länge n. Solche Codes nennt man Blockcodes.

Definition 1.2.1 Es sei A ein Alphabet. Eine Folge von n Symbolen aus A nennen wir ein A-Wort (oder kurz Wort) der Länge n. Die Menge aller A-Wörter der Länge n bezeichnen wir mit A^{n}.

Wenn A aus q Symbolen besteht, dann gibt es genau q^{n} A-Wörter der Länge n. Wir können jetzt Blockcodes formal definieren:

Definition 1.2.2 Ein [n, k]-Blockcode C über einem Alphabet A mit q Elementen ist eine Teilmenge von A^{n} bestehend aus genau q^{k} Codewörtern. Ein Encoder E für C ist eine bijektive Abbildung von A^{k} nach C, welche jedem A-Wort x der Länge k ein Codewort u = E(x) zuordnet. Der dazugehörige Decoder D ist die zu E inverse Abbildung. Die Zahl n heißt Länge des Codes, k heißt der Rang oder die Dimension des Codes und k/n heißt die Rate des Codes C.

Der Encoder setzt das Codewort oft so zusammen, daß das Nachrichtenwort x der Anfang des Codewortes E(x) ist. Einen solchen Encoder nennen wir systematisch. In diesem Fall besteht das Codewort aus dem Nachrichtenwort und den Prüfziffern. Der Decoder lässt lediglich die Prüfzeichen weg. Da k ≤ n ist, muss die Rate stets ≤ 1 sein.

Zunächst wollen wir die Methoden zur Fehlererkennung und Fehlerkorrektur betrachten, welche nur das Redundanzprinzip verwenden. Sei also C ⊆ A^{n}. Jedes w ∈ A^{n} heißt ein Empfangswort. Ist w ∈ F := A^{n}\C, so hat ein Übertragungsfehler stattgefunden. Ist w ∈ C, so kann man trotzdem die Möglichkeit eines Fehlers nicht ausschließen.

Definition 1.2.3 Für v = (v_{1}, …, v_{n}), w = (w_{1}, …, w_{n}) ∈ A^{n} heißt die Anzahl der Stellen i ∈ {1, …, n} mit v_{i} ≠ w_{i} (Hamming-) Distanz d(v, w) von v, w. Das (Hamming-) Gewicht wt(v) von v ist die Anzahl der von 0 verschiedenen Einträge von v.

Satz 1.2.4 Die Hamming-Distanz ist eine Metrik auf A^{n}.

Beweis. Aus der Definition folgt sofort, dass d(v, w) stets eine positive, reelle Zahl ist, dass d(v, w) = 0 ⇔ v = w gilt und dass d(v, w) = d(w, v) ist. Es bleibt also die Dreiecksungleichung zu zeigen: Sei x = (x_{1}, …, x_{n}), y = (y_{1}, …, y_{n}) und z = (z_{1}, …, z_{n}). Dann ist d(x, z) gleich der Anzahl der Stellen in denen sich x und z unterscheiden. Sei U die Menge der Indizes dieser Stellen, dann ist

d(x, z) = |U| = |{i | x_{i} ≠ z_{i}}|.

Sei S = {i | x_{i} ≠ z_{i} und x_{i} = y_{i}} und T = {i | x_{i} ≠ z_{i} und x_{i} ≠ y_{i}}. Dann ist U die disjunkte Vereinigung von S und T. Also gilt

d(x, z) = |S| + |T |.

Aus der Definition von d(x, y) und T folgt daher, dass

|T | ≤ d(x, y).

Andererseits gilt für i ∈ S, dass y_{i} = x_{i} ≠ z_{i} ist. Es folgt

|S| ≤ d(y, z),

und damit insgesamt d(x, z) ≤ d(x, y) + d(y, z). □

Definition 1.2.5 Ein Fehler-Prozessor P für einen [n, k]-Code C über A ist eine Abbildung, die einem Empfangswort w das Paar (a, u) zuordnet, wobei a die Werte ”gut“ oder ”schlecht“ annehmen kann und u ein Wort der Länge n ist. Dabei hat das Signal a hat den Wert ”gut“, wenn w ein Codewort ist und sonst ”schlecht“. Ein Fehler-Prozessor, der stets u = w liefert, nennt man einen Fehler-Detektor und einen, der stets ein Codewort von C zurückliefert nennt man perfekt.

Das Prinzip der Decodierung ist das Folgende: Wird w ∈ A^{n} empfangen, so werden wir annehmen, dass es von einem c ∈ C stammt, für welches d(c, w) minimal ist. Gibt es ein solches c, so wird w als dieses c decodiert. Gibt es mehr als ein solches c, dann erhält man keine eindeutige Entscheidung.

Definition 1.2.6 Es sei v ein gesendetes A-Wort und w ∈ A^{n} das empfangene Wort. Weiters sei t := d(v, w). Dann heißt t die Anzahl der Übertragungsfehler und wir sagen, dass t Fehler aufgetreten sind, oder dass ein Fehler mit Gewicht t stattgefunden hat.

Definition 1.2.7 Sei P ein Fehler-Prozessor für einen [n, k]-Code C über A. Wir sagen, P kann alle Fehler vom Gewicht ≤ t erkennen, wenn kein Codewort durch einen Fehler mit Gewicht ≤ t in ein anderes Codewort übergeführt werden kann. Wir sagen außerdem, P kann alle Fehler vom Gewicht ≤ t korrigieren, wenn zu jedem Empfangswort w ∈ A^{n} genau ein Codewort c mit d(w, c) ≤ t existiert.

Ein Fehler-Prozessor überprüft also zuerst, ob das Empfangswort w ein Codewort ist oder nicht. Wenn w ein Codewort ist, dann ist die Aufgabe des Fehler-Prozessors beendet, dass Wort wird als ”gut“ bewertet und weitergeleitet. Das bedeutet, wenn ein Fehler so auftritt, dass ein Codewort in ein anderes gestört wird, dann kann dieser Fehler nicht entdeckt und damit auch nicht korrigiert werden. Wenn wir alle Fehler bis zum Gewicht t erkennen wollen, ist es klarerweise notwendig, dass zwei verschiedene Codewörter mindestens Distanz t + 1 haben. Deshalb liegt es auf der Hand, folgendes Maß für den kleinstmöglichen Abstand zwischen verschiedenen Codewörtern einzuführen.

Definition 1.2.8 Sei C ein [n, k]-Code über A. Wir nennen

d := min_{x,y∈C,x≠y} d(x, y)

die Minimaldistanz von C. Dieses Maß ist so wichtig, dass wir C auch einen [n, k, d]-Code nennen.

Es gilt dann der folgende Satz:

Satz 1.2.9 Sei C ein [n, k]-Code über A und t ∈ ℕ. Dann kann ein Fehler-Prozessor für C alle Fehler mit Gewicht ≤ t erkennen, genau dann wenn d ≥ t + 1 ist.

Beweis. Wenn u und v Codewörter sind mit u ≠ v und d(u, v) ≤ t, dann kann u in v durch einen Fehler vom Gewicht ≤ t übergeführt werden. In diesem Fall kann kein Fehler-Prozessor für C alle Fehler vom Gewicht ≤ t erkennen. Umgekehrt gilt, wenn je zwei Codewörter mindestens Distanz t+1 voneinander haben, dann führt ein Fehler vom Gewicht t ein Codewort in ein Wort über das kein Codewort ist. Der Fehler kann also entdeckt werden, indem man überprüft, ob das empfangene Wort ein Codewort ist. Also sind alle Fehler mit Gewicht ≤ t erkennbar. □

Satz 1.2.10 Es gibt einen Fehler-Prozessor für den [n, k]-Code C über A, welcher alle Fehler bis zum Gewicht t ∈ ℕ korrigiert, dann und nur dann, wenn d ≥ 2t + 1.

Beweis. Angenommen es gibt Codewörter u und v mit u ≠ v und d(u, v) ≤ 2t. Sei w ein Wort das mit u an allen Stellen übereinstimmt, an denen u mit v übereinstimmt. Weiters soll w mit u an den ersten t Stellen übereinstimmen, an denen u und v nicht übereinstimmen und an den restlichen Stellen soll w mit v übereinstimmen (wenn d(u, v) < t dann wählen wir w = u). Dann gilt: d(u, w) ≤ t und d(v, w) ≤ t. Angenommen w wird zusammen mit der Information empfangen, dass höchstens t Fehler aufgetreten sind. Dann kann sowohl u als auch v (oder ein ganz anderes Wort) gesendet worden sein. Also gibt es keinen Fehler-Prozessor der Fehler vom Gewicht ≤ t korrigieren kann. Umgekehrt nehmen wir an, dass ein Wort w zusammen mit der Information empfangen wurde, dass höchstens t Fehler aufgetreten sind. Wenn es zwei Codewörter u und v mit d(u, w) ≤ t und d(v, w) ≤ t geben würde, dann müßte d(u, v) ≤ 2t gelten. Widerspruch zur Annahme, dass d ≥ 2t + 1 gilt. Also gibt es ein eindeutiges Wort u mit d(u, w) ≤ t, und wir decodieren w durch u. □

1.3 Linearcodes

Als nächstes wollen wir das Prinzip der Grammatik nachbilden, indem wir dem Alphabet A und damit auch A^{n}, sowie dem Code C Struktur verleihen. Dies führt uns zum Begriff des Linearcodes.

Definition 1.3.1 Sei das Alphabet A der endliche Körper 𝔽_{q} mit q Elementen. Dann heißt ein [n, k]-Code C über A ein Linearcode, wenn C ein Unterraum des Vektorraumes A^{n} ist.

Wenn C ein [n, k]-Linearcode über 𝔽_{q} ist, dann ist k = dim(C). Wir nützen diese Struktur um die Minimaldistanz eines Linearcodes zu charakterisieren.

Satz 1.3.2 Für einen [n, k]-Linearcode C über 𝔽_{q} ist die Minimaldistanz gleich dem minimalen Gewicht aller vom Nullwort verschiedenen Codewörter.

Beweis. Für Codewörter u und v gilt d(u, v) =wt(u − v). Aufgrund der Linearität ist u − v wieder ein Codewort. □

Wenn ein Wort c gesendet und y ∈ A^{n} empfangen worden ist, so heißt e = y − c Fehlerwort (Fehlermuster oder kurz Fehler) von c. Es gilt:

wt(e) = wt(y − c) = d(y, c) = Anzahl der Übertragungsfehler.

Wenn wir mit Linearcodes arbeiten, dann werden wir stets verlangen, dass der Encoder die Linearität respektiert. Deshalb definieren wir:

Definition 1.3.3 Ein linearer Encoder E für einen [n, k]-Linearcode C über 𝔽_{q} ist ein Isomorphismus von 𝔽_{q}^{k} auf C.

Da wir nun nur mehr Linearcodes betrachten, sprechen wir in der Folge kurz von einem Encoder.

Definition 1.3.4 Sei C ein linearer [n, k]-Code über 𝔽_{q} mit Encoder E. Sei G jene k × n - Matrix, sodass E(x) = xG für jedes Wort x mit Länge k ist. Dann heißt G eine Generatormatrix des Codes C.

Wenn wir also eine Generatormatrix G eines [n, k]-Codes C über 𝔽_{q} gegeben haben, dann ist durch E(x) := xG eindeutig ein Encoder für C definiert. Wir haben einen Encoder systematisch genannt, wenn das Nachrichtenwort genau die ersten k Symbole des zugehörigen Codewortes sind. Diese Eigenschaft kann man sehr leicht an der Generatormatrix ablesen.

Satz 1.3.5 Sei C ein linearer [n, k]-Code über 𝔽_{q} mit Generatormatrix G. Dann ist der zugehörige Encoder systematisch, dann und nur dann, wenn die ersten k Spalten von G die k × k Einheitsmatrix I_{k} bilden.

Beweis. Die Spalten von G sind Gleichungen, mit deren Hilfe man aus den Symbolen eines Elementes x das Codewort u für x gewinnt. Deshalb sind die ersten k Symbole von u die Symbole von x ⇔ wenn die ersten k Spalten von G (1, 0, …, 0)^{T} , (0, 1, 0, …, 0)^{T} , …, (0, …, 0, 1)^{T} lauten. □

Wir nennen eine Generatormatrix G daher systematisch, wenn der dazugehörige Encoder systematisch ist (also wenn die ersten k Spalten von G gleich I_{k} sind). Klarerweise kann ein Code mehrere verschiedene Generatormatrizen besitzen. Der folgende Satz gibt eine einfache, notwendige und hinreichende Bedingung um festzustellen, ob eine Matrix eine Generatormatrix eines Linearcodes ist.

Satz 1.3.6 Sei C ein [n, k]-Linearcode über 𝔽_{q} und sei G eine k × n-Matrix. Dann ist G eine Generatormatrix von C, dann und nur dann, wenn die Zeilen von G eine Basis von C bilden.

Beweis. ⇒: Nach Voraussetzung ist E eine bijektive Abbildung von 𝔽_{q}^{k} nach C. Die Zeilen von G sind die Bilder der Nachrichtenwörter (1, 0, …, 0), (0, 1, 0, …, 0), …, (0, …, 0, 1) und bilden daher eine Basis von C. ⇐: Bezeichnen wir die Zeilen von G mit g_{1}, … g_{k}. Multiplikation des Nachrichtenwortes (a_{1}, …, a_{k}) mit G gibt das Wort a_{1}g_{1}+⋯+a_{k}g_{k}. Nach Annahme ist das eine Linearkombination von Codewörtern. Da C ein Linearcode ist, handelt es sich dabei wieder um ein Codewort. G bildet 𝔽_{q}^{k} also auf einen Teilraum von C ab. Die Dimension dieses Teilraumes ist k, daher haben wir eine bijektive Zuordnung, also einen Encoder für C. □

Einer der Hauptgründe, Linearcodes zu verwenden, ist die Tatsache, dass man sehr einfach überprüfen kann, ob ein Empfangswort ein Codewort ist oder nicht.

Definition 1.3.7 Eine Kontrollmatrix für einen [n, k]-Linearcode C über 𝔽_{q} ist eine l × n-Matrix H, mit der Eigenschaft, dass für v ∈ 𝔽_{q}^{n} gilt:

Hv^{T} = 0 ⇔ v ∈ C

Die Zahl l ist zunächst beliebig. Wir werden sehen, dass der kleinstmögliche Wert n − k ist. Wir sagen eine Kontrollmatrix sei systematisch, wenn sie von der Gestalt (D, J) ist, wobei J die (n − k) × (n − k) Einheitsmatrix ist. Es gilt die folgende, sehr einfache Beziehung zwischen systematischer Generator- und Kontrollmatrix.

Satz 1.3.8 Es sei C ein [n, k]-Linearcode über 𝔽_{q}. Dann gilt: Falls C eine systematische Generatormatrix G besitzt, dann auch eine systematische Kontrollmatrix H und umgekehrt. Insbesondere wird eine durch die andere eindeutig bestimmt, denn in diesem Fall gilt: Sei G = (I, A) und H = (B, J), dann ist A = −B^{T}.

Beweis. Zunächst sollen systematische Generatormatrix G und systematische Kontrollmatrix H existieren. Dann haben sie die Form G = (I, A) und H = (B, J). Es gilt dann HG^{T} = 0, da die Zeilen von G Codewörter sind. Also erhalten wir BI + JA^{T} = 0. Also folgt B = −A^{T}. Deshalb wird G durch H bestimmt und umgekehrt, also sind beide eindeutig und sie haben die angegebene Form. Wenn nun G = (I, A) eine systematische Kontrollmatrix ist, dann zeigen wir, dass durch H = (−A^{T} , J) eine systematische Kontrollmatrix definiert wird. Sei v = uG für ein u. Wegen HG^{T} = 0 folgt aus v = uG, dass Hv^{T} = HG^{T} u^{T} = 0u^{T} = 0 ist. Daher ist H eine Kontrollmatrix und sie ist sytematisch. Umgekehrt sei H = (B, J) gegeben. Wir setzen G = (I, −B^{T}) und zeigen G ist eine Generatormatrix. Sei also Hv^{T} = 0. Wir zerlegen v in (u, w), wo u aus den ersten k Symbolen von v besteht. Dann gilt Hv^{T} = 0 ⇔ −A^{T} u^{T} + Jw^{T} = −A^{T} u^{T} + w^{T} = 0. Also gilt w = uA und damit v = (u, w) = (u, uA) = (I, A)u = uG. □

Die Frage, ob jeder Code eine systematische Generatormatrix besitzt, beantwortet der folgende Satz:

Satz 1.3.9 Sei C ein [n, k]-Linearcode über 𝔽_{q}. Dann können die Codewörter so permutiert werden, dass der permutierte Code C̃ eine systematische Generatormatrix besitzt.

Beweis. Sei G eine Generatormatrix von C. Durch elementare Zeilenoperationen ist es möglich die Matrix G in eine Matrix G′ überzuführen , sodass diese folgende Eigenschaften hat: Der erste Eintrag ≠ 0 der (i + 1)-ten Zeile erfolgt später als der von der i. Zeile. Der erste Eintrag ≠ 0 jeder Zeile ist 1. Alle anderen Einträge in der Spalte, die die 1 enthält sind 0. Die Zeilen von G′ sind Linearkombinationen der Zeilen von G und daher Codewörter. Dann permutieren wir die Spalten von G′, so dass die 1 in der i. Zeile in der i. Spalte steht. Die so erhaltene Matrix bezeichnen wir mit G′′. Diese Permutation entspricht einer Permutation der Symbole der Codewörter von C. Den permutierten Code nennen wir C̃. Nach Konstruktion beginnt G′′ mit der k × k Einheitsmatrix und ist eine Generatormatrix für C̃, da die Spalten eine Basis für C̃ bilden. □

Nun wollen wir die Behauptung über die Größe der Kontrollmatrix zeigen:

Satz 1.3.10 Sei C ein [n, k]-Linearcode über 𝔽_{q} und H eine Kontrollmatrix für C. Dann gilt:

(a) rank H = n − k.

(b) H hat mindestens n − k Zeilen.

(c) Sei K eine Matrix, die aus H durch Hinzufügen von weiteren Zeilen entsteht, die Linearkombinationen der Zeilen von H sind, dann ist K ebenfalls eine Kontrollmatrix für C.

Beweis.

(a) Da H eine Kontrollmatrix für C ist, folgt, dass C der Kern der linearen Abbildung H ist. Aus der Rangformel folgt rank H = n − k.

(b) Der Rang ist höchstens gleich der Anzahl der Zeilen einer Matrix.

(c) Trivial. □

Wir wollen noch eine andere Beschreibung der Kontrollmatrix eines Codes geben.

Definition 1.3.11 Das kanonische innere Produkt in 𝔽_{q}^{n} ist definiert durch

⟨a, b⟩ := ∑_{i=1}^{n} a_{i}b_{i},

für a = (a_{1}, …, a_{n}) und b = (b_{1}, …, b_{n}) ∈ 𝔽_{q}^{n}. Offensichtlich liefert das eine nicht ausgeartete symmetrische Bilinearform auf 𝔽_{q}^{n}.

Definition 1.3.12 Sei C ein [n, k]-Linearcode über 𝔽_{q}. Dann heißt

C^{⊥} := {u ∈ 𝔽_{q}^{n} | ⟨u, c⟩ = 0 für alle c ∈ C}

der zu C duale Code.

Aus der linearen Algebra wissen wir, dass der duale Code zu einem [n, k]- Linearcode über 𝔽_{q} ein [n, n − k]-Linearcode über 𝔽_{q} ist. Der duale Code lässt sich sehr einfach mit Hilfe der Kontrollmatrix von C beschreiben.

Satz 1.3.13 Sei H eine Kontrollmatrix eines linearen [n, k]-Codes C über 𝔽_{q} mit n − k Zeilen. Dann ist H eine Generatormatrix des zu C dualen Codes C^{⊥}.

Beweis. Sei U = {vH | v ∈ 𝔽_{q}^{n−k}}. Wir zeigen, dass U = C^{⊥} gilt.

1. Klarerweise ist U ein Teilraum von 𝔽_{q}^{n} mit dim U = n − k.

2. Sei G eine Generatormatrix von C. Jedes u ∈ U ist orthogonal zu jedem c ∈ C, denn für u = vH und c = aG gilt, wegen HG^{T} = 0,

⟨u, c⟩ = uc^{T} = (vH)(aG)^{T} = v(HG^{T})a^{T} = 0.

Also ist U ⊆ C^{⊥}. Da der Unterraum U ⊆ C^{⊥} und dim U = dim C^{⊥} = n − k ist, folgt die Behauptung. □

Zum Schluss zeigen wir, dass in der Kontrollmatrix die ganze Information über die Minimaldistanz des Codes steckt.

Satz 1.3.14 Sei C ein [n, k]-Linearcode über 𝔽_{q} mit Kontrollmatrix H. C hat Minimaldistanz > d, dann und nur dann, wenn es keine Menge mit d Spalten von H gibt, die linear abhängig sind.

Beweis. Wir bezeichnen die Spalten von H mit h_{1}, …, h_{n}. Angenommen es existiert ein Codewort c = (c_{1}, c_{2}, …, c_{n}) ≠ 0 mit Gewicht ≤ d. Wir müssen zeigen, dass H eine linear abhängige Menge von d Spalten besitzt. Da c ein Codewort ist, gilt

Hc^{T} = c_{1}h_{1} + c_{2}h_{2} + ⋯ + c_{n}h_{n} = 0.

Wir wählen eine Menge von genau d Spalten von H, wo alle jene Spalten h_{i} vorkommen, in denen c_{i} ≠ 0 ist. Diese Spalten seien o.B.d.A. h_{1}, …, h_{d}. Wegen c_{i} = 0 für i > d, gilt dann

c_{1}h_{1} + c_{2}h_{2} + ⋯ + c_{d}h_{d} = 0.

Da c ≠ 0 ist, muß mindestens einer der Koeffizienten c_{i} ≠ 0 sein. Die Menge {h_{1}, …, h_{d}} ist also linear abhängig. Umgekehrt gilt für eine linear abhängige Menge von d Spalten von H (wir nehmen wieder o.B.d.A. an, dass sie wie oben numeriert sind), dass Koeffizienten c_{i}, i = 1, … d nicht alle 0 existieren, sodass

c_{1}h_{1} + c_{2}h_{2} + ⋯ + c_{d}h_{d} = 0

gilt. Definieren wir c_{i} = 0 für i > d, dann haben wir ein Codewort c = (c_{1}, …, c_{n}) ungleich dem Nullwort gefunden, da gilt

Hc^{T} = c_{1}h_{1} + ⋯ + c_{n}h_{n} = 0.

Da wt(c) ≤ d gilt, muss die Minimaldistanz ≤ d sein. □

Wenn wir also einen Linearcode C mit Generatormatrix G und Kontrollmatrix H gegeben haben, können wir den Encoder und den Decoder von C sehr leicht mit Hilfe der Operationen von 𝔽_{q} beschreiben. Ein Nachrichtenwort wird in ein Codewort umgewandelt, indem wir die Generatormatrix darauf anwenden. Ob ein Empfangswort ein Codewort ist, können wir überprüfen, indem wir es mit H multiplizieren. Wenn das Ergebnis 0 ist, dann ist es ein Codewort, sonst nicht. Falls G systematisch ist, wird decodiert, indem die Prüfzeichen weggelassen werden.

Wie man die Struktur des Codes ausnützen kann, um entstandene Fehler zu korrigieren, soll hier nicht behandelt werden. Informationen darüber findet man zum Beispiel in [17].

1.4 Äquivalente Codes

Wir wollen später Konstruktionen für Codes angeben. Dabei treten Codes auf, die im wesentlichen gleichwertig sind. Um diese Gleichheit exakt zu formulieren definieren wir:

Definition 1.4.1 Gegeben seien zwei Linearcodes C_{1}, C_{2} ⊆ 𝔽_{q}^{n}. C_{1} und C_{2} heißen äquivalent, wenn ein Vektor a = (a_{1}, …, a_{n}) ∈ (𝔽_{q}\{0})^{n} existiert, sodass C_{2} = a · C_{1} ist, das heißt, dass

C_{2} = {(a_{1}c_{1}, …, a_{n}c_{n}) | (c_{1}, …, c_{n}) ∈ C_{1}}

gilt.

Äquivalente Codes haben viele qualitative Eigenschaften gemeinsam. Genauer gilt der folgende Satz:

Satz 1.4.2 C_{1} und C_{2} seien äquivalente Codes über 𝔽_{q} der Länge n. Dann haben C_{1} und C_{2} dieselbe Dimension und dieselbe Minimaldistanz.

Beweis. Da C_{1} und C_{2} äquivalent sind, gibt es ein a = (a_{1}, …, a_{n}) ∈ (𝔽_{q}\{0})^{n} mit C_{2} = a · C_{1}. Die Aussage über die Dimension folgt aus der Tatsache, dass die Abbildung

α : \{ \begin{matrix}𝔽_{q}^{n} & ⟶ & 𝔽_{q}^{n} \\ (v_{1}, …, v_{n}) & ⟼ & (a_{1}v_{1}, …, a_{n}v_{n}) \end{matrix}

ein Isomorphismus ist. Da nach Definition der Äquivalenz C_{2} = α(C_{1}) ist, gilt dim C_{2} = dim C_{1}. Die zweite Aussage folgt sofort aus

wt(a_{1}c_{1}, …, a_{n}c_{n}) = wt(c_{1}, …, c_{n})

und Satz 1.3.2. □

Man beachte aber, dass äquivalente Codes nicht in allen interessanten Eigenschaften eines Codes übereinstimmen müssen. Zum Beispiel können äquivalente Codes nicht-isomorphe Automorphismengruppen besitzen (für eine Definition der Automorphismengruppe eines Codes siehe [19]).

1.5 Die Gilbert-Varshamov-Schranke

Ziel der Codierungstheorie ist es ”gute“ Codes oder ”gute“ Klassen von Codes zu konstruieren. Die meisten Schranken für Codes sind obere Schranken, die angeben, dass die Parameter eines Codes sich innerhalb gewisser Schranken bewegen müssen. Die Gilbert-Varshamov-Schranke ist eine untere Schranke. Sie besagt, dass Codes mit Parametern, die größer als gewisse Werte sind, existieren. Wir werden Codes, deren Parameter diese Schranke erreichen, ”gut“ nennen. Die Gilbert-Varshamov-Schranke stellt also sicher, dass ”gute“ Codes existieren.

Die Herleitung der Gilbert-Varshamov-Schranke beruht (so wie die meisten anderen Schranken auch) darauf, die Anzahl der Wörter zu zählen, die zu einem festen Wort eine vorgegebene Entfernung haben.

Definition 1.5.1 Sei A ein Alphabet mit q Elementen. Der q-äre Ball B_{q}(u, r) um u ∈ A^{n} mit Radius r ∈ ℕ, besteht aus allen Wörtern v ∈ A^{n} mit d(u, v) ≤ r. Die Anzahl der Wörter in B_{q}(u, r) bezeichnen wir mit V (q, n, r).

Satz 1.5.2 Sei A ein Alphabet mit q Elementen und sei B_{q}(u, r) ein qärer Ball um u ∈ A^{n} mit Radius r ∈ ℕ. Dann gilt für die Anzahl der Wörter in B_{q}(u, r) die Formel

V (q, n, r) = \binom{n}{0} + \binom{n}{1}(q − 1) + ⋯ + \binom{n}{r}(q − 1)^{r} = ∑_{k=0}^{r} \binom{n}{k}(q − 1)^{k}.

Beweis. Der Ball B_{q}(u, r) ist die disjunkte Vereinigung der Mengen {v ∈ A^{n} | d(u, v) = k} für k = 0, …, r. Um ein Wort mit Distanz k zu finden, müssen wir zuerst k Plätze wählen an denen sich v von u unterscheiden soll. Dafür gibt es \binom{n}{k} Möglichkeiten. An jeder Stelle gibt es q − 1 mögliche Symbole, die verschieden von jenem von u an dieser Stelle sind. Insgesamt gibt es (q − 1)^{k} Möglichkeiten, wenn man die k Stellen gewählt hat. Daher gibt es \binom{n}{k}(q − 1)^{k} Wörter mit Distanz k von u. □

Als sehr einfache Anwendung dieses Satzes erhält man die folgenden oberen Schranken für die Anzahl der Codewörter bei gegebener Länge und Minimaldistanz.

Satz 1.5.3 (Hamming-Schranke) Sei C ein Code über dem q-elementigen Alphabet A mit Blocklänge n und Minimaldistanz d = 2r + 1. Dann hat C höchstens q^{n}/V (q, n, r) Codewörter.

Beweis. Die Bälle mit Radius r um verschiedene Codewörter müssen disjunkt sein. Daher gilt |C| · V (q, n, r) ≤ |A^{n}| = q^{n} und damit sofort die Behauptung. □

Satz 1.5.4 (Singleton-Schranke) Für einen linearen [n, k, d]-Code C über 𝔽_{q} gilt

k + d ≤ n + 1.

Beweis. Wenn wir die ersten d−1 Symbole in jedem Codewort von C entfernen, haben wir nach wie vor q^{k} verschiedene Wörter, da die Minimaldistanz d ist. Die Blocklänge reduziert sich dabei auf n−d+1. Also gilt k ≤ n−d+1 und damit die Behauptung. □

Definition 1.5.5 Einen Code, der die Hamming-Schranke erreicht, nennt man perfekt. Einen Code, der die Singleton-Schranke erreicht, heißt MDS-Code (maximum distance separable-Code).

Die Gilbert-Varshamov-Schranke erhält man, wenn man die Anzahl der Bälle zählt, die man benötigt um den ganzen A^{n} zu überdecken.

Satz 1.5.6 (Gilbert-Varshamov-Schranke) Es gibt einen Code C über dem q-elementigen Alphabet A mit Länge n und Minimaldistanz d mit |C| ≥ q^{n}/V (q, n, d − 1).

Beweis. Sei C ⊆ A^{n} ein Code mit Minimaldistanz d. Wir können annehmen das C maximal ist, in dem Sinn, dass kein Wort zu C hinzugefügt werden kann ohne die Minimaldistanz zu verkleinern, denn wenn C nicht maximal in diesem Sinne wäre, könnten wir ein Codewort hinzufügen (ohne die Minimaldistanz zu verkleinern), usw. Die Maximalität von C impliziert, dass jedes Wort in A^{n} eine Distanz ≤ d − 1 von einem Codewort hat. Die Bälle mit Radius d−1 um Codewörter überdecken also den A^{n}. Es gilt daher

q^{n} = |A|^{n} ≤ |C|V (q, n, d − 1).

Daraus folgt

|C| ≥ q^{n}/V (q, n, d − 1),

und damit die Behauptung. □

Die Gilbert-Varshamov-Schranke kann durch lineare Codes stets erreicht werden. Es gilt der folgende Satz:

Satz 1.5.7 Sei C ein Linearcode mit Blocklänge n über 𝔽_{q} und Minimaldistanz ≥ d. Falls |C| < q^{n}/V (q, n, d − 1), dann existiert ein Linearcode C′ ⊋ C in 𝔽_{q}^{n}, sodass die Minimaldistanz von C′ ebenfalls ≥ d ist.

Beweis. Aus dem Beweis von Satz 1.5.6 folgt, dass wir ein Wort v ∈ 𝔽_{q}^{n} wählen können, dessen Distanz zu jedem Codewort mindestens d ist. Wir definieren

C′ := {u − av | u ∈ C und a ∈ 𝔽_{q}}.

Offensichtlich ist C′ linear, denn für a, a′, b, b′ ∈ 𝔽_{q} und u, u′ ∈ C gilt

b(u − av) − b′(u′ − a′v) = (bu − b′u′) − (ba − b′a′)v,

wobei bu − b′u′ ∈ C ist, da C linear ist, und ba − b′a′ ∈ 𝔽_{q}. C′ enthält C (indem man a = 0 setzt). Um zu zeigen, dass C′ immer noch Minimaldistanz ≥ d hat verwenden wir Satz 1.3.2. Sei w = u − av ein Codewort ungleich dem Nullwort. Wenn a = 0 gilt, dann ist w ∈ C und damit ist in diesem Fall wt(w) ≥ d. Wenn a ≠ 0 ist, setzen wir b = a^{−1}. Dann gilt

wt(w) = wt(bw) = wt(bu − v) = d(bu, v).

Da C linear ist, ist bu ein Codewort von C und v war so gewählt, dass die Distanz zu jedem Codewort ≥ d ist. Es ist also d(bu, v) ≥ d. Satz 1.3.2 impliziert die Behauptung. □

Folgerung 1.5.8 Es gibt einen Linearcode C ⊆ 𝔽_{q}^{n} mit Minimaldistanz d, Rang ≥ n − log_{q}(V (q, n, d − 1)) und daher Rate ≥ 1 − log_{q}(V (q, n, d − 1))/n.

Beweis. Man wähle einen Code der die Gilbert-Varshamov-Schranke erreicht. So einer existiert nach Satz 1.5.7. Dieser hat mindestens q^{n}/V (q, n, d− 1) Codewörter. Deshalb ist der Rang k mindestens

log_{q}(q^{n}/V (q, n, d − 1)) = n − log_{q}(V (q, n, d − 1)).

Die Aussage über die Rate folgt jetzt sofort aus der Definition der Rate als Quotient k/n. □

Für kurze Blocklängen gibt es viele Codes, die die Gilbert-Varshamov-Schranke erreichen. Mit zunehmender Blocklänge wird es dann aber immer schwieriger die Gilbert-Varshamov-Schranke zu erreichen.

Um eine Schranke für Familien von Codes zu erhalten, müssen wir Codes mit verschiedenen Blocklängen vergleichen können. Der Rang wird dabei durch die Rate ersetzt und wir verwenden folgendes Maß für die Minimaldistanz, welches nicht mehr von der Länge abhängt.

Definition 1.5.9 Für einen Code der Länge n und Minimaldistanz d über 𝔽_{q} nennen wir d/n die relative Minimaldistanz.

Wir benötigen auch noch eine Schätzung für den zweiten Term in der Gilbert-Varshamov-Schranke, die nicht von n abhängt. Dazu eignet sich die folgende Funktion:

Definition 1.5.10 Sei q ∈ ℕ. Für 0 ≤ δ ≤ (q − 1)/q definieren wir die q-äre Entropie Funktion H_{q}(δ) durch H_{q}(0) = 0 und,

H_{q}(δ) = δ log_{q}(q − 1) − δ log_{q}(δ) − (1 − δ) log_{q}(1 − δ).

Satz 1.5.11 Sei q ∈ ℕ. Für alle 0 ≤ δ ≤ (q − 1)/q gilt H_{q}(δ) ≤ δq/(q − 1). Gleichheit gilt dann und nur dann, wenn δ = 0 oder δ = q − 1)/q.

Beweis. Für 0 < δ ≤ (q − 1)/q, gilt für die Ableitung von H_{q}(δ)

log_{q}(q − 1) − log_{q}(δ/(1 − δ)) ≥ 0.

Die zweite Ableitung ist

1/((δ − 1)δ ln(q)) < 0.

Die Kurve definiert durch y = H_{q}(δ) ist also konkav auf (0, (q − 1)/q]. Für δ = (q −1)/q ist H_{q}(δ) = 1. Deshalb muß die Gerade durch die Punkte (0, 0) und ((q − 1)/q, 1) überall echt oberhalb der Kurve sein. □

Mit Hilfe dieser Funktion können wir die Funktion V (q, n, d − 1) in der Gilbert-Varshamov-Schranke ersetzen.

Hilfssatz 1.5.12 Sei 0 ≤ δ ≤ (q − 1)/q und für n ∈ ℕ sei r = r(n) als die größte Zahl ∈ ℕ definiert, sodass r ≤ δn ist. Dann gilt

(a) log_{q}(V (q, n, r)) ≤ nH_{q}(δ) und

(b) n^{−1} log_{q}(V (q, n, r)) ⟶ H_{q}(δ) für n ⟶ ∞.

Beweis. (a) Man beachte, dass 0 ≤ 1/q = 1 − (q − 1)/q ≤ 1 − δ gilt. Daher ist für jedes reelle k ≥ 0,

δ^{k} ≤ (q − 1)^{k}/q^{k} ≤ (q − 1)^{k}(1 − δ)^{k}.

Für 0 ≤ i ≤ δn erhalten wir daher mit k = δn − i

δ^{δn−i} ≤ (q − 1)^{δn−i}(1 − δ)^{δn−i}.

Umformen und Multiplikation mit (1 − δ)^{n} ergibt

δ^{i}(1 − δ)^{n−i}/(q − 1)^{i} ≥ δ^{δn}(1 − δ)^{n−δn}/(q − 1)^{δn} = q^{−nH_{q}(δ)}.

Mit Hilfe des Binomischen Lehrsatzes erhalten wir

1 = 1^{n} = (δ + (1 − δ))^{n}
≥ ∑_{i=0}^{r} \binom{n}{i}(q − 1)^{i} (\frac{δ}{q − 1})^{i} (1 − δ)^{n−i}

≥ ∑_{i=0}^{r} \binom{n}{i}(q − 1)^{i} (\frac{δ}{q − 1})^{δn} (1 − δ)^{n−δn}
= V (q, n, r)q^{−nH_{q}(δ)}.

Wenn wir den Logarithmus zur Basis q anwenden, erhalten wir

0 ≥ log_{q}(V (q, n, r)) − n · H_{q}(δ),

was die erste Aussage beweist.

(b) Für den Beweis der zweiten Aussage benötigen wir die Stirling’sche Formel für ln(n!):

ln(n!) − 1/(12n) ≤ (n + 1/2) ln(n) − n + K ≤ ln(n!),

wobei K = ln(2π)/2 und damit eine Konstante ist. Wenn wir zum Logarithmus zur Basis q übergehen ändert sich die Konstante und wir erhalten

log_{q}(n!) − log_{q}(e)/(12n) ≤ (n + 1/2) log_{q}(n) − n log_{q}(e) + K′ ≤ log_{q}(n!).

Aus Satz 1.5.2 folgt

V (q, n, r) ≥ \binom{n}{r}(q − 1)^{r}.

Wir setzen nun \binom{n}{r} = n!/(r!(n−r)!), logarithmieren zur Basis q und verwenden die Stirling’sche Formel um die Faktoren abzuschätzen. Damit erhalten wir

log_{q}(V (q, n, r)) ≥ (n + 1/2) log_{q}(n) − (r + 1/2) log_{q}(r)
−(n − r + 1/2) log_{q}(n − r) + r log_{q}(q − 1)
−n log_{q}(e) + r log_{q}(e) + (n − r) log_{q}(e) − K′
− log_{q}(e)/(12r) − log_{q}(e)/(12(n − r)).

Wenn wir durch n dividieren und n gegen ∞ gehen lassen, können wir Terme die gegen 0 gehen vernachlässigen. Wir erhalten

lim_{n→∞}(n^{−1} log_{q}(V (q, n, r)))

≥ lim_{n→∞}(log_{q}(n) − (r/n) log_{q}(r)

−((n − r)/n) log_{q}(n − r) + (r/n) log_{q}(q − 1)).

Aus der Definition für r folgt, dass δn/r und (1 − δ)n/(n − r) beide für n → ∞ gegen 1 konvergieren. Also gilt

lim_{n→∞}(n^{−1} log_{q}(V (q, n, r)))

≥ lim_{n→∞}(log_{q}(n) − δ log_{q}(δn) − (1 − δ) log_{q}((1 − δ)n) + δ log_{q}(q − 1))

= lim_{n→∞}(log_{q}(n) − δ log_{q}(δ) − δ log_{q}(n)
−(1 − δ) log_{q}(1 − δ) − (1 − δ) log_{q}(n) + δ log_{q}(q − 1))
= lim_{n→∞}(−δ log_{q}(δ) − (1 − δ) log_{q}(1 − δ) + δ log_{q}(q − 1))
= H_{q}(δ).

Aus der ersten Aussage folgt nun die Behauptung. □

Satz 1.5.13 (Asymptotische Gilbert-Varshamov-Schranke) Für alle δ ≤ (q − 1)/q gibt es eine Folge von Linearcodes C_{n} ⊆ 𝔽_{q}^{n}, sodass die relative Minimaldistanz von C_{n} gegen δ und die Rate gegen 1−H_{q}(δ) konvergiert.

Beweis. Sei r die größte Zahl ∈ ℕ mit r ≤ δn. Aus Folgerung 1.5.8 erhalten wir, dass ein Linearcode C_{n} ⊆ 𝔽_{q}^{n} mit Minimaldistanz r + 1 und Rate k/n ≥ 1 − n^{−1} log_{q}(V (q, n, r)) existiert. Aus Hilfssatz 1.5.12 folgt, dass die Raten von C_{n} gegen 1 − H_{q}(δ) konvergieren. Es gilt δn < r + 1 ≤ δn + 1. Daraus folgt δ < (r + 1)/n ≤ δ + 1/n. Also konvergiert (r + 1)/n gegen δ, wenn n gegen ∞ geht. □

Mit Hilfe dieses Satzes definieren wir jetzt ”gute“ und ”schlechte“ Familien von Codes.

Definition 1.5.14 Sei W eine Familie von Linearcodes über 𝔽_{q}. Wir nennen W schlecht, wenn für jede unendliche Folge von Codes in W, entweder die Rate oder die relative Minimaldistanz gegen 0 konvergiert. Wir nennen W gut, wenn es eine unendliche Folge von Codes in W gibt, die gegen die asymptotische Gilbert-Varshamov-Schranke konvergieren, das heißt, es gibt ein δ ≤ (q − 1)/q, sodass die relativen Minimaldistanzen gegen δ und die Raten gegen 1 − H_{q}(δ) konvergieren.

Man beachte, dass es Familien von Codes gibt, die weder gut noch schlecht sind. Unter guten Familien von Codes verstehen wir also solche, in denen es lange Codes mit vernünftigen Raten bei nicht zu großer relativer Minimaldistanz gibt.

Satz 1.5.13 garantiert uns zwar, dass gute Familien von Codes existieren, leider ist der Beweis nicht konstruktiv. Er zeigt uns nicht, wie wir gute Familien von Codes konstruieren können. Die erste Frage, die sich stellt ist, ob die Codes die am bekanntesten sind und die in den Anwendungen am häufigsten verwendet werden, gut oder schlecht oder keines von beiden sind? Dieser Frage soll im nächsten Kapitel kurz nachgegangen werden.

1.6 BCH-Codes

Die folgende wichtige Klasse von Codes wurde von R. C. Bose und D. K. Ray-Chaudhuri und unabhängig zur selben Zeit von A. Hocquenghem entdeckt (siehe [2] und [9]). Sie sind bekannt unter dem Namen BCH-Codes.

Definition 1.6.1 Sei n|q^{m} − 1 und β ∈ 𝔽_{q^{m}} eine primitive n-te Einheitswurzel. Sei weiters l ∈ ℤ und δ ≥ 2. Wir definieren den Code C(n, l, δ) über 𝔽_{q^{m}} durch die Generatormatrix

H := ( \begin{matrix}1 & β^{l} & β^{2l} & ⋯ & β^{(n−1)l} \\ 1 & β^{l+1} & β^{2(l+1)} & ⋯ & β^{(n−1)(l+1)} \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ 1 & β^{l+δ−2} & β^{2(l+δ−2)} & ⋯ & β^{(n−1)(l+δ−2)} \end{matrix} ) .  (1.1)

Der Code C := C(n, l, δ)^{⊥} ∩ 𝔽_{q}^{n} wird ein BCH-Code mit konstruierter Minimaldistanz δ genannt. Mit anderen Worten,

C = {c ∈ 𝔽_{q}^{n} | H · c^{T} = 0},

wobei H die Generatormatrix von C(n, l, δ) ist.

Normalerweise definiert man BCH-Codes als spezielle zyklische Codes (siehe zum Beispiel [23]). Ihre Bedeutung liegt vor allem, in der für diese Codes einfachen und effizienten Fehlerkorrektur (siehe dazu [17]).

Für die Dimension k eines BCH-Codes C gilt offensichtlich:

k ≥ n − m(δ − 1).

Wir nennen n−m(δ−1) die konstruierte Dimension des BCH-Codes C. Der folgende Satz behauptet, dass eine untere Schranke für die Minimaldistanz durch δ gegeben ist.

Satz 1.6.2 Sei C ein BCH-Code mit konstruierter Minimaldistanz δ. Dann gilt: d ≥ δ.

Beweis. Der Beweis soll hier nicht geführt werden, da er aus einem allgemeineren Satz (siehe Folgerung 3.3.6) im Kapitel 4 folgt. Einen elementaren Beweis findet man z.B. in [23]. □

Es gilt der folgende Satz:

Satz 1.6.3 Sei C_{k} eine Folge von BCH-Codes über 𝔽_{2} der Länge n = 2^{k} − 1 mit konstruierter Minimaldistanz δ = 2t + 1 > ϵ · n, wobei ϵ > 0 ist. Dann folgt, dass die konstruierte Rate (=konstruierte Dimension/n) bei genügend großem n unter 0 fällt.

Beweis. Die konstruierte relative Minimaldistanz ist (2t + 1)/n. Wenn diese > ϵ sein soll, muß t > (ϵn − 1)/2 gelten. Da k = log_{2}(n + 1) ist, folgt, dass die konstruierte Dimension n−2kt < n−(ϵn−1) log_{2}(n+1) sein muß. Wenn n genügend groß ist, gilt log_{2}(n + 1) > 2/ϵ und damit

n − (ϵn − 1) log_{2}(n + 1) = n − ϵn log_{2}(n + 1) + log_{2}(n + 1)
< n − 2n + log_{2}(n + 1)
= log_{2}(n + 1) − n < 0.

Damit fällt auch die konstruierte Rate unter 0. Es gilt also: Wenn die konstruierte Rate über 0 bleibt, kann die relative Minimaldistanz nicht größer als ϵ sein für großes n. □

Dieser Satz besagt zwar nur, dass diese spezielle Klasse von BCH-Codes entweder schlecht ist oder die Abschätzungen für Rang und Minimaldistanz schlecht sind. Man kann aber zeigen, dass die BCH-Codes insgesamt eine schlechte Familie von Codes bilden.

Satz 1.6.4 Die BCH-Codes bilden eine schlechte Familie von Codes.

Beweis. Einen Beweis findet man in [11] und soll hier entfallen. □

Die Frage, nach guten Familien von Codes bleibt zunächst noch offen. Der russische Mathematiker V. D. Goppa entdeckte 1970 eine Klasse von Codes (siehe [6]), welche die BCH-Codes als Spezialfall beinhalten. Von dieser Klasse konnte er zeigen, dass es sich um eine gute Klasse von Codes handelt. Allerdings konnte er keine explizite Konstruktion angeben. Im Jahr 1980 hat Goppa seine Definition nochmals erweitert (siehe [7]), indem er Kurven über endlichen Körpern betrachtete. In dieser Klasse von ”geometrischen“ Codes, gibt es explizite Codes, die die Gilbert-Varshamov-Schranke sogar übertreffen.

Diese Codes werden im folgenden betrachtet. Das nächste Kapitel wird die dafür notwendige Sprache bereitstellen.

Algebraische Funktionenkörper

In diesem Kapitel sollen die grundlegenden Definitionen und Resultate der Theorie der algebraischen Funktionenkörper entwickelt werden. Wir setzen stets voraus:

Es sei K ein beliebiger Körper.

Ein algebraischer Funktionenkörper über K ist eine endliche und somit algebraische Erweiterung des rationalen Funktionenkörpers K(x). Solche Typen von Körpererweiterungen treten in vielen verschiedenen Bereichen der Mathematik auf, wie zum Beispiel in der algebraischen Geometrie, in der Zahlentheorie und in der Theorie der kompakten Riemann’schen Flächen.

Wir wollen hier einen rein algebraischen Zugang zur Theorie der algebraischen Funktionenkörper geben. Diese Formulierung stammt ursprünglich hauptsächlich von Chevalley (1951, siehe [3]), wurde aufgenommen und weiterentwickelt von Roquette (1958) und seinen Schülern Deuring und Stichtenoth (siehe [4] und [19]). Der Vorteil dieses Zuganges ist, dass er sehr elementar ist, und dass man die wichtigen Sätze relativ schnell für beliebigen Körper K zeigen kann.

2.1 Funktionenkörper und Stellen

Definition 2.1.1 Ein Erweiterungkörper F ⊇ K (wir schreiben auch F/K dafür) heißt ein algebraischer Funktionenkörper in einer Variable über K (oder kurz Funktionenkörper), falls es eine Element x ∈ F gibt, welches transzendent über K ist, sodass F eine endliche und somit algebraische Erweiterung von K(x) ist.

Im Spezialfall, dass F = K(x) ist, für ein x ∈ F, welches transzendent über K ist, nennen wir F/K den rationalen Funktionenkörper.

Die Menge K̄ := {z ∈ F | z ist algebraisch über K} ist ein Unterkörper von F, da Summen, Produkte und Inverse algebraischer Elemente algebraisch sind. K̄ wird Konstantentkörper von F/K genannt. Es gilt K ⊆ K̄ ⊂ F und klarerweise ist F/K̄ ein Funktionenkörper über K̄. Wir nennen K algebraisch abgeschlossen in F (oder sagen K ist der volle Konstantenkörper von F), falls K̄ = K ist. Außerdem nennen wir κ = [K̄ : K] den Konstantengrad von F/K.

Der erste Satz zeigt uns, dass das Element x in der Definition des Funktionenkörpers keine besondere Rolle spielt. Wir können die transzendenten Elemente von F über K nämlich folgendermaßen charakterisieren:

Satz 2.1.2 Sei F/K ein Funktionenkörper mit Konstantenkörper K̄. Dann gilt:

[F : K(y)] < ∞ ⟺ y ∈ F \K̄.

Beweis. ⇐: Da [F : K(x)] < ∞ ist, sind die Potenzen von y nicht linear unabhängig über K(x). Also ist y Nullstelle eines Polynomes f(T) ∈ K(x)[T]. Wenn wir mit dem gemeinsamen Nenner multiplizieren, können wir annehmen, dass die Koeffizienten von f Polynome in x sind. Wir können f also auffassen als f(S, T) ∈ K[S, T], sodass f(x, y) = 0 gilt. Angenommen S kommt in f(S, T) nicht vor, dann wäre y algebraisch über K und würde daher in K̄ liegen. Widerspruch! Daher ist x algebraisch über K(y) und daher gilt [K(x, y) : K(y)] ≤ deg_{K(y)} f(S, y) < ∞. Andererseits ist [F : K(x, y)] ≤ [F : K(x)]. Insgesamt erhalten wir [F : K(y)] = [F : K(x, y)] · [K(x, y) : K(y)] < ∞. ⇒: Nehmen wir indirekt an, dass [F : K(y)] < ∞ mit y ∈ K̄ gilt. Klarerweise ist [K(y) : K] < ∞. Damit erhalten wir [F : K] = [F : K(y)] · [K(y) : K] < ∞. Also ist F eine endliche und damit algebraische Erweiterung von K. Widerspruch zu F/K ein Funktionenkörper! □

Als nächstes wollen wir Bewertungsringe und Stellen definieren.

Definition 2.1.3 Ein Bewertungsring eines Funktionenkörpers F/K ist ein Unterring O ⊆ F mit den folgenden Eigenschaften:

(1) K ⊊ O ⊊ F, und

(2) für jedes z ∈ F gilt: z ∈ O oder z^{−1} ∈ O.

Der folgende Satz liefert erste wichtige Einblicke in die Struktur von Bewertungsringen.

Satz 2.1.4 Sei O ein Bewertungsring eines Funktionenkörpers F/K. Dann gilt:

(a) O ist ein lokaler Ring, das heißt O besitzt ein eindeutiges maximales Ideal P = O\O^{∗}, wobei O^{∗} = {z ∈ O | ∃w ∈ O mit zw = 1} die Gruppe der Einheiten von O bezeichnet.

(b) Für 0 ≠ x ∈ F gilt: x ∈ P ⟺ x^{−1} ∉ O.

(c) Für den Konstantenkörper K̄ von F/K gilt K̄ ⊆ O und K̄ ∩ P = {0}.

Beweis. (a) Wir brauchen nur zu zeigen, dass P := O\O^{∗} ein Ideal ist. Daraus folgt nämlich sofort, dass es das eindeutige maximale Ideal sein muss, da ein echtes Ideal von O keine Einheit enthalten kann.

(1) Sei also x ∈ P, z ∈ O. Dann ist xz ∉ O^{∗} (sonst wäre x eine Einheit), also gilt xz ∈ P.

(2) Seien x, y ∈ P. O.B.d.A. können wir annehmen, dass x/y ∈ O gilt. Dann ist 1 + x/y ∈ O und damit x + y = y(1 + x/y) ∈ P wegen (1). Also ist P ein Ideal von O.

(b) Offensichtlich.

(c) Sei z ∈ K̄. Angenommen z ∉ O. Dann ist z^{−1} ∈ O, da O ein Bewertungsring ist. Da z^{−1} algebraisch über K ist, existieren Elemente a_{1}, …, a_{r} ∈ K mit a_{r}(z^{−1})^{r} +⋯+a_{1}z^{−1} +1 = 0, also gilt z^{−1}(a_{r}(z^{−1})^{r−1} +⋯+a_{1}) = −1. Daraus folgt z = −(a_{r}(z^{−1})^{r−1} + ⋯ + a_{1}) ∈ K[z^{−1}] ⊆ O, und damit z ∈ O. Dass K̄ ∩ P = {0} gilt, folgt aus dem eben bewiesenen, denn es gilt 0 ≠ z ∈ K̄ ∩ P ⇒ z^{−1} ∉ O ⇒ z^{−1} ∉ K̄. Dies widerspricht der Tatsache, dass K̄ ein Körper ist. □

Zur Untersuchung der Eigenschaften des eindeutigen maximalen Ideals P benötigen wir den folgenden Hilfssatz:

Hilfssatz 2.1.5 Sei O ein Bewertungsring eines Funktionenkörpers F/K, P das maximale Ideal und 0 ≠ x ∈ P. Seien x_{1}, …, x_{n} ∈ P, sodass x_{1} = x und x_{i} ∈ x_{i+1}P für i = 1, …, n − 1. Dann gilt: n ≤ [F : K(x)] < ∞.

Beweis. Aus den Sätzen 2.1.2 und 2.1.4 folgt, dass [F : K(x)] < ∞ ist. Es genügt also zu zeigen, dass x_{1}, …, x_{n} linear unabhängig über K(x) sind. Zunächst gilt, aufgrund der Definition, dass alle x_{i} ≠ 0 sind. Angenommen es gibt eine nicht triviale Linearkombination ∑_{i=1}^{n} φ_{i}x_{i} = 0 mit φ_{i} ∈ K(x). Wir können annehmen, dass alle φ_{i} Polynome in x sind, und dass x nicht alle von ihnen teilt. Wir setzen a_{i} := φ_{i}(0) und definieren j ∈ {1, …, n} durch die Bedingung a_{j} ≠ 0, aber a_{i} = 0 für alle i > j. Wir erhalten

−φ_{j}x_{j} = ∑_{i≠j} φ_{i}x_{i}  (2.1)

mit φ_{i} ∈ O für i = 1, …, n (da x = x_{1} ∈ P), x_{i} ∈ x_{j}P für i < j und φ_{i} = xg_{i} für i > j, wobei g_{i} Polynome in x sind. Wenn wir (2.1) durch x_{j} dividieren, erhalten wir

−φ_{j} = ∑_{i<j} φ_{i} · \frac{x_{i}}{x_{j}} + ∑_{i>j} \frac{x}{x_{j}} · g_{i}x_{i}.

Alle Summanden auf der rechten Seite gehören zu P, daher folgt φ_{j} ∈ P. Andererseits gilt φ_{j} = a_{j} + xg_{j} mit g_{j} ∈ K[x] ⊆ O und x ∈ P, sodass a_{j} = φ_{j} − xg_{j} ∈ P ∩ K gilt. Da a_{j} ≠ 0 gilt, ist das ein Widerspruch zu Satz 2.1.4 (c). □

Satz 2.1.6 Sei O ein Bewertungsring eines Funktionenkörpers F/K und P das eindeutige maximale Ideal. Dann gilt:

(a) P ist ein Hauptideal.

(b) Falls P = tO, dann hat jedes 0 ≠ z ∈ F eine eindeutige Darstellung der Form z = t^{n}u, für ein n ∈ ℤ, u ∈ O^{∗}.

(c) O ist ein Hauptidealring. Genauer, wenn P = tO und {0} ≠ I ⊆ O ein Ideal ist, dann ist I = t^{n}O für ein n ∈ ℕ.

Beweis. (a) Nehmen wir indirekt an, dass P kein Hauptideal wäre und wählen wir ein Element 0 ≠ x_{1} ∈ P. Da P ≠ x_{1}O ist, gibt es ein x_{2} ∈ P \x_{1}O. Da x_{2}x_{1}^{−1} ∉ O ist, folgt aus Satz 2.1.4 (b) x_{2}^{−1}x_{1} ∈ P, und daher gilt x_{1} ∈ x_{2}P. Durch Induktion erhält man eine Folge x_{1}, x_{2}, x_{3}, … aus P, sodass x_{i} ∈ x_{i+1}P für jedes i ≥ 1 gilt, was ein Widerspruch zu Hilfssatz 2.1.5 ist.

(b) Die Eindeutigkeit der Darstellung z = t^{n}u mit u ∈ O^{∗} und n ∈ ℤ ist trivial, sodass wir nur die Existenz einer solchen zeigen müssen. Da z oder z^{−1} in O liegt, können wir annehmen, dass z ∈ O gilt. Falls z ∈ O^{∗}, dann ist z = t^{0}z. Es bleibt also der Fall z ∈ P. In diesem Fall gibt es ein maximales m ≥ 1 mit z ∈ t^{m}O, da die Länge der Sequenz

x_{1} = z, x_{2} = t^{m−1}, x_{3} = t^{m−2}, …, x_{m} = t

wegen Hilfssatz 2.1.5 beschränkt sein muß. Wir erhalten also z = t^{m}u mit u ∈ O. Angenommen u wäre keine Einheit von O, dann würde u ∈ P = tO gelten, also u = tw mit w ∈ O und daher z = t^{m+1}w ∈ t^{m+1}O, was ein Widerspruch zur Maximalität von m ist. Daher ist u ∈ O^{∗}.

(c) Sei {0} ≠ I ⊆ O ein Ideal. Die Menge A := {r ∈ ℕ | t^{r} ∈ I} ist nicht leer, da für 0 ≠ x ∈ I gilt: x = t^{r}u mit u ∈ O^{∗} und daher t^{r} = xu^{−1} ∈ I. Wir setzen n := min(A) und behaupten, dass I = t^{n}O gilt. Die Inklusion I ⊇ t^{n}O ist trivial, da t^{n} ∈ I ist. Umgekehrt sei y ∈ I und sei y ≠ 0. Dann ist y = t^{s}w mit w ∈ O^{∗} und s ≥ 0, woraus t^{s} ∈ I und damit s ≥ n folgt. Daher gilt y = t^{n} · t^{s−n}w ∈ t^{n}O. □

Einen Ring mit den Eigenschaften des letzten Satzes nennt man auch einen diskreten Bewertungsring.

Definition 2.1.7

(a) Eine Stelle P eines Funktionenkörpers F/K ist das maximale Ideal eines Bewertungsringes O von F/K. Jedes Element t ∈ P, sodass P = tO gilt, wird ein Primelement von P (oder lokaler Parameter oder Uniformisierungsvariable) genannt.

(b) ℙ_{F} := {P | P ist eine Stelle von F/K}.

Wenn O ein Bewertungsring von F/K und P sein maximales Ideal ist, dann wird O durch P eindeutig bestimmt, es gilt nämlich nach Satz 2.1.4 (b), dass O = {z ∈ F \{0} | z^{−1} ∉ P }∪{0} ist. Deshalb nennen wir O_{P} := O den Bewertungsring der Stelle P.

Sei jetzt P eine Stelle von F/K und O_{P} sein Bewertungsring. Da P ein maximales Ideal ist, ist der Restklassenring O_{P} /P ein Körper. Für x ∈ O_{P} definieren wir x(P) ∈ O_{P} /P als die Restklasse von x modulo P, für x ∈ F \O_{P} setzen wir x(P) := ∞. Aus Satz 2.1.4 wissen wir, dass K ⊆ O_{P} und K∩P = {0}, deshalb induziert die Restklassenabbildung O_{P} ⟶ O_{P} /P eine kanonische Einbettung von K in O_{P} /P. Über diese Einbettung wollen wir im folgenden K stets als einen Unterkörper von O_{P} /P auffassen. Man beachte, dass diese Beobachtung auch auf K̄ anstatt K angewandt werden kann. Wir fassen also auch K̄ als Unterkörper von O_{P} /P auf.

Definition 2.1.8 Sei P ∈ ℙ_{F}.

(a) F_{P} := O_{P} /P ist der Restklassenkörper von P. Die Abbildung

\begin{matrix}F & ⟶ & F_{P} ∪ \{∞\} \\ x & ⟼ & x(P) \end{matrix}

nennt man die Restklassenabbildung in Bezug auf P. Manchmal verwenden wir die Notation x + P := x(P) für x ∈ O_{P}.

(b) deg P := [F_{P} : K] nennen wir den Grad von P.

Der Grad einer Stelle ist stets endlich. Genauer gilt der folgende Satz:

Satz 2.1.9 Sei P eine Stelle von F/K und 0 ≠ x ∈ P, dann gilt:

deg P ≤ [F : K(x)] < ∞

Beweis. Zunächst bemerken wir, dass aus Satz 2.1.2 folgt, dass [F : K(x)] < ∞ ist. Seien z_{1}, …, z_{n} ∈ O_{P}, sodaß die Restklassen z_{1}(P), …, z_{n}(P) ∈ F_{P} linear unabhängig über K sind. Es genügt zu zeigen, dass die Elemente linear unabhängig über K(x) sein müssen. Angenommen es gibt eine nicht triviale Linearkombination

∑_{i=1}^{n} φ_{i}z_{i} = 0  (2.2)

mit φ_{i} ∈ K(x). O.B.d.A. können wir annehmen, dass die φ_{i} Polynome in x sind und dass nicht alle davon von x geteilt werden, das heißt φ_{i} = a_{i} + xg_{i} mit a_{i} ∈ K, g_{i} ∈ K[x], nicht alle a_{i} = 0. Wegen x ∈ P und g_{i} ∈ O_{P} gilt φ_{i}(P) = a_{i}(P) = a_{i}. Wenn wir die Restklassenabbildung auf (2.2) anwenden erhalten wir

0 = 0(P) = ∑_{i=1}^{n} φ_{i}(P)z_{i}(P) = ∑_{i=1}^{n} a_{i}z_{i}(P).

Das ist ein Widerspruch zur linearen Unabhängigkeit von z_{1}(P), …, z_{n}(P) über K. □

Definition 2.1.10 Eine Stelle P eines Funktionenkörpers F/K heißt rational, wenn deg P = 1 ist, das heißt wenn F_{P} = K ist.

Aus dieser Definition erhalten wir die nachstehende Folgerung. Sie ist ein einfaches Kriterium für den Grundkörper K eines Funktionenkörpers, um zu entscheiden, ob er der volle Konstantenkörper K̄ ist.

Folgerung 2.1.11 Wenn der Funktionenkörper F/K eine rationale Stelle besitzt, dann ist K̄ = K und daher ist der Konstantengrad κ = 1.

Beweis. Sei P ∈ ℙ_{F} die rationale Stelle. Aus Satz 2.1.4 (c) folgt dann, K̄ ⊆ O_{P} \P. Daher folgt K̄ ⊆ O_{P} /P = K, und damit K̄ = K. □

Als nächstes wollen wir die Existenz von Stellen in einem Funktionenkörper beweisen. Wir werden sogar sehen, dass ein Funktionenkörper sehr viele Stellen besitzt.

Satz 2.1.12 Sei F/K ein Funktionenkörper und R ein Unterring von F mit K ⊆ R ⊆ F. Angenommen {0} ≠ I ⊊ R ist ein echtes Ideal von R. Dann gibt es eine Stelle P ∈ ℙ_{F}, sodass I ⊆ P und R ⊆ O_{P} ist.

Beweis. Wir betrachten die Menge

F := {S | S ist ein Untering von F mit R ⊆ S und IS ≠ S },

wobei IS das Idealprodukt (die Menge aller endlichen Summen von Produkten as mit a ∈ I und s ∈ S) bezeichnet. F ist nicht leer, da R ∈ F ist, und F ist mit der Inklusion induktiv geordnet. Sei nämlich H ⊆ F eine total geordnete Teilmenge von F, dann ist T := ⋃{S | S ∈ H} ein Unterring von F mit R ⊆ T. Wir müssen zeigen, dass IT ≠ T ist. Angenommen das wäre falsch, dann ist 1 = ∑_{ν=1}^{n} a_{ν}s_{ν} mit a_{ν} ∈ I, s_{ν} ∈ T. Da H total geordnet ist, gibt es ein S_{0} ∈ H, sodass s_{1}, …, s_{n} ∈ S_{0} ist. Also gilt 1 = ∑_{ν=1}^{n} a_{ν}s_{ν} ∈ IS_{0}, womit ein Widerspruch erzielt wurde. Mit Hilfe des Zornschen Lemmas folgt, dass F ein maximales Element besitzt, also gibt es einen Ring O ⊆ F, sodass R ⊆ O ⊆ F, IO ≠ O und O ist maximal mit diesen Eigenschaften. Wir wollen zeigen, dass O einen Bewertungsring von F/K bildet. Aus I ≠ {0} und IO ≠ O folgt O ⊊ F und I ⊆ O\O^{∗}. Außerdem ist O ⊋ K, denn angenommen O sei gleich K, dann wäre K = R und damit würde kein echtes Ideal I existieren. Widerspruch! Angenommen es gibt ein Element z ∈ F mit z ∉ O und z^{−1} ∉ O. Dann gilt – wegen der Maximalität von O – IO[z] = O[z] und IO[z^{−1}] = O[z^{−1}] und wir können a_{0}, …, a_{n}, b_{0}, …, b_{m} ∈ IO finden mit

1 = a_{0} + a_{1}z + ⋯ + a_{n}z^{n} und  (2.3)
1 = b_{0} + b_{1}z^{−1} + ⋯ + b_{m}z^{−m}.  (2.4)

Klarerweise ist n ≥ 1 und m ≥ 1. Wir können annehmen, dass m,n in (2.3) und (2.4) minimal gewählt sind und m ≤ n gilt. Wenn wir (2.3) mit 1 − b_{0} und (2.4) mit a_{n}z^{n} multiplizieren, erhalten wir

1 − b_{0} = (1 − b_{0})a_{0} + (1 − b_{0})a_{1}z + ⋯ + (1 − b_{0})a_{n}z^{n} und
0 = (b_{0} − 1)a_{n}z^{n} + b_{1}a_{n}z^{n−1} + ⋯ + b_{m}a_{n}z^{n−m}.

Wenn wir diese Gleichungen addieren, erhalten wir 1 = c_{0} + c_{1}z + ⋯ + c_{n−1}z^{n−1} mit Koeffizienten c_{i} ∈ IO. Das ist ein Widerspruch zur Minimalität von n in (2.3). Wir haben also gezeigt, dass z ∈ O oder z^{−1} ∈ O für jedes z ∈ F gilt, also dass O ein Bewertungsring von F/K ist. □

Folgerung 2.1.13 Sei F/K ein Funktionenkörper, z ∈ F transzendent über K. Dann gilt:

(a) z ∈ O_{P} für eine Stelle P.

(b) Es gibt unendlich viele Stellen in F. Insbesondere gilt also ℙ_{F} ≠ ∅.

Beweis. (a) Wende Satz 2.1.12 auf R = K[z] und I = zK[z] an.

(b) Wir zeigen zunächst: Seien R und I wie in Satz 2.1.12. Ist I ein Primideal, dann kann ein P mit P ∩ R = I gefunden werden. Wir erweitern R und definieren B als den Ring {a/b | a ∈ R, b ∈ R\I}. Dann ist IB = {a/b | a ∈ I, b ∈ R\I} ein Ideal von B. Da genau die Elemente, die nicht in IB liegen, ein inverses Element besitzen, ist IB das eindeutige maximale Ideal von B. Nach Konstruktion folgt I ⊆ IB ∩ R und (R\I) ∩ IB = ∅. Also IB ∩ R = I. Wenn wir Satz 2.1.12 auf B anwenden, finden wir eine Stelle P mit IB ⊆ P. P ∩ B ist ein echtes Ideal von B, da es die 1 nicht enthält, also gilt P ∩ B ⊆ IB. Daraus folgt P ∩ B = IB und damit P ∩ R = IB ∩ R = I. Die Behauptung ergibt sich jetzt folgendermaßen: In K[z] gibt es unendlich viele verschiedene nicht assoziierte Primelemente p und jedes dieser Polynome erzeugt ein anderes Primideal ⟨p⟩. Zu jedem dieser Ideale gibt es eine andere Stelle P, sodass P ∩ K[z] = ⟨p⟩ ist. □

Folgerung 2.1.14 Der Konstantenkörper K̄ von F/K ist eine endliche Erweiterung von K.

Beweis. Wir wählen eine Stelle P ∈ ℙ_{F}. Da K̄ in F_{P} eingebettet ist, folgt dass [K̄ : K] ≤ [F_{P} : K] = deg P < ∞ ist. □

Wenn P eine rationale Stelle des Funktionenkörper F/K ist, dann gilt F_{P} = K, und die Restklassenabbildung bildet F auf K ∪ {∞} ab. Wenn wir voraussetzen K sei algebraisch abgeschlossen, dann ist jede Stelle rational. Deshalb können wir in diesem Fall ein Element z ∈ F als Funktion

z : \{ \begin{matrix}ℙ_{F} & ⟶ & K ∪ \{∞\}, \\ P & ⟼ & z(P) \end{matrix}  (2.5)

auffassen. Aus diesem Grund heißt F/K ein Funktionenkörper. Interpretiert man die Elemente von K als Funktionen, so sind sie konstante Funktionen. Aus diesem Grund nennt man K den Konstantenkörper von F.

2.2 Bewertungen

Wir wollen noch eine andere nützliche Beschreibung von Stellen geben. Dazu definieren wir:

Definition 2.2.1 Eine diskrete Bewertung von F/K ist eine Funktion ν : F ⟶ ℤ ∪ {∞} mit den folgenden Eigenschaften:

(1) ν(x) = ∞ ⟺ x = 0.

(2) ν(xy) = ν(x) + ν(y) für alle x, y ∈ F.

(3) ν(x + y) ≥ min{ν(x), ν(y)} für alle x, y ∈ F.

(4) Es gibt ein Element z ∈ F mit ν(z) = 1.

(5) ν(a) = 0 für alle a ∈ K\{0}.

Das Symbol ∞ bezeichnet hier ein Element ∉ ℤ, sodass ∞+∞ = ∞+n = n + ∞ = ∞ und ∞ > m für alle m, n ∈ ℤ. Aus (2) und (4) folgt sofort, dass ν : F ⟶ ℤ ∪ {∞} surjektiv ist. Eigenschaft (3) wird Dreiecksungleichung genannt. Eine stärkere Version dieser Ungleichung liefert der folgende Hilfssatz:

Hilfssatz 2.2.2 (Strikte Dreiecksungleichung) Sei ν eine diskrete Bewertung von F/K und x, y ∈ F mit ν(x) ≠ ν(y). Dann gilt: ν(x + y) = min{ν(x), ν(y)}.

Beweis. Aus (2) und (5) folgt, dass ν(ay) = ν(y) für 0 ≠ a ∈ K. Speziell erhalten wir ν(−y) = ν(y). Nach Voraussetzung ist ν(x) ≠ ν(y), also können wir o.B.d.A. ν(x) < ν(y) annehmen. Falls ν(x + y) ≠ min{ν(x), ν(y)} ist, dann folgt ν(x + y) > ν(x) aus (3) und wir erhalten ν(x) = ν((x + y) − y) ≥ min{ν(x + y), ν(y)} > ν(x), Widerspruch! □

Definition 2.2.3 Wir ordnen jeder Stelle P ∈ ℙ_{F} eine Funktion ν_{P} : F ⟶ ℤ ∪ {∞} auf folgende Art und Weise zu: Sei t ein Primelement für P. Dann hat jedes 0 ≠ z ∈ F eine eindeutige Darstellung z = t^{n}u mit u ∈ O_{P}^{∗} und n ∈ ℤ. Wir definieren ν_{P} (z) := n und ν_{P} (0) := ∞.

Diese Funktion ν_{P} wird sich als diskrete Bewertung von F/K herausstellen. Man beachte, dass diese Definition nur von P, nicht aber von der Wahl von t abhängt. Sei nämlich t′ ein anderes Primelement für P, dann gilt P = tO = t′O, sodass t = t′w ist für ein w ∈ O_{P}^{∗}. Daraus folgt t^{n}u = (t^{′n}w^{n})u = t^{′n}(w^{n}u) mit w^{n}u ∈ O_{P}^{∗}.

Der folgende Satz liefert die Beziehung zwischen P, O_{P} und ν_{P}:

Satz 2.2.4 Sei F/K ein Funktionenkörper.

(a) Für jede Stelle P ∈ ℙ_{F} ist die Funktion ν_{P} eine diskrete Bewertung von F/K. Es gilt:

O_{P} = {z ∈ F | ν_{P} (z) ≥ 0},
O_{P}^{∗} = {z ∈ F | ν_{P} (z) = 0},
P = {z ∈ F | ν_{P} (z) > 0}.

Ein Element x ∈ F ist ein Primelement von P, dann und nur dann, wenn ν_{P} (x) = 1.

(b) Umgekehrt gilt: Sei ν eine diskrete Bewertung von F/K. Dann ist die Menge P := {z ∈ F | ν(z) > 0} eine Stelle von F/K, und O_{P} = {z ∈ F | ν(z) ≥ 0} ist der dazugehörige Bewertungsring.

(c) Jeder Bewertungsring O von F/K bildet einen maximalen echten Unterring von F.

Beweis. (a) Offensichtlich hat ν_{P} die Eigenschaften (1), (2), (4) und (5) in Definition 2.2.1. Um die Dreiecksungleichung (3) zu zeigen, nehmen wir Elemente x, y ∈ F mit ν_{P} (x) = n, ν_{P} (y) = m. Wir können annehmen, dass n ≤ m < ∞ ist. Wir haben x = t^{n}u_{1} und y = t^{m}u_{2} mit u_{1}, u_{2} ∈ O_{P}^{∗}. Dann gilt x + y = t^{n}(u_{1} + t^{m−n}u_{2}) = t^{n}z mit z ∈ O_{P}. Wenn z = 0 ist, dann gilt ν_{P} (x + y) = ∞ > min{n, m}, sonst ist z = t^{k}u mit k ≥ 0 und u ∈ O_{P}^{∗}. Daher ist

ν_{P} (x + y) = ν_{P} (t^{n+k}u) = n + k ≥ n = min{ν_{P} (x), ν_{P} (y)}.

Wir haben also gezeigt, dass ν_{P} eine diskrete Bewertung von F/K ist. Die restlichen Aussagen von (a) sind trivial, genauso wie (b).

(c) Sei O ein Bewertungsring von F/K, P sein maximales Ideal, ν_{P} die diskrete Bewertung zu P und z ∈ F \O. Wir müssen zeigen, dass F = O[z] ist. Sei dazu y ∈ F beliebig. Dann ist ν_{P} (yz^{−k}) ≥ 0 für hinreichend großes k ≥ 0 (beachte ν_{P} (z^{−1}) > 0, da z ∉ O). Daraus folgt w := yz^{−k} ∈ O und damit y = wz^{k} ∈ O[z]. □

Dieser Satz besagt also, dass Stellen, Bewertungsringe und diskrete Bewertungen eines Funktionenkörpers im wesentlichen dasselbe Objekt beschreiben.

Die folgende Definition ist naheliegend, da wir uns, falls K algebraisch abgeschlossen ist, die Elemente eines Funktionenkörpers als Funktionen denken können.

Definition 2.2.5 Sei z ∈ F und P ∈ ℙ_{F}. Wir sagen: P sei eine Nullstelle von z, wenn ν_{P} (z) > 0 ist, und P sei ein Pol von z, wenn ν_{P} (z) < 0 ist. Falls ν_{P} (z) = m > 0 ist, nennen wir P eine Nullstelle der Ordnung m, falls ν_{P} (z) = −m < 0 ist, sagen wir P ist ein Pol der Ordnung m.

Die nächste Folgerung kann man folgendermaßen interpretieren: jedes z ∈ F, welches nicht konstant ist, erzeugt eine nicht-konstante Funktion im Sinne von (2.5).

Folgerung 2.2.6 Sei F/K ein Funktionenkörper, z ∈ F nicht konstant. Dann hat z mindestens eine Nullstelle und einen Pol.

Beweis. Betrachten wir den Ring R = K[z] und das Ideal I = zK[z]. Satz 2.1.12 garantiert uns, dass eine Stelle P ∈ ℙ_{F} mit z ∈ P existiert, also ist P eine Nullstelle von z. Dasselbe Argument zeigt, dass z^{−1} eine Nullstelle Q ∈ ℙ_{F} besitzt. Dieses Q ist ein Pol von z. □

Ein wichtiges Resultat ist die folgende Verallgemeinerung des Chinesischen Restsatzes. Dieser Satz stammt von Artin und Whaples (1967, siehe [1]) und ist unter anderem als schwacher Approximationssatz bekannt.

Satz 2.2.7 (Schwacher Approximationssatz) Sei F/K ein Funktionenkörper, P_{1}, …, P_{n} ∈ ℙ_{F} paarweise verschiedene Stellen von F/K, x_{1}, …, x_{n} ∈ F und r_{1}, …, r_{n} ∈ ℤ. Dann gibt es ein x ∈ F mit

ν_{P_{i}}(x − x_{i}) = r_{i} für i = 1, …, n.

Beweis. Der Beweis ist in mehrere Schritte eingeteilt. Der Einfachheit halber schreiben wir ν_{i} anstatt ν_{P_{i}}.

1. Schritt: Es gibt ein u ∈ F mit ν_{1}(u) > 0 und ν_{i}(u) < 0 für i = 2, …, n. Der Beweis dieser Behauptung erfolgt durch Induktion nach n. Für n = 2 beachten wir, dass O_{P_{1}} ⊈ O_{P_{2}} gilt und umgekehrt, da Bewertungsringe nach Satz 2.2.4 (c) maximale Unterringe von F sind. Deshalb gibt es ein y_{1} ∈ O_{P_{1}}\O_{P_{2}} und ein y_{2} ∈ O_{P_{2}}\O_{P_{1}}. Es gilt ν_{1}(y_{1}) ≥ 0, ν_{2}(y_{1}) < 0, ν_{1}(y_{2}) < 0 und ν_{2}(y_{2}) ≥ 0. Das Element u := y_{1}/y_{2} hat also die gewünschte Eigenschaft: ν_{1}(u) > 0, ν_{2}(u) < 0. Für n > 2 haben wir nach Induktionsannahme ein Element y mit ν_{1}(y) > 0, ν_{2}(y) < 0, …, ν_{n−1}(y) < 0. Wir müssen zeigen, dass ν_{n}(y) < 0 ist. Im Fall ν_{n}(y) ≥ 0 wählen wir ein z mit ν_{1}(z) > 0, ν_{n}(z) < 0 und setzen u := y + z^{r}. Dabei ist r ≥ 1 so gewählt, dass r · ν_{i}(z) ≠ ν_{i}(y) für i = 1, …, n − 1 ist. Es folgt, dass ν_{1}(u) ≥ min{ν_{1}(y), r · ν_{1}(z)} > 0 und ν_{i}(u) = min{ν_{i}(y), r · ν_{i}(z)} < 0 für i = 2, …, n ist.

2. Schritt: Es gibt ein w ∈ F, sodass ν_{1}(w − 1) > r_{1} und ν_{i}(w) > r_{i} für i = 2, …, n ist. Wähle u aus dem 1. Schritt und setze w := (1 + u^{s})^{−1}. Wir erhalten für genügend großes s ∈ ℕ, ν_{1}(w − 1) = ν_{1}(−u^{s}(1 + u^{s})^{−1}) = s · ν_{1}(u) > r_{1} und ν_{i}(w) = −ν_{i}(1 + u^{s}) = −s · ν_{i}(u) > r_{i} für i = 2, …, n.

3. Schritt: Bei gegebenen y_{1}, …, y_{n} ∈ F gibt es ein Element z ∈ F mit ν_{i}(z − y_{i}) > r_{i} für i = 1, …, n. Wir wählen ein s ∈ ℤ, sodass ν_{i}(y_{j}) ≥ s für alle i, j ∈ {1, …, n} ist. Mit Hilfe von Schritt 2 erhalten wir w_{1}, …, w_{n} mit

ν_{i}(w_{i} − 1) > r_{i} − s und ν_{j}(w_{i}) > r_{j} − s für j ≠ i.

Dann hat z := ∑_{j=1}^{n} y_{j}w_{j} die gewünschten Eigenschaften.

Jetzt können wir den Beweis vervollständigen. Aus Schritt 3 erhalten wir ein z ∈ F mit ν_{i}(z − x_{i}) > r_{i}, i = 1, …, n. Als nächstes wählen wir z_{i} mit ν_{i}(z_{i}) = r_{i}, was trivialerweise möglich ist. Wieder finden wir aufgrund von Schritt 3 ein z′ mit ν_{i}(z′ − z_{i}) > r_{i} für i = 1, …, n. Es folgt

ν_{i}(z′) = ν_{i}((z′ − z_{i}) + z_{i}) = min{ν_{i}(z′ − z_{i}), ν_{i}(z_{i})} = r_{i}.

Sei x := z + z′. Dann ist

ν_{i}(x − x_{i}) = ν_{i}((z − x_{i}) + z′) = min{ν_{i}(z − x_{i}), ν_{i}(z′)} = r_{i},

womit die Behauptung gezeigt ist. □

Im Wesentlichen ist die Aussage des Approximationssatzes die Folgende: Wenn v_{1}, …, v_{n} paarweise verschiedene diskrete Bewertungen von F/K sind, z ∈ F und wenn wir die Werte v_{1}(z), …, v_{n−1}(z) kennen, dann können wir nichts über den Wert v_{n}(z) aussagen. Aus diesem Grund heißt Satz 2.2.7 auch manchmal Satz von der Unabhängigkeit der Bewertungen.

Wir erhalten mit Hilfe des schwachen Approximationssatzes 2.2.7 einen anderen Beweis von Folgerung 2.1.13 (b).

Folgerung 2.2.8 Jeder Funktionenkörper hat unendlich viele Stellen.

Beweis. Angenommen es gäbe nur endlich viele Stellen P_{1}, …, P_{n}. Aufgrund des schwachen Approximationssatzes 2.2.7 könnten wir ein Element 0 ≠ x ∈ F mit ν_{P_{i}}(x) > 0 für i = 1, …, n finden. Dann muß x transzendent über K sein, da x Nullstellen besitzt. Widerspruch zu Folgerung 2.2.6, da x keine Pole besitzt. □

Wir können jetzt zeigen, dass die Anzahl der Nullstellen von x ∈ F beschränkt ist. Später werden wir sehen, dass ein nicht konstantes x genauso viele Nullstellen, wie Polstellen besitzt, wenn man sie nur geeignet zählt. Ein wichtiger Schritt in diese Richtung wird der folgende Satz sein. Außerdem ist er eine Verschärfung der Resultate von Hilfssatz 2.1.5 und Satz 2.1.9.

Satz 2.2.9 (Nullstellensatz) Sei F/K ein Funktionenkörper und P_{1}, …, P_{r} Nullstellen von einem Element x ∈ F. Dann gilt:

∑_{i=1}^{r} v_{P_{i}}(x) · deg P_{i} ≤ [F : K(x)].

Beweis. Wir setzen ν_{i} := ν_{P_{i}}, f_{i} := deg P_{i} und e_{i} := ν_{i}(x). Für jedes i gibt es ein Element t_{i} mit

ν_{i}(t_{i}) = 1 und ν_{k}(t_{i}) = 0 für k ≠ i.

Als nächstes wählen wir s_{i1}, …, s_{if_{i}} ∈ O_{P_{i}}, sodass s_{i1}(P_{i}), …, s_{if_{i}}(P_{i}) eine Basis des Restklassenkörpers F_{P_{i}} über K bildet. Aufgrund des schwachen Approximationssatzes 2.2.7 können wir z_{ij} ∈ F finden, sodass für alle i, j gilt:

ν_{i}(s_{ij} − z_{ij}) > 0 und ν_{k}(z_{ij}) ≥ e_{k} für k ≠ i.  (2.6)

Wir behaupten, dass die Elemente

t_{i}^{a} · z_{ij}, 1 ≤ i ≤ r, 1 ≤ j ≤ f_{i}, 0 ≤ a < e_{i}

linear unabhängig über K(x) sind. Die Anzahl dieser Elemente ist ∑_{i=1}^{r} f_{i}e_{i} = ∑_{i=1}^{r} ν_{P_{i}}(x)·deg P_{i}, sodass aus dieser Behauptung die Aussage des Satzes folgt. Angenommen es gibt eine nicht triviale Linearkombination

∑_{i=1}^{r} ∑_{j=1}^{f_{i}} ∑_{a=0}^{e_{i}−1} φ_{ija}t_{i}^{a}z_{ij} = 0  (2.7)

über K(x). O.B.d.A. können wir annehmen, dass die φ_{ija} ∈ K[x] sind und dass nicht alle φ_{ija} von x geteilt werden. Dann gibt es Indizes k ∈ {1, …, r} und c ∈ {0, 1, …, e_{k} − 1}, sodass

x | φ_{kja} für jedes a < c und jedes j ∈ {1, …, f_{k}}, (2.8)
und x ∤ φ_{kjc} für mindestens ein j ∈ {1, …, f_{k}}.

Wenn wir (2.7) mit t_{k}^{−c} multiplizieren, erhalten wir

∑_{i=1}^{r} ∑_{j=1}^{f_{i}} ∑_{a=0}^{e_{i}−1} φ_{ija}t_{i}^{a}t_{k}^{−c}z_{ij} = 0.  (2.9)

Für i ≠ k liegen alle Summanden von (2.9) in P_{k} da

ν_{k}(φ_{ija}t_{i}^{a}t_{k}^{−c}z_{ij}) = ν_{k}(φ_{ija}) + aν_{k}(t_{i}) − cν_{k}(t_{k}) + ν_{k}(z_{ij})
≥ 0 + 0 − c + e_{k} > 0.

Für i = k und a < c folgt aus der Implikation x | φ_{kja} ⇒ ν_{k}(φ_{kja}) ≥ e_{k}, dass

ν_{k}(φ_{kja}t_{k}^{a−c}z_{kj}) ≥ e_{k} + a − c ≥ e_{k} − c > 0

ist. Für i = k und a > c gilt

ν_{k}(φ_{kja}t_{k}^{a−c}z_{kj}) ≥ a − c > 0.

Wenn wir das mit (2.9) kombinieren, erhalten wir

∑_{j=1}^{f_{k}} φ_{kjc}z_{kj} ∈ P_{k}.  (2.10)

Wenn wir beachten, dass φ_{kjc}(P_{k}) ∈ K ist, und dass aufgrund (2.8) nicht alle φ_{kjc}(P_{k}) = 0 sein können, erhalten wir aus (2.10) eine nicht triviale Linearkombination

∑_{j=1}^{f_{k}} φ_{kjc}(P_{k}) · z_{kj}(P_{k}) = 0

über K. Das ist ein Widerspruch, dazu dass z_{k1}(P_{k}), …, z_{kf_{k}}(P_{k}) eine Basis von F_{P_{k}}/K bildet. □

Folgerung 2.2.10 In einem Funktionenkörper F/K hat jedes Element 0 ≠ x ∈ F nur endlich viele Nullstellen und Pole.

Beweis. Wenn x konstant ist, besitzt x weder Nullstellen noch Pole. Wenn x transzendent über K ist, dann ist die Anzahl der Nullstellen ≤ [F : K(x)] aufgrund des Nullstellensatzes 2.2.9. Dasselbe Argument zeigt, dass x^{−1} nur endlich viele Nullstellen besitzt. □

Eine weitere unmittelbare Folgerung ist, dass verschiedene Elemente eines Funktionenkörpers verschiedene Funktionen auf den Stellen induzieren. Es gilt:

Folgerung 2.2.11 Sei F/K ein Funktionenkörper und x, y ∈ F. Falls x(P) = y(P) für alle Stellen P von F/K gilt, dann folgt x = y.

Beweis. Die Bedingung impliziert, dass ν_{P} (x − y) > 0 für alle Stellen P ist, also sind alle Stellen Nullstellen von x − y. Wegen Folgerung 2.1.13 (b) oder Folgerung 2.2.8 gibt es unendlich viele Stellen. Aus Folgerung 2.2.10 folgt nun, dass x − y = 0 gelten muss. □

2.3 Der rationale Funktionenkörper

Um ein besseres Verständnis für Bewertungen und Stellen zu bekommen, ist es wichtig eine genaue Vorstellung von ihnen zu haben, zumindest im einfachsten Fall, dem des rationalen Funktionenkörpers. Deshalb wollen wir jetzt den rationalen Funktionenkörper F = K(x) betrachten, wobei x transzendent über K ist.

Gegeben sei ein irreduzibles Polynom p(x) ∈ K[x]. Wir betrachten die Menge

O_{p(x)} := \{\frac{f(x)}{g(x)} | f(x), g(x) ∈ K[x], p(x) ∤ g(x)\} .  (2.11)

Wie man sofort sieht, ist O_{p(x)} ein Bewertungsring von K(x)/K. Die dazugehörige Stelle lautet

P_{p(x)} = \{\frac{f(x)}{g(x)} | f(x), g(x) ∈ K[x], p(x) | f(x), p(x) ∤ g(x)\} .  (2.12)

Im Fall, dass p(x) = x − α linear ist, mit α ∈ K, schreiben wir abkürzend

P_{α} := P_{x−α} ∈ ℙ_{K(x)}.  (2.13)

Ein weiterer Bewertungsring von K(x)/K ist der folgende

O_{∞} := \{\frac{f(x)}{g(x)} | f(x), g(x) ∈ K[x], deg f(x) ≤ deg g(x)\}  (2.14)

mit dem maximalen Ideal

P_{∞} = \{\frac{f(x)}{g(x)} | f(x), g(x) ∈ K[x], deg f(x) < deg g(x)\} .  (2.15)

Diese Stelle nennt man auch die unendliche Stelle von K(x)/K. Man beachte, dass diese Bezeichnungen von der speziellen Wahl des erzeugenden Elementes x von K(x)/K abhängen und dass die unendliche Stelle bezüglich 1/x die Stelle P_{0} bezüglich x ist.

Ihre Eigenschaften sind im folgenden Satz zusammengefasst:

Satz 2.3.1 Sei F = K(x) der rationale Funktionenkörper.

(a) Sei P = P_{p(x)} ∈ ℙ_{K(x)} die durch (2.12) definierte Stelle, wobei p(x) ∈ K[x] ein irreduzibles Polynom ist. Dann ist p(x) ein Primelement von P und die dazugehörige diskrete Bewertung ν_{P} kann folgendermaßen beschrieben werden: wenn z ∈ K(x)\{0} in der Form z = p(x)^{n} · (f(x)/g(x)) mit n ∈ ℤ, f(x), g(x) ∈ K[x], p(x) ∤ f(x) und p(x) ∤ g(x) geschrieben wird, dann ist ν_{P} (z) = n. Der Restklassenkörper K(x)_{P} = O/P ist isomorph zu K[x]/(p(x)), ein Isomorphismus ist gegeben durch

ϕ : \{ \begin{matrix}K[x]/(p(x)) & ⟶ & K(x)_{P} , \\ f(x) mod p(x) & ⟼ & f(x)(P) \end{matrix}

Daraus folgt außerdem: deg P = deg p(x).

(b) Im Fall: p(x) = x − α mit α ∈ K, ist der Grad von P = P_{α} eins und der Restklassenabbildung ist gegeben durch

z(P) = z(α) für z ∈ K(x),

wobei z(α) folgendermaßen definiert ist: sei z = f(x)/g(x) mit relativ primen Polynomen f(x), g(x) ∈ K[x]. Dann ist

z(α) = \{ \begin{matrix}f(α)/g(α) & falls g(α) ≠ 0, \\ ∞ & falls g(α) = 0. \end{matrix}

(c) Sei P = P_{∞} die unendliche Stelle von K(x)/K definiert durch (2.15).

Dann gilt deg P_{∞} = 1. Ein Primelement für P_{∞} ist 1/x. Die dazugehörige diskrete Bewertung ist gegeben durch

ν_{∞}(f(x)/g(x)) = deg g(x) − deg f(x),

wobei f(x), g(x) ∈ K[x] sind. Die Restklassenabbildung zu P_{∞} wird bestimmt durch z(P_{∞}) = z(∞) für z ∈ K(x), wobei z(∞) wie folgt definiert ist: falls

z = \frac{a_{n}x^{n} + ⋯ + a_{0}}{b_{m}x^{m} + ⋯ + b_{0}} mit a_{n}, b_{m} ≠ 0,

dann ist

z(∞) = \{ \begin{matrix}a_{n}/b_{m} & falls n = m, \\ 0 & falls n < m, \\ ∞ & falls n > m. \end{matrix}

(d) K ist der volle Konstantenkörper von K(x)/K.

Beweis. (a) Sei P = P_{p(x)}, p(x) ∈ K[x] irreduzibel. Das Ideal P_{p(x)} ⊆ O_{p(x)} wird offensichtlich von p(x) erzeugt, daher ist p(x) ein Primelement für P. Die Beschreibung der zugehörigen diskreten Bewertung ist daher ebenfalls klar. Um die Aussage über den Restklassenkörper zu zeigen, betrachten wir den Ringhomomorphismus

φ : \{ \begin{matrix}K[x] & ⟶ & K(x)_{P} , \\ f(x) & ⟼ & f(x)(P). \end{matrix}

Der Kern von φ ist klarerweise das von p(x) erzeugte Ideal. Die Abbildung ist surjektiv, denn wenn z ∈ O_{p(x)} ist – wir können z = u(x)/v(x) und u(x), v(x) ∈ K[x] mit a(x)p(x) + b(x)v(x) = 1 schreiben –, dann gilt

z = 1 · z = \frac{a(x)u(x)}{v(x)}p(x) + b(x)u(x),

und z(P) = (b(x)u(x))(P) liegt im Bild von φ. Deshalb induziert φ den behaupteten Isomorphismus ϕ von K[x]/(p(x)) auf K(x)_{P}.

(b) Jetzt sei P = P_{α} mit α ∈ K. Falls f(x) ∈ K[x] ist, dann gilt (x − α) | (f(x) − f(α)) und daher f(x)(P) = (f(x) − f(α))(P) + f(α)(P) = f(α). Ein beliebiges Element z ∈ O_{P} kann als z = f(x)/g(x) mit Polynomen f(x), g(x) ∈ K[x] und (x−α) ∤ g(x) geschrieben werden. Daher ist g(x)(P) = g(α) ≠ 0 und damit

z(P) = \frac{f(x)(P)}{g(x)(P)} = \frac{f(α)}{g(α)} = z(α).

(c) Die erste Aussage folgt aus der Beobachtung, dass F_{P_{∞}} = O_{∞}/P_{∞} = {r + P_{∞} | r ∈ K} ≅ K gilt. Das bedeutet: deg P_{∞} = 1. Wir zeigen als nächstes, dass 1/x ein Primelement von P_{∞} ist. Wir nehmen ein Element z = f(x)/g(x) ∈ P_{∞}. Es gilt also deg f(x) < deg g(x). Dann gilt

z = \frac{1}{x} · \frac{xf(x)}{g(x)}, mit deg(xf(x)) ≤ deg g(x).

Daher ist z ∈ (1/x)O_{∞} und somit 1/x ein P_{∞}-Primelement. Die Aussage über die zu P_{∞} gehörige diskrete Bewertung folgt jetzt unmittelbar aus der Definition. Die letzte Aussage rechnet man direkt nach.

(d) Es gibt in K(x)/K rationale Stellen, nämlich die Stellen P = P_{α} mit α ∈ K. Daher folgt die Aussage sofort aus Folgerung 2.1.11. □

Satz 2.3.2 Es gibt außer den Stellen P_{p(x)} und P_{∞}, definiert durch (2.12) und (2.15), keine weiteren Stellen im rationalen Funktionenkörper K(x)/K.

Beweis. Es genügt folgendes zu zeigen: Gegeben sei P ∈ ℙ_{K(x)}, dann ist entweder P = P_{∞}, oder es gibt es ein irreduzibles Polynom p(x) ∈ K[x] mit O_{p(x)} = O_{P}.

1. Fall: Sei x ∈ O_{P}. Dann gilt K[x] ⊆ O_{P}. Sei I := K[x] ∩ P. Dann ist I ein Ideal von K[x] und prim. Die Restklassenabbildung induziert eine Einbettung K[x]/I ↪ K(x)_{P}, daher ist nach Satz 2.1.9 I ≠ {0}. Es folgt, dass ein eindeutig bestimmtes, irreduzibles, normiertes Polynom p(x) ∈ K[x] existiert, mit I = K[x] ∩ P = p(x) · K[x]. Jedes g(x) ∈ K[x] mit p(x) ∤ g(x) ist nicht in I, daher ist g(x) ∉ P und damit 1/g(x) ∈ O_{P} nach Satz 2.1.4. Wir schließen

O_{p(x)} = \{\frac{f(x)}{g(x)} | f(x), g(x) ∈ K[x], p(x) ∤ g(x)\} ⊆ O_{P} .

Da Bewertungsringe nach Satz 2.2.4 maximale echte Unterringe von K[x] sind, muß O_{P} = O_{p(x)} gelten.

2. Fall: Angenommen x ∉ O_{P}. Wir können zunächst K[x^{−1}] ⊆ O_{P} , x^{−1} ∈ P ∩ K[x^{−1}] und P ∩ K[x^{−1}] = x^{−1}K[x^{−1}] schließen. Wie im 1. Fall erhalten wir

O_{P} ⊇ \{\frac{f(x^{−1})}{g(x^{−1})} | f(x^{−1}), g(x^{−1}) ∈ K[x^{−1}], x^{−1} ∤ g(x^{−1})\}
= \{\frac{a_{0} + a_{1}x^{−1} + ⋯ + a_{n}x^{−n}}{b_{0} + b_{1}x^{−1} + ⋯ + b_{m}x^{−m}} | b_{0} ≠ 0\}
= \{\frac{a_{0}x^{m+n} + ⋯ + a_{n}x^{m}}{b_{0}x^{m+n} + ⋯ + b_{m}x^{n}} | b_{0} ≠ 0\}
= \{\frac{u(x)}{v(x)} | u(x), v(x) ∈ K[x], deg u(x) ≤ deg v(x)\}
= O_{∞}.

Daraus folgt schließlich O_{P} = O_{∞} und damit P = P_{∞}. □

Folgerung 2.3.3 Die rationalen Stellen von K(x)/K stehen in einer umgekehrt eindeutigen Beziehung mit K ∪ {∞}.

Beweis. Unmittelbare Folgerung aus Satz 2.3.1 und Satz 2.3.2. □

2.4 Divisoren

Der Konstantenkörper K̄ eines algebraischen Funktionenkörpers F/K ist nach Folgerung 2.1.14 eine endliche Erweiterung von K und wir können F auch als Funktionenkörper über K̄ auffassen. Deshalb ist es uns problemlos möglich von nun an folgende Voraussetzung zu treffen:

F/K sei ein algebraischer Funktionenkörper in einer Variablen, sodass K der volle Konstantenkörper von F/K ist.

Wir definieren nun Folgendes:

Definition 2.4.1 Die (additiv geschriebene) freie abelsche Gruppe, welche durch die Stellen von F/K erzeugt wird, heißt die Divisorengruppe von F/K und wird mit D_{F} bezeichnet. Die Elemente von D_{F} heißen Divisoren von F/K.

Ein Divisor D ist also eine formale Summe

D = ∑_{P ∈ℙ_{F}} n_{P} P mit n_{P} ∈ ℤ, fast alle n_{P} = 0.

Der Träger von D ist definiert durch

supp D := {P ∈ ℙ_{F} | n_{P} ≠ 0}.

Die Addition von zwei Divisoren D = ∑ n_{P} P und D′ = ∑ n′_{P} P erfolgt komponentenweise:

D + D′ = ∑_{P ∈ℙ_{F}}(n_{P} + n′_{P})P.

Das Nullelement der Divisorengruppe D_{F} ist der Nulldivisor

0 := ∑_{P ∈ℙ_{F}} n_{P} P, mit allen n_{P} = 0.

Wir können die diskreten Bewertungen folgendermaßen auf Divisoren fortsetzen: Für Q ∈ ℙ_{F} und D = ∑ n_{P} P ∈ D_{F} definieren wir ν_{Q}(D) := n_{Q}.

Es ist dann

supp D = {P ∈ ℙ_{F} | ν_{P} (D) ≠ 0} und D = ∑_{P ∈supp D} ν_{P} (D) · P.

Auf D_{F} kann man durch

D_{1} ≤ D_{2} : ⟺ ν_{P} (D_{1}) ≤ ν_{P} (D_{2}) für alle P ∈ ℙ_{F}

eine partielle Ordnung definieren. Definition 2.4.2 Ein Divisor der Form D = P mit P ∈ ℙ_{F} heißt ein Primdivisor. Ein Divisor D ≥ 0 heißt positiv (oder effektiv). Der Grad eines Divisors D wird definiert durch

deg D := ∑_{P ∈ℙ_{F}} ν_{P} (D) · deg P.

Dadurch ist ein Homomorphismus deg : D_{F} → ℤ definiert.

Nach Folgerung 2.2.10 hat jedes Element 0 ≠ x ∈ F nur endlich viele Nullstellen und Pole in ℙ_{F}. Deshalb ist die folgende Definition sinnvoll. Definition 2.4.3 Sei 0 ≠ x ∈ F und bezeichne Z (bzw. N) die Menge der Nullstellen (bzw. Pole) von x in ℙ_{F}. Wir definieren

(x)_{0} := ∑_{P ∈Z} ν_{P} (x)P, den Nullstellendivisor von x,

(x)_{∞} := ∑_{P ∈N}(−ν_{P} (x))P, den Polstellendivisor von x,
(x) := (x)_{0} − (x)_{∞}, den Hauptdivisor von x.

Klarerweise ist (x)_{0} ≥ 0, (x)_{∞} ≥ 0 und es gilt

(x) = ∑_{P ∈ℙ_{F}} ν_{P} (x)P.  (2.16)

Hilfssatz 2.4.4 Für 0 ≠ x ∈ F gilt:

x ∈ K ⟺ (x) = 0.

Beweis. Folgt sofort aus Satz 2.1.4, Folgerung 2.2.6 und der Generalvoraussetzung, dass K = K̄ ist. □

Hilfssatz 2.4.5 Die Menge {(x) | x ∈ F \{0}} ist eine Untergruppe von D_{F}.

Beweis. Nach Hilfssatz 2.4.4 liegt der Nulldivisor in dieser Menge. Falls 0 ≠ x, y ∈ F gegeben sind, dann gilt nach (2.16) (xy) = (x) + (y) und damit die Behauptung. □

Definition 2.4.6

P_{F} := {(x) | x ∈ F \{0}}

heißt die Gruppe der Hauptdivisoren von F/K. Die Faktorgruppe

C_{F} := D_{F} /P_{F}

heißt die Divisorklassengruppe. Für einen Divisor D ∈ D_{F} schreiben wir [D] für das zugehörige Element in der Faktorgruppe C_{F}, und sprechen von der Divisorklasse von D. Zwei Divisoren D, D′ ∈ D_{F} nennen wir äquivalent, wenn [D] = [D′] gilt, also wenn D = D′ + (x) für ein x ∈ F \{0} ist. Wir schreiben in diesem Fall

D ∼ D′.

Wie man sofort sieht, ist ∼ eine Äquivalenzrelation.

Die nächste Definition spielt eine entscheidende Rolle in der weiteren Theorie.

Definition 2.4.7 Für einen Divisor A ∈ D_{F} setzen wir

L(A) := {x ∈ F \{0} | (x) ≥ −A} ∪ {0},

und nennen L(A) den Riemann-Roch-Raum von A.

Diese Definition läßt sich folgendermaßen interpretieren: Es sei

A = ∑_{i=1}^{r} n_{i}P_{i} − ∑_{j=1}^{s} m_{j}Q_{j}

mit n_{i} > 0, m_{j} > 0 dann enthält L(A) alle Elemente x ∈ F, die folgende Bedingungen erfüllen:

(1) x hat Nullstellen mit Ordnung ≥ m_{j} an den Stellen Q_{j} für j = 1, …, s, und

(2) x darf nur an den Stellen P_{1}, …, P_{r} Pole haben, mit Polordnung höchstens n_{i} bei P_{i} (i = 1, …, r).

Zunächst wollen wir einige Eigenschaften und einfache Beobachtungen zusammenfassen.

Hilfssatz 2.4.8 Sei A ∈ D_{F}. Dann gilt:

(a) x ∈ L(A) ⟺ ν_{P} (x) ≥ −ν_{P} (A) für alle P ∈ ℙ_{F}.

(b) L(A) ≠ {0} ⟺ es gibt einen Divisor A′ ∼ A mit A′ ≥ 0.

Beweis. (a) Trivial.

(b) Folgt sofort aus 0 ≠ x ∈ L(A) ⇔ (x) ≥ −A ⇔ A′ := (x) + A ≥ 0 und der Definition von ∼. □

Hilfssatz 2.4.9 Sei A ∈ D_{F}. Dann gilt:

(a) L(A) ist ein Vektorraum über K.

(b) Wenn A′ ein zu A äquivalenter Divisor ist, dann gilt L(A) ≅ L(A′) (isomorph als Vektorräume über K).

Beweis. (a) Sei x, y ∈ L(A) und a ∈ K. Für jedes P ∈ ℙ_{F} gilt: ν_{P} (x + y) ≥ min{ν_{P} (x), ν_{P} (y)} ≥ −ν_{P} (A) und ν_{P} (ax) = ν_{P} (a) + ν_{P} (x) ≥ −ν_{P} (A). Daher sind nach Hilfssatz 2.4.8 x + y und ax in L(A).

(b) Nach Annahme ist A = A′ +(z) mit 0 ≠ z ∈ F. Betrachte die Abbildung

φ : \{ \begin{matrix}L(A) & ⟶ & F, \\ x & ⟼ & xz. \end{matrix}

Das ist eine K-lineare Abbildung, deren Bild in L(A′) liegt. Genauso ist

φ′ : \{ \begin{matrix}L(A′) & ⟶ & F, \\ x & ⟼ & xz^{−1} \end{matrix}

eine K-lineare Abbildung von L(A′) nach L(A). Diese Abbildungen sind zueinander invers, daher ist φ ein Isomorphismus zwischen L(A) und L(A′). □

Hilfssatz 2.4.10 Es gilt:

(a) L(0) = K.

(b) Falls A < 0, A ∈ D_{F} ist, dann ist L(A) = {0}.

Beweis. (a) Wir haben (x) = 0 für 0 ≠ x ∈ K nach Hilfssatz 2.4.4, daher ist K ⊆ L(0). Umgekehrt folgt aus 0 ≠ x ∈ L(0), dass (x) ≥ 0 ist. Das bedeutet aber, dass x keine Pole besitzt. Aus Folgerung 2.2.6 erhalten wir, dass x ∈ K sein muß.

(b) Angenommen es gibt ein Element 0 ≠ x ∈ L(A). Dann ist (x) ≥ −A > 0, was zur Folge hat, dass x mindestens eine Nullstelle, aber keinen Pol besitzt, was unmöglich ist. □

Unser nächstes Ziel ist es zu zeigen, dass L(A) für alle A ∈ D_{F} endlichdimensional ist.

Hilfssatz 2.4.11 Seien A, B Divisoren von F/K mit A ≤ B. Dann haben wir L(A) ⊆ L(B) und

dim(L(B)/L(A)) ≤ deg B − deg A.

Beweis. L(A) ⊆ L(B) ist trivial. Um die zweite Aussage zu beweisen, können wir annehmen, dass B = A+P für ein P ∈ ℙ_{F} gilt. Der allgemeine Fall folgt dann durch vollständige Induktion. Wählen wir also ein Element t ∈ F mit ν_{P} (t) = ν_{P} (B) = ν_{P} (A) + 1. Für x ∈ L(B) gilt: ν_{P} (x) ≥ −ν_{P} (B) = −ν_{P} (t). Daher ist xt ∈ O_{P}. Wir erhalten durch

ψ : \{ \begin{matrix}L(B) & ⟶ & F_{P} , \\ x & ⟼ & (xt)(P) \end{matrix}

eine K-lineare Abbildung. Es gilt: x ∈ ker(ψ) ⇔ ν_{P} (xt) > 0, das heißt ν_{P} (x) ≥ −ν_{P} (A). Daher ist ker(ψ) = L(A), und ψ induziert eine K-lineare injektive Abbildung von L(B)/L(A) nach F_{P}. Es folgt

dim(L(B)/L(A)) ≤ dim F_{P} = deg B − deg A.
□

Satz 2.4.12 Für jeden Divisor A ∈ D_{F} ist der Riemann-Roch-Raum L(A) ein endlichdimensionaler Vektorraum über K. Genauer gilt: Wenn A = A_{+} − A_{−} mit positiven Divisoren A_{+} und A_{−} ist, dann ist

dim L(A) ≤ deg A_{+} + 1.

Beweis. Da L(A) ⊆ L(A_{+}) ist, genügt es zu zeigen, dass

dim L(A_{+}) ≤ deg A_{+} + 1.

Da 0 ≤ A_{+} gilt, folgt aus Hilfssatz 2.4.11, dass dim(L(A_{+})/L(0)) ≤ deg A_{+} ist. Andererseits gilt dim L(A_{+}) = dim(L(A_{+})/L(0)) + 1, da nach Hilfssatz 2.4.10 (a) L(0) = K ist, und damit folgt die Behauptung. □

Definition 2.4.13 Für A ∈ D_{F} nennt man die Zahl dim A := dim L(A) die Dimension des Divisors A.

Eine der wichtigsten Fragen in der Theorie der algebraischen Funktionenkörper ist die Berechnung der Dimension eines Divisors. Die Antwort wird uns der Satz von Riemann-Roch geben.

Als erster Schritt in diese Richtung zeigen wir die folgende Verschärfung des Nullstellensatzes 2.2.9. Ihre Aussage ist im wesentlichen, dass jedes Element 0 ≠ x ∈ F genauso viele Nullstellen wie Pole besitzt, wenn man sie nur richtig zählt.

Satz 2.4.14 Jeder Hauptdivisor hat Grad 0. Genauer: Sei 0 ≠ x ∈ F/K und (x)_{0} bzw. (x)_{∞} bezeichne den Nullstellen- bzw. Poldivisor von x. Dann gilt:

deg(x)_{0} = deg(x)_{∞} = [F : K(x)].

Beweis. Sei n := [F : K(x)] und

B := (x)_{∞} = ∑_{i=1}^{r} −ν_{P_{i}}(x)P_{i},

wo P_{1}, …, P_{r} alle Pole von x sind. Dann gilt nach dem Nullstellensatz 2.2.9

deg B = ∑_{i=1}^{r} ν_{P_{i}}(x^{−1}) · deg P_{i} ≤ [F : K(x)] = n,

und daher bleibt zu zeigen, dass n ≤ deg B ebenfalls gilt. Wählen wir eine Basis u_{1}, …, u_{n} von F/K(x) und einen Divisor C ≥ 0, sodass (u_{i}) ≥ −C für i = 1, …, n gilt. Wir erhalten

dim(lB + C) ≥ n(l + 1) für alle l ≥ 0,  (2.17)

was unmittelbar aus der Tatsache, dass x^{i}u_{j} ∈ L(lB + C) für 0 ≤ i ≤ l, 1 ≤ j ≤ n gilt, folgt. Man beachte dabei, dass diese Elemente linear unabhängig über K sind, da u_{1}, …, u_{n} linear unabhängig über K(x) sind. Wenn wir c := deg C setzen, erhalten wir nach Satz 2.4.12 n(l + 1) ≤ dim(lB + C) ≤ l · deg B + c + 1. Daher gilt

l(deg B − n) ≥ n − c − 1  (2.18)

für alle l ∈ ℕ. Die rechte Seite von (2.18) ist unabhängig von l, daher ist (2.18) nur möglich, wenn deg B ≥ n ist. Wir haben also gezeigt, dass deg(x)_{∞} = [F : K(x)] ist. Da (x)_{0} = (x^{−1})_{∞} gilt, können wir nun schließen, dass deg(x)_{0} = deg(x^{−1})_{∞} = [F : K(x^{−1})] = [F : K(x)] ist. □

Folgerung 2.4.15

(a) Seien A, A′ äquivalente Divisoren. Dann ist dim A = dim A′ und deg A = deg A′.

(b) Falls deg A < 0, dann ist dim A = 0.

(c) Für einen Divisor A mit Grad 0 sind die folgenden Aussagen äquivalent:

(1) A ist ein Hauptdivisor.

(2) dim A ≥ 1.

(3) dim A = 1.

Beweis. (a) Folgt sofort aus Hilfssatz 2.4.9 und Satz 2.4.14.

(b) Angenommen, dass dim A > 0 gilt. Nach Hilfssatz 2.4.8 (b) gibt es einen Divisor A′ ∼ A mit A′ ≥ 0. Daher ist deg A = deg A′ ≥ 0. Widerspruch!

(c) (1) ⇒ (2): Falls A = (x) ein Hauptdivisor ist, dann ist x^{−1} ∈ L(A) und daher gilt dim A ≥ 1.

(2) ⇒ (3): Nach Voraussetzung gilt dim A ≥ 1 und deg A = 0. Dann ist A ∼ A′ für ein A′ ≥ 0. Die Bedingungen A′ ≥ 0 und deg A′ = 0 implizieren, dass A′ = 0 ist, daher gilt nach Hilfssatz 2.4.10 (a) dim A = dim A′ = dim 0 = 1.

(3) ⇒ (1): Nach Voraussetzung gilt dim A = 1 und deg A = 0. Wähle 0 ≠ z ∈ L(A), dann ist (z) + A ≥ 0. Da deg((z) + A) = 0 ist, folgt dass (z) + A = 0 ist. Daher ist A = −(z) = (z^{−1}) ein Hauptdivisor. □

In Satz 2.4.12 haben wir gesehen, dass

dim A ≤ 1 + deg A  (2.19)

für jeden Divisor A ≥ 0 ist. Tatsächlich gilt (2.19) für beliebige Divisoren mit Grad ≥ 0.

Hilfssatz 2.4.16 Sei A ein Divisor mit deg A ≥ 0. Dann gilt:

dim A ≤ 1 + deg A.

Beweis. Wir können annehmen, dass dim A > 0 ist. Nach Hilfssatz 2.4.8 (b) gilt A ∼ A′ für einen Divisor A′ ≥ 0. Daher ist dim A = dim A′ ≤ 1 + deg A′ = 1 + deg A nach Folgerung 2.4.15 (a). □

Als nächstes wollen wir die Existenz einer unteren Schranke für dim A zeigen, die von ähnlicher Gestalt wie (2.19) ist.

Satz 2.4.17 Es gibt eine Konstante γ ∈ ℤ, sodass für alle Divisoren A ∈ D_{F} gilt:

deg A − dim A ≤ γ.

Beweis. Zunächst gilt nach Hilfssatz 2.4.11

A_{1} ≤ A_{2} ⇒ deg A_{1} − dim A_{1} ≤ deg A_{2} − dim A_{2}.  (2.20)

Wir wählen ein Element x ∈ F \K fest und betrachten den Divisor B := (x)_{∞}. Wie im Beweis von Satz 2.4.14 gibt es einen Divisor C ≥ 0 (abhängig von x), sodass dim(lB + C) ≥ (l + 1) · deg B für alle l ≥ 0 gilt (siehe (2.17)). Andererseits gilt nach Hilfssatz 2.4.11 dim(lB + C) ≤ dim(lB) + deg C. Durch Kombination dieser beiden Ungleichungen erhalten wir

dim(lB) ≥ (l + 1) deg B − deg C = deg(lB) + ([F : K(x)] − deg C).

Daher gilt

deg(lB) − dim(lB) ≤ γ für alle l ≥ 0  (2.21)

mit einem γ ∈ ℤ. Wir wollen zeigen, dass (2.21) mit demselben γ auch dann noch gilt, wenn wir lB durch irgendeinen Divisor A ∈ D_{F} ersetzen. Dazu zeigen wir zunächst die folgende Behauptung:

Behauptung: Gegeben sei ein Divisor A. Dann existieren Divisoren A_{1}, D und eine ganze Zahl l ≥ 0, sodass A ≤ A_{1}, A_{1} ∼ D und D ≤ lB ist.

Zum Beweis dieser Behauptung wählen wir A_{1} ≥ A, sodass A_{1} ≥ 0 ist. Dann gilt

dim(lB − A_{1}) ≥ dim(lB) − deg A_{1}  (nach Hilfssatz 2.4.11)
≥ deg(lB) − γ − deg A_{1} (nach (2.21))
> 0

für genügend großes l. Daher gibt es ein Element 0 ≠ z ∈ L(lB − A_{1}). Wenn wir D := A_{1}−(z) setzen, erhalten wir A_{1} ∼ D und D ≤ A_{1}−(A_{1}−lB) = lB, wie gewünscht.

Die Aussage des Satzes folgt jetzt so:

deg A − dim A ≤ deg A_{1} − dim A_{1}  (nach (2.20))
= deg D − dim D  (nach Folgerung 2.4.15)
≤ deg(lB) − dim(lB) (nach (2.20))
≤ γ  (nach (2.21)).
□

Besonders wichtig ist dabei die Tatsache, dass γ nicht von A, sondern nur vom Funktionenkörper F/K abhängt.

Definition 2.4.18 Das Geschlecht von F/K ist definiert durch

g := max{deg A − dim A + 1 | A ∈ D_{F} }.

Man beachte, dass diese Definition aufgrund von Satz 2.4.17 sinnvoll ist. Es wird sich herausstellen, dass das Geschlecht die wichtigste Invariante eines Funktionenkörpers ist. Im Folgenden setzen wir stets voraus:

F/K sei ein algebraischer Funktionenkörper mit Geschlecht g.

Als erstes erhalten wir die nachstehende einfache Aussage über das Geschlecht.

Hilfssatz 2.4.19 Das Geschlecht von F/K ist eine nicht negative ganze Zahl.

Beweis. Wir setzen in der Definition des Geschlechtes A = 0. Dann erhalten wir deg(0) − dim(0) + 1 = 0, daher ist g ≥ 0. □

Satz 2.4.20 (Satz von Riemann) Sei F/K ein Funktionenkörper mit Geschlecht g.

(a) Für jeden Divisor A ∈ D_{F} gilt:

dim A ≥ deg A + 1 − g.

(b) Es gibt eine ganze Zahl c, die nur von F/K abhängt, sodass

dim A = deg A + 1 − g

ist, wann immer deg A ≥ c ist.

Beweis. (a) Folgt sofort aus der Definition des Geschlechts.

(b) Wähle einen Divisor A_{0} mit g = deg A_{0} − dim A_{0} + 1 und setze c := deg A_{0} + g. Falls deg A ≥ c ist, dann gilt

dim(A − A_{0}) ≥ deg(A − A_{0}) + 1 − g ≥ c − deg A_{0} + 1 − g ≥ 1.

Daher gibt es ein Element 0 ≠ z ∈ L(A − A_{0}). Betrachten wir jetzt den Divisor A′ := A + (z), der ≥ A_{0} ist. Dann haben wir

deg A − dim A = deg A′ − dim A′ (nach Folgerung 2.4.15)
≥ deg A_{0} − dim A_{0} (nach Hilfssatz 2.4.11)
= g − 1.

Daher ist dim A ≤ deg A + 1 − g. □

Im Allgemeinen ist es sehr schwer, das Geschlecht eines Funktionenkörpers zu bestimmen. Als sehr einfaches Beispiel wollen wir das Geschlecht des rationalen Funktionenkörpers berechnen.

Satz 2.4.21 Der rationale Funktionenkörper K(x)/K hat Geschlecht g = 0.

Beweis. Sei P_{∞} der Poldivisor von x. Betrachte für r ≥ 0 den Vektorraum L(rP_{∞}). Offensichtlich sind die Elemente 1, x, …, x^{r} in L(rP_{∞}), daher gilt

r + 1 ≤ dim(rP_{∞}) = deg(rP_{∞}) + 1 − g = r + 1 − g

für genügend großes r. Es ist also g ≤ 0. Nach Hilfssatz 2.4.19 ist aber für jeden Funktionenkörper g ≥ 0. Damit folgt die Behauptung. □

2.5 Adèle und Weil-Differentiale

Am Beginn steht folgende Definition:

Definition 2.5.1 Für A ∈ D_{F}, nennen wir

i(A) := dim A − deg A + g − 1

den Spezialitätsindex von A.

Der Satz von Riemann 2.4.20 zeigt uns, dass i(A) eine nicht negative ganze Zahl ist, mit i(A) = 0 für deg A genügend groß. Wir werden in diesem Kapitel einige Interpretationen für i(A) als Dimension gewisser Vektorräume besprechen.

Definition 2.5.2 Ein Adèle von F/K ist eine Abbildung

α : \{ \begin{matrix}ℙ_{F} & ⟶ & F, \\ P & ⟼ & α_{P} , \end{matrix}

sodass α_{P} ∈ O_{P} für fast alle P ∈ ℙ_{F} ist. Wir wollen ein Adèle stets als Element des direkten Produktes ∏_{P ∈ℙ_{F}} F auffassen und verwenden daher die Notation α = (α_{P})_{P ∈ℙ_{F}} oder kürzer α = (α_{P}). Die Menge

A_{F} := {α | α ist ein Adèle von F/K}

nennen wir den Adèleraum von F/K und fassen sie in offensichtlicher Weise als Vektorraum über K auf.

Das Hauptadèle eines Elementes x ∈ F ist das Adèle, dessen Komponenten alle gleich x sind. Nach Folgerung 2.2.10 ist diese Definition sinnvoll. Es gibt also eine Einbettung F ↪ A_{F}. Die Bewertungen ν_{P} von F/K können in natürlicher Weise auf A_{F} fortgesetzt werden, indem wir ν_{P} (α) := ν_{P} (α_{P}) setzen (wo α_{P} die P -Komponente des Adèles α bezeichnet). Nach Definition ist ν_{P} (α) ≥ 0 für fast alle P ∈ ℙ_{F}.

Definition 2.5.3 Für A ∈ D_{F} definieren wir

A_{F} (A) := {α ∈ A_{F} | ν_{P} (α) ≥ −ν_{P} (A) für alle P ∈ ℙ_{F} }.

Offensichtlich ist A_{F} (A) ein K-Unterraum von A_{F}.

Zunächst zeigen wir eine analoge Aussage zu Hilfssatz 2.4.11, wobei anstelle des Raumes L(A) nun A_{F} (A) gesetzt wird.

Hilfssatz 2.5.4 Seien A, B ∈ D_{F} mit A ≤ B. Dann gilt A_{F} (A) ⊆ A_{F} (B) und

dim(A_{F} (B)/A_{F} (A)) = deg B − deg A.

Beweis. A_{F} (A) ⊆ A_{F} (B) ist trivial. Es genügt die Aussage für den Fall zu beweisen, dass B = A + P mit P ∈ ℙ_{F} ist. Der allgemeine Fall folgt durch vollständige Induktion. Wir wählen ein t ∈ F mit ν_{P} (t) = ν_{P} (A) + 1 und betrachten die K-lineare Abbildung

φ : \{ \begin{matrix}A_{F} (B) & ⟶ & F_{P} , \\ α & ⟼ & (tα_{P})(P). \end{matrix}

Wegen ν_{P} (tα_{P}) = ν_{P} (t) + ν_{P} (α_{P}) = ν_{P} (A) + 1 + ν_{P} (α_{P}) ≥ ν_{P} (A) + 1 − ν_{P} (B) = 0 ist φ wohldefiniert. Genauso einfach sieht man, dass φ surjektiv ist, und dass der Kern von φ gleich A_{F} (A) ist. Daher folgt:

deg B − deg A = deg P = [F_{P} : K] = dim(A_{F} (B)/A_{F} (A)).
□

Man nennt den Raum A_{F} (A) den Adèleraum über A. Außerdem bezeichnet man A_{F} (A) + F als den erweiterten Adèleraum über A. Analog zum vorigen Hilfssatz erhalten wir:

Hilfssatz 2.5.5 Seien A, B ∈ D_{F} mit A ≤ B. Dann gilt:

dim((A_{F} (B) + F)/(A_{F} (A) + F)) = (deg B − dim B) − (deg A − dim A).

Beweis. Wir haben eine exakte Sequenz von linearen Abbildungen

0 ⟶ L(B)/L(A) ⟶ A_{F} (B)/A_{F} (A) ⟶  (2.22)
⟶ (A_{F} (B) + F)/(A_{F} (A) + F) ⟶ 0,

wobei die Abbildungen σ_{1} : L(B)/L(A) → A_{F} (B)/A_{F} (A) und σ_{2} : A_{F} (B)/ A_{F} (A) → (A_{F} (B)+F)/(A_{F} (A)+F) in offensichtlicher Weise definiert sind. Die einzige nicht triviale Behauptung ist, dass der Kern von σ_{2} im Bild von σ_{1} enthalten ist. Es sei also α ∈ A_{F} (B) mit σ_{2}(α + A_{F} (A)) = 0. Dann ist α ∈ A_{F} (A) + F, und daher gibt es ein x ∈ F mit α − x ∈ A_{F} (A). Da A_{F} (A) ⊆ A_{F} (B) ist, können wir schließen, dass x ∈ A_{F} (B) ∩ F = L(B) gilt. Daher liegt α + A_{F} (A) = x + A_{F} (A) = σ_{1}(x + L(A)) im Bild von σ_{1}.

Aus der Exaktheit der Sequenz (2.22) erhalten wir

dim(A_{F} (B) + F)/(A_{F} (A) + F)
= dim(A_{F} (B)/A_{F} (A)) − dim(L(B)/L(A))
= (deg B − deg A) − (dim B − dim A),

wobei wir Hilfssatz 2.5.4 verwendet haben. □

Der nächste Hilfssatz stellt eine Verbindung zwischen den Räumen A_{F} (A) und A_{F} her.

Hilfssatz 2.5.6 Falls B ein Divisor mit dim B = deg B + 1 − g ist, dann gilt:

A_{F} = A_{F} (B) + F.

Beweis. Zunächst haben wir nach Hilfssatz 2.4.11 für B_{1} ≥ B

dim B_{1} ≤ deg B_{1} + dim B − deg B = deg B_{1} + 1 − g.

Andererseits gilt dim B_{1} ≥ deg B_{1}+1−g nach dem Satz von Riemann 2.4.20. Daher gilt

dim B_{1} = deg B_{1} + 1 − g für jeden Divisor B_{1} ≥ B.  (2.23)

Die Behauptung erhält man nun folgendermaßen: Sei α ∈ A_{F}. Offensichtlich kann man einen Divisor B_{1} ≥ B finden, sodass α ∈ A_{F} (B_{1}) ist. Aus Hilfssatz 2.5.5 und (2.23) folgt

dim(A_{F} (B_{1}) + F)/(A_{F} (B) + F)
= (deg B_{1} − dim B_{1}) − (deg B − dim B)
= (g − 1) − (g − 1) = 0.

Damit gilt: A_{F} (B) + F = A_{F} (B_{1}) + F. Da α ∈ A_{F} (B_{1}) ist, folgt, dass α ∈ A_{F} (B) + F ist. □

Man beachte, dass die Vektorräume A_{F}, A_{F} (A) und F alle unendlichdimensionale Vektorräume sind. Der nächste Satz besagt, dass der Faktorraum A_{F} /(A_{F} (A) + F) jedoch endliche Dimension hat.

Satz 2.5.7 (Schwacher Satz von Riemann-Roch) Für den Spezialitätsindex eines Divisors A gilt:

i(A) = dim(A_{F} /(A_{F} (A) + F)).

Beweis. Aus dem Satz von Riemann 2.4.20 (b) folgt, dass ein Divisor A_{1} ≥ A mit dim A_{1} = deg A_{1}+1−g existiert. Nach Hilfssatz 2.5.6 ist A_{F} = A_{F} (A_{1})+ F, und aus Hilfssatz 2.5.2 erhalten wir daher

dim(A_{F} /(A_{F} (A) + F)) = dim(A_{F} (A_{1}) + F)/(A_{F} (A) + F)
= (deg A_{1} − dim A_{1}) − (deg A − dim A)
= (g − 1) + dim A − deg A = i(A)
□

Diesen Satz kann man auch so formulieren: Für jedes A ∈ D_{F} gilt:

dim A = deg A + 1 − g + dim(A_{F} /(A_{F} (A) + F)).  (2.24)

Der Spezialitätsindex von A ist also das fehlende Glied im Satz von Riemann. Dieser Satz ist eine schwache Version des Satzes von Riemann-Roch, den wir im nächsten Kapitel beweisen werden. Leider ist der Spezialitätsindex ebenfalls schwer zu ermitteln. In der starken Form des Satzes von Riemann-Roch werden wir sehen, dass man den Spezialitätsindex von A als die Dimension des Divisors W −A für einen geeigneten Divisor W berechnen kann.

Als Folgerung erhalten wir eine andere Charakterisierung des Geschlechtes von F/K.

Folgerung 2.5.8 g = dim(A_{F} /(A_{F} (0) + F)).

Beweis. i(0) = dim(0) − deg(0) + g − 1 = 1 − 0 + g − 1 = g. □

Als nächstes führen wir das Konzept der Weil-Differentiale ein, welches dann zu einer weiteren Interpretation des Spezialitätsindex eines Divisors führen wird.

Definition 2.5.9 Ein Weil-Differential von F/K ist eine K-lineare Abbildung ω : A_{F} → K, die auf dem erweiterten Adèleraum A_{F} (A) + F über A für einen Divisor A ∈ D_{F} verschwindet. Wir nennen

Ω_{F} := {ω | ω ist ein Weil-Differential von F/K}

den Raum der Weil-Differentiale von F/K. Für A ∈ D_{F} sei

Ω_{F} (A) := {ω ∈ Ω_{F} | ω verschwindet auf A_{F} (A) + F },

der Raum der Weil-Differentiale über A.

Zunächst sammeln wir die folgenden, sehr einfachen Eigenschaften über Ω_{F} und Ω_{F} (A) für einen Divisor A.

Hilfssatz 2.5.10

(a) Ω_{F} ist ein Vektorraum über K.

(b) Ω_{F} (A) ist ein Teilraum von Ω_{F}.

(c) Seien A, B ∈ D_{F} mit A ≤ B, dann ist Ω_{F} (B) ⊆ Ω_{F} (A).

Beweis. (a) Angenommen ω_{1} verschwindet auf A_{F} (A_{1}) + F und ω_{2} auf Ω_{F} (A_{2}) + F, dann verschwindet ω_{1} + ω_{2} auf Ω_{F} (A_{3}) + F für jeden Divisor A_{3} mit A_{3} ≤ A_{1} und A_{3} ≤ A_{2}. Weiters verschwindet aω_{1} auf Ω_{F} (A_{1}) + F für jedes a ∈ K.

(b) Klarerweise ist Ω_{F} (A) ein Teilraum von Ω_{F}.

(c) Wenn A ≤ B ist, dann ist A_{F} (A) + F ⊆ A_{F} (B) + F. Daher gilt, wenn ω auf A_{F} (B) + F verschwindet, dann erst recht auf A_{F} (A) + F. □

Hilfssatz 2.5.11 Für A ∈ D_{F} gilt dim Ω_{F} (A) = i(A).

Beweis. Ω_{F} (A) ist in natürlicher Weise isomorph zum Raum der Linearformen auf A_{F} /(A_{F} (A)+F). Da nach dem schwachen Satz von Riemann-Roch 2.5.7 dim A_{F} /(A_{F} (A)+F) = i(A) ist, folgt sofort unsere Behauptung. □

Als einfache Folgerung aus Hilfssatz 2.5.11 erhalten wir:

Folgerung 2.5.12 Ω_{F} ≠ 0.

Beweis. Wähle einen Divisor A mit Grad ≤ −2. Dann gilt nach Hilfssatz 2.5.11

dim Ω_{F} (A) = i(A) = dim A − deg A + g − 1 ≥ 1,

daher ist Ω_{F} (A) ≠ 0. □

Definition 2.5.13 Für x ∈ F und ω ∈ Ω_{F} definieren wir xω : A_{F} ⟶ K durch

(xw)(α) := ω(xα).

Klarerweise ist dadurch eine K-lineare Abbildung von A_{F} ⟶ K definiert. Es handelt sich dabei sogar wieder um ein Weil-Differential:

Hilfssatz 2.5.14 xω ist ein Weil-Differential von F/K. Es gilt: Falls ω auf A_{F} (A) + F verschwindet, dann verschwindet xω auf A_{F} (A + (x)) + F.

Beweis. Es genügt zu zeigen, dass xω auf A_{F} (A+(x))+F verschwindet. Sei β = α + y ∈ A_{F} (A + (x)) + F mit α ∈ A_{F} (A + (x)) und y ∈ F. Dann gilt ν_{P} (α) + ν_{P} (x) + ν_{P} (A) ≥ 0. Daraus folgt, dass xβ = xα + xy mit xy ∈ F und xα ∈ A_{F} (A) ist. Das heißt wiederum ω(xβ) = 0, woraus man aufgrund der Definition (xω)(β) = ω(xβ) = 0 erhält. Daher gilt die Behauptung. □

Durch diese Definition bekommt Ω_{F} die Struktur eines Vektorraumes über F. Als nächstes wollen wir die Dimension dieses Raumes untersuchen.

Satz 2.5.15 Ω_{F} ist ein ein-dimensionaler Vektorraum über F.

Beweis. Wir wählen ein 0 ≠ ω_{1} ∈ Ω_{F}, was nach Folgerung 2.5.12 möglich ist. Wir müssen zeigen, dass für jedes Weil-Differential ω_{2} ∈ Ω_{F} ein z ∈ F existiert, mit ω_{2} = zω_{1}. Wir können annehmen, es gelte ω_{2} ≠ 0. Zunächst wählen wir Divisoren A_{1}, A_{2} ∈ D_{F}, sodass ω_{1} ∈ Ω_{F} (A_{1}) und ω_{2} ∈ Ω_{F} (A_{2}) ist. Für einen Divisor B (den wir später noch genauer spezifizieren werden) betrachten wir die K-linearen injektiven Abbildungen

φ_{i} : \{ \begin{matrix}L(A_{i} + B) & ⟶ & Ω_{F} (−B), \\ x & ⟼ & xω_{i}. \end{matrix} (i = 1, 2)

Zuerst zeigen wir eine Behauptung:

Behauptung: Für eine geeignete Wahl von B gilt:

φ_{1}(L(A_{1} + B)) ∩ φ_{2}(L(A_{2} + B)) ≠ {0}.

Für den Beweis verwenden wir eine einfache, bekannte Tatsache aus der linearen Algebra (siehe z.B. [8]): U_{1}, U_{2} seien Teilräume eines endlichdimensionalen Vektorraumes V, dann gilt:

dim(U_{1} ∩ U_{2}) ≥ dim U_{1} + dim U_{2} − dim V.  (2.25)

Sei jetzt B > 0 ein Divisor mit genügend großem Grad, sodass

dim(A_{i} + B) = deg(A_{i} + B) + 1 − g

für i = 1, 2 ist. Das geht nach dem Satz von Riemann 2.4.20. Sei U_{i} := φ_{i}(L(A_{i} + B)) ⊆ Ω_{F} (−B). Da

dim Ω_{F} (−B) = i(−B) = dim(−B) − deg(−B) + g − 1
= deg B + g − 1

ist, erhalten wir

dim U_{1} + dim U_{2} − dim Ω_{F} (−B)
= deg(A_{1} + B) + 1 − g + deg(A_{2} + B) + 1 − g − (deg B + g − 1)
= deg B + (deg A_{1} + deg A_{2} + 3(1 − g)).

Der geklammerte Term ist unabhängig von B, daher ist

dim U_{1} + dim U_{2} − dim Ω_{F} (−B) > 0,

wenn deg B genügend groß ist. Mit (2.25) folgt U_{1} ∩ U_{2} ≠ {0}, was unsere Behauptung zeigt.

Der Rest des Beweises folgt jetzt sehr schnell: Wähle x_{1} ∈ L(A_{1} + B) und x_{2} ∈ L(A_{2} + B), sodass x_{1}ω_{1} = x_{2}ω_{2} ≠ 0 ist. Dann ist ω_{2} = (x_{1}x_{2}^{−1})ω_{1}, was zu zeigen war. □

Als nächstes wollen wir jedem Weil-Differential ω ≠ 0 einen Divisor zuordnen. Dazu betrachten wir die folgende Menge von Divisoren

M(ω) := {A ∈ D_{F} | ω verschwindet auf A_{F} (A) + F }.  (2.26)

Hilfssatz 2.5.16 Sei 0 ≠ ω ∈ Ω_{F}. Dann gibt es einen eindeutig bestimmten Divisor W ∈ M(ω), für den A ≤ W für jedes A ∈ M(ω) gilt.

Beweis. Nach dem Satz von Riemann 2.4.20 gibt es eine Konstante c, die nur vom Funktionenkörper F/K abhängt, mit der Eigenschaft: i(A) = 0, für alle A ∈ D_{F} mit Grad ≥ c. Da nach dem schwachen Satz von Riemann-Roch 2.5.7 dim(A_{F} /(A_{F} (A) + F)) = i(A) ist, erhalten wir, dass deg A < c ist für alle A ∈ M(ω). Daher gibt es einen Divisor W ∈ M(ω) mit maximalem Grad. Angenommen W habe nicht die gewünschte Eigenschaft. Dann gibt es einen Divisor A_{0} ∈ M(ω) mit A_{0} ⩽̸ W, das heißt ν_{Q}(A_{0}) > ν_{Q}(W) für ein Q ∈ ℙ_{F}. Wir behaupten, es sei

W + Q ∈ M(ω),  (2.27)

was ein Widerspruch zur Maximalität von W ist. Um diese Behauptung zu zeigen betrachten wir ein Adèle α = (α_{P}) ∈ A_{F} (W + Q). Wir können α = α′ + α′′ schreiben mit

α′_{P} := \{ \begin{matrix}α_{P} & für P ≠ Q, \\ 0 & für P = Q, \end{matrix} und α′′_{P} := \{ \begin{matrix}0 & für P ≠ Q, \\ α_{Q} & für P = Q. \end{matrix}

Dann ist α′ ∈ A_{F} (W) und α′′ ∈ A_{F} (A_{0}), daher gilt ω(α) = ω(α′) + ω(α′′) = 0. ω verschwindet also auf A_{F} (W + Q) + F, und (2.27) ist damit bewiesen. Die Eindeutigkeit von W ist offensichtlich. □

Die folgende Definition ist jetzt nach dem Hilfssatz 2.5.16 sinnvoll.

Definition 2.5.17

(a) Der Divisor (ω) eines Weil-Differentiales ω ≠ 0 ist der eindeutig bestimmte Divisor von F/K, der die folgenden Eigenschaften erfüllt:

(1) ω verschwindet auf A_{F} ((ω)) + F.

(2) Falls ω auf A_{F} (A) + F verschwindet, dann ist A ≤ (ω).

(b) Für 0 ≠ ω ∈ Ω_{F} und P ∈ ℙ_{F} definieren wir ν_{P} (ω) := ν_{P} ((ω)).

(c) Eine Stelle P heißt Nullstelle (bzw. Pol) von ω ≠ 0, falls ν_{P} (ω) > 0 (bzw. ν_{P} (ω) < 0) ist. ω ≠ 0 heißt regulär bei P, wenn ν_{P} (ω) ≥ 0 ist, und ω heißt regulär (oder holomorph), wenn ω regulär ist für alle P ∈ ℙ_{F}.

Als unmittelbare Konsequenz aus diesen Definitionen erhalten wir

Ω_{F} (A) = {ω ∈ Ω_{F} | ω = 0 oder (ω) ≥ A}  (2.28)

und

Ω_{F} (0) = {ω ∈ Ω_{F} | ω ist regulär }.

Als Folgerung aus Definition 2.5.1 und Hilfssatz 2.5.11 ergibt sich

dim Ω_{F} (0) = g.

Bis jetzt haben wir die sogenannte Diagonaleinbettung F ↪ A_{F} betrachtet, die jedem x ∈ F das dazugehörige Hauptadèle zuordnet. Es gibt aber noch andere Möglichkeiten F in den Raum der Adèle einzubetten. Wir wollen jetzt, für jede Stelle P ∈ ℙ_{F} eine andere Einbettung ι_{P} : F ↪ A_{F} betrachten.

Definition 2.5.18 Sei P ∈ ℙ_{F}.

(a) Für x ∈ F sei ι_{P} (x) ∈ A_{F} das Adèle, dessen P -Komponente x ist, und dessen andere Komponenten alle 0 sind.

(b) Für ein Weil-Differential ω ∈ Ω_{F} definieren wir seine lokale Komponente ω_{P} : F ⟶ K durch

ω_{P} (x) := ω(ι_{P} (x)).

Klarerweise ist ω_{P} eine K-lineare Abbildung.

Satz 2.5.19 Sei ω ∈ Ω_{F} und α = (α_{P}) ∈ A_{F}. Dann ist ω_{P} (α_{P}) ≠ 0 für höchstens endlich viele Stellen P und es gilt

ω(α) = ∑_{P ∈ℙ_{F}} ω_{P} (α_{P}).

Insbesondere gilt:

∑_{P ∈ℙ_{F}} ω_{P} (1) = 0.  (2.29)

Beweis. Wir können ω ≠ 0 annehmen und wir setzen W := (ω) gleich dem Divisor von ω. Es gibt eine endliche Menge S ⊆ ℙ_{F}, sodass

ν_{P} (W) = 0 und ν_{P} (α_{P}) ≥ 0 für alle P ∉ S.

Definieren wir β = (β_{P}) ∈ A_{F} durch

β_{P} := \{ \begin{matrix}α_{P} & für P ∉ S, \\ 0 & für P ∈ S. \end{matrix}

Dann ist β ∈ A_{F} (W) und α = β + ∑_{P ∈S} ι_{P} (α_{P}), daher haben wir ω(β) = 0 und schließlich

ω(α) = ∑_{P ∈S} ω_{P} (α_{P}).

Für P ∉ S gilt, ι_{P} (α_{P}) ∈ A_{F} (W) und daher ω_{P} (α_{P}) = 0. □

Wir zeigen noch, dass ein Weil-Differential durch jede seiner lokalen Komponenten eindeutig bestimmt wird.

Satz 2.5.20

(a) Sei ω ≠ 0 ein Weil-Differential von F/K und P ∈ ℙ_{F}. Dann gilt

ν_{P} (ω) = max{r ∈ ℤ | ω_{P} (x) = 0 für alle x ∈ F mit ν_{P} (x) ≥ −r}.

Insbesondere ist ω_{P} ≠ 0.

(b) Falls ω, ω′ ∈ Ω_{F} gegeben sind und ω_{P} = ω′_{P} für ein P ∈ ℙ_{F} gilt, dann folgt ω = ω′.

Beweis. (a) Zur Erinnerung, es gilt laut Definition ν_{P} (ω) = ν_{P} (W), wobei W = (ω) den Divisor von ω bezeichnet. Sei s := ν_{P} (ω). Für x ∈ F mit ν_{P} (x) ≥ −s erhalten wir ι_{P} (x) ∈ A_{F} (W), daher gilt ω_{P} (x) = ω(ι_{P} (x)) = 0. Wir nehmen jetzt an, dass ω_{P} (x) = 0 ist, für jedes x ∈ F mit ν_{P} (x) ≥ −s−1. Sei α = (α_{Q})_{Q∈ℙ_{F}} ∈ A_{F} (W + P). Dann gilt

α = (α − ι_{P} (α_{P})) + ι_{P} (α_{P})

mit α − ι_{P} (α_{P}) ∈ A_{F} (W) und ν_{P} (α_{P}) ≥ −s − 1. Daher ist

ω(α) = ω(α − ι_{P} (α_{P})) + ω_{P} (α_{P}) = 0.

Aus diesem Grund verschwindet ω auf A_{F} (W + P), was ein Widerspruch zur Definition von W ist.

(b) Falls ω_{P} = ω′_{P} gilt, dann ist (ω−ω′)_{P} = 0, und daher nach (a) ω−ω′ = 0. □

2.6 Der Satz von Riemann-Roch und Anwendungen

In diesem Abschnitt wollen wir den Satz von Riemann-Roch zeigen, der wohl einer der wichtigsten Sätze in der Theorie der algebraischen Funktionenkörper ist. Der Schlüssel zu seinem Beweis liegt in der Betrachtung von Divisoren, die von Weil-Differentialen kommen.

Definition 2.6.1 Ein Divisor W heißt ein kanonischer Divisor von F/K, wenn W = (ω) für ein ω ∈ Ω_{F} ist.

Satz 2.6.2

(a) Für 0 ≠ x ∈ F und 0 ≠ ω ∈ Ω_{F} gilt: (xω) = (x) + (ω).

(b) Je zwei kanonische Divisoren von F/K sind äquivalent.

Beweis. Falls ω auf A_{F} (A) + F verschwindet, dann verschwindet xω nach Hilfssatz 2.5.14 auf A_{F} (A + (x)) + F, daher ist

(ω) + (x) ≤ (xω).

Genauso sieht man (xω) + (x^{−1}) ≤ (x^{−1}xω) = (ω). Die Kombination dieser beiden Unlgeichungen ergibt:

(ω) + (x) ≤ (xω) ≤ −(x^{−1}) + (ω) = (ω) + (x).

Das zeigt (a). Die Aussage (b) folgt aus (a) und aus Satz 2.5.15. □

Eine einfache Folgerung aus diesem Satz lautet: Die kanonischen Divisoren von F/K bilden eine ganze Klasse der Divisorenklassengruppe C_{F}. Diese Divisorenklasse nennt man die kanonische Klasse von F/K.

Der entscheidende Schritt zum Beweis des Satzes von Riemann-Roch ist der folgende Satz. Das wichtigste Resultat für den Beweis ist der Satz 2.5.15.

Satz 2.6.3 Sei A ein beliebiger Divisor, und W = (ω) ein kanonischer Divisor von F/K. Dann ist die Abbildung

μ : \{ \begin{matrix}L(W − A) & ⟶ & Ω_{F} (A), \\ x & ⟼ & xω \end{matrix}

ein Isomorphismus zwischen K-Vektorräumen. Insbesondere gilt:

i(A) = dim(W − A).

Beweis. Für x ∈ L(W − A) gilt

(xω) = (x) + (ω) ≥ −(W − A) + W = A,

daher ist nach (2.28) xω ∈ Ω_{F} (A). Die Abbildung μ bildet also L(W − A) in Ω_{F} (A) ab. Klarerweise ist μ linear und injektiv. Um zu zeigen, dass μ auch surjektiv ist, betrachten wir ein Weil-Differential ω_{1} ∈ Ω_{F} (A). Nach Satz 2.5.15 gilt w_{1} = xω für ein x ∈ F. Da

(x) + W = (x) + (ω) = (xω) = (ω_{1}) ≥ A,

ist, erhalten wir (x) ≥ −(W − A), daher ist x ∈ L(W − A) und ω_{1} = μ(x). Wir haben gezeigt, dass dim Ω_{F} (A) = dim(W − A) ist. Da nach Hilfssatz 2.5.11 dim Ω_{F} (A) = i(A) ist, folgt i(A) = dim(W − A). □

Die Zusammenfassung aller erhaltenen Resultate liefert den Satz von Riemann-Roch.

Satz 2.6.4 (Satz von Riemann-Roch) Sei W ein kanonischer Divisor von F/K. Dann gilt für jedes A ∈ D_{F}

dim A = deg A + 1 − g + dim(W − A).

Beweis. Unmittelbare Folgerung aus Satz 2.6.3 und der Definition 2.5.1 von i(A). □

Folgerung 2.6.5 Für einen kanonischen Divisor W gilt

deg W = 2g − 2 und dim W = g.

Beweis. Für A = 0 folgt aus dem Satz von Riemann-Roch 2.6.4 und Hilfssatz 2.4.10

1 = dim(0) = deg(0) + 1 − g + dim(W − 0).

Daher ist dim W = g. Wenn wir A = W setzen, erhalten wir

g = dim W = deg W + 1 − g + dim(W − W) = deg W + 2 − g.

Es folgt deg W = 2g − 2. □

Aus dem Satz von Riemann 2.4.20 wissen wir bereits, dass es eine Konstante c gibt, sodass i(A) = 0, wann immer deg A ≥ c gilt. Wir können nun eine genauere Beschreibung geben, wie diese Konstante zu wählen ist.

Satz 2.6.6 Wenn A ein Divisor von F/K vom Grad ≥ 2g − 1 ist, dann gilt

dim A = deg A + 1 − g.

Beweis. Wir wissen dim A = deg A + 1 − g + dim(W − A), wobei W ein kanonischer Divisor ist. Da deg A ≥ 2g − 1 und deg W = 2g − 2 gilt, folgt deg(W − A) < 0. Aus Folgerung 2.4.15 erhalten wir dim(W − A) = 0. □

Man beachte, dass die Schranke 2g − 1 im letzten Satz bestmöglich ist, da für einen kanonischen Divisor W nach Folgerung 2.6.5

dim W > deg W + 1 − g

gilt.

Wir können jetzt den Satz von Riemann-Roch 2.6.4 so formulieren, wie wir ihn später stets brauchen werden (wir werden trotzdem stets auf den Satz 2.6.4 verweisen): Für jeden Divisor A ∈ D_{F} gilt

dim A ≥ deg A + 1 − g,

mit Gleichheit, wenn deg A ≥ 2g − 1 ist.

Wir wollen jetzt noch einige Anwendungen des Satzes von Riemann-Roch 2.6.4 diskutieren. Unser erstes Ziel ist zu zeigen, dass wir mit Hilfe des Satzes von Riemann-Roch 2.6.4 sowohl das Geschlecht, als auch die kanonische Klasse von F/K charakterisieren können.

Satz 2.6.7 Angenommen g_{0} ∈ ℤ und W_{0} ∈ D_{F} erfüllen

dim A = deg A + 1 − g_{0} + dim(W_{0} − A)  (2.30)

für jedes A ∈ D_{F}. Dann ist g_{0} = g und W_{0} ein kanonischer Divisor.

Beweis. Indem wir A = 0 bzw. A = W_{0} in (2.30) setzen, erhalten wir so wie im Beweis von Folgerung 2.6.5 dim W_{0} = g_{0} und deg W_{0} = 2g_{0} − 2. Sei W ein kanonischer Divisor von F/K. Wir wählen einen Divisor A mit deg A > max{2g−2, 2g_{0}−2}. Dann ist nach Satz 2.6.6 dim A = deg A+1−g und nach (2.30) dim A = deg A + 1 − g_{0}. Daher gilt g = g_{0}. Wenn wir A = W in (2.30) substituieren, erhalten wir

g = (2g − 2) + 1 − g + dim(W_{0} − W).

Daher ist dim(W_{0} − W) = 1. Da deg(W_{0} − W) = 0 ist, folgt nach Hilfssatz 2.4.15 W_{0} − W ist ein Hauptdivisor, und daher gilt W_{0} ∼ W. □

Eine nützliche Charakterisierung der Klasse der kanonischen Divisoren ist die Folgende:

Satz 2.6.8 Ein Divisor B ist kanonisch, dann und nur dann, wenn deg B = 2g − 2 und dim B ≥ g ist.

Beweis. Man nehme an, dass deg B = 2g − 2 und dim B ≥ g ist, und wähle einen kanonischen Divisor W. Dann gilt

g ≤ dim B = deg B + 1 − g + dim(W − B) = g − 1 + dim(W − B).

Daher gilt dim(W −B) ≥ 1. Da deg(W −B) = 0 ist, impliziert die Folgerung 2.4.15 W ∼ B und damit die Behauptung. □

Die nächste Anwendung ist eine Verschärfung des schwachen Approximationssatzes 2.2.7.

Satz 2.6.9 (Starker Approximationssatz) Sei S ⊊ ℙ_{F} eine echte Teilmenge von ℙ_{F} und P_{1}, …, P_{r} ∈ S paarweise verschiedene Stellen von F/K. Es seien die Elemente x_{1}, …, x_{r} ∈ F und n_{1}, …, n_{r} ∈ ℤ gegeben. Dann gibt es ein Element x ∈ F, sodass

ν_{P_{i}}(x − x_{i}) = n_{i} (i = 1, …, r), und
ν_{P} (x) ≥ 0 für alle P ∈ S\{P_{1}, …, P_{r}}.

Beweis. Betrachte das Adèle α = (α_{P})_{P ∈ℙ_{F}} mit

α_{P} := \{ \begin{matrix}x_{i} & für P = P_{i}, i = 1, …, r, \\ 0 & sonst. \end{matrix}

Wähle eine Stelle Q ∈ ℙ_{F} \S. Für genügend großes m ∈ ℕ erhalten wir mit dem schwachen Satz von Riemann-Roch 2.5.7 in Kombination mit Satz 2.6.6

A_{F} = A_{F} (mQ − ∑_{i=1}^{r}(n_{i} + 1)P_{i}) + F.

Daher gibt es ein Element z ∈ F mit z − α ∈ A_{F} (mQ − ∑_{i=1}^{r}(n_{i} + 1)P_{i}). Das bedeutet

ν_{P_{i}}(z − x_{i}) > n_{i} für i = 1, …, r,  (2.31)
ν_{P} (z) ≥ 0 für P ∈ S\{P_{1}, …, P_{r}}.  (2.32)

Wir wählen jetzt y_{1}, …, y_{r} ∈ F mit ν_{P_{i}}(y_{i}) = n_{i}. In derselben Weise wie oben, konstruieren wir ein y ∈ F mit

ν_{P_{i}}(y − y_{i}) > n_{i} für i = 1, …, r,  (2.33)
ν_{P} (y) ≥ 0 für P ∈ S\{P_{1}, …, P_{r}}.  (2.34)

Wir haben also für i = 1, …, r

ν_{P_{i}}(y) = ν_{P_{i}}((y − y_{i}) + y_{i}) = n_{i}  (2.35)

aufgrund (2.33) und der strikten Dreiecksungleichung 2.2.2. Setzen wir x := y + z, dann erhalten wir mit (2.35)

ν_{P_{i}}(x − x_{i}) = ν_{P_{i}}(y + (z − x_{i})) = n_{i} (i = 1, …, r).

Für P ∈ S\{P_{1}, …, P_{r}} gilt nach (2.32) und (2.34) ν_{P} (x) = ν_{P} (y+z) ≥ 0. □

Als Beispiel berechnen wir einen kanonischen Divisor im rationalen Funktionenkörper K(x).

Satz 2.6.10 Für den rationalen Funktionenkörper F = K(x) gelten die folgenden Aussagen:

(a) Der Divisor −2P_{∞} ist kanonisch.

(b) Es gibt ein eindeutiges Weil-Differential η ∈ Ω_{K(x)} mit (η) = −2P_{∞} und η_{P_{∞}}(x^{−1}) = −1.

(c) Die lokalen Komponenten η_{P_{∞}} bzw. η_{P_{a}} des obigen Weil-Differentials η erfüllen:

η_{P_{∞}}((x − a)^{n}) = \{ \begin{matrix}0 & für n ≠ −1, \\ −1 & für n = −1, \end{matrix}

η_{P_{a}}((x − a)^{n}) = \{ \begin{matrix}0 & für n ≠ −1, \\ 1 & für n = −1. \end{matrix}

Beweis. (a) deg(−2P_{∞}) = −2 = 2g − 2 < 0, daher ist dim(−2P_{∞}) = 0 = g, und damit ist −2P_{∞} nach Satz 2.6.8 kanonisch.

(b) Wähle ein Weil-Differential ω mit Divisor (ω) = −2P_{∞}. Dann verschwindet ω auf dem Raum A_{K(x)}(−2P_{∞}) und ω verschwindet nicht identisch auf A_{K(x)}(−P_{∞}). Nach Hilfssatz 2.5.4 ist

dim A_{K(x)}(−P_{∞})/A_{K(x)}(−2P_{∞}) = 1.

Außerdem gilt

ι_{P_{∞}}(x^{−1}) ∈ A_{K(x)}(−P_{∞})\A_{K(x)}(−2P_{∞}).

Mit den letzten beiden Formeln können wir schließen, dass

ω_{P_{∞}}(x^{−1}) = ω(ι_{P_{∞}}(x^{−1})) =: c ≠ 0.

Wir setzen η := c^{−1}ω und erhalten (η) = −2P_{∞} und η_{P_{∞}}(x^{−1}) = −1. Die Eindeutigkeit von η erhalten wir folgendermaßen: Falls η^{∗} dieselben Eigenschaften wie η hat, dann verschwindet η−η^{∗} auf dem Raum A_{K(x)}(−P_{∞}). Wegen deg −P_{∞} = −1 = 2g − 1 folgt aus Satz 2.6.6 und Hilfssatz 2.5.6 A_{K(x)}(−P_{∞}) + K(x) = A_{K(x)}. Dies hat η − η^{∗} = 0 zur Folge.

(c) Da Weil-Differentiale auf Hauptadèlen verschwinden, gilt nach Satz 2.5.19

0 = η((x − a)^{n}) = ∑_{P ∈ℙ_{K(x)}} η_{P} ((x − a)^{n}).  (2.36)

Für P ≠ P_{∞} und P ≠ P_{a} ist ν_{P} ((x − a)^{n}) = 0, daher folgt nach Satz 2.5.20 η_{P} ((x − a)^{n}) = 0 und (2.36) impliziert

η_{P_{∞}}((x − a)^{n}) + η_{P_{a}}((x − a)^{n}) = 0.  (2.37)

Im Fall n ≤ −2, erhalten wir ν_{P_{∞}}((x − a)^{n}) ≥ 2 = −ν_{P_{∞}}(η), daher ist nach Satz 2.5.20 η_{P_{∞}}((x − a)^{n}) = 0 und (2.37) hat zur Folge, dass auch η_{P_{a}}((x − a)^{n}) = 0 ist. Im Fall n ≥ 0, gilt nach Satz 2.5.20 η_{P_{a}}((x − a)^{n}) = 0 = −ν_{P_{a}}(η) und wir erhalten das Ergebnis für η_{P_{∞}}((x − a)^{n}) wieder durch (2.37). Zum Schluss betrachten wir den Fall n = −1. Da

\frac{1}{x − a} = \frac{a}{x(x − a)} + \frac{1}{x} und ι_{P_{∞}} (\frac{a}{x(x − a)}) ∈ A_{K(x)}(−2P_{∞}),

sehen wir, dass η_{P_{∞}}((x − a)^{−1}) = η_{P_{∞}}(x^{−1}) = −1 nach Definition von η gilt und aus (2.37) folgt, dass η_{P_{a}}((x − a)^{−1}) = 1 ist. □

Für einen Divisor A mit Grad < 0 gilt dim A = 0 nach Hilfssatz 2.4.10. Andererseits gilt nach Satz 2.6.6, dass dim A = deg A + 1 − g ist, falls deg A > 2g − 2. Die Dimension von A hängt in diesen Fällen also nur von deg A (und dem Geschlecht) ab. Im Fall 0 ≤ deg A ≤ 2g−2, ist die Situation komplizierter, aber trotzdem kann man allgemeine Resultate ableiten. Wir führen zunächst eine Bezeichnung für Divisoren mit Spezialitätsindex 0 ein.

Definition 2.6.11 Ein Divisor A ∈ D_{F} heißt nicht speziell, wenn i(A) = 0 ist, und sonst wird A speziell genannt.

Wir sammeln einige Eigenschaften, die sofort aus dieser Definition folgen:

Hilfssatz 2.6.12 Sei A ∈ ℙ_{F}.

(a) A ist nicht speziell ⟺ dim A = deg A + 1 − g.

(b) deg A > 2g − 2 ⇒ A ist nicht speziell.

(c) Die Eigenschaft eines Divisors A speziell oder nicht speziell zu sein, hängt nur von der Klasse [A] von A in der Divisorklassengruppe ab.

(d) Kanonische Divisoren sind speziell.

(e) Jeder Divisor A mit dim A > 0 und deg A < g ist speziell.

(f) Falls A nicht speziell ist und B ≥ A, dann ist auch B nicht speziell.

Beweis. (a) ist klar aufgrund der Definition von i(A), (b) ist Satz 2.6.6 und (c) folgt aus der Tatsache, dass dim A und deg A nur von der Divisorklasse [A] abhängen.

(d) Für einen kanonischen Divisor W haben wir i(W) = dim(W − W) = 1 nach Satz 2.6.3, daher ist W speziell.

(e) 1 ≤ dim A = deg A + 1 − g + i(A) ⇒ i(A) ≥ g − deg A > 0, da deg A < g ist. Daher ist A speziell.

(f) Nach dem schwachen Satz von Riemann-Roch 2.5.7 ist A nicht speziell ⇔ A_{F} = A_{F} (A) + F. Falls B ≥ A, dann ist A_{F} (A) ⊆ A_{F} (B) nach Hilfssatz 2.5.4 und daher folgt die Aussage. □

Satz 2.6.13 Angenommen T ⊆ ℙ_{F} sei eine Menge von Stellen vom Grad eins, sodass |T | ≥ g. Dann gibt es einen nicht speziellen Divisor B ≥ 0 mit deg B = g und supp B ⊆ T.

Beweis. Der wesentliche Schritt im Beweis besteht darin, die folgende Behauptung zu zeigen:

Gegeben seien g verschiedene Stellen P_{1}, …, P_{g} ∈ T und ein Divisor A ≥ 0 mit dim A = 1 und deg A ≤ g − 1. Dann gibt es einen Index j ∈ {1, …, g}, sodass dim(A + P_{j}) = 1 ist.

Angenommen diese Behauptung sei falsch. Dann ist dim(A + P_{j}) > 1 und es gibt Elemente z_{j} ∈ L(A + P_{j})\L(A) für j = 1, …, g. Da

ν_{P_{j}}(z_{j}) = −ν_{P_{j}}(A) − 1 und ν_{P_{i}}(z_{j}) ≥ −ν_{P_{i}}(A) für i ≠ j,

folgt mit der strikten Dreiecksungleichung 2.2.2, dass die g + 1 Elemente 1, z_{1}, …, z_{g} linear unabhängig über K sind. Wähle einen Divisor D ≥ A + P_{1} + ⋯ + P_{g} mit deg D = 2g − 1. Dann sind 1, z_{1}, …, z_{g} ∈ L(D), daher ist dim D ≥ g + 1. Andererseits ist dim D = deg D + 1 − g = g nach dem Satz von Riemann-Roch 2.6.4. Das ist ein Widerspruch. Aufgrund dieser Behauptung finden wir Divisoren 0 < P_{i_{1}} < P_{i_{1}} + P_{i_{2}} < … < P_{i_{1}} + P_{i_{2}} + ⋯ + P_{i_{g}} =: B (mit i_{ν} ∈ {1, …, g}), sodass dim(P_{i_{1}} + ⋯ + P_{i_{j}}) = 1 ist für j = 1, …, g. Insbesondere ist daher dim B = 1. Der Divisor B ist nicht speziell, da

deg B + 1 − g = g + 1 − g = 1 = dim B

aufgrund Hilfssatz 2.6.12 (a). □

Das einzige Beispiel eines algebraischen Funktionenkörpers, das wir kennengelernt haben, ist der rationale Funktionenkörper, und der ist aus algebraischer Sicht ein Trivialbeispiel. Häufig hat ein nicht rationaler Funktionenkörper F/K für ein irreduzibles Polynom φ(T) ∈ K(x)[T] eine Darstellung der Form

F = K(x, y) mit φ(y) = 0.

Damit kann F als eine endliche algebraische Erweiterung des rationalen Funktionenkörpers K(x) aufgefasst werden. Viele Probleme liegen dabei auf der Hand:

• Ist K der volle Konstantenkörper von F?

• Berechne das Geschlecht von F.

• Beschreibe die Stellen von F explizit. Wie sehen insbesondere die rationalen Stellen aus?

• Konstruiere eine Basis des Raumes L(G), zumindest in Spezialfällen.

Diese Probleme zu beantworten ist das Hauptziel der Theorie der algebraischen Funktionenkörper. Wir werden uns damit hier nicht beschäftigen. Eine ausführliche Behandlung dieser Probleme findet man in [19] und [18].

2.7 Die P -adische Vervollständigung

In diesem Kapitel wollen wir einen bewertungstheoretischen Aspekt ins Spiel bringen. Wir werden die Vervollständigung eines Funktionenkörpers F/K bezüglich einer Stelle P ∈ ℙ_{F} betrachten. Zunächst verallgemeinern wir Definition 2.2.1 auf einen beliebigen Körper.

Definition 2.7.1 Eine diskrete Bewertung eines Körper T ist eine surjektive Abbildung ν : T ⟶ ℤ ∪ {∞}, die folgende Bedingungen erfüllt:

(1) ν(x) = ∞ ⟺ x = 0.

(2) ν(xy) = ν(x) + ν(y) für alle x, y ∈ T.

(3) ν(x + y) ≥ min{ν(x), ν(y)} für alle x, y ∈ T (Dreiecksungleichung). Das Paar (T, ν) nennt man einen bewerteten Körper.

Wie in Hilfssatz 2.2.2 kann man leicht zeigen, dass die strikte Dreiecksungleichung

ν(x + y) = min{ν(x), ν(y)} falls x, y ∈ T und ν(x) ≠ ν(y)

auch hier gilt.

Definition 2.7.2 Sei (T, ν) ein bewerteter Körper. Wir sagen, die Folge (x_{n})_{n≥0} konvergiert in T, falls ein Element x ∈ T (genannt der Grenzwert der Folge) existiert, mit

∀c ∈ ℝ ∃n_{0} ∈ ℕ : ν(x − x_{n}) ≥ c ∀n ≥ n_{0}.

Eine Folge (x_{n})_{n≥0} heißt eine Cauchy Folge, wenn sie die folgende Eigenschaft hat:

∀c ∈ ℝ ∃n_{0} ∈ ℕ : ν(x_{n} − x_{m}) ≥ c ∀n, m ≥ n_{0}.

Wie in der reellen Analysis zeigt man:

(a) Sei (x_{n})_{n≥0} eine konvergente Folge in T. Dann ist sein Grenzwert x ∈ T eindeutig bestimmt. Daher schreiben wir: x = lim_{n→∞} x_{n}.

(b) Jede konvergente Folge ist eine Cauchy Folge.

Bekanntlich gilt im Allgemeinen die Umkehrung der letzten Aussage nicht. Wir führen die folgende Notation ein.

Definition 2.7.3

(a) Ein bewerteter Körper (T, ν) heißt vollständig, wenn jede Cauchy Folge in T konvergent ist.

(b) Sei (T, ν) ein bewerteter Köper. Die Vervollständigung von T ist ein bewerteter Körper (T̂, ν̂) mit den folgenden Eigenschaften:

(1) T ⊆ T̂ und ν ist die Einschränkung von ν̂ auf T.

(2) (T̂, ν̂) ist vollständig.

(3) T ist dicht in T̂, das heißt für jedes z ∈ T̂ gibt es eine Folge (x_{n})_{n≥0} in T mit lim_{n→∞} x_{n} = z.

Ohne Beweis führen wir den folgenden Satz an:

Satz 2.7.4 (Vervollständigungssatz) Für jeden bewerteten Körper (T, ν) gibt es eine Vervollständigung (T̂, ν̂). Sie ist eindeutig im folgenden Sinne: Falls (T̃, ν̃) eine andere Vervollständigung von (T, ν) ist, dann gibt es einen eindeutigen Isomorphismus f : T̂ → T̃, sodass ν̂ = ν̃ ∘ f. Daher nennen wir (T̂, ν̂) die Vervollständigung von (T, ν).

Beweis. Einen Beweis findet man z. B. in [19]. □

Häufig ist es zweckmäßiger konvergente Reihen anstatt Folgen zu betrachten. Sei (z_{n})_{n≥0} eine Folge in einem bewerteten Körper (T, ν) und s_{m} := ∑_{i=0}^{m} z_{i}. Wir sagen, die unendliche Reihe ∑_{i=0}^{∞} z_{i} ist konvergent, wenn die Folge der Paritalsummen (s_{m})_{m≥0} konvergiert. In diesem Fall schreiben wir, wie üblich,

∑_{i=0}^{∞} z_{i} := lim_{m→∞} s_{m}.

In einem vollständigen bewerteten Körper gibt es ein sehr einfaches Kriterium für die Konvergenz einer unendlichen Reihe.

Hilfssatz 2.7.5 Sei (z_{n})_{n≥0} eine Folge in einem vollständigen, bewerteten Körper (T, ν). Dann gilt: Die unendliche Reihe ∑_{i=0}^{∞} z_{i} ist konvergent, dann und nur dann, wenn die Folge (z_{n})_{n≥0} gegen 0 konvergiert.

Beweis. Angenommen (z_{n})_{n≥0} konvergiert gegen 0. Betrachte die m-te Parialsumme s_{m} := ∑_{i=0}^{m} z_{i}. Für n > m ist

ν(s_{n} − s_{m}) = ν ( ∑_{i=m+1}^{n} z_{i}) ≥ min{ν(z_{i}) | m < i ≤ n} ≥ min{ν(z_{i}) | i > m}.

ν(z_{i}) → ∞ für i → ∞ impliziert, dass die Folge (s_{n})_{n≥0} eine Cauchy Folge in T und damit konvergent ist. Die umgekehrte Richtung zeigt man genauso wie in der Analysis. □

Wir spezialisieren diese Resultate jetzt auf den Fall eines algebraischen Funktionenkörpers F/K.

Definition 2.7.6 Sei P eine Stelle von F/K. Die Vervollständigung von F bezüglich der Bewertung ν_{P} nennen wir die P -adische Vervollständigung von F. Wir bezeichnen diese Vervollständigung mit F̂_{P} und die Bewertung von F̂_{P} wieder mit ν_{P}.

Es gilt jetzt der folgende Satz.

Satz 2.7.7 Sei P ∈ ℙ_{F} eine rationale Stelle und t ∈ F ein P -primes Element. Dann hat jedes Element z ∈ F̂_{P} eine eindeutige Darstellung der Form

z = ∑_{i=n}^{∞} a_{i}t^{i} mit ν_{P} (z) ≥ n ∈ ℤ und a_{i} ∈ K.  (2.38)

Diese Darstellung heißt die P -adische Potenzreihe von z bezüglich t.

Umgekehrt gilt: Sei (c_{i})_{i≥n}, n ∈ ℤ eine Folge in K, dann ist die Reihe ∑_{i=n}^{∞} c_{i}t^{i} in F̂_{P} konvergent, und es gilt

ν_{P} (∑_{i=n}^{∞} c_{i}t^{i}) = min{i | c_{i} ≠ 0}.

Beweis. Zunächst beweisen wir die Existenz einer Darstellung der Form (2.38). Sei also z ∈ F̂_{P} gegeben. Wir wählen ein n ∈ ℤ mit n ≤ ν_{P} (z). Da F in F̂_{P} dicht ist, gibt es ein Element y ∈ F mit ν_{P} (z − y) > n. Aufgrund der Dreiecksungleichung gilt ν_{P} (y) ≥ n und daher ν_{P} (yt^{−n}) ≥ 0. Da P eine rationale Stelle ist, gibt es ein Element a_{n} ∈ K mit ν_{P} (yt^{−n}−a_{n}) > 0, und

ν_{P} (z − a_{n}t^{n}) = ν_{P} ((z − y) + (y − a_{n}t^{n})) > n.

Genauso finden wir ein a_{n+1} ∈ K mit

ν_{P} (z − a_{n}t^{n} − a_{n+1}t^{n+1}) > n + 1.

Wenn wir diese Konstruktion iterieren, erhalten wir eine unendliche Folge a_{n}, a_{n+1}, a_{n+2}, … in K, sodass

ν_{P} (z − ∑_{i=n}^{m} a_{i}t^{i}) > m

für alle m ≥ n. Das zeigt, dass

z = ∑_{i=n}^{∞} a_{i}t^{i}

gilt. Um die Eindeutigkeit dieser Darstellung zu zeigen, betrachten wir eine andere Folge (b_{i})_{i≥m} in K, welche folgende Bedingung erfüllt:

z = ∑_{i=n}^{∞} a_{i}t^{i} = ∑_{i=m}^{∞} b_{i}t^{i}.

Wir können n = m annehmen, denn wenn n < m ist, definieren wir b_{i} := 0 für alle n ≤ i < m. Angenommen es gibt ein j mit a_{j} ≠ b_{j}. Dann wählen wir ein minimales j mit dieser Eigenschaft und erhalten für alle k > j

ν_{P} (∑_{i=n}^{k} a_{i}t^{i} − ∑_{i=n}^{k} b_{i}t^{i}) = ν_{P} ((a_{j} − b_{j})t^{j} + ∑_{i=j+1}^{k}(a_{i} − b_{i})t^{i}) = j. (2.39)

Die letzte Gleichheit gilt, da ν_{P} ((a_{j} − b_{j})t^{j}) = j, und damit ist die strikte Dreiecksungleichung 2.2.2 anwendbar. Andererseits gilt

ν_{P} (∑_{i=n}^{k} a_{i}t^{i} − ∑_{i=n}^{k} b_{i}t^{i}) = ν_{P} (∑_{i=n}^{k} a_{i}t^{i} − z + z − ∑_{i=n}^{k} b_{i}t^{i})

≥ min {ν_{P} (z − ∑_{i=n}^{k} a_{i}t^{i}) , ν_{P} (z − ∑_{i=n}^{k} b_{i}t^{i})} .  (2.40)

Für k → ∞, strebt (2.40) gegen unendlich. Das ist ein Widerspruch zu (2.39) und zeigt, dass die Darstellung (2.38) eindeutig ist. Um die letzte Aussage des Satzes zu zeigen, betrachten wir eine beliebige Folge (c_{i})_{i≥n}, n ∈ ℤ in K. Da ν_{P} (c_{i}t^{i}) ≥ i für alle i gilt, strebt die Folge (c_{i}t^{i})_{i≥n} gegen 0. Daher konvergiert nach Hilfssatz 2.7.5 die Reihe ∑_{i=n}^{∞} c_{i}t^{i} in F̂_{P}, wir definieren:

∑_{i=n}^{∞} c_{i}t^{i} =: y ∈ F̂_{P} .

Setze j_{0} := min{i | c_{i} ≠ 0}. Im Fall j_{0} = ∞ sind alle c_{i} = 0 und daher ist hier y = 0 und ν_{P} (y) = ∞. Im Fall j_{0} < ∞, gilt nach der strikten Dreiecksungleichung 2.2.2 für alle k ≥ j_{0}

ν_{P} (∑_{i=n}^{k} c_{i}t^{i}) = j_{0}.

Da für genügend großes k

ν_{P} (y − ∑_{i=n}^{k} c_{i}t^{i}) > j_{0}

ist, folgt

ν_{P} (y) = ν_{P} (y − ∑_{i=n}^{k} c_{i}t^{i} + ∑_{i=n}^{k} c_{i}t^{i})

= min {ν_{P} (y − ∑_{i=n}^{k} c_{i}t^{i}) , ν_{P} (∑_{i=n}^{k} c_{i}t^{i})} = j_{0},

und damit die Behauptung. □

Wie man aus dem Beweis des letzten Satzes sieht, läßt sich die P -adische Potenzreihenentwicklung sofort folgendermaßen verallgemeinern:

Satz 2.7.8 Es sei P ∈ ℙ_{F} eine rationale Stelle und (t_{r})_{r∈ℤ} eine Folge von Elementen in F mit ν_{P} (t_{r}) = r für alle r ∈ ℤ. Dann besitzt jedes Element z ∈ F̂_{P} eine eindeutige Darstellung der Form

z = ∑_{i=n}^{∞} a_{i}t_{i} mit ν_{P} (z) ≥ n ∈ ℤ und a_{i} ∈ K.

Diese Darstellung nennen wir die P -adische Potenzreihe von z bezüglich der Folge (t_{r})_{r∈ℤ}.

Beweis. Der Beweis läuft genauso wie in Satz 2.7.7. □

2.8 Die Hasse-Weil-Schranke

In den letzten Abschnitten haben wir die Theorie der algebraischen Funktionenkörper über einem beliebigen Körper entwickelt. Im Hinblick auf die codierungstheoretischen Anwendungen wollen wir den Fall eines endlichen Konstantenkörpers genauer beleuchten. Deshalb setzen wir ab jetzt und für alles weitere voraus:

F/𝔽_{q} sei ein algebraischer Funktionenkörper mit Geschlecht g, dessen Konstantenkörper der endliche Körper 𝔽_{q} ist.

Besonders sind wir an rationalen Stellen, also an Stellen deren Grad eins ist, interessiert. Ihre Anzahl ist endlich und kann durch die Hasse-Weil-Schranke abgeschätzt werden. Diese Schranke spielt eine wesentliche Rolle bei den Anwendungen der algebraischen Funktionenkörper in der Codierungstheorie. Da die Beweise der in diesem Abschnitt vorkommenden Sätze ein wesentlich tieferes Verständnis der Theorie der algebraischen Funktionenkörper verlangen, als wir entwickeln konnten, sollen sie in diesem Kapitel gänzlich entfallen. Eine vollständige Darstellung dieser Theorie findet man in [19].

Wir wollen im Folgenden die Zahl

A_{n} := |{A ∈ D_{F} | A ≥ 0 und deg A = n}|  (2.41)

untersuchen. Diese Zahl ist stets endlich. Zum Beispiel ist A_{0} = 1 und A_{1} die Anzahl der rationalen Stellen P ∈ ℙ_{F}. Wir codieren diese Information in die folgende Potenzreihe:

Definition 2.8.1 Die Potenzreihe

Z(t) := Z_{F} (t) := ∑_{n=0}^{∞} A_{n}t^{n} ∈ ℂ[[t]]

heißt die Zetafunktion von F/𝔽_{q}.

Man beachte, dass t hier als komplexe Variable und Z(t) als Potenzreihe über ℂ aufgefasst wird, und nicht etwa eine P -adische Potenzreihe ist, wie sie im vorigen Kapitel betrachtet wurde. Diese Potenzreihe konvergiert in einer Umgebung von 0:

Satz 2.8.2 Die Potenzreihe Z(t) = ∑_{n=0}^{∞} A_{n}t^{n} konvergiert für |t| < q^{−1}.

Satz 2.8.3 Z(t) kann zu einer rationalen Funktion, die genau bei t = q^{−1} und bei t = 1 einfache Pole besitzt, fortgesetzt werden.

Als nächstes definieren wir:

Definition 2.8.4 Das Polynom L(t) := L_{F} (t) := (1 − t)(1 − qt)Z(t) nennt man L-Polynom von F/𝔽_{q}.

Man beachte, dass L(t) die ganze Information über die Zahlen A_{n} (n ≥ 0) beinhaltet, da

L(t) = (1 − t)(1 − qt) ∑_{n=0}^{∞} A_{n}t^{n}

gilt. Die Eigenschaften von L(t) sind im folgenden Satz zusammengefasst:

Satz 2.8.5

(a) L(t) ∈ ℤ[t] und deg L(t) = 2g.

(b) Sei L(t) = a_{0} + a_{1}t + ⋯ + a_{2g}t^{2g}. Dann gilt:

(1) a_{0} = 1 und a_{2g} = q^{g}.

(2) a_{2g−i} = q^{g−i}a_{i} für 0 ≤ i ≤ g.

(3) a_{1} = N − (q + 1), wobei N die Anzahl der rationalen Stellen P ∈ ℙ_{F} bezeichnet.

(c) L(t) faktorisiert über ℂ[t] in

L(t) = ∏_{i=1}^{2g}(1 − α_{i}t).

Die komplexen Zahlen α_{1}, …, α_{2g} können in einer Weise angeordnet werden, sodass α_{i}α_{g+i} = q für i = 1, …, g gilt.

Der letzte Satz zeigt, dass die Zahl

N(F) := N = |{P ∈ ℙ_{F} | deg P = 1}|

sehr einfach mit Hilfe des L-Polynomes L(t) von F/𝔽_{q} berechnet werden kann.

Folgerung 2.8.6 Für N(F) gilt:

N(F) = q + 1 − ∑_{i=1}^{2g} α_{i}.

Das Hauptresultat zum Beweis der Hasse-Weil-Schranke ist der folgende Satz:

Satz 2.8.7 (Satz von Hasse-Weil) Für die Reziprokwerte der Nullstellen von L_{F} (t) gilt:

|α_{i}| = q^{1/2} für i = 1, …, 2g.

Der Satz von Hasse-Weil 2.8.7 wird auch oft die Riemann’sche Vermutung für algebraische Funktionenkörper genannt. Diese Notation wollen wir kurz erläutern:

Man kann die Zetafunktion Z_{F} (t) als ein Analogon zur klassischen Riemann’schen ζ-Funktion

ζ(s) := ∑_{n=1}^{∞} n^{−s}  (2.42)

(wobei s ∈ ℂ und Re(s) > 1 ist) auffassen. Definiere die absolute Norm eines Divisors A ∈ D_{F} durch

N (A) := q^{degA}.

Die absolute Norm N (P) eines Primdivisors P ∈ ℙ_{F} ist zum Beispiel die Kardinalität seines Restklassenkörpers F_{P}. Dann kann die Funktion

ζ_{F} (s) := Z_{F} (q^{−s})

in der Form

ζ_{F} (s) = ∑_{n=0}^{∞} A_{n}q^{−sn} = ∑_{A∈D_{F} ,A≥0} N (A)^{−s}

geschrieben werden, was ein geeignetes Analogon zu (2.42) darstellt. Es ist eine wohl bekannte Tatsache (siehe z.B. [20]), dass die Riemann’sche ζ-Funktion (2.42) eine analytische Fortsetzung zu einer meromorphen Funktion auf ℂ besitzt. Die klassische Riemann’sche Vermutung (eines der wichtigsten ungelösten Probleme) besagt, dass - abgesehen von den sogenannten trivialen Nullstellen s = −2, −4, −6, … - alle Nullstellen von ζ(s) auf der Geraden Re(s) = 1/2 liegen.

Der Satz von Hasse-Weil 2.8.7 impliziert, dass

ζ_{F} (s) = 0 ⇒ Z_{F} (q^{−s}) = 0 ⇒ |q^{−s}| = q^{−1/2}

gilt. Da |q^{−s}| = q^{−Re(s)} ist, bedeutet die vorige Implikation Folgendes:

ζ_{F} (s) = 0 ⇒ Re(s) = 1/2.

Deshalb kann der Satz von Hasse-Weil 2.8.7 als Analogon zur klassischen Riemann’schen Vermutung aufgefasst werden.

Als direkte Folgerung aus dem Satz von Hasse-Weil 2.8.7 erhalten wir den nachstehenden Satz:

Satz 2.8.8 (Hasse-Weil-Schranke) Die Zahl N = N(F) der rationalen Stellen von F/𝔽_{q} kann durch

|N − (q + 1)| ≤ 2gq^{1/2}

abgeschätzt werden.

Beweis. Aus Folgerung 2.8.6 erhalten wir

N − (q + 1) = − ∑_{i=1}^{2g} α_{i}.

Daher ist die Hasse-Weil-Schranke eine sofortige Folgerung aus dem Satz von Hasse-Weil 2.8.7. □

Die Hasse-Weil-Schranke ist scharf, man kann Beispiele für Funktionenkörper F/𝔽_{q} angeben, wo sie angenommen wird. Mit ihrer Hilfe können auch Abschätzungen für die Anzahl der Stellen von festem Grad r

B_{r} := B_{r}(F) := |{P ∈ ℙ_{F} | deg P = r}|

angegeben werden. Solche Untersuchungen findet man zum Beispiel in [19].

Geometrische Goppa-Codes

In diesem Kapitel wollen wir Linearcodes betrachten, die Goppa um 1981 basierend auf algebraischen Funktionenkörper F/𝔽_{q} konstruiert hat. Heute nennt man diese Codes algebraisch-geometrische Codes (kurz AG-Codes) oder geometrische Goppa-Codes.

In Goppas Konstruktion wählt man einen Divisor G und n rationale Stellen. Dann bildet die Auswertung der Funktionen von L(G) an diesen rationalen Stellen einen Code der Länge n. Goppa hat zwei duale Klassen von Codes definiert. Diese beiden Klassen sind aber verschiedene Beschreibungen für dieselben Codes. Später werden wir eine weitere äquivalente Methode kennenlernen, geometrische Goppa-Codes zu konstruieren. Diese ist erst kürzlich entdeckt worden und zeigt ganz neue Perspektiven von AG-Codes auf.

3.1 Konstruktion nach Goppa

Wir wollen einige Notationen für diesen Abschnitt festhalten:

F/𝔽_{q} sei ein algebraischer Funktionenkörper mit Geschlecht g. P_{1}, …, P_{n} seien paarweise verschiedene rationale Stellen von F/𝔽_{q}. D = P_{1} + ⋯ + P_{n}. G sei ein Divisor von F/𝔽_{q} mit supp G ∩ supp D = ∅.

Dann definieren wir:

Definition 3.1.1 Der geometrische Goppa-Code (oder algebraisch-geome-trische Code) C_{L}(D, G) assoziiert mit den Divisoren D und G ist definiert durch

C_{L}(D, G) := {(x(P_{1}), …, x(P_{n})) | x ∈ L(G)} ⊆ 𝔽_{q}^{n}.

Man beachte, dass diese Definition aus folgendem Grund sinvoll ist: für x ∈ L(G) gilt ν_{P_{i}}(x) ≥ 0 (i = 1, …, n), da supp G ∩ supp D = ∅ ist. Die Restklasse x(P_{i}) von x modulo P_{i} ist ein Element des Restklassenkörpers von P_{i}. Wegen deg P_{i} = 1, ist der Restklassenkörper der Körper 𝔽_{q}, daher gilt x(P_{i}) ∈ 𝔽_{q}.

Wir können die Auswertungsabbildung ev_{D} : L(G) → 𝔽_{q}^{n} betrachten, die gegeben ist durch

ev_{D}(x) := (x(P_{1}), …, x(P_{n})) ∈ 𝔽_{q}^{n}.  (3.1)

Die Auswertungsabbildung ist 𝔽_{q}-linear und C_{L}(D, G) ist das Bild von L(G) unter dieser Abbildung.

Tatsächlich stellt Definition 3.1.1 eine komplizierte Möglichkeit dar, einen speziellen Unterraum von 𝔽_{q}^{n} zu definieren. Der nächste Satz zeigt, warum diese Codes interessant sind. Mit Hilfe des Satzes von Riemann-Roch 2.6.4 kann man nämlich die Paramter k und d dieses Codes berechnen oder zumindest abschätzen.

Satz 3.1.2 C_{L}(D, G) ist ein [n, k, d]-Code mit den Parametern

k = dim G − dim(G − D) und d ≥ n − deg G.

Beweis. Die Auswertungsabbildung (3.1) ist eine surjektive lineare Abbildung von L(G) nach C_{L}(D, G) mit dem Kern

ker(ev_{D}) = {x ∈ L(G) | ν_{P_{i}}(x) > 0 für i = 1, …, n} = L(G − D).

Es folgt, dass k = dim C_{L}(D, G) = dim L(G)−dim L(G−D) ist. Die Behauptung über die Minimaldistanz d macht nur dann Sinn, wenn C_{L}(D, G) ≠ {0} gilt, daher nehmen wir das an. Wähle x ∈ L(G) mit wt(ev_{D}(x)) = d. Dann sind genau n − d Stellen P_{i_{1}}, …, P_{i_{n−d}} im Träger von D Nullstellen von x, daher ist

0 ≠ x ∈ L(G − (P_{i_{1}} + ⋯ + P_{i_{n−d}})).

Nach Folgerung 2.4.15 (b) können wir schließen, dass

0 ≤ deg(G − (P_{i_{1}} + ⋯ + P_{i_{n−d}})) = deg G − n + d

gilt. Daher ist d ≥ n − deg G. □

Folgerung 3.1.3 Angenommen, der Grad von G sei echt kleiner als n.

Dann ist die Auswertungsabbildung ev_{D} : L(G) → C_{L}(D, G) injektiv und es gilt:

(a) C_{L}(D, G) ist ein [n, k, d]-Code mit

d ≥ n − deg G und k = dim G ≥ deg G + 1 − g.

Daher gilt

k + d ≥ n + 1 − g.  (3.2)

(b) Falls zusätzlich 2g − 2 < deg G < n gilt, dann ist k = deg G + 1 − g.

(c) Falls {x_{1}, …, x_{k}} eine Basis von L(G) ist, dann ist die Matrix

M = ( \begin{matrix}x_{1}(P_{1}) & x_{1}(P_{2}) & ⋯ & x_{1}(P_{n}) \\ ⋮ & ⋮ & & ⋮ \\ x_{k}(P_{1}) & x_{k}(P_{2}) & ⋯ & x_{k}(P_{n}) \end{matrix} )

eine Generatormatrix für C_{L}(D, G).

Beweis. Nach Annahme sei deg(G−D) = deg G−n < 0, daher ist L(G−D) = 0. Da L(G − D) den Kern der Auswertungsabbildung bildet, ist diese Abbildung injektiv. Die verbleibenden Aussagen sind triviale Folgerungen aus Satz 3.1.2 und dem Satz von Riemann-Roch 2.6.4. □

Man beachte, dass die untere Schranke für die Minimaldistanz (3.2), einer oberen Schranke, nämlich der Singelton-Schranke 1.5.4, sehr ähnlich ist. Wenn wir diese beiden Schranken zusammensetzen, erhalten wir für deg G < n

n + 1 − g ≤ k + d ≤ n + 1.  (3.3)

Falls das Geschlecht g des Funktionenkörpers F gleich 0 ist, dann gilt k + d = n + 1. Daher sind geometrische Goppa-Codes, die über dem rationalen Funktionenkörper 𝔽_{q}(z) konstruiert werden, nach Satz 2.4.21 im Fall deg G < n stets MDS-Codes.

Um eine sinnvolle Schranke für die Minimaldistanz von C_{L}(D, G) und der Dimension k zu bekommen, setzen wir deshalb oft g ≤ deg G < n voraus.

Definition 3.1.4 Die Zahl d^{∗} := n − deg G nennt man die konstruierte Distanz des Codes C_{L}(D, G).

Satz 3.1.3 besagt, dass die Minimaldistanz d eines geometrischen Goppa-Codes nicht kleiner als seine konstruierte Distanz sein kann. Die Frage, ob d^{∗} = d oder d^{∗} < d gilt, wird durch den folgenden Hilfssatz beantwortet:

Hilfssatz 3.1.5 Angenommen es gelte dim G > 0 und d^{∗} = n − deg G > 0.

So gilt d^{∗} = d dann und nur dann, wenn ein Divisor D′ mit 0 ≤ D′ ≤ D, deg D′ = deg G und dim(G − D′) > 0 existiert.

Beweis. Zunächst nehmen wir d^{∗} = d an. Dann gibt es ein Element 0 ≠ x ∈ L(G), sodass das Codewort (x(P_{1}), …, x(P_{n})) ∈ C_{L}(D, G) genau n − d = n − d^{∗} = deg G Komponenten hat, die 0 sind, sagen wir x(P_{i_{j}}) = 0 für j = 1, …, deg G. Setzen wir

D′ := ∑_{j=1}^{deg G} P_{i_{j}}.

Dann gilt: 0 ≤ D′ ≤ D, deg D′ = deg G und dim(G − D′) > 0 (da x ∈ L(G − D′) ist). Umkehrung: Falls D′ die obigen Eigenschaften hat, wählen wir ein Element 0 ≠ y ∈ L(G − D′). Das Gewicht des dazugehörigen Codewortes (y(P_{1}), …, y(P_{n})) ist ≤ n − deg G = d^{∗}, daher gilt d = d^{∗}. □

Mit Hilfe der lokalen Komponenten von Weil-Differentialen kann auch ein anderer Code zu den Divisoren G und D assoziiert werden.

Definition 3.1.6 Seien G und D = P_{1} + ⋯ + P_{n} Divisoren wie zuvor. Dann definieren wir den Code C_{Ω}(D, G) ⊆ 𝔽_{q}^{n} durch

C_{Ω}(D, G) := {(ω_{P_{1}}(1), …, ω_{P_{n}}(1)) | ω ∈ Ω_{F} (G − D)}.

Unser erstes Resultat ist ein Analogon zu Satz 3.1.2.

Satz 3.1.7 C_{Ω}(D, G) ist ein [n, k′, d′]-Code mit den Parametern

k′ = i(G − D) − i(G) und d′ ≥ deg G − (2g − 2).

Unter der zusätzlichen Voraussetzung, dass deg G > 2g − 2 ist, gilt k′ = i(G − D) ≥ n + g − 1 − deg G. Falls 2g − 2 < deg G < n ist ,dann gilt

k′ = n + g − 1 − deg G.

Beweis. Sei P ∈ ℙ_{F} eine rationale Stelle und ω ein Weil-Differential mit ν_{P} (ω) ≥ −1. Wir behaupten

ω_{P} (1) = 0 ⟺ ν_{P} (ω) ≥ 0.  (3.4)

Um diese Aussage zu zeigen, verwenden wir Satz 2.5.20 (a), der besagte, dass für eine ganze Zahl r ∈ ℤ Folgendes gilt:

ν_{P} (ω) ≥ r ⟺ ω_{P} (x) = 0 für alle x ∈ F mit ν_{P} (x) ≥ −r. (3.5)

Die Implikation ⇐ von (3.4) ist eine offensichtliche Folgerung aus (3.5). Umgekehrt nehmen wir an, dass ω_{P} (1) = 0 sei. Sei nun x ∈ F mit ν_{P} (x) ≥ 0. Da deg P = 1 ist, können wir x = a + y mit a ∈ 𝔽_{q} und ν_{P} (y) ≥ 1 schreiben. Dann ist

ω_{P} (x) = ω_{P} (a) + ω_{P} (y) = a · ω_{P} (1) + 0 = 0.

Aus (3.5) folgt nämlich ω_{P} (y) = 0, da ν_{P} (ω) ≥ −1 und ν_{P} (y) ≥ 1 gilt. Damit ist (3.4) gezeigt. Wir betrachten jetzt die 𝔽_{q}-lineare Abbildung

ρ_{D} : \{ \begin{matrix}Ω_{F} (G − D) & ⟶ & C_{Ω}(D, G), \\ ω & ⟼ & (ω_{P_{1}}(1), …, ω_{P_{n}}(1)). \end{matrix}

ρ_{D} ist surjektiv, und nach (3.4) ist Ω_{F} (G) ihr Kern. Daraus ergibt sich

k′ = dim Ω_{F} (G − D) − dim Ω_{F} (G) = i(G − D) − i(G).  (3.6)

Sei ρ_{D}(ω) ∈ C_{Ω}(D, G) ein Codewort mit Gewicht m > 0. Dann ist ω_{P_{i}}(1) = 0 für gewisse Indizes i = i_{1}, …, i_{n−m}, daher gilt nach (3.4)

ω ∈ Ω_{F} (G − (D − ∑_{j=1}^{n−m} P_{i_{j}})).

Da Ω_{F} (A) ≠ 0 nach Satz 2.6.6 deg A ≤ 2g − 2 impliziert, erhalten wir

2g − 2 ≥ deg G − (n − (n − m)) = deg G − m.

Daher gilt für die Minimaldistanz d′ von C_{Ω}(D, G) die Ungleichung d′ ≥ deg G − (2g − 2). Wenn wir noch deg G > 2g − 2 annehmen, erhalten wir nach Satz 2.6.6 i(G) = 0. Deshalb impliziert (3.6)

k′ = i(G − D) = dim(G − D) − deg(G − D) − 1 + g
= dim(G − D) + n + g − 1 − deg G.

Die verbleibenden Aussagen des Satzes folgen jetzt sofort. □

In Analogie zu Definition 3.1.4 nennt man deg G − (2g − 2) die konstruierte Distanz von C_{Ω}(D, G).

Die enge Verbindung, die es zwischen C_{L}(D, G) und C_{Ω}(D, G) gibt, zeigt der folgende Satz:

Satz 3.1.8 Die Codes C_{L}(D, G) und C_{Ω}(D, G) sind dual zueinander, das heißt es gilt

C_{Ω}(D, G) = C_{L}(D, G)^{⊥}.

Beweis. Wir bemerken zunächst die folgende Tatsache: Man betrachte eine rationale Stelle P ∈ ℙ_{F}, ein Weil-Differential ω mit ν_{P} (ω) ≥ −1 und ein Element x ∈ F mit ν_{P} (x) ≥ 0. Dann gilt

ω_{P} (x) = x(P) · ω_{P} (1).  (3.7)

Um dies zu zeigen, schreiben wir x = a+y mit a = x(P) ∈ 𝔽_{q} und ν_{P} (y) > 0. Dann gilt nach (3.5) ω_{P} (x) = ω_{P} (a) + ω_{P} (y) = a · ω_{P} (1) + 0 = x(P) · ω_{P} (1). Als nächstes zeigen wir, dass C_{Ω}(D, G) ⊆ C_{L}(D, G)^{⊥}. Sei dazu ω ∈ Ω_{F} (G − D) und x ∈ L(G). Wir erhalten

0 = ω(x) = ∑_{P ∈ℙ_{F}} ω_{P} (x)  (3.8)

= ∑_{i=1}^{n} ω_{P_{i}}(x)  (3.9)

= ∑_{i=1}^{n} x(P_{i}) · ω_{P_{i}}(1)  (3.10)
= ⟨(ω_{P_{1}}(1), …, ω_{P_{n}}(1)), (x(P_{1}), …, x(P_{n}))⟩,

wobei ⟨, ⟩ das kanonische innere Produkt von 𝔽_{q}^{n} bezeichnet (siehe Definition 1.3.11). Wir müssen noch die einzelnen Schritte in der obigen Rechnung rechtfertigen. (3.8) folgt aus Satz 2.5.19 und der Tatsache, dass Weil-Differentiale auf Hauptadèlen verschwinden. Für P ∈ ℙ_{F} \{P_{1}, …, P_{n}} gilt ν_{P} (x) ≥ −ν_{P} (ω), da x ∈ L(G) und ω ∈ Ω_{F} (G − D) ist, deshalb folgt aus (3.5) ω_{P} (x) = 0. Das beweist (3.9). Schlussendlich folgt (3.10) aus (3.7). Daher ist C_{Ω}(D, G) ⊆ C_{L}(D, G)^{⊥}. Es genügt jetzt zu zeigen, dass die Codes C_{Ω}(D, G) und C_{L}(D, G)^{⊥} diesselbe Dimension haben. Aus den Sätzen 3.1.2, 3.1.7 und aus der Definition des Spezialitätsindex 2.5.1 folgt:

dim C_{Ω}(D, G) = i(G − D) − i(G)
= dim(G − D) − deg(G − D) − 1 + g
−(dim G − deg G − 1 + g)
= deg D + dim(G − D) − dim G
= n − (dim G − dim(G − D))
= n − dim C_{L}(D, G) = dim C_{L}(D, G)^{⊥}.
□

Als nächstes wollen wir zeigen, dass C_{Ω}(D, G) als C_{L}(D, H) mit einem geeigneten Divisor H dargestellt werden kann. Daraus wird dann ersichtlich, dass die beiden Definitionen ein und dieselbe Klasse von Codes, nämlich die geometrischen Goppa-Codes, beschreiben. Für diesen Zweck benötigen wir zunächst den folgenden Hilfssatz.

Hilfssatz 3.1.9 Es gibt ein Weil-Differential η mit den folgenden Eigenschaften:

ν_{P_{i}}(η) = −1 und η_{P_{i}}(1) = 1 für i = 1, …, n.

Beweis. Wähle ein beliebiges Weil-Differential ω_{0} ≠ 0. Nach dem schwachen Approximationssatz 2.2.7 gibt es ein Element z ∈ F mit ν_{P_{i}}(z) = −ν_{P_{i}}(ω_{0})−1 für i = 1, …, n. Setze ω := zω_{0}, dann erhalten wir ν_{P_{i}}(ω) = −1. Daher gilt nach (3.4) a_{i} := ω_{P_{i}}(1) ≠ 0. Wieder gibt es nach dem schwachen Approximationssatz 2.2.7 ein Element y ∈ F, sodass ν_{P_{i}}(y − a_{i}) > 0 ist. Es folgt: ν_{P_{i}}(y) = 0 und y(P_{i}) = a_{i}. Wir setzen η := y^{−1}ω und erhalten ν_{P_{i}}(η) = ν_{P_{i}}(ω) = −1 und

η_{P_{i}}(1) = ω_{P_{i}}(y^{−1}) = y^{−1}(P_{i}) · ω_{P_{i}}(1) = a_{i}^{−1} · a_{i} = 1.
□

Satz 3.1.10 Sei η ein Weil-Differential mit ν_{P_{i}}(η) = −1 und η_{P_{i}}(1) = 1 für i = 1, …, n. Dann gilt

C_{L}(D, G)^{⊥} = C_{Ω}(D, G) = C_{L}(D, D − G + (η)).

Beweis. Beachte, dass supp (D − G + (η)) ∩ supp D = ∅ ist, da ν_{P_{i}}(η) = −1 für i = 1, …, n gilt. Daher ist C_{L}(D, D − G + (η)) wohldefiniert. Nach Satz 2.6.3 gibt es einen Isomorphismus μ : L(D −G+(η)) → Ω_{F} (G−D) definiert durch μ(x) := xη. Für x ∈ L(D − G + (η)) gilt nach (3.7)

(xη)_{P_{i}}(1) = η_{P_{i}}(x) = x(P_{i}) · η_{P_{i}}(1) = x(P_{i}).

Daraus folgt C_{Ω}(D, G) = C_{L}(D, D − G + (η)). □

Wir könnten Satz 3.1.10 zum Beispiel dazu verwenden um einen anderen Beweis von Satz 3.1.7 – und zwar als direkte Folgerung aus Satz 3.1.2 – zu geben. Als Nächstes wollen wir noch zeigen, dass zu G äquivalente Divisoren, diesselben geometrischen Goppa-Codes definieren.

Satz 3.1.11

(a) Angenommen G_{1} und G_{2} sind Divisoren mit G_{1} ∼ G_{2} und

supp G_{1} ∩ supp D = supp G_{2} ∩ supp D = ∅.

Dann sind die Codes C_{L}(D, G_{1}) und C_{L}(D, G_{2}) äquivalent. Dasselbe gilt für C_{Ω}(D, G_{1}) und C_{Ω}(D, G_{2}).

(b) Umgekehrt gilt: Wenn C ⊆ 𝔽_{q}^{n} ein zu C_{L}(D, G) (bzw. zu C_{Ω}(D, G)) äquivalenter Code ist, dann gibt es einen Divisor G′ ∼ G, sodass supp G′∩supp D = ∅ und C = C_{L}(D, G′) (bzw. C = C_{Ω}(D, G′)) ist.

Beweis. (a) Nach Annahme ist G_{2} = G_{1}−(z) mit ν_{P_{i}}(z) = 0 für i = 1, …, n. Daher ist a := (z(P_{1}), …, z(P_{n})) ∈ (𝔽_{q}\{0})^{n}. Außerdem ist die Abbildung x ↦ xz von L(G_{1}) nach L(G_{2}) bijektiv (nach Hilfssatz 2.4.9). Das zeigt C_{L}(D, G_{2}) = a · C_{L}(D, G_{1}). Die Äquivalenz von C_{Ω}(D, G_{1}) und C_{Ω}(D, G_{2}) beweist man ähnlich.

(b) Sei C = a · C_{L}(D, G) mit a = (a_{1}, …, a_{n}) ∈ (𝔽_{q}\{0})^{n}. Nach dem Approximationssatz 2.2.7 gibt es ein z ∈ F mit z(P_{i}) = a_{i} (i = 1, …, n) und setze G′ := G − (z). Dann ist C = C_{L}(D, G′). □

Dieser Satz hat die folgende Konsequenz: Falls G ein Divisor ist, dessen Träger nicht disjunkt zu supp D ist, können wir immer noch einen geometrischen Goppa-Code C_{L}(D, G) assoziiert zu D und G definieren. Wähle nämlich einen Divisor G′ ∼ G mit supp G′ ∩ supp D = ∅ (das ist nach dem schwachen Approximationssatz 2.2.7 möglich) und setze C_{L}(D, G) := C_{L}(D, G′). Die Wahl von G′ ist nicht kanonisch, daher ist nach Satz 3.1.11 C_{L}(D, G) nur bis auf Äquivalenz wohldefiniert.

3.2 Konstruktion nach Xing - Niederreiter - Lam und Özbudak - Stichtenoth

Kürzlich haben C. P. Xing, H. Niederreiter und K. Y. Lam eine Reihe von neuen Konstruktionen von Linearcodes, basierend auf algebraischen Funktionenkörpern, entdeckt (siehe [15], [25] und [26]). Diese neuen Konstruktionen unterscheiden sich wesentlich von Goppas Konstruktion der geometrischen Goppa-Codes, die wir im letzten Kapitel kennengelernt haben. Während Goppa nur die Auswertung von Funktionen (bzw. von Weil-Differe-ntialen bei 1) verwendet, machen Xing, Niederreiter und Lam wesentlichen Gebrauch von P -adischen Potenzreihenentwicklungen, nicht speziellen Divisoren, usw.

Diese neuen Codes haben sich als äquivalent zu gewissen geometrischen Goppa-Codes herausgestellt. Wir werden sie im nächsten Abschnitt kennenlernen. In diesem Abschnitt wollen wir eine Verallgemeinerung der Konstruktion von Xing, Niederreiter und Lam betrachten, die äquivalent zu Goppas Konstruktion ist, und von F. Özbudak und H. Stichtenoth stammt (siehe [16]).

Die grundsätzliche Idee dabei ist recht einfach: Seien G_{1} und G_{2} zwei Divisoren eines algebraischen Funkionenkörpers über 𝔽_{q} mit G_{1} ≤ G_{2}. Dann ist L(G_{1}) ein Unterraum des Vektorraumes L(G_{2}) über 𝔽_{q}. Wenn wir daher eine Basis von L(G_{2}) wählen, dann bilden die Koordinatenvektoren der Elemente von L(G_{1}) einen linearen Code über 𝔽_{q} der Länge n = dim(L(G_{2})) und mit Dimension k = dim(L(G_{1})). Wir werden eine leicht verbesserte Variante dieser Idee verwenden. Klarerweise müssen dabei die Basis, sowie die Divisoren G_{1} und G_{2} geeignet gewählt werden, denn nimmt man zum Beispiel eine Basis von L(G_{1}) und erweitert diese zu einer Basis von L(G_{2}), dann erhält man einen uninteressanten Linearcode mit Minimaldistanz 1.

Es sei F/𝔽_{q} ein algebraischer Funktionenkörper mit Geschlecht g. Wir wählen einen nicht speziellen Divisor B und n verschiedene rationale Stellen P_{1}, …, P_{n}. Für 1 ≤ j ≤ n betrachten wir den Vektorraum

L(B + P_{j}).

Dann ist L(B + P_{j})\L(B) nichtleer. Da nämlich B als nicht speziell vorausgesetzt war, folgt mit Hilfsatz 2.6.12

dim(B + P_{j}) = dim(B) + 1.

Wir wählen Elemente

f_{j} ∈ L(B + P_{j})\L(B)  (3.11)

für jedes 1 ≤ j ≤ n. Dann gilt der folgende Hilfssatz:

Hilfssatz 3.2.1 Seien f_{1}, f_{2}, …, f_{n} wie in (3.11), dann hat jedes f ∈ L(B + ∑_{i=1}^{n} P_{i}) eine eindeutige Darstellung der Form

f = ∑_{i=1}^{n} c_{i}f_{i} + w, mit c_{i} ∈ 𝔽_{q} und w ∈ L(B).

Beweis. Es sei s := dim B und g_{1}, …, g_{s} eine Basis von L(B). Zunächst gilt wieder mit Hilfssatz 2.6.12

dim (B + ∑_{i=1}^{n} P_{i}) = dim(B) + n.

Es genügt also zu zeigen, dass f_{1}, …, f_{n}, g_{1}, …, g_{s}, linear unabhängig über 𝔽_{q} sind. Sei dazu

∑_{i=1}^{n} a_{i}f_{i} + ∑_{j=1}^{s} b_{j}g_{j} = 0

mit a_{i}, b_{j} ∈ 𝔽_{q}. Angenommen a_{h} ≠ 0 für ein 1 ≤ h ≤ n. Dann gilt

−a_{h}f_{h} = ∑_{i≠h} a_{i}f_{i} + ∑_{j=1}^{s} b_{j}g_{j}.  (3.12)

Nach Konstruktion der f_{i}, g_{j} erhalten wir die Ungleichungen

ν_{P_{h}}(−a_{h}f_{h}) = ν_{P_{h}}(f_{h}) ≤ −ν_{P_{h}}(B) − 1

und

ν_{P_{h}} (∑_{i≠h} a_{i}f_{i} + ∑_{j=1}^{s} b_{j}g_{j}) ≥ −ν_{P_{h}}(B).

Diese zwei Ungleichungen sind ein Widerspruch zu (3.12). Daher ist a_{1} = a_{2} = ⋯ = a_{n} = 0 und nach Wahl der g_{j} ist daher auch b_{1} = ⋯ = b_{s} = 0. Daraus folgt die Behauptung. □

Als nächstes betrachten wir die 𝔽_{q}-lineare Abbildung

α : \{ \begin{matrix}L(B + ∑_{i=1}^{n} P_{i}) & ⟶ & 𝔽_{q}^{n}, \\ f & ⟼ & (c_{1}, …, c_{n}). \end{matrix}  (3.13)

Diese Abbildung ist klarerweise surjektiv und besitzt den Kern ker(α) = L(B).

Sei A ein weiterer Divisor mit den folgenden Eigenschaften:

A ≥ 0 und supp A ∩ {P_{1}, …, P_{n}} = ∅.  (3.14)

Dann definieren wir den folgenden Code:

Definition 3.2.2 Seien B, P_{1}, …, P_{n}, A und die Abbildung α wie vorher. Dann definieren wir den Code C_{N S}(B; P_{1}, …, P_{n}; A) ⊆ 𝔽_{q}^{n} durch

C_{N S} := C_{N S}(B; P_{1}, …, P_{n}; A) = α (L (B + ∑_{i=1}^{n} P_{i} − A)) .

Wir wollen als Nächstes zeigen, dass die so erhaltenen Codes in Wirklichkeit geometrische Goppa-Codes sind.

Wir betrachten also den Code

C_{N S} = C_{N S}(B; P_{1}, …, P_{n}; A),

wobei B ein nicht spezieller Divisor ist, P_{1}, …, P_{n} verschiedene rationale Stellen sind und A ein positiver Divisor mit supp A ∩ {P_{1}, …, P_{n}} = ∅ ist. Mit Hilfe des schwachen Approximationssatzes 2.2.7 finden wir ein Element z ∈ F mit

ν_{P_{i}}(z − f_{i}^{−1}) = −ν_{P_{i}}(f_{i}) + 1, i = 1, …, n.

Es gilt dann

ν_{P_{i}}(zf_{i}) = 0 und (zf_{i})(P_{i}) = 1,

für i = 1, …, n. Wir definieren den Divisor:

G := B + ∑_{i=1}^{n} P_{i} − A − (z).

Es gilt dann der folgende Satz:

Satz 3.2.3 Seien A, B, P_{1}, …, P_{n}, und G wie vorhin. Dann gilt

C_{N S}(B; P_{1}, …, P_{n}; A) = C_{L}(P_{1} + ⋯ + P_{n}, G).

Beweis. Zunächst sei bemerkt, dass

ν_{P_{i}}(G) = ν_{P_{i}}(B) + 1 − ν_{P_{i}}(z) = −ν_{P_{i}}(f_{i}) − ν_{P_{i}}(z) = 0

für i = 1, …, n gilt, daher ist supp G ∩ {P_{1}, …, P_{n}} = ∅. Betrachte die Auswertungsabbildung

ev : \{ \begin{matrix}L(G) & ⟶ & 𝔽_{q}^{n}, \\ h & ⟼ & (h(P_{1}), …, h(P_{n})) \end{matrix}

und die Abbildung

φ : \{ \begin{matrix}L (B + ∑_{i=1}^{n} P_{i} − A) & ⟶ & L(G), \\ f & ⟼ & zf. \end{matrix}

Die Abbildung φ ist ein 𝔽_{q}-linearer Isomorphismus (siehe Hilfssatz 2.4.9 (b)). Wir betrachten jetzt das folgende Diagramm:

L (B + ∑_{i=1}^{n} P_{i} − A) ⟶ L(G)
↘  ↙
𝔽_{q}^{n}

wobei α : L(B + ∑_{i=1}^{n} P_{i} − A) → 𝔽_{q}^{n} durch (3.13) definiert ist. Wie man leicht sieht ist dieses Diagramm kommutativ. Sei nämlich

f ∈ L (B + ∑_{i=1}^{n} P_{i} − A) ,

dann erhalten wir

f = ∑_{i=1}^{n} c_{i}f_{i} + w

mit c_{1}, …, c_{n} ∈ 𝔽_{q} und w ∈ L(B) (das geht nach Hilfssatz 3.2.1). Daher ist (c_{1}, …, c_{n}) = α(f). Andererseits gilt

(zf)(P_{j}) = (∑_{i=1}^{n} c_{i}zf_{i} + zw) (P_{j}) = c_{j}(zf_{j})(P_{j}) = c_{j}

für alle 1 ≤ j ≤ n, nach Wahl von z und da ν_{P_{j}}(zf_{i}) = ν_{P_{j}}(z) + ν_{P_{j}}(f_{i}) ≥ −ν_{P_{j}}(B) + 1 + ν_{P_{j}}(B) = 1 > 0 und genauso ν_{P_{j}}(zw) ≥ 1 > 0 ist. Also gilt ev(φ(f)) = α(f). Daher folgt

C_{N S} = α (L (B + ∑_{i=1}^{n} P_{i} − A)) = ev(L(G)) = C_{L}(P_{1} + ⋯ + P_{n}, G).

□

Als Folgerung erhalten wir sofort Abschätzungen für die Parameter des Codes C_{N S}(B; P_{1}, …, P_{n}; A).

Satz 3.2.4 Es sei B ein nicht spezieller Divisor, P_{1}, …, P_{n} verschiedene rationale Stellen, sowie A ein Divisor mit (3.14). Zusätzlich gelte deg A > deg B. Dann ist C_{N S}(B; P_{1}, …, P_{n}; A) ein [n, k, d]-Code mit

k ≥ deg B − deg A + n + 1 − g und d ≥ deg A − deg B.

Beweis. Folgt sofort aus Satz 3.2.3 und Satz 3.1.3. □

Aus dem Beweis von Satz 3.2.3 sieht man außerdem leicht, dass jeder geometrische Goppa-Code als ein Code C_{N S}, mit geeigneten Divisoren, dargestellt werden kann. In diesem Sinne sind diese beiden Konstruktionen äquivalent.

3.3 Einige spezielle Klassen von Goppa-Codes

In diesem Abschnitt wollen wir zunächst geometrische Goppa-Codes untersuchen, die mit Hilfe von Divisoren des rationalen Funktionenkörpers definiert werden.

Definition 3.3.1 Ein geometrischer Goppa-Code C_{L}(D, G) assoziiert mit Divisoren G und D des rationalen Funktionenkörpers 𝔽_{q}(z)/𝔽_{q} nennt man rational (wir nehmen wieder stets an, dass D = P_{1} + ⋯ + P_{n} mit paarweise verschiedenen rationalen Stellen und supp G∩supp D = ∅ gilt).

Beachte, dass die Länge von C_{L}(D, G) durch q + 1 beschränkt ist, da 𝔽_{q}(z) nur q + 1 rationale Stellen besitzt, nämlich den Pol P_{∞} von z und für jedes α ∈ 𝔽_{q} die Nullstelle P_{α} von z − α (siehe Satz 2.3.1). Das folgende Resultat ist eine sofortige Konsequenz aus Abschnitt 3.1.

Satz 3.3.2 Sei C = C_{L}(D, G) ein rationaler geometrischer Goppa-Code über 𝔽_{q}, und seien n, k, d die Parameter von C. Dann gilt:

(a) n ≤ q + 1.

(b) k = 0 ⟺ deg G < 0, und k = n ⟺ deg G > n − 2.

(c) Für 0 ≤ deg G ≤ n − 2 gilt,

k = 1 + deg G und d = n − deg G.

Insbesondere ist C daher ein MDS Code.

(d) C^{⊥} ist ebenfalls ein rationaler geometrischer Goppa-Code.

Als nächstes berechnen wir die Generatormatrix eines rationalen geometrischen Goppa-Codes.

Satz 3.3.3 Sei C = C_{L}(D, G) ein rationaler geometrischer Goppa-Code über 𝔽_{q} mit Parametern n, k und d.

(a) Falls n ≤ q ist, gibt es paarweise verschiedene Elemente α_{1}, …, α_{n} ∈ 𝔽_{q} und v_{1}, …, v_{n} ∈ 𝔽_{q}\{0} (nicht notwendig verschieden), sodass

C = {(v_{1} · f(α_{1}), v_{2} · f(α_{2}), …, v_{n} · f(α_{n})) | f ∈ 𝔽_{q}[z] und deg f ≤ k − 1}.

Die Matrix

M = ( \begin{matrix}v_{1} & v_{2} & ⋯ & v_{n} \\ α_{1}v_{1} & α_{2}v_{2} & ⋯ & α_{n}v_{n} \\ α_{1}^{2}v_{1} & α_{2}^{2}v_{2} & ⋯ & α_{n}^{2}v_{n} \\ ⋮ & ⋮ & & ⋮ \\ α_{1}^{k−1}v_{1} & α_{2}^{k−1}v_{2} & ⋯ & α_{n}^{k−1}v_{n} \end{matrix} )  (3.15)

ist eine Generatormatrix von C.

(b) Falls n = q + 1 ist, hat C die folgende Generatormatrix

M = ( \begin{matrix}v_{1} & v_{2} & ⋯ & v_{n−1} & 0 \\ α_{1}v_{1} & α_{2}v_{2} & ⋯ & α_{n}v_{n−1} & 0 \\ α_{1}^{2}v_{1} & α_{2}^{2}v_{2} & ⋯ & α_{n}^{2}v_{n−1} & 0 \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ α_{1}^{k−1}v_{1} & α_{2}^{k−1}v_{2} & ⋯ & α_{n}^{k−1}v_{n−1} & 1 \end{matrix} )  (3.16)

wobei 𝔽_{q} = {α_{1}, …, α_{n−1}} und v_{1}, …, v_{n−1} ∈ 𝔽_{q}\{0}.

Beweis. (a) Sei D = P_{1} + ⋯ + P_{n}. Da n ≤ q ist, gibt es eine rationale Stelle P, die nicht im Träger von D liegt. Wähle eine rationale Stelle Q ≠ P (z.B. Q = P_{1}). Nach dem Satz von Riemann-Roch 2.6.4 gilt dim(Q−P) = 1, daher ist nach Folgerung 2.4.15 Q − P ein Hauptdivisor. Sei Q − P = (z). Dann ist z ein erzeugendes Element des rationalen Funktionenkörpers über 𝔽_{q}, und P ist ein Poldivisor von z. Wie gewöhnlich schreiben wir P = P_{∞}. Nach Satz 3.3.2 können wir annehmen, dass deg G = k − 1 ≥ 0 sei, denn der Fall k = 0 ist trivial. Der Divisor (k − 1)P_{∞} − G hat Grad 0, daher ist er ein Hauptdivisor (wieder nach dem Satz von Riemann-Roch 2.6.4 und Folgerung 2.4.15). Sei (k − 1)P_{∞} − G = (u) mit 0 ≠ u ∈ F. Die k Elemente u, z · u, …, z^{k−1} · u sind in L(G), und sie sind linear unabhängig über 𝔽_{q}. Da dim G = k ist, bilden sie eine Basis von L(G), das heißt

L(G) = {u · f(z) | f ∈ 𝔽_{q}[z] und deg f ≤ k − 1}.

Wir setzen α_{i} := z(P_{i}) und v_{i} := u(P_{i}) und erhalten

(u · f(z))(P_{i}) = u(P_{i}) · f(z(P_{i})) = v_{i} · f(α_{i})

für i = 1, …, n. Daher gilt

C = C_{L}(D, G) = {(v_{1} · f(α_{1}), …, v_{n} · f(α_{n})) | deg f ≤ k − 1}.

Das Codewort in C, das zu u · z^{j} gehört, ist (v_{1}α_{1}^{j}, v_{2}α_{2}^{j}, …, v_{n}α_{n}^{j}), daher ist die Matrix (3.15) eine Generatormatrix von C.

(b) Der Beweis ist im Wesentlichen derselbe wie der im Fall n ≤ q. Doch jetzt gilt n = q + 1, und wir können ein Element z so wählen, dass P_{n} = P_{∞} der Pol von z ist. Wie oben haben wir (k − 1)P_{∞} − G = (u) mit 0 ≠ u ∈ F und {u, z · u, …, z^{k−1} · u} ist eine Basis von L(G). Für 1 ≤ i ≤ n − 1 = q sind die Elemente α_{i} := z(P_{i}) ∈ 𝔽_{q} paarweise verschieden, daher gilt 𝔽_{q} = {α_{1}, …, α_{n−1}}. Weiters ist v_{i} := u(P_{i}) ∈ 𝔽_{q}\{0} für i = 1, …, n − 1. Für 0 ≤ j ≤ k − 2 erhalten wir

((uz^{j})(P_{1}), …, (uz^{j})(P_{n})) = (α_{1}^{j}v_{1}, …, α_{n−1}^{j}v_{n−1}, 0),

aber für j = k − 1 folgt

((uz^{k−1})(P_{1}), …, (uz^{k−1})(P_{n})) = (α_{1}^{k−1}v_{1}, …, α_{n−1}^{k−1}v_{n−1}, γ)

mit einem Element 0 ≠ γ ∈ 𝔽_{q}. Wenn wir u durch γ^{−1}u ersetzen, erhalten wir die Generatormatrix (3.16). □

Um den zum rationalen geometrischen Goppa-Code C = C_{L}(D, G) dualen Code zu berechnen, benötigen wir nach Satz 3.1.8 und 3.1.10 ein Weil-Differential ω von 𝔽_{q}(z), sodass

ν_{P_{i}}(ω) = −1 und ω_{P_{i}}(1) = 1 für i = 1, …, n.  (3.17)

Hilfssatz 3.3.4 Betrachte den rationalen Funktionenkörper F = 𝔽_{q}(z) und n verschiedene Elemente α_{1}, …, α_{n} ∈ 𝔽_{q}. Sei P_{i} ∈ ℙ_{F} eine Nullstelle von z − α_{i} und h(z) := ∏_{i=1}^{n}(z − α_{i}). Angenommen y ist ein Element von F mit y(P_{i}) = 1 für i = 1, …, n. Dann gibt es ein Weil-Differential ω von F/𝔽_{q} mit der Eigenschaft (3.17) und dem Divisor

(ω) = (y) + (h′(z)) − (h(z)) − 2P_{∞}

(wobei h′(z) ∈ 𝔽_{q}[z] die Ableitung des Polynomes h(z) bezeichnet).

Beweis. Nach Satz 2.6.10 gibt es ein Weil-Differential η von F mit (η) = −2P_{∞} und η_{P_{∞}}(z^{−1}) = −1. Wir setzen

ω := y · (h′(z)/h(z)) · η.

Der Divisor von ω ist (ω) = (y) + (h′(z)) − (h(z)) − 2P_{∞}, insbesondere gilt ν_{P_{i}}(ω) = −1 für i = 1, …, n. Wir müssen zeigen, dass ω_{P_{i}}(1) = 1 ist. Dazu schreiben wir h(z) = (z − α_{i})g_{i}(z). Dann folgt

y · \frac{h′(z)}{h(z)} = (1 + (y − 1)) · (\frac{g′_{i}(z)}{g_{i}(z)} + \frac{1}{z − α_{i}} ) = \frac{1}{z − α_{i}} + u

mit u ∈ F und ν_{P_{i}}(u) ≥ 0 (da ν_{P_{i}}(y − 1) > 0 und ν_{P_{i}}(g_{i}(z)) = 0 ist). Da nach Satz 2.6.10 (c) und Satz 2.5.20 (a) η_{P_{i}}((z − α_{i})^{−1}) = 1 und η_{P_{i}}(u) = 0 ist, erhalten wir

ω_{P_{i}}(1) = η_{P_{i}} (y · \frac{h′(z)}{h(z)}) = η_{P_{i}} (\frac{1}{z − α_{i}} + u) = 1.

□

Beachte, dass man mit Hilfe von Hilfssatz 3.3.4 - kombiniert mit den Sätzen 3.1.8, 3.1.10 und 3.3.3 - eine Kontrollmatrix für C_{L}(D, G) angeben kann.

Beispiele für rationale geometrische Goppa-Codes kennen wir bereits: BCH-Codes. Der nächste Satz stellt die Verbindung her.

Satz 3.3.5 Sei n|q^{m} − 1 und β ∈ 𝔽_{q^{m}} eine n-te primitive Einheitswurzel. Sei F = 𝔽_{q^{m}}(z) der rationale Funktionenkörper über 𝔽_{q^{m}} und P_{0} (bzw. P_{∞}) die Nullstelle (bzw. der Pol) von z. Für i = 1, …, n bezeichne P_{i} die Nullstelle von z − β^{i−1}, und wir setzen D_{β} := P_{1} + ⋯ + P_{n}. Angenommen a, b ∈ ℤ sind ganze Zahlen mit 0 ≤ a + b ≤ n − 2. Dann gilt:

(a) C_{L}(D_{β}, aP_{0} + bP_{∞}) = C(n, l, δ) mit l = −a und δ = a + b + 2 (für C(n, l, δ) siehe Definition 1.6.1).

(b) Der zu C_{L}(D_{β}, aP_{0} + bP_{∞}) duale Code ist gegeben durch

C_{L}(D_{β}, aP_{0} + bP_{∞})^{⊥} = C_{L}(D_{β}, rP_{0} + sP_{∞})

mit r = −(a + 1) und s = n − b − 1. Daher ist der BCH-Code C(n, l, δ)^{⊥}|_{𝔽_{q}} die Einschränkung des Codes C_{L}(D_{β}, rP_{0} + sP_{∞}) auf 𝔽_{q}, mit r = l − 1 und s = n + 1 − δ − l.

Beweis. (a) Wir betrachten den Code C_{L}(D_{β}, aP_{0} +bP_{∞}), wobei 0 ≤ a+b ≤ n − 2 ist. Die Elemente z^{−a} · z^{j} mit 0 ≤ j ≤ a + b bilden eine Basis von L(aP_{0} + bP_{∞}). Daher ist die Matrix

( \begin{matrix}1 & β^{−a} & β^{−2a} & ⋯ & (β^{n−1})^{−a} \\ 1 & β^{−a+1} & β^{−2a+2} & ⋯ & (β^{n−1})^{−a+1} \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ 1 & β^{−a+(a+b)} & β^{−2a+2(a+b)} & ⋯ & (β^{n−1})^{−a+(a+b)} \end{matrix} )

eine Generatormatrix von C_{L}(D_{β}, aP_{0} + bP_{∞}). Setzen wir l := −a und δ := a + b + 2, dann erhalten wir (1.1), daher ist C_{L}(D_{β}, aP_{0} + bP_{∞}) = C(n, l, δ).

(b) Wir verwenden die Bezeichnungen von Hilfssatz 3.3.4 und setzen

y := z^{−n} und h(z) := ∏_{i=1}^{n}(z − β^{i−1}) = z^{n} − 1.

Nach Satz 3.1.10 ist C_{L}(D_{β}, aP_{0} + bP_{∞})^{⊥} = C_{L}(D_{β}, B) mit

B = D_{β} − (aP_{0} + bP_{∞}) + (z^{−n}) + (h′(z)) − (h(z)) − 2P_{∞}
= D_{β} − (aP_{0} + bP_{∞}) + n(P_{∞} − P_{0}) + (n − 1)(P_{0} − P_{∞})
−(D_{β} − nP_{∞}) − 2P_{∞}
= (−a − 1)P_{0} + (n − b − 1)P_{∞}.

Da nach (a) l = −a und δ = a + b + 2 ist, finden wir C_{L}(D_{β}, aP_{0} + bP_{∞})^{⊥} = C_{L}(D_{β}, rP_{0} + sP_{∞}) mit s = n − b − 1 = n − (δ − a − 2) − 1 = n + 1 − δ − l und r = −a − 1 = l − 1. □

Satz 1.6.2, der eine Schranke für die Minimaldistanz eines BCH-Codes angab, erhalten wir nun als einfache Folgerung.

Folgerung 3.3.6 Die Minimaldistanz eines BCH-Codes mit konstruierter Minimaldistanz δ ist mindestens δ.

Beweis. Nach Satz 3.3.5 können wir einen BCH-Code in der Form C = C_{L}(D_{β}, rP_{0}+sP_{∞})|_{𝔽_{q}} darstellen. Die Minimaldistanz von C_{L}(D_{β}, rP_{0}+sP_{∞}) ist nach Satz 3.3.2 und Satz 3.3.5 (b)

d = n − deg(rP_{0} + sP_{∞}) = n − ((l − 1) + (n + 1 − δ − l)) = δ.

Da die Minimaldistanz bei der Einschränkung auf 𝔽_{q} nicht kleiner werden kann, ist die Minimaldistanz von C ≥ δ. □

Als nächstes wollen wir zwei Klassen von geometrischen Goppa-Codes betrachten, die auf der P -adischen Potenzreihenentwicklung beruhen, wobei P ∈ ℙ_{F} eine rationale Stelle ist. Die Konstruktionen dieser Codes stammen von Xing, Niederreiter und Lam (siehe [25]), deshalb werden wir sie XNL-Codes nennen.

Ab jetzt sei also F/𝔽_{q} wieder ein beliebiger algebraischer Funktionenkörper mit Geschlecht g. Gegeben seien n + 1 verschiedene rationale Stellen P_{∞}, P_{1}, …, P_{n} und ein Divisor E ≥ 0 mit deg E = 2g und P_{∞} ∉ supp E. Als erstes wollen wir eine spezielle Basis von L(E) wählen.

Hilfssatz 3.3.7 Es gibt eine Basis w_{0}, w_{1}, …, w_{g} von L(E), sodass

ν_{P_{∞}}(w_{l}) = n_{l} mit 0 = n_{0} < n_{1} < ⋯ < n_{g} ≤ 2g.

Beweis. Zunächst gilt nach dem Satz von Riemann-Roch 2.6.4, dass

dim E = g + 1.  (3.18)

Außerdem folgt dim(E − P_{∞}) = g und dim(E − (2g + 1)P_{∞}) = 0. Deshalb existieren ganze Zahlen

0 = n_{0} < n_{1} < ⋯ < n_{g} ≤ 2g,

sodass

dim(E − n_{l}P_{∞}) = dim(E − (n_{l} + 1)P_{∞}) + 1,

für 0 ≤ l ≤ g ist. Für jedes 0 ≤ l ≤ g wählen wir ein Element

w_{l} ∈ L(E − n_{l}P_{∞})\L(E − (n_{l} + 1)P_{∞}).

Nach Konstruktion gilt ν_{P_{∞}}(w_{l}) = n_{l}. Wegen (3.18) genügt es zu zeigen, dass w_{0}, …, w_{g} linear unabhängig über 𝔽_{q} sind. Angenommen wir haben

∑_{l=0}^{g} a_{l}w_{l} = 0

mit a_{l} ∈ 𝔽_{q} und a_{k} ≠ 0 für ein 0 ≤ k ≤ g. Wir nehmen an, dass k minimal mit dieser Eigenschaft ist. Dann gilt

a_{k}w_{k} = − ∑_{l=k+1}^{g} a_{l}w_{l} ≠ 0.

Nun gilt einerseits: ν_{P_{∞}}(a_{k}w_{k}) = n_{k}, andererseits:

ν_{P_{∞}} (− ∑_{l=k+1}^{g} a_{l}w_{l}) ≥ min_{k+1≤l≤g}{ν_{P_{∞}}(w_{l})} = n_{k+1} > n_{k}.

Das ist ein Widerspruch, und damit ist der Hilfssatz bewiesen. □

Wie in der Konstruktion in Kapitel 3.2 (siehe (3.11)) wählen wir für 1 ≤ j ≤ n Elemente

f_{j} ∈ L(E + P_{j})\L(E).  (3.19)

Das ist – genauso wie dort – möglich nach dem Satz von Riemann-Roch 2.6.4, indem wir beachten, dass deg E = 2g ist.

Hilfssatz 3.3.8 Die Elemente w_{0}, w_{1}, …, w_{g}, f_{1}, f_{2}, …, f_{n} aus Hilfssatz 3.3.7 bzw. (3.19) sind linear unabhängig über 𝔽_{q}.

Beweis. Man zeigt dies genauso wie im Beweis von Hilfssatz 3.2.1. □

Wir wählen nun einen lokalen Parameter t für P_{∞} und setzen

t_{r} := \{ \begin{matrix}t^{r} & für r ∉ \{n_{0}, …, n_{g}\}, \\ w_{l} & für r = n_{l} ∈ \{n_{0}, …, n_{g}\} \end{matrix}

für r = 0, 1, 2, …, wobei n_{0}, …, n_{g} wie in Hilfssatz 3.3.7 sind. Dann gilt ν_{P_{∞}}(t_{r}) = r für alle r ≥ 0. Jedes f_{j} besitzt nach Satz 2.7.8 eine P_{∞}- Potenzreihenentwicklung bezüglich der Folge (t_{r})_{r≥0} der Form

f_{j} = ∑_{r=0}^{∞} a_{rj}t_{r}  (3.20)

mit a_{rj} ∈ 𝔽_{q} (man beachte: wegen P_{∞} ∉ supp (E + P_{j}) für 1 ≤ j ≤ n ist ν_{P_{∞}}(f_{j}) ≥ 0).

Wir wählen eine feste ganze Zahl m mit g ≤ m < n und definieren den Vektor c_{j} ∈ 𝔽_{q}^{m} für 1 ≤ j ≤ n durch

c_{j} = (â_{n_{0}j}, a_{1j}, …, â_{n_{1}j}, …, â_{n_{g}j}, …, a_{m+g j}),

wobei bedeutet, dass der zugehörige Eintrag weggelassen wird. Der Einfachheit halber schreiben wir

c_{j} = (c_{1j}, c_{2j}, …, c_{mj}).

Definieren wir jetzt eine m × n-Matrix H über 𝔽_{q} durch

H = (c_{1}^{T} , c_{2}^{T} , …, c_{n}^{T}) = ( \begin{matrix}c_{11} & c_{12} & ⋯ & c_{1n} \\ c_{21} & c_{22} & ⋯ & c_{2n} \\ ⋮ & ⋮ & & ⋮ \\ c_{m1} & c_{m2} & ⋯ & c_{mn} \end{matrix} ) .

Definition 3.3.9 Wir bezeichnen mit C_{F} = C_{F} (P_{∞}, P_{1}, …, P_{n}; E; m) den Linearcode mit Kontrollmatrix H und nennen ihn einen XNL-Code 1.Art.

Der Code C_{F} ist ein Linearcode der Länge n. Wir zeigen zunächst, dass er in die Klasse der geometrischen Goppa-Codes fällt, indem wir ihn auf die Konstruktion in Kapitel 3.2 zurückführen.

Satz 3.3.10 Gegeben seien n + 1 verschiedene rationale Stellen P_{∞}, P_{1}, …, P_{n}, ein positiver Divisor E mit deg E = 2g und P_{∞} ∉ supp E und eine positive ganze Zahl m mit g ≤ m < n. Dann gilt

C_{F} (P_{∞}, P_{1}, …, P_{n}; E; m) = C_{N S}(E; P_{1}, …, P_{n}; (m + g + 1)P_{∞}).

Beweis. Seien f_{j} wie in (3.19) und betrachte ihre P_{∞}- Potenzreihenentwicklung (3.20). Aus der Definition des Codes C_{F} wissen wir, dass der Vektor c = (c_{1}, …, c_{n}) ∈ 𝔽_{q}^{n} genau dann ein Codewort von C_{F} ist, wenn

∑_{i=1}^{n} a_{ji}c_{i} = 0 für alle j ∈ {0, …, m + g}\{n_{0}, …, n_{g}},

wobei die n_{i} wie in Hilfssatz 3.3.7 definiert werden. Daraus folgt

∑_{i=1}^{n} c_{i}f_{i} = ∑_{i=1}^{n} c_{i} (∑_{r=0}^{∞} a_{ri}t_{r}) = ∑_{r=0}^{∞} (∑_{i=1}^{n} c_{i}a_{ri}) t_{r}

= ∑_{r∈{n_{0},...,n_{g}}} (∑_{i=1}^{n} a_{ri}c_{i}) w_{r} + ∑_{r≥m+g+1} (∑_{i=1}^{n} a_{ri}c_{i}) t_{r}
= w + u,

mit w ∈ L(E) und u mit ν_{P_{∞}}(u) ≥ m + g + 1. Es folgt, dass

u ∈ L(E + ∑_{i=1}^{n} P_{i} − (m + g + 1)P_{∞}).

Daher ist c ein Codewort von C_{N S}. Umgekehrt sei c = (c_{1}, …, c_{n}) ein Codewort von C_{N S}. Dann gibt es ein f ∈ L(E + ∑_{i=1}^{n} P_{i} − (m + g + 1)P_{∞}), welches sich in der Form

f = ∑_{i=1}^{n} c_{i}f_{i} + w

darstellen läßt, wobei c_{i} ∈ 𝔽_{q} für i = 1, …, n und w ∈ L(E) ist. Man beachte, dass nach Hilfssatz 3.3.8 w_{0}, …, w_{g}, f_{1}, …, f_{n} eine Basis von L(D+ ∑_{i=1}^{n} P_{i}) bilden. Daher kann jedes Element von

L (E + ∑_{i=1}^{n} P_{i} − (m + g + 1)P_{∞}) ⊆ L (E + ∑_{i=1}^{n} P_{i})

eindeutig in obiger Form geschrieben werden. Betrachten wir die P_{∞}-Potenz-reihenentwicklung von f bezüglich der Folge (t_{r})_{r∈ℤ}, dann erhalten wir mit Hilfe von (3.20)

f = ∑_{i=1}^{n} c_{i} (∑_{r=0}^{∞} a_{ri}t_{r}) + w = ∑_{r=0}^{∞} (∑_{i=1}^{n} c_{i}a_{ri}) t_{r} + w

= ∑_{r∉{n_{0},...,n_{g}}} (∑_{i=1}^{n} c_{i}a_{ri}) t_{r} + w + ∑_{r∈{n_{0},...,n_{g}}} (∑_{i=1}^{n} c_{i}a_{ri}) .

Da ν_{P_{∞}}(f) ≥ (m + g + 1) − ν_{P_{∞}}(E) = m + g + 1 ist, erhalten wir

∑_{i=1}^{n} c_{i}a_{ri} = 0

für r ∈ {0, …, m + g}\{n_{0}, …, n_{g}} und

w = − ∑_{r∈{n_{0},...,n_{g}}} (∑_{i=1}^{n} c_{i}a_{ri}) .

Damit ist c ein Codewort von C_{F} und somit der Beweis geführt. □

Folgerung 3.3.11 Der Linearcode C_{F} (P_{∞}, P_{1}, …, P_{n}; E; m) ist ein [n, k, d]- Code über 𝔽_{q} mit

k ≥ n − m und d ≥ m − g + 1.

Beweis. Folgt sofort aus Satz 3.3.10 und Satz 3.2.4. □

Wir wollen noch eine zweite Konstruktion betrachten, die ebenfalls auf der Potenzreihenentwicklung an einer rationalen Stelle beruht. Anstatt des Divisors E vom Grad 2g verwenden wir diesmal einen nicht speziellen Divisor D ≥ 0 mit deg D = g, das heißt wir haben dim D = 1. Der folgende Hilfssatz sichert die Existenz eines solchen Divisors.

Hilfssatz 3.3.12 Der algebraische Funktionenkörper F/𝔽_{q} besitzt einen nicht speziellen Divisor D ≥ 0 mit deg D = g in jedem der folgenden Fälle:

(a) F/𝔽_{q} ist der rationale Funktionenkörper.

(b) F/𝔽_{q} hat Geschlecht g = 1 (in diesem Fall nennt man F einen elliptischen Funktionenkörper).

(c) F/𝔽_{q} hat mindestens vier rationale Stellen, wenn q = 2 ist, und mindestens zwei rationale Stellen, wenn q ≥ 3 gilt.

Beweis. (a) Wähle D gleich dem Nulldivisor.

(b) Nach der Hasse-Weil-Schranke 2.8.8 besitzt F/𝔽_{q} mindestens eine rationale Stelle P. Wähle D = P, dann gilt deg D = 1 = g und dim D = 1 (nach dem Satz von Riemann-Roch 2.6.4).

(c) Einen Beweis findet man z.B. in [13]. □

Seien P_{∞}, P_{1}, …, P_{n} n + 1 verschiedene rationale Stellen. Wie vorhin wählen wir für 1 ≤ j ≤ n Elemente

g_{j} ∈ L(D + P_{j})\L(D).  (3.21)

Dies ist aufgrund des Satzes von Riemann-Roch möglich, da D nicht speziell ist (siehe (3.11) und (3.19)). Dann gilt

Hilfssatz 3.3.13 Die Elemente 1, g_{1}, …, g_{n} aus (3.21) bilden eine Basis von L(D + ∑_{i=1}^{n} P_{i}).

Beweis. Zeigt man genauso wie im Beweis von Hilfssatz 3.2.1. □

Wähle einen lokalen Parameter t von P_{∞} und betrachte die P_{∞}- adische Potenzreihe von g_{j} bezüglich t

g_{j} = t^{−v} · ∑_{r=0}^{∞} b_{rj}t^{r}

wo v = ν_{P_{∞}}(D) ≥ 0 und alle Koeffizienten b_{rj} ∈ 𝔽_{q} sind. Für 1 ≤ j ≤ n definieren wir

c_{rj} = \{ \begin{matrix}b_{r−1 j} & für 1 ≤ r ≤ v, \\ b_{rj} & für r ≥ v + 1. \end{matrix}

Wir wählen wieder ein festes m mit g ≤ m < n und setzen

c_{j} = (c_{1j}, c_{2j}, …, c_{mj}) ∈ 𝔽_{q}^{m}.

Schlussendlich definieren wir die m × n-Matrix H durch

H = (c_{1}^{T} , c_{2}^{T} , …, c_{n}^{T}).

Definition 3.3.14 Der Code C_{S} = C_{S}(P_{∞}, P_{1}, P_{2}, …, P_{n}; D; m) ⊆ 𝔽_{q}^{n} ist der Linearcode mit Kontrollmatrix H. Wir nennen ihn XNL-Code 2.Art.

Wie vorhin erhalten wir die folgenden Aussagen:

Satz 3.3.15 Gegeben seien n+1 verschiedene rationale Stellen P_{∞}, P_{1}, …, P_{n}, ein nichtspezieller Divisor D ≥ 0 mit deg D = g und eine positive ganze Zahl m mit g ≤ m < n. Dann gilt

C_{S}(P_{∞}, P_{1}, …, P_{n}; D; m) = C_{N S}(D; P_{1}, …, P_{n}; (m + 1)P_{∞}).

Beweis. Der Nachweis verläuft genauso wie Satz 3.3.10. □

Folgerung 3.3.16 Der Linearcode C_{S}(P_{∞}, P_{1}, …, P_{n}; D; m) ist ein [n, k, d]- Code über 𝔽_{q} mit

k ≥ n − m und d ≥ m − g + 1.

Beweis. Dies ist eine unmittelbare Folgerung aus Satz 3.3.15 und Satz 3.2.4. □

3.4 Geometrische Goppa-Codes und die asymptotische Gilbert-Varshamov-Schranke

In diesem Abschnitt werden wir sehen, dass geometrische Goppa-Codes eine gute Familie von Codes sind (siehe Definition 1.5.14). Um gute Codes zu konstruieren, benötigen wir lange Codes. Betrachten wir also lange geometrische Goppa-Codes. Gegeben sei ein algebraischer Funktionenkörper F/𝔽_{q} mit N = N(F) rationalen Stellen. Dann ist die Länge eines geometrischen Goppa-Codes C_{L}(D, G) assoziiert zu den Divisoren D und G von F beschränkt durch N, da D die Summe von rationalen Stellen ist. Tatsächlich stellt dies die einzige Einschränkung an die Länge eines geometrischen Goppa-Codes dar.

Hilfssatz 3.4.1 Seien P_{1}, …, P_{n} verschiedene rationale Stellen von F/𝔽_{q}. Dann gibt es für jedes r ≥ 0 einen Divisor G mit deg G = r und P_{i} ∉ supp G für i = 1, …, n.

Beweis. Der Hilfssatz ist trivial, falls eine weitere rationale Stelle Q existiert, die verschieden von P_{1}, …, P_{n} ist. In diesem Fall setzen wir G := rQ. Falls P_{1}, …, P_{n} alle rationalen Stellen von F/𝔽_{q} sind, wählen wir einen Divisor G ∼ rP_{1}, sodass ν_{P_{i}}(G) = 0 ist, für i = 1, …, n. Dies ist möglich nach dem schwachen Approximationssatz 2.2.7. □

Die Hasse-Weil-Schranke gibt uns eine Schranke für die Anzahl der rationalen Stellen von F/𝔽_{q} an.

Tsfasman, Vlǎdut und Zink gaben 1982 eine ”explizite“ Beschreibung einer Folge von geometrischen Goppa-Codes über 𝔽_{p^{2}}, deren Rate und relative Minimaldistanz gegen die asymptotische Gilbert-Varshamov-Schranke konvergieren (siehe [22]). Ihre Konstruktion verwendet so genannte Shimura-Modular-Kurven und benötigt viel algebraische Geometrie. Die Funktionenkörper, die von Tsfasman, Vlǎdut und Zink verwendet wurden, sind Beispiele für die Richtigkeit des folgenden Satzes, den wir nicht beweisen.

Satz 3.4.2 Es sei q = p^{2} mit p ≥ 7 eine Primzahl. Dann gibt es eine Familie algebraischer Funktionenkörper F^{(ν)}/𝔽_{p^{2}} mit Geschlecht g^{(ν)} = g(F^{(ν)}) ⟶ ∞ so, dass die Anzahl N^{(ν)} = N(F^{(ν)}) der rationalen Stellen gegen unendlich konvergiert, aber g^{(ν)}/N^{(ν)} gegen 1/(p − 1) geht.

Beweis. Einen Beweis findet man in [21]. □

Mit Hilfe dieses Satzes kann man die Existenz einer guten Familie von geometrischen Goppa-Codes sofort ableiten. Zunächst definieren wir:

Definition 3.4.3

(a) N_{q}(g) := max{N(F) | F ist ein algebraischer Funktionenkörper über 𝔽_{q} mit Geschlecht g}.

(b) A(q) := lim sup_{g→∞} N_{q}(g)/g.

Satz 3.4.4 (Drinfeld-Vlǎdut-Schranke) A(q) ≤ q^{1/2} − 1.

Beweis. Einen Beweis, der den Satz von Hasse-Weil 2.8.7 verwendet, findet man z.B. in [19]. □

Folgerung 3.4.5 A(q) = q^{1/2} − 1, falls q = p^{2} mit p ≥ 7 eine Primzahl ist.

Beweis. Folgt aus Satz 3.4.2 und der Drinfeld-Vlǎdut-Schranke 3.4.4. □

Es sei bemerkt, dass Satz 3.4.2 und Folgerung 3.4.5 bereits dann gelten, wenn q ein Quadrat ist.

Satz 3.4.6 Es sei A(q) > 1. Dann gibt es für alle 0 ≤ δ ≤ 1 − A(q)^{−1} eine Folge von Linearcodes C_{n} ⊆ 𝔽_{q}^{n}, sodass die relative Minimaldistanz gegen eine Zahl ≥ δ und die Rate gegen eine Zahl ≥ (1 − A(q)^{−1}) − δ konvergieren.

Beweis. Sei δ ∈ [0, 1 − A(q)^{−1}]. Wähle eine Folge von Funktionenkörpern F_{i}/𝔽_{q} mit Geschlecht g_{i}, sodass

g_{i} ⟶ ∞ und n_{i}/g_{i} ⟶ A(q),  (3.22)

wobei n_{i} := N(F_{i}) ist. Das ist möglich, sofern n_{i} → ∞ für i → ∞ strebt. Wähle r_{i} > 0, sodass

r_{i}/n_{i} ⟶ 1 − δ.  (3.23)

Sei D_{i} die Summe aller rationalen Stellen von F_{i}/𝔽_{q}, dann ist deg D_{i} = n_{i}. Nach Hilfssatz 3.4.1 gibt es einen Divisor G_{i} von F_{i}/𝔽_{q} mit deg G_{i} = r_{i} und supp G_{i} ∩ supp D_{i} = ∅. Betrachte die Codes C_{i} := L(D_{i}, G_{i}). Diese C_{i} sind [n_{i}, k_{i}, d_{i}]-Codes, deren Parameter k_{i} und d_{i} nach Folgerung 3.1.3 folgendermaßen abgeschätzt werden können:

k_{i} ≥ deg G_{i} + 1 − g_{i} = r_{i} + 1 − g_{i} und d_{i} ≥ n_{i} − deg G_{i} = n_{i} − r_{i}.

Daher gilt

R_{i} := \frac{k_{i}}{n_{i}} ≥ \frac{r_{i} + 1}{n_{i}} − \frac{g_{i}}{n_{i}} und δ_{i} := \frac{d_{i}}{n_{i}} ≥ 1 − \frac{r_{i}}{n_{i}} .  (3.24)

Wir können o.B.d.A. annehmen, dass die Folgen (R_{i})_{i≥1} und (δ_{i})_{i≥1} konvergieren, andernfalls betrachten wir geeigenete Teilfolgen. Gelte R_{i} → R und δ_{i} → δ̃. Aus (3.22), (3.23) und (3.24) folgt R ≥ 1 − δ − A(q)^{−1} und δ̃ ≥ δ und damit die Behauptung. □

Als unmittelbare Folgerung erhalten wir:

Satz 3.4.7 (Tsfasman-Vlǎdut-Zink-Schranke) Es sei q = p^{2} mit p ≥ 7 eine Primzahl. Dann gibt es für alle 0 ≤ δ ≤ 1 − 1/(p − 1) eine Folge von Linearcodes C_{n} ⊆ 𝔽_{q}^{n} so, dass die relative Minimaldistanz gegen eine Zahl ≥ δ und die Rate gegen eine Zahl ≥ (1 − 1/(p − 1)) − δ konvergieren.

Beweis. Folgt sofort aus Satz 3.4.5 und Satz 3.4.6. □

Falls q = p^{2} ≥ 49 ist, dann ist die Tsfasman-Vlǎdut-Zink-Schranke in einem gewissen Intervall besser als die Gilbert-Varshamov-Schranke. Das heißt, dass geometrische Goppa-Codes die Gilbert-Varshamov-Schranke nicht nur erreichen, sondern sie sogar noch übertreffen.

Satz 3.4.8 Sei q = p^{2} mit p ≥ 7 eine Primzahl. Dann ist für δ = (q − 1)/(2q−1) die Tsfasman-Vlǎdut-Zink-Schranke besser als die Gilbert-Varsha-mov-Schranke.

Beweis. Für p = 7 berechnen wir log_{49}(97) ≈ 1.1755 > 7/6. Daher ist 1/(p − 1) < log_{q}(2q − 1) − 1. Da die linke Seite dieser Ungleichung mit wachsendem p stärker fällt als die rechte Seite, bleibt die Ungleichung für größer werdende p richtig. Daher gilt in diesem Fall,

(1 − 1/(p − 1)) − δ > 1 − δ − log_{q}(2q − 1) + 1 = 1 − H_{q}(δ),

woraus die Behauptung folgt. □

H. Niederreiter und C. P. Xing konnten im Jahr 1998 sogar noch eine weitere Verbesserung erzielen: Sie zeigten, dass für q kein Quadrat und keine Primzahl die asymptotische Gilbert-Varshamov-Schranke, mit Hilfe von geometrischen Goppa-Codes, immer noch gebrochen werden kann. Details dazu findet man in [14].

Die Bedeutung der AG-Codes liegt also darin, dass sie hervorragende asymptotische Eigenschaften besitzen. Um diese nützen zu können benötigt man aber möglichst viele rationale Stellen. Wenn der Funktionenkörper F/𝔽_{q} Geschlecht g = 0 hat, dann gibt es nach der Hasse-Weil-Schranke 2.8.8 genau q + 1 rationale Stellen. Wir müssen also Funktionenkörper mit Geschlecht g > 0 betrachten. Der Preis den man aber dafür zu zahlen hat, ist der, dass das Rechnen in einem solchen Funktionenkörper wesentlich schwieriger ist. Insbesondere die Berechnung des Geschlechts stellt ein großes Problem dar. Aus diesem Grund haben wir auch keine explizite Angabe von Codes, welche die asymptotische Gilbert-Varshamov-Schranke erreichen, kennengelernt (solche expliziten Darstellungen gibt es z.B. seit kurzem auch von Garcia und Stichtenoth, siehe [18]).

Verallgemeinerte AG-Codes

In diesem Kapitel wollen wir Goppas Methode, Codes mit Hilfe von algebraischen Funktionenkörpern zu konstruieren, in dem Sinn verallgemeinern, dass die Verwendung von Stellen beliebig hohen Grades zugelassen wird. Damit ist es möglich Linearcodes zu konstruieren, die alle bisher dagewesenen übertreffen. Diese Resultate stammen von Xing, Niederreiter und Lam (siehe [15], [26] und [16]).

4.1 Konstruktion nach Xing - Niederreiter - Lam

Die Idee dieser Konstruktion besteht darin, einige ”innere“ Codes mit einem ”äußeren“ Code - einem AG-Code - zu verknüpfen, um einen neuen Code zu gewinnen.

Wir betrachten also wieder einen algebraischen Funktionenkörper F/𝔽_{q} mit Geschlecht g. Gegeben seien s verschieden Stellen P_{1}, …, P_{s} und ein Divisor G von F mit supp G∩{P_{1}, …, P_{s}} = ∅. Für i = 1, …, s seien lineare [n_{i}, k_{i} = deg P_{i}, d_{i}]-Codes C_{i} ⊆ 𝔽_{q}^{n_{i}} gegeben. Weiters seien π_{i} : F_{P_{i}} → C_{i} fest gewählte 𝔽_{q}-lineare Isomorphismen vom Restklassenkörper F_{P_{i}} auf den Linearcode C_{i}. Wir betrachten jetzt die Abbildung

π : \{ \begin{matrix}L(G) & ⟶ & 𝔽_{q}^{n}, \\ f & ⟼ & (π_{1}(f(P_{1})), …, π_{s}(f(P_{s}))), \end{matrix}  (4.1)

wobei n = ∑_{i=1}^{s} n_{i} gilt. Klarerweise ist π eine 𝔽_{q}-lineare Abbildung. Wir definieren:

Definition 4.1.1 Wir nennen

C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) := π(L(G))

einen verallgemeinerten AG-Code.

Offensichtlich ist C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) ein Linearcode über 𝔽_{q} der Länge n. Außerdem ist klar, dass, falls alle Stellen P_{i} rational und n_{i} = k_{i} = d_{i} = 1 für 1 ≤ i ≤ s gewählt werden, C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) ein geometrischer Goppa-Code ist. Wenn man nämlich π_{i} = id_{𝔽_{q}} wählt für i = 1, …, s, dann ist C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) = C_{L}(P_{1} +⋯+P_{n}, G). In jedem anderen Fall erhält man einen zu C_{L}(P_{1} + ⋯ + P_{n}, G) äquivalenten Code.

Als nächstes wollen wir Abschätzungen für die Parameter von C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) herleiten. Wir zeigen zuerst den folgenden Hilfssatz:

Hilfssatz 4.1.2 Mit den Notationen von oben gilt: Falls

deg G < ∑_{i=1}^{n} k_{i},

dann ist π injektiv.

Beweis. Sei h ∈ L(G) mit π(h) = 0. Dann ist auch

π_{i}(h(P_{i})) = 0 für alle 1 ≤ i ≤ s.

Damit ist h(P_{i}) = 0 für alle 1 ≤ i ≤ s, da die π_{i} Isomorphismen sind. Es folgt

h ∈ L (G − ∑_{i=1}^{s} P_{i}) .

Wegen

deg G < ∑_{i=1}^{s} k_{i} = deg (∑_{i=1}^{s} P_{i})

folgt h = 0 und damit die Behauptung. □

Satz 4.1.3 Seien die Bezeichnungen wie oben. Außerdem gelte wieder

deg G < ∑_{i=1}^{s} k_{i}.

Dann ist C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) ein [n, k, d]-Code mit den Parametern

k ≥ deg G + 1 − g,
d ≥ ∑_{i=1}^{s} d_{i} − deg G − max_{R} {∑_{i∈R}(d_{i} − k_{i})} ,

wobei das Maximum über alle Teilmengen R von {1, 2, …, s} gebildet, und eine leere Summe, wie gewöhnlich, als 0 definiert wird. Weiters gilt: k = deg G + 1 − g, falls deg G ≥ 2g − 1.

Beweis. Es folgt sofort aus Hilfssatz 4.1.2 und dem Satz von Riemann-Roch 2.6.4, dass

k = dim L(G) = dim G ≥ deg G + 1 − g,

mit Gleichheit, falls deg G ≥ 2g − 1 ist. Wählen wir jetzt ein Element f ∈ L(G) so, dass das Codewort π(f) Gewicht d hat. Wir können annehmen, dass f ≠ 0 sei, da sonst der Code trivial ist. Sei

S = {i ∈ {1, 2, …, s} | f(P_{i}) = 0}.  (4.2)

Da 0 ≠ f ∈ L(G − ∑_{i∈S} P_{i}) gilt, folgt

deg G ≥ deg (∑_{i∈S} P_{i}) = ∑_{i∈S} k_{i} = ∑_{i∈S} d_{i} − ∑_{i∈S}(d_{i} − k_{i}).

Andererseits gilt

d = wt(π(f)) = ∑_{i=1}^{s} wt(π_{i}(f(P_{i}))) = ∑_{i∉S} wt(π_{i}(f(P_{i}))) ≥ ∑_{i∉S} d_{i}.

Wenn wir diese beiden Ungleichungen kombinieren, erhalten wir

wt(π(f)) + deg G ≥ ∑_{i=1}^{s} d_{i} − ∑_{i∈S}(d_{i} − k_{i})

und daraus folgt die gewünschte Schranke für d. □

Folgerung 4.1.4 Zusätzlich zu den Voraussetzungen in Satz 4.1.3 gelte k_{i} ≥ d_{i} für 1 ≤ i ≤ s. Dann gilt für die Minimaldistanz d von C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s})

d ≥ ∑_{i=1}^{s} d_{i} − deg G.

Beweis. Folgt sofort aus Satz 4.1.3. □

Folgerung 4.1.5 Es gelten die Voraussetzungen von Satz 4.1.3. Für die Minimaldistanz d von C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) folgt dann

d ≥ δ := min {∑_{i∉S} d_{i} | S ∈ X} ,

wobei die Menge X folgendermaßen definiert ist:

X := {S ⊆ {1, 2, …, s} | ∑_{i∈S} k_{i} ≤ deg G} .

Beweis. Sei 0 ≠ f ∈ L(G), sodass das Codewort π(f) Gewicht d hat. Im Beweis des letzten Satzes haben wir folgende Ungleichungen gezeigt:

deg G ≥ ∑_{i∈S} k_{i} und d ≥ ∑_{i∉S} d_{i},

wobei S durch (4.2) definiert ist. Daraus folgt die Behauptung. □

Man beachte, dass die Folgerung 3.1.3, welche die Abschätzungen für die Parameter eines geometrischen Goppa-Codes C_{L}(D, G) – im Fall, dass deg G < n ist – liefert, jetzt ein Spezialfall von Satz 4.1.3 ist. Außerdem sei bemerkt, dass sich jeder lineare [n, k, d]-Code über 𝔽_{q} in trivialer Weise als ein verallgemeinerter AG-Code realisieren läßt: Sei F = 𝔽_{q}(x) der rationale Funktionenkörper, P_{∞} der Pol von x und wähle eine Stelle P ∈ ℙ_{F} mit Grad deg P = k. Sei π : F_{P} → C ein 𝔽_{q}-linearer Isomorphismus. Dann gilt

C = C(P; (k − 1)P_{∞}; C),

da die Abbildung L((k − 1)P_{∞}) → C ⊆ 𝔽_{q}^{n} definiert durch f ↦ π(f(P)) nach Hilfssatz 4.1.2 injektiv, und nach dem schwachen Approximationssatz 2.2.7 surjektiv ist.

Wir wollen noch eine spezielle Klasse von Codes untersuchen, die eine Verallgemeinerung der Konstruktion von Xing - Niederreiter - Lam und Özbudak - Stichtenoth ist und von Xing, Niederreiter und Lam stammt (siehe [15]). Auch bei dieser Konstruktion werden Stellen beliebigen Grades verwendet. Wir werden sehen, dass es sich dabei um spezielle verallgemeinerte AG-Codes handelt.

Wie immer sei F/𝔽_{q} ein algebraischer Funktionenkörper mit Geschlecht g. Wir wählen einen nicht speziellen Divisor B und s verschiedene Stellen P_{1}, …, P_{s} vom Grad deg P_{i} = k_{i} (i = 1, …, s). Weiters setzen wir

n = ∑_{i=1}^{s} k_{i}.

Da B nicht speziell ist und B + P_{i} ≥ B für 1 ≤ i ≤ s folgt nach Hilfssatz 2.6.12

dim(B + P_{i}) = dim B + k_{i}.

Daher können wir k_{i} Elemente f_{i,1}, …, f_{i,k_{i}} ∈ L(B + P_{i}) finden, die linear unabhängig modulo L(B) sind. Es gilt dann der folgende Hilfssatz:

Hilfssatz 4.1.6 Die n Elemente f_{1,1}, …, f_{1,k_{1}}, f_{2,1}, …, f_{s,k_{s}} bilden eine Basis von L(B + ∑_{i=1}^{s} P_{i}) modulo L(B).

Beweis. Mit demselben Argument wie zuvor sieht man:

dim (B + ∑_{i=1}^{s} P_{i}) = dim B + n.

Daher genügt es zu zeigen, dass f_{1,1}, …, f_{1,k_{1}}, f_{2,1}, …, f_{s,k_{s}} linear unabhängig modulo L(B) über 𝔽_{q} sind. Angenommen, dass

w + ∑_{i=1}^{s} h_{i} = 0,

wobei w ∈ L(B) und h_{i} eine 𝔽_{q}-Linearkombination von f_{i,1}, …, f_{i,k_{i}} für 1 ≤ i ≤ s ist. Wir können h_{j} ∉ L(B) für mindestens ein 1 ≤ j ≤ s annehmen. Dann schreiben wir die letzte Gleichung um in

−h_{j} = w + ∑_{i=1,i≠j}^{s} h_{i}.

Es ist h_{j} ∈ L(B + P_{j})\L(B) und daher

ν_{P_{j}}(−h_{j}) = ν_{P_{j}}(h_{j}) ≤ −ν_{P_{j}}(B) − 1.

Andererseits erhalten wir aus h_{i} ∈ L(B + P_{i}) für 1 ≤ i ≤ s

ν_{P_{j}} (w + ∑_{i=1,i≠j}^{s} h_{i}) ≥ −ν_{P_{j}}(B),

was ein Widerspruch ist. Damit gilt die Behauptung. □

Aus Hilfssatz 4.1.6 folgt nun, dass jedes f ∈ L(B + ∑_{i=1}^{s} P_{i}) eine eindeutige Darstellung der Form

f = ∑_{i=1}^{s} ∑_{j=1}^{k_{i}} c_{i,j}f_{i,j} + w

mit c_{i,j} ∈ 𝔽_{q} und w ∈ L(B) besitzt. Wie in Abschnitt 3.2 erhalten wir eine surjektive 𝔽_{q}-lineare Abbildung

α : \{ \begin{matrix}L(B + ∑_{i=1}^{s} P_{i}) & ⟶ & 𝔽_{q}^{n}, \\ f & ⟼ & (c_{1,1}, …, c_{s,k_{s}}) \end{matrix}  (4.3)

mit dem Kern ker(α) = L(B).

Sei A ein weiterer Divisor, sodass

A ≥ 0 und supp A ∩ {P_{1} …, P_{s}} = ∅

gilt. Der Grad von A sei m mit g < m ≤ n. Wir definieren:

Definition 4.1.7 Seien B, P_{1}, …, P_{s}, A und die Abbildung α wie oben festgelegt. Dann definieren wir den Code C_{V -N S}(B; P_{1}, …, P_{s}; A) ⊆ 𝔽_{q}^{n} durch

C_{V -N S} := C_{V -N S}(B; P_{1}, …, P_{n}; A) = α (L (B + ∑_{i=1}^{s} P_{i} − A)) .

Diese Konstruktion ist eine offensichtliche Verallgemeinerung der Konstruktion in Abschnitt 3.2. Wir zeigen jetzt, dass es sich beim Code C_{V -N S}(B; P_{1} …, P_{s}; A) um einen verallgemeinerten AG-Code handelt.

Satz 4.1.8 Seien A, B, P_{1}, …, P_{s} wie vorhin. Dann ist C_{V -N S}(B; P_{1}, …, P_{s}; A) äquivalent zu C(P_{1}, …, P_{s}; G; C_{1}, …, C_{s}) mit

C_{i} = 𝔽_{q}^{k_{i}} und [n_{i}, k_{i}, d_{i}] = [k_{i}, k_{i}, 1],

wobei k_{i} = deg P_{i} für i = 1, …, s ist und

G ∼ B + ∑_{i=1}^{s} P_{i} − A.

Beweis. Zunächst findet man mit dem schwachen Approximationssatz 2.2.7 ein Element z mit

ν_{P_{i}}(z) = ν_{P_{i}}(B + P_{i}), für i = 1, …, s.

Dann ist ν_{P_{i}}(zf_{i,j}) = ν_{P_{i}}(z) + ν_{P_{i}}(f_{i,j}) = 0 und die Restklassen

(zf_{i,j})(P_{i}), j = 1, …, k_{i}

bilden eine Basis des Restklassenkörpers F_{P_{i}} über 𝔽_{q}. Angenommen wir haben nämlich eine nicht triviale 𝔽_{q}-Linearkombination

∑_{j=1}^{k_{i}} a_{j}(zf_{i,j})(P_{i}) = 0

mit a_{j} ∈ 𝔽_{q}. Dann gilt einerseits

∑_{j=1}^{k_{i}} a_{j}(zf_{i,j}) ∈ P_{i}.

Andererseits ist aber, wegen a_{j}(zf_{i,j}) ∈ O_{P_{i}}^{∗},

∑_{j=1}^{k_{i}} a_{j}(zf_{i,j}) ∈ O_{P_{i}}^{∗},

was nicht gleichzeitig möglich sein kann. Wir definieren die lineare Abbildung

π_{i} : \{ \begin{matrix}F_{P_{i}} & ⟶ & C_{i} := 𝔽_{q}^{k_{i}}, \\ (zf_{i,j})(P_{i}) & ⟼ & e_{j}^{(i)} \end{matrix}

wobei e_{j}^{(i)} = (0, …, 0, 1, 0, …, 0) ∈ 𝔽_{q}^{k_{i}} den j-ten Vektor der kanonischen Basis von 𝔽_{q}^{k_{i}} bezeichnet. Weiters sei der Divisor

G := B + ∑_{i=1}^{s} P_{i} − A − (z).

Offensichtlich ist G äquivalent zu B + ∑_{i=1}^{s} P_{i} − A. Weiters definieren wir die Abbildung

φ : \{ \begin{matrix}L(B + ∑_{i=1}^{s} P_{i} − A) & ⟶ & L(G) \\ f & ⟼ & zf. \end{matrix}

Die Abbildung φ ist ein 𝔽_{q}-linearer Isomorphismus (siehe Hilfssatz 2.4.9 (b)). Wie im Beweis von Satz 3.2.3 betrachten wir das Diagramm

L (B + ∑_{i=1}^{s} P_{i} − A) ⟶ L(G)
↘  ↙
𝔽_{q}^{n}

wobei α : L(B + ∑_{i=1}^{s} P_{i} − A) → 𝔽_{q}^{n} durch (4.3) und π : L(G) → 𝔽_{q}^{n} durch (4.1) definiert sind. Wie man leicht sieht ist dieses Diagramm kommutativ. Sei nämlich

f ∈ L (B + ∑_{i=1}^{n} P_{i} − A) .

Wir setzen

f = ∑_{i=1}^{s} ∑_{j=1}^{k_{i}} c_{i,j}f_{i,j} + w

mit c_{i,j} ∈ 𝔽_{q} und w ∈ L(B) (das geht nach Hilfssatz 4.1.6). Dann ist (c_{1,1}, …, c_{s,k_{s}}) = α(f). Andererseits gilt

π_{l}((zf)(P_{l})) = π_{l} ((∑_{i=1}^{s} ∑_{j=1}^{k_{i}} c_{i,j}(zf_{i,j}) + zw) (P_{l}))

= π_{l} (∑_{j=1}^{k_{l}} c_{l,j}(zf_{l,j})(P_{l}))

= ∑_{j=1}^{k_{l}} c_{l,j}e_{j}^{(l)} = (c_{l,1}, …, c_{l,k_{l}})

für alle 1 ≤ l ≤ s, nach Wahl von z und da ν_{P_{l}}(zf_{i,j}) = ν_{P_{l}}(z) + ν_{P_{l}}(f_{i,j}) ≥ ν_{P_{l}}(B) + 1 − ν_{P_{l}}(B) = 1 > 0 für l ≠ i und genauso ν_{P_{l}}(zw) ≥ 1 > 0 ist. Also ist π(φ(f)) = α(f). Daher gilt

C_{V -N S} = α (L (B + ∑_{i=1}^{s} P_{i} − A)) = π(L(G))
= C(P_{1}, …, P_{s}; G; 𝔽_{q}^{k_{1}}, …, 𝔽_{q}^{k_{s}}).
□

Als Folgerung können wir jetzt die Parameter des Codes C_{V -N S}(B; P_{1}, …, P_{s}; A) abschätzen. Man beachte auch hier wieder, die offensichtliche Verallgemeinerung von Satz 3.2.4.

Satz 4.1.9 Sei B ein nicht spezieller Divisor, und P_{1}, …, P_{s} verschiedene Stellen von F/𝔽_{q}. Weiters sei A ein positiver Divisor von F mit g < deg A ≤ n und supp A∩{P_{1}, …, P_{s}} = ∅. Dann ist C_{V -N S}(B; P_{1}, …, P_{s}; A) ein linearer [n, k, d]-Code über 𝔽_{q} mit

n = ∑_{i=1}^{s} k_{i}, k ≥ deg B − deg A + n + 1 − g, d ≥ δ,

wobei k_{i} = deg P_{i} für 1 ≤ i ≤ s und δ die kleinste Kardinalität einer Teilmenge R von {1, …, s} ist, für welche ∑_{i∈R} k_{i} ≥ deg A−deg B gilt. Weiters folgt: k = deg B − deg A + n + 1 − g, falls deg B − deg A + n + 1 − g ≥ g.

Beweis. Folgt sofort aus Satz 4.1.8, Satz 4.1.3 und Folgerung 4.1.5. □

Eine weitere untere Schranke für δ erhält man, indem man R ⊆ {1, …, s} mit ∑_{i∈R} k_{i} ≥ deg A − deg B und |R| = δ nimmt und beachtet, dass

deg A − deg B ≤ ∑_{i∈R}((k_{i} − 1) + 1) ≤ ∑_{i=1}^{s}(k_{i} − 1) + δ.

Dann gilt nämlich

δ ≥ deg A − deg B − ∑_{i=1}^{s}(k_{i} − 1).

Im nächsten Abschnitt werden wir sehen, welchen Gewinn verallgemeinerten AG-Codes gegenüber Goppas Konstruktion bedeuten.

4.2 Gewinn gegenüber Goppas Konstruktion

In diesem Abschnitt wollen wir zunächst zeigen, dass verallgemeinerte AG-Codes besser sind als geometrische Goppa-Codes. Indem wir Stellen höheren Grades verwenden, können wir nämlich mit der letzten Konstruktion in Abschnitt 4.1, Codes gewinnen, die eine bessere Schranke für k + d haben, als geometrische Goppa-Codes.

Wir bezeichnen mit g_{q}(N) das kleinste g, sodass ein algebraischer Funktionenkörper F/𝔽_{q} mit Geschlecht g und mit mindestens N rationalen Stellen existiert. Der hier verwendete Wert für g_{q}(N) stammt aus einer Tabelle von [12].

Sei F der rationale Funktionenkörper über 𝔽_{2}. Für P_{1}, …, P_{s} wählen wir drei rationale Stellen von F/𝔽_{2}, eine Stelle vom Grad 2, und zwei Stellen vom Grad 3. A sei eine Stelle von F/𝔽_{2} vom Grad 7 und B sei ein nicht spezieller Divisor von F/𝔽_{2}, zum Beispiel einer dessen Existenz nach Satz 3.3.12 gesichert ist. Dann erhalten wir einen binären Linearcode C_{V -N S}(B; P_{1}, …, P_{s}; A) der Länge 11 und nach Satz 4.1.9 gilt k + d ≥ 8. Goppas Konstruktion liefert uns – zum Vergleich – nur einen binären Linearcode der Länge 11 mit k + d ≥ 11 − g_{2}(11) + 1 = 4.

Auf diese Art und Weise lassen sich leicht weiter Beispiele erzeugen, welche die Schwäche Goppas Konstruktion aufzeigen.

Zum Schluß wollen wir noch einige Beispiele für verallgemeinerte AG-Codes präsentieren, welche die derzeit besten mit diesen Parametern sind. Dabei betrachten wir q-äre Linearcodes für q = 2, 3. Bekanntlich ist es schwierig, gute q-äre geomtetrische Goppa-Codes für kleine q zu bekommen.

Wir denken uns die Stellen von F/𝔽_{q} mit nichtabsteigendem Grad aufgelistet und es seien P_{1}, P_{2}, …, P_{s} die ersten s Stellen von dieser Liste. Wir wählen stets einen Divisor G mit deg G = m und supp G ∩ {P_{1}, …, P_{s}} = ∅. Die abgeschätzten Parameter erhält man bei allen Beispielen aus Satz 4.1.3 und Folgerung 4.1.4.

1. Beispiel: Sei F = 𝔽_{2}(x, y) der durch

y^{2} + xy = x^{3} + x

definierte Funktionenkörper. Das Geschlecht von F ist 1 und die Zetafunktion von F lautet

Z(t) = \frac{2t^{2} + t + 1}{(1 − t)(1 − 2t)}.

Außerdem gilt B_{1} = 4, B_{2} = 2, B_{3} = 0, B_{4} = 2 (B_{r} bezeichnet die Anzahl der Stellen von Grad r).

(a) Wenn wir s = 6, [n_{i}, k_{i}, d_{i}] = [1, 1, 1] für 1 ≤ i ≤ 4, und [n_{i}, k_{i}, d_{i}] = [3, 2, 2] für i = 5, 6 setzen, erhalten wir einen binären Linearcode C(P_{1}, …, P_{6}; G; C_{1}, …, C_{6}) mit Parametern

[10, m, 8 − m], für 1 ≤ m ≤ 7.

(b) Wenn wir s = 7, [n_{i}, k_{i}, d_{i}] = [1, 1, 1] für 1 ≤ i ≤ 4, [n_{i}, k_{i}, d_{i}] = [3, 2, 2] für i = 5, 6 und [n_{7}, k_{7}, d_{7}] = [8, 4, 4] setzen, erhalten wir einen binären Linearcode C(P_{1}, …, P_{7}; G; C_{1}, …, P_{7}) mit Parametern

[18, m, 12 − m], für 1 ≤ m ≤ 11.

2. Beispiel: Sei F = 𝔽_{3}(x, y) der durch

y^{2} = 2x^{4} + x^{2} + 1

definierte Funktionenkörper. Das Geschlecht von F ist 1 und die Zetafunktion von F lautet

Z(t) = \frac{3t^{2} + 2t + 1}{(1 − t)(1 − 3t)}.

Außerdem gilt B_{1} = 6, B_{2} = 3, B_{3} = 4.

(a) Wenn wir s = 7, [n_{i}, k_{i}, d_{i}] = [1, 1, 1] für 1 ≤ i ≤ 6 und [n_{7}, k_{7}, d_{7}] = [3, 2, 2] wählen, erhalten wir einen Linearcode C(P_{1}, …, P_{7}; G; C_{1}, …, C_{7}) über 𝔽_{3} mit Parametern

[9, m, 8 − m], für 1 ≤ m ≤ 7.

(b) Wenn wir s = 9, [n_{i}, k_{i}, d_{i}] = [1, 1, 1] für 1 ≤ i ≤ 6 und [n_{i}, k_{i}, d_{i}] = [3, 2, 2] für 7 ≤ i ≤ 9 wählen, erhalten wir einen Linearcode C(P_{1}, …, P_{9}; G; C_{1}, …, C_{9}) über 𝔽_{3} mit den Parametern

[15, m, 12 − m], für 1 ≤ m ≤ 11.

Die folgende Tabelle gibt eine Reihe von Codes aus den letzten Beispielen an, die bestmöglich sind, in dem Sinne, dass die Minimaldistanz eine bekannte obere Schranke für die Minimaldistanz d eines q-ären Linearcodes von gegebener Länge n und Dimension k erreicht.

q [n, k, d] Beispiel
2 [10, 2, 6] 1(a)
2 [10, 3, 5] 1(a)
2 [10, 4, 4] 1(a)
2 [18, 4, 8] 1(b)
3 [9, 2, 6]  2(a)
3 [15, 3, 9] 2(b)

Weitere Beispiele, welche zeigen wie gut verallgemeinerte AG-Codes sind, findet man in [5] und [26].

Die verallgemeinerten AG-Codes sind also eine effektive und weitreichende Verallgemeinerung der geometrischen Goppa-Codes. Es bleibt die Hoffnung, dass damit in Zukunft Linearcodes mit guten Fehlerkorrektureigenschaften konstruiert werden können. Dabei sind natürlich noch viele Probleme offen:

• Für die Konstruktion von verallgemeinerten AG-Codes benötigt man Funktionenkörper mit einer ausgewogenen Balance zwischen der Anzahl der Stellen kleinen Grades. Nach einem bekannten Prinzip (siehe [21]) besitzt nämlich ein Funktionenkörper mit maximal vielen rationalen Stellen bei gegebenen Geschlecht nur wenige Stellen anderer kleiner Grade. Wie kann man also geeignete Funktionenkörper wählen?

• Wie sehen Decodierungsalgorithmen für verallgemeinerte AG-Codes aus? Können damit auch interessante Rückschlüsse auf geometrische Goppa-Codes gemacht werden?

• Gibt es eine einfachere Theorie für geometrische Goppa-Codes und verallgemeinerte AG-Codes?

• Was passiert, wenn man andere bekannte Methoden der Codierungstheorie auf geometrische Goppa-Codes oder verallgemeinerte AG-Codes anwendet?

Wenn diese Probleme gelöst sind, könnten Codes, die von algebraischen Funktionenkörpern kommen, in Zukunft vielleicht die entscheidende Rolle in der Codierungstheorie spielen.

Literaturverzeichnis

[1] E. Artin: Algebraic numbers and algebraic functions, Gordon and Breach, New York, 1967.

[2] R. C. Bose and D. K. Ray-Chaudhuri: “On a class of error correcting binary group codes”, Info. and Control 3, 68 - 79, 1960.

[3] C. Chevalley: Introduction to the theory of algebraic functions of one variable, American Mathematical Society, Providence, RI, 1951.

[4] M. Deuring: Lectures on the theory of algebraic functions of one variable, Lecture Notes in Mathematics 314, Springer-Verlag, Berlin, 1973.

[5] C. Ding - H. Niederreiter - C. P. Xing: “Some New Codes from Algebraic Curves”, erscheint in IEEE Trans. Inform. Theory, 2000.

[6] V. D. Goppa: “A new class of linear error-correcting codes”, Problems of Info. Transmission 8(3), 207 - 212, 1970.

[7] V. D. Goppa: “Codes on algebraic curves”, Dokl. Akad. Nauk SSSR 259, 1289 - 1290, 1981, (in russischer Sprache).

[8] H. Havlicek: Lineare Algebra und Analytische Geometrie I, II, TU Wien, 1995-96.

[9] A. Hocquenghem: “Codes correcteurs d’erreurs”, Chiffres 2, 147 - 156, 1959.

[10] R. Lidl und H. Niederreiter: Finite Fields, Addison-Wesley, Reading, Mass., 1983.

[11] F. J. MacWilliams - N. J. A. Sloane: Theory of error-correcting codes, North-Holland, Amsterdam, 1977.

[12] H. Niederreiter: “Nets, (t, s)-sequences, and algebraic curves over finite fields with many rational points”, Proc. International Congress of Mathematicians (Berlin, 1998), Documenta Math. Extra Volume ICM III, 337 - 386, 1998.

[13] H. Niederreiter and C. P. Xing: “Low-discrepancy sequences and global function fields with many rational places”, Finite Fields Appl. 2, 241 - 273, 1996.

[14] H. Niederreiter and C. P. Xing: “Towers of global funktion fields with asymptotically many rational places and an improvement on the Gilbert-Varshamov bound”, Math. Nachrichtentech. 195, 171 - 186, 1998.

[15] H. Niederreiter - C. P. Xing - K. Y. Lam: “A New Construction of Algebraic-Geometry Codes”, Applicable Algebra Engrg. Comm. Comput. 9, 373 - 381, 1999.

[16] F. Özbudak - H. Stichtenoth: “Constructing Codes from Algebraic Curves”, IEEE Trans. Inform. Theory 45, 2502 - 2505, 1999.

[17] O. Pretzel: Error-Correcting Codes and Finite Fields, Oxford University Press, Oxford, 1992.

[18] O. Pretzel: Codes and Algebraic Curves, Oxford University Press, Oxford, 1998.

[19] H. Stichtenoth: Algebraic Function Fields and Codes, Springer-Verlag, Berlin, 1993.

[20] E. C. Titchmarsh: The Zeta-function of Riemann, Stechert-Hafner Verlag, New York, 1964.

[21] M. A. Tsfasman - S. G. Vlǎdut: Algebraic-Geometric Codes, Kluwer Academic Publishers, Dordrecht-Boston-London, 1991.

[22] M. A. Tsfasman - S. G. Vlǎdut - T. Zink: “Modular curves, Shimura curves and Goppa codes better than the Varshamov-Gilbert bound”, Math. Nachr. 109, 21 - 28, 1982.

[23] J. H. van Lint: Introduction to Coding Theory, Springer-Verlag, New York, 1999.

[24] C. P. Xing and H. Niederreiter: “A construction of lowdiscrepancy sequences using global function fields”, Acta Arith. 73, 87 - 102, 1995.

[25] C. P. Xing - H. Niederreiter - K. Y. Lam: “Constructions of Algebraic-Geometry Codes”, IEEE Trans. Inform. Theory 45, 1186 - 1193, 1999.

[26] C. P. Xing - H. Niederreiter - K. Y. Lam: “A Generalization of Algebraic-Geometry Codes”, IEEE Trans. Inform. Theory 45, 2498 - 2501, 1999.