Analysis of PSLQ, an integer relation finding algorithm

Let be either the real, complex, or quaternion number system and let be the corresponding integers. Let be a vector in . The vector has an integer relation if there exists a vector , , such that . In this paper we define the parameterized integer relation construction algorithm PSLQ, where the parameter can be freely chosen in a certain interval. Beginning with an arbitrary vector , iterations of PSLQ will produce lower bounds on the norm of any possible relation for . Thus PSLQ can be used to prove that there are no relations for of norm less than a given size. Let be the smallest norm of any relation for . For the real and complex case and each fixed parameter in a certain interval, we prove that PSLQ constructs a relation in less than iterations.

     

Explicit values of multi-dimensional Kloosterman sums for prime powers, II

For any integer fix , and let denote the group of reduced residues modulo . Let , a power of a prime . The hyper-Kloosterman sums of dimension are defined for by

where denotes the multiplicative inverse of modulo .

Salie evaluated in the classical setting for even , and for odd with . Later, Smith provided formulas that simplified the computation of in these cases for . Recently, Cochrane, Liu and Zheng computed upper bounds for in the general case , stopping short of their explicit evaluation. Here I complete the computation they initiated to obtain explicit values for the Kloosterman sums for , relying on basic properties of some simple specialized exponential sums. The treatment here is more elementary than the author's previous determination of these Kloosterman sums using character theory and -adic methods. At the least, it provides an alternative, independent evaluation of the Kloosterman sums.

     

Sharply localized pointwise and estimates for finite element methods for quasilinear problems

We establish pointwise and estimates for finite element methods for a class of second-order quasilinear elliptic problems defined on domains in . These estimates are localized in that they indicate that the pointwise dependence of the error on global norms of the solution is of higher order. Our pointwise estimates are similar to and rely on results and analysis techniques of Schatz for linear problems. We also extend estimates of Schatz and Wahlbin for pointwise differences in pointwise errors to quasilinear problems. Finally, we establish estimates for the error in , where is a subdomain. These negative norm estimates are novel for linear as well as for nonlinear problems. Our analysis heavily exploits the fact that Galerkin error relationships for quasilinear problems may be viewed as perturbed linear error relationships, thus allowing easy application of properly formulated results for linear problems.

     

Corrigenda and addition to ``Computer verification of the Ankeny-Artin-Chowla conjecture for all primes less than '

An error in the program for verifying the Ankeny-Artin-Chowla (AAC) conjecture is reported. As a result, in the case of primes which are , the AAC conjecture has been verified using a different multiple of the regulator of the quadratic field than was meant. However, since any multiple of this regulator is suitable for this purpose, provided that it is smaller than , the main result that the AAC conjecture is true for all the primes which are , remains valid.

As an addition, we have verified the AAC conjecture for all the primes between and , with the corrected program.

     

On the modular curves

Let denote an elliptic curve over and the modular curve classifying the elliptic curves over such that the representations of in the 7-torsion points of and of are symplectically isomorphic. In case is given by a Weierstraß equation such that the invariant is a square, we exhibit here nontrivial points of . From this we deduce an infinite family of curves for which has at least four nontrivial points.

     

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 .

     

Class numbers of real cyclotomic fields of prime conductor

The class numbers of the real cyclotomic fields are notoriously hard to compute. Indeed, the number is not known for a single prime . In this paper we present a table of the orders of certain subgroups of the class groups of the real cyclotomic fields for the primes . It is quite likely that these subgroups are in fact equal to the class groups themselves, but there is at present no hope of proving this rigorously. In the last section of the paper we argue --on the basis of the Cohen-Lenstra heuristics-- that the probability that our table is actually a table of class numbers , is at least .

     

On quadratic fields with large 3-rank

Davenport and Heilbronn defined a bijection between classes of binary cubic forms and classes of cubic fields, which has been used to tabulate the latter. We give a simpler proof of their theorem then analyze and improve the table-building algorithm. It computes the multiplicities of the general cubic discriminants (real or imaginary) up to in time and space , or more generally in time and space for a freely chosen positive . A variant computes the -ranks of all quadratic fields of discriminant up to with the same time complexity, but using only units of storage. As an application we obtain the first real quadratic fields with , and prove that is the smallest imaginary quadratic field with -rank equal to .

     

Multigrid methods for the computation of singular solutions and stress intensity factors I: Corner singularities

We consider the Poisson equation with homogeneous Dirichlet boundary condition on a two-dimensional polygonal domain with re-entrant angles. A multigrid method for the computation of singular solutions and stress intensity factors using piecewise linear functions is analyzed. When , the rate of convergence to the singular solution in the energy norm is shown to be , and the rate of convergence to the stress intensity factors is shown to be , where is the largest re-entrant angle of the domain and can be arbitrarily small. The cost of the algorithm is . When , the algorithm can be modified so that the convergence rate to the stress intensity factors is . In this case the maximum error of the multigrid solution over the vertices of the triangulation is shown to be .

     

Aurifeuillian factorization

The Cunningham project seeks to factor numbers of the form with small. One of the most useful techniques is Aurifeuillian Factorization whereby such a number is partially factored by replacing by a polynomial in such a way that polynomial factorization is possible. For example, by substituting into the polynomial factorization we can partially factor . In 1962 Schinzel gave a list of such identities that have proved useful in the Cunningham project; we believe that Schinzel identified all numbers that can be factored by such identities and we prove this if one accepts our definition of what ``such an identity' is. We then develop our theme to similarly factor for any given polynomial , using deep results of Faltings from algebraic geometry and Fried from the classification of finite simple groups.

     

Rationality problem of three-dimensional purely monomial group actions: the last case

A -automorphism of the rational function field is called purely monomial if sends every variable to a monic Laurent monomial in the variables . Let be a finite subgroup of purely monomial -automorphisms of . The rationality problem of the -action is the problem of whether the -fixed field is -rational, i.e., purely transcendental over , or not. In 1994, M. Hajja and M. Kang gave a positive answer for the rationality problem of the three-dimensional purely monomial group actions except one case. We show that the remaining case is also affirmative.

     

Efficient CM-constructions of elliptic curves over finite fields

We present an algorithm that, on input of an integer together with its prime factorization, constructs a finite field and an elliptic curve over for which has order . Although it is unproved that this can be done for all , a heuristic analysis shows that the algorithm has an expected run time that is polynomial in , where is the number of distinct prime factors of . In the cryptographically relevant case where is prime, an expected run time can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order and nextprime.

     

Even moments of generalized Rudin-Shapiro polynomials

We know from Littlewood (1968) that the moments of order of the classical Rudin-Shapiro polynomials satisfy a linear recurrence of degree . In a previous article, we developed a new approach, which enables us to compute exactly all the moments of even order for . We were also able to check a conjecture on the asymptotic behavior of , namely , where , for even and . Now for every integer there exists a sequence of generalized Rudin-Shapiro polynomials, denoted by . In this paper, we extend our earlier method to these polynomials. In particular, the moments have been completely determined for and , for and and for and . For higher values of and , we formulate a natural conjecture, which implies that , where is an explicit constant.

     

Computing rational points on rank 1 elliptic curves via -series and canonical heights

Let be an elliptic curve of rank 1. We describe an algorithm which uses the value of and the theory of canonical heghts to efficiently search for points in and . For rank 1 elliptic curves of moderately large conductor (say on the order of to ) and with a generator having moderately large canonical height (say between 13 and 50), our algorithm is the first practical general purpose method for determining if the set contains non-torsion points.

     

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.

     

Merging the Bramble-Pasciak-Steinbach and the Crouzeix-Thomée criterion for -projection onto finite element spaces

Suppose is a finite-dimensional linear space based on a triangulation of a domain , and let denote the -projection onto . Provided the mass matrix of each element and the surrounding mesh-sizes obey the inequalities due to Bramble, Pasciak, and Steinbach or that neighboring element-sizes obey the global growth-condition due to Crouzeix and Thomée, is -stable: For all we have with a constant that is independent of, e.g., the dimension of .

This paper provides a more flexible version of the Bramble-Pasciak- Steinbach criterion for -stability on an abstract level. In its general version, (i) the criterion is applicable to all kind of finite element spaces and yields, in particular, -stability for nonconforming schemes on arbitrary (shape-regular) meshes; (ii) it is weaker than (i.e., implied by) either the Bramble-Pasciak-Steinbach or the Crouzeix-Thomée criterion for regular triangulations into triangles; (iii) it guarantees -stability of a priori for a class of adaptively-refined triangulations into right isosceles triangles.

     

On the embedding problem for representations

Let denote the double cover of corresponding to the element in where transpositions lift to elements of order and the product of two disjoint transpositions to elements of order . Given an elliptic curve , let denote its -torsion points. Under some conditions on elements in correspond to Galois extensions of with Galois group (isomorphic to) . In this work we give an interpretation of the addition law on such fields, and prove that the obstruction for having a Galois extension with gives a homomorphism . As a corollary we can prove (if has conductor divisible by few primes and high rank) the existence of -dimensional representations of the absolute Galois group of attached to and use them in some examples to construct modular forms mapping via the Shimura map to (the modular form of weight attached to) .

     

Computation of several cyclotomic Swan subgroups

Let denote the locally free class group, that is the group of stable isomorphism classes of locally free -modules, where is the ring of algebraic integers in the number field and is a finite group. We show how to compute the Swan subgroup, , of when , a primitive -th root of unity, , where is an odd (rational) prime so that and 2 is inert in We show that, under these hypotheses, this calculation reduces to computing a quotient ring of a polynomial ring; we do the computations obtaining for several primes a nontrivial divisor of These calculations give an alternative proof that the fields for =11, 13, 19, 29, 37, 53, 59, and 61 are not Hilbert-Speiser.

     

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 .

     

On strong tractability of weighted multivariate integration

We prove that for every dimension and every number of points, there exists a point-set whose -weighted unanchored discrepancy is bounded from above by independently of provided that the sequence has for some (even arbitrarily large) . Here is a positive number that could be chosen arbitrarily close to zero and depends on but not on or . This result yields strong tractability of the corresponding integration problems including approximation of weighted integrals over unbounded domains such as . It also supplements the results that provide an upper bound of the form when .