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.

     

Random Fibonacci sequences and the number

For the familiar Fibonacci sequence (defined by , and for ), increases exponentially with at a rate given by the golden ratio . But for a simple modification with both additions and subtractions - the random Fibonacci sequences defined by , and for , , where each sign is independent and either or - with probability - it is not even obvious if should increase with . Our main result is that

with probability . Finding the number involves the theory of random matrix products, Stern-Brocot division of the real line, a fractal measure, a computer calculation, and a rounding error analysis to validate the computer calculation.

     

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.

     

Class group frequencies of real quadratic function fields: The degree 4 case

The distribution of ideal class groups of is examined for degree-four monic polynomials when is a finite field of characteristic greater than 3 with or and is irreducible or has an irreducible cubic factor. Particular attention is paid to the distribution of the -Sylow part of the class group, and these results agree with those predicted using the Cohen-Lenstra heuristics to within about 1 part in 10000. An alternative set of conjectures specific to the cases under investigation is in even sharper agreement.

     

Families of irreducible polynomials of Gaussian periods and matrices of cyclotomic numbers

Given an odd prime we show a way to construct large families of polynomials , , where is a set of primes of the form mod and is the irreducible polynomial of the Gaussian periods of degree in . Examples of these families when are worked in detail. We also show, given an integer and a prime mod , how to represent by matrices the Gaussian periods of degree in , and how to calculate in a simple way, with the help of a computer, irreducible polynomials for elements of .

     

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 .

     

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.

     

On the convergence of certain Gauss-type quadrature formulas for unbounded intervals

We consider the convergence of Gauss-type quadrature formulas for the integral , where is a weight function on the half line . The -point Gauss-type quadrature formulas are constructed such that they are exact in the set of Laurent polynomials }, where is a sequence of integers satisfying and . It is proved that under certain Carleman-type conditions for the weight and when or goes to , then convergence holds for all functions for which is integrable on . Some numerical experiments compare the convergence of these quadrature formulas with the convergence of the classical Gauss quadrature formulas for the half line.

     

On fundamental domains of arithmetic Fuchsian groups

Let be a totally real algebraic number field and an order in a quaternion algebra over . Assume that the group of units in with reduced norm equal to is embedded into as an arithmetic Fuchsian group. It is shown how Ford's algorithm can be effectively applied in order to determine a fundamental domain of as well as a complete system of generators of .

     

Tables of curves with many points

These tables record results on curves with many points over finite fields. For relatively small genus () and a small power of or we give in two tables the best presently known bounds for , the maximum number of rational points on a smooth absolutely irreducible projective curve of genus over a field of cardinality . In additional tables we list for a given pair the type of construction of the best curve so far, and we give a reference to the literature where such a curve can be found.

     

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.

     

Computational scales of Sobolev norms with application to preconditioning

This paper provides a framework for developing computationally efficient multilevel preconditioners and representations for Sobolev norms. Specifically, given a Hilbert space and a nested sequence of subspaces , we construct operators which are spectrally equivalent to those of the form . Here , , are positive numbers and is the orthogonal projector onto with . We first present abstract results which show when is spectrally equivalent to a similarly constructed operator defined in terms of an approximation of , for . We show that these results lead to efficient preconditioners for discretizations of differential and pseudo-differential operators of positive and negative order. These results extend to sums of operators. For example, singularly perturbed problems such as can be preconditioned uniformly independently of the parameter . We also show how to precondition an operator which results from Tikhonov regularization of a problem with noisy data. Finally, we describe how the technique provides computationally efficient bounded discrete extensions which have applications to domain decomposition.

     

Salem numbers of negative trace

We prove that, for all , there are Salem numbers of degree and trace , and that the number of such Salem numbers is . As a consequence, it follows that the number of totally positive algebraic integers of degree and trace is also .

     

A modification of Shanks' baby-step giant-step algorithm

I describe a modification to Shanks' baby-step giant-step algorithm for computing the order of an element of a group , assuming is finite. My method has the advantage of being able to compute quickly, which Shanks' method fails to do when the order of is infinite, unknown, or much larger than . I describe the algorithm in detail. I also present the results of implementations of my algorithm, as well as those of a similar algorithm developed by Buchmann, Jacobson, and Teske, for calculating the order of various ideal classes of imaginary quadratic orders.

     

Using number fields to compute logarithms in finite fields

We describe an adaptation of the number field sieve to the problem of computing logarithms in a finite field. We conjecture that the running time of the algorithm, when restricted to finite fields of an arbitrary but fixed degree, is where is the cardinality of the field, and the is for . The number field sieve factoring algorithm is conjectured to factor a number the size of in the same amount of time.

     

The third largest prime divisor of an odd perfect number exceeds one hundred

Let denote the sum of positive divisors of the natural number . Such a number is said to be perfect if . It is well known that a number is even and perfect if and only if it has the form where is prime.

It is unknown whether or not odd perfect numbers exist, although many conditions necessary for their existence have been found. For example, Cohen and Hagis have shown that the largest prime divisor of an odd perfect number must exceed , and Iannucci showed that the second largest must exceed . In this paper, we prove that the third largest prime divisor of an odd perfect number must exceed 100.

     

On a unit group generated by special values of Siegel modular functions

There has been important progress in constructing units and -units associated to curves of genus 2 or 3. These approaches are based mainly on the consideration of properties of Jacobian varieties associated to hyperelliptic curves of genus 2 or 3. In this paper, we construct a unit group of the ray class field of modulo 6 with full rank by special values of Siegel modular functions and circular units. We note that . Our construction of units is number theoretic, and closely based on Shimura's work describing explicitly the Galois actions on the special values of theta functions.

     

Rudin-Shapiro-like polynomials in

We examine sequences of polynomials with coefficients constructed using the iterations , where is the degree of and is the reciprocal polynomial of . If these generate the Rudin-Shapiro polynomials. We show that the norm of these polynomials is explicitly computable. We are particularly interested in the case where the iteration produces sequences with smallest possible asymptotic norm (or, equivalently, with largest possible asymptotic merit factor). The Rudin-Shapiro polynomials form one such sequence.

We determine all of degree less than 40 that generate sequences under the iteration with this property. These sequences have asymptotic merit factor 3. The first really distinct example has a of degree 19.

     

Improving the parallelized Pollard lambda search on anomalous binary curves

The best algorithm known for finding logarithms on an elliptic curve is the (parallelized) Pollard lambda collision search. We show how to apply a Pollard lambda search on a set of equivalence classes derived from , which requires fewer iterations than the standard approach. In the case of anomalous binary curves over , the new approach speeds up the standard algorithm by a factor of .