Monotone Nondecreasing Sequences of the Euler Totient Function

Let M(x) denote the largest cardinality of a subset of \(\{n \in \mathbb {N}: n \le x\}\) $\{n\in \mathbb{N}:n\le x\}$ on which the Euler totient function \(\varphi (n)\) $\phi (n)$ is nondecreasing. We show that \(M(x) = \left( 1+O\left( \frac{(\log \log x)^5}{\log x}\right) \right) \pi (x)\) $M(x)=\left(1,+,O,\left(\frac{{(loglogx)}^5}{logx}\right)\right)\pi (x)$ for all \(x \ge 10\) $x\ge 10$ , answering questions of Erdős and Pollack–Pomerance–Treviño. A similar result is also obtained for the sum of divisors function \(\sigma (n)\) $\sigma (n)$ .