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

Disse a ion
Eine kanonische Fo m zu Da s ellung
äqui alen e Codes
– Compu e ges ü z e Be echnung und ih e Anwendung in de
Codie ungs heo ie, K yp og aphie und Geome ie –
Von de Uni e si ä Bay eu h
zu E langung des akademischen G ades eines
Dok o s de Na u wissenscha en (D . e . na .)
genehmig e Abhandlung
on
Thomas Feulne
gebo en am 16. Feb ua 1982
in Bay eu h
Vo wo
Die o liegende A bei en s and in den Jah en 2008 bis 2013 an de Uni e si ä Bay eu h
un e Be euung on He n P o . D . Adalbe Ke be . Seine behe z en Ini ia i e is es
zu e danken, dass ich nach dem Diplom meine Fo schungsa bei zu Kanonisie ung li-
nea e Codes o se zen konn e. Meinem Dok o a e möch e ich ü seine Un e s ü zung
und das allzei en gegengeb ach e Ve auen he zlich danken.
Als wei e e Glücks all e wies sich ü mich, dass nach de Eme i ie ung on He n
P o . D . Ke be die A bei sg uppe du ch P o . D . Al ed Wasse mann und PD D .
Axel Kohne o ge üh wu de. Ihnen is es zu e danken, dass die Finanzie ung mei-
ne A bei , zunächs übe ein S ipendium de Baye ischen Eli e ö de ung und schließlich
im Rahmen des DFG Schwe punk p og amms 1489, siche ges ell we den konn e. Zu-
ie s be o en bin ich imme noch da übe , dass ich Di , Axel, diesen Dank nich meh
pe sönlich aussp echen kann.
Fü eine kons uk i e und s e s unkomplizie e Zusammena bei bedanke ich mich
bei allen wei e en Kollegen de A bei sg uppe, die mi hil eichen Diskussionen und
Ra schlägen zu diese A bei bei ugen. Insbesonde e meinen Bü okollegen Michael Kie -
maie und Johannes Zwanzge sowie El i a Re ne möch e ich abe hie mi nochmals
gesonde , ü die angenehme A bei sa mosphä e und ein allzei o enes Oh bei F agen
und P oblemen danken.
Meine El e n, Roswi ha und Ge ha d, haben mich mi Au nahme des S udiums bis
heu e kon inuie lich und bedingungslos un e s ü z . Meine F eundin Melanie s and mi
imme liebe oll mo i ie end au dem langen Weg bis zu P omo ion zu Sei e. Fü das
en gegengeb ach e Ve s ändnis möch e ich mich on ganzem He zen bei ihnen bedanken.
Ecke sdo , im Mä z 2014 Thomas Feulne
Inhal s e zeichnis
1. Einlei ung 1
2. G undlagen 7
2.1. G uppen und G uppenope a ionen . . . . . . . . . . . . . . . . . . . . . 7
2.2. G aphen.................................... 11
2.3. EndlicheKe en inge............................. 13
2.3.1. Moduln und linea e Codes . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2. Dis anzen und Isome ien . . . . . . . . . . . . . . . . . . . . . . 17
2.4. Komplexi ä de P obleme . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3. Kanonisie ungsalgo i hmen 29
3.1. G undbaus eine de Kanonisie ung . . . . . . . . . . . . . . . . . . . . . 30
3.1.1. Kanonisie ung mi els Homomo phiep inzip . . . . . . . . . . . . 30
3.1.2. Kanonisie ung übe Un e g uppen . . . . . . . . . . . . . . . . . . 37
3.2. Pa i ionen und Ve eine ungen . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1. Zu Kanonizi ä un e isomo phen G uppenope a ionen . . . . . . 44
3.2.2. Ausnu zen bekann e Au omo phismen . . . . . . . . . . . . . . . 47
3.2.3. Implemen ie ungsde ails . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.4. Spezial all: Die Kanonisie ung on G aphen . . . . . . . . . . . . 54
3.2.5. I e ie e Ve eine ung . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3. G uppen de Ges al GoϕSP0....................... 61
3.3.1. Inne e Kanonisie ung . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.3.2. Gleichwe ige Algo i hmenen wu . . . . . . . . . . . . . . . . . 66
4. Endliche Ke en inge 71
4.1. Wei e eG undlagen.............................. 71
4.2. Au omo phismen ............................... 78
5. Linea e Codes übe endlichen Ke en ingen 87
5.1. Gene a o ma izen .............................. 87
5.1.1. Re o mulie ung de G uppenope a ion . . . . . . . . . . . . . . . 92
5.1.2. Die Ope a ion on (GLk(R)×R∗n)oAu T............ 96
5.2. EinKanonisie e ...............................117
5.2.1. Inne e Kanonisie ung . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.2.2. Äuße e Ve eine ung . . . . . . . . . . . . . . . . . . . . . . . . . 121
iii

Inhal s e zeichnis
5.2.3. Zu Kanonizi ä de kanonischen Rep äsen an en bei isomo phen
Ringen.................................129
6. Modi ika ionen & Anwendungen 133
6.1. Linea e Codes übe Galois-Ringen de Cha ak e is ik 4 . . . . . . . . . . 133
6.1.1. Klassi ika ion e allgemeine e Teichmülle -Codes . . . . . . . . . 133
6.1.2. Au omo phismen on e allgemeine en Ke dock-Codes . . . . . . 136
6.2. Klassi ika ionsp obleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.2.1. Linea e Codes übe endlichen Kö pe n . . . . . . . . . . . . . . . 139
6.2.2. Nich exis enz eines ex emalen, selbs dualen Codes de Länge 72
mi o gesch iebenen Au omo phismen . . . . . . . . . . . . . . . 141
6.2.3. Linea e Codes übe endlichen Ke en ingen de O dnung 4 . . . . 144
6.2.4. K yp og aphie.............................146
6.3. Ne wo k- und Fq-linea e Fq -Codes .....................150
6.3.1. Ne wo k-Codes ............................150
6.3.2. Fq-linea e Fq -Codes .........................151
6.3.3. Ein Kanonisie e . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7. En wickel e P og amme 155
7.1. Sage ......................................155
7.1.1. Linea e Codes übe endlichen Kö pe n . . . . . . . . . . . . . . . 155
7.1.2. Linea e Codes übe endlichen Ke en ingen . . . . . . . . . . . . . 156
7.2. C++ Implemen ie ung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.2.1. Ins alla ion ..............................158
7.2.2. Benu zung...............................159
8. Zusammen assung & Ausblick 161
A. Un e g uppen de Au omo phismeng uppe eines Ke en ings 165
i
Abbildungs e zeichnis
3.1. Homomo phiep inzip............................. 31
3.2. Kanonisie en mi els Homomo phiep inzip; Au spal en . . . . . . . . . . 31
3.3. Kanonisie en mi els Homomo phiep inzip; Ve schmelzen . . . . . . . . . 35
3.4. Illus a ion on Fak 3.2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5. I e ie e Ve eine ung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.6. Suchbaum zu Beispiel 3.2.29 . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.7. Isomo phie de Suchbäume . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.1. G aph G(Γ) zuBeispiel5.2.5.........................125
Tabellen e zeichnis
4.1. To alo dnung au F4[X]/(X2)........................ 75
6.1. Lau zei en des Kanonisie e s ü Tq,k,s ....................136
6.2. Pa ame e , ü welche keine linea en Codes exis ie en . . . . . . . . . . . 140
6.3. Anzahl nich isomo phe [n, k, d]d⊥
4-Codes ü d≥6mi Un e scheidung
nach d⊥....................................141
6.4. Resul a e im Fall Z7.............................143
6.5. Klassi ika ionse gebnisse ü Ke en inge de Ka dinali ä 4........145
6.6. Minimaldis anz de G ay-Bilde de Codes aus Tabelle 6.5 . . . . . . . . 146
Algo i hmen e zeichnis
5.1. MinS ep ...................................107
5.1. MinS ep (Fo se zung) ...........................108
5.2. MinimizeDependen ............................114
5.3. MinimizeIndependen ...........................115
5.4. Inne Can ..................................119
A.1. Be echnung eines E zeugendensys ems ü Au T..............166
i
Symbol e zeichnis
GXEine G uppenope a ion on Gau eine Menge X, Sei e 7
G XDie Bahnen eine G uppenope a ion GX, Sei e 7
FixG(X)Die Fixpunk e de Ope a ion on Gau X, Sei e 7
L(G){H|H≤G}, Sei e 7
C(G){Hg |H≤G, g ∈G}, Sei e 8
CFG(x)De kanonische Rep äsen an eine Bahn Gx, Sei e 8
TRG(x)Ein T anspo e elemen zu eine Kanonisie ung CFG, Sei e 8
S abG(x)De S abilisa o on x∈Xzu eine G uppenope a ion GX, Sei-
e 9
CanX
GEin Kanonisie e zu eine G uppenope a ion GX, Sei e 9
[n]{0, . . . , n −1}, Sei e 9
Rad(R)Das Jacobson-Radikal eines Rings R, Sei e 13
θEin E zeuge on Rad(R), Sei e 14
pe (x)Die Pe iode eines Elemen s x∈RM, Sei e 14
h (x)Die Höhe eines Elemen s x∈RM, Sei e 14
shp(M)De Um iss eines R-Linksmoduls M, Sei e 15
g(M)De Rang eines R-Linksmoduls M, Sei e 15
λEin es o gegebene Um iss de be ach e en linea en Codes,
Sei e 16
Rk×n,λ Die Menge alle Gene a o ma izen zu allen linea en Codes de
Länge n om Um iss λ= (λ0, . . . , λk−1), Sei e 16
T(x, G)De Suchbaum zu De ini ion on CanX
G, Sei e 39
I(x, Hg)Die Pa i ionie ungs o sch i im Suchbaum T(x, G), Sei e 39
V(x, Hg)Die Ve eine ungs o sch i im Suchbaum T(x, G), Sei e 40
L(x, G)Die Menge alle G uppenelemen e, welche Blä e on T(x, G)
de inie en, Sei e 40
L0(x, G){g∈L(x, G)|gx = CFG(x)}, Sei e 41
B(x, Hg)Die Bewe ung des Kno ens Hg im Suchbaum T(x, Hg), Sei e 42
FpDie Fä bung de Koo dina en bezüglich de Pa i ion p, Sei e 51
PEine kanonische Pa i ion zu [n], Sei e 51
ii
1. Einlei ung
in meine Diploma bei [22] be ei s en wo en wu de. Die zug unde liegenden Ideen we -
den wi in eine Allgemeinhei aus üh en, die es dann e laub , unse Vo gehen auch au
wei e e Klassen on Codes bzw. au wei e e G uppenope a ionen leich zu übe agen.
Diese Disse a ion is nun olgende maßen au gebau : Zunächs we den wi in dem
anschließenden Kapi el 2 wich ige G undlagen übe G uppen und endliche G uppen-
ope a ionen (Abschni 2.1), G aphen (2.2), Ke en inge Rund R-linea e Codes (2.3)
zusammen assen und die No a ion es legen. In diesem Kapi el klä en wi auch die F a-
ge zu Komplexi ä de Be echnung kanonische Rep äsen an en beziehungsweise eines
Tes s au die Äqui alenz zweie gegebene R-linea e Codes, siehe Abschni 2.4. Hie -
du ch ech e igen wi unse Vo gehen im wei e en Ve lau de A bei .
Das Kapi el 3 besch eib dann e schiedene Ansä ze zu Be echnung kanonische Re-
p äsen an en eine beliebigen G uppenope a ion on Gau X. Das on uns be o zug e
Ve ah en be uh au de Besch eibung eines Back ackalgo i hmus, welche e s mals ü
die Kanonisie ung on G aphen [55] en wickel wu de. Ve allgemeine ungen au belie-
bige G uppenope a ionen we den in [35] und [42] gegeben. De Abschni 3.2 e ein
beide Quellen und besch eib den Back ackbaum aus [42] übe das Homomo phiep in-
zip ü G uppenope a ionen, siehe [35, 50]. Wei e hin wi d eine Bewe ung de Kno en
des Back ackbaums de inie , welche das ühzei ige Abschneiden on Teilbäumen e -
möglich .
Übe die Un e g uppe alle bislang bekann en Au omo phismen des zu kanonisie en-
den Objek s x∈Xwi d ein wei e e Tes en wickel , welche es eben alls e laub ,
Teilbäume des Back ackbaums on de Suche auszuschließen. Hie zu wi d de Hil ssa z
3.3.3 aus de A bei [35] e schä , um bes mögliche Resul a e zu e zielen. Diese Ve -
allgemeine ung wu de be ei s in [22] angegeben, jedoch nich im Zusammenhang eine
allgemeinen G uppenope a ion on Gau X o mulie . Zum Abschluss des Kapi els
wi d au Sonde älle ü die G uppe Geingegangen.
Zu Vo be ei ung de Kanonisie ung R-linea e Codes wi d die S uk u eines Ke en-
ings Rin Kapi el 4 un e such und eine To alo dnung de inie . Insbesonde e wi d in
diesem Kapi el auch au die S uk u de addi i en G uppe, de mul iplika i en G uppe
und de Au omo phismeng uppe übe die Angabe on No mal eihen eingegangen. Das
Kapi el 5 geh dann schließlich au linea e Codes übe einem gegebenen Ke en ing ein.
Zunächs we den wei e e wich ige G undlagen geleg . Anschließend o mulie man die
Äqui alenz R-linea e Codes de Länge nübe eine G uppenope a ion eine G uppe
GoSnau de Menge de Gene a o ma izen. Fü diese Ope a ion wi d schließlich ein
Kanonisie e en wickel .
Das olgende Kapi el 6 gib Anwendungsbeispiele ü den en wickel en Kanonisie e
und besch eib mögliche Modi ika ionen, um diesen auch in de K yp og aphie ode ü
Ne wo k-Codes und Fq-linea e Fq -Codes anzuwenden. In meh e en Beispielen wi d ge-
zeig , dass eine e izien e Kanonisie ung häu ig im Rahmen eine Klassi ika ion benö ig
wi d und do das He zs ück bilde . So konn e e wa übe eine olls ändige Klassi ika ion
in 217 Fällen die Exis enz eines Fq-linea en Codes zu einem o gesch iebenen Pa a-
4

me e sa z, welche in [31] als o en5ge üh wi d, ausgeschlossen we den. Die Beispiele
belegen, dass es sich bei dem Kanonisie e um einen kompe i i en Algo i hmus handel .
Übe die beiliegende CD können die e ziel en Ve besse ungen eingesehen we den.
Das Kapi el 7 schließ die A bei mi de Besch eibung de en s andenen So wa e ab.
Die en s andenen P og ammpake e können übe die beiliegende CD ins allie we den.
De Quellcode diese P og amme is un e den Bedingungen de GNU Gene al Public
License (Ve sion 3) [30] eigegeben, d.h. e da beliebig kopie , e b ei e , modi izie
und genu z we den.
5Die Minimaldis anz eines op imalen linea en Codes is bei o gegebene Länge und Dimension unbe-
kann .
5
2. G undlagen
In diese A bei we den die au e enden algeb aischen S uk u en, wie G uppen, Ringe,
Kö pe , Moduln usw., s e s endlich sein. Wi we den die au e enden Ope a ionen,
d.h. G uppenope a ionen au Mengen bzw. die Modulope a ionen, be o zug on links
be ach en. Zumeis lassen sich die De ini ionen und Sä ze au eine Ope a ion on ech s
übe agen. Gegebenen alls we den wi au diese auch ohne eine en sp echende De ini ion
zu ückg ei en.
Zu Un e scheidung on Links- bzw. Rech smoduln we den wi RMbzw. MRsch ei-
ben. Im Fall on M=Rkwollen wi übe dies e einba en, dass RRkden Linksmodul
alle Zeilen ek o en und Rk
Rden Rech smodul alle Spal en ek o en bezeichne. Wi we -
den also, wie in de Codie ungs heo ie üblich, Vek o en als Zeilen ek o en au assen.
2.1. G uppen und G uppenope a ionen
Bis au Wei e es sei Geine es o gegebene endliche G uppe, die au eine endlichen
Menge Xope ie e. Wi bezeichnen Xauch als G-Menge und we den diese Eigenscha
auch ku z mi GXkennzeichnen. Diese Abschni soll o allem zu Fes legung de
No a ionen dienen, ü eine Ein üh ung in die Theo ie de G uppenope a ionen e weisen
wi au [43].
Die Bahn eines Elemen s x∈Xwe den wi mi Gx := {gx |g∈G}bezeichnen
und die Menge alle Bahnen mi G X:= {Gx |x∈X}. Ein minimales Sys em on
Rep äsen an en alle Bahnen nennen wi T ans e sale. Diejenigen Elemen e x∈X,
welche un e allen G uppenelemen en wiede au sich selbs abgebilde we den, nennen
wi Fixpunk e. Die Menge alle Fixpunk e on Xwe den wi mi FixG(X) := {x∈X|
gx =x, ∀g∈G}bezeichnen.
Zu eine G uppe Gsei L(G) := {H|H≤G}die Menge alle Un e g uppen on G. Die
G uppe Gope ie du ch Konjuga ion au L(G). Is umgekeh H∈ L(G)eine beliebige
Un e g uppe on Gso können wi die Mul iplika ion mi Elemen en aus H
• on links als eine Ope a ion de G uppe H on links au assen. Eine Bahn Hg zu
g∈Gnennen wi auch eine Rech snebenklasse on H. Die Bahnenmenge bezeich-
nen wi dann zu Auszeichnung diese speziellen Si ua ion mi H G.
• on ech s als eine Ope a ion de G uppe H on ech s au assen. Die Bahnen
nennen wi en sp echend Linksnebenklassen und wi bezeichnen die Bahnenmenge
mi G/H.
7
2. G undlagen
Eine T ans e sale T⊆Gde (Links-)Rech snebenklassen on Hnennen wi dann eine
(Links-)Rech s ans e sale on Hin G. Is Hein No mal eile on Gso äg G/H =
H Geine on Ginduzie e G uppens uk u mi neu alem Elemen H.
Im Folgenden wollen wi auße dem mi
C(G) := {Hg |H≤G, g ∈G}:= [
·
H∈L(G)
H G
die Menge alle Rech snebenklassen alle Un e g uppen H on Gbezeichnen. Zusä zlich
de inie en wi au de Menge C(G)eine G uppenope a ion on g0∈Gübe g0? Hg :=
Hgg−1
0.
Eine en scheidende Rolle bei de Un e suchung on G uppenope a ionen bilden Ho-
momo phismen: Is Yeine wei e e G-Menge, so nennen wi eine Funk ion :X→Y
einen G-Homomo phismus, alls (gx) = g (x) ü alle x∈Xund g∈Ggil . Is die
Ope a ion im Bildbe eich i ial (gy =y ü alle g∈Gund y∈Y), so sp echen wi
auch on eine G-In a ian en .
Ope ie au Yeine G uppe Hund is ϕ:G→Hein G uppenhomomo phismus,
welche mi eine Abbildung :X→Yim olgenden Sinne
(gx) = ϕ(g) (x),∀g∈G, x ∈X,
e äglich is , so nennen wi das Paa (ϕ, )einen Homomo phismus on G uppenope-
a ionen.
2.1.1 Beme kung. O ensich lich können wi übe einen solchen Homomo phismus
(ϕ, ) on G uppenope a ionen auch eine Ope a ion on Gau dem Bild (X)⊆Y
de inie en, e möge: g· (x) := ϕ(g) (x). Se zen wi die Ope a ion on Gau Y (X)
i ial o , so haben wi eine G uppenope a ion on Gau Yde inie . Die Abbildung
is also auch ein G-Homomo phismus. Homomo phismen on G uppenope a ionen
haben den Vo eil, dass sich die Angabe de Ope a ion hie du ch im Bildbe eich zumeis
au na ü liche Weise de inie en läss .
Nun zu de o malen Besch eibung unse e P oblems ellung ü allgemeine G uppen-
ope a ionen.
2.1.2 De ini ion (Kanonisie ung).Eine G-in a ian e Funk ion CFG:X→Xnen-
nen wi Kanonisie ung, alls CFG(x)∈Gx ü alle x∈Xgil . Das Elemen CFG(x)
bezeichnen wi als den kanonischen Rep äsen an en on xbzw. de Bahn Gx.
2.1.3 De ini ion (T anspo e elemen ).Is CFG:X→Xeine Kanonisie ung so nen-
nen wi G uppenelemen e g∈Gmi gx = CFG(x)T anspo e elemen e zu x∈X. Eine
Abbildung TRG:X→G, welche jedem x∈Xein zugehö iges T anspo e elemen
zuo dne heiß T anspo e abbildung.
8
2.1. G uppen und G uppenope a ionen
T anspo e elemen e sind bis au Rech smul iplika ion mi Elemen en aus dem S a-
bilisa o S abG(x) := {g∈G|gx =x} on xeindeu ig bes imm . Is die ope ie ende
G uppe aus dem Zusammenhang e sich lich, so wollen wi Elemen e des S abilisa o s
auch als Au omo phismen on xbezeichnen. Inso e n we den wi auch on de Au o-
mo phismeng uppe Au (x)des Objek s xsp echen. Genauso benu zen wi auch den
Beg i isomo ph ü Elemen e x, x0de gleichen Bahn. Da jede G uppenope a ion auch
eine Äqui alenz ela ion au Xde inie , we den wi die Elemen e x, x0de gleichen Bahn
auch als äqui alen bezeichnen.
2.1.4 De ini ion (Kanonisie e ).Is CFG:X→Xeine Kanonisie ung mi eine T ans-
po e abbildung TRG:X→G, so wollen wi das T ipel CanG:= (CFG,TRG,S abG)
als Kanonisie e bezeichnen.
2.1.5 Beme kung. Gegebenen alls – e wa alls Gau meh e en Mengenope ie – we -
den wi die Kanonisie e CanX
G:= (CFX
G,TRX
G,S abG)übe die zusä zliche Angabe de
Menge Xim Exponen en un e scheiden. Fü die Zuo dnung on x∈Xau seinen S abi-
lisa o S abG(x)bes eh keine Wahlmöglichkei . Wi e zich en dahe au die zusä zliche
Angabe on Xin diese Besch eibung de S abilisa o unk ion S abG:X→ L(G).
2.1.6 Beme kung. Du ch Angabe des T anspo e elemen s TRG(x)is de kanonische
Rep äsen an CFG(x) = TRG(x)x on x∈Xbe ei s eindeu ig bes imm . Die edundan-
e In o ma ion CFGbei de De ini ion des Kanonisie e s soll o allem e deu lichen, zu
welche Kanonisie ungs unk ion die T anspo e elemen e bes imm wu den.
Diese De ini ion eines Kanonisie e s is wenige aus ma hema ische Sich weise mo i-
ie sonde n gib ielmeh unse en algo i hmischen S andpunk au das P oblem wiede .
Wi wollen ein Compu e p og amm en we en, welches einen Kanonisie e implemen-
ie . Eingabe is also ein Objek x∈Xund wi e wa en die Rückgabe eines kanoni-
schen Rep äsen an en, eines zugehö igen T anspo e elemen s und des S abilisa o s. In
diesem Sinne wollen wi auch die Be echnung des S abilisa o s S abG(x)als du chge-
üh ansehen, d.h. wi haben diese Un e g uppe nich nu o mal sonde n a sächlich
übe ein be echne es E zeugendensys em E ü wei e e Un e suchungen zu Ve ügung.
Übe den P og amm luss s eue n wi , dass a sächlich ein Kanonisie e CanG eali-
sie wi d. Die ma hema ische Angabe de zugehö igen Kanonisie ungs unk ion is dami
häu ig seh um ang eich und nu dem P og ammablau zu en nehmen.
Folgende G uppen sind ü uns on besonde em In e esse:
•Die symme ische G uppe SX:= { :X→X| bijek i }au eine endlichen
Menge X. Is X= [n] := {0, . . . , n −1}, so sch eiben wi auch ku z Sns a S[n].
•Die mul iplika i e G uppe R∗alle Einhei en des Rings R.
•Die G uppe alle in e ie ba en (k×k)-Ma izen, die allgemeine linea e G uppe
GLk(R)übe dem Ring R.
9

2. G undlagen
Übe die De ini ion (A, x)7→ xA−1ope ie die G uppe GLk(R) on links au RRk.
Fü es gewähl es A∈GLk(R)is hie du ch auch eindeu ig eine linkslinea e, in e -
ie ba e Abbildungen A:RRk→RRk, x 7→ xA−1gegeben und dami de na ü liche
G uppenisomo phismus in die G uppe de linkslinea en Abbildungen de inie .
Des Wei e en bezeichnen wi zu zwei G uppen G, H und einem gegebenen G uppenho-
momo phismus θ:G→Au (H)mi HoθG:= {(h;g)|h∈H, g ∈G}das semidi ek e
P oduk beide G uppen bezüglich θ. Die Mul iplika ion is dabei übe die Vo sch i
(h;g)(h0;g0) := (hθ(g)(h0); gg0)
de inie . Wi we den die Angabe des G uppenhomomo phismus θun e d ücken, so e n
diese aus dem Kon ex eindeu ig he o geh . Is θ(g) = idH ü alle g∈G, so is das
semidi ek e P oduk gleich dem di ek en P oduk beide G uppen.
2.1.7 Beispiel. Es sei Rein Ring und de G uppenhomomo phismus
θ: Au (R)→Au (GLk(R))
α7→ ((Ai,j)7→ (α(Ai,j)))
de inie übe die komponen enweise Anwendung des Au omo phismus α∈Au (R)au
die Ma izen A∈GLk(R). Das semidi ek e P oduk ΓLk(R) := GLk(R)oθAu (R)
nennen wi die allgemeine semilinea e G uppe om G ad k.
2.1.8 De ini ion (semilinea e Abbildungen).Wi nennen eine Abbildung :RRn→
RRnlinkssemilinea , alls es einen Ringau omo phismus α∈Au (R)gib , so dass
(u+ ) = (u) + ( )und ( u) = α( ) (u) ü alle u, ∈Rkund ∈Rgil .
Die G uppe ΓLk(R)ope ie au RRkübe die De ini ion (A;α) := α( )A−1und
is isomo ph zu G uppe de linkssemilinea en Abbildungen au Rk. Im Folgenden we -
den wi dahe die G uppe de (semi-)linea en Abbildungen als GLk(R)bzw. ΓLk(R)
ausd ücken.
Schließlich we den wi zu eine Pe mu a ion π∈Snund einem Ring Rdie Pe mu a-
ionsma ix P(π)∈ {0R,1R}übe
P(π):= 


eπ−1(0)
.
.
.
eπ−1(n−1)


=eT
π(0) · · · eT
π(n−1)
de inie en. Es bezeichne hie bei eiden i- en Einhei s ek o . Wi können also übe den
G uppenmonomo phismus Sn→GLn(R), π 7→ P(π)die G uppe Snauch als Un e g up-
pe on GLn(R)bzw. ΓLn(R)au assen. Eine Pe mu a ion π∈Snope ie dahe au
RRndu ch Rech smul iplika ion mi (P(π))−1= (P(π))T=P(π−1), d.h.
π·ei:= eiP(π−1)=eπ(i)=(ei)π−1(0),...,(ei)π−1(n−1)
=⇒π·( 0, . . . , n−1)=( 0, . . . , n−1)P(π−1)
= ( π−1(0), . . . , π−1(n−1)) ü alle ∈RRn.
10
2.2. G aphen
Is Rein Ring und ϕ∈Rn, so bezeichne diag(ϕ) := D∈Rn×ndie Diagonalma ix D
mi Ein ägen Di,i =ϕi. Das semidi ek e P oduk (R∗)noΘSnmi Θ(π)(ϕ) := ϕP(π−1)
nennen wi die monomiale G uppe om G ad nübe R. Diese P oduk bildung kann auch
als das K anzp oduk R∗onSn on R∗mi Sngesehen we den.
Auch die monomiale G uppe läss sich übe den G uppenmonomo phismus
(R∗)noΘSn→GLn(R),(ϕ;π)7→ diag(ϕ)P(π)
in die G uppe GLn(R)einbe en. Die Bilde nennen wi dahe auch monomiale Ma izen.
Diese G uppe ope ie somi au RRndu ch:
(ϕ;π) := P(π−1)diag(ϕ)−1= π−1(0)ϕ−1
0, . . . , π−1(n−1)ϕ−1
n−1.
Nimm man zusä zlich noch die Ringau omo phismen hinzu, so e häl man die soge-
nann e semimonomiale G uppe ((R∗)noΘSn)oθAu (R)und wi können diese analog
in ΓLk(R)einbe en. Die on (ϕ;π, α)∈((R∗)noΘSn)oθAu (R)au RRninduzie e
Abbildung
7→ (ϕ;π, α) := (ϕ;π)α( ) = α( )P(π−1)diag(ϕ)−1
=α( π−1(0))ϕ−1
0, . . . , α( π−1(n−1))ϕ−1
n−1
nennen wi auch eine (semi-)monomiale T ans o ma ion on Rn.
Da die Ope a ion de Au omo phismeng uppe au Pe mu a ionsma izen i ial is ,
können wi dieses semidi ek e P oduk auch wie olg besch eiben:
((R∗)noΘSn)oθAu (R)=(R∗)noϑ(Sn×Au (R)) (2.1)
mi ϑ((π, α)) := Θ(π)◦θ(α) = θ(α)◦Θ(π) ü alle (π, α)∈Sn×Au (R).
Wi we den spä e sehen, dass die G uppe (2.1) in de Codie ungs heo ie übe endli-
chen Ke en ingen1Reine zen ale Rolle spiel . Sie de inie den allgemeins en Äqui a-
lenzbeg i ü R-linea e Codes.
Analog is die Ope a ion on ΓLn(R)au de Menge de Spal en ek o en Rn
Rgegeben
du ch (A;α) T=Aα( T). Sie is isomo ph zu den ech ssemilinea en Abbildungen au
Rn
R. En sp echend lei en sich auch die Ope a ionen de einge üh en Un e g uppen ab.
2.2. G aphen
Wie wi be ei s in de Einlei ung ku z beme k en, lassen sich iele Isomo phiep oble-
me disk e e S uk u en, wie e wa linea e Codes, au das G aphenisomo phiep oblem
zu ück üh en. Wi wollen dahe au diese kombina o ische S uk u ku z eingehen. Um-
gekeh läss sich das G aphenisomo phiep oblem abe auch mi einem Äqui alenz es
1De ini ion olg .
11
2. G undlagen
ü linea e Codes lösen. Dies is o allem aus G ünden de Komplexi ä sabschä zung,
die wi in Abschni 2.4 du ch üh en we den, on g oßem In e esse.
Des Wei e en is diese Exku s auch du ch die Ta sache mo i ie , dass de in [55]
besch iebene Kanonisie e ü G aphen undamen ale Ideen, siehe Kapi el 3, ü die
En wicklung unse e codie ungs heo e ischen Kanonisie e beinhal e . Schließlich e olg
die Fo mulie ung des Lösungsalgo i hmus selbs übe die De ini ion eines Suchbaums,
d.h. übe spezielle G aphen.
Wi wollen zu eine beliebigen Menge Vmi V
kdie Menge ih e k-Teilmengen be-
zeichnen. Ein (unge ich e e ) G aph Γ=(V, E)is ein Tupel mi eine Menge V on
Kno en und eine Menge E⊆V
2 on Kan en. Wi sch eiben dann auch [2](V
2) ü die
Menge alle G aphen mi Kno enmenge V, wobei wi den Vek o e∈[2](V
2)als die Menge
E:= {{ , w} ∈ V
2|e{ ,w}= 1}in e p e ie en.
Einen ge ich e en G aphen e häl man, wenn man die Kno enpaa e geo dne be ach-
e , d.h. E⊆V×Vwähl . Fü unse e Zwecke können wi imme on eine endlichen
Menge Vausgehen und zumeis sind die un e such en G aphen unge ich e .
Wi nennen zwei G aphen (V, E),(V0, E0)isomo ph, alls es eine Bijek ion :V→V0
gib mi { , w} ∈ E⇐⇒ { ( ), (w)} ∈ E0. Isomo phe G aphen gehen also du ch
Umnumme ie ung de Kno enbesch i ungen auseinande he o . Zu Un e suchung de
Isomo phie on G aphen können wi s e s annehmen, dass die Kno enmengen V, V 0gleich
sind und dass ohne Besch änkung de Allgemeinhei V= [n] := {0, . . . , n −1} ü ein
n∈Ngil . Ande n alls bilden wi Vbzw. V0übe eine beliebige Bijek ion nach [n]ab.
Diese Beobach ung e laub es uns nun, die G aphenisomo phie übe die G uppenope a-
ion de symme ischen G uppe Snau de Po enzmenge [2]([n]
2)alle Zweie eilmengen
on [n]zu un e suchen.
Zwei Kno en u, ∈Veines G aphen (V, E)heißen benachba (adjazen ), alls {u, } ∈
Egil . Eine Adjazenzma ix A∈ {0,1}n×neines G aphen ([n], E)besch eib die Nach-
ba scha sbeziehung du ch die De ini ion Ai,j =1:⇐⇒ {i, j} ∈ E. Übe eine Inzi-
denzma ix I∈ {0,1}m×neines G aphen ([n], E)wi d die Kno en-Kan en-Inklusion
besch ieben; man e häl sie übe eine Ano dnung de Kan enmenge (e0, . . . , em−1)und
Se zung Ii,j = 1 :⇐⇒ j∈ei. Inzidenzma izen sind also nu bis au Pe mu a ion de
Zeilen eindeu ig bes imm .
De nach olgende Sa z besch eib die Isomo phie on G aphen übe e schiedene
G uppenope a ionen, je nachdem ob man zu Da s ellung des G aphen die Kan en-
menge, eine Adjazenzma ix ode eine Inzidenzma ix wähl :
2.2.1 Fak . Es seien Gi= ([n], Ei),i= 0,1G aphen mi mKan en und gegebenen
Inzidenzma izen Iiund Adjazenzma izen Ai. Dann sind äqui alen :
•G0und G1sind isomo ph.
•E1∈SnE0(mi π{. . . , {u, }, . . .}:= {. . . , {π(u), π( )}, . . .})
12
2.3. Endliche Ke en inge
•A1∈SnA0(mi πA := P(π)AP(π−1))
•I1∈(Sm×Sn)I0(mi (σ, π)I:= P(σ)IP(π−1))
Abschließend wollen wi noch Wu zelbäume ein üh en, die wi zu De ini ion de Ka-
nonisie e benö igen we den. Im G aphen (V, E)nennen wi eine Folge paa weise e -
schiedene Kno en 0, . . . , k∈Vmi { i, i+1} ∈ E ü alle i∈[k]einen P ad on 0
nach k. Die Kno en 0, k∈Vnennen wi dann auch e bunden. De G aph (V, E)is
zusammenhängend, alls alle Kno en paa weise e bunden sind.
Einen zusammenhängenden G aphen (V, E), bei welchem genau ein P ad zwischen
jedem beliebigen Kno enpaa exis ie , nennen wi Baum. Is übe dies ∈Vein aus-
gezeichne e Kno en, so nennen wi ((V, E), )einen Wu zelbaum mi Wu zel . Jedem
Kno en eines Wu zelbaums können wi übe die P adlänge des P ads on de Wu zel
nach eine eindeu ige na ü liche Zahl d( )zuo dnen. Wi nennen sie die Tie e des
Kno ens . Is { , w} ∈ Eeine Kan e eines Wu zelbaums und d( ) = d(w)+1, so nennen
wi wein Kind(-kno en) on und den Va e (-kno en) zu w. Demen sp echend nennen
wi alle Kno en w, die au dem P ad on de Wu zel zu ∈Vliegen, auch Vo ah en on
und umgekeh einen Nach ah en on w. Kno en ohne Nach ah en heißen Blä e .
De Teilg aph bes ehend aus allen Nach ah en eines Kno ens ∈Vbilde wiede um
selbs einen Wu zelbaum mi Wu zel .
Un e eine B ei ensuche (b ead h- i s -sea ch) au einem Wu zelbaum ((V, E), ) e -
s ehen wi eine Besuchs eihen olge ( 0, . . . , n−1)alle Kno en, so dass die en sp echende
Folge de Tie en mono on wächs . Im Gegensa z dazu d ing die sogenann e Tie ensu-
che (dep h- i s -sea ch) zunächs bis zu einem beliebigen Bla im Baum o und keh
danach eku si zu den Vo ah en zu ück um do alle wei e en unbesuch en Kinde und
de en Nach ah en eben alls in Tie ensuche zu du chlau en.
2.3. Endliche Ke en inge
Es sei Rs e s ein assozia i e Ring mi Eins. Die hie angegebenen Resul a e übe
Ke en inge wu den aus [11] en nommen.
2.3.1 De ini ion (Ke en ing).Wi nennen Reinen Linkske en ing, alls die Menge
de Linksideale bzgl. Inklusion o algeo dne is . De Ideal e band bilde also eine Ke e
{0}=I0I1. . . Im=R. Rech ske en inge seien analog de inie . Einen Ring, de
sowohl Links- als auch Rech ske en ing is , nennen wi Ke en ing.
2.3.2 Fak . Is Rendlich, so is Rgenau dann ein Linkske en ing, wenn Rein Rech s-
ke en ing is .
Da wi im Folgenden nu noch endliche Ke en inge be ach en we den, können wi
also die Un e scheidung zwischen Links- und Rech ske en ingen e nachlässigen. Das
Jacobson-Radikal Rad(R)eines Rings Ris de inie als de Schni alle maximalen
13
2. G undlagen
2.3.27 Fak (J. MacWilliams [52]).Das Hamming-Gewich besi z die MacWilliams-
Eigenscha ü jeden endlichen Kö pe Fq.
Die Menge alle Uw-monomialen T ans o ma ionen on Rnbilde eine Un e g uppe de
monomialen G uppe om G ad n. Wi wollen diese Un e g uppe auch die Uw-monomiale
G uppe om G ad nnennen. Ha ein Gewich w:R→R+
0die MacWilliams-Eigenscha ,
so olg so o mi C=Rn, dass dann die Menge alle linea en Isome ien on Rngleich
de Uw-monomialen G uppe om G ad nis .
2.3.28 Fak ([72, Theo em 9.4]).Alle Gewich e w:R→R+
0mi Uw=R∗haben die
MacWilliams-Eigenscha .
2.3.29 Beme kung. J. Wood [72] de inie einen wesen lich eie en Gewich sbeg i
als wi ihn hie zulassen. E o de lediglich eine Funk ion w:R→Qmi w(0R)=0.
Das obige Theo em benö ig dann als wei e e Vo ausse zung w(θm−1)6= 0.
Ha das Gewich weine kleine e Symme ieg uppe, so können die zu e üllenden Be-
dingungen ü die MacWilliams-Eigenscha um ein Viel aches schwie ige we den, siehe
[72]. Da die ü unse e Zwecke en scheidenden Gewich e (das Hamming-Gewich und
auch das homogene Gewich ) abe die obige Eigenscha e üllen, we den wi im Fol-
genden nu noch Gewich e mi maximale Symme ieg uppe Uw=R∗un e suchen. Fü
beide Gewich e bzw. Dis anzen is also die G uppe de linea en Isome ien isomo ph
zu de monomialen G uppe (R∗)noSn. Das wei e e Vo gehen ließe sich abe du ch-
aus analog ü beliebige Uw-monomiale G uppen umse zen. Wi e zich en hie au zu
ein ache en Ve s ändlichkei de wei e en A gumen a ionen.
2.3.30 Hil ssa z. Is w:R→R+
0ein Gewich mi Uw=R∗, so de inie die kom-
ponen enweise Anwendung eines Ringau omo phismus α∈Au (R)eine Isome ie au
dem me ischen Raum (Rn, dw),n∈N.
Beweis. Fü alle a∈Ris h (α(a)) = h (a)und wegen Uw=R∗auch w(α(a)) = w(a).
Dami de inie die komponen enweise Anwendung on αabe ganz o ensich lich eine
Isome ie on (Rn, dw).
Wi haben die Fo mulie ung de MacWilliams-Eigenscha eines Gewich s on J. Wood
übe nommen. Ta sächlich zeig J. MacWilliams abe in ih e A bei [52], dass sich jede
semilinea e Isome ie zwischen zwei gegebenen linea en Codes übe einem Kö pe Fq
zu eine semimonomialen T ans o ma ion au ganz Fn
q o se zen läss . De olgende
Hil ssa z zeig , dass die MacWilliams-Eigenscha im Fall on Uw=R∗auch hin eichend
is . E e allgemeine die Aussage aus [73, Sa z 2.16], welche nu das Hamming-Gewich
und das homogene Gewich be ach e . Die Beweisidee is jedoch iden isch.
2.3.31 Hil ssa z. Es sei w:R→R+
0ein Gewich mi Uw=R∗. Dann läss sich jede
semilinea e Isome ie : (C, dw)→(Rn, dw)zu jedem C≤Rnund n∈Nzu eine
semimonomialen T ans o ma ion on Rn o se zen.
20

2.3. Endliche Ke en inge
Beweis. Es sei wein Gewich mi de MacWilliams-Eigenscha und :C→RRn
eine beliebige semilinea e Isome ie ü C≤Rnmi zugehö igen Ringau omo phismus
α∈Au (R). Dann is abe ◦α−1eben alls eine Isome ie on Cund linea . Sie läss
sich wegen de MacWilliams-Eigenscha des Gewich s abe übe eine monomiale Ma ix
A= diag(ϕ)P(π) ü ein (ϕ;π)∈(R∗)noSnda s ellen. Insgesam e gib sich also die zu
beweisende Behaup ung, dass eine semimonomiale T ans o ma ion on Rnis .
2.3.32 Folge ung. Is w:R→R+
0ein Gewich mi Uw=R∗, dann is die G uppe
alle semilinea en Isome ien on (Rn, dw)isomo ph zu (R∗)no(Au (R)×Sn).
2.3.33 Beme kung. Ha das Gewich weine kleine e Symme ieg uppe Uw6=R∗, so
muss man sich auch bei de Ope a ion de Au omo phismeng uppe on Rau diejenige
Un e g uppe einsch änken, welche das Gewich espek ie .
2.3.34 Beme kung. Ha ein Gewich wmi Uw=R∗die MacWilliams-Eigenscha , so
können wi diese nich nu dazu nu zen, den Äqui alenzbeg i au die G uppenope a ion
de semimonomialen G uppe zu ückzu üh en. Sie zeig auch, dass wi die De ini ion de
Äqui alenz on zwei linea en Codes C0, C1≤Rnallgemeine übe die Exis enz eine
semilinea en Isome ie ι:C0→C1de inie en könn en, ohne dass dies zu e ände en
Äqui alenzklassen üh en wü de.
Wi we den im Folgenden on Gewich en wbzw. Me iken dwausgehen, ü welche
die Symme ieg uppe Uw=R∗maximal is . Wi nennen dann zwei Codes C0, C1≤Rn
•(semi-)linea isome isch, wenn es eine (semi-)monomiale T ans o ma ion on Rn
gib , die den einen au den ande en übe üh , bzw.
•pe mu a ionsisome isch, wenn es eine Koo dina enpe mu a ion gib , welche den
einen au den ande en übe üh .
2.3.35 De ini ion (symme isie es Gewich ).Das symme isie e Gewich 3eines Vek-
o s ∈Rnde inie en wi als wsym( ) := (a0( ), . . . , am( )) mi ai:= |{j∈[n]|
pe (aj) = i},∀i∈[m+ 1].
2.3.36 Folge ung. Jedes Gewich wmi maximale Symme ieg uppe Uw=R∗läss
sich mi Hil e des symme isie en Gewich s als Vek o p oduk
w( ) = wsym( )·(w(θm), . . . , w(θ0))T
sch eiben.
Das Gewich wselbs wi d also nich wei e Eingang in diese A bei inden. Wi
we den ielmeh das symme isie e Gewich wsym benu zen, da es eindeu ig die Bahnen
de G uppe alle semilinea en Isome ien au RRnbesch eib .
3Dies is kein Gewich im Sinne on De ini ion 2.3.22.
21
2. G undlagen
2.4. Komplexi ä de P obleme
Fü eine Ein üh ung in die Komplexi ä s heo ie e weisen wi den Lese au eines de
zahl eichen Leh büche zu heo e ischen In o ma ik ode zu diesem speziellen Teilge-
bie , e wa [71]. Zunächs is es ü wei e e Komplexi ä sun e suchungen no wendig, das
zu un e suchende P oblem als ein En scheidungsp oblem zu o mulie en, d.h. als eine
F ages ellung, die eindeu ig (en scheidba ) mi ja ode nein ü alle Eingaben zu bean -
wo en is . Zum Beispiel de inie en wi das G aphenisomo phiep oblem GI als die F age:
„Sind zwei beliebige gegebene G aphen isomo ph?“
Un e eine Eingabe zu einem En scheidungsp oblem Pwollen wi nun die F ages el-
lung e s ehen, die es im Konk e en zu bean wo en gil ; im Beispiel de G apheniso-
mo phie also ein Vo gabe eines Paa es (G0, G1)aus zwei G aphen G0, G1∈V
2. De
Eingabe wi d nun eine Eingabelänge zugeo dne , um die benö ig e Rechenzei auch in
Rela ion zu de P oblemg öße se zen zu können. Wi gehen dahe da on aus, dass sich
die Eingabe Iau na ü liche Weise als eine Zeichenke e übe einem endlichen Alpha-
be besch eiben läss . Zum Beispiel we den die G aphen du ch Adjazenzma izen ode
linea e Codes du ch Gene a o ma izen besch ieben. De Eingabe Io dnen wi dann
die Länge |I|diese Zeichenke e zu. Fü das G aphenisomo phiep oblem ha somi die
Eingabe (G0, G1)zum Beispiel die Länge |(G0, G1)|= 2 ·2n2.
Eine Tu ingmaschine is nun ein Modell de In o ma ik um den Beg i de Rechenzei
eines Algo i hmus zu s anda disie en. Bei eine de e minis ischen Tu ingmaschine is
die nächs e du chge üh e Ak ion eindeu ig du ch den ak uellen Zus and de Maschine
und des Zeichens an de ak uellen Posi ion des Lesekop s de inie . Wi sagen, eine
de e minis ische Tu ingmaschine (ein de e minis ische Algo i hmus) lös ein P oblem
Pin Polynomialzei , alls ein Polynom p∈R[x]exis ie , so dass sich ü alle Eingaben I
die maximal no wendige Anzahl on Sch i en de Tu ingmaschine zu Eingabe Idu ch
p(|I|)nach oben abschä zen läss .
Im Gegensa z dazu kann eine nich de e minis ische Tu ingmaschine in jedem Zus and
ü die ak uelle Eingabe s e s zwischen zwei Ak ionen wählen, wobei es keine Vo sch i
gib , wie diese Ak ion ausgewähl wi d. Eine nich de e minis ische Tu ingmaschine lös
ein En scheidungsp oblem zu Eingabe I, alls sie bei de Ko ek hei de Aussage die
An wo „ja“ au einem zulässigen Rechenweg e eichen kann. Is die An wo au die
Aussage „nein“, so üh en auch alle Rechenwege zu An wo „nein“. Eine nich de e -
minis ische Tu ingmaschine a bei e in Polynomialzei , alls sie die Rechnung au allen
zulässigen Rechenwegen in Polynomialzei in de Eingabelänge beende .
Wi sagen, ein En scheidungsp oblem P0sei schwe e als das En scheidungsp oblem
P1, alls wi jede Eingabe I ü das P oblem P1in Polynomialzei au eine Eingabe J(I)
zu P0 ans o mie en können, so dass Igenau dann mi „ja“ bean wo e wi d, wenn
auch J(I)mi „ja“ bean wo e wi d. Wi sagen hie zu auch, dass wi das En schei-
dungsp oblem P1in Polynomialzei au das En scheidungsp oblem P0zu ück üh en.
22
2.4. Komplexi ä de P obleme
Mi diesen De ini ionen lassen sich nun die bekann en Komplexi ä sklassen
Pdie Klasse alle En scheidungsp obleme, welche in Polynomialzei au eine de e mi-
nis ischen Tu ingmaschine lösba sind,
NP die Klasse alle En scheidungsp obleme, die in Polynomialzei au eine nich de e -
minis ischen Tu ingmaschine lösba sind,
NP-schwe die Klasse alle En scheidungsp obleme P0, ü die jedes P oblem P1aus
de Klasse NP in Polynomialzei au P0zu ückge üh we den kann und
NP- olls ändig die Klasse alle NP-schwe en En scheidungsp obleme in NP
de inie en. En scheidungsp obleme aus de Klasse NP lassen sich auch dadu ch cha ak-
e isie en, dass jede „Ja“-An wo in Polynomialzei au eine de e minis ischen Tu ing-
maschine e i izie ba is .
2.4.1 Beispiel. Das G aphenisomo phiep oblem GI is in NP, denn wi können in Poly-
nomialzei übe p ü en, ob eine gegebene Pe mu a ion πde Kno en einen Isomo phismus
zwischen beiden G aphen de inie .
Die P oblemklasse Pis in NP en hal en und sie beinhal e die ein ache en F age-
s ellungen. NP-schwe e P obleme zeichnen sich dadu ch aus, dass sie mindes ens so
schwe sind wie alle ande en P obleme aus NP.
Eine de wich igs en F ages ellungen de Ma hema ik is die En scheidung, ob P=NP
gil . Das Clay Ma hema ics Ins i u e4ha einen Geldp eis in Höhe on eine Millionen
Dolla ü die Lösung ausgesch ieben. In de o iziellen P oblembesch eibung [14] inde
sich auch die Eino dnung des G aphenisomo phiep oblems (GI):
„The e a e in e es ing examples o NP p oblems no known o be ei he in
Po NP-comple e. One example is he g aph isomo phism p oblem: Gi en
wo undi ec ed g aphs, de e mine whe he hey a e isomo phic.“
Diese Eigenscha de G aphenisomo phie wi d auch in [71] behandel . Fü linea e Co-
des de inie en wi analog zu G aphenisomo phie olgende En scheidungsp obleme in
Abhängigkei on dem Ke en ing Rund des gewähl en Isome iebeg i s:
PCER: Sind Γund Γ0Gene a o ma izen R-linea e Codes, en scheide ob de on Γ
e zeug e Code pe mu a ionsisome isch zu dem on Γ0e zeug en Code is .
LCER: Sind Γund Γ0Gene a o ma izen R-linea e Codes, en scheide ob de on Γ
e zeug e Code linea isome isch zu dem on Γ0e zeug en Code is .
SCER: Sind Γund Γ0Gene a o ma izen R-linea e Codes, en scheide ob de on Γ
e zeug e Code semilinea isome isch zu dem on Γ0e zeug en Code is .
4h p://www.clayma h.o g
23
2. G undlagen
Wenige A bei en un e suchen die Komplexi ä de oben de inie en P obleme aus de
Codie ungs heo ie. In [62] lie e n Pe ank und Ro h zunächs einen Beweis ü die Ta -
sache, dass – un e eine e mu lich gül igen Annahme übe die S uk u de Kom-
plexi ä sklassen – das on ihnen de inie e En scheidungsp oblem „Code Equi alence“
(= Ve einigung alle PCEFq ü alle endlichen Kö pe Fq) nich in die Klasse de NP-
olls ändigen P obleme einzuo dnen is :
„I is belie ed ha he polynomial- ime hie a chy does no collapse, and hus
we end up wi h he conclusion ha Code Equi alence is unlikely o be NP-
comple e.“
Eine ähnliche Schluss olge ung inde sich auch in [71] ü das G aphenisomo phiep o-
blem. Ande e sei s geben die Au o en in [62] abe auch einen Hinweis da au , dass es
sich um ein nich allzu ein aches P oblem handeln kann:
„Ye , we do s a e also a nega i e esul , namely, ha Code Equi alence is
also unlikely o be oo easy. We do his by ela ing Code Equi alence o he
G aph Isomo phism p oblem. [...] The p oblem o deciding e icien ly (i.e.,
in polynomial ime) whe he wo g aphs a e isomo phic is a no o iously open
ques ion in Compu e Science. The p oblem has been s udied ex ensi ely in
ecen decades, bu he s a e o he a is ha he e is no known e icien
algo i hm o de e mining whe he wo gi en g aphs a e isomo phic.“
Da Pe ank und Ro h die G aphenisomo phie nu übe eine Polynomialzei eduk ion
au PCEF2zu ück üh en, ließe sich du chaus a gumen ie en, dass das P oblem PCEFq
ü einen ande en endlichen Kö pe Fq, q > 2mögliche weise leich e zu bean wo en is .
Hie zu lie e jedoch [34] einen analoge Polynomialzei eduk ion des G aphenisomo phie-
p oblems au PCEFq.
Es sei im Folgenden Rein es o gegebene Ke en ing und es bezeichne Im∈Rm×m
die Einhei sma ix de Dimension m×mzu m∈N. Wi wollen nun das Resul a on
[34] nich nu au PCERsonde n auch au die En scheidungsp obleme LCERund SCER
e allgemeine n.
2.4.2 De ini ion. Es sei A∈ {0,1}n×meine Inzidenzma ix eines G aphen Gmi n
Punk en und mKan en. Wi de inie en zu Adie Gene a o ma ix
Γ(A):= ImIm1m×1A∈Rm×(2m+n+1)
eines linea en Codes C(A)≤R2m+n+1 de Länge 2m+n+ 1.
2.4.3 Hil ssa z. Γ(A)is bis au Zeilen e auschungen und -skalie ungen mi Einhei en
die eindeu ige Gene a o ma ix on C(A), welche olgende Eigenscha en e üll :
∀ ∈Rm: wH( ) = 1 ⇐⇒ wH Γ(A)= 5 (2.2)
24
2.4. Komplexi ä de P obleme
Beweis. Zunächs zeigen wi , dass Γ(A)die Bedingung (2.2) e üll : Sei ∈Rmbeliebig.
Is wH( ) = 1 so is Γ(A)ein Viel aches eine Zeile on Γ(A)und somi wH Γ(A)=
2+1+2 = 5. Ansons en e hal en wi ü das Hamming-Gewich die olgende Abschä zung
wH Γ(A)≥2 wH( )+wH( A)≥(4+2, alls wH( )=2
6, alls wH( )≥3.
Is Γ0eine wei e e Gene a o ma ix on C(A)mi de Eigenscha (2.2), so is Γ0=BΓ(A)
ü ein B∈GLm(R). Fü die i- e Zeile Bi,∗,i∈[m], on Bgil nun abe wHBi,∗Γ(A)=
wHΓ0
i,∗= 5 und somi wH(Bi,∗) = 1. Dami is Babe wegen seine In e ie ba kei
zwingend das P oduk eine Pe mu a ionsma ix und eine in e ie ba en Diagonalma-
ix.
2.4.4 Sa z. GI besi z eine Polynomialzei eduk ion au SCER.
Beweis. Wi zeigen, dass zwei gegebene Inzidenzma izen A0und A1genau dann isomo -
phe G aphen da s ellen, wenn die Gene a o ma izen Γ(A0)und Γ(A1)semilinea isome i-
sche Codes e zeugen. Diese Reduk ion is o ensich lich in Polynomialzei zu be echnen.
Zunächs gehen wi da on aus, dass die Inzidenzma izen A0und A1isomo phe G a-
phen da s ellen. Es exis ie en also Pe mu a ionen π∈Smund σ∈Snmi A1=
P(π)A0P(σ−1). Dann is abe
P(π)Γ(A0) P(π−1)
P(π−1)
1
P(σ−1)!= Γ(A1)
und dami e zeugen Γ(A0)und Γ(A1)pe mu a ionsisome ische Codes.
Fü die Rück ich ung nehmen wi an, dass die Codes C(A0)und C(A1)semilinea
isome isch sind. Dann exis ie eine Ma ix B∈GLm(R)und ein G uppenelemen
(ϕ;α, σ)∈(R∗)2m+n+1 o(Au (R)×S2m+n+1)
mi
Γ(A1)=B(ϕ;α, σ)Γ(A0)=BαΓ(A0)P(σ−1)diag(ϕ)−1=BΓ(A0)P(σ−1)diag(ϕ)−1.
Die Ma ix Γ(A0)P(σ−1)diag(ϕ)−1is eine Gene a o ma ix zu C(A1)mi de Eigenscha
(2.2). Da aus olg nun mi dem Hil ssa z, dass B=P(π)diag(ψ)das P oduk eine
Pe mu a ionsma ix P(π)∈Rm×mund eine in e ie ba en Diagonalma ix diag(ψ)∈
Rm×mis .
De Eins ek o Γ(A1)∗,2m=1m×1so g nun da ü , dass diag(ψ)kons an au de
Diagonalen is , also diag(ψ) = Im ü ein ∈R∗gil . Dami e hal en wi
Γ(A1)= ·P(π)Γ(A0)P(σ−1)diag(ϕ)−1.
25

2. G undlagen
Da P(π)Γ(A0)P(σ−1)und Γ(A1)nu Ein äge aus {0R,1R}besi zen, können wi ohne Be-
sch änkung de Allgemeinhei 5diag(ϕ) = Imannehmen. Somi haben wi eine Glei-
chung de Ges al
Γ(A1)=P(π)Γ(A0)P(σ−1)
e eich . Die R-linea en Codes C(A0)und C(A1)sind also auch pe mu a ionsisome isch.
Un e Be ücksich igung de Au omo phismen6 on C(A0)können wi wei e annehmen,
dass σdie Koo dina en {0, . . . , m−1},{m, . . . , 2m−1},{2m}und {2m+1,...,2m+n}
mengenweise ix läss . Un e diese Vo ausse zung is dann
Γ(A1)=P(π)Γ(A0) P(π−1)
P(π−1)
1
P(ρ−1)!
ü eine Pe mu a ion ρ∈Sn. Es is also A1=P(π)A0P(ρ−1)und dami sind A0und A1
Inzidenzma izen on isomo phen G aphen.
2.4.5 Folge ung. Fü einen beliebigen endlichen Ke en ing Rbesi z GI eine Polyno-
mialzei eduk ion sowohl au PCERals auch au LCER.
Beweis. Eine zen ale Aussage des Beweises zum o ausgegangenen Sa z is , dass die
on Γ(A0)und Γ(A1)e zeug en R-linea en Codes C(A0)und C(A1)genau dann semilinea
isome isch sind, wenn sie auch pe mu a ionsisome isch bzw. linea isome isch sind.
A0und A1sind also genau dann Inzidenzma izen on isomo phen G aphen, wenn
C(A0)und C(A1)pe mu a ionsisome isch bzw. linea isome isch sind.
Dami haben wi gezeig , dass die Isomo phiep obleme ü linea e Codes übe endli-
chen Ke en ingen mindes ens genauso schwe sind wie das G aphenisomo phiep oblem.
Die oben einge üh en Komplexi ä sklassen machen Aussagen übe die wo s -case-
Lau zei en de P obleme. Ein P oblem lieg nich in P, sobald es zu jedem Polynom
p∈R[x]eine nich lee e Teilmenge de e laub en Eingaben gib , welche ü das expo-
nen ielle Lau zei e hal en e an wo lich is . Es is also wei e hin du chaus möglich,
dass ü as alle Eingaben die Anzahl de Rechensch i e du ch das Polynom pnach
oben besch änk is . Dahe möch en wi im Folgenden auch ku z au die du chschni li-
che Komplexi ä de P obleme eingehen.
Mi Hil e des Suppo -Spli ing-Algo i hmus [66] wi d in [61] bewiesen, dass ü einen
beliebigen Kö pe Fqdie P obleme PCEFq ü as alle Eingaben in Polynomialzei gelös
we den können. Fü die Kö pe F3und F4wi d in [67] ein ähnliches Resul a ü die
P oblems ellungen LCEF3,LCEF4und SCEF4e eich . Gleichzei ig geben die Au o en
N. Send ie und D. Simos abe auch eine Ve mu ung übe die Kö pe Fq, q ≥5ab:
5Nullspal en müssen be ücksich ig we den, d.h. isolie e Kno en des G aphen. Diese können abe mi
beliebigen Einhei en mul iplizie we den, ohne den Code C(A0)zu ände n.
6Es können wei e e Einhei s ek o en ode Eins ek o en in de Ma ix A0en hal en sein.
26
2.4. Komplexi ä de P obleme
2.4.6 Ve mu ung (aus [67]).Zu gegebenem q≥5sind die P obleme LCEFqund SCEFq
ü as alle Eingaben schwe 7.
Aus de Reduk ion au das G aphenisomo phiep oblem schließen wi , dass es e mu -
lich zu jede de e minis ischen Tu ingmaschine zu Lösung on SCERund zu jedem
Polynom p∈R[X]ein Paa on Gene a o ma izen (Γ0,Γ1)mi Eingabelänge ngib , so
dass die Maschine meh als p(n)Rechensch i e zu Bean wo ung benö ig . Falls sich
die Ve mu ung 2.4.6 ü die Kö pe Fq, q ≥5bzw. auch ü beliebige Ke en inge Rbe-
wah hei e , is soga da on auszugehen, dass as alle Eingaben (Γ0,Γ1)dieses Ve hal en
zeigen. Insbesonde e e mu en wi auch, dass sich ge ade die ü die Codie ungs heo ie
in e essan en Codes in diese Hinsich ungüns ig e hal en we den.
Wi können also nich da on ausgehen, einen Kanonisie e zu en wickeln, welche in
de Lage is , die kanonische Fo m eine beliebigen Gene a o ma ix in Polynomialzei
in de Länge de Eingabe zu be echnen. Die Ve mu ung 2.4.6 ech e ig unse wei-
e es Vo gehen, einen Algo i hmus zu en wickeln, welche s e s ü alle Eingaben mi
exponen ielle Lau zei a bei e .
Da die Komplexi ä s heo ie uns also kein Maß ü die Bewe ung des Algo i hmus
an die Hand gib , können wi uns nu mi den wenigen konku ie enden Sys emen ü
linea e Codes übe endlichen Kö pe n e gleichen. Fü beliebige Ke en inge können
wi die Gü e des Algo i hmus nu übe seine p ak ische Anwendba kei au gewisse
in e essan e P oblemins anzen e i izie en, siehe Kapi el 6.
7Fas alle Eingaben we den on einem Lösungsalgo i hmus mi exponen iellen Au wand bea bei e .
27
3. Kanonisie ungsalgo i hmen
Zunächs sei Geine beliebige endliche G uppe, welche au eine endlichen Menge X
ope ie e. Die Ope a ion sei ohne Besch änkung de Allgemeinhei eu, d.h. de Ke n
N:= ∩x∈XS abG(x)de G uppenope a ion is i ial. Lieg diese Si ua ion nich o , so
is Nein No mal eile in Gund wi können s a dessen auch die induzie e1G uppen-
ope a ion on G/N au Xun e suchen. Auße dem wollen wi au Ximme eine gegebene
To alo dnung o ausse zen.
Zu Kanonisie ung des o liegenden kombina o ischen Objek s x∈Xun e de Ope-
a ion on Gwe den wi die P inzipien des Ve eine ns und Indi idualisie ens on Pa i-
ionen (pa i ion e inemen , indi idualiza ion) en wickeln. Diese algo i hmische G und-
idee bilde die Basis zu De ini ion eines Suchbaums, mi dessen Hil e de kanonische
Rep äsen an und die Au omo phismeng uppe on xbes imm we den können. Lau
eine Aussage in [56] a diese S a egie e s mals in [63] im Zusammenhang mi de
Isomo phiee kennung bei G aphen au . Auch alle gegenwä igen (we bewe bs ähigen)
Algo i hmen zu Be echnung eines kanonischen Rep äsen an en eines G aphen basie en
imme noch au diese G undlage. In [56] wi d hie zu eine de aillie e Lau zei analyse
de wich igs en Implemen ie ungen o genommen.
Die in Abschni 3.2 besch iebene Fo mulie ung is zunächs eine Ve allgemeine ung
des G aphenkanonisie e s [55]. Sie kombinie die zei gleich e schienenen Diskussionen
aus [35] und [42] und e gänz diese mi eigenen Ideen. Wi gehen wie olg o :
Zunächs besch eiben wi in Abschni 3.1 einige g undlegende Ideen, die wi bei de
En wicklung eines Kanonisie e s einb ingen können. Dies olg im Wesen lichen de Be-
sch eibung aus [35]. De Au o R. Gugisch bau aus diesen Einzelkomponen en den
Kanonisie e aus Abschni 3.2 ü die Ope a ion GX„ on un en“ au . Nach eil diese
He angehensweise is abe , dass de Ko ek hei sbeweis ü den Gesam algo i hmus mi
allen zusä zlichen Modi ika ionen schwe zu üh en is . Dahe übe nehmen wi diesen
Teil aus [42]. In diese Besch eibung, siehe Abschni 3.2, wi d g öße e We au das
Gesam bild geleg , ohne zu seh im De ail zu e sinken. Mi diesem Blick „ on oben“
wi d die Ko ek hei des Vo gehens so o o ensich lich.
Im Anschluss modi izie en wi diese Besch eibung aus [42] übe meh e e Sch i e hin-
weg de a , dass die Ko ek hei wei e hin leich e sich lich bleib und die Fo mulie ung
auch zu einem p axis auglichen Kanonisie e üh . Zum Beispiel besch eiben wi , wie
man die Au omo phismen des zu kanonisie enden Objek s x∈Xzu Ve besse ung des
Lau zei e hal ens einb ingen kann.
1gNx := gx.
29
3. Kanonisie ungsalgo i hmen
G uppe G≃(G×Sn)/Snau de Menge Sn Xn. Eine Bahn Sn(x0, . . . , xn−1)∈
Sn Xnkönnen wi abe eineindeu ig mi dem Inhal des Vek o s besch eiben,
d.h. übe eine Au zählung {{x0, . . . , xn−1}} alle Ein äge in ih e Viel achhei ,
die keinen We au die Reihen olge leg . Eine solche S uk u bezeichnen wi als
Mul imenge und wi no ie en diese mi doppel geschwei en Klamme n, um sie
on gewöhnlichen Mengen zu un e scheiden.
Somi haben wi einen al e na i en Ansa z zu Kanonisie ung on n-elemen igen
(Mul i-)Mengen un e de Ope a ion on Ggegeben. Da die Da s ellung eine
(Mul i-)Menge ohnehin inne halb des Compu e s übe eine geeigne e Ano dnung
de Elemen e ealisie we den muss, mach es übe dies Sinn, diese zusä zliche alge-
b aische S uk u übe die G uppenope a ion mi Snin dem Algo i hmenen wu
zu be ücksich igen.
Den Kanonisie e CanX
G×Snaus dem le z en Beispiel kann man wiede um übe das
Au spal en zu dem Homomo phismus ((g, π)7→ g, x 7→ Gx)gewinnen. Wi bezeichnen
mi Mn(X)die Menge alle n-elemen igen Mul imengen eine Menge X. Es e gib sich
olgendes Bild on Homomo phismen on G uppenope a ionen und die Möglichkei zu
De ini ion on Kanonisie e n:
Sn(G Xn)π←[(g,π)
←−−−−−
Gx←[xG×SnXn(g,π)7→g
−−−−→
x7→SnxG(Sn Xn)≃G(Mn(X))
CanG Xn
Sn
Au spal en
−−−−−−→ CanXn
G×Sn
Ve schmelzen
−−−−−−−→ CanSn Xn
G
Dieses Beispiel dien uns zu Mo i a ion des wei e en Vo gehens, jedoch sei da au hin-
gewiesen, dass in diesem Spezial all die Bahnenmengen G (Sn Xn),(G×Sn) Xnund
Sn (G Xn)ohnehin in Bijek ion s ehen, d.h. keine Au spal ungen und Ve schmelzungen
im eigen lichen Sinne s a inden. Es handel sich hie bei um äqui alen e Fo mulie ungen
des gleichen P oblems.
Schließlich möch en wi noch da au hinweisen, dass wi a sächlich die Kanonisie ung
zu G uppenope a ionen on G uppen GoSnau Mengen Xnzum Ziel haben we den.
Da GGoSnwei e hin No mal eile is , is die Gewinnung des Kanonisie e s CanXn
GoSn
aus CanG Xn
Snübe das Au spal en wei e hin möglich.
De Übe gang zu eine Ope a ion on Gau Sn Xnis abe , wegen de ehlenden
No mal eile eigenscha on Sn, nich ohne wei e e Vo ausse zungen möglich. In den on
uns zu un e suchenden Si ua ionen (z.B. semilinea e Isome ie on linea en Codes) is
die G uppe Gjedoch selbs ein semidi ek es P oduk HnoG0mi olgenden Annahmen:
•Die symme ische G uppe ope ie au HnoG0nu übe eine Pe mu a ion de
Komponen e Hn, d.h. (HnoG0)oSn=Hno(G0×Sn).
•Die G uppe G0ope ie simul an au allen Komponen en on Xnund die G uppe
Hnkomponen enweise.
36

3.1. G undbaus eine de Kanonisie ung
Dann können wi zunächs den No mal eile HnoSnhe aus eilen und e hal en
dami eine Ope a ion on G0au (HnoSn) Xn. Diese Menge können wi abe als
Sn (Hn Xn) = Mn(H X)in e p e ie en.
3.1.9 Beispiel. Die G uppe
(GLk(R)×(R∗)n)o(Au (R)×Sn)
ope ie au de Menge Rk×nalle k×n-Ma izen. Wi se zen H:= R∗und G0:=
ΓLk(R) = (GLk(R)oAu (R)). Dami e hal en wi also eine Ope a ion de G uppe
ΓLk(R)au Mn(R∗ Rk
R), ia
(A, α)· {{R∗? x0, . . . , R∗? xn−1}} := {{R∗? Aα(x0), . . . , R∗? Aα(xn−1)}}.
Fü ein ∈Rk
Rkönnen wi die Bahn R∗? ={ ϕ−1|ϕ∈R∗}abe ge ade mi dem
zyklischen Rech smodul R iden i izie en.
3.1.10 Folge ung. Zwei Gene a o ma izen Γ,Γ0∈Rk×n,(m,...,m)e zeugen genau dann
semilinea isome ische Codes, wenn die Mul imengen
{{Γ∗,iR|i∈[n]}} und {{Γ0
∗,iR|i∈[n]}}
de on den Spal en e zeug en zyklischen R-Rech smoduln un e de G uppenope a ion
on ΓLk(R)isomo ph sind.
Dami haben wi ein wei e es Theo em aus [52] au R-linea e Codes e wei e und den
wohlbekann en Zusammenhang zwischen dem Äqui alenzbeg i de Codie ungs heo ie
und dem de p ojek i en Geome ie he ges ell . Diese Zusammenhang wi d e wa in
[37, 45, 73] und ielen wei e en A bei en zu Kons uk ion on gu en linea en Codes
aus Punk kon igu a ionen de p ojek i en Rech s-Hjelmsle -Geome ie ausgenu z , siehe
auch Kapi el 6.1.
Gleicha ig e häl es sich, wenn wi in de p ojek i en Geome ie on den eindimen-
sionalen Un e äumen (=Punk en) zu -dimensionalen Un e äumen übe gehen. Dies
wi d uns eine Bijek ion de Äqui alenzklassen on Ne wo k-Codes übe Fqund den
Äqui alenzklassen on Fq-linea en Codes übe dem Alphabe Fq lie e n, siehe Kapi el
6.3.
3.1.2. Kanonisie ung übe Un e g uppen
Nich imme is es möglich, einen leich zu be echnenden G-Homomo phismus anzu-
geben, ü den die Kanonisie ung im Bildbe eich e izien zu implemen ie en is . Zumeis
lieg ü diesen dann die Si ua ion o , dass S abG( (x)) gleich Gis und somi keine
In o ma ion gewonnen we den kann. Wi wollen nun zeigen, wie sich das Au e en diese
Si ua ion umgehen läss .
37
3. Kanonisie ungsalgo i hmen
Zunächs nehmen wi an, es sei eine Un e g uppe U on Ggegeben, ü die wi be ei s
einen e izien en Kanonisie e CanUen wickel haben. Des Wei e en benö igen wi ü
unse Vo gehen eine T ans e sale Tde Rech snebenklassen U G. Dann können wi den
Kanonisie e CanG= (CFG,TRG,S abG)wie olg de inie en:
•Zu einem gegebenen x∈Xbe echne CFG(x) := min ∈TCFU( x)und speiche e in
T0diejenigen T ans e salenelemen e, welche zum Minimum üh en;
•se ze TRG(x) := TRU( 0x) 0 ü ein 0∈T0;
•e zeuge den S abilisa o S abG(x)übe
−1
0S abU( 0x) 0und {TRG(x)−1TRU( x) | ∈T0}
Wi bezeichnen dieses Vo gehen als das Heben eines Kanonisie e s ü die Ope a ion
mi Uzu einem Kanonisie e ü G. Im Wesen lichen ze legen wi das P oblem also in
|U G|=|G|
|U|Teilp obleme in de Ho nung, dass diese ein ache zu lösen sind.
Wi können dieses Vo gehen zum Beispiel dann einse zen, wenn wi keinen geeigne-
en G-Homomo phismus ü die Anwendung des Homomo phiep inzips angeben können,
jedoch seh wohl einen U-Homomo phismus zu Ve ügung haben.
3.1.11 Beispiel. Es sei de olgende G aph Γ = ([8], E)gegeben:
0
1
2
3
4
5
6
7
Fü diesen G aph is o ensich lich de Zykel (0,1,2,...,7) ∈S8ein Au omo phismus.
Somi we den wi die Kno en du ch Anwendung eines beliebigen S8-Homomo phismus
nich un e scheiden können.
Ze legen wi jedoch das P oblem mi Hil e de Un e g uppe U= S abS8(0), so b e-
chen wi die Symme ie und wi können einen e izien e en Kanonisie e ü Uübe den
U-Homomo phismus
: [2]([8]
2)→N8, E 7→ (Länge eines kü zes en P ades in E on inach 0)i∈[8]
en we en. Wi e hal en dann (Γ) = (0,1,2,3,4,3,2,1). Bei de Anwendung des Ho-
momo phiep inzips so ie en wi diesen Vek o lexikog aphisch au s eigend, e wa übe
die Anwendung de Pe mu a ion π= (2,3,6,4,7). Anschließend wenden wi diese Pe -
mu a ion auch au Γan und sch änken uns im wei e en Ve lau au den S abilisa o
U0= S abU((0,1,1,2,2,3,3,4)) = h(1,2),(3,4),(5,6)i
38
3.2. Pa i ionen und Ve eine ungen
des kanonischen Rep äsen an en (πΓ) = (0,1,1,2,2,3,3,4) ein.
Es is leich einzusehen, dass die kanonischen Rep äsen an en CFU( Γ) ü alle Rech s-
ans e salenelemen e ∈T on U Gin diesem Beispiel iden isch sind. Übe dieses
Vo gehen we den wi also maximal |T| · S abU( ( x)) = 8 ·8 = 64 Pe mu a ionen un e -
suchen.
Ein wei e e solche Sch i mi de Un e g uppe S abU0(1) in de Kanonisie ung ü
U eduzie in diesem Beispiel die Anzahl de zu be ach enden Pe mu a ionen soga
au die Mäch igkei 16 de Au omo phismeng uppe.
3.2. Pa i ionen und Ve eine ungen
In diesem Abschni wollen wi nun au zeigen, wie wi die o angegangenen Ideen zu
De ini ion eines e izien en Kanonisie e s zusammen ügen. Wi we den dazu einen Back-
ack-Algo i hmus zum sys ema ischen Du chlau de G uppe G o mulie en. Das Vo ge-
hen läss sich ü ein x∈Xam bes en übe die De ini ion eines zugehö igen Suchbaums
T(x, G)analog zu [42] besch eiben. Wiede sei mi L(G)die Menge alle Un e g uppen
on Gbezeichne und mi C(G)die Menge alle Rech snebenklassen alle Un e g uppen
H on G.
Die Kno en des Suchbaums T(x, G)we den on eine Teilmenge de Rech sneben-
klassen Hg ∈ C(G)gebilde . Die Un e g uppe H ep äsen ie dabei genau diejenigen
G uppenelemen e, welche wi in diese Phase des Algo i hmus noch zu Anwendung
b ingen wollen. Das G uppenelemen gwu de an diese S elle be ei s au xangewand .
De Baum selbs beziehungsweise de Ablau des Algo i hmus wi d induk i übe die
olgenden Basisope a ionen de inie :
Pa i ionie ung Die Nebenklasse Hg mi |H|>1wi d ze leg in eine disjunk e Men-
ge on Nebenklassen {H0h0g, . . . , H0hu−1g}eine ech en Un e g uppe H0< H.
Die Menge {h0, . . . , hu−1}sei dabei eine beliebige Rech s ans e sale on H0in H.
Dieses Vo gehen haben wi oben als das Heben eines Kanonisie e s ü die Ope-
a ion mi de Un e g uppe H0zu einem Kanonisie e ü die Ope a ion mi H
besch ieben.
O ensich lich läss sich diese Ope a ion be ei s du ch Angabe de Un e g uppe H0
eindeu ig besch eiben. Um gleiche Resul a e bei isomo phen Eingaben ga an ie en
zu können, se zen wi o aus, dass diese Ope a ion übe die Be ei s ellung eine
G-In a ian en
I:X× C(G)→ L(G),(x, Hg)7→ H0mi H0< H (3.1)
eindeu ig bes imm is . Dabei is die Ope a ion on Gau dem De ini ionsbe eich
X× C(G)übe die De ini ion
g0?(x, Hg) := (g0x, Hgg−1
0) ü alle g0∈G, (x, Hg)∈X× C(G)
gegeben.
39
3. Kanonisie ungsalgo i hmen
Ve eine ung Un e eine Ve eine ung e s ehen wi das E se zen eine Nebenklasse
Hg du ch eine Teilmenge H0hg mi H0≤Hund h∈H. Auch diese Vo gehen
kann mi Hil e eines G-Homomo phismus
V:X× C(G)→ C(G),(x, Hg)7→ (H0hg)mi H0≤Hund h∈H(3.2)
besch ieben we den. Wie wi spä e zeigen we den, e hal en wi Ve eine ungen
übe die Anwendung des Homomo phiep inzips.
Es läss sich leich e i izie en, dass die Bedingungen, welche in [42] an diese Ba-
sisope a ionen ges ell we den, äqui alen zu unse e Fo de ung de G-In a ianz bzw.
G-Homomo phie de Funk ionen Iund Vsind. Nun können wi den eigen lichen Au -
bau des Suchbaums T(x, G)besch eiben:
3.2.1 De ini ion. Es sei x∈Xbeliebig. Wi de inie en einen Wu zelbaum T(x, G)
induk i wie olg :
1. Die Wu zel des Baums T(x, G)wi d on de Ve eine ung V(x, G)gebilde .
2. Fü einen Kno en Hg mi |H|>1sei H0:= I(x, G)und {h0, . . . , hu−1}eine
Rech s ans e sale on H0in H. Die Kinde {V(x, H0h0g), . . . , V (x, H0hu−1g)} on
Hg we den dann übe die Ve eine ung de Pa i ionie ung de inie .
3.2.2 Fak ([42], Theo em 5.30).Fü x∈Xund g0∈Ginduzie die G uppenope a ion
on Gau C(G)einen Isomo phismus de Suchbäume T(x, G)und T(g0x, G), d.h.
•die Wu zel on T(g0x, G)is g0? V (x, G) = V(x, G)g−1
0,
•Hg ∈ C(G)is genau dann ein Kno en on T(x, G), wenn Hgg−1
0ein Kno en in
T(g0x, G)is und
•{H0hg, Hg}is genau dann eine Kan e in T(x, G), wenn {H0hgg−1
0, Hgg−1
0}eine
Kan e in T(g0x, G)is .
Eine eingängige Visualisie ung dieses Theo ems zeig Abbildung 3.4.
Au g und unse e De ini ion we den die Bla kno en on T(x, G) on einelemen igen
Mengen {g}mi g∈Ggebilde . Wi wollen die Menge diese G uppenelemen e mi
L(x, G) := {g∈G| {g}Bla in T(x, G)} ⊆ G
bezeichnen.
3.2.3 Folge ung. Die Abbildung x7→ {gx |g∈L(x, G)}is G-in a ian . Insbesonde e
de inie also die Zuo dnung CFG(x) := min{gx |g∈L(x, G)}einen kanonischen
Rep äsen an en ü x∈X.
40
3.2. Pa i ionen und Ve eine ungen
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.: Illus a ion on Fak 3.2.2, siehe auch [42, Figu e 5.3]
Beweis. Is g0∈Gbeliebig, so is nach Fak 3.2.2 die Menge de Bla kno en on
T(g0x, G)bes imm du ch Rech smul iplika ion de Blä e on T(x, G)mi g−1
0. Es is
also L(g0x, G) = L(x, G)g−1
0und somi
{gx |g∈L(x, G)}={gg−1
0g0x|g∈L(x, G)}={g0g0x|g0∈L(g0x, G)}.
Dami haben wi die G-In a ianz gezeig und somi auch, dass die Funk ion CFG(x) :=
min{gx |g∈L(x, G)}eine Kanonisie ung de inie .
Wi we den im Folgenden zu x∈Xmi
L0(x, G) := {g∈L(x, G)|gx = CFG(x)}
die Menge alle T anspo e elemen e bezeichnen. En scheidend ü die Lau zei des Al-
go i hmus is nun die F age, wie wi möglichs iele Äs e des Suchbaums T(x, G)ab-
schneiden können, ohne wesen liche In o ma ionen zu e lie en.
Zum einen können wi bekann e Au omo phismen A≤S abG(x)des Objek s xaus-
nu zen, da es o ensich lich genüg , eine T ans e sale on L0(x, G)/A zu un e suchen.
Eine Diskussion diese Me hode inde sich im Abschni 3.2.2. Zunächs wollen wi uns
abe de F age:
„Is L0(x, G)∩Hg =∅ ü einen Kno en Hg on T(x, G)?“
zuwenden. O ensich lich können wi – ü eine beliebig gewähl e To alo dnung (X, ≤)–
dies nu dann en scheiden, alls wi CFG(x)und Hgx be ei s kennen.
Nun e olg e abe die Wahl de To alo dnung au Xzu De ini ion des Minimums
in Folge ung 3.2.3 willkü lich. Wi we den also e suchen diese Wahl unse em P oblem
anzupassen, d.h. wi wollen eine To alo dnung wählen, welche einen e izien en Tes au
L0(x, G)∩Hg =∅e möglich . Dazu beobach en wi zunächs , dass wi die Ve eine ung
V:X× C(G)→ C(G)auch als Anwendung des Homomo phiep inzips sehen können.
41

3. Kanonisie ungsalgo i hmen
3.2.4 Sa z. Fü alle H∈ L(G)sei ein H-Homomo phismus H:X7→ Ygegeben sowie
ein Kanonisie e y7→ (CFH(y),TRH(y),S abH(y)). Dann is
V:X× C(G)→ C(G),(x, Hg)7→ S abH(CFH( H(gx))) TRH( H(gx))g(3.3)
ein G-Homomo phismus und e üll somi die Bedingungen an eine Ve eine ung.
Beweis. Zunächs zeigen wi die Wohlde inie hei de Abbildungs o sch i : Sind g, g0∈
G e schiedene Nebenklassen ep äsen an en on Hg, e wa hg =g0 ü ein h∈H, so gil
TRH( H(gx))
| {z }
=:h
H(gx) = CFH( H(gx)) = CFH( H(g0x)) = TRH( H(g0x))
| {z }
=:h0
H(g0x),
denn H(gx)und H(g0x) = h H(gx)liegen in de gleichen H-Bahn. Wi olge n hie aus,
dass H:= S abH(CFH( H(gx))) unabhängig on dem Nebenklassen ep äsen an en gis .
Es bleib zu zeigen, dass Hh0g0=Hhg is . Wi zeigen hie zu h0hh−1∈H:
h0hh−1CFH( H(gx)) = h0hh−1h H(gx) = h0 H(hgx) = h0 H(g0x)
= CFH( H(g0x)) = CFH( H(gx))
Die Behaup ung übe die G-Homomo phie de Abbildung Vbeweis man olgende -
maßen: Es seien g0∈Gund (x, Hg)∈ C(G)beliebig. Dann gil :
V(g0?(x, Hg)) = V(g0x, Hgg−1
0)
= S abHCFH( H(gg−1
0g0x))TRH( H(gg−1
0g0x))gg−1
0
=V(x, Hg)g−1
0=g0? V (x, Hg)
Im Folgenden se zen wi o aus, dass die Ve eine ung Vübe eine es e Wahl eine
Familie ( H)H∈L(G) on H-Homomo phismen de inie sei. Dabei sei ohne Besch änkung
de Allgemeinhei die Menge Y o algeo dne 3.
Übe die H-Homomo phismen können wi dann induk i eine Bewe ung B(x, Hg)
au den Kno en des Suchbaums T(x, G)ein üh en:
1. Die Wu zel Hg =V(x, G)sei mi B(x, Hg)=( G(gx)) bewe e .
2. Is H0hg ein Kno en de Tie e i > 0im Baum T(x, Hg)mi Va e Hg und Bewe -
ung B(x, Hg) = (y0, . . . , yi−1), so de inie en wi
B(x, H0hg) := (y0, . . . , yi−1, I(x,Hg)(hgx)).
3. Is {g}ein Bla kno en, so modi izie en wi dessen ak uelle Bewe ung du ch das
zusä zliche An ügen on gx.
3Dies können wi imme e eichen, da wi Y=SH∈L(G) H(X)als endliche Ve einigung endliche
Mengen wählen können.
42
3.2. Pa i ionen und Ve eine ungen
3.2.5 Hil ssa z. Is Hg ein Kno en in T(x, G)mi Bewe ung B(x, Hg)und g0∈Gbe-
liebig, so äg de Kno en Hgg−1
0in T(g0x, G)eine iden ische Bewe ung B(g0x, Hgg−1
0)
=B(x, Hg).
Beweis. Is g0∈Gbeliebig und H0hgg−1
0ein Kno en in T(g0x, G), dann is übe eine
Induk ion übe die Tie e de Kno en leich zu beweisen, dass die Bewe ungs ek o en
B(g0x, H0hgg−1
0)und B(x, H0hg)übe eins immen:
Im Induk ionssch i schließ man aus de G-In a ianz on Izunächs , dass H:=
I(x, Hg) = I(g0x, Hgg−1
0)gel en muss. Dami is abe o ensich lich die Gleichhei on
H(hgg−1
0g0x) = H(hgx)s e s gegeben. Is H0hg ={hg}übe dies ein Bla , so is auch
do die ange üg e Bewe ung hgg−1
0g0x=hgx iden isch.
3.2.6 Folge ung. Is g0∈S abG(x)und {g}ein Bla on T(x, G), so is {gg0}eben alls
ein Bla on T(x, G)mi Bewe ung B(x, {gg0}) = B(x, {g}).
Beweis. Es de inie g−1
0∈S abG(x)einen Au omo phismus on T(x, G). Nach dem
o angegangenen Hil ssa z is somi {gg0}eben alls ein Bla on T(x, G) = T(g−1
0x, G)
mi eine iden ischen Bewe ung.
Du ch die Blä e {g} on T(x, G)e hal en wi übe den lexikog aphischen Ve -
gleich de Bewe ung B(x, {g})eine wohlde inie e To alo dnung au de Teilmenge
{gx |g∈L(x, G)}de Bahn Gx. Wi können diese zu Minimumbildung und dami
zu eindeu igen Fes legung eines kanonischen Rep äsen an en he anziehen. Diese O d-
nung au Xha nun den Vo eil, dass wi be ei s beim Du chlau des Suchbaums nich
op imale Äs e e kennen und abschneiden können:
3.2.7 Folge ung. Es seien Hg und H0g0Kno en de gleichen Tie e ides Suchbaums
T(x, G). Dann gil
B(x, Hg)< B(x, H0g0) =⇒H0g0∩L0(x, G) = ∅.
Zusammen assend e hal en wi also den olgenden Kanonisie e CanG ü die G up-
penope a ion on Gzu eine Eingabe x∈X:
•Bilde einen Suchbaum T(x, G)übe eine es gewähl e Pa i ionie ungs o sch i
Iund Ve eine ung Vun e e en uelle Be ücksich igung des Abschneidek i e i-
ums aus Folge ung 3.2.7. (Wi geben hie zu auch eine aus üh liche, wei e üh ende
Diskussion in Abschni 3.2.3).
•Bes imme die Menge
L0(x, G) := {g∈L(x, G)|B(x, {g})≤B(x, {g})∀g∈L(x, G)}
alle Blä e mi minimale Bewe ung.
•Wähle ein Elemen TRG(x)∈L0(x, G)beliebig.
43
3. Kanonisie ungsalgo i hmen
•Se ze CFG(x) := TRG(x)x.
•Be echne SG(x) := {TRG(x)−1g|g∈L0(x, G)}.
3.2.8 Sa z. Die oben e klä e Funk ion
CanG:X→X×G× L(G)
x7→ (CFG(x),TRG(x), SG(x))
de inie eine Kanonisie ung ü die G uppenope a ion on Gau X.
Beweis. Die Ko ek hei de Aussage zu dem kanonischen Rep äsen an en und dem ge-
wähl en T anspo e elemen olg so o aus de o angegangenen Diskussion. Die Menge
SG(x)is o ensich lich eine Teilmenge on S abG(x). Is umgekeh g0∈S abG(x)be-
liebig, so gil
L0(x, G)g−1
0=L0(g0x, G) = L0(x, G).
Dami exis ie ein G uppenelemen g∈L0(x, G)mi TRG(x) = gg−1
0und es is
g0= TRG(x)−1g∈SG(x).
3.2.1. Zu Kanonizi ä un e isomo phen G uppenope a ionen
Wi wollen nun besp echen, inwiewei de on uns besch iebene Algo i hmus zu Ka-
nonisie ung on de Da s ellung de G uppenope a ion abhäng . Wi be ach en also
eine wei e e G uppenope a ion on G0au X0, welche zu de u sp ünglichen Ope a i-
on on Gau Xisomo ph is , d.h. es gib einen G uppenisomo phismus Ψ : G0→G
und eine Bijek ion Φ : X0→X, welche mi den G uppenope a ionen e äglich sind:
Φ(g0x0) = Ψ(g0)Φ(x0) ü alle g0∈G0und x0∈X0.
Als Mo i a ion dien uns das nach olgende Beispiel, welches wi in Abschni 5.2.3
dann wiede au g ei en we den.
3.2.9 Beispiel. Wi wollen annehmen, dass wi linea e Codes übe isomo phen Ke -
en ingen Rund R0be ach en, die e wa du ch den Ringisomo phismus α:R0→R
au einande übe ge üh we den können. Dann en sp ich die Abbildung Φde kompo-
nen enweise Anwendung on αau die Vek o en in Rn. Zusammen mi dem G uppen-
isomo phismus
Ψ : (R0∗)no(Au (R0)×Sn)→(R∗)no(Au (R)×Sn)
(ϕ;β, π)7→ (α(ϕ); αβα−1, π)
e hal en wi dann einen Isomo phismus on G uppenope a ionen.
44
3.2. Pa i ionen und Ve eine ungen
Wi gehen nun zunächs zu de u sp ünglichen De ini ion des Suchbaums zu ück und
nehmen an, dass die Ve eine ungs unk ion ü die isomo phe Ope a ion wie olg de i-
nie sei:
V0:X0× C(G0)→ C(G0),(x0, H0g0)7→ Ψ−1(V(Φ(x0),Ψ(H0g0))).(3.4)
Auße dem sei die Pa i ionie ung übe
I0:X0× C(G0)→ L(G0),(x0, H0g0)7→ Ψ−1(I(Φ(x0),Ψ(H0g0))) (3.5)
gegeben.
3.2.10 Hil ssa z. Die Abbildung V0is ein G0-Homomo phismus. Die Abbildung I0is
eine G0-In a ian e.
Beweis. Wi zeigen die Aussage exempla isch ü V0. Es sei g0
0∈G0,x0∈X0und
H0g0∈ C(G0)beliebig. Dann gil :
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)
Is nun x0∈X0beliebig, so wollen wi mi T0(x0, G0)den übe V0und I0de inie en
Suchbaum zu Kanonisie ung on x0∈X0bezeichnen. Dabei wollen wi zunächs das
Abschneiden on Teilbäumen übe die Bewe ungs unk ion noch unbe ücksich ig lassen.
3.2.11 Hil ssa z. Die Suchbäume T0(x0, G0)und T(Φ(x0), G)sind isomo ph, d.h.
•die Wu zel on T(x0, G0)is Ψ−1(V(Φ(x0), G)),
•Ψ−1(Hg)is genau dann ein Kno en on T(x0, G0), wenn Hg ∈ C(G)ein Kno en
on T(Φ(x0), G)is und
•{Ψ−1(H0hg),Ψ−1(Hg)}is genau dann eine Kan e in T(x0, G0), wenn {H0hg, Hg}
eine Kan e in T(Φ(x0), G)is .
Beweis. Wi üh en eine Induk ion nach de Tie e des Kno ens Hg im Baum T(Φ(x0), G)
du ch. Is de Kno en Hg die Wu zel on T(Φ(x0), G), so gil
Ψ−1(Hg) = Ψ−1(V(Φ(x0), G)) = V0(x0, G0).
Dami is de Induk ionsan ang be ei s gezeig .
Is nun Hg ein beliebige Kno en und H6={1G}, so we den die Kinde on Hg du ch
einen Pa i ionie ungssch i und die nach olgende Ve eine ung gewonnen. Is Teine
45
3. Kanonisie ungsalgo i hmen
3.2.26 Hil ssa z. Es sei π∈Snund P:= (P0, . . . , P`−1)eine kanonische Pa i ion zu
0 = n0< n1< . . . < n`=n. Dann gib es in de Rech snebenklasse SPπgenau dann
opologische Ano dnungen zu einem olls ändigen Labelled B anching (([n], E), σ) on
A≤Sn, wenn aus (i, j)∈Ebe ei s FP(π(i)) ≤ FP(π(j)) olg .
Beweis. Zu i∈[n]bezeichne i0:= FP(π(i)) die Fa be des Bilds π(i).
Wi nehmen zunächs an, dass π∈Sndie Implika ion nich e üll , es also eine Kan e
(i, j)∈Egib mi i0=FP(π(i)) >FP(π(j)) = j0. Fü eine beliebige Pe mu a ion
σ∈SPliegen die Bilde σπ(i)∈Pi0bzw. σπ(j)∈Pj0abe in den gleichen Mengen wie
π(i)bzw. π(j). Dami is abe wegen σπ(j)≤nj0+1 −1< ni0≤σπ(i)die Pe mu a ion
σπ eben alls keine opologische Ano dnung zu ([n], E).
Fü die Rück ich ung geben wi eine Pe mu a ion σ∈SPan, so dass σπ eine opolo-
gische Ano dnung zu ([n], E)is . Wi wählen hie zu σ∈SPde a , dass in jedem Block
P`0= [n`0+1] [n`0],`0∈[`]die U bilde on σπ lexikog aphisch angeo dne sind:
π−1σ−1(n`0)< . . . < π−1σ−1(n`0+1 −1).
Eine solche Pe mu a ion exis ie , da wi – mi Hil e de G uppenope a ion on Snau
[n]n– mi de G uppe SPden Vek o
(π−1(0), . . . , π−1(n−1)) = (0, . . . , n −1) ·P(π−1)
blockweise lexikog aphisch so ie en können. Die Einsch änkung de Abbildung (σπ)−1
au einen Block P∈Pis also o dnungse hal end. Fü eine beliebige Kan e (i, j)∈E
gil nun en wede
•i0< j0und dami ohnehin σπ(i)≤ni0+1 −1< nj0≤σπ(j),
•ode es is i0=j0und dami nach Kons uk ion σπ(i)< σπ(j), da ü die U bilde
i, j ∈(σπ)−1(Pi0)die Rela ion i<jgil .
Anhand de Bahnen de G uppe Hau [n] ü einen Kno en Hg in T(x, G)können
wi eine minimale kanonische Young-Un e g uppe H≤SP ü diesen Tes bes immen.
Wiede läss sich du ch einen Basiswechsel e eichen, dass die Bahnen on HIn e alle
bilden. Somi s eh die olls ändige In o ma ion aus dem Hil ssa z zu Ve ügung. Wi
we den abe im Abschni 3.2.4 au zeigen, dass dies in den on uns be ach e en Fällen
bei geeigne e Wahl de Homomo phismen Hund de Pa i ionie ungs o sch i Inich
no wendig is , da alle im Back acking au e enden G uppen H≤Sns e s kanonische
Young-Un e g uppen sind.
3.2.3. Implemen ie ungsde ails
De Algo i hmus aus Sa z 3.2.8 mach noch keine Aussage zum Au bau des Suchbaums
T(x, G). Dies möch en wi – da nun alle e o de lichen Hil smi el zu Ve ügung s ehen
– an diese S elle nachholen.
52

3.2. Pa i ionen und Ve eine ungen
•Im Rahmen eine B ei ensuche kann man übe die Bewe ungs unk ion Bleich
Teilbäume iden i izie en, die nich zu Elemen en g∈L0(x, G) üh en. Da wi
Au omo phismen abe nu übe besuch e Bla kno en au inden we den, bedeu e
dies auch, dass wi diese e s im le z en Sch i e eichen we den. Somi kann das
Abschneiden nach Hil ssa z 3.2.26 nu seh eingesch änk genu z we den.
•Umgekeh können wi im Rahmen eine Tie ensuche den ak uellen Kno en H0g0
de Tie e i– wegen de nich olls ändigen In o ma ion übe die au e enden
Bewe ungen – nu dann abschneiden, alls ein ande e , be ei s besuch e Kno en
Hg de gleichen Tie e imi kleine e Bewe ung B(x, Hg)< B(x, H0g0)exis ie .
Man wi d also auch Teilbäume un e suchen, de en Blä e nich in de Menge
L0(x, G)liegen. Das zule z besuch e Bla lie e wäh end de Lau zei imme nu
einen Kandida en ü das T anspo e elemen .
Jedoch de inie en gleich bewe e e Blä e imme einen Au omo phismus on x,
unabhängig da on ob sie den kanonischen Rep äsen an en de inie en. Eine s e ig
wachsende Un e g uppe A≤S abG(x)des S abilisa o s on xs eh also be ei s
ühzei ig zu Ve ügung, um das Abschneidek i e ium aus Hil ssa z 3.2.26 anzu-
wenden. Auße dem muss im Rahmen eine Tie ensuche imme nu die lokale In-
o ma ion abgespeiche we den, d.h. im wesen lichen die Zus ände de Vo ah en
zum ak uellen Kno en Hg.
Es is leich e sich lich, dass das Lau zei e hal en eines solchen Algo i hmus auch
en scheidend on de Ta sache abhängig is , wann zum e s en mal ein Bla aus
de Menge L0(x, G)e eich wi d. Dahe kann es bei e schiedenen isomo phen
Eingaben xund x0=g0xzu e heblichen Lau zei un e schieden kommen.
•Eine iel e sp echende Kombina ion beide Ansä ze im Be eich de G aphenka-
nonisie ung wi d gegenwä ig in [56] disku ie . De Baum wi d in B ei ensuche
du chlau en. Dabei wi d jedem au e enden Kno en Hg ein zu ällig gewähl e
Bla kno en {g0}mi g0∈Hg zugeo dne . Die Au o en nennen diese Zuo dnung
einen expe imen ellen P ad zu einem Bla kno en. Nach dem Abschneiden mi -
els de Bewe ungs unk ion we den zusä zlich noch die Bahnenelemen e g0xzu
den expe imen ellen P aden gebilde und e glichen. Bei Gleichhei kann de so
ge undene Au omo phismus zu den E zeuge n de G uppe Ahinzuge üg we den.
•Schließlich möch en wi noch au das sogenann e I e a i e Deepening hinweisen,
welches den zu e wa enden hohen Speiche beda eine B ei ensuche mi dem
Einsa z eines höhe en Rechenau wands e such zu e meiden. R. Gugisch [35,
Sei e 87] sch eib hie zu:
„Als Lösung bie e sich an, den Baum i e a i meh mals zu du chlau en,
und in jedem Du chlau eine Ebene wei e o zud ingen. In Du chlau i
we den also nu die Kno en bis zu Ebene ibesuch und das Op imum
[...] bes imm . So kann man bei den da au olgenden Du chläu en alle
au Ebene i nich op imalen Kno en übe sp ingen.
53
3. Kanonisie ungsalgo i hmen
Dieses als I e a i e Deepening bekann e Vo gehen benö ig e s aunliche -
weise kaum meh heo e ischen Au wand als eine B ei ensuche.“
Bei R. Gugisch we den die Bahnenelemen e gx de Nebenklassen e e e galle
Kno en Hg de Tie e idi ek mi einande e glichen9. Dami eduzie sich de
Rechenau wand – abe auch die E olgsaussich en zu Gene ie ung on Au omo -
phismen – na ü lich e heblich im Ve gleich zu dem Ve ah en expe imen elle P ade
analog zu [56] zu bes immen. Eine Kombina ion beide Ansä ze s ell somi eine
wei e e seh in e essan e S a egie da .
Im Wei e en we den wi den Suchbaum imme übe eine Tie ensuche au bauen, da
sich eine klassische B ei ensuche wegen des benö ig en Speiche beda s unp ak ikabel
e weis . Ebenso e schien uns das I e a i e Deepening als nich geeigne , da sich de
Au wand zu Bes immung de Kinde in unse em Fall wesen lich echenin ensi e als
bei [35] ges al e und auße dem wie be ei s besp ochen, die F age nach de Bes immung
de Au omo phismen unzu eichend bean wo e wu de. Eine Un e suchung de S a egie
nach [56] konn e leide aus zei lichen G ünden nich meh umgese z we den.
3.2.27 Beme kung. Möch e man nu die Au omo phismeng uppe on xbes immen,
so genüg es, die Bewe ung des zue s e eich en Bla kno ens {g0}he anzuziehen. Man
schneide dann im Back ackdu chlau einen Teilbaum mi Wu zelkno en Hg au Tie e
i > 0ab, alls B(x, {g0})i6=B(x, Hg)igil .
3.2.28 Beme kung. Will man zwei Elemen e x, x0∈Xausschließlich au Isomo phie
es en, so kann man die Bewe ung eines beliebigen Bla kno ens {g0}in T(x, G)als
Abschneidek i e ium ü die E zeugung on T(x0, G)he anziehen. Man b ich das Back-
acking an den Kno en Hg on T(x0, G)au Tie e i≥0ab, ü welche die Bewe ungen
B(x0, Hg)inich mi den en sp echenden We en B(x, {g0})iübe eins immen. E eich
man ein Bla {g0}, so gil g0x0=g0xund man kann den Algo i hmus mi posi i e
An wo so o beenden. D ing de Algo i hmus nich bis zu den Blä e n on T(x0, G)
o , so liegen die Elemen e x, x0in e schiedenen Bahnen Gx 6=Gx0.
3.2.4. Spezial all: Die Kanonisie ung on G aphen
Wi wollen nun als Beispiel die Kanonisie ung eines G aphen Γ = ([n], E)un e de
Ope a ion de symme ischen G uppe Snun e suchen. Insbesonde e wollen wi hie bei
au zeigen, dass sich die in de Li e a u [41], [55], [56], u. .m. en wo enen Algo i h-
men zu Ope a ion de symme ischen G uppe Snals Spezial all des hie da ges ell en
Algo i hmus besch eiben lassen.
9Wi wollen jedoch da au hinweisen, dass die an diese S elle gemach e Aussage [35, Sei e 87]
„gop x∼i−1gimi a:= g−1
op gi∈G(xi,...,xn−1), so is a∈Gx“
im Allgemeinen inko ek is .
54
3.2. Pa i ionen und Ve eine ungen
Zunächs s ellen wi den Zusammenhang zwischen geo dne en Pa i ionen und Ne-
benklassen he , da die oben genann en Implemen ie ungen einen Suchbaum au bauen,
dessen Kno en mi geo dne en Pa i ionen besch ieben we den. Zu eine geo dne e Pa -
i ion p= (p0, . . . , p`−1) on [n]sei nun imme P= (P0, . . . , P`−1)diejenige kanonische
Pa i ion on [n] ü die |pi|=|Pi|,∀i∈[`]gil . Die geo dne e Pa i ion p ep äsen ie
in den oben genann en Algo i hmen die Menge alle Pe mu a ionen
Sp
n:= {π∈Sn|π(pi) = Pi,∀i∈[`]}.
Sie läss sich auch übe die Nebenklasse Sp
n=SPπ∈ C(Sn)mi π∈Sp
nausd ücken.
Somi is also gezeig , dass die geo dne e Pa i ion pnu eine wei e e Da ens uk u zu
Ve wal ung de Nebenklassen SPπda s ell .
Au de Menge alle Pa i ionen on [n]läss sich wie olg eine Halbo dnung de inie-
en:
pq:⇐⇒ (∀i, j ∈[n] : Fq(i)<Fq(j) =⇒ Fp(i)<Fp(j))
Sind pund qPa i ionen on [n]und p≺q, dann sagen wi pis eine als qode p
is eine Ve eine ung on q. Eine Ve eine ung p≺qimplizie , dass jede Block on
pin einem Block on qen hal en sein muss. Diese Beobach ung is abe noch nich
hin eichend, es muss zusä zlich auch noch die Ano dnung de Blöcke in qbe ücksich ig
we den. Dies e klä auch die Wahl des Beg i s „Ve eine ung“ ü die in Gleichung (3.2)
de inie e Basisope a ion.
Die Pa i ionie ung eine Nebenklasse Sp
n=SPπwi d in diesen Algo i hmen s e s
übe eine sogenann e Indi idualisie ung e eich . Dazu wähl man einen Block pi∈p
mi |pi|>1und de inie das Resul a eines Pa i ionie ungssch i s übe die Menge
{(p0, . . . , pi−1,{p}, pi {p}, pi+1, . . . , p`−1)|p∈pi},
welche alle Möglichkei en da s ell einen Punk p∈pi on dem Block piabzu ennen.
De gewähl e Index i∈[`]muss, um die Bedingungen an eine Pa i ionie ung zu e -
üllen, wiede ü isomo phe Eingaben (Γ, Sp
n),(π0Γ, Sp
nπ−1
0)iden isch sein. Man wähl
zum Beispiel imme den kleins en (bzgl. Ka dinali ä ) nich i ialen Block pimi nied-
igs em Index i. In de Sp ache aus Gleichung (3.1) üh dies dann zu De ini ion de
Un e g uppe I(Γ, SPπ) := S abSP(min(Pi)) < SP.
Wi wollen noch e was nähe au die Ve eine ung eingehen. Im Rahmen de G a-
phenkanonisie ung wi d diese zum Beispiel übe das Zählen de Nachba n nach de
Kno en a be e eich , also du ch Anwendung de SP-Homomo phismen
NP: [2]([n]
2)→Z|P|n
E7→ |{j∈Pk| {i, j} ∈ E}|k∈[|P|]i∈[n]
.
Hie zeig sich, dass es un e Ums änden no wendig is , das Homomo phiep inzip
i e ie anzuwenden. Man be ach e dazu olgendes Beispiel:
55
3. Kanonisie ungsalgo i hmen
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.: I e ie e Ve eine ung
3.2.29 Beispiel. Es soll de olgende G aph Γ = 01234kanonisie
we den.
•Die Wu zel des Suchbaums T(Γ, S5)wi d übe die Ve eine ung V(Γ, S5)de inie
und diese wiede um mi els Homomo phiep inzip aus dem S5-Homomo phismus
N([5]). Das Bild N([5])(Γ) = ((1),(2),(2),(2),(1)) o dne jedem Kno en die Anzahl
seine Nachba n zu, siehe auch Abbildung 3.5 (links).
Die Kanonisie ung des Vek o s N([5])(Γ) = ((1),(2),(2),(2),(1)) un e de Ope a-
ion de symme ischen G uppe S5e olg nun du ch lexikog aphisches So ie en,
e wa übe die Pe mu a ion (1,4). Im Anschluss we den nu noch Pe mu a ionen
aus dem S abilisa o
S abS5N([5])((1,4)Γ)
| {z }
=((1),(1),(2),(2),(2))=S({0,1},{2,3,4})
au (1,4)Γ angewand . Wi e hal en somi als Wu zel des Back ackbaums T(Γ, S5)
die Nebenklasse V(Γ, S5) = S({0,1},{2,3,4})(1,4).
•An diese S elle wü de man nun mi de Pa i ionie ung on SP1(1,4) o ah en.
Man beobach e abe , siehe Abbildung 3.5 (Mi e), dass es du ch die o he gehende
Ve eine ung möglich is , im G aphen (1,4)Γ den Kno en 2 on 3und 4zu
sepa ie en. Dies e olg du ch eine e neu e Anwendung des Homomo phiep inzips
zum Homomo phismus N({0,1},{2,3,4}).
•E s du ch diesen Sch i e eich man eine Fä bung de Kno en bzw. eine Neben-
klasse SP2(1,2,4), welche un e Anwendung de Ve eine ung Vin a ian bleib .
56
3.2. Pa i ionen und Ve eine ungen
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
”=“
de inie Au omo phismus on Γ
¨
ube (1,2,4)−1(0,1,3,2,4) =
(0,4)(1,3)
Kanonische Rep ¨
asen an
on Γ
T anspo e -
elemen zu Γ
Ve eine ung
Abbildung 3.6.: Suchbaum zu Beispiel 3.2.29
In de G aphenkanonisie ung wi d eine solche Pa i ionie ung als balancie (engl.
„equi able“) bezeichne .
Abbildung 3.6 zeig nun den gesam en Suchbaum T(Γ, S5). Wi haben zu Ve deu li-
chung die Zwischensch i e de Ve eine ung eben alls no ie . Die ges ichel en Be eiche
zeigen U bild und Bild eine jeden (i e ie en) Ve eine ung. Nu die Bilde e en a -
sächliche im Suchbaum T(Γ, S5)als Kno en au .
3.2.30 Beme kung. Sollen be ei s ge ä b e G aphen als die zu kanonisie enden Objek e
un e such we den, so ans o mie man das P oblem zu Kanonisie ung eines gegebenen
G aphen Γ = ([n], E), welche übe eine geo dne e Pa i ion pge ä b is , au eine
Kanonisie ung on πΓun e SPmi Sp
n=SPπ. Dann e en im Back acking eben alls
nu kanonische Young-Un e g uppen au .
3.2.5. I e ie e Ve eine ung
Das Beispiel 3.2.29 deu e an, dass die a sächlich genu z e Ve eine ungs unk ion V
auch übe eine meh ache Anwendung eine wei e en Ve eine ung V:X×C(G)→ C(G)
gewonnen we den kann. Wi de inie en hie zu:
V0(x, Hg) := V(x, Hg)
und ü beliebiges n≥1
Vn(x, Hg) := V(x, Vn−1(x, Hg)).
57

3. Kanonisie ungsalgo i hmen
3.2.31 Hil ssa z. Es sei n≥1beliebig. Dann de inie die Funk ion Vneben alls eine
Ve eine ung. Auße dem exis ie eine na ü liche Zahl N≥1, so dass ü alle n0≥N
die Gleichhei Vn0=VNgil .
Beweis. Es seien g0∈G,x∈Xund Hg ∈ C(G)beliebig. Dann e gib sich die e s e
Aussage induk i aus de 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 de Ta sache, dass Vn(x, Hg) = V(x, Vn−1(x, Hg)) ⊆Vn−1(x, Hg)⊆Hg gil . Da
die Menge alle Rech snebenklassen endlich is , muss die abs eigende Ke e
V0(x, Hg)⊇V1(x, Hg)⊇. . .
on Rech snebenklassen ab eine na ü lichen Zahl N(x, Hg)s a ionä we den, d.h.
V0(x, Hg))V1(x, Hg)). . . )VN(x,Hg)(x, Hg) = VN(x,Hg)+1(x, Hg) = . . . .
Da auch de De ini ionsbe eich X× C(G)endlich is , e üll
N:= max
(x0,H0g0)∈X×C(G)N(x0, H0g0)∈N
die Aussage aus dem zwei en Punk .
3.2.32 Beme kung. Wi nennen dieses P inzip zu Gewinnung wei e e Ve eine ungen
dahe auch i e ie e Ve eine ung. De Beg i eine balancie en Pa i ion zu einem
ge ä b en G aphen aus de G aphenkanonisie ung besch eib also genau das E eichen
de Zahl N(x, Hg).
Fü die Ko ek hei des in Sa z 3.2.8 en wo enen Kanonisie ungsalgo i hmus is es
une heblich ob Vn(x, Hg) = Vn−1(x, Hg)gil , beziehungsweise ob die Ve eine ungen
noch zu ech en Un e g uppen ge üh haben. Wi gehen dahe zu Ve ein achung im
Folgenden on eine es gewähl en, eingabeunabhängigen Zahl ∈Naus und be ach en
die Ve eine ung V .
Wi nehmen wei e an, dass die u sp üngliche Ve eine ung Vübe die Anwendung
des Homomo phiep inzips aus eine Familie ( H)H∈L(G) on H-Homomo phismen H
gewonnen wu de, siehe Sa z 3.2.4. Das Ziel dieses Abschni es is es, nun zu beweisen,
dass sich auch V übe eine Familie ( H)H∈L(G)gewinnen läss . Dies is no wendig um
wei e hin die Bewe ungen B(x, Hg)au den Kno en Hg des Back ackbaums T(x, G)
de inie en zu können.
Wi wollen diese Aussage induk i beweisen. Dahe nehmen wi zunächs an, dass ü
alle Un e g uppen H on Gzwei H-Homomo phismen (0)
H:X→Yund (1)
H:X→Z
gegeben seien.
58
3.2. Pa i ionen und Ve eine ungen
3.2.33 Hil ssa z. Fü alle H∈ L(G)de inie die Funk ion
H:X→Y×Z
x7→  (0)
H(x),TRY
H (0)
H(x)−1· (1)
S abHCFY
H( (0)
H(x))TRY
H (0)
H(x)·x
einen H-Homomo phismus.
Beweis. Es seien h∈H∈ L(G)und x∈Xbeliebig. Zunächs beweis man leich übe
die Kanonisie ung on (0)
H(x)und (0)
H(hx), dass es ein h0∈H0:= S abHCFY
H( (0)
H(x))
gib mi
TRY
H (0)
H(hx)
| {z }
=:h1
h=h0TRY
H (0)
H(x)
| {z }
=:h0
.
Dami zeigen wi :
h−1· H(hx) = h−1· (0)
H(hx), h−1
1· (1)
H0(h1·hx)
= (0)
H(x), h−1h−1
1· (1)
H0(h1hx)= (0)
H(x), h−1
0h0−1· (1)
H0(h0h0x)
= (0)
H(x), h−1
0· (1)
H0(h0·x)= H(x)
Fü die Un e g uppen H∈ L(G)seien CanY
Hbzw. CanZ
HKanonisie e ü die Ope-
a ionen on Hau den Mengen Yund Z. Mi diesen gewinnen wi die Ve eine ungen
V(0) und V(1) gemäß Sa z 3.2.4.
Auße dem können wi nach Beispiel 3.1.5 einen Kanonisie e CanX×Y
H ü das di ek e
P oduk Y×Zde inie en, indem wi zunächs die e s e Komponen e au ih en kanoni-
schen Rep äsen an en ans o mie en und anschließend nu noch mi dem S abilisa o
au de zwei en Komponen en ope ie en. Es de inie also auch die Familie ( H)H∈L(G)
zusammen mi den Kanonisie e n CanX×Y
HH∈L(G)nach Sa z 3.2.4 eine Ve eine ung V.
Wi zeigen nun, dass diese als i e ie e Ve eine ung gesehen we den kann:
3.2.34 Hil ssa z. Fü alle (x, Hg)∈X× C(G)gil V(x, Hg) = V(1)x, V (0)(x, Hg).
Beweis. Wi zeigen ü ein beliebiges Paa (x, Hg)∈X× C(G), dass
V(1)x, V (0)(x, Hg)= S abHCFX×Y
H( H(gx))TRX×Y
H( H(gx))g
gil . Hie zu sei H0= S abHCFY
H (0)
H(gx)und h0:= TRY
H (0)
H(gx). Es is also
V(0)(x, Hg) = H0h0gund wi e hal en:
V(1)(x, H0h0g) = S abH0CFZ
H0 (1)
H0(h0gx)·TRZ
H0 (1)
H0(h0gx)·h0g
= S abHCFX×Y
H( H(gx))·TRX×Y
H( H(gx)) ·g=V(x, Hg)
59
3. Kanonisie ungsalgo i hmen
Nun sei Vdie aus  H,CanHH∈L(G)gewonnene Ve eine ung, welche wi i e ie
– wie zu Beginn des Abschni s angedeu e – anwenden wollen. Obige Hil ssa z e -
laub es uns nun induk i zu jede Ve eine ung Vi,i∈[ + 1] eine geeigne e Familie
( (i)
H)H∈L(G) on H-Homomo phismen (i)
Hund zugehö igen Kanonisie e n Can(i)
Hanzu-
geben. Zum Induk ionss a können wi o ensich lich
 (0)
H,Can(0)
HH∈L(G):=  H,CanHH∈L(G)
se zen. Aus de Induk ions o ausse zung olg , dass es zu de Ve eine ung Vi−1eine
Familie on H-Homomo phismen sam Kanonisie ung im Bildbe eich gib , welche Vi−1
de inie . Dami sind die Vo ausse zungen ü den Hil ssa z 3.2.34 e üll (mi V(1) =V
und V(0) =Vi−1) und wi schließen, dass sich Viebenso de inie en läss .
Diese Beweis zeig noch meh . Es is also möglich die Ve eine ung V ü das Back-
acking übe eine Folge beliebige Ve eine ungen (V0, . . . , V −1)zu de inie en. Wi
sch eiben aus diesem G und eine Folge on Ve eine ungen (V0, . . . , V −1)bzw. ü je-
des i∈[ ]eine Familie ( (i)
H)H∈L(G)sam Kanonisie e n im Bildbe eich zu Gewinnung
de i e a i en Ve eine ung V o .
3.2.35 Beme kung. Man kann sich auch übe legen, dass die Wahl de Ve eine ung
Vi, i ∈[ ]hie bei du chaus on den Resul a en de Ve eine ungen au den Vo ah en
abhängig gemach we den kann. Wi gehen hie au abe nich meh nähe ein.
Um im Folgenden leich e au die Eingaben und Ausgaben ü den i e ie en Au u
de Ve eine ungen zug ei en zu können, we den wi mi T(x, G)denjenigen Wu zelbaum
bezeichnen, de auch alle Zwischensch i e des Back acking übe eine i e ie e Ve ei-
ne ung wiede gib . Die Kno enmenge is hie bei übe eine Teilmenge on C(G)×[ + 1]
gegeben. Die zusä zliche Be ei s ellung des I e a ionszähle s ü die Kno enbesch i un-
gen e hinde , dass Schlei en in T(x, G)au e en. Den Wu zelbaum de inie en wi
wiede induk i :
•Die Wu zel on T(x, G)sei (G, 0).
•Is (Hg, i)ein Kno en in T(x, G)mi i< so de inie (Vi(x, Hg), i + 1) das
einzige Kind on (Hg, i).
•Fü einen Kno en (Hg, )mi |H|>1sei H0:= I(x, Hg)und {h0, . . . , hu−1}eine
Rech s ans e sale on H0in H. Die Kinde on (Hg, )we den dann on de
Menge {H0h0g, . . . , H0hu−1g}gebilde .
Die Bewe ungs unk ion e allgemeine n wi wie oben: Die Kno en de Ges al (Hg, 0)
mi Hg 6=Gwu den du ch eine Pa i ionie ung e zeug , sie übe nehmen dahe ih e Be-
we ung om Va e . Fü alle ande en Kno en (Hg, i),i≥1 e länge n wi den Bewe -
ungs ek o des Va e s (H0g, i −1) um den Ein ag CFH0( (i−1)
H0(gx)). Wi können somi
alle zu o bewiesenen Aussagen ü T(x, G)so o au T(x, G)übe agen, insbesonde e
Fak 3.2.2 und auch das Abschneiden on Teilbäumen übe bekann e Au omo phismen
und nich op imale Bewe ungen.
60
3.3. G uppen de Ges al GoϕSP0
3.3. G uppen de Ges al GoϕSP0
In diesem Abschni sei P0eine es gewähl e kanonische Pa i ion on [n]. Wi wollen
nun unse Vo gehen ü G uppenope a ionen de Ges al GoϕSP0mi einem G uppen-
homomo phismus ϕ:SP0→Au (G)au eine Menge Xnähe besch eiben. Da wi uns
ϕ es o geben, we den wi au die wei e e Angabe on ϕinne halb des semidi ek en
P oduk s zu Guns en de Übe sich lichkei e zich en.
Wie wi be ei s in Abschni 3.1.1 gesehen haben, können wi einen Kanonisie e
zu diese Ope a ion auch aus einem Kanonisie e CanSP0zu de Ope a ion on SP0
au G Xübe das Homomo phiep inzip gewinnen. Wi we den au diese En sp echung
spä e eingehen, zunächs besch eiben wi das Back acking abe übe den Suchbaum
T(x, G oSP0). Als Beispiel und Mo i a ion dien uns die G uppenope a ion on
((GLk(R)×(R∗)n)oAu (R)) oSn
au de Menge Rk×n,(m,...,m)alle Gene a o ma izen on eien Codes om Rang k.
3.3.1 Beme kung. Unse Vo gehen is maßgeblich du ch diese G uppenope a ion mo-
i ie . Im Allgemeinen haben wi mi diesem Ansa z zu De ini ion des Kanonisie e s
ü de a ige G uppenope a ionen, d.h. ü G uppenope a ionen, die sich auch als Ope-
a ion on Gau Sn Ynmi X=Ynbesch eiben lassen, bislang ausnahmslos posi i e
E ah ungen gemach . Gegebenen alls sind ü G uppenope a ionen aus ande sa igen
P oblems ellungen abe auch g und e schiedene Ansä ze zu Gewinnung eines e izien-
en Kanonisie e s nö ig.
Übe die Wahl de Ve eine ung und de Pa i ionie ung we den wi übe dies s eu-
e n, dass die zulässigen Kno en des Wu zelbaums T(x, G oSP0)bzw. die au e enden
Rech snebenklassen, au die Menge
C(GoSP0) := HoSP(g;π)|HoSP∈ L(GoSP0)und (g;π)∈GoSP0
zu Un e g uppen de Ges al
L(GoSP0) := {HoSP|H≤G, PP0:HoSP∈ L(GoSP0)}(3.6)
besch änk is . Demen sp echend besch änken wi auch De ini ions- und Bildbe eich de
Ve eine ungen bzw. Pa i ionie ungs o sch i be ei s im Vo eld au :
Vi:X× C(GoSP0)→ C(GoSP0), i ∈[ ]
und
I:X× C(GoSP0)→ L(GoSP0).
Im Folgenden wollen wi zu i∈[ ]mi  (i)
HoSPHoSP∈L(GoSP0)diejenige Familie on
HoSP-Homomo phismen bezeichnen, welche zu De ini ion de Ve eine ung Vi o ge-
sch ieben wu de.
61
3. Kanonisie ungsalgo i hmen
Beweis. Die Abbildungs o sch i is wohlde inie :
•Aus de Pa i ionie ung on P0 olg zunächs , dass es ü beliebiges x∈Gx
höchs ens einen Kno en ((HoSP), i)de Tie e in T(x, G oSP0)diese Ges al
geben kann. Alle wei e en Kno en diese Tie e sind Rech snebenklassen mi nich
i iale Pe mu a ionskomponen e.
•Exis ie ein wei e es Bahnenelemen g0x,g0∈G, mi diese Eigenscha , so is
(HoSP)g−1
0de eindeu ig bes imm e Kno en in T(g0x, GoSP0)de Tie e , de als
Rech snebenklasse mi i iale Pe mu a ion gesch ieben we den kann. In diesem
Fall is dann g0∈Hund CFH (im)
HoSP(x)= CFH (im)
HoSP(g0x).
Nun zu de SP-In a ianz de Abbildungs o sch i . Es genüg die Si ua ion zu be-
ach en, in welche zu Gx ∈G Xein solches G uppenelemen x∈Gx exis ie ( ü
den ande en Fall is die Aussage o ensich lich wah ). Is π∈SPbeliebig, so is wiede
((HoSP)π−1= (HoSP), i)ein Kno en in T(πx, G oSP0)de Tie e . Somi olg :
( )
P(πGx) = CFH (im)
HoSP(πx)= CFH (im)
HoSP(x)= ( )
P(Gx)
Analog beweis man ü Kno en au unge ade Tie e :
3.3.13 Hil ssa z. Is ≥0unge ade, 6≡ mod + 1 und PP0, so de inie
( )
P:G X→Zn∪ {()}
Gx 7→ 


(a)
HoSP(x),∃x∈Gx, HoSP∈ L(GoSP0)sd. (HoSP, i)
ein Kno en de Tie e in T(x, G oSP0)
(),sons
einen SP-Homomo phismus.
Beweis. Die Wohlde inie hei de Abbildungs o sch i zeig man, wie im o ausge-
gangenen Hil ssa z, indem man die H-In a ianz de Funk ion (a)
HoSPbenu z . Fü die
SP-Homomo phie genüg es wiede , diejenigen Gx ∈G Xzu un e suchen, ü welche
ein solches Bahnenelemen x∈Gx und eine Un e g uppe HoSP∈ L(GoSP0)exis ie .
Is π∈SPbeliebig, so olg :
( )
P(πGx) = ( )
P(πGx) = (a)
HoSP(πx) = π (a)
HoSP(x) = π ( )
P(Gx)
Induk i läss sich nun leich zeigen, dass man übe diese Familien on Homomo -
phismen genau den gewünsch en Suchbaum T(Gx, SP0)en wickel . Wi geben nu die
zen ale Idee ü den Beweis am Beispiel de Kno en au unge ade Tie e :
68

3.3. G uppen de Ges al GoϕSP0
Is (HoSP(g;π), i)ein Kno en in T(x, G oSP0)de Tie e und wi d ü diesen die
Ve eine ung V(a)ge u en, so is das E gebnis:
(HoSQ)(h;σ)(g;π) := V(a)(x, H oSP(g;π))
= S abHoSPCFHoSP( (a)((g;π)x))TRHoSP( (a)((g;π)x))(g;π)
Fü den isomo phen Kno en (SPπ, i)in T(Gx, SP0)e gib sich dann an diese S elle als
E gebnis de en sp echend de inie en Ve eine ung V :
V (Gx, SPπ) = S abSPCFSP( ( )
P(πGx))TRHoSP( ( )
P(πGx)
| {z }
= (a)((g;π)x)
)π=SQσπ
Wi geben nun noch abschließend einige Hinweise zu a sächliche Algo i hmenimple-
men ie ung:
•Zu jedem Kno en (SPπ, i)in T(Gx, SP0) e wal en wi im Hin e g und die injek-
i e Folge ede jenigen Koo dina en, ü welche die inne e Kanonisie ung be ei s
du chge üh wu de. Zu diese Folge eis ein e-semikanonische Rep äsen an x(π,e)
on Gπx und dessen S abilisa o H=G(e,πx)= S abGx(e,π)bes imm .
•Is ige ade, so bes immen wi zunächs := F(x(e,π), H oSP)und bewe en den
Kno en mi de SP-In a ian en Π (x(π, )) = CFHΠ (x(e,π))und se zen als Kind
(SPπ, i + 1).
•Is i < unge ade, so e eine n wi die Pa i ion Pübe die Kanonisie ung on
(a)
HoSP(x(e,π))un e Ausnu zung des Homomo phiep inzips. Is
(h;σ) := TRHoSP (a)
HoSP(x(e,π))
und
SP:= S abSPσ (a)
HoSP(x(e,π),
so e gib sich de neue e-semikanonische Rep äsen an x(e,σπ):= σx(e,π). Die G up-
pe Hmuss nich abgeände we den und wi se zen als Kind (SQσπ, i + 1).
Die Isomo phie de beiden Suchbäume gib uns nun auch einen Hinweis, wie wi das
Abschneiden on Teilbäumen in T(x, GoSP0)mi Hil e de bekann en Au omo phismen
on xdu ch üh en we den. Wi e wal en nu den Pe mu a ionsan eil, d.h. die G uppe
S abSP0(Gx), übe ein Labelled B anching mi Basis (0, . . . , n −1). Das Abschneiden
on Teilbäumen e olg wiede übe den Hil ssa z 3.2.26.
Un e de Annahme, dass ü alle x∈Xde S abilisa o S abG(x) = {1G} i ial is ,
können wi soga zeigen, dass dies zu keinem Ve lus on In o ma ionen üh :
69
3. Kanonisie ungsalgo i hmen
3.3.14 Hil ssa z. Es sei A≤GoϕSP0mi A:= {π|(g;π)∈A}und |A|=|A|. Is
TAeine Links ans e sale on SP0/A, so de inie TA:= {(g;π)|g∈G, π ∈TA}eine
Links ans e sale on (GoϕSP0)/A.
Beweis. Wi nehmen an, in de Menge TAseien (g0;π0),(g1;π1)Nebenklassen ep äsen-
an en zu de gleichen Linksnebenklassen on A. Es is also
(g0;π0)−1(g1;π1)=(ϕ(π−1
0)(g−1
0); π−1
0)(g1;π1)=(ϕ(π−1
0)(g−1
0g1); π−1
0π1)∈A
Hie aus schließen wi π−1
0π1∈Aund dami π0=π1. Au g und unse e Vo ausse zung
|A|=|A|implizie dies be ei s g0=g1. Die Volls ändigkei on TA olg so o aus
Anzahlg ünden.
3.3.15 Folge ung. Is A≤GoSP0wie oben, TAeine Links ans e sale und
(HoSP)(g;π)∈ C(GoSP0)beliebig, so gil :
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 Ke en inge
Wi we den nun zunächs noch wei e e Eigenscha en endliche Ke en inge besp echen,
welche wi bei de Fo mulie ung eines Kanonisie e s ü linea e Codes benö igen we den.
De e s e Abschni ass hie im Wesen lichen Resul a e aus [44] zusammen. Insbeson-
de e wi d auch au die S uk u de addi i en und mul iplika i en G uppe eingegangen.
Anschließend lei en wi eine S uk u aussage übe endliche Ke en inge he , welche sich
zum Beispiel auch in [59] inde . De nach olgende Abschni behandel dann die Au o-
mo phismeng uppe eines Ke en ings.
Es sei wei e Rs e s ein endliche Ke en ing de Ke enlänge mmi R/ Rad(R)≃Fq
und q=p ü eine P imzahl pund Exponen en . Auße dem bezeichne θ∈Reinen es
gewähl en E zeuge des Jacobson-Radikals Rad(R) = Rθ.
4.1. Wei e e G undlagen
4.1.1 De ini ion (Teichmülle -Menge).Eine Teilmenge T⊆Rnennen wi Teichmülle -
Menge on R, alls 0∈Tund T∗:= T {0}ein mul iplika i abgeschlossenes Ve e e -
sys em de Menge (R/ Rad(R))∗≃F∗
qis . Wi nennen T∗auch eine Teichmülle -G uppe.
4.1.2 Fak . De endliche Ke en ing Rbesi z mindes ens eine Teichmülle -Menge. Die
Teichmülle -G uppen sind ge ade die zyklischen Un e g uppen on R∗de O dnung q−1.
Teichmülle -Mengen gehen du ch Konjuga ion mi Einhei en auseinande he o . Is R
kommu a i , dann is also die Teichmülle -Menge Teindeu ig.
4.1.3 De ini ion (Schie polynom ing).Es sei Rein Ring und σ∈Au (R)ein Ringau-
omo phismus. Wi wollen mi R[X;σ]den Schie polynom ing übe Rzum Au omo -
phismus σbezeichnen. Diese Ring un e scheide sich on dem klassischen Polynom ing
R[X]nu in de De ini ion de Mul iplika ion Xa := σ(a)Xeines Ringelemen s a∈R
mi de Unbes imm en X.
Übe die Schie polynom inge können wi nich kommu a i e Ke en inge kons uie en,
siehe Fak 4.1.25.
4.1.4 Beispiel. Es sei τde F obenius-Au omo phismus on F4. De Ke en ing R=
F4[X;τ]/(X2)ha die olgenden Teichmülle -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 wei e en Ve lau diese A bei sei s e s Teine es gewähl e Teichmülle -Menge
on Rund ξein E zeuge de Teichmülle -G uppe T∗. Es gil wei e :
71
4. Endliche Ke en inge
4.1.5 Fak (θ-adische En wicklung).De Ke en ing Rbesi z qmElemen e und jedes
beliebige a∈Rläss sich eindeu ig in de Fo m a=Pm−1
i=0 aiθi, mi ai∈Tsch eiben.
Wi nennen eine solche Da s ellung die θ-adische En wicklung on abezüglich T. Das
Ideal Rad(R)k, k ∈[m+ 1] ha somi genau qm−kElemen e.
4.1.6 Beispiel. Die Teichmülle -Menge on Z9is {0,1,8}und θ= 3 is ein E zeuge
on Rad(Z9). Die 3-adische En wicklung on 2is 2=8·30+ 1 ·31. Neben dem Ring-
elemen θ= 3 können wi auch θ0= 6 als E zeuge des Jacobson-Radikals wählen. Die
6-adische En wicklung on 2is dann 2 = 8 ·60+ 8 ·61
4.1.7 De ini ion. Wi we den im Folgenden zu i∈[m]mi coe (i):R→T, a 7→ ai
diejenige Abbildung bezeichnen, welche das Ringelemen a∈Rau seinen eindeu igen
Koe izien en ai∈Tde θ-adischen En wicklung a=Pm−1
i=0 aiθiabbilde .
Den Ring Rkönnen wi (übe die addi i e G uppe) auch au na ü liche Weise als
Z-Modul in e p e ie en, indem wi ü z∈Zund a∈Rdie Skala mul iplika ion übe
z·a:= 


a+. . . +a
| {z }
z−mal
, alls z≥0
(−z)·(−a), alls z < 0
de inie en. Wi iden i izie en dann die ganze Zahl zauch mi z·1R∈R. Die g öß e Zahl
ε∈Nmi p·1R∈Rad(R)εnennen wi den Ve zweigungsindex zu R. Es is s e s ε≥1,
da die Gleichung p·1R=p·1Fq= 0Fqbe ei s p∈Rad(R)implizie .
Wi nu zen nun diese Beobach ung aus, um die θ-adische En wicklung eines Ringele-
men s wei e zu e eine n. Diese e eine e Besch eibung gib uns dann die Möglichkei ,
bequem eine To alo dnung au Rzu de inie en.
4.1.8 Hil ssa z ((ξ, θ)-adische En wicklung).Is ξein E zeuge de Teichmülle -G uppe
T∗ on R, so gib es zu jedem a∈Reine eindeu ige Da s ellung de Ges al
a=
−1
X
i=0
m−1
X
j=0
aijξ −1−iθj= (ξ −1, . . . , ξ0)


a0,0. . . a0,m−1
.
.
.....
.
.
a −1,0. . . a −1,m−1



| {z }
=:coe (a)



θ0
.
.
.
θm−1


mi coe (a)∈[p] ×m. Wi nennen sie die (ξ, θ)-adische En wicklung on a.
Beweis. Besi z jedes Ringelemen eine (ξ, θ)-adische En wicklung, so olg die Eindeu-
igkei so o aus Anzahlg ünden. Wi beweisen die Exis enz eine (ξ, θ)-adischen En -
wicklung nun induk i ü die Ringelemen e a∈Rad(R)k ü alle k∈[m+ 1]. Fü das
Nullelemen – gleichzei ig de Induk ionss a Rad(R)m={0R}– gib es o ensich lich
eine solche Da s ellung.
72
4.1. Wei e e G undlagen
Es sei nun k∈[m]und die Behaup ung ü alle Ringelemen e aus dem Ideal Rad(R)k+1
be ei s bewiesen. Wi wählen a∈Rad(R)k Rad(R)k+1 beliebig. Da Tein Ve e e -
sys em on R/ Rad(R)≃Fqbilde , können wi coe (k)
(a)eindeu ig übe die Linea -
kombina ion P −1
i=0 aikξ −1−i, aik ∈[p]de Fp-Basis (1, ξ, . . . , ξ −1) on Fqda s ellen. Es
exis ie also ein Elemen b∈Rad(R)mi coe (k)
(a)−P −1
i=0 aikξ −1−i=bund es olg
a0:= a−
−1
X
i=0
aikξ −1−iθk=bθk+
m−1
X
j=k+1
coe (j)
(a)θj∈Rad(R)k+1.
Fü das Ringelemen a0∈Rad(R)k+1 exis ie nach de Induk ions o ausse zung abe
eine (ξ, θ)-adische En wicklung a0=P −1
i=0 Pm−1
j=k+1 aijξ −1−iθj. Es is also
a=
−1
X
i=0
m−1
X
j=k
aijξ −1−iθj
die gesuch e (ξ, θ)-adische En wicklung on a.
4.1.9 De ini ion. Wi we den im Folgenden zu i∈[ ]und j∈[m]mi
coe (i,j):R→[p], a 7→ aij = coe (a)i,j
diejenige Abbildung bezeichnen, welche das Ringelemen a∈Rau seinen eindeu i-
gen Koe izien en aij ∈[p]de (ξ, θ)-adischen En wicklung a=P −1
i=0 Pm−1
j=0 aijξ −1−iθj
abbilde .
Häu ig we den wi die Ma ix coe (a)∈[p] ×mde (ξ, θ)-adischen En wicklung on
a∈Rauch übe dem Kö pe Fpau assen. S a coe (a)sch eiben wi dann auch
coe (a). Gleiches gil ü die Koe izien en de θ-adischen En wicklung coe (i)
(a)bezüg-
lich dem Kö pe Fq.
4.1.10 Beme kung. Bei de De ini ion eine To alo dnung au Rwi d sich die zunächs
kon ain ui i e Zuo dnung des Koe izien en aij zu ξ −1−iθjals o eilha e weisen.
4.1.11 Beispiel. Es is R=F4[X]/(X2)ein Ke en ing de Ke enlänge m= 2 mi
Teichmülle -Menge T:= {0,1, ξ, ξ2}=F4und θ:= X. Das Ringelemen 1 + ξ2X∈R
ha die (ξ, X)-adische En wicklung 1 + ξ2X= 0 ·ξ1X0+ 1 ·ξ0X0+ 1 ·ξ1X1+ 1 ·ξ0X1.
4.1.12 Folge ung. Fü beliebiges a∈Rund j≤min{h (a), m −1}is
coe (j)
(a) =
−1
X
i=0
coe (i,j)
(a)ξ −1−i.
Beweis. Folg so o aus dem Beweis zu Exis enz de (ξ, θ)-adischen En wicklung on
a∈R.
73

4. Endliche Ke en inge
4.1.13 Beme kung. Die Teichmülle -Menge Tis im Allgemeinen nich addi i abge-
schlossen. Es is somi ü beliebiges a∈Rund j∈[m]mi j > h (a)im Allgemeinen
coe (j)
(a)6=
−1
X
i=0
coe (i,j)
(a)ξ −1−i.
Eine ähnliche Aussage gil ü Summen on Ringelemen en:
4.1.14 Hil ssa z. Es seien a, b ∈Rbeliebig und j∈[m] : j≤max{h (a),h (b)}. Dann
gil :
coe (j)
(a+b) = coe (j)
(a) + coe (j)
(b)
und
coe (i,j)
(a+b) = coe (i,j)
(a) + coe (i,j)
(b),∀i∈[ ]
Beweis. Folg so o aus den θ-adischen bzw. (ξ, θ)-adischen En wicklungen on a, b und
a+b.
Wi nu zen nun die Bijek ion on Rnach [p] ×mum ausgehend on eine To alo d-
nung au [p] ×meine To alo dnung au Rzu de inie en. Hie zu lesen wi die Ma izen
spal enweise und e gleichen die esul ie enden Vek o en lexikog aphisch:
4.1.15 De ini ion (To alo dnung au R).Fü alle a, b ∈Rsei
a≤b:⇐⇒ coe (a)≤coe (b)
4.1.16 Beispiel. Die To alo dnung au dem Ke en ing R:= F4[X]/(X2)bes imm
sich wie in Tabelle 4.1 angegeben übe die le z e Tabellenspal e.
Die Abbildungen coe (i,j)e lauben es uns nich nu , eine To alo dnung au Rzu
de inie en, sonde n auch die S uk u de G uppen (R, +) und (R∗,·)genaue zu un e -
suchen. Hie zu de inie en wi zunächs zu i∈[ + 1] und j∈[m]die Mengen
R(i,j):= na∈Rad(R)j| ∀ 0≤ν < i : coe (ν,j)
(a) = 0o
=( −1
X
ν=i
aν,jξ −1−νθj|aν,j ∈[p],∀i≤ν≤ −1)+ Rad(R)j+1.
4.1.17 Folge ung. Fü beliebiges i∈[ ]und j∈[m]gil :
•∀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)|=p (m−j)−i
•∀a∈R(i+1,j),∀b∈R(i,j) R(i+1,j):a < ξ −1−iθj≤b
74
4.1. Wei e e G undlagen
X-adische En wicklung on a∈R(ξ, X)-adische En wicklung on acoe (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.: To alo dnung au F4[X]/(X2)
Beweis. Anschaulich bedeu e de Übe gang on R(i+1,j)nach R(i,j)die F eihei einen
wei e en Ein ag de Ma ix coe (a)beliebig zu belegen. Dabei wi d analog zu De ini-
ion de To alo dnung au R o gegangen. An den Übe gängen R(0,j+1) zu R( ,j)nu z
man die Gleichhei de Mengen R(0,j+1) = Rad(R)j+1 =R( ,j).
4.1.18 Hil ssa z. Fü jedes i∈[ ]und j∈[m]is die Teilmenge R(i,j)eine Un e g uppe
de abelschen G uppe (R, +) und
R=R(0,0) B. . . BR( ,0) =R(0,1) B. . . BR( ,m−1) ={0R}
is eine Komposi ions eihe on (R, +), bei welche jede Fak o R(i,j)/R(i+1,j), i ∈[ ]
isomo ph zu Zpis .
Beweis. Wi zeigen die Behaup ung ü ein es gewähl es j∈[m]übe eine Induk ion
nach i∈[ ]. O ensich lich sind die Mengen R(0,j)= Rad(R)jUn e g uppen und wegen
de Kommu a i i ä auch No mal eile . Die Abbildung
coe (i,j):R(i,j)→Zp, a 7→ coe (i,j)
(a)
de inie einen Epimo phismus, dessen Ke n gleich R(i+1,j)is .
Au gleiche Weise gewinnen wi eine No mal eihe on (R∗,·)mi zyklischen Fak o en.
Im wei e en Ve lau diese A bei we den wi die zu den Fak o g uppen isomo phen
G uppen jeweils übe dem No mal eile zeichen no ie en:
4.1.19 Hil ssa z. Fü i∈[ + 1] und j∈[m] : j≥1sei R∗(i,j):= 1 + R(i,j). Dann
bilden die Mengen R∗(i,j)Un e g uppen on (R∗,·)und
R∗F∗
q
D1 + Rad(R) = R∗(0,1) Zp
B. . . Zp
BR∗( ,1) =R∗(0,2) Zp
B. . . Zp
BR∗( ,m−1) ={1R}
is eine No mal eihe on R∗mi zyklischen Fak o en.
75
4. Endliche Ke en inge
Beweis. Zunächs zeigen wi , dass ü jedes i∈[ ]und j∈[m]die Mengen R∗(i,j)
mul iplika i abgeschlossen sind. Dazu wählen wi a, b ∈R(i,j)beliebig. Es gil :
(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)
De e s e No mal eile 1 + Rad(R)CR∗de Ke e e gib sich so o aus dem G up-
penepimo phismus ¯: R∗→F∗
q, a 7→ a. Die No mal eile eigenscha de Un e g uppen
R∗(i+1,j)in R∗(i,j)mi i∈[ ]und j∈[m] : j≥1e häl man aus dem Epimo phismus
coe (i,j):R∗(i,j)→Zp, dessen Ke n gleich R∗(i+1,j)is .
Ke en inge Rmi Ve zweigungsindex ε= 1 nennen wi Galois-Ringe. Das Jacobson-
Radikal Rad(R) = pR wi d also on eine P imzahl pe zeug . Wi e einba en, ü
Galois-Ringe s e s den E zeuge θ=pzu wählen.
4.1.20 Fak ([59, Theo em 4.2]).Galois-Ringe sind s e s kommu a i . Zu eine belie-
bigen P imzahl pund na ü lichen Zahlen m, > 0exis ie ein bis au Isomo phie ein-
deu ige Galois-Ring GR(pm, )de Cha ak e is ik pmund Ka dinali ä p m. Zu Kon-
s uk ion des Galois-Ring GR(pm, ) = Zpm[X]/( )wähl man ein no mie es Polynom1
∈Zpm[X] om G ad , dessen Bild modulo pin Zp[X]i eduzibel is .
4.1.21 Beispiel. De endliche Kö pe Fp is isomo ph zum Galois-Ring GR(p, ). De
Ke en ing Zpmis isomo ph zu dem Galois-Ring GR(pm,1).
Die Galois-Ringe sind nich nu wegen ih e Eindeu igkei und Kons uk ion den end-
lichen Kö pe n seh e wand :
4.1.22 Fak ([59, Theo em 4.5]).Die Au omo phismeng uppe Au (GR(pm, )) eines
Galois-Rings is zyklisch und on de O dnung . Sie wi d on dem F obenius-Au o-
mo phismus τ∈Au (GR(pm, )) e zeug , de die Elemen e a∈GR(pm, )in p-adische
En wicklung a=Pm−1
i=0 aipiau τ(a) := Pm−1
i=0 ap
ipiabbilde .
4.1.23 Beme kung. Da die Abbildung ϕ: Au (GR(pm, )) →Au (Fp )mi σ(a) :=
ϕ(σ)(a) := σ(a) ü alle σ∈Au (GR(pm, )) und a∈Reinen kanonischen Isomo phis-
mus zwischen beiden Au omo phismeng uppen de inie , we den wi im Folgenden auch
den F obenius-Au omo phismus des Kö pe s Fp mi dem gleichen Symbol τbezeichnen.
1In [73, Tabelle 1.1] gib J. Zwanzge eine Lis e solche Polynome. Sie bilden übe dies eine Ve all-
gemeine ung de sogenann en Conway-Polynome übe endlichen Kö pe n, e gleiche [64]. Sie sind
eben alls ü gegebenes qund meindeu ig bes imm und können somi zu s anda disie en Da s el-
lung de Elemen e eines Galois-Rings he angezogen we den. Übe dies gewäh leis en sie eine gewisse
Kompa ibili ä in de Da s ellung des Galois-Rings und seinen Galois-Un e ingen.
76
4.1. Wei e e G undlagen
Es sei pmSdie Cha ak e is ik des endlichen Ke en ings R. Nach [12, 59] besi z R
einen bis au Isomo phie eindeu ig bes imm en Galois-Un e ing S≃GR(pmS, )⊆
Rmi S=R=Fp . Man nenn den Ring Sauch einen Koe izien en ing zu R, da
man als eine Teichmülle -Menge on Rauch die Teichmülle -Menge T on Swählen
kann2. Dami zeig man abe auch leich übe Konjuga ion, dass das Ringe zeugnis
eine jeden Teichmülle -Menge T on Reinen solchen Un e ing S≃GR(pmS, ) on
Re gib . Es liegen also ohne Besch änkung de Allgemeinhei alle Koe izien en de
θ-adischen En wicklung eines Elemen s a∈Rin dem Galois-Un e ing S. Is εde
Ve zweigungsindex zu R, so gil somi ü eine beliebige Teichmülle -Menge T on R
und a, b, c ∈T:
a+b=c⇐⇒ a+b−c∈Rad(R)∩S=Sp ⊆Rp = Rad(R)ε
Wi benö igen noch einige wei e e Eigenscha de endlichen Ke en inge, be o wi zu
de Kanonisie ung de linea en Codes übe gehen können. Die nach olgende Diskussion
olg dem Übe sich sa ikel [59]. Die Beweise ü unse e Aussagen inden sich in [58].
Unse e Aus üh ungen we den bis zu de Ta sache o d ingen, dass sich jede endliche
Ke en ing als Quo ien eines Schie polynom ings übe einem beliebigen Koe izien en-
ing da s ellen läss .
4.1.24 Fak ([59, P oposi ion 5.17]).Es sei Rein endliche Ke en ing und S≃
GR(pmS, )ein Koe izien en ing on R. Dann gib es einen E zeuge θ on Rad(R)
und einen ausgezeichne en Au omo phismus τe∈Au (S), so dass die Ringelemen e
a∈Sübe die Vo sch i θa =τe(a)θmi θ e auschen.
Wi e einba en also wei e , dass zu dem gegebenen Ke en ing Rmi Koe izien en-
ing Sde E zeuge θund de Ringau omo phismus τe∈Au (S)du ch Fak 4.1.24
bes imm sind. Dann läss sich auch übe die θ-adische En wicklung eines Ringelemen s
a=Pm−1
i=0 aiθimi ai∈T⊆Sdie Mul iplika ion on ami θ on links leich besch ei-
ben:
θa =θ·
m−1
X
i=0
aiθi= m−1
X
i=0
τe(ai)θi!·θ
Wi schließen mi eine Cha ak e isie ung de endliche Ke en inge ohne die au e-
enden Beg i e exak zu de inie en:
4.1.25 Fak ([59, Theo em 5.18]).Zu jedem endlichen Ke en ing Rmi Koe izien en-
ing Sexis ie ein spezielles Eisens einpolynom ∈S[X;τe]übe dem Schie polynom-
ing S[X;τe], so dass R≃S[X;τe]/ , pmS−1XmR−(mS−1).
Wei e gehende In o ma ionen inde man in [59], insbesonde e auch zu de De ini ion
eines spezielles Eisens einpolynoms und den wei e en Einsch änkungen, die man zum
Beispiel an den G ad on machen muss. Eine Klassi ika ion de endlichen Ke en inge
bis au Isomo phie is imme noch o en.
2Dies is so o e sich lich, da die Teichmülle -G uppen genau die mul iplika i abgeschlossene Teil-
mengen on Rbzw. Smi q−1Elemen en sind.
77
4. Endliche Ke en inge
4.2.12 Hil ssa z. Es sei χθ+aθi
ξ∈Inn(i)
ξein inne e Au omo phismus ü ein a∈R∗
und i≥2. Dann gib es eine Einhei b∈Z(i−1)(ξ), welche χθ+aθi
ξinduzie .
Beweis. Da χθ+aθi
ξein inne e Au omo phismus is , wissen wi , dass ein c∈Z(ξ)exis ie
mi cθc−1=θ+aθi. Wi nehmen zunächs an, dass c=c0+c1θ ü ein c0∈T∗, c06= 1
und c1∈Rsei. Dann gil :
θ≡(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 abe c0, τe(c−1
0)und auch c0τe(c−1
0)in de Teichmülle -Menge liegen, olg wei e
c0τe(c−1
0) = 1 ⇐⇒ c0=τe(c0)⇐⇒ c0θ=θc0.
Das Ringelemen c0∈Tkommu ie also mi allen Ringelemen en und es de inie dahe
c−1
0c= 1 + c−1
0c1θ∈1 + Rad(R)den gleichen inne en Au omo phismus χθ+aθi
ξ.
Wi haben hie mi gezeig , dass de inne e Au omo phismus χθ+aθi
ξbe ei s on einem
Ringelemen c∈1 + Rad(R)e zeug wi d. Wi nehmen dies als Induk ionss a und
zeigen ü 2≤j≤i−1, dass aus de Exis enz eines Elemen s c∈Z(j−1)(ξ)mi
θ+aθi=cθc−1auch die Exis enz eines Elemen s c0∈Z(j)(ξ)mi θ+aθi=c0θc0−1 olg :
Lieg cbe ei s in Z(j)(ξ), so is nich s zu zeigen. Es sei also c= 1 + c0θj−1+c1θjmi
c0∈T∗und c1∈R. Aus Hil ssa z 4.2.10 schließen wi auße dem, dass
ggT( ,e)ein Teile
on (j−1) is . Dann olg 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
be ei s
(c0−τe(c0)) ∈Rad(R)⇐⇒ c0=τe(c0)⇐⇒ c0θ=θc0.
Hie du ch e gib sich, dass das Ringelemen (1 −c0θj−1)sowohl mi ξals auch mi θ
kommu ie und also de on (1 −c0θj−1)e zeug e inne e Au omo phismus i ial is .
Somi is de on c0:= (1 −c0θj−1)c∈1 + Rad(R)je zeug e inne e Au omo phismus
eben alls gleich χθ+aθi
ξ.
4.2.13 Folge ung. Es sei i∈[m],i≥2mi
ggT( ,e)-(i−1), dann is Inn(i)
ξ= Inn(i+1)
ξ,
d.h. es gib in de Menge Au (0,i)
ξ Au (0,i+1)
ξkeine inne en Au omo phismen.
Beweis. Jede Einhei b∈Z(i−1)(ξ) = Z(i)(ξ)induzie einen Au omo phismus χbθb−1
ξ∈
Inn(i+1)
ξ.
84

4.2. Au omo phismen
4.2.14 Folge ung. Es sei i∈[m],i≥2mi
ggT( ,e)|(i−1). Dann is
ncoe (i)
(α(θ)) |α∈Inn(i)
ξo={a−τe(a)|a∈Fq}
Beweis. Fü einen Ringau omo phismus α∈Inn(i+1)
ξis coe (i)
(α(θ)) = 0 = 1 −τe(1).
Wi müssen also nu die Ringau omo phismen α∈Inn(i)
ξ Inn(i+1)
ξbe ach en. Ein sol-
che we de on dem Ringelemen 1 + θi−1+b0θi+1 mi ∈T∗und b0∈Rinduzie . Es
olg :
θ+ coe (i)
(α(θ))θi≡(1 + θi−1)θ(1 − θi−1)≡θ+ ( −τe( ))θimod Rad(R)i+1
Dami haben wi die Inklusions ich ung „⊆“ bewiesen. Umgekeh sieh man leich ,
dass ü ∈T∗die Einhei 1 + θi−1∈Z(ξ)einen inne en Au omo phismus α∈Inn(i)
ξ
induzie mi coe (i)
(α(θ)) = −τe( ).
Es sei wiede Fps≤Fqde Fixkö pe on τe, also s= ggT( , e). Die Abbildung
Fq→Fq, x 7→ x−τe(x)is dann Fps-linea . Die Menge T1:= {a−τe(a)|a∈Fq}aus
dem o angegangenem Hil ssa z is somi ein Fp-Un e aum de Dimension −s. Die
o ausgegangenen E gebnisse übe die G uppen Z(ξ),Z(R)und Innξ assen wi nun in
dem olgenden Sa z zusammen:
4.2.15 Sa z. Es sei x:=
ggT( ,e)und l:= m−1
x. Dann sind
Z(ξ)
F∗
q
DZ(x)(ξ)
F
p
DZ(2x)(ξ)
F
p
D. . .
F
p
DZ(lx)(ξ)
F
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)
ξ
F −s
p
DInn(2x+1)
ξ
F −s
p
D. . .
F −s
p
DInn(lx+1)
ξ
F −s
p
DInn((l+1)x+1)
ξ={idR}
die No mal eihen on Z(ξ),Z(R)und Innξ. Is (l+ 1)x=m−1⇐⇒ x|(m−1), so
is Z((l+1)x)(R) = Z((l+1)x)(ξ)≃F
p. Ande n alls sind beide G uppen i ial.
4.2.16 Beme kung. Das hie e ziel e E gebnis zu Z(R)deck sich mi dem Resul a
on A. Nechae übe das Zen um [59, Theo em 5.18 (d)] des Rings R.
Wi schließen das Kapi el mi eine Besch eibung de G uppe Ou (R)übe eine No -
mal eihe. Hie zu seien ü i∈[ + 1] und j∈[m], j ≥2die G uppen
Inn(i,j)
ξ:= Au (i,j)
ξ∩Inn(R)und Ou (i,j)
ξ:= Au (i,j)
ξ/Inn(i,j)
ξ.
Aus dem e s en Isomo phiesa z ü G uppen e gib sich wiede die Isomo phie
Ou (i,j)
ξ≃Au (i,j)
ξ◦Inn(R)/Inn(R)
85
4. Endliche Ke en inge
und dami auch, dass wi Ou (i+1,j)
ξals No mal eile in Ou (i,j)
ξau assen können. Wei e
is genau dann Ou (i+1,j)
ξ= Ou (i,j)
ξ, wenn Au (i+1,j)
ξ= Au (i,j)
ξode Inn(i+1,j)
ξ6= Inn(i,j)
ξ
gil . Ande n alls is die Fak o g uppe Ou (i,j)
ξ/Ou (i+1,j)
ξisomo ph zu Zp. Zusammen as-
send e gib sich de olgende Sa z:
4.2.17 Sa z. Es sei x:=
ggT( ,e)und
I:= ni∈[ ]| ∃ ∈Tsd. ∀i0< i : coe (i0,0)
( −τe( )) = 0 ∧coe (i,0)
( −τe( )) 6= 0o.
Dann is
Ou (R)DOu ξDOu (0,2)
ξD. . . DOu ( ,2)
ξ= Ou (0,3)
ξD. . . DOu ( ,m−1)
ξ(4.2)
eine No mal eihe mi zyklischen Fak o en. Dabei is
•Ou T/Ou ξ≃Z 0mi 0| aus Hil ssa z 4.2.6 und
•Ou ξ/Ou (0,2)
ξ≃Zs0mi s0|(pggT( ,e)−1).
Fü i∈[ ]und j∈[m] : j≥2gil wei e
•Ou (i,j)
ξ/Ou (i+1,j)
ξ≃Zp, alls Au (i,j)
ξ6= Au (i+1,j)
ξund x-(j−1) ∨i6∈ Iund
•Ou (i,j)
ξ= Ou (i+1,j)
ξin allen ande en Fällen.
Beweis. Mi Ausnahme on Ou ξ/Ou (0,2)
ξ≃Zs0mi s0|(pggT( ,e)−1) wu den alle
Aussagen be ei s wei e oben behandel . Die e bliebene Aussage läss sich abe mi dem
Homomo phismus Ψ : Au ξ→F∗
q,α7→ coe (1)
(α(θ)) und de Beobach ung Ψ(Innξ) =
ξ1−pe=DξpggT( ,e)−1Eso o olge n.
Die no wendigen Modi ika ionen an Algo i hmus A.1 zu Be echnung eines E zeugen-
densys ems on Ou (R)geben wi in Beme kung A.5 im Anhang A.
86
5. Linea e Codes übe endlichen
Ke en ingen
Wi we den nun im Folgenden linea e Codes de Länge nübe einem Ke en ing Rmi
es o gegebenen Um iss λ= (λ0, . . . , λk−1)un e suchen. Ziel dieses Kapi els is es,
einen Kanonisie e ü die Ope a ion de G uppe de semilinea en Isome ien on Rn
au diese Menge zu en wickeln.
Da wi einen linea en Code Cin diesem Algo i hmus übe eine Gene a o ma ix da -
s ellen möch en, we den wi zunächs die Menge alle Gene a o ma izen on Cübe
eine G uppenope a ion besch eiben. Wie wi be ei s in Beispiel 2.3.18 gesehen haben,
üh – bei nich eien Codes – die Mul iplika ion eine Gene a o ma ix Γ on Cmi
eine in e ie ba en Ma ix A∈GLk(R)nich no wendige weise zu eine wei e en Ge-
ne a o ma ix on C. Wi wollen dahe zunächs die G uppe GLk(R)de a au eine
Un e g uppe GLλ(R)einsch änken, dass wi die Menge alle Gene a o ma izen on C
wiede übe die Bahnenmenge GLλ(R)Γ e hal en. Einen eindeu igen Rep äsen an en
diese Bahn e hal en wi übe eine Ve allgemeine ung de eduzie en Zeilens u en o m.
In einem wei e en Sch i ans o mie en wi dann die P oblems ellung au eine Ope-
a ion de G uppe ((GLλ(R)×(R∗)n)oAu T)oSnau de Menge Rk×n,λ alle Ge-
ne a o ma izen zum Um iss λ. Diese Ope a ion können wi mi den Algo i hmen aus
Kapi el 3 behandeln. Eine en scheidende Rolle wi d hie bei de Ope a ion de Un e -
g uppe ((GLλ(R)×(R∗)n)oAu T)zukommen. Fü diese we den wi in dem Abschni
5.1.2 einen e izien en Kanonisie e be ei s ellen.
De zwei e Abschni 5.2 besch eib dann schlussendlich den gewünsch en Kanoni-
sie e ü die Ope a ion on ((GLλ(R)×(R∗)n)oAu T)oSnau de Menge Rk×n,λ.
Diesen we den wi du ch Be ei s ellung eine inne en Kanonisie ung und eine äuße en
Ve eine ung übe den in Abschni 3.3 besch iebenen Basisalgo i hmus gewinnen.
5.1. Gene a o ma izen
Wi wollen nun, wie be ei s angedeu e , zunächs die Un e g uppe GLλ(R)de inie en
und die Ope a ion diese G uppe au de Menge Rk×n,λ un e suchen.
5.1.1 De ini ion. Zu einem Um iss λ= (λ0, . . . , λk−1)und i∈[m]sei
kλ
i:= |{j∈[k]|λj=m−i}|
87
5. Linea e Codes übe endlichen Ke en ingen
und GLλ(R)die Menge alle Blockma izen de Ges al A(i,j)i,j∈[m]∈Rk×kmi
A(i,j)∈




Rkλ
i×kλ
j, alls 0≤i<j≤m−1
GLkλ
i(R), alls 0≤i=j≤m−1
θi−jRkλ
i×kλ
j, alls 0≤j < i ≤m−1.
5.1.2 Fak ([73, Lemma 2.21]).Die Menge GLλ(R)bilde eine Un e g uppe on GLk(R).
5.1.3 Beme kung. Nach [73, Lemma 2.20] is eine Blockma ix A(i,j)i,j∈[m]mi
A(i,j)∈(Rkλ
i×kλ
j, alls 0≤i≤j≤m−1
Rad(R)kλ
i×kλ
j, alls 0≤j < i ≤m−1
genau dann in e ie ba , wenn alle A(i,i)in e ie ba sind.
5.1.4 Fak ([73, Sa z 2.22]).Is Γ∈Rk×n,λ eine Gene a o ma ix zu einem Code C om
Um iss λ, so is die Menge alle Gene a o ma izen on Cgleich de Bahn GLλ(R)Γ.
Fü nich eie Codes üh diese G uppe abe zu eine nich euen G uppenope a ion:
5.1.5 Fak ([73, Lemma 2.23]).Fü eine beliebige Gene a o ma ix Γ∈Rk×n,λ is
S abGLλ(R)(Γ) = Nλ(R) := Ik+ 0θλ0, . . . , k−1θλk−1| i∈(Rk)R.
Insbesonde e is ü λ6= (m, . . . , m)– d.h. ü nich eie Codes – die G uppenope a-
ion on GLλ(R)au Rk×n,λ nich eu. Die Un e g uppe Nλ(R)is als Schni alle
S abilisa o en ein No mal eile on GLλ(R).
5.1.6 Beme kung. Im Folgenden we den wi die Ope a ion de G uppe GLλ(R)au
Rk×n,λ du ch die na ü liche Ope a ion de Fak o g uppe GLλ(R)/Nλ(R)e se zen.
Aus G ünden de Übe sich lichkei we den wi abe keine Un e scheidung zwischen
den G uppenelemen en A∈GLλ(R)und ANλ(R)∈GLλ(R)/Nλ(R)machen. Aussagen,
wie zum Beispiel „ANλ(R)is on obe e D eiecksges al “, beziehen sich dann au die
Exis enz eines Nebenklassen e e e s A∈GLλ(R)mi diese Eigenscha .
5.1.7 Folge ung. Zwei Gene a o ma izen Γ,Γ0∈Rk×n,λ e zeugen genau dann semili-
nea isome ische Codes, wenn es ein G uppenelemen
(ANλ(R), ϕ;α, π)∈(GLλ(R)/Nλ(R)×(R∗)n)o(Au (R)×Sn)
gib mi (ANλ(R), ϕ;α, π)Γ = (A, ϕ;α, π)Γ = Γ0.
88
5.1. Gene a o ma izen
Übe einem endlichen Kö pe Fqkönnen wi jedem linea en Code Ceine eindeu ige
Gene a o ma ix zuo dnen, indem wi diejenige Gene a o ma ix Γ∈Fk×n
qauszeichnen,
welche in eduzie e Zeilens u en o m o lieg . Sie is bekann e maßen eindeu ig in de
Bahn GLk(Fq)Γ und bilde somi einen kanonischen Rep äsen an en ü diese Ope a ion.
Wi wollen nun zeigen, dass dies im Fall eines linea en Codes übe einem endlichen Ke -
en ing genauso möglich is . Wi e allgemeine n zunächs die De ini ion de eduzie en
Zeilens u en o m eine Ma ix:
5.1.8 De ini ion ( eduzie e Zeilens u en o m).Wi sagen eine Ma ix Γ∈Rk×nis in
Zeilens u en o m, alls es eine Folge on Spal enindizes 0≤j0< . . . < jk0−1≤n−1mi
k0≤kgib , so dass
• ü alle i∈[k0]die Ein äge Γi,jiPi o elemen e sind, d.h. Γi,ji6= 0 und ü alle
i∈[k0]und j∈[ji]is Γi0,j = 0, und
•alle wei e en Zeilen Γi,∗ ü k0≤i<kNullzeilen sind.
Die Spal en Γjinennen wi auch Pi o spal en. Die Zeilens u en o m is eduzie , alls
sie übe dies die olgenden Eigenscha en e üll :
• ü alle i∈[k0]is das Pi o elemen Γi,ji=θm−λimi λi:= pe (Γi,∗),
•die Folge (λ0, . . . , λk0−1)is mono on allend und
•alle wei e en Ein äge de Spal e Γ∗,jisind modulo dem Pi o elemen eduzie ,
d.h. Γ`,ji= mina∈RΓ`,ji+aθm−λi,∀`6=i.
5.1.9 Beme kung. Au g und de on uns gewähl en O dnung au Rbesch eib die
le z e Bedingung, dass die le z en λiSummanden de θ-adischen En wicklung on Γ`,ji
gleich Null sind, d.h. Γ`,ji=Pm−λi−1
h=0 coe (h)
(Γ`,ji)·θh. Insbesonde e alls λi=mgil ,
is somi die Spal e Γ∗,jigleich dem i- en Einhei s ek o .
5.1.10 Folge ung. Die e s en k0Zeilen eine Ma ix Γ∈Rk×nin eduzie e Zeilen-
s u en o m bilden eine Gene a o ma ix des on Γe zeug en linea en Codes.
Beweis. Man zeig leich , dass die Zeilen unabhängig sind. Au g und de ge o de en
Ano dnung de Pe ioden is Γ[k0],∗also eine Gene a o ma ix.
5.1.11 Beispiel. Die Ma ix Γ = 2 1∈Z1×2,(2)
4is eine Gene a o ma ix eines
linea en Codes in Zeilens u en o m. Sie is jedoch nich eduzie . Da alle wei e en Ge-
ne a o ma izen on Cdu ch Linksmul iplika ion mi Einhei en aus Γhe o gehen, gib
es also ü Ckeine Gene a o ma ix in eduzie e Zeilens u en o m.
Das Beispiel e deu lich , dass nich jede Bahn GLk(R)Γ eine Ma ix Γ∈Rk×nein
Elemen in eduzie e Zeilens u en o m en häl . Umgekeh zeig abe de nach olgende
Hil ssa z, dass sie im Fall de Exis enz eindeu ig bes imm is und dami du chaus zu
De ini ion eines kanonischen Rep äsen an en geeigne is .
89

5. Linea e Codes übe endlichen Ke en ingen
5.1.12 Hil ssa z. Is Γ∈Rk×neine Ma ix in eduzie e Zeilens u en o m, so exis ie
in de Bahn GLk(R)Γ keine wei e e Ma ix in eduzie e Zeilens u en o m.
Beweis. Wi nehmen an, dass e
Γ∈GLk(R)Γ eine wei e e Ma ix in eduzie e Zei-
lens u en o m sei. Is nun k0de Rang des on Γe zeug en linea en Codes Cund λ
dessen Um iss, so sind also Γ[k0],∗und e
Γ[k0],∗beides Gene a o ma izen on Cund beide
Teilma izen in eduzie e Zeilens u en o m.
Die wei e en Zeilen on Γund e
Γsind Nullzeilen und somi können wi ohne Besch än-
kung de Allgemeinhei annehmen, dass k0=kgil . Die Ma ix e
Γe hal en wi also
du ch Linksmul iplika ion on Γmi eine geeigne en Ma ix A∈GLλ(R). Wi zeigen
nun übe eine Induk ion nach k, dass Abe ei s in Nλ(R)lieg und somi beide Ma izen
gleich sind.
Fü k= 1 is die Behaup ung leich einzusehen. Fü den Induk ionssch i seien
j0, . . . , jk−1sowie `0, . . . , `k−1die Indizes de Pi o spal en on Γbzw. e
Γ. Man übe leg
sich leich , dass j0=`0gel en muss. Aus de Gleichung AΓ∗,j0=e
Γ∗,j0e häl man da-
mi A0,0∈1 + Rad(R)λ0und Ai,0∈Rad(R)λ0 ü alle i > 0. Die Teilma izen Γ≥1,∗
und e
Γ≥1,∗e zeugen aus diesem G und den gleichen linea en Code und sind Gene a o -
ma izen in eduzie e Zeilens u en o m. Fü sie gil also die Induk ions o ausse zung
und es is Γ≥1,∗=e
Γ≥1,∗. Dami liegen auch die wei e en Pi o spal en an iden ischen
Koo dina enposi ionen, d.h. jµ=`µ ü alle µ∈[k].
Abschließend zeig man übe eine Induk ion ü µ > 0, dass A0,µ ∈Rad(R)λµlieg .
Wi be ach en hie zu 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 Ma ixein äge e
Γ0,jµ=und Γ0,jµsind modulo θm−λµ eduzie , d.h. Nebenklassen e-
p äsen an en on R/ Rad(R)m−λµ. Dami olg die Behaup ung A0,µ ∈Rad(R)λµ.
5.1.13 De ini ion (sys ema ische Gene a o ma ix).Eine Gene a o ma ix Γ∈Rk×n,λ
in eduzie e Zeilens u en o m heiß sys ema isch, alls sich die Pi o spal en an den
Posi ionen j0= 0 bis jk−1=k−1be inden.
Fü linea e Codes übe endlichen Kö pe n kenn man be ei s die Aussage, dass ein
beliebige linea e Code pe mu a ionsäqui alen zu einem Code mi sys ema ische Ge-
ne a o ma ix is . Fü Ke en inge gil diese Aussage eben alls:
5.1.14 Fak ([73, Sa z 2.1]).Es sei Γ∈Rk×neine beliebige Ma ix, welche einen
linea en Code C om Um iss shp(C) = λ= (λ0, . . . , λk0−1)e zeug . Dann gib es eine
Pe mu a ion π∈Sn, so dass de linea e Code π·Ceine sys ema ische Gene a o ma ix
e
Γ∈Rk×n,λ besi z .
90
5.1. Gene a o ma izen
Insbesonde e is de Beweis zu dem Sa z kons uk i . Es wi d also in [73] explizi ein
Algo i hmus zu Be echnung de Pe mu a ion π∈Snund eine Ma ix A∈GLk(R)mi
AΓP(π)−1=e
Γ
0(k−k0)×nangegeben.
Will man nun ü beliebige Ma izen Γ∈Rk×neinen kanonischen Rep äsen an en
CFGLk(R)(Γ) un e de Ope a ion on GLk(R)bes immen, so is es einzig nö ig, die
Wahl de Pe mu a ion π∈Snaus Fak 5.1.14 GLk(R)-in a ian o zunehmen. Dies is
in de Ta auch möglich: Man kann sich leich übe legen, dass es genüg , die Auswahl
eines Elemen s ai,j im Beweis zu [73, Sa z 2.1] de a o zunehmen, dass js e s minimal
is . Dann bes imm man den kanonischen Rep äsen an en CFGLk(R)(Γ) on Γübe die
olgenden Sch i e:
1. Bes imme eine Ma ix A∈GLk(R), so dass A(ΓP(π)−1)bis au wei e e Nullzeilen
die eindeu ige sys ema ische Gene a o ma ix in de Bahn GLk(R)(ΓP(π)−1)is .
2. De inie e CFGLk(R)(Γ) := AΓ = AΓP(π)−1P(π). Diese Auswahl is somi eben-
alls eindeu ig in de Bahn GLk(R)Γ.
5.1.15 Beme kung. Man kann sich leich übe legen, dass dieses Vo gehen mi de De-
ini ion de sog. Fulle Canonical Fo m1 ü Galois-Ringe, gemäß [54, Exe cise (XVI.7)]
bzw. de en wei e e Ve allgemeine ung au beliebige Ke en inge in [17], übe eins imm .
Is Γ∈Rk×neine Gene a o ma ix in eduzie e Zeilens u en o m, so is sie mi
diese De ini ion de kanonische Rep äsen an ih e eigenen Bahn. Wi wollen nun noch
diejenigen Ma izen auszeichnen, welche ohne Pe mu a ion de Spal en au eduzie e
Zeilens u en o m geb ach we den können:
5.1.16 De ini ion (um iss eu).Wi sagen eine Ma ix Γ∈Rk×nmi shp(Γ) = λis
um iss eu, alls ü alle i∈[n]die Teilma izen Γ∗,[i]den Um iss shp(Γ∗,[i]) = λ[ g(Γ∗,[i])]
haben. Dabei bezeichne g(Γ∗,[i]), wie e einba , den Rang des on Γ∗,[i]e zeug en
Zeilen aums.
5.1.17 Hil ssa z. Eine Ma ix Γ∈Rk×nis genau dann um iss eu, wenn sie du ch
Linksmul iplika ion mi eine Ma ix A∈GLk(R)au eduzie e Zeilens u en o m AΓ
ans o mie we den kann.
Beweis. Jede Ma ix Γ0∈Rk×nin eduzie e Zeilens u en o m is ganz o ensich lich
um iss eu. Die Eigenscha um iss eu zu sein, is abe eine GLk(R)-In a ian e. Somi
is auch jedes wei e e Elemen de Bahn GLk(R)Γ0um iss eu.
Es bleib also nu noch zu zeigen, dass sich jede um iss eue Ma ix Γ∈Rk×nauch
au eduzie e Zeilens u en o m ans o mie en läss . Wi zeigen dies übe eine Induk ion
nach de Anzahl de Spal en. Fü den Induk ionss a n= 0 is die Aussage i ial.
1Sie is mo i ie du ch die A bei [27].
91
5. Linea e Codes übe endlichen Ke en ingen
Fü den Induk ionssch i on n−1nach n≥1sei k0= g(Γ∗,[n−1])und λ= shp(Γ).
Die Ma ix Γ∗,[n−1] is eben alls um iss eu und wi können dahe ohne Besch änkung
de Allgemeinhei annehmen, dass diese in eduzie e Zeilens u en o m o lieg :
Γ = Γ[k0],[n−1] Γ[k0],n−1
0(k−k0)×(n−1)Γ[k] [k0],n−1
Is Γ[k] [k0],n−1=0(k−k0)×1, d.h. k0= g(Γ), so is Γin eduzie e Zeilens u en o m.
Hie zu mach man sich leich kla , dass ü i∈[k0]die Annahme Γi,n−16∈ Rad(R)m−λi
so o de Eigenscha um iss eu zu sein wide sp äche.
Im Fall Γ[k] [k0],n−16=0(k−k0)×1schließ man analog, dass ü alle i∈[k0]be ei s
Γi,n−1∈Rad(R)m−λigel en muss. Des Wei e en is dann auch pe (Γ[k] [k0],n−1) = λk0
und es exis ie ein Ein ag Γj,n−1mi k0≤j < k und pe (Γj,n−1) = λk0. De S abilisa o
S abGLk(R)Γ∗,[n−1]beinhal e abe nun alle Ma izen de Ges al
Ik0B
0(k−k0)×k0Ami A∈GLk−k0(R)und B∈Rk0×(k−k0),
welche es uns e lauben, Γau eduzie e Zeilens u en o m zu ans o mie en.
5.1.18 Hil ssa z. Is die Ma ix Γ∈Rk×num iss eu und (ϕ;α)∈(R∗)noAu (R)
beliebig, so is auch (ϕ;α)Γ um iss eu.
Beweis. Die G uppenope a ion mi (ϕ;α)de inie einen Ve bandsau omo phismus au
PHG(RRn). Insbesonde e bleib also de Um iss eine Ma ix unbe üh . Dies gil na-
ü lich auch ü alle Teilma izen ((ϕ;α)Γ)∗,[i],i∈[n+ 1]. Somi is (ϕ;α)Γ eben alls
um iss eu.
5.1.1. Re o mulie ung de G uppenope a ion
In Folge ung 5.1.7 haben wi das Kanonisie ungsp oblem ü linea e Codes be ei s au
eine G uppenope a ion de G uppe
(GLλ(R)/Nλ(R)×(R∗)n)o(Au (R)×Sn)
au de Menge Rk×n,λ zu ückge üh . Insbesonde e haben wi auch es ges ell , dass die
Un e g uppe GLλ(R)nich eu ope ie und dies du ch den Übe gang zu de Fak o -
g uppe GLλ(R)/Nλ(R)behoben. Eine analoge Aussage wollen wi nun auch ü die
Spal en de Gene a o ma ix he lei en. Hie du ch we den wi die Komponen en (R∗)n
und Snde ope ie enden G uppe noch wei e einsch änken.
5.1.19 Hil ssa z. Es sei G:= (GLλ(R)/Nλ(R)×(R∗)n)oAu (R). Die Abbildung
(pe ) :Rk×n,λ →[m+ 1]n,Γ7→ (pe (Γ∗,i))i∈[n],
welche jede Spal e on Γ∈Rk×n,λ ih e Pe iode2zuo dne , is eine G-In a ian e und
ein Sn-Homomo phismus.
2Zu E inne ung: Die Pe iode pe ( )eines Spal en ek o s ∈Rk
Ris de inie als die minimale ganze
Zahl mi θpe ( )=01×k.
92
5.1. Gene a o ma izen
Beweis. Die Pe iode eines Spal en ek o s ∈(Rk)Rbleib in a ian un e de Mul i-
plika ion mi in e ie ba en Ma izen on links, de Mul iplika ion on Einhei en on
ech s und auch un e de komponen enweisen Anwendung eines Ringau omo phismus.
Somi is die Funk ion in a ian un e de Ope a ion mi els Gim De ini ionsbe eich.
Sie is auße dem ganz o ensich lich auch ein Sn-Homomo phismus.
Zwei Gene a o ma izen Γ,Γ0∈Rk×n,λ e zeugen nu dann semilinea isome ische
Codes, wenn die Bilde (pe )(Γ) und (pe )(Γ0)in de gleichen Bahn un e de Ope a ion
on Snliegen.
Wi legen nun übe das Homomo phiep inzip und übe die Kanonisie ung im Bild-
be eich on (pe ) es , dass die Folge CFSn (pe )(Γ)=: µ∈[m+ 1]nmono on äll .
Somi sind die Pe ioden de Spal en jede kanonischen Gene a o ma ix CFGoSn(Γ),
Γ∈Rk×n,λ beliebig, eben alls mono on allend. Wi können also im Folgenden, ohne
Besch änkung de Allgemeinhei , be ei s im Vo eld o ausse zen, dass die Eingaben
Γ∈Rk×n,λ des Kanonisie e s CanGoSnbe ei s diese Bedingungen e üllen.
In de Ope a ion de symme ischen G uppe ziehen wi uns dann au den S abilisa o
SP0:= S abSn(µ)zu ück. Die Blöcke de kanonischen Pa i ion P0besch eiben hie bei
die Koo dina en de Spal en mi gleiche Pe iode.
Eine wei e e Beobach ung, die wi an diese S elle einb ingen können, bezieh sich au
e en uell au e ende Nullspal en de Gene a o ma izen (dann is µi= 0). Vom codie-
ungs heo e ischen S andpunk sind diese Koo dina en ohnehin edundan . Aus Sich
de G uppenope a ion gil diese Beobach ung eben alls, da wi un e einem beliebigen
G uppenelemen (A, ϕ;α, π)∈((GLλ(R)/Nλ(R)×(R∗)n)oAu (R)) oSP0Nullspal en
imme au Nullspal en abbilden. Wi en e nen diese gegebenen alls o de Kanonisie-
ung und ügen sie nach Abschluss in gleiche Zahl wiede an die kanonische Fo m an.
Es is kla , wie in diesem Fall de be echne e S abilisa o zu modi izie en is .
5.1.20 De ini ion. Zu einem beliebigen Vek o µ∈({1, . . . , m})nsei
Rk×n,λ,µ := Γ∈Rk×n,λ | ∀ i∈[n] : pe (Γ∗,i) = µi
die Menge alle Gene a o ma izen om Um iss λmi es o gegebene Pe iode µide
i- en Spal e.
Im Folgenden sei also auch die mono on allende Folge µ∈({1, . . . , m})n es o geben
und es we den nu noch Gene a o ma izen aus de Teilmenge Rk×n,λ,µ be ach e . Zu
dem Vek o µsei im wei e en Ve lau P0die kanonische Pa i ion on [n], welche übe
den S abilisa o SP0:= S abSn(µ)eindeu ig bes imm is .
5.1.21 Beme kung. Einen Vek o ∈(Rk)Rmi pe ( ) = mwollen wi als e
bezeichnen. E e zeug den Punk R in de p ojek i en Rech s-Hjelmsle -Geome ie
PHG((Rk)R). Besi zen die au e enden Gene a o ma izen nu e e Spal en ek o en
(d.h. µ= (m, . . . , m)), so können wi nach Folge ung 3.1.10 dies auch als ein Kanonisie-
ungsp oblem on Punk kon igu a ionen in PHG((Rk)R)au assen.
93
5. Linea e Codes übe endlichen Ke en ingen
Es bleib also de Fall zu be ach en, dass die le z e Spal e eine Pi o spal e is , d.h.
Γ = Γ[k−1],[n−1] Γ[k−1],n−1
0n−1θm−λk−1. Die Teilma ix Γ0:= Γ[k−1],[n−1] ∈R(k−1)×(n−1),λ[k−1],µ[n−1] is
in eduzie e Zeilens u en o m und es is CFG(λ[k−1],µ[n−1])(Γ0)=Γ0. Aus de 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 de Unabhängigkei de Zeilen de Ma ix α(Γ0)schließen wi wie oben zunächs
Ak−1,j ∈Rad(R)λj ü alle j∈[k−1]. Da abe A a sächlich die Nebenklasse ANλ(R) e-
p äsen ie , können wi auch Ak−1,j = 0 se zen. Fü die wei e en Ein äge Ai,j,
i∈[k−1] de Spal e A∗,j e gib sich die Aussage übe die Induk ionsannahme, denn es
is A[k−1],[k−1] ∈S abG(λ[k−1],µ[n−1] (Γ0)↓GLλ[k−1] (R).
Somi bleib die Aussage ü die le z e Spal e A∗,k−1zu beweisen. Es sei also
i∈[k−1] mi λi=λk−1beliebig. Da Γeine Gene a o ma ix is , lieg de Ein ag Γi,n−1
in Rad(R)m−λi. Ande e sei s is e abe auch modulo dem Pi o elemen θm−λk−1=θm−λi
eduzie . Wi schließen, dass Γi,n−1= 0 is , und e hal en hie mi
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).
Hie aus e gib sich Ai,k−1∈Rad(R)λk−1und wie oben können wi den Ein ag Ai,k−1= 0
se zen.
5.1.36 Folge ung. Besch eiben wi die Ma ix A∈S abG(Γ)↓GLλ(R)übe die Blockma-
izen A(i,j)∈Rkλ
i×kλ
j ü i, j ∈[m]gemäß de De ini ion 5.1.1, so is
A=




A(0,0) A(0,1) . . . A(0,m−1)
A(1,1) . . . A(1,m−1)
....
.
.
A(m−1,m−1)




mi Diagonalma izen A(i,i)∈GLkλ
i(R).
Im Folgenden bezeichnen wi wiede mi Sden Koe izien en ing on R, welche on
de Teichmülle -Menge Te zeug wi d. Wei e sei e∈[ ]de eindeu ige Exponen des
F obenius-Au omo phismus τ∈Au (S), ü welchen τe(ξ)θ=θξ gil .
5.1.37 Hil ssa z. Is Γ∈Rk×n,λ,µ eine Ma ix in eduzie e Zeilens u en o m und
CFG(Γ) = Γ, so gil ü jedes beliebige P∈pΓ:
100

5.1. Gene a o ma izen
1. Zu i∈Pund j∈ColsP(Γ) gib es ein x∈h
ggT( ,e)i:Ai,i =τxe(ϕj) ü alle
(A, ϕ)∈S abGlin (Γ).
2. Zu i, j ∈Pgib es ein x∈h
ggT( ,e)i:Ai,i =τxe(Aj,j) ü alle (A, ϕ)∈S abGlin (Γ).
3. Zu i, j ∈ColsP(Γ) gib es ein x∈h
ggT( ,e)i:ϕi=τxe(ϕj) ü alle (A, ϕ)∈
S abGlin (Γ).
Beweis. Die zwei e und d i e Behaup ung e geben sich o ensich lich so o aus de
E s en. Wi beweisen diese übe eine Induk ion nach de Länge ndes Codes. Fü n= 1
is sie i ial.
Es sei n≥2beliebig und Γ∈Rk×n,λ,µ eine Gene a o ma ix in eduzie e Zei-
lens u en o m mi CFG(Γ) = Γ. Wi de inie en e
Γ := Γ∗,[n−1]. Die Blöcke e
P∈pe
Γmi
e
P∩supp(Γ∗,n−1) = ∅ e en auch in pΓau . Da de Index n−1nich in Colse
P(Γ) lieg ,
e hal en wi die Aussage ü alle i∈e
Pübe die Induk ions o ausse zung.
In pΓgib es genau einen wei e en Block P, welche aus de Ve einigung de Blöcke
e
P∈pe
Γmi e
P∩supp(Γ∗,n−1)6=∅he o geh . Fü die Indizes i∈Pund j=n−1is
die Behaup ung noch zu beweisen.
1. Fall: Wi un e suchen zunächs den Fall, dass e
Γeinen linea en Code mi gleichem
Um iss λe zeug , d.h. die le z e Spal e is keine Pi o spal e. Zu einem Block e
P∈pe
Γ
mi e
P⊆Pde inie en wi `:= max( e
P∩supp(Γ∗,n−1)). Is (A, ϕ)∈S abGlin (Γ) beliebig,
so olg
Γ`,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·h (Γ`,n−1)(ϕ−1
n−1)Γ`,n−1mod Rad(R)h (Γ`,n−1)+1
und dami A`,`τe·h (Γ`,n−1)(ϕ−1
n−1)∈1+Rad(R). Die kleins e posi i e Zahl x≡h (Γ`,n−1)
mod
ggT( ,e)is also unabhängig on de Wahl des Elemen s (A, ϕ)∈S abGlin (Γ). Fü
alle wei e en i∈Pbenu z man die Induk ions o ausse zung und Punk 2. de Be-
haup ung.
2. Fall: Im zwei en zu un e suchenden Fall is die le z e Spal e on Γeine Pi o spal e
und dahe Γk−1,n−1=θm−λk−1. Die Ein äge Ak−1,k−1und ϕn−1eines G uppenelemen s
(A, ϕ)∈S abGlin (Γ) e üllen die Gleichung θm−λk−1=Ak−1,k−1θm−λk−1ϕ−1
n−1. Dies be-
weis die Aussage 1. im Spezial all i=k−1und j=n−1.
101
5. Linea e Codes übe endlichen Ke en ingen
Um die Aussage ü beliebiges i∈Pund j=n−1zu zeigen, wählen wi zunächs ein
e
P∈pe
Γ[k−1],∗mi e
P∩supp(Γ∗,n−1)6=∅und se zen wiede `:= maxe
P∩supp(Γ∗,n−1)
gleich dem g öß en Zeilenindex im Schni des T äge s mi dem Block e
P. Es olg
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ä e nun λk−1=m, so is de Ein ag Γ`,n−1modulo dem Pi o elemen Γk−1,n−1= 1
eduzie und dami gleich 0. Dies is abe ein Wide sp uch zu unse e Wahl on `.
Aus dem gleichen G und gil auch Γ`,n−16∈ Rad(R)m−λk−1. Somi is in diese Si ua ion
eben alls A`,`τe·h (Γ`,n−1)(ϕ−1
n−1)∈1 + Rad(R).
Die Aussagen ü die wei e en, nich disku ie en We e i∈Pund j∈ColsP(Γ) e geben
sich dann wiede übe die Induk ionsannahme.
5.1.38 Folge ung. Zu P∈pΓde inie en wi
aP(Γ) := minna∈N|a > 0∧ ∃ i∈P, (A, ϕ)∈S abGlin (Γ) : Ai,i =ξao.
Dann is ü alle (B, ψ)∈S abGlin (Γ):Bj,j, ψ`∈DξaP(Γ)E ü alle j∈Pund alle
`∈ColsP(Γ).
Beweis. Es sei (A, ϕ)∈S abGlin (Γ) ein Elemen des S abilisa o s, welches ü den Index
i∈Pden We Ai,i =ξaP(Γ) annimm . Du ch Po enzie en on (A, ϕ)zeig man leich ,
dass aP(Γ) ein Teile on q−1is .
Wi nehmen nun an, es gäbe ein wei e es Elemen (B, ψ)∈S abGlin (Γ) mi Bj,j =ξb
ü j∈Pode ψ`=ξb ü ein `∈ColsP(Γ), so dass ξb6∈ hξaP(Γ)i. Mi dem o ausge-
gangenen Hil ssa z is also Bi,i =ξbpex ü ein x∈h
ggT( ,e)i. Da aP(Γ) den Exponen en
bnich eil , exis ie en ganze Zahlen y, z mi
yaP(Γ) + zbpex = ggT(aP(Γ), bpex) = ggT(aP(Γ), b)< aP(Γ).
Das G uppenelemen (A, ϕ)y(B, ψ)z∈S abGlin (Γ) wide sp ich dann de Minimali ä
on aP(Γ).
Das nächs e Beispiel zeig , dass a sächlich nich i iale Teile aP(Γ) on q−1au -
e en we den.
5.1.39 Beispiel. Es is Γ := 1 0 1 1
0 1 1 Xeine Gene a o ma ix in eduzie e Zei-
lens u en o m eines linea en Codes übe dem nich kommu a i en Ke en ing R=
F16[X, τ2]/(X2). Die Pa i ion pΓis o ensich lich gleich {{0,1}}. Auße dem kann man
sich leich übe legen, dass CFG(Γ) = Γ gil .
102
5.1. Gene a o ma izen
Wegen λ0=λ1, sind die Ma izen A ü die G uppenelemen e (A, ϕ;α)∈S abG(Γ)
Diagonalma izen. Aus de Spal e Γ∗,2läss sich leich die Gleichhei A0,0=A1,1de
Ein äge de Diagonalen olge n. Is nun α= id, so e hal en wi aus de le z en Spal e
die beiden Gleichungen A1,1=A0,0=ϕ3und X=A1,1Xϕ−1
3=A1,1ϕ−4
3X=A−3
1,1X.
Dies zwing die Diagonalein äge de Ma ix Ain die Un e g uppe hξ5i+ Rad(R).
Insgesam e gib sich, dass de S abilisa o S abG(Γ) on den G uppenelemen en
•((1 + aX)·I2,(1 + aX)·14; idR)mi a∈ {1, ξ, ξ2, ξ3} ⊆ F16 beliebig,
•(ξ5·I2, ξ5·14; idR)
•und dem F obenius-Au omo phismus I2,14;χX
ξ2des Koe izien en ings F16
e zeug wi d. Be ücksich ig man auch noch, dass ξ5die G uppe alle zen alen Einhei en
e zeug , so is de zwei e Gene a o edundan .
5.1.40 Folge ung. Is Γ∈Rk×n,λ,µ eine Ma ix in eduzie e Zeilens u en o m und
CFG(Γ) = Γ, so ha de No mal eile Ψ(P,Γ)(S abGlin (Γ)) die Ka dinali ä p`P(Γ) ·q−1
aP(Γ)
ü ein `P(Γ) ∈Nund eine No mal eihe
{1G}=: G(P)
0
Zp
CG(P)
1
Zp
CG(P)
2
Zp
C. . . Zp
CG(P)
`P(Γ)
Zx
Ψ(P,Γ)(S abGlin (Γ)) (5.1)
mi zyklischen Fak o en. Dabei is x:= q−1
aP(Γ).
Beweis. Folg so o aus de o angegangenen Folge ung und Hil ssa z 5.1.28.
Es sei Γ∈Rk×n,λ,µ eine Ma ix in eduzie e Zeilens u en o m mi CFG(Γ) = Γ.
Wei e sei pΓ={P(0), . . . , P(x−1)}. Wi assen nun ku z zusammen, welche Aussagen wi
übe den S abilisa o be ei s bewiesen haben: Es is
{1G}S abGlin (Γ) S abG(Γ).
und den e s en No mal eile können wi zunächs übe die Folge ung 5.1.34 wie olg
e eine n:
{1G}Ψ(P(0),Γ)(S abGlin (Γ)) 
1
Y
i=0
Ψ(P(i),Γ)(S abGlin (Γ)) . . .

x−1
Y
i=0
Ψ(P(i),Γ)(S abGlin (Γ)) = S abGlin (Γ)
Jede Einzelsch i läss sich dann wei e mi de No mal eihe (5.1) e eine n. Somi
kennen wi ü S abGlin (Γ) eine No mal eihe mi zyklischen Fak o en. Den No mal eile
103
5. Linea e Codes übe endlichen Ke en ingen
S abGlin (Γ) S abG(Γ) e eine n wi mi de Ke e (4.1) zu:
S abGlin (Γ) S abGlinoAu ( −1,m−1)
ξ
(Γ) . . . S abGlinoAu (0,m−1)
ξ
(Γ)
. . . S abGlinoAu (0,2)
ξ
(Γ) S abGlinoAu ξ(Γ) S abGlinoAu T(Γ) = S abG(Γ)
(5.2)
5.1.41 Beme kung. Insgesam können wi also da on ausgehen, dass wi eine No mal-
eihe zu S abG(Γ) mi zyklischen Fak o en kennen. In diese No mal eihe sind höchs ens
|pΓ|+ 2 nich i iale Fak o en on eine O dnung ungleich p.
5.1.42 Beme kung. Es sei Γ∈Rk×n,λ,µ eine Ma ix in eduzie e Zeilens u en o m
mi CFG(Γ) = Γ. Wei e sei pΓ={P(0), . . . , P(x−1)}. Wi we den da on ausgehen,
dass wi ein E zeugendensys em (E(P(0)), . . . , E(P(x−1)), E(Au ))de G uppe S abG(Γ) zu
Ve ügung haben, welches an die oben besch iebenen No mal eihe angepass is . Dies
bedeu e , dass:
• ü einen Block P∈pΓdas E zeugendensys em E(P)=E(P)
0, . . . , E(P)
`P(Γ) on
Ψ(P,Γ)(S abGlin (Γ)) de a gewähl wi d, dass G(P)
i:= hE(P)
[i]i ü alle i∈[`P(Γ) + 1]
eine No mal eihe (5.1) bilde ; und
•die Folge E(Au ) in diesem Sinne je einen wei e en E zeuge gemäß de No mal eihe
(5.2) be ei s ell .
Mi diesen Vo be ei ungen können wi nun schließlich einen Algo i hmus zu induk-
i en Be echnung on CFG(Γ) angeben. Da wi obige Eigenscha en des S abilisa o s
eine Gene a o ma ix in eduzie e Zeilens u en o m benu zen wollen, müssen wi abe
die Menge de zulässigen Eingaben bzw. die G-Menge, au welche wi die Ope a ion
be ach en, wei e einsch änken. Wi wollen nun nu noch au um iss euen Gene a o -
ma izen ope ie en. Wi haben be ei s bewiesen, dass die Eigenscha , um iss eu zu
sein, G-in a ian is . Dami is diese Einsch änkung hinsich lich eine wohlde inie en
G uppenope a ion auch zulässig.
Fü das wei e e Vo gehen is de nach olgende Hil ssa z on zen ale Bedeu ung.
E lie e uns spä e die Vo ausse zungen zu De ini ion des Induk ionssch i s bei de
algo i hmischen Besch eibung de Kanonisie ung CFRk×n,λ,µ
G.
5.1.43 Hil ssa z. Es sei Γ∈Rk×n,λ,µ eine Gene a o ma ix, so dass CFG(Γ∗,[n−1]) =
Γ∗,[n−1] in eduzie e Zeilens u en o m is . Zu i∈[k]und x∈[m+ 1] de inie en wi
GΓ,(i,x):= ((A, ϕ;α)∈S abGΓ∗,[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 is GΓ,(i,0) =GΓ,(i+1,m)und GΓ,(i,x+1) ≤GΓ,(i,x) ü alle x∈[m].
104
5.1. Gene a o ma izen
Beweis. Die Gleichhei on GΓ,(i,0) =GΓ,(i+1,m)is so o kla . Die ande e Aussage zeigen
wi übe eine Induk ion übe die Paa e (i, x)∈[k]×[m+ 1] ausgehend on dem Paa
(k−1,0). Fü dieses beobach e man leich , dass GΓ,(k−1,0) = S abGΓ∗,[n−1]gil .
Nun we den wi sch i weise den Pa ame e xbis zum We x=me höhen, anschlie-
ßend zu (i−1,0) übe gehen und do wiede induk i bis zum We (i−1, m) o d ingen.
Es sei also nun (i, x)∈[k]×[m]beliebig. Die Aussage we den wi übe die Angabe eines
G uppenhomomo phismus
Φ(i,x,Γ) :GΓ,(i,x)→FqoF∗
qoAu (Fq)
(A, ϕ;α)7→ coe (x)
(((A, ϕ;α)Γ −Γ)i,n−1),coe (x)
(α(θx)) ·Ai,i
τex(ϕn−1), α
e i izie en. Die Mul iplika ion im Bildbe eich is hie bei übe die De ini ion
(a0, a1, α)·(b0, b1, β) := (a0+a1·α(b0), a1·α(b1), α ◦β)
ü alle (a0, a1, α),(b0, b1, β)∈FqoF∗
qoAu (Fq)gegeben. Die Menge GΓ,(i,x+1) is
dann das U bild de Un e g uppe3
(0, a1, α)|(0, a1, α)∈Φ(i,x,Γ)(GΓ,(i,x))≤FqoF∗
qoAu (Fq)
und somi eine Un e g uppe on GΓ,(i,x).
Wi beweisen, dass die Funk ion Φ(i,x,Γ) =Φ(i,x,Γ)
0,Φ(i,x,Γ)
1,Φ(i,x,Γ)
2einen Homomo -
phismus de inie , indem wi dies ge enn nach den einzelnen Komponen en (Fq,+),
(F∗
q,·)und Au (Fq)des semidi ek en P oduk s nach echnen. Es gil ü beliebige
(A, ϕ;α),(B, ψ;β)∈GΓ,(i,x):
Φ(i,x,Γ)
0(A, ϕ;α)(B, ψ;β)= coe (x)
((A, ϕ;α)(B, ψ;β)Γ −Γ)i,n−1
= coe (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!
= coe (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!
= coe (x)
Ai,iαΦ(i,x,Γ)
0(B, ψ;β)θxϕ−1
n−1+ coe (x)
((A, ϕ;α)Γ)i,n−1−Γi,n−1
=Ai,i ·τex(ϕn−1−1)·coe (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Übe die Komponen e (Fq,+) messen wi die Ve ände ung an dem Ein ag Γi,n−1.
105

5. Linea e Codes übe endlichen Ke en ingen
und
Φ(i,x,Γ)
1(A, ϕ;α)(B, ψ;β)= Φ(i,x,Γ)
1(Aα(B), ϕα(ψ); α◦β)
= coe (x)
α◦β(θx)·Ai,iα(Bi,i)·τexϕn−1α(ψn−1)−1
= coe (x)
αcoe (x)
(β(θx))θx·Ai,i ·α(Bi,i)·τex(ϕn−1)−1·τexα(ψn−1)−1
=αcoe (x)
(β(θx))·coe (x)
(α(θx)) ·Ai,i ·α(Bi,i)·τex(ϕn−1)−1·ατexψn−1−1
=coe (x)
(α(θx)) ·Ai,i ·τex(ϕn−1)−1·αcoe (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 Hil ssa z Γ∈Rk×n,λ,µ eine Gene a o ma ix, so dass CFG(Γ∗,[n−1]) =
Γ∗,[n−1] in eduzie e Zeilens u en o m is . Die zum Beweis de Aussage ü i∈[k]
und x∈[m]einge üh e Abbildung Φ(i,x,Γ) e möglich es uns nun, Algo i hmen zu
Be echnung on CanG(Γ) anzugeben. Wi gehen dabei wie olg o :
•De Algo i hmus 5.1 besch eib zunächs das Vo gehen, um den Koe izien en
coe (x)
(Γi,n−1)des Spal enein ags Γi,n−1un e de G uppenope a ion on GΓ,(i,x)
zu minimie en. Hie nu zen wi den G uppenhomomo phismus Φ(i,x,Γ) aus.
•In den Algo i hmen 5.2 und 5.3 we den dann die beiden Si ua ionen shp(Γ) =
shp(Γ∗,[n−1])bzw. shp(Γ) 6= shp(Γ∗,[n−1])ge enn oneinande un e such .
In den Algo i hmen we den wi auch au olgende, leich zu e i izie ende Eigenscha
de G uppen GΓ,(i,x)zu ückg ei en:
5.1.44 Hil ssa z. Fü beliebiges i∈[k],x∈[m]und (A, ϕ;α)∈GΓ,(i,x)is
G(A,ϕ;α)Γ,(i,x+1) = (A, ϕ;α)GΓ,(i,x+1)(A, ϕ;α)−1
Beweis. Dies läss sich leich aus de De ini ion de G uppen als S abilisa o en he lei en.
106
5.1. Gene a o ma izen
Algo i hmus 5.1 MinS ep
Inpu : i∈[k−1] ,x∈[m]
Inpu : Γ∈Rk×n,λ,µ so dass CFG(Γ∗,[n−1])=Γ∗,[n−1] in eduzie e Zeilens u en o m
Inpu : E:= (Ej)j∈[s+1] E zeugendensys em de G uppe hEi=GΓ,(i,x)mi
•hE[j]ihE[j+1]i ü alle j∈[s+ 1] mi hE[j+1]i/hE[j]i ≃ Zej
• ü alle j∈[s]gil Φ(i,x,Γ)
2(Ej) = idFqund ej6=p⇐⇒ ej|(q−1)
•es= o d(Φ(i,x,Γ)
2(Es))
Ou pu : Γ0∈GΓ,(i,x)Γmi coe (x)
Γ0
i,n−1minimal un e allen Bahnenelemen en
Ou pu : T∈GΓ,(i,x):TΓ = Γ0und E0E zeugendensys em on GΓ0,(i,x+1)
1: p ocedu e MinS ep(i, x, Γ, E)
2: E0←()
3: (aj, bj, αj)←Φ(i,x,Γ)(Ej) ü alle j∈[s+ 1]
4: V← {0Fq}// als Fp-Un e ek o aum on (Fq,+)
5: B← ∅ // Indizes zu eine Basis on V
6: W← {0Fq},B0← ∅
7: o j∈[s+ 1] do
8: i j6=s∧bj= 1Fq hen
9: i aj∈V hen
10: bes imme x∈[p]B, so dass aj+P`∈Bx`a`= 0
11: Append(E0,Q`∈BEx`
`Ej)
12: else
13: V← hV, aji// als Fp-Un e ek o aum on 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: bes imme x∈[p]Bund y`0∈[e`0] ü `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 o
107
5. Linea e Codes übe endlichen Ke en ingen
Algo i hmus 5.1 MinS ep (Fo se zung)
27: ( , w)←a gmin
( 0,w0)∈V×Wcoe (x)
(Γi,n−1) + w0+ 0
28: bes imme x∈[p]B:P`∈Bx`a`=
29: bes imme y`0∈[e`0] ü `0∈B0mi Φ(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 Beme kung 5.1.46
32: e u n (TΓ, T, E0)
5.1.45 Hil ssa z. Algo i hmus 5.1 is ko ek .
Beweis. Um au e schiedene Va iablenbelegungen wäh end des Ablau s des Algo i h-
mus zug ei en zu können, bezeichne die mi [j+ 1] indizie en Va iablen V[j+1],W[j+1],
B[j+1] den We de Va iablen V, W, B nach Abschluss on Zeile 25 in Algo i hmus 5.1
zum Index j∈[s+ 1]. Auße dem sei die Va iablenbelegung di ek nach de Ini ialisie-
ung mi [0] indizie .
Fü den Beweis zeigen wi zunächs induk i , dass ü alle j∈[s+ 1] die olgende
Hil saussage gil :
V[j]=a`|`∈B[j]Fp= Φ(i,x,Γ)
0hE[j]i ∩ ke Φ(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)
De Induk ionss a j= 0 en sp ich den ini ialisie en Va iablen. Diese e üllen ganz
o ensich lich die gemach en Aussagen. Fü den Induk ionssch i on jnach j+ 1 un-
e scheiden wi nun die beiden Fälle analog zu de I -Bedingung in Zeile 8:
1. Fall (j6=s∧bj= 1Fq): Jedes beliebige G uppenelemen (A, ϕ;α)∈ hE[j+1]iläss sich
in de Fo m (A, ϕ;α) = Ez
j(B, ψ;β)mi z∈Nund (B, ψ;β)∈ hE[j]ida s ellen.
Um Gleichung (5.3) zu beweisen, sei nun (A, ϕ;α)∈ hE[j]i ∩ ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2
beliebig. Da auch Ej∈ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2im Ke n lieg , is (B, ψ;β)eben alls ein
Elemen diese Un e g uppe, und es gil
Φ(i,x,Γ)
0(A, ϕ;α) = Φ(i,x,Γ)
0(Ez
j(B, ψ;β)) ∈zaj+V[j]⊆V[j+1].
Umgekeh läss sich abe auch au g und de Induk ions o ausse zung jedes Elemen
∈V[j+1] als Summe =Pb∈B[j+1] zbabmi zb∈[p]da s ellen. Das G uppenelemen
Qb∈B[j+1] Ezb
blieg im Ke n on Φ(i,x,Γ)
1oΦ(i,x,Γ)
2und es is Φ(i,x,Γ)
1(Qb∈B[j+1] Ezb
b) = .
108
5.1. Gene a o ma izen
Dami is die Aussage de Gleichung (5.3) in beiden Teil ällen aj∈V[j]bzw. aj6∈ V[j]
gezeig . Gleichung (5.4) zeig man analog.
Die Gül igkei on Gleichung (5.5) e gib sich aus dem Un e g uppendiag amm
ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2∩ hE[j+1]i
ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2∩ hE[j]ike Φ(i,x,Γ)∩ hE[j+1]i
ke Φ(i,x,Γ)∩ hE[j]i
ejp|B[j+1]|
p|B[j]|
Die angegebenen Indizes de jeweiligen Un e g uppen lassen sich leich übe den Homo-
mo phiesa z, also übe die Mäch igkei en de Bilde schließen. Is nun aj∈V[j], so is
|B[j+1]|=|B[j]|und dahe de Index on ke Φ(i,x,Γ)∩ hE[j]iin ke Φ(i,x,Γ)∩ hE[j+1]i
gleich ej. Man übe leg sich leich , dass de neu hinzugenommene E zeuge E0
jin Zeile
11 genau den nö igen Ans ieg de G uppeno dnung bewi k .
Im Fall on aj6∈ V[j]is abe pein Teile on ejund dami ej=p. Dami sind abe
die G uppen ke Φ(i,x,Γ)∩ hE[j]iund ke Φ(i,x,Γ)∩ hE[j+1]iin diesem Fall gleich.
2.Fall (j=s∨bj6= 1Fq): Wi beginnen wiede mi dem Beweis de Aussage (5.3). Falls
j < s gil , so is ejein Teile on (q−1). Also sind auch die Quo ien en
ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2∩ hE[j+1]i
ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2∩ hE[j]i
bzw. Φ(i,x,Γ)
0hE[j+1]i ∩ ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2
Φ(i,x,Γ)
0hE[j]i ∩ ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2
Teile on ejbzw. (q−1). Hie aus schließen wi , dass
V[j+1] = Φ(i,x,Γ)
0hE[j+1]i ∩ ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2
= Φ(i,x,Γ)
0hE[j]i ∩ ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2=V[j]
gel en muss. Im Spezial all j=skönnen wi nich übe die Teilba kei a gumen ie en,
da mögliche weise de Index esein Viel aches on pis . Wi nu zen in diese Si ua ion
die Ta sache, dass ü beliebiges (B, ψ;β)∈ hE[s+1]ieine Gleichung de Ges al :
idFq= Φ(i,x,Γ)
2Ez0
s(B, ψ;β)=αz0
s◦idFq ü ein z0∈Z
so o αz0
s= idFqund somi z0≡0 mod esimplizie . Hie aus e gib sich V[s+1] =V[s],
denn es is
ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2∩ hE[s+1]i= ke Φ(i,x,Γ)
1oΦ(i,x,Γ)
2∩ hE[s]i.
109
5. Linea e Codes übe endlichen Ke en ingen
Genauso zeig man auch, dass die sepa a e Behandlung de Fälle x≥m−λk−1in
Zeile 26 ko ek is . Nun gehen die wei e en E zeuge (A(i,j,h),1n; idR)j∈[ ],h∈[λk−1]ein.
Hie i die on uns oben besch iebene Si ua ion au , dass die Bilde diese E zeuge
eine Basis on V=F
pim Algo i hmus MinS ep bilden.
Fü die wei e en Beobach ungen nehmen wi an, dass de kanonische Rep äsen an
CFG(Γ) = Γ induk i übe eine Folge de Algo i hmen 5.2 und 5.3 ausgehend on eine
beliebigen um iss euen Ma ix Γ0∈GΓbe echne wu de.
5.1.50 Beme kung. In de Zeile 8 on Algo i hmus 5.2 und in Zeile 12 on Algo i hmus
5.3 wü de es genügen, jeweils das le z e Elemen on Fund E(Q)zu übe geben, da alle
wei e en Elemen e nachweislich im Ke n on Φ(i,x,Γ) liegen.
Wi beenden diesen Abschni mi eine Abschä zung de Ka dinali ä des E zeugen-
densys ems E. Sie beein luss maßgeblich die Lau zei des Back ackalgo i hmus. Wi
zeigen, dass diese Zahl im Wesen lichen on ,λund de Länge de No mal eihe (4.2)
abhäng .
5.1.51 Hil ssa z. Mi osei die Länge de Komposi ions eihe on Au Tgemäß (4.2)
bezeichne . Die Anzahl de E zeuge de G uppe S abG(Γ), welche in den Algo i hmen
5.2 und 5.3 zu ückgegeben4we den, is s e s du ch
pΓ+ X
j∈[k]
λj+o
nach oben besch änk .
Beweis. Alle neuen E zeuge , die zu Beginn on Algo i hmus 5.2 in de Folge Fzu
Ve ügung ges ell we den, we den auch wiede in den Au u en on MinS ep en e n .
Dabei häng de Zei punk on de Ve eilung de Höhen in de Spal e Γ∗,n−1ab. De
Ein ag Γi,n−1mi de Höhe m−µn−1ga an ie abe , dass alle E zeuge aus Fbei
dessen Kanonisie ung en e n we den.
Bei eine Ve einigung on Qmi P0kann man übe dies leich aus de o ausgegangenen
Beme kung und dem Ablau on Algo i hmus 5.1 schließen, dass sich do eben alls die
Länge des E zeugendensys ems um eins e inge .
In Algo i hmus 5.3 we den dahingegen (µn−1−1) + 1 wei e e E zeuge in de Folge
Fzu Ve ügung ges ell . Wi un e scheiden zwei Teil älle: Is µn−1=λk−1so handel es
sich um eine Spal e, bei welche wi alle wei e en Nich nullein äge übe eine Addi ion
mi dem Pi o elemen zu 0 ans o mie en können. Dami bleiben alle neu hinzugenom-
menen E zeuge e hal en. Dies deck sich abe mi de Behaup ung.
Is hingegen µn−1> λk−1, so gib es mindes ens einen Ein ag de Höhe m−µn−1.
Fü diesen können wi wie oben schließen, dass alle Spal enmul iplika ionen de Ges al
4Die Aussage basie au de Annahme, dass Algo i hmus 5.1 gemäß Beme kung 5.1.47 modi izie
wu de.
116

5.2. Ein Kanonisie e
1+aθx ü 1≤x≤µn−1−λk−1−1und a∈R∗nich du ch eine Addi ion des Pi o elemen
ausgeglichen we den können. Es we den also mindes ens (µn−1−λk−1−1) E zeuge
aus Fin den Au u en de Sub ou ine MinS ep in den Zeilen 12 und 21 auch wiede
en e n . Somi bleiben höchs ens
(µn−1−1) − (µn−1−λk−1−1) = λk−1
neu hinzuge üg e E zeuge auch nach Abschluss on Algo i hmus 5.3 e hal en.
Übe eine Induk ion e häl man dami die angegebene obe e Sch anke.
5.1.52 Folge ung. Die Mäch igkei de G uppe S abG(Γ) is höchs ens
(q−1)pΓ·qPk−1
i=0 λi· |Au T|.
5.2. Ein Kanonisie e
Nun sind alle G undlagen geleg , um einen Kanonisie e CanRk×n,λ,µ
GoSP0 ü die Ope a ion
de G uppe GoSP0mi
G:= GLλ(R)/Nλ(R)×(R∗)n/(R∗)µoAu T
au de Menge alle Gene a o ma izen Γ∈Rk×n,λ,µ zu en wickeln. Fü die zugehö igen
linea en Codes können wi das E gebnis als eine Kanonisie ung un e de Ope a ion de
G uppe alle semilinea en Isome ien on Rnin e p e ie en. Wie wi be ei s in Abschni
2.3.1 beobach en konn en, is die G uppe alle semilinea en Isome ien die maximale Un-
e g uppe de Isome ieg uppe, welche linea e Codes au linea e Codes abbilde . Somi
is de hie be ach e e Äqui alenzbeg i ü linea e Codes, de allgemeins Mögliche,
welche sich noch als eine G uppenope a ion au de Menge alle linea en Codes be-
sch eiben läss . Die beiden schwäche en Äqui alenzbeg i e – Pe mu a ionsisome ie und
linea e Isome ie – e geben sich dann leich du ch die en sp echenden Einsch änkungen
au die jeweiligen Un e g uppen
GLλ(R)/Nλ(R)bzw. GLλ(R)/Nλ(R)×(R∗)n/(R∗)µ.
Mi Γ∈Rk×n,λ,µ sei nun bis au Wei e es imme diejenige Gene a o ma ix bezeichne ,
ü welche wi die Kanonisie ung du ch üh en we den. Wi besch eiben, wie wi einen
Suchbaum T(Γ, G oSP0)gemäß Abschni 3.3 au bauen we den. Die Pa i ionie ung
is do be ei s übe die Indi idualisie ung on Koo dina en i∈[n] es o gesch ie-
ben wo den. Die Ve eine ung Vse z sich aus eine i e ie en Anwendung de inne en
Kanonisie ung V(im), siehe auch Abschni 3.3.1, und de äuße en Ve eine ung V(a)
zusammen. Diese Funk ionen sind noch nich nähe spezi izie und müssen nun on
uns be ei ges ell we den. Insbesonde e we den wi hie bei auch ga an ie en, dass nu
die Nebenklassen e e e C(GoSP0)zu den speziellen Un e g uppen L(GoSP0)aus
Gleichung (3.6) als Bilde au e en we den.
117
5. Linea e Codes übe endlichen Ke en ingen
Im Rahmen de äuße en Ve eine ung V(a)we den wi i e ie e schiedene Familien
 HoSPHoSP∈L(GoSP0) on HoSP-Homomo phismen zu Anwendung b ingen. Fü das
wei e e Vo gehen is zunächs an diese S elle nu en scheidend, dass diese H-in a ian
sind. Fü Γ∈Rk×n,λ,µ und (g;π)∈GoSP0sind dami die Bilde V(a)(Γ, H oSP(g;π))
de äuße en Ve eine ung s e s Rech snebenklassen on HoSQ ü eine kanonische
Pa i ion QP.
Wi gehen nun wie olg o . Im e s en Abschni 5.2.1 we den wi zunächs besch ei-
ben, wie wi aus dem o angegangenen Abschni 5.1.2 eine e izien e inne e Kanonisie-
ung V(im) gewinnen we den. Die De ini ion de Homomo phismen HoSPzu De ini ion
de äuße en Ve eine ung olg dann in Abschni 5.2.2.
Die gewähl e O dnung au Rbeein luss die De ini ion des kanonischen Rep äsen an-
en CanRk×n,λ,µ
GoSP0(Γ) maßgeblich. Insbesonde e is die O dnung on de Wahl on θund ξ
abhängig. In Abschni 5.2.3 we den wi dahe disku ie en, ob wi die Resul a e on e -
schiedenen Kanonisie ungen, e wa zu einem isomo phen Ke en ing R0ode bei ande e
Wahl on ξund θ, mi einande e gleichen können.
5.2.1. Inne e Kanonisie ung
Die inne e Kanonisie ung wu de in Abschni 3.3.1 in Abhängigkei de Funk ionen
Πi:X→Y(i), on Kanonisie e n CanY(i)
H ü alle H≤Gund eine Fixie eihen olge
F:X× L(GoSP0)→[n]≤nbesch ieben. Wi beginnen aus diesem G und unse e
Besch eibung zunächs mi de De ini ion de Abbildung Πi ü i∈[n]
Πi:Rk×n,λ,µ →Rk
R,Γ7→ Γ∗,i
als P ojek ion au die i- e Spal e de Ma ix. Sch änken wi die Menge de Spal en-
ek o en au das Bild Y(i):= Πi(Rk×n,λ,µ)ein, so können wi au diesem eine na ü -
liche Ope a ion on GoS abSP0(i)de inie en: Fü (A, ϕ;α, π)∈GoS abSP0(i)und
γ∈Πi(Rk×n,λ,µ)se zen wi (A, ϕ;α, π)γ:= Aα(γ)ϕ−1
i. Mi diese De ini ion is Πiganz
o ensich lich ein (GoS abSP0(i))-Homomo phismus, welche S abSP0(i)-in a ian is .
Dami e üll Πidie in Abschni 3.3.1 besch iebenen An o de ungen.
Als nächs en Sch i s ellen wi ü die Un e g uppen H≤Gdie Kanonisie e CanY(i)
H
ü die Ope a ion on Hau Y(i)zu Ve ügung. Dies ges al e sich ü beliebige Un e -
g uppen H≤Gund Spal en ek o en γ∈Y(i)als schwie ige es P oblem. Jedoch können
wi übe die Fixie eihen olge (De ini ion 3.3.4) und unse Wissen, dass nu gewisse Ne-
benklassen HoSP(g;π)∈ C(GoSP0)auch a sächlich im Back acking o kommen,
die Kombina ionen (H, γ := Πi((g;π)Γ)) s eue n.
Aus diesem G und wollen wi uns noch einmal ku z e gegenwä igen, in welche
Si ua ion wi im Back acking zu einem Kno en (HoSP(g;π), j) on T(Γ, G oSP0)
eine Kanonisie ung CanY(i)
H(γ)du ch üh en we den: Es sei = ( 0, . . . , n0−1)dasjenige
injek i e Wo de Länge n0< n mi Ein ägen aus [n] {i}, welches die Reihen ol-
ge de be ei s ixie en und un e Gminimie en Spal en angib . Dann is (g;π)Γ ein
118
5.2. Ein Kanonisie e
Algo i hmus 5.4 Inne Can
Inpu : PP0kanonische Pa i ion
Inpu : ∈FixSP([n])0n ü ein n0∈[n+ 1]
Inpu : Γ∈Rk×n,λ,µ -semikanonisch, d.h. CFG(Π (Γ)) = Π (Γ)
Ou pu : Fixie eihen olge F(Γ, G( ,Γ) oSP)
1: p ocedu e Inne Can(P, , Γ)
2: ˜
←()
3: F←FixSP([n]) { j|j∈[n0]}
4: while F6=∅do
5: k0← g(Π +˜
(Γ))
6: o e∈Fdo// in lexikog aphische Reihen olge
7: x←pe Γ[k] [k0], e
8: i x∈ {0, λk0} hen
9: (A, ϕ;α)←TRY(e)
G( +˜
,Γ) (Γ∗,e)// alls x= 0 u e Algo i hmus 5.2, sons
Algo i hmus 5.3
10: Γ←(A, ϕ;α)Γ
11: ˜
←˜
+ (e)
12: F←F {e}
13: i x=λk0 hen
14: b eak // e lasse die Fo -Schlei e
15: e u n +˜
-semikanonische Rep äsen an de Bahn GπΓ, d.h. Π ((g;π)Γ) = CFG(Π ((g;π)Γ)),
und H=G( ,πΓ) = S abG(Π ((g;π)Γ)) dessen S abilisa o . Die Koo dina e i∈[n]wu de
ixie und die Spal e γ= Πi((g;π)Γ) soll nun un e Hminimie we den. Is die Ma-
ix Π +(i)((g;π)Γ) um iss eu, so ko espondie dies abe genau mi den Si ua ionen,
welche wi mi den Algo i hmen 5.2 und 5.3 behandeln können.
Aus diesem G und we den wi also nun ga an ie en, dass die on uns gewähl e Fi-
xie eihen olge s e s zu um iss euen Ma izen Π +(i)((g;π)Γ) üh . Wi kombinie en
hie zu die De ini ion de Fixie eihen olge mi de inne en Kanonisie ung, da uns dies
die Besch eibung wesen lich e ein ach . Wi besch eiben unse Vo gehen algo i hmisch,
siehe Algo i hmus 5.4. Die Un e g uppe H=G( ,πΓ) übe geben wi dem Algo i hmus
übe die Angabe on und πΓ.
5.2.1 Sa z. De Algo i hmus 5.4 de inie eine Fixie eihen olge, indem wi pa allel zum
Back acking den benö ig en Funk ionswe ü den Kno en ((HoSP)(g;π), j)im Baum
T(Γ, G oSP0)du ch
F((g;π)Γ,(HoSP)) := Inne Can(P, F(Γ,(HoSP)(g;π), j),(g;π)Γ)
bes immen.
119
5. Linea e Codes übe endlichen Ke en ingen
Beweis. Zunächs zeigen wi , dass die Funk ion wohlde inie is . In einem e s en Sch i
lösen wi dazu die Abhängigkei on jau . Es sei also zunächs jminimal, so dass
((HoSP)(g;π), j)ein Kno en im Baum T(Γ, G oSP0)is . Wi bezeichnen mi :=
F(Γ,(HoSP)(g;π), j)und ˜
:= Inne Can(P, , (g;π)Γ) die ge o ene Koo dina en-
auswahl. Ein Kon lik kann nu dann au e en, wenn de Sohn nach de inne en Ka-
nonisie ung on de Ges al ((HoSP)(g;π), j + 1) is . Dann is abe (g;π)Γ be ei s
˜
-semikanonisch und H=G(˜
,πΓ). Diese Ta sache kann man nun nu zen um zu zei-
gen, dass dann de Algo i hmus ü die modi izie e Eingabe ˜
= +˜
eine iden ische
Ausgabe gene ie
˜
=Inne Can(P,˜
, (g;π)Γ).
Da abe ü alle wei e en Kno en ((HoSP)(g;π), j0)mi j0> j de Funk ionsau u
F(Γ,(HoSP)(g;π), j0)ge ade die Folge ˜
zu ück gib , is die Unabhängigkei on dem
I e a ionszähle jgezeig .
Als nächs es beweisen wi , dass die Funk ion auch on dem ak uell be ach e en Back-
ackbaum unabhängig is . Dazu sei ˜
Γ∈Rk×n,λ,µ eine wei e e Gene a o ma ix und
(˜g, ˜π)∈GoSP0ein G uppenelemen mi (˜g, ˜π)˜
Γ=(g;π)Γ, so dass ((HoSP)(˜g, ˜π), i)
ein Kno en im Baum T(˜
Γ, G oSP0)is . Somi is (˜g, ˜π)−1(g;π)Γ = ˜
Γund beide Bäu-
me isomo ph5. Dami können wi auch ohne Besch änkung de Allgemeinhei j=i
annehmen. Mi de Gleichhei
F(Γ,(HoSP)(g, π), j) = F((˜g, ˜π)−1(g;π)Γ,(HoSP)(g, π)(˜g, ˜π)−1(g;π)−1, j)
=F(˜
Γ,(HoSP)(˜g, ˜π), j)
is dann die Wohlde inie hei de Funk ion bewiesen.
Es bleib die ge o de en Eigenscha en eine Fixie eihen olge zu zeigen. Ohne Be-
sch änkung de Allgemeinhei können wi hie bei auch (g;π) = (1G; idn) o ausse zen.
Ganz o ensich lich is die esul ie ende Folge injek i und beinhal e nu Fixpunk e on
SP. Is nun (h;σ)∈HoSPbeliebig, so is
F((h;σ)Γ,(HoSP))
=Inne Can(P, F(Γ,(HoSP)(h;σ), j),(h;σ)Γ)
=Inne Can(P, F(Γ,(HoSP), j),(h;σ)Γ)
=Inne Can(P, F(Γ,(HoSP), j),Γ)
Fü den Beweis de le z en Gleichhei is zunächs die Beobach ung en scheidend, dass
σ∈SPdie Koo dina en e∈FixSP([n]) un e ände läss und unse Vo gehen nu au
diese Spal enauswahl be uh . Somi können wi ohne Besch änkung de Allgemeinhei
auch σ= idnannehmen. Die H-In a ianz des Resul a s zeig man übe eine ein ache
Induk ion, wi übe lassen diese dem Lese .
5Genaue gesag , können wi dies nu induk i ü den Teilbaum bis zu diese Tie e zeigen, da in einem
de a igen Beweis auch die ak uell zu beweisende Aussage eingehen müss e.
120
5.2. Ein Kanonisie e
Wi haben nun dami die no wendigen Vo ausse zungen gescha en, um die inne e
Kanonisie ung gemäß Abschni 3.3.1 zu implemen ie en. Insbesonde e können wi nun
auch im nächs en Abschni , welche die äuße e Ve eine ung behandel , unse seh um-
ang eiches Wissen übe die S abilisa o en G( ,πΓ) einb ingen.
5.2.2. Äuße e Ve eine ung
Wie be ei s angedeu e , wi d die äuße e Ve eine ung V(a)selbs wiede aus eine i e-
ie en Anwendung des Homomo phiep inzips he o gehen. In diesem Abschni wollen
wi nun die Familien on HoSP-Homomo phismen angeben, welche wi zu De ini ion
de Ve eine ung V(a)nu zen we den.
Au die exak e Besch eibung de Anwendungs eihen olge de nach olgenden einge üh -
en Homomo phismen we den wi aus olgendem G und nich meh wei e eingehen: Die
Gü e eine Ve eine ung häng zu s a k on de ak uellen Eingabe (d.h. dem ak uel-
len Kno en im Back acking) und den be ei s du chge üh en Ve eine ungen ab. Eine
Un e suchung alle möglichen Ve eine ungen und de en gegensei ige Beein lussung im
Rahmen eine i e ie en Ve eine ung ges al e sich als ein seh um ang eiches und kaum
abschließba es Un e angen. Die Fes legung eine op imalen S a egie ü jede beliebige
Eingabe Γ∈Rk×n,λ,µ is also kaum zu gewäh leis en.
Wi beme ken hie zu abe auch, dass das eingabespezi ische Ve hal en de Ve eine-
ungen be ei s bei de Kanonisie ung on G aphen zu beobach en is . Auch hie is die
Fes legung de Reihen olge, de zu Anwendung zu b ingenden Ve eine ungen, imme
noch Gegens and eines übe d eißig Jah e wäh enden und anhal enden En wicklungs-
p ozesses.
Eine geeigne e Fes legung de Reihen olge de Ve eine ungen ü die Kanonisie ung
linea e Codes e olg e bislang nu au G undlage de Beobach ung e schiedene In-
s anzen und is imme noch Gegens and ak uelle Un e suchungen. Wi geben nun also
im Folgenden nu eine Auswahl mögliche Familien on HoSP-Homomo phismen zu
möglichen De ini ion on äuße en Ve eine ungen.
Wi haben be ei s es ges ell , dass wi nich ü alle Un e g uppen HoSP∈
L(GoSP0)einen HoSP-Homomo phismus
HoSP:Rk×n,λ,µ →Zn
in eine geeigne e, geo dne e Menge Zzu Ve ügung s ellen müssen. In unse em Fall
genüg es, sich au Un e g uppen HoSPzu besch änken, welche als Besch i ung ei-
nes Kno ens (HoSP(g;π), j)in einem Back ackbaum T(Γ, G oSP0)zu eine Ma ix
Γ∈Rk×n,λ,µ au e en. Zum Beispiel wissen wi s e s, dass H=G( ,πΓ) ü :=
F(Γ, H oSP(g;π), j)gil . Dahe können wi den De ini ionsbe eich de Homomo phis-
men HoSPau die Menge de Ma izen
[
(g;π),Γ
wie oben
(HoSP)((g;π)Γ)
einsch änken.
121

5. Linea e Codes übe endlichen Ke en ingen
Einen e s en Typus on Ve eine ungen e hal en wi aus de Beobach ung de Ope a-
ion de G uppe G( ,πΓ) au (g;π)Γ. Es gil :
5.2.2 Hil ssa z. Fü alle HoSP∈ L(GoSP0)de inie die Funk ion
(inn)
HoSP:Rk×n,λ,µ →(Rk)n,Γ7→ (CFH(Γ∗,i))i∈[n]
einen HoSP-Homomo phismus, welche H-in a ian is .
Beweis. T i ial.
De Funk ionswe (inn)
G( ,πΓ)oSP((g;π)Γ) läss sich mi den Algo i hmen aus dem Ab-
schni 5.2.1 be echnen. Jedoch bedeu e diese Be echnung be ei s einen e heblichen
Au wand, alls die Anzahl de E zeuge de G uppe G( ,πΓ) ü := F(Γ, H oSP(g;π), j)
g oß is .
Aus den Homomo phismen (inn)
HoSPlassen sich abe au iel äl igs e Weisen Abschwä-
chungen en wickeln. Fo mal e hal en wi sie du ch Komposi ion mi einem wei e en
SP-Homomo phismus. Jedoch haben wi dann im Allgemeinen besse e Me hoden zu
Ve ügung, um das Bild de Komposi ion zu be echnen. Hie zu meh e e Beispiele:
•Es sei κ:= g(Π (πΓ)) < k, dann können wi die Ma ix (inn)
G( ,πΓ)oSP((g;π)Γ) au
die Zeile mi Index κp ojizie en. Diese Funk ion de inie also eben alls einen
G( ,πΓ) oSP-Homomo phismus (pe ,κ)
G( ,πΓ)oSP. Ande e sei s echne man leich nach,
dass ü i∈[n]und h∈[m+ 1] de Ein ag  (pe ,κ)
G( ,πΓ)oSP((g;π)Γ)igenau dann
gleich θhis , wenn pe ((g;π)Γ)[k] [κ],i=m−hgil . Mi diese Äqui alenz läss
sich das Bild des Homomo phismus seh iel leich e di ek bes immen.
•Eine zwei e Al e na i e gewinn man, indem man ü jedes i∈[n]den T äge de
Spal e  (inn)
G( ,πΓ)oSP((g;π)Γ)∗,i bes imm . Man kann sich auch au den Schni mi
eine es o gegebenen Teilmenge on [κ]besch änken.
•Eine wei e e Möglichkei bes eh da in, im Anschluss an die Abbildung (inn)
G( ,πΓ)oSP
eine Reduk ion modulo einem Ideal Rad(R)x ü x∈[m]du chzu üh en. Auch hie
können wi die Algo i hmen aus dem Abschni 5.1.2 abwandeln und somi den
Funk ionswe e izien e be echnen.
Diese Lis e on Vo schlägen s ell nu eine kleine Auswahl de Möglichkei en da .
Wi gehen wegen ih e Vielzahl au wei e e, so gewonnene Homomo phismen auch nich
meh wei e ein, zumal sie im Allgemeinen zu Beginn des Back ackings nich aus eichend
gu e Ve eine ungen lie e n. Ge ade hie is es abe wich ig, die Anzahl de Kinde eines
Kno ens möglichs ge ing zu hal en. Aus diesem G und we den wi auch bei den Kno en
ge inge Tie e g öße e Rechenzei en zu Be echnung de Ve eine ung au wenden.
122
5.2. Ein Kanonisie e
Einen zwei en Typ on Ve eine ungen gewinnen wi übe einen al e na i en Ansa z.
Wi we den hie zu aus de Gene a o ma ix Γdes R-linea en Codes Ceinen bipa i en
G aphen (V, E(Γ))gewinnen und die ü G aphen zu Ve ügung s ehenden Ve eine-
ungen [55] benu zen. De G aph wi d sich im Wesen lichen aus eine Teilmenge de
Codewö e on Ce geben. Dieses Vo gehen ha sich bei linea en Codes übe endlichen
Kö pe n be ei s als seh nü zlich e wiesen, siehe [24, 51].
Homomo phismen zu Wö e n eines o gesch iebenen Gewich s Im Folgenden
sei mi B(V(0), V (1))die Menge alle bipa i en G aphen au den Punk en V(0) ∪· V(1)
bezeichne . Inne halb de Kno en eilmengen V(0) bzw. V(1) e en also keine Kan en au .
Wi skizzie en zunächs , wie wi den G aphen (V, E(Γ))gewinnen wollen: Zunächs
de inie en wi Uλ:= ×k−1
i=0 R/ Rad(R)λi. Diese Menge ep äsen ie alle möglichen
In o ma ions ek o en6, welche wi mi de Abbildung
Uλ→C
(u0+ Rad(R)λ0, . . . , uk−1+ Rad(R)λk−1)7→ (u0, . . . , uk−1)Γ
codie en. De Übe gang zu den Nebenklassen R/ Rad(R)λiis no wendig, um eine Bijek-
ion beide Mengen zu e eichen. In o ma ions ek o en bzw. Codewö e , welche du ch
Linksmul iplika ion mi Ringelemen en auseinande he o gehen, wollen wi im wei e en
Ve lau zusammen assen. Aus diesem G und besch änken wi uns auch au diejenigen
Vek o en u∈U0
λ:= nu0∈Uλ| ∃ i∈[k] : u0
i∈(R/ Rad(R)λi)∗o, welche mindes ens eine
Einhei en hal en. Da zwei Vek o en u, ∈U0
λgenau dann den gleichen Modul e zeugen,
wenn sie du ch Mul iplika ion mi eine Einhei auseinande he o gehen, we den wi
in unse e Fo mulie ung on den Bahnen R∗ U0
λzu den zyklischen Linksun e moduln
Uλ:= {Ru |u∈U0
λ} on U0
λübe gehen. Mi nλ:= |Uλ|we den wi die en sp echende
Ka dinali ä diese Menge bezeichnen.
5.2.3 Beme kung. Wiede we den wi im wei e en Ve lau keine o male Un e schei-
dung zwischen den Elemen en (u0+ Rad(R)λ0, . . . , uk−1+ Rad(R)λk−1)∈Uλund den
Vek o en (u0, . . . , uk−1)∈Rk o nehmen. Die Wohlde inie hei de nach olgenden De-
ini ionen läss sich jeweils leich Nach echnen.
Als Kno enmenge des G aphen (V, E(Γ))wählen wi nun V:= [n]∪· Uλ. Die Kan en-
menge E(Γ) =Sm
j=0 E(Γ,j)pa i ionie en wi in m+ 1 disjunk e Teilmengen
E(Γ,j):= {{i, Ru} | i∈[n], Ru ∈Uλ: pe (uΓ∗,i) = j}.
De G aph (V, E(Γ))is olls ändig bipa i , d.h. jede Kno en aus [n]is mi jedem
Kno en aus Uλbenachba . Is u∈Uλbeliebig und wsym(uΓ) = (a0(uΓ), . . . , am(uΓ)),
6Bei de Da enübe mi lung we den die zu übe agenden In o ma ionen diesen Vek o en zugeo dne ,
anschließend codie und übe agen.
123
5. Linea e Codes übe endlichen Ke en ingen
so sind ü jedes j∈[m+ 1] genau aj(uΓ) Kan en aus E(Γ,j)inziden mi dem Kno en
Ru ∈Uλ. Die Pa i ionie ung de Kan enmenge können wi auch als eine Fä bung mi
m+ 1 Fa ben in e p e ie en. Ope ie en wi mi eine Pe mu a ion au diesen kan en-
ge ä b en G aphen, so soll die Pa i ionie ung de Kan enmenge hie on be ücksich ig
we den.
5.2.4 Hil ssa z. Es is (G,Ψ = (idSP0,Ψ1)) mi
G:Rk×n,λ,µ → B([n], Uλ)und Ψ1:GoSP0→SUλ
Γ7→ (V, E(Γ)) (A, ϕ;α, π)7→ Ru 7→ Rα(u)A−1
ein Homomo phismus on G uppenope a ionen.
Beweis. Es seien Γ∈Rk×n,λ,µ,(A, ϕ;α, π)∈(GoSP0),i∈[n]und Ru ∈Uλbeliebig.
Wei e sei Γ0:= (A, ϕ;α, π)Γ. Dann gil
pe (uΓ∗,i) = pe (α(u)α(Γ∗,i))
= pe α(u)A−1Aα(Γ∗,i)ϕ−1
π(i)= pe (α(u)A−1)Γ0
∗,π(i)
und somi ü j∈[m+ 1]
{i, Ru} ∈ E(Γ,j)⇐⇒ π(i), α(u)A−1= (Ψ(A, ϕ;α, π)· {i, Ru})∈E(Γ0,j).
Es is also G((A, ϕ;α, π)Γ) = Ψ(A, ϕ;α, π)· G(Γ).
Du ch den Sch i zu den G aphen G(Γ) haben wi nun ein seh mäch iges We kzeug
zu De ini ion wei e e Ve eine ungen an de Hand. Im Back ackbaum T(Γ, G oSP0)
zu Γ∈Rk×n,λ,µ können wi zum Beispiel an einem Kno en ((HoSP)(A, ϕ;α, π), j)den
G aphen
G((A, ϕ;α, π)Γ) = Ψ(A, ϕ;α, π)· G(Γ)
bilden und dann übe die Komposi ion mi einem beliebigen SP-Homomo phismus
P:B([n], Uλ)→ZnEigenscha en de Koo dina en i∈[n]bes immen.
Auch hie haben wi also eine Fülle on Möglichkei en zu Ve ügung, um wei e e
Ve eine ungen zu gewinnen. Jedoch is ü dieses nai e Vo gehen de zu e wa ende
hohe Au wand zu Be echnung de Funk ionswe e G((A, ϕ;α, π)Γ) und Ψ(A, ϕ;α, π)
seh p oblema isch.
Be o wi uns diesem P oblem zuwenden, wollen wi zunächs eine mögliche De ini ion
eines solchen SP-Homomo phismus Pan einem Beispiel o üh en:
5.2.5 Beispiel. Wi be ach en die Gene a o ma ix Γ = 1 0 2
0 1 1∈Z2×3
4. Aus ih
e hal en wi den G aphen G(Γ) in Abbildung 5.1a. In diesem konk e en Beispiel is jede
Kno en i∈[3] mi jeweils de gleichen Anzahl on ge ä b en Kan en aus E(Γ,j), j ∈[3]
inziden . Wi können also die Kno en i∈[3] zunächs nich un e scheiden.
124
5.2. Ein Kanonisie e
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) unge ä b e Kno en
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)
Fa bklasse 0 Fa bklasse 1 Fa bklasse 2 Fa bklasse 3
(b) balancie e Fä bung des G aphen
Abbildung 5.1.: G aph G(Γ) zu Beispiel 5.2.5
Jedoch beme ken wi , dass diese Beobach ung ü die Kno en aus Uλnich gegeben
is . Pa i ionie en wi die Kno enmenge Z4u∈U(2,2) nach de Fä bung de inziden en
Kan en in die angedeu e en Fa bklassen, siehe Abbildung 5.1b, so können wi in einem
wei e en Sch i die Pa i ion {{0},{1,2}} de Kno en eilmenge [3] gewinnen.
Wi wollen nun beweisen, dass wi s e s die balancie e Fä bung des G aphen G(Γ),
e gleiche Beispiel 5.2.5, zu De ini ion eines SP-Homomo phismus benu zen dü en.
Auße dem we den wi besch eiben, wie wi es e meiden, Bilde und U bilde un e dem
Homomo phismus Ψ1zu be echnen7.
Dazu wechseln wi unse e Sich weise au das P oblem: Ans a de Au gabe Γun e
de Ope a ion on GoSP0zu kanonisie en, wollen wi nun eine Kanonisie ung des Paa s
7Dadu ch e lie en wi abe gegebenen alls auch nü zliche In o ma ionen ü das Back acking. Dies is
wiede ein Beispiel ü das Abwägen zwischen de Komplexi ä de Ve eine ung und ih em Nu zen
im Back ackalgo i hmus.
125

6. Modi ika ionen & Anwendungen
Dieses Kapi el soll nun o allem au zeigen, dass de Kanonisie e aus dem Abschni
5.2 bzw. dessen Implemen ie ung, siehe Kapi el 7, auch ü g öße e und in e essan e
Codes imme noch p ak ikabel is und kanonische Rep äsen an en o allem bei Klassi-
ika ionsp oblemen den en scheidenden Vo eil b ingen. Auße dem wollen wi in diesem
Kapi el auch mögliche Modi ika ionen des Algo i hmus disku ie en, welche es e lauben,
den Kanonisie e auch in wei e en Teilgebie en de angewand en Ma hema ik, wie e wa
de K yp og aphie, einzuse zen. Es zeig sich, dass de on uns besch iebene Ansa z
seh lexibel is . Wi we den abe auch in Abschni 6.2.4 die G enzen unse es Ansa zes
au zeigen.
6.1. Linea e Codes übe Galois-Ringen de
Cha ak e is ik 4
6.1.1. Klassi ika ion e allgemeine e Teichmülle -Codes
In [45, Abschni 3.1] wu de eine Familie Tq,k,s on linea en Codes übe Galois-Ringen
R= GR(4, )de Cha ak e is ik 4kons uie , welche he o agende Pa ame e besi -
zen. Wi gehen spä e nochmals ku z au die en scheidenden Sch i e de Kons uk ion
ein. Die Codes Tq,k,s we den e allgemeine e Teichmülle -Codes genann . De Pa ame e
q= 2 besch eib hie bei, wie bishe , den Res klassenkö pe Fq≃R/ Rad(R).
Übe die G ay-Abbildung können wi die e allgemeine en Teichmülle -Codes Tq,k,s
de Länge n:= 2sqk−1
q−1mi den linea en Codes de Länge nq und de gleichen Mäch ig-
kei q2kübe Fq e gleichen. Die Hamming-Minimaldis anz des Bildes un e de G ay-
Abbildung is in ielen Fällen besse als diejenige, welche alle bekann en linea en Codes
mi gleichen Pa ame e n e eichen. Die e allgemeine en Teichmülle -Codes sind also
BTKL-Codes.
Das Kons uk ionsp inzip zu De ini ion diese Codes nu z die in Folge ung 3.1.10
gemach e Beobach ung übe den Zusammenhang zwischen linea en Codes und den Mul-
imengen de on den Spal en eine Gene a o ma ix e zeug en, zyklischen R-Rech smo-
duln. De Code Tq,k,s bes imm sich hie bei übe die Auswahl eine geeigne en Teilmenge
Tq,k,s de Punk menge ( eie Moduln om Rang 1) de p ojek i en Rech s-Hjelmsle -
Geome ie PHG(Rk
R),k≥2.
Wi we den die no wendigen Sch i e zu De ini ion de Punk menge Tq,k,s nu ku z
skizzie en, ü De ails e weisen wi au O iginalli e a u [45]:
133
6. Modi ika ionen & Anwendungen
1. Man be ach e eine Ringe wei e ung GR(4, )⊆GR(4, k) =: Sund nu z die
Isomo phie de eien R-Rech smoduln SRund Rk
R.
2. Anschließend wähl man einen Un e ek o aum Udes F2-Vek o aums Fqkde
Dimension dim(U) = s+ , welche Fqen häl . Diese de inie eine Un e g up-
pe R∗≤ΣU≤S∗de mul iplika i en G uppe und induzie eine Punk menge
p s(ΣU) := {xR |x∈ΣU⊂S}de Ka dinali ä 2sqk−1
q−1.
3. Fü gewisse Einsch änkungen an sund an die Un e äume U, siehe [45, Sa z 3.1.8],
se zen wi die Punk menge T(U)
q,k,s gleich p s(ΣU).
In den Fällen s= 0 bzw. s= (k−1) exis ie genau ein solche Un e aum U=Fq
bzw. U=Fqk. Dahe is de Code Tq,k,s bis au Isomo phie eindeu ig bes imm . In allen
wei e en Fällen gib es jedoch ü es gewähl e Pa ame e q, k, s meh e e Möglichkei en
zu Auswahl des Un e ek o aums U.
Mi den Beispielen 3.1.16 und 3.1.17 in [45] wu de nachgewiesen, dass sich aus den e -
schiedenen Wahlmöglichkei en ü Uauch nich isomo phe Z4-linea e Codes T2,5,2bzw.
T2,6,1e geben können. Die Aussage wu de hie bei übe eine Implemen ie ung unse es
Kanonisie e s in C++, siehe Abschni 7.2, bewiesen. Wi g ei en diese Aussage zu den
e allgemeine en Teichmülle -Codes T2,6,1im Beispiel 6.1.2 nochmals au .
Wi wollen nun diese Un e suchung auch au die Teichmülle -Codes übe dem nächs -
g öße en1Galois-Ring GR(4,2) o se zen. Be o wi die Beispiele bea bei en, beme ken
wi an diese S elle noch, dass die Au omo phismeng uppe Au (Tq,k,s)≤ΓLk(R)de
Punk menge Tq,k,s s e s die O dnung |Au (Tq,k,s)|=|Au (Tq,k,s)|
|Z(R)|ha .
6.1.1 Beme kung. Lau [45, Lemma 3.1.7] ope ie die G uppe ΣU/R∗scha ansi i
au p s(ΣU). Dies e klä , dass wi im Folgenden s e s eine ansi i e Ope a ion on
Au (Tq,k,s)↓Snau de Koo dina enmenge [n]des Codes Tq,k,s bzw. on Au (Tq,k,s)au
de Punk menge Tq,k,s beobach en können.
6.1.2 Beispiel. Es gib 16 Un e äume, welche zu De ini ion eines Z4-linea en Teich-
mülle -Codes T2,6,1he angezogen we den können. Diese Menge pa i ionie sich in
•zwei Isomo phieklasse mi je 6Codes, de en Au omo phismeng uppen jeweils die
O dnung 126 · |Z(Z4)|= 252 haben,
•eine Isomo phieklasse mi 3Codes, de en Au omo phismeng uppen die O dnung
252 ·2haben,
•und einen wei e en, dazu nich isomo phen Code mi eine Au omo phismeng uppe
de O dnung 756 ·2.
1Fü noch g öße e Galois-Ringe GR(4, ), ≥3is die Ka dinali ä de Codes Tq,k,s be ei s zu g oß,
um sie mi dem Kanonisie e behandeln zu können.
134
6.1. Linea e Codes übe Galois-Ringen de Cha ak e is ik 4
Fü die Codes aus den e s en beiden Isomo phieklassen beobach en wi eine Rechenzei
zwischen 150 und 220 Sekunden bei eine du chschni lichen Lau zei on 190 Sekun-
den. Bei de d i en Klasse on Codes s eig die du chschni liche Rechenzei au 220
Sekunden an. Fü den Code mi de g öß en Au omo phismeng uppe beobach en wi
einen wei e en Ans ieg de Rechenzei au unge äh 4000 Sekunden. Diese e hebliche
Ans ieg e klä sich dadu ch, dass de Back ackalgo i hmus im Gegensa z zu den an-
de en Ins anzen auch Blä e e eich , welche nich zu de schlussendlich bes imm en
kanonischen Fo m ko espondie en. Gegebenen alls ließe sich das Lau zei e hal en mi
eine Übe a bei ung de eingese z en äuße en Ve eine ung also noch wei e e besse n.
6.1.3 Beispiel. Zu De ini ion eine Punk menge T(U)
4,3,2s ehen 20 geeigne e Un e äume
Uzu Auswahl. Die Menge de esul ie enden linea en Codes T(U)
4,3,2und dami auch die
Menge de Punk mengen T(U)
4,3,2wi d du ch die G uppenope a ion in 4Isomo phieklassen
pa i ionie :
•d ei diese Klassen beinhal en je sechs linea e Codes mi eine Au omo phismen-
g uppe de O dnung 84 · |Z(GR(4,2))|,
•eine wei e e en häl genau zwei linea e Codes mi eine Au omo phismeng uppe
de O dnung 252 · |Z(GR(4,2))|.
6.1.4 Beispiel. Zu De ini ion eine Punk menge T(U)
4,4,2ha man 256 Möglichkei en
zu Wahl des Un e aums U. Jede e allgemeine e Teichmülle -Code T(U)
4,4,2ha eine
Au omo phismeng uppe de O dnung 340·|Z(GR(4,2))|. Je ach Un e äume de inie en
semilinea isome ische Codes.
Ebenso e eilen sich die 320 möglichen Codes T(U)
4,4,4au 40 Isomo phieklassen mi
je 8linea en Codes. Jede Code T(U)
4,4,4ha eine Au omo phismeng uppe de O dnung
1360 · |Z(GR(4,2))|.
Lau zei en zu den hie behandel en und wei e en Beispielen inden sich in de Tabelle
6.1. Bei dem P og ammau u handel es sich in allen Fällen um eine Implemen ie ung
des Kanonisie e s in Sage [70], siehe Abschni 7.1.2. Dabei sei mi min, max und die
minimale, maximale und du chschni liche Lau zei (in Minu en) au den Ins anzen T(U)
q,k,s
bezeichne . Die le z e Tabellenspal e gib die Anzahl de Isomo phieklassen in Abhängig-
kei on de Au omo phismeng uppe und de Anzahl zueinande isomo phe Codes an.
Ein Ein ag (a, b)xsoll hie die Bedeu ung haben, dass es xIsomo phieklassen on linea-
en Codes gib , welche bElemen e T(U)
q,k,s en hal en und de en Au omo phismeng uppen
jeweils die O dnung Au T(U)
q,k,s=a· |Z(R)|haben.
6.1.5 Folge ung. Die Ve eilung alle un e such en linea en Codes T(U)
q,k,s, ü U≤Fqk
zulässig, au Isomo phieklassen ha s e s die Eigenscha , dass die P oduk e
Au (T(U)
q,k,s)·nT(U0)
q,k,s | T (U0)
q,k,s semilinea isome isch zu T(U)
q,k,so
nu on den Pa ame e n q,k,sabhängig sind.
135
6. Modi ika ionen & Anwendungen
q k s min max 
Anzahl Isomo phieklassen nach
|Au (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.: Lau zei en de Sage-Implemen ie ung des Kanonisie e s ü Tq,k,s in Minu-
en
Da ü alle x∈Xeine G-Menge Xs e s die Bahnen o mel |S abG(x)|·|Gx|=|G|
e üll is , leg die obige Beobach ung die olgende Ve mu ung nahe:
6.1.6 Ve mu ung. Es exis ie eine G uppenope a ion eine (unbekann en) G uppe
G≤(R∗)no(Sn×Au (R)) au de Menge de linea en Codes {T (U)
q,k,s |U≤Fqkzulässig},
welche die au e enden Isomo phieklassen und alle Au omo phismen olls ändig be-
sch eib .
Wi e mu en wei e , dass sich diese Ope a ion aus eine isomo phen G uppenope a-
ion eine G uppe G0au {U|U≤Fqkzulässig}mi Hil e des Homomo phiep inzips,
de Bijek ion U7→ T (U)
q,k,s und eine Einbe ung G0,→G≤(R∗)no(Sn×Au (R)) e gib .
6.1.7 Beme kung. Diese Ve mu ung wu de be ei s on Michael Kie maie aus dem
ausgewe e en Da enma e ial zu dem Galois-Ring Z4= GR(4,1) gezogen. Sie konn e
in diese A bei mi de Un e suchung des nächs g öße en Galois-Rings GR(4,2) nun
schließlich un e maue we den.
6.1.2. Au omo phismen on e allgemeine en Ke dock-Codes
In [49] wu de die Kons uk ion de Z4-linea en Ke dock-Codes au beliebige Galois-
Ringe R= GR(4, )de Cha ak e is ik 4 e allgemeine . Wi wollen nun zunächs
diese Ve allgemeine ung besch eiben und anschließend die Au omo phismeng uppe de
e allgemeine en Ke dock-Codes un e suchen und mi unse em P og amm be echnen.
Wi können hie mi die Ko ek hei de Ausgabe e i izie en und die Einsa z ähigkei
de Implemen ie ung au in e essan en P oblemins anzen au zeigen.
Es sei k≥3und unge ade. Wie oben be ach e man wiede eine Ringe wei e ung
S= GR(4, k) on R, de inie q:= 2 und nu z die R-Modul-Isomo phie ψ:SR→Rk
R.
136
6.1. Linea e Codes übe Galois-Ringen de Cha ak e is ik 4
Dann de inie die Ma ix
Γq,k+1 := 1R1R1R. . . 1R
ψ(0S)ψ(ξ0
S)ψ(ξ1
S). . . ψ(ξqk−1
S)
einen eien, linea en Code Kq,k+1 de Länge qk om Rang k+ 1 übe dem Ke en ing
R. Die on den Spal en on Γq,k+1 e zeug e Punk menge in PHG(Rk+1
R)wollen wi die
Ke dock-Punk menge zu Kq,k+1 nennen. Im Folgenden we den wi nun ausnahmsweise
mi Tund T∗die Teichmülle -Menge bzw. Teichmülle -G uppe on Sbezeichnen.
Nun zu de angekündig en Un e suchung de Au omo phismeng uppe de e allge-
meine en Ke dock-Codes Kq,k+1. Kla is , dass
•die Mul iplika ion mi Elemen en a∈T∗de Teichmülle -G uppe eine R-linea e
Abbildung au S≃Rk
Rde inie . Diese läss sich somi übe eine Ma ix
A∈GLk(R)da s ellen. Wi schließen, dass die Ma ix (1A)∈GLk+1(R)einen
Au omo phismus de Ke dock-Punk menge de inie und somi auch einen Au o-
mo phismus des Ke dock-Codes induzie .
•Genauso de inie ein Ringau omo phismus α∈Au (S)eine R-semilinea e Abbil-
dung au S≃Rk
R. Man zeig leich , dass hie du ch eben alls ein Au omo phismus
de Ke dock-Punk menge induzie wi d.
•Die mul iplika i e G uppe R∗de inie wegen de Linea i ä de Codes übe die
i iale Ope a ion c7→ c·a−1 ü alle a∈R∗s e s Au omo phismen.
Man echne leich nach, dass alle so gewonnenen Au omo phismen (mi Ausnahme de
Iden i ä ) de Ke dock-Punk menge e schieden sind. Sie e zeugen eine Un e g uppe
on ΓLk+1(R), welche zu (R∗×T∗)oAu (S)isomo ph is .
6.1.8 Folge ung. Es sei k≥3unge ade und ∈Nbeliebig, sowie R:= GR(4, ),
S:= GR(4, k)und T∗die Teichmülle -G uppe on S. Dann besi z die Au omo phis-
meng uppe des R-linea en Ke dock-Codes Kq,k+1 eine Un e g uppe, welche isomo ph zu
(R∗×T∗)oAu (S)is .
Fü die klassischen Z4-linea en Ke dock-Codes K2,k+1 is die Au omo phismeng uppe
bekann :
6.1.9 Fak ([36]).Fü unge ades k≥5ha de Z4-linea e Ke dock-Code K2,k+1 eine
Au omo phismeng uppe de O dnung |Au (K2,k+1)|= 2·2k(2k−1)·k. De Ke dock-Code
K2,3+1 bilde eine Ausnahme und ha eine um den Fak o 8g öße e Au omo phismen-
g uppe2. Die O dnung is also 2688 = 2 ·8·23(23−1) ·3.
In beiden Fällen ope ie die Au omo phismeng uppe zwei ach ansi i au de Ke dock-
Punk menge.
2In [36] wi d älschliche weise |Au (K2,3+1)|= 1344 angegeben. Diese ehle ha e Angabe i auch in
wei e en A bei en au .
137

6. Modi ika ionen & Anwendungen
Das Zus andekommen des wei e en Fak o s 2kin de O dnung de Au omo phismen-
g uppe de Ke dock-Codes K2,k+1 wi d in [36] besch ieben.
Wi wollen nun ü den nächs g öße en Ke en ing R= GR(4,2) eben alls die Au o-
mo phismeng uppe des e allgemeine en Ke dock-Codes K4,k+1 be echnen. Au g und
des exponen iellen Wachs ums de O dnung |K4,k+1|= 42(k+1) geling uns dies ü die
e s en beiden Fälle k= 3 und k= 5:
6.1.10 Hil ssa z. Die Ke dock-Codes K4,3+1 und K4,5+1 übe dem Galois-Ring GR(4,2)
besi zen nu die in Folge ung 6.1.8 besch iebenen Au omo phismen.
Die Ke dock-Punk mengen beide Codes ze allen un e de Ope a ion de jeweiligen
Au omo phismeng uppe in zwei Bahnen. Die e s e bes eh jeweils nu aus dem Punk
(1R, ψ(0S))T. Die Punk e (1R, ψ(ξi
S))Tde Teichmülle -G uppe bilden die zwei e Bahn.
Beweis. Resul a des Au u s unse es Kanonisie e s aus Abschni 7.1.2. Die Be echnun-
gen wu den in 20 Sekunden bzw. in 18 S unden abgeschlossen.
6.1.11 Ve mu ung. Fü alle Ke dock-Codes K2 ,k+1, > 1und k≥3unge ade, is
die Au omo phismeng uppe Au (K2 ,k+1)isomo ph zu (R∗×T∗)oAu (S).
Du ch Punk ie en an de Spal e (1R, ψ(0S))Tde inie en wi zu Kq,k+1 den punk ie en
Ke dock-Code ˙
Kq,k+1. Bei den klassischen Z4-linea en Ke dock-Codes is diese besonde e
Auszeichnung eine Spal e – wegen de ansi i en Ope a ion de Au omo phismeng up-
pe au de Ke dock-Punk menge – willkü lich. In den Beispielen K4,3+1 und K4,5+1 is
dies au g und unse e Beobach ungen zu Au omo phismeng uppe abe nich meh de
Fall. In de Ta e geben sich hie zwei Isomo phieklassen on Codes mi un e schiedlichen
Eigenscha en:
•Das G ay-Bild des punk ie en Ke dock-Codes ˙
K4,3+1 de inie einen nich linea en
Code de Länge 252 übe F4de Ka dinali ä 48und Minimaldis anz 177. De
Ve gleich mi [31] zeig , dass K4,3+1 ein BTKL-Code is .
•Das Punk ie en an eine beliebigen ande en Spal e üh dahingegen zu einem Code
mi Minimaldis anz 176 und sons iden ischen Pa ame e n, siehe [45, Beme kung
2.4.3 (e)].
Hie spiel also die Auswahl de punk ie en Spal e eine gewich ige Rolle. Nu bei de
Punk ie ung an de Spal e (1R,0S)Te gib sich auch ein in e essan e BTKL-Code übe
GR(4,2).
6.2. Klassi ika ionsp obleme
Dieses Kapi el beinhal e eine Sammlung on E gebnissen, welche mi Hil e eine C++
Implemen ie ung des Kanonisie e s, siehe Abschni 7.2, im Spezial all R=Fq,R=Z4
und R=F2[X]/(X2)e ziel we den konn en. Diese E gebnisse anden auch be ei s
Eingang in die A bei en [21, 25, 26].
138
6.2. Klassi ika ionsp obleme
6.2.1. Linea e Codes übe endlichen Kö pe n
Diese Abschni bilde eine Zusammen assung de Resul a e aus dem A ikel [21]. E
behandel die olls ändige Klassi ika ion alle linea en Codes mi es gewähl en Pa a-
me e n bis au semilinea e Isome ie.
6.2.1 De ini ion. Es sei C≤Fn
qein linea e Code de Länge nund Dimension k. Fü
eine Koo dina e i∈[n]de inie man den
•in ipunk ie en Code Pi(C) := {(c0, . . . , ci−1, ci+1,...cn−1)|c∈C}du ch S ei-
chen de i- en Koo dina en, und den
•in i e kü z en Code Si(C) := Pi(S0
i(C)), indem man sich zunächs au den
linea en Teilcode S0
i(C) := {c∈C|ci= 0}zu ückzieh und anschließend die
i- e Koo dina e punk ie .
Wei e is zu einem Codewo c∈Cde esiduelle Code Res(C, c)de inie du ch das
Punk ie en des Codes Cau de T äge menge3supp(c) on c.
6.2.2 Fak ([39], Co olla y 2.7.2).Es sei C≤Fqein linea e Code de Dimension k∈
[n+ 1], mi Minimaldis anz dund duale Minimaldis anz d⊥, ku z: ein [n, k, d]d⊥
q-Code.
Fü jedes beliebige c∈Cmi wH(c) = dis Res(C, c)ein hn−d, k −1,≥ld
qmi≥d⊥
q-Code.
6.2.3 Fak (Kons uk ion Y1).Wende man die obige Kons uk ion au ein Codewo
c∈C⊥mi wH(c) = d⊥an und dualisie anschließend wiede , so nenn man dieses
Ve ah en Kons uk ion Y1. De Code Res(C⊥, c)⊥ha dann die Pa ame e
n−d⊥, k −d⊥+ 1,≥d≥ld⊥
qm
q.
Das Ziel is es nun, ü es geleg e Pa ame e n, k, q und Minimaldis anzen dsowie
d⊥alle linea en [n, k, ≥d]d⊥
q-Codes bis au semilinea e Isome ie zu klassi izie en. Diese
können wi eindeu ig du ch eine T ans e sale T(n, k, d, d⊥, q)⊆F(n−k)×n
q on Kon oll-
ma izen besch eiben. Das Ve ah en be uh nun au einem Vo gehen, welches e such ,
übe eine In e ie ung de Kons uk ion Y1einen i e a i en Algo i hmus zu en wickeln.
Ausgangspunk bilde also eine T ans e sale
S:= [
d0≥ld⊥
qm
T(n−d⊥, k −d⊥+ 1, d, d0, q)
zu allen Codes mi den möglichen Pa ame e n, welche wi aus Kons uk ion Y1gewin-
nen könn en. Anschließend we den sukzessi wei e e d⊥Spal en an die Kon ollma ix
ange üg .
3Man s eich alle Koo dina en i∈supp(c)simul an.
139
6. Modi ika ionen & 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.: Pa ame e , ü welche keine linea en Codes exis ie en
Das An ügen on Spal en kann wiede mi einem Suchbaum modellie we den. Die
Kinde eines Kno ens ∆∈T(n−(d⊥−i), k−(d⊥−i), d, i, q)au Tie e i<d⊥we den on
allen zulässigen E wei e ungen on ∆um eine wei e e Spal e gebilde . Eine E wei e ung
is zulässig, alls die Bedingungen an die Minimaldis anzen eingehal en we den. Wei e
können wi auch o sch eiben, dass die Spal en au s eigend so ie in de Kon ollma ix
o liegen. De Suchbaum wi d nun im Rahmen eine Tie ensuche du chlau en.
In de A bei [21] wu de gezeig , dass es genüg , sich in diese Suche au jede Tie e
i≤d⊥au eine T ans e sale T(n−(d⊥−i), k−(d⊥−i), d, i, q)zu ückzuziehen4. Um dies
zu gewäh leis en, wi d nun de Kanonisie e ü linea e Codes benö ig : Zu jede neu
hinzugenommenen Spal e wi d zunächs de kanonische Rep äsen an de esul ie enden
Kon ollma ix be echne . T a diese bislang noch nich au , so muss das An ügen on
Spal en o ge üh we den. Ande n alls kann man die Suche an diese S elle abb echen
und mi dem nächs en Kandida en o ah en.
E gebnisse Zu 16 e schiedenen Pa ame e upeln [n, k, d]q, siehe Tabelle 6.2, mi q=
2,3,4,5,7,8konn e die Exis enz eines linea en [n, k, d]q-Codes ausgeschlossen we den.
Übe die in De ini ion 6.2.1 au gezeig en S anda dkons uk ionen lassen sich dami soga
217 Ve besse ungen de obe en Sch anken ub(n, k, q)an die Minimaldis anz deines li-
nea en [n, k, d]q-Codes gewinnen. Dabei haben wi uns mi den e ügba en Tabellen [31]
und [65] übe die Minimaldis anz eines op imalen linea en Codes e glichen. Leide sind
die Da en in beiden Tabellen nich olls ändig. So e n bekann wu den wei e e Quellen,
e wa [2], eben alls be ücksich ig . In 109 Fällen konn e anhand diese Ve besse ungen
soga die Lücke zwischen obe e und un e e Sch anke geschlossen we den und dami
die Minimaldis anz eines op imalen linea en Codes exak bes imm we den.
Die e ziel en Resul a e sind im Un e e zeichnis esul s au de beige üg en CD ab-
u ba . Die Da ei mi dem Namen ub<q>.h ml ü q= 2,3,4,5,7,8,9en häl die obe en
Sch anken an die Minimaldis anz eines linea en [n, k]q-Codes. Die Ve besse ungen gegen-
übe de Tabelle [31] sind a big he o gehoben. Füh man den Mauszeige übe einen
a big hin e leg en Tabellenein ag, so wi d ein Beweis ode die Re e enz angegeben.
4Dieses Vo gehen is allgemein als isomo ph ejec ion bekann .
140
6.2. Klassi ika ionsp obleme
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 nich isomo phe [n, k, d]d⊥
4-Codes ü d≥6mi Un e scheidung
nach d⊥
Wi wollen nun exempla isch das Beispiel eines [21,14,6]4-Codes behandeln. Die Exis-
enz eines solchen Codes konn e übe die olgenden Be echnungen ausgeschlossen we den:
Zunächs beobach e man, dass die duale Dis anz d⊥eines de a igen linea en Codes nu
die We e 9,10 ode 11 annehmen kann. Die obe e Sch anke lies man di ek aus [31]
ab, die un e e gewinn man übe eine A gumen a ion mi dem esiduellen Code.
Die Tabelle 6.3 gib nun die Mäch igkei en de jenigen T ans e salen T(n, k, d, d⊥, q),
welche im Zuge diese Klassi ika ion bes imm wu den. De Ein ag d⊥xsag hie bei aus,
dass es xIsomo phieklassen on [n, k, ≥d]d⊥
q-Codes gib . In de Spal e n−k= 6 inde
man die Mäch igkei en de Ausgangspunk e S ü das i e a i e Vo gehen. Die Spal e
n−k= 7 besch eib die Anzahlen de zu be ach enden, nich isomo phen Codes ü
jeden Zwischensch i .
Die Ein äge mi d⊥= 1 we den also aus den diagonal da übe liegenden Ein ägen
de Spal e n−k= 6 be echne . Alle wei e en Ein äge e geben sich aus den Ein ägen,
welche di ek obe halb no ie sind. Insgesam konn en das E gebnis in eine Gesam zei
on 2.5Minu en bes imm we den.
6.2.2. Nich exis enz eines ex emalen, selbs dualen Codes de
Länge 72 mi o gesch iebenen Au omo phismen
Es sei C≤Fn
2ein selbs duale , linea e Code. Dann haben alle Codewö e ge ades
Hamming-Gewich . Sind alle au e enden Hamming-Gewich e soga du ch 4 eilba ,
so nennen wi Cdoppel -ge ade. Einen doppel -ge aden, selbs dualen Code nenn man
141