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 .

     

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 .

     

Biquadratic reciprocity and a Lucasian primality test

Let be the sequence defined from a given initial value, the seed, , by the recurrence . Then, for a suitable seed , the number (where is odd) is prime iff . In general depends both on and on . We describe a slight modification of this test which determines primality of numbers with a seed which depends only on , provided . In particular, when , odd, we have a test with a single seed depending only on , in contrast with the unmodified test, which, as proved by W. Bosma in Explicit primality criteria for , Math. Comp. 61 (1993), 97-109, needs infinitely many seeds. The proof of validity uses biquadratic reciprocity.

     

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.

     

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 .

     

All first-order averaging techniques for a posteriori finite element error control on unstructured grids are efficient and reliable

All first-order averaging or gradient-recovery operators for lowest-order finite element methods are shown to allow for an efficient a posteriori error estimation in an isotropic, elliptic model problem in a bounded Lipschitz domain in . Given a piecewise constant discrete flux (that is the gradient of a discrete displacement) as an approximation to the unknown exact flux (that is the gradient of the exact displacement), recent results verify efficiency and reliability of

in the sense that is a lower and upper bound of the flux error up to multiplicative constants and higher-order terms. The averaging space consists of piecewise polynomial and globally continuous finite element functions in components with carefully designed boundary conditions. The minimal value is frequently replaced by some averaging operator applied within a simple post-processing to . The result provides a reliable error bound with .

This paper establishes and so equivalence of and . This implies efficiency of for a large class of patchwise averaging techniques which includes the ZZ-gradient-recovery technique. The bound established for tetrahedral finite elements appears striking in that the shape of the elements does not enter: The equivalence is robust with respect to anisotropic meshes. The main arguments in the proof are Ascoli's lemma, a strengthened Cauchy inequality, and elementary calculations with mass matrices.

     

The Brumer-Stark conjecture in some families of extensions of specified degree

As a starting point, an important link is established between Brumer's conjecture and the Brumer-Stark conjecture which allows one to translate recent progress on the former into new results on the latter. For example, if is an abelian extension of relative degree , an odd prime, we prove the -part of the Brumer-Stark conjecture for all odd primes with belonging to a wide class of base fields. In the same setting, we study the -part and -part of Brumer-Stark with no special restriction on and are left with only two well-defined specific classes of extensions that elude proof. Extensive computations were carried out within these two classes and a complete numerical proof of the Brumer-Stark conjecture was obtained in all cases.

     

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.

     

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 .

     

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.

     

Real zeros of real odd Dirichlet -functions

Let be a real odd Dirichlet character of modulus , and let be the associated Dirichlet -function. As a consequence of the work of Low and Purdy, it is known that if and , , , then has no positive real zeros. By a simple extension of their ideas and the advantage of thirty years of advances in computational power, we are able to prove that if , then has no positive real zeros.

     

Inverse inequalities on non-quasi-uniform meshes and application to the mortar element method

We present a range of mesh-dependent inequalities for piecewise constant and continuous piecewise linear finite element functions defined on locally refined shape-regular (but possibly non-quasi-uniform) meshes. These inequalities involve norms of the form for positive and negative and , where is a function which reflects the local mesh diameter in an appropriate way. The only global parameter involved is , the total number of degrees of freedom in the finite element space, and we avoid estimates involving either the global maximum or minimum mesh diameter. Our inequalities include new variants of inverse inequalities as well as trace and extension theorems. They can be used in several areas of finite element analysis to extend results--previously known only for quasi-uniform meshes--to the locally refined case. Here we describe applications to (i) the theory of nonlinear approximation and (ii) the stability of the mortar element method for locally refined meshes.

     

An estimate for the number of integers without large prime factors

denotes the number of positive integers and free of prime factors y$">. Hildebrand and Tenenbaum provided a good approximation of . However, their method requires the solution to the equation , and therefore it needs a large amount of time for the numerical solution of the above equation for large . Hildebrand also showed approximates for , where and is the unique solution to . Let be defined by for 0$">. We show approximates , and also approximates , where . Using these approximations, we give a simple method which approximates within a factor in the range , where is any positive constant.

     

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

     

A sensitive algorithm for detecting the inequivalence of Hadamard matrices

A Hadamard matrix of side is an matrix with every entry either or , which satisfies . Two Hadamard matrices are called equivalent if one can be obtained from the other by some sequence of row and column permutations and negations. To identify the equivalence of two Hadamard matrices by a complete search is known to be an NP hard problem when increases. In this paper, a new algorithm for detecting inequivalence of two Hadamard matrices is proposed, which is more sensitive than those known in the literature and which has a close relation with several measures of uniformity. As an application, we apply the new algorithm to verify the inequivalence of the known inequivalent Hadamard matrices of order ; furthermore, we show that there are at least pairwise inequivalent Hadamard matrices of order . The latter is a new discovery.

     

Convergence of nonconforming -cycle and -cycle multigrid algorithms for second order elliptic boundary value problems

The convergence of -cycle and -cycle multigrid algorithms with a sufficiently large number of smoothing steps is established for nonconforming finite element methods for second order elliptic boundary value problems.

     

Numerical simulation of stochastic evolution equations associated to quantum Markov semigroups

We address the problem of approximating numerically the solutions of stochastic evolution equations on Hilbert spaces , with respect to Brownian motions, arising in the unraveling of backward quantum master equations. In particular, we study the computation of mean values of , where is a linear operator. First, we introduce estimates on the behavior of . Then we characterize the error induced by the substitution of with the solution of a convenient stochastic ordinary differential equation. It allows us to establish the rate of convergence of to , where denotes the explicit Euler method. Finally, we consider an extrapolation method based on the Euler scheme. An application to the quantum harmonic oscillator system is included.

     

Reducing the construction cost of the component-by-component construction of good lattice rules

The construction of randomly shifted rank- lattice rules, where the number of points is a prime number, has recently been developed by Sloan, Kuo and Joe for integration of functions in weighted Sobolev spaces and was extended by Kuo and Joe and by Dick to composite numbers. To construct -dimensional rules, the shifts were generated randomly and the generating vectors were constructed component-by-component at a cost of operations. Here we consider the situation where is the product of two distinct prime numbers and . We still generate the shifts randomly but we modify the algorithm so that the cost of constructing the, now two, generating vectors component-by-component is only operations. This reduction in cost allows, in practice, construction of rules with millions of points. The rules constructed again achieve a worst-case strong tractability error bound, with a rate of convergence for 0$">.

     

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.