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

Walter Ferrer wrferrer en gmail.com
Dom Abr 26 17:36:18 UYT 2015


>
> Seminario de álgebra y temas afines
>>
>>>>>> Centro de Matemática
>>> Salón de Seminarios del Piso 14
>>> hora 14:30/16
>>>
>>
>> ​                                    Expositor: Gonzalo Tornaría​
>> 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/20150426/99023ce2/attachment.html>


Más información sobre la lista de distribución Todos