Bounds on differences of adjacent zeros of Bessel functions and iterative relations between consecutive zeros

Bounds for the distance between adjacent zeros of cylinder functions are given; and are such that ; stands for the th positive zero of the cylinder (Bessel) function , , .

These bounds, together with the application of modified (global) Newton methods based on the monotonic functions and , give rise to forward ( ) and backward ( ) iterative relations between consecutive zeros of cylinder functions.

The problem of finding all the positive real zeros of Bessel functions for any real and inside an interval , 0$">, is solved in a simple way.

     

Computation of differential operators in wavelet coordinates

In [Found. Comput. Math., 2 (2002), pp. 203-245], Cohen, Dahmen, and DeVore proposed an adaptive wavelet algorithm for solving general operator equations. Assuming that the operator defines a boundedly invertible mapping between a Hilbert space and its dual, and that a Riesz basis of wavelet type for this Hilbert space is available, the operator equation is transformed into an equivalent well-posed infinite matrix-vector system. This system is solved by an iterative method, where each application of the infinite stiffness matrix is replaced by an adaptive approximation. It was shown that if the errors of the best linear combinations from the wavelet basis with terms are for some , which is determined by the Besov regularity of the solution and the order of the wavelet basis, then approximations yielded by the adaptive method with terms also have errors of . Moreover, their computation takes only operations, provided , with being a measure of how well the infinite stiffness matrix with respect to the wavelet basis can be approximated by computable sparse matrices. Under appropriate conditions on the wavelet basis, for both differential and singular integral operators and for the relevant range of , in [SIAM J. Math. Anal., 35(5) (2004), pp. 1110-1132] we showed that , assuming that each entry of the stiffness matrix is exactly available at unit cost.

Generally these entries have to be approximated using numerical quadrature. In this paper, restricting ourselves to differential operators, we develop a numerical integration scheme that computes these entries giving an additional error that is consistent with the approximation error, whereas in each column the average computational cost per entry is . As a consequence, we can conclude that the adaptive wavelet algorithm has optimal computational complexity.

     

Lower bounds for the condition number of a real confluent Vandermonde matrix

Lower bounds on the condition number of a real confluent Vandermonde matrix are established in terms of the dimension , or and the largest absolute value among all nodes that define the confluent Vandermonde matrix and the interval that contains the nodes. In particular, it is proved that for any modest (the largest multiplicity of distinct nodes), behaves no smaller than , or than if all nodes are nonnegative. It is not clear whether those bounds are asymptotically sharp for modest .

     

Computing the arithmetic genus of Hilbert modular fourfolds

The Hilbert modular fourfold determined by the totally real quartic number field is a desingularization of a natural compactification of the quotient space , where PSL acts on by fractional linear transformations via the four embeddings of into . The arithmetic genus, equal to one plus the dimension of the space of Hilbert modular cusp forms of weight , is a birational invariant useful in the classification of these varieties. In this work, we describe an algorithm allowing for the automated computation of the arithmetic genus and give sample results.

     

Hermite and Hermite-Fejér interpolation for Stieltjes polynomials

Let and be the ultraspherical polynomials with respect to . Then we denote by the Stieltjes polynomials with respect to satisfying

In this paper, we show uniform convergence of the Hermite-Fejér interpolation polynomials and based on the zeros of the Stieltjes polynomials and the product for and , respectively. To prove these results, we prove that the Lebesgue constants of Hermite-Fejér interpolation operators for the Stieltjes polynomials and the product are optimal, that is, the Lebesgue constants and have optimal order . In the case of the Hermite-Fejér interpolation polynomials for , we prove weighted uniform convergence. Moreover, we give some convergence theorems of Hermite-Fejér and Hermite interpolation polynomials for in weighted norms.

     

Jacobi sums and new families of irreducible polynomials of Gaussian periods

Let 2$">, an -th primitive root of 1, mod a prime number, a primitive root modulo and . We study the Jacobi sums , , where is the least nonnegative integer such that mod . We exhibit a set of properties that characterize these sums, some congruences they satisfy, and a MAPLE program to calculate them. Then we use those results to show how one can construct families , , of irreducible polynomials of Gaussian periods, , of degree , where is a suitable set of primes mod . We exhibit examples of such families for several small values of , and give a MAPLE program to construct more of them.

     

The parameterized algorithm for symplectic (butterfly) matrices

The algorithm is a structure-preserving algorithm for computing the spectrum of symplectic matrices. Any symplectic matrix can be reduced to symplectic butterfly form. A symplectic matrix in butterfly form is uniquely determined by parameters. Using these parameters, we show how one step of the symplectic algorithm for can be carried out in arithmetic operations compared to arithmetic operations when working on the actual symplectic matrix. Moreover, the symplectic structure, which will be destroyed in the numerical process due to roundoff errors when working with a symplectic (butterfly) matrix, will be forced by working just with the parameters.

     

Computing the tame kernel of quadratic imaginary fields

J. Tate has determined the group (called the tame kernel) for six quadratic imaginary number fields where Modifying the method of Tate, H. Qin has done the same for and and M. Skaba for and

In the present paper we discuss the methods of Qin and Skaba, and we apply our results to the field

In the Appendix at the end of the paper K. Belabas and H. Gangl present the results of their computation of for some other values of The results agree with the conjectural structure of given in the paper by Browkin and Gangl.

     

Complexity of inverting the Euler function

Given an integer , how hard is it to find the set of all integers such that , where is the Euler totient function? We present a certain basic algorithm which, given the prime number factorization of , in polynomial time ``on average' (that is, ), finds the set of all such solutions . In fact, in the worst case this set of solutions is exponential in , and so cannot be constructed by a polynomial time algorithm. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that the PARTITION PROBLEM, an NP-complete problem, can be reduced in polynomial (in the input size) time to the problem of deciding whether has a solution, for polynomially (in the input size of the PARTITION PROBLEM) many values of (where the prime factorizations of these are given). What this means is that the problem of deciding whether there even exists a solution to , let alone finding any or all such solutions, is very likely to be intractable. Finally, we establish close links between the problem of inverting the Euler function and the integer factorization problem.

     

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.

     

Small generators of the ideal class group

Assuming the Generalized Riemann Hypothesis, Bach has shown that the ideal class group of a number field can be generated by the prime ideals of having norm smaller than . This result is essential for the computation of the class group and units of by Buchmann's algorithm, currently the fastest known. However, once has been computed, one notices that this bound could have been replaced by a much smaller value, and so much work could have been saved. We introduce here a short algorithm which allows us to reduce Bach's bound substantially, usually by a factor 20 or so. The bound produced by the algorithm is asymptotically worse than Bach's, but favorable constants make it useful in practice.

     

Optimal logarithmic energy points on the unit sphere

We study minimum energy point charges on the unit sphere in , , that interact according to the logarithmic potential , where is the Euclidean distance between points. Such optimal -point configurations are uniformly distributed as . We quantify this result by estimating the spherical cap discrepancy of optimal energy configurations. The estimate is of order . Essential is an improvement of the lower bound of the optimal logarithmic energy which yields the second term in the asymptotical expansion of the optimal energy. Previously, this was known for the unit sphere in only. Furthermore, we present an upper bound for the error of integration for an equally-weighted numerical integration rule with the nodes forming an optimal logarithmic energy configuration. For polynomials of degree at most this bound is as . For continuous functions of satisfying a Lipschitz condition with constant the bound is as .

     

Linear law for the logarithms of the Riemann periods at simple critical zeta zeros

Each simple zero of the Riemann zeta function on the critical line with is a center for the flow of the Riemann xi function with an associated period . It is shown that, as ,

Numerical evaluation leads to the conjecture that this inequality can be replaced by an equality. Assuming the Riemann Hypothesis and a zeta zero separation conjecture for some exponent , we obtain the upper bound . Assuming a weakened form of a conjecture of Gonek, giving a bound for the reciprocal of the derivative of zeta at each zero, we obtain the expected upper bound for the periods so, conditionally, . Indeed, this linear relationship is equivalent to the given weakened conjecture, which implies the zero separation conjecture, provided the exponent is sufficiently large. The frequencies corresponding to the periods relate to natural eigenvalues for the Hilbert-Polya conjecture. They may provide a goal for those seeking a self-adjoint operator related to the Riemann hypothesis.

     

On the irreducibility of Hecke polynomials

Let be the characteristic polynomial of the th Hecke operator acting on the space of cusp forms of weight for the full modular group. We record a simple criterion which can be used to check the irreducibility of the polynomials . Using this criterion with some machine computation, we show that if there exists such that is irreducible and has the full symmetric group as Galois group, then the same is true of for each prime .

     

Limiting set of second order spectra

Let be a self-adjoint operator acting on a Hilbert space . A complex number is in the second order spectrum of relative to a finite-dimensional subspace iff the truncation to of is not invertible. This definition was first introduced in Davies, 1998, and according to the results of Levin and Shargorodsky in 2004, these sets provide a method for estimating eigenvalues free from the problems of spectral pollution. In this paper we investigate various aspects related to the issue of approximation using second order spectra. Our main result shows that under fairly mild hypothesis on the uniform limit of these sets, as increases towards , contain the isolated eigenvalues of of finite multiplicity. Therefore, unlike the majority of the standard methods, second order spectra combine nonpollution and approximation at a very high level of generality.

     

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 .

     

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

     

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.

     

Class numbers of some abelian extensions of rational function fields

Let be a monic irreducible polynomial. In this paper we generalize the determinant formula for of Bae and Kang and the formula for of Jung and Ahn to any subfields of the cyclotomic function field By using these formulas, we calculate the class numbers of all subfields of when and are small.