An analysis of the Rayleigh-Ritz method for approximating eigenspaces

This paper concerns the Rayleigh-Ritz method for computing an approximation to an eigenspace of a general matrix from a subspace that contains an approximation to . The method produces a pair that purports to approximate a pair , where is a basis for and . In this paper we consider the convergence of as the sine of the angle between and approaches zero. It is shown that under a natural hypothesis--called the uniform separation condition--the Ritz pairs converge to the eigenpair . When one is concerned with eigenvalues and eigenvectors, one can compute certain refined Ritz vectors whose convergence is guaranteed, even when the uniform separation condition is not satisfied. An attractive feature of the analysis is that it does not assume that has distinct eigenvalues or is diagonalizable.

     

Finding strong pseudoprimes to several bases

Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke, are known for . Upper bounds for were given by Jaeschke.

In this paper we tabulate all strong pseudoprimes (spsp's) to the first ten prime bases which have the form with odd primes and There are in total 44 such numbers, six of which are also spsp(31), and three numbers are spsp's to both bases 31 and 37. As a result the upper bounds for and are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for to be a strong pseudoprime to one or to several prime bases. Comparisons of effectiveness with both Jaeschke's and Arnault's methods are given.

     

On the uniformity of distribution of the RSA pairs

Let be a product of two distinct primes and . We show that for almost all exponents with the RSA pairs are uniformly distributed modulo when runs through

the group of units modulo (that is, as in the classical RSA scheme);

the set of -products , , where are selected at random (that is, as in the recently introduced RSA scheme with precomputation).

These results are based on some new bounds of exponential sums.

     

Tenth degree number fields with quintic fields having one real place

In this paper, we enumerate all number fields of degree of discriminant smaller than in absolute value containing a quintic field having one real place. For each one of the (resp. found fields of signature (resp. the field discriminant, the quintic field discriminant, a polynomial defining the relative quadratic extension, the corresponding relative discriminant, the corresponding polynomial over , and the Galois group of the Galois closure are given.

In a supplementary section, we give the first coincidence of discriminant of (resp. nonisomorphic fields of signature (resp. .

     

Wavelet bases in

Some years ago, compactly supported divergence-free wavelets were constructed which also gave rise to a stable (biorthogonal) wavelet splitting of . These bases have successfully been used both in the analysis and numerical treatment of the Stokes and Navier-Stokes equations. In this paper, we construct stable wavelet bases for the stream function spaces . Moreover, -free vector wavelets are constructed and analysed. The relationship between and are expressed in terms of these wavelets. We obtain discrete (orthogonal) Hodge decompositions.

Our construction works independently of the space dimension, but in terms of general assumptions on the underlying wavelet systems in that are used as building blocks. We give concrete examples of such bases for tensor product and certain more general domains . As an application, we obtain wavelet multilevel preconditioners in and .

     

Period of the power generator and small values of Carmichael's function

Consider the pseudorandom number generator where we are given the modulus , the initial value and the exponent . One case of particular interest is when the modulus is of the form , where are different primes of the same magnitude. It is known from work of the first and third authors that for moduli , if the period of the sequence exceeds , then the sequence is uniformly distributed. We show rigorously that for almost all choices of it is the case that for almost all choices of , the period of the power generator exceeds . And so, in this case, the power generator is uniformly distributed.

We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto.

The principal tool is an estimate related to the Carmichael function , the size of the largest cyclic subgroup of the multiplicative group of residues modulo . In particular, we show that for any , we have for all integers with , apart from at most exceptions.

     

Approximating the exponential from a Lie algebra to a Lie group

Consider a differential equation with and , where is a Lie algebra of the matricial Lie group . Every can be mapped to by the matrix exponential map with .

Most numerical methods for solving ordinary differential equations (ODEs) on Lie groups are based on the idea of representing the approximation of the exact solution , , by means of exact exponentials of suitable elements of the Lie algebra, applied to the initial value . This ensures that .

When the exponential is difficult to compute exactly, as is the case when the dimension is large, an approximation of plays an important role in the numerical solution of ODEs on Lie groups. In some cases rational or polynomial approximants are unsuitable and we consider alternative techniques, whereby is approximated by a product of simpler exponentials.

In this paper we present some ideas based on the use of the Strang splitting for the approximation of matrix exponentials. Several cases of and are considered, in tandem with general theory. Order conditions are discussed, and a number of numerical experiments conclude the paper.

     

Families of irreducible polynomials of Gaussian periods and matrices of cyclotomic numbers

Given an odd prime we show a way to construct large families of polynomials , , where is a set of primes of the form mod and is the irreducible polynomial of the Gaussian periods of degree in . Examples of these families when are worked in detail. We also show, given an integer and a prime mod , how to represent by matrices the Gaussian periods of degree in , and how to calculate in a simple way, with the help of a computer, irreducible polynomials for elements of .

     

On a conjecture of Erdos and Stewart

For any , let be the th prime number. In this paper, we confirm a conjecture of Erdos and Stewart concerning all the solutions of the diophantine equation , when .

     

Continued fractions in local fields, II

The present paper is a continuation of an earlier work by the author. We propose some new definitions of -adic continued fractions. At the end of the paper we give numerical examples illustrating these definitions. It turns out that for every if then has a periodic continued fraction expansion. The same is not true in for some larger values of

     

Computation of several cyclotomic Swan subgroups

Let denote the locally free class group, that is the group of stable isomorphism classes of locally free -modules, where is the ring of algebraic integers in the number field and is a finite group. We show how to compute the Swan subgroup, , of when , a primitive -th root of unity, , where is an odd (rational) prime so that and 2 is inert in We show that, under these hypotheses, this calculation reduces to computing a quotient ring of a polynomial ring; we do the computations obtaining for several primes a nontrivial divisor of These calculations give an alternative proof that the fields for =11, 13, 19, 29, 37, 53, 59, and 61 are not Hilbert-Speiser.

     

Upper bounds for the prime divisors of Wendt's determinant

Let be an even integer, . The resultant of the polynomials and is known as Wendt's determinant of order . We prove that among the prime divisors of only those which divide or can be larger than , where and is the th Lucas number, except when and . Using this estimate we derive criteria for the nonsolvability of Fermat's congruence.

     

Random Fibonacci sequences and the number

For the familiar Fibonacci sequence (defined by , and for ), increases exponentially with at a rate given by the golden ratio . But for a simple modification with both additions and subtractions - the random Fibonacci sequences defined by , and for , , where each sign is independent and either or - with probability - it is not even obvious if should increase with . Our main result is that

with probability . Finding the number involves the theory of random matrix products, Stern-Brocot division of the real line, a fractal measure, a computer calculation, and a rounding error analysis to validate the computer calculation.

     

Computer verification of the Ankeny-Artin-Chowla Conjecture for all primes less than

Let be a prime congruent to 1 modulo 4, and let be rational integers such that is the fundamental unit of the real quadratic field . The Ankeny-Artin-Chowla conjecture (AAC conjecture) asserts that will not divide . This is equivalent to the assertion that will not divide , where denotes the th Bernoulli number. Although first published in 1952, this conjecture still remains unproved today. Indeed, it appears to be most difficult to prove. Even testing the conjecture can be quite challenging because of the size of the numbers ; for example, when , then both and exceed . In 1988 the AAC conjecture was verified by computer for all . In this paper we describe a new technique for testing the AAC conjecture and we provide some results of a computer run of the method for all primes up to .

     

Korovkin tests, approximation, and ergodic theory

We consider sequences of matrices with a block structure spectrally distributed as an -variate matrix-valued function , and, for any , we suppose that is a linear and positive operator. For every fixed we approximate the matrix in a suitable linear space of matrices by minimizing the Frobenius norm of when ranges over . The minimizer is denoted by . We show that only a simple Korovkin test over a finite number of polynomial test functions has to be performed in order to prove the following general facts:

1.

the sequence is distributed as ,

2.

the sequence is distributed as the constant function (i.e. is spectrally clustered at zero).

The first result is an ergodic one which can be used for solving numerical approximation theory problems. The second has a natural interpretation in the theory of the preconditioning associated to cg-like algorithms.

     

Computation of relative class numbers of CM-fields by using Hecke -functions

We develop an efficient technique for computing values at of Hecke -functions. We apply this technique to the computation of relative class numbers of non-abelian CM-fields which are abelian extensions of some totally real subfield . We note that the smaller the degree of the more efficient our technique is. In particular, our technique is very efficient whenever instead of simply choosing (the maximal totally real subfield of ) we can choose real quadratic. We finally give examples of computations of relative class numbers of several dihedral CM-fields of large degrees and of several quaternion octic CM-fields with large discriminants.

     

On the modular curves

Let denote an elliptic curve over and the modular curve classifying the elliptic curves over such that the representations of in the 7-torsion points of and of are symplectically isomorphic. In case is given by a Weierstraß equation such that the invariant is a square, we exhibit here nontrivial points of . From this we deduce an infinite family of curves for which has at least four nontrivial points.

     

Numerical indefinite integration of functions with singularities

We derive an indefinite quadrature formula, based on a theorem of Ganelius, for functions, for 1$">, over the interval . The main factor in the error of our indefinite quadrature formula is , with nodes and . The convergence rate of our formula is better than that of the Stenger-type formulas by a factor of in the constant of the exponential. We conjecture that our formula has the best possible value for that constant. The results of numerical examples show that our indefinite quadrature formula is better than Haber's indefinite quadrature formula for -functions.

     

On irregular prime power divisors of the Bernoulli numbers

Let ( ) denote the usual th Bernoulli number. Let be a positive even integer where or . It is well known that the numerator of the reduced quotient is a product of powers of irregular primes. Let be an irregular pair with . We show that for every the congruence has a unique solution where and . The sequence defines a -adic integer which is a zero of a certain -adic zeta function originally defined by T. Kubota and H. W. Leopoldt. We show some properties of these functions and give some applications. Subsequently we give several computations of the (truncated) -adic expansion of for irregular pairs with below 1000.

     

Two kinds of strong pseudoprimes up to

Let be an odd composite integer. Write with odd. If either mod or mod for some , then we say that is a strong pseudoprime to base , or spsp() for short. Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the are known for . Conjectured values of were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024).

The main purpose of this paper is to give exact values of for ; to give a lower bound of : ; and to give reasons and numerical evidence of K2- and -spsp's to support the following conjecture: for any , where (resp. ) is the smallest K2- (resp. -) strong pseudoprime to all the first prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: with primes and ; and that a -spsp is an spsp and a Carmichael number of the form: with each prime factor mod .)