The Lucas-Pratt primality tree

In 1876, E. Lucas showed that a quick proof of primality for a prime could be attained through the prime factorization of and a primitive root for . V. Pratt's proof that PRIMES is in NP, done via Lucas's theorem, showed that a certificate of primality for a prime could be obtained in modular multiplications with integers at most . We show that for all constants , the number of modular multiplications necessary to obtain this certificate is greater than for a set of primes with relative asymptotic density 1.

     

Explicit values of multi-dimensional Kloosterman sums for prime powers, II

For any integer fix , and let denote the group of reduced residues modulo . Let , a power of a prime . The hyper-Kloosterman sums of dimension are defined for by

where denotes the multiplicative inverse of modulo .

Salie evaluated in the classical setting for even , and for odd with . Later, Smith provided formulas that simplified the computation of in these cases for . Recently, Cochrane, Liu and Zheng computed upper bounds for in the general case , stopping short of their explicit evaluation. Here I complete the computation they initiated to obtain explicit values for the Kloosterman sums for , relying on basic properties of some simple specialized exponential sums. The treatment here is more elementary than the author's previous determination of these Kloosterman sums using character theory and -adic methods. At the least, it provides an alternative, independent evaluation of the Kloosterman sums.

     

A counterexample concerning the -projector onto linear spline spaces

For the -orthogonal projection onto spaces of linear splines over simplicial partitions in polyhedral domains in , , we show that in contrast to the one-dimensional case, where independently of the nature of the partition, in higher dimensions the -norm of cannot be bounded uniformly with respect to the partition. This fact is folklore among specialists in finite element methods and approximation theory but seemingly has never been formally proved.

     

Uniform error estimates in the finite element method for a singularly perturbed reaction-diffusion problem

Consider the problem with homogeneous Neumann boundary condition in a bounded smooth domain in . The whole range is treated. The Galerkin finite element method is used on a globally quasi-uniform mesh of size ; the mesh is fixed and independent of .

A precise analysis of how the error at each point depends on and is presented. As an application, first order error estimates in , which are uniform with respect to , are given.

     

Divisors in residue classes, constructively

Let be integers satisfying , , , and let . Lenstra showed that the number of integer divisors of equivalent to is upper bounded by . We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to .

     

Convergence of classes of high-order semi-Lagrangian schemes for the Vlasov-Poisson system

In this paper we present some classes of high-order semi-Lagran- gian schemes for solving the periodic one-dimensional Vlasov-Poisson system in phase-space on uniform grids. We prove that the distribution function and the electric field converge in the norm with a rate of

where is the degree of the polynomial reconstruction, and and are respectively the time and the phase-space discretization parameters.

     

On Meinardus' examples for the conjugate gradient method

The conjugate gradient (CG) method is widely used to solve a positive definite linear system of order . It is well known that the relative residual of the th approximate solution by CG (with the initial approximation ) is bounded above by

   with

where is 's spectral condition number. In 1963, Meinardus (Numer. Math., 5 (1963), pp. 14-23) gave an example to achieve this bound for but without saying anything about all other . This very example can be used to show that the bound is sharp for any given by constructing examples to attain the bound, but such examples depend on and for them the th residual is exactly zero. Therefore it would be interesting to know if there is any example on which the CG relative residuals are comparable to the bound for all . There are two contributions in this paper:

1. A closed formula for the CG residuals for all on Meinardus' example is obtained, and in particular it implies that the bound is always within a factor of of the actual residuals;
2. A complete characterization of extreme positive linear systems for which the th CG residual achieves the bound is also presented.

     

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.

     

Construction of hyperelliptic function fields of high three-rank

We present several explicit constructions of hyperelliptic function fields whose Jacobian or ideal class group has large -rank. Our focus is on finding examples for which the genus and the base field are as small as possible. Most of our methods are adapted from analogous techniques used for generating quadratic number fields whose ideal class groups have high -rank, but one method, applicable to finding large -ranks for odd primes is new and unique to function fields. Algorithms, examples, and numerical data are included.

     

Littlewood polynomials with high order zeros

Let be the minimal length of a polynomial with coefficients divisible by . Byrnes noted that for each , and asked whether in fact . Boyd showed that for all , but . He further showed that , and that is one of the 5 numbers , or . Here we prove that . Similarly, let be the maximal power of dividing some polynomial of degree with coefficients. Boyd was able to find for . In this paper we determine for .

     

Constructing representations of higher degrees of finite simple groups and covers

Let be a finite group and an irreducible character of . A simple method for constructing a representation affording can be used whenever has a subgroup such that has a linear constituent with multiplicity 1. In this paper we show that (with a few exceptions) if is a simple group or a covering group of a simple group and is an irreducible character of of degree between 32 and 100, then such a subgroup exists.

     

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.

     

Three- and four-dimensional -optimal lattice rules of moderate trigonometric degree

A systematic search for optimal lattice rules of specified trigonometric degree over the hypercube has been undertaken. The search is restricted to a population of lattice rules . This includes those where the dual lattice may be generated by points for each of which . The underlying theory, which suggests that such a restriction might be helpful, is presented. The general character of the search is described, and, for , and , , a list of -optimal rules is given. It is not known whether these are also optimal rules in the general sense; this matter is discussed.

     

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.

     

Integer transfinite diameter and polynomials with small Mahler measure

In this work, we show how suitable generalizations of the integer transfinite diameter of some compact sets in give very good bounds for coefficients of polynomials with small Mahler measure. By this way, we give the list of all monic irreducible primitive polynomials of of degree at most with Mahler measure less than and of degree and with Mahler measure less than .

     

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

     

The hyperdeterminant and triangulations of the 4-cube

The hyperdeterminant of format is a polynomial of degree in unknowns which has terms. We compute the Newton polytope of this polynomial and the secondary polytope of the -cube. The regular triangulations of the -cube are classified into -equivalence classes, one for each vertex of the Newton polytope. The -cube has coarsest regular subdivisions, one for each facet of the secondary polytope, but only of them come from the hyperdeterminant.

     

Largest known twin primes and Sophie Germain primes

The numbers are twin primes. The number is a Sophie Germain prime, i.e. and are both primes. For , the numbers , and are all primes.

     

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 .