[Todos CMAT] Seminario de álgebra y temas afines--CMAT

[Walter Ferrer]

Seminario de álgebra y temas afines

> ​
> Centro de Matemática
> Salón de Seminarios del Piso 14
> hora 14:30/16
>

​​
Titulo:
​El problema de los números congruentes

y la multiplicación de polinomios

​


Un entero n se dice "congruente" si es el área de un triángulo rectángulo
con
lados racionales.  El problema, enunciado hace más de mil años por el
matemático persa al-Karaji, consiste en determinar cuales números enteros
son
congruentes.  En 1225 Fibonacci mostró que 5 y 7 son congruentes, y
conjeturó
que 1 no es congruente, hecho que fue demostrado por Fermat en 1659.  Para
1915
los números congruentes menores que 100 habían sido determinados pero en
1980
aún había casos menores que 1000 sin resolver.

En 1982 Tunnel descubrió una fórmula simple para determinar si un número
dado
es congruente o no, sujeto a la conjetura de Birch y Swinnerton-Dyer.
Utilizando esta fórmula se han podido determinar todos los números
congruentes
hasta 10^9 (Rubinstein ca. 2005). Sin embargo, los algoritmos utilizados
hasta
entonces empleaban un tiempo asintótico O(N^3/2) para determinar todos los
números congruentes hasta N.

En 2009 en un trabajo con Hart y Watkins, utilizando técnicas de
multiplicación
rápida — transformada de Fourier y métodos multi-modulares — implementamos
un
algoritmo con tiempo casi-lineal en N que fue usado para determinar todos
los
números congruentes hasta 10^12 en 1250 horas de cpu (alrededor de 3 días de
tiempo real). En nuestro método, el problema computacional fundamental es la
multiplicación de polinomios con 10^12 coeficientes. Estos polinomios
exceden
largamente la capacidad de memoria por lo que no pueden usarse las técnicas
usuales de multiplicación rápida que emplean acceso aleatorio a los
factores.

En esta charla haré una breve presentación histórica del problema de los
números congruentes y la fórmula de Tunnel, y una introducción a técnicas de
multiplicación rápida y el problema de calcular fuera de la memoria.
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://www.cmat.edu.uy/pipermail/todos/attachments/20150423/26645aff/attachment.html>