The irreducibility of some level 1 Hecke polynomials

Let be the characteristic polynomial of the Hecke operator acting on the space of level 1 cusp forms . We show that is irreducible and has full Galois group over  for and ,  prime.

     

Upper bounds for the prime divisors of Wendt's determinant

Let be an even integer, . The resultant of the polynomials and is known as Wendt's determinant of order . We prove that among the prime divisors of only those which divide or can be larger than , where and is the th Lucas number, except when and . Using this estimate we derive criteria for the nonsolvability of Fermat's congruence.

     

On the primality of

For each prime , let be the product of the primes less than or equal to . We have greatly extended the range for which the primality of and are known and have found two new primes of the first form ( ) and one of the second (). We supply heuristic estimates on the expected number of such primes and compare these estimates to the number actually found.

     

New convergence results on the generalized Richardson extrapolation process GREP for logarithmic sequences

Let as , where and are known for for some 0$">, but and the are not known. The generalized Richardson extrapolation process GREP is used in obtaining good approximations to , the limit or antilimit of as . The approximations to obtained via GREPare defined by the linear systems , , where is a decreasing positive sequence with limit zero. The study of GREP for slowly varying functions was begun in two recent papers by the author. For such we have as with possibly complex and . In the present work we continue to study the convergence and stability of GREPas it is applied to such with different sets of collocation points that have been used in practical situations. In particular, we consider the cases in which (i) are arbitrary, (ii) , (iii) as for some 0$">, (iv) for all , (v) , and (vi) for all .

     

Finite SAGBI bases for polynomial invariants of conjugates of alternating groups

It is well-known, that the ring of polynomial invariants of the alternating group has no finite SAGBI basis with respect to the lexicographical order for any number of variables . This note proves the existence of a nonsingular matrix such that the ring of polynomial invariants , where denotes the conjugate of with respect to , has a finite SAGBI basis for any .     

Thue's theorem and the diophantine equation

A constructive version of a theorem of Thue is used to provide representations of certain integers as , where .

     

Solving norm equations in relative number fields using -units

In this paper, we are interested in solving the so-called norm equation , where is a given arbitrary extension of number fields and a given algebraic number of . By considering -units and relative class groups, we show that if there exists at least one solution (in , but not necessarily in ), then there exists a solution for which we can describe precisely its prime ideal factorization. In fact, we prove that under some explicit conditions, the -units that are norms are norms of -units. This allows us to limit the search for rational solutions to a finite number of tests, and we give the corresponding algorithm. When is an algebraic integer, we also study the existence of an integral solution, and we can adapt the algorithm to this case.

     

Security of the most significant bits of the Shamir message passing scheme

Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a ``hidden' element of a finite field of elements from rather short strings of the most significant bits of the remainder modulo of for several values of selected uniformly at random from . Unfortunately the applications to the computational security of most significant bits of private keys of some finite field exponentiation based cryptosystems given by Boneh and Venkatesan are not quite correct. For the Diffie-Hellman cryptosystem the result of Boneh and Venkatesan has been corrected and generalized in our recent paper. Here a similar analysis is given for the Shamir message passing scheme. The results depend on some bounds of exponential sums.

     

A computational approach to Hilbert modular group fixed points

Some useful information is known about the fundamental domain for certain Hilbert modular groups. The six nonequivalent points with nontrivial isotropy in the fundamental domains under the action of the modular group for , , and have been determined previously by Gundlach. In finding these points, use was made of the exact size of the isotropy groups. Here we show that the fixed points and the isotropy groups can be found without such knowledge by use of a computer scan. We consider the cases and . A computer algebra system and a C compiler were essential in perfoming the computations.

     

On the least prime primitive root modulo a prime

We derive a conditional formula for the natural density of prime numbers having its least prime primitive root equal to , and compare theoretical results with the numerical evidence.

     

On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

We develop and justify an algorithm for the construction of quasi-Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found ``component-by-component': the ()-th component of the generator vector and the shift are obtained by successive -dimensional searches, with the previous components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for -point rules with prime and all dimensions 1 to requires a total cost of operations. This may be reduced to operations at the expense of storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.

     

Directional Newton methods in variables

Directional Newton methods for functions of variables are shown to converge, under standard assumptions, to a solution of . The rate of convergence is quadratic, for near-gradient directions, and directions along components of the gradient of with maximal modulus. These methods are applied to solving systems of equations without inversion of the Jacobian matrix.

     

Some computations on the spectra of Pisot and Salem numbers

Properties of Pisot numbers have long been of interest. One line of questioning, initiated by Erdos, Joó and Komornik in 1990, is the determination of for Pisot numbers , where

Although the quantity is known for some Pisot numbers , there has been no general method for computing . This paper gives such an algorithm. With this algorithm, some properties of and its generalizations are investigated.

A related question concerns the analogy of , denoted , where the coefficients are restricted to ; in particular, for which non-Pisot numbers is nonzero? This paper finds an infinite class of Salem numbers where .

     

Special prime numbers and discrete logs in finite prime fields

A set of primes involving numbers such as , where and , is defined. An algorithm for computing discrete logs in the finite field of order with is suggested. Its heuristic expected running time is for , where as , , and . At present, the most efficient algorithm for computing discrete logs in the finite field of order for general is Schirokauer's adaptation of the Number Field Sieve. Its heuristic expected running time is for . Using rather than general does not enhance the performance of Schirokauer's algorithm. The definition of the set and the algorithm suggested in this paper are based on a more general congruence than that of the Number Field Sieve. The congruence is related to the resultant of integer polynomials. We also give a number of useful identities for resultants that allow us to specify this congruence for some .

     

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.

     

Numerical calculation of the density of prime numbers with a given least primitive root

In this paper the densities of prime numbers having the least primitive root , where is equal to one of the initial positive integers less than 32, have been numerically calculated. The computations were carried out under the assumption of the Generalised Riemann Hypothesis. The results of these computations were compared with the results of numerical frequency estimations.

     

Two contradictory conjectures concerning Carmichael numbers

Erdos conjectured that there are Carmichael numbers up to , whereas Shanks was skeptical as to whether one might even find an up to which there are more than Carmichael numbers. Alford, Granville and Pomerance showed that there are more than Carmichael numbers up to , and gave arguments which even convinced Shanks (in person-to-person discussions) that Erdos must be correct. Nonetheless, Shanks's skepticism stemmed from an appropriate analysis of the data available to him (and his reasoning is still borne out by Pinch's extended new data), and so we herein derive conjectures that are consistent with Shanks's observations, while fitting in with the viewpoint of Erdos and the results of Alford, Granville and Pomerance.

     

Approximation by quadrilateral finite elements

We consider the approximation properties of finite element spaces on quadrilateral meshes. The finite element spaces are constructed starting with a given finite dimensional space of functions on a square reference element, which is then transformed to a space of functions on each convex quadrilateral element via a bilinear isomorphism of the square onto the element. It is known that for affine isomorphisms, a necessary and sufficient condition for approximation of order in and order in is that the given space of functions on the reference element contain all polynomial functions of total degree at most . In the case of bilinear isomorphisms, it is known that the same estimates hold if the function space contains all polynomial functions of separate degree . We show, by means of a counterexample, that this latter condition is also necessary. As applications, we demonstrate degradation of the convergence order on quadrilateral meshes as compared to rectangular meshes for serendipity finite elements and for various mixed and nonconforming finite elements.

     

Estimates of

We extend a result of Ramaré and Rumely, 1996, about the Chebyshev function in arithmetic progressions. We find a map such that and 0)}$">, whereas is a constant. Now we are able to show that, for ,

and, for ,

\frac{x}{2\ln x}.\end{displaymath}">

     

Jacobi sums and new families of irreducible polynomials of Gaussian periods

Let 2$">, an -th primitive root of 1, mod a prime number, a primitive root modulo and . We study the Jacobi sums , , where is the least nonnegative integer such that mod . We exhibit a set of properties that characterize these sums, some congruences they satisfy, and a MAPLE program to calculate them. Then we use those results to show how one can construct families , , of irreducible polynomials of Gaussian periods, , of degree , where is a suitable set of primes mod . We exhibit examples of such families for several small values of , and give a MAPLE program to construct more of them.