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.
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. .
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 .
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.
For the construction of an interpolatory integration rule on the unit circle with nodes by means of the Laurent polynomials as basis functions for the approximation, we have at our disposal two nonnegative integers and which determine the subspace of basis functions. The quadrature rule will integrate correctly any function from this subspace. In this paper upper bounds for the remainder term of interpolatory integration rules on are obtained. These bounds apply to analytic functions up to a finite number of isolated poles outside In addition, if the integrand function has no poles in the closed unit disc or is a rational function with poles outside , we propose a simple rule to determine the value of and hence in order to minimize the quadrature error term. Several numerical examples are given to illustrate the theoretical results.
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).
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.
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.
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 .
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.
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 .
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 .)