Lema de Burnside

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 grupo finito que actúa sobre un conjunto X. Para cada g en G, sea X ^g el conjunto de elementos en X que están fijados por g (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]$${\displaystyle |X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|.}$$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:$${\displaystyle G\times X/G\ \longleftrightarrow \ \coprod _{g\in G}X^{g}.}$$

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:

${\displaystyle X=\{000\}\cup \{001,010,100\}\cup \{011,101,110\}\cup \{111\}.}$

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:$${\displaystyle 4={\frac {1}{3}}(8+2+2).}$$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í: ${\displaystyle 6={\tfrac {1}{4}}(16+2+4+2)}$, 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 ⁶ 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 3⁶ colores
• seis rotaciones de cara de 90 grados cada una fija 3³ colores
• tres rotaciones de cara de 180 grados cada una fija 3⁴ colores
• ocho rotaciones de vértice de 120 grados cada una fija 3² colores
• seis rotaciones de borde de 180 grados fijan cada una 3³ colores.

Puede encontrar un examen detallado aquí.

El tamaño medio del conjunto fijo es, por tanto:

${\displaystyle |X/G|={\frac {1}{24}}\left(3^{6}+6\cdot 3^{3}+3\cdot 3^{4}+8\cdot 3^{2}+6\cdot 3^{3}\right)=57.}$

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:

${\displaystyle {\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right).}$

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:

${\displaystyle \sum _{g\in G}|X^{g}|=\#\{(g,x)\in G\times X\mid g\cdot x=x\}=\sum _{x\in X}|G_{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.)

El teorema del estabilizador de órbita dice que para cada x ∈ X existe una biyección natural entre la órbita G·x = { g·x | gramo ∈ G} y el conjunto de clases laterales izquierdas G/G_x. El teorema de Lagrange implica:

${\displaystyle |G\cdot x|=[G\,:\,G_{x}]=|G|/|G_{x}|.}$

Por lo tanto, la suma puede reescribirse como:

${\displaystyle \sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|G\cdot x|}}=|G|\sum _{x\in X}{\frac {1}{|G\cdot x|}}.}$

Escribiendo X como la unión disjunta de sus órbitas en X/G:

${\displaystyle |G|\,\sum _{x\in X}{\frac {1}{|G\cdot x|}}\ =\ |G|\!\sum _{A\in X/G}\,\sum _{x\in A}{\frac {1}{|A|}}\ =\ |G|\!\sum _{A\in X/G}1\ =\ |G|\,|X/G|.}$

Juntando todo da el resultado deseado:

${\displaystyle \sum _{g\in G}|X^{g}|=|G|\cdot |X/G|.}$

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 ⁻¹, 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.

Véase también

• Teorema de enumeración de Pólya
• Índice de ciclo

Notas

1. Burnside, 1897, §119
2. Rotman, 1995, Chapter 3
3. Cull, Paul; Pandey, Rajeev (1994). «Isomorphism and the N-Queens problem». ACM Sigcse Bulletin 26 (3): 29-36. doi:10.1145/187387.187400.
4. Neumann, Peter M. (1979). «A lemma that is not Burnside's». The Mathematical Scientist 4 (2): 133-141. ISSN 0312-3685..

Referencias

• Burnside, William (1897). Theory of Groups of Finite Order. Cambridge University Press. Also available here at Archive.org. (This is the first edition; the introduction to the second edition contains Burnside's famous volte face regarding the utility of representation theory.)
• Frobenius, Ferdinand Georg (1887), «Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul», Crelle's Journal 101 (4): 273-299, doi:10.3931/e-rara-18804..
• Cheng, Yuanyou (1986). «A generalization of Burnside's lemma to multiply transitive groups». Journal of Hubei University of Technology. ISSN 1003-4684..
• Rotman, Joseph (1995), An introduction to the theory of groups, Springer-Verlag, ISBN 0-387-94285-8..