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.

     

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.

     

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.

     

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.

     

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.

     

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.

     

Balanced multi-wavelets in

The notion of -balancing was introduced a few years ago as a condition for the construction of orthonormal scaling function vectors and multi-wavelets to ensure the property of preservation/annihilation of scalar-valued discrete polynomial data of order (or degree ), when decomposed by the corresponding matrix-valued low-pass/high-pass filters. While this condition is indeed precise, to the best of our knowledge only the proof for is known. In addition, the formulation of the -balancing condition for is so prohibitively difficult to satisfy that only a very few examples for and vector dimension 2 have been constructed in the open literature. The objective of this paper is to derive various characterizations of the -balancing condition that include the polynomial preservation property as well as equivalent formulations that facilitate the development of methods for the construction purpose. These results are established in the general multivariate and bi-orthogonal settings for any .

     

A finite dimensional realization of the mollifier method for compact operator equations

We introduce and analyze a stable procedure for the approximation of where is the least residual norm solution of the minimal norm of the ill-posed equation , with compact operator between Hilbert spaces, and has some smoothness assumption. Our method is based on a finite number of singular values of and some finite rank operators. Our results are in a more general setting than the one considered by Rieder and Schuster (2000) and Nair and Lal (2003) with special reference to the mollifier method, and it is also applicable under fewer smoothness assumptions on .

     

Solutions of the congruence

To supplement existing data, solutions of are tabulated for primes with and . For , five new solutions 2^{32}$"> are presented. One of these, for , also satisfies the ``reverse' congruence . An effective procedure for searching for such ``double solutions' is described and applied to the range , . Previous to this, congruences are generally considered for any and fixed prime to see where the smallest prime solution occurs.

     

A finite element method for nearly incompressible elasticity problems

A finite element method is considered for dealing with nearly incompressible material. In the case of large deformations the nonlinear character of the volumetric contribution has to be taken into account. The proposed mixed method avoids volumetric locking also in this case and is robust for (with being the well-known Lamé constant). Error estimates for the -norm are crucial in the control of the nonlinear terms.

     

Counting primes in residue classes

We explain how the Meissel-Lehmer-Lagarias-Miller-Odlyzko method for computing can be used for computing efficiently , the number of primes congruent to modulo up to . As an application, we computed the number of prime numbers of the form less than for several values of up to and found a new region where is less than near .

     

Involutions and characters of upper triangular matrix groups

We study the realizability over of representations of the group of upper-triangular matrices over . We prove that all the representations of are realizable over if , but that if , has representations not realizable over . This theorem is a variation on a result that can be obtained by combining work of J. Arregi and A. Vera-López and of the authors, but the proof of the theorem in this paper is much more natural.

     

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.

     

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 .

     

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.

     

Five consecutive positive odd numbers, none of which can be expressed as a sum of two prime powers

In this paper, we prove that there is an arithmetic progression of positive odd numbers for each term of which none of five consecutive odd numbers and can be expressed in the form , where is a prime and are nonnegative integers.

     

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.

     

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 .