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 .

     

Fast convergence of quasi-Monte Carlo for a class of isotropic integrals

We consider the approximation of -dimensional weighted integrals of certain isotropic functions. We are mainly interested in cases where is large. We show that the convergence rate of quasi-Monte Carlo for the approximation of these integrals is . Since this is a worst case result, compared to the expected convergence rate of Monte Carlo, it shows the superiority of quasi-Monte Carlo for this type of integral. This is much faster than the worst case convergence, , of quasi-Monte Carlo.

     

Heuristics for class numbers and lambda invariants

Let be an imaginary quadratic field and let be the associated real quadratic field. Starting from the Cohen-Lenstra heuristics and Scholz's theorem, we make predictions for the behaviors of the 3-parts of the class groups of these two fields as varies. We deduce heuristic predictions for the behavior of the Iwasawa -invariant for the cyclotomic -extension of and test them computationally.

     

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.

     

Practical solution of the Diophantine equation

Let be an odd prime and , positive integers. In this note we prove that the problem of the determination of the integer solutions to the equation can be easily reduced to the resolution of the unit equation over . The solutions of the latter equation are given by Wildanger's algorithm.

     

Analysis of recovery type a posteriori error estimators for mildly structured grids

Some recovery type error estimators for linear finite elements are analyzed under 0)$"> regular grids. Superconvergence of order is established for recovered gradients by three different methods. As a consequence, a posteriori error estimators based on those recovery methods are asymptotically exact.

     

Quaternionic Manin symbols, Brandt matrices, and Hilbert modular forms

In this paper, we propose a generalization of the algorithm we developed previously. Along the way, we also develop a theory of quaternionic -symbols whose definition bears some resemblance to the classical -symbols, except for their combinatorial nature. The theory gives a more efficient way to compute Hilbert modular forms over totally real number fields, especially quadratic fields, and we have illustrated it with several examples. Namely, we have computed all the newforms of prime levels of norm less than 100 over the quadratic fields and , and whose Fourier coefficients are rational or are defined over a quadratic field.

     

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.

     

The -approximation order of surface spline interpolation

We show that if the open, bounded domain has a sufficiently smooth boundary and if the data function is sufficiently smooth, then the -norm of the error between and its surface spline interpolant is ( ), where and is an integer parameter specifying the surface spline. In case , this lower bound on the approximation order agrees with a previously obtained upper bound, and so we conclude that the -approximation order of surface spline interpolation is .

     

A hidden number problem in small subgroups

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element , where is prime, from rather short strings of the most significant bits of the residue of modulo for several randomly chosen . González Vasco and the first author have recently extended this result to subgroups of of order at least for all and to subgroups of order at least for almost all . Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the multipliers and thus extend this result to subgroups of order at least for all primes . As in the above works, we give applications of our result to the bit security of the Diffie-Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

     

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

     

Sums of heights of algebraic numbers

For , we consider the set . The polynomials are in , with only mild restrictions, and is the Weil height of . We show that this set is dense in for some effectively computable limit point .

     

Continued fractions in local fields, II

The present paper is a continuation of an earlier work by the author. We propose some new definitions of -adic continued fractions. At the end of the paper we give numerical examples illustrating these definitions. It turns out that for every if then has a periodic continued fraction expansion. The same is not true in for some larger values of

     

Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

We examine the problem of factoring the th cyclotomic polynomial, over , and distinct primes. Given the traces of the roots of we construct the coefficients of in time . We demonstrate a deterministic algorithm for factoring in time when has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of in time .

     

Primitive central idempotents of finite group rings of symmetric groups

Let be a prime. We denote by the symmetric group of degree , by the alternating group of degree and by the field with elements. An important concept of modular representation theory of a finite group is the notion of a block. The blocks are in one-to-one correspondence with block idempotents, which are the primitive central idempotents of the group ring , where is a prime power. Here, we describe a new method to compute the primitive central idempotents of for arbitrary prime powers and arbitrary finite groups . For the group rings of the symmetric group, we show how to derive the primitive central idempotents of from the idempotents of . Improving the theorem of Osima for symmetric groups we exhibit a new subalgebra of which contains the primitive central idempotents. The described results are most efficient for . In an appendix we display all primitive central idempotents of and for which we computed by this method.

     

Computing the tame kernel of quadratic imaginary fields

J. Tate has determined the group (called the tame kernel) for six quadratic imaginary number fields where Modifying the method of Tate, H. Qin has done the same for and and M. Skaba for and

In the present paper we discuss the methods of Qin and Skaba, and we apply our results to the field

In the Appendix at the end of the paper K. Belabas and H. Gangl present the results of their computation of for some other values of The results agree with the conjectural structure of given in the paper by Browkin and Gangl.

     

Computing weight modular forms of level

For a prime we describe an algorithm for computing the Brandt matrices giving the action of the Hecke operators on the space of modular forms of weight and level . For we define a special Hecke stable subspace of which contains the space of modular forms with CM by the ring of integers of and we describe the calculation of the corresponding Brandt matrices.

     

``Chinese & Match', an alternative to Atkin's ``Match and Sort' method used in the SEA algorithm

A classical way to compute the number of points of elliptic curves defined over finite fields from partial data obtained in SEA (Schoof Elkies Atkin) algorithm is a so-called ``Match and Sort' method due to Atkin. This method is a ``baby step/giant step' way to find the number of points among candidates with elliptic curve additions. Observing that the partial information modulo Atkin's primes is redundant, we propose to take advantage of this redundancy to eliminate the usual elliptic curve algebra in this phase of the SEA computation. This yields an algorithm of similar complexity, but the space needed is smaller than what Atkin's method requires. In practice, our technique amounts to an acceleration of Atkin's method, allowing us to count the number of points of an elliptic curve defined over . As far as we know, this is the largest point-counting computation to date. Furthermore, the algorithm is easily parallelized.

     

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 .

     

Univariate splines: Equivalence of moduli of smoothness and applications

Several results on equivalence of moduli of smoothness of univariate splines are obtained. For example, it is shown that, for any , , and , the inequality , , is satisfied, where is a piecewise polynomial of degree on a quasi-uniform (i.e., the ratio of lengths of the largest and the smallest intervals is bounded by a constant) partition of an interval. Similar results for Chebyshev partitions and weighted Ditzian-Totik moduli of smoothness are also obtained. These results yield simple new constructions and allow considerable simplification of various known proofs in the area of constrained approximation by polynomials and splines.