On the normal order of \(\varphi_{k+1}(n)/\varphi_k(n)\), where \(\varphi_k\) is the \(k\)-fold iterate of Euler's function (Q1881756)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the normal order of \(\varphi_{k+1}(n)/\varphi_k(n)\), where \(\varphi_k\) is the \(k\)-fold iterate of Euler's function |
scientific article |
Statements
On the normal order of \(\varphi_{k+1}(n)/\varphi_k(n)\), where \(\varphi_k\) is the \(k\)-fold iterate of Euler's function (English)
0 references
15 October 2004
0 references
Denote by \(\varphi_k\) the \(k\)-th iterate of Euler's function \(\varphi\). \textit{P. Erdős, A. Granville, C. Pomerance}, and \textit{C. Spiro} [Analytic Number Theory, Proc. Conf. in Honor of Paul Bateman, Boston 1990, Prog. Math. 85, 165--204 (1990; Zbl 0721.11034)] showed that \( \varphi_{k+1}(n)/\varphi_k(n)\) has the normal order \[ w_k(x) =\prod_{p < (\log\log x)^{k+1}} \left( 1 -{1\over p} \right). \] The authors' aim is to give an asymptotic formula for the number \[ N_k(Q,x) = \# \left\{ n\leq x; \; Q \nmid \varphi_{k+1}(n) \right\}, \] and for \[ N_k(Q_1,\dots,Q_r,\, x) = \# \{ n \leq x; \; \text{gcd}(Q_j,\, \varphi_k(n) ) = 1 \text{ for } j=1,\dots,r\}, \] where \(Q_1, \dots, Q_r\) are different primes. Using many techniques from analytic number theory (for example, the Brun-Titchmarsh theorem, the Bombieri-Vinogradov prime number theorem, an estimate for large values of certain iterated additive functions due to \textit{N. L. Bassily, I. Kátai} and \textit{M. Wijsmuller} [J. Number Theory 65, 226--239 (1997; Zbl 0878.11036)]), the authors prove: For fixed \(\varepsilon\) and \(k\geq 2\), the asymptotics \[ N_k(Q,x) = \rho_k(Q)\cdot x \cdot \left( 1 + O\left({1 \over {\log\log x}}\right)\right) \] holds in the range \((\log\log x)^{k+\varepsilon} \leq Q \leq (\log\log x)^{k+1 - \varepsilon}\). Here, \[ \rho_k(Q) = \prod_{p < x, \, \kappa_{k+1}(p) \not= 0} \left( 1 - {1\over p}\right), \] and the \(\kappa's\) are completely additive functions defined by\(\kappa_0(p) = 1\), if \(p=Q\), otherwise \(=0\), and \(\kappa_{j+1}(p) = \sum_{q\in {\mathcal P},\, q \mid (p-1)} \kappa_j(q)\). An asymptotic for \(\log \rho_k(Q)\) also is given. In the range \(\log\log\log x \cdot \log\log x \leq Q \leq (\log\log x)^2\) an asymptotic formula for \(N_1(Q,x)\) is given. For \(Q_1, \dots, Q_r \in [ (\log\log x)^{k+{1\over2} +\varepsilon}, \, (\log\log x)^{k+{1} - \varepsilon}]\), \(k\geq 2\), the authors prove \[ N_k(Q_1,\dots,Q_r,\, x) = x \rho_k(Q_1) \cdots \rho_k(Q_r) + \text{ remainder term}. \] Finally, if \(J_x\) is a sequence of intervals for which \(\sigma_k^2(J_x) = \sum_{Q\in J_x} \rho_k^2(Q) \to \infty\), \[ \lim_{x\to\infty} {1\over x} \cdot \# \left\{ n<x;\; {{\eta(n,J_x)}\over {\sigma_k(J_x)}} < z \right\} = \Phi(z) \quad\text{ (Gaussian law)}. \] Here, \[ \eta(n,J_x) = \sum_{Q\in J_x} (\xi_Q(n) - \rho_k(Q)), \] where \(\xi_Q(n) = 1\), if \(Q \nmid \varphi_{k+1}(n)\), and \(=0\) otherwise.
0 references
iterates of the Euler function
0 references
asymptotics for the number of integers for which \(\varphi_k(n)\) is not divisible by a given prime
0 references
Bombieri-Vinogradov prime number theorem
0 references