Quasigruppe

In der Mathematik ist eine Quasigruppe eine nichtleere Menge $Q$ mit einer binären Verknüpfung $\star$, in der für alle $a$ und $b$ in $Q$ die Gleichungen

$a\star x=b$ (1)

und

$y\star a=b$ (2)

genau eine Lösung haben, d.h. die Lösung existiert und ist eindeutig. Dies ist zu unterscheiden, von Strukturen, in denen lediglich die sog. Kürzungseigenschaft (s. u.) gefordert wird. Dort wird zwar auch die Eindeutigkeit der Lösungen dieser Gleichungen gefordert, aber nur falls überhaupt eine Lösung existiert. Auf die Nichtleerheit der zugrundegelegten Menge kann auch verzichtet werden, dann ist die leere Menge trivialerweise auch eine (dann die kleinste) Quasigruppe.

Beispiele

Jede Gruppe ist eine Quasigruppe, denn $a\star x=b$ ist genau für $x=a^{-1}\star b$ und $y\star a=b$ genau für $y=b\star a^{-1}$ erfüllt.

Jeder Vektorraum über einem Körper der Charakteristik ungleich 2 ist eine Quasigruppe mit der Verknüpfung $x\star y=(x+y)/2$.

Jedes Steinersche Tripel-System ist eine Quasigruppe.

Jede Menge von Nichtnull-Elementen in einer nullteilerfreien endlichdimensionalen Algebra ist eine Quasigruppe (z. B. die Oktaven ohne 0).

Die einzige Quasigruppe der Ordnung 2 ist die zyklische Gruppe $\mathbb {Z} /2\mathbb {Z}$. Es gibt fünf Quasigruppen der Ordnung 3, von denen nur Eine eine Gruppe ist. Die kleinste echte Loop (die nicht assoziativ ist) hat die Ordnung 5.

Wie viele Probleme der Gruppentheorie finden auch Quasigruppen wichtige Anwendungen im Bereich der Kryptographie. Es lassen sich Hashfunktionen, Blockchiffren und auch Signaturverfahren konstruieren (siehe externe Links).

Eigenschaften

Jede Quasigruppe hat die Kürzungseigenschaft, d.h.

• $a\star c=b\star c$ folgt $a=b$
• $c\star a=c\star b$ folgt $a=b$

Das liegt daran, dass die linken Gleichungen bedeuten, dass $x_{1}=a$ und $x_{2}=b$ Lösungen der Gleichung $a\star c=x\star c$ (bzw. $c\star a=c\star x)$ sind. Weil in einer Quasigruppe aber höchstens eine Lösung für die Gleichung existiert, folgt $x_{1}=x_{2}$ bzw. $a=b.$

Anders ausgedrückt besagt die Kürzungseigenschaft nichts anderes, als dass sowohl die Links- als auch die Rechtsmultiplikation mit einem Element $a$ aus $Q$ eine injektive Abbildung von $Q$ in sich beschreiben $(x\mapsto a\star x$ bzw. $x\mapsto x\star a).$ Da Injektivität und Surjektivität für endliche Mengen identisch sind, sind die beiden Abbildungen für endliches $Q$ ersichtlich bijektiv. Aber auch im allgemeinen Fall (d. h. inklusive unendlichem $Q)$ ergibt sich die Bijektivität, da die Surjektivität durch die Existenz der Lösung jeder Gleichung $x\star a=y$ bzw. $a\star x=y$ garantiert wird. Denn damit gibt es zu jedem Bild $y$ einer Links- oder Rechtsmultiplikation mit dem Element $a$ ein Urbild $x.$

Die Bijektivität dieser beiden Abbildungen ist eine definierende Eigenschaft der Quasigruppen, d.h. sie kann ohne Weiteres zur alternativen Definition der Quasigruppen herangezogen werden: Ein Magma ist ganau dann eine Quasigruppe, wenn in ihm die durch die Rechts- und Linksmultiplikation induzierten Abbildungen bijektiv sind. Die Surjektivität garantiert dabei die Existenz der Lösungen der Gleichungen (1) und (2), aus der Injektivität ergibt sich die Eindeutigkeit.

Viele Beweise aus der Gruppentheorie, zu Aussagen, die sich speziell auf Gruppen beziehen, benutzen ganz wesentlich diese Eigenschaft. Benutzen sie nur diese Eigenschaft (von allen Eigenschaften, die sich rein aus den Gruppenaxiomen ergeben), so können die gemachten Aussagen sofort auf Quasigruppen verallgemeinert werden. Aber auch viele Aussagen, die nur geringfügig stärkere Voraussetzungen machen, können auf spezielle Quasigruppen – die keine Gruppen sein müssen – verallgemeinert werden.

Die Verknüpfungstabelle einer endlichen Quasigruppe ist ein lateinisches Quadrat: Eine $n\times n$-Tabelle gefüllt mit $n$ verschiedenen Symbolen, in der in jeder Zeile und in jeder Spalte jedes Symbol genau einmal vorkommt. Umgekehrt ist jedes lateinische Quadrat Verknüpfungstabelle einer Quasigruppe. Damit sind lateinische Quadrate und die hier ausgeführte abstrakt-beschreibende Definition lediglich zwei unterschiedliche, prinzipiell gleichberechtigte Darstellungen desselben mathematischen Objektes Quasigruppe.

Alternative Definition

Man kann in einer Quasigruppe $Q$ zwei weitere Verknüpfungen definieren: Für $a$ und $b$ aus $Q$ sei $a\operatorname {\setminus } b$ die Lösung von $a\star x=b$ und sei $b\operatorname {/} a$ die Lösung von $y\star a=b$ (man kann sich diese beiden als „Quasi-Brüche“ bzw. Links- und Rechtsbrüche „b links-durch a“ und „b rechts-durch a“ denken). Dann gilt offenbar:

${\begin{aligned}a\star (a\operatorname {\setminus } b)=b\\(b\operatorname {/} a)\star a=b\\a\operatorname {\setminus } (a\star b)=b\\(b\star a)\operatorname {/} a=b\\\end{aligned}}$

Dabei beschreiben die ersten beiden Gleichungen die Lösbarkeit von (1) und (2), und die anderen beiden Gleichungen die Eindeutigkeit der Lösungen. Man kann eine Quasigruppe also auch definieren als Algebra $(Q,\star ,\setminus ,\operatorname {/} )$ mit drei binären Verknüpfungen, die die eben genannten vier Gleichungen erfüllen.

Ist $Q$ eine Gruppe, dann ist $a\operatorname {\setminus } b=a^{{-}1}\star b$ und $b\operatorname {/} a=b\star a^{{-}1}.$ Ist die Quasigruppe kommutativ, dann sind die beiden Forderungen nach der eindeutigen Lösbarkeit von (1) und (2) gleichwertig und die Verknüpfungen $\operatorname {/}$ und $\operatorname {\setminus }$ fallen zusammen.

Quasigruppe mit Inverseneigenschaft

Eine Quasigruppe mit Inverseneigenschaft ist ein Magma $Q$, in dem es für alle $a$ und $b$ aus $Q$ ein eindeutiges Element $a^{{-}1}$ gibt, so dass gilt:

$a^{{-}1}\star (a\star b)=b=(b\star a)\star a^{{-}1}$ (Inverseneigenschaft).

Wie der Name anzeigt, ist eine Quasigruppe mit Inverseneigenschaft eine Quasigruppe, was wir hier beweisen wollen. Wir zeigen zunächst, dass eine Lösung $x$ der Gleichung $a\star x=c$ mit $a$ und $c$ aus $Q$ existiert; die Existenz von $x$ für $x\star a=c$ folgt analog. Sei dazu $w=a\star (a^{{-}1}\star c).$ Dann folgt aus der linken Seite der Inversengleichung:

$a^{{-}1}\star w=a^{{-}1}\star (a\star (a^{{-}1}\star c))=a^{{-}1}\star c.$

Multiplikation von links mit $(a^{{-}1})^{{-}1}$ gibt $(a^{{-}1})^{{-}1}(a^{{-}1}\star w)=(a^{{-}1})^{{-}1}(a^{{-}1}\star c)$ also $w=c.$ Das bedeutet aber $a\star (a^{{-}1}\star c)=c$, womit $x=a^{{-}1}\star c$ eine Lösung der Gleichung $a\star x=c$ ist.

Die Eindeutigkeit der Lösung $b$ (und analog der Lösung $a)$ folgt weil $b=a^{{-}1}\star c$ nur von a und c abhängt und die Zuordnung

$a\mapsto a^{{-}1}\mapsto (a^{{-}1}\star c)\mapsto b$

in jedem Teilschritt eindeutig ist.

Loop

Hat eine Quasigruppe ein neutrales Element, dann heißt sie eine Loop. Direkt aus der Definition der Quasigruppe folgt, dass in einer Loop jedes Element ein linksinverses und ein rechtsinverses Element hat, die aber – im Gegensatz zur Situation in einer Gruppe – nicht übereinstimmen müssen (siehe auch inverses Element). Die Struktur von Loops ist denen von Gruppen sehr ähnlich.

Eine Moufang-Loop (benannt nach Ruth Moufang) ist eine Quasigruppe $Q$, in der für alle $a,b$ und $c$ aus $Q$ gilt:

$(a\star b)\star (c\star a)=(a\star (b\star c))\star a.$

Wie der Name anzeigt, ist eine Moufang-Loop eine Loop, was wir hier beweisen wollen. Sei $a$ ein Element von $Q$ und $e=a\operatorname {\setminus } a$ das (eindeutig bestimmte) Element mit $a\star e=a.$ Dann gilt für jedes $x$ in $Q$:

$(x\star a)\star x=(x\star (a\star e))\star x=(x\star a)\star (e\star x),$

also nach dem Kürzen $x=e\star x.$ Damit ist $e$ ein linksneutrales Element. Sei nun $b=e\operatorname {\setminus } e$ das (eindeutig bestimmte) Element mit $b\star e=e.$ Dann gilt $y\star b=e\star (y\star b),$ da $e$ linksneutral ist, und

$(y\star b)\star e=(e\star (y\star b))\star e=(e\star y)\star (b\star e)=(e\star y)\star e=y\star e.$

Kürzen von $e$ ergibt $y\star b=y,$ also ist $b$ ein rechtsneutrales Element. Schließlich erhalten wir $e=e\star b=b,$ also ist $e$ ein beidseitig neutrales Element.

Da in einer Loop Links- und Rechtsinverse existieren, zeigt man analog, dass diese in einer Moufang-Loop identisch sind: Zu $a$ aus $Q$ seien $a^{L}$ und $a^{R}$ Links- und Rechsinverses. Dann gilt insbesondere $e=a\star a^{R},$ da $a^{R}$ rechtsneutral ist, und dann $a^{L}=a^{L}\star (a\star a^{R}).$ Multiplikation von rechts mit $a^{L}$ gibt:

$a^{L}\star a^{L}=(a^{L}\star (a\star a^{R}))\star a^{L}=\underbrace {(a^{L}\star a)} _{\text{= e}}\star (a^{R}\star a^{L})=e\star (a^{R}\star a^{L})=a^{R}\star a^{L}.$

Kürzen von $a^{L}$ ergibt $a^{L}=a^{R}.$

Jede assoziative Quasigruppe ist eine Moufang-Loop, und als assoziative Loop folglich eine Gruppe (da die Gruppenaxiome dann offensichtlich erfüllt sind). Dies zeigt, dass die Gruppen genau die assoziativen Quasigruppen sind (bzw. jene Quasigruppen, die gleichzeitig auch Halbgruppen sind).

Literatur

• Hall, Marshall: The theory of groups. © Macmillan New York, 1959.
• Kurosch, Aleksander Gennadljewitsch: Gruppentheorie.

Weblinks

• Enthält auch Verknüpfungstabellen der Quasigruppen der Ordnung 3 und einer echten Loop der Ordnung 5.
• Hashverfahren auf Basis Quasigruppen String Transformationen
• Übersicht über die wichtigsten kryptographische Anwendungen der Quasigruppen