Accelerated polynomial approximation of finite order entire functions by growth reduction

Let be an entire function of positive order and finite type. The subject of this note is the convergence acceleration of polynomial approximants of by incorporating information about the growth of for . We consider ``near polynomial approximation' on a compact plane set , which should be thought of as a circle or a real interval. Our aim is to find sequences of functions which are the product of a polynomial of degree and an ``easy computable' second factor and such that converges essentially faster to on than the sequence of best approximating polynomials of degree . The resulting method, which we call Reduced Growth method (-method) is introduced in Section 2. In Section 5, numerical examples of the -method applied to the complex error function and to Bessel functions are given.

     

Bounds for Multiplicative Cosets over Fields of Prime Order

Let be a positive integer and suppose that is an odd prime with . Suppose that and consider the polynomial . If this polynomial has any roots in , where the coset representatives for are taken to be all integers with , then these roots will form a coset of the multiplicative subgroup of consisting of the th roots of unity mod . Let be a coset of in , and define . In the paper ``Numbers Having Small th Roots mod ' (Mathematics of Computation, Vol. 61, No. 203 (1993),pp. 393-413), Robinson gives upper bounds for of the form , where is the Euler phi-function. This paper gives lower bounds that are of the same form, and seeks to sharpen the constants in the upper bounds of Robinson. The upper bounds of Robinson are proven to be optimal when is a power of or when

     

Computing irreducible representations of supersolvable groups over small finite fields

We present an algorithm to compute a full set of irreducible representations of a supersolvable group over a finite field , , which is not assumed to be a splitting field of . The main subroutines of our algorithm are a modification of the algorithm of Baum and Clausen (Math. Comp. 63 (1994), 351-359) to obtain information on algebraically conjugate representations, and an effective version of Speiser's generalization of Hilbert's Theorem 90 stating that vanishes for all .

     

On some inequalities for the incomplete gamma function

Let be a positive real number. We determine all real numbers and such that the inequalities

are valid for all . And, we determine all real numbers and such that

hold for all .

     

Numbers whose positive divisors have small integral harmonic mean

A natural number is said to be harmonic when the harmonic mean of its positive divisors is an integer. These were first introduced almost fifty years ago. In this paper, all harmonic numbers less than are listed, along with some other useful tables, and all harmonic numbers with are determined.

     

Optimal information for approximating periodic analytic functions

Let be a strip in the complex plane. For fixed integer let denote the class of -periodic functions , which are analytic in and satisfy in . Denote by the subset of functions from that are real-valued on the real axis. Given a function , we try to recover at a fixed point by an algorithm on the basis of the information

where , are the Fourier coefficients of . We find the intrinsic error of recovery

Furthermore the -dimensional optimal information error, optimal sampling error and -widths of in , the space of continuous functions on , are determined. The optimal sampling error turns out to be strictly greater than the optimal information error. Finally the same problems are investigated for the class , consisting of all -periodic functions, which are analytic in with -integrable boundary values. In the case sampling fails to yield optimal information as well in odd as in even dimensions.

     

The exponent of discrepancy is at most

We study discrepancy with arbitrary weights in the norm over the -dimensional unit cube. The exponent of discrepancy is defined as the smallest for which there exists a positive number such that for all and all there exist points with discrepancy at most . It is well known that . We improve the upper bound by showing that

This is done by using relations between discrepancy and integration in the average case setting with the Wiener sheet measure. Our proof is not constructive. The known constructive bound on the exponent is .

     

Computational experiences on the distances of polynomials to irreducible polynomials

In this paper we deal with a problem of Turán concerning the `distance' of polynomials to irreducible polynomials. Using computational methods we prove that for any monic polynomial of degree there exists a monic polynomial with deg() = deg() such that is irreducible over and the `distance' of and is .

     

The practical computation of areas associated with binary quartic forms

We derive formulas for practically computing the area of the region defined by a binary quartic form . These formulas, which involve a particular hypergeometric function, are useful when estimating the number of lattice points in certain regions of the type and will likely find application in many contexts. We also show that for forms of arbitrary degree, the maximal size of the area of the region , normalized with respect to the discriminant of and taken with respect to the number of conjugate pairs of , increases as the number of conjugate pairs decreases; and we give explicit numerical values for these normalized maxima when is a quartic form.

     

Computing Canonical Heights With Little (or No) Factorization

Let be an elliptic curve with discriminant , and let . The standard method for computing the canonical height is as a sum of local heights . There are well-known series for computing the archimedean height , and the non-archimedean heights are easily computed as soon as all prime factors of have been determined. However, for curves with large coefficients it may be difficult or impossible to factor . In this note we give a method for computing the non-archimedean contribution to which is quite practical and requires little or no factorization. We also give some numerical examples illustrating the algorithm.

     

On a Problem of Byrnes concerning Polynomials with Restricted Coefficients

We consider a question of Byrnes concerning the minimal degree of a polynomial with all coefficients in which has a zero of a given order at . For , we prove his conjecture that the monic polynomial of this type of minimal degree is given by , but we disprove this for . We prove that a polynomial of this type must have , which is in sharp contrast with the situation when one allows coefficients in . The proofs use simple number theoretic ideas and depend ultimately on the fact that .

     

The Rabin-Monier theorem for Lucas pseudoprimes

We give bounds on the number of pairs with such that a composite number is a strong Lucas pseudoprime with respect to the parameters .

     

Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems

In this paper we are concerned with the solution of Hermitian Toeplitz systems with nonnegative generating functions . The preconditioned conjugate gradient (PCG) method with the well-known circulant preconditioners fails in the case where has zeros. In this paper we consider as preconditioners band-Toeplitz matrices generated by trigonometric polynomials of fixed degree . We use different strategies of approximation of to devise a polynomial which has some analytical properties of , is easily computable and is such that the corresponding preconditioned system has a condition number bounded by a constant independent of . For each strategy we analyze the cost per iteration and the number of iterations required for the convergence within a preassigned accuracy. We obtain different estimates of for which the total cost of the proposed PCG methods is optimal and the related rates of convergence are superlinear. Finally, for the most economical strategy, we perform various numerical experiments which fully confirm the effectiveness of approximation theory tools in the solution of this kind of linear algebra problems.

     

A search for Wieferich and Wilson primes

An odd prime is called a Wieferich prime if

alternatively, a Wilson prime if

To date, the only known Wieferich primes are and , while the only known Wilson primes are , and . We report that there exist no new Wieferich primes , and no new Wilson primes . It is elementary that both defining congruences above hold merely (mod ), and it is sometimes estimated on heuristic grounds that the ``probability" that is Wieferich (independently: that is Wilson) is about . We provide some statistical data relevant to occurrences of small values of the pertinent Fermat and Wilson quotients (mod ).

     

A continuity property of multivariate Lagrange interpolation

Let be a sequence of interpolation schemes in of degree (i.e. for each one has unique interpolation by a polynomial of total degree and total order . Suppose that the points of tend to as and the Lagrange-Hermite interpolants, , satisfy for all monomials with . Theorem: for all functions of class in a neighborhood of . (Here denotes the Taylor series of at 0 to order .) Specific examples are given to show the optimality of this result.

     

On the -divisibility of Fermat quotients

The authors carried out a numerical search for Fermat quotients vanishing mod , for , up to . This article reports on the results and surveys the associated theoretical properties of . The approach of fixing the prime rather than the base leads to some aspects of the theory apparently not published before.

     

On generalized bisection of -simplices

A generalized procedure of bisection of -simplices is introduced, where the bisection point can be an (almost) arbitrary point at one of the longest edges. It is shown that nested sequences of simplices generated by successive generalized bisection converge to a singleton, and an exact bound of the convergence speed in terms of diameter reduction is given. For regular simplices, which mark the worst case, the edge lengths of each worst and best simplex generated by successive bisection are given up to depth . For and , the sequence of worst case diameters is provided until it is halved.

     

On the rapid computation of various polylogarithmic constants

We give algorithms for the computation of the -th digit of certain transcendental numbers in various bases. These algorithms can be easily implemented (multiple precision arithmetic is not needed), require virtually no memory, and feature run times that scale nearly linearly with the order of the digit desired. They make it feasible to compute, for example, the billionth binary digit of or on a modest work station in a few hours run time. We demonstrate this technique by computing the ten billionth hexadecimal digit of , the billionth hexadecimal digits of and , and the ten billionth decimal digit of . These calculations rest on the observation that very special types of identities exist for certain numbers like , , and . These are essentially polylogarithmic ladders in an integer base. A number of these identities that we derive in this work appear to be new, for example the critical identity for :

     

A stochastic particle method for the McKean-Vlasov and the Burgers equation

In this paper we introduce and analyze a stochastic particle method for the McKean-Vlasov and the Burgers equation; the construction and error analysis are based upon the theory of the propagation of chaos for interacting particle systems. Our objective is three-fold. First, we consider a McKean-Vlasov equation in with sufficiently smooth kernels, and the PDEs giving the distribution function and the density of the measure , the solution to the McKean-Vlasov equation. The simulation of the stochastic system with particles provides a discrete measure which approximates for each time (where is a discretization step of the time interval ). An integration (resp. smoothing) of this discrete measure provides approximations of the distribution function (resp. density) of . We show that the convergence rate is for the approximation in of the cumulative distribution function at time , and of order for the approximation in of the density at time ( is the underlying probability space, is a smoothing parameter). Our second objective is to show that our particle method can be modified to solve the Burgers equation with a nonmonotonic initial condition, without modifying the convergence rate . This part extends earlier work of ours, where we have limited ourselves to monotonic initial conditions. Finally, we present numerical experiments which confirm our theoretical estimates and illustrate the numerical efficiency of the method when the viscosity coefficient is very small.

     

Some extensions of the Lanczos-Ortiz theory of canonical polynomials in the Tau Method

Lanczos and Ortiz placed the canonical polynomials (c.p.'s) in a central position in the Tau Method. In addition, Ortiz devised a recursive process for determining c.p.'s consisting of a generating formula and a complementary algorithm coupled to the formula. In this paper a) We extend the theory so as to include in the formalism also the ordinary linear differential operators with polynomial coefficients with negative height

where denotes the degree of . b) We establish a basic classification of the c.p.'s and their orders , as primary or derived, depending, respectively, on whether or such does not exist; and we state a classification of the indices , as generic , singular , and indefinite . Then a formula which gives the set of primary orders is proved. c) In the rather frequent case in which all c.p.'s are primary, we establish, for differential operators with any height , a recurrency formula which generates bases of the polynomial space and their multiple c.p.'s arising from distinct , , so that no complementary algorithmic construction is needed; the (primary) c.p.'s so produced are classified as generic or singular, depending on the index . d) We establish the general properties of the multiplicity relations of the primary c.p.'s and of their associated indices. It becomes clear that Ortiz's formula generates, for , the generic c.p.'s in terms of the singular and derived c.p.'s, while singular and derived c.p.'s and the multiples of distinct indices are constructed by the algorithm.