B.D: Proving C_m^+ in Lucas-Lehmer Test (LLT)

[T.Rex]

Let's say: L(x)=x^2-2 , L^1 = L, L^m = L \circ L^{m-1} = L \circ L \circ L \ldots \circ L.
Where L(x) is the polynomial used in the Lucas-Lehmer Test (LLT) :
S_0=4 \ , \ S_{i+1}=S_i^2-2=L(S_i) \ ; \ M_q \text{ is prime } \Longleftrightarrow \ S_{q-2} \equiv 0 modulo M_q .

We have:
L^2(x)=x^4-4x^2+2
L^3(x)=x^8-8x^6+20x^4-16x^2+2
L^4(x)=x^{16}-16x^{14}+104x^{12}-352x^{10}+660x^8-672x^6+336x^4-64x^2+2

Let's call C_m^+ the sum of the positive coefficients of the polynomial L^m(x).
We call C_m^+ a "LLT number": C_1^+ = 1 , C_2^+ = 3 , \ C_3^+ = 23 , \ C_4^+ = 1103 , \ C_5^+ = 2435423 .

It seems that we have the formula: C_m^+ = 2^m \prod_{i=1}^{m-1} C_{i}^+ - 1 \ \ \text{ for: } m>1.

How to prove it ? (I have no idea ...)

T.

 

[CRGreathouse]

How to prove it ? (I have no idea ...)

T.

Induction?

 

[Hurkyl]

If that pattern of alternating signs keeps up, oberve that

<br /> C_m^+ = \frac{L^m(i) + L^m(1)}{2}<br />

 

[T.Rex]

Got it !

OK. I've got a proof. Thanks for the hints! Not so difficult once you think using "i" !
T.

 

[T.Rex]

LLT numbers and Fermat primes

Now, more difficult, I think.
Can you prove:

\prod_{i=1}^{2^n-1}C_i^{+} \equiv 1 \pmod{F_n}\ \ iff \ \ F_n=2^{2^n}+1 is prime.

T.

 

[T.Rex]

Better, simpler

Can you prove:

C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}.

T.

 

[Playdo]

Can you prove:

C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}.

T.

If it has already been proven then why ask us? If not, do you intend to include our names in the published paper as sources of help?

 

[T.Rex]

Hello,

If it has already been proven then why ask us ?

I'm an amateur: I play with numbers and try to find nice/interesting properties about nice numbers. I have no proof of this one. I like the way Hurkyl did: he gave an hint and then some of the Maths I learned 30 years ago plus the Number Theory I've learned these last years come back and I try to find the proof.

If not, do you intend to include our names in the published paper as sources of help?

Sure. Last year I asked questions in this forum and got answers and proofs and I wrote a paper where I said who helped me. If I write a paper about the LLT numbers, I'll talk about people who helped me. About a "published" paper, my only candidate target is arXiv.org . So, do not dream about being published in a famous journal. My main goal is fun.
As examples, look at:
http://tony.reix.free.fr/Mersenne/GeneralizedPellNumbers.pdf" : Zhi-Wei SUN helped me.
http://tony.reix.free.fr/Mersenne/Mersenne8x3qy.pdf" : an anonymous reviewer provided a nice proof.
http://tony.reix.free.fr/Mersenne/LoopsUnderLLTmodMersennePrime.pdf" : 2 guys helped me, including ZetaX from this forum.
Regards,
Tony

 

[T.Rex]

Lucas numbers

Can you prove:

C_{2^n}^{+} \equiv -2 \pmod{F_n} \ \Longleftrightarrow \ F_n=2^{2^n}+1 \text{ is prime.}.

T.

I think I have an idea.
It appears that we have: L^m(i) = V_{2^m}(1,-1), where i is the square root of -1, m is greater than 1, and V_n(1,-1) is a Lucas number defined by: V_0=2 , V_1=1, V_{n+1}=V_n+V_{n-1}. Look at "The Little Book of BIGGER primes" by Paulo Ribenboim, 2nd edition, page 59.
So, what I called LLT numbers are: C_m^+ = \frac{V_{2^m}-1}{2}.
I did not know this relationship.
Now, in order to prove the theorem, I think I could use either the method used by Lehmer or the one used by Ribenboim. I'll see.
Any more ideas ?
Regards,
Tony

 

[Hurkyl]

There's a U sequence too, I think. There's a nice formula not just for increasing the indices by 1, but also for doubling the indices.

 

[T.Rex]

... but also for doubling the indices.

Yes: V_{2n}=V_n^2-2Q^n.
When n is even and Q=-1 or 1, we have: V_{2^n}=V_{2^{n-1}}^2-2 which is the LLT basic formula.
Have I found something useful or is it simply another way to look at an old result ? (Probably second one !)
T.

 

[Hurkyl]

IIRC, there's a more general one. If you know U_m, U_{m+1}, V_m, V_{m+1}, you can leap directly to U_{2m}, U_{2m+1}, V_{2m}, V_{2m+1}. I don't remember the details; I just wanted to throw it out there, in case the idea was useful. The U and V sequences have a ton of useful properties!