Problem Statement
Let $A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}$ be such that $\phi(a_1)<\cdots<\phi(a_t)$. The primes are such an example. Are they the largest possible? Can one show that $\lvert A\rvert<(1+o(1))\pi(N)$ or even $\lvert A\rvert=o(N)$?
Categories:
Number Theory Primes
Progress
Erdős remarks that the last conjecture is probably easy, and that similar questions can be asked about $\sigma(n)$.Solved by Tao [Ta23b], who proved that\[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]In [Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.
Source: erdosproblems.com/49 | Last verified: January 13, 2026