Does anyone know "why" LL testing works?

[T.Rex]

Hi,
This thread of discussion is very interesting, and I'm sorry to have been so busy re-installing my PC at that time.

Moloch, I've been at your place some years ago: I was not able to understand why LLT works so well, though I received a good education in Maths before I got my Engineer diploma. But I learnt nothing about Number Theory at that time (26 years ago).
The answers you got in this thread talk about "group theory", "finite fields", and many other stuff. This stuff is not useful.
I spent several years trying to understand why LLT works. It's clear now.

First, many mathematicians now have forgotten the early period when Edouard Lucas (end of XIX) discovered that one can prove a number is prime or not without searching his divisors.
At that time, there were no "group theory" and other modern Maths stuff.

Edouard Lucas, in fact, was not a "true" Mathematician: He did not provide all the proofs that were needed. If he thought that something was clear/evident, he gave some sort of proof for A ==> B but not for B ==> A, and then he said it's a theorem (A <==> B). Derrick Lehmer then gave complete proofs plus new stuff.

If you want to learn how it can be proven, read the chapter 2 of the "Little Book for Greater Primes" of Paulo Ribenboim. You can get it for free at:Springer.
But don't believe him totally. He's wrong about the limits of several theorems he gives. They also can be used for numbers like Fermat numbers, not only for Mersenne numbers.
If you have a good library near your home, read also the book of Williams: "Edouard Lucas and Primality proving". It's a Great book, but difficult (I understand a very small part of it).
But don't read the "Hardy and Wright". It really does not help.
According to your math level, understanding the method underneaf the LLT could take months or years ... but it's worth to do it.

Reading these books, you can easily see that no "group theory" is needed.
The Mathematicians now using "group theory" for proving LLT do not know that they loose a big part of the power of Lucas/Lehmer method. On the web, many of the proofs given for the LLT are so specialized that they can ONLY be used for LLT. So they are of very little use for understanding the nice method discovered by Lucas and improved by Lehmer.

Then you could have a look at 2 tries I did for re-inventing the wheel about Fermat numbers:
First Wheel
Second wheel
So you can see that LLT method can be used for Fermat numbers. A fact that is not known by many Number Theory experts.

Though this looks very difficult, it is very simple for many people.

Many people that are giving you explanations in this thread like to talk about things they perfectly know. But they don't like exploring unclear or unproven fields, like the one I proposed in the paper:A primality test for Fermat numbers. Nobody seems to have studied my paper, though Edouard Lucas found quite the same theorem. Or maybe the paper is wrong or very bad. Is it wrong, Mister Silverman ?

Though I now understand quite well the theory underneaf the LLT, I still don't understand how it can be computed so quickly, by means of specialized FFT (Fast Fourier Transform). It's too complex for me and I never found a book (several books in fact) explaining all the steps required for understanding the technic used. Some day maybe. People in this forum provided very good explanations of general theory under FFT, but much more is needed. A book would be very useful !

I think some day I'll put on my web site all the documents I've found about Lucas work. But they are all in French, except one.
Who is interested ?

Have a good day.

Tony
Carpe Diem

[cheesehead]

Originally Posted by T.Rex

The answers you got in this thread talk about "group theory", "finite fields", and many other stuff. This stuff is not useful.

Maybe you don't have uses for them, but others do.

First, many mathematicians now have forgotten the early period when Edouard Lucas (end of XIX) discovered that one can prove a number is prime or not without searching his divisors.
At that time, there were no "group theory" and other modern Maths stuff.

Group theory was still in its early development during Lucas's lifetime. Now that there exists a more complete and systematic understanding of the properties of groups, plus many powerful theorems, than was available to Lucas, why not take advantage of that?

According to your math level, understanding the method underneaf the LLT could take months or years ... but it's worth to do it.

A couple of weeks may be all that's needed to learn enough group theory to understand Silverman's explanation. Why go the long way?

Reading these books, you can easily see that no "group theory" is needed.

Before automobiles were invented, one could easily travel 10 miles on foot or horse. Autos aren't needed for such a distance. But use of the auto may be faster and more convenient than traveling by foot or horse.

The Mathematicians now using "group theory" for proving LLT do not know that they loose a big part of the power of Lucas/Lehmer method.

Maybe what they do know is that group theory (why put it in quotes?) is a powerful mathematical tool applicable to a wide variety of mathematical problems, not just the Lucas-Lehmer test.

One might find that the proof of part of Lucas's method (by Lehmer's time, more group theory was available) actually corresponds to certain theorems of group theory, except that it's not as general.

I think some day I'll put on my web site all the documents I've found about Lucas work. But they are all in French, except one.
Who is interested ?

I am. But my high-school French is so rusty I'll probably use one of those Web translators.

[T.Rex]

Originally Posted by cheesehead

Maybe you don't have uses for them, but others do.

Group theory was still in its early development during Lucas's lifetime. Now that there exists a more complete and systematic understanding of the properties of groups, plus many powerful theorems, than was available to Lucas, why not take advantage of that ?

I'm not an expert. Nevertheless, I've found several recent papers on the web that are still using the theory elaborated by Lucas and Lehmer. So it seems still useful.

By the way, the Book of HC Williams about E. Lucas has only 4 or 5 pages about the thesis of D. Lehmer. I would be very pleased to be able to read it.
Does someone knows where it can be found (on the web) ?

A couple of weeks may be all that's needed to learn enough group theory to understand Silverman's explanation. Why go the long way ?

Because I think there are other interesting things to find with these tools. Most of people are using the new tools, so they are not aware that LLT may be used for other numbers than Mersenne numbers or N-1 numbers.

Before automobiles were invented, one could easily travel 10 miles on foot or horse. Autos aren't needed for such a distance. But use of the auto may be faster and more convenient than traveling by foot or horse.

Using automobiles does not enable you to discover the wonderful world leaving in the grass. Walking does. Using different tools enables to see differents things or same things but differently.

Maybe what they do know is that group theory (why put it in quotes?) is a powerful mathematical tool applicable to a wide variety of mathematical problems, not just the Lucas-Lehmer test.

You're right. But, the first time I tried to understand the LLT, I read a proof provided by http://www.utm.edu/research/primes , I think. It was really badly explained. Very short. Boring. But it is a general complain I have against Maths: most of the books provide the shortest possible proof, rather than explaining the long and difficult way used by the first discoverers. (I put group theory inside quotes in order to "group" the 2 words, so that it is more readable.)

One might find that the proof of part of Lucas's method (by Lehmer's time, more group theory was available) actually corresponds to certain theorems of group theory, except that it's not as general.

It is a question: does group theory enables to provide all the primality theorems appearing in Ribenboim's book ?

I learnt group theory at school, long time ago. And I forgot many things. I think I prefer the maths used by Lehmer and Lucas because they enable "amateurs" like me to play with.

I am. But my high-school French is so rusty I'll probably use one of those Web translators.

I've collected all papers I've found about Lucas' work on my WebSite: Edouard Lucas . All of them were taken on official web-sites. It also contains a thesis devoted to E. Lucas work. It is all in French, and I think you cannot translate them since they are scanned images.

By the way, I've found the official web-site of Edouard Lucas: Edouard Lucas Site . It contains valuable information about Lucas. And there are a French and an English version !

Regards,
Tony

[cheesehead]

T.Rex,

I was responding to your disparagement of group theory and its use to explain L-L. I was defending group theory and its use to explain why L-L works. I was discussing why group theory was better than Lucas's work for the purpose of understanding the L-L method, not tearing down Lucas's work itself as it seemed you were treating group theory.

Originally Posted by T.Rex

Nevertheless, I've found several recent papers on the web that are still using the theory elaborated by Lucas and Lehmer. So it seems still useful.

Fine. I never said Lucas's work wasn't useful in other contexts.

Originally Posted by cheesehead

Why go the long way ?

Originally Posted by T.Rex

Because I think there are other interesting things to find with these tools.

But I was asking about your advocating avoidance of group theory in understanding L-L, not about other contexts. So, again, why should someone go the long way while learning why the L-L method works?

Originally Posted by T.Rex

Using automobiles does not enable you to discover the wonderful world leaving in the grass. Walking does. Using different tools enables to see differents things or same things but differently.

Again, you're changing the subject, from study of the L-L method to mathematics in general. Do you question that my analogy about automobiles is valid in the context in which I intended it?

Originally Posted by T.Rex

But it is a general complain I have against Maths: most of the books provide the shortest possible proof, rather than explaining the long and difficult way used by the first discoverers.

So, what you want is an exposition on the history of the quest for the results to be included in every math book, not just the results? Come on, be reasonable. Some books are not intended to cover math history; don't criticize them for not being in your preferred catagory. Instead, stick to the books that include math history and leave the others alone to fulfill their authors' and readers' goals.