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.

     

Solving polynomials by radicals with roots of unity in minimum depth

Let be an algebraic number field. Let be a root of a polynomial which is solvable by radicals. Let be the splitting field of over . Let be a natural number divisible by the discriminant of the maximal abelian subextension of , as well as the exponent of , the Galois group of over . We show that an optimal nested radical with roots of unity for can be effectively constructed from the derived series of the solvable Galois group of over .

     

Nonexistence conditions of a solution for the congruence

We obtain nonexistence conditions of a solution for of the congruence , where , and are integers, and is a prime power. We give nonexistence conditions of the form for , , , , , and of the form for , , , . Furthermore, we complete some tables concerned with Waring's problem in -adic fields that were computed by Hardy and Littlewood.

     

Normal bases via general Gauss periods

Gauss periods have been used successfully as a tool for constructing normal bases in finite fields. Starting from a primitive th root of unity, one obtains under certain conditions a normal basis for over , where is a prime and for some integer . We generalize this construction by allowing arbitrary integers with , and find in many cases smaller values of than is possible with the previously known approach.

     

Tables of linear congruential generators of different sizes and good lattice structure

We provide sets of parameters for multiplicative linear congruential generators (MLCGs) of different sizes and good performance with respect to the spectral test. For , we take as a modulus the largest prime smaller than , and provide a list of multipliers such that the MLCG with modulus and multiplier has a good lattice structure in dimensions 2 to 32. We provide similar lists for power-of-two moduli , for multiplicative and non-multiplicative LCGs.

     

New Fibonacci and Lucas primes

Extending previous searches for prime Fibonacci and Lucas numbers, all probable prime Fibonacci numbers have been determined for and all probable prime Lucas numbers have been determined for . A rigorous proof of primality is given for and for numbers with , , , , , , , , the prime having 3020 digits. Primitive parts and of composite numbers and have also been tested for probable primality. Actual primality has been established for many of them, including 22 with more than 1000 digits. In a Supplement to the paper, factorizations of numbers and are given for as far as they have been completed, adding information to existing factor tables covering .

     

A posteriori error estimation for variational problems with uniformly convex functionals

The objective of this paper is to introduce a general scheme for deriving a posteriori error estimates by using duality theory of the calculus of variations. We consider variational problems of the form

where is a convex lower semicontinuous functional, is a uniformly convex functional, and are reflexive Banach spaces, and is a bounded linear operator. We show that the main classes of a posteriori error estimates known in the literature follow from the duality error estimate obtained and, thus, can be justified via the duality theory.

     

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 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.

     

On the discrete logarithm in the divisor class group of curves

Let be a curve which is defined over a finite field of characteristic . We show that one can evaluate the discrete logarithm in by operations in . This generalizes a result of Semaev for elliptic curves to curves of arbitrary genus.

     

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 .

     

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.

     

Stability of Runge-Kutta methods for quasilinear parabolic problems

We consider a quasilinear parabolic problem

where , , is a family of sectorial operators in a Banach space with fixed domain . This problem is discretized in time by means of a strongly A()-stable, , Runge-Kutta method. We prove that the resulting discretization is stable, under some natural assumptions on the dependence of with respect to . Our results are useful for studying in norms, , many problems arising in applications. Some auxiliary results for time-dependent parabolic problems are also provided.

     

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.

     

Constructing representations of higher degrees of finite simple groups and covers

Let be a finite group and an irreducible character of . A simple method for constructing a representation affording can be used whenever has a subgroup such that has a linear constituent with multiplicity 1. In this paper we show that (with a few exceptions) if is a simple group or a covering group of a simple group and is an irreducible character of of degree between 32 and 100, then such a subgroup exists.

     

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 .

     

Locking-free finite elements for the Reissner-Mindlin plate

Two new families of Reissner-Mindlin triangular finite elements are analyzed. One family, generalizing an element proposed by Zienkiewicz and Lefebvre, approximates (for the transverse displacement by continuous piecewise polynomials of degree , the rotation by continuous piecewise polynomials of degree plus bubble functions of degree , and projects the shear stress into the space of discontinuous piecewise polynomials of degree . The second family is similar to the first, but uses degree rather than degree continuous piecewise polynomials to approximate the rotation. We prove that for , the errors in the derivatives of the transverse displacement are bounded by and the errors in the rotation and its derivatives are bounded by and , respectively, for the first family, and by and , respectively, for the second family (with independent of the mesh size and plate thickness . These estimates are of optimal order for the second family, and so it is locking-free. For the first family, while the estimates for the derivatives of the transverse displacement are of optimal order, there is a deterioration of order in the approximation of the rotation and its derivatives for small, demonstrating locking of order . Numerical experiments using the lowest order elements of each family are presented to show their performance and the sharpness of the estimates. Additional experiments show the negative effects of eliminating the projection of the shear stress.

     

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 .

     

Tame and wild kernels of quadratic imaginary number fields

For all quadratic imaginary number fields of discriminant
we give the conjectural value of the order of Milnor's group (the tame kernel) where is the ring of integers of Assuming that the order is correct, we determine the structure of the group and of its subgroup (the wild kernel). It turns out that the odd part of the tame kernel is cyclic (with one exception, ).

     

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 .