Para mi asignatura de Complejidad Computacional he hecho un trabajo más o menos bibliográfico, más o menos divulgativo, sobre tests de primalidad. La estrella, digamos, del trabajo, es la demostración desmenuzada, en términos algo más elementales que los del paper original, del test AKS. Aparecen también, sin tanto detalle, los tests probabilistas de Fermat, Miller-Rabin y Solovay-Strassen. Aquí lo dejo.
jueves, 9 de enero de 2014
miércoles, 25 de septiembre de 2013
El Test de Miller-Rabin y su dependencia de la HGR
Estoy aprendiendo a programar en Python y para practicar estoy haciendo los problemas de Project Euler. El décimo problema pide encontrar la suma de todos los números primos menores que 2 millones. Para ello, una opción posible es ir comprobando cada número natural menor que 2 millones. Si el número es primo, se añade a la suma, y si es compuesto, no se añade. Para saber si un número es primo o no, lo que hay que hacer es un test de primalidad.
lunes, 1 de julio de 2013
El fibrado de Hopf
He decidido escribir esta entrada en un pdf. Se puede descargar en el siguiente enlace:
martes, 11 de junio de 2013
Dualidad álgebra - geometría
Para seguir esta entrada conviene saber lo que es un anillo, lo que es un ideal de un anillo y lo que es un cuerpo algebraicamente cerrado. También haber leído la entrada anterior, Una traducción álgebra - geometría.
Como esta tarde no tengo nada mejor que hacer, voy a extenderme en el tema de la última entrada, explicando por qué la equivalencia entre variedad irreducible e ideal primo no es una serendipia, que diría Iker, sino que hay una verdad más profunda oculta detrás de esto: la categoría de las variedades algebraicas afines sobre un cuerpo $\mathbb{K}$ algebraicamente cerrado y la categoría de $\mathbb{K}$-álgebras finitamente generadas y reducidas son categorías duales. Veamos qué significa esto.
domingo, 2 de junio de 2013
Una traducción álgebra - geometría
Para seguir esta entrada conviene saber lo que es un anillo y lo que es un ideal de un anillo.
Las variedades algebraicas afines de $\mathbb{K}^n$ (donde $\mathbb{K}$ es un cuerpo, que a efectos de lo que quiero contar puede pensarse que es $\mathbb{R}$ o $\mathbb{C}$) son los conjuntos de ceros de polinomios de $\mathbb{K}\left[X_1, X_2, ..., X_n\right]$. Por ejemplo, la circunferencia unidad es una variedad algebraica afín de $\mathbb{K}^2$ porque es el conjunto de puntos que satisfacen $X^2 + Y^2 = 1$, es decir, el conjunto de ceros del polinomio $f(X,Y) = X^2 + Y^2 -1$. También todas las rectas afínes, de ecuación $Y = mX + n$, son conjuntos algebraicos afines de $\mathbb{K}^2$, porque son conjuntos de ceros de polinomios de la forma $f(X,Y) = mX - Y + n$. Pero también son conjuntos algebraicos afines algunas curvas un poco más raras, como la parábola de Neil, que es el conjunto de ceros del polinomio $f(X,Y) = Y^2 - X^3$, o el nudo de Newton, que es el conjunto de ceros del polinomio $f(X,Y) = Y^2-X^3-X^2$.
Las variedades algebraicas afines de $\mathbb{K}^n$ (donde $\mathbb{K}$ es un cuerpo, que a efectos de lo que quiero contar puede pensarse que es $\mathbb{R}$ o $\mathbb{C}$) son los conjuntos de ceros de polinomios de $\mathbb{K}\left[X_1, X_2, ..., X_n\right]$. Por ejemplo, la circunferencia unidad es una variedad algebraica afín de $\mathbb{K}^2$ porque es el conjunto de puntos que satisfacen $X^2 + Y^2 = 1$, es decir, el conjunto de ceros del polinomio $f(X,Y) = X^2 + Y^2 -1$. También todas las rectas afínes, de ecuación $Y = mX + n$, son conjuntos algebraicos afines de $\mathbb{K}^2$, porque son conjuntos de ceros de polinomios de la forma $f(X,Y) = mX - Y + n$. Pero también son conjuntos algebraicos afines algunas curvas un poco más raras, como la parábola de Neil, que es el conjunto de ceros del polinomio $f(X,Y) = Y^2 - X^3$, o el nudo de Newton, que es el conjunto de ceros del polinomio $f(X,Y) = Y^2-X^3-X^2$.
La notación estándar que suele utilizarse para no tener que estar diciendo todo el rato "conjunto de ceros del polinomio (o polinomios) tal" es la siguiente: dado un conjunto de polinomios $f_1, ..., f_r$, denotamos su lugar de ceros comunes por $V(f_1, ..., f_r)$ (donde $V$ es por variedad). Así, la circunferencia sería $V(X^2+Y^2-1)$, o la parábola (usual) sería $V(Y-X^2)$.
Si ahora consideramos el polinomio $f(X,Y) = (X-Y)(X^2+Y^2-1)$, ¿qué pinta tiene $V(f)$? Un punto $(x,y)$ de $\mathbb{K}^2$ satisface la ecuación $f(x,y) = 0$ si $x-y = 0$, o si $y^2+x^2-1 = 0$ (o ambas condiciones, claro). Por tanto en este caso $V(f)$ es la unión de la recta $Y = X$ con la circunferencia $X^2+Y^2 = 1$. En efecto, si metemos en Wolfram Alpha "(x-y)*(x^2+y^2-1) = 0", el dibujo que nos sale es este:
La diferencia entre este dibujo y los anteriores es evidente: de alguna manera, entendemos que esta variedad es algo así como la unión de dos variedades más pequeñas: una circunferencia y una recta. En cierto sentido, es una variedad algebraica "reducible". Pero, ¿qué entendemos por variedad reducible? Nos gustaría dar una definición satisfactoria de variedad reducible, y eso es lo que vamos a intentar hacer aquí, comparando dos enfoques distintos: el enfoque geométrico y el enfoque algebraico.
domingo, 17 de marzo de 2013
Interpretación geométrica de la torsión
Dada una variedad riemanniana $(M,g)$, sabemos que la conexión de Levi-Civita $\nabla$ es simétrica, es decir, se verifica que para toda curva diferenciable $\alpha:I \rightarrow M$ y cada par de campos de vectores $X,Y$ a lo largo de $\alpha$,
$$\nabla_XY - \nabla_YX = [X,Y]$$
Ahora bien, supongamos que tenemos otra conexión $D$ sobre $M$ que no verifica esta condición. Definimos el tensor de torsión como
$$T(X,Y) = D_XY - D_YX - [X,Y]$$
de modo que podemos expresar la condición anterior como que la conexión de Levi-Civita tiene torsión cero, pero la conexión $D$ tiene torsión no nula. Se puede probar que para cualquier conexión afín $D$ sobre $M$, existe un tensor $A$ de tipo $(2,1)$ tal que
$$D_XY = \nabla_XY + A(X,Y)$$
Entonces, podemos calcular la torsión de $D$:
$$T(X,Y) = D_XY - D_YX - [X,Y] = $$
$$= \nabla_XY + A(X,Y) - \nabla_XY - A(X,Y) - [X,Y] = A(X,Y) - A(Y,X)$$
Luego $D$ tiene torsión $0$ (es simétrica) si, y sólo si, $A(X,Y) - A(Y,X) = 0$, si y sólo si, por definición, $A$ es un tensor simétrico. Por otro lado, dada una geodésica $\gamma:I \rightarrow M$ para la conexión de Levi-Civita, se verifica por definición que $\nabla_{\gamma'}\gamma' = 0$, luego
$$D_{\gamma'}\gamma' = \nabla_{\gamma'}\gamma' + A(\gamma',\gamma') = A(\gamma',\gamma')$$
y entonces $\gamma$ es una geodésica para $D$ si, y sólo si, $A(\gamma',\gamma') = 0$, si y sólo si $A$ es un tensor antisimétrico. Con lo anterior, se deduce que $D$ define las mismas geodésicas que la conexión de Levi-Civita y tiene torsión cero si, y sólo si, $A$ es simétrico y antisimétrico, lo que ocurre sólo si $A$ es idénticamente nulo, en cuyo caso $D$ es precisamente la conexión de Levi-Civita.
Ahora bien, dada una conexión $D$ que define las mismas geodésicas que la conexión de Levi-Civita, ¿cómo se interpreta geométricamente que tenga torsión no nula? Intentaremos dar una idea con un pequeño ejemplo.
$$\nabla_XY - \nabla_YX = [X,Y]$$
Ahora bien, supongamos que tenemos otra conexión $D$ sobre $M$ que no verifica esta condición. Definimos el tensor de torsión como
$$T(X,Y) = D_XY - D_YX - [X,Y]$$
de modo que podemos expresar la condición anterior como que la conexión de Levi-Civita tiene torsión cero, pero la conexión $D$ tiene torsión no nula. Se puede probar que para cualquier conexión afín $D$ sobre $M$, existe un tensor $A$ de tipo $(2,1)$ tal que
$$D_XY = \nabla_XY + A(X,Y)$$
Entonces, podemos calcular la torsión de $D$:
$$T(X,Y) = D_XY - D_YX - [X,Y] = $$
$$= \nabla_XY + A(X,Y) - \nabla_XY - A(X,Y) - [X,Y] = A(X,Y) - A(Y,X)$$
Luego $D$ tiene torsión $0$ (es simétrica) si, y sólo si, $A(X,Y) - A(Y,X) = 0$, si y sólo si, por definición, $A$ es un tensor simétrico. Por otro lado, dada una geodésica $\gamma:I \rightarrow M$ para la conexión de Levi-Civita, se verifica por definición que $\nabla_{\gamma'}\gamma' = 0$, luego
$$D_{\gamma'}\gamma' = \nabla_{\gamma'}\gamma' + A(\gamma',\gamma') = A(\gamma',\gamma')$$
y entonces $\gamma$ es una geodésica para $D$ si, y sólo si, $A(\gamma',\gamma') = 0$, si y sólo si $A$ es un tensor antisimétrico. Con lo anterior, se deduce que $D$ define las mismas geodésicas que la conexión de Levi-Civita y tiene torsión cero si, y sólo si, $A$ es simétrico y antisimétrico, lo que ocurre sólo si $A$ es idénticamente nulo, en cuyo caso $D$ es precisamente la conexión de Levi-Civita.
Ahora bien, dada una conexión $D$ que define las mismas geodésicas que la conexión de Levi-Civita, ¿cómo se interpreta geométricamente que tenga torsión no nula? Intentaremos dar una idea con un pequeño ejemplo.
jueves, 29 de noviembre de 2012
Grupos de Lie (II): La aplicación exponencial
En esta entrada quiero presentar la aplicación exponencial de un grupo de Lie, uno de esos objetos que aparecen de vez en cuando en matemáticas y que, mágicamente, conectan otros objetos que intuíamos relacionados, pero sin terminar de ver bien el bosque. Se trata de una aplicación que se puede definir en cualquier álgebra de Lie asociada a un grupo de Lie, y que permite reconstruir completamente un grupo de Lie (en el caso conexo) a partir de su álgebra de Lie. En el caso del grupo de Lie $\mathbb{R}^* = \mathbb{R}\setminus \{0\}$, la aplicación exponencial será la exponencial real $e^t$ que todos conocemos, y en el caso de las matrices, será la exponencial matricial $e^A$ que conocerá todo aquel que sepa resolver sistemas de ecuaciones diferenciales lineales de primer orden.
Suscribirse a:
Entradas (Atom)



