Asymptotic semismoothness probabilities

We call an integer semismooth with respect to and if each of its prime factors is , and all but one are . Such numbers are useful in various factoring algorithms, including the quadratic sieve. Let be the asymptotic probability that a random integer is semismooth with respect to and . We present new recurrence relations for and related functions. We then give numerical methods for computing , tables of , and estimates for the error incurred by this asymptotic approximation.

     

Explicit bounds for primes in residue classes

Let be an abelian extension of number fields, with . Let and denote the absolute discriminant and degree of . Let denote an element of the Galois group of . We prove the following theorems, assuming the Extended Riemann Hypothesis:

(1)

There is a degree- prime of such that , satisfying .

(2)

There is a degree- prime of such that generates
the same group as , satisfying .

(3)

For , there is a prime such that , satisfying
.

In (1) and (2) we can in fact take to be unramified in . A special case of this result is the following.

(4)

If , the least prime satisfies
.

It follows from our proof that (1)--(3) also hold for arbitrary Galois extensions, provided we replace by its conjugacy class . Our theorems lead to explicit versions of (1)--(4), including the following: the least prime is less than .

     

The versions of the finite element method for problems with boundary layers

We study the uniform approximation of boundary layer functions for , , by the and versions of the finite element method. For the version (with fixed mesh), we prove super-exponential convergence in the range . We also establish, for this version, an overall convergence rate of in the energy norm error which is uniform in , and show that this rate is sharp (up to the term) when robust estimates uniform in are considered. For the version with variable mesh (i.e., the version), we show that exponential convergence, uniform in , is achieved by taking the first element at the boundary layer to be of size . Numerical experiments for a model elliptic singular perturbation problem show good agreement with our convergence estimates, even when few degrees of freedom are used and when is as small as, e.g., . They also illustrate the superiority of the approach over other methods, including a low-order version with optimal ``exponential" mesh refinement. The estimates established in this paper are also applicable in the context of corresponding spectral element methods.

     

Solvability of norm equations over cyclic number fields of prime degree

Let be an abelian number field of prime degree , and let be a nonzero rational number. We describe an algorithm which takes as input and the minimal polynomial of over , and determines if is a norm of an element of . We show that, if we ignore the time needed to obtain a complete factorization of and a complete factorization of the discriminant of , then the algorithm runs in time polynomial in the size of the input. As an application, we give an algorithm to test if a cyclic algebra over is a division algebra.

     

Results and estimates on pseudopowers

Let be a positive integer. We say looks like a power of 2 modulo a prime if there exists an integer such that . First, we provide a simple proof of the fact that a positive integer which looks like a power of modulo all but finitely many primes is in fact a power of . Next, we define an -pseudopower of the base to be a positive integer that is not a power of , but looks like a power of modulo all primes . Let denote the least such . We give an unconditional upper bound on , a conditional result (on ERH) that gives a lower bound, and a heuristic argument suggesting that is about for a certain constant . We compare our heuristic model with numerical data obtained by a sieve. Some results for bases other than are also given.

     

On beta expansions for Pisot numbers

Given a number , the beta-transformation is defined for by (mod 1). The number is said to be a beta-number if the orbit is finite, hence eventually periodic. In this case is the root of a monic polynomial with integer coefficients called the characteristic polynomial of . If is the minimal polynomial of , then for some polynomial . It is the factor which concerns us here in case is a Pisot number. It is known that all Pisot numbers are beta-numbers, and it has often been asked whether must be cyclotomic in this case, particularly if . We answer this question in the negative by an examination of the regular Pisot numbers associated with the smallest 8 limit points of the Pisot numbers, by an exhaustive enumeration of the irregular Pisot numbers in (an infinite set), by a search up to degree in , to degree in , and to degree in . We find the smallest counterexample, the counterexample of smallest degree, examples where is nonreciprocal, and examples where is reciprocal but noncyclotomic. We produce infinite sequences of these two types which converge to from above, and infinite sequences of with nonreciprocal which converge to from below and to the th smallest limit point of the Pisot numbers from both sides. We conjecture that these are the only limit points of such numbers in . The Pisot numbers for which is cyclotomic are related to an interesting closed set of numbers introduced by Flatto, Lagarias and Poonen in connection with the zeta function of . Our examples show that the set of Pisot numbers is not a subset of .

     

Expansion and Estimation of the Range of Nonlinear Functions

Many verification algorithms use an expansion , for , where the set of matrices is usually computed as a gradient or by means of slopes. In the following, an expansion scheme is described which frequently yields sharper inclusions for . This allows also to compute sharper inclusions for the range of over a domain. Roughly speaking, has to be given by means of a computer program. The process of expanding can then be fully automatized. The function need not be differentiable. For locally convex or concave functions special improvements are described. Moreover, in contrast to other methods, may be empty without implying large overestimations for . This may be advantageous in practical applications.

     

Computation of -invariants of real quadratic fields

Let be a real quadratic field and an odd prime number which splits in . In a previous work, the author gave a sufficient condition for the Iwasawa invariant of the cyclotomic -extension of to be zero. The purpose of this paper is to study the case of this result and give new examples of with , by using information on the initial layer of the cyclotomic -extension of .

     

Computing : the Meissel, Lehmer, Lagarias, Miller, Odlyzko method

Let denote the number of primes . Our aim in this paper is to present some refinements of a combinatorial method for computing single values of , initiated by the German astronomer Meissel in 1870, extended and simplified by Lehmer in 1959, and improved in 1985 by Lagarias, Miller and Odlyzko. We show that it is possible to compute in time and space. The algorithm has been implemented and used to compute .

     

Which Circulant Preconditioner is Better?

The eigenvalue clustering of matrices and is experimentally studied, where , and respectively are Toeplitz matrices, Strang, and optimal circulant preconditioners generated by the Fourier expansion of a function . Some illustrations are given to show how the clustering depends on the smoothness of and which preconditioner is preferable. An original technique for experimental exploration of the clustering rate is presented. This technique is based on the bisection idea and on the Toeplitz decomposition of a three-matrix product , where is a Toeplitz matrix and is a circulant. In particular, it is proved that the Toeplitz (displacement) rank of is not greater than 4, provided that and are symmetric.

     

Computing the canonical height on K3 surfaces

Let be a surface in given by the intersection of a (1,1)-form and a (2,2)-form. Then is a K3 surface with two noncommuting involutions and . In 1991 the second author constructed two height functions and which behave canonically with respect to and , and in 1993 together with the first author showed in general how to decompose such canonical heights into a sum of local heights . We discuss how the geometry of the surface is related to formulas for the local heights, and we give practical algorithms for computing the involutions , , the local heights , , and the canonical heights , .

     

On Quadrature Convergence of Extended Lagrange Interpolation

Quadrature convergence of the extended Lagrange interpolant for any continuous function is studied, where the interpolation nodes are the zeros of an orthogonal polynomial of degree and the zeros of the corresponding ``induced' orthogonal polynomial of degree . It is found that, unlike convergence in the mean, quadrature convergence does hold for all four Chebyshev weight functions. This is shown by establishing the positivity of the underlying quadrature rule, whose weights are obtained explicitly. Necessary and sufficient conditions for positivity are also obtained in cases where the nodes and interlace, and the conditions are checked numerically for the Jacobi weight function with parameters and . It is conjectured, in this case, that quadrature convergence holds for .

     

Simultaneous Pell Equations

Let and be positive integers with . We shall call the simultaneous Diophantine equations

simultaneous Pell equations in and . Each such pair has the trivial solution but some pairs have nontrivial solutions too. For example, if and , then is a solution. Using theorems due to Baker, Davenport, and Waldschmidt, it is possible to show that the number of solutions is always finite, and it is possible to give a complete list of them. In this paper we report on the solutions when .

     

Some New Error Estimates for Ritz--Galerkin Methods with Minimal Regularity Assumptions

New uniform error estimates are established for finite element approximations of solutions of second-order elliptic equations using only the regularity assumption . Using an Aubin--Nitsche type duality argument we show for example that, for arbitrary (fixed) sufficiently small, there exists an such that for

Here, denotes the norm on the Sobolev space . Other related results are established.

     

Two new points in the spectrum of the absolute Mahler measure of totally positive algebraic integers

For totally positive algebraic integers of degree , we consider the set of values of , where is the Mahler measure of . C. J. Smyth has found the four smallest values of and conjectured that the fifth point is . We prove that this is so and, moreover, we give the sixth point of .

     

Construction of Local Quartic Spline Elements for Optimal-Order Approximation

This paper is concerned with a study of approximation order and construction of locally supported elements for the space of (piecewise polynomial) functions on an arbitrary triangulation of a connected polygonal domain in . It is well known that even when is a three-directional mesh , the order of approximation of is only 4, not 5. The objective of this paper is two-fold: (i) A local Clough-Tocher refinement procedure of an arbitrary triangulation is introduced so as to yield the optimal (fifth) order of approximation, where locality means that only a few isolated triangles need refinement, and (ii) locally supported Hermite elements are constructed to achieve the optimal order of approximation.

     

Quality Local Refinement of Tetrahedral Meshes Based on 8-Subtetrahedron Subdivision

Let be a tetrahedral mesh. We present a 3-D local refinement algorithm for which is mainly based on an 8-subtetrahedron subdivision procedure, and discuss the quality of refined meshes generated by the algorithm. It is proved that any tetrahedron produces a finite number of classes of similar tetrahedra, independent of the number of refinement levels. Furthermore, , where , is a positive constant independent of and the number of refinement levels, is any refined tetrahedron of , and is a tetrahedron shape measure. It is also proved that local refinements on tetrahedra can be smoothly extended to their neighbors to maintain a conforming mesh. Experimental results show that the ratio of the number of tetrahedra actually refined to the number of tetrahedra chosen for refinement is bounded above by a small constant.

     

Spontaneous Generation of Modular Invariants

It is possible to compute and its modular equations with no perception of its related classical group structure except at . We start by taking, for prime, an unknown ``-Newtonian' polynomial equation with arbitrary coefficients (based only on Newton's polygon requirements at for and ). We then ask which choice of coefficients of leads to some consistent Laurent series solution , (where . It is conjectured that if the same Laurent series works for -Newtonian polynomials of two or more primes , then there is only a bounded number of choices for the Laurent series (to within an additive constant). These choices are essentially from the set of ``replicable functions,' which include more classical modular invariants, particularly . A demonstration for orders and is done by computation. More remarkably, if the same series works for the -Newtonian polygons of 15 special ``Fricke-Monster' values of , then is (essentially) determined uniquely. Computationally, this process stands alone, and, in a sense, modular invariants arise ``spontaneously.'

     

Turán's Pure Power Sum Problem

Let be complex numbers, and consider the power sums , . Put , where the minimum is over all possible complex numbers satisfying the above. Turán conjectured that , for some positive absolute constant. Atkinson proved this conjecture by showing . It is now known that , for . Determining whether or approaches some other limiting value as is still an open problem. Our calculations show that an upper bound for decreases for , suggesting that decreases to a limiting value less than as .