15.3: Lema de Burnside

El lema de Burnside relaciona el número de clases de equivalencia de la acción de un grupo en un conjunto finito con el número de elementos del conjunto fijado por los elementos del grupo. Antes de declararlo y probarlo, necesitamos alguna notación y una proposición. Si un grupo\(G\) actúa sobre un conjunto finito\(\mathcal{C}\), sea ~ la relación de equivalencia inducida por esta acción. (Como antes, se\(\mathcal{C}\) denotará la acción de\(\pi∈G\) on\(\pi^∗\).) Denotar la clase de equivalencia que contiene\(C∈\mathcal{C}\) por\(C\) ⟩. Para\(\pi∈G\), vamos\(fix_C⁡(\pi)=\{C∈ \mathcal{C}:\pi^∗(C)=C\}\), el conjunto de colorantes fijados por\(\pi\). Porque\(C∈ \mathcal{C}\), deja\(stab_G⁡(C)=\{\pi∈G: \pi (C)=C\}\) ser el estabilizador de\(C\) in\(G\), las permutaciones en\(G\) ese arreglo\(C\).

Para ilustrar estos conceptos antes de aplicarlos, refiérase de nuevo a la Figura 15.2. Usando esa información, podemos determinarla\(fix_C⁡(r_2)=\{C_1,C_{10},C_{11},C_{16}\}\). Determinar el estabilizador de una coloración requiere encontrar las filas de la tabla en la que aparece. Así,\(stab_{D8}⁡(C_7)=\{ι,h\}\) y\(stab_{D8}⁡(C_{11})=\{ι,r_2,p,n\}\).

Proposición 15.8.

Que un grupo\(G\) actúe sobre un conjunto finito\(\mathcal{C}\). Entonces para todos\(C \in \mathcal{C}\),

\(\displaystyle \sum_{C' \in ⟨C⟩} |stab_G(C')| = |G|\).

Prueba

Dejar\(stab_G⁡(C)=\{\pi_1,…,\pi_k\}\) y\(T(C,C′)=\{\pi∈G:\pi^∗(C)=C′\}\). (Tenga en cuenta que\(T(C,C)=stab_G⁡(C)\).) Tomar\(\pi∈T(C,C′)\). Entonces\(\pi \circ \pi_1 ∈T(C,C′)\) para\(1≤i≤k\). Además, si\(\pi \circ \pi_i = \pi \circ \pi_j\), entonces\(\pi^{-1} \circ \pi \circ \pi_i = \pi^{-1} \circ \pi \circ \pi_j\). Así\(\pi_i = \pi_j\) y\(i=j\). Si\(\pi'∈T(C,C′)\), entonces\(\pi^{−1} \circ \pi′∈T(C,C)\). Así,\(\pi−1 \circ \pi′=\pi_i\) para algunos\(i\), y por lo tanto\(\pi′= \pi \circ \pi_i\). Por lo tanto\(T(C,C′)=\{\pi \circ \pi_1,…,\pi \circ \pi_k\}\). Adicionalmente, observamos eso\(T(C′,C)=\{\pi^{-1}:\pi∈T(C,C′)\}\). Ahora para todos\(C′∈⟨C⟩\),

\(|stab_G⁡(C′)|=|T(C′,C′)|=|T(C′,C)|=|T(C,C′)|=|T(C,C)|=|stab_G⁡(C)|\).

Por lo tanto,

\(\displaystyle \sum_{C' \in ⟨C⟩} |stab_G(C')| = \sum_{C' \in ⟨C⟩} |T(C,C')|\).

Ahora fíjate que cada elemento de\(G\) aparece en precisamente\(T(C,C′)\) por uno\(C′∈⟨C⟩\), y la proposición sigue.

Con la Proposición 15.8 establecida, ahora estamos preparados para el lema de Burnside.

Lema 15.9. Lema de Burnside.

Que un grupo\(G\) actúe sobre un conjunto finito\(\mathcal{C}\). Si\(N\) es el número de clases de equivalencia de\(\mathcal{C}\) inducidas por esta acción, entonces

\(N = \dfrac{1}{|G|} \displaystyle \sum_{\pi \in G} |fix_{\mathcal{C}}(\pi)|\).

Antes de proceder a la prueba, tenga en cuenta que el cálculo en el lema de Burnside para el ejemplo de 2-colorear los vértices de un cuadrado es exactamente el cálculo que realizamos al final de la Sección 15.1.

Prueba

Vamos\(X=\{(\pi,C) \in G \times \mathcal{C}: \pi (C)=C\}\). Observe que\(\sum_{\pi \in G} |fix_C⁡(\pi )|=|X|\), ya que cada término en la suma cuenta cuántos pares ordenados de\(X\) tienen\(\pi\) en su primera coordenada. De igual manera\(\sum_{C \in \mathcal{C}}|stab_G⁡(C)|=|X|\),, con cada término de esta suma contando cuántos pares ordenados de\(X\) tienen\(C\) como segunda coordenada. Por lo tanto,\(\sum_{C \in \mathcal{C}} |fix_C⁡(\pi)|=\sum_{C \in \mathcal{C}} |stab_G⁡(C)|\). Ahora tenga en cuenta que esta última suma puede ser reescrita como

\(\displaystyle \sum_{equivalence \\ classes ⟨C⟩} (\sum_{C' \in ⟨C⟩} |stab_G(C')|)\).

Por la Proposición 15.8, la suma interna es\(|G|\). Por lo tanto, la suma total es\(N \cdot |G|\), por lo que resolviendo para\(N\) da la ecuación deseada.

El lema de Burnside valida amparadamente los cálculos que hicimos en la sección anterior. No obstante, ¿y si en lugar de un cuadrado estuviéramos trabajando con un hexágono y en lugar de dos colores permitiéramos cuatro? Entonces habría\(4^6=4096\) diferentes colorantes y el grupo diedro del hexágono tiene 12 elementos. ¡Ensamblar el análogo de la Figura 15.2 en esta situación sería una pesadilla! Aquí es donde entra en juego el genio del enfoque de Pólya, como vemos en la siguiente sección.