Monotone non-decreasing sequences of the Euler totient function

Abstract

Let $M(x)$ denote the largest cardinality of a subset of $\{n\in \mathbf{N}:n\le x\}$ on which the Euler totient function $\phi (n)$ is non-decreasing. We show that $M(x)=(1+O(\frac{(\log \log x{)}^5}{\log x}))\pi (x)$ for all $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)$.

23 pages. This is the final version, addressing referee comments