Wojciech Florek <[EMAIL PROTECTED]> notes:
> Hi all!
>
> S.A. Fulling from Texas A&M Univ. posted two articles at
> the Los Alamos Nat. Lab. archive. The first is on
> quantum computers and refers to the second one `abstracted' as
>
> "This is a pedagogical article cited in the foregoing research note"
>
>
> I'd be obliged if some of our number-theory/programming wizards
> will look at these articles (esp. the second).
>
> [To look visit http://xxx.lanl.gov/abs/quant-ph/9911050
> and http://xxx.lanl.gov/abs/quant-ph/9911051 ]
>
>
> Is there something new?
> Is there something interesting for the GIMPS and other math projects?
I looked only at the second article. It begins with the recurrence
a[n+1] = a[n]^2 + (n + 3)*n*a[n] a[0] = 1
We can grind out a[1] = 1, a[2] = 5, a[3] = 75,
a[4] = 6975, a[5] = 48845925, ...
Author S.A. Fulling suggests computing the sequence by modular
arithmetic (using primes below 2^16) to avoid big-integer computations.
Then use the Chinese remainder theorem to get the final result.
This technique is well-known, but it requires a good _upper bound_
on the final answer. Here we see a[2] = 5 > 2^2, and it is easy to prove
a[n] > 2^(2^(n-1)) (n >= 2)
The product of the primes below 65536 is obviously below
65536^65536 = 2^(2^20). So
a[21] > 2^(2^20) > (product of primes below 65536)
We can't determine a[21] uniquely from its remainder modulo these primes.
An example where the CRT can be useful is determinant evaluation.
Consider an n x n matrix of integers, all bounded by B in absolute value.
The determinant of this matrix is a sum of n! products, each at most B^n,
so the determinant is bounded by n! * B^n. The Hadamard inequality gives
a better bound: n^(n/2) * B^n. A 100 x 100 matrix with integer
entries up to 10^6 will have determinant bounded by
100^50 * (10^6)^100 = 10^700.
We can evaluate this determinant modulo 150 primes near 60000,
after which we know it uniquely. The modular evaluations can
use Gaussian elimination. A direct approach using Gaussian elimination
would involve many rational numbers with huge numerator and denominator,
and soon become unwieldly. Direct evalation by minors avoids the fractions
but needs 100! arithmetic operations.
Peter Montgomery
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
