Publications of (and about) Paul Erdös
Autor: Erdös, Paul; Granville, A.; Pomerance, C.; Spiro, C.
Title: On the normal behavior of the iterates of some arithmetic functions. (In English)
Source: Analytic number theory, Proc. Conf. in Honor of Paul T. Bateman, Urbana/IL (USA) 1989, Prog. Math. 85, 165-204 (1990).
Review: [For the entire collection see Zbl 711.00008.]
Let \phi1(n) = \phi(n) (Euler's function), \phik(n) = \phi(\phik-1(n)) for k \geq 2; denote by k(n) the least k such that \phik(n) = 1, and let F(n) = k(n) or k(n)-1 according as n is even or odd. This paper contains a wealth of interesting results concerning these functions and related quantities, and also the iterated function sk(n), where s1(n) = \sigma (n)-n, sk(n) = s(sk-1(n)) for k \geq 2. We select just a few typical ones here.
The authors begin by obtaining conditional results on the average and normal order of the (completely additive) function F(n) under the assumption of suitable strong versions of the Elliott-Halberstam conjecture. They prove also that the normal order of \phik(n)/\phik+1(n) for n \leq x is ke\gamma log log log x for any k \leq (log log x)\epsilon(x) for positive \epsilon(x) tending to zero arbitrarily slowly as x > oo. They go on to show that there is an absolute constant c > 0 such that the set of positive integers n, for which there is some k with \phik(n) divisible by every prime up to (log n)c, has asymptotic density 1. The proofs are elementary in nature but very intricate.
The authors correct some errors pointed out to them by A. Smati by making some minor changes to the proof of a lemma in [Rocky Mt. Math. J. 15, 343-352 (1985; Zbl 617.10037)] by P. Erdös and C. Pomerance.
Reviewer: E.J.Scourfield (Egham)
Classif.: * 11N37 Asymptotic results on arithmetic functions
11A25 Arithmetic functions, etc.
Keywords: iteration of Euler's function; normal order; Elliott-Halberstam conjecture
Citations: Zbl 711.00008; Zbl 617.10037
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag