LLT numbers

T.Rex

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

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

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

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

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

T.

CRGreathouse

Induction?

Hurkyl

If that pattern of alternating signs keeps up, oberve that

[tex]
C_m^+ = \frac{L^m(i) + L^m(1)}{2}
[/tex]

T.Rex

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

T.Rex

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

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

T.

T.Rex

Can you prove:

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

T.

Playdo

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,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 learnt 30 years ago plus the Number Theory I've learnt these last years come back and I try to find the proof.
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:
Generalized Pell Numbers: Zhi-Wei SUN helped me.
New properties of Mersenne numbers: an anonymous reviewer provided a nice proof.
Cycles under the LLT modulo a Mersenne prime: 2 guys helped me, including ZetaX from this forum.
Regards,
Tony

T.Rex

I think I have an idea.
It appears that we have: [tex]L^m(i) = V_{2^m}(1,-1)[/tex], where i is the square root of -1, m is greater than 1, and [tex]V_n(1,-1)[/tex] is a Lucas number defined by: [tex]V_0=2 , V_1=1, V_{n+1}=V_n+V_{n-1}[/tex]. Look at "The Little Book of BIGGER primes" by Paulo Ribenboim, 2nd edition, page 59.
So, what I called LLT numbers are: [tex]C_m^+ = \frac{V_{2^m}-1}{2}[/tex].
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

Yes: [tex]V_{2n}=V_n^2-2Q^n[/tex].
When n is even and Q=-1 or 1, we have: [tex]V_{2^n}=V_{2^{n-1}}^2-2[/tex] 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 [itex]U_m, U_{m+1}, V_m, V_{m+1}[/itex], you can leap directly to [itex]U_{2m}, U_{2m+1}, V_{2m}, V_{2m+1}[/itex]. 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!