En matemáticas, una secuencia de divisibilidad elíptica (EDS) es una secuencia de números enteros que satisfacen una relación de recursividad no lineal que surge de polinomios de división en curvas elípticas . Los EDS fueron definidos por primera vez, y sus propiedades aritméticas estudiadas, por Morgan Ward [1] en la década de 1940. Atrajeron sólo una atención esporádica hasta alrededor de 2000, cuando los EDS se consideraron una clase de recurrencias no lineales que son más susceptibles de análisis que la mayoría de estas secuencias. Esta manejabilidad se debe principalmente a la estrecha conexión entre EDS y curvas elípticas. Además del interés intrínseco que EDS tiene dentro de la teoría de números, EDS tiene aplicaciones en otras áreas de las matemáticas, incluida la lógica.y criptografía .
Definición
Una secuencia de divisibilidad elíptica (no degenerada) (EDS) es una secuencia de números enteros ( W n ) n ≥ 1 definida recursivamente por cuatro valores iniciales W 1 , W 2 , W 3 , W 4 , con W 1 W 2 W 3 ≠ 0 y con valores posteriores determinados por las fórmulas
Se puede demostrar que si W 1 divide cada uno de W 2 , W 3 , W 4 y si W 2 más divide W 4 , entonces cada término W n en la secuencia es un número entero.
Propiedad de divisibilidad
Un EDS es una secuencia de divisibilidad en el sentido de que
En particular, cada término en una EDS es divisible por W 1 , por lo que las EDS se normalizan con frecuencia para tener W 1 = 1 dividiendo cada término por el término inicial.
Cualesquiera tres enteros b , c , d con d divisible por b conducen a una EDS normalizada en el ajuste
No es obvio, pero se puede probar, que la condición b | d es suficiente para asegurar que cada término de la secuencia sea un número entero.
Recursividad general
Una propiedad fundamental de las secuencias de divisibilidad elíptica es que satisfacen la relación de recursividad general
(Esta fórmula se aplica a menudo con r = 1 y W 1 = 1.)
EDS no singular
El discriminante de una EDS normalizada es la cantidad
Un EDS no es singular si su discriminante es distinto de cero.
Ejemplos de
Un ejemplo simple de una EDS es la secuencia de números naturales 1, 2, 3,…. Otro ejemplo interesante es (secuencia A006709 en el OEIS ) 1, 3, 8, 21, 55, 144, 377, 987,… que consiste en cualquier otro término en la secuencia de Fibonacci , comenzando con el segundo término. Sin embargo, ambas secuencias satisfacen una recurrencia lineal y ambas son EDS singulares. Un ejemplo de EDS no singular es (secuencia A006769 en la OEIS )
Periodicidad de EDS
Se dice que una secuencia ( A n ) n ≥ 1 es periódica si hay un número N ≥ 1 de modo que A n + N = A n para cada n ≥ 1. Si una EDS no degenerada ( W n ) n ≥ 1 es periódica , luego uno de sus términos desaparece. El menor r ≥ 1 con W r = 0 se denomina rango de aparición de la EDS. Un teorema profundo de Mazur [2] implica que si el rango de aparición de una EDS es finito, entonces satisface r ≤ 10 o r = 12.
Curvas elípticas y puntos asociados a EDS
Ward demuestra que asociada a cualquier EDS no singular ( W n ) hay una curva elíptica E / Q y un punto P ε E ( Q ) tal que
Aquí ψ n es el polinomio de n divisiones de E ; las raíces de ψ n son los puntos distintos de cero de orden n en E . Existe una fórmula complicada [3] para E y P en términos de W 1 , W 2 , W 3 y W 4 .
Existe una definición alternativa de EDS que utiliza directamente curvas elípticas y produce una secuencia que, hasta el signo, casi satisface la recursividad de EDS. Esta definición comienza con una curva elíptica E / Q dada por una ecuación de Weierstrass y un punto de no torsión P ε E ( Q ). Uno escribe las coordenadas x de los múltiplos de P como
Entonces, la secuencia ( D n ) también se denomina secuencia de divisibilidad elíptica . Es una secuencia de divisibilidad, y existe un número entero k de modo que la subsecuencia (± D nk ) n ≥ 1 (con una elección apropiada de signos) es una EDS en el sentido anterior.
Crecimiento de EDS
Sea ( W n ) n ≥ 1 una EDS no singular que no es periódica. Entonces la secuencia crece exponencialmente cuadrática en el sentido de que hay una constante positiva h tal que
El número h es la altura canónica del punto de la curva elíptica asociada a la EDS.
Primas y divisores primitivos en EDS
Se conjetura que una EDS no singular contiene sólo un número finito de números primos [4] Sin embargo, todos los términos de una EDS no singular, excepto un número finito, admiten un divisor primo primitivo. [5] Por lo tanto, para todos, excepto para un número finito de n , hay un primo p tal que p divide W n , pero p no divide W m para todos m < n . Esta afirmación es análoga al teorema de Zsigmondy .
EDS sobre campos finitos
Una EDS sobre un campo finito F q , o más generalmente sobre cualquier campo, es una secuencia de elementos de ese campo que satisface la recursividad EDS. Una EDS sobre un campo finito es siempre periódica y, por tanto, tiene un rango de aparición r . El período de una EDS sobre F q tiene entonces la forma rt , donde r y t satisfacen
Más precisamente, hay elementos A y B en F q * tales que
Los valores de A y B están relacionados con el emparejamiento Tate del punto en la curva elíptica asociada.
Aplicaciones de EDS
Bjorn Poonen [6] ha aplicado EDS a la lógica. Utiliza la existencia de divisores primitivos en EDS en curvas elípticas de rango uno para demostrar la indecidibilidad del décimo problema de Hilbert sobre ciertos anillos de números enteros.
Katherine E. Stange [7] ha aplicado EDS y sus generalizaciones de rango superior llamadas redes elípticas a la criptografía. Ella muestra cómo se puede utilizar EDS para calcular el valor de los emparejamientos de Weil y Tate en curvas elípticas sobre campos finitos. Estos emparejamientos tienen numerosas aplicaciones en la criptografía basada en emparejamientos .
Referencias
- ^ Morgan Ward, Memorias sobre secuencias de divisibilidad elíptica, Amer. J. Math. 70 (1948), 31–74.
- ^ B. Mazur. Curvas modulares y el ideal de Eisenstein, Inst. Hautes Études Sci. Publ. Matemáticas. 47: 33–186, 1977.
- ^ Esta fórmula se debe a Ward. Consulte el apéndice de JH Silverman y N. Stephens. El signo de una secuencia de divisibilidad elíptica. J. Ramanujan Math. Soc. , 21 (1): 1–17, 2006.
- ^ M. Einsiedler, G. Everest y T. Ward. Primas en secuencias de divisibilidad elíptica. LMS J. Comput. Matemáticas. , 4: 1–13 (electrónico), 2001.
- ^ JH Silverman. El criterio de Wieferich y laconjetura abc . J. Teoría de números , 30 (2): 226-237, 1988.
- ^ B. Poonen. Usando curvas elípticas de rango uno hacia la indecidibilidad del décimo problema de Hilbert sobre anillos de números enteros algebraicos. En teoría algorítmica de números (Sydney, 2002) , volumen 2369 de Lecture Notes in Comput. Sci. , páginas 33–42. Springer, Berlín, 2002.
- ^ K. Stange. El emparejamiento Tate a través de redes elípticas. En Criptografía basada en emparejamiento (Tokio, 2007) , volumen 4575 de Lecture Notes in Comput. Sci. Springer, Berlín, 2007.
Material adicional
- G. Everest, A. van der Poorten, I. Shparlinski y T. Ward. Secuencias de recurrencia , volumen 104 de Encuestas y monografías matemáticas . Sociedad Americana de Matemáticas, Providence, RI, 2003. ISBN 0-8218-3387-1 . (El Capítulo 10 está sobre EDS).
- R. Shipsey. Secuencias de divisibilidad elíptica . Tesis doctoral, Goldsmith's College (Universidad de Londres), 2000.
- K. Stange. Redes elípticas . Tesis de doctorado, Brown University, 2008.
- C. Swart. Secuencias relacionadas con curvas elípticas . Tesis doctoral, Royal Holloway (Universidad de Londres), 2003.