Trees and loops hidden in Lucas-Lehmer test.

[Tony Reix]

Trees and loops hidden in Lucas-Lehmer test.

Hello,

This topic is about some new conjectures dealing with the Lucas-Lehmer test.

We all know the Lucas-Lehmer test:
[code:1] Sq(n+1) = Sq(n)^2 - 2 (mod Mq)
With q prime and Sq(0)=4 , Mq=2^q-1 is prime if Sq(n-2) is 0 [/code:1]
That means that Sq (for a given q) builds a series, starting from a first item x0.
If Mq is a Mersenne Prime, and if x0 is 4 or 10 or one of the other roots described in the "A new Mersenne conjecture: Lucas-Lehmer roots" topic of this forum, then this series finishes with the last element 0.
Since Sq(x) = Sq(-x), then in all this note each time we find a
negative number -x, we will replace it by x; and each time we find a number greater than 2^(q-1)-1, we will replace it by Mq - x . So we will only consider numbers between 0 and 2^(q-1)-1 .
So, after the last item 0, there is another item: 0^2-2=2 . And, since 2^2-2=2, 2 is the true final item of the Sq series (when the first element was a root, like 4;and when Mq is prime).
So, as an example, with q=5 and x0=4, Sq builds the following series:
[code:1]
4 --> 14 --> 8 --> 0 --> 2 --> 2
[/code:1]
But this series is not the unic one we can build by means of Sq.
If we use Sq with the first item x0 taking values from 0 up to 2^(q-1)-1 = 0...15 , then we can compute new series. And we can see that all these series (with Mq prime) build ONE tree (from the leaves to the root) and several (or many with large q) loops:
[code:1]
q=5:
loops:
1 --> 1
2 --> 2
3 --> 7 --> 15 --> 6 --> 3
12 --> 13 --> 12

tree:
10 --> 5 --> 8 --> 0 --> 2 --> 2
11 --> 5 --> 8 --> 0 --> 2
4 --> 14 --> 8 --> 0 --> 2
9 --> 14 --> 8 --> 0 --> 2
[/code:1]
A shorter way to display the tree is (each number is connected to the number on its right if any, or on the number on the right above if none : 4 --> 14 , 9 --> 14 and 14 --> 8 ) :
[code:1]
0 1 2
--------------------------------
10 5 8 0 2
11
4 14
9
[/code:1]
The tree has 2^(q-3) {4 with q=5} roots, like 4, 10, ...
And the last number before 0 is 2^((q+1)/2) {8 for q=5}.
There are some special numbers, like 2^((q-1)/2) for q>=7 {8 for q=7}.
For 2^(q-1)-3 {13 for q=5} -which is always connected to 3.2^((q-1)/2) {12 for q=5}- the sum of all other numbers in its loop is equal to it minus 1.
q=7 : 24+36=61-1 .
That's true even for q=11 .

For q=7, the tree is:
[code:1]
0 1 2 3 4
----------------------------------------
10 29 50 42 16 0 2
44
18 59
51
4 14 60
49
21 58
43
37 30 9 48
63
38 45
46
3 7 47
54
27 35
52
[/code:1]
The loops are (not including the 1 --> 1 and 2 --> 2 loops):
[code:1]
5 23 19 22 26 39 5
6 34 11 8 62 32 6
12 15 31 57 55 25 12
17 33 56 41 28 20 17
13 40 53 13
24 61 36 24
[/code:1]
Since, for each loop, it takes n computations of Sq for looping back to the first value, we call them n-loops. (It's the number of different items in the loop).

For q=5, there are 1 2-loop and 1 4-loop.
For q=7, there are 2 3-loops and 4 6-loops.
For q=13, there are 1 2-loop, 2 3-loops, 1 4-loops, 9 6-loops, and 165 12-loops.
For q=17, there are 1 2-loop, 3 4-loops, 30 8-loops, and 2032 16-loops.
This seems to be connected to the following facts:
[code:1]
5=4+1=2*2+1
7=6+1=2*3+1
13=12+1=2*6+1=4*3+1
17=16+1=2*8+1
[/code:1]
But q=7 has no 2-loop ?!
(I remember this (N=pq+1) is a way for testing the primality of numbers, but I can't remember its name.)

And what about q=11 ?
There are 2 2-loops, 2 3-loops, 2 4-loops, 9 5-loops, 1 10-loop, 2 12-loops, 1 15-loop, 1 20-loop, and 1 60-loop.
Since 11=2*5+1 , why are there 3-loops and 4-loops. And why this so big 60-loop ?
M11 is not a prime.
(About tree(s) with q=11, I haven't yet any result. Some specific program must be written).
About the 2 2-loops: (277 --> 988 and 366 ---> 899), we have:
366-277=988-899=89
and we know that M11=23*89 . Strange ...
About the 2 3-loops, and the 2 4-loops, if we substract between the 2 x-loops, we also get 89.
It's seems 89 doesn't appear by chance.

The trees have another property, described hereafter.

If we multiply all numbers having the same rank (the number on the top of the tree), we get the same number that the one appearing before 0:
(q=7) 42*48=60*50*47*9=....=16 (mod 127)
If we multiply the 2 numbers producing the same number A, then we get the number B that produces the same number as A does:
(q=5)
[code:1]
4* 9= 5 (mod 31)
10*11=14 (mod 31)
[/code:1]
(That explains the previous result.)


As a conclusion, does all this stuff help for factorizing Mersenne numbers ? and does it help for proving their primality ? No. And there is no proof that there is a tree for all Mersenne primes. That' only experiments with some VERY SMALL values of q ! And maybe it can be proven by means of already well-known theorems.

Was it fun to study all that ? Yes !

I hope someone could prove some of the above conjectures, or check with other q, or connect them with some already known results about Mersenne numbers.
I also hope there are more mystery and tresors to be found. Just for fun!

(Since I only used some white papers and pen, shell and awk programs, and my pocket computer, I guess one can find more with more mathematical tools.)

If you want the trees for q=13, 17, 19 , just ask.

Tony
Carpe diem.

[wsc812]

GraphPlot[Table[i->Mod[2*i^2-1,Mq],{i,Mq}]]

[R.D. Silverman]

Originally Posted by Tony Reix

<numerology deleted by me>

As a conclusion, does all this stuff help for factorizing Mersenne numbers ? and does it help for proving their primality ? No. And there is no proof that there is a tree for all Mersenne primes. That' only experiments with some VERY SMALL values of q ! And maybe it can be proven by means of already well-known theorems.

Was it fun to study all that ? Yes !

I hope someone could prove some of the above conjectures, or check with other q, or connect them with some already known results about Mersenne numbers.

The place to start would by by deleting and ignoring all of the numerical
stuff and using some mathematics. In particular, GROUP THEORY.
You will neither prove nor confirm any conjectures via numerical examples.
[However: you might disprove them]

Start by understanding how these prime proving algorithms work in
general. They work (basically) by showing that the sub-group structure
in the group over which you are working has a sub-group that is too big
for the candidate to be composite.

For LL tests, the group in which you are working is the twisted sub-group
of order P+1 in GF(P^2). Any hope of proving your conjectures [if they
are true] lies in analyzing the sub-group structure. You will need an
expert in group theory [which I am definitely NOT] for this.

[ATH]

This is an old post from 2002 that recently got bumped. I think this is what later turned into the Vrba-Reix algorithm ?