Prueba de asociatividad de la luz

En matemáticas , la prueba de asociatividad de Light es un procedimiento inventado por FW Light para probar si una operación binaria definida en un conjunto finito por una tabla de multiplicar de Cayley es asociativa . El ingenuo procedimiento de verificación de la asociatividad de una operación binaria especificada por una tabla de Cayley, que compara los dos productos que se pueden formar a partir de cada triple de elementos, es engorroso. La prueba de asociatividad de Light simplifica la tarea en algunos casos (aunque no mejora el tiempo de ejecución en el peor de los casos del algoritmo ingenuo, es decir, para conjuntos de tamaño ). ${\ Displaystyle {\ mathcal {O}} \ left (n ^ {3} \ right)}$ ${\ Displaystyle n}$

Sea una operación binaria '·' definida en un conjunto finito A mediante una tabla de Cayley. Al elegir algún elemento a en A , se definen dos nuevas operaciones binarias en A de la siguiente manera:

Se construyen y comparan las tablas de Cayley de estas operaciones. Si las tablas coinciden, entonces x · ( a · y ) = ( x · a ) · y para todo x e y . Esto se repite para cada elemento del conjunto A .

El siguiente ejemplo ilustra una simplificación adicional en el procedimiento para la construcción y comparación de las tablas Cayley de las operaciones ' ' y ' '. ${\ Displaystyle \ star}$ ${\ Displaystyle \ circ}$

Ni siquiera es necesario construir las tablas de Cayley de ' ' y ' ' para todos los elementos de A . Basta comparar las tablas de Cayley de ' ' y ' ' que corresponden a los elementos de un subconjunto de generación adecuada de A . ${\ Displaystyle \ star}$ ${\ Displaystyle \ circ}$ ${\ Displaystyle \ star}$ ${\ Displaystyle \ circ}$

Cuando la operación '. 'es conmutativa , entonces x y = y x. Como resultado, solo se debe calcular una parte de cada tabla de Cayley, porque x x = x x siempre se cumple, y x y = x y implica y x = y x. ${\ Displaystyle \ star}$ ${\ Displaystyle \ circ}$ ${\ Displaystyle \ star}$ ${\ Displaystyle \ circ}$ ${\ Displaystyle \ star}$ ${\ Displaystyle \ circ}$ ${\ Displaystyle \ star}$ ${\ Displaystyle \ circ}$