Inicio » 2024 (Página 3)

Archivos anuales: 2024

Mi email: framonde@mat.upv.es

diciembre 2024
L M X J V S D
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Comentarios recientes

No hay comentarios que mostrar.
Videos interesantes

Introducción a la Teoría de Grupos: https://www.youtube.com/watch?v=RnqwFpyqJFw

Concepto de grupo: https://www.youtube.com/watch?v=g7L_r6zw4-c

Concepto de subgrupo y sistema generador: https://www.youtube.com/watch?v=3ydwbo2OrnA

Clases módulo un subgrupo (o clases laterales): https://www.youtube.com/watch?v=cIVUs2z0-lg

Sobre la clasificación de los grupos simples finitos: https://youtu.be/bKi1i_49yrw?si=ZJVOGfVU-LyEvNAW

Problema propuesto

Problema B-4: “Consideremos los siguientes subgrupos de $S_9$ :
$$
H:=\langle(1,2)(3,4)\rangle \quad \text { у } \quad N:=\langle(5,6,7,8,9)\rangle .
$$
(a) Demuestra que $H N$ es un subgrupo de $S_9$.
(b) Demuestra que $G=H N$ es producto directo interno de $H$ y $N$.”

Solución

De «Introduction to Mathematical Philosophy»(Bertrand Russell)

«Mathematics is a study which, when we start from its most familiar portions, may be pursued in either of two opposite directions. The more familiar direction is constructive, towards gradually increasing complexity: from integers to fractions, real numbers, complex numbers; from addition and multiplication to differentiation and integration, and on to higher mathematics. The other direction, which is less familiar, proceeds, by analysing, to greater and greater abstractness and logical simplicity; instead of asking what can be defined and deduced from what is assumed to begin with, we ask instead what more general ideas and principles can be found, in terms of which what was our starting-point can be defined or deduced. It is the fact of pursuing this opposite direction that characterises mathematical philosophy as opposed to ordinary mathematics. But it should be understood that the distinction is one, not in the subject matter, but in the state of mind of the investigator. Early Greek geometers, passing from the empirical rules of Egyptian land-surveying to the general propositions by which those rules were found to be justifiable, and thence to Euclid’s axioms and postulates, were engaged in mathematical philosophy, according to the above definition; but when once the axioms and postulates had been reached, their deductive employment, as we find it in Euclid, belonged to mathematics in the ordinary sense. The distinction between mathematics and mathematical philosophy is one which depends upon the interest inspiring the research, and upon the stage which the research has reached; not upon the propositions with which the research is concerned.»

Clase del 17 de octubre (2 horas)

Se resolvieron los siguientes problemas del tema 1: 3, 4 (de dos maneras), 5, 7, 8, 9 y 11.

Os propongo a continuación el siguiente problema:

PROBLEMA B-3: «Sea $G$ un grupo y sean $A$ y $B$ dos subgrupos de $G$ tales que $G=AB$, siendo $A$ abeliano y normal en $G$. Demuestra que $A\cap B$ es un subgrupo normal de $G$».

Solución

Clase del 14 de octubre (1 hora)

Durante la clase consideramos la terna $(\mathbb{Z}_n,+,\cdot)$ y recordamos las propiedades de las dos operaciones: suma y producto de clases de congruencia módulo $n$:

  • $(\mathbb{Z}_n,+)$ es un grupo abeliano.
  • La operación $\cdot$ es asociativa y distributiva respecto de la suma.

Estas dos propiedades se resumen diciendo que $(\mathbb{Z}_n,+,\cdot)$ tiene estructura de anillo. Además, la operación $\cdot$ es conmutativa (se trata, por tanto, de un anillo conmutativo) y tiene elemento neutro, la clase del 1 (es un anillo unitario). En resumen: $(\mathbb{Z}_n,+,\cdot)$ tiene estructura de anillo conmutativo y unitario.

Los elementos de $\mathbb{Z}_n$ que tienen inverso multiplicativo se denominan unidades. El conjunto de las unidades de $\mathbb{Z}_n$ se denota por $U_n$, y tiene estructura de grupo con la operación producto. Se dice que $(U_n,\cdot)$ es el grupo de las unidades de $\mathbb{Z}_n$.

La Proposición 1.9, que probamos, muestra cuáles son exactamente los elementos de $U_n$: las clases de los enteros que son coprimos con $n$.

En la parte final de la clase resolvimos los problemas 2 y 6 de la hoja de problemas del tema 1.

Clase del 10 de octubre (2 horas)

En la clase de hoy hemos definido los grupos simples como aquellos grupos $G$ cuyos únicos subgrupos normales son $1$ y $G$ (no tienen subgrupos normales intermedios).

Hemos demostrado también que si $G\neq 1$ es un grupo finito entonces se satisface la siguiente equivalencia: $G$ es simple y abeliano $\Leftrightarrow$ $G$ es cíclico de orden primo.

Ya vimos, con un ejemplo, que el producto de dos subgrupos de un grupo no es necesariamente un subgrupo. Hoy hemos probado una caracterización de cuándo se satisface esta propiedad. Más concretamente: si $H$ y $K$ son dos subgrupos de un grupo $G$ entonces $HK$ es un subgrupo si y sólo si $HK=KH$. También hemos visto una condición suficiente: si uno de los subgrupos, $H$ o $K$, es normal en $G$, entonces $HK$ es subgrupo.

Cabe señalar que el producto de dos subgrupos de un grupo abeliano siempre es un subgrupo (debido a la caracterización anterior).

Hemos demostrado que, si $a\mathbb{Z}$ y $b\mathbb{Z}$ son dos subgrupos de $(\mathbb{Z},+)$, entonces el subgrupo “suma” $a\mathbb{Z}+b\mathbb{Z}$ concide con el subgrupo $d\mathbb{Z}$, donde $d$ es el máximo común divisor de $a$ y $b$. (Nótese que, al usarse notación aditiva, el “producto” de subgrupos se reemplaza por la “suma”). Este resultado es equivalente a la Identidad de Bézout, que ya visteis el curso pasado en Matemática Discreta.

Hemos definido la noción de producto directo interno: Un grupo $G$ es producto directo interno de dos subgrupos suyos $H$ y $K$ si:

  • $hk=kh$ para todo $h\in H$ y para todo $k\in K$,
  • $H\cap K=1$
  • $G=HK$

Hemos demostrado otra caracterización de producto directo interno que se obtiene sustituyendo, en la definición, la primera de las propiedades por la siguiente:

  • $H$ y $K$ son subgrupos normales de $G$.

Finalmente hemos definido el concepto de producto directo externo: Dados dos grupos $G_1$ y $G_2$, se denomina producto directo externo de ambos grupos al producto cartesiano $G_1\times G_2$ dotado de la siguiente operación: $(x_1,x_2)(y_1,y_2)=(x_1y_1,x_2y_2)$ (es decir, el producto “componente a componente”). Esta operación dota a $G_1\times G_2$ de estructura de grupo, siendo $(1_{G_1},1_{G_2})$ el neutro y $(x^{-1},y^{-1})$ el inverso de cualquier elemento $(x,y)\in G_1\times G_2$.

Cabe señalar que, si $G$ un grupo $G$ es producto directo interno de dos subgrupos suyos $H$ y $K$ entonces $G=HK$ es isomorfo al producto directo externo $H\times K$ (precisaremos la noción de “isomorfismo” en el tema siguiente). Por ello, muchas veces se abusa de notación y se escribe $G=H\times K$ para dar a entender que $G$ es producto directo interno de $H$ y $K$. Incluso se dice, simplemente, que es “producto directo”, omitiendo el calificativo “interno”.

COMENTARIO RELEVANTE: Aunque no lo demostraremos en clase (ni irá para examen la demostración), hay un resultado muy relevante (enunciado y probado en la última sección el Tema 1) que debéis saber: el grupo alternado de grado $n$, $A_n$, es simple para todo $n\geq 5$. (La definición de grupo alternado se ve en la Práctica 2). Este hecho resulta fundamental para probar que una ecuación polinómica general de grado $n \geq 5$ no es resoluble por radicales. Este resultado lo veréis en Estructuras Algebraicas II, y es el colofón de una preciosa teoría denominada Teoría de Galois (en honor a Evariste Galois, matemático francés que dio con la caracterización precisa de cuándo una ecuación polinómica es resoluble por radicales, constituyendo el germen de la Teoría de Grupos). ¿Qué significa que “la ecuación polinómica general de grado mayor o igual que 5 no es resoluble por radicales”? Lo explico someramente a continuación: existen fórmulas que permiten resolver una ecuación polinómica de primer grado cualquiera, una ecuación de segundo grado $ax^2+bx+c=0$, y también las ecuaciones polinómicas de grado 3 y de grado 4. Todas estas fórmulas usan las siguientes operaciones: suma, resta, producto, división y toma de radicales. Sin embargo, no se conoce ninguna fórmula similar para resolver ecuaciones polinómicas de grado 5 o superior. Lo que demostró Abel (y luego precisó todavía más Galois, encontrando la razón de fondo) es que no pueden existir dichas fórmulas. Os sugiero hacer una búsqueda en internet sobre la vida y obra de Evariste Galois. También podéis ver algo aquí:

https://framonde.webs.upv.es/Galois.html

Como avance os diré que falleció en un duelo a la edad de 20 años.

Clase del 7 de octubre (1 hora)

Hemos terminado de resolver el Ejercicio 1.23. Un apartado especialmente importante de este ejercicio, y que debemos tener siempre presente pues resulta muy útil, es el siguiente: todo subgrupo de índice 2 es normal. En particular, como se vio (o se verá) en la práctica 2, el grupo alternado de grado $n$ (formado por las permutaciones pares) es un subgrupo normal de $S_n$, pues tiene índice 2.

Como ejemplo, se vio que el grupo especial lineal $SL(n,K)$ es un subgrupo normal del grupo general lineal $GL(n,K)$, y que todos los subgrupos del grupo cuaternio de orden 8, $Q_8$, son normales (a pesar de no ser $Q_8$ un grupo abeliano).

Finalmente se definió el concepto de centro de un grupo $G$, denotado por $Z(G)$, como el conjunto de todos los elementos de $G$ que conmutan con todos los elementos de $G$, y vimos que se trata de un subgrupo normal de $G$. Probamos que el centro de $S_n$ es trivial si $n\geq 3$ y vimos que el centro de $Q_8$ es $\{1,-1\}$.

El último ejercicio de la sección muestra que, para todo $r\geq 3$, el centro del grupo diédrico de orden $2r$, $D_{2r}$, es trivial si $r$ es impar y es el subgrupo cíclico de orden 2 $\{1,\rho^{r/2}\}$ si $r$ es par (donde $\rho$ es la rotación de ángulo $2\pi/r$).

Clase del 3 de octubre (2 horas)

En la clase de ayer probamos algunos resultados que se obtienen aplicando el Teorema de Lagrange:

  • El orden de todo elemento de un grupo finito divide al orden del grupo.
  • Si un grupo tiene orden primo entonces es cíclico.
  • Un grupo finito no tiene subgrupos propios no triviales si y sólo si tiene orden primo.

Definimos el concepto de subgrupo normal de un grupo $G$ como aquél en el que las clases a izquierda y a derecha de cualquier elemento coinciden. Es decir, $n\leq G$ es normal en $G$ si $xN=Nx$ para todo $x\in G$. En particular, si $G$ es abeliano, todos sus subgrupos son normales. Observamos, como ejemplo, que el subgrupo $\{1,-1\}$ de $Q_8$ es un subgrupo normal.

Demostramos que, cuando $N$ es un subgrupo normal de un grupo $G$, el conjunto de sus clases a izquierda (o a derecha, porque son las mismas), denotado por $G/N$ en este caso, tiene estructura de grupo con la operación “producto de clases”. En particular, vimos que $(xN)(yN)=(xy)N$ (con lo cual el producto de clases es una clase y, por tanto, constituye una operación binaria interna en $G/N$), el elemento neutro es $1N=N$ (la clase del $1$) y el elemento inverso de una clase $xN$ es $x^{-1}N$, es decir, $(xN)^{-1}=x^{-1}N$. El grupo $G/N$ (con esta operación) se denomina grupo cociente de $G$ con $N$. Calculamos los elementos del grupo cociente $Q_8/H$, donde $H=\{1,-1\}$, construimos su tabla de Cayley, y vimos que $Q_8/H$ es isomorfo al 4-grupo de Klein comparando ambas tablas de Cayley. También vimos que el grupo cociente $\mathbb{Z}/n\mathbb{Z}$ (para todo entero $n$) coincide con el grupo de clases de congruencia módulo $n$ (con las operación suma).

Demostramos que, dados un subgrupo $H$ de un grupo $G$ y un elemento $g\in G$, el conjugado de $H$ con $g$, $H^g$, es un subgrupo de $G$. Además, si $H$ es finito, $H^g$ tiene el mismo orden que $H$.

Probamos un par de caracterizaciones de los subgrupos normales: un subgrupo $N$ de un grupo $G$ es normal si y sólo si $N^g=N$ para todo $g\in G$ si y sólo si $N^g\subseteq N$ para todo $g\in G$.

Finalmente, vimos en un ejercicio que la intersección de subgrupos normales es un subgrupo normal.

Clase del 30 de septiembre (1 hora)

En la clase de hoy hemos probado el Teorema de Lagrange, que afirma que, dado un grupo finito $G$ y un subgrupo $H$ de $G$, el orden de $G$ es igual al producto del orden de $H$ por su índice. Como consecuencia directa de este resultado se infiere que el orden de cualquier subgrupo de un grupo finito $G$ tiene que ser un divisor de $|G|$. También, dado un elemento $g\in G$, como $o(g)$ coincide con el orden del subgrupo generado por $g$, $\langle g \rangle$, se tiene como consecuencia que $o(g)$ es un divisor de $|G|$.

Hemos demostrado, como corolario del Teorema de Lagrange, la propiedad de “transitividad de índices” y también la fórmula que permite calcular el “cardinal” de $HK$, cuando $H$ y $K$ son sobgrupos de un grupo finito $G$.

Hay que tener en cuenta aquí que $HK$ no es necesariamente un subgrupo de $G$ (hemos visto un ejemplo de ello). Más adelante veremos un resultado que caracterizará aquellas situaciones en las que el producto de dos subgrupos es un subgrupo.

En la siguiente clase probaremos otras consecuencias del Teorema de Lagrange y, posteriormente, nos plantearemos la siguiente cuestión: dado un grupo $G$ y un subgrupo $H$ de $G$, ¿cuándo el conjunto de sus clases a derecha, $\{Hx\mid x\in G\}$, tiene estructura de grupo? Veremos que esto ocurre cuando $H$ pertenece a una clase muy importante de subgrupos: los subgrupos normales.

Clase del 26 de septiembre (2 horas)

Hemos comenzado la clase recordando un importante teorema que nos indica cuál es la estructura de los grupos cíclicos finitos. En particular, un grupo cíclico finito tiene un único subgrupo de orden $k$ para cada divisor $k$ del orden del grupo (y estos son exactamente sus subgrupos). Hemos visto, como ejemplo, todos los subgrupos de $\mathbb{Z}_6$; aquí lo “engorroso” es pasar de notación multiplicativa a notación aditiva, pero resulta muy fácil si se va con un poco de cuidado.

Hemos comenzado la sección sobre el Teorema de Lagrange. Hemos comenzado con un lema técnico, de demostración muy sencilla, pero que nos va a facilitar bastante la escritura de las demostraciones.

Después hemos definido el concepto de clases a derecha y a izquierda de un elemento módulo un subgrupo $H$ de un grupo $G$. Hemos visto que el conjunto de las clases a derecha forman una partición del grupo (análogamente con las clases a izquierda). También hemos visto que el cardinal del conjunto de las clases a izquierda coincide con el de las clases a derecha estableciendo una biyección entre ambos conjuntos. Esta biyección asigna, a cada clase a izquierda $xH$, la clase a derecha $Hx^{-1}$.

Si el conjunto de clases a izquierda (o a derecha) de un grupo $G$ módulo un subgrupo $H$ es finito, hemos definido el “índice de $H$ en $G$”, o “índice según $G$ de $H$”, como el número de tales clases. Se denota por $|G:H|$.

El objetivo del próximo lunes será enunciar y probar el Teorema de Lagrange, así como algunas consecuencias importantes. El Teorema de Lagrange afirma que, si $G$ es un grupo finito y $H$ es un subgrupo suyo entonces $$|G|=|H||G:H|.$$ En particular, el orden de todo subgrupo de $G$ debe ser necesariamente un divisor del orden de $G$. Por ejemplo, un grupo de orden $15$ puede tener subgrupos de ordenes $1$, $3$, $5$ y $15$, pero no puede tener subgrupos de orden $4$.

Con el objetivo de clarificar el concepto de clase a izquierda y a derecha módulo un subgrupo, vamos a incluir aquí un ejemplo (no mencionado en clase). Supongamos que $G$ es el grupo cuaternio de orden 8, $Q_8$, es decir, $$G=\{1, -1, i, -i-, j, -j, k, -k\}.$$

Vamos a considerar el subgrupo de $G$ generado por $i$, es decir, el subgrupo cíclico $$H:=\langle i \rangle.$$ Recordad que $i^2=-1$, $i^3=-i$ y $i^4=1$. Por tanto, $i$ es un elemento de orden 4. Así pues, por el teorema de estructura de los grupos cíclicos, se tiene que $$H=\{1,i,-1,-i\}.$$

Se trata, por tanto, de un subgrupo de orden 4. Aunque no lo hemos probado todavía, vamos a aplicar aquí el Teorema de Lagrange para conocer su índice en $G$. Por este teorema: $$|G|=|H||G:H|,$$

es decir: $8=4\cdot |G:H|$. Así pues, el índice de $H$ en $G$, $|G:H|$, es igual a 2. Esto significa que existen 2 clases a izquierda de $G$ módulo $H$ (y dos clases a derecha también). Veamos cuáles son las clases a izquierda. Sabemos que forman una PARTICIÓN de $G$. Una de las clases es, por supuesto, la clase del neutro (del $1$), que es $1H=H$. Por tanto, ya tenemos una clase: $$H=\{1, i, -1, -i\}.$$

Escojamos ahora un elemento que no esté en esta clase, como por ejemplo $j$, y calculemos la clase de $j$: $$jH=\{jh\mid h\in H\}=\{j\cdot 1, j \cdot i, j\cdot (-1), j\cdot (-i)\}=\{j, -k, -j,k\}.$$

Como, tal y como hemos visto, solo hay dos clases a izquierda (pues el índice era 2), ya las tenemos todas. Son las siguientes: $$H=\{1, i, -1, -i\}\;\;\mbox{ y }\;\;\; jH=\{j, -k, -j,k\}.$$

Obsérvese que, tal y como hemos mencionado en clase, se trata de clases de equivalencia. Las clases de $1, i, -1$ y $-i$ coinciden y son iguales a $H$, es decir, $$1H=iH=(-1)H=(-i)H=H.$$ También, las clases de $j$, $-k$, $-j$ y $k$ coinciden, es decir, $$jH=(-k)H=(-j)H=kH.$$

Obsérvese que el conjunto de las clases a izquierda de $G=Q_8$ módulo $H$, $\{H, jH\}$, constituye una partición de $G$.

Veamos ahora otro ejemplo. Sigamos con el mismo grupo $G=Q_8$ y consideremos el subgrupo $N$ generado por $-1$, es decir, $N:=\langle -1\rangle=\{1, -1\}$ (observad que $-1$ tiene orden 2 y, por tanto, $N$ posee solo dos elementos: $(-1)^0=1$ y $(-1)^1=-1$). Vamos a calcular, igual que antes, el índice de $N$ en $G$, usando el Teorema de Lagrange: $$|G|=|N||G:N|.$$

Por tanto: $8=2\cdot |G:N|$. Luego $|G:N|=4$. Así pues, existen 4 clases a izquierda de $G$ módulo $N$. Veamos cuáles son:

  • Tenemos la clase del $1$, es decir, $1N=N=\{1, -1\}$.
  • Elegimos un elemento que no esté en la clase anterior; por ejemplo, $i$. Calculemos la clase de $i$: $$iN=\{in\mid n\in N\}=\{i\cdot 1, i\cdot (-1)\}=\{i, -i\}.$$
  • Elegimos un elemento de $G$ que no esté en ninguna de las clases anteriores; por ejemplo, $j$. Calculemos la clase de $j$: $$jN=\{jn\mid n\in N\}=\{j, -j\}.$$
  • Elegimos un elemento de $G$ que no esté en ninguna de las clases anteriores; por ejemplo, $k$. Calculemos la clase de $k$: $$kN=\{kn\mid n\in N\}=\{k, -k\}.$$

Ya tenemos las 4 clases. Observamos que el conjunto de estas cuatro clases a izquierda forman una partición de $G$.

Si reproducís los cálculos anteriores para clases a derecha, observaréis que la clase a izquierda y a derecha módulo $H$ de cualquier elemento $x$ de $G$ coinciden (y lo mismo pasa con las clases módulo $N$), a pesar de que el grupo $G$ no es abeliano. ¡Ojo! Esto no pasa siempre. Cuando esto pasa (es decir, cuando las clases a izquierda y a derecha módulo un subgrupo coinciden) se dice que ese subgrupo es normal (y $Q_8$ tiene la peculiaridad de que todos sus subgrupos son normales, a pesar de no ser un grupo abeliano). Este concepto de subgrupo normal es muy importante y lo estudiaremos en la sección siguiente.

Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 6)

¿Dónde radica la seguridad del criptosistema RSA?

Conocer la aplicación de descifrado $D$ equivale a conocer la clave privada $d$, que sólo posee Bob. Y esta clave secreta $d$ no puede conocerse a partir de $(n, e)$ sin el conocimiento de $r=\varphi(n)=(p-1)(p-1)$ (recuérdese que $d$ es un representante del inverso de la clase de $e$ módulo $r=(p-1)(q-1))$. Puede razonarse que conocer $r$ es igual de difícil que saber factorizar $n$ como producto de los primos $p$ y $q$. Si estos primos se han elegido suficientemente grandes (y satisfaciendo ciertas condiciones buenas), $n$ tendrá un valor tan grande que será imposible factorizarlo con los recursos computacionales existentes en este momento. Aquí radica la seguridad del criptosistema RSA. Si una supuesta espía Eve interceptara el mensaje que Alice le envía a Bob, le resultaría imposible averiguar la clave secreta $d$ (y, por tanto, descifrar el mensaje) aún sabiendo la clave pública $(n,e)$.