Notes on some new kinds of pseudoprimes

J. Browkin defined in his recent paper (Math. Comp. 73 (2004), pp. 1031-1037) some new kinds of pseudoprimes, called Sylow -pseudoprimes and elementary Abelian -pseudoprimes. He gave examples of strong pseudoprimes to many bases which are not Sylow -pseudoprime to two bases only, where or .

In this paper, in contrast to Browkin's examples, we give facts and examples which are unfavorable for Browkin's observation to detect compositeness of odd composite numbers. In Section 2, we tabulate and compare counts of numbers in several sets of pseudoprimes and find that most strong pseudoprimes are also Sylow -pseudoprimes to the same bases. In Section 3, we give examples of Sylow -pseudoprimes to the first several prime bases for the first several primes . We especially give an example of a strong pseudoprime to the first six prime bases, which is a Sylow -pseudoprime to the same bases for all . In Section 4, we define to be a -fold Carmichael Sylow pseudoprime, if it is a Sylow -pseudoprime to all bases prime to for all the first smallest odd prime factors of . We find and tabulate all three -fold Carmichael Sylow pseudoprimes . In Section 5, we define a positive odd composite to be a Sylow uniform pseudoprime to bases , or a Syl-upsp for short, if it is a Syl-psp for all the first small prime factors of , where is the number of distinct prime factors of . We find and tabulate all the 17 Syl-upsp's and some Syl-upsp 's . Comparisons of effectiveness of Browkin's observation with Miller tests to detect compositeness of odd composite numbers are given in Section 6.

     

Minimality and other properties of the width- nonadjacent form

Let be an integer and let be the set of integers that includes zero and the odd integers with absolute value less than . Every integer can be represented as a finite sum of the form , with , such that of any consecutive 's at most one is nonzero. Such representations are called width- nonadjacent forms (-NAFs). When these representations use the digits and coincide with the well-known nonadjacent forms. Width- nonadjacent forms are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. We provide some new results on the -NAF. We show that -NAFs have a minimal number of nonzero digits and we also give a new characterization of the -NAF in terms of a (right-to-left) lexicographical ordering. We also generalize a result on -NAFs and show that any base 2 representation of an integer, with digits in , that has a minimal number of nonzero digits is at most one digit longer than its binary representation.

     

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

     

Extension of a class of periodizing variable transformations for numerical Integration

Class variable transformations with integer , for numerical computation of finite-range integrals, were introduced and studied by the author in the paper [A. Sidi, A new variable transformation for numerical integration, Numerical Integration IV, 1993 (H. Brass and G. Hämmerlin, eds.), pp. 359-373.] A representative of this class is the -transformation that has been used with lattice rules for multidimensional integration. These transformations ``periodize' the integrand functions in a way that enables the trapezoidal rule to achieve very high accuracy, especially with even . In the present work, we extend these transformations to arbitrary values of , and give a detailed analysis of the resulting transformed trapezoidal rule approximations. We show that, with suitable , they can be very useful in different situations. We prove, for example, that if the integrand function is smooth on the interval of integration and vanishes at the endpoints, then results of especially high accuracy are obtained by taking to be an odd integer. Such a situation can be realized in general by subtracting from the integrand the linear interpolant at the endpoints of the interval of integration. We also illustrate some of the results with numerical examples via the extended -transformation.

     

Approximating the number of integers without large prime factors

denotes the number of positive integers and free of prime factors . Hildebrand and Tenenbaum gave a smooth approximation formula for in the range , where is a fixed positive number . In this paper, by modifying their approximation formula, we provide a fast algorithm to approximate . The computational complexity of this algorithm is . We give numerical results which show that this algorithm provides accurate estimates for and is faster than conventional methods such as algorithms exploiting Dickman's function.

     

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.

     

Finite element approximation of a phase field model for surface diffusion of voids in a stressed solid

We consider a fully practical finite element approximation of the degenerate Cahn-Hilliard equation with elasticity: Find the conserved order parameter, , and the displacement field, , such that

subject to an initial condition on and boundary conditions on both equations. Here is the interfacial parameter, is a non-smooth double well potential, is the symmetric strain tensor, is the possibly anisotropic elasticity tensor, with and is the degenerate diffusional mobility. In addition to showing stability bounds for our approximation, we prove convergence, and hence existence of a solution to this nonlinear degenerate parabolic system in two space dimensions. Finally, some numerical experiments are presented.

     

Accurate and efficient evaluation of Schur and Jack functions

We present new algorithms for computing the values of the Schur and Jack functions in floating point arithmetic. These algorithms deliver guaranteed high relative accuracy for positive data ( 0$">) and run in time that is only linear in .

     

Continuous-time Kreiss resolvent condition on infinite-dimensional spaces

Given the infinitesimal generator of a -semigroup on the Banach space which satisfies the Kreiss resolvent condition, i.e., there exists an such that for all complex with positive real part, we show that for general Banach spaces this condition does not give any information on the growth of the associated -semigroup. For Hilbert spaces the situation is less dramatic. In particular, we show that the semigroup can grow at most like . Furthermore, we show that for every there exists an infinitesimal generator satisfying the Kreiss resolvent condition, but whose semigroup grows at least like . As a consequence, we find that for with the standard Euclidian norm the estimate cannot be replaced by a lower power of or .

     

Runge-Kutta time discretizations of nonlinear dissipative evolution equations

Global error bounds are derived for Runge-Kutta time discretizations of fully nonlinear evolution equations governed by -dissipative vector fields on Hilbert spaces. In contrast to earlier studies, the analysis presented here is not based on linearization procedures, but on the fully nonlinear framework of logarithmic Lipschitz constants in order to extend the classical -convergence theory to infinite-dimensional spaces. An algebraically stable Runge-Kutta method with stage order is derived to have a global error which is at least of order or , depending on the monotonicity properties of the method.

     

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.

     

The monic integer transfinite diameter

We study the problem of finding nonconstant monic integer polynomials, normalized by their degree, with small supremum on an interval . The monic integer transfinite diameter is defined as the infimum of all such supremums. We show that if has length , then .

We make three general conjectures relating to the value of for intervals of length less than . We also conjecture a value for where . We give some partial results, as well as computational evidence, to support these conjectures.

We define functions and , which measure properties of the lengths of intervals with on either side of . Upper and lower bounds are given for these functions.

We also consider the problem of determining when is a Farey interval. We prove that a conjecture of Borwein, Pinner and Pritsker concerning this value is true for an infinite family of Farey intervals.

     

Iterated function systems, Ruelle operators, and invariant projective measures

We introduce a Fourier-based harmonic analysis for a class of discrete dynamical systems which arise from Iterated Function Systems. Our starting point is the following pair of special features of these systems. (1) We assume that a measurable space comes with a finite-to-one endomorphism which is onto but not one-to-one. (2) In the case of affine Iterated Function Systems (IFSs) in , this harmonic analysis arises naturally as a spectral duality defined from a given pair of finite subsets in of the same cardinality which generate complex Hadamard matrices.

Our harmonic analysis for these iterated function systems (IFS) is based on a Markov process on certain paths. The probabilities are determined by a weight function on . From we define a transition operator acting on functions on , and a corresponding class of continuous -harmonic functions. The properties of the functions in are analyzed, and they determine the spectral theory of . For affine IFSs we establish orthogonal bases in . These bases are generated by paths with infinite repetition of finite words. We use this in the last section to analyze tiles in .

     

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.

     

Constructing representations of higher degrees of finite simple groups and covers

Let be a finite group and an irreducible character of . A simple method for constructing a representation affording can be used whenever has a subgroup such that has a linear constituent with multiplicity 1. In this paper we show that (with a few exceptions) if is a simple group or a covering group of a simple group and is an irreducible character of of degree between 32 and 100, then such a subgroup exists.

     

Littlewood polynomials with high order zeros

Let be the minimal length of a polynomial with coefficients divisible by . Byrnes noted that for each , and asked whether in fact . Boyd showed that for all , but . He further showed that , and that is one of the 5 numbers , or . Here we prove that . Similarly, let be the maximal power of dividing some polynomial of degree with coefficients. Boyd was able to find for . In this paper we determine for .

     

The trace of totally positive algebraic integers

For all totally positive algebraic numbers except a finite number of explicit exceptions, the following inequality holds:

\max(1.780022,1.66+\alpha_1), \end{displaymath}">

where is the degree of and its conjugates. This improves previous results of Smyth, Flammang and Rhin.

     

Explicit primality criteria for

Deterministic polynomial time primality criteria for have been known since the work of Lucas in 1876-1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form , where is any fixed prime. When (p-1)/2$"> we show that it is always possible to produce a Lucas-like deterministic test for the primality of which requires that only modular multiplications be performed modulo , as long as we can find a prime of the form such that is not divisible by . We also show that for all with such a can be found very readily, and that the most difficult case in which to find a appears, somewhat surprisingly, to be that for . Some explanation is provided as to why this case is so difficult.

     

CM-fields with relative class number one

We will show that the normal CM-fields with relative class number one are of degrees . Moreover, if we assume the Generalized Riemann Hypothesis, then the normal CM-fields with relative class number one are of degrees , and the CM-fields with class number one are of degrees . By many authors all normal CM-fields of degrees with class number one are known except for the possible fields of degree or . Consequently the class number one problem for normal CM-fields is solved under the Generalized Riemann Hypothesis except for these two cases.