The Størmer Problem (Lehmer's method etc) - Page 2

Jim White · 2007-09-02, 00:12

Quote:

Originally Posted by Jim White

... the $n$ -th term in any such sequence must have at least one prime divisor $\geq 2n - 1$

Lehmer's paper states this as Lemma 5:

If $n > 3$ , then $y_n$ is divisible by some prime $p \geq 2n-1$

You'll find his full proof there.

Empirical evidence suggests that Lehmer's effective bound, $n \leq max (3, {p+1 \over 2})$ , for which $y_n$ might remain $p$ -smooth, might in fact be further reduced, but this is not of major consequence for expected running times, as I mentioned earlier, and so is not yet fully investigated.

R. Gerbicz · 2007-09-02, 00:42

Quote:

Originally Posted by Jim White

So we can use known existing bounds, otherwise we'd need something like a bound produced by a lattice basis reduction algorithm.

One more question, Jim:
What exact upper bound is known?

Citrix · 2007-09-02, 02:37

Jim,

Out of curiosity.
The only application I can think of right now, is to study Pell equations and the largest possible solution for each D.
From what I understand, the prime values have the first solution as a large number, whereas smooth D values have smaller first solutions. But there has been no work done on the largest solution, if the first solution is known.
May be some pell equations have infinite solutions? Any thoughts?

Jim White · 2007-09-02, 03:53

Regarding Citrix's question, if all variables are strictly positive integers then we know $x^2 - Dy^2 = 1$ does always have an infinite number of solutions in positive integers.

Now, going the other way, we may also find a particular solution $(x', y')$ as a solution, even a fundamental solution, to more than one Pell equation

An example (based on a smooth pair):

$a = 195 = 3.5.13$
$a+1 = 196 = 2^2.7^2$

$2a+1 = 391$
$a(a+1) = 38220$

$391^2 - 195(2^2 * 7)^2 = 1$
$391^2 - 780(2*7)^2 = 1$
$391^2 - 3120(7)^2 = 1$
$391^2 - 9555(2^2)^2 = 1$
$391^2 - 38220.(2)^2= 1$

For each distinct square $y^2$ that divides $4a(a+1)$ , we have a corresponding $D$ whose Pell equation solutions must include $(2a+1, y)$ . In many such cases it can occur as a fundamental solution.

If we call any $D$ that produces $2a+1$ as a solution a producer of $a$ , then the Størmer/Lehmer schemes work by giving a scheme for constructing a finite set of $D$ which is guaranteed to include at least one producer of all target value $a$

Jim White · 2007-09-02, 05:14

Quote:

Originally Posted by R. Gerbicz

One more question, Jim:
What exact upper bound is known?

By existing known bounds I meant only those which are themselves already established, which, strictly speaking, is limited to those resulting from complete and accurate applications of Lehmer's method (or of Størmer's, but that's very much slower).

At the moment we have only two ways to confirm any individual bound (and for any given number of primes it must be individually computed). That's by either following Lehmer's recipe correctly, and completely, or by getting a provably correct (and usefully close) bound from above.

The latter can perhaps be obtained from "Bakersfield", the general area of Baker's Theorems regarding linear forms in logarithms used to approximate solutions to Diophantine equations. For $n$ primes there is an $n$ -dimensional integer lattice in which we can (theoretically) find a reduced basis that will yield a vector of "shortest height", from which we can derive such a bound. I think the tightness of the bound inevitably depends to some extent on how long you're prepared to wait, of course.

Our particular problem is not one that the Bakersfield mob have really thought much about, other than to observe in passing that it is theoretically applicable ... I am corresponding with somebody knowledgable in the area and hope to lerrn more

Meanwhile, Lehmer's results, meanwhile, which showed all 869 smooth pairs for the 13 primes up to 41, can be read as gospel, and are easily verified/reproduced.

The sequence of greatest values currently on show at OEIS is, presumably, also verified. Myself, I have only performed such a strictly correct enumeration for the 17 primes up to 59, for which the incremental run alone was starting to take hours (see above posts).

I assume the providers of the values for p to 97 have followed the recipe strictly, and have been able to devote sufficient time (and perhaps a more powerful machine) to the computation ...

... or they know something which I don't, but apparently should!

My figures for the primes beyond 97, which go up to p = 149 are not gospel, but are "almost certainly" correct. They can't yet be claimed correct, as they were performed by a "stripped-down" Lehmer method that does very much less work.

This method is new and as yet unsupported by a theorem, but I have high hopes that will come in due course.

I will describe this in a post soon, but meanwhile, those of you who have some form of working code for the Lehmer method can guess what I'm doing through a simple, but revealing, experiment:

When your program reports each smooth-pair index value, $a$ , have it also report the period length for the producer of $a$ , ie. the period length of the corresponding $\sqrt{D}$ .

It will be sufficient to run it just for the Lehmer example (p <= 41), where the periods for all equations involved range up to 16k or so, and the maximum period encountered for a producer is ... ??

A caveat is necessary - even if a firm analytical result in these terms is obtainable, all it gives us is another finite increment in the number of primes (say around 10) that might be "doable" in reasonable time. It opens a door, but only to a larger room, not to the open!

But there is cause for optimism in the nature of the periodicity properties which might well lead to an evantual escape from the tyrrany of running times exponential in terms of $n$ .

One suspects that some combinatorial-number-theoretical piece of the jigsaw is just there waiting to be found ...

... this could be intuitive, or perhaps one simply hopes (desperately enough)that it turns out to be the case!

Jim White · 2007-09-02, 05:55

Another thought regarding Citrix's question: if you take the fundamental solution (which is just that involving the smallest possible pair of integers x,y), you can then apply either of the recurrence formulae above to generate the infinite number of pairs that also satisfy the same equation.

This I think will be found to be just the same process that lets you generate an infinite family of related but distinct Pythagorean triplets from any one starting case ....

Each solution has common divisors with the fundamental one, in particular $y_1 | y_k$ always, and $D$ will always divide $x_k^2 - 1$ , but also the sequences are increasing, so they are picking up new divisors that were not in the original $D$ . Some of these become periodic, some do not. The solution number k in which a prime divisor first appears is called its "Index of Appearance" (or Apparition), and various Laws relating thereto are called "Laws of Apparition"

The prime divisors in any solution that do not divide $D$ are also called extrinsic, for obvious reasons

So Lehmer's bound on the range of multiple solutions that should be checked can most probably be tightened if expressed in the number of prime divisors of the solution in question, by comparison with the number of primes available (unused) that could possibly appear in solutions as extrinsic divisors ... well, I think so, anyway

But as I said, no complexity gain is likely to arise from a tightening of this particular bound. Multiple solutions are more probable when the $D$ are small - they indicate that there are "shortcuts" to some solutions that can be found by extrinsic-divisor-based solutions, which tend to be cheaper ... as we try to work with more and bigger primes, their current role diminishes accordingly

R. Gerbicz · 2007-09-02, 16:00

Quote:

Originally Posted by Jim White

On a 2GHz AMD64 (with GMP for MP-arithmetic where necessary), 17 primes (p \leq 59) takes about 4 hours using Lehmer's method, while the generative search method (armed with the known bound), gets there in just 20 seconds.

I've completed my own gmp program for the problem. You can download this from http://robert.gerbicz.googlepages.com/stormer.c
This program takes only 4 seconds for N=17 so p=59 on my slow computer ( 1.7 GHz Celeron ).
So probably it is faster than your program.
I've assumed for this that S'(p[N])<2^(3*N+1) is true ( p[1]=2,p[2]=3,p[3]=5... are the primes ). Note that this is true for the known solutions.

Jim White · 2007-09-03, 07:31

Thanks Robert. That sounds good, I'll have a good look at it ...

Jim White · 2007-09-03, 08:45

Very nice work, Robert. That certainly runs faster than my initial hack ... I'll make an updated version of that timing chart above with a plot for your program running times. I have spare suits - you can be diamonds!

A description of your approach would be welcome! Your smoothness testing, for example, looks interesting. Mine doesn't do any gcd calls, for a start!

Jim White · 2007-09-03, 10:03

(a little later)

I'm beginning to understand (and appreciate) it a little better now ... you've implemented a Bounded version of the Lehmer method?

If the bound is known, then the CF development process can take an early exit when the convergents get too big ...

We know that this will in fact be the case far more often than not, so the time saving over regular (unbounded) Lehmer method, is substantial ... all we need is a reasonably good bound ...

Now I see how it works, I will try an experiment with it!

Cheers

R. Gerbicz · 2007-09-03, 10:51

Quote:

Originally Posted by Jim White

A description of your approach would be welcome! Your smoothness testing, for example, looks interesting. Mine doesn't do any gcd calls, for a start!

First I generate the odd *squarefree* numbers of the Q' set.
In fact half of the numbers are divisible by p[N]^2, the other half of them are divisible by only p[N], the reason for this that we've to guarantee that a or a-1 is divisible by p[N].
There are 2^(N-1) such numbers, and after testing 2*D I'm testing 4*D, but only if D!=1, otherwise it is a square number, and the Pell equation is trivial. That part of the code is a little crazy, but not time critical, for example the following code do the same job, in almost the same time ( it isn't faster or slower by 1% ):

Code:

mpz_set_ui(D,2);
for(i=1;i<N-1;i++)  {
    if(J&1)  {
       mpz_mul_ui(D,D,primes[i]);
    }     
    J>>=1;
}

if(J&1)  {
    mpz_mul_ui(D,D,primes[N-1]);
}
else {
    mpz_mul_ui(D,D,primes[N-1]*primes[N-1]);
}

About testing smoothness: that's also not time critical. For example for N=17 there are only 1648 smoothness tests in my program but we've to solve much more Pell equations.

The time critical part is in solving Pell equations. For this I've used a well known approach to compute the continued fraction of sqrt(D) using only integer arithmetic, see:
http://en.wikipedia.org/wiki/Methods...tion_expansion
This is the same in my program d[],a[],m[]. For this I'm using also exact division for calculating d[n].
The other parts of the code is what you've already described. Note that I'm using LARGEST where LARGEST=p[n]=2*a-1. But maximizing a or LARGEST is the same.

2007-09-02, 05:55	#17
Jim White Aug 2007 Canberra, Australia 33₁₀ Posts	On Multiple Solutions to the Pell Equations Another thought regarding Citrix's question: if you take the fundamental solution (which is just that involving the smallest possible pair of integers x,y), you can then apply either of the recurrence formulae above to generate the infinite number of pairs that also satisfy the same equation. This I think will be found to be just the same process that lets you generate an infinite family of related but distinct Pythagorean triplets from any one starting case .... Each solution has common divisors with the fundamental one, in particular $y_1 \| y_k$ always, and $D$ will always divide $x_k^2 - 1$ , but also the sequences are increasing, so they are picking up new divisors that were not in the original $D$ . Some of these become periodic, some do not. The solution number k in which a prime divisor first appears is called its "Index of Appearance" (or Apparition), and various Laws relating thereto are called "Laws of Apparition" The prime divisors in any solution that do not divide $D$ are also called extrinsic, for obvious reasons So Lehmer's bound on the range of multiple solutions that should be checked can most probably be tightened if expressed in the number of prime divisors of the solution in question, by comparison with the number of primes available (unused) that could possibly appear in solutions as extrinsic divisors ... well, I think so, anyway But as I said, no complexity gain is likely to arise from a tightening of this particular bound. Multiple solutions are more probable when the $D$ are small - they indicate that there are "shortcuts" to some solutions that can be found by extrinsic-divisor-based solutions, which tend to be cheaper ... as we try to work with more and bigger primes, their current role diminishes accordingly Last fiddled with by Jim White on 2007-09-02 at 06:02

2007-09-03, 10:03	#21
Jim White Aug 2007 Canberra, Australia 3×11 Posts	(a little later) I'm beginning to understand (and appreciate) it a little better now ... you've implemented a Bounded version of the Lehmer method? If the bound is known, then the CF development process can take an early exit when the convergents get too big ... We know that this will in fact be the case far more often than not, so the time saving over regular (unbounded) Lehmer method, is substantial ... all we need is a reasonably good bound ... Now I see how it works, I will try an experiment with it! Cheers Last fiddled with by Jim White on 2007-09-03 at 10:28 Reason: Obsessive Computational Disorder

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
B1 and B2 in P-1 method	Miszka	Math	13	2013-12-27 20:23
New Method	Unregistered	Miscellaneous Math	14	2013-05-24 10:55
Lucas-Lehmer	Dougal	Information & Answers	9	2009-02-06 10:25
Emma Lehmer	R.D. Silverman	Information & Answers	1	2007-08-28 06:20
Størmer's theorem	grandpascorpion	Factoring	0	2006-09-10 04:59

2007-09-02, 02:37	#14
Citrix Jun 2003 2×7×113 Posts	Jim, Out of curiosity. The only application I can think of right now, is to study Pell equations and the largest possible solution for each D. From what I understand, the prime values have the first solution as a large number, whereas smooth D values have smaller first solutions. But there has been no work done on the largest solution, if the first solution is known. May be some pell equations have infinite solutions? Any thoughts?

2007-09-02, 03:53	#15
Jim White Aug 2007 Canberra, Australia 33₁₀ Posts	Regarding Citrix's question, if all variables are strictly positive integers then we know $x^2 - Dy^2 = 1$ does always have an infinite number of solutions in positive integers. Now, going the other way, we may also find a particular solution $(x', y')$ as a solution, even a fundamental solution, to more than one Pell equation An example (based on a smooth pair): $a = 195 = 3.5.13$ $a+1 = 196 = 2^2.7^2$ $2a+1 = 391$ $a(a+1) = 38220$ $391^2 - 195(2^2 * 7)^2 = 1$ $391^2 - 780(27)^2 = 1$ $391^2 - 3120(7)^2 = 1$ $391^2 - 9555(2^2)^2 = 1$ $391^2 - 38220.(2)^2= 1$ For each distinct square $y^2$ that divides $4a(a+1)$ , we have a corresponding $D$ whose Pell equation solutions must include $(2a+1, y)$ . In many such cases it can occur as a fundamental solution. If we call any $D$ that produces $2a+1$ as a solution a producer* of $a$ , then the Størmer/Lehmer schemes work by giving a scheme for constructing a finite set of $D$ which is guaranteed to include at least one producer of all target value $a$

2007-09-03, 07:31	#19
Jim White Aug 2007 Canberra, Australia 3×11 Posts	Thanks Robert. That sounds good, I'll have a good look at it ...

2007-09-03, 08:45	#20
Jim White Aug 2007 Canberra, Australia 3·11 Posts	Very nice work, Robert. That certainly runs faster than my initial hack ... I'll make an updated version of that timing chart above with a plot for your program running times. I have spare suits - you can be diamonds! A description of your approach would be welcome! Your smoothness testing, for example, looks interesting. Mine doesn't do any gcd calls, for a start!