Eine kanonische Form zur Darstellung äquivalenter Codes : Computergestützte Berechnung und ihre Anwendung in der Codierungstheorie, Kryptographie und Geometrie

Dissertation Eine kanonische Form zur Darstellung äquivalenter Codes – Computergestützte Berechnung und ihre Anwendung in der Codierungstheorie, Kryptographie und Geometrie – Von der Universität Bayreuth zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlung von Thomas Feulner geboren am 16. Februar 1982 in Bayreuth Vorwort Die vorliegende Arbeit entstand in den Jahren 2008 bis 2013 an der Universität Bayreuth unter Betreuung von Herrn Prof. Dr. Adalbert Kerber. Seiner beherzten Initiative ist es zu verdanken, dass ich nach dem Diplom meine Forschungsarbeit zur Kanonisierung linearer Codes fortsetzen konnte. Meinem Doktorvater möchte ich für seine Unterstützung und das allzeit entgegengebrachte Vertrauen herzlich danken. Als weiterer Glücksfall erwies sich für mich, dass nach der Emeritierung von Herrn Prof. Dr. Kerber die Arbeitsgruppe durch Prof. Dr. Alfred Wassermann und PD Dr. Axel Kohnert fortgeführt wurde. Ihnen ist es zu verdanken, dass die Finanzierung meiner Arbeit, zunächst über ein Stipendium der Bayerischen Eliteförderung und schließlich im Rahmen des DFG Schwerpunktprogramms 1489, sichergestellt werden konnte. Zutiefst betroffen bin ich immer noch darüber, dass ich Dir, Axel, diesen Dank nicht mehr persönlich aussprechen kann. Für eine konstruktive und stets unkomplizierte Zusammenarbeit bedanke ich mich bei allen weiteren Kollegen der Arbeitsgruppe, die mit hilfreichen Diskussionen und Ratschlägen zu dieser Arbeit beitrugen. Insbesondere meinen Bürokollegen Michael Kiermaier und Johannes Zwanzger sowie Elvira Rettner möchte ich aber hiermit nochmals gesondert, für die angenehme Arbeitsatmosphäre und ein allzeit offenes Ohr bei Fragen und Problemen danken. Meine Eltern, Roswitha und Gerhard, haben mich mit Aufnahme des Studiums bis heute kontinuierlich und bedingungslos unterstützt. Meine Freundin Melanie stand mir immer liebevoll motivierend auf dem langen Weg bis zur Promotion zur Seite. Für das entgegengebrachte Verständnis möchte ich mich von ganzem Herzen bei ihnen bedanken. Eckersdorf, im März 2014 Thomas Feulner Inhaltsverzeichnis 1. Einleitung 1 2. Grundlagen 7 2.1. Gruppen und Gruppenoperationen . . . . . . . . . . . . . . . . . . . . . 7 2.2. Graphen.................................... 11 2.3. EndlicheKettenringe............................. 13 2.3.1. Moduln und lineare Codes . . . . . . . . . . . . . . . . . . . . . . 14 2.3.2. Distanzen und Isometrien . . . . . . . . . . . . . . . . . . . . . . 17 2.4. Komplexität der Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3. Kanonisierungsalgorithmen 29 3.1. Grundbausteine der Kanonisierung . . . . . . . . . . . . . . . . . . . . . 30 3.1.1. Kanonisierung mittels Homomorphieprinzip . . . . . . . . . . . . 30 3.1.2. Kanonisierung über Untergruppen . . . . . . . . . . . . . . . . . . 37 3.2. Partitionen und Verfeinerungen . . . . . . . . . . . . . . . . . . . . . . . 39 3.2.1. Zur Kanonizität unter isomorphen Gruppenoperationen . . . . . . 44 3.2.2. Ausnutzen bekannter Automorphismen . . . . . . . . . . . . . . . 47 3.2.3. Implementierungsdetails . . . . . . . . . . . . . . . . . . . . . . . 52 3.2.4. Spezialfall: Die Kanonisierung von Graphen . . . . . . . . . . . . 54 3.2.5. Iterierte Verfeinerung . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3. Gruppen der Gestalt GoϕSP0....................... 61 3.3.1. Innere Kanonisierung . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.3.2. Gleichwertiger Algorithmenentwurf . . . . . . . . . . . . . . . . . 66 4. Endliche Kettenringe 71 4.1. WeitereGrundlagen.............................. 71 4.2. Automorphismen ............................... 78 5. Lineare Codes über endlichen Kettenringen 87 5.1. Generatormatrizen .............................. 87 5.1.1. Reformulierung der Gruppenoperation . . . . . . . . . . . . . . . 92 5.1.2. Die Operation von (GLk(R)×R∗n)oAutT............ 96 5.2. EinKanonisierer ...............................117 5.2.1. Innere Kanonisierung . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.2.2. Äußere Verfeinerung . . . . . . . . . . . . . . . . . . . . . . . . . 121 iii Inhaltsverzeichnis 5.2.3. Zur Kanonizität der kanonischen Repräsentanten bei isomorphen Ringen.................................129 6. Modifikationen & Anwendungen 133 6.1. Lineare Codes über Galois-Ringen der Charakteristik 4 . . . . . . . . . . 133 6.1.1. Klassifikation verallgemeinerter Teichmüller-Codes . . . . . . . . . 133 6.1.2. Automorphismen von verallgemeinerten Kerdock-Codes . . . . . . 136 6.2. Klassifikationsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 6.2.1. Lineare Codes über endlichen Körpern . . . . . . . . . . . . . . . 139 6.2.2. Nichtexistenz eines extremalen, selbstdualen Codes der Länge 72 mit vorgeschriebenen Automorphismen . . . . . . . . . . . . . . . 141 6.2.3. Lineare Codes über endlichen Kettenringen der Ordnung 4 . . . . 144 6.2.4. Kryptographie.............................146 6.3. Networkund Fq-lineare Fqr-Codes .....................150 6.3.1. Network-Codes ............................150 6.3.2. Fq-lineare Fqr-Codes .........................151 6.3.3. Ein Kanonisierer . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 7. Entwickelte Programme 155 7.1. Sage ......................................155 7.1.1. Lineare Codes über endlichen Körpern . . . . . . . . . . . . . . . 155 7.1.2. Lineare Codes über endlichen Kettenringen . . . . . . . . . . . . . 156 7.2. C++ Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 7.2.1. Installation ..............................158 7.2.2. Benutzung...............................159 8. Zusammenfassung & Ausblick 161 A. Untergruppen der Automorphismengruppe eines Kettenrings 165 iv Abbildungsverzeichnis 3.1. Homomorphieprinzip............................. 31 3.2. Kanonisieren mittels Homomorphieprinzip; Aufspalten . . . . . . . . . . 31 3.3. Kanonisieren mittels Homomorphieprinzip; Verschmelzen . . . . . . . . . 35 3.4. Illustration von Fakt 3.2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.5. Iterierte Verfeinerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.6. Suchbaum zu Beispiel 3.2.29 . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.7. Isomorphie der Suchbäume . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.1. Graph G(Γ) zuBeispiel5.2.5.........................125 Tabellenverzeichnis 4.1. Totalordnung auf F4[X]/(X2)........................ 75 6.1. Laufzeiten des Kanonisierers für Tq,k,s ....................136 6.2. Parameter, für welche keine linearen Codes existieren . . . . . . . . . . . 140 6.3. Anzahl nicht isomorpher [n, k, d]d⊥ 4-Codes für d≥6mit Unterscheidung nach d⊥....................................141 6.4. Resultate im Fall Z7.............................143 6.5. Klassifikationsergebnisse für Kettenringe der Kardinalität 4........145 6.6. Minimaldistanz der Gray-Bilder der Codes aus Tabelle 6.5 . . . . . . . . 146 v Algorithmenverzeichnis 5.1. MinStep ...................................107 5.1. MinStep (Fortsetzung) ...........................108 5.2. MinimizeDependent ............................114 5.3. MinimizeIndependent ...........................115 5.4. InnerCan ..................................119 A.1. Berechnung eines Erzeugendensystems für AutT..............166 vi Symbolverzeichnis GXEine Gruppenoperation von Gauf einer Menge X, Seite 7 G\\XDie Bahnen einer Gruppenoperation GX, Seite 7 FixG(X)Die Fixpunkte der Operation von Gauf X, Seite 7 L(G){H|H≤G}, Seite 7 C(G){Hg |H≤G, g ∈G}, Seite 8 CFG(x)Der kanonische Repräsentant einer Bahn Gx, Seite 8 TRG(x)Ein Transporterelement zu einer Kanonisierung CFG, Seite 8 StabG(x)Der Stabilisator von x∈Xzu einer Gruppenoperation GX, Seite 9 CanX GEin Kanonisierer zu einer Gruppenoperation GX, Seite 9 [n]{0, . . . , n −1}, Seite 9 Rad(R)Das Jacobson-Radikal eines Rings R, Seite 13 θEin Erzeuger von Rad(R), Seite 14 per(x)Die Periode eines Elements x∈RM, Seite 14 ht(x)Die Höhe eines Elements x∈RM, Seite 14 shp(M)Der Umriss eines R-Linksmoduls M, Seite 15 rg(M)Der Rang eines R-Linksmoduls M, Seite 15 λEin fest vorgegebener Umriss der betrachteten linearen Codes, Seite 16 Rk×n,λ Die Menge aller Generatormatrizen zu allen linearen Codes der Länge nvom Umriss λ= (λ0, . . . , λk−1), Seite 16 T(x, G)Der Suchbaum zur Definition von CanX G, Seite 39 I(x, Hg)Die Partitionierungsvorschrift im Suchbaum T(x, G), Seite 39 V(x, Hg)Die Verfeinerungsvorschrift im Suchbaum T(x, G), Seite 40 L(x, G)Die Menge aller Gruppenelemente, welche Blätter von T(x, G) definieren, Seite 40 L0(x, G){g∈L(x, G)|gx = CFG(x)}, Seite 41 B(x, Hg)Die Bewertung des Knotens Hg im Suchbaum T(x, Hg), Seite 42 FpDie Färbung der Koordinaten bezüglich der Partition p, Seite 51 PEine kanonische Partition zu [n], Seite 51 vii 1. Einleitung in meiner Diplomarbeit [22] bereits entworfen wurde. Die zugrunde liegenden Ideen werden wir in einer Allgemeinheit ausführen, die es dann erlaubt, unser Vorgehen auch auf weitere Klassen von Codes bzw. auf weitere Gruppenoperationen leicht zu übertragen. Diese Dissertation ist nun folgendermaßen aufgebaut: Zunächst werden wir in dem anschließenden Kapitel 2 wichtige Grundlagen über Gruppen und endliche Gruppenoperationen (Abschnitt 2.1), Graphen (2.2), Kettenringe Rund R-lineare Codes (2.3) zusammenfassen und die Notation festlegen. In diesem Kapitel klären wir auch die Frage zur Komplexität der Berechnung kanonischer Repräsentanten beziehungsweise eines Tests auf die Äquivalenz zweier gegebener R-linearer Codes, siehe Abschnitt 2.4. Hierdurch rechtfertigen wir unser Vorgehen im weiteren Verlauf der Arbeit. Das Kapitel 3 beschreibt dann verschiedene Ansätze zur Berechnung kanonischer Repräsentanten einer beliebigen Gruppenoperation von Gauf X. Das von uns bevorzugte Verfahren beruht auf der Beschreibung eines Backtrackalgorithmus, welcher erstmals für die Kanonisierung von Graphen [55] entwickelt wurde. Verallgemeinerungen auf beliebige Gruppenoperationen werden in [35] und [42] gegeben. Der Abschnitt 3.2 vereint beide Quellen und beschreibt den Backtrackbaum aus [42] über das Homomorphieprinzip für Gruppenoperationen, siehe [35, 50]. Weiterhin wird eine Bewertung der Knoten des Backtrackbaums definiert, welche das frühzeitige Abschneiden von Teilbäumen ermöglicht. Über die Untergruppe aller bislang bekannten Automorphismen des zu kanonisierenden Objekts x∈Xwird ein weiterer Test entwickelt, welcher es ebenfalls erlaubt, Teilbäume des Backtrackbaums von der Suche auszuschließen. Hierzu wird der Hilfssatz 3.3.3 aus der Arbeit [35] verschärft, um bestmögliche Resultate zu erzielen. Diese Verallgemeinerung wurde bereits in [22] angegeben, jedoch nicht im Zusammenhang einer allgemeinen Gruppenoperation von Gauf Xformuliert. Zum Abschluss des Kapitels wird auf Sonderfälle für die Gruppe Geingegangen. Zur Vorbereitung der Kanonisierung R-linearer Codes wird die Struktur eines Kettenrings Rin Kapitel 4 untersucht und eine Totalordnung definiert. Insbesondere wird in diesem Kapitel auch auf die Struktur der additiven Gruppe, der multiplikativen Gruppe und der Automorphismengruppe über die Angabe von Normalreihen eingegangen. Das Kapitel 5 geht dann schließlich auf lineare Codes über einem gegebenen Kettenring ein. Zunächst werden weitere wichtige Grundlagen gelegt. Anschließend formuliert man die Äquivalenz R-linearer Codes der Länge nüber eine Gruppenoperation einer Gruppe GoSnauf der Menge der Generatormatrizen. Für diese Operation wird schließlich ein Kanonisierer entwickelt. Das folgende Kapitel 6 gibt Anwendungsbeispiele für den entwickelten Kanonisierer und beschreibt mögliche Modifikationen, um diesen auch in der Kryptographie oder für Network-Codes und Fq-lineare Fqr-Codes anzuwenden. In mehreren Beispielen wird gezeigt, dass eine effiziente Kanonisierung häufig im Rahmen einer Klassifikation benötigt wird und dort das Herzstück bildet. So konnte etwa über eine vollständige Klassifikation in 217 Fällen die Existenz eines Fq-linearen Codes zu einem vorgeschriebenen Para4 metersatz, welcher in [31] als offen5geführt wird, ausgeschlossen werden. Die Beispiele belegen, dass es sich bei dem Kanonisierer um einen kompetitiven Algorithmus handelt. Über die beiliegende CD können die erzielten Verbesserungen eingesehen werden. Das Kapitel 7 schließt die Arbeit mit der Beschreibung der entstandenen Software ab. Die entstandenen Programmpakete können über die beiliegende CD installiert werden. Der Quellcode dieser Programme ist unter den Bedingungen der GNU General Public License (Version 3) [30] freigegeben, d.h. er darf beliebig kopiert, verbreitet, modifiziert und genutzt werden. 5Die Minimaldistanz eines optimalen linearen Codes ist bei vorgegebener Länge und Dimension unbekannt. 5 2. Grundlagen In dieser Arbeit werden die auftretenden algebraischen Strukturen, wie Gruppen, Ringe, Körper, Moduln usw., stets endlich sein. Wir werden die auftretenden Operationen, d.h. Gruppenoperationen auf Mengen bzw. die Moduloperationen, bevorzugt von links betrachten. Zumeist lassen sich die Definitionen und Sätze auf eine Operation von rechts übertragen. Gegebenenfalls werden wir auf diese auch ohne eine entsprechende Definition zurückgreifen. Zur Unterscheidung von Linksbzw. Rechtsmoduln werden wir RMbzw. MRschreiben. Im Fall von M=Rkwollen wir überdies vereinbaren, dass RRkden Linksmodul aller Zeilenvektoren und Rk Rden Rechtsmodul aller Spaltenvektoren bezeichne. Wir werden also, wie in der Codierungstheorie üblich, Vektoren als Zeilenvektoren auffassen. 2.1. Gruppen und Gruppenoperationen Bis auf Weiteres sei Geine fest vorgegebene endliche Gruppe, die auf einer endlichen Menge Xoperiere. Wir bezeichnen Xauch als G-Menge und werden diese Eigenschaft auch kurz mit GXkennzeichnen. Dieser Abschnitt soll vor allem zur Festlegung der Notationen dienen, für eine Einführung in die Theorie der Gruppenoperationen verweisen wir auf [43]. Die Bahn eines Elements x∈Xwerden wir mit Gx := {gx |g∈G}bezeichnen und die Menge aller Bahnen mit G\\X:= {Gx |x∈X}. Ein minimales System von Repräsentanten aller Bahnen nennen wir Transversale. Diejenigen Elemente x∈X, welche unter allen Gruppenelementen wieder auf sich selbst abgebildet werden, nennen wir Fixpunkte. Die Menge aller Fixpunkte von Xwerden wir mit FixG(X) := {x∈X| gx =x, ∀g∈G}bezeichnen. Zu einer Gruppe Gsei L(G) := {H|H≤G}die Menge aller Untergruppen von G. Die Gruppe Goperiert durch Konjugation auf L(G). Ist umgekehrt H∈ L(G)eine beliebige Untergruppe von Gso können wir die Multiplikation mit Elementen aus H •von links als eine Operation der Gruppe Hvon links auffassen. Eine Bahn Hg zu g∈Gnennen wir auch eine Rechtsnebenklasse von H. Die Bahnenmenge bezeichnen wir dann zur Auszeichnung dieser speziellen Situation mit H\G. •von rechts als eine Operation der Gruppe Hvon rechts auffassen. Die Bahnen nennen wir entsprechend Linksnebenklassen und wir bezeichnen die Bahnenmenge mit G/H. 7 2. Grundlagen Eine Transversale T⊆Gder (Links-)Rechtsnebenklassen von Hnennen wir dann eine (Links-)Rechtstransversale von Hin G. Ist Hein Normalteiler von Gso trägt G/H = H\Geine von Ginduzierte Gruppenstruktur mit neutralem Element H. Im Folgenden wollen wir außerdem mit C(G) := {Hg |H≤G, g ∈G}:= [ · H∈L(G) H\G die Menge aller Rechtsnebenklassen aller Untergruppen Hvon Gbezeichnen. Zusätzlich definieren wir auf der Menge C(G)eine Gruppenoperation von g0∈Güber g0? Hg := Hgg−1 0. Eine entscheidende Rolle bei der Untersuchung von Gruppenoperationen bilden Homomorphismen: Ist Yeine weitere G-Menge, so nennen wir eine Funktion f:X→Y einen G-Homomorphismus, falls f(gx) = gf(x)für alle x∈Xund g∈Ggilt. Ist die Operation im Bildbereich trivial (gy =yfür alle g∈Gund y∈Y), so sprechen wir auch von einer G-Invarianten f. Operiert auf Yeine Gruppe Hund ist ϕ:G→Hein Gruppenhomomorphismus, welcher mit einer Abbildung f:X→Yim folgenden Sinne f(gx) = ϕ(g)f(x),∀g∈G, x ∈X, verträglich ist, so nennen wir das Paar (ϕ, f)einen Homomorphismus von Gruppenoperationen. 2.1.1 Bemerkung. Offensichtlich können wir über einen solchen Homomorphismus (ϕ, f)von Gruppenoperationen auch eine Operation von Gauf dem Bild f(X)⊆Y definieren, vermöge: g·f(x) := ϕ(g)f(x). Setzen wir die Operation von Gauf Y\f(X) trivial fort, so haben wir eine Gruppenoperation von Gauf Ydefiniert. Die Abbildung fist also auch ein G-Homomorphismus. Homomorphismen von Gruppenoperationen haben den Vorteil, dass sich die Angabe der Operation hierdurch im Bildbereich zumeist auf natürliche Weise definieren lässt. Nun zu der formalen Beschreibung unserer Problemstellung für allgemeine Gruppenoperationen. 2.1.2 Definition (Kanonisierung).Eine G-invariante Funktion CFG:X→Xnennen wir Kanonisierung, falls CFG(x)∈Gx für alle x∈Xgilt. Das Element CFG(x) bezeichnen wir als den kanonischen Repräsentanten von xbzw. der Bahn Gx. 2.1.3 Definition (Transporterelement).Ist CFG:X→Xeine Kanonisierung so nennen wir Gruppenelemente g∈Gmit gx = CFG(x)Transporterelemente zu x∈X. Eine Abbildung TRG:X→G, welche jedem x∈Xein zugehöriges Transporterelement zuordnet heißt Transporterabbildung. 8 2.1. Gruppen und Gruppenoperationen Transporterelemente sind bis auf Rechtsmultiplikation mit Elementen aus dem Stabilisator StabG(x) := {g∈G|gx =x}von xeindeutig bestimmt. Ist die operierende Gruppe aus dem Zusammenhang ersichtlich, so wollen wir Elemente des Stabilisators auch als Automorphismen von xbezeichnen. Insofern werden wir auch von der Automorphismengruppe Aut(x)des Objekts xsprechen. Genauso benutzen wir auch den Begriff isomorph für Elemente x, x0der gleichen Bahn. Da jede Gruppenoperation auch eine Äquivalenzrelation auf Xdefiniert, werden wir die Elemente x, x0der gleichen Bahn auch als äquivalent bezeichnen. 2.1.4 Definition (Kanonisierer).Ist CFG:X→Xeine Kanonisierung mit einer Transporterabbildung TRG:X→G, so wollen wir das Tripel CanG:= (CFG,TRG,StabG) als Kanonisierer bezeichnen. 2.1.5 Bemerkung. Gegebenenfalls – etwa falls Gauf mehreren Mengenoperiert – werden wir die Kanonisierer CanX G:= (CFX G,TRX G,StabG)über die zusätzliche Angabe der Menge Xim Exponenten unterscheiden. Für die Zuordnung von x∈Xauf seinen Stabilisator StabG(x)besteht keine Wahlmöglichkeit. Wir verzichten daher auf die zusätzliche Angabe von Xin dieser Beschreibung der Stabilisatorfunktion StabG:X→ L(G). 2.1.6 Bemerkung. Durch Angabe des Transporterelements TRG(x)ist der kanonische Repräsentant CFG(x) = TRG(x)xvon x∈Xbereits eindeutig bestimmt. Die redundante Information CFGbei der Definition des Kanonisierers soll vor allem verdeutlichen, zu welcher Kanonisierungsfunktion die Transporterelemente bestimmt wurden. Diese Definition eines Kanonisierers ist weniger aus mathematischer Sichtweise motiviert sondern gibt vielmehr unseren algorithmischen Standpunkt auf das Problem wieder. Wir wollen ein Computerprogramm entwerfen, welches einen Kanonisierer implementiert. Eingabe ist also ein Objekt x∈Xund wir erwarten die Rückgabe eines kanonischen Repräsentanten, eines zugehörigen Transporterelements und des Stabilisators. In diesem Sinne wollen wir auch die Berechnung des Stabilisators StabG(x)als durchgeführt ansehen, d.h. wir haben diese Untergruppe nicht nur formal sondern tatsächlich über ein berechnetes Erzeugendensystem Efür weitere Untersuchungen zur Verfügung. Über den Programmfluss steuern wir, dass tatsächlich ein Kanonisierer CanGrealisiert wird. Die mathematische Angabe der zugehörigen Kanonisierungsfunktion ist damit häufig sehr umfangreich und nur dem Programmablauf zu entnehmen. Folgende Gruppen sind für uns von besonderem Interesse: •Die symmetrische Gruppe SX:= {f:X→X|fbijektiv}auf einer endlichen Menge X. Ist X= [n] := {0, . . . , n −1}, so schreiben wir auch kurz Snstatt S[n]. •Die multiplikative Gruppe R∗aller Einheiten des Rings R. •Die Gruppe aller invertierbaren (k×k)-Matrizen, die allgemeine lineare Gruppe GLk(R)über dem Ring R. 9 2. Grundlagen Über die Definition (A, x)7→ xA−1operiert die Gruppe GLk(R)von links auf RRk. Für fest gewähltes A∈GLk(R)ist hierdurch auch eindeutig eine linkslineare, invertierbare Abbildungen fA:RRk→RRk, x 7→ xA−1gegeben und damit der natürliche Gruppenisomorphismus in die Gruppe der linkslinearen Abbildungen definiert. Des Weiteren bezeichnen wir zu zwei Gruppen G, H und einem gegebenen Gruppenhomomorphismus θ:G→Aut(H)mit HoθG:= {(h;g)|h∈H, g ∈G}das semidirekte Produkt beider Gruppen bezüglich θ. Die Multiplikation ist dabei über die Vorschrift (h;g)(h0;g0) := (hθ(g)(h0); gg0) definiert. Wir werden die Angabe des Gruppenhomomorphismus θunterdrücken, sofern dieser aus dem Kontext eindeutig hervorgeht. Ist θ(g) = idHfür alle g∈G, so ist das semidirekte Produkt gleich dem direkten Produkt beider Gruppen. 2.1.7 Beispiel. Es sei Rein Ring und der Gruppenhomomorphismus θ: Aut(R)→Aut(GLk(R)) α7→ ((Ai,j)7→ (α(Ai,j))) definiert über die komponentenweise Anwendung des Automorphismus α∈Aut(R)auf die Matrizen A∈GLk(R). Das semidirekte Produkt ΓLk(R) := GLk(R)oθAut(R) nennen wir die allgemeine semilineare Gruppe vom Grad k. 2.1.8 Definition (semilineare Abbildungen).Wir nennen eine Abbildung f:RRn→ RRnlinkssemilinear, falls es einen Ringautomorphismus α∈Aut(R)gibt, so dass f(u+v) = f(u) + f(v)und f(ru) = α(r)f(u)für alle u, v ∈Rkund r∈Rgilt. Die Gruppe ΓLk(R)operiert auf RRküber die Definition (A;α)v:= α(v)A−1und ist isomorph zur Gruppe der linkssemilinearen Abbildungen auf Rk. Im Folgenden werden wir daher die Gruppe der (semi-)linearen Abbildungen als GLk(R)bzw. ΓLk(R) ausdrücken. Schließlich werden wir zu einer Permutation π∈Snund einem Ring Rdie Permutationsmatrix P(π)∈ {0R,1R}über P(π):=    eπ−1(0) . . . eπ−1(n−1)   =eT π(0) · · · eT π(n−1) definieren. Es bezeichne hierbei eiden i-ten Einheitsvektor. Wir können also über den Gruppenmonomorphismus Sn→GLn(R), π 7→ P(π)die Gruppe Snauch als Untergruppe von GLn(R)bzw. ΓLn(R)auffassen. Eine Permutation π∈Snoperiert daher auf RRndurch Rechtsmultiplikation mit (P(π))−1= (P(π))T=P(π−1), d.h. π·ei:= eiP(π−1)=eπ(i)=(ei)π−1(0),...,(ei)π−1(n−1) =⇒π·(v0, . . . , vn−1)=(v0, . . . , vn−1)P(π−1) = (vπ−1(0), . . . , vπ−1(n−1))für alle v∈RRn. 10 2.2. Graphen Ist Rein Ring und ϕ∈Rn, so bezeichne diag(ϕ) := D∈Rn×ndie Diagonalmatrix D mit Einträgen Di,i =ϕi. Das semidirekte Produkt (R∗)noΘSnmit Θ(π)(ϕ) := ϕP(π−1) nennen wir die monomiale Gruppe vom Grad nüber R. Diese Produktbildung kann auch als das Kranzprodukt R∗onSnvon R∗mit Sngesehen werden. Auch die monomiale Gruppe lässt sich über den Gruppenmonomorphismus (R∗)noΘSn→GLn(R),(ϕ;π)7→ diag(ϕ)P(π) in die Gruppe GLn(R)einbetten. Die Bilder nennen wir daher auch monomiale Matrizen. Diese Gruppe operiert somit auf RRndurch: (ϕ;π)v:= vP(π−1)diag(ϕ)−1=vπ−1(0)ϕ−1 0, . . . , vπ−1(n−1)ϕ−1 n−1. Nimmt man zusätzlich noch die Ringautomorphismen hinzu, so erhält man die sogenannte semimonomiale Gruppe ((R∗)noΘSn)oθAut(R)und wir können diese analog in ΓLk(R)einbetten. Die von (ϕ;π, α)∈((R∗)noΘSn)oθAut(R)auf RRninduzierte Abbildung v7→ (ϕ;π, α)v:= (ϕ;π)α(v) = α(v)P(π−1)diag(ϕ)−1 =α(vπ−1(0))ϕ−1 0, . . . , α(vπ−1(n−1))ϕ−1 n−1 nennen wir auch eine (semi-)monomiale Transformation von Rn. Da die Operation der Automorphismengruppe auf Permutationsmatrizen trivial ist, können wir dieses semidirekte Produkt auch wie folgt beschreiben: ((R∗)noΘSn)oθAut(R)=(R∗)noϑ(Sn×Aut(R)) (2.1) mit ϑ((π, α)) := Θ(π)◦θ(α) = θ(α)◦Θ(π)für alle (π, α)∈Sn×Aut(R). Wir werden später sehen, dass die Gruppe (2.1) in der Codierungstheorie über endlichen Kettenringen1Reine zentrale Rolle spielt. Sie definiert den allgemeinsten Äquivalenzbegriff für R-lineare Codes. Analog ist die Operation von ΓLn(R)auf der Menge der Spaltenvektoren Rn Rgegeben durch (A;α)vT=Aα(vT). Sie ist isomorph zu den rechtssemilinearen Abbildungen auf Rn R. Entsprechend leiten sich auch die Operationen der eingeführten Untergruppen ab. 2.2. Graphen Wie wir bereits in der Einleitung kurz bemerkten, lassen sich viele Isomorphieprobleme diskreter Strukturen, wie etwa linearer Codes, auf das Graphenisomorphieproblem zurückführen. Wir wollen daher auf diese kombinatorische Struktur kurz eingehen. Umgekehrt lässt sich das Graphenisomorphieproblem aber auch mit einem Äquivalenztest 1Definition folgt. 11 2. Grundlagen für lineare Codes lösen. Dies ist vor allem aus Gründen der Komplexitätsabschätzung, die wir in Abschnitt 2.4 durchführen werden, von großem Interesse. Des Weiteren ist dieser Exkurs auch durch die Tatsache motiviert, dass der in [55] beschriebene Kanonisierer für Graphen fundamentale Ideen, siehe Kapitel 3, für die Entwicklung unserer codierungstheoretischen Kanonisierer beinhaltet. Schließlich erfolgt die Formulierung des Lösungsalgorithmus selbst über die Definition eines Suchbaums, d.h. über spezielle Graphen. Wir wollen zu einer beliebigen Menge Vmit V kdie Menge ihrer k-Teilmengen bezeichnen. Ein (ungerichteter) Graph Γ=(V, E)ist ein Tupel mit einer Menge Vvon Knoten und einer Menge E⊆V 2von Kanten. Wir schreiben dann auch [2](V 2)für die Menge aller Graphen mit Knotenmenge V, wobei wir den Vektor e∈[2](V 2)als die Menge E:= {{v, w} ∈ V 2|e{v,w}= 1}interpretieren. Einen gerichteten Graphen erhält man, wenn man die Knotenpaare geordnet betrachtet, d.h. E⊆V×Vwählt. Für unsere Zwecke können wir immer von einer endlichen Menge Vausgehen und zumeist sind die untersuchten Graphen ungerichtet. Wir nennen zwei Graphen (V, E),(V0, E0)isomorph, falls es eine Bijektion f:V→V0 gibt mit {v, w} ∈ E⇐⇒ {f(v), f(w)} ∈ E0. Isomorphe Graphen gehen also durch Umnummerierung der Knotenbeschriftungen auseinander hervor. Zur Untersuchung der Isomorphie von Graphen können wir stets annehmen, dass die Knotenmengen V, V 0gleich sind und dass ohne Beschränkung der Allgemeinheit V= [n] := {0, . . . , n −1}für ein n∈Ngilt. Andernfalls bilden wir Vbzw. V0über eine beliebige Bijektion nach [n]ab. Diese Beobachtung erlaubt es uns nun, die Graphenisomorphie über die Gruppenoperation der symmetrischen Gruppe Snauf der Potenzmenge [2]([n] 2)aller Zweierteilmengen von [n]zu untersuchen. Zwei Knoten u, v ∈Veines Graphen (V, E)heißen benachbart (adjazent), falls {u, v} ∈ Egilt. Eine Adjazenzmatrix A∈ {0,1}n×neines Graphen ([n], E)beschreibt die Nachbarschaftsbeziehung durch die Definition Ai,j =1:⇐⇒ {i, j} ∈ E. Über eine Inzidenzmatrix I∈ {0,1}m×neines Graphen ([n], E)wird die Knoten-Kanten-Inklusion beschrieben; man erhält sie über eine Anordnung der Kantenmenge (e0, . . . , em−1)und Setzung Ii,j = 1 :⇐⇒ j∈ei. Inzidenzmatrizen sind also nur bis auf Permutation der Zeilen eindeutig bestimmt. Der nachfolgende Satz beschreibt die Isomorphie von Graphen über verschiedene Gruppenoperationen, je nachdem ob man zur Darstellung des Graphen die Kantenmenge, eine Adjazenzmatrix oder eine Inzidenzmatrix wählt: 2.2.1 Fakt. Es seien Gi= ([n], Ei),i= 0,1Graphen mit mKanten und gegebenen Inzidenzmatrizen Iiund Adjazenzmatrizen Ai. Dann sind äquivalent: •G0und G1sind isomorph. •E1∈SnE0(mit π{. . . , {u, v}, . . .}:= {. . . , {π(u), π(v)}, . . .}) 12 2.3. Endliche Kettenringe •A1∈SnA0(mit πA := P(π)AP(π−1)) •I1∈(Sm×Sn)I0(mit (σ, π)I:= P(σ)IP(π−1)) Abschließend wollen wir noch Wurzelbäume einführen, die wir zur Definition der Kanonisierer benötigen werden. Im Graphen (V, E)nennen wir eine Folge paarweise verschiedener Knoten v0, . . . , vk∈Vmit {vi, vi+1} ∈ Efür alle i∈[k]einen Pfad von v0 nach vk. Die Knoten v0, vk∈Vnennen wir dann auch verbunden. Der Graph (V, E)ist zusammenhängend, falls alle Knoten paarweise verbunden sind. Einen zusammenhängenden Graphen (V, E), bei welchem genau ein Pfad zwischen jedem beliebigen Knotenpaar existiert, nennen wir Baum. Ist überdies r∈Vein ausgezeichneter Knoten, so nennen wir ((V, E), r)einen Wurzelbaum mit Wurzel r. Jedem Knoten veines Wurzelbaums können wir über die Pfadlänge des Pfads von der Wurzel rnach veine eindeutige natürliche Zahl d(v)zuordnen. Wir nennen sie die Tiefe des Knotens v. Ist {v, w} ∈ Eeine Kante eines Wurzelbaums und d(v) = d(w)+1, so nennen wir wein Kind(-knoten) von vund vden Vater(-knoten) zu w. Dementsprechend nennen wir alle Knoten w, die auf dem Pfad von der Wurzel zu v∈Vliegen, auch Vorfahren von vund umgekehrt veinen Nachfahren von w. Knoten ohne Nachfahren heißen Blätter. Der Teilgraph bestehend aus allen Nachfahren eines Knotens v∈Vbildet wiederum selbst einen Wurzelbaum mit Wurzel v. Unter einer Breitensuche (breadth-first-search) auf einem Wurzelbaum ((V, E), r)verstehen wir eine Besuchsreihenfolge (v0, . . . , vn−1)aller Knoten, so dass die entsprechende Folge der Tiefen monoton wächst. Im Gegensatz dazu dringt die sogenannte Tiefensuche (depth-first-search) zunächst bis zu einem beliebigen Blatt im Baum vor und kehrt danach rekursiv zu den Vorfahren zurück um dort alle weiteren unbesuchten Kinder und deren Nachfahren ebenfalls in Tiefensuche zu durchlaufen. 2.3. Endliche Kettenringe Es sei Rstets ein assoziativer Ring mit Eins. Die hier angegebenen Resultate über Kettenringe wurden aus [11] entnommen. 2.3.1 Definition (Kettenring).Wir nennen Reinen Linkskettenring, falls die Menge der Linksideale bzgl. Inklusion totalgeordnet ist. Der Idealverband bildet also eine Kette {0}=I0I1. . . Im=R. Rechtskettenringe seien analog definiert. Einen Ring, der sowohl Linksals auch Rechtskettenring ist, nennen wir Kettenring. 2.3.2 Fakt. Ist Rendlich, so ist Rgenau dann ein Linkskettenring, wenn Rein Rechtskettenring ist. Da wir im Folgenden nur noch endliche Kettenringe betrachten werden, können wir also die Unterscheidung zwischen Linksund Rechtskettenringen vernachlässigen. Das Jacobson-Radikal Rad(R)eines Rings Rist definiert als der Schnitt aller maximalen 13 2. Grundlagen 2.3.27 Fakt (J. MacWilliams [52]).Das Hamming-Gewicht besitzt die MacWilliamsEigenschaft für jeden endlichen Körper Fq. Die Menge aller Uw-monomialen Transformationen von Rnbildet eine Untergruppe der monomialen Gruppe vom Grad n. Wir wollen diese Untergruppe auch die Uw-monomiale Gruppe vom Grad nnennen. Hat ein Gewicht w:R→R+ 0die MacWilliams-Eigenschaft, so folgt sofort mit C=Rn, dass dann die Menge aller linearen Isometrien von Rngleich der Uw-monomialen Gruppe vom Grad nist. 2.3.28 Fakt ([72, Theorem 9.4]).Alle Gewichte w:R→R+ 0mit Uw=R∗haben die MacWilliams-Eigenschaft. 2.3.29 Bemerkung. J. Wood [72] definiert einen wesentlich freieren Gewichtsbegriff als wir ihn hier zulassen. Er fordert lediglich eine Funktion w:R→Qmit w(0R)=0. Das obige Theorem benötigt dann als weitere Voraussetzung w(θm−1)6= 0. Hat das Gewicht weine kleinere Symmetriegruppe, so können die zu erfüllenden Bedingungen für die MacWilliams-Eigenschaft um ein Vielfaches schwieriger werden, siehe [72]. Da die für unsere Zwecke entscheidenden Gewichte (das Hamming-Gewicht und auch das homogene Gewicht) aber die obige Eigenschaft erfüllen, werden wir im Folgenden nur noch Gewichte mit maximaler Symmetriegruppe Uw=R∗untersuchen. Für beide Gewichte bzw. Distanzen ist also die Gruppe der linearen Isometrien isomorph zu der monomialen Gruppe (R∗)noSn. Das weitere Vorgehen ließe sich aber durchaus analog für beliebige Uw-monomiale Gruppen umsetzen. Wir verzichten hierauf zur einfacheren Verständlichkeit der weiteren Argumentationen. 2.3.30 Hilfssatz. Ist w:R→R+ 0ein Gewicht mit Uw=R∗, so definiert die komponentenweise Anwendung eines Ringautomorphismus α∈Aut(R)eine Isometrie auf dem metrischen Raum (Rn, dw),n∈N. Beweis. Für alle a∈Rist ht(α(a)) = ht(a)und wegen Uw=R∗auch w(α(a)) = w(a). Damit definiert die komponentenweise Anwendung von αaber ganz offensichtlich eine Isometrie von (Rn, dw). Wir haben die Formulierung der MacWilliams-Eigenschaft eines Gewichts von J. Wood übernommen. Tatsächlich zeigt J. MacWilliams aber in ihrer Arbeit [52], dass sich jede semilineare Isometrie zwischen zwei gegebenen linearen Codes über einem Körper Fq zu einer semimonomialen Transformation auf ganz Fn qfortsetzen lässt. Der folgende Hilfssatz zeigt, dass die MacWilliams-Eigenschaft im Fall von Uw=R∗auch hinreichend ist. Er verallgemeinert die Aussage aus [73, Satz 2.16], welche nur das Hamming-Gewicht und das homogene Gewicht betrachtet. Die Beweisidee ist jedoch identisch. 2.3.31 Hilfssatz. Es sei w:R→R+ 0ein Gewicht mit Uw=R∗. Dann lässt sich jede semilineare Isometrie f: (C, dw)→(Rn, dw)zu jedem C≤Rnund n∈Nzu einer semimonomialen Transformation von Rnfortsetzen. 20 2.3. Endliche Kettenringe Beweis. Es sei wein Gewicht mit der MacWilliams-Eigenschaft und f:C→RRn eine beliebige semilineare Isometrie für C≤Rnmit zugehörigen Ringautomorphismus α∈Aut(R). Dann ist aber f◦α−1ebenfalls eine Isometrie von Cund linear. Sie lässt sich wegen der MacWilliams-Eigenschaft des Gewichts aber über eine monomiale Matrix A= diag(ϕ)P(π)für ein (ϕ;π)∈(R∗)noSndarstellen. Insgesamt ergibt sich also die zu beweisende Behauptung, dass feine semimonomiale Transformation von Rnist. 2.3.32 Folgerung. Ist w:R→R+ 0ein Gewicht mit Uw=R∗, dann ist die Gruppe aller semilinearen Isometrien von (Rn, dw)isomorph zu (R∗)no(Aut(R)×Sn). 2.3.33 Bemerkung. Hat das Gewicht weine kleinere Symmetriegruppe Uw6=R∗, so muss man sich auch bei der Operation der Automorphismengruppe von Rauf diejenige Untergruppe einschränken, welche das Gewicht respektiert. 2.3.34 Bemerkung. Hat ein Gewicht wmit Uw=R∗die MacWilliams-Eigenschaft, so können wir diese nicht nur dazu nutzen, den Äquivalenzbegriff auf die Gruppenoperation der semimonomialen Gruppe zurückzuführen. Sie zeigt auch, dass wir die Definition der Äquivalenz von zwei linearen Codes C0, C1≤Rnallgemeiner über die Existenz einer semilinearen Isometrie ι:C0→C1definieren könnten, ohne dass dies zu veränderten Äquivalenzklassen führen würde. Wir werden im Folgenden von Gewichten wbzw. Metriken dwausgehen, für welche die Symmetriegruppe Uw=R∗maximal ist. Wir nennen dann zwei Codes C0, C1≤Rn •(semi-)linear isometrisch, wenn es eine (semi-)monomiale Transformation von Rn gibt, die den einen auf den anderen überführt, bzw. •permutationsisometrisch, wenn es eine Koordinatenpermutation gibt, welche den einen auf den anderen überführt. 2.3.35 Definition (symmetrisiertes Gewicht).Das symmetrisierte Gewicht3eines Vektors v∈Rndefinieren wir als wsym(v) := (a0(v), . . . , am(v)) mit ai:= |{j∈[n]| per(aj) = i},∀i∈[m+ 1]. 2.3.36 Folgerung. Jedes Gewicht wmit maximaler Symmetriegruppe Uw=R∗lässt sich mit Hilfe des symmetrisierten Gewichts als Vektorprodukt w(v) = wsym(v)·(w(θm), . . . , w(θ0))T schreiben. Das Gewicht wselbst wird also nicht weiter Eingang in diese Arbeit finden. Wir werden vielmehr das symmetrisierte Gewicht wsym benutzen, da es eindeutig die Bahnen der Gruppe aller semilinearen Isometrien auf RRnbeschreibt. 3Dies ist kein Gewicht im Sinne von Definition 2.3.22. 21 2. Grundlagen 2.4. Komplexität der Probleme Für eine Einführung in die Komplexitätstheorie verweisen wir den Leser auf eines der zahlreichen Lehrbücher zur theoretischen Informatik oder zu diesem speziellen Teilgebiet, etwa [71]. Zunächst ist es für weitere Komplexitätsuntersuchungen notwendig, das zu untersuchende Problem als ein Entscheidungsproblem zu formulieren, d.h. als eine Fragestellung, die eindeutig (entscheidbar) mit ja oder nein für alle Eingaben zu beantworten ist. Zum Beispiel definieren wir das Graphenisomorphieproblem GI als die Frage: „Sind zwei beliebige gegebene Graphen isomorph?“ Unter einer Eingabe zu einem Entscheidungsproblem Pwollen wir nun die Fragestellung verstehen, die es im Konkreten zu beantworten gilt; im Beispiel der Graphenisomorphie also ein Vorgabe eines Paares (G0, G1)aus zwei Graphen G0, G1∈V 2. Der Eingabe wird nun eine Eingabelänge zugeordnet, um die benötigte Rechenzeit auch in Relation zu der Problemgröße setzen zu können. Wir gehen daher davon aus, dass sich die Eingabe Iauf natürliche Weise als eine Zeichenkette über einem endlichen Alphabet beschreiben lässt. Zum Beispiel werden die Graphen durch Adjazenzmatrizen oder lineare Codes durch Generatormatrizen beschrieben. Der Eingabe Iordnen wir dann die Länge |I|dieser Zeichenkette zu. Für das Graphenisomorphieproblem hat somit die Eingabe (G0, G1)zum Beispiel die Länge |(G0, G1)|= 2 ·2n2. Eine Turingmaschine ist nun ein Modell der Informatik um den Begriff der Rechenzeit eines Algorithmus zu standardisieren. Bei einer deterministischen Turingmaschine ist die nächste durchgeführte Aktion eindeutig durch den aktuellen Zustand der Maschine und des Zeichens an der aktuellen Position des Lesekopfs definiert. Wir sagen, eine deterministische Turingmaschine (ein deterministischer Algorithmus) löst ein Problem Pin Polynomialzeit, falls ein Polynom p∈R[x]existiert, so dass sich für alle Eingaben I die maximal notwendige Anzahl von Schritten der Turingmaschine zur Eingabe Idurch p(|I|)nach oben abschätzen lässt. Im Gegensatz dazu kann eine nichtdeterministische Turingmaschine in jedem Zustand für die aktuelle Eingabe stets zwischen zwei Aktionen wählen, wobei es keine Vorschrift gibt, wie diese Aktion ausgewählt wird. Eine nichtdeterministische Turingmaschine löst ein Entscheidungsproblem zur Eingabe I, falls sie bei der Korrektheit der Aussage die Antwort „ja“ auf einem zulässigen Rechenweg erreichen kann. Ist die Antwort auf die Aussage „nein“, so führen auch alle Rechenwege zur Antwort „nein“. Eine nichtdeterministische Turingmaschine arbeitet in Polynomialzeit, falls sie die Rechnung auf allen zulässigen Rechenwegen in Polynomialzeit in der Eingabelänge beendet. Wir sagen, ein Entscheidungsproblem P0sei schwerer als das Entscheidungsproblem P1, falls wir jede Eingabe Ifür das Problem P1in Polynomialzeit auf eine Eingabe J(I) zu P0transformieren können, so dass Igenau dann mit „ja“ beantwortet wird, wenn auch J(I)mit „ja“ beantwortet wird. Wir sagen hierzu auch, dass wir das Entscheidungsproblem P1in Polynomialzeit auf das Entscheidungsproblem P0zurückführen. 22 2.4. Komplexität der Probleme Mit diesen Definitionen lassen sich nun die bekannten Komplexitätsklassen Pdie Klasse aller Entscheidungsprobleme, welche in Polynomialzeit auf einer deterministischen Turingmaschine lösbar sind, NP die Klasse aller Entscheidungsprobleme, die in Polynomialzeit auf einer nichtdeterministischen Turingmaschine lösbar sind, NP-schwer die Klasse aller Entscheidungsprobleme P0, für die jedes Problem P1aus der Klasse NP in Polynomialzeit auf P0zurückgeführt werden kann und NP-vollständig die Klasse aller NP-schweren Entscheidungsprobleme in NP definieren. Entscheidungsprobleme aus der Klasse NP lassen sich auch dadurch charakterisieren, dass jede „Ja“-Antwort in Polynomialzeit auf einer deterministischen Turingmaschine verifizierbar ist. 2.4.1 Beispiel. Das Graphenisomorphieproblem GI ist in NP, denn wir können in Polynomialzeit überprüfen, ob eine gegebene Permutation πder Knoten einen Isomorphismus zwischen beiden Graphen definiert. Die Problemklasse Pist in NP enthalten und sie beinhaltet die einfacheren Fragestellungen. NP-schwere Probleme zeichnen sich dadurch aus, dass sie mindestens so schwer sind wie alle anderen Probleme aus NP. Eine der wichtigsten Fragestellungen der Mathematik ist die Entscheidung, ob P=NP gilt. Das Clay Mathematics Institute4hat einen Geldpreis in Höhe von einer Millionen Dollar für die Lösung ausgeschrieben. In der offiziellen Problembeschreibung [14] findet sich auch die Einordnung des Graphenisomorphieproblems (GI): „There are interesting examples of NP problems not known to be either in Por NP-complete. One example is the graph isomorphism problem: Given two undirected graphs, determine whether they are isomorphic.“ Diese Eigenschaft der Graphenisomorphie wird auch in [71] behandelt. Für lineare Codes definieren wir analog zur Graphenisomorphie folgende Entscheidungsprobleme in Abhängigkeit von dem Kettenring Rund des gewählten Isometriebegriffs: PCER: Sind Γund Γ0Generatormatrizen R-linearer Codes, entscheide ob der von Γ erzeugte Code permutationsisometrisch zu dem von Γ0erzeugten Code ist. LCER: Sind Γund Γ0Generatormatrizen R-linearer Codes, entscheide ob der von Γ erzeugte Code linear isometrisch zu dem von Γ0erzeugten Code ist. SCER: Sind Γund Γ0Generatormatrizen R-linearer Codes, entscheide ob der von Γ erzeugte Code semilinear isometrisch zu dem von Γ0erzeugten Code ist. 4http://www.claymath.org 23 2. Grundlagen Wenige Arbeiten untersuchen die Komplexität der oben definierten Probleme aus der Codierungstheorie. In [62] liefern Petrank und Roth zunächst einen Beweis für die Tatsache, dass – unter einer vermutlich gültigen Annahme über die Struktur der Komplexitätsklassen – das von ihnen definierte Entscheidungsproblem „Code Equivalence“ (= Vereinigung aller PCEFqfür alle endlichen Körper Fq) nicht in die Klasse der NPvollständigen Probleme einzuordnen ist: „It is believed that the polynomial-time hierarchy does not collapse, and thus we end up with the conclusion that Code Equivalence is unlikely to be NPcomplete.“ Eine ähnliche Schlussfolgerung findet sich auch in [71] für das Graphenisomorphieproblem. Andererseits geben die Autoren in [62] aber auch einen Hinweis darauf, dass es sich um ein nicht allzu einfaches Problem handeln kann: „Yet, we do state also a negative result, namely, that Code Equivalence is also unlikely to be too easy. We do this by relating Code Equivalence to the Graph Isomorphism problem. [...] The problem of deciding efficiently (i.e., in polynomial time) whether two graphs are isomorphic is a notoriously open question in Computer Science. The problem has been studied extensively in recent decades, but the state of the art is that there is no known efficient algorithm for determining whether two given graphs are isomorphic.“ Da Petrank und Roth die Graphenisomorphie nur über eine Polynomialzeitreduktion auf PCEF2zurückführen, ließe sich durchaus argumentieren, dass das Problem PCEFq für einen anderen endlichen Körper Fq, q > 2möglicherweise leichter zu beantworten ist. Hierzu liefert jedoch [34] einen analoge Polynomialzeitreduktion des Graphenisomorphieproblems auf PCEFq. Es sei im Folgenden Rein fest vorgegebener Kettenring und es bezeichne Im∈Rm×m die Einheitsmatrix der Dimension m×mzu m∈N. Wir wollen nun das Resultat von [34] nicht nur auf PCERsondern auch auf die Entscheidungsprobleme LCERund SCER verallgemeinern. 2.4.2 Definition. Es sei A∈ {0,1}n×meine Inzidenzmatrix eines Graphen Gmit n Punkten und mKanten. Wir definieren zu Adie Generatormatrix Γ(A):= ImIm1m×1A∈Rm×(2m+n+1) eines linearen Codes C(A)≤R2m+n+1 der Länge 2m+n+ 1. 2.4.3 Hilfssatz. Γ(A)ist bis auf Zeilenvertauschungen und -skalierungen mit Einheiten die eindeutige Generatormatrix von C(A), welche folgende Eigenschaften erfüllt: ∀v∈Rm: wH(v) = 1 ⇐⇒ wHvΓ(A)= 5 (2.2) 24 2.4. Komplexität der Probleme Beweis. Zunächst zeigen wir, dass Γ(A)die Bedingung (2.2) erfüllt: Sei v∈Rmbeliebig. Ist wH(v) = 1 so ist vΓ(A)ein Vielfaches einer Zeile von Γ(A)und somit wHvΓ(A)= 2+1+2 = 5. Ansonsten erhalten wir für das Hamming-Gewicht die folgende Abschätzung wHvΓ(A)≥2 wH(v)+wH(vA)≥(4+2,falls wH(v)=2 6,falls wH(v)≥3. Ist Γ0eine weitere Generatormatrix von C(A)mit der Eigenschaft (2.2), so ist Γ0=BΓ(A) für ein B∈GLm(R). Für die i-te Zeile Bi,∗,i∈[m], von Bgilt nun aber wHBi,∗Γ(A)= wHΓ0 i,∗= 5 und somit wH(Bi,∗) = 1. Damit ist Baber wegen seiner Invertierbarkeit zwingend das Produkt einer Permutationsmatrix und einer invertierbaren Diagonalmatrix. 2.4.4 Satz. GI besitzt eine Polynomialzeitreduktion auf SCER. Beweis. Wir zeigen, dass zwei gegebene Inzidenzmatrizen A0und A1genau dann isomorphe Graphen darstellen, wenn die Generatormatrizen Γ(A0)und Γ(A1)semilinear isometrische Codes erzeugen. Diese Reduktion ist offensichtlich in Polynomialzeit zu berechnen. Zunächst gehen wir davon aus, dass die Inzidenzmatrizen A0und A1isomorphe Graphen darstellen. Es existieren also Permutationen π∈Smund σ∈Snmit A1= P(π)A0P(σ−1). Dann ist aber P(π)Γ(A0) P(π−1) P(π−1) 1 P(σ−1)!= Γ(A1) und damit erzeugen Γ(A0)und Γ(A1)permutationsisometrische Codes. Für die Rückrichtung nehmen wir an, dass die Codes C(A0)und C(A1)semilinear isometrisch sind. Dann existiert eine Matrix B∈GLm(R)und ein Gruppenelement (ϕ;α, σ)∈(R∗)2m+n+1 o(Aut(R)×S2m+n+1) mit Γ(A1)=B(ϕ;α, σ)Γ(A0)=BαΓ(A0)P(σ−1)diag(ϕ)−1=BΓ(A0)P(σ−1)diag(ϕ)−1. Die Matrix Γ(A0)P(σ−1)diag(ϕ)−1ist eine Generatormatrix zu C(A1)mit der Eigenschaft (2.2). Daraus folgt nun mit dem Hilfssatz, dass B=P(π)diag(ψ)das Produkt einer Permutationsmatrix P(π)∈Rm×mund einer invertierbaren Diagonalmatrix diag(ψ)∈ Rm×mist. Der Einsvektor Γ(A1)∗,2m=1m×1sorgt nun dafür, dass diag(ψ)konstant auf der Diagonalen ist, also diag(ψ) = rImfür ein r∈R∗gilt. Damit erhalten wir Γ(A1)=r·P(π)Γ(A0)P(σ−1)diag(ϕ)−1. 25 2. Grundlagen Da P(π)Γ(A0)P(σ−1)und Γ(A1)nur Einträge aus {0R,1R}besitzen, können wir ohne Beschränkung der Allgemeinheit5diag(ϕ) = rImannehmen. Somit haben wir eine Gleichung der Gestalt Γ(A1)=P(π)Γ(A0)P(σ−1) erreicht. Die R-linearen Codes C(A0)und C(A1)sind also auch permutationsisometrisch. Unter Berücksichtigung der Automorphismen6von C(A0)können wir weiter annehmen, dass σdie Koordinaten {0, . . . , m−1},{m, . . . , 2m−1},{2m}und {2m+1,...,2m+n} mengenweise fix lässt. Unter dieser Voraussetzung ist dann Γ(A1)=P(π)Γ(A0) P(π−1) P(π−1) 1 P(ρ−1)! für eine Permutation ρ∈Sn. Es ist also A1=P(π)A0P(ρ−1)und damit sind A0und A1 Inzidenzmatrizen von isomorphen Graphen. 2.4.5 Folgerung. Für einen beliebigen endlichen Kettenring Rbesitzt GI eine Polynomialzeitreduktion sowohl auf PCERals auch auf LCER. Beweis. Eine zentrale Aussage des Beweises zum vorausgegangenen Satz ist, dass die von Γ(A0)und Γ(A1)erzeugten R-linearen Codes C(A0)und C(A1)genau dann semilinear isometrisch sind, wenn sie auch permutationsisometrisch bzw. linear isometrisch sind. A0und A1sind also genau dann Inzidenzmatrizen von isomorphen Graphen, wenn C(A0)und C(A1)permutationsisometrisch bzw. linear isometrisch sind. Damit haben wir gezeigt, dass die Isomorphieprobleme für lineare Codes über endlichen Kettenringen mindestens genauso schwer sind wie das Graphenisomorphieproblem. Die oben eingeführten Komplexitätsklassen machen Aussagen über die worst-caseLaufzeiten der Probleme. Ein Problem liegt nicht in P, sobald es zu jedem Polynom p∈R[x]eine nicht leere Teilmenge der erlaubten Eingaben gibt, welche für das exponentielle Laufzeitverhalten verantwortlich ist. Es ist also weiterhin durchaus möglich, dass für fast alle Eingaben die Anzahl der Rechenschritte durch das Polynom pnach oben beschränkt ist. Daher möchten wir im Folgenden auch kurz auf die durchschnittliche Komplexität der Probleme eingehen. Mit Hilfe des Support-Splitting-Algorithmus [66] wird in [61] bewiesen, dass für einen beliebigen Körper Fqdie Probleme PCEFqfür fast alle Eingaben in Polynomialzeit gelöst werden können. Für die Körper F3und F4wird in [67] ein ähnliches Resultat für die Problemstellungen LCEF3,LCEF4und SCEF4erreicht. Gleichzeitig geben die Autoren N. Sendrier und D. Simos aber auch eine Vermutung über die Körper Fq, q ≥5ab: 5Nullspalten müssen berücksichtigt werden, d.h. isolierte Knoten des Graphen. Diese können aber mit beliebigen Einheiten multipliziert werden, ohne den Code C(A0)zu ändern. 6Es können weitere Einheitsvektoren oder Einsvektoren in der Matrix A0enthalten sein. 26 2.4. Komplexität der Probleme 2.4.6 Vermutung (aus [67]).Zu gegebenem q≥5sind die Probleme LCEFqund SCEFq für fast alle Eingaben schwer7. Aus der Reduktion auf das Graphenisomorphieproblem schließen wir, dass es vermutlich zu jeder deterministischen Turingmaschine zur Lösung von SCERund zu jedem Polynom p∈R[X]ein Paar von Generatormatrizen (Γ0,Γ1)mit Eingabelänge ngibt, so dass die Maschine mehr als p(n)Rechenschritte zur Beantwortung benötigt. Falls sich die Vermutung 2.4.6 für die Körper Fq, q ≥5bzw. auch für beliebige Kettenringe Rbewahrheitet, ist sogar davon auszugehen, dass fast alle Eingaben (Γ0,Γ1)dieses Verhalten zeigen. Insbesondere vermuten wir auch, dass sich gerade die für die Codierungstheorie interessanten Codes in dieser Hinsicht ungünstig verhalten werden. Wir können also nicht davon ausgehen, einen Kanonisierer zu entwickeln, welcher in der Lage ist, die kanonische Form einer beliebigen Generatormatrix in Polynomialzeit in der Länge der Eingabe zu berechnen. Die Vermutung 2.4.6 rechtfertigt unser weiteres Vorgehen, einen Algorithmus zu entwickeln, welcher stets für alle Eingaben mit exponentieller Laufzeit arbeitet. Da die Komplexitätstheorie uns also kein Maß für die Bewertung des Algorithmus an die Hand gibt, können wir uns nur mit den wenigen konkurrierenden Systemen für lineare Codes über endlichen Körpern vergleichen. Für beliebige Kettenringe können wir die Güte des Algorithmus nur über seine praktische Anwendbarkeit auf gewisse interessante Probleminstanzen verifizieren, siehe Kapitel 6. 7Fast alle Eingaben werden von einem Lösungsalgorithmus mit exponentiellen Aufwand bearbeitet. 27 3. Kanonisierungsalgorithmen Zunächst sei Geine beliebige endliche Gruppe, welche auf einer endlichen Menge X operiere. Die Operation sei ohne Beschränkung der Allgemeinheit treu, d.h. der Kern N:= ∩x∈XStabG(x)der Gruppenoperation ist trivial. Liegt diese Situation nicht vor, so ist Nein Normalteiler in Gund wir können stattdessen auch die induzierte1Gruppenoperation von G/N auf Xuntersuchen. Außerdem wollen wir auf Ximmer eine gegebene Totalordnung voraussetzen. Zur Kanonisierung des vorliegenden kombinatorischen Objekts x∈Xunter der Operation von Gwerden wir die Prinzipien des Verfeinerns und Individualisierens von Partitionen (partition refinement, individualization) entwickeln. Diese algorithmische Grundidee bildet die Basis zur Definition eines Suchbaums, mit dessen Hilfe der kanonische Repräsentant und die Automorphismengruppe von xbestimmt werden können. Laut einer Aussage in [56] trat diese Strategie erstmals in [63] im Zusammenhang mit der Isomorphieerkennung bei Graphen auf. Auch alle gegenwärtigen (wettbewerbsfähigen) Algorithmen zur Berechnung eines kanonischen Repräsentanten eines Graphen basieren immer noch auf dieser Grundlage. In [56] wird hierzu eine detaillierte Laufzeitanalyse der wichtigsten Implementierungen vorgenommen. Die in Abschnitt 3.2 beschriebene Formulierung ist zunächst eine Verallgemeinerung des Graphenkanonisierers [55]. Sie kombiniert die zeitgleich erschienenen Diskussionen aus [35] und [42] und ergänzt diese mit eigenen Ideen. Wir gehen wie folgt vor: Zunächst beschreiben wir in Abschnitt 3.1 einige grundlegende Ideen, die wir bei der Entwicklung eines Kanonisierers einbringen können. Dies folgt im Wesentlichen der Beschreibung aus [35]. Der Autor R. Gugisch baut aus diesen Einzelkomponenten den Kanonisierer aus Abschnitt 3.2 für die Operation GX„von unten“ auf. Nachteil dieser Herangehensweise ist aber, dass der Korrektheitsbeweis für den Gesamtalgorithmus mit allen zusätzlichen Modifikationen schwer zu führen ist. Daher übernehmen wir diesen Teil aus [42]. In dieser Beschreibung, siehe Abschnitt 3.2, wird größerer Wert auf das Gesamtbild gelegt, ohne zu sehr im Detail zu versinken. Mit diesem Blick „von oben“ wird die Korrektheit des Vorgehens sofort offensichtlich. Im Anschluss modifizieren wir diese Beschreibung aus [42] über mehrere Schritte hinweg derart, dass die Korrektheit weiterhin leicht ersichtlich bleibt und die Formulierung auch zu einem praxistauglichen Kanonisierer führt. Zum Beispiel beschreiben wir, wie man die Automorphismen des zu kanonisierenden Objekts x∈Xzur Verbesserung des Laufzeitverhaltens einbringen kann. 1gNx := gx. 29 3. Kanonisierungsalgorithmen Gruppe G≃(G×Sn)/Snauf der Menge Sn\\Xn. Eine Bahn Sn(x0, . . . , xn−1)∈ Sn\\Xnkönnen wir aber eineindeutig mit dem Inhalt des Vektors beschreiben, d.h. über eine Aufzählung {{x0, . . . , xn−1}} aller Einträge in ihrer Vielfachheit, die keinen Wert auf die Reihenfolge legt. Eine solche Struktur bezeichnen wir als Multimenge und wir notieren diese mit doppelt geschweiften Klammern, um sie von gewöhnlichen Mengen zu unterscheiden. Somit haben wir einen alternativen Ansatz zur Kanonisierung von n-elementigen (Multi-)Mengen unter der Operation von Ggegeben. Da die Darstellung einer (Multi-)Menge ohnehin innerhalb des Computers über eine geeignete Anordnung der Elemente realisiert werden muss, macht es überdies Sinn, diese zusätzliche algebraische Struktur über die Gruppenoperation mit Snin dem Algorithmenentwurf zu berücksichtigen. Den Kanonisierer CanX G×Snaus dem letzten Beispiel kann man wiederum über das Aufspalten zu dem Homomorphismus ((g, π)7→ g, x 7→ Gx)gewinnen. Wir bezeichnen mit Mn(X)die Menge aller n-elementigen Multimengen einer Menge X. Es ergibt sich folgendes Bild von Homomorphismen von Gruppenoperationen und die Möglichkeit zur Definition von Kanonisierern: Sn(G\\Xn)π←[(g,π) ←−−−−− Gx←[xG×SnXn(g,π)7→g −−−−→ x7→SnxG(Sn\\Xn)≃G(Mn(X)) CanG\\Xn Sn Aufspalten −−−−−−→ CanXn G×Sn Verschmelzen −−−−−−−→ CanSn\\Xn G Dieses Beispiel dient uns zur Motivation des weiteren Vorgehens, jedoch sei darauf hingewiesen, dass in diesem Spezialfall die Bahnenmengen G\\(Sn\\Xn),(G×Sn)\\Xnund Sn\\(G\\Xn)ohnehin in Bijektion stehen, d.h. keine Aufspaltungen und Verschmelzungen im eigentlichen Sinne stattfinden. Es handelt sich hierbei um äquivalente Formulierungen des gleichen Problems. Schließlich möchten wir noch darauf hinweisen, dass wir tatsächlich die Kanonisierung zu Gruppenoperationen von Gruppen GoSnauf Mengen Xnzum Ziel haben werden. Da GGoSnweiterhin Normalteiler ist, ist die Gewinnung des Kanonisierers CanXn GoSn aus CanG\\Xn Snüber das Aufspalten weiterhin möglich. Der Übergang zu einer Operation von Gauf Sn\\Xnist aber, wegen der fehlenden Normalteilereigenschaft von Sn, nicht ohne weitere Voraussetzungen möglich. In den von uns zu untersuchenden Situationen (z.B. semilineare Isometrie von linearen Codes) ist die Gruppe Gjedoch selbst ein semidirektes Produkt HnoG0mit folgenden Annahmen: •Die symmetrische Gruppe operiert auf HnoG0nur über eine Permutation der Komponente Hn, d.h. (HnoG0)oSn=Hno(G0×Sn). •Die Gruppe G0operiert simultan auf allen Komponenten von Xnund die Gruppe Hnkomponentenweise. 36 3.1. Grundbausteine der Kanonisierung Dann können wir zunächst den Normalteiler HnoSnheraus teilen und erhalten damit eine Operation von G0auf (HnoSn)\\Xn. Diese Menge können wir aber als Sn\\(Hn\\Xn) = Mn(H\\X)interpretieren. 3.1.9 Beispiel. Die Gruppe (GLk(R)×(R∗)n)o(Aut(R)×Sn) operiert auf der Menge Rk×naller k×n-Matrizen. Wir setzen H:= R∗und G0:= ΓLk(R) = (GLk(R)oAut(R)). Damit erhalten wir also eine Operation der Gruppe ΓLk(R)auf Mn(R∗\\Rk R), via (A, α)· {{R∗? x0, . . . , R∗? xn−1}} := {{R∗? Aα(x0), . . . , R∗? Aα(xn−1)}}. Für ein v∈Rk Rkönnen wir die Bahn R∗? v ={vϕ−1|ϕ∈R∗}aber gerade mit dem zyklischen Rechtsmodul vR identifizieren. 3.1.10 Folgerung. Zwei Generatormatrizen Γ,Γ0∈Rk×n,(m,...,m)erzeugen genau dann semilinear isometrische Codes, wenn die Multimengen {{Γ∗,iR|i∈[n]}} und {{Γ0 ∗,iR|i∈[n]}} der von den Spalten erzeugten zyklischen R-Rechtsmoduln unter der Gruppenoperation von ΓLk(R)isomorph sind. Damit haben wir ein weiteres Theorem aus [52] auf R-lineare Codes erweitert und den wohlbekannten Zusammenhang zwischen dem Äquivalenzbegriff der Codierungstheorie und dem der projektiven Geometrie hergestellt. Dieser Zusammenhang wird etwa in [37, 45, 73] und vielen weiteren Arbeiten zur Konstruktion von guten linearen Codes aus Punktkonfigurationen der projektiven Rechts-Hjelmslev-Geometrie ausgenutzt, siehe auch Kapitel 6.1. Gleichartig verhält es sich, wenn wir in der projektiven Geometrie von den eindimensionalen Unterräumen (=Punkten) zu r-dimensionalen Unterräumen übergehen. Dies wird uns eine Bijektion der Äquivalenzklassen von Network-Codes über Fqund den Äquivalenzklassen von Fq-linearen Codes über dem Alphabet Fqrliefern, siehe Kapitel 6.3. 3.1.2. Kanonisierung über Untergruppen Nicht immer ist es möglich, einen leicht zu berechnenden G-Homomorphismus fanzugeben, für den die Kanonisierung im Bildbereich effizient zu implementieren ist. Zumeist liegt für diesen dann die Situation vor, dass StabG(f(x)) gleich Gist und somit keine Information gewonnen werden kann. Wir wollen nun zeigen, wie sich das Auftreten dieser Situation umgehen lässt. 37 3. Kanonisierungsalgorithmen Zunächst nehmen wir an, es sei eine Untergruppe Uvon Ggegeben, für die wir bereits einen effizienten Kanonisierer CanUentwickelt haben. Des Weiteren benötigen wir für unser Vorgehen eine Transversale Tder Rechtsnebenklassen U\G. Dann können wir den Kanonisierer CanG= (CFG,TRG,StabG)wie folgt definieren: •Zu einem gegebenen x∈Xberechne CFG(x) := mint∈TCFU(tx)und speichere in T0diejenigen Transversalenelemente, welche zum Minimum führen; •setze TRG(x) := TRU(t0x)t0für ein t0∈T0; •erzeuge den Stabilisator StabG(x)über t−1 0StabU(t0x)t0und {TRG(x)−1TRU(tx)t|t∈T0} Wir bezeichnen dieses Vorgehen als das Heben eines Kanonisierers für die Operation mit Uzu einem Kanonisierer für G. Im Wesentlichen zerlegen wir das Problem also in |U\G|=|G| |U|Teilprobleme in der Hoffnung, dass diese einfacher zu lösen sind. Wir können dieses Vorgehen zum Beispiel dann einsetzen, wenn wir keinen geeigneten G-Homomorphismus für die Anwendung des Homomorphieprinzips angeben können, jedoch sehr wohl einen U-Homomorphismus zur Verfügung haben. 3.1.11 Beispiel. Es sei der folgende Graph Γ = ([8], E)gegeben: 0 1 2 3 4 5 6 7 Für diesen Graph ist offensichtlich der Zykel (0,1,2,...,7) ∈S8ein Automorphismus. Somit werden wir die Knoten durch Anwendung eines beliebigen S8-Homomorphismus nicht unterscheiden können. Zerlegen wir jedoch das Problem mit Hilfe der Untergruppe U= StabS8(0), so brechen wir die Symmetrie und wir können einen effizienteren Kanonisierer für Uüber den U-Homomorphismus f: [2]([8] 2)→N8, E 7→ (Länge eines kürzesten Pfades in Evon inach 0)i∈[8] entwerfen. Wir erhalten dann f(Γ) = (0,1,2,3,4,3,2,1). Bei der Anwendung des Homomorphieprinzips sortieren wir diesen Vektor lexikographisch aufsteigend, etwa über die Anwendung der Permutation π= (2,3,6,4,7). Anschließend wenden wir diese Permutation auch auf Γan und schränken uns im weiteren Verlauf auf den Stabilisator U0= StabU((0,1,1,2,2,3,3,4)) = h(1,2),(3,4),(5,6)i 38 3.2. Partitionen und Verfeinerungen des kanonischen Repräsentanten f(πΓ) = (0,1,1,2,2,3,3,4) ein. Es ist leicht einzusehen, dass die kanonischen Repräsentanten CFU(tΓ) für alle Rechtstransversalenelemente t∈Tvon U\Gin diesem Beispiel identisch sind. Über dieses Vorgehen werden wir also maximal |T| · StabU(f(tx)) = 8 ·8 = 64 Permutationen untersuchen. Ein weiterer solcher Schritt mit der Untergruppe StabU0(1) in der Kanonisierung für Ureduziert in diesem Beispiel die Anzahl der zu betrachtenden Permutationen sogar auf die Mächtigkeit 16 der Automorphismengruppe. 3.2. Partitionen und Verfeinerungen In diesem Abschnitt wollen wir nun aufzeigen, wie wir die vorangegangenen Ideen zur Definition eines effizienten Kanonisierers zusammenfügen. Wir werden dazu einen Backtrack-Algorithmus zum systematischen Durchlauf der Gruppe Gformulieren. Das Vorgehen lässt sich für ein x∈Xam besten über die Definition eines zugehörigen Suchbaums T(x, G)analog zu [42] beschreiben. Wieder sei mit L(G)die Menge aller Untergruppen von Gbezeichnet und mit C(G)die Menge aller Rechtsnebenklassen aller Untergruppen Hvon G. Die Knoten des Suchbaums T(x, G)werden von einer Teilmenge der Rechtsnebenklassen Hg ∈ C(G)gebildet. Die Untergruppe Hrepräsentiert dabei genau diejenigen Gruppenelemente, welche wir in dieser Phase des Algorithmus noch zur Anwendung bringen wollen. Das Gruppenelement gwurde an dieser Stelle bereits auf xangewandt. Der Baum selbst beziehungsweise der Ablauf des Algorithmus wird induktiv über die folgenden Basisoperationen definiert: Partitionierung Die Nebenklasse Hg mit |H|>1wird zerlegt in eine disjunkte Menge von Nebenklassen {H0h0g, . . . , H0hu−1g}einer echten Untergruppe H0< H. Die Menge {h0, . . . , hu−1}sei dabei eine beliebige Rechtstransversale von H0in H. Dieses Vorgehen haben wir oben als das Heben eines Kanonisierers für die Operation mit der Untergruppe H0zu einem Kanonisierer für die Operation mit H beschrieben. Offensichtlich lässt sich diese Operation bereits durch Angabe der Untergruppe H0 eindeutig beschreiben. Um gleiche Resultate bei isomorphen Eingaben garantieren zu können, setzen wir voraus, dass diese Operation über die Bereitstellung einer G-Invarianten I:X× C(G)→ L(G),(x, Hg)7→ H0mit H0< H (3.1) eindeutig bestimmt ist. Dabei ist die Operation von Gauf dem Definitionsbereich X× C(G)über die Definition g0?(x, Hg) := (g0x, Hgg−1 0)für alle g0∈G, (x, Hg)∈X× C(G) gegeben. 39 3. Kanonisierungsalgorithmen Verfeinerung Unter einer Verfeinerung verstehen wir das Ersetzen einer Nebenklasse Hg durch eine Teilmenge H0hg mit H0≤Hund h∈H. Auch diese Vorgehen kann mit Hilfe eines G-Homomorphismus V:X× C(G)→ C(G),(x, Hg)7→ (H0hg)mit H0≤Hund h∈H(3.2) beschrieben werden. Wie wir später zeigen werden, erhalten wir Verfeinerungen über die Anwendung des Homomorphieprinzips. Es lässt sich leicht verifizieren, dass die Bedingungen, welche in [42] an diese Basisoperationen gestellt werden, äquivalent zu unserer Forderung der G-Invarianz bzw. G-Homomorphie der Funktionen Iund Vsind. Nun können wir den eigentlichen Aufbau des Suchbaums T(x, G)beschreiben: 3.2.1 Definition. Es sei x∈Xbeliebig. Wir definieren einen Wurzelbaum T(x, G) induktiv wie folgt: 1. Die Wurzel des Baums T(x, G)wird von der Verfeinerung V(x, G)gebildet. 2. Für einen Knoten Hg mit |H|>1sei H0:= I(x, G)und {h0, . . . , hu−1}eine Rechtstransversale von H0in H. Die Kinder {V(x, H0h0g), . . . , V (x, H0hu−1g)}von Hg werden dann über die Verfeinerung der Partitionierung definiert. 3.2.2 Fakt ([42], Theorem 5.30).Für x∈Xund g0∈Ginduziert die Gruppenoperation von Gauf C(G)einen Isomorphismus der Suchbäume T(x, G)und T(g0x, G), d.h. •die Wurzel von T(g0x, G)ist g0? V (x, G) = V(x, G)g−1 0, •Hg ∈ C(G)ist genau dann ein Knoten von T(x, G), wenn Hgg−1 0ein Knoten in T(g0x, G)ist und •{H0hg, Hg}ist genau dann eine Kante in T(x, G), wenn {H0hgg−1 0, Hgg−1 0}eine Kante in T(g0x, G)ist. Eine eingängige Visualisierung dieses Theorems zeigt Abbildung 3.4. Aufgrund unserer Definition werden die Blattknoten von T(x, G)von einelementigen Mengen {g}mit g∈Ggebildet. Wir wollen die Menge dieser Gruppenelemente mit L(x, G) := {g∈G| {g}Blatt in T(x, G)} ⊆ G bezeichnen. 3.2.3 Folgerung. Die Abbildung x7→ {gx |g∈L(x, G)}ist G-invariant. Insbesondere definiert also die Zuordnung CFG(x) := min{gx |g∈L(x, G)}einen kanonischen Repräsentanten für x∈X. 40 3.2. Partitionen und Verfeinerungen R(x, G) Hg H′hg R(x, G)g−1 0 Hgg−1 0 H′hgg−1 0 g0∈G T(x, G)T(g0x, G) Abbildung 3.4.: Illustration von Fakt 3.2.2, siehe auch [42, Figure 5.3] Beweis. Ist g0∈Gbeliebig, so ist nach Fakt 3.2.2 die Menge der Blattknoten von T(g0x, G)bestimmt durch Rechtsmultiplikation der Blätter von T(x, G)mit g−1 0. Es ist also L(g0x, G) = L(x, G)g−1 0und somit {gx |g∈L(x, G)}={gg−1 0g0x|g∈L(x, G)}={g0g0x|g0∈L(g0x, G)}. Damit haben wir die G-Invarianz gezeigt und somit auch, dass die Funktion CFG(x) := min{gx |g∈L(x, G)}eine Kanonisierung definiert. Wir werden im Folgenden zu x∈Xmit L0(x, G) := {g∈L(x, G)|gx = CFG(x)} die Menge aller Transporterelemente bezeichnen. Entscheidend für die Laufzeit des Algorithmus ist nun die Frage, wie wir möglichst viele Äste des Suchbaums T(x, G)abschneiden können, ohne wesentliche Informationen zu verlieren. Zum einen können wir bekannte Automorphismen A≤StabG(x)des Objekts xausnutzen, da es offensichtlich genügt, eine Transversale von L0(x, G)/A zu untersuchen. Eine Diskussion dieser Methode findet sich im Abschnitt 3.2.2. Zunächst wollen wir uns aber der Frage: „Ist L0(x, G)∩Hg =∅für einen Knoten Hg von T(x, G)?“ zuwenden. Offensichtlich können wir – für eine beliebig gewählte Totalordnung (X, ≤)– dies nur dann entscheiden, falls wir CFG(x)und Hgx bereits kennen. Nun erfolgte aber die Wahl der Totalordnung auf Xzur Definition des Minimums in Folgerung 3.2.3 willkürlich. Wir werden also versuchen diese Wahl unserem Problem anzupassen, d.h. wir wollen eine Totalordnung wählen, welche einen effizienten Test auf L0(x, G)∩Hg =∅ermöglicht. Dazu beobachten wir zunächst, dass wir die Verfeinerung V:X× C(G)→ C(G)auch als Anwendung des Homomorphieprinzips sehen können. 41 3. Kanonisierungsalgorithmen 3.2.4 Satz. Für alle H∈ L(G)sei ein H-Homomorphismus fH:X7→ Ygegeben sowie ein Kanonisierer y7→ (CFH(y),TRH(y),StabH(y)). Dann ist V:X× C(G)→ C(G),(x, Hg)7→ StabH(CFH(fH(gx))) TRH(fH(gx))g(3.3) ein G-Homomorphismus und erfüllt somit die Bedingungen an eine Verfeinerung. Beweis. Zunächst zeigen wir die Wohldefiniertheit der Abbildungsvorschrift: Sind g, g0∈ Gverschiedene Nebenklassenrepräsentanten von Hg, etwa hg =g0für ein h∈H, so gilt TRH(fH(gx)) | {z } =:h fH(gx) = CFH(fH(gx)) = CFH(fH(g0x)) = TRH(fH(g0x)) | {z } =:h0 fH(g0x), denn fH(gx)und fH(g0x) = hfH(gx)liegen in der gleichen H-Bahn. Wir folgern hieraus, dass H:= StabH(CFH(fH(gx))) unabhängig von dem Nebenklassenrepräsentanten gist. Es bleibt zu zeigen, dass Hh0g0=Hhg ist. Wir zeigen hierzu h0hh−1∈H: h0hh−1CFH(fH(gx)) = h0hh−1hfH(gx) = h0fH(hgx) = h0fH(g0x) = CFH(fH(g0x)) = CFH(fH(gx)) Die Behauptung über die G-Homomorphie der Abbildung Vbeweist man folgendermaßen: Es seien g0∈Gund (x, Hg)∈ C(G)beliebig. Dann gilt: V(g0?(x, Hg)) = V(g0x, Hgg−1 0) = StabHCFH(fH(gg−1 0g0x))TRH(fH(gg−1 0g0x))gg−1 0 =V(x, Hg)g−1 0=g0? V (x, Hg) Im Folgenden setzen wir voraus, dass die Verfeinerung Vüber eine feste Wahl einer Familie (fH)H∈L(G)von H-Homomorphismen definiert sei. Dabei sei ohne Beschränkung der Allgemeinheit die Menge Ytotalgeordnet3. Über die H-Homomorphismen können wir dann induktiv eine Bewertung B(x, Hg) auf den Knoten des Suchbaums T(x, G)einführen: 1. Die Wurzel Hg =V(x, G)sei mit B(x, Hg)=(fG(gx)) bewertet. 2. Ist H0hg ein Knoten der Tiefe i > 0im Baum T(x, Hg)mit Vater Hg und Bewertung B(x, Hg) = (y0, . . . , yi−1), so definieren wir B(x, H0hg) := (y0, . . . , yi−1, fI(x,Hg)(hgx)). 3. Ist {g}ein Blattknoten, so modifizieren wir dessen aktuelle Bewertung durch das zusätzliche Anfügen von gx. 3Dies können wir immer erreichen, da wir Y=SH∈L(G)fH(X)als endliche Vereinigung endlicher Mengen wählen können. 42 3.2. Partitionen und Verfeinerungen 3.2.5 Hilfssatz. Ist Hg ein Knoten in T(x, G)mit Bewertung B(x, Hg)und g0∈Gbeliebig, so trägt der Knoten Hgg−1 0in T(g0x, G)eine identische Bewertung B(g0x, Hgg−1 0) =B(x, Hg). Beweis. Ist g0∈Gbeliebig und H0hgg−1 0ein Knoten in T(g0x, G), dann ist über eine Induktion über die Tiefe der Knoten leicht zu beweisen, dass die Bewertungsvektoren B(g0x, H0hgg−1 0)und B(x, H0hg)übereinstimmen: Im Induktionsschritt schließt man aus der G-Invarianz von Izunächst, dass H:= I(x, Hg) = I(g0x, Hgg−1 0)gelten muss. Damit ist aber offensichtlich die Gleichheit von fH(hgg−1 0g0x) = fH(hgx)stets gegeben. Ist H0hg ={hg}überdies ein Blatt, so ist auch dort die angefügte Bewertung hgg−1 0g0x=hgx identisch. 3.2.6 Folgerung. Ist g0∈StabG(x)und {g}ein Blatt von T(x, G), so ist {gg0}ebenfalls ein Blatt von T(x, G)mit Bewertung B(x, {gg0}) = B(x, {g}). Beweis. Es definiert g−1 0∈StabG(x)einen Automorphismus von T(x, G). Nach dem vorangegangenen Hilfssatz ist somit {gg0}ebenfalls ein Blatt von T(x, G) = T(g−1 0x, G) mit einer identischen Bewertung. Durch die Blätter {g}von T(x, G)erhalten wir über den lexikographischen Vergleich der Bewertung B(x, {g})eine wohldefinierte Totalordnung auf der Teilmenge {gx |g∈L(x, G)}der Bahn Gx. Wir können diese zur Minimumbildung und damit zur eindeutigen Festlegung eines kanonischen Repräsentanten heranziehen. Diese Ordnung auf Xhat nun den Vorteil, dass wir bereits beim Durchlauf des Suchbaums nicht optimale Äste erkennen und abschneiden können: 3.2.7 Folgerung. Es seien Hg und H0g0Knoten der gleichen Tiefe ides Suchbaums T(x, G). Dann gilt B(x, Hg)< B(x, H0g0) =⇒H0g0∩L0(x, G) = ∅. Zusammenfassend erhalten wir also den folgenden Kanonisierer CanGfür die Gruppenoperation von Gzu einer Eingabe x∈X: •Bilde einen Suchbaum T(x, G)über eine fest gewählte Partitionierungsvorschrift Iund Verfeinerung Vunter eventueller Berücksichtigung des Abschneidekriteriums aus Folgerung 3.2.7. (Wir geben hierzu auch eine ausführliche, weiterführende Diskussion in Abschnitt 3.2.3). •Bestimme die Menge L0(x, G) := {g∈L(x, G)|B(x, {g})≤B(x, {g})∀g∈L(x, G)} aller Blätter mit minimaler Bewertung. •Wähle ein Element TRG(x)∈L0(x, G)beliebig. 43 3. Kanonisierungsalgorithmen •Setze CFG(x) := TRG(x)x. •Berechne SG(x) := {TRG(x)−1g|g∈L0(x, G)}. 3.2.8 Satz. Die oben erklärte Funktion CanG:X→X×G× L(G) x7→ (CFG(x),TRG(x), SG(x)) definiert eine Kanonisierung für die Gruppenoperation von Gauf X. Beweis. Die Korrektheit der Aussage zu dem kanonischen Repräsentanten und dem gewählten Transporterelement folgt sofort aus der vorangegangenen Diskussion. Die Menge SG(x)ist offensichtlich eine Teilmenge von StabG(x). Ist umgekehrt g0∈StabG(x)beliebig, so gilt L0(x, G)g−1 0=L0(g0x, G) = L0(x, G). Damit existiert ein Gruppenelement g∈L0(x, G)mit TRG(x) = gg−1 0und es ist g0= TRG(x)−1g∈SG(x). 3.2.1. Zur Kanonizität unter isomorphen Gruppenoperationen Wir wollen nun besprechen, inwieweit der von uns beschriebene Algorithmus zur Kanonisierung von der Darstellung der Gruppenoperation abhängt. Wir betrachten also eine weitere Gruppenoperation von G0auf X0, welche zu der ursprünglichen Operation von Gauf Xisomorph ist, d.h. es gibt einen Gruppenisomorphismus Ψ : G0→G und eine Bijektion Φ : X0→X, welche mit den Gruppenoperationen verträglich sind: Φ(g0x0) = Ψ(g0)Φ(x0)für alle g0∈G0und x0∈X0. Als Motivation dient uns das nachfolgende Beispiel, welches wir in Abschnitt 5.2.3 dann wieder aufgreifen werden. 3.2.9 Beispiel. Wir wollen annehmen, dass wir lineare Codes über isomorphen Kettenringen Rund R0betrachten, die etwa durch den Ringisomorphismus α:R0→R aufeinander übergeführt werden können. Dann entspricht die Abbildung Φder komponentenweise Anwendung von αauf die Vektoren in Rn. Zusammen mit dem Gruppenisomorphismus Ψ : (R0∗)no(Aut(R0)×Sn)→(R∗)no(Aut(R)×Sn) (ϕ;β, π)7→ (α(ϕ); αβα−1, π) erhalten wir dann einen Isomorphismus von Gruppenoperationen. 44 3.2. Partitionen und Verfeinerungen Wir gehen nun zunächst zu der ursprünglichen Definition des Suchbaums zurück und nehmen an, dass die Verfeinerungsfunktion für die isomorphe Operation wie folgt definiert sei: V0:X0× C(G0)→ C(G0),(x0, H0g0)7→ Ψ−1(V(Φ(x0),Ψ(H0g0))).(3.4) Außerdem sei die Partitionierung über I0:X0× C(G0)→ L(G0),(x0, H0g0)7→ Ψ−1(I(Φ(x0),Ψ(H0g0))) (3.5) gegeben. 3.2.10 Hilfssatz. Die Abbildung V0ist ein G0-Homomorphismus. Die Abbildung I0ist eine G0-Invariante. Beweis. Wir zeigen die Aussage exemplarisch für V0. Es sei g0 0∈G0,x0∈X0und H0g0∈ C(G0)beliebig. Dann gilt: V0(g0 0?(x0, H0g0)) = V0(g0 0x0, H0g0g0 0 −1) = Ψ−1V(Φ(g0 0x0),Ψ(H0g0g0 0 −1)) = Ψ−1V(Ψ(g0 0)Φ(x0),Ψ(H0g0)Ψ(g0 0)−1) = Ψ−1(Ψ(g0 0)? V (Φ(x0),Ψ(H0g0))) =g0 0?Ψ−1(V(Φ(x0),Ψ(H0g0))) = g0 0? V 0(x0, H0g0) Ist nun x0∈X0beliebig, so wollen wir mit T0(x0, G0)den über V0und I0definierten Suchbaum zur Kanonisierung von x0∈X0bezeichnen. Dabei wollen wir zunächst das Abschneiden von Teilbäumen über die Bewertungsfunktion noch unberücksichtigt lassen. 3.2.11 Hilfssatz. Die Suchbäume T0(x0, G0)und T(Φ(x0), G)sind isomorph, d.h. •die Wurzel von T(x0, G0)ist Ψ−1(V(Φ(x0), G)), •Ψ−1(Hg)ist genau dann ein Knoten von T(x0, G0), wenn Hg ∈ C(G)ein Knoten von T(Φ(x0), G)ist und •{Ψ−1(H0hg),Ψ−1(Hg)}ist genau dann eine Kante in T(x0, G0), wenn {H0hg, Hg} eine Kante in T(Φ(x0), G)ist. Beweis. Wir führen eine Induktion nach der Tiefe des Knotens Hg im Baum T(Φ(x0), G) durch. Ist der Knoten Hg die Wurzel von T(Φ(x0), G), so gilt Ψ−1(Hg) = Ψ−1(V(Φ(x0), G)) = V0(x0, G0). Damit ist der Induktionsanfang bereits gezeigt. Ist nun Hg ein beliebiger Knoten und H6={1G}, so werden die Kinder von Hg durch einen Partitionierungsschritt und die nachfolgende Verfeinerung gewonnen. Ist Teine 45 3. Kanonisierungsalgorithmen 3.2.26 Hilfssatz. Es sei π∈Snund P:= (P0, . . . , P`−1)eine kanonische Partition zu 0 = n0< n1< . . . < n`=n. Dann gibt es in der Rechtsnebenklasse SPπgenau dann topologische Anordnungen zu einem vollständigen Labelled Branching (([n], E), σ)von A≤Sn, wenn aus (i, j)∈Ebereits FP(π(i)) ≤ FP(π(j)) folgt. Beweis. Zu i∈[n]bezeichne i0:= FP(π(i)) die Farbe des Bilds π(i). Wir nehmen zunächst an, dass π∈Sndie Implikation nicht erfüllt, es also eine Kante (i, j)∈Egibt mit i0=FP(π(i)) >FP(π(j)) = j0. Für eine beliebige Permutation σ∈SPliegen die Bilder σπ(i)∈Pi0bzw. σπ(j)∈Pj0aber in den gleichen Mengen wie π(i)bzw. π(j). Damit ist aber wegen σπ(j)≤nj0+1 −1< ni0≤σπ(i)die Permutation σπ ebenfalls keine topologische Anordnung zu ([n], E). Für die Rückrichtung geben wir eine Permutation σ∈SPan, so dass σπ eine topologische Anordnung zu ([n], E)ist. Wir wählen hierzu σ∈SPderart, dass in jedem Block P`0= [n`0+1]\[n`0],`0∈[`]die Urbilder von σπ lexikographisch angeordnet sind: π−1σ−1(n`0)< . . . < π−1σ−1(n`0+1 −1). Eine solche Permutation existiert, da wir – mit Hilfe der Gruppenoperation von Snauf [n]n– mit der Gruppe SPden Vektor (π−1(0), . . . , π−1(n−1)) = (0, . . . , n −1) ·P(π−1) blockweise lexikographisch sortieren können. Die Einschränkung der Abbildung (σπ)−1 auf einen Block P∈Pist also ordnungserhaltend. Für eine beliebige Kante (i, j)∈E gilt nun entweder •i0< j0und damit ohnehin σπ(i)≤ni0+1 −1< nj0≤σπ(j), •oder es ist i0=j0und damit nach Konstruktion σπ(i)< σπ(j), da für die Urbilder i, j ∈(σπ)−1(Pi0)die Relation i<jgilt. Anhand der Bahnen der Gruppe Hauf [n]für einen Knoten Hg in T(x, G)können wir eine minimale kanonische Young-Untergruppe H≤SPfür diesen Test bestimmen. Wieder lässt sich durch einen Basiswechsel erreichen, dass die Bahnen von HIntervalle bilden. Somit steht die vollständige Information aus dem Hilfssatz zur Verfügung. Wir werden aber im Abschnitt 3.2.4 aufzeigen, dass dies in den von uns betrachteten Fällen bei geeigneter Wahl der Homomorphismen fHund der Partitionierungsvorschrift Inicht notwendig ist, da alle im Backtracking auftretenden Gruppen H≤Snstets kanonische Young-Untergruppen sind. 3.2.3. Implementierungsdetails Der Algorithmus aus Satz 3.2.8 macht noch keine Aussage zum Aufbau des Suchbaums T(x, G). Dies möchten wir – da nun alle erforderlichen Hilfsmittel zur Verfügung stehen – an dieser Stelle nachholen. 52 3.2. Partitionen und Verfeinerungen •Im Rahmen einer Breitensuche kann man über die Bewertungsfunktion Bleicht Teilbäume identifizieren, die nicht zu Elementen g∈L0(x, G)führen. Da wir Automorphismen aber nur über besuchte Blattknoten auffinden werden, bedeutet dies auch, dass wir diese erst im letzten Schritt erreichen werden. Somit kann das Abschneiden nach Hilfssatz 3.2.26 nur sehr eingeschränkt genutzt werden. •Umgekehrt können wir im Rahmen einer Tiefensuche den aktuellen Knoten H0g0 der Tiefe i– wegen der nicht vollständigen Information über die auftretenden Bewertungen – nur dann abschneiden, falls ein anderer, bereits besuchter Knoten Hg der gleichen Tiefe imit kleinerer Bewertung B(x, Hg)< B(x, H0g0)existiert. Man wird also auch Teilbäume untersuchen, deren Blätter nicht in der Menge L0(x, G)liegen. Das zuletzt besuchte Blatt liefert während der Laufzeit immer nur einen Kandidaten für das Transporterelement. Jedoch definieren gleich bewertete Blätter immer einen Automorphismus von x, unabhängig davon ob sie den kanonischen Repräsentanten definieren. Eine stetig wachsende Untergruppe A≤StabG(x)des Stabilisators von xsteht also bereits frühzeitig zur Verfügung, um das Abschneidekriterium aus Hilfssatz 3.2.26 anzuwenden. Außerdem muss im Rahmen einer Tiefensuche immer nur die lokale Information abgespeichert werden, d.h. im wesentlichen die Zustände der Vorfahren zum aktuellen Knoten Hg. Es ist leicht ersichtlich, dass das Laufzeitverhalten eines solchen Algorithmus auch entscheidend von der Tatsache abhängig ist, wann zum ersten mal ein Blatt aus der Menge L0(x, G)erreicht wird. Daher kann es bei verschiedenen isomorphen Eingaben xund x0=g0xzu erheblichen Laufzeitunterschieden kommen. •Eine viel versprechende Kombination beider Ansätze im Bereich der Graphenkanonisierung wird gegenwärtig in [56] diskutiert. Der Baum wird in Breitensuche durchlaufen. Dabei wird jedem auftretenden Knoten Hg ein zufällig gewählter Blattknoten {g0}mit g0∈Hg zugeordnet. Die Autoren nennen diese Zuordnung einen experimentellen Pfad zu einem Blattknoten. Nach dem Abschneiden mittels der Bewertungsfunktion werden zusätzlich noch die Bahnenelemente g0xzu den experimentellen Pfaden gebildet und verglichen. Bei Gleichheit kann der so gefundene Automorphismus zu den Erzeugern der Gruppe Ahinzugefügt werden. •Schließlich möchten wir noch auf das sogenannte Iterative Deepening hinweisen, welches den zu erwartenden hohen Speicherbedarf einer Breitensuche mit dem Einsatz eines höheren Rechenaufwands versucht zu vermeiden. R. Gugisch [35, Seite 87] schreibt hierzu: „Als Lösung bietet sich an, den Baum iterativ mehrmals zu durchlaufen, und in jedem Durchlauf eine Ebene weiter vorzudringen. In Durchlauf i werden also nur die Knoten bis zur Ebene ibesucht und das Optimum [...] bestimmt. So kann man bei den darauf folgenden Durchläufen alle auf Ebene i nicht optimalen Knoten überspringen. 53 3. Kanonisierungsalgorithmen Dieses als Iterative Deepening bekannte Vorgehen benötigt erstaunlicherweise kaum mehr theoretischen Aufwand als eine Breitensuche.“ Bei R. Gugisch werden die Bahnenelemente gx der Nebenklassenvertreter galler Knoten Hg der Tiefe idirekt miteinander verglichen9. Damit reduziert sich der Rechenaufwand – aber auch die Erfolgsaussichten zur Generierung von Automorphismen – natürlich erheblich im Vergleich zu dem Verfahren experimentelle Pfade analog zu [56] zu bestimmen. Eine Kombination beider Ansätze stellt somit eine weitere sehr interessante Strategie dar. Im Weiteren werden wir den Suchbaum immer über eine Tiefensuche aufbauen, da sich eine klassische Breitensuche wegen des benötigten Speicherbedarfs unpraktikabel erweist. Ebenso erschien uns das Iterative Deepening als nicht geeignet, da sich der Aufwand zur Bestimmung der Kinder in unserem Fall wesentlich rechenintensiver als bei [35] gestaltet und außerdem wie bereits besprochen, die Frage nach der Bestimmung der Automorphismen unzureichend beantwortet wurde. Eine Untersuchung der Strategie nach [56] konnte leider aus zeitlichen Gründen nicht mehr umgesetzt werden. 3.2.27 Bemerkung. Möchte man nur die Automorphismengruppe von xbestimmen, so genügt es, die Bewertung des zuerst erreichten Blattknotens {g0}heranzuziehen. Man schneidet dann im Backtrackdurchlauf einen Teilbaum mit Wurzelknoten Hg auf Tiefe i > 0ab, falls B(x, {g0})i6=B(x, Hg)igilt. 3.2.28 Bemerkung. Will man zwei Elemente x, x0∈Xausschließlich auf Isomorphie testen, so kann man die Bewertung eines beliebigen Blattknotens {g0}in T(x, G)als Abschneidekriterium für die Erzeugung von T(x0, G)heranziehen. Man bricht das Backtracking an den Knoten Hg von T(x0, G)auf Tiefe i≥0ab, für welche die Bewertungen B(x0, Hg)inicht mit den entsprechenden Werten B(x, {g0})iübereinstimmen. Erreicht man ein Blatt {g0}, so gilt g0x0=g0xund man kann den Algorithmus mit positiver Antwort sofort beenden. Dringt der Algorithmus nicht bis zu den Blättern von T(x0, G) vor, so liegen die Elemente x, x0in verschiedenen Bahnen Gx 6=Gx0. 3.2.4. Spezialfall: Die Kanonisierung von Graphen Wir wollen nun als Beispiel die Kanonisierung eines Graphen Γ = ([n], E)unter der Operation der symmetrischen Gruppe Snuntersuchen. Insbesondere wollen wir hierbei aufzeigen, dass sich die in der Literatur [41], [55], [56], u.v.m. entworfenen Algorithmen zur Operation der symmetrischen Gruppe Snals Spezialfall des hier dargestellten Algorithmus beschreiben lassen. 9Wir wollen jedoch darauf hinweisen, dass die an dieser Stelle gemachte Aussage [35, Seite 87] „goptx∼i−1gimit a:= g−1 optgi∈G(xi,...,xn−1), so ist a∈Gx“ im Allgemeinen inkorrekt ist. 54 3.2. Partitionen und Verfeinerungen Zunächst stellen wir den Zusammenhang zwischen geordneten Partitionen und Nebenklassen her, da die oben genannten Implementierungen einen Suchbaum aufbauen, dessen Knoten mit geordneten Partitionen beschrieben werden. Zu einer geordnete Partition p= (p0, . . . , p`−1)von [n]sei nun immer P= (P0, . . . , P`−1)diejenige kanonische Partition von [n]für die |pi|=|Pi|,∀i∈[`]gilt. Die geordnete Partition prepräsentiert in den oben genannten Algorithmen die Menge aller Permutationen Sp n:= {π∈Sn|π(pi) = Pi,∀i∈[`]}. Sie lässt sich auch über die Nebenklasse Sp n=SPπ∈ C(Sn)mit π∈Sp nausdrücken. Somit ist also gezeigt, dass die geordnete Partition pnur eine weitere Datenstruktur zur Verwaltung der Nebenklassen SPπdarstellt. Auf der Menge aller Partitionen von [n]lässt sich wie folgt eine Halbordnung definieren: pq:⇐⇒ (∀i, j ∈[n] : Fq(i)<Fq(j) =⇒ Fp(i)<Fp(j)) Sind pund qPartitionen von [n]und p≺q, dann sagen wir pist feiner als qoder p ist eine Verfeinerung von q. Eine Verfeinerung p≺qimpliziert, dass jeder Block von pin einem Block von qenthalten sein muss. Diese Beobachtung ist aber noch nicht hinreichend, es muss zusätzlich auch noch die Anordnung der Blöcke in qberücksichtigt werden. Dies erklärt auch die Wahl des Begriffs „Verfeinerung“ für die in Gleichung (3.2) definierte Basisoperation. Die Partitionierung einer Nebenklasse Sp n=SPπwird in diesen Algorithmen stets über eine sogenannte Individualisierung erreicht. Dazu wählt man einen Block pi∈p mit |pi|>1und definiert das Resultat eines Partitionierungsschritts über die Menge {(p0, . . . , pi−1,{p}, pi\ {p}, pi+1, . . . , p`−1)|p∈pi}, welche alle Möglichkeiten darstellt einen Punkt p∈pivon dem Block piabzutrennen. Der gewählte Index i∈[`]muss, um die Bedingungen an eine Partitionierung zu erfüllen, wieder für isomorphe Eingaben (Γ, Sp n),(π0Γ, Sp nπ−1 0)identisch sein. Man wählt zum Beispiel immer den kleinsten (bzgl. Kardinalität) nicht trivialen Block pimit niedrigstem Index i. In der Sprache aus Gleichung (3.1) führt dies dann zur Definition der Untergruppe I(Γ, SPπ) := StabSP(min(Pi)) < SP. Wir wollen noch etwas näher auf die Verfeinerung eingehen. Im Rahmen der Graphenkanonisierung wird diese zum Beispiel über das Zählen der Nachbarn nach der Knotenfarbe erreicht, also durch Anwendung der SP-Homomorphismen NP: [2]([n] 2)→Z|P|n E7→ |{j∈Pk| {i, j} ∈ E}|k∈[|P|]i∈[n] . Hier zeigt sich, dass es unter Umständen notwendig ist, das Homomorphieprinzip iteriert anzuwenden. Man betrachte dazu folgendes Beispiel: 55 3. Kanonisierungsalgorithmen 0 [1] 1 [2] 2 [2] 3 [2] 4 [1] P0= ([5]) π0= id5 0 [0,1] 4 [1,1] 2 [0,2] 3 [1,1] 1 [0,1] P1= ({0,1},{2,3,4}) π1= (1,4) 0 [0,1,0] 2 [1,0,1] 4 [0,2,0] 3 [1,0,1] 1 [0,1,0] P2= ({0,1},{2,3},{4}) π2= (2,4)(1,4) = (1,2,4) V(Γ, SP0)V(Γ, SP1π1) V(Γ, SP2π2) Abbildung 3.5.: Iterierte Verfeinerung 3.2.29 Beispiel. Es soll der folgende Graph Γ = 01234kanonisiert werden. •Die Wurzel des Suchbaums T(Γ, S5)wird über die Verfeinerung V(Γ, S5)definiert und diese wiederum mittels Homomorphieprinzip aus dem S5-Homomorphismus N([5]). Das Bild N([5])(Γ) = ((1),(2),(2),(2),(1)) ordnet jedem Knoten die Anzahl seiner Nachbarn zu, siehe auch Abbildung 3.5 (links). Die Kanonisierung des Vektors N([5])(Γ) = ((1),(2),(2),(2),(1)) unter der Operation der symmetrischen Gruppe S5erfolgt nun durch lexikographisches Sortieren, etwa über die Permutation (1,4). Im Anschluss werden nur noch Permutationen aus dem Stabilisator StabS5N([5])((1,4)Γ) | {z } =((1),(1),(2),(2),(2))=S({0,1},{2,3,4}) auf (1,4)Γ angewandt. Wir erhalten somit als Wurzel des Backtrackbaums T(Γ, S5) die Nebenklasse V(Γ, S5) = S({0,1},{2,3,4})(1,4). •An dieser Stelle würde man nun mit der Partitionierung von SP1(1,4) fortfahren. Man beobachtet aber, siehe Abbildung 3.5 (Mitte), dass es durch die vorhergehende Verfeinerung möglich ist, im Graphen (1,4)Γ den Knoten 2von 3und 4zu separieren. Dies erfolgt durch eine erneute Anwendung des Homomorphieprinzips zum Homomorphismus N({0,1},{2,3,4}). •Erst durch diesen Schritt erreicht man eine Färbung der Knoten bzw. eine Nebenklasse SP2(1,2,4), welche unter Anwendung der Verfeinerung Vinvariant bleibt. 56 3.2. Partitionen und Verfeinerungen S5 SP2π2 S({0},{1},{2,3},{4})π2 {π0:= (1,2,4)} 02431 S({0},{1},{2,3},{4})(0,1)π2 {π1:= (0,1,3,2,4)} 13420 ”=“ definiert Automorphismus von Γ ¨ uber (1,2,4)−1(0,1,3,2,4) = (0,4)(1,3) Kanonischer Repr¨ asentant von Γ Transporterelement zu Γ Verfeinerung Abbildung 3.6.: Suchbaum zu Beispiel 3.2.29 In der Graphenkanonisierung wird eine solche Partitionierung als balanciert (engl. „equitable“) bezeichnet. Abbildung 3.6 zeigt nun den gesamten Suchbaum T(Γ, S5). Wir haben zur Verdeutlichung die Zwischenschritte der Verfeinerung ebenfalls notiert. Die gestrichelten Bereiche zeigen Urbild und Bild einer jeden (iterierten) Verfeinerung. Nur die Bilder treten tatsächliche im Suchbaum T(Γ, S5)als Knoten auf. 3.2.30 Bemerkung. Sollen bereits gefärbte Graphen als die zu kanonisierenden Objekte untersucht werden, so transformiert man das Problem zur Kanonisierung eines gegebenen Graphen Γ = ([n], E), welcher über eine geordnete Partition pgefärbt ist, auf eine Kanonisierung von πΓunter SPmit Sp n=SPπ. Dann treten im Backtracking ebenfalls nur kanonische Young-Untergruppen auf. 3.2.5. Iterierte Verfeinerung Das Beispiel 3.2.29 deutet an, dass die tatsächlich genutzte Verfeinerungsfunktion V auch über eine mehrfache Anwendung einer weiteren Verfeinerung V:X×C(G)→ C(G) gewonnen werden kann. Wir definieren hierzu: V0(x, Hg) := V(x, Hg) und für beliebiges n≥1 Vn(x, Hg) := V(x, Vn−1(x, Hg)). 57 3. Kanonisierungsalgorithmen 3.2.31 Hilfssatz. Es sei n≥1beliebig. Dann definiert die Funktion Vnebenfalls eine Verfeinerung. Außerdem existiert eine natürliche Zahl N≥1, so dass für alle n0≥N die Gleichheit Vn0=VNgilt. Beweis. Es seien g0∈G,x∈Xund Hg ∈ C(G)beliebig. Dann ergibt sich die erste Aussage induktiv aus der Gleichung g0∗Vn(x, Hg) = g0∗V(x, Vn−1(x, Hg)) = V(g0x, g ∗Vn−1(x, Hg)) =Vg0x, Vn−1(g0x, Hgg−1 0)=Vn(g0x, Hgg−1 0) = Vn(g0∗(x, Hg)), sowie der Tatsache, dass Vn(x, Hg) = V(x, Vn−1(x, Hg)) ⊆Vn−1(x, Hg)⊆Hg gilt. Da die Menge aller Rechtsnebenklassen endlich ist, muss die absteigende Kette V0(x, Hg)⊇V1(x, Hg)⊇. . . von Rechtsnebenklassen ab einer natürlichen Zahl N(x, Hg)stationär werden, d.h. V0(x, Hg))V1(x, Hg)). . . )VN(x,Hg)(x, Hg) = VN(x,Hg)+1(x, Hg) = . . . . Da auch der Definitionsbereich X× C(G)endlich ist, erfüllt N:= max (x0,H0g0)∈X×C(G)N(x0, H0g0)∈N die Aussage aus dem zweiten Punkt. 3.2.32 Bemerkung. Wir nennen dieses Prinzip zur Gewinnung weiterer Verfeinerungen daher auch iterierte Verfeinerung. Der Begriff einer balancierten Partition zu einem gefärbten Graphen aus der Graphenkanonisierung beschreibt also genau das Erreichen der Zahl N(x, Hg). Für die Korrektheit des in Satz 3.2.8 entworfenen Kanonisierungsalgorithmus ist es unerheblich ob Vn(x, Hg) = Vn−1(x, Hg)gilt, beziehungsweise ob die Verfeinerungen noch zu echten Untergruppen geführt haben. Wir gehen daher zur Vereinfachung im Folgenden von einer fest gewählten, eingabeunabhängigen Zahl v∈Naus und betrachten die Verfeinerung Vv. Wir nehmen weiter an, dass die ursprüngliche Verfeinerung Vüber die Anwendung des Homomorphieprinzips aus einer Familie (fH)H∈L(G)von H-Homomorphismen fH gewonnen wurde, siehe Satz 3.2.4. Das Ziel dieses Abschnittes ist es, nun zu beweisen, dass sich auch Vvüber eine Familie (fH)H∈L(G)gewinnen lässt. Dies ist notwendig um weiterhin die Bewertungen B(x, Hg)auf den Knoten Hg des Backtrackbaums T(x, G) definieren zu können. Wir wollen diese Aussage induktiv beweisen. Daher nehmen wir zunächst an, dass für alle Untergruppen Hvon Gzwei H-Homomorphismen f(0) H:X→Yund f(1) H:X→Z gegeben seien. 58 3.2. Partitionen und Verfeinerungen 3.2.33 Hilfssatz. Für alle H∈ L(G)definiert die Funktion fH:X→Y×Z x7→ f(0) H(x),TRY Hf(0) H(x)−1·f(1) StabHCFY H(f(0) H(x))TRY Hf(0) H(x)·x einen H-Homomorphismus. Beweis. Es seien h∈H∈ L(G)und x∈Xbeliebig. Zunächst beweist man leicht über die Kanonisierung von f(0) H(x)und f(0) H(hx), dass es ein h0∈H0:= StabHCFY H(f(0) H(x)) gibt mit TRY Hf(0) H(hx) | {z } =:h1 h=h0TRY Hf(0) H(x) | {z } =:h0 . Damit zeigen wir: h−1·fH(hx) = h−1·f(0) H(hx), h−1 1·f(1) H0(h1·hx) =f(0) H(x), h−1h−1 1·f(1) H0(h1hx)=f(0) H(x), h−1 0h0−1·f(1) H0(h0h0x) =f(0) H(x), h−1 0·f(1) H0(h0·x)=fH(x) Für die Untergruppen H∈ L(G)seien CanY Hbzw. CanZ HKanonisierer für die Operationen von Hauf den Mengen Yund Z. Mit diesen gewinnen wir die Verfeinerungen V(0) und V(1) gemäß Satz 3.2.4. Außerdem können wir nach Beispiel 3.1.5 einen Kanonisierer CanX×Y Hfür das direkte Produkt Y×Zdefinieren, indem wir zunächst die erste Komponente auf ihren kanonischen Repräsentanten transformieren und anschließend nur noch mit dem Stabilisator auf der zweiten Komponenten operieren. Es definiert also auch die Familie (fH)H∈L(G) zusammen mit den Kanonisierern CanX×Y HH∈L(G)nach Satz 3.2.4 eine Verfeinerung V. Wir zeigen nun, dass diese als iterierte Verfeinerung gesehen werden kann: 3.2.34 Hilfssatz. Für alle (x, Hg)∈X× C(G)gilt V(x, Hg) = V(1)x, V (0)(x, Hg). Beweis. Wir zeigen für ein beliebiges Paar (x, Hg)∈X× C(G), dass V(1)x, V (0)(x, Hg)= StabHCFX×Y H(fH(gx))TRX×Y H(fH(gx))g gilt. Hierzu sei H0= StabHCFY Hf(0) H(gx)und h0:= TRY Hf(0) H(gx). Es ist also V(0)(x, Hg) = H0h0gund wir erhalten: V(1)(x, H0h0g) = StabH0CFZ H0f(1) H0(h0gx)·TRZ H0f(1) H0(h0gx)·h0g = StabHCFX×Y H(fH(gx))·TRX×Y H(fH(gx)) ·g=V(x, Hg) 59 3. Kanonisierungsalgorithmen Nun sei Vdie aus fH,CanHH∈L(G)gewonnene Verfeinerung, welche wir iteriert – wie zu Beginn des Abschnitts angedeutet – anwenden wollen. Obiger Hilfssatz erlaubt es uns nun induktiv zu jeder Verfeinerung Vi,i∈[v+ 1] eine geeignete Familie (f(i) H)H∈L(G)von H-Homomorphismen f(i) Hund zugehörigen Kanonisierern Can(i) Hanzugeben. Zum Induktionsstart können wir offensichtlich f(0) H,Can(0) HH∈L(G):= fH,CanHH∈L(G) setzen. Aus der Induktionsvoraussetzung folgt, dass es zu der Verfeinerung Vi−1eine Familie von H-Homomorphismen samt Kanonisierung im Bildbereich gibt, welche Vi−1 definiert. Damit sind die Voraussetzungen für den Hilfssatz 3.2.34 erfüllt (mit V(1) =V und V(0) =Vi−1) und wir schließen, dass sich Viebenso definieren lässt. Dieser Beweis zeigt noch mehr. Es ist also möglich die Verfeinerung Vfür das Backtracking über eine Folge beliebiger Verfeinerungen (V0, . . . , V v−1)zu definieren. Wir schreiben aus diesem Grund eine Folge von Verfeinerungen (V0, . . . , V v−1)bzw. für jedes i∈[v]eine Familie (f(i) H)H∈L(G)samt Kanonisierern im Bildbereich zur Gewinnung der iterativen Verfeinerung Vvor. 3.2.35 Bemerkung. Man kann sich auch überlegen, dass die Wahl der Verfeinerung Vi, i ∈[v]hierbei durchaus von den Resultaten der Verfeinerungen auf den Vorfahren abhängig gemacht werden kann. Wir gehen hierauf aber nicht mehr näher ein. Um im Folgenden leichter auf die Eingaben und Ausgaben für den iterierten Aufruf der Verfeinerungen zugreifen zu können, werden wir mit T(x, G)denjenigen Wurzelbaum bezeichnen, der auch alle Zwischenschritte des Backtracking über eine iterierte Verfeinerung wiedergibt. Die Knotenmenge ist hierbei über eine Teilmenge von C(G)×[v+ 1] gegeben. Die zusätzliche Bereitstellung des Iterationszählers für die Knotenbeschriftungen verhindert, dass Schleifen in T(x, G)auftreten. Den Wurzelbaum definieren wir wieder induktiv: •Die Wurzel von T(x, G)sei (G, 0). •Ist (Hg, i)ein Knoten in T(x, G)mit i<vso definiert (Vi(x, Hg), i + 1) das einzige Kind von (Hg, i). •Für einen Knoten (Hg, v)mit |H|>1sei H0:= I(x, Hg)und {h0, . . . , hu−1}eine Rechtstransversale von H0in H. Die Kinder von (Hg, v)werden dann von der Menge {H0h0g, . . . , H0hu−1g}gebildet. Die Bewertungsfunktion verallgemeinern wir wie oben: Die Knoten der Gestalt (Hg, 0) mit Hg 6=Gwurden durch eine Partitionierung erzeugt, sie übernehmen daher ihre Bewertung vom Vater. Für alle anderen Knoten (Hg, i),i≥1verlängern wir den Bewertungsvektor des Vaters (H0g, i −1) um den Eintrag CFH0(f(i−1) H0(gx)). Wir können somit alle zuvor bewiesenen Aussagen für T(x, G)sofort auf T(x, G)übertragen, insbesondere Fakt 3.2.2 und auch das Abschneiden von Teilbäumen über bekannte Automorphismen und nicht optimaler Bewertungen. 60 3.3. Gruppen der Gestalt GoϕSP0 3.3. Gruppen der Gestalt GoϕSP0 In diesem Abschnitt sei P0eine fest gewählte kanonische Partition von [n]. Wir wollen nun unser Vorgehen für Gruppenoperationen der Gestalt GoϕSP0mit einem Gruppenhomomorphismus ϕ:SP0→Aut(G)auf einer Menge Xnäher beschreiben. Da wir uns ϕfest vorgeben, werden wir auf die weitere Angabe von ϕinnerhalb des semidirekten Produkts zu Gunsten der Übersichtlichkeit verzichten. Wie wir bereits in Abschnitt 3.1.1 gesehen haben, können wir einen Kanonisierer zu dieser Operation auch aus einem Kanonisierer CanSP0zu der Operation von SP0 auf G\\Xüber das Homomorphieprinzip gewinnen. Wir werden auf diese Entsprechung später eingehen, zunächst beschreiben wir das Backtracking aber über den Suchbaum T(x, G oSP0). Als Beispiel und Motivation dient uns die Gruppenoperation von ((GLk(R)×(R∗)n)oAut(R)) oSn auf der Menge Rk×n,(m,...,m)aller Generatormatrizen von freien Codes vom Rang k. 3.3.1 Bemerkung. Unser Vorgehen ist maßgeblich durch diese Gruppenoperation motiviert. Im Allgemeinen haben wir mit diesem Ansatz zur Definition des Kanonisierers für derartige Gruppenoperationen, d.h. für Gruppenoperationen, die sich auch als Operation von Gauf Sn\\Ynmit X=Ynbeschreiben lassen, bislang ausnahmslos positive Erfahrungen gemacht. Gegebenenfalls sind für Gruppenoperationen aus andersartigen Problemstellungen aber auch grundverschiedene Ansätze zur Gewinnung eines effizienten Kanonisierers nötig. Über die Wahl der Verfeinerung und der Partitionierung werden wir überdies steuern, dass die zulässigen Knoten des Wurzelbaums T(x, G oSP0)bzw. die auftretenden Rechtsnebenklassen, auf die Menge C(GoSP0) := HoSP(g;π)|HoSP∈ L(GoSP0)und (g;π)∈GoSP0 zu Untergruppen der Gestalt L(GoSP0) := {HoSP|H≤G, PP0:HoSP∈ L(GoSP0)}(3.6) beschränkt ist. Dementsprechend beschränken wir auch Definitionsund Bildbereich der Verfeinerungen bzw. Partitionierungsvorschrift bereits im Vorfeld auf: Vi:X× C(GoSP0)→ C(GoSP0), i ∈[v] und I:X× C(GoSP0)→ L(GoSP0). Im Folgenden wollen wir zu i∈[v]mit f(i) HoSPHoSP∈L(GoSP0)diejenige Familie von HoSP-Homomorphismen bezeichnen, welche zur Definition der Verfeinerung Vivorgeschrieben wurde. 61 3. Kanonisierungsalgorithmen Beweis. Die Abbildungsvorschrift ist wohldefiniert: •Aus der Partitionierung von P0folgt zunächst, dass es für beliebiges x∈Gx höchstens einen Knoten ((HoSP), i)der Tiefe tin T(x, G oSP0)dieser Gestalt geben kann. Alle weiteren Knoten dieser Tiefe sind Rechtsnebenklassen mit nicht trivialer Permutationskomponente. •Existiert ein weiteres Bahnenelement g0x,g0∈G, mit dieser Eigenschaft, so ist (HoSP)g−1 0der eindeutig bestimmte Knoten in T(g0x, GoSP0)der Tiefe t, der als Rechtsnebenklasse mit trivialer Permutation geschrieben werden kann. In diesem Fall ist dann g0∈Hund CFHf(im) HoSP(x)= CFHf(im) HoSP(g0x). Nun zu der SP-Invarianz der Abbildungsvorschrift. Es genügt die Situation zu betrachten, in welcher zu Gx ∈G\\Xein solches Gruppenelement x∈Gx existiert (für den anderen Fall ist die Aussage offensichtlich wahr). Ist π∈SPbeliebig, so ist wieder ((HoSP)π−1= (HoSP), i)ein Knoten in T(πx, G oSP0)der Tiefe t. Somit folgt: f(t) P(πGx) = CFHf(im) HoSP(πx)= CFHf(im) HoSP(x)=f(t) P(Gx) Analog beweist man für Knoten auf ungerader Tiefe t: 3.3.13 Hilfssatz. Ist t≥0ungerade, t6≡ vmod v+ 1 und PP0, so definiert f(t) P:G\\X→Zn∪ {()} Gx 7→    f(a) HoSP(x),∃x∈Gx, HoSP∈ L(GoSP0)sd. (HoSP, i) ein Knoten der Tiefe tin T(x, G oSP0) (),sonst einen SP-Homomorphismus. Beweis. Die Wohldefiniertheit der Abbildungsvorschrift zeigt man, wie im vorausgegangenen Hilfssatz, indem man die H-Invarianz der Funktion f(a) HoSPbenutzt. Für die SP-Homomorphie genügt es wieder, diejenigen Gx ∈G\\Xzu untersuchen, für welche ein solches Bahnenelement x∈Gx und eine Untergruppe HoSP∈ L(GoSP0)existiert. Ist π∈SPbeliebig, so folgt: f(t) P(πGx) = f(t) P(πGx) = f(a) HoSP(πx) = πf(a) HoSP(x) = πf(t) P(Gx) Induktiv lässt sich nun leicht zeigen, dass man über diese Familien von Homomorphismen genau den gewünschten Suchbaum T(Gx, SP0)entwickelt. Wir geben nur die zentrale Idee für den Beweis am Beispiel der Knoten auf ungerader Tiefe t: 68 3.3. Gruppen der Gestalt GoϕSP0 Ist (HoSP(g;π), i)ein Knoten in T(x, G oSP0)der Tiefe tund wird für diesen die Verfeinerung V(a)gerufen, so ist das Ergebnis: (HoSQ)(h;σ)(g;π) := V(a)(x, H oSP(g;π)) = StabHoSPCFHoSP(f(a)((g;π)x))TRHoSP(f(a)((g;π)x))(g;π) Für den isomorphen Knoten (SPπ, i)in T(Gx, SP0)ergibt sich dann an dieser Stelle als Ergebnis der entsprechend definierten Verfeinerung Vt: Vt(Gx, SPπ) = StabSPCFSP(f(t) P(πGx))TRHoSP(f(t) P(πGx) | {z } =f(a)((g;π)x) )π=SQσπ Wir geben nun noch abschließend einige Hinweise zur tatsächliche Algorithmenimplementierung: •Zu jedem Knoten (SPπ, i)in T(Gx, SP0)verwalten wir im Hintergrund die injektive Folge ederjenigen Koordinaten, für welche die innere Kanonisierung bereits durchgeführt wurde. Zu dieser Folge eist ein e-semikanonischer Repräsentant x(π,e) von Gπx und dessen Stabilisator H=G(e,πx)= StabGx(e,π)bestimmt. •Ist igerade, so bestimmen wir zunächst f:= F(x(e,π), H oSP)und bewerten den Knoten mit der SP-Invarianten Πf(x(π,f)) = CFHΠf(x(e,π))und setzen als Kind (SPπ, i + 1). •Ist i < r ungerade, so verfeinern wir die Partition Püber die Kanonisierung von f(a) HoSP(x(e,π))unter Ausnutzung des Homomorphieprinzips. Ist (h;σ) := TRHoSPf(a) HoSP(x(e,π)) und SP:= StabSPσf(a) HoSP(x(e,π), so ergibt sich der neue e-semikanonische Repräsentant x(e,σπ):= σx(e,π). Die Gruppe Hmuss nicht abgeändert werden und wir setzen als Kind (SQσπ, i + 1). Die Isomorphie der beiden Suchbäume gibt uns nun auch einen Hinweis, wie wir das Abschneiden von Teilbäumen in T(x, GoSP0)mit Hilfe der bekannten Automorphismen von xdurchführen werden. Wir verwalten nur den Permutationsanteil, d.h. die Gruppe StabSP0(Gx), über ein Labelled Branching mit Basis (0, . . . , n −1). Das Abschneiden von Teilbäumen erfolgt wieder über den Hilfssatz 3.2.26. Unter der Annahme, dass für alle x∈Xder Stabilisator StabG(x) = {1G}trivial ist, können wir sogar zeigen, dass dies zu keinem Verlust von Informationen führt: 69 3. Kanonisierungsalgorithmen 3.3.14 Hilfssatz. Es sei A≤GoϕSP0mit A:= {π|(g;π)∈A}und |A|=|A|. Ist TAeine Linkstransversale von SP0/A, so definiert TA:= {(g;π)|g∈G, π ∈TA}eine Linkstransversale von (GoϕSP0)/A. Beweis. Wir nehmen an, in der Menge TAseien (g0;π0),(g1;π1)Nebenklassenrepräsentanten zu der gleichen Linksnebenklassen von A. Es ist also (g0;π0)−1(g1;π1)=(ϕ(π−1 0)(g−1 0); π−1 0)(g1;π1)=(ϕ(π−1 0)(g−1 0g1); π−1 0π1)∈A Hieraus schließen wir π−1 0π1∈Aund damit π0=π1. Aufgrund unserer Voraussetzung |A|=|A|impliziert dies bereits g0=g1. Die Vollständigkeit von TAfolgt sofort aus Anzahlgründen. 3.3.15 Folgerung. Ist A≤GoSP0wie oben, TAeine Linkstransversale und (HoSP)(g;π)∈ C(GoSP0)beliebig, so gilt: TA∩(HoSP)(g;π) = ∅ ⇐⇒ TA∩SPπ=∅ Beweis. TA∩SPπ6=∅ ⇐⇒ ∃ π∈TA, σ ∈SP:π=σπ ⇐⇒ ∃ (g;π)∈TA,(h;σ)∈HoSP: (g;π)=(h;σ)(g;π) ⇐⇒ TA∩(HoSP)(g;π)6=∅ 70 4. Endliche Kettenringe Wir werden nun zunächst noch weitere Eigenschaften endlicher Kettenringe besprechen, welche wir bei der Formulierung eines Kanonisierers für lineare Codes benötigen werden. Der erste Abschnitt fasst hier im Wesentlichen Resultate aus [44] zusammen. Insbesondere wird auch auf die Struktur der additiven und multiplikativen Gruppe eingegangen. Anschließend leiten wir eine Strukturaussage über endliche Kettenringe her, welche sich zum Beispiel auch in [59] findet. Der nachfolgende Abschnitt behandelt dann die Automorphismengruppe eines Kettenrings. Es sei weiter Rstets ein endlicher Kettenring der Kettenlänge mmit R/ Rad(R)≃Fq und q=prfür eine Primzahl pund Exponenten r. Außerdem bezeichne θ∈Reinen fest gewählten Erzeuger des Jacobson-Radikals Rad(R) = Rθ. 4.1. Weitere Grundlagen 4.1.1 Definition (Teichmüller-Menge).Eine Teilmenge T⊆Rnennen wir TeichmüllerMenge von R, falls 0∈Tund T∗:= T\ {0}ein multiplikativ abgeschlossenes Vertretersystem der Menge (R/ Rad(R))∗≃F∗ qist. Wir nennen T∗auch eine Teichmüller-Gruppe. 4.1.2 Fakt. Der endliche Kettenring Rbesitzt mindestens eine Teichmüller-Menge. Die Teichmüller-Gruppen sind gerade die zyklischen Untergruppen von R∗der Ordnung q−1. Teichmüller-Mengen gehen durch Konjugation mit Einheiten auseinander hervor. Ist R kommutativ, dann ist also die Teichmüller-Menge Teindeutig. 4.1.3 Definition (Schiefpolynomring).Es sei Rein Ring und σ∈Aut(R)ein Ringautomorphismus. Wir wollen mit R[X;σ]den Schiefpolynomring über Rzum Automorphismus σbezeichnen. Dieser Ring unterscheidet sich von dem klassischen Polynomring R[X]nur in der Definition der Multiplikation Xa := σ(a)Xeines Ringelements a∈R mit der Unbestimmten X. Über die Schiefpolynomringe können wir nichtkommutative Kettenringe konstruieren, siehe Fakt 4.1.25. 4.1.4 Beispiel. Es sei τder Frobenius-Automorphismus von F4. Der Kettenring R= F4[X;τ]/(X2)hat die folgenden Teichmüller-Mengen T0={0,1, a, a2}=F4,T1= {0,1, a +X, a2+X},T2={0,1, a +aX, a2+aX}und T3={0,1, a +a2X, a2+a2X}. Im weiteren Verlauf dieser Arbeit sei stets Teine fest gewählte Teichmüller-Menge von Rund ξein Erzeuger der Teichmüller-Gruppe T∗. Es gilt weiter: 71 4. Endliche Kettenringe 4.1.5 Fakt (θ-adische Entwicklung).Der Kettenring Rbesitzt qmElemente und jedes beliebige a∈Rlässt sich eindeutig in der Form a=Pm−1 i=0 aiθi, mit ai∈Tschreiben. Wir nennen eine solche Darstellung die θ-adische Entwicklung von abezüglich T. Das Ideal Rad(R)k, k ∈[m+ 1] hat somit genau qm−kElemente. 4.1.6 Beispiel. Die Teichmüller-Menge von Z9ist {0,1,8}und θ= 3 ist ein Erzeuger von Rad(Z9). Die 3-adische Entwicklung von 2ist 2=8·30+ 1 ·31. Neben dem Ringelement θ= 3 können wir auch θ0= 6 als Erzeuger des Jacobson-Radikals wählen. Die 6-adische Entwicklung von 2ist dann 2 = 8 ·60+ 8 ·61 4.1.7 Definition. Wir werden im Folgenden zu i∈[m]mit coeff(i):R→T, a 7→ ai diejenige Abbildung bezeichnen, welche das Ringelement a∈Rauf seinen eindeutigen Koeffizienten ai∈Tder θ-adischen Entwicklung a=Pm−1 i=0 aiθiabbildet. Den Ring Rkönnen wir (über die additive Gruppe) auch auf natürliche Weise als Z-Modul interpretieren, indem wir für z∈Zund a∈Rdie Skalarmultiplikation über z·a:=    a+. . . +a | {z } z−mal ,falls z≥0 (−z)·(−a),falls z < 0 definieren. Wir identifizieren dann die ganze Zahl zauch mit z·1R∈R. Die größte Zahl ε∈Nmit p·1R∈Rad(R)εnennen wir den Verzweigungsindex zu R. Es ist stets ε≥1, da die Gleichung p·1R=p·1Fq= 0Fqbereits p∈Rad(R)impliziert. Wir nutzen nun diese Beobachtung aus, um die θ-adische Entwicklung eines Ringelements weiter zu verfeinern. Diese verfeinerte Beschreibung gibt uns dann die Möglichkeit, bequem eine Totalordnung auf Rzu definieren. 4.1.8 Hilfssatz ((ξ, θ)-adische Entwicklung).Ist ξein Erzeuger der Teichmüller-Gruppe T∗von R, so gibt es zu jedem a∈Reine eindeutige Darstellung der Gestalt a= r−1 X i=0 m−1 X j=0 aijξr−1−iθj= (ξr−1, . . . , ξ0)   a0,0. . . a0,m−1 . . ..... . . ar−1,0. . . ar−1,m−1    | {z } =:coeff(a)    θ0 . . . θm−1   mit coeff(a)∈[p]r×m. Wir nennen sie die (ξ, θ)-adische Entwicklung von a. Beweis. Besitzt jedes Ringelement eine (ξ, θ)-adische Entwicklung, so folgt die Eindeutigkeit sofort aus Anzahlgründen. Wir beweisen die Existenz einer (ξ, θ)-adischen Entwicklung nun induktiv für die Ringelemente a∈Rad(R)kfür alle k∈[m+ 1]. Für das Nullelement – gleichzeitig der Induktionsstart Rad(R)m={0R}– gibt es offensichtlich eine solche Darstellung. 72 4.1. Weitere Grundlagen Es sei nun k∈[m]und die Behauptung für alle Ringelemente aus dem Ideal Rad(R)k+1 bereits bewiesen. Wir wählen a∈Rad(R)k\Rad(R)k+1 beliebig. Da Tein Vertretersystem von R/ Rad(R)≃Fqbildet, können wir coeff(k) (a)eindeutig über die Linearkombination Pr−1 i=0 aikξr−1−i, aik ∈[p]der Fp-Basis (1, ξ, . . . , ξr−1)von Fqdarstellen. Es existiert also ein Element b∈Rad(R)mit coeff(k) (a)−Pr−1 i=0 aikξr−1−i=bund es folgt a0:= a− r−1 X i=0 aikξr−1−iθk=bθk+ m−1 X j=k+1 coeff(j) (a)θj∈Rad(R)k+1. Für das Ringelement a0∈Rad(R)k+1 existiert nach der Induktionsvoraussetzung aber eine (ξ, θ)-adische Entwicklung a0=Pr−1 i=0 Pm−1 j=k+1 aijξr−1−iθj. Es ist also a= r−1 X i=0 m−1 X j=k aijξr−1−iθj die gesuchte (ξ, θ)-adische Entwicklung von a. 4.1.9 Definition. Wir werden im Folgenden zu i∈[r]und j∈[m]mit coeff(i,j):R→[p], a 7→ aij = coeff(a)i,j diejenige Abbildung bezeichnen, welche das Ringelement a∈Rauf seinen eindeutigen Koeffizienten aij ∈[p]der (ξ, θ)-adischen Entwicklung a=Pr−1 i=0 Pm−1 j=0 aijξr−1−iθj abbildet. Häufig werden wir die Matrix coeff(a)∈[p]r×mder (ξ, θ)-adischen Entwicklung von a∈Rauch über dem Körper Fpauffassen. Statt coeff(a)schreiben wir dann auch coeff(a). Gleiches gilt für die Koeffizienten der θ-adischen Entwicklung coeff(i) (a)bezüglich dem Körper Fq. 4.1.10 Bemerkung. Bei der Definition einer Totalordnung auf Rwird sich die zunächst kontraintuitive Zuordnung des Koeffizienten aij zu ξr−1−iθjals vorteilhaft erweisen. 4.1.11 Beispiel. Es ist R=F4[X]/(X2)ein Kettenring der Kettenlänge m= 2 mit Teichmüller-Menge T:= {0,1, ξ, ξ2}=F4und θ:= X. Das Ringelement 1 + ξ2X∈R hat die (ξ, X)-adische Entwicklung 1 + ξ2X= 0 ·ξ1X0+ 1 ·ξ0X0+ 1 ·ξ1X1+ 1 ·ξ0X1. 4.1.12 Folgerung. Für beliebiges a∈Rund j≤min{ht(a), m −1}ist coeff(j) (a) = r−1 X i=0 coeff(i,j) (a)ξr−1−i. Beweis. Folgt sofort aus dem Beweis zur Existenz der (ξ, θ)-adischen Entwicklung von a∈R. 73 4. Endliche Kettenringe 4.1.13 Bemerkung. Die Teichmüller-Menge Tist im Allgemeinen nicht additiv abgeschlossen. Es ist somit für beliebiges a∈Rund j∈[m]mit j > ht(a)im Allgemeinen coeff(j) (a)6= r−1 X i=0 coeff(i,j) (a)ξr−1−i. Eine ähnliche Aussage gilt für Summen von Ringelementen: 4.1.14 Hilfssatz. Es seien a, b ∈Rbeliebig und j∈[m] : j≤max{ht(a),ht(b)}. Dann gilt: coeff(j) (a+b) = coeff(j) (a) + coeff(j) (b) und coeff(i,j) (a+b) = coeff(i,j) (a) + coeff(i,j) (b),∀i∈[r] Beweis. Folgt sofort aus den θ-adischen bzw. (ξ, θ)-adischen Entwicklungen von a, b und a+b. Wir nutzen nun die Bijektion von Rnach [p]r×mum ausgehend von einer Totalordnung auf [p]r×meine Totalordnung auf Rzu definieren. Hierzu lesen wir die Matrizen spaltenweise und vergleichen die resultierenden Vektoren lexikographisch: 4.1.15 Definition (Totalordnung auf R).Für alle a, b ∈Rsei a≤b:⇐⇒ coeff(a)≤coeff(b) 4.1.16 Beispiel. Die Totalordnung auf dem Kettenring R:= F4[X]/(X2)bestimmt sich wie in Tabelle 4.1 angegeben über die letzte Tabellenspalte. Die Abbildungen coeff(i,j)erlauben es uns nicht nur, eine Totalordnung auf Rzu definieren, sondern auch die Struktur der Gruppen (R, +) und (R∗,·)genauer zu untersuchen. Hierzu definieren wir zunächst zu i∈[r+ 1] und j∈[m]die Mengen R(i,j):= na∈Rad(R)j| ∀ 0≤ν < i : coeff(ν,j) (a) = 0o =(r−1 X ν=i aν,jξr−1−νθj|aν,j ∈[p],∀i≤ν≤r−1)+ Rad(R)j+1. 4.1.17 Folgerung. Für beliebiges i∈[r]und j∈[m]gilt: •∀a∈Rad(R)j+1,∀b∈Rad(R)j\Rad(R)j+1 :a<θj≤b •R(i+1,j)⊂R(i,j)und |R(i,j)|=pr(m−j)−i •∀a∈R(i+1,j),∀b∈R(i,j)\R(i+1,j):a < ξr−1−iθj≤b 74 4.1. Weitere Grundlagen X-adische Entwicklung von a∈R(ξ, X)-adische Entwicklung von acoeff(a) 0 0 ( 0 0 0 0 ) X1·X(0 0 0 1 ) ξX 1·ξX + 0 ·X(0 1 0 0 ) ξ2X1·ξX + 1 ·X(0 1 0 1 ) 1 1 ·1 + 0 ·ξX + 0 ·X(0 0 1 0 ) 1 + X1·1 + 0 ·ξX + 1 ·X(0 0 1 1 ) . . .. . .. . . ξ2+ξ2X1·ξ+ 1 ·1 + 1 ·ξX + 1 ·X(1 1 1 1 ) Tabelle 4.1.: Totalordnung auf F4[X]/(X2) Beweis. Anschaulich bedeutet der Übergang von R(i+1,j)nach R(i,j)die Freiheit einen weiteren Eintrag der Matrix coeff(a)beliebig zu belegen. Dabei wird analog zur Definition der Totalordnung auf Rvorgegangen. An den Übergängen R(0,j+1) zu R(r,j)nutzt man die Gleichheit der Mengen R(0,j+1) = Rad(R)j+1 =R(r,j). 4.1.18 Hilfssatz. Für jedes i∈[r]und j∈[m]ist die Teilmenge R(i,j)eine Untergruppe der abelschen Gruppe (R, +) und R=R(0,0) B. . . BR(r,0) =R(0,1) B. . . BR(r,m−1) ={0R} ist eine Kompositionsreihe von (R, +), bei welcher jeder Faktor R(i,j)/R(i+1,j), i ∈[r] isomorph zu Zpist. Beweis. Wir zeigen die Behauptung für ein fest gewähltes j∈[m]über eine Induktion nach i∈[r]. Offensichtlich sind die Mengen R(0,j)= Rad(R)jUntergruppen und wegen der Kommutativität auch Normalteiler. Die Abbildung coeff(i,j):R(i,j)→Zp, a 7→ coeff(i,j) (a) definiert einen Epimorphismus, dessen Kern gleich R(i+1,j)ist. Auf gleiche Weise gewinnen wir eine Normalreihe von (R∗,·)mit zyklischen Faktoren. Im weiteren Verlauf dieser Arbeit werden wir die zu den Faktorgruppen isomorphen Gruppen jeweils über dem Normalteilerzeichen notieren: 4.1.19 Hilfssatz. Für i∈[r+ 1] und j∈[m] : j≥1sei R∗(i,j):= 1 + R(i,j). Dann bilden die Mengen R∗(i,j)Untergruppen von (R∗,·)und R∗F∗ q D1 + Rad(R) = R∗(0,1) Zp B. . . Zp BR∗(r,1) =R∗(0,2) Zp B. . . Zp BR∗(r,m−1) ={1R} ist eine Normalreihe von R∗mit zyklischen Faktoren. 75 4. Endliche Kettenringe Beweis. Zunächst zeigen wir, dass für jedes i∈[r]und j∈[m]die Mengen R∗(i,j) multiplikativ abgeschlossen sind. Dazu wählen wir a, b ∈R(i,j)beliebig. Es gilt: (1 + a)(1 + b) = 1 + (a+b) |{z } ∈R(i,j) +ab |{z} ∈Rad(R)2j⊆Rad(R)j+1 ∈1 + R(i,j)=R∗(i,j) Der erste Normalteiler 1 + Rad(R)CR∗der Kette ergibt sich sofort aus dem Gruppenepimorphismus ¯: R∗→F∗ q, a 7→ a. Die Normalteilereigenschaft der Untergruppen R∗(i+1,j)in R∗(i,j)mit i∈[r]und j∈[m] : j≥1erhält man aus dem Epimorphismus coeff(i,j):R∗(i,j)→Zp, dessen Kern gleich R∗(i+1,j)ist. Kettenringe Rmit Verzweigungsindex ε= 1 nennen wir Galois-Ringe. Das JacobsonRadikal Rad(R) = pR wird also von einer Primzahl perzeugt. Wir vereinbaren, für Galois-Ringe stets den Erzeuger θ=pzu wählen. 4.1.20 Fakt ([59, Theorem 4.2]).Galois-Ringe sind stets kommutativ. Zu einer beliebigen Primzahl pund natürlichen Zahlen m, r > 0existiert ein bis auf Isomorphie eindeutiger Galois-Ring GR(pm, r)der Charakteristik pmund Kardinalität prm. Zur Konstruktion des Galois-Ring GR(pm, r) = Zpm[X]/(f)wählt man ein normiertes Polynom1 f∈Zpm[X]vom Grad r, dessen Bild modulo pin Zp[X]irreduzibel ist. 4.1.21 Beispiel. Der endliche Körper Fprist isomorph zum Galois-Ring GR(p, r). Der Kettenring Zpmist isomorph zu dem Galois-Ring GR(pm,1). Die Galois-Ringe sind nicht nur wegen ihrer Eindeutigkeit und Konstruktion den endlichen Körpern sehr verwandt: 4.1.22 Fakt ([59, Theorem 4.5]).Die Automorphismengruppe Aut(GR(pm, r)) eines Galois-Rings ist zyklisch und von der Ordnung r. Sie wird von dem Frobenius-Automorphismus τ∈Aut(GR(pm, r)) erzeugt, der die Elemente a∈GR(pm, r)in p-adischer Entwicklung a=Pm−1 i=0 aipiauf τ(a) := Pm−1 i=0 ap ipiabbildet. 4.1.23 Bemerkung. Da die Abbildung ϕ: Aut(GR(pm, r)) →Aut(Fpr)mit σ(a) := ϕ(σ)(a) := σ(a)für alle σ∈Aut(GR(pm, r)) und a∈Reinen kanonischen Isomorphismus zwischen beiden Automorphismengruppen definiert, werden wir im Folgenden auch den Frobenius-Automorphismus des Körpers Fprmit dem gleichen Symbol τbezeichnen. 1In [73, Tabelle 1.1] gibt J. Zwanzger eine Liste solcher Polynome. Sie bilden überdies eine Verallgemeinerung der sogenannten Conway-Polynome über endlichen Körpern, vergleiche [64]. Sie sind ebenfalls für gegebenes qund meindeutig bestimmt und können somit zur standardisierten Darstellung der Elemente eines Galois-Rings herangezogen werden. Überdies gewährleisten sie eine gewisse Kompatibilität in der Darstellung des Galois-Rings und seinen Galois-Unterringen. 76 4.1. Weitere Grundlagen Es sei pmSdie Charakteristik des endlichen Kettenrings R. Nach [12, 59] besitzt R einen bis auf Isomorphie eindeutig bestimmten Galois-Unterring S≃GR(pmS, r)⊆ Rmit S=R=Fpr. Man nennt den Ring Sauch einen Koeffizientenring zu R, da man als eine Teichmüller-Menge von Rauch die Teichmüller-Menge Tvon Swählen kann2. Damit zeigt man aber auch leicht über Konjugation, dass das Ringerzeugnis einer jeden Teichmüller-Menge Tvon Reinen solchen Unterring S≃GR(pmS, r)von Rergibt. Es liegen also ohne Beschränkung der Allgemeinheit alle Koeffizienten der θ-adischen Entwicklung eines Elements a∈Rin dem Galois-Unterring S. Ist εder Verzweigungsindex zu R, so gilt somit für eine beliebige Teichmüller-Menge Tvon R und a, b, c ∈T: a+b=c⇐⇒ a+b−c∈Rad(R)∩S=Sp ⊆Rp = Rad(R)ε Wir benötigen noch einige weitere Eigenschaft der endlichen Kettenringe, bevor wir zu der Kanonisierung der linearen Codes übergehen können. Die nachfolgende Diskussion folgt dem Übersichtsartikel [59]. Die Beweise für unsere Aussagen finden sich in [58]. Unsere Ausführungen werden bis zu der Tatsache vordringen, dass sich jeder endliche Kettenring als Quotient eines Schiefpolynomrings über einem beliebigen Koeffizientenring darstellen lässt. 4.1.24 Fakt ([59, Proposition 5.17]).Es sei Rein endlicher Kettenring und S≃ GR(pmS, r)ein Koeffizientenring von R. Dann gibt es einen Erzeuger θvon Rad(R) und einen ausgezeichneten Automorphismus τe∈Aut(S), so dass die Ringelemente a∈Süber die Vorschrift θa =τe(a)θmit θvertauschen. Wir vereinbaren also weiter, dass zu dem gegebenen Kettenring Rmit Koeffizientenring Sder Erzeuger θund der Ringautomorphismus τe∈Aut(S)durch Fakt 4.1.24 bestimmt sind. Dann lässt sich auch über die θ-adische Entwicklung eines Ringelements a=Pm−1 i=0 aiθimit ai∈T⊆Sdie Multiplikation von amit θvon links leicht beschreiben: θa =θ· m−1 X i=0 aiθi= m−1 X i=0 τe(ai)θi!·θ Wir schließen mit einer Charakterisierung der endliche Kettenringe ohne die auftretenden Begriffe exakt zu definieren: 4.1.25 Fakt ([59, Theorem 5.18]).Zu jedem endlichen Kettenring Rmit Koeffizientenring Sexistiert ein spezielles Eisensteinpolynom f∈S[X;τe]über dem Schiefpolynomring S[X;τe], so dass R≃S[X;τe]/f, pmS−1XmR−(mS−1). Weitergehende Informationen findet man in [59], insbesondere auch zu der Definition eines spezielles Eisensteinpolynoms und den weiteren Einschränkungen, die man zum Beispiel an den Grad von fmachen muss. Eine Klassifikation der endlichen Kettenringe bis auf Isomorphie ist immer noch offen. 2Dies ist sofort ersichtlich, da die Teichmüller-Gruppen genau die multiplikativ abgeschlossene Teilmengen von Rbzw. Smit q−1Elementen sind. 77 4. Endliche Kettenringe 4.2.12 Hilfssatz. Es sei χθ+aθi ξ∈Inn(i) ξein innerer Automorphismus für ein a∈R∗ und i≥2. Dann gibt es eine Einheit b∈Z(i−1)(ξ), welche χθ+aθi ξinduziert. Beweis. Da χθ+aθi ξein innerer Automorphismus ist, wissen wir, dass ein c∈Z(ξ)existiert mit cθc−1=θ+aθi. Wir nehmen zunächst an, dass c=c0+c1θfür ein c0∈T∗, c06= 1 und c1∈Rsei. Dann gilt: θ≡(c0+c1θ)θ(c0+c1θ)−1≡c0θc−1 0≡c0τe(c−1 0)θmod Rad(R)2 ⇐⇒ c0τe(c−1 0)∈1 + Rad(R). Da aber c0, τe(c−1 0)und auch c0τe(c−1 0)in der Teichmüller-Menge liegen, folgt weiter c0τe(c−1 0) = 1 ⇐⇒ c0=τe(c0)⇐⇒ c0θ=θc0. Das Ringelement c0∈Tkommutiert also mit allen Ringelementen und es definiert daher c−1 0c= 1 + c−1 0c1θ∈1 + Rad(R)den gleichen inneren Automorphismus χθ+aθi ξ. Wir haben hiermit gezeigt, dass der innere Automorphismus χθ+aθi ξbereits von einem Ringelement c∈1 + Rad(R)erzeugt wird. Wir nehmen dies als Induktionsstart und zeigen für 2≤j≤i−1, dass aus der Existenz eines Elements c∈Z(j−1)(ξ)mit θ+aθi=cθc−1auch die Existenz eines Elements c0∈Z(j)(ξ)mit θ+aθi=c0θc0−1folgt: Liegt cbereits in Z(j)(ξ), so ist nichts zu zeigen. Es sei also c= 1 + c0θj−1+c1θjmit c0∈T∗und c1∈R. Aus Hilfssatz 4.2.10 schließen wir außerdem, dass r ggT(r,e)ein Teiler von (j−1) ist. Dann folgt aus θ≡cθc−1≡(1 + c0θj−1+c1θj)θ(1 + c0θj−1+c1θj)−1 ≡(1 + c0θj−1)θ(1 −c0θj−1)≡θ+ (c0−τe(c0))θjmod Rad(R)j+1 bereits (c0−τe(c0)) ∈Rad(R)⇐⇒ c0=τe(c0)⇐⇒ c0θ=θc0. Hierdurch ergibt sich, dass das Ringelement (1 −c0θj−1)sowohl mit ξals auch mit θ kommutiert und also der von (1 −c0θj−1)erzeugte innere Automorphismus trivial ist. Somit ist der von c0:= (1 −c0θj−1)c∈1 + Rad(R)jerzeugte innere Automorphismus ebenfalls gleich χθ+aθi ξ. 4.2.13 Folgerung. Es sei i∈[m],i≥2mit r ggT(r,e)-(i−1), dann ist Inn(i) ξ= Inn(i+1) ξ, d.h. es gibt in der Menge Aut(0,i) ξ\Aut(0,i+1) ξkeine inneren Automorphismen. Beweis. Jede Einheit b∈Z(i−1)(ξ) = Z(i)(ξ)induziert einen Automorphismus χbθb−1 ξ∈ Inn(i+1) ξ. 84 4.2. Automorphismen 4.2.14 Folgerung. Es sei i∈[m],i≥2mit r ggT(r,e)|(i−1). Dann ist ncoeff(i) (α(θ)) |α∈Inn(i) ξo={a−τe(a)|a∈Fq} Beweis. Für einen Ringautomorphismus α∈Inn(i+1) ξist coeff(i) (α(θ)) = 0 = 1 −τe(1). Wir müssen also nur die Ringautomorphismen α∈Inn(i) ξ\Inn(i+1) ξbetrachten. Ein solcher werde von dem Ringelement 1 + tθi−1+b0θi+1 mit t∈T∗und b0∈Rinduziert. Es folgt: θ+ coeff(i) (α(θ))θi≡(1 + tθi−1)θ(1 −tθi−1)≡θ+ (t−τe(t))θimod Rad(R)i+1 Damit haben wir die Inklusionsrichtung „⊆“ bewiesen. Umgekehrt sieht man leicht, dass für t∈T∗die Einheit 1 + tθi−1∈Z(ξ)einen inneren Automorphismus α∈Inn(i) ξ induziert mit coeff(i) (α(θ)) = t−τe(t). Es sei wieder Fps≤Fqder Fixkörper von τe, also s= ggT(r, e). Die Abbildung Fq→Fq, x 7→ x−τe(x)ist dann Fps-linear. Die Menge T1:= {a−τe(a)|a∈Fq}aus dem vorangegangenem Hilfssatz ist somit ein Fp-Unterraum der Dimension r−s. Die vorausgegangenen Ergebnisse über die Gruppen Z(ξ),Z(R)und Innξfassen wir nun in dem folgenden Satz zusammen: 4.2.15 Satz. Es sei x:= r ggT(r,e)und l:= m−1 x. Dann sind Z(ξ) F∗ q DZ(x)(ξ) Fr p DZ(2x)(ξ) Fr p D. . . Fr p DZ(lx)(ξ) Fr p DZ((l+1)x)(ξ)D{1R} Z(R) F∗ ps DZ(x)(R) Fs p DZ(2x)(R) Fs p D. . . Fs p DZ(lx)(R) Fs p DZ((l+1)x)(R)D{1R} Innξ F∗ q/F∗ ps DInn(x+1) ξ Fr−s p DInn(2x+1) ξ Fr−s p D. . . Fr−s p DInn(lx+1) ξ Fr−s p DInn((l+1)x+1) ξ={idR} die Normalreihen von Z(ξ),Z(R)und Innξ. Ist (l+ 1)x=m−1⇐⇒ x|(m−1), so ist Z((l+1)x)(R) = Z((l+1)x)(ξ)≃Fr p. Andernfalls sind beide Gruppen trivial. 4.2.16 Bemerkung. Das hier erzielte Ergebnis zu Z(R)deckt sich mit dem Resultat von A. Nechaev über das Zentrum [59, Theorem 5.18 (d)] des Rings R. Wir schließen das Kapitel mit einer Beschreibung der Gruppe Out(R)über eine Normalreihe. Hierzu seien für i∈[r+ 1] und j∈[m], j ≥2die Gruppen Inn(i,j) ξ:= Aut(i,j) ξ∩Inn(R)und Out(i,j) ξ:= Aut(i,j) ξ/Inn(i,j) ξ. Aus dem ersten Isomorphiesatz für Gruppen ergibt sich wieder die Isomorphie Out(i,j) ξ≃Aut(i,j) ξ◦Inn(R)/Inn(R) 85 4. Endliche Kettenringe und damit auch, dass wir Out(i+1,j) ξals Normalteiler in Out(i,j) ξauffassen können. Weiter ist genau dann Out(i+1,j) ξ= Out(i,j) ξ, wenn Aut(i+1,j) ξ= Aut(i,j) ξoder Inn(i+1,j) ξ6= Inn(i,j) ξ gilt. Andernfalls ist die Faktorgruppe Out(i,j) ξ/Out(i+1,j) ξisomorph zu Zp. Zusammenfassend ergibt sich der folgende Satz: 4.2.17 Satz. Es sei x:= r ggT(r,e)und I:= ni∈[r]| ∃ t∈Tsd. ∀i0< i : coeff(i0,0) (t−τe(t)) = 0 ∧coeff(i,0) (t−τe(t)) 6= 0o. Dann ist Out(R)DOutξDOut(0,2) ξD. . . DOut(r,2) ξ= Out(0,3) ξD. . . DOut(r,m−1) ξ(4.2) eine Normalreihe mit zyklischen Faktoren. Dabei ist •OutT/Outξ≃Zr0mit r0|raus Hilfssatz 4.2.6 und •Outξ/Out(0,2) ξ≃Zs0mit s0|(pggT(r,e)−1). Für i∈[r]und j∈[m] : j≥2gilt weiter •Out(i,j) ξ/Out(i+1,j) ξ≃Zp, falls Aut(i,j) ξ6= Aut(i+1,j) ξund x-(j−1) ∨i6∈ Iund •Out(i,j) ξ= Out(i+1,j) ξin allen anderen Fällen. Beweis. Mit Ausnahme von Outξ/Out(0,2) ξ≃Zs0mit s0|(pggT(r,e)−1) wurden alle Aussagen bereits weiter oben behandelt. Die verbliebene Aussage lässt sich aber mit dem Homomorphismus Ψ : Autξ→F∗ q,α7→ coeff(1) (α(θ)) und der Beobachtung Ψ(Innξ) = ξ1−pe=DξpggT(r,e)−1Esofort folgern. Die notwendigen Modifikationen an Algorithmus A.1 zur Berechnung eines Erzeugendensystems von Out(R)geben wir in Bemerkung A.5 im Anhang A. 86 5. Lineare Codes über endlichen Kettenringen Wir werden nun im Folgenden lineare Codes der Länge nüber einem Kettenring Rmit fest vorgegebenen Umriss λ= (λ0, . . . , λk−1)untersuchen. Ziel dieses Kapitels ist es, einen Kanonisierer für die Operation der Gruppe der semilinearen Isometrien von Rn auf dieser Menge zu entwickeln. Da wir einen linearen Code Cin diesem Algorithmus über eine Generatormatrix darstellen möchten, werden wir zunächst die Menge aller Generatormatrizen von Cüber eine Gruppenoperation beschreiben. Wie wir bereits in Beispiel 2.3.18 gesehen haben, führt – bei nicht freien Codes – die Multiplikation einer Generatormatrix Γvon Cmit einer invertierbaren Matrix A∈GLk(R)nicht notwendigerweise zu einer weiteren Generatormatrix von C. Wir wollen daher zunächst die Gruppe GLk(R)derart auf eine Untergruppe GLλ(R)einschränken, dass wir die Menge aller Generatormatrizen von C wieder über die Bahnenmenge GLλ(R)Γ erhalten. Einen eindeutigen Repräsentanten dieser Bahn erhalten wir über eine Verallgemeinerung der reduzierten Zeilenstufenform. In einem weiteren Schritt transformieren wir dann die Problemstellung auf eine Operation der Gruppe ((GLλ(R)×(R∗)n)oAutT)oSnauf der Menge Rk×n,λ aller Generatormatrizen zum Umriss λ. Diese Operation können wir mit den Algorithmen aus Kapitel 3 behandeln. Eine entscheidende Rolle wird hierbei der Operation der Untergruppe ((GLλ(R)×(R∗)n)oAutT)zukommen. Für diese werden wir in dem Abschnitt 5.1.2 einen effizienten Kanonisierer bereitstellen. Der zweite Abschnitt 5.2 beschreibt dann schlussendlich den gewünschten Kanonisierer für die Operation von ((GLλ(R)×(R∗)n)oAutT)oSnauf der Menge Rk×n,λ. Diesen werden wir durch Bereitstellung einer inneren Kanonisierung und einer äußeren Verfeinerung über den in Abschnitt 3.3 beschriebenen Basisalgorithmus gewinnen. 5.1. Generatormatrizen Wir wollen nun, wie bereits angedeutet, zunächst die Untergruppe GLλ(R)definieren und die Operation dieser Gruppe auf der Menge Rk×n,λ untersuchen. 5.1.1 Definition. Zu einem Umriss λ= (λ0, . . . , λk−1)und i∈[m]sei kλ i:= |{j∈[k]|λj=m−i}| 87 5. Lineare Codes über endlichen Kettenringen und GLλ(R)die Menge aller Blockmatrizen der Gestalt A(i,j)i,j∈[m]∈Rk×kmit A(i,j)∈     Rkλ i×kλ j,falls 0≤i<j≤m−1 GLkλ i(R),falls 0≤i=j≤m−1 θi−jRkλ i×kλ j,falls 0≤j < i ≤m−1. 5.1.2 Fakt ([73, Lemma 2.21]).Die Menge GLλ(R)bildet eine Untergruppe von GLk(R). 5.1.3 Bemerkung. Nach [73, Lemma 2.20] ist eine Blockmatrix A(i,j)i,j∈[m]mit A(i,j)∈(Rkλ i×kλ j,falls 0≤i≤j≤m−1 Rad(R)kλ i×kλ j,falls 0≤j < i ≤m−1 genau dann invertierbar, wenn alle A(i,i)invertierbar sind. 5.1.4 Fakt ([73, Satz 2.22]).Ist Γ∈Rk×n,λ eine Generatormatrix zu einem Code Cvom Umriss λ, so ist die Menge aller Generatormatrizen von Cgleich der Bahn GLλ(R)Γ. Für nicht freie Codes führt diese Gruppe aber zu einer nicht treuen Gruppenoperation: 5.1.5 Fakt ([73, Lemma 2.23]).Für eine beliebige Generatormatrix Γ∈Rk×n,λ ist StabGLλ(R)(Γ) = Nλ(R) := Ik+v0θλ0, . . . , vk−1θλk−1|vi∈(Rk)R. Insbesondere ist für λ6= (m, . . . , m)– d.h. für nicht freie Codes – die Gruppenoperation von GLλ(R)auf Rk×n,λ nicht treu. Die Untergruppe Nλ(R)ist als Schnitt aller Stabilisatoren ein Normalteiler von GLλ(R). 5.1.6 Bemerkung. Im Folgenden werden wir die Operation der Gruppe GLλ(R)auf Rk×n,λ durch die natürliche Operation der Faktorgruppe GLλ(R)/Nλ(R)ersetzen. Aus Gründen der Übersichtlichkeit werden wir aber keine Unterscheidung zwischen den Gruppenelementen A∈GLλ(R)und ANλ(R)∈GLλ(R)/Nλ(R)machen. Aussagen, wie zum Beispiel „ANλ(R)ist von oberer Dreiecksgestalt“, beziehen sich dann auf die Existenz eines Nebenklassenvertreters A∈GLλ(R)mit dieser Eigenschaft. 5.1.7 Folgerung. Zwei Generatormatrizen Γ,Γ0∈Rk×n,λ erzeugen genau dann semilinear isometrische Codes, wenn es ein Gruppenelement (ANλ(R), ϕ;α, π)∈(GLλ(R)/Nλ(R)×(R∗)n)o(Aut(R)×Sn) gibt mit (ANλ(R), ϕ;α, π)Γ = (A, ϕ;α, π)Γ = Γ0. 88 5.1. Generatormatrizen Über einem endlichen Körper Fqkönnen wir jedem linearen Code Ceine eindeutige Generatormatrix zuordnen, indem wir diejenige Generatormatrix Γ∈Fk×n qauszeichnen, welche in reduzierter Zeilenstufenform vorliegt. Sie ist bekanntermaßen eindeutig in der Bahn GLk(Fq)Γ und bildet somit einen kanonischen Repräsentanten für diese Operation. Wir wollen nun zeigen, dass dies im Fall eines linearen Codes über einem endlichen Kettenring genauso möglich ist. Wir verallgemeinern zunächst die Definition der reduzierten Zeilenstufenform einer Matrix: 5.1.8 Definition (reduzierte Zeilenstufenform).Wir sagen eine Matrix Γ∈Rk×nist in Zeilenstufenform, falls es eine Folge von Spaltenindizes 0≤j0< . . . < jk0−1≤n−1mit k0≤kgibt, so dass •für alle i∈[k0]die Einträge Γi,jiPivotelemente sind, d.h. Γi,ji6= 0 und für alle i∈[k0]und j∈[ji]ist Γi0,j = 0, und •alle weiteren Zeilen Γi,∗für k0≤i<kNullzeilen sind. Die Spalten Γjinennen wir auch Pivotspalten. Die Zeilenstufenform ist reduziert, falls sie überdies die folgenden Eigenschaften erfüllt: •für alle i∈[k0]ist das Pivotelement Γi,ji=θm−λimit λi:= per(Γi,∗), •die Folge (λ0, . . . , λk0−1)ist monoton fallend und •alle weiteren Einträge der Spalte Γ∗,jisind modulo dem Pivotelement reduziert, d.h. Γ`,ji= mina∈RΓ`,ji+aθm−λi,∀`6=i. 5.1.9 Bemerkung. Aufgrund der von uns gewählten Ordnung auf Rbeschreibt die letzte Bedingung, dass die letzten λiSummanden der θ-adischen Entwicklung von Γ`,ji gleich Null sind, d.h. Γ`,ji=Pm−λi−1 h=0 coeff(h) (Γ`,ji)·θh. Insbesondere falls λi=mgilt, ist somit die Spalte Γ∗,jigleich dem i-ten Einheitsvektor. 5.1.10 Folgerung. Die ersten k0Zeilen einer Matrix Γ∈Rk×nin reduzierter Zeilenstufenform bilden eine Generatormatrix des von Γerzeugten linearen Codes. Beweis. Man zeigt leicht, dass die Zeilen unabhängig sind. Aufgrund der geforderten Anordnung der Perioden ist Γ[k0],∗also eine Generatormatrix. 5.1.11 Beispiel. Die Matrix Γ = 2 1∈Z1×2,(2) 4ist eine Generatormatrix eines linearen Codes in Zeilenstufenform. Sie ist jedoch nicht reduziert. Da alle weiteren Generatormatrizen von Cdurch Linksmultiplikation mit Einheiten aus Γhervorgehen, gibt es also für Ckeine Generatormatrix in reduzierter Zeilenstufenform. Das Beispiel verdeutlicht, dass nicht jede Bahn GLk(R)Γ einer Matrix Γ∈Rk×nein Element in reduzierter Zeilenstufenform enthält. Umgekehrt zeigt aber der nachfolgende Hilfssatz, dass sie im Fall der Existenz eindeutig bestimmt ist und damit durchaus zur Definition eines kanonischen Repräsentanten geeignet ist. 89 5. Lineare Codes über endlichen Kettenringen 5.1.12 Hilfssatz. Ist Γ∈Rk×neine Matrix in reduzierter Zeilenstufenform, so existiert in der Bahn GLk(R)Γ keine weitere Matrix in reduzierter Zeilenstufenform. Beweis. Wir nehmen an, dass e Γ∈GLk(R)Γ eine weitere Matrix in reduzierter Zeilenstufenform sei. Ist nun k0der Rang des von Γerzeugten linearen Codes Cund λ dessen Umriss, so sind also Γ[k0],∗und e Γ[k0],∗beides Generatormatrizen von Cund beide Teilmatrizen in reduzierter Zeilenstufenform. Die weiteren Zeilen von Γund e Γsind Nullzeilen und somit können wir ohne Beschränkung der Allgemeinheit annehmen, dass k0=kgilt. Die Matrix e Γerhalten wir also durch Linksmultiplikation von Γmit einer geeigneten Matrix A∈GLλ(R). Wir zeigen nun über eine Induktion nach k, dass Abereits in Nλ(R)liegt und somit beide Matrizen gleich sind. Für k= 1 ist die Behauptung leicht einzusehen. Für den Induktionsschritt seien j0, . . . , jk−1sowie `0, . . . , `k−1die Indizes der Pivotspalten von Γbzw. e Γ. Man überlegt sich leicht, dass j0=`0gelten muss. Aus der Gleichung AΓ∗,j0=e Γ∗,j0erhält man damit A0,0∈1 + Rad(R)λ0und Ai,0∈Rad(R)λ0für alle i > 0. Die Teilmatrizen Γ≥1,∗ und e Γ≥1,∗erzeugen aus diesem Grund den gleichen linearen Code und sind Generatormatrizen in reduzierter Zeilenstufenform. Für sie gilt also die Induktionsvoraussetzung und es ist Γ≥1,∗=e Γ≥1,∗. Damit liegen auch die weiteren Pivotspalten an identischen Koordinatenpositionen, d.h. jµ=`µfür alle µ∈[k]. Abschließend zeigt man über eine Induktion für µ > 0, dass A0,µ ∈Rad(R)λµliegt. Wir betrachten hierzu die Gleichung e Γ0,jµ= (AΓ)0,jµ=A0,0Γ0,jµ+ µ−1 X i=1 A0,iΓi,jµ | {z } =0 +A0,µθm−λµ= Γ0,jµ+A0,µθm−λµ. Die Matrixeinträge e Γ0,jµ=und Γ0,jµsind modulo θm−λµreduziert, d.h. Nebenklassenrepräsentanten von R/ Rad(R)m−λµ. Damit folgt die Behauptung A0,µ ∈Rad(R)λµ. 5.1.13 Definition (systematische Generatormatrix).Eine Generatormatrix Γ∈Rk×n,λ in reduzierter Zeilenstufenform heißt systematisch, falls sich die Pivotspalten an den Positionen j0= 0 bis jk−1=k−1befinden. Für lineare Codes über endlichen Körpern kennt man bereits die Aussage, dass ein beliebiger linearer Code permutationsäquivalent zu einem Code mit systematischer Generatormatrix ist. Für Kettenringe gilt diese Aussage ebenfalls: 5.1.14 Fakt ([73, Satz 2.1]).Es sei Γ∈Rk×neine beliebige Matrix, welche einen linearen Code Cvom Umriss shp(C) = λ= (λ0, . . . , λk0−1)erzeugt. Dann gibt es eine Permutation π∈Sn, so dass der lineare Code π·Ceine systematische Generatormatrix e Γ∈Rk×n,λ besitzt. 90 5.1. Generatormatrizen Insbesondere ist der Beweis zu dem Satz konstruktiv. Es wird also in [73] explizit ein Algorithmus zur Berechnung der Permutation π∈Snund einer Matrix A∈GLk(R)mit AΓP(π)−1=e Γ 0(k−k0)×nangegeben. Will man nun für beliebige Matrizen Γ∈Rk×neinen kanonischen Repräsentanten CFGLk(R)(Γ) unter der Operation von GLk(R)bestimmen, so ist es einzig nötig, die Wahl der Permutation π∈Snaus Fakt 5.1.14 GLk(R)-invariant vorzunehmen. Dies ist in der Tat auch möglich: Man kann sich leicht überlegen, dass es genügt, die Auswahl eines Elements ai,j im Beweis zu [73, Satz 2.1] derart vorzunehmen, dass jstets minimal ist. Dann bestimmt man den kanonischen Repräsentanten CFGLk(R)(Γ) von Γüber die folgenden Schritte: 1. Bestimme eine Matrix A∈GLk(R), so dass A(ΓP(π)−1)bis auf weitere Nullzeilen die eindeutige systematische Generatormatrix in der Bahn GLk(R)(ΓP(π)−1)ist. 2. Definiere CFGLk(R)(Γ) := AΓ = AΓP(π)−1P(π). Diese Auswahl ist somit ebenfalls eindeutig in der Bahn GLk(R)Γ. 5.1.15 Bemerkung. Man kann sich leicht überlegen, dass dieses Vorgehen mit der Definition der sog. Fuller Canonical Form1für Galois-Ringe, gemäß [54, Exercise (XVI.7)] bzw. deren weiterer Verallgemeinerung auf beliebige Kettenringe in [17], übereinstimmt. Ist Γ∈Rk×neine Generatormatrix in reduzierter Zeilenstufenform, so ist sie mit dieser Definition der kanonische Repräsentant ihrer eigenen Bahn. Wir wollen nun noch diejenigen Matrizen auszeichnen, welche ohne Permutation der Spalten auf reduzierte Zeilenstufenform gebracht werden können: 5.1.16 Definition (umrisstreu).Wir sagen eine Matrix Γ∈Rk×nmit shp(Γ) = λist umrisstreu, falls für alle i∈[n]die Teilmatrizen Γ∗,[i]den Umriss shp(Γ∗,[i]) = λ[rg(Γ∗,[i])] haben. Dabei bezeichnet rg(Γ∗,[i]), wie vereinbart, den Rang des von Γ∗,[i]erzeugten Zeilenraums. 5.1.17 Hilfssatz. Eine Matrix Γ∈Rk×nist genau dann umrisstreu, wenn sie durch Linksmultiplikation mit einer Matrix A∈GLk(R)auf reduzierte Zeilenstufenform AΓ transformiert werden kann. Beweis. Jede Matrix Γ0∈Rk×nin reduzierter Zeilenstufenform ist ganz offensichtlich umrisstreu. Die Eigenschaft umrisstreu zu sein, ist aber eine GLk(R)-Invariante. Somit ist auch jedes weitere Element der Bahn GLk(R)Γ0umrisstreu. Es bleibt also nur noch zu zeigen, dass sich jede umrisstreue Matrix Γ∈Rk×nauch auf reduzierte Zeilenstufenform transformieren lässt. Wir zeigen dies über eine Induktion nach der Anzahl der Spalten. Für den Induktionsstart n= 0 ist die Aussage trivial. 1Sie ist motiviert durch die Arbeit [27]. 91 5. Lineare Codes über endlichen Kettenringen Für den Induktionsschritt von n−1nach n≥1sei k0= rg(Γ∗,[n−1])und λ= shp(Γ). Die Matrix Γ∗,[n−1] ist ebenfalls umrisstreu und wir können daher ohne Beschränkung der Allgemeinheit annehmen, dass diese in reduzierter Zeilenstufenform vorliegt: Γ = Γ[k0],[n−1] Γ[k0],n−1 0(k−k0)×(n−1)Γ[k]\[k0],n−1 Ist Γ[k]\[k0],n−1=0(k−k0)×1, d.h. k0= rg(Γ), so ist Γin reduzierter Zeilenstufenform. Hierzu macht man sich leicht klar, dass für i∈[k0]die Annahme Γi,n−16∈ Rad(R)m−λi sofort der Eigenschaft umrisstreu zu sein widerspräche. Im Fall Γ[k]\[k0],n−16=0(k−k0)×1schließt man analog, dass für alle i∈[k0]bereits Γi,n−1∈Rad(R)m−λigelten muss. Des Weiteren ist dann auch per(Γ[k]\[k0],n−1) = λk0 und es existiert ein Eintrag Γj,n−1mit k0≤j < k und per(Γj,n−1) = λk0. Der Stabilisator StabGLk(R)Γ∗,[n−1]beinhaltet aber nun alle Matrizen der Gestalt Ik0B 0(k−k0)×k0Amit A∈GLk−k0(R)und B∈Rk0×(k−k0), welche es uns erlauben, Γauf reduzierte Zeilenstufenform zu transformieren. 5.1.18 Hilfssatz. Ist die Matrix Γ∈Rk×numrisstreu und (ϕ;α)∈(R∗)noAut(R) beliebig, so ist auch (ϕ;α)Γ umrisstreu. Beweis. Die Gruppenoperation mit (ϕ;α)definiert einen Verbandsautomorphismus auf PHG(RRn). Insbesondere bleibt also der Umriss einer Matrix unberührt. Dies gilt natürlich auch für alle Teilmatrizen ((ϕ;α)Γ)∗,[i],i∈[n+ 1]. Somit ist (ϕ;α)Γ ebenfalls umrisstreu. 5.1.1. Reformulierung der Gruppenoperation In Folgerung 5.1.7 haben wir das Kanonisierungsproblem für lineare Codes bereits auf eine Gruppenoperation der Gruppe (GLλ(R)/Nλ(R)×(R∗)n)o(Aut(R)×Sn) auf der Menge Rk×n,λ zurückgeführt. Insbesondere haben wir auch festgestellt, dass die Untergruppe GLλ(R)nicht treu operiert und dies durch den Übergang zu der Faktorgruppe GLλ(R)/Nλ(R)behoben. Eine analoge Aussage wollen wir nun auch für die Spalten der Generatormatrix herleiten. Hierdurch werden wir die Komponenten (R∗)n und Snder operierenden Gruppe noch weiter einschränken. 5.1.19 Hilfssatz. Es sei G:= (GLλ(R)/Nλ(R)×(R∗)n)oAut(R). Die Abbildung f(per) :Rk×n,λ →[m+ 1]n,Γ7→ (per(Γ∗,i))i∈[n], welche jeder Spalte von Γ∈Rk×n,λ ihre Periode2zuordnet, ist eine G-Invariante und ein Sn-Homomorphismus. 2Zur Erinnerung: Die Periode per(v)eines Spaltenvektors v∈Rk Rist definiert als die minimale ganze Zahl mit vθper(v)=01×k. 92 5.1. Generatormatrizen Beweis. Die Periode eines Spaltenvektors v∈(Rk)Rbleibt invariant unter der Multiplikation mit invertierbaren Matrizen von links, der Multiplikation von Einheiten von rechts und auch unter der komponentenweisen Anwendung eines Ringautomorphismus. Somit ist die Funktion invariant unter der Operation mittels Gim Definitionsbereich. Sie ist außerdem ganz offensichtlich auch ein Sn-Homomorphismus. Zwei Generatormatrizen Γ,Γ0∈Rk×n,λ erzeugen nur dann semilinear isometrische Codes, wenn die Bilder f(per)(Γ) und f(per)(Γ0)in der gleichen Bahn unter der Operation von Snliegen. Wir legen nun über das Homomorphieprinzip und über die Kanonisierung im Bildbereich von f(per) fest, dass die Folge CFSnf(per)(Γ)=: µ∈[m+ 1]nmonoton fällt. Somit sind die Perioden der Spalten jeder kanonischen Generatormatrix CFGoSn(Γ), Γ∈Rk×n,λ beliebig, ebenfalls monoton fallend. Wir können also im Folgenden, ohne Beschränkung der Allgemeinheit, bereits im Vorfeld voraussetzen, dass die Eingaben Γ∈Rk×n,λ des Kanonisierers CanGoSnbereits diese Bedingungen erfüllen. In der Operation der symmetrischen Gruppe ziehen wir uns dann auf den Stabilisator SP0:= StabSn(µ)zurück. Die Blöcke der kanonischen Partition P0beschreiben hierbei die Koordinaten der Spalten mit gleicher Periode. Eine weitere Beobachtung, die wir an dieser Stelle einbringen können, bezieht sich auf eventuell auftretende Nullspalten der Generatormatrizen (dann ist µi= 0). Vom codierungstheoretischen Standpunkt sind diese Koordinaten ohnehin redundant. Aus Sicht der Gruppenoperation gilt diese Beobachtung ebenfalls, da wir unter einem beliebigen Gruppenelement (A, ϕ;α, π)∈((GLλ(R)/Nλ(R)×(R∗)n)oAut(R)) oSP0Nullspalten immer auf Nullspalten abbilden. Wir entfernen diese gegebenenfalls vor der Kanonisierung und fügen sie nach Abschluss in gleicher Zahl wieder an die kanonische Form an. Es ist klar, wie in diesem Fall der berechnete Stabilisator zu modifizieren ist. 5.1.20 Definition. Zu einem beliebigen Vektor µ∈({1, . . . , m})nsei Rk×n,λ,µ := Γ∈Rk×n,λ | ∀ i∈[n] : per(Γ∗,i) = µi die Menge aller Generatormatrizen vom Umriss λmit fest vorgegebener Periode µider i-ten Spalte. Im Folgenden sei also auch die monoton fallende Folge µ∈({1, . . . , m})nfest vorgeben und es werden nur noch Generatormatrizen aus der Teilmenge Rk×n,λ,µ betrachtet. Zu dem Vektor µsei im weiteren Verlauf P0die kanonische Partition von [n], welche über den Stabilisator SP0:= StabSn(µ)eindeutig bestimmt ist. 5.1.21 Bemerkung. Einen Vektor v∈(Rk)Rmit per(v) = mwollen wir als fett bezeichnen. Er erzeugt den Punkt vR in der projektiven Rechts-Hjelmslev-Geometrie PHG((Rk)R). Besitzen die auftretenden Generatormatrizen nur fette Spaltenvektoren (d.h. µ= (m, . . . , m)), so können wir nach Folgerung 3.1.10 dies auch als ein Kanonisierungsproblem von Punktkonfigurationen in PHG((Rk)R)auffassen. 93 5. Lineare Codes über endlichen Kettenringen Es bleibt also der Fall zu betrachten, dass die letzte Spalte eine Pivotspalte ist, d.h. Γ = Γ[k−1],[n−1] Γ[k−1],n−1 0n−1θm−λk−1. Die Teilmatrix Γ0:= Γ[k−1],[n−1] ∈R(k−1)×(n−1),λ[k−1],µ[n−1] ist in reduzierter Zeilenstufenform und es ist CFG(λ[k−1],µ[n−1])(Γ0)=Γ0. Aus der Gleichung 0n−1= Γk−1,[n−1] = Γk−1,[n−1] diag(ϕn−1) = Ak−1,∗α(Γ∗,[n−1]) = k−2 X j=0 Ak−1,jα(Γj,[n−1]) = k−2 X j=0 Ak−1,jα(Γ0 j,∗) und der Unabhängigkeit der Zeilen der Matrix α(Γ0)schließen wir wie oben zunächst Ak−1,j ∈Rad(R)λjfür alle j∈[k−1]. Da aber Atatsächlich die Nebenklasse ANλ(R)repräsentiert, können wir auch Ak−1,j = 0 setzen. Für die weiteren Einträge Ai,j, i∈[k−1] der Spalte A∗,j ergibt sich die Aussage über die Induktionsannahme, denn es ist A[k−1],[k−1] ∈StabG(λ[k−1],µ[n−1] (Γ0)↓GLλ[k−1] (R). Somit bleibt die Aussage für die letzte Spalte A∗,k−1zu beweisen. Es sei also i∈[k−1] mit λi=λk−1beliebig. Da Γeine Generatormatrix ist, liegt der Eintrag Γi,n−1 in Rad(R)m−λi. Andererseits ist er aber auch modulo dem Pivotelement θm−λk−1=θm−λi reduziert. Wir schließen, dass Γi,n−1= 0 ist, und erhalten hiermit 0 = Γi,n−1ϕn−1=Ai,∗α(Γ∗,n−1) = i−1 X j=0 Ai,j |{z} =0,da j<i α(Γj,n−1) + k−2 X j=i Ai,j |{z} =0,da λi≥λj≥λk−1 α(Γj,n−1) + Ai,k−1α(θm−λk−1) =Ai,k−1α(θm−λk−1). Hieraus ergibt sich Ai,k−1∈Rad(R)λk−1und wie oben können wir den Eintrag Ai,k−1= 0 setzen. 5.1.36 Folgerung. Beschreiben wir die Matrix A∈StabG(Γ)↓GLλ(R)über die Blockmatrizen A(i,j)∈Rkλ i×kλ jfür i, j ∈[m]gemäß der Definition 5.1.1, so ist A=     A(0,0) A(0,1) . . . A(0,m−1) A(1,1) . . . A(1,m−1) .... . . A(m−1,m−1)     mit Diagonalmatrizen A(i,i)∈GLkλ i(R). Im Folgenden bezeichnen wir wieder mit Sden Koeffizientenring von R, welcher von der Teichmüller-Menge Terzeugt wird. Weiter sei e∈[r]der eindeutige Exponent des Frobenius-Automorphismus τ∈Aut(S), für welchen τe(ξ)θ=θξ gilt. 5.1.37 Hilfssatz. Ist Γ∈Rk×n,λ,µ eine Matrix in reduzierter Zeilenstufenform und CFG(Γ) = Γ, so gilt für jedes beliebige P∈pΓ: 100 5.1. Generatormatrizen 1. Zu i∈Pund j∈ColsP(Γ) gibt es ein x∈hr ggT(r,e)i:Ai,i =τxe(ϕj)für alle (A, ϕ)∈StabGlin (Γ). 2. Zu i, j ∈Pgibt es ein x∈hr ggT(r,e)i:Ai,i =τxe(Aj,j)für alle (A, ϕ)∈StabGlin (Γ). 3. Zu i, j ∈ColsP(Γ) gibt es ein x∈hr ggT(r,e)i:ϕi=τxe(ϕj)für alle (A, ϕ)∈ StabGlin (Γ). Beweis. Die zweite und dritte Behauptung ergeben sich offensichtlich sofort aus der Ersten. Wir beweisen diese über eine Induktion nach der Länge ndes Codes. Für n= 1 ist sie trivial. Es sei n≥2beliebig und Γ∈Rk×n,λ,µ eine Generatormatrix in reduzierter Zeilenstufenform mit CFG(Γ) = Γ. Wir definieren e Γ := Γ∗,[n−1]. Die Blöcke e P∈pe Γmit e P∩supp(Γ∗,n−1) = ∅treten auch in pΓauf. Da der Index n−1nicht in Colse P(Γ) liegt, erhalten wir die Aussage für alle i∈e Püber die Induktionsvoraussetzung. In pΓgibt es genau einen weiteren Block P, welcher aus der Vereinigung der Blöcke e P∈pe Γmit e P∩supp(Γ∗,n−1)6=∅hervorgeht. Für die Indizes i∈Pund j=n−1ist die Behauptung noch zu beweisen. 1. Fall: Wir untersuchen zunächst den Fall, dass e Γeinen linearen Code mit gleichem Umriss λerzeugt, d.h. die letzte Spalte ist keine Pivotspalte. Zu einem Block e P∈pe Γ mit e P⊆Pdefinieren wir `:= max( e P∩supp(Γ∗,n−1)). Ist (A, ϕ)∈StabGlin (Γ) beliebig, so folgt Γ`,n−1= k−1 X j=` A`,jΓj,n−1!ϕ−1 n−1 =  X j∈e P:j≥` A`,j Γj,n−1 |{z} =0⇐⇒j>` +X j∈[k]\e P:j≥` A`,j |{z} =0 Γj,n−1  ϕ−1 n−1=A`,`Γ`,n−1ϕ−1 n−1 ≡A`,`τe·ht(Γ`,n−1)(ϕ−1 n−1)Γ`,n−1mod Rad(R)ht(Γ`,n−1)+1 und damit A`,`τe·ht(Γ`,n−1)(ϕ−1 n−1)∈1+Rad(R). Die kleinste positive Zahl x≡ht(Γ`,n−1) mod r ggT(r,e)ist also unabhängig von der Wahl des Elements (A, ϕ)∈StabGlin (Γ). Für alle weiteren i∈Pbenutzt man die Induktionsvoraussetzung und Punkt 2. der Behauptung. 2. Fall: Im zweiten zu untersuchenden Fall ist die letzte Spalte von Γeine Pivotspalte und daher Γk−1,n−1=θm−λk−1. Die Einträge Ak−1,k−1und ϕn−1eines Gruppenelements (A, ϕ)∈StabGlin (Γ) erfüllen die Gleichung θm−λk−1=Ak−1,k−1θm−λk−1ϕ−1 n−1. Dies beweist die Aussage 1. im Spezialfall i=k−1und j=n−1. 101 5. Lineare Codes über endlichen Kettenringen Um die Aussage für beliebiges i∈Pund j=n−1zu zeigen, wählen wir zunächst ein e P∈pe Γ[k−1],∗mit e P∩supp(Γ∗,n−1)6=∅und setzen wieder `:= maxe P∩supp(Γ∗,n−1) gleich dem größten Zeilenindex im Schnitt des Trägers mit dem Block e P. Es folgt 06= Γ`,n−1= k−1 X j=` A`,jΓj,n−1!ϕ−1 n−1= (A`,`Γ`,n−1+A`,k−1θm−λk−1)ϕ−1 n−1. Wäre nun λk−1=m, so ist der Eintrag Γ`,n−1modulo dem Pivotelement Γk−1,n−1= 1 reduziert und damit gleich 0. Dies ist aber ein Widerspruch zu unserer Wahl von `. Aus dem gleichen Grund gilt auch Γ`,n−16∈ Rad(R)m−λk−1. Somit ist in dieser Situation ebenfalls A`,`τe·ht(Γ`,n−1)(ϕ−1 n−1)∈1 + Rad(R). Die Aussagen für die weiteren, nicht diskutierten Werte i∈Pund j∈ColsP(Γ) ergeben sich dann wieder über die Induktionsannahme. 5.1.38 Folgerung. Zu P∈pΓdefinieren wir aP(Γ) := minna∈N|a > 0∧ ∃ i∈P, (A, ϕ)∈StabGlin (Γ) : Ai,i =ξao. Dann ist für alle (B, ψ)∈StabGlin (Γ):Bj,j, ψ`∈DξaP(Γ)Efür alle j∈Pund alle `∈ColsP(Γ). Beweis. Es sei (A, ϕ)∈StabGlin (Γ) ein Element des Stabilisators, welches für den Index i∈Pden Wert Ai,i =ξaP(Γ) annimmt. Durch Potenzieren von (A, ϕ)zeigt man leicht, dass aP(Γ) ein Teiler von q−1ist. Wir nehmen nun an, es gäbe ein weiteres Element (B, ψ)∈StabGlin (Γ) mit Bj,j =ξb für j∈Poder ψ`=ξbfür ein `∈ColsP(Γ), so dass ξb6∈ hξaP(Γ)i. Mit dem vorausgegangenen Hilfssatz ist also Bi,i =ξbpex für ein x∈hr ggT(r,e)i. Da aP(Γ) den Exponenten bnicht teilt, existieren ganze Zahlen y, z mit yaP(Γ) + zbpex = ggT(aP(Γ), bpex) = ggT(aP(Γ), b)< aP(Γ). Das Gruppenelement (A, ϕ)y(B, ψ)z∈StabGlin (Γ) widerspricht dann der Minimalität von aP(Γ). Das nächste Beispiel zeigt, dass tatsächlich nicht triviale Teiler aP(Γ) von q−1auftreten werden. 5.1.39 Beispiel. Es ist Γ := 1 0 1 1 0 1 1 Xeine Generatormatrix in reduzierter Zeilenstufenform eines linearen Codes über dem nicht kommutativen Kettenring R= F16[X, τ2]/(X2). Die Partition pΓist offensichtlich gleich {{0,1}}. Außerdem kann man sich leicht überlegen, dass CFG(Γ) = Γ gilt. 102 5.1. Generatormatrizen Wegen λ0=λ1, sind die Matrizen Afür die Gruppenelemente (A, ϕ;α)∈StabG(Γ) Diagonalmatrizen. Aus der Spalte Γ∗,2lässt sich leicht die Gleichheit A0,0=A1,1der Einträge der Diagonalen folgern. Ist nun α= id, so erhalten wir aus der letzten Spalte die beiden Gleichungen A1,1=A0,0=ϕ3und X=A1,1Xϕ−1 3=A1,1ϕ−4 3X=A−3 1,1X. Dies zwingt die Diagonaleinträge der Matrix Ain die Untergruppe hξ5i+ Rad(R). Insgesamt ergibt sich, dass der Stabilisator StabG(Γ) von den Gruppenelementen •((1 + aX)·I2,(1 + aX)·14; idR)mit a∈ {1, ξ, ξ2, ξ3} ⊆ F16 beliebig, •(ξ5·I2, ξ5·14; idR) •und dem Frobenius-Automorphismus I2,14;χX ξ2des Koeffizientenrings F16 erzeugt wird. Berücksichtigt man auch noch, dass ξ5die Gruppe aller zentralen Einheiten erzeugt, so ist der zweite Generator redundant. 5.1.40 Folgerung. Ist Γ∈Rk×n,λ,µ eine Matrix in reduzierter Zeilenstufenform und CFG(Γ) = Γ, so hat der Normalteiler Ψ(P,Γ)(StabGlin (Γ)) die Kardinalität p`P(Γ) ·q−1 aP(Γ) für ein `P(Γ) ∈Nund eine Normalreihe {1G}=: G(P) 0 Zp CG(P) 1 Zp CG(P) 2 Zp C. . . Zp CG(P) `P(Γ) Zx Ψ(P,Γ)(StabGlin (Γ)) (5.1) mit zyklischen Faktoren. Dabei ist x:= q−1 aP(Γ). Beweis. Folgt sofort aus der vorangegangenen Folgerung und Hilfssatz 5.1.28. Es sei Γ∈Rk×n,λ,µ eine Matrix in reduzierter Zeilenstufenform mit CFG(Γ) = Γ. Weiter sei pΓ={P(0), . . . , P(x−1)}. Wir fassen nun kurz zusammen, welche Aussagen wir über den Stabilisator bereits bewiesen haben: Es ist {1G}StabGlin (Γ) StabG(Γ). und den ersten Normalteiler können wir zunächst über die Folgerung 5.1.34 wie folgt verfeinern: {1G}Ψ(P(0),Γ)(StabGlin (Γ))  1 Y i=0 Ψ(P(i),Γ)(StabGlin (Γ)) . . .  x−1 Y i=0 Ψ(P(i),Γ)(StabGlin (Γ)) = StabGlin (Γ) Jeder Einzelschritt lässt sich dann weiter mit der Normalreihe (5.1) verfeinern. Somit kennen wir für StabGlin (Γ) eine Normalreihe mit zyklischen Faktoren. Den Normalteiler 103 5. Lineare Codes über endlichen Kettenringen StabGlin (Γ) StabG(Γ) verfeinern wir mit der Kette (4.1) zu: StabGlin (Γ) StabGlinoAut(r−1,m−1) ξ (Γ) . . . StabGlinoAut(0,m−1) ξ (Γ) . . . StabGlinoAut(0,2) ξ (Γ) StabGlinoAutξ(Γ) StabGlinoAutT(Γ) = StabG(Γ) (5.2) 5.1.41 Bemerkung. Insgesamt können wir also davon ausgehen, dass wir eine Normalreihe zu StabG(Γ) mit zyklischen Faktoren kennen. In dieser Normalreihe sind höchstens |pΓ|+ 2 nicht triviale Faktoren von einer Ordnung ungleich p. 5.1.42 Bemerkung. Es sei Γ∈Rk×n,λ,µ eine Matrix in reduzierter Zeilenstufenform mit CFG(Γ) = Γ. Weiter sei pΓ={P(0), . . . , P(x−1)}. Wir werden davon ausgehen, dass wir ein Erzeugendensystem (E(P(0)), . . . , E(P(x−1)), E(Aut))der Gruppe StabG(Γ) zur Verfügung haben, welches an die oben beschriebenen Normalreihe angepasst ist. Dies bedeutet, dass: •für einen Block P∈pΓdas Erzeugendensystem E(P)=E(P) 0, . . . , E(P) `P(Γ)von Ψ(P,Γ)(StabGlin (Γ)) derart gewählt wird, dass G(P) i:= hE(P) [i]ifür alle i∈[`P(Γ) + 1] eine Normalreihe (5.1) bildet; und •die Folge E(Aut) in diesem Sinne je einen weiteren Erzeuger gemäß der Normalreihe (5.2) bereitstellt. Mit diesen Vorbereitungen können wir nun schließlich einen Algorithmus zur induktiven Berechnung von CFG(Γ) angeben. Da wir obige Eigenschaften des Stabilisators einer Generatormatrix in reduzierter Zeilenstufenform benutzen wollen, müssen wir aber die Menge der zulässigen Eingaben bzw. die G-Menge, auf welcher wir die Operation betrachten, weiter einschränken. Wir wollen nun nur noch auf umrisstreuen Generatormatrizen operieren. Wir haben bereits bewiesen, dass die Eigenschaft, umrisstreu zu sein, G-invariant ist. Damit ist diese Einschränkung hinsichtlich einer wohldefinierten Gruppenoperation auch zulässig. Für das weitere Vorgehen ist der nachfolgende Hilfssatz von zentraler Bedeutung. Er liefert uns später die Voraussetzungen zur Definition des Induktionsschritts bei der algorithmischen Beschreibung der Kanonisierung CFRk×n,λ,µ G. 5.1.43 Hilfssatz. Es sei Γ∈Rk×n,λ,µ eine Generatormatrix, so dass CFG(Γ∗,[n−1]) = Γ∗,[n−1] in reduzierter Zeilenstufenform ist. Zu i∈[k]und x∈[m+ 1] definieren wir GΓ,(i,x):= ((A, ϕ;α)∈StabGΓ∗,[n−1]Aα(Γ∗,n−1)ϕ−1 n−1j= Γj,n−1,∀j > i Aα(Γ∗,n−1)ϕ−1 n−1i−Γi,n−1∈Rad(R)x). Dann ist GΓ,(i,0) =GΓ,(i+1,m)und GΓ,(i,x+1) ≤GΓ,(i,x)für alle x∈[m]. 104 5.1. Generatormatrizen Beweis. Die Gleichheit von GΓ,(i,0) =GΓ,(i+1,m)ist sofort klar. Die andere Aussage zeigen wir über eine Induktion über die Paare (i, x)∈[k]×[m+ 1] ausgehend von dem Paar (k−1,0). Für dieses beobachtet man leicht, dass GΓ,(k−1,0) = StabGΓ∗,[n−1]gilt. Nun werden wir schrittweise den Parameter xbis zum Wert x=merhöhen, anschließend zu (i−1,0) übergehen und dort wieder induktiv bis zum Wert (i−1, m)vordringen. Es sei also nun (i, x)∈[k]×[m]beliebig. Die Aussage werden wir über die Angabe eines Gruppenhomomorphismus Φ(i,x,Γ) :GΓ,(i,x)→FqoF∗ qoAut(Fq) (A, ϕ;α)7→ coeff(x) (((A, ϕ;α)Γ −Γ)i,n−1),coeff(x) (α(θx)) ·Ai,i τex(ϕn−1), α verifizieren. Die Multiplikation im Bildbereich ist hierbei über die Definition (a0, a1, α)·(b0, b1, β) := (a0+a1·α(b0), a1·α(b1), α ◦β) für alle (a0, a1, α),(b0, b1, β)∈FqoF∗ qoAut(Fq)gegeben. Die Menge GΓ,(i,x+1) ist dann das Urbild der Untergruppe3 (0, a1, α)|(0, a1, α)∈Φ(i,x,Γ)(GΓ,(i,x))≤FqoF∗ qoAut(Fq) und somit eine Untergruppe von GΓ,(i,x). Wir beweisen, dass die Funktion Φ(i,x,Γ) =Φ(i,x,Γ) 0,Φ(i,x,Γ) 1,Φ(i,x,Γ) 2einen Homomorphismus definiert, indem wir dies getrennt nach den einzelnen Komponenten (Fq,+), (F∗ q,·)und Aut(Fq)des semidirekten Produkts nachrechnen. Es gilt für beliebige (A, ϕ;α),(B, ψ;β)∈GΓ,(i,x): Φ(i,x,Γ) 0(A, ϕ;α)(B, ψ;β)= coeff(x) ((A, ϕ;α)(B, ψ;β)Γ −Γ)i,n−1 = coeff(x) Ai,iα((B, ψ;β)Γ)i,n−1 + k−1 X j=i+1 Ai,jα((B, ψ;β)Γ)j,n−1!ϕ−1 n−1−Γi,n−1! = coeff(x) Ai,iαΦ(i,x,Γ) 0(B, ψ;β)θx+ Γi,n−1+ k−1 X j=i+1 Ai,jα(Γj,n−1) !ϕ−1 n−1−Γi,n−1! = coeff(x) Ai,iαΦ(i,x,Γ) 0(B, ψ;β)θxϕ−1 n−1+ coeff(x) ((A, ϕ;α)Γ)i,n−1−Γi,n−1 =Ai,i ·τex(ϕn−1−1)·coeff(x) (α(θx)) ·αΦ(i,x,Γ) 0(B, ψ;β)+ Φ(i,x,Γ) 0(A, ϕ;α) = Φ(i,x,Γ) 1(A, ϕ;α)·Φ(i,x,Γ) 2(A, ϕ;α)Φ(i,x,Γ) 0(B, ψ;β)+ Φ(i,x,Γ) 0(A, ϕ;α) 3Über die Komponente (Fq,+) messen wir die Veränderung an dem Eintrag Γi,n−1. 105 5. Lineare Codes über endlichen Kettenringen und Φ(i,x,Γ) 1(A, ϕ;α)(B, ψ;β)= Φ(i,x,Γ) 1(Aα(B), ϕα(ψ); α◦β) = coeff(x) α◦β(θx)·Ai,iα(Bi,i)·τexϕn−1α(ψn−1)−1 = coeff(x) αcoeff(x) (β(θx))θx·Ai,i ·α(Bi,i)·τex(ϕn−1)−1·τexα(ψn−1)−1 =αcoeff(x) (β(θx))·coeff(x) (α(θx)) ·Ai,i ·α(Bi,i)·τex(ϕn−1)−1·ατexψn−1−1 =coeff(x) (α(θx)) ·Ai,i ·τex(ϕn−1)−1·αcoeff(x) (β(θx)) ·Bi,i ·τexψn−1−1 = Φ(i,x,Γ) 1(A, ϕ;α)·αΦ(i,x,Γ) 1(B, ψ;β) = Φ(i,x,Γ) 1(A, ϕ;α)·Φ(i,x,Γ) 2(A, ϕ;α)Φ(i,x,Γ) 1(B, ψ;β) sowie Φ(i,x,Γ) 2(A, ϕ;α)(B, ψ;β)= Φ(i,x,Γ) 2(Aα(B), ϕα(ψ); α◦β) =α◦β=α◦β= Φ(i,x,Γ) 2(A, ϕ;α)◦Φ(i,x,Γ) 2(B, ψ;β) Es sei nun wie im Hilfssatz Γ∈Rk×n,λ,µ eine Generatormatrix, so dass CFG(Γ∗,[n−1]) = Γ∗,[n−1] in reduzierter Zeilenstufenform ist. Die zum Beweis der Aussage für i∈[k] und x∈[m]eingeführte Abbildung Φ(i,x,Γ) ermöglicht es uns nun, Algorithmen zur Berechnung von CanG(Γ) anzugeben. Wir gehen dabei wie folgt vor: •Der Algorithmus 5.1 beschreibt zunächst das Vorgehen, um den Koeffizienten coeff(x) (Γi,n−1)des Spalteneintrags Γi,n−1unter der Gruppenoperation von GΓ,(i,x) zu minimieren. Hier nutzen wir den Gruppenhomomorphismus Φ(i,x,Γ) aus. •In den Algorithmen 5.2 und 5.3 werden dann die beiden Situationen shp(Γ) = shp(Γ∗,[n−1])bzw. shp(Γ) 6= shp(Γ∗,[n−1])getrennt voneinander untersucht. In den Algorithmen werden wir auch auf folgende, leicht zu verifizierende Eigenschaft der Gruppen GΓ,(i,x)zurückgreifen: 5.1.44 Hilfssatz. Für beliebiges i∈[k],x∈[m]und (A, ϕ;α)∈GΓ,(i,x)ist G(A,ϕ;α)Γ,(i,x+1) = (A, ϕ;α)GΓ,(i,x+1)(A, ϕ;α)−1 Beweis. Dies lässt sich leicht aus der Definition der Gruppen als Stabilisatoren herleiten. 106 5.1. Generatormatrizen Algorithmus 5.1 MinStep Input: i∈[k−1] ,x∈[m] Input: Γ∈Rk×n,λ,µ so dass CFG(Γ∗,[n−1])=Γ∗,[n−1] in reduzierter Zeilenstufenform Input: E:= (Ej)j∈[s+1] Erzeugendensystem der Gruppe hEi=GΓ,(i,x)mit •hE[j]ihE[j+1]ifür alle j∈[s+ 1] mit hE[j+1]i/hE[j]i ≃ Zej •für alle j∈[s]gilt Φ(i,x,Γ) 2(Ej) = idFqund ej6=p⇐⇒ ej|(q−1) •es= ord(Φ(i,x,Γ) 2(Es)) Output: Γ0∈GΓ,(i,x)Γmit coeff(x) Γ0 i,n−1minimal unter allen Bahnenelementen Output: T∈GΓ,(i,x):TΓ = Γ0und E0Erzeugendensystem von GΓ0,(i,x+1) 1: procedure MinStep(i, x, Γ, E) 2: E0←() 3: (aj, bj, αj)←Φ(i,x,Γ)(Ej)für alle j∈[s+ 1] 4: V← {0Fq}// als Fp-Untervektorraum von (Fq,+) 5: B← ∅ // Indizes zu einer Basis von V 6: W← {0Fq},B0← ∅ 7: for j∈[s+ 1] do 8: if j6=s∧bj= 1Fqthen 9: if aj∈Vthen 10: bestimme x∈[p]B, so dass aj+P`∈Bx`a`= 0 11: Append(E0,Q`∈BEx` `Ej) 12: else 13: V← hV, aji// als Fp-Untervektorraum von Fq 14: Append(B, j) 15: Append(E0,(Ik,1n; idR)) 16: else 17: (ea,eb, eα)←(aj, bj, αj),z←1 18: W0←W 19: while @a0∈W0:ea+eb·eα(a0)∈Vdo 20: W←W∪ {ea+eb·eα(a0)|a0∈W0} 21: z←z+ 1 22: (ea,eb, eα)←(ea,eb, eα)·(aj, bj, αj)// = (aj, bj, αj)z 23: bestimme x∈[p]Bund y`0∈[e`0]für `0∈B0, so dass Φ(i,x,Γ) 0Ez jY `0∈B0 Ey`0 `0+X `∈B x`a`= 0 24: Append(E0,Q`∈BEx` `Ez jQ`0∈B0Ey`0 `0) 25: B0←B0∪ {j} 26: // Ende for 107 5. Lineare Codes über endlichen Kettenringen Algorithmus 5.1 MinStep (Fortsetzung) 27: (v, w)←argmin (v0,w0)∈V×Wcoeff(x) (Γi,n−1) + w0+v0 28: bestimme x∈[p]B:P`∈Bx`a`=v 29: bestimme y`0∈[e`0]für `0∈B0mit Φ(i,x,Γ) 0Q`0∈B0Ey`0 `0=w 30: T←Q`∈BEx` `·Q`0∈B0Ey`0 `0 31: E0←TE0 jT−1j∈[s+1] // siehe Bemerkung 5.1.46 32: return (TΓ, T, E0) 5.1.45 Hilfssatz. Algorithmus 5.1 ist korrekt. Beweis. Um auf verschiedene Variablenbelegungen während des Ablaufs des Algorithmus zugreifen zu können, bezeichne die mit [j+ 1] indizierten Variablen V[j+1],W[j+1], B[j+1] den Wert der Variablen V, W, B nach Abschluss von Zeile 25 in Algorithmus 5.1 zum Index j∈[s+ 1]. Außerdem sei die Variablenbelegung direkt nach der Initialisierung mit [0] indiziert. Für den Beweis zeigen wir zunächst induktiv, dass für alle j∈[s+ 1] die folgende Hilfsaussage gilt: V[j]=a`|`∈B[j]Fp= Φ(i,x,Γ) 0hE[j]i ∩ kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2 (5.3) [ w∈W[j]w+V[j]= Φ(i,x,Γ) 0hE[j]i(5.4) hE0 [j]i= Φ(i,x,Γ) 0 −1(0) ∩ hE[j]i(5.5) Der Induktionsstart j= 0 entspricht den initialisierten Variablen. Diese erfüllen ganz offensichtlich die gemachten Aussagen. Für den Induktionsschritt von jnach j+ 1 unterscheiden wir nun die beiden Fälle analog zu der If-Bedingung in Zeile 8: 1. Fall (j6=s∧bj= 1Fq): Jedes beliebige Gruppenelement (A, ϕ;α)∈ hE[j+1]ilässt sich in der Form (A, ϕ;α) = Ez j(B, ψ;β)mit z∈Nund (B, ψ;β)∈ hE[j]idarstellen. Um Gleichung (5.3) zu beweisen, sei nun (A, ϕ;α)∈ hE[j]i ∩ kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2 beliebig. Da auch Ej∈kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2im Kern liegt, ist (B, ψ;β)ebenfalls ein Element dieser Untergruppe, und es gilt Φ(i,x,Γ) 0(A, ϕ;α) = Φ(i,x,Γ) 0(Ez j(B, ψ;β)) ∈zaj+V[j]⊆V[j+1]. Umgekehrt lässt sich aber auch aufgrund der Induktionsvoraussetzung jedes Element v∈V[j+1] als Summe v=Pb∈B[j+1] zbabmit zb∈[p]darstellen. Das Gruppenelement Qb∈B[j+1] Ezb bliegt im Kern von Φ(i,x,Γ) 1oΦ(i,x,Γ) 2und es ist Φ(i,x,Γ) 1(Qb∈B[j+1] Ezb b) = v. 108 5.1. Generatormatrizen Damit ist die Aussage der Gleichung (5.3) in beiden Teilfällen aj∈V[j]bzw. aj6∈ V[j] gezeigt. Gleichung (5.4) zeigt man analog. Die Gültigkeit von Gleichung (5.5) ergibt sich aus dem Untergruppendiagramm kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2∩ hE[j+1]i kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2∩ hE[j]ikerΦ(i,x,Γ)∩ hE[j+1]i kerΦ(i,x,Γ)∩ hE[j]i ejp|B[j+1]| p|B[j]| Die angegebenen Indizes der jeweiligen Untergruppen lassen sich leicht über den Homomorphiesatz, also über die Mächtigkeiten der Bilder schließen. Ist nun aj∈V[j], so ist |B[j+1]|=|B[j]|und daher der Index von kerΦ(i,x,Γ)∩ hE[j]iin kerΦ(i,x,Γ)∩ hE[j+1]i gleich ej. Man überlegt sich leicht, dass der neu hinzugenommene Erzeuger E0 jin Zeile 11 genau den nötigen Anstieg der Gruppenordnung bewirkt. Im Fall von aj6∈ V[j]ist aber pein Teiler von ejund damit ej=p. Damit sind aber die Gruppen kerΦ(i,x,Γ)∩ hE[j]iund kerΦ(i,x,Γ)∩ hE[j+1]iin diesem Fall gleich. 2.Fall (j=s∨bj6= 1Fq): Wir beginnen wieder mit dem Beweis der Aussage (5.3). Falls j < s gilt, so ist ejein Teiler von (q−1). Also sind auch die Quotienten kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2∩ hE[j+1]i kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2∩ hE[j]i bzw. Φ(i,x,Γ) 0hE[j+1]i ∩ kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2 Φ(i,x,Γ) 0hE[j]i ∩ kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2 Teiler von ejbzw. (q−1). Hieraus schließen wir, dass V[j+1] = Φ(i,x,Γ) 0hE[j+1]i ∩ kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2 = Φ(i,x,Γ) 0hE[j]i ∩ kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2=V[j] gelten muss. Im Spezialfall j=skönnen wir nicht über die Teilbarkeit argumentieren, da möglicherweise der Index esein Vielfaches von pist. Wir nutzen in dieser Situation die Tatsache, dass für beliebiges (B, ψ;β)∈ hE[s+1]ieine Gleichung der Gestalt: idFq= Φ(i,x,Γ) 2Ez0 s(B, ψ;β)=αz0 s◦idFqfür ein z0∈Z sofort αz0 s= idFqund somit z0≡0 mod esimpliziert. Hieraus ergibt sich V[s+1] =V[s], denn es ist kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2∩ hE[s+1]i= kerΦ(i,x,Γ) 1oΦ(i,x,Γ) 2∩ hE[s]i. 109 5. Lineare Codes über endlichen Kettenringen Genauso zeigt man auch, dass die separate Behandlung der Fälle x≥m−λk−1in Zeile 26 korrekt ist. Nun gehen die weiteren Erzeuger (A(i,j,h),1n; idR)j∈[r],h∈[λk−1]ein. Hier tritt die von uns oben beschriebene Situation auf, dass die Bilder dieser Erzeuger eine Basis von V=Fr pim Algorithmus MinStep bilden. Für die weiteren Beobachtungen nehmen wir an, dass der kanonische Repräsentant CFG(Γ) = Γ induktiv über eine Folge der Algorithmen 5.2 und 5.3 ausgehend von einer beliebigen umrisstreuen Matrix Γ0∈GΓberechnet wurde. 5.1.50 Bemerkung. In der Zeile 8 von Algorithmus 5.2 und in Zeile 12 von Algorithmus 5.3 würde es genügen, jeweils das letzte Element von Fund E(Q)zu übergeben, da alle weiteren Elemente nachweislich im Kern von Φ(i,x,Γ) liegen. Wir beenden diesen Abschnitt mit einer Abschätzung der Kardinalität des Erzeugendensystems E. Sie beeinflusst maßgeblich die Laufzeit des Backtrackalgorithmus. Wir zeigen, dass diese Zahl im Wesentlichen von r,λund der Länge der Normalreihe (4.2) abhängt. 5.1.51 Hilfssatz. Mit osei die Länge der Kompositionsreihe von AutTgemäß (4.2) bezeichnet. Die Anzahl der Erzeuger der Gruppe StabG(Γ), welche in den Algorithmen 5.2 und 5.3 zurückgegeben4werden, ist stets durch pΓ+rX j∈[k] λj+o nach oben beschränkt. Beweis. Alle neuen Erzeuger, die zu Beginn von Algorithmus 5.2 in der Folge Fzur Verfügung gestellt werden, werden auch wieder in den Aufrufen von MinStep entfernt. Dabei hängt der Zeitpunkt von der Verteilung der Höhen in der Spalte Γ∗,n−1ab. Der Eintrag Γi,n−1mit der Höhe m−µn−1garantiert aber, dass alle Erzeuger aus Fbei dessen Kanonisierung entfernt werden. Bei einer Vereinigung von Qmit P0kann man überdies leicht aus der vorausgegangenen Bemerkung und dem Ablauf von Algorithmus 5.1 schließen, dass sich dort ebenfalls die Länge des Erzeugendensystems um eins verringert. In Algorithmus 5.3 werden dahingegen r(µn−1−1) + 1 weitere Erzeuger in der Folge Fzur Verfügung gestellt. Wir unterscheiden zwei Teilfälle: Ist µn−1=λk−1so handelt es sich um eine Spalte, bei welcher wir alle weiteren Nichtnulleinträge über eine Addition mit dem Pivotelement zu 0transformieren können. Damit bleiben alle neu hinzugenommenen Erzeuger erhalten. Dies deckt sich aber mit der Behauptung. Ist hingegen µn−1> λk−1, so gibt es mindestens einen Eintrag der Höhe m−µn−1. Für diesen können wir wie oben schließen, dass alle Spaltenmultiplikationen der Gestalt 4Die Aussage basiert auf der Annahme, dass Algorithmus 5.1 gemäß Bemerkung 5.1.47 modifiziert wurde. 116 5.2. Ein Kanonisierer 1+aθxfür 1≤x≤µn−1−λk−1−1und a∈R∗nicht durch eine Addition des Pivotelement ausgeglichen werden können. Es werden also mindestens r(µn−1−λk−1−1) Erzeuger aus Fin den Aufrufen der Subroutine MinStep in den Zeilen 12 und 21 auch wieder entfernt. Somit bleiben höchstens r(µn−1−1) −r(µn−1−λk−1−1) = rλk−1 neu hinzugefügte Erzeuger auch nach Abschluss von Algorithmus 5.3 erhalten. Über eine Induktion erhält man damit die angegebene obere Schranke. 5.1.52 Folgerung. Die Mächtigkeit der Gruppe StabG(Γ) ist höchstens (q−1)pΓ·qPk−1 i=0 λi· |AutT|. 5.2. Ein Kanonisierer Nun sind alle Grundlagen gelegt, um einen Kanonisierer CanRk×n,λ,µ GoSP0für die Operation der Gruppe GoSP0mit G:= GLλ(R)/Nλ(R)×(R∗)n/(R∗)µoAutT auf der Menge aller Generatormatrizen Γ∈Rk×n,λ,µ zu entwickeln. Für die zugehörigen linearen Codes können wir das Ergebnis als eine Kanonisierung unter der Operation der Gruppe aller semilinearen Isometrien von Rninterpretieren. Wie wir bereits in Abschnitt 2.3.1 beobachten konnten, ist die Gruppe aller semilinearen Isometrien die maximale Untergruppe der Isometriegruppe, welche lineare Codes auf lineare Codes abbildet. Somit ist der hier betrachtete Äquivalenzbegriff für lineare Codes, der allgemeinst Mögliche, welcher sich noch als eine Gruppenoperation auf der Menge aller linearen Codes beschreiben lässt. Die beiden schwächeren Äquivalenzbegriffe – Permutationsisometrie und lineare Isometrie – ergeben sich dann leicht durch die entsprechenden Einschränkungen auf die jeweiligen Untergruppen GLλ(R)/Nλ(R)bzw. GLλ(R)/Nλ(R)×(R∗)n/(R∗)µ. Mit Γ∈Rk×n,λ,µ sei nun bis auf Weiteres immer diejenige Generatormatrix bezeichnet, für welche wir die Kanonisierung durchführen werden. Wir beschreiben, wie wir einen Suchbaum T(Γ, G oSP0)gemäß Abschnitt 3.3 aufbauen werden. Die Partitionierung ist dort bereits über die Individualisierung von Koordinaten i∈[n]fest vorgeschrieben worden. Die Verfeinerung Vsetzt sich aus einer iterierten Anwendung der inneren Kanonisierung V(im), siehe auch Abschnitt 3.3.1, und der äußeren Verfeinerung V(a) zusammen. Diese Funktionen sind noch nicht näher spezifiziert und müssen nun von uns bereitgestellt werden. Insbesondere werden wir hierbei auch garantieren, dass nur die Nebenklassenvertreter C(GoSP0)zu den speziellen Untergruppen L(GoSP0)aus Gleichung (3.6) als Bilder auftreten werden. 117 5. Lineare Codes über endlichen Kettenringen Im Rahmen der äußeren Verfeinerung V(a)werden wir iteriert verschiedene Familien fHoSPHoSP∈L(GoSP0)von HoSP-Homomorphismen zur Anwendung bringen. Für das weitere Vorgehen ist zunächst an dieser Stelle nur entscheidend, dass diese H-invariant sind. Für Γ∈Rk×n,λ,µ und (g;π)∈GoSP0sind damit die Bilder V(a)(Γ, H oSP(g;π)) der äußeren Verfeinerung stets Rechtsnebenklassen von HoSQfür eine kanonische Partition QP. Wir gehen nun wie folgt vor. Im ersten Abschnitt 5.2.1 werden wir zunächst beschreiben, wie wir aus dem vorangegangenen Abschnitt 5.1.2 eine effiziente innere Kanonisierung V(im) gewinnen werden. Die Definition der Homomorphismen fHoSPzur Definition der äußeren Verfeinerung folgt dann in Abschnitt 5.2.2. Die gewählte Ordnung auf Rbeeinflusst die Definition des kanonischen Repräsentanten CanRk×n,λ,µ GoSP0(Γ) maßgeblich. Insbesondere ist die Ordnung von der Wahl von θund ξ abhängig. In Abschnitt 5.2.3 werden wir daher diskutieren, ob wir die Resultate von verschiedenen Kanonisierungen, etwa zu einem isomorphen Kettenring R0oder bei anderer Wahl von ξund θ, miteinander vergleichen können. 5.2.1. Innere Kanonisierung Die innere Kanonisierung wurde in Abschnitt 3.3.1 in Abhängigkeit der Funktionen Πi:X→Y(i), von Kanonisierern CanY(i) Hfür alle H≤Gund einer Fixierreihenfolge F:X× L(GoSP0)→[n]≤nbeschrieben. Wir beginnen aus diesem Grund unsere Beschreibung zunächst mit der Definition der Abbildung Πifür i∈[n] Πi:Rk×n,λ,µ →Rk R,Γ7→ Γ∗,i als Projektion auf die i-te Spalte der Matrix. Schränken wir die Menge der Spaltenvektoren auf das Bild Y(i):= Πi(Rk×n,λ,µ)ein, so können wir auf diesem eine natürliche Operation von GoStabSP0(i)definieren: Für (A, ϕ;α, π)∈GoStabSP0(i)und γ∈Πi(Rk×n,λ,µ)setzen wir (A, ϕ;α, π)γ:= Aα(γ)ϕ−1 i. Mit dieser Definition ist Πiganz offensichtlich ein (GoStabSP0(i))-Homomorphismus, welcher StabSP0(i)-invariant ist. Damit erfüllt Πidie in Abschnitt 3.3.1 beschriebenen Anforderungen. Als nächsten Schritt stellen wir für die Untergruppen H≤Gdie Kanonisierer CanY(i) H für die Operation von Hauf Y(i)zur Verfügung. Dies gestaltet sich für beliebige Untergruppen H≤Gund Spaltenvektoren γ∈Y(i)als schwierigeres Problem. Jedoch können wir über die Fixierreihenfolge (Definition 3.3.4) und unser Wissen, dass nur gewisse Nebenklassen HoSP(g;π)∈ C(GoSP0)auch tatsächlich im Backtracking vorkommen, die Kombinationen (H, γ := Πi((g;π)Γ)) steuern. Aus diesem Grund wollen wir uns noch einmal kurz vergegenwärtigen, in welcher Situation wir im Backtracking zu einem Knoten (HoSP(g;π), j)von T(Γ, G oSP0) eine Kanonisierung CanY(i) H(γ)durchführen werden: Es sei f= (f0, . . . , fn0−1)dasjenige injektive Wort der Länge n0< n mit Einträgen aus [n]\ {i}, welches die Reihenfolge der bereits fixierten und unter Gminimierten Spalten angibt. Dann ist (g;π)Γ ein 118 5.2. Ein Kanonisierer Algorithmus 5.4 InnerCan Input: PP0kanonische Partition Input: f∈FixSP([n])0nfür ein n0∈[n+ 1] Input: Γ∈Rk×n,λ,µ f-semikanonisch, d.h. CFG(Πf(Γ)) = Πf(Γ) Output: Fixierreihenfolge F(Γ, G(f,Γ) oSP) 1: procedure InnerCan(P, f, Γ) 2: ˜ f←() 3: F←FixSP([n]) \ {fj|j∈[n0]} 4: while F6=∅do 5: k0←rg(Πf+˜ f(Γ)) 6: for e∈Fdo// in lexikographischer Reihenfolge 7: x←perΓ[k]\[k0], e 8: if x∈ {0, λk0}then 9: (A, ϕ;α)←TRY(e) G(f+˜ f,Γ) (Γ∗,e)// falls x= 0 rufe Algorithmus 5.2, sonst Algorithmus 5.3 10: Γ←(A, ϕ;α)Γ 11: ˜ f←˜ f+ (e) 12: F←F\ {e} 13: if x=λk0then 14: break // verlasse die For-Schleife 15: return f+˜ f f-semikanonischer Repräsentant der Bahn GπΓ, d.h. Πf((g;π)Γ) = CFG(Πf((g;π)Γ)), und H=G(f,πΓ) = StabG(Πf((g;π)Γ)) dessen Stabilisator. Die Koordinate i∈[n]wurde fixiert und die Spalte γ= Πi((g;π)Γ) soll nun unter Hminimiert werden. Ist die Matrix Πf+(i)((g;π)Γ) umrisstreu, so korrespondiert dies aber genau mit den Situationen, welche wir mit den Algorithmen 5.2 und 5.3 behandeln können. Aus diesem Grund werden wir also nun garantieren, dass die von uns gewählte Fixierreihenfolge stets zu umrisstreuen Matrizen Πf+(i)((g;π)Γ) führt. Wir kombinieren hierzu die Definition der Fixierreihenfolge mit der inneren Kanonisierung, da uns dies die Beschreibung wesentlich vereinfacht. Wir beschreiben unser Vorgehen algorithmisch, siehe Algorithmus 5.4. Die Untergruppe H=G(f,πΓ) übergeben wir dem Algorithmus über die Angabe von fund πΓ. 5.2.1 Satz. Der Algorithmus 5.4 definiert eine Fixierreihenfolge, indem wir parallel zum Backtracking den benötigten Funktionswert für den Knoten ((HoSP)(g;π), j)im Baum T(Γ, G oSP0)durch F((g;π)Γ,(HoSP)) := InnerCan(P, F(Γ,(HoSP)(g;π), j),(g;π)Γ) bestimmen. 119 5. Lineare Codes über endlichen Kettenringen Beweis. Zunächst zeigen wir, dass die Funktion wohldefiniert ist. In einem ersten Schritt lösen wir dazu die Abhängigkeit von jauf. Es sei also zunächst jminimal, so dass ((HoSP)(g;π), j)ein Knoten im Baum T(Γ, G oSP0)ist. Wir bezeichnen mit f:= F(Γ,(HoSP)(g;π), j)und ˜ f:= InnerCan(P, f, (g;π)Γ) die getroffene Koordinatenauswahl. Ein Konflikt kann nur dann auftreten, wenn der Sohn nach der inneren Kanonisierung von der Gestalt ((HoSP)(g;π), j + 1) ist. Dann ist aber (g;π)Γ bereits ˜ f-semikanonisch und H=G(˜ f,πΓ). Diese Tatsache kann man nun nutzen um zu zeigen, dass dann der Algorithmus für die modifizierte Eingabe ˜ f=f+˜ feine identische Ausgabe generiert ˜ f=InnerCan(P,˜ f, (g;π)Γ). Da aber für alle weiteren Knoten ((HoSP)(g;π), j0)mit j0> j der Funktionsaufruf F(Γ,(HoSP)(g;π), j0)gerade die Folge ˜ fzurück gibt, ist die Unabhängigkeit von dem Iterationszähler jgezeigt. Als nächstes beweisen wir, dass die Funktion auch von dem aktuell betrachteten Backtrackbaum unabhängig ist. Dazu sei ˜ Γ∈Rk×n,λ,µ eine weitere Generatormatrix und (˜g, ˜π)∈GoSP0ein Gruppenelement mit (˜g, ˜π)˜ Γ=(g;π)Γ, so dass ((HoSP)(˜g, ˜π), i) ein Knoten im Baum T(˜ Γ, G oSP0)ist. Somit ist (˜g, ˜π)−1(g;π)Γ = ˜ Γund beide Bäume isomorph5. Damit können wir auch ohne Beschränkung der Allgemeinheit j=i annehmen. Mit der Gleichheit F(Γ,(HoSP)(g, π), j) = F((˜g, ˜π)−1(g;π)Γ,(HoSP)(g, π)(˜g, ˜π)−1(g;π)−1, j) =F(˜ Γ,(HoSP)(˜g, ˜π), j) ist dann die Wohldefiniertheit der Funktion bewiesen. Es bleibt die geforderten Eigenschaften einer Fixierreihenfolge zu zeigen. Ohne Beschränkung der Allgemeinheit können wir hierbei auch (g;π) = (1G; idn)voraussetzen. Ganz offensichtlich ist die resultierende Folge injektiv und beinhaltet nur Fixpunkte von SP. Ist nun (h;σ)∈HoSPbeliebig, so ist F((h;σ)Γ,(HoSP)) =InnerCan(P, F(Γ,(HoSP)(h;σ), j),(h;σ)Γ) =InnerCan(P, F(Γ,(HoSP), j),(h;σ)Γ) =InnerCan(P, F(Γ,(HoSP), j),Γ) Für den Beweis der letzten Gleichheit ist zunächst die Beobachtung entscheidend, dass σ∈SPdie Koordinaten e∈FixSP([n]) unverändert lässt und unser Vorgehen nur auf dieser Spaltenauswahl beruht. Somit können wir ohne Beschränkung der Allgemeinheit auch σ= idnannehmen. Die H-Invarianz des Resultats zeigt man über eine einfache Induktion, wir überlassen diese dem Leser. 5Genauer gesagt, können wir dies nur induktiv für den Teilbaum bis zu dieser Tiefe zeigen, da in einem derartigen Beweis auch die aktuell zu beweisende Aussage eingehen müsste. 120 5.2. Ein Kanonisierer Wir haben nun damit die notwendigen Voraussetzungen geschaffen, um die innere Kanonisierung gemäß Abschnitt 3.3.1 zu implementieren. Insbesondere können wir nun auch im nächsten Abschnitt, welcher die äußere Verfeinerung behandelt, unser sehr umfangreiches Wissen über die Stabilisatoren G(f,πΓ) einbringen. 5.2.2. Äußere Verfeinerung Wie bereits angedeutet, wird die äußere Verfeinerung V(a)selbst wieder aus einer iterierten Anwendung des Homomorphieprinzips hervorgehen. In diesem Abschnitt wollen wir nun die Familien von HoSP-Homomorphismen angeben, welche wir zur Definition der Verfeinerung V(a)nutzen werden. Auf die exakte Beschreibung der Anwendungsreihenfolge der nachfolgenden eingeführten Homomorphismen werden wir aus folgendem Grund nicht mehr weiter eingehen: Die Güte einer Verfeinerung hängt zu stark von der aktuellen Eingabe (d.h. dem aktuellen Knoten im Backtracking) und den bereits durchgeführten Verfeinerungen ab. Eine Untersuchung aller möglichen Verfeinerungen und deren gegenseitige Beeinflussung im Rahmen einer iterierten Verfeinerung gestaltet sich als ein sehr umfangreiches und kaum abschließbares Unterfangen. Die Festlegung einer optimalen Strategie für jede beliebige Eingabe Γ∈Rk×n,λ,µ ist also kaum zu gewährleisten. Wir bemerken hierzu aber auch, dass das eingabespezifische Verhalten der Verfeinerungen bereits bei der Kanonisierung von Graphen zu beobachten ist. Auch hier ist die Festlegung der Reihenfolge, der zur Anwendung zu bringenden Verfeinerungen, immer noch Gegenstand eines über dreißig Jahre währenden und anhaltenden Entwicklungsprozesses. Eine geeignete Festlegung der Reihenfolge der Verfeinerungen für die Kanonisierung linearer Codes erfolgte bislang nur auf Grundlage der Beobachtung verschiedener Instanzen und ist immer noch Gegenstand aktueller Untersuchungen. Wir geben nun also im Folgenden nur eine Auswahl möglicher Familien von HoSP-Homomorphismen zur möglichen Definition von äußeren Verfeinerungen. Wir haben bereits festgestellt, dass wir nicht für alle Untergruppen HoSP∈ L(GoSP0)einen HoSP-Homomorphismus fHoSP:Rk×n,λ,µ →Zn in eine geeignete, geordnete Menge Zzur Verfügung stellen müssen. In unserem Fall genügt es, sich auf Untergruppen HoSPzu beschränken, welche als Beschriftung eines Knotens (HoSP(g;π), j)in einem Backtrackbaum T(Γ, G oSP0)zu einer Matrix Γ∈Rk×n,λ,µ auftreten. Zum Beispiel wissen wir stets, dass H=G(f,πΓ) für f:= F(Γ, H oSP(g;π), j)gilt. Daher können wir den Definitionsbereich der Homomorphismen fHoSPauf die Menge der Matrizen [ (g;π),Γ wie oben (HoSP)((g;π)Γ) einschränken. 121 5. Lineare Codes über endlichen Kettenringen Einen ersten Typus von Verfeinerungen erhalten wir aus der Beobachtung der Operation der Gruppe G(f,πΓ) auf (g;π)Γ. Es gilt: 5.2.2 Hilfssatz. Für alle HoSP∈ L(GoSP0)definiert die Funktion f(inn) HoSP:Rk×n,λ,µ →(Rk)n,Γ7→ (CFH(Γ∗,i))i∈[n] einen HoSP-Homomorphismus, welcher H-invariant ist. Beweis. Trivial. Der Funktionswert f(inn) G(f,πΓ)oSP((g;π)Γ) lässt sich mit den Algorithmen aus dem Abschnitt 5.2.1 berechnen. Jedoch bedeutet diese Berechnung bereits einen erheblichen Aufwand, falls die Anzahl der Erzeuger der Gruppe G(f,πΓ) für f:= F(Γ, H oSP(g;π), j) groß ist. Aus den Homomorphismen f(inn) HoSPlassen sich aber auf vielfältigste Weisen Abschwächungen entwickeln. Formal erhalten wir sie durch Komposition mit einem weiteren SP-Homomorphismus. Jedoch haben wir dann im Allgemeinen bessere Methoden zur Verfügung, um das Bild der Komposition zu berechnen. Hierzu mehrere Beispiele: •Es sei κ:= rg(Πf(πΓ)) < k, dann können wir die Matrix f(inn) G(f,πΓ)oSP((g;π)Γ) auf die Zeile mit Index κprojizieren. Diese Funktion definiert also ebenfalls einen G(f,πΓ) oSP-Homomorphismus f(per,κ) G(f,πΓ)oSP. Andererseits rechnet man leicht nach, dass für i∈[n]und h∈[m+ 1] der Eintrag f(per,κ) G(f,πΓ)oSP((g;π)Γ)igenau dann gleich θhist, wenn per((g;π)Γ)[k]\[κ],i=m−hgilt. Mit dieser Äquivalenz lässt sich das Bild des Homomorphismus sehr viel leichter direkt bestimmen. •Eine zweite Alternative gewinnt man, indem man für jedes i∈[n]den Träger der Spalte f(inn) G(f,πΓ)oSP((g;π)Γ)∗,i bestimmt. Man kann sich auch auf den Schnitt mit einer fest vorgegebenen Teilmenge von [κ]beschränken. •Eine weitere Möglichkeit besteht darin, im Anschluss an die Abbildung f(inn) G(f,πΓ)oSP eine Reduktion modulo einem Ideal Rad(R)xfür x∈[m]durchzuführen. Auch hier können wir die Algorithmen aus dem Abschnitt 5.1.2 abwandeln und somit den Funktionswert effizienter berechnen. Diese Liste von Vorschlägen stellt nur eine kleine Auswahl der Möglichkeiten dar. Wir gehen wegen ihrer Vielzahl auf weitere, so gewonnene Homomorphismen auch nicht mehr weiter ein, zumal sie im Allgemeinen zu Beginn des Backtrackings nicht ausreichend gute Verfeinerungen liefern. Gerade hier ist es aber wichtig, die Anzahl der Kinder eines Knotens möglichst gering zu halten. Aus diesem Grund werden wir auch bei den Knoten geringer Tiefe größere Rechenzeiten zur Berechnung der Verfeinerung aufwenden. 122 5.2. Ein Kanonisierer Einen zweiten Typ von Verfeinerungen gewinnen wir über einen alternativen Ansatz. Wir werden hierzu aus der Generatormatrix Γdes R-linearen Codes Ceinen bipartiten Graphen (V, E(Γ))gewinnen und die für Graphen zur Verfügung stehenden Verfeinerungen [55] benutzen. Der Graph wird sich im Wesentlichen aus einer Teilmenge der Codewörter von Cergeben. Dieses Vorgehen hat sich bei linearen Codes über endlichen Körpern bereits als sehr nützlich erwiesen, siehe [24, 51]. Homomorphismen zu Wörtern eines vorgeschriebenen Gewichts Im Folgenden sei mit B(V(0), V (1))die Menge aller bipartiten Graphen auf den Punkten V(0) ∪· V(1) bezeichnet. Innerhalb der Knotenteilmengen V(0) bzw. V(1) treten also keine Kanten auf. Wir skizzieren zunächst, wie wir den Graphen (V, E(Γ))gewinnen wollen: Zunächst definieren wir Uλ:= ×k−1 i=0 R/ Rad(R)λi. Diese Menge repräsentiert alle möglichen Informationsvektoren6, welche wir mit der Abbildung Uλ→C (u0+ Rad(R)λ0, . . . , uk−1+ Rad(R)λk−1)7→ (u0, . . . , uk−1)Γ codieren. Der Übergang zu den Nebenklassen R/ Rad(R)λiist notwendig, um eine Bijektion beider Mengen zu erreichen. Informationsvektoren bzw. Codewörter, welche durch Linksmultiplikation mit Ringelementen auseinander hervorgehen, wollen wir im weiteren Verlauf zusammenfassen. Aus diesem Grund beschränken wir uns auch auf diejenigen Vektoren u∈U0 λ:= nu0∈Uλ| ∃ i∈[k] : u0 i∈(R/ Rad(R)λi)∗o, welche mindestens eine Einheit enthalten. Da zwei Vektoren u, v ∈U0 λgenau dann den gleichen Modul erzeugen, wenn sie durch Multiplikation mit einer Einheit auseinander hervorgehen, werden wir in unserer Formulierung von den Bahnen R∗\\U0 λzu den zyklischen Linksuntermoduln Uλ:= {Ru |u∈U0 λ}von U0 λübergehen. Mit nλ:= |Uλ|werden wir die entsprechende Kardinalität dieser Menge bezeichnen. 5.2.3 Bemerkung. Wieder werden wir im weiteren Verlauf keine formale Unterscheidung zwischen den Elementen (u0+ Rad(R)λ0, . . . , uk−1+ Rad(R)λk−1)∈Uλund den Vektoren (u0, . . . , uk−1)∈Rkvornehmen. Die Wohldefiniertheit der nachfolgenden Definitionen lässt sich jeweils leicht Nachrechnen. Als Knotenmenge des Graphen (V, E(Γ))wählen wir nun V:= [n]∪· Uλ. Die Kantenmenge E(Γ) =Sm j=0 E(Γ,j)partitionieren wir in m+ 1 disjunkte Teilmengen E(Γ,j):= {{i, Ru} | i∈[n], Ru ∈Uλ: per(uΓ∗,i) = j}. Der Graph (V, E(Γ))ist vollständig bipartit, d.h. jeder Knoten aus [n]ist mit jedem Knoten aus Uλbenachbart. Ist u∈Uλbeliebig und wsym(uΓ) = (a0(uΓ), . . . , am(uΓ)), 6Bei der Datenübermittlung werden die zu übertragenden Informationen diesen Vektoren zugeordnet, anschließend codiert und übertragen. 123 5. Lineare Codes über endlichen Kettenringen so sind für jedes j∈[m+ 1] genau aj(uΓ) Kanten aus E(Γ,j)inzident mit dem Knoten Ru ∈Uλ. Die Partitionierung der Kantenmenge können wir auch als eine Färbung mit m+ 1 Farben interpretieren. Operieren wir mit einer Permutation auf diesen kantengefärbten Graphen, so soll die Partitionierung der Kantenmenge hiervon berücksichtigt werden. 5.2.4 Hilfssatz. Es ist (G,Ψ = (idSP0,Ψ1)) mit G:Rk×n,λ,µ → B([n], Uλ)und Ψ1:GoSP0→SUλ Γ7→ (V, E(Γ)) (A, ϕ;α, π)7→ Ru 7→ Rα(u)A−1 ein Homomorphismus von Gruppenoperationen. Beweis. Es seien Γ∈Rk×n,λ,µ,(A, ϕ;α, π)∈(GoSP0),i∈[n]und Ru ∈Uλbeliebig. Weiter sei Γ0:= (A, ϕ;α, π)Γ. Dann gilt per(uΓ∗,i) = per(α(u)α(Γ∗,i)) = perα(u)A−1Aα(Γ∗,i)ϕ−1 π(i)= per(α(u)A−1)Γ0 ∗,π(i) und somit für j∈[m+ 1] {i, Ru} ∈ E(Γ,j)⇐⇒ π(i), α(u)A−1= (Ψ(A, ϕ;α, π)· {i, Ru})∈E(Γ0,j). Es ist also G((A, ϕ;α, π)Γ) = Ψ(A, ϕ;α, π)· G(Γ). Durch den Schritt zu den Graphen G(Γ) haben wir nun ein sehr mächtiges Werkzeug zur Definition weiterer Verfeinerungen an der Hand. Im Backtrackbaum T(Γ, G oSP0) zu Γ∈Rk×n,λ,µ können wir zum Beispiel an einem Knoten ((HoSP)(A, ϕ;α, π), j)den Graphen G((A, ϕ;α, π)Γ) = Ψ(A, ϕ;α, π)· G(Γ) bilden und dann über die Komposition mit einem beliebigen SP-Homomorphismus fP:B([n], Uλ)→ZnEigenschaften der Koordinaten i∈[n]bestimmen. Auch hier haben wir also eine Fülle von Möglichkeiten zur Verfügung, um weitere Verfeinerungen zu gewinnen. Jedoch ist für dieses naive Vorgehen der zu erwartende hohe Aufwand zur Berechnung der Funktionswerte G((A, ϕ;α, π)Γ) und Ψ(A, ϕ;α, π) sehr problematisch. Bevor wir uns diesem Problem zuwenden, wollen wir zunächst eine mögliche Definition eines solchen SP-Homomorphismus fPan einem Beispiel vorführen: 5.2.5 Beispiel. Wir betrachten die Generatormatrix Γ = 1 0 2 0 1 1∈Z2×3 4. Aus ihr erhalten wir den Graphen G(Γ) in Abbildung 5.1a. In diesem konkreten Beispiel ist jeder Knoten i∈[3] mit jeweils der gleichen Anzahl von gefärbten Kanten aus E(Γ,j), j ∈[3] inzident. Wir können also die Knoten i∈[3] zunächst nicht unterscheiden. 124 5.2. Ein Kanonisierer 0 1 2 Z4(1,0) Z4(1,2) Z4(1,1) Z4(1,3) Z4(0,1) Z4(2,1) E(Γ,0) E(Γ,1) E(Γ,2) (a) ungefärbte Knoten 0 1 2 Z4(1,0) Z4(1,2) Z4(1,1) Z4(1,3) Z4(0,1) Z4(2,1) E(Γ,0) E(Γ,1) E(Γ,2) Farbklasse 0 Farbklasse 1 Farbklasse 2 Farbklasse 3 (b) balancierte Färbung des Graphen Abbildung 5.1.: Graph G(Γ) zu Beispiel 5.2.5 Jedoch bemerken wir, dass diese Beobachtung für die Knoten aus Uλnicht gegeben ist. Partitionieren wir die Knotenmenge Z4u∈U(2,2) nach der Färbung der inzidenten Kanten in die angedeuteten Farbklassen, siehe Abbildung 5.1b, so können wir in einem weiteren Schritt die Partition {{0},{1,2}} der Knotenteilmenge [3] gewinnen. Wir wollen nun beweisen, dass wir stets die balancierte Färbung des Graphen G(Γ), vergleiche Beispiel 5.2.5, zur Definition eines SP-Homomorphismus benutzen dürfen. Außerdem werden wir beschreiben, wie wir es vermeiden, Bilder und Urbilder unter dem Homomorphismus Ψ1zu berechnen7. Dazu wechseln wir unsere Sichtweise auf das Problem: Anstatt der Aufgabe Γunter der Operation von GoSP0zu kanonisieren, wollen wir nun eine Kanonisierung des Paars 7Dadurch verlieren wir aber gegebenenfalls auch nützliche Informationen für das Backtracking. Dies ist wieder ein Beispiel für das Abwägen zwischen der Komplexität der Verfeinerung und ihrem Nutzen im Backtrackalgorithmus. 125 6. Modifikationen & Anwendungen Dieses Kapitel soll nun vor allem aufzeigen, dass der Kanonisierer aus dem Abschnitt 5.2 bzw. dessen Implementierung, siehe Kapitel 7, auch für größere und interessante Codes immer noch praktikabel ist und kanonische Repräsentanten vor allem bei Klassifikationsproblemen den entscheidenden Vorteil bringen. Außerdem wollen wir in diesem Kapitel auch mögliche Modifikationen des Algorithmus diskutieren, welche es erlauben, den Kanonisierer auch in weiteren Teilgebieten der angewandten Mathematik, wie etwa der Kryptographie, einzusetzen. Es zeigt sich, dass der von uns beschriebene Ansatz sehr flexibel ist. Wir werden aber auch in Abschnitt 6.2.4 die Grenzen unseres Ansatzes aufzeigen. 6.1. Lineare Codes über Galois-Ringen der Charakteristik 4 6.1.1. Klassifikation verallgemeinerter Teichmüller-Codes In [45, Abschnitt 3.1] wurde eine Familie Tq,k,s von linearen Codes über Galois-Ringen R= GR(4, r)der Charakteristik 4konstruiert, welche hervorragende Parameter besitzen. Wir gehen später nochmals kurz auf die entscheidenden Schritte der Konstruktion ein. Die Codes Tq,k,s werden verallgemeinerte Teichmüller-Codes genannt. Der Parameter q= 2rbeschreibt hierbei, wie bisher, den Restklassenkörper Fq≃R/ Rad(R). Über die Gray-Abbildung können wir die verallgemeinerten Teichmüller-Codes Tq,k,s der Länge n:= 2sqk−1 q−1mit den linearen Codes der Länge nq und der gleichen Mächtigkeit q2küber Fqvergleichen. Die Hamming-Minimaldistanz des Bildes unter der GrayAbbildung ist in vielen Fällen besser als diejenige, welche alle bekannten linearen Codes mit gleichen Parametern erreichen. Die verallgemeinerten Teichmüller-Codes sind also BTKL-Codes. Das Konstruktionsprinzip zur Definition dieser Codes nutzt die in Folgerung 3.1.10 gemachte Beobachtung über den Zusammenhang zwischen linearen Codes und den Multimengen der von den Spalten einer Generatormatrix erzeugten, zyklischen R-Rechtsmoduln. Der Code Tq,k,s bestimmt sich hierbei über die Auswahl einer geeigneten Teilmenge Tq,k,s der Punktmenge (freie Moduln vom Rang 1) der projektiven Rechts-HjelmslevGeometrie PHG(Rk R),k≥2. Wir werden die notwendigen Schritte zur Definition der Punktmenge Tq,k,s nur kurz skizzieren, für Details verweisen wir auf Originalliteratur [45]: 133 6. Modifikationen & Anwendungen 1. Man betrachtet eine Ringerweiterung GR(4, r)⊆GR(4, rk) =: Sund nutzt die Isomorphie der freien R-Rechtsmoduln SRund Rk R. 2. Anschließend wählt man einen Untervektorraum Udes F2-Vektorraums Fqkder Dimension dim(U) = s+r, welcher Fqenthält. Dieser definiert eine Untergruppe R∗≤ΣU≤S∗der multiplikativen Gruppe und induziert eine Punktmenge pts(ΣU) := {xR |x∈ΣU⊂S}der Kardinalität 2sqk−1 q−1. 3. Für gewisse Einschränkungen an sund an die Unterräume U, siehe [45, Satz 3.1.8], setzen wir die Punktmenge T(U) q,k,s gleich pts(ΣU). In den Fällen s= 0 bzw. s= (k−1)rexistiert genau ein solcher Unterraum U=Fq bzw. U=Fqk. Daher ist der Code Tq,k,s bis auf Isomorphie eindeutig bestimmt. In allen weiteren Fällen gibt es jedoch für fest gewählte Parameter q, k, s mehrere Möglichkeiten zur Auswahl des Untervektorraums U. Mit den Beispielen 3.1.16 und 3.1.17 in [45] wurde nachgewiesen, dass sich aus den verschiedenen Wahlmöglichkeiten für Uauch nicht isomorphe Z4-lineare Codes T2,5,2bzw. T2,6,1ergeben können. Die Aussage wurde hierbei über eine Implementierung unseres Kanonisierers in C++, siehe Abschnitt 7.2, bewiesen. Wir greifen diese Aussage zu den verallgemeinerten Teichmüller-Codes T2,6,1im Beispiel 6.1.2 nochmals auf. Wir wollen nun diese Untersuchung auch auf die Teichmüller-Codes über dem nächstgrößeren1Galois-Ring GR(4,2) fortsetzen. Bevor wir die Beispiele bearbeiten, bemerken wir an dieser Stelle noch, dass die Automorphismengruppe Aut(Tq,k,s)≤ΓLk(R)der Punktmenge Tq,k,s stets die Ordnung |Aut(Tq,k,s)|=|Aut(Tq,k,s)| |Z(R)|hat. 6.1.1 Bemerkung. Laut [45, Lemma 3.1.7] operiert die Gruppe ΣU/R∗scharf transitiv auf pts(ΣU). Dies erklärt, dass wir im Folgenden stets eine transitive Operation von Aut(Tq,k,s)↓Snauf der Koordinatenmenge [n]des Codes Tq,k,s bzw. von Aut(Tq,k,s)auf der Punktmenge Tq,k,s beobachten können. 6.1.2 Beispiel. Es gibt 16 Unterräume, welche zur Definition eines Z4-linearen Teichmüller-Codes T2,6,1herangezogen werden können. Diese Menge partitioniert sich in •zwei Isomorphieklasse mit je 6Codes, deren Automorphismengruppen jeweils die Ordnung 126 · |Z(Z4)|= 252 haben, •eine Isomorphieklasse mit 3Codes, deren Automorphismengruppen die Ordnung 252 ·2haben, •und einen weiteren, dazu nicht isomorphen Code mit einer Automorphismengruppe der Ordnung 756 ·2. 1Für noch größere Galois-Ringe GR(4, r),r≥3ist die Kardinalität der Codes Tq,k,s bereits zu groß, um sie mit dem Kanonisierer behandeln zu können. 134 6.1. Lineare Codes über Galois-Ringen der Charakteristik 4 Für die Codes aus den ersten beiden Isomorphieklassen beobachten wir eine Rechenzeit zwischen 150 und 220 Sekunden bei einer durchschnittlichen Laufzeit von 190 Sekunden. Bei der dritten Klasse von Codes steigt die durchschnittliche Rechenzeit auf 220 Sekunden an. Für den Code mit der größten Automorphismengruppe beobachten wir einen weiteren Anstieg der Rechenzeit auf ungefähr 4000 Sekunden. Dieser erhebliche Anstieg erklärt sich dadurch, dass der Backtrackalgorithmus im Gegensatz zu den anderen Instanzen auch Blätter erreicht, welche nicht zu der schlussendlich bestimmten kanonischen Form korrespondieren. Gegebenenfalls ließe sich das Laufzeitverhalten mit einer Überarbeitung der eingesetzten äußeren Verfeinerung also noch weiter verbessern. 6.1.3 Beispiel. Zur Definition einer Punktmenge T(U) 4,3,2stehen 20 geeignete Unterräume Uzur Auswahl. Die Menge der resultierenden linearen Codes T(U) 4,3,2und damit auch die Menge der Punktmengen T(U) 4,3,2wird durch die Gruppenoperation in 4Isomorphieklassen partitioniert: •drei dieser Klassen beinhalten je sechs lineare Codes mit einer Automorphismengruppe der Ordnung 84 · |Z(GR(4,2))|, •eine weitere enthält genau zwei lineare Codes mit einer Automorphismengruppe der Ordnung 252 · |Z(GR(4,2))|. 6.1.4 Beispiel. Zur Definition einer Punktmenge T(U) 4,4,2hat man 256 Möglichkeiten zur Wahl des Unterraums U. Jeder verallgemeinerte Teichmüller-Code T(U) 4,4,2hat eine Automorphismengruppe der Ordnung 340·|Z(GR(4,2))|. Je acht Unterräume definieren semilinear isometrische Codes. Ebenso verteilen sich die 320 möglichen Codes T(U) 4,4,4auf 40 Isomorphieklassen mit je 8linearen Codes. Jeder Code T(U) 4,4,4hat eine Automorphismengruppe der Ordnung 1360 · |Z(GR(4,2))|. Laufzeiten zu den hier behandelten und weiteren Beispielen finden sich in der Tabelle 6.1. Bei dem Programmaufruf handelt es sich in allen Fällen um eine Implementierung des Kanonisierers in Sage [70], siehe Abschnitt 7.1.2. Dabei sei mit tmin,tmax und tdie minimale, maximale und durchschnittliche Laufzeit (in Minuten) auf den Instanzen T(U) q,k,s bezeichnet. Die letzte Tabellenspalte gibt die Anzahl der Isomorphieklassen in Abhängigkeit von der Automorphismengruppe und der Anzahl zueinander isomorpher Codes an. Ein Eintrag (a, b)xsoll hier die Bedeutung haben, dass es xIsomorphieklassen von linearen Codes gibt, welche bElemente T(U) q,k,s enthalten und deren Automorphismengruppen jeweils die Ordnung AutT(U) q,k,s=a· |Z(R)|haben. 6.1.5 Folgerung. Die Verteilung aller untersuchten linearen Codes T(U) q,k,s, für U≤Fqk zulässig, auf Isomorphieklassen hat stets die Eigenschaft, dass die Produkte Aut(T(U) q,k,s)·nT(U0) q,k,s | T (U0) q,k,s semilinear isometrisch zu T(U) q,k,so nur von den Parametern q,k,sabhängig sind. 135 6. Modifikationen & Anwendungen q k s tmin tmax t Anzahl Isomorphieklassen nach |Aut(T(U) q,k,s)|und nU0| T (U) q,k,s∼ T (U0) q,k,so 2 4 1 0.040 0.050 0.048 (30,4)1 2 5 2 1.8 3.5 3.0 (124,5)4 2 6 1 2.5 67 7.1 (126,6)2,(252,3)1,(756,1)1 4 3 2 0.69 2.0 1.0 (84,6)3,(252,2)1 4 4 2 25 69 46 (340,8)32 4 4 4 2500 4500 3500 (1360,8)40 Tabelle 6.1.: Laufzeiten der Sage-Implementierung des Kanonisierers für Tq,k,s in Minuten Da für alle x∈Xeiner G-Menge Xstets die Bahnenformel |StabG(x)|·|Gx|=|G| erfüllt ist, legt die obige Beobachtung die folgende Vermutung nahe: 6.1.6 Vermutung. Es existiert eine Gruppenoperation einer (unbekannten) Gruppe G≤(R∗)no(Sn×Aut(R)) auf der Menge der linearen Codes {T (U) q,k,s |U≤Fqkzulässig}, welche die auftretenden Isomorphieklassen und alle Automorphismen vollständig beschreibt. Wir vermuten weiter, dass sich diese Operation aus einer isomorphen Gruppenoperation einer Gruppe G0auf {U|U≤Fqkzulässig}mit Hilfe des Homomorphieprinzips, der Bijektion U7→ T (U) q,k,s und einer Einbettung G0,→G≤(R∗)no(Sn×Aut(R)) ergibt. 6.1.7 Bemerkung. Diese Vermutung wurde bereits von Michael Kiermaier aus dem ausgewerteten Datenmaterial zu dem Galois-Ring Z4= GR(4,1) gezogen. Sie konnte in dieser Arbeit mit der Untersuchung des nächstgrößeren Galois-Rings GR(4,2) nun schließlich untermauert werden. 6.1.2. Automorphismen von verallgemeinerten Kerdock-Codes In [49] wurde die Konstruktion der Z4-linearen Kerdock-Codes auf beliebige GaloisRinge R= GR(4, r)der Charakteristik 4verallgemeinert. Wir wollen nun zunächst diese Verallgemeinerung beschreiben und anschließend die Automorphismengruppe der verallgemeinerten Kerdock-Codes untersuchen und mit unserem Programm berechnen. Wir können hiermit die Korrektheit der Ausgabe verifizieren und die Einsatzfähigkeit der Implementierung auf interessanten Probleminstanzen aufzeigen. Es sei k≥3und ungerade. Wie oben betrachtet man wieder eine Ringerweiterung S= GR(4, rk)von R, definiert q:= 2rund nutzt die R-Modul-Isomorphie ψ:SR→Rk R. 136 6.1. Lineare Codes über Galois-Ringen der Charakteristik 4 Dann definiert die Matrix Γq,k+1 := 1R1R1R. . . 1R ψ(0S)ψ(ξ0 S)ψ(ξ1 S). . . ψ(ξqk−1 S) einen freien, linearen Code Kq,k+1 der Länge qkvom Rang k+ 1 über dem Kettenring R. Die von den Spalten von Γq,k+1 erzeugte Punktmenge in PHG(Rk+1 R)wollen wir die Kerdock-Punktmenge zu Kq,k+1 nennen. Im Folgenden werden wir nun ausnahmsweise mit Tund T∗die Teichmüller-Menge bzw. Teichmüller-Gruppe von Sbezeichnen. Nun zu der angekündigten Untersuchung der Automorphismengruppe der verallgemeinerten Kerdock-Codes Kq,k+1. Klar ist, dass •die Multiplikation mit Elementen a∈T∗der Teichmüller-Gruppe eine R-lineare Abbildung auf S≃Rk Rdefiniert. Diese lässt sich somit über eine Matrix A∈GLk(R)darstellen. Wir schließen, dass die Matrix (1A)∈GLk+1(R)einen Automorphismus der Kerdock-Punktmenge definiert und somit auch einen Automorphismus des Kerdock-Codes induziert. •Genauso definiert ein Ringautomorphismus α∈Aut(S)eine R-semilineare Abbildung auf S≃Rk R. Man zeigt leicht, dass hierdurch ebenfalls ein Automorphismus der Kerdock-Punktmenge induziert wird. •Die multiplikative Gruppe R∗definiert wegen der Linearität der Codes über die triviale Operation c7→ c·a−1für alle a∈R∗stets Automorphismen. Man rechnet leicht nach, dass alle so gewonnenen Automorphismen (mit Ausnahme der Identität) der Kerdock-Punktmenge verschieden sind. Sie erzeugen eine Untergruppe von ΓLk+1(R), welche zu (R∗×T∗)oAut(S)isomorph ist. 6.1.8 Folgerung. Es sei k≥3ungerade und r∈Nbeliebig, sowie R:= GR(4, r), S:= GR(4, rk)und T∗die Teichmüller-Gruppe von S. Dann besitzt die Automorphismengruppe des R-linearen Kerdock-Codes Kq,k+1 eine Untergruppe, welche isomorph zu (R∗×T∗)oAut(S)ist. Für die klassischen Z4-linearen Kerdock-Codes K2,k+1 ist die Automorphismengruppe bekannt: 6.1.9 Fakt ([36]).Für ungerades k≥5hat der Z4-lineare Kerdock-Code K2,k+1 eine Automorphismengruppe der Ordnung |Aut(K2,k+1)|= 2·2k(2k−1)·k. Der Kerdock-Code K2,3+1 bildet eine Ausnahme und hat eine um den Faktor 8größere Automorphismengruppe2. Die Ordnung ist also 2688 = 2 ·8·23(23−1) ·3. In beiden Fällen operiert die Automorphismengruppe zweifach transitiv auf der KerdockPunktmenge. 2In [36] wird fälschlicherweise |Aut(K2,3+1)|= 1344 angegeben. Diese fehlerhafte Angabe tritt auch in weiteren Arbeiten auf. 137 6. Modifikationen & Anwendungen Das Zustandekommen des weiteren Faktors 2kin der Ordnung der Automorphismengruppe der Kerdock-Codes K2,k+1 wird in [36] beschrieben. Wir wollen nun für den nächstgrößeren Kettenring R= GR(4,2) ebenfalls die Automorphismengruppe des verallgemeinerten Kerdock-Codes K4,k+1 berechnen. Aufgrund des exponentiellen Wachstums der Ordnung |K4,k+1|= 42(k+1) gelingt uns dies für die ersten beiden Fälle k= 3 und k= 5: 6.1.10 Hilfssatz. Die Kerdock-Codes K4,3+1 und K4,5+1 über dem Galois-Ring GR(4,2) besitzen nur die in Folgerung 6.1.8 beschriebenen Automorphismen. Die Kerdock-Punktmengen beider Codes zerfallen unter der Operation der jeweiligen Automorphismengruppe in zwei Bahnen. Die erste besteht jeweils nur aus dem Punkt (1R, ψ(0S))T. Die Punkte (1R, ψ(ξi S))Tder Teichmüller-Gruppe bilden die zweite Bahn. Beweis. Resultat des Aufrufs unseres Kanonisierers aus Abschnitt 7.1.2. Die Berechnungen wurden in 20 Sekunden bzw. in 18 Stunden abgeschlossen. 6.1.11 Vermutung. Für alle Kerdock-Codes K2r,k+1,r > 1und k≥3ungerade, ist die Automorphismengruppe Aut(K2r,k+1)isomorph zu (R∗×T∗)oAut(S). Durch Punktieren an der Spalte (1R, ψ(0S))Tdefinieren wir zu Kq,k+1 den punktierten Kerdock-Code ˙ Kq,k+1. Bei den klassischen Z4-linearen Kerdock-Codes ist diese besondere Auszeichnung einer Spalte – wegen der transitiven Operation der Automorphismengruppe auf der Kerdock-Punktmenge – willkürlich. In den Beispielen K4,3+1 und K4,5+1 ist dies aufgrund unserer Beobachtungen zur Automorphismengruppe aber nicht mehr der Fall. In der Tat ergeben sich hier zwei Isomorphieklassen von Codes mit unterschiedlichen Eigenschaften: •Das Gray-Bild des punktierten Kerdock-Codes ˙ K4,3+1 definiert einen nichtlinearen Code der Länge 252 über F4der Kardinalität 48und Minimaldistanz 177. Der Vergleich mit [31] zeigt, dass K4,3+1 ein BTKL-Code ist. •Das Punktieren an einer beliebigen anderen Spalte führt dahingegen zu einem Code mit Minimaldistanz 176 und sonst identischen Parametern, siehe [45, Bemerkung 2.4.3 (e)]. Hier spielt also die Auswahl der punktierten Spalte eine gewichtige Rolle. Nur bei der Punktierung an der Spalte (1R,0S)Tergibt sich auch ein interessanter BTKL-Code über GR(4,2). 6.2. Klassifikationsprobleme Dieses Kapitel beinhaltet eine Sammlung von Ergebnissen, welche mit Hilfe einer C++ Implementierung des Kanonisierers, siehe Abschnitt 7.2, im Spezialfall R=Fq,R=Z4 und R=F2[X]/(X2)erzielt werden konnten. Diese Ergebnisse fanden auch bereits Eingang in die Arbeiten [21, 25, 26]. 138 6.2. Klassifikationsprobleme 6.2.1. Lineare Codes über endlichen Körpern Dieser Abschnitt bildet eine Zusammenfassung der Resultate aus dem Artikel [21]. Er behandelt die vollständige Klassifikation aller linearen Codes mit fest gewählten Parametern bis auf semilineare Isometrie. 6.2.1 Definition. Es sei C≤Fn qein linearer Code der Länge nund Dimension k. Für eine Koordinate i∈[n]definiert man den •in ipunktierten Code Pi(C) := {(c0, . . . , ci−1, ci+1,...cn−1)|c∈C}durch Streichen der i-ten Koordinaten, und den •in iverkürzten Code Si(C) := Pi(S0 i(C)), indem man sich zunächst auf den linearen Teilcode S0 i(C) := {c∈C|ci= 0}zurückzieht und anschließend die i-te Koordinate punktiert. Weiter ist zu einem Codewort c∈Cder residuelle Code Res(C, c)definiert durch das Punktieren des Codes Cauf der Trägermenge3supp(c)von c. 6.2.2 Fakt ([39], Corollary 2.7.2).Es sei C≤Fqein linearer Code der Dimension k∈ [n+ 1], mit Minimaldistanz dund dualer Minimaldistanz d⊥, kurz: ein [n, k, d]d⊥ q-Code. Für jedes beliebige c∈Cmit wH(c) = dist Res(C, c)ein hn−d, k −1,≥ld qmi≥d⊥ q-Code. 6.2.3 Fakt (Konstruktion Y1).Wendet man die obige Konstruktion auf ein Codewort c∈C⊥mit wH(c) = d⊥an und dualisiert anschließend wieder, so nennt man dieses Verfahren Konstruktion Y1. Der Code Res(C⊥, c)⊥hat dann die Parameter n−d⊥, k −d⊥+ 1,≥d≥ld⊥ qm q. Das Ziel ist es nun, für festgelegte Parameter n, k, q und Minimaldistanzen dsowie d⊥alle linearen [n, k, ≥d]d⊥ q-Codes bis auf semilineare Isometrie zu klassifizieren. Diese können wir eindeutig durch eine Transversale T(n, k, d, d⊥, q)⊆F(n−k)×n qvon Kontrollmatrizen beschreiben. Das Verfahren beruht nun auf einem Vorgehen, welches versucht, über eine Invertierung der Konstruktion Y1einen iterativen Algorithmus zu entwickeln. Ausgangspunkt bildet also eine Transversale S:= [ d0≥ld⊥ qm T(n−d⊥, k −d⊥+ 1, d, d0, q) zu allen Codes mit den möglichen Parametern, welche wir aus Konstruktion Y1gewinnen könnten. Anschließend werden sukzessiv weitere d⊥Spalten an die Kontrollmatrix angefügt. 3Man streicht alle Koordinaten i∈supp(c)simultan. 139 6. Modifikationen & Anwendungen q=2 q =3 q =4 q =5 q =7 q =8 n35 22 24 28 19 21 22 27 30 39 16 16 17 15 26 30 k10 8 14 21 8 14 16 17 21 27 5 6 8 8 20 23 d13 10 7 5 9 6 5 8 7 9 10 9 8 7 6 7 Tabelle 6.2.: Parameter, für welche keine linearen Codes existieren Das Anfügen von Spalten kann wieder mit einem Suchbaum modelliert werden. Die Kinder eines Knotens ∆∈T(n−(d⊥−i), k−(d⊥−i), d, i, q)auf Tiefe i<d⊥werden von allen zulässigen Erweiterungen von ∆um eine weitere Spalte gebildet. Eine Erweiterung ist zulässig, falls die Bedingungen an die Minimaldistanzen eingehalten werden. Weiter können wir auch vorschreiben, dass die Spalten aufsteigend sortiert in der Kontrollmatrix vorliegen. Der Suchbaum wird nun im Rahmen einer Tiefensuche durchlaufen. In der Arbeit [21] wurde gezeigt, dass es genügt, sich in dieser Suche auf jeder Tiefe i≤d⊥auf eine Transversale T(n−(d⊥−i), k−(d⊥−i), d, i, q)zurückzuziehen4. Um dies zu gewährleisten, wird nun der Kanonisierer für lineare Codes benötigt: Zu jeder neu hinzugenommenen Spalte wird zunächst der kanonischer Repräsentant der resultierenden Kontrollmatrix berechnet. Trat dieser bislang noch nicht auf, so muss das Anfügen von Spalten fortgeführt werden. Andernfalls kann man die Suche an dieser Stelle abbrechen und mit dem nächsten Kandidaten fortfahren. Ergebnisse Zu 16 verschiedenen Parametertupeln [n, k, d]q, siehe Tabelle 6.2, mit q= 2,3,4,5,7,8konnte die Existenz eines linearen [n, k, d]q-Codes ausgeschlossen werden. Über die in Definition 6.2.1 aufgezeigten Standardkonstruktionen lassen sich damit sogar 217 Verbesserungen der oberen Schranken ub(n, k, q)an die Minimaldistanz deines linearen [n, k, d]q-Codes gewinnen. Dabei haben wir uns mit den verfügbaren Tabellen [31] und [65] über die Minimaldistanz eines optimalen linearen Codes verglichen. Leider sind die Daten in beiden Tabellen nicht vollständig. Sofern bekannt wurden weitere Quellen, etwa [2], ebenfalls berücksichtigt. In 109 Fällen konnte anhand dieser Verbesserungen sogar die Lücke zwischen oberer und unterer Schranke geschlossen werden und damit die Minimaldistanz eines optimalen linearen Codes exakt bestimmt werden. Die erzielten Resultate sind im Unterverzeichnis results auf der beigefügten CD abrufbar. Die Datei mit dem Namen ub<q>.html für q= 2,3,4,5,7,8,9enthält die oberen Schranken an die Minimaldistanz eines linearen [n, k]q-Codes. Die Verbesserungen gegenüber der Tabelle [31] sind farbig hervorgehoben. Führt man den Mauszeiger über einen farbig hinterlegten Tabelleneintrag, so wird ein Beweis oder die Referenz angegeben. 4Dieses Vorgehen ist allgemein als isomorph rejection bekannt. 140 6.2. Klassifikationsprobleme n n −k=6 n −k=7 10 10. . . 3042 11 10. . . 405112 12 10. . . 506111251 13 112631219 14 22330 47431 15 37488 53797 16 413 564 6261 17 59617 74 18 657180 19 718090 20 8190100 21 90100110 Tabelle 6.3.: Anzahl nicht isomorpher [n, k, d]d⊥ 4-Codes für d≥6mit Unterscheidung nach d⊥ Wir wollen nun exemplarisch das Beispiel eines [21,14,6]4-Codes behandeln. Die Existenz eines solchen Codes konnte über die folgenden Berechnungen ausgeschlossen werden: Zunächst beobachtet man, dass die duale Distanz d⊥eines derartigen linearen Codes nur die Werte 9,10 oder 11 annehmen kann. Die obere Schranke liest man direkt aus [31] ab, die untere gewinnt man über eine Argumentation mit dem residuellen Code. Die Tabelle 6.3 gibt nun die Mächtigkeiten derjenigen Transversalen T(n, k, d, d⊥, q), welche im Zuge dieser Klassifikation bestimmt wurden. Der Eintrag d⊥xsagt hierbei aus, dass es xIsomorphieklassen von [n, k, ≥d]d⊥ q-Codes gibt. In der Spalte n−k= 6 findet man die Mächtigkeiten der Ausgangspunkte Sfür das iterative Vorgehen. Die Spalte n−k= 7 beschreibt die Anzahlen der zu betrachtenden, nicht isomorphen Codes für jeden Zwischenschritt. Die Einträge mit d⊥= 1 werden also aus den diagonal darüberliegenden Einträgen der Spalte n−k= 6 berechnet. Alle weiteren Einträge ergeben sich aus den Einträgen, welche direkt oberhalb notiert sind. Insgesamt konnten das Ergebnis in einer Gesamtzeit von 2.5Minuten bestimmt werden. 6.2.2. Nichtexistenz eines extremalen, selbstdualen Codes der Länge 72 mit vorgeschriebenen Automorphismen Es sei C≤Fn 2ein selbstdualer, linearer Code. Dann haben alle Codewörter gerades Hamming-Gewicht. Sind alle auftretenden Hamming-Gewichte sogar durch 4teilbar, so nennen wir Cdoppelt-gerade. Einen doppelt-geraden, selbstdualen Code nennt man 141