Prufziersysteme uber
Quasigruppen
H. Michael Damm
Marz 1998
Diplomarbeit
am Fachbereich Mathematik und Informatik der
Philipps-Universitat Marburg
Betreuer: Prof. Dr. H. Peter Gumm
Zweitgutachter: Prof. Dr. A. Dressler
2
3
Prufziersysteme uber Quasigruppen
Zusammenfassung
Der Begri Prufziersystem wurde von H.P. Gumm 1985 eingefuhrt. Wir untersuchen Prufziersysteme uber Gruppen und Quasigruppen. Zu jeder Ordnung
gro
er als zwei existiert ein Prufziersystem, das alle Einzelfehler und alle Nachbarvertauschungen erkennt. Fur den wichtigen Spezialfall der Prufziersysteme
uber Gruppen der Ordnung 10 zeigen wir allerdings, da
diese nicht alle Zwillings-,
Sprungzwillingsfehler oder Sprungtranspositionen erkennen.
Bei den Prufziersystemen uber Quasigruppen werden wir sehen, da
verschiedene Ansatze das Problem ebenfalls nicht losen konnen. Dennoch werden wir ein
Prufziersystem zur Basis 10 angeben, das eine Fehlererkennung von 99,89% aller
nicht zufalligen Fehler aufweist.
4
Inhaltsverzeichnis
Einleitung
1 Prufziersysteme uber Gruppen
7
11
2 Anti-symmetrische Abbildungen
21
1.1 Modulo-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Verallgemeinerung auf beliebige Gruppen . . . . . . . . . . . . . . . 13
1.3 Prufziersysteme uber abelschen Gruppen . . . . . . . . . . . . . . 15
2.1 Gruppen mit anti-symmetrischen Abbildungen
2.1.1 Beispiele . . . . . . . . . . . . . . . . .
2.1.2 Existenztheoreme . . . . . . . . . . . .
2.1.3 Erweiterungstheoreme . . . . . . . . .
2.1.4 Einfache Gruppen . . . . . . . . . . . .
2.1.5 Verallgemeinerte Diedergruppen . . . .
2.2 Invarianten von Ant(G) . . . . . . . . . . . .
2.3 A quivalenzklassen . . . . . . . . . . . . . . . .
2.4 Automorphismen und Anti-Automorphismen .
2.5 Eine Abschatzung von jAnt(G)j . . . . . . . .
2.6 Konstruktion anti-symmetrischer Abbildungen
3 Gruppen mit Vorzeichen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.1 Gruppen mit Vorzeichen . . . . . . . . . . . . . . . . . .
3.2 Anti-symmetrische Abbildungen . . . . . . . . . . . . . .
3.3 Anti-symmetrische Abbildungen der Diedergruppe . . . .
3.3.1 Fehlererkennung . . . . . . . . . . . . . . . . . . .
3.3.2 Automorphismen und Anti-Automorphismen der
Diedergruppe . . . . . . . . . . . . . . . . . . . .
3.3.3 Beispiele . . . . . . . . . . . . . . . . . . . . . . .
4 Prufziersysteme uber Quasigruppen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
22
24
25
26
27
30
31
33
37
39
45
45
48
51
53
. . . . . . 55
. . . . . . 58
61
4.1 Allgemeine Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 n-Quasigruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5
6
INHALTSVERZEICHNIS
Reduzible n-Quasigruppen . . . . . . .
Existenz von Prufziersystemen . . . .
Prufziersysteme uber Quasigruppen .
Verallgemeinerte Assoziativitat . . . .
Quasigruppen isotop zu einer Gruppe .
4.7.1 Lineare Quasigruppen . . . . .
4.8 Total anti-symmetrische Quasigruppen
4.8.1 Konstruktion . . . . . . . . . .
4.9 Quasigruppen mit Vorzeichen . . . . .
4.9.1 Beispiele . . . . . . . . . . . . .
4.10 Total anti-symmetrische Abbildungen .
4.10.1 Konstruktion . . . . . . . . . .
4.3
4.4
4.5
4.6
4.7
Literaturverzeichnis
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
69
73
74
79
84
86
88
89
94
96
98
99
103
Einleitung
Prufziern sind unscheinbar und allgegenwartig. Sie werden von Banken benutzt,
um falsch erfa
te Kontonummern oder Bankleitzahlen zu erkennen, der Buchhandel spurt mit ihrer Hilfe falsche ISBN-Nummern auf und schlie
lich bemerkt der
Laserscanner an den Kassen im Supermarkt anhand einer falschen Prufzier, da
er den Strichcode der Artikelnummer falsch eingelesen hat.
Die grundlegende Idee besteht darin, da
man aus der vorgegebenen Zahl eine
weitere Zier berechnet, welche in die Zahl eingebaut wird. Diese Prufzier wird
so bestimmt, da
Eingabe und U bertragungsfehler erkannt werden konnen. Dabei wird die errechnete Zier mit der Prufzier verglichen. Stimmen diese nicht
uberein, dann wurde die ursprungliche Zahl verfalscht. Die Prufzier wird in der
Praxis fast immer an die zu sichernde Zahl angehangt, grundsatzlich spricht aber
nichts dagegen, sie in der Mitte einzufugen oder sie an den Anfang zu stellen.
Fehlerstatistik
Um die Qualitat eines Prufzierverfahrens beurteilen zu konnen, mu
man naturlich zuerst die Art der moglichen Eingabefehler sowie deren Haugkeit feststellen.
Verhoeff 27] hat Ende der sechziger Jahre eine entsprechende Untersuchung
mit 6-stelligen Zahlen durchgefuhrt. Dabei wurde deutlich, da
die sogenannten
Einzelfehler, d.h. eine falsch eingegebene Zier, am haugsten vorkommt (siehe
Tabelle). Bereits mit gro
em Abstand folgt die zweithaugste Fehlerart, namlich
die Vertauschung zweier benachbarter Ziern (Zahlendreher), vor den anderen
moglichen Fehlern.
7
8
EINLEITUNG
Fehlerart
Symbol Haugkeit
1. eine falsche Zier (Einzelfehler)
x!y
79,0 %
2. Nachbarvertauschung (Vertauschung xy ! yx
10,2 %
einer Zier mit der nachsten)
3. Sprungtransposition (Vertauschung ei- xzy ! yzx
0,8 %
ner Zier mit der ubernachsten)
4. Zwillingsfehler
xx ! yy
0,6 %
5. phonetische Fehler (a = 2 ::: 9)
a0 $ 1a
0,5 %
6. Sprung-Zwillingsfehler
xzx ! yzy
0,3 %
7. sonstige/zufallige Fehler
8,6 %
Phonetische Fehler entstehen durch die Verwechslung ahnlich klingender Zahlen, zum Beispiel von "funfzig" und "funfzehn". Die Anzahl der Fehler dieses
Fehlertyps hangt naturlich
von der Sprache ab, d.h. Verhoeffs Untersuchung
gilt genaugenommen nur fur die hollandische und ahnliche Sprachen wie Deutsch
und Englisch.
Im Deutschen existiert eigentlich noch eine weitere Klasse phonetischer Fehler, denn die Zahl 35 (funf-und-drei
ig) wird hauger mit der 53 verwechselt als
z.B. im Englischen (thirty-ve). Diese Fehler werden allerdings schon durch die
Nachbarvertauschungen abgedeckt und mussen daher nicht gesondert betrachtet
werden.
In der Klasse der sonstigen und zufalligen Fehler benden sich alle sehr seltenen Fehlerarten, wie z.B. xyx ! yxy, wxyz ! xwzy oder xxxx ! yyyy, sowie Fehler, bei denen kein oensichtlicher Zusammenhang zwischen der korrekten
und der fehlerhaften Zahl besteht. Auch wenn kein oensichtlicher Zusammenhang zwischen den Zahlen besteht, kann es trotzdem eine versteckte Verbindung
geben, z.B. konnten beide Zahlen zur selben Person gehoren, eine ist seine Telefonnummer und die andere seine Kontonummer. Eine andere Moglichkeit besteht
darin, da
die korrekte Kundennummer eines anderen Kunden eingegeben wird.
Es ist unmoglich jeden dieser Fehler zu erkennen, man kann allerdings erwarten,
da
durch die Redundanz des Codes (Zahl + Prufzier) eine gro
e Anzahl der
zufalligen Fehler erkannt wird.
Eine Fehlerklasse, die nicht weiter betrachtet wird, bildet das Einfugen oder
Weglassen einzelner Ziern. Die Haugkeit dieser Fehler liegt zwischen zehn und
zwanzig Prozent, wobei die letzte Zier und die 0 am haugsten betroen sind. Es
ist also nicht sinnvoll, fehlende Nullen nach der Eingabe automatisch zu erganzen.
Ansonsten fallen fehlende Ziern anhand der abweichenden Stellenzahl auf.
Mit zunehmender Stellenzahl nimmt sowohl die relative als auch die absolute Haugkeit von (Mehrfach-)Fehlern zu. Da Verhoeff die Fehlerstatistik mit
sechsstelligen Zahlen ermittelt hat, konnen die ermittelten Zahlen im allgemeinen nur als Anhaltswerte angesehen werden. So kann, gema
Verhoeff, die
EINLEITUNG
9
Fehlerhaugkeit von Doppelfehlern (d.h. die Summe der Fehler 2-6) durchaus zwischen zehn und zwanzig Prozent schwanken. Die Fehler verteilen sich auch nicht
gleichma
ig auf die einzelnen Stellen, vielmehr sind die letzten beiden Stellen im
Vergleich mit den anderen etwa doppelt so haug betroen.
Ein weiterer Faktor, der sowohl die absolute als auch die relative Fehlerhaugkeit beeinu
t, ist die Art der Datenubertragung. Bei der U bermittlung per Telefon ist sicherlich eine andere Fehlerverteilung zu erwarten, als beim U bertragen
von hand- oder maschinengeschriebenen Texten.
10
EINLEITUNG
Kapitel 1
Prufziersysteme uber Gruppen
In diesem Kapitel werden Prufziersysteme untersucht, die auf einer vorgegebenen Gruppe basieren. Die einfachsten Verfahren sind dabei solche, die auf
den Restklassenringen Z10,Z11 usw. beruhen, die sogenannten Modulo-Verfahren.
Wir werden sehen, da
diese einige Nachteile besitzen und daher in den meisten
Fallen in der Praxis nicht benutzt werden sollten. Aus diesem Grund werden
wir Prufziersysteme basierend auf anderen Gruppen untersuchen. Da es nur
zwei Gruppen der Ordnung 10 gibt, namlich Z10 und die Diedergruppe D5, sind
Prufziersysteme basierend auf einer Diedergruppe von besonderem Interesse.
1.1 Modulo-Verfahren
Das einfachste Prufverfahren fur Zahlen mit den Ziern 0 bis 9 besteht darin, alle
Ziern zu addieren (also die Quersumme zu bilden) und dann den 10er Rest als
Prufzier anzuhangen. Fur die Zahl xm xm;1 : : : x1 mit den Ziern xi 2 Z10 wird
also die Prufzier x0 berechnet durch
x0 xm + xm;1 + : : : + x1 (mod 10)
oder, wenn man + als Gruppenoperation von Z10 ansieht,
x0 = xm + xm;1 + : : : + x1 :
Dieses Verfahren erkennt alle Einzelfehler, da sich beim A ndern einer Zier auch
die Prufzier andert. Fur die Zahl 72201 erhalt man z.B. die Prufzier 2, denn
7+2+2+0+1=12. Mit angehangter Prufzier wurde also 722012 abgespeichert.
Wenn nun spater die Zahl 722212 eingegeben wird, kann man diese Zahl als fehlerhaft erkennen, denn 7+2+2+2+1=14 ergibt die Prufzier 4 ungleich 2. Da diese
einfache Prufsumme aber nicht von der Reihenfolge der Ziern abhangt (Die Gruppe Z10 ist abelsch), wird leider keine einzige Vertauschung erkannt. Eine Eingabe
von 272012 statt 722012 kann daher nicht als falsch erkannt werden.
11
12
KAPITEL 1. PRUFZIFFERSYSTEME
UBER
GRUPPEN
Eine Erweiterung dieses Verfahrens besteht darin, die Prufzier nicht aus einer
einfachen, sondern aus einer gewichteten Summe der einzelnen Ziern zu berechnen, d.h.
x0 = am xm + am;1 xm;1 + : : : + a1 x1
mit ai 2 Z10.
Die Deutsche Post AG benutzt z.B. die Gewichte ai = 6 falls i ungerade und
ai = 1 falls i gerade ist, um den Ident- und den Leitcode der Pakete zu sichern. Mit
diesen Gewichten konnen zwar fast alle Nachbarvertauschungen erkannt werden,
aber jetzt werden nicht mehr alle Einzelfehler erkannt. Da 6 nicht teilerfremd zu 10
ist, gilt 6 5 = 6 0, d.h. es werden an allen ungeraden Positionen Verwechslungen
von 5 mit 0, 1 mit 6 und so weiter nicht erkannt.
Auch die Wahl anderer Gewichte fuhrt nicht dazu, da
sowohl alle Einzelfehler
als auch alle Nachbarvertauschungen erkannt werden. Um die Einzelfehler erkennen zu konnen, mussen die Gewichte teilerfremd zu 10 sein. Dies fuhrt aber dazu,
da
(ai ; ai;1 ) gerade ist, also ist (ai ; ai;1 ) ein Nullteiler im Ring Z10 und alle Vertauschungen der Form xm : : : xi xi;1 : : : x1 ! xm : : : xi;1 xi : : : x1 bleiben unerkannt,
wenn (xi ; xi;1) 5 (modulo 10).
Auch mit einem noch allgemeineren Ansatz, bei dem statt der Multiplikation
mit einem Element ai eine Permutation auf die einzelnen Ziern angewendet wird,
kann das Problem nicht gelost werden, denn im Abschnitt "Prufziersysteme uber
abelschen Gruppen" werden wir zeigen, da
uber der Gruppe Z10 kein Prufzierverfahren
existiert.
Die Notwendigkeit, da
sowohl die Gewichte, als auch die Dierenzen benachbarter Gewichte Einheiten sein mussen, fuhrt auf den Gedanken, eine Primzahl
als Modulus zu benutzen. Die zur 10 nachste Primzahl ist die 11, so da
beim
Rechnen in der Gruppe Z11 die Schwierigkeiten bei der Suche nach geeigneten
Gewichten zur Fehlererkennung nicht auftreten. Es reicht vielmehr aus, da
benachbarte Gewichte verschieden sind und im Bereich von 1 bis 10 liegen, um alle
Einzelfehler und Nachbarvertauschungen zu erkennen.
Ein bekanntes Beispiel einer Modulo-11-Prufung stellen die Internationalen
Standard Buchnummern (ISBN) dar. Eine ISBN hat zehn Ziern x10 : : : x1 und
setzt sich aus vier Abschnitten zusammen, von denen der erste das Land, der zweite den Verlag und der dritte das Buch kennzeichnet. Zuletzt folgt eine Prufzier,
x1 , die durch die Gleichung
10x10 + 9x9 + 8x8 + : : : + 2x2 + x1 = 0
bestimmt wird. Eine gultige ISBN ist z.B. 3-411-04011-4, beim Nachrechnen erhalt
man: 3 10 + 4 9 + 1 8 + : : : + 1 1 + 4 = 110 0 (mod 11).
Das Modulo-11-Verfahren mit den Gewichten 2i erkennt sogar alle nicht zufalligen
Fehler, da die 2 eine primitive zehnte Einheitswurzel ist (vgl. Verhoeff 27]).
1.2. VERALLGEMEINERUNG AUF BELIEBIGE GRUPPEN
13
Ein gravierender Nachteil bei den Modulo-11-Verfahren ist, da
beim Rechnen der Rest (die Prufzier) 10 heraus kommen kann. Es gibt verschiedene
Moglichkeiten, mit diesem Problem umzugehen. Man kann etwa bei einem Rest
von 10 ein nicht-numerisches Zeichen als Ersatz nehmen. So wird z.B. bei den
ISBN-Prufziern ein 'X' als elfte Zier benutzt. Eine weitere Moglichkeit besteht
darin, alle Zahlen, bei denen als Prufzier die 10 entsteht, nicht zu verwenden.
Laut Ecker und Poch 9] verfahrt die Dresdner Bank auf diese Weise.
Im Normalfall sollen die Prufziern allerdings aus den gleichen Ziern bestehen,
wie die zu sichernde Zahl. Haug mochte man auch nicht auf eine fortlaufende
Vergabe der Zahlen verzichten, abgesehen davon, da
die Redundanz durch das
Weglassen einiger Zahlen deutlich erhoht wird. In den meisten Fallen ist daher das
Modulo-11-Verfahren unbrauchbar. Als Alternative bietet sich die zweite Gruppe
mit 10 Elementen an, namlich die Diedergruppe. Prufzierverfahren basierend auf
Diedergruppen bieten ebenfalls eine sehr gute Fehlererkennung, z.B. werden die
Seriennummern deutscher Banknoten mit diesen gesichert. Wir behandeln diese
im Kapitel "Gruppen mit Vorzeichen".
1.2 Verallgemeinerung auf beliebige Gruppen
Bei den Modulo-Verfahren wird von den Restklassenringen Z10, Z11 usw. im wesentlichen nur die additive Gruppe benotigt. Die Multiplikation dient nur dazu,
eine Permutation der Ziern zu erzeugen. Fur beliebige Gruppen ist es daher
sinnvoll, folgende Denition zu treen (vergleiche Schulz 21]):
Denition 1 Sei (G ) eine endliche Gruppe der Ordnung n und m 2 eine fest
gewahlte ganze Zahl. Dann ist ein Prufziersystem uber der Gruppe G deniert
durch ein Element c 2 G und m + 1 Permutationen m : : : 0 der Grundmenge
G, mit der Eigenschaft i i;;11(x) y = i i;;11(y) x ) x = y, fur i = 1 : : : m
und alle x y 2 G. Zu jeder Zahl xm xm;1 : : : x1 wird eine Prufzier x0 hinzugefugt,
welche die Kontrollgleichung
m (xm ) m;1 (xm;1 ) : : : 1(x1 ) 0 (x0 ) = c
erfullt.
Lemma 1
1. Fur gegebene xm xm;1 : : : x1 ist die Prufzier x0 eindeutig durch
die Kontrollgleichung bestimmt.
2. Jedes Prufziersystem uber einer Gruppe erkennt alle Einzelfehler und alle
Nachbarvertauschungen.
KAPITEL 1. PRUFZIFFERSYSTEME
UBER
GRUPPEN
14
Beweis zu 1: Da 0 eine Permutation ist, ist die Kontrollgleichung eindeutig nach
x0 auosbar:
x0 = 0;1 (1 (x1 );1 : : : m;1 (xm;1 );1 m (xm );1 c):
zu 2: Wenn wir annehmen, da
sowohl xm : : : xi : : : x0 als auch xm : : : x0i : : : x0 die
Kontrollgleichung erfullt, dann folgt m (xm ) : : : i (xi) : : : 0 (x0 ) = c = m (xm ) : : : i (x0i) : : : 0(x0 ). Nun konnen sowohl links als auch rechts gleiche Elemente
gekurzt werden und es folgt i (xi) = i(x0i ) und damit xi = x0i . Fur xi 6= x0i konnen
also nicht beide Zahlen xm : : : xi : : : x0 und xm : : : x0i : : : x0 die Kontrollgleichung
erfullen, es werden somit alle Einzelfehler erkannt.
Ebenso zeigen wir, da
alle Vertauschungen benachbarter Elemente erkannt
werden. Gilt namlich m(xm ) : : : i(xi ) i;1(xi;1 ) : : : 0 (x0 ) = c = m (xm ) : : : i (xi;1 ) i;1 (xi) : : : 0 (x0 ), so folgt, nach kurzen der gleichen Elemente auf
beiden Seiten, i (xi) i;1(xi;1 ) = i (xi;1) i;1(xi ). Wir setzen yi;1 := i;1 (xi;1 )
und yi := i;1 (xi), womit i(i;;11 (yi)) yi;1 = i (i;;11(yi;1)) yi folgt. Nach Voraussetzung ist damit yi = yi;1, also i;1(xi;1 ) = i;1 (xi ) und xi;1 = xi. Folglich
werden alle Nachbarvertauschungen erkannt. 2
Bemerkung Es ist fur die Erkennung aller Einzelfehler erforderlich, da
die i
Permutationen sind. Ebenso ist die Forderung i i;;11 (x)y = i i;;11 (y)x ) x = y
nicht nur hinreichend, sondern auch notwendig fur die Erkennung aller Nachbarvertauschungen. Gibt es namlich ein i und x 6= y mit i i;;11 (x) y = i i;;11 (y) x,
dann gilt fur xi := i;;11(x) und xi;1 := i;;11 (y) die Gleichung i (xi) i;1 (xi;1 ) =
i (xi;1 ) i;;11(xi ) und xi 6= xi;1. Damit erfullen aber die Zahlen xm : : : xixi;1 : : : x0
und xm : : : xi;1 xi : : : x0 die Kontrollgleichung, d.h. es werden nicht alle Nachbarvertauschungen erkannt.
Fur weitere Fehlertypen ndet man folgende Bedingungen, die fur alle x y z 2
G und alle i erfullt sein mussen:
Fehlertyp
Sprungtranspositionen
Zwillingsfehler
Sprungzwillingsfehler
phonetische Fehler
Bedingungen fur die Fehlererkennung
i+1 i;;11 (x) z y = i+1 i;;11(y) z x
impliziert x = y
i i;;11 (x) x = i i;;11(y) y impliziert
x=y
i+1 i;;11 (x) z x = i+1 i;;11 (y) z y
impliziert x = y
Fur a = 2 : : : n ; 1 gilt i+1(a)i (0) 6=
i+1(1)i(a)
1.3. PRUFZIFFERSYSTEME
UBER
ABELSCHEN GRUPPEN
15
Die Bedingungen werden ahnlich wie im obigen Lemma gezeigt. Wir verzichten
daher auf einen Beweis.
Da diese Fehlertypen nur sehr selten auftauchen, werden wir uns im folgenden
vorrangig mit dem Erkennen der Einzelfehler und der Nachbarvertauschungen
beschaftigen. Wie wir sehen, spielen die Permutationen ', bei denen aus '(x) y =
'(y) x die Gleichheit von x und y folgt, eine wichtige Rolle. Diese werden antisymmetrisch genannt (vgl. Kapitel 2). Sie sind erforderlich fur die Existenz eines
Prufziersystems uber einer Gruppe. Andererseits kann man mit ihnen auch ein
Prufziersystem denieren.
Satz 1 (vgl.
H.P. Gumm 12]) Sei ' eine anti-symmetrische Permutation der
Gruppe G, dann wird durch i := 'i, ein beliebiges Element c
Kontrollgleichung
2 G sowie der
'm(xm ) 'm;1(xm;1 ) : : : '(x1 ) x0 = c
ein Prufziersystem deniert.
Beweis Es ist i i;;11 = 'i ';i+1 = ' und ' erfullt nach Voraussetzung die
geforderte Bedingung. 2
1.3 Prufziersysteme uber abelschen Gruppen
In abelschen Gruppen stehen die anti-symmetrischen Abbildungen in direkter Beziehung zu den von Mann 15] 1942 eingefuhrten vollstandigen Abbildungen. Eine
Permutation ' hei
t vollstandig, wenn x '(x) = y '(y) impliziert, da
x = y
ist (also wenn x '(x) wieder eine Permutation ist). Mit Hilfe der vollstandigen
Abbildungen ist es moglich, orthogonale lateinische Quadrate zu konstruieren.
Lemma 2 Eine abelsche Gruppe (G +) besitzt eine vollstandige Abbildung genau
dann, wenn sie eine anti-symmetrische Abbildung besitzt.
Beweis Es gilt fur alle x y 2 G: '(x) + y = '(y) + x , x ; '(x) = y ; '(y).
Damit folgt, wenn inv die Abbildung x 7! ;x bezeichnet,
' anti-symmetrisch , inv ' vollstandig
und
' vollstandig , inv (inv ') vollstandig , inv ' anti-symmetrisch: 2
Die Frage, wann eine endliche abelsche Gruppe eine vollstandige Abbildung
besitzt, wurde von Paige 1947 gelost.
16
KAPITEL 1. PRUFZIFFERSYSTEME
UBER
GRUPPEN
Theorem 1 ( Paige 18]) Eine endliche abelsche Gruppe der Ordnung n besitzt
eine vollstandige und damit eine anti-symmetrische Abbildung genau dann, wenn
n ungerade ist oder wenn G mindestens zwei verschiedene Involutionen enthalt
(also die 2-Sylowgruppe von G nicht zyklisch ist).
Beweis 1) Falls n ungerade ist, dann ist ' = (x 7! 2x) eine anti-symmetrische
Permutation, denn aus 2x = 2y oder aus x + x + y = y + y + x folgt direkt x = y.
2) Der Fall n gerade wird konstruktiv bewiesen. Um den Beweis des Theorems zu
vereinfachen, zeigen wir allerdings zunachst einige Lemmata.
Im folgenden sei n = n(G) die Ordnung der Gruppe G und die Summe aller
Elemente der Gruppe werde mit p = p(G) bezeichnet, d.h.
p(G) =
X
x2G
x:
Weiterhin sei eine Permutation von G und = (x 7! x + (x)) eine abgeleitete Abbildung. Die Ordnung von , bezeichnet mit O(), sei die Anzahl der
verschiedenen Elemente (x), fur x 2 G.
Lemma 3 Wenn G nicht genau ein Element der Ordnung 2 besitzt, dann ist
p(G) = 0, ansonsten ist p(G) das einzige Element der Ordnung 2.
Beweis Sei S die eindeutig bestimmte Untergruppe, die aus dem neutralen Ele-
ment und allen Elementen der Ordnung 2 der Gruppe G besteht. Wenn die Ordnung von a 2 G gro
er als 2 ist, dann ist a 6= ;a und deshalb kommen a und ;a
in der Summe p(G) vor, folglich gilt p(G) = p(S ).
Hat S die Ordnung 1, dann ist p(S ) = 0. Hat S die Ordnung 2, d.h. S = f0 gg,
dann ist p(S ) = 0 + g = g und p(S ) ist das einzige Element von S (und damit
auch von G) der Ordnung 2.
Es bleibt der Fall, da
die Ordnung von S gro
er als 2 ist. Dann hat S die
Ordnung 2k , k > 1 und die k Erzeugenden g1 : : : gk . Jedes Element von S hat
eine eindeutige Darstellung
der Form n1 g1 + n2g2 + : : : + nk gk mit ni 2 f0 1g.
P
Folglich ist p(S ) = (n1 g1 + n2 g2 + : : : + nk gk ), wobei uber die verschiedenen
Tupel (n1 : : : nk ) mit ni 2 f0 1g summiert wird. Es gibt 2k solche Tupel, wobei an jeder Position der Wert 0 genau 2k =2 = 2k;1-mal vorkommt. Also ist
p(S ) = 2k;1 (g1 + : : : + gk ) und weil k > 1 ist, erhalten wir p(S ) = 0. 2
Lemma 4 Eine notwendige Bedingung fur O() = n(G) ist, da
p(G) = 0.
Korollar 1 Wenn p(G) 6= 0 ist, dann ist O() < n(G) fur alle Permutationen .
1.3. PRUFZIFFERSYSTEME
UBER
ABELSCHEN GRUPPEN
17
Beweis Angenommen, es existiert eine Permutation mit O() = n(G), d.h. ist ebenfalls eine Permutation. Die Elemente von G werden mit xi bezeichnet
(i = 1 2 : : : n). Es ist
n
X
i=1
(xi ) =
n
X
n
X
i=1
i=1
(xi + (xi )) =
xi +
n
X
i=1
(xi)
und es folgt, da und bijektiv sind, p = p + p bzw. p = 0. 2
Lemma 5 Wenn fur ein O() n ; 2, wobei n = n(G), dann existiert ein 0
mit O(0) > O( ).
Korollar 2 Es existiert ein mit O() n(G) ; 1.
Beweis Sei eine Permutation fur die O() = r n ; 2 gilt. Die Elemente
von G werden mit xi, i = 1 : : : n, bezeichnet, dabei seien (xi ), i = 1 : : : r
die r verschiedenen Elemente von (x) mit x 2 G. Existieren h k > r mit xh +
(xk ) 6= (xi ) fur alle i r, dann wird das Problem gelost durch 0(xh ) := (xk ),
0 (xk ) := (xh) und 0(x) := (x) sonst. Also nehmen wir an, da
dies nicht der
Fall sei.
Da (xr+1) = (xi) fur ein i r, konnen wir ohne Beschrankung der Allgemeinheit annehmen, da
(xr+1) = (x1 ) ist. Ist x1 + (xr+2) 6= (xi), fur alle
i r, dann konnen wir 0(x1 ) := (xr+2), 0(xr+2 ) := (x1 ) und 0(x) := (x) sonst
setzen, um ein 0 mit O(0) > r zu konstruieren (wenigstens sind dann die Elemente 0(x1 ) : : : 0(xr+1 ) paarweise verschieden). Aber wenn x1 + (xr+2 ) = (xi)
fur ein i r gilt, dann konnen wir o.B.d.A. annehmen, da
x1 + (xr+2) = (x2 )
(i 6= 1, denn x1 + (xr+2) 6= x1 + (x1 ) = (x1 )).
Es gilt x2 + (x1 ) 6= (x1) (x2 ). Wenn x2 + (x1) 6= (xi ), fur alle i r,
konnen wir andern durch 0(x1 ) := (xr+2), 0(x2 ) := (x1 ), 0(xr+2 ) := (x2 )
und wir erhalten ein 0 mit O(0) > r (auch hier sind wenigstens die Elemente 0(x1) : : : 0(xr+1 ) paarweise verschieden). Andernfalls konnen wir ohne Einschrankung der Allgemeinheit annehmen, da
x2 + (x1) = (x3) ist.
In dieser Weise fahren wir fort: Nehmen wir an, wir hatten die Stelle erreicht,
wo
x1 + (xr+2 ) = (x2)
xi+1 + (xi) = (xi+2 )
i = 1 2 ::: k
(1.1)
gilt. Hieraus erhalten wir die Gleichungen
(x1) + (xr+2 ) = (xi+1) + (xi )
i = 1 2 : : : k + 1:
(1.2)
Dies zeigen wir durch Induktion: Es ist (x1 ) + (xr+2 ) = x1 + (x1 ) + (xr+2 ) =
x1 + (xr+2) + (x1) = (x2) + (x1) und fur 1 j k gilt (xj+1) + (xj ) =
xj+1 + (xj+1) + (xj ) = xj+1 + (xj ) + (xj+1) = (xj+2) + (xj+1).
KAPITEL 1. PRUFZIFFERSYSTEME
UBER
GRUPPEN
18
Nun gilt xk+2 + (xk+1) 6= (xi) fur alle i k +2, denn andernfalls folgt mit 1.2
(xi ) + (xk+2 ) = xk+2 + (xk+1) + (xk+2) = (xk+2) + (xk+1) = (xi) + (xi;1 ),
bzw. (xk+2) = (xi;1 ), was unmoglich ist, da i k + 2.
Ist xk+2 + (xk+1 ) 6= (xi ) fur alle i r, dann setzen wir 0 (x1) := (xr+2 ),
0 (xi+1) := (xi), i = 1 2 : : : k + 1, 0(xr+2 ) := (xk+2) und erhalten eine Permutation 0 mit O(0) > r.
Gilt dagegen xk+2 + (xk+1 ) = (xi) fur ein i r, dann konnen wir o.B.d.A.
annehmen, da
i = k+3 gilt und wir konnen die Gleichung xk+2+(xk+1 ) = (xk+3)
zu den Gleichungen 1.1 dazunehmen. In jedem Fall erreichen wir, da O() endlich
ist, eine Summe xj + (xj;1) 6= (xi) fur alle i r. Damit ist der Beweis des
Lemmas abgeschlossen. Das Korollar ist oensichtlich. 2
Wir zeigen nun den verbleibenden Fall des Theorems.
Sei die Ordnung von G gerade (d.h. G hat wenigstens ein Element der Ordnung
2). Besitzt G eine vollstandige Abbildung, dann folgt mit Lemma 4, da
n(G) = 0
ist und mit Lemma 3, da
G mindestens zwei Elemente der Ordnung 2 besitzt.
Hat G wenigstens zwei Involutionen, dann ist p = p(G) = 0. Durch das
Korollar konnen wir annehmen, da
eine Permutation existiert mit O() n ; 1.
Mit (xi), i = 1 : : : n;1 bezeichnen wir n;1 Elemente, die paarweise verschieden
sind und mit z das verbleibende Element der Gruppe. Dann gilt
n;1
X
n;1
X
i=1
i=1
(xi + (xi )) =
(xi ):
Wir erhalten p ; xn + p ; (xn) = p ; z und damit xn + (xn) = z, also ist O() = n
und G besitzt die vollstandige Abbildung . 2
Im folgenden geben wir einige Ergebnisse von Siemon 23] wieder:
Satz 2 ( Siemon)
1. Die identische Abbildung x 7! x einer endlichen Gruppe der Ordnung n ist
genau dann vollstandig, wenn n ungerade ist.
2. Ist Zn eine zyklische Gruppe der Ordnung n, dann ist die durch f (x) :=
xk denierte Abbildung genau dann vollstandig, wenn ggT (k n) = 1 und
ggT (k + 1 n) = 1.
Beweis zu 1) Sei n ungerade, n = 2k + 1, dann gilt x2k+2 = x = (xk+1)2 also ist
x2 surjektiv und, da G endlich ist, damit auch injektiv. Folglich ist x 7! x eine
vollstandige Abbildung.
Ist dagegen n gerade, dann besitzt G ein Element a der Ordnung 2, somit ist
2
a = e = e2 und x2 ist nicht injektiv, also auch keine Permutation.
1.3. PRUFZIFFERSYSTEME
UBER
ABELSCHEN GRUPPEN
19
zu 2) Die Eigenschaft ggT (k n) = 1 bzw. ggT (k + 1 n) = 1 ist aquivalent zu xk
bzw. xk+1 injektiv. Daraus folgt die Behauptung. 2
Bemerkung
1. Ist ggT (k n) = 1, dann ist die Abbildung f (x) := xk ein Automorphismus
von Zn.
2. Fur n gerade gibt es kein k das die Bedingung ggT (k n) = ggT (k +1 n) = 1
erfullt, denn entweder ist k oder k + 1 gerade.
Theorem 2 ( Siemon) Eine Gruppe G der Ordnung n = 4k + 2, k 1, besitzt
keine vollstandige Abbildung und, falls G abelsch ist, auch keine anti-symmetrische
Abbildung.
Mit etwas mehr Theorie konnen wir den Beweis von Siemon deutlich verkurzen,
wir verschieben ihn daher auf den Abschnitt "Gruppen mit Vorzeichen".
Korollar 3 Eine zyklische Gruppe Zn der Ordnung n besitzt eine vollstandige bzw.
anti-symmetrische Abbildung genau dann, wenn n ungerade ist.
Beweis Der Fall n ungerade wurde bereits gezeigt. Ist n gerade, dann ist n=2 das
einzige Element der Ordnung 2 in Zn, also besitzt Zn keine vollstandige Abbildung.
Korollar 4 Uber den Gruppen Z2k, k 1, insbesondere uber Z10, existiert kein
Prufziersystem.
Uber Gruppen der Ordnung n = 4k + 2, k 1 existiert kein Prufziersystem, das
alle Zwillings- oder Sprungzwillingsfehler erkennt.
Die Gruppe Z10 eignet sich also grundsatzlich nicht dazu, ein Prufziersystem
zu denieren. Fur die Erkennung der Zwillings- und Sprungzwillingsfehler benotigen wir eine vollstandige Abbildung (siehe Tabelle Seite 14, i;1 i;1 bzw. z i;1 i;+11 sind vollstandige Abbildungen), daher konnen diese Fehler in Gruppen
der Ordnung n = 4k + 2, insbesondere n = 10, nicht erkannt werden.
Fur den nicht abelschen Fall ist bislang noch keine vollstandige Losung bekannt. 1950 bewies Batemann 2], da
alle unendlichen Gruppen eine vollstandige
Abbildung besitzen. Also haben alle unendlichen abelschen Gruppen eine antisymmetrische Abbildung. Hall und Paige 14] haben 1955 gezeigt, da
in Sn
(n > 3), An (n > 3) und auosbaren Gruppen mit nicht-zyklischer 2-Sylowgruppe
eine vollstandige Abbildung existiert. Sie zeigten au
erdem, da
eine endliche
Gruppe mit zyklischer 2-Sylowgruppe keine vollstandige Abbildung besitzt und
vermuteten, da
in jeder endlichen Gruppe mit nicht-zyklischer 2-Sylowgruppe
eine vollstandige Abbildung existiert.
20
KAPITEL 1. PRUFZIFFERSYSTEME
UBER
GRUPPEN
Wir werden spater zeigen, da
die Diedergruppe D5 mit 10 Elementen eine
anti-symmetrische Abbildung besitzt. Nach Theorem 2 besitzt sie aber keine
vollstandige Abbildung, d.h. im nicht abelschen Fall unterscheiden sich die beiden
Begrie voneinander.
Zum Abschlu
dieses Abschnittes sei noch angemerkt, da
man auf dem direkten Produkt G1 G2 der Gruppen G1 und G2 (nicht notwendig abelsch) mit
den vollstandigen Abbildungen g1 und g2 in naturlicher Weise eine vollstandige
Abbildung denieren kann.
Lemma 6 Sind g1, g2 vollstandige Abbildungen der Gruppen G1 bzw. G2, dann
ist f = (x y ) 7! (g1(x) g2 (y )) eine vollstandige Abbildung von G1 G2.
Beweis Da
f bijektiv ist, ergibt sich aus der Bijektivitat von g1 und g2. Ebenso
folgt aus der Vollstandigkeit von g1 und g2, da
(x y) f (x y) = (x g1(x) y g2(y))
eine Permutation und damit vollstandig ist. 2
Kapitel 2
Anti-symmetrische Abbildungen
Eine Gruppe la
t die Denition eines Prufziersystems genau dann zu, wenn sie
eine anti-symmetrische Abbildung besitzt (siehe Kapitel 1). In diesem Kapitel
beschaftigen wir uns daher ausfuhrlich mit der Existenz, den Eigenschaften und
der Konstruktion von anti-symmetrischen Abbildungen.
Denition 2 ( Gallian 10]) Eine Permutation ' einer Gruppe (G ) hei
t anti-
symmetrisch, wenn fur alle x y 2 G gilt
'(x) y = '(y) x
)
x = y:
Die Menge aller anti-symmetrischen Abbildungen einer Gruppe G werde mit Ant(G)
bezeichnet.
Bemerkung Ant(G) ist fur eine Gruppe G der Ordnung n > 1 keine Untergruppe
von Sn, da die Identitat nicht anti-symmetrisch ist. Es gilt namlich fur beliebige
x 6= e
Id(x) e = x e = e x = Id(e) x:
Aus der Eigenschaft '(x) y = '(y) x ) x = y folgt nicht, da
' injektiv ist,
z.B. wird sie von '(x) := e erfullt. Da solche Funktionen nicht alle Einzelfehler
erkennen, meinen wir mit dem Begri "anti-symmetrische Abbildung" daher immer eine anti-symmetrische Permutation.
In der Literatur (z.B. Verhoeff 27]) wird der Begri "anti-symmetrisch"
auch fur Permutationen mit der Eigenschaft y '(x) = x '(y) ) x = y benutzt.
Diese konnen aber bijektiv auf die anti-symmetrischen Permutationen gema
Denition 2 abgebildet werden:
Lemma 7 Ist ' eine Permutation mit y '(x) = x '(y) ) x = y, dann ist ';1
anti-symmetrisch.
21
22
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
Beweis Es gelte ';1 (x) y = ';1(y) x. Wir setzen x~ := ';1(x) y~ := ';1(y) und
es folgt x~ '(~y) = y~ '(~x). Nach Voraussetzung ist damit x = y. 2
2.1 Gruppen mit anti-symmetrischen
Abbildungen
In diesem Abschnitt prasentieren wir eine Arbeit von Gallian und Mullin
10], welche sich mit der Existenz anti-symmetrischer Abbildungen beschaftigt.
In Kapitel 1 haben wir den direkten Zusammenhang zwischen vollstandigen und
anti-symmetrischen Abbildungen bei abelschen Gruppen gezeigt. Diese Arbeit
ubertragt die wesentlichen Ergebnisse von Hall und Paige 14] bzgl. vollstandiger
Abbildungen bei nicht-abelschen Gruppen auf anti-symmetrische Abbildungen.
2.1.1 Beispiele
Denition 3 Unter der Diedergruppe der Ordnung 2n versteht man die Gruppe
Dn = fe a a2 : : : an;1 b ba ba2 : : : ban;1 g, wobei a b zwei erzeugende Elemente sind, die den Relationen an = e (und am 6= e fur 1 m < n), b2 = e 6= b
und ab = ba;1 genugen. (Abkurzende Schreibweise: Dn =< a bjan = b2 = e ab =
ba;1 >).
Theorem 3 Die folgenden Gruppen besitzen anti-symmetrische Abbildungen:
1. Dn =< a bjan = b2 = e ab = ba;1 >, n 3 (die Diedergruppe der Ordnung
2n )
2. Qn =< a bja2n = b4 = e b2 = an ab = ba;1 >, n 2
(die verallg. Quaternionengruppe der Ordnung 4n)
3. SDn+ =< a bja4n = b2 = e ab = ba2n+1 >, n gerade (Semi-Diedergruppe der
Ordnung 8n)
4. SDn; =< a bja4n = b2 = e ab = ba2n;1 >, n gerade (Semi-Diedergruppe der
Ordnung 8n)
Beweis 1) Die folgende Abbildung ist anti-symmetrisch: Wenn n ungerade ist,
sei '(ai) = a2;i und '(bai) = bai . Wenn n gerade ist, d.h. n = 2k, wird ' deniert
durch:
'(e) = b '(a) = e
'(ai) = a1;i fur 2 i k
'(ai ) = ba1;i fur k + 1 i n ; 1
'(bai) = ai+1 fur 0 i k ; 1 '(bai ) = bai+1 fur k i n ; 2
'(ban;1) = ba
2.1. GRUPPEN MIT ANTI-SYMMETRISCHEN ABBILDUNGEN
23
2) Wir denieren ' durch
'(e) = e '(ai) = ba;i fur 1 i n
'(ai) = a;i fur n + 1 i 2n ; 1
'(bai) = bai+1 fur 0 i n ; 2
'(bai) = ai+1 fur n ; 1 i 2n ; 2 '(ba2n;1 ) = b
3) Wir denieren ' durch
'(ai) = a4n;1;i fur 0 i 2n ; 1
'(ai) = ba4n;1;i fur 2n i 4n ; 1
'(bai ) = ba4n;i fur 1 i 2n
'(b) = e
'(bai ) = a4n;i fur 2n + 1 i 4n ; 1
4) Wir denieren ' durch
'(ai ) = a4n;1;i fur 0 i 2n ; 1
'(ai ) = ba4n;1;i fur 2n i 4n ; 1
'(bai ) = ai fur 0 i 2n ; 1
'(bai ) = bai fur 2n i 4n ; 1
zu 1) Da
die genannte Permutation fur ungerades n anti-symmetrisch ist, zeigen
wir im Abschnitt "Beispiele", Seite 58. Im Fall n gerade mussen wir eine Vielzahl
verschiedener Falle unterscheiden. Dazu sei 0 i k ; 1 und k j n ; 2. Wir
zeigen exemplarisch '(x)y 6= '(y)x fur einige x 6= y.
x
e
e
e
a.
b.
c.
d. ai+1
e. baj
y
ai+1
aj+1
bai
baj
ban;1
'(x)y
bai+1
baj+1
ai
a;ibaj = baj+i
baj+1 ban;1 = an;j;2
6=
6=
6=
6
=
6
=
'(y)x
a;i
ba;j
ai+1
baj+1 ai+1
babaj = aj;1
Bei b. folgt aus j + 1 = n ; j die Gleichung 2j + 1 = 2k, Widerspruch (da n
gerade). Bei d. konnen die beiden Seiten nur gleich sein, falls n = 2 ist. Dann
kommt dieser Fall allerdings nicht vor, da kein j existiert mit 1 j 0. Und
schlie
lich folgt bei e. aus n ; j ; 2 = j ; 1 die Gleichung 2k ; 1 = 2j , Widerspruch.
Die anderen Falle und Behauptungen konnen analog gezeigt werden. 2
24
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
2.1.2 Existenztheoreme
Theorem 4 Sei G eine Gruppe und a ein Element von G. Die Abbildung '(x) =
x;1 a ist genau dann anti-symmetrisch, wenn a mit keinem Element der Ordnung
2 kommutiert.
Beweis Sei '(x) = x;1 a anti-symmetrisch. Oensichtlich ist ' fur jedes a eine
Permutation. Es ist also ausreichend zu untersuchen fur welche a gilt: x 6= y )
'(x)y 6= '(y)x. Angenommen es existieren verschiedene x und y s.d. '(x)y =
'(y)x oder aquivalent dazu x;1ay = y;1ax gilt. Multiplikation von links mit y
und von rechts mit x;1 ergibt
(yx;1)a(yx;1) = a:
(2.1)
Wir setzen z := yx;1. Es folgt a2 z = zazaz = za2 und mit Induktion
a2n z = za2n
fur alle n
(2.2)
Wenn die Ordnung von a gerade ist, z.B. 2m, dann hat am die Ordnung 2 und
kommutiert mit a. Wenn andererseits die Ordnung von a ungerade, d.h. 2k + 1
ist, dann folgt mit 2.2:
za = za2(k+1) = a2(k+1) z = az
Also kommutiert z mit a. Benutzt man diese Eigenschaft zusammen mit 2.1, dann
erhalt man
zaz = z2 a = a:
Folglich hat z = yx;1 die Ordnung 2 und kommutiert mit a. Dies zeigt, da
'(x) := x;1a eine anti-symmetrische Abbildung ist, wenn a mit keinem Element
der Ordnung 2 kommutiert.
Um den Beweis abzuschlie
en, nehmen wir an, da
a mit einem Element z der
Ordnung 2 kommutiert. Es folgt, da
'(x) := x;1 a nicht anti-symmetrisch ist,
denn es gilt:
und z 6= e. 2
'(z)e = z;1 a = za = az = e;1az = '(e)z
Korollar 5 Alle Gruppen mit ungerader Ordnung besitzen eine anti-symmetrische
Abbildung.
Beweis Da eine Gruppe mit ungerader Ordnung kein Element der Ordnung 2
besitzt, ist '(x) := x;1a eine anti-symmetrische Abbildung fur alle a. 2
2.1. GRUPPEN MIT ANTI-SYMMETRISCHEN ABBILDUNGEN
25
Korollar 6 Fur alle n > 2 besitzen die symmetrischen Gruppen Sn und die alter-
nierenden Gruppen An anti-symmetrische Abbildungen.
Beweis Wenn n ungerade ist, ist jeder n-Zykel in An und kommutiert mit keinem
Element der Ordnung 2. Ist n gerade so gilt dies fur jeden (n ; 1)-Zykel. 2
Korollar 7 Wenn eine endliche Gruppe ein Element a besitzt, dessen Zentralisa-
tor Z (a) ungerade Ordnung hat, dann besitzt die Gruppe eine anti-symmetrische
Abbildung.
Beweis Wenn die Ordnung von Z (a) = fx 2 Gjxa = axg ungerade ist, dann
kommutiert a mit keinem Element der Ordnung 2. 2
2.1.3 Erweiterungstheoreme
Theorem 5 Sei G eine Gruppe mit Normalteiler H und es existieren anti-sym-
metrische Abbildungen ' auf H und auf G=H , dann existiert eine anti-symmetrische Abbildung auf G. Kurz gesagt: Die Klasse der Gruppen mit antisymmetrischen Abbildungen ist gegen Erweiterung abgeschlossen.
Beweis Seien u1H : : : ur H die Elemente von G=H . Wir denieren die Abbildung : fu1 : : : ur g ! fu1 : : : ur g durch die Bedingung
(ui)H = (uiH ):
(2.3)
Da jedes Element von G eindeutig als Produkt g = hu geschrieben werden
kann, wobei h 2 H und u = ui fur ein i, ist die Abbildung : G ! G, (g) =
(hu) := (u)'(h) wohldeniert. Wir zeigen nun, da
anti-symmetrisch ist.
Seien g = hu und g0 = h0u0 Elemente von G, dann folgt aus (g)g0 = (g0)g:
(u)'(h)h0u0 = (u0)'(h0)hu:
(2.4)
Durch Multiplikation mit H erhalt man (u)Hu0H = (u0)HuH . Mit 2.3 folgt
(uH )u0H = (u0H )uH und damit, weil anti-symmetrisch ist, uH = u0H bzw.
u = u0, da die Reprasentanten fest gewahlt sind. Nun wird aus 2.4 die Gleichung
(u)'(h)h0u = (u)'(h0)hu:
Nach kurzen von (u) und u bleibt die Gleichung '(h)h0 = '(h0 )h, woraus, wegen
der Anti-Symmetrie von ', h = h0 folgt und insgesamt g = g0. Also ist eine antisymmetrische Abbildung. 2
Denition 4 ( 3]) Seien (G ;1 e) und (X + ; 0) Gruppen und : G
!
Aut(X ) ein Gruppenhomomorphismus. Das semi-direkte Produkt von X und G
relativ zu wird deniert durch:
X G = f(x a)jx 2 X a 2 Gg
26
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
mit der Operation (x1 a1 )(x2 a2 ) = (x1 + (a1)x2 ] a1 a2), fur x1 x2
a1 a2 2 G.
Proposition 1
2 X und
1. Das semi-direkte Produkt X G ist eine Gruppe.
2. Die Menge f(x a) 2 X Gjx = 0g ist eine Untergruppe von X G, welche
isomorph zu G ist.
3. Die Menge N = f(x a) 2 X Gja = eg ist ein Normalteiler von X G,
die isomorph zu X ist und (X G)=N ist isomorph zu G.
Beweis zu 3.: Es ist klar, da
X isomorph zu N ist. Deniere ' : X G ! G
durch '(x a) = a, dann ist ' ein Homomorphismus mit '(X G) = G und
Kern(') = N . Der Homomorphiesatz zeigt nun (X G)=N = G. 2
Korollar 8 Wenn A und B Gruppen mit anti-symmetrischen Abbildungen sind
und : G ! Aut(X ) ein Gruppenhomomorphismus ist, dann besitzt das semidirekte Produkt A B eine anti-symmetrische Abbildung.
Beweis A B hat eine Untergruppe isomorph zu A und die Faktorgruppe (A B )=A ist isomorph zu B . Mit dem Erweiterungstheorem folgt nun die Behauptung.
Korollar 9 Sind A und B Gruppen mit anti-symmetrischen Abbildungen, dann
besitzt das direkte Produkt A B eine anti-symmetrische Abbildung.
Beweis Spezialfall vom vorherigen Korollar, wobei alle Elemente auf die Identitat abbildet.
2.1.4 Einfache Gruppen
Die einfachen Gruppen spielen angesichts Theorem 5 eine entscheidende Rolle bei
der Bestimmung der endlichen Gruppen mit anti-symmetrischen Abbildungen. Die
Klassikation der einfachen Gruppen (Gorenstein 11]) zeigt, da
jede endliche
einfache Gruppe von einem der folgenden Typen ist: eine zyklische Gruppe mit
Primzahlordnung, eine alternierende Gruppe, ein Mitglied einer von sechzehn Familien vom Lie-Typ oder eine von 26 sporadischen Gruppen.
Theorem 6 Jede endliche einfache Gruppe, au
er Z2, besitzt eine anti-symmet-
rische Abbildung.
Beweis Die zyklischen und alternierenden Gruppen werden von Korollar 5 und
Korollar 6 abgedeckt. Mit dem Atlas der endlichen Gruppen 7] kann man verizieren, da
in allen 26 sporadischen einfachen Gruppen der Zentralisator der Elemente
mit maximaler Primzahlordnung ungerade Ordnung hat und diese Gruppen daher
eine anti-symmetrische Abbildung besitzen (Korollar 7). Korollar 7 kann auch
2.1. GRUPPEN MIT ANTI-SYMMETRISCHEN ABBILDUNGEN
27
auf die Lie-Gruppen angewendet werden, da Lyons, Solomon und Seitz 10,
Gallian] gezeigt haben, da
jede einfache Lie-Gruppe ein Element besitzt, dessen
Zentralisator ungerade Ordnung hat. 2
2.1.5 Verallgemeinerte Diedergruppen
Denition 5 Sei G eine abelsche Gruppe. Die verallgemeinerte Diedergruppe
dih(G) wird deniert durch das semi-direkte Produkt G Z2, wobei (0) = id
und (1) = inv.
Beispiel Die Diedergruppe Dn ist das semi-direkte Produkt von Zn und Z2: Dn =
Zn Z2 .
Lemma 8 Fur zwei abelsche Gruppen A und B gilt: dih(A B ) = A dih(B ),
wobei (b 0) = id und (b 1) = inv.
Beweis Die Abbildung : dih(A B ) ! A dih(B ), ((a b) z) = (a (b z)),
mit a 2 A, b 2 B und z 2 Z2 ist ein Isomorphismus. 2
Theorem 7 Sei G eine nicht-triviale abelsche Gruppe, dann besitzt dih(G) eine
anti-symmetrische Abbildung.
Beweis Fallunterscheidung:
1. Fall: Ist G eine zyklische Gruppe der Ordnung n, dann gilt dih(G) = Dn und
G hat demnach eine anti-symmetrische Abbildung.
2. Fall: Hat G ungerade Ordnung und ist nicht zyklisch, dann kann man G faktorisieren in eine zyklische Gruppe Zm und eine Gruppe H mit ungerader Ordnung.
Es folgt mit Hilfe von Lemma 8:
dih(G) = dih(H Zm) = H dih(Zm):
H besitzt eine anti-symmetrische Abbildung (H hat ungerade Ordnung) und es
gilt dih(Zm ) = Dm . Mit Korollar 8 folgt, da
dih(G) eine anti-symmetrische
Abbildung besitzt.
3. Fall: Ist G eine nicht-zyklische 2-Gruppe, dann gilt G = Z2 1 Z2 2 : : : Z2
mit s 2. Folglich hat das Zentrum Z (dih(G)) die Ordnung 2s und ist isomorph
zu H = Z2 Z2 : : : Z2. Da H abelsch ist und wenigstens zwei Involutionen
enthalt, besitzt H eine vollstandige und damit eine anti-symmetrische Abbildung.
Der Quotient dih(G)=Z (dih(G)) ist isomorph zu dih(Z2( 1 ;1) Z2( 2 ;1) : : :Z2( ;1) )
und besitzt, durch Induktion nach dem Maximum von ij nachweisbar, eine antisymmetrische Abbildung und wir konnen mit Korollar 8 folgern, da
G eine antisymmetrische Abbildung besitzt.
4. Fall: Nun habe G gerade Ordnung, sei aber keine 2-Gruppe, dann kann man G in
i
i
i
i
is
is
28
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
zwei nicht-triviale Gruppen faktorisieren: eine Gruppe H mit ungerader Ordnung
und eine 2-Gruppe N . Es folgt, da
dih(G) = dih(H N ) = H dih(N ):
H und dih(N ) haben anti-symmetrische Abbildungen also auch dih(G). 2
Wir adaptieren nun die Argumente von Hall und Paige 14] zur Charakterisierung der endlichen p-Gruppen, die eine vollstandige Abbildung besitzen, um zu
zeigen, da
die selbe Charakterisierung auch fur anti-symmetrische Abbildungen
gilt.
Theorem 8 Eine nicht-triviale endliche p-Gruppe hat eine anti-symmetrische Ab-
bildung genau dann, wenn sie keine zyklische 2-Gruppe ist.
Beweis Sei G eine nicht-triviale endliche p-Gruppe. Wenn p ungerade ist, dann
hat G eine anti-symmetrische Abbildung. Wenn G eine zyklische 2-Gruppe ist,
dann wissen wir durch das Resultat von Paige, Theorem 1 (Seite 16), da
G
keine vollstandige und damit auch keine anti-symmetrische Abbildung besitzt. Der
Fall, da
G eine nicht-zyklische abelsche 2-Gruppe ist wurde ebenfalls von Paige
gezeigt. Deshalb konnen wir uns auf den Fall beschranken, da
G eine nichtabelsche 2-Gruppe ist mit der Ordnung 2n.
Besitzt G eine zyklische Untergruppe der Ordnung 2n;1 dann ist bekanntlich
G entweder eine Diedergruppe, eine verallgemeinerte Quaternionen-Gruppe oder
eine Semi-Diedergruppe (Paige 14]). Nach Theorem 3 haben diese Gruppen eine
anti-symmetrische Abbildung.
Also nehmen wir an, da
G keine zyklische Untergruppe der Ordnung 2n;1
hat. Wenn G genau ein Element der Ordnung 2 enthalt, dann ware sie eine
verallgemeinerte Quaternionen-Gruppe und hatte eine zyklische Untergruppe der
Ordnung 2n;1 (siehe Paige 14]), im Widerspruch zu unserer Annahme. Also hat
G wenigstens zwei Elemente der Ordnung 2 und wenigstens eins davon im Zentrum.
Diese beiden Elemente erzeugen eine 4-Gruppe V . Wenn V in zwei verschiedenen
maximalen Untergruppen M1 und M2 enthalten ist, dann ist M1 \ M2 = K V
ein Normalteiler von G und sowohl K als auch G=K sind nicht zyklisch. Also
haben, mit Induktion, K und G=K anti-symmetrische Abbildungen und, mit dem
Erweiterungstheorem, damit auch G.
Wir nehmen daher an, da
V in genau einer maximalen Untergruppe M1 enthalten ist. Weil G nicht zyklisch ist, enthalt sie eine weitere maximale Untergruppe
M2 (Paige 14]). Wenn M1 \ M2 nicht zyklisch ist, dann stellt sie eine normale
nicht-zyklische Untergruppe K mit nicht-zyklischer Quotientengruppe dar und wir
konnen mit Induktion schlie
en, da
G eine anti-symmetrische Abbildung besitzt.
Nun sei M1 \ M2 zyklisch. Es mu
M1 eine Gruppe der Ordnung 2n;1 sein,
die eine zyklische Untergruppe der Ordnung 2n;2 und die 4-Gruppe V enthalt.
2.1. GRUPPEN MIT ANTI-SYMMETRISCHEN ABBILDUNGEN
29
Demnach mu
M1 entweder eine Diedergruppe, eine Semi-Diedergruppe oder eine
abelsche Gruppe sein. In jedem Fall konnen wir
M1 =< a bja2 ;2 = b2 = e ba = ak b >
n
schreiben, wobei k gleich ;1,2n;3 1 oder 1 ist, abhangig davon, ob M1 einer
Dieder-, Semi-Dieder- oder einer abelschen Gruppe entspricht, und es ist M1 \
M2 =< a >. Sei c ein Element von M2 aber nicht von M1 . Da < a > normal in
M2 ist, mu
c2 = ar gelten, wobei r gerade ist, da sonst c die Ordnung 2n;1 hat,
was wir ausgeschlossen haben. Weil < a > normal in G ist, erhalten wir cb = bcas
fur ein s.
Sei H die Untergruppe < a2 b >. Eine einfache Rechnung zeigt, da
H mit den
Elementen a, c und ac kommutiert, wenn s gerade ist. Also ist H ein Normalteiler
in G. H ist nicht zyklisch, also wissen wir durch Induktion, da
H eine antisymmetrische Abbildung hat und der Quotient G=H = Z2 Z2 hat ebenfalls eine
anti-symmetrische Abbildung. Mit dem Erweiterungstheorem folgt nun, da
G
eine anti-symmetrische Abbildung besitzt.
Es bleibt der Fall, da
s ungerade ist. Wir untersuchen die Untergruppe, die
durch cb erzeugt wird. Wir haben
(cb)2 = cbcb = cb2 cas = c2 as = as+r
wobei s + r ungerade ist.
Also hat (cb)2 die Ordnung 2n;2, was ord(cb) = 2n;1 impliziert. Aber dies widerspricht unserer Annahme, da
G keine zyklische Untergruppe der Ordnung 2n;1
besitzt. Damit haben wir die Behauptung bewiesen. 2
Korollar 10 Eine endliche nilpotente Gruppe mit trivialer oder nicht-zyklischer
2-Sylow-Untergruppe hat eine anti-symmetrische Abbildung.
Beweis Eine endliche nilpotente Gruppe ist das direkte Produkt ihrer Sylow-
Untergruppen. Die p-Sylow-Untergruppen mit ungeradem p haben gema
Theorem 8 eine anti-symmetrische Abbildung. Da die 2-Sylow-Untergruppe trivial oder
nicht-zyklisch ist, hat sie ebenfalls eine anti-symmetrische Abbildung. Demnach
hat auch das direkte Produkt, also G, eine anti-symmetrische Abbildung. 2
Die obengenannten Theoreme reichen aus, um zu zeigen, da
alle nicht-abelschen Gruppen der Ordnung kleiner als 36 eine anti-symmetrische Abbildung besitzen, mit Ausnahme der Gruppe < a bja3 = b8 = e ab = ba2 > der Ordnung 24,
wobei bei dieser Gruppe ebenfalls gezeigt werden kann, da
sie eine besitzt.
Da es keinen Anhaltspunkt gibt, da
eine nicht-abelsche Gruppe keine antisymmetrische Abbildung besitzt, vermuten Gallian und Mullin, da
alle nichtabelschen Gruppen eine anti-symmetrische Abbildung besitzen.
30
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
2.2 Invarianten von Ant(G)
Wir untersuchen nun welche Transformationen die Menge der anti-symmetrischen
Abbildungen einer Gruppe invariant lassen.
Satz 3 Sei '(x) eine anti-symmetrische Abbildung einer Gruppe (G ), dann ist
auch die Abbildung a '(x b), a b 2 G, anti-symmetrisch.
Beweis Aus (a '(x b)) y = (a '(y b)) x folgt mit dem Assoziativgesetz und
der Kurzungsregel '(x b) y = '(y b) x. Die Gleichung wird nun von rechts mit
b durchmultipliziert, also gilt '(x b) y b = '(y b) x b und es folgt, da ' antisymmetrisch ist, x b = y b und damit x = y. Also ist a '(x b) anti-symmetrisch.
2
Satz 4 Wenn '(x) eine anti-symmetrische Abbildung der Gruppe (G ) ist, dann
ist fur jedes c 2 G auch '(c x) c anti-symmetrisch.
Beweis Es gilt, da ' anti-symmetrisch ist: '(c x) c y = '(c y) c x ) c x =
c y ) x = y. 2
Mit la = (x 7! a x) werde die Linksmultiplikation und mit rb = (x 7! x b)
die Rechtsmultiplikation bezeichnet. Die Transformationen La = (' 7! la '),
Rb = (' 7! ' rb) und Mc = (' 7! rc ' lc) bilden jeweils eine Gruppe mit der
Verknupfung , die isomorph zu G ist.
Satz 5 ( Verhoeff 27]) Sei ' eine anti-symmetrische Abbildung und ein Automorphismus, dann ist auch ' ;1 anti-symmetrisch.
Beweis Aus ' ;1(x) y = ' ;1(y) x folgt mit y = (;1(y)) und
x = (;1(x)), da
('(;1(x)) ;1(y)) = ('(;1(y)) ;1(x)) gilt. Nachdem
wir auf beiden Seiten gekurzt haben, folgt aus der Anti-Symmetrie von ', da
;1 (x) = ;1 (y) ist und damit x = y. 2
Auch hier bilden die Transformationen T = (' 7! ' ;1 ) eine Gruppe.
Diese ist isomorph zur Automorphismen-Gruppe Aut(G).
Bemerkung Satz 4 la
t sich auch mit Satz 5 und 3 beweisen. Dazu setzt man
(x) := c;1xc und a = b = c.
Andere Moglichkeiten, wie aus einer vorgegebenen anti-symmetrischen Abbildung weitere konstruiert werden konnen, ndet man im Abschnitt "Automorphismen und Anti-Automorphismen" sowie im Kapitel "Gruppen mit Vorzeichen".
2.3. AQUIVALENZKLASSEN
31
2.3 A quivalenzklassen
Auf der Menge der anti-symmetrischen Abbildungen einer Gruppe denieren wir in
diesem Abschnitt eine A quivalenzrelation. Diese ermoglicht es uns, eine U bersicht
uber alle anti-symmetrischen Abbildungen einer Gruppe zu gewinnen.
Mit 0 bezeichnen wir im folgenden das neutrale Element der Gruppe. Weiterhin sei ' ein Automorphismus der Gruppe G und la bzw. ra die Links- bzw.
Rechtsmultiplikation mit dem Element a 2 G.
Die genannten Abbildungen haben folgende Eigenschaften:
1. la lb = lab, ra rb = rba, la;1 = la;1 , ra;1 = ra;1 :
2. la rb = rb la .
3. ' lb = l'(b) ', ' ra = r'(a) '.
Die ersten beiden Eigenschaften folgen aus dem Assoziativgesetz, fur die letzte
gilt: ' lb(x) = '(b x) = '(b) '(x) = l'(b) '(x) und ' ra(x) = '(x a) =
'(x) '(a) = r'(a) '(x).
Die A quivalenzklassen werden nun wie folgt deniert:
Denition 6 Seien f g Permutationen. f und g hei
en aquivalent, f g, wenn
Elemente a b 2 G und ein Automorphismus ' existieren, so da
gilt:
f = lb ';1 g ' ra :
Die Relation bildet eine A quivalenzrelation auf der Menge der Permutationen:
1. ist reexiv: f = l0 Id f Id r0
2. ist symmetrisch: f = lb ';1 g ' ra genau dann, wenn
g = ' lb;1 f ra;1 ';1
= ' lb;1 f ra;1 ';1
1:2:
=3: l'(b;1 ) ' f ';1 r'(a;1 )
Also: f g impliziert g f .
3. ist transitiv: Sei f = lb1 ';1 1 g '1 ra1 und g = lb2 ';2 1 h '2 ra2 ,
dann folgt
f = lb1 ';1 1 lb2 ';2 1 h '2 ra2 '1 ra1
=3: lb1 l';1 1 (b2 ) ('2 '1);1 h ('2 '1 ) r'1(a2 ) ra1
=1: lb1 ';1 1(b2 ) ('2 '1);1 h ('2 '1) ra1 '1 (a2 )
32
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
Damit ist f g g h ) f h gezeigt.
Aus dem vorherigen Abschnitt konnen wir das folgende Korollar ableiten.
Korollar 11 Seien f g 2 Sn mit f g, dann gilt
f anti-symmetrisch , g anti-symmetrisch.
Beispiel Die Diedergruppe D5 besitzt 34040 anti-symmetrische Abbildungen. Es
konnen 3040 von x;1 a abgeleitet werden (siehe Satz 21, Seite 53). Fur die restlichen 31000 anti-symmetrischen Abbildungen erhalten wir folgende Reprasentanten
der A quivalenzklassen:
1. Diese 15 Permutationen erzeugen 30000 anti-symmetrische Abbildungen
(rechts: Zyklenschreibweise):
0215637894]
0215638974]
0215647938]
0215694378]
0215748396]
0215748936]
0215794638]
0215867394]
0215874936]
0215897436]
0245678931]
0245718936]
0256714893]
0256743918]
0257918436]
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
(21)(53)(67894)
(21)(53)(68794)
(21)(5467983)
(21)(59873)(64)
(21)(5473)(896)
(21)(5479683)
(21)(5983)(764)
(21)(5673)(894)
(21)(5796483)
(21)(5967483)
(246835791)
(247968351)
(251)(647893)
(2547981)(63)
(251)(749683)
2. Die Permutation 0215643978] = (21)(5463)(987) erzeugt die restlichen 1000
anti-symmetrischen Abbildungen.
Bemerkung Mit a0 a1 : : : a9 ] meinen wir die Permutation x 7! ax, d.h.
a0 a1 : : : a9 ] = a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 :
0
1
2
3
4
5
6
7
8
9
Dieses Beispiel zeigt auch, da
die Klassen nicht unbedingt gleich gro
sein
mussen.
2.4. AUTOMORPHISMEN UND ANTI-AUTOMORPHISMEN
33
2.4 Automorphismen und Anti-Automorphismen
In diesem Abschnitt untersuchen wir einen Spezialfall, namlich anti-symmetrische
Automorphismen bzw. Anti-Automorphismen. Automorphismen sind bekanntlich
bijektive Permutationen einer Gruppe ' : G ! G mit '(xy) = '(x)'(y). Der
Begri "Anti-Automorphismus" wird dagegen nicht so haug benutzt, er wird
aber ganz ahnlich deniert:
Denition 7 Eine bijektive Abbildung : G ! G einer Gruppe G hei
t AntiAutomorphismus, wenn fur alle x y 2 G gilt: (xy) = (y)(x). Ein AntiAutomorphismus oder ein Automorphismus hei
t xpunktfrei, wenn fur alle x 6= 0
gilt: (x) 6= x.
Die folgenden Eigenschaften eines Anti-Automorphismus werden genauso gezeigt wie bei einem Automorphismus:
1. (0) = 0
2. (x);1 = g(x;1)
3. ord((x)) = ord(x)
Bemerkung Da fur einen (Anti-)Automorphismus immer (0) = 0 gilt, ist es
sinnvoll, bei der Denition von "xpunktfrei" die Stelle x = 0 auszuschlie
en.
Die Menge der Automorphismen einer Gruppe konnen wir bijektiv auf die
Menge der Anti-Automorphismen abbilden. Es gilt namlich
' ist ein Automorphismus , ' inv ist ein Anti-Automorphismus
Ist ' ein Automorphismus, dann gilt
' inv(xy) = '((xy);1) = '(y;1x;1 ) = '(y;1)'(x;1 ) = ' inv(y)' inv(x;1 )
und ' inv ist ein Anti-Automorphismus. Ist andererseits ' inv ein AntiAutomorphismus, dann haben wir
'(xy) = '((y;1x;1 );1) = ' inv(x;1 )' inv(y;1) = '(x)'(y)
und ' ist ein Automorphismus.
Wenn wir also die Automorphismen einer Gruppe kennen, dann konnen wir
auch ohne weiteres alle Anti-Automorphismen dieser Gruppe bestimmen.
Ist ein Anti-Automorphismus, so ist fur zwei beliebige Automorphismen
'1 '2 auch '1 '2 ein Anti-Automorphismus:
'1 '2(xy) = '1 ('2 (x)'2(y)) = '1 (('2(y))g('2(x)))
= '1(('2(y)))'1(('2(x)))
= '1 '2 (y)'1 '2 (x)
34
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
Das Gleiche gilt auch, wenn '1 und '2 zwei Anti-Automorphismen sind.
Wie man leicht sieht, gilt au
erdem: Sind 1 2 Anti-Automorphismen, dann
ist 1 2 ein Automorphismus.
Ist ein (xpunktfreier) Anti-Automorphismus, dann ist auch ;1 ein (xpunktfreier) Anti-Automorphismus:
;1(xy) = ;1((;1(x))(;1 (y))) = ;1((;1 (y);1(x))) = ;1 (y);1(x)
und
(x) = x
, x = ;1(x):
Damit haben wir gezeigt, da
die Menge der Anti-Automorphismen zusammen
mit den Automorphismen eine Gruppe bildet. Gibt es einen Anti-Automorphismus
der auch ein Automorphismus ist, so folgt
xy = (;1(x))(;1(y)) = (;1(y);1(x)) = yx
und die Gruppe ist abelsch. In einer abelschen Gruppe sind Anti-Automorphismen
auch Automorphismen, wahrend in einer nicht-abelschen Gruppe kein Anti-Automorphismus ein Automorphismus ist.
Mit Hilfe der Anti-Automorphismen nden wir eine zusatzliche Moglichkeit,
aus einer vorgegebenen anti-symmetrischen Abbildung eine weitere zu konstruieren.
Satz 6 Sei ' eine anti-symmetrische Abbildung und ein Anti-Automorphismus,
dann ist auch ';1 ;1 anti-symmetrisch.
Beweis Es gelte ';1 ;1(x)y = ';1 ;1(y)x. Wir setzen x~ := ';1 ;1(x)
und y~ := ';1 ;1(y), womit (~x)('(~y)) = (~y)('(~x)) folgt. Wir nutzen die
Eigenschaft aus, da
ein Anti-Automorphismus ist, um ('(~y)~x) = ('(~x)~y)
zu erhalten. In dieser Gleichung kurzen wir . Aus der resultierenden Gleichung
folgt x~ = y~, denn ' 2 Ant(G). Da ';1 ;1 bijektiv ist, haben wir damit x = y,
und der Satz ist bewiesen. 2
Wir untersuchen nun, wann ein (Anti-)Automorphismus anti-symmetrisch ist.
Satz 7 Ein Anti-Automorphismus ist genau dann anti-symmetrisch, wenn er x-
punktfrei ist.
Beweis Sei ein xpunktfreier Anti-Automorphismus und es gelte (x)y =
(y)x. Die Gleichung wird von links mit (y);1 und von rechts mit y;1 durchmultipliziert, es folgt (y;1)(x) = (xy;1) = xy;1. Da xpunktfrei ist, mu
2.4. AUTOMORPHISMEN UND ANTI-AUTOMORPHISMEN
35
xy;1 = 0, bzw. x = y gelten. Also ist anti-symmetrisch. Wenn andererseits
einen Fixpunkt x 6= 0 besitzt, dann gilt (0)x = x = (x) = (x)0 und ist
nicht anti-symmetrisch. 2
Satz 8 Sei ' ein Automorphismus. ' ist genau dann anti-symmetrisch, wenn fur
alle y 2 G gilt: y ;1 '(z)y ist xpunktfrei.
Beweis Die Gleichung '(x)y = '(y)x ist aquivalent zu '(y;1)'(x) = xy;1 bzw.
'(y;1x) = x(y;1x)x;1 . Mit z := y;1x ist dies aquivalent zu '(z) = yzy;1 bzw.
y;1'(z)y = z. 2
Lemma 9 Sei ein Anti-Automorphismus und ' ein (Anti-)Automorphismus,
dann gilt:
xpunktfrei
,
';1 ' xpunktfrei
Beweis Es ist (x) = x aquivalent zu ';1(('(';1(x)))) = ';1(x). 2
Wir konnen nun Satz 4 von Gallian und Mullin etwas anders formulieren:
Satz 9 Der Anti-Automorphismus (x) := a;1x;1 a ist genau dann xpunktfrei,
wenn x;1 und a;1 xa keinen gemeinsamen Fixpunkt x 6= 0 besitzen.
Beweis (x) xpunktfrei , (x) anti-symmetrisch , a(x) = x;1 a anti-symmetrisch , a kommutiert mit keinem Element der Ordnung 2 , fur alle x 6= 0
gilt: x;1 = x ) a;1xa 6= x. 2
Satz 10 Sei h g ein Anti-Automorphismus der Gruppe G der Ordnung n, h g 2
Sn mit den Eigenschaften: ord(g) = 2, ord(h) ungerade und g h = h g. Genau
dann ist h g xpunktfrei, wenn g und h keinen gemeinsamen Fixpunkt x 6= 0
besitzen.
Beweis Sei h g nicht xpunktfrei, d.h. es existiert ein x 6= 0 mit h(g(x)) = x.
Es folgt h(g(h(g(x)))) = h(h(g(g(x)))) = h(h(x)) = x. Da die Ordnung von h
ungerade, sprich 2k + 1 ist, haben wir x = h2k+1(x) = h(h2k (x)) = h(x). Damit
gilt h(g(x)) = g(h(x)) = g(x) = x und x 6= 0 ist ein gemeinsamer Fixpunkt von
g und h. Haben andererseits g und h den gemeinsamen Fixpunkt x 6= 0, dann ist
h(g(x)) = h(x) = x und h g ist nicht xpunktfrei. 2
Bemerkung Jede Permutation p kann in zwei Permutationen h und g zerlegt
werden, so da
die Bedingungen des Satzes erfullt sind. Dazu schreibt man p als
36
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
Produkt disjunkter Zykel. Die Transpositionen werden dann zu g zusammengefa
t, der Rest zu h.
Wir geben nun notwendige und hinreichende Konditionen fur die Erkennung
der anderen Fehlertypen an, wenn wir ein Prufziersystem n(xn ) : : : (x1 ) x0 = c
mit einem (Anti-)Automorphismus benutzen. Dazu sei ' ein Automorphismus
und ein Anti-Automorphismus.
Nachbarvertauschungen
a.) Fur alle x 6= 0: (x) 6= x (d.h. ist xpunktfrei)
b.) Fur alle x 6= 0 und alle y 2 G gilt:
xpunktfreier Automorphismus)
Sprungtranspositionen
a.) Fur alle x 6= 0 und alle z 2 G gilt:
symmetrischer Automorphismus)
y;1'(x)y =
6 x (d.h. y;1'(x)y ist ein
z;1 2 (x)z =
6 x (d.h. 2 ist ein anti-
b.) wie a. fur '
Zwillingsfehler
a.) Fur alle x 6= 0: (x;1 ) 6= x (d.h. inv ist ein xpunktfreier Automorphismus)
b.) Fur alle x 6= 0 und alle z 2 G gilt: z;1 '(x;1)z 6= x (d.h. z;1 '(x;1 )z ist ein
xpunktfreier Anti-Automorphismus)
Sprungzwillingsfehler
a.) Fur alle x 6= 0 und alle z 2 G gilt: z;1 2(x;1 )z 6= x (d.h. z;1 2(x;1 )z ist ein
xpunktfreier Anti-Automorphismus)
b.) wie a. fur '
phonetische Fehler
a.) Fur a = 2 : : : n ; 1 gilt: (a)a;1 6= (1) 6= a;1(a)
b.) Fur a = 2 : : : n ; 1 gilt: '(a)a;1 6= '(1)
Beweis Die Aussagen werden analog zu Satz 7 und 8 gezeigt. Die phonetischen
Fehler werden erkannt, falls fur a = 2 : : : n ; 1 gilt i+1(a)i (0) 6= i+1 (1)i(a).
Da (0) = 0 ist haben wir i+1(a)i (a;1) 6= i+1(1). Je nachdem ob i gerade oder
ungerade ist, ist dies aquivalent zu i ((a)a;1) 6= i+1(1) oder i(a;1 (a)) 6=
i+1 (1). Wir konnen i kurzen und erhalten damit die angegebene Bedingung.
2.5. EINE ABSCHATZUNG
VON jANT (G)j
37
2.5 Eine Abschatzung von Ant(G)
j
j
Die folgenden Satze zeigen, da
eine gro
e Anzahl Permutationen nicht antisymmetrisch sein kann.
Lemma 10 Sei (G ) eine Gruppe, G 6= feg. Die Permutationen g(x) = a x b
mit a b 2 G sind nicht anti-symmetrisch.
Beweis Es gilt fur beliebige y 2 G g(b;1) y = a b;1 b y = a y = a y b b;1 =
g(y) b;1. Da in G ein Element y 6= b;1 existiert, ist g nicht anti-symmetrisch. 2
Lemma 11 Wenn g(x) = g(0) x fur ein x =6 0 ist, dann ist g nicht antisymmetrisch.
Beweis g(x) 0 = g(x) = g(0) x. 2
Mit diesem Lemma ndet man eine untere Grenze fur die Anzahl der Permutationen, die nicht anti-symmetrisch sein konnen. Man kann namlich die Anzahl
der Permutationen mit g(x) = g(0) x, fur ein x 6= 0, berechnen.
Wir bestimmen die Anzahl a(n) der Permutationen die an der ersten (y = 0)
und einer weiteren Stelle y 2 f1 : : : ng mit einer vorgegebenen Permutation g 2
Sn+1 ubereinstimmen. a(n) ist nicht von g abhangig, daher wahlen wir o.B.d.A.
g(x) = x. Da die erste Stelle einer weiteren Permutation p gleich 0 sein mu
,
reicht es, die letzten n Stellen zu betrachten. Die letzten n Stellen sind aber
Permutationen aus Sn, d.h.
a(n) =
=
jfp 2 Sn : p(0) = 0 und jf1 y n : p(y) = ygj 1gj
jfp 2 Sn : jf0 y n ; 1 : p(y) = ygj 1gj:
+1
(Mit jM j bezeichnen wir die Anzahl der Elemente in der Menge M .)
Dieses Problem ist in der Literatur bekannt als "Mausefallenspiel mit n Karten":
Gegeben seien n Ziern und n numerierte Umschlage. Wieviele Moglichkeiten
gibt es, die Ziern in die Umschlage einzulegen, so da
mindestens eine Zahl
in den richtigen Umschlag kommt.
Die gesuchte Losung a(n) kann wie folgt berechnet werden (siehe 25], Zahlenreihe:
A002467):
1. a(0) = 0, a(1) = 1 und a(n) = (n ; 1)(a(n ; 1) + a(n ; 2)), oder
2. a(0) = 0, a(1) = 1, a(n) = n a(n ; 1) ; (;1)n , oder
38
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
3. a(0) = 0, a(n) = n! e;e 1 ], wobei e = 2 71828::: die Eulersche Zahl ist und ]
die (verschobene) Gau
klammer (auf die nachste ganze Zahl runden).
Nun betrachten wir alle Permutationen aus Sn, die mit a x an der Stelle 0
und einer weiteren Stelle ubereinstimmen. Die Anzahl dieser Permutationen ist
gleich a(n ; 1). Da fur a 6= b auch a 0 6= b 0 ist, sind die Permutationen, die
mit a x an der ersten Stelle ubereinstimmen und die, die mit b x an der ersten
Stelle ubereinstimmen, alle verschieden. Es gibt daher mindestens n a(n ; 1)
Permutationen in Sn, die nicht anti-symmetrisch sind.
Satz 11 Die Anzahl der nicht anti-symmetrischen Permutationen ist gro
er oder
gleich n a(n ; 1) = n (n ; 1)! e;e 1 ], also
n! ; jAnt(G)j n (n ; 1)! e ;e 1 ]:
Durch einfaches Umformen erhalten wir nun ein Abschatzung fur jAnt(G)j.
Theorem 9 Sei G eine Gruppe der Ordnung n, dann gilt
jAnt(G)j n! ; n (n ; 1)! e ;e 1 ] ne! + n2 :
Beweis Wir konnen die verschobene Gau
klammer wie folgt abschatzen:
(n ; 1)! e ; 1 ] (n ; 1)! e ; 1 ; 1 :
e
e
2
Damit folgt
jAnt(G)j n! ; n (n ; 1)! e ;e 1 ] n! ; n! e ;e 1 + n2
ne! + n2 :
2
Fur Gruppen der Ordnungen 2 bis 12 geben wir eine Abschatzung von jAnt(G)j
an:
n a(n ; 1)
n! n! ; n a(n ; 1)
2
1
2
0
1
6
3
3
4
4
24
8
5
15
120
45
6
76
720
264
455
5.040
1.855
7
8
3.186
40.320
14.832
9
25.487
362.880
133.497
10
229.384 3.628.800
1.334.960
11 2.293.839 39.916.800
14.684.571
176.214.840
12 25.232.230 479.001.600
2.6. KONSTRUKTION ANTI-SYMMETRISCHER ABBILDUNGEN
39
Fur n = 2 3 4 sind die Abschatzungen sogar bestmoglich. Die Gruppe Z2
besitzt keine, die Gruppe Z3 genau 3 und die Kleinsche-Vierergruppe genau 8
anti-symmetrische Abbildungen.
Fur gro
ere n gilt jAntn(!G)j 1e . Demnach konnen hochstens 36,8% der Permutationen einer beliebigen Gruppe anti-symmetrisch sein.
2.6 Konstruktion anti-symmetrischer
Abbildungen
Die anti-symmetrischen Abbildungen einer Gruppe (G ;1 0) konnen, ahnlich
wie die Primzahlen, durch eine Siebmethode bestimmt werden. Man beginnt dabei
mit einer Matrix M = (mij ) mit n n Elementen (n = jGj), wobei in jeder Zeile
die Zahlen 0 1 : : : n ; 1 stehen, d.h. mij = j fur i j = 0 : : : n ; 1.
Der folgende Algorithmus erzeugt anti-symmetrische Abbildungen oder er zeigt,
da
bestimmte Abbildungen nicht anti-symmetrisch sein konnen.
1) F
ur
i
von
0
bis
n;1
tue 2-6
2) Sind alle Elemente der
dann Abbruch
m
i-ten
Zeile von
i aus,
'(i) := j
3) W
ahle ein Element
ij der Zeile
gestrichen ist, und setze
i = n ; 1, dann Ende
F
ur k von i + 1 bis n ; 1 tue
6) Streiche die Elemente mkj
k-ten Zeile
M
gestrichen,
das noch nicht
4) Falls
5)
und
mkjki;1
aus der
Beispiel Im folgenden wird mit diesem Algorithmus
Ab2 eine anti-symmetrische
3
0 1 2 3 4
660 1 2 3 477
bildung der Gruppe Z5 bestimmt. Dazu sei M := 660 1 2 3 477.
40 1 2 3 45
0 1 2 3 4
40
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
20
Das Element m00 ist nicht gestrichen, wir konnen 66 0
also '(0) := 0 setzen. Die Elemente m10 , 666 0
m10+1;0 , m20 , m20+2;0 , m30, m30+3;0 , m40 , 646 0
m40+4;0 werden gestrichen.
26 00
Nun konnen wir '(1) := 2 wahlen die Elemente 666 0
m22 , m22+2;1 , m32 , m32+3;1 , m42, m42+4;1 wer- 666 0
4
60
den gestrichen.
1
61
1
1
1
1
61
1
1
1
1
61
1
1
61
1
61
1
60
2
Als nachstes mu
'(2) := 4 gewahlt werden, da 0
sonst in der vorletzten Zeile alle Elemente ge- 666 0
strichen waren und der Algorithmus im nachsten 666 0
Durchlauf abbrechen wurde. m34 , m34+3;2 , m44 , 46 0
m44+4;2 werden gestrichen.
26 00
Es bleibt '(3) := 1, wodurch die Elemente m41 666 0
und m41+4;3 gestrichen werden. Im letzten Durch- 666 0
46 0 1
lauf ist damit die Wahl '(4) := 3 moglich.
2
2
62
2
2
2
2
62
62
62
2
2
62
62
62
2
2
62
62
60 61 62
3
3
3
63
3
3
3
63
63
3
3
3
63
63
3
3
3
63
63
43
4 77
4 77
45
6 43
4
4 77
4 77
6 45
6 43
4
4 77
4 77
6 45
6 43
4
4 77
4 77
6 45
3 6 4
Der Algorithmus endet mit dem Ergebnis, da
' = 00 12 24 31 43 eine antisymmetrische Abbildung von Z5 ist. Der folgende Satz zeigt, da
der Algorithmus
wie gewunscht arbeitet:
Satz 12 Es gilt:
1. Jede vorgegebene anti-symmetrische Abbildung kann mit dem obengenannten
Algorithmus konstruiert werden.
2. Endet der Algorithmus im Schritt 4), dann ist die konstruierte Abbildung '
anti-symmetrisch.
3. Bricht der Algorithmus im Schritt 2) ab, dann existiert keine anti-symmetrische Abbildung, welche mit dem bis dahin denierten ' ubereinstimmt.
Es ist zu zeigen, da
fur k = 0 : : : n ; 1 das
Element mk(k) nicht gestrichen ist und damit die Wahl '(k) = (k) moglich ist.
Dies wird durch Induktion nach k gezeigt.
1) In der Zeile k = 0 ist kein Element gestrichen, man kann also '(0) := (0)
setzen.
2) Es gelte '(j ) = (j ) fur j = 0 : : : k ; 1 < n ; 1. Nimmt man an, da
das Element mk(k) in Schritt 6 gestrichen wurde, dann gibt es ein i < k mit '(i) = (k)
Beweis zu 1: Sei 2 Ant(G).
2.6. KONSTRUKTION ANTI-SYMMETRISCHER ABBILDUNGEN
41
oder mit '(i) k i;1 = (k). Im ersten Fall folgt (i) = (k) und ware
keine Permutation. Im zweiten Fall ware (i) k = (k) i. Beides steht im
Widerspruch zur Voraussetzung 2 Ant(G). Also ist das Element mk(k) nicht
gestrichen und die Wahl '(k) := (k) in Schritt 3 ist moglich.
Der Algorithmus bricht auch nicht ab, da das Elemente mk(k) nicht gestrichen
ist.
Dies zeigt, da
jede anti-symmetrische Abbildung mit dem Algorithmus konstruiert werden kann.
zu 2: Es gelte '(k) i = '(i) k fur i k (o.B.d.A.) und damit '(k) = '(i) k i;1 .
Da fur k > i das Element '(i) k i;1 gestrichen wird und die Wahl '(k) =
'(i) k i;1 nicht moglich ist, mu
k i gelten, also ist k = i und ' ist eine
anti-symmetrische Abbildung.
zu 3: Dies ist eine direkte Folgerung aus 1. 2
Um alle anti-symmetrischen Abbildungen einer Gruppe zu bestimmen, mu
man oensichtlich in Schritt 3 nacheinander alle nicht gestrichenen Elemente auswahlen. Der folgende rekursive Algorithmus verwirklicht dieses Vorgehen.
Erzeuge alle anti-symmetrischen Abbildungen, die mit der Permutation ' bis
zur Stelle i ; 1 ubereinstimmen und benutze dabei die Matrix M = (mij ):
i
Prozedur AntiSymm( )
i = n,
1) Ist
sonst:
dann gib die anti-symmetrische Abbildung
m
'
aus,
i
2) F
ur alle Elemente
ij der Zeile , die nicht
gestrichen sind, tue 3-7
'(i) := j
k von i + 1
3) Setze
4) F
ur
bis
n;1
tue (falls
5) Streiche die Elemente
-ten Zeile von
k
i+1
M
mkj
und
i < n ; 1)
mkjki;1
aus der
6) AntiSymm(
),
d.h. erzeuge alle anti-symmetrischen Abbildungen,
die mit der Permutation
bis zur Stelle
uberein
stimmen.
'
i
7) Widerrufe die Anderungen der Schritte 4+5 (Elemente die
bereits vorher gestrichen waren, bleiben gestrichen!)
Der Algorithmus wird mit dem Aufruf AntiSymm(0) gestartet. Wobei mij := j
fur i j = 0 : : : n ; 1.
42
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
Das folgende Pascal-Programm implementiert diesen Algorithmus. In der Matrix M wird dabei aber nicht das Element mij = j gespeichert, sondern vielmehr
wie oft dieses Element gestrichen wurde. Das Streichen eines Elements entspricht
dann dem Erhohen dieses Elements um 1. Die Schritte 4+5 werden dann durch
Erniedrigen der veranderten Elemente um 1 ruckgangig gemacht.
program antsymm
const Basis = 10
type TDigit = 0..Basis-1
TAbb
= arrayTDigit] of TDigit
TMatrix = arrayTDigit,TDigit] of TDigit
var phi : TAbb
M
: TMatrix
procedure AntiSymm(i : TDigit)
var j,k : Integer
begin
if i=Basis then phi ausgeben
else begin
for j:=0 to Basis-1 do
F
ur jedes Element der i-ten Zeile
if Mi,j]=0 then begin
Wenn Mi,j] nicht gestrichen ist,
phii]:=j
dann setze phi(i):=j
for k:=i+1 to Basis-1 do begin
Inc(Mk,j])
Streiche die Elemente Mk,j]
Inc(Mk,j*k*i^(-1)])
und Mk,j*k*i^(-1)]
end
AntiSymm(i+1)
Rekursiver Aufruf
for k:=i+1 to Basis-1 do begin
Dec(Mk,j])
Streichungen r
uckg
angig machen
Dec(Mk,j*k*i^(-1)])
end
end
end
end
f
g
f
f
f
f
f
f
f
var j,k : TDigit
begin
for j:=0 to Basis-1 do
for k:=0 to Basis-1 do Mk,j]:=0
AntiSymm(0)
end.
g
g
g
g
g
g
g
2.6. KONSTRUKTION ANTI-SYMMETRISCHER ABBILDUNGEN
43
Damit das Programm lauahig ist, mu
noch die Verknupfung und das Inverse i;1 eines Elements deniert werden. Fur die Diedergruppe lautet eine entsprechende Implementierung (vgl. H.P. Gumm 13]):
const Basis_2 = Basis div 2
fBasis mu gerade sein!g
function inv(x : TDigit) : TDigit
begin
if x<Basis_2 then inv:=(Basis_2-x) mod Basis_2
else inv:=x
end
function add(x,y : TDigit) : TDigit
begin
if x<Basis_2 then begin
if y<Basis_2 then add:= (x+y) mod Basis_2
else add:=((x+y) mod Basis_2)+Basis_2
end
else begin
if y<Basis_2 then add:=((x-y) mod Basis_2)+Basis_2
else add:=(x-y+Basis_2) mod Basis_2
end
end
Damit ist j*k*i^(-1)=add(add(j,k),inv(i)). Fur die Gruppe Zn kann man
die Operationen +,; und mod benutzen, d.h.
j*k*i^(-1)=(Basis+j+k-i) mod Basis
.
Bei der Konstruktion aller anti-symmetrischen Abbildungen einer Gruppe konnen wir noch folgende Eigenschaft ausnutzen:
Lemma 12 Sei g 2 Ant(G), dann existiert eine eindeutig bestimmte anti-sym-
metrische Abbildung g0 2 Ant(G), mit g0 (0) = 0, und ein eindeutig bestimmtes
b 2 G mit g = lb g0.
Beweis Sei g0 = lg(0);1 g, dann ist g0 2 Ant(G) und es gilt g0(0) = g(0);1 g(0) =
0. Wenn lb1 g0 = lb2 h0 gilt, mit g0(0) = 0 = h0 (0), dann folgt b1 = b1 g0 (0) =
b2 h0 (0) = b2 und damit g0 = h0 . 2
Wir mussen also lediglich die anti-symmetrischen Abbildungen g0 konstruieren,
fur die g0(0) = 0 ist. Alle anderen erhalten wir dann durch die Links-Multiplikation
44
KAPITEL 2. ANTI-SYMMETRISCHE ABBILDUNGEN
mit einem Element aus der Gruppe. Fur den Algorithmus bedeutet dies, da
'(0) = 0 gesetzt wird und in der Matrix M die Elemente mk0 und mkk , k =
1 : : : n ; 1, gestrichen werden. Der Aufruf erfolgt dann mit AntiSymm(1).
Aus diesem Lemma folgt auch, da
die Anzahl der anti-symmetrischen Abbildungen durch die Anzahl der Elemente der Gruppe teilbar ist.
Mit diesem Programm haben wir die Anzahl der anti-symmetrischen Abbildungen
der Diedergruppen D3 bis D8 und der zyklischen Gruppen Z3 bis Z15 bestimmt:
jAnt(Ds)j Rechenzeit jAnt(Ds)j=(2s)!
Ordnung 2 s
23
120 nicht me
bar
16,667%
24
1.472 nicht me
bar
3,651%
25
34.040
ca. 50ms
0,938%
26
1.412.928
2,5s
0,295%
2 7 100.229.976
1m 36s
0,114%
2 8 6.744.202.240 1h 48m 40s
0,032%
Ordnung n
3
5
7
9
11
13
15
jAnt(Zn)j
3
15
133
2.025
37.851
1.030.367
36.362.925
Rechenzeit
nicht me
bar
nicht me
bar
nicht me
bar
nicht me
bar
ca. 110ms
4s
2m 3s
jAnt(Zn)j=n!
50,000%
12,500%
2,639%
0,558%
0,095%
0,017%
0,003%
Bemerkung Fur n gerade haben wir bereits gezeigt, da
jAnt(Zn)j = 0 gilt.
Kapitel 3
Gruppen mit Vorzeichen und ihre
anti-symmetrischen Abbildungen
an, M.
Bei der Untersuchung der Diedergruppen stie
en wir unabhangig von J. Sir
Skoviera
24] auf den Begri des Vorzeichens eines Gruppenelements. Im ersten
an, M. Skoviera
Abschnitt beweisen wir zunachst einige, von J. Sir
erwahnte,
grundlegende Eigenschaften. Danach zeigen wir, da
Gruppen der Ordnung 4k +2
eine nicht-triviale Vorzeichenfunktion besitzen. Damit konnen wir einen sehr kurzen Beweis von Theorem 2 (Siemon, Seite 19) ableiten. Einen wichtigen Spezialfall
untersuchen wir im Abschnitt "Anti-symmetrische Abbildungen der Diedergruppe". Wie bereits gezeigt, ist die Diedergruppe D5 die einzige Gruppe der Ordnung
10, uber der ein Prufziersystem existiert.
3.1 Gruppen mit Vorzeichen
Denition 8 Eine Gruppe (G ) besitzt das Vorzeichen sgnG, falls sgnG : G !
f;1 +1g ein Homomorhpismus ist, d.h. sgnG(x y) = sgnG(x) sgnG(y). Ein
Vorzeichen sgnG hei
t nicht-trivial, wenn sgnG surjektiv ist. Das Vorzeichen eines
Gruppenelements x 2 G ist sgnG(x). Die Elemente mit Vorzeichen +1 hei
en
positiv und die mit Vorzeichen ;1 negativ. Die Menge aller positiven Elemente
;
von G werde mit G+ , die der negativen Elemente mit G bezeichnet.
Jede Gruppe G der Ordnung n besitzt das triviale Vorzeichen x 7! 1. Eine
weitere Moglichkeit ein Vorzeichen auf G zu denieren erhalten wir, wenn wir G in
die symmetrische Gruppe einbetten: Mit la = (x 7! a x), der Linksmultiplikation
mit a, ist = (a 7! la ) ein Isomorphismus von G auf G = flaja 2 Gg Sn. Auf Sn
konnen wir die Signatur eines Elements als Vorzeichen benutzen (vgl. Meyberg
17]):
sgnG(a) := sgnG (la)
45
(3.1)
46
KAPITEL 3. GRUPPEN MIT VORZEICHEN
wobei sgnG (la ) = 1, falls la als Produkt von einer geraden Anzahl Transpositionen
dargestellt werden kann und sgnG (la) = ;1 sonst. Ist G keine Untergruppe von
An, so ist dieses Vorzeichen nicht-trivial.
Fur das Vorzeichen gilt:
1. sgnG(e) = 1:
2. sgnG(x;1 ) = sgnG(x);1 = sgnG(x).
3. G = G+ G;.
Lemma 13 G+ ist ein Normalteiler mit Index 2.
Beweis Als Kern des Homomorphismus sgnG ist G+ ein Normalteiler in G und
alle Nebenklassen eines Normalteilers sind gleichmachtig. 2
Korollar 12 Gruppen mit ungerader Ordnung und einfache Gruppen (au
er Z2)
besitzen nur die triviale Vorzeichenfunktion sgnG : x 7! 1.
Elemente mit ungerader Ordnung haben das Vorzeichen 1, denn aus ord(x) =
2k + 1 folgt
sgn(x) = sgn(x2k+2) = sgn(x)2k+2 = sgn(x)k+1sgn(x)k+1 = 1:
Einfache Gruppen (au
er Z2) haben keine Normalteiler mit Index 2.
Lemma 14 Ist U eine Untergruppe mit Index 2 in G, dann wird durch
sgn(x) =
(
falls x 2 U
;1 sonst
1
ein Vorzeichen auf G deniert.
Beweis U ist ein Normalteiler in G und es gilt
xy 2U
und
,
x y 2 U oder x y 2= U
x y 2= U
, x 2 U y 2= U oder x 2= U y 2 U:
Folglich ist sgn : G ! f;1 1g ein Homomorphismus. 2
Die letzten beiden Lemmata fassen wir wie folgt zusammen
3.1. GRUPPEN MIT VORZEICHEN
47
Satz 13 Eine Gruppe besitzt eine nicht-triviale Vorzeichenfunktion genau dann,
wenn sie eine Untergruppe mit Index 2 besitzt.
Bemerkung Falls G ein nicht-triviales Vorzeichen besitzt, so gilt G=G+ = Z2,
d.h. man kann die Gruppe G als Erweiterung von G+ durch Z2 ansehen.
Beispiel Die zyklische Gruppe Zn besitzt ein nicht-triviales Vorzeichen genau
dann, wenn n gerade ist. Ist n ungerade, dann hat Zn kein Vorzeichen. Ist n
gerade dann wird durch
sgn(x) =
(
falls x gerade
;1 falls x ungerade
1
ein Vorzeichen auf Zn deniert.
Beispiel Auf der Gruppe der Anti-Automorphismen vereinigt mit den Automor-
phismen einer Gruppe G wird durch sgn(') = 1, falls ' ein Automorphismus
ist und sgn(') = ;1, falls ' ein Anti-Automorphismus ist, ein Vorzeichen deniert. Dieses Vorzeichen ist genau dann nicht trivial, wenn G nicht abelsch ist
(vgl. Abschnitt "Automorphismen und Anti-Automorphismen").
Satz 14 Eine Gruppe G der Ordnung n = 2(2k + 1), k 1, besitzt ein nichttriviales Vorzeichen.
Beweis Wir zeigen, da
das in 3.1 denierte Vorzeichen nicht-trivial ist, d.h. es
existiert ein a 2 G mit sgnG(a) = sgnG (la ) = ;1. Da die Ordnung von G gerade
ist, existiert ein a 2 G der Ordnung 2. Daher ist la la = Id und la besteht aus
2k + 1 Transpositionen (xi 2 G geeignet)
la = (e la(e))(x2 la (x2)) : : : (x2k+1 la (x2k+1)):
Da 2k + 1 ungerade ist, folgt sgnG(a) = sgnG (la ) = ;1. 2
Korollar 13 Jede Gruppe der Ordnung n = 2(2k + 1), k 1, besitzt einen Nor-
malteiler der Ordnung 2k + 1.
Beweis Da eine solche Gruppe ein nicht-triviales Vorzeichen besitzt, hat die zugehorige Menge der positiven Elemente G+ die Ordnung 2k + 1 und ist daher ein
Normalteiler mit der gesuchten Eigenschaft. 2
Wir geben nun den noch fehlenden Beweis von Theorem 2 an. Wir mussen
zeigen, da
eine Gruppe G der Ordnung 2(2k + 1), k 1, keine vollstandige
Abbildung besitzt. G besitzt ein nicht-triviales Vorzeichen sgn (Satz 14) und G+
48
KAPITEL 3. GRUPPEN MIT VORZEICHEN
ist ein Normalteiler der Ordnung 2k + 1 (Korollar 13).
Wenn G eine vollstandige Abbildung f besitzt, dann folgt:
Y
x2G
und
Y
x2G
sgn(x) =
Y
x2G
+
sgn(x)
Y
x2G;
sgn(x)
= 1 (;1)jG;j = (;1)jG+j = (;1)2k+1 = ;1
Y
Y
sgn(xf (x)) = sgn(x) sgn(f (x))
x2G
x2G
Y
Y x2G
= sgn(x) sgn(x) = (;1) (;1) = 1
sgn(x) =
Y
x2G
x2G
also ein Widerspruch. Demnach kann G keine vollstandige Abbildung besitzen. 2
3.2 Anti-symmetrische Abbildungen
In diesem Abschnitt zeigen wir weitere Moglichkeiten, wie wir aus einer antisymmetrischen Abbildung neue konstruieren konnen.
Wir nennen zwei Permutationen p q elementfremd, wenn fur alle x gilt:
p(x) = x
oder
q(x) = x:
Satz 15 Sei (G ) eine Gruppe mit Vorzeichen sgn, g g r 2 Ant(G), und es gelte
fur alle x 2 G: sgn(g(x)) = c sgn(x) und sgn(r(x)) 6= sgn(x) mit c 2 f;1 1g,
dann ist fur jede Zerlegung von r in elementfremde Faktoren, r = p q, auch
g p 2 Ant(G).
Beweis Annahme: g p ist nicht anti-symmetrisch, d.h. es existieren a b 2 G,
a 6= b mit
g p(a) b = g p(b) a:
Oensichtlich gilt dann p(a) 6= a oder p(b) 6= b, sonst ware g nicht anti-symmetrisch:
g p(a) b = g(a) b = g(b) a = g p(b) a:
Wenn dagegen p(a) 6= a und p(b) 6= b gilt, dann kommen a und b nicht in q vor
3.2. ANTI-SYMMETRISCHE ABBILDUNGEN
und es folgt q(a) = a, q(b) = b und damit
g r(a) b =
=
=
=
=
49
g p q(a) b
g p(a) b
g p(b) a
g p q(b) a
g r(b) a
im Widerspruch zur Voraussetzung q r 2 Ant(G). Es bleibt daher nur die
Moglichkeit p(a) 6= a p(b) = b. (Die Annahme ist in a und b symmetrisch, es
ist also auch p(a) = a p(b) 6= b abgedeckt.) Auch in diesem Fall kommt a in p vor
und damit nicht in q, d.h. q(a) = a. Aus der Annahme folgt somit die Gleichung
g r(a) b = g p q(a) b = g p(a) b = g p(b) a = g(b) a:
Ein Vergleich der Vorzeichen zeigt aber
sgn(g r(a) b) = c sgn(r(a))sgn(b) 6= c sgn(a)sgn(b) = sgn(g(b) a):
Damit ist die Annahme widerlegt, d.h. es gilt fur alle a b 2 G, a 6= b, g p(a) b 6=
g p(b) a, folglich ist g p eine anti-symmetrische Abbildung. 2
Ein ahnlicher Satz gilt fur eine nachgeschaltete Permutation.
Satz 16 Sei (G ) eine Gruppe mit Vorzeichen sgn, g r g 2 Ant(G) und es gelte
fur alle x 2 G: sgn(g(x)) = c sgn(x) und sgn(r(x)) 6= sgn(x), mit c 2 f;1 1g,
dann ist fur jede Zerlegung von r in elementfremde Faktoren, r = p q, auch
p g 2 Ant(G).
Beweis Seien r~ := g;1 r g, p~ := g;1 p g und q~ := g;1 q g, dann ist
g r~ = r g anti-symmetrisch und r~ = p~ q~. Die Permutationen p~ und q~ sind
elementfremd, denn wenn p~(a) 6= a gilt, dann folgt p(g(a)) 6= g(a) und, da p und q
elementfremd sind, q(g(a)) = g(a). Also gilt q~(a) = g;1(q(g(a))) = g;1(g(a)) = a
und a kommt in q nicht vor. Au
erdem gilt
sgn(~r(x)) = sgn(g;1 r g(x)) = c sgn(g g;1 r g(x))
= c sgn(r g(x))
6 c sgn(g(x)) = sgn(x):
=
Nun sind die Voraussetzungen des vorherigen Satzes fur r~,~p und q~ erfullt und es
folgt g p~ = g g;1 p g = p g 2 Ant(G). 2
50
KAPITEL 3. GRUPPEN MIT VORZEICHEN
Wie der Beweis zeigt, besitzt jede anti-symmetrische Abbildung p~ g (~p g
gema
Satz 16) ein weitere Darstellung g p (p gema
Satz 15).
Am Beweis von Satz 15 sehen wir au
erdem, da
wir das nicht-trivale Vorzeichen der Gruppe nur an einer Stelle benutzen. Fur beliebige Gruppen gilt daher:
Satz 17 Sei (G ) eine Gruppe, g g r 2 Ant(G) und es gelte fur alle x y 2 G
g r(x) y = g(y) x ) x = y
dann ist fur jede Zerlegung von r in elementfremde Faktoren, r = p q , auch
g p 2 Ant(G).
Bemerkung Aus g g r 2 Ant(G) folgt nicht g r(x) y = g(y) x ) x = y wie
folgendes Gegenbeispiel der Diedergruppe D5 (Gruppentafel auf Seite 52) zeigt:
Sei g(x) = x;1 2 und r(x) = x 1, dann gilt g g r 2 Ant(D5 ) (Satz 20, Seite 52),
aber
g r(0) 3 = g(1) 3 = 1 3 = 4 = 2 2 = g(3) 0:
Fur die speziellen anti-symmetrischen Abbildungen g(x) = b x;1 a konnen wir
konkret angeben, fur welche p die Voraussetzungen von Satz 15 erfullt sind.
Satz 18 Sei (G ) eine Gruppe mit Vorzeichen sgn, und g(x) = b x;1 a sei eine
anti-symmetrische Abbildung. Zudem erfulle die Permutation
p = (k1 l1 )(k2 l2 ) : : : (kn ln)
wobei (ki li) eine Transposition ist (ki li 2 G), die Bedingungen:
1. l1;1 k1 = lj;1 kj , fur j = 2 : : : n
2. ord(l1;1 k1 ) = 2, sgn(l1;1 k1) = ;1
dann ist auch g p(x) anti-symmetrisch.
Beweis Es sei p = (k1 l1)(k2 l2 ) : : : (kn ln) eine Permutation mit den genannten
Eigenschaften. Aus den Voraussetzungen folgt, da
die Transpositionen (ki li)
und (kj lj ) entweder gleich oder elementfremd sind. Wir nehmen daher o.B.d.A.
an, da
sie paarweise elementfremd sind. Sei c := l1;1 k1 und r(x) := x c, dann ist
g r 2 Ant(G) und man sieht leicht, da
fur die Zerlegung von r in elementfremde
Faktoren
r = (k1 l1 )(k2 l2 ) : : : (kn ln) q = p q
3.3. ANTI-SYMMETRISCHE ABBILDUNGEN DER DIEDERGRUPPE
51
gilt, denn r(li) = li l1;1 k1 = li li;1 ki = ki und r r = id. Au
erdem ist
sgn(g(x)) = sgn(b x;1 a) = sgn(a b)sgn(x) und sgn(r(x)) = sgn(x l1;1 k1) =
sgn(x)sgn(l1;1 k1 ) = ;sgn(x) 6= sgn(x). Damit sind die Voraussetzungen von
Satz 15 fur g und r = p q erfullt und es folgt g p 2 Ant(G). 2
Ganz analog zeigt man den folgenden Satz, der ein Spezialfall von Satz 16 ist.
Satz 19 Sei (G ) eine Gruppe mit Vorzeichen sgn, und g(x) = b x;1 a
Ant(G). Zudem erfulle die Permutation
2
p = (k1 l1)(k2 l2 ) : : : (kn ln)
die folgenden Bedingungen:
1. l1 k1;1 = lj kj;1 , fur j = 2 : : : n
2. ord(l1 k1;1 ) = 2, sgn(l1 k1;1 ) = ;1
dann ist auch p g(x) anti-symmetrisch.
3.3 Anti-symmetrische Abbildungen der
Diedergruppe
Die Diedergruppe D5 spielt eine wichtige Rolle bei der Suche nach einem Prufziffersystem, denn sie ist die einzige Gruppe der Ordnung 10 die eine anti-symmetrische
Abbildung besitzt. In diesem Abschnitt zeigen wir daher einige Eigenschaften
der anti-symmetrischen Abbildungen der Diedergruppe. Dazu benutzen wir die
Matrixschreibweise der Diedergruppe (H.P. Gumm 12]) (s > 2)
Ds = f(e x)je 2 f;1 1g und x 2 Zsg
mit der Verknupfung
(e x) (f y) := (e f e y + x):
In der ersten Komponente wird in der multiplikativ geschriebenen Gruppe Z2
gerechnet, in der zweiten im Ring Zs. Den Paaren (e x) ordnen wir die Ziern
f0 : : : 2s ; 1g auf folgende Weise zu:
(1 x) 7! x
(;1 x) 7! s + x
Fur D5 haben wir damit die Gruppentafel:
52
KAPITEL 3. GRUPPEN MIT VORZEICHEN
0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 0 6 7 8 9 5
2 2 3 4 0 1 7 8 9 5 6
3 3 4 0 1 2 8 9 5 6 7
4 4 0 1 2 3 9 5 6 7 8
5 5 9 8 7 6 0 4 3 2 1
6 6 5 9 8 7 1 0 4 3 2
7 7 6 5 9 8 2 1 0 4 3
8 8 7 6 5 9 3 2 1 0 4
9 9 8 7 6 5 4 3 2 1 0
Durch die Matrixschreibweise konnen wir eine anti-symmetrische Abbildung
g 2 Ant(Ds ) in der Form
g(e x) = (g1(e x) g2(e x))
schreiben, wobei g1 : Ds ! f;1 1g und g2 : Ds ! f0 : : : s ; 1g surjektive Abbildungen sind.
Als Folgerung von Theorem 4 (Seite 24) und Satz 3 (Seite 30) erhalten wir
2 Ds, (s > 2 ungerade) und a 2
f1 ::: s ; 1g sind anti-symmetrisch.
Beweis Die Abbildung x; a, a 2 f1 ::: s ; 1g ist anti-symmetrisch, da a mit
keinem Element der Ordnung 2 kommutiert: Weil s ungerade ist, haben nur die
Elemente (;1 c) die Ordnung 2, denn aus (1 x) (1 x) = (1 2x) = (1 0) folgt
x = 0. Angenommen a = (1 a) kommutiert mit dem Element (;1 c), d.h.
(1 a) (;1 c) = (;1 c + a) = (;1 c ; a) = (;1 c) (1 a):
Es folgt c + a = c ; a bzw. 2a = 0 und damit a = 0, im Widerspruch zu
a 2 f1 ::: s ; 1g. Also ist x; a und somit auch bx; a anti-symmetrisch. 2
Satz 20 Die Abbildungen b x;1 a mit b
1
1
1
Bei einem Vergleich dieses Satzes mit dem vorherigen Abschnitt, stellt sich die
Frage, ob Satz 18 anwendbar ist. Dies ist moglich, wie der folgende Satz zeigt.
Zunachst fuhren wir allerdings das Vorzeichen eines Elements der Diedergruppe
ein. Auf der Diedergruppe wird durch die Funktion sgn : Ds ! f;1 1g
sgn(e x) := e
ein nicht-triviales Vorzeichen deniert, denn es gilt
sgn((e x) (f y)) = sgn(ef ey + x) = ef = sgn(e x)sgn(f y):
3.3. ANTI-SYMMETRISCHE ABBILDUNGEN DER DIEDERGRUPPE
53
Wenn wir die Darstellung der Diedergruppe mit den Ziern f0 : : : 2s ; 1g benutzen, dann ist sgn(x) = sgn(1 x) = 1, 0 x s ; 1 und sgn(s + x) = sgn(;1 x) =
;1, s s + x 2s ; 1.
Satz 21 Sei g(x) := b x;1 a 2 Ant(Ds) und p := (k1 l1 )(k2 l2) : : : (kn ln) mit
den Eigenschaften s ki 2s ; 1, 0 li s ; 1, ki 6= kj und l1;1 k1 = lj;1 kj ,
bzw. l1 k1;1 = lj kj;1 , j = 2 : : : n, dann ist auch g p bzw. p g 2 Ant(Ds ).
Beweis Es ist sgn(k1) = ;1 6= 1 = sgn(l1) und (l1;1 k1) (l1;1 k1) = (1 y) (;1 x) (1 y) (;1 x) = (;1 x + y) (;1 x + y) = (1 ;x ; y + x + y) = (1 0) also
ord(l1;1 k1) = ord(l1 k1;1) = 2. Mit Satz 18 bzw. Satz 19 folgt die Behauptung. 2
Mit diesem Satz konnen wir 3040 anti-symmetrische Abbildungen der Diedergruppe D5 aus den Permutationen b x;1 a konstruieren (bislang waren nur 40
bekannt).
Beispiel Wir wahlen b = 0 a = 1, dann ist g(x) = x;1 1 = (10)(42)(98765) 2
Ant(D5 ). Aus Satz 21 folgt, da
z.B. auch g (50) (61)
g (61) (83) (94) = (50) (73) (82) g 2 Ant(D5 ).
3.3.1 Fehlererkennung
2
Ant(D5 ) oder
Fur die Komponentenfunktionen g1 g2 der Diedergruppe konnen wir weitere Eigenschaften zeigen. Au
erdem beweisen wir am Ende dieses Abschnitts, da
uber
den Diedergruppen Ds, s > 2 ungerade, kein Prufziersystem existiert, welches
alle Sprungtranspositionen erkennt.
Satz 22 Sei g 2 Ant(Ds) (s > 2), g(e x) = (g1(e x) g2(e x)), dann hangt g2 von
e und von x ab.
Beweis Fall 1: g2 hange nur von e ab, d.h. g2(e x) = g2(e). In diesem Fall besitzt
g2 (Ds) hochstens zwei Elemente (namlich g2(1 0) und g2(;1 0)) und g(Ds) besitzt
hochstens vier Elemente (1 g2(1 0)). Damit kann g keine Permutation sein, da
Ds fur s > 2 mindestens sechs Elemente hat. Also ist g 62 Ant(Ds).
Fall 2: g2 hange nur von x ab, d.h. g2 (e x) = g2(x). Auch hier folgt, da
g nicht
anti-symmetrisch ist, denn es gilt entweder g1(1 0) = g1(;1 0) und g ware nicht
injektiv, g(1 0) = (g1(1 0) g2(0)) = (g1(;1 0) g2(0)) = g(;1 0), oder g1(1 0) =
;g1(;1 0) und damit
g(1 0) (;1 0) = (g1(1 0) g2(0)) (;1 0) = (;g1(1 0) g2(0))
= (g1(;1 0) g2(0))
= g(;1 0) (1 0):
54
KAPITEL 3. GRUPPEN MIT VORZEICHEN
Folglich ist g nur anti-symmetrisch wenn g2 von e und von x abhangt. 2
Satz 23 Sei g 2 Ant(Ds ) (s > 2 ungerade), g(e x) = (g1(e x) g2(e x)), dann
hangt g1 entweder nur von e oder von e und x ab.
Beweis Wenn g1 nur von x abhangt, dann gilt fur alle x 2 f0 : : : s ; 1g g1(1 x) =
g1 (;1 x). Die Anzahl a1 := jf(e x) 2 Dsjg1(e x) = 1gj und a;1 := jf(e x) 2
Dsjg1(e x) = ;1gj der Elemente, fur die g1 (e x) gleich 1 bzw. ;1 ist, mu
daher
gerade sein, ai = 2ki. Weiterhin gilt a1 + a;1 = 2k1 + 2k;1 = jDsj = 2s, woraus
k1 + k;1 = s folgt. Da s ungerade ist, mu
k1 6= k;1 und deshalb a1 6= a;1 gelten.
Damit kann g nicht injektiv sein, denn es gilt jf(e x) 2 Dsje = 1gj = s = jf(e x) 2
Dsje = ;1gj. Also ist g im Fall, da
g1 nur von x abhangt, nicht anti-symmetrisch.
2
Satz 24 Sei g 2 Ant(Ds), s > 2, g(e x) = (e g2(e x)), dann sind g2(1 x) und
g2 (;1 ;x) anti-symmetrische Abbildungen von Zs.
Beweis Sei c 2 f;1 1g, wir zeigen g2(c cx) 2 Ant(Zs). Dazu sei g2(c cx) + y =
g2 (c cy) + x. Es folgt g(c cx) (c cy) = (1 y + g2 (c cx)) = (1 x + g2(c cy)) =
g(c cy) (c cx) und damit (c cx) = (c cy) bzw. x = y. 2
Satz 25 Sei g 2 Ant(Ds) (s > 2 gerade), g(e x) = (g1(e x) g2(e x)), dann hangt
g1 entweder nur von x oder von e und x ab.
Beweis Wenn g1 nur von e abhangt, dann ware g2(1 x) eine anti-symmetrische
Abbildung von Zs. Wir haben aber bereits gezeigt, da
Zs fur gerades s keine
anti-symmetrische Abbildung besitzt. 2
Abschlie
end zeigen wir eine wichtige Eigenschaft der anti-symmetrischen Abbildungen der Diedergruppe.
Satz 26 Sei g
2 Ant(Ds), s > 2 ungerade, dann existiert ein c 2 Ds, so da
g(x) c 62 Ant(Ds) ist.
Korollar 14 Uber der Diedergruppe Ds, s > 2 ungerade, existiert kein Prufzier-
system das alle Sprungtranspositionen erkennt.
Beweis Es existiert ein Element (;1 x) 2 Ds, so da
;g1(1 0) = g1 (;1 x) gilt,
denn sonst hatten wir mindestens s +1 Elemente mit dem gleichen Vorzeichen und
g ware keine Permutation. In Zs existiert ein multiplikativ Inverses von 2, namlich
1=2 = k + 1, wenn s = 2k + 1 ist. Wir setzen
;
;
c := 1 1=2 g1(;1 x) g1(1 0)x + g2(1 0) ; g2(;1 x)
3.3. ANTI-SYMMETRISCHE ABBILDUNGEN DER DIEDERGRUPPE
55
und es folgt
;
;
g(1 0) c (;1 x) = ;g1(1 0) g2(1 0) 1 1=2 g1 (;
1 x;) ;g1(1 0)x + g2(1 0) ; g2(;1 x) ; 1 x
= g1(1 0) g1(1 0) 1=2 g1(;1 x) ;
;
g
1 (1 0)x + g2 (1 0) ; g2 (;1 x) + g2 (1 0) ; 1 x
;
= ; g1(1 0) g1(1 0)x + g1(1 0) 1=2 g1(;1 x) ;
g1(1 0)x + g2(1 0) ; g2(;1 x) + g2(1 0)
;
;
= ; g1(1 0) 1=2 g1(1 0)x + g2(1 0) + g2(;1 x)
g(;1 x) c (1 0) = g; (;1 x) c
;
= g1(;1 x) g2(;1 x) 1 1=2 g1(;1 x) ;
g1(1 0)x + g2(1 0) ; g2(;1 x)
;
= g1(;1 x) g1(;1 x) 1=2 g1(;1 x) ;
g1(1 0)x + g2(1 0) ; g2(;1 x) + g2(;1 x)
;
;
= ; g1(1 0) 1=2 g1(1 0)x + g2(1 0) + g2(;1 x)
also g(1 0) c (;1 x) = g(;1 x) c (1 0) und g(x) c ist nicht anti-symmetrisch.
Au
erdem erkennt g nicht alle Sprungtranspositionen (vgl. Seite 14). 2
Zusammen mit Korollar 4 (Seite 19) haben wir damit gezeigt:
Theorem 10 Sei s > 2 ungerade. Uber der Gruppe Ds existiert kein Prufziffersystem, das alle Sprungtranspositionen oder alle Zwillings- oder alle Sprungzwillingsfehler erkennt.
3.3.2 Automorphismen und Anti-Automorphismen der
Diedergruppe
Die Automorphismen und die Anti-Automorphismen sind bei der Bestimmung der
A quivalenzklassen bzw. bei der Suche nach anti-symmetrischen Abbildungen sehr
wichtig. Fur die Diedergruppe Ds, s > 2, kann man diese recht einfach bestimmen.
Dazu nutzt man aus, da
die Diedergruppe von den Elementen (1 1) und (;1 0)
erzeugt wird. Das Element (1 1) hat in Ds die Ordnung s und (;1 x) hat fur alle
x die Ordnung 2. Da fur jeden Automorphismus oder Anti-Automorphismus '
die Elemente '(x) und x die gleiche Ordnung haben, mu
'(1 1) = (1 d) fur ein
d 2 Zs gelten. d mu
dabei eine Einheit des Ringes Zs sein, d.h. ggT (d s) = 1,
sonst hatte (1 d) nicht die Ordnung s. Ebenso folgt, da
'(;1 0) = (;1 c)
ist mit c 2 Zs, denn andernfalls wurde ' alle Elemente auf die Untergruppe
56
KAPITEL 3. GRUPPEN MIT VORZEICHEN
f(1 x)jx 2 Zsg abbilden und ' ware demnach nicht surjektiv. Wie wir bereits
gezeigt haben, reicht es, die Automorphismen einer Gruppe zu bestimmen, denn
die Anti-Automorphismen lassen sich durch inv ' darstellen, wobei ' ein Automorphismus ist. Mit der Verknupfung (e x) (f y) = (ef ey + x) der Diedergruppe
erhalten wir die folgenden Eigenschaften des Automorphismus ':
1. '(1 x) = '(1 1)x = (1 d)x = (1 dx), fur alle x 2 Zs.
2. '(;1 x) = '((1 x) (;1 0)) = '(1 x) '(;1 0) = (1 dx) (;1 c) = (;1 c +
dx), fur alle x 2 Zs.
Die Eigenschaften 1 und 2 sind also notwendig dafur, da
' ein Automorphismus
ist. Sie sind aber auch hinreichend. Dazu seien d eine Einheit von Zs, c ein
Element von Zs und ' : Ds ! Ds eine Abbildung mit '(1 x) = (1 dx), '(;1 x) =
(;1 c + dx). Mit dieser Denition ist ' bijektiv, denn aus '(e x) = '(f y) folgt
e = f und dx = dy bzw. c + dx = c + dy und damit, weil d eine Einheit ist, x = y.
Also ist ' injektiv und damit auch surjektiv (Ds ist endlich). ' ist au
erdem ein
Homomorphismus, denn es gilt fur alle x y 2 Zs:
- '((1 x) (1 y)) = '(1 x + y) = (1 dx + dy) = (1 dx) (1 dy) = '(1 x) '(1 y)
- '((1 x) (;1 y)) = '(;1 y + x) = (;1 c + dy + dx) = (1 dx) (;1 c + dy) =
'(1 x) '(;1 y)
- '((;1 x) (1 y)) = '(;1 ;y + x) = (;1 c ; dy + dx) = (;1 c + dx) (1 dy) =
'(;1 x) '(1 y)
- '((;1 x) (;1 y)) = '(1 ;y + x) = (1 ;dy + dx) = (;1 c + dx) (;1 c +
dy) = '(;1 x) '(;1 y)
Also ist ' ein Automorphismus.
Damit haben wir fur die Anti-Automorphismen der Diedergruppe die Darstellung
inv '(1 x) = (1 dx);1 = (1 ;dx)
inv '(;1 x) = (;1 c + dx);1 = (;1 c + dx):
Der folgende Satz fa
t dieses Ergebnis zusammen:
Satz 27 Seien ' : Ds ! Ds Abbildungen der Diedergruppe Ds,s > 2, dann gilt:
1. Genau dann ist ' ein Automorphismus, wenn eine Einheit d und ein Element
c von Zs existieren mit '(1 x) = (1 dx) und '(;1 x) = (;1 c + dx).
3.3. ANTI-SYMMETRISCHE ABBILDUNGEN DER DIEDERGRUPPE
57
2. Genau dann ist ein Anti-Automorphismus, wenn eine Einheit d und ein
Element c von Zs existieren mit (1 x) = (1 ;dx) und (;1 x) = (;1 c +
dx).
Wenn s ungerade ist, d.h. s = 2k + 1, dann besitzt 2 ein multiplikativ Inverses, namlich 1=2 = k + 1. Die Funktion (1 ; e)=2 ist dann gleich 0, wenn e = 1
ist und gleich 1, wenn e = ;1 ist. Die Automorphismen der Diedergruppe Ds
haben daher fur s > 2 ungerade alle die Form '(e x) = (e (1 ; e)=2 c + dx) =
(e (1 ; e)~c + dx) = (e c~ ; ec~ + dx) und die Anti-Automorphismen haben die Form
(e x) = (e c~ ; ec~ ; edx) mit d 2 Zs und c~ 2 Zs.
Damit konnen wir die folgenden Satze zeigen:
Satz 28 Die Diedergruppe Ds s > 2 besitzt keinen anti-symmetrischen Automor-
phismus und sie besitzt einen xpunktfreien, d.h. anti-symmetrischen, Anti-Automorphismus genau dann, wenn s ungerade ist.
Beweis Ist s gerade, dann ist s=2 das einzige Element der Ordnung 2 in Zs. Da
jeder (Anti-)Automorphismus die Ordnung und das Vorzeichen e = sgn(e x)
erhalt, gilt (1 s=2) = (1 s=2) und ist nicht anti-symmetrisch.
Ist s ungerade, dann kommutiert (1 1) mit keinem Element der Ordnung 2,
(1 1) (;1 x) = (;1 x + 1) 6= (;1 x ; 1) = (;1 x) (1 1), und damit ist
(x) = (1 ;1) x;1 (1 1) ein xpunktfreier Anti-Automorphismus. Ist ' ein
Automorphismus mit '(;1 0) = (;1 c), dann denieren wir z := (;1 1=2 c)
und es folgt
'(;1 0) = (;1 c) = (;1 1=2 c + 1=2 c)
= (;1 1=2 c)(;1 0)(;1 1=2 c)
= z;1 (;1 0)z:
Also ist ' nicht anti-symmetrisch (Satz 8, Seite 35). 2
Satz 29 Sei ein Anti-Automorphismus der Diedergruppe Ds, d.h. (1 x) =
(1 dx) und (;1 x) = (;1 c ; dx) mit c 2 Zs, d 2 Zs, dann ist genau dann
xpunktfrei, wenn d ; 1 eine Einheit und d + 1 kein Teiler von c (in Zs) ist.
Beweis Wenn einen Fixpunkt (1 x) 6= (1 0) oder (;1 x) besitzt, dann gilt
(1 x) = (1 dx) = (1 x) oder (;1 x) = (;1 c ; dx) = (;1 x). Im ersten Fall
folgt dx = x bzw. (d ; 1)x = 0 und d ; 1 ist keine Einheit. Im zweiten Fall ist
c ; dx = x also c = (d + 1)x und d + 1 teilt c. Da nur A quivalenzumformungen
benutzt wurden, folgt damit auch die Ruckrichtung. 2
Beispiel Fur die Diedergruppe D5 konnen wir c = 1 2 3 4 und d = 4 wahlen.
58
KAPITEL 3. GRUPPEN MIT VORZEICHEN
3.3.3 Beispiele
In diesem Abschnitt geben wir verschiedene Literatur-Beispiele von anti-symmetrischen Abbildungen der Diedergruppe an und zeigen, da
diese Spezialfalle der
bisher erarbeiteten Satze darstellen. Mit diesen Satzen gelingt uns jeweils ein deutlich kurzerer Beweis der Behauptungen.
Beispiel (Verhoeff 27]) Deniere ' durch '(ak ) = a;k und '(aj b) = aj;db,
d 6= 0, dann ist ' 2 Ant(Ds ), s ungerade.
Beweis Wir schreiben ' zunachst in der Matrixschreibweise: '(1 k) = (1 ;k)
und '(;1 j ) = (;1 j ; d). Es folgt, da
'(e x) = (1 ;1=2 d) (e x);1 (1 1=2 d)
ist, denn
(1 ;1=2 d) (e x);1 (1 1=2 d) = (1 ;1=2 d) (e ;ex) (1 1=2 d)
= ((e ;ex ; 1=2 d + 1=2 ed)
(1 ;x)
falls e = 1
=
(;1 x ; d) falls e = ;1:
Nach Satz 20 (Seite 52) ist damit ' eine anti-symmetrische Abbildung von D5 .
2 Zs, s ungerade, a 6= 0 ist '(e x) :=
(e e(a ; x) + b) 2 Ant(Ds).
Beweis Es ist '(e x) = (1 b)(e x); (1 a) = (1 b)(e ;ex)(1 a) = (e ;ex + b +
ea) = (e e(a ; x) + b) und wir konnen wieder Satz 20 anwenden.
Beispiel (H.P.
Gumm 12]) Fur a b
1
Beispiel (Gallian/Mullin 10]) Die im Beweis von Theorem 3 (Seite 22) de-
nierte Abbildung der Diedergruppe Dn, n ungerade, in Matrixschreibweise lautet
'(1 x) = (1 2 ; x), '(;1 x) = (;1 x). Mit a = b = 1 ist dies ein Spezialfall des
vorherigen Beispiels.
Beispiel (Steven J. Winters 28]) Fur jede ungerade Zahl s > 2 deniere die
Permutation (Zyklenschreibweise)
' = (0)(1 s ; 1)(2 s ; 2) : : : ( s ;2 1 s +2 1 )(s s + 1 : : : 2s ; 1):
Dann ist ' eine anti-symmetrische Abbildung von Ds.
Beweis Die Matrixschreibweise dieser Permutation lautet
'(e x) =
(
(1 ;x)
falls e = 1
(;1 x + 1) falls e = ;1:
3.3. ANTI-SYMMETRISCHE ABBILDUNGEN DER DIEDERGRUPPE
59
Fur d = ;1 stimmt diese Permutation mit der von Verhoeff gefundenen uberein.
Beispiel Die elfstelligen Seriennummern der deutschen Banknoten werden mit der
Permutation ' = 1576283094] = 7046913258];1 (vgl. Seite 100) gesichert 21].
Die Nummern enthalten an den Positionen 1,2 und 10 statt Ziern Buchstaben.
Diese werden vor der Prufung gema
folgender Tabelle umgesetzt:
A D G K L N S U Y Z
0 1 2 3 4 5 6 7 8 9
Die Prufgleichung lautet
'(x10 ) '2(x9 ) : : : '10 (x1 ) x0 = 0:
Ware die vorletzte Stelle der Seriennummer kein Buchstabe, sondern eine Zier,
dann wurde das Verfahren nicht alle Vertauschungen von x0 mit x1 erkennen.
Aber durch den Buchstaben besteht keine Verwechslungsgefahr. Bei der benutzten
Prufgleichung ist nicht ', sondern ';1 eine anti-symmetrische Abbildung, da die
Potenzen von ' aufsteigend gewahlt wurden.
Fur die Seriennummer DG2661778N1 eines 10-DM Scheines ergibt sich beispielsweise
Seriennummer
DG2661778N1
codierte Zahl
12266177851
10
'(x10 ) : : : ' (x1 ) x0 50163727991
Die Diedermultiplikation liefert 5 0 1 6 3 7 2 7 9 9 1 = 0, d.h. die
Seriennummer ist gultig.
60
KAPITEL 3. GRUPPEN MIT VORZEICHEN
Kapitel 4
Prufziersysteme uber
Quasigruppen
In diesem Kapitel verallgemeinern wir den Begri des Prufziersystems auf Quasigruppen. Wir untersuchen verschiedene Ansatze und geben am Ende Prufziersysteme zu den Basen 6, 8 und 10 an, die eine bessere oder zumindest gleich gute
Fehlererkennung bieten, wie Prufziersysteme basierend auf Gruppen. Au
erdem
zeigen wir, da
eine Reihe von Quasigruppen keine bessere Fehlererkennung bieten
konnen als Prufziersysteme uber Gruppen.
4.1 Allgemeine Ergebnisse
Wir stellen zuerst zwei Moglichkeiten vor, wie der Begri "Prufziersystem" verallgemeinert werden kann.
Denition 9 Sei D = f0 : : : m ; 1g eine Menge von Ziern, c 2 D und g :
Dn+1 ! D eine Abbildung. Die Menge Pgc := f(dn : : : d0) 2 Dn+1jg(dn : : : d0) =
cg hei
t implizites Prufziersystem zur Basis m, wenn gilt:
1. g (dn : : : di : : : d0) = g (dn : : : d0i : : : d0 ) = c impliziert di = d0i
2. g (dn : : : di di;1 : : : d0 ) = g (dn : : : di;1 di : : : d0) = c impliziert di = di;1
3. fur alle dn : : : d1 2 D existiert ein d0 2 D s.d. g(dn : : : d1 d0 ) = c
oder, vgl. H.P. Gumm 12]
Denition 10 Sei D = f0 : : : m ; 1g eine Menge von Ziern und f : Dn ! D
eine Abbildung. Die Menge Pf0 := f(dn : : : d0 ) 2 Dn+1jf (dn : : : d1 ) = d0 g hei
t
explizites Prufziersystem zur Basis m, wenn gilt:
1. f (dn : : : di : : : d1 ) = f (dn : : : d0i : : : d1 ) impliziert di = d0i
61
62
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
2. f (dn : : : di di;1 : : : d1) = f (dn : : : di;1 di : : : d1 ) impliziert di = di;1
3. f (dn : : : d2 d0 ) = d1 , wobei f (dn : : : d1 ) = d0 , impliziert d0 = d1
Bei den impliziten Prufziersystemen ist die Prufzier d0 einer vorgegebenen
Zahl dndn;1 : : : d1 die eindeutig bestimmte Losung der Gleichung g(dn : : : d1 d0) =
c. Dabei garantiert uns die dritte Eigenschaft, da
uberhaupt eine Losung existiert,
mit der ersten Eigenschaft folgt deren Eindeutigkeit. Die zweite Eigenschaft sorgt
fur die Erkennung aller Nachbarvertauschungen.
Die expliziten Prufziersysteme haben den Vorteil, da
sich die Prufzier nicht als
Losung einer Gleichung ergibt, sondern da
diese direkt durch f (dn : : : d1) ausgerechnet werden kann. Die dritte Eigenschaft dient hier dazu, die Vertauschung
der letzten Zier mit der Prufzier zu erkennen.
Beide Denitionen lassen es auch zu, eine Prufzier zu bestimmen, die in die
ursprungliche Zahl an einer Position i eingebaut wird. Dazu bestimmt man die
eindeutige Losung p der Gleichung
g(dn : : : di+1 p di : : : d1) = c
bzw.
f (dn : : : di+1 p di : : : d2) = d1:
Die gesicherte Zahl lautet in beiden Fallen dndn;1 : : : di+1pdi : : : d2d1 .
Die Denitionen sind im folgenden Sinne aquivalent: Zu jedem expliziten Prufziffersystem Pf0 erhalt man ein implizites Prufziersystem Pgc mit der Eigenschaft
f (dn : : : d1) = d0 , g(dn : : : d0) = c (und damit Pf0 = Pgc) durch die Denitionen c := 0 und
(
g(dn : : : d0) := 0 falls f (dn : : : d1) = d0
1 sonst
Und umgekehrt erhalt man zu jedem impliziten Prufziersystem Pgc ein explizites Prufziersystem Pf0 indem man f (dn : : : d1) durch die eindeutig bestimmte
Losung x der Gleichung g(dn : : : d1 x) = c deniert, also
f (dn : : : d1) := x , g(dn : : : d1 x) = c:
Schwieriger ist die Losung des folgenden Problems: Wenn f eine bestimmte
Darstellung (z.B. mit Quasigruppen) besitzt, gibt es dann auch ein g, das eine
analoge Darstellung mit der Eigenschaft
f (dn : : : d1) = d0 , g(dn : : : d0) = c
(4.1)
besitzt? Fur das genannte Beispiel kann man die Fragestellung positiv beantworten, wie der folgende Satz zeigt:
4.2. N-QUASIGRUPPEN
63
Satz 30
1. Zu jedem expliziten Prufziersystem Pf0 , wobei f eine Darstellung
mit n ; 1 Quasigruppen i besitzt, f (dn : : : d1) = (: : : ((dn n dn;1 ) n;1
dn;2) n;1 : : : ) 2 d1 , existiert eine Quasigruppe 1 und ein c 2 D, so da
4.1 fur g(dn : : : d0) := f (dn : : : d1) 1 d0 = (: : : ((dn n dn;1) n;1 dn;2) n;1
: : : ) 1 d0 gilt.
2. Zu jedem impliziten Prufziersystem Pgc, wobei g eine Darstellung mit n
Quasigruppen i besitzt, g(dn : : : d0 ) = (: : : ((dn n dn;1) n;1 dn;2) n;1
: : : ) 1 d0, existiert eine Quasigruppe 02, so da
4.1 fur f (dn : : : d1) :=
((: : : ((dn n dn;1) n;1 dn;2) n;1 : : : ) 3 d2) 02 d1 gilt.
Beweis Mit x 1 y := x ; y (Rechnung in der Gruppe Zm) und c := 0 folgt Behauptung 1. 02 wird durch die Bedingung x 02 y = z , (x 2 y) 1 z = c deniert. Damit
folgt Behauptung 2. (Das 02 eine Quasigruppe ist, folgt aus den Kurzungsregeln
der Quasigruppen 2 und 1, siehe unten)
Sollen allerdings alle benutzten Quasigruppen gleich sein, so fuhren die unterschiedlichen Denitionen i.allg. auch zu unterschiedlichen Codewortern:
Beispiel Seien D := f0 : : : 6g, f (x y) := x ; 2y, g(x y z) := (x ; 2y) ; 2z und
c := 0. Es gilt f (5 2) = 1, aber g(5 2 1) = ;1 6= 0 = g(5 2 4), d.h. im ersten
Fall ist 52-1, im zweiten Fall 52-4 die gesicherte Zahl.
4.2 n-Quasigruppen
Zunachst denieren wir einige Grundbegrie.
Denition 11 Eine Quasigruppe ist eine Algebra (Q ) mit der Eigenschaft, da
die Gleichungen a x = b und y a = b fur jedes Paar a b eine eindeutige Losung
x, bzw. y besitzen.
Eine n-Quasigruppe ist eine Algebra (Q f ), f : Qn ! Q, so da
fur i =
1 : : : n und alle xn : : : xi+1 xi;1 : : : x1 x0 2 Q die Gleichung
f (xn : : : xi+1 x xi;1 : : : x1) = x0
eine eindeutig bestimmte Losung x 2 Q besitzt.
Bemerkung Die Quasigruppen sind ein Spezialfall der n-Quasigruppen. Sie werden daher im Zusammenhang mit n-Quasigruppen als binare Quasigruppen bezeichnet.
Bekanntlich ist ein endlicher Gruppoid genau dann eine Quasigruppe, wenn in
ihm die Kurzungsregeln a x = a y ) x = y und x a = y a ) x = y gelten.
64
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Denition 12 Zwei n-Quasigruppen f g sind isotop, falls Permutationen ,
n : : : 1 existieren mit
(f (xn : : : x1 )) = g(n(xn) : : : 1(x1 ))
sie hei
en isomorph, falls = n = : : : = 1 gilt.
Bemerkung Isotopie und Isomorphie denieren eine A quivalenzrelation auf der
Menge der n-Quasigruppen.
Denition 13 Die Parastrophie f einer n-Quasigruppe f und der Permutation
2 Sn+1 wird deniert durch
f (xn : : : x1) = x0
,
f(x(n) : : : x(n) ) = x(0) :
Sie hei
t hauptsachlich wenn (0) = 0 ist.
Oensichtlich sind die Parastrophien einer n-Quasigruppe wieder eine n-Quasigruppe. Fur eine Quasigruppe (Q ) denieren wir speziell:
x t y = z
x=y = z
xny = z
x=t y = z
x nt y = z
,
,
,
,
,
yx=z
y =xz
x=zy
x=yz
y =zx
Es gilt x=(x y) = y, x (x=y) = y und (x y)ny = x, (xny) y = x.
Denition 14 Die Quasigruppen (Q ) und (Q ) hei
en orthogonal, wenn die
Paare (x y x y ) fur alle x y 2 Q paarweise verschieden sind. Eine Quasigruppe
(Q ) hei
t selbstorthogonal, wenn sie orthogonal zu (Q t) ist.
Lemma 15 Zwei endliche Quasigruppen (Q ) und (Q ) der Ordnung m sind
genau dann orthogonal, wenn fur alle a b 2 Q die Gleichungen x y = a, x y = b
eine eindeutig bestimmte Losung x y 2 Q besitzen.
Beweis Seien (Q ) und (Q ) orthogonal, und es gelten die Gleichungen x0 y0 =
x y = a, x0 y0 = x y = b. Dies ist aquivalent zur Gleichheit der Paare (x0 y0 x0 y0)
und (x y x y). Die Paare sind aber nach Voraussetzung genau dann gleich, wenn
x = x0 und y = y0 gilt. Also ist die Losung der Gleichungen eindeutig.
Wir mussen noch zeigen, da
die Gleichungen uberhaupt eine Losung besitzen.
Da die Paare (x y x y) alle verschieden sind, haben wir m2 verschiedene Paare.
Folglich mu
es fur jedes Paar (a b) Elemente x y 2 Q mit (x y x y) = (a b)
geben. Die Ruckrichtung folgt analog. 2
4.2. N-QUASIGRUPPEN
65
Fur die Verknupfungstafel einer Quasigruppe ist der Begri lateinisches Quadrat ublich. Lateinische Quadrate hei
en orthogonal, wenn ihre zugehorigen Quasigruppen orthogonal sind. Die orthogonalen lateinischen Quadrate spielen im
Zusammenhang mit den endlichen a!nen Ebenen eine wichtige Rolle.
Beispiel 1. Die folgenden beiden Quasigruppen sind orthogonal.
0
0 0
1 2
2 1
1
1
0
2
2
2
1
0
0
0 0
1 1
2 2
1
1
2
0
2
2
0
1
;!
1
2
( ) 0
0 (0,0) (1,1) (2,2)
1 (2,1) (0,2) (1,0)
2 (1,2) (2,0) (0,1)
2. Die folgende Quasigruppe ist selbstorthogonal.
t 0 1 2 3
0 1 2 3
0 0 1 2 3
0 0 2 3 1
1 2 3 0 1
1 1 3 2 0
2 3 2 1 0
2 2 0 1 3
3 1 0 3 2
3 3 1 0 2
Orthogonale lateinische Quadrate wurden zuerst von Euler Ende des 18.
Jahrhunderts untersucht. Fur das Kreuzprodukt zweier orthogonaler lateinischer
Quadrate benutzte er den Begri "Griechisch-Lateinisches-Quadrat", da er fur das
eine Quadrat griechische und fur das andere lateinische Buchstaben verwendete.
Griechisch-Lateinische-Quadrate werden aus diesem Grund auch Euler-Quadrate
genannt.
Denition 15 Eine Quasigruppe (Q ) ist anti-symmetrisch, wenn xy = y x )
x = y gilt. Analog hei
t eine n-Quasigruppe anti-symmetrisch, wenn
f (xn : : : xi xi;1 : : : x1 ) = f (xn : : : xi;1 xi : : : x1 ) ) xi = xi;1:
Denition 16 Eine Permutation ' einer Quasigruppe (Q ) hei
t anti-symmetrische bzw. vollstandige Abbildung, falls gilt:
'(x) y = '(y) x
bzw.
';1(x) x = ';1 (y) y
)
)
x=y
x = y:
Die Menge aller anti-symmetrischen bzw. vollstandigen Abbildungen einer Quasigruppe werde mit Ant(Q ) bzw. Com(Q ) bezeichnet.
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
66
Bemerkung Die zweite Eigenschaft ist aquivalent zu
x '(x) = y '(y)
)
x = y:
Die Denition der vollstandigen Abbildungen stimmt also mit der fur Gruppen
getroenen Denition uberein.
Denition 17 Sei f eine n-Quasigruppe dann wird die n-Quasigruppe f^ deniert
durch
f^(xn : : : x1 ) = x0 , f (x0 x1 : : : xn;1) = xn
Wir zeigen nun den Zusammenhang zwischen n-Quasigruppen und Prufziersystemen.
Satz 31
1. Jede n-Quasigruppe erkennt alle Einzelfehler. Wenn g eine antisymmetrische n-Quasigruppe ist, so deniert Pgc ein implizites Prufziffersystem fur alle c 2 D.
2. Pf0 ist ein explizites Prufziersystem genau dann, wenn Pf0^ ein explizites
Prufziersystem ist.
3. Pf0 ist genau dann ein explizites Prufziersystem, wenn f und f^ anti-symmetrische n-Quasigruppen sind.
Beweis 1) Folgt direkt aus den Denitionen.
2) Da (f^^) = f gilt, reicht es, eine Richtung zu zeigen. Sei Pf0 ein Prufziersystem.
f^ ist eine n-Quasigruppe und erkennt daher alle Einzelfehler. Es gelte nun
f^(dn : : : di di;1 : : : d1) = d0 = f^(dn : : : di;1 di : : : d1)
oder
f^(dn : : : d1) = d0 f^(dn : : : d2 d0) = d1:
Es folgt
f (d0 : : : di;1 di : : : dn;1) = dn = f (d0 : : : di di;1 : : : dn;1), falls i < n
und
f (d0 : : : dn;1) = dn, f (d0 : : : dn;2 dn) = dn;1, falls i = n:
Mit den Eigenschaften von f folgt nun, da
di = di;1 ist. Also ist Pf0^ ein Prufziffersystem.
3) Sei Pf0 ein Prufziersystem. Aus 2) folgt, da
auch Pf0^ ein Prufziersystem ist
4.2. N-QUASIGRUPPEN
67
und damit f und f^ anti-symmetrische n-Quasigruppen sind. Sind umgekehrt f
und f^ anti-symmetrische n-Quasigruppen so sind die Bedingungen 1 und 2 der
Denition 10 (Seite 61) fur f erfullt. Bedingung 3 folgt aus der Anti-Symmetrie
von f^:
,
,
f (dn : : : d2 d1) = d0 f (dn : : : d2 d0) = d1
f^(d0 d1 : : : dn;1) = f^(d1 d0 d2 : : : dn;1)
d0 = d1:
2
Lemma 16 Sei (Q f ) eine anti-symmetrische n-Quasigruppe und ' Permuta-
tionen von Q, dann ist auch (Q f) mit
f(xn : : : x1) := ;1 (f ('(xn) : : : '(x1 )))
anti-symmetrisch.
Beweis Aus f(xn : : : xi;1 xi : : : x1 ) = f(xn : : : xi xi;1 : : : x1) folgt
f ('(xn) : : : '(xi) '(xi;1) : : : '(x1 )) = f ('(xn) : : : '(xi;1 ) '(xi) : : : '(x1 )):
Da (Q f ) anti-symmetrisch ist, folgt '(xi) = '(xi;1 ) und damit xi = xi;1 : 2
Der folgende Satz stellt einen Zusammenhang zwischen anti-symmetrischen
Abbildungen und anti-symmetrischen Quasigruppen her:
Satz 32 Eine Quasigruppe, und insbesondere eine Gruppe, besitzt eine anti-sym-
metrische Abbildung genau dann, wenn sie isotop zu einer anti-symmetrischen
Quasigruppe ist.
Beweis Die Quasigruppe (Q ) besitze die anti-symmetrische Abbildung ', dann
ist (Q ) mit x y := '(x) y eine anti-symmetrische Quasigruppe. Sei umgekehrt
die anti-symmetrische Quasigruppe (Q ) isotop zur Quasigruppe (Q ), also (x y) = (x) (y) mit den Permutationen . Die Quasigruppe xy := ( ;1(x)
;1(y)) ist wieder anti-symmetrisch (Lemma 16 fur n = 2). Es folgt, da
;1
eine anti-symmetrische Abbildung von (Q ) ist, denn
xy =
=
=
=
=
( ;1(x) ;1(y))
(
;1 (( ;1(x)) ( ;1(y))))
;1(x) y
;1(y) x
yx
68
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
ist nur erfullt wenn x = y ist. 2
Satz 33 In einer Isotopieklasse besitzt entweder jede oder keine Quasigruppe eine
anti-symmetrische bzw. vollstandige Abbildung.
Beweis Aus dem vorherigen Satz folgt, da
jede Quasigruppe, die isotop ist zu
einer Quasigruppe mit anti-symmetrischer Abbildung, ebenfalls eine anti-symmetrische Abbildung besitzt.
Sei (Q ) eine Quasigruppe mit vollstandiger Abbildung ';1 und (Q ) mit
x y = ;1((x) (y)) sei isotop zu (Q ), dann ist '~;1 := ;1 ';1 eine
vollstandige Abbildung von (Q ): Aus
'~(x) x = ;1(('~(x)) (x)) = ;1(('~(y)) (y)) = '~(y) y
folgt
';1( (x)) (x) = ';1( (y)) (y):
';1 ist eine vollstandige Abbildung von (Q ), also folgt (x) = (y) und damit x = y. 2
Denition 18 Eine Quasigruppe besitzt die Transversale ('1 '2), wenn '1 '2
und '1(x) '2(x) Permutationen sind.
Lemma 17 Eine Quasigruppe besitzt eine vollstandige Abbildung genau dann,
wenn sie eine Transversale besitzt.
Beweis Ist ('1 '2) eine Transversale, so ist '2 ';1 1 eine vollstandige Abbildung.
Andererseits erhalten wir durch die vollstandige Abbildung ' die Transversale
(Id '). 2
Wenn die Quasigruppe (Q ) die anti-symmetrische bzw. vollstandige Abbildung ' besitzt, dann ist ';1 eine anti-symmetrische bzw. vollstandige Abbildung
der Parastrophie (Q t). Fur vollstandige Abbildungen gilt au
erdem:
Lemma 18 (vgl. Belousov 4]) Besitzt die Quasigruppe (Q ) eine vollstandige
Abbildung, dann gilt dies auch fur jede Parastrophie von (Q ).
Beweis Wir zeigen die Behauptung mit Lemma 17. (Q ) besitze die Transversale ('1 '2). Wir denieren die Permutation '3 durch '3(x) := '1 (x) '2(x).
Damit ist ('1 '3) eine Transversale der Parastrophie (Q =), denn '1 (x)='3(x) =
'1 (x)=('1(x) '2(x)) = '2(x) ist eine Permutation. Die Behauptung fur die anderen Parastrophien folgt analog. 2
4.3. REDUZIBLE N -QUASIGRUPPEN
69
4.3 Reduzible n-Quasigruppen
In diesem Abschnitt geben wir ein Kriterium an, mit dem wir entscheiden konnen,
ob eine n-Quasigruppe eine Darstellung mit binaren Quasigruppen hat.
Denition 19 (vgl. 6]) Eine n-Quasigruppe (Q f ), n > 2 hei
t reduzibel wenn
eine Permutation 2 Sn und Quasigruppen g : Qn;k+1
(1 k < n ; 1) existieren mit
! Q, h : Qk ! Q
x0 = f (xn : : : x1 ) = g(x : : : x +1 h(x : : : x1 )):
n
k
k
Sie hei
t total reduzibel wenn n ; 1 binare Quasigruppen (Q gi), i = 1 : : : n ; 1
existieren, so da
f als Komposition der gi dargestellt werden kann. Eine nQuasigruppe hei
t irreduzibel wenn sie nicht reduzibel ist.
Theorem 11 ( Verhoeff 27]) Es existieren irreduzible n-Quasigruppen.
Man konnte vermuten, da
die Anti-Symmetrie-Eigenschaft verhindert, da
eine n-Quasigruppe irreduzibel ist. Dies ist allerdings nicht der Fall, wie folgendes
Theorem zeigt:
Theorem 12 Es existieren irreduzible anti-symmetrische n-Quasigruppen.
Beweis Die folgende 3-Quasigruppe f ist irreduzibel und anti-symmetrisch:
=
j=0
1
2
3
4
5
k
012345
012345
201453
120534
453012
534201
345120
i=0
012345
120534
012345
201453
345120
453012
534201
1
012345
201453
120534
012345
534201
345120
453012
2
012345
345120
534201
453012
012453
120345
201534
3
012345
453012
345120
534201
201534
012453
120345
4
012345
534201
453012
345120
120345
201534
012453
5
Wenn f (i j k) zerlegbar ware in g(i j ) und h(i j ), dann wurde gelten
1. f (i j k) = g(i h(j k)) oder
2. f (i j k) = g(j h(i k)) oder
3. f (i j k) = g(k h(i j )).
Im ersten Fall folgt aus f (i j k) = f (i j 0 k0), da
h(j k) = h(j 0 k0) und folglich,
da
f (i0 j k) = f (i0 j 0 k0). Es gilt aber f (0 0 0) = f (0 3 3) = 0 und f (3 0 0) =
3 6= 4 = f (3 3 3). Analog folgt im zweiten bzw. dritten Fall, da
f (i j k) =
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
70
f (i0 j k0) ) f (i j 0 k) = f (i0 j 0 k0) bzw. f (i j k) = f (i0 j 0 k) ) f (i j k0 ) =
f (i0 j 0 k0). Es gilt aber f (0 0 0) = f (1 0 2) = 0, f (0 3 0) = 4 6= 5 = f (1 3 2)
und f (0 0 0) = f (3 3 0) = 0, f (0 0 3) = 3 6= 4 = f (3 3 3).
Da
diese 3-Quasigruppe die Vertauschungen j $ k erkennt, la
t sich leicht
an den anti-symmetrischen Quasigruppen f (0 j k) : : : f (5 j k) ablesen. Wenn
wir eine andere Projektionsebene wahlen, dann sieht man ebenso, da
auch die
Quasigruppen f (i j 0) : : : f (i j 5) anti-symmetrisch sind.
i=
j=0
1
2
3
4
5
012345
012345
201534
120453
435021
543102
354210
k=0
012345
120453
012345
201534
543102
354210
435021
1
012345
201534
120453
012345
354210
435021
543102
2
012345
354102
435210
543021
012453
201345
120534
3
012345
435210
543021
354102
120534
012453
201345
4
012345
543021
354102
435210
201345
120534
012453
5
Damit ist f eine irreduzible anti-symmetrische 3-Quasigruppe. 2
Verhoeff 27] gab ein Beispiel fur eine irreduzible 3-Quasigruppen bereits fur
m = 4 an. Diese deniert aber kein Prufziersystem, da sie nicht anti-symmetrisch
ist.
Eine interessante Anwendungsmoglichkeit der irreduziblen n-Quasigruppen ergibt sich aus der Tatsache, da
man mit einer kleinen Anzahl gesicherter Zahlen
nicht auf das verwendete Prufziersystem schlie
en kann. Damit kann man verhindern, da
absichtlich falsche Zahlen (z.B. Kreditkartennummern) mit gultiger
Prufzier eingegeben werden.
Im folgenden beschaftigen wir uns mit reduziblen n-Quasigruppen.
Satz 34 Wenn das explizite Prufziersystem Pf0 auf der (total) reduziblen n-Quasi-
gruppe f beruht, dann existiert ein aquivalentes implizites Prufziersystem Pgc,
bei dem g eine (total) reduzible n + 1-Quasigruppe ist. Die Umkehrung gilt im
allgemeinen nicht.
Beweis Wir denieren
g(dn : : : d1 d0) := f (dn : : : d1) ; d0
und c = 0. Damit folgt der erste Teil der Behauptung. Sei nun Pf0 ein explizites
Prufziersystem und f eine irreduzible n-Quasigruppe. Dann ist g eine, oensichtlich reduzible, n + 1-Quasigruppe. Wenn eine n-Quasigruppe f~ mit
f~(dn : : : d1) = d0 , g(dn : : : d0) = 0
4.3. REDUZIBLE N -QUASIGRUPPEN
71
existiert, dann folgt, da
f~(dn : : : d1) = d0 = f (dn : : : d1) und damit f = f~ gilt.
Also ist f~ irreduzibel und es existiert kein reduzibles explizites Prufziersystem,
das aquivalent zu Pgc ist. 2
Theorem 13 Sei f eine n-Quasigruppe uber der Menge Q und cn;2 : : : c1 2 Q
beliebige, aber fest gewahlte Konstanten. Es gibt Quasigruppen i, i = 2 : : : n mit
f (xn : : : x1 ) = (: : : ((xn n xn;1) n;1 xn;2 ) n;1 : : : ) 2 x1
genau dann, wenn fur i = 1 : : : n ; 2 gilt
f (xn : : : xi+1 ci ci;1 : : : c1) = f (x0n : : : x0i+1 ci ci;1 : : : c1)
) f (xn : : : xi+1 x ci;1 : : : c1) = f (xn0 : : : x0i+1 x ci;1 : : : c1)
Beweis Es gelte f (xn : : : x1) = (: : : ((xn n xn;1 ) n;1 xn;2) n;1 : : : ) 2 x1 fur
die Quasigruppen i. Aus
f (xn : : : xi+1 ci ci;1 : : : c1) = f (x0n : : : x0i+1 ci ci;1 : : : c1)
folgt mit Hilfe der Kurzungsregel fur die Quasigruppen j , j = 2 : : : i + 1
(: : : (xn n xn;1 ) n;1 : : : ) i+2 xi+1 = (: : : (x0n n x0n;1) n;1 : : : ) i+2 x0i+1
und damit
f (xn :: xi+1 x ci;1 :: c1) = (::((::(xn n xn;1 ) n;1 ::) i+1 x) i ci;1::) 2 c1
= (::((::(x0n n x0n;1 ) n;1 ::) i+1 x) i ci;1::) 2 c1
= f (x0n :: x0i+1 x ci;1 :: c1):
Fur die Ruckrichtung denieren wir die Quasigruppen i, i = 2 : : : n ; 1
folgenderma
en:
x i y := f (xn : : : xi y ci;2 : : : c1), falls f (xn : : : xi ci;1 ci;2 : : : c1 ) = x
und
x n y := f (x y cn;2 : : : c1):
Die i sind wohldeniert, weil die Gleichung f (0 : : : 0 y ci;1 ci;2 : : : c1) = x
eine Losung y besitzt und weil aus
f (xn : : : xi ci;1 ci;2 : : : c1) = x = f (x0n : : : x0i ci;1 ci;2 : : : c1)
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
72
folgt, da
f (xn : : : xi y ci;2 : : : c1) = f (x0n : : : x0i y ci;2 : : : c1) ist. Au
erdem
gilt:
f (xn : : : x1) =
=
...
=
=
f (xn : : : x2 c1 ) 2 x1
(f (xn : : : x3 c2 c1) 3 x2 ) 2 x1
(: : : (f (xn xn;1 cn;2 : : : c1) n;1 xn;2 ) n;1 : : : ) 2 x1
(: : : ((xn n xn;1 ) n;1 xn;2 ) n;1 : : : ) 2 x1
2
Ist f auf diese Weise zerlegbar, dann gilt sogar fur beliebige xj x0j
f (xn : : : xi+1 xi xi;1 : : : x1) = f (x0n : : : x0i+1 xi xi;1 : : : x1 )
) f (xn : : : xi+1 x0i xi;1 : : : x1) = f (x0n : : : x0i+1 x0i xi;1 : : : x1)
und die Voraussetzungen des Theorems sind fur verschiedene Konstanten cj erfullt.
Fur verschiedene c1 6= c01 sind aber die Quasigruppen x n y := f (x y cn;2 : : : c1)
und x 0n y := f (x y cn;2 : : : c01) verschieden, denn aus x n y = x 0n y folgt,
da f eine n-Quasigruppe ist, c1 = c01. Wir sehen also, da
fur f unterschiedliche
Darstellungen existieren.
Theorem 14 ( Belousov 6]) Eine n-Quasigruppe f ist reduzibel genau dann,
wenn folgende Abschlu
bedingung fur eine hauptsachliche Parastrophie f erfullt
ist (1 < k < n):
f (x : : : x +1 x : : : x1 ) = f (x : : : x +1 y : : : y1 )
) f(x0 : : : x0 +1 x : : : x1 ) = f(x0 : : : x0 +1 y : : : y1 )
n
k
k
n
k
k
n
k
k
n
k
k
Den folgenden Beweis dieser Aussage haben wir unabhangig von Belousov
gefunden.
Beweis Sei f reduzibel, also
f (xn : : : x1) = g(x : : : x +1 h(x : : : x1 )):
n
k
k
Aus
f (xn : : : x1) =
=
=
=
f (x
g(x
g(x
f (x
n
n
n
n
: : : x +1 x : : : x1 )
: : : x +1 h(x : : : x1 ))
: : : x +1 h(y : : : y1 ))
: : : x +1 y : : : y1 )
k
k
k
k
k
k
k
k
4.4. EXISTENZ VON PRUFZIFFERSYSTEMEN
73
folgt h(x : : : x1 ) = h(y : : : y1 ) und damit
f (x0 : : : x0 +1 x : : : x1 ) = g(x0 : : : x0 +1 h(x : : : x1 ))
= g(x0 : : : x0 +1 h(y : : : y1 ))
= f (x0 : : : x0 +1 y : : : y1 )
Es gelte nun die Abschlu
bedingung fur die n-Quasigruppe f und die Permutation
, 1 k < n. Wir denieren die beiden Abbildungen g und h durch:
h(x : : : x1 ) := f (0 : : : 0 x : : : x1 )
und g(x : : : x +1 y) := f (x : : : x +1 x : : : x1 )
falls h(x : : : x1 ) = y:
Die (n;k +1)-Quasigruppe g ist wohldeniert, weil die Gleichung h(0 : : : 0 x) = y
fur jedes y eine eindeutig bestimmte Losung x besitzt (h ist eine k-Quasigruppe),
und au
erdem folgt, falls h(x : : : x1 ) = h(x0 : : : x01 ) = y, d.h.
f (0 : : : 0 x : : : x1 ) = f(0 : : : 0 x0 : : : x01 )
da
f(x : : : x +1 x : : : x1 ) = g(x : : : x +1 y)
= f(x : : : x +1 x0 : : : x01 )
gilt. Aus der Denition von g und h folgt nun
f (xn : : : x1 ) = f(x : : : x +1 x : : : x1 )
= g(x : : : x +1 h(x : : : x1 )):
k
k
n
k
k
n
k
k
n
k
k
n
k
k
k
k
n
n
k
k
k
k
k
k
k
n
k
k
n
k
k
n
n
n
k
k
k
k
k
k
Also ist f reduzibel. 2
Bemerkung Anstatt der 0 2 Q konnen wir, wie im vorhergehenden Theorem,
verschiedene Konstanten cn : : : ck+1 2 Q benutzen, um die Abbildungen g und h
zu denieren.
4.4 Existenz von Prufziersystemen
Die Existenz von Prufziersystemen fur beliebige Basen gro
er 2 wurde von H.P.
Gumm 12] 1985 bewiesen.
Theorem 15 ( H.P.
Gumm) Fur jede Basis m > 2 und alle n
eine Abbildung f :
! D bzw. g :
Prufziersystem deniert.
Dn
Dn+1
! D, so da
P0
f
2 existiert
bzw. Pg0 ein
74
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Beweis Wir konnen den Beweis durch die in Kapitel 2 aufgebaute Theorie etwas
verkurzen. Ist m ungerade, dann besitzt Zm die anti-symmetrische Abbildung
(x) := ;x. Ist m = 2k gerade, dann wissen wir, da
die Diedergruppe Dk
(neutrales Element '0') mit m Elementen eine anti-symmetrische Abbildung besitzt. In beiden Fallen deniert daher die Gleichung
f (xn xn;1 : : : x2 x1) := n(xn ) n;1(xn;1 ) : : : 2 (x2 ) (x1 )];1 = x0
bzw.
g(xn xn;1 : : : x1 x0 ) := n (xn) n;1 (xn;1) : : : 2 (x2 ) (x1 )x0 = 0
ein Prufziersystem zur Basis m. 2
Korollar 15 Fur alle n 2 und fur alle m > 2 existiert eine anti-symmetrische
n-Quasigruppe zur Basis m.
Zur Basis 2 existiert kein Prufziersystem (und damit auch keine anti-symmetrische n-Quasigruppe), denn den Zahlen 00, 01 und 10 mu
ten verschiedene
Prufziern aus der Menge f0 1g zugeordnet werden, was unmoglich ist.
Eine weitere Moglichkeit ein Prufziersystem zur Basis pm , wobei p eine Primm
zahl ist, zu denieren,
Pn bietet der Galois-Korper mit p Elementen. Mit der gewichteten Summe i=0 aixi = 0 erhalten wir ein Prufziersystem, falls ai 6= 0
und benachbarte Gewichte verschieden sind. Auch hier sehen wir, da
der Fall
p = 2 ausgeschlossen ist, da wir nur ai = 1 wahlen konnen und damit benachbarte
Gewichte gleich sind.
Des weiteren ist erwahnenswert, da
wir aus zwei Prufziersystemen zu den
Basen m1 und m2 auf naturliche Weise ein Prufziersystem zur Basis m1 m2 erhalten, indem wir jede Zahl der Basis m1 m2 als eindeutiges Paar (d1 d2) darstellen,
wobei d1 eine Zier der Basis m1 und d2 eine Zier der Basis m2 ist. Danach berechnen wir die Prufziern p1 und p2 getrennt fur jede Komponente und wandeln
das Paar (p1 p2) zuruck in die zugehorige Zahl der Basis m1 m2 . Es ist leicht
einzusehen, da
die Eigenschaften 1{3 der Denitionen 9 und 10 (Seite 61) sowohl
bei den impliziten als auch bei expliziten Prufziersystemen erhalten bleiben.
4.5 Prufziersysteme uber Quasigruppen
In diesem Abschnitt untersuchen wir die total reduziblen Prufziersysteme der
Form
g(xn xn;1 : : : x0 ) = (: : : (xn n xn;1 ) n;1 : : : ) 1 x0 = d
4.5. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
75
mit den (endlichen) Quasigruppen (Q i), i = 1 : : : n, und d 2 Q. Wir benutzen die implizite Form, weil dadurch die Bedingungen fur die Fehlererkennung
einfacher formuliert werden konnen. Fur die einzelnen Fehlerarten stellen wir die
Anforderungen an die benutzten Quasigruppen zusammen. Zunachst zeigen wir,
da
durch eine solche Prufgleichung alle Einzelfehler erkannt werden konnen. Es
gelte
(: : : ((: : : (xn n xn;1) n;1 : : : ) i+1 xi ) : : : ) 1 x0 = d
und
(: : : ((: : : (xn n xn;1 ) n;1 : : : ) i+1 x0i) : : : ) 1 x0 = d:
Wir setzen c := (: : : (xn n xn;1 ) n;1 : : : ) i+2 xi+1 und kurzen die Elemente
xi;1 : : : x0 auf der rechten Seite. Es folgt
c i xi = c i x0i
und durch Kurzen von c erhalten wir xi = x0i .
Da d 2 Q beliebig gewahlt werden kann, haben wir damit auch die Injektivitat, und weil Q endlich ist, auch die Surjektiviat der Translationen x 7!
g(xn : : : xi+1 x xi;1 : : : x0) fur alle i gezeigt. Folglich deniert g eine (n + 1)Quasigruppe uber der Menge Q.
Die Transposition benachbarter Elemente wird genau dann erkannt, wenn die
folgenden Implikationen fur alle i und alle c x y 2 Q gelten:
x n y = y n x ) x = y
(4.2)
(c i+1 x) i y = (c i+1 y) i x ) x = y:
Diese Aussage wird genauso gezeigt, wie die Aussage zur Erkennung der Einzelfehler. Zunachst werden die gleichen Elemente auf der rechten Seite gekurzt,
dann werden die gleichen Elemente auf der linken Seite zu c zusammengefa
t.
Wir haben damit den folgenden Satz bewiesen:
Satz 35 Mit den Quasigruppen (Q i) wird durch
g(xn xn;1 : : : x0) := (: : : (xn n xn;1) n;1 : : : ) 1 x0
genau dann eine anti-symmetrische (n + 1)-Quasigruppe deniert, wenn n antisymmetrisch ist und jede Zeile der Quasigruppe i+1 eine anti-symmetrisch Abbildung der Quasigruppe i ist.
Die anderen Fehlerarten benotigen weitere Voraussetzungen, die fur alle i und
fur alle x y z c 2 Q erfullt sein mussen.
76
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Sprungtranspositionen:
(x n z) n;1 y = (y n z) n;1 x ) x = y
((c i+1 x) i z) i;1 y = ((c i+1 y) i z) i;1 x ) x = y:
Zwillingsfehler:
x n x = y n y ) x = y
(c i+1 x) i x = (c i+1 y) i y ) x = y:
Sprungzwillingsfehler:
(x n z) n;1 x = (y n z) n;1 y ) x = y
((c i+1 x) i z) i;1 x = ((c i+1 y) i z) i;1 y ) x = y:
Im Vergleich zu den Prufziersystemen uber Gruppen mussen wir also eine
Vielzahl verschiedener Bedingungen uberprufen. Eine Verbesserung dieser Situation ware erreichbar, wenn wir jeweils bei der zweiten Voraussetzung umklammern konnten. Dann ware es moglich, das Element c ebenfalls zu kurzen. Diesen
Gedanken werden wir im Abschnitt "Verallgemeinerte Assoziativitat" ausfuhren.
Zunachst zeigen wir jedoch einige wichtige Eigenschaften einer Quasigruppe in
einem Prufziersystem.
Satz 36 Jede Quasigruppe in einem Prufziersystem besitzt eine anti-symmetrische Abbildung. Erkennt das Prufziersystem alle Zwillingsfehler, dann besitzt
jede Quasigruppe eine vollstandige Abbildung, erkennt es alle Sprungzwillingsfehler, dann besitzt jede Quasigruppe au
er ggf. n eine vollstandige Abbildung.
Beweis Sei i eine Quasigruppe eines Prufziersystems uber Quasigruppen, d.h.
sie erfullt die Bedingung 4.2. Ist i = n, dann ist n anti-symmetrisch und die
Identitat ist eine anti-symmetrische Abbildung. Fur i, i < n, denieren wir
'(x) := c i+1 x fur eine beliebige Konstante c. Damit ist '(x) i y = '(y) i
x aquivalent zur zweiten Bedingung von 4.2 und ' ist eine anti-symmetrische
Abbildung von i.
Erkennt das Prufziersystem alle Zwillingsfehler, dann ist die Identitat eine
vollstandige Abbildung von n und ' mit ';1(x) := c i+1 x eine vollstandige
Abbildung von i, i < n. Falls das Prufziersystem alle Sprungzwillingsfehler erkennt, dann ist fur fest gewahlte c z 2 Q die Permutation ' mit ';1(x) := x n z
Element von Com(Q n;1) und die Permutation ' mit ';1 (x) := (c i+1 x) i z ist
Element von Com(Q i;1), i < n. 2
Zusammen mit Satz 33 (Seite 68) sehen wir, da
viele Quasigruppen ungeeignet
sind, ein Prufziersystem zu denieren, das alle (Sprung-)Zwillingsfehler erkennt.
4.5. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
77
Insbesondere eignen sich die Isotopien einer Gruppe ohne anti-symmetrische oder
vollstandige Abbildung nicht. Speziell fur den Fall m = 10 bedeutet dies, da
wir
kein Prufziersystem nden werden, das alle (Sprung-)Zwillingsfehler erkennt und
in dem Quasigruppen vorkommen, die zu einer Gruppe isotop sind.
Da wir bereits gezeigt haben, da
Z2k keine anti-symmetrische und jede Gruppe
der Ordnung 2k fur ungerades k keine vollstandige Abbildung besitzt, erhalten wir
das Korollar:
Korollar 16 In einem Prufziersystem uber Quasigruppen der Ordnung 2k ist
keine Quasigruppe zur Gruppe Z2k isotop. Erkennt das Prufziersystem alle Zwillings- oder alle Sprungzwillingsfehler und ist k ungerade, dann ist keine Quasigruppe isotop zu einer Gruppe der Ordnung 2k.
Der im Abschnitt "Quasigruppen isotop zu einer Gruppe" beschriebene Ansatz
ist daher hauptsachlich fur andere Ordnungen von Interesse.
Wir zeigen nun einen interessanten Zusammenhang zwischen Prufziersystemen
uber Quasigruppen und orthogonalen lateinischen Quadraten.
Satz 37 Seien (Q i) die Quasigruppen eines Prufziersystems, das alle Zwillingsfehler erkennt, dann ist die Quasigruppe (Q i ), i = 1 : : : n ; 1, orthogonal
zu der durch
x 0i y = z :, z i+1 y = x
denierten.
Beweis Wir mussen zeigen, da
die Gleichungen x i y = a und x 0i y = b
fur alle a b 2 Q eine Losung besitzen. Die zweite Gleichung ist aquivalent zu
b i+1 y = x. Wir setzen diese in die erste Gleichung ein und erhalten die Bedingung, da
(b i+1 y) i y = a fur alle a b 2 Q eine Losung besitzt. Weil das
Prufziersystem alle Zwillingsfehler erkennt, ist 'b(y) = (b i+1 y) i y eine Permutation und die Gleichung besitzt eine Losung y = ';b 1(a). 2
Ganz analog zeigt man den folgenden Satz:
Satz 38 Seien (Q i) die Quasigruppen eines Prufziersystems, das alle Sprung-
zwillingsfehler erkennt, dann ist die Quasigruppe (Q i ), i = 1 : : : n ; 2, orthogonal zu den durch
x 0ci y = z :, (c i+2 y) i+1 z = x
denierten Quasigruppen mit c 2 Q, und n;1 ist orthogonal zu
x 00n;1 y = z :, y n z = x:
78
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Wenn ein Prufziersystem uber Quasigruppen der Ordnung m alle Zwillingsoder alle Sprungzwillingsfehler erkennt, dann konnen wir also eine ganze Reihe
verschiedener orthogonaler lateinischer Quadrate konstruieren. Hat au
erdem die
Gleichung a n x = x n b oder fur feste c1 c2 2 Q die Gleichung (c1 i+2 y) i+1 a =
(c2 i+2 y) i+1 b fur alle a b 2 Q eine Losung, dann ist, wie man leicht durch die
Denition der Quasigruppen sieht, 0n;1 orthogonal zu 00n;1 bzw. 0c1i orthogonal
zu 0c2i. In diesem Fall hatten wir drei paarweise orthogonale lateinische Quadrate
der Ordnung m.
Die Frage, fur welche Ordnungen ein Paar orthogonaler lateinischer Quadrate,
bzw. ein griechisch-lateinisches Quadrat existiert, blieb lange ungeklart. Euler
wu
te (1780), da
es kein griechisch-lateinisches Quadrat der Ordnung 2 gibt und
er kannte Konstruktionen fur ungerade oder durch 4 teilbare Ordnungen. Basierend auf vielfaltigen Untersuchungen vermutete er, da
griechisch-lateinische
Quadrate der Ordnung 4k +2 nicht existieren. G. Tarry bewies 1900 durch Ausschlu
aller Moglichkeiten, da
es kein griechisch-lateinisches Quadrat der Ordnung
6 gibt 8], womit er die Vermutung von Euler stutzte. Trotzdem gelang es Parker, Bose und Shrikhande 1960, also 180 Jahre nach Eulers Vermutung, ein
griechisch-lateinisches Quadrat der Ordnung 10 zu konstruieren 8]. Au
erdem lieferten sie eine Konstruktion fur die fehlenden geraden Ordnungen, die nicht durch
vier teilbar sind (au
er fur 2 und 6).
0A
6I
5J
9F
3H
8G
7D
4B
1C
2E
7E
1B
0I
6J
9G
4H
8A
5C
2D
3F
8B
7F
2C
1I
0J
9A
5H
6D
3E
4G
6H
8C
7G
3D
2I
1J
9B
0E
4F
5A
9C
0H
8D
7A
4E
3I
2J
1F
5G
6B
3J
9D
1H
8E
7B
5F
4I
2G
6A
0C
5I
4J
9E
2H
8F
7C
6G
3A
0B
1D
4D
5E
6F
0G
1A
2B
3C
7H
9I
8J
1G
2A
3B
4C
5D
6E
0F
8I
7J
9H
2F
3G
4A
5B
6C
0D
1E
9J
8H
7I
Grichisch-lateinisches Quadrat der Ordnung 10.
Ob dagegen drei paarweise orthogonale lateinische Quadrate der Ordnung 10
existieren, ist bis heute unbekannt. Wir konnen allerdings zeigen:
Satz 39 ( 8]) Die Anzahl der paarweise orthogonalen lateinischen Quadrate der
Ordnung n ist nicht gro
er als n ; 1.
Beweis Die Elemente der lateinischen Quadrate konnen umbenannt werden, oh-
ne die Eigenschaft der Orthogonalitat zu zerstoren. Daher permutieren wir die
4.6. VERALLGEMEINERTE ASSOZIATIVITAT
79
Elemente so, da
die erste Zeile jedes lateinischen Quadrates gleich 0 1 2 : : : ist.
Nun folgt, da die 1 bei jedem Paar lateinischer Quadrate mit sich selbst in der
ersten Zeile zusammenfallt, da
die 1 in der ersten Spalte nicht zweimal an der
gleichen Position steht. Weil sie auch nicht an der Position (0 0) steht, gibt es
folglich nur n ; 1 mogliche Positionen fur 1. 2
4.6 Verallgemeinerte Assoziativitat
Denition 20 ( R.
Schauffler 20]) Die vier Quasigruppen (Q
), (Q ),
(Q 3 ) und (Q 4 ), deniert auf der gleichen Grundmenge Q, erfullen das verallgemeinerte Assoziativgesetz, wenn fur alle x y z 2 Q die folgende Gleichung
gilt:
1
2
(x 1 y) 2 z = x 3 (y 4 z):
Eine Menge $ von Quasigruppen hei
t im Ganzen assoziativ (oder Assoziativsystem) wenn zu je zwei Quasigruppen 1 2 2 $ zwei weitere Quasigruppen
3 4 2 $ existieren, so da
diese das verallgemeinerte Assoziativgesetz erfullen.
3 4 hei
en dann rechts assoziiert zu 1 2 und 1 2 links assoziiert zu 3 4.
Die Menge der Quasigruppen mit den Elementen 0 1 : : : n werde mit $n bezeichnet. Es ware sehr nutzlich, wenn $n im Ganzen assoziativ ware, dann konnten
wir immer umklammern und die notwendigen Bedingungen zur Fehlererkennung
waren deutlich einfacher nachzuprufen. Leider ist dies i.allg. nicht der Fall, wie
das folgende Theorem zeigt.
Theorem 16 ( R.
wenn n 3 ist.
Schauffler 20]) $n ist nur dann im Ganzen assoziativ,
Beweis Fur n = 1 ist die Aussage trivial.
Fur n = 2 haben wir die beiden Quasigruppen
0 1
+ 0 1
und
0 0 1
0 1 0
1 1 0
1 0 1
Die erste Quasigruppe ist die zyklische Gruppe (Z2 +), die zweite la
t sich
darstellen durch x y = x + y + 1 und ist isotop zu (Z2 +). Wie man nun leicht
sieht, gilt damit das verallgemeinerte Assoziativgesetz fur die vier moglichen Paare
++, +, + und .
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
80
Auch fur n = 3 sind alle Quasigruppen isotop zu (Z3 +), denn es existieren
fur alle Quasigruppen (Q ) vier Permutationen p1 p2, p3 p4, so da
x y = p1(x) + p2 (y) = p3 (x + p4(y))
gilt. Fur die 12 Quasigruppen der Ordnung 3 geben wir in der folgenden Tabelle
jeweils die zugehorigen Permutationen mit der genannten Eigenschaft an:
Q
p1 p2 p3 p4
Q
p1 p2 p3 p4
0 1 2
1 2 0
012]
012]
012]
0 2 1
1 0 2
012]
2 0 1
0 1 2
2 0 1
012]
021]
021]
2 1 0
012]
102]
012]
1 2 0
2 0 1
102]
021]
102]
021]
1 2 0
0 1 2
201]
021]
021]
021]
012]
012]
120]
012]
120]
021]
120]
021]
210]
012]
210]
012]
210]
021]
210]
021]
120]
2 0 1
2 0 1
2 0 1
1 2 0
0 1 2
021]
0 1 2
2 1 0
0 1 2
1 2 0
012]
1 0 2
0 2 1
1 0 2
0 2 1
021]
0 2 1
021]
1 2 0
1 0 2
2 1 0
012]
2 1 0
2 1 0
012]
201]
012]
201]
021]
201]
021]
102]
Fur zwei beliebige Quasigruppen 1,
x 2 y = p3(x + p4(y)). Es folgt
0 2 1
1 0 2
2 1 0
1 0 2
0 2 1
2
gilt also x 1 y = p1 (x) + p2(y) und
(x 1 y) 2 z = p3 ((p1(x) + p2 (y)) + p4(z))
= p3 (p1(x) + (p2(y) + p4(z)))
= x 3 (y 4 z)
wobei wir die Quasigruppen
p2 (y) + p4(z) denieren.
3
4
durch x 3 y = p3 (p1(x) + y) und y 4 z =
Wir zeigen nun, da
es fur n 4 stets Quasigruppen gibt, die keine rechtsassozierten Quasigruppen besitzen. Wenn die Quasigruppen 1 2 3 4 das verallgemeinerte Assoziativgesetz erfullen, d.h. es gilt fur alle x y z 2 Q
(x 1 y) 2 z = x 3 (y 4 z)
dann gibt es nur n verschiedene Permutationen
'yz (x) := (x 1 y) 2 z = x 3 (y 4 z)
4.6. VERALLGEMEINERTE ASSOZIATIVITAT
81
denn y 4 z nimmt nur n unterschiedliche Werte an. Im folgenden Beispiel erhalten
wir aber mehr als n verschiedene Permutationen. Diese Quasigruppen benden
sich daher nicht in einem Assoziativsystem.
Sei p = (0 1) die Transposition, welche die Elemente 0 und 1 vertauscht. Wir
denieren die Quasigruppen durch
x 1 y := x + p(y) (mod n)
x 2 y := p(x) + y (mod n):
Beide Quasigruppen entstehen aus der Gruppe (Zn +), indem die ersten beiden
Spalten bzw. Zeilen vertauscht werden. Die Permutationen '0i, i = 0 : : : n ; 1,
sind paarweise verschieden, denn es gilt
'0i(0) = (0 1 0) 2 i = p(0 + 1) + i = 0 + i = i:
Fur die Permutation '10 erhalten wir '10 (0) = p(0 + p(1)) + 0 = 1 und '10 (1) =
p(1 + p(1)) + 0 = 0. Weil '01(1) = p(1 + p(0)) + 1 = p(2) + 1 = 3 gilt, unterscheidet sich '10 von den Permutationen '0i in wenigstens einer Stelle. Damit haben
wir aber n + 1 paarweise verschiedene Permutationen und die Quasigruppen 1 2
genugen nicht dem verallgemeinerten Assoziativgesetz. 2
Theorem 17 ( Aczel, Belousov, Hosszu 1]) Erfullen die vier Quasigruppen
(Q 1 ), (Q 2), (Q 3) und (Q 4) das verallgemeinerte Assoziativgesetz,
(x 1 y) 2 z = x 3 (y 4 z)
(4.3)
dann existiert eine Verknupfung , so da
(Q ) eine Gruppe bildet, zu der die i
isotop sind. Im Detail: Es existieren 5 Permutation von Q, so da
x 1 y = ;1((x) (y))
x 2 y = (x) (y)
x 3 y = (x) (y)
x 4 y = ;1 ( (x) (y)):
(4.4)
Die Gruppe, zu der die i isotop sind, ist bis auf Isomorphie eindeutig bestimmt.
Andererseits erfullen alle Isotopien einer beliebigen Gruppe mit den genannten
Eigenschaften das verallgemeinerte Assoziativgesetz.
Beweis Die letzte Behauptung wird einfach durch Einsetzen von 4.4 in 4.3 gezeigt,
wobei wir die Assoziativitat der Gruppe (Q ) benutzen.
Um die erste Aussage beweisen zu konnen, denieren wir zunachst die Permutationen
i(x) := x i a
i (x) := a i x
(i = 1 2 3 4)
82
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
wobei a ein beliebiges, fest gewahltes Element aus Q ist. Wir setzen x = z = a in
4.3 und erhalten
2 (1(y)) = 3(4 (y)):
(4.5)
Wir erhalten nun durch Substitution von x = a y = ;1 1(;2 1 (u)) z = ;4 1(;3 1(v))
und x = ;1 1 (;2 1(u)) y = a z = ;4 1(;3 1(v)) und x = ;1 1 (;2 1(u)) y = ;4 1 (;3 1(v)),
z = a in 4.3 die Gleichungen
;2 1(u) 2 ;4 1 (;3 1(v)) = 3(;1 1(;2 1 (u)) 4 ;4 1 (;3 1(v)))
und
;2 1(u) 2 ;4 1 (;3 1(v)) = ;1 1 (;2 1 (u)) 3 ;3 1(v)
und
2 (;1 1 (;2 1(u)) 1 ;4 1 (;3 1(v))) = ;1 1(;2 1 (u)) 3 ;3 1(v):
Die letzten drei Gleichungen zeigen, da
alle 4 Ausdrucke in ihnen gleich sind. Wir
benennen diesen gemeinsamen Wert mit
u v:
Damit erhalten wir 4.4 wenn wir
:= 2 1 := 2 := 34 := 3
und (vergleiche 4.5)
:= 3 4 = 21
setzen.
Setzen wir 4.4 in 4.3 ein, dann sehen wir, da
die Operation x y assoziativ ist
und, als Isotopie einer Quasigruppe, ebenfalls eine Quasigruppe ist. Bekanntlich
sind die Gruppen genau die assoziativen Quasigruppen und so bildet Q eine Gruppe
mit der Operation . Die Eindeutigkeit, bis auf Isomorphie, der Gruppe (G ) folgt
aus dem folgenden Theorem.
Theorem 18 ( 1]) Isotope Gruppen sind isomorph, d.h. wenn die Gruppen (Q )
und (R ) isotop sind
dann sind sie isomorph
'(x y) = (x) (y)
(4.6)
(x y) = (x) (y):
(4.7)
4.6. VERALLGEMEINERTE ASSOZIATIVITAT
83
Beweis Sei e das neutrale Element von (Q ). Wir setzen y = e bzw. x = e in
4.6 und erhalten
(x) = '(x) b;1
und
(y) = a;1 '(y)
wobei a = (e), b = (e) und a;1 b;1 die Inversen in (R ) sind. Setzen wir diese
Gleichungen wieder in 4.6 ein, dann erhalten wir
'(x y) = '(x) b;1 a;1 '(y)
und wenn wir diese Gleichung von links mit a;1 und von rechts mit b;1 durchmultiplizieren und
(x) := a;1 '(x) b;1
denieren, so erhalten wir 4.7. 2
Korollar 17 In einem Assoziativsystem sind alle Quasigruppen zur selben Gruppe
isotop.
Wie bereits erwahnt, konnen wir bei Quasigruppen, die das verallgemeinerte
Assoziativgesetz erfullen, die Voraussetzungen vereinfachen, die fur das Erkennen
der einzelnen Fehlerarten notwendig sind. Seien 0i+1 0i rechstsassozierte Quasigruppen von i+1 und i. Wir erhalten fur die einzelnen Fehlertypen folgende
Bedingungen:
Satz 40 Sei $ ein Assoziativsystem. Durch die Quasigruppen i
Gleichung
2 $ und die
g(xn xn;1 : : : x0 ) = (: : : (xn n xn;1 ) n;1 : : : ) 1 x0 = d
wird genau dann ein Prufziersystem deniert, wenn n anti-symmetrisch ist und
fur jedes Paar i+1 i rechtsassoziierte Quasigruppen 0i+1 0i 2 $ existieren, so
da
0i anti-symmetrisch ist.
Sind die Quasigruppen n 0i selbstorthogonal, dann erkennt dieses Prufziffersystem zusatzlich noch alle Zwillingsfehler.
Beweis Die genannte Gleichung erkennt alle Einzehlfehler und sie erkennt alle
Nachbarvertauschungen, falls
x n y = y n x ) x = y
(c i+1 x) i y = (c i+1 y) i x ) x = y:
84
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
gilt. Die erste Bedingung ist nach Voraussetzung erfullt. Um die zweite Bedingung
nachzuweisen, nehmen wir an, da
(ci+1 x)i y = (ci+1 y)i x gilt. Nach Voraussetzung existieren rechtsassozierte Quasigruppen 0i+1 0i, wobei 0i anti-symmetrisch
ist, so da
(s i+1 t) i u = s 0i+1 (t 0i u) fur alle s t u 2 Q gilt. Damit folgt
c 0i+1 (x 0i y) = c 0i+1 (y 0i x). Wir kurzen c auf beiden Seiten der Gleichung und
erhalten x 0i y = y 0i x. Da 0i anti-symmetrisch ist, folgt x = y und die zweite
Bedingung ist erfullt. Bei der Ruckrichtung sieht man leicht, da
falls entweder 0i
oder n nicht anti-symmetrisch ist, die Gleichung nicht alle Nachbarvertauschungen erkennen kann.
Fur den zweiten Teil der Behauptung mussen wir zeigen, da
aus x n x = y n y
bzw. x0i x = y 0i y die Gleichheit von x und y folgt. Dazu benutzen wir das folgende
Lemma:
Lemma 19 Eine selbstorthogonale Quasigruppe (Q ) ist anti-symmetrisch und
es gilt:
xx=yy
) x = y:
Beweis Weil Q selbstorthogonal ist, sind die Paare (x y y x) fur alle x y 2 Q
paarweise verschieden. Gabe es x y 2 Q mit x 6= y und x y = y x, dann waren
die Paare (x y y x) und (y x x y) gleich und Q ware nicht selbstorthogonal.
Ebenso folgt aus x x = y y, da
die Paare (x x x x) und (y y y y) gleich
sind, also folgt entweder x = y oder Q ist nicht selbstorthogonal. 2
Fur m = 10 existiert allerdings keine selbstorthogonale Quasigruppe in einem
Assoziativsystem. Denn solch eine Quasigruppe ware isotop zu der Diedergruppe,
die dann eine vollstandige Abbildung hatte. Aber D5 besitzt keine vollstandige
Abbildung, Theorem 2 (Seite 19).
Bemerkung Selbstorthogonale Quasigruppen werden auch anti-abelsch genannt
(vgl. Denes, Keedwell 8]). Eine anti-symmetrische Quasigruppe mu
aber
0 1 2
nicht anti-abelsch sein, wie das folgende Gegenbeispiel zeigt: 01 02 10 21
2 1 2 0
Diese Quasigruppe ist oensichtlich anti-symmetrisch, aber es gilt 0 0 = 1 1,
also ist sie nicht anti-abelsch.
4.7 Quasigruppen isotop zu einer Gruppe
In diesem Abschnitt untersuchen wir die speziellen Eigenschaften von Prufziffersystemen uber Quasigruppen, die isotop zu einer Gruppe sind. Im vorherigen
4.7. QUASIGRUPPEN ISOTOP ZU EINER GRUPPE
85
Abschnitt haben wir gesehen, da
der dortige Ansatz mit Quasigruppen in einem
Assoziativsystem ebenfalls zu diesen Quasigruppen fuhrt.
Im folgenden seien die Quasigruppen (Q i) isotop zu der Gruppe (Q ), d.h.
es existieren Permutationen 'i1 'i2 'i3, so da
x i y = 'i3('i1(x) 'i2(y))
gilt.
Die entsprechenden Voraussetzungen an die 'ij fur das Erkennen der einzelnen
Fehlertypen erhalt man nun einfach durch Einsetzen dieser Gleichungen in die
Bedingungen 4.2, Seite 75f, fur Quasigruppen. Wir zeigen allerdings eine etwas
einfacher zu erfullende Voraussetzung:
Satz 41 Die Quasigruppen (G i) seien isotop zu (G ). Sie denieren ein Prufziffersystem, falls folgende Bedingungen erfullt sind, i = 1 : : : n ; 1,
'n1 ';n12 2 Ant(G)
(4.8)
'i1 'i+13 'i+12 ';i21 2 Ant(G)
(4.9)
'i1 'i+13 2 Aut(G):
(4.10)
Beweis Es ist x n y = y n x aquivalent zu
'n3('n1(x) 'n2(y)) = 'n3('n1(y) 'n2(x)):
Wir kurzen 'n3, setzen x~ := 'n2(x) und y~ := 'n2(y) womit 'n1(';n12(~x)) y~ =
'n1(';n12(~y)) x~ folgt. Nach Voraussetzung ist 'n1 ';n12 anti-symmetrisch und
daher impliziert diese Gleichung x = y.
Nun nehmen wir an, da
(c i+1 x) i y = (c i+1 y) i x bzw.
;
'i3 'i1 'i+13('i+11(c) 'i+12(x)) 'i2(y)
;
= 'i3 'i1 'i+13('i+11(c) 'i+12(y)) 'i2(x)
gilt. Wir denieren x~ := 'i2(x), y~ := 'i2(y), c~ := 'i+11(c) und := 'i1 'i+13,
:= 'i+12 ';i21 . Es folgt
(~c (~x)) y~ = (~c (~y)) x~
und, weil ist ein Automorphismus ist,
(~c) (~x)) y~ = (~c) (~y)) x~:
Wir konnen (~c) auf beiden Seiten der Gleichung kurzen. Da wir vorausgesetzt
haben, da
= 'i1 'i+13 'i+12 ';i21 eine anti-symmetrische Abbildung
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
86
ist, folgt aus der resultierenden Gleichung x~ = y~ bzw. x = y. Damit haben wir
gezeigt, da
die Quasigruppen (G i) ein Prufziersystem denieren. 2
Bemerkung Die ersten beiden Eigenschaften sind auch notwendig fur das Erkennen aller Nachbarvertauschungen.
Beispiel Sei ' eine anti-symmetrische Abbildung der Gruppe (G ). Wir wahlen
'i2 := 'i;1 , 'n1 := 'n, 'i1 'i+13 = Id und '13 beliebig. ; Damit sind die
Voraussetzungen des Satzes fur die Quasigruppen x i y := 'i3 'i1(x) 'i2(y)
erfullt. Es folgt, da
(: : : (xn n xn;1) n;1 : : : ) 1 x0 = c
ein Prufziersystem deniert.
Konkret wahlen wir die anti-symmetrische Abbildung ' := 02413] der Gruppe
(Z5 +) (vgl. Seite 40) und 'i1 := 'i3 := 10324]. Damit erhalten wir fur n = 3
die folgenden Quasigruppen:
3
0
1
2
3
4
0
1
2
0
4
3
1
4
3
1
2
0
2
2
0
4
3
1
3
3
1
2
0
4
4
0
4
3
1
2
2
0
1
2
3
4
0
0
1
2
3
4
1
2
3
1
4
0
2
1
4
3
0
2
3
3
0
4
2
1
4
4
2
0
1
3
1
0
1
2
3
4
0
0
1
2
3
4
1
3
0
4
2
1
2
2
3
1
4
0
3
4
2
0
1
3
4
1
4
3
0
2
4.7.1 Lineare Quasigruppen
Um die Anforderungen an die Quasigruppen zu verringern, ist es sinnvoll, sogenannte lineare Quasigruppen zu betrachten, da diese eine sehr einfache Darstellung
besitzen.
Denition 21 ( 5]) Sei (Q ) eine Gruppe mit den Automorphismen 1 , 2 und
einem fest gewahlten c 2 Q. Die Quasigruppe (Q ) hei
t lineare Quasigruppe
(der Gruppe (Q )), falls die Gleichung x y = 1 (x) c 2 (y) fur alle x y 2 Q
erfullt ist.
Satz 42 Die Menge der linearen Quasigruppen einer Gruppe (Q ) bildet ein Assoziativsystem.
Beweis Seien (Q 1) und (Q 2) lineare Quasigruppen der Gruppe (Q ), d.h.
x 1 y = 1 (x) c 2 (y) und x 2 y = '1(x) d '2(y) mit 1 2 '1 '2 2 Aut(Q ),
4.7. QUASIGRUPPEN ISOTOP ZU EINER GRUPPE
87
c d 2 Q. Es gilt:
(x 1 y) 2 z = '1(1 (x) c 2 (y)) d '2 (z)
;
= '1 1 (x) '1 (c) '1 2(y) d '2(z)
= x 3 (y 4 z)
mit x 3 y := '1 1 (x) '1(c) y und y 4 z := '1 2 (y) d '2(z) und 3, 4 sind
lineare Quasigruppen der Gruppe (Q ). 2
Der folgende Spezialfall der linearen Quasigruppen wurde von Ecker und
Poch untersucht. Dabei setzen wir i := fur alle i:
Satz 43 ( Ecker, Poch 9]) Sei Zn = f0 : : : n ; 1g, n 2 und h k l 2 Zn mit
h und k teilerfremd zu n. Dann ist Qn = (Zn ) mit x y = (h x + k y + l) mod n
eine lineare Quasigruppe. Nachbarvertauschungen werden erkannt, falls h ; 1 und
h ; k teilerfremd zu n sind, und Sprungtranspositionen werden erkannt, falls h ; 1,
h + 1 und h2 ; k teilerfremd zu n sind.
Beweis Die Abbildungen x 7! h x und y 7! k y sind Automorphismen der
Gruppe Zn, da h und k teilerfremd zu n sind. Wir zeigen die erste Eigenschaft
von 4.2 (Seite 75). Dazu sei x y = y x, also hx + ky + l = hy + kx + l. Es
folgt (h ; k)(x ; y) = 0 und mit der Eigenschaft, da
h ; k eine Einheit in Zn
ist, x ; y = 0 bzw. x = y. Nun nehmen wir an, da
(c x) y = (c y) x gilt,
d.h. h(hc + kx + l) + ky + l = h(hc + ky + l) + kx + l. Wir kurzen auf beiden
Seiten die gleichen Terme und erhalten hkx + ky = hky + kx. k ist eine Einheit,
daher konnen wir auch k kurzen. Es folgt (h ; 1)(x ; y) = 0 und damit, weil wir
h ; 1 als Einheit vorausgesetzt haben, x = y. Die entsprechenden Bedingungen
fur Sprungtranspositionen werden ganz analog gezeigt. 2
Korollar 18 ( Ecker, Poch 9]) Sei q teilerfremd zu n, 1 q n ; 2 (n 3).
Wenn wir h = ;q, k = 1 und l = 0 setzen, dann werden alle Nachbarvertauschungen erkannt, vorausgesetzt, da
q + 1 teilerfremd zu n ist. Zusatzlich werden alle
Sprungtranspositionen erkannt, falls q ; 1 teilerfremd zu n ist.
Ist n gerade, dann ist entweder h oder h ; 1 gerade und daher nicht teilerfremd
zu n. Also gibt es fur gerades n keine lineare Quasigruppe, die alle Nachbarvertauschungen erkennt. Dies liegt u.a. auch am folgenden Zusammenhang:
Satz 44 Ein Prufziersystem uber linearen Quasigruppen der Gruppe (G ) ist
ein Prufziersystem uber dieser Gruppe.
Beweis Seien (G i), i = 1 : : : n, lineare Quasigruppen der Gruppe (G ) mit
x i y = i (x) ci 'i(y). Wir zeigen die Behauptung durch vollstandige Induktion
88
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
nach der Anzahl der beteiligten Quasigruppen. Fur eine Quasigruppe n haben
wir
xn n xn;1 = n (xn) cn 'n(xn;1):
Wir setzen n (x) := n (x) und n;1 (x) := cn 'n(x) und erhalten den Induktionsanfang
xn n xn;1 = n(xn ) n;1 (xn;1):
Nun gelte (: : : (xn n xn;1) n;1 : : : ) i xi;1 = n(xn ) : : : i;1 (xi;1). Es folgt
(n (xn) : : : i;1 (xi;1 )) i;1 xi;2 = i;1 (n(xn) : : : i;1(xi;1 )) ci;1 'i;1 (xi;2):
Mit ~j (x) := i;1 j (x), j = n : : : i ; 1, ~i;2 (x) := ci;1 'i;1(x) und der Eigenschaft, da
i;1 ein Automorphismus ist, haben wir (: : : (xn n xn;1 ) n;1 : : : ) i
xi;2 = ~n (xn) : : : ~i;2 (xi;2 ) gezeigt. Damit folgt die Behauptung. 2
Bemerkung Wir haben die Eigenschaft, da
n und die 'i Automorphismen sind
nicht benutzt. Die gleiche Aussage gilt daher auch fur Quasigruppen, bei denen
n und die 'i nur Permutationen sind, aber keine Automorphismen.
Der Ansatz mit linearen Quasigruppen fuhrt also auf die bereits in Kapitel 1 behandelten Prufziersysteme uber Gruppen. Da wir schon gezeigt haben, da
uber
der Gruppe Z2n, kein Prufziersystem existiert, kann es auch kein Prufziersystem
uber linearen Quasigruppen der Gruppe Z2n geben.
4.8 Total anti-symmetrische Quasigruppen
Ein naheliegender Ansatz zur Reduktion der Anzahl der Paare orthogonaler lateinischer Quadrate, ist es, anstatt verschiedener Quasigruppen, nur eine einzelne
Quasigruppe zu betrachten. Dies hat auch praktische Vorteile, da wir in diesem
Fall die Stellenzahl der zu sichernden Zahlen einfach erhohen konnen, wahrend bei
verschiedenen Quasigruppen nicht klar ist, wie wir eine weitere Quasigruppe hinzu
nehmen konnen, ohne dabei die Fehlererkennung zu zerstoren.
Wir betrachten daher die Prufziersysteme der Form
(4.11)
(: : : ((xn xn;1) xn;2 ) : : : ) x0 = c:
Eine Quasigruppe hei
t total anti-symmetrisch, falls sie anti-symmetrisch ist und
au
erdem gilt:
(c x) y = (c y) x
) x = y:
(4.12)
Damit deniert die Gleichung 4.11 genau dann ein Prufziersystem, wenn eine
total anti-symmetrische Quasigruppe ist.
4.8. TOTAL ANTI-SYMMETRISCHE QUASIGRUPPEN
89
4.8.1 Konstruktion
In diesem Abschnitt geben wir einen Algorithmus an, mit dessen Hilfe total antisymmetrische Quasigruppen konstruiert werden konnen. Die Eigenschaft 4.12
konnen wir durch die Parastrophie (Q =) etwas anders formulieren. Wir setzen
x~ := c x, also c=x~ = x und erhalten die neue Bedingung
x~ y = (c y) (c=x~)
)
c=x~ = y (fur alle c x~ y 2 Q)
Nun sei M = m(i j k) ein Wurfel mit m(i j k) := k, (i j k = 0 1 : : : n ; 1).
Wir konstruieren die Quasigruppe durch:
1) F
ur
2)
n ; 1 tue 2-10
F
ur j von 0 bis n ; 1 tue 3-7
3) Sind alle Elemente m(i j 0) : : : m(i j n ; 1)
i
von
0
bis
gestrichen,
dann Abbruch
m(i j k) aus, das noch nicht
i j := k
5) Streiche die Elemente m(i + 1 j k ) : : : m(n ; 1 j k )
6) Streiche die Elemente m(i j + 1 k ) : : : m(i n ; 1 k )
7) Streiche das Element m(j i k ), falls j > i
Streiche die Elemente m(c y c=x x y ),
c = 0 : : : i ; 1, x = i, y = 0 : : : n ; 1
Streiche die Elemente m(c y c=x x y ),
c = i, x = 0 : : : i, y = 0 : : : n ; 1
Gibt es in den Schritten 8 oder 9 x 6= c y mit x y = (c y ) (c=x), c y i, dann Abbruch
4) W
ahle ein Element
gestrichen ist und setze
8)
9)
10)
Erlauterungen: Die Schritte 5+6 sorgen dafur, da
eine Quasigruppe konstruiert wird. Durch Schritt 7 werden nur anti-symmetrische Quasigruppen erzeugt.
Die Schritte 8-10 beschleunigen den Algorithmus erheblich, denn es werden schon
wahrend der Konstruktion diejenigen Quasigruppen ausgeschlossen, die nicht total
anti-symmetrisch sind. Wir zeigen dies in dem folgenden Satz:
Satz 45 Eine Quasigruppe (Q ) kann genau dann mit dem Algorithmus konstru-
iert werden, wenn sie total anti-symmetrisch ist.
Beweis Wir zeigen zunachst mit vollstandiger Induktion, da
eine total antisymmetrische Quasigruppe (Q ) mit dem Algorithmus konstruiert werden kann.
Es sei (i0 j 0) < (i j ) falls i0 < i oder falls i0 = i und j 0 < j ist. Wir beginnen die
90
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Induktion mit (i j ) = (0 0). Da fur i = j = 0 noch kein Element gestrichen ist,
konnen wir 0 0 := 0 0 setzen. Nun gelte i0 j 0 = i0 j 0 fur alle (i0 j 0) < (i j ).
Annahme: In Durchlauf (i j ) ist das Element m(i j i j ) gestrichen, d.h. es existiert ein (i0 j 0) < (i j ), so da
in Durchlauf (i0 j 0) m(i j i j ) gestrichen wurde.
Wir unterscheiden die folgenden Falle:
Fall 1: m(i j i j ) wurde in Schritt 5 oder 6 gestrichen. Entweder gilt dann j = j 0
und i0 j = i0 j = i j oder i = i0 und i j 0 = i j 0 = i j . In beiden Fallen folgt
(i0 j 0) = (i j ) im Widerspruch zu (i0 j 0) < (i j ).
Fall 2: m(i j i j ) wurde in Schritt 7 gestrichen, also i0 = j und j 0 = i. Es folgt
j i = j i = i j . Nach Voraussetzung an (Q ) impliziert dies i = j und damit
(i0 j 0) = (i j ), Widerspruch.
Fall 3: m(i j i j ) wurde in Schritt 8 gestrichen, d.h. i0 < i und es existiert ein
c < i0 , y 2 f0 : : : n ; 1g mit c y = c y = i, c=i0 = j , i0 y = i0 y = i j .
Die zweite Gleichung ist aquivalent zu i0 = c j = c j . Wir setzen diese und die
erste Gleichung in die dritte ein und erhalten (c j ) y = (c y) j . Dies impliziert
nach Voraussetzung j = y und wir erhalten aus der dritten Gleichung i0 = i im
Widerspruch zu i0 < i.
Fall 4: m(i j i j ) wurde in Schritt 9 gestrichen, d.h. i0 < i und es existiert ein
x i0 < i, y 2 f0 : : : n ; 1g mit i0 y = i0 y = i, i0=x = j und x y = x y = i j .
Auch hier folgt durch Einsetzen in die letzte Gleichung (i0 j ) y = (i0 y) j .
Demnach ist j = y und i = x im Widerspruch zu x < i.
Damit ist die Annahme widerlegt, d.h. das Element m(i j i j ) ist nicht gestrichen. Wir setzen daher i j := i j .
Der Algorithmus bricht nicht in Schritt 3 ab, da wir gezeigt haben, da
mindestens ein Element, namlich m(i j i j ) nicht gestrichen ist. Wenn der Algorithmus
in Schritt 10 abbrechen wurde, dann gabe es c x 2 f0 : : : ig, y 2 f0 : : : n ; 1g,
c y i, x 6= c y = c y mit x y = (c y) (c=x). Wir setzen z := c=x
bzw. x = c z = c z und es folgt x y = (c y) z = (c z) y. Wir erhalten z = y, woraus x = c y folgt im Widerspruch zu x 6= c y. Damit haben wir
gezeigt, da
die Quasigruppe (Q ) mit dem Algorithmus konstruiert werden kann.
Sei nun andererseits (Q ) eine Quasigruppe, die mit dem Algorithmus konstruiert wurde. Wir nehmen an, es gabe c x y 2 f0 : : : n ; 1g, x 6= c y mit
x y = (c y) (c=x). Sei i := max(c x), also c x i. Wir betrachten nun den
Algorithmus in Durchlauf i bei den Schritten 8-10.
Fall 1: c = i, x i, c y i. In Schritt 9 gibt es demnach x 6= c y mit
x y = (c y) (c=x), c y i und der Algorithmus bricht ab.
Fall 2: c < i, x = i, c y i. In Schritt 8 sind damit die Bedingungen von Schritt
4.8. TOTAL ANTI-SYMMETRISCHE QUASIGRUPPEN
91
10 erfullt und der Algorithmus bricht ab.
Fall 3: c = i, x i, c y > i. Es ist (x y) < (c y c=x). In Schritt 9 wurde das
Element m(c y c=x x y) gestrichen, daher ist die Wahl (c y) (c=x) = x y im
Durchlauf (i0 j 0) = (c y c=x) nicht moglich, im Widerspruch dazu, da
wir (Q )
mit dem Algorithmus konstruiert haben.
Fall 4: c < i, x = i, c y > i. Auch hier ist (x y) < (c y c=x) und es folgt analog
zu Fall 3, da
in Schritt 8 m(c y c=x x y) gestrichen wurde und deshalb ist
(c y) (c=x) 6= x y, Widerspruch.
Nun nehmen wir an, es gabe x 6= y mit x y = y x, o.B.d.A. x < y. Im Durchlauf
(x y) wird das Element m(y x x y) gestrichen und kann daher im Durchlauf
(y x) nicht ausgewahlt werden, also x y 6= y x, Widerspruch.
Damit ist der Beweis des Satzes abgeschlossen. 2
Wie bei den anti-symmetrischen Abbildungen kann man alle total anti-symmetrischen Quasigruppen konstruieren, indem man in Schritt 4) nacheinander alle
nicht gestrichenen Elemente auswahlt und den Algorithmus rekursiv aufruft.
Mit diesem rekursiven Algorithmus haben wir die Anzahl der total anti-symmetrischen Quasigruppen mit einer Linkseins und derer, die zusatzlich noch alle
Sprungtranspositionen erkennen, bestimmt.
Ordnung Anzahl (Gesamt)
3
4
5
6
7
8
total antisymmetrisch
2
1
24
2
1.344
18
1.128.960
0
12.198.297.600
2.400
2.697.818.265.354.240 31.680
Sprungtranspositionen
0
2
12
0
480
1.440
Die Werte fur n = 3 4 5 6 bestatigen die von Ecker und Poch 9] bestimmte
Anzahl. Die Rechenzeit fur n = 7 betrug ca. 6 Minuten, die fur n = 8 ca. 12,5
Stunden. Fur die Konstruktion der total anti-symmetrischen Quasigruppen haben
wir die folgenden Satze ausgenutzt.
Satz 46 Ist (Q ) eine total anti-symmetrische Quasigruppe, ' und Permu-
tationen, dann wird durch x y := ;1 ( (x) '(y )) ebenfalls eine total antisymmetrische Quasigruppe deniert, falls ';1 2 Ant(Q ) oder (Q ) eine
Linkseins besitzt.
Beweis Wir nehmen zunachst an, da
(c x) y = (c y) x gilt, dann folgt mit
der Denition von (Q ), da
((c) '(x)) '(y) = ((c) '(y)) '(x) ist. Da
(Q ) total anti-symmetrisch ist, folgt '(x) = '(y) und demnach x = y.
92
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Falls (Q ) eine Linkseins 0 besitzt, dann folgt aus x y = (0 x) y = (0 y) x = y x
die Gleichung x = y. Also ist (Q ) total anti-symmetrisch.
Gilt ';1 2 Ant(Q ), dann impliziert x y = ;1 ((x) '(y)) = ;1((y) '(x)) = y x die Gleichung (x) '(y) = (y) '(x) und damit (';1 ('(x))) '(y) = (';1 ('(y)))'(x). Nach Voraussetzung ist ';1 eine anti-symmetrische
Abbildung der Quasigruppe (Q ), deshalb folgt '(x) = '(y) und x = y. Folglich
ist (Q ) total anti-symmetrisch. 2
Korollar 19 Ist (Q ) eine total anti-symmetrische Quasigruppe, so ist auch
(Q ) mit x y := ';1 ('(x) '(y)) total anti-symmetrisch.
Beweis Setze := ', dann ist ';1 = Id 2 Ant(Q ), weil (Q ) antisymmetrisch ist.
Satz 47 Sei (Q ) eine total anti-symmetrische Quasigruppe, dann existiert eine
total anti-symmetrische Quasigruppe mit Linkseins, (Q ) und eine anti-symmetrische Abbildung ';1 2 Ant(Q ) mit x y = x '(y ).
Beweis Sei '(x) := 0 x und x y := x ';1 (y), dann gilt y = 0 ';1(y) und
demnach 0 y = 0 ';1(y) = y fur alle y 2 Q, also besitzt (Q ) eine Linkseins
und ist nach Satz 46 total anti-symmetrisch. Au
erdem gilt ';1 2 Ant(Q ), denn
aus ';1(x) y = ';1(y) x folgt ';1(x) ';1 (y) = ';1(y) ';1 (x). (Q ) ist
anti-symmetrisch daher erhalten wir ';1(x) = ';1 (y) bzw. x = y. Damit haben
wir x '(y) = x ';1 ('(y)) = x y und die Behauptung ist bewiesen. 2
Wir konnen also alle total anti-symmetrischen Quasigruppen bestimmen, indem wir die total anti-symmetrischen Quasigruppen mit Linkseins und deren antisymmetrische Abbildungen konstruieren.
Satz 48 Eine total anti-symmetrische Quasigruppe mit Linkseins ist isomorph zu
einer total anti-symmetrischen Quasigruppe mit Linkseins (Q ), Q = f0 : : : n ;
1g, fur die
1x x+2
x = 0 ::: n; 1
gilt.
Beweis Sei (Q ) eine total anti-symmetrische Quasigruppe mit Linkseins 0. Wir
beweisen den Satz mit vollstandiger Induktion.
Falls 1 0 2 ist (Bem.: in diesem Fall gilt 1 0 = 2) , dann ist nichts zu
zeigen. Gilt 1 0 > 0 + 2 = 2, dann denieren wir '(1 0) := 2, '(2) := 1 0 und
4.8. TOTAL ANTI-SYMMETRISCHE QUASIGRUPPEN
93
'(x) := x sonst. Die Quasigruppe (Q ) mit x y := '('(x) '(y)) ist isomorph
zu (Q ), da ';1 = ' gilt und es ist 1 0 = '('(1) '(0)) = '(1 0) = 2 0 + 2.
Nun sei (Q ) isomorph zu (Q 0), und es gelte 1 0 x x + 2 fur 0 x k < n ; 3. Ist 1 0 (k + 1) > k + 3, dann setzen wir '(1 0 (k + 1)) := k + 3,
'(k + 3) := 1 0 (k + 1) und '(x) := x sonst. Damit erfullt die Quasigruppe (Q )
mit x y := '('(x) '(y)) die gesuchte Bedingung, denn es gilt
1 x = '('(1) 0 '(x)) = '(1 0 x) = 1 0 x x + 2
fur 0 x k
und
1 (k + 1) = '('(1) 0 '(k + 1)) = '(1 0 (k + 1)) = k + 3 = (k + 1) + 2
und (Q ) ist isomorph zu (Q ).
Da fur x n ; 3 die Aussage 1 x x + 2 trivial ist (denn schlie
lich ist
1 x n ; 1 fur alle x 2 Q), haben wir damit den Satz bewiesen. 2
Wir brauchen also nur solche Quasigruppen zu konstruieren, welche eine Linkseins besitzen, und fur die 1 x x + 2 gilt. Die Gesamtanzahl erhalten wir durch
das Auszahlen der verschiedenen isomorphen Quasigruppen. Damit verkurzt sich
die Rechenzeit erheblich, z.B. fur n = 8 von schatzungsweise einer Woche auf etwa
einen halben Tag.
Au
erdem haben wir den Algorithmus noch dadurch beschleunigt, da
wir beim
Streichen eines Elements gleich uberprufen, ob bereits alle Elemente m(i j k),
k = 0 : : : n ; 1 gestrichen wurden. Dies erreichen wir, indem wir mitzahlen,
wieviele Elemente noch nicht gestrichen sind. Sind alle Elemente gestrichen, so
konnen wir den aktuellen Durchlauf abbrechen und in der Rekursion eine Ebene
hoher gehen.
Fur n = 10 haben wir auch nach langerer Suche keine total anti-symmetrische
Quasigruppe gefunden. Da die Zahl der Quasigruppen mit n stark anwachst (siehe
McKay, Rogoyski 16]), konnten wir allerdings nur einen sehr geringen Prozentsatz uberprufen. Ecker und Poch haben sogar die Vermutung ausgesprochen,
da
Quasigruppen der Ordnung 4k + 2 nicht total anti-symmetrisch sein konnen.
Wir stutzen diese Vermutung durch den folgenden Satz:
Satz 49 Es existiert keine zu Ds, s > 2 ungerade, isotope Quasigruppe, die total
anti-symmetrisch ist. Die Quasigruppen, die zu Z2k isotop sind, konnen nicht
anti-symmetrisch sein.
Beweis Nehmen wir an, wir hatten eine total anti-symmetrische Quasigruppe
(Q ), die isotop zu Ds ist, d.h. x y = '3('1(x)'2 (y)). Damit ist (c x) y = '3 ('1(c x)'2 (y)) = '3('1('3 ('1(c)'2(x)))'2 (y)). Mit '~ = '1 '3 , c~ =
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
94
'1 (c), x~ = '2 (x) und y~ = '2(y) folgt (c x) y = '3('~(~cx~)~y). Da (Q ) total anti-symmetrisch ist, folgt, da
fur alle c~ 2 Ds die Permutation '~(~cx~) eine
anti-symmtrische Abbildung von Ds ist. Nach Satz 4 (Seite 30) ist damit auch
'~(~c;1c~x~)~c;1 = '~(~x)~c;1 2 Ant(Ds) im Widerspruch zu Satz 26 (Seite 54).
Da Zn keine anti-symmetrische Abbildung besitzt, gilt dies auch fur alle Isotopien. 2
Wenn die Vermutung stimmt, dann existiert kein Prufziersystem basierend
auf einer einzelnen Quasigruppe der Ordnung 10. Falls es allerdings eine total
anti-symmetrische Quasigruppe der Ordnung 10 geben sollte, dann bedeutet dies
allerdings noch nicht, da
diese eine bessere Fehlererkennung der anderen Fehler
(Zwillingsfehler, Sprungzwillingsfehler) bietet als ein Prufziersystem basierend
auf der Diedergruppe D5. Im nachsten Abschnitt werden wir zeigen, da
bestimmte Quasigruppen nicht alle Fehler erkennen konnen.
Fur ungerade n gilt allerdings:
Satz 50 Es existieren total anti-symmetrische Quasigruppen fur alle ungeraden
n.
Beweis In (Zn +) sind die Abbildungen '(x) = c ; x anti-symmetrisch fur al-
le c 2 Zn. Wir denieren nun x y := ;x + y und haben damit (c x) y =
;(;c + x) + y = c ; x + y und ist total anti-symmetrisch. 2
4.9 Quasigruppen mit Vorzeichen
Dieser Abschnitt verallgemeinert den Begri des Vorzeichens auf Quasigruppen.
Denition 22 Eine (endliche) Quasigruppe (Q ) mit einem Homomorphismus
sgn : Q
! f;1 +1g hei
t Quasigruppe mit Vorzeichen sgn.
Ist sgn surjektiv,
dann hei
t das Vorzeichen nicht-trivial. Die Menge der positiven bzw. negativen
Elemente wird mit Q+ bzw. Q; bezeichnet.
Eigenschaften:
1. Besitzt (Q ) eine Links- oder Rechtseins e, dann ist sgn(e) = 1.
2. Q = Q+ Q; und Q+ \ Q; = .
3. Es gilt jQ+j = jQ;j, falls das Vorzeichen auf Q nicht trivial ist, sonst Q+ = Q
und Q; = .
4.9. QUASIGRUPPEN MIT VORZEICHEN
95
zu 1: sgn(e) = sgn(e e) = sgn(e)sgn(e) = 1.
zu 2: klar.
zu 3: Sei x 2 Q; 6= , dann ist x x 2 Q+, denn sgn(x x) = sgn(x)sgn(x) = 1,
also ist das Vorzeichen sgn nicht trivial. Es ist x Q+ Q; , und da x y1 6= x y2
fur y1 6= y2 gilt, haben wir jQ+j jQ;j. Ebenso gilt x Q; Q+ und damit
jQ;;j jQ+j. Folglich+ haben wir jQ+j = jQ;j. Ist das Vorzeichen trivial, dann gilt
Q = und Q = Q .
Satz 51 Quasigruppen mit ungerader Ordnung besitzen nur die triviale Vorzeichenfunktion sgn(x) = 1.
Eine Quasigruppe der Ordnung 2k besitzt ein nicht-triviales Vorzeichen genau
dann, wenn sie eine Unterquasigruppe der Ordnung k besitzt.
Beweis Falls eine Quasigruppe ein nicht-triviales Vorzeichen besitzt, dann gilt
jQ j = jQ;;j und die Anzahl der Elemente der Quasigruppe ist gerade, denn jQj =
jQ j + jQ j = k + k = 2k. Q ist in diesem Fall eine Unterquasigruppe der Ordnung k, denn wenn x y 2 Q sind, dann gilt sgn(x y) = sgn(x)sgn(y) = 1 1 = 1
und es folgt x y 2 Q .
+
+
+
+
+
Andererseits konnen wir mit einer Unterquasigruppe U der Ordnung k ein Vorzeichen denieren durch
sgn(x) =
(
falls x 2 U
;1 sonst.
1
Wir mussen zeigen, da
sgn(x y) = sgn(x)sgn(y) gilt. Dazu sei x 2 U . Fur y 2 U
sind auch die Elemente x y 2 U . Da x y1 6= x y2 fur y1 6= y2 gilt, ist x U = U .
Aus diesem Grund ist fur z 62 U auch x z 62 U , denn wenn x z 2 U ware, dann
gabe es ein y 2 U mit x z = x y und damit ist y = z, Widerspruch. Genauso
folgt, da
fur z 62 U auch z x 62 U ist. Nun sei z 2 U := Q n U . Wir haben
gezeigt, da
fur x 2 U , z x und x z Elemente von U sind, d.h. z U = U z = U ,
denn die Elemente z x bzw. x z sind fur verschiedene x ebenfalls verschieden
und jU j = jU j. Ist y 2 U , dann mu
z y y z 2 U gelten, denn sonst gabe es
ein x 2 U mit z y = z x bzw. y z = x z und es wurde x = y und daher ein
Widerspruch folgen. Damit haben wir gezeigt, da
sgn ein Homomorphismus ist.
2
Theorem 19 Sei Q eine Quasigruppe der Ordnung 4k + 2 mit nicht trivialem
Vorzeichen, dann besitzt Q keine vollstandige Abbildung.
Beweis Siehe Beweis auf der Seite 48.
96
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Wir haben bereits gezeigt, da
in einer Isotopieklasse entweder alle oder keine
Quasigruppe eine vollstandige Abbildung besitzt. Daher wissen wir, da
jede
Quasigruppe der Ordnung 4k + 2, die zu einer Quasigruppe mit Vorzeichen isotop
ist, keine vollstandige Abbildung besitzt. Also gilt:
Korollar 20 Prufziersysteme zur Basis 4k + 2 uber Quasigruppen, von denen
wenigstens eine isotop zu einer Quasigruppe mit Vorzeichen ist, erkennen nicht
alle Zwillings- und auch nicht alle Sprungzwillingsfehler.
Das Gleiche gilt auch fur alle Parastrophien dieser Quasigruppen.
4.9.1 Beispiele
Die Quasigruppe (Zn ), n gerade, mit
(
falls x gerade
x y = (x + y) mod n
(x ; y ; k) mod n falls x ungerade,
k 2 Zn gerade, besitzt das nicht-triviale Vorzeichen
(
sgn(x) = 1 falls x gerade
;1 falls x ungerade,
denn die Menge der geraden Zahlen bildet eine Unterquasigruppe von (Zn ). Dies
wird besonders deutlich, wenn wir die Zeilen und Spalten so permutieren, da
zuerst die geraden und dann die ungeraden Zahlen kommen. Fur n = 10 k = 0
haben wir z.B. die Quasigruppe
*
0
2
4
6
8
1
3
5
7
9
0
0
2
4
6
8
1
3
5
7
9
2
2
4
6
8
0
9
1
3
5
7
4
4
6
8
0
2
7
9
1
3
5
6
6
8
0
2
4
5
7
9
1
3
8
8
0
2
4
6
3
5
7
9
1
1
1
3
5
7
9
0
2
4
6
8
3
3
5
7
9
1
8
0
2
4
6
5
5
7
9
1
3
6
8
0
2
4
7
7
9
1
3
5
4
6
8
0
2
9
9
1
3
5
7
2
4
6
8
0
Wir zeigen, da
(Zn ) fur alle geraden n k eine Quasigruppe deniert. Wir
setzen y := a ; x, falls x gerade und y := x ; a ; k, falls x ungerade ist, und haben
4.9. QUASIGRUPPEN MIT VORZEICHEN
97
so eine eindeutige Losung der Gleichung x y = a mit vorgegebenen x a 2 Zn.
Sind y b 2 Zn vorgegeben und y und b entweder beide gerade oder beide ungerade,
dann ist x := b ; y gerade und Losung der Gleichung x y = b. Falls y und b
unterschiedliche Vorzeichen haben, dann ist x := b + y + k ungerade und lost die
Gleichung x y = b. Um zu zeigen, da
diese Losung eindeutig ist, nehmen wir
an, da
x1 y = x2 y = b gilt. Haben x1 und x2 das gleiche Vorzeichen, dann
konnen wir y und ggf. k auf beiden Seiten der Gleichung kurzen und erhalten
x1 = x2 . Gilt dagegen x1 ungerade und x2 gerade, so haben wir die Gleichung
x1 ; y ; k = x2 + y bzw. x1 = x2 + 2y + k. Auf der rechten Seite der Gleichung
steht eine gerade, auf der linken eine ungerade Zahl, da n gerade ist haben wir
daher einen Widerspruch. Damit folgt, da
(Zn ) eine Quasigruppe ist. 2
Weitere Beispiele konnen wir aus der Arbeit von Ecker und Poch entnehmen. Sie denieren uber den folgenden Quasigruppen der Ordnung 2n = 4k + 2
ein Prufziersystem (siehe letzten Abschnitt). Fur x y 2 Zn sei x 1 y bzw. x 2 y
deniert durch:
0x y n;1
0 x n ; 1 n y 2n ; 1
n x 2n ; 1 0 y n ; 1
n x y 2n ; 1
bzw.
0x y n;1
0 x n ; 1 n y 2n ; 1
n x 2n ; 1 0 y n ; 1
n x y 2n ; 1
:
x 1 y = (y ; x) mod n
: x 1 y = n + ((y ; x) mod n)
: x 1 y = n + ((;x ; y) mod n)
: x 1 y = (y ; x + 1) mod n
:
x 2 y = (y ; x) mod n
: x 2 y = n + ((y + x) mod n)
: x 2 y = n + ((y ; x + 1) mod n)
: x 2 y = (;y + x + 1) mod n
Auch diese Quasigruppen besitzen ein nicht triviales Vorzeichen, denn fur
0 x y n ; 1 gilt 0 x 12 y n ; 1 und damit habe wir eine Unterquasigruppe der Ordnung 2k +1. Also konnen wir Korollar 20 (Seite 96) anwenden und
es folgt, da
uber dieser Quasigruppe kein Prufziersystem existiert, welches alle
(Sprung-)Zwillingsfehler erkennt.
Im Gegensatz zu den Gruppen, mu
eine Quasigruppe der Ordnung 4k + 2
nicht unbedingt ein nicht-triviales Vorzeichen besitzen, wie das folgende Beispiel
zeigt.
98
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 6 2 9 4 3 7 5 1 0 8
2 5 6 4 8 7 3 1 9 2 0
3 9 5 6 7 0 1 3 8 4 2
4 3 8 5 6 1 2 9 0 7 4
5 8 3 0 5 6 9 4 2 1 7
6 7 0 3 2 5 6 8 4 9 1
7 2 4 7 1 9 8 0 3 6 5
8 4 7 1 9 8 0 2 6 5 3
9 1 9 8 0 2 4 7 5 3 6
Die Identitat ist eine vollstandige Abbildung dieser Quasigruppe, denn die
Elemente x x auf der Diagonalen sind paarweise verschieden. Nach Theorem 19
kann sie daher nicht isotop zu einer Quasigruppe mit nicht-trivialem Vorzeichen
sein, insbesondere besitzt sie selbst nur das triviale Vorzeichen.
4.10 Total anti-symmetrische Abbildungen
Wenn wir den Ansatz im Abschnitt "Total anti-symmetrische Quasigruppen" mit
Kapitel 1 vergleichen (insbesondere Satz 1, Seite 15), dann ist der deutlichste
Unterschied, da
wir die Prufzier nur mit einer Quasigruppe berechnet haben,
ohne eine Permutation auf die einzelnen Elemente anzuwenden.
Wir untersuchen nun diese Moglichkeit mit dem Ansatz
((: : : (('n(xn) 'n;1(xn;1)) 'n;2(xn;2 )) : : : ) '(x1)) x0 = c
(4.13)
wobei (Q ) eine Quasigruppe und ' eine Permutation ist.
Zunachst zeigen wir, da
dies im wesentlichen dem vom Ecker und Poch
vorgeschlagenen Ansatz entspricht. Sie denieren die Prufzier durch
x0 := (: : : ((xn '(xn;1 )) '2(xn;2 )) : : : ) 'n;1(x1)
(4.14)
und verzichten auf das Erkennen der Vertauschung x0 $ x1. Dies erscheint aufgrund der Tatsache, da
die Haugkeit der Fehler mit wachsender Stellenzahl
zunimmt, als wenig sinnvoll. Au
erdem konnen wir auf die einzelnen Stellen xi die
Permutation ';n anwenden, ohne da
die Anti-Symmetrie-Eigenschaft der durch
die Gleichung denierten n-Quasigruppe verlorengeht (Satz 16, Seite 67). Wir erhalten somit die Form 4.13, wobei es besser ist, die Prufzier implizit durch die
genannte Gleichung zu bestimmen.
Fur eine Quasigruppe reicht es nicht aus, da
' eine anti-symmetrische Abbildung ist. Wir benotigen zusatzlich noch die Bedingung
(c '(x)) y = (c '(y)) x ) x = y
4.10. TOTAL ANTI-SYMMETRISCHE ABBILDUNGEN
99
damit alle Nachbarvertauschungen erkannt werden. Wir nennen eine Permutation die anti-symmetrisch ist und zusatzlich diese Bedingung erfullt total antisymmetrisch. In einer Gruppe sind anti-symmetrische Abbildungen auch total
anti-symmetrisch, fur Quasigruppen gilt dies aber i.allg. nicht.
4.10.1 Konstruktion
Total anti-symmetrische Abbildungen einer Quasigruppen (Q ) konnen ganz ahnlich wie die anti-symmetrischen Abbildungen einer Gruppe konstruiert werden.
In einer Quasigruppe haben wir allerdings im allgemeinen kein inverses Element.
Dieses Problem konnen wir aber leicht losen, indem wir die Parastrophien (Q =)
und (Q n) betrachten. Dann sind die Implikationen
aquivalent zu
'(x) y = '(y) x
(c '(x)) y = (c '(y)) x
)
)
x=y
x=y
'(x) = ('(y) x)ny
'(x) = c=(((c '(y)) x)ny)
)
)
x=y
x = y:
Damit erhalten wir einen Algorithmus, der die total anti-symmetrischen Abbildungen einer Quasigruppe konstruiert, indem wir statt des Elements mkjki;1 bei
Gruppen, das Element mk(jk)ni und fur alle c 2 Q die Elemente mkc=(((cj)k)ni)
streichen (vgl. Seite 39). Mit diesem Algorithmus konnen wir sehr eektiv die
total anti-symmetrischen Abbildungen einer vorgegebenen Quasigruppe konstruieren. Wir haben nun fur verschiedene Quasigruppen die total anti-symmetrischen
Abbildungen bestimmt und deren Erkennungsquote der anderen Fehlerarten untersucht. Dabei fanden wir eine Quasigruppe, die eine bessere Fehlererkennung
bietet als die Diedergruppe.
Zum Vergleich geben wir zunachst die Erkennungsquote des von Ecker und
Poch denierten "Shift-Code" an. Sie benutzen die im Abschnitt 4.9.1 (Seite
97) denierten Quasigruppen mit der Prufgleichung 4.14 und der Permutation
'(x) := x + 1. Damit erzielten sie die folgenden Fehlererkennungsraten fur die
Quasigruppe 1 der Ordnung 10: Sprungtranspositionen (Spr.): 84,89%, Zwillingsfehler (Zw.): 71,11%, Sprungzwillingsfehler (SprZw.): 87,67% und phonetische Fehler (Ph.): 76,19%.
100
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Bei der zweiten angegebenen Quasigruppe stellten wir fest, da
diese zusammen
mit ' nicht alle Nachbarvertauschungen erkennt. Es gilt fur 2n = 4k + 2, k > 1:
0 2 '(3k + 2) = 0 2 (3k + 3) = 2k + 1 + ((3k + 3) mod 2k + 1) = 3k + 3
und
(3k + 2) 2 '(0) = (3k + 2) 2 1 = 2k + 1 + ((1 ; 3k ; 2 + 1) mod 2k + 1) = 3k + 3:
Folglich ist (3k + 2) 2 '(0) = 0 2 '(3k + 2).
Das Ergebnis von Ecker und Poch 9, Seite 299] ist fur diese Quasigruppe
daher falsch.
Bei der Diedergruppe fanden wir total anti-symmetrische Permutationen, die
eine deutlich hohere Fehlererkennung bieten als der Shift-Code von Ecker und
Poch.
Ordnung Permutation Spr.
Zw. SprZw. Ph.
6
034152]
82,22% 86,67% 82,22% 80,00%
305214]
82,22% 86,67% 82,22% 100,00%
8
07526431] 89,29% 100,00% 89,29% 91,43%
43571602] 92,86% 92,86% 92,86% 97,14%
10
0458613297] 92,00% 95,56% 92,00% 90,48%
0542978136] 92,00% 91,11% 92,00% 100,00%
7046913258] 94,22% 95,56% 94,22% 96,83%
Bei der Suche nach anderen Quasigruppen, die eine bessere Fehlererkennung
haben als die Diedergruppe, fanden wir die Quasigruppe (Zn ), n gerade, deniert
durch
(
falls x gerade
x y = (x + y) mod n
(x ; y ; 2) mod n falls x ungerade
(vgl. Abschnitt 4.9.1) und die folgenden total anti-symmetrischen Abbildungen:
Ordnung Permutation Spr.
6
013425]
82,22%
014352]
82,22%
8
12053467] 92,86%
01526374] 92,86%
10
0137268459] 92,00%
0147389625] 92,00%
2096813574] 94,22%
Zw.
86,67%
86,67%
100,00%
100,00%
95,56%
95,56%
95,56%
SprZw.
82,22%
82,22%
92,86%
92,86%
92,00%
92,00%
94,22%
Ph.
100,00%
100,00%
94,29%
100,00%
100,00%
100,00%
96,83%
4.10. TOTAL ANTI-SYMMETRISCHE ABBILDUNGEN
101
Mit der Permutation 2096813574] erreichen wir eine Fehlererkennung von 99,89%
aller nicht zufalligen Fehler (einschlie
lich der Einzelfehler und der Nachbarvertauschungen, die zu 100% erkannt werden). Die Permutation 0147389625] bietet eine
Fehlererkennung von 99,87%. Sie hat den Vorteil, da
die 0 xiert wird, womit
fuhrende Nullen die Prufzier nicht verandern und Formatfehler erkannt werden
konnen. Im Vergleich zur Permutation 0542978136] der Diedergruppe erkennt
dieses Prufziersystem mehr Fehler und ist diesem daher vorzuziehen.
Schlubemerkung
Wir haben gesehen, da
das Problem, ein Prufziersystem zur Basis 10 zu bestimmen, welches alle Sprung-/Zwillingsfehler, alle Sprungtranspositionen und alle phonetischen Fehler erkennt, keine naheliegende Losung besitzt. Die Frage, ob
es uberhaupt ein solches Prufziersystem gibt, bleibt oen. Die Existenz zu widerlegen, erscheint allerdings sehr schwer, da ein entsprechender Beweis auf den
speziellen Eigenschaften der Zahl 10 beruhen mu
, denn zur Basis 11 existiert ein
entsprechendes Prufziersystem. Trotzdem konnen wir mit dem im letzten Abschnitt angegebenen Prufziersystem 99,89% aller nicht zufalligen Fehler erkennen
und somit eine sehr hohe Fehlererkennung gewahrleisten.
102
KAPITEL 4. PRUFZIFFERSYSTEME
UBER
QUASIGRUPPEN
Literaturverzeichnis
1] J. Aczel, V.D. Belousov, M. Hosszu. Generalized associativity and bisymmetry on quasigroups. Acta Math. Acad. Sci. Hungar 11 (1960), 127-136.
2] P. Batemann. Complete mappings of innite groups. Amer. Math. Monthly
57 (1950), 621-622.
3] J. A. Beachy, W. D. Blair. Abstract Algebra, Second Edition. Waveland
Press, Illinois 1996.
4] V.D. Belousov. Extensions of quasigroups. Bull. Akad. Stiince RSS Moldoven No. 8 (1967), 3-24. (Russisch)
5] G.B. Belyavskaya, A.Kh. Tabarov. Characteristic of linear and alinear
quasigroups. Diskretn. Mat. 4, No.2 (1992), 142-147. (Russisch)
6] O. Chein, H.O. Pflugfelder, J.D.H. Smith. Quasigroups and Loops,
Theory and Applications. Sigma Series in Pure Mathematics, Volume 8
(1990), Heldermann Verlag Berlin.
7] J. Conway, R. Curtis, S. Norton, R. Parker, R. Wilson. Atlas of
Finit Groups. Oxford 1985.
8] J. Denes, A.D. Keedwell. Latin Squares and theire Applications. New
York: Academic Press (1974).
9] A. Ecker, G. Poch. Check Character Systems. Computing 37 (1986), 277301.
10] J. A. Gallian, M. Mullin. Groups with Anti-symmetric Mappings. Archive der Math. 65 (1995), 273-280.
11] D. Gorenstein. Classifying the nit simple groups. Bull. Amer. Math. Soc.
14 (1986), 1-98.
12] H.P. Gumm. A New Class of Check-Digit Methods for Arbitrary Number
Systems. IEEE Tran. Inf. Th. 31 (1985), 102-105.
103
104
LITERATURVERZEICHNIS
13] H.P. Gumm. Encoding of Numbers to Detect Typing Errors. Inter. J. Applied
Eng. Ed. 2 (1986), 61-65.
14] M. Hall, L.J. Paige. Complete mappings of nite groups. Pacic J. Math.
5 (1955), 541-549.
15] H.B. Mann. The construction of orthogonal latin squares. Ann. Math. Statistics 13 (1942), 418-423.
16] B. D. McKay, E. Rogoyski. Latin Squares of Order 10. The Electronic
Journal of Combinatorics 2 (1995) #N3.
17] K. Meyberg. Algebra, Teil 1. Carl Hanser Verlag Munchen Wien 1980.
18] L.J. Paige. A note on nite abelian groups. Bull. Amer. Math. Soc. 53 (1947),
590-593.
19] L.J. Paige. Complete mappings of nite groups. Pacic J. Math. 1 (1951),
111-116.
20] R. Schauffler. Die Assoziativitat im Ganzen, besonders bei Quasigruppen.
Math. Z. 67 (1957), 428-435.
21] R.-H. Schulz. Codierungstheorie. Eine Einfuhrung. Vieweg V. Braunschweig/Wiesbaden 1991.
22] R.-H. Schulz. A note on Check character Systems using Latin squares.
Discr. Math. 97 (1991) 371-375.
23] H. Siemon. Anwendungen der elementaren Gruppentheorie in Zahlentheorie
und Kombinatorik. Stuttgart: Klett-Verlag 1981.
an, M. Skoviera
24] J. Sir
. Groups with sign structure and theire antiautomorphisms. Discr. Math. 108 (1992), 189-202.
25] N. J. A. Sloane, S. Plouffe. The Encyclopedia of Integer Sequences.
Academic Press, San Diego, 1995.
26] S. K. Stein. On the foundations of quasigroups. Trans. Amer. Math. Soc.
85 (1957), 228-256.
27] J. Verhoeff. Error detecting decimal codes. Math. Centre Tracts 29, Amsterdam 1969.
28] Steven J. Winters. Error Detecting Schemes Using Dihedral Groups.
UMAP Journal 11 (1990), 299-308.
Erklarung
Hiermit versichere ich, da
ich diese Arbeit selbstandig verfa
t und keine anderen
als die angegebenen Quellen und Hilfsmittel benutzt habe.
Marburg, den 6. Marz 1998
105

Abbildungen zur Rekonstruktion des Helmvisiers

1 括弧内の語句を用いてそれぞれの日本語に 1

Flyer - SG Niederwangen

Beweis_3

Addieren Sie zwei beliebige Quadratzahlen und verdoppeln Sie das

Präsenzblatt 3

Ausgewählte Abbildungen für Baden

In den vorigen Beispielen (3) und (4) benutzten wir implizit bereits

impressum - Linguaffin

Hochkarätige Teilnehmer beim 17. Neukirchner Sommerblitzturnier