8
$\begingroup$

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 .

$\endgroup$
1
  • $\begingroup$ At a least show a few of your attempts $\endgroup$ Aug 16 '15 at 17:04
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I know this isn't really an answer, but simplifying p_2(x) in a comment would have resulted in a big mess. $\endgroup$
    – Mastrem
    Aug 19 '15 at 12:32
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Hi Tony . Thanks for reference . Here are some links to the papers you may find interesting : On a Compositeness Test for $(2^p+1)/3$ , PROBABLE PRIME TESTS FOR GENERALIZED MERSENNE NUMBERS , Primality tests for specific classes of $N=k \cdot 2^m \pm 1$ . $\endgroup$ Sep 2 '15 at 7:12
  • $\begingroup$ Hi. Thanks for the papers ! I'm sad to see that I do not appear in references of Berrizbeitia's paper and of Melham's paper Theorem (5.1), though I wrote my paper 3 years before first one and 1 year before second one. Anyway, your 4 conjectures here are fantastic. I tried to connect them with travelling over a cycle of the digraph, but that worked only for some of them. Anyway, your formulae look coherent and seem to show a generic property. I hope you will be able to prove the converse, and I suggest you to focus on the one dealing with Mersenne numbers, Conjecture2(1,1) which may be easier. $\endgroup$
    – Tony Reix
    Sep 3 '15 at 16:08
  • $\begingroup$ These 4 conjectures are much more generic than the theorems of 3rd paper in your list. They even could me more generic, by having only 2 conjectures. Note that $\lfloor c/2 \rfloor$ is $\frac{c-1}{2}$, and similar for ceil(). So, if you write: $N=k \cdot 2^n+s\cdot c ~$ with $~ s=\pm1$, then Conjectures 1 & 3 have: $S_{n-1} \equiv s \cdot P_{\frac{c+s}{2}}(6) \pmod{N}$ and Conjectures 2 & 4 have: $S_{n-1} \equiv P_{\frac{c-s}{2}}(6) \pmod{N}$ . That does not help for a proof, but that reduces the cases. $\endgroup$
    – Tony Reix
    Sep 3 '15 at 17:09
  • $\begingroup$ Thanks for advice ! Please see answer to this question $\endgroup$ Sep 4 '15 at 5:42
  • $\begingroup$ So, it looks that you have some proofs of the first part of some cases of these new 4 conjectures. Maybe you can find a general proof for each case. $\endgroup$
    – Tony Reix
    Sep 4 '15 at 7:34
1
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
1
-1
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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)))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.