Conjectured compositeness tests for $N=k \cdot 2^n \pm c$

Question

How to prove that these conjectures are true ?

Definition : $\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} .$

Conjecture 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}$$

Searching for counterexample (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)))
}

Conjecture 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}$$

Searching for counterexample (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)))
}

Conjecture 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}$$

Searching for counterexample (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)))
}

Conjecture 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}$$

Searching for counterexample (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)))
}

Any hint is appreciated .

Answer 1

First thing I would do is simplify $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$$

How did you come up with these conjectures? And why do you think they would work? Because,if we know that, it's way easier to prove them.

Answer 2

Your $P_m(x)$ is exactly the $C_n(x)$ that appears in H.C. Williams' book "Edouard Lucas and Primality Testing" page 77 and 78. But $C_n(x)$ is defined in a much simpler way: $C_0(x)=2$, $C_1(x)=x$, $C_{i+1}(x)= xC_i(x) - C_{i-1}(x)$.

If we consider the digraph under $x^2-2 \pmod N$, I think I remember that cycles are connected when using $C_3(x)$ (I mean to say that you jump from a cycle to another cycle by applying $C_3$ to a member of a cycle), to be checked.

Answer 3

About conjecture 2, with $k=1$ and $c=1$, $N=2^n-1$ is a Mersenne number (with q prime). Then: $S_0=P_1(6)=6$ and the final test is: $S_{n-1} \equiv P_1(6)=6$ . So, your conjecture is equivalent to say that N is prime iff we run a complete $n-1$ cycle of the digraph under $x^2-2 \pmod N$ starting with seed $S_0=6$ (and returning back to 6 after $n-1$ iterations). And this test is very close to a primality test conjecture I wrote for Mersenne numbers, where I used $S_0=3^2+\frac{1}{3^2}$ and also $q-1$ iterations. See: http://tony.reix.free.fr/Mersenne/ConjectureLLTCyclesMersenne.pdf .

Please note that I added another condition : $\prod_{1}^{q-1}S_i\equiv1 \pmod N$. This condition also holds for you. Maybe this additional condition may help for proving the converse (if property(N) then N is prime).

Now, for conjecture 1, with $k=1$ and $c=3$, we have : $N=2^n-3$, and $S_0=P_1(6)=6$ and the final test is $S_{n-1}\equiv-P_1(6)=-6$ . However, if we say that $S_O=P_2(6)=34$ and the final test is $S_{n-1} \equiv S_0$, that changes nothing to your test but, again, the test consists to run through a complete cycle of length $n-1$, starting from 34 and ending in 34.

So, I'm asking myself if all your tests can be transformed in: 1) reach the beginning of a cycle: $S_0$ ; 2) run $n-1$ iterations ; 3) return back to the seed $S_0$. If yes, that would create a link with digraph theory, where there are binary trees and cycles. Running from a universal initial value ($4$ for LLT for Mersenne numbers) to $0$ means go through a branch of the big binary tree. Running from a universal initial value ($6$ in your case) back to it means go through a cycle of the digraph.

Answer 4

Your four conjectures are true.

First of all,$$\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}$$ where $p=\sqrt 2-1,q=\sqrt 2+1$ with $pq=1$.

Since $$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,$$ we can prove by induction that $$S_i=p^{2^{i+1}k}+q^{2^{i+1}k}$$

By the way, $$\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}$$ Also, $$\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}$$

Here, for $N\equiv\pm 1\pmod 8$, since $2^{\frac{N-1}{2}}\equiv 1\pmod N$, from $(1)(2)$, we can prove by induction that $$p^{N+2i-1}+q^{N+2i-1}\equiv p^{2i}+q^{2i}\pmod N\tag 3$$

For $N\equiv 3,5\pmod 8$, since $2^{\frac{N-1}{2}}\equiv -1\pmod N$, from $(1)(2)$, we can prove by induction that $$p^{N+2i-1}+q^{N+2i-1}\equiv -\left(p^{2i-2}+q^{2i-2}\right)\pmod N\tag 4$$

To prove $(3)(4)$, we can use $$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$$and $$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$$

(Note that $(3)(4)$ holds for every integer $i$ (not necessarily positive) because of $pq=1$.)

Conjecture 1 is true because from $(4)$ setting $c=2d-1$ gives $$\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}$$

Conjecture 2 is true because from $(3)$ setting $c=2d-1$ gives $$\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}$$

Conjecture 3 is true because from $(4)$ setting $c=2d-1$ gives $$\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}$$

Conjecture 4 is true because from $(3)$ setting $c=2d-1$ gives $$\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 5

This is not an answer, but this would not enter a comment. Here is a PARI/gp program that implements a unic formula that manages all 4 conjectures, showing that they are related and can be generalized into only one, showing that it looks to be a deep property. I've found no counter-example with the two verification loops provided after. You have found something deep, I think. However, it needs a proof now ! ;)

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)))

New conjecture summarizing the 4 conjectures:

$$\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}$$

Answer 6

Now that the conjecture has been proven, by a nice proof, I'm interested in the converse: if the number has the property, is it a prime ? Or: are there (many) pseudoprimes for the test ?

With program below (which requires that $S_i \ne S_{n-1} ~ \text{, for}~ i<n-1$, and with some search, I've found that, for $N= k*2^n + c ~ , c ~\text{odd} > 0$, it looks that there are pseudoprimes ONLY when $c \equiv 1 \pmod{8}$. For now, I've only found the following values for c : 1, 17, 25, 33, 41, 57, 73, 81, 89, 105, 129, 137, 145 .

Examples: 1*2^3+1 , 97*2^48+17 , 54*2^220+25 , 64*2^119+33 , 419*2^117+41 , 343*2^291+57 , 471*2^393+73 , 467*2^259+81 , 419*2^267+89 , 307*2^319+105 , 256*2^319+129 , 136*2^396+137 , 171*2^379+145

(k should be set as odd in CEk2c(), for sure.)

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

for(k=1,100,for(c=0,200,CEk2c(k,2*c+1,400)))