Monotone Nondecreasing Sequences of the Euler Totient Function

Let M ( x ) denote the largest cardinality of a subset of ∈ N: n ≤ x\ { n ∈ N : n ≤ x } on which the Euler totient function φ (n) φ ( n ) is nondecreasing. We show that M(x) = ( 1+O( (log log x)⁵/log x) ) π (x) M ( x ) = 1 + O ( log log x ) 5 log x π ( x ) for all x ≥ 10 x ≥ 10 , answering questions of Erdős and Pollack–Pomerance–Treviño. A similar result is also obtained for the sum of divisors function σ (n) σ ( n ) .