Prueba de que $x^2 - 2y^2 = -1$ tiene una solución recurrente para $x$

Question

Leo aquí sobre la siguiente variación de Pell's equation : $$ x^2 - 2y^2 = -1.$$

Según El solucionador de Darío Alpern la ecuación tiene infinitas soluciones enteras, que pueden ser generadas por la recursión: $$x_n = 3x_{n-1} + 4y_{n-1},\\ y_n = 2x_{n-1} + 3y_{n-1}.$$

Sólo me interesan las soluciones para $x$ . Según el Enciclopedia en línea de las secuencias de números enteros resulta (al introducir los primeros valores de $x_n$ de lo anterior), que la secuencia se puede escribir como la siguiente recurrencia lineal: $$x_n = 6x_{n-1} - x_{n-2}.$$

Pregunta: ¿Hay pruebas de que las soluciones para $x$ puede escribirse como $2$ -recurrencia lineal profunda (sin utilizar la fórmula anterior para $x$ y $y$ del solucionador)? Si la respuesta es larga y complicada, bastaría con una referencia a una prueba bien explicada.

Answer 1

Los problemas de este tipo se manejan mejor usando Transformación z . Me resulta más fácil trabajar con $z$ que es el operador de avance unitario, es decir, aumenta el subíndice en $1$

Podemos reescribir la recurrencia original como (donde se acostumbra a usar mayúsculas) $$ z X= 3 X + 4Y,\\ z Y = 2X + 3Y. $$ Eliminar $Y$ y aislar la mayor potencia de $z$ : $$ z^2 X - 6 z X + X = 0 ~\Rightarrow z^2 X = 6 z X -X$$

Ahora que $z$ ha hecho su parte, utiliza el hecho de que $z$ avanza el índice en $1$ y $z^2$ por 2 para obtener $$ z^2 X = 6 z X -X \Rightarrow x_{n+2} = 6 x_{n+1} - x_n$$

Si quiere escribir en términos de índices antes de $n$ luego vuelve a dividir la última ecuación por $z^2$ para conseguir $$X = 6 z^{-1} X - z^{-2} X$$ o $$ X = 6 z^{-1} X - z^{-2} X \Rightarrow x_n = 6 x_{n-1} -x_{n-2}$$

Es una cuestión de gusto trabajar con $z$ o $z^{-1}$ . Personalmente prefiero $z$ hasta el final. El procedimiento anterior funciona para cualquier relación de recurrencia lineal acoplada en cualquier número de variables. Sólo el álgebra se complica

Answer 2

A ver si puedo mostrarte cómo descubrir la fórmula de recurrencia sin usar la fracción continua. Para ello tienes que asume que existe una recurrencia lineal e intentas descubrirla.

Ahora dejemos que $$ J = \begin{bmatrix}1 & 0\cr 0 & -2\end{bmatrix}$$ Entonces la ecuación original es $$ \begin{bmatrix}x & y\end{bmatrix}\, J \,\begin{bmatrix}x \\ y\end{bmatrix}=-1$$

Supongamos que existe una relación de recurrencia $$ \begin{bmatrix}x_n \\ y_n\end{bmatrix}= \begin{bmatrix}\alpha& \beta\cr \gamma & \delta\end{bmatrix}\begin{bmatrix}x_{n-1}\\ y_{n-1}\end{bmatrix}$$ Para satisfacer la ecuación original necesitamos $$ \begin{bmatrix}\alpha& \beta\cr \gamma & \delta\end{bmatrix}^{T} \begin{bmatrix}1 & 0\cr 0 & -2\end{bmatrix} \begin{bmatrix}\alpha& \beta\cr \gamma & \delta\end{bmatrix} = \begin{bmatrix}1 & 0\cr 0 & -2\end{bmatrix} $$

Si lo multiplicas para obtener 4 ecuaciones. Terminarás con otra ecuación de Pellian de la misma forma. Todo lo que necesitas es un solución con el menor valor para el $\alpha$ , $\beta$ , $\gamma$ y $\delta$ .

Obtendrás las ecuaciones: $$ \beta^2 - 2 \alpha^2 = 2$$ La solución más pequeña es $\alpha =3$ , $\beta=4$ .

La otra ecuación que necesitas es $$ \delta^2-2\gamma^2=1$$ $\delta=3$ , $\gamma=2$ es claramente la solución más pequeña.

Answer 3

Recomiendo al menos dos libros, Formas cuadráticas binarias por Duncan A. Buell, y Formas cuadráticas binarias de Buchmann y Vollmer. Buell lo explica mejor.

Teniendo en cuenta algunos $n,$ que es $2$ en su caso, encontramos la solución más pequeña para $$ u^2 - n v^2 = 1 $$ con ambos $u,v > 0.$ El hecho de que siempre haya una solución no trivial requiere varios pasos.

Obtenemos el generador del grupo de automorfismo, $$ A = \left( \begin{array}{cc} u & nv \\ v & u \end{array}\right). $$ Los valores propios son $\lambda = u + v \sqrt n$ y $1/\lambda = u - v \sqrt n,$ y satisfacen $$ \lambda^2 - 2 u \lambda + 1 = 0. $$ Dividir por $\lambda^2$ para confirmar que $$ \frac{1}{\lambda^2} - 2 u \frac{1}{\lambda} + 1 = 0. $$ Los vectores propios son $$ \left( \begin{array}{c} \sqrt n \\ 1 \end{array}\right), \left( \begin{array}{c} - \sqrt n \\ 1 \end{array}\right). $$ No son ortogonales, pero son una base del espacio vectorial $\mathbb R^2.$ Cualquier vector de columnas $$ \left( \begin{array}{c} x \\ y \end{array}\right) $$ puede escribirse como una combinación lineal de esas dos. Es bastante fácil de comprobar, $$ A^2 - 2 u A + I = 0. $$ Por lo tanto, si $$ w = \left( \begin{array}{c} x_j \\ y_j \end{array}\right), \; \; A w = \left( \begin{array}{c} x_{j+1} \\ y_{j+1} \end{array}\right), \; \; A^2 w = \left( \begin{array}{c} x_{j+2} \\ y_{j+2} \end{array}\right), $$ encontramos $$ A^2 w = 2 u A w - w, $$ y su recurrencia sigue.

También se puede confirmar fácilmente que $$ x_{j+2}^2 - n y_{j+2}^2 = x_{j+1}^2 - n y_{j+1}^2 = x_{j}^2 - n y_{j}^2. $$

Si su $ x_{j}^2 - n y_{j}^2$ fueran otra cosa que $\pm 1,$ habría un problema exactamente en este punto, porque no es el caso en general que todas las soluciones de una variante de Pell, con otra mano derecha, esté en la órbita de automorfismo de un único vector semilla. Sin embargo, como ha $x^2 - n y^2 = -1,$ se deduce, después de bastante detalle, que sólo hay una órbita: todas las soluciones suceden así, permitir entradas negativas no cambia nada y así sucesivamente. Obsérvese también que cuando tenemos $x^2 - n y^2 = -1$ con un mínimo de positivos $x,y,$ se deduce que $$ u = x^2 + n y^2, \; \; \; v = 2 x y. $$

El jueves. Puede ayudar a señalar que, por algún problema $x^2 - n y^2 = k,$ el formalismo anterior da una conjunto finito de secuencias $(x_j,y_j)$ de soluciones que sí satisfacen la recurrencia de grado dos. Lo que ocurre es que, si se ponen todas las $x$ en orden, el efecto es que se mezclan las secuencias, la indexación se desvía y ya no se pueden ver estas relaciones. Pero, si se sabe lo que está pasando, es bastante fácil sacar un conjunto finito de valores semilla para $x.$ Esto ocurriría, por ejemplo, al resolver $$ x^2 - 2 y^2 = 119 = 7 \cdot 17 . $$ Esto se divide naturalmente en cuatro secuencias de soluciones, $$ (11,1); \; (37,25); \; (211,149); \; (1229,869); \ldots $$ $$ (13,5); \; (59,41); \; (341,241); \; (1987,1405); \ldots $$ $$ (19,11); \; (101,71); \; (587,415); \; (3421,2419); \ldots $$ $$ (29,19); \; (163,115); \; (949,671); \; (5531,3911); \ldots $$ Si pones todos los $x$ valores en orden, $$ 11,13,19,29,37,59,101,163,211,341,587,949,1229,1987,3421,5531,\ldots $$ se obtiene $$ x_{j + 8} = 6 x_{j+4} - x_j. $$