Geometrische Konstruktionen linearer Codes über Galois-Ringen der Charakteristik 4 von hoher homogener Minimaldistanz

Universit¨ at Bayreuth Fakult¨ at f¨ ur Mathematik, Physik und Informatik Dissertation Geometrische Konstruktionen linearer Codes ¨ uber Galois-Ringen der Charakteristik 4 von hoher homogener Minimaldistanz Michael Kiermaier 2012 F¨ ur meinen Vater 1954 – 2001 Vorwort Die vorliegende Dissertation entstand in den Jahren 2006 bis 2012 an der Universit¨ at Bayreuth unter der Betreuung von Herrn Prof. Dr. Kerber. F¨ ur seine best¨ andige Unterst¨ utzung und das mir vom ersten Augenblick an entgegengebrachte Vertrauen geb¨ uhrt ihm mein tiefer Dank. Weiter bedanke ich mich bei Herrn Prof. Dr. Laue, Axel Kohnert, Alfred Wassermann, Stephan Elsenhans, Sascha Kurz, Johannes Zwanzger und Thomas Feulner f¨ ur die konstruktive und stets unkomplizierte Zusammenarbeit. Meine Stelle wurde teilweise aus dem DFG-Projekt WA 1666/4 finanziert, das Axel Kohnert und Alfred Wassermann beantragt hatten. Ein besonderer Dank gilt meinem langj¨ ahrigen Lehrer Thomas Honold, der mich als Betreuer meiner Diplomarbeit zum Thema der linearen Codes ¨ uber endlichen Ringen gebracht hat. Mit seinem unersch¨ opflichen Wissen war er mir stets ein wertvoller Ansprechpartner. Nicht unerw¨ ahnt bleiben soll auch seine großz¨ ugige Einladung an die Zhejiang Universit¨ at in Hangzhou, China, die mir im M¨ arz und April 2010 sechs unvergessliche und wissenschaftlich sehr fruchtbare Wochen bescherte. Nicht zuletzt m¨ ochte ich mich bei meiner Familie f¨ ur ihre Unterst¨ utzung bedanken: bei meiner Mutter, meinem leider viel zu fr¨ uh verstorbenen Vater und besonders bei meiner Ehefrau Julia, deren dreißigsten Geburtstag ich mir als Abgabetermin f¨ ur die Dissertation gesetzt hatte, den ich auch auf den Tag genau einhalten konnte. Bayreuth, im November 2012 Michael Kiermaier i Inhaltsverzeichnis Vorwort i 1. Einleitung 1 1.1. Geschichte der linearen Codes ¨ uberRingen................. 1 1.2. Ringlineare Codes und Hjelmslev-Geometrien . . . . . . . . . . . . . . . 4 1.3. Entstehung dieser Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4. Vier neue unendliche Serien ringlinearer Codes . . . . . . . . . . . . . . . 5 2. Grundlagen 9 2.1. Galois-Ringe.................................. 9 2.1.1. Wahl des definierenden Polynoms . . . . . . . . . . . . . . . . . . 10 2.1.2. Eigenschaften............................. 11 2.1.3. Gestutzte Witt-Vektoren . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.4. Endlich erzeugte Moduln ¨ uber einem Galois-Ring . . . . . . . . . 13 2.2. Lineare Codes ¨ uber Galois-Ringen der Kettenl¨ ange 2 . . . . . . . . . . . 17 2.2.1. Generatormatrizen . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2. Gewichte, Distanzen und die Gray-Abbildung . . . . . . . . . . . 21 2.2.3. Lineare und semilineare Isometrien . . . . . . . . . . . . . . . . . 25 2.2.4. Dualit¨ at................................ 27 2.2.5. Radikalcode und Torsionscode . . . . . . . . . . . . . . . . . . . . 28 2.2.6. Modifikationen R-linearerCodes................... 29 2.3. Projektive Hjelmslev-Geometrie . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.1. Definitionen.............................. 32 2.3.2. Punkt-Geraden-Inzidenzen . . . . . . . . . . . . . . . . . . . . . . 34 2.3.3. Inzidenzanzahlen ........................... 35 2.3.4. Verbindung zur Codierungstheorie . . . . . . . . . . . . . . . . . . 36 2.4. Beispiele R-linearerCodes .......................... 39 2.4.1. Simplex-Codes ............................ 39 2.4.2. Teichm¨ uller-Codes und Kerdock-Codes . . . . . . . . . . . . . . . 40 3. Konstruktionen 45 3.1. Verallgemeinerte Teichm¨ uller-Codes..................... 45 3.1.1. Unterr¨ aume vom Typ I und II . . . . . . . . . . . . . . . . . . . . 45 3.1.2. Symmetrische Translationsschemata auf (GR(4, t),+)....... 47 3.1.3. Punktmengen in PHG(Rk) mit zwei Schnittzahlen . . . . . . . . . 51 3.1.4. Beispiele................................ 56 iii Inhaltsverzeichnis 3.2. Geometrisches Dualisieren . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.1. Dualisierte verallgemeinerte Teichm¨ uller-Codes . . . . . . . . . . . 61 3.2.2. Dualisierte Kerdock-Codes . . . . . . . . . . . . . . . . . . . . . . 66 3.3. Vergr¨ oßerte und verl¨ angerte Simplex-Codes . . . . . . . . . . . . . . . . . 70 3.3.1. Beispiele................................ 79 4. Ausblick 81 A. Bilinearformen ¨ uber F283 B. Assoziationsschemata 85 Literatur 87 iv 1. Einleitung Fehlerkorrigierende Codes werden heute in nahezu jeder Form der Informations¨ ubertragung und -speicherung eingesetzt. Prominente Beispiele sind CD-Spieler, WLAN sowie die Kommunikation mit Weltraumsonden. In der Codierungstheorie werden fehlerkorrigierende Codes wie folgt mathematisch modelliert: Ein Blockcode Cder L¨ ange nist eine Teilmenge von Γn, wobei das Alphabet Γ eine endliche Menge ist. F¨ ur die Anwendungen sind die bin¨ aren Blockcodes mit #Γ = 2 von besonderem Interesse.1Die Hamming-Distanz zweier Codew¨ orter ist die Anzahl der Positionen, an denen sie sich unterscheiden, und die Minimaldistanz deines Blockcodes Cist das Minimum ¨ uber die Hamming-Distanzen aller Paare verschiedener Codew¨ orter in C. Man bezeichnet dann Cals einen (n, #C, d)#Γ-Code. Eine wichtige Klasse sind die linearen Codes ¨ uber endlichen K¨ orpern: Hier ist Γ = Fqein endlicher K¨ orper und C ein Untervektorraum des Fq-Vektorraums Fn q. Gute Fehlerkorrektureigenschaften von C entsprechen einem m¨ oglichst kleinen Parameter nsowie m¨ oglichst großen Parametern #Cund d. 1.1. Geschichte der linearen Codes ¨ uber Ringen Im Jahr 1967 hielt John Robinson, Elektrotechniker an der University of Iowa, USA, einen Einf¨ uhrungsvortrag f¨ ur Sch¨ uler ¨ uber Codierungstheorie [4, S. 68]. Er illustrierte seinen Vortrag mit dem folgenden offenen Forschungsproblem: Der nach dem damaligen Wissensstand gr¨ oßte bekannte bin¨ are Blockcode der L¨ ange 16 und Minimaldistanz 6 war ein linearer bin¨ arer Code der Gr¨ oße 128. Man wusste, dass kein gr¨ oßerer linearer bin¨ arer Code dieser L¨ ange und Minimaldistanz existiert. F¨ ur allgemeine bin¨ are Blockcodes der L¨ ange 16 und Minimaldistanz 6 war nach den bekannten oberen Schranken jedoch noch eine Gr¨ oße von bis zu 256 Codew¨ ortern denkbar. ¨ Uberraschenderweise gelang es dem Sch¨ uler Alan W. Nordstrom aufgrund des Vortrags, einen nichtlinearen bin¨ aren (16,28,6)2-Blockcode zu konstruieren.2Dieser Code hat eine h¨ ohere Minimaldistanz als jeder lineare bin¨ are Code gleicher L¨ ange und Gr¨ oße, weshalb wir ihn als BTL-Code (better than linear) bezeichnen. Er wurde 1967 in einer gemeinsamen Arbeit von Nordstrom und Robinson ver¨ offentlicht [114] und 1969 nochmals 1In dieser Arbeit bezeichnet das Symbol # die M¨ achtigkeit einer Menge oder Multimenge oder auch das Gewicht einer Partition. 2Tats¨ achlich handelte es sich sowohl in Robinsons Vortrag als auch bei dem von Nordstrom gefundenen Code um bin¨ are Blockcodes der L¨ ange 15 und Minimaldistanz 5. Durch Anh¨ angen eines Parit¨ atsbits entsprechen diese Codes jedoch eindeutig den bin¨ aren Blockcodes der L¨ ange 16 und Minimaldistanz 6. 1 2. Grundlagen 2.1. Galois-Ringe In diesem Abschnitt werden die Grundringe der sp¨ ater betrachteten ringlinearen Codes vorgestellt.11 Details findet man beispielsweise in [109, 112]. In [109, S. 307] sind zwei Gr¨ unde f¨ ur die Bedeutung der Galois-Ringe aufgef¨ uhrt: Zum einen bilden sie eine Oberklasse sowohl der endlichen K¨ orper als auch der Restklassenringe der ganzen Zahlen modulo einer Primzahlpotenz. Dies erm¨ oglicht eine einheitliche Behandlung gewisser kombinatorischer Fragestellungen ¨ uber diesen beiden Ringklassen (in unserem Fall ist das nat¨ urlich die Codierungstheorie). Zum anderen sind die GaloisRinge wichtige Grundbausteine in der Theorie der endlichen Ringe. Viele Eigenschaften der Galois-Ringe sind in ihrer Idealstruktur – einer Kette – begr¨ undet. Daher ¨ uberrascht es nicht, dass sich etliche Resultate ohne M¨ uhe auf die endlichen Kettenringe ausweiten lassen, also auf endliche Ringe, deren Verband der Linksideale (und dann auch Rechtsideale) eine Kette ist.12 Die endlichen Kettenringe sind in der Klasse der endlichen Frobenius-Ringe enthalten, und diese wiederum in der Klasse der endlichen Quasi-Frobenius-Ringe, die von vielen Codierungstheoretikern als die gr¨ oßte noch f¨ ur die Codierungstheorie taugliche Ringklasse angesehen wird. Die Einordnung in die Hierarchie endlicher Ringe ist an folgendem Diagramm veranschaulicht: Restklassenringe Zpm ⊂ endliche K¨ orper Fpr ⊂ Galois-Ringe GR(pm, r) ⊂ endliche Kettenringe ⊂ endliche Frobenius-Ringe ⊂ endliche Quasi-Frobenius-Ringe Definition 2.1.1 Sei peine Primzahl, meine positive ganze Zahl und f∈Zpm[X]ein normiertes Polynom vom Grad r≥1, so dass sein Bild modulo pin Fp[X]irreduzibel ist. Der Ring Zpm[X]/(f)heißt Galois-Ring GR(pm, r)der Charakteristik pmvom Rang r. 11Unter einem Ring verstehen wir einen nicht zwingend kommutativen Ring mit Einselement. 12Alternativ lassen sich die endlichen Kettenringe als die endlichen lokalen Hauptidealringe charakterisieren. 9 2. Grundlagen Die Ordnung dieses Galois-Rings ist # GR(pm, r) = pmr. Unter vorgegebenen Parametern p,rund mh¨ angt die Definition bis auf Ringisomorphie nicht von der genauen Wahl des Polynoms fab ([98, Satz 8]). Die Galois-Ringe umfassen zwei wichtige Klassen endlicher Ringe: Die endlichen K¨ orper Fpr= GR(p, r) und die Restklassenringe der ganzen Zahlen modulo einer Primzahlpotenz Zpm= GR(pm,1). Im Folgenden sind die Bezeichner p,m,r,q=prund R= GR(pm, r) wie in Definition 2.1.1 fest vorgegeben. Bemerkung 2.1.2 Die Galois-Ringe tauchen erstmals 1924 unter dem Namen Grundringe bei Krull auf [98, §4]. Sie wurden 1966 von Janusz [78, S. 476] und 1969 von Raghavendran [119, Sec. 3.1] offenbar unabh¨ angig voneinander neu entdeckt und von beiden Autoren aufgrund der starken Verwandtschaft zu den endlichen K¨ orpern GaloisRinge genannt. Der oben eingef¨ uhrte Bezeichner GR(Charakteristik,Rang) ist von Janusz ¨ ubernommen. Raghavendran benutzt denselben Bezeichner GR, allerdings mit den Parametern GR(Ordnung,Charakteristik). In der Literatur sind heute beide Varianten ¨ ublich, wobei erstere die h¨ aufigere zu sein scheint. 2.1.1. Wahl des definierenden Polynoms F¨ ur die explizite Darstellung von endlichen K¨ orpern Fprhat man das Problem, dass es im Allgemeinen viele verschiedene irreduzible Polynome vom Grad r¨ uber Fpgibt. Leider ist keine glatte mathematische Charakterisierung bekannt, die auf eindeutige Weise ein ”sch¨ ones” Polynom ausw¨ ahlt. In aktuellen Computeralgebrasystemen wie Magma [10] werden hierf¨ ur die Conway-Polynome fpr∈Fp[X] benutzt. Diese werden rekursiv definiert: Das Conway-Polynom fprist das lexikographisch kleinste normierte primitive Polynom vom Grad r, das f¨ ur alle echten Teiler svon rdie Teilbarkeitseigenschaft fps(X)|fpr(X(pr−1)/(ps−1)) (Norm-Kompatibilit¨ at) erf¨ ullt.13 Ist jedoch einmal eine Wahl f¨ ur die definierenden Polynome der endlichen K¨ orper getroffen, so ist der Schritt zu den Galois-Ringen nicht mehr schwierig: F¨ ur das definierende Polynom fvon GR(pm, r) bietet es sich an, den Hensel-Lift nach Zpm[X] des definierenden Polynoms fpr∈Fp[X] von Fprzu benutzen, also das eindeutig bestimmte normierte Polynom f∈Zpm[X] mit f|Xpr−1−1, dessen Bild modulo Rp mit fpr¨ ubereinstimmt (siehe z.B. [127]). Der Hensel-Lift kann effizient berechnet werden [22, Th. 1], [132, Sec. 1.3]. Im Fall p= 2 ist die Methode von Gr¨ affe (benannt nach dem Mathematiker Karl Heinrich Gr¨ affe) gut geeignet, siehe [126, Appendix V] und [52, Sec. III-A]. Neben dieser eindeutigen Auswahl des Polynoms fergibt sich auch der Vorteil, dass im Fall eines primitiven Ausgangspolynoms fprjede Nullstelle des Hensel-Lifts fein Erzeuger der Teichm¨ uller-Gruppe T∗(s.u.) ist. In der aktuellen Implementierung der Galois-Ringe in Magma wird leider nicht der Hensel-Lift, sondern der ”naive” Lift von Fp[X] nach Zpm[X] benutzt. 13Laut [121] stammt die Idee, Norm-kompatible Polynome zur Darstellung der endlichen K¨ orper zu benutzen, von J. H. Conway. Die exakte Definition der Conway-Polynome wurde 1990 von R. A. Parker in einem Vortrag mit dem Titel Finite fields and Conway polynomials im IBM Scientific Center in Heidelberg gegeben. 10 2.1. Galois-Ringe 2.1.2. Eigenschaften Der Galois-Ring R= GR(pm, r) ist ein lokaler kommutativer Ring. Das eindeutige maximale Ideal ist das Hauptideal Rp. Der zugeh¨ orige Restklassenk¨ orper R/Rp ist isomorph zu Fqmit q=pr. Des Weiteren ist Rein Hauptidealring, und sein Idealverband bildet die Kette {0}=Rpm⊂Rpm−1⊂. . . ⊂Rp1⊂Rp0=R. Aus diesem Grund bezeichnen wir mauch als die Kettenl¨ ange von R. Die H¨ ohe h(x) eines Elements x∈Rist die gr¨ oßte ganze Zahl s≤mmit x∈Rps. Es gilt h(x)∈ {0, . . . , m}. Zwei Ringelemente haben genau dann dieselbe H¨ ohe, wenn sie assoziiert sind. Das einzige Ringelement von H¨ ohe 0 ist das Nullelement, und die Ringelemente von H¨ ohe msind genau die Einheiten. Die Gr¨ oße eines Ideals Rx schreibt sich unter Zuhilfenahme der H¨ ohe als #(Rx) = qm−h(x). Einheiten und die p-adische Entwicklung Die Einheitengruppe R∗=R\Rp hat die Ordnung #R∗= #R−#(Rp) = qm−1(q−1). Weil qm−1und q−1 teilerfremd sind und R∗abelsch ist, gibt es als Hall-Untergruppen von R∗genau eine Untergruppe T∗der Ordnung q−1 und genau eine Untergruppe Hder Ordnung qm−1. Die Untergruppe T∗ist zyklisch und heißt Teichm¨ uller-Gruppe. W¨ ahlt man das definierende Polynom fvon Rals den Hensel-Lift eines primitiven Polynoms in Fp[X] vom Grad r, so ist X+ (f) ein Erzeuger von T∗. Weiter heißt T=T∗∪ {0}die Teichm¨ uller-Menge in R. Sie bildet ein multiplikativ abgeschlossenes Vertretersystem des Restklassenk¨ orpers. Jedes Element x∈Rl¨ asst sich eindeutig in der p-adischen Entwicklung Pm−1 i=0 tipimit Koeffizienten ti∈Tschreiben. Ein Ideal Rpi besteht genau aus den Elementen, f¨ ur die in der p-adischen Entwicklung alle Koeffizienten bis einschließlich zum (i−1)-ten gleich 0 sind. Weiter ist H= 1 + Rp die Menge der Haupteinheiten (engl. principal units) von R. Die Untergruppen T∗und Hsind in R∗komplement¨ ar. Genauer gilt: Fakt 2.1.3 ([119, Th. 9]) Es gilt R∗=T∗·H∼ =T∗×H, dabei ist T∗∼ =Zpr−1und H∼ =(Z2×Z2m−2×Zr−1 2m−1falls p= 2 und m≥3, Zr pm−1sonst. Automorphismen und Galois-Teilringe Wir definieren den verallgemeinerten Frobenius-Automorphismus von Rmit Hilfe der p-adischen Entwicklung als φ:R→R, m−1 X i=0 tipi7→ m−1 X i=0 tp ipi. Fakt 2.1.4 ([119, Prop. 2]) Die Automorphismengruppe Aut(R)von Rist zyklisch von Ordnung rund wird vom verallgemeinerten Frobenius-Automorphismus erzeugt. 11 2. Grundlagen Ein Galois-Ring R= GR(pm, r) ist genau dann isomorph zum Teilring eines anderen Galois-Rings S= GR(c, s), wenn die Charakteristiken ¨ ubereinstimmen (d.h. c=pm) und rein Teiler von sist. In dieser Situation enth¨ alt Sgenau einen zu Risomorphen Teilring, welcher in perfekter Analogie zur Galois-Theorie ¨ uber endlichen K¨ orpern aus den Fixpunkten des Automorphismus φs/r von Sbesteht. In p-adischer Entwicklung sind dies alle Elemente, deren Koeffizienten Repr¨ asentanten von Elementen in Fqrsind. Betrachten wir Rin Seingebettet, so ist die Teichm¨ uller-Gruppe T∗von Reine Untergruppe der Teichm¨ uller-Gruppe U∗von S, und Rist das Ring-Erzeugnis von T∗in S. Auf diese Weise ist der Galois-Ring S= GR(pm, rk) f¨ ur jede positive ganze Zahl kein freier R-Modul vom Rang k, so dass wir die Elemente von Smit Vektoren in Rkidentifizieren d¨ urfen. Diese Identifikation liefert einen R-Modulisomorphismus Rk∼ = SR,14 der die Vektoren in Rkmit einer zus¨ atzlichen multiplikativen Struktur versieht. Anders als mancherorts behauptet (beispielsweise [119, Prop. 1] oder [109, Lemma XVI.7]) ist im Allgemeinen nicht jeder Teilring eines Galois-Rings selbst wieder ein Galois-Ring [81]. Beispielsweise bilden im Galois-Ring GR(4,2) der Ordnung 16 die Elemente mit der 2-adischen Entwicklung t0+ 2t1mit t0∈ {0,1},t1∈Teinen Teilring der Ordnung 8, w¨ ahrend der einzige echte Galois-Teilring GR(4,1) die Ordnung 4 hat. 2.1.3. Gestutzte Witt-Vektoren Ernst Witt gab 1937 eine Arithmetik an, die der Menge der Folgen (den Witt-Vektoren) ¨ uber einem K¨ orper Kder Charakteristik peine kommutative Ringstruktur W(K) der Charakteristik 0 aufpr¨ agt [128]. Der Witt-Ring W(Fp) ist isomorph zum Ring der ganzen p-adischen Zahlen. Beschr¨ ankt man sich auf die ersten mKomponenten der WittVektoren, so erh¨ alt man einen Teilring von W(K), den Ring der gestutzten Witt-Vektoren Wm(K) der Charakteristik pm. F¨ ur uns sind die gestutzten Witt-Vektoren aufgrund der Isomorphie Wm(Fpr)∼ = GR(pm, r) von Interesse [119, Th. 7]. Ein Isomorphismus GR(pm, r)→Wmbildet ein Element a∈GR(pm, r) im Wesentlichen auf die Koeffizientenfolge seiner p-adischen Entwicklung ab [67, Th. 11]. In R=Wm(Fpr) ist das Nullelement durch (0, . . . 0) gegeben, das Einselement durch (1,0,...,0) und das Element pdurch (0,1,0,...,0). Die Teichm¨ uller-Elemente haben die Form (∗,0,...,0), und ein Element (α, 0,...,0) ist genau dann ein Erzeuger der Teichm¨ uller-Gruppe, wenn α∈Fprein primitives Element ist. Die Haupteinheiten haben die Form (1,∗,...,∗). F¨ ur i∈ {0, . . . , m}besteht das Ideal Rpiaus allen Elementen von R, bei denen die ersten iKomponenten gleich 0 sind. Insbesondere ist ein Element genau dann invertierbar, wenn seine erste Komponente in Fprinvertierbar ist. F¨ ur einen Teiler svon rbesteht der eindeutige zu GR(pm, s) isomorphe Teilring von Raus allen Elementen, deren Eintr¨ age im Teilk¨ orper Fpsvon Fpr liegen. 14Der Index Rim Ausdruck SRverdeutlicht, dass in diesem Moment Sals ein R-Modul aufgefasst wird. 12 2.1. Galois-Ringe Die Arithmetik der Witt-Vektoren ist im Allgemeinen ziemlich kompliziert, weshalb wir uns hier auf den sp¨ ater ben¨ otigten Spezialfall p=m= 2 beschr¨ anken: F¨ ur a= (a0, a1),b= (b0, b1)∈W2(F2r) ist a+b= (a0+b0, a1+b1+a0b0) und a·b= (a0b0, a1b2 0+b1a2 0). Weiter gilt −a= (a0, a2 0+a1) und a−1= (a−1 0, a−4 0a1) falls a06= 0. 2.1.4. Endlich erzeugte Moduln ¨ uber einem Galois-Ring Im Folgenden werden die wichtigsten Strukturs¨ atze f¨ ur endlich erzeugte R-Moduln diskutiert. Weil Rendlich ist, ist ein R-Modul genau dann endlich erzeugt, wenn er endlich ist. So wie die Galois-Ringe als eine Verallgemeinerung sowohl der endlichen K¨ orper als auch der ganzzahligen Restklassenringe modulo einer Primzahlpotenz aufgefasst werden k¨ onnen, ist die Theorie der endlich erzeugten R-Moduln eine Verallgemeinerung sowohl der Theorie der endlichdimensionalen Vektorr¨ aume ¨ uber endlichen K¨ orpern als auch der Theorie der endlichen abelschen p-Gruppen.15 Die Theorie kann ohne Probleme noch auf die endlichen Kettenringe ausgeweitet werden, siehe hierzu [65, 69]. M¨ ochte man noch allgemeiner ¨ uber endlichen Frobenius-Ringen Codierungstheorie betreiben, so steht man vor dem Problem, dass keine einheitliche Beschreibung der endlich erzeugten Moduln bekannt ist. Partitionen Unter einer Partition λverstehen wir eine schwach monoton fallende Folge (λi)i∈Nmit Koeffizienten λi∈N,16 in der nur endlich viele Eintr¨ age von Null verschieden sind. Die Nulleintr¨ age werden bei der Angabe einer Partition ¨ ublicherweise weggelassen. Besteht keine Verwechslungsgefahr mit den ¨ ublichen Potenzen, so wird eine Partition (a0, . . . , a0 | {z } t0mal , a1, . . . , a1 | {z } t1mal , . . .). auch in Exponentialschreibweise als (at0 0at1 1. . .) geschrieben. Auf die Exponentialschreibweise d¨ urfen die gewohnten Potenzrechenregeln angewendet werden. Beispielsweise beschreiben die Ausdr¨ ucke (413113), (133141), (4 ·3·13), (41312013) und (0311413112) alle die Partition (4,3,1,1,1). Die Anzahl der Partitionsglieder ungleich Null heißt L¨ ange `(λ) von λ, und das gr¨ oßte Folgenglied λ0heißt H¨ ohe. Weiter heißt die Zahl #λ=Pi∈Nλi∈Ndas Gewicht von λ. Die Partitionen vom Gewicht n∈Nentsprechen genau den M¨ oglichkeiten, die Zahl nin positive ganzzahlige Summanden zu zerlegen, wobei nicht nach der Reihenfolge der Summanden unterschieden wird. 15Die endlich erzeugten Moduln ¨ uber dem Galois-Ring Zpmsind genau die endlichen abelschen pGruppen vom Exponent h¨ ochstens pm. 16In dieser Arbeit ist N={0,1,2, . . .}. 13 2. Grundlagen Abbildung 2.1.: Ferrers-Diagramm einer Partition und ihrer konjugierten Partition 4 3 1 1 1 5 2 2 1 λ= (4,3,1,1,1) ←→ λ0= (5,2,2,1) Oft ist es g¨ unstig, eine Partition in einem sogenannten Ferrers-Diagramm zu veranschaulichen. Hierzu wird jede Komponente λivon λals eine Zeile von λiK¨ astchen dargestellt, die linksb¨ undig untereinandergesetzt werden. Das Gewicht #λist dann die Gesamtzahl der K¨ astchen im Diagramm. Spiegelt man das Ferrers-Diagramm einer Partition λentlang der Diagonale von links oben nach rechts unten, so entsteht wieder ein Ferrers-Diagramm, siehe Abbildung 2.1. Die zugeh¨ orige Partition wird als die konjugierte Partition λ0von λbezeichnet. Offenbar ist (λ0)0=λund #λ= #λ0. Formal l¨ asst sich λ0auch definieren als die Partition (#{j∈N|λj> i})i∈N Es gilt `(λ0) = λ0und `(λ)=(λ0)0. Mit Hilfe der konjugierten Partition ergibt sich die Exponentialschreibweise als Q∞ i=1 iλ0 i−1−λ0 i. F¨ ur zwei Partitionen λund µschreiben wir λ≤µ, wenn λi≤µif¨ ur alle i∈Ngilt. Damit ist auf der Menge aller Partitionen eine Halbordnung definiert, die sogar einen distributiven Verband bildet, den sogenannten Young-Verband. Anschaulich bedeutet λ≤µ, dass das Ferrers-Diagramm von λim Ferrers-Diagramm von µenthalten ist. Es ist λ≤µgenau dann, wenn λ0≤µ0. Der konjugierte Umriss Es gilt folgende Verallgemeinerung des Hauptsatzes ¨ uber endliche abelsche Gruppen: Fakt 2.1.5 ([109, S. 310, Th. XVI.2]) Es sei Mein endlich erzeugter R-Modul. Dann existiert genau eine Partition λder H¨ ohe h¨ ochstens mmit M∼ =Rpm−λ0⊕. . . ⊕Rpm−λ`(λ)−1. Die Partition λaus Fakt 2.1.5 heißt Umriss (engl. shape, siehe [64, Def. 2] und [65, Def. 2.1]) shp(M) von M. Als trennende Invariante auf den endlich erzeugten R-Moduln ist der Umriss eine direkte Verallgemeinerung des Dimensionsbegriffs der linearen Algebra ¨ uber K¨ orpern. In vielen Fragestellungen erscheint es nat¨ urlicher, nicht den Umriss λ, sondern den konjugierten Umriss cshp(M) = shp(M)0=λ0zu betrachten. Ist beispielsweise Rein endlicher K¨ orper und Mein endlich erzeugter R-Vektorraum, so hat M 14 2.1. Galois-Ringe genau dann die R-Dimension n, wenn Mals R-Modul den konjugierten Umriss (n) der L¨ ange 1 hat. Aus diesem Grund werden wir im Folgenden konsequent den konjugierten Umriss anstelle des Umrisses benutzen. Es gilt #M=q# cshp(M)=q# shp(M). Der R-Modul Mist genau dann frei, wenn cshp(M) = (km) mit k∈Ngilt. In diesem Fall ist kder Rang von M. F¨ ur zwei Partitionen λund µist der verallgemeinerte Gauß-Koeffizient definiert als λ µq = ∞ Y i=0 qµi+1(λi−µi)·λi−µi+1 µi−µi+1q!. Dabei bezeichnet f¨ ur n∈Z,k∈N n kq =(Qk−1 i=0 qn−i−1 qi+1−1falls n≥0 0 falls n < 0 =     0 falls k > n, 1 falls k∈ {0, n},17 (qn−1)(qn−1−1)·...·(qn−k+1−1) (q−1)(q2−1)·...·(qk−1) falls k∈ {1, . . . , n −1} den herk¨ ommlichen Gauß-Koeffizienten, der im Fall n≥0 die Anzahl der Unterr¨ aume der Dimension kin einem n-dimensionalen Fq-Vektorraum angibt. F¨ ur µ6≤ λwird einer der herk¨ ommlichen Gauß-Koeffizienten in der Definition von λ µqgleich Null, so dass sich in diesem Fall λ µq= 0 ergibt. Auch hier bietet es sich an, nat¨ urliche Zahlen amit der Partition (a) der L¨ ange 1 zu identifizieren, denn f¨ ur Partitionen λ= (n) und µ= (k) stimmt der verallgemeinerte Gauß-Koeffizient mit dem ¨ ublichen Gauß-Koeffizienten ¨ uberein. Bemerkung 2.1.6 Die Definition des verallgemeinerten Gauß-Koeffizienten in [86] weicht von der obigen insofern ab, als die Eingabepartitionen λund µdurch ihre konjugierten Partitionen ersetzt wurden. Um die herk¨ ommlichen Gauß-Koeffizienten einzubetten, muss man dann aber nmit der Partition (1n) identifizieren. Die obige Definition wurde gew¨ ahlt, weil zum einen die Identifikation von nmit (n) nat¨ urlicher erscheint und man zum anderen innerhalb der Definition ohne eine ” Verdrehung” von λbzw. µzu λ0bzw. µ0auskommt. Die vorgenommene Definition der verallgemeinerten Gauß-Koeffizienten wird durch die folgende Aussage gerechtfertigt: Fakt 2.1.7 ([65, Th. 2.4]) Seien λund µzwei Partitionen. Ein R-Modul vom konjugierten Umriss λenth¨ alt genau dann einen Untermodul vom konjugierten Umriss µ, wenn µ≤λist. Genauer ist die Anzahl der Untermoduln vom konjugierten Umriss µ gegeben durch den verallgemeinerten Gauß-Koeffizienten λ µq. 17Im Fall k= 0 steht ein leeres Produkt. 15 2. Grundlagen Abbildung 2.2.: Ferrers-Diagramm des komplement¨ aren konjugierten Umrisses 4 3 1 1 1 k m 5 5 5 3 2 λ= (4,3,1,1,1) ¯ λ= (5,5,5,3,2) Bemerkung 2.1.8 (a) F¨ ur die Galois-Ringe R=Zpmz¨ ahlt Fakt 2.1.7 genau die Untergruppen vom Typ µeiner endlichen abelschen p-Gruppe vom Typ λ. Dieses Resultat wurde laut [15, S. 22] im Jahr 1948 unabh¨ angig voneinander in drei Artikeln publiziert, auf Englisch [130], auf Franz¨ osisch [33] (durch M¨ obius-Inversion auf dem Untergruppenverband, siehe auch [26]) und auf Russisch [36]. (b) Die den verallgemeinerten Gauß-Koeffizienten zugrundeliegende Fragestellung l¨ asst sich noch verfeinern: Gibt man zus¨ atzlich zu λund µnoch eine dritte Partition νvor, so sei gλ µν(q) die Anzahl der Untermoduln Neines endlichen R-Moduls M vom Umriss λ, f¨ ur die shp(N) = µund shp(M/N) = νist. Im Jahr 1959 definierte Philip Hall diese Zahlen in der Situation von endlichen abelschen p-Gruppen M und zeigte, dass gλ µν ein Polynom in pmit ganzzahligen Koeffizienten ist [51]. Aus diesem Grund werden die Polynome gλ µν heute als Hall-Polynome bezeichnet, tats¨ achlich tauchten diese Polynome samt der zugeh¨ origen Hall-Algebra bereits 1901 bei Ernst Steinitz auf [123]. Als ein Spezialfall der Resultate von [106] gelten diese Ergebnisse auch f¨ ur endlich erzeugte R-Moduln. Insbesondere ist es legitim, in der obigen Situation die Anzahl gλ µν nur mit der Zahl qzu parametrisieren und nicht mit dem Ring R. Offenbar gilt Pνgλ µν(q) = λ0 µ0q, d.h. die Hall-Polynome verfeinern die Information der verallgemeinerten Gauß-Koeffizienten. Allerdings sind die Hall-Polynome deutlich schwieriger explizit zu berechnen als die verallgemeinerten Gauß-Koeffizienten, siehe z.B. [110]. Sei nun ein freier R-Modul MRvom Rang kfest als Umgebungsraum vorgegeben und die Graßmann-Variet¨ at G(MR, λ) definiert als die Menge aller Untermoduln von MR eines vorgegebenen konjugierten Umrisses λ. Nach Fakt 2.1.7 gilt #G(MR, λ) = (km) λq . Im Fall λ≤(km) definieren wir weiter den komplement¨ aren konjugierten Umriss ¯ λanschaulich durch dasjenige Ferrers-Diagramm, das – um 180 Grad gedreht – das 16 2.2. Lineare Codes ¨ uber Galois-Ringen der Kettenl¨ ange 2 Ferrers-Diagramm von λzum Ferrers-Diagramm des konjugierten Umrisses (km) des Umgebungsraum Rk, also zu einem (m×k)-Rechteck erg¨ anzt. In Abbildung 2.2 ist ein Beispiel mit m= 5 und k= 6 zu sehen. Formal ist der komplement¨ are konjugierte Umriss definiert als ¯ λ= (k−λm−i−1)i∈{0,...,m−1}. F¨ ur jeden R-Modul M≤Rkvom konjugierten Umriss λhat der Faktormodul Rk/M den konjugierten Umriss ¯ λ. F¨ ur zwei Vektoren x= (x1, . . . , xn),y= (y1, . . . , yn)∈Rnist das Standardskalarprodukt wie ¨ ublich erkl¨ art als x·y= n X i=1 xiyi. F¨ ur eine beliebige Teilmenge M⊆Rndefinieren wir den orthogonalen (auch: dualen) Untermodul als M⊥={x∈Rn|x·y= 0 f¨ ur alle y∈M}. Man pr¨ uft nach, dass M⊥tats¨ achlich ein Untermodul von Rmist. Fakt 2.1.9 ([64, Th. 3], [65, Th. 3.1]) Sei M≤Rn. Es gilt: (a) cshp(M⊥) = cshp(M). (b) (M⊥)⊥=M. (c) ⊥induziert einen Verbandsantiautomorphismus auf dem Verband aller Untermoduln von Rn. Insbesondere gilt (U+V)⊥=U⊥∩V⊥und (U∩V)⊥=U⊥+V⊥ f¨ ur alle Untermoduln Uund Vvon Rn. Mit Fakt 2.1.7 folgt daraus unmittelbar: Fakt 2.1.10 ([57, Prop. 1]) Seien λund µzwei Partitionen kleiner gleich (km). Ein R-Modul vom konjugierten Umriss λist in genau ¯ λ ¯µqUntermoduln von Rkvom konjugierten Umriss µenthalten. 2.2. Lineare Codes ¨ uber Galois-Ringen der Kettenl¨ ange 2 Es wird nun ein Abriss ¨ uber die Codierungstheorie ¨ uber Galois-Ringen der Kettenl¨ ange 2 gegeben. Die Theorie kann ohne Probleme auf endliche Kettenringe beliebiger Kettenl¨ ange verallgemeinert werden [65, 69], f¨ ur die sp¨ ateren Anwendungen ist die hier beschriebene Situation jedoch ausreichend. Die traditionelle Codierungstheorie ¨ uber endlichen K¨ orpern wird als bekannt vorausgesetzt, hierzu sei auf die Lehrb¨ ucher [53, 75, 5] verwiesen. 17 2. Grundlagen (b) Das homogene Gewicht wurde in [27] als eine Verallgemeinerung des Lee-Gewichts auf die Restklassenringe Zkeingef¨ uhrt; f¨ ur den Fall k=p2mit pprim findet sich dort auch eine verallgemeinerte Gray-Abbildung. (c) Ein in unserer Situation der Galois-Ringe der L¨ ange 2 passendes homogenes Gewicht mit zugeh¨ origer verallgemeinerter Gray-Abbildung γ∗wurde in [113] angegeben. Die Abbildungsvorschrift von γ∗l¨ asst sich im Wesentlichen so beschreiben: Wir identifizieren die Elemente von Rmit ihrer p-adischen Entwicklung a0+a1p, wobei a0und a1Elemente der Teichm¨ uller-Menge von Rsind, und bezeichnen die Reduktion von aimodulo pmit ¯ai∈Fq. Sei G=b1b2. . . bq 1 1 . . . 1, wobei b1, b2, . . . , bqdie Elemente des endlichen K¨ orpers Fqdurchl¨ auft. Die Abbildung (R, dhom)→(Fq q, dHam), a0+a1p7→ (¯a0,¯a1)G ist eine distanzerhaltende injektive Abbildung. Koordinatenweises Anwenden liefert nun eine verallgemeinerte Gray-Abbildung. Diese Abbildung kann als Konkatenation mit dem von Gerzeugten Fq-linearen Code – ein MDS-Code mit den Parametern [q, 2, q −1]q– aufgefasst werden. Weil dieser Code ein Reed-Solomon-Code ist, wurde γ∗in [113] Reed-Solomon map genannt. (d) Der von Gerzeugte Code l¨ asst sich auch als q-n¨ arer Reed-Muller-Code RMq(1,1) erster Ordnung beschreiben.23 Diese Sichtweise erlaubt eine Verallgemeinerung f¨ ur allgemeine Kettenringe beliebiger Kettenl¨ ange m: Durch Konkatenation mit dem Reed-Muller-Code RMq(m−1,1) erh¨ alt man auf ¨ ahnliche Weise eine verallgemeinerte Gray-Abbildung [49] (siehe [23] f¨ ur den Spezialfall der Kettenringe Z2m). Weitere Verallgemeinerungen des homogenen Gewichts und der Gray-Abbildung findet man in [73, 50]. (e) Die verallgemeinerte Gray-Abbildung ist genau f¨ ur den kleinsten Grundring Z4 eine Isometrie. F¨ ur gr¨ oßere Galois-Ringe ist die verallgemeinerte Gray-Abbildung nicht mehr surjektiv. (f) Weil die verallgemeinerte Gray-Abbildung distanzerhaltend ist, ist mit einem Rlinearen Code Cauch sein Gray-Bild stets distanzhomogen. BTLund BTKL-Codes Unser Ziel wird sein, durch Gray-Bilder R-linearer Codes nichtlineare Blockcodes ¨ uber Fq zu konstruieren, deren Parameter Fq-linear nicht realisierbar sind. Wir nennen einen Rlinearen Code CBTL (better than linear), wenn sein Gray-Bild nachweislich eine h¨ ohere 23Das Symbol RMq(m, r) bezeichnet den Fq-linearen Reed-Muller-Code der L¨ ange qmund der Ordnung r. Der Code RMq(m, r) hat die Parameter [qm, m + 1, qm−qm−r]q. 24 2.2. Lineare Codes ¨ uber Galois-Ringen der Kettenl¨ ange 2 Minimaldistanz hat als jeder vergleichbare (d.h. gleiche L¨ ange und Gr¨ oße) Fq-lineare Code. Hat das Gray-Bild eine h¨ ohere Minimaldistanz als jeder bekannte vergleichbare Fqlineare Code, so nennen wir den Code CBTKL (better than known linear). W¨ ahrend BTL eine harte mathematische Eigenschaft eines ringlinearen Codes ist, beschreibt BTKL lediglich den aktuellen Kenntnisstand: Ein BTKL-Code ist ein Kandidat f¨ ur einen BTLCode. Das folgende Beispiel belegt, dass es tats¨ achlich BTL-Codes gibt: Beispiel 2.2.8 Der aufgrund seiner relativ kleinen Parameter, seiner Entdeckungsgeschichte und vieler interessanter Eigenschaften wohl prominenteste ringlineare Code ist der von der (sowohl systematischen als auch kanonischen) Generatormatrix     10002111 01001231 00101123 00011312     erzeugte Z4-lineare Oktacode O. Der Oktacode hat den symmetrisierten Gewichtsz¨ ahler wsym(O) = X8 2+ 112X4 0X1X3 2+ 14X4 1X4 2+ 16X8 0+ 112X4 0X3 1X2+X8 1 und den Lee-Gewichtsz¨ ahler wLee(O) = 1 + 112X6+ 30X8+ 112X10 +X16. Damit ist der Oktacode ein (8,28,6)Z4-Code bzw. genauer ein [8,(4,4),6]Z4-Code. Die minimale Lee-Distanz ist dLee(O) = 6, und das Gray-Bild ist demzufolge ein bin¨ arer (16,28,6)2-Code, der Nordstrom-Robinson-Code [114]. Weil ein linearer bin¨ arer [16,8]F2-Code bestenfalls die Minimaldistanz 5 hat, handelt es sich bei dem Oktacode um einen BTL-Code. 2.2.3. Lineare und semilineare Isometrien Dieser Abschnitt hat die strukturerhaltenden Abbildungen von R-linearen Codes zum Inhalt. Zur Theorie der Gruppenoperationen siehe z.B. [79]. Lineare Isometrien Zu einem Vektor v∈Rndefinieren wir die Diagonalmatrix diag(v)∈Rn×nmit der Diagonale v. Weiter definieren wir zu einer Permutation σ∈Sndie Permutationsmatrix Pσ∈GL(n, R) als diejenige Matrix, deren Eintrag an der Position (i, j) durch δi,σ(j) gegeben ist, wobei δdas Kronecker-Delta bezeichnet. Die Abbildung Sn→GL(n, R), σ7→ Pσist ein Gruppenmonomorphismus.24 Eine Abbildung f:Rn→Rnheißt monomial, wenn es einen Permutationsanteil σ∈Snund einen Skalierungsanteil v∈(R∗)ngibt mit f(c) = diag(v)Pσcf¨ ur alle 24Permutationen sind Abbildungen, operieren also von links. 25 2. Grundlagen c∈Rn. Permutationsund Skalierungsanteil einer monomialen Abbildung sind eindeutig festgelegt. Die Menge aller monomialen Abbildungen bildet eine zum Kranzprodukt R∗oSnisomorphe Gruppe, die wir die monomiale Gruppe Mon(n, R) auf Rnnennen. In der Kranzproduktschreibweise entspricht die Sn-Komponente dem Permutationsanteil, und die R∗-Komponenten (nSt¨ uck) bilden zusammen den Skalierungsanteil. Die Gruppenstruktur von R∗ist durch Fakt 2.1.3 festgelegt. Monomiale Abbildungen sind linear. Die zugeh¨ origen Abbildungsmatrizen diag(v)Pσbilden eine die Permutationsmatrizen umfassende Untergruppe der GL(n, R). In der Codierungstheorie werden Vektoren meist als Zeilenvektoren aufgefasst; die monomiale Abbildung fschreibt sich dann als c7→ cPσ−1diag(v). Nach [129, Prop. 6.1] sind die linearen Isometrien (Rn, dHam)→(Rn, dHam) gerade die monomialen Abbildungen auf Rn, die wir deshalb auch als die linearen Codeisometrien auf Rnbezeichnen. Von den Eigenschaften des Hamming-Gewichts wird hierf¨ ur nur ben¨ otigt, dass es invariant unter Multiplikation mit Einheiten ist, und dass es ein Gewicht gibt, das genau von den Vektoren der Bauart λemit einer Einheit λ∈R∗ und einem Einheitsvektor eangenommen wird. Weil diese Eigenschaften auch auf whom und wsym zutreffen, sind die linearen Codeisometrien auch genau die linearen Isometrien (Rn, dhom)→(Rn, dhom) und auch genau die linearen Isometrien (Rn, dsym)→(Rn, dsym). Semilineare Isometrien Weiter definieren wir die semilinearen Codeisometrien auf Rndurch die Menge aller Abbildungen f◦ρ, wobei f∈Mon(n, R) eine monomiale Abbildung auf Rnist und ρ∈Aut(R) einen Ringautomorphismus von Rbezeichnet, der komponentenweise auf Rnangewendet wird. Auch hier ist der Monomialanteil fund der Automorphismenanteil ρdurch die semilineare Abbildung f◦ρeindeutig festgelegt. Die semilinearen Codeisometrien bilden eine Gruppe, die die monomialen Abbildungen als Normalteiler enthalten. Genauer ist die Gruppe der semilinearen Codeisometrien ein semidirektes Produkt Mon(n, R)oθAut(R), wobei der definierende Homomorphismus θ: Aut(R)→Aut(Mon(n, R)) gegeben ist durch θ(ρ) = (c7→ diag(v)Pσc)7→ (c7→ diag(ρ(v))Pσc). Nach Fakt 2.1.4 bilden die semilinearen Codeisometrien also eine zu (R∗oSn)oZrisomorphe Untergruppe von ΓL(Rn R).25 Mit Hilfe des Hauptsatzes der projektiven HjelmslevGeometrie (siehe Abschnitt 2.3.1) kann man sich ¨ uberlegen, dass die semilinearen Codeisometrien genau die Isometrien (Rn, wHam)→(Rn, wHam) sind, die Untermoduln von Rnwieder auf Untermoduln vom gleichen konjugierten Umriss abbilden. Wie zuvor kann hier anstelle von wHam auch wieder whom oder wsym benutzt werden. Die Gruppe Gder (semi-)linearen Codeisometrien operiert auf Rnund damit auch auf der Menge der Untermoduln von Rnund partitioniert diese in Bahnen. Zwei R-lineare 25Die semilineare Gruppe ΓL(Rn R) besteht aus allen R-semilinearen Abbildungen Rn→Rn, d.h. aus allen Abbildungen f, f¨ ur die ein Automorphismus ρ∈Aut(R) existiert mit f(v+w) = f(v) + f(w) und f(λv) = ρ(λ)f(v) f¨ ur alle Vektoren v,w∈Rnund alle Skalare λ∈R. 26 2.2. Lineare Codes ¨ uber Galois-Ringen der Kettenl¨ ange 2 Codes heißen nun (semi-)linear isometrisch (auch: isomorph,¨ aquivalent), wenn sie unter der Operation von Gin der gleichen Bahn liegen. Sind zwei Codes Cund Dsemilinear isometrisch, so schreiben wir C∼ =D. Die (semi-)lineare Automorphismengruppe eines Codes Cist der Stabilisator von Cunter der Operation von G. Isometrische Codes stimmen in vielen codierungstheoretischen Eigenschaften ¨ uberein, sie haben beispielsweise dieselben Gewichtsz¨ ahler. Zur Untersuchung von Isometriefragen auf Z4-linearen Codes ist der Algorithmus von Thomas Feulner in [39] sehr n¨ utzlich. Dort wird der Ansatz f¨ ur herk¨ ommliche lineare Codes aus [38] auf die Situation der Z4-linearen Codes angepasst. Der Algorithmus berechnet aus einer Generatormatrix die Automorphismengruppe und eine kanonische Form des davon erzeugten Codes. 2.2.4. Dualit¨ at Der orthogonale Untermodul C⊥im Sinne von Abschnitt 2.1.4 heißt der duale Code von C. Hat Cden konjugierten Umriss cshp(C) = λ= (λ0, λ1) = (k1+k2, k1), so hat nach Fakt 2.1.9(a) der duale Code den konjugierten Umriss cshp(C⊥) = ¯ λ. In der Schreibweise cshp(C⊥) = (k⊥ 1+k⊥ 2, k⊥ 1) gilt k⊥ 1=n−(k1+k2) und k⊥ 2=k2. Ist Cder Zeilenraum einer systematischen Generatormatrix wie in Gleichung (2.1), so ist eine Generatormatrix von C⊥gegeben durch (AC −B)>−C>Ik⊥ 1 −pA>pIk20k2×k⊥ 1. (2.2) (Siehe [28, Gleichung (3)] f¨ ur R=Z4, [22, Gleichung (3)] f¨ ur R=Zpmund [115, Th. 3.10] f¨ ur endliche kommutative Kettenringe.) Diese Generatormatrix ist bis auf eine Permutation der Koordinaten wieder systematisch. Im Fall C ≤ C⊥heißt Cselbstorthogonal, im Fall C∼ =C⊥isodual und im Fall C=C⊥ selbstdual. Selbstdualit¨ at und Selbstorthogonalit¨ at sind im Allgemeinen nicht invariant unter (semi)-linearen Codeisometrien. Um die Selbstorthogonalit¨ at zu erhalten, m¨ ussen beide Gruppen auf Skalierungsanteile v= (v1, . . . , vn) mit der Eigenschaft v2 i= 1 f¨ ur alle i∈ {1, . . . , n}eingeschr¨ ankt werden. Die symmetrisierten Gewichtsz¨ ahler von Cund C⊥k¨ onnen durch die MacWilliamsTransformation ineinander umgerechnet werden: Fakt 2.2.9 (MacWilliams-Transformation [113, Prop. 3]) Sei Cein R-linearer Code. Mit der Variablensubstitution   Y0 Y1 Y2 =  0−1 1 −q q −1 1 q2−q q −1 1   X0 X1 X2  gilt wsym(C⊥)(X0, X1, X2) = wsym(C)(Y0, Y1, Y2) wsym(C)(1,1,1) . 27 2. Grundlagen Die Variablensubstitution aus Fakt 2.2.9 wird MacWilliams-Transformation genannt. Bleibt der symmetrisierte Gewichtsz¨ ahler eines (nicht notwendig linearen) Codes C¨ uber Runter dieser Transformation unver¨ andert, so heißt Cformal selbstdual. Isoduale Codes sind stets auch formal selbstdual. 2.2.5. Radikalcode und Torsionscode Wir betrachten die Multiplikation mit pals eine Abbildung auf C: Sei µC:C → C, c7→ pc. Die Abbildung µCist ein Homomorphismus von R-Moduln, und es gilt im(µC)≤ker(µC)≤(Rp)n. Definition 2.2.10 Sei Cein R-linearer Code. Wir definieren den Radikalcode C(1) und den Torsionscode C(2) durch C(1) =ϕ−1(im(µC)) und C(2) =ϕ−1(ker(µC)). Dabei bezeichnet ϕ:Fn q→(Rp)nden im Zusammenhang mit Torsionsvektoren auf Seite 18 eingef¨ uhrten Isomorphismus von R-Moduln. Radikalund Torsionscode sind beide Fq-linear. Der Radikalcode C(1) stimmt mit dem Bild modulo Rp von C¨ uberein, und der Torsionscode C(2) ist das ϕ−1-Bild aller Torsionsvektoren in C. Ist der Code Cdurch eine systematische Generatormatrix wie in Gleichung (2.1) gegeben, so erhalten wir systematische Generatormatrizen von C(1) und C(2) als Ik1¯ A¯ B∈Fk1×n qund Ik10k1×k2¯ B−¯ A¯ C 0k2×k1Ik2¯ C∈F(k1+k2)×n q, (2.3) wobei f¨ ur eine Matrix M¨ uber Rdie durch eintragsweise Reduktion modulo Rp enstehende Matrix ¨ uber Fqmit ¯ Mbezeichnet wird. Fakt 2.2.11 Sei Cein R-linearer Code und cshp(C)=(λ0, λ1)=(k1+k2, k1). Es gilt: (a) dimFq(C(1)) = λ1=k1und dimFq(C(2)) = λ0=k1+k2. (b) C(1) ≤ C(2) mit Gleichheit genau dann, wenn Cein freier Code ist. (c) (C⊥)(1) = (C(2))⊥und (C⊥)(2) = (C(1))⊥. (d) Ist Cein selbstorthogonaler Code, so ist auch C(1) selbstorthogonal. Im Fall R=Z4 ist C(1) zus¨ atzlich doppeltgerade, d.h. alle auftretenden Hamming-Gewichte sind Vielfache von 4. (e) Ist Cein selbstdualer Code, so ist C(1) = (C(2))⊥und C(2) = (C(1))⊥. (f) Es gilt (q−1)dHam(C(1))≤dhom(C)≤qdHam(C(2)). 28 2.2. Lineare Codes ¨ uber Galois-Ringen der Kettenl¨ ange 2 Bemerkung 2.2.12 (a) Die Codes C(1) und C(2) wurden f¨ ur R=Z4in [28] eingef¨ uhrt. Dort finden sich alle Aussagen von Fakt 2.2.11 bis auf Teil (c) und Teil (f). In [115] wurde mit den Codes (C:γi) eine Verallgemeinerung f¨ ur allgemeine kommutative Kettenringe angegeben, die unsere Situation der Galois-Ringe der Kettenl¨ ange 2 abdeckt. Die Codes (C:γi) h¨ angen eng mit der Ulm-Kaplansky-Reihe zusammen, siehe [69, Rem. 3.1]. (b) Mit Hilfe unserer Vorarbeiten ist Fakt 2.2.11 nicht schwer zu beweisen: Wir k¨ onnen o.E. annehmen, dass Cdurch eine systematische Generatormatrix wie in Gleichung (2.1) erzeugt wird (denn Dualit¨ at ist invariant unter Permutations¨ aquivalenz). Die einzelnen Aussagen lassen sich nun ausgehend von den abgeleiteten Generatormatrizen in den Gleichungen (2.2) und (2.3) leicht nachrechnen. (c) Ein freier selbstdualer Z4-linearer Code Chat stets eine durch 8 teilbare L¨ ange, denn f¨ ur diesen ist nach Fakt 2.2.11 (b), (d) und (e) C(1) =C(2) ein selbstdualer doppeltgerader F2-linearer Code. Solche F2-linearen Codes werden auch selbstduale Codes vom Typ II genannt und existieren nur f¨ ur durch 8 teilbare L¨ angen. 2.2.6. Modifikationen R-linearer Codes Punktieren, Verk¨ urzen, Residuum Zu einer Teilmenge I⊆ {1, . . . , n}bezeichne {I={1, . . . , n} \ Idie komplement¨ are Koordinatenmenge und πI:Rn→R#I,(c1, . . . , cn)7→ (ci)i∈Iden Restriktionshomomorphismus auf die Koordinaten in I.26 Definition 2.2.13 Sei Cein R-linearer Code der L¨ ange nund I⊆ {1, . . . , n}. Der in Ipunktierte Code (engl. punctured code) ist gegeben durch PI(C) = π{I(C), und der in I verk¨ urzte Code (engl. shortened code) ist gegeben durch SI(C) = π{I(C∩ker(πI)). Weiter ist zu einem Codewort c∈ C der residuelle Code in c(engl. residual code) gegeben durch den in supp(c)punktierten Code resc(C) = Psupp(c)(C). Fakt 2.2.14 Sei Cein R-linearer Code der L¨ ange nund der homogenen Minimaldistanz d. (a) Sei I⊆ {1, . . . , n}. Es gilt PI(C)⊥=SI(C⊥)und SI(C)⊥=PI(C⊥). (b) F¨ ur alle a∈ {1, . . . , n}gilt: Ist d>q, so ist der in apunktierte Code P{a}(C)ein R-linearer Code mit den Parametern [n−1,cshp(C),≥d−q]R. 26 ¨ Ublicherweise werden die restringierten Codew¨ orter nicht mit der Koordinatenmenge Iindiziert, sondern mit {1,...,#I}. 29 2. Grundlagen (c) F¨ ur alle a∈ {1, . . . , n}gilt: Der in averk¨ urzte Code S{a}(C)ist ein R-linearer Code mit den Parametern n−1,#C #π{a}(C),≥dR . (d) Sei c∈ C ein Codewort mit (q−1)wHam(c)< d. Dann ist der residuelle Code resc(C)in cein R-linearer Code mit den Parametern n−wHam(c),#C #(Rc),≥d−(q−1)wHam(c)R . Beweis. Die Teile (b) und (c) sind klar. Teil (d) wurde in [17, Cor. 1] bewiesen. Konstruktion X ¨ Ahnlich wie f¨ ur herk¨ ommliche lineare Codes ¨ uber K¨ orpern (z.B. [108, Ch. 18, §7.1]) l¨ asst sich die Konstruktion X auch f¨ ur R-lineare Codes formulieren: Definition 2.2.15 Seien C1und C2zwei R-lineare Codes der L¨ ange nmit den homogenen Minimaldistanzen d1und d2und C1≤ C2. Sei weiter ein R-linearer Hilfscode (engl: auxiliary code)Avon L¨ ange na, homogener Minimaldistanz daund konjugiertem Umriss cshp(A) = cshp(C2/C1)gegeben. Nach Fakt 2.1.5 existiert ein R-Modul-Isomorphismus ϕ:C2/C1→ A. Wir definieren die Konstruktion X aus C1≤ C2mit dem Hilfscode Aals den R-linearen Code ˆ C={(c, ϕ(c+C1)) |c∈ C2} der L¨ ange n+naund der Gr¨ oße #C2. Bemerkung 2.2.16 (a) Die Konstruktion X h¨ angt neben den Codes C1,C2und Aauch vom gew¨ ahlten Isomorphismus ϕab. Somit k¨ onnen im Allgemeinen mehrere Isomorphietypen von Codes als Konstruktion X aus C1≤ C2mit dem Hilfscode Akonstruiert werden. (b) ¨ Ublicherweise wird die Konstruktion X dazu benutzt, um ausgehend von zwei Codes C1≤ C2von hoher Minimaldistanz d1bzw. d2einen weiteren guten Code ˆ C zu konstruieren. Hierzu sucht man nach einem m¨ oglichst kurzen Hilfscode Avom konjugierten Umriss cshp(C2/C1) und von Minimaldistanz da=d2−d1. Die Wahl von ϕist dann uninteressant, weil nach Fakt 2.2.17 die Minimaldistanz des Codes ˆ Cbereits festgelegt ist. Aus diesem Grund werden f¨ ur die Konstruktion X in der Regel die Codes C1,C2und A, aber nicht der Homomorphismus ϕangegeben. (c) Tats¨ achlich ist der durch Konstruktion X entstehende Code ˆ Cbereits durch die R-lineare Abbildung ρ:C2→Rna,c7→ ϕ(c+C1) 30 2.3. Projektive Hjelmslev-Geometrie festgelegt. Ausgehend von ρerh¨ alt man C2als den Definitionsbereich und die anderen beiden Codes als C1= ker(ρ) und A= im(ρ) zur¨ uck. Durch Anwenden des Homomorphiesatzes auf ρrekonstruiert man schließlich den Isomorphismus ϕ:C2/C1→ A. Fakt 2.2.17 Ein durch Konstruktion X aus C1≤ C2mit dem Hilfscode Agewonnener Code ˆ Cist ein R-linearer Code mit den Parametern hn+na,cshp(C2),ˆ diR, wobei min(d1, d2+da)≤ˆ d≤d1gilt. Der Beweis l¨ asst sich v¨ ollig analog zur Situation von Codes ¨ uber endlichen K¨ orpern f¨ uhren: Beweis. Weil ϕeine lineare Abbildung ist, ist ˆ Cein R-linearer Code und als R-Modul isomorph zu C2. Die homogene Minimaldistanz von ˆ Ckann also als das minimale homogene Gewicht von ˆ Cberechnet werden. Jedes Codewort von ˆ Chat die Form ˆ c= (c, ϕ(c+C1)) mit c∈ C2. (i) Ist c∈ C1, so ist ϕ(c+C1) = 0. Wenn cdas Nullwort ist, so ist auch ˆ cdas Nullwort. Andernfalls ist whom(ˆ c) = whom(c)≥d1. F¨ ur die Codew¨ orter c∈ C1von minimalem Gewicht gilt whom(ˆ c) = d1. (ii) Ist c/∈ C1, so ist c6=0und ϕ(c+C1)6=0und es folgt whom(ˆ c) = whom(c) + whom(ϕ(c+C1)) ≥d2+da. 2.3. Projektive Hjelmslev-Geometrie Die Hjelmslev-Geometrie geht zur¨ uck auf den Artikel [56] aus dem Jahr 1916, in dem der d¨ anische Mathematiker Johannes Hjelmslev eine ”Geometrie der Wirklichkeit” vorstellte, in der sich zwei verschiedene Geraden in mehreren Punkten schneiden k¨ onnen und demzufolge die Verbindungsgerade zweier verschiedener Punkte nicht immer eindeutig ist. Dieser Abschnitt hat die ben¨ otigten Grundlagen der projektiven Hjelmslev-Geometrie ¨ uber Galois-Ringen der Kettenl¨ ange 2 zum Inhalt. Wir richten uns dabei nach [65, 69, 71], wo die projektive Hjelmslev-Geometrie allgemeiner ¨ uber endlichen Kettenringen beschrieben wird. Im Folgenden ist wieder peine Primzahl, reine positive ganze Zahl, Rder Galois-Ring GR(p2, r), q=prdie Ordnung seines Restklassenk¨ orpers und k≥2. 31 2. Grundlagen 2.3.1. Definitionen Sei MRein freier R-Modul vom Rang k. Der Verband aller Untermoduln von MRwird mit PHG(MR) bezeichnet und heißt die projektive Hjelmslev-Geometrie der Dimension k−1¨ uber R. Bis auf Isomorphie h¨ angt der Verband PHG(MR) nur von Rund dem Rang kvon MRab. Die freien Untermoduln vom Rang 1 heißen Punkte, diejenigen vom Rang 2 Geraden und diejenigen vom Rang k−1Hyperebenen von PHG(MR). Die Menge aller Punkte, Geraden bzw. Hyperebenen wird mit P=G(MR,(1,1)), L=G(MR,(2,2)) bzw. H=G(MR,(k−1, k−1)) bezeichnet, zur Notation siehe Abschnitt 2.1.4. Wir werden die geometrische Sprechweise der Inzidenz benutzen, die Inzidenzrelation auf den Objekten von PHG(MR) ist die Inklusion von Mengen. Koordinatenvektoren Nach Fakt 2.1.5 gilt MR∼ =Rk R, so dass wir im Folgenden Mmit Rkidentifizieren d¨ urfen. Sei x∈ P ein Punkt und H∈ H eine Hyperebene. Ein Vektor v∈Rkmit x=Rvheißt Koordinatenvektor des Punkts x. Analog dazu heißt ein Vektor v∈Rkmit H=v⊥ Koordinatenvektor der Hyperebene H. Offenbar hat jeder Punkt und jede Hyperebene genau #R∗=q(q−1) Koordinatenvektoren, und wenn vein Koordinatenvektor eines Punkts oder einer Hyperebene ist, so ist die Menge aller Koordinatenvektoren durch R∗vgegeben. Die als Koordinatenvektoren eines Punkts oder einer Hyperebene auftretenden Vektoren sind genau die torsionsfreien Vektoren in Rk. Jedem Punkt xund jeder Hyperebene Hwird willk¨ urlich ein fest gew¨ ahlter Koordinatenvektor κ(x) bzw. κ(H) zugewiesen. Beispielsweise kann man unter den m¨ oglichen Koordinatenvektoren immer denjenigen Vektor ausw¨ ahlen, dessen erster invertierbarer Eintrag gleich 1 ist. Multimengen Wie ¨ ublich ist eine Multimenge M¨ uber einer endlichen Grundmenge Xeine Abbildung X→N, die jedem Element x∈Xeine Vielfachheit (auch Multiplizit¨ at)M(x) zuordnet. Die Multiplizit¨ at M(x) gibt an, wie oft die Multimenge Mdas Element xenth¨ alt. Die M¨ achtigkeit #M=Px∈XM(x) ist die Anzahl der Elemente von M, die entsprechend ihrer Vielfachheit gez¨ ahlt werden. Weiter bezeichnen wir die Menge {x∈X|M(x)6= 0} als den Tr¨ ager von M. Ist S⊆X, so k¨ onnen wir Sdurch die charakteristische Funktion χS:X→N, x 7→ (1 falls x∈X, 0 falls x /∈X auch als eine Multimenge auf Xauffassen. Kollineationen Ein Verbandsisomorphismus zwischen zwei Hjelmslev-Geometrien wird auch als Kollineation bezeichnet; die beiden Geometrien heißen dann isomorph. Aus der Diskussion in Abschnitt 2.3.2 geht hervor, dass eine Kollineation bereits durch die Bilder der Punkte 32 2.3. Projektive Hjelmslev-Geometrie festgelegt ist. Deshalb d¨ urfen wir eine Kollineation zwischen zwei Hjelmslev-Geometrien auch als eine Abbildung zwischen den beiden zugeh¨ origen Punktmengen auffassen. Die Gruppe der Verbandsautomorphismen von PHG(MR) heißt auch Kollineationsgruppe von PHG(MR). In perfekter Analogie zu den herk¨ ommlichen desargueschen projektiven Geometrien ist nach dem Hauptsatz der projektiven Hjelmslev-Geometrie [96] die Kollineationsgruppe von PHG(MR) durch die Gruppe PΓL(k, R) gegeben. Die Operation der Kollineationsgruppe von PHG(MR) induziert einen Isomorphiebegriff auf den Multimengen von Punkten in PHG(MR): Zwei Multimengen kund k0von Punkten heißen isomorph, wenn sie in derselben Bahn unter dieser Gruppenoperation liegen, d.h. wenn eine Kollineation f:P → P existiert mit k◦f=k0. In diesem Fall schreiben wir k∼ =k0. Der Stabilisator von kunter der Operation der Kollineationsgruppe wird als die Kollineationsgruppe oder Automorphismengruppe von kbezeichnet. Der zu PHG(MR) duale Verband ist die duale Hjelmslev-Geometrie. Beim ¨ Ubergang zur dualen Geometrie wird die Rolle der Punkte und Hyperebenen vertauscht. Nach Fakt 2.1.9(c) sind PHG(MR) und die zu PHG(MR) duale Hjelmslev-Geometrie isomorph. Teilr¨ aume Ein Untermodul Uvon MRist genau dann mit mindestens einem Punkt inzident, wenn cshp(U)16= 0 ist. In dieser Situation ist Udurch die Menge kUder mit Uinzidenten Punkte eindeutig festgelegt, so dass wir Umit kUidentifizieren d¨ urfen. Die Punktmenge kUheißt dann Teilraum von PHG(MR) vom konjugierten Umriss cshp(kU) = cshp(U). Ist Uein freier Modul, so heißt kUauch Hjelmslev-Teilraum. Punkte, Geraden und Hyperebenen sind Hjelmslev-Teilr¨ aume von PHG(MR) vom konjugierten Umriss (1,1), (2,2) bzw. (k−1, k −1). Der Spann einer Multimenge kvon Punkten in PHG(MR) ist der kleinste Teilraum von PHG(MR), der alle Punkte aus dem Tr¨ ager von kenth¨ alt. Nachbarn Anders als in der herk¨ ommlichen projektiven Geometrie kann es in PHG(Rk) passieren, dass zwei verschiedene Punkte durch mehr als eine Gerade verbunden sind. In diesem Fall heißen die beiden Punkte Nachbarn. Auf duale Weise erhalten wir auch einen Nachbarschaftsbegriff auf den Hyperebenen. F¨ ur zwei Koordinatenvektoren vund w∈Rk sind die beiden Punkte Rvund Rwgenau dann Nachbarn, wenn die beiden Hyperebenen v⊥und w⊥Nachbarn sind. Dies ist genau dann der Fall, wenn p(v−w) = 0ist. Damit erkennt man, dass die Nachbarrelation eine ¨ Aquivalenzrelation ist, welche die Punktmenge Pin Punktklassen und die Menge der Hyperebenen Hin Hyperebenenklassen partitioniert. Die Punktklasse eines Punkts xwerden wir mit [x] und die Hyperebenenklasse einer Hyperebene Hmit [H] bezeichnen. Punktund Hyperebenenklassen27 sind Teilr¨ aume von PHG(Rk) vom konjugierten Umriss cshp([x]) = (k, 1) bzw. cshp([H]) = (k, k −1). Weiter heißt der Punkt xNachbar der Hyperebene H, wenn H 27An dieser Stelle identifizieren wir wie ¨ ublich [H] mit der Menge aller Punkte, die in irgendeiner Hyperebene in [H] enthalten sind. 33 2. Grundlagen Tabelle 2.4.1.: Symmetrisierter Gewichtsz¨ ahler des Simplex-Code Sim(k, R) Typ #Codew¨ orter ω0ω1ω2whom S qk(qk−1) q2(k−1) qk−2(qk−1−1) qk−2·qk−1−1 q−1q2k−1−qk−1 pS qk−1 0 q2(k−1) qk−1·qk−1−1 q−1q2k−1 0 1 0 0 qk−1·qk−1 q−10 (b) Das Gray-Bild von Sim(k, R)hat die Parameter qk·qk−1 q−1, q2k, q2k−1−qk−1q und den Hamming-Gewichtsz¨ ahler 1 + qk(qk−1)Xq2k−1−qk−1+ (qk−1)Xq2k−1. Bemerkung 2.4.2 (a) Das Gray-Bild von Sim(k, R) hat hervorragende Parameter, als Fq-linearer Code w¨ are es Griesmer-optimal. Andererseits ist Sim(k, R) kein BTL-Code, denn mit den MacDonald-Codes aus [116] existiert stets ein Fq-linearer Code mit denselben Parametern.30 Als eine weitere Konstruktionsm¨ oglichkeit kann man die SimplexKonstruktion ¨ uber dem Kettenring Fq[X]/(X2) durchf¨ uhren; die verallgemeinerten Gray-Bilder solcher Codes sind stets linear. Tats¨ achlich sind alle linearen Codes mit den entsprechenden Parametern zu den MacDonald-Codes isomorph [124, Th. 2.1]. Ein kurzer Beweis ¨ uber geometrisches Dualisieren findet sich in [35, Prop. 5]. Zur Darstellung allgemeinerer MacDonald-Codes ¨ uber endlichen Kettenringen siehe [64, Th. 11] und [65, Th. 6.1]. (b) Das Beispiel der Simplex-Codes belegt, dass die Konstruktionsmethode ”GrayBilder R-linearer Codes” – unabh¨ angig vom Parameter q– prinzipiell in der Lage ist, sehr gute Blockcodes zu generieren. 2.4.2. Teichm¨ uller-Codes und Kerdock-Codes Es sei p= 2. Wir betrachten die Ringerweiterung R= GR(4, r)⊆S= GR(4, rk) mit k≥3 ungerade. F¨ ur die Teichm¨ uller-Gruppen U∗von Rund T∗von Sgilt U∗≤T∗ und [T∗:U∗] = (qk−1)/(q−1). Verm¨ oge der R-Modul-Isomorphie S∼ =Rkk¨ onnen wir ein Vertretersystem von T∗/U∗als eine Menge von (qk−1)/(q−1) Vektoren in Rkauffassen. Weil alle solchen Elemente in S∗liegen, hat jeder dieser Vektoren mindestens einen invertierbaren Eintrag, d.h. jeder Vektor ist der Koordinatenvektor eines 30Die Codes werden in [116] auf Seite 108 mit Mmbezeichnet. Die dortigen Parameter kund mm¨ ussen in unserer Schreibweise auf 2kund kgesetzt werden. F¨ ur den bin¨ aren Fall q= 2 wurden die Codes bereits in [107] als Type 13-Codes eingef¨ uhrt. 40 2.4. Beispiele R-linearer Codes Punkts in PHG(Rk). Die durch diese Koordinatenvektoren gegebene Punktmenge heißt Teichm¨ uller-Punktmenge Tq,k. Da je zwei Vektoren in derselben Nebenklasse von T∗/U∗ denselben Punkt beschreiben, ist Tq,k unabh¨ angig von der Wahl des Vertretersystems. Betrachtet man die Teichm¨ uller-Menge T=T∗∪ {0}als eine Menge von qkaffinen Koordinatenvektoren, so erh¨ alt man eine Teilmenge der Punktmenge von AHG(Rk). Das Bild dieser Punktmenge in PHG(Rk+1) unter der Standardeinbettung heißt KerdockPunktmenge Kq,k+1. Sowohl Tq,k als auch Kq,k+1 spannen jeweils die komplette Punktmenge der Umgebungsgeometrie PHG(Rk) bzw. PHG(Rk+1) auf. Die erzeugten Codes Tq,k = cde(Tq,k) und Kq,k = cde(Kq,k) heißen Teichm¨ uller-Codes bzw. Kerdock-Codes. Bemerkung 2.4.3 (a) Der Name Teichm¨ uller-Punktmenge (Teichm¨ uller set) stammt aus [55, 68], [59, Ex. II.3]. Sie enthalten mit Tq,3die Hyperovale aus [67] als Spezialfall. Der naheliegende Bezeichner Teichm¨ uller-Codes f¨ ur die erzeugten Codes wurde in [91, 92] eingef¨ uhrt. Die Teichm¨ uller-Codes fassen die verk¨ urzten Z4-linearen Kerdock-Codes (q= 2) und die von den Hyperovalen in [67] kommenden Codes (k= 3) in einer allgemeineren Codeklasse zusammen. Das Spektrum der Teichm¨ uller-Punktmengen und der symmetrisierte Gewichtsz¨ ahler der Teichm¨ uller-Codes lassen sich aus [59, Ex. II.3] ableiten. In Abschnitt 3.1 werden wir die Teichm¨ uller-Punktmengen und -Codes verallgemeinern und erhalten damit einen zus¨ atzlichen Parameter s. Spektrum und symmetrisierte Gewichtsz¨ ahler ergeben sich dann auch als der Spezialfall s= 0 aus den S¨ atzen 3.1.8 und 3.1.10. (b) Unter den Kerdock-Codes verstand man zun¨ achst die von Kerdock in [80] eingef¨ uhrten nichtlinearen bin¨ aren Blockcodes. In [111, 52] wurde gezeigt, dass sich diese bis auf eine Koordinatenpermutation als Gray-Bild der Z4-linearen KerdockCodes K2,k+1 darstellen lassen. Diese Z4-linearen Kerdock-Codes werden wir im Folgenden einfacher mit Kk+1 und die zugeh¨ origen Punktmengen mit Kk+1 bezeichnen. In [99] wurden die Codes Kk+1 auf die Codes Kq,k+1 ¨ uber beliebigen Galois-Ringen der Charakteristik 4 verallgemeinert. (c) Im Z4-linearen Fall gilt #U∗= 1, und damit erh¨ alt man den Teichm¨ uller-Code T2,k durch Verk¨ urzen des Kerdock-Codes Kk+1 an der zum Teichm¨ uller-Element 0 geh¨ orenden Position. Weil nach [52, Sec. V-E] die Automorphismengruppe der Z4-linearen Kerdock-Codes transitiv (sogar doppelt transitiv) auf den Positionen operiert, f¨ uhrt auch das Verk¨ urzen an jeder anderen Position zum Code T2,k. (d) Im vorliegenden Fall der geraden Charakteristik hat die Teichm¨ uller-Menge Teine reiche kombinatorische Struktur (siehe. z.B. [8, Sec. III], [59, Sec. VI], wir werden diese Aussagen in Abschnitt 3.1 verallgemeinern), wodurch sich Codes mit sehr wenigen Gewichten und hoher Minimaldistanz ergeben und ein allgemeiner Beweis der Eigenschaften erm¨ oglicht wird. Prinzipiell sind die genannten Konstruktionen 41 2. Grundlagen Tabelle 2.4.2.: Spektrum der Kerdock-Punktmenge Kq,k+1 Typ #Hyperebenen ω0ω1ω2 H++ 1 2 qk−1 q−1(qk+qk+1 2)qk−qk−1qk−1−qk−2−(qk−1 2−qk−3 2)qk−2+ (qk−1 2−qk−3 2) H+1 2(qk−1)(qk−qk+1 2)qk−qk−1qk−1−qk−2−qk−3 2qk−2+qk−3 2 H0qkqk0 0 H−1 2(qk−1)(qk+qk+1 2)qk−qk−1qk−1−qk−2+qk−3 2qk−2−qk−3 2 H−− 1 2 qk−1 q−1(qk−qk+1 2)qk−qk−1qk−1−qk−2+ (qk−1 2−qk−3 2)qk−2−(qk−1 2−qk−3 2) auch in ungerader Charakteristik durchf¨ uhrbar. Hier verh¨ alt sich Tjedoch ziemlich chaotisch und die erzeugten Codes erscheinen aufgrund vieler verschiedener Gewichte und einer schlechten Minimaldistanz uninteressant. (e) Durch Punktieren an der Position des Teichm¨ uller-Elements 0 entsteht aus dem Kerdock-Code Kq,k+1 der punktierte Kerdock-Code ˙ Kq,k+1. An dieser Stelle sei angemerkt, dass die Parameter in [113, Th. 4] f¨ ur den punktierten Kerdock-Code fehlerhaft sind: Demzufolge h¨ atte der Code ˙ K4,3+1 nur die homogene Minimaldistanz 176. Tats¨ achlich hat das Gray-Bild aber die BTKL-Parameter (252,48,177)4. Auch operiert die Automorphismengruppe im Allgemeinen nicht mehr transitiv auf den Positionen: Punktieren von K4,3+1 an jeder anderen Position liefert einen Code der minimalen homogenen Distanz 176. Fakt 2.4.4 (a) Die Kerdock-Punktmenge Kq,k+1 ist in einer affinen Teilgeometrie von PHG(Rk+1) enthalten. Jede Punktklasse dieser affinen Teilgeometrie enth¨ alt genau einen Punkt von Kq,k+1. Tabelle 2.4.2 zeigt das Spektrum von Kq,k+1. (b) Der Kerdock-Code Kq,k+1 ist ein fetter, freier Code vom Rang k+ 1 mit den Parametern hqk,(k+ 1, k + 1),(q−1)(qk−qk−1 2)iR. Tabelle 2.4.3 zeigt den symmetrisierten Gewichtsz¨ ahler von Kq,k+1. Beweis. Der symmetrisierte Gewichtsz¨ ahler von Kq,k+1 kann aus dem vollst¨ andigen Gewichtsz¨ ahler in [100, Th. 1] abgeleitet werden. Satz 2.3.1(a) liefert das Spektrum von Kq,k+1. Nach Konstruktion sind die Punkte von Kq,k+1 im Bild von AHG(Rk) unter der Standardeinbettung enthalten. Weil die Elemente der Teichm¨ uller-Menge Tein Vertretersystem des Restklassenk¨ orpers Fqkvon Sbilden, liegen keine zwei Punkte in derselben Punktklasse. Damit enth¨ alt jede Punktklasse der affinen Teilgeometrie genau einen Punkt der Kerdock-Punktmenge, und der Spann von Kq,k+1 ist die volle Geometrie PHG(Rk+1). 42 2.4. Beispiele R-linearer Codes Tabelle 2.4.3.: Symmetrisierter Gewichtsz¨ ahler des Kerdock-Codes Kq,k+1 Typ H++ #Cw. 1 2(qk−1)(qk+1 +qk+3 2) ω0qk−qk−1 ω1qk−1−qk−2−(qk−1 2−qk−3 2) ω2qk−2+ (qk−1 2−qk−3 2) whom qk+1 −qk−(qk+1 2−qk−1 2) Typ H+#Cw. 1 2(q−1)(qk−1)(qk+1 −qk+3 2) ω0qk−qk−1 ω1qk−1−qk−2−qk−3 2 ω2qk−2+qk−3 2 whom qk+1 −qk−qk−1 2 Typ H0#Cw. qk+1(q−1) ω0qk ω10 ω20 whom qk+1 −qk Typ H−#Cw. 1 2(q−1)(qk−1)(qk+1 +qk+3 2) ω0qk−qk−1 ω1qk−1−qk−2+qk−3 2 ω2qk−2−qk−3 2 whom qk+1 −qk+qk−1 2 Typ H−− #Cw. 1 2(qk−1)(qk+1 −qk+3 2) ω0qk−qk−1 ω1qk−1−qk−2+ (qk−1 2−qk−3 2) ω2qk−2−(qk−1 2−qk−3 2) whom qk+1 −qk+ (qk+1 2−qk−1 2) Typ pH±#Cw. q(qk−1) ω00 ω1qk−qk−1 ω2qk−1 whom qk+1 −qk Typ pH0#Cw. q−1 ω00 ω1qk ω20 whom qk+1 Typ 0 #Cw. 1 ω00 ω10 ω2qk whom 0 43 2. Grundlagen Tabelle 2.4.4.: Spektrum der Kerdock-Punktmenge Kk+1 ¨ uber Z4 Typ #Hyperebenen ω0ω1ω2 H+22k−2k2k−12k−2−2k−3 22k−2+ 2k−3 2 H02k2k0 0 H−22k−2k2k−12k−2+ 2k−3 22k−2−2k−3 2 Tabelle 2.4.5.: Symmetrisierter Gewichtsz¨ ahler des Z4-linearen Kerdock-Codes Kk+1 Typ #Codew¨ orter ω0ω1ω2wLee H−22k+1 −2k+1 2k−12k−2−2k−3 22k−2+ 2k−3 22k−2k−1 2 H02k+1 2k002k H+22k+1 −2k+1 2k−12k−2+ 2k−3 22k−2−2k−3 22k+ 2k−1 2 2H±2k+1 −2 0 2k−12k−12k 2H01 0 2k0 2k+1 0 1 0 0 2k0 Bemerkung 2.4.5 Im Fall q= 2 reduziert sich die Anzahl der symmetrisierten Gewichte von K2,k+1 =Kk+1 wie auch die Anzahl der Typen im Spektrum von K2,k+1 gegen- ¨ uber dem allgemeinen Fall jeweils um zwei. Denn in den beiden Tabellen fallen jeweils die Typen H+und H++ sowie die Typen H−und H−− zusammen. Außerdem vereinfachen sich die Ausdr¨ ucke in den Tabellen deutlich, so dass wir f¨ ur den Fall R=Z4 bequemlichkeitshalber das Spektrum nochmals in Tabelle 2.4.4 sowie den symmetrisierten Gewichtsz¨ ahler nochmals in Tabelle 2.4.5 auflisten. 44 3. Konstruktionen 3.1. Verallgemeinerte Teichm¨ uller-Codes In [59, Th. V.7] wurde bewiesen, dass eine Teichm¨ uller-Punktmenge ¨ uber R= GR(4, r) in der projektiven Hjelmslev-Geometrie PHG(Rk) f¨ ur ungerades knur zwei Schnittzahlen mit den Hyperebenen zul¨ asst. Dieses Resultat soll nun verallgemeinert werden. Wir werden durch das Kombinieren mehrerer paarweise disjunkter Teichm¨ uller-Punktmengen zwei neue Serien von Punktmengen in PHG(Rk) mit zwei Schnittzahlen konstruieren. Die erste Serie Tq,k,s verallgemeinert die Teichm¨ uller-Punktmengen und erzeugt R-lineare Codes Tq,k,s mit hervorragenden Parametern. In diesen Codes sind die Teichm¨ uller-Codes sowie die Simplex-Codes als Spezialf¨ alle enthalten. Die zweite Serie Uq,k,s erzeugt R-lineare Codes Uq,k,s mit nur zwei von Null verschiedenen Gewichten. In [59] wurde der Nachweis der Schnitteigenschaften ¨ uber ein symmetrisches Translationsschema auf der additiven Gruppe eines Galois-Rings Sder Charakteristik 4 gef¨ uhrt. Das dort betrachtete Translationsschema wird von einer bestimmten Obergruppe der Teichm¨ uller-Gruppe T∗von Sinduziert. In Satz 3.1.5 wird allgemein entschieden, unter welchen Umst¨ anden eine T∗umfassende echte Untergruppe von S∗ein symmetrisches Translationsschema auf (S, +) induziert. Der wesentliche Schritt besteht in Lemma 3.1.4, einer Verallgemeinerung von [59, Lemma VI.1]. Der Nachweis dieses Lemmas kann in weiten Teilen wie in [59] gef¨ uhrt werden. Eine Stelle bereitet jedoch zus¨ atzliche Schwierigkeiten. Die hierf¨ ur ben¨ otigten Aussagen werden in Lemma 3.1.1 und 3.1.2 vorbereitet und erfordern eine Untersuchung von symmetrischen Bilinearformen ¨ uber F2. 3.1.1. Unterr¨ aume vom Typ I und II Die in diesem Abschnitt ben¨ otigten Definitionen und Grundlagen ¨ uber symmetrische Bilinearformen in endlichdimensionalen F2-Vektorr¨ aumen finden sich in Anhang A. Zwei der rang-extremalen Typen von Unterr¨ aumen einer Bilinearform Bt,t mit t∈N spielen in den folgenden Untersuchungen eine wichtige Rolle: Ein Unterraum Uvon Bt,t heiße  vom Typ I, falls Rad(U) = {0}, d.h. falls rk(U) = dim(U). (mit anderen Worten: Die eingeschr¨ ankte Bilinearform B|U×Uist nicht ausgeartet.)  vom Typ II, falls Rad(U) = U⊥, d.h. falls rk(U) = 2 dim(U)−t. (mit anderen Worten: U⊥besteht nur aus isotropen Vektoren.) 45 3. Konstruktionen Unterr¨ aume vom Typ I existieren f¨ ur alle Dimensionen 0, . . . , t und Unterr¨ aume vom Typ II f¨ ur die Dimensionen dt/2e, . . . , t. Lemma 3.1.1 Sei Vein t-dimensionaler F2-Vektorraum mit der Bilinearform Bt,t. Sei weiter Uein Unterraum von Vund σ= dim(U). F¨ ur v∈Vbezeichnen wir die Anzahl der L¨ osungen (x,y)∈(U\ {0})×Uder Gleichung x⊥(y+v)mit Nv. Die Zahl Nv ist genau dann f¨ ur alle v∈V\Ugleich, wenn Uvom Typ I oder vom Typ II ist. In diesem Fall gilt Nv=(22σ−1−2σ−1falls Uvom Typ I, 22σ−1−2σfalls Uvom Typ II. Beweis. Sei B=Bt,t. Wegen B(x,y+v) = B(x,y) + B(x,v) sind die Vektorpaare (x,y)∈(U\ {0})×Uzu z¨ ahlen, f¨ ur die B(x,y) = B(x,v) ist. Ist x/∈Rad(U), so gibt es stets #U/2 Vektoren ymit B(x,y) = B(x,v). Dies ergibt (#U−# Rad(U))(#U/2) L¨ osungspaare mit x/∈Rad(U). Ist x∈Rad(U), so ist immer B(x,y) = 0. F¨ ur ein L¨ osungspaar (x,y) muss also B(x,v) = 0 gelten, d.h. x∈(Rad(U)∩v⊥)\ {0}. Folglich gibt es (#(Rad(U)∩v⊥)−1)#UL¨ osungspaare mit x∈Rad(U). Damit Nvf¨ ur alle v∈V\Ugleich ist, muss also f¨ ur alle v∈V\Uder Unterraum Rad(U)∩v⊥, bzw. dazu ¨ aquivalent der Unterraum (Rad(U)∩v⊥)⊥= Rad(U)⊥+hvi=U+U⊥+hvi stets dieselbe Dimension haben. Hierf¨ ur gibt es zwei M¨ oglichkeiten: (i) F¨ ur alle v∈V\Uist v∈U+U⊥. Dies ist ¨ aquivalent zu U+U⊥=V, d.h. Rad(U) = U∩U⊥={0}und weiter Uvom Typ I. Mit rk(U) = σergibt sich Nv= (#U−1)#U 2+ 0 = 22σ−1−2σ−1. (ii) F¨ ur alle v∈V\Uist v/∈U+U⊥. Dies ist ¨ aquivalent zu U⊥⊆U, d.h. Rad(U) = U∩U⊥=U⊥und weiter Uvom Typ II. Mit rk(U) = 2σ−tergibt sich Nv= (#U−#U⊥)#U 2+ #U#U⊥ 2−1= 22σ−1−2σ. Lemma 3.1.2 Seien kund rpositive ganze Zahlen, q= 2r,σ∈ {0, . . . , kr}und die Spurform auf dem F2-Vektorraum Fqkvorgegeben. (a) Der F2-Vektorraum Fqkhat genau dann einen Fqumfassenden Unterraum Uder Dimension σvom Typ I, wenn gilt: σ∈({r, r + 2, r + 4, . . . , kr}falls k ungerade, {2r, 2r+ 2,2r+ 4, . . . , kr}falls k gerade. 46 3.1. Verallgemeinerte Teichm¨ uller-Codes (b) Der F2-Vektorraum Fqkhat genau dann einen Fqumfassenden Unterraum Uder Dimension σvom Typ II, wenn gilt: σ∈k 2r, k 2r+ 1, . . . , kr. Beweis. Ist f= TrF2die Spur auf Fqksowie g= TrF2die Spur auf Fq, so gilt wegen (2r)i≡1 (mod 2r−1) f¨ ur alle x∈Fq f(x) = kr−1 X i=0 x2i= k−1 X i=0 r−1 X j=0 x2ri+j= k−1 X i=0 r−1 X j=0 (x(2r)i)2j= k−1 X i=0 r−1 X j=0 x2j=k·g(x). Daraus folgt rk(Fq) = (0 falls kgerade, rfalls kungerade. Die Bedingung U≥Fqist ¨ aquivalent zu U⊥≤F⊥ q. Wegen 1 ∈Fqist F⊥ qalternierend. Mit der obigen Rangaussage ist F⊥ qalso vom Typ A(k−1)r,(k−1)rf¨ ur kungerade bzw. A(k−1)r,(k−2)rf¨ ur kgerade. Im Fall von Typ I ist U⊥wegen 1 ∈Uvom Typ A(kr−σ,kr−σ). Ein solcher Unterraum von F⊥ qexistiert f¨ ur ungerades kgenau dann, wenn σ≥rund kr −σgerade ist (also σ−rgerade); und f¨ ur gerades kgenau dann, wenn σ≥2rund σgerade ist. Im Fall von Typ II ist U⊥wegen 1 ∈Uvom Typ A(kr−σ,0). Ein solcher Unterraum von F⊥ qexistiert f¨ ur ungerades kgenau dann, wenn 1 2(k−1)r≥kr −σ, d.h. σ≥r(k+ 1)/2; und f¨ ur gerades kgenau dann, wenn (k−2)r−2(σ−r)≤0, d.h. σ≥kr/2. 3.1.2. Symmetrische Translationsschemata auf (GR(4, t),+) Die im Folgenden ben¨ otigten Grundlagen zur Theorie der Assoziationsschemata finden sich in Anhang B. In diesem Abschnitt sei teine positive ganze Zahl, S= GR(4, t) ein Galois-Ring der Charakteristik 4 und T∗die Teichm¨ uller-Gruppe von S. Zu einer Untergruppe Σ ≤S∗ sei ¯ Σ = S∗\Σ. Im Fall Σ 6=S∗definieren wir die Partition AΣ={{0},2S\ {0},Σ,¯ Σ} von S. Wir wollen allgemein die Frage beantworten, unter welchen Umst¨ anden AΣf¨ ur T∗≤Σ< S∗ein symmetrisches Translationsschema auf (S, +) ist. Um der Anforderung −Σ = Σ zu gen¨ ugen, muss hierf¨ ur sicher −1∈Σ gelten. Bezeichnet H= 1 + 2Sdie Haupteinheiten von S(siehe S. 11), so gilt S∗=T∗·H∼ = T∗×H. Nach Fakt 2.1.3 ist Heine elementarabelsche Gruppe der Form Zt 2. Folglich gibt es eine Bijektion zwischen den T∗umfassenden Untergruppen Σ von S∗und den F2-Untervektorr¨ aumen von H. Zur Angabe einer expliziten Bijektion identifizieren wir weiterhin Smit dem Ring der gestutzten Witt-Vektoren W2(F2t), siehe Abschnitt 2.1.3. 47 3. Konstruktionen Die Abbildung ρ: (F2t,+) →(H, ·), x7→ (1, x) ist dann ein Gruppenhomomorphismus, und jede T∗umfassende Untergruppe Σ hat die Form ΣU=T∗·ρ(U)∼ =T∗×ρ(U), wobei Uein Untervektorraum des F2-Vektorraums F2tist. Weil sich −1 in den gestutzten WittVektoren als (1,1) schreibt, ¨ ubersetzt sich die Bedingung −1∈ΣUin F2⊆U. Es gilt #ΣU= #U·#T∗= 2σ·(2t−1) mit σ= dimF2(U). Lemma 3.1.3 Sei Uein Untervektorraum des F2-Vektorraums F2t. Es gilt ΣU={(γ0, γ1)∈W2(F2t)|γ0∈F∗ 2t, γ1∈F2t, γ1/γ2 0∈U}. Beweis. Wegen ΣU=T∗·ρ(U) haben die Elemente von ΣUdie Form (α, 0) ·(1, u) = (α, uα2) mit u∈Uund α∈F∗ 2t. Im Folgenden betrachten wir den F2-Vektorraum F2tzusammen mit der Spurform B: (x, y)7→ TrF2(xy). Lemma 3.1.4 Sei Uein echter Untervektorraum des F2-Vektorraums F2tmit F2⊆U und sei σ= dim(U). Sei weiter f¨ ur alle γ∈Sdie L¨ osungsanzahl nγ= #{(A, B)∈ΣU×ΣU|A+B=γ} definiert. Die Zahl nγist genau dann nur vom Partitionsteil P∈ AΣUmit γ∈P abh¨ angig, wenn einer der folgenden beiden F¨ alle eintritt: (i) Uist vom Typ I. In diesem Fall gilt nγ=         2σ(2t−1) falls γ= 0, 2σ(2σ−1) falls γ∈2S\ {0}, 2σ(2σ−2) falls γ∈ΣU, 22σfalls γ∈¯ ΣU. (ii) Uist vom Typ II. In diesem Fall gilt nγ=         2σ(2t−1) falls γ= 0, 2σ(2σ−1) falls γ∈2S\ {0}, 2σ(2σ+ 2t−σ−3) falls γ∈ΣU, 2σ(2σ−1) falls γ∈¯ ΣU. Mit der Vorarbeit von Lemma 3.1.1 kann der Beweis nun ¨ ahnlich wie in [59, Lemma VI.1] gef¨ uhrt werden. Beweis. Wir schreiben γals den gestutzten Witt-Vektor (γ0, γ1) und A= (α, a0), B= (β, b0). Mit der Arithmetik der gestutzten Witt-Vektoren ¨ uber einem Grundk¨ orper der Charakteristik 2 ist die Anzahl der L¨ osungen des Gleichungssystems α+β=γ0a0+b0+αβ =γ1 48 3.1. Verallgemeinerte Teichm¨ uller-Codes mit (α, a0),(β, b0)∈ΣUzu bestimmen. Mit der Substitution a0=α2aund b0=β2bist dies ¨ aquivalent zu α+β=γ0(3.1) α2a+β2b+αβ =γ1(3.2) mit α, β ∈F∗ 2tund a, b ∈U. Im Fall γ0= 0 (d.h. γ∈2S) k¨ onnen wir weiter umformen zu α=βund α2(a+b+ 1) = γ1. F¨ ur γ1= 0 (d.h. γ= 0) muss wegen α6= 0 die Gleichheit a+b+ 1 = 0 gelten. D.h. αkann beliebig in F∗ 2tund abeliebig in Ugew¨ ahlt werden, und β=αund b= 1 + a sind dann eindeutig festgelegt. Wegen 1 ∈Uist b∈U. F¨ ur γ= 0 ergeben sich also (#F∗ 2t)·#U= (2t−1) ·2σL¨ osungen. Ist γ16= 0 (d.h. γ∈2S\ {0}), so durchl¨ auft γ1/α2 mit αganz F∗ 2t, d.h. f¨ ur genau #U−1 Werte von αist γ1/α2∈U. F¨ ur diese αkann nun a∈Ubeliebig gew¨ ahlt werden, und b=γ1/α2+a+ 1 ∈Uist dann festgelegt. Folglich gibt es f¨ ur γ∈2S\ {0}genau (#U−1)#U= 2σ(2σ−1) L¨ osungen. Sei nun also γ06= 0 (d.h. γ∈S∗). Gleichung (3.1) ist ¨ aquivalent zu β=γ0+α, und die Bedingung α, β 6= 0 ist ¨ aquivalent zu α∈F2t\ {0, γ0}. Einsetzen in Gleichung (3.2) liefert α2(a+b+ 1) + αγ0+γ2 0b=γ1. Die Substitution α0=α/γ0und u=a+b+ 1 liefert u(α0)2+α0=γ1/γ2 0+b, (3.3) und die Bedingung α∈F2t\ {0, γ0}¨ ubersetzt sich in α0∈F2t\F2. Folglich ist nγdie Anzahl der L¨ osungen (α0, u, b)∈(F2t\F2)×U×Uder Gleichung (3.3). Wir unterscheiden zwei F¨ alle: Ist u= 0, so hat die Gleichung (3.3) #U−2 L¨ osungen falls γ∈ΣU(denn hier ist nach Lemma 3.1.3 γ1/γ2 0∈Uund demnach m¨ ussen die F¨ alle α0=γ1/γ2 0+b∈ {0,1} ausgeschlossen werden) und #UL¨ osungen falls γ∈¯ ΣU. Sei also u6= 0. Zun¨ achst ¨ uberlegen wir uns die Anzahl der ”verbotenen” L¨ osungen mit α0∈F2. Mit (α0)2=α0vereinfacht sich Gleichung (3.3) zu (u+ 1)α0−b=γ1/γ2 0. Die linke Seite liegt in U, und die rechte Seite liegt nach Lemma 3.1.3 genau dann in U, wenn γ∈ΣUist. D.h. f¨ ur γ∈¯ ΣUgibt es keine verbotene L¨ osung. F¨ ur γ∈ΣUgibt es die verbotenen L¨ osungen α0= 0, u∈U\ {0},b=γ1/γ2 0und α0= 1, u∈U\ {0}, b=u+1+γ1/γ2 0, insgesamt also 2(#U−1) St¨ uck. Wir multiplizieren nun Gleichung (3.3) mit uund gelangen zu (uα0)2+uα0=u(γ1/γ2 0+b). (3.4) 49 3. Konstruktionen (b) F¨ ur s6= (k−1)rhat der Uq,k,s genau zwei von Null verschiedene homogene Gewichte w1< w2. Bezeichnet man zwei Codew¨ orter cund c0mit whom(c−c0) = w1als benachbart, so entsteht ein Graph Gauf der Knotenmenge Uq,k,s. Dieser Graph ist stark regul¨ ar mit den Parametern (N, K, λ, µ) = q2k,2sq(qk−1), qk+ 2sq(2sq−3),2sq(2sq−1). Beweis. Der homogene Gewichtsz¨ ahler und die Parameter von Uq,k,s ergeben sich mit Fakt 2.3.1 wieder aus dem Spektrum von Uq,k,s in Satz 3.1.8(b). Wir sehen, dass Uq,k,s fett und projektiv ist (d.h. die zugeh¨ orige Multimenge Uq,k,s ist eine Menge) und nur zwei von Null verschiedene homogene Gewichte hat. Nach [16, Th. 5.5] ist Gstark regul¨ ar. Die Parameter von Gwerden mit den dort angegebenen Formeln berechnet. Bemerkung 3.1.13 (a) Die Codes Uq,k,s ¨ uberschneiden sich im Fall s≥(k−2)rmit der Konstruktion in [101] (der Spezialfall k= 3 findet sich bereits in [16, Prop. 6.6]), in der dortigen Notation m¨ ussen daf¨ ur qund sZweierpotenzen sein. Vermutlich k¨ onnen die partiellen Differenzenmengen in [74] benutzt werden, um eine Klasse von Codes mit zwei Schnittzahlen anzugeben, welche die Codes Uq,k,s sowie die Codes aus [101] als Spezialfall enth¨ alt. Da die homogene Minimaldistanz der Codes Uq,k,s jedoch nicht besonders gut ist, soll dieser Frage hier nicht weiter nachgegangen werden. (b) F¨ ur herk¨ ommliche lineare Codes wurde der Zusammenhang zwischen Codes mit nur zwei verschiedenen Gewichten (engl.: two-weight codes) und stark regul¨ aren Graphen erstmals in [29] beobachtet, siehe auch [19]. In [16, 58] wurde diese Theorie auf two-weight Codes ¨ uber endlichen Frobenius-Ringen ausgeweitet, weitere Ergebnisse hierzu finden sich in [18]. Zur allgemeinen Theorie stark regul¨ arer Graphen siehe z.B. [43, Sec. 10]. (c) Die Parameter der stark regul¨ aren Graphen Gaus Satz 3.1.12 sind nicht neu. Jedes orthogonale Array OA(qk,2sq) erzeugt einen stark regul¨ aren Graphen mit denselben Parametern [43, Sec. 10.4]. 3.1.4. Beispiele Im Folgenden diskutieren wir einige konkrete F¨ alle der Codes Tq,k,s. F¨ ur Isomorphietests wurde der Algorithmus aus [39] verwendet, alle weiteren Berechnungen wurden im Computeralgebrasystem Magma [10] realisiert. Beispiel 3.1.14 (Heptacode) Der eindeutige Code T2,3,0hat die Parameter [7,(3,3),6]Z4 und den symmetrisierten Gewichtsz¨ ahler X7 2+ 42X4 0X1X2 2+ 7X4 1X3 2+ 14X4 0X3 1. 56 3.1. Verallgemeinerte Teichm¨ uller-Codes T2,3,0ist bis auf Isomorphie der einzige (7,26,6)Z4-Code [39]. Er ist isomorph zur Verk¨ urzung des Z4-linearen Oktacodes (Beispiel 2.2.8) an beliebiger Position. Das Gray-Bild ist ein nichtlinearer Code mit den BTL-Parametern (14,26,6)2und dem Hamming-Gewichtsz¨ ahler 1 + 42X6+ 7X8+ 14X10. Damit ist T2,3,0der k¨ urzeste Z4-lineare BTL-Code. Es ist auch kein Z4-linearer BTKLCode kleinerer Gr¨ oße oder kleinerer Minimaldistanz bekannt. Aus diesem Grund dr¨ angt es sich auf, diesen bemerkenswerten Code mit dem noch nicht vergebenen Namen Heptacode zu adeln. Beispiel 3.1.15 Es gibt 4 passende Unterr¨ aume Uzur Erzeugung eines Codes T2,4,1. Die resultierenden Codes sind alle isomorph, das Symbol T2,4,1legt also einen bis auf Isomorphie eindeutigen Z4-linearen Code fest. Eine m¨ ogliche Generatormatrix ist     100012131231231001113022033201 010011010201130213320112213312 001011001222111123131331100220 000122100110022021111111111112    . Dieser Code ist fett und hat die Parameter [30,(4,4),28]Z4und den symmetrisierten Gewichtsz¨ ahler X30 2+ 180X16 0X6 1X8 2+ 15X16 1X14 2+ 60X16 0X10 1X4 2. Das Gray-Bild hat die Parameter (60,28,28)2und ist damit ein BTL-Code [12, Th. 3]. Der Hamming-Gewichtsz¨ ahler ist 1 + 180X28 + 15X32 + 60X36. Der Code aus [3, Ex. 4] ist zu T2,4,1isomorph. Doppeltes Verk¨ urzen des Z4-linearen Kerdock-Codes K5+1 in zwei beliebigen Koordinaten liefert einen nicht zu T2,4,1isomorphen Code mit denselben Parametern und demselben symmetrisierten Gewichtsz¨ ahler. Eine m¨ ogliche Generatormatrix ist     100011231020211132330310220131 010010202012020123313111131312 001001101221131223111331122000 000100111100112211201112211112    . Im Jahr 2009 wurde von Johannes Zwanzger durch ein heuristisches Suchverfahren ein weiterer [30,(4,4),28]Z4-Code mit der Generatormatrix     100011121101101110112221121002 010021310112322011010111102121 001000021313311222001131311322 000113233032313212121211222213     57 3. Konstruktionen gefunden. Im Gegensatz zu den vorherigen beiden Codes hat dieser Code zwei identische Spalten.34 Der symmetrisierte Gewichtsz¨ ahler ist X30 2+ 182X16 0X6 1X8 2+ 15X16 1X14 2+ 56X16 0X10 1X4 2+ 2X16 0X14 1, und das Gray-Bild hat den Hamming-Gewichtsz¨ ahler 1 + 182X28 + 15X32 + 56X36 + 2X44. Mit den eben genannten Gewichtsz¨ ahlern existiert schließlich noch ein vierter Isomorphietyp: K¨ urzlich wurde in [72, Ex. 3] ein nicht freier [30,(5,3),28]Z4-Code durch Vergr¨ oßerung des Simplex-Codes Sim(3,Z4) um zwei nicht freie Zeilen konstruiert. Der Code hat zwei Torsionsspalten, ist also nicht fett. Eine m¨ ogliche Generatormatrix ist       100110002311310320133122231102 010111310121001123112210110202 001000111111120011111111222220 000202022200222022000022200020 000022202220020002220020002202       . Beispiel 3.1.16 Zur Erzeugung eines Codes T2,5,2gibt es 20 M¨ oglichkeiten f¨ ur den Unterraum U. Je 5 dieser Unterr¨ aume liefern zueinander isomorphe Codes, d.h. es gibt 4 Isomorphietypen von Codes T2,5,2. Jeder solche Code ist fett mit den Parametern [124,(5,5),120]Z4und dem symmetrisierten Gewichtsz¨ ahler X124 2+ 744X64 0X28 1X32 2+ 31X64 1X60 2+ 248X64 0X36 1X24 2. Das Gray-Bild hat die Parameter (248,210,120)2und den Hamming-Gewichtsz¨ ahler 1 + 744X120 + 31X128 + 248X136. Die Codes T2,5,2sind BTKL: Die Internetseite [46] zeigt f¨ ur die gr¨ oßtm¨ ogliche Minimaldistanz eines [248,10]F2-Codes das Intervall 119–120, die untere Schranke stammt aus [37]. Die obere Schranke erh¨ alt man so: G¨ abe es einen linearen [248,10,121]F2-Code, so durch das Bilden des Residuums in einem Codewort von minimalem Gewicht auch einen [127,9,61]F2-Code,35 durch erneutes Bilden des Residuums in einem Codewort von minimalem Gewicht einen [66,8,31]F2-Code und durch Anh¨ angen eines Parit¨ atsbits schließlich einen [67,8,32]F2-Code im Widerspruch zu [34, Th. 2.3]. Beispiel 3.1.17 Zur Erzeugung eines Codes T2,6,1gibt es 16 Wahlm¨ oglichkeiten f¨ ur den Unterraum U. Bez¨ uglich der Isomorphieklassen der erzeugten Codes zerfallen diese 16 34Die angegebene Matrix wurde unver¨ andert von der Programmausgabe von Johannes Zwanzger ¨ ubernommen. Dort sind die achte und die letzte Spalte identisch. 35Sollte die Minimaldistanz des Residuums >61 sein, so kann dieser Code durch Nullsetzen einer oder mehrerer im Tr¨ ager eines Codeworts von minimalem Gewicht enthaltenen Position zu einem [127,9,61]F2-Code modifiziert werden. 58 3.1. Verallgemeinerte Teichm¨ uller-Codes M¨ oglichkeiten in die Partition (6,6,3,1). Es gibt also vier Isomorphietypen von Codes T2,6,1. Eine der beiden zu einem Partitionseintrag 6 geh¨ orenden Isomorphieklassen enth¨ alt auch den Code aus [3, Ex. 4]. Jeder Code T2,6,1ist fett und hat die Parameter [126,(6,6),120]Z4und den symmetrisierten Gewichtsz¨ ahler X126 2+ 2520X64 0X28 1X34 2+ 63X64 1X62 2+ 1512X64 0X36 1X26 2. Die Gray-Bilder haben die Parameter (252,212,120)2und den Hamming-Gewichtsz¨ ahler 1 + 2520X120 + 63X128 + 1512X136. Die Internetseite [46] zeigt f¨ ur die gr¨ oßtm¨ ogliche Minimaldistanz eines [252,12]F2Codes das Intervall 118–120. Damit sind die Codes T2,6,1BTKL. Die obere Schranke erh¨ alt man durch die Betrachtung des Residuums in einem Codewort von minimalem Gewicht und der oberen Schranke 60 an die Minimaldistanz eines [131,11]F2-Codes aus [77]. Ein weiterer, nicht in den 4 Isomorphieklassen von T2,6,1enthaltener Code mit demselben symmetrisierten Gewichtsz¨ ahler ist der doppelt verk¨ urzte Kerdock-Code K7+1. Beispiel 3.1.18 Zur Erzeugung eines Codes T2,6,3gibt es 80 Wahlm¨ oglichkeiten f¨ ur den Unterraum U. Bez¨ uglich der Isomorphieklassen der erzeugten Codes zerfallen diese 80 M¨ oglichkeiten in die Partition (61321), es gibt also 14 Isomorphietypen von Codes T2,6,3. Jeder Code T2,6,3ist fett und hat die Parameter [504,(6,6),496]Z4und den symmetrisierten Gewichtsz¨ ahler X504 2+ 3024X256 0X120 1X128 2+ 63X256 1X248 2+ 1008X256 0X136 1X112 2. Die Gray-Bilder haben die Parameter (1008,212,496)2und den Hamming-Gewichtsz¨ ahler 1 + 3024X496 + 63X512 + 1008X528. Dieser Code ist leider zu lang, um ihn direkt mit den Tabellen f¨ ur lineare Codes vergleichen zu k¨ onnen. Beispiel 3.1.19 Wegen s= 0 ist der Unterraum U=F4und damit der Code T4,3,0 eindeutig. Er hat die Parameter [21,(3,3),60]GR(4,2) und den symmetrisierten Gewichtsz¨ ahler X21 2+ 2520X16 0X3 1X2 2+ 63X16 1X5 2+ 1512X16 0X5 1. Das Gray-Bild hat die Parameter (84,46,60)4und den Hamming-Gewichtsz¨ ahler 1 + 2520X60 + 63X64 + 1512X68. Die Internetseite [46] zeigt f¨ ur die gr¨ oßtm¨ ogliche Minimaldistanz eines [84,6]F4-Codes das Intervall 59–60. Damit ist T4,3,0ein BTKL-Code. Er wurde erstmals in [55] angegeben. Dort wurde der Code als das Erzeugnis eines Hyperovals in PHG(GR(4,2)3) realisiert. F¨ ur die Erzeugung von T4,3,0wird ein zweidimensionaler F2-Vektorraum Uvon F26 benutzt. Die gleiche Situation liegt bei dem Code T2,6,1aus Beispiel 3.1.17 vor. Hierdurch erkl¨ art sich die ¨ Ahnlichkeit zwischen den Gewichtsz¨ ahlern der beiden Codes. 59 3. Konstruktionen 3.2. Geometrisches Dualisieren Im Abschnitt 2.3 haben wir gesehen, dass jede Hjelmslev-Geometrie PHG(Rk) zu ihrer dualen Geometrie isomorph ist. Ist also eine Multimenge kvon Punkten in PHG(Rk) vorgegeben, so k¨ onnen wir anhand des k-Typs bestimmte Hyperebenen der Geometrie (evtl. mehrfach) ausw¨ ahlen und wieder als eine Multimenge von Punkten in PHG(Rk) interpretieren. Auf diese Weise erhalten wir die dualisierte Punktmenge. Die Auswahl der Hyperebenen wird durch eine Dualisierungsfunktion τrealisiert. Sei dazu Ω = {ak(H)|H∈ H} ⊂ N3die Menge aller k-Typen. Eine Dualisierungsfunktion τ ist dann eine Abbildung Ω →N, die einer Hyperebene vom Typ ωdie Multiplizit¨ at τ(ω) zuweist. Damit definiert τeine Multimenge kτvon Hyperebenen in der dualen Geometrie, die wir als die dualisierte Multimenge von Punkten in der Ausgangsgeometrie PHG(Rk) auffassen. Wir nennen eine Multimenge kvon Punkten selbstdual, wenn eine Dualisierungsfunktion τexistiert mit kτ∼ =k,36 und formal selbstdual, wenn eine Dualisierungsfunktion τ existiert mit spec(k) = spec(kτ). Selbstduale Punktmengen sind auch formal selbstdual. F¨ ur lineare Dualisierungsfunktionen, d.h. τ((ω0, ω1, ω2)) = α+βω1+γω2mit α, β, γ ∈ Q,37 h¨ angt das Spektrum der dualisierten Punktmenge nur vom urspr¨ unglichen Spektrum und der Verteilung der Punkte auf die Punktklassen ab: Fakt 3.2.1 ([70, Th. 2]) Der kτ-Typ einer Hyperebene x∈ P der dualen Geometrie ist akτ(x) = (b0, b1, b2) mit b0=αq2k−2+β·#k·q2k−4(q−1) + γ·#k·q2k−4 −βq2k−4(q−1) + γq2k−4k([x]), b1=αqk−2(qk−1−1) + β·#k·qk−3(qk−2−1)(q−1) + γ·#k·qk−3(qk−2−1) +βqk−3(qk−2qk−1+qk−2−1) + γqk−3(qk−1−qk−2+ 1)k([x]) −(γ−β)q2k−4k(x), b2=αqk−2·qk−1−1 q−1+β·#k·qk−3(qk−2−1) + γ·#k·qk−3·qk−2−1 q−1 +βqk−3(qk−1−qk−2+ 1) + γqk−3(qk−2−1)k([x]) + (γ−β)q2k−4k(x). Aus Sicht der Codierungstheorie w¨ ahlt die Dualisierungskonstruktion f¨ ur jedes symmetrisierte Gewicht ω= (ω0, ω1, ω2) mit ω06= 0 eine Menge Xvon projektiven Vertretern 36Gleichheit kann an dieser Stelle nicht gefordert werden, denn die Identifizierung der dualen Geometrie mit der Ausgangsgeometrie ist nur bis auf einen Isomorphismus festgelegt. 37Zun¨ achst nennt man eine Dualisierungsfunktion der Form τ((ω0, ω1, ω2)) = α0ω0+β0ω1+γ0ω2linear. Mit #k=ω0+ω1+ω2kann τdann aber durch τ((ω0, ω1, ω2)) = (α0#k)+(β0−α0)ω1+ (γ0−α0)ω2 auf die angegebene Form gebracht werden. 60 3.2. Geometrisches Dualisieren der Informationsw¨ orter der Codew¨ orter in cde(k) vom symmetrisierten Gewicht ωaus und setzt je τ(ω) Kopien von jedem Vektor in Xals Spalten in eine Generatormatrix G∗. Der Zeilenraum von G∗ist der Code cde(kτ). Diese Dualisierungskonstruktion soll nun auf die Codes Tq,k,s und die Z4-linearen Kerdock-Codes Kk+1 angewendet werden. 3.2.1. Dualisierte verallgemeinerte Teichm¨ uller-Codes In diesem Abschnitt seien ganze Zahlen r≥1, k≥2, q= 2rund s∈({0,2,4,...,(k−1)r}falls k ungerade, {r, r + 2, r + 4,...,(k−1)r}falls k gerade vorgegeben. Das Spektrum der Punktmenge Tq,k,s ist laut Satz 3.1.8 in Tabelle 3.1.1 angegeben. Wir bezeichnen die beiden auftretenden Typen wie dort mit H−und H+. Es sei nun eine Dualisierungsfunktion τdefiniert durch τ(H−) = 1 und τ(H+) = 0, d.h. τ w¨ ahlt genau die Hyperebenen vom Typ H−aus. Sei T∗ q,k,s =Tτ q,k,s. Im Fall s= (k−1)r ist T∗ q,k,(k−1)rdie leere Menge. F¨ ur s6= (k−1)rspannt T∗ q,k,s die volle Punktmenge von PHG(Rk) auf (das werden wir in Satz 3.2.3(a) zeigen), so dass wir an dieser Stelle bereits T∗ q,k,s = cde(T∗ q,k,s) definieren. Lemma 3.2.2 In jeder Hyperebenenklasse von PHG(Rk)gibt es 1 2qk−1−2s/2qk−1 2 Hyperebenen vom Typ H−und 1 2qk−1+ 2s/2qk−1 2Hyperebenen vom Typ H+. Durch einen Punkt in Tq,k,s gehen n−(Tq,k,s) = 1 2 qk−2qk−1−1 q−1−2s/2qk−1 2qk−2−1 q−1−qk−1 2 2s/2qk−2! =1 2 qk−1 2 2s/2−1!2s/2qk−1 2qk−2−1 q−1−qk−2 Hyperebenen vom Typ H−und n+(Tq,k,s) = 1 2 qk−2qk−1−1 q−1+ 2s/2qk−1 2qk−2−1 q−1+qk−1 2 2s/2qk−2! =1 2 qk−1 2 2s/2+ 1!2s/2qk−1 2qk−2−1 q−1+qk−2 Hyperebenen vom Typ H+. 61 3. Konstruktionen Durch einen Punkt außerhalb von Tq,k,s gehen n−({Tq,k,s) = 1 2qk−2qk−1−1 q−1−2s/2qk−1 2qk−2−1 q−1 Hyperebenen vom Typ H−und n+({Tq,k,s) = 1 2qk−2qk−1−1 q−1+ 2s/2qk−1 2qk−2−1 q−1 Hyperebenen vom Typ H+. Beweis. Laut Satz 3.1.8(a) gibt es 1 2 qk−1 q−1qk−1−2s/2qk−1 2Hyperebenen vom Typ H−. Nach Lemma 3.1.7 operiert Aut(Tq,k,s) transitiv auf der Menge der Hyperebenenklassen. Weil es insgesamt qk−1 q−1Hyperebenenklassen gibt, folgen daraus die behaupteten Anzahlen der Hyperebenen vom Typ H−bzw. H+innerhalb einer Hyperebenenklasse. Die Anzahlen n−(Tq,k,s), n+(Tq,k,s), n−({Tq,k,s) und n+({Tq,k,s) lassen sich nun wie in [59, Sec. IV] durch doppeltes Abz¨ ahlen aus dem aus Satz 3.1.8(a) bekannten Spektrum von Tq,k,s berechnen. Satz 3.2.3 (a) Die Punktmenge T∗ q,k,s enth¨ alt 1 2 qk−1 q−1qk−1−2s/2qk−1 2Punkte. F¨ ur s6= (k−1)r spannt T∗ q,k,s die volle Punktmenge der Geometrie PHG(Rk)auf und hat nur zwei verschiedene Schnittzahlen mit den Hyperebenen. Das Spektrum von T∗ q,k,s ist in Tabelle 3.2.1 angegeben. (b) Der Code T∗ q,k,s hat die Parameter 1 2 qk−1 q−1qk−1−2s/2qk−1 2,(k, k), qk−2s/2qk+1 2−1R und den in Tabelle 3.2.2 angegebenen homogenen Gewichtsz¨ ahler. Beweis. Die Anzahl der Punkte in T∗ q,k,s ist die Anzahl der Hyperebenen vom Tq,k,sTyp H−aus 3.2.2. Nach Lemma 3.2.2 enth¨ alt T∗ q,k,s f¨ ur s6= (k−1)rPunkte aus jeder Punktklasse und spannt folglich die volle Geometrie PHG(Rk) auf. Aus der Anzahl der Punkte pro Punktklasse ergeben sich die ω0-Eintr¨ age in Tabelle 3.2.1. Die ω2-Eintr¨ age sind die Werte n−(Tq,k,s) und n−({Tq,k,s) aus Lemma 3.2.2. Mit ω0+ω1+ω2= #T∗ q,k,s folgen nun auch die ω1-Eintr¨ age. Die Anzahl-Eintr¨ age sind nichts anderes als die Gr¨ oße der Punktmenge Tq,k,s bzw. ihres Komplements. ¨ Uber Fakt 2.3.1 berechnet man nun den symmetrisierten Gewichtsz¨ ahler von T∗ q,k,s und daraus weiter den homogenen Gewichtsz¨ ahler und die Parameter. Bemerkung 3.2.4 Die Serie T∗ q,k,s verallgemeinert die Serie der dualisierten Teichm¨ ullerCodes T∗ q,k aus [91, 92], diese bilden den Spezialfall s= 0. 62 3.2. Geometrisches Dualisieren Tabelle 3.2.1.: Spektrum der dualisierten Punktmenge T∗ q,k,s Typ H∗ −#Hyperebenen 2sqk−1 q−1 ω0 1 2qk−1qk−1−2s/2qk−1 2 ω1 1 2qk−2 qk−1−1−2s/2qk−1 2+qk−1 2 2s/2! =1 2qk−2 qk−1 2 2s/2−1!2s/2qk−1 2+ 1 ω2 1 2 qk−2qk−1−1 q−1−2s/2qk−1 2qk−2−1 q−1−qk−1 2 2s/2qk−2! =1 2 qk−1 2 2s/2−1!2s/2qk−1 2qk−2−1 q−1−qk−2 Typ H∗ +#Hyperebenen (qk−1−2s)qk−1 q−1 ω0 1 2qk−1qk−1−2s/2qk−1 2 ω1 1 2qk−2qk−1−1−2s/2qk−1 2 ω2 1 2qk−2qk−1−1 q−1−2s/2qk−1 2qk−2−1 q−1 Tabelle 3.2.2.: Homogener Gewichtsz¨ ahler von T∗ q,k,s Typ #Codew¨ orter whom 0 1 0 H∗ +q(qk−1)(qk−1−2s)1 2qk−1qk−2s/2qk+1 2−1 2H∗qk−11 2qk−1qk−2s/2qk+1 2 H∗ −q(qk−1)2s1 2qk−1qk−2s/2qk+1 2−1 + qk−1 2 2s/2 63 3. Konstruktionen Tabelle 3.2.3.: Spektrum der selbstdualen Punktmenge Tq,k,(k−1)r−2 Typ #Hyperebenen ω0ω1ω2 H−1 4qk−1qk−1 q−1 1 4q2k−21 4q2k−3+1 2qk−21 4qk−1qk−2−1 q−1−1 2qk−2 H+3 4qk−1qk−1 q−1 1 4q2k−21 4q2k−3−1 2qk−21 4qk−1qk−2−1 q−1+1 2qk−2 Satz 3.2.5 Die Punktmenge Tq,k,s ist genau f¨ ur s∈ {(k−1)r−2,(k−1)r}formal selbstdual. Das Spektrum der formal selbstdualen Punktmenge Tq,k,(k−1)r−2ist in Tabelle 3.2.3 angegeben. Beweis. Im Fall s= (k−1)rist Tq,k,s die komplette Punktmenge von PHG(Rk), diese ist offensichtlich selbstdual. Sei also s < (k−1)rund Tq,k,s formal selbstdual. Weil es nach Satz 3.1.8(a) nur zwei verschiedene Tq,k,s-Typen gibt, gibt es f¨ ur die Dualisierungsfunktion nur die beiden M¨ oglichkeiten τ(H−)=0, τ(H+) = 1 und τ(H−)=1, τ(H+) = 0. Im ersten Fall erhalten wir aus #Tq,k,s = #Tτ q,k,s = #Hyperebenen vom Typ H+ und dem Spektrum in Satz 3.1.8(a) die Gleichung 2s−1 2qk−1−2s/2qk−1 2= 0 und weiter s= (k−1)r, Widerspruch. Im zweiten Fall erhalten wir genauso 2s+1 2qk−1−2s/2qk−1 2= 0 und weiter s= (k−1)r−2. Die Dualisierungsfunktion stimmt hier mit der in Satz 3.2.3(a) betrachteten ¨ uberein. Einsetzen in das in Satz 3.1.8(a) bzw. in Satz 3.2.3(a) angegebene Spektrum zeigt, dass Tq,k,(k−1)r−2wirklich dasselbe Spektrum hat wie T∗ q,k,(k−1)r−2und dieses durch das Spektrum in Tabelle 3.2.3 gegeben ist. Bemerkung 3.2.6 Eine Untersuchung mit dem Algorithmus aus [39] zeigt, dass in den formal selbstdualen F¨ allen T2,3,0(bis auf Isomorphie 1 Punktmenge, vgl. Beispiel 3.1.14), T2,4,1(1 Punktmenge, vgl. Beispiel 3.1.15), T2,5,2(4 Punktmengen, vgl. Beispiel 3.1.16) und T2,6,3(14 Punktmengen, vgl. Beispiel 3.1.18) jede Punktmenge zu ihrer dualisierten Punktmenge isomorph ist. Damit liegt die Vermutung nahe, dass die Punktmengen Tq,k,(k−1)r−2sogar selbstdual sind. Beispiel 3.2.7 Der Code T∗ 2,5,0hat die Parameter [186,(5,5),184]Z4und den symmetrisierten Gewichtsz¨ ahler X186 2+ 930X96 0X44 1X46 2+ 31X96 1X90 2+ 62X96 0X60 1X30 2. 64 3.2. Geometrisches Dualisieren Das Gray-Bild ist ein (372,210,184)2-Code mit dem Hamming-Gewichtsz¨ ahler 1 + 930X184 + 31X192 + 62X216. Dieser Code ist BTL, denn g¨ abe es einen linearen [372,10,184]F2-Code, so ¨ uber das Residuum in einem Codewort von minimalem Gewicht auch einen [188,9,92]F2-Code. Ein solcher Code existiert nach [77] jedoch nicht. Der Code T∗ 2,5,0wurde als dualisierter Teichm¨ uller-Code bereits in [91, 92] ver¨ offentlicht. Beispiel 3.2.8 Wie von den Codes T2,6,1in Beispiel 3.1.17 gibt es auch von den Codes T∗ 2,6,1genau 4 Isomorphietypen. Sie haben die Parameter [756,(6,6),752]Z4und den symmetrisierten Gewichtsz¨ ahler X756 2+ 3780X384 0X184 1X188 2+ 63X384 1X372 2+ 252X384 0X216 1X156 2. Das Gray-Bild ist stets ein (1512,212,752)2-Code mit dem Hamming-Gewichtsz¨ ahler 1 + 3780X752 + 63X768 + 252X816. Dieser Code ist leider zu lang, um ihn direkt mit den Tabellen f¨ ur lineare Codes vergleichen zu k¨ onnen. Einen f¨ unften Isomorphietyp mit demselben symmetrisierten Gewichtsz¨ ahler erh¨ alt man durch Dualisieren einer doppelten Verk¨ urzung des Kerdock-Codes K7+1. Beispiel 3.2.9 Der Code T∗ 4,3,0hat die Parameter [126,(3,3),376]GR(4,2) und den symmetrisierten Gewichtsz¨ ahler X126 2+ 3780X96 0X22 1X8 2+ 63X96 1X30 2+ 252X96 0X30 1. Das Gray-Bild ist ein (504,46,376)4-Code mit dem Hamming-Gewichtsz¨ ahler 1 + 3780X376 + 63X384 + 252X408. Dieser Code ist BTKL: Das Residuum eines F4-linearen [504,6,376]F4-Codes in einem Codewort von minimalem Gewicht w¨ are ein [128,5,≥94]F4-Code. Der Internetseite [46] zufolge ist ein solcher Code nicht bekannt, f¨ ur die gr¨ oßtm¨ ogliche Minimaldistanz eines [128,5]F4-Codes verbleibt das Intervall 93–94. Die untere Schranke entsteht durch dreifaches Verk¨ urzen des [131,5,96]F4-Codes in [11, Th. 11]. Die obere Schranke erh¨ alt man so: G¨ abe es einen [128,5,95]F4-Code, so durch das Residuum in einem Codewort von minimalem Gewicht auch einen [33,4,23]F4-Code und durch Verk¨ urzen weiter einen [32,4,22]F4-Code im Widerspruch zu [47, Th. 3.3(vi)]. Als der von einem maximalen (126,8)-Arc in PHG(GR(4,2)3) erzeugte Code wurde T∗ 4,3,0bereits in [85, Sec. 5] ver¨ offentlicht. 65 3. Konstruktionen Teilcode Cbesteht genau aus den Codew¨ ortern mit einem Eintrag a= 0 im Informationsvektor. Dies ergibt die Typen S,pS und 0 in Tabelle 3.3.1. Sei also a6= 0. Das an den mit einem Punkt xassoziierten q−1 Positionen stehende Teilwort von cbezeichnen wir mit cx. Zur blockweisen Berechnung von wsym(c)¨ uberlegen wir uns die Formel wsym(cx) = ((q−1)wsym(y·κ(x)) falls x∈k, Pa∈R∗pwsym(y·κ(x) + a) falls x /∈k.(3.6) Wir unterscheiden nun 3 F¨ alle: (i) Der Vektor yist torsionsfrei: Sei Hdie Hyperebene y⊥und (ψ0, ψ1, ψ2) = ak(H) der k-Typ von H. Es ergeben sich die folgenden 6 F¨ alle f¨ ur das symmetrisierte Gewicht von cx; der Exponent gibt jeweils an f¨ ur wie viele Punkte xder entsprechende Fall auftritt: x∈H x ∈[H]\H x ∈ P \ [H] x∈k(0,0, q −1)ψ2(0, q −1,0)ψ1(q−1,0,0)ψ0 x /∈k(0, q −1,0)#H−ψ2(0, q −2,1)#([H]\H)−ψ1(q−1,0,0)#(P\[H])−ψ0 Wir erkl¨ aren exemplarisch den Eintrag im Fall x /∈k,x∈[H]\H: Die Anzahl #([H]\H)−ψ1solcher Punkte xfolgt direkt aus der Definition des Typs. Wegen x /∈kbenutzen wir den zweiten Fall in Formel (3.6), und wegen x∈[H]\H gilt y·κ(x)∈R∗p. Damit ist y·κ(x) + agenau im Fall a=−y·κ(x) gleich 0, in den anderen (q−2) F¨ allen ergibt sich jeweils ein Element aus R∗p. Dies zeigt wsym(cx) = (0, q −2,1). Auf diese Art erhalten wir den Typ Hψin Tabelle 3.3.1. Die Anzahl der Codew¨ orter folgt dabei so: Je q(q−1) Informationsvektoren ydefinieren dieselbe Hyperebene H=y⊥, und f¨ ur die Wahl von a∈T\ {0}gibt es q−1 M¨ oglichkeiten. Damit repr¨ asentiert jede Hyperebene Hje q(q−1)2Codew¨ orter. (ii) Der Vektor yist ein Torsionsvektor, aber nicht der Nullvektor: Es existiert ein torsionsfreier Vektor zmit y=pz. Wir bezeichnen die Hyperebene z⊥mit H.¨ Ahnlich wie zuvor erhalten wir 4 F¨ alle f¨ ur wsym(cx): x∈[H]x∈ P \ [H] x∈k(0,0, q −1)ψ1+ψ2(0, q −1,0)ψ0 x /∈k(0, q −1,0)#[H]−(ψ1+ψ2)(0, q −2,1)#(P\[H])−ψ0 Dies liefert den Typ pHψin Tabelle 3.3.1. F¨ ur die Anzahl der Codew¨ orter ist hier zus¨ atzlich zu beachten, dass f¨ ur je qkverschiedene torsionsfreie Vektoren zdie Torsionsvektoren y=pz¨ ubereinstimmen. (iii) Der Vektor yist der Nullvektor: Hier sind nur die folgenden beiden F¨ alle zu unterscheiden: x∈k(0,0, q −1)#k x /∈k(0, q −1,0)#(P\k) 72 3.3. Vergr¨ oßerte und verl¨ angerte Simplex-Codes Dies liefert den Typ 00in Tabelle 3.3.1. Die Anzahl der Codew¨ orter ist gegeben durch die Anzahl q−1 der Wahlm¨ oglichkeiten f¨ ur a∈T\ {0}. Bemerkung 3.3.3 (a) Sei SimAug(k) ein [n, (k+ 1, k), d]R-Code. Weil die (q−1)-fache Wiederholung des Simplex-Codes Sim(k, R) als Teilcode vom Index qin Centhalten ist, gilt d≤d0= (q−1)dhom(Sim(k, R)). Folglich ist es wie f¨ ur die dualisierten Kerdock-Codes in Abschnitt 3.2.2 m¨ oglich, den Code SimAug(k) durch Konstruktion X (siehe Abschnitt 2.2.6) mit dem q-elementigen (n0, q, qn0)R-Wiederholungscode R(p, . . . , p) der L¨ ange n0=d(d0−d)/qeals Hilfscode zu verl¨ angern, um SimAug(k) zu einem (n+n0, q2k+1, d0)R-Code SimLen(k) (verl¨ angerter Simplex-Code,lengthened Simplex code) zu verbessern. F¨ uhrt man diese Konstruktion f¨ ur verschiedene Punktmengen kdurch, so haben die resultierenden Codes SimLen(k) alle dieselbe homogene Minimaldistanz d0, aber im Allgemeinen verschiedene L¨ angen n+n0. Je h¨ oher die homogene Minimaldistanz dvon SimAug(k) ist, desto k¨ urzer (und damit besser) ist der resultierende Code SimLen(k). (b) In [72] wurde f¨ ur den Z4-linearen Fall eine ¨ ahnliche Konstruktion angegeben. Die symmetrisierten Gewichte des Codes SimAug(k) k¨ onnen aus [72, Th. 1] abgelesen werden; allerdings fehlen im Vergleich zu Satz 3.3.2 die Anzahlen der jeweiligen Codew¨ orter bzw. Hyperebenen. Die Codes werden dort pauschal um eine Torsionsspalte verl¨ angert und nicht wie oben diskutiert in Abh¨ angigkeit von dum n0 Spalten. Der weiter unten in Beispiel 3.3.10 diskutierte Z4-lineare BTKL-Code ˆ S2,4 kann damit beispielsweise nicht erzeugt werden, denn dieser erfordert das Anh¨ angen von zwei Torsionsspalten. Lemma 3.3.4 Sei r, k ∈N,k≥3und q= 2r. Sei keine der Punktmengen Tq,k,s oder T∗ q,k,s mit s∈({0,2,4,...,(k−1)r−2}falls k ungerade, {r, r + 2, r + 4,...,(k−1)r−2}falls k gerade. Unter den M¨ oglichkeiten f¨ ur kwird die homogene Minimaldistanz von SimAug(k)f¨ ur k=     T∗ 2,k,0falls q= 2 und kungerade, T∗ 2,k,1falls q= 2 und kgerade, Tq,k,(k−3)rfalls q≥4 maximal. Beweis. Laut Satz 3.1.8(a) gibt es genau zwei verschiedene Tq,k,s-Typen, diese wurden in Tabelle 3.1.1 mit H−und H+bezeichnet. In Tabelle 3.3.1 liefert unter Hψder Typ H+das kleinere homogene Gewicht von SimAug(Tq,k,s), dieses ist w1(s) = qk−1(q−1)(qk−1) + q·2s/2(2s/2−qk−1 2). 73 3. Konstruktionen F¨ ur 0 ≤s≤(k−1)r−4 gilt w1(s+ 2) −w1(s) = 2s/2q(3 ·2s/2−qk−1 2)≤2s/2q3 4qk−1 2−qk−1 2<0, und damit ist w1als Funktion in sstreng monoton fallend. Die Typen H+und H−liefern unter pHψin Tabelle 3.3.1 dasselbe homogene Gewicht w2(s) = qk−1(q−1)(qk−1) −qk−1+ 2sq. Dies ist eine streng monoton steigende Funktion in s. Man ¨ uberpr¨ uft, dass f¨ ur s= (k−3)rdie beiden Gewichte w1(s) und w2(s) denselben Wert q2k−q2k−1−qk+qk−2liefern, und dass dieses Gewicht wirklich die homogene Minimaldistanz von SimAug(Tq,k,s) ist. Damit ist unter den Punktmengen Tq,k,s die homogene Minimaldistanz f¨ ur s= (k−3)rmaximal. Wir betrachten nun die Punktmengen T∗ q,k,s. Nach Satz 3.2.5 stimmt das Spektrum der Punktmenge T∗ q,k,(k−1)r−2mit dem Spektrum der bereits betrachteten Punktmenge Tq,k,(k−1)r−2¨ uberein, so dass wir im Folgenden s≤(k−1)r−4 voraussetzen d¨ urfen. In SimAug(T∗ q,k,s) liefert der Typ 00das homogene Gewicht 1 2(qk−1)(qk+ 2s/2qk+1 2). Mit s≤(k−1)r−4 k¨ onnen wir dieses Gewicht nach oben absch¨ atzen durch 5 8(q2k−qk). F¨ ur q≥4 ist diese Zahl kleiner als die oben ermittelte homogene Minimaldistanz von SimAug(Tq,k,(k−3)r). Es verbleibt also, die Punktmengen T∗ 2,k,s zu untersuchen. Laut Satz 3.2.3(a) gibt es genau zwei verschiedene T∗ 2,k,s-Typen, welche in Tabelle 3.2.1 mit H∗ −und H∗ +bezeichnet wurden. In Tabelle 3.3.1 liefert unter Hψder Typ H∗ +das kleinere homogene Gewicht von SimAug(T∗ 2,k,s), dieses ist w(s)=22k−1−2k−1−2s+k−1 2. Unter 2Hψliefern die beiden Typen H∗ −und H∗ +dasselbe homogene Gewicht. Dieses stimmt mit w(s)¨ uberein. Weiter erhalten wir unter 00das homogene Gewicht 22k−1− 2k−1+ (2k−1)2s+k−1 2, welches sicher gr¨ oßer als w(s) ist. Die homogene Minimaldistanz von SimAug(T∗ 2,k,s) ist also w(s) und wird f¨ ur den kleinsten zul¨ assigen Wert von smaximal, d.h. f¨ ur s= 0 falls kungerade und f¨ ur s= 1 falls kgerade. Ein Vergleich der resultierenden Minimaldistanz mit der Minimaldistanz von SimAug(T2,k,k−3) liefert dhom(SimAug(T∗ 2,k,s)) −dhom(SimAug(T2,k,k−3)) = w(s)−w1(k−3) = 2k−2−2s+k−1 2. Diese Differenz ist genau dann nicht negativ, wenn s≤k−3 ist. Damit ist alles gezeigt. Bemerkung 3.3.5 Der Beweis von Lemma 3.3.4 zeigt auch, dass unter den betrachteten Punktmengen kdie homogene Minimaldistanz von SimAug(k) außer in den beiden F¨ allen (q, k)∈ {(2,3),(2,4)}genau f¨ ur die angegebenen Punktmengen maximal wird. Bis auf Isomorphie stimmt dies auch in den beiden Sonderf¨ allen. Denn in Bemerkung 3.2.6 haben wir gesehen, dass die eindeutige Punktmenge T2,3,0zu T∗ 2,3,0und die eindeutige Punktmenge T2,4,1zu T∗ 2,4,1isomorph ist. 74 3.3. Vergr¨ oßerte und verl¨ angerte Simplex-Codes Tabelle 3.3.2.: Lee-Gewichtsz¨ ahler des Codes ˆ S2,k f¨ ur kungerade Typ #Codew¨ orter whom 0 1 0 H+,2H, S 22k+1 −3·2k+ 1 22k−1−2k−1 2S2k−1 22k−1 H−2k+1 −2 22k−1−2k−1+ 23k−3 2 001 22k−1−2k−1+ 23k−1 2 Tabelle 3.3.3.: Lee-Gewichtsz¨ ahler des Codes ˆ S2,k f¨ ur kgerade Typ #Codew¨ orter whom 0 1 0 H+,2H, S 22k+1 −5·2k+ 3 22k−1−2k−1 2S2k−1 22k−1 H−2k+2 −4 22k−1−2k−1+ 23k−4 2 001 22k−1−2k−1+ 23k 2 Die im Sinne von Lemma 3.3.4 bestm¨ ogliche Erweiterung der (q−1)-fachen Wiederholung des Simplex-Codes Sim(k, R) bezeichnen wir nun mit ˆ Sq,k: Es sei ˆ Sq,k =     SimLen(T∗ 2,k,0) falls q= 2 und kungerade, SimLen(T∗ 2,k,1) falls q= 2 und kgerade, SimLen(Tq,k,(k−3)r) falls q≥4 gerade. Satz 3.3.6 (a) Der Code SimLen(T∗ 2,k,s)hat die Parameter h22k−1−2k−1+ 2k−3+s 2,(k+ 1, k),22k−1−2k−1iZ4 . Tabelle 3.3.4 zeigt den symmetrisierten Gewichtsz¨ ahler. (b) F¨ ur ungerades k≥3hat ˆ S2,k die Parameter h22k−1−2k−1+ 2k−3 2,(k+ 1, k),22k−1−2k−1iZ4 . Tabelle 3.3.2 zeigt den Lee-Gewichtsz¨ ahler. (c) F¨ ur gerades k≥4hat ˆ S2,k die Parameter h22k−1−2k−1+ 2k−2 2,(k+ 1, k),22k−1−2k−1iZ4 . Tabelle 3.3.3 zeigt den Lee-Gewichtsz¨ ahler. 75 3. Konstruktionen Tabelle 3.3.4.: Symmetrisierter Gewichtsz¨ ahler des Codes SimLen(T∗ 2,k,s) Typ H+, S #Codew¨ orter (2k−1)(2k+1 −2s+1) ω022k−2 ω122k−3−2k−2 ω222k−3−2k−2+ 2k−3+s 2 whom 22k−1−2k−1 Typ H−#Codew¨ orter (2k−1)2s+1 ω022k−2 ω122k−3−2k−2+ 23k−5−s 2 ω222k−3−2k−2+ 2k−3+s 2−23k−5−s 2 whom 22k−1−2k−1+ 23k−3−s 2 Typ 2H±#Codew¨ orter 2k−1 ω00 ω122k−2−2k−2 ω222k−2−2k−2+ 2k−3+s 2 whom 22k−1−2k−1 Typ 00#Codew¨ orter 1 ω00 ω122k−2−2k−2−23k−1+s 2 ω222k−2−2k−2−23k−3+s 2+ 2k−3+s 2 whom 22k−1−2k−1+ 23k−1+s 2 Typ 2S#Codew¨ orter 2k−1 ω00 ω122k−2 ω222k−2−2k−1+ 2k−3+s 2 whom 22k−1 Typ 0 #Codew¨ orter 1 ω00 ω10 ω222k−1−2k−1+ 2k−3+s 2 whom 0 76 3.3. Vergr¨ oßerte und verl¨ angerte Simplex-Codes Tabelle 3.3.5.: Homogener Gewichtsz¨ ahler des Codes ˆ Sq,k f¨ ur q≥4 Typ #Codew¨ orter whom H+,2H, S 1 2q2k+1 +q2k−1 2q2k−1+3 2qk+1 q2k−q2k−1−qk+qk−1 −2qk−1 2qk−1−q+ 1 H−1 2q2k+1 −q2k+1 2q2k−1−1 2qk+1 +qk−1 2qk−1q2k−q2k−1−qk+ 3qk−1 2S qk−1q2k−q2k−1 00q−1q2k−q2k−2−qk+qk−1 0 1 0 Beweis. Aus Satz 3.2.3(a) erhalten wir das Spektrum von T∗ 2,k,s, und mit Satz 3.3.2 berechnen wir daraus den symmetrisierten Gewichtsz¨ ahler von SimAug(T∗ 2,k,s). Aus dem Beweis von Lemma 3.3.4 wissen wir, dass SimAug(T∗ 2,k,s) die minimale Lee-Distanz 22k−1−2k−1−2s+k−1 2hat. Beim ¨ Ubergang zu SimLen(T∗ 2,k,s) wird der Code durch Konstruktion X also um 2s+k−3 2Symbole verl¨ angert. Die im Simplex-Code liegenden Codew¨ orter werden dabei um Symbole 0, die restlichen Codew¨ orter um Symbole 2 verl¨ angert. Damit berechnet man nun weiter den in Tabelle 3.3.4 angegebenen symmetrisierten Gewichtsz¨ ahler sowie die Parameter von SimLen(T∗ 2,k,s). Durch Spezialisieren erh¨ alt man nun f¨ ur s= 0 die Aussagen in Teil (b), und f¨ ur s= 1 die Aussagen in Teil (c). Satz 3.3.7 Sei q≥4eine Zweierpotenz und k≥3. Der Code ˆ Sq,k hat die Parameter q2k−1−qk−1+qk−2−qk−3,(k+ 1, k), q2k−q2k−1−qk+qk−1R. Der symmetrisierte Gewichtsz¨ ahler ist in Tabelle 3.3.6 und der homogene Gewichtsz¨ ahler in Tabelle 3.3.5 angegeben. Beweis. Aus Satz 3.1.8(a) erhalten wir das Spektrum von Tq,k,(k−3)r, und mit Satz 3.3.2 berechnen wir daraus den symmetrisierten Gewichtsz¨ ahler von SimAug(Tq,k,(k−3)r). Aus dem Beweis von Lemma 3.3.4 wissen wir, dass SimAug(Tq,k,(k−3)r) die homogene Minimaldistanz q2k−q2k−1−qk+qk−2hat. Durch Konstruktion X werden beim ¨ Ubergang zu SimLen(Tq,k,(k−3)r) die in der (q−1)-fachen Wiederholung des Simplex-Codes liegenden Codew¨ orter also um qk−2−qk−3Symbole 0 verl¨ angert und die restlichen Codew¨ orter um qk−2−qk−3Symbole der H¨ ohe 1. Damit kann weiter der in Tabelle 3.3.6 angegebene symmetrisierte Gewichtsz¨ ahler von ˆ Sq,k abgeleitet werden. An diesem liest man schließlich die Parameter und den homogenen Gewichtsz¨ ahler ab. Bemerkung 3.3.8 (a) Die f¨ ur q≥4 gemachten Aussagen aus Satz 3.3.7 sind auch im Fall q= 2 (d.h. r= 1) f¨ ur die Codes SimLen(T2,k,k−3) richtig. Aufgrund von Bemerkung 3.2.6 sind f¨ ur k∈ {3,4}die beiden Codes SimLen(T2,k,k−3) und ˆ S2,k isomorph. F¨ ur k≥5 ist dies nach Lemma 3.3.4 nicht mehr der Fall, hier sind die Codes ˆ S2,k besser. (b) Die Codes ˆ Sq,k verallgemeinern die bereits in [90] ver¨ offentlichten Codes, diese bilden den Spezialfall k= 3. 77 3. Konstruktionen Tabelle 3.3.6.: Symmetrisierter Gewichtsz¨ ahler des Codes ˆ Sq,k f¨ ur q≥4 Typ H+, S #Cw. 1 2q2k+1 +q2k−1 2q2k−1+1 2qk+1 −qk−1 2qk−1 ω0q2k−1−q2k−2 ω1q2k−2−q2k−3−qk−1+qk−2 ω2q2k−3−qk−3 whom q2k−q2k−1−qk+qk−1 Typ H−#Cw. 1 2q2k+1 −q2k+1 2q2k−1−1 2qk+1 +qk−1 2qk−1 ω0q2k−1−q2k−2 ω1q2k−2−q2k−3−qk−1+ 3qk−2 ω2q2k−3−2qk−2−qk−3 whom q2k−q2k−1−qk+ 3qk−1 Typ 2H#Cw. qk+1 −qk−q+ 1 ω00 ω1q2k−1−q2k−2−qk−1+qk−2 ω2q2k−2−qk−3 whom q2k−q2k−1−qk+qk−1 Typ 00#Cw. q−1 ω00 ω1q2k−1−q2k−3−qk−1+qk−2 ω2q2k−3−qk−3 whom q2k−q2k−2−qk+qk−1 Typ 2S#Cw. qk−1 ω00 ω1q2k−1−q2k−2 ω2q2k−2−qk−1+qk−2−qk−3 whom q2k−q2k−1 Typ 0 #Cw. 1 ω00 ω10 ω2q2k−1−qk−1+qk−2−qk−3 whom 0 78 3.3. Vergr¨ oßerte und verl¨ angerte Simplex-Codes 3.3.1. Beispiele Beispiel 3.3.9 Der Code ˆ S2,3hat die Parameter [29,(4,3),28]Z4und den symmetrisierten Gewichtsz¨ ahler X29 2+ (98X16 0X6 1X7 2+ 7X14 1X15 2)+7X16 1X13 2+ 14X16 0X10 1X3 2+X22 1X7 2. Eine m¨ ogliche Generatormatrix ist     1111 0220 0220 2002 1111 1111 1111 0 2020 1111 2020 1111 0202 3113 3131 0 2200 2200 1111 3311 3311 0022 3113 0 2220 2220 2220 2220 2220 2220 2220 2    . Das Gray-Bild hat die Parameter (58,27,28)2und den Hamming-Gewichtsz¨ ahler 1 + 105X28 + 7X32 + 14X36 +X44. Dieser Code ist BTL [125, Th. 3.7]. Der Code ˆ S2,3wurde zuerst 2009 von Johannes Zwanzger gefunden (siehe auch [132]) und in [90] computerfrei beschrieben. Beispiel 3.3.10 Der Code ˆ S2,4hat die Parameter [122,(5,4),120]Z4und den symmetrisierten Gewichtsz¨ ahler X122 2+ (420X64 0X28 1X30 2+ 15X60 1X62 2) + 15X64 1X58 2+ 60X64 0X36 1X22 2+X92 1X30 2. Das Gray-Bild hat die Parameter (244,29,120)2und den Hamming-Gewichtsz¨ ahler 1 + 435X120 + 15X128 + 60X136 +X184. Die Internetseite [46] zeigt f¨ ur die gr¨ oßtm¨ ogliche Minimaldistanz eines [244,9]F2-Codes das Intervall 119–120. Damit ist der Code ˆ S2,4BTKL. Die obere Schranke 120 erh¨ alt man dabei so: F¨ ur einen F2-linearen Code der Dimension 9 und der Minimaldistanz 121 gilt aufgrund der Griesmer-Schranke n≥P8 i=0d121/2ie= 245. Vier weitere Isomorphieklassen von Z4-lineare Codes mit denselben Parametern wie ˆ S2,4wurden bereits in [91, 92] ver¨ offentlicht. Sie entstehen als zweifaches Residuum des dualisierten Kerdock-Codes ˆ K∗ 5+1. Beispiel 3.3.11 Der Code ˆ S2,5hat die Parameter [498,(6,5),496]Z4und den symmetrisierten Gewichtsz¨ ahler X498 2+ (1922X256 0X120 1X122 2+ 31X248 1X250 2) + 31X256 1X242 2+ 62X256 0X152 1X90 2+X312 1X186 2. Das Gray-Bild hat die Parameter (996,211,496)2und den Hamming-Gewichtsz¨ ahler 1 + 1953X496 + 31X512 + 62X560 +X624. 79 3. Konstruktionen Dieser Code ist leider zu lang, um ihn direkt mit den Tabellen f¨ ur lineare Codes vergleichen zu k¨ onnen. Die Parameter sehen aber sehr vielversprechend aus: Wenn ein linearer [996,11,496]F2-Code existiert, so ¨ uber das Residuum in einem Codewort von minimalem Gewicht auch ein [500,10,248]F2-Code und durch nochmaliges Bilden des Residuums in einem Codewort von minimalem Gewicht auch ein [252,9,124]F2-Code. Ein solcher Code w¨ are laut [46] distanzoptimal. Beispiel 3.3.12 Der Code ˆ S4,3hat die Parameter [1011,(4,3),3024]GR(16,4) und den symmetrisierten Gewichtsz¨ ahler X1011 2+ (11592X768 0X180 1X63 2+ 189X756 1X255 2) + 4536X768 0X188 1X55 2+ 63X768 1X243 2+ 3X948 1X63 2. Das Gray-Bild hat die Parameter (4044,47,3024)4und den Hamming-Gewichtsz¨ ahler 1 + 11781X3024 + 4536X3056 + 63X3072 + 3X3792. Auch dieser Code ist leider f¨ ur einen Tabellenvergleich zu lang. Er wurde bereits in [90] ver¨ offentlicht. 80 4. Ausblick In dieser Arbeit wurden vier neue Serien von linearen Codes ¨ uber Galois-Ringen der Charakteristik 4 konstruiert. Die Qualit¨ at der Codes insbesondere im Z4-linearen Fall wird durch Tabelle 1.4.1 belegt. In allen F¨ allen, wo ein Tabellenvergleich m¨ oglich ist, sind die Codes entweder BTL oder BTKL. Diese Resultate werfen jedoch auch eine Reihe von Fragen auf, die Gegenstand zuk¨ unftiger Untersuchungen sein sollten und auf die hier zum Abschluss noch kurz eingegangen wird. (a) Es ist kein einziger BTLoder BTKL-Code als Gray-Bild eines ringlinearen Codes in ungerader Charakteristik bekannt. Eine denkbare Erkl¨ arung hierf¨ ur ist, dass die meisten bekannten BTLund BTKL-Codes in Charakteristik 4 auf die eine oder andere Weise von Teichm¨ uller-Mengen herr¨ uhren, deren Eigenschaften in gerader und ungerader Charakteristik sehr unterschiedlich sind. Andererseits gibt es mit den Z4-linearen Preparata-Codes unendlich viele BTL-Codes in Charakteristik 4, so dass es wenig wahrscheinlich erscheint, dass beispielsweise ¨ uber Z9kein einziger BTL-Code existiert. (b) Die nach Heptaund Oktacode n¨ achstgr¨ oßeren41 bekannten Z4-linearen BTLCodes haben die Parameter [29,7,28]Z4und [30,8,28]Z4. Im ersten Fall ist ein einziger Isomorphietyp bekannt (Beispiel 3.3.9), im zweiten Fall vier Isomorphietypen (Beispiel 3.1.15). Eventuell ist es m¨ oglich, alle Z4-linearen Codes mit diesen Parametern komplett zu klassifizieren. (c) Um zu entscheiden, ob die neuen Serien als R-lineare Codes optimal sind, w¨ are eine schlagkr¨ aftige Optimalit¨ atstheorie f¨ ur lineare Codes ¨ uber Galois-Ringen der L¨ ange 2 oder zumindest f¨ ur Z4-lineare Codes w¨ unschenswert. Zwar stehen mit [17] einige obere Schranken zur Verf¨ ugung, die aber f¨ ur die wesentlich allgemeinere Klasse der linearen Codes ¨ uber endlichen Frobenius-Ringen entwickelt wurden und in unserer Situation nicht richtig greifen. Beispielsweise verfehlen s¨ amtliche Codes der neuen vier Serien knapp die Voraussetzung (q−1)n < d f¨ ur die verallgemeinerte Plotkin-Schranke [17, Th. 1]. Insbesondere w¨ are eine Verallgemeinerung der Griesmer-Schranke hilfreich. (d) In diesem Zusammenhang sollte auch systematisch eine Datenbank f¨ ur die besten bekannten oberen Schranken f¨ ur R-lineare Codes kleiner Parameter aufgebaut werden. Ein erster Schritt wurde hierzu von Thomas Feulner mit der Klassifikation in 41im Hinblick auf den zu erwartenden Rechenaufwand einer vollst¨ andigen Klassifikation 81 Literatur [14] A. E. Brouwer und L. M. G. M. Tolhuizen. “A sharpening of the Johnson bound for binary linear codes and the nonexistence of linear codes with Preparata parameters”. In: Designs, Codes and Cryptography 3 (1993), S. 95–98. [15] L. M. Butler. Subgroup Lattices and Symmetric Functions. Memoirs of the American Mathematical Society 539. American Mathematical Society, 1994. isbn: 0-8218-2600-X. [16] E. Byrne, M. Greferath und T. Honold. “Ring geometries, two-weight codes, and strongly regular graphs”. In: Designs, Codes and Cryptography 48.1 (2008), S. 1– 16. [17] E. Byrne, M. Greferath, A. Kohnert und V. Skachek. “New bounds for codes over finite Frobenius rings”. In: Designs, Codes and Cryptography 57.2 (2010), S. 169– 179. [18] E. Byrne, M. Kiermaier und A. Sneyd.“Properties of codes with two homogeneous weights”. In: Finite Fields and Their Applications 18.4 (2012), S. 711–727. [19] A. R. Calderbank und W. M. Kantor. “The geometry of two-weight codes”. In: The Bulletin of the London Mathematical Society 18.2 (1986), S. 97–122. [20] A. R. Calderbank und G. McGuire.“Construction of a (64,237,12) code via Galois rings”. In: Designs, Codes and Cryptography 10 (1997), S. 157–165. [21] A. R. Calderbank, G. McGuire, P. V. Kumar und T. Helleseth. “Cyclic codes over Z4, locator polynomials, and Newton’s identities”. In: IEEE Transactions on Information Theory 42.1 (1996), S. 217–226. [22] A. R. Calderbank und N. J. A. Sloane. “Modular and p-adic cyclic codes”. In: Designs, Codes and Cryptography 6.1 (1995), S. 21–35. [23] C. Carlet. “Z2k-linear codes”. In: IEEE Transactions on Information Theory 44.4 (1998), S. 1543–1547. [24] R. Chapman und P. Sol´e. “Universal codes and unimodular lattices”. In: Journal de Th´eorie des Nombres de Bordeaux 8 (1996), S. 269–276. [25] B. Cirpa. “Straightening out nonlinear codes”. In: What’s Happening in the Mathematical Sciences. Hrsg. von P. Zorn. Bd. 2. American Mathematical Society, 1994, S. 37–40. [26] G. Constantine und R. S. Kulkarni. “On a result of S. Delsarte”. In: Proceedings of the American Mathematical Society 92.1 (1984), S. 149–152. [27] I. Constantinescu und W. Heise. “A metric for codes over residue class rings”. In: Problems of Information Transmission 33 (1997), S. 208–213. [28] J. H. Conway und N. J. A. Sloane. “Self-dual codes over the integers modulo 4”. In: Journal of Combinatorial Theory. Series A 62.1 (1993), S. 30–45. [29] P. Delsarte. “Weights of linear codes and strongly regular normed spaces”. In: Discrete Mathematics 3.1–3 (1972), S. 47–64. 88 Literatur [30] P. Delsarte. “An algebraic approach to the association schemes of coding theory”. In: Philips Research Reports 10 (1973). [31] P. Delsarte und J.-M. Goethals.“Alternating bilinear forms over GFq”. In: Journal of Combinatorial Theory. Series A 19.1 (1975), S. 26–50. [32] P. Delsarte und V. I. Levenshtein. “Association schemes and coding theory”. In: IEEE Transactions on Information Theory 44.6 (1998), S. 2477–2504. [33] S. Delsarte. “Fonctions de M¨ obius Sur Les Groupes Abeliens Finis”. In: Annals of Mathematics. Second Series 49.3 (1948), S. 600–609. [34] S. Dodunekov, T. Helleseth, N. Manev und Ø. Ytrehus. “New bounds on binary linear codes of dimension eight”. In: IEEE Transactions on Information Theory 33.6 (1987), S. 917–919. [35] S. Dodunekov und J. Simonis. “Codes and projective multisets”. In: Electronic Journal of Combinatorics 5 (1998), #R37. [36] P. E. Dyubyuk.“On the number of subgroups of an abelian p-group”. In: Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya 12.4 (1948), S. 351–378. [37] Y. Edel und J. Bierbrauer. “Twisted BCH-codes”. In: Journal of Combinatorial Designs 5.5 (1997), S. 377–389. [38] T. Feulner. “The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes”. In: Advances in Mathematics of Communications 3.4 (2009), S. 363–383. [39] T. Feulner. “Canonization of linear codes over Z4”. In: Advances in Mathematics of Communications 5.2 (2011), S. 245–266. [40] L. E. Fuller. “A canonical set for matrices over a principal ideal ring modulo m”. In: Canadian Journal of Mathematics 7 (1955), S. 54–59. [41] P. Gaborit und M. Harada. “Construction of extremal type II codes over Z4”. In: Designs, Codes and Cryptography 16.3 (1999), S. 257–269. [42] C. D. Godsil. Algebraic Combinatorics. New York: Chapman & Hall, 1993. isbn: 0-412-04131-6. [43] C. D. Godsil und G. Royle. Algebraic Graph Theory. Graduate Texts in Mathematics 207. New York: Springer, 2001. isbn: 0-387-95220-9. [44] J.-M. Goethals. “Two dual families of nonlinear binary codes”. In: Electronics Letters 10.23 (1974), S. 471–472. [45] J.-M. Goethals. “Nonlinear codes defined by quadratic forms over GF(2)”. In: Information and Control 31.1 (1976), S. 43–74. [46] M. Grassl. Code Tables: Bounds on the parameters of various types of codes.url: www.codetables.de. [47] P. P. Greenough und R. Hill. “Optimal linear codes over GF(4)”. In: Discrete Mathematics 125.1–3 (1994), S. 187–199. 89 Literatur [48] M. Greferath. “An introduction to ring-linear coding theory”. In: M. Sala, S. Sakata, T. Mora, C. Traverso und L. Perret. Gr¨ obner Bases, Coding, and Cryptography. Berlin: Springer, 2009, S. 219–238. isbn: 978-3-540-93805-7. [49] M. Greferath und S. E. Schmidt.“Gray isometries for finite chain rings and a nonlinear ternary (36,312,15) code.” In: IEEE Transactions on Information Theory 45.7 (1999), S. 2522–2524. [50] M. Greferath und S. E. Schmidt. “Finite-ring combinatorics and MacWilliams’ equivalence theorem”. In: Journal of Combinatorial Theory. Series A 92.1 (2000), S. 17–28. [51] P. Hall. “The algebra of partitions”. In: Proceedings of the 4th Canadian mathematical congress. Banff, 1959, S. 147–159. [52] A. R. Hammons Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane und P. Sol´e. “The Z4-linearity of Kerdock, Preparata, Goethals, and related codes”. In: IEEE Transactions on Information Theory 40.2 (1994), S. 301–319. [53] W. Heise und P. Quattrocchi. Informationsund Codierungstheorie. 3. Aufl. Berlin: Springer, 1995. isbn: 3-540-57477-8. [54] T. Helleseth. “Codes over Z4”. In: Computational Discrete Mathematics. Hrsg. von H. Alt. Lecture Notes in Computer Science 2122. Springer, 2001, S. 47–55. [55] L. Hemme, T. Honold und I. Landjev.“Arcs in projective Hjelmslev spaces obtained from Teichm¨ uller sets”. In: Proceedings of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory 2000. 2000, S. 4–12. [56] J. Hjelmslev.“Die Geometrie der Wirklichkeit”. In: Acta Mathematica 40.1 (1916), S. 35–66. [57] T. Honold. “Arcs and MDS-like codes over finite chain rings”. In: Proceedings of the Ninth International Workshop on Algebraic and Combinatorial Coding Theory 2004 (ACCT-2004). 2004, S. 223–229. [58] T. Honold. “Further results on homogeneous two-weight codes”. In: Proceedings of the Fifth International Workshop on Optimal Codes and related Topics 2007 (OC-2007). 2007, S. 80–86. [59] T. Honold.“Two-intersection sets in projective Hjelmslev spaces”. In: Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems. 2010, S. 1807–1813. isbn: 978-963-311-370-7. [60] T. Honold und M. Kiermaier. “Classification of maximal arcs in small projective Hjelmslev geometries”. In: Proceedings of the Tenth International Workshop on Algebraic and Combinatorial Coding Theory 2006 (ACCT-2006). 2006, S. 112– 117. [61] T. Honold und M. Kiermaier. “The existence of maximal (q2,2)-arcs in uniform projective Hjelmslev planes over chain rings of odd prime characteristic”. In: Designs, Codes and Cryptography (2012). Erscheint demn¨ achst. 90 Literatur [62] T. Honold und M. Kiermaier. “The maximal size of 6and 7-arcs in projective Hjelmslev planes over chain rings of order 9”. In: Science China. Mathematics 55.1 (2012), S. 73–92. [63] T. Honold, M. Kiermaier und I. Landjev. “New arcs of maximal size in projective Hjelmslev planes of order 9”. In: Comptes Rendus de l’Acad´emie Bulgare des Sciences 63.2 (2010), S. 171–180. [64] T. Honold und I. Landjev. “Linearly representable codes over chain rings”. In: Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg 69.1 (1999), S. 187–203. [65] T. Honold und I. Landjev. “Linear codes over finite chain rings”. In: Electronic Journal of Combinatorics 7 (2000), #R11. [66] T. Honold und I. Landjev. “On arcs in projective Hjelmslev planes”. In: Discrete Mathematics 231.1–3 (2001), S. 265–278. [67] T. Honold und I. Landjev. “On maximal arcs in projective Hjelmslev planes over chain rings of even characteristic”. In: Finite Fields and Their Applications 11.2 (2005), S. 292–304. [68] T. Honold und I. Landjev. “Caps in projective Hjelmslev spaces over finite chain rings of nilpotency index 2”. In: Innovations in incidence geometry. 4 (2006), S. 13–25. [69] T. Honold und I. Landjev. “Linear codes over finite chain rings and projective Hjelmslev geometries”. In: Codes over Rings. Proceedings of the CIMPA Summer School Ankara, Turkey, 18 – 29 August 2008. Hrsg. von P. Sol´e. Series on Coding Theory and Cryptology 6. World Scientific, 2009, S. 60–123. isbn: 978-981-283768-4. [70] T. Honold und I. Landjev.“The dual construction for arcs in projective Hjelmslev spaces”. In: Advances in Mathematics of Communications 5.1 (2011), S. 11–21. [71] T. Honold und I. Landjev. “Codes over rings and ring geometries”. In: Current research topics in Galois geometry. Hrsg. von L. Storme und J. de Beule. Mathematics Research Developments. New York: Nova Science Publishers, 2012, S. 161– 186. isbn: 978-1-61209-523-3. [72] T. Honold und I. Landjev. “Non-free extensions of the simplex codes over a chain ring with four elements”. In: Designs, Codes and Cryptography (2012). Erscheint demn¨ achst. [73] T. Honold und A. A. Nechaev. “Weighted modules and representations of codes”. In: Problems of Information Transmission 35.3 (1999), S. 205–223. [74] X.-D. Hou, K. H. Leung und Q. Xiang. “New partial difference sets in Zt p2and a related problem about Galois rings”. In: Finite Fields and Their Applications 7.1 (2001), S. 165–188. [75] W. C. Huffman und V. S. Pless. Fundamentals of Error-Correcting Codes. Cambridge: Cambridge University Press, 2003. isbn: 0521782805. 91 Literatur [76] T. Ito, A. Munemasa und M. Yamada. “Amorphous association schemes over the Galois rings of characteristic 4”. In: European Journal of Combinatorics 12.6 (1991), S. 513–526. [77] D. B. Jaffe. “Binary linear codes: New results on nonexistence”. 1996. url:http: //www.math.unl.edu/~djaffe/codes/code.ps.gz. [78] G. J. Janusz. “Separable algebras over commutative rings”. In: Transactions of the American Mathematical Society 122.2 (1966), S. 461–479. [79] A. Kerber. Applied finite group actions. 2. Aufl. Algorithms and Combinatorics 19. Berlin: Springer, 1999. isbn: 3-540-65941-2. [80] A. M. Kerdock. “A class of low-rate nonlinear binary codes”. In: Information and Control 20 (1972), S. 182–187. [81] Y. Al-Khamees. “The intersection of distinct Galois subrings is not necessarily Galois”. In: Compositio Mathematica 40.3 (1980), S. 283–286. [82] M. Kiermaier. “Arcs und Codes ¨ uber endlichen Kettenringen”. Diplomarbeit. Technische Universit¨ at M¨ unchen, 2006. [83] M. Kiermaier und M. Koch. “New complete 2-arcs in the uniform projective Hjelmslev planes over chain rings of order 25”. In: Proceedings of the Sixth International Workshop on Optimal Codes and Related Topics 2009. 2009, S. 206– 113. [84] M. Kiermaier, M. Koch und S. Kurz.“2-arcs of maximal size in the affine and the projective Hjelmslev plane over Z25”. In: Advances in Mathematics of Communications 5.2 (2011), S. 287–301. [85] M. Kiermaier und A. Kohnert. “New arcs in projective Hjelmslev planes over Galois rings”. In: Proceedings of the Fifth International Workshop on Optimal Codes and Related Topics 2007. 2007, S. 112–119. [86] M. Kiermaier und I. Landjev. “Designs in projective Hjelmslev spaces”. In: Contemporary Mathematics 579 (2012), S. 111–121. [87] M. Kiermaier und A. Wassermann.“Minimum weights and weight enumerators of Z4-linear quadratic residue codes”. In: IEEE Transactions on Information Theory 58.7 (2012), S. 4870–4883. [88] M. Kiermaier und J. Zwanzger. Online tables of linear codes over finite chain rings.url:codes.uni-bayreuth.de/Linear_Codes_R/. [89] M. Kiermaier und J. Zwanzger.“A new series of Z4-linear codes of high minimum Lee distance derived from the Kerdock codes”. In: Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems. 2010, S. 929–932. isbn: 978-963-311-370-7. [90] M. Kiermaier und J. Zwanzger. “A Z4-linear code of high minimum Lee distance derived from a hyperoval”. In: Advances in Mathematics of Communications 5.2 (2011), S. 275–286. 92 Literatur [91] M. Kiermaier und J. Zwanzger. “New ring-linear codes from geometric dualization”. In: Proceedings of the Seventh International Workshop on Coding and Cryptography. 2011, S. 111–120. [92] M. Kiermaier und J. Zwanzger. “New ring-linear codes from dualization in projective Hjelmslev geometries”. In: Designs, Codes and Cryptography (2012). Erscheint demn¨ achst. [93] W. Klingenberg. “Projektive und affine Ebenen mit Nachbarelementen”. In: Mathematische Zeitschrift 60 (1954), S. 384–406. [94] A. Kohnert.“Sets of type (d1, d2) in projective Hjelmslev planes over Galois rings”. In: Algorithmic Algebraic Combinatorics and Gr¨ obner Bases. Hrsg. von M. Klin, G. A. Jones, A. Juriˇsi´c, M. Muzychuk und I. Ponomarenko. Heidelberg: Springer, 2009, S. 269–278. isbn: 978-3-642-01959-3. [95] A. Kohnert und J. Zwanzger. “New linear codes with prescribed group of automorphisms found by heuristic search”. In: Advances in Mathematics of Communications 3.2 (2009), S. 157–266. [96] A. Kreuzer. “Projektive Hjelmslev-R¨ aume”. Diss. Technische Universit¨ at M¨ unchen, 1988. [97] A. Kreuzer. “A system of axioms for projective Hjelmslev spaces”. In: Journal of Geometry 40.1–2 (1991), S. 125–147. [98] W. Krull.“Algebraische Theorie der Ringe. II.” In: Mathematische Annalen 91.1– 2 (1924), S. 1–46. [99] A. S. Kuzmin und A. A. Nechaev. “Linearly representable codes and the Kerdock code over an arbitrary Galois field of characteristic 2”. In: Russian Mathematical Surveys 49.5 (1994), S. 183–184. [100] A. S. Kuzmin und A. A. Nechaev. “Complete weight enumerators of generalized Kerdock code and related linear codes over Galois rings”. In: Discrete Applied Mathematics 111.1–2 (2001), S. 117–137. [101] I. Landjev und S. Boev. “A family of two-weight ring codes and strongly regular graphs”. In: Comptes Rendus de l’Acad´emie Bulgare des Sciences 62.3 (2009), S. 297–302. [102] I. Landjev, S. Boev und T. Honold. “Optimal arcs in Hjelmslev spaces of higher dimension”. In: Proceedings of the Sixth International Workshop on Optimal Codes and Related Topics 2009. 2009, S. 132–138. [103] I. Landjev und T. Honold. “Arcs in projective Hjelmslev planes”. In: Discrete Mathematics and Applications 11.1 (2001), S. 53–70. [104] H. L¨ uneburg. “Affine Hjelmslev-Ebenen mit transitiver Translationsgruppe”. In: Mathematische Zeitschrift 79 (1962), S. 260–288. [105] J. Ma. “Three-class association schemes on Galois rings in characteristic 4”. In: Graphs and Combinatorics 23.1 (2007), S. 73–86. 93 Literatur [106] I. G. MacDonald. Symmetric Functions and Hall Polynomials. 2. Aufl. Oxford: Oxford University Press, 1995. isbn: 0-19-853489-2. [107] J. E. MacDonald. “Design methods for maximum minimum-distance error-correcting codes”. In: IBM Journal of Research and Development 4.1 (1960), S. 43– 57. [108] F. J. MacWilliams und N. J. A. Sloane. The Theory of Error-Correcting Codes. Amsterdam: North-Holland, 1977. isbn: 0-444-85009-0. [109] B. R. McDonald. Finite Rings with Identity. New York: Marcel Dekker, 1974. isbn: 0-8247-6161-8. [110] F. Miller Maley. “The Hall polynomial revisited”. In: Journal of Algebra 184.2 (1996), S. 363–371. [111] A. A. Nechaev. “Kerdock code in a cyclic form”. In: Discrete Mathematics and Applications 1.4 (1991), S. 365–384. [112] A. A. Nechaev. “Finite rings with applications”. In: Handbook of Algebra. Hrsg. von M. Hazewinkel. Bd. 5. Amsterdam: North-Holland, 2008. Kap. 5, S. 213–320. isbn: 978-0-444-53101-8. [113] A. A. Nechaev und A. S. Kuzmin.“Linearly presentable codes”. In: Proceedings of the International Symposium on Information Theory and its Application (ISITA) 1996. 1996, S. 31–34. [114] A. W. Nordstrom und J. P. Robinson. “An optimum nonlinear code”. In: Information and Control 11.5–6 (1967), S. 613–616. [115] G. H. Norton und A. S˘al˘agean. “On the structure of linear and cyclic codes over a finite chain ring”. In: Applicable Algebra in Engineering, Communication and Computing 10 (2000), S. 489–506. [116] A. M. Patel. “Maximal q-nary linear codes with large minimum distance”. In: IEEE Transactions on Information Theory 21.1 (1975), S. 106–110. [117] V. S. Pless und Z. Qian. “Cyclic codes and quadratic residue codes over Z4”. In: IEEE Transactions on Information Theory 42.5 (1996), S. 1594–1600. [118] F. P. Preparata. “A class of optimum nonlinear double-error-correcting codes”. In: Information and Control 13.4 (1968), S. 378–400. [119] R. Raghavendran. “Finite associative rings”. In: Compositio Mathematica 21.2 (1969), S. 195–229. [120] S. Roman. Advanced Linear Algebra. 3. Aufl. Graduate Texts in Mathematics 135. New York: Springer, 2008. isbn: 978-0-387-72828-5. [121] A. Scheerhorn.“Traceand norm-compatible extensions of finite fields”. In: Applicable Algebra in Engineering, Communication and Computing 3.3 (1992), S. 199– 209. [122] N. V. Semakov und V. A. Zinoviev. “Complete and quasi-complete balanced codes”. In: Problems of Information Transmission 5.2 (1969), S. 11–13. 94 Literatur [123] E. Steinitz. “Zur Theorie der Abel’schen Gruppen”. In: Jahresbericht der Deutschen Mathematiker-Vereinigung 9 (1901), S. 80–85. [124] F. Tamari.“On linear codes which attain the Solomon-Stiffler bound”. In: Discrete Mathematics 49.2 (1984), S. 179–191. [125] H. C. A. van Tilborg. “The smallest length of binary 7-dimensional linear codes with prescribed minimum distance”. In: Discrete Mathematics 33.2 (1981), S. 197– 207. [126] J. V. Uspensky. Theory of Equations. New York: McGraw-Hill, 1948. [127] Z.-X. Wan. Lectures on finite fields and Galois rings. World Scientific, 2003. isbn: 978-981-238-570-3. [128] E. Witt. “Zyklische K¨ orper und Algebren der Charakteristik pvom Grad pn. Struktur diskret bewerteter perfekter K¨ orper mit vollkommenem Restklassenk¨ orper der Charakteristik p”. In: Journal f¨ ur die Reine und Angewandte Mathematik 176 (1937), S. 126–140. [129] J. A. Wood. “Duality for modules over finite rings and applications to coding theory”. In: American Journal of Mathematics 121 (1999), S. 555–575. [130] Y. Yeh. “On prime power abelian groups”. In: Bulletin of the American Mathematical Society 54.4 (1948), S. 323–327. [131] J. Zwanzger. “A heuristic algorithm for the construction of good linear codes”. In: IEEE Transactions on Information Theory 54.5 (2008), S. 2388–2392. [132] J. Zwanzger.“Computergest¨ utzte Suche nach optimalen linearen Codes ¨ uber endlichen Kettenringen unter Verwendung heuristischer Methoden”. Diss. Universit¨ at Bayreuth, 2011. 95