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.

     

Computation of Stark-Tamagawa units

Let be a totally real number field and let denote an odd prime number. We design an algorithm which computes strong numerical evidence for the validity of the ``Equivariant Tamagawa Number Conjecture' for the -equivariant motive , where is a cyclic extension of degree and group . This conjecture is a very deep refinement of the classical analytic class number formula. In the course of the algorithm, we compute a set of special units which must be considered as a generalization of the (conjecturally existing) Stark units associated to first order vanishing Dirichlet -functions.

     

Linear algebra algorithms for divisors on an algebraic curve

We use an embedding of the symmetric th power of any algebraic curve of genus into a Grassmannian space to give algorithms for working with divisors on , using only linear algebra in vector spaces of dimension , and matrices of size . When the base field is finite, or if has a rational point over , these give algorithms for working on the Jacobian of that require field operations, arising from the Gaussian elimination. Our point of view is strongly geometric, and our representation of points on the Jacobian is fairly simple to deal with; in particular, none of our algorithms involves arithmetic with polynomials. We note that our algorithms have the same asymptotic complexity for general curves as the more algebraic algorithms in Florian Hess' 1999 Ph.D. thesis, which works with function fields as extensions of . However, for special classes of curves, Hess' algorithms are asymptotically more efficient than ours, generalizing other known efficient algorithms for special classes of curves, such as hyperelliptic curves (Cantor 1987), superelliptic curves (Galbraith, Paulus, and Smart 2002), and curves (Harasawa and Suzuki 2000); in all those cases, one can attain a complexity of .

     

High rank elliptic curves with torsion group

We develop an algorithm for bounding the rank of elliptic curves in the family , all of them with torsion group and modular invariant . We use it to look for curves of high rank in this family and present four such curves of rank  and of rank .

     

Chebyshev's bias for composite numbers with restricted prime divisors

Let denote the number of primes with . Chebyshev's bias is the phenomenon for which ``more often' \pi(x;d,r)$">, than the other way around, where is a quadratic nonresidue mod and is a quadratic residue mod . If for every up to some large number, then one expects that for every . Here denotes the number of integers such that every prime divisor of satisfies . In this paper we develop some tools to deal with this type of problem and apply them to show that, for example, for every .

In the process we express the so-called second order Landau-Ramanujan constant as an infinite series and show that the same type of formula holds for a much larger class of constants.

     

On iterates of Möbius transformations on fields

Let be a quadratic polynomial over a splitting field , and be the set of zeros of . We define an associative and commutative binary relation on so that every Möbius transformation with fixed point set is of the form ``plus' for some . This permits an easy proof of Aitken acceleration as well as generalizations of known results concerning Newton's method, the secant method, Halley's method, and higher order methods. If is equipped with a norm, then we give necessary and sufficient conditions for the iterates of a Möbius transformation to converge (necessarily to one of its fixed points) in the norm topology. Finally, we show that if the fixed points of are distinct and the iterates of converge, then Newton's method converges with order 2, and higher order generalizations converge accordingly.

     

Lax theorem and finite volume schemes

This work addresses a theory of convergence for finite volume methods applied to linear equations. A non-consistent model problem posed in an abstract Banach space is proved to be convergent. Then various examples show that the functional framework is non-empty. Convergence with a rate of all TVD schemes for linear advection in 1D is an application of the general result. Using duality techniques and assuming enough regularity of the solution, convergence of the upwind finite volume scheme for linear advection on a 2D triangular mesh is proved in , : provided the solution is in , it proves a rate of convergence in .

     

A complete description of Golay pairs for lengths up to 100

In his 1961 paper, Marcel Golay showed how the search for pairs of binary sequences of length with complementary autocorrelation is at worst a problem. Andres, in his 1977 master's thesis, developed an algorithm which reduced this to a search and investigated lengths up to 58 for existence of pairs. In this paper, we describe refinements to this algorithm, enabling a search at length 82. We find no new pairs at the outstanding lengths 74 and 82. In extending the theory of composition, we are able to obtain a closed formula for the number of pairs of length generated by a primitive pair of length . Combining this with the results of searches at all allowable lengths up to 100, we identify five primitive pairs. All others pairs of lengths less than 100 may be derived using the methods outlined.

     

Iterated function systems, Ruelle operators, and invariant projective measures

We introduce a Fourier-based harmonic analysis for a class of discrete dynamical systems which arise from Iterated Function Systems. Our starting point is the following pair of special features of these systems. (1) We assume that a measurable space comes with a finite-to-one endomorphism which is onto but not one-to-one. (2) In the case of affine Iterated Function Systems (IFSs) in , this harmonic analysis arises naturally as a spectral duality defined from a given pair of finite subsets in of the same cardinality which generate complex Hadamard matrices.

Our harmonic analysis for these iterated function systems (IFS) is based on a Markov process on certain paths. The probabilities are determined by a weight function on . From we define a transition operator acting on functions on , and a corresponding class of continuous -harmonic functions. The properties of the functions in are analyzed, and they determine the spectral theory of . For affine IFSs we establish orthogonal bases in . These bases are generated by paths with infinite repetition of finite words. We use this in the last section to analyze tiles in .

     

Efficient CM-constructions of elliptic curves over finite fields

We present an algorithm that, on input of an integer together with its prime factorization, constructs a finite field and an elliptic curve over for which has order . Although it is unproved that this can be done for all , a heuristic analysis shows that the algorithm has an expected run time that is polynomial in , where is the number of distinct prime factors of . In the cryptographically relevant case where is prime, an expected run time can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order and nextprime.

     

Bounds for computing the tame kernel

The tame kernel of the of a number field  is the kernel of some explicit map , where the product runs over all finite primes  of  and is the residue class field at . When is a set of primes of , containing the infinite ones, we can consider the -unit group  of . Then has a natural image in . The tame kernel is contained in this image if  contains all finite primes of  up to some bound. This is a theorem due to Bass and Tate. An explicit bound for imaginary quadratic fields was given by Browkin. In this article we give a bound, valid for any number field, that is smaller than Browkin's bound in the imaginary quadratic case and has better asymptotics. A simplified version of this bound says that we only have to include in  all primes with norm up to  , where  is the discriminant of . Using this bound, one can find explicit generators for the tame kernel, and a ``long enough' search would also yield all relations. Unfortunately, we have no explicit formula to describe what ``long enough' means. However, using theorems from Keune, we can show that the tame kernel is computable.

     

Recurrence relations and convergence theory of the generalized polar decomposition on Lie groups

The subject matter of this paper is the analysis of some issues related to generalized polar decompositions on Lie groups. This decomposition, depending on an involutive automorphism , is equivalent to a factorization of , being a Lie group, as with and , and was recently discussed by Munthe-Kaas, Quispel and Zanna together with its many applications to numerical analysis. It turns out that, contrary to , an analysis of is a very complicated task. In this paper we derive the series expansion for , obtaining an explicit recurrence relation that completely defines the function in terms of projections on a Lie triple system and a subalgebra of the Lie algebra , and obtain bounds on its region of analyticity. The results presented in this paper have direct application, among others, to linear algebra, integration of differential equations and approximation of the exponential.

     

On splitting methods for Schrödinger-Poisson and cubic nonlinear Schrödinger equations

We give an error analysis of Strang-type splitting integrators for nonlinear Schrödinger equations. For Schrödinger-Poisson equations with an -regular solution, a first-order error bound in the norm is shown and used to derive a second-order error bound in the norm. For the cubic Schrödinger equation with an -regular solution, first-order convergence in the norm is used to obtain second-order convergence in the norm. Basic tools in the error analysis are Lie-commutator bounds for estimating the local error and -conditional stability for error propagation, where for the Schrödinger-Poisson system and for the cubic Schrödinger equation.

     

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.

     

Class numbers of imaginary quadratic fields

The classical class number problem of Gauss asks for a classification of all imaginary quadratic fields with a given class number . The first complete results were for by Heegner, Baker, and Stark. After the work of Goldfeld and Gross-Zagier, the task was a finite decision problem for any . Indeed, after Oesterlé handled , in 1985 Serre wrote, ``No doubt the same method will work for other small class numbers, up to 100, say.' However, more than ten years later, after doing , Wagner remarked that the case seemed impregnable. We complete the classification for all , an improvement of four powers of 2 (arguably the most difficult case) over the previous best results. The main theoretical technique is a modification of the Goldfeld-Oesterlé work, which used an elliptic curve -function with an order 3 zero at the central critical point, to instead consider Dirichlet -functions with low-height zeros near the real line (though the former is still required in our proof). This is numerically much superior to the previous method, which relied on work of Montgomery-Weinberger. Our method is still quite computer-intensive, but we are able to keep the time needed for the computation down to about seven months. In all cases, we find that there is no abnormally large ``exceptional modulus' of small class number, which agrees with the prediction of the Generalised Riemann Hypothesis.

     

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.

     

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.

     

Some new kinds of pseudoprimes

We define some new kinds of pseudoprimes to several bases, which generalize strong pseudoprimes. We call them Sylow -pseudoprimes and elementary Abelian -pseudoprimes. It turns out that every which is a strong pseudoprime to bases 2, 3 and 5, is not a Sylow -pseudoprime to two of these bases for an appropriate prime

We also give examples of strong pseudoprimes to many bases which are not Sylow -pseudoprimes to two bases only, where or