On strong tractability of weighted multivariate integration

We prove that for every dimension and every number of points, there exists a point-set whose -weighted unanchored discrepancy is bounded from above by independently of provided that the sequence has for some (even arbitrarily large) . Here is a positive number that could be chosen arbitrarily close to zero and depends on but not on or . This result yields strong tractability of the corresponding integration problems including approximation of weighted integrals over unbounded domains such as . It also supplements the results that provide an upper bound of the form when .

     

Computation of relative class numbers of CM-fields by using Hecke -functions

We develop an efficient technique for computing values at of Hecke -functions. We apply this technique to the computation of relative class numbers of non-abelian CM-fields which are abelian extensions of some totally real subfield . We note that the smaller the degree of the more efficient our technique is. In particular, our technique is very efficient whenever instead of simply choosing (the maximal totally real subfield of ) we can choose real quadratic. We finally give examples of computations of relative class numbers of several dihedral CM-fields of large degrees and of several quaternion octic CM-fields with large discriminants.

     

The generalized triangular decomposition

Given a complex matrix , we consider the decomposition , where is upper triangular and and have orthonormal columns. Special instances of this decomposition include the singular value decomposition (SVD) and the Schur decomposition where is an upper triangular matrix with the eigenvalues of on the diagonal. We show that any diagonal for can be achieved that satisfies Weyl's multiplicative majorization conditions:

where is the rank of , is the -th largest singular value of , and is the -th largest (in magnitude) diagonal element of . Given a vector which satisfies Weyl's conditions, we call the decomposition , where is upper triangular with prescribed diagonal , the generalized triangular decomposition (GTD). A direct (nonrecursive) algorithm is developed for computing the GTD. This algorithm starts with the SVD and applies a series of permutations and Givens rotations to obtain the GTD. The numerical stability of the GTD update step is established. The GTD can be used to optimize the power utilization of a communication channel, while taking into account quality of service requirements for subchannels. Another application of the GTD is to inverse eigenvalue problems where the goal is to construct matrices with prescribed eigenvalues and singular values.

     

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.

     

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.

     

On the absolute Mahler measure of polynomials having all zeros in a sector. II

Let be an algebraic integer of degree , not or a root of unity, all of whose conjugates are confined to a sector . In the paper On the absolute Mahler measure of polynomials having all zeros in a sector, G. Rhin and C. Smyth compute the greatest lower bound of the absolute Mahler measure ( of , for belonging to nine subintervals of . In this paper, we improve the result to thirteen subintervals of and extend some existing subintervals.

     

Fast algorithms for discrete polynomial transforms

Consider the Vandermonde-like matrix , where the polynomials satisfy a three-term recurrence relation. If are the Chebyshev polynomials , then coincides with . This paper presents a new fast algorithm for the computation of the matrix-vector product in arithmetical operations. The algorithm divides into a fast transform which replaces with and a subsequent fast cosine transform. The first and central part of the algorithm is realized by a straightforward cascade summation based on properties of associated polynomials and by fast polynomial multiplications. Numerical tests demonstrate that our fast polynomial transform realizes with almost the same precision as the Clenshaw algorithm, but is much faster for .

     

Visible evidence for the Birch and Swinnerton-Dyer conjecture for modular abelian varieties of analytic rank zero

This paper provides evidence for the Birch and Swinnerton-Dyer conjecture for analytic rank  abelian varieties  that are optimal quotients of attached to newforms. We prove theorems about the ratio , develop tools for computing with , and gather data about certain arithmetic invariants of the nearly abelian varieties of level . Over half of these have analytic rank , and for these we compute upper and lower bounds on the conjectural order of  . We find that there are at least such for which the Birch and Swinnerton-Dyer conjecture implies that is divisible by an odd prime, and we prove for of these that the odd part of the conjectural order of really divides by constructing nontrivial elements of using visibility theory. We also give other evidence for the conjecture. The appendix, by Cremona and Mazur, fills in some gaps in the theoretical discussion in their paper on visibility of Shafarevich-Tate groups of elliptic curves.

     

On the computation of all extensions of a -adic field of a given degree

Let be a -adic field. It is well-known that has only finitely many extensions of a given finite degree. Krasner has given formulae for the number of extensions of a given degree and discriminant. Following his work, we present an algorithm for the computation of generating polynomials for all extensions of a given degree and discriminant.

     

Wavelet bases in

Some years ago, compactly supported divergence-free wavelets were constructed which also gave rise to a stable (biorthogonal) wavelet splitting of . These bases have successfully been used both in the analysis and numerical treatment of the Stokes and Navier-Stokes equations. In this paper, we construct stable wavelet bases for the stream function spaces . Moreover, -free vector wavelets are constructed and analysed. The relationship between and are expressed in terms of these wavelets. We obtain discrete (orthogonal) Hodge decompositions.

Our construction works independently of the space dimension, but in terms of general assumptions on the underlying wavelet systems in that are used as building blocks. We give concrete examples of such bases for tensor product and certain more general domains . As an application, we obtain wavelet multilevel preconditioners in and .

     

The irreducibility of some level 1 Hecke polynomials

Let be the characteristic polynomial of the Hecke operator acting on the space of level 1 cusp forms . We show that is irreducible and has full Galois group over  for and ,  prime.

     

On quadratic fields with large 3-rank

Davenport and Heilbronn defined a bijection between classes of binary cubic forms and classes of cubic fields, which has been used to tabulate the latter. We give a simpler proof of their theorem then analyze and improve the table-building algorithm. It computes the multiplicities of the general cubic discriminants (real or imaginary) up to in time and space , or more generally in time and space for a freely chosen positive . A variant computes the -ranks of all quadratic fields of discriminant up to with the same time complexity, but using only units of storage. As an application we obtain the first real quadratic fields with , and prove that is the smallest imaginary quadratic field with -rank equal to .

     

Two efficient algorithms for the computation of ideal sums in quadratic orders

This paper deals with two different asymptotically fast algorithms for the computation of ideal sums in quadratic orders. If the class number of the quadratic number field is equal to 1, these algorithms can be used to calculate the GCD in the quadratic order. We show that the calculation of an ideal sum in a fixed quadratic order can be done as fast as in up to a constant factor, i.e., in where bounds the size of the operands and denotes an upper bound for the multiplication time of -bit integers. Using Schönhage-Strassen's asymptotically fast multiplication for -bit integers, we achieve

     

On irregular prime power divisors of the Bernoulli numbers

Let ( ) denote the usual th Bernoulli number. Let be a positive even integer where or . It is well known that the numerator of the reduced quotient is a product of powers of irregular primes. Let be an irregular pair with . We show that for every the congruence has a unique solution where and . The sequence defines a -adic integer which is a zero of a certain -adic zeta function originally defined by T. Kubota and H. W. Leopoldt. We show some properties of these functions and give some applications. Subsequently we give several computations of the (truncated) -adic expansion of for irregular pairs with below 1000.

     

Error estimates for semi-discrete gauge methods for the Navier-Stokes equations

The gauge formulation of the Navier-Stokes equations for incompressible fluids is a new projection method. It splits the velocity in terms of auxiliary (nonphysical) variables and and replaces the momentum equation by a heat-like equation for and the incompressibility constraint by a diffusion equation for . This paper studies two time-discrete algorithms based on this splitting and the backward Euler method for with explicit boundary conditions and shows their stability and rates of convergence for both velocity and pressure. The analyses are variational and hinge on realistic regularity requirements on the exact solution and data. Both Neumann and Dirichlet boundary conditions are, in principle, admissible for but a compatibility restriction for the latter is uncovered which limits its applicability.

     

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

     

An analysis of the Rayleigh-Ritz method for approximating eigenspaces

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.

     

All first-order averaging techniques for a posteriori finite element error control on unstructured grids are efficient and reliable

All first-order averaging or gradient-recovery operators for lowest-order finite element methods are shown to allow for an efficient a posteriori error estimation in an isotropic, elliptic model problem in a bounded Lipschitz domain in . Given a piecewise constant discrete flux (that is the gradient of a discrete displacement) as an approximation to the unknown exact flux (that is the gradient of the exact displacement), recent results verify efficiency and reliability of

in the sense that is a lower and upper bound of the flux error up to multiplicative constants and higher-order terms. The averaging space consists of piecewise polynomial and globally continuous finite element functions in components with carefully designed boundary conditions. The minimal value is frequently replaced by some averaging operator applied within a simple post-processing to . The result provides a reliable error bound with .

This paper establishes and so equivalence of and . This implies efficiency of for a large class of patchwise averaging techniques which includes the ZZ-gradient-recovery technique. The bound established for tetrahedral finite elements appears striking in that the shape of the elements does not enter: The equivalence is robust with respect to anisotropic meshes. The main arguments in the proof are Ascoli's lemma, a strengthened Cauchy inequality, and elementary calculations with mass matrices.

     

Finite SAGBI bases for polynomial invariants of conjugates of alternating groups

It is well-known, that the ring of polynomial invariants of the alternating group has no finite SAGBI basis with respect to the lexicographical order for any number of variables . This note proves the existence of a nonsingular matrix such that the ring of polynomial invariants , where denotes the conjugate of with respect to , has a finite SAGBI basis for any .     

A new bound for the smallest

Let denote the number of primes and let denote the usual integral logarithm of . We prove that there are at least integer values of in the vicinity of with . This improves earlier bounds of Skewes, Lehman, and te Riele. We also plot more than 10000 values of in four different regions, including the regions discovered by Lehman, te Riele, and the authors of this paper, and a more distant region in the vicinity of , where appears to exceed by more than . The plots strongly suggest, although upper bounds derived to date for are not sufficient for a proof, that exceeds for at least integers in the vicinity of . If it is possible to improve our bound for by finding a sign change before , our first plot clearly delineates the potential candidates. Finally, we compute the logarithmic density of and find that as departs from the region in the vicinity of , the density is , and that it varies from this by no more than over the next integers. This should be compared to Rubinstein and Sarnak.