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 .

     

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.

     

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.

     

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.

     

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.

     

The Euler implicit/explicit scheme for the 2D time-dependent Navier-Stokes equations with smooth or non-smooth initial data

This paper considers the stability and convergence results for the Euler implicit/explicit scheme applied to the spatially discretized two-dimensional (2D) time-dependent Navier-Stokes equations. A Galerkin finite element spatial discretization is assumed, and the temporal treatment is implicit/explict scheme, which is implicit for the linear terms and explicit for the nonlinear term. Here the stability condition depends on the smoothness of the initial data , i.e., the time step condition is in the case of , in the case of and in the case of for mesh size and some positive constant . We provide the -stability of the scheme under the stability condition with and obtain the optimal error estimate of the numerical velocity and the optimal error estimate of the numerical pressure under the stability condition with .

     

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 .

     

About the sharpness of the stability estimates in the Kreiss matrix theorem

One of the conditions in the Kreiss matrix theorem involves the resolvent of the matrices under consideration. This so-called resolvent condition is known to imply, for all , the upper bounds and . Here is the spectral norm, is the constant occurring in the resolvent condition, and the order of is equal to .

It is a long-standing problem whether these upper bounds can be sharpened, for all fixed 1$">, to bounds in which the right-hand members grow much slower than linearly with and with , respectively. In this paper it is shown that such a sharpening is impossible. The following result is proved: for each 0$">, there are fixed values 0, K>1$"> and a sequence of matrices , satisfying the resolvent condition, such that for .

The result proved in this paper is also relevant to matrices whose -pseudospectra lie at a distance not exceeding from the unit disk for all 0$">.

     

On the nonexistence of -cycles for the problem

This article generalizes a proof of Steiner for the nonexistence of -cycles for the problem to a proof for the nonexistence of -cycles. A lower bound for the cycle length is derived by approximating the ratio between numbers in a cycle. An upper bound is found by applying a result of Laurent, Mignotte, and Nesterenko on linear forms in logarithms. Finally numerical calculation of convergents of shows that -cycles cannot exist.

     

Security of the most significant bits of the Shamir message passing scheme

Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a ``hidden' element of a finite field of elements from rather short strings of the most significant bits of the remainder modulo of for several values of selected uniformly at random from . Unfortunately the applications to the computational security of most significant bits of private keys of some finite field exponentiation based cryptosystems given by Boneh and Venkatesan are not quite correct. For the Diffie-Hellman cryptosystem the result of Boneh and Venkatesan has been corrected and generalized in our recent paper. Here a similar analysis is given for the Shamir message passing scheme. The results depend on some bounds of exponential sums.

     

The monic integer transfinite diameter

We study the problem of finding nonconstant monic integer polynomials, normalized by their degree, with small supremum on an interval . The monic integer transfinite diameter is defined as the infimum of all such supremums. We show that if has length , then .

We make three general conjectures relating to the value of for intervals of length less than . We also conjecture a value for where . We give some partial results, as well as computational evidence, to support these conjectures.

We define functions and , which measure properties of the lengths of intervals with on either side of . Upper and lower bounds are given for these functions.

We also consider the problem of determining when is a Farey interval. We prove that a conjecture of Borwein, Pinner and Pritsker concerning this value is true for an infinite family of Farey intervals.

     

Iterated function systems, Ruelle operators, and invariant projective measures

We introduce a Fourier-based harmonic analysis for a class of discrete dynamical systems which arise from Iterated Function Systems. Our starting point is the following pair of special features of these systems. (1) We assume that a measurable space comes with a finite-to-one endomorphism which is onto but not one-to-one. (2) In the case of affine Iterated Function Systems (IFSs) in , this harmonic analysis arises naturally as a spectral duality defined from a given pair of finite subsets in of the same cardinality which generate complex Hadamard matrices.

Our harmonic analysis for these iterated function systems (IFS) is based on a Markov process on certain paths. The probabilities are determined by a weight function on . From we define a transition operator acting on functions on , and a corresponding class of continuous -harmonic functions. The properties of the functions in are analyzed, and they determine the spectral theory of . For affine IFSs we establish orthogonal bases in . These bases are generated by paths with infinite repetition of finite words. We use this in the last section to analyze tiles in .

     

Solving quadratic equations using reduced unimodular quadratic forms

Let be an symmetric matrix with integral entries and with , but not necesarily positive definite. We describe a generalized LLL algorithm to reduce this quadratic form. This algorithm either reduces the quadratic form or stops with some isotropic vector. It is proved to run in polynomial time. We also describe an algorithm for the minimization of a ternary quadratic form: when a quadratic equation is solvable over , a solution can be deduced from another quadratic equation of determinant . The combination of these algorithms allows us to solve efficiently any general ternary quadratic equation over , and this gives a polynomial time algorithm (as soon as the factorization of the determinant of is known).

     

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 .

     

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

     

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.

     

A convergence and stability study of the iterated Lubkin transformation and the -algorithm

In this paper we analyze the convergence and stability of the iterated Lubkin transformation and the -algorithm as these are being applied to sequences whose members behave like as , where and are complex scalars and is a nonnegative integer. We study the three different cases in which (i) , , and (logarithmic sequences), (ii) and (linear sequences), and (iii) (factorial sequences). We show that both methods accelerate the convergence of all three types of sequences. We show also that both methods are stable on linear and factorial sequences, and they are unstable on logarithmic sequences. On the basis of this analysis we propose ways of improving accuracy and stability in problematic cases. Finally, we provide a comparison of these results with analogous results corresponding to the Levin -transformation.

     

On the smallest value of the maximal modulus of an algebraic integer

The house of an algebraic integer of degree is the largest modulus of its conjugates. For , we compute the smallest house of degree , say m. As a consequence we improve Matveev's theorem on the lower bound of m We show that, in this range, the conjecture of Schinzel-Zassenhaus is satisfied. The minimal polynomial of any algebraic integer whose house is equal to m is a factor of a bi-, tri- or quadrinomial. The computations use a family of explicit auxiliary functions. These functions depend on generalizations of the integer transfinite diameter of some compact sets in They give better bounds than the classical ones for the coefficients of the minimal polynomial of an algebraic integer whose house is small.

     

On the primality of

For each prime , let be the product of the primes less than or equal to . We have greatly extended the range for which the primality of and are known and have found two new primes of the first form ( ) and one of the second (). We supply heuristic estimates on the expected number of such primes and compare these estimates to the number actually found.