Finding finite -sequences faster

A -sequence is a sequence of positive integers such that the sums , , are different. When is a power of a prime and is a primitive element in then there are -sequences of size with , which were discovered by R. C. Bose and S. Chowla.

In Theorem 2.1 I will give a faster alternative to the definition. In Theorem 2.2 I will prove that multiplying a sequence by integers relatively prime to the modulus is equivalent to varying . Theorem 3.1 is my main result. It contains a fast method to find primitive quadratic polynomials over when is an odd prime. For fields of characteristic 2 there is a similar, but different, criterion, which I will consider in ``Primitive quadratics reflected in -sequences', to appear in Portugaliae Mathematica (1999).

     

An algorithm for constructing a basis for -spline modules over polynomial rings

Let be a polyhedral complex embedded in the euclidean space and , , denote the set of all -splines on . Then is an -module where is the ring of polynomials in several variables. In this paper we state and prove the existence of an algorithm to write down a free basis for the above -module in terms of obvious linear forms defining common faces of members of . This is done for the case when consists of a finite number of parallelopipeds properly joined amongst themselves along the above linear forms.

     

Remarks on the Schoof-Elkies-Atkin algorithm

Schoof's algorithm computes the number of points on an elliptic curve defined over a finite field . Schoof determines modulo small primes using the characteristic equation of the Frobenius of and polynomials of degree . With the works of Elkies and Atkin, we have just to compute, when is a ``good" prime, an eigenvalue of the Frobenius using polynomials of degree . In this article, we compute the complexity of Müller's algorithm, which is the best known method for determining one eigenvalue and we improve the final step in some cases. Finally, when is ``bad", we describe how to have polynomials of small degree and how to perform computations, in Schoof's algorithm, on -values only.

     

Factoring elementary groups of prime cube order into subsets

Let be a prime and let be the -fold direct product of the cyclic group of order . Rédei conjectured if is the direct product of subsets and , each of which contains the identity element of , then either or does not generate all of . The paper verifies Rédei's conjecture for .

     

Class number bounds and Catalan's equation

We improve a criterion of Inkeri and show that if there is a solution to Catalan's equation

with and prime numbers greater than 3 and both congruent to 3 , then and form a double Wieferich pair. Further, we refine a result of Schwarz to obtain similar criteria when only one of the exponents is congruent to 3 . Indeed, in light of the results proved here it is reasonable to suppose that if , then and form a double Wieferich pair.

     

On the Diophantine equation

If and are positive integers with and , then the equation of the title possesses at most one solution in positive integers and , with the possible exceptions of satisfying , and . The proof of this result relies on a variety of diophantine approximation techniques including those of rational approximation to hypergeometric functions, the theory of linear forms in logarithms and recent computational methods related to lattice-basis reduction. Additionally, we compare and contrast a number of these last mentioned techniques.

     

Detecting perfect powers in essentially linear time

This paper (1) gives complete details of an algorithm to compute approximate th roots; (2) uses this in an algorithm that, given an integer , either writes as a perfect power or proves that is not a perfect power; (3) proves, using Loxton's theorem on multiple linear forms in logarithms, that this perfect-power decomposition algorithm runs in time .

     

Subquadratic-time factoring of polynomials over finite fields

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree over a finite field of constant cardinality in time . Previous algorithms required time . The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree over the finite field with elements, the algorithms use arithmetic operations in .

The new ``baby step/giant step' techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.

     

On -amicable pairs

Let denote Euler's totient function, i.e., the number of positive integers and prime to . We study pairs of positive integers with such that for some integer . We call these numbers -amicable pairs with multiplier , analogously to Carmichael's multiply amicable pairs for the -function (which sums all the divisors of ).

We have computed all the -amicable pairs with larger member and found pairs for which the greatest common divisor is squarefree. With any such pair infinitely many other -amicable pairs can be associated. Among these pairs there are so-called primitive -amicable pairs. We present a table of the primitive -amicable pairs for which the larger member does not exceed . Next, -amicable pairs with a given prime structure are studied. It is proved that a relatively prime -amicable pair has at least twelve distinct prime factors and that, with the exception of the pair , if one member of a -amicable pair has two distinct prime factors, then the other has at least four distinct prime factors. Finally, analogies with construction methods for the classical amicable numbers are shown; application of these methods yields another 79 primitive -amicable pairs with larger member , the largest pair consisting of two 46-digit numbers.

     

Minus class groups of the fields of the -th roots of unity

We show that for any prime number the minus class group of the field of the -th roots of unity admits a finite free resolution of length 1 as a module over the ring . Here denotes complex conjugation in . Moreover, for the primes we show that the minus class group is cyclic as a module over this ring. For these primes we also determine the structure of the minus class group.

     

Multilevel Additive Schwarz Method for the Version of the Galerkin Boundary Element Method

We study a multilevel additive Schwarz method for the - version of the Galerkin boundary element method with geometrically graded meshes. Both hypersingular and weakly singular integral equations of the first kind are considered. As it is well known the - version with geometric meshes converges exponentially fast in the energy norm. However, the condition number of the Galerkin matrix in this case blows up exponentially in the number of unknowns . We prove that the condition number of the multilevel additive Schwarz operator behaves like . As a direct consequence of this we also give the results for the -level preconditioner and also for the - version with quasi-uniform meshes. Numerical results supporting our theory are presented.

     

Multigrid and multilevel methods for nonconforming elements

In this paper we study theoretical properties of multigrid algorithms and multilevel preconditioners for discretizations of second-order elliptic problems using nonconforming rotated finite elements in two space dimensions. In particular, for the case of square partitions and the Laplacian we derive properties of the associated intergrid transfer operators which allow us to prove convergence of the -cycle with any number of smoothing steps and close-to-optimal condition number estimates for -cycle preconditioners. This is in contrast to most of the other nonconforming finite element discretizations where only results for -cycles with a sufficiently large number of smoothing steps and variable -cycle multigrid preconditioners are available. Some numerical tests, including also a comparison with a preconditioner obtained by switching from the nonconforming rotated discretization to a discretization by conforming bilinear elements on the same partition, illustrate the theory.

     

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 .

     

On divisibility of the class number

In this paper, criteria of divisibility of the class number of the real cyclotomic field of a prime conductor and of a prime degree by primes the order modulo of which is , are given. A corollary of these criteria is the possibility to make a computational proof that a given does not divide for any (conductor) such that both are primes. Note that on the basis of Schinzel's hypothesis there are infinitely many such primes .

     

An algorithm for evaluation of discrete logarithms in some nonprime finite fields

In this paper we propose an algorithm for evaluation of logarithms in the finite fields , where the number has a small primitive factor . The heuristic estimate of the complexity of the algorithm is equal to
, where grows to , and is limited by a polynomial in . The evaluation of logarithms is founded on a new congruence of the kind of D. Coppersmith, , which has a great deal of solutions-pairs of polynomials of small degrees.

     

Factors of generalized Fermat numbers

A search for prime factors of the generalized Fermat numbers has been carried out for all pairs with and GCD. The search limit on the factors, which all have the form , was for and for . Many larger primes of this form have also been tried as factors of . Several thousand new factors were found, which are given in our tables.-For the smaller of the numbers, i.e. for , or, if , for , the cofactors, after removal of the factors found, were subjected to primality tests, and if composite with , searched for larger factors by using the ECM, and in some cases the MPQS, PPMPQS, or SNFS. As a result all numbers with are now completely factored.

     

Fast algorithms for discrete polynomial transforms

Consider the Vandermonde-like matrix , where the polynomials satisfy a three-term recurrence relation. If are the Chebyshev polynomials , then coincides with . This paper presents a new fast algorithm for the computation of the matrix-vector product in arithmetical operations. The algorithm divides into a fast transform which replaces with and a subsequent fast cosine transform. The first and central part of the algorithm is realized by a straightforward cascade summation based on properties of associated polynomials and by fast polynomial multiplications. Numerical tests demonstrate that our fast polynomial transform realizes with almost the same precision as the Clenshaw algorithm, but is much faster for .

     

Computing

Let denote the Von Mangoldt function and . We describe an elementary method for computing isolated values of . The complexity of the algorithm is time and space. A table of values of for up to is included, and some times of computation are given.

     

Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities

The smoothing Newton method for solving a system of nonsmooth equations , which may arise from the nonlinear complementarity problem, the variational inequality problem or other problems, can be regarded as a variant of the smoothing method. At the th step, the nonsmooth function is approximated by a smooth function , and the derivative of at is used as the Newton iterative matrix. The merits of smoothing methods and smoothing Newton methods are global convergence and convenience in handling. In this paper, we show that the smoothing Newton method is also superlinearly convergent if is semismooth at the solution and satisfies a Jacobian consistency property. We show that most common smooth functions, such as the Gabriel-Moré function, have this property. As an application, we show that for box constrained variational inequalities if the involved function is -uniform, the iteration sequence generated by the smoothing Newton method will converge to the unique solution of the problem globally and superlinearly (quadratically).

     

Fast evaluation of multiple zeta sums

We show that the multiple zeta sum:

for positive integers with , can always be written as a finite sum of products of rapidly convergent series. Perhaps surprisingly, one may develop fast summation algorithms of such efficiency that the overall complexity can be brought down essentially to that of one-dimensional summation. In particular, for any dimension one may resolve good digits of in arithmetic operations, with the implied big- constant depending only on the set .