Saltar al contenido principal
LibreTexts Español

14.3: Teorema del conteo de Burnside

  • Page ID
    111359
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Supongamos que deseamos colorear los vértices de un cuadrado con dos colores diferentes, digamos blanco y negro. Podríamos sospechar que habría\(2^4=16\) diferentes colorantes. Sin embargo, algunos de estos colorantes son equivalentes. Si coloreamos el primer vértice negro y los vértices restantes blancos, es lo mismo que colorear el segundo vértice negro y los restantes blancos ya que podríamos obtener la segunda coloración simplemente girando el cuadrado\(90^\circ\) (Figura\(14.17\)).

    clipboard_eb73378a8b6d01164636fac20817a4f61.png

    \(Figure \text { } 14.17.\)Colorantes equivalentes de cuadrado.

    El teorema de conteo de Burnside ofrece un método para calcular el número de formas distinguibles en las que se puede hacer algo. Además de sus aplicaciones geométricas, el teorema tiene interesantes aplicaciones a áreas de teoría de conmutación y química. La prueba del teorema de conteo de Burnside depende del siguiente lema.

    Lema\(14.18\)

    \(X\)Sea un\(G\) -set y supongamos que\(x \sim y\text{.}\) Entonces\(G_x\) es isomórfico a\(G_y\text{.}\) En particular,\(|G_x| = |G_y|\text{.}\)

    Prueba

    Vamos a\(G\) actuar\(X\) por\((g,x) \mapsto g \cdot x\text{.}\) Dado que\(x \sim y\text{,}\) existe\(g \in G\) tal que\(g \cdot x=y\text{.}\) Let\(a \in G_x\text{.}\) Since

    \[ gag^{-1} \cdot y = ga \cdot g^{-1}y = ga \cdot x = g \cdot x = y\text{,} \nonumber \]

    podemos definir un mapa\(\phi: G_x \rightarrow G_y\) por\(\phi(a) = gag^{-1}\text{.}\) El mapa\(\phi\) es un homomorfismo ya que

    \[ \phi(ab) = gabg^{-1} = gag^{-1} gbg^{-1} = \phi(a) \phi(b)\text{.} \nonumber \]

    Supongamos que\(\phi(a) = \phi(b)\text{.}\) Entonces\(gag^{-1}= gbg^{-1}\) o\(a=b\text{;}\) por lo tanto, el mapa es inyectivo. Para mostrar que\(\phi\) está en, dejar\(b\) estar en\(G_y\text{;}\) entonces\(g^{-1}bg\) está en\(G_x\) desde

    \[ g^{-1}bg \cdot x = g^{-1}b \cdot gx = g^{-1}b \cdot y = g^{-1} \cdot y = x; \nonumber \]

    y\(\phi(g^{-1}bg ) = b\text{.}\)

    Teorema\(14.19\). Burnside

    Dejar\(G\) ser un grupo finito actuando sobre un conjunto\(X\) y dejar\(k\) denotar el número de órbitas de\(X\text{.}\) Entonces

    \[ k = \frac{1}{|G|} \sum_{g \in G} |X_g|\text{.} \nonumber \]
    Prueba

    Miramos todos los puntos fijos\(x\) de todos los elementos en\(g \in G\text{;}\) eso es, miramos todos y todos\(g\)\(x\) tales que\(gx =x\text{.}\) Si se ve en términos de conjuntos de puntos fijos, el número de todos los\(g\) fijadores\(x\) es

    \[ \sum_{g \in G} |X_g|\text{.} \nonumber \]

    Sin embargo, si se ve en términos de los subgrupos estabilizadores, este número es

    \[ \sum_{x \in X} |G_x|; \nonumber \]

    por lo tanto,\(\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x|\text{.}\) Por Lema\(14.18\),

    \[ \sum_{y \in {\mathcal O}_x} |G_y| = | {\mathcal O}_x| \cdot |G_x|\text{.} \nonumber \]

    Por Teorema\(14.11\) y Teorema de Lagrange, esta expresión es igual a\(|G|\text{.}\) Sumar sobre todas las\(k\) distintas órbitas, concluimos que

    \[ \sum_{g \in G} |X_g| = \sum_{x \in X} |G_x| = k \cdot |G|\text{.} \nonumber \]

    Ejemplo\(14.20\)

    Supongamos que ese\(G\) es el grupo de permutación\(X = \{1, 2, 3, 4, 5 \}\)\(G= \{(1), (1 \, 3), (1 \, 3)(2 \, 5), (2 \, 5) \}\text{.}\)

    Solución

    Las órbitas de\(X\) son\(\{1, 3\}\text{,}\)\(\{2, 5\}\text{,}\) y\(\{4\}\text{.}\) Los conjuntos de puntos fijos son

    \ begin {alinear*} X_ {(1)} & = X\\ X_ {(1\, 3)} & =\ {2, 4, 5\}\ X_ {(1\, 3) (2\, 5)} & =\ {4\}\ X_ {(2\, 5)} & =\ {1, 3, 4\}\ texto {.} \ end {alinear*}

    El teorema de Burnside dice que

    \[ k = \frac{1}{|G|} \sum_{g \in G} |X_g| = \frac{1}{4}(5 + 3 + 1 + 3) = 3\text{.} \nonumber \]

    Un Ejemplo Geométrico

    Antes de aplicar el teorema de Burnside a los problemas de la teoría del cambio, examinemos el número de formas en que los vértices de un cuadrado pueden ser coloreados en blanco o negro. Observe que en ocasiones podemos obtener colorantes equivalentes simplemente aplicando un movimiento rígido al cuadrado. Por ejemplo, como hemos señalado, si coloreamos uno de los vértices negro y los tres restantes blancos, no importa qué vértice fue coloreado de negro ya que una rotación dará una coloración equivalente.

    El grupo de simetría de un cuadrado,\(D_4\text{,}\) viene dado por las siguientes permutaciones:

    \ begin {alinear*} & (1) & (1\, 3) & (2\, 4) & (1\, 4) & (1\, 4\, 3\, 2)\ & (1\, 2\, 3\, 4) & (1\, 3) (3\, 4) & (1\, 4) (2\, 3) & (1\, 3) (2\, 3), 4)\ end {alinear*}

    El grupo\(G\) actúa sobre el conjunto de vértices\(\{ 1, 2, 3, 4\}\) de la manera habitual. Podemos describir los diferentes colorantes por mapeos desde\(X\)\(Y = \{ B, W \}\) donde\(B\) y\(W\) representar los colores blanco y negro, respectivamente. Cada mapa\(f : X \rightarrow Y\) describe una manera de colorear las esquinas del cuadrado. Cada\(\sigma \in D_4\) induce una permutación\(\widetilde{ \sigma }\) de los posibles colorantes dados por por\(\widetilde{\sigma}(f) = f \circ \sigma\)\(f : X \rightarrow Y\text{.}\) ejemplo, supongamos que\(f\) se define por

    \ begin {alinear*} f (1) & = B\\ f (2) & = W\\ f (3) & = W\\ f (4) & = W\ final {alinear*}

    y\(\sigma = (1 2)(3 4)\text{.}\) Luego\(\widetilde{\sigma}(f) = f \circ \sigma\) envía vértice\(2\) a\(B\) y los vértices restantes a\(W\text{.}\) El conjunto de todos los tales\(\widetilde{\sigma}\) es un grupo de permutación\(\widetilde{G}\) en el conjunto de posibles colorantes. Dejar\(\widetilde{X}\) denotar el conjunto de todos los colorantes posibles; es decir,\(\widetilde{X}\) es el conjunto de todos los mapas posibles desde\(X\) hasta\(Y\text{.}\) Ahora debemos calcular el número de clases de\(\widetilde{G}\) -equivalencia.

    1. \(\widetilde{X}_{(1)} = \widetilde{X}\)ya que la identidad fija todos los colores posibles. \(|\widetilde{X}| = 2^4 =~16\text{.}\)
    2. \(\widetilde{X}_{(1 \, 2 \, 3 \, 4)}\)consiste en todos los\(f \in \widetilde{X}\) tales que no\(f\) se modifica por la permutación\((1 \, 2 \, 3 \, 4)\text{.}\) En este caso\(f(1) = f(2) = f(3) = f(4)\text{,}\) para que todos los valores de\(f\) deben ser iguales; es decir, ya sea\(f(x)= B\) o\(f(x)= W\) por cada vértice\(x\) del cuadrado. Entonces\(|\widetilde{X}_{(1 \, 2 \, 3 \, 4)}| = 2\text{.}\)
    3. \(|\widetilde{X}_{(1 \, 4 \, 3 \, 2)}| = 2\text{.}\)
    4. Para\(\widetilde{X}_{(1 \, 3)(2 \, 4)}\text{,}\)\(f(1) = f(3)\) y por\(f(2) = f(4)\text{.}\) lo tanto,\(|\widetilde{X}_{(1 \, 3)(2 \, 4)}| = 2^2 = 4\text{.}\)
    5. \(|\widetilde{X}_{(1 \, 2)(3 \, 4)}| = 4\text{.}\)
    6. \(|\widetilde{X}_{(1 \, 4)(2 \, 3)}| = 4\text{.}\)
    7. Para\(\widetilde{X}_{(1 \, 3 )}\text{,}\)\(f(1) = f(3)\) y las otras esquinas pueden ser de cualquier color; por lo tanto,\(|\widetilde{X}_{(1 \, 3)}| = 2^3 = 8\text{.}\)
    8. \(|\widetilde{X}_{(2 \, 4)}| = 8\text{.}\)

    Por el teorema de Burnside, podemos concluir que hay exactamente

    \[ \frac{1}{8} ( 2^4 + 2^1 + 2^2 + 2^1 + 2^2 + 2^2 +2^3 + 2^3) = 6 \nonumber \]

    formas de colorear los vértices del cuadrado.

    Proposición\(14.21\)

    Dejar\(G\) ser un grupo de permutación de\(X\) y\(\widetilde{X}\) el conjunto de funciones de\(X\) a\(Y\text{.}\) Entonces existe un grupo de permutación\(\widetilde{G}\) que actúa sobre\(\widetilde{X}\text{,}\) dónde \(\widetilde{\sigma} \in \widetilde{G}\)se define por\(\widetilde{\sigma}(f) = f \circ \sigma\) for\(\sigma \in G\) y\(f \in \widetilde{X}\text{.}\) Además, si\(n\) es el número de ciclos en la descomposición del ciclo de\(\sigma\text{,}\) entonces\(|\widetilde{X}_{\sigma}| = |Y|^n\text{.}\)

    Prueba

    Dejar\(\sigma \in G\) y\(f \in \widetilde{X}\text{.}\) Claramente, también\(f \circ \sigma\) está en\(\widetilde{X}\text{.}\) Supongamos que\(g\) es otra función de\(X\) a\(Y\) tal que\(\widetilde{\sigma}(f) = \widetilde{\sigma}(g)\text{.}\) Entonces para cada\(x \in X\text{,}\)

    \[ f( \sigma(x )) = \widetilde{\sigma}(f)(x) = \widetilde{\sigma}(g)(x) = g( \sigma(x ))\text{.} \nonumber \]

    Ya que\(\sigma\) es una permutación de\(X\text{,}\) cada elemento\(x'\) en\(X\) es la imagen de algunos\(x\) en\(X\) debajo de\(\sigma\text{;}\) ahí,\(f\) y de\(g\) acuerdo en todos los elementos de\(X\text{.}\) Por lo tanto,\(f=g\) y\(\widetilde{\sigma}\) es inyectivo. El mapa\(\sigma \mapsto \widetilde{\sigma}\) está encendido, ya que los dos conjuntos son del mismo tamaño.

    Supongamos que\(\sigma\) es una permutación de\(X\) con descomposición del ciclo\(\sigma = \sigma_1 \sigma_2 \cdots \sigma_n\text{.}\) Cualquiera\(f\) en\({\widetilde{X}}_{\sigma}\) debe tener el mismo valor en cada ciclo de\(\sigma\text{.}\) Dado que hay\(n\) ciclos y\(|Y|\) posibles valores para cada ciclo,\(|{\widetilde{X}}_{\sigma}| = |Y|^n\text{.}\)

    Ejemplo\(14.22\)

    Supongamos que\(Y = \{ A, B, C \}\text{.}\) si\(g\) es la permutación de\(X\) dada por\(X = \{1, 2, \ldots, 7\}\)\((1 \, 3)(2 \, 4 \, 5) = (1 \, 3)(2 \, 4 \, 5)(6)(7)\text{,}\)

    Solución

    entonces\(n = 4\text{.}\) Cualquiera\(f \in \widetilde{X}_g\) debe tener el mismo valor en cada ciclo en\(g\text{.}\) Hay\(|Y|=3\) tales opciones para cualquier valor, entonces\(|\widetilde{X}_g| = 3^4 = 81\text{.}\)

    Ejemplo\(14.23\)

    Supongamos que deseamos colorear los vértices de un cuadrado usando cuatro colores diferentes. Por Proposición\(14.21\), podemos decidir de inmediato que hay

    Solución

    \[ \frac{1}{8} (4^4 + 4^1 + 4^2 + 4^1 + 4^2 + 4^ 2 + 4^3 + 4^3) = 55 \nonumber \]

    formas posibles.

    Funciones de conmutación

    En la teoría de conmutación nos preocupa el diseño de circuitos electrónicos con entradas y salidas binarias. El más simple de estos circuitos es una función de conmutación que tiene\(n\) entradas y una única salida (Figura\(14.24\)). A menudo se pueden construir circuitos electrónicos grandes combinando módulos más pequeños de este tipo. El problema inherente aquí es que incluso para un circuito simple se puede construir un gran número de diferentes funciones de conmutación. Con solo cuatro entradas y una sola salida, podemos construir 65.536 funciones de conmutación diferentes. Sin embargo, a menudo podemos reemplazar una función de conmutación por otra simplemente permutando los cables de entrada al circuito (Figura\(14.25\)).

    clipboard_e41f7797e4bdb45bf6ca0e5af0de8ee1f.png

    \(Figure \text { } 14.24.\)Una función de conmutación de\(n\) variables

    Definimos una función de conmutación o booleana de\(n\) variables para que sea una función de\({\mathbb Z}_2^n\) a\({\mathbb Z}_2\text{.}\) Dado que cualquier función de conmutación puede tener dos valores posibles para cada\(n\) -tupla binaria y hay\(2^n\) binarios\(n\) - tuplas, funciones\(2^{2^n}\) de conmutación son posibles para\(n\) las variables. En general, permitir permutaciones de las entradas reduce en gran medida el número de diferentes tipos de módulos que se necesitan para construir un circuito grande.

    clipboard_e16cc6e3bba80fc9a54eefe0b22bd3022.png

    \ (Figura\ texto {} 14.25. Una función de conmutación de dos variables

    Las posibles funciones de conmutación con dos variables de entrada\(a\) y\(b\) se enumeran en Tabla\(14.26\). Dos funciones de conmutación\(f\) y\(g\) son equivalentes si se\(g\) pueden obtener a partir\(f\) de 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\) vía la permutación\((a,c,b)\text{.}\) En el caso de funciones de conmutación de dos variables, la permutación\((a,b)\) reduce 16 posibles funciones de conmutación a 12 funciones equivalentes ya que

    \ begin {alinear*} f_2 &\ sim f_4\\ f_3 &\ sim f_5\\ f_ {10} &\ sim f_ {12}\\ f_ {11} &\ sim f_ {13}\ texto {.} \ end {alinear*}

    \(Table \text { } 14.26\).Funciones de conmutación en dos variables

    Insumos 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\)
    Insumos 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\) posibles funciones de conmutación; en el caso de cuatro variables hay\(2^{2^4} =65{,}536\text{.}\) El número de clases de equivalencia es demasiado grande para calcularlo razonablemente directamente. Es necesario emplear el Teorema de Burnside.

    Consideremos una función de conmutación con tres entradas posibles,\(a\text{,}\)\(b\text{,}\) y\(c\text{.}\) como hemos mencionado, 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 la 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\) posibles salidas, no solo tres valores de entrada. Por ejemplo, cada triple binario\((a, b, c)\) tiene asociada una salida específica. La permutación\((acb)\) cambia los resultados de la siguiente manera:

    \ 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) &\ mapsto (1, 1, 1)\ text {.} \ end {alinear*}

    Let\(X\) Ser 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 de la siguiente manera:

    \ 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\ text {.} \ end {alinear*}

    Ahora consideremos un circuito con cuatro variables de entrada y una sola salida. Supongamos que podemos permutar los cables de cualquier circuito de acuerdo con el siguiente grupo de permutación:

    \ begin {reunir*} (a),\ quad (a, c),\ quad (b, d),\ quad (a, d, c, b),\\ (a, b, c, d),\ quad (a, b) (c, d),\ quad (a, d) (b, c),\ quad (a, c) (b, d)\ text {.} \ end {reunir*}

    Las permutaciones de las cuatro posibles variables de entrada inducen las permutaciones de los valores de salida en la Tabla\(14.27\).

    De ahí que haya

    \[ \frac{1}{8} (2^{16} + 2 \cdot 2^{12} + 2 \cdot 2^6 + 3 \cdot 2^{10}) = 9616 \nonumber \]

    posibles funciones de conmutación de cuatro variables bajo este grupo de permutaciones. Este número será aún menor si consideramos el grupo simétrico completo en cuatro letras.

    \(Table \text { } 14.27\). Permutaciones de funciones de conmutación en cuatro variables

    Grupo   Número
    Permutación Permutación de la 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

    Nota Histórica

    William Burnside nació en Londres en 1852. Asistió a la Universidad de Cambridge de 1871 a 1875 y ganó el Smith's Prize en su último año. Después de su graduación dio conferencias en Cambridge. Fue hecho miembro de la Royal Society en 1893. Burnside escribió aproximadamente 150 artículos sobre temas de matemáticas aplicadas, geometría diferencial y probabilidad, pero sus contribuciones más famosas fueron en la teoría de grupos. Varias de las conjeturas de Burnside han estimulado la investigación hasta el día de hoy. Una de esas conjeturas fue que cada grupo de orden impar es solucionable; es decir, para un grupo\(G\) de orden impar, existe una secuencia de subgrupos

    \[ G = H_n \supset H_{n-1} \supset \cdots \supset H_1 \supset H_0 = \{ e \} \nonumber \]

    tal que\(H_i\) es normal en\(H_{i+1}\) y\(H_{i+1} / H_i\) es abeliano. Esta conjetura fue finalmente probada por W. Feit y J. Thompson en 1963. La teoría de los grupos de orden finito de Burnside, publicada en 1897, fue uno de los primeros libros en tratar a los grupos en un contexto moderno en oposición a los grupos de permutación. La segunda edición, publicada en 1911, sigue siendo un clásico.


    This page titled 14.3: Teorema del conteo de Burnside is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Thomas W. Judson (Abstract Algebra: Theory and Applications) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.