Chebytchev
 

Let's have: [tex]C_0(x)=2 \ , \ C_1(x)=x \ , \ C_{n+1}(x)=x C_n(x)-C_{n-1} [/tex] .

We know:[tex]V_{n+1} = P V_n - Q V_{n-1}[/tex] which is the second Lucas function.

And we see that: [tex]C_n(x)=V_n [/tex] with [tex]P=x \ , \ Q=1[/tex].

[tex]C_2(x) = x^2-2[/tex] is the LLT function.

Now, with: [tex]C_3(x) = x^3-3x[/tex], let say: [tex]A_0=4[/tex], and [tex]A_{i+1}=C_3(A_i) \ \pmod{2^q-1}[/tex].

Then [tex]A_i[/tex] generates all the possible initial values of the LLT for a given q.

As an example, with [tex]q=5[/tex], we build the series: A0= 4, 21, 22, 11, 27, 10, 9, 20, A8=A0=4 .
All these 8 values can be used as [tex]S_0[/tex] for the LLT test, leading to [tex]S_3 \equiv 0[/tex] .

Who can explain/prove why [tex]C3(x)[/tex] generates all the possible initial values of the LLT for a given q ?
I never found any explaination/proof.

Tony

Unclear ? Nuts ? Evident ? ....
 

Huum,
I got no answer after 2 days.
Is my question: Unclear ? Nuts ? Evident ? Stupid ? Incomplete ? Too Vague ? Not Useful nor Interesting ?
In his book "Edouard Lucas and Primality Testing", HC Williams talks about Cn(x). But not about this specific property of C3(x).
Who could help ?
Tony

Using the following program in UBASIC:

[code] 10 E=17
20 M=2^E-1
30 E=E-2
40 A=4
50 for I=1 to 2^E
60 A=(A*A*A-3*A)@M
70 B=A
80 for J=1 to E
90 B=(B*B-2)@M
100 next J
110 print A;"-";
120 if B<>0 then print "b is not zero!!!!":end
130 next I
140 end[/code]I tested for exponents E equal to 3, 5, 7, 13, 17 and 19. Your conjecture appears to works OK. Now somebody would have to prove if it actually works for all Mersenne prime exponents.

Tony,
I'm sorry I am not able to answer your actual question, but what I did notice (and you may have already noticed this yourself) is that the answers for q = 5 at least are arranged very symmetrically within the group. This may just be a coincidence, or another example of the law of small numbers, so I checked for q = 7 as well. Although the pattern is quite different, these are also arranged symmetrically within the group. The series starts (note that this is in numerical order, not the order in which they appear) {3, 4, 10, 18, 21, 27, ...} and finishes {..., 100, 106, 109, 117, 123, 124}, completely symmetrical. And I also noticed that in both cases the number of terms in the series is 2^q+1/4. Maybe that is just another coincidence.

The series must be symmetric because you have to square them [tex]e-2[/tex] times (where [tex]e[/tex] is the exponent of the Mersenne prime) in order to get the final value zero.

So if [tex]a[/tex] is a member of the group, the number [tex]b = 2^e-1-a[/tex] must also be a member, because [tex]a^2-2\eq \,b^2-2 \pmod {2^e-1}[/tex].

I think we are talking about different series (but I may be wrong). The series you are talking about is the one that goes:

s[sub]0[/sub] = 4, s[sub]1[/sub] = 4[sup]2[/sup]-2, s[sub]n+1[/sub] = s[sub]n[/sub][sup]2[/sup]-2.

These are the numbers that are generated in the course of calculating the LL number that is used to conduct a specific LL test. So that when testing 2[sup]p[/sup]-1 you will eventually end up with s[sub]p[/sub] = s[sub]p-1[/sub][sup]2[/sup]-2.

The series I was referring to is the one that goes:

a[sub]0[/sub] = 4, a[sub]1[/sub] = 4[sup]3[/sup] - 12, a[sub]n+1[/sub] = a[sub]n[/sub][sup]3[/sup] - 3a[sub]n[/sub].

This series can be used to generate different starting elements for the series starting s[sub]0[/sub] = 4, so that it can in fact start s[sub]0[/sub] = 21 if we like. In practice there doesn't appear to be any point in doing so because we only end up with an even bigger LL number against which to check our Mersenne prime, but we can do it if we want to.

Your second point also confuses me. It seems to me that if we are operating modulo some number m then our answers will always be elements of the group of residue classes modulo m. So proving that b is some element of the group strikes me as being pretty pointless (except in the sense that it proves that the answer exists). It must be in the group because we are doing modular arithmetic. But that doesn't explain why it should necessarily be symmetrical within the group.

What I meant by symmetrical within the group is that if we take q = 5 as an example, the series generates in this order the numbers 4, 21, 22, 11, 27, 10, 9, 20, 4. We see that 4 is the fourth element of the group and 27 is the fourth element counting from the other end of the group. But 27 is not generated immediately after 4 to preserve the symmetry. The symmetry is only apparent when the whole series has been generated.

But I will be the first to admit that I know very little about group theory, my maths course is currently in the discrete modelling stage and I have yet to reach group theory, so I could be wrong in everything I've said.

I should also point that when I said there were 2^q+1/4 terms in the series that was incorrect. It should in fact be 2[sup]q[/sup]/4.

Symmetry and opposites
 

Thanks "Numbers" to have looked at my question !
As said Alpertron, I forgot to remind readers that there are exactly [tex]2^{q-2}[/tex]roots (or also called "initial values") of the LLT for each [tex]M_q[/tex]. This is clearly known and proven. And, if [tex]a[/tex] is a root of LLT, then [tex]-a \ \bmod{M_q}[/tex] also is a root, thanks to the square in the LLT.
Notice also that: [tex]C_n(C_m(x)) = C_m(C_n(x))[/tex].

Since it can be easily proven (done in Mersenne forum) that the LLT test is equivalent to:
[tex]S_0=5 \ , \ S_{i}=2 S_{i-1}^2-1 \ \ ; \ \ M_q=2^q-1[/tex] is prime iff [tex]S_{q-2} \ \equiv \ 0 \ \pmod{M_q}[/tex].
And since: [tex]T_0(x)=1 \ , \ T_1(x)=x \ , \ T_{n+1}(x)=2T_n(x)-T_{n-1}(x)[/tex], which is the Chebyshev Polynomial of the First Kind, I think there is a clear link between the property I'm asking about and Chebyshev.
But which one ?

Tony

Initial values of LL-test have form
S(k) = (2+sqrt(3))^k + (2-sqrt(3))^k mod (2^q - 1),
where k is odd. For example, S(1)=4.
It is important to notice that S(k)=S(k mod 2^q) and S(k)=(2^q - k) meanning that to get all possible initial values k should go over all odd numbers from 1 to 2^(q-1) - 1. So there are 2^(q-2) distinct initial values.

It is easy to see that
C3(S(k)) = S(3k)
meanning that C3(x) transform initial value into another initial value.

It is also easy to see that 3 is a generator modulo 2^q meanning that
1, 3, 9, ..., 3^m, ...
generate all odd residues modulo 2^q and
S(1), S(3), S(9), ..., S(3^m), ...
generate all possible values S(k).
Moreover, there are no repeats in the interval m=0..2^(q-2)-1 so
S(1), S(3), S(9), ..., S(3^(2^(q-2)-1))
give all distinct initial values.

A small correction: [tex]S(k)\,\eq \,S(2^q - k)[/tex].

[QUOTE=alpertron]A small correction: [tex]S(k)\,\eq \,S(2^q - k)[/tex].[/QUOTE]
Oh, I missed "S". But there is no need in congruence since S(k) is defined modulo 2^q - 1. So it should be:
[i]It is important to notice that S(k)=S(k mod 2^q) and S(k)=S(2^q - k) meanning that to get all possible initial values k should go over all odd numbers from 1 to 2^(q-1) - 1.[/i]

C3(S(k)) = S(3k)
 

[QUOTE=maxal]It is easy to see that
C3(S(k)) = S(3k)
meanning that C3(x) transform initial value into another initial value..[/QUOTE] Oh yes. Now it is easy to see why it works.
Thanks!
Tony