Lights Assoziativitätstest

In der Mathematik ist Lights Assoziativitätstest ein von F. W. Light entwickeltes Verfahren, um zu prüfen, ob eine binäre Operation, die in einer endlichen Menge durch eine Cayley-Multiplikationstabelle definiert ist, assoziativ ist . Das naive Verfahren zur Überprüfung der Assoziativität einer durch eine Cayley-Tabelle spezifizierten binären Operation, das die beiden Produkte vergleicht, die aus jedem Tripel von Elementen gebildet werden können, ist umständlich. Lights Assoziativitätstest vereinfacht die Aufgabe in einigen Fällen (verbessert jedoch nicht die Laufzeit des naiven Algorithmus im ungünstigsten Fall, insbesondere für Mengen der Größe n ). ${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$${\displaystyle n}$

Eine binäre Operation ' · ' sei in einer endlichen Menge A durch eine Cayley-Tabelle definiert . Wählt man ein Element a in A , so werden zwei neue binäre Operationen in A wie folgt definiert:

${\displaystyle x\star y=x\cdot (a\cdot y)}$

${\displaystyle x\circ y=(x\cdot a)\cdot y}$

Die Cayley-Tabellen dieser Operationen werden erstellt und verglichen. Stimmen die Tabellen überein, so gilt dies für alle x und y . Dies wird für jedes Element der Menge A wiederholt . ${\displaystyle x\cdot (a\cdot y)=(x\cdot a)\cdot y}$

Das folgende Beispiel veranschaulicht eine weitere Vereinfachung des Verfahrens zur Erstellung und zum Vergleich der Cayley-Tabellen der Operationen ' ' und ' '. ${\displaystyle \star }$${\displaystyle \circ }$

Es ist nicht einmal notwendig, die Cayley-Tabellen von ' ' und ' ' für alle Elemente von A zu erstellen . Es genügt, die Cayley-Tabellen von ' ' und ' ' zu vergleichen, die den Elementen in einer echten erzeugenden Teilmenge von A entsprechen . ${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$

Wenn die Operation '·' kommutativ ist , dann gilt x y = y x. Daher muss nur ein Teil jeder Cayley-Tabelle berechnet werden, da x x = x x immer gilt und x y = x y y x = y x impliziert . ${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$

Wenn es ein neutrales Element e gibt , muss es nicht in die Cayley-Tabellen aufgenommen werden, da x y = x y immer gilt, wenn mindestens eines von x und y gleich e ist. ${\displaystyle \star }$${\displaystyle \circ }$

Betrachten Sie die binäre Operation ' · ' in der Menge A = { a , b , c , d , e }, die durch die folgende Cayley-Tabelle (Tabelle 1) definiert ist:

Die Menge { c , e } ist ein Erzeugendensystem für die Menge A bezüglich der in der obigen Tabelle definierten binären Operation, für die a = e · e , b = c · c und d = c · e gilt. Daher genügt es zu überprüfen, ob die zu c gehörigen binären Operationen ' ' und ' ' übereinstimmen und ob die zu e gehörigen binären Operationen ' ' und ' ' übereinstimmen . ${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$

Um zu überprüfen, ob die Binäroperationen ' ' und ' ', die dem Element c entsprechen , übereinstimmen, wählen Sie die Zeile in Tabelle 1, die dem Element c entspricht : ${\displaystyle \star }$${\displaystyle \circ }$

Diese Zeile wird als Kopfzeile einer neuen Tabelle (Tabelle 3) kopiert:

Unter der Überschrift a wird die entsprechende Spalte aus Tabelle 1 kopiert, unter der Überschrift b wird die entsprechende Spalte aus Tabelle 1 kopiert usw., und Tabelle 4 wird erstellt.

Um Tabelle 5 zu erhalten, werden nun die Spaltenüberschriften von Tabelle 4 gelöscht:

Die Cayley-Tabelle der binären Operation ' ', die dem Element c entspricht , ist in Tabelle 6 angegeben. ${\displaystyle \star }$

Tabelle 6

${\displaystyle \star }$(C)	A	B	C	D	e
A	A	A	A	D	D
B	A	C	B	D	D
C	A	B	C	D	D
D	D	D	D	A	A
e	D	e	e	A	A

Wählen Sie als Nächstes die Spalte c aus Tabelle 1 aus:

Kopieren Sie diese Spalte in die Indexspalte, um Tabelle 8 zu erhalten:

Für jeden Eintrag a in Tabelle 8 wird die entsprechende Zeile aus Tabelle 1 kopiert, für jeden Eintrag b die entsprechende Zeile aus Tabelle 1 usw., und Tabelle 9 wird erstellt.

Um Tabelle 10 zu erhalten, werden nun die Indexeinträge in der ersten Spalte von Tabelle 9 gelöscht:

Die Cayley-Tabelle der binären Operation ' ', die dem Element c entspricht , ist in Tabelle 11 angegeben. ${\displaystyle \circ }$

Tabelle 11

${\displaystyle \circ }$(C)	A	B	C	D	e
A	A	A	A	D	D
B	A	C	B	D	D
C	A	B	C	D	D
D	D	D	D	A	A
e	D	e	e	A	A

Man kann überprüfen, dass die Einträge in den verschiedenen Zellen von Tabelle 6 mit den Einträgen in den entsprechenden Zellen von Tabelle 11 übereinstimmen. Dies zeigt, dass x · ( c · y ) = ( x · c ) · y für alle x und y ∈ A gilt . Gäbe es eine Abweichung, so wäre x · ( c · y ) = ( x · c ) · y für alle x und y ∈ A nicht mehr gültig .

Dass x · ( e · y ) = ( x · e ) · y für alle x und y in A gilt, kann auf ähnliche Weise durch Aufstellen der folgenden Tabellen (Tabelle 12 und Tabelle 13) überprüft werden:

Tabelle 12

${\displaystyle \star }$( e )	A	B	C	D	e
A	D	D	D	A	A
B	D	D	D	A	A
C	D	D	D	A	A
D	A	A	A	D	D
e	A	A	A	D	D

Tabelle 13

${\displaystyle \circ }$( e )	A	B	C	D	e
A	D	D	D	A	A
B	D	D	D	A	A
C	D	D	D	A	A
D	A	A	A	D	D
e	A	A	A	D	D

Es ist nicht notwendig, die Cayley-Tabellen (Tabelle 6 und Tabelle 11) der binären Operationen ' ' und ' ' zu erstellen. Es genügt, die Spalte mit der Überschrift c aus Tabelle 1 in die Indexspalte von Tabelle 5 zu kopieren und die folgende Tabelle (Tabelle 14) zu erstellen. Anschließend kann überprüft werden, ob die a- Zeile von Tabelle 14 mit der a -Zeile von Tabelle 1, die b -Zeile von Tabelle 14 mit der b- Zeile von Tabelle 1 usw. übereinstimmt. Dieser Vorgang ist sinngemäß für alle Elemente der Erzeugendenmenge von A zu wiederholen . ${\displaystyle \star }$${\displaystyle \circ }$

Computersoftware kann geschrieben werden, um Lights Assoziativitätstest durchzuführen. Kehayopulu und Argyris haben ein solches Programm für Mathematica entwickelt . ^{[ 1 ]}

Lights Assoziativitätstest kann erweitert werden, um Assoziativität in einem allgemeineren Kontext zu testen. ^{[ 2 ] [ 3 ]}

Sei T = { t₁ _, t₂ _, , tₘ _} eine Menge , in der die Operation mit Juxtaposition bezeichnet wird . Sei X = { x₁ , x₂ _, , xₙ _} eine Menge. Es gebe eine Abbildung vom kartesischen Produkt T × X nach X, bezeichnet mit ( t , x ) ↦ tx _, und es sei gefordert zu prüfen, ob diese Abbildung die Eigenschaft besitzt. ${\displaystyle \ldots }$${\displaystyle \ldots }$

( st ) x = s ( tx ) für alle s , t in T und alle x in X .

Eine Verallgemeinerung des Assoziativitätstests von Light kann angewendet werden, um zu überprüfen, ob die obige Eigenschaft gilt oder nicht. Mathematisch ausgedrückt lautet die Verallgemeinerung wie folgt: Für jedes t ∈ T sei L ( t ) die m × n- Matrix der Elemente von X, deren i -te Zeile …

( ( t _i t ) x ₁ , ( t _i t ) x ₂ , , ( t _i t ) x _n ) für i = 1, , m${\displaystyle \ldots }$${\displaystyle \ldots }$

und sei R ( t ) die m × n- Matrix der Elemente von X , deren j -te Spalte die folgenden Elemente enthält:

( t ₁ ( tx _j ), t ₂ ( tx _j ), , t _m ​​( tx _j ) ) für j = 1, , n .${\displaystyle \ldots }$${\displaystyle \ldots }$

Gemäß dem verallgemeinerten Test (von Bednarek) ist die zu überprüfende Eigenschaft genau dann erfüllt, wenn L ( t ) = R ( t ) für alle t ∈ T gilt . Wenn X = T , reduziert sich Bednareks Test auf Lights Test.

Es gibt einen randomisierten Algorithmus von Rajagopalan und Schulman , der die Assoziativität in einer zur Eingabegröße proportionalen Zeit testet. (Die Methode eignet sich auch zum Testen bestimmter anderer Identitäten.) Die Laufzeit beträgt für eine Tabelle und eine Fehlerwahrscheinlichkeit . Der Algorithmus kann so modifiziert werden, dass er ein Tripel erzeugt , für das , falls vorhanden, in der Zeit . ^{[ 4 ]}${\displaystyle O(n^{2}\log {\frac {1}{\delta }})}$${\displaystyle n\times n}$${\displaystyle \delta }$${\displaystyle \langle a,b,c\rangle }$${\displaystyle (ab)c\neq a(bc)}$${\displaystyle O(n^{2}\log n\cdot \log {\frac {1}{\delta }})}$

• Clifford, Alfred Hoblitzelle ; Preston, Gordon Bamford (1961). Die algebraische Theorie der Halbgruppen. Band I. Mathematical Surveys, Nr. 7. Providence, RI: American Mathematical Society . ISBN 978-0-8218-0272-4MR  0132791 .​{{cite book}}: ISBN / Date incompatibility (help)(S. 7–9)