Pruebas de composición conjeturadas para $N=k \cdot 2^n \pm c$

Question

¿Cómo demostrar que estas conjeturas son ciertas?

Definición : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ~\text{are nonnegative integers} .$

Conjetura 1 : $ \text{Let} ~N=k\cdot 2^n-c ~\text{such that}~ n>2c , k>0 , c>0 ~\text{and}~ c\equiv 3,5 \pmod{8}$

$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$ $$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv -P_{\lfloor c/2 \rfloor}(6) \pmod{N}$$

Búsqueda de contraejemplo (Pari GP) :

CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n-c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==N-2*polchebyshev(floor(c/2),1,a/2)) && isprime(N),print(n)))
}

Conjetura 2 : $ \text{Let} ~N=k\cdot 2^n-c ~\text{such that}~ n>2c , k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$

$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$ $$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{\lceil c/2 \rceil}(6) \pmod{N}$$

Búsqueda de contraejemplo (Pari GP) :

CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n-c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==2*polchebyshev(ceil(c/2),1,a/2)) && isprime(N),print(n)))
}

Conjetura 3 : $ \text{Let} ~N=k\cdot 2^n+c ~\text{such that}~ n>2c , k>0 , c>0 ~\text{and}~ c\equiv 3,5 \pmod{8}$

$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$ $$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv -P_{\lceil c/2 \rceil}(6) \pmod{N}$$

Búsqueda de contraejemplo (Pari GP) :

CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n+c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==N-2*polchebyshev(ceil(c/2),1,a/2)) && isprime(N),print(n)))
}

Conjetura 4 : $ \text{Let} ~N=k\cdot 2^n+c ~\text{such that}~ n>2c , k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$

$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$ $$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{\lfloor c/2 \rfloor}(6) \pmod{N}$$

Búsqueda de contraejemplo (Pari GP) :

CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n+c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==2*polchebyshev(floor(c/2),1,a/2)) && isprime(N),print(n)))
}

Se agradece cualquier pista.

Answer 1

Lo primero que haría es simplificar $P_2(x)$ $$P_2(x)=\dfrac{(x-\sqrt{x^2-4})^2+(x+\sqrt{x^2-4})^2}{4}=\dfrac{x^2-2x\sqrt{x^2-4}+x^2-4+x^2+2\sqrt{x^2-4}+x^2-4}{4}=\dfrac{4x^2-8}{4}=x^2-2$$

¿Cómo ha llegado a estas conjeturas? ¿Y por qué crees que funcionarán? Porque, si lo sabemos, es mucho más fácil demostrarlas.

Answer 2

Sobre la conjetura 2, con $k=1$ y $c=1$ , $N=2^n-1$ es un número de Mersenne (con q primo). Entonces: $S_0=P_1(6)=6$ y la prueba final es: $S_{n-1} \equiv P_1(6)=6$ . Por lo tanto, su conjetura equivale a decir que N es primo si ejecutamos una $n-1$ ciclo del dígrafo bajo $x^2-2 \pmod N$ empezando por las semillas $S_0=6$ (y volviendo al 6 después de $n-1$ iteraciones). Y esta prueba está muy cerca de una conjetura de prueba de primalidad que escribí para los números de Mersenne, en la que utilicé $S_0=3^2+\frac{1}{3^2}$ y también $q-1$ iteraciones. Ver: http://tony.reix.free.fr/Mersenne/ConjectureLLTCyclesMersenne.pdf .

Tenga en cuenta que he añadido otra condición : $\prod_{1}^{q-1}S_i\equiv1 \pmod N$ . Esta condición también es válida para usted. Tal vez esta condición adicional pueda ayudar a demostrar lo contrario (si la propiedad(N) entonces N es primo).

Ahora, para la conjetura 1, con $k=1$ y $c=3$ tenemos : $N=2^n-3$ y $S_0=P_1(6)=6$ y la prueba final es $S_{n-1}\equiv-P_1(6)=-6$ . Sin embargo, si decimos que $S_O=P_2(6)=34$ y la prueba final es $S_{n-1} \equiv S_0$ , que no cambia nada a su prueba pero, de nuevo, la prueba consiste en correr a través de un ciclo completo de longitud $n-1$ empezando por el 34 y terminando en el 34.

Entonces, me pregunto si todas sus pruebas pueden transformarse en 1) llegar al inicio de un ciclo: $S_0$ ; 2) ejecutar $n-1$ iteraciones ; 3) volver a la semilla $S_0$ . Si es así, eso crearía un vínculo con la teoría de los digrafos, donde hay árboles binarios y ciclos. Partiendo de un valor inicial universal ( $4$ para el LLT de los números de Mersenne) a $0$ significa pasar por una rama del gran árbol binario. Partiendo de un valor inicial universal ( $6$ en tu caso) de vuelta a ella significa recorrer un ciclo del dígrafo.

Answer 3

Sus cuatro conjeturas son verdadero .

En primer lugar, $$\begin{align}S_0=P_k(6)&=2^{-k}\cdot \left(\left(6-4\sqrt{2}\right)^k+\left(6+4\sqrt{2}\right)^k\right)\\&=\left(3-2\sqrt 2\right)^k+\left(3+2\sqrt 2\right)^k\\&=(\sqrt 2-1)^{2k}+(\sqrt 2+1)^{2k}\\&=p^{2k}+q^{2k}\end{align}$$ donde $p=\sqrt 2-1,q=\sqrt 2+1$ con $pq=1$ .

Desde $$S_i=P_2(S_{i-1})=2^{-2}\cdot \left(\left(S_{i-1}-\sqrt{S_{i-1}^2-4}\right)^2+\left(S_{i-1}+\sqrt{S_{i-1}^2-4}\right)^2\right)=S_{i-1}^2-2,$$ podemos demostrar por inducción que $$S_i=p^{2^{i+1}k}+q^{2^{i+1}k}$$

Por cierto, $$\begin{align}p^{N+1}+q^{N+1}&=\sum_{i=0}^{N+1}\binom{N+1}{i}(\sqrt 2)^{i}\left((-1)^{N+1-i}+1\right)\\&=\sum_{j=0}^{(N+1)/2}\binom{N+1}{2j}2^{j+1}\\&\equiv 2+2^{(N+3)/2}\pmod N\\&\equiv 2+4\cdot 2^{\frac{N-1}{2}}\pmod N\tag1\end{align}$$ También, $$\begin{align}p^{N+3}+q^{N+3}&=\sum_{i=0}^{N+3}\binom{N+3}{i}(\sqrt 2)^{i}\left((-1)^{N+3-i}+1\right)\\&=\sum_{j=0}^{(N+3)/2}\binom{N+3}{2j}2^{j+1}\\&\equiv 2+\binom{N+3}{2}\cdot 2^2+\binom{N+3}{N+1}\cdot 2^{\frac{N+3}{2}}+2^{\frac{N+5}{2}}\pmod N\\&\equiv 14+12\cdot 2^{\frac{N-1}{2}}+8\cdot 2^{\frac{N-1}{2}}\pmod N\tag2\end{align}$$

Aquí, para $N\equiv\pm 1\pmod 8$ ya que $2^{\frac{N-1}{2}}\equiv 1\pmod N$ , de $(1)(2)$ podemos demostrar por inducción que $$p^{N+2i-1}+q^{N+2i-1}\equiv p^{2i}+q^{2i}\pmod N\tag 3$$

Para $N\equiv 3,5\pmod 8$ ya que $2^{\frac{N-1}{2}}\equiv -1\pmod N$ , de $(1)(2)$ podemos demostrar por inducción que $$p^{N+2i-1}+q^{N+2i-1}\equiv -\left(p^{2i-2}+q^{2i-2}\right)\pmod N\tag 4$$

Para demostrar $(3)(4)$ podemos utilizar $$p^{N+2(i+1)-1}+q^{N+2(i+1)-1}\equiv \left(p^{N+2i-1}+q^{N+2i-1}\right)\left(p^2+q^2\right)-\left(p^{N+2(i-1)-1}+q^{N+2(i-1)-1}\right)\pmod N$$ y $$p^{N+2(i-1)-1}+q^{N+2(i-1)-1}\equiv \left(p^{N+2i-1}+q^{N+2i-1}\right)\left(p^{-2}+q^{-2}\right)-\left(p^{N+2(i+1)-1}+q^{N+2(i+1)-1}\right)\pmod N$$

(Tenga en cuenta que $(3)(4)$ se mantiene para cada entero $i$ (no necesariamente positiva) debido a $pq=1$ .)

La conjetura 1 es verdadero porque de $(4)$ ajuste $c=2d-1$ da $$\begin{align}S_{n-1}&=p^{N+c}+q^{N+c}\\&=p^{N+2d-1}+q^{N+2d-1}\\&\equiv -\left(p^{2d-2}+q^{2d-2}\right)\pmod N\\&\equiv -P_{d-1}(6)\pmod N\\&\equiv -P_{\lfloor c/2\rfloor}(6)\pmod N\end{align}$$

La conjetura 2 es verdadero porque de $(3)$ ajuste $c=2d-1$ da $$\begin{align}S_{n-1}&=p^{N+c}+q^{N+c}\\&=p^{N+2d-1}+q^{N+2d-1}\\&\equiv p^{2d}+q^{2d}\pmod N\\&\equiv P_{d}(6)\pmod N\\&\equiv P_{\lceil c/2\rceil}(6)\pmod N\end{align}$$

La conjetura 3 es verdadero porque de $(4)$ ajuste $c=2d-1$ da $$\begin{align}S_{n-1}&=p^{N-c}+q^{N-c}\\&=p^{N-2d+1}+q^{N-2d+1}\\&=p^{N+2(-d+1)-1}+q^{N+2(-d+1)-1}\\&\equiv -\left(p^{2(-d+1)-2}+q^{2(-d+1)-2}\right)\pmod N\\&\equiv -\left(p^{-2d}+q^{-2d}\right)\pmod N\\&\equiv -\left(q^{2d}+p^{2d}\right)\pmod N\\&\equiv -P_{d}(6)\pmod N\\&\equiv -P_{\lceil c/2\rceil}(6)\pmod N\end{align}$$

La conjetura 4 es verdadero porque de $(3)$ ajuste $c=2d-1$ da $$\begin{align}S_{n-1}&=p^{N-c}+q^{N-c}\\&=p^{N-2d+1}+q^{N-2d+1}\\&=p^{N+2(-d+1)-1}+q^{N+2(-d+1)-1}\\&\equiv p^{2(-d+1)}+q^{2(-d+1)}\pmod N\\&\equiv p^{-(2d-2)}+q^{-(2d-2)}\pmod N\\&\equiv q^{2d-2}+p^{2d-2}\pmod N\\&\equiv P_{d-1}(6)\pmod N\\&\equiv P_{\lfloor c/2\rfloor}(6)\pmod N\end{align}$$

Answer 4

Su $P_m(x)$ es exactamente el $C_n(x)$ que aparece en el libro de H.C. Williams "Edouard Lucas and Primality Testing" página 77 y 78. Pero $C_n(x)$ se define de forma mucho más sencilla: $C_0(x)=2$ , $C_1(x)=x$ , $C_{i+1}(x)= xC_i(x) - C_{i-1}(x)$ .

Si consideramos el dígrafo bajo $x^2-2 \pmod N$ Creo recordar que los ciclos se conectan cuando se utiliza $C_3(x)$ (Quiero decir que se salta de un ciclo a otro aplicando $C_3$ a un miembro de un ciclo), para ser comprobado.

Answer 5

Esto no es una respuesta, pero esto no entraría en un comentario. Aquí hay un programa PARI/gp que implementa una fórmula unica que maneja las 4 conjeturas, mostrando que están relacionadas y pueden ser generalizadas en una sola, mostrando que parece ser una propiedad profunda. No he encontrado ningún contraejemplo con los dos bucles de verificación proporcionados después. Creo que has encontrado algo profundo. Sin embargo, ¡necesita una prueba ahora! ;)

CEk2c(k,c,g)=
{
a=6;
if(c>0,s=1,s=-1;c=-c);
for(n=2*c+1,g,
N=k*2^n+s*c;
e=c%4;if(e!=1,e=-1);
d=((c-e)%8)/4;
A=(-1)^d;
B=(c-A*s)/2;
s0=Mod(2*polchebyshev(k,1,a/2),N);
sn=Mod(A*2*polchebyshev(B,1,a/2),N);
my(s=s0);
for(i=1,n-1,s=Mod(s^2-2,N));
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),100)))

Nueva conjetura que resume las 4 conjeturas:

$$\text{Let } ~N=k\cdot 2^n+ s \cdot c ~\text{ such that: }$$

$$ n>2c , k>0 , c>0 ~\text{ and }~ s = \pm 1 ~\text{ and }~ c \equiv 4 \cdot d ~ \pm 1 \pmod 8 ~\text{ and }~ d=0,1$$

$$\text{Let }~ S_i \equiv P_2(S_{i-1}) \pmod{N} ~ \text{ with } ~ S_0=P_k(6) ~ \text{ , thus: }$$

$$\text{If } ~ N ~\text{ is prime then }~ S_{n-1} \equiv {(-1)}^d \cdot P_{(c - {(-1)^d \cdot s})/2} ~ (6) \pmod{N}$$