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

     

Lower bounds for the total stopping time of iterates

The total stopping time of a positive integer is the minimal number of iterates of the function needed to reach the value , and is if no iterate of reaches . It is shown that there are infinitely many positive integers having a finite total stopping time such that 6.14316 \log n.$"> The proof involves a search of trees to depth 60, A heuristic argument suggests that for any constant , a search of all trees to sufficient depth could produce a proof that there are infinitely many such that \gamma\log n.$">It would require a very large computation to search trees to a sufficient depth to produce a proof that the expected behavior of a ``random' iterate, which is occurs infinitely often.

     

Nontrivial Galois module structure of cyclotomic fields

We say a tame Galois field extension with Galois group has trivial Galois module structure if the rings of integers have the property that is a free -module. The work of Greither, Replogle, Rubin, and Srivastav shows that for each algebraic number field other than the rational numbers there will exist infinitely many primes so that for each there is a tame Galois field extension of degree so that has nontrivial Galois module structure. However, the proof does not directly yield specific primes for a given algebraic number field For any cyclotomic field we find an explicit so that there is a tame degree extension with nontrivial Galois module structure.

     

Strong tractability of multivariate integration using quasi-Monte Carlo algorithms

We study quasi-Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of depends on and the dimension . Strong tractability means that it does not depend on and is bounded by a polynomial in . The least possible value of the power of is called the -exponent of strong tractability. Sloan and Wozniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the -exponent of strong tractability is between 1 and 2. However, their proof is not constructive.

In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Wozniakowski's assumption. We show that quasi-Monte Carlo algorithms using Niederreiter's -sequences and Sobol sequences achieve the optimal convergence order for any 0$"> independent of the dimension with a worst case deterministic guarantee (where is the number of function evaluations). This implies that strong tractability with the best -exponent can be achieved in appropriate weighted Sobolev spaces by using Niederreiter's -sequences and Sobol sequences.

     

Class numbers of real cyclotomic fields of prime conductor

The class numbers of the real cyclotomic fields are notoriously hard to compute. Indeed, the number is not known for a single prime . In this paper we present a table of the orders of certain subgroups of the class groups of the real cyclotomic fields for the primes . It is quite likely that these subgroups are in fact equal to the class groups themselves, but there is at present no hope of proving this rigorously. In the last section of the paper we argue --on the basis of the Cohen-Lenstra heuristics-- that the probability that our table is actually a table of class numbers , is at least .

     

Enhanced accuracy by post-processing for finite element methods for hyperbolic equations

We consider the enhancement of accuracy, by means of a simple post-processing technique, for finite element approximations to transient hyperbolic equations. The post-processing is a convolution with a kernel whose support has measure of order one in the case of arbitrary unstructured meshes; if the mesh is locally translation invariant, the support of the kernel is a cube whose edges are of size of the order of only. For example, when polynomials of degree are used in the discontinuous Galerkin (DG) method, and the exact solution is globally smooth, the DG method is of order in the -norm, whereas the post-processed approximation is of order ; if the exact solution is in only, in which case no order of convergence is available for the DG method, the post-processed approximation converges with order in , where is a subdomain over which the exact solution is smooth. Numerical results displaying the sharpness of the estimates are presented.

     

Linear quintuple-product identities

In the first part of this paper, series and product representations of four single-variable triple products , , , and four single-variable quintuple products , , , are defined. Reduced forms and reduction formulas for these eight functions are given, along with formulas which connect them. The second part of the paper contains a systematic computer search for linear trinomial identities. The complete set of such families is found to consist of two 2-parameter families, which are proved using the formulas in the first part of the paper.

     

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.

     

New quadratic polynomials with high densities of prime values

Hardy and Littlewood's Conjecture F implies that the asymptotic density of prime values of the polynomials , is related to the discriminant of via a quantity The larger is, the higher the asymptotic density of prime values for any quadratic polynomial of discriminant . A technique of Bach allows one to estimate accurately for any , given the class number of the imaginary quadratic order with discriminant , and for any 0$"> given the class number and regulator of the real quadratic order with discriminant . The Manitoba Scalable Sieve Unit (MSSU) has shown us how to rapidly generate many discriminants for which is potentially large, and new methods for evaluating class numbers and regulators of quadratic orders allow us to compute accurate estimates of efficiently, even for values of with as many as decimal digits. Using these methods, we were able to find a number of discriminants for which, under the assumption of the Extended Riemann Hypothesis, is larger than any previously known examples.

     

Finite element approximation of -surfaces

In this paper a piecewise linear finite element approximation of -surfaces, or surfaces with constant mean curvature, spanned by a given Jordan curve in is considered. It is proved that the finite element -surfaces converge to the exact -surfaces under the condition that the Jordan curve is rectifiable. Several numerical examples are given.

     

Modular curves of genus 2

We prove that there are exactly genus two curves defined over such that there exists a nonconstant morphism defined over and the jacobian of is -isogenous to the abelian variety attached by Shimura to a newform . We determine the corresponding newforms and present equations for all these curves.

     

Sums of heights of algebraic numbers

For , we consider the set . The polynomials are in , with only mild restrictions, and is the Weil height of . We show that this set is dense in for some effectively computable limit point .

     

A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377

The standard algorithm for testing reducibility of a trinomial of prime degree over requires bits of memory. We describe a new algorithm which requires only bits of memory and significantly fewer memory references and bit-operations than the standard algorithm.

If is a Mersenne prime, then an irreducible trinomial of degree is necessarily primitive. We give primitive trinomials for the Mersenne exponents , , and . The results for extend and correct some computations of Kumada et al. The two results for are primitive trinomials of the highest known degree.

     

Newton-Cotes integration for approximating Stieltjes (generalized Euler) constants

In the Laurent expansion

of the Riemann-Hurwitz zeta function, the coefficients are known as Stieltjes, or generalized Euler, constants. [When , (the Riemann zeta function), and .] We present a new approach to high-precision approximation of . Plots of our results reveal much structure in the growth of the generalized Euler constants. Our results when for , and when for (for such as 53/100, 1/2, etc.) suggest that published bounds on the growth of the Stieltjes constants can be much improved, and lead to several conjectures. Defining , we conjecture that is attained: for any given , for some (and similarly that, given and , is within of for infinitely many ). In addition we conjecture that satisfies for 1$">. We also conjecture that , a special case of a more general conjecture relating the values of and for . Finally, it is known that for . Using this to define for all real 0$">, we conjecture that for nonintegral , is precisely times the -th (Weyl) fractional derivative at of the entire function . We also conjecture that , now defined for all real arguments 0$">, is smooth. Our numerical method uses Newton-Cotes integration formulae for very high-degree interpolating polynomials; it differs in implementation from, but compares in error bounding to, Euler-Maclaurin summation based methods.

     

Corrigenda and addition to ``Computer verification of the Ankeny-Artin-Chowla conjecture for all primes less than '

An error in the program for verifying the Ankeny-Artin-Chowla (AAC) conjecture is reported. As a result, in the case of primes which are , the AAC conjecture has been verified using a different multiple of the regulator of the quadratic field than was meant. However, since any multiple of this regulator is suitable for this purpose, provided that it is smaller than , the main result that the AAC conjecture is true for all the primes which are , remains valid.

As an addition, we have verified the AAC conjecture for all the primes between and , with the corrected program.

     

Maximum norm stability of difference schemes for parabolic equations on overset nonmatching space-time grids

In this paper, theoretical results are described on the maximum norm stability and accuracy of finite difference discretizations of parabolic equations on overset nonmatching space-time grids. We consider parabolic equations containing a linear reaction term on a space-time domain which is decomposed into an overlapping collection of cylindrical subregions of the form , for . Each of the space-time domains are assumed to be independently grided (in parallel) according to the local geometry and space-time regularity of the solution, yielding space-time grids with mesh parameters and . In particular, the different space-time grids need not match on the regions of overlap, and the time steps can differ from one grid to the next. We discretize the parabolic equation on each local grid by employing an explicit or implicit -scheme in time and a finite difference scheme in space satisfying a discrete maximum principle. The local discretizations are coupled together, without the use of Lagrange multipliers, by requiring the boundary values on each space-time grid to match a suitable interpolation of the solution on adjacent grids. The resulting global discretization yields a large system of coupled equations which can be solved by a parallel Schwarz iterative procedure requiring some communication between adjacent subregions. Our analysis employs a contraction mapping argument.

Applications of the results are briefly indicated for reaction-diffusion equations with contractive terms and heterogeneous hyperbolic-parabolic approximations of parabolic equations.

     

Pseudozeros of multivariate polynomials

The pseudozero set of a system of polynomials in complex variables is the subset of which is the union of the zero-sets of all polynomial systems that are near to in a suitable sense. This concept is made precise, and general properties of pseudozero sets are established. In particular it is shown that in many cases of natural interest, the pseudozero set is a semialgebraic set. Also, estimates are given for the size of the projections of pseudozero sets in coordinate directions. Several examples are presented illustrating some of the general theory developed here. Finally, algorithmic ideas are proposed for solving multivariate polynomials.

     

-error estimates for ``shifted' surface spline interpolation on Sobolev space

The accuracy of interpolation by a radial basis function is usually very satisfactory provided that the approximant is reasonably smooth. However, for functions which have smoothness below a certain order associated with the basis function , no approximation power has yet been established. Hence, the purpose of this study is to discuss the -approximation order ( ) of interpolation to functions in the Sobolev space with \max(0,d/2-d/p)$">. We are particularly interested in using the ``shifted' surface spline, which actually includes the cases of the multiquadric and the surface spline. Moreover, we show that the accuracy of the interpolation method can be at least doubled when additional smoothness requirements and boundary conditions are met.