Higher-order Carmichael numbers

We define a Carmichael number of order to be a composite integer such that th-power raising defines an endomorphism of every -algebra that can be generated as a -module by elements. We give a simple criterion to determine whether a number is a Carmichael number of order , and we give a heuristic argument (based on an argument of Erdos for the usual Carmichael numbers) that indicates that for every there should be infinitely many Carmichael numbers of order . The argument suggests a method for finding examples of higher-order Carmichael numbers; we use the method to provide examples of Carmichael numbers of order .

     

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.

     

Computing the tame kernel of quadratic imaginary fields

J. Tate has determined the group (called the tame kernel) for six quadratic imaginary number fields where Modifying the method of Tate, H. Qin has done the same for and and M. Skaba for and

In the present paper we discuss the methods of Qin and Skaba, and we apply our results to the field

In the Appendix at the end of the paper K. Belabas and H. Gangl present the results of their computation of for some other values of The results agree with the conjectural structure of given in the paper by Browkin and Gangl.

     

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.

     

Explicit primality criteria for

Deterministic polynomial time primality criteria for have been known since the work of Lucas in 1876-1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form , where is any fixed prime. When (p-1)/2$"> we show that it is always possible to produce a Lucas-like deterministic test for the primality of which requires that only modular multiplications be performed modulo , as long as we can find a prime of the form such that is not divisible by . We also show that for all with such a can be found very readily, and that the most difficult case in which to find a appears, somewhat surprisingly, to be that for . Some explanation is provided as to why this case is so difficult.

     

On searching for solutions of the Diophantine equation

We propose an efficient search algorithm to solve the equation for a fixed value of 0$">. By parametrizing , this algorithm obtains and (if they exist) by solving a quadratic equation derived from divisors of . Thanks to the use of several efficient number-theoretic sieves, the new algorithm is much faster on average than previous straightforward algorithms. We performed a computer search for six values of below 1000 for which no solution had previously been found. We found three new integer solutions for and 931 in the range of .

     

On the iteratively regularized Gauss-Newton method for solving nonlinear ill-posed problems

The iteratively regularized Gauss-Newton method is applied to compute the stable solutions to nonlinear ill-posed problems when the data is given approximately by with . In this method, the iterative sequence is defined successively by

where is an initial guess of the exact solution and is a given decreasing sequence of positive numbers admitting suitable properties. When is used to approximate , the stopping index should be designated properly. In this paper, an a posteriori stopping rule is suggested to choose the stopping index of iteration, and with the integer determined by this rule it is proved that

with a constant independent of , where denotes the iterative solution corresponding to the noise free case. As a consequence of this result, the convergence of is obtained, and moreover the rate of convergence is derived when satisfies a suitable ``source-wise representation". The results of this paper suggest that the iteratively regularized Gauss-Newton method, combined with our stopping rule, defines a regularization method of optimal order for each . Numerical examples for parameter estimation of a differential equation are given to test the theoretical results.

     

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 .

     

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. .

     

On iterates of Möbius transformations on fields

Let be a quadratic polynomial over a splitting field , and be the set of zeros of . We define an associative and commutative binary relation on so that every Möbius transformation with fixed point set is of the form ``plus' for some . This permits an easy proof of Aitken acceleration as well as generalizations of known results concerning Newton's method, the secant method, Halley's method, and higher order methods. If is equipped with a norm, then we give necessary and sufficient conditions for the iterates of a Möbius transformation to converge (necessarily to one of its fixed points) in the norm topology. Finally, we show that if the fixed points of are distinct and the iterates of converge, then Newton's method converges with order 2, and higher order generalizations converge accordingly.

     

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.

     

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.

     

Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

We examine the problem of factoring the th cyclotomic polynomial, over , and distinct primes. Given the traces of the roots of we construct the coefficients of in time . We demonstrate a deterministic algorithm for factoring in time when has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of in time .

     

Error estimates for the three-field formulation with bubble stabilization

In this paper we prove convergence and error estimates for the so-called 3-field formulation using piecewise linear finite elements stabilized with boundary bubbles. Optimal error bounds are proved in and in the broken norm for the internal variable , and in suitable weighted norms for the other variables and .     

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 .

     

Special prime numbers and discrete logs in finite prime fields

A set of primes involving numbers such as , where and , is defined. An algorithm for computing discrete logs in the finite field of order with is suggested. Its heuristic expected running time is for , where as , , and . At present, the most efficient algorithm for computing discrete logs in the finite field of order for general is Schirokauer's adaptation of the Number Field Sieve. Its heuristic expected running time is for . Using rather than general does not enhance the performance of Schirokauer's algorithm. The definition of the set and the algorithm suggested in this paper are based on a more general congruence than that of the Number Field Sieve. The congruence is related to the resultant of integer polynomials. We also give a number of useful identities for resultants that allow us to specify this congruence for some .

     

The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors

This paper concerns a harmonic projection method for computing an approximation to an eigenpair of a large matrix . Given a target point and a subspace that contains an approximation to , the harmonic projection method returns an approximation to . Three convergence results are established as the deviation of from approaches zero. First, the harmonic Ritz value converges to if a certain Rayleigh quotient matrix is uniformly nonsingular. Second, the harmonic Ritz vector converges to if the Rayleigh quotient matrix is uniformly nonsingular and remains well separated from the other harmonic Ritz values. Third, better error bounds for the convergence of are derived when converges. However, we show that the harmonic projection method can fail to find the desired eigenvalue --in other words, the method can miss if it is very close to . To this end, we propose to compute the Rayleigh quotient of with respect to and take it as a new approximate eigenvalue. is shown to converge to once tends to , no matter how is close to . Finally, we show that if the Rayleigh quotient matrix is uniformly nonsingular, then the refined harmonic Ritz vector, or more generally the refined eigenvector approximation introduced by the author, converges. We construct examples to illustrate our theory.

     

Adaptive wavelet methods for elliptic operator equations: Convergence rates

This paper is concerned with the construction and analysis of wavelet-based adaptive algorithms for the numerical solution of elliptic equations. These algorithms approximate the solution of the equation by a linear combination of wavelets. Therefore, a benchmark for their performance is provided by the rate of best approximation to by an arbitrary linear combination of wavelets (so called -term approximation), which would be obtained by keeping the largest wavelet coefficients of the real solution (which of course is unknown). The main result of the paper is the construction of an adaptive scheme which produces an approximation to with error in the energy norm, whenever such a rate is possible by -term approximation. The range of 0$"> for which this holds is only limited by the approximation properties of the wavelets together with their ability to compress the elliptic operator. Moreover, it is shown that the number of arithmetic operations needed to compute the approximate solution stays proportional to . The adaptive algorithm applies to a wide class of elliptic problems and wavelet bases. The analysis in this paper puts forward new techniques for treating elliptic problems as well as the linear systems of equations that arise from the wavelet discretization.

     

The number of primes is finite

For a positive integer let and let . The number of primes of the form is finite, because if , then is divisible by . The heuristic argument is given by which there exists a prime such that for all large ; a computer check however shows that this prime has to be greater than . The conjecture that the numbers are squarefree is not true because .

     

Minimality and other properties of the width- nonadjacent form

Let be an integer and let be the set of integers that includes zero and the odd integers with absolute value less than . Every integer can be represented as a finite sum of the form , with , such that of any consecutive 's at most one is nonzero. Such representations are called width- nonadjacent forms (-NAFs). When these representations use the digits and coincide with the well-known nonadjacent forms. Width- nonadjacent forms are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. We provide some new results on the -NAF. We show that -NAFs have a minimal number of nonzero digits and we also give a new characterization of the -NAF in terms of a (right-to-left) lexicographical ordering. We also generalize a result on -NAFs and show that any base 2 representation of an integer, with digits in , that has a minimal number of nonzero digits is at most one digit longer than its binary representation.