Test asociativity světel - Lights associativity test - Wikipedia

v matematika, Lightův test asociativity je postup, který vynalezl F. W. Light pro testování, zda a binární operace definované v a konečná množina podle a Cayleyův multiplikační stůl je asociativní. Naivní postup pro ověření asociativity binární operace specifikovaný Cayleyovou tabulkou, který porovnává dva produkty, které lze vytvořit z každé trojice prvků, je těžkopádný. Lightův test asociativity v některých případech úlohu zjednodušuje (i když nezlepšuje nejhorší dobu běhu naivního algoritmu, jmenovitě ${ displaystyle { mathcal {O}} vlevo (n ^ {3} vpravo)}$ pro sady velikostí ${ displaystyle n}$).

Popis postupu

Nechte binární operaci '·' definovat v konečné sadě A u Cayleyho stolu. Výběr nějakého prvku A v A, jsou definovány dvě nové binární operace A jak následuje:

X ${ displaystyle star}$ y = X · ( A · y )

X ${ displaystyle circ}$ y = ( X · A ) · y

Cayleyovy tabulky těchto operací jsou konstruovány a porovnány. Pokud se tabulky shodují, pak X · ( A · y ) = ( X · A ) · y pro všechny X a y. To se opakuje pro každý prvek sady A.

Níže uvedený příklad ilustruje další zjednodušení postupu pro konstrukci a srovnání Cayleyových tabulek operací. ${ displaystyle star}$ ' a ' ${ displaystyle circ}$ '.

Není ani nutné konstruovat Cayleyovy tabulky ${ displaystyle star}$ ' a ' ${ displaystyle circ}$ ' pro Všechno prvky A. Stačí srovnat Cayleyovy tabulky ${ displaystyle star}$ ' a ' ${ displaystyle circ}$ "odpovídající prvkům ve správné generující podmnožině A.

Když operace “. ' je komutativní, pak x ${ displaystyle star}$ y = y ${ displaystyle circ}$ X. Ve výsledku musí být vypočítána pouze část každé tabulky Cayley, protože x ${ displaystyle star}$ x = x ${ displaystyle circ}$ x vždy drží a x ${ displaystyle star}$ y = x ${ displaystyle circ}$ y znamená y ${ displaystyle star}$ x = y ${ displaystyle circ}$ X.

Když tam je prvek identity e, nemusí být zahrnuto do Cayleyových tabulek, protože x ${ displaystyle star}$ y = x ${ displaystyle circ}$ y vždy platí, pokud alespoň jedno z xay je rovno e.

Příklad

Zvažte binární operaci '·' v sadě A = { A, b, C, d, E } definovaný následující tabulkou Cayley (tabulka 1):

Sada { C, E } je generující množina pro množinu A v rámci binární operace definované výše uvedenou tabulkou, pro, A = E · E, b = C · C, d = C · E. Stačí tedy ověřit, že binární operace ${ displaystyle star}$ ' a ' ${ displaystyle circ}$ ' souhlasí s C shodovat a také, že binární operace ' ${ displaystyle star}$ ' a ' ${ displaystyle circ}$ ' souhlasí s E shodovat se.

Chcete-li ověřit, že binární operace ' ${ displaystyle star}$ ' a ' ${ displaystyle circ}$ ' souhlasí s C shodovat, vyberte řádek v tabulce 1 odpovídající prvku C:

Tento řádek je zkopírován jako řádek záhlaví nové tabulky (tabulka 3):

Pod hlavičkou A zkopírujte odpovídající sloupec v tabulce 1 pod záhlavím b zkopírujte odpovídající sloupec v tabulce 1 atd. a vytvořte tabulku 4.

Záhlaví sloupců tabulky 4 jsou nyní odstraněna, aby se získala tabulka 5:

Cayleyova tabulka binární operace ' ${ displaystyle star}$ 'odpovídající prvku C je uveden v tabulce 6.

Tabulka 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

Dále zvolte C sloupec tabulky 1:

Zkopírováním tohoto sloupce do indexového sloupce získáte tabulku 8:

Proti záznamu indexu A v tabulce 8 zkopírujte odpovídající řádek v tabulce 1 proti položce indexu b zkopírujte odpovídající řádek v tabulce 1 atd. a vytvořte tabulku 9.

Položky rejstříku v prvním sloupci tabulky 9 jsou nyní odstraněny, aby se získala tabulka 10:

Cayleyova tabulka binární operace ' ${ displaystyle circ}$ 'odpovídající prvku C je uveden v tabulce 11.

Tabulka 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

Lze ověřit, že položky v různých buňkách v tabulce 6 souhlasí s položkami v odpovídajících buňkách v tabulce 11. To ukazuje X · ( C · y ) = ( X · C ) · y pro všechny X a y v A. Pokud by došlo k nějakému rozporu, pak by to nebyla pravda X · ( C · y ) = ( X · C ) · y pro všechny X a y v A.

Že X · ( E · y ) = ( X · E ) · y pro všechny X a y v A lze ověřit podobným způsobem vytvořením následujících tabulek (tabulka 12 a tabulka 13):

Tabulka 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

Tabulka 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

Další zjednodušení

Není nutné sestavovat Cayleyovy tabulky (tabulka 6 a tabulka 11) binárních operací ' ${ displaystyle star}$ ' a ' ${ displaystyle circ}$ '. Stačí zkopírovat sloupec odpovídající hlavičce C v tabulce 1 do indexového sloupce v tabulce 5 a vytvořte následující tabulku (tabulka 14) a ověřte, zda A-row tabulky 14 je totožná s A- v tabulce 1, b-row tabulky 14 je totožná s b- řádek tabulky 1 atd. Toto je třeba opakovat mutatis mutandis pro všechny prvky generující sady A.

Program

Počítačový software lze napsat k provedení testu asociativity Light. Kehayopulu a Argyris vyvinuli takový program pro Mathematica.^[1]

Rozšíření

Lightův test asociativity lze rozšířit na testování asociativity v obecnějším kontextu.^[2][3]

Nechat T = { t₁, t₂, ${ displaystyle ldots}$, t_m } být magma ve kterém je operace označena juxtapozice. Nechat X = { X₁, X₂, ${ displaystyle ldots}$, X_n } být množinou. Nechť existuje mapování z kartézský součin T × X na X označeno (t, X) ↦ tx a nechat to být povinen otestovat, zda tato mapa má tuto vlastnost

(Svatý)X = s(tx) pro všechny s, t v T a všechno X v X.

K ověření, zda výše uvedená vlastnost platí nebo ne, lze použít zobecnění Lightova testu asociativity. V matematických notacích probíhá zobecnění následovně: Pro každou t v T, nechť L(t) být m × n matice prvků X jehož i - ta řada je

( (t_it)X₁, (t_it)X₂, ${ displaystyle ldots}$ , (t_it)X_n ) pro i = 1, ${ displaystyle ldots}$, m

a nechte R(t) být m × n matice prvků X, jehož prvky j - ten sloupec je

( t₁(tx_j), t₂(tx_j), ${ displaystyle ldots}$ , t_m(tx_j) ) pro j = 1, ${ displaystyle ldots}$, n.

Podle zobecněného testu (kvůli Bednarkovi) platí, že vlastnost, která má být ověřena, platí tehdy a jen tehdy L(t) = R(t) pro všechny t v T. Když X = T, Bednarkův test se redukuje na Lightův test.

Pokročilejší algoritmy

Existuje randomizovaný algoritmus Rajagopalana a Schulman testovat asociativitu v čase úměrném velikosti vstupu. (Metoda funguje také pro testování určitých dalších identit.) Konkrétně je to běhový modul ${ displaystyle O (n ^ {2} log { frac {1} { delta}})}$ pro ${ displaystyle n krát n}$ pravděpodobnost tabulky a chyby ${ displaystyle delta}$. Algoritmus lze upravit tak, aby vznikl trojnásobek ${ displaystyle langle a, b, c rangle}$ pro který ${ displaystyle (ab) c neq a (bc)}$, pokud existuje, včas ${ displaystyle O (n ^ {2} log n cdot log { frac {1} { delta}})}$.^[4]

Poznámky

Reference

• Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (1961). Algebraická teorie poloskupin. Sv. Já. Mathematical Surveys, No. 7. Providence, R.I .: Americká matematická společnost. ISBN  978-0-8218-0272-4. PAN  0132791. (str. 7–9)