Lema14.18
Sea \(X\) un \(G\)-conjunto y supongamos que \(x \sim y\text{.}\) Entonces \(G_x\) es isomorfo a \(G_y\text{.}\) En particular, \(|G_x| = |G_y|\text{.}\)
Sección14.3Teorema de Conteo de Burnside
¶Supongamos que deseamos pintar los vértices de un cuadrado con dos colores diferentes, digamos blanco y negro. Podríamos sospechar que habría \(2^4=16\) coloreados diferentes. Pero, algunos de estos son equivalentes. Si pintamos el primer vértice negro y los demás vértices blancos, es lo mismo que pintar el segundo vértice negro y los demás blancos pues podemos obtener el segundo coloreado simplemente rotando el cuadrado \(90^\circ\) (Figura 14.17).
El Teorema de Conteo de Burnside ofrece un método de calcular el número de maneras distinguibles en que algo puede ser realizado. Además de sus aplicaciones geométricas, el teorema tiene interesantes aplicaciones en teoría de conmutación (switching theory) y en química. La demostración del Teorema de Conteo de Burnside depende del siguiente lema.
Demostración
Supongamos que la acción de \(G\) en \(X\) está dada por \((g,x) \mapsto g \cdot x\text{.}\) Como \(x \sim y\text{,}\) existe \(g \in G\) tal que \(g \cdot x=y\text{.}\) Sea \(a \in G_x\text{.}\) Como
\begin{equation*} gag^{-1} \cdot y = ga \cdot g^{-1}y = ga \cdot x = g \cdot x = y, \end{equation*}podemos definir una función \(\phi: G_x \rightarrow G_y\) por \(\phi(a) = gag^{-1}\text{.}\) La función \(\phi\) es un homomorfismo pues
\begin{equation*} \phi(ab) = gabg^{-1} = gag^{-1} gbg^{-1} = \phi(a) \phi(b). \end{equation*}Supongamos que \(\phi(a) = \phi(b)\text{.}\) Entonces \(gag^{-1}= gbg^{-1}\) y \(a=b\text{;}\) es decir, la función es inyectiva. Para mostrar que \(\phi\) es epiyectiva, sea \(b\) en \(G_y\text{;}\) entonces \(g^{-1}bg\) está en \(G_x\) pues
\begin{equation*} g^{-1}bg \cdot x = g^{-1}b \cdot gx = g^{-1}b \cdot y = g^{-1} \cdot y = x; \end{equation*}y \(\phi(g^{-1}bg ) = b\text{.}\)
Teorema14.19Burnside
Sea \(G\) un grupo finito que actuando en un conjunto \(X\) y sea \(k\) el número de órbitas de \(X\text{.}\) Entonces
\begin{equation*} k = \frac{1}{|G|} \sum_{g \in G} |X_g|. \end{equation*}Demostración
Consideramos todos los puntos fijos de \(x\) para cada elemento \(g \in G\text{;}\) es decir, consideramos todos los \(g\) y todos los \(x\) tales que \(gx =x\text{.}\) En términos de conjuntos de puntos fijos, el número de todos los \(g\) que fijan a \(x\) es
\begin{equation*} \sum_{g \in G} |X_g|. \end{equation*}Pero, en términos de subgrupos estabilizadores, este número es
\begin{equation*} \sum_{x \in X} |G_x|; \end{equation*}luego, \(\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x|\text{.}\) Por el Lema 14.18,
\begin{equation*} \sum_{y \in {\mathcal O}_x} |G_y| = | {\mathcal O}_x| \cdot |G_x|. \end{equation*}Por el Teorema 14.11 y el Teorema de Lagrange, esta expresión es igual a \(|G|\text{.}\) Sumando en las \(k\) órbitas distintas, concluimos que
\begin{equation*} \sum_{g \in G} |X_g| = \sum_{x \in X} |G_x| = k \cdot |G|. \end{equation*}Ejemplo14.20
Sea \(X = \{1, 2, 3, 4, 5 \}\) y supongamos que \(G\) es el grupo de permutaciones \(G= \{(1), (1 3), (1 3)(2 5), (2 5) \}\text{.}\) Las órbitas en \(X\) son \(\{1, 3\}\text{,}\) \(\{2, 5\}\text{,}\) y \(\{4\}\text{.}\) Los conjuntos de puntos fijos son
\begin{align*} X_{(1)} & = X\\ X_{(1 3)} & = \{2, 4, 5 \}\\ X_{(1 3)(2 5)} & = \{4\}\\ X_{(2 5)} & = \{1, 3, 4 \}. \end{align*}El Teorema de Burnside dice que
\begin{equation*} k = \frac{1}{|G|} \sum_{g \in G} |X_g| = \frac{1}{4}(5 + 3 + 1 + 3) = 3. \end{equation*}SubsecciónUn Ejemplo Geométrico
¶Antes de aplicar el Teorema de Burnside a problemas de teoría de conmutación, examinemos el número de maneras en que se pueden colorear los vértices de un cuadrado utilizando dos colores, blanco y negro. Notemos que a veces obtendremos coloreados equivalentes simplemente aplicando un movimiento rígido al cuadrado. Por ejemplo, como mencionamos antes, si pintamos un vértice negro y los restantes blancos, no importa cuál es el vértice negro pues una rotación nos dará una forma equivalente de pintarlos.
El grupo de simetría de un cuadrado, \(D_4\text{,}\) está dado por las siguientes permutaciones:
\begin{align*} &(1) & &(13) & & (24) & & (1432)\\ &(1234) & &(12)(34) & & (14)(23) & & (13)(24) \end{align*}El grupo \(G\) actúa en el conjunto de vértices \(\{ 1, 2, 3, 4\}\) en la forma usual. Podemos describir los diferentes coloreados como funciones de \(X\) en \(Y = \{ N, B \}\) donde \(N\) y \(B\) representan los colores negro y blango, respectivamente. Cada función \(f : X \rightarrow Y\) describe una forma de colorear las esquinas del cuadrado. Cada \(\sigma \in D_4\) induce una permutación \(\widetilde{ \sigma }\) de los posibles coloreados dada por \(\widetilde{\sigma}(f) = f \circ \sigma\) for \(f : X \rightarrow Y\text{.}\) Por ejemplo, supongamos que \(f\) está definida por
\begin{align*} f(1) & = N\\ f(2) & = B\\ f(3) & = B\\ f(4) & = B \end{align*}y \(\sigma = (1 2)(3 4)\text{.}\) Entonces \(\widetilde{\sigma}(f) = f \circ \sigma\) envía el vértice 2 en \(N\) y los restantes vértices en \(B\text{.}\) El conjunto de tales \(\widetilde{\sigma}\) es un grupo de permutaciones \(\widetilde{G}\) en el conjunto de los posibles coloreados. Digamos que \(\widetilde{X}\) denota el conjunto de todos los posibles coloreados; es decir, \(\widetilde{X}\) es el conjunto de todas las posibles funciones de \(X\) en \(Y\text{.}\) Ahora debemos calcular el número de clases de equivalencia respecto a \(\widetilde{G}\text{.}\)
\(\widetilde{X}_{(1)} = \widetilde{X}\) pues la identidad fija todos los posibles coloreados. \(|\widetilde{X}| = 2^4 =~16\text{.}\)
\(\widetilde{X}_{(1 2 3 4)}\) consiste de todas las \(f \in \widetilde{X}\) tales que \(f\) no cambia al aplicarle la permutación \((1 2 3 4)\text{.}\) En este caso \(f(1) = f(2) = f(3) = f(4)\text{,}\) de manera que todos los valores de \(f\) deben ser iguales; es decir, ya sea \(f(x)= N\) o \(f(x)= B\) para todos los vértices \(x\) del cuadrado. Así \(|\widetilde{X}_{(1 2 3 4)}| = 2\text{.}\)
\(|\widetilde{X}_{(1 4 3 2)}| = 2\text{.}\)
For \(\widetilde{X}_{(1 3)(2 4)}\text{,}\) \(f(1) = f(3)\) and \(f(2) = f(4)\text{.}\) Luego, \(|\widetilde{X}_{(13)(24)}| = 2^2 = 4\text{.}\)
\(|\widetilde{X}_{(1 2)(3 4)}| = 4\text{.}\)
\(|\widetilde{X}_{(1 4)(2 3)}| = 4\text{.}\)
Para \(\widetilde{X}_{(1 3 )}\text{,}\) \(f(1) = f(3)\) y las demás esquinas pueden ser de cualquier color; luego, \(|\widetilde{X}_{(1 3)}| = 2^3 = 8\text{.}\)
\(|\widetilde{X}_{(2 4)}| = 8\text{.}\)
Por el Teorema de Burnside, podemos conluir que hay exactamente
\begin{equation*} \frac{1}{8} ( 2^4 + 2^1 + 2^2 + 2^1 + 2^2 + 2^2 +2^3 + 2^3) = 6 \end{equation*}maneras de colorear los vértices del cuadrado.
Proposición14.21
Sea \(G\) un grupo de permutaciones de \(X\) y \(\widetilde{X}\) el conjunto de funciones de \(X\) en \(Y\text{.}\) Entonces existe un grupo de permutaciones \(\widetilde{G}\) actuando en \(\widetilde{X}\text{,}\) donde \(\widetilde{\sigma} \in \widetilde{G}\) está definido por \(\widetilde{\sigma}(f) = f \circ \sigma\) para \(\sigma \in G\) y \(f \in \widetilde{X}\text{.}\) Más aún, si \(n\) es el número de ciclos en la descomposición cíclica de \(\sigma\text{,}\) entonces \(|\widetilde{X}_{\sigma}| = |Y|^n\text{.}\)
Demostración
Sea \(\sigma \in G\) y \(f \in \widetilde{X}\text{.}\) Claramente, \(f \circ \sigma\) también está en \(\widetilde{X}\text{.}\) Supongamos que \(g\) es otra función de \(X\) en \(Y\) tal que \(\widetilde{\sigma}(f) = \widetilde{\sigma}(g)\text{.}\) Entonces para cada \(x \in X\text{,}\)
\begin{equation*} f( \sigma(x )) = \widetilde{\sigma}(f)(x) = \widetilde{\sigma}(g)(x) = g( \sigma(x )). \end{equation*}Como \(\sigma\) es una permutación de \(X\text{,}\) todo elemento \(x'\) en \(X\) es la imagen de algún \(x\) en \(X\) por \(\sigma\text{;}\) luego, \(f\) y \(g\) coinciden en los elementos de \(X\text{.}\) Por lo tanto, \(f=g\) y \(\widetilde{\sigma}\) es inyectiva. La función \(\sigma \mapsto \widetilde{\sigma}\) es epiyectiva, pues los dos conjuntos son del mismo tamaño (finito).
Supongamos que \(\sigma\) es una permutación de \(X\) con descomposición cíclica \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_n\text{.}\) Cualquier \(f\) en \({\widetilde{X}}_{\sigma}\) debe tener el mismo valor en cada ciclo de \(\sigma\text{.}\) Como hay \(n\) ciclos e \(|Y|\) valores posibles para cada ciclo, \(|{\widetilde{X}}_{\sigma}| = |Y|^n\text{.}\)
Ejemplo14.22
Sea \(X = \{1, 2, \ldots, 7\}\) y supongamos que \(Y = \{ A, B, C \}\text{.}\) Si \(g\) es la permutación de \(X\) dada por \((1 3)(2 4 5) = (1 3)(2 4 5)(6)(7)\text{,}\) entonces \(n = 4\text{.}\) Cualquier \(f \in \widetilde{X}_g\) debe tener el mismo valor para cada ciclo en \(g\text{.}\) Existen \(|Y|=3\) elecciones para cada valor, así \(|\widetilde{X}_g| = 3^4 = 81\text{.}\)
Ejemplo14.23
Supongamos que queremos colorear los vértices de un cuadrado usando cuatro colores diferentes. Por la Proposición 14.21, podemos decidir inmediatamente que existen
\begin{equation*} \frac{1}{8} (4^4 + 4^1 + 4^2 + 4^1 + 4^2 + 4^ 2 + 4^3 + 4^3) = 55 \end{equation*}maneras posibles.
SubsecciónFunciones de Conmutación
¶En la teoría de conmutación, estamos interesados en el diseño de circuitos electrónicos con entradas y salidas binarias. El más simple de tales circuitos es una función de conmutación que tiene \(n\) entradas y una sola salida (Figura 14.24). Circuitos electrónicos grandes con frecuencia se pueden construir combinando módulos más pequeños de este tipo. El problema inherente acá es que incluso para un circuito simple existe un gran número de funciones de conmutación. Con solo cuatro entradas y una salida, podemos construir 65,536 funciones de conmutación diferentes. Pero, muchas veces podemos transformar una función de conmutación en otra simplemente permutando las entradas del circuito (Figura 14.25).
Definimos una función de conmutación o función Booleana de \(n\) variables como una función de \({\mathbb Z}_2^n\) en \({\mathbb Z}_2\text{.}\) Como cualquier función de conmutación puede tomar dos valores para cada \(n\)-tupla binaria y hay \(2^n\) \(n\)-tuplas binarias, existen \(2^{2^n}\) funciones de conmutación para \(n\) variables. En general, permitir las permutaciones de las entradas, reduce dramáticamente el número de módulos de diferente tipo requeridos para construir un circuito grande.
Las posibles funciones de conmutación con dos variables de entrada \(a\) y \(b\) se listan en la Tabla 14.26. Dos funciones de conmutación \(f\) y \(g\) son equivalentes si \(g\) puede ser obtenida a partir de \(f\) por una permutación de las variables de entrada. Por ejemplo, \(g(a, b, c) = f(b, c, a)\text{.}\) En este caso \(g \sim f\) via la permutación \((acb)\text{.}\) En el caso de funciones de permutación de dos variables, la permutación \((ab)\) reduce las 16 posibles funciones de permutación a 12 funciones no-equivalentes pues
\begin{align*} f_2 & \sim f_4\\ f_3 & \sim f_5\\ f_{10} & \sim f_{12}\\ f_{11} & \sim f_{13}. \end{align*}| Entradas | Salidas | ||||||||
| \(f_0\) | \(f_1\) | \(f_2\) | \(f_3\) | \(f_4\) | \(f_5\) | \(f_6\) | \(f_7\) | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Entradas | Salidas | ||||||||
| \(f_8\) | \(f_9\) | \(f_{10}\) | \(f_{11}\) | \(f_{12}\) | \(f_{13}\) | \(f_{14}\) | \(f_{15}\) | ||
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Para tres variables de entrada hay \(2^{2^3} = 256\) funciones de conmutación posibles; en el caso de cuatro variables hay \(2^{2^4} =\text{65,536}\text{.}\) El número de clases de equivalencia es demasiado grande para que sea razonable calcularlo directamente. Es necesario emplear el Teorema de Burnside.
Considere la función de conmutación con tres entradas posibles, \(a\text{,}\) \(b\text{,}\) y \(c\text{.}\) Como mencionamos, dos funciones de conmutación \(f\) y \(g\) son equivalentes si una permutación de las variables de entrada de \(f\) da \(g\text{.}\) Es importante notar que una permutación de las funciones de conmutación no es simplemente una permutación de los valores de entrada \(\{a, b, c\}\text{.}\) Una función de conmutación es un conjunto de valores de salida para las entradas \(a\text{,}\) \(b\text{,}\) y \(c\text{,}\) así, cuando consideramos funciones de conmutación equivalentes, estamos permutando \(2^3\) salidas posibles, no solo tres valores de entrada. Por ejemplo, cada tripleta binaria \((a, b, c)\) tiene asociada una salida específica. La permutación \((acb)\) cambia la salida como sigue:
\begin{align*} (0, 0, 0) & \mapsto (0, 0, 0)\\ (0, 0, 1) & \mapsto (0, 1, 0)\\ (0, 1, 0) & \mapsto (1, 0, 0)\\ & \vdots \\ (1, 1, 0) & \mapsto (1, 0, 1)\\ (1, 1, 1) & \mapsto (1, 1, 1). \end{align*}Sea \(X\) el conjunto de valores de salida para una función de conmutación en \(n\) variables. Entonces \(|X|=2^n\text{.}\) Podemos enumerar estos valores como sigue:
\begin{align*} (0, \ldots, 0, 1) & \mapsto 0\\ (0, \ldots, 1, 0) & \mapsto 1\\ (0, \ldots, 1, 1) & \mapsto 2\\ & \vdots \\ (1, \ldots, 1, 1) & \mapsto 2^n-1. \end{align*}Ahora consideremos un circuito con cuatro variables de entrada y una sola salida. Supongamos que podemos permutar los cables de cualquier circuito de acuerdo al siguiente grupo de permutaciones:
\begin{gather*} (a) \quad (ac) \quad (bd) \quad (adcb)\\ (abcd) \quad (ab)(cd) \quad (ad)(bc) \quad (ac)(bd). \end{gather*}Las permutaciones de las cuatro variables de entrada posible inducen las permutaciones de los valores de salida en la Tabla 14.27.
Lugo, existen
\begin{equation*} \frac{1}{8} (2^{16} + 2 \cdot 2^{12} + 2 \cdot 2^6 + 3 \cdot 2^{10}) = 9616 \end{equation*}funciones de conmutación posibles de cuatro variables bajo este grupo de permutaciones. Este número será incluso menor si consideramos el grupo completo de simetrías en cuatro símbolos.
| Permutación | Número | |
| en el grupo | Permutación de función de conmutación | de Ciclos |
| \((a)\) | \((0)\) | 16 |
| \((a c)\) | \((2,8)(3,9)(6,12)(7,13)\) | 12 |
| \((b d)\) | \((1,4)(3,6)(9,12)(11,14)\) | 12 |
| \((a d c b)\) | \((1,2,4,8)(3,6.12,9)(5,10)(7,14,13,11)\) | 6 |
| \((a b c d)\) | \((1,8,4,2)(3,9,12,6)(5,10)(7,11,13,14)\) | 6 |
| \((a b)(c d)\) | \((1,2)(4,8)(5,10)(6,9)(7,11)(13,14)\) | 10 |
| \((a d)(b c)\) | \((1,8)(2,4)(3,12)(5,10)(7,14)(11,13)\) | 10 |
| \((a c)(b d)\) | \((1,4)(2,8)(3,12)(6,9)(7,13)(11,14)\) | 10 |
SubsecciónNota Histórica
¶William Burnside nació en Londres en 1852. Estudió en la Universidad de Cambridge desde 1871 hasta 1875 y ganó el Smith's Prize en su último año. Después de graduarse dió clases en Cambridge. Se convirtió en miebro de la Royal Society en 1893. Burnside escribió aproximadamente 150 artículos en matemáticas aplicadas, geometría diferencial y probabilidades, pero sus contribuciones más famosas fueron en teoría de grupos. Varias de las conjeturas de Burnside han estimulado la investigación hasta hoy. Una conjetura fue que todo grupo de orden impar es soluble; es decir, para un grupo \(G\) de orden impar, existe una sucesión de subgrupos
\begin{equation*} G = H_n \supset H_{n-1} \supset \cdots \supset H_1 \supset H_0 = \{ e \} \end{equation*}tales que \(H_i\) es normal en \(H_{i+1}\) y \(H_{i+1} / H_i\) es abeliano. Esta conjetura fue finalmente demostrada por W. Feit y J. Thompson en 1963. El libro The Theory of Groups of Finite Order de Burnside, publicado en 1897, fue uno de los primeros libros en dar un tratamiento moderno a los grupos en lugar de verlos solo como grupos de permutaciones. La segunda edición, publicada en 1911, es todavía un clásico.