¿Qué ecuaciones diofantinas pueden resolverse utilizando fracciones continuas?

Question

Las ecuaciones de Pell pueden resolverse utilizando fracciones continuas. He oído que algunas curvas elípticas pueden "resolverse" utilizando fracciones continuas. ¿Es esto cierto?

¿Qué ecuaciones diofantinas distintas de las ecuaciones de Pell pueden resolverse para puntos racionales o enteros utilizando fracciones continuas? Si hay otras, ¿cuáles son algunas buenas referencias?

Edita:

El profesor Elkies ha dado una excelente respuesta sobre el papel de las fracciones continuas en la resolución de ecuaciones diofánticas generales, incluidas las curvas elípticas. ¿Cuáles son otros métodos para resolver las ecuaciones de Diofantina $$X^2 - \Delta Y^2 = 4 Z^3$$ y $$18 x y + x^2 y^2 - 4 x^3 - 4 y^3 - 27 = D z^2 ?$$

Answer 1

[editado para insertar un párrafo sobre Cornacchia y el recuento de puntos].

Las fracciones continuas, o (más o menos) equivalentemente el algoritmo euclidiano, pueden utilizarse para encontrar soluciones de números enteros pequeños de ecuaciones lineales diofánticas $ax+by=c$ y soluciones enteras de ecuaciones cuadráticas como $x^2-Dy^2=\pm1$ ("Pell"). Las fracciones continuas en sí mismas no encuentran puntos racionales en curvas elípticas, pero existe una técnica que utiliza los puntos de Heegner para calcular una aproximación real a un punto racional, que se recupera a partir de una fracción continua. Esto es posible porque el problema de recuperación consiste en encontrar una solución entera pequeña de una ecuación lineal diofántica. Mi artículo

Noam D. Elkies: Heegner point computations, Lecture Notes in Computer Science 877 (actas de ANTS-1, 5/94; L.M. Adleman y M.-D. Huang, eds.), 122-133.

podría haber sido el primero en describir este enfoque.

Otra aplicación de las fracciones continuas es Algoritmo de Cornacchia resolver $x^2+Dy^2=m$ para grandes $m>0$ coprimo a $D$ dado $x/y \bmod m$ que es la raíz cuadrada de $-D \bmod m$ . Esto se aplica a Contando puntos en curvas elípticas $E\bmod p$ para $E$ como $y^2 = x^3 + b$ ou $y^2 = x^3 + ax$ para el que el campo CM ${\bf Q}(\sqrt{-D})$ es conocido: el recuento (incluido el punto en el infinito) es $p+1-t$ où $t^2+Du^2=4p$ para algunos números enteros $t$ y $u$ y esto determina $t$ hasta una ambigüedad de como máximo $6$ posibilidades que en la práctica se resuelve fácilmente. La raíz cuadrada necesaria mod $p$ se encuentra fácilmente en al azar tiempo polinómico, aunque es una vergüenza persistente que no podamos extraer raíces cuadradas módulo a un primo grande en determinista tiempo polinómico sin asumir algo como la hipótesis de Riemann ampliada. De hecho, la aplicación que Schoof dio para motivar su algoritmo de tiempo polinomial para calcular $t$ para cualquier curva elíptica mod $p$ era recuperar una raíz cuadrada de $-D \bmod p$ para pequeños $D$ ¡! (Aunque esto nunca se haría en la práctica porque el exponente en el algoritmo de Schoof es mucho mayor que para el algoritmo aleatorio). La referencia del artículo de Schoof es

René Schoof: Curvas elípticas sobre campos finitos y cálculo de raíces cuadradas $\bmod p$ , Matemáticas. Comp. 44 (nº 170, abril de 1985), 483-494.

Una generalización natural del algoritmo euclidiano a dimensiones superiores es el algoritmo LLL y otras técnicas de reducción de bases reticulares (LBR), que han encontrado varios otros usos diofánticos, incluidas algunas otras técnicas para encontrar puntos racionales en curvas elípticas; otro de mis trabajos describe algunas de estas aplicaciones diofantinas de LBR.

Answer 2

En 1993, Tzanakis ( http://matwbn.icm.edu.pl/ksiazki/aa/aa64/aa6435.pdf ) demostraron que resolver una ecuación cuártica de Thue, cuyo campo cuártico correlativo es el compositum de dos campos cuadráticos reales, se reduce a resolver un sistema de ecuaciones de Pellian.

Aunque el sistema de ecuaciones de Pellian no pueda resolverse completamente, la información sobre las soluciones obtenida a partir de la teoría de fracciones continuas y aproximaciones diofánticas podría ser suficiente para demostrar que la ecuación de Thue (o desigualdad de Thue) no tiene soluciones o sólo tiene soluciones triviales. Para ello, una herramienta muy útil es el resultado de Worley que caracteriza todas las aproximaciones racionales que satisfacen $|\alpha - \frac{p}{q}| < \frac{c}{q^2}$ en términos de convergentes de fracción continua de $\alpha$ . Puede consultar el documento "Solving a family of quartic Thue inequalities using continued fractions" ( http://web.math.pmf.unizg.hr/~duje/pdf/dij.pdf ) y las referencias que allí figuran.

Answer 3

Para tu problema de ejemplo, obtengo dos tipos de identidad, principal y no principal.

Para el discriminante 229, tomo la forma de identidad como $$ f(x,y) = x^2 + 15 x y - y^2.$$ Una de sus familias es $$ f(x^3 + 3 x y^2 + 5 y^3, \; 3 x^2 y + 45 x y^2 + 226 y^3 ) \; = \; f^3(x,y).$$ Como automorfo de $f$ es $$ \left( \begin{array}{rr} 1 & 15 \\\ 15 & 226 \end{array} \right) , $$ del vector columna $(1,0)^T$ obtenemos otra representación de 1 como $(1,15)^T.$ Así que eso es un tipo de cosa.

Para las otras dos clases, tome $$ g(x,y) = 3 x^2 + 13 x y - 5 y^2.$$ Una segunda familia es $$ f( x^3 + 12 x^2 y + 57 x y^2 + 89 y^3, \; 2 x^3 - 3 x^2 y - 3 x y^2 - 6 y^3 ) \; = \; g^3(x,y).$$
$$ $$ $$ $$ Los siguientes ciclos de formas reducidas son como en el libro de Buell, páginas 21-30.

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle 
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
1  15  -1

0  form   1 15 -1   delta  -15
1  form   -1 15 1   delta  15
2  form   1 15 -1
minimum was   1rep 1 0 disc   229 dSqrt 15.13274595  M_Ratio  229
Automorph, written on right of Gram matrix:  
-1  -15
-15  -226
 Trace:  -227   gcd(a21, a22 - a11, a12) : 15
=========================================

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle 
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
3 13 -5

0  form   3 13 -5   delta  -2
1  form   -5 7 9   delta  1
2  form   9 11 -3   delta  -4
3  form   -3 13 5   delta  2
4  form   5 7 -9   delta  -1
5  form   -9 11 3   delta  4
6  form   3 13 -5
minimum was   3rep 1 0 disc   229 dSqrt 15.13274595  M_Ratio  25.44444
Automorph, written on right of Gram matrix:  
-16  -75
-45  -211
 Trace:  -227   gcd(a21, a22 - a11, a12) : 15
=========================================

Answer 4

Estaba a punto de mencionar el algoritmo de H J S Smith para encontrar soluciones enteras a $x^2 + y^2 = p$ para $p \equiv 1$ mod 4; pero a esto se hace referencia en un hilo relacionado en Aplicaciones de las fracciones continuas finitas

(Disculpas si ese hilo se encuentra fácilmente a partir de éste; pero yo no me habría dado cuenta sin hacer una búsqueda en Google, y quizá algunos otros lectores sean igualmente inexpertos en las formas de StackOverflow o poco observadores).

Además, ¿qué ocurre con las fracciones continuas de dimensiones superiores, expresadas como relaciones de recurrencia matriciales? Creo recordar que se pueden utilizar para encontrar soluciones racionales de ecuaciones en las que intervienen algunos tipos de formas cúbicas.

Answer 5

Debería haberme ceñido a su notación preferida, como en su $B^2 + B C - 57 C^2 = A^3$ en un comentario. Así que la forma de interés será $x^2 + x y - 57 y^2.$ Las otras clases con este discriminante de formas cuadráticas binarias integrales indefinidas vendrían dadas entonces por $ 3 x^2 \pm xy - 19 y^2.$

Por lo tanto, tome $$ \phi(x,y) = x^2 + x y - 57 y^2.$$ La identidad que necesita para hacer frente a su $A= \pm 3$ es $$ \phi( 15 x^3 - 99 x^2 y + 252 x y^2 - 181 y^3 , \; 2 x^3 - 15 x^2 y + 33 x y^2 - 28 y^3 ) \; = \; ( 3 x^2 + xy - 19 y^2 )^3 $$

Esto nos lleva directamente a $\phi(15,2) = 27.$ Utilizando $ 3 x^2 + x y - 19 y^2 = -3$ cuando $x=7, y=3,$ esto conduce directamente a $ \phi(1581, -196) = -27.$

Sin embargo, tenemos un automorfo de $\phi,$ $$ W \; = \; \left( \begin{array}{rr} 106 & 855 \\\ 15 & 121 \end{array} \right) , $$ y $ W \cdot (1581,-196)^T = (6, -1)^T,$ así que $\phi(6,-1) = -27.$

Por último, cualquier forma principal del discriminante impar, llámese $x^2 + x y + k y^2,$ (tiene $k=-57$ ) tiene el automorfo impropio $$ Z \; = \; \left( \begin{array}{rr} 1 & 1 \\\ 0 & -1 \end{array} \right) , $$ mientras que $ Z \cdot (6,-1)^T = (5, 1)^T,$ así que $\phi(5,1) = -27.$

EDIT: una única fórmula no puede ser visualmente obvia para todos los resultados deseados. Hay un número infinito de soluciones integrales para $3 x^2 + x y - 19y^2 = -3.$ Es una excelente apuesta que uno de estos conduce, a través de la identidad que doy, a por lo menos uno de los deseados $\phi(5,1) = -27$ ou $\phi(6,-1) = -27,$ pero no necesariamente ambos, en gran parte porque $3 x^2 + x y - 19y^2$ y $3 x^2 - x y - 19y^2$ no son propiamente equivalentes. Creo que merece la pena investigarlo.