Algoritmos para encontrar puntos racionales en una curva elíptica?

Question

Estoy buscando algoritmos sobre cómo encontrar puntos racionales en un curva elíptica $$y^2 = x^3 + a x + b$$ donde $a$ et $b$ son números enteros. Cualquier idea sobre cómo proceder será bienvenida. Por ejemplo, cómo encontrar soluciones en las que los numeradores y denominadores estén acotados, o cómo encontrar soluciones con un algoritmo aleatorio. Cualquier cosa mejor que la fuerza bruta es interesante.

Antecedentes: un estudiante trabajó en el Teorema de Mordell-Weil y lo ilustró con algunos ejemplos sencillos de curvas elípticas. Buscó puntos racionales por fuerza bruta (realmente quiero decir bruto enumerando todas las posibilidades y probándolas). Como continuación del proyecto, ahora está interesada en algoritmos más inteligentes para encontrar puntos racionales. Una búsqueda superficial en Math Reviews no ha encontrado gran cosa.

Answer 1

Hay toda una industria dedicada a ello. El método básico es descenso que es una versión formalizada de las pruebas de descenso infinito de Fermat y Euler. Ayuda si hay puntos racionales de 2 torsión pero no es esencial. Capítulo X del libro de Silverman La aritmética de las elípticas Elípticas se llama "Computing the Mordell-Weil group". Contiene muchas información, pero tal vez no es tan fácil para un principiante debido a su uso pesado de cohomología de grupos.

Answer 2

Hay formas inteligentes de acelerar la enumeración por fuerza bruta. Una de ellas es el programa ratpoints de M. Stoll: http://www.mathe2.uni-bayreuth.de/stoll/programs/index.html

Una forma completamente distinta de generar puntos en curvas elípticas es utilizar puntos de Heegner, pero sólo funciona cuando el rango es uno. Esto es técnicamente más sofisticado, pero creo que también hay implementaciones. Google rinde: http://www.math.mcgill.ca/darmon/programs/programs.html

Answer 3

Una buena referencia para empezar desde el punto de vista algorítmico es el capítulo 3 del libro de Cremona Algoritmos para curvas elípticas modulares . Contiene una buena cantidad de pseudocódigo que explica cómo el paquete C++ mwrank de Cremona calcula puntos racionales en curvas elípticas.

Algunos de los detalles más intrincados, como los segundos descensos, se dejan en manos de los documentos de Cremona aquí . Dada una curva elíptica con coeficientes que no son demasiado grandes, su mejor apuesta para encontrar rápidamente los puntos que está buscando probablemente será utilizar mwrank como se incluye en Salvia .

Como me han explicado en los comentarios. Sage no es la única forma de acceder a mwrank y a los otros programas que componen la librería de curvas elípticas de Cremona (eclib), pero es posiblemente la forma más fácil de conseguirlo, y contiene mucha más funcionalidad de curvas elípticas, como el método E.analytic_rank() que si se ejecuta en una curva elíptica de un conductor de tamaño razonable, devolverá un entero que es proBablemente el rango analítico de la curva.

Answer 4

La mejor solución práctica es encargar el trabajo a otra persona. Puede consultar la curva en Mesas de Cremona si no es demasiado grande. Si es mayor, puede utilizar mwrank un programa C++ independiente. Creo que SAGE y MAGMA también tienen esta funcionalidad, aunque no he podido encontrar la sintaxis en una búsqueda rápida.

Answer 5

En realidad, es engañoso decir "algoritmo". Hay algoritmos probabilísticos, y luego casos difíciles (pruebas de un punto de orden infinito difícil de encontrar). Véase, por ejemplo http://www.jstor.org/pss/2152939 . Considero a Andrew Bremner como uno de los expertos en el lado altamente numérico, y debería añadir su nombre al de John Cremona.