¿Una partición en tres clases del conjunto de todos los números primos?

Question

Esta es una continuación (y tipo de simplificación) de esta pregunta.

Deje que las secuencias de enteros $(r_n)$, $(s_n)$ y $(t_n)$, ($n \ge 0$) será definido por el mismo segundo orden lineal de la recurrencia, pero con un poco diferentes condiciones iniciales: $$r_n=4r_{n-1}-r_{n-2}\ \ \text{ with} \ r_0 =1, \ r_1=2$$ $$s_n=4s_{n-1}-s_{n-2}\ \ \text{ with} \ s_0 =1, \ s_1=5$$ $$t_n=4t_{n-1}-t_{n-2}\ \ \text{ with} \ t_0 =1, \ t_1=3$$ Estas son las secuencias de A001075, A001834 y A001835 (desplazado), respectivamente.

Deje $\mathbb{R}$ ( $\mathbb{S}$ $\mathbb{T}$ ) el conjunto de los primos divisores de los miembros de la secuencia de $(r_n)$ ( $(s_n)$ $(t_n)$). $$\mathbb{R}=\{2,7,13,31,37,61,73,79,97,103,109,127,151,157,181,193,199,223,229,271,…\}$$ $$\mathbb{S}=\{5,19,23,29,43,47,53,71,101,149,163,167,173,191,197,239,263,269,...\}$$ $$\mathbb{T}=\{3,11,17,41,59,67,83,89,107,113,131,137,139,179,211,227,233,241,251,257,…\}$$

Es cierto que $\mathbb{R}$, $\mathbb{S}$ y $\mathbb{T}$ hacer una partición en tres clases de el conjunto de todos los números primos?

Edit: Gracias a la observación de @Yong Hao Ng que no se conoce ningún miembro de $\mathbb {R}$$19 \pmod {24}$, y dado que se conoce el hecho de que la densidad de los números primos que están en $\mathbb {S}$ (resp. en $\mathbb {T}$)$\frac{1}{3}$, [Lagarias, J. C., El conjunto de los números primos dividiendo los números de Lucas tiene una densidad de 2/3, Pac. J. Math. 118, 449-461 (1985). ZBL0569.10003.], nos aventuramos la siguiente conjetural de la tabla sobre la densidad de los números primos en un determinado residuo de la clase modulo $24$ $\mathbb {R}$ (resp. en $\mathbb {S}$,$\mathbb {T}$): \begin{matrix} &|&1&5&7&11&13&17&19&23\\ -&&---&---&---&---&---&---&---&---\\ \mathbb{T}&|&\frac{1}{48} & &&\frac{1}{8}&&\frac{1}{8}&\frac{1}{16}&\\ \mathbb{S}&|&\frac{1}{48} & \frac{1}{8}&&&&&\frac{1}{16}&\frac{1}{8}\\ \mathbb{R}&|&\frac{1}{12} && \frac{1}{8}&&\frac{1}{8}&&&&\\ \end{de la matriz}

La suma de cada fila es $\frac{1}{3}$ y la suma de cada columna es $\frac{1}{8}$, como se esperaba desde $\phi(24)=8$.

Answer 1

Se puede demostrar que $(r_n),(s_n),(t_n)$ son coprime, por lo que los números primos que ocurren en la que uno no puede ocurrir en otro. Sin embargo no estoy tan seguro de si todos los primos se producen. Buscando en la reciprocidad cuadrática, podemos ver que $$ \begin{align*} \mathbb R&: p\equiv 7,13,1,19 \pmod{24}\\ \mathbb S&: p\equiv 5,23,1,19 \pmod{24}\\ \mathbb T&: p\equiv 11,17,1,19 \pmod{24} \end{align*} $$ Edit 1: véase el apéndice B
Así que por lo menos no cubrir todas las clases de $\pmod{24}$. Este método es mucho más corto, pero por desgracia no hay superposición de modo que no puede dividir los números primos en lo propio.

0. Esquema de la prueba
Queremos mostrar que los números primos que ocurren en $(s_n)$ no aparece en $(r_n)$ o $(t_n)$, por lo tanto de una manera directa, es para mostrar que $$ \gcd(r_i,s_j)=\gcd(t_i,s_j)=1 $$ para todos los $i,j\geq 0$. (De manera similar comprobación $\gcd(r_i,t_j)=1$.)

Para ello, ponemos a prueba un conjunto de 6 igualdades para todos los $n,k\geq 0$: $$ \begin{align*} \gcd(r_{n+1+k},s_n) &= \gcd(t_k,s_n)\\ \gcd(r_n,s_{n+k}) &= \gcd(r_n,t_k)\\ \gcd(t_{n+k},s_n) &= \gcd(r_k,s_n)\\ \gcd(t_n,s_{n+k}) &= \gcd(t_n,r_k)\\ \gcd(t_{n+k},r_n) &= \gcd(s_k,r_n)\\ \gcd(t_n,r_{n+1+k}) &= \gcd(t_n,s_k) \end{align*} $$ (Observe que los índices no están en equilibrio, lo que sucede por $r$ con el mayor índice).

Observar que al momento de la aplicación repetida de los índices son estrictamente decreciente. Esta no cubre $\gcd(r_n,s_n)$$\gcd(t_n,r_n)$, pero la prueba cubrirá los gastos a lo largo del camino.

Por lo tanto, dado un iniciando $\gcd(r_i,s_j)$ o $\gcd(t_i,s_j)$, se puede reducir a un $\gcd(r_l,s_m)$ o $\gcd(t_l,s_m)$ para algunos pequeños $l,m$, decir $0\leq l,m\leq 2$. Todo esto puede ser demostrado ser igual a $1$, por lo tanto $(s_n)$ es coprime a$(r_n)$$(t_n)$. (De manera similar $(r_n)$ coprime a $(t_n)$.)

1. Relación lineal entre las secuencias.
La actualización de la fórmula de las formas $$ \begin{align*} \begin{bmatrix} 1 & 1\\ 2 & 3 \end{bmatrix} \begin{bmatrix} r_n\\ s_n \end{bmatrix} = \begin{bmatrix} r_{n+1}\\ s_{n+1} \end{bmatrix}, \begin{bmatrix} 2 & 1\\ 3 & 2 \end{bmatrix} \begin{bmatrix} t_n\\ s_n \end{bmatrix} = \begin{bmatrix} t_{n+1}\\ s_{n+1} \end{bmatrix}, \begin{bmatrix} 5 & -2\\ 3 & -1 \end{bmatrix} \begin{bmatrix} t_n\\ r_n \end{bmatrix} = \begin{bmatrix} t_{n+1}\\ r_{n+1} \end{bmatrix} \end{align*} $$

Esto puede ser muestra de la siguiente manera: $$ \begin{align*} r_{n+1} &= r_n + s_n = r_n + 2r_{n-1}+3s_{n-1} = r_k + 2r_{n-1} + 3(r_n-r_{n-1}) = 4r_n-r_{n-1}\\ s_{n+1} &= 2r_n+3s_n = 2(r_{n-1}+s_{n-1})+3s_n= (s_n-3s_{n-1})+2s_{n-1}+3s_n=4s_n-s_{n-1}\\ t_{n+1} &= 2t_n+s_n = 2t_n+3t_{n-1}+2s_{n-1}=2t_n+3t_{n-1}+2(t_n-2t_{n-1})=4t_n-t_{n-1}\\ s_{n+1} &= 3t_n+2s_n=3(2t_{n-1}+s_{n-1})+2s_n=2(s_n-2s_{n-1})+3s_{n-1}+2s_n=4s_n-s_{n-1}\\ t_{n+1} &= 5t_n-2r_n = 5t_n-2(3t_{n-1}-r_{n-1})=5t_n-6t_{n-1}-(t_n-5t_{n-1})=4t_n-t_{n-1}\\ r_{n+1} &= 3t_n-r_n=3(5t_{n-1}-2r_{n-1})-r_n = 5(r_n+r_{n-1})-6r_{n-1}-r_n=4r_n-r_{n-1} \end{align*} $$

2. Mostrando que $r_n,s_n,t_n$ son parejas coprime
Desde $\gcd(r_1,s_1)=\gcd(t_1,s_1)=\gcd(r_1,t_1)=1$, podemos encontrar $u_1,v_1,w_1,z_1,f_1,g_1$ tal que $$ \begin{align*} u_1r_1 + v_1s_1 &= 1\\ w_zt_1 + z_1s_1 &= 1\\ f_1t_1 + g_1r_1 &= 1 \end{align*} $$ Podemos escribir esto en forma de matriz: $$ \begin{align*} \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} = 1, \begin{bmatrix} w_1 & z_1 \end{bmatrix} \begin{bmatrix} t_1\\ s_1 \end{bmatrix} = 1 , \begin{bmatrix} f_1 & g_1 \end{bmatrix} \begin{bmatrix} t_1\\ r_1 \end{bmatrix} = 1 \end{align*} $$ Debido a que la actualización de las matrices son invertible, más en general, tenemos $$ \begin{align*} 1= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} &= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} 3 & -1\\ -2 & 1 \end{bmatrix}^{n-1} \begin{bmatrix} 1 & 1\\ 2 & 3 \end{bmatrix}^{n-1} \begin{bmatrix} r_1\\ s_1 \end{bmatrix}\\ &= \begin{bmatrix} u_n & v_n \end{bmatrix} \begin{bmatrix} r_n\\ s_n \end{bmatrix}\\ 1 &= u_nr_n + v_ns_n \end{align*} $$ Por lo $\gcd(r_n,s_n)=1$ todos los $n$. Del mismo modo, $\gcd(t_n,s_n)=\gcd(r_n,t_n)=1$ desde $$ \begin{align*} 1= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} &= \begin{bmatrix} w_1 & z_1 \end{bmatrix} \begin{bmatrix} 2 & -1\\ -3 & 2 \end{bmatrix}^{n-1} \begin{bmatrix} 2 & 1\\ 3 & 2 \end{bmatrix}^{n-1} \begin{bmatrix} t_1\\ s_1 \end{bmatrix}\\ 1 &= w_nt_n + z_ns_n\\ 1= \begin{bmatrix} u_1 & v_1 \end{bmatrix} \begin{bmatrix} r_1\\ s_1 \end{bmatrix} &= \begin{bmatrix} f_1 & g_1 \end{bmatrix} \begin{bmatrix} -1 & 2\\ -3 & 5 \end{bmatrix}^{n-1} \begin{bmatrix} 5 & -2\\ 3 & -1 \end{bmatrix}^{n-1} \begin{bmatrix} t_1\\ r_1 \end{bmatrix}\\ 1 &= f_nt_n + g_nr_n \end{align*} $$ En particular, esta cubre los casos de $\gcd(r_n,s_n)=\gcd(t_n,r_n)=1$, como se menciona en [0].

3. Muestra el descenso de las igualdades
En lugar de computación $\gcd(a,b)$ directamente, utilizamos el hecho de que $$ \gcd(a,b) = \gcd(a\pmod b,b) $$ para reducir el $a$ a algo más pequeño.

El uso de $u_nr_n+v_ns_n=1$, tenemos $$ \begin{align*} u_nr_n &\equiv 1 \pmod{s_n}\\ u_nr_{n+1} &= u_n(r_n+s_n) \equiv 1 \equiv t_0 \pmod{s_n}\\ u_nr_{n+1+1} &= u_n(4r_{n+1}-r_n) \equiv 4\cdot 1 -1 \equiv t_1 \pmod{s_n}\\ u_nr_{n+1+k} &= u_n(4r_{n+k}-r_{n+k-1}) \equiv 4t_{k-1}-t_k\equiv t_k \pmod{s_n} \end{align*} $$ Por lo tanto, el uso de $\gcd(u_n,s_n)=1$, $$ \begin{align*} \gcd(r_{n+1+k},s_n) &= \gcd(u_nr_{n+1+k},s_n)\\ &= \gcd(u_nr_{n+1+k}\pmod{s_n},s_n)\\ &= \gcd(t_k,s_n) \end{align*} $$ muestra la primera de las seis de la igualdad. El resto de los cinco son similares, lo que completa la prueba. (Se enumeran en la siguiente sección de integridad, con la última de ellas es un poco diferente).

A. Misc. los cálculos
$$ \begin{align*} v_ns_n &\equiv 1 \equiv t_0 \pmod{r_n}\\ v_ns_{n+1} &= v_n(2r_n+3s+n) \equiv 3 \equiv t_1 \pmod{r_n}\\ v_ns_{n+k} &= v_n(4s_{n+k-1}+s_{n+k-2}) \equiv 4t_{k-1}-t_{k-2}\equiv t_k \pmod{r_n}\\ \gcd(r_n,s_{n+k}) &= \gcd(r_n,v_ns_{n+k})\\ &= \gcd(r_n,v_ns_{n+k}\pmod{r_n})\\ &= \gcd(r_n,t_k)\\ w_nt_n &\equiv 1 \equiv r_0 \pmod{s_n}\\ w_nt_{n+1} &=w_n(2t_n+s_n)\equiv 2\equiv r_1 \pmod{s_n}\\ w_nt_{n+k} &= w_n(4t_{n+k-1}-t_{n+k-2}) \equiv 4r_{k-1}-r_{k-2}\equiv r_k \pmod{s_n}\\ \gcd(t_{n+k},s_n) &=\gcd(w_nt_{n+k},s_n)\\ &= \gcd(w_nt_{n+k}\pmod{s_n},s_n)\\ &= \gcd(r_k,s_n)\\ z_ns_n &\equiv 1 \equiv r_0 \pmod{t_n}\\ z_ns_{n+1} &= z_n(3t_n+2s_n) \equiv 2 \equiv r_1 \pmod{t_n}\\ z_ns_{n+k} &= z_n(4s_{n+k-1}-s_{n+k-2}) \equiv 4r_{k-1}-r_{k-2} \equiv r_k\pmod{t_n}\\ \gcd(t_n,s_{n+k}) &= \gcd(t_n,z_ns_{n+k})\\ &= \gcd(t_n,z_ns_{n+k}\pmod{t_n})\\ &= \gcd(t_n,r_k)\\ f_nt_n &\equiv 1 \equiv s_0\pmod{r_n}\\ f_nt_{n+1} &= f_n(5t_n-2r_n)\equiv 5 \equiv s_1\pmod{r_n}\\ f_nt_{n+k} &= f_n(4t_{n+k-1}-t_{n+k-2}) \equiv 4s_{k-1}-s_{k-2}\equiv s_k \pmod{r_n}\\ \gcd(t_{n+k},r_n) &= \gcd(f_nt_{n+k},r_n)\\ &= \gcd(f_nt_{n+k}\pmod{r_n},r_n)\\ &= \gcd(s_k,r_n)\\ g_nr_n &\equiv 1 \pmod{t_n}\\ g_nr_{n+1} &=g_n(3t_n-r_n) \equiv -1 \equiv -s_0\pmod{t_n}\\ g_nr_{n+1+1} &=g_n(4r_{n+1}-r_n)\equiv -4-1\equiv -s_1 \pmod{t_n}\\ g_nr_{n+1+k} &= g_n(4r_{n+k}-r_{n+k-1}) \equiv -4s_{k-1}+s_{k-2}\equiv -s_k \pmod{t_n}\\ \gcd(t_n,r_{n+1+k}) &= \gcd(t_n,g_nr_{n+1+k})\\ &= \gcd(t_n,g_nr_{n+1+k}\pmod{t_n})\\ &= \gcd(t_n,-s_k)\\ &= \gcd(t_n,s_k) \end{align*} $$

B. Parcial de clasificación a través de la reciprocidad cuadrática
A partir de la OEIS enlaces (o tal vez comprobada directamente a través de la inducción), tenemos $$ \begin{align*} (r_n) &\subseteq \{x : x^2-3y^2=1\}\\ (s_n) &\subseteq \{x : 3y^2-x^2=2\}\\ (t_n) &\subseteq \{x : 3x^2-2 = y^2\} \end{align*} $$ Por lo tanto, los números primos $p$ $\mathbb R$ satisface $$ \begin{align*} -3y^2 &\equiv 1 \pmod p\\ -3 &\equiv (3y)^2 \pmod p \end{align*} $$ lo que significa que $-3$ es una ecuación cuadrática de residuos para $\mathbb R$. Se puede demostrar que esto es posible si y sólo si $p\equiv 1\pmod 3$, por ejemplo aquí. (Aunque no una prueba.)

Del mismo modo primos $p$ $\mathbb S$ y los primos $q$ $\mathbb T$ satisfacer $$ \begin{align*} 3y^2 &\equiv 2 \pmod p & -2&\equiv y^2 \pmod q\\ 6 &\equiv (3y)^2 \pmod p \end{align*} $$ Por lo tanto $6$ $-2$ son residuos cuadráticos para $\mathbb {S,T}$ respectivamente. Desde el enlace de Wikipedia de nuevo, tenemos $p\equiv 1, 5, 19, 23\pmod{24}$$q\equiv 1,3 \pmod 8$.

La ampliación y la comprobación de los números primos $\pmod{24}$ usando las 3 reglas, obtenemos: $$ \begin{align*} \mathbb R&: p\equiv 7,13,1,19 \pmod{24}\\ \mathbb S&: p\equiv 5,23,1,19 \pmod{24}\\ \mathbb T&: p\equiv 11,17,1,19 \pmod{24} \end{align*} $$ Y, de hecho, la clase de $1\pmod{24}$ aparece en todas las clases por la inspección, aunque escriba $19$ no parece aparecen en $\mathbb R$.