Patrón de iteración Newton-Raphson$x\mapsto\frac{1}{2}(x+\frac{q}{x})$ sobre campos finitos

Question

Jugando con el de Newton-Raphson método de campo finito $\mathbb{F}_p$, me di cuenta de algo lindo patrones que no puedo explicar de mi cerebro contaminado con el análisis.

Aquí está la configuración:

De configuración. Deje $p$ ser impar el primer y $q \in \mathbb{F}_p$. Definir el grafo dirigido $G_{p,q}$ como sigue:

• El vértice de $G_{p,q}$ es simplemente $\mathbb{F}_p$.
• Un (dirigida) edge $[x, y\rangle$ está en el borde de $G_{p,q}$ si y sólo si $x^2 - 2xy + q = 0$ sostiene.

En el caso de $q \neq 0$, bordes de $G_{p,q}$ son de la forma $[x, f(x) \rangle$ para $f(x) = \frac{1}{2}(x+\frac{q}{x})$ e $x\in\mathbb{F}_p\setminus\{0\}$. Observe que $f$ es exactamente la función que se plantea en el método de Newton-Raphson el método para encontrar los ceros de $x^2 - q$.

Aquí hay una rápida observación: Para cada una de las $ y \in \mathbb{F}_p$,

1. $y^2-q$ es un no-cero residuo cuadrático módulo $p$, por lo que son exactamente $2$ bordes apunta a $y$.

2. $y^2 - q = 0$ en $\mathbb{F}_p$, por lo que $\{y\}$ está conectado a un componente de $G_{p,q}$ con el bucle de $[y, y\rangle$.

3. $y^2 - q$ no es un residuo cuadrático módulo $p$, de modo que ningún borde puntos en $y$, es decir, $y$ es una hoja.

Parece que, por cada $p$, la conectividad de la estructura de $G_{p,q}$ sólo depende de si $q$ es un residuo cuadrático módulo $p$ o no. Por ejemplo, si $p=43$, entonces sólo los dos siguientes posibilidades de conectividad emerge:

Y el siguiente es el caso de $p=113$.

Así que la pregunta obvia es

Pregunta.

(1) Podemos encontrar una explicación de por qué la conectividad de la estructura de $G_{p,q}$ para $p$ impar primer y $q \in \mathbb{F}_{p}\setminus\{0\}$ parece que sólo dependen de los residuos cuadráticos de $q$?

(2) Podemos relacionar la estructura de la $G_{p,q}$ en términos de número de la teoría de las propiedades de $(p, q)$? Por ejemplo, ¿qué es tan especial acerca de esta construcción que los componentes se ven tan 'simétrico'?

Sé que estoy en lugar de lanzar preguntas al azar de profunda curiosidad, así que me perdone si las preguntas parecen no bien formado o es ya bien conocido. Me gustaría considerar esta cuestión como una recreación de uno, y agradecería cualquier comentario.

Answer 1

Supongamos primero que $q$ es un residuo cuadrático módulo $p$. Por Misha Lavrov, la respuesta de podemos entonces asumir que $q=1$. Estamos interesados en el comportamiento de la recorre de $$ f(x):=\frac12\left(x+\frac1x\right). $$

Considere la posibilidad de la transformación de Möbius el conjunto $P=\Bbb{F}_p\cup\{\infty\}$ a sí mismo $$ \mu(t):=\frac{t+1}{t-1}. $$ Vemos que $$ \begin{aligned} f(\mu(t))&=\frac12\left(\frac{t+1}{t-1}+\frac{t-1}{t+1}\right)\\ &=\frac{t^2+1}{t^2-1}\\ &=\mu(t^2). \end{aligned} $$ Esto significa que, hasta la conjugación por $\mu$, la asignación de $f$ se acaba de cuadrar en el conjunto $P$. Por lo tanto, $f$ y el cuadrado de producir isomorfo gráficos de las transiciones.

Lo que sucede en el conjunto de $P$ cuando nos iteratedly elementos cuadrados en la que se estudió en este hilo (disculpas por la voladura de mi propia trompeta a este punto). De todos modos, podemos decir lo siguiente:

Suponga $q$ es una ecuación cuadrática de residuos. Escribir $p-1=2^m a,$ donde $a$ es impar. Entonces después de $m$ iteraciones de $f$ el conjunto de imágenes se ha estabilizado. Llamar a este conjunto de $S$. A continuación, más iteraciones se acaba de permutar el conjunto $S$. La estructura del ciclo de una sola iteración en el set $S$ puede ser conseguido por mirar lo que sucede con la multiplicación por dos del modulo $a$.

Como ejemplo vamos a considerar el caso de $p=43$. Esta vez $m=1, a=21$. Modulo $21$ multiplicación por dos produce los ciclos $$ (0)(1,2,4,8,16,11)(3,6,12)(5,10,20,19,17,13)(7,14)(9,18,15). $$ De hecho, podemos ver dos de 6 ciclos, de dos 3-ciclos y solo un 2-ciclo en Sangchul Lee la imagen de este gráfico.

Por otro lado, con $p=113$ obtenemos $p-1=2^4\cdot7$. Esto explica por qué podemos obtener la inversa de binario ramificación hasta la profundidad de los cuatro, y luego el modulo $a=7$ vemos los ciclos $$ (0)(124)(365). $$

---

Cuando $q$ no es un cuadrado de un elemento de $\Bbb{F}_p$ , la situación es un poco diferente. Para aplicar las ideas anteriores también trabajamos en el interior de la cuadrática extensión de campo $\Bbb{F}_p(\sqrt{q})$.

En este momento estamos interesados en las iteraciones de $$ f(x)=\frac12\left(x+\frac q x\right). $$ Como en el anterior, vemos que (como se observa en la Sangchul Lee en un comentario a la primera parte) la transformación de Möbius $$ \mu_q(t)=\sqrt q\frac{t+1}{t-1} $$ todavía podemos obtener la cuadratura de la regla $$ f(\mu_q(t))=\mu_q(t^2). $$ La diferencia proviene de la selección de un conjunto apropiado para el parámetro $t$ a gama.

La pregunta especifica que $$ x=\mu_q(t)\qquad(*) $$ debe variar más de $x\in\Bbb{F}_p$. La solución para $t$ a partir de la ecuación $(*)$da $$ t=\frac{x+\sqrt{p}}{x-\sqrt{q}}. $$

Lema. Cuando $x$ rangos de $\Bbb{F}_p\cup\{\infty\}$ la fracción $t=(x+\sqrt q)/(x-\sqrt q)$ rangos sobre el grupo multiplicativo de la norma uno de los elementos de $\Bbb{F}_{p^2}$. En otras palabras $$ S:=\left\{\frac{x+\sqrt{p}}{x-\sqrt{q}}\bigg\vert\,x\in\Bbb{F}_p\cup\{\infty\}\right\} =\{z\in\Bbb{F}_{p^2}\mediados de z^{p+1}=1\}. $$ Prueba. La no-trivial automorphism del campo $\Bbb{F}_{p^2}$ es claramente $$F:a+b\sqrt q\mapsto a-b\sqrt q.$$ Por otro lado, por la bien conocida teoría de Galois de campos finitos, $F$ debe ser el Frobenius automorphism y también tenemos $F(z)=z^p$. En particular, $(x\pm\sqrt q)^p=x\mp\sqrt q$ para todos los $x\in\Bbb{F}_p$. Por lo tanto, si $z=(x+\sqrt q)/(x-\sqrt q)$ hemos $$ z^p=F(z)=\frac{x-\sqrt q}{x+\sqrt q}=\frac 1z. $$ Esto implica que $z^{p+1}=1$. Debido a que el grupo multiplicativo $\Bbb{F}_{p^2}^*$ es cíclico de orden $p^2-1=(p-1)(p+1)$, la ecuación de $z^{p+1}=1$ ha $p+1$ soluciones en $\Bbb{F}_{p^2}$. Diferentes opciones de $x$ llevar a diferentes valores de $z$, por lo que hemos encontrado todas las soluciones. QED.

El resto es entonces fácil. Sabemos que $S$ es un grupo cíclico de orden $p+1$. Repitiendo el argumento anterior, llegamos a la siguiente caracterización:

Suponga que $q$ es una ecuación cuadrática no residuo. Escribir $p+1=2^\ell b$, $b$impar. Luego, después de $\ell$ iteraciones la imagen de $f$ se ha estabilizado. Cualquier iteraciones de $f$ va a permutar este conjunto con la misma estructura del ciclo como la multiplicación por $2$ perutes el residuo de clases modulo $b$.

Como un ejemplo, considere el caso $p=43$, $q=3$ a partir de la parte superior derecha de la imagen en Sangchul Lee la pregunta. Aquí $p+1=44=2^2\cdot11$. Por lo tanto, la gráfica tiene dos etapas de binario rama de convergencia. Modulo $b=11$ multiplicación por dos ve como $$(0)(1,2,4,8,5,10,9,7,3,6)$$ explicar la aparición de un 10-ciclo (y un punto fijo) se ve en la imagen.

Del mismo modo, cuando se $p=113$, obtenemos $p+1=114=2\cdot57$. Después de un solo paso de dos ramas convergentes que nos queda para el estudio de los ciclos de multiplicación por dos del modulo $57=3\cdot19$. Dos es una raíz primitiva módulo $19$, por lo que se deduce que tenemos tres de 18 ciclos, un punto fijo $0$, y un 2-ciclo de $(19,38)$. De nuevo, de acuerdo con el gráfico en la parte inferior derecha.

---

Comentario: he cocinado un análogo de la Lexema una vez para el estudio de ciertos caracteres sumas. Un colega se utiliza para estudiar la correlación de las propiedades de ciertas familias de secuencias. Ver este MathOverflow hilo, donde Michael Zieve hace algo similar. Véase también Peter Müller respuesta para una generalización. Así que yo no soy el inventor. Yo simplemente no lo había visto antes. De todos modos, el Lema es totalmente análogo al hecho de que $$ \left\{\frac{x+y}{x i}\in\Bbb{C}\bigg\vert\,x\in\Bbb{R}\cup\{\infty\}\right\} $$ es el círculo unitario del plano complejo.

Answer 2

Siempre que $q_1, q_2$ son ambos residuos cuadráticos módulo $p$, o ambos cuadrática nonresidues modulo $p$, podemos encontrar una constante $c \ne 0$ tal que $q_2 \equiv c^2 \cdot q_1 \pmod p$. A continuación, la multiplicación por $c$ induce un gráfico de isomorfismo entre $G_{p,q_1}$ e $G_{p,q_2}$:

$$ (x,y) \in E(G_{p,q_1}) \iff x^2 - 2xy + q_1 \equiv 0 \\ \iff (cx)^2 - 2(cx)(cy) + c^2q_1 \equiv 0 \iff (cx, cy) \in E(G_{p,q_2}). $$ Así que en este caso, $G_{p,q_1}$ e $G_{p,q_2}$ va a mirar de la misma con sólo los vértices recalificado (y el reetiquetado es la multiplicación por $c$).