Monotone Nondecreasing Sequences of the Euler Totient Function

Abstract Let M (x) denote the largest cardinality of a subset of \n {N: n x\} n ∈ N: n ≤ x on which the Euler totient function (n) φ (n) is nondecreasing. We show that M (x) = (1+O ( (x) ⁵ 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).