viernes, 21 de diciembre de 2018

(419) - Teorema de Futurama o de Ken Keeler

En el día de hoy traemos una entrega algo más ligera. Un teorema matemático conocido informalmente como Teorema de Futurama.

En 2010, en el episodio 98 de la serie Futurama, «El prisionero de Benda» (The prisoner of Benda - temporada 6, episodio 10) el profesor Hubert y Amy se intercambian los cuerpos con una máquina, pero a la hora de volver a sus cuerpos originales, la máquina no es capaz de hacerlo, es decir, si A intercambió su cuerpo con B con la máquina, la máquina no podrá intercambiar de vuelta directamente de B a A. Al final el profesor Hubert consigue resolver el problema creando y demostrando un teorema que recibe el nombre de Teorema de Futurama.

El Teorema en sí lo enunció y demostró Ken Keeler, guionista de Futurama y doctor en matemáticas aplicadas por la Universidad de Harvard.


Esta situación es muy similar a una escena de 1999 del episodio «Vacaciones» (Holiday - temporada 2, episodio 18) de la serie de ciencia ficción Spacegate SG-1. Este tipo de situaciones ya habían aparecido en series de dibujos en 1996.


El teorema en sí dice: Sea A un conjunto finito y sean x, y objetos distintos que no pertenezcan a A. Cualquier permutación sobre A se puede reducir a la permutación identidad al usar una serie de diferentes trasposiciones A∪{x,y}, cada una de las cuales incluye al menos un elemento de {x,y}.

Dejamos aquí dos enlaces a vídeos donde explican el teorema con cierta profundidad:


AutorĐɑvɪẟ Ƒernández-De la Cruʒ.

miércoles, 28 de noviembre de 2018

(409) - Nicolás Bourbaki y el Bourbakismo

¿Qué tienen en común Tintín, unos rusos disparando a británicos a caballo y un hito de las matemáticas? (No es el inicio de ningún chiste aunque parezca que sea uno graciosísimo).

En el día de hoy traemos la historia, biografía e hitos del gran matemático poldavo nacionalizado francés, Nicolás Bourbaki, con un poco de trasfondo.

Nicolás Bourbaki (Никола́ Бурбаки́–Nikolá Burbakí en ruso, Нікаля Бурбакі–Nìkalja Burbakì en bielorruso, Ніколя Бурбакі–Nìkolya Burbakì en ucraniano, Никола́ Бурбаки́–Nikolá Bourbakí en búlgaro, Nicolas Bourbaki en francés, polaco y en checo) ha sido uno de los matemáticos más influyentes y prolíficos de la matemática de los siglos XX y XXI.
Bandera del I.Ruso circa la Guerra de Crimea

La familia Bourbaki es originaria de Poldavia, una región eslava e histórica de Europa del Este, en Rutenia y cercana a la ciudad de Poltava (Ucrania), con la cual es probable que comparta etimología.



C.Bourbaki (Pau1816–Bayona1897)
La primera mención en la historia de la que se tiene constancia de la familia Bourbaki viene de la Guerra de Crimea (1853 – 1856) en la que Piamonte-Cerdeña y los Imperios Británico, Francés y Otomano se enfrentaron al Imperio Ruso. En esta campaña cabe destacar la acción de un francés, el general Charles Denis Sauter Bourbaki, conocido por sus históricas acciones militares e intervenciones bélicas en la Conquista de Argelia, en la Guerra de Crimea, en la Guerra italiana de 1859 y en la Guerra franco–prusiana. El general Bourbaki sirvió al mando de Napoleón III, siguiendo el ejemplo de su padre, un griego nacionalizado francés, el coronel Constantin Denis Bourbaki (nacido Διονύσιος Βούρβαχης–Dionýsios Voúrvachis, Cefalonia 1787 – Kamatero 1827), que luchó en la Guerra de Independecia de Grecia y sirvió al mando de Napoleón I, gracias a los contactos de su padre, el cretense Κωνσταντῖνος-Σοτιριος Βούρβαχης–Konstantinos-Sotirios Voúrvachis.

Estandarte imperial ruso durante la guerra
 Tras la Guerra de Crimea no se sabe bien por qué una familia poldava tomó el apellido Bourbaki, ya fuese el apellido que se le asignó a un huérfano, como gesto de admiración al tan conocido general o como testigo de un posible hijo bastardo, la familia Bourbaki ya estaba establecida en Poldavia. 

Los primeros años del siglo XX fueron bastante convulsos para Europa del Este con distintos conflictos bélicos: I Guerra de los Balcanes (1912 – 1913), II Guerra de los Balcanes (1913), I Guerra Mundial (1914 – 1918), Revolución de Febrero y Revolución de Noviembre (Revolución rusa de 1917), Guerra bolchevique-ucraniana (1917 – 1921) y Guerra polaco-soviética (1919 – 1921). Tras tanta guerra y tanta inestabilidad en 1929, el Comité de Defensa de los poldavos envió una carta a los diputados de su tan amiga Francia para llevar su caso a la Liga de Naciones (la ONU de su época) y traer de vuelta la estabilidad.

La relaciones poldavo-francófonas fueron tales que Hergé, el autor del cómic Tintín, incluyó al cónsul de Poldavia en el libro «el Loto Azul». (Un enlace a la serie de televisión de Tintín en Youtube para ver esta escena y el episodio para los interesados, minutos:33-34)

The Blue Lotus

The Blue Lotus
Tras la II Guerra Mundial (1939–1945) toda la Europa del Este cayó directa o indirectamente bajo influencia y control soviéticos. Sin embargo la familia Bourbaki consiguió emigrar a tiempo a Francia donde el genio de Nicolás Bourbaki empezó a gestarse. Más concretamente se instalaron en Besse (más tarde conocida como Besse-en-Chandesse y después como Besse-et-Saint-Anastaise).


Weil (París 1906 – Princeton 1998)
 Una de las grandes mentes matemáticas que modelaron al joven Bourbaki fue el parisino André Weil, hermano de la filósofa Simone Weil. A. Weil fue miembro de la Academia de Ciencias de Francia (Académie des sciences), de la Royal Society, de la Academia Nacional de Ciencias de Estados Unidos (National Academy of Sciences) y de la Academia de Ciencias de Baviera (Bayerische Akademie der Wissenschafte). Entrar en cualquiera de ellas ya es difícil, pero a todas ya es signo de un verdadero genio. No obstante, ninguna de estas era de la que más orgulloso se sentía, pues tal y como aparece en su biografía oficial, el honor que resaltaba sobre el resto era ser miembro de la Academia de Ciencias y de Letras de Poldavia, gracias al trabajo conjunto y amistad de su alumno Nicolás Bourbaki.

Bourbaki conseguió desde adolescente organizar seminarios de matemáticas en París en los que se exponían los últimos hitos de las matemáticas y cómo iba avanzando. Estos seminarios, se han estado realizando desde 1948, por lo que este año ha sido el LXX aniversario del I Séminaire Nicolas Bourbaki (I Seminario Nicolás Burbaki.)

Una vez que hubo acabado la carrera de matemáticas, Bourbaki se volvió a su Poldavia natal, aún bajo influencia comunista en medio de la Guerra Fría, para ser profesor de universidad. Este cambio de aires trastocó hasta tal punto a Bourbaki que se propuso homogeneizar y unificar las diferentes ramas de las matemáticas que estaban saliendo a mediados del siglo XX. Al cabo de unos años, el aún joven Bourbaki se volvió de vuelta a Francia. Tras este suceso, su mentor A. Weil lo describió desde los años 60 como «ancien professeur à l'Université royale de Besse-en-Poldavie» (un exprofesor de la Universidad Real de Besse en Poldavia), cuando todos los libros de matemáticas empezaron a escribir siguiendo sus exigencias y rigurosidad.

Tras su regreso, Bourbaki trajo un espíritu de «partigiano matemático» y entre sus lemas resaltaban «Todos deben interesarse en todo», con la idea de redactar textos nuevos para sus clases universitarias, y «À bas Euclide» (Abajo Euclides/Muera Euclides), que no lo consiguió ya que en vez de unificar y formalizar, la geometría básica y computacional se separaron más del tronco principal que son las matemáticas bourbakistas.

Hasta el día de hoy Bourbaki ha conseguido hasta cinco medallas Fields con la considerable recompensa en matemáticas. Todas ellas se obtuvieron en colaboración: con Laurent Schwartz en 1950, con Jean-Pierre Serre en 1954, con Alexandre Grothendieck en 1966, con Alain Connes en 1982 y con Jean-Christophe Yoccoz en 1994.

Hilbert (1862 - 1943)
Bourbaki siempre ha trabajado con matemáticos jóvenes de mentes frescas, pues todos sus miembros opinaban que a partir de los 50 años las personas eran reacias a ver los problemas desde otra perspectiva. La Asociación de colaboradores de Nicolás Bourbaki (Association des collaborateurs de Nicolas Bourbaki) tiene sus oficinas en la Escuela Normal Superior de París (École Normale Supérieur) desde donde ha estado trabajando durante años el Grupo Bourbaki.

Topologie générale
Este conjunto de matemáticos ha intentado desde su fundación en el siglo XX basar, unificar y formalizar todas las matemáticas en la teoría de conjuntos. Este movimiento se conoce como bourbakisme (bourbakismo) y se puede trazar sus orígenes al Congreso Internacional de Matemáticos de 1900 en el que el prusiano David Hilbert la convocó para resolver los famosos 23 Problemas de Hilbert.
Élémentes de Mathématique

Él mismo ha redactado los volúmenes de «Théorie des ensembles (Teoría de conjuntos)», «Algèbre (Álgebra)»,​ «Topologie générale (Topología general)», «Fonctions d'une variable réelle (Funciones de una variable real)», «Espaces vectoriels topologiques (Espacios vectoriales topológicos)», «Intégration (Integración)»,​ «Álgebra conmutativa», «Variedades diferenciables y analíticas», «Grupos y álgebras de Lie» y «Teorías espectrales», cuyas notas (por las que Nicolás Bourbaki era conocido) se publicaron en 2006 bajo el título «Elementos de Historia de la matemática».

Théorie des ensembles


Su impacto puede verse desde los programas educativos de matemáticas de secundaria y bachillerato, que se dan con mucha más teoría de conjuntos que antes de publicarse sus obras en especial en países como Irlanda o Escocia, hasta en el rigorismo y formalismo matemáticos apreciándose claramente las diferencias entre un texto anterior y posterior a la llegada de Nicolás Bourbaki a las matemáticas. 





Autor: Đɑvɪẟ Ƒernández-De la Cruʒ.

miércoles, 14 de noviembre de 2018

(401) - Dilema del Barquero en Lógica

En el día de hoy traemos un problema muy conocido de lógica, que tiene, como todo en matemáticas, diez mil una maneras de complicarse.

El problema ha aparecido en series tan conocidas como los Simpson, pero con condiciones más laxas y humorísticas.

El enunciado del problema reza así: Un barquero tiene una pequeña barca y quiere llevar consigo a un lobo, una oveja y una caja de lechugas. Sin embargo la barca solo permite un máximo de dos ocupantes: un remero y un acompañante así que si deja el lobo y la oveja solos, el lobo se como la oveja y si deja la oveja y la caja de lechugas solas, la oveja se come las lechugas. ¿Cómo ha de actuar para «salvar» a los tres?

Razonemos como si fuésemos medio tontos (si es que no lo somos del todo):
  • Si se lleva el lobo, deja la oveja con las lechugas y adiós lechugas. Game over.
  • Si se lleva las lechugas, deja el lobo con la oveja  y adiós oveja. Game over.
  • Si se lleva la oveja, deja el lobo con las lechugas y dado que los lobos no comen lechugas, el lobo no interactuará con las lechugas  y el juego sigue.


El barquero llega a la otra orilla, deja la oveja, y se vuelve a la orilla de partida. Ahora tiene dos opciones: o bien se lleva al lobo, o bien se lleva las lechugas. Veamos qué pasa con cada una de ellas:


El lobo primero:
  • Si se lleva el lobo, deja las lechugas solas y el juego sigue. 
Sin embargo cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva la oveja o bien la deja (llevarse el lobo sería volver al paso anterior).
  • Si se va solo, deja el lobo con la oveja  y adiós oveja. Game over.
  • Si se lleva la oveja, deja el lobo solo en una orilla y las lechugas en la orilla a la que se dirige y el juego sigue.
No obstante cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva las lechugas o bien las deja (llevarse la oveja sería volver al paso anterior).
  • Si se va solo, deja la oveja con las lechugas y adiós lechugas. Game over.
  • Si se lleva las lechugas, deja la oveja sola en una orilla y el lobo, en la orilla a la que se dirigy el juego sigue.


Cuando llega a la otra orilla deja las lechugas y como ya se ha explicado, el lobo no se come las lechugas y puede volver a la orilla de partida despreocupado para recoger la oveja a moverla por tercera vez de orilla. Una vez que llegan con la oveja, tanto el lobo, como la oveja y la caja de lechugas ya están en la otra orilla y el juego ya ha acabado.

Las lechugas primero:
  • Si se lleva las lechugas, deja el lobo solo y el juego sigue. 
Sin embargo cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva la oveja o bien la deja (llevarse las lechugas sería volver al paso anterior).
  • Si se va solo, deja la oveja con las lechugas y adiós oveja. Game over.
  • Si se lleva la oveja, deja las lechugas solas en una orilla y el lobo, en la orilla a la que se dirige y el juego sigue.
No obstante cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva el lobo o bien lo deja (llevarse la oveja sería volver al paso anterior).
  • Si se va solo, deja el lobo con la oveja  y adiós oveja. Game over.
  • Si se lleva el lobo, deja la oveja sola en una orilla y las lechugas, en la orilla a la que se dirigy el juego sigue.


Cuando llega a la otra orilla deja sl lobo y como ya se ha explicado, el lobo no se come las lechugas y puede volver a la orilla de partida despreocupado para recoger la oveja a moverla por tercera vez de orilla. Una vez que llegan con la oveja, tanto el lobo, como la oveja y la caja de lechugas ya están en la otra orilla y el juego ya ha acabado.
(Como se puede apreciar el problema tiene cierto punto de repetitividad).
Visualicemos esto un poco: creemos un sistema de coordenadas de tres ejes (x, y, z) en el que cada variable solo puede tomar dos valores, o bien 0 (que indica que está en la orilla de  partida), o bien 1 (que indica que está en la orilla de  llegada). La variable x indica la posición del lobo, la variable y indica la posición de las ovejas, y la variable z indica la posición de la caja de lechugas.
Siguiendo el método anteriormente descrito, el conjunto de puntos que sigue el barquero en orden es:
  • si se toma el lobo primero en la disyunción anterior (0,0,0) → (0,1,0) → (1,1,0) → (1,0,0) → (1,0,1) → (1,1,1).
  • si se toma la caja primero en la disyunción anterior (0,0,0) → (0,1,0) → (0,1,1) → (0,0,1) → (1,0,1) → (1,1,1).
Nótese que los dos únicos puntos que no son los mismos son los dos intermedios.
Los vectores que definen cada pareja de puntos consecutivos describen un cubo de arista 1, como se puede apreciar en la figura.

Los vectores y puntos-posiciones en el cubo

Los vectores y puntos-posiciones en el espacio

Propongamos ahora una pequeña modificación del problema. Supongamos que aparte del remero, en la barca pueden ir otros dos ocupantes y se quiere llegar a la misma solución que antes, pero mucho más deprisa, por lo que el método anteriormente descrito para un solo ocupante no es el más efectivo ni el óptimo.
Antes se ha jugado con el concepto que el lobo no «reacciona» con las lechugas así que vamos a seguir jugando con esa idea, pues todas las demás se han desechado por el camino.


  • Si se lleva el lobo y las lechugas, deja la oveja sola. Tras esto, pone a esperar el lobo y las lechugas en la otra orilla, se va por la oveja y cuando vuelve el juego ya ha acabado.
También hay una subvariante de este método empezando al revés es decir:
  • Si se lleva la oveja, deja el lobo y las lechugas solos. Tras esto, pone a esperar la oveja en la otra orilla, se va por el lobo y por las lechugas y cuando vuelve el juego ya ha acabado.
De un modo similar al sistema de coordenadas descrito con anterioridad si se hace los mismo, se obtiene:
  • si se toma la pareja primero (0,0,0) → (1,0,1) → (1,1,1).
  • si se toma la oveja primero  (0,0,0) → (0,1,0) → (1,1,1).
Nótese que el único punto que no es el mismo es el intermedio y que comparten cada ruta un vector con el apartado anterior.

Una cosa curiosa que ocurre aquí es que hay vectores que describen la diagonal de caras cuadradas, cosa que antes no pasaba.

Los vectores y puntos-posiciones en el cubo

Los vectores y puntos-posiciones en el espacio
Propongamos ahora otra pequeña modificación al problema. Supongamos que aparte del remero, en la barca pueden ir otros tres ocupantes y se quiere llegar a la misma solución que antes, pero mucho más deprisa, por lo cualquier método anteriormente descrito no sería el más efectivo ni el óptimo.
Antes se ha jugado con el concepto que los tres transportados no interactúan entre sí o intentan comerse en la presencia del barquero.


  • Si se lleva el lobo, la oveja y las lechugas, se lleva todo y cuando llega a la otra orilla el juego ya ha acabado.
De un modo similar al sistema de coordenadas descrito con anterioridad si se hace los mismo, se obtiene (0,0,0)  → (1,1,1).
Una cosa curiosa que ocurre aquí es que el único vector que hay describe la diagonal espacial del cubo, cosa que antes no pasaba.
Los vectores y puntos-posiciones en el cubo
Los vectores y puntos-posiciones en el espacio
Teniendo una configuración de este estilo, de tres elementos [lobo, oveja, lechugas] que cada superior erradica a su estrictamente inferior sin supervisión del barquero. Además, no es posible resolverlo si la barca no admite ningún ocupante sin contar el remero y se resolvería de la misma manera [la última descrita] si tiene un número igual o mayor que tres puestos para ocupantes sin contar el remero.

El problema propuesto en los Simpson tiene la misma temática. He aquí un enlace al Dilema del barquero por los Simpson.

Próximamente vendrá otro problema de lógica y barcas, algo más difícil y mucho menos conocido.



AutorĐɑvɪẟ Ƒernández-De la Cruʒ.

domingo, 4 de noviembre de 2018

(397) ESTRUCTURA Y ALEATORIEDAD DE LOS NÚMEROS PRIMOS.

ESTRUCTURA Y ALEATORIEDAD DE LOS NÚMEROS PRIMOS.

Los números primos han sido uno de los temas más estudiados de las Matemáticas.
Uno de los aspectos sobre los que se busca una respuesta es la distribución de
los números primos, es decir, si siguen algún tipo de patrón o por el contrario,
tienen una distribución aleatoria.

Encontrar números primos es una tarea compleja que se intentará explicar en este artículo.

Teorema de Euclides. El número de números primos es infinito. En particular, sea k N, entonces, existe un número primo con al menos k cifras.

Sin embargo no se conoce una manera rápida y precisa de localizar números primos (en este caso, la palabra rápido hace referencia a que sea computable en un tiempo polinómico en k), en particular, no se conoce una fórmula que nos genere grandes números y nos garantice que estos sean primos.
Dado un número de k-dígitos se puede comprobar si es primo de manera <<rápida>> mediante métodos probabilísticos (Miller- Rabin 1980) o mediante métodos determinísticos (Agarwal-Kayal-Saxena 2002).

Teorema de los números primos (Hadamard, de Vallee Poussin 1896).
El número de primos menores que n ∈ N es donde o(1) tiende hacia 0 cuando . En particular, la probabilidad de que dado un número de k dígitos sea primo es de .

Por lo tanto, uno puede encontrar rápidamente un número primo de k dígitos con una probabilidad relativamente alta seleccionando de manera aleatoria. Resumiendo, no conocemos una manera determinista de encontrar números primos sin embargo, tenemos maneras <<rápidas>> de encontrar números primos de manera aleatoria.
Además, conocemos una conjetura en teoría de la complejidad P = BPP que dice (coloquialmente hablando) que cualquier problema que puede ser resuelto de manera rápida haciendo uso de métodos probabilísticos, también puede ser resuelto de manera determinista (esta conjetura está relacionada con la conjetura P vs NP).

Hemos visto que encontrar un número primo grande es complicado. Haciendo
uso del teorema fundamental de la aritmética se puede establecer la fórmula del producto de Euler


para cada s > 1. La fórmula (1) conecta el comportamiento de los números primos con el comportamiento de la función zeta de Riemann

por lo que se tiene


Uno puede deducir información de los números primos haciendo uso de la función zeta de Riemann (y en particular, sus ceros). Por ejemplo, de la divergencia de la serie armónica podemos ver que  tiende a 0 cuando se aproxima a 1 (por la derecha, al menos). De esto y de (2) se puede recuperar
el teorema de Euclides y de hecho obtenemos el resultado más fuerte de Euler de que la suma de los recíprocos de los números primos diverge también. Uno puede hacer uso de técnicas de análisis complejo combinado con el hecho (no trivial) de que  nunca es cero para s C cuando  para establecer el teorema de los números primos.
La hipótesis de Riemann afirma que no tiene ceros cuando . Esto nos lleva a una versión mucho más fuerte del teorema de los números primos, de manera resumida dice que el número de primos menores que un entero n > 1 viene dado de manera más precisa por la fórmula



Una manera acertada de pensar en el conjunto de los números primos es que es un conjunto pseudoaleatorio. El teorema de los números primos afirma que cogiendo de manera aleatoria un entero n grande hay una probabilidad de 1/log(n) de que sea primo. Uno puede modelizar el conjunto de los números primos reemplazándolos con un conjunto aleatorio de números enteros, donde el entero n > 1 es seleccionado con independencia de la probabilidad 1/log(n); esto es llamado el modelo aleatorio de Cramer.

Considerando la conjetura débil de Goldbach, todo número entero impar mayor que 5 se puede expresar como suma de tres números primos. Si consideramos los números primos grandes cuyo último dígito es 1, las conjeturas de Goldbach pueden fallar para grandes números enteros cuyo ultimo dígito sea distinto de 3. Entonces se ve que las conjeturas pueden fallar si hay una conspiración <<lo suficientemente extraña>>. Sin embargo, uno puede formalizar fuera de una conspiración particular haciendo uso del teorema de los números primos para progresiones aritméticas, que nos dice que (además de otras cosas) hay muchos primos cuyo ultimo dígito es distinto de 1. Además, usando el método del círculo de Hardy- Littlewood, uno puede mostrar que todas las conspiraciones que posiblemente podrían hundir la conjetura de Goldbach (para enteros grandes, al menos) son en general de este tipo: un <<sesgo inesperado>> para que los primos prefieran un resto módulo 10 (o módulo en otra base, que no necesite ser un entero), sobre otro. Vinogradov eliminó cada una de estas posibles conspiraciones, y estableció lo siguiente.

Teorema de Vinogradov. Cada entero impar suficientemente grande es la suma de tres primos.

Este método ha sido usado por muchos autores. En concreto, matemáticos expertos en teoría de números como Terence Tao y Ben Green en sus artículos usan técnicas relacionadas con este método para probar que los números primos contienen arbitrariamente largas progresiones aritméticas, y en el trabajo posterior de Terence Tao, Ben Green y Tamar Ziegler para contar una amplia gama de otros patrones aditivos. (En términos generales, las técnicas conocidas pueden contar patrones aditivos que involucran dos parámetros independientes, como las progresiones aritméticas a, a + r, ..., a + (k - 1) r  de una longitud fija k).

Desafortunadamente aún queda mucho por hacer en este área que espero que tras este artículo haya resultado de su interés.

Autor: Carlos Saravia.