El lema de Burnside, a veces también llamado teorema de conteo de Burnside, lema de Cauchy-Frobenius o teorema de conteo de órbitas, es un resultado de la teoría de grupos que suele ser útil para tener en cuenta la simetría al contar objetos matemáticos. Fue descubierto por Augustin Louis Cauchy y Ferdinand Georg Frobenius, y se hizo muy conocido después de que William Burnside lo citara. [1] El resultado enumera las órbitas de un grupo de simetría que actúa sobre algunos objetos: es decir, cuenta objetos distintos, considerando los objetos simétricos entre sí como iguales; o contar objetos distintos hasta una relación de equivalencia de simetría; o contando sólo objetos en forma canónica. Por ejemplo, al describir posibles compuestos orgánicos de cierto tipo, se los considera hasta la simetría de rotación espacial: diferentes dibujos rotados de una molécula dada son químicamente idénticos. (Sin embargo, un reflejo en un espejo podría dar un compuesto diferente).
Formalmente, sea G un grupofinito que actúa sobre un conjuntoX. Para cada g en G, sea X g el conjunto de elementos en X que están fijados porg (invariantes a la izquierda por g): es decir, X g = {x ∈ X | g.x = x}. El lema de Burnside afirma la siguiente fórmula para el número de órbitas, denotada |X/G|: [2]Así, el número de órbitas (un número natural o +∞) es igual al número medio de puntos fijados por un elemento de G. Para un grupo infinito G, todavía hay una biyección:
Ejemplos de aplicaciones a la enumeración
Collares
Hay 8 posibles cadenas de bits de longitud 3, pero al unir los extremos de la cadena solo se obtienen cuatro collares distintos de 2 colores de longitud 3, dados por las formas canónicas 000, 001, 011, 111: las otras cadenas 100 y 010 son equivalentes a 001 por rotación, mientras que 110 y 101 equivalen a 011. Es decir, la equivalencia de rotación divide el conjunto X de cuerdas en cuatro órbitas:
La fórmula de Burnside utiliza el número de rotaciones, que es 3 incluida la rotación nula, y el número de cadenas de bits que no cambian con cada rotación. Todos los vectores de 8 bits no cambian con la rotación nula, y dos (000 y 111) no cambian con las otras dos rotaciones. Por tanto, el número de órbitas es:Para una longitud 4, hay 16 cadenas de bits posibles; 4 rotaciones; la rotación nula deja las 16 cadenas sin cambios; las rotaciones de 1 y 3 dejan cada una dos cadenas sin cambios (0000 y 1111); la rotación 2 deja cadenas de 4 bits sin cambios (0000, 0101, 1010, 1111). El número de collares distintos es así: , representado por las formas canónicas 0000, 0001, 0011, 0101, 0111, 1111.
El caso general de n bits y k colores viene dado por un polinomio de collar.
Colores de un cubo
El lema de Burnside puede calcular el número de coloraciones rotacionalmente distintas de las caras de un cubo utilizando tres colores.
Sea X el conjunto de 3 6 posibles combinaciones de colores de caras que se pueden aplicar a un cubo fijo, y dejemos que el grupo de rotación G del cubo actúe sobre X moviendo las caras coloreadas: dos coloraciones en X pertenecen a la misma órbita precisamente cuando uno es una rotación del otro. Los colores rotacionalmente distintos corresponden a órbitas de grupo, y se pueden encontrar contando los tamaños de los conjuntos fijos para los 24 elementos de G, los colores no cambian con cada rotación:
Cubo con caras de colores.
el elemento de identidad arregla los 36 colores
seis rotaciones de cara de 90 grados cada una fija 33 colores
tres rotaciones de cara de 180 grados cada una fija 34 colores
ocho rotaciones de vértice de 120 grados cada una fija 32 colores
seis rotaciones de borde de 180 grados fijan cada una 33 colores.
Puede encontrar un examen detallado aquí.
El tamaño medio del conjunto fijo es, por tanto:
Hay 57 colores distintos por rotación de las caras de un cubo en tres colores. En general, el número de coloraciones rotacionalmente distintas de las caras de un cubo en n colores es:
Prueba
En la prueba del lema de Burnside, el primer paso es reexpresar la suma sobre los elementos del grupo g ∈ G como suma equivalente sobre el conjunto de elementos x ∈ X:
Aquí X g = {X ∈ X | gx = x} es el conjunto de puntos de X fijados por g ∈ G, mientras que G x = {g ∈ GRAMO | gx = x} es el subgrupo estabilizador de G, simetrías que fijan el punto x ∈ X.)
Escribiendo X como la unión disjunta de sus órbitas en X/G:
Juntando todo da el resultado deseado:
Esto es similar a la prueba de la ecuación de clase de conjugación, que considera la acción de conjugación de G sobre sí mismo: X = G y g.x = gxg−1, de modo que el estabilizador de x es centralizador: G x = Z G (x).
Enumeración versus generación
El lema de Burnside cuenta objetos distintos, pero no los construye. En general, la generación combinatoria con rechazo de isomorfos considera la de simetrías g, sobre objetos x. Pero en lugar de verificar que gx = x, verifica que gx aún no se haya generado. Una forma de lograr esto es verificando que gx no sea lexicográficamente menor que x, utilizando el miembro lexicográficamente menor de cada clase de equivalencia como la forma canónica de la clase. [3] Contar los objetos generados con dicha técnica puede verificar que el lema de Burnside se aplicó correctamente.
Historia: el lema que no es el de Burnside
William Burnside afirmó y demostró este lema en su libro de 1897 sobre grupos finitos, atribuyéndolo a Frobenius, 1887. Pero incluso antes de Frobenius, Cauchy conocía la fórmula en 1845. En consecuencia, este lema a veces se denomina lema que no es de Burnside . [4] La denominación errónea de los descubrimientos científicos se conoce como ley de eponimia de Stigler.
Cheng, Yuanyou (1986). «A generalization of Burnside's lemma to multiply transitive groups». Journal of Hubei University of Technology. ISSN1003-4684..
Rotman, Joseph (1995), An introduction to the theory of groups, Springer-Verlag, ISBN0-387-94285-8..