Finding -strong pseudoprimes

Let be odd primes and . Put

Then we call the kernel, the triple the signature, and the height of , respectively. We call a -number if it is a Carmichael number with each prime factor . If is a -number and a strong pseudoprime to the bases for , we call a -spsp . Since -numbers have probability of error (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of (the smallest strong pseudoprime to all the first prime bases). If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement.

In this paper, we first describe an algorithm for finding -spsp(2)'s, to a given limit, with heights bounded. There are in total -spsp's with heights . We then give an overview of the 21978 - spsp(2)'s and tabulate of them, which are -spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No -spsp's to the first prime bases with heights were found. We conjecture that there exist no -spsp's to the first prime bases with heights and so that

which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those -spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of -spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger -spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding -strong pseudoprimes to the first several prime bases are given.

     

Polyharmonic splines on grids and their limits

Radial Basis Functions (RBF) have found a wide area of applications. We consider the case of polyharmonic RBF (called sometimes polyharmonic splines) where the data are on special grids of the form having practical importance. The main purpose of the paper is to consider the behavior of the polyharmonic interpolation splines on such grids for the limiting process 0.$"> For a large class of data functions defined on it turns out that there exists a limit function This limit function is shown to be a polyspline of order on strips. By the theory of polysplines we know that the function is smooth up to order everywhere (in particular, they are smooth on the hyperplanes , which includes existence of the normal derivatives up to order while the RBF interpolants are smooth only up to the order The last fact has important consequences for the data smoothing practice.

     

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

     

Comparison theorems of Kolmogorov type and exact values of -widths on Hardy-Sobolev classes

Let be a strip in complex plane. denotes those -periodic, real-valued functions on which are analytic in the strip and satisfy the condition , . Osipenko and Wilderotter obtained the exact values of the Kolmogorov, linear, Gel'fand, and information -widths of in , , and 2-widths of in , , .

In this paper we continue their work. Firstly, we establish a comparison theorem of Kolmogorov type on , from which we get an inequality of Landau-Kolmogorov type. Secondly, we apply these results to determine the exact values of the Gel'fand -width of in , . Finally, we calculate the exact values of Kolmogorov -width, linear -width, and information -width of in , , .

     

Elliptic curves with nonsplit mod representations

We calculate explicitly the -invariants of the elliptic curves corresponding to rational points on the modular curve by giving an expression defined over of the -function in terms of the function field generators and of the elliptic curve . As a result we exhibit infinitely many elliptic curves over with nonsplit mod representations.

     

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.

     

Two kinds of strong pseudoprimes up to

Let be an odd composite integer. Write with odd. If either mod or mod for some , then we say that is a strong pseudoprime to base , or spsp() for short. Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the are known for . Conjectured values of were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024).

The main purpose of this paper is to give exact values of for ; to give a lower bound of : ; and to give reasons and numerical evidence of K2- and -spsp's to support the following conjecture: for any , where (resp. ) is the smallest K2- (resp. -) strong pseudoprime to all the first prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: with primes and ; and that a -spsp is an spsp and a Carmichael number of the form: with each prime factor mod .)

     

On the greatest prime factor of with effective constants

Let denote a prime. In this article we provide the first published lower bounds for the greatest prime factor of exceeding in which the constants are effectively computable. As a result we prove that it is possible to calculate a value such that for every x_0$"> there is a with the greatest prime factor of exceeding . The novelty of our approach is the avoidance of any appeal to Siegel's Theorem on primes in arithmetic progression.

     

Improved methods and starting values to solve the matrix equations iteratively

The two matrix iterations are known to converge linearly to a positive definite solution of the matrix equations , respectively, for known choices of and under certain restrictions on . The convergence for previously suggested starting matrices is generally very slow. This paper explores different initial choices of in both iterations that depend on the extreme singular values of and lead to much more rapid convergence. Further, the paper offers a new algorithm for solving the minus sign equation and explores mixed algorithms that use Newton's method in part.

     

New expansions of numerical eigenvalues for by nonconforming elements

The paper explores new expansions of the eigenvalues for in with Dirichlet boundary conditions by the bilinear element (denoted ) and three nonconforming elements, the rotated bilinear element (denoted ), the extension of (denoted ) and Wilson's elements. The expansions indicate that and provide upper bounds of the eigenvalues, and that and Wilson's elements provide lower bounds of the eigenvalues. By extrapolation, the convergence rate can be obtained, where is the maximal boundary length of uniform rectangles. Numerical experiments are carried out to verify the theoretical analysis made.

     

A counterexample concerning the -projector onto linear spline spaces

For the -orthogonal projection onto spaces of linear splines over simplicial partitions in polyhedral domains in , , we show that in contrast to the one-dimensional case, where independently of the nature of the partition, in higher dimensions the -norm of cannot be bounded uniformly with respect to the partition. This fact is folklore among specialists in finite element methods and approximation theory but seemingly has never been formally proved.

     

Table of integrals of squared Jacobian elliptic functions and reductions of related hypergeometric -functions

Any product of real powers of Jacobian elliptic functions can be written in the form . If all three 's are even integers, the indefinite integral of this product with respect to is a constant times a multivariate hypergeometric function with half-odd-integral 's and , showing it to be an incomplete elliptic integral of the second kind unless all three 's are 0. Permutations of c, d, and n in the integrand produce the same permutations of the variables }, allowing as many as six integrals to take a unified form. Thirty -functions of the type specified, incorporating 136 integrals, are reduced to a new choice of standard elliptic integrals obtained by permuting , , and in , which is symmetric in its first two variables and has an efficient algorithm for numerical computation.

     

High rank elliptic curves with torsion group

We develop an algorithm for bounding the rank of elliptic curves in the family , all of them with torsion group and modular invariant . We use it to look for curves of high rank in this family and present four such curves of rank  and of rank .

     

More on the total number of prime factors of an odd perfect number

Let denote the sum of the positive divisors of . We say that is perfect if . Currently there are no known odd perfect numbers. It is known that if an odd perfect number exists, then it must be of the form , where are distinct primes and . Define the total number of prime factors of as . Sayers showed that . This was later extended by Iannucci and Sorli to show that . This paper extends these results to show that .

     

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.

     

A solution to certain polynomial equations with applications to nonlinear fitting

We present a combinatorial method for solving a certain system of polynomial equations of Vandermonde type in variables by reducing it to the problem of solving two special linear systems of size and rooting a single univariate polynomial of degree . Over , all solutions can be found with fixed precision using, up to polylogarithmic factors, bitwise operations in the worst case. Furthermore, if the data is well conditioned, then this can be reduced to bit operations, up to polylogarithmic factors. As an application, we show how this can be used to fit data to a complex exponential sum with terms in the same, nearly optimal, time.

     

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 .

     

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.

     

A primitive trinomial of degree 6972593

The only primitive trinomials of degree over are and its reciprocal.

     

On the absolute Mahler measure of polynomials having all zeros in a sector. II

Let be an algebraic integer of degree , not or a root of unity, all of whose conjugates are confined to a sector . In the paper On the absolute Mahler measure of polynomials having all zeros in a sector, G. Rhin and C. Smyth compute the greatest lower bound of the absolute Mahler measure ( of , for belonging to nine subintervals of . In this paper, we improve the result to thirteen subintervals of and extend some existing subintervals.