Prueba de asociatividad de Light

Procedimiento del álgebra abstracta

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 multiplicación de Cayley es asociativa . El procedimiento ingenuo para la 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}$

Descripción del procedimiento

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

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

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

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 ejemplo siguiente ilustra una simplificación adicional en el procedimiento de construcción y comparación de las tablas de 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 . Es suficiente comparar las tablas de Cayley de ' ' y ' ' correspondientes a los elementos en un subconjunto generador propio 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 }$

Cuando hay un elemento identidad e, no es necesario incluirlo en las tablas de Cayley porque x y = x y siempre es válido si al menos uno de x e y son iguales a e. ${\displaystyle \star }$ ${\displaystyle \circ }$

Ejemplo

Considérese la operación binaria ' · ' en el conjunto A = { a , b , c , d , e } definido por la siguiente tabla de Cayley (Tabla 1):

El conjunto { c , e } es un conjunto generador del conjunto A bajo la operación binaria definida por la tabla anterior, para, a = e · e , b = c · c , d = c · e . Por lo tanto, basta con verificar que las operaciones binarias ' ' y ' ' correspondientes a c coinciden y también que las operaciones binarias ' ' y ' ' correspondientes a e coinciden. ${\displaystyle \star }$ ${\displaystyle \circ }$ ${\displaystyle \star }$ ${\displaystyle \circ }$

Para verificar que las operaciones binarias ' ' y ' ' correspondientes a c coinciden, elija la fila de la Tabla 1 correspondiente al elemento c : ${\displaystyle \star }$ ${\displaystyle \circ }$

Esta fila se copia como fila de encabezado de una nueva tabla (Tabla 3):

Bajo el encabezado a copie la columna correspondiente en la Tabla 1, bajo el encabezado b copie la columna correspondiente en la Tabla 1, etc., y construya la Tabla 4.

Los encabezados de columna de la Tabla 4 ahora se eliminan para obtener la Tabla 5:

La tabla de Cayley de la operación binaria ' ' correspondiente al elemento c está dada en la Tabla 6. ${\displaystyle \star }$

A continuación, seleccione la columna c de la Tabla 1:

Copie esta columna en la columna de índice para obtener la Tabla 8:

Frente a la entrada de índice a de la Tabla 8, copie la fila correspondiente de la Tabla 1, frente a la entrada de índice b, copie la fila correspondiente de la Tabla 1, etc., y construya la Tabla 9.

Las entradas de índice en la primera columna de la Tabla 9 ahora se eliminan para obtener la Tabla 10:

La tabla de Cayley de la operación binaria ' ' correspondiente al elemento c está dada en la Tabla 11. ${\displaystyle \circ }$

Se puede verificar que las entradas en las distintas celdas de la Tabla 6 concuerdan con las entradas en las celdas correspondientes de la Tabla 11. Esto muestra que x · ( c · y ) = ( x · c ) · y para todos los x e y en A . Si hubiera alguna discrepancia, entonces no sería cierto que x · ( c · y ) = ( x · c ) · y para todos los x e y en A .

Que x · ( e · y ) = ( x · e ) · y para todos los x e y en A se puede verificar de manera similar construyendo las siguientes tablas (Tabla 12 y Tabla 13):

Una simplificación adicional

No es necesario construir las tablas de Cayley (Tabla 6 y Tabla 11) de las operaciones binarias ' ' y ' '. Es suficiente copiar la columna correspondiente al encabezado c de la Tabla 1 a la columna de índice de la Tabla 5 y formar la tabla siguiente (Tabla 14) y verificar que la fila a de la Tabla 14 es idéntica a la fila a de la Tabla 1, la fila b de la Tabla 14 es idéntica a la fila b de la Tabla 1, etc. Esto debe repetirse mutatis mutandis para todos los elementos del conjunto generador de A . ${\displaystyle \star }$ ${\displaystyle \circ }$

Programa

Se puede escribir un programa informático para realizar la prueba de asociatividad de Light. Kehayopulu y Argyris han desarrollado un programa de este tipo para Mathematica . ^[1]

Extensión

La prueba de asociatividad de Light se puede extender para probar la asociatividad en un contexto más general. ^{[2] [3]}

Sea T = { t ₁ , t ₂ , , t _m ​​} un magma en el que la operación se denota por yuxtaposición . Sea X = { x ₁ , x ₂ , , x _n } un conjunto. Sea una aplicación del producto cartesiano T × X a X denotada por ( t , x ) ↦ tx y sea necesario comprobar si esta aplicación tiene la propiedad ${\displaystyle \ldots }$ ${\displaystyle \ldots }$

( st ) x = s ( tx ) para todos los s , t en T y todos los x en X .

Se puede aplicar una generalización de la prueba de asociatividad de Light para verificar si la propiedad anterior se cumple o no. En notación matemática, la generalización es la siguiente: Para cada t en T , sea L ( t ) la matriz m × n de elementos de X cuya i - ésima fila es

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

y sea R ( t ) la matriz m × n de elementos de X , cuyos elementos de la j - ésima columna son

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

Según la prueba generalizada (debida a Bednarek), la propiedad a verificar se cumple si y sólo si L ( t ) = R ( t ) para todo t en T . Cuando X = T , la prueba de Bednarek se reduce a la prueba de Light.

Algoritmos más avanzados

Existe un algoritmo aleatorio de Rajagopalan y Schulman para probar la asociatividad en tiempo proporcional al tamaño de entrada. (El método también funciona para probar otras identidades). Específicamente, el tiempo de ejecución es para una tabla y probabilidad de error . El algoritmo se puede modificar para producir un triple para el cual , si hay uno, en tiempo . ^[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 }})}$

Notas

1. Kehayopulu, Niovi; Philip Argyris (1993). "Un algoritmo para la prueba de asociatividad de Light usando Mathematica". J. Comput. Inform . 3 (1): 87–98. ISSN  1180-3886.
2. Bednarek, AR (1968). "Una extensión de la prueba de asociatividad de Light". American Mathematical Monthly . 75 (5): 531–532. doi :10.2307/2314731. JSTOR  2314731.
3. Kalman, JA (1971). "Extensión de Bednarek de la prueba de asociatividad de Light". Semigroup Forum . 3 (1): 275–276. doi :10.1007/BF02572966. S2CID  124362744.
4. Rajagopalan, Sridhar; Schulman, Leonard J. (2000). "Verificación de identidades". Revista SIAM de informática . 29 (4): 1155–1163. CiteSeerX 10.1.1.4.6898 . doi :10.1137/S0097539797325387. 

Referencias

• Clifford, Alfred Hoblitzelle ; Preston, Gordon Bamford (1961). La teoría algebraica de semigrupos. Vol. I. Mathematical Surveys, n.º 7. Providence, RI: American Mathematical Society . ISBN. 978-0-8218-0272-4.Sr .  0132791.(págs. 7–9)