Linear difference equations with transition points

Two linearly independent asymptotic solutions are constructed for the second-order linear difference equation

where and have power series expansions of the form

with . Our results hold uniformly for in an infinite interval containing the transition point given by . As an illustration, we present an asymptotic expansion for the monic polynomials which are orthogonal with respect to the modified Jacobi weight , , where , -1$"> and is real analytic and strictly positive on .

     

Finding -strong pseudoprimes

Let be odd primes and . Put

Then we call the kernel, the triple the signature, and the height of , respectively. We call a -number if it is a Carmichael number with each prime factor . If is a -number and a strong pseudoprime to the bases for , we call a -spsp . Since -numbers have probability of error (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of (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.

In this paper, we first describe an algorithm for finding -spsp(2)'s, to a given limit, with heights bounded. There are in total -spsp's with heights . We then give an overview of the 21978 - spsp(2)'s and tabulate of them, which are -spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No -spsp's to the first prime bases with heights were found. We conjecture that there exist no -spsp's to the first prime bases with heights and so that

which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those -spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of -spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger -spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding -strong pseudoprimes to the first several prime bases are given.

     

An infinite family of bounds on zeros of analytic functions and relationship to Smale's bound

Smale's analysis of Newton's iteration function induce a lower bound on the gap between two distinct zeros of a given complex-valued analytic function . In this paper we make use of a fundamental family of iteration functions , , to derive an infinite family of lower bounds on the above gap. However, even for , where coincides with Newton's, our lower bound is more than twice as good as Smale's bound or its improved version given by Blum, Cucker, Shub, and Smale. When is a complex polynomial of degree , for small the corresponding bound is computable in arithmetic operations. For quadratic polynomials, as increases the lower bounds converge to the actual gap. We show how to use these bounds to compute lower bounds on the distance between an arbitrary point and the nearest root of . In particular, using the latter result, we show that, given a complex polynomial , , for each we can compute upper and lower bounds and such that the roots of lie in the annulus . In particular, , ; and , , where . An application of the latter bounds is within Weyl's classical quad-tree algorithm for computing all roots of a given complex polynomial.

     

A search for Fibonacci-Wieferich and Wolstenholme primes

A prime is called a Fibonacci-Wieferich prime if , where is the th Fibonacci number. We report that there exist no such primes . A prime is called a Wolstenholme prime if . To date the only known Wolstenholme primes are 16843 and 2124679. We report that there exist no new Wolstenholme primes . Wolstenholme, in 1862, proved that for all primes . It is estimated by a heuristic argument that the ``probability' that is Fibonacci-Wieferich (independently: that is Wolstenholme) is about . We provide some statistical data relevant to occurrences of small values of the Fibonacci-Wieferich quotient modulo .

     

Improved methods and starting values to solve the matrix equations iteratively

The two matrix iterations are known to converge linearly to a positive definite solution of the matrix equations , respectively, for known choices of and under certain restrictions on . The convergence for previously suggested starting matrices is generally very slow. This paper explores different initial choices of in both iterations that depend on the extreme singular values of and lead to much more rapid convergence. Further, the paper offers a new algorithm for solving the minus sign equation and explores mixed algorithms that use Newton's method in part.

     

Finite element superconvergence on Shishkin mesh for 2-D convection-diffusion problems

In this work, the bilinear finite element method on a Shishkin mesh for convection-diffusion problems is analyzed in the two-dimensional setting. A superconvergence rate in a discrete -weighted energy norm is established under certain regularity assumptions. This convergence rate is uniformly valid with respect to the singular perturbation parameter . Numerical tests indicate that the rate is sharp for the boundary layer terms. As a by-product, an -uniform convergence of the same order is obtained for the -norm. Furthermore, under the same regularity assumption, an -uniform convergence of order in the norm is proved for some mesh points in the boundary layer region.

     

Computing weight modular forms of level

For a prime we describe an algorithm for computing the Brandt matrices giving the action of the Hecke operators on the space of modular forms of weight and level . For we define a special Hecke stable subspace of which contains the space of modular forms with CM by the ring of integers of and we describe the calculation of the corresponding Brandt matrices.

     

Continuous-time Kreiss resolvent condition on infinite-dimensional spaces

Given the infinitesimal generator of a -semigroup on the Banach space which satisfies the Kreiss resolvent condition, i.e., there exists an such that for all complex with positive real part, we show that for general Banach spaces this condition does not give any information on the growth of the associated -semigroup. For Hilbert spaces the situation is less dramatic. In particular, we show that the semigroup can grow at most like . Furthermore, we show that for every there exists an infinitesimal generator satisfying the Kreiss resolvent condition, but whose semigroup grows at least like . As a consequence, we find that for with the standard Euclidian norm the estimate cannot be replaced by a lower power of or .

     

Finding strong pseudoprimes to several bases. II

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 . Upper bounds for were first given by Jaeschke, and those for were then sharpened by the first author in his previous paper (Math. Comp. 70 (2001), 863-872).

In this paper, we first follow the first author's previous work to use biquadratic residue characters and cubic residue characters as main tools to tabulate all strong pseudoprimes (spsp's) to the first five or six prime bases, which have the form with odd primes and ; then we tabulate all Carmichael numbers , to the first six prime bases up to 13, which have the form with each prime factor . There are in total 36 such Carmichael numbers, 12 numbers of which are also spsp's to base 17; 5 numbers are spsp's to bases 17 and 19; one number is an spsp to the first 11 prime bases up to 31. As a result the upper bounds for and are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number:

We conjecture that

and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor and propose necessary conditions on to be a strong pseudoprime to the first prime bases. Comparisons of effectiveness with Arnault's, Bleichenbacher's, Jaeschke's, and Pinch's methods for finding (Carmichael) numbers with three prime factors, which are strong pseudoprimes to the first several prime bases, are given.

     

A solution to certain polynomial equations with applications to nonlinear fitting

We present a combinatorial method for solving a certain system of polynomial equations of Vandermonde type in variables by reducing it to the problem of solving two special linear systems of size and rooting a single univariate polynomial of degree . Over , all solutions can be found with fixed precision using, up to polylogarithmic factors, bitwise operations in the worst case. Furthermore, if the data is well conditioned, then this can be reduced to bit operations, up to polylogarithmic factors. As an application, we show how this can be used to fit data to a complex exponential sum with terms in the same, nearly optimal, time.

     

Zeta functions of a class of elliptic curves over a rational function field of characteristic two

We show how to calculate the zeta functions and the orders of Tate-Shafarevich groups of the elliptic curves with equation over the rational function field , where is a power of 2. In the range , , odd of degree , the largest values obtained for are (one case), (one case) and (three cases). We observe and discuss a remarkable pattern for the distributions of signs in the functional equation and of fudge factors at places of bad reduction. These imply strong restrictions on the precise form of the Langlands correspondence for GL over local or global fields of characteristic two.

     

New convergence results on the generalized Richardson extrapolation process GREP for logarithmic sequences

Let as , where and are known for for some 0$">, but and the are not known. The generalized Richardson extrapolation process GREP is used in obtaining good approximations to , the limit or antilimit of as . The approximations to obtained via GREPare defined by the linear systems , , where is a decreasing positive sequence with limit zero. The study of GREP for slowly varying functions was begun in two recent papers by the author. For such we have as with possibly complex and . In the present work we continue to study the convergence and stability of GREPas it is applied to such with different sets of collocation points that have been used in practical situations. In particular, we consider the cases in which (i) are arbitrary, (ii) , (iii) as for some 0$">, (iv) for all , (v) , and (vi) for all .

     

Predicting nonlinear pseudorandom number generators

Let be a prime and let and be elements of the finite field of elements. The inversive congruential generator (ICG) is a sequence of pseudorandom numbers defined by the relation . We show that if sufficiently many of the most significant bits of several consecutive values of the ICG are given, one can recover the initial value (even in the case where the coefficients and are not known). We also obtain similar results for the quadratic congruential generator (QCG), , where . This suggests that for cryptographic applications ICG and QCG should be used with great care. Our results are somewhat similar to those known for the linear congruential generator (LCG), , but they apply only to much longer bit strings. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for LCG.

     

On the total number of prime factors of an odd perfect number

We say is perfect if , where denotes the sum of the positive divisors of . No odd perfect numbers are known, but it is well known that if such a number exists, it must have prime factorization of the form , where , , ..., are distinct primes and . We prove that if or for all , , then . We also prove as our main result that , where . This improves a result of Sayers given in 1986.

     

Multigrid methods for the computation of singular solutions and stress intensity factors I: Corner singularities

We consider the Poisson equation with homogeneous Dirichlet boundary condition on a two-dimensional polygonal domain with re-entrant angles. A multigrid method for the computation of singular solutions and stress intensity factors using piecewise linear functions is analyzed. When , the rate of convergence to the singular solution in the energy norm is shown to be , and the rate of convergence to the stress intensity factors is shown to be , where is the largest re-entrant angle of the domain and can be arbitrarily small. The cost of the algorithm is . When , the algorithm can be modified so that the convergence rate to the stress intensity factors is . In this case the maximum error of the multigrid solution over the vertices of the triangulation is shown to be .

     

Stability of Runge-Kutta methods for quasilinear parabolic problems

We consider a quasilinear parabolic problem

where , , is a family of sectorial operators in a Banach space with fixed domain . This problem is discretized in time by means of a strongly A()-stable, , Runge-Kutta method. We prove that the resulting discretization is stable, under some natural assumptions on the dependence of with respect to . Our results are useful for studying in norms, , many problems arising in applications. Some auxiliary results for time-dependent parabolic problems are also provided.

     

Double roots of power series and related matters

For a given collection of distinct arguments , multiplicities and a real interval containing zero, we are interested in determining the smallest for which there is a power series with coefficients in , and roots of order respectively. We denote this by . We describe the usual form of the extremal series (we give a sufficient condition which is also necessary when the extremal series possesses at least non-dependent coefficients strictly inside , where is 1 or 2 as is real or complex). We focus particularly on , the size of the smallest double root of a power series lying on a given ray (of interest in connection with the complex analogue of work of Boris Solomyak on the distribution of the random series ). We computed the value of for the rationals in of denominator less than fifty. The smallest value we encountered was . For the one-sided intervals and the corresponding smallest values were and .

     

Real zeros of Dedekind zeta functions of real quadratic fields

Let be a primitive, real and even Dirichlet character with conductor , and let be a positive real number. An old result of H. Davenport is that the cycle sums are all positive at and this has the immediate important consequence of the positivity of . We extend Davenport's idea to show that in fact for , 0$"> for all with so that one can deduce the positivity of by the nonnegativity of a finite sum for any . A simple algorithm then allows us to prove numerically that has no positive real zero for a conductor up to 200,000, extending the previous record of 986 due to Rosser more than 50 years ago. We also derive various estimates explicit in of the as well as the shifted cycle sums considered previously by Leu and Li for . These explicit estimates are all rather tight and may have independent interests.

     

Recovering signals from inner products involving prolate spheroidals in the presence of jitter

The paper deals with recovering band- and energy-limited signals from a finite set of perturbed inner products involving the prolate spheroidal wavefunctions. The measurement noise (bounded by ) and jitter meant as perturbation of the ends of the integration interval (bounded by ) are considered. The upper and lower bounds on the radius of information are established. We show how the error of the best algorithms depends on and . We prove that jitter causes error of order , where is a bandwidth, which is similar to the error caused by jitter in the case of recovering signals from samples.