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 .

     

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

     

Constructing nonresidues in finite fields and the extended Riemann hypothesis

We present a new deterministic algorithm for the problem of constructing th power nonresidues in finite fields , where is prime and is a prime divisor of . We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed and , our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if is exponentially large. More generally, assuming the ERH, in time we can construct a set of elements that generates the multiplicative group . An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991.

     

An asymptotic expansion for the incomplete beta function

A new asymptotic expansion is derived for the incomplete beta function , which is suitable for large , small and . This expansion is of the form

where is the incomplete Gamma function ratio and . This form has some advantages over previous asymptotic expansions in this region in which depends on as well as on and .

     

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 .

     

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 the beta expansion for Salem numbers of degree 6

For a given , the beta transformation is defined for by (mod ). The number is said to be a beta number if the orbit is finite, hence eventually periodic. It is known that all Pisot numbers are beta numbers, and it is conjectured that this is true for Salem numbers, but this is known only for Salem numbers of degree . Here we consider some computational and heuristic evidence for the conjecture in the case of Salem numbers of degree , by considering the set of such numbers of trace at most . Although the orbit is small for the majority of these numbers, there are some examples for which the orbit size is shown to exceed and for which the possibility remains that the orbit is infinite. There are also some very large orbits which have been shown to be finite: an example is given for which the preperiod length is and the period length is . This is in contrast to Salem numbers of degree where the orbit size is bounded by . An heuristic probabilistic model is proposed which explains the difference between the degree- and degree- cases. The model predicts that all Salem numbers of degree and should be beta numbers but that degree- Salem numbers can have orbits which are arbitrarily large relative to the size of . Furthermore, the model predicts that a positive proportion of Salem numbers of any fixed degree will not be beta numbers. This latter prediction is not tested here.

     

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

     

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 .

     

Stieltjes Polynomials and Related Quadrature Formulae for a Class of Weight Functions

Consider a (nonnegative) measure with support in the interval such that the respective orthogonal polynomials, above a specific index , satisfy a three-term recurrence relation with constant coefficients. We show that the corresponding Stieltjes polynomials, above the index , have a very simple and useful representation in terms of the orthogonal polynomials. As a result of this, the Gauss-Kronrod quadrature formulae for have all the desirable properties, namely, the interlacing of nodes, their inclusion in the closed interval (under an additional assumption on ), and the positivity of all weights. Furthermore, the interpolatory quadrature formulae based on the zeros of the Stieltjes polynomials have positive weights, and both of these quadrature formulae have elevated degrees of exactness.

     

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.

     

An algorithm for matrix extension and wavelet construction

This paper gives a practical method of extending an matrix , , with Laurent polynomial entries in one complex variable , to a square matrix also with Laurent polynomial entries. If has orthonormal columns when is restricted to the torus , it can be extended to a paraunitary matrix. If has rank for each , it can be extended to a matrix with nonvanishing determinant on . The method is easily implemented in the computer. It is applied to the construction of compactly supported wavelets and prewavelets from multiresolutions generated by several univariate scaling functions with an arbitrary dilation parameter.

     

Complete solutions of a family of quartic Thue and index form equations

Continuing the recent work of the second author, we prove that the diophantine equation

for has exactly 12 solutions except when , when it has 16 solutions. If denotes one of the zeros of , then for we also find all with .

     

-complete sequences of integers

An infinite sequence is -complete if every sufficiently large integer is the sum of such that no one divides the other. We investigate -completeness of sets of the form and with nonnegative.

     

Further investigations with the strong probable prime test

Recently, Damgård, Landrock and Pomerance described a procedure in which a -bit odd number is chosen at random and subjected to random strong probable prime tests. If the chosen number passes all tests, then the procedure will return that number; otherwise, another -bit odd integer is selected and then tested. The procedure ends when a number that passes all tests is found. Let denote the probability that such a number is composite. The authors above have shown that when and . In this paper we will show that this is in fact valid for all and .

     

Cyclotomic Units and Greenberg's Conjecture for Real Quadratic Fields

We give new examples of real quadratic fields for which the Iwasawa invariant and are both zero by calculating cyclotomic units of real cyclic number fields of degree 18.

     

Density computations for real quadratic units

In order to study the density of the set of positive integers for which the negative Pell equation is solvable in integers, we compute the norm of the fundamental unit in certain well-chosen families of real quadratic orders. A fast algorithm that computes 2-class groups rather than units is used. It is random polynomial-time in as the factorization of is a natural part of the input for the values of we encounter. The data obtained provide convincing numerical evidence for the density heuristics for the negative Pell equation proposed by the second author. In particular, an irrational proportion of the real quadratic fields without discriminantal prime divisors congruent to 3 mod 4 should have a fundamental unit of norm .

     

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.

     

On integral bases in relative quadratic extensions

Let be an algebraic number field and a quadratic extension with . We describe a minimal set of elements for generating the integral elements of as an module. A consequence of this theoretical result is an algorithm for constructing such a set. The construction yields a simple procedure for computing an integral basis of as well. In the last section, we present examples of relative integral bases which were computed with the new algorithm and also give some running times.