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.

     

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 .

     

Analysis of PSLQ, an integer relation finding algorithm

Let be either the real, complex, or quaternion number system and let be the corresponding integers. Let be a vector in . The vector has an integer relation if there exists a vector , , such that . In this paper we define the parameterized integer relation construction algorithm PSLQ, where the parameter can be freely chosen in a certain interval. Beginning with an arbitrary vector , iterations of PSLQ will produce lower bounds on the norm of any possible relation for . Thus PSLQ can be used to prove that there are no relations for of norm less than a given size. Let be the smallest norm of any relation for . For the real and complex case and each fixed parameter in a certain interval, we prove that PSLQ constructs a relation in less than iterations.

     

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.

     

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.

     

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 .

     

Upper bounds for the prime divisors of Wendt's determinant

Let be an even integer, . The resultant of the polynomials and is known as Wendt's determinant of order . We prove that among the prime divisors of only those which divide or can be larger than , where and is the th Lucas number, except when and . Using this estimate we derive criteria for the nonsolvability of Fermat's congruence.

     

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.

     

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.

     

Some properties of the gamma and psi functions, with applications

In this paper, some monotoneity and concavity properties of the gamma, beta and psi functions are obtained, from which several asymptotically sharp inequalities follow. Applying these properties, the authors improve some well-known results for the volume of the unit ball , the surface area of the unit sphere , and some related constants.

     

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 Postage Stamp Problem: An algorithm to determine the

Given an integral ``stamp" basis with and a positive integer , we define the -range as

. For given and , the extremal basis has the largest possible extremal -range

We give an algorithm to determine the -range. We prove some properties of the -range formula, and we conjecture its form for the extremal -range. We consider parameter bases , where the basis elements are given functions of . For we conjecture the extremal parameter bases for .

     

Elliptic curves with nonsplit mod representations

We calculate explicitly the -invariants of the elliptic curves corresponding to rational points on the modular curve by giving an expression defined over of the -function in terms of the function field generators and of the elliptic curve . As a result we exhibit infinitely many elliptic curves over with nonsplit mod representations.

     

Short effective intervals containing primes in arithmetic progressions and the seven cubes problem

For any and any non-exceptional modulus , we prove that, for large enough ( ), the interval contains a prime in any of the arithmetic progressions modulo . We apply this result to establish that every integer larger than is a sum of seven cubes.

     

Extrapolation methods and derivatives of limits of sequences

Let be an infinite sequence whose limit or antilimit can be approximated very efficiently by applying a suitable extrapolation method E to . Assume that the and hence also are differentiable functions of some parameter , being the limit or antilimit of , and that we need to approximate . A direct way of achieving this would be by applying again a suitable extrapolation method E to the sequence , and this approach has often been used efficiently in various problems of practical importance. Unfortunately, as has been observed at least in some important cases, when and have essentially different asymptotic behaviors as , the approximations to produced by this approach, despite the fact that they are good, do not converge as quickly as those obtained for , and this is puzzling. In this paper we first give a rigorous mathematical explanation of this phenomenon for the cases in which E is the Richardson extrapolation process and E is a generalization of it, thus showing that the phenomenon has very little to do with numerics. Following that, we propose a procedure that amounts to first applying the extrapolation method E to and then differentiating the resulting approximations to , and we provide a thorough convergence and stability analysis in conjunction with the Richardson extrapolation process. It follows from this analysis that the new procedure for has practically the same convergence properties as E for . We show that a very efficient way of implementing the new procedure is by actually differentiating the recursion relations satisfied by the extrapolation method used, and we derive the necessary algorithm for the Richardson extrapolation process. We demonstrate the effectiveness of the new approach with numerical examples that also support the theory. We discuss the application of this approach to numerical integration in the presence of endpoint singularities. We also discuss briefly its application in conjunction with other extrapolation methods.

     

A hidden number problem in small subgroups

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element , where is prime, from rather short strings of the most significant bits of the residue of modulo for several randomly chosen . González Vasco and the first author have recently extended this result to subgroups of of order at least for all and to subgroups of order at least for almost all . Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the multipliers and thus extend this result to subgroups of order at least for all primes . As in the above works, we give applications of our result to the bit security of the Diffie-Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

     

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.

     

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 .

     

More on the total number of prime factors of an odd perfect number

Let denote the sum of the positive divisors of . We say that is perfect if . Currently there are no known odd perfect numbers. It is known that if an odd perfect number exists, then it must be of the form , where are distinct primes and . Define the total number of prime factors of as . Sayers showed that . This was later extended by Iannucci and Sorli to show that . This paper extends these results to show that .