Re: U-Tetration-matrix and iterated mersenne-primes (applic. to Lucas-Lehmer-test) /corrected repost

Hmm, I was missing some references and examples in my previous post.
Instead of editing line-by-line I'm resending an extended version to
make a more self-contained msg here.

=====================================================================

Am 14.01.2009 22:33 schrieb Gottfried Helms:

It was stated, that for p=13 this does not hold; at some h is M°h_13
not (a Mersenne-)prime, but for p=2 (and subsequently p=3,7,127)
this holds and is not known, whether it holds for higher iterations
h.
V(2)~ * Ut = V(3) ~ // 3 = M_2 is prime
V(2)~ * Ut^2 = V(7) ~ // 7 = M_3 is prime
V(2)~ * Ut^3 = V(127) ~ // 127 = M_7 is prime
V(2)~ * Ut^4 = V(M_127) ~ // M_127 is prime
... // prime ???



Well, may be there is indeed some information in this all,
worth to investigate it in more detail and generality.

What I fiddled with was the application of the Lucas-Lehmer-
test for Mersenne-primes in this matrix-framework.

In my other post (see *1 below) I introduced the matrix-operator G for
the implementation of the function g(z) which replaces
the "Lucas-Lehmer-function" f(x) = x^2 - 2 by a (invertible)
function without constant term

g(z) = z^2 + 4z

with the identity

f(x) = g(z-2) + 2

which holds also for iterates

f(f(x)) = g(g(z-2))+2

and allows to perform the Lucas-Lehmer-test using g(2)
instead of f(4) appropriately iterated depending on the
prime being tested.

The iteration of the function g(2) is expressible by powers
of the associated matrix-operator G. For the test of a prime
p I need p-2 iterations of f(4) or g(2) , or the matrix-
product V(2)~* G^(p-2)=V(y)~ and then a test of the result
y+2 (modulo 2^p-1)

Here the significant entries in G^(p-2) reach up to row
2^(p-2), so for p=5 I test, whether with
V(2)~*G^3 = V(y)~
test: 0 == y+2 (mod 31)
the result "test" is true, using G only up to the indicated row
which is 2^3 = 8.




Now heuristically it seems, that I can assume

G^p == G (mod 2^p-1) // for a certain top-left-segment

up to the rownumber of significant entries in the second
column in G^p, and thus it seems I can use G^-2 for the
Lucas-Lehmer-test for all primes p if indeed

G^-2 == G^(p-2) (mod 2^p-1)

in the relevant truncated size.



In scalar notation, I can use

g°(-2) (2) (mod 2^p -1 )

where I need the powerseries of g°-2(x) only up to the
"significant" exponent 2^(p-2), and g°(-2)(x) can be
determined by series-reversion.

g(x) = x^2 + 4x
g°-1(x) = sqrt(x+4) - 2

The powerseries of g°-1(x) begins with

g°-1(x) = 0 + 1/4*x - 1/64*x^2 + 1/512*x^3 - 5/16384*x^4 + 7/131072*x^5 - 8/798915*x^6 + 1/508400*x^7 - ...

and of g°-2(x)

g°-2(x) = 0 + 1/16*x - 5/1024*x^2 + 21/32768*x^3 - 74/723493*x^4 + 11/607320*x^5 - 1/292244*x^6 + 1/1000000*x^7 - ...

and of g°-2(2)
g°-2(2) = 0 + 1/2^3 - 5/2^8 + 21/2^12 - 429/2^18 + 217/374399 - ...


-------------------------------------

The problem is, that the series inversion needs 2^(p-2) terms
if p shall be tested. This is practical only for relatively
small primes p. So this is still not a full replacement
of the LL test.

On the other hand: the interesting thing is, that

G^-2 (or g°(-2)(2) )

is then (if all this actually holds) one constant for LL-tests
of all primes p, and the problem of required number of iterations
of g(2) (or f(4)) is translated into a problem of summing a
powerseries (modulo 2^p -1) up to a certain index.

Besides its practical limitation I find this an interesting aspect
of the LL-test... I'll be checking later how far I can heuristically
go with this.

Gottfried

--------------------

(*1) see my other post "Re: prime numbers formula please."
(...)
The lucas-Lehmer test employs a recursion x_k+1 = (x_k)^2 - 2.
so we have a function f(x) = x^2 - 2 iteratively applied, beginning
at x0 = 4.

The function f(x) can be replaced by

g(z) = z^2 + 4z

without constant term and fixpoint-shift

f(x) = g(x-2) + 2
f(f(x)) = g(g(x-2)) + 2
f°h(x) = g°h(x-2) + 2 // where "f°h" means h recursive iterations of f


So, regarding the application for Lucas-Lehmer we have for any n

f°n(4) = g°n(2)+2

and
if g°(p-2)(2) == 0 (mod 2^p -1)
then 2^p -1 is a Mersenne-prime Mp

The function g(x) can be implemented as a triangular matrix-operator G, of
which we can then use the powers G^h for iterations in the same spirit
as the msg at (<the first article>).
(...)


.

Relevant Pages